基于DAG的基本块优化

基于DAG的基本块优化1．实验目的与任务了解基本块的DAG表示及其应用，掌握局部优化的基本方法。2．实验要求设计一个转换程序，把由四元式序列表示的基本块转换为DAG，并在构造DAG的过程中，进行合并已知量、删除无用赋值及删除公共子表达式等局部优化处理。最后再从所得到的DAG出发，按原来生成DAG各个结点的顺序，重建四元式序列形式的基本块。3．实验内容（1）DAG的结点类型只考虑0型、1型和2型，如下表所示。（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){makeleaf(p);类型四元式DAG结点0型（=，B，，A）①AB1型(op，B，，A)②op①2型(op，B，C，A)(=[]，B，C，A)(jrop，B，C，A)BC=[]312BCrop312BCop312n=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时新建结点*/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的值（即合并已知量）。它的另一种调用形式是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)=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=T6**-③T1,T4⑤T3,X⑨T6,Y①AB1.52052④T2②⑧T5⑥⑦CCode.txt文件内容T1=A*BT2=3/2T3=T1―T2X=T3C=5T4=A*BC=2T5=18+CT6=T4*T5Y=T6#includestdio.h#includectype.h#includestring.h#includestdlib.h/*functionansdatastatement*/#defineMAXN5/*符号或变量最大长度*//*结点类型*/typedefstructnode{intiscons;/*0--无1--整型2--浮点*/intval_int;/*整型值*/doubleval_float;/*浮点值*/intidnum;/*变量的个数*/charid[MAXN][MAXN];/*变量0~valnum-1*/charop[MAXN];/*结点操作*/intleft,right;/*左右节点*/}DAGNODE;#defineMAXNN20/*DAG最大结点数目*//*DAG*/typedefstructmnode{intnum;/*结点个数*/DAGNODEnode[MAXNN];/*结点内容1~NUM*/}DAG;/*四元式Quaternion*/typedefstructsnode{inttype;/*类型012*/charop[MAXN];/*操作*/charop1[MAXN];/*操作数1*/charop2[MAXN];/*操作数2*/charans[MAXN];/*结果*/}QUA;voidinit();/*初始化函数*/boolgetqua(QUA*qua);/*获取一个四元式*/intisnums(char*val);/*检测字符串是否是数字串0标识符1整型数串2浮点数串*/voidmakeleaf(DAGNODE*n,charval[]);/*构造叶子结点*/voidmakenode(DAGNODE*n,charop[],intleft,intright);/*构造中间结点*/intgetnode(DAGdag,charvar[]);/*获取var[]所在结点号*/intfind1node(DAGdag,charop1[],charop[]);/*查找已有的表达式1*/intfind2node(DAGdag,charop1[],charop2[],charop[]);/*查找已知表达式2*/char*isconsnode(DAGdag,charid[]);/*是否是常数结点的id*/voiddelnode(DAG*dag,intnum);/*删除结点num*/voiddelid(DAG*dag,intnum);/*删除某节点的Id*/voidcopynode(DAGNODE*to,DAGNODEfrom);/*复制结点值*/voidinsertvar(DAG*dag,intnoden,charvar[]);/*将值var附加在noden结点*/intinsertnode(DAG*dag,DAGNODEdagn);/*将结点插入DAG*/char*calcons1(charop[],charop1[]);/*计算opop1的运算值*/char*calcons2(charop[],charop1[],charop2[]);/*op1opop2*/voidmakeDAG();/*构造DAG*/voiddispDAG(DAGdag);/*输出DAG*/char*getv(DAGdag,intdagn);FILE*fp;/*文件指针，指向代码文件*/voiddispcode();intmain(){init();dispcode();init();makeDAG();return0;}voiddispcode(){staticinti=1;QUAq;while(getqua(&q)){if(q.type==0)printf((%d)%s%s%s\n,i++,q.ans,q.op,q.op1);elseif(q.type==1)printf((%d)%s=%s%s\n,i++,q.ans,q.op,q.op1);elseprintf((%d)%s=%s%s%s\n,i++,q.ans,q.op1,q.op,q.op2);}}/*初始化函数*/voidinit(){if((fp=fopen(code.txt,r))==NULL){printf(thecodefileisnotexisted.);exit(0);}}/*获取一个四元式*/boolgetqua(QUA*qua){intt;if(feof(fp)){fclose(fp);returnfalse;}fscanf(fp,%d,&t);fscanf(fp,%s,qua-ans);fscanf(fp,%s,qua-op);fscanf(fp,%s,qua-op1);if(fgetc(fp)=='\n'||feof(fp)){strcpy(qua-op2,);if(!strcmp(qua-op,=))qua-type=0;if(feof(fp)){fclose(fp);returnfalse;}returntrue;}fscanf(fp,%s,qua-op);if(fgetc(fp)=='\n'||feof(fp)){strcpy(qua-op2,qua-op);strcpy(qua-op,qua-op1);strcpy(qua-op1,qua-op2);strcpy(qua-op2,);qua-type=1;if(feof(fp)){fclose(fp);returnfalse;}returntrue;}fscanf(fp,%s,qua-op2);qua-type=2;returntrue;}intisnums(char*val){inti,flag;for(i=0;val[i];i++){if(!isdigit(val[i])){if(val[i]=='.')/*浮点*/{flag=2;break;}flag=0;break;}else{flag=1;/*整型*/}}returnflag;}/*构造叶子结点*/voidmakeleaf(DAGNODE*n,charval[]){switch(isnums(val)){case0:n-iscons=0;n-val_float=0;n-val_int=0;n-idnum=1;strcpy(n-id[0],val);break;case1:n-idnum=0;n-iscons=1;n-val_int=atoi(val);n-val_float=0;break;case2:n-idnum=0;n-iscons=2;n-val_int=0;n-val_float=atof(val);break;}strcpy(n-op,);n-left=n-right=0;}/*构造中间结点*/voidmakenode(DAGNODE*n,charop[],intleft,intright){n-idnum=0;n-iscons=0;strcpy(n-op,op);n-left=left;n-right=right;}/*获取var[]所在结点号*/intgetnode(DAGdag,charvar[]){inti,j;if(dag.num==0)return0;for(i=1;i=dag.num;i++){switc