[RFC] Change MIR to use block arguments instead of phis

[arsenm]

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 MachineOperands 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
Function flag
SUCC_ARGS introduction
Main block argument definition
Pass migration, MachineCSE
Pass migration, MachineLICM

[amara]

Do you think this would help our value materialization/localization issue on GlobalISel at all?

[arsenm]

Probably not but I haven’t thought too hard about it

[nikic]

cc @aengelke I think you had opinions on block arguments.

[aengelke]

Some questions:

• How does SUCC_ARGS disambiguate multi-edges with different values? Or will the verifier forbid such cases?
• Could you, for non-experts on AMDGPU, briefly give an example of such pseudoinstructions? (I suppose there’s a reason to not make these “PHI-like”/“executed-on-edge” instructions and permit them before PHIs?)
• Can you add the asymptotic runtimes of certain operations (get incoming value for one predecessor, get all incoming values for one arg/phi, add/remove one arg/phi) before/after to the RFC?

@nikic

cc @aengelke I think you had opinions on block arguments.

• Pro block args: PHIs are not really instructions as they execute on the edge, block args make this clear.
• Pro block args: getting the value for a PHI/arg from a specific predecessor is O(#succs) instead of O(#preds), #succs is usually <=2 while #preds can be huge.
  • This is probably the biggest scalability problem of PHI nodes. This can be reduced to O(log #preds) by sorting predecessors.
• Pro block args: multi-edges can have different values, with PHIs, this needs empty basic blocks (e.g. br cond, block1(a, b), block1(c, d) is typically not expressible with PHIs).
• Contra block args: the terminator operand list become two-dimensional. Here, via n SUCC_ARGS instructions. This may be more annoying to work with and also be more expensive to inspect/modify.
• Contra block args: adding a new PHI node is easy and cheap, adding a new block arg is not, as all predecessor terminators need to be updated.
• Contra block args: checking the merged values is easier with PHIs as all values are stored together and don’t need to be gathered from all predecessors.
• Contra block args: values have a new type of source (block arguments are not instructions), adding new corner cases.

While block arguments are conceptually cleaner, I think a practical implementation also has drawbacks. For LLVM IR, I think the drawbacks are larger than the possible benefits, not mentioning the churn of porting.

For Machine IR, transformations inspecting/modifying PHIs are less common, so it probably doesn’t matter much. In my opinion, this primarily replaces one ugly solution with its set of corner cases with another ugly solution with a different set of corner cases. I’m ambivalent here, but I’d like a confirmation that this doesn’t asymptotically regress performance for large/dense CFGs (something we’re bad at already and shouldn’t make worse).

[arsenm]

@aengelke

• How does SUCC_ARGS disambiguate multi-edges with different values? Or will the verifier forbid such cases?

The verifier forbids it. Each SUCC_ARGS corresponds to one edge, and the verifier enforces no duplicates

@aengelke

• Could you, for non-experts on AMDGPU, briefly give an example of such pseudoinstructions? (I suppose there’s a reason to not make these “PHI-like”/“executed-on-edge” instructions and permit them before PHIs?)

SI_ELSE. It writes the execution mask depending on an incoming condition and returns an SSA register returning the saved exec mask lanes. After the lowered form is hacked into the correct position, it satisfies TargetInstrInfo::isBasicBlockPrologue (which is another wart that needs some proper IR support to replace.

@aengelke

Can you add the asymptotic runtimes of certain operations (get incoming value for one predecessor, get all incoming values for one arg/phi, add/remove one arg/phi) before/after to the RFC?

  Operation                                   PHI              Block args

  -----------------------------------------   -----------      ----------

  Incoming value from one pred, one arg       O(Pred)          O(Succ)

  All incoming values for one arg             O(Pred)          O(Pred * Succ)

  All incoming for every arg of a block       O(Pred * Args)   O(Pred * Succ)

  Add / remove one arg                        O(Pred)          O(Pred)

@aengelke

I’m ambivalent here, but I’d like a confirmation that this doesn’t asymptotically regress performance for large/dense CFGs (something we’re bad at already and shouldn’t make worse).

I did a slop benchmark, and it’s no worse than phi. The block arguments are 14%-ish faster in phi elimination in degenerate cases.

I also realized I made a mistake in my original CTT runs; it was measuring the unused block argument implementation without flipping the switch. With the properly flipped switch the stage1 compile time is improved. There’s some oddities here though (stage1-ReleaseLTO-g is unreasonably fantastic).

Stage 2 has some regressions to investigate, but I haven’t fully updated all the optimization passes yet.

[aengelke]

Thanks. I remain ±0.

@arsenm

Add / remove one arg O(Pred) O(Pred)

Shouldn’t removal be O(Pred*Args) for block args? SUCC_ARGS has a linear list of operands, when removing the first, all following operands need to be moved?

BlockArgDefs should maybe store the argument index, otherwise everything has an extra +O(args) to find the argument index. Not sure if this is needed anywhere, however.

@arsenm

There’s some oddities here though (stage1-ReleaseLTO-g is unreasonably fantastic).

Looks like most of them produce zero-sized binaries, probably it crashes.

@arsenm

Stage 2 has some regressions to investigate, but I haven’t fully updated all the optimization passes yet.

Yeah, the difference is a bit surprising. But I’m also surprised about the rather large size-text changes – I’d be curious about their sources as well.