Make RegAllocFast consume MachineIR in SSA form

[MaskRay]

Teach RegAllocFast to consume SSA MachineIR directly, so that the pipelines it serves — -O0, and -O2 -mllvm -regalloc=fast – can drop PHIElimination and TwoAddressInstructionPass entirely. The allocator lowers PHIs and tied operands itself, instead of having two whole-function passes rewrite the function first and then leaning on the allocator to clean up after them.

That alone cuts llc -O0 codegen time by 4.5% on lld/ELF/Driver.cpp, with .text size mostly unchanged.
A follow-up that lowers PHIs into the stack slots keeps the same time saving and reduces .text section sizeA: .text -1.10% for Driver.cpp and -1.89% for ScalarEvolution.cpp.

My prototype migrates X86 (24 updated tests) and AArch64 (9 updated tests), and adds roughly 450 lines under llvm/include and llvm/lib.
It is up for preview at [RegAllocFast] Consume SSA MachineIR, absorbing PHI and two-address lowering by MaskRay · Pull Request #6 · MaskRay/llvm-project · GitHub.
The remaining targets should be straightforward. AMDGPU needs new anchors for two of its passes first, which is the main open question below.

Why absorb the two passes

RegAllocFast is block-local: it keeps nothing in registers across block boundaries, so every value live across one gets a dedicated stack slot, spilled at its definition and reloaded where used.
No liveness analysis, no live-range splitting, no interference graph, and no RegisterCoalescer.
The only coalescing is its own copy hint: allocating a COPY’s source, it prefers the destination’s already-assigned register and erases the copy when both ends land in the same one.

The two passes are 3.8-4.1% of llc -O0 time (-time-passes on
lld/ELF/Driver.cpp and ScalarEvolution.cpp: Two-Address 3.1-3.3%,
PHIElimination 0.6-0.8%).
The two passes were designed for a smart allocator, RegAllocGreedy, and RegAllocFast then has to undo most of it:

• PHIElimination isolates every PHI through a fresh virtual register:
  %incoming = COPY %src in each predecessor and %dst = COPY %incoming at the
  top of the block. That is the correct conservative lowering — it makes the
  lost-copy and swap problems impossible without splitting edges — but it
  produces copy chains whose only hope of disappearing is the copy hint.
• TwoAddressInstructionPass inserts a copy for every tied operand it cannot
  commute or convert to three-address, which register allocation then tries to
  fold away.

Neither pass can tell which of those copies are needed, because neither has liveness.
The allocator does: it knows which values are block-local and which physical register each value is in at each point.
A tied use that dies at its instruction simply takes over the tied def’s register.
And a PHI, where cross-block values live in dedicated slots, is not a register question at all — it is a question about which slot each incoming value is written to.

What the allocator takes over

Three things, in one SSAInput mode selected per function.

1. PHIs

Step 1 — isolation, exactly as PHIElimination does it.
A pre-pass creates the incoming register, inserts the destination copy at the top of the block and one source copy per distinct predecessor, and erases the PHI.
The incoming register is read at exactly one place, so a copy on a not-taken edge cannot be observed: no edge splitting, no lost-copy or swap problem.

Step 2 — lower PHIs into the stack slots the allocator already owns.
Every edge transfer is still a COPY. What changes is how many copies a PHI
needs and which slots its values land in. For a loop-carried PHI in %loop with
predecessors %entry and %latch:

%p = PHI %init, %entry, %next, %latch

	selected when	copies emitted	slots for the web
A	%next is defined in %latch, dies there, and %p is not read there	none	1
B	A does not apply	%p = COPY %next at the end of %latch	1
C	writing %p’s slot in %latch could be observed on another edge out of %latch	%incoming = COPY %next in each predecessor, plus %p = COPY %incoming at the top of %loop	2

A gives %next the destination’s slot, so the spill %next needed anyway
is the edge transfer — no copy, no extra slot, no extra store.

B emits the copy and retargets the PHI’s operand to %p, so the PHI
stops counting as a cross-block use of %next. That second half is what makes it
cheap: without it %next keeps a slot of its own and is spilled into it for
nothing; with it %next becomes block-local and the copy hint folds the COPY
into the store %p needed anyway. A and B usually emit identical machine code,
and B costs at most one register-to-register move when the hint misses.

C is step 1’s isolation, kept as the fallback. It is the only case needing
two slots, and it is what PHIElimination does for every PHI today:

%loop, cases A and B            %loop, case C
  movl -4(%rsp), %eax             movl -8(%rsp), %ecx
  movl -8(%rsp), %ecx             movl -4(%rsp), %eax    # reload %incoming
                                  movl %eax, -12(%rsp)   # %p = COPY %incoming
  cmpl %ecx, %eax                 cmpl %ecx, %eax

One extra store on every iteration, and -4(%rsp) holds the whole web in A and
B but only %incoming in C, with %p needing -12(%rsp) of its own. The
.text win in the table below is A and B displacing C.

A and B write the destination’s slot inside a predecessor, so both need an
argument that the write cannot be observed on an edge leaving that predecessor
for anywhere but the PHI’s block. That is a cheap, conservative, one-sided test:
every read of the destination is inside the PHI’s own block and none of them is
a PHI operand; or the predecessor cannot reach those reads; or the predecessor
has no other successor. A PHI that fails it takes C.

Where several PHIs share an edge, the copies are ordered so a destination is
written only once nothing left reads it, with a fresh register breaking a cycle
— the classic parallel-copy sequentialization, which is what makes the swap
shapes come out right.

Step 2 is where the code-size win is, and the part that carries a real correctness argument.

2. Tied operands

A tied use that dies at the instruction takes over the tied def’s register: zero copies.
One that lives on, or that reads a subregister, is copied into the def’s register before the instruction, matching what TwoAddressInstructionPass would have emitted.
Copy-hint tracing follows ties as chain links, since a def and its tied use share a register, so argument copies feeding two-address chains still fold.
An early-clobber def whose tied value is also read through another operand keeps that operand in a distinct register and gets the copy, preserving the early-clobber guarantee.

3. REG_SEQUENCE and INSERT_SUBREG

Expanded to subregister COPYs in a pre-pass, mirroring the lowering
TwoAddressInstructionPass performs today; without this they survive to the
AsmPrinter, which cannot print them. These two are the complete list — that pass
expands REG_SEQUENCE, rewrites INSERT_SUBREG as a COPY, and touches no
other subregister pseudo.

Numbers

llc -O0 -filetype=obj wall time on an otherwise idle i7-14700K pinned to one P-core, Release build without assertions.

Step 1 (isolation only), x86-64:

	codegen time	.text
lld/ELF/Driver.cpp, clang -O0 IR	276.2ms → 263.8ms (-4.5%)	+0.00%
lld/ELF/Driver.cpp, -O2 IR	170.5ms → 165.7ms (-2.8%)	+0.05%
ScalarEvolution.cpp, -O2 IR	346.2ms → 333.8ms (-3.6%)	+0.16%

Code size is a wash, as it should be: the lowering is the one PHIElimination already performed.
The deltas up to +0.16% come from the allocator creating its
incoming registers in a different order, shifting virtual register numbering and
with it the allocator’s choices.

On clang -O0 IR the 4.5% saved exceeds the passes’ own 4.1% share — the allocator no longer folds away the copies TwoAddressInstructionPass inserted, and there are two fewer passes for the pass manager, and the machine verifier in an assertions build, to run. On the optimized-IR inputs it falls a little short, since the pre-pass lowers five to thirteen times as many PHIs.

Step 2 (slot-based PHI lowering). Timing matches step 1 — the slot machinery
adds nothing measurable (Driver.cpp clang -O0 IR: 276.6ms → 264.2ms, the same
-4.5%) — and the win is code size on PHI-heavy input:

	.text
lld/ELF/Driver.cpp, -O2 IR, x86-64	-1.10%
ScalarEvolution.cpp, -O2 IR, x86-64	-1.89%
ScalarEvolution.cpp, -O2 IR, AArch64	-0.16%

AArch64 gains much less by design: with 31 allocatable GPRs, values survive in registers more often and the copy hint already folds most PHI copies away. Even the -0.16% depends on slot sharing testing slot geometry — equal spill size, alignment and stack ID — rather than requiring identical register classes; with the exact-class test AArch64 measured +0.01%.

llvm-test-suite CTMark at -O0, x86-64: all 10 programs build, run and verify
against their reference output, aggregate .text -0.12% (consumer-typeset
best at -0.53%, lencod worst at +0.02%). That sweep predates the slot-geometry
relaxation above, so it is a conservative figure.

Debug info

Measured on llvm-test-suite CTMark: no significance at -O0 -g but measurably better at -O2 -g -mllvm -regalloc=fast

At -O0 -g (the configuration this ships in): statistically identical. Variables with a location: 153,834 on both sides, per-program equal. Scope coverage 99.9999% both; zero local variables without any location, both. The only delta is that scope byte counts shrink ~0.16% — the code got smaller, coverage stayed flat.

At -O2 -g -regalloc=fast (instruction-referencing LiveDebugValues): the SSA path is better on every program — +0.56pp aggregate variables-with-location coverage (62.54% vs 61.98%), 1,391 more variables carrying locations, and 435 fewer variables with no location at all; lencod is the biggest winner at +1.6pp. That direction makes sense: fewer inserted copies and tier-A slot sharing mean a value sits in one register or one stable stack slot for longer, so its location ranges extend instead of fragmenting. Caveat: this arm covered 8 of 10 programs (7zip and ClamAV were lost to the class-mismatch crash); the 10/10 re-run happens right after the fix lands.

Opting in, and the migration path

The mode is per target and initially off by default:

// In the target's TargetMachine constructor
setEnableSSAFastRegAlloc(true);

Both codegen pipelines resolve it through one predicate,
useSSAFastRegAlloc(const TargetMachine &), which also applies the hidden
-regalloc-fast-ssa flag, so the legacy and new pass managers cannot drift:

if (!useSSAFastRegAlloc(*TM)) {
  addPass(&PHIEliminationID);
  addPass(&TwoAddressInstructionPassID);
}
addRegAssignAndRewriteFast();

-regalloc-fast-ssa=0 and -regalloc-fast-ssa=1 override the target default in either direction.
With =0 the output is byte-identical to today’s pipeline, which makes any suspected regression a one-flag bisect.

The staged plan:

1. Plumbing plus step 1, with no target opting in. The mode is reachable
   only through the flag, so the patch is NFC: no in-tree configuration takes
   the new path, and the only edits to existing tests add RUN lines passing the
   flag.
2. Step 2, the slot-based PHI lowering, as a separate review.
3. Targets opt in one at a time. Each is a one-line target change plus regenerating that target’s -O0 tests. X86, AArch64, then other targets.
4. Once all in-tree targets have opted in, SSAInput becomes unconditional, the two passes leave the -O0 pipeline for good, and RegAllocFast will declare SSA as a required MIR property instead of tolerating both shapes.

What a target maintainer should check before flipping the switch:

• Passes anchored on the two pass IDs. This is why AMDGPU has migration difficulty: it inserts SILowerControlFlow relative to PHIEliminationID at
  two sites (AMDGPUTargetMachine.cpp:1815 and :1841) and SIWholeQuadMode
  relative to TwoAddressInstructionPassID (:1817), and documents an
  SI_ELSE tied-operand dependency on their timing. Those anchors need
  somewhere else to attach before AMDGPU can opt in.
• Anything between ISel and register allocation that assumes non-SSA MIR, or
  that assumes tied operands have already been rewritten.
• Tests that pin the -O0 pass list or use -start-after on either pass.
  Those should pin the standard pipeline with -regalloc-fast-ssa=0.

Testing

• All of llvm/test passes with the mode enabled (76.7k tests), and again with
  it off, which is what makes step 1 NFC.
• CTMark at -O0 builds, runs and verifies, 10/10.
• Sweeping llvm/test/CodeGen/AArch64 at -O0 with -verify-machineinstrs
  gives identical pass/fail on both paths across 3160 files.
• New tests drive the mode with -regalloc-fast-ssa: the PHI shapes isolation
  has to keep apart, PHIs reached over an exceptional edge, the tied-operand
  cases including a hint traced through a two-address tie, and the
  REG_SEQUENCE expansion. From MIR, since instruction selection does not
  produce them: PHI operands carrying a subregister index, an undef flag or a
  repeated predecessor; a tied use of a subregister; a tied use whose value the
  early-clobber def also reads through another operand; and INSERT_SUBREG on
  an undef base.

AMDGPU pipeline challenges

Two AMDGPU passes are anchored on the pass IDs this proposal removes, at four sites across both pass managers:

pass	fast pipeline	optimized pipeline
SILowerControlFlow	after PHIEliminationID (AMDGPUTargetMachine.cpp:1815)	after PHIEliminationID (:1841, :2609 NPM)
SIWholeQuadMode	after TwoAddressInstructionPassID (:1817, :2550 NPM)	after MachineSchedulerID (:1851, :2620 NPM)

This is only blocker to remove the classical (non-SSA) code path, though two observations that may make this easier than it looks, both of which I would like AMDGPU maintainers to confirm:

• The “before TwoAddressInstructions” half of that comment appears stale. SI_ELSE (SIInstructions.td:604) declares no Constraints, and neither does CFPseudoInstSI (SIInstrFormats.td:284), so it has no tied operand left for TwoAddressInstructionPass to process. Running -run-pass=twoaddressinstruction over lower-control-flow-live-intervals.mir leaves %3 = SI_ELSE killed %2, %bb.1 untouched, inserting copies only for genuinely two-address instructions elsewhere in the function.
• The “after phi elimination” half may be satisfiable on SSA MIR. emitElse inserts the S_OR_SAVEEXEC at MBB.begin() because it must precede “phis and any spill code inserted before the else”. Pre-allocation there is no spill code, and the PHIs it wants to precede are PHIElimination’s own copies, which the SSA mode never creates. If the insertion point becomes SkipPHIsAndLabels(MBB.begin()), the pass may simply run before the allocator on SSA input.

If both hold, AMDGPU’s migration is a re-anchor rather than a redesign.

Future direction

SSA input makes some optimizations reachable, but they may not be a good compile-time tradeoff. None of this is proposed here.

PHIElimination and TwoAddressInstructionPass get simpler: Once every in-tree target has opted in, they run only in the optimized pipeline, where their analyses always exist — so they can require LiveVariables instead of using it when available.

LLM Disclosure

A great many tokens using both Opus 5 and Fable 5 over multiple days.
The model was used as a reading and cross-checking partner over many rounds.
That went into working through the SSA-destruction literature (Briggs et al. on the lost-copy and swap problems, Sreedhar et al.'s Methods I-III, and the PHI-isolation and parallel-copy sequentialization material in SSA-based Compiler Design), reading what PHIElimination, TwoAddressInstructionPass and RegAllocFast actually do in tree rather than what the folklore says they do, and arguing out which of those designs suits an allocator that has neither liveness nor a coalescer.

[efriedma-quic]

Are you sure AMDGPU is the only target that has potential porting issues here? RISC-V also adds a couple passes in addRegAssignAndRewriteFast().

[MaskRay]

I have ported RISC-V in my prototype as well, i.e. setEnableSSAFastRegAlloc(true);.

RISCVPassConfig::addRegAssignAndRewriteFast builds

RegAllocFast<filter=onlyAllocateRVVReg, ClearVirtRegs=false>   # vector registers
RISCVInsertVSETVLI
RegAllocFast                                                   # everything else

so only the first run ever sees SSA MachineIR, and that run allocates just the RVV classes. This run lowers all PHI nodes and vector tied operands, and the second run lowers non-vector tied operands.

This means SSAInput becomes unconditional is not a reachable goal.

[aengelke]

This is an interesting proposal, about which I currently have mixed feelings. The proposal does two things at once: merge TwoAddress into RegAllocFast and merge PHIElim into RegAllocFast.

O0 IR from typical front-ends (e.g. Clang) typically has very few PHIs, so PHIElim is fairly cheap (maybe it could be made even cheaper for that case, I don’t think I looked at that deeply in the past).

I’m wary of introducing complex lowering logic for PHIs in RegAllocFast that our typical front-ends (Clang, Flang, likely also rustc), through which the back-end receives most real-world coverage, don’t exercise by default, especially as such bugs only tend to show under rare circumstances (high register pressure, etc.). This will only show in more unusual configurations (compilers producing better IR directly or JIT compilers) and has potential of being or becoming subtly broken by other changes without us noticing that quickly. In TPDE we implemented a similar algorithm for lowering PHIs and it took quite a while to iron out bugs that occurred only under very specific circumstances.

Therefore: how much could we gain by folding TwoAddress alone? That should give most of c-t benefits while introducing only little further complexity.

Other question: how does the code handle critical edges?

[MaskRay]

TwoAddressInstruction alone. Essentially the whole compile time win.
Folding TwoAddressInstruction alone gets ~90% of the -O0 win.

However, absorbing PHIElimination as well is worth a further ~0.4pp of -O0 compile time,
and it is the precondition for the slot-based lowering, which is where the .text win is.

Critical edges. None are split — and PHIElimination does not split any at -O0 either:
its SplitPHIEdges is gated on LiveVariables || LiveIntervals (PHIElimination.cpp:245)
and the fast pipeline computes neither, so edge splitting there is a coalescer-quality
heuristic that never runs in this configuration.

Correctness comes from isolation instead: the incoming register is read at exactly one
place, the copy at the top of the PHI’s block, so a write on a not-taken edge cannot be
observed — the extra name does what the extra block would have done. The logic is not
complex at all Here is the complete algorithm used by my Step 1:

void RegAllocFastImpl::lowerPHIs(MachineFunction &MF) {
  SmallPtrSet<MachineBasicBlock *, 8> InsertedInto;
  for (MachineBasicBlock &MBB : MF) {
    // Not a range over MBB.phis(): the destination copy lands at the end of
    // that range, and iterating it would walk into the copy.
    while (!MBB.empty() && MBB.begin()->isPHI()) {
      MachineInstr &PHI = *MBB.begin();
      Register Dst = PHI.getOperand(0).getReg();
      Register Incoming = MRI->createVirtualRegister(MRI->getRegClass(Dst));
      TII->createPHIDestinationCopy(MBB, MBB.SkipPHIsAndLabels(MBB.begin()),
                                    PHI.getDebugLoc(), Incoming, Dst);
      InsertedInto.clear();
      for (unsigned I = 1, E = PHI.getNumOperands(); I != E; I += 2) {
        const MachineOperand &SrcMO = PHI.getOperand(I);
        MachineBasicBlock &Pred = *PHI.getOperand(I + 1).getMBB();
        // Duplicate predecessors carry the same value; one copy suffices.
        if (!InsertedInto.insert(&Pred).second)
          continue;
        // No debug location: the copy lands in another block than the PHI.
        TII->createPHISourceCopy(
            Pred, findPHICopyInsertPoint(&Pred, &MBB, SrcMO.getReg()),
            DebugLoc(), SrcMO.getReg(), SrcMO.getSubReg(), Incoming);
      }
      PHI.eraseFromParent();
      ++NumPHIsViaVReg;
    }
  }
}

Byte-identical .o on -O0 IR but slightly regresses .text size on -O2 IR:

┌───────────────────────────────────┬──────────┬────────┬───────────────────┐
│              module               │ baseline │ step 1 │         Δ         │
├───────────────────────────────────┼──────────┼────────┼───────────────────┤
│ Driver.cpp, clang -O0 IR          │ 206031   │ 206031 │ byte-identical .o │
│ ScalarEvolution.cpp, clang -O0 IR │ 389076   │ 389076 │ byte-identical .o │
│ Driver.cpp, -O2 IR                │ 414118   │ 414534 │ +416 B (+0.10%)   │
│ ScalarEvolution.cpp, -O2 IR       │ 851137   │ 851921 │ +784 B (+0.09%)   │
└───────────────────────────────────┴──────────┴────────┴───────────────────┘

On PHI elimination coverage. I did catch three issues when working on the slot-sharing optimization (custom interference test),
every one found only by running CTMark built -O2 -g -mllvm -regalloc=fast — lit, the verifier and .text diffs
were blind to all three.

Revised staging:

• Absorb PHIElimination and TwoAddress. Folding TwoAddress alone would regress nothing at
  all, but it leaves the last 0.4pp on the table and does not get us to the lowering below,
  so I would rather pay the +0.10% once, visibly, here.
• Migrate every non-AMDGPU target and enable regalloc-fast-ssa by default.
• (With risk) Slot-based PHI lowering: cases A and B from the table in the first post — the copy that
  defines the destination directly, then the source taking the destination’s slot. As you
  mentioned, there is risk, and this is the only step that carries it.

Agreed on your last point — I’m not claiming a substantially faster -O0 back end. ~4% is
the ceiling and step 1 reaches it.

[aengelke]

In that case, I think a better path forward is to first teach RegAllocFast (only) to lower tied-defs, allowing to eliminate TwoAddress from the O0 pipeline. That should be fairly straight-forward, easy to review, and receive good test coverage through our front-ends. I think this is a good idea.

Teaching RegAllocFast to also lower PHIs should be a second step and be evaluated separately and solely on the merits on the top of the first step. I’m unconvinced here: the compile-time gains seem rather low (and maybe we could improve PHIElim) and the size-text improvements on O0 IR are barely significant (<0.1%), but this introduces some new complex lowering path that will only be fully exercised by niche/JIT compilers. Our O0 back-end already has a somewhat bad reputation, especially with that group of users, and I don’t think “adding spurious miscompiles for complex IR” is something we should add to that list. size-text changes on optimized IR with RegAllocFast are, IMO, irrelevant, as the baseline is extremely bad due to extensive spilling.

Regardless of whether we add SSA support to RegAllocFast, I think these two changes should be separate PRs.

[MaskRay]

Then Revised staging in my previous comment is still applicable

<---------- new comment: net increase on lines of code: ~180
* Absorb PHIElimination and TwoAddress. Folding TwoAddress alone would regress nothing at
  all, but it leaves the last 0.4pp on the table and does not get us to the lowering below,
  so I would rather pay the +0.10% once, visibly, here.

* Migrate every non-AMDGPU target and enable `regalloc-fast-ssa` by default.

* (With risk) Slot-based PHI lowering: cases A and B from the table in the first post — the copy that
  defines the destination directly, then the source taking the destination’s slot. As you
  mentioned, there is risk, and this is the only step that carries it.

However, -regalloc-fast-ssa is no longer appropriate. New option name: regalloc-fast-tied.

Slot sharing optimization (both compile time and code quality) requires access to RegAllocFastImpl::getStackSpaceFor, which genuinely needs the register allocator.

[qcolombet]

Hi @MaskRay ,

Given the impact of such a change on all backends, I would be opposed to it.

More precisely, I’m opposed to changing the default pipeline under the hood at this point in time, but having an SSA based regalloc sounds like a good idea to me.

Could we work towards a separate ssa based pipeline?

And by the way the baseline doesn’t need to be RegAllocFast. You’re probably better starting from scratch actually.

I think focusing on O0 is fine, but eventually you’ll have to think about doing scheduling on SSA as well, hence handling copies and so on.

Cheers,

-Quentin

[efriedma-quic]

What makes a “separate SSA based pipeline” different from what we currently do? Are you imagining a representation where we do SSA numbering of physical registers? I guess that’s something we could do, but I’m not sure how that’s related to this proposal, or how it’s even helpful at -O0.

[MaskRay]

Could you elaborate your concern and why a separate pipeline is needed?

(Step 1) https://github.com/MaskRay/llvm-project/commits/fastra-tied/ adds only ~140 lines to RegAllocFast.cpp, absorbing TwoAddressInstructionPass and achieving the main compile time gain. Very few in-tree tests need updating.

(Step 2) Absorbing PHIElimination and implementing slot-based PHI lowering. Once implemented, RegAllocFast’s input will be SSA MachineIR.

[aengelke]

@MaskRay

(Step 1) Commits · MaskRay/llvm-project · GitHub adds only ~140 lines to RegAllocFast.cpp, absorbing TwoAddressInstructionPass and achieving the main compile time gain. Very few in-tree tests need updating.

Thanks, I think this looks good. Do you have compile-time numbers on this patch compared to the patch that also merges PHIElim?

@qcolombet

I’m opposed to changing the default pipeline under the hood at this point in time, but having an SSA based regalloc sounds like a good idea to me.

Could we work towards a separate ssa based pipeline?

I think this proposal is not about good SSA-based regalloc as described in the papers from you and others; this seems to be primarily mechanical change for RegAllocFast to not require separate lowering passes with some minor enhancement bolted on the top of it. The proposal doesn’t seek to fundamentally change the way registers are allocated.

I don’t think anybody has seriously proposed implementing a good SSA-based regalloc in LLVM. I’m also unsure whether it’s worth the effort. For O0 it most probably isn’t. For optimized RegAlloc, a proper implementation would be a large amount of effort just to get something that doesn’t regress too much from the many heuristics in RegAllocGreedy. Algorithmically, SSA-based regalloc replaces one hard problem (register assignment) with another (resolving shuffles afterwards), spilling and coalescing remain.

For RegAllocFast in particular, I see no need for separating the pipeline, as it is already isolated and basically it’s own pipeline already. For the other register allocators, I agree that if somebody implements fully SSA-based regalloc it should be a separate pipeline, but that’s not what’s proposed here.

[MaskRay]

Still proceeding, just slowly. I need to read RegAllocFast closely enough to be confident about the change.
(
I am also improving documentation ([RegAllocFast] Document the allocation algorithm. NFC by MaskRay · Pull Request #219835 · llvm/llvm-project · GitHub) and fixing a minor bug [RegAllocFast] Give an undef tied use the register of its tied def by MaskRay · Pull Request #222249 · llvm/llvm-project · GitHub (clang -fcf-protection=return on setjmp/longjmp) during the slow process.)

“SSA form” in the title is only about the input the allocator accepts, so that TwoAddressInstruction (and PHIElimination, Step 2, if deed useful) can leave the -O0 pipeline. RegAllocFast keeps its backward per-block scan.

---

Step 1 [RegAllocFast] Lower tied operands, absorbing TwoAddressInstructionPass (RegAllocFast.cpp net +167 lines)

An earlier experiment

Config	instructions:u	σ	max-rss
stage1-O0-g	-0.82%	50	-0.05%
stage1-aarch64-O0-g	-0.44%	22	-0.04%
stage2-O0-g	-0.82%	37	+0.09%

[qcolombet]

The thing that worries me is that RegAllocFast keeps being augmented (although slowly) with a bunch of capabilities that complicates his whole design (to be frank the design is/was rather simple).

The first part may be fine given the size of the patch, but the more we “absorb” in that pass the more complex it becomes.

Therefore I’m questioning if it is even the right thing to do as opposed to having a new allocator. Ultimately, my worries is that RegAllocFast was not meant to do that and is used by default for a lot of targets so the chances we break someone is high.

[qcolombet]

@MaskRay

I need to read RegAllocFast closely enough to be confident about the change.

That illustrates my worries

[MaskRay]

I think RegAllocFast grows over the years mostly because the input MIR gets richer (some seem AMDGPU specific) (BUNDLE, INLINEASM_BR, DBG_VALUE, register-class filtering), necessary performance fixes (dominates, InstrPosIndexes), robustness fixes (getErrorAssignment), infrastructure (new pass manager).

It’s indeed unfortunate that such a basic block-local backward-scan allocator requires 2000 lines, but these are the cost of being a usable allocator at all within LLVM…

In theory, a minimum allocator just needs to handle defs and uses. However, within LLVM, we need these steps:

  // Backwards, a def frees a register and a use occupies it. The phases:
////////// defs
  // * pre-assigned physreg defs
  // * virtual register defs
  // * free the def operands' registers
  // * displace registers clobbered by regmasks

////////// uss
  // * pre-assigned physreg uses
  // * virtual register uses, inserting reloads ***and tied-operand copies***
       <--------- absorbed TwoAddressInstructionPass is here
  // * undef uses

/////// early-clobber def
  // * free early-clobber defs

The absorbed TwoAddressInstructionPass will be added to the “virtual register uses” step. The current pipeline, where tied operands are handled before RegAllocFast, is actually unnatural.

[qcolombet]

That part sounds fine, the step 2 (phi elimination) is not as clear cut.