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

[nickdesaulniers]

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

[arsenm]

clang/docs/ReleaseNotes.rst

187

Typo garunteed

[nickdesaulniers]

• typo, iwyu

[nickdesaulniers]

• another typo in release notes

[efriedma]

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

[nickdesaulniers]

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

In D138078#3929590, @efriedma wrote:

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.

[nickdesaulniers]

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?

[nickdesaulniers]

In D138078#3931247, @nickdesaulniers wrote:

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?

[arsenm]

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

[nickdesaulniers]

In D138078#3931843, @arsenm wrote:

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]

• move critical edge splitting from CodeGenPrepare to SelectionDAGISel

[nickdesaulniers]

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

481–482

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

clang/docs/ReleaseNotes.rst

void h() {
       g(42);
     }
 
 - Clang's resource dir used to include the full clang version. It will now
   include only the major version. The new resource directory is
   ``$prefix/lib/clang/$CLANG_MAJOR_VERSION`` and can be queried using
   ``clang -print-resource-dir``, just like before.
 
+- Indirect edges of asm goto statements under certain circumstances may not be
+  split. In previous releases of clang, that means for the following input the
+  two inputs may have compared equal in the inline assembly.  This is no longer
+  garunteed (and necessary to support outputs along indirect edges, which is
+  still not yet supported).
+
+  .. code-block:: c
+
+    foo: asm goto ("# %0 %1"::"i"(&&foo)::foo);
+
 What's New in Clang |release|?
 ==============================
 Some of the major new features and improvements to Clang are listed
 here. Generic improvements to Clang as a whole or to its underlying
 infrastructure are described first, followed by language-specific
 sections with improvements to Clang's support for those languages.
 
 Major New Features

llvm/docs/LangRef.rst

 This instruction is designed to operate as a standard '``call``'
 instruction in most regards. The primary difference is that it
 establishes an association with additional labels to define where control
 flow goes after the call.
 
 The output values of a '``callbr``' instruction are available only to
 the '``fallthrough``' block, not to any '``indirect``' blocks(s).
 
+To support outputs along indirect edges, LLVM may need to split critical edges.
+This means that basic blocks may be synthesized; ``indirect labels`` from
+inline asm may not compare equal to the label when passed as a
+``function args``.
+
 The only use of this today is to implement the "goto" feature of gcc inline
 assembly where additional labels can be provided as locations for the inline
 assembly to jump to.
 
 Example:
 """"""""
 
 .. code-block:: llvm

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly.
 // When `IgnoreBlocksWithoutPHI` is set to `true` critical edges leading to a
 // block without phi-instructions will not be split.
 bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI,
                                   BranchProbabilityInfo *BPI = nullptr,
                                   BlockFrequencyInfo *BFI = nullptr);
 
+// Split critical edges from CallBrInsts when the CallBrInst has outputs. When
+// we take an indirect jump from the CallBrInst, we need somewhere to copy any
+// Physical Register outputs back to virtual register outputs, but we must do
+// so before any phi instructions (phi's must occur first in a BasicBlock).
+// Does not split the default edge.
+bool SplitCallBrCriticalEdges(Function &F);
+
 /// Given a set of incoming and outgoing blocks, create a "hub" such that every
 /// edge from an incoming block InBB to an outgoing block OutBB is now split
 /// into two edges, one from InBB to the hub and another from the hub to
 /// OutBB. The hub consists of a series of guard blocks, one for each outgoing
 /// block. Each guard block conditionally branches to the corresponding outgoing
 /// block, or the next guard block in the chain. These guard blocks are returned
 /// in the argument vector.
 ///

llvm/lib/CodeGen/CodeGenPrepare.cpp

bool CodeGenPrepare::runOnFunction(Function &F) {
   ModifyDT ModifiedDT = ModifyDT::NotModifyDT;
   if (!DisableBranchOpts)
     EverMadeChange |= splitBranchCondition(F, ModifiedDT);
 
   // Split some critical edges where one of the sources is an indirect branch,
   // to help generate sane code for PHIs involving such edges.
   EverMadeChange |=
       SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/true);
+  // CallBr may have phyreg outputs. The use of these may be a PHI node, so we
+  // need somewhere to put the vreg copies after the INLINEASM_BR but before
+  // the phis.
+  EverMadeChange |= SplitCallBrCriticalEdges(F);
 
   // If we are optimzing huge function, we need to consider the build time.
   // Because the basic algorithm's complex is near O(N!).
   IsHugeFunc = F.size() > HugeFuncThresholdInCGPP;
 
   bool MadeChange = true;
   bool FuncIterated = false;
   while (MadeChange) {

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
+
+#include <utility>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "break-crit-edges"
 
 STATISTIC(NumBroken, "Number of blocks inserted");
 
 namespace {
   struct BreakCriticalEdges : public FunctionPass {
while (Indirect != End) {
       IndPHI->eraseFromParent();
     }
 
     Changed = true;
   }
 
   return Changed;
 }
+
+bool llvm::SplitCallBrCriticalEdges(Function &F) {
+  bool Changed = false;
+  CriticalEdgeSplittingOptions Options;
+  Options.setMergeIdenticalEdges();
+  SmallPtrSet<const BasicBlock *, 4> Visited;
+  SmallVector<unsigned, 4> UniqueCriticalSuccessorIndices;
+
+  for (Instruction &I : instructions(F)) {
+    if (auto *CBR = dyn_cast<CallBrInst>(&I)) {
+      // If the CallBrInst has no output, then we do not need to split any
+      // critical edges.
+      if (CBR->getFunctionType()->getReturnType()->isVoidTy())
+        continue;
+
+      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;
+        if (isCriticalEdge(CBR, i))
+          UniqueCriticalSuccessorIndices.push_back(i);
+      }
+      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;
+}

llvm/test/CodeGen/X86/callbr-asm-outputs.ll

 
 define i32 @test2(i32 %out1, i32 %out2) nounwind {
 ; CHECK-LABEL: test2:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    pushl %edi
 ; CHECK-NEXT:    pushl %esi
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %edi
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; CHECK-NEXT:    movl $-1, %eax
 ; CHECK-NEXT:    cmpl %edi, %esi
-; CHECK-NEXT:    jge .LBB1_2
+; CHECK-NEXT:    jge .LBB1_3
 ; CHECK-NEXT:  # %bb.1: # %if.then
 ; CHECK-NEXT:    #APP
 ; CHECK-NEXT:    testl %esi, %esi
 ; CHECK-NEXT:    testl %edi, %esi
-; CHECK-NEXT:    jne .LBB1_4
+; CHECK-NEXT:    jne .LBB1_2
 ; CHECK-NEXT:    #NO_APP
-; CHECK-NEXT:    jmp .LBB1_3
-; CHECK-NEXT:  .LBB1_2: # %if.else
+; CHECK-NEXT:    jmp .LBB1_4
+; CHECK-NEXT:  .LBB1_2: # Block address taken
+; CHECK-NEXT:    # %if.then.label_true_crit_edge
+; CHECK-NEXT:    # Label of block must be emitted
+; CHECK-NEXT:    jmp .LBB1_8
+; CHECK-NEXT:  .LBB1_3: # %if.else
 ; CHECK-NEXT:    #APP
 ; CHECK-NEXT:    testl %esi, %edi
 ; CHECK-NEXT:    testl %esi, %edi
-; CHECK-NEXT:    jne .LBB1_5
+; CHECK-NEXT:    jne .LBB1_9
 ; CHECK-NEXT:    #NO_APP
-; CHECK-NEXT:  .LBB1_3:
+; CHECK-NEXT:  .LBB1_4:
 ; CHECK-NEXT:    movl %esi, %eax
 ; CHECK-NEXT:    addl %edi, %eax
-; CHECK-NEXT:  .LBB1_5: # Block address taken
-; CHECK-NEXT:    # %return
-; CHECK-NEXT:    # Label of block must be emitted
+; CHECK-NEXT:  .LBB1_5: # %return
 ; CHECK-NEXT:    popl %esi
 ; CHECK-NEXT:    popl %edi
 ; CHECK-NEXT:    retl
-; CHECK-NEXT:  .LBB1_4: # Block address taken
-; CHECK-NEXT:    # %label_true
+; CHECK-NEXT:  .LBB1_7: # Block address taken
+; CHECK-NEXT:    # %if.else.label_true_crit_edge
 ; CHECK-NEXT:    # Label of block must be emitted
+; CHECK-NEXT:  .LBB1_8: # %label_true
 ; CHECK-NEXT:    movl $-2, %eax
 ; CHECK-NEXT:    jmp .LBB1_5
+; CHECK-NEXT:  .LBB1_9: # Block address taken
+; CHECK-NEXT:    # %if.else.return_crit_edge
+; CHECK-NEXT:    # Label of block must be emitted
+; CHECK-NEXT:  .LBB1_6: # Block address taken
+; CHECK-NEXT:    # %if.then.return_crit_edge
+; CHECK-NEXT:    # Label of block must be emitted
+; CHECK-NEXT:    movl $-1, %eax
+; CHECK-NEXT:    jmp .LBB1_5
 entry:
   %cmp = icmp slt i32 %out1, %out2
   br i1 %cmp, label %if.then, label %if.else
 
 if.then:                                          ; preds = %entry
   %0 = callbr { i32, i32 } asm sideeffect "testl $0, $0; testl $1, $2; jne ${3:l}", "={si},={di},r,!i,!i,0,1"(i32 %out1, i32 %out1, i32 %out2)
           to label %if.end [label %label_true, label %return]
 

 ; CHECK-NEXT:    #NO_APP
 ; CHECK-NEXT:  # %bb.4:
 ; CHECK-NEXT:    movl %edx, %eax
 ; CHECK-NEXT:  .LBB2_5: # %asm.fallthrough
 ; CHECK-NEXT:    popl %esi
 ; CHECK-NEXT:    popl %edi
 ; CHECK-NEXT:    retl
 ; CHECK-NEXT:  .LBB2_6: # Block address taken
-; CHECK-NEXT:    # %indirect
+; CHECK-NEXT:    # %true.indirect_crit_edge
+; CHECK-NEXT:    # Label of block must be emitted
+; CHECK-NEXT:  .LBB2_7: # Block address taken
+; CHECK-NEXT:    # %false.indirect_crit_edge
 ; CHECK-NEXT:    # Label of block must be emitted
 ; CHECK-NEXT:    movl $42, %eax
 ; CHECK-NEXT:    jmp .LBB2_5
 entry:
   br i1 %cmp, label %true, label %false
 
 true:
   %0 = callbr { i32, i32 } asm sideeffect ".word $0, $1", "={si},={di},!i" () to label %asm.fallthrough [label %indirect]

 indirect:
   ret i32 42
 }
 
 ; Test 4 - asm-goto with output constraints.
 define i32 @test4(i32 %out1, i32 %out2) {
 ; CHECK-LABEL: test4:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    movl $-1, %eax
-; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; CHECK-NEXT:    #APP
-; CHECK-NEXT:    testl %ecx, %ecx
-; CHECK-NEXT:    testl %edx, %ecx
+; CHECK-NEXT:    testl %eax, %eax
+; CHECK-NEXT:    testl %ecx, %eax
 ; CHECK-NEXT:    jne .LBB3_3
 ; CHECK-NEXT:    #NO_APP
 ; CHECK-NEXT:  # %bb.1: # %asm.fallthrough
 ; CHECK-NEXT:    #APP
-; CHECK-NEXT:    testl %ecx, %edx
-; CHECK-NEXT:    testl %ecx, %edx
-; CHECK-NEXT:    jne .LBB3_4
+; CHECK-NEXT:    testl %eax, %ecx
+; CHECK-NEXT:    testl %eax, %ecx
+; CHECK-NEXT:    jne .LBB3_5
 ; CHECK-NEXT:    #NO_APP
 ; CHECK-NEXT:  # %bb.2: # %asm.fallthrough2
-; CHECK-NEXT:    addl %edx, %ecx
-; CHECK-NEXT:    movl %ecx, %eax
+; CHECK-NEXT:    addl %ecx, %eax
+; CHECK-NEXT:    retl
 ; CHECK-NEXT:  .LBB3_4: # Block address taken
-; CHECK-NEXT:    # %return
+; CHECK-NEXT:    # %entry.return_crit_edge
+; CHECK-NEXT:    # Label of block must be emitted
+; CHECK-NEXT:  .LBB3_5: # Block address taken
+; CHECK-NEXT:    # %asm.fallthrough.return_crit_edge
 ; CHECK-NEXT:    # Label of block must be emitted
+; CHECK-NEXT:    movl $-1, %eax
 ; CHECK-NEXT:    retl
+; CHECK-NEXT:  .LBB3_6: # Block address taken
+; CHECK-NEXT:    # %asm.fallthrough.label_true_crit_edge
+; CHECK-NEXT:    # Label of block must be emitted
 ; CHECK-NEXT:  .LBB3_3: # Block address taken
-; CHECK-NEXT:    # %label_true
+; CHECK-NEXT:    # %entry.label_true_crit_edge
 ; CHECK-NEXT:    # Label of block must be emitted
 ; CHECK-NEXT:    movl $-2, %eax
-; CHECK-NEXT:    jmp .LBB3_4
+; CHECK-NEXT:    retl
 entry:
   %0 = callbr { i32, i32 } asm sideeffect "testl $0, $0; testl $1, $2; jne ${3:l}", "=r,=r,r,!i,!i"(i32 %out1)
           to label %asm.fallthrough [label %label_true, label %return]
 
 asm.fallthrough:                                  ; preds = %entry
   %asmresult = extractvalue { i32, i32 } %0, 0
   %asmresult1 = extractvalue { i32, i32 } %0, 1
   %1 = callbr { i32, i32 } asm sideeffect "testl $0, $1; testl $2, $3; jne ${5:l}", "=r,=r,r,r,!i,!i"(i32 %asmresult, i32 %asmresult1)

 ; GCCAsmStmt being turned into "={esp},0" since after D87279 they're turned
 ; into "={esp},{esp}". This previously caused an ICE; this test is more so
 ; about avoiding another ICE than what the actual output is.
 define dso_local void @test5() {
 ; CHECK-LABEL: test5:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    #APP
 ; CHECK-NEXT:    #NO_APP
-; CHECK-NEXT:  .LBB4_1: # Block address taken
+; CHECK-NEXT:  # %bb.1:
+; CHECK-NEXT:    retl
+; CHECK-NEXT:  .LBB4_2: # Block address taken
+; CHECK-NEXT:    # %._crit_edge
 ; CHECK-NEXT:    # Label of block must be emitted
 ; CHECK-NEXT:    retl
   %1 = call i32 @llvm.read_register.i32(metadata !3)
   %2 = callbr i32 asm "", "={esp},!i,{esp}"(i32 %1)
           to label %3 [label %4]
 
 3:
   call void @llvm.write_register.i32(metadata !3, i32 %2)

llvm/test/Transforms/CodeGenPrepare/AArch64/callbr.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -codegenprepare %s -o - | FileCheck %s
+
+target triple = "aarch64-linux-gnu"
+
+; Don't split edges unless they are critical and callbr produces output.
+; Here we have neither.
+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.
+; 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.
+; 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.
+; 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:    ret i32 0
+;
+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:
+  ret i32 0
+}
+
+; 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
+}