基于DAG的基本块优化

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业基于DAG的基本块优化1实验目的与任务了解基本块的DAG表示及其应用，掌握局部优化的基本方法。2实验要求设计一个转换程序，把由四元式序列表示的基本块转换为DAG，并在构造DAG的过程中，进行合并已知量、删除无用赋值及删除公共子表达式等局部优化处理。最后再从所得到的DAG出发，按原来生成DAG各个结点的顺序，重建四元式序列形式的基本块。3实验内容（1）DAG的结点类型只考虑0型、1型和2型，如下表所示。类型四元式DAG结点0型（=，B， ，A） AB1型(op，B， ，A

2、) op2型(op，B，C，A)(= ，B，C，A)(jrop，B，C，A)BCrop3BCrop312BC=312BCop312（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) /* getnod

3、e(B)是处理Q时新建结点 */delnode(B);if(n=getnode(p)= =NULL)makeleaf(p);n=getnode(p)；elseif(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

4、(B);if(newright=1) /* getnode(C)是处理Q时新建结点 */delnode(C);if(n=getnode(p)= =NULL)makeleaf(p);n=getnode(p)；elseif(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对应的结点是否为标记为常数的叶子结点。calc

5、ons(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，

6、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 =

7、18 + C(9) T6 = T4 * T5(10) Y = T6基本块的DAG如下：*-T1,T4T3,XT6,YAB1.52052T2T5C按生成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 = T3 C = 5T4 = A * BC = 2T5 = 18 + CT6 = T4 * T5Y =

8、 T6#include #include #include #include /*function ans data statement*/#define MAXN 5 /*符号或变量最大长度*/*结点类型*/typedef struct nodeint iscons; /*0- 无 1-整型 2-浮点*/int val_int; /*整型值*/double val_float; /*浮点值*/int idnum; /*变量的个数*/char idMAXNMAXN; /*变量0valnum-1*/char opMAXN; /*结点操作*/int left,right; /*左右节点*/DAGN

9、ODE;#define MAXNN20/*DAG最大结点数目*/*DAG*/typedef struct mnodeint num;/*结点个数*/DAGNODE nodeMAXNN;/*结点内容1NUM*/DAG;/*四元式Quaternion*/typedef struct snodeint type;/*类型0 1 2*/char opMAXN;/*操作*/char op1MAXN;/*操作数1*/char op2MAXN;/*操作数2*/char ansMAXN;/*结果*/QUA;void init();/*初始化函数*/bool getqua(QUA *qua);/*获取一个四元式

10、*/int isnums(char *val);/*检测字符串是否是数字串 0 标识符 1整型数串 2浮点数串*/void makeleaf(DAGNODE *n,char val);/*构造叶子结点*/void makenode(DAGNODE *n,char op,int left,int right);/*构造中间结点*/int getnode(DAG dag,char var); /*获取var所在结点号*/int find1node(DAG dag,char op1,char op);/*查找已有的表达式1*/int find2node(DAG dag,char op1,char o

11、p2,char op);/*查找已知表达式2*/char *isconsnode(DAG dag,char id);/*是否是常数结点的id*/void delnode(DAG *dag,int num);/*删除结点num*/void delid(DAG *dag,int num);/*删除某节点的Id*/void copynode(DAGNODE *to,DAGNODE from);/*复制结点值*/void insertvar(DAG *dag,int noden,char var); /*将值var附加在noden结点*/int insertnode(DAG *dag,DAGNODE

12、dagn);/*将结点插入DAG*/char *calcons1(char op,char op1);/*计算op op1的运算值*/char *calcons2(char op,char op1,char op2);/*op1 op op2*/void makeDAG();/*构造DAG*/void dispDAG(DAG dag); /*输出DAG*/char *getv(DAG dag,int dagn);FILE *fp;/*文件指针，指向代码文件*/void dispcode();int main()init();dispcode();init();makeDAG();return

13、0;void dispcode()static int i=1;QUA q;while(getqua(&q)if(q.type=0)printf(%d) %s%s%sn,i+,q.ans,q.op,q.op1);else if(q.type=1)printf(%d) %s=%s%sn,i+,q.ans,q.op,q.op1);elseprintf(%d) %s=%s%s%sn,i+,q.ans,q.op1,q.op,q.op2);/*初始化函数*/void init()if(fp=fopen(code.txt,r)=NULL)printf(the code file is not existe

14、d.);exit(0);/*获取一个四元式*/bool getqua(QUA *qua)int t;if(feof(fp)fclose(fp);return false;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);return false;return true;fscanf(fp,%s,qu

15、a-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);return false;return true; fscanf(fp,%s,qua-op2);qua-type=2;return true;int isnums(char *val)int i,flag;for(i=0;vali;i+)if(!isdigit(vali)if(vali=.)/*浮点*

16、/flag=2;break;flag=0;break;elseflag=1; /*整型*/return flag;/*构造叶子结点*/void makeleaf(DAGNODE *n,char val)switch(isnums(val)case 0:n-iscons=0;n-val_float=0;n-val_int=0;n-idnum=1;strcpy(n-id0,val);break;case 1:n-idnum=0;n-iscons=1;n-val_int=atoi(val);n-val_float=0;break;case 2:n-idnum=0;n-iscons=2;n-val_i

17、nt=0;n-val_float=atof(val);break;strcpy(n-op,);n-left=n-right=0;/*构造中间结点*/void makenode(DAGNODE *n,char op,int left,int right)n-idnum=0;n-iscons=0;strcpy(n-op,op);n-left=left;n-right=right;/*获取var所在结点号*/int getnode(DAG dag,char var)int i,j;if(dag.num=0) return 0;for(i=1;i=dag.num;i+)switch(isnums(va

18、r)case 0:for(j=0;jdag.nodei.idnum;j+)if(!strcmp(dag.nodei.idj,var)return i;break;case 1:if(dag.nodei.val_int=atoi(var)return i;break;case 2:if(dag.nodei.val_float=atof(var)return i;break;return 0;/*是否是常数节点,常数*/char *isconsnode(DAG dag,char id)int i,j;char *temp;temp=(char *)malloc(MAXN*sizeof(char);

19、if(isnums(id) strcpy(temp,id);return temp;for(i=1;i0)/*常数结点*/for(j=0;jdag.nodei.idnum;j+)if(!strcmp(dag.nodei.idj,id)switch(dag.nodei.iscons)case 1:sprintf(temp,%d,dag.nodei.val_int);break;case 2:sprintf(temp,%g,dag.nodei.val_float);break;return temp;return NULL;/*查找已定义的表达式1*/int find1node(DAG dag,c

20、har op1,char op)int i;int op1n;op1n=getnode(dag,op1);for(i=1;i=dag.num;i+)if(dag.nodei.left=op1n)&!strcmp(dag.nodei.op,op)return i;return 0;/*查找已知表示式2*/int find2node(DAG dag,char op1,char op2,char op)int i;int op1n,op2n;op1n=getnode(dag,op1);op2n=getnode(dag,op2);for(i=1;inum=0) return;for(i=1;inum;

21、i+)if(i=num)for(j=i;jnum;j+)copynode(&(dag-nodej),dag-nodej+1);-(dag-num);/*删除某结点的id*/void delid(DAG *dag,int num)int i;if(dag-num=0) return;for(i=0;inodenum.idnum;i+)strcpy(dag-nodenum.idi,);dag-nodenum.idnum=0;/*赋值结点值*/void copynode(DAGNODE*to,DAGNODE from)int i;to-idnum=from.idnum;for(i=0;iidi,fr

22、om.idi);to-iscons=from.iscons;to-val_int=from.val_int;to-val_float=from.val_float;strcpy(to-op,from.op);to-left=from.left;to-right=from.right;/*将值var附加在noden结点*/void insertvar(DAG *dag,int noden,char var)(dag-nodenoden.idnum)+;strcpy(dag-nodenoden.iddag-nodenoden.idnum-1,var);/*将结点插入DAG*/int insertn

23、ode(DAG *dag,DAGNODE dagn)dag-num=dag-num+1;copynode(&(dag-nodedag-num),dagn);return dag-num;/*计算op op1的运算值*/char *calcons1(char op,char op1)char *temp;if(!strcmp(op,!)temp=(char *)malloc(MAXN*sizeof(char);switch(isnums(op1)case 1:sprintf(temp,%d,!atoi(op1);break; return temp;/*计算 op1 op op2 的值*/cha

24、r *calcons2(char op,char op1,char op2)int ch=isnums(op1)isnums(op2)?isnums(op1):isnums(op2);char *temp;temp=(char *)malloc(MAXN*sizeof(char);if(!strcmp(op,+)switch(ch)case 1:sprintf(temp,%d,atoi(op1)+atoi(op2);break;case 2:sprintf(temp,%g,atof(op1)+atof(op2);break;else if(!strcmp(op,-)switch(ch)case

25、 1:sprintf(temp,%d,atoi(op1)-atoi(op2);break;case 2:sprintf(temp,%g,atof(op1)-atof(op2);break;else if(!strcmp(op,*)switch(ch)case 1:sprintf(temp,%d,atoi(op1)*atoi(op2);break;case 2:sprintf(temp,%g,atof(op1)*atof(op2);break;else if(!strcmp(op,/)/*！除法结果为浮点*/sprintf(temp,%g,atof(op1)/atof(op2);return t

26、emp;/*构造DAG*/void makeDAG()DAG dag;dag.num=0;/*DAG*/QUA qua; /*四元式*/DAGNODE dagn; /*DAG结点*/int op1n,op2n,opn,oopn; /*操作数1-B 2-C所在结点号*/char tempMAXN;int newleft,newright;while(getqua(&qua)/*op1-B没有定义*/newleft=newright=0;if(getnode(dag,qua.op1)=0)makeleaf(&dagn,qua.op1);insertnode(&dag,dagn);/*将结点插入DA

27、G*/newleft=1;switch(qua.type)case 0:/*(=,B, ,A)*/op1n=getnode(dag,qua.op1);if(opn=getnode(dag,qua.ans)!=0)/*ans-A已经定义*/delid(&dag,opn);insertvar(&dag,op1n,qua.ans);/*将ans-A附加在B的结点上*/break;case 1:/*(op,B, A)*/if(isconsnode(dag,qua.op1)!=NULL)/*op1-B是常数 返回值为 1或者 2*/if(newleft=1)/*op1-B是新建结点*/delnode(&

28、dag,getnode(dag,qua.op1);sprintf(temp,%s,calcons1(qua.op,isconsnode(dag,qua.op1);if(getnode(dag,temp)=0)makeleaf(&dagn,temp);opn=insertnode(&dag,dagn);elseif(opn=find1node(dag,qua.op1,qua.op)=0) makenode(&dagn,qua.op,getnode(dag,qua.op1),0); opn=insertnode(&dag,dagn);if(oopn=getnode(dag,qua.ans)!=0)

29、/*ans-A已经定义*/delid(&dag,oopn);insertvar(&dag,opn,qua.ans);/*将ans-A附加在B的结点上*/break;case 2:/*(op,B,C,A)*/if(getnode(dag,qua.op2)=0)makeleaf(&dagn,qua.op2);insertnode(&dag,dagn);/*将结点插入DAG*/newright=1;if(isconsnode(dag,qua.op1)!=NULL)&(isconsnode(dag,qua.op2)!=NULL) /*op1 -A op2 -B 在结点中*/sprintf(temp,%

30、s,calcons2(qua.op,isconsnode(dag,qua.op1),isconsnode(dag,qua.op2);if(newleft=1)delnode(&dag,getnode(dag,qua.op1);if(newright=1)delnode(&dag,getnode(dag,qua.op2);if(getnode(dag,temp)=0)makeleaf(&dagn,temp);opn=insertnode(&dag,dagn);/*/else/*/if(opn=find2node(dag,qua.op1,qua.op2,qua.op)=0)op1n=getnode(dag,qua.op1);op2n=getnode(dag,qua.op2);makenode(&da