Page MenuHomePhabricator

[SelectionDAGISel] split critical indirect edges from callbr w/ outputs
AbandonedPublic

Authored by nickdesaulniers on Nov 15 2022, 4:52 PM.

Details

Summary

Towards the goal of supporting outputs from callbr in its indirect
successors, split indirect edges that are critical when there are
outputs.

There are 2 invariants of LLVM that make this change necessary. Consider
a callbr with outputs that have physical register constraints, where the
indirect destination tries to use the result in a PHI.

The first constraint is that PHIs in MachineIR (MIR) do not support a
mix of physreg and virtreg operands. Physregs MUST be COPY'd to a
virtreg BEFORE they can be used in a PHI.

The second constraint is that PHIs MUST occur before non-PHIs in
MachineBasicBlocks. So where do we place the COPY, in the predecessor or
the successor? A: Neither. We split the "critical edge" that occurs when
the predecessor has multiple successors and the successor has multiple
predecessors. In a follow up patch, we could then place the COPY in
that newly synthesized block, but this patch is just the critical edge
splitting.

This change was done prior to support for outputs along indirect edges,
because the changes to existing tests for outputs along the direct edge
are quite noisy and tricky to review itself.

Labels can be passed to asm goto in BOTH the input operands AND goto
labels lists, example:

foo: asm goto ("# %0 %1"::"i"(&&foo)::foo);

This change has the implications that in the inline asm, the above
parameters need not compare equal; the goto label might refer to the
block synthesized when we split the critical edge while the input
operand will refer to the final destination. IMO, you're asking for
trouble if you have code doing this, but this patch will very much
change the codegen of LLVM in such an observable way. We initially
decided not to do this during the initial implementation of support for
outputs along "fallthrough" (aka "direct") edges from callbr, but
support for outputs along indirect edges is more valuable (subjective)
than labels passed simultaneously as input operands and goto labels
comparing equal. Also, this is how GCC chose to implement support for
outputs along indirect edges. Document this behavior change.

SelectionDAGISel did pro-active critical edge splitting as of
commit 8ee913d83b17 ("[IR] Remove Constant::canTrap() (NFC)").

Also, it might seem like we could also avoid splitting the
critical+indirect edge when there's no physreg defines, but it helps the
later patch for outputs along indirect edges not have to special case
virtreg COPYs vs physreg COPYs.

Link: https://github.com/llvm/llvm-project/issues/53562

Diff Detail

Unit TestsFailed

TimeTest
60 msx64 debian > LLVM.CodeGen/AArch64::callbr-split-critedge.ll
Script: -- : 'RUN: at line 2'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/llc /var/lib/buildkite-agent/builds/llvm-project/llvm/test/CodeGen/AArch64/callbr-split-critedge.ll -O0 -stop-after=finalize-isel -o - | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/llvm/test/CodeGen/AArch64/callbr-split-critedge.ll

Event Timeline

nickdesaulniers requested review of this revision.Nov 15 2022, 4:52 PM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptNov 15 2022, 4:52 PM
arsenm added a subscriber: arsenm.Nov 15 2022, 4:55 PM
arsenm added inline comments.
clang/docs/ReleaseNotes.rst
187

Typo garunteed

nickdesaulniers marked an inline comment as done.Nov 15 2022, 4:59 PM
nickdesaulniers added reviewers: arsenm, nikic.
nickdesaulniers removed a subscriber: arsenm.
  • another typo in release notes

You can't put transforms that are necessary for correctness in CodeGenPrepare; it isn't enabled at -O0.

nickdesaulniers planned changes to this revision.Nov 16 2022, 9:33 AM

the question "when is the best time to split critical edges" is perhaps important to consider.

You can't put transforms that are necessary for correctness in CodeGenPrepare; it isn't enabled at -O0.

Of course...

ok overnight I was thinking maybe we do the critical edge splitting on the MBB level based on if the BB has a critical edge (in SelectionDAGBuilder::visitCallBr). Then I think we can remove the isInlineAsmBrIndirectTarget guard from MachineBasicBlock::canSplitCriticalEdge (I wonder if we always eagerly split critical edges, if we might be able to remove the MachineBasicBlock::IsInlineAsmBrIndirectTarget machinery outright, but that might be too aggressive). Let me play with doing the splitting in SelectionDAGBuilder::visitCallBr.

in SelectionDAGBuilder::visitCallBr

So the issue I hit immediate is that the ValueMap SelectionDAG has maps the indirect destination BB to the original MBB; I can't split the edge and have the CallBrInst lower correctly to refer to the synthesized MBB.

I think I can reuse this commit mostly as is, just move it from codegen prepare to another pass.

It looks like indirectbr-expand _is_ enabled at -O0 and is necessary for correctness IIUC. Thoughts on moving this there, and maybe renaming the pass to indirectbr-callbr-expand?

It looks like indirectbr-expand _is_ enabled at -O0 and is necessary for correctness IIUC. Thoughts on moving this there, and maybe renaming the pass to indirectbr-callbr-expand?

Looks like indirectbr-expand isn't run for certain targets...thoughts on where to put this logic?

To me it sounds like the kind of issue we deal with in FinalizeISel to hack around dag limitations

To me it sounds like the kind of issue we deal with in FinalizeISel to hack around dag limitations

I think it would be MUCH better to do this work BEFORE ISEL, otherwise in FinalizeISEL we have to generate bad code then bend over backwards to clean up. If we do this BEFORE ISEL, we get the expected codegen for free.

nickdesaulniers retitled this revision from [CodeGenPrepare] split critical indirect edges from callbr w/ outputs to [SelectionDAGISel] split critical indirect edges from callbr w/ outputs.
nickdesaulniers edited the summary of this revision. (Show Details)
  • move critical edge splitting from CodeGenPrepare to SelectionDAGISel
nickdesaulniers planned changes to this revision.Nov 28 2022, 10:05 AM
nickdesaulniers added inline comments.
llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp
482–483

Rather than scan every Instruction looking for CallBrInst, it would be better to look at the terminator for each BasicBlock.