Compilers and Static Analyzers（编译器与静态分析）
静态分析基本都是基于 IR 来做的，这就是编译与静态分析的关系
AST vs. IR（抽象语法树与中间代码）
AST：
- 具有高层次和封闭的语法结构
- 通常和语言相关
- 适合快速类型检测
- 缺乏控制流信息
IR：
- 低级和封闭的机器代码
- 通常独立于具体的高级语言
- 结构紧凑统一
- 包含控制流信息
- 通常被认为是静态分析的基础
IR: Three-Address Code (3AC)（三地址码）
定义：最多一个操作符，地址可以是变量名，常量，编译器临时变量
Static Single Assignment (SSA)（静态单赋值）
SSA 中的所有赋值都是对具有不同名称的变量的赋值
- 给每个定义一个新的名称
- 将新的名称传播给后续使用
- 每个变量只有一个定义
- 对于控制流无法确定用哪一个变量，引入一个特殊的合并运算符来选择合并节点上的值
- 对于 ∅(x0,x1)，如果控制流通过条件为真，则值为 x0，否则为 x1
优点：
- 流信息被间接地合并到唯一的变量名中
- 有助于提供一些更简单的分析，例如，流不敏感分析通过 SSA 获得流敏感分析的部分精度
- 在一些特点需求的任务中支持更有效的 data fact 存储和传播
- 一些优化任务在 SSA 上执行得更好(例如，条件常数传播，全局值编号)。
缺点：
- SSA 可能会引入太多的变量和临时函数
- 在转换为机器码时可能会引入效率低下的问题(由于复制操作)
Basic Blocks (BB)（基本块）
定义：是一个连续三地址指令的最大序列组成的块，这个序列满足：入口唯一，出口唯一
基本块构建算法：（现在不考虑包含方法调用的控制流图）
-
输入：程序 P 的三地址码序列
-
输出：程序 P 的一系列基本块
-
流程：
-
（1）确定各个基本块的 leader
P 的第一条指令是一个 leader
任何无条件或者有条件跳转的目标指令是一个 leader
任何紧跟在无条件或者有条件跳转指令之后的指令都是 leader
（2）一个基本块有一个 leader 和所有后续指令组成，直至下一个 leader
Control Flow Graphs (CFG)（控制流图）
组成：
节点：一个基本块（通常要加上一个 entry 节点（这个在第一个基本块前）和多个 exit 节点（这个跟着每一个出现的 return 后））
边：从一个基本块连向下一个基本块
- 从 a 的结尾到 B 的开头有一个条件或无条件的跳转
- B 立即按照原指令顺序跟随 A，并且 A 不会以无条件跳转结束
重点问题
1.编译器和静态分析器之间的关系
编译器是一种将高级程序代码（如 C、C++、Java 等）转换为底层机器代码（如汇编语言或机器语言）的工具。编译器执行词法分析、语法分析、语义分析、优化和代码生成等阶段，以生成可执行的机器代码。编译器主要关注将源代码转化为可执行代码，以便在计算机上运行程序。
静态分析器则是一种用于对程序进行静态分析的工具。静态分析是在不执行程序的情况下，对程序源代码或二进制代码进行分析，以推断程序的性质、行为或错误。静态分析器可以用于检测潜在的编程错误、漏洞、代码质量问题等，以及进行程序验证和优化。
关于编译器和静态分析器之间的关系，可以有以下几个方面的联系：
- 编译器可以包含静态分析的功能：现代编译器通常具备一些静态分析的功能，用于检查代码的语法错误、类型错误、未初始化变量、不可到达代码等。这些静态分析功能帮助编译器在编译过程中提供更严格的错误检查，并生成更可靠的目标代码。
- 静态分析器可以使用编译器的工具链：静态分析器可以利用编译器提供的工具链和中间表示（如抽象语法树、中间代码表示），从而更方便地进行静态分析。静态分析器可以使用编译器的前端组件（如词法分析器和语法分析器）解析源代码，并利用编译器的优化和代码生成技术分析代码结构和性质。
-
静态分析器可以为编译器提供信息：静态分析器可以对程序进行更深入的静态分析，以推断程序的行为、性能瓶颈、代码优化机会等。这些信息可以用于优化编译器的代码生成过程，提高生成的机器代码的质量和性能。
-
编译器和静态分析器的相互补充：
- 编译器主要关注将源代码转换为可执行代码，以便在计算机上执行。它执行词法分析、语法分析、语义分析、优化和代码生成等步骤，以生成目标代码。
- 静态分析器则关注对程序源代码或二进制代码进行静态分析，以推断程序的性质、行为或错误。它可以检测代码中的潜在问题，如空指针解引用、资源泄漏、并发问题等。
- 编译器和静态分析器在软件开发过程中相互补充。编译器可以提供语法和语义检查，以及一些基本的静态分析功能。而静态分析器可以执行更深入的代码分析，发现更复杂的问题，并提供优化建议。
-
静态分析在编译器中的应用：
- 静态分析技术在编译器中有广泛的应用。例如，编译器可以使用静态分析来进行代码优化，如常量折叠、无用代码消除、循环展开等。静态分析可以提供有关代码的信息，帮助编译器进行更有效的优化。
- 静态分析还可以用于进行代码质量分析和性能分析。通过静态分析，可以检测代码中的潜在问题，如代码规范违规、复杂性过高等。静态分析还可以识别性能瓶颈和潜在的优化机会，帮助编译器生成更高效的代码。
-
静态分析器的独立应用：
- 静态分析器也可以作为独立工具使用，与编译器分开。这些独立的静态分析器可以针对特定的代码质量、安全性或性能问题进行分析。它们可以提供更全面的静态分析功能，并生成有关代码的详细报告。
- 静态分析器还可以用于进行程序验证和漏洞检测。通过对程序进行静态分析，可以发现代码中的潜在漏洞和安全风险，如缓冲区溢出、代码注入、访问控制问题等。
- 互补的工具链：
- 编译器和静态分析器可以在工具链中相互配合。例如，编译器可以将生成的中间表示形式（如抽象语法树、中间代码）提供给静态分析器，作为其输入。静态分析器可以利用这些中间表示形式来进行更高级的静态分析。
- 反过来，静态分析器可以为编译器提供有关代码的信息和建议。这些信息可以用于改进编译器的优化和代码生成策略，从而生成更高质量的目标代码。
总的来说，编译器和静态分析器虽然有一些联系，但它们的主要关注点和目标不同。编译器旨在将高级代码转换为可执行代码，而静态分析器则旨在通过对源代码或二进制代码的分析，提供一些关于程序性质、行为和错误的信息。两者在软件开发过程中可以相互辅助，共同提高代码的质量和可靠性。
2.了解 3AC 及其常见形式
三地址码是一种中间代码表示形式，用于在编译器和解释器中表示程序的执行过程。它将每个表达式转换为一个或多个三地址指令，其中每个指令最多包含三个操作数。
三地址码的常见形式如下：
-
三地址指令：三地址指令是三地址码的基本构建块，它包含一个操作符和一个或多个操作数。操作符表示执行的操作，如赋值、算术运算、逻辑运算等。操作数表示参与操作的变量、常量或内存位置。
-
赋值语句：赋值语句是最常见的三地址码形式之一。它使用赋值操作符将一个表达式的结果存储到一个变量中。例如，将表达式 “a = b + c” 转换为三地址码可以表示为 “t1 = b + c”，然后再将 “t1” 的值赋给变量 “a”。
-
算术运算：三地址码可以表示各种算术运算，如加法、减法、乘法和除法。例如，将表达式 “a = b + c _ d” 转换为三地址码可以表示为 “t1 = c _ d”，然后再将 “b + t1” 的结果赋给变量 “a”。
-
逻辑运算：三地址码还可以表示逻辑运算，如与、或、非等。例如，将表达式 “a = (b && c) d” 转换为三地址码可以表示为 “t1 = b && c”，然后再将 “t1 d” 的结果赋给变量 “a”。 -
条件语句：条件语句在三地址码中通常表示为跳转指令。例如，将条件语句 “if (a > b) then x = y else x = z” 转换为三地址码可以表示为 “if a > b goto L1”，然后再将 “x = y” 和无条件跳转指令 “goto L2” 放在标签 “L1” 的位置，最后将 “x = z” 放在标签 “L2” 的位置。
- 标签：标签用于标识代码中的跳转目标，例如条件语句中的跳转指令。标签在三地址码中通常以某种形式表示，如 “L1:”。
需要注意的是，上述形式只是三地址码的常见表示形式之一，实际上三地址码的具体形式和格式可以根据编译器或解释器的设计和需求而有所不同。三地址码的目的是提供一种简单且易于理解的中间代码表示形式，以便进行后续的优化和代码生成。
3.如何在 IR 之上构建基本块
-
输入：程序 P 的三地址码序列
-
输出：程序 P 的一系列基本块
-
流程：
-
（1）确定各个基本块的 leader
P 的第一条指令是一个 leader
任何无条件或者有条件跳转的目标指令是一个 leader
任何紧跟在无条件或者有条件跳转指令之后的指令都是 leader
（2）一个基本块有一个 leader 和所有后续指令组成，直至下一个 leader
4.如何在基础块之上构建控制流图？
组成：
节点：一个基本块（通常要加上一个 entry 节点（这个在第一个基本块前）和多个 exit 节点（这个跟着每一个出现的 return 后））
边：从一个基本块连向下一个基本块
- 从 a 的结尾到 B 的开头有一个条件或无条件的跳转
- B 立即按照原指令顺序跟随 A，并且 A 不会以无条件跳转结束