文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.
【关键字】精品
基于DAG的基本块优化
1．实验目的与任务
了解基本块的DAG表示及其应用，掌握局部优化的基本方法。 2．实验要求
设计一个转换程序，把由四元式序列表示的基本块转换为DAG，并在构造DAG的过程中，进行合并已知量、删除无用赋值及删除公共子表达式等局部优化处理。最后再从所得到的DAG出发，按原来生成DAG各个结点的顺序，重建四元式序列形式的基本块。
3．实验内容
（1）DAG的结点类型只考虑0型、1型和2型，如下表所示。
类型 四元式 DAG结点 0型 （=，B， ，A） 1型 (op，B， ，A) ①A B ② op ① 2型 (op，B，C，A) (=[ ]，B，C，A) (jrop，B，C，A) （2）由基本块构造DAG算法如下： while(基本块中还有未处理过的四元式) { 取下一个四元式Q;
3 3 3 newleft=newright=0;
op rop =[] if(getnode(B)= =NULL){
makeleaf(B); 1 1 1 2 2 2 newleft=1; B C B C B C }
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)；
1word版本可编辑.欢迎下载支持.
文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.
}
} 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)
2word版本可编辑.欢迎下载支持.
文档从网络中收集，已重新整理排版.word版本可编辑.欢迎下载支持.
的内部结点。
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各个结点的顺序，重建四元式序列如下：-⑤T3,X (1) T1 = A * B (2) T2 = 1.5 ⑨T6,Y (3) T3 = T1 ③T1,T4― 1.5 * (4) X = T3 * (5) T4 = T1 (6) C = 2 ① ② ④T2 ⑧T5 ⑥ (7) T5 = 20 A B 1.5 20 5
(8) T6 = T1 * 20 (9) Y = T6 Code.txt文件内容 T1 = A * B T2 = 3 / 2 T3 = T1 ― T2 X = T3 C = 5
T4 = A * B C = 2
T5 = 18 + C T6 = T4 * T5 Y = T6
#include
3word版本可编辑.欢迎下载支持.
⑦C 2
【精品】参考基于dag的基本块优化
