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