Topic 6 Basic BackBack End Optimization Instruction Selection Instruction scheduling Register allocation 2008 4 8 course cpeg421 08s Topic 6 ppt 1 ABET Outcome Ability to apply knowledge of basic code generation techniques e g Instruction selection instruction scheduling register allocation to solve code generation problems Ability to analyze the basic algorithms on the above techniques and conduct experiments to show their effectiveness Ability to use a modern compiler development platform and tools for the practice of above A Knowledge on contemporary issues on this topic 2008 4 8 course cpeg421 08s Topic 6 ppt 2 Three Basic Back End Optimization Instruction selection Mapping IR into assembly code Assumes a fixed storage mapping code shape Combining operations using address modes Instruction scheduling Reordering operations to hide latencies Assumes a fixed program set of operations Changes demand for registers Register allocation Deciding which values will reside in registers Changes the storage mapping may add false sharing Concerns about placement of data memory operations 2008 4 8 course cpeg421 08s Topic 6 ppt 3 Instruction Selection Some slides are from CS 640 lecture in George Mason University 2008 4 8 course cpeg421 08s Topic 6 ppt 4 Reading List 1 K D Cooper L Torczon Engineering a Compiler Chapter 11 2 Dragon Book Chapter 8 7 8 9 Some slides are from CS 640 lecture in George Mason University 2008 4 8 course cpeg421 08s Topic 6 ppt 5 Objectives Introduce the complexity and importance of instruction selection Study practical issues and solutions Case study Instruction Selectation in Open64 2008 4 8 course cpeg421 08s Topic 6 ppt 6 Instruction Selection Retargetable Front End Middle End Back End Infrastructure Machine description Back end Generator Tables Pattern Matching Engine 2008 4 8 course cpeg421 08s Topic 6 ppt Descriptionbased retargeting 7 Complexity of Instruction Selection Modern computers have many ways to do anything Consider a register to register copy Obvious operation is move rj ri Many others exist 2008 4 8 add rj ri 0 sub rj ri 0 rshiftI rj ri 0 mul rj ri 1 or rj ri 0 xor rj ri 0 others divI rj r 1 course cpeg421 08s Topic 6 ppt 8 Complexity of Instruction Selection Cont Multiple addressing modes Each alternate sequence has its cost Complex ops mult div several cycles Memory ops latency vary Sometimes cost is context related Use under utilized FUs Dependent on objectives speed power code size 2008 4 8 course cpeg421 08s Topic 6 ppt 9 Complexity of Instruction Selection Cont Additional constraints on specific operations Load store multiple words contiguous registers Multiply need special register Accumulator Interaction between instruction selection instruction scheduling and register allocation For scheduling instruction selection predetermines latencies and function units For register allocation instruction selection pre colors some variables e g non uniform registers such as registers for multiplication 2008 4 8 course cpeg421 08s Topic 6 ppt 10 Instruction Selection Techniques Tree Pattern Matching Tree oriented IR suggests pattern matching on trees Tree patterns as input matcher as output Each pattern maps to a target machine instruction sequence Use dynamic programming or bottom up rewrite systems Peephole based Matching Linear IR suggests using some sort of string matching Inspired by peephole optimization Strings as input matcher as output Each string maps to a target machine instruction sequence In practice both work well matchers are quite different 2008 4 8 course cpeg421 08s Topic 6 ppt 11 A Simple Tree Walk Code Generation Method Assume starting with a Tree like IR Starting from the root recursively walking through the tree At each node use a simple unique rule to generate a low level instruction 2008 4 8 course cpeg421 08s Topic 6 ppt 12 Tree Pattern Matching Assumptions tree like IR an AST Assume each subtree of IR there is a corresponding set of tree patterns or operation trees low level abstract syntax tree Problem formulation Find a best mapping of the AST to operations by tiling the AST with operation trees where tiling is a collection of AST node operation tree pairs 2008 4 8 course cpeg421 08s Topic 6 ppt 13 Tile AST An AST tree Tile 6 gets val Tile 5 ref num Tile 1 ref num Tile 4 ref val num lab Tile 3 num Tile 2 2008 4 8 course cpeg421 08s Topic 6 ppt 14 Tile AST with Operation Trees Goal is to tile AST with operation trees A tiling is collection of ast node op tree pairs ast node is a node in the AST op tree is an operation tree ast node op tree means that op tree could implement the subtree at ast node A tiling implements an AST if it covers every node in the AST and the overlap between any two trees is limited to a single node ast node op tree tiling means ast node is also covered by a leaf in another operation tree in the tiling unless it is the root Where two operation trees meet they must be compatible expect the value in the same location 2008 4 8 course cpeg421 08s Topic 6 ppt 15 Tree Walk by Tiling An Example a a 22 MOVE SP a MEM 22 SP 2008 4 8 a course cpeg421 08s Topic 6 ppt 16 Example a a 22 t4 MOVE t3 SP a t2 t1 MEM 22 SP 2008 4 8 a course cpeg421 08s Topic 6 ppt ld t1 sp a add t2 t1 22 add t3 sp a st t3 t2 17 Example An Alternative a a 22 t3 MOVE t2 t1 SP a MEM 22 ld t1 sp a add t2 t1 22 st sp a t2 SP 2008 4 8 a course cpeg421 08s Topic 6 ppt 18 Finding Matches to Tile the Tree Compiler writer connects operation trees to AST subtrees Provides a set of rewrite rules Encode tree syntax in linear form Associated with each is a code template 2008 4 8 course cpeg421 08s Topic 6 ppt 19 Generating Code in Tilings Given a tiled tree Postorder treewalk with node dependent order for children Do right child before its left child Emit code sequence for tiles in order Tie boundaries together with register names Can incorporate a real register allocator or can simply use NextRegister approach 2008 4 8 course cpeg421 08s Topic 6 ppt 20 Optimal Tilings Best tiling corresponds to least cost instruction sequence Optimal tiling no two adjacent tiles can be combined to a tile of lower cost 2008 4 8 course cpeg421 08s Topic 6 ppt 21 Dynamic Programming for Optimal Tiling For a node x let f x be the cost of the optimal tiling for the whole expression tree rooted at x Then f x min cost T tile T covering x 2008 4 8 course cpeg421 08s Topic 6 ppt f y child y of tile T 22 Dynamic Programming for Optimal Tiling Con t Maintain a table node x