diff options
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 19 | ||||
| -rw-r--r-- | test/Transforms/LoopUnroll/scevunroll.ll | 50 | ||||
| -rw-r--r-- | test/Transforms/LoopUnroll/unloop.ll | 34 |
3 files changed, 76 insertions, 27 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index d26ec9a25d..f876748af3 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -3937,10 +3937,19 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { /// before taking the branch. For loops with multiple exits, it may not be the /// number times that the loop header executes because the loop may exit /// prematurely via another branch. +/// +/// FIXME: We conservatively call getBackedgeTakenCount(L) instead of +/// getExitCount(L, ExitingBlock) to compute a safe trip count considering all +/// loop exits. getExitCount() may return an exact count for this branch +/// assuming no-signed-wrap. The number of well-defined iterations may actually +/// be higher than this trip count if this exit test is skipped and the loop +/// exits via a different branch. Ideally, getExitCount() would know whether it +/// depends on a NSW assumption, and we would only fall back to a conservative +/// trip count in that case. unsigned ScalarEvolution:: -getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock) { +getSmallConstantTripCount(Loop *L, BasicBlock */*ExitingBlock*/) { const SCEVConstant *ExitCount = - dyn_cast<SCEVConstant>(getExitCount(L, ExitingBlock)); + dyn_cast<SCEVConstant>(getBackedgeTakenCount(L)); if (!ExitCount) return 0; @@ -3967,8 +3976,8 @@ getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock) { /// As explained in the comments for getSmallConstantTripCount, this assumes /// that control exits the loop via ExitingBlock. unsigned ScalarEvolution:: -getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock) { - const SCEV *ExitCount = getExitCount(L, ExitingBlock); +getSmallConstantTripMultiple(Loop *L, BasicBlock */*ExitingBlock*/) { + const SCEV *ExitCount = getBackedgeTakenCount(L); if (ExitCount == getCouldNotCompute()) return 1; @@ -3997,7 +4006,7 @@ getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock) { } // getExitCount - Get the expression for the number of loop iterations for which -// this loop is guaranteed not to exit via ExitintBlock. Otherwise return +// this loop is guaranteed not to exit via ExitingBlock. Otherwise return // SCEVCouldNotCompute. const SCEV *ScalarEvolution::getExitCount(Loop *L, BasicBlock *ExitingBlock) { return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); diff --git a/test/Transforms/LoopUnroll/scevunroll.ll b/test/Transforms/LoopUnroll/scevunroll.ll index 99b3a7d861..308a036316 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 5a9cacda44..9a938cc287 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() |