【文章內(nèi)容簡介】 ryExit3完成。 規(guī)范化從已經(jīng)得到的IR 樹出發(fā)，規(guī)范化過程將幫助完成下面的工作:A．IR 樹被寫成一個沒有SEQ和ESEQ 結(jié)點的規(guī)范樹表B．根據(jù)該表劃分基本塊，每個基本塊中不包含內(nèi)部跳轉(zhuǎn)和標(biāo)號C．基本塊被順序放置，所有的CJUMP 都跟有false標(biāo)號由于這部分的代碼在實現(xiàn)框架中已經(jīng)提供所以我們不需要知道任何細(xì)節(jié)，只需將提供的Canon 文件夾復(fù)制,對于以上三步,只需在最后裝配時調(diào)用下面的接口就可以了。 ( s). BasicBlocks( stms)(BasicBlocks b)6. 匯編指令選擇6 常用MIPS匯編指令sw reg, addr 將寄存器reg保存到內(nèi)存地址addr中l(wèi)w reg, addr 將內(nèi)存地址addr中的內(nèi)容保存到寄存器reg中l(wèi)i reg, imm 將立即值imm保存到寄存器reg中l(wèi)a reg, addr 將地址addr (而不是其中的內(nèi)容) 保存到寄存器reg 中move reg1, reg2將寄存器reg2 移動到寄存器reg1中jal label 無條件轉(zhuǎn)移到label, 返回地址 (下一指令) 存于$Ra寄存器jr reg 無條件轉(zhuǎn)移到reg中所保存的地址, 返回地址存于$Rasubu reg1,reg2,CONST 將reg2 的值減去CONST后放入reg1addu reg1,reg2,CONST 將reg2 的值加上CONST后放入reg1beq reg, src, label 當(dāng)reg=src時跳轉(zhuǎn)到labelbge reg, src, label 當(dāng)reg=src時跳轉(zhuǎn)到labelbgt reg, src, label 當(dāng)regsrc時跳轉(zhuǎn)到labelble reg, src, label 當(dāng)reg=src時跳轉(zhuǎn)到labelblt reg, src, label 當(dāng)regsrc時跳轉(zhuǎn)到labelbne reg, src, label 當(dāng)reg!=src時跳轉(zhuǎn)到labeladd reg1, reg2, src 將reg2+src送到reg1sub reg1, reg2, src 將reg2src送到reg1mul reg1, reg2, src 將reg2*src送到reg1div reg1, reg2, src 將reg2/src送到reg1 MIPS中的寄存器REGISTERNAMEUSAGE$0 $zero常量0(constant value 0)$1 $at保留給匯編器(Reserved for assembler)$2$3$v0$v1函數(shù)調(diào)用返回值(values for results and expression evaluation)$4$7$a0$a3函數(shù)調(diào)用參數(shù)(arguments)$8$15$t0$t7暫時的(或隨便用的)$16$23$s0$s7保存的(或如果用，需要SAVE/RESTORE的)(saved)$24$25$t8$t9暫時的(或隨便用的)$28 $gp全局指針(Global Pointer)$29 $sp堆棧指針(Stack Pointer)$30 $fp幀指針(Frame Pointer)$31 $ra返回地址(return address) MIPS匯編語言語法注釋: 以 號開始指令: 見本章第一節(jié)標(biāo)識符: 以字母,下劃線,點號,數(shù)字序列(不以數(shù)字開頭)標(biāo)號 :標(biāo)識符后加冒號例如:.dataitem: .word 1.text.globl main Must be globalmain: lw $t0, item數(shù)值可以為十進(jìn)制或十六進(jìn)制，例如255或0xff字符串用引號括起來，可以使用如下轉(zhuǎn)義字符:\n (換行) \t (tab) \”(引號)還有如下會用到的匯編指令:.globl symbol 聲明symbol是全局的，main函數(shù)必須是全局的(globl main).text 聲明指令區(qū):后面跟上連續(xù)的匯編指令.data 聲明數(shù)據(jù)區(qū):后面跟上連續(xù)的數(shù)據(jù).word w1,w2… 在數(shù)據(jù)區(qū)中存儲連續(xù)的32位整數(shù).asciiz str 在數(shù)據(jù)區(qū)中存儲字符串，并用null結(jié)尾 Assem包Instr類用來表示一條匯編語言指令。它有三個派生類OPER,LABEL和MOVE。OPER類中包含匯編語言指令assem，一個操作數(shù)寄存器列表src 和一系列的結(jié)果寄存器dst，這些寄存器列表都可以是空的。方法OPER(assem, dst, src)將構(gòu)造跳轉(zhuǎn)至下一條指令的操作，并且jumps()方法的返回值為null；OPER(assem, dst, src, jump) 還擁有目標(biāo)標(biāo)記列表并通過查找這個列表進(jìn)行跳轉(zhuǎn)。LABEL表示程序?qū)⒁D(zhuǎn)的地點。其中包括一個assem，指明在匯編語言中如何找到標(biāo)號，有一個label參數(shù)，用于確定使用哪個標(biāo)號符號。MOVE與OPER 很接近，但MOVE必須進(jìn)行數(shù)據(jù)轉(zhuǎn)換。如果dst和src被分配給了同一個寄存器，MOVE指令將被刪除。(m) 將匯編指令轉(zhuǎn)化成為字符串形式。m 是一個實現(xiàn)TempMap 接口的對象,在TempMap 接口中，存在一個方法可以為每個臨時變量分配一個寄存器或者為不同的變量分配相同的寄存器 (給出名字) 。Instr是與特定的機(jī)器無關(guān)的。 Assem包類圖 生成匯編指令，輸入中間表示樹節(jié)點，將生成Instr類對象將其加入到InstrList對象成員instrList中(調(diào)用emit)。::munchStm(MOVE s)為例，展示生成匯編指令的一半方法。以MOVE為樹根時總共有六種可能情況需要分別處理。圖 MOVE為根時的六種可能情形其中d標(biāo)記數(shù)據(jù)寄存器，a標(biāo)記地址寄存器。這六種情況的處理方式分別如下：情況1:sw d, CONST (a) //CONST 為常數(shù)偏移量, a 為內(nèi)存地址,下同情況2:sw d, CONST (a)情況3:sw d, CONST情況4:sw d, CONST情況5:li d, CONST //CONST 寫入寄存器 d情況6:move d1, d2 //d2 寫入寄存器 d1 public void munchStm(MOVE s) { Expr dst = 。 Expr src = 。 if (dst instanceof MEM) { MEM dst1 = (MEM) dst。 if (() amp。amp。 ((BINOP) ).binop == amp。amp。 (((BINOP) ).right)) { Temp t1 = munchExp(src)。 Temp t2 = munchExp(((BINOP) ).left)。 emit(new OPER(sw `s0, + ((CONST) ((BINOP) ).right).value + (`s1), null, new TempList(t1, new TempList(t2, null))))。 } else if (() amp。amp。 ((BINOP) ).binop == amp。amp。 (((BINOP) ).left)) { Temp t1 = munchExp(src)。 Temp t2 = munchExp(((BINOP) ).right)。 emit(new OPER(sw `s0, + ((CONST) ((BINOP) ).left).value + (`s1), null, new TempList(t1, new TempList(t2, null))))。 } else if (()) { Temp t1 = munchExp(src)。 emit(new OPER(sw `s0, + ((CONST) ).value, null, new TempList(t1, null)))。 } else { Temp t1 = munchExp(src)。 Temp t2 = munchExp()。 emit(new OPER(sw `s0, (`s1), null, new TempList(t1, new TempList(t2, null))))。 } } else if ((dst)) if ((src)) { emit(new OPER(li `d0, + ((CONST) src).value, new TempList( ((TEMP) dst).temp, null), null))。 } else { Temp t1 = munchExp(src)。 emit(new OPER(move `d0, `s0, new TempList(((TEMP) dst).temp, null), new TempList(t1, null)))。 } }其他匯編指令生成方式詳見工程代碼。7. 寄存器分配這個模塊可以說是整個工程的難點，因為涉及到一系列的算法。大致的步驟為：根據(jù)匯編指令生成流圖 活性分析 生成干擾圖 – 根據(jù)干擾圖分配寄存器(著色算法)7 流圖的生成，在這個類中每個結(jié)點代表一個匯編指令，邊為可能的控制轉(zhuǎn)移。該類還提供了一個構(gòu)造函數(shù)，可以輸入InstrList對象來生成流圖。 public AssemFlowGraph(InstrList instrs) { represent = new HashtableNode, Instr()。 DictionaryLabel, Node labels = new HashtableLabel, Node()。 for (InstrList i = instrs。 i != null。 i = ) { Node node = newNode()。 (node, )。 if ( instanceof LABEL) (((LABEL) ).label, node)。 } for (NodeList node = nodes()。 node != null。 node = ) { Targets next = instr().jumps()。 if (next == null) { if ( != null) addEdge(, )。 } else for (LabelList l = 。 l != null。 l = ) addEdge(, (Node) ())。 } } 活性分析對于流圖中的每個結(jié)點,用下面的結(jié)構(gòu)RegAlloc::NodeInfo來描述它的結(jié)點信息:class NodeInfo { NodeInfo(TempList u, TempList d) { for (TempList t = u。 t != null。 t = ) ()。 for (TempList t = d。 t != null。 t = ) ()。 } SetTemp in = new HashSetTemp()。 SetTemp out = new HashSetTemp()。 SetTemp use = new HashSetTemp()。 SetTemp def = new HashSetTemp()。}活性分析，就是求出每個結(jié)點的out變量，即活躍變量。首先，對每個結(jié)點的use和def初始化，這在flowgraph中已經(jīng)提供，并且置in和out為空，，直到in和out不變?yōu)橹?。最后將生成的活躍變量記錄到活躍變量表中。. calculateLiveness中實現(xiàn)。void calculateLiveness() { boolean done = false。 do { done = true。 for (NodeList node = ()。 node != null。 node = ) { NodeInfo inf = (NodeInfo) ()。 SetTemp in1 = new HashSetTemp()。 ()。 ()。 if (!()) done = false。 = in1。 SetTemp out1 = new HashSetTemp()。 for (NodeList succ = ()。 succ != null。 succ = ) { NodeInfo i = (NodeInfo) ()。 ()。 } if (!()) done = false。 = out1。 } } while (!done)。 for (NodeList node = ()。 node != null。 node = ) { TempList list = null。 IteratorTemp i = ((NodeInfo)