各类图的生成

一般来说，完整的编译过程会经历：对源代码进行词法、语法、语义的分析，生成AST，接着转换为IR，生成CFG、CG等，对数据流进行分析、优化，生成目标代码。

AST

AST， Abstract Syntax Tree 抽象语法树，是用来表示程序代码结构的树形数据结构。

源码与AST之间的转换关系是：

1. 通过编译器或解析器进行词法分析、语法分析、语义分析等操作，生成AST
2. AST也可以通过代码生成器或泛解析器进行优化、转换、翻译等操作，转换生成源码

词法分析：scanner和分词器。Scanner会从头到尾去扫描源代码文件，把文本拆成单词；之后这些单词会传入分词器，经过一些列识别器（关键字识别器、标识符识别器、常量识别器、操作符识别器等），识别确认单词的词性，生成一个<type, value>形式的二元组token序列（组合里的type指单词种类，value则是属性值）

语法分析：

token序列会传递给解析器，根据给定的语法规则，由其识别出代码中的各类短语并根据语言的文法规则来生成解析树

语义分析：

对抽象语法树进行下一步的检查和处理。其主要目的是为了确定源码是否有意义，同时也可以对源代码进行一些优化和转换。

转换工具如下AST explorer

IR

IR,中间代码(Intermediate Representation,有时也称为Intermediate Code,IC)，它是编译器中很重要的一种数据结构。编译器在做完前端工作以后，首先就生成IR,并在此基础上执行各种优化算法，最后再生成目标代码。

通常情况下，IR有两种用途，一种用来做分析和变换，一种用于解释执行。在编译器中，基于 IR 的分析和处理工作，一开始可以基于一些抽象层次比较高的语义，这时所需要的 IR 更接近源代码。而在后面，则会使用低层次的、更加接近目标代码的语义。基于这种从高到底的抽象层，IR可以归结为HIR/MIR和LIR三类

HIR

基于语言做一些分析和变换。例如你要开发一款 IDE，那最主要的功能包括：发现语法错误、分析符号之间的依赖关系（以便进行跳转、判断方法的重载等）、根据需要自动生成或修改一些代码（提供重构能力）。

MIR

独立于源语言和CPU架构做分析和优化，这些优化包括部分算术优化、常量和变量传播、死代码删除等。因为MIR跟源代码和目标代码都无关，所以在讲解优化算法时，通常是基于MIR,比如三地址代码(Three Address Code,TAC)

示例如下：

int foo (int a){
  int b = 0;
  if (a > 10)
    b = a;
  else
    b = 10;
  return b;
}

对应的TAC为

BB1:
  b := 0
  if a>10 goto BB3   //如果t是false(0),转到BB3
BB2:
  b := 10
  goto BB4
BB3:
  b := a
BB4:
  return b

可以看到，TAC 用 goto 语句取代了 if 语句、循环语句这种比较高级的语句，当然也不会有类、继承这些高层的语言结构。但是，它又没有涉及数据如何在内存读写等细节，书写格式也不像汇编代码，与具体的目标代码也是独立的。

LIR

这类IR的特点，是它的指令通常可以与机器指令一一对应，比较容易翻译成机器指令(或汇编代码)。因为LIR体现了CPU架构的底层特征，因此可以做一些于具体CPU架构相关的优化。

比如，下面是 Java 的 JIT 编译器输出的 LIR 信息，里面的指令名称已经跟汇编代码很像了，并且会直接使用 AMD64 架构的寄存器名称。
Java的JIT编译器的LIR：

编译过程可以理解为，抽象层次高的 IR 一直 lower 到抽象层次低的 IR 的过程，并且在每种 IR 上都会做一些适合这种 IR 的分析和处理工作，直到最后生成了优化的目标代码

CFG

概念：控制流图（control-flow graph）简称CFG，是计算机科学中的表示法，利用数学中图的表示方式，标示计算机程序执行过程中所经过的所有路径。CFG是从IR生成来的，是一种用来表示程序代码执行流程的图形数据结构；可以这么说，CFG是IR的一种变形，它把代码分给为基本块，并用边表示基本块之间的跳转关系。

使用angr生成CFG代码如下

import angr
from angrutils import *
 
p = angr.Project(程序路径)
 
#使用快速生成方法生成CFG
cfg = p.analyses.CFGFast()
 
#使用完整生成方法生成CFG
cfg1 = p.analyses.CFGEmulated()
 
#调用angr-utils库可视化
plot_cfg(cfg1, "生成的cfg文件名", asminst=True, remove_imports=True, remove_path_terminator=True)  
 
 

CG

概念：调用图，一种有向图，表示计算机程序中调用和调用子例程之间的关系，用于代码分析。

两种CG，一种是动态，一种是静态。静态：静态调用图是用于表示程序的每个可能运行的调用图。确切的静态调用图是一个不可判定的问题，因此静态调用图算法通常是过度的。也就是说，发生的每个调用关系都表示在图中，并且可能还有一些在程序的实际运行中永远不会发生的调用关系。动态：动态调用图只描述程序的一次运行。

angr生成程序的CG代码如下

p = angr.Project(文件路径)
cfg = p.analyses.CFGFast()
cg = cfg.functions.callgraph
#cg即是函数调用图

CDG

控制流依赖图

示例代码

import angr
 
b = angr.Project(文件路径)
 
 
cfg = b.analyses.CFGEmulated(keep_state=True, 
                           state_add_options=angr.sim_options.refs, 
                            context_sensitivity_level=2)
 
# 生成控制流依赖图
cdg = b.analyses.CDG(cfg)
 

DDG

数据依赖图，两个句子存在数据依赖：一条语句中一个变量的定义，可以到达另一条语句中对该变量的使用

代码示例

import angr
 
b = angr.Project(文件路径)
 
 
cfg = b.analyses.CFGEmulated(keep_state=True, 
                           state_add_options=angr.sim_options.refs, 
                            context_sensitivity_level=2)
 
 
# 生成数据流依赖图
ddg = b.analyses.DDG(cfg)

打赏