随笔-149  评论-223  文章-30  trackbacks-0
 
叶调用优化与收缩包装
1. 叶调用优化适用于被调者是不调用任何过程的过程之场景,这种过程叫叶过程
2. 有几种可能的优化
a)如果过程的实现使用display数组来寻址非局部变量,那么叶过程可避免在起始代码序列中更新display数组
b)如果叶过程内不使用由被调者保存的寄存器(寄存器分配器应设法优先使用由调用者保存的寄存器),那么可避免起始代码序列中保存代码和收尾代码序列中恢复代码。很小的叶过程很可能不使用到被调者保存的寄存器,只使用部分调用者保存的寄存器的叶过程,那么调用者也可以避免一部分寄存器保存与恢复代码
c)如果调用者有很多次调用叶过程,而且两者代码同时可见,那么叶过程不必自己分配栈帧,由调用者一次性分配好
3. 收缩包装是叶调用优化的一种推广,目的是尽可能去掉过程起始代码序列和收尾代码序列中实际没用的寄存器保存恢复代码。可以先用数据流分析来计算每个基本块的保存寄存器集合(基本块入口可预见但其前驱不可预见且入口不可达的那些寄存器)与恢复寄存器集合(基本块出口可达但其后继不可达且出口不可预见的那些寄存器),再在保存寄存器集合非空的基本块入口处插入save指令(插入点已是最早的合适的位置),恢复寄存器集合非空的基本块出口处插入restore指令(插入点已是最晚的合适的位置)

尾调用优化与尾递归删除
1. 尾调用优化的条件是两个(不同)过程编译时同时可见,比如处于同一编译单元,或调用者有足够多的、使得优化可能发生的关于被调用者的信息
2. 尾调用优化的实现,因为被调者返回后代码序列到调用者收尾代码序列之间不存在有用计算,所以原来标准链接处理要保存的那些寄存器不可能活跃,首先要裁剪调用前代码序列即不保存由调用者保存的寄存器和不压栈返回地址,以及裁剪被调过程的起始代码序列即不保存由被调者保存的寄存器和不分配新栈帧(借用调用者的栈帧,若被调者的栈帧比调用者的大,则需按两者之差扩展栈帧),然后转移到被调者裁剪过的起始代码序列,最后修改被调过程的收尾代码序列:正确释放栈帧,比如用帧指针赋给栈指针,使之直接返回到调用者的调用者(比如o调用p,p调用q,q是尾调用,那么优化后q实际返回到o)。综上可得,尾调用优化减免了压栈返回地址与保存寄存器的开销
3. 尾递归删除是尾调用优化的一种特例,由于调用者和被调者是同一过程,因此不存在扩展栈帧和额外释放栈帧,只须改变参数及跳转到过程入口处即可
posted @ 2023-09-06 23:23 春秋十二月 阅读(24) | 评论 (0)编辑 收藏
1. 数学基础:两者的共同点是都基于数据流值的半格和对组合运算封闭的传递函数,不同点是区域分析算法还要求传递函数是一个半格,不仅支持组合运算,而且支持交汇运算和闭包运算,交汇运算用于把有相同后继的不同执行路径组合起来,闭包运算用于环上(比如循环)执行零到多次的效果

2. 流程:迭代算法由初始化和循环求不动解组成,以前向数据流为例,其中初始化包括初始化入口基本块的out集合为合适值,其它基本块的out集合为半格的顶元素;循环求不动解遍历除入口外(因为入口的out不会变)的每个基本块,计算其out集合,直至所有基本块的out不再改变。区域分析算法由计算层次区域序列、构造区域传递函数和计算各区域入口值组成,计算层次区域序列自底向上,基本块为叶子区域,自然循环分为循环体区域和循环区域,都是内部区域,不是自然循环的整个流图为根区域;区域传递函数有2个,一是R区域入口到其直接子区域S的入口的数据流值传递,记作Fin(R,S),另一是R区域入口到其直接子区域出口基本块B(可能有多个)出口处的数据流值传递,记作Fout(R,B),区域传递函数的计算自底向上,对于叶子区域,Fin是恒等函数,Fout和迭代算法的传递函数一样,取决于具体数据流问题;对于更大的区域(非叶子区域),遍历每个子区域,Fin由所有Fout(R,B)交汇而成,B为S在R中的前驱,若R为循环区域,则再求Fout的闭包,遍历S的每个出口基本块B,Fout由Fout(S,B)和Fin(R,S)组合而成。计算各区域入口值自顶向下,根区域的In值等于流图入口的In值,其它区域S的In值等于Fin(R,S),R为父区域,所有Fin在前一环节已构造好

3. 结果:对同一数据流问题比如到达定值,两种算法求得的数据流值是一样的。为什么区域分析算法是正确的?因为它实际是按照程序控制流来构造传递函数的,包含了所有可能执行路径数据流值传递的效果,这相当于迭代算法求不动解的过程,所以最后只要一个流图的入口值,就能算出各区域的入口值。为什么迭代算法是收敛的?因为半格是单调的且高度有穷。收敛速度取决于遍历基本块的顺序,如果按基本块深度优先排序(逆后序)遍历,那么迭代轮数不超过流图的深度(各条无环路径后退边的最大数)加2

4. 区别:迭代算法用于可归约流图和不可归约流图,区域分析算法仅能用于可归约流图
posted @ 2023-09-06 23:18 春秋十二月 阅读(35) | 评论 (0)编辑 收藏
1. 作为指令高速缓层优化的一种重要技术,它根据CFG流图边的执行频率将频繁执行的基本块排列在一起,并布局那些基本块在下降分支路径,而不在一起的也就是很少执行的基本块布局在转移分支路径。这样做一来可以使取到I-cache中的指令实际被执行的比例较高,二来对于某些体系结构上转移和下降路径延迟不等的分支指令,可以降低跳转延迟

2. 实现过程内代码置放有以下几个环节:
a)获取剖析数据:编译器可以先在基本块出口处插入代码以统计到其后继基本块的执行次数,作为CFG流图边的权重,然后编译生成可执行文件,输入代表性数据运行它,结果输出一个数据文件,用于第二次编译,这次编译实施过程内代码置放优化
b)以链的形式构建热路径:热路径是CFG路径的一个集合,其中包括频繁执行的那些边,每条路径是一个或多个基本块按边的方向构成的链,每个链关联一个优先级,用于布局代码的先后顺序。初始时,每个基本块构成一个只有它本身的链,其优先级为CFG流图边的数量或者更大值;接下来,在CFG中按权重降序遍历每条边<x,y>(x不等于y),若x是某个链a的尾结点且y是某链b的头结点,则把b合并到a后面,更新a的优先级为a原来优先级、b优先级、P三者的最小值,同时递增P,其中P为链合并操作的计数器,用于决定链的相对次序由低到高排列,初值为0。当遍历结束时,所有热路径构建完成
c)进行代码布局:经过前一环节,就得到了链的集合。首先从链集合找出含有入口基本块的链t,将t加入工作表WL;然后从WL移出一个优先级最低的链c,按序(构建链时加入基本块的顺序)遍历c的每个基本块x,把x放在过程可执行代码体的末端,对于边<x,y>,将包含y的链t加入WL(若t不在WL中),重复该过程直至WL为空
posted @ 2023-09-06 23:15 春秋十二月 阅读(24) | 评论 (0)编辑 收藏
【输入输出】
一个过程的所有基本块,除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 春秋十二月 阅读(44) | 评论 (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 春秋十二月 阅读(19) | 评论 (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 春秋十二月 阅读(21) | 评论 (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 春秋十二月 阅读(26) | 评论 (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 春秋十二月 阅读(22) | 评论 (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 春秋十二月 阅读(21) | 评论 (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 春秋十二月 阅读(334) | 评论 (0)编辑 收藏
仅列出标题
共15页: 1 2 3 4 5 6 7 8 9 Last