资源描述：
《编译原理chapter8.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第八章基本块和轨迹BasicBlocksandTraces计算机科学与技术学院刘慧canonical（规范的）：被尽可能地简化到最简单或最清楚样式的。语义分析阶段生成的中间语言树必须转换成汇编语言或机器语言：Tree语言的操作符都经过了仔细的选择以便与大多数机器的能力相匹配；然而，Tree语言中存在一些与机器语言不能完全对应的情况，也存在一些与编译优化分析相冲突的情况。Tree语言表示的程序和机器语言程序之间存在的不匹配(mismatch)情况：CJUMP指令，真正的机器语言的转移指令在条件为假时下降至下一
2、条指令。ESEQ结点会使得子树的不同计算顺序产生不同的结果。在表达式中使用CALL结点情况类似。当企图将参数送入固定的形参寄存器集合时，在一个CALL结点的参数表达式中使用另一个CALL结点会出现问题。对于任意一棵树，将它重写为等价的没有上述任何一种情况的树：重写成一列不含SEQ和ESEQ结点的规范树(canonicaltree)；将这一列树分组组合成其内不含转移和标号的基本块(basicblock)集合；对基本块排序并形成一组轨迹(trace)，轨迹中每一个CJUMP之后都直接跟随它的false标号。8.
3、1CanonicalTreesTransformationsonESEQTheideatoeliminateESEQnodes:liftthemhigherandhigherinthetree,untiltheycanbecomeSEQnodes.规范树：（1）无SEQ或ESEQ；（2）每一个CALL的父亲不是EXP(…)，就是MOVE(TEMPt,…)。ESEQs1ESEQs2eESEQ(s1,ESEQ(s2,e))ESEQs1SEQs2eESEQ(SEQ(s1,s2),e)BINOP(op,ESEQ(s
4、,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(TEMP
5、t,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,ES
6、EQ(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;Anythingelseisassumednotto
7、commute.staticboolcommute(T_stmx,T_expy){returnisNop(x)
8、
9、y->kind==T_NAME
10、
11、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
12、交换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，使得reco
