11.5 Short-Circuit Boolean Code Generation

Short-circuit operators are control flow disguised as expressions. In A() && B(), B() runs only if A() is true. In A() || B(), it runs only if A() is false. A compiler that eagerly computes both operands changes side effects, exceptions, performance, and sometimes program validity.

The most useful lowering interface is often lowerCondition(expr, trueBlock, falseBlock). It emits branches directly instead of first constructing a boolean value.

This is called control form: the meaning of a condition is represented by where execution goes, not by a temporary containing true or false. It fits if, while, and conditional expressions naturally, and it avoids instructions that would immediately be consumed by a branch.

Compose conditions with destinations

The recursive rules are compact:

• for A && B, send A's true edge to a fresh block that evaluates B, and send its false edge directly to the final false destination;

• for A || B, send A's false edge to B, and its true edge directly to the final true destination;

• for !A, swap the true and false destinations.

These rules naturally handle nesting without materializing intermediate booleans. They also preserve exactly which calls, loads, and checks are skipped.

; A() && B()
entry:
  %a = call @A()
  br %a, rhs, false
rhs:
  %b = call @B()
  br %b, true, false

For the nested expression A() && (B() || !C()), apply the same rules recursively:

entry:
  %a = call @A()
  br %a, eval_b, false
eval_b:
  %b = call @B()
  br %b, true, eval_c
eval_c:
  %c = call @C()
  br %c, false, true   ; destinations swapped for !C

The possible traces explain the graph. If A() is false, the trace is only A. If A() is true and B() is true, the trace is A, B. Only when A() is true and B() is false does C() run. The final truth value alone cannot show whether these skips were preserved.

Comparisons such as x < y are leaf conditions. Their lowerer computes both operands, emits a comparison, and branches on the result. A boolean variable is another leaf: load or reference its value, then branch. The recursive AND/OR/NOT rules compose these leaves into arbitrarily large conditions.

When a boolean value is required

Direct branches are ideal for if and while, but x = A() && B() needs a value. Lower the condition to true and false blocks, then merge them:

true:  br merge
false: br merge
merge:
  %x = phi [true, true], [false, false]

This is value form. It is needed when a boolean is stored, passed to a function, returned, or used by a non-control operation. The lowerer can implement lowerValue(booleanExpr) by creating true, false, and merge blocks, delegating to lowerCondition, then producing a phi at the merge. Conversely, when a value-form boolean is used by if, the compiler can branch on it directly.

Avoid materializing too early. Generating and %a, %b after eagerly computing both values is valid only for non-short-circuit boolean operators or when both operands are already safe, effect-free values. For language operators && and ||, CFG edges are the default correct representation.

Test skipped behavior

Truth-table tests are not enough. Give the right operand a visible effect—a counter increment, trace event, or deliberate trap—and assert that it is absent on short-circuited paths. Also test nested combinations, negation, and value materialization. The critical property is not only the final truth value; it is the execution trace that produced it.

A complete test set should cover each edge at least once: AND failing on the left, AND reaching the right, OR succeeding on the left, OR reaching the right, negation swapping destinations, and a nested expression reaching every leaf. For value form, also verify that the merge has exactly the true and false predecessors expected by the phi. These structural assertions catch accidental eager evaluation even when all ordinary truth-table results happen to match.