C语言基于dag的基本块优化,基于dag的基本块优化参考.docx

基于dag的基本块优化参考

基于DAG的基本块优化1．实验目的与任务了解基本块的DAG表示及其应用，掌握局部优化的基本方法。2．实验要求设计一个转换程序，把由四元式序列表示的基本块转换为DAG，并在构造DAG的过程中，进行合并已知量、删除无用赋值及删除公共子表达式等局部优化处理。最后再从所得到的DAG出发，按原来生成DAG各个结点的顺序，重建四元式序列形式的基本块。3．实验内容(1)DAG的结点类型只考虑0型、1型和2型，如下表所示。类型四元式DAG结点0型(=，B， ，A) ①AB1型(op，B， ，A)② op①2型(op，B，C，A)(=[ ]，B，C，A)(jrop，B，C，A)(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) 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) delnode(B);if(newright==1) 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如下：按生成DAG各个结点的顺序，重建四元式序列如下：(1) T1 = A * B(2) T2 = 1.5(3) T3 = T1 ― 1.5(4) X = T3 (5) T4 = T1(6) C = 2(7) T5 = 20(8) T6 = T1 * 20(9) Y = T6Code.txt文件内容T1 = A * BT2 = 3 / 2T3