Interprocedural Analysis

过程间分析简介

本小节通过四个部分介绍过程间分析。

1. Motivation
   • 为什么 要引入过程间分析？
2. Call Graph Construction (CHA)
   • 介绍一个过程间分析 必要的数据结构Call Graph
   • 当前有数种方法来构建Call Graph，本节介绍其中速度最快的一种（Class hierarchy analysis，简称CHA）
3. Interprocedural Control-Flow Graph
   • 之前的章节关注CFG，引入过程间分析后，我们向CFG中添加相应的元素，得到过程间的控制流图（ICFG）
   • 讨论由于添加了新元素而需要增加的操作
4. Interprocedural Data-Flow Analysis
   • 通过一个例子（也就是实验一中做的常量传播分析）来总结过程间分析

DFA-FD

Iterative Algorithm, Another View

给定一个有 k 个节点的 CFG，迭代算法会更新每个节点 n 的 OUT[n] 值。那么就可以考虑把这些值定义为一个 k-tuple：

则，我们的数据流分析迭代算法框架就可记为

迭代过程就被记为：

• ...

• 此时我们发现，意味着就是的一个不动点。

DFA-AP

数据流分析总揽

数据流分析的核心：How Data Flows on CFG?

将这句话展开来，所谓数据流分析就是：

How application-specific Data (对数据的抽象：+, -, 0 等……)

Flows (根据分析的类型，做出合适的估算) through the

Nodes (数据如何 transfer, 如 + op + = +) and

Edges (控制流如何处理，例如两个控制流汇入一个BB) of

CFG (整个程序) ?