CodeGen: If Convert blocks that would form a diamond when tail-merged.

[iteratee]

Summary

Some if conversion currently requires tail-merging to have run first.

As an example the following function currently relies on tail-merging for if
conversion to succeed. The common tail of cond_true and cond_false is
extracted, and this then forms a diamond pattern that can be
successfully if converted.

If this block does not get extracted, either because tail-merging is
disabled or the threshold is higher, we should still recognize this
pattern and if-convert it.

define i32 @t2(i32 %a, i32 %b) nounwind {
entry:
      %tmp1434 = icmp eq i32 %a, %b           ; <i1> [#uses=1]
      br i1 %tmp1434, label %bb17, label %bb.outer

bb.outer:               ; preds = %cond_false, %entry
      %b_addr.021.0.ph = phi i32 [ %b, %entry ], [ %tmp10, %cond_false ]
      %a_addr.026.0.ph = phi i32 [ %a, %entry ], [ %a_addr.026.0, %cond_false ]
      br label %bb

bb:             ; preds = %cond_true, %bb.outer
      %indvar = phi i32 [ 0, %bb.outer ], [ %indvar.next, %cond_true ]
      %tmp. = sub i32 0, %b_addr.021.0.ph
      %tmp.40 = mul i32 %indvar, %tmp.
      %a_addr.026.0 = add i32 %tmp.40, %a_addr.026.0.ph
      %tmp3 = icmp sgt i32 %a_addr.026.0, %b_addr.021.0.ph
      br i1 %tmp3, label %cond_true, label %cond_false

cond_true:              ; preds = %bb
      %tmp7 = sub i32 %a_addr.026.0, %b_addr.021.0.ph
      %tmp1437 = icmp eq i32 %tmp7, %b_addr.021.0.ph
      %indvar.next = add i32 %indvar, 1
      br i1 %tmp1437, label %bb17, label %bb

cond_false:             ; preds = %bb
      %tmp10 = sub i32 %b_addr.021.0.ph, %a_addr.026.0
      %tmp14 = icmp eq i32 %a_addr.026.0, %tmp10
      br i1 %tmp14, label %bb17, label %bb.outer

bb17:           ; preds = %cond_false, %cond_true, %entry
      %a_addr.026.1 = phi i32 [ %a, %entry ], [ %tmp7, %cond_true ], [ %a_addr.026.0, %cond_false ]
      ret i32 %a_addr.026.1
}

Without tail-merging or diamond-tail if conversion:

LBB1_1:                                 @ %bb
                                      @ =>This Inner Loop Header: Depth=1
      cmp     r0, r1
      ble     LBB1_3
@ BB#2:                                 @ %cond_true
                                      @   in Loop: Header=BB1_1 Depth=1
      subs    r0, r0, r1
      cmp     r1, r0
      it      ne
      cmpne   r0, r1
      bgt     LBB1_4
LBB1_3:                                 @ %cond_false
                                      @   in Loop: Header=BB1_1 Depth=1
      subs    r1, r1, r0
      cmp     r1, r0
      bne     LBB1_1
LBB1_4:                                 @ %bb17
      bx      lr

With diamond-tail if conversion, but without tail-merging:

@ BB#0:                                 @ %entry
      cmp     r0, r1
      it      eq
      bxeq    lr
LBB1_1:                                 @ %bb
                                      @ =>This Inner Loop Header: Depth=1
      cmp     r0, r1
      ite     le
      suble   r1, r1, r0
      subgt   r0, r0, r1
      cmp     r1, r0
      bne     LBB1_1
@ BB#2:                                 @ %bb17
      bx      lr

[iteratee]

Removed debugging, tidied spacing, added comments.

[davidxl]

I am torn about this change. While this looks like a useful thing to do, I suspect this is not the right way to approach the problem.

The example actually confirms the fact the pre-layout tailmerging is a good normalization/enabler pass for later optimizations. This is the reason why it should be run with lower threshold enabling as much optimization as possible, and later let TailDup to undo those that do not bring benefit and to improve layout.

Another question is that whether this patch can handle more cases where (tailMerge + ifcvt) can not handle. If not, it seems to me the patch seems to have duplicated logics (e.g, counting dups) in tailMerge which is not the right approach.

Is this patch required to enable your tailDup enhancement patch? I don't think this one is essential for it. We can probably focus on getting your tailDup patch in first (it is very close to get -- probably just to make your latest tailMerge tuning to be enabled only in post layout mode?)

[iteratee]

In D22551#490028, @davidxl wrote:

I am torn about this change. While this looks like a useful thing to do, I suspect this is not the right way to approach the problem.

The example actually confirms the fact the pre-layout tailmerging is a good normalization/enabler pass for later optimizations. This is the reason why it should be run with lower threshold enabling as much optimization as possible, and later let TailDup to undo those that do not bring benefit and to improve layout.

I couldn't find any of the original commits about tail merging that refer to normalization. It's always about reducing code size. Also, it's unusual for a canonicalization pass to have a threshold.

Another question is that whether this patch can handle more cases where (tailMerge + ifcvt) can not handle. If not, it seems to me the patch seems to have duplicated logics (e.g, counting dups) in tailMerge which is not the right approach.

Two things:

1. The code has to count duplicates anyway. Look at how IfConvertDiamond is written.
2. There is a precedent for teaching optimization passes to look deeper, even if there is a canonicalization pass that would prevent the need.

Is this patch required to enable your tailDup enhancement patch? I don't think this one is essential for it. We can probably focus on getting your tailDup patch in first (it is very close to get -- probably just to make your latest tailMerge tuning to be enabled only in post layout mode?)

Not specifically. If tailMerge is made less aggressive only during layout, then this is not necessary.

[iteratee]

Refactor shared code between Diamond and Diamond with shared tail.

[davidxl]

The validateDiamond refactoring change can be split out from the functional change into a different patch .

[davidxl]

lib/CodeGen/IfConversion.cpp

677

Document the difference between this pattern vs ValidDiamond?

Also since there is no common tail shared between truebb and falsebb, the shape is not really 'Diamond'. Perfhaps make it named "ValidDiamondWithTailCommonned' ? to indicate the shape will be diamond if the tail is commonned?

695

is 'fallthough' check needed here?

705

Can this check be moved earlier? If so, common check can be extracted and shared across this and ValidDiamond.

719

Merge these two :

if (TF == FT && TT == FF) {
    if (! Reversable)
         return false;
    reverse ...
 }

737

Better move this out of line to improve readability.

742

I have not looked in details here. Is there existing code that can be refactored/reused by any chance?

[iteratee]

Move closure to member function.

[iteratee]

Renamed to ForkedDiamond, and add more documentation about how it differs from standard diamond.

lib/CodeGen/IfConversion.cpp

695

No. It's just checking if the branch is analyzable.

705

It's short enough that I don't think it's worth factoring out. If there were more checks in common, then maybe, but there aren't.

742

The function that is the most similar is ScanInstructions. I think they're different enough that having them share code would be more confusing than helpful.

818

I renamed it ForkedDiamond, and added more comments about it.

[davidxl]

The code looks in pretty good shape now. I find the test case is little missing -- how about adding some more (including negative one)?

lib/CodeGen/IfConversion.cpp

90

nit: with a common tail that can be shared

498

Split out the independent fix with a test case if possible

992

Document the parameters.

992

Why can't this function be folded into existing FeasbilityAnalysis with a new flag : hasCommonForkedTail (which defaults to false) ?

1841

Why is this check not done for the forked case?

[iteratee]

Cleanups in response to comments.
Removed DebugLocation propagation.

lib/CodeGen/IfConversion.cpp

498

I've removed it. Finding a test case is enough work that I just don't have time.

1841

Good catch.

[iteratee]

Add negative test.

[iteratee]

Is there anything else that I need to do for this patch?

[davidxl]

lib/CodeGen/IfConversion.cpp

708

The variable names here does not seem to match the control flow graph drawn in the comment. Please make it consistent.

745

Clean up the comment -- last instruction of what?

746

Is this a good assumption to make? Any assert can be added countDuplicatedInstructions?

778

This skip code pattern has appeared many times -- good candidate to extract into an inline function.

786

Why is this check not done outside of this function (in ValidForkedForkedDiamond before countDuplicatedInstuctions as in ValidDiamond ?

791

Why is this not already computed?

794

feasbilityAnalysis already checks isUnpredicable bit -- why is it still done here?

1122

This code looks almost exactly the same as the regular diamond case. Perhaps defined a lamba function
auto DiamondFinder = [&](decltype(&IfConverter::ValidDiamond) Checker) {

  if (CanRevCond && (this->*Checker(..) && ...) {
 ....
}

};

DiamondFinder(&IfConverter::ValidDiamond);
DiamondFinder(&IfConverter::ValidForkedDiamond);

[iteratee]

Refactor and comments.

lib/CodeGen/IfConversion.cpp

708

Which comment specifically? The names in the graph are member names of BBInfo, and are assumed to coincide. Here we can't make that assumption.

The names are also logical: TT = TrueBBI.TrueBB, TF = TrueBBI.FalseBB, etc.

746

I've elaborated in the comment. The size is computed by ScanInstructions, and the duplicated portion is subtracted off, so there's no point in recomputing the size, we would get the same answer.

786

Because countDuplicatedInstructions adjusts the iterators so that we know exactly which instructions are duplicated. We only worry about the non-duplicated instructions that clobber the predicate info.

791

See above.

794

Same reason as above.

1122

It would take too many parameters, and the code would be less legible.

I would have to pass in TrueBBICalc, FalseBBICalc, hasCommonTail, and then conditionalize the calls, because
ValidDiamond takes a different number of arguments from ValidForkedDiamond.

I don't think it would be cleaner.

[iteratee]

Missed changes from last patch. (Refactor and comments.)

[davidxl]

lib/CodeGen/IfConversion.cpp

708

Ok -- the naming convention makes sense.

746

My question in this comment is that countDuplicatiedInstruction does not document exit state of TIE and FIE, so add assertions to make sure TIE and FIE point to what you expect to see (pointing to identical instructions before and not identical after ?)

786

Should this be done for ValidDiamond too -- only check the non-shared portion?

Also I don't think it is ideal to have code duplication like this. Looks like you should re-use scanInstructions or part of it (by making it accepting BIB and BIE) ?

1122

I still think refactoring is better -- the main reason of doing the refactoring is to avoid code duplication which is better longer term. For instance, no need to worry about fixing bugs in multiple different places.

Another point is that Diamond and ForkedDiamond patterns are exclusive, so there is no need to do forked diamond check after diamond check returns true. In other words, the code can be further simplified to:

if (CanRevCond) {

if (!DiamondFinder(...::ValidDiamond)) {
    DiamondFilnder(... ::ValidForkedDiamond);

}

Also it seems to me you don't need to introduce TrueBBICalc and FalseBBICalc. How about in ValidForkedDiamond

1. saving the initial value of TrueBBI and FalseBBI
2. re-scan region of BB and update TrueBBI and FalseBBI
3. if ValidForkedDiamond fails, restore TrueBBI etc value before returning.

[iteratee]

More refactors and comments.

[iteratee]

I split ScanInstructions in two, made the actual scan take iterator bounds, and removed RecaculateCostsAndClobbers.

lib/CodeGen/IfConversion.cpp

1150

I factored out the feasibility analysis. Take a look now.

[iteratee]

More refactoring.

[davidxl]

lgtm

When commtting, I suggest you carve out the refactoring changes into one or more NFC patches (debug skip for one, scanning for one, and the rest of refactoring) before committing the functional change.

[iteratee]

Added bug fix from the revert.

[iteratee]

Committed in: r278287

[iteratee]

I have a possible fix for the broken self hosting bot. I've split the fixed patch into 3: Fix (which can apply to top), Rescan diamonds, and Forked diamond. I'm going to re-commit all 3 and let the bots churn through them again.

[iteratee]

Recommitted in r279670 and r279671

lib/CodeGen/IfConversion.cpp

 static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev",
                                       cl::init(false), cl::Hidden);
 static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false",
                                       cl::init(false), cl::Hidden);
 static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev",
                                        cl::init(false), cl::Hidden);
 static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
                                     cl::init(false), cl::Hidden);
+static cl::opt<bool> DisableDiamondTail("disable-ifcvt-diamond-tail",
+                                        cl::init(false), cl::Hidden);
 static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold",
                                      cl::init(true), cl::Hidden);
 
 STATISTIC(NumSimple,       "Number of simple if-conversions performed");
 STATISTIC(NumSimpleFalse,  "Number of simple (F) if-conversions performed");
 STATISTIC(NumTriangle,     "Number of triangle if-conversions performed");
 STATISTIC(NumTriangleRev,  "Number of triangle (R) if-conversions performed");
 STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");
 STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");
 STATISTIC(NumDiamonds,     "Number of diamond if-conversions performed");
+STATISTIC(NumDiamondTails, "Number of diamond-tail if-conversions performed");
 STATISTIC(NumIfConvBBs,    "Number of if-converted blocks");
 STATISTIC(NumDupBBs,       "Number of duplicated blocks");
 STATISTIC(NumUnpred,       "Number of true blocks of diamonds unpredicated");
 
 namespace {
   class IfConverter : public MachineFunctionPass {
     enum IfcvtKind {
       ICNotClassfied,  // BB data valid, but not classified.
       ICSimpleFalse,   // Same as ICSimple, but on the false path.
       ICSimple,        // BB is entry of an one split, no rejoin sub-CFG.
       ICTriangleFRev,  // Same as ICTriangleFalse, but false path rev condition.
       ICTriangleRev,   // Same as ICTriangle, but true path rev condition.
       ICTriangleFalse, // Same as ICTriangle, but on the false path.
       ICTriangle,      // BB is entry of a triangle sub-CFG.
-      ICDiamond        // BB is entry of a diamond sub-CFG.
+      ICDiamond,       // BB is entry of a diamond sub-CFG.
+      ICDiamondTail    // BB is entry of an almost diamond sub-CFG, with a
+                       // shared tail.
     };
 
     /// BBInfo - One per MachineBasicBlock, this is used to cache the result
     /// if-conversion feasibility analysis. This includes results from
     /// TargetInstrInfo::analyzeBranch() (i.e. TBB, FBB, and Cond), and its
     /// classification, and common tail block of its successors (if it's a
     /// diamond shape), its size, whether it's predicable, and whether any
     /// instruction can clobber the 'would-be' predicate.
class IfConverter : public MachineFunctionPass {
     /// BrCond          - Conditions for end of block conditional branches.
     /// Predicate       - Predicate used in the BB.
     struct BBInfo {
       bool IsDone          : 1;
       bool IsBeingAnalyzed : 1;
       bool IsAnalyzed      : 1;
       bool IsEnqueued      : 1;
       bool IsBrAnalyzable  : 1;
+      bool IsBrReversible  : 1;
       bool HasFallThrough  : 1;
       bool IsUnpredicable  : 1;
       bool CannotBeCopied  : 1;
       bool ClobbersPred    : 1;
       unsigned NonPredSize;
       unsigned ExtraCost;
       unsigned ExtraCost2;
       MachineBasicBlock *BB;
       MachineBasicBlock *TrueBB;
       MachineBasicBlock *FalseBB;
       SmallVector<MachineOperand, 4> BrCond;
       SmallVector<MachineOperand, 4> Predicate;
       BBInfo() : IsDone(false), IsBeingAnalyzed(false),
                  IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),
-                 HasFallThrough(false), IsUnpredicable(false),
-                 CannotBeCopied(false), ClobbersPred(false), NonPredSize(0),
-                 ExtraCost(0), ExtraCost2(0), BB(nullptr), TrueBB(nullptr),
+                 IsBrReversible(false), HasFallThrough(false),
+                 IsUnpredicable(false), CannotBeCopied(false),
+                 ClobbersPred(false), NonPredSize(0), ExtraCost(0),
+                 ExtraCost2(0), BB(nullptr), TrueBB(nullptr),
                  FalseBB(nullptr) {}
     };
 
     /// IfcvtToken - Record information about pending if-conversions to attempt:
     /// BBI             - Corresponding BBInfo.
     /// Kind            - Type of block. See IfcvtKind.
     /// NeedSubsumption - True if the to-be-predicated BB has already been
     ///                   predicated.
     /// NumDups      - Number of instructions that would be duplicated due
     ///                   to this if-conversion. (For diamonds, the number of
     ///                   identical instructions at the beginnings of both
     ///                   paths).
     /// NumDups2     - For diamonds, the number of identical instructions
     ///                   at the ends of both paths.
     struct IfcvtToken {
       BBInfo &BBI;
       IfcvtKind Kind;
-      bool NeedSubsumption;
       unsigned NumDups;
       unsigned NumDups2;
-      IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0)
-        : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {}
+      bool NeedSubsumption : 1;
+      bool TClobbersPred : 1;
+      bool FClobbersPred : 1;
+      IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0,
+                 bool tc = false, bool fc = false)
+        : BBI(b), Kind(k), NumDups(d), NumDups2(d2), NeedSubsumption(s),
+          TClobbersPred(tc), FClobbersPred(fc) {}
     };
 
     /// BBAnalysis - Results of if-conversion feasibility analysis indexed by
     /// basic block number.
     std::vector<BBInfo> BBAnalysis;
     TargetSchedModel SchedModel;
 
     const TargetLoweringBase *TLI;
private:
     bool ReverseBranchCondition(BBInfo &BBI) const;
     bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
                      BranchProbability Prediction) const;
     bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
                        bool FalseBranch, unsigned &Dups,
                        BranchProbability Prediction) const;
     bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
                       unsigned &Dups1, unsigned &Dups2) const;
+    bool ValidDiamondTail(BBInfo &TrueBBI, BBInfo &FalseBBI,
+                          unsigned &Dups1, unsigned &Dups2,
+                          BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;
+    bool RecalculateCostsAndClobbers(MachineBasicBlock::iterator &BIB,
+                                     MachineBasicBlock::iterator &BIE,
+                                     BBInfo &BBIRecalc) const;
     void ScanInstructions(BBInfo &BBI);
     void AnalyzeBlock(MachineBasicBlock *MBB,
                       std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
     bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
                              bool isTriangle = false, bool RevBranch = false);
+    // Perform Feasability Analysis, assuming that BBI contains a shared tail.
+    // This disregards IsUnpredicable, as the tail may contain unpredicable
+    // instructions, but may be shared. It is assumed that the caller has
+    // verified this.
+    bool FeasibilityAnalysisSharedTail(
+        BBInfo &BBI, SmallVectorImpl<MachineOperand> &Pred);
     void AnalyzeBlocks(MachineFunction &MF,
                        std::vector<std::unique_ptr<IfcvtToken>> &Tokens);
     void InvalidatePreds(MachineBasicBlock *BB);
     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 RemoveTrueBranch, bool RemoveFalseBranch,
+                                bool MergeAddEdges);
     bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
                           unsigned NumDups1, unsigned NumDups2);
+    bool IfConvertDiamondTail(BBInfo &BBI, IfcvtKind Kind,
+                              unsigned NumDups1, unsigned NumDups2,
+                              bool TClobbers, bool FClobbers);
     void PredicateBlock(BBInfo &BBI,
                         MachineBasicBlock::iterator E,
                         SmallVectorImpl<MachineOperand> &Cond,
                         SmallSet<unsigned, 4> *LaterRedefs = nullptr);
     void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
                                SmallVectorImpl<MachineOperand> &Cond,
                                bool IgnoreBr = false);
     void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true);
while (!Tokens.empty()) {
         DEBUG(dbgs() << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
                      << BBI.TrueBB->getNumber() << ",F:"
                      << BBI.FalseBB->getNumber() << ") ");
         RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2);
         DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
         if (RetVal) ++NumDiamonds;
         break;
       }
+      case ICDiamondTail: {
+        if (DisableDiamondTail) break;
+        DEBUG(dbgs() << "Ifcvt (Diamond w/ tail): BB#" << BBI.BB->getNumber() << " (T:"
+                     << BBI.TrueBB->getNumber() << ",F:"
+                     << BBI.FalseBB->getNumber() << ") ");
+        RetVal = IfConvertDiamondTail(BBI, Kind, NumDups, NumDups2,
+                                      Token->TClobbersPred,
+                                      Token->FClobbersPred);
+        DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
+        if (RetVal) ++NumDiamondTails;
+        break;
+      }
       }
 
       Change |= RetVal;
 
       NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
         NumTriangleFalse + NumTriangleFRev + NumDiamonds;
       if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit)
         break;
if (SuccBB != TrueBB)
       return SuccBB;
   }
   return nullptr;
 }
 
 /// ReverseBranchCondition - Reverse the condition of the end of the block
 /// branch. Swap block's 'true' and 'false' successors.
 bool IfConverter::ReverseBranchCondition(BBInfo &BBI) const {
-  DebugLoc dl;  // FIXME: this is nowhere
+  DebugLoc dl;
+  MachineBasicBlock::iterator BBIT = BBI.BB->getFirstTerminator();
+  if (BBIT != BBI.BB->end())
+    dl = BBIT->getDebugLoc();
   if (!TII->ReverseBranchCondition(BBI.BrCond)) {
     TII->RemoveBranch(*BBI.BB);
     TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl);
     std::swap(BBI.TrueBB, BBI.FalseBB);
     return true;
   }
   return false;
 }
while (TIE != TIB && FIE != FIB) {
     // still don't want to count them.
     if (SkipConditionalBranches || !TIE->isBranch())
       ++Dups2;
     --TIE;
     --FIE;
   }
 }
 
+/// ValidDiamondTail - Returns true if the 'true' and 'false' blocks (along
+/// with their common predecessor) form a diamond if a common tail block is
+/// extracted
+bool IfConverter::ValidDiamondTail(
+    BBInfo &TrueBBI, BBInfo &FalseBBI,
+    unsigned &Dups1, unsigned &Dups2,
+    BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {
+  Dups1 = Dups2 = 0;
+  if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
+      FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
+    return false;
+
+  MachineBasicBlock *TT = TrueBBI.TrueBB;
+  MachineBasicBlock *TF = TrueBBI.FalseBB;
+  MachineBasicBlock *FT = FalseBBI.TrueBB;
+  MachineBasicBlock *FF = FalseBBI.FalseBB;
+
+  if (!TrueBBI.IsBrAnalyzable || !FalseBBI.IsBrAnalyzable)
+    return false;
+
+  if (!TT)
+    TT = getNextBlock(TrueBBI.BB);
+  if (!TF)
+    TF = getNextBlock(TrueBBI.BB);
+  if (!FT)
+    FT = getNextBlock(FalseBBI.BB);
+  if (!FF)
+    FF = getNextBlock(FalseBBI.BB);
+
+  if (!TT || !TF)
+    return false;
+  if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
+    return false;
+
+  // Only looking for the case where it's not an actual diamond.
+  if (TT == TF || FT == FF)
+    return false;
+
+  // Check successors. If they don't match, bail.
+  if (!((TT == FT && TF == FF) || (TF == FT && TT == FF)))
+    return false;
+
+  if (TF == FT && TT == FF) {
+    // If the branches are opposing, but we can't reverse, don't do it.
+    if (!FalseBBI.IsBrReversible)
+      return false;
+    ReverseBranchCondition(FalseBBI);
+  }
+
+  // Count duplicate instructions at the beginning of the true and false blocks.
+  MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();
+  MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();
+  MachineBasicBlock::iterator TIE = TrueBBI.BB->end();
+  MachineBasicBlock::iterator FIE = FalseBBI.BB->end();
+  countDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
+                              *TrueBBI.BB, *FalseBBI.BB,
+                              /* SkipConditionalBranches */ false);
+
+  // TIE and FIE both point at the last instruction, move them back.
+  ++TIE; ++FIE;
+  // The size of the blocks are the same.
+  TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;
+  FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;
+  // We only count extra cost for instructions that aren't shared.
+  TrueBBICalc.ExtraCost = TrueBBICalc.ExtraCost2 = 0;
+  FalseBBICalc.ExtraCost = FalseBBICalc.ExtraCost2 = 0;
+  TrueBBICalc.ClobbersPred = false;
+  FalseBBICalc.ClobbersPred = false;
+  if (!RecalculateCostsAndClobbers(TIB, TIE, TrueBBICalc))
+    return false;
+  if (!RecalculateCostsAndClobbers(FIB, FIE, FalseBBICalc))
+    return false;
+  if (TrueBBICalc.ClobbersPred && FalseBBICalc.ClobbersPred)
+    return false;
+  return true;
+}
+
+/// Run through the non-duplicated portion of a block and recalculate the cost
+/// predicate and whether the non-duplicated portion clobbers the predicate
+/// info.
+/// @param BIB points to the first non-shared instruction.
+/// @param BIE points to the first shared instruction in the tail, or End() if
+/// no instructions are shared.
+/// @param BBIRecalc a BBInfo structure to hold the results of recalculating.
+/// @return true if the block can be predicated.
+bool IfConverter::RecalculateCostsAndClobbers(MachineBasicBlock::iterator &BIB,
+                                              MachineBasicBlock::iterator &BIE,
+                                              BBInfo &BBIRecalc) const {
+  std::vector<MachineOperand> PredDefs;
+  while (BIB != BIE) {
+    // Skip dbg_value instructions. These do not count.
+    if (BIB->isDebugValue()) {
+      while (BIB != BIE && BIB->isDebugValue())
+        ++BIB;
+      if (BIB == BIE)
+        break;
+    }
+    // A Cond-clobbering instruction can only occur at the end of the
+    // non-duplicated section.
+    if (BBIRecalc.ClobbersPred)
+      return false;
+    if (TII->isPredicated(*BIB))
+      return false;
+    if (TII->DefinesPredicate(*BIB, PredDefs))
+      BBIRecalc.ClobbersPred = true;
+    if (BIB->isBranch())
+      return false;
+    if (!TII->isPredicable(*BIB))
+      return false;
+    unsigned ExtraPredCost = TII->getPredicationCost(*BIB);
+    unsigned NumCycles = SchedModel.computeInstrLatency(&(*BIB), false);
+    if (NumCycles > 1)
+      BBIRecalc.ExtraCost += NumCycles-1;
+    BBIRecalc.ExtraCost2 += ExtraPredCost;
+    ++BIB;
+  }
+  return true;
+};
 /// ValidDiamond - Returns true if the 'true' and 'false' blocks (along
 /// with their common predecessor) forms a valid diamond shape for ifcvt.
 bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
                                unsigned &Dups1, unsigned &Dups2) const {
   Dups1 = Dups2 = 0;
   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
       FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
     return false;
 
   MachineBasicBlock *TT = TrueBBI.TrueBB;
   MachineBasicBlock *FT = FalseBBI.TrueBB;
 
   if (!TT && blockAlwaysFallThrough(TrueBBI))
     TT = getNextBlock(TrueBBI.BB);
   if (!FT && blockAlwaysFallThrough(FalseBBI))
     FT = getNextBlock(FalseBBI.BB);
   if (TT != FT)
     return false;
   if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
     return false;
   if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
     return false;
 
   // FIXME: Allow true block to have an early exit?
   if (TrueBBI.FalseBB || FalseBBI.FalseBB ||
       (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred))
     return false;
 
   // Count duplicate instructions at the beginning and end of the true and
   // false blocks.
   MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();
   MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();
   MachineBasicBlock::iterator TIE = TrueBBI.BB->end();
   MachineBasicBlock::iterator FIE = FalseBBI.BB->end();
   countDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,
if (BBI.IsDone)
     return;
 
   bool AlreadyPredicated = !BBI.Predicate.empty();
   // First analyze the end of BB branches.
   BBI.TrueBB = BBI.FalseBB = nullptr;
   BBI.BrCond.clear();
   BBI.IsBrAnalyzable =
       !TII->analyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
+  SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
+  BBI.IsBrReversible = (RevCond.size() == 0) ||
+      !TII->ReverseBranchCondition(RevCond);
   BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == nullptr;
 
   if (BBI.BrCond.size()) {
     // No false branch. This BB must end with a conditional branch and a
     // fallthrough.
     if (!BBI.FalseBB)
       BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);
     if (!BBI.FalseBB) {
if (BBI.BrCond.size()) {
     if (TII->ReverseBranchCondition(RevPred) ||
         !TII->SubsumesPredicate(Cond, RevPred))
       return false;
   }
 
   return true;
 }
 
+/// FeasibilityAnalysisSharedTail - Determine if the block is a suitable
+/// candidate to be predicated by the specified predicate, assuming that all
+/// non predicable instructions are part of a shared tail.
+bool IfConverter::FeasibilityAnalysisSharedTail(
+    BBInfo &BBI, SmallVectorImpl<MachineOperand> &Pred) {
+  // If the block is dead, then it cannot be predicated. Don't check
+  // IsUnpredicable, because while the whole block may not be, the portion that
+  // is unshared may well be predicable.
+  if (BBI.IsDone)
+    return false;
+
+  // If it is already predicated but we couldn't analyze its terminator, the
+  // latter might fallthrough, but we can't determine where to.
+  // Conservatively avoid if-converting again.
+  if (BBI.Predicate.size() && !BBI.IsBrAnalyzable)
+    return false;
+
+  // If it is already predicated, check if the new predicate subsumes
+  // its predicate.
+  if (BBI.Predicate.size() && !TII->SubsumesPredicate(Pred, BBI.Predicate))
+    return false;
+
+  return true;
+}
+
 /// AnalyzeBlock - Analyze the structure of the sub-CFG starting from
 /// the specified block. Record its successors and whether it looks like an
 /// if-conversion candidate.
 void IfConverter::AnalyzeBlock(
     MachineBasicBlock *MBB, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {
   struct BBState {
     BBState(MachineBasicBlock *BB) : MBB(BB), SuccsAnalyzed(false) {}
     MachineBasicBlock *MBB;
if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
       //   \ /
       //  TailBB
       // Note TailBB can be empty.
       Tokens.push_back(llvm::make_unique<IfcvtToken>(
           BBI, ICDiamond, TNeedSub | FNeedSub, Dups, Dups2));
       Enqueued = true;
     }
 
+    BBInfo TrueBBICalc, FalseBBICalc;
+    if (CanRevCond && ValidDiamondTail(TrueBBI, FalseBBI, Dups, Dups2,
+                                       TrueBBICalc, FalseBBICalc) &&
+        MeetIfcvtSizeLimit(*TrueBBI.BB, (TrueBBICalc.NonPredSize - (Dups + Dups2) +
+                                         TrueBBICalc.ExtraCost),
+                           TrueBBICalc.ExtraCost2,
+                           *FalseBBI.BB, (FalseBBICalc.NonPredSize - (Dups + Dups2) +
+                                          FalseBBICalc.ExtraCost),
+                           FalseBBICalc.ExtraCost2,
+                           Prediction) &&
+        FeasibilityAnalysisSharedTail(TrueBBI, BBI.BrCond) &&
+        FeasibilityAnalysisSharedTail(FalseBBI, RevCond)) {
+      // DiamondTail:
+      // if TBB and FBB have a common tail that includes their conditional
+      // branch instructions, then we can If Convert this pattern.
+      //          EBB
+      //         _/ \_
+      //         |   |
+      //        TBB  FBB
+      //        / \ /   \
+      //  FalseBB TrueBB FalseBB
+      //
+      Tokens.push_back(llvm::make_unique<IfcvtToken>(
+          BBI, ICDiamondTail, TNeedSub | FNeedSub, Dups, Dups2,
+          (bool) TrueBBICalc.ClobbersPred, (bool) FalseBBICalc.ClobbersPred));
+      Enqueued = true;
+    }
+
     if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&
         MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
                            TrueBBI.ExtraCost2, Prediction) &&
         FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
       // Triangle:
       //   EBB
       //   | \_
       //   |  |
       //   | TBB
       //   |  /
bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
   CvtBBI->IsDone = true;
   if (FalseBBDead)
     NextBBI->IsDone = true;
 
   // FIXME: Must maintain LiveIns.
   return true;
 }
 
-/// IfConvertDiamond - If convert a diamond sub-CFG.
-///
-bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
-                                   unsigned NumDups1, unsigned NumDups2) {
-  BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
-  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
-  MachineBasicBlock *TailBB = TrueBBI.TrueBB;
-  // True block must fall through or end with an unanalyzable terminator.
-  if (!TailBB) {
-    if (blockAlwaysFallThrough(TrueBBI))
-      TailBB = FalseBBI.TrueBB;
-    assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
-  }
-
-  if (TrueBBI.IsDone || FalseBBI.IsDone ||
-      TrueBBI.BB->pred_size() > 1 ||
-      FalseBBI.BB->pred_size() > 1) {
+/// IfConvertDiamondCommon - Common code shared between diamond conversions.
+/// BBI, TrueBBI, and FalseBBI form the diamond shape.
+/// NumDups1 - number of shared instructions at the beginning of TrueBBI and
+///            FalseBBI
+/// NumDups2 - number of shared instructions at the end of TrueBBI and FalseBBI
+/// RemoveTrueBranch - Remove the branch of the true block before predicating
+///                    Only false for unanalyzable fallthrough cases.
+/// RemoveFalseBranch - Remove the branch of the false block before predicating
+///                     Only false for unanalyzable fallthrough cases.
+/// MergeAddEdges - Add successor edges when merging blocks. Only false for
+///                 unanalyzable fallthrough
+bool IfConverter::IfConvertDiamondCommon(
+    BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
+    unsigned NumDups1, unsigned NumDups2,
+    bool TClobbersPred, bool FClobbersPred,
+    bool RemoveTrueBranch, bool RemoveFalseBranch,
+    bool MergeAddEdges) {
+  if (TrueBBI.IsDone || FalseBBI.IsDone) {
     // Something has changed. It's no longer safe to predicate these blocks.
     BBI.IsAnalyzed = false;
     TrueBBI.IsAnalyzed = false;
     FalseBBI.IsAnalyzed = false;
     return false;
   }
 
   if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken())
     // Conservatively abort if-conversion if either BB has its address taken.
     return false;
 
   // Put the predicated instructions from the 'true' block before the
   // instructions from the 'false' block, unless the true block would clobber
   // the predicate, in which case, do the opposite.
   BBInfo *BBI1 = &TrueBBI;
   BBInfo *BBI2 = &FalseBBI;
   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
   if (TII->ReverseBranchCondition(RevCond))
     llvm_unreachable("Unable to reverse branch condition!");
   SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
   SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
 
   // Figure out the more profitable ordering.
   bool DoSwap = false;
-  if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred)
+  if (TClobbersPred && !FClobbersPred)
     DoSwap = true;
-  else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) {
+  else if (TClobbersPred == FClobbersPred) {
     if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
       DoSwap = true;
   }
   if (DoSwap) {
     std::swap(BBI1, BBI2);
     std::swap(Cond1, Cond2);
+    std::swap(RemoveTrueBranch, RemoveFalseBranch);
   }
 
   // Remove the conditional branch from entry to the blocks.
   BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
 
   // Initialize liveins to the first BB. These are potentially redefined by
   // predicated instructions.
   Redefs.init(TRI);
bool IfConverter::IfConvertDiamondCommon(
   for (MachineBasicBlock::const_iterator I = BBI1->BB->begin(), E = DI1; I != E;
        ++I) {
     SmallVector<std::pair<unsigned, const MachineOperand*>, 4> IgnoredClobbers;
     Redefs.stepForward(*I, IgnoredClobbers);
   }
   BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
   BBI2->BB->erase(BBI2->BB->begin(), DI2);
 
-  // Remove branch from the 'true' block, unless it was not analyzable.
-  // Non-analyzable branches need to be preserved, since in such cases,
-  // the CFG structure is not an actual diamond (the join block may not
-  // be present).
-  if (BBI1->IsBrAnalyzable)
+  if (RemoveTrueBranch)
     BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
   // Remove duplicated instructions.
   DI1 = BBI1->BB->end();
   for (unsigned i = 0; i != NumDups2; ) {
     // NumDups2 only counted non-dbg_value instructions, so this won't
     // run off the head of the list.
     assert (DI1 != BBI1->BB->begin());
     --DI1;
     // skip dbg_value instructions
     if (!DI1->isDebugValue())
       ++i;
   }
   BBI1->BB->erase(DI1, BBI1->BB->end());
 
   // Kill flags in the true block for registers living into the false block
   // must be removed.
   RemoveKills(BBI1->BB->begin(), BBI1->BB->end(), DontKill, *TRI);
 
-  // Remove 'false' block branch (unless it was not analyzable), and find
-  // the last instruction to predicate.
-  if (BBI2->IsBrAnalyzable)
+  // Remove 'false' block branch, and find the last instruction to predicate.
+  // Save the debug location.
+  if (RemoveFalseBranch)
     BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
   DI2 = BBI2->BB->end();
   while (NumDups2 != 0) {
     // NumDups2 only counted non-dbg_value instructions, so this won't
     // run off the head of the list.
     assert (DI2 != BBI2->BB->begin());
     --DI2;
     // skip dbg_value instructions
if (BBI1T != BBI1->BB->end() && TII->isPredicated(*BBI1T) &&
         BBI2T != BBI2->BB->end() && !TII->isPredicated(*BBI2T))
       --DI2;
   }
 
   // Predicate the 'false' block.
   PredicateBlock(*BBI2, DI2, *Cond2);
 
   // Merge the true block into the entry of the diamond.
-  MergeBlocks(BBI, *BBI1, TailBB == nullptr);
-  MergeBlocks(BBI, *BBI2, TailBB == nullptr);
+  MergeBlocks(BBI, *BBI1, MergeAddEdges);
+  MergeBlocks(BBI, *BBI2, MergeAddEdges);
+  return true;
+}
+
+/// IfConvertDiamondTail - If convert an almost-diamond sub-CFG where the true
+/// and false blocks share a common tail.
+bool IfConverter::IfConvertDiamondTail(
+    BBInfo &BBI, IfcvtKind Kind,
+    unsigned NumDups1, unsigned NumDups2,
+    bool TClobbersPred, bool FClobbersPred) {
+  BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
+  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
+
+  // Save the debug location for later.
+  DebugLoc dl;
+  MachineBasicBlock::iterator TIE = TrueBBI.BB->getFirstTerminator();
+  if (TIE != TrueBBI.BB->end())
+    dl = TIE->getDebugLoc();
+  // Removing branches from both blocks is safe, because we have already
+  // determined that both blocks have the same branch instructions. The branch
+  // will be added back at the end, unpredicated.
+  if (!IfConvertDiamondCommon(
+      BBI, TrueBBI, FalseBBI,
+      NumDups1, NumDups2,
+      TClobbersPred, FClobbersPred,
+      /* RemoveTrueBranch */ true, /* RemoveFalseBranch */ 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;
+}
+
+/// IfConvertDiamond - If convert a diamond sub-CFG.
+///
+bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
+                                   unsigned NumDups1, unsigned NumDups2) {
+  BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
+  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
+  MachineBasicBlock *TailBB = TrueBBI.TrueBB;
+
+  // True block must fall through or end with an unanalyzable terminator.
+  if (!TailBB) {
+    if (blockAlwaysFallThrough(TrueBBI))
+      TailBB = FalseBBI.TrueBB;
+    assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
+  }
+
+  if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) {
+    BBI.IsAnalyzed = false;
+    TrueBBI.IsAnalyzed = false;
+    FalseBBI.IsAnalyzed = false;
+    return false;
+  }
+
+  if (!IfConvertDiamondCommon(
+      BBI, TrueBBI, FalseBBI,
+      NumDups1, NumDups2,
+      TrueBBI.ClobbersPred, FalseBBI.ClobbersPred,
+      /* RemoveTrueBranch */ TrueBBI.IsBrAnalyzable,
+      /* RemoveFalseBranch */ FalseBBI.IsBrAnalyzable,
+      /* 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) {
     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))
       CanMergeTail = false;
     // There may still be a fall-through edge from BBI1 or BBI2 to TailBB;
     // check if there are any other predecessors besides those.
     unsigned NumPreds = TailBB->pred_size();
     if (NumPreds > 1)
       CanMergeTail = false;
     else if (NumPreds == 1 && CanMergeTail) {
       MachineBasicBlock::pred_iterator PI = TailBB->pred_begin();
-      if (*PI != BBI1->BB && *PI != BBI2->BB)
+      if (*PI != TrueBBI.BB && *PI != FalseBBI.BB)
         CanMergeTail = false;
     }
     if (CanMergeTail) {
       MergeBlocks(BBI, TailBBI);
       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(BBI1->BB);
-  BBI.BB->removeSuccessor(BBI2->BB, true);
+  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;

test/CodeGen/Thumb2/thumb2-ifcvt1.ll

 ; RUN: llc < %s -mtriple=thumbv7-apple-darwin | FileCheck %s
 ; RUN: llc < %s -mtriple=thumbv7-apple-darwin -arm-default-it | FileCheck %s
-; RUN: llc < %s -mtriple=thumbv8 -arm-no-restrict-it |FileCheck %s
+; RUN: llc < %s -mtriple=thumbv8 -arm-no-restrict-it | FileCheck %s
+; RUN: llc < %s -mtriple=thumbv8 -arm-no-restrict-it -enable-tail-merge=0 | FileCheck %s
 define i32 @t1(i32 %a, i32 %b, i32 %c, i32 %d) nounwind {
 ; CHECK-LABEL: t1:
 ; CHECK: ittt ne
 ; CHECK: cmpne
 ; CHECK: addne
 ; CHECK: bxne lr
   switch i32 %c, label %cond_next [
      i32 1, label %cond_true
      i32 7, label %cond_true
   ]
 
 cond_true:
   %tmp12 = add i32 %a, 1
   %tmp1518 = add i32 %tmp12, %b
   ret i32 %tmp1518
 
 cond_next:
   %tmp15 = add i32 %b, %a
   ret i32 %tmp15
 }
 
 define i32 @t2(i32 %a, i32 %b) nounwind {
 entry:
 ; CHECK-LABEL: t2:
-; CHECK: ite gt
-; CHECK: subgt
-; CHECK: suble
+; CHECK: ite {{gt|le}}
+; CHECK-DAG: suble
+; CHECK-DAG: subgt
   %tmp1434 = icmp eq i32 %a, %b    ; <i1> [#uses=1]
   br i1 %tmp1434, label %bb17, label %bb.outer
 
 bb.outer:   ; preds = %cond_false, %entry
   %b_addr.021.0.ph = phi i32 [ %b, %entry ], [ %tmp10, %cond_false ]    ; <i32> [#uses=5]
   %a_addr.026.0.ph = phi i32 [ %a, %entry ], [ %a_addr.026.0, %cond_false ]    ; <i32> [#uses=1]
   br label %bb