Erik Eckstein 3bdec7df65 SIL: native instruction ordering via persistent instruction indices ...

The compiler previously computed instruction ordering within a basic block on demand using InstructionIndices — a NodeBitfield-backed data structure that assigned
temporary per-pass indices by iterating the whole block. Every pass that needed to compare instruction positions had to construct one, paying O(n) up front each time.
LinearLifetimeChecker, BoundsCheckOpts each maintained their own copy.

Now, persistent indices stored on each instruction. Each SILNode now carries an integer index in its SmallCustomBits/LargeCustomBits storage (a new indexInList field).
Indices are lazily computed on first use and persist across optimization passes. Within a block, non-zero indices are strictly monotonically increasing; zero means "not
yet assigned."

Lazy assignment with gap filling: When an instruction is inserted, the block tries to assign it an index that fits in the gap between its neighbors (stride = 8). If the
gap is large enough the instruction immediately gets an index assigned. When no gap exists the instruction gets index 0 and the next ordering query on that instruction
triggers a full O(n) recompute of the block.

`Instruction.dominatesInBlock` — the primary API. Uses the stored indices directly (O(1)) when both are available; calls recomputeInstructionIndices() otherwise.

`Instruction.rawIndexInBlock: Int?` — exposes the raw index for diagnostics and the verifier (nil = not yet computed).

`BasicBlock.recomputeInstructionIndices()` — assigns fresh indices (multiples of stride 8) to every instruction in the block. Called automatically by isBeforeInBlock when
needed.

SmallCustomBits / LargeCustomBits overflow: The index is stored as a uint16_t in the small path and a uint32_t in the large path. When the index exceeds UINT16_MAX
(= ~8K instructions per basic block) the node transparently promotes to LargeCustomBits (heap-allocated), so even very large blocks are still handled correctly.

All SILBasicBlock mutation APIs that insert or move instructions are updated to maintain the monotonicity invariant:

- insert / push_back / push_front — attempt gap assignment on insertion.
- moveInstruction / moveInstructionToFront / moveTo — clear the index (set to 0) before moving, then gap-assign in the new position.
- spliceAtEnd / spliceAtBegin / split — zero all moved instructions' indices.

2026-06-14 21:55:32 +02:00

11 KiB

Raw Permalink Blame History

View Raw