【输入输出】
一个过程的所有基本块，除entry和exit外的每个基本块包含指令序列
【流程】
由前向数据流分析、局部复写传播和遍历基本块构成
1. 前向数据流分析：目标是计算出每个基本块入口处有效的复写赋值集合，这里定义为CPin(i)，i为基本块，其元素为表示复写赋值的四元组<u,v,blk,pos>，u为左变量，v为右变量，blk为基本块，pos为在blk中的位置。另外定义COPY(i)为基本块i中出现且到达了出口的那些复写赋值集合，即u和v在i中pos后没被赋值；KILL(i)为被基本块i杀死的那些赋值集合，即i中存在对其它基本块复写赋值右变量的赋值；CPout(i)为基本块i出口处有效的复写赋值集合。以上四种集合的数据流方程为：CPin(i)等于i的每个前驱p的CPout的交集，CPout(i)等于COPY(i)与CPin(i)减去KILL(i)之差的并集。CPout(entry)初值为空集，其它基本块的CPout初值为全集U，U为过程所有复写赋值的集合即所有基本块的COPY之并集，根据迭代求不动点法可算出每个基本块最终的CPin值
2. 局部复写传播：作为被全局复写传播调用的例程，有两个参数，一个为输入输出参数单个基本块，另一个为输入参数CPin，即前向数据流分析求得的结果。该例程内部维护一个有效复写赋值的表，称作ACP，其元素为二元组<u,v>，u是复写赋值的左变量，v是右变量。首先初始化ACP即将CPin中的复写赋值加入到ACP，再遍历基本块的每条指令，针对指令类别做对应的处理，有以下几种情况
a）对于一元/二元表达式及过程调用，将表达式的操作数或调用参数替换为ACP中对应元组的第二分量，若不存在这样的元组则不用替换
b）对于赋值语句（包括复写赋值），从ACP中删除第一或第二分量为赋值语句左变量的元组，这是为了删除被杀死的复写赋值
c）对于复写赋值且左变量u不等于右变量v，将元组<u,v>加入到ACP
当遍历结束后，局部复写传播就完成了
3. 遍历基本块：对每个基本块调用局部复写传播，当遍历结束后，全局复写传播就完成了
【分析】
数据流分析的复杂度取决于基本块总数及指令总数，局部复写传播的复杂度取决于基本块的指令总数，遍历基本块复杂度取决于基本块数量。全局复写传播会造成无用的赋值指令，但是这正给死代码删除和强度削减（比如两个相同的整型变量加法用移位代替）提供了机会
posted @
2023-09-06 23:13 春秋十二月 阅读(97) |
评论 (0) |
编辑 收藏【输入】
ssa控制流图。结点为一个phi函数或一条运算指令，边包含控制流边和ssa边
【输出】
所有ssa变量的最终LatCell（常量半格值）
【流程】
1. 算法维护两个工作表，一是流图边FlowWL，用于跟踪控制流的执行，二是ssa边SSAWL，用于单赋值变量的传播。还有一个ExecFlag映射，用于确保仅有控制流边导向的运算结点最多执行一次，多次执行是没必要的，因为运算涉及的分量不会变（没有ssa前驱边），ExecFlag(a,b)为true表示边a->b导向的结点b已执行，否则未执行
2. 两种结点的分析：
a) 对于phi结点，不管被哪种边导向，都先计算其LatCell（phi结果与各个phi参数的交），若与旧值不同，则将它的ssa后继边加入SSAWL，若控制流后继边尚未执行即对应ExecFlag为false，则将它的控制流后继边加入FlowWL
b) 对于运算结点，若是控制流边导向且未被执行过（到结点的所有边的ExecFlag为false）或ssa边导向且以前执行过（存在至少一条边的ExecFlag为true），则执行其运算，计算左值变量的LatCell（解释执行整数运算），若与旧值不同，则将ssa后继边加入SSAWL，若LatCell是常量且为条件运算，则将满足条件的Y或N边加入FlowWL，否则将所有控制流后继边加入FlowWL
3. 算法初始时，设置所有控制流边的ExecFlag为false，设置所有ssa变量的LatCell为未知（半格顶元素），将流图入口到第1个结点的边加入FlowWL。然后进行主循环，先从FlowWL移出一条边，若边的ExecFlag为false则设为true，判断尾结点类型，若为phi则转到上述2-a处理，若为运算则转到2-b处理；再从SSAWL移出一条边，若边尾结点为phi类型则转到2-a处理，否则为运算类型转到2-b处理，以上过程直至FlowWL和SSAWL皆为空
【分析】
该算法思想是符号执行，对于运算x=y或x=y+z（这里+泛指对整型有意义的操作），在常量半格中，x、y、z初值为未知，y和z单调降低，导致x也单调降低，它们最多降低2次，故当格值不变后，SSAWL终为空，另外由于ExecFlag的作用导致所有仅控制流边导向的结点最多执行一次，因此FlowWL终为空，算法是收敛的，复杂度取决于控制流边和ssa边的总数
posted @
2023-09-06 23:10 春秋十二月 阅读(45) |
评论 (0) |
编辑 收藏【输入】
程序控制流图CFG
【输出】
带区域结点的控制依赖图CDG
【流程】
1. 为CFG添加一个虚构谓词结点start，它的Y边指向入口结点entry，出边指向出口结点exit，得到CFG+。添加start是因为entry到第1个基本块没有条件判断
2. 为CFG+构建后必经结点树PDOMTree，将CFG+中所有n不是m的后必经结点的边m->n加入集合S，边的标号来自CFG为Y或N
3. 遍历S，对每条边m->n，先在PDOMTree中找到最低公共祖先p（如果m为根结点则为m，否则为m的父结点），再将PDOMTree中p到n路径上每个结点（p和entry除外）x加入CDG，并添加边m->x，其边标号同m->n
4. 对CDG的每个内部结点，若存在Y边，则新建一个区域结点，连接所有Y边对应的子结点；若存在N结点，则新建一个区域结点，连接所有N边对应的子结点
【应用】
对于控制依赖于同一结点的所有结点，只要它们之间没有数据依赖关系，就可以并行执行
posted @
2023-09-06 23:07 春秋十二月 阅读(73) |
评论 (0) |
编辑 收藏【输入】
根过程，及每个过程（含根过程）的指令序列
【输出】
调用图，由过程点集和调用边（形如<p,i,q>，p在位置i调用q）集构成
【全局结构】
PVVs：过程值变量集合
PVVals：过程值变量到过程常数集合的映射
PVBinds：过程值变量到过程值变量集合的映射
PVCalls：调用边的集合
【流程核心】
1. 分析过程p内指令，要处理调用指令和赋值指令两种类型。对于调用指令，若被调过程q是过程常数，则将q和<p,i,q>加入调用图，先解析q的过程值形参与传入实参的关系，有4种情况
a）过程常数cp传入过程值形参fp，将偶对<fp,cp>加入PVVals，fp加入PVVs
b）过程值变量vp传入过程值形参fp，将<fp,vp>加入PVBinds，fp和vp加入PVVs
c）过程值形参fp传出过程值变量vp，将<vp,fp>加入PVBinds，vp和fp加入PVVs
d）过程值形参fp传出过程常数cp，将<fp,cp>加入PVVals，fp加入PVVs
若q不是常数而是过程值变量，则将q加入PVVs，<p,i,q>加入PVCalls。再解析q的返回与p的关系，有2种情况
e）返回一个过程值变量vp1赋给另一过程值变量vp2，将<vp2,vp1>加入PVBinds，vp2和vp1加入PVVs
f）返回一个过程常数cp赋给一个过程值变量vp，将<vp,cp>加入PVVals，vp加入PVVs
对于赋值指令，其实情况和上述返回赋值一样
----------------------------------------------------------------
2. 遍历PVVs，传播各过程值变量的PVBinds，直至不再改变（迭代求不动解），本质是计算过程值变量的传递闭包
3. 遍历PVCalls，对每个<p,i,q>，先遍历它的每个PVVals u，将u和<p,i,u>加入调用图；再遍历它的每个PVBinds u及u的每个PVVals v，将v和<p,i,v>加入调用图
----------------------------------------------------------------
以上三环节可使用工作表w来驱动，w初始只有根过程，不断从w移出一个过程p、分析p，每当在环节1或环节3发现一个新过程（过程常数）就加入w，直至w为空，这时所有过程都已分析，调用图构建完成
posted @
2023-09-06 23:04 春秋十二月 阅读(52) |
评论 (0) |
编辑 收藏【输入】
调用图，其顶端是根过程
【输出】
每个过程每个参数的icp值
【算法步骤】
1. 将根过程加入工作表，遍历调用图，构建每个过程的形参集合，初始化每个形参的icp值为未知（icp格的顶元素）
2. 从工作表移出一个过程p，若工作表为空则终止
3. 遍历p的指令序列，对每个调用点遍历被调过程q的形参，对每个形参x，若对应的传入实参是p的一个形参，则计算x的icp值（等于x旧值和传入实参的icp值之交）
4. 若x的icp值比旧值小，则将q加入工作表，转到步骤2继续
【算法分析】
数学基础是icp半格，高度为3，所以必定收敛（因为半格是单调偏序的，icp最多变小2次：未知->常量，常量->非常量）。步骤1复杂度取决于过程数及其参数数量，步骤2～4之外循环次数取决于调用图的深度，内循环取决于调用点数、被调过程的参数数量。该算法是位置无关的，不能处理特定调用点的特定过程之常量传播，另外过程的形参集合不能有交集
【应用】
可以计算出每个过程入口形参对应的常量实参集合，进而可以运用全局常数传播使结果更精确。如果确定了一个过程的哪些参数是常量，那么可以克隆出一个副本，对副本进行优化，比如裁剪调用和起始代码序列，使之不传递常数参数，再运用过程内优化
posted @
2023-09-06 23:02 春秋十二月 阅读(42) |
评论 (0) |
编辑 收藏【输入】控制流图<N, E> G，回边m—>n
【输出】循环子图<N, E> loop
【流程】
1. 将m、n加入loop的结点集合，及m—>n加入loop的边集合，若m不等于n即不为自环，则加入m到queue（先进先出队列）
2. 若queue非空，则其从头出队得结点q；否则结束
3. 在G中遍历q的每一个前驱结点p，将p加入queue尾，若p不在loop结点集合中，则加入到loop结点集合，及边p—>q加入loop的边集合。转到步骤2继续
【分析】
正确性：检验最终loop中的结点集合是否满足自然循环的定义，注意到输入指定了回边，这说明n是m的支配结点，当为自环时只有一个结点而满足支配自反性，当不为自环时，加入的结点是m的所有直接与间接前驱，所以n也是它们的支配结点（假设不是，则必有m的一个前驱p，从入口结点经过p到m但不经过n，这与n是m的支配结点矛盾），且回边已在第1步加入loop，故满足了自然循环的定义。由于m在loop中的前驱数量是有限的，因此算法必然终止
复杂度：第3步判断p是否在loop结点集合中，取决于图的具体结构，设n为循环子图的结点数，若是邻接矩阵，则只需O(1)时间检测边是否存在，因此总耗时为O(n)。若为邻接表，检测边是否存在与结点数成正比，则总耗时为O(n^2)
其它算法：从m开始，标记n为visited，在G的反向流图中深度优先搜索，将访问到的结点及边加入loop，遇到n就回溯
posted @
2023-09-06 22:59 春秋十二月 阅读(38) |
评论 (0) |
编辑 收藏【命题1】控制流图G中若a dom n，且b dom n，则a dom b 或b dom a
【证明】设G入口为s，假设结论不成立，即a 不dom b且b 不dom a，或a dom b且b dom a。根据支配结点定义，如果是前者，则从s有全部路径经a（或b）到n但不经过b（或a），这与题设b（或a）dom n矛盾；如果是后者，则从s有全部路径经a，然后经b，再经a，构成了无限循环a->b->a->•••，永远到不了n，这也与题设矛盾。故结论成立
【命题2】控制流图G中若m idom n，则m是唯一的，若d ≠ n 且d dom n ，则d dom m
【证明】设G入口为s，假设不唯一，G中有另一个结点m'且m' idom n，根据支配结点定义，从s经m到n的路径上必有m' dom m，从s经m'到n的路径上必有m dom m'，根据支配关系的反对称性，有m'=m，故唯一。假设d 不dom m，则从s到m的路径上不必然经过d，又m是n的唯一直接支配结点，则从s到n的路径上不必然经过d，即d 不dom n，这与题设矛盾，故d dom m。可以看到用反证法证明后一个结论时，直接支配结点的唯一性很关键
posted @
2023-09-06 22:57 春秋十二月 阅读(415) |
评论 (0) |
编辑 收藏1. 迭代算法在什么情况下是正确的
数据流值满足半格的定义，以及数据流方程中的传递函数满足单调性
2. 迭代算法在什么情况下必定收敛
在满足正确性的前提下，当数据流值对应的半格高度有限时，必定收敛。以最小元为初值的迭代收敛于最小不动点，以最大元为初值的迭代收敛于最大不动点
3. IDEAL、MOP、MFP三种解的意义与关系
IDEAL是理想解即最精确的解，它将程序入口entry到某点p所有可达路径（可执行路径）的尾端的数据流值做聚合操作，区分来自不同路径的数据流值，若聚合操作是交运算，则最大下界为其值，任何大于IDEAL的解都是错误的，而小于IDEAL的解是保守的；若聚合操作是并运算，则最小上界为其值，任何小于IDEAL的解都是错误的，而大于IDEAL的解是保守的。MOP是全路径聚合解，它将entry到p所有流图路径（不一定可执行）的尾端的数据流值做聚合操作，区分来自不同路径的数据流值，若包含了不可执行路径，则会丢失精确性，否则等于IDEAL；MFP是基于数据流方程与迭代算法求得的最大或最小不动点解，它在每个控制流图的汇合节点做聚合操作而非路径尾端，不区分来自不同路径的数据流值，若传递函数不满足分配律，则会丢失精确性，否则等于MOP。故精确性关系为MFP<=MOP<=IDEAL，可知MFP解是安全的，基于MFP作的优化是正确的
4. 为什么不采用IDEAL和MOP解
因为一般程序路径数可能无限，所以没有求MOP的有效算法，且不可达路径是一个不可判定问题，所以没有求IDEAL的有效算法
posted @
2023-09-06 22:53 春秋十二月 阅读(42) |
评论 (0) |
编辑 收藏为什么要加宽算子？
因为当格的偏序集合L不满足升链条件，从最小元迭代计算最小不动点的过程是不收敛的，即迭代序列(fⁿ(⊥))ₙ不保证最终稳定，且其最小上界不保证等于最小不动点，因此需要一种近似lfp(f)的方法。引入加宽算子fw:L×L—>L, fw(x)=x▽f(x)，可以将L上的一个序列转为收敛的升链，从L的最小元开始迭代不断上升，直至lfp(f)的一个上近似即fw的最小不动点lfp(fw)，关系式为lfp(f)<=f(lfp(fw))<=fw(lfp(fw))=lfp(fw)。对上式反复应用f单调得到：lfp(f)<=fⁿ⁺¹(lfp(fw))<=fⁿ(lfp(fw))<=…<=f(lfp(fw))<=lfp(fw)，这表明对lfp(fw)使用f迭代可获得更精确的上近似，其过程可看成沿一个递降链进一步逼近lfp(f)，但L不一定满足降链条件而导致上述过程不收敛，故需要引入变窄算子fn:L×L—>L, fn(x)=x△f(x)，将L的一个序列转为收敛的降链，从lfp(fw)开始迭代，不断下降直至fn的一个不动点fp(fn)，则有关系式：lfp(f)<=fp(fn)<=lfp(fw)。注意，这里根据加宽算子的定义可知fw是单调的，但根据变窄算子的定义不确定fn是否单调，故从lfp(fw)迭代求得的fp(fn)，不确定是最小还是最大不动点，只能说是一个不动点，这也反映了变窄算子不需要满足单调性，就可以更加逼近lfp(f)
posted @
2023-09-06 22:45 春秋十二月 阅读(62) |
评论 (0) |
编辑 收藏【性质】
1. 判定两个完全格L和M能否构成伽罗瓦连接，即抽象化函数α: L—>M是否完全加性的，或具体化函数γ: M—>L是否完全乘性的
2. 构造抽象化函数和具体化函数，即对于一个Galois连接（L, α, γ, M），给定α可通过γ(m) = ⊔{l | α(l) ⊑ m}确定γ，这对于所有m成立，且由于α是确定的，因此γ是唯一确定的。取最小上界是为了保证m描述的L中元素对于所有安全地描述了M中α(l)的l是安全的；给定γ可通过 α(l) = ⊓ {m | l ⊑ γ(m) } 确定α，其唯一性和取最大下界的原因类似前面
3. 帮助定义分析具体格源值到抽象格属性的正确性关系与表示函数。设有Galois连接（L, α, γ, M），R: V×L —>{true, false}为正确性关系，由表示函数β:V—>L生成，定义S: V×M —>{true, false}，则有v S m ⇔ v R (γ(m)) ⇔ β(v ) ⊑ γ(m) ⇔ (α◦β)(v) ⊑ m，即S为正确性关系，由表示函数α◦β: V—>M生成
4. 抽象化上迭代多次具体化+抽象化，结果等于一次抽象化，即α◦γ◦α = α；具体化上迭代多次抽象化+具体化，结果等于一次具体化，即γ◦α◦ γ = γ。这个性质被用于基于约化算子构造的伽罗瓦插入（特殊的伽罗瓦连接：具体化为单射，抽象化为满射）的证明
【组合】
分三大类，即顺序组合、并行组合和函数空间。为简化描述，下文简称Galois为G
1. 顺序组合：取第一个G连接的具体格，最后一个G连接的抽象格，从第一个G连接到最后一个G连接组合各抽象化函数，从最后一个G连接到第一个G连接组合各具体化函数。例如，设（L₀, α₁, γ₁, L₁）和（L₁, α₂, γ₂, L₂）都是G连接，则（L₀, α₂◦α₁, γ₂◦γ₁, L₂）也是一个G连接
2. 并行组合：有六种方法，即独立特征、相关性、直积、直张量积、约化积、约化张量积，前两种用于组合分别针对不同结构多个分析的多个G连接为一个G连接。中间两种组合针对同一结构多个分析的多个G连接为一个G连接，后两种组合针对同一结构多个分析的多个G连接为一个G插入。独立特征、直积、约化积与其它方法的区别是两对抽象化函数与具体化函数之间没有相互作用，会损失分析结果精度，本质就是P(A)×P(B)和P(A×B)的差别（P为幂集，A、B为集合）；独立特征与直积、约化积的区别是具体化函数定义不同（抽象化函数相同），前者是两个具体化函数的二元组即γ(m₁, m₂)=(γ₁(m₁), γ₂(m₂))，后者则是最大下界即γ(m)=γ₁(m₁)∧γ₂(m₂)
3. 函数空间：分为总函数空间和单调函数空间。对于前者，设（L, α, γ, M）为一个G连接，S为一个集合，f为S到L的函数，g为S到M的函数，因L和M为完全格，故由f或g构成的函数集合为总函数空间，则得到一个G连接（S—>L, α', γ', S—>M），其中α'(f)=α◦f, γ'(g)=γ◦g。对于后者，设（L₁, α₁, γ₁, M₁）和（L₂, α₂, γ₂, M₂）为G连接，f为L₁到L₂的函数，g为M₁到M₂的函数，因每个L及M为完全格，故由f或g构成的函数集合为单调函数空间，则得到一个G连接（L₁—>L₂, α, γ, M₁—>M₂），其中α(f)=α₂ ◦f ◦γ₁，γ(g)=γ₂◦ g◦ α₁
【应用】
当要做数据流分析的一个完全格L不满足升链条件时，除了直接对L运用加宽算子及变窄算子外，还怎么去计算近似它的最小不动点？这时伽罗瓦连接就派上用场了，先将L对应到另一个完全格M，即构造一个Galois连接或插入（L, α, γ, M），设A是L上的广义单调框架（不要求L满足升链条件，指定传递函数集合F为L到L的单调函数空间，即F本身也是完全格），其中f是L到L的单调函数，B是M上的广义单调框架，其中g是M到M的单调函数，保证g是由f衍生的函数的上近似即α◦f◦γ ⊑ g，及M满足升链条件。到了这里可以证明两个结论：
➀ lfp(f) ⊑ γ(lfp(g)) 和 α(lfp(f)) ⊑ lfp(g)
➁B的约束解(B₁, B₂)蕴含A的约束解(A₁, A₂)=(γ◦B₁, γ◦B₂)，下标1、2表示流图结点的入口、出口。接下来有两种方法可以计算近似L的最小不动点
1. 直接计算M上的最小不动点，然后应用上述结论➀，取lfp(f) = γ(lfp(g))
2. 构造M的上界算子（针对Galois连接）或加宽算子（针对Galois插入），满足 l₁ ∇ₗ l₂ = γ(α(l₁) ∇ₘ α(l₂))，可以证明左式为L上的一个加宽算子，取其lfp∇ₗ (f)。如果前面构造的是Galois插入，那么可以证明L和M两者的加宽算子精度是一样的，即lfp∇ₗ (f) = γ(lfp∇ₘ(α◦f◦γ ))
posted @
2023-09-06 22:42 春秋十二月 阅读(255) |
评论 (0) |
编辑 收藏