9. Basic Blocks and Traces

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 valuation which restricts optimization (eg, if s1 and s2 do not interfere to each other, we would like to be able to switch SEQ(s1,s2) into SEQ(s2,s1) because it may result to a more efficient program.

The abovementioned problems can be eliminated in two phases:

1.

transforming IR trees into a list of canonical trees, and

2.

transforming unrestricted CJUMPs into CJUMPs that are followed by their false target label.

An IR is a canonical tree if it does not contain SEQ or ESEQ and the parent node of each CALL node is either an EXP or a MOVE(TEMP(t),...) node. The idea is that we transform an IR in such a way that all ESEQs are pulled up in the IR and become SEQs at the top of the tree. At the end, we are left with nested SEQs at the top of the tree, which are eliminated to form a list of statements. For example, the IR:

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))

To handle function calls, we store the function results to a new register:

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).

Also, if there is a JUMP(L) followed by a LABEL(L), we remove the JUMP.