[AttributeSet] Overload AttributeSet::addAttribute to reduce compile time

[ahatanak]

Summary

The new overloaded function is used when an attribute is added to a large number of slots of an AttributeSet (for example, to function parameters). This is much faster than calling AttributeSet::addAttribute once per slot, because AttributeSet::getImpl (which calls FoldingSet::FIndNodeOrInsertPos) is called only once per function instead of once per slot.

With this patch applied, clang compiles a file which used to take over 22 minutes in just 13 seconds.

[pete]

A few nitpicks, but honestly this is great. So LGTM.

Many of the nitpicks are up to you if you even want to fix them. I don't think any block this from going in.

Thanks for doing this!

include/llvm/IR/Attributes.h

230 ↗

(On Diff #41413)

Nitpicking, but we don't put \brief any more. Although you were just matching the style of th rest of the file, so probably fine to leave it here.

lib/IR/Attributes.cpp

775 ↗

(On Diff #41413)

I didn't know we could actually pass around 'Attribute' which would wrap up enum/integer/string attributes. Unfortunately this could lead to a slight difference in behavior compared to the old way of adding attributes. The difference being that you don't have this code in your implementation:

#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 = getParamAlignment(Index);
unsigned NewAlign = Attrs.getParamAlignment(Index);
assert((!OldAlign || !NewAlign || OldAlign == NewAlign) &&
       "Attempt to change alignment!");

#endif

I imagine you could add that to the appropriate conditional in your loop, although i'm not sure if we want to or not. Up to you, but just wanted to point it out.

Another solution is to change your API from 'Attribute' to 'Attribute::AttrKind' and so only accept enum attributes. I kinda like the generic API which can take any attributes, but the enum has the advantage of not worrying about the alignment issue (which FYI is totally out of date anyway as we have more integer attributes than just alignment, and none of the others are checked here)

lib/Transforms/InstCombine/InstCombineCalls.cpp

1952 ↗

(On Diff #41413)

Again nitpicking, but I would move the 'Changed = true' in to the 'if (!Indices.empty()) {' conditional as thats where you apply the changes.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

323 ↗

(On Diff #41413)

Similarly here.

330 ↗

(On Diff #41413)

And this conditional can be changed to be 'if (Indices.empty()) return false'. Then you can follow it with what was in the conditional and a 'return true' as no need for the 'bool Changed' any more in this case.

[ahatanak]

lib/IR/Attributes.cpp

775 ↗

(On Diff #41413)

I wonder if we can remove the assert in AttributeSet::addAttributes and just allow it to override the old alignment using the alignment in Attrs. This is consistent with the way it handles string attributes: if there is an attribute "some_str_attr"="true" in Attrs, it will change the value of attribute "some_str_attr"="false". Also, as you've pointed out, we don't check other integer attributes here, so if we are going to keep the assert we should make changes to check those attributes too.

lib/Transforms/InstCombine/InstCombineCalls.cpp

1952 ↗

(On Diff #41413)

Will fix

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

330 ↗

(On Diff #41413)

Will fix.

[pete]

lib/IR/Attributes.cpp

775 ↗

(On Diff #41413)

Yeah, removing that assert is probably best. If someone did trigger the assert, then I imagine all that would happen is they would change the call from AS.addAttribute(..., ::Align) to AS.removeAttribute(..., ::Align).addAttribute(..., ::Align) which would match the behavior you describe anyway.

I guess the issue might be that its likely incorrect to lower the alignment. Other code could have applied optimizations based on a given alignment so lowering it would invalidate those optimizations. But then again, thats true for pretty much all attributes anyway. You couldn't go and remove a readonly for example as someone may have used the presence of readonly to move a store around. The point is that we don't assert on readonly or anything else, so seems weird to assert on alignment.

BTW, I think there's a few places which assert on alignment. I think AttrBuilder has some too, so certainly worth looking in to that in a follow up patch.

[ahatanak]

lib/IR/Attributes.cpp

775 ↗

(On Diff #41413)

OK, I'll take care of this in follow-up patches.

In the short term, I might just add a check similar to the one in AttributeSet::addAttributes, but it seems to me that the users of those functions should be responsible for making sure adding or removing attributes doesn't invalidate optimizations that have already been applied.

[ahatanak]

I'll commit this patch shortly. Thank you for the review.

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

public:
 
   /// \brief Add an attribute to the attribute set at the given index. Because
   /// attribute sets are immutable, this returns a new set.
   AttributeSet addAttribute(LLVMContext &C, unsigned Index,
                             StringRef Kind) const;
   AttributeSet addAttribute(LLVMContext &C, unsigned Index,
                             StringRef Kind, StringRef Value) const;
 
+  /// Add an attribute to the attribute set at the given indices. Because
+  /// attribute sets are immutable, this returns a new set.
+  AttributeSet addAttribute(LLVMContext &C, ArrayRef<unsigned> Indices,
+                            Attribute A) const;
+
   /// \brief Add attributes to the attribute set at the given index. Because
   /// attribute sets are immutable, this returns a new set.
   AttributeSet addAttributes(LLVMContext &C, unsigned Index,
                              AttributeSet Attrs) const;
 
   /// \brief Remove the specified attribute at the specified index from this
   /// attribute list. Because attribute lists are immutable, this returns the
   /// new list.

llvm/trunk/lib/IR/Attributes.cpp

 
 AttributeSet AttributeSet::addAttribute(LLVMContext &C, unsigned Index,
                                         StringRef Kind, StringRef Value) const {
   llvm::AttrBuilder B;
   B.addAttribute(Kind, Value);
   return addAttributes(C, Index, AttributeSet::get(C, Index, B));
 }
 
+AttributeSet AttributeSet::addAttribute(LLVMContext &C,
+                                        ArrayRef<unsigned> Indices,
+                                        Attribute A) const {
+  unsigned I = 0, E = pImpl ? pImpl->getNumAttributes() : 0;
+  auto IdxI = Indices.begin(), IdxE = Indices.end();
+  SmallVector<AttributeSet, 4> AttrSet;
+
+  while (I != E && IdxI != IdxE) {
+    if (getSlotIndex(I) < *IdxI)
+      AttrSet.emplace_back(getSlotAttributes(I++));
+    else if (getSlotIndex(I) > *IdxI)
+      AttrSet.emplace_back(AttributeSet::get(C, std::make_pair(*IdxI++, A)));
+    else {
+      AttrBuilder B(getSlotAttributes(I), *IdxI);
+      B.addAttribute(A);
+      AttrSet.emplace_back(AttributeSet::get(C, *IdxI, B));
+      ++I;
+      ++IdxI;
+    }
+  }
+
+  while (I != E)
+    AttrSet.emplace_back(getSlotAttributes(I++));
+
+  while (IdxI != IdxE)
+    AttrSet.emplace_back(AttributeSet::get(C, std::make_pair(*IdxI++, A)));
+
+  return get(C, AttrSet);
+}
+
 AttributeSet AttributeSet::addAttributes(LLVMContext &C, unsigned Index,
                                          AttributeSet Attrs) const {
   if (!pImpl) return Attrs;
   if (!Attrs.pImpl) return *this;
 
 #ifndef NDEBUG
   // FIXME it is not obvious how this should work for alignment. For now, say
   // we can't change a known alignment.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

Instruction *InstCombiner::visitCallSite(CallSite CS) {
   if (isAllocLikeFn(CS.getInstruction(), TLI))
     return visitAllocSite(*CS.getInstruction());
 
   bool Changed = false;
 
   // Mark any parameters that are known to be non-null with the nonnull
   // attribute.  This is helpful for inlining calls to functions with null
   // checks on their arguments.
+  SmallVector<unsigned, 4> Indices;
   unsigned ArgNo = 0;
+
   for (Value *V : CS.args()) {
     if (V->getType()->isPointerTy() && !CS.paramHasAttr(ArgNo+1, Attribute::NonNull) &&
-        isKnownNonNullAt(V, CS.getInstruction(), DT, TLI)) {
-      AttributeSet AS = CS.getAttributes();
-      AS = AS.addAttribute(CS.getInstruction()->getContext(), ArgNo+1,
-                           Attribute::NonNull);
-      CS.setAttributes(AS);
-      Changed = true;
-    }
-    ArgNo++;
-  }
-  assert(ArgNo == CS.arg_size() && "sanity check");
+        isKnownNonNullAt(V, CS.getInstruction(), DT, TLI))
+      Indices.push_back(ArgNo + 1);
+    ArgNo++;
+  }
+
+  assert(ArgNo == CS.arg_size() && "sanity check");
+
+  if (!Indices.empty()) {
+    LLVMContext &Ctx = CS.getInstruction()->getContext();
+    AS = AS.addAttribute(Ctx, Indices,
+                         Attribute::get(Ctx, Attribute::NonNull));
 
   // If the callee is a pointer to a function, attempt to move any casts to the
   // arguments of the call/invoke.
   Value *Callee = CS.getCalledValue();
   if (!isa<Function>(Callee) && transformConstExprCastCall(CS))
     return nullptr;
 
   if (Function *CalleeF = dyn_cast<Function>(Callee))

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

if (Changed)
     ConstantFoldTerminator(BB);
 
   return Changed;
 }
 
 /// processCallSite - Infer nonnull attributes for the arguments at the
 /// specified callsite.
 bool CorrelatedValuePropagation::processCallSite(CallSite CS) {
-  bool Changed = false;
-
+  SmallVector<unsigned, 4> Indices;
   unsigned ArgNo = 0;
+
   for (Value *V : CS.args()) {
     PointerType *Type = dyn_cast<PointerType>(V->getType());
 
     if (Type && !CS.paramHasAttr(ArgNo + 1, Attribute::NonNull) &&
         LVI->getPredicateAt(ICmpInst::ICMP_EQ, V,
                             ConstantPointerNull::get(Type),
-                            CS.getInstruction()) == LazyValueInfo::False) {
-      AttributeSet AS = CS.getAttributes();
-      AS = AS.addAttribute(CS.getInstruction()->getContext(), ArgNo + 1,
-                           Attribute::NonNull);
-      CS.setAttributes(AS);
-      Changed = true;
-    }
+                            CS.getInstruction()) == LazyValueInfo::False)
+      Indices.push_back(ArgNo + 1);
     ArgNo++;
   }
+
   assert(ArgNo == CS.arg_size() && "sanity check");
 
-  return Changed;
+  if (Indices.empty())
+    return false;
+
+  AttributeSet AS = CS.getAttributes();
+  LLVMContext &Ctx = CS.getInstruction()->getContext();
+  AS = AS.addAttribute(Ctx, Indices, Attribute::get(Ctx, Attribute::NonNull));
+  CS.setAttributes(AS);
+
+  return true;
 }
 
 Constant *CorrelatedValuePropagation::getConstantAt(Value *V, Instruction *At) {
   if (Constant *C = LVI->getConstant(V, At->getParent(), At))
     return C;
 
   // TODO: The following really should be sunk inside LVI's core algorithm, or
   // at least the outer shims around such.