編譯原理之代碼生成-預(yù)覽頁
【正文】 中的名字采用不同尋址方式。 ? 計算 ? OP dst, src1, src2；把 src1和 scr2中的值運算后將結(jié)果存放到 dst中。 addr：內(nèi)存地址 /寄存器 ? 保存 ? ST x, r；把寄存器 r中的內(nèi)容保存到 x中。 目標代碼中的地址 ? Q:如何將 IR中的名字轉(zhuǎn)換成目標代碼中的地址？ A：程序運行時環(huán)境劃分為 4個區(qū)域：代碼區(qū) Code、靜態(tài)區(qū) Static、棧區(qū) Stack和堆區(qū) Heap。 ?下次引用和活躍信息可用于代碼生成 ? 如果 x在 i處不活躍，且 x占用了一個寄存器，則該寄存器在 i后可用于其它目的。 ? 令語句 i和 x、 y、 z的當前活躍性信息 /使用信息關(guān)聯(lián) ? 設(shè)置 x為不活躍、無下次引用 ? 設(shè)置 y和 z為活躍，并指明它們的下一次使用為語句 i 注意二和三順序不能錯， ? 查看基本塊 a=a+b,a最終是活躍還是？ 流圖的構(gòu)造 ?流圖的頂點是基本塊 ?兩個頂點 B和 C之間有一條有向邊，當且僅當基本塊 C的第一個指令有可能在 B的最后一個指令之后執(zhí)行。 ? 標記： s的運算符 ? 附加標記：一組變量，表明 s是在此基本塊內(nèi)最晚對該變量定值 ? 某些輸出結(jié)點：結(jié)點對應(yīng)的變量在基本塊出口處活躍 （ 出口活躍屬于全局數(shù)據(jù)流分析 ） DAG示例 語句 S的結(jié)點 N和子結(jié)點 s運算符當結(jié)點標記 附加標記 變量的結(jié)點 DAG圖的構(gòu)造 ?為基本塊中出現(xiàn)的每個變量建立結(jié)點（表示基本值） ?順序掃描各個三地址指令 ? 如果指令為 x=y op z ? 為這個指令建立結(jié)點 N，標號為 op； ? N的子結(jié)點為 y、 z當前關(guān)聯(lián)的結(jié)點； ? X和 N關(guān)聯(lián)； ? 如果指令為 x=y； ? 不建立新結(jié)點； ? 設(shè) y關(guān)聯(lián)到 N，那么 x現(xiàn)在也關(guān)聯(lián)到 N ?掃描結(jié)束后，對于所有在出口處活躍的變量 x，將x所關(guān)聯(lián)的結(jié)點設(shè)置為輸出結(jié)點 DAG的作用 ?DAG圖描述了基本塊運行時各個值之間的關(guān)系。該代碼本可優(yōu)化，但發(fā)現(xiàn)不了 在 DAG上應(yīng)用代數(shù)恒等式的優(yōu)化 ?消除計算步驟 ? x+0=0+x=x x0=x ? x*1=1*x=x x/1=x ?降低計算強度 ? X2=x*x 2*x=x+x ?常量合并 ? 2* ?實現(xiàn)這些優(yōu)化時，只需要在 DAG圖上尋找特定的模式 56 數(shù)組引用－避免誤優(yōu)化 ?注意： a[j]可能改變 a[i]的值，因此不能和普通的運算符一樣構(gòu)造相應(yīng)的結(jié)點 ? x=a[i] ? a[j]=y ? z=a[i] ?從數(shù)組取值的運算 x=a[i]對應(yīng)于 “ =[]”的結(jié)點， x作為這個結(jié)點的標號之一； ?對數(shù)組賦值的運算對應(yīng)于 “ []=”的結(jié)點；沒有關(guān)聯(lián)的變量、且殺死所有依賴于 a的變量； Killed節(jié)點不能成為公共子表達式 ? 殺手 ? 被殺者 ? 殺手 引入新的運算符 數(shù)組引用的 DAG的例子 ?b=12+a ?x=b[i] ?b[j]=y ?注意 a是被殺死結(jié)點的孫結(jié)點?？梢酝ㄟ^（全局 /局部）指針分析 ,縮小范圍；比如針對 ? p=amp。 ? 對數(shù)組元素的求值必須跟在所有原來在它之前的賦值指令之后 ? 對變量的使用必須跟在所有原來在它之前的過程調(diào) 用和指針間接賦值之后 ? 任何過程調(diào)用或者指針間接賦值必須跟在原來在它 之前的變量求值之后。 代碼生成算法（ 3） ?代碼生成時必須更新寄存器和地址描述符 ?處理普通指令時生成 LD R x ? R的寄存器描述符：只包含 x（ 因為 R被修改了 ） ? x的地址描述符： R作為 x的新位置，加入到 x的位置集合中 ? 從任何不同于 x的變量的地址描述符中刪除 R，（因為 R中僅有 x了） ?ST x, R ? 修改 x的地址描述符，包含自己的內(nèi)存位置 代碼生成算法（ 4） ?ADD Rx, Ry, Rz ? Rx的寄存器描述符只包含 x ? X的地址描述符只包含 Rx（不包含 x的內(nèi)存位置！，因為最新的 x值只這有） ? 從任何不同于 x的變量的地址描述符中刪除 Rx。得分最低則找到了最合適的R getReg函數(shù)的設(shè)計（ 3） ?為 x選擇寄存器 Rx的方法類似 y，但 ? 如有一個只存了 x值的寄存器，則可選該寄存器 ? 若 y在指令 I之后不再使用，且 Ry僅僅保存了 y的值，則 Ry同時也可作為 Rx； ?處理 x=y時，總讓 Rx=Ry。 L1: goto L2 替換為： goto L2。 ?缺點：寄存器的使用效率較低
研究報告相關(guān)推薦
鄂ICP備17016276號-1