SSA

Where is a Variable Defined or Used?

Example: Loop-Invariant Code Motion
- Are B, C, and D only defined outside the loop?
- Other definitions of A inside the loop?
- Uses of A inside the loop?
Example: Copy Propagation
- For a given use of X
  - All are reaching definitions of X
    - Copies from same variable: e.g., X = Y
  - Where Y is not redefined since that copy?
- If so, substitute use of X with use of Y
It would be nice if we could traverse directly between related uses and defs
- This would enable a form of sparse code analysis (skip over “don’t care” cases)

Appearances of same variable name may be unrelated

This values in reused storage locations may be provably independent
- In which case the compiler can optimize them as separate values
Compiler could use renaming to make these different versions more explicit

Definition-Use and Use-Definition Chains

Use-Definition(UD) Chains
- for a given definition of a variable X, what are all of its uses
Definition-Use(DU) Chains
- for a given use of a variable x, what are all the reaching definitions of X

Static single Assignment (SSA)

Static single assignment is an IR where every variable is assigned a value at most once in the program text.
Easy for a basic block(reminiscent of Value Numbering):
- Visit each instruction in program order:
  - LHS: assign to a fresh version of the variable
  - RHS: use the most recent version of each variable

What about joins in the CFG?

Solution: Use a notational fiction $\Phi$ function

The $\Phi$ function

$\Phi$ merges multiple definitions along multiple control paths into a single definition
At a basic block with p predecessors, there are p arguments to the $\Phi$ function
- $X_{new} \leftarrow \Phi(x_1, x_2, … x_p)$

Trivial SSA & Minimal SSA

Each assignment generates a fresh variable
At each join point insert $\Phi$ functions for all live variables
Trivial SSA results too many $\Phi$ functions inserted
Solution: Minimal SSA
At each join point insert $\Phi$ functions for all live variables with multiple outstanding defs

Trivial SSA	Minimal SSA

Example

When do we insert $\Phi$

We insert a $\Phi$ function for variable A in block Z iff:
- A was defined more than once before
  - (i.e., A defined in X and Y AND X $\neq$ Y)
- There exists a non-empty path from x to z, $P_{xz}$ and a non-empty path from y to z, $P_{yz}$, s.t.
  - $P_{xz} \cap P_{yz}$ = {z}
    - i.e. (Z is only common block along paths)
  - z $\not\in$ $P_{xq}$ or z $\not\in$ $P_{yr}$ where $P_{xz} = P_{xq} \rightarrow z$ and $P_{yz} = P_{yr} \rightarrow z$
    - i.e. (At least one path reaches Z for first time)
Entry block contains an implicit def of all vars
Note: v = $\Phi(…)$ is a def of v

Dominance Property of SSA

In SSA, definitions dominate uses
- If $x_i$ is used in $x \leftarrow \phi(…, x_i, xxx)$, then BB($x_i$) dominates $i^{th}$ predecessor of BB(PHI)
- If $x$ is used in $y \leftarrow …x…$, then BB(x) dominates BB(y)
We can use this for an efficient algorithm to convert to SSA

Dominance Frontier

The Dominance Frontier of a node x = {w $|$ x dom pred(w) And !(x sdom w)}
- Recall x strictly dominates w iff x dom w and x $\neq$ w

If there is a def of a in block 5, then nodes in the dominance frontier(5) need to insert a $\phi$ for a
To Compute SSA
1. Place all $\Phi$
2. Rename all variables

Using Dominance Frontier to Place $\Phi$

Gather all the defsites of every variable
Then, for every variable
- for each defsite
  - for each node in DominanceFrontier
    - if we haven’t put $\Phi$ in node, then put one in
    - if this node didn’t define the variable before, then add this node to the defsites
This essentially computes the Iterated Dominance Frontier on the fly, inserting the minimal number of $\Phi$ necessary

for each node n
    for each variable v defined in n
        orig[n] add v
        defsites[v] add n
        
for each variable v
    W = defsites[v]
    while W not empty
        n = remove node from W
        for each y in DF[n]
            if y not in PHI[v]
                insert v = phi() at top of y
                PHI[v] add y
                if v not in orig[y]
                    W add y

Renaming Variables

Algorithm:
- Walk the D-tree, renaming variables as you go
- Replace uses with more recent renamed def
For straight-line code this is easy
What if there are branches and joins?
- use the closest def such that the def is above the use in the D-tree
Easy Implementation
- for each var: rename(v)
- rename(v):
  - replace uses with top of stack
  - at def: push onto stack
  - call rename(v) on all children in D-tree
  - for each def in this block pop from stack

Example

Dominance Frontier

Node	DF
1	{}
2	{2}
3	{2}
4	{}
5	{7}
6	{7}
7	{2}

Insert $\Phi$

Node	DF	Orig[Node]
1	{}	{i, j, k}
2	{2}
3	{2}
4	{}
5	{7}	{j, k}
6	{7}	{j, k}
7	{2}

variable	defsites[variable]
i	{1}
j	{1, 5, 6}
k	{1,5, 6}

variable	defsite	W	DF	insert block
i	{1}	{1}	{}
j	{1, 5, 6}	{1}	{}
j	{1, 5, 6} {1, 5, 6, 7}	{5} <7>	{7} {2}	{7} {2}
j	{1, 5, 6}	{7}	{2}	Because the previous one insert a $\Phi$ to 2 no duplicate insert here
k	{1, 5, 6}	{1}	{}
k	{1, 5, 6} {1, 5, 6, 7}	{5} <7>	{7} {2}	{7} {2}
k	{1, 5, 6}	{7}	{2}	Because the previous one insert a $\Phi$ to 2 no duplicate insert here

Rename vars

Constant Propagation

If v $\leftarrow$ c, replace all uses of v with c
If v $\leftarrow \Phi(c, c, c)$ (each input is the same constant), replace all uses of v with c

W = list of all defs
while !W.isEmpty
    Stmt S = W.removeOne
    if ((S has form v <- c) || (S has form v <- phi(c,...c,)))
    then
        delete S
        for each stmt U that uses v
        begin
            replace v with c in U
            W.add(U)
        end
    end if

SSA	Constant Propagation

Conditional Constant Propagation

Does block 6 every execute?
Simple Constant Propagation can’t tell
But “Conditional Const Prop” can tell:
- Assumes blocks don’t execute until proven otherwise
- Assumes values are constants until proven otherwise
Algorithm
- Keeps track of
  - Blocks:
    - Assume unexecuted until proven otherwise
  - Variables:
    - Assume not executed (only with proof of assignments of a non-constant value do we assume not constant)
    - Lattice for representing variables:
Example

CSCD70 Lec4

Where is a Variable Defined or Used?

Appearances of same variable name may be unrelated

Definition-Use and Use-Definition Chains

Static single Assignment (SSA)

What about joins in the CFG?

The $\Phi$ function

Trivial SSA & Minimal SSA

When do we insert $\Phi$

Dominance Property of SSA

Dominance Frontier

Using Dominance Frontier to Place $\Phi$

Renaming Variables

Example

Constant Propagation

Conditional Constant Propagation

CATALOG

FEATURED TAGS