Merge the implementations of isLoopInvariant and hasComputableLoopEvolution, and

memoize the results. This improves compile time in code which highly complex
expressions which get queried many times.

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

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 750a090fe786962b16f3c2c239970978408ee6bd..26eceba81523d96e04ba9cc9379e264ca5911f5a 100644 (file)
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -142,6 +142,16 @@ namespace llvm {
   /// they must ask this class for services.
   ///
   class ScalarEvolution : public FunctionPass {
   /// they must ask this class for services.
   ///
   class ScalarEvolution : public FunctionPass {

+  public:
+    /// LoopDisposition - An enum describing the relationship between a
+    /// SCEV and a loop.
+    enum LoopDisposition {
+      LoopVariant,    ///< The SCEV is loop-variant (unknown).
+      LoopInvariant,  ///< The SCEV is loop-invariant.
+      LoopComputable  ///< The SCEV varies predictably with the loop.
+    };
+
+  private:

     /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be
     /// notified whenever a Value is deleted.
     class SCEVCallbackVH : public CallbackVH {
     /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be
     /// notified whenever a Value is deleted.
     class SCEVCallbackVH : public CallbackVH {


@@ -229,6 +239,13 @@ namespace llvm {
     std::map<const SCEV *,
              std::map<const Loop *, const SCEV *> > ValuesAtScopes;
 
     std::map<const SCEV *,
              std::map<const Loop *, const SCEV *> > ValuesAtScopes;
 

+    /// LoopDispositions - Memoized computeLoopDisposition results.
+    std::map<const SCEV *,
+             std::map<const Loop *, LoopDisposition> > LoopDispositions;
+
+    /// computeLoopDisposition - Compute a LoopDisposition value.
+    LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
+

     /// UnsignedRanges - Memoized results from getUnsignedRange
     DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
 
     /// UnsignedRanges - Memoized results from getUnsignedRange
     DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
 


@@ -663,6 +680,10 @@ namespace llvm {
                               const SCEV *&LHS,
                               const SCEV *&RHS);
 
                               const SCEV *&LHS,
                               const SCEV *&RHS);
 

+    /// getLoopDisposition - Return the "disposition" of the given SCEV with
+    /// respect to the given loop.
+    LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
+

     /// isLoopInvariant - Return true if the value of the given SCEV is
     /// unchanging in the specified loop.
     bool isLoopInvariant(const SCEV *S, const Loop *L);
     /// isLoopInvariant - Return true if the value of the given SCEV is
     /// unchanging in the specified loop.
     bool isLoopInvariant(const SCEV *S, const Loop *L);

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 99ab84dc0c200b57f35dc1a8b9e02ad2b3389b32..b734d00f7fe05587d601154ceb97c78fb384b9e3 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -326,6 +326,7 @@ SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
 void SCEVUnknown::deleted() {
   // Clear this SCEVUnknown from various maps.
   SE->ValuesAtScopes.erase(this);
 void SCEVUnknown::deleted() {
   // Clear this SCEVUnknown from various maps.
   SE->ValuesAtScopes.erase(this);

+  SE->LoopDispositions.erase(this);

   SE->UnsignedRanges.erase(this);
   SE->SignedRanges.erase(this);
 
   SE->UnsignedRanges.erase(this);
   SE->SignedRanges.erase(this);
 


@@ -339,6 +340,7 @@ void SCEVUnknown::deleted() {
 void SCEVUnknown::allUsesReplacedWith(Value *New) {
   // Clear this SCEVUnknown from various maps.
   SE->ValuesAtScopes.erase(this);
 void SCEVUnknown::allUsesReplacedWith(Value *New) {
   // Clear this SCEVUnknown from various maps.
   SE->ValuesAtScopes.erase(this);

+  SE->LoopDispositions.erase(this);

   SE->UnsignedRanges.erase(this);
   SE->SignedRanges.erase(this);
 
   SE->UnsignedRanges.erase(this);
   SE->SignedRanges.erase(this);
 


@@ -2635,6 +2637,7 @@ ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) {
           !isa<SCEVUnknown>(Old) ||
           (I != PN && Old == SymName)) {
         ValuesAtScopes.erase(Old);
           !isa<SCEVUnknown>(Old) ||
           (I != PN && Old == SymName)) {
         ValuesAtScopes.erase(Old);

+        LoopDispositions.erase(Old);

         UnsignedRanges.erase(Old);
         SignedRanges.erase(Old);
         ValueExprMap.erase(It);
         UnsignedRanges.erase(Old);
         SignedRanges.erase(Old);
         ValueExprMap.erase(It);


@@ -3675,6 +3678,7 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
           // own when it gets to that point.
           if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
             ValuesAtScopes.erase(Old);
           // own when it gets to that point.
           if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
             ValuesAtScopes.erase(Old);

+            LoopDispositions.erase(Old);

             UnsignedRanges.erase(Old);
             SignedRanges.erase(Old);
             ValueExprMap.erase(It);
             UnsignedRanges.erase(Old);
             SignedRanges.erase(Old);
             ValueExprMap.erase(It);


@@ -3710,6 +3714,7 @@ void ScalarEvolution::forgetLoop(const Loop *L) {
     if (It != ValueExprMap.end()) {
       const SCEV *Old = It->second;
       ValuesAtScopes.erase(Old);
     if (It != ValueExprMap.end()) {
       const SCEV *Old = It->second;
       ValuesAtScopes.erase(Old);

+      LoopDispositions.erase(Old);

       UnsignedRanges.erase(Old);
       SignedRanges.erase(Old);
       ValueExprMap.erase(It);
       UnsignedRanges.erase(Old);
       SignedRanges.erase(Old);
       ValueExprMap.erase(It);


@@ -3746,6 +3751,7 @@ void ScalarEvolution::forgetValue(Value *V) {
     if (It != ValueExprMap.end()) {
       const SCEV *Old = It->second;
       ValuesAtScopes.erase(Old);
     if (It != ValueExprMap.end()) {
       const SCEV *Old = It->second;
       ValuesAtScopes.erase(Old);

+      LoopDispositions.erase(Old);

       UnsignedRanges.erase(Old);
       SignedRanges.erase(Old);
       ValueExprMap.erase(It);
       UnsignedRanges.erase(Old);
       SignedRanges.erase(Old);
       ValueExprMap.erase(It);


@@ -5803,6 +5809,7 @@ void ScalarEvolution::releaseMemory() {
   BackedgeTakenCounts.clear();
   ConstantEvolutionLoopExitValue.clear();
   ValuesAtScopes.clear();
   BackedgeTakenCounts.clear();
   ConstantEvolutionLoopExitValue.clear();
   ValuesAtScopes.clear();

+  LoopDispositions.clear();

   UnsignedRanges.clear();
   SignedRanges.clear();
   UniqueSCEVs.clear();
   UnsignedRanges.clear();
   SignedRanges.clear();
   UniqueSCEVs.clear();


@@ -5901,54 +5908,82 @@ void ScalarEvolution::print(raw_ostream &OS, const Module *) const {
     PrintLoopInfo(OS, &SE, *I);
 }
 
     PrintLoopInfo(OS, &SE, *I);
 }
 

-bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
+ScalarEvolution::LoopDisposition
+ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
+  std::map<const Loop *, LoopDisposition> &Values = LoopDispositions[S];
+  std::pair<std::map<const Loop *, LoopDisposition>::iterator, bool> Pair =
+    Values.insert(std::make_pair(L, LoopVariant));
+  if (!Pair.second)
+    return Pair.first->second;
+
+  LoopDisposition D = computeLoopDisposition(S, L);
+  return LoopDispositions[S][L] = D;
+}
+
+ScalarEvolution::LoopDisposition
+ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) {

   switch (S->getSCEVType()) {
   case scConstant:
   switch (S->getSCEVType()) {
   case scConstant:

-    return true;
+    return LoopInvariant;

   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:

-    return isLoopInvariant(cast<SCEVCastExpr>(S)->getOperand(), L);
+    return getLoopDisposition(cast<SCEVCastExpr>(S)->getOperand(), L);

   case scAddRecExpr: {
     const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
 
   case scAddRecExpr: {
     const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
 

+    // If L is the addrec's loop, it's computable.
+    if (AR->getLoop() == L)
+      return LoopComputable;
+

     // Add recurrences are never invariant in the function-body (null loop).
     if (!L)
     // Add recurrences are never invariant in the function-body (null loop).
     if (!L)

-      return false;
+      return LoopVariant;

 
     // This recurrence is variant w.r.t. L if L contains AR's loop.
     if (L->contains(AR->getLoop()))
 
     // This recurrence is variant w.r.t. L if L contains AR's loop.
     if (L->contains(AR->getLoop()))

-      return false;
+      return LoopVariant;

 
     // This recurrence is invariant w.r.t. L if AR's loop contains L.
     if (AR->getLoop()->contains(L))
 
     // This recurrence is invariant w.r.t. L if AR's loop contains L.
     if (AR->getLoop()->contains(L))

-      return true;
+      return LoopInvariant;

 
     // This recurrence is variant w.r.t. L if any of its operands
     // are variant.
     for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end();
          I != E; ++I)
       if (!isLoopInvariant(*I, L))
 
     // This recurrence is variant w.r.t. L if any of its operands
     // are variant.
     for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end();
          I != E; ++I)
       if (!isLoopInvariant(*I, L))

-        return false;
+        return LoopVariant;

 
     // Otherwise it's loop-invariant.
 
     // Otherwise it's loop-invariant.

-    return true;
+    return LoopInvariant;

   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr: {
     const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr: {
     const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);

+    bool HasVarying = false;

     for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
     for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();

-         I != E; ++I)
-      if (!isLoopInvariant(*I, L))
-        return false;
-    return true;
+         I != E; ++I) {
+      LoopDisposition D = getLoopDisposition(*I, L);
+      if (D == LoopVariant)
+        return LoopVariant;
+      if (D == LoopComputable)
+        HasVarying = true;
+    }
+    return HasVarying ? LoopComputable : LoopInvariant;

   }
   case scUDivExpr: {
     const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
   }
   case scUDivExpr: {
     const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);

-    return isLoopInvariant(UDiv->getLHS(), L) &&
-           isLoopInvariant(UDiv->getRHS(), L);
+    LoopDisposition LD = getLoopDisposition(UDiv->getLHS(), L);
+    if (LD == LoopVariant)
+      return LoopVariant;
+    LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L);
+    if (RD == LoopVariant)
+      return LoopVariant;
+    return (LD == LoopInvariant && RD == LoopInvariant) ?
+           LoopInvariant : LoopComputable;

   }
   case scUnknown:
     // All non-instruction values are loop invariant.  All instructions are loop
   }
   case scUnknown:
     // All non-instruction values are loop invariant.  All instructions are loop


@@ -5956,71 +5991,23 @@ bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
     // Instructions are never considered invariant in the function body
     // (null loop) because they are defined within the "loop".
     if (Instruction *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
     // Instructions are never considered invariant in the function body
     // (null loop) because they are defined within the "loop".
     if (Instruction *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))

-      return L && !L->contains(I);
-    return true;
+      return (L && !L->contains(I)) ? LoopInvariant : LoopVariant;
+    return LoopInvariant;

   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");

-    return false;
+    return LoopVariant;

   default: break;
   }
   llvm_unreachable("Unknown SCEV kind!");
   default: break;
   }
   llvm_unreachable("Unknown SCEV kind!");

-  return false;
+  return LoopVariant;
+}
+
+bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
+  return getLoopDisposition(S, L) == LoopInvariant;

 }
 
 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) {
 }
 
 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) {

-  switch (S->getSCEVType()) {
-  case scConstant:
-    return false;
-  case scTruncate:
-  case scZeroExtend:
-  case scSignExtend:
-    return hasComputableLoopEvolution(cast<SCEVCastExpr>(S)->getOperand(), L);
-  case scAddRecExpr:
-    return cast<SCEVAddRecExpr>(S)->getLoop() == L;
-  case scAddExpr:
-  case scMulExpr:
-  case scUMaxExpr:
-  case scSMaxExpr: {
-    const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
-    bool HasVarying = false;
-    for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
-         I != E; ++I) {
-      const SCEV *Op = *I;
-      if (!isLoopInvariant(Op, L)) {
-        if (hasComputableLoopEvolution(Op, L))
-          HasVarying = true;
-        else
-          return false;
-      }
-    }
-    return HasVarying;
-  }
-  case scUDivExpr: {
-    const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
-    bool HasVarying = false;
-    if (!isLoopInvariant(UDiv->getLHS(), L)) {
-      if (hasComputableLoopEvolution(UDiv->getLHS(), L))
-        HasVarying = true;
-      else
-        return false;
-    }
-    if (!isLoopInvariant(UDiv->getRHS(), L)) {
-      if (hasComputableLoopEvolution(UDiv->getRHS(), L))
-        HasVarying = true;
-      else
-        return false;
-    }
-    return HasVarying;
-  }
-  case scUnknown:
-    return false;
-  case scCouldNotCompute:
-    llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
-    return false;
-  default: break;
-  }
-  llvm_unreachable("Unknown SCEV kind!");
-  return false;
+  return getLoopDisposition(S, L) == LoopComputable;

 }
 
 bool ScalarEvolution::dominates(const SCEV *S, BasicBlock *BB) const {
 }
 
 bool ScalarEvolution::dominates(const SCEV *S, BasicBlock *BB) const {