Fix a huge performance problem in reassociate by introducing a

rank map cache for instruction ranks

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

diff --git a/lib/Transforms/Scalar/Reassociate.cpp b/lib/Transforms/Scalar/Reassociate.cpp
index 63fe33f33eb5d987f16fe89e715ebaa6377169ac..4212e6ae69f83e322d4cc54ad2a7c1fa9734fb6f 100644 (file)
--- a/lib/Transforms/Scalar/Reassociate.cpp
+++ b/lib/Transforms/Scalar/Reassociate.cpp
@@ -36,6 +36,7 @@ namespace {
 
   class Reassociate : public FunctionPass {
     std::map<BasicBlock*, unsigned> RankMap;
+    std::map<Instruction*, unsigned> InstRankMap;
   public:
     bool runOnFunction(Function &F);
 
@@ -76,12 +77,16 @@ unsigned Reassociate::getRank(Value *V) {
         I->hasSideEffects())
       return RankMap[I->getParent()];
 
+    unsigned &CachedRank = InstRankMap[I];
+    if (CachedRank) return CachedRank;    // Rank already known?
+
+    // If not, compute it!
     unsigned Rank = 0, MaxRank = RankMap[I->getParent()];
     for (unsigned i = 0, e = I->getNumOperands();
          i != e && Rank != MaxRank; ++i)
       Rank = std::max(Rank, getRank(I->getOperand(i)));
 
-    return Rank;
+    return CachedRank = Rank;
   }
 
   // Otherwise it's a global or constant, rank 0.
@@ -267,5 +272,6 @@ bool Reassociate::runOnFunction(Function &F) {
 
   // We are done with the rank map...
   RankMap.clear();
+  InstRankMap.clear();
   return Changed;
 }