[IfConversion] Maintain the CFG when predicating/merging blocks in IfConvert*

[uabelho]

Summary

This fixes PR32721 in IfConvertTriangle and possible similar problems in
IfConvertSimple, IfConvertDiamond and IfConvertForkedDiamond.

In PR32721 we had a triangle

EBB
| \
|  |
| TBB
|  /
FBB

where FBB didn't have any successors at all since it ended with an
unconditional return. Then TBB and FBB were be merged into EBB, but EBB
would still keep its successors, and the use of analyzeBranch and
CorrectExtraCFGEdges wouldn't help to remove them since the return
instruction is not analyzable (at least not on ARM).

The edge updating code and branch probability updating code is now pushed
into MergeBlocks() which allows us to share the same update logic between
more callsites. This lets us remove several dependencies on analyzeBranch
and completely eliminate RemoveExtraEdges.

One thing that showed up with this patch was that IfConversion sometimes
left a successor with 0% probability even if there was no branch or
fallthrough to the successor.

One such example from the test case ifcvt_bad_zero_prob_succ.mir. The
indirect branch tBRIND can only jump to bb.1, but without the patch we
got:

bb.0:
  successors: %bb.1(0x80000000)

bb.1:
  successors: %bb.1(0x80000000), %bb.2(0x00000000)
  tBRIND %r1, 1, %cpsr
  B %bb.1

bb.2:

There is no way to jump from bb.1 to bb2, but still there is a 0% edge
from bb.1 to bb.2.

With the patch applied we instead get the expected:

bb.0:
  successors: %bb.1(0x80000000)

bb.1:
  successors: %bb.1(0x80000000)
  tBRIND %r1, 1, %cpsr
  B %bb.1

Since bb.2 had no predecessor at all, it was removed.

Several testcases had to be updated due to this since the removed
successor made the "Branch Probability Basic Block Placement" pass
sometimes place blocks in a different order.

Finally added a couple of new test cases:

• PR32721_ifcvt_triangle_unanalyzable.mir: Regression test for the original problem dexcribed in PR 32721.

• ifcvt_triangleWoCvtToNextEdge.mir: Regression test for problem that caused a revert of my first attempt to solve PR 32721.

• ifcvt_simple_bad_zero_prob_succ.mir: Test case showing the problem where a wrong successor with 0% probability was previously left.

• ifcvt_[diamond|forked_diamond|simple]_unanalyzable.mir Very simple test cases for the simple and (forked) diamond cases involving unanalyzable branches that can be nice to have as a base if wanting to write more complicated tests.

[uabelho]

Ok, a new attempt to fix this.

Of course I would like to have done the patch in smaller steps, as I tried in https://reviews.llvm.org/D33037,
but since I came to the conclusion that I needed to attack MergeBlocks I kind of had to update all the different
IfConvert* cases in one go.

It's incredible how complicated the IfConverter is, but at least I feel this is a step in the right direction.

Fire away :)

[grosser]

Thanks for the contribution!

I don't think I am an expert on the if-converter. If you feel you really need my input, please add me back.

[uabelho]

Ping!

[iteratee]

Mostly looks good. It will be easier to follow when you factor out the NFC sections and rebase.

lib/CodeGen/IfConversion.cpp

1487

This section looks like an NFC. Please commit it first, and then rebase this patch on top of it.

1587–1588

Same for this section. Please factor out the NFC change and commit it first.

[uabelho]

Pulled out a few NFC changes to https://reviews.llvm.org/D34388 according to Kyle's comments and rebased on top of that.

[uabelho]

Thanks!

[uabelho]

Ping!

Any other comments on this?

[kparzysz]

I've run through some of our tests and they all passed. LGTM

[uabelho]

In D34099#817440, @kparzysz wrote:

I've run through some of our tests and they all passed. LGTM

Thank you kparzysz!

I've been on vacation the last month, but I'll try to push this in a few days when I'm up to speed again.

[uabelho]

Rebased the patch to top of tree.

Needed another change in test/CodeGen/PowerPC/logic-ops-on-compares.ll due to a new test
that had been added to that file since last rebase.

lib/CodeGen/IfConversion.cpp

private:
     void AnalyzeBlock(MachineBasicBlock &MBB,
                       std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
     bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
                              bool isTriangle = false, bool RevBranch = false,
                              bool hasCommonTail = false);
     void AnalyzeBlocks(MachineFunction &MF,
                        std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
     void InvalidatePreds(MachineBasicBlock &MBB);
-    void RemoveExtraEdges(BBInfo &BBI);
     bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
     bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
     bool IfConvertDiamondCommon(BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
                                 unsigned NumDups1, unsigned NumDups2,
                                 bool TClobbersPred, bool FClobbersPred,
                                 bool RemoveBranch, bool MergeAddEdges);
     bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
                           unsigned NumDups1, unsigned NumDups2,

 /// Inserts an unconditional branch from \p MBB to \p ToMBB.
 static void InsertUncondBranch(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB,
                                const TargetInstrInfo *TII) {
   DebugLoc dl;  // FIXME: this is nowhere
   SmallVector<MachineOperand, 0> NoCond;
   TII->insertBranch(MBB, &ToMBB, nullptr, NoCond, dl);
 }
 
-/// Remove true / false edges if either / both are no longer successors.
-void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
-  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
-  SmallVector<MachineOperand, 4> Cond;
-  if (!TII->analyzeBranch(*BBI.BB, TBB, FBB, Cond))
-    BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
-}
-
 /// Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all
 /// values defined in MI which are also live/used by MI.
 static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs) {
   const TargetRegisterInfo *TRI = MI.getParent()->getParent()
     ->getSubtarget().getRegisterInfo();
 
   // Before stepping forward past MI, remember which regs were live
   // before MI. This is needed to set the Undef flag only when reg is
bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
   // block to it.
   BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
 
   if (CvtMBB.pred_size() > 1) {
     // Copy instructions in the true block, predicate them, and add them to
     // the entry block.
     CopyAndPredicateBlock(BBI, *CvtBBI, Cond);
 
-    // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
-    // explicitly remove CvtBBI as a successor.
+    // Keep the CFG updated.
     BBI.BB->removeSuccessor(&CvtMBB, true);
   } else {
     // Predicate the instructions in the true block.
     RemoveKills(CvtMBB.begin(), CvtMBB.end(), DontKill, *TRI);
     PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);
 
-    // Merge converted block into entry block.
+    // Merge converted block into entry block. The BB to Cvt edge is removed
+    // by MergeBlocks.
     MergeBlocks(BBI, *CvtBBI);
   }
 
   bool IterIfcvt = true;
   if (!canFallThroughTo(*BBI.BB, NextMBB)) {
     InsertUncondBranch(*BBI.BB, NextMBB, TII);
     BBI.HasFallThrough = false;
     // Now ifcvt'd block will look like this:
     // BB:
     // ...
     // t, f = cmp
     // if t op
     // b BBf
     //
     // We cannot further ifcvt this block because the unconditional branch
     // will have to be predicated on the new condition, that will not be
     // available if cmp executes.
     IterIfcvt = false;
   }
 
-  RemoveExtraEdges(BBI);
-
   // Update block info. BB can be iteratively if-converted.
   if (!IterIfcvt)
     BBI.IsDone = true;
   InvalidatePreds(*BBI.BB);
   CvtBBI->IsDone = true;
 
   // FIXME: Must maintain LiveIns.
   return true;
if (HasEarlyExit) {
     BBNext = MBPI->getEdgeProbability(BBI.BB, &NextMBB);
     BBCvt = MBPI->getEdgeProbability(BBI.BB, &CvtMBB);
   }
 
   // Remove the branches from the entry so we can add the contents of the true
   // block to it.
   BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
 
   if (CvtMBB.pred_size() > 1) {
     // Copy instructions in the true block, predicate them, and add them to
     // the entry block.
     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
-
-    // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
-    // explicitly remove CvtBBI as a successor.
-    BBI.BB->removeSuccessor(&CvtMBB, true);
   } else {
     // Predicate the 'true' block after removing its branch.
     CvtBBI->NonPredSize -= TII->removeBranch(CvtMBB);
     PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);
 
     // Now merge the entry of the triangle with the true block.
     MergeBlocks(BBI, *CvtBBI, false);
   }
 
+  // Keep the CFG updated.
+  BBI.BB->removeSuccessor(&CvtMBB, true);
+
   // If 'true' block has a 'false' successor, add an exit branch to it.
   if (HasEarlyExit) {
     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
                                            CvtBBI->BrCond.end());
     if (TII->reverseBranchCondition(RevCond))
       llvm_unreachable("Unable to reverse branch condition!");
 
     // Update the edge probability for both CvtBBI->FalseBB and NextBBI.
if (!HasEarlyExit &&
       InsertUncondBranch(*BBI.BB, NextMBB, TII);
       BBI.HasFallThrough = false;
     }
     // Mixed predicated and unpredicated code. This cannot be iteratively
     // predicated.
     IterIfcvt = false;
   }
 
-  RemoveExtraEdges(BBI);
-
   // Update block info. BB can be iteratively if-converted.
   if (!IterIfcvt)
     BBI.IsDone = true;
   InvalidatePreds(*BBI.BB);
   CvtBBI->IsDone = true;
   if (FalseBBDead)
     NextBBI->IsDone = true;
 
if (!IfConvertDiamondCommon(
       /* RemoveBranch */ true, /* MergeAddEdges */ true))
     return false;
 
   // Add back the branch.
   // Debug location saved above when removing the branch from BBI2
   TII->insertBranch(*BBI.BB, TrueBBI.TrueBB, TrueBBI.FalseBB,
                     TrueBBI.BrCond, dl);
 
-  RemoveExtraEdges(BBI);
-
   // Update block info.
   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
   InvalidatePreds(*BBI.BB);
 
   // FIXME: Must maintain LiveIns.
   return true;
 }
 
if (!IfConvertDiamondCommon(
       /* MergeAddEdges */ TailBB == nullptr))
     return false;
 
   // If the if-converted block falls through or unconditionally branches into
   // the tail block, and the tail block does not have other predecessors, then
   // fold the tail block in as well. Otherwise, unless it falls through to the
   // tail, add a unconditional branch to it.
   if (TailBB) {
+    // We need to remove the edges to the true and false blocks manually since
+    // we didn't let IfConvertDiamondCommon update the CFG.
+    BBI.BB->removeSuccessor(TrueBBI.BB);
+    BBI.BB->removeSuccessor(FalseBBI.BB, true);
+
     BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()];
     bool CanMergeTail = !TailBBI.HasFallThrough &&
       !TailBBI.BB->hasAddressTaken();
     // The if-converted block can still have a predicated terminator
     // (e.g. a predicated return). If that is the case, we cannot merge
     // it with the tail block.
     MachineBasicBlock::const_iterator TI = BBI.BB->getFirstTerminator();
     if (TI != BBI.BB->end() && TII->isPredicated(*TI))
if (CanMergeTail) {
       TailBBI.IsDone = true;
     } else {
       BBI.BB->addSuccessor(TailBB, BranchProbability::getOne());
       InsertUncondBranch(*BBI.BB, *TailBB, TII);
       BBI.HasFallThrough = false;
     }
   }
 
-  // RemoveExtraEdges won't work if the block has an unanalyzable branch,
-  // which can happen here if TailBB is unanalyzable and is merged, so
-  // explicitly remove BBI1 and BBI2 as successors.
-  BBI.BB->removeSuccessor(TrueBBI.BB);
-  BBI.BB->removeSuccessor(FalseBBI.BB, /* NormalizeSuccessProbs */ true);
-  RemoveExtraEdges(BBI);
-
   // Update block info.
   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
   InvalidatePreds(*BBI.BB);
 
   // FIXME: Must maintain LiveIns.
   return true;
 }
 
#endif
   ToBBI.IsAnalyzed = false;
 
   ++NumDupBBs;
 }
 
 /// Move all instructions from FromBB to the end of ToBB.  This will leave
 /// FromBB as an empty block, so remove all of its successor edges except for
 /// the fall-through edge.  If AddEdges is true, i.e., when FromBBI's branch is
-/// being moved, add those successor edges to ToBBI.
+/// being moved, add those successor edges to ToBBI and remove the old edge
+/// from ToBBI to FromBBI.
 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
   MachineBasicBlock &FromMBB = *FromBBI.BB;
   assert(!FromMBB.hasAddressTaken() &&
          "Removing a BB whose address is taken!");
 
   // In case FromMBB contains terminators (e.g. return instruction),
   // first move the non-terminator instructions, then the terminators.
   MachineBasicBlock::iterator FromTI = FromMBB.getFirstTerminator();
void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
   SmallVector<MachineBasicBlock *, 4> FromSuccs(FromMBB.succ_begin(),
                                                 FromMBB.succ_end());
   MachineBasicBlock *NBB = getNextBlock(FromMBB);
   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
   // The edge probability from ToBBI.BB to FromMBB, which is only needed when
   // AddEdges is true and FromMBB is a successor of ToBBI.BB.
   auto To2FromProb = BranchProbability::getZero();
   if (AddEdges && ToBBI.BB->isSuccessor(&FromMBB)) {
+    // Remove the old edge but remember the edge probability so we can calculate
+    // the correct weights on the new edges being added further down.
     To2FromProb = MBPI->getEdgeProbability(ToBBI.BB, &FromMBB);
-    // Set the edge probability from ToBBI.BB to FromMBB to zero to avoid the
-    // edge probability being merged to other edges when this edge is removed
-    // later.
-    ToBBI.BB->setSuccProbability(find(ToBBI.BB->successors(), &FromMBB),
-                                 BranchProbability::getZero());
+    ToBBI.BB->removeSuccessor(&FromMBB);
   }
 
   for (MachineBasicBlock *Succ : FromSuccs) {
     // Fallthrough edge can't be transferred.
     if (Succ == FallThrough)
       continue;
 
     auto NewProb = BranchProbability::getZero();
if (AddEdges) {
         ToBBI.BB->setSuccProbability(
             find(ToBBI.BB->successors(), Succ),
             MBPI->getEdgeProbability(ToBBI.BB, Succ) + NewProb);
       else
         ToBBI.BB->addSuccessor(Succ, NewProb);
     }
   }
 
-  // Now FromBBI always falls through to the next block!
-  if (NBB && !FromMBB.isSuccessor(NBB))
-    FromMBB.addSuccessor(NBB);
+  // Move the now empty FromMBB out of the way to the end of the function so
+  // it doesn't interfere with fallthrough checks done by canFallThroughTo().
+  MachineBasicBlock *Last = &*FromMBB.getParent()->rbegin();
+  if (Last != &FromMBB)
+    FromMBB.moveAfter(Last);
 
   // Normalize the probabilities of ToBBI.BB's successors with all adjustment
   // we've done above.
   if (ToBBI.IsBrAnalyzable && FromBBI.IsBrAnalyzable)
     ToBBI.BB->normalizeSuccProbs();
 
   ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
   FromBBI.Predicate.clear();

test/CodeGen/ARM/ifcvt-branch-weight.ll

bb:
   %5 = getelementptr inbounds %struct.S, %struct.S* %y, i32 0, i32 1, i32 0
   %6 = load i8, i8* %5, align 1
   %7 = zext i8 %6 to i32
   %8 = and i32 %7, 112
   %9 = icmp eq i32 %8, 0
   br i1 %9, label %return, label %bb2
 
 ; CHECK: BB#2: derived from LLVM BB %bb2
-; CHECK: Successors according to CFG: BB#3({{[0-9a-fx/= ]+}}50.00%) BB#4({{[0-9a-fx/= ]+}}50.00%)
+; CHECK: Successors according to CFG: BB#4({{[0-9a-fx/= ]+}}50.00%) BB#3({{[0-9a-fx/= ]+}}50.00%)
 
 bb2:
   %v10 = icmp eq i32 %3, 16
   br i1 %v10, label %bb4, label %bb3, !prof !0
 
 bb3:
   %v11 = icmp eq i32 %8, 16
   br i1 %v11, label %bb4, label %return, !prof !1

test/CodeGen/ARM/indirectbr-3.ll

 ; REQUIRES: asserts
 ; RUN: llc < %s -mtriple=thumbv7-apple-ios -arm-atomic-cfg-tidy=0 -stats 2>&1 | FileCheck %s
 
 ; If ARMBaseInstrInfo::AnalyzeBlocks returns the wrong value, which was possible
 ; for blocks with indirect branches, the IfConverter could end up deleting
 ; blocks that were the destinations of indirect branches, leaving branches to
 ; nowhere.
 ; <rdar://problem/14464830>
 
 define i32 @preserve_blocks(i32 %x) {
 ; preserve_blocks:
 ; CHECK: Block address taken
-; CHECK: movs r0, #1
-; CHECK: Block address taken
+; CHECK: %ibt1
 ; CHECK: movs r0, #2
+; CHECK: Block address taken
+; CHECK: %ibt2
+; CHECK: movs r0, #1
 ; CHECK-NOT: Address of block that was removed by CodeGen
 
 ; Separate bug. There are no valid diamonds to if-convert in this file.
 ; There was a bug in the if-conversion code that would if-convert a false
 ; diamond where one side had a return and the other had an indirect branch.
 ; Make sure no diamond conversions occurred while compiling this file.
 ; CHECK: Statistics Collected
 ; CHECK-NOT: 1 ifcvt          - Number of diamond if-conversions performed

test/CodeGen/ARM/struct-byval-frame-index.ll

 ; RUN: llc < %s -mcpu=cortex-a15 -verify-machineinstrs -arm-atomic-cfg-tidy=0 | FileCheck %s
 
 ; Check a spill right after a function call with large struct byval is correctly
 ; generated.
 ; PR16393
 
+; We expect the spill to be generated in %if.end230 and the reloads in
+; %if.end249 and %for.body285.
+
 ; CHECK: set_stored_macroblock_parameters
+; CHECK: @ %if.end230
+; CHECK-NOT:@ %if.
+; CHECK-NOT:@ %for.
 ; CHECK: str r{{.*}}, [sp, [[SLOT:#[0-9]+]]] @ 4-byte Spill
-; CHECK: bl RestoreMVBlock8x8
-; CHECK: bl RestoreMVBlock8x8
-; CHECK: bl RestoreMVBlock8x8
+; CHECK: @ %if.end249
+; CHECK-NOT:@ %if.
+; CHECK-NOT:@ %for.
+; CHECK: ldr r{{.*}}, [sp, [[SLOT]]] @ 4-byte Reload
+; CHECK: @ %for.body285
+; CHECK-NOT:@ %if.
+; CHECK-NOT:@ %for.
 ; CHECK: ldr r{{.*}}, [sp, [[SLOT]]] @ 4-byte Reload
 
 target triple = "armv7l-unknown-linux-gnueabihf"
 
 %structA = type { double, [16 x [16 x i16]], [16 x [16 x i16]], [16 x [16 x i16]], i32****, i32***, i32, i16, [4 x i32], [4 x i32], i8**, [16 x i8], [16 x i8], i32, i64, i32, i16******, i16******, [2 x [4 x [4 x i8]]], i32, i32, i32, i32, i32, i32, i32, i32, i32 }
 %structB = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, float, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i8**, i8**, i32, i32***, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [9 x [16 x [16 x i16]]], [5 x [16 x [16 x i16]]], [9 x [8 x [8 x i16]]], [2 x [4 x [16 x [16 x i16]]]], [16 x [16 x i16]], [16 x [16 x i32]], i32****, i32***, i32***, i32***, i32****, i32****, %structC*, %structD*, %structK*, i32*, i32*, i32, i32, i32, i32, [4 x [4 x i32]], i32, i32, i32, i32, i32, double, i32, i32, i32, i32, i16******, i16******, i16******, i16******, [15 x i16], i32, i32, i32, i32, i32, i32, i32, i32, [6 x [32 x i32]], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [1 x i32], i32, i32, [2 x i32], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, %structL*, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, double**, double***, i32***, double**, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [3 x [2 x i32]], [2 x i32], i32, i32, i16, i32, i32, i32, i32, i32 }
 %structC = type { i32, i32, [100 x %structD*], i32, float, float, float }
 %structD = type { i32, i32, i32, i32, i32, i32, %structE*, %structH*, %structJ*, i32, i32*, i32*, i32*, i32, i32*, i32*, i32*, i32 (i32)*, [3 x [2 x i32]] }

test/CodeGen/MIR/ARM/PR32721_ifcvt_triangle_unanalyzable.mir

+# RUN: llc -mtriple=arm-apple-ios -run-pass=if-converter %s -o - | FileCheck %s
+---
+name:            foo
+body:             |
+  bb.0:
+    B %bb.2
+
+  bb.1:
+    BX_RET 14, 0
+
+  bb.2:
+    Bcc %bb.1, 1, %cpsr
+
+  bb.3:
+    B %bb.1
+...
+
+# We should get a single block containing the BX_RET, with no successors at all
+
+# CHECK:      body:
+# CHECK-NEXT:   bb.0:
+# CHECK-NEXT:     BX_RET
+

test/CodeGen/MIR/ARM/ifcvt_diamond_unanalyzable.mir

+# RUN: llc -mtriple=arm-apple-ios -run-pass=if-converter %s -o - | FileCheck %s
+---
+name:            foo
+body:             |
+  bb.0:
+    Bcc %bb.2, 1, %cpsr
+
+  bb.1:
+    %sp = tADDspi %sp, 1, 14, _
+    B %bb.3
+
+  bb.2:
+    %sp = tADDspi %sp, 2, 14, _
+    B %bb.3
+
+  bb.3:
+  successors:
+    %sp = tADDspi %sp, 3, 14, _
+    BX_RET 14, _
+...
+
+# Diamond testcase with unanalyzable instruction in the BB following the
+# diamond.
+
+# CHECK: body:             |
+# CHECK:   bb.0:
+# CHECK:     %sp = tADDspi %sp, 2, 1, %cpsr
+# CHECK:     %sp = tADDspi %sp, 1, 0, %cpsr, implicit %sp
+# CHECK:     %sp = tADDspi %sp, 3, 14, _
+# CHECK:     BX_RET 14, _

test/CodeGen/MIR/ARM/ifcvt_forked_diamond_unanalyzable.mir

+# RUN: llc -mtriple=arm-apple-ios -run-pass=if-converter %s -o - | FileCheck %s
+---
+name:            foo
+body:             |
+  bb.0:
+    Bcc %bb.2, 1, %cpsr
+
+  bb.1:
+  successors: %bb.3(0x20000000), %bb.4(0x60000000)
+    %sp = tADDspi %sp, 1, 14, _
+    Bcc %bb.3, 1, %cpsr
+    B %bb.4
+
+  bb.2:
+  successors: %bb.3(0x20000000), %bb.4(0x60000000)
+    %sp = tADDspi %sp, 2, 14, _
+    Bcc %bb.3, 1, %cpsr
+    B %bb.4
+
+  bb.3:
+  successors:
+    %sp = tADDspi %sp, 3, 14, _
+    BX_RET 14, _
+
+  bb.4:
+  successors:
+    %sp = tADDspi %sp, 4, 14, _
+    BX_RET 14, _
+...
+
+# Forked-diamond testcase with unanalyzable instructions in both the True and
+# False BBs following the forked diamond.
+
+# CHECK: body:             |
+# CHECK:   bb.0:
+# CHECK:     successors: %bb.2(0x20000000), %bb.1(0x60000000)
+
+# CHECK:     %sp = tADDspi %sp, 2, 1, %cpsr
+# CHECK:     %sp = tADDspi %sp, 1, 0, %cpsr, implicit %sp
+# CHECK:     Bcc %bb.2, 1, %cpsr
+
+# CHECK:   bb.1:
+# CHECK:     %sp = tADDspi %sp, 4, 14, _
+# CHECK:     BX_RET 14, _
+
+# CHECK:   bb.2:
+# CHECK:     %sp = tADDspi %sp, 3, 14, _
+# CHECK:     BX_RET 14, _

test/CodeGen/MIR/ARM/ifcvt_simple_bad_zero_prob_succ.mir

+# RUN: llc -mtriple=arm-apple-ios -run-pass=if-converter %s -o - | FileCheck %s
+---
+name:            f1
+body:             |
+  bb.0:
+
+  bb.1:
+    Bcc %bb.3, 0, %cpsr
+
+  bb.2:
+
+  bb.3:
+    Bcc %bb.1, 0, %cpsr
+
+  bb.4:
+  successors: %bb.1
+    tBRIND %r1, 14, _
+...
+
+# We should only get bb.1 as successor to bb.1. No zero percent probability
+# edge from bb.1 to bb.2. There shouldn't even be a bb.2 at all.
+
+# CHECK: body:             |
+# CHECK:   bb.0:
+# CHECK:     successors: %bb.1(0x80000000)
+
+# CHECK:   bb.1:
+# CHECK:     successors: %bb.1(0x80000000)
+# CHECK-NOT: %bb.2(0x00000000)
+# CHECK:     tBRIND %r1, 1, %cpsr
+# CHECK:     B %bb.1
+
+#CHECK-NOT: bb.2:

test/CodeGen/MIR/ARM/ifcvt_simple_unanalyzable.mir

+# RUN: llc -mtriple=arm-apple-ios -run-pass=if-converter %s -o - | FileCheck %s
+---
+name:            foo
+body:             |
+  bb.0:
+    Bcc %bb.2, 0, %cpsr
+
+  bb.1:
+  successors:
+    BX_RET 14, _
+
+  bb.2:
+  successors:
+    %sp = tADDspi %sp, 2, 14, _
+    BX_RET 14, _
+...
+
+# Simple testcase with unanalyzable instructions in both TBB and FBB.
+
+# CHECK: body:             |
+# CHECK:   bb.0:
+# CHECK:     %sp = tADDspi %sp, 2, 0, %cpsr
+# CHECK:     BX_RET 0, %cpsr
+# CHECK:     BX_RET 14, _
+

test/CodeGen/MIR/ARM/ifcvt_triangleWoCvtToNextEdge.mir

+# RUN: llc -mtriple=arm-apple-ios -run-pass=if-converter %s -o - | FileCheck %s
+--- |
+  declare void @__stack_chk_fail()
+  declare void @bar()
+
+  define void @foo() {
+    ret void
+  }
+...
+---
+name:            foo
+body:             |
+
+  bb.0:
+    Bcc %bb.1, 1, %cpsr
+    B %bb.2
+
+  bb.1:
+    Bcc %bb.3, 0, %cpsr
+
+  bb.2:
+  successors:
+    tBL 14, %cpsr, @__stack_chk_fail
+
+  bb.3:
+  successors:
+    %sp = tADDspi %sp, 2, 14, _
+    %sp = tADDspi %sp, 2, 14, _
+    tTAILJMPdND @bar, 14, %cpsr
+...
+
+# bb.2 has no successors, presumably because __stack_chk_fail doesn't return,
+# so there should be no edge from bb.2 to bb.3.
+# Nevertheless, IfConversion treats bb.1, bb.2, bb.3 as a triangle and
+# inserts a predicated copy of bb.2 in bb.1.
+
+# This caused r302876 to die with a failed assertion.
+
+# CHECK:     bb.0:
+# CHECK:       successors: %bb.2(0x40000000), %bb.1(0x40000000)
+# CHECK:       Bcc %bb.2, 1, %cpsr
+
+# CHECK:     bb.1:
+# CHECK-NOT:   successors:
+# CHECK:       tBL 14, %cpsr, @__stack_chk_fail
+
+# CHECK:     bb.2:
+# CHECK-NOT:   successors:
+# CHECK:       tBL 1, %cpsr, @__stack_chk_fail
+# CHECK:       %sp = tADDspi %sp, 2, 14, _
+# CHECK:       %sp = tADDspi %sp, 2, 14, _
+# CHECK:       tTAILJMPdND @bar, 14, %cpsr

test/CodeGen/PowerPC/logic-ops-on-compares.ll

 
 define void @neg_truncate_i32(i32 *%ptr) {
 ; CHECK-LABEL: neg_truncate_i32:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    lwz r3, 0(r3)
 ; CHECK-NEXT:    rldicl. r3, r3, 0, 63
 ; CHECK-NEXT:    bclr 12, 2, 0
 ; CHECK-NEXT:  # BB#1: # %if.end29.thread136
-; CHECK-NEXT:  .LBB1_2: # %if.end29
 entry:
   %0 = load i32, i32* %ptr, align 4
   %rem17127 = and i32 %0, 1
   %cmp18 = icmp eq i32 %rem17127, 0
   br label %if.else
 
 if.else:                                          ; preds = %entry
   br i1 %cmp18, label %if.end29, label %if.end29.thread136

 
 define void @neg_truncate_i64(i64 *%ptr) {
 ; CHECK-LABEL: neg_truncate_i64:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    ld r3, 0(r3)
 ; CHECK-NEXT:    rldicl. r3, r3, 0, 63
 ; CHECK-NEXT:    bclr 12, 2, 0
 ; CHECK-NEXT:  # BB#1: # %if.end29.thread136
-; CHECK-NEXT:  .LBB3_2: # %if.end29
 entry:
   %0 = load i64, i64* %ptr, align 4
   %rem17127 = and i64 %0, 1
   %cmp18 = icmp eq i64 %rem17127, 0
   br label %if.else
 
 if.else:                                          ; preds = %entry
   br i1 %cmp18, label %if.end29, label %if.end29.thread136

test/CodeGen/PowerPC/ppc-shrink-wrapping.ll

body2:
   br label %for.body
 
 if.end:
   ret void
 }
 
 ; Another infinite loop test this time with two nested infinite loop.
 ; CHECK-LABEL: infiniteloop3
-; CHECK: # %end
+; CHECK: Lfunc_begin[[FUNCNUM:[0-9]+]]
+; CHECK: bclr
+; CHECK: Lfunc_end[[FUNCNUM]]
 define void @infiniteloop3() {
 entry:
   br i1 undef, label %loop2a, label %body
 
 body:                                             ; preds = %entry
   br i1 undef, label %loop2a, label %end
 
 loop1:                                            ; preds = %loop2a, %loop2b

test/CodeGen/SystemZ/atomicrmw-minmax-03.ll

 ; Test 32-bit atomic minimum and maximum.  Here we match the z10 versions,
 ; which can't use LOCR.
 ;
 ; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z10 | FileCheck %s
 
 ; Check signed minium.
 define i32 @f1(i32 %dummy, i32 *%src, i32 %b) {
 ; CHECK-LABEL: f1:
 ; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: crjle %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lr [[NEW]], %r4
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw min i32 *%src, i32 %b seq_cst
   ret i32 %res
 }
 
 ; Check signed maximum.
 define i32 @f2(i32 %dummy, i32 *%src, i32 %b) {
 ; CHECK-LABEL: f2:
 ; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: crjhe %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lr [[NEW]], %r4
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw max i32 *%src, i32 %b seq_cst
   ret i32 %res
 }
 
 ; Check unsigned minimum.
 define i32 @f3(i32 %dummy, i32 *%src, i32 %b) {
 ; CHECK-LABEL: f3:
 ; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: clrjle %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lr [[NEW]], %r4
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw umin i32 *%src, i32 %b seq_cst
   ret i32 %res
 }
 
 ; Check unsigned maximum.
 define i32 @f4(i32 %dummy, i32 *%src, i32 %b) {
 ; CHECK-LABEL: f4:
 ; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: clrjhe %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lr [[NEW]], %r4
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw umax i32 *%src, i32 %b seq_cst
   ret i32 %res
 }
 
 ; Check the high end of the aligned CS range.
 define i32 @f5(i32 %dummy, i32 *%src, i32 %b) {
 ; CHECK-LABEL: f5:
 ; CHECK: l %r2, 4092(%r3)
; CHECK: ber %r14
   %res = atomicrmw min i32 *%ptr, i32 %b seq_cst
   ret i32 %res
 }
 
 ; Check that constants are handled.
 define i32 @f13(i32 %dummy, i32 *%ptr) {
 ; CHECK-LABEL: f13:
 ; CHECK: lhi [[LIMIT:%r[0-9]+]], 42
-; CHECK: l %r2, 0(%r3)
-; CHECK: [[LOOP:\.[^:]*]]:
-; CHECK: lr [[NEW:%r[0-9]+]], %r2
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: cs %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
+; CHECK: [[LOOP]]:
+; CHECK: lr [[NEW]], %r2
 ; CHECK: crjle %r2, [[LIMIT]], [[KEEP:\..*]]
 ; CHECK: lhi [[NEW]], 42
-; CHECK: cs %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw min i32 *%ptr, i32 42 seq_cst
   ret i32 %res
 }

test/CodeGen/SystemZ/atomicrmw-minmax-04.ll

 ; Test 64-bit atomic minimum and maximum.  Here we match the z10 versions,
 ; which can't use LOCGR.
 ;
 ; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z10 | FileCheck %s
 
 ; Check signed minium.
 define i64 @f1(i64 %dummy, i64 *%src, i64 %b) {
 ; CHECK-LABEL: f1:
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: cgrjle %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lgr [[NEW]], %r4
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw min i64 *%src, i64 %b seq_cst
   ret i64 %res
 }
 
 ; Check signed maximum.
 define i64 @f2(i64 %dummy, i64 *%src, i64 %b) {
 ; CHECK-LABEL: f2:
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: cgrjhe %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lgr [[NEW]], %r4
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw max i64 *%src, i64 %b seq_cst
   ret i64 %res
 }
 
 ; Check unsigned minimum.
 define i64 @f3(i64 %dummy, i64 *%src, i64 %b) {
 ; CHECK-LABEL: f3:
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: clgrjle %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lgr [[NEW]], %r4
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw umin i64 *%src, i64 %b seq_cst
   ret i64 %res
 }
 
 ; Check unsigned maximum.
 define i64 @f4(i64 %dummy, i64 *%src, i64 %b) {
 ; CHECK-LABEL: f4:
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: clgrjhe %r2, %r4, [[KEEP:\..*]]
 ; CHECK: lgr [[NEW]], %r4
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw umax i64 *%src, i64 %b seq_cst
   ret i64 %res
 }
 
 ; Check the high end of the aligned CSG range.
 define i64 @f5(i64 %dummy, i64 *%src, i64 %b) {
 ; CHECK-LABEL: f5:
 ; CHECK: lg %r2, 524280(%r3)
; CHECK: ber %r14
   ret i64 %res
 }
 
 ; Check that constants are handled.
 define i64 @f10(i64 %dummy, i64 *%ptr) {
 ; CHECK-LABEL: f10:
 ; CHECK: lghi [[LIMIT:%r[0-9]+]], 42
 ; CHECK: lg %r2, 0(%r3)
+; CHECK: j [[LOOP:\.[^:]*]]
+; CHECK: [[BB1:\.[^:]*]]:
+; CHECK: csg %r2, [[NEW:%r[0-9]+]], 0(%r3)
+; CHECK: ber %r14
 ; CHECK: [[LOOP:\.[^:]*]]:
 ; CHECK: lgr [[NEW:%r[0-9]+]], %r2
 ; CHECK: cgrjle %r2, [[LIMIT]], [[KEEP:\..*]]
 ; CHECK: lghi [[NEW]], 42
-; CHECK: csg %r2, [[NEW]], 0(%r3)
-; CHECK: ber %r14
-; CHECK: j [[LOOP]]
+; CHECK: j [[BB1]]
   %res = atomicrmw min i64 *%ptr, i64 42 seq_cst
   ret i64 %res
 }