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@158979 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 99 insertions, 31 deletions

diff --git a/include/llvm/Instructions.h b/include/llvm/Instructions.h
index 955522539e..83f85f62da 100644
--- a/include/llvm/Instructions.h
+++ b/include/llvm/Instructions.h
@@ -2442,10 +2442,31 @@ 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();
@@ -2470,12 +2491,20 @@ protected:
   virtual SwitchInst *clone_impl() const;
 public:
   
-  template <class SwitchInstTy, class ConstantIntTy, class BasicBlockTy> 
+  // 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> 
     class CaseIteratorT;
 
-  typedef CaseIteratorT<const SwitchInst, const ConstantInt, const BasicBlock>
-      ConstCaseIt;
-  
+  typedef CaseIteratorT<const SwitchInst, const ConstantInt,
+                        SubsetsConstIt, const BasicBlock> ConstCaseIt;
   class CaseIt;
   
   // -2
@@ -2516,23 +2545,23 @@ public:
   /// Returns a read/write iterator that points to the first
   /// case in SwitchInst.
   CaseIt case_begin() {
-    return CaseIt(this, 0);
+    return CaseIt(this, 0, TheSubsets.begin());
   }
   /// Returns a read-only iterator that points to the first
   /// case in the SwitchInst.
   ConstCaseIt case_begin() const {
-    return ConstCaseIt(this, 0);
+    return ConstCaseIt(this, 0, TheSubsets.begin());
   }
   
   /// Returns a read/write iterator that points one past the last
   /// in the SwitchInst.
   CaseIt case_end() {
-    return CaseIt(this, getNumCases());
+    return CaseIt(this, getNumCases(), TheSubsets.end());
   }
   /// Returns a read-only iterator that points one past the last
   /// in the SwitchInst.
   ConstCaseIt case_end() const {
-    return ConstCaseIt(this, getNumCases());
+    return ConstCaseIt(this, getNumCases(), TheSubsets.end());
   }
   /// Returns an iterator that points to the default case.
   /// Note: this iterator allows to resolve successor only. Attempt
@@ -2540,10 +2569,10 @@ public:
   /// Also note, that increment and decrement also causes an assertion and
   /// makes iterator invalid. 
   CaseIt case_default() {
-    return CaseIt(this, DefaultPseudoIndex);
+    return CaseIt(this, DefaultPseudoIndex, TheSubsets.end());
   }
   ConstCaseIt case_default() const {
-    return ConstCaseIt(this, DefaultPseudoIndex);
+    return ConstCaseIt(this, DefaultPseudoIndex, TheSubsets.end());
   }
   
   /// findCaseValue - Search all of the case values for the specified constant.
@@ -2622,24 +2651,38 @@ public:
   
   // Case iterators definition.
 
-  template <class SwitchInstTy, class ConstantIntTy, class BasicBlockTy> 
+  template <class SwitchInstTy, class ConstantIntTy,
+            class SubsetsItTy, class BasicBlockTy> 
   class CaseIteratorT {
   protected:
     
     SwitchInstTy *SI;
     unsigned Index;
-    
-  public:
-    
-    typedef CaseIteratorT<SwitchInstTy, ConstantIntTy, BasicBlockTy> Self;
+    SubsetsItTy SubsetIt;
     
     /// Initializes case iterator for given SwitchInst and for given
     /// case number.    
-    CaseIteratorT(SwitchInstTy *SI, unsigned CaseNum) {
+    friend class SwitchInst;
+    CaseIteratorT(SwitchInstTy *SI, unsigned SuccessorIndex,
+                  SubsetsItTy CaseValueIt) {
       this->SI = SI;
-      Index = CaseNum;
+      Index = SuccessorIndex;
+      this->SubsetIt = CaseValueIt;
     }
     
+  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) {
@@ -2654,19 +2697,18 @@ public:
     /// @Deprecated
     ConstantIntTy *getCaseValue() {
       assert(Index < SI->getNumCases() && "Index out the number of cases.");
-      IntegersSubset CaseRanges =
-          reinterpret_cast<Constant*>(SI->getOperand(2 + Index*2));
-      IntegersSubset::Range R = CaseRanges.getItem(0);
+      IntegersSubsetRef CaseRanges = *SubsetIt;
       
       // FIXME: Currently we work with ConstantInt based cases.
       // So return CaseValue as ConstantInt.
-      return R.getLow().toConstantInt();
+      return CaseRanges.getSingleNumber(0).toConstantInt();
     }
 
     /// Resolves case value for current case.
+//    IntegersSubsetRef getCaseValueEx() {
     IntegersSubset getCaseValueEx() {
       assert(Index < SI->getNumCases() && "Index out the number of cases.");
-      return reinterpret_cast<Constant*>(SI->getOperand(2 + Index*2));
+      return *SubsetIt;
     }
     
     /// Resolves successor for current case.
@@ -2689,9 +2731,14 @@ public:
     
     Self operator++() {
       // Check index correctness after increment.
-      // Note: Index == getNumCases() means end().      
-      assert(Index+1 <= SI->getNumCases() && "Index out the number of cases.");
+      // Note: Index == getNumCases() means end().
+      unsigned NumCases = SI->getNumCases();
+      assert(Index+1 <= NumCases && "Index out the number of cases.");
       ++Index;
+      if (Index == 0)
+        SubsetIt = SI->TheSubsets.begin();
+      else
+        ++SubsetIt;
       return *this;
     }
     Self operator++(int) {
@@ -2703,9 +2750,18 @@ public:
       // Check index correctness after decrement.
       // Note: Index == getNumCases() means end().
       // Also allow "-1" iterator here. That will became valid after ++.
-      assert((Index == 0 || Index-1 <= SI->getNumCases()) &&
+      unsigned NumCases = SI->getNumCases();
+      assert((Index == 0 || Index-1 <= NumCases) &&
              "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) {
@@ -2723,14 +2779,25 @@ public:
     }
   };
 
-  class CaseIt : public CaseIteratorT<SwitchInst, ConstantInt, BasicBlock> {
+  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) {}
     
-    typedef CaseIteratorT<SwitchInst, ConstantInt, BasicBlock> ParentTy;
+    void updateCaseValueOperand(IntegersSubset& V) {
+      SI->setOperand(2 + Index*2, reinterpret_cast<Value*>((Constant*)V));      
+    }
   
   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.
@@ -2740,14 +2807,15 @@ public:
       // FIXME: Currently we work with ConstantInt based cases.
       // So inititalize IntItem container directly from ConstantInt.
       Mapping.add(IntItem::fromConstantInt(V));
-      SI->setOperand(2 + Index*2,
-          reinterpret_cast<Value*>((Constant*)Mapping.getCase()));
+      *SubsetIt = Mapping.getCase();
+      updateCaseValueOperand(*SubsetIt);
     }
     
     /// Sets the new value for current case.
     void setValueEx(IntegersSubset& V) {
       assert(Index < SI->getNumCases() && "Index out the number of cases.");
-      SI->setOperand(2 + Index*2, reinterpret_cast<Value*>((Constant*)V));      
+      *SubsetIt = V;
+      updateCaseValueOperand(*SubsetIt);   
     }
     
     /// Sets the new successor for current case.