Prof. Bodik CS 164 Lecture 16, Fall 2004 1Intermediate Code. Local Op timization sLecture 34Prof. Bodik CS 164 Lecture 16, Fall 2004 2Lecture Outline¥ Intermediate code¥ Local optimizations¥ Next time: global optimizationsProf. Bodik CS 164 Lecture 16, Fall 2004 3Code Generation S ummary¥ We have discussedÐ Runtime organizationÐ Simple stack machine code generationÐ Improvements to stack machine code generation¥ Our compiler goes directly from AST toassembly languageÐ And does not perform optimizations¥ Most real compilers use intermediatelanguagesProf. Bodik CS 164 Lecture 16, Fall 2004 4Why Inter mediat e Language s ?¥ When to perform optimizationsÐ On AST¥ Pro: Machine independent¥ Cons: Too high levelÐ On assembly language¥ Pro: Exposes optimization opportunities¥ Cons: Machine dependent¥ Cons: Must reimplement optimizations when retargettingÐ On an intermediate language¥ Pro: Machine independent¥ Pro: Exposes optimization opportunities¥ Cons: One more language to worry aboutProf. Bodik CS 164 Lecture 16, Fall 2004 5Intermediate Language s¥ Each compiler uses its own intermediate languageÐ sometimes more than one¥ Intermediate language = high-level assemblylanguageÐ Uses register names, but has an unlimited numberÐ Uses control structures like assembly languageÐ Uses opcodes but some are higher level¥ E.g., push translates to several assembly instructions¥ Most opcodes correspond directly to assembly opcodesProf. Bodik CS 164 Lecture 16, Fall 2004 6Th ree-Address I ntermedia te Code¥ Each instruction is of the formx := y op zÐ y and z can be only registers or constantsÐ Just like assembly¥ Common form of intermediate code¥ The AST expression x + y * z is translated ast1 := y * zt2:= x + t1Ð Each subexpression has a ÒhomeÓProf. Bodik CS 164 Lecture 16, Fall 2004 7Ge nerating Intermediat e Code¥ Similar to assembly code generation¥ Major differenceÐ Use any number of IL registers to holdintermediate resultsProf. Bodik CS 164 Lecture 16, Fall 2004 8Ge nerating Intermediat e Code (C ont.)¥ Igen(e, t) function generates code tocompute the value of e in register t¥ Example:igen(e1+ e2, t) =igen(e1, t1) (t1is a fresh register)igen(e2, t2) (t2is a fresh register)t := t1+ t2¥ Unlimited number of registers⇒ simple code generationProf. Bodik CS 164 Lecture 16, Fall 2004 9An Intermediate L ang uageP " 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. Bodik CS 164 Lecture 16, Fall 2004 10De finition. Basic B locks¥ A basic block is a maximal sequence of instructionswith:Ð no labels (except at the first instruction), andÐ no jumps (except in the last instruction)¥ Idea:Ð Cannot jump in 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 thepreceding instructions have been executedProf. Bodik CS 164 Lecture 16, Fall 2004 11Basic B l ock 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. Bodik CS 164 Lecture 16, Fall 2004 12De finition. Control-Flow Gra phs¥ 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 flowfrom 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 CFGProf. Bodik CS 164 Lecture 16, Fall 2004 13Control-Flow Gra phs . Example.¥ The body of a method (orprocedure) can berepresented as a control-flow graph¥ There is one initial node¥ All ÒreturnÓ nodes areterminalx := 1i := 1L:x := x * xi := i + 1if i < 10 goto LProf. Bodik CS 164 Lecture 16, Fall 2004 14Op timization Ove rvie w¥ Optimization seeks to improve a programÕsutilization of some resourceÐ Execution time (most often)Ð Code sizeÐ Network messages sentÐ Battery power used, etc.¥ Optimization should not alter what theprogram computesÐ The answer must still be the sameProf. Bodik CS 164 Lecture 16, Fall 2004 15A Cl assification of Optimizations¥ For languages like C and Decaf there are threegranularities of optimizations1. Local optimizations¥ Apply to a basic block in isolation2. Global optimizations¥ Apply to a control-flow graph (method body) in isolation3. Inter-procedural optimizations¥ Apply across method boundaries¥ Most compilers do (1), many do (2) and a few do (3)Prof. Bodik CS 164 Lecture 16, Fall 2004 16Cost of Optimizati ons¥ In practice, a conscious decision is made notto implement the fanciest optimization known¥ Why?Ð Some optimizations are hard to implementÐ Some optimizations are costly in terms ofcompilation timeÐ The fancy optimizations are both hard and costly¥ The goal: maximum improvement withminimum of costProf. Bodik CS 164 Lecture 16, Fall 2004 17Local O ptimizatio ns¥ The simplest form of optimizations¥ No need to analyze the whole procedure bodyÐ Just the basic block in question¥ Example: algebraic simplificationProf. Bodik CS 164 Lecture 16, Fall 2004 18Algebraic Sim plif i cation¥ Some statements can be deletedx := x + 0x := x * 1¥ Some statements can be simplifiedx := x * 0 ⇒ x := 0y := y ** 2 ⇒ y := y * yx := x * 8 ⇒ x := x << 3x := x * 15 ⇒ t := x << 4; x := t - x(on some machines << is faster than *; but not on all!)Prof. Bodik CS 164 Lecture 16, Fall 2004 19Constant Folding¥ Operations on constants can be computed at compiletime¥ In general, if there is a statementx := y op zÐ And y and z are constantsÐ Then y op z can be computed at compile time¥ Example: x := 2 + 2 ⇒ x := 4¥ Example: if 2 < 0 jump L can be deleted¥ When might constant folding be dangerous?Prof. Bodik CS 164 Lecture 16, Fall 2004 20Flow of Control Opt i miz ations¥ Eliminating unreachable code:Ð Code that is unreachable in the control-flow graphÐ Basic blocks that are not the target of any jump or ÒfallthroughÓ from a conditionalÐ Such basic blocks can be eliminated¥ Why would such basic blocks occur?¥ Removing unreachable code makes the programsmallerÐ And sometimes also faster¥ Due to memory cache effects (increased spatial locality)Prof. Bodik CS 164 Lecture 16, Fall 2004 21Single
View Full Document
Unlocking...