Instruction Selection and Scheduling The Problem Writing a compiler is a lot of work Would like to reuse components whenever possible Would like to automate construction of components Front End Middle End Back End Infrastructure Front end construction is largely automated Middle is largely hand crafted Parts of back end can be automated Today s lecture Automating Instruction Selection and Scheduling Definitions 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 The Problem Modern computers still have many ways to do anything Consider register to register copy in ILOC Obvious operation is i2i ri rj Many others exist addI ri 0 rj subI ri 0 rj lshiftI ri 0 rj multI ri 1 rj divI ri 1 rj rshiftI ri 0 rj orI xorI ri 0 rj ri 0 rj and others Human would ignore all of these Algorithm must look at all of them find low cost encoding Take context into account busy functional unit The Goal Want to automate generation of instruction selectors Front End Middle End Back End Infrastructure Machine description Back end Generator Tables Pattern Matching Engine Description based retargeting Machine description should also help with scheduling allocation The Big Picture Need pattern matching techniques Must produce good code Must run quickly some metric for good A treewalk code generator runs quickly How good was the code Tree x IDENT a ARP 4 IDENT b ARP 8 Treewalk Code loadI loadAO loadI loadAO mult 4 r5 rarp r5 r6 8 r7 rarp r7 r8 r6 r8 r9 Desired Code loadAI rarp 4 r5 loadAI rarp 8 r6 mult r5 r6 r7 The Big Picture Need pattern matching techniques Must produce good code Must run quickly some metric for good A treewalk code generator runs quickly How good was the code Tree Treewalk Code x IDENT a ARP 4 IDENT b ARP 8 loadI loadAO loadI loadAO mult 4 r5 rarp r5 r6 8 r7 rarp r7 r8 r6 r8 r9 Pretty easy to fix See 1st digression in Ch 7 pg 317 Desired Code loadAI rarp 4 r5 loadAI rarp 8 r6 mult r5 r6 r7 How do we perform this kind of 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 bottom up rewrite systems Linear IR suggests using some sort of string matching Strings as input matcher as output Each string maps to a target machine instruction sequence Use text matching or peephole matching In practice both work well matchers are quite different Peephole Matching Basic idea Compiler can discover local improvements locally Look at a small set of adjacent operations Move a peephole over code search for improvement Classic example store followed by load Original code Improved code storeAI r1 rarp 8 loadAI rarp 8 r15 storeAI r1 rarp 8 i2i r1 r15 Peephole Matching Basic idea Compiler can discover local improvements locally Look at a small set of adjacent operations Move a peephole over code search for improvement Classic example store followed by load Simple algebraic identities Original code addI mult r2 0 r7 r4 r7 r10 Improved code mult r4 r2 r10 Peephole Matching Basic idea Compiler can discover local improvements locally Look at a small set of adjacent operations Move a peephole over code search for improvement Classic example store followed by load Simple algebraic identities Jump to a jump Original code jumpI L10 jumpI L10 L11 Improved code L10 jumpI L11 Peephole Matching Implementing it Early systems used limited set of hand coded patterns Window size ensured quick processing Modern peephole instruction selectors Break problem into three tasks IR Expander IR LLIR LLIR Simplifier LLIR LLIR LLIR Matcher LLIR ASM ASM Peephole Matching Expander Turns IR code into a low level IR LLIR Operation by operation template driven rewriting LLIR form includes all direct effects e g setting cc Significant albeit constant expansion of size IR Expander IR LLIR LLIR Simplifier LLIR LLIR LLIR Matcher LLIR ASM ASM Peephole Matching Simplifier Looks at LLIR through window and rewrites is Uses forward substitution algebraic simplification local constant propagation and dead effect elimination Performs local optimization within window IR Expander IR LLIR LLIR Simplifier LLIR LLIR LLIR Matcher ASM LLIR ASM This is the heart of the peephole system Benefit of peephole optimization shows up in this step Peephole Matching Matcher Compares simplified LLIR against a library of patterns Picks low cost pattern that captures effects Must preserve LLIR effects may add new ones e g set cc Generates the assembly code output IR Expander IR LLIR LLIR Simplifier LLIR LLIR LLIR Matcher LLIR ASM ASM Example Original IR Code OP Arg1 Arg2 Result mult 2 Y t1 sub x t1 w t1 r14 w r20 Expand LLIR Code r10 2 r11 y r12 rarp r11 r13 MEM r12 r14 r10 x r13 r15 x r16 rarp r15 r17 MEM r16 r18 r17 r14 r19 w r20 rarp r19 MEM r20 r18 Example LLIR Code r10 2 r11 y r12 rarp r11 r13 MEM r12 r14 r10 x r13 r15 x r16 rarp r15 r17 MEM r16 r18 r17 r14 r19 w r20 rarp r19 MEM r20 r18 Simplify LLIR Code r13 MEM rarp y r14 2 x r13 r17 MEM rarp x r18 r17 r14 MEM rarp w r18 Example LLIR Code r13 MEM rarp y r14 2 x r13 r17 MEM rarp x r18 r17 r14 MEM rarp w r18 Match ILOC Assembly Code loadAI rarp y r13 multI 2 x r13 r14 loadAI rarp x r17 sub r17 r14 r18 storeAI r18 rarp w Introduced all memory operations temporary names Turned out pretty good code Making It All Work Details LLIR is largely machine independent Target machine described as LLIR ASM pattern Actual pattern matching Use a hand coded pattern matcher gcc Several important compilers use this technology It seems to produce good portable instruction selectors Key strength appears to be late low level optimization Definitions 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 What Makes Code Run Fast Many operations have non zero latencies