Dynamic Compilation and Adaptive Optimization in Virtual MachinesWho am I?Course GoalsCourse OutlineCourse OutlineCourse Outline - SummaryDeveloping Sophisticated SoftwareThe CatchType Safe, OO, VM-implemented Languages Are MainstreamHave We Answered the Performance Challenges?Future Trends - SoftwareFuture Trends – HardwareFuture Trends – HardwareCourse OutlineWell-Known “Facts”TerminologyAdaptive Optimization Hall of FameAdaptive Optimization Hall of FameQuick History of VMsQuick History of VMsFeatured VMs in this TalkCourse Outline How are Programs Executed?Interpretation vs. (Dynamic) CompilationSelective OptimizationCourse Outline What is a JIT Compiler?Design RequirementsStructure of a JIT CompilerCourse Outline - SummaryCase Study 1: Jikes RVM [Fink et al., OOPSLA’02 tutorial]Jikes RVM Opt Level 0Jikes RVM Opt Level 1Jikes RVM Opt Level 2Case Study 2: IBM DK [Ishizaki et al. ’03]Optimizations on Extended BytecodesOptimizations on QuadruplesOptimizations on DAG of QUADsEffectiveness of Optimizations in IBM DK [Ishizaki, et al. OOPSLA’03]Case Study 3: HotSpot Server JIT [Paleczny et al. ’01]HotSpot Server JITCourse OutlineHigh level language-specific optimizationsOptimizing Virtual Function CallsSpeculatively Optimizing Virtual Function CallsOptimization of Heap Allocated ObjectsScalar ReplacementRedundant Load EliminationOptimizing with Precise ExceptionsCourse Outline JIT/VM InteractionsJIT Support for Memory ManagementJIT Support for Other Runtime ServicesRuntime Support for JIT Generated CodeAdvantages of JIT/VM InterdependencyDisadvantages of JIT/VM InterdependencyCourse Outline Selective OptimizationSelective Optimization ExamplesSelective Optimization Effectiveness: Jikes RVM, [Arnold et al.,TR Nov’04]Selective Optimization Effectiveness: Jikes RVM, [Arnold et al.,TR Nov’04]Designing an Adaptive Optimization SystemCourse Outline Profiling: How to Find Candidates for OptimizationHow to Find Candidates for Optimization: CountersHow to Find Candidates for Optimization: Call Stack SamplingHow to Find Candidates for Optimization: Call Stack SamplingHow to Find Candidates for OptimizationRecompilation Policies: Which Candidates to Optimize?Course Outline Case StudiesCase Study 1: Jikes RVM Architecture [Arnold et al. ’00]Jikes RVM: Recompilation Policy – Cost/Benefit ModelShort-running Programs: Jikes RVMShort-running Programs: Jikes RVMSteady State: Jikes RVMSteady State: Jikes RVM, no FDO (Mar ’04)Case Study 2: IBM DK for Java [Suganuma et al. ’01, ‘05]Profile CollectionRecompilation PolicyStartup: IBM DK for Java, no Specialization [Suganuma et al. ’01]Steady State: IBM DK for Java, no Specialization [Suganuma et al. ’01]But the world is not always simpleExample: Jikes RVM Compilers on AIX/PPCCourse Outline Understanding System BehaviorCode Size Comparison, startup: IBM DK for JavaCode Size Comparison, steady state: IBM DK for JavaExecution Profile: Jikes RVM (Jul ’02)Recomp. Decisions, 20 iterations for each benchmarkJikes RVMRecomp. Decisions, 20 iterations for each benchmarkJikes RVMRecompilation Activity: Jikes RVM (Jul ’02)Recompilation Activity (IBM DK for Java)Course Outline Research Issues for Adaptive Optimization (1/2)Research Issues for Adaptive Optimization (2/2)Learning From a Previous RunArnold, Welc, Rajan [OOPSLA’05]Profile Repository: Histogram of Method RuntimesProfile Repository: Histogram of Method RuntimesCourse OutlineFeedback-Directed Optimization (FDO)Issues in Gathering Profile DataIssue 1: What data do you collect?Issue 2: How do you collect the data?Issue 3: When do you collect the data?Common Approaches in VMsIBM DK Profiler [Suganuma et al ’01,’02]Arnold-Ryder [PLDI 01]: Full Duplication ProfilingCourse OutlineTypes of OptimizationCommon FDO TechniquesFully Automatic Profile-Directed InliningFully Automatic Profile-Directed InliningInlining Trials in SELF [Dean and Chambers 94]Code positioningMultiversioningStatic Multiversioning ExampleStatic Multiversioning with On-Stack Replacement [SELF, HotSpot, Jikes RVM]Dynamic Multiversioning: Customization in SELFIBM DK for Java with FDO [Suganuma et al. ’01]Specialization: IBM DK [Suganuma et al. ‘01]Impact AnalysisSteady State: IBM DK for Java + FDO/Specialization [Suganuma et al.’01]FDO PotpourriCourse OutlineExample: Class hierarchy based inliningInvalidation via On-Stack Replacement (OSR) [Chambers,Hölzle&Ungar’91-94, Fink&Qian’03]OSR MechanismsOSR and InliningApplications of OSRInvalidation DiscussionInvalidation via pre-existence [Detlefs & Agesen’99]Dynamic Class Hierarchy Mutation [Su and Lipasti, 06]Dynamic Class Hierarchy Mutation [Su and Lipasti, ’06]Runtime Specialization With Optimistic Heap Analysis [Shankar et al., OOPSLA’05]Finding Specialization PointsFinding Invariant Memory LocationsInvalidationResultsRuntime Specialization With Optimistic Heap Analysis [Shankar et al., OOPSLA’05]Course OutlineVirtual/Interface DispatchSpeculative Meta-data RepresentationsAdaptive GC techniquesSpatial Locality OptimizationsSpatial Locality Optimizations Course OutlineDebunked MythsMyths Revisited IMyths Revisited IIMyths Revisited IIIMyths Revisited IVMyths Revisited VMyth VI - Production VMs avoid complex optimizations, favoring stability over performanceThis does not mean there are no problemsHow much performance gain is interesting?Comparison Between HLL VMs and Dynamic Binary OptimizersWaves of Adaptive OptimizationThe 4th Wave of Adaptive Optimization?Performance AuditorWishful ThinkingChallengeTiming Infrastructure DesignResultsResultsPer-Method AccuracyNo shortage of research problems for virtual machines (1/2)No shortage of research problems for virtual machines (2/2)Future DirectionsConcluding ThoughtsAdditional Information – details on my web pageAcknowledgementsGeneral ReferencesReferences: Case Study Virtual MachinesReferenced PapersReferenced PapersReferenced PapersReferenced PapersReferenced PapersReferenced PapersReferenced PapersReferenced PapersReferenced Papers© 2006 IBM CorporationDynamic Compilation and Adaptive Optimization in Virtual MachinesInstructor: Michael HindMaterial contributed by: Matthew Arnold, Stephen Fink, David Grove, and Michael Hind2IBM ResearchACACES’06 | Dynamic Compilation and Adaptive Optimization in Virtual Machines | July 24-28, 2006© 2006 IBM CorporationWho am I? Helped build Jikes RVM (1998-2006)– GC Maps, live analysis, dominators, register allocation refactoring– Adaptive