Teach getZeroExtendExpr and getSignExtendExpr to use trip-count

information to simplify [sz]ext({a,+,b}) to {zext(a),+,[zs]ext(b)},
as appropriate.

These functions and the trip count code each call into the other, so
this requires careful handling to avoid infinite recursion. During
the initial trip count computation, conservative SCEVs are used,
which are subsequently discarded once the trip count is actually
known.

Among other benefits, this change lets LSR automatically eliminate
some unnecessary zext-inreg and sext-inreg operation where the
operand is an induction variable.


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

1 files changed, 133 insertions, 9 deletions

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index a9521bb..63ad297 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -701,17 +701,81 @@ SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op,
   if (SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
     return getZeroExtendExpr(SZ->getOperand(), Ty);
 
-  // FIXME: If the input value is a chrec scev, and we can prove that the value
+  // If the input value is a chrec scev, and we can prove that the value
   // did not overflow the old, smaller, value, we can zero extend all of the
-  // operands (often constants).  This would allow analysis of something like
+  // operands (often constants).  This allows analysis of something like
   // this:  for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
+  if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
+    if (AR->isAffine()) {
+      // Check whether the backedge-taken count is SCEVCouldNotCompute.
+      // Note that this serves two purposes: It filters out loops that are
+      // simply not analyzable, and it covers the case where this code is
+      // being called from within backedge-taken count analysis, such that
+      // attempting to ask for the backedge-taken count would likely result
+      // in infinite recursion. In the later case, the analysis code will
+      // cope with a conservative value, and it will take care to purge
+      // that value once it has finished.
+      SCEVHandle BECount = getBackedgeTakenCount(AR->getLoop());
+      if (!isa<SCEVCouldNotCompute>(BECount)) {
+        // Compute the extent of AR and divide it by the step value. This is
+        // used to determine if it's safe to extend the stride value.
+        SCEVHandle Start = AR->getStart();
+        SCEVHandle Step = AR->getStepRecurrence(*this);
+
+        // Check whether the backedge-taken count can be losslessly casted to
+        // the addrec's type. The count is always unsigned.
+        SCEVHandle CastedBECount =
+          getTruncateOrZeroExtend(BECount, Start->getType());
+        if (BECount ==
+            getTruncateOrZeroExtend(CastedBECount, BECount->getType())) {
+          const Type *WideTy =
+            IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
+          SCEVHandle ZMul =
+            getMulExpr(CastedBECount,
+                       getTruncateOrZeroExtend(Step, Start->getType()));
+          // Check whether Start+Step*BECount has no unsigned overflow.
+          if (getZeroExtendExpr(ZMul, WideTy) ==
+              getMulExpr(getZeroExtendExpr(CastedBECount, WideTy),
+                         getZeroExtendExpr(Step, WideTy))) {
+            SCEVHandle Add = getAddExpr(Start, ZMul);
+            if (getZeroExtendExpr(Add, WideTy) ==
+                getAddExpr(getZeroExtendExpr(Start, WideTy),
+                           getZeroExtendExpr(ZMul, WideTy)))
+              // Return the expression with the addrec on the outside.
+              return getAddRecExpr(getZeroExtendExpr(Start, Ty),
+                                   getZeroExtendExpr(Step, Ty),
+                                   AR->getLoop());
+          }
+
+          // Similar to above, only this time treat the step value as signed.
+          // This covers loops that count down.
+          SCEVHandle SMul =
+            getMulExpr(CastedBECount,
+                       getTruncateOrSignExtend(Step, Start->getType()));
+          // Check whether Start+Step*BECount has no unsigned overflow.
+          if (getSignExtendExpr(SMul, WideTy) ==
+              getMulExpr(getZeroExtendExpr(CastedBECount, WideTy),
+                         getSignExtendExpr(Step, WideTy))) {
+            SCEVHandle Add = getAddExpr(Start, SMul);
+            if (getZeroExtendExpr(Add, WideTy) ==
+                getAddExpr(getZeroExtendExpr(Start, WideTy),
+                           getSignExtendExpr(SMul, WideTy)))
+              // Return the expression with the addrec on the outside.
+              return getAddRecExpr(getZeroExtendExpr(Start, Ty),
+                                   getSignExtendExpr(Step, Ty),
+                                   AR->getLoop());
+          }
+        }
+      }
+    }
 
   SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)];
   if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
   return Result;
 }
 
-SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type *Ty) {
+SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op,
+                                              const Type *Ty) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
 
@@ -726,10 +790,54 @@ SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type *
   if (SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
     return getSignExtendExpr(SS->getOperand(), Ty);
 
-  // FIXME: If the input value is a chrec scev, and we can prove that the value
+  // If the input value is a chrec scev, and we can prove that the value
   // did not overflow the old, smaller, value, we can sign extend all of the
-  // operands (often constants).  This would allow analysis of something like
+  // operands (often constants).  This allows analysis of something like
   // this:  for (signed char X = 0; X < 100; ++X) { int Y = X; }
+  if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
+    if (AR->isAffine()) {
+      // Check whether the backedge-taken count is SCEVCouldNotCompute.
+      // Note that this serves two purposes: It filters out loops that are
+      // simply not analyzable, and it covers the case where this code is
+      // being called from within backedge-taken count analysis, such that
+      // attempting to ask for the backedge-taken count would likely result
+      // in infinite recursion. In the later case, the analysis code will
+      // cope with a conservative value, and it will take care to purge
+      // that value once it has finished.
+      SCEVHandle BECount = getBackedgeTakenCount(AR->getLoop());
+      if (!isa<SCEVCouldNotCompute>(BECount)) {
+        // Compute the extent of AR and divide it by the step value. This is
+        // used to determine if it's safe to extend the stride value.
+        SCEVHandle Start = AR->getStart();
+        SCEVHandle Step = AR->getStepRecurrence(*this);
+
+        // Check whether the backedge-taken count can be losslessly casted to
+        // the addrec's type. The count is always unsigned.
+        SCEVHandle CastedBECount =
+          getTruncateOrZeroExtend(BECount, Start->getType());
+        if (BECount ==
+            getTruncateOrZeroExtend(CastedBECount, BECount->getType())) {
+          const Type *WideTy =
+            IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
+          SCEVHandle SMul =
+            getMulExpr(CastedBECount,
+                       getTruncateOrSignExtend(Step, Start->getType()));
+          // Check whether Start+Step*BECount has no signed overflow.
+          if (getSignExtendExpr(SMul, WideTy) ==
+              getMulExpr(getSignExtendExpr(CastedBECount, WideTy),
+                         getSignExtendExpr(Step, WideTy))) {
+            SCEVHandle Add = getAddExpr(Start, SMul);
+            if (getSignExtendExpr(Add, WideTy) ==
+                getAddExpr(getSignExtendExpr(Start, WideTy),
+                           getSignExtendExpr(SMul, WideTy)))
+              // Return the expression with the addrec on the outside.
+              return getAddRecExpr(getSignExtendExpr(Start, Ty),
+                                   getSignExtendExpr(Step, Ty),
+                                   AR->getLoop());
+          }
+        }
+      }
+    }
 
   SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)];
   if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
@@ -1962,20 +2070,36 @@ SCEVHandle ScalarEvolution::createSCEV(Value *V) {
 /// hasLoopInvariantBackedgeTakenCount).
 ///
 SCEVHandle ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
-  std::map<const Loop*, SCEVHandle>::iterator I = BackedgeTakenCounts.find(L);
-  if (I == BackedgeTakenCounts.end()) {
+  // Initially insert a CouldNotCompute for this loop. If the insertion
+  // succeeds, procede to actually compute a backedge-taken count and
+  // update the value. The temporary CouldNotCompute value tells SCEV
+  // code elsewhere that it shouldn't attempt to request a new
+  // backedge-taken count, which could result in infinite recursion.
+  std::pair<std::map<const Loop*, SCEVHandle>::iterator, bool> Pair =
+    BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
+  if (Pair.second) {
     SCEVHandle ItCount = ComputeBackedgeTakenCount(L);
-    I = BackedgeTakenCounts.insert(std::make_pair(L, ItCount)).first;
     if (ItCount != UnknownValue) {
       assert(ItCount->isLoopInvariant(L) &&
              "Computed trip count isn't loop invariant for loop!");
       ++NumTripCountsComputed;
+
+      // Now that we know the trip count for this loop, forget any
+      // existing SCEV values for PHI nodes in this loop since they
+      // are only conservative estimates made without the benefit
+      // of trip count information.
+      for (BasicBlock::iterator I = L->getHeader()->begin();
+           PHINode *PN = dyn_cast<PHINode>(I); ++I)
+        deleteValueFromRecords(PN);
+
+      // Update the value in the map.
+      Pair.first->second = ItCount;
     } else if (isa<PHINode>(L->getHeader()->begin())) {
       // Only count loops that have phi nodes as not being computable.
       ++NumTripCountsNotComputed;
     }
   }
-  return I->second;
+  return Pair.first->second;
 }
 
 /// forgetLoopBackedgeTakenCount - This method should be called by the