网站推荐

https://liuyehcf.github.io/categories/Compile-Principle/

程序分析过程

词法分析

语法分析

语义分析

中间代码生成

基本块和流图

基本块

中间代码可以划分为基本块(basic block)，每个基本块满足下列条件：

  1. 控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间的转移指令。
  2. 除了基本块的最后一个指令，控制流在离开基本块之间不会停机或跳转。

流图

基本块形成了流图(flow graph)的结点。流图的边指明了哪些基本块可能紧随一个基本块之后执行。

控制流分析和数据流分析

控制流分析

控制流分析(Control flow analysis)简称CFA，是一种确认程序控制流的静态代码分析技术。控制流程会以控制流图来进行表示。

数据流分析

数据流分析(Data flow anaysis)简称DFA，能从程序代码中收集程序的语义信息，并通过代数的方法在编译时确定变量的定义和使用。

过程内分析和过程间分析

过程内分析

过程内分析(intra-procedure analysis)，指每次都在一个过程(函数)内执行的分析。

过程间分析

过程间分析(inter-procedure analysis)处理的是整个程序，将信息从调用者传递到被调用者，或返向传送。主要有基于克隆和基于摘要的过程间分析方法。

调用图

一个程序的调用图(call graph)是一个结点和边的集合，满足：

  1. 程序中的每个过程都对应一个结点
  2. 对于每个调用点(call site)都有一个结点。所谓调用点就是程序中调用某过程的一个位置。
  3. 如果调用点c调用了过程p，就存在一条从c结点到p结点的边。

相关性(敏感性)

流敏感

流敏感(flow-sensitive)指的是考虑程序语句的执行顺序。例如，一个非流敏感的指针别名分析不考虑控制流，认为所发现的别名在程序的所有位置都成立。

路径敏感

路径敏感(path-sensitive)指的是依据条件分支的不同谓词，计算不同的分析信息。也就是说，路径敏感分析将跟踪控制流的每一个分之，以记录不同分支的不同程序状态。相应的，非路径敏感的分析并不考虑分支之间的区别。简单的路径敏感存在“路径爆炸”(path explosion)或“无穷搜索空间”(infinite search space)的问题。

上下文敏感

上下文敏感(context-sensitive)指的是在过程间分析时，考虑函数调用的上下文信息。

指针分析

别名分析