鲸书阅读笔记-------第八章数据流分析（四）常见数据流问题以及求解方法

本篇介绍

1）数据流分析问题归类尺度有哪些

2）与程序优化有关的数据流分析问题有哪些，以及格，位向量、数据流方向等描述。

3）解决数据流分析的方法有哪些

归类尺度

1。他们所提供的信息；

2. 他们是有关系的还是属性无关的;

3.他们使用的格的类型，以及格元素所代表的含义和在这些格上定义的函数

4.信息流的方向：按程序执行的方向（向前问题）、程序执行的反方向（后向问题），还是同时两个方向（双向问题）。

数据流分析问题分类

1.到达-定值（reaching definition）

     1）到达-定值问题确定过程中一个变量的那些定值（即对它的赋值）可以达到该变量的各个使用；

     2）向前问题；

     3）使用位向量的格。其中位向量的每一位对应变量的一个定值。

2.可用表达式（available expression）

     1）可用表达式问题确定在过程的每个点上那些表达式是可用的，在某点可用的含义是指：从入口到该点的每一条路径上存在着该表达式的一个计算，并且在此路径上的这个计算之后到该点之间，出现在该表达式中的所有变量都没有被重新赋值，

     2）向前问题

     3）使用位向量上的格，其中，位向量的每一位对应表达式的一个定值，

3.活跃变量（live variable）

     1）对于给定的变量和程序中给定的点，活跃变量问题确定沿着此点到出口路径上是否存在对该变量的使用。

     2）后向问题

    3）使用位向量上的格，变量的每一个使用在位向量中有一个位置。

4.向上暴露使用(upwards exposed use)

   1）确定在特定点上哪些变量的使用可以由特定的定值到达。

   2）后向问题

   3）一个变量的每一个使用在位向量中有对应一位.

 与到达-定值的区别：

向上暴露使用是到达-定值的对偶问题，到达-定值连接定值到使用，向上暴露使用连接使用到定值。

注意这两者是不同的，如图8-5所示，其中x在B2中的定值到达B4和B5的使用，而在B5中的使用是由B2和B3中的定值所到达的。

理解：根据程序流向不同，侧重点不一样。到达-定值是向前（沿着程序流的方向），对变量的定值可以到达某个后继程序点（也可以说到达哪个基本块）。向上暴露使用是向后（逆着程序流的方向），对变量的使用是由某个前驱程序点定值的。

5.常数传播分析（constant-propagation analysis）

  1） 确定从对一个变量的常数赋值，比如x=const，到x的一个使用的每一条路径上，对x的赋值都只是此常数值const。

  2）向前流问题

  3）使用格ICP，每个定值都有一个格值，并且是符号执行。

上图表示了一个整数类型变量的所有可能“取值”的半格

6.部分冗余分析(partial-redundancy analysis)

     1) 确定在某条执行路径上被执行了两次（或多次），而其操作数在这些计算之间没有修改过的那些计算。

     2）双向问题

    3）位向量的每一位表示一个表达式计算

解数据流问题的方法

 1。简单迭代法，包含关于确定迭代次序的若干策略

2。消去法或利用区间的基于控制树的方法

3。使用结构分析的基于控制数的方法。

本博客主要介绍迭代数据流分析，因为其最容易实现，并且是最频繁使用的方法。