Instruction SelectionBack EndTargetLexer ParserSourceStream ofTokensAbstractSyntax Tree SemanticAnalysisIR Trees Canon-icalizerIR Trees InstructionSelectionAssemblyPseudo-Instruction Selection• Process of finding set of machine instructions that implement operations specifiedin IR tree.• Each machine instruction can be specified as an IR tree fragment → tree pattern• Goal of instruction selection is to cover IR tree with non-overlapping tree patterns.Computer Science 320Prof. David August-1-The Jouette Architecture• Load/Store architecture• Relatively large, general purpose register file– Data or addresses can reside in registers (unlike Motorola 68000)– Each instruction can access any register (unlike x86)• r0always contains zero.• Each instruction has latency of one cycle.• Execution of only one instruction per cycle.Computer Science 320Prof. David August-2-The Jouette ArchitectureArithmetic:ADD rd= rs1+ rs2ADDI rd= rs+ cSUB rd= rs1− rs2SUBI rd= rs− cMUL rd= rs1∗ rs2DIV rd= rs1/rs2Memory:LOAD rd= M[rs+ c]STORE M[rs1+ c]=rs2MOVEM M[rs1]=M[rs2]Computer Science 320Prof. David August-3-Pseudo-opsPseudo-op - An assembly operation which does not have a corresponding machine codeoperation. Pseudo-ops are resolved during assembly.MOV rd= rsADDI rd= rs+0MOV rd= rsADD rd= rs1+ r0MOVI rd= c ADDI rd= r0+ c(Pseudo-op can also mean assembly directive, such as .align.)Computer Science 320Prof. David August-4-Instruction Tree PatternsName Effect Trees— ri.TEMPADD ri rj+ rk.+MUL ri rj× rk.*SUB ri rjrk.-DIV ri rj/rk./ADDI ri rj+ c.+CONST.+CONST.CONSTSUBI ri rjc.-CONSTLOAD ri M[rj+ c].MEM+CONST.MEM+CONST.MEMCONST.MEM. . . .Computer Science 320Prof. David August-5-Instruction Tree PatternsSTORE M[rj+ c] ri.MOVEMEM+CONST.MOVEMEM+CONST.MOVEMEMCONST.MOVEMEMMOVEM M[rj] M[ri].MOVEMEM MEMComputer Science 320Prof. David August-6-Examplea[i] := x assuming i in register, a and x in stack frame.MOVEMEM MEMPLUS PLUSCONSToffset-xTEMPFPMEM MULTCONSTTEMPtemp-i 4PLUSoffset-aCONSTTEMPFPComputer Science 320Prof. David August-7-Individual Node SelectionMOVEMEM MEMPLUS PLUSCONSToffset-xTEMPFPMEM MULTCONSTTEMPtemp-i 4PLUSoffset-aCONSTTEMPFPComputer Science 320Prof. David August-8-Individual Node SelectionADDI r1 = r0 + offset_aADD r2 = r1 + FPLOAD r3 = M[r2 + 0]ADDI r4 = r0 + 4MUL r5 = r4 * r_iADD r6 = r3 + r5ADDI r7 = r0 + offset_xADD r8 = r7 + FPLOAD r9 = M[r8 + 0]STORE M[r6 + 0] = r99 registers, 10 instructionsComputer Science 320Prof. David August-9-Random TilingMOVEMEM MEMPLUS PLUSCONSToffset-xTEMPFPMEM MULTCONSTTEMPtemp-i 4PLUSoffset-aCONSTTEMPFPComputer Science 320Prof. David August-10-Random TilingADDI r1 = r0 + offset_aADD r2 = r1 + FPLOAD r3 = M[r2 + 0]ADDI r4 = r0 + 4MUL r5 = r4 * r_iADD r6 = r3 + r5ADDI r7 = r0 + offset_xADD r8 = r7 + FPMOVEM M[r6] = M[r8]Saves a register (9 → 8) and an instruction (10 → 9).Computer Science 320Prof. David August-11-Node Selection• There exist many possible tilings - want tiling/covering that results in instructionsequence of least cost– Sequence of instructions that takes least amount of time to execute.– For single issue fixed-latency machine: fewest number of instructions.• Suppose each instruction has fixed cost:– Optimum Tiling: tiles sum to lowest possible value - globally “the best”– Optimal Tiling: no two adjacent tiles can be combined into a single tile of lowercost - locally “the best”– Optimal instruction selection easier to implement than Optimum instruction se-lection.– Optimal is roughly equivalent to Optimum for RISC machines.– Optimal and Optimum are noticeably different for CISC machines.• Instructions are not self-contained with individual costs.Computer Science 320Prof. David August-12-Optimal Instruction Selection - Maximal Munch• Cover root node of IR tree with largest tile t that fits (most nodes)– Tiles of equivalent size ⇒ arbitrarily choose one.• Repeat for each subtree at leaves of t.• Generate assembly instructions in reverse order - instruction for tile at root emittedlast.Computer Science 320Prof. David August-13-Maximal MunchMOVEMEM MEMPLUS PLUSCONSToffset-xTEMPFPMEM MULTCONSTTEMPtemp-i 4PLUSoffset-aCONSTTEMPFPComputer Science 320Prof. David August-14-Maximal MunchLOAD r3 = M[FP + offset_a]ADDI r4 = r0 + 4MUL r5 = r4 * r_iADD r6 = r3 + r5ADD r8 = FP + offset_xMOVEM M[r6] = M[r8]5 registers, 6 instructionsComputer Science 320Prof. David August-15-Maximal MunchMaximum Munch very easy to write in ML - use pattern-matching capability• Two recursive functions: munchStm, munchExp• Each clause in these functions matches pattern/tile• Clauses ordered in order of decreasing tile size• ML pattern matching chooses first rule that matchesComputer Science 320Prof. David August-16-Assembly Representationstructure Assem = structtype reg = stringtype temp = Temp.temptype label = Temp.labeldatatype instr = OPER of{assem: string,dst: temp list,src: temp list,jump: label list option}| ......endComputer Science 320Prof. David August-17-Codegenfun codegen(frame)(stm: Tree.stm):Assem.instr list =letval ilist = ref(nil: Assem.instr list)fun emit(x) = ilist := x::!ilistfun munchStm: Tree.stm -> unitfun munchExp: Tree.exp -> Temp.tempinmunchStm(stm);rev(!ilist)endComputer Science 320Prof. David August-18-Statement Munchfun munchStm(T.MOVE(T.MEM(T.BINOP(T.PLUS, e1, T.CONST(c))), e2))=emit(Assem.OPER{assem="STORE M[’s0 + " ˆint(c) ˆ "] = ’s1\n",src=[munchExp(e1), munchExp(e2)],dst=[],jump=NONE})| munchStm(T.MOVE(T.MEM(e1), T.MEM(e2))) =emit(Assem.OPER{assem="MOVEM M[’s0] = M[’s1]\n"src=[munchExp(e1), munchExp(e2)],dst=[],jump=NONE})Computer Science 320Prof. David August-19-Statement Munch| munchStm(T.MOVE(T.MEM(e1), e2)) =emit(Assem.OPER{assem="STORE M[’s0] = ’s1\n"src=[munchExp(e1), munchExp(e2)],dst=[],jump=NONE})...Computer Science 320Prof. David August-20-Expression Munchand munchExp(T.MEM(T.BINOP(T.PLUS, e1, T.CONST(c)))) =letval t = Temp.newtemp()inemit(Assem.OPER{assem="LOAD ’d0 = M[’s0 +" ˆint(c) ˆ "]\n",src=[munchExp(e1)],dst=[t],jump=NONE});tendComputer Science 320Prof. David August-21-Expression Munch| munchExp(T.BINOP(T.PLUS, e1, T.CONST(c))) =letval t = Temp.newtemp()inemit(Assem.OPER{assem="ADDI ’d0 = ’s0 +" ˆint(c) ˆ "\n",src=[munchExp(e1)],dst=[t],jump=NONE});tend...| munchExp(T.TEMP(t)) = tComputer Science 320Prof. David August-22-Optimum Instruction Selection• Find optimum solution for problem (tiling of IR tree) based on optimum