diff options
author | Craig Topper <craig.topper@gmail.com> | 2017-03-23 06:15:56 +0000 |
---|---|---|
committer | Craig Topper <craig.topper@gmail.com> | 2017-03-23 06:15:56 +0000 |
commit | ba5e42097673772536f380ab4bf7c3e6bf47c8b2 (patch) | |
tree | a3edf3f7edc706607a1bb0031fa4543a7d413c5f /lib/IR/DataLayout.cpp | |
parent | a3bd80e90a19de9697c378e6fa3946e12ac3e122 (diff) |
[IR] Use a binary search in DataLayout::getAlignmentInfo
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.
Reviewers: sanjoy, davide, majnemer, resistor, arsenm, mehdi_amini
Reviewed By: arsenm
Subscribers: arsenm, llvm-commits
Differential Revision: https://reviews.llvm.org/D31232
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@298579 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/IR/DataLayout.cpp')
-rw-r--r-- | lib/IR/DataLayout.cpp | 105 |
1 files changed, 47 insertions, 58 deletions
diff --git a/lib/IR/DataLayout.cpp b/lib/IR/DataLayout.cpp index 23b2de8df2b..de08f920f09 100644 --- a/lib/IR/DataLayout.cpp +++ b/lib/IR/DataLayout.cpp @@ -402,6 +402,18 @@ bool DataLayout::operator==(const DataLayout &Other) const { 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) { @@ -420,18 +432,17 @@ DataLayout::setAlignment(AlignTypeEnum align_type, unsigned 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; - } + AlignmentsTy::iterator I = findAlignmentLowerBound(align_type, bit_width); + if (I != Alignments.end() && + I->AlignType == (unsigned)align_type && I->TypeBitWidth == bit_width) { + // Update the abi, preferred alignments. + 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)); } - - Alignments.push_back(LayoutAlignElem::get(align_type, abi_align, - pref_align, bit_width)); } DataLayout::PointersTy::iterator @@ -465,45 +476,29 @@ void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign, 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; - } - } - - // 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; + 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; + + if (AlignType == INTEGER_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; } - } + } 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 still couldn't find a reasonable default alignment, fall back // to a simple heuristic that the alignment is the first power of two @@ -511,15 +506,9 @@ unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType, // 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; + unsigned Align = getTypeStoreSize(Ty); + Align = PowerOf2Ceil(Align); + return Align; } namespace { |