[RFC] Change MIR to use block arguments instead of phis
Today’s MIR/gMIR represent SSA dataflow the same way as the IR, with
PHI instructions. This RFC proposes to change MIR away from PHIs, and
towards block arguments, as MLIR uses. This will help make a few
register allocation infrastructure problems easier for AMDGPU. With
block arguments, no explicit instruction exists in successor blocks,
but predecessors need to explicitly represent what it is passing to a
specific successor for a value.
**An example:**
``` define i32 @test(i1 %c, i1 %d, i1 %e, i32 %a, i32 %b) { entry: br i1 %c, label %hdr, label %other
hdr: %s = add i32 %a, %b %t = sub i32 %a, %b br i1 %d, label %left, label %right
other: br i1 %e, label %left, label %right
left: %l1 = phi i32 [ %s, %hdr ], [ %a, %other ] %l2 = phi i32 [ %t, %hdr ], [ %b, %other ] %lr = add i32 %l1, %l2 ret i32 %lr
right: %r1 = phi i32 [ %t, %hdr ], [ %b, %other ] %r2 = phi i32 [ %s, %hdr ], [ %a, %other ] %rr = sub i32 %r1, %r2 ret i32 %rr } ```
Today with MIR, the phi values pass through essentially as-is:
``` // ... bb.3.left: %2:gr32 = PHI %9, %bb.2, %0, %bb.1 %3:gr32 = PHI %10, %bb.2, %1, %bb.1 ...
bb.4.right: %4:gr32 = PHI %10, %bb.2, %1, %bb.1 %5:gr32 = PHI %9, %bb.2, %0, %bb.1 // ... ```
With block arguments, this becomes
``` bb.1.hdr: successors: %bb.3, %bb.4 %0:gr32 = ADD32rr %9, %10, implicit-def dead $eflags ; %s %1:gr32 = SUB32rr %9, %10, implicit-def dead $eflags ; %t TEST8ri %11, 1, implicit-def $eflags ; 2 successors receive block arguments from here, so 2 SUCC_ARGS instructions SUCC_ARGS %bb.3, %0, %1 ; hdr -> left : forward {%s, %t} SUCC_ARGS %bb.4, %1, %0 ; hdr -> right : forward {%t, %s} JCC_1 %bb.3, 5, implicit $eflags JMP_1 %bb.4
bb.2.other: successors: %bb.3, %bb.4 TEST8ri %12, 1, implicit-def $eflags SUCC_ARGS %bb.3, %9, %10 ; other -> left : forward {%a, %b} SUCC_ARGS %bb.4, %10, %9 ; other -> right : forward {%b, %a} JCC_1 %bb.4, 4, implicit $eflags JMP_1 %bb.3
bb.3.left: arguments: %2:gr32, %3:gr32 %15:gr32 = ADD32rr %2:gr32, %3:gr32, implicit-def dead $eflags ... bb.4.right: arguments: %4:gr32, %5:gr32 %14:gr32 = SUB32rr %4:gr32, %5:gr32, implicit-def dead $eflags ```
**Motivations:**
1. For control flow lowering, AMDGPU has to insert pseudoinstructions
in the block prolog which logically execute before the phis. However,
there is a structural requirement for phis to be clustered at the top
of the block. We currently have a hacky lowering pass which forcibly
reorder the prolog instructions in front of the lowered phis, which is
ugly. If there are no phi instructions, block prologs can naturally be
placed at the top of blocks.
2. Moves the instruction placement to where CodeGen logically reasons
about it. This moves MIR closer to how liveness is already represented
in `LiveIntervals`. Typically `LiveIntervals` are computed after SSA
deconstruction at the start of the register allocation
pipeline. LiveIntervals maintains a pseudo-SSA value numbering system,
and some value defs are PHIs which do not have a corresponding
instruction. This is logically the same thing as block arguments. As
such, this also makes it less awkward to use LiveIntervals in SSA
passes, where there is a physical instruction present for the PHI
defs.
**Implementation details**
In MLIR, like LLVM IR, there is a single terminator instruction for a
basic block. In MLIR, the successor arguments are owned by the
terminator instruction. That’s not directly translatable to MIR; there
can be 0 or multiple true terminator instructions, and every target
uses its own set.
What I’ve implemented is a `SUCC_ARGS` pseudoinstruction. This is a
variadic instruction where the first argument is a reference to a
MachineBasicBlock, and all remaining arguments are a positionally
encoded list of Register values to pass to a successor. This means
each block is expected to have N `SUCC_ARGS` instructions, one per
successor receiving block arguments. The verifier enforces these are
clustered together immediately before the terminator
instructions. This means doing a linear scan through the instructions
to find the argument list for a specific successor, but successor
lists are small in practice. Debug instructions aren’t allowed to
break the sequence, the same as for PHIs today.
MIR implementation costs:
- MachineBasicBlock gains a new `SmallVector` for the block arguments
- MachineRegisterInfo gains a new `DenseMap` from `Register` to
`MachineBasicBlock` to find the defining block.
MIR implementation savings:
- PHIs operand list encodes (value, predecessor) pairs, resulting in
duplicate block references for each PHI. `SUCC_ARGS` encodes the
full edge argument list at once, with only 1 block reference, saving
duplicated `MachineOperand`s encoding the `MachineBasicBlock`
pointer
- No significant compile time change: LLVM Compile-Time Tracker
**API changes**
- Biggest impact is getVRegDef is far more likely to return
null.
- Most of the required code churn is ensuring getVRegDef calls are
guarded.
- Unchecked uses are a latent bug already reachable on main today
using undef operands. It was never guaranteed that this would
succeed, and could return null if there was no defining
instruction. This case was only valid MIR if the use operand had
an undef flag, which was rare and only actively introduced by the
backend during register allocation. Consequently, many pre-RA
passes were broken on a manually specified undef flag. This was
also annoying when using `llvm-reduce`, since it tries putting
undef on every register operand. Now this will fail for any block
argument value, so this needs to be clean.
- This is a straightforward bug fix, testable with the existing
code. As such, I’ve fixed all of these instances already with a
handful of PRs still awaiting review.
- Cases that only care about the defining block should migrate to
use getDefBlock. In-tree code has already converted to do this.
- Change of end-of-block insert point
s/getFirstTerminator/getBlockEndInsertPt/
- Iteration over phis is gone, replaced with iteration over succ_args
in each predecessor.
**Migration path**
This migration turns out to be less daunting than I feared. I have a
working prototype of this conversion implemented. The lit tests suite
is free of crashes (with both SelectionDAG and GlobalISel). I’ve also
completed a clang bootstrap build. Therefore this should move at the
speed of review, which is broken up into about 40-50 PRs, arranged
per-pass/component.
- A new `MachineFunctionProperties` flag is added to indicate use of
block arguments instead of phis, and 2 bringup cl::opts, one to change
SelectionDAG to start emitting block arguments, and the equivalent
flag for GlobalISel.
There is some light codegen churn, mostly neutral with some small
improvements.
**Design variations**
The main decisions I struggled with is the specifics of the SUCC_ARGS
instruction. Some other possibilities:
- Directly encode the successor register mapping in the
`MachineBasicBlock` itself. This is somewhat awkward because of the
register use list implementation. The use list is managed by
MachineOperand, which implies a `MachineInstr` user. It might be
possible to decouple the use list from `MachineOperand` or otherwise
hack it into the block, but it would introduce a special case any
use/user list scan would need to account for.
- Change `SUCC_ARGS` to handle all of the successors in one
mega-instruction, instead of 1 expected `SUCC_ARGS` per successor.
- Make `SUCC_ARGS` a terminator instruction which is required to be at
the start of the terminator sequence. This would avoid some of the
API churn and isn’t that different from the `SUCC_ARGS` cluster
requirement. This has a tradeoff that more target control flow
code would need to be taught to manage these.
- Let the target figure out how to attach these to its
terminators. This seemed impractical
- Syntax for the arguments. This follows current mir precedent of a
named “arguments” field of the block, similar to “liveins”. It is
probably possible to have an inline syntax after the block name
(e.g., bb.1(%0:gpr_32 %bb.1, %1:gpr_64 %bb.2)
**Initial Patches**
Main block argument definition
Pass migration, MachineCSE
Pass migration, MachineLICM