Advanced Compilers L9. Dynamic Compilation Lecture 9 Dynamic Compilation I. Motivation & Background II. Overview III. Compilation Policy IV. Partial Method Compilation V. Partial Dead Code Elimination VI. Escape Analysis VII. Results “Partial Method Compilation Using Dynamic Profile Information”, John Whaley, OOPSLA 01 M. Lam & J. WhaleyAdvanced Compilers L9. Dynamic Compilation I. Goals of This Lecture • Beyond static compilation • Example of a complete system • Use of data flow techniques in a new context • Experimental approachAdvanced Compilers L9. Dynamic Compilation Static/Dynamic • Compiler: high-level  binary, static • Interpreter: high-level, emulate, dynamic • Dynamic compilation: high-level  binary, dynamic – machine-independent, dynamic loading – cross-module optimization – Specialize program using runtime information (without profiling)Advanced Compilers L9. Dynamic Compilation High-Level/Binary • Binary translator: Binary-binary; mostly dynamic – Run “as-is” – Software migration (x86  alpha, sun, transmeta; 68000  powerPC  x86) – Virtualization (make hardware virtualizable) – Dynamic optimization (Dynamo Rio) – Security (execute out of code in a cache that is “protected”)Advanced Compilers L9. Dynamic Compilation Closed-world vs. Open-world • Closed-world assumption (most static compilers) – All code is available a priori for analysis and compilation. • Open-world assumption (most dynamic compilers) – Code is not available; arbitrary code can be loaded at run time. • Open-world assumption precludes many optimization opportunities. – Solution: Optimistically assume the best case, but provide a way out if necessary.Advanced Compilers L9. Dynamic Compilation II. Overview in Dynamic Compilation • Interpretation/Compilation policy decisions – Choosing what and how to compile • Collecting runtime information – Instrumentation – Sampling • Exploiting runtime information – frequently-executed code pathsAdvanced Compilers L9. Dynamic Compilation Speculative Inlining • Virtual call sites are deadly. – Kill optimization opportunities – Virtual dispatch is expensive on modern CPUs – Very common in object-oriented code • Speculatively inline the most likely call target based on class hierarchy or profile information. – Many virtual call sites have only one target, so this technique is very effective in practice.Advanced Compilers L9. Dynamic Compilation III. Compilation Policy • ∆Ttotal = Tcompile – (nexecutions * Timprovement) – If ∆Ttotal is negative, our compilation policy decision was effective. • We can try to: – Reduce Tcompile (faster compile times) – Increase Timprovement (generate better code) – Focus on large nexecutions (compile hot spots) • 80/20 rule: Pareto Principle – 20% of the work for 80% of the advantageAdvanced Compilers L9. Dynamic Compilation Latency vs. Throughput • Tradeoff: startup speed vs. execution performance Startup speed Execution performance Interpreter Best Poor ‘Quick’ compiler Fair Fair Optimizing compiler Poor BestAdvanced Compilers L9. Dynamic Compilation interpreted code compiled code fully optimized code when execution count = t1 (e.g. 2000) when execution count = t2 (e.g. 25000) Stage 1: Stage 2: Stage 3: Multi-Stage Dynamic Compilation System Execution count is the sum of method invocations & back edges executed.Advanced Compilers L9. Dynamic Compilation Granularity of Compilation • Compilation takes time proportional to the amount of code being compiled. • Many optimizations are not linear. • Methods can be large, especially after inlining. • Cutting inlining too much hurts performance considerably. • Even “hot” methods typically contain some code that is rarely or never executed.Advanced Compilers L9. Dynamic Compilation Example: SpecJVM db void read_db(String fn) { int n = 0, act = 0; byte buffer[] = null; try { FileInputStream sif = new FileInputStream(fn); buffer = new byte[n]; while ((b = sif.read(buffer, act, n-act))>0) { act = act + b; } sif.close(); if (act != n) { /* lots of error handling code, rare */ } } catch (IOException ioe) { /* lots of error handling code, rare */ } } Hot loopAdvanced Compilers L9. Dynamic Compilation Lots of rare code! void read_db(String fn) { int n = 0, act = 0; byte buffer[] = null; try { FileInputStream sif = new FileInputStream(fn); buffer = new byte[n]; while ((b = sif.read(buffer, act, n-act))>0) { act = act + b; } sif.close(); if (act != n) { /* lots of error handling code, rare */ } } catch (IOException ioe) { /* lots of error handling code, rare */ } } Example: SpecJVM dbAdvanced Compilers L9. Dynamic Compilation Optimize hot “regions”, not methods • Optimize only the most frequently executed segments within a method. • Simple technique: any basic block executed during Stage 2 is said to be hot. • Beneficial secondary effect of improving optimization opportunities on the common paths.Advanced Compilers L9. Dynamic Compilation Method-at-a-time Strategy execution threshold %of basic blocks compiledAdvanced Compilers L9. Dynamic Compilation execution threshold Actual Basic Blocks Executed %of basic blocksAdvanced Compilers L9. Dynamic Compilation Dynamic Code Transformations • Compiling partial methods • Partial dead code elimination • Escape analysisAdvanced Compilers L9. Dynamic Compilation IV. Partial Method Compilation 1. Based on profile data, determine the set of rare blocks. – Use code coverage information from the first compiled versionAdvanced Compilers L9. Dynamic Compilation 2. Perform live variable analysis. – Determine the set of live variables at rare block entry points. live: x,y,z Partial Method CompilationAdvanced Compilers L9. Dynamic Compilation 3. Redirect the control flow edges that targeted rare blocks, and remove the rare blocks. to interpreter… Partial Method CompilationAdvanced Compilers L9. Dynamic Compilation 4. Perform compilation normally. – Analyses treat the interpreter transfer point as an unanalyzable method call. Partial