[IR] Use a binary search in DataLayout::getAlignmentInfo

[craig.topper]

Summary

We currently do a linear scan through all of the Alignments array entries anytime getAlignmentInfo is called. I noticed while profiling compile time on a -O2 opt run that this function can be called quite frequently and was showing about as about 1% of the time in callgrind.

This patch puts the Alignments array into a sorted order by type and then by bitwidth. We can then do a binary search. And use the sorted nature to handle the special cases for INTEGER_ALIGN. Some of this is modeled after the sorting/searching we do for pointers already.

This reduced the time spent in this routine by about 2/3 in the one compilation I was looking at.

We could maybe improve this more by using a DenseMap to cache the results, but just sorting was easy and didn't require extra data structure. And I think it made the integer handling simpler.

[arsenm]

LGTM

[mehdi_amini]

It is not clear to me why an associative container instead of a vector wouldn't be even easier to use?

include/llvm/IR/DataLayout.h

123 ↗

(On Diff #92590)

Document that it is sorted by construction.

lib/IR/DataLayout.cpp

443 ↗

(On Diff #92590)

Here as well: a reference to the fact that we insert in the right position to keep the vector sorted.

[davide]

lg, thanks for the fix.

llvm/trunk/include/llvm/IR/DataLayout.h

enum ManglingModeT {
     MM_WinCOFF,
     MM_WinCOFFX86,
     MM_Mips
   };
   ManglingModeT ManglingMode;
 
   SmallVector<unsigned char, 8> LegalIntWidths;
 
-  /// \brief Primitive type alignment data.
-  SmallVector<LayoutAlignElem, 16> Alignments;
+  /// \brief Primitive type alignment data. This is sorted by type and bit
+  /// width during construction.
+  typedef SmallVector<LayoutAlignElem, 16> AlignmentsTy;
+  AlignmentsTy Alignments;
+
+  AlignmentsTy::const_iterator
+  findAlignmentLowerBound(AlignTypeEnum AlignType, uint32_t BitWidth) const {
+    return const_cast<DataLayout *>(this)->findAlignmentLowerBound(AlignType,
+                                                                   BitWidth);
+  }
+
+  AlignmentsTy::iterator
+  findAlignmentLowerBound(AlignTypeEnum AlignType, uint32_t BitWidth);
 
   /// \brief The string representation used to create this DataLayout
   std::string StringRepresentation;
 
   typedef SmallVector<PointerAlignElem, 8> PointersTy;
   PointersTy Pointers;
 
   PointersTy::const_iterator

llvm/trunk/lib/IR/DataLayout.cpp

bool Ret = BigEndian == Other.BigEndian &&
              StackNaturalAlign == Other.StackNaturalAlign &&
              ManglingMode == Other.ManglingMode &&
              LegalIntWidths == Other.LegalIntWidths &&
              Alignments == Other.Alignments && Pointers == Other.Pointers;
   // Note: getStringRepresentation() might differs, it is not canonicalized
   return Ret;
 }
 
+DataLayout::AlignmentsTy::iterator
+DataLayout::findAlignmentLowerBound(AlignTypeEnum AlignType,
+                                    uint32_t BitWidth) {
+  auto Pair = std::make_pair((unsigned)AlignType, BitWidth);
+  return std::lower_bound(Alignments.begin(), Alignments.end(), Pair,
+                          [](const LayoutAlignElem &LHS,
+                             const std::pair<unsigned, uint32_t> &RHS) {
+                            return std::tie(LHS.AlignType, LHS.TypeBitWidth) <
+                                   std::tie(RHS.first, RHS.second);
+                          });
+}
+
 void
 DataLayout::setAlignment(AlignTypeEnum align_type, unsigned abi_align,
                          unsigned pref_align, uint32_t bit_width) {
   if (!isUInt<24>(bit_width))
     report_fatal_error("Invalid bit width, must be a 24bit integer");
   if (!isUInt<16>(abi_align))
     report_fatal_error("Invalid ABI alignment, must be a 16bit integer");
   if (!isUInt<16>(pref_align))
     report_fatal_error("Invalid preferred alignment, must be a 16bit integer");
   if (abi_align != 0 && !isPowerOf2_64(abi_align))
     report_fatal_error("Invalid ABI alignment, must be a power of 2");
   if (pref_align != 0 && !isPowerOf2_64(pref_align))
     report_fatal_error("Invalid preferred alignment, must be a power of 2");
 
   if (pref_align < abi_align)
     report_fatal_error(
         "Preferred alignment cannot be less than the ABI alignment");
 
-  for (LayoutAlignElem &Elem : Alignments) {
-    if (Elem.AlignType == (unsigned)align_type &&
-        Elem.TypeBitWidth == bit_width) {
-      // Update the abi, preferred alignments.
-      Elem.ABIAlign = abi_align;
-      Elem.PrefAlign = pref_align;
-      return;
-    }
-  }
-
-  Alignments.push_back(LayoutAlignElem::get(align_type, abi_align,
+  AlignmentsTy::iterator I = findAlignmentLowerBound(align_type, bit_width);
+  if (I != Alignments.end() &&
+      I->AlignType == (unsigned)align_type && I->TypeBitWidth == bit_width) {
+    I->ABIAlign = abi_align;
+    I->PrefAlign = pref_align;
+  } else {
+    // Insert before I to keep the vector sorted.
+    Alignments.insert(I, LayoutAlignElem::get(align_type, abi_align,
                                               pref_align, bit_width));
   }
+}
 
 DataLayout::PointersTy::iterator
 DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
     return A.AddressSpace < AddressSpace;
   });
 }
void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
   }
 }
 
 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
                                       uint32_t BitWidth, bool ABIInfo,
                                       Type *Ty) const {
-  // Check to see if we have an exact match and remember the best match we see.
-  int BestMatchIdx = -1;
-  int LargestInt = -1;
-  for (unsigned i = 0, e = Alignments.size(); i != e; ++i) {
-    if (Alignments[i].AlignType == (unsigned)AlignType &&
-        Alignments[i].TypeBitWidth == BitWidth)
-      return ABIInfo ? Alignments[i].ABIAlign : Alignments[i].PrefAlign;
-
-    // The best match so far depends on what we're looking for.
-    if (AlignType == INTEGER_ALIGN &&
-        Alignments[i].AlignType == INTEGER_ALIGN) {
-      // The "best match" for integers is the smallest size that is larger than
-      // the BitWidth requested.
-      if (Alignments[i].TypeBitWidth > BitWidth && (BestMatchIdx == -1 ||
-          Alignments[i].TypeBitWidth < Alignments[BestMatchIdx].TypeBitWidth))
-        BestMatchIdx = i;
-      // However, if there isn't one that's larger, then we must use the
-      // largest one we have (see below)
-      if (LargestInt == -1 ||
-          Alignments[i].TypeBitWidth > Alignments[LargestInt].TypeBitWidth)
-        LargestInt = i;
-    }
-  }
+  AlignmentsTy::const_iterator I = findAlignmentLowerBound(AlignType, BitWidth);
+  // See if we found an exact match. Of if we are looking for an integer type,
+  // but don't have an exact match take the next largest integer. This is where
+  // the lower_bound will point to when it fails an exact match.
+  if (I != Alignments.end() && I->AlignType == (unsigned)AlignType &&
+      (I->TypeBitWidth == BitWidth || AlignType == INTEGER_ALIGN))
+    return ABIInfo ? I->ABIAlign : I->PrefAlign;
 
-  // Okay, we didn't find an exact solution.  Fall back here depending on what
-  // is being looked for.
-  if (BestMatchIdx == -1) {
-    // If we didn't find an integer alignment, fall back on most conservative.
-    if (AlignType == INTEGER_ALIGN) {
-      BestMatchIdx = LargestInt;
-    } else if (AlignType == VECTOR_ALIGN) {
-      // By default, use natural alignment for vector types. This is consistent
-      // with what clang and llvm-gcc do.
-      unsigned Align = getTypeAllocSize(cast<VectorType>(Ty)->getElementType());
-      Align *= cast<VectorType>(Ty)->getNumElements();
-      Align = PowerOf2Ceil(Align);
-      return Align;
-    }
-  }
+    // If we didn't have a larger value try the largest value we have.
+    if (I != Alignments.begin()) {
+      --I; // Go to the previous entry and see if its an integer.
+      if (I->AlignType == INTEGER_ALIGN)
+        return ABIInfo ? I->ABIAlign : I->PrefAlign;
+    }
 
   // If we still couldn't find a reasonable default alignment, fall back
   // to a simple heuristic that the alignment is the first power of two
   // greater-or-equal to the store size of the type.  This is a reasonable
   // approximation of reality, and if the user wanted something less
   // less conservative, they should have specified it explicitly in the data
   // layout.
-  if (BestMatchIdx == -1) {
-    unsigned Align = getTypeStoreSize(Ty);
-    Align = PowerOf2Ceil(Align);
-    return Align;
-  }
 
-  // Since we got a "best match" index, just return it.
-  return ABIInfo ? Alignments[BestMatchIdx].ABIAlign
-                 : Alignments[BestMatchIdx].PrefAlign;
-}
-
 namespace {
 
 class StructLayoutMap {
   typedef DenseMap<StructType*, StructLayout*> LayoutInfoTy;
   LayoutInfoTy LayoutInfo;
 
 public:
   ~StructLayoutMap() {