Use code-size reduction metrics to estimate the amount of savings we'll get when we unroll a loop.

Next step is to recalculate the threshold values given this new heuristic.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113525 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 24 insertions, 1 deletions

diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp
index f0a661cb69..967ce93a24 100644
--- a/lib/Transforms/Scalar/LoopUnrollPass.cpp
+++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp
@@ -90,7 +90,30 @@ static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls) {
        I != E; ++I)
     Metrics.analyzeBasicBlock(*I);
   NumCalls = Metrics.NumCalls;
-  return Metrics.NumInsts;
+  
+  unsigned LoopSize = Metrics.NumInsts;
+  
+  // If we can identify the induction variable, we know that it will become
+  // constant when we unroll the loop, so factor that into our loop size 
+  // estimate.
+  // FIXME: We have to divide by InlineConstants::InstrCost because the
+  // measure returned by CountCodeReductionForConstant is not an instruction
+  // count, but rather a weight as defined by InlineConstants.  It would 
+  // probably be a good idea to standardize on a single weighting scheme by
+  // pushing more of the logic for weighting into CodeMetrics.
+  if (PHINode *IndVar = L->getCanonicalInductionVariable()) {
+    unsigned SizeDecrease = Metrics.CountCodeReductionForConstant(IndVar);
+    // NOTE: Because SizeDecrease is a fuzzy estimate, we don't want to allow
+    // it to totally negate the cost of unrolling a loop.
+    SizeDecrease = SizeDecrease > LoopSize / 2 ? LoopSize : SizeDecrease;
+  }
+  
+  // 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;
 }
 
 bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) {