Revert commit 158979 (dyatkovskiy) since it is causing several buildbots to

fail.  Original commit message:

Performance optimizations:
- SwitchInst: case values stored separately from Operands List. It allows to make faster access to individual case value numbers or ranges.
- Optimized IntItem, added APInt value caching.
- Optimized IntegersSubsetGeneric: added optimizations for cases when subset is single number or when subset consists from single numbers only.

On my machine these optimizations gave about 4-6% of compile-time improvement.



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

2 files changed, 50 insertions, 159 deletions

diff --git a/include/llvm/Instructions.h b/include/llvm/Instructions.h
index 83f85f6..9555225 100644
--- a/include/llvm/Instructions.h
+++ b/include/llvm/Instructions.h
@@ -2442,31 +2442,10 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BranchInst, Value)
 class SwitchInst : public TerminatorInst {
   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
   unsigned ReservedSpace;
-  // Operands format:
   // Operand[0]    = Value to switch on
   // Operand[1]    = Default basic block destination
   // Operand[2n  ] = Value to match
   // Operand[2n+1] = BasicBlock to go to on match
-  
-  // Store case values separately from operands list. We needn't User-Use
-  // concept here, since it is just a case value, it will always constant,
-  // and case value couldn't reused with another instructions/values.
-  // Additionally:
-  // It allows us to use custom type for case values that is not inherited
-  // from Value. Since case value is a complex type that implements
-  // the subset of integers, we needn't extract sub-constants within
-  // slow getAggregateElement method.
-  // For case values we will use std::list to by two reasons:
-  // 1. It allows to add/remove cases without whole collection reallocation.
-  // 2. In most of cases we needn't random access.
-  // Currently case values are also stored in Operands List, but it will moved
-  // out in future commits.
-  typedef std::list<IntegersSubset> Subsets;
-  typedef Subsets::iterator SubsetsIt;
-  typedef Subsets::const_iterator SubsetsConstIt;
-  
-  Subsets TheSubsets;
-  
   SwitchInst(const SwitchInst &SI);
   void init(Value *Value, BasicBlock *Default, unsigned NumReserved);
   void growOperands();
@@ -2491,20 +2470,12 @@ protected:
   virtual SwitchInst *clone_impl() const;
 public:
   
-  // FIXME: Currently there are a lot of unclean template parameters,
-  // we need to make refactoring in future.
-  // All these parameters are used to implement both iterator and const_iterator
-  // without code duplication.
-  // SwitchInstTy may be "const SwitchInst" or "SwitchInst"
-  // ConstantIntTy may be "const ConstantInt" or "ConstantInt"
-  // SubsetsItTy may be SubsetsConstIt or SubsetsIt
-  // BasicBlockTy may be "const BasicBlock" or "BasicBlock"
-  template <class SwitchInstTy, class ConstantIntTy,
-            class SubsetsItTy, class BasicBlockTy> 
+  template <class SwitchInstTy, class ConstantIntTy, class BasicBlockTy> 
     class CaseIteratorT;
 
-  typedef CaseIteratorT<const SwitchInst, const ConstantInt,
-                        SubsetsConstIt, const BasicBlock> ConstCaseIt;
+  typedef CaseIteratorT<const SwitchInst, const ConstantInt, const BasicBlock>
+      ConstCaseIt;
+  
   class CaseIt;
   
   // -2
@@ -2545,23 +2516,23 @@ public:
   /// Returns a read/write iterator that points to the first
   /// case in SwitchInst.
   CaseIt case_begin() {
-    return CaseIt(this, 0, TheSubsets.begin());
+    return CaseIt(this, 0);
   }
   /// Returns a read-only iterator that points to the first
   /// case in the SwitchInst.
   ConstCaseIt case_begin() const {
-    return ConstCaseIt(this, 0, TheSubsets.begin());
+    return ConstCaseIt(this, 0);
   }
   
   /// Returns a read/write iterator that points one past the last
   /// in the SwitchInst.
   CaseIt case_end() {
-    return CaseIt(this, getNumCases(), TheSubsets.end());
+    return CaseIt(this, getNumCases());
   }
   /// Returns a read-only iterator that points one past the last
   /// in the SwitchInst.
   ConstCaseIt case_end() const {
-    return ConstCaseIt(this, getNumCases(), TheSubsets.end());
+    return ConstCaseIt(this, getNumCases());
   }
   /// Returns an iterator that points to the default case.
   /// Note: this iterator allows to resolve successor only. Attempt
@@ -2569,10 +2540,10 @@ public:
   /// Also note, that increment and decrement also causes an assertion and
   /// makes iterator invalid. 
   CaseIt case_default() {
-    return CaseIt(this, DefaultPseudoIndex, TheSubsets.end());
+    return CaseIt(this, DefaultPseudoIndex);
   }
   ConstCaseIt case_default() const {
-    return ConstCaseIt(this, DefaultPseudoIndex, TheSubsets.end());
+    return ConstCaseIt(this, DefaultPseudoIndex);
   }
   
   /// findCaseValue - Search all of the case values for the specified constant.
@@ -2651,38 +2622,24 @@ public:
   
   // Case iterators definition.
 
-  template <class SwitchInstTy, class ConstantIntTy,
-            class SubsetsItTy, class BasicBlockTy> 
+  template <class SwitchInstTy, class ConstantIntTy, class BasicBlockTy> 
   class CaseIteratorT {
   protected:
     
     SwitchInstTy *SI;
     unsigned Index;
-    SubsetsItTy SubsetIt;
+    
+  public:
+    
+    typedef CaseIteratorT<SwitchInstTy, ConstantIntTy, BasicBlockTy> Self;
     
     /// Initializes case iterator for given SwitchInst and for given
     /// case number.    
-    friend class SwitchInst;
-    CaseIteratorT(SwitchInstTy *SI, unsigned SuccessorIndex,
-                  SubsetsItTy CaseValueIt) {
+    CaseIteratorT(SwitchInstTy *SI, unsigned CaseNum) {
       this->SI = SI;
-      Index = SuccessorIndex;
-      this->SubsetIt = CaseValueIt;
+      Index = CaseNum;
     }
     
-  public:
-    typedef typename SubsetsItTy::reference IntegersSubsetRef;
-    typedef CaseIteratorT<SwitchInstTy, ConstantIntTy,
-                          SubsetsItTy, BasicBlockTy> Self;
-    
-    CaseIteratorT(SwitchInstTy *SI, unsigned CaseNum) {
-          this->SI = SI;
-          Index = CaseNum;
-          SubsetIt = SI->TheSubsets.begin();
-          std::advance(SubsetIt, CaseNum);
-        }
-        
-    
     /// Initializes case iterator for given SwitchInst and for given
     /// TerminatorInst's successor index.
     static Self fromSuccessorIndex(SwitchInstTy *SI, unsigned SuccessorIndex) {
@@ -2697,18 +2654,19 @@ public:
     /// @Deprecated
     ConstantIntTy *getCaseValue() {
       assert(Index < SI->getNumCases() && "Index out the number of cases.");
-      IntegersSubsetRef CaseRanges = *SubsetIt;
+      IntegersSubset CaseRanges =
+          reinterpret_cast<Constant*>(SI->getOperand(2 + Index*2));
+      IntegersSubset::Range R = CaseRanges.getItem(0);
       
       // FIXME: Currently we work with ConstantInt based cases.
       // So return CaseValue as ConstantInt.
-      return CaseRanges.getSingleNumber(0).toConstantInt();
+      return R.getLow().toConstantInt();
     }
 
     /// Resolves case value for current case.
-//    IntegersSubsetRef getCaseValueEx() {
     IntegersSubset getCaseValueEx() {
       assert(Index < SI->getNumCases() && "Index out the number of cases.");
-      return *SubsetIt;
+      return reinterpret_cast<Constant*>(SI->getOperand(2 + Index*2));
     }
     
     /// Resolves successor for current case.
@@ -2731,14 +2689,9 @@ public:
     
     Self operator++() {
       // Check index correctness after increment.
-      // Note: Index == getNumCases() means end().
-      unsigned NumCases = SI->getNumCases();
-      assert(Index+1 <= NumCases && "Index out the number of cases.");
+      // Note: Index == getNumCases() means end().      
+      assert(Index+1 <= SI->getNumCases() && "Index out the number of cases.");
       ++Index;
-      if (Index == 0)
-        SubsetIt = SI->TheSubsets.begin();
-      else
-        ++SubsetIt;
       return *this;
     }
     Self operator++(int) {
@@ -2750,18 +2703,9 @@ public:
       // Check index correctness after decrement.
       // Note: Index == getNumCases() means end().
       // Also allow "-1" iterator here. That will became valid after ++.
-      unsigned NumCases = SI->getNumCases();
-      assert((Index == 0 || Index-1 <= NumCases) &&
+      assert((Index == 0 || Index-1 <= SI->getNumCases()) &&
              "Index out the number of cases.");
       --Index;
-      if (Index == NumCases) {
-        SubsetIt = SI->TheSubsets.end();
-        return *this;
-      }
-        
-      if (Index != -1UL)
-        --SubsetIt;
-      
       return *this;
     }
     Self operator--(int) {
@@ -2779,25 +2723,14 @@ public:
     }
   };
 
-  class CaseIt : public CaseIteratorT<SwitchInst, ConstantInt,
-                                      SubsetsIt, BasicBlock> {
-    typedef CaseIteratorT<SwitchInst, ConstantInt, SubsetsIt, BasicBlock>
-      ParentTy;
-    
-  protected:
-    friend class SwitchInst;
-    CaseIt(SwitchInst *SI, unsigned CaseNum, SubsetsIt SubsetIt) :
-      ParentTy(SI, CaseNum, SubsetIt) {}
+  class CaseIt : public CaseIteratorT<SwitchInst, ConstantInt, BasicBlock> {
     
-    void updateCaseValueOperand(IntegersSubset& V) {
-      SI->setOperand(2 + Index*2, reinterpret_cast<Value*>((Constant*)V));      
-    }
+    typedef CaseIteratorT<SwitchInst, ConstantInt, BasicBlock> ParentTy;
   
   public:
-
-    CaseIt(SwitchInst *SI, unsigned CaseNum) : ParentTy(SI, CaseNum) {}    
     
     CaseIt(const ParentTy& Src) : ParentTy(Src) {}
+    CaseIt(SwitchInst *SI, unsigned CaseNum) : ParentTy(SI, CaseNum) {}
 
     /// Sets the new value for current case.    
     /// @Deprecated.
@@ -2807,15 +2740,14 @@ public:
       // FIXME: Currently we work with ConstantInt based cases.
       // So inititalize IntItem container directly from ConstantInt.
       Mapping.add(IntItem::fromConstantInt(V));
-      *SubsetIt = Mapping.getCase();
-      updateCaseValueOperand(*SubsetIt);
+      SI->setOperand(2 + Index*2,
+          reinterpret_cast<Value*>((Constant*)Mapping.getCase()));
     }
     
     /// Sets the new value for current case.
     void setValueEx(IntegersSubset& V) {
       assert(Index < SI->getNumCases() && "Index out the number of cases.");
-      *SubsetIt = V;
-      updateCaseValueOperand(*SubsetIt);   
+      SI->setOperand(2 + Index*2, reinterpret_cast<Value*>((Constant*)V));      
     }
     
     /// Sets the new successor for current case.
diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h
index 69c94a3..2ceeea5 100644
--- a/include/llvm/Support/IntegersSubset.h
+++ b/include/llvm/Support/IntegersSubset.h
@@ -40,26 +40,26 @@ namespace llvm {
 
 #define INT_ITEM_DEFINE_COMPARISON(op,func) \
   bool operator op (const APInt& RHS) const { \
-    return getAPIntValue().func(RHS); \
+    return ConstantIntVal->getValue().func(RHS); \
   }
   
 #define INT_ITEM_DEFINE_UNARY_OP(op) \
   IntItem operator op () const { \
-    APInt res = op(getAPIntValue()); \
+    APInt res = op(ConstantIntVal->getValue()); \
     Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
     return IntItem(cast<ConstantInt>(NewVal)); \
   }
   
 #define INT_ITEM_DEFINE_BINARY_OP(op) \
   IntItem operator op (const APInt& RHS) const { \
-    APInt res = getAPIntValue() op RHS; \
+    APInt res = ConstantIntVal->getValue() op RHS; \
     Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
     return IntItem(cast<ConstantInt>(NewVal)); \
   }
   
 #define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \
   IntItem& operator op (const APInt& RHS) {\
-    APInt res = getAPIntValue();\
+    APInt res = ConstantIntVal->getValue();\
     res op RHS; \
     Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
     ConstantIntVal = cast<ConstantInt>(NewVal); \
@@ -68,7 +68,7 @@ namespace llvm {
   
 #define INT_ITEM_DEFINE_PREINCDEC(op) \
     IntItem& operator op () { \
-      APInt res = getAPIntValue(); \
+      APInt res = ConstantIntVal->getValue(); \
       op(res); \
       Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
       ConstantIntVal = cast<ConstantInt>(NewVal); \
@@ -77,7 +77,7 @@ namespace llvm {
 
 #define INT_ITEM_DEFINE_POSTINCDEC(op) \
     IntItem& operator op (int) { \
-      APInt res = getAPIntValue();\
+      APInt res = ConstantIntVal->getValue();\
       op(res); \
       Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
       OldConstantIntVal = ConstantIntVal; \
@@ -87,24 +87,18 @@ namespace llvm {
   
 #define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \
   RetTy operator op (IntTy RHS) const { \
-    return (*this) op APInt(getAPIntValue().getBitWidth(), RHS); \
+    return (*this) op APInt(ConstantIntVal->getValue().getBitWidth(), RHS); \
   }  
 
 class IntItem {
   ConstantInt *ConstantIntVal;
-  const APInt* APIntVal;
-  IntItem(const ConstantInt *V) :
-    ConstantIntVal(const_cast<ConstantInt*>(V)),
-    APIntVal(&ConstantIntVal->getValue()){}
-  const APInt& getAPIntValue() const {
-    return *APIntVal;
-  }
+  IntItem(const ConstantInt *V) : ConstantIntVal(const_cast<ConstantInt*>(V)) {}
 public:
   
   IntItem() {}
   
   operator const APInt&() const {
-    return getAPIntValue();
+    return (const APInt&)ConstantIntVal->getValue();
   }  
   
   // Propagate APInt operators.
@@ -143,7 +137,7 @@ public:
   
   // Special case for <<=
   IntItem& operator <<= (unsigned RHS) {
-    APInt res = getAPIntValue();
+    APInt res = ConstantIntVal->getValue();
     res <<= RHS;
     Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res);
     ConstantIntVal = cast<ConstantInt>(NewVal);
@@ -284,9 +278,9 @@ public:
   // In short, for more compact memory consumption we can store flat
   // numbers collection, and define range as pair of indices.
   // In that case we can safe some memory on 32 bit machines.
-  typedef std::vector<IntTy> FlatCollectionTy;
+  typedef std::list<IntTy> FlatCollectionTy;
   typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
-  typedef std::vector<RangeLinkTy> RangeLinksTy;
+  typedef SmallVector<RangeLinkTy, 64> RangeLinksTy;
   typedef typename RangeLinksTy::const_iterator RangeLinksConstIt;
   
   typedef IntegersSubsetGeneric<IntTy> self;
@@ -296,33 +290,21 @@ protected:
   FlatCollectionTy FlatCollection;
   RangeLinksTy RangeLinks;
   
-  bool IsSingleNumber;
-  bool IsSingleNumbersOnly;
-  
 public:
   
   template<class RangesCollectionTy>
   explicit IntegersSubsetGeneric(const RangesCollectionTy& Links) {
     assert(Links.size() && "Empty ranges are not allowed.");
-    
-    // In case of big set of single numbers consumes additional RAM space,
-    // but allows to avoid additional reallocation.
-    FlatCollection.reserve(Links.size() * 2);
-    RangeLinks.reserve(Links.size());        
-    IsSingleNumbersOnly = true;
     for (typename RangesCollectionTy::const_iterator i = Links.begin(),
          e = Links.end(); i != e; ++i) {
       RangeLinkTy RangeLink;
       FlatCollection.push_back(i->getLow());
       RangeLink.first = &FlatCollection.back();
-      if (i->getLow() != i->getHigh()) {
+      if (i->getLow() != i->getHigh())
         FlatCollection.push_back(i->getHigh());
-        IsSingleNumbersOnly = false;
-      }
       RangeLink.second = &FlatCollection.back();
       RangeLinks.push_back(RangeLink);
     }
-    IsSingleNumber = IsSingleNumbersOnly && RangeLinks.size() == 1;
   }
   
   IntegersSubsetGeneric(const self& RHS) {
@@ -332,8 +314,6 @@ public:
   self& operator=(const self& RHS) {
     FlatCollection.clear();
     RangeLinks.clear();
-    FlatCollection.reserve(RHS.RangeLinks.size() * 2);
-    RangeLinks.reserve(RHS.RangeLinks.size());
     for (RangeLinksConstIt i = RHS.RangeLinks.begin(), e = RHS.RangeLinks.end();
          i != e; ++i) {
       RangeLinkTy RangeLink;
@@ -344,8 +324,6 @@ public:
       RangeLink.second = &FlatCollection.back();
       RangeLinks.push_back(RangeLink);
     }
-    IsSingleNumber = RHS.IsSingleNumber;
-    IsSingleNumbersOnly = RHS.IsSingleNumbersOnly;
     return *this;
   }
   
@@ -355,13 +333,6 @@ public:
   /// true if it equals to one of contained values or belongs to the one of
   /// contained ranges.
   bool isSatisfies(const IntTy &CheckingVal) const {
-    if (IsSingleNumber)
-      return FlatCollection.front() == CheckingVal;
-    if (IsSingleNumbersOnly)
-      return std::find(FlatCollection.begin(),
-                       FlatCollection.end(),
-                       CheckingVal) != FlatCollection.end();
-    
     for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
       if (RangeLinks[i].first == RangeLinks[i].second) {
         if (*RangeLinks[i].first == CheckingVal)
@@ -389,12 +360,8 @@ public:
   
   /// Returns true if whole subset contains single element.
   bool isSingleNumber() const {
-    return IsSingleNumber;
-  }
-  
-  /// Returns true if whole subset contains only single numbers, no ranges.
-  bool isSingleNumbersOnly() const {
-    return IsSingleNumbersOnly;
+    return RangeLinks.size() == 1 &&
+           RangeLinks[0].first == RangeLinks[0].second;
   }
 
   /// Does the same like getItem(idx).isSingleNumber(), but
@@ -418,7 +385,7 @@ public:
     }
     return sz.getZExtValue();    
   }
-    
+  
   /// Allows to access single value even if it belongs to some range.
   /// Ranges set is considered as flat numbers collection.
   /// [<1>, <4,8>] is considered as [1,4,5,6,7,8] 
@@ -442,14 +409,6 @@ public:
     assert(0 && "Index exceeds high border.");
     return sz;    
   }
-  
-  /// Does the same as getSingleValue, but works only if subset contains
-  /// single numbers only.
-  const IntTy& getSingleNumber(unsigned idx) const {
-    assert(IsSingleNumbersOnly && "This method works properly if subset "
-                                  "contains single numbers only.");
-    return FlatCollection[idx];
-  }
 };  
 
 //===----------------------------------------------------------------------===//
@@ -496,9 +455,9 @@ class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
   }
   
 public:
-
-  explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
-                          Holder(C) {}
+  
+  IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
+                                Holder(C) {}
   
   template<class RangesCollectionTy>
   explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) {