CS 4980 CC, Note 14

Copyright © 2004, 2010
Robert W. Hasker

CS 4980 CC - Note 14

Ch. 17

Dataflow analysis

Is there a perfect optimizing compiler?

Suppose Opt(P) is a fully optimizing compiler which transforms P into the smallest program with the same input/output behavior as P.
- Can generalize to optimizing for speed, memory usage, etc.
- Let Q be a program which produces no output and never halts; then Opt(Q) must be
```
        L₁:  goto L₁
```
- Thus given Opt, we can solve the halting problem: is Opt(P) = Opt(Q), then the program does not halt; otherwise, it does.
Consequence: cannot build "fully optimizing compiler", must build "optimizing compilers": these transform programs into versions with same input/output behavior that hopefully are smaller and/or faster.
- goal: our optimized result is better than competitors'
Given any optimizing compiler, there's always (bigger) one which does a better job!
- one solution: recognize specific code segments, produce code for just that segment - really huge!
- real life solution: recognize general patterns and optimize those
"For any optimizing compiler there exists a better one:" known as the full employment theorem for compiler writers

This chapter

intraprocedural global optimization - optimizations within a procedure, but across all basic blocks
representation: quadruples
- Assem form hard to process because lose information about what is done to registers (just have uses and defs)
- Tree: too many forms
- quadruples: (a, b, c, ⊕): a ← b ⊕ c
control flow graph: nodes = quadruples, directed edges from each node to successors (nodes that can follow given node in execution sequence)
overview
- how to compute dataflow
- applications: common-subexpression elimination, constant propagation, copy propagation, dead-code elimination, etc.

Dataflow Analyses

unambiguous definition: t ← a ⊕ b or t ← M[a] are unambiguous definitions of t
- example of ambiguous definition: call function, passing variable as a reference parameter or accessing globals
unambiguous definition d of variable t reaches statement u if there is some path from d to u that does not contain any unambiguous definitions of t
computing reaching definitions
- label each move statement with an id
- given statement d₁: t ← x ⊕ y:
  - d₁ generates definition d₁ because no matter what other definitions reach the beginning of d₁, we know d₁ reaches the end
  - d₁ kills any other definition of t (coming into d₁)
- defs(t): set of all definitions (definition id's) of temporary t
- Fig. 17.2: gen and kill for all statements
- let
  - in[n]: set of definitions that reach the beginning of node n
  - out[n]: set of definitions that are available after executing n
- formula:
```
        in[n] = ∪ out[p] where p ∈ pred[n]
        out[n] = gen[n] ∪ (in[n] - kill[n])
```
  (where ∪ is the "big cup" - see p. 355)
- solve by iteration
Example: program 17.3, p. 356
- note: the only definition of a reaching statement 3 is at statement 1, so can change test to c > 5
available expressions
- issue: how to eliminate common subexpressions; for example, simplify the code z = a[i] * a[i]:
```
        t₁ ← i * 4
        t₂ ← a + t₁
        t₃ ← i * 4
        t₄ ← a + t₃
        z  ← t₂ * t₄
```
- identify available expressions: x ⊕ y is available at node n if
  - from every path from the entry point of the graph to node n, x ⊕ y is computed at least once; AND
  - there are no (potential!) definitions of x or y on the path from the start to node n
- computation: gen and kill sets over expressions [not on final]:
  - let gen[s]: expressions generated by s
    - node computing x ⊕ y generates {x ⊕ y}
  - let kill[s]: expressions killed by s
    - definition of x or y kills {x ⊕ y}
  - note b ← b + c does not generate b + c, because b is redefined!
  - store statement, M[a] ← b, kills any fetch of M[x] unless we can show x != a
  - formulas:
```
        in[n] = ∩ out[p] for p ∈ pred[n]
        out[n] = gen[n] ∪ (in[n] - kill[n])
```
  - algorithm
    - set in[] for start to empty set
    - set in[] for all other nodes to set of all expressions
    - set out[] for all nodes to empty?
    - apply above definitions
reaching expressions
- given node s with statement t ← x ⊕ y, x ⊕ y reaches node n if there is a path from s to n that does not redefine x or y and does not compute x ⊕ y
- useful for common subexpression elimination
liveness analysis
- see page. 358 for table defining gen[] and kill[]
- resulting def of in and out:
```
        in[n] = gen[n] ∪ (out[n] - kill[n])
        out[n] = ∪ in[s] for s ∈ succ[n]
```
  - this is backwards from other defs since liveness looks backwards!

Transformations using Dataflow Analysis

Common-subexpression elimination; algorithm:
1. identify a statement s: t ← x ⊕ y where x ⊕ y is available at s
2. compute set of reaching expressions for s; that is, find statements of the form n: v ← x ⊕ y where path from n to s does not compute x ⊕ y or redefine x or y
3. let w be a new temporary; rewrite n using
```
        n:  w ← x ⊕ y
        n': v ← w
```
4. modify s to be
```
        s: t ← w
```
- this may introduce new assignments that can be eliminated; this will be resolved by copy propagation
Constant Propagation
- Given
  - d : t ← c where c is a constant, and
  - n : y ← t ⊕ x (or vice-versa)
  where this is the only definition of t to reach n
- Rewrite n as y ← c ⊕ x
Copy Propagation
- similar to constant propagation
- algorithm
  1. Given
    - d : t ← z, and
    - n : y ← t ⊕ x (or vice-versa) where d is the only definition of t to reach n and z is not defined on any path from d to n (including loops!)
  2. Rewrite n as n : y ← z ⊕ x
- note: coalescing is a form of copy propagation, but need both since copy propagation can reveal other optimizations
Dead-code Elimination
- Given
```
        s : a ← b ⊕ c
```
  or
```
        s : a ← M[x]
```
  where a is not live-out from s, then s can be deleted
- note: instructions may have side-effects that are used
  - example: trap on overflow, divide by zero
  - must be careful about removing such instructions
  - eliminating such instructions can make debugging difficult: the optimized program should behave the same as the non-optimized program
    - However, this applies to just the defined bits of the language
    - If the language does not say how to compute a result, then the compiler can change
    - For example, a(x) + b(y) (in C, C++, most languages) might execute a before or after b
    - x++ + ++x has no defined value - there is no ordering on the computation of the x++ vs. the ++x or which value is used for x when computing the other subterm
speed-ups to dataflow analysis: not considered here

Alias Analysis

issue: can we optimize
```
        p.x ← 5
        q.x ← 7
        a   ← p.x
```
- would look at analysis of reaching definitions
- Only if know p and q are not at same location!
- this is the aliasing problem
possible places for aliases
- call-by-reference parameters
- variables whose address is taken
- l-value expressions that reference pointers (*p in C++, for example)
- "variables used in inner-nested procedures" - accessing something both globally and as a parameter?
issue: run into computability issues
solution: define "p may-alias q" if we cannot prove p is never an alias for q

Alias analysis based on types

appropriate for strongly-typed languages (Pascal, Java, Ada, ML, etc.)
if two variables have incomparable types, they cannot be aliases
algorithm
1. divide all memory locations into disjoint sets, alias classes;
  example for MiniJava:
  - new class for every frame location created by Frame.allocLocal
  - new class for every record field of every record type
  - new class for every array type
2. every fetch and store is labelled by its class
  - requires adding an aliasClass value in MEM nodes
3. if MEM nodes M_i[x] and M_j[y] have alias classes i and j with i = j, then M_i[x] may-alias M_j[y]
very conservative
- better: use flow information: see textbook
fails with languages supporting call-by-reference, type casting

Using may-alias information

treat each class as a separate variable

application to available expressions:

redefine kill set for storing results:

        M[a] ← b    gen: {}   kill: {M[x] | a may alias x at s}

example: apply to

        1: u    ← M[t]
        2: M[x] ← r
        3: w    ← M[t]
        4: b    ← u + w

if can show t may-alias x is false at statement 2; this means u and w are the same, so can apply copy-propagation to get

        1: z    ← M[t]
        2: M[x] ← r
        4: b    ← z + z

Review

full employment theorem for compiler writers
dataflow analysis
- available expressions, reaching expressions, liveness analysis
optimizations:
- common-subexpression elimination
- constant propagation
- copy propagation
- dead-code elimination
alias analysis: refining kills definition

Copyright © 2004, 2010 Robert W. Hasker