基于dag的基本塊優(yōu)化參考

基于DAG的基本塊優(yōu)化1．實驗?zāi)康呐c任務(wù)了解基本塊的DAG表示及其應(yīng)用，掌握局部優(yōu)化的基本方法。2．實驗要求設(shè)計一個轉(zhuǎn)換程序，把由四元式序列表示的基本塊轉(zhuǎn)換為DAG，并在構(gòu)造DAG的過程中，進行合并已知量、刪除無用賦值及刪除公共子表達式等局部優(yōu)化處理。最后再從所得到的DAG出發(fā)，按原來生成DAG各個結(jié)點的順序，重建四元式序列形式的基本塊。3．實驗內(nèi)容(1)DAG的結(jié)點類型只考慮0型、1型和2型，如下表所示。類型四元式DAG結(jié)點0型(=，B， ，A) ①AB1型(op，B， ，A)② op①2型(op，B，C，A)(=[ ]，B，C，A)(jrop，B，C，A)(2)由基本塊構(gòu)造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) /* getnode(B)是處理Q時新建結(jié)點 */delnode(B);if((n=getnode(p))= =NULL){makeleaf(p);n=getnode(p)；}}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時新建結(jié)點 */delnode(B);if(newright==1) /* getnode(C)是處理Q時新建結(jié)點 */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;}}}上述算法中應(yīng)設(shè)置如下的函數(shù)：getnode(B)：返回B(可以是標記或附加信息)在當(dāng)前DAG中對應(yīng)的結(jié)點號。makeleaf(B)：構(gòu)造標記為B的葉子結(jié)點。isconsnode(B)：檢查B對應(yīng)的結(jié)點是否為標記為常數(shù)的葉子結(jié)點。calcons(Q.op，B)：計算op B 的值(即合并已知量)。它的另一種調(diào)用形式是calcons(Q.op，B，C)：計算B op C 的值。delnode(B)：刪除B(結(jié)點的標記)在當(dāng)前DAG中對應(yīng)的結(jié)點。findnode(Q.op，B)：在當(dāng)前DAG中查找并返回這樣的結(jié)點：標記為op，后繼為getnode(B)(即查找公共子表達式op B)。它的另一種調(diào)用形式是findnode (Q.op，B，C) (即查找公共子表達式B op C)。makenode(Q.op，B，C)：構(gòu)造并返回標記為op，左右后繼分別為getnode(B)、getnode(C)的內(nèi)部結(jié)點。insertidset(n，A)：若getnode(A)=NULL，則把A附加到結(jié)點n；否則，若A在getnode(A)的附加標識符集中，且getnode(A)無前驅(qū)或雖有前驅(qū)但getnode(A) 附加標識符集中符號數(shù)大于1，則把A從getnode(A)的附加標識符集中刪除(即刪除無用賦值)。請實現(xiàn)上述基本塊的DAG構(gòu)造算法，并添加從所得DAG按原來生成DAG各個結(jié)點的順序，重建四元式序列的功能。(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各個結(jié)點的順序，重建四元式序列如下：(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

總結(jié)

以上是生活随笔為你收集整理的C语言基于dag的基本块优化,基于dag的基本块优化参考.docx的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。