TC-5 Optimizing Cascading If (The Tiger Compiler Project Assignment)

Optimize the number of jumps needed to compute nested if, using ‘translate::Ix’. A plain use of ‘translate::Cx’ is possible, but less efficient.

if if 11 < 22 then 33 < 44 else 55 < 66 then print("OK\n")

$ tc --hir-naive -H boolean.tig
/* == High Level Intermediate representation. == */
label l7
        "OK\n"
# Routine: _main
label main
# Prologue
# Body
seq
  seq
    cjump ne
      eseq
      seq
        cjump lt
          const 11
          const 22
          name l0
          name l1
        label l0
        move
          temp t0
          eseq
          seq
            move
              temp t1
              const 1
            cjump lt
              const 33
              const 44
              name l3
              name l4
            label l4
            move
              temp t1
              const 0
            label l3
          seq end
            temp t1
        jump
          name l2
        label l1
        move
          temp t0
          eseq
          seq
            move
              temp t2
              const 1
            cjump lt
              const 55
              const 66
              name l5
              name l6
            label l6
            move
              temp t2
              const 0
            label l5
          seq end
            temp t2
        jump
          name l2
        label l2
      seq end
        temp t0
      const 0
      name l8
      name l9
    label l8
    sxp
      call
        name print
        name l7
      call end
    jump
      name l10
    label l9
    sxp
      const 0
    jump
      name l10
    label l10
  seq end
  sxp
    const 0
seq end
# Epilogue
label end

$ tc --hir-naive -H boolean.tig >boolean-1.hir

$ havm --profile boolean-1.hir
error→/* Profiling.  */
error→fetches from temporary : 2
error→fetches from memory    : 0
error→binary operations      : 0
error→function calls         : 1
error→stores to temporary    : 2
error→stores to memory       : 0
error→jumps                  : 2
error→conditional jumps      : 3
error→/* Execution time.  */
error→number of cycles : 19
OK

An analysis of this pessimization reveals that it is related to the computation of an intermediate expression (the value of ‘if 11 < 22 then 33 < 44 else 55 < 66’) later decoded as a condition. A better implementation will produce:

$ tc -H boolean.tig
/* == High Level Intermediate representation. == */
label l0
        "OK\n"
# Routine: _main
label main
# Prologue
# Body
seq
  seq
    seq
      cjump lt
        const 11
        const 22
        name l4
        name l5
      label l4
      cjump lt
        const 33
        const 44
        name l1
        name l2
      label l5
      cjump lt
        const 55
        const 66
        name l1
        name l2
    seq end
    label l1
    sxp
      call
        name print
        name l0
      call end
    jump
      name l3
    label l2
    sxp
      const 0
    label l3
  seq end
  sxp
    const 0
seq end
# Epilogue
label end

$ tc -H boolean.tig >boolean-2.hir

$ havm --profile boolean-2.hir
error→/* Profiling.  */
error→fetches from temporary : 0
error→fetches from memory    : 0
error→binary operations      : 0
error→function calls         : 1
error→stores to temporary    : 0
error→stores to memory       : 0
error→jumps                  : 1
error→conditional jumps      : 2
error→/* Execution time.  */
error→number of cycles : 13
OK

4.14.2.2 TC-5 Optimizing Cascading If

Footnotes

(6)