編譯原理之代碼生成(存儲版)
【正文】 ：每個(gè)語句 i中變量的活躍性、下次使用信息 ?方法： ? 所有的非臨時(shí)變量初始化為活躍的，從 B的最后一個(gè)語句開始 反向掃描 , ? 對于每個(gè)語句 i： x=y+z。 尋址模式 ?變量 x：指向分配 x的內(nèi)存位置 ?a(r)：地址是 a的左值加上 r中的值 （可類比一維數(shù)組方便記憶） ?constant(r)：寄存器中內(nèi)容加上前面的常數(shù)即其地址； （可類比一維數(shù)組方便記憶） ?*r：寄存器 r的內(nèi)容為其地址 ?*constant(r)： r中內(nèi)容加上常量的和所指地址中存放的值為其地址 （可類比一維數(shù)組方便記憶） ?常量 constant56 例子 ?x=yz ? LD R1, y //R1=y ? LD R2, z //R2=x ? SUB R1, R1, R2 //R1=R1R2 ? ST x, R1 //x=R1 ?b=a[i] ? LR R1, i //R1=i ? MUL R1, R1, 8 //R1=R1*8 ? LD R2, a(R1) //R2=contents(a+contents(R1)) ? ST b, R2 //b = R2 程序及指令代價(jià) ?不同的目的有不同的度量 ? 最短編譯時(shí)間、目標(biāo)程序大小、運(yùn)行時(shí)間、能耗 ?不可判定一個(gè)目標(biāo)程序是否最優(yōu) ?指令代價(jià)＝指令固定代價(jià) (設(shè)為 1)＋運(yùn)算分量尋址模式代價(jià)，例： ? LD R0, R1；代價(jià)為 1 ? LD R0, M；代價(jià)是 2 ? LD R1, *100(R2)；代價(jià)為 2 常數(shù)和內(nèi)存地址增加代價(jià) 1， 寄存器增加代價(jià)為 0。 ? 無條件跳轉(zhuǎn) ? BR L；控制流轉(zhuǎn)向標(biāo)號 L的指令 ? 條件跳轉(zhuǎn) ? Bcond r, L；對 r中的值進(jìn)行測試，如果為真則轉(zhuǎn)向 L。 ? 簡單的說， Q活躍就是指 Q定義的值被使用過。 ? 如果存在，則不需要生成新的結(jié)點(diǎn)，用 N代表 M； ? 例如： ? a=b+c ? b=ad ? c=b+c ? d=ad ? 找出公共的表達(dá)式？ ? 注意：兩個(gè) b+c實(shí)際上并不是公共子表達(dá)式 消除死代碼 ?在 DAG圖上消除沒有附加活躍變量的根結(jié)點(diǎn)（沒有父結(jié)點(diǎn)的結(jié)點(diǎn)），即可消除死代碼 ?如果圖中 c、 e不是活躍變量，則可以刪除標(biāo)號為 e、 c的結(jié)點(diǎn)。殺誰？ ? 全殺 !! 從 DAG到基本塊 ?重構(gòu)的方法 ? 對每個(gè)結(jié)點(diǎn)構(gòu)造一個(gè)三地址語句來計(jì)算對應(yīng)的值 ? 結(jié)果應(yīng)該盡量賦給一個(gè)活躍的變量 ?一般為出口活躍，如果不確定則假設(shè)所有非臨時(shí)變量都出口活躍 ? 如果結(jié)點(diǎn)有多個(gè)關(guān)聯(lián)的變量，則需要用復(fù)制語句進(jìn)行賦值。 例 （ 1） ?已知： ? a、 b、 c、 d在出口處活躍 ? t、 u、 v是局部臨時(shí)變量 ?將基本塊翻譯成代碼 ,只有三個(gè)寄存器 t = a b u = a – c v = t + u a = d d = v + u 例 （ 2） 寄存器描述符 地址描述符 圖 816 生成的指令及寄存器和地址描述符的改變過程 初始 例 （ 3） 寄存器描述符 地址描述符 圖 816 生成的指令及寄存器和地址描述符的改變過程 getReg函數(shù)的設(shè)計(jì)（ 1） ?目標(biāo)：減少 LD/ST指令 ?任務(wù)：為運(yùn)算分量和結(jié)果分配寄存器 ? 例： x＝ y+z ?為運(yùn)算分量 y分配寄存器 ? 若 y已在某個(gè)寄存器中，不需處理 ? 若 y不在寄存器中，且有空閑寄存器，選擇這個(gè)寄存器 ? 若 y不在寄存器中，且沒有空閑寄存器（見下頁） getReg函數(shù)的設(shè)計(jì)（ 2） ?為運(yùn)算分量 y分配寄存器 ? … 如果不在寄存器中，且沒有空閑寄存器，則尋找一個(gè)可使用的寄存器 R ? 設(shè) R的寄存器描述符表示變量 v在 R中，若 V滿足以下三種情況之一，則可以選擇寄存器 R分配給 y： ? v還有其他存儲位置 ? v就是 x，且 x不是運(yùn)算分量之一 (怕 v被修改 ) ? V此后不再被使用 ? 如果前面三條不滿足。 L1: goto L2 若沒有跳轉(zhuǎn)到 L1的指令，且指令 L1: goto L2之前是一個(gè)無條件跳轉(zhuǎn)指令，則 L1該行指令可刪除?？梢詣h除第二條指令 消除不可達(dá)指令 ?緊跟在無條件轉(zhuǎn)移指令后不帶標(biāo)號的指令 ? 重復(fù)這個(gè)操作，可刪除一個(gè)指令序列 ?級聯(lián)跳轉(zhuǎn)代碼 ? 比如示例：調(diào)試代碼（當(dāng) debug＝ 1時(shí)才運(yùn)行的程序片斷）的原始中間代碼可能如下： ?if debug==1 goto L1 ?goto L2
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1