11.2 Expression Translation

Expression lowering turns nested syntax into an explicit evaluation schedule. A source expression such as (a + b) * c says what should be computed; IR must also say where intermediate values live and in which order operations occur.

A common interface is lowerExpr(e) -> Value. Literals return constants, names return loaded values or SSA names, and operators recursively lower their operands before emitting a new instruction.

The AST has already resolved precedence, so the lowerer does not parse operators again. For (a + b) * c, the multiplication node contains an addition node as its left child. A postorder traversal naturally produces:

%a = load @a
%b = load @b
%sum = add %a, %b
%c = load @c
%result = mul %sum, %c

Each temporary names one completed computation. This makes definition-use relationships explicit and gives later passes precise places to fold constants, remove dead work, or allocate registers.

Trees, temporaries, and shared work

For a * b + a * b, direct tree lowering emits both multiplications. If the operations are pure and their operands have not changed, a directed acyclic graph (DAG) or common-subexpression pass can share the result:

%t1 = mul a, b
%t2 = add %t1, %t1

This reuse is not automatically legal. Loads, calls, volatile operations, traps, and mutable memory may make two textually identical expressions observably different. A lowering stage should preserve semantics first; optimization may share work only with sufficient proof.

For example, the two calls in random() - random() are textually identical but intentionally produce two results. Similarly, a[i] + (a[i] = 0) + a[i] contains two identical-looking reads separated by a write. Treating them as one DAG node would silently change the program.

Type-directed operator selection

The source operator + does not identify one IR instruction. The operand types and language rules choose the operation:

Implicit conversions must appear at a defined point. If count + 0.5 has type f64, the lowerer might emit %wide = sitofp %count to f64 before fadd %wide, 0.5. Making the conversion explicit preserves the type checker's decision and lets later passes reason about conversion cost and precision.

Evaluation order is part of meaning

In f() + g(), addition may look commutative, but the calls may print, mutate state, throw, or read the same memory. If the language specifies left-to-right evaluation, the IR must call f before g. Even when the language leaves order unspecified, the compiler must choose a valid order consistently within the generated CFG.

This distinction also limits algebraic simplification. Replacing x * 0 with 0 is not safe when evaluating x can throw. Replacing x + y with y + x is not safe when either side has ordered effects. Optimization reasons about both the result value and the events required to produce it.

Values versus locations

An expression lowerer often needs two related operations:

• lowerValue(e) computes the value of e;

• lowerPlace(e) computes a writable location for e.

The left side of items[i] = value needs an address, while the right side of x = items[i] needs a loaded value. Keeping these interfaces distinct prevents accidental extra loads and makes assignments, compound updates, fields, and dereferences easier to lower correctly.

For a variable, lowerPlace(x) may return the stack slot or global address bound to x; lowerValue(x) then loads from that place. For record.field, place lowering computes the base address plus a field offset. For *pointer, it uses the pointer value itself as the place after any required null or safety check.

Not every expression has a place. The temporary result of a + b can be used as a value but cannot normally appear on the left of an assignment. Encoding that distinction in the lowerer's types—rather than reporting it only with comments—prevents whole classes of invalid stores.