Alias analysis: the oracle, the audit, and what is still assumed

The vectorization, range-analysis and scheduling lanes all need one question answered — "may these two memory operations be reordered?" — and the review named sound alias metadata as their prerequisite. This document is the answer in one place:

• §1 names the one oracle those lanes must ask, and states its contract and the premises its every "no, they do not alias" answer rests on.
• §2 is the audit of the two analysis passes that answer alias questions themselves (jit/src/ir_optimize.rs, jit/src/escape_analysis.rs), question by question, with the proof each relies on and whether that proof is established.
• §3 is the escape-invalidation set: everything that can make a "does not escape" conclusion wrong, and where each is checked.
• §4 is what remains unvalidated — assumptions that are load-bearing today and that nothing tests.

Three defects were found and fixed; they are marked FIXED in §2 with the regression test that fails without the fix. All three are the same shape as the miscompilation this branch already paid for (escape analysis forwarding a field load to a later store's value): a may-alias answer used where a must-alias answer was required.

---

1. The oracle

There is one. Do not build a second. It lives in jit/src/ir.rs and it is:

Graph::may_alias(&self, a: AliasClass, b: AliasClass) -> bool
Graph::may_reorder(&self, earlier: NodeId, later: NodeId) -> Reorder
Graph::may_reorder_effects(&self, earlier: MemEffect, later: MemEffect) -> Reorder

Reorder carries the reason — a ReorderProof naming the fact that licenses the move, or a ReorderBlock naming the fact that forbids it. Record the proof; do not re-derive it. A pass that invents its own reasoning is a fourth private notion of aliasing, which is the exact situation the model was built to end (jit/src/ir.rs, the section header at the AliasClass definition, enumerates the three copies that existed before it).

1.1 Contract

1.2 The premises behind every false

Each of these is a claim about the VM's object layout, not a fact about the IR. If one is broken, may_alias silently starts licensing reordering across a real dependence.

1. Different storage kinds never overlap. A field cell is not an array element (a Java object is either an array or a class instance, and verified bytecode never reaches getfield on an array); an array's length word is not a field cell; a class's static storage is a per-class area no object reference addresses; an object's monitor is none of them. Obligation: any new op with a computed/raw address (an Unsafe-style access) must classify as AliasClass::Any, not as one of the structured classes.

2. AliasClass::ArrayLength is read-only storage. Nothing writes an array's length after the allocation that produced it, so a length read never conflicts with a write. This is what lets an ArrayLength commute with a store, which the token chain (where it sits between two writers) cannot.

3. Same kind, same base ⇒ disjoint only for two unequal constant offsets. AccessOffset::Absent — the layouts that carry no offset operand at all — is "the object's storage", and is therefore never disjoint from another access to the same base. This is a may-alias. It was the source of audit item A3.

4. Same kind, different base ⇒ disjoint only when the bases are provably different objects (Graph::refs_may_alias → RefOrigin::provably_distinct: both sides must have known provenance, their allocation sets must be disjoint, and at most one may be possibly-pre-existing, because two parameters can be the same object — foo(x, x)).

5. Two array elements at different element types never overlap. AliasClass::ArrayElem { elem } distinguishes an int[] cell from an Object[] cell without needing either reference's provenance, because a Java array's component type is fixed at allocation.

   This is the premise the parallel lanes must not break, and it is the one most easily broken. It is sound only while every Op::ArrayLoad / Op::ArrayStore carries the array's component type as its MemKind. The guard is written as x != y && ke != kf (Graph::may_alias): two accesses at different kinds through the same array node keep must-aliasing, so an ill-typed graph cannot manufacture a disjointness. But two accesses at different kinds through different nodes are declared disjoint outright.

   A widened or vectorized access that keeps a different MemKind than the array's component type breaks this — e.g. rewriting eight byte[] accesses as one MemKind::Long access would make that access provably non-aliasing with every remaining MemKind::Byte access to the same array. Any lane that widens an element access must either keep the component MemKind or degrade the class to AliasClass::Any.

   The tag is read off the accessing op by array_elem_kind, never supplied by a caller, which is what makes x64::simd_analysis's refusal of vector accesses to MemKind::Ref elements (a vector store of oops bypasses the GC write barrier) unforgeable. Reading it from the class rather than carrying a private copy is a requirement, not a style preference.

6. Ordering is separate from aliasing. Two monitor operations on provably distinct objects do not alias and still do not commute, because monitor-enter is an Acquire and monitor-exit a Release. Anything that asks only may_alias and skips may_reorder_effects loses the JMM fences, the allocation-order rule, and the safepoint rule.

1.3 What may_reorder_effects applies, in order

1. Either side inert → Allowed(EffectFree).
2. Either side a full fence (SeqCst, i.e. a volatile write) → Blocked(Fence).
3. earlier has acquire → Blocked(Acquire): nothing after a monitor-enter or a volatile read may move above it.
4. later has release → Blocked(Release): nothing before a monitor-exit or a volatile write may move below it. 3 and 4 are one-sided on purpose — that asymmetry is the JMM's roach motel, and it is why a synchronized region bounds the accesses inside it without pinning the ones outside.
5. Both allocate → Blocked(Allocation). Which allocation runs first is observable through OutOfMemoryError and through the addresses and identity hashes the collector hands out.
6. Locations may conflict (W/R, R/W, W/W) → Blocked(MayAlias).
7. One is a safepoint and the other writes → Blocked(Safepoint). The constraint is specifically about writes: every store the method has performed must have happened before an interpreter frame is rebuilt, and no store it has not yet performed may have. Loads cross a safepoint freely.
8. Neither writes → Allowed(ReadOnly).
9. Otherwise → Allowed(DisjointLocations).

---

2. Audit

Scope: every place in jit/src/ir_optimize.rs and jit/src/escape_analysis.rs that answers "can these be reordered / is this load redundant / is this store dead / is this object confined".

---

3. The escape-invalidation set

A "does not escape" conclusion is invalidated by anything that can make the reference observable outside the allocating frame, or that can make its address observable. Both lists are checked; they are different questions and conflating them is how the last miscompilation on this branch happened.

3.1 Reachability (EscapeState)

Not escapes, deliberately: Op::MonitorEnter/Exit (a monitor does not publish the object — but see §3.2), Op::ArrayLength, Op::If (its operand is a comparison result), Op::Load with the object as holder, and a comparison against the null literal (a fresh allocation is non-null by construction, so o == null reads no address; classifying it as an identity observation would refuse every object that is ever null-checked).

3.2 Identity (independent of §3.1)

An object can be perfectly NoEscape and still be unreplaceable because something observes its address. find_identity_observations collects these, and find_scalar_replacements applies the gate before the use walk, so an observation reached through an alias the walk does not classify as transparent cannot slip past:

• if_acmpeq / if_acmpne — two scalar-replaced objects with equal fields are indistinguishable; two heap objects are not (Op::RefCompare).
• System.identityHashCode, and an Object.hashCode that is not overridden — a stable per-object value derived from the header (Op::IdentityHash).
• monitorenter / monitorexit — the monitor is the object header.

The supported route to replacing a synchronized object is two-phase: analyse, apply the elision the analysis offers (the monitors become Op::Dead), analyse again. Coupling the two — "the monitor will be removed anyway" — is wrong, because apply_ea_to_ir independently refuses elisions this module offers (for a lock naming a safepoint slot, for one whose memory chain cannot be spliced, for one whose value is still read), and each refusal would leave a live monitorenter on a deleted reference.

---

4. What remains unvalidated

Ordered by how much a wrong answer costs.

1. The element-type premise has no negative control. Nothing tests that a pass cannot introduce an Op::ArrayLoad/Op::ArrayStore whose MemKind is not the array's component type. §1.2 item 5 states the obligation; it is currently enforced by nobody. The cheapest guard would be an ir_verify lane asserting that all array accesses through the same array node agree on their MemKind — that catches the widening mistake at the node that made it. (Cross-file: jit/src/ir_verify.rs, not this lane's to edit.)

2. LICM repoints a hoisted load's control edge but not its memory token. licm sets inputs[0] to the pre-header and leaves inputs[1] naming an in-loop memory φ or store. The value is sound — A1 and A2 together prove no in-loop writer touches that load's location, so the memory state at the pre-header and inside the loop agree for that cell — but the graph now encodes a node anchored before the loop that consumes a token defined inside it. Whether ir_schedule can honour that, and whether ir_verify's ordering lane should reject it, is a scheduling question this lane did not answer. (Cross-file: jit/src/ir_schedule.rs, jit/src/ir_verify.rs.)

3. LICM hoists a faulting load out of a possibly-zero-trip loop. There is no trip-count guard. Op::Load faults on a null base and deopts; the deopt re-enters the interpreter at the load's bci, which does not execute the loop body, so the fault is not observed — but this rests on the deopt path, not on anything the alias model says, and ir.rs's own section header explicitly excludes implicit-exception order from what may_reorder answers.

4. AliasClass::Static has no producer. getstatic / putstatic have no IR lowering, so static field access reaches EA as a store to a holder with an empty points-to set (caught, GlobalEscape) and reaches the memory model not at all. The class exists so the lowering lands with a classification instead of widening everything to Any. Nothing exercises it end to end.

5. Op::Safepoint, Op::Throw, Op::RefCompare and Op::IdentityHash are partly unproduced in the EA graph. escape_analysis_from_ir now emits RefCompare and IdentityHash for the two shapes it can prove, but nothing emits Op::Safepoint (the IR keeps safepoints in a side table, not as nodes) and nothing emits Op::Throw. LockRefusal::SafepointInGap is therefore unreachable from production IR, and lock coarsening relies on the gap allowlist alone. The allowlist admits no node that can be a safepoint, so the outcome is right; the reason is incidental.

6. A5's fix leaves a residual precision cliff that nothing measures. A store in a no-offset layout to a multi-field allocation is now never matched. Since the production lowering always carries an offset, this should cost zero deletions on real code — but there is no counter that would show it if a future producer started emitting the compact form.

7. MAX_ALIAS_ALLOC_SET (8) and REF_ORIGIN_MAX_DEPTH (32) are unmeasured. Both degrade to unknown provenance, which is the safe direction, but nothing reports how often a real method hits either bound — so the difference between "this pass is precise" and "this pass silently gave up" is currently invisible.