基于DAG的基本块优化.docxVIP

基于DAG的基本块优化 1．实验目的与任务 了解基本块的DAG表示及其应用，掌握局部优化的基本方法。 2．实验要求 设计一个转换程序，把由四元式序列表示的基本块转换为DAG，并在构造DAG的过程中，进行合并已知量、删除无用赋值及删除公共子表达式等局部优化处理。最后再从所得到的DAG出发，按原来生成DAG各个结点的顺序，重建四元式序列形式的基本块。 3．实验内容 （1）DAG的结点类型只考虑0型、1型和2型，如下表所示。 类型 四元式 DAG结点 0型 （=，B， ，A） ①A B 1型 (op，B， ，A) ② op ① 2型 (op，B，C，A) (=[ ]，B，C，A) (jrop，B，C，A) BCrop3 B C rop 3 1 2 B C =[] 3 1 2 B C op 3 1 2 （2）由基本块构造DAG算法如下： while(基本块中还有未处理过的四元式) { 取下一个四元式Q; newleft=newright=0; if(getnode(B)= =NULL){ makeleaf(B); newleft=1; } switch(Q的类型){ case 0 : n= getnode(B); insertidset(n，A); break; case 1: if(isconsnode(B)){ p=calcons(Q.op，B); if(newleft= =1) /* getnode(B)是处理Q时新建结点 */ delnode(B); if((n=getnode(p))= =NULL){ makeleaf(p); n=getnode(p)； } } else{ if((n=findnode(Q.op，B))= =NULL) n=makenode(Q.op，B); } insertidset(n，A); break; case 2: if(getnode(C)= =NULL){ makeleaf(C); newright=1; } if(isconsnode(B) isconsnode(C)){ p=calcons(Q.op，B，C); if(newleft==1) /* getnode(B)是处理Q时新建结点 */ delnode(B); if(newright==1) /* getnode(C)是处理Q时新建结点 */ delnode(C); if((n=getnode(p))= =NULL){ makeleaf(p); n=getnode(p)； } } else{ if((n=findnode(Q.op，B，C))= =NULL) n=makenode(Q.op，B，C); } insertidset(n，A); break; } } } 上述算法中应设置如下的函数： getnode(B)：返回B（可以是标记或附加信息）在当前DAG中对应的结点号。 makeleaf(B)：构造标记为B的叶子结点。 isconsnode(B)：检查B对应的结点是否为标记为常数的叶子结点。 calcons(Q.op，B)：计算op B 的值（即合并已知量）。它的另一种调用形式是 calcons(Q.op，B，C)：计算B op C 的值。 delnode(B)：删除B（结点的标记）在当前DAG中对应的结点。 findnode(Q.op，B)：在当前DAG中查找并返回这样的结点：标记为op，后继为getnode(B)（即查找公共子表达式op B）。它的另一种调用形式是findnode (Q.op，B，C) （即查找公共子表达式B op C）。 makenode(Q.op，B，C)：构造并返回标记为op，左右后继分别为getnode(B)、getnode(C)的内部结点。 insertidset(n，A)：若getnode(A)=NULL，则把A附加到结点n；否则，若A在getnode(A)的附加标识符集中，且getnode(A)无前驱或虽有前驱但getnode(A) 附加标识符集中符号数大于1，则把A从getnode(A)的附加标识符集中删除（即删除无用赋值）。 请实现上述基本块的DAG构造算法，并添加从所得DAG按原来生成DAG各个结点的顺序，重建四元式序列的功能。 （3）测试用例 用下面的基本块作为输入： (1) T1 = A * B (2) T2 = 3 / 2 (3) T3 = T1 ― T2 (4) X = T3 (5) C = 5 (6) T4 = A * B (7) C = 2 (8) T5 = 18 + C (9) T6 = T4 * T5 (10) Y = T6 基本块的DAG如下： * * * - ③T1,T4 ⑤T3,X ⑨T6,Y ① A B