編譯原理之代碼生成-全文預(yù)覽
【正文】 址碼 ?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ù)組的賦值必須跟在所有原來在它之前的賦值 / 求值操作之后。 ?數(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ù)流信息來分配最佳的寄存器； ? 得到的機器指令的質(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中，生成機器指令 LD Ry, y ?基本塊的收尾 ? 如果變量 x在出口處活躍，且 x現(xiàn)在不在內(nèi)存，那么生成指令 ST x, Rx。則只好生成保存指令 ST v R；（溢出操作）修改 v的地址描述符； ? 若 R中存放了多個變量的值，則需要生成多個 ST指令； ? ST指令數(shù)目就是選擇 R的得分。 … … 。 控制流優(yōu)化 ?if ab goto L1 … … L1: goto L2 替換為： if ab goto L2 … … L1: goto L2 代數(shù)化簡 /強度消減 ?應(yīng)用代數(shù)恒等式進行優(yōu)化 ?消除 x=x+0 x=x*1 ?x*x替換 x2 ?使用機器特有指令 ? INC， DEC， … 寄存器分配和指派 ?目的：有效利用寄存器； ?簡單的基本方法：把特定類型的值分配給特定的寄存器 ? 數(shù)組基地址指派給一組寄存器 ? 算術(shù)計算分配給一組寄存器 ? 棧頂指針分配一個寄存器 ? 。 … … 。 窺孔優(yōu)化 ?使用一個滑動窗口（窺孔）來檢查目標(biāo)指令，在窺孔內(nèi)實現(xiàn)優(yōu)化 ? 冗余指令消除 ? 控制流優(yōu)化 ? 代數(shù)簡化 ? 機器特有指令的使用 消除冗余指令 ?多余的 LD/ST指令 ? LD R0 a ? ST a R0 ? 且沒有指令跳到第二條指令處，即第二指令沒有標(biāo)號。 ?處理 x=y時，如果生成 LD Ry y ? LD按照第一個規(guī)則處理； ? 把 x加入到 Ry中； ** ? 修改 x的地址描述符，使它只包含 Ry。 ?總的來說，必須保證：如果兩個指令之間可能相互影響，那么它們的順序就不應(yīng)該改變。x ? *p=y可以只殺死那些以 x為附加變量的結(jié)點 ?過程調(diào)用也類似，為了安全： ? 必須假設(shè)它使用了訪問范圍內(nèi)所有變量 ? 假設(shè)修改了訪問范圍內(nèi)的所有變量 。 x ? 如果沒有殺手的出現(xiàn)則被殺者本可以象前述一樣進行優(yōu)化。 ?可以 DAG為基礎(chǔ)，對代碼進行轉(zhuǎn)換 ? 消除局部公共子表達式 ? 消除死代碼 ? 對語句重新排序 ? 重新排序運算分量的順序 局部公共子表達式 ? 局部公共子表達式的發(fā)現(xiàn) ? 建立某個結(jié)點 M之前，首先檢查是否存在一個結(jié)點 N，它和 M具有相同的運算符和子結(jié)點（順序相同）。原因： ? B的結(jié)尾指令是一條跳轉(zhuǎn)到 C的開頭的條件 /無條件語句 ? 在原來的序列中， C緊跟在 B之后，且 B的結(jié)尾不是無條件跳轉(zhuǎn)語句 ? B是 C的 前驅(qū) ， C是 B的 后繼 ?流圖中增加額外的入口，出口結(jié)點各一個 ? 不對應(yīng)于實際的中間指令 （ 是增加 ） 。 活躍變量與非活躍變量 ?⒈ 變量的定值點和使用點： ? 設(shè)有四元式： q(w B C A ) ? B,C的使用點 (q) ? A的定值點 (q) ?⒉ 活躍變量與非活躍變量 ? 【 活躍變量 】 一個變量從某時刻 (q)起 ,到下一個定義點止，其間若有使用點，則稱該變量在 q是活躍的 (y),否則稱該變量在 q是非活躍的 (n)。 不同區(qū)域
研究報告相關(guān)推薦
鄂ICP備17016276號-1