微信小程序联盟网站,加强学科网站建设,装饰工程验收规范最新版,阿里巴巴网站备案号基于dag的基本块优化参考基于DAG的基本块优化1#xff0e;实验目的与任务了解基本块的DAG表示及其应用#xff0c;掌握局部优化的基本方法。2#xff0e;实验要求设计一个转换程序#xff0c;把由四元式序列表示的基本块转换为DAG#xff0c;并在构造DAG的过程中#xff…基于dag的基本块优化参考基于DAG的基本块优化1实验目的与任务了解基本块的DAG表示及其应用掌握局部优化的基本方法。2实验要求设计一个转换程序把由四元式序列表示的基本块转换为DAG并在构造DAG的过程中进行合并已知量、删除无用赋值及删除公共子表达式等局部优化处理。最后再从所得到的DAG出发按原来生成DAG各个结点的顺序重建四元式序列形式的基本块。3实验内容(1)DAG的结点类型只考虑0型、1型和2型如下表所示。类型四元式DAG结点0型(B A) ①AB1型(opB A)② op①2型(opBCA)([ ]BCA)(jropBCA)(2)由基本块构造DAG算法如下while(基本块中还有未处理过的四元式) {取下一个四元式Q;newleftnewright0;if(getnode(B) NULL){makeleaf(B);newleft1;} switch(Q的类型){case 0 :n getnode(B);insertidset(nA);break;case 1: if(isconsnode(B)){pcalcons(Q.opB);if(newleft 1) /* getnode(B)是处理Q时新建结点 */delnode(B);if((ngetnode(p)) NULL){makeleaf(p);ngetnode(p)}}else{if((nfindnode(Q.opB)) NULL)nmakenode(Q.opB);}insertidset(nA);break;case 2: if(getnode(C) NULL){makeleaf(C);newright1;}if(isconsnode(B) isconsnode(C)){pcalcons(Q.opBC);if(newleft1) /* getnode(B)是处理Q时新建结点 */delnode(B);if(newright1) /* getnode(C)是处理Q时新建结点 */delnode(C);if((ngetnode(p)) NULL){makeleaf(p);ngetnode(p)}}else{if((nfindnode(Q.opBC)) NULL)nmakenode(Q.opBC);}insertidset(nA);break;}}}上述算法中应设置如下的函数getnode(B)返回B(可以是标记或附加信息)在当前DAG中对应的结点号。makeleaf(B)构造标记为B的叶子结点。isconsnode(B)检查B对应的结点是否为标记为常数的叶子结点。calcons(Q.opB)计算op B 的值(即合并已知量)。它的另一种调用形式是calcons(Q.opBC)计算B op C 的值。delnode(B)删除B(结点的标记)在当前DAG中对应的结点。findnode(Q.opB)在当前DAG中查找并返回这样的结点标记为op后继为getnode(B)(即查找公共子表达式op B)。它的另一种调用形式是findnode (Q.opBC) (即查找公共子表达式B op C)。makenode(Q.opBC)构造并返回标记为op左右后继分别为getnode(B)、getnode(C)的内部结点。insertidset(nA)若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
