Remove SmallMap, and the several files that were used to implement it.

We have SmallDenseMap now that has more correct and predictable
semantics, even though it is a more narrow abstraction.

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

3 files changed, 0 insertions, 912 deletions

diff --git a/include/llvm/ADT/FlatArrayMap.h b/include/llvm/ADT/FlatArrayMap.h
deleted file mode 100644
index 2d60ef8..0000000
--- a/include/llvm/ADT/FlatArrayMap.h
+++ /dev/null
@@ -1,325 +0,0 @@
-//===- llvm/ADT/FlatArrayMap.h - 'Normally small' pointer set ----*- C++ -*-==//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the FlatArrayMap class.
-// See FlatArrayMap doxygen comments for more details.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef FLATARRAYMAP_H_
-#define FLATARRAYMAP_H_
-
-#include <algorithm>
-#include <utility>
-#include "llvm/Support/type_traits.h"
-
-namespace llvm {
-
-  template <typename KeyTy, typename MappedTy>
-  struct FlatArrayMapTypes {
-    typedef KeyTy key_type;
-    typedef MappedTy mapped_type;
-    typedef typename std::pair<key_type, mapped_type> value_type;
-  };
-
-  template<typename KeyTy, typename MappedTy, bool IsConst = false>
-  class FlatArrayMapIterator;
-
-  //===--------------------------------------------------------------------===//
-  /// FlatArrayMap presents map container interface.
-  /// It uses flat array implementation inside:
-  /// [ <key0, value0>, <key1, value1>, ... <keyN, valueN> ]
-  /// It works fast for small amount of elements.
-  /// User should pass key type, mapped type (type of value), and maximum
-  /// number of elements.
-  /// After maximum number of elements is reached, map declines any farther
-  /// attempts to insert new elements ("insert" method returns <end(),false>).
-  ///
-  template <typename KeyTy, typename MappedTy, unsigned MaxArraySize>
-  class FlatArrayMap {
-  public:
-    typedef FlatArrayMapTypes<KeyTy, MappedTy> Types;
-
-    typedef typename Types::key_type key_type;
-    typedef typename Types::mapped_type mapped_type;
-    typedef typename Types::value_type value_type;
-
-    typedef FlatArrayMapIterator<KeyTy, MappedTy> iterator;
-    typedef FlatArrayMapIterator<KeyTy, MappedTy, true> const_iterator;
-
-    typedef FlatArrayMap<KeyTy, MappedTy, MaxArraySize> self;
-
-  private:
-
-    enum { BadIndex = -1U };
-
-    key_type EmptyKey;
-    mapped_type EmptyValue;
-
-    value_type Array[MaxArraySize + 1];
-    unsigned NumElements;
-
-  unsigned findFor(const KeyTy Ptr) const {
-    // Linear search for the item.
-    for (const value_type *APtr = Array, *E = Array + NumElements;
-               APtr != E; ++APtr) {
-      if (APtr->first == Ptr) {
-        return APtr - Array;
-      }
-    }
-    return BadIndex;
-  }
-
-  bool lookupFor(const KeyTy &Ptr, const value_type*& Found) const {
-    unsigned FoundIdx = findFor(Ptr);
-    if (FoundIdx != BadIndex) {
-      Found = Array + FoundIdx;
-      return true;
-    }
-    return false;
-  }
-
-  bool lookupFor(const KeyTy &Ptr, value_type*& Found) {
-    unsigned FoundIdx = findFor(Ptr);
-    if (FoundIdx != BadIndex) {
-      Found = Array + FoundIdx;
-      return true;
-    }
-    return false;
-  }
-
-
-  void copyFrom(const self &RHS) {
-    std::copy(RHS.Array, RHS.Array + MaxArraySize + 1, Array);
-    NumElements = RHS.NumElements;
-  }
-
-  void init () {
-    // Even if Array contains non POD, use memset for last element,
-    // since it is used as end() iterator only.
-    memset(Array + MaxArraySize, 0, sizeof(value_type));
-    NumElements = 0;
-  }
-
-  bool insertInternal(KeyTy Ptr, MappedTy Val, value_type*& Item) {
-    // Check to see if it is already in the set.
-    value_type *Found;
-    if (lookupFor(Ptr, Found)) {
-      Item = Found;
-      return false;
-    }
-    if (NumElements < MaxArraySize) {
-      unsigned Idx = NumElements++;
-      Array[Idx] = std::make_pair(Ptr, Val);
-      Item = Array + Idx;
-      return true;
-    }
-    Item = Array + MaxArraySize; // return end()
-    return false;
-  }
-
-  public:
-
-    // Constructors
-
-    FlatArrayMap() : EmptyKey(), EmptyValue() {
-      init();
-    }
-
-    FlatArrayMap(const self &that) :
-      EmptyKey(), EmptyValue() {
-      copyFrom(that);
-    }
-
-    template<typename It>
-    FlatArrayMap(It I, It E) :
-      EmptyKey(), EmptyValue() {
-      init();
-      insert(I, E);
-    }
-
-    // Size
-
-    unsigned size() const {
-      return NumElements;
-    }
-
-    bool empty() const {
-      return !NumElements;
-    }
-
-    // Iterators
-
-    iterator begin() {
-      return iterator(Array);
-    }
-    const_iterator begin() const {
-      return const_iterator(Array);
-    }
-
-    iterator end() {
-      return iterator(Array + NumElements);
-    }
-    const_iterator end() const {
-      return const_iterator(Array + NumElements);
-    }
-
-    // Modifiers
-
-    void clear() {
-      for (unsigned i = 0; i < NumElements; ++i) {
-        Array[i].first = EmptyKey;
-        Array[i].second = EmptyValue;
-      }
-      NumElements = 0;
-    }
-
-    // The map container is extended by inserting a single new element.
-    // The behavior is the same as the std::map::insert, except the
-    // case when maximum number of elements is reached;
-    // in this case map declines any farther attempts
-    // to insert new elements ("insert" method returns <end(),false>).
-    std::pair<iterator, bool> insert(const value_type& KV) {
-      value_type* Item;
-      bool Res = insertInternal(KV.first, KV.second, Item);
-      return std::make_pair(iterator(Item), Res);
-    }
-
-    template <typename IterT>
-    void insert(IterT I, IterT E) {
-      for (; I != E; ++I)
-        insert(*I);
-    }
-
-    void erase(key_type K) {
-      unsigned Found = findFor(K);
-      if (Found != BadIndex) {
-        value_type *APtr = Array + Found;
-        value_type *E = Array + NumElements;
-        *APtr = E[-1];
-        E[-1].first.~key_type();
-        E[-1].second.~mapped_type();
-        --NumElements;
-      }
-    }
-
-    void erase(iterator i) {
-      erase(i->first);
-    }
-
-    void swap(self& RHS) {
-      std::swap_ranges(Array, Array+MaxArraySize,  RHS.Array);
-      std::swap(this->NumElements, RHS.NumElements);
-    }
-
-    // Search operations
-
-    iterator find(const key_type& K) {
-      value_type *Found;
-      if (lookupFor(K, Found))
-        return iterator(Found);
-      return end();
-    }
-
-    const_iterator find(const key_type& K) const {
-      const value_type *Found;
-      if (lookupFor(K, Found))
-        return const_iterator(Found);
-      return end();
-    }
-
-    bool count(const key_type& K) const {
-      return find(K) != end();
-    }
-
-    mapped_type &operator[](const key_type &Key) {
-      std::pair<iterator, bool> res = insert(Key, mapped_type());
-      return res.first->second;
-    }
-
-    // Other operations
-
-    self& operator=(const self& other) {
-      clear();
-      copyFrom(other);
-      return *this;
-    }
-
-    /// isPointerIntoBucketsArray - Return true if the specified pointer points
-    /// somewhere into the map's array of buckets (i.e. either to a key or
-    /// value).
-    bool isPointerIntoBucketsArray(const void *Ptr) const {
-      return Ptr >= Array && Ptr < Array + NumElements;
-    }
-
-    /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
-    /// array.
-    const void *getPointerIntoBucketsArray() const { return Array; }
-  };
-
-  template<typename KeyTy, typename MappedTy, bool IsConst>
-  class FlatArrayMapIterator {
-
-    typedef FlatArrayMapTypes<KeyTy, MappedTy> Types;
-
-    typedef typename conditional<IsConst,
-                                 const typename Types::value_type,
-                                 typename Types::value_type>::type value_type;
-    typedef value_type *pointer;
-    typedef value_type &reference;
-
-    typedef FlatArrayMapIterator<KeyTy, MappedTy, IsConst> self;
-    typedef FlatArrayMapIterator<KeyTy, MappedTy, false> non_const_self;
-    typedef FlatArrayMapIterator<KeyTy, MappedTy, true> const_self;
-
-    friend class FlatArrayMapIterator<KeyTy, MappedTy, false>;
-    friend class FlatArrayMapIterator<KeyTy, MappedTy, true>;
-
-    pointer TheBucket;
-
-  public:
-
-    FlatArrayMapIterator() : TheBucket(0) {}
-
-    explicit FlatArrayMapIterator(pointer BP) :
-        TheBucket(BP) {}
-
-    // If IsConst is true this is a converting constructor from iterator to
-    // const_iterator and the default copy constructor is used.
-    // Otherwise this is a copy constructor for iterator.
-    FlatArrayMapIterator(const non_const_self& I)
-      : TheBucket(I.TheBucket) {}
-
-    bool operator==(const const_self &RHS) const {
-      return TheBucket->first == RHS.TheBucket->first;
-    }
-    bool operator!=(const const_self &RHS) const {
-      return TheBucket->first != RHS.TheBucket->first;
-    }
-
-    reference operator*() const {
-      return *TheBucket;
-    }
-
-    pointer operator->() const {
-      return TheBucket;
-    }
-
-    inline self& operator++() {   // Preincrement
-      ++TheBucket;
-      return *this;
-    }
-
-    self operator++(int) {        // Postincrement
-      FlatArrayMapIterator tmp = *this; ++*this; return tmp;
-    }
-  };
-}
-
-#endif /* FLATARRAYMAP_H_ */
diff --git a/include/llvm/ADT/MultiImplMap.h b/include/llvm/ADT/MultiImplMap.h
deleted file mode 100644
index da453aa..0000000
--- a/include/llvm/ADT/MultiImplMap.h
+++ /dev/null
@@ -1,550 +0,0 @@
-//===- llvm/ADT/MultiImplMap.h - 'Normally small' pointer set ----*- C++ -*-==//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the MultiImplMap class.
-// MultiImplMap presents map container interface.
-// It has two modes, one for small amount of elements and one for big amount.
-// User should set map implementation for both of them. User also should
-// set the maximum possible number of elements for small mode.
-// If user want to use MultiImplMap instead of DenseMap, he should pass
-// DenseMapCompatible = true. Note that in this case map implementations should
-// present additional DenseMap specific methods (see below).
-// Initially MultiImplMap uses small mode and small map implementation.
-// It triggered to the big mode when number of contained elements exceeds
-// maximum possible elements for small mode.
-//
-// Types that should be defined in nested map class:
-//
-//    key_type;
-//    mapped_type;
-//    value_type; // std::pair<key_type, mapped_type>
-//                // or std::pair<const key_type, mapped_type>
-//    iterator;
-//    const_iterator;
-//
-// Map implementation should provide the next interface:
-//
-//    // Constructors
-//    (default constructor)
-//    (copy constructor)
-//
-//    // Size
-//    unsigned size() const;
-//    bool empty() const;
-//
-//    // Iterators
-//    iterator begin();
-//    const_iterator begin();
-//    iterator end();
-//    const_iterator end();
-//
-//    // Modifiers
-//    void clear();
-//    std::pair<iterator, bool> insert(const value_type& KV);
-//    template <typename IterT>
-//      void insert(IterT I, IterT E);
-//    void erase(key_type K);
-//    void erase(iterator i);
-//    void swap(MultiImplMap& rhs);
-//
-//    // Search operations
-//    iterator find(const key_type& K);
-//    const_iterator find(const key_type& K) const;
-//    bool count(const key_type& K) const;
-//    mapped_type &operator[](const key_type &Key);
-//
-//    // Other operations
-//    self& operator=(const self& other);
-//
-//    // If DenseMapCompatible == true, you also should present next methods.
-//    // See DenseMap comments for more details about its behavior.
-//    bool isPointerIntoBucketsArray(const void *Ptr) const;
-//    const void *getPointerIntoBucketsArray() const;
-//    value_type& FindAndConstruct(const key_type &Key);
-//
-// The list of methods that should be implemented in nested map iterator class:
-//
-//    (conversion constructor from non-constant iterator)
-//
-//    bool operator==(const const_iterator& rhs) const;
-//    bool operator!=(const const_iterator& rhs) const;
-//    reference operator*() const;
-//    pointer operator->() const;
-//    inline self& operator++();
-//
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef MULTIIMPLEMENTATIONMAP_H_
-#define MULTIIMPLEMENTATIONMAP_H_
-
-
-#include <algorithm>
-#include <utility>
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/FlatArrayMap.h"
-#include "llvm/Support/type_traits.h"
-
-namespace llvm {
-
-  template<class SmallMapTy, class BigMapTy, bool IsConst = false>
-  class MultiImplMapIterator;
-
-  template<class SmallMapTy, class BigMapTy>
-    struct MultiImplMapIteratorsFactory;
-
-  template<class SmallMapTy, class BigMapTy>
-  struct MultiImplMapTypes {
-    typedef typename SmallMapTy::key_type key_type;
-    typedef typename SmallMapTy::mapped_type mapped_type;
-    typedef typename std::pair<key_type, mapped_type> value_type;
-  };
-
-  //===--------------------------------------------------------------------===//
-  /// MultiImplMap is map that has two modes, one for small amount of
-  /// elements and one for big amount.
-  /// User should set map implementation for both of them. User also should
-  /// set the maximum possible number of elements for small mode.
-  /// If user want to use MultiImplMap instead of DenseMap, he should pass
-  /// DenseMapCompatible = true.
-  /// Initially MultiImplMap uses small mode and small map implementation.
-  /// It triggered to the big mode when number of contained elements exceeds
-  /// maximum possible elements for small mode.
-  template<class SmallMapTy, class BigMapTy, unsigned MaxSmallN,
-           bool DenseMapCompatible = false,
-           class ItFactory =
-               MultiImplMapIteratorsFactory<SmallMapTy, BigMapTy> >
-  class MultiImplMap {
-
-  protected:
-    SmallMapTy SmallMap;
-    BigMapTy BigMap;
-    bool UseSmall;
-    enum { MaxSmallSize = MaxSmallN };
-
-  public:
-    typedef MultiImplMapTypes<SmallMapTy, BigMapTy> Types;
-
-    typedef typename Types::key_type key_type;
-    typedef typename Types::mapped_type mapped_type;
-    typedef typename Types::value_type value_type;
-
-    typedef typename ItFactory::iterator iterator;
-    typedef typename ItFactory::const_iterator const_iterator;
-
-    typedef std::pair<iterator, bool> ins_res;
-
-    typedef typename std::pair<typename SmallMapTy::iterator, bool>
-      small_ins_res;
-
-    typedef typename std::pair<typename BigMapTy::iterator, bool>
-      big_ins_res;
-
-    typedef MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN> self;
-
-    MultiImplMap() : UseSmall(true) {}
-
-    MultiImplMap(const self& other) {
-      if (other.UseSmall) {
-        SmallMap = other.SmallMap;
-        UseSmall = true;
-      } else {
-        if (other.size() <= MaxSmallN) {
-          SmallMap.insert(other.BigMap.begin(), other.BigMap.end());
-          UseSmall = true;
-        } else {
-          BigMap = other.BigMap;
-          UseSmall = false;
-        }
-      }
-    }
-
-    // Size
-
-    unsigned size() const {
-      if (UseSmall)
-        return SmallMap.size();
-      return BigMap.size();
-    }
-
-    bool empty() const {
-      if (UseSmall)
-        return SmallMap.empty();
-      return BigMap.empty();
-    }
-
-    // Iterators
-
-    iterator begin() {
-      if (UseSmall)
-        return ItFactory::begin(SmallMap);
-      return ItFactory::begin(BigMap);
-    }
-    const_iterator begin() const {
-      if (UseSmall)
-        return ItFactory::begin(SmallMap);
-      return ItFactory::begin(BigMap);
-    }
-
-    iterator end() {
-      if (UseSmall)
-        return ItFactory::end(SmallMap);
-      return ItFactory::end(BigMap);
-    }
-    const_iterator end() const {
-      if (UseSmall)
-        return ItFactory::end(SmallMap);
-      return ItFactory::end(BigMap);
-    }
-
-    // Modifiers
-
-    void clear() {
-      if (UseSmall)
-        SmallMap.clear();
-      else
-        BigMap.clear();
-    }
-
-    std::pair<iterator, bool> insert(const value_type& KV) {
-      if (UseSmall) {
-        if (SmallMap.size() < MaxSmallSize) {
-          small_ins_res Res = SmallMap.insert(KV);
-          return std::make_pair(ItFactory::it(SmallMap, Res.first), Res.second);
-        }
-
-        // Move all to big map.
-        BigMap.insert(SmallMap.begin(), SmallMap.end());
-        SmallMap.clear();
-
-        UseSmall = false;
-      }
-      big_ins_res Res = BigMap.insert(KV);
-      return std::make_pair(ItFactory::it(BigMap, Res.first), Res.second);
-    }
-
-    template <typename OtherValTy>
-    std::pair<iterator, bool> insert(const OtherValTy& OtherKV) {
-      const value_type* KV = reinterpret_cast<const value_type*>(
-          reinterpret_cast<const void*>(OtherKV));
-      return insert(*KV);
-    }
-
-    template <typename IterT>
-    void insert(IterT I, IterT E) {
-      for (; I != E; ++I)
-        insert(*I);
-    }
-
-    void erase(key_type K) {
-      if (UseSmall)
-        SmallMap.erase(K);
-      else
-        BigMap.erase(K);
-    }
-
-    void erase(iterator i) {
-      erase(i->first);
-    }
-
-    void swap(MultiImplMap& rhs) {
-      SmallMap.swap(rhs.SmallMap);
-      BigMap.swap(rhs.BigMap);
-      std::swap(UseSmall, rhs.UseSmall);
-    }
-
-    // Search operations
-
-    iterator find(const key_type& K) {
-      if (UseSmall)
-        return ItFactory::it(SmallMap, SmallMap.find(K));
-      return ItFactory::it(BigMap, BigMap.find(K));
-    }
-
-    const_iterator find(const key_type& K) const {
-      if (UseSmall)
-        return ItFactory::const_it(SmallMap, SmallMap.find(K));
-      return ItFactory::const_it(BigMap, BigMap.find(K));
-    }
-
-    bool count(const key_type& K) const {
-      return find(K) != end();
-    }
-
-    mapped_type &operator[](const key_type &Key) {
-      ins_res res = insert(std::make_pair(Key, mapped_type()));
-      return res.first->second;
-    }
-
-    // Other operations
-
-    self& operator=(const self& other) {
-      if (other.isSmall()) {
-        SmallMap = other.SmallMap;
-        if (!UseSmall) {
-          BigMap.clear();
-          UseSmall = true;
-        }
-        return *this;
-      }
-      if (UseSmall) {
-        SmallMap.clear();
-        UseSmall = false;
-      }
-      BigMap = other.BigMap;
-      return *this;
-    }
-
-    // Utilities
-
-    bool isSmall()const {
-      return UseSmall;
-    }
-
-    SmallMapTy& getSmallMap() {
-      return SmallMap;
-    }
-
-    const SmallMapTy& getSmallMap() const {
-      return SmallMap;
-    }
-
-    BigMapTy& getBigMap() {
-      return BigMap;
-    }
-
-    const BigMapTy& getBigMap() const {
-      return BigMap;
-    }
-  };
-
-  template<class SmallMapTy, class BigMapTy, unsigned MaxSmallN>
-  class MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, true> :
-        public MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, false>
-  {
-  public:
-    typedef MultiImplMap<SmallMapTy, BigMapTy, MaxSmallN, false> ParentTy;
-    typedef typename ParentTy::Types Types;
-
-    typedef typename Types::key_type key_type;
-    typedef typename Types::mapped_type mapped_type;
-    typedef typename Types::value_type value_type;
-    typedef typename ParentTy::iterator iterator;
-
-    /// isPointerIntoBucketsArray - Return true if the specified pointer points
-    /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
-    /// value).
-    bool isPointerIntoBucketsArray(const void *Ptr) const {
-      if (this->UseSmall)
-        return this->SmallMap.isPointerIntoBucketsArray(Ptr);
-      return this->BigMap.isPointerIntoBucketsArray(Ptr);
-    }
-
-    /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
-    /// array.  In conjunction with the previous method, this can be used to
-    /// determine whether an insertion caused the map to reallocate data.
-    const void *getPointerIntoBucketsArray() const {
-      if (this->UseSmall)
-        return this->SmallMap.getPointerIntoBucketsArray();
-      return this->BigMap.getPointerIntoBucketsArray();
-    }
-
-    value_type& FindAndConstruct(const key_type &Key) {
-      std::pair<iterator, bool> Res =
-          this->insert(std::make_pair(Key, mapped_type()));
-      return *Res.first;
-    }
-  };
-
-  template<class SmallMapTy, class BigMapTy, bool IsConst>
-  class MultiImplMapIterator {
-  public:
-
-    typedef MultiImplMapTypes<SmallMapTy, BigMapTy> Types;
-
-    typedef typename Types::mapped_type mapped_type;
-
-    typedef typename conditional<IsConst,
-                                 const typename Types::value_type,
-                                 typename Types::value_type>::type value_type;
-
-    typedef typename conditional<IsConst,
-                                 typename SmallMapTy::const_iterator,
-                                 typename SmallMapTy::iterator>::type
-                                 small_iterator;
-
-    typedef typename conditional<IsConst,
-                                 typename BigMapTy::const_iterator,
-                                 typename BigMapTy::iterator>::type
-                                 big_iterator;
-
-    typedef typename conditional<IsConst, const void*, void*>::type void_ptr_ty;
-
-    typedef value_type *pointer;
-    typedef value_type &reference;
-
-    typedef MultiImplMapIterator<SmallMapTy, BigMapTy, IsConst> self;
-
-    typedef MultiImplMapIterator<SmallMapTy, BigMapTy, false> non_const_self;
-    typedef MultiImplMapIterator<SmallMapTy, BigMapTy, true> const_self;
-
-    friend class MultiImplMapIterator<SmallMapTy, BigMapTy, true>;
-    friend class MultiImplMapIterator<SmallMapTy, BigMapTy, false>;
-
-  protected:
-
-    template <typename OtherValTy>
-    static value_type* toValueTypePtr(OtherValTy& ValTyRef) {
-      return reinterpret_cast<value_type*>(
-               reinterpret_cast<void_ptr_ty>(&ValTyRef));
-    }
-
-    template <typename OtherValTy>
-    static value_type& toValueTypeRef(OtherValTy& ValTyRef) {
-      return *reinterpret_cast<value_type*>(
-                reinterpret_cast<void_ptr_ty>(&ValTyRef));
-    }
-
-    small_iterator SmallIt;
-    big_iterator BigIt;
-    bool UseSmall;
-
-  public:
-
-    MultiImplMapIterator() : UseSmall(true) {}
-    MultiImplMapIterator(small_iterator It) : SmallIt(It), UseSmall(true) {}
-    MultiImplMapIterator(big_iterator It) : BigIt(It), UseSmall(false) {}
-    MultiImplMapIterator(const non_const_self& src) :
-      SmallIt(src.SmallIt), BigIt(src.BigIt), UseSmall(src.UseSmall) {}
-
-    bool operator==(const const_self& rhs) const {
-      if (UseSmall != rhs.UseSmall)
-        return false;
-      if (UseSmall)
-        return SmallIt == rhs.SmallIt;
-      return BigIt == rhs.BigIt;
-    }
-
-    bool operator!=(const const_self& rhs) const {
-      if (UseSmall != rhs.UseSmall)
-        return true;
-      if (UseSmall)
-        return SmallIt != rhs.SmallIt;
-      return BigIt != rhs.BigIt;
-    }
-
-    reference operator*() const {
-      return UseSmall ? toValueTypeRef(*SmallIt) : toValueTypeRef(*BigIt);;
-    }
-
-    pointer operator->() const {
-      return UseSmall ? toValueTypePtr(*SmallIt) : toValueTypePtr(*BigIt);
-    }
-
-    // Preincrement
-    inline self& operator++() {
-      if (UseSmall) ++SmallIt;
-      return *this;
-    }
-
-    // Postincrement
-    self operator++(int) {
-      self tmp = *this; ++*this; return tmp;
-    }
-  };
-
-  template<class SmallMapTy, class BigMapTy>
-  struct MultiImplMapIteratorsFactory {
-
-    typedef MultiImplMapIterator<SmallMapTy, BigMapTy, false> iterator;
-    typedef MultiImplMapIterator<SmallMapTy, BigMapTy, true> const_iterator;
-
-    template<class MapImpl, class ItTy>
-    static iterator it(MapImpl& impl, ItTy it) {
-      return iterator(it);
-    }
-    template<class MapImpl, class ConstItTy>
-    static const_iterator const_it(const MapImpl& impl, ConstItTy it) {
-      return const_iterator(it);
-    }
-    template<class MapImpl>
-    static iterator begin(MapImpl& impl) {
-      return iterator(impl.begin());
-    }
-    template<class MapImpl>
-    static const_iterator begin(const MapImpl& impl) {
-      return const_iterator(impl.begin());
-    }
-    template<class MapImpl>
-    static iterator end(MapImpl& impl) {
-      return iterator(impl.end());
-    }
-    template<class MapImpl>
-    static const_iterator end(const MapImpl& impl) {
-      return const_iterator(impl.end());
-    }
-  };
-
-  template<typename KeyTy, typename MappedTy, unsigned MaxArraySize,
-            typename KeyInfoT>
-  struct MultiImplMapIteratorsFactory<
-          FlatArrayMap<KeyTy, MappedTy, MaxArraySize>,
-          DenseMap<KeyTy, MappedTy, KeyInfoT> >
-  {
-
-    typedef FlatArrayMap<KeyTy, MappedTy, MaxArraySize> SmallMapTy;
-    typedef DenseMap<KeyTy, MappedTy, KeyInfoT> BigMapTy;
-
-    typedef DenseMapIterator<KeyTy, MappedTy, KeyInfoT, false>
-      iterator;
-    typedef DenseMapIterator<KeyTy, MappedTy, KeyInfoT, true>
-      const_iterator;
-
-    static iterator it(SmallMapTy& impl, typename SmallMapTy::iterator it) {
-      return iterator(&(*it), &(*impl.end()));
-    }
-    static const_iterator const_it(
-        const SmallMapTy& impl, typename SmallMapTy::const_iterator it) {
-      return const_iterator(&(*it), &(*impl.end()));
-    }
-    static iterator it(BigMapTy& impl, typename BigMapTy::iterator it) {
-      return it;
-    }
-    static const_iterator const_it(
-        const BigMapTy& impl, typename BigMapTy::const_iterator it) {
-      return it;
-    }
-    static iterator begin(SmallMapTy& impl) {
-      return it(impl, impl.begin());
-    }
-    static const_iterator begin(const SmallMapTy& impl) {
-      return it(impl, impl.begin());
-    }
-    static iterator begin(BigMapTy& impl) {
-      return impl.begin();
-    }
-    static const_iterator begin(const BigMapTy& impl) {
-      return impl.begin();
-    }
-    static iterator end(SmallMapTy& impl) {
-      return it(impl, impl.end());
-    }
-    static const_iterator end(const SmallMapTy& impl) {
-      return const_it(impl, impl.end());
-    }
-    static iterator end(BigMapTy& impl) {
-      return impl.end();
-    }
-    static const_iterator end(const BigMapTy& impl) {
-      return impl.end();
-    }
-  };
-}
-
-#endif /* MULTIIMPLEMENTATIONMAP_H_ */
diff --git a/include/llvm/ADT/SmallMap.h b/include/llvm/ADT/SmallMap.h
deleted file mode 100644
index 42d27ce..0000000
--- a/include/llvm/ADT/SmallMap.h
+++ /dev/null
@@ -1,37 +0,0 @@
-//===- llvm/ADT/SmallMap.h - 'Normally small' pointer set -------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the SmallMap class.
-// SmallMap is DenseMap compatible MultiImplMap.
-// It uses FlatArrayMap for small mode, and DenseMap for big mode.
-// See MultiMapImpl comments for more details on the algorithm is used.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef SMALLPTRMAP_H_
-#define SMALLPTRMAP_H_
-
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/FlatArrayMap.h"
-#include "llvm/ADT/MultiImplMap.h"
-
-namespace llvm {
-
-  //===--------------------------------------------------------------------===//
-  /// SmallMap is wrapper around MultiImplMap. It uses FlatArrayMap for
-  /// small mode, and DenseMap for big mode.
-  template <typename KeyTy, typename MappedTy, unsigned N = 16>
-  class SmallMap : public MultiImplMap<
-                        FlatArrayMap<KeyTy, MappedTy, N>,
-                        DenseMap<KeyTy, MappedTy>,
-                        N, true> {
-  };
-}
-
-#endif /* SMALLPTRMAP_H_ */