程序编译过程
源码首先经过Scanner/Lexer做词法分析成为token stream,接着,再经过parser做语法分析成为AST抽象语法树,对于大多数语言来说,接下来的一步是类型检查Type checker,然后,Translator将经过检查的Decorated AST转化为较底层的表示法IR,我们一般直接在IR上面做静态分析完成code optimization之类的功能,最后,code generator将优化之后的IR转化为底层machine code。
IR
中间表示Intermediate Representation。
通常与具体语言无关,控制流信息在IR中能够得到一定程度的表示。
AST与IR的区别
3-Address Code(3AC)
特点:一条指令中最多出现3个地址,右值只能有一个、
这里Address可以是:
- Variable name: x, y
- Constant: 3
- Compiler-generated temporary: t1, t2
如果有类似于x = 1 + 2 + 3的语句,就需要改为t1 = 1 + 2; x = t1 + 3;
Java Static Analysis Framework-Soot
IR: Jimple
https://github.com/soot-oss/soot
对于Helloworld类,可以通过java -cp soot-4.2.1-jar-with-dependencies.jar soot.Main -cp . -pp HelloWorld -f j
将编译后的源码转化为Jimple结构,可以看到Jimple结构还是根据java做了特化的。
class HelloWorld {
public static void main(String[] args) {
System.out.println("Hello, World!");
}
}
class HelloWorld extends java.lang.Object
{
void <init>()
{
HelloWorld r0;
r0 := @this;
specialinvoke r0.<init>();
return;
}
public static void main(java.lang.String[])
{
java.io.PrintStream $r0;
java.lang.String[] r1;
r1 := @parameter0;
$r0 = java.lang.System.out;
$r0.println("Hello, World!");
return;
}
}
SSA
基本结构还是3AC Code,但SSA把每个赋值都视为产生新的变量
e.g:
对于这种情况下,translator就不明白x到底应该对应哪个分支的x,此时就引入phi-function。
优点:
- variable names中实际上有控制流图本身的信息。
- Define-and-Use Pairs是被直接定义出来了。
缺点:可能引入过多变量;使得翻译为机器码时效率下降。
Control Flow Analysis
Basic Blocks定义:
Basic blocks (BB) are maximal sequences of consecutive three-address instructions with the properties that
- It can be entered only at the beginning, i.e., the first instruction in the block
- It can be exited only at the end, i.e., the last instruction in the block
构建basic blocks
- method中第一句
- jump
- jump目的地
能构建边的情况:
- A能够jump到B
- B在A后,A不是unconditional jump
此外,一般还要再加一个Entry,一个Exit
相关术语:
conditional/unconditional jump
predecessor, successor