Motivation:

• elegant and efficient compilation for conditionals
• compilation for more complex control structures

To describe this compilation we introduce an imaginary, big, instruction

branch(c,nThen,nElse)

Here

• c is a potentially complex Java boolean expression
• nThen is label to jump to when c evaluates to true
• nFalse is label to jump to when c evaluates to false

Next, we show how to expand branch(c,nThen,nElse) into actual instructions. This is a recursive process.

[[ if (c) sThen else sElse ]] =
        branch(c,nThen,nElse)
nThen:  [[ sThen ]]
        goto nAfter
nElse:  [[ sElse ]]
nAfter:

[[ while (c) s ]] =

lBegin: branch(c,start,lExit)
start:  [[ s ]]
        goto lBegin
lExit:

branch(!c,nThen,nElse) =
         branch(c,nElse,nThen)

branch(c1 && c2,nThen,nElse) =
         branch(c1,nNext,nElse)
  nNext: branch(c2,nThen,nElse)

Here, nNext is a fresh label.

branch(c1 || c2,nThen,nElse) =

           branch(c1,nThen,nNext)
    nNext: branch(c2,nThen,nElse)

branch(true,nThen,nElse) =
        goto nThen

branch(false,nThen,nElse) =
        goto nElse

Option one:

branch(xN,nThen,nElse) =
  iload_N
  ifeq nElse
  goto nThen

Option two:

branch(xN,nThen,nElse) =
  iload_N
  ifne nThen
  goto nElse

Option one:

branch(e1 R e2,nThen,nElse) =
         [[ e1 ]]
         [[ e2 ]]
         if_cmpR nThen
         goto nElse

Option two:

branch(e1 R e2,nThen,nElse) =
         [[ e1 ]]
         [[ e2 ]]
         if_cmpNegR nElse
         goto nThen

What if we need to compute

x = c

where x,c are boolean?

• What are nThen,nElse labels?

Producing boolean expression on stack:

[[ c ]] = 
        branch(c,nThen,nElse)
nThen:  iconst_1
        goto nAfter
nElse:  iconst_0
nAfter:

Then we can store the value as usual

Note also that we can eliminate the pattern

   goto L
L: 

if it is generated in the process above

We can pick the option that eliminates the jump

We can detect this kind of optimization by looking only at neighboring instructions

• example of 'peephole optimization'

Generated instructions:
-----------------------------------
|   |   |   |   |   |   |   |   |
-----------------------------------
    |               |
    ----------------
            |
       optimizer looks at a 'window' of instructions

Other examples:

• recognize pattern for 'x=x+c', replace with iinc
• recognize copying of boolean variables (b1=b2) - no need for 'branch'
• how to compile this assignment: b1= b2 && b3; (no better than simple scheme, but for larger expressions and simple comparisons we have an improvement)

Further advanced reading

• Compiling with Continuations
• The essence of compiling with continuations