基于DAG的基本塊優(yōu)化

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)基于DAG的基本塊優(yōu)化1實(shí)驗(yàn)?zāi)康呐c任務(wù)了解基本塊的DAG表示及其應(yīng)用，掌握局部優(yōu)化的基本方法。2實(shí)驗(yàn)要求設(shè)計(jì)一個(gè)轉(zhuǎn)換程序，把由四元式序列表示的基本塊轉(zhuǎn)換為DAG，并在構(gòu)造DAG的過程中，進(jìn)行合并已知量、刪除無用賦值及刪除公共子表達(dá)式等局部優(yōu)化處理。最后再從所得到的DAG出發(fā)，按原來生成DAG各個(gè)結(jié)點(diǎn)的順序，重建四元式序列形式的基本塊。3實(shí)驗(yàn)內(nèi)容（1）DAG的結(jié)點(diǎn)類型只考慮0型、1型和2型，如下表所示。類型四元式DAG結(jié)點(diǎn)0型（=，B， ，A） AB1型(op，B， ，A

2、) op2型(op，B，C，A)(= ，B，C，A)(jrop，B，C，A)BCrop3BCrop312BC=312BCop312（2）由基本塊構(gòu)造DAG算法如下：while(基本塊中還有未處理過的四元式) 取下一個(gè)四元式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時(shí)新建結(jié)點(diǎn) */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時(shí)新建結(jié)點(diǎn) */delnode

4、(B);if(newright=1) /* getnode(C)是處理Q時(shí)新建結(jié)點(diǎn) */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;上述算法中應(yīng)設(shè)置如下的函數(shù)：getnode(B)：返回B（可以是標(biāo)記或附加信息）在當(dāng)前DAG中對應(yīng)的結(jié)點(diǎn)號。makeleaf(B)：構(gòu)造標(biāo)記為B的葉子結(jié)點(diǎn)。isconsnode(B)：檢查B對應(yīng)的結(jié)點(diǎn)是否為標(biāo)記為常數(shù)的葉子結(jié)點(diǎn)。calc

5、ons(Q.op，B)：計(jì)算op B 的值（即合并已知量）。它的另一種調(diào)用形式是calcons(Q.op，B，C)：計(jì)算B op C 的值。delnode(B)：刪除B（結(jié)點(diǎn)的標(biāo)記）在當(dāng)前DAG中對應(yīng)的結(jié)點(diǎn)。findnode(Q.op，B)：在當(dāng)前DAG中查找并返回這樣的結(jié)點(diǎn)：標(biāo)記為op，后繼為getnode(B)（即查找公共子表達(dá)式op B）。它的另一種調(diào)用形式是findnode (Q.op，B，C) （即查找公共子表達(dá)式B op C）。makenode(Q.op，B，C)：構(gòu)造并返回標(biāo)記為op，左右后繼分別為getnode(B)、getnode(C)的內(nèi)部結(jié)點(diǎn)。insertidset(n，

6、A)：若getnode(A)=NULL，則把A附加到結(jié)點(diǎn)n；否則，若A在getnode(A)的附加標(biāo)識符集中，且getnode(A)無前驅(qū)或雖有前驅(qū)但getnode(A) 附加標(biāo)識符集中符號數(shù)大于1，則把A從getnode(A)的附加標(biāo)識符集中刪除（即刪除無用賦值）。請實(shí)現(xiàn)上述基本塊的DAG構(gòu)造算法，并添加從所得DAG按原來生成DAG各個(gè)結(jié)點(diǎn)的順序，重建四元式序列的功能。（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各個(gè)結(jié)點(diǎn)的順序，重建四元式序列如下：(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文件內(nèi)容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 /*符號或變量最大長度*/*結(jié)點(diǎn)類型*/typedef struct nodeint iscons; /*0- 無 1-整型 2-浮點(diǎn)*/int val_int; /*整型值*/double val_float; /*浮點(diǎn)值*/int idnum; /*變量的個(gè)數(shù)*/char idMAXNMAXN; /*變量0valnum-1*/char opMAXN; /*結(jié)點(diǎn)操作*/int left,right; /*左右節(jié)點(diǎn)*/DAGN

9、ODE;#define MAXNN20/*DAG最大結(jié)點(diǎn)數(shù)目*/*DAG*/typedef struct mnodeint num;/*結(jié)點(diǎn)個(gè)數(shù)*/DAGNODE nodeMAXNN;/*結(jié)點(diǎn)內(nèi)容1NUM*/DAG;/*四元式Quaternion*/typedef struct snodeint type;/*類型0 1 2*/char opMAXN;/*操作*/char op1MAXN;/*操作數(shù)1*/char op2MAXN;/*操作數(shù)2*/char ansMAXN;/*結(jié)果*/QUA;void init();/*初始化函數(shù)*/bool getqua(QUA *qua);/*獲取一個(gè)四元式

10、*/int isnums(char *val);/*檢測字符串是否是數(shù)字串 0 標(biāo)識符 1整型數(shù)串 2浮點(diǎn)數(shù)串*/void makeleaf(DAGNODE *n,char val);/*構(gòu)造葉子結(jié)點(diǎn)*/void makenode(DAGNODE *n,char op,int left,int right);/*構(gòu)造中間結(jié)點(diǎn)*/int getnode(DAG dag,char var); /*獲取var所在結(jié)點(diǎn)號*/int find1node(DAG dag,char op1,char op);/*查找已有的表達(dá)式1*/int find2node(DAG dag,char op1,char o

11、p2,char op);/*查找已知表達(dá)式2*/char *isconsnode(DAG dag,char id);/*是否是常數(shù)結(jié)點(diǎn)的id*/void delnode(DAG *dag,int num);/*刪除結(jié)點(diǎn)num*/void delid(DAG *dag,int num);/*刪除某節(jié)點(diǎn)的Id*/void copynode(DAGNODE *to,DAGNODE from);/*復(fù)制結(jié)點(diǎn)值*/void insertvar(DAG *dag,int noden,char var); /*將值var附加在noden結(jié)點(diǎn)*/int insertnode(DAG *dag,DAGNODE

12、dagn);/*將結(jié)點(diǎn)插入DAG*/char *calcons1(char op,char op1);/*計(jì)算op op1的運(yùn)算值*/char *calcons2(char op,char op1,char op2);/*op1 op op2*/void makeDAG();/*構(gòu)造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);/*初始化函數(shù)*/void init()if(fp=fopen(code.txt,r)=NULL)printf(the code file is not existe

14、d.);exit(0);/*獲取一個(gè)四元式*/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=.)/*浮點(diǎn)*

16、/flag=2;break;flag=0;break;elseflag=1; /*整型*/return flag;/*構(gòu)造葉子結(jié)點(diǎn)*/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;/*構(gòu)造中間結(jié)點(diǎn)*/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所在結(jié)點(diǎn)號*/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;/*是否是常數(shù)節(jié)點(diǎn),常數(shù)*/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)/*常數(shù)結(jié)點(diǎn)*/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;/*查找已定義的表達(dá)式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);/*刪除某結(jié)點(diǎn)的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;/*賦值結(jié)點(diǎn)值*/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結(jié)點(diǎn)*/void insertvar(DAG *dag,int noden,char var)(dag-nodenoden.idnum)+;strcpy(dag-nodenoden.iddag-nodenoden.idnum-1,var);/*將結(jié)點(diǎn)插入DAG*/int insertn

23、ode(DAG *dag,DAGNODE dagn)dag-num=dag-num+1;copynode(&(dag-nodedag-num),dagn);return dag-num;/*計(jì)算op op1的運(yùn)算值*/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;/*計(jì)算 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,/)/*！除法結(jié)果為浮點(diǎn)*/sprintf(temp,%g,atof(op1)/atof(op2);return t

26、emp;/*構(gòu)造DAG*/void makeDAG()DAG dag;dag.num=0;/*DAG*/QUA qua; /*四元式*/DAGNODE dagn; /*DAG結(jié)點(diǎn)*/int op1n,op2n,opn,oopn; /*操作數(shù)1-B 2-C所在結(jié)點(diǎn)號*/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);/*將結(jié)點(diǎn)插入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已經(jīng)定義*/delid(&dag,opn);insertvar(&dag,op1n,qua.ans);/*將ans-A附加在B的結(jié)點(diǎn)上*/break;case 1:/*(op,B, A)*/if(isconsnode(dag,qua.op1)!=NULL)/*op1-B是常數(shù) 返回值為 1或者 2*/if(newleft=1)/*op1-B是新建結(jié)點(diǎn)*/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已經(jīng)定義*/delid(&dag,oopn);insertvar(&dag,opn,qua.ans);/*將ans-A附加在B的結(jié)點(diǎn)上*/break;case 2:/*(op,B,C,A)*/if(getnode(dag,qua.op2)=0)makeleaf(&dagn,qua.op2);insertnode(&dag,dagn);/*將結(jié)點(diǎn)插入DAG*/newright=1;if(isconsnode(dag,qua.op1)!=NULL)&(isconsnode(dag,qua.op2)!=NULL) /*op1 -A op2 -B 在結(jié)點(diǎn)中*/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