From f690986f314fbf3f4b3ca9ec0b87b95166008dc1 Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Thu, 26 Nov 2020 17:30:44 +0700 Subject: [PATCH] Return "[SCEV] Use isBasicBlockEntryGuardedByCond in isLoopBackedgeGuardedByCond", 2nd try Reverted because the compile time impact is still too high. isKnownViaNonRecursiveReasoning is used twice, we can do it just once. Differential Revision: https://reviews.llvm.org/D92152 --- llvm/lib/Analysis/ScalarEvolution.cpp | 43 +--------------------- .../LoopStrengthReduce/post-inc-icmpzero.ll | 2 +- 2 files changed, 3 insertions(+), 42 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 53fd668..f8c9a23 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -9851,10 +9851,6 @@ ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L, assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()) && "This cannot be done on broken IR!"); - - if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS)) - return true; - BasicBlock *Latch = L->getLoopLatch(); if (!Latch) return false; @@ -9870,7 +9866,7 @@ ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L, // We don't want more than one activation of the following loops on the stack // -- that can lead to O(n!) time complexity. if (WalkingBEDominatingConds) - return false; + return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS); SaveAndRestore ClearOnExit(WalkingBEDominatingConds, true); @@ -9911,42 +9907,7 @@ ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L, if (isImpliedViaGuard(Latch, Pred, LHS, RHS)) return true; - for (DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()]; - DTN != HeaderDTN; DTN = DTN->getIDom()) { - assert(DTN && "should reach the loop header before reaching the root!"); - - BasicBlock *BB = DTN->getBlock(); - if (isImpliedViaGuard(BB, Pred, LHS, RHS)) - return true; - - BasicBlock *PBB = BB->getSinglePredecessor(); - if (!PBB) - continue; - - BranchInst *ContinuePredicate = dyn_cast(PBB->getTerminator()); - if (!ContinuePredicate || !ContinuePredicate->isConditional()) - continue; - - Value *Condition = ContinuePredicate->getCondition(); - - // If we have an edge `E` within the loop body that dominates the only - // latch, the condition guarding `E` also guards the backedge. This - // reasoning works only for loops with a single latch. - - BasicBlockEdge DominatingEdge(PBB, BB); - if (DominatingEdge.isSingleEdge()) { - // We're constructively (and conservatively) enumerating edges within the - // loop body that dominate the latch. The dominator tree better agree - // with us on this: - assert(DT.dominates(DominatingEdge, Latch) && "should be!"); - - if (isImpliedCond(Pred, LHS, RHS, Condition, - BB != ContinuePredicate->getSuccessor(0))) - return true; - } - } - - return false; + return isBasicBlockEntryGuardedByCond(Latch, Pred, LHS, RHS); } bool ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB, diff --git a/llvm/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll b/llvm/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll index 8a07a49..c398289 100644 --- a/llvm/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll +++ b/llvm/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll @@ -69,7 +69,7 @@ define void @_Z15IntegerToStringjjR7Vector2(i32 %i, i32 %radix, %struct.Vector2* ; CHECK-NEXT: [[UGLYGEP2:%.*]] = bitcast i8* [[UGLYGEP]] to i16* ; CHECK-NEXT: [[TMP29:%.*]] = load i16, i16* [[LSR_IV810]], align 2 ; CHECK-NEXT: store i16 [[TMP29]], i16* [[UGLYGEP2]], align 2 -; CHECK-NEXT: [[LSR_IV_NEXT]] = add i64 [[LSR_IV]], 2 +; CHECK-NEXT: [[LSR_IV_NEXT]] = add nuw nsw i64 [[LSR_IV]], 2 ; CHECK-NEXT: [[LSR_IV_NEXT3:%.*]] = inttoptr i64 [[LSR_IV_NEXT]] to i16* ; CHECK-NEXT: [[SCEVGEP9:%.*]] = getelementptr [33 x i16], [33 x i16]* [[LSR_IV8]], i64 0, i64 1 ; CHECK-NEXT: [[TMP3]] = bitcast i16* [[SCEVGEP9]] to [33 x i16]* -- 2.7.4