Chapter 5 Lowering

Conceptually, we’re reducing operator sequences

3+4*5

to nested expressions in the parser

3+(4*5)

and we’re mapping those to temporary storage

val y = 4*5
3+y

before assigning specific storage locations.

While these steps aren’t all made explicit, it is useful to think about how one language feature can be expressed using another one that is “simpler” or more general.

5.1 Single vs. Multi-Pass

Now that we have variables, do we still need to support code generation for nested expressions?

Idea – take an expression like:

3+(4*5)

Why don’t we translate (“desugar”, “lower”) it into:

val x0 = 3
val x1 = 4
val x2 = 5
val x3 = x1 * x2
x0 + x3

This would save us the code generation logic for nested expressions.

For one, this code does not have the same space behavior. Variable x3 is unnecessary, the stack translation would overwrite x1. We can fix this by translating as follows:

val x0 = 3
val x1 = {
  val x1 = 4
  val x2 = 5
  x1 * x2
}
x0 + x1

Or equivalently (note that this isn’t legal Scala, we’d have to write val x = 1; { val x = 2; ..} to achieve shadowing):

val x0 = 3
val x1 = 4
val x2 = 5
val x1 = x1 * x2
x0 + x1

This should have the same rough overall behavior (register usage and all), but will it actually generate the same assembly?

Exercise: will this generate the same code using the compilation logic we have implemented? If not, what would be required to make it produce the same code?

Lesson: lowering is a good strategy for adding new features to a language quickly, by translating them away in early phases of the compiler. But this simplicity doesn’t come for free. The price is often either less efficient execution or increased effort in analysis and optimization to recognize a pattern from the special case in the general one, and improve it.

5.2 Revised Implementation

On the other hand, there are opportunities to generate better code by making the structure of the program more regular.

If we translate

3+(4*5)

to lets that are uniformly named based on their nesting depth (de Bruijn levels)

val x0 = 3
val x1 = {
  val x1 = 4
  val x2 = 5
  x1 * x2
}
x0 + x1

then we can directly assign storage locations

memory(0) = 3
memory(1) = {
  memory(1) = 4
  memory(2) = 5
  memory(1) * memory(2)
}
memory(0) + memory(1)

and flatten the code

memory(0) = 3
memory(1) = 4
memory(2) = 5
memory(1) *= memory(2)
memory(0) + memory(1)

leading to a result that is as efficient as our single-pass compilation.

And in fact we get better code now for expressions that mix variables and expressions! Example:

val x = 4 * 5
3 + x

Compare before and after (before has additional load/store logic).

** Exercise: implement these lowering steps as independent transformations**

** Exercise: fuse the transformations back together, to derive a single-pass “destination passing style” transformation. Compare with what we had so far**