当先锋百科网

首页 1 2 3 4 5 6 7

【静态分析】简述IR中介码、SSA Form（静态单赋值形式）、IFDS，涉及Graph中支配点、支配边界的含义

参考资源：
百度百科：
SSA
知乎：
【南大软件分析】lecture15 笔记-CFL Reachability and IFDS
IR和ByteCode有什么区别
方舟编译器学习笔记66 Dominance中的支配树和支配边界计算
方舟编译器学习笔记64 MeFuncPhase之ssa分析

CSDN：
静态单赋值（SSA）
这篇讲的很好
IR中间码学习（基于llvm3.3）
源代码转换成图-控制流图、数据流图

如果需要看更具体的内容可以查看上述资源，本文整理简单的概念

1. 中介码（中间码）（IR，intermediate representation)

  • IR在编译器中承担承前启后的角色
    • 编译器前端对源程序进行语法和语义分析，生成IR
    • 编译器后端将IR汇编成对应的机器指令
    • 编译器中大部分的优化都是在IR上完成的
  • 常用的字节码Bytecode是一种IR（中间表示）的形式，编译器所使用的IR可以有很多种形式
    • 基于图：基于树 基于DAG（有向无环图） 基于一般图
    • 基于线性代码的，常见的情况有：三地址代码（四元组）二地址代码（三元组）零地址代码
    • 基于图与线性代码混合的，最常见的情况是控制流图（CFG）用图表示，而CFG的每个节点是基本块，每个基本块里的代码是线性代码

2. 静态单赋值形式（static single assignment form，简写为SSA form或是SSA）

2.1 SSA是中介码IR的特性，每个变数仅被赋值一次

2.2 SSA的用途

  • 最主要的用途，是借由简化变数的特性，来进行简化及改进编译器最佳化的结果
    y := 1 y := 2 x := y
    第一行赋值行为是不需要的。
    y在第二行被二度赋值，y的数值在第三行被使用，一个程式通常会进行定义可达性分析（reaching definition analysis）来测定它。在SSA下，将会变成下列的形式：
    y1 := 1 y2 := 2 x1 := y2
  • 其它用途
    在这里插入图片描述

2.3 利用支配边界计算出最小的SSA

静态单赋值（SSA） 这里面支配边界和支配点定义的更好

  • Graph中支配点（Dominator）：当一个点A到点B在控制流程图中，如果没有其他的路线，那么A及B就是支配点。这是相当有用的，因为如果程式进行到B就代表着A一定也会执行到，我们可以说A支配着B（B也支配着A）
  • 支配边界：如果A没有直接支配着B但是支配着一个B的前置程序，则节点B就是点A的支配边界（有可能点A是点B的前置程序，那么，因为任何一个点都支配着自己，点A也支配着自己，所以点A也是点B的支配边界）【感觉这里有点问题】，从A的观点来看，还有点在其他没有经过A的控制路径，可以使他们更早出现。
  • 下图截自百度百科
    在这里插入图片描述

3.IFDS(Interprocedural，Finite，Distributive，Subset Problem)

3.1 不可行路径Infeasible path 可实现路径Realizable path CFL技术（context free language）

3.2 IFDS的含义

  • IFDS是一种基于图可达性的程序分析框架。
  • 这个框架适用的问题范围：
  1. 全程序（跨函数）的
  2. 分析对象的域是有限的
  3. 流函数满足分配律

必须满足以上条件才可以使用IFDS解决
IFDS将程序看作一个图，并通过对图上的可达性来求解诸如到达定义这类静态分析问题。

下图来自【南大软件分析】lecture15 笔记-CFL Reachability and IFDS
过程的例子以及设计流函数的过程也看这篇文章
在这里插入图片描述