淘先锋技术网

首页 1 2 3 4 5 6 7

参考资源:
百度百科:
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
过程的例子以及设计流函数的过程也看这篇文章
在这里插入图片描述