基于dag的基本塊優化參考

基于DAG的基本塊優化1．實驗目的與任務了解基本塊的DAG表示及其應用，掌握局部優化的基本方法。2．實驗要求設計一個轉換程序，把由四元式序列表示的基本塊轉換為DAG，并在構造DAG的過程中，進行合并已知量、刪除無用賦值及刪除公共子表達式等局部優化處理。最后再從所得到的DAG出發，按原來生成DAG各個結點的順序，重建四元式序列形式的基本塊。3．實驗內容(1)DAG的結點類型只考慮0型、1型和2型，如下表所示。類型四元式DAG結點0型(=，B， ，A) ①AB1型(op，B， ，A)② op①2型(op，B，C，A)(=[ ]，B，C，A)(jrop，B，C，A)(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) /* getnode(B)是處理Q時新建結點 */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時新建結點 */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)的內部結點。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 = T6Code.txt文件內容T1 = A * BT2 = 3 / 2T3