From 7bba9c5c0a5235f585ee4bd3efec29e0982de3f8 Mon Sep 17 00:00:00 2001 From: Peter Collingbourne Date: Fri, 2 Aug 2013 22:29:40 +0000 Subject: [PATCH] Make one of the AttributeSet ctors maintain the invariant that the attribute list is ordered by index. Differential Revision: http://llvm-reviews.chandlerc.com/D1265 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187682 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/IR/AttributeImpl.h | 9 +++++++++ lib/IR/Attributes.cpp | 22 ++++++++++++++++++++-- unittests/IR/AttributesTest.cpp | 13 +++++++++++++ 3 files changed, 42 insertions(+), 2 deletions(-) diff --git a/lib/IR/AttributeImpl.h b/lib/IR/AttributeImpl.h index 5a72c37505e..7bf9e8ab6ba 100644 --- a/lib/IR/AttributeImpl.h +++ b/lib/IR/AttributeImpl.h @@ -200,6 +200,15 @@ public: AttributeSetImpl(LLVMContext &C, ArrayRef > Attrs) : Context(C), NumAttrs(Attrs.size()) { +#ifndef NDEBUG + if (Attrs.size() >= 2) { + for (const std::pair *i = Attrs.begin() + 1, + *e = Attrs.end(); + i != e; ++i) { + assert((i-1)->first <= i->first && "Attribute set not ordered!"); + } + } +#endif // There's memory after the node where we can store the entries in. std::copy(Attrs.begin(), Attrs.end(), reinterpret_cast(this + 1)); diff --git a/lib/IR/Attributes.cpp b/lib/IR/Attributes.cpp index 894ff7dda1f..c4834671ac6 100644 --- a/lib/IR/Attributes.cpp +++ b/lib/IR/Attributes.cpp @@ -621,12 +621,30 @@ AttributeSet AttributeSet::get(LLVMContext &C, unsigned Index, AttributeSet AttributeSet::get(LLVMContext &C, ArrayRef Attrs) { if (Attrs.empty()) return AttributeSet(); + if (Attrs.size() == 1) return Attrs[0]; SmallVector, 8> AttrNodeVec; - for (unsigned I = 0, E = Attrs.size(); I != E; ++I) { + AttributeSetImpl *A0 = Attrs[0].pImpl; + if (A0) + AttrNodeVec.append(A0->getNode(0), A0->getNode(A0->getNumAttributes())); + // Copy all attributes from Attrs into AttrNodeVec while keeping AttrNodeVec + // ordered by index. Because we know that each list in Attrs is ordered by + // index we only need to merge each successive list in rather than doing a + // full sort. + for (unsigned I = 1, E = Attrs.size(); I != E; ++I) { AttributeSetImpl *AS = Attrs[I].pImpl; if (!AS) continue; - AttrNodeVec.append(AS->getNode(0), AS->getNode(AS->getNumAttributes())); + SmallVector, 8>::iterator + ANVI = AttrNodeVec.begin(), ANVE; + for (const AttributeSetImpl::IndexAttrPair + *AI = AS->getNode(0), + *AE = AS->getNode(AS->getNumAttributes()); + AI != AE; ++AI) { + ANVE = AttrNodeVec.end(); + while (ANVI != ANVE && ANVI->first <= AI->first) + ++ANVI; + ANVI = AttrNodeVec.insert(ANVI, *AI) + 1; + } } return getImpl(C, AttrNodeVec); diff --git a/unittests/IR/AttributesTest.cpp b/unittests/IR/AttributesTest.cpp index 2368bdf94dc..ebcb772bc37 100644 --- a/unittests/IR/AttributesTest.cpp +++ b/unittests/IR/AttributesTest.cpp @@ -31,4 +31,17 @@ TEST(Attributes, Uniquing) { EXPECT_EQ(SetA, SetB); } +TEST(Attributes, Ordering) { + LLVMContext C; + + AttributeSet ASs[] = { + AttributeSet::get(C, 2, Attribute::ZExt), + AttributeSet::get(C, 1, Attribute::SExt) + }; + + AttributeSet SetA = AttributeSet::get(C, ASs); + AttributeSet SetB = SetA.removeAttributes(C, 1, ASs[1]); + EXPECT_NE(SetA, SetB); +} + } // end anonymous namespace -- 2.34.1