LARA

Linearizing Trees with Control-Flow

Evaluating control-flow in interpreter is easy

  • recall the interpreter, as in Labs 01
statement match {
 ...
 case IfStat(cond,sThen,sElse) => {
   interpExpr(e)(cond) match {
     case BoolValue(b) => {
       if (b) {
         interpStats(e, UnitValue, sThen :: stmts1)
       } else {
         interpStats(e, UnitValue, sElse :: stmts1)
       }
     }
     case _ => error("Expected boolean as condition")
   }
 }
 ...
}

One reason it is easy: interpreter works on trees

But machine code and JVM work on instruction sequences

We need to linearize the sequence - decide how to order different subtrees in a sequence

  • the default JVM behavior: go to next instruction
  • for trees we need jump instructions

Different Views of IfThenElse

Java

sBefore
if (e) {
  sThen
} else {
  sElse
}
sAfter

Abstract Syntax Tree

Sequence
|
|--sBefore
|
|---IfThenElse
   /   |     \
  e   sThen  sElse
|
|--sAfter

Flow Graph

(We will learn more on such graphs later)

        sBefore
           |
          _|_
    _____/ e \______
   |true \___/ false|
   |                |
 sThen            sElse
   |                |
   |                |
   ----- sAfter -----

Linearizing graph into a sequence

Using hypothetical conditional branch instruction: branch(thenAddress,elseAddress)

Use 'goto' for unconditional jumps

Note: 'e' can be complex, must translate it first

  • for stack machine: expressions leave the result on stack
  • branching instructions can inspect result from the stack

Symmetric translation:

instruction number instructions
nBefore [ [ sBefore ] ]
[ [ e ] ]
branch(nTrue,nFalse)
someOtherCode
nTrue [ [ sThen ] ]
goto nAfter
someOtherCode
nFalse [ [ sElse ] ]
goto nAfter
someOtherCode
nAfter sAfter

Aligning Blocks to Avoid Jumps

Eliminate branching by chosing where to put translated block:

  • put nTrue right after the branch - one branch target is next instrution
  • put nAfter right after else branch - no need for goto in else branch
instruction number instructions
nBefore [ [ sBefore ] ]
[ [ e ] ]
branchIfFalse(nFalse)
nTrue [ [ sThen ] ]
goto nAfter
nFalse [ [ sElse ] ]
nAfter sAfter