編譯原理之代碼生成(參考版)
2025-05-17 04:33本頁面
【正文】 控制流優(yōu)化 ?if ab goto L1 … … L1: goto L2 替換為： if ab goto L2 … … L1: goto L2 代數(shù)化簡 /強度消減 ?應(yīng)用代數(shù)恒等式進(jìn)行優(yōu)化 ?消除 x=x+0 x=x*1 ?x*x替換 x2 ?使用機(jī)器特有指令 ? INC， DEC， … 寄存器分配和指派 ?目的：有效利用寄存器； ?簡單的基本方法：把特定類型的值分配給特定的寄存器 ? 數(shù)組基地址指派給一組寄存器 ? 算術(shù)計算分配給一組寄存器 ? 棧頂指針分配一個寄存器 ? 。 … … 。 … … 。 窺孔優(yōu)化 ?使用一個滑動窗口（窺孔）來檢查目標(biāo)指令，在窺孔內(nèi)實現(xiàn)優(yōu)化 ? 冗余指令消除 ? 控制流優(yōu)化 ? 代數(shù)簡化 ? 機(jī)器特有指令的使用 消除冗余指令 ?多余的 LD/ST指令 ? LD R0 a ? ST a R0 ? 且沒有指令跳到第二條指令處，即第二指令沒有標(biāo)號。則只好生成保存指令 ST v R；（溢出操作）修改 v的地址描述符； ? 若 R中存放了多個變量的值，則需要生成多個 ST指令； ? ST指令數(shù)目就是選擇 R的得分。 ?處理 x=y時，如果生成 LD Ry y ? LD按照第一個規(guī)則處理； ? 把 x加入到 Ry中； ** ? 修改 x的地址描述符，使它只包含 Ry。 ?數(shù)據(jù)結(jié)構(gòu)：記錄各個值對應(yīng)的位置 ? 寄存器描述符：跟蹤哪些變量的當(dāng)前值存放在寄存器內(nèi)；有 M個對應(yīng)于 M個寄存器 ? 地址描述符：在哪個或哪些位置上可以找到該變量的當(dāng)前值；有 N個對應(yīng)于 N個變量 代碼生成算法（ 1） ?重要子函數(shù)： getReg(I) ? 為三地址指令 I選擇寄存器； ? 根據(jù)寄存器描述符和地址描述符、以及數(shù)據(jù)流信息來分配最佳的寄存器； ? 得到的機(jī)器指令的質(zhì)量依賴于 getReg函數(shù)選取寄存器的算法； ?代碼生成算法逐個處理三地址指令 代碼生成算法（ 2） ?x=y+z ? 調(diào)用 getReg(x=y+z)，為 x,y,z選擇寄存器 Rx,Ry,Rz ? 查 Ry的寄存器描述符，如果 y不在 Ry中則生成指令：LD Ry y’ (y’是存放 y的內(nèi)存位置之一 ) ? 類似地，確定是否生成 LD Rz,z’ ? 生成指令 ADD Rx, Ry, Rz ?復(fù)制語句： x=y ? getReg(x=y)總是為 x和 y選擇相同的寄存器 ? 如果 y不在 Ry中，生成機(jī)器指令 LD Ry, y ?基本塊的收尾 ? 如果變量 x在出口處活躍，且 x現(xiàn)在不在內(nèi)存，那么生成指令 ST x, Rx。 ?總的來說，必須保證：如果兩個指令之間可能相互影響，那么它們的順序就不應(yīng)該改變。 重組基本塊的例子 ?原三地址碼 ?a=b+c ?b=ad ?c=b+c ?d=ad ?根據(jù) DAG構(gòu)造是結(jié)點產(chǎn)生的順序 ?a=b+c ?d=ad ?b=d ?c=d+c 重組的規(guī)則 ?重組時應(yīng)該注意求值的順序 ? 指令的順序必須遵守 DAG中結(jié)點的順序 ? 對數(shù)組的賦值必須跟在所有原來在它之前的賦值 / 求值操作之后。x ? *p=y可以只殺死那些以 x為附加變量的結(jié)點 ?過程調(diào)用也類似，為了安全： ? 必須假設(shè)它使用了訪問范圍內(nèi)所有變量 ? 假設(shè)修改了訪問范圍內(nèi)的所有變量 。最粗略地估計： ? x使用了任意變量，因此無法消除死代碼 ? 而 *q=y對任意變量賦值，因此殺死了全部其他結(jié)點(可類似引出新的運算符 “ =*”與 “ *=”幫助分析 ) ?殺的范圍過大。 x ? 如果沒有殺手的出現(xiàn)則被殺者本可以象前述一樣進(jìn)行優(yōu)化。 DAG方法的不足 為了計算第四式的 e值，而有的 2,3式實際上是冗余的，也就是第一式和第四式等價。 ?可以 DAG為基礎(chǔ)，對代碼進(jìn)行轉(zhuǎn)換 ? 消除局部公共子表達(dá)式 ? 消除死代碼 ? 對語句重新排序 ? 重新排序運算分量的順序 局部公共子表達(dá)式 ? 局部公共子表達(dá)式的發(fā)現(xiàn) ? 建立某個結(jié)點 M之前，首先檢查是否存在一個結(jié)點 N，它和 M具有相同的運算符和子結(jié)點（順序相同）。 循環(huán)的例子 ?循環(huán) ? {B3} ? {B6} ? {B2,B3,B4} 基本塊的幾種優(yōu)化 ? 一個基本塊可用一個 DAG圖表示 (基本的 DAG圖 ) ? 每個變量對應(yīng)于一個結(jié)點，表示初始值 ? 每條語句 s有一個相關(guān)結(jié)點 N,具有 ? 子結(jié)點：對應(yīng)于其它語句 ,是在 s之前
研究報告相關(guān)推薦
鄂ICP備17016276號-1