Prevent loop-unroll from making assumptions about undefined behavior.

Fixes rdar:14036816, PR16130.

There is an opportunity to compute precise trip counts for 'or'
expressions and multi-exit loops.
rdar:14038809: Optimize trip count computation for multi-exit loops.

To do this we need to record the fact that ExitLimit assumes NSW. When
it does not we can safely assume that the loop trip count is the
minimum ExitLimt across all subexpressions and loop exits.

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

2 files changed, 62 insertions, 22 deletions

diff --git a/test/Transforms/LoopUnroll/scevunroll.ll b/test/Transforms/LoopUnroll/scevunroll.ll
index 99b3a7d..308a036 100644
--- a/test/Transforms/LoopUnroll/scevunroll.ll
+++ b/test/Transforms/LoopUnroll/scevunroll.ll
@@ -66,13 +66,16 @@ exit2:
 
 ; SCEV properly unrolls multi-exit loops.
 ;
+; SCEV cannot currently unroll this loop.
+; It should ideally detect a trip count of 5.
+; rdar:14038809 [SCEV]: Optimize trip count computation for multi-exit loops.
 ; CHECK: @multiExit
-; CHECK: getelementptr i32* %base, i32 10
-; CHECK-NEXT: load i32*
-; CHECK: br i1 false, label %l2.10, label %exit1
-; CHECK: l2.10:
-; CHECK-NOT: br
-; CHECK: ret i32
+; CHECKFIXME: getelementptr i32* %base, i32 10
+; CHECKFIXME-NEXT: load i32*
+; CHECKFIXME: br i1 false, label %l2.10, label %exit1
+; CHECKFIXME: l2.10:
+; CHECKFIXME-NOT: br
+; CHECKFIXME: ret i32
 define i32 @multiExit(i32* %base) nounwind {
 entry:
   br label %l1
@@ -170,3 +173,38 @@ for.body87:
   br label %for.body87
 }
 
+; PR16130: clang produces incorrect code with loop/expression at -O2
+; rdar:14036816 loop-unroll makes assumptions about undefined behavior
+;
+; The loop latch is assumed to exit after the first iteration because
+; of the induction variable's NSW flag. However, the loop latch's
+; equality test is skipped and the loop exits after the second
+; iteration via the early exit. So loop unrolling cannot assume that
+; the loop latch's exit count of zero is an upper bound on the number
+; of iterations.
+;
+; CHECK: @nsw_latch
+; CHECK: for.body:
+; CHECK: %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ]
+; CHECK: return:
+; CHECK: %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ]
+define void @nsw_latch(i32* %a) nounwind {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.cond, %entry
+  %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ]
+  %tobool = icmp eq i32 %b.03, 0
+  %add = add nsw i32 %b.03, 8
+  br i1 %tobool, label %for.cond, label %return
+
+for.cond:                                         ; preds = %for.body
+  %cmp = icmp eq i32 %add, 13
+  br i1 %cmp, label %return, label %for.body
+
+return:                                           ; preds = %for.body, %for.cond
+  %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ]
+  %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ]
+  store i32 %b.03.lcssa, i32* %a, align 4
+  ret void
+}
diff --git a/test/Transforms/LoopUnroll/unloop.ll b/test/Transforms/LoopUnroll/unloop.ll
index 5a9cacd..9a938cc 100644
--- a/test/Transforms/LoopUnroll/unloop.ll
+++ b/test/Transforms/LoopUnroll/unloop.ll
@@ -21,8 +21,8 @@ outer:
 inner:
   %iv = phi i32 [ 0, %outer ], [ %inc, %tail ]
   %inc = add i32 %iv, 1
-  %wbucond = call zeroext i1 @check()
-  br i1 %wbucond, label %outer.backedge, label %tail
+  call zeroext i1 @check()
+  br i1 true, label %outer.backedge, label %tail
 
 tail:
   br i1 false, label %inner, label %exit
@@ -126,25 +126,27 @@ return:
 ; Ensure that only the middle loop is removed and rely on verify-loopinfo to
 ; check soundness.
 ;
-; CHECK: @unloopDeepNested
+; This test must be disabled until trip count computation can be optimized...
+; rdar:14038809 [SCEV]: Optimize trip count computation for multi-exit loops.
+; CHECKFIXME: @unloopDeepNested
 ; Inner-inner loop control.
-; CHECK: while.cond.us.i:
-; CHECK: br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
-; CHECK: if.then.us.i:
-; CHECK: br label %while.cond.us.i
+; CHECKFIXME: while.cond.us.i:
+; CHECKFIXME: br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i
+; CHECKFIXME: if.then.us.i:
+; CHECKFIXME: br label %while.cond.us.i
 ; Inner loop tail.
-; CHECK: if.else.i:
-; CHECK: br label %while.cond.outer.i
+; CHECKFIXME: if.else.i:
+; CHECKFIXME: br label %while.cond.outer.i
 ; Middle loop control (removed).
-; CHECK: valid_data.exit:
-; CHECK-NOT: br
-; CHECK: %cmp = call zeroext i1 @check()
+; CHECKFIXME: valid_data.exit:
+; CHECKFIXME-NOT: br
+; CHECKFIXME: %cmp = call zeroext i1 @check()
 ; Outer loop control.
-; CHECK: copy_data.exit:
-; CHECK: br i1 %cmp38, label %if.then39, label %while.cond.outer
+; CHECKFIXME: copy_data.exit:
+; CHECKFIXME: br i1 %cmp38, label %if.then39, label %while.cond.outer
 ; Outer-outer loop tail.
-; CHECK: while.cond.outer.outer.backedge:
-; CHECK: br label %while.cond.outer.outer
+; CHECKFIXME: while.cond.outer.outer.backedge:
+; CHECKFIXME: br label %while.cond.outer.outer
 define void @unloopDeepNested() nounwind {
 for.cond8.preheader.i:
   %cmp113.i = call zeroext i1 @check()