1CS553 Lecture Dynamic Optimizations 2Dynamic Optimizations Last time– Profiling Today– Dynamic compilationCS553 Lecture Dynamic Optimizations 3 Limitations of static analysis– Programs can have values and invariants that are known at runtime butunknown at compile time. Static compilers cannot exploit such values orinvariants– Many of the motivations for profile-guided optimizations apply here Basic idea– Perform translation at runtime when more information is known– Traditionally, two types of translations are done– Runtime code generation (JIT compilers)– Partial evaluation (Staged compilation)MotivationCS553 Lecture Dynamic Optimizations 4 Basic idea– Take a general program and partially evaluate it, producing a specializedprogram that’s more efficient e.g., f(a,b,c)→f’(a,b), where the result has its third parameter hard-coded into the implementation. f’ is typically more efficient than f– Exploit runtime constants, which are variables whose value does notchange during program execution, e.g., write-once variablesPartial Evaluation Exploiting runtime constants− Perform constant propagation− Eliminate memory ops− Remove branches− Unroll loopsImproves performance by moving computation from runtime to compiletimeCS553 Lecture Dynamic Optimizations 5Applications with Runtime Constants Interpreters: Simulators: Graphics renderers: Scientific simulations: Extensible OS kernels: Examples– A cache simulator might take the line size as a parameter– A partially evaluated simulator might produce a faster simulator for thespecial case where the line size is 16Program being interpreted is runtime constantSubject of simulation (circuit, cache, network) isruntime constantThe scene to render is runtime constantMatrices can be runtime constantsExtensions to the kernel can be runtime constant2CS553 Lecture Dynamic Optimizations 6Partial Evaluation (cont) Active research area– Interesting theoretical results– Can partially evaluate an interpreter with respect to a program (i.e.,compile the program) [1st Futamura projection]– Can partially evaluate a partial evaluator with respect to an interpreter(i.e, generate a compiler) [2nd Futamura projection]– Can partially evaluate a partial evaluator with respect to a partialevaluator (i.e., generate a compiler generator) [3rd Futamuraprojection]– Most PE research focuses on functional languages– Key issue– When do we stop partially evaluating the code when there is iterationor recursion?CS553 Lecture Dynamic Optimizations 7Dynamic Compilation with DyC DyC [Auslander, et al 1996]– Staged compilation– Apply ideas of Partial Evaluation– Perform some of the Partial Evaluation at runtime– Can handle more runtime constants than Partial Evaluation– Reminiscent of link-time register allocation in the sense that thecompilation is performed in stages Tradeoffs– Must overcome the run-time cost of the dynamic compiler– Fast dynamic compilation: low overhead– High quality dynamically generated code: high benefit– Ideal: dynamically translate code once, execute this code many times– Implication: don’t dynamically translate everything– Only perform dynamic translation where it will be profitableCS553 Lecture Dynamic Optimizations 8Applying Dynamic Compilation System goal– Both fast dynamic compilation and high quality compiled code How do we know what will be profitable?– Let user annotations guide the dynamic compilation process System design– Dynamic compilation for the C language– Declarative annotations:– Identify pieces of code to dynamically compile: dynamic regions– Identify source code variables that will be constant during theexecution of dynamic regionsCS553 Lecture Dynamic Optimizations 9Staged Compilation in DyCannotated Ccodestaticcompilertemplatesetup codedirectivesdynamiccompiler(stitcher)executableprogramruntimevaluesstatic compile time dynamic compile time− Make the static compiler do as much work as possible− Give the dynamic compiler as little work as possible3CS553 Lecture Dynamic Optimizations 10Dynamically Compiled Code Static compiler– Produces machine code templates, in addition to normal mach code– Templates contain holes that will be filled with runtime const values– Generates setup code to compute the vals of these runtime consts.– Together, the template and setup code will replace the original dynamicregiondynamic region entrancefirst time?setup codetemplate codedynamic region exitCS553 Lecture Dynamic Optimizations 11The Dynamic Compiler The Stitcher– Follows directives, which are produced by the static compiler, to copycode templates and to fill in holes with appropriate constants– The resulting code becomes part of the executable code and is hopefullyexecuted many timesCS553 Lecture Dynamic Optimizations 12cacheResult cacheLookup (void *addr, Cache *cache) { dynamicRegion(cache) { /* cache is a runtime constant */ int blockSize = cache->blockSize; int numLines = cache->numLines; int tag = addr / (blockSize * numLines); int line = (add / blockSize) % numLines; setStructure **setArray = cache->lines[line]->sets; int assoc = cache->associativity; int set; unrolled for (set=0; set<assoc; set++) { if (setArray[set]dynamic->tag == tag) return CacheHit; } return CacheMiss; } /* end of dynamic region */}The Annotations CS553 Lecture Dynamic Optimizations 13cacheResult cacheLookup (void *addr, Cache *cache) { dynamicRegion(cache) { /* cache is a runtime constant */ int blockSize = cache->blockSize; int numLines = cache->numLines; int tag = addr / (blockSize * numLines); int line = (add / blockSize) % numLines; setStructure **setArray = cache->lines[line]->sets; int assoc = cache->associativity; int set; unrolled for (set=0; set<assoc; set++) { if (setArray[set]dynamic->tag == tag) return CacheHit; } return CacheMiss; } /* end of dynamic region */ dynamicRegion(cache)− Identifies a block that will be dynamically compiled− Its arguments are runtime constants within the scope of the dynamicregion− The static compiler will compute additional runtime constants that arederived from this initial setThe Annotations4CS553 Lecture Dynamic Optimizations 14cacheResult cacheLookup (void *addr, Cache *cache) { dynamicRegion(cache) { /* cache is a runtime constant */ int blockSize = cache->blockSize;