#1Local Local OptimizationsOptimizations#2One-Slide Summary• An optimization changes a program so that it computes the same answer in less time (or using less of some other resource). •We represent the program using a special intermediate form. •Each method is viewed as a control flow graph where the nodes as basic blocks of instructions with known entry and exit points. The instructions have been changed so that a single assignment defines each variable.#3Upcoming Events• This Friday, 4pm, 228E/236D– “Halloween Fall Festival”. Prizes for best costumes, trick-or-treats provided, bring an artistic dish if you like, apple dunking, music?• Postponed!– Barbara Liskov lectures, www.liskovatuva.com• Wednesday Nov 18, evening– Fireside chat with Kim “Reality TV” Hazelwood and Wes “Romance Novel” Weimer•???– The final for this class. Vote.#4Lecture Outline•Intermediate code•Local optimizations•Next time: larger-scale program analyses#5Why Optimize?• What's the point?• Do we care about this in real life?#6When To Optimize?• When to perform optimizations–On AST (just like type checking)• Pro: Machine independent• Cons: Too high level–On assembly language (compilers only)• 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#7Intermediate Languages• 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 translates to several assembly instructions• Most opcodes correspond directly to assembly opcodes#8Three-Address Intermediate Code• Each instruction is of the form x := y op z– y and z can be only registers, variables or constants•Common form of intermediate code•The AST expression x + y * z is translated as t1 := y * z t2 := x + t1– Each subexpression lives in a temporary#9Generating Intermediate Code• 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•Unlimited number of registers ⇒ simple code generation#10An 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: +, -, *#11Basic 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 executed#12Basic Block Example• Consider the basic block1. L1: 2. t := 2 * x3. w := t + x4. if w > 0 goto L2•No way for (3) to be executed without (2) having been executed right before#13Basic Block Example• Consider the basic block1. L1: 2. t := 2 * x3. w := t + x4. if w > 0 goto L2•No way for (3) to be executed without (2) having been executed right before– We can change (3) to w := 3 * x#14Basic Block Example• Consider the basic block1. L1: 2. t := 2 * x3. w := t + x4. if w > 0 goto L2•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?#15Control-Flow Graphs• A control-flow graph is a directed graph:– 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#16Control-Flow Graphs. Example.• The body of a method (or procedure) can be represented as a control-flow graph•There is one initial node– The “start node” •All “return” nodes are terminalx := 1i := 1L: x := x * x i := i + 1 if i < 10 goto L#17CFG ' Flow Chart#18Optimization 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 –First Rule of Optimization Club: Don't Break The Build#19A Classification of Optimizations• For languages like C and Cool 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 very few do (3)• Some interpreters do (1), few do (2), basically none do (3)#20Cost of Optimizations• In practice, a conscious decision is made not to implement the fanciest optimization known•Why?#21Cost 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/interpretation time– The fancy optimizations are both hard and costly•The goal: maximum improvement with minimum of costQ: Movies (363 / 842) •This 1993 comedy film also starring Andie MacDowell "begins" with the following radio banter: "Rise and shine, campers, and don't forget your booties 'cause it's cooooold out there today. / It's cold out there every day. What is this, Miami Beach? / Not hardly. So the big question on everybody's lips / -- On their chapped lips -- / their chapped lips is, does Phil feel lucky?"Q: Books (763 / 842) • This 18th- and 19th-century English poet, painter and religious printmaker believed in racial and sexual equality and rejected imposed secular authority. Peter Marshall described him as, "a revolutionary anarchist, [...] anticipating modern anarchism and social ecology. With William Godwin, he