TC-S Static Single Assignment Samples

Note

SSA form requires all temporaries to be statically defined once. After renaming, a number is added at the end of each temporary. When there is no branching path, this renaming method is analogous to the one described in TC-R, Unique Identifiers.

two_variables.tig

let
    var a := 1
    var b := 2
in
    a + b
end

Without SSA Form

$ tc -eL two_variables.tig
/* == Low Level Intermediate representation. == */
# Routine: _main
label main
# Prologue
# Body
seq
  label l2
  move
    temp t0
    const 1
  move
    temp t1
    const 2
  sxp
    binop add
      temp t0
      temp t1
  label l0
seq end
# Epilogue
label end
$ echo $?
0

After SSA Form

$ tc -e --ssa -L two_variables.tig
/* == Low Level Intermediate representation. == */
# Routine: _main
label main
# Prologue
# Body
seq
  label l2
  move
    temp t1.0
    const 0
  move
    temp t0.0
    const 0
  move
    temp t0.1
    const 1
  move
    temp t1.1
    const 2
  sxp
    binop add
      temp t0.1
      temp t1.1
  label l0
seq end
# Epilogue
label end
$ echo $?
0

Note

One of the important things to notice is the apparition of a new definition for each temporary: tx.0. These new definitions are here to account for variables defined on branching paths, where they might be used before their assignment.

redefinition.tig

let
    var a := 1
in
    a := 42
end

tc -eL redefinition.tig

$ tc -eL redefinition.tig
/* == Low Level Intermediate representation. == */
# Routine: _main
label main
# Prologue
# Body
seq
  label l2
  move
    temp t0
    const 1
  move
    temp t0
    const 42
  label l0
seq end
# Epilogue
label end
$ echo $?
0

After SSA Form

$ tc -e --ssa -L redefinition.tig
/* == Low Level Intermediate representation. == */
# Routine: _main
label main
# Prologue
# Body
seq
  label l2
  move
    temp t0.0
    const 0
  move
    temp t0.1
    const 1
  move
    temp t0.2
    const 42
  label l0
seq end
# Epilogue
label end
$ echo $?
0

---

Now we can check programs with branching paths.

Warning

As SSA form is an abstract form, it cannot be visualized directly in the LIR output. This is why we have 4 steps to output:

1. LIR before SSA,

2. BasicBlock Flow Graph in SSA form,

3. abstract Phi-Nodes visualization in SSA form,

4. from SSA form back to LIR.

if.tig

let
    var a := 1
in
    print_int(if 1 then a else a + 1)
end

Before SSA

$ tc -eL if.tig
/* == Low Level Intermediate representation. == */
# Routine: _main
label main
# Prologue
# Body
seq
  label l5
  move
    temp t0
    const 1
  cjump ne
    const 1
    const 0
    name l0
    name l1
  label l1
  move
    temp t1
    binop add
      temp t0
      const 1
  label l2
  sxp
    call
      name print_int
      temp t1
    call end
  jump
    name l3
  label l0
  move
    temp t1
    temp t0
  jump
    name l2
  label l3
seq end
# Epilogue
label end
$ echo $?
0

SSA form BasicBlock Graph dump

$ tc -e --rename-variables --bbflowgraph-dump if.tig

$ echo $?
0

if.main._main.basic-block-flow.gv

SSA form abstract Phi-Nodes visualization

$ tc -e --ssa-debug if.tig
label main
seq
  label l5
  move
    temp t0.1
    const 1
  cjump ne
    const 1
    const 0
    name l0
    name l1
  label l1
  move
    temp t1.3
    binop add
      temp t0.1
      const 1
  jump
    name l2
  label l2
  move
    temp t1.2
    phi(t1.1, t1.3)
  sxp
    call
      name print_int
      temp t1.2
    call end
  jump
    name l3
  label l0
  move
    temp t1.1
    temp t0.1
  jump
    name l2
  label l3
seq end
$ echo $?
0

As we can see, a Phi-Node was inserted at the end of the two branching paths of the condition. The temporary t1.2, which contains the result of the Phi-Node, is then used in the print_int call.

Translating back to LIR

$ tc -e --ssa -L if.tig
/* == Low Level Intermediate representation. == */
# Routine: _main
label main
# Prologue
# Body
seq
  label l5
  move
    temp t1.0
    const 0
  move
    temp t0.0
    const 0
  move
    temp t0.1
    const 1
  cjump ne
    const 1
    const 0
    name l0
    name l1
  label l1
  move
    temp t1.3
    binop add
      temp t0.1
      const 1
  move
    temp t1.2
    temp t1.3
  label l2
  sxp
    call
      name print_int
      temp t1.2
    call end
  jump
    name l3
  label l0
  move
    temp t1.1
    temp t0.1
  move
    temp t1.2
    temp t1.1
  jump
    name l2
  label l3
seq end
# Epilogue
label end
$ echo $?
0

When translating back to LIR, the Phi-Node is replaced by a series of assignments.

Let’s see another example.

while.tig

let
    var a := 1
in
    while a = 1 do
        a := 2;
    print_int(a)
end

Before SSA

$ tc -eL while.tig
/* == Low Level Intermediate representation. == */
# Routine: _main
label main
# Prologue
# Body
seq
  label l5
  move
    temp t0
    const 1
  label l1
  cjump eq
    temp t0
    const 1
    name l2
    name l0
  label l0
  sxp
    call
      name print_int
      temp t0
    call end
  jump
    name l3
  label l2
  move
    temp t0
    const 2
  jump
    name l1
  label l3
seq end
# Epilogue
label end
$ echo $?
0

SSA form BasicBlock Graph dump

$ tc -e --rename-variables --bbflowgraph-dump while.tig

$ echo $?
0

while.main._main.basic-block-flow.gv

SSA form abstract Phi-Nodes visualization

$ tc -e --ssa-debug while.tig
label main
seq
  label l5
  move
    temp t0.1
    const 1
  jump
    name l1
  label l1
  move
    temp t0.2
    phi(t0.1, t0.3)
  cjump eq
    temp t0.2
    const 1
    name l2
    name l0
  label l0
  sxp
    call
      name print_int
      temp t0.2
    call end
  jump
    name l3
  label l2
  move
    temp t0.3
    const 2
  jump
    name l1
  label l3
seq end
$ echo $?
0

Note

In the case of a loop, the Phi-Node is inserted before the condition. This makes t0.2 use the value of a temporary not yet defined.

This behavior makes sense when translating back to LIR.

Translating back to LIR

$ tc -e --ssa -L while.tig
/* == Low Level Intermediate representation. == */
# Routine: _main
label main
# Prologue
# Body
seq
  label l5
  move
    temp t0.0
    const 0
  move
    temp t0.1
    const 1
  move
    temp t0.2
    temp t0.1
  label l1
  cjump eq
    temp t0.2
    const 1
    name l2
    name l0
  label l0
  sxp
    call
      name print_int
      temp t0.2
    call end
  jump
    name l3
  label l2
  move
    temp t0.3
    const 2
  move
    temp t0.2
    temp t0.3
  jump
    name l1
  label l3
seq end
# Epilogue
label end
$ echo $?
0

Since a Phi-Node is replaced by a series of assignments, the first one is made at its location. In case of a loop, assigning the value before the condition and reassigning it in the body is the expected behavior.

In case of definitions in only one branch, the Phi-Node uses the definition of tx.0.

branching_definition.tig

let
    var a := if 1 then (
        let var b := 42 in b end
    ) else 10
in
    print_int(a)
end

tc -e --rename-variables --bbflowgraph-dump branching_definition.tig

$ tc -e --rename-variables --bbflowgraph-dump branching_definition.tig

$ echo $?
0

branching_definition.main._main.basic-block-flow.gv