TC-S Dead Code Elimination Samples

Note

The goal of dead code elimination is to remove unused temporaries from the code.

For those examples, we will compare the result of the conversion back to LIR with and without dead code elimination performed during the SSA stage.

unused_variable.tig

let
    var used := "toto"
    var unused := "tata"
in
    print(used)
end

Without Dead Code Elimination

$ tc -e --ssa -L unused_variable.tig
/* == Low Level Intermediate representation. == */
label l0
	"toto"
label l1
	"tata"
# Routine: _main
label main
# Prologue
# Body
seq
  label l6
  move
    temp t1.0
    const 0
  move
    temp t0.0
    const 0
  move
    temp t0.1
    name l0
  move
    temp t1.1
    name l1
  sxp
    call
      name print
      temp t0.1
    call end
  label l2
seq end
# Epilogue
label end
$ echo $?
0

With Dead Code Elimination

$ tc -e --dead-code-elimination --ssa -L unused_variable.tig
/* == Low Level Intermediate representation. == */
label l0
	"toto"
label l1
	"tata"
# Routine: _main
label main
# Prologue
# Body
seq
  label l6
  move
    temp t1.0
    const 0
  move
    temp t0.0
    const 0
  move
    temp t0.1
    name l0
  sxp
    call
      name print
      temp t0.1
    call end
  label l2
seq end
# Epilogue
label end
$ echo $?
0

double_branch.tig

let
    var b := 2
    var a := if 1 then (b := 3; b) else (b := 4; 0)
in
    print_int(a)
end

If a temporary is never used, it is simply removed from the final output, along with its definition.

Note

Note that we keep the definition of tx.0 as a fallback after deletion. An example of this behavior is presented below.

Without Dead Code Elimination

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

$ echo $?
0

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

With Dead Code Elimination

$ tc -e --dead-code-elimination --rename-variables --bbflowgraph-dump double_branch_dce.tig

$ echo $?
0

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

---

Warning

Before removing a function call, we need to make sure that the method is pure.

A pure method is one without side effects, meaning that they do not write in memory outside the function’s scope.

For exemple, functions that perform I/O operations are ones that produce side effects, as they write somewhere in memory. In Tiger, IO builtins such as print, print_int, getchar, etc. produce side effects and have been dealt with (reordered/extracted) during canonicalization (see TC-6, Translating to the Low Level Intermediate Representation).

In the following example, we declare a unused variable val that is initialized to an array, with some IO call in its initialization.

io_side_effects.tig

let
  type arr = array of int
  var val := (
    print("Where DCE?"); /* Handled during canonicalization. */
    arr[10] of 42        /* Calls `init_array', side effects procedure! */
  )
in
end

What can be seen after canonicalization is that:

1. The IO call (print, returning nothing), has been correctly handled and extracted, so we have nothing to deal with IO calls during dead code elimination,

2. However, the variable initialization value, implicitly calling init_array, will be handled during dead code elimination.

LIR IO Side Effects

$ tc -L io_side_effects.tig
/* == Low Level Intermediate representation. == */
label l0
	"Where DCE?"
# Routine: _main
label main
# Prologue
move
  temp t1
  temp fp
move
  temp fp
  temp sp
move
  temp sp
  binop sub
    temp sp
    const 4
# Body
seq
  label l4
  move
    temp t2
    temp fp
  sxp
    call
      name print
      name l0
    call end
  move
    temp t0
    call
      name init_array
      const 10
      const 42
    call end
  move
    mem
      temp t2
    temp t0
  label l1
seq end
# Epilogue
move
  temp sp
  temp fp
move
  temp fp
  temp t1
label end
$ echo $?
0

impure_method.tig

let
    type arr = array of int
    var my_array := arr[10] of 0
    
    function f(arr : arr, i : int) : int = (arr[i] := 42; arr[i])
    
    var a := 0
in
    a := f(my_array, 0)
end

Since the function shown above writes in the array that is defined outside the function’s scope, we consider it to be impure. Therefore, the function call and its associated variable are not removed even if they are not used.

With Dead Code Elimination

$ tc -e --dead-code-elimination --ssa -L impure_method.tig
/* == Low Level Intermediate representation. == */
# Routine: f
label l0
# Prologue
move
  temp t4
  temp fp
move
  temp fp
  temp sp
move
  temp sp
  binop sub
    temp sp
    const 4
move
  mem
    temp fp
  temp i0
move
  temp t2.0
  temp i1
move
  temp t3.0
  temp i2
# Body
seq
  label l5
  move
    temp rv
    const 0
  move
    mem
      binop add
        temp t2.0
        binop mul
          temp t3.0
          const 4
    const 42
  move
    temp rv
    mem
      binop add
        temp t2.0
        binop mul
          temp t3.0
          const 4
  label l1
seq end
# Epilogue
move
  temp sp
  temp fp
move
  temp fp
  temp t4
label end

# Routine: _main
label main
# Prologue
# Body
seq
  label l6
  move
    temp t5.0
    const 0
  move
    temp t1.0
    const 0
  move
    temp t0.0
    const 0
  move
    temp t0.1
    call
      name init_array
      const 10
      const 0
    call end
  move
    temp t1.1
    temp t0.1
  move
    temp t5.2
    call
      name l0
      temp fp
      temp t1.1
      const 0
    call end
  label l2
seq end
# Epilogue
label end
$ echo $?
0

In case of a pure method like the one below, the function call is removed from the final output.

pure_method.tig

let
    function f() : int = 42
    var a := f()
in
end

With Dead Code Elimination

$ tc -e --dead-code-elimination --ssa -L pure_method.tig
/* == Low Level Intermediate representation. == */
# Routine: f
label l0
# Prologue
move
  temp t0
  temp fp
move
  temp fp
  temp sp
move
  temp sp
  binop sub
    temp sp
    const 4
move
  mem
    temp fp
  temp i0
# Body
seq
  label l5
  move
    temp rv
    const 0
  move
    temp rv
    const 42
  label l1
seq end
# Epilogue
move
  temp sp
  temp fp
move
  temp fp
  temp t0
label end

# Routine: _main
label main
# Prologue
# Body
seq
  label l6
  move
    temp t1.0
    const 0
  label l2
seq end
# Epilogue
label end
$ echo $?
0