Static Single Assignment

Static single assignment (SSA)

A variable in a program can have multiple definitions. In Bril definitions are instructions which compute values. Up till now we have been thinking about analysis which look at variables (names) but a different way to look at this is based on values, If we think of instructions calculating values, and uses being uses of values we can picture a graph called the data flow graph showing how values move through a program

ssa

in SSA we change our IR so that every variable has exactly one definition in the program (each variable is assigned only once). The name SSA means statically there is only a single assignment per variable.

The SSA Philosophy

In addition to a language form, SSA is also a philosophy! It can fundamentally change the way you think about programs. In the SSA philosophy:

definitions == variables
instructions == values
arguments == data flow graph edges

In LLVM, for example, instructions do not refer to argument variables by name—an argument is a pointer to defining instruction.

Static means in the text, not in the execution.

an example

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
B0["0: i = 0
    1: s = 0"]
B1["2: x = m
    3: s = s + x
    4: i = i +4
    5: if i < n go to B0"]
B0 --> B1
B1 --> B1

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
B0["0: i = 0
    1: s = 0"]
B1["2: x = m
    3: s = s + x
    4: i = i +4
    5: if i < n go to B0"]
B0 --> B1
B1 --> B1

variable i has two static assignments 0 and 4, so this program is not in SSA

Variable s has two static assignments, x has one static assignment but x has lots of dynamic assignments (when the program executes)

straight line code

We call a program without branches a piece of straight line code.

    @main {
      a: int = const 4;
      b: int = const 2;
      a: int = add a b;
      b: int = add a b;
      print b;
    }

. . .

Its easy to see how to convert straight line code into ssa

    @main {
      a.1: int = const 4;
      b.1: int = const 2;
      a.2: int = add a.1 b.1;
      b.2: int = add a.2 b.1;
      print b.2;
    }

pseudo code for one basic block

for each variable a: 
    Count[a] = 0 
    Stack[a] = [0]

rename_basic_block(B): 
    for each instruction S in block B:
        for each use of a argument x in S: 
            i = top(Stack[x]) 
            replace the use of x with x_i
            
        for each variable a that S defines (a dest)
            count[a] = Count[a] + 1 
            i = Count[a]             
            push i onto Stack[a]             
            replace definition of a with a_i

We don’t need the stack here but we will need it later.

Of course, things will get a little more complicated when there is control flow. And because real machines are not SSA, using separate variables (i.e., memory locations and registers) for everything is bound to be inefficient.

The idea in SSA is to convert general programs into SSA form, do all our optimization there, and then convert back to a standard mutating form before we generate backend code.

phi-Nodes

Just renaming assignments will quickly run into problems. Consider this program:

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
B0[".b0
    a: int = const 47;
    br cond .left .right;"]
left["a: int = add a a;
    jmp .exit;"]
right["a: int = mul a a;
        jmp .exit;"]
exit["print a;"]
B0 --> left
B0 --> right
left --> exit
right --> exit

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
B0[".b0
    a: int = const 47;
    br cond .left .right;"]
left["a: int = add a a;
    jmp .exit;"]
right["a: int = mul a a;
        jmp .exit;"]
exit["print a;"]
B0 --> left
B0 --> right
left --> exit
right --> exit

Which “version” of a should we use in the print statement?

phi nodes

To match the expressiveness of unrestricted programs, SSA adds a new kind of instruction: a phi-node.

phi-nodes are flow-sensitive copy instructions: they get a value from one of several variables, depending on which incoming CFG edge was most recently taken to get to them.

phi nodes in Bril

In Bril, a phi-node appears as a phi instruction:

a.4: int = phi .left a.2 .right a.3;

The phi instruction chooses between any number of variables, and it picks between them based on labels. If the program most recently executed a basic block with the given label, then the phi instruction takes its value from the corresponding variable.

back to the example

You can write the above program in SSA like this:

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
B0[".b0
    a: int = const 47;
    br cond .left .right;"]
left["a: int = add a a;
    jmp .exit;"]
right["a: int = mul a a;
        jmp .exit;"]
exit["print a;"]
B0 --> left
B0 --> right
left --> exit
right --> exit

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
B0[".b0
    a: int = const 47;
    br cond .left .right;"]
left["a: int = add a a;
    jmp .exit;"]
right["a: int = mul a a;
        jmp .exit;"]
exit["print a;"]
B0 --> left
B0 --> right
left --> exit
right --> exit

    @main(cond: bool) {
    .entry:
        a.1: int = const 47;
        br cond .left .right;
    .left:
        a.2: int = add a.1 a.1;
        jmp .exit;
    .right:
        a.3: int = mul a.1 a.1;
        jmp .exit;
    .exit:
        a.4: int = phi .left a.2 .right a.3;
        print a.4;
    }

Bril in SSA

Bril has an SSA extension It adds support for a phi instruction. Beyond that, SSA form is just a restriction on the normal expressiveness of Bril—if you solemnly promise never to assign statically to the same variable twice, you are writing “SSA Bril.”

The reference interpreter has built-in support for phi, so you can execute your SSA-form Bril programs without fuss.

Converting to SSA - Very simple scheme

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph LR
X["Block X
   a = 
   b = 
   if s > b"]
Y["Block Y
  b = a"]
Z["Block Z
ret b"]
X --> Y
Y--> Z
X --> Z

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph LR
X["Block X
   a = 
   b = 
   if s > b"]
Y["Block Y
  b = a"]
Z["Block Z
ret b"]
X --> Y
Y--> Z
X --> Z

Where do we need phi-functions?

Which variables

. . .

phi At the merge (join) node

variable b

conditions

conditions: phi-function for variable b at node z

There is a block x containing a definition of b
There is a block y (with y ≠ x) containing a definition of b
There is a nonempty path Pxz of edges from x to z
There is a nonempty path Pyz of edges from y to z
Paths Pxz and Pyz do not have any node in common other than z, and…
The node z does not appear within both Pxz and Pyz prior to the end, though it may appear in one or the other.

scheme part 2

this is iterative since when we add a phi, we are creating a new defintion, which may add new phi-functions

When we find nodes X,Y,Z that match these steps and z does not contain a phi function for b, insert a phi

While really expensive this will work

diagram

using dash for path

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
a["x:x="]
b["y:x="]
c[join]
d
a-.-> c
b-.-> c
c-.->d

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
a["x:x="]
b["y:x="]
c[join]
d
a-.-> c
b-.-> c
c-.->d

We could have complex flow - including loops on the paths

reminder dominators

while dom is changing 
for vertex in cfg 
   dom[vertex] =

while dom is changing 
for vertex in cfg 
   dom[vertex] =  {vertex} + ...

if b has multiple preds, and a dominates all of them, a dom b

while dom is changing 
for vertex in cfg 
   dom[vertex] =  {vertex} + Intersection( dom(p) for p a pred of vertex)

fast methods for inserting phi’s

The method for this has two steps

insert phi instructions where needed (do not add subscripts yet)
in a second pass insert all the numbers

to ssa

To convert to SSA, we want to insert phi-nodes whenever there are distinct paths containing distinct definitions of a variable. We don’t need phi-nodes in places that are dominated by a definition of the variable. So what’s a way to know when control reachable from a definition is not dominated by that definition?

The dominance frontier!

recall the dominance frontier

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
A-->B 
A--> F
B-->C
B--> D
C--> E
D--> E
E--> F

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
A-->B 
A--> F
B-->C
B--> D
C--> E
D--> E
E--> F

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TD
A--> B
A--> F
B--> C
B-->D
B--> E

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TD
A--> B
A--> F
B--> C
B-->D
B--> E

block	A	B	C	D	E
frontier	empty	F	E	E	F

a block can be in its own dom frontier

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
A--> B
B--> A
B--> C

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
A--> B
B--> A
B--> C

why: A dom B, but B does not dom A. so A is in the dom frontier of A

an almost linear method

We do it in two steps.

insert phi-nodes:
rename variables:

placing Phi functions

let b be a block with a def of a variable v, if b has multiple defs of v, use the last one

What is the first block following v that can be reached by a different def of v

in blocks dominated by b, b’s def must have been executed, (other defs of v in a dominated block may overwrite it)

we need to place a phi function for b at the start of all blocks in the dom frontier of b.

after we add phi functions to S where S = df(b) we have more defs, so we need to add phi’s in the dom frontier of all the blocks in S

example 1

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
N["v=1"]
M
M2["v=2"]
Z["M"]
N--> M
M-->Z
M2--> Z

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
N["v=1"]
M
M2["v=2"]
Z["M"]
N--> M
M-->Z
M2--> Z

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
N["v1=1"]
M
M2["v2=2"]
Z["M:v3= phi(v1,v2)"]
N--> M
M-->Z
M2--> Z

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
N["v1=1"]
M
M2["v2=2"]
Z["M:v3= phi(v1,v2)"]
N--> M
M-->Z
M2--> Z

a loop

::: {.columns}

::: {.column}

graph TD
 V["v=init"]
 Z{"z:v = v+1"}
 V --> Z
 Z -->Z

 graph TD
 V["v=init"]
 Z{"z:v = v+1"}
 V --> Z
 Z -->Z

:::

::: {.column}

graph TD
 V["v1=init"]
 Z{"z:v2 = phi(v1,v3)\nv3 = v2+1"}
 V --> Z
 Z -->Z

 graph TD
 V["v1=init"]
 Z{"z:v2 = phi(v1,v3)\nv3 = v2+1"}
 V --> Z
 Z -->Z

:::

iterative placement

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TD
B1[v=1]
B2[v=2]
B3
B4[v=3]
B5
B1--> B3
B2--> B3
B3--> B5
B4--> B5

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TD
B1[v=1]
B2[v=2]
B3
B4[v=3]
B5
B1--> B3
B2--> B3
B3--> B5
B4--> B5

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TD
B1[v1=1]
B2[v2=2]
B3["v3=phi(v1,v2)"]
B4[v4=3]
B5["v5=phi(v3,v4)"]
B1--> B3
B2--> B3
B3--> B5
B4--> B5

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TD
B1[v1=1]
B2[v2=2]
B3["v3=phi(v1,v2)"]
B4[v4=3]
B5["v5=phi(v3,v4)"]
B1--> B3
B2--> B3
B3--> B5
B4--> B5

phi placement

for each block b in the cfg 
  for each var v defined in b
    add block to the set defs(v)  ## blocks that contain an assignment to v 

  W = Defs[v]
    while W is not empty
      remove a node n from w
         for block in DF[n]:  # Dominance frontier.
           Add a phi-node to block,
             unless we have done so already.
           Add block to W (because it now writes to v),
             unless it's already in there.

an example

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
N1["1:x = 1"]
N2["2:"]
N3["3:x= 2"]
N4["4:"]
N5["5:x=3"]
N6[6:x=4]
N7[7:]
N1--> N2
N1--> N3
N2--> N4
N3--> N4
N4--> N5
N5-->  N4
N5--> N6
N6--> N7
N6--> N5

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB
N1["1:x = 1"]
N2["2:"]
N3["3:x= 2"]
N4["4:"]
N5["5:x=3"]
N6[6:x=4]
N7[7:]
N1--> N2
N1--> N3
N2--> N4
N3--> N4
N4--> N5
N5-->  N4
N5--> N6
N6--> N7
N6--> N5

initially w = {1,3,5,6}
process DF(1) = empty
process DF(3) = 4, add 4 to w and add a phi function for x to 4
process DF(5) = 4,5 no need to add 5 to w, add phi for x to 5
process DF(6) = 5
process DF(4) = 4

add phi’s to blocks 4 and 5

rename variables:

# allocate a stack and a counter for each variable
for each V a variable 
  c[v] = 0
  s[v] = empty stack
  search(entry)

search(n):
  for each instr i in n:
     if instr is not a phi
         replace every variable in the rhs of instr by vi where i = top(s[v])
         if instr has a dest v
           i = C(v)
            replace v by new vi, push i onto s[v]
            increment c[v]

  for each y a successor of n
     j = which pred (y,n)
     for each phi function pinstr in Y replace the jth opernmad of pinstr by vi where 
        i = top(s(v)
  
  for each Y a child of n in the dominator tree 
      call search(Y)

an example

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9[L9: goto l3]

L10["l10: ret j"]

L0--> L3

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7

L5--> L9
L7 --> L9
L9 --> L3

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9[L9: goto l3]

L10["l10: ret j"]

L0--> L3

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7

L5--> L9
L7 --> L9
L9 --> L3

What is the dominator tree?

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9[L9: goto l3]

L10["l10: ret j"]

L0--> L3

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7
L5 --> L9
L7 -.-> L9
L9 --> L3

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9[L9: goto l3]

L10["l10: ret j"]

L0--> L3

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7
L5 --> L9
L7 -.-> L9
L9 --> L3

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB 
L0 --> L3 
L3--> L4
L3 --> L10
L4--> L5 
L4 --> L9
L4 --> L7

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB 
L0 --> L3 
L3--> L4
L3 --> L10
L4--> L5 
L4 --> L9
L4 --> L7

dominance frontiers

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9[L9: goto l3]

L10["l10: ret j"]

L0--> L3 

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7
L5 --> L9
L7 -.-> L9
L9 --> L3

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9[L9: goto l3]

L10["l10: ret j"]

L0--> L3 

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7
L5 --> L9
L7 -.-> L9
L9 --> L3

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB 
L0 --> L3 
L3--> L4
L3 --> L10
L4--> L5 
L4 --> L9
L4 --> L7

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TB 
L0 --> L3 
L3--> L4
L3 --> L10
L4--> L5 
L4 --> L9
L4 --> L7

add phi nodes

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9[L9: goto l3]

L10["l10: ret j"]

L0--> L3

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7
L5 --> L9
L7 --> L9
L9 --> L3

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9[L9: goto l3]

L10["l10: ret j"]

L0--> L3

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7
L5 --> L9
L7 --> L9
L9 --> L3

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["j = phi(j,j) 
    k = phi(k,k) 
   L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9["j = phi(j,j)
   k = phi(k,k)
  L9: goto l3"]

L10["l10: ret j"]

L0--> L3

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7
L5 --> L9
L7 --> L9
L9 --> L3

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
L0["L0: i = 1
   L1: j = 1
   L2: k = 0"]

L3["j = phi(j,j) 
    k = phi(k,k) 
   L3: if j <20 go to l4 else l10"]

L4["l4: if j < 20 goto l7 else l5"]

L5["l5: j = i
   l6: k = k +1"]


L7["l7: j = k
  l8: k = k +2"]

L9["j = phi(j,j)
   k = phi(k,k)
  L9: goto l3"]

L10["l10: ret j"]

L0--> L3

L3--> L4
L3 --> L10

L4 --> L5
L4 --> L7
L5 --> L9
L7 --> L9
L9 --> L3

The arity of phi-functions

Could we have a phi-function in a node with only one predecessor?

could we have a phi-function wit more then two arguments?

This algorithm computes what is called minimal SSA form which is not so mimimal since it can leave dead assignments

doing dead code elimination pruned ssa form

Getting out of ssa

Compilers that use the SSA form usually contain a step, before the generation of actual assembly code, in which phi functions are replaced by ordinary instructions. Normally these instructions are simple copies.

an example

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
 A0["io =
     j0 = 
     k0 ="]
A1["i1 =
   j1 =
   k1 = "]
A2["i2 = phi(i0, i1)
   j2 = phi(j0, j1)
   k2 = phi(k0, k1)
   ...
    = i2
    = j2 
    = k2"]

    A0 --> A2
    A1--> A2

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
 A0["io =
     j0 = 
     k0 ="]
A1["i1 =
   j1 =
   k1 = "]
A2["i2 = phi(i0, i1)
   j2 = phi(j0, j1)
   k2 = phi(k0, k1)
   ...
    = i2
    = j2 
    = k2"]

    A0 --> A2
    A1--> A2

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
 B0["io =
     j0 = 
     k0 ="]
B1["i1 =
   j1 =
   k1 = "]
B2["
   ...
    = i2
    = j2 
    = k2"]
    B0 --"i2 = i0
       j2 = j0
       k2 = k0"--> B2
    B1 --"i2 = i1
          j2 = j1
          k2 = k1"--> B2

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TD
 B0["io =
     j0 = 
     k0 ="]
B1["i1 =
   j1 =
   k1 = "]
B2["
   ...
    = i2
    = j2 
    = k2"]
    B0 --"i2 = i0
       j2 = j0
       k2 = k0"--> B2
    B1 --"i2 = i1
          j2 = j1
          k2 = k1"--> B2

we cannot put instructions on edges, but we can add to prev block

critical edges

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
A0["L1:
   a0 =
   b0 =
   if A0 > b0"]
A1["b1 = a0"]
A2["l2:
b2 = phi(b1,b0)"]
A0 --> A1
A1 --> A2
A0 --> A2

%%{init: {"flowchart": {"htmlLabels": false}} }%%
graph TB
A0["L1:
   a0 =
   b0 =
   if A0 > b0"]
A1["b1 = a0"]
A2["l2:
b2 = phi(b1,b0)"]
A0 --> A1
A1 --> A2
A0 --> A2

b2 = b0?

The placement of the copy b2 = b0 is not simple, because the edge that links L2 to L5 is critical. A critical edge connects a block with multiple successors to a block with multiple predecessors. This should remind you of adding a preheader to a loop

critical edge splitting

We can solve this problem by doing critical edge splitting. This CFG transformation consists in adding an empty basic block (empty, except by – perhaps – a goto statement) between each pair of blocks connected by a critical edge.

making use of ssa form

Our previous analyses always used a (variable, program point), but in ssa these are the same

dead code elimination in ssa

while there is some variable v with no uses and the statement that defines v has no other side effects, delete the statement that defines v from the program.

we need a counter for each variable (or each instruction)

walk the program once increment the counter each time the variable is used

while there exists v, such that counter[v] = 0 remove the instruction that defined v, e.g., “v = E for each variable x used in E decrement counter[x]

sparse constant prop

we define a partial order on constats, any > all constants > undefined and define the intersection of two states as the common parent

with each variable we have an abstract state (like a value number)

v  = const c   ==> v state is const 

v = id q      ==> v state is the state of  q 

v = v0 op v1  ==> if both are constants v = c0 op c1

             ==> if one is any, v's state is any

v = phi(v0,..vn) ==> v's state is the intersection of the states of v0,..,vn

What order do we process nodes?

because the program is in ssa form we can do the nodes in dominator tree order, then before processing any instruction that is not a phi, we will have processed all the arguments

B0: x0  = input 
    a0 = 1 
    c0 = a0 +10
    if a0 < c0 go to b1

B1: a1 phi(a1,a2 )
    b0 = x0 * a1
    print b0 
    a2 = a1 +1 
    go to b1

walking the dominator tree b0 -> b1

B0: x0  = input 
    a0 = 1 
    c0 = a0 +10
    if a0 < c0 go to b1

B1: a1 phi(a0,a2 )
    b0 = x0 * a1
    print b0 
    a2 = a1 +1 
    go to b1

B0:
x0 - any 
a0 - 1 
c0 - 11 (folding the constant)
a0 < c0  skip
B1:
a1 -  1 (only one input defined)
b0  - any
a2 -  2
update the uses of a2 - the phi
a1 -  any 

update the uses of a1 
no change

Converting from SSA

Eventually, we need to convert out of SSA form to generate efficient code for real machines that don’t have phi-nodes and do have finite space for variable storage.

basic algorithm

The basic algorithm is pretty straightforward. If you have a phi-node:

v = phi .l1 x .l2 y;

Then there must be assignments to x and y (recursively) preceding this statement in the CFG.

The paths from x to the phi-containing block and from y to the same block must “converge” at that block. So insert code into the phi-containing block’s immediate predecessors along each of those two paths: one that does v = id x and one that does v = id y. Then you can delete the phi instruction.

extra copies

This basic approach can introduce some redundant copying. (Take a look at the code it generates after you implement it!) Non-SSA copy propagation optimization can work well as a post-processing step. For a more extensive take on how to translate out of SSA efficiently, see “Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency” by Boissinot et al.

overlap

its possible that an optimization can give overlapping phi-functions

b0 
  x1 = 1
  y1 = 2
B1 
x2 = phi(x1,x3)
y2 = phi(y1, y3)
  z = x2
  x3 = y2
  y3= z
  if() go to b1

optimize it

b0 
  x1 = 1
  y1 = 2
B1 
x2 = phi(x1, y2)
y2 = phi(y1, x2)
  if() go to b1

lost the temp (this is called the swap problem)

if we add copies x2 = y3 y2 = x2 (uses the wrong value of x2)

phi nodes execute all at once - not one at a time

Some SSA slides from Todd Mowry at CMU

Other Formats