Topic 6 Basic Back End Optimization Instruction Selection Instruction scheduling Register allocation 108 01 14 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 108 01 14 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 108 01 14 course cpeg421 08s Topic 6 ppt 3 Instruction Selection Some slides are from CS 640 lecture in George Mason University 108 01 14 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 108 01 14 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 108 01 14 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 Descriptionbased retargeting Machine description should also help with scheduling allocation 108 01 14 course cpeg421 08s Topic 6 ppt 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 108 01 14 add rj ri 0 sub rj ri 0 rshiftI rj ri 0 mul rj ri 1 or rj ri 0 divI rj r 1 xor rj ri 0 others 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 108 01 14 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 108 01 14 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 108 01 14 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 108 01 14 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 108 01 14 course cpeg421 08s Topic 6 ppt 13 Tile AST An AST tree Tile 6 get s ref val nu m Tile 1 ref nu m val Tile 2 108 01 14 Tile 5 Tile 4 ref nu m course cpeg421 08s Topic 6 ppt lab Tile 3 nu m 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 108 01 14 course cpeg421 08s Topic 6 ppt Where two operation trees meet they must be 15 Tree Walk by Tiling An Example a a 22 MOVE SP a MEM 22 SP 108 01 14 a course cpeg421 08s Topic 6 ppt 16 Example a a 22 t3 SP t4 MOVE a t2 t1 MEM 22 SP 108 01 14 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 SP 108 01 14 ld t1 sp a add t2 t1 22 st sp a t2 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 108 01 14 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 108 01 14 Tie boundaries together with register names Can incorporate a real register allocator or can simply course cpeg421 08s Topic 6 ppt use NextRegister 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 108 01 14 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 tile T covering x 108 01 14 cost T course cpeg421 08s Topic 6 ppt f y child y of tile T 22 Dynamic Programming for Optimal Tiling