Lesson 11.4 — Places, values and loop shapes: l-value/r-value evaluation, top-tested vs rotated loops¶

Techniques: l-value/r-value evaluation — an expression is lowered either to the location it denotes (a place, Strachey's L-value) or to the value stored there (an R-value), and the order in which places are computed and read is part of the language (Strachey 1967); loop shapes — the top-tested while form a front end emits vs the rotated (guarded do-while, "inverted") form optimizers prefer (LLVM loop-rotate, GCC ch) · Pebble implements: lowerPlace/lowerOperand with the materialize rule (E1, E3) and top-tested loops (E2) in lowerToPIR; LLVM's -O2 pipeline rotates them (pebblec -O2, or --passes='function(mem2reg,loop-rotate)'; pebblec -O1 is the course pipeline, Lesson 11.9 §2) · Prerequisites: Lesson 11.1; loops and preheaders (Ch 15) · Time: 3–4 hours

Two questions a lowering must answer for every statement. Where: xs[i] = next(&mut i) writes a location computed from xs and i; is i read before or after the call changes it? Pebble says before (spec §7), C++17 says the right side runs first, C leaves it unspecified. How often: a while loop tests its condition at the top of every iteration and jumps back unconditionally at the bottom; turning it into "test once, then loop with the test at the bottom" saves a jump per iteration and gives the optimizer a block that runs exactly when the body runs. The running examples:

fn next(i: &mut int) -> int { i += 1; return 7; }
fn main() -> int {
    var xs = [0, 0, 0];
    var i = 1;
    xs[i] = next(&mut i);      // stores into xs[1]; afterwards i = 2
    xs[i] += xs[0];
    return xs[1] + i;
}

fn sum(xs: &[int; 8], n: int) -> int {
    var s = 0;
    var i = 0;
    while i < n { s = s &+ xs[i]; i = i &+ 1; }
    return s;
}

1. Problem and motivation¶

L-value/r-value evaluation¶

Strachey distinguished the L-value of an expression, the location it denotes, from its R-value, the contents of that location, and observed that the left side of an assignment is evaluated for its L-value [Str00]. Every lowering has two translation functions, one returning a place and one returning a value; C's "lvalue conversion" and Clang's EmitLValue/EmitScalarExpr are the same split [CLANG-CGExpr]. The split matters for more than assignment: &mut place arguments, compound assignment (place op= e reads and writes one place, evaluated once), and PIR's rule that an operand that is a place is read when the instruction executes — not when the lowering produced it. lowerToPIR returns places whenever it can ((*_0)[_2] as an operand, no copy) and copies a place into a temporary only when a later call could change it (E1, E3).

Loop shapes¶

A front end naturally emits a while loop top-tested: the header evaluates the condition and branches to the body or the exit, and the body jumps back unconditionally. Each iteration then executes two control transfers. The rotated form (loop inversion) tests once before the loop (the guard) and then at the bottom: one conditional branch per iteration, and a block (the preheader) that executes exactly when the loop runs at least once — the place where loop-invariant code motion can put hoisted code without executing it on the zero-trip path (Ch 18). LLVM's loop-rotate and GCC's "copy loop headers" pass convert top-tested loops early in their -O2 pipelines [LLVM-LoopRotate, GCC-LoopCH]; LLVM's loop terminology calls the result a rotated loop [LLVM-LoopTerm]. Pebble lowers every while and for top-tested (spec §15) and leaves rotation to LLVM.

2. Definitions and algorithms¶

Definition 11.4.1 (Place expression, value, the two lowerings)

A place expression is a variable, a parameter, p.f or p[e] for a place expression p, or a parenthesized one (spec §9.1). Its place \(\mathcal{P}[\![p]\!]\) is a PIR place (a local, a global, with field, index and deref projections). The value \(\mathcal{V}[\![e]\!]\) of any expression is a PIR operand. A place used as an operand is read when the instruction that uses it executes.

Definition 11.4.2 (May-write, stable operand)

An expression may write if it contains a call with a &mut argument. An operand is stable if it is a constant or a place rooted at a temporary with no deref projection and only temporaries as index locals — nothing a later evaluation can change.

Lemma 11.4.3 (Only &mut calls write variables)

During the evaluation of a Pebble expression, a variable or parameter of the current function can change only inside a call that received a &mut reference to a place rooted at it.

Proof

Pebble has no assignment expressions (assignment is a statement, spec §7) and no global variables. A callee can reach a caller's variable only through a reference argument (spec §9.3), and & references are read-only. References are second-class (parameters only), so no reference to a variable can be stored and used by a later call. A &mut parameter of the current function is itself such a reference; by the exclusivity rule (E0414) it aliases no other parameter, and it can be written only by passing it on as &mut, which is again a call with a &mut argument.

Algorithm 11.4.4 (Places, operands and assignments)

Input: a typed expression or assignment statement.
Output: PIR statements, and a place or an operand.
Precondition: the program passed analyze().
Postcondition: the order of reads, checks and calls is the order of spec §7 and §8.2 (Theorem 11.4.5).
Invariant: every operand returned for an expression \(e_j\) in a list \(e_1 \dots e_k\) is stable if some \(e_{j'}\) with \(j' > j\) may write.

function Place(e):                                # 𝒫[[e]]
    x (a variable):          return _x   (or (*_x) for a reference parameter)
    p.f:                     return Place(p).f
    p[i]:                    b ← Place(p);  o ← Operand(i)
                             if o is a constant k with 0 ≤ k < N: return b[k]
                             t ← a local holding o;  emit c ← ult t, N;  assert c, bounds
                             return b[t]
    (a call, a literal):     return a temporary holding Value(e)

function Operand(e):                              # 𝒱[[e]] as an operand
    if e is a place expression: return Place(e)   # read later, when used
    if e is a constant:          return it
    return a temporary holding Rvalue(e)

function Operands(e1, ..., ek):                   # left to right, spec §8.2
    for j in 1..k:
        o_j ← Operand(e_j)
        if some e_j' (j' > j) may write and o_j is not stable: o_j ← Copy(o_j)
    return o_1 .. o_k

function Assign(p = e):
    d ← Place(p)                                  # the place's indices and checks first (spec §7)
    if e may write: replace every non-temporary index local of d by a copy
    emit  d ← Rvalue(e)                           # or `d = call ...` for a call

function CompoundAssign(p op= e):
    d ← Place(p);  (stabilize as above);  o ← Operand(e)
    emit the checks of `d op o`, then  d ← op d, o     # d is read after e

Theorem 11.4.5 (The lowering preserves evaluation order)

For every Pebble expression and assignment, the PIR produced by Algorithm 11.4.4 performs the reads of variables, the checks and the calls in the order spec §7 and §8.2 prescribe, and every read yields the value the source semantics reads.

Proof

Calls and checks are emitted in the order of the recursive walk, which is the source order (left to right, place before value in assignments). It remains to show that a read delayed to the instruction that uses a place operand sees the value the source would have read at the operand's position. Between the position of \(o_j\) and its use, only the evaluations of \(e_{j+1}, \dots, e_k\) run; by Lemma 11.4.3 they can change a variable only if one of them may write, and in that case Operands copied \(o_j\) at its position (the copy is a read there), and a copy into a temporary is stable (temporaries are never written again, Lemma 11.1.4). For an assignment, the index locals of the destination are copied before the value is evaluated if it may write, so the store goes to the element the source computed first; derefs of reference parameters cannot change because parameters are immutable bindings. For op=, the destination is read after \(e\) — exactly the source's order ("then reads the place").

Definition 11.4.6 (Top-tested and rotated loops)

A top-tested loop has a header \(H\) that evaluates the condition \(c\) and branches to the body \(B\) or the exit \(X\); \(B\) ends with a jump to \(H\). A rotated loop has a guard evaluating \(c\) before the loop, a preheader \(P\) entered only if \(c\) held, the body \(B\), and a bottom test at the end of \(B\) that evaluates \(c\) and branches back to \(B\) or to \(X\) (LLVM: the latch is also the only exiting block).

Algorithm 11.4.7 (Loop rotation)

Input: a top-tested loop \(H \to \{B, X\}\), \(B \to^{+} H\), whose header computes only \(c\) and values that are either dead after \(H\) or can be recomputed.
Output: the rotated loop of Definition 11.4.6.
Precondition: the header can be duplicated (LLVM: at most 16 instructions, -rotation-max-header-size); the loop has one latch.
Postcondition: the same sequence of condition and body evaluations on every execution (Theorem 11.4.8).
Invariant: before each execution of \(B\), the most recent evaluation of \(c\) was true.

function Rotate(L = (H, B, X)):
    G ← a copy of H's instructions placed in the preheader position     # the guard
    in G:  br c', P, X                  # c' = c computed from the values on loop entry
    P ← new preheader: goto B
    replace the latch's `goto H` by a copy of H's instructions and `br c'', B, X`
    H becomes part of the latch; values defined in H get phis at B (first/next)
    and at X (from G or from the bottom test)       # LCSSA

Theorem 11.4.8 (Rotation preserves behavior; cost per iteration)

If the duplicated header instructions have no side effects (or are duplicated exactly), the rotated loop evaluates \(c\) and \(B\) in the same sequence as the top-tested loop. For a loop that runs \(n \ge 0\) iterations, the top-tested form executes \(n + 1\) conditional branches and \(n\) unconditional jumps; the rotated form executes \(n + 1\) conditional branches and no unconditional jump.

Proof

Both forms evaluate \(c\); if it is false they leave to \(X\) without running \(B\) (\(n = 0\): one conditional branch each). Otherwise, by induction on the iteration: after the \(k\)-th execution of \(B\) the top-tested form jumps to \(H\) and evaluates \(c\), the rotated form evaluates the same \(c\) at the bottom — with the same inputs, since nothing runs between the end of \(B\) and either test — and both continue with \(B\) if it is true and leave otherwise. So the sequences \(c\,B\,c\,B \dots c\) coincide. Counting: \(n + 1\) evaluations of \(c\), each ending in one conditional branch, in both forms; the top-tested form additionally jumps back after each of the \(n\) bodies, the rotated form falls into the bottom test.

3. Worked example¶

L-value/r-value evaluation¶

pebblec --emit=pir on the first example:

bb0:
  _0 = [0, 0, 0] @6:5
  _1 = 1 @7:5
  _2 = ult _1, 3 @8:5
  assert _2, bounds @8:5
  _3 = _1 @8:5
  _4 = &mut _1 @8:18
  _0[_3] = call @next(_4) @8:13
  _5 = ult _1, 3 @9:5
  assert _5, bounds @9:5
  _6 = saddo _0[_1], _0[0] @9:5
  assert !_6, overflow @9:5
  _0[_1] = add _0[_1], _0[0] @9:5
  _7 = saddo _0[1], _1 @10:12
  assert !_7, overflow @10:12
  _8 = add _0[1], _1 @10:12
  return _8 @10:5

Step by step through Assign(xs[i] = next(&mut i)):

step	action (Algorithm 11.4.4)	emitted	why
1	`Place(xs[i])`: base `_0`, index operand `_1` (a variable)	`_2 = ult _1, 3`, `assert _2, bounds`	the place's check comes first (spec §7)
2	the value `next(&mut i)` may write	`_3 = _1`	stabilize: the destination becomes `_0[_3]`
3	the `&mut i` argument	`_4 = &mut _1`	references are taken into temporaries (spec §15)
4	the call writes the place directly	`_0[_3] = call @next(_4)`	destination-driven (Lesson 11.1 §6)

At run time i is 1 at step 2, so the store goes to xs[1] although next sets i to 2 — the e2e test order-assign-place.pbl checks this. The compound assignment xs[i] += xs[0] evaluates the place (i is now 2, check), then xs[0] (a constant index in bounds: no check, _0[0]), then reads _0[_1] in the saddo and the add: nothing between may write, so no copy. The result is xs[1] + i = 7 + 2 = 9.

Loop shapes¶

sum is lowered top-tested: bb1: _4 = slt _3, _1; br _4, bb2, bb3, and bb2 ends with goto bb1. After mem2reg and loop-rotate (box in §7), the guard is icmp slt i64 0, %n in bb0, bb2.lr.ph is the preheader, and the bottom test icmp slt i64 %8, %n ends the body. Counting control transfers for Theorem 11.4.8 (the bounds-check branch is the same in both forms and not counted):

\(n\)	top-tested: cond. branches	top-tested: jumps	rotated: cond. branches
0	1	0	1 (guard)
1	2	1	2
3	4	3	4
8	9	8	9

4. Invariants and correctness¶

L-value/r-value evaluation¶

Theorem 11.4.5, with the invariant of Algorithm 11.4.4. The rule is conservative: it copies an earlier operand when any later operand may write, even if the write targets an unrelated variable (§6 has the precise variant). The precondition that breaks the argument is Lemma 11.4.3: in a language with global variables, pointers or assignment expressions (C, Rust with unsafe), any call or even any assignment may change a place, and the translator must copy or prove otherwise.

Reading the destination too early in op=

Lowering t += add5(&mut t) as tmp = t; call; t = tmp + result reads t before the call and gives 10 instead of 15 (the e2e test order-assign-place.pbl). Spec §7 says e first, then the place is read; Algorithm 11.4.4 uses the place as an operand after e precisely so.

Loop shapes¶

Theorem 11.4.8 needs the header to be duplicable: if the condition calls a function with side effects, both copies must call it exactly when the original would — which they do, because each evaluation of \(c\) happens once in either form — but a header with many instructions doubles code size, which is why LLVM refuses above 16 instructions. Rotation also needs a single latch (LoopSimplify form, Lesson 15.7).

5. Complexity¶

\(\lvert e \rvert\) = expression size, \(k\) = operands in a list, \(h\) = header size, \(n\) = iterations.

Technique	Time (compile)	Cost (run time)	Justification
Places and values	\(O(\lvert e \rvert)\) with `mayWrite` memoized	\(\le 1\) extra copy per operand, per index local of a destination	each node's `mayWrite` is computed once (a cache); `Operands` inspects each operand once
Loop rotation	\(O(h)\) per loop, plus SSA/LCSSA repair	saves \(n\) unconditional jumps; adds \(h\) instructions of code	Algorithm 11.4.7 copies the header once; Theorem 11.4.8 counts the transfers

Pathological family (places). f(x1, x2, ..., x_{k-1}, g(&mut y)): every one of the \(k - 1\) earlier arguments is a variable and the last may write, so the conservative rule copies all \(k - 1\) although only arguments rooted at y needed it: \(k - 1\) copies instead of 0. (They are free after mem2reg — copies of SSA values vanish — so the cost is only in the PIR.) Pathological family (loops). A header whose condition is a long && chain of \(m\) comparisons exceeds the 16-instruction limit for \(m \gtrsim 8\) and is not rotated; the loop keeps a jump per iteration and LICM loses its guaranteed-to-execute preheader.

L-value/r-value evaluation¶

Unspecified order (C, C++ before 17 for most operators): the compiler may evaluate either side first; Clang evaluates the right side of = first (box in §7), C++17 made that mandatory, Java requires left to right (box).
Precise may-write by root variable: copy an operand only if a later &mut argument is rooted at the same variable (Lemma 11.4.3 makes this sound for Pebble); trade-off: a small analysis, fewer copies in PIR.
Two-phase borrows (Rust): v.push(v.len()) reserves the &mut v place, evaluates the argument, then activates the borrow — the same "place first, value later" problem solved in the borrow checker.

Loop shapes¶

Guard elimination: when the trip count is known to be \(\ge 1\) (SCEV, Ch 18), the guard folds away and the rotated loop is a plain do-while.
Header copying in GCC (pass_ch) copies the header up to a cost limit and peels the first exit test; LLVM's loop-rotate additionally creates LCSSA phis on the exit (the %s.addr.0.lcssa in §7) [GCC-LoopCH, LLVM-LoopRotate].
Front-end rotation: a front end can emit for loops rotated directly (some do for counted loops); Pebble does not, to keep PIR close to the source and the golden tests stable.

7. In real compilers¶

L-value/r-value evaluation¶

Clang: CodeGenFunction::EmitLValue (places) in clang/lib/CodeGen/CGExpr.cpp [CLANG-CGExpr] and ScalarExprEmitter::VisitBinAssign/EmitCompoundAssignLValue in CGExprScalar.cpp [CLANG-ExprScalar]. javac: Gen.visitAssign in src/jdk.compiler/share/classes/com/sun/tools/javac/jvm/Gen.java [JAVAC-Gen]. rustc: as_place and as_operand in compiler/rustc_mir_build/src/builder/expr/ [RUSTC-AsPlace]. Pebble: FunctionLowering::lowerPlace, lowerOperands, stabilize.

Which side of a[idx()] = val() runs first: Clang vs javac

Reproduce (clang 23.1.2, javac 21.0.10):

cat > lv.cpp <<'EOF'
int idx();
int val();
int a[4];
void store() { a[idx()] = val(); }
EOF
clang++-23 -std=c++17 -O0 -S -emit-llvm lv.cpp -o - | sed -n '/define.*store/,/^}/p'
mkdir -p j && cat > j/Order.java <<'EOF'
class Order {
    static int[] a = new int[4];
    static int idx() { return 1; }
    static int val() { return 7; }
    static void store() { a[idx()] = val(); }
}
EOF
cd j && javac Order.java 2>/dev/null && javap -c -p Order 2>/dev/null | sed -n '/static void store/,/return/p'

Output:

define dso_local void @_Z5storev() #0 {
  %1 = call noundef i32 @_Z3valv()
  %2 = call noundef i32 @_Z3idxv()
  %3 = sext i32 %2 to i64
  %4 = getelementptr inbounds [4 x i32], ptr @a, i64 0, i64 %3
  store i32 %1, ptr %4, align 4
  ret void
}
  static void store();
    Code:
       0: getstatic     #7                  // Field a:[I
       3: invokestatic  #13                 // Method idx:()I
       6: invokestatic  #17                 // Method val:()I
       9: iastore
      10: return

What to notice: C++17 sequences the right operand of = before the left, so Clang calls val() first and computes the place (getelementptr) last; Java evaluates the array reference and the index (the L-value) before the right side. Pebble follows Java's order (spec §7), which is why Algorithm 11.4.4 lowers the place first and stabilizes it.

Loop shapes¶

LLVM: LoopRotate::rotateLoop in llvm/lib/Transforms/Utils/LoopRotationUtils.cpp, driven by LoopRotatePass::run (llvm/lib/Transforms/Scalar/LoopRotation.cpp, option -rotation-max-header-size, default 16) [LLVM-LoopRotate]. GCC: pass_ch in gcc/tree-ssa-loop-ch.cc [GCC-LoopCH].

LLVM rotates Pebble's top-tested loop

Reproduce (pebblec from this repository with -DPEBBLE_USE_SOLUTION=all, LLVM 23.1.2; loop.pbl is the sum function of this lesson plus fn main() -> int { let xs = [1, 2, 3, 4, 5, 6, 7, 8]; return sum(&xs, 8); }):

pebblec --passes='function(mem2reg,loop-rotate)' --emit=llvm loop.pbl -o - | sed -n '/define internal i64 @sum/,/^bb1.bb3_crit_edge:/p'

Output:

define internal i64 @sum(ptr %xs, i64 %n) {
entry:
  br label %bb0

bb0:                                              ; preds = %entry
  %0 = icmp slt i64 0, %n
  %1 = zext i1 %0 to i8
  br i1 %0, label %bb2.lr.ph, label %bb3

bb2.lr.ph:                                        ; preds = %bb0
  br label %bb2

bb2:                                              ; preds = %bb2.lr.ph, %assert.ok
  %i.addr.03 = phi i64 [ 0, %bb2.lr.ph ], [ %8, %assert.ok ]
  %s.addr.02 = phi i64 [ 0, %bb2.lr.ph ], [ %7, %assert.ok ]
  %2 = icmp ult i64 %i.addr.03, 8
  %3 = zext i1 %2 to i8
  %4 = trunc i8 %3 to i1
  br i1 %4, label %assert.ok, label %trap.bounds

bb1.bb3_crit_edge:                                ; preds = %assert.ok

What to notice: PIR's header bb1 is gone: its test was copied into bb0 as the guard (icmp slt i64 0, %n, with i = 0 substituted) and to the end of the body as the bottom test (in assert.ok, not shown); bb2.lr.ph is the preheader of Definition 11.4.6. The loop body now starts with the phis — no unconditional jump back (Theorem 11.4.8).

GCC copies the loop header to make a do-while loop

Reproduce (gcc 14.2.0):

cat > sum.c <<'EOF'
long sum(const long *a, long n) {
  long s = 0;
  for (long i = 0; i < n; i++)
    s += a[i];
  return s;
}
EOF
gcc-14 -O2 -fdump-tree-ch2-details -c sum.c
grep -E 'do-while|Duplicating|Copying' sum.c.*ch2

Output:

Loop 1 is not do-while loop: latch is not empty.
    Duplicating header BB to obtain do-while loop
Copying headers of loop 1
Duplicating header of the loop 1 up to edge 4->5
Loop 1 is do-while loop
Loop 1 is now do-while loop.

What to notice: GCC's name for the rotated form is "do-while loop"; pass_ch duplicates the header (Algorithm 11.4.7) so that the loop's test is at the bottom.

Find where LLVM does it. In llvm/lib/Transforms/Scalar/LoopRotation.cpp, what is the name of the command-line option that bounds the size of a header loop-rotate will duplicate, and its default? (Quiz llvm-where-rotate-limit.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
L-value/r-value evaluation (places as operands + materialize rule)	Exact source evaluation order (Theorem 11.4.5); conservative copies	\(O(\lvert e \rvert)\) · copies vanish after mem2reg	PIR keeps places visible (`(*_0)[_2]`), so later chapters see every access	Medium (two translation functions, the may-write rule)	Every front end (Clang, javac, rustc MIR, Pebble)
Top-tested loops	Any loop	\(n\) extra jumps per \(n\) iterations	Mirrors the source	Lowest	Front ends' output (Clang, rustc, Pebble)
Rotated loops	Loops with a duplicable header and one latch	saves \(n\) jumps; gives a guaranteed-to-execute preheader	Guard + preheader + bottom test; LCSSA phis	Medium (header copy, SSA repair)	LLVM `loop-rotate`, GCC `ch` at `-O1`/`-O2`, before LICM and vectorization

Choose place-first evaluation with the materialize rule when the language fixes evaluation order and has &mut-style references (Pebble, Java, Swift); a language with unspecified order may evaluate in whatever order is cheapest. Emit top-tested loops and let the optimizer rotate when you target LLVM or GCC: rotation needs SSA repair that the optimizer already does; rotate in the front end only if there is no optimizer.

9. Assessment¶

Quiz (./course quiz 11): lvalue-order, lvalue-copies (tag lvalue-rvalue); rotate-branch-count, rotate-preheader, llvm-where-rotate-limit (tag loop-shapes).
Drill: ./course drill loop-forms (Chapter 15: preheaders, latches and the canonical loop form that rotation produces); the evaluation-order rules have no drill of their own — the e2e programs order-*.pbl and the quiz's lvalue-* questions trace them, and a random-program drill would duplicate the e2e runner.
Flashcards: tags lvalue-rvalue, loop-shapes.
Exercises: E1, E2, E3.

References¶

See the chapter references.

Lesson 11.4 — Places, values and loop shapes: l-value/r-value evaluation, top-tested vs rotated loops¶

1. Problem and motivation¶

L-value/r-value evaluation¶

Loop shapes¶

2. Definitions and algorithms¶

3. Worked example¶

L-value/r-value evaluation¶

Loop shapes¶

4. Invariants and correctness¶

L-value/r-value evaluation¶

Loop shapes¶

5. Complexity¶

6. Variants and refinements¶

L-value/r-value evaluation¶

Loop shapes¶

7. In real compilers¶

L-value/r-value evaluation¶

Loop shapes¶

8. Comparison¶

9. Assessment¶

References¶