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

1 files changed, 20 insertions, 2 deletions

diff --git a/lib/IR/Attributes.cpp b/lib/IR/Attributes.cpp
index 894ff7d..c483467 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);