编译原理chapter8

第八章基本块和轨迹BasicBlocksandTraces计算机科学与技术学院刘慧canonical（规范的）：被尽可能地简化到最简单或最清楚样式的。语义分析阶段生成的中间语言树必须转换成汇编语言或机器语言：Tree语言的操作符都经过了仔细的选择以便与大多数机器的能力相匹配；然而，Tree语言中存在一些与机器语言不能完全对应的情况，也存在一些与编译优化分析相冲突的情况。Tree语言表示的程序和机器语言程序之间存在的不匹配(mismatch)情况：CJUMP指令，真正的机器语言的转移指令在条件为假时下降至下一条指令。ESEQ结点会使得子树的不同计算顺序产生不同的结果。在表达式中使用CALL结点情况类似。当企图将参数送入固定的形参寄存器集合时，在一个CALL结点的参数表达式中使用另一个CALL结点会出现问题。对于任意一棵树，将它重写为等价的没有上述任何一种情况的树：重写成一列不含SEQ和ESEQ结点的规范树(canonicaltree)；将这一列树分组组合成其内不含转移和标号的基本块(basicblock)集合；对基本块排序并形成一组轨迹(trace)，轨迹中每一个CJUMP之后都直接跟随它的false标号。8.1CanonicalTreesTransformationsonESEQTheideatoeliminateESEQnodes:liftthemhigherandhigherinthetree,untiltheycanbecomeSEQnodes.规范树：（1）无SEQ或ESEQ；（2）每一个CALL的父亲不是EXP(…)，就是MOVE(TEMPt,…)。ESEQs1ESEQs2eESEQ(s1,ESEQ(s2,e))ESEQs1SEQs2eESEQ(SEQ(s1,s2),e)BINOP(op,ESEQ(s,e1),e2)BINOPopESEQse1e2BINOPopESEQse1ESEQ(s,BINOP(op,e1,e2))e2MEM(ESEQ(s,e1))=ESEQ(s,MEM(e1))JUMP(ESEQ(s,e1))=SEQ(s,JUMP(e1))CJUMP(op,ESEQ(s,e1),e2,l1,l2)=SEQ(s,CJUMP(op,e1,e2,l1,l2))BINOP(op,e1,ESEQ(s,e2))BINOPope1ESEQse2TEMPESEQopESEQsTEMPESEQ(MOVE(TEMPt,e1),ESEQ(s,BINOP(op,TEMPt,e2)))e2MOVEtBINOPe1tBINOPopESEQse1ESEQ(s,BINOP(op,e1,e2))e2?s是MOVE(MEM(x),y)e1是BINOP(PLUS,MEM(x),z)则当s的计算先于e1时，该程序的计算结果会与s的计算后于e1时不同。CJUMP(op,e1,ESEQ(s,e2),l1,l2)=SEQ(MOVE(TEMPt,e1),SEQ(s,CJUMP(op,TEMPt,e2,l1,l2)))BINOP(op,e1,ESEQ(s,e2))BINOPope1CJUMP(op,e1,ESEQ(s,e2),l1,l2)=SEQ(s,CJUMP(op,e1,e2,l1,l2))ESEQse2BINOPopESEQse1ESEQ(s,BINOP(op,e1,e2))e2ifs,e1commute‘commute’function:Aconstantcommuteswithanystatement;Theemptystatementcommuteswithanyexpression;Anythingelseisassumednottocommute.staticboolcommute(T_stmx,T_expy){returnisNop(x)||y-kind==T_NAME||y-kind==T_CONST;}GeneralRewritingRules像Fig8.1那样，建立一套重写规则，将ESEQ移出语句或者表达式之外。[e1,e2,ESEQ(s,e3)]s与e1,e2可交换(s;[e1,e2,e3])(SEQ(MOVE(t1,e1),SEQ(MOVE(t2,e2),s);[TEMP(t1),TEMP(t2),e3])e2不能与s交换e2可与s交换，但e1不行(SEQ(MOVE(t1,e1),s);[TEMP(t1),e2,e3])Algorithm：“subexpression-extraction”method;“subexpression-insertion”method.给定一个已清除了所有子表达式中的ESEQ的表达式或语句，算法将生成该表达式或语句的一个新版本。函数do_exp和do_stm辅助函数recorder，使得recorder能够根据给它的指针表从右至左地从一个表达式ei中抽出语句si。MovingCALLStoTopLevelTree语言允许将CALL结点作为子表达式。但是，在实际应用中CALL的实现是：将结果返回到同一个规定的返回值寄存器TEMP(RV)中。举例：BINOP(PLUS,CALL(…),CALL(…))利用重写规则解决：将每一个返回值立即赋给一个新的临时寄存器。CALL(fun,args)→ESEQ(MOVE(TEMPt,CALL(fun,args)),TEMPt)ALinearListofStatements一旦整个函数体s0已用do_exp处理完毕，将得到一棵树s0’，其中所有的SEQ结点都集中在树的顶部（决不会在其他类型的结点之下）。规则：SEQ(SEQ(a,b),c)=SEQ(a,seq(b,c))将s0’线性化SEQ(s1,SEQ(s2,…,SEQ(sn-1,sn)…))其中SEQ结点完全不提供结构化信息，只是由语句组成的简单列表：s1,s2,…,sn-1,sn8.2TamingConditionalBranchesTree语言与大多数机器指令集不能直接等价的另一个原因是两路分支CJUMP指令。在真实的机器中，条件转移指令或者使控制发生转移（条件为真时），或者“下降到”下一条指令。重新安排CJUMP，使得每一个CJUMP(cond,lt,lf)之后直接跟随的是LABEL(lf)，即“false分支”。Step1:取一列规范树，并由它们形成基本块；Step2:对这些基本块排列形成一条轨迹。BasicBlocks在确定程序中转移指令的目标地址时，需要分析程序的控制流(controlflow)。分析程序的控制流中，任何非转移指令的行为对分析都没有意义，因此可以将由非分支指令组成的序列集中到一个基本块中，并分析这些基本块之间的控制流。基本块是语句组成的一个序列，控制只能从这个序列的开始处进入并从结尾处退出：第一个语句是一个LABEL；最后一个语句是JUMP或者CJUMP；没有其他的LABEL、JUMP或者CJUMP。方法：从头至尾扫描语句序列，每发现一个LABEL，就开始一个新的基本块（并结束前一个基本块）；每发现一个JUMP或CJUMP，就结束一个基本块（并开始下一个基本块）。Traces可以按任意顺序安排这些基本块，并且程序执行的结果仍是相同的。利用这一点选择适当的基本块排列顺序，以满足每个CJUMP之后都跟随它的false标号这一条件。同样可以安排基本块使得无条件转移JUMP之后直接跟随的是它们的目标标号，这样便可以删除这些JUMP，使编译生成的程序的执行速度更快。轨迹(trace)是在程序执行期间可能连贯执行的语句序列，它可以包含条件分支。为了适当安排CJUMP和false标号，需要建立一组正好能覆盖整个程序的轨迹，即每一个基本块在一条且只在一条轨迹中。方法：从某个基本块开始（它是一个轨迹的开始），寻找一条可能执行的路径——及寻求该轨迹的其余部分。将程序的所有基本块放至表Q中。whileQ不为空开始一个新的（空）轨迹，称之为T。从Q中删除头元素b。whileb还未被标记标记b；将b添加到当前轨迹T的末尾。检查b的各个后继（b分支到的基本块）；if存在着未标记的后继cb←c（b的所有后继都已被标记。）结束当前轨迹T。Finishingup此时，大多数的CJUMP之后跟随着它们的true或false标号。进行细微调整：所有后面跟着false标号的CJUMP维持不变；对任何后跟true标号的CJUMP，交换它们的true和false标号，并将其条件更改成相反的条件；对其后跟随的既不是它的true也不是false标号的CJUMP（cond,a,b,lt,lf)，生成一个新的标号lf’，并用如下三条语句重写该CJUMP，使其false紧跟其后：CJUMP（cond,a,b,lt,l’f)LABELl’fJUMP(NAMElf)