精华内容
下载资源
问答
  • 论文《编译系统中数据流分析研究》
  • 数据流分析 PAGE 4 [文档标题 数据流分析-说课稿 编号 幻灯片 说课稿 幻灯片01 今天我们来学习白盒测试方法中的数据流分析 幻灯片02 数据流分析最初是随着编译系统要生成有效的目标码而出现的是一组用来获取有关数据...
  • 数据流分析(一)

    万次阅读 2016-02-21 17:25:12
    引子编译器后端会对前端生成的中间代码做很多优化,也就是在保证程序...所以掌握数据流分析编译后端极为重要。 何为数据流分析 数据流抽象 数据流分析模式 基本块上的数据流模式 何为数据流分析 数据流分析指的是一

    想学数据流分析的人还是找一个国外大学的讲义学吧,以下内容都是自己多年前按照自己的理解写的,很多内容可能会误人子弟,sorry


    引子

    编译器后端会对前端生成的中间代码做很多优化,也就是在保证程序语义不变的前提下,提高程序执行的效率或减少代码size等优化目标。优化需要依靠代码分析给出的“指导信息”来相应地改进代码,而代码分析中最重要的就是数据流分析。另外数据流分析是程序静态分析的基础。所以掌握数据流分析对编译后端极为重要。

    • 何为数据流分析
    • 数据流抽象
    • 数据流分析模式
    • 基本块上的数据流模式

    何为数据流分析

    数据流分析指的是一组用来获取有关数据如何沿着程序执行路径流动的相关信息的技术. 《编译原理》

    数据流分析的目的是提供一个过程(或一大段程序)如何操纵其数据的全局信息. 《高级编译器设计与实现》

    从上面的表述中,我们可以看出数据流分析通过静态代码来**“推断”**程序动态执行的相关信息,数据流分析并不真正执行程序。虽然数据流分析和符号执行在某些方面比较相似,但还是两种完全不同的概念,更确切的说数据流分析是符号执行的基础。

    数据流分析和符号执行从某些方面都很相似,例如符号执行有程序点(ProgramPoint)的概念,并且在当前程序点存储着程序运行到此刻的所有状态和值信息(一般情况下不会维护历史程序点的信息,开销太大)。数据流分析中也有程序点的概念,程序点存储着数据流信息。两者都是在CFG(Control Flow Graph)图的基础上,进行的分析。Clang的静态分析示意图如下所示,Clang会时刻维护符号执行当前的状态和内存信息。从这一点上看,符号执行和虚拟机更为相似。

    这里写图片描述

    但数据流分析和符号执行还是不同的,虽然都有程序点,但程序点存储的信息却是两个不同的概念。数据流分析中程序点存储的是数据流值,这些数据流值是和具体的数据流问题相关的,有可能是当前程序点的定值信息,也有可能是可用表达式信息,这些信息标识着该程序内含的一些属性。符号执行中程序点存储的是程序符号执行到此处的所有状态和值信息,这些信息和程序运行更为相关。

    而且两者的分析方法也不同,符号执行是单次执行,而数据流分析大多采用迭代分析的框架,然后在迭代分析的过程中不断更新程序点的数据流信息,最终得到比精确解更小(更保守)的解。但为了进行更为激进的优化,要求数据流分析在保证保守的同时又尽可能是激进的。


    数据流抽象

    前面的文章中我们也提到过,程序的执行可以看作是程序状态的一系列转换。程序状态是由程序中所有变量的值以及运行时栈帧上的相关值组成。程序语句对应着转换函数,将前一个程序点的输入程序状态转换到下一个程序点的新的输出状态。

    这里写图片描述

    上图所示中的红点表示的就是程序点,数据流转换函数就是作用在程序点上的状态,并沿着程序路径一步步进行的。其实这个过程就是一个自动机,抽象出的自动机如下图所示。程序点代表自动机中的一个节点,程序语句或者说是转换函数代表自动机中的一条边。一般来说,一个程序有无穷多条可能的执行路径,执行路径的长度并没有上界(例如死循环)。程序分析可以推断出各个程序点的程序状态(有穷的特性集合),当然很少有哪种数据流分析会用到所有的数据流信息,一般只是提取出感兴趣的特性集合进行分析。

    这里写图片描述

    我们考虑的多数数据流分析问题关注的是各种程序对象(常数,变量,定值,表达式等)的集合,以及在过程内任意一点这些对象的什么集合是合法的有关判断。另外在数据流分析中,一般是会忽略掉路径条件判断的,也就是说默认所有路径都可达(这种近似是正确且有效的,现在我还没有找到忽略控制条件也能够保证数据流分析正确性的证明!),在程序分析中忽略掉程序控制条件,所以核心的部分就是状态数据如何变化了,也就是数据流分析。

    我们虽然可以对过程的控制流图进行数据流分析,但通常更有效的做法是将它分解为局部数据流分析全局数据流分析,局部数据流分析针对每一个基本块进行,全局数据流分析针对控制流图进行分析,其实就是一个粒度问题。我们可以将同一个基本块内的各个语句的作用综合起来合成整一个基本块的作用。例如我们可以将上面的自动机改造为基于基本块的形式,如下图所示。

    这里写图片描述


    数据流分析模式

    在数据流分析中,程序点一般和数据流值(data-flow value)关联起来,注意这个数据流值不是程序中变量的值。“这个值是在该点可能观察到的所有程序状态的集合的抽象表示”,这句话说起来有点绕口,每个数据流分析问题都有其对应的值域,每个程序点的数据流值都是该值域的子集。比如,到达定值的数据流值的域是程序的定值集合的所有子集的集合。某个数据流值是一个定值的集合,数据流分析的目的就是推导出所有程序点与其对应的到达定值的集合。

    一个定值是对某个变量的赋值。可能沿着某条路径到达某个程序点的定值称为到达定值(reaching definition)。

    我们把每个语句s之前和之后的数据流值分别记为***IN***[s]和***OUT***[s]。数据流问题就是对一组约束求解,得到所有IN[s]和OUT[s]的结果。

    这里写图片描述

    每个语句都约束了该语句之前程序点状态和之后程序点状态的关系,也就是说语句s限定了IN[s]和OUT[s]之间的关系。整个程序就是由无穷个这样的约束构成的。数据流问题(data-flow problem)就是对这一组约束求解,另外约束不仅有语义(传递函数)上的约束,更有基于控制流的约束。

    传递函数

    在一个语句之前和之后的数据流值受该语句语义的约束,也就是程序语句前后程序点的数据流值受该语句语义的约束,这种约束关系成为传递函数(transfer function)

    传递函数有两种风格:数据流信息可能沿着执行路径向前传播,或者沿着程序路径逆向流动,相应的就有前向(forward)数据流问题后向(backward)数据流问题

    Forward data-flow analysis, Information at a node is based on what happens earlier in the flow graph.
    Backward data-flow analysis, Information at a node is based on what happens later in the flow graph.

    大部分人刚接触到后向数据流问题时会比较困惑,数据流值怎么会依赖于后面的数据流值信息呢。其实这是由于有些人还是对于数据流值的概念不是很理解,将数据流值简单的归结于变量的值,如果这么对比的话,就会出现矛盾

    对于前向数据流问题,一个程序语句s的传递函数以语句前程序点的数据流值作为输入,并产生出语句之后程序点对应的新数据流值。例如到达定值就是前向数据流问题。

    这里写图片描述

    对于后向数据流问题,一个程序语句s的传递函数以语句后的程序点的数据流值作为输入,转变成语句之前程序点的新数据流值。例如活变量分析就是后向数据流问题。

    这里写图片描述

    控制流约束

    第二组关于数据流值的约束是从控制流中得到的,基本块内都是顺序执行,没有控制流的约束。但是基本块之间有相应的控制流约束,例如一个基本块的最后一个语句和后继基本块的第一个语句之间的约束,这些约束比较复杂。

    ##基本块上的数据流模式
    前面我们已经提到过程序语句的约束分为两种,基于程序语句语义的约束和基于控制流的约束。基本块之间的约束都是基于控制流的约束,由于基本块内没有分支,所以我们可以基于整个基本块来描述基本块对于数据流值的约束,而不是基于程序语句(前面也提到过,我们可以使用局部数据流和全局数据流分析结合更加高效)。我们以基本块为最小单位来研究基本块上的数据流模式。

    这里写图片描述

    基本块的传递函数和基本块内程序语句所表示的传递函数之间的关系如上图所示。那么基本块之间的约束是如何的呢?如下图所示。

    这里写图片描述

    图中展示出来的是基本块之间的前向数据流问题的约束方程。后向数据流问题的方程如下图所示。

    这里写图片描述

    数据流分析就是根据这一组约束,得到一个满足这些约束的解。和线性算术方程不同,数据流方程通常没有唯一解。数据流分析的目标是寻找一个最“精确的”满足这两组约束(即控制流和传递函数)的解,当然这个解必须是保守的,能够保证我们根据这个解进行代码优化不会导致不安全的转换。

    当然数据流分析,不是直接联立方程求解的,一般是通过一种迭代分析的方法来求解的。

    这里写图片描述

    在下一篇文章中我们继续分析到达定值、活变量和可用表达式的数据流分析实例。

    展开全文
  • 大部分全局优化都是数据流分析实现的,讲了到达定值分析,到达定值方程的计算(到达 IN 值表,ud链)。

    本次笔记内容:
    8-5 数据流分析
    8-6 到达定值分析
    8-7 到达定值方程的计算

    本节课幻灯片,见于我的 GitHub 仓库:第17讲 代码优化_2.pdf

    数据流分析

    数据流分析(data-flow analysis)

    数据流分析:一组用来获取程序执行路径上的数据流信息的技术。

    数据流分析应用:

    • 到达-定值分析(Reaching-Definition Analysis)
    • 活跃变量分析(Live-Variable Analysis)
    • 可用表达式分析(Available-Expression Analysis)

    在每一种数据流分析应用中,都会把每个程序点和一个数据流值关联起来。

    数据流分析模式

    语句的数据流模式

    • IN[s]IN[s]:语句s之前的数据流值
    • OUT[s]OUT[s]: 语句s之后的数据流值
    • fsf_s:语句s的传递函数(transfer function)
      • 一个赋值语句s之前和之后的数据流值的关系
      • 传递函数的两种风格
        • 信息沿执行路径前向传播(前向数据流问题)
          OUT[s]=fs(IN[s])OUT[s] = f_s(IN[s])
        • 信息沿执行路径逆向传播(逆向数据流问题)
          IN[s]=fs(OUT[s])IN[s] = f_s(OUT[s])
    • 基本块中相邻两个语句之间的数据流值的关系
      • 设基本块B由语句s1,s2,,sns_1, s_2, … , s_n顺序组成,则
        IN[si+1]=OUT[si]i=1,2,,n1IN[s_{i+1}]= OUT[s_i] i=1, 2, … , n-1

    基本块上的数据流模式

    到达定值分析

    定值(Definition):变量x的定值是(可能)将一个值赋给x的语句

    到达定值(Reaching Definition):

    • 如果存在一条从紧跟在定值d后面的点到达某一程序点p的路径,而且在此路径上d没有被“杀死” (如果在此路径上有对变量x的其它定值d′,则称变量x被这个定值 d′ “杀死”了) ,则称定值d到达程序点p。
    • 直观地讲,如果某个变量x的一个定值d到达点p,在点p处使用的x的值可能就是由d最后赋予的。

    例:可以到达各基本块的入口处的定值


    假设每个控制流图都有两个空基本块,分别是表示流图的开始点的ENTRY结点和结束点的EXIT结点(所有离开该图的控制流都流向它)。

    如上,是哪些定值可以到达BiB_i的入口处。

    到达定值分析的主要用途

    • 循环不变计算的检测:如果循环中含有赋值x=y+z ,而y和z所有可能的定值都在循环外面(包括y或z是常数的特殊情况) ,那么y+z就是循环不变计算
    • 常量合并:如果对变量x的某次使用只有一个定值可以到达,并且该定值把一个常量赋给x,那么可以简单地把x替换为该常量
    • 判定变量x在p点上是否未经定值被引用

    “生成”与“杀死”定值

    对于定值 ddu=v+wu=v+w。这里,“+”代表一个一般性的二元运算符

    该语句“生成”了一个对变量u的定值d,并“杀死”了程序中其它对u的定值。

    到达定值的传递函数

    fdf_d:定值ddu=v+wu=v+w的传递函数,fd(x)=gend(xkilld)f_{d}(x)=\operatorname{gen}_{d} \cup\left(x-k i l l_{d}\right)

    fBf_B:基本块BB的传递函数。fB(x)=genB(xkillB)f_{B}(x)=\operatorname{gen}_{B} \cup\left(x-k i l l_{B}\right),其中,killB=kill1kill2...killnkill_B = kill_1 \cup kill_2 \cup ... \cup kill_n,被基本块B中各个语句杀死的定值的集合;而genB=genn(genn1killn)(genn2killn1killn)...(gen1kill2kill3killn)gen_B = gen_n \cup (gen_{n-1} - kill_n) \cup (gen_{n-2} - kill_{n-1} - kill_n) \cup ... \cup (gen_1 - kill_2 - kill_3 - kill_n),表示基本块中没有被块中各语句“杀死”的定值的集合。

    例:各基本块B的gen_B 和kill_B


    如上,计算了各流图中各个基本块的 gen 与 kill 集合。

    到达定值的数据流方程


    gen_Bkill_B的值可以直接从流图计算出来,因此在方程中作为已知量

    到达定值方程的计算

    求解上面提出的 “到达定值的数据流方程” 。

    计算到达定值的迭代算法

    • 输入:流图 GG ,其中每个基本块 BBgenBgen_BkillBkill_B 都已计算出来;
    • 输出:IN[B]IN[B]OUT[B]OUT[B]


    如上,上角标 i 表示第 i 次迭代。

    如上,可以根据结束时,各个 B 的 IN 值,来直接构建到达 IN 值表。

    引用-定值链(Use-Definition Chains)

    可以用上面的 到达 IN 值表 构建 ud 链。

    引用-定值链(简称ud链) 是一个列表,对于变量的每一次引用,到达该引用的所有定值都在该列表中。

    • 如果块B中变量a的引用之前a的定值,那么只有a的最后一次定值会在该引用的ud链中;
    • 如果块B中变量a的引用之前没有a的定值,那么a的这次引用的ud链就是IN[B]中a的定值的集合。
    展开全文
  • 顾名思义,数据流分析就是分析数据如何在程序执行路径上流动的技术,那么数据流分析的前提条件就是基于 IR (源代码经过编译得到的中间表示形式)构造 CFG 控制流图。 基于数据流分析,可以实现多种全局...

     

    什么是数据流分析

    编译器的一个重要功能是分析和优化代码。编译时分析(或称静态分析)得到若干信息后,编译器可以确定在何处应用何种变换是安全并且有利可图的。而其中一种重要的分析技术就是数据流分析。顾名思义,数据流分析就是分析数据如何在程序执行路径上流动的技术,那么数据流分析的前提条件就是基于 IR (源代码经过编译得到的中间表示形式)构造 CFG 控制流图。

    基于数据流分析,可以实现多种全局优化:

    1. 复制传播:形如 u=v 的赋值之后,变量 u 用 v 代替
    2. 常量折叠:若每次运行时表达式的值是常量,则用此常量代替
    3. 全局公共子表达式:例如表达式 a+b 多处出现而且值都相同,那么可以只计算一次
    4. 死代码消除:删除其计算结果不被使用的语句

    等等。

    数据流问题研究的是程序的某个点处的数据流值。

    数据流分析的通用方法是在控制流图上定义一组方程并迭代求解,一般分为正向传播和逆向传播。正向传播就是沿着控制流路径,状态向前传递,前驱块的值传到后继块;逆向传播就是逆着控制流路径,后继块的值反向传给前驱块。这里有两个术语:传递函数与控制流约束。传递函数是指基本块的入口与出口的数据流值为两个集合,满足函数关系 f, 正向传播时入口值集 X,则出口值集为 f(X),逆向传播时出口值集 X,则入口值集为 f(X). 控制流约束是在一条路径两端的前驱与后继块的数据流值的传递关系。

    数据流分析举例

    下面举两个实际例子。

    到达定值问题

    考虑这样的一个问题,变量 x 在哪些地方被定值,在某个位置使用的 x 是这个值吗?

    某个地方变量 x 被赋值了,如果存在路径到达一个点,这个位置 x 被使用了,那么我们说定值 x 到达了此程序点。如果这条路径上 x 被重新定值,我们说 x 被杀死 (kill) 了。可以知道如果某个变量 x 的一个定值 d 到达点 p,那么 p 处使用的 x 的值就可能是 d 定义的。在流图的入口为 x 引入一个未定义值 ⊥,如果 ⊥ 能达到某个 x 的使用,那么说明这个地方的使用可能是未定义值,这就是一个程序错误隐患。

    假设有一个程序的控制流图如下所示:

    图1 待分析的控制流图
    到达定值问题的传递函数被定义为:Out[s] = In[s] + gen - kill。gen 集合是块内的赋值语句产生的新定值,kill 集合是块内赋值语句 kill 的其他定值。对每个变量,有赋值语句则加入到 gen,其他位置的赋值语句都加入 kill。所有块的 gen/kill 集可以一趟扫描完成。路径上的约束为:In[B] = ∪ Out[P],其中P是B的所有前驱块。另外还有边界条件:Out[Entry] = Φ。

    建立完方程组之后,循环迭代,每轮迭代中,每个块的 In/Out 集合都在更新。直到所有的 In[s] 与 Out[s] 都不发生变化,此时就是最终的结果。这个结果是保守的,但不是精确的。因为路径是一个不可判定问题,我们只能尽可能保守的包含全部可能路径。因此,某些实际运行中不会走到的路径,也被我们允许穿越定值。伪代码如下:

    ```

    Init:

        Out[Entry] = Φ

        for each block: Out[B] = Φ

    loops:

        In[B] = ∪ Out[P]   

        Out[B] = In[B] + gen - kill
    ```

    用表格表示计算结果如下:

          loop 1   loop 2   loop 3  
      gen kill In Out In Out In Out
    Entry Φ Φ Φ Φ Φ Φ Φ Φ
    B1 1,2,3 4,5,6,7 Φ 1,2,3 Φ 1,2,3 Φ 1,2,3
    B2 4,5 1,2,7 Φ 4,5 1,2,3,7 3,4,5 1,2,3,5,6,7 3,4,5,6
    B3 6 3 Φ 6 3,4,5 4,5,6 3,4,5,6 4,5,6
    B4 7 1,4 Φ 7 3,4,5,6 3,5,6,7 3,4,5,6 3,5,6,7
    Exit Φ Φ Φ Φ 3,5,6,7 3,5,6,7 3,5,6,7 3,5,6,7

    表1 方程组迭代过程中每个块的 In/Out 集合的计算结果

    算法在第三轮停止。 以 exit 块为例,最终可到达的定值是d3, d5, d6, d7。也就是说图1中 d3, d5, d6, d7 这几行赋值语句的定值,能传递到结束位置。

    活动变量分析

    在这个例子中,我们希望知道变量 x 在某个位置 p 处的值,是否在流图上某条从 p 出发的路径上所使用。如果答案是真,那么我们说 x 在 p 上活跃 (live),如果答案是假,我们说 x 在 p 上是死 (dead) 的。

    这里我们用In[B] Out[B] 分别表示基本块的入口与出口处的活跃变量。这里定义 def 集合为变量在块中被定值之前未被使用,use 集合为变量在块中被使用前未被定值。很容易想到,在块中先被使用的变量在入口是活跃的,在块中先被定义的变量被杀死了,而块中不相关的变量则在块入口的状态与块出口的状态一致。则有传递函数为 In[B] = use + (Out[B] - def)。控制流约束为 Out[B] = ∪ In[S],(其中 S 为 B 的全部后继),等同于变量离开块时活跃当且仅当在某个后继块的入口处活跃。边界条件为 In[Exit] =  Φ。

    同样方程组迭代求解。伪码如下:

    ```

    Init:

        In[Exit] = Φ

        for each block: In[B] = Φ

    loops:

        Out[B] = ∪ In[S]   

        In[B] = Out[B] + use - def
    ```

    可以看到这组方程的一个特点是逆向传播。从 Exit 开始,每个块出口传播到入口,后继块传播到前驱块。与上面的问题刚好相反。但是迭代求解的方法是相同的。

    数据流问题的通用框架

    数据流分析研究的具体问题不同,但方法非常相似,就是在控制流图上定义一组方程组然后迭代求解。方程组有以下特点:

    1. 数据流值在每个结点 s 的前后分别记为 In[s] 与 Out[s]
    2. In[s] 与 Out[s] 之间有约束关系即传递函数,含义是单个块对数据流值的改变
    3. 控制流路径前后结点 s, s' 的 In[s'] 与 Out[s] 有约束关系,含义是数据在路径上的流动
    4. 所有结点的 In[s] 与 Out[s] 及其相互约束关系构成方程组
    5. 迭代遍历控制流图,在每个结点处对方程反复求值,直到方程组的解到达定值即不动点

    方程定义在数据流值上。数据流值传播的路径一般分正向和逆向。控制路径上的约束,通常是交集或并集,例如 In[s] = ∪ Out[s'] (例如定值问题和活跃变量问题) 或 In[s] = ∩ Out[s'] (例如可用表达式问题) 。块内的传递函数,通常写为 Out[s] = In[s] + GenSet - KillSet 的形式。

    数据流问题都可以用这样的框架来解决,它们之间的区别无非是定义域不同,传递函数不同,控制流约束不同,或者数据流方向不同。

    数据流分析算法分析

    一个算法必须回答几个问题:算法收敛性,算法是可停机的吗?算法正确性,结果是正确的吗?算法的复杂度可接受吗?

    数据流分析的算法框架可以抽象为一个代数问题。数据流值全部可能的取值的幂集为V,在 V 上定义一个半格 (semilattice),有meet 运算 ∧。两个元素的 ∧ 运算得到它们的最大下界。半格的 meet 运算 ∧ 有以下特点:等幂:x ∧ x = x; 可交换 x ∧ y = y ∧ x; 有结合律x (y ∧ z) = (x ∧ y) ∧ z. ∧ 运算定义了半格上的偏序关系 ≤。半格的顶元素 T 满足:任意 x ∈ V, x ∧ T = x,底元素 ⊥ 满足:任意 x ∈ V, x  ∧ ⊥ = ⊥。底即最小元素,顶即最大元素。

    图2 定值的子集的半格

    ∧ 运算实际就是控制流约束。在控制流算法框架里面,就是并集或者交集运算,偏序关系实际就是包含或被包含关系。以定值问题举例,如图2所示,所有可能的定值构成半格,顶为空集,底为满集。箭头的指向表明了偏序关系 ≤。控制流上的 meet 运算 ∧ 是并集运算∪, 偏序关系 ≤ 是 包含关系 ⊇。

    框架中的传递函数族F: V → V,包含了块内的传递函数f,以及传递函数的组合。传递函数的组合封闭于函数族F。f ∈ F 是单调函数。x ≤ y 等价于 f(x) ≤ f(y). 

    基于以上模型,以正向传播为例,控制流算法框架的模型可以写作如下形式:

    ```

    Init: 

        for each block:  Out[B] = T

    Loop:

        In[B] = ∧ Out[P]   

        Out[B] = fb(In[B])

    ```

    我们来看迭代过程。每次迭代,对每个程序点 p 上的值,In[B] = ∧ Out[P] 导致值在格上位置下降,fb(In[B]) 是单调函数也会导致值在格上下降。格的高度是有限的,基本块的数量也是有限的,所以迭代算法必然能够收敛。迭代得到的结果就是在格上组合传递函数的最大不动点。

    从 Entry 到基本块 B 上的路径 p,所有经过的块的传递函数组合为 fp = f1▫f2▫f3...= f1(f2(f3...))),  最理想的解 IDEAL[B]  = ∧ fp(Entry),其中 p 为所有可能路径。IDEAL[B] 满足数据流方程组,而且根据单调函数 f ∈ F 的等价关系 f(x ∧ y) ≤ f(x) ∧ f(y) 知道,IDEAL[B] 是最大的正确答案,即精确解。迭代解是正确的,但是可能小于理想解,即不够精确。

    因为迭代算法是格下降的,格的最大高度为值集中元素数量 - 1,以块为单位时,最大高度是块的数量 - 1。同时每次迭代需要遍历全部基本块,所以最恶劣情况下,时间复杂度为 O(n ^ 2),n 为基本块数量。

    以上是对数据流迭代分析算法的简单总结。例子与图引用自《编译原理》。

    展开全文
  • 数据流分析的应用 引用定义链的到达-定义分析(前向数据流问题)、活跃变量分析(逆向数据流问题)、可用表达式分析。 在每一种数据流分析应用中,都会把每个程序点和一个数据流值关联起来。基本上这个程序点是...

    坐标:编译原理,代码优化


    1. 数据流分析的应用

    引用定义链的到达-定义分析(前向数据流问题)、活跃变量分析(逆向数据流问题)、可用表达式分析

    在每一种数据流分析应用中,都会把每个程序点一个数据流值关联起来。基本上这个程序点是基本块层级。

    2. 基本块的数据流分析方程

    B:基本块,IN[B]: 紧靠基本块之前的数据流值,

    OUT[B]: 紧随基本块之后的数据流值,

    fB: 基本块B的传递函数。注意数据流的方向。

    正向: OUT[B] = f_B (IN[B])

    教课书中则是这样的数据流方程,S是一条语句

     

    其中,gen[S]是在S中产生的信息,kill[S]是被S注销的信息。

    out[S] = gen[S] \cup (in[S]-kill[S])

     

    <!-- 按照自己浅显的理解组织的,如不严谨,欢迎指正,勿喷 -->

    先不管怎么分析,以上数据流分析应用中的数据流分析问题定义如下:

    1) 到达-定义分析问题

    与程序点(基本块)关联的数据流值是:变量定义(赋值语句)。

    相关概念:引用-定值链(ud链),它是一个列表,对于变量的每一次引用,到达该引用的所有定值都在该列表中。

    in[B]: 紧靠基本块B之前的有效定义的变量(暂不管具体的变量值)。

    out[B]: 紧随基本块B之后的有效变量定义。

    gen[B]: 在基本块B中,生成的新的变量定义。

    kill[B]: 在基本块B中,被新的变量定义注销的变量定义。

    数据流方程:

    out[B]=gen[B]\cup(in[B]-kill[B])

    in[B]= \bigcup\limits_{P-is-the-precursor-of-B}out[P]

    2) 活跃变量分析问题

    与程序点(基本块)关联的数据流值是:对变量的引用(也因此称为活跃变量)。

    相关概念:定义-引用链(du链)。du链是个集合,对于每个定义,它能到达(途中不被注销)的所有引用的集合。

    in[B]: 紧靠基本块B之前的有效的变量引用

    out[B]: 紧随基本块B之后的效的变量引用

    use[B]: 在基本块B中,使用到的变量引用

    def[B]: 在基本块B中,定义的变量

    数据流方程:

    in[B] = use[B] \cup (out[B]-def[B])

    out[B] = \bigcup\limits_{P-is-the-successor-of-B} in[P]

     

    3)可用表示式分析问题

    与程序点(基本块)关联的数据流值是:可用的表达式。

    同样使用到达定义进行分析。

    U: 全集,程序中出现在一个或多个语句右边的所有表达式的全集。

    in[B]: 紧靠基本块B之前的可用表达式集合。

    out[B]: 紧随基本块B之后的可用表达式集合。

    e_gen[B]: 在基本块B中,生成的可用表达式的集合。

    e_kill[B]: 在基本块B中,注销的可用表达式集合。

    数据流方程:交集。

    out[B] = e\_gen[B] \cup (in[B] - e\_kill[B])

    in[B] = \bigcap\limits_{P-is-the-precursor-of-B} out[P]

    in[ENTRY] = \emptyset

    整理成表格对比:

    问题

    层级

    数据流方向

    IN[B]

    OUT[B]

    聚合操作

    用途

    到达-定义分析

    基本块

    正向

    如上所述

    如上所述

    并集

    如下所述

    活跃变量分析

    基本块

    逆向

    同上

    同上

    并集

    如下所述

    可用表示式

    基本块

    正向

    如上所述

    如上所述

    交集

    如下所述

    4. ud链和du链的用途

    <!-- 明确了用途,又有干劲了 -->

     

    展开全文
  • 为此,分析了GCC编译器在编译时的中间表示,首次提出了基于GCC关键变量数据流分析算法的程序切片技术,以程序的GIMPLE中间表示为基础,以程序基本块为单位,通过迭代求解数据流方程,分析程序基本块内和不同基本块间...
  • 数据流

    2018-12-20 00:52:00
    数据流 引子 编译器后端会对前端生成的中间代码做很多优化,也就是在保证程序...所以掌握数据流分析编译后端极为重要。 何为数据流分析 数据流分析指的是一组用来获取有关数据如何沿着程序执行路径流动的相关...
  • 最近复习《高级编译技术》课程,里面涉及到偏序、完全偏序、格、半格、完全格、不动点等众多形式化分析的概念。现做一个简要总结。1、偏序首先是
  • 举例来说,a+b+b+b+b就是可用表达式,如果不加以优化,其将被计算三次,太浪费了,所以编译优化过程要求发现这个可用表达式。 活跃变量: 举例来说,a,b就是活跃变量,c是不活跃变量,前者叫做live,后者叫做dead。 ...
  • <br />主要模块及数据流 经过多年的发展,mysql的主要模块已经稳定,基本不会有大的修改。本文将对MySQL的整体架构及重要目录进行讲述。源码结构(MySQL-5.5.0-m2)BUILD: 内含在各个平台、各种编译器下...
  • 给出了基于数据流分析框架的双向类型传播模型,通过构建类型格并在格的基础上求解类 型传播方程,从而达到类型细化的目的;通过分析复杂数据结构的存储特点及寻址方式, 以等价类划分的思想求取复杂数据结构的内存...
  • 编译原理——词法分析器的任务

    千次阅读 2019-12-30 19:35:36
    词法分析器的任务 任务主要是负责字符到记号的转换 ...记号: 经过词法分析分析后生成的一串记号(也可以称为单词)的集合,这个记号是在编译器内事先定义好的数据结构,负责编码字符。 举例...
  • Soot是一个Java编译优化框架,可以利用它实现Java字节码程序的数据流分析和控制流分析。在深入分析Soot控制流生成机制的基础上,详细叙述了利用Soot分析Java类的控制流并生成其控制流图的方法和过程,同时提出了将Soot...
  • 1.源码结构(MySQL-5.5.0-m2)BUILD: 内含在各个平台、各种编译器下进行编译的脚本。如compile-pentium-debug表示在pentium架构上进行编译的脚本。Client: 客户端工具,如mysql, mysqladmin之类。Cmd-line-utils: ...
  • 模拟文件系统,操作系统课程设计的心血,含详细设计报告(设计要求、设计思想、数据结构设计、实体关系图、数据流图、程序流程图、结果分析等)。界面友好,模拟MS-DOS命令行方式,并提供命令列表和命令帮助。编程...
  • 编译原理——CMM语义分析

    千次阅读 2018-06-10 23:59:09
    一、语义分析要解决的问题•确定类型:确定标识符所关联的数据对象的数据类型。•类型检查:按照语言的类型规则,对运算及运算分量进行类型检查,必要时做出相应类型转换。•识别含义:根据程序设计语言的语义定义,...
  • 第1章 绪论 第2章 指令系统 第3章 可执行文件 第4章 反汇编技术 第5章 指令的语义抽象 第6章 基本数据类型分析 第7章 高级控制恢复 第8章 过程恢复技术 第9章 部分编译优化效果的消除 第10章 程序的调试与测试
  • 作者 | Renan Ferreira编译 | VK来源 | Towards Datas Science典型的数据科学工作由以下步骤组成:❝确定业务需求->数据获取->数据准备->数据分析->共享数据见解❞每一个步骤都需要一套专业知识,这些...
  • 编译原理词法分析

    热门讨论 2008-05-07 21:50:08
    分析出来的单词 char str[1024] 输入缓冲区 int sta 输入缓冲区下标 int symbol 单词种别 int attr 属性 2. 子函数 scan(char s[]) 输入:字符 输出:Symbol(单词种别...
  • 编译 | Rik R  来源 | Bloomberg 在缅甸,大多数的死亡事件发生在家中,只有四分之一得到了医生开具的证明。而我们并不知道的是,死亡计数也关乎生者存亡。 现在,东南亚国家正在采用新方式来计算死亡...
  • 编译程序完成词法分析功能,扫描输入字符,产生用于语法分析的词法记号序列。下述文法描述了该词法分析程序: <标识符>--><字母>|<标识符><字母>|<标识符><数字> <无符号整数>--><数字>|<无符号整数><数字> ...
  • KUBO:适用于OS内核的精确且可扩展的静态UB检测器 要求: Ubuntu 16.04、18.04、20.04 Python3 第三方软件包:networkx,matploitlib,argparse,termcolor,ipython ... 编译linux二进制文件:python main.py build
  • 编译 | 周小璐编辑 | VincentAI 前线导读:通过本文,你可以对数据科学及其几大分支,包括商业分析数据分析、商业智能、先进分析、机器学习和 AI 有初步的认识。更多干货内容请关注微信公众号“AI 前线”,(ID:...
  • 使用两个提供交通事件(或事件)数据的API收集了2016年2月至2020年6月的事故数据。 这些API广播了各种实体(例如美国和州交通运输部门,执法机构,交通摄像头和道路网络中的交通传感器)捕获的交通数据。 当前,...
  • 编译原理语义分析和中间代码生成

    千次阅读 2018-06-15 13:05:33
    语义分析的任务:审查每一个语法结构的静态语义,即验证语法正确的结构是否有意义在语义正确的基础上生成一种中间代码或目标代码语义分析的范围:确定类型:确定标识符所关联的数据类型类型检查:按语言的类型规则,...
  • 通过词法分析, 可以将一个字符串转换成记号, 但是记号如何转换成语法树, 需要进行语法分析. 实质: 无结构的数据转化成有结构的数据 依据: 上下文无关语法 上下文无关文法 前言 正规式来定义一些简单的语言...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 879
精华内容 351
关键字:

数据流分析编译