Prof. Bodik CS 164 Lecture 16, Fall 2004 1Intermediate Code. Local OptimizationsLecture 15Prof. 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 Summary• We have discussed– Runtime organization– Simple stack machine code generation– Improvements to stack machine code generation• Our compiler goes directly from AST to assembly language– And does not perform optimizations• Most real compilers use intermediate languagesProf. Bodik CS 164 Lecture 16, Fall 2004 4Why Intermediate Languages ?• 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 about Prof. Bodik CS 164 Lecture 16, Fall 2004 5Intermediate Languages• Each compiler uses its own intermediate language– sometimes more than one• 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 translates to several assembly instructions• Most opcodes correspond directly to assembly opcodesProf. Bodik CS 164 Lecture 16, Fall 2004 6Three-Address Intermediate Code• Each instruction is of the formx := y op z–yand 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 7Generating Intermediate Code• Similar to assembly code generation• Major difference– Use any number of IL registers to hold intermediate resultsProf. Bodik CS 164 Lecture 16, Fall 2004 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) (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 LanguageP → 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 10Definition. Basic Blocks• A basic blockis a maximal sequence of instructions with: – 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 the preceding instructions have been executedProf. Bodik CS 164 Lecture 16, Fall 2004 11Basic 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. Bodik CS 164 Lecture 16, Fall 2004 12Definition. Control-Flow Graphs• A control-flow graphis 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 CFGProf. Bodik CS 164 Lecture 16, Fall 2004 13Control-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 := 1i := 1L:x := x * xi := i + 1if i < 10 goto LProf. Bodik CS 164 Lecture 16, Fall 2004 14Optimization Overview• Optimization seeks to improve a program’s utilization of some resource– Execution time (most often)–Code size– Network messages sent– Battery power used, etc.• Optimization should not alter what the program computes– The answer must still be the same Prof. Bodik CS 164 Lecture 16, Fall 2004 15A Classification of Optimizations• For languages like C and Decaf there are three granularities 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 Optimizations• In practice, a conscious decision is made not to implement the fanciest optimization known•Why?– Some optimizations are hard to implement– Some optimizations are costly in terms of compilation time– The fancy optimizations are both hard and costly• The goal: maximum improvement with minimum of costProf. Bodik CS 164 Lecture 16, Fall 2004 17Local Optimizations• 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 Simplification• 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 compile time• In general, if there is a statementx := y op z–And y and z are constants–Then yopzcan 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 Optimizations• Eliminating unreachable code:– Code that is unreachable in the control-flow graph– Basic blocks that are not the target of any jump or “fall through” from a conditional– Such basic blocks can be eliminated• Why would such basic blocks occur?• Removing unreachable code makes the
View Full Document
Unlocking...