From ba03377fa171d2340bfff2ec817e62ec09eab992 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Sat, 23 Jul 2011 00:29:16 +0000 Subject: whitespace git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135828 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnrollPass.cpp | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'lib/Transforms/Scalar/LoopUnrollPass.cpp') diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp index fef6bc3..38259f0 100644 --- a/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -49,7 +49,7 @@ namespace { CurrentAllowPartial = (P == -1) ? UnrollAllowPartial : (bool)P; UserThreshold = (T != -1) || (UnrollThreshold.getNumOccurrences() > 0); - + initializeLoopUnrollPass(*PassRegistry::getPassRegistry()); } @@ -57,11 +57,11 @@ namespace { /// that the loop unroll should be performed regardless of how much /// code expansion would result. static const unsigned NoThreshold = UINT_MAX; - + // Threshold to use when optsize is specified (and there is no // explicit -unroll-threshold). static const unsigned OptSizeUnrollThreshold = 50; - + unsigned CurrentCount; unsigned CurrentThreshold; bool CurrentAllowPartial; @@ -107,14 +107,14 @@ static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls) { I != E; ++I) Metrics.analyzeBasicBlock(*I); NumCalls = Metrics.NumInlineCandidates; - + unsigned LoopSize = Metrics.NumInsts; - + // Don't allow an estimate of size zero. This would allows unrolling of loops // with huge iteration counts, which is a compile time problem even if it's // not a problem for code quality. if (LoopSize == 0) LoopSize = 1; - + return LoopSize; } @@ -125,13 +125,13 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { DEBUG(dbgs() << "Loop Unroll: F[" << Header->getParent()->getName() << "] Loop %" << Header->getName() << "\n"); (void)Header; - + // Determine the current unrolling threshold. While this is normally set // from UnrollThreshold, it is overridden to a smaller value if the current // function is marked as optimize-for-size, and the unroll threshold was // not user specified. unsigned Threshold = CurrentThreshold; - if (!UserThreshold && + if (!UserThreshold && Header->getParent()->hasFnAttr(Attribute::OptimizeForSize)) Threshold = OptSizeUnrollThreshold; -- cgit v1.1 From 2045ce154a69b8f251d3a5259324528f0def337b Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Sat, 23 Jul 2011 00:33:05 +0000 Subject: Move trip count discovery outside of the generic LoopUnroll helper. This removes its dependence on canonical induction variables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135829 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnrollPass.cpp | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'lib/Transforms/Scalar/LoopUnrollPass.cpp') diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp index 38259f0..6d7901f 100644 --- a/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -137,9 +137,14 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { // Find trip count unsigned TripCount = L->getSmallConstantTripCount(); - unsigned Count = CurrentCount; + + // Find trip multiple if count is not available + unsigned TripMultiple = 1; + if (TripCount == 0) + TripMultiple = L->getSmallConstantTripMultiple(); // Automatically select an unroll count. + unsigned Count = CurrentCount; if (Count == 0) { // Conservative heuristic: if we know the trip count, see if we can // completely unroll (subject to the threshold, checked below); otherwise @@ -183,7 +188,7 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { // Unroll the loop. Function *F = L->getHeader()->getParent(); - if (!UnrollLoop(L, Count, LI, &LPM)) + if (!UnrollLoop(L, Count, TripCount, TripMultiple, LI, &LPM)) return false; // FIXME: Reconstruct dom info, because it is not preserved properly. -- cgit v1.1 From 39f40299a6efc06747db0de53deb9be248913998 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Wed, 10 Aug 2011 04:29:49 +0000 Subject: Invoke SimplifyIndVar when we partially unroll a loop. Fixes PR10534. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137203 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnrollPass.cpp | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'lib/Transforms/Scalar/LoopUnrollPass.cpp') diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp index 6d7901f..94afff6 100644 --- a/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -79,6 +79,7 @@ namespace { AU.addPreservedID(LoopSimplifyID); AU.addRequiredID(LCSSAID); AU.addPreservedID(LCSSAID); + AU.addRequired(); AU.addPreserved(); // FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info. // If loop unroll does not preserve dom info then LCSSA pass on next @@ -187,12 +188,8 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { } // Unroll the loop. - Function *F = L->getHeader()->getParent(); if (!UnrollLoop(L, Count, TripCount, TripMultiple, LI, &LPM)) return false; - // FIXME: Reconstruct dom info, because it is not preserved properly. - if (DominatorTree *DT = getAnalysisIfAvailable()) - DT->runOnFunction(*F); return true; } -- cgit v1.1 From b1831c66403315a1d84593b7c198ddbd43a574cf Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Thu, 11 Aug 2011 23:36:16 +0000 Subject: Allow loop unrolling to get known trip counts from ScalarEvolution. SCEV unrolling can unroll loops with arbitrary induction variables. It is a prerequisite for -disable-iv-rewrite performance. It is also easily handles loops of arbitrary structure including multiple exits and is generally more robust. This is under a temporary option to avoid affecting default behavior for the next couple of weeks. It is needed so that I can checkin unit tests for updateUnloop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137384 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnrollPass.cpp | 30 +++++++++++++++++++++++------- 1 file changed, 23 insertions(+), 7 deletions(-) (limited to 'lib/Transforms/Scalar/LoopUnrollPass.cpp') diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp index 94afff6..dab3ac4 100644 --- a/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -39,6 +39,11 @@ UnrollAllowPartial("unroll-allow-partial", cl::init(false), cl::Hidden, cl::desc("Allows loops to be partially unrolled until " "-unroll-threshold loop size is reached.")); +// Temporary flag to be made default shortly. +static cl::opt +UnrollWithSCEV("unroll-scev", cl::init(false), cl::Hidden, + cl::desc("Use ScalarEvolution to analyze loop trip counts for unrolling")); + namespace { class LoopUnroll : public LoopPass { public: @@ -121,6 +126,7 @@ static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls) { bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { LoopInfo *LI = &getAnalysis(); + ScalarEvolution *SE = &getAnalysis(); BasicBlock *Header = L->getHeader(); DEBUG(dbgs() << "Loop Unroll: F[" << Header->getParent()->getName() @@ -136,14 +142,24 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { Header->getParent()->hasFnAttr(Attribute::OptimizeForSize)) Threshold = OptSizeUnrollThreshold; - // Find trip count - unsigned TripCount = L->getSmallConstantTripCount(); - - // Find trip multiple if count is not available + // Find trip count and trip multiple if count is not available + unsigned TripCount = 0; unsigned TripMultiple = 1; - if (TripCount == 0) - TripMultiple = L->getSmallConstantTripMultiple(); - + if (UnrollWithSCEV) { + // 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); + } + } + else { + TripCount = L->getSmallConstantTripCount(); + if (TripCount == 0) + TripMultiple = L->getSmallConstantTripMultiple(); + } // Automatically select an unroll count. unsigned Count = CurrentCount; if (Count == 0) { -- cgit v1.1 From 12d1ebe9435437a04577ea550eb679ae54698554 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Fri, 2 Sep 2011 17:26:28 +0000 Subject: Enable SCEV-based unrolling by default. This changes loop unrolling to use the same mechanism for trip count computation as indvars. This is a stronger check that tends to unroll more loops. A very common side-effect is that many single iteration loops will be removed sooner. The real goal was simply to remove dependence on canonical IVs. x86 is break even. ARM performance changes to expect (+ is good): External/SPEC/CFP2000/183.equake/183.equake +13% SingleSource/Benchmarks/Dhrystone/fldry +21% MultiSource/Applications/spiff/spiff +3% SingleSource/Benchmarks/Stanford/Puzzle -14% The Puzzle regression is actually an improvement in loop optimization that defeats GVN: rdar://problem/10065079. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139009 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnrollPass.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib/Transforms/Scalar/LoopUnrollPass.cpp') diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp index dab3ac4..cca7ba0 100644 --- a/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -39,9 +39,9 @@ UnrollAllowPartial("unroll-allow-partial", cl::init(false), cl::Hidden, cl::desc("Allows loops to be partially unrolled until " "-unroll-threshold loop size is reached.")); -// Temporary flag to be made default shortly. +// Temporary flag to be removed in 3.0 static cl::opt -UnrollWithSCEV("unroll-scev", cl::init(false), cl::Hidden, +NoSCEVUnroll("disable-unroll-scev", cl::init(false), cl::Hidden, cl::desc("Use ScalarEvolution to analyze loop trip counts for unrolling")); namespace { @@ -145,7 +145,7 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { // Find trip count and trip multiple if count is not available unsigned TripCount = 0; unsigned TripMultiple = 1; - if (UnrollWithSCEV) { + if (!NoSCEVUnroll) { // 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. -- cgit v1.1 From b2ab2fa524f3f90376639037bd81924483cca0af Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Sat, 1 Oct 2011 01:39:05 +0000 Subject: Inlining and unrolling heuristics should be aware of free truncs. We want heuristics to be based on accurate data, but more importantly we don't want llvm to behave randomly. A benign trunc inserted by an upstream pass should not cause a wild swings in optimization level. See PR11034. It's a general problem with threshold-based heuristics, but we can make it less bad. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140919 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnrollPass.cpp | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'lib/Transforms/Scalar/LoopUnrollPass.cpp') diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp index cca7ba0..91395b2 100644 --- a/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -22,6 +22,7 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/UnrollLoop.h" +#include "llvm/Target/TargetData.h" #include using namespace llvm; @@ -107,11 +108,12 @@ Pass *llvm::createLoopUnrollPass(int Threshold, int Count, int AllowPartial) { } /// ApproximateLoopSize - Approximate the size of the loop. -static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls) { +static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls, + const TargetData *TD) { CodeMetrics Metrics; for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E; ++I) - Metrics.analyzeBasicBlock(*I); + Metrics.analyzeBasicBlock(*I, TD); NumCalls = Metrics.NumInlineCandidates; unsigned LoopSize = Metrics.NumInsts; @@ -174,8 +176,9 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { // Enforce the threshold. if (Threshold != NoThreshold) { + const TargetData *TD = getAnalysisIfAvailable(); unsigned NumInlineCandidates; - unsigned LoopSize = ApproximateLoopSize(L, NumInlineCandidates); + unsigned LoopSize = ApproximateLoopSize(L, NumInlineCandidates, TD); DEBUG(dbgs() << " Loop Size = " << LoopSize << "\n"); if (NumInlineCandidates != 0) { DEBUG(dbgs() << " Not unrolling loop with inlinable calls.\n"); -- cgit v1.1