Use a sorted array to store the information about a few address spaces.

We don't have any test with more than 6 address spaces, so a DenseMap is
probably not the correct answer.

An unsorted array would also be OK, but we have to sort it for printing anyway.

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

2 files changed, 44 insertions, 33 deletions

diff --git a/include/llvm/IR/DataLayout.h b/include/llvm/IR/DataLayout.h
index 8a162430f7..e26dd026bd 100644
--- a/include/llvm/IR/DataLayout.h
+++ b/include/llvm/IR/DataLayout.h
@@ -115,7 +115,14 @@ private:
   /// pointers vs. 64-bit pointers by extending LayoutAlignment, but for now,
   /// we don't.
   SmallVector<LayoutAlignElem, 16> Alignments;
-  DenseMap<unsigned, PointerAlignElem> Pointers;
+  typedef SmallVector<PointerAlignElem, 8> PointersTy;
+  PointersTy Pointers;
+
+  PointersTy::const_iterator findPoiterLowerBound(uint32_t AddressSpace) const {
+    return const_cast<DataLayout *>(this)->findPoiterLowerBound(AddressSpace);
+  }
+
+  PointersTy::iterator findPoiterLowerBound(uint32_t AddressSpace);
 
   /// InvalidAlignmentElem - This member is a signal that a requested alignment
   /// type and bit width were not found in the SmallVector.
diff --git a/lib/IR/DataLayout.cpp b/lib/IR/DataLayout.cpp
index ed7c12fc9d..7089b7b85f 100644
--- a/lib/IR/DataLayout.cpp
+++ b/lib/IR/DataLayout.cpp
@@ -374,18 +374,29 @@ DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
                                             pref_align, bit_width));
 }
 
+static bool comparePointerAlignElem(const PointerAlignElem &A,
+                                    uint32_t AddressSpace) {
+  return A.AddressSpace < AddressSpace;
+}
+
+DataLayout::PointersTy::iterator
+DataLayout::findPoiterLowerBound(uint32_t AddressSpace) {
+  return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
+                          comparePointerAlignElem);
+}
+
 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
                                      unsigned PrefAlign,
                                      uint32_t TypeByteWidth) {
   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
-  DenseMap<unsigned,PointerAlignElem>::iterator val = Pointers.find(AddrSpace);
-  if (val == Pointers.end()) {
-    Pointers[AddrSpace] =
-        PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign, TypeByteWidth);
+  PointersTy::iterator I = findPoiterLowerBound(AddrSpace);
+  if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
+    Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
+                                             TypeByteWidth));
   } else {
-    val->second.ABIAlign = ABIAlign;
-    val->second.PrefAlign = PrefAlign;
-    val->second.TypeByteWidth = TypeByteWidth;
+    I->ABIAlign = ABIAlign;
+    I->PrefAlign = PrefAlign;
+    I->TypeByteWidth = TypeByteWidth;
   }
 }
 
@@ -529,19 +540,9 @@ std::string DataLayout::getStringRepresentation() const {
     break;
   }
 
-  SmallVector<unsigned, 8> addrSpaces;
-  // Lets get all of the known address spaces and sort them
-  // into increasing order so that we can emit the string
-  // in a cleaner format.
-  for (DenseMap<unsigned, PointerAlignElem>::const_iterator
-      pib = Pointers.begin(), pie = Pointers.end();
-      pib != pie; ++pib) {
-    addrSpaces.push_back(pib->first);
-  }
-  std::sort(addrSpaces.begin(), addrSpaces.end());
-  for (SmallVectorImpl<unsigned>::iterator asb = addrSpaces.begin(),
-      ase = addrSpaces.end(); asb != ase; ++asb) {
-    const PointerAlignElem &PI = Pointers.find(*asb)->second;
+  for (PointersTy::const_iterator I = Pointers.begin(), E = Pointers.end();
+       I != E; ++I) {
+    const PointerAlignElem &PI = *I;
 
     // Skip default.
     if (PI.AddressSpace == 0 && PI.ABIAlign == 8 && PI.PrefAlign == 8 &&
@@ -586,27 +587,30 @@ std::string DataLayout::getStringRepresentation() const {
 }
 
 unsigned DataLayout::getPointerABIAlignment(unsigned AS) const {
-  DenseMap<unsigned, PointerAlignElem>::const_iterator val = Pointers.find(AS);
-  if (val == Pointers.end()) {
-    val = Pointers.find(0);
+  PointersTy::const_iterator I = findPoiterLowerBound(AS);
+  if (I == Pointers.end() || I->AddressSpace != AS) {
+    I = findPoiterLowerBound(0);
+    assert(I->AddressSpace == 0);
   }
-  return val->second.ABIAlign;
+  return I->ABIAlign;
 }
 
 unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const {
-  DenseMap<unsigned, PointerAlignElem>::const_iterator val = Pointers.find(AS);
-  if (val == Pointers.end()) {
-    val = Pointers.find(0);
+  PointersTy::const_iterator I = findPoiterLowerBound(AS);
+  if (I == Pointers.end() || I->AddressSpace != AS) {
+    I = findPoiterLowerBound(0);
+    assert(I->AddressSpace == 0);
   }
-  return val->second.PrefAlign;
+  return I->PrefAlign;
 }
 
 unsigned DataLayout::getPointerSize(unsigned AS) const {
-  DenseMap<unsigned, PointerAlignElem>::const_iterator val = Pointers.find(AS);
-  if (val == Pointers.end()) {
-    val = Pointers.find(0);
+  PointersTy::const_iterator I = findPoiterLowerBound(AS);
+  if (I == Pointers.end() || I->AddressSpace != AS) {
+    I = findPoiterLowerBound(0);
+    assert(I->AddressSpace == 0);
   }
-  return val->second.TypeByteWidth;
+  return I->TypeByteWidth;
 }
 
 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {