Content

  1. Overview
    1. Local: Backward Copy Propagation
    2. Local: Common Subexpression Elimination
    3. Global: Induction Variable Elimination
    4. Global: Common Subexpression Elimination
    5. Global: Data Flow Analysis
      1. Reachability Analysis
      2. Availability Analysis

Overview

  • Local
    • Constant folding
    • Constant combining
    • Strength reduction
    • Constant propagation
    • Common subexpression elimination
    • Backward copy propagation
  • Global
    • Deadcode elimination
    • Constant propagation
    • Forward copy propagation
    • Common subexpression elimination
    • Code motion
    • Loop strength reduction
    • Induction variable elimination

Local: Backward Copy Propagation

  • Rules
    1. X and Y in same block
    2. Y is a move to register
    3. dest(X) is not live out of the block
    4. Y uses dest(X)
    5. dest(Y) not used between X and Y
    6. dest(X) not used after the first redef of dest(Y)
    7. Replace src(Y) with dest(Y) on path X to Y

Local: Common Subexpression Elimination

  • Rules
    1. X and Y have same opcode; Y follows X
    2. src(X) = src(Y) for all srcs
    3. No def of src between X and Y for all srcs
    4. No def of dest(X) between X and Y
    5. Replace Y with dest(Y) = dest(X)

Global: Induction Variable Elimination

Global: Common Subexpression Elimination

  • Rules
    1. X and Y have same opcode; X dominates Y
    2. src(X) = src(Y) for all srcs
    3. No def of src between X and Y for all srcs
    4. Insert rx = dest(X) after X
    5. Replace Y with dest(Y) = rx
Dominance

n dominates m if all paths to m goes through n

Global: Data Flow Analysis

Liveliness and reachability are important knowledge derived from data flow analysis. Used for applications e.g. CSE, copy propagation, etc.

Reachability Analysis

Whether a definition reaches a statement.

in[B]     - variables live on entry of B
out[B]    - variables live on exit of B
gen[B]    - definitions generated by B
kill[B]   - subsequent definitions killing those in B | killed by B

gen[n: v = f(...)] = {n}
kill[n] = defs[v] - {n} if n defines v
in[n] = ∪_pred_P_of_n(out[P])
out[n] = gen[n] ∪ (in[n] - kill[n])

Availability Analysis

For CSE, reachability is not safe.

in[n] = ∩_pred_P_of_n(out[P]) if n not entry
out[n] = gen[n] ∪ (in[n] - kill[n])

If (<x op y> reaches s ≡ b = x op y) && (s is in B):
    For all s' s.t. (s' ≡ z = x op y) && (s' reaches s):
        Replace s' by (t1 = x op y; z = t1;) where t1 is the same for all s'
    Replace s by (b = t1;)

If the subexpression is expensive, better reuse the result even it comes from only 1 branch.

Glossary

  • Define: an expression having its value computed at point p
  • Kill: one of the arguments of an expression is redefined at point p
  • Available: every path leading to point p contains a prior definition of an expression that is not killed between its definition and p

References

results matching ""

    No results matching ""