Instruction Selection Source Lexer Back End Stream of Tokens Parser Abstract Syntax Tree Semantic Analysis IR Trees Canonicalizer IR Trees Instruction Selection PseudoAssembly Target Instruction Selection Process of finding set of machine instructions that implement operations specified in 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 320 Prof 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 r0 always contains zero Each instruction has latency of one cycle Execution of only one instruction per cycle Computer Science 320 Prof David August 2 The Jouette Architecture Arithmetic ADD ADDI SUB SUBI MUL DIV rd rd rd rd rd rd rs1 rs2 rs c rs1 rs2 rs c rs1 rs2 rs1 rs2 Memory LOAD STORE MOVEM Computer Science 320 Prof David August rd M rs c M rs1 c rs2 M rs1 M rs2 3 Pseudo ops Pseudo op An assembly operation which does not have a corresponding machine code operation Pseudo ops are resolved during assembly MOV MOV MOVI rd rs ADDI rd rs 0 rd rs ADD rd rs1 r0 rd c ADDI rd r0 c Pseudo op can also mean assembly directive such as align Computer Science 320 Prof David August 4 Instruction Tree Patterns Name Effect ri ADD ri r j rk MUL ri r j rk SUB ri rj DIV ri r j r k ADDI ri Trees TEMP rk ri rj CONST c CONST MEM LOAD ri CONST MEM CONST 5 CONST MEM M r j c Computer Science 320 Prof David August CONST rj c CONST SUBI MEM Instruction Tree Patterns MOVE STORE M r j c ri MOVE MEM MEM MEM CONST CONST CONST MOVE MOVEM Computer Science 320 Prof David August M r j M ri MOVE MEM MEM 6 MOVE MEM Example a i x assuming i in register a and x in stack frame MOVE MEM MEM PLUS PLUS MEM MULT PLUS TEMP CONST TEMP CONST temp i 4 FP offset a Computer Science 320 Prof David August 7 TEMP CONST FP offset x Individual Node Selection MOVE MEM MEM PLUS PLUS MEM MULT PLUS TEMP CONST TEMP CONST temp i 4 FP offset a Computer Science 320 Prof David August 8 TEMP CONST FP offset x Individual Node Selection ADDI ADD LOAD r1 r0 offset a r2 r1 FP r3 M r2 0 ADDI MUL r4 r0 4 r5 r4 r i ADD r6 r3 r5 ADDI ADD LOAD r7 r0 offset x r8 r7 FP r9 M r8 0 STORE M r6 0 r9 9 registers 10 instructions Computer Science 320 Prof David August 9 Random Tiling MOVE MEM MEM PLUS PLUS MEM MULT PLUS TEMP CONST TEMP CONST temp i 4 FP offset a Computer Science 320 Prof David August 10 TEMP CONST FP offset x Random Tiling ADDI ADD LOAD r1 r0 offset a r2 r1 FP r3 M r2 0 ADDI MUL r4 r0 4 r5 r4 r i ADD r6 r3 r5 ADDI r7 r0 offset x ADD r8 r7 FP MOVEM M r6 M r8 Saves a register 9 8 and an instruction 10 9 Computer Science 320 Prof David August 11 Node Selection There exist many possible tilings want tiling covering that results in instruction sequence 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 lower cost locally the best Optimal instruction selection easier to implement than Optimum instruction selection 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 320 Prof 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 emitted last Computer Science 320 Prof David August 13 Maximal Munch MOVE MEM MEM PLUS PLUS MEM MULT PLUS TEMP CONST TEMP CONST temp i 4 FP offset a Computer Science 320 Prof David August 14 TEMP CONST FP offset x Maximal Munch LOAD r3 M FP offset a ADDI MUL r4 r0 4 r5 r4 r i ADD r6 r3 r5 ADD r8 FP offset x MOVEM M r6 M r8 5 registers 6 instructions Computer Science 320 Prof David August 15 Maximal Munch Maximum 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 matches Computer Science 320 Prof David August 16 Assembly Representation structure Assem struct type reg string type temp Temp temp type label Temp label datatype instr OPER of assem string dst temp list src temp list jump label list option end Computer Science 320 Prof David August 17 Codegen fun codegen frame stm Tree stm Assem instr list let val ilist ref nil Assem instr list fun emit x ilist x ilist fun munchStm Tree stm unit fun munchExp Tree exp Temp temp in munchStm stm rev ilist end Computer Science 320 Prof David August 18 Statement Munch fun 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 320 Prof 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 320 Prof David August 20 Expression Munch and munchExp T MEM T BINOP T PLUS e1 T CONST c let val t Temp newtemp in emit Assem OPER assem LOAD d0 M s0 int c n src munchExp e1 dst t jump NONE t end Computer Science 320 Prof David August 21 Expression Munch munchExp T BINOP T PLUS e1 T CONST c let val t Temp newtemp in emit Assem OPER assem ADDI d0 s0 int c n src munchExp e1 dst t jump NONE t end munchExp T TEMP t t Computer Science 320 Prof David August 22 Optimum Instruction Selection Find optimum solution for problem tiling of IR tree based on optimum solutions for each subproblem tiling of subtrees Use Dynamic Programming to avoid unnecessary recomputation of subtree costs cost assigned to every node in IR tree Cost of best instruction sequence that can tile subtree rooted at node Algorithm …