[SimlifyCFG] Prevent passes from destroying canonical loop structure, especially for nested loops

    
When eliminating or merging almost empty basic blocks, the existence of non-trivial PHI nodes
is currently used to recognize potential loops of which the block is the header and keep the block.
However, the current algorithm fails if the loops' exit condition is evaluated only with volatile
values hence no PHI nodes in the header. Especially when such a loop is an outer loop of a nested
loop, the loop is collapsed into a single loop which prevent later optimizations from being
applied (e.g., transforming nested loops into simplified forms and loop vectorization).
    
The patch augments the existing PHI node-based check by adding a pre-test if the BB actually
belongs to a set of loop headers and not eliminating it if yes.

llvm-svn: 264697

1 files changed, 16 insertions, 16 deletions

diff --git a/llvm/test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll b/llvm/test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll
index 13ccad6a1ee..21e9bc7b7f4 100644
--- a/llvm/test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll
+++ b/llvm/test/Transforms/SimplifyCFG/2008-05-16-PHIBlockMerge.ll
@@ -1,6 +1,6 @@
 ; RUN: opt < %s -simplifycfg -S > %t
 ; RUN: not grep "^BB.tomerge" %t
-; RUN: grep "^BB.nomerge" %t | count 2
+; RUN: grep "^BB.nomerge" %t | count 4
 
 ; ModuleID = '<stdin>' 
 declare i1 @foo()
@@ -54,24 +54,24 @@ Exit:		; preds = %Succ
 	ret void
 }
 
-; This function can be merged
+; This function can't be merged (for keeping canonical loop structures)
 define void @c() {
 entry:
-	br label %BB.tomerge
+	br label %BB.nomerge
 
-BB.tomerge:		; preds = %Common, %entry
+BB.nomerge:		; preds = %Common, %entry
 	br label %Succ
 
 Succ:		; preds = %Common, %BB.tomerge, %Pre-Exit
         ; This phi has identical values for Common and (through BB) Common,
         ; blocks can't be merged
-	%b = phi i32 [ 1, %BB.tomerge ], [ 1, %Common ], [ 2, %Pre-Exit ]
+	%b = phi i32 [ 1, %BB.nomerge ], [ 1, %Common ], [ 2, %Pre-Exit ]
 	%conde = call i1 @foo( )		; <i1> [#uses=1]
 	br i1 %conde, label %Common, label %Pre-Exit
 
 Common:		; preds = %Succ
 	%cond = call i1 @foo( )		; <i1> [#uses=1]
-	br i1 %cond, label %BB.tomerge, label %Succ
+	br i1 %cond, label %BB.nomerge, label %Succ
 
 Pre-Exit:       ; preds = %Succ
         ; This adds a backedge, so the %b phi node gets a third branch and is
@@ -83,25 +83,25 @@ Exit:		; preds = %Pre-Exit
 	ret void
 }
 
-; This function can be merged
+; This function can't be merged (for keeping canonical loop structures)
 define void @d() {
 entry:
-	br label %BB.tomerge
+	br label %BB.nomerge
 
-BB.tomerge:		; preds = %Common, %entry
+BB.nomerge:		; preds = %Common, %entry
         ; This phi has a matching value (0) with below phi (0), so blocks
         ; can be merged.
 	%a = phi i32 [ 1, %entry ], [ 0, %Common ]		; <i32> [#uses=1]
 	br label %Succ
 
 Succ:		; preds = %Common, %BB.tomerge
-	%b = phi i32 [ %a, %BB.tomerge ], [ 0, %Common ]		; <i32> [#uses=0]
+	%b = phi i32 [ %a, %BB.nomerge ], [ 0, %Common ]		; <i32> [#uses=0]
 	%conde = call i1 @foo( )		; <i1> [#uses=1]
 	br i1 %conde, label %Common, label %Exit
 
 Common:		; preds = %Succ
 	%cond = call i1 @foo( )		; <i1> [#uses=1]
-	br i1 %cond, label %BB.tomerge, label %Succ
+	br i1 %cond, label %BB.nomerge, label %Succ
 
 Exit:		; preds = %Succ
 	ret void
@@ -110,21 +110,21 @@ Exit:		; preds = %Succ
 ; This function can be merged
 define void @e() {
 entry:
-	br label %BB.tomerge
+	br label %Succ
 
-BB.tomerge:		; preds = %Use, %entry
+Succ:		; preds = %Use, %entry
         ; This phi is used somewhere else than Succ, but this should not prevent
         ; merging this block
 	%a = phi i32 [ 1, %entry ], [ 0, %Use ]		; <i32> [#uses=1]
-	br label %Succ
+	br label %BB.tomerge
 
-Succ:		; preds = %BB.tomerge
+BB.tomerge:		; preds = %BB.tomerge
 	%conde = call i1 @foo( )		; <i1> [#uses=1]
 	br i1 %conde, label %Use, label %Exit
 
 Use:		; preds = %Succ
 	%cond = call i1 @bar( i32 %a )		; <i1> [#uses=1]
-	br i1 %cond, label %BB.tomerge, label %Exit
+	br i1 %cond, label %Succ, label %Exit
 
 Exit:		; preds = %Use, %Succ
 	ret void