[IR] Switch AttributeList to use an array for O(1) access

[rnk]

Summary

Before this change, AttributeLists stored a pair of index and
AttributeSet. This is memory efficient if most arguments do not have
attributes. However, it requires doing a search over the pairs to test
an argument or function attribute. Profiling shows that this loop was
0.76% of the time in 'opt -O2' of sqlite3.c, because LLVM constantly
tests values for nullability.

This was worth about 2.5% of mid-level optimization cycles on the
sqlite3 amalgamation. Here are the full perf results:
https://reviews.llvm.org/P7995

Here are just the before and after cycle counts:

$ perf stat -r 5 ./opt_before -O2 sqlite3.bc -o /dev/null
    13,274,181,184      cycles                    #    3.047 GHz                      ( +-  0.28% )
$ perf stat -r 5 ./opt_after -O2 sqlite3.bc -o /dev/null
    12,906,927,263      cycles                    #    3.043 GHz                      ( +-  0.51% )

This patch *does not* change the indices used to query attributes, as
requested by reviewers. Tracking whether an index is usable for array
indexing is a huge pain that affects many of the internal APIs, so it
would be good to come back later and do a cleanup to remove this
internal adjustment.

[rnk]

rebase

[rnk]

I benchmarked opt on sqlite3.bc, and this was a nice improvement.

I could try to measure memory usage, but I've convinced myself that there should be the exact same number of AttributeLists as their were before.

One question remains: do you think I should completely encapsulate this indexing change by adding 1 inside AttributeList::getAttributes, or is it better to update all the callers as I did in this change? The problem with this change is that it will break out-of-tree backends and frontends that use the APIs with one-based indexing. It won't even be a compile failure because the APIs still take unsigned integers. That's a bit rude without some more hand waving on llvm-dev and release notes.

[javed.absar]

llvm/include/llvm/IR/Attributes.h

287 ↗

(On Diff #98222)

Yes, make the code much neater. Unfortunately, because of legacy stuff, as you mention, adjustments are needed in lot of places. I think encapsulating the index change inside AttributeList might be neater (less pervasive change).

303 ↗

(On Diff #98222)

Should pImpl also have 'private' access-specifier, given getImpl is moved to there?

[rnk]

llvm/include/llvm/IR/Attributes.h

287 ↗

(On Diff #98222)

OK, I'll go ahead and split the changes.

303 ↗

(On Diff #98222)

It is already private.

[rnk]

In D32819#749163, @rnk wrote:

One question remains: do you think I should completely encapsulate this indexing change by adding 1 inside AttributeList::getAttributes, or is it better to update all the callers as I did in this change? The problem with this change is that it will break out-of-tree backends and frontends that use the APIs with one-based indexing. It won't even be a compile failure because the APIs still take unsigned integers. That's a bit rude without some more hand waving on llvm-dev and release notes.

@javed.absar suggested that this was worth it, so I tried it, but I don't like the result. It means this doesn't work anymore:

// Do lookups for all attribute groups.
for (unsigned i = 0, e = PAL.getNumAttrSets(); i != e; ++i) {
  AttributeSet AS = PAL.getAttributes(i);
  if (!AS.hasAttributes())
    continue;
  IndexAndAttrSet Pair = {i, AS};
  unsigned &Entry = AttributeGroupMap[Pair];
  if (Entry == 0) {
    AttributeGroups.push_back(Pair);
    Entry = AttributeGroups.size();
  }
}

We would need to expose something like index_begin() / index_end() / indices() to make it easy to iterate over AttributeList indices. If we need to have a loop over indices, that loop should start at zero. Anything else is surprising.

llvm/include/llvm/IR/Attributes.h

287 ↗

(On Diff #98222)

I tried this and I don't like the result. I'll explain more in a top-level comment.

[tobiasvk]

In D32819#749163, @rnk wrote:

One question remains: do you think I should completely encapsulate this indexing change by adding 1 inside AttributeList::getAttributes, or is it better to update all the callers as I did in this change? The problem with this change is that it will break out-of-tree backends and frontends that use the APIs with one-based indexing. It won't even be a compile failure because the APIs still take unsigned integers. That's a bit rude without some more hand waving on llvm-dev and release notes.

I'm very concerned about breaking out-of-tree code in a way that's not detectable at compile time. We have a whole bunch of out-of-tree passes that will be affected by this (...I'll fix them since I know about it) but others may not be watching the mailing lists as closely. Of course we make no guarantees about C++ API stability, but I feel we shouldn't cause unnecessary pain and breakage if it can be avoided.

How about renaming the APIs that take or return arg indices? That'll make it abundantly clear that their behavior has changed (and will also easily flag up all the places in upstream code that need to be changed).

[ahatanak]

llvm/include/llvm/IR/Attributes.h

484 ↗

(On Diff #98222)

Is it necessary to have two functions, empty and isEmpty, which have the same functionality?

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

4959 ↗

(On Diff #98222)

Is this change related to the changes in AttributeList?

llvm/lib/IR/Attributes.cpp

843 ↗

(On Diff #98222)

Since Attrs is already sorted when it's passed to this function, can you just look at the last element to find the max index?

895 ↗

(On Diff #98222)

Space before and after +.

[rnk]

• Address Akira's comments

llvm/include/llvm/IR/Attributes.h

484 ↗

(On Diff #98222)

I never actually ended up using this or size(), so I'll remove them. We can standardize on the STL names later.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

4959 ↗

(On Diff #98222)

I will rebase and it should go away. This was in my local master, but not origin/master, which arcanist diffs against.

llvm/lib/IR/Attributes.cpp

843 ↗

(On Diff #98222)

You're right, I can.

[rnk]

In D32819#749907, @tobiasvk wrote:

In D32819#749163, @rnk wrote:

One question remains: do you think I should completely encapsulate this indexing change by adding 1 inside AttributeList::getAttributes, or is it better to update all the callers as I did in this change? The problem with this change is that it will break out-of-tree backends and frontends that use the APIs with one-based indexing. It won't even be a compile failure because the APIs still take unsigned integers. That's a bit rude without some more hand waving on llvm-dev and release notes.

I'm very concerned about breaking out-of-tree code in a way that's not detectable at compile time. We have a whole bunch of out-of-tree passes that will be affected by this (...I'll fix them since I know about it) but others may not be watching the mailing lists as closely. Of course we make no guarantees about C++ API stability, but I feel we shouldn't cause unnecessary pain and breakage if it can be avoided.

Having just debugged a lot of "index out of bounds" type runtime failures, I generally agree, I don't want to put others through it. :)

How about renaming the APIs that take or return arg indices? That'll make it abundantly clear that their behavior has changed (and will also easily flag up all the places in upstream code that need to be changed).

I don't want to use bad names (hasAttributeEx?) just for backwards compatibility. One idea I had was to make a better API, one that has no attribute list indices at all, but there are a handful of places in LLVM that abstract over argument and return attributes with attribute list indices, and I couldn't find a way to replace them. Maybe rename the old APIs to hasRetOrArgAttr or something painfully ugly like that to discourage people from using them? We'd have (has|get|add|remove)ParamAttr, *RetAttr, *FnAttr to make it easier to migrate code to do the right thing.

Anyway, I'll upload a patch that retains compatibility. I want to get the performance win before dealing with that.

[rnk]

• Undo AttributeList indexing change

[rnk]

• rebase to remove undesired changes

[chandlerc]

In D32819#752793, @rnk wrote:

In D32819#749907, @tobiasvk wrote:

In D32819#749163, @rnk wrote:

One question remains: do you think I should completely encapsulate this indexing change by adding 1 inside AttributeList::getAttributes, or is it better to update all the callers as I did in this change? The problem with this change is that it will break out-of-tree backends and frontends that use the APIs with one-based indexing. It won't even be a compile failure because the APIs still take unsigned integers. That's a bit rude without some more hand waving on llvm-dev and release notes.

I'm very concerned about breaking out-of-tree code in a way that's not detectable at compile time. We have a whole bunch of out-of-tree passes that will be affected by this (...I'll fix them since I know about it) but others may not be watching the mailing lists as closely. Of course we make no guarantees about C++ API stability, but I feel we shouldn't cause unnecessary pain and breakage if it can be avoided.

Having just debugged a lot of "index out of bounds" type runtime failures, I generally agree, I don't want to put others through it. :)

How about renaming the APIs that take or return arg indices? That'll make it abundantly clear that their behavior has changed (and will also easily flag up all the places in upstream code that need to be changed).

I don't want to use bad names (hasAttributeEx?) just for backwards compatibility. One idea I had was to make a better API, one that has no attribute list indices at all, but there are a handful of places in LLVM that abstract over argument and return attributes with attribute list indices, and I couldn't find a way to replace them. Maybe rename the old APIs to hasRetOrArgAttr or something painfully ugly like that to discourage people from using them? We'd have (has|get|add|remove)ParamAttr, *RetAttr, *FnAttr to make it easier to migrate code to do the right thing.

FWIW, I really like this plan. Keep the "compatible" indexing API but make it much more clear why it's a bad idea with a simple rename. Wait some time unit, then introduce new API that doesn't have these failuremodes with a nice set of names.

[rnk]

• Port changes addressing Akira's comments to the branch with no indexing change

[rnk]

• rebase

[rnk]

Added Hans as a reviewer. I think there is consensus from code owners that this is the right thing to do, but I'm still looking for a code reviewer with time.

[chandlerc]

(FWIW, given the overall plan, I'm very happy for Hans to handle the code review.)

[hans]

llvm/lib/IR/AttributeImpl.h

235 ↗

(On Diff #99793)

Not related to your patch, but why is this needed?

llvm/lib/IR/Attributes.cpp

813 ↗

(On Diff #99793)

I might have gone for Sets[0] to make it more obvious that's what the assert above is about. Or would it make sense to just do Sets[attrIdxToArrayIdx(AttributeList::FunctionIndex)]?

815 ↗

(On Diff #99793)

Not related to this patch of course, but is there any reason to not just use 1ULL?

847 ↗

(On Diff #99793)

I suppose we'd still assert when hitting the AttributeListImpl constructor, but maybe this is worth keeping to assert early?

939 ↗

(On Diff #99793)

I think it would be more clear to loop over ArgAttrs with an index and just set LastAttrPos = I + 2. Or see my suggestion further down.

951 ↗

(On Diff #99793)

I didn't know that. Is it worth asserting?

954 ↗

(On Diff #99793)

Are there always RetAttrs if there are ArgAttrs? Oh, it doesn't matter; pushing an empty RetAttrs does the job just as well.

957 ↗

(On Diff #99793)

I had to do a double-take on that -1, but it looks right.

I wonder if this function could be simpler though. Perhaps first loop from the back of ArgAttrs to find the last one that has attributes, then based on that and .hasAttributes on FnAttrs and RetAttrs, either return early or push into the SmallVector straight up?

969 ↗

(On Diff #99793)

Is 5 significant?

998 ↗

(On Diff #99793)

Below you just do for (AttributeList List : Attrs, i.e. no auto and no reference. That seems nicer.

1035 ↗

(On Diff #99793)

Maybe fold into the previous statement? unsigned MaxIndex = attrIdxToArrayIdx(Indices.back()).

llvm/lib/IR/Instructions.cpp

457 ↗

(On Diff #99793)

Use ReturnIndex instead of i?

[rnk]

Thanks!

llvm/lib/IR/AttributeImpl.h

235 ↗

(On Diff #99793)

This appears to inhibit sized deallocation. @rsmith added it in r260180. Perhaps it deserves a comment.

llvm/lib/IR/Attributes.cpp

813 ↗

(On Diff #99793)

Perhaps, but the only reason that .front() or [0] are safe is because we asserted above that Sets isn't empty, so we still need some assertion or comment indicating that function attributes are always available. I'll do Set[0].

957 ↗

(On Diff #99793)

I implemented this, and I also switched to a set count instead of a "last position" variable, which I think improves things a lot. I don't know why I used "LastPos" instead of a size or count variable. I think that is what was introducing these confusing off by one calculations.

969 ↗

(On Diff #99793)

Not really, let's go to 8 for consistency. That is one thing I hate about SmallVector: you are forced to invent magic numbers all the time, and it makes the reader think the number was tuned. :)

[rnk]

• Address Hans's comments

[hans]

lgtm

llvm/trunk/include/llvm/IR/Attributes.h

 
 //===----------------------------------------------------------------------===//
 /// \class
 /// \brief This class holds the attributes for a function, its return value, and
 /// its parameters. You access the attributes for each of them via an index into
 /// the AttributeList object. The function attributes are at index
 /// `AttributeList::FunctionIndex', the return value is at index
 /// `AttributeList::ReturnIndex', and the attributes for the parameters start at
-/// index `1'.
+/// index `AttributeList::FirstArgIndex'.
 class AttributeList {
 public:
   enum AttrIndex : unsigned {
     ReturnIndex = 0U,
     FunctionIndex = ~0U,
     FirstArgIndex = 1,
   };
 
 private:
   friend class AttrBuilder;
   friend class AttributeListImpl;
   friend class AttributeSet;
   friend class AttributeSetNode;
 
   template <typename Ty> friend struct DenseMapInfo;
 
   /// \brief The attributes that we are managing. This can be null to represent
   /// the empty attributes list.
   AttributeListImpl *pImpl = nullptr;
 
 public:
   /// \brief Create an AttributeList with the specified parameters in it.
   static AttributeList get(LLVMContext &C,
                            ArrayRef<std::pair<unsigned, Attribute>> Attrs);
-  static AttributeList
-  get(LLVMContext &C, ArrayRef<std::pair<unsigned, AttributeSet>> Attrs);
+  static AttributeList get(LLVMContext &C,
+                           ArrayRef<std::pair<unsigned, AttributeSet>> Attrs);
 
   /// \brief Create an AttributeList from attribute sets for a function, its
   /// return value, and all of its arguments.
   static AttributeList get(LLVMContext &C, AttributeSet FnAttrs,
                            AttributeSet RetAttrs,
                            ArrayRef<AttributeSet> ArgAttrs);
 
-  static AttributeList
-  getImpl(LLVMContext &C,
-          ArrayRef<std::pair<unsigned, AttributeSet>> Attrs);
-
 private:
   explicit AttributeList(AttributeListImpl *LI) : pImpl(LI) {}
 
+  static AttributeList getImpl(LLVMContext &C, ArrayRef<AttributeSet> AttrSets);
+
 public:
   AttributeList() = default;
 
   //===--------------------------------------------------------------------===//
   // AttributeList Construction and Mutation
   //===--------------------------------------------------------------------===//
 
   /// \brief Return an AttributeList with the specified parameters in it.
public:
 
   /// Get the allocsize argument numbers (or pair(0, 0) if unknown).
   std::pair<unsigned, Optional<unsigned>>
   getAllocSizeArgs(unsigned Index) const;
 
   /// \brief Return the attributes at the index as a string.
   std::string getAsString(unsigned Index, bool InAttrGrp = false) const;
 
-  using iterator = ArrayRef<Attribute>::iterator;
+  //===--------------------------------------------------------------------===//
+  // AttributeList Introspection
+  //===--------------------------------------------------------------------===//
+
+  typedef const AttributeSet *iterator;
+  iterator begin() const;
+  iterator end() const;
+
+  unsigned getNumAttrSets() const;
 
-  iterator begin(unsigned Slot) const;
-  iterator end(unsigned Slot) const;
+  /// Use these to iterate over the valid attribute indices.
+  unsigned index_begin() const { return AttributeList::FunctionIndex; }
+  unsigned index_end() const { return getNumAttrSets() - 1; }
 
   /// operator==/!= - Provide equality predicates.
   bool operator==(const AttributeList &RHS) const { return pImpl == RHS.pImpl; }
   bool operator!=(const AttributeList &RHS) const { return pImpl != RHS.pImpl; }
 
-  //===--------------------------------------------------------------------===//
-  // AttributeList Introspection
-  //===--------------------------------------------------------------------===//
-
   /// \brief Return a raw pointer that uniquely identifies this attribute list.
   void *getRawPointer() const {
     return pImpl;
   }
 
   /// \brief Return true if there are no attributes.
-  bool isEmpty() const {
-    return getNumSlots() == 0;
-  }
-
-  /// \brief Return the number of slots used in this attribute list.  This is
-  /// the number of arguments that have an attribute set on them (including the
-  /// function itself).
-  unsigned getNumSlots() const;
-
-  /// \brief Return the index for the given slot.
-  unsigned getSlotIndex(unsigned Slot) const;
-
-  /// \brief Return the attributes at the given slot.
-  AttributeSet getSlotAttributes(unsigned Slot) const;
+  bool isEmpty() const { return pImpl == nullptr; }
 
   void dump() const;
 };
 
 //===----------------------------------------------------------------------===//
 /// \class
 /// \brief Provide DenseMapInfo for AttributeList.
 template <> struct DenseMapInfo<AttributeList> {

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

 void ModuleBitcodeWriter::writeAttributeTable() {
   const std::vector<AttributeList> &Attrs = VE.getAttributeLists();
   if (Attrs.empty()) return;
 
   Stream.EnterSubblock(bitc::PARAMATTR_BLOCK_ID, 3);
 
   SmallVector<uint64_t, 64> Record;
   for (unsigned i = 0, e = Attrs.size(); i != e; ++i) {
-    const AttributeList &A = Attrs[i];
-    for (unsigned i = 0, e = A.getNumSlots(); i != e; ++i)
-      Record.push_back(
-          VE.getAttributeGroupID({A.getSlotIndex(i), A.getSlotAttributes(i)}));
+    AttributeList AL = Attrs[i];
+    for (unsigned i = AL.index_begin(), e = AL.index_end(); i != e; ++i) {
+      AttributeSet AS = AL.getAttributes(i);
+      if (AS.hasAttributes())
+        Record.push_back(VE.getAttributeGroupID({i, AS}));
+    }
 
     Stream.EmitRecord(bitc::PARAMATTR_CODE_ENTRY, Record);
     Record.clear();
   }
 
   Stream.ExitBlock();
 }
 

llvm/trunk/lib/Bitcode/Writer/ValueEnumerator.cpp

void ValueEnumerator::EnumerateAttributes(AttributeList PAL) {
   unsigned &Entry = AttributeListMap[PAL];
   if (Entry == 0) {
     // Never saw this before, add it.
     AttributeLists.push_back(PAL);
     Entry = AttributeLists.size();
   }
 
   // Do lookups for all attribute groups.
-  for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) {
-    IndexAndAttrSet Pair = {PAL.getSlotIndex(i), PAL.getSlotAttributes(i)};
+  for (unsigned i = PAL.index_begin(), e = PAL.index_end(); i != e; ++i) {
+    AttributeSet AS = PAL.getAttributes(i);
+    if (!AS.hasAttributes())
+      continue;
+    IndexAndAttrSet Pair = {i, AS};
     unsigned &Entry = AttributeGroupMap[Pair];
     if (Entry == 0) {
       AttributeGroups.push_back(Pair);
       Entry = AttributeGroups.size();
     }
   }
 }
 

llvm/trunk/lib/IR/AttributeImpl.h

 using IndexAttrPair = std::pair<unsigned, AttributeSet>;
 
 //===----------------------------------------------------------------------===//
 /// \class
 /// \brief This class represents a set of attributes that apply to the function,
 /// return type, and parameters.
 class AttributeListImpl final
     : public FoldingSetNode,
-      private TrailingObjects<AttributeListImpl, IndexAttrPair> {
+      private TrailingObjects<AttributeListImpl, AttributeSet> {
   friend class AttributeList;
   friend TrailingObjects;
 
 private:
-  LLVMContext &Context;
-  unsigned NumSlots; ///< Number of entries in this set.
   /// Bitset with a bit for each available attribute Attribute::AttrKind.
   uint64_t AvailableFunctionAttrs;
+  LLVMContext &Context;
+  unsigned NumAttrSets; ///< Number of entries in this set.
 
   // Helper fn for TrailingObjects class.
-  size_t numTrailingObjects(OverloadToken<IndexAttrPair>) { return NumSlots; }
-
-  /// \brief Return a pointer to the IndexAttrPair for the specified slot.
-  const IndexAttrPair *getSlotPair(unsigned Slot) const {
-    return getTrailingObjects<IndexAttrPair>() + Slot;
-  }
+  size_t numTrailingObjects(OverloadToken<AttributeSet>) { return NumAttrSets; }
 
 public:
-  AttributeListImpl(LLVMContext &C,
-                    ArrayRef<std::pair<unsigned, AttributeSet>> Slots);
+  AttributeListImpl(LLVMContext &C, ArrayRef<AttributeSet> Sets);
 
   // AttributesSetImpt is uniqued, these should not be available.
   AttributeListImpl(const AttributeListImpl &) = delete;
   AttributeListImpl &operator=(const AttributeListImpl &) = delete;
 
   void operator delete(void *p) { ::operator delete(p); }
 
   /// \brief Get the context that created this AttributeListImpl.
   LLVMContext &getContext() { return Context; }
 
-  /// \brief Return the number of slots used in this attribute list. This is
-  /// the number of arguments that have an attribute set on them (including the
-  /// function itself).
-  unsigned getNumSlots() const { return NumSlots; }
-
-  /// \brief Get the index of the given "slot" in the AttrNodes list. This index
-  /// is the index of the return, parameter, or function object that the
-  /// attributes are applied to, not the index into the AttrNodes list where the
-  /// attributes reside.
-  unsigned getSlotIndex(unsigned Slot) const {
-    return getSlotPair(Slot)->first;
-  }
-
-  /// \brief Retrieve the attribute set node for the given "slot" in the
-  /// AttrNode list.
-  AttributeSet getSlotAttributes(unsigned Slot) const {
-    return getSlotPair(Slot)->second;
-  }
-
   /// \brief Return true if the AttributeSet or the FunctionIndex has an
   /// enum attribute of the given kind.
   bool hasFnAttribute(Attribute::AttrKind Kind) const {
     return AvailableFunctionAttrs & ((uint64_t)1) << Kind;
   }
 
-  using iterator = AttributeSet::iterator;
-
-  iterator begin(unsigned Slot) const {
-    return getSlotAttributes(Slot).begin();
-  }
-  iterator end(unsigned Slot) const { return getSlotAttributes(Slot).end(); }
+  typedef const AttributeSet *iterator;
+  iterator begin() const { return getTrailingObjects<AttributeSet>(); }
+  iterator end() const { return begin() + NumAttrSets; }
 
   void Profile(FoldingSetNodeID &ID) const;
-  static void Profile(FoldingSetNodeID &ID,
-                      ArrayRef<std::pair<unsigned, AttributeSet>> Nodes);
+  static void Profile(FoldingSetNodeID &ID, ArrayRef<AttributeSet> Nodes);
 
   void dump() const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_IR_ATTRIBUTEIMPL_H

llvm/trunk/lib/IR/Attributes.cpp

AttributeSet AttributeSet::get(LLVMContext &C, const AttrBuilder &B) {
   return AttributeSet(AttributeSetNode::get(C, B));
 }
 
 AttributeSet AttributeSet::get(LLVMContext &C, ArrayRef<Attribute> Attrs) {
   return AttributeSet(AttributeSetNode::get(C, Attrs));
 }
 
 AttributeSet AttributeSet::addAttribute(LLVMContext &C,
                                         Attribute::AttrKind Kind) const {
   if (hasAttribute(Kind)) return *this;
   AttrBuilder B;
   B.addAttribute(Kind);
   return addAttributes(C, AttributeSet::get(C, B));
 }
 
 AttributeSet AttributeSet::addAttribute(LLVMContext &C, StringRef Kind,
                                         StringRef Value) const {
   AttrBuilder B;
   B.addAttribute(Kind, Value);
   return addAttributes(C, AttributeSet::get(C, B));
 }
 
 AttributeSet AttributeSet::addAttributes(LLVMContext &C,
                                          const AttributeSet AS) const {
   if (!hasAttributes())
std::string AttributeSetNode::getAsString(bool InAttrGrp) const {
   }
   return Str;
 }
 
 //===----------------------------------------------------------------------===//
 // AttributeListImpl Definition
 //===----------------------------------------------------------------------===//
 
-AttributeListImpl::AttributeListImpl(
-    LLVMContext &C, ArrayRef<std::pair<unsigned, AttributeSet>> Slots)
-    : Context(C), NumSlots(Slots.size()), AvailableFunctionAttrs(0) {
-#ifndef NDEBUG
-  assert(!Slots.empty() && "pointless AttributeListImpl");
-  if (Slots.size() >= 2) {
-    auto &PrevPair = Slots.front();
-    for (auto &CurPair : Slots.drop_front()) {
-      assert(PrevPair.first <= CurPair.first && "Attribute set not ordered!");
-    }
-  }
-#endif
+/// Map from AttributeList index to the internal array index. Adding one works:
+///   FunctionIndex: ~0U -> 0
+///   ReturnIndex:    0  -> 1
+///   FirstArgIndex: 1.. -> 2..
+static constexpr unsigned attrIdxToArrayIdx(unsigned Index) {
+  return Index + 1;
+
+AttributeListImpl::AttributeListImpl(LLVMContext &C,
+                                     ArrayRef<AttributeSet> Sets)
+    : AvailableFunctionAttrs(0), Context(C), NumAttrSets(Sets.size()) {
+  assert(!Sets.empty() && "pointless AttributeListImpl");
 
   // There's memory after the node where we can store the entries in.
-  std::copy(Slots.begin(), Slots.end(), getTrailingObjects<IndexAttrPair>());
+  std::copy(Sets.begin(), Sets.end(), getTrailingObjects<AttributeSet>());
 
   // Initialize AvailableFunctionAttrs summary bitset.
   static_assert(Attribute::EndAttrKinds <=
                     sizeof(AvailableFunctionAttrs) * CHAR_BIT,
                 "Too many attributes");
-  static_assert(AttributeList::FunctionIndex == ~0u,
-                "FunctionIndex should be biggest possible index");
-  const auto &Last = Slots.back();
-  if (Last.first == AttributeList::FunctionIndex) {
-    AttributeSet Node = Last.second;
-    for (Attribute I : Node) {
-      if (!I.isStringAttribute())
-        AvailableFunctionAttrs |= ((uint64_t)1) << I.getKindAsEnum();
-    }
+  static_assert(attrIdxToArrayIdx(AttributeList::FunctionIndex) == 0U,
+                "function should be stored in slot 0");
+  for (Attribute I : Sets[0]) {
+      AvailableFunctionAttrs |= 1ULL << I.getKindAsEnum();
   }
 }
 
 void AttributeListImpl::Profile(FoldingSetNodeID &ID) const {
-  Profile(ID, makeArrayRef(getSlotPair(0), getNumSlots()));
+  Profile(ID, makeArrayRef(begin(), end()));
 }
 
-void AttributeListImpl::Profile(
-    FoldingSetNodeID &ID, ArrayRef<std::pair<unsigned, AttributeSet>> Nodes) {
-  for (const auto &Node : Nodes) {
-    ID.AddInteger(Node.first);
-    ID.AddPointer(Node.second.SetNode);
-  }
+void AttributeListImpl::Profile(FoldingSetNodeID &ID,
+                                ArrayRef<AttributeSet> Sets) {
+  for (const auto &Set : Sets)
+    ID.AddPointer(Set.SetNode);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void AttributeListImpl::dump() const {
   AttributeList(const_cast<AttributeListImpl *>(this)).dump();
 }
 #endif
 
 //===----------------------------------------------------------------------===//
 // AttributeList Construction and Mutation Methods
 //===----------------------------------------------------------------------===//
 
-AttributeList AttributeList::getImpl(
-    LLVMContext &C, ArrayRef<std::pair<unsigned, AttributeSet>> Attrs) {
-  assert(!Attrs.empty() && "creating pointless AttributeList");
-#ifndef NDEBUG
-  unsigned LastIndex = 0;
-  bool IsFirst = true;
-  for (auto &&AttrPair : Attrs) {
-    assert((IsFirst || LastIndex < AttrPair.first) &&
-           "unsorted or duplicate AttributeList indices");
-    assert(AttrPair.second.hasAttributes() && "pointless AttributeList slot");
-    LastIndex = AttrPair.first;
-    IsFirst = false;
-  }
-#endif
+AttributeList AttributeList::getImpl(LLVMContext &C,
+                                     ArrayRef<AttributeSet> AttrSets) {
+  assert(!AttrSets.empty() && "pointless AttributeListImpl");
 
   LLVMContextImpl *pImpl = C.pImpl;
   FoldingSetNodeID ID;
-  AttributeListImpl::Profile(ID, Attrs);
+  AttributeListImpl::Profile(ID, AttrSets);
 
   void *InsertPoint;
   AttributeListImpl *PA =
       pImpl->AttrsLists.FindNodeOrInsertPos(ID, InsertPoint);
 
   // If we didn't find any existing attributes of the same shape then
   // create a new one and insert it.
   if (!PA) {
     // Coallocate entries after the AttributeListImpl itself.
     void *Mem = ::operator new(
-        AttributeListImpl::totalSizeToAlloc<IndexAttrPair>(Attrs.size()));
-    PA = new (Mem) AttributeListImpl(C, Attrs);
+        AttributeListImpl::totalSizeToAlloc<AttributeSet>(AttrSets.size()));
+    PA = new (Mem) AttributeListImpl(C, AttrSets);
     pImpl->AttrsLists.InsertNode(PA, InsertPoint);
   }
 
   // Return the AttributesList that we found or created.
   return AttributeList(PA);
 }
 
 AttributeList
for (ArrayRef<std::pair<unsigned, Attribute>>::iterator I = Attrs.begin(),
     while (I != E && I->first == Index) {
       AttrVec.push_back(I->second);
       ++I;
     }
 
     AttrPairVec.emplace_back(Index, AttributeSet::get(C, AttrVec));
   }
 
-  return getImpl(C, AttrPairVec);
+  return get(C, AttrPairVec);
 }
 
 AttributeList
 AttributeList::get(LLVMContext &C,
                    ArrayRef<std::pair<unsigned, AttributeSet>> Attrs) {
   // If there are no attributes then return a null AttributesList pointer.
   if (Attrs.empty())
     return AttributeList();
 
-  return getImpl(C, Attrs);
+  assert(std::is_sorted(Attrs.begin(), Attrs.end(),
+                        [](const std::pair<unsigned, AttributeSet> &LHS,
+                           const std::pair<unsigned, AttributeSet> &RHS) {
+                          return LHS.first < RHS.first;
+                        }) &&
+         "Misordered Attributes list!");
+  assert(none_of(Attrs,
+                 [](const std::pair<unsigned, AttributeSet> &Pair) {
+                   return !Pair.second.hasAttributes();
+                 }) &&
+         "Pointless attribute!");
+
+  unsigned MaxIndex = Attrs.back().first;
+
+  SmallVector<AttributeSet, 4> AttrVec(attrIdxToArrayIdx(MaxIndex) + 1);
+  for (auto Pair : Attrs)
+    AttrVec[attrIdxToArrayIdx(Pair.first)] = Pair.second;
+
+  return getImpl(C, AttrVec);
 }
 
 AttributeList AttributeList::get(LLVMContext &C, AttributeSet FnAttrs,
                                  AttributeSet RetAttrs,
                                  ArrayRef<AttributeSet> ArgAttrs) {
-  SmallVector<std::pair<unsigned, AttributeSet>, 8> AttrPairs;
+  // Scan from the end to find the last argument with attributes.  Most
+  // arguments don't have attributes, so it's nice if we can have fewer unique
+  // AttributeListImpls by dropping empty attribute sets at the end of the list.
+  unsigned NumSets = 0;
+  for (size_t I = ArgAttrs.size(); I != 0; --I) {
+    if (ArgAttrs[I - 1].hasAttributes()) {
+      NumSets = I + 2;
+      break;
+    }
+  }
+  if (NumSets == 0) {
+    // Check function and return attributes if we didn't have argument
+    // attributes.
     if (RetAttrs.hasAttributes())
-    AttrPairs.emplace_back(ReturnIndex, RetAttrs);
-  size_t Index = 1;
-  for (AttributeSet AS : ArgAttrs) {
-    if (AS.hasAttributes())
-      AttrPairs.emplace_back(Index, AS);
-    ++Index;
-  }
-  if (FnAttrs.hasAttributes())
-    AttrPairs.emplace_back(FunctionIndex, FnAttrs);
-  if (AttrPairs.empty())
+      NumSets = 2;
+    else if (FnAttrs.hasAttributes())
+      NumSets = 1;
+  }
+
+  // If all attribute sets were empty, we can use the empty attribute list.
+  if (NumSets == 0)
     return AttributeList();
-  return getImpl(C, AttrPairs);
+
+  SmallVector<AttributeSet, 8> AttrSets;
+  AttrSets.reserve(NumSets);
+  // If we have any attributes, we always have function attributes.
+  AttrSets.push_back(FnAttrs);
+  if (NumSets > 1)
+    AttrSets.push_back(RetAttrs);
+  if (NumSets > 2) {
+    // Drop the empty argument attribute sets at the end.
+    ArgAttrs = ArgAttrs.take_front(NumSets - 2);
+    AttrSets.insert(AttrSets.end(), ArgAttrs.begin(), ArgAttrs.end());
+  }
+
+  return getImpl(C, AttrSets);
 }
 
 AttributeList AttributeList::get(LLVMContext &C, unsigned Index,
                                  const AttrBuilder &B) {
   if (!B.hasAttributes())
     return AttributeList();
-  AttributeSet AS = AttributeSet::get(C, B);
-  std::pair<unsigned, AttributeSet> Arr[1] = {{Index, AS}};
-  return getImpl(C, Arr);
+  Index = attrIdxToArrayIdx(Index);
+  SmallVector<AttributeSet, 8> AttrSets(Index + 1);
+  AttrSets[Index] = AttributeSet::get(C, B);
+  return getImpl(C, AttrSets);
 }
 
 AttributeList AttributeList::get(LLVMContext &C, unsigned Index,
                                  ArrayRef<Attribute::AttrKind> Kinds) {
   SmallVector<std::pair<unsigned, Attribute>, 8> Attrs;
   for (Attribute::AttrKind K : Kinds)
     Attrs.emplace_back(Index, Attribute::get(C, K));
   return get(C, Attrs);
 }
 
 AttributeList AttributeList::get(LLVMContext &C, unsigned Index,
                                  ArrayRef<StringRef> Kinds) {
   SmallVector<std::pair<unsigned, Attribute>, 8> Attrs;
   for (StringRef K : Kinds)
     Attrs.emplace_back(Index, Attribute::get(C, K));
   return get(C, Attrs);
 }
 
 AttributeList AttributeList::get(LLVMContext &C,
                                  ArrayRef<AttributeList> Attrs) {
   if (Attrs.empty())
     return AttributeList();
-  if (Attrs.size() == 1) return Attrs[0];
+  if (Attrs.size() == 1)
+    return Attrs[0];
 
-  SmallVector<std::pair<unsigned, AttributeSet>, 8> AttrNodeVec;
-  AttributeListImpl *A0 = Attrs[0].pImpl;
-  if (A0)
-    AttrNodeVec.append(A0->getSlotPair(0), A0->getSlotPair(A0->getNumSlots()));
-  // 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) {
-    AttributeListImpl *ALI = Attrs[I].pImpl;
-    if (!ALI) continue;
-    SmallVector<std::pair<unsigned, AttributeSet>, 8>::iterator
-      ANVI = AttrNodeVec.begin(), ANVE;
-    for (const IndexAttrPair *AI = ALI->getSlotPair(0),
-                             *AE = ALI->getSlotPair(ALI->getNumSlots());
-         AI != AE; ++AI) {
-      ANVE = AttrNodeVec.end();
-      while (ANVI != ANVE && ANVI->first <= AI->first)
-        ++ANVI;
-      ANVI = AttrNodeVec.insert(ANVI, *AI) + 1;
-    }
+  unsigned MaxSize = 0;
+  for (AttributeList List : Attrs)
+    MaxSize = std::max(MaxSize, List.getNumAttrSets());
+
+  SmallVector<AttributeSet, 8> NewAttrSets(MaxSize);
+  for (unsigned I = 0; I < MaxSize; ++I) {
+    AttrBuilder CurBuilder;
+    for (AttributeList List : Attrs)
+      CurBuilder.merge(List.getAttributes(I - 1));
+    NewAttrSets[I] = AttributeSet::get(C, CurBuilder);
   }
 
-  return getImpl(C, AttrNodeVec);
+  return getImpl(C, NewAttrSets);
 }
 
 AttributeList AttributeList::addAttribute(LLVMContext &C, unsigned Index,
                                           Attribute::AttrKind Kind) const {
   if (hasAttribute(Index, Kind)) return *this;
   AttrBuilder B;
   B.addAttribute(Kind);
   return addAttributes(C, Index, B);
 }
 
 AttributeList AttributeList::addAttribute(LLVMContext &C, unsigned Index,
                                           StringRef Kind,
                                           StringRef Value) const {
   AttrBuilder B;
   B.addAttribute(Kind, Value);
   return addAttributes(C, Index, B);
 }
 
 AttributeList AttributeList::addAttribute(LLVMContext &C,
                                           ArrayRef<unsigned> Indices,
                                           Attribute A) const {
   assert(std::is_sorted(Indices.begin(), Indices.end()));
 
-  unsigned I = 0, E = pImpl ? pImpl->getNumSlots() : 0;
-  SmallVector<IndexAttrPair, 4> AttrVec;
-  for (unsigned Index : Indices) {
-    // Add all attribute slots before the current index.
-    for (; I < E && getSlotIndex(I) < Index; ++I)
-      AttrVec.emplace_back(getSlotIndex(I), pImpl->getSlotAttributes(I));
+  SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
+  unsigned MaxIndex = attrIdxToArrayIdx(Indices.back());
+  if (MaxIndex >= AttrSets.size())
+    AttrSets.resize(MaxIndex + 1);
 
-    // Add the attribute at this index. If we already have attributes at this
-    // index, merge them into a new set.
-    AttrBuilder B;
-    if (I < E && getSlotIndex(I) == Index) {
-      B.merge(AttrBuilder(pImpl->getSlotAttributes(I)));
-      ++I;
-    }
+  for (unsigned Index : Indices) {
+    Index = attrIdxToArrayIdx(Index);
+    AttrBuilder B(AttrSets[Index]);
     B.addAttribute(A);
-    AttrVec.emplace_back(Index, AttributeSet::get(C, B));
+    AttrSets[Index] = AttributeSet::get(C, B);
   }
 
-  // Add remaining attributes.
-  for (; I < E; ++I)
-    AttrVec.emplace_back(getSlotIndex(I), pImpl->getSlotAttributes(I));
-
-  return get(C, AttrVec);
+  return getImpl(C, AttrSets);
 }
 
 AttributeList AttributeList::addAttributes(LLVMContext &C, unsigned Index,
                                            const AttrBuilder &B) const {
   if (!B.hasAttributes())
     return *this;
 
   if (!pImpl)
     return AttributeList::get(C, {{Index, AttributeSet::get(C, B)}});
 
 #ifndef NDEBUG
   // FIXME it is not obvious how this should work for alignment. For now, say
   // we can't change a known alignment.
   unsigned OldAlign = getAttributes(Index).getAlignment();
   unsigned NewAlign = B.getAlignment();
   assert((!OldAlign || !NewAlign || OldAlign == NewAlign) &&
          "Attempt to change alignment!");
 #endif
 
-  SmallVector<IndexAttrPair, 4> AttrVec;
-  uint64_t NumAttrs = pImpl->getNumSlots();
-  unsigned I;
-
-  // Add all the attribute slots before the one we need to merge.
-  for (I = 0; I < NumAttrs; ++I) {
-    if (getSlotIndex(I) >= Index)
-      break;
-    AttrVec.emplace_back(getSlotIndex(I), pImpl->getSlotAttributes(I));
-  }
+  Index = attrIdxToArrayIdx(Index);
+  SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
+  if (Index >= AttrSets.size())
+    AttrSets.resize(Index + 1);
+
+  AttrBuilder Merged(AttrSets[Index]);
+  Merged.merge(B);
+  AttrSets[Index] = AttributeSet::get(C, Merged);
 
-  AttrBuilder NewAttrs;
-  if (I < NumAttrs && getSlotIndex(I) == Index) {
-    // We need to merge the attribute sets.
-    NewAttrs.merge(pImpl->getSlotAttributes(I));
-    ++I;
-  }
-  NewAttrs.merge(B);
-
-  // Add the new or merged attribute set at this index.
-  AttrVec.emplace_back(Index, AttributeSet::get(C, NewAttrs));
-
-  // Add the remaining entries.
-  for (; I < NumAttrs; ++I)
-    AttrVec.emplace_back(getSlotIndex(I), pImpl->getSlotAttributes(I));
-
-  return get(C, AttrVec);
+  return getImpl(C, AttrSets);
 }
 
 AttributeList AttributeList::removeAttribute(LLVMContext &C, unsigned Index,
                                              Attribute::AttrKind Kind) const {
   if (!hasAttribute(Index, Kind)) return *this;
   AttrBuilder B;
   B.addAttribute(Kind);
   return removeAttributes(C, Index, B);
 }
 
 AttributeList AttributeList::removeAttribute(LLVMContext &C, unsigned Index,
                                              StringRef Kind) const {
   if (!hasAttribute(Index, Kind)) return *this;
   AttrBuilder B;
   B.addAttribute(Kind);
   return removeAttributes(C, Index, B);
 }
 
-AttributeList AttributeList::removeAttributes(LLVMContext &C, unsigned Index,
-                                              const AttrBuilder &Attrs) const {
+AttributeList
+AttributeList::removeAttributes(LLVMContext &C, unsigned Index,
+                                const AttrBuilder &AttrsToRemove) const {
   if (!pImpl)
     return AttributeList();
 
   // FIXME it is not obvious how this should work for alignment.
   // For now, say we can't pass in alignment, which no current use does.
-  assert(!Attrs.hasAlignmentAttr() && "Attempt to change alignment!");
-
-  // Add the attribute slots before the one we're trying to add.
-  SmallVector<IndexAttrPair, 4> AttrSets;
-  uint64_t NumAttrs = pImpl->getNumSlots();
-  AttrBuilder B;
-  uint64_t LastIndex = 0;
-  for (unsigned I = 0, E = NumAttrs; I != E; ++I) {
-    if (getSlotIndex(I) >= Index) {
-      if (getSlotIndex(I) == Index)
-        B = AttrBuilder(getSlotAttributes(LastIndex++));
-      break;
-    }
-    LastIndex = I + 1;
-    AttrSets.push_back({getSlotIndex(I), getSlotAttributes(I)});
-  }
+  assert(!AttrsToRemove.hasAlignmentAttr() && "Attempt to change alignment!");
 
-  // Remove the attributes from the existing set and add them.
-  B.remove(Attrs);
-  if (B.hasAttributes())
-    AttrSets.push_back({Index, AttributeSet::get(C, B)});
+  Index = attrIdxToArrayIdx(Index);
+  SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
+  if (Index >= AttrSets.size())
+    AttrSets.resize(Index + 1);
+
+  AttrBuilder B(AttrSets[Index]);
+  B.remove(AttrsToRemove);
+  AttrSets[Index] = AttributeSet::get(C, B);
 
-  // Add the remaining attribute slots.
-  for (unsigned I = LastIndex, E = NumAttrs; I < E; ++I)
-    AttrSets.push_back({getSlotIndex(I), getSlotAttributes(I)});
-
-  return get(C, AttrSets);
+  return getImpl(C, AttrSets);
 }
 
 AttributeList AttributeList::removeAttributes(LLVMContext &C,
                                               unsigned WithoutIndex) const {
   if (!pImpl)
     return AttributeList();
-
-  SmallVector<std::pair<unsigned, AttributeSet>, 4> AttrSet;
-  for (unsigned I = 0, E = pImpl->getNumSlots(); I != E; ++I) {
-    unsigned Index = getSlotIndex(I);
-    if (Index != WithoutIndex)
-      AttrSet.push_back({Index, pImpl->getSlotAttributes(I)});
-  }
-  return get(C, AttrSet);
+  WithoutIndex = attrIdxToArrayIdx(WithoutIndex);
+  if (WithoutIndex >= getNumAttrSets())
+    return *this;
+  SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
+  AttrSets[WithoutIndex] = AttributeSet();
+  return getImpl(C, AttrSets);
 }
 
 AttributeList AttributeList::addDereferenceableAttr(LLVMContext &C,
                                                     unsigned Index,
                                                     uint64_t Bytes) const {
   AttrBuilder B;
   B.addDereferenceableAttr(Bytes);
   return addAttributes(C, Index, B);

 }
 
 bool AttributeList::hasFnAttribute(StringRef Kind) const {
   return hasAttribute(AttributeList::FunctionIndex, Kind);
 }
 
 bool AttributeList::hasParamAttribute(unsigned ArgNo,
                                       Attribute::AttrKind Kind) const {
-  return hasAttribute(ArgNo + 1, Kind);
+  return hasAttribute(ArgNo + FirstArgIndex, Kind);
 }
 
 bool AttributeList::hasAttrSomewhere(Attribute::AttrKind Attr,
                                      unsigned *Index) const {
   if (!pImpl) return false;
 
-  for (unsigned I = 0, E = pImpl->getNumSlots(); I != E; ++I)
-    for (AttributeListImpl::iterator II = pImpl->begin(I), IE = pImpl->end(I);
-         II != IE; ++II)
-      if (II->hasAttribute(Attr)) {
-        if (Index) *Index = pImpl->getSlotIndex(I);
-        return true;
-      }
+  for (unsigned I = index_begin(), E = index_end(); I != E; ++I) {
+    if (hasAttribute(I, Attr)) {
+      if (Index)
+        *Index = I;
+  }
 
   return false;
 }
 
 Attribute AttributeList::getAttribute(unsigned Index,
                                       Attribute::AttrKind Kind) const {
   return getAttributes(Index).getAttribute(Kind);
 }
AttributeList::getAllocSizeArgs(unsigned Index) const {
   return getAttributes(Index).getAllocSizeArgs();
 }
 
 std::string AttributeList::getAsString(unsigned Index, bool InAttrGrp) const {
   return getAttributes(Index).getAsString(InAttrGrp);
 }
 
 AttributeSet AttributeList::getAttributes(unsigned Index) const {
-  if (!pImpl) return AttributeSet();
-
-  // Loop through to find the attribute node we want.
-  for (unsigned I = 0, E = pImpl->getNumSlots(); I != E; ++I)
-    if (pImpl->getSlotIndex(I) == Index)
-      return pImpl->getSlotAttributes(I);
-
+  Index = attrIdxToArrayIdx(Index);
+  if (!pImpl || Index >= getNumAttrSets())
     return AttributeSet();
+  return pImpl->begin()[Index];
 }
 
-AttributeList::iterator AttributeList::begin(unsigned Slot) const {
-  if (!pImpl)
-    return ArrayRef<Attribute>().begin();
-  return pImpl->begin(Slot);
+AttributeList::iterator AttributeList::begin() const {
+  return pImpl ? pImpl->begin() : nullptr;
 }
 
-AttributeList::iterator AttributeList::end(unsigned Slot) const {
-  if (!pImpl)
-    return ArrayRef<Attribute>().end();
-  return pImpl->end(Slot);
+AttributeList::iterator AttributeList::end() const {
+  return pImpl ? pImpl->end() : nullptr;
 }
 
 //===----------------------------------------------------------------------===//
 // AttributeList Introspection Methods
 //===----------------------------------------------------------------------===//
 
-unsigned AttributeList::getNumSlots() const {
-  return pImpl ? pImpl->getNumSlots() : 0;
-}
-
-unsigned AttributeList::getSlotIndex(unsigned Slot) const {
-  assert(pImpl && Slot < pImpl->getNumSlots() &&
-         "Slot # out of range!");
-  return pImpl->getSlotIndex(Slot);
-}
-
-AttributeSet AttributeList::getSlotAttributes(unsigned Slot) const {
-  assert(pImpl && Slot < pImpl->getNumSlots() &&
-         "Slot # out of range!");
-  return pImpl->getSlotAttributes(Slot);
+unsigned AttributeList::getNumAttrSets() const {
+  return pImpl ? pImpl->NumAttrSets : 0;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void AttributeList::dump() const {
   dbgs() << "PAL[\n";
 
-  for (unsigned i = 0, e = getNumSlots(); i < e; ++i) {
-    uint64_t Index = getSlotIndex(i);
-    dbgs() << "  { ";
-    if (Index == ~0U)
-      dbgs() << "~0U";
-    else
-      dbgs() << Index;
-    dbgs() << " => " << getAsString(Index) << " }\n";
+  for (unsigned i = index_begin(), e = index_end(); i != e; ++i) {
+    if (getAttributes(i).hasAttributes())
+      dbgs() << "  { " << i << " => " << getAsString(i) << " }\n";
   }
 
   dbgs() << "]\n";
 }
 #endif
 
 //===----------------------------------------------------------------------===//
 // AttrBuilder Method Implementations
 //===----------------------------------------------------------------------===//
 
+// FIXME: Remove this ctor, use AttributeSet.
 AttrBuilder::AttrBuilder(AttributeList AL, unsigned Index) {
-  AttributeListImpl *pImpl = AL.pImpl;
-  if (!pImpl) return;
-
-  for (unsigned I = 0, E = pImpl->getNumSlots(); I != E; ++I) {
-    if (pImpl->getSlotIndex(I) != Index) continue;
-
-    for (AttributeListImpl::iterator II = pImpl->begin(I), IE = pImpl->end(I);
-         II != IE; ++II)
-      addAttribute(*II);
-
-    break;
-  }
+  AttributeSet AS = AL.getAttributes(Index);
+  for (const Attribute &A : AS)
+    addAttribute(A);
 }
 
 AttrBuilder::AttrBuilder(AttributeSet AS) {
-  if (AS.hasAttributes()) {
-    for (const Attribute &A : AS)
-      addAttribute(A);
-  }
-}
 
 void AttrBuilder::clear() {
   Attrs.reset();
   TargetDepAttrs.clear();
   Alignment = StackAlignment = DerefBytes = DerefOrNullBytes = 0;
   AllocSizeArgs = 0;
 }
 

llvm/trunk/lib/IR/Instructions.cpp

bool CallInst::dataOperandHasImpliedAttr(unsigned i,
   // There are getNumOperands() - 1 data operands.  The last operand is the
   // callee.
   assert(i < getNumOperands() && "Data operand index out of bounds!");
 
   // The attribute A can either be directly specified, if the operand in
   // question is a call argument; or be indirectly implied by the kind of its
   // containing operand bundle, if the operand is a bundle operand.
 
+  if (i == Attribute::ReturnIndex)
+    return hasRetAttr(Kind);
+
   // FIXME: Avoid these i - 1 calculations and update the API to use zero-based
   // indices.
   if (i < (getNumArgOperands() + 1))
     return paramHasAttr(i - 1, Kind);
 
   assert(hasOperandBundles() && i >= (getBundleOperandsStartIndex() + 1) &&
          "Must be either a call argument or an operand bundle!");
   return bundleOperandHasAttr(i - 1, Kind);
bool InvokeInst::dataOperandHasImpliedAttr(unsigned i,
   // There are getNumOperands() - 3 data operands.  The last three operands are
   // the callee and the two successor basic blocks.
   assert(i < (getNumOperands() - 2) && "Data operand index out of bounds!");
 
   // The attribute A can either be directly specified, if the operand in
   // question is an invoke argument; or be indirectly implied by the kind of its
   // containing operand bundle, if the operand is a bundle operand.
 
+  if (i == Attribute::ReturnIndex)
+    return hasRetAttr(Kind);
+
   // FIXME: Avoid these i - 1 calculations and update the API to use zero-based
   // indices.
   if (i < (getNumArgOperands() + 1))
     return paramHasAttr(i - 1, Kind);
 
   assert(hasOperandBundles() && i >= (getBundleOperandsStartIndex() + 1) &&
          "Must be either an invoke argument or an operand bundle!");
   return bundleOperandHasAttr(i - 1, Kind);

llvm/trunk/lib/IR/Verifier.cpp

StringRef Msg = CE->getOpcode() == Instruction::IntToPtr
                         : "ptrtoint not supported for non-integral pointers";
     Assert(
         !DL.isNonIntegralPointerType(cast<PointerType>(PtrTy->getScalarType())),
         Msg);
   }
 }
 
 bool Verifier::verifyAttributeCount(AttributeList Attrs, unsigned Params) {
-  if (Attrs.getNumSlots() == 0)
-    return true;
-
-  unsigned LastSlot = Attrs.getNumSlots() - 1;
-  unsigned LastIndex = Attrs.getSlotIndex(LastSlot);
-  if (LastIndex <= Params ||
-      (LastIndex == AttributeList::FunctionIndex &&
-       (LastSlot == 0 || Attrs.getSlotIndex(LastSlot - 1) <= Params)))
-    return true;
-
-  return false;
+  // There shouldn't be more attribute sets than there are parameters plus the
+  // function and return value.
+  return Attrs.getNumAttrSets() <= Params + 2;
 }
 
 /// Verify that statepoint intrinsic is well formed.
 void Verifier::verifyStatepoint(ImmutableCallSite CS) {
   assert(CS.getCalledFunction() &&
          CS.getCalledFunction()->getIntrinsicID() ==
            Intrinsic::experimental_gc_statepoint);
 

llvm/trunk/lib/Transforms/Utils/FunctionComparator.cpp

int FunctionComparator::cmpMem(StringRef L, StringRef R) const {
 
   // Compare strings lexicographically only when it is necessary: only when
   // strings are equal in size.
   return L.compare(R);
 }
 
 int FunctionComparator::cmpAttrs(const AttributeList L,
                                  const AttributeList R) const {
-  if (int Res = cmpNumbers(L.getNumSlots(), R.getNumSlots()))
+  if (int Res = cmpNumbers(L.getNumAttrSets(), R.getNumAttrSets()))
     return Res;
 
-  for (unsigned i = 0, e = L.getNumSlots(); i != e; ++i) {
-    AttributeList::iterator LI = L.begin(i), LE = L.end(i), RI = R.begin(i),
-                            RE = R.end(i);
+  for (unsigned i = L.index_begin(), e = L.index_end(); i != e; ++i) {
+    AttributeSet LAS = L.getAttributes(i);
+    AttributeSet RAS = R.getAttributes(i);
+    AttributeSet::iterator LI = LAS.begin(), LE = LAS.end();
+    AttributeSet::iterator RI = RAS.begin(), RE = RAS.end();
     for (; LI != LE && RI != RE; ++LI, ++RI) {
       Attribute LA = *LI;
       Attribute RA = *RI;
       if (LA < RA)
         return -1;
       if (RA < LA)
         return 1;
     }