Previous    Next

Basic Blocks and Traces

ca-non-i-cal: reduced to the simplest or clearest schema possible

Webster's Dictionary


The trees generated by the semantic analysis phase must be translated into assembly or machine language. The operators of the Tree language are chosen carefully to match the capabilities of most machines. However, there are certain aspects of the tree language that do not correspond exactly with machine languages, and some aspects of the Tree language interfere with compiletime optimization analyses. For example, it's useful to be able to evaluate the subexpressions of an expression in any order. But the subexpressions of Tree.exp can contain side effects - ESEQ and CALL nodes that contain assignment statements and perform input/output. If tree expressions did not contain ESEQ and CALL nodes, then the order of evaluation would not matter. Some of the mismatches between Trees and machine-language programs are

Why does the Tree language allow ESEQ and two-way CJUMP, if they are so troublesome? Because they make it much more convenient for the Translate (translation to intermediate code) phase of the compiler. We can take any tree and rewrite it into an equivalent tree without any of the cases listed above. Without these cases, the only possible parent of a SEQ node is another SEQ; all the SEQ nodes will be clustered at the top of the tree. This makes the SEQs entirely uninteresting; we might as well get rid of them and make a linear list of Tree.Stms. The transformation is done in three stages: First, a tree is rewritten into a list of canonical trees without SEQ or ESEQ nodes; then this list is grouped into a set of basic blocks, which contain no internal jumps or labels; then the basic blocks are ordered into a set of traces in which every CJUMP is immediately followed by its false label. Thus the module Canon has these tree-rearrangement functions:

package Canon;
public class Canon {
 static public Tree.StmList linearize(Tree.Stm s);
public class BasicBlocks {
 public StmListList blocks;
 public Temp.Label done;
 public BasicBlocks(Tree.StmList stms);
StmListList(Tree.StmList head, StmListList tail);
public class TraceSchedule {
 public TraceSchedule(BasicBlocks b);
 public Tree.StmList stms;

Linearize removes the ESEQs and moves the CALLs to top level. Then BasicBlocks groups statements into sequences of straight-line code. Finally, TraceSchedule orders the blocks so that every CJUMP is followed by its false label.

JaVaScreenshot Previous    Next