Chapter 8
Basic Blocks and Traces

powered by FreeFind

Modified: 

RESOURCES

Download Chapters 7 and 8 software

Test package contains test.java that can be used to test your understanding of Chapter 7 and 8. The file contains an example of:

The file can be edited to verify your understanding of the input and results of each phase.

Directions:

  1. Unzip to directory: Chap8
  2. At command prompt, change to Chap8 directory.
  3. Compile by:  javac -classpath . Test\test.java
  4. Execute by: java -cp . Test.test

OVERVIEW

IR trees must eventually be translated into assembly or machine code. IR does not correspond precisely to any architecture's assembly language so translation problems are to be expected and some IR interferes with optimization.

Two types of IR nodes and some examples of translation difficulties:

Exp

ESEQ(s, e) - Statement s is evaluated with possible side-effects then e is evaluated for results.

CALL(f,l) - Applies function f to argument list l.

Stm

SEQ( s1, s2 ) - Statement s1 followed by statement s2 where s1 and s2 are branches on the IR tree.

CJUMP( o, e1, e2, t, f ) - Compare evaluation of e1 and e2 using relation operator o; if result is true jump to address t else jump to address f.

 

                                SEQ      
                          /               \
                         SEQ            LABEL(F)
                   /                \
              SEQ                   SEQ   
           /         \             /           \
LABEL(while)  CJUMP   LABEL(T)    SEQ
                                               /        \
                                        MOVE       JUMP(while)
               
   

Some Mismatches

Following are useful in building trees of parent and child nodes but cause problems when translating to linear assembly code.

Remember that a nested call generates assembly code not the result of the evaluation. Functions can produce side-effects so that order code executed determines order of side-effects produced.

 

Transform tree to list

      +
    /   \
   *     -      linearization to RPN:  a b * c d -
 /  \   /  \
a   b c    d

 

Canon: Translation of tree to linear list package. Three stages:

  1. rewrite tree into a list of canonical trees without SEQ or ESEQ nodes.
  2. group list into set of basic blocks with no internal jumps or labels.
  3. order basic blocks into set of traces in which every CJUMP is followed by its false label.
package Canon;
public class Canon{
     static public Tree.StmList linearize(Tree.Stm s)  // removes ESEQs and move CALLs to top level
}

public class BasicBlocks {                                     // groups statements into sequences of straightline code
   public StmListList blocks;
   public Temp.Label done;
   public BasicBlocks(Tree.StmList stms)
}

public class StmListList {
   public Tree.StmList head;
   public StmListList tail;
   public StmListList(Tree.StmList h, StmListList t) {head=h; tail=t;}
}

public class TraceSchedule {                                // orders blocks so every CJUMP followed by its false label
   public Tree.StmList stms;
   BasicBlocks theBlocks;
   public TraceSchedule(BasicBlocks b)
}

 

Exercise - Why are the three operations on IR trees important to code production?

 

Example - The following is a simplified example of the AST to IR translation and linearized results; note that the AST node is not used so that the details of the if statment could be more simply presented.

The following is the template for translating AST to IR tree. The Ex expression and Nx statement objects of the if statement are translated by the unEx() and unNx() methods.

AST to IR AIfStatement IR tree Linearized
public Stm caseAIfStatement( AIfStatement node ) {
  Label T = new Label("T");
  Label F = new Label("F");
  Label D = new Label("D");
  Ex exp = new Ex(CONST(0));
  Nx stmT = new Nx(MOVE(TEMP(new Temp(1)), CONST(1)));
  Nx stmF = new Nx(MOVE(TEMP(new Temp(3)), CONST(3)));

  return
    SEQ(
      SEQ(
        SEQ(
          SEQ(
            CJUMP(CJUMP.EQ, exp.unEx(), CONST(1),T,F),
            SEQ(
              LABEL(T),
              stmT.unNx()
            )
          ),
          JUMP(D)
        ),
        SEQ(
          LABEL(F),
          stmF.unNx()
        )
      ),
      LABEL(D)
  );
}		 SEQ(
  SEQ(
    SEQ(
      SEQ(
        CJUMP(EQ,
          CONST 0,
          CONST 1,
          T,F),
        SEQ(
          LABEL T,
          MOVE(
            TEMP t1,
            CONST 1)
        )
      ),
      JUMP(NAME D)
    ),
    SEQ(
      LABEL F,
      MOVE(
        TEMP t3,
        CONST 3)
    )
  ),
  LABEL D
)		 CJUMP(EQ,
  CONST 0,
  CONST 1,
  T,F)
LABEL T
MOVE(
  TEMP t1,
  CONST 1)
JUMP(NAME D)
LABEL F
MOVE(
  TEMP t3,
  CONST 3)
LABEL D

 

8.1 CANONICAL TREES

  1. have no SEQ or ESEQ
  2. parent of each CALL is either EXP(...) or MOVE(TEMP t, ... )

TRANSFORMATIONS ON ESEQ

Remove ESEQs because make different orders of evaluating subtrees yield different result.

ESEQ(s, e) - Statement s is evaluated with possible side-effects then e is evaluated for results.

SEQ( s1, s2 ) - Statement s1 followed by statement s2

  1. Obvious since side-effect of s1 and s2 still occur before evaluation of e.
     
  2. Recall that ESEQ(s, e) where e is the result. In each the side-effect of s occurs before e1 or e2 are evaluated (assuming left-to-right evaluation)
     
  3. The order in which s is evaluated must not change; after e1 evaluated and before e2. Solution is to save evaluation of e1 in temporary, perform s for side-effects, use temporary and potentially side-effected e2.
     
  4. Special commutative case of 3. Can be used when s does not side-effect any locations referenced by e1 and neither perform I/O since the order of s and e1 is changed.

    Not easy to determine in general so conservatively will only commute when e is CONST or NAME; neither can be side-effected or do I/O.

Example - Rewriting using identities moves ESEQ to top of IR tree.

Before After Linearized
BINOP(
  PLUS,
  CONST(1),
  ESEQ(
     MOVE(
        TEMP(t2),
        CONST(2)
      ),
      TEMP(t2)
  )
)		 ESEQ(
  MOVE(
     TEMP (t1),
     CONST(1)
  ),
  ESEQ(
    MOVE(
       TEMP (t2),
       CONST(2)
    ),
    BINOP(
       PLUS,
       TEMP(t1),
       TEMP(t2)
    )
  )
)		 MOVE(
  TEMP t2,
  CONST 1
)
 

MOVE(
  TEMP t3,
  CONST 2
)


BINOP(
  PLUS,
  TEMP t2,
  TEMP t3
)

 

Example - One goal of rewriting is to eliminate ESEQ but preserve the results.

Before After
MOVE(
 TEMP t0,
 ESEQ(
   MOVE(
     TEMP t0,
     CONST 4
   ),
   CONST 3
 )
)		 MOVE(
  TEMP t0,
  CONST 4
)
MOVE(
  TEMP t0,
  CONST 3
)

 

GENERAL REWRITING RULES

Three possible rewrites of the expressions to remove ESEQ by moving s to left of e1 and e2:

[e1, e2, ESEQ( s, e3 )]

  1. e1 and e2 commute, not affected by side-effects of s: (s; [e1, e2, e3])
  2. e2 does not commute: SEQ( MOVE(t1, e1), SEQ(MOVE( t2, e2), s));   (s; [TEMP(t1), TEMP(t2), e3])
  3. e2 does but e1 does not commute: SEQ( MOVE(t1, e1), s);   (s; [TEMP(t1), e2, e3])

Exercise - Do both e1 and e2 need to be in TEMPs in case 2?

 

reorder function takes a list of expressions and returns (statement, expression-list) as illustrated in Figure 8.1 of the text.

The reorder method code illustrates:

 static StmExpList reorder(ExpList exps) {            // Remove ESEQs
     if (exps==null) return nopNull;
     else {
       Exp a = exps.head;
       if (a instanceof CALL) {                               // parent of each CALL is either EXP(...) or MOVE(TEMP t, ... )
         Temp.Temp t = new Temp.Temp();
         Exp e = ESEQ(MOVE( TEMP(t), a), TEMP(t));
         return reorder(new ExpList(e, exps.tail)); 
       } else {
             ESEQ aa = do_exp(a);                          // translate expression a into ESEQ( s, e )
             StmExpList bb = reorder(exps.tail);
             if (commute(bb.stm, aa.exp))            // Stms on left, expressions on right
                  return new StmExpList( SEQ(aa.stm, bb.stm), new ExpList(aa.exp, bb.exps));
             else {
               Temp.Temp t = new Temp.Temp();
               return new StmExpList(
                                      SEQ(aa.stm,
                                             SEQ(MOVE(TEMP(t), aa.exp), bb.stm)),
                                             new ExpList(TEMP(t), bb.exps));
             }
       }
     }
 }

 

Algorithm

Each Tree kind will require:

  1. kids - sub-expression extraction method to pull each type of expression apart for reordering
  2. build - sub-expression insertion method to put the reordered expression back together

The basic idea of two above methods is to pull ESEQs out from right-to-left using  and insert the reordering to the left

Each Exp or Stm  subclass must implement kids and build. Some examples:

package Tree;
abstract public class Exp {
  abstract public ExpList kids();
  abstract public Exp build(ExpList kids);
}
 		 package Tree;
abstract public class Stm {
  abstract public ExpList kids();
  abstract public Stm build(ExpList kids);
}
 
public class BINOP extends Exp {
  public int binop;
  public Exp left, right;
  public BINOP(int b, Exp l, Exp r) { binop=b; left=l; right=r;  }
  public final static int PLUS=0, MINUS=1, MUL=2, DIV=3,
                              AND=4,OR=5,LSHIFT=6,RSHIFT=7,
                              ARSHIFT=8,XOR=9;
  public ExpList kids() {return new ExpList(left, new ExpList(right,null));}
  public Exp build(ExpList kids) {
                            return new BINOP(binop, kids.head, kids.tail.head);
   }
}		 public class CONST extends Exp {
  public int value;
  public CONST(int v) {value=v;}
  public ExpList kids() {return null;}
  public Exp build(ExpList kids) {return this;}
public class CALL extends Exp {
  public Exp func;
  public ExpList args;
  public CALL(Exp f, ExpList a) {func=f; args=a;}
  public ExpList kids() {return new ExpList(func,args);}
  public Exp build(ExpList kids) { return new CALL(kids.head, kids.tail); }		 public class MOVE extends Stm {
  public Exp dst, src;
  public MOVE(Exp d, Exp s) { dst=d; src=s; }
  public ExpList kids() {
    if (dst instanceof MEM)
        return new ExpList(((MEM)dst).exp, new ExpList(src,null));
    else return new ExpList(src,null);
  }
  public Stm build(ExpList kids) {
    if (dst instanceof MEM)
      return new MOVE(new MEM(kids.head), kids.tail.head);
    else return new MOVE(dst, kids.head);
  }
public class ESEQ extends Exp {
public Stm stm;
public Exp exp;
public ESEQ(Stm s, Exp e) {stm=s; exp=e;}
public ExpList kids() {
            throw new Error("kids() not applicable to ESEQ");
}
public Exp build(ExpList kids) {
            throw new Error("build() not applicable to ESEQ");
}		  

MOVE must determine whether left-hand side (destination) is MEM, which then acts as a source. (see bottom p. 167)

Note that an ExpList is a list of expressions with an Exp head and ExpList tail.

package Tree;
public class ExpList {
  public Exp head;
  public ExpList tail;
  public ExpList(Exp h, ExpList t) {head=h; tail=t;}
}		 ExpList a = new ExpList(CONST(1),null);

ExpList b = new ExpList(CONST(2), a );

b = [CONST(2), [CONST(1), null] ]

Example

public class BINOP extends Exp {
  public int binop;
  public Exp left, right;
  public BINOP(int b, Exp l, Exp r) { binop=b; left=l; right=r;  }
  public final static int PLUS=0, MINUS=1, MUL=2, DIV=3,
                              AND=4,OR=5,LSHIFT=6,RSHIFT=7,
                              ARSHIFT=8,XOR=9;
  public ExpList kids() {
       return new ExpList(left, new ExpList(right,null));
  }
  public Exp build(ExpList kids) {
       return new BINOP(binop, kids.head, kids.tail.head);
   }
}		 BINOP e = BINOP( PLUS, e1, e2 )
  • binop = PLUS
  • left = e1
  • right = e2

e.kids() returns

  • el = ExpList(e1, new ExpList(e2, null))

e.build( el ) returns

  • BINOP( PLUS, e1, e2 )

 

MOVING CALLS TO TOP LEVEL

Because all calls return result in TEMP(RV) register and CALL nodes can be sub-expressions:

BINOP( PLUS, CALL(...), CALL(...) )

the first call overwrites the second. We saw that on the 386 the intermediate result could be saved by pushing, however the IR has no PUSHs and POPs, only TEMPs. Rewriting:

BINOP( PLUS, ESEQ( MOVE(TEMP(tnew), CALL(...)), TEMP(tnew)), CALL(...) )

reorder replaces each CALL(...) not preceded by a MOVE by:

ESEQ( MOVE(TEMP(tnew), CALL(...)), TEMP(tnew) )

where TEMP(tnew) holds the result of the CALL expression.

 

A LINEAR LIST OF STATEMENTS

The result of processing the IR is a tree with SEQs near the root, never under another type of node.

linearize method repeatedly applies the rule:

SEQ( SEQ( a, b ), c ) = SEQ( a, SEQ( b, c ) )

to convert a tree into a linearized expression of the form:

SEQ( s1, SEQ( s2, SEQ ( s3, ..., SEQ(sn-1, sn)...))

which is equivalent to a list of statements without ESEQ or SEQ:

s1, s2, s3, ..., sn-1, sn

Rewrite SEQ rule is implemented below:

static Tree.StmList linear(Tree.SEQ s, Tree.StmList l) {
  return linear(s.left,linear(s.right,l));
}

static Tree.StmList linear(Tree.Stm s, Tree.StmList l) {
  if (s instanceof Tree.SEQ) return linear((Tree.SEQ)s, l);
  else return new Tree.StmList(s,l);
}

static public Tree.StmList linearize(Tree.Stm s) {
  return linear(do_stm(s), null);
}

Example - The following is a simplified example of the AST to IR translation and linearized results; note that the AST node is not used so that the details of the if statement could be more simply presented.

The following is the template for translating AST to IR tree. The Ex expression and Nx statement objects of the if statement are translated by the unEx() and unNx() methods

AST to IR AIfStatement IR tree Linearized
public Stm caseAIfStatement( AIfStatement node ) {
  Label T = new Label("T");
  Label F = new Label("F");
  Label D = new Label("D");
  Ex exp = new Ex(CONST(0));
  Nx stmT = new Nx(MOVE(TEMP(new Temp(1)), CONST(1)));
  Nx stmF = new Nx(MOVE(TEMP(new Temp(3)), CONST(3)));

  return
    SEQ(
      SEQ(
        SEQ(
          SEQ(
            CJUMP(CJUMP.EQ, exp.unEx(), CONST(1),T,F),
            SEQ(
              LABEL(T),
              stmT.unNx()
            )
          ),
          JUMP(D)
        ),
        SEQ(
          LABEL(F),
          stmF.unNx()
        )
      ),
      LABEL(D)
  );
}		 SEQ(
  SEQ(
    SEQ(
      SEQ(
        CJUMP(EQ,
          CONST 0,
          CONST 1,
          T,F),
        SEQ(
          LABEL T,
          MOVE(
            TEMP t1,
            CONST 1)
        )
      ),
      JUMP(NAME D)
    ),
    SEQ(
      LABEL F,
      MOVE(
        TEMP t3,
        CONST 3)
    )
  ),
  LABEL D
)		 CJUMP(EQ,
  CONST 0,
  CONST 1,
  T,F)
LABEL T
MOVE(
  TEMP t1,
  CONST 1)
JUMP(NAME D)
LABEL F
MOVE(
  TEMP t3,
  CONST 3)
LABEL D

 

8.2 TAMING CONDITIONAL BRANCHES - ANALYZING THE CONTROL FLOW

CJUMP is a two-way branch, convenient for translating into trees but most machines have only single-branch, branching on true or falling through to the next instruction.

For more direct translation to machine code, CJUMP's will be arranged so that each is followed immediately by the false branch. Recall that the CJUMP is defined as:

CJUMP( condition, e1, e2, T, F )

Consider the following while pseudo-code:

while( e1 <= e2) do
    statement(s)
endwhile

There are a number of possible implementations; the following all compute the same result but the two at right have the false immediately following the CJUMP, more easily translated into machine code:

LABEL( while )
  CJUMP (<=, e1, e2, do, endwhile)

LABEL( do )
  statement(s)
  JUMP( while )

LABEL(endwhile)
 		 LABEL( while )
  CJUMP (<=, e1, e2, do, endwhile)

LABEL( endwhile )
  JUMP( end )

LABEL( do )
  statement(s)
  JUMP( while )

LABEL( end )

 LABEL( while )
  CJUMP (>, e1, e2, endwhile, do)

LABEL( do )
  statement(s)
  JUMP( while )

LABEL( endwhile )

 

Rewrite

The rearrangement of each CJUMP( condition, T, F ) can then be directly implemented on a machine as a conditional branch to T.

Requires:

  1. forming sequences of statements into groupings called basic blocks,
  2. ordering basic blocks into flow sequence.

BASIC BLOCKS

Basic blocks are statement sequences that are always entered at the beginning and exited at the end:

The idea behind rewriting as basic blocks is that blocks can be rearranged without changing execution result. The purpose of the rearrangement is to rewrite a general two-branch CJUMP into a one that is always followed by the false branch (i.e. fall through).

Example

IR Linearization Basic Blocks
MOVE(
  TEMP t0,
  ESEQ(
    MOVE(
      TEMP t0,
      CONST 4
    ),
    CONST 3
  )
)		 MOVE(
  TEMP t0,
  CONST 4
)
MOVE(
  TEMP t0,
  CONST 3
)		 LABEL L1
  MOVE(
     TEMP t0,
     CONST 4
  )
  MOVE(
     TEMP t0,
     CONST 3
  )
JUMP(NAME L0)

Exercise - Circle which part, if any of the following are basic blocks. Are execution results the same for the two?

  MOVE( e1, e2 )
LABEL( L1 )
  BINOP(PLUS, e1, e2)
  CJUMP(<, e1, e3, L1, L2)       
LABEL( L2 )  
  MOVE( e1, e2 )
  JUMP( L1 )
  MOVE( e1, e2 )

LABEL( L0 )
  MOVE( e1, e2 )
  JUMP( L1 )
LABEL( L2 )  
  MOVE( e1, e2 )
  JUMP( L1 )
LABEL( L1 )
  BINOP(PLUS, e1, e2)
  CJUMP(<, e1, e3, L1, L2)
  MOVE( e1, e2 )

 

Algorithm for Basic Blocks

Keep in mind that:

Scan each method-body sequence of statements, when:

  1. No LABEL at beginning, create one
  2. LABEL is found:
    • end the current block
      • if current block does not end with JUMP or CJUMP the add a JUMP to LABEL
    • start a new block with LABEL
  3. JUMP or CJUMP is found:
    • end the current block with the JUMP or CJUMP
    • start a new block
      • if new block does not start with a LABEL, create one for the start

Translation - The general approach can be seen by example, the following left-hand side is transformed to the right-hand side:

MOVE(
  TEMP t0,
  CONST 4
)

LABEL L1
  MOVE(
    TEMP t0,
    CONST 4)
  JUMP(
    NAME L0)

  JUMP(
    NAME L0)
  MOVE(
    TEMP t0,
    CONST 4)
LABEL L0

LABEL L2
  JUMP(
    NAME L0)
LABEL L3
  MOVE(
    TEMP t0,
    CONST 4)
  JUMP(
     NAME L0)
LABEL L0
  JUMP(
     NAME L1)

LABEL L0
  MOVE(
    TEMP t0,
    CONST 4)
  JUMP(
    NAME L0)

LABEL L0
  MOVE(
    TEMP t0,
    CONST 4)
  JUMP(
    NAME L0)

LABEL L0
MOVE(
TEMP t1,
CONST 4)
CJUMP(LT,
TEMP t0,
CONST 4,
L1,L2)
JUMP(
NAME L0)

LABEL L0
  MOVE(
    TEMP t1,
    CONST 4)
  CJUMP(LT,
    TEMP t0,
    CONST 4,
    L1,L2)
LABEL L4
  JUMP(
    NAME L0)

Exercise - Apply the basic blocks algorithm to the following sequences:

  MOVE( e1, e2 )
LABEL( L1 )
  BINOP(PLUS, e1, e2)
  CJUMP(<, e1, e3, L1, L2)       
LABEL( L2 )  
  MOVE( e1, e2 )
  JUMP( L1 )
  MOVE( e1, e2 )

LABEL( L0 )
  MOVE( e1, e2 )
  JUMP( L1 )
LABEL( L2 )  
  MOVE( e1, e2 )
  JUMP( L1 )
LABEL( L1 )
  BINOP(PLUS, e1, e2)
  CJUMP(<, e1, e3, L1, L2)
  MOVE( e1, e2 )

 

Scan each method-body sequence of statements, when:

  1. No LABEL at beginning, create one
  2. LABEL is found:
    • end the current block
      • if current block does not end with JUMP or CJUMP the add a JUMP to LABEL
    • start a new block with LABEL
  3. JUMP or CJUMP is found:
    • end the current block with the JUMP or CJUMP
    • start a new block
      • if new block does not start with a LABEL, create one for the start

 

BasicBlocks.Java

package Canon;

public class BasicBlocks {
  public StmListList blocks;
  public Temp.Label done;
  private StmListList lastBlock;
  private Tree.StmList lastStm;

  public BasicBlocks(Tree.StmList stms) {
    done = new Temp.Label();
    mkBlocks(stms);
  }

  void mkBlocks(Tree.StmList l) {
    if (l==null) return;
    else if (l.head instanceof LABEL) {                      // Already has LABEL
            lastStm = new Tree.StmList(l.head,null);
            if (lastBlock==null)
                lastBlock= blocks= new StmListList(lastStm,null);
            else
                lastBlock = lastBlock.tail = new StmListList(lastStm,null);
            doStms(l.tail);
          }                                                                // No LABEL at start, insert LABEL
          else mkBlocks(new Tree.StmList( LABEL(new Temp.Label()), l));
    }
  }

  private void doStms(Tree.StmList l) {
    if (l==null)                                                          // if none at end of block add JUMP
        doStms(new Tree.StmList( JUMP(done), null));
    else if (l.head instanceof  JUMP || l.head instanceof  CJUMP) {
            addStm(l.head);                                          // head is a JUMP or CJUMP
            mkBlocks(l.tail);                                           // followed by LABEL block JUMP
          }
          else if (l.head instanceof LABEL)                     
                    doStms(new Tree.StmList( JUMP(((LABEL)l.head).label),  l));
                else {
                    addStm(l.head);
                    doStms(l.tail);
                }
  }

  private void addStm(Tree.Stm s) {
    lastStm = lastStm.tail = new Tree.StmList(s,null);
  }
}
package Tree;
public class StmList {
   public Stm head;
   public StmList tail;
   public StmList(Stm h, StmList t) {head=h; tail=t;}
}
package Canon;
public class StmListList {
  public Tree.StmList head;
  public StmListList tail;
  public StmListList(Tree.StmList h, StmListList t) {head=h; tail=t;}
}

 

TRACES

A trace is a sequence of statements that could be consecutively executed during the execution of the program.

The purpose of the trace phase is rearrange CJUMPS so that all are immediately followed by their false branch; allowing for conversion into single conditional branch machine code.

Original Basic Blocks Trace
LABEL WHILE
  MOVE(TEMP t0, CONST 4)
  CJUMP(LT, TEMP t1, CONST 4,T,F)
LABEL T
  JUMP(NAME WHILE)
LABEL F		 LABEL WHILE
  MOVE(TEMP t0, CONST 4)
  CJUMP(LT, TEMP t1, CONST 4,T,F)
LABEL T
  JUMP(NAME WHILE)
LABEL F
  JUMP(NAME L1)		 LABEL WHILE
  MOVE(TEMP t0, CONST 4)
  CJUMP(LT,TEMP t1,CONST 4,T,F)
LABEL F
  JUMP(NAME L1)
LABEL T
  JUMP(NAME WHILE)
LABEL L1
LABEL b1
  MOVE(TEMP t0,CONST 0)
  JUMP(NAME b4)
LABEL b6
  MOVE(TEMP t1,CONST 1)
LABEL b4
  MOVE(TEMP t2,CONST 2)
  JUMP(NAME b6)		 LABEL b1
  MOVE(TEMP t0,CONST 0)
  JUMP(NAME b4)
LABEL b6
  MOVE(TEMP t1,CONST 1)
  JUMP(NAME b4)
LABEL b4
  MOVE(TEMP t2,CONST 2)
  JUMP(NAME b6)		 LABEL b1
  MOVE(TEMP t0,CONST 0)
LABEL b4
  MOVE(TEMP t2,CONST 2)
LABEL b6
  MOVE(TEMP t1,CONST 1)
  JUMP(NAME b4)
LABEL L0
LABEL b1
  MOVE(TEMP t0,CONST 0)
  JUMP(NAME b4)
LABEL b6
  MOVE(TEMP t1,CONST 1)
LABEL b4
  MOVE(TEMP t2,CONST 2)
  CJUMP(LT,TEMP t10,CONST 10,b7,b3)
LABEL b7
  MOVE(TEMP t7,CONST 7)
LABEL b3
  MOVE(TEMP t3,CONST 3)		 LABEL b1
  MOVE(TEMP t0,CONST 0)
  JUMP(NAME b4)
LABEL b6
  MOVE(TEMP t1,CONST 1)
  JUMP(NAME b4)
LABEL b4
  MOVE(TEMP t2,CONST 2)
  CJUMP(LT,TEMP t10,CONST 10,b7,b3)
LABEL b7
  MOVE(TEMP t7,CONST 7)
  JUMP(NAME b3)
LABEL b3
  MOVE(TEMP t3,CONST 3)
  JUMP(NAME L0)		 LABEL b1
  MOVE(TEMP t0,CONST 0)
LABEL b4
  MOVE(TEMP t2,CONST 2)
  CJUMP(LT,TEMP t10,CONST 10,b7,b3)
LABEL b3
  MOVE(TEMP t3,CONST 3)
  JUMP(NAME L0)
LABEL b6
  MOVE(TEMP t1,CONST 1)
  JUMP(NAME b4)
LABEL b7
  MOVE(TEMP t7,CONST 7)
  JUMP(NAME b3)
LABEL L0

Exercise - Comment on the effect of the basic block and the trace applications to each row above.

Exercise - The following illustrates three traces that produce the same results; which is the more efficient? Why?

LABEL test
  CJUMP(GT,TEMP t10,CONST 10,body,done)
LABEL body
  MOVE(TEMP t7,CONST 7)
  JUMP(NAME test)
LABEL done
  MOVE(TEMP t9,CONST 9)		 LABEL test
  CJUMP(GT,TEMP t10,CONST 10,body,done)
LABEL body
  MOVE(TEMP t7,CONST 7)
  JUMP(NAME test)
LABEL done
  MOVE(TEMP t9,CONST 9)
  JUMP(NAME L0)		 LABEL test
  CJUMP(GT,TEMP t10,CONST 10,body,done)
LABEL done
  MOVE(TEMP t9,CONST 9)
  JUMP(NAME L0)
LABEL body
  MOVE(TEMP t7,CONST 7)
  JUMP(NAME test)
LABEL L0

 

Exercise - The following illustrates three traces that produce the same results; which is the more efficient? Why?

LABEL(test)
  CJUMP (>, e1, e2, done, body)

LABEL(body)
  statement(s)
  JUMP( test )

LABEL(done)
  statement(s)		 LABEL( test )
  CJUMP (<=, e1, e2, body, done)

LABEL(done)
  statement(s)
  JUMP( join )

LABEL(body)
  statement(s)
  JUMP( test )

LABEL( join )

   JUMP( test )

LABEL(body)
  statement(s)

LABEL( test )
  CJUMP (<=, e1, e2, body, done)

LABEL(done)
  statement(s)

TraceSchedule.java

package Canon;
 
public class TraceSchedule {
 
  public Tree.StmList stms;
  BasicBlocks theBlocks;
  java.util.Dictionary table = new java.util.Hashtable();
 
  Tree.StmList getLast(Tree.StmList block) {
     Tree.StmList l=block;
     while (l.tail.tail!=null)  l=l.tail;
     return l;
  }
 
  void trace(Tree.StmList l) {
   for(;;) {
     Tree.LABEL lab = (Tree.LABEL)l.head;
     table.remove(lab.label);
     Tree.StmList last = getLast(l);
     Tree.Stm s = last.tail.head;
     if (s instanceof Tree.JUMP) {
            Tree.JUMP j = (Tree.JUMP)s;
            Tree.StmList target = (Tree.StmList)table.get(j.targets.head);
            if (j.targets.tail==null && target!=null) {
               last.tail=target;
               l=target;
            }
            else {
              last.tail.tail=getNext();
              return;
            }
     }
     else
       if (s instanceof Tree.CJUMP) {
            Tree.CJUMP j = (Tree.CJUMP)s;
            Tree.StmList t = (Tree.StmList)table.get(j.iftrue);
            Tree.StmList f = (Tree.StmList)table.get(j.iffalse);
            if (f!=null) {
              last.tail.tail=f;
              l=f;
            }
            else
              if (t!=null) {
                 last.tail.head=new Tree.CJUMP(Tree.CJUMP.notRel(j.relop), j.left,j.right, j.iffalse,j.iftrue);
                 last.tail.tail=t;
                 l=t;
              }
        else {
                Temp.Label ff = new Temp.Label();
                last.tail.head=new Tree.CJUMP(j.relop,j.left,j.right, j.iftrue,ff);
                last.tail.tail=new Tree.StmList(new Tree.LABEL(ff),
                                   new Tree.StmList(new Tree.JUMP(j.iffalse),
                                                                getNext()));
                return;
         }
     }
     else throw new Error("Bad basic block in TraceSchedule");
    }
  }
 
  Tree.StmList getNext() {
      if (theBlocks.blocks==null)
            return new Tree.StmList(new Tree.LABEL(theBlocks.done), null);
      else {
             Tree.StmList s = theBlocks.blocks.head;
             Tree.LABEL lab = (Tree.LABEL)s.head;
             if (table.get(lab.label) != null) {
                trace(s);
                return s;
             }
             else {
               theBlocks.blocks = theBlocks.blocks.tail;
               return getNext();
             }
        }
  }
 
  public TraceSchedule(BasicBlocks b) {
    theBlocks=b;
    for(StmListList l = b.blocks; l!=null; l=l.tail)
       table.put(((Tree.LABEL)l.head.head).label, l.head);
    stms=getNext();
    table=null;
  }       
}