Many computer architectures have instructions that do not exactly
match the IR representations given in the previous sections. For
example, they do not support two-way branching as in
`CJUMP(op,e1,e2,l1,l2)`

. In addition, nested calls, such as
`CALL(f,[CALL(g,[1])])`

, will cause interference between register
arguments and returned results. The nested SEQs, such as
`SEQ(SEQ(s1,s2),s3)`

, impose an order of a evaluation, which
restricts optimization (eg, if `s1`

and `s2`

do not
interfere with each other, we would like to be able to switch
`SEQ(s1,s2)`

with `SEQ(s2,s1)`

because it may result to a
more efficient program.

The problems mentioned above can be eliminated in two phases:

- transforming IR trees into a list of
*canonical trees*, and - transforming unrestricted CJUMPs into CJUMPs that are followed by their false target label.

SEQ(MOVE(NAME(x),ESEQ(MOVE(TEMP(t),CONST(1)),TEMP(t))), JUMP(ESEQ(MOVE(NAME(z),NAME(L)),NAME(z))))is translated into:

SEQ(SEQ(MOVE(TEMP(t),CONST(1)), MOVE(NAME(x),TEMP(t))) SEQ(MOVE(NAME(z),NAME(L)), JUMP(NAME(z))))which corresponds to a list of statements (if we remove the top SEQs):

[ MOVE(TEMP(t),CONST(1)), MOVE(NAME(x),TEMP(t)), MOVE(NAME(z),NAME(L)), JUMP(NAME(z)) ]Here are some rules to make canonical trees:

- ESEQ(s1,ESEQ(s2,e)) = ESEQ(SEQ(s1,s2),e)
- BINOP(op,ESEQ(s,e1),e2) = ESEQ(s,BINOP(op,e1,e2))
- MEM(ESEQ(s,e)) = ESEQ(s,MEM(e))
- JUMP(ESEQ(s,e)) = SEQ(s,JUMP(e))
- CJUMP(op,ESEQ(s,e1),e2,l1,l2) = SEQ(s,CJUMP(op.e1,e2,l1,l2))
- BINOP(op,e1,ESEQ(s,e2)) = ESEQ(MOVE(temp(t),e1),ESEQ(s,BINOP(op,TEMP(t),e2)))
- CJUMP(op,e1,ESEQ(s,e2),l1,l2) = SEQ(MOVE(temp(t),e1),SEQ(s,CJUMP(op,TEMP(t),e2,l1,l2)))
- MOVE(ESEQ(s,e1),e2) = SEQ(s,MOVE(e1,e2))

CALL(f,a) = ESEQ(MOVE(TEMP(t),CALL(f,a)),TEMP(t))

That way expressions, such as `+(CALL(f,a),CALL(g,b))`

, would not
rewrite each others result register.

Now the next thing to do is to transform any CJUMP into a CJUMP whose
false target label is the next instruction after CJUMP. This reflects
the conditional JUMP found in most architectures (ie. ``if condition
then JUMP label''). To do so, we first form *basic blocks* from
the IR tree. A basic block is a sequence of statements whose first
statement is a LABEL, the last statement is a JUMP or CJUMP, and does
not contain any other LABELs, JUMPs, or CJUMPs. That is, we can only
enter at the beginning of a basic block and exit at the end. To solve
the CJUMP problem, we first create the basic blocks for an IR tree and
then we reorganize the basic blocks in such a way that every CJUMP at
the end of a basic block is followed by a block the contains the CJUMP
false target label. A secondary goal is to put the target of a JUMP
immediately after the JUMP. That way, we can eliminate the JUMP (and
maybe merge the two blocks). The algorithm is based on *traces*:
You start a trace with an unmark block and you consider the target of
the JUMP of this block or the false target block of its CJUMP. Then,
if the new block is unmarked, you append the new block to the trace,
you use it as your new start, and you apply the algorithm recursively;
otherwise, you close this trace and you start a new trace by going
back to a point where there was a CJUMP and you choose the true target
this time. You continue until all blocks are marked. This is a greedy
algorithm. At the end, there may be still some CJUMPs that have a
false target that does not follow the CJUMP (this is the case where
this false target label was the target of another JUMP or CJUMP found
earlier in a trace). In that case:

- if we have a CJUMP followed by a true target, we negate the condition and switch the true and false targets;
- otherwise, we create a new block LABEL(L) followed by JUMP(F) and we replace CJUMP(op,a,b,T,F) with CJUMP(op,a,b,T,L).

2002-08-26