[LoopUnroll] Peel off iterations if it makes conditions true/false.
If the loop body contains conditions of the form IndVar < #constant, we
can remove the checks by peeling off #constant iterations.
This improves codegen for PR34364.
Reviewers: mkuper, mkazantsev, efriedma
Reviewed By: mkazantsev
Differential Revision: https://reviews.llvm.org/D43876
llvm-svn: 327671
diff --git a/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp b/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
index 68d86d9..093f340 100644
--- a/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
@@ -795,7 +795,7 @@
}
// 4th priority is loop peeling
- computePeelCount(L, LoopSize, UP, TripCount);
+ computePeelCount(L, LoopSize, UP, TripCount, SE);
if (UP.PeelCount) {
UP.Runtime = false;
UP.Count = 1;
diff --git a/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp b/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
index 1374930..d4d78bf 100644
--- a/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
@@ -20,6 +20,7 @@
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
@@ -30,6 +31,7 @@
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
+#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
@@ -46,6 +48,7 @@
#include <limits>
using namespace llvm;
+using namespace llvm::PatternMatch;
#define DEBUG_TYPE "loop-unroll"
@@ -136,10 +139,87 @@
return ToInvariance;
}
+// Return the number of iterations to peel off that make conditions in the
+// body true/false. For example, if we peel 2 iterations off the loop below,
+// the condition i < 2 can be evaluated at compile time.
+// for (i = 0; i < n; i++)
+// if (i < 2)
+// ..
+// else
+// ..
+// }
+static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount,
+ ScalarEvolution &SE) {
+ assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form");
+ unsigned DesiredPeelCount = 0;
+
+ for (auto *BB : L.blocks()) {
+ auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
+ if (!BI || BI->isUnconditional())
+ continue;
+
+ // Ignore loop exit condition.
+ if (L.getLoopLatch() == BB)
+ continue;
+
+ Value *Condition = BI->getCondition();
+ Value *LeftVal, *RightVal;
+ CmpInst::Predicate Pred;
+ if (!match(Condition, m_ICmp(Pred, m_Value(LeftVal), m_Value(RightVal))))
+ continue;
+
+ const SCEV *LeftSCEV = SE.getSCEV(LeftVal);
+ const SCEV *RightSCEV = SE.getSCEV(RightVal);
+
+ // Do not consider predicates that are known to be true or false
+ // independently of the loop iteration.
+ if (SE.isKnownPredicate(Pred, LeftSCEV, RightSCEV) ||
+ SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), LeftSCEV,
+ RightSCEV))
+ continue;
+
+ // Check if we have a condition with one AddRec and one non AddRec
+ // expression. Normalize LeftSCEV to be the AddRec.
+ if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
+ if (isa<SCEVAddRecExpr>(RightSCEV)) {
+ std::swap(LeftSCEV, RightSCEV);
+ Pred = ICmpInst::getSwappedPredicate(Pred);
+ } else
+ continue;
+ }
+
+ const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(LeftSCEV);
+
+ // Avoid huge SCEV computations in the loop below and make sure we only
+ // consider AddRecs of the loop we are trying to peel.
+ if (!LeftAR->isAffine() || LeftAR->getLoop() != &L)
+ continue;
+
+ // Check if extending DesiredPeelCount lets us evaluate Pred.
+ const SCEV *IterVal = LeftAR->evaluateAtIteration(
+ SE.getConstant(LeftSCEV->getType(), DesiredPeelCount), SE);
+
+ // If the original condition is not known, get the negated predicate
+ // (which holds on the else branch) and check if it is known. This allows
+ // us to peel of iterations that make the original condition false.
+ if (!SE.isKnownPredicate(Pred, IterVal, RightSCEV))
+ Pred = ICmpInst::getInversePredicate(Pred);
+
+ const SCEV *Step = LeftAR->getStepRecurrence(SE);
+ while (DesiredPeelCount < MaxPeelCount &&
+ SE.isKnownPredicate(Pred, IterVal, RightSCEV)) {
+ IterVal = SE.getAddExpr(IterVal, Step);
+ DesiredPeelCount++;
+ }
+ }
+
+ return DesiredPeelCount;
+}
+
// Return the number of iterations we want to peel off.
void llvm::computePeelCount(Loop *L, unsigned LoopSize,
TargetTransformInfo::UnrollingPreferences &UP,
- unsigned &TripCount) {
+ unsigned &TripCount, ScalarEvolution &SE) {
assert(LoopSize > 0 && "Zero loop size is not allowed!");
UP.PeelCount = 0;
if (!canPeel(L))
@@ -170,10 +250,15 @@
if (ToInvariance != InfiniteIterationsToInvariance)
DesiredPeelCount = std::max(DesiredPeelCount, ToInvariance);
}
+
+ // Pay respect to limitations implied by loop size and the max peel count.
+ unsigned MaxPeelCount = UnrollPeelMaxCount;
+ MaxPeelCount = std::min(MaxPeelCount, UP.Threshold / LoopSize - 1);
+
+ DesiredPeelCount = std::max(DesiredPeelCount,
+ countToEliminateCompares(*L, MaxPeelCount, SE));
+
if (DesiredPeelCount > 0) {
- // Pay respect to limitations implied by loop size and the max peel count.
- unsigned MaxPeelCount = UnrollPeelMaxCount;
- MaxPeelCount = std::min(MaxPeelCount, UP.Threshold / LoopSize - 1);
DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);
// Consider max peel count limitation.
assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");