南开大学编译原理第十章课件PPT.ppt

例10.39 D(2)={2}∪D(1)={1,2} D(3)={3}∪{{1}∩{1,2}∩{1,2,…,10})={1,3} D(4)={4}∪{{1,3}∩{1,2,…,10})={1,3,4} D(5)={5}∪{1,3,4}={1,3,4,5} D(6)={6}∪{1,3,4}={1,3,4,6} D(7)={7}∪{{1,3,4}∩{1,3,4,6}∩{1,2,…,10})={1,3,4,7} D(8)={8}∪{1,3,4,7}={1,3,4,7,8} D(9)={9}∪{1,3,4,7,8}={1,3,4,7,8,9} D(10)={10}∪{1,3,4,7,8}={1,3,4,7,8,10} 不再改变 10.10 高效数据流算法 10.10.1 迭代算法中的深度优先顺序 前面的研究都假定信息沿无环路径传播，实际上环路没有影响——删除环，形成更短的无环路径，信息传播没有改变 无环路径：修改数据流迭代算法的节点访问顺序，加快算法速度 区间深度：得到限制流图所需的区间划分次数 Knuth统计得到：典型流图的区间深度很低，评价为2.75 深度：无环路径上后退边的最大数目 区间深度永远不会比深度小 迭代次数 a?b是后退边时，b的深度优先编号才比a的编号小——修改算法10.2，按每个块B深度优先编号顺序计算到达定义 假定存在定义d的传播路径：3?5?19?35?16?23?45?4?10?17 第一次迭代：d?out[3]?in[5]?out[5]… ?out[35]，在16处截断——先计算的in[16]、out[16]，后计算的35 第二次迭代：在4处截断 第三次迭代：完成 迭代次数（续） 一般的，迭代次数不超过后退边数目＋1 所需遍历次数是深度＋1 使用深度优先算法的遍数实际上是深度＋2——遍历次数不超过5 可用表达式或其他通过前向传播计算的数据流问题，按深度优先顺序计算 活跃变量等后向传播计算的问题，按深度优先顺序的逆序计算 10.10.2 基于结构的数据流分析 访问节点的次数不会大于区间深度，平均次数比区间深度小得多 算法基于T1和T2变换得到结构上 对区域R中的每个块B，计算从区域首节点到B的末尾的路径上所产生和注销的定义集合genR, B和killR, B 然后计算转移函数transR, B(S)：S中哪些定义会沿着R中路径到达B的末尾 基于结构的数据流分析（续） 到达块B末尾的定义可分为两类 在R中产生并传播到B末尾——与S无关 不是在R中产生，但在到B末尾的路径中也未注销，若它在S中则它在transR,B(S)中 transR,B(S)=genR,B∪(S - killR,B) 算法核心思想：对流图使用T1、T2变换逐渐变大的区域计算transR,B 基于结构的数据流分析算法 起点是单个块B构成的区域 genB,B=gen[B]，killB,B=kill[B] 使用T2变换：R1消掉R2构成R R2到R1首节点的边不属于R——R中没有R2到R1后退边——R中路径都是先穿过R1（可无），然后穿过R2（可无），但不能返回R1——R2不会影响R1中节点转移函数 对R1中的B：genR,B=genR1,B，killR,B=killR1,B 指针指向规则（续） 若对p进行其他形式的赋值，p不能指向任何对象 对其他变量进行赋值，不会影响p指向哪个变量（无多重指针） in[B]：在块B的入口点，指针p指向的变量的集合——序对(p, a)的集合 out[B]：含义类似in[B] trans函数 transB：将in[B]作为参数，计算出out[B] 对单条语句计算，组合起来即可 transB计算规则： a为数组，语句s是p=a或p=a±c，则transs(S)=(S-{(p,b)|b是任意变量})∪{(p,a)} s:p=q±c，q是指针，c是非零整数，则transs(S)=(S-{(p,b)|b是任意变量})∪{(p,b)|(q,b)∈S且b为数组} s：p=q，则transs(S)=(S-{(p,b)|b是任意变量})∪{(p,b)|(q,b)∈S} transB计算规则（续） s将其他任何表达式的值赋予p，则transs(S)=S-{(p,b)|b是任意变量} s不是为指针赋值，则transs(S)=S  若B由语句s1, s2, …, sk组成，则transB(S)=transs k(transs k-1(…(transs2(transs1(S)))…) 例10.26 out[B1]=transB1(Φ)={(q, c)} out[B2]=transB2({(q,c)})={(p, c), (q, a)} out[B3]=transB3({(q,c)})={(p, a), (q, c