Copyright © 2004
Robert W. Hasker

Ch. 8

• issue: IR Trees easy to generate from grammar, but not a direct match to code to be generated
  • example: CJUMP has two branches, but instructions usually fall-through in false case
• solution: transform the IR trees so they do not contain such cases
  • code for function: list of basic blocks
  • basic block: sequence of instructions with no internal jumps or labels
    • basic block (generally) starts with a label, ends with a jump
  • represent list as a trace
    • trace: sequence of basic blocks in which every CJUMP is immediately followed by its false label
• Module Canon
  • operations to reorganize IR trees
    • linearize: "remove ESEQs and move CALLS to top level"
    • class BasicBlocks: "groups statements into sequences of straight-line code"
    • class TraceSchedule: order blocks so every CJump followed by its false label

Canonical Trees

• canonical: reduced/simplest form
• canonical trees for our project:
  • no SEQ or ESEQ
  • all CALLs embedded in either EXP or MOVE(TEMP t, ...)
• removing ESEQ
  • Figure 8.1
  • identity 1: obvious
  • identity 2: distribution across ESEQ's (also obvious)
  • identity 3: moving a statement from within an operation
  • identity 4: special case of #3 when s does not affect e1
    • how to tell when the expression (e1) and the statement (s) commute?
    • conservative answer: expression is a constant, statement is a no-op
• rewrite rules
  • issue: how to implement the above
  • reorder operation:
    • takes list of expressions, returns pair (statement, expression-list) where statement is done first, then expression-list evaluated for the result
  • implementation:
    • Extend Stm, Exp classes with two operations:
      • abstract public ExpList kids();
        • returns list of child expressions in each statement
      • abstract public Stm build(ExpList kids);
        • returns a new statement comprising given expressions (after reordering)
    • Define these operations for each subclass
      • BINOP from p. 167 (also in assignment 4 code); key operations:

          public class BINOP extends Exp { ...
            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);
            }
          }
        

      • MOVE (p. 168):

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

        • note destination treated as an expression that needs to be reordered only if destination is a computed memory address rather than a temporary
• call: return result in register "RV"
  • but BINOP(CALL(...), CALL(...)) would cause problems
    • need temporary for result of CALL:

          CALL(fun, args) → ESEQ(MOVE(TEMP t, CALL(fun, args)), TEMP t)
      

• linear list of statements
  • constructed by traversing IR tree

Conditional Branches

• transform conditional branches so false branch can fall through, true branch jumps
  1. construct basic blocks
  2. order basic blocks into a "trace"
• basic blocks
  • always entered at top and exit at bottom:
    • first statement is a label
    • last statement is a JUMP or CJUMP
    • no other labels or jumps
  • algorithm: scan sequence of instructions for the above pattern
  • simplification: put label done at end of procedure (right before epilog) and JUMP(NAME done) at the end of the last block
• traces
  • basic blocks can be reordered at will
  • want block representing false branch of each CJUMP to follow the jump
  • speed-up: given JUMP(label), move block for label right after the JUMP
  • algorithm (implemented as Canon.TraceSchedule):
    1. start with some block, follow chain of jumps, marking each block as added to chain
    2. when reach block who's successors are all marked, end trace
    3. goto 1
• Finishing up
  • optimization usually done at basic block level
  • for simplicity, MiniJava will flatten traces into one long sequence
  • adjustments:
    • given CJUMP(..., t, f) where t immediately follows the jump, switch false and true labels and negate condition
    • given CJUMP(cond, a, b, t, f) where neither t nor f follows the jump, replace by following:

              CJUMP(cond, a, b, t, f')
              label f'
              jump f
      

      • makes processing more consistent
  • remove unconditional jumps which are immediately followed by their label
• issue: optimizing traces
  • which is a better implementation of a loop?

            LABEL(NAME(test))
            CJUMP(>, i, N, done, body)
            label(body)
            loop body statements
            JUMP(NAME(test))
            LABEL(done)
    

    or

            JUMP(NAME(test))
            LABEL(body)
            loop body statements
            LABEL(test)
            CJUMP(<=, i, N, body, done)
            LABEL(done)
    

  • Second version eliminates a jump, reducing pipeline flushes
  • in general, may want to consider instruction scheduling

Review

• canonical trees: code = sequence of statements
• basic blocks
• traces