TC-5 Optimizing Cascading If
Optimize the number of jumps needed to compute nested if,
using translate::Ix. A plain use of translate::Cx
is possible, but less efficient.
Consider the following sample.
boolean.tig
if if 11 < 22 then 33 < 44 else 55 < 66 then print("OK\n")
A naive implementation will probably produce too many cjump
instructions.
tc --hir-naive -H boolean.tig
$ 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
$ echo $?
0
tc --hir-naive -H boolean.tig > boolean-1.hir
$ tc --hir-naive -H boolean.tig > boolean-1.hir
$ echo $?
0
havm --profile boolean-1.hir
$ havm --profile boolean-1.hir
OK
/* Profiling. */
fetches from temporary : 2
fetches from memory : 0
binary operations : 0
function calls : 1
stores to temporary : 2
stores to memory : 0
jumps : 2
conditional jumps : 3
/* Execution time. */
number of cycles : 19
$ echo $?
0
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 the following HIR.
tc -H boolean.tig
$ 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
$ echo $?
0
tc -H boolean.tig > boolean-2.hir
$ tc -H boolean.tig > boolean-2.hir
$ echo $?
0
havm --profile boolean-2.hir
$ havm --profile boolean-2.hir
OK
/* Profiling. */
fetches from temporary : 0
fetches from memory : 0
binary operations : 0
function calls : 1
stores to temporary : 0
stores to memory : 0
jumps : 1
conditional jumps : 2
/* Execution time. */
number of cycles : 13
$ echo $?
0
If you don’t yet want to implement procedure calls, here is an example with only integers:
boolean-no-print.tig
if if 11 < 22 then 33 < 44 else 55 < 66 then 77 else 88
tc -H boolean-no-print.tig
$ tc -H boolean-no-print.tig
/* == High Level Intermediate representation. == */
# Routine: _main
label main
# Prologue
# Body
seq
seq
seq
cjump lt
const 11
const 22
name l3
name l4
label l3
cjump lt
const 33
const 44
name l0
name l1
label l4
cjump lt
const 55
const 66
name l0
name l1
seq end
label l0
sxp
const 77
jump
name l2
label l1
sxp
const 88
label l2
seq end
sxp
const 0
seq end
# Epilogue
label end
$ echo $?
0
tc -H boolean-no-print.tig > boolean-no-print.hir
$ tc -H boolean-no-print.tig > boolean-no-print.hir
$ echo $?
0
havm --profile boolean-no-print.hir
$ havm --profile boolean-no-print.hir
/* Profiling. */
fetches from temporary : 0
fetches from memory : 0
binary operations : 0
function calls : 1
stores to temporary : 0
stores to memory : 0
jumps : 1
conditional jumps : 2
/* Execution time. */
number of cycles : 13
$ echo $?
0