# Linearizing Trees with Control-Flow

Evaluating control-flow in interpreter is easy

• recall the interpreter 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

• 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

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