Local OptimizationsLecture OutlineCode Generation SummaryWhen to perform optimizationsIntermediate Languages for OptimizationTexts often consider optimizing based on Three-Address Intermediate CodeHow hard to generate this kind of Intermediate Code?Generating Intermediate Code (Cont.)We can define an Intermediate Language formally, too...Optimization ConceptsDefinition. Basic BlocksBasic Block ExampleDefinition. Control-Flow GraphsControl-Flow Graphs. Example.Optimization OverviewA Classification of OptimizationsCost of OptimizationsSlide 18Algebraic SimplificationConstant FoldingFlow of Control OptimizationsUsing (Static) Single Assignment Form SSACommon Subexpression EliminationCopy PropagationCopy Propagation and Constant FoldingCopy Propagation and Dead Code EliminationApplying Local OptimizationsAn ExampleSlide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Peephole Optimizations on Assembly CodePeephole Optimizations (Cont.)Slide 43Local Optimizations. Notes.Prof. Fateman CS164 Lecture 21 1Local OptimizationsLecture 21Prof. Fateman CS164 Lecture 21 2Lecture Outline•Local optimization•Next time: global optimizationsProf. Fateman CS164 Lecture 21 3Code Generation Summary•We have discussed–Runtime organization–Simple stack machine code generation•Our compiler goes directly from AST to assembly language with a brief stop or two–If we preserved environment data from typecheck, use that;–cleanup other minor loose ends perhaps.–Simple-compile.lisp does not perform optimizations•Most real compilers use some optimization somewhere (history of Fortran I..)Prof. Fateman CS164 Lecture 21 4When to perform optimizations–On AST•Pro: Machine independent•Con: Too high level–On assembly language•Pro: Exposes more optimization opportunities•Con: Machine dependent•Con: Must reimplement optimizations when retargetting–On an intermediate language between AST and assembler•Pro: Machine independent•Pro: Exposes many optimization opportunitiesProf. Fateman CS164 Lecture 21 5Intermediate Languages for Optimization•Each compiler uses its own intermediate language–IL design is still an active area of research•Intermediate language = high-level assembly language–Uses register names, but has an unlimited number–Uses control structures like assembly language–Uses opcodes but some are higher level•E.g., push may translate to several assembly instructions•Perhaps some opcodes correspond directly to assembly opcodes•Usually not stack oriented.Prof. Fateman CS164 Lecture 21 6Texts often consider optimizing based on Three-Address Intermediate Code•Computations are reduced to simple forms like x := y op z [3 addresses]or maybe x := op y–y and z can be only registers or constants (not expressions!)–Also need control flow test/jump/call/ •New variables are generated, perhaps to be used only once (SSA= static single assignment)•The expression x + y * z is translated as t1 := y * z t2 := x + t1–Each subexpression then has a “home” for its valueProf. Fateman CS164 Lecture 21 7How hard to generate this kind of Intermediate Code? •Similar technique to our assembly code generation•Major differences–Use any number of IL registers to hold intermediate results–Not stack oriented•Same compiler organization..Prof. Fateman CS164 Lecture 21 8Generating Intermediate Code (Cont.)•Igen(e, t) function generates code to compute the value of e in register t•Example:igen(e1 + e2, t) = igen(e1, t1) ;(t1 is a fresh register) igen(e2, t2) ;(t2 is a fresh register) t := t1 + t2 ;(instead of “+”)•Unlimited number of registers simple code generationProf. Fateman CS164 Lecture 21 9We can define an Intermediate Language formally, too...P S ; P | S id := id op id | id := op id | id := id | push id | id := pop | if id relop id goto L | L: | jump L•id’s are register names•Constants can replace id’s•Typical operators: +, -, *Prof. Fateman CS164 Lecture 21 10Optimization Concepts•Inside Basic Blocks•Between/Around Basic Blocks: Control Flow GraphsProf. Fateman CS164 Lecture 21 11Definition. Basic Blocks•A basic block is a maximal sequence of instructions with: –no labels (except at the first instruction), and –no jumps (except in the last instruction)•Idea: –Cannot jump into a basic block (except at beginning)–Cannot jump out of a basic block (except at end)–Each instruction in a basic block is executed after all the preceding instructions have been executedProf. Fateman CS164 Lecture 21 12Basic Block Example•Consider the basic block1. L: 2. t := 2 * x3. w := t + x4. if w > 0 goto L•No way for (3) to be executed without (2) having been executed right before–We can change (3) to w := 3 * x–Can we eliminate (2) as well?Prof. Fateman CS164 Lecture 21 13Definition. Control-Flow Graphs•A control-flow graph is a directed graph with–Basic blocks as nodes–An edge from block A to block B if the execution can flow from the last instruction in A to the first instruction in B–E.g., the last instruction in A is jump LB –E.g., the execution can fall through from block A to block B•Frequently abbreviated as CFG ... too bad we already used this..Prof. Fateman CS164 Lecture 21 14Control-Flow Graphs. Example.•The body of a method (or procedure) can be represented as a control-flow graph•There is one initial node•All “return” nodes are terminalx := 1 i := 1L: x := x * x i := i + 1 if i < 10 goto LProf. Fateman CS164 Lecture 21 15Optimization Overview•Optimization seeks to improve a program’s utilization of some resource–Execution time (most often) [instructions, memory access]–Code size–Network messages sent, –Battery power used, etc.•Optimization should not alter what the program computes–The answers must still be the same (* sometimes relaxed for floating point numbers… a bad idea, though)–Same behavior on bad input (?) e.g. array bounds?Prof. Fateman CS164 Lecture 21 16A Classification of Optimizations•For languages like Java there are three granularities of optimizations1. Local optimizations•Apply to a basic block in isolation2. Global optimizations•Apply to a control-flow graph (function body) in isolation3. Inter-procedural optimizations•Apply across call
View Full Document
Unlocking...