Make tail merging handle blocks with repeated predecessors correctly, and

remove RemoveDuplicateSuccessor, as it is no longer necessary, and because
it breaks assumptions made in
MachineBasicBlock::isOnlyReachableByFallthrough.

Convert test/CodeGen/X86/omit-label.ll to FileCheck and add a testcase
for PR4732.

test/CodeGen/Thumb2/thumb2-ifcvt2.ll sees a diff with this commit due to
it being bugpoint-reduced to the point where it doesn't matter what the
condition for the branch is.

Add some more interesting code to
test/CodeGen/X86/2009-08-06-branchfolder-crash.ll, which is the testcase
that originally motivated the RemoveDuplicateSuccessor code, to help
verify that the original problem isn't being re-broken.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79338 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 93 insertions, 28 deletions

diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp
index 1ab3df2857..1ce83f81af 100644
--- a/lib/CodeGen/BranchFolding.cpp
+++ b/lib/CodeGen/BranchFolding.cpp
@@ -700,6 +700,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
 
   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
     if (I->pred_size() >= 2 && I->pred_size() < TailMergeThreshold) {
+      SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;
       MachineBasicBlock *IBB = I;
       MachineBasicBlock *PredBB = prior(I);
       MergePotentials.clear();
@@ -710,6 +711,9 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
         // Skip blocks that loop to themselves, can't tail merge these.
         if (PBB==IBB)
           continue;
+        // Visit each predecessor only once.
+        if (!UniquePreds.insert(PBB))
+          continue;
         MachineBasicBlock *TBB = 0, *FBB = 0;
         SmallVector<MachineOperand, 4> Cond;
         if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) {
@@ -850,27 +854,6 @@ bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) {
   return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond);
 }
 
-/// RemoveDuplicateSuccessor - make sure block Pred has at most one
-/// successor edge leading to Succ.  This is only called in one place,
-/// but Chris prefers that it be a separate function.
-static void RemoveDuplicateSuccessor(MachineBasicBlock *Pred,
-                                     MachineBasicBlock *Succ) {
-  MachineBasicBlock::succ_iterator SI = Pred->succ_begin();
-  bool found = false;
-  while (SI != Pred->succ_end()) {
-    if (*SI == Succ) {
-      if (!found) {
-        found = true;
-        ++SI;
-      } else {
-        SI = Pred->removeSuccessor(SI);
-      }
-    } else {
-      ++SI;
-    }
-  }
-}
-
 /// IsBetterFallthrough - Return true if it would be clearly better to
 /// fall-through to MBB1 than to fall through into MBB2.  This has to return
 /// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
@@ -914,10 +897,6 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
       while (!MBB->pred_empty()) {
         MachineBasicBlock *Pred = *(MBB->pred_end()-1);
         Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);
-        // If this resulted in a predecessor with true and false edges
-        // both going to the fallthrough block, clean up; 
-        // BranchFolding doesn't like this.
-        RemoveDuplicateSuccessor(Pred, FallThrough);
       }
       // If MBB was the target of a jump table, update jump tables to go to the
       // fallthrough instead.
diff --git a/test/CodeGen/Thumb2/thumb2-ifcvt2.ll b/test/CodeGen/Thumb2/thumb2-ifcvt2.ll
index 15ccb2d185..299ab4d642 100644
--- a/test/CodeGen/Thumb2/thumb2-ifcvt2.ll
+++ b/test/CodeGen/Thumb2/thumb2-ifcvt2.ll
@@ -82,7 +82,7 @@ define fastcc void @t2() nounwind {
 entry:
 ; CHECK: t2:
 ; CHECK: cmp r0, #0
-; CHECK: bne.n
+; CHECK: beq.n
 	br i1 undef, label %bb.i.i3, label %growMapping.exit
 
 bb.i.i3:		; preds = %entry
diff --git a/test/CodeGen/X86/2009-08-06-branchfolder-crash.ll b/test/CodeGen/X86/2009-08-06-branchfolder-crash.ll
index 5e58725cb9..2c8cf0c8cd 100644
--- a/test/CodeGen/X86/2009-08-06-branchfolder-crash.ll
+++ b/test/CodeGen/X86/2009-08-06-branchfolder-crash.ll
@@ -88,3 +88,55 @@ for.inc:		; preds = %for.inc, %lor.end.i, %lor.rhs.i, %land.lhs.true3.i
 }
 
 declare i32 @safe()
+
+define i32 @func_35(i8 signext %p_35) nounwind readonly {
+entry:
+  %tobool = icmp eq i8 %p_35, 0                   ; <i1> [#uses=1]
+  br i1 %tobool, label %lor.lhs.false, label %if.then
+
+lor.lhs.false:                                    ; preds = %entry
+  %tmp1 = load i8* @g_3                           ; <i8> [#uses=1]
+  %tobool3 = icmp eq i8 %tmp1, 0                  ; <i1> [#uses=1]
+  br i1 %tobool3, label %return, label %if.then
+
+if.then:                                          ; preds = %lor.lhs.false, %entry
+  %tmp4 = load i8* @g_3                           ; <i8> [#uses=1]
+  %conv5 = sext i8 %tmp4 to i32                   ; <i32> [#uses=1]
+  ret i32 %conv5
+
+return:                                           ; preds = %lor.lhs.false
+  ret i32 0
+}
+
+define void @bar(i32 %p_5) noreturn nounwind {
+entry:
+  %cmp = icmp sgt i32 %p_5, 0                     ; <i1> [#uses=2]
+  %call = tail call i32 @safe() nounwind          ; <i32> [#uses=1]
+  %conv1 = trunc i32 %call to i8                  ; <i8> [#uses=3]
+  %tobool.i = xor i1 %cmp, true                   ; <i1> [#uses=3]
+  %cmp.i = icmp sgt i8 %conv1, 0                  ; <i1> [#uses=3]
+  %or.cond.i = or i1 %cmp.i, %tobool.i            ; <i1> [#uses=1]
+  br i1 %or.cond.i, label %lor.rhs.i, label %land.lhs.true3.i
+
+land.lhs.true3.i:                                 ; preds = %entry
+  %xor = zext i1 %cmp to i32                      ; <i32> [#uses=1]
+  %conv5.i = sext i8 %conv1 to i32                ; <i32> [#uses=1]
+  %cmp7.i = icmp slt i32 %conv5.i, %xor           ; <i1> [#uses=1]
+  %cmp7.i.not = xor i1 %cmp7.i, true              ; <i1> [#uses=1]
+  %or.cond23.i = and i1 %cmp.i, %tobool.i         ; <i1> [#uses=1]
+  %or.cond = and i1 %cmp7.i.not, %or.cond23.i     ; <i1> [#uses=1]
+  br i1 %or.cond, label %lor.end.i, label %for.inc
+
+lor.rhs.i:                                        ; preds = %entry
+  %or.cond23.i.old = and i1 %cmp.i, %tobool.i     ; <i1> [#uses=1]
+  br i1 %or.cond23.i.old, label %lor.end.i, label %for.inc
+
+lor.end.i:                                        ; preds = %lor.rhs.i, %land.lhs.true3.i
+  %tobool19.i = icmp eq i8 %conv1, 0              ; <i1> [#uses=0]
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.inc, %lor.end.i, %lor.rhs.i, %land.lhs.true3.i
+  br label %for.inc
+}
+
+declare i32 @safe()
diff --git a/test/CodeGen/X86/omit-label.ll b/test/CodeGen/X86/omit-label.ll
index 457b66b35d..6450f95d9b 100644
--- a/test/CodeGen/X86/omit-label.ll
+++ b/test/CodeGen/X86/omit-label.ll
@@ -1,7 +1,11 @@
-; RUN: llvm-as < %s | llc -march=x86-64 | grep BB1_1:
+; RUN: llvm-as < %s | llc -march=x86-64 -asm-verbose=false | FileCheck %s
 ; PR4126
+; PR4732
 
-; Don't omit this label's definition.
+; Don't omit these labels' definitions.
+
+; CHECK: bux:
+; CHECK: .LBB1_1:
 
 define void @bux(i32 %p_53) nounwind optsize {
 entry:
@@ -21,3 +25,33 @@ bb3:		; preds = %bb.i, %entry
 }
 
 declare i32 @baz(...)
+
+; Don't omit this label in the assembly output.
+; CHECK: int321:
+; CHECK:    jne .LBB2_1
+; CHECK:    jle .LBB2_1
+; CHECK: .LBB2_1:
+
+define void @int321(i8 signext %p_103, i32 %uint8p_104) nounwind readnone {
+entry:
+  %tobool = icmp eq i8 %p_103, 0                  ; <i1> [#uses=1]
+  %cmp.i = icmp sgt i8 %p_103, 0                  ; <i1> [#uses=1]
+  %or.cond = and i1 %tobool, %cmp.i               ; <i1> [#uses=1]
+  br i1 %or.cond, label %land.end.i, label %for.cond.preheader
+
+land.end.i:                                       ; preds = %entry
+  %conv3.i = sext i8 %p_103 to i32                ; <i32> [#uses=1]
+  %div.i = sdiv i32 1, %conv3.i                   ; <i32> [#uses=1]
+  %tobool.i = icmp eq i32 %div.i, -2147483647     ; <i1> [#uses=0]
+  br label %for.cond.preheader
+
+for.cond.preheader:                               ; preds = %land.end.i, %entry
+  %cmp = icmp sgt i8 %p_103, 1                    ; <i1> [#uses=1]
+  br i1 %cmp, label %for.end.split, label %for.cond
+
+for.cond:                                         ; preds = %for.cond.preheader, %for.cond
+  br label %for.cond
+
+for.end.split:                                    ; preds = %for.cond.preheader
+  ret void
+}