Fixes PR 1200

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

4 files changed, 103 insertions, 15 deletions

diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp
index 10262f2854..9145418cc3 100644
--- a/lib/CodeGen/BranchFolding.cpp
+++ b/lib/CodeGen/BranchFolding.cpp
@@ -431,6 +431,9 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
 bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
   MadeChange = false;
   
+  // Make sure blocks are numbered in order
+  MF.RenumberBlocks();
+
   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
     MachineBasicBlock *MBB = I++;
     OptimizeBlock(MBB);
@@ -849,22 +852,35 @@ void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
                       PriorTBB, PriorFBB, PriorCond)) {
     // Now we know that there was no fall-through into this block, check to
     // see if it has a fall-through into its successor.
-    if (!CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB, CurCond)) {
-      // Check all the predecessors of this block.  If one of them has no fall
-      // throughs, move this block right after it.
-      for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
-           E = MBB->pred_end(); PI != E; ++PI) {
-        // Analyze the branch at the end of the pred.
-        MachineBasicBlock *PredBB = *PI;
-        MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
-        std::vector<MachineOperand> PredCond;
-        if (PredBB != MBB && !CanFallThrough(PredBB)) {
-          MBB->moveAfter(PredBB);
-          MadeChange = true;
-          return OptimizeBlock(MBB);
+    bool CurFallsThru = CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB, 
+                                            CurCond);
+
+    // Check all the predecessors of this block.  If one of them has no fall
+    // throughs, move this block right after it.
+    for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
+         E = MBB->pred_end(); PI != E; ++PI) {
+      // Analyze the branch at the end of the pred.
+      MachineBasicBlock *PredBB = *PI;
+      MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
+      if (PredBB != MBB && !CanFallThrough(PredBB)
+          && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
+        // If the current block doesn't fall through, just move it.
+        // If the current block can fall through and does not end with a
+        // conditional branch, we need to append an unconditional jump to 
+        // the (current) next block.  To avoid a possible compile-time
+        // infinite loop, move blocks only backward in this case.
+        if (CurFallsThru) {
+          MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB));
+          CurCond.clear();
+          TII->InsertBranch(*MBB, NextBB, 0, CurCond);
         }
+        MBB->moveAfter(PredBB);
+        MadeChange = true;
+        return OptimizeBlock(MBB);
       }
+    }
         
+    if (!CurFallsThru) {
       // Check all successors to see if we can move this block before it.
       for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
            E = MBB->succ_end(); SI != E; ++SI) {
diff --git a/test/CodeGen/Generic/2007-02-16-BranchFold.ll b/test/CodeGen/Generic/2007-02-16-BranchFold.ll
new file mode 100644
index 0000000000..13ed6526e0
--- /dev/null
+++ b/test/CodeGen/Generic/2007-02-16-BranchFold.ll
@@ -0,0 +1,71 @@
+; RUN: llvm-as < %s | llc &&
+; RUN: llvm-as < %s | llc | grep jmp | wc -l | grep 0
+
+; ModuleID = 'bugpoint.test.bc'
+target datalayout = "e-p:32:32"
+target triple = "i686-apple-darwin8"
+	%struct.FILE = type { i8*, i32, i32, i16, i16, %struct.__sbuf, i32, i8*, i32 (i8*)*, i32 (i8*, i8*, i32)*, i64 (i8*, i64, i32)*, i32 (i8*, i8*, i32)*, %struct.__sbuf, %struct.__sFILEX*, i32, [3 x i8], [1 x i8], %struct.__sbuf, i32, i64 }
+	%struct.Index_Map = type { i32, %struct.item_set** }
+	%struct.Item = type { [4 x i16], %struct.rule* }
+	%struct.__sFILEX = type opaque
+	%struct.__sbuf = type { i8*, i32 }
+	%struct.dimension = type { i16*, %struct.Index_Map, %struct.mapping*, i32, %struct.plankMap* }
+	%struct.item_set = type { i32, i32, %struct.operator*, [2 x %struct.item_set*], %struct.item_set*, i16*, %struct.Item*, %struct.Item* }
+	%struct.list = type { i8*, %struct.list* }
+	%struct.mapping = type { %struct.list**, i32, i32, i32, %struct.item_set** }
+	%struct.nonterminal = type { i8*, i32, i32, i32, %struct.plankMap*, %struct.rule* }
+	%struct.operator = type { i8*, i8, i32, i32, i32, i32, %struct.table* }
+	%struct.pattern = type { %struct.nonterminal*, %struct.operator*, [2 x %struct.nonterminal*] }
+	%struct.plank = type { i8*, %struct.list*, i32 }
+	%struct.plankMap = type { %struct.list*, i32, %struct.stateMap* }
+	%struct.rule = type { [4 x i16], i32, i32, i32, %struct.nonterminal*, %struct.pattern*, i8 }
+	%struct.stateMap = type { i8*, %struct.plank*, i32, i16* }
+	%struct.table = type { %struct.operator*, %struct.list*, i16*, [2 x %struct.dimension*], %struct.item_set** }
+@outfile = external global %struct.FILE*		; <%struct.FILE**> [#uses=1]
+@str1 = external global [11 x i8]		; <[11 x i8]*> [#uses=1]
+
+implementation   ; Functions:
+
+declare i32 @fprintf(%struct.FILE*, i8*, ...)
+
+define i16 @main_bb_2E_i9_2E_i_2E_i932_2E_ce(%struct.list* %l_addr.01.0.i2.i.i929, %struct.operator** %tmp66.i62.i.out) {
+newFuncRoot:
+	br label %bb.i9.i.i932.ce
+
+bb36.i.i.exitStub:		; preds = %bb.i9.i.i932.ce
+	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
+	ret i16 0
+
+bb.i14.i.exitStub:		; preds = %bb.i9.i.i932.ce
+	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
+	ret i16 1
+
+bb12.i.i935.exitStub:		; preds = %bb.i9.i.i932.ce
+	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
+	ret i16 2
+
+bb20.i.i937.exitStub:		; preds = %bb.i9.i.i932.ce
+	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
+	ret i16 3
+
+bb28.i.i938.exitStub:		; preds = %bb.i9.i.i932.ce
+	store %struct.operator* %tmp66.i62.i, %struct.operator** %tmp66.i62.i.out
+	ret i16 4
+
+bb.i9.i.i932.ce:		; preds = %newFuncRoot
+	%tmp1.i3.i.i930 = getelementptr %struct.list* %l_addr.01.0.i2.i.i929, i32 0, i32 0		; <i8**> [#uses=1]
+	%tmp2.i4.i.i931 = load i8** %tmp1.i3.i.i930		; <i8*> [#uses=1]
+	%tmp66.i62.i = bitcast i8* %tmp2.i4.i.i931 to %struct.operator*		; <%struct.operator*> [#uses=7]
+	%tmp1.i6.i = getelementptr %struct.operator* %tmp66.i62.i, i32 0, i32 2		; <i32*> [#uses=1]
+	%tmp2.i7.i = load i32* %tmp1.i6.i		; <i32> [#uses=1]
+	%tmp3.i8.i = load %struct.FILE** @outfile		; <%struct.FILE*> [#uses=1]
+	%tmp5.i9.i = call i32 (%struct.FILE*, i8*, ...)* @fprintf( %struct.FILE* %tmp3.i8.i, i8* getelementptr ([11 x i8]* @str1, i32 0, i32 0), i32 %tmp2.i7.i )		; <i32> [#uses=0]
+	%tmp7.i10.i = getelementptr %struct.operator* %tmp66.i62.i, i32 0, i32 5		; <i32*> [#uses=1]
+	%tmp8.i11.i = load i32* %tmp7.i10.i		; <i32> [#uses=1]
+	switch i32 %tmp8.i11.i, label %bb36.i.i.exitStub [
+		 i32 -1, label %bb.i14.i.exitStub
+		 i32 0, label %bb12.i.i935.exitStub
+		 i32 1, label %bb20.i.i937.exitStub
+		 i32 2, label %bb28.i.i938.exitStub
+	]
+}
diff --git a/test/CodeGen/PowerPC/branch-opt.ll b/test/CodeGen/PowerPC/branch-opt.ll
index 7f40a2d866..9048f0f8d1 100644
--- a/test/CodeGen/PowerPC/branch-opt.ll
+++ b/test/CodeGen/PowerPC/branch-opt.ll
@@ -1,5 +1,6 @@
 ; RUN: llvm-upgrade < %s | llvm-as | llc -march=ppc32 &&
-; RUN: llvm-upgrade < %s | llvm-as | llc -march=ppc32 | grep 'b LBB.*cond_next48.loopexit' | wc -l | grep 1
+; RUN: llvm-upgrade < %s | llvm-as | llc -march=ppc32 | grep 'b LBB.*' | wc -l | grep 5
+;;; FIXME, 4 unconditional branches is minimal
 
 target endian = big
 target pointersize = 32
diff --git a/test/CodeGen/X86/2006-10-19-SwitchUnnecessaryBranching.ll b/test/CodeGen/X86/2006-10-19-SwitchUnnecessaryBranching.ll
index 5103679ccc..48c6a1a69e 100644
--- a/test/CodeGen/X86/2006-10-19-SwitchUnnecessaryBranching.ll
+++ b/test/CodeGen/X86/2006-10-19-SwitchUnnecessaryBranching.ll
@@ -1,4 +1,4 @@
-; RUN: llvm-upgrade < %s | llvm-as | llc -march=x86 | %prcontext je 1 | grep "BB1_4:"
+; RUN: llvm-upgrade < %s | llvm-as | llc -march=x86 | %prcontext je 1 | grep "BB1_1:"
 
 %str = internal constant [14 x sbyte] c"Hello world!\0A\00"		; <[14 x sbyte]*> [#uses=1]
 %str = internal constant [13 x sbyte] c"Blah world!\0A\00"		; <[13 x sbyte]*> [#uses=1]