From c13c09106e0559e20c876c6e76ebb3a094cc5128 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sat, 11 Oct 2014 00:12:11 +0000 Subject: [PATCH] [SCEV] Add some asserts to the recently improved trip count computation routines and fix all of the bugs they expose. I hit a test case that crashed even without these asserts due to passing a non-exiting latch to the ExitingBlock parameter of the trip count computation machinery. However, when I add the nice asserts, it turns out we have plenty of coverage of these bugs, they just didn't manifest in crashers. The core problem seems to stem from an assumption that the latch *is* the exiting block. While this is often true, and somewhat the "normal" way to think about loops, it isn't necessarily true. The correct way to call the trip count routines in a *generic* fashion (that is, without a particular exit in mind) is to just use the loop's single exiting block if it has one. The trip count can't be computed generically unless it does. This works great for the loop vectorizer. The loop unroller actually *wants* to select the latch when it has to chose between multiple exits because for unrolling it is the latch trips that matter. But if this is the desire, it needs to explicitly guard for non-exiting latches and check for the generic trip count in that case. I've added the asserts, and added convenience APIs for querying the trip count generically that check for a single exit block. I've kept the APIs consistent between computing trip count and trip multiples. Thansk to Mark for the help debugging and tracking down the *right* fix here! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@219550 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 15 +++++++++++++++ lib/Analysis/ScalarEvolution.cpp | 22 ++++++++++++++++++++++ lib/Transforms/Scalar/LoopUnrollPass.cpp | 16 +++++++++------- lib/Transforms/Vectorize/LoopVectorize.cpp | 5 ++--- 4 files changed, 48 insertions(+), 10 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 1467ffeecc9..bc31b8e4c3f 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -742,6 +742,13 @@ namespace llvm { bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// \brief Returns the maximum trip count of the loop if it is a single-exit + /// loop and we can compute a small maximum for that loop. + /// + /// Implemented in terms of the \c getSmallConstantTripCount overload with + /// the single exiting block passed to it. See that routine for details. + unsigned getSmallConstantTripCount(Loop *L); + /// getSmallConstantTripCount - Returns the maximum trip count of this loop /// as a normal unsigned value. Returns 0 if the trip count is unknown or /// not constant. This "trip count" assumes that control exits via @@ -751,6 +758,14 @@ namespace llvm { /// the loop exits prematurely via another branch. unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock); + /// \brief Returns the largest constant divisor of the trip count of the + /// loop if it is a single-exit loop and we can compute a small maximum for + /// that loop. + /// + /// Implemented in terms of the \c getSmallConstantTripMultiple overload with + /// the single exiting block passed to it. See that routine for details. + unsigned getSmallConstantTripMultiple(Loop *L); + /// getSmallConstantTripMultiple - Returns the largest constant divisor of /// the trip count of this loop as a normal unsigned value, if /// possible. This means that the actual trip count is always a multiple of diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index e40c2f2447a..b015481b76c 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -4367,6 +4367,14 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // Iteration Count Computation Code // +unsigned ScalarEvolution::getSmallConstantTripCount(Loop *L) { + if (BasicBlock *ExitingBB = L->getExitingBlock()) + return getSmallConstantTripCount(L, ExitingBB); + + // No trip count information for multiple exits. + return 0; +} + /// getSmallConstantTripCount - Returns the maximum trip count of this loop as a /// normal unsigned value. Returns 0 if the trip count is unknown or not /// constant. Will also return 0 if the maximum trip count is very large (>= @@ -4379,6 +4387,9 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { /// prematurely via another branch. unsigned ScalarEvolution::getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock) { + assert(ExitingBlock && "Must pass a non-null exiting block!"); + assert(L->isLoopExiting(ExitingBlock) && + "Exiting block must actually branch out of the loop!"); const SCEVConstant *ExitCount = dyn_cast(getExitCount(L, ExitingBlock)); if (!ExitCount) @@ -4394,6 +4405,14 @@ unsigned ScalarEvolution::getSmallConstantTripCount(Loop *L, return ((unsigned)ExitConst->getZExtValue()) + 1; } +unsigned ScalarEvolution::getSmallConstantTripMultiple(Loop *L) { + if (BasicBlock *ExitingBB = L->getExitingBlock()) + return getSmallConstantTripMultiple(L, ExitingBB); + + // No trip multiple information for multiple exits. + return 0; +} + /// getSmallConstantTripMultiple - Returns the largest constant divisor of the /// trip count of this loop as a normal unsigned value, if possible. This /// means that the actual trip count is always a multiple of the returned @@ -4409,6 +4428,9 @@ unsigned ScalarEvolution::getSmallConstantTripCount(Loop *L, unsigned ScalarEvolution::getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock) { + assert(ExitingBlock && "Must pass a non-null exiting block!"); + assert(L->isLoopExiting(ExitingBlock) && + "Exiting block must actually branch out of the loop!"); const SCEV *ExitCount = getExitCount(L, ExitingBlock); if (ExitCount == getCouldNotCompute()) return 1; diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp index d83816a5a51..f60d9903a55 100644 --- a/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -382,13 +382,15 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { // Find trip count and trip multiple if count is not available unsigned TripCount = 0; unsigned TripMultiple = 1; - // Find "latch trip count". UnrollLoop assumes that control cannot exit - // via the loop latch on any iteration prior to TripCount. The loop may exit - // early via an earlier branch. - BasicBlock *LatchBlock = L->getLoopLatch(); - if (LatchBlock) { - TripCount = SE->getSmallConstantTripCount(L, LatchBlock); - TripMultiple = SE->getSmallConstantTripMultiple(L, LatchBlock); + // If there are multiple exiting blocks but one of them is the latch, use the + // latch for the trip count estimation. Otherwise insist on a single exiting + // block for the trip count estimation. + BasicBlock *ExitingBlock = L->getLoopLatch(); + if (!ExitingBlock || !L->isLoopExiting(ExitingBlock)) + ExitingBlock = L->getExitingBlock(); + if (ExitingBlock) { + TripCount = SE->getSmallConstantTripCount(L, ExitingBlock); + TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock); } // Select an initial unroll count. This may be reduced later based diff --git a/lib/Transforms/Vectorize/LoopVectorize.cpp b/lib/Transforms/Vectorize/LoopVectorize.cpp index 68d4858662e..2004f62a80c 100644 --- a/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -1360,8 +1360,7 @@ struct LoopVectorize : public FunctionPass { // Check the loop for a trip count threshold: // do not vectorize loops with a tiny trip count. - BasicBlock *Latch = L->getLoopLatch(); - const unsigned TC = SE->getSmallConstantTripCount(L, Latch); + const unsigned TC = SE->getSmallConstantTripCount(L); if (TC > 0u && TC < TinyTripCountVectorThreshold) { DEBUG(dbgs() << "LV: Found a loop with a very small trip count. " << "This loop is not worth vectorizing."); @@ -5352,7 +5351,7 @@ LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize) { } // Find the trip count. - unsigned TC = SE->getSmallConstantTripCount(TheLoop, TheLoop->getLoopLatch()); + unsigned TC = SE->getSmallConstantTripCount(TheLoop); DEBUG(dbgs() << "LV: Found trip count: " << TC << '\n'); unsigned WidestType = getWidestType(); -- 2.34.1