Its optimization time!! Program Optimization “maximum benefit for minimal cost” When should optimization happen? AST? pro: machine independent con: no notion registers, not language dependent Assembly? pro: many optimization opportunities con: machine dependent And so, we really should be doing this with some IR. Three-address intermediate code Each instruction is of the form: x := y op z x := op z where x, z are registers, constants, etc. basic block A basic block is a sequence with no labels (except in the first point) an no jumps (except in the last point). So when we are inside a basic block, we can optimize the code inside sans worry about control flow. control-flow graph a control-flow graph is a directed graph with…. basic blocks as nodes as edge from A to B if an execution can pass from the last instruction in A to first instruction in B Three Levels of Optimizations local optimizations: apply to a basic block in isolation global optimizations: apply to a control-flow graph inter-procedural optimizations: optimizations between graphs, such as inclining some stuff you should run basic block dataflow loop instruction optimization / peephole register some special oop stuff function inclining method call targets class unboxing some functional stuff tail recursion deforestation basic block optimizations algebraic simplification x := x + 0 => x := x x := x * 1 => x := x y := y ** 2 => y := yy x := x * 8 => x := x << 3 on --ffast-math -- only works on ints (since nan * 0 = nan) x := x * 0 => x := 0 constant folding x := y op z with constant y and z, we can just fold it. so x := 2+2 => x := 4 static single-assignment form rewrite intermediate code in SSA form <= never reassign variables. Meaning, if two assignments end up with the same rhs, they compute the same value. Namely: So in SSA, x := y + z ... w := y + z we know that x and w can’t be redefined in SSA; this means that we cloud write: x := y + z ... w := x copy propagation so we can keep writing using static single-assignment form replacements. In particular note that once we are just assigning a variable to another, the first variable can just be replaced with the second everywhere. b := z + y a := b x := 2 * a we can stick b into a b := z + y a := b x := 2 * b and then we see that a := b is deadcode. b := z + y x := 2 * b dead code elimination within a basic block, only one type of dead code Suppose “w := rhs” appears in a basic block, but “w” doesn’t appear anywhere else in the program. We can say “w := rhs” is dead and can be eliminated. peephole optimization a “peephole” is a sequence of contiguous instructions; the optimizer replaces the sequence with another equivalent one, but faster. global optimizations How do we apply local optimizations to a global scope? Generally, to prove postulate P at any point requires knowing the entire function; so we either know X is definitely true, or we say “we don’t know.” example Consider the branching order: (X := 3, B > 0) => {(Y := Z + W), (Y := 0)} => (A := 2x) in this control flow graph, we never touch x in the middle, therefore we can just propagate x forward by replace it. program point every statement is associated with 2 program points: right before a statement right after a statement global constant propagation Let’s consider three states x can be: value interpretation \top not constant c constant, on every path \bot unreachable code so by the time you hit a program point, if x=c, then its constant. To perform this labeling, we must… transfer function for “in”(to a statement) and “out” (of a statement), we have, slides 21 and more https://web.stanford.edu/class/cs143/lectures/lecture15.pdf. an algorithm For every entry s_{0} to the program, we set:

and set:

everywhere else. An then we just apply the rules above. convergence This system converges because the rules have it such that \bot &lt; c &lt; \top (once something is top, it can’t go back.) So, \top is the “greatest” value, and \bot the “least”. We can then lub the rules 1-4 from above into on rule:

So you can just see the lub of predecessor hierarchy of each statement. dead code elimination a variable x is “live” at statement s if… there’s a statement s&rsquo; that uses x there’s a path from s to s&rsquo; that path has no intervening assignment to x