From 7bba9c5c0a5235f585ee4bd3efec29e0982de3f8 Mon Sep 17 00:00:00 2001
From: Peter Collingbourne <peter@pcc.me.uk>
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<std::pair<unsigned, AttributeSetNode *> > Attrs)
       : Context(C), NumAttrs(Attrs.size()) {
+#ifndef NDEBUG
+    if (Attrs.size() >= 2) {
+      for (const std::pair<unsigned, AttributeSetNode *> *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<IndexAttrPair *>(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<AttributeSet> Attrs) {
   if (Attrs.empty()) return AttributeSet();
+  if (Attrs.size() == 1) return Attrs[0];
 
   SmallVector<std::pair<unsigned, AttributeSetNode*>, 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<std::pair<unsigned, AttributeSetNode *>, 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