[llvm][CallBrPrepare] split critical edges

[nickdesaulniers]

Summary

If we have a CallBrInst with output that's used, we need to split
critical edges so that we have some place to insert COPYs for physregs
to virtregs.

Part 2a of
https://discourse.llvm.org/t/rfc-syncing-asm-goto-with-outputs-with-gcc/65453/8.

Test cases and logic re-purposed from D138078.

[nickdesaulniers]

• remove setPreservesAll

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

64

@aeubanks does this delta look correct?

128–129

@aeubanks does this look correct?

[nickdesaulniers]

llvm/test/CodeGen/AArch64/callbr-prepare.ll

140–142

looks like this should have been split...

[nickdesaulniers]

llvm/test/CodeGen/AArch64/callbr-prepare.ll

140–142

oh, right, no uses of the output in the indirect edge.

[aeubanks]

llvm/lib/CodeGen/CallBrPrepare.cpp

59

this needs to be changed to be like this to initialize dom tree (annoying legacy-PM boilerplate)

67–72

both ShouldRun can be static

71

I'd just return the list of CallBrInsts and check if it's empty in the caller, that's a lot more explicit

90–91

moving these variables into the loop makes this less errorprone

114

unnecessary if

128–129

yup, lg

[nickdesaulniers]

• add test case about missing use in indirect branch

[nickdesaulniers]

• INITIALIZE_PASS_DEPENDENCY
• return SmallVector (NVRO)
• mark ShouldRun static
• create new SmallPtrSet, SmallVector per loop iter

llvm/lib/CodeGen/CallBrPrepare.cpp

114

SplitKnownCriticalEdge is fallible. If we don't end up splitting the critical edge, then we shouldn't mark denote that the pass has made changes, right?

[aeubanks]

llvm/lib/CodeGen/CallBrPrepare.cpp

114

there's an assert right above that Synth != nullptr, it doesn't make sense to assert on something then check if it's true

looking at SplitKnownCriticalEdge, it only returns nullptr for the options we're passing it when DestBB->isEHPad(), can that happen?

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

114

there's an assert right above that Synth != nullptr, it doesn't make sense to assert on something then check if it's true

If assertions are disabled, we should still denote correctly whether the pass made modifications.

looking at SplitKnownCriticalEdge, it only returns nullptr for the options we're passing it when DestBB->isEHPad(), can that happen?

If someone was deranged enough to mix C++ structured exception handling with asm goto, perhaps.

int y;
asm goto ("":"=r"(y):::out);
try {} catch (int x) {
out:
}

Though looks like the frontend rejects it: https://godbolt.org/z/dKGnjKK49.

I've also tried:

define i32 @x() {
  %out = callbr i32 asm "", "=r,!i"() to label %direct [label %lp]
direct:
  br label %lp
lp:
  %foo = landingpad { ptr, i32 } cleanup
  ret i32 42
}

which fails the verifier check

Block containing LandingPadInst must be jumped to only by the unwind edge of an invoke.
  %foo = landingpad { ptr, i32 }
          cleanup
LandingPadInst needs to be in a function with a personality.
  %foo = landingpad { ptr, i32 }
          cleanup

I don't know enough about the rest of the EHPad instructions to know if someone could conjure up such an abomination, hence extra checks. "Let's support those if we actually ever do see them in the wild."

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

128–129

Oh, I guess later on (in a later commit) I will need to query DT.dominates. If DOM tree info isn't available, wat do?

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

128–129

Perhaps I would manually need to construct a DomTreeUpdater or something?

I guess there's prior art in SafeStackLegacyPass::runOnFunction

[efriedma]

llvm/lib/CodeGen/CallBrPrepare.cpp

128–129

If you need a domtree, just explicitly request one. With LegacyPM, something like AU.addRequired<DominatorTreeWrapperPass>(); in CallBrPrepare::getAnalysisUsage

[nickdesaulniers]

• require domtree

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

128–129

So I think the issue with AU.addRequired<DominatorTreeWrapperPass>(); is that it might now introduce a Dominator Tree Construction into -O0 pipelines pessimistically.

The idea being that if we scanned the IR for callbrs (which are highly unlikely to exist in most programs outside of the Linux kernel and tcmalloc), we could lazily compute the DOMTree only if we needed (I think that's why SafeStackLegacyPass::runOnFunction has that pattern? cc @ab @pcc @davide @lebedev.ri )

[efriedma]

llvm/lib/CodeGen/CallBrPrepare.cpp

128–129

Oh, hmm, I see what you mean. Yes, that's what the code in SafeStackLegacyPass involving the std::optional<DominatorTree> is doing: if an existing domtree is available, it uses it, otherwise it only computes the domtree if it's needed.

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

128–129

So it looks like there's a tradeoff (FWICT) with that pattern:

+  // It's highly likely that most programs do not contain CallBrInsts. Follow a
+  // similar pattern from SafeStackLegacyPass::runOnFunction to reuse previous
+  // domtree analysis if available, otherwise compute it lazily. This avoids
+  // forcing Dominator Tree Construction at -O0 for programs that likely do not
+  // contain CallBrInsts. It does pessimize programs with callbr at higher
+  // optimization levels, as the DominatorTree created here is not reused by
+  // subsequent passes.

[nickdesaulniers]

• lazily compute domtree

[nickdesaulniers]

Ready for review:

1. https://reviews.llvm.org/D135997
2. https://reviews.llvm.org/D140166
3. https://reviews.llvm.org/D139861
4. https://reviews.llvm.org/D139872
5. https://reviews.llvm.org/D139883
6. https://reviews.llvm.org/D139970
7. https://reviews.llvm.org/D140160
8. https://reviews.llvm.org/D137113
9. https://reviews.llvm.org/D136497

[void]

llvm/lib/CodeGen/CallBrPrepare.cpp

114

I agree with @aeubanks. This sequence looks bad. I know that asserts aren't enabled for a release, but it's either bad or it isn't. If it's bad, we should at the very least report it.

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

114

Is this really better looking?

diff --git a/llvm/lib/CodeGen/CallBrPrepare.cpp b/llvm/lib/CodeGen/CallBrPrepare.cpp
index 9835b5b41e2f..752e2d6f442f 100644
--- a/llvm/lib/CodeGen/CallBrPrepare.cpp
+++ b/llvm/lib/CodeGen/CallBrPrepare.cpp
@@ -117,8 +117,8 @@ bool CallBrPrepare::SplitCriticalEdges(ArrayRef<CallBrInst *> CBRs,
     for (unsigned i : UniqueCriticalSuccessorIndices) {
       BasicBlock *Synth = SplitKnownCriticalEdge(CBR, i, Options);
       assert(Synth && "Failed to split a known critical edge from callbr");
-      if (Synth)
-        Changed = true;
+      (void)Synth;
+      Changed = true;
     }
   }
   return Changed;

[void]

llvm/lib/CodeGen/CallBrPrepare.cpp

114

That's how it's done in other places. E.g. in llvm/include/llvm/CodeGen/LiveVariables.h:

/// removeVirtualRegisterKilled - Remove the specified kill of the virtual
/// register from the live variable information. Returns true if the
/// variable was marked as killed by the specified instruction,
/// false otherwise.
bool removeVirtualRegisterKilled(Register Reg, MachineInstr &MI) {
  if (!getVarInfo(Reg).removeKill(MI))
    return false;

  bool Removed = false;
  for (MachineOperand &MO : MI.operands()) {
    if (MO.isReg() && MO.isKill() && MO.getReg() == Reg) {
      MO.setIsKill(false);
      Removed = true;
      break;
    }
  }

  assert(Removed && "Register is not used by this instruction!");
  (void)Removed;
  return true;
}

It's not particularly satisfying, but at least it appears to be consistent with the rest of the code base.

[nickdesaulniers]

• remove unnecessary if, as per @aeubanks and @void

[void]

In D139872#4014003, @nickdesaulniers wrote:

• remove unnecessary if, as per @aeubanks and @void

I've been thinking about this and I'm not really sure why LLVM hasn't created their own version of assert yet. It could be something as simple as this:

#define LLVM_ASSERT(cond, msg)  if (!cond) assert(false && msg)

But that's a separate issue.

This pass looks okay to me. I'll accept, but I think others who commented should also accept.

[nickdesaulniers]

• rebase, format

[nickdesaulniers]

• rebase

[void]

LGTM. One suggestion that you can ignore if you wish.

llvm/lib/CodeGen/CallBrPrepare.cpp

136

You can iterate over the indirect destinations. Something like:

for (BasicBlock *BB : CBR->getIndirectDests()) {
}

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

136

I would have preferred to use range-for iteration here. IIRC, the issue with that approach was that isCriticalEdge takes an unsigned as the successor number (rather than the BasicBlock successor itself. If it did, that would probably have improved the ergonomics here. Let me know if you think I should add an overload of isCriticalEdge perhaps, or if I missed something else?

[void]

llvm/lib/CodeGen/CallBrPrepare.cpp

136

isCriticalEdge can also take a BB:

llvm/include/llvm/Analysis/CFG.h:
bool isCriticalEdge(const Instruction *TI, const BasicBlock *Succ,
                    bool AllowIdenticalEdges = false);

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

136

Ah, it was SplitKnownCriticalEdge used later outside of this loop that expected the index of the successor number. That's why this loop builds up a vector of indices; the next loop will then split them. So I don't think I can change this first loop, but let me know if I'm still missing something.

[jyknight]

llvm/lib/CodeGen/CallBrPrepare.cpp

75–116

Doesn't seem to add anything to have "ShouldRun" as a separate function. I'd just inline the check here.

If not that, rename it; the name "ShouldRun" is not adding any understandability here.

132–133

I don't understand this comment. With a single loop, if we iterate over the successors in order, and successors 1 and 3 are both to the same block, the MergeIdenticalEdges option should ensure that when we call SplitKnownCriticalEdge on 1, it'll also rewrite 3.

Oh, I see -- I think you needed isCriticalEdge(CBR, i, /*AllowIdenticalEdges=*/true), so that we don't report the edge as critical when it's only used from a single block (and won't split the already-split edge!)

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

132–133

if we iterate over the successors in order, and successors 1 and 3 are both to the same block, the MergeIdenticalEdges option should ensure that when we call SplitKnownCriticalEdge on 1, it'll also rewrite 3.

Correct, see @split_me1 in llvm/test/CodeGen/AArch64/callbr-prepare.ll which covers this part of the code.

I think you needed isCriticalEdge(CBR, i, /*AllowIdenticalEdges=*/true), so that we don't report the edge as critical when it's only used from a single block (and won't split the already-split edge!)

I don't think setting AllowIdenticalEdges to true works. I have vague memories of trying to use it, but I can't recall specifically why I wasn't able to use it and haven't been able to rework this block via setting AllowIdenticalEdges to true.

The comment also mentions SplitCriticalEdge rather than SplitKnownCriticalEdge. That may be an artifact from an earlier revision. At the least, I should fix that part of the comment.

Do you have thoughts on how I could better rephrase the comment block you didn't understand (assuming now that you do)?

Are you asking that I try to use AllowIdenticalEdges set to true?

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

136

It looks like llvm::GetSuccessorNumber could be used. So even if SplitKnownCriticalEdge needs an index, I could use range-for then llvm::GetSuccessorNumber. That may be more readable, but it looks like it would be O(N^2) rather than two sequential O(N) loops? I guess N is likely too small to matter though.

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

132–133

For instance, I would have like for this code to simply have been something like:

for (BasicBlock *BB : CBR->getIndirectDests())
  if (BasicBlock *Synth = SplitCriticalEdge(CBR, GetSuccessorNumber(CBR->getParent(), BB), Options))
    Changed = true;

but that doesn't work, hence the two loops and (obtuse) commentary.

[nickdesaulniers]

• inline ShouldRun, as per @jyknight
• update comment s/SplitCriticalEdge/SplitKnownCriticalEdge/

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

132–133

So I think the issue here is what happens if the direct and indirect destination are the same. Maybe @split_me5 test case added later, where we don't want to split both edges, vs two indirect branches that are the same, in case we'd like to split both of them @split_me1 but only once.

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

132–133

@jyknight what are your thoughts on rewording the comment block as such (sorry, the block has shifted around from edits since your comment; we're referring to the comment blocks in CallBrPrepare::SplitCriticalEdges)

Conceptually, these two loops are doing:

for (BasicBlock *Dest : CBR->getIndirectDests())
  if (BasicBlock *Synth = SplitCriticalEdge(CBR, GetSuccessorNumber(CBR->getParent(), Dest)))
    Changed = true;

But there is a problem resulting in two special cases; a single callbr instruction may have multiple edges to the
same destination.  Consider the first case:

  %0 = callbr ... to label %x [label %y, label %y]

We want to split the edge to %y once, not twice so that both instance of %y go to the new destination.
Now consider the second case:

  %0 = callbr ... to label %x [label %x]

We want to split the indirect edge, but not the direct edge (since the direct edge doesn't
have the problem of where to store copies).  This pair of sequential loops is necessary to
handle what is logically a pass over indirect edges to split them.

(with necessary word wrapping, since I haven't typed it out in code yet) (I would then delete all existing comments in that method).

Thoughts?

[nickdesaulniers]

• refactor and significantly simply CallBrPrepare::SplitCriticalEdges.

@jyknight figured out how to properly use AllowIdenticalEdges together with
MergeIdenticalEdges. Use code he sent me and add a comment.

[jyknight]

Thanks, looks good now!

[nickdesaulniers]

• rebase

[nickdesaulniers]

• final rebase

llvm/lib/CodeGen/CallBrPrepare.cpp

 // destination.
 //
 // This enables us to keep the use of the callbr's Value simple in IR, and
 // expand control flow when necessary at the last minute before instruction
 // selection.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "callbrprepare"
 
 namespace {
 
 class CallBrPrepare : public FunctionPass {
+  bool ShouldRun(const CallBrInst *CBR) const;
+  bool ShouldRun(Function &Fn, SmallVectorImpl<CallBrInst *> &CBRs) const;
+  bool SplitCriticalEdges(ArrayRef<CallBrInst *> CBRs, DominatorTree *DT);
+
 public:
   CallBrPrepare() : FunctionPass(ID) {}
-  static char ID;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
   bool runOnFunction(Function &Fn) override;
+  static char ID;
 };
 
 } // end anonymous namespace
 
 char CallBrPrepare::ID = 0;
 INITIALIZE_PASS(CallBrPrepare, DEBUG_TYPE, "Prepare callbr", false, false)
 
 FunctionPass *llvm::createCallBrPass() { return new CallBrPrepare(); }
 
 void CallBrPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.setPreservesAll();
+  AU.addPreserved<DominatorTreeWrapperPass>();
 }
 
-bool CallBrPrepare::runOnFunction(Function &Fn) {
+bool CallBrPrepare::ShouldRun(const CallBrInst *CBR) const {
+  return CBR && !CBR->getType()->isVoidTy() && !CBR->use_empty();
+}
+
+bool CallBrPrepare::ShouldRun(Function &Fn,
+                              SmallVectorImpl<CallBrInst *> &CBRs) const {
   for (BasicBlock &BB : Fn) {
     auto *CBR = dyn_cast<CallBrInst>(BB.getTerminator());
-    if (!CBR)
+    if (ShouldRun(CBR))
+      CBRs.push_back(CBR);
+  }
+  return CBRs.size();
+}
+
+bool CallBrPrepare::SplitCriticalEdges(ArrayRef<CallBrInst *> CBRs,
+                                       DominatorTree *DT) {
+  bool Changed = false;
+  CriticalEdgeSplittingOptions Options(DT);
+  Options.setMergeIdenticalEdges();
+  SmallPtrSet<const BasicBlock *, 4> Visited;
+  SmallVector<unsigned, 4> UniqueCriticalSuccessorIndices;
+
+  for (CallBrInst *CBR : CBRs) {
+    Visited.clear();
+    UniqueCriticalSuccessorIndices.clear();
+
+    // Do one pass to find the indices of unique indirect successors BEFORE
+    // attempting to split critical edges (otherwise the BasicBlock inserted
+    // in the Visited Set below will not catch duplicates; it would get
+    // updated to the new synthetic block while iterating this loop). Start
+    // at index 1 to avoid the default destination.
+    for (unsigned i = 1, e = CBR->getNumSuccessors(); i != e; ++i) {
+      // The same destination may appear multiple times in a callbr
+      // indirect label list. Also, a phi may list the same predecessor
+      // multiple times as long as they use the same value.
+      //
+      // The CriticalEdgeSplittingOptions option MergeIdenticalEdges will
+      // handle this properly for us, but we don't want to call
+      // SplitCriticalEdge on such repeated destinations more than once.
+      if (!Visited.insert(CBR->getSuccessor(i)).second)
         continue;
-    // TODO: something interesting.
-    // https://discourse.llvm.org/t/rfc-syncing-asm-goto-with-outputs-with-gcc/65453/8
+      if (isCriticalEdge(CBR, i))
+        UniqueCriticalSuccessorIndices.push_back(i);
     }
-  return false;
+    for (unsigned i : UniqueCriticalSuccessorIndices) {
+      BasicBlock *Synth = SplitKnownCriticalEdge(CBR, i, Options);
+      assert(Synth && "Failed to split a known critical edge from callbr");
+      if (Synth)
+        Changed = true;
+    }
+  }
+  return Changed;
+}
+
+bool CallBrPrepare::runOnFunction(Function &Fn) {
+  bool Changed = false;
+  SmallVector<CallBrInst *, 2> CBRs;
+
+  if (!ShouldRun(Fn, CBRs))
+    return Changed;
+
+  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+  DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
+
+  if (SplitCriticalEdges(CBRs, DT))
+    Changed = true;
+
+  return Changed;
 }

llvm/test/CodeGen/AArch64/callbr-prepare.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -callbrprepare -S -o - | FileCheck %s
 
-; TODO: update this test to split critical edges.
 define i32 @test0() {
 ; CHECK-LABEL: @test0(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[OUT:%.*]] = callbr i32 asm "# $0", "=r,!i"()
-; CHECK-NEXT:    to label [[DIRECT:%.*]] [label %indirect]
+; CHECK-NEXT:    to label [[DIRECT:%.*]] [label %entry.indirect_crit_edge]
+; CHECK:       entry.indirect_crit_edge:
+; CHECK-NEXT:    br label [[INDIRECT:%.*]]
 ; CHECK:       direct:
 ; CHECK-NEXT:    [[OUT2:%.*]] = callbr i32 asm "# $0", "=r,!i"()
-; CHECK-NEXT:    to label [[DIRECT2:%.*]] [label %indirect]
+; CHECK-NEXT:    to label [[DIRECT2:%.*]] [label %direct.indirect_crit_edge]
+; CHECK:       direct.indirect_crit_edge:
+; CHECK-NEXT:    br label [[INDIRECT]]
 ; CHECK:       direct2:
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       indirect:
-; CHECK-NEXT:    [[OUT3:%.*]] = phi i32 [ [[OUT]], [[ENTRY:%.*]] ], [ [[OUT2]], [[DIRECT]] ]
+; CHECK-NEXT:    [[OUT3:%.*]] = phi i32 [ [[OUT]], [[ENTRY_INDIRECT_CRIT_EDGE:%.*]] ], [ [[OUT2]], [[DIRECT_INDIRECT_CRIT_EDGE:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[OUT3]]
 ;
 entry:
   %out = callbr i32 asm "# $0", "=r,!i"()
   to label %direct [label %indirect]
 direct:
   %out2 = callbr i32 asm "# $0", "=r,!i"()
   to label %direct2 [label %indirect]
 direct2:
   ret i32 0
 indirect:
   %out3 = phi i32 [%out, %entry], [%out2, %direct]
   ret i32 %out3
 }
+
+; Don't split edges unless they are critical, and callbr produces output, and
+; that output is used.
+; Here we have none of the above.
+define i32 @dont_split0() {
+; CHECK-LABEL: @dont_split0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    callbr void asm "", "!i"()
+; CHECK-NEXT:    to label [[X:%.*]] [label %y]
+; CHECK:       x:
+; CHECK-NEXT:    ret i32 42
+; CHECK:       y:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  callbr void asm "", "!i"()
+  to label %x [label %y]
+
+x:
+  ret i32 42
+
+y:
+  ret i32 0
+}
+
+; Don't split edges unless they are critical, and callbr produces output, and
+; that output is used.
+; Here we have output, but no critical edge.
+define i32 @dont_split1() {
+; CHECK-LABEL: @dont_split1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = callbr i32 asm "", "=r,!i"()
+; CHECK-NEXT:    to label [[X:%.*]] [label %y]
+; CHECK:       x:
+; CHECK-NEXT:    ret i32 42
+; CHECK:       y:
+; CHECK-NEXT:    ret i32 [[TMP0]]
+;
+entry:
+  %0 = callbr i32 asm "", "=r,!i"()
+  to label %x [label %y]
+
+x:
+  ret i32 42
+
+y:
+  ret i32 %0
+}
+
+; Don't split edges unless they are critical, and callbr produces output, and
+; that output is used.
+; Here we have a critical edge along an indirect branch, but no output.
+define i32 @dont_split2() {
+; CHECK-LABEL: @dont_split2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    callbr void asm "", "!i"()
+; CHECK-NEXT:    to label [[X:%.*]] [label %y]
+; CHECK:       x:
+; CHECK-NEXT:    br label [[Y:%.*]]
+; CHECK:       y:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ 0, [[X]] ], [ 42, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[TMP0]]
+;
+entry:
+  callbr void asm "", "!i"()
+  to label %x [label %y]
+
+x:
+  br label %y
+
+y:
+  %0 = phi i32 [ 0, %x ], [ 42, %entry ]
+  ret i32 %0
+}
+
+; Don't split edges unless they are critical, and callbr produces output, and
+; that output is used.
+; Here we're missing a use.
+define i32 @dont_split3() {
+; CHECK-LABEL: @dont_split3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = callbr i32 asm "", "=r,!i"()
+; CHECK-NEXT:    to label [[X:%.*]] [label %v]
+; CHECK:       x:
+; CHECK-NEXT:    br label [[V:%.*]]
+; CHECK:       v:
+; CHECK-NEXT:    ret i32 42
+;
+entry:
+  %0 = callbr i32 asm "", "=r,!i"() to label %x [label %v]
+
+x:
+  br label %v
+
+v:
+  ret i32 42
+}
+
+; Don't split edges unless they are critical, and callbr produces output, and
+; that output is used.
+; Here we have output and a critical edge along an indirect branch.
+define i32 @split_me0() {
+; CHECK-LABEL: @split_me0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = callbr i32 asm "", "=r,!i"()
+; CHECK-NEXT:    to label [[X:%.*]] [label %entry.y_crit_edge]
+; CHECK:       entry.y_crit_edge:
+; CHECK-NEXT:    br label [[Y:%.*]]
+; CHECK:       x:
+; CHECK-NEXT:    br label [[Y]]
+; CHECK:       y:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[TMP0]], [[ENTRY_Y_CRIT_EDGE:%.*]] ], [ 42, [[X]] ]
+; CHECK-NEXT:    ret i32 [[TMP1]]
+;
+entry:
+  %0 = callbr i32 asm "", "=r,!i"()
+  to label %x [label %y]
+
+x:
+  br label %y
+
+y:
+  %1 = phi i32 [ %0, %entry ], [ 42, %x ]
+  ret i32 %1
+}
+
+; Here we have output and a critical edge along an indirect branch.
+; Ensure that if we repeat the indirect destination, that we only split it
+; once.
+define i32 @split_me1(i1 %z) {
+; CHECK-LABEL: @split_me1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[Z:%.*]], label [[W:%.*]], label [[V:%.*]]
+; CHECK:       w:
+; CHECK-NEXT:    [[TMP0:%.*]] = callbr i32 asm "", "=r,!i,!i"()
+; CHECK-NEXT:    to label [[X:%.*]] [label [[W_V_CRIT_EDGE:%.*]], label %w.v_crit_edge]
+; CHECK:       w.v_crit_edge:
+; CHECK-NEXT:    br label [[V]]
+; CHECK:       x:
+; CHECK-NEXT:    ret i32 42
+; CHECK:       v:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[TMP0]], [[W_V_CRIT_EDGE]] ], [ undef, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[TMP1]]
+;
+entry:
+  br i1 %z, label %w, label %v
+
+w:
+  %0 = callbr i32 asm "", "=r,!i,!i"()
+  to label %x [label %v, label %v]
+
+x:
+  ret i32 42
+
+v:
+  %1 = phi i32 [%0, %w], [%0, %w], [undef, %entry]
+  ret i32 %1
+}
+
+; A more interessting case of @split_me1. Check that we still only split the
+; critical edge from w to v once.
+define i32 @split_me2(i1 %z) {
+; CHECK-LABEL: @split_me2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[Z:%.*]], label [[W:%.*]], label [[V:%.*]]
+; CHECK:       w:
+; CHECK-NEXT:    [[TMP0:%.*]] = callbr i32 asm "", "=r,!i,!i"()
+; CHECK-NEXT:    to label [[X:%.*]] [label [[W_V_CRIT_EDGE:%.*]], label %w.v_crit_edge]
+; CHECK:       w.v_crit_edge:
+; CHECK-NEXT:    br label [[V]]
+; CHECK:       x:
+; CHECK-NEXT:    ret i32 42
+; CHECK:       v:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[TMP0]], [[W_V_CRIT_EDGE]] ], [ 42, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[TMP1]]
+;
+entry:
+  br i1 %z, label %w, label %v
+
+w:
+  %0 = callbr i32 asm "", "=r,!i,!i"()
+  to label %x [label %v, label %v]
+
+x:
+  ret i32 42
+
+v:
+  %1 = phi i32 [ %0, %w ], [ 42, %entry ], [ %0, %w ]
+  ret i32 %1
+}