Revert patches to add case-range support for PR1255.

The work on this project was left in an unfinished and inconsistent state.
Hopefully someone will eventually get a chance to implement this feature, but
in the meantime, it is better to put things back the way the were.  I have
left support in the bitcode reader to handle the case-range bitcode format,
so that we do not lose bitcode compatibility with the llvm 3.3 release.

This reverts the following commits: 155464, 156374, 156377, 156613, 156704,
156757, 156804 156808, 156985, 157046, 157112, 157183, 157315, 157384, 157575,
157576, 157586, 157612, 157810, 157814, 157815, 157880, 157881, 157882, 157884,
157887, 157901, 158979, 157987, 157989, 158986, 158997, 159076, 159101, 159100,
159200, 159201, 159207, 159527, 159532, 159540, 159583, 159618, 159658, 159659,
159660, 159661, 159703, 159704, 160076, 167356, 172025, 186736

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

1 files changed, 121 insertions, 237 deletions

diff --git a/include/llvm/IR/Instructions.h b/include/llvm/IR/Instructions.h
index e05c3a8..6adee6a 100644
--- a/include/llvm/IR/Instructions.h
+++ b/include/llvm/IR/Instructions.h
@@ -23,8 +23,6 @@
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/IntegersSubset.h"
-#include "llvm/Support/IntegersSubsetMapping.h"
 #include <iterator>
 
 namespace llvm {
@@ -2457,31 +2455,10 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BranchInst, Value)
 class SwitchInst : public TerminatorInst {
   void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
   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();
@@ -2506,25 +2483,121 @@ 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>
-    class CaseIteratorT;
-
-  typedef CaseIteratorT<const SwitchInst, const ConstantInt,
-                        SubsetsConstIt, const BasicBlock> ConstCaseIt;
-  class CaseIt;
-
   // -2
   static const unsigned DefaultPseudoIndex = static_cast<unsigned>(~0L-1);
 
+  template <class SwitchInstTy, class ConstantIntTy, class BasicBlockTy>
+  class CaseIteratorT {
+  protected:
+
+    SwitchInstTy *SI;
+    unsigned Index;
+
+  public:
+
+    typedef CaseIteratorT<SwitchInstTy, ConstantIntTy, BasicBlockTy> Self;
+
+    /// Initializes case iterator for given SwitchInst and for given
+    /// case number.
+    CaseIteratorT(SwitchInstTy *SI, unsigned CaseNum) {
+      this->SI = SI;
+      Index = CaseNum;
+    }
+
+    /// Initializes case iterator for given SwitchInst and for given
+    /// TerminatorInst's successor index.
+    static Self fromSuccessorIndex(SwitchInstTy *SI, unsigned SuccessorIndex) {
+      assert(SuccessorIndex < SI->getNumSuccessors() &&
+             "Successor index # out of range!");
+      return SuccessorIndex != 0 ?
+             Self(SI, SuccessorIndex - 1) :
+             Self(SI, DefaultPseudoIndex);
+    }
+
+    /// Resolves case value for current case.
+    ConstantIntTy *getCaseValue() {
+      assert(Index < SI->getNumCases() && "Index out the number of cases.");
+      return reinterpret_cast<ConstantIntTy*>(SI->getOperand(2 + Index*2));
+    }
+
+    /// Resolves successor for current case.
+    BasicBlockTy *getCaseSuccessor() {
+      assert((Index < SI->getNumCases() ||
+              Index == DefaultPseudoIndex) &&
+             "Index out the number of cases.");
+      return SI->getSuccessor(getSuccessorIndex());
+    }
+
+    /// Returns number of current case.
+    unsigned getCaseIndex() const { return Index; }
+
+    /// Returns TerminatorInst's successor index for current case successor.
+    unsigned getSuccessorIndex() const {
+      assert((Index == DefaultPseudoIndex || Index < SI->getNumCases()) &&
+             "Index out the number of cases.");
+      return Index != DefaultPseudoIndex ? Index + 1 : 0;
+    }
+
+    Self operator++() {
+      // Check index correctness after increment.
+      // Note: Index == getNumCases() means end().
+      assert(Index+1 <= SI->getNumCases() && "Index out the number of cases.");
+      ++Index;
+      return *this;
+    }
+    Self operator++(int) {
+      Self tmp = *this;
+      ++(*this);
+      return tmp;
+    }
+    Self operator--() {
+      // 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()) &&
+             "Index out the number of cases.");
+      --Index;
+      return *this;
+    }
+    Self operator--(int) {
+      Self tmp = *this;
+      --(*this);
+      return tmp;
+    }
+    bool operator==(const Self& RHS) const {
+      assert(RHS.SI == SI && "Incompatible operators.");
+      return RHS.Index == Index;
+    }
+    bool operator!=(const Self& RHS) const {
+      assert(RHS.SI == SI && "Incompatible operators.");
+      return RHS.Index != Index;
+    }
+  };
+
+  typedef CaseIteratorT<const SwitchInst, const ConstantInt, const BasicBlock>
+    ConstCaseIt;
+
+  class CaseIt : public CaseIteratorT<SwitchInst, ConstantInt, BasicBlock> {
+
+    typedef CaseIteratorT<SwitchInst, ConstantInt, BasicBlock> ParentTy;
+
+  public:
+
+    CaseIt(const ParentTy& Src) : ParentTy(Src) {}
+    CaseIt(SwitchInst *SI, unsigned CaseNum) : ParentTy(SI, CaseNum) {}
+
+    /// Sets the new value for current case.
+    void setValue(ConstantInt *V) {
+      assert(Index < SI->getNumCases() && "Index out the number of cases.");
+      SI->setOperand(2 + Index*2, reinterpret_cast<Value*>(V));
+    }
+
+    /// Sets the new successor for current case.
+    void setSuccessor(BasicBlock *S) {
+      SI->setSuccessor(getSuccessorIndex(), S);
+    }
+  };
+
   static SwitchInst *Create(Value *Value, BasicBlock *Default,
                             unsigned NumCases, Instruction *InsertBefore = 0) {
     return new SwitchInst(Value, Default, NumCases, InsertBefore);
@@ -2560,23 +2633,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
@@ -2584,10 +2657,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.
@@ -2596,13 +2669,13 @@ public:
   /// that it is handled by the default handler.
   CaseIt findCaseValue(const ConstantInt *C) {
     for (CaseIt i = case_begin(), e = case_end(); i != e; ++i)
-      if (i.getCaseValueEx().isSatisfies(IntItem::fromConstantInt(C)))
+      if (i.getCaseValue() == C)
         return i;
     return case_default();
   }
   ConstCaseIt findCaseValue(const ConstantInt *C) const {
     for (ConstCaseIt i = case_begin(), e = case_end(); i != e; ++i)
-      if (i.getCaseValueEx().isSatisfies(IntItem::fromConstantInt(C)))
+      if (i.getCaseValue() == C)
         return i;
     return case_default();
   }
@@ -2628,19 +2701,13 @@ public:
   /// point to the added case.
   void addCase(ConstantInt *OnVal, BasicBlock *Dest);
 
-  /// addCase - Add an entry to the switch instruction.
-  /// Note:
-  /// This action invalidates case_end(). Old case_end() iterator will
-  /// point to the added case.
-  void addCase(IntegersSubset& OnVal, BasicBlock *Dest);
-
   /// removeCase - This method removes the specified case and its successor
   /// from the switch instruction. Note that this operation may reorder the
   /// remaining cases at index idx and above.
   /// Note:
   /// This action invalidates iterators for all cases following the one removed,
   /// including the case_end() iterator.
-  void removeCase(CaseIt& i);
+  void removeCase(CaseIt i);
 
   unsigned getNumSuccessors() const { return getNumOperands()/2; }
   BasicBlock *getSuccessor(unsigned idx) const {
@@ -2652,190 +2719,7 @@ public:
     setOperand(idx*2+1, (Value*)NewSucc);
   }
 
-  uint16_t hash() const {
-    uint32_t NumberOfCases = (uint32_t)getNumCases();
-    uint16_t Hash = (0xFFFF & NumberOfCases) ^ (NumberOfCases >> 16);
-    for (ConstCaseIt i = case_begin(), e = case_end();
-         i != e; ++i) {
-      uint32_t NumItems = (uint32_t)i.getCaseValueEx().getNumItems();
-      Hash = (Hash << 1) ^ (0xFFFF & NumItems) ^ (NumItems >> 16);
-    }
-    return Hash;
-  }
-
-  // Case iterators definition.
-
-  template <class SwitchInstTy, class ConstantIntTy,
-            class SubsetsItTy, class BasicBlockTy>
-  class CaseIteratorT {
-  protected:
-
-    SwitchInstTy *SI;
-    unsigned Index;
-    SubsetsItTy SubsetIt;
-
-    /// Initializes case iterator for given SwitchInst and for given
-    /// case number.
-    friend class SwitchInst;
-    CaseIteratorT(SwitchInstTy *SI, unsigned SuccessorIndex,
-                  SubsetsItTy CaseValueIt) {
-      this->SI = SI;
-      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) {
-      assert(SuccessorIndex < SI->getNumSuccessors() &&
-             "Successor index # out of range!");
-      return SuccessorIndex != 0 ?
-             Self(SI, SuccessorIndex - 1) :
-             Self(SI, DefaultPseudoIndex);
-    }
-
-    /// Resolves case value for current case.
-    ConstantIntTy *getCaseValue() {
-      assert(Index < SI->getNumCases() && "Index out the number of cases.");
-      IntegersSubsetRef CaseRanges = *SubsetIt;
-
-      // FIXME: Currently we work with ConstantInt based cases.
-      // So return CaseValue as ConstantInt.
-      return CaseRanges.getSingleNumber(0).toConstantInt();
-    }
-
-    /// Resolves case value for current case.
-    IntegersSubsetRef getCaseValueEx() {
-      assert(Index < SI->getNumCases() && "Index out the number of cases.");
-      return *SubsetIt;
-    }
-
-    /// Resolves successor for current case.
-    BasicBlockTy *getCaseSuccessor() {
-      assert((Index < SI->getNumCases() ||
-              Index == DefaultPseudoIndex) &&
-             "Index out the number of cases.");
-      return SI->getSuccessor(getSuccessorIndex());
-    }
-
-    /// Returns number of current case.
-    unsigned getCaseIndex() const { return Index; }
-
-    /// Returns TerminatorInst's successor index for current case successor.
-    unsigned getSuccessorIndex() const {
-      assert((Index == DefaultPseudoIndex || Index < SI->getNumCases()) &&
-             "Index out the number of cases.");
-      return Index != DefaultPseudoIndex ? Index + 1 : 0;
-    }
-
-    Self operator++() {
-      // Check index correctness after increment.
-      // 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) {
-      Self tmp = *this;
-      ++(*this);
-      return tmp;
-    }
-    Self operator--() {
-      // 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) &&
-             "Index out the number of cases.");
-      --Index;
-      if (Index == NumCases) {
-        SubsetIt = SI->TheSubsets.end();
-        return *this;
-      }
-
-      if (Index != -1U)
-        --SubsetIt;
-
-      return *this;
-    }
-    Self operator--(int) {
-      Self tmp = *this;
-      --(*this);
-      return tmp;
-    }
-    bool operator==(const Self& RHS) const {
-      assert(RHS.SI == SI && "Incompatible operators.");
-      return RHS.Index == Index;
-    }
-    bool operator!=(const Self& RHS) const {
-      assert(RHS.SI == SI && "Incompatible operators.");
-      return RHS.Index != Index;
-    }
-  };
-
-  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) {}
-
-    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) {}
-
-    /// Sets the new value for current case.
-    void setValue(ConstantInt *V) {
-      assert(Index < SI->getNumCases() && "Index out the number of cases.");
-      IntegersSubsetToBB Mapping;
-      // 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);
-    }
-
-    /// 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);
-    }
-
-    /// Sets the new successor for current case.
-    void setSuccessor(BasicBlock *S) {
-      SI->setSuccessor(getSuccessorIndex(), S);
-    }
-  };
-
   // Methods for support type inquiry through isa, cast, and dyn_cast:
-
   static inline bool classof(const Instruction *I) {
     return I->getOpcode() == Instruction::Switch;
   }