83. Loops

Where are the loops?

Viscosity needs loops for three decisions: which fields each loop touches, how many times a loop runs (to estimate sizes), and whether an index can run off the end of the array. But in the IR, the for is gone. Here is the outer loop of this function as Viscosity sees it:

function sum(g) {
  let s = 0;
  for (let i = 0; i < g.length; i++) {
    for (let k = 0; k < 3; k++) {
      s += g[i].x;
    }
  }
  return s;
}

  b1:  ; preds b0 b3
    %20 = phi %1, %11
    %3 = phi %2, %23
    %5 = field.get %0 .length
    %6 = binop < %3, %5
    condbr %6, b2, b4
  ...
  b3:  ; preds b8
    %21 = unop + %3
    %22 = const 1
    %23 = binop + %21, %22
    br b1

The loop is just the arrow from b3 back up to b1. The compiler has to rediscover it.

Back edges

“Had to pass through” is dominance, from chapter 76. An edge t → h whose target h dominates its source t is a back edge. Step through how Viscosity’s naturalLoops finds both loops in sum:

The heart of it, from cfg.ts (simplified: the real code also merges back edges that share a header):

for (const s of successors(f, b.id)) {
  if (!dominates(idom, s, b.id)) continue;
  // b → s is a back edge; s is the header
  const body = new Set([s]);
  const stack = [b.id];
  while (stack.length) {
    const x = stack.pop();
    if (body.has(x)) continue;
    body.add(x);
    for (const p of f.blocks[x].preds)
      stack.push(p);
  }
}

For sum, it returns (printed one loop per entry):

header b1  depth 1
  body b1 b2 b3 b5 b6 b7 b8
header b5  depth 2
  body b5 b6 b7

LLVM uses the same definition, and calls a block with a back edge a latch and the single block that enters the loop from outside its preheader^[1].

The counter that drives the loop

Look again at b1. In SSA, i is a phi, %3 = phi %2, %23: coming from b0 it is %2 (the 0); coming back from b3 it is %23, which is %3 plus one.

Viscosity’s isCountingPhi checks for this pattern with a step of exactly +1 and a start that is provably a non-negative integer (a constant, a sum or product of non-negative integers, or a phi of them). The core of it, from analysis.ts:

const [x, y] = step.args.map(inst);
const unary = x.op === 'unop' &&
  x.operator === '+';
const base = unary ? inst(x.args[0]) : x;
if (base.id === phi.id && y.op === 'const'
    && y.value === 1 && nonNegInt(start))
  return true;

The unary + is there because i++ first converts i to a number: %21 = unop + %3, then %23 = %21 + 1.

With a counting phi from 0 and a test like i < 100, Viscosity knows the trip count: 100. A push inside nested loops of 10 and 20 trips gives about 200 elements in explain; a non-constant bound gives size unknown statically.

Proving ps[i] is in bounds

When ps becomes a struct of arrays, ps[i].x becomes ps.x[i]. In the original, ps[i] past the end is undefined, and .x on it throws a TypeError. The typed array just returns undefined. So Viscosity wraps the index in a check that throws the original error, unless it can prove the check never fires.

The proof uses everything in this chapter. For an access ps[idx]:

1. idx is a counting phi (start ≥ 0, step +1), so it is a whole number ≥ 0.
2. Some loop containing the access has idx’s block as its header, and the header’s test (or one of its && parts) is idx < ps.length.
3. The test’s “true” successor dominates the access: you can’t reach the access without the test having just passed.

const guarded = conjuncts(inst(t.cond))
  .some((c) => c.op === 'binop' &&
    c.operator === '<' &&
    c.args[0] === idx.id &&
    isLengthOf(c.args[1], coll));
if (guarded &&
    dominates(idom, t.then, access.block))
  ig.boundsProven = true;

(Simplified: t is the header’s branch, and isLengthOf stands for an inline check that the bound is the same collection’s .length.) The length can only grow meanwhile, because Viscosity bails out on anything that could shrink the array, such as .pop().

Here are seven loops over ps, each followed by one console.log(ps[0].x) (outside any loop, so never proven), with the last line of explain:

loop                         proven
i < ps.length                2 of 3
i < n   (const n = 1000)     0 of 3
i < ps.length && go          2 of 3
i <= ps.length               0 of 3
i < ps.length; i += 2        0 of 3
ps[i] in an inner k loop     2 of 3
ps[i - 1], i from 1          1 of 3

Each failure breaks a condition: the bound isn’t ps.length, <= allows i === length, the step isn’t +1, i - 1 isn’t a counting phi. In the compiled code:

// i < ps.length: proven, no check
ps.x[i] += ps.vx[i];

// i < n: checked
ps.x[__vsc_bc(ps, i, 'x', true)] +=
  ps.vx[__vsc_bc(ps, i, 'vx', false)];

This mattered. The engine’s history records that extending the proofs to outer-loop indexes, non-negative starts and && guards removed the checks that had made n-body and boids slower than the original. n-body reads b[i].x inside its j loop; boids runs j from i + 1 while j < i + 64 && j < b.length. In the engine’s committed end-to-end run (bench/results/e2e-node-2026-10-31.md), both are now faster than the original (1.09× and 1.18×), with every element access proven.

Loop invariants

In the inner loop of sum, block b6 starts with %14 = index.get %0, %3: that is g[i]. Both operands come from outside the k loop (%0 is the parameter, %3 the outer counter), so every trip around the k loop computes the same thing.

For arithmetic that rule is enough. For memory reads it isn’t: g[i] is invariant only if nothing in the loop changes what is stored there, and g.length in a loop that pushes onto g changes every trip, though g itself never does. Hoisting a read needs to know which writes might touch the same memory. LLVM’s licm pass says this directly: it uses alias analysis to decide whether a load in a loop can be hoisted^[2].

Your turn

function findLoops(succ, dom) {
  // your code here
  return {};
}

const succ = {
  b0: ['b1'], b1: ['b2', 'b3'],
  b2: ['b1'], b3: [],
};
const dom = {
  b0: ['b0'], b1: ['b0', 'b1'],
  b2: ['b0', 'b1', 'b2'],
  b3: ['b0', 'b1', 'b3'],
};
console.log(findLoops(succ, dom));
// { b1: ['b1', 'b2'] }

const PURE = ['const', '+', '-', '*'];

function invariants(loop, outside) {
  // your code here
  return [];
}

const I = (id, op, ...args) =>
  ({ id, op, args });
const loop = [
  I('i', 'phi', 'z', 'j'),
  I('k', 'const'),
  I('m', '*', 'n', 'k'),
  I('j', '+', 'i', 'k'),
];
const out = ['n', 'z'];
console.log(invariants(loop, out));
// ['k', 'm']

What you learned

• A natural loop comes from a back edge t → h, where h dominates t: it is h plus every block that reaches t without passing through h. Walk predecessors backwards from t, stopping at h.
• Loops nest; a loop’s depth is how many loops contain it.
• An induction variable steps by a fixed amount each trip. In SSA, the basic one is a phi in the header: start from outside, phi + step from the latch. With a constant bound, it gives the trip count.
• Viscosity proves ps[i] in bounds when i is a counting phi, the header tests i < ps.length (perhaps inside &&), and the test’s true branch dominates the access.
• A loop-invariant value is the same on every trip. Moving a memory read out of a loop also needs to know that nothing in the loop writes there: that is alias analysis, next.