IfConversion: Fix branch predication bug.

[iteratee]

Summary

This bug shows up with diamonds that share unpredicable, unanalyzable branches.
There's an included test case from Hexagon. What was happening was that we were
attempting to predicate the branch instruction despite the fact that it was
checked to be the same. Now for unanalyzable branches we skip over the branch
instructions when predicating the block.

[iteratee]

Add forgotten testcase.

[davidxl]

lib/CodeGen/IfConversion.cpp

1778 ↗

(On Diff #69417)

Is trueBranch always analyzable?

1807 ↗

(On Diff #69417)

Why skipping debug value here? Does that affect the NumDups2 adjustment below?

[iteratee]

lib/CodeGen/IfConversion.cpp

1778 ↗

(On Diff #69417)

No, but we have previously verified that both blocks have the same branch instructions, so we only need one copy.

1807 ↗

(On Diff #69417)

Does that affect the NumDups2 adjustment below?

No. NumDups2 doesn't count debug values.

Would it be clearer if it read (DI2->isBranch() || DI2->isDebugValue())?

The goal is to skip all the branch instructions, because they have been checked to match MBB1 and don't need to predicated.
This is where the actual crash was occurring. We were attempting to predicate the branch instruction when we didn't need to.

[davidxl]

lib/CodeGen/IfConversion.cpp

1807 ↗

(On Diff #69417)

Ok. Can you add some comments?

Can you also add assertion to make sure that the instructions from two blocks are indeed common?

[iteratee]

Added assertion that branches are the same.
Added comments that we have already checked the sameness.
Verified that if I remove the earlier check for branch sameness, the later assertion does fire.

[iteratee]

lib/CodeGen/IfConversion.cpp

797 ↗

(On Diff #69447)

I shrank the space here, but don't see a need for a new diff.

[davidxl]

lib/CodeGen/IfConversion.cpp

1815–1820 ↗

(On Diff #69447)

Is it an expectation later that the terminator instruction (in two BBs) are either both removed or they both exist -- i.e. what verifySameInstructions does?

You patch looks right, but can you check why the problem does not appear before ? Is it because NumDups2 computation is different?

1843 ↗

(On Diff #69447)

Why not always skip it?

[iteratee]

Narrowed scope of branch match assertion to the un-analyzable case.

lib/CodeGen/IfConversion.cpp

1815–1820 ↗

(On Diff #69447)

They are expected to match except for a possible unconditional branch, and they may be reversed from each other.
If they are unanalyzable, they must match exactly.

It didn't occur because by rescanning, we find new opportunities to if-convert.

Previously if the branch instruction were unpredicable, the block was not considered a candidate for diamond if-conversion. Now, as long as the branch instruction at the end of the 2 blocks is the same, we are willing to diamond convert.

That means we now miss the case of a "diamond" where both sides end in an unanalyzable but predicable branch.

1843 ↗

(On Diff #69447)

For analyzable branches, the actual branch instruction may not be necessary. e.g. a diamond, where the join block is either merged, or a fallthrough. In that case, the caller will handle the branch.

[davidxl]

lgtm

llvm/trunk/lib/CodeGen/IfConversion.cpp

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 RemoveTrueBranch, bool RemoveFalseBranch,
-                                bool MergeAddEdges);
+                                bool RemoveBranch, bool MergeAddEdges);
     bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
                           unsigned NumDups1, unsigned NumDups2,
                           bool TClobbers, bool FClobbers);
     bool IfConvertForkedDiamond(BBInfo &BBI, IfcvtKind Kind,
                               unsigned NumDups1, unsigned NumDups2,
                               bool TClobbers, bool FClobbers);
     void PredicateBlock(BBInfo &BBI,
                         MachineBasicBlock::iterator E,
bool IfConverter::RescanInstructions(
   ScanInstructions(FalseBBI, FIB, FIE, BranchUnpredicable);
   if (FalseBBI.IsUnpredicable)
     return false;
   if (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)
     return false;
   return true;
 }
 
+#ifndef NDEBUG
+static void verifySameBranchInstructions(
+    MachineBasicBlock *MBB1,
+    MachineBasicBlock *MBB2) {
+  MachineBasicBlock::iterator B1 = MBB1->begin();
+  MachineBasicBlock::iterator B2 = MBB2->begin();
+  MachineBasicBlock::iterator E1 = std::prev(MBB1->end());
+  MachineBasicBlock::iterator E2 = std::prev(MBB2->end());
+  bool Empty1 = false, Empty2 = false;
+  while (!Empty1 && !Empty2) {
+    skipDebugInstructionsBackward(B1, E1, Empty1);
+    skipDebugInstructionsBackward(B2, E2, Empty2);
+    if (Empty1 && Empty2)
+      break;
+
+    if (Empty1) {
+      assert(!E2->isBranch() && "Branch mis-match, one block is empty.");
+      break;
+    }
+    if (Empty2) {
+      assert(!E1->isBranch() && "Branch mis-match, one block is empty.");
+      break;
+    }
+
+    if (E1->isBranch() || E2->isBranch())
+      assert(E1->isIdenticalTo(*E2) &&
+             "Branch mis-match, branch instructions don't match.");
+    else
+      break;
+    shrinkInclusiveRange(B1, E1, Empty1);
+    shrinkInclusiveRange(B2, E2, Empty2);
+  }
+}
+#endif
+
 /// ValidForkedDiamond - Returns true if the 'true' and 'false' blocks (along
 /// with their common predecessor) form a diamond if a common tail block is
 /// extracted.
 /// While not strictly a diamond, this pattern would form a diamond if
 /// tail-merging had merged the shared tails.
 ///           EBB
 ///         _/   \_
 ///         |     |

 }
 
 /// Common code shared between diamond conversions.
 /// \p BBI, \p TrueBBI, and \p FalseBBI form the diamond shape.
 /// \p NumDups1 - number of shared instructions at the beginning of \p TrueBBI
 ///               and FalseBBI
 /// \p NumDups2 - number of shared instructions at the end of \p TrueBBI
 ///               and \p FalseBBI
-/// \p RemoveTrueBranch - Remove the branch of the true block before predicating
-///                       Only false for unanalyzable fallthrough cases.
-/// \p RemoveFalseBranch - Remove the branch of the false block before
-///                        predicating Only false for unanalyzable fallthrough
-///                        cases.
+/// \p RemoveBranch - Remove the common branch of the two blocks before
+///                   predicating. Only false for unanalyzable fallthrough
+///                   cases. The caller will replace the branch if necessary.
 /// \p 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) {
+    bool RemoveBranch, bool MergeAddEdges) {
 
   if (TrueBBI.IsDone || FalseBBI.IsDone ||
       TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) {
     // Something has changed. It's no longer safe to predicate these blocks.
     BBI.IsAnalyzed = false;
     TrueBBI.IsAnalyzed = false;
     FalseBBI.IsAnalyzed = false;
     return false;
if (TClobbersPred && !FClobbersPred)
     DoSwap = true;
   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);
 
   MachineBasicBlock &MBB1 = *BBI1->BB;
   MachineBasicBlock &MBB2 = *BBI2->BB;
 
bool IfConverter::IfConvertDiamondCommon(
 
   for (const MachineInstr &MI : make_range(MBB1.begin(), DI1)) {
     SmallVector<std::pair<unsigned, const MachineOperand*>, 4> IgnoredClobbers;
     Redefs.stepForward(MI, IgnoredClobbers);
   }
   BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.begin(), DI1);
   MBB2.erase(MBB2.begin(), DI2);
 
-  if (RemoveTrueBranch)
-    BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
+  // The branches have been checked to match, so it is safe to remove the branch
+  // in BB1 and rely on the copy in BB2
+#ifndef NDEBUG
+  // Unanalyzable branches must match exactly. Check that now.
+  if (!BBI1->IsBrAnalyzable)
+    verifySameBranchInstructions(&MBB1, &MBB2);
+#endif
   // Remove duplicated instructions.
   DI1 = MBB1.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 != MBB1.begin());
     --DI1;
     // skip dbg_value instructions
     if (!DI1->isDebugValue())
       ++i;
   }
   MBB1.erase(DI1, MBB1.end());
 
   // Kill flags in the true block for registers living into the false block
   // must be removed.
   RemoveKills(MBB1.begin(), MBB1.end(), DontKill, *TRI);
 
-  // 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();
+  // The branches have been checked to match. Skip over the branch in the false
+  // block so that we don't try to predicate it.
+  if (RemoveBranch)
+    BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
+  else {
+    do {
+      assert(DI2 != MBB2.begin());
+      DI2--;
+    } while (DI2->isBranch() || DI2->isDebugValue());
+    DI2++;
+  }
   while (NumDups2 != 0) {
     // NumDups2 only counted non-dbg_value instructions, so this won't
     // run off the head of the list.
     assert(DI2 != MBB2.begin());
     --DI2;
     // skip dbg_value instructions
     if (!DI2->isDebugValue())
       --NumDups2;
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))
+      /* 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);
if (blockAlwaysFallThrough(TrueBBI))
       TailBB = FalseBBI.TrueBB;
     assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
   }
 
   if (!IfConvertDiamondCommon(
       BBI, TrueBBI, FalseBBI,
       NumDups1, NumDups2,
       TrueBBI.ClobbersPred, FalseBBI.ClobbersPred,
-      /* RemoveTrueBranch */ TrueBBI.IsBrAnalyzable,
-      /* RemoveFalseBranch */ FalseBBI.IsBrAnalyzable,
+      /* RemoveBranch */ TrueBBI.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) {

llvm/trunk/test/CodeGen/Hexagon/ifcvt-diamond-bug-2016-08-26.ll

+; RUN: llc -march=hexagon -o - %s | FileCheck %s
+target triple = "hexagon"
+
+%struct.0 = type { i16, i16 }
+
+@t = external local_unnamed_addr global %struct.0, align 2
+
+define void @foo(i32 %p) local_unnamed_addr #0 {
+entry:
+  %conv90 = trunc i32 %p to i16
+  %call105 = call signext i16 @bar(i16 signext 16384, i16 signext undef) #0
+  %call175 = call signext i16 @bar(i16 signext %conv90, i16 signext 4) #0
+  %call197 = call signext i16 @bar(i16 signext %conv90, i16 signext 4) #0
+  %cmp199 = icmp eq i16 %call197, 0
+  br i1 %cmp199, label %if.then200, label %if.else201
+
+; CHECK-DAG: [[R4:r[0-9]+]] = #4
+; CHECK: p0 = cmp.eq(r0, #0)
+; CHECK: if (!p0.new) [[R3:r[0-9]+]] = #3
+; CHECK-DAG: if (!p0) memh(##t) = [[R3]]
+; CHECK-DAG: if (p0) memh(##t) = [[R4]]
+if.then200:                                       ; preds = %entry
+  store i16 4, i16* getelementptr inbounds (%struct.0, %struct.0* @t, i32 0, i32 0), align 2
+  store i16 0, i16* getelementptr inbounds (%struct.0, %struct.0* @t, i32 0, i32 1), align 2
+  br label %if.end202
+
+if.else201:                                       ; preds = %entry
+  store i16 3, i16* getelementptr inbounds (%struct.0, %struct.0* @t, i32 0, i32 0), align 2
+  br label %if.end202
+
+if.end202:                                        ; preds = %if.else201, %if.then200
+  ret void
+}
+
+declare signext i16 @bar(i16 signext, i16 signext) local_unnamed_addr #0
+
+attributes #0 = { optsize "target-cpu"="hexagonv55" }