基于DAG的基本块优化.doc

《基于DAG的基本块优化.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于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)BCrop312BC=[

2、]312BCop312（2）由基本块构造DAG算法如下：while(基本块中还有未处理过的四元式){取下一个四元式Q;newleft=newright=0;if(getnode(B)==NULL){makeleaf(B);newleft=1;}switch(Q的类型){case0:n=getnode(B);insertidset(n，A);break;case1:if(isconsnode(B)){p=calcons(Q.op，B);if(newleft==1)/*getnode(B)是处理Q时新建结点*/delnode(B);if((n=getnode(p))==NULL

3、){makeleaf(p);n=getnode(p)；}}else{if((n=findnode(Q.op，B))==NULL)n=makenode(Q.op，B);}insertidset(n，A);break;case2: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

4、时新建结点*/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)：计算opB

5、的值（即合并已知量）。它的另一种调用形式是calcons(Q.op，B，C)：计算BopC的值。delnode(B)：删除B（结点的标记）在当前DAG中对应的结点。findnode(Q.op，B)：在当前DAG中查找并返回这样的结点：标记为op，后继为getnode(B)（即查找公共子表达式opB）。它的另一种调用形式是findnode(Q.op，B，C)（即查找公共子表达式BopC）。makenode(Q.op，B，C)：构造并返回标记为op，左右后继分别为getnode(B)、getnode(C)的内部结点。insertidset(n，A)：若getnode(A)=NU

6、LL，则把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

7、,T4⑤T3,X⑨T6,Y①AB1.52052④T2②⑧T5⑥⑦C按生成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=T1―T2X=T3C=5T4=A*BC=2T5=18+CT6=T4*T5Y=T6#include#include#include#includ