Verify the LLVMContext for Attributes.

[nickwasmer]

Summary

Attributes don't know their parent Context. Instead of using extra memory to store that, we have the verifier query the Attribute with a prospective parent LLVMContext and the Attribute checks whether its contents exists in that context's FoldingSet.

There's an oddity I noticed while working on this patch. There are methods to create attributes with types which also take a context. If I check for nullptr Type* in attributes in the verifier, there are none in a run of the llvm testsuite. However, the C API does create these things in LLVMCreateEnumAttribute. I'm not sure what the intended state is here, but I'm thinking that the Attribute::get* functions that take Context+Type should either remove the Context or assert that the Type's Context matches the supplied Context when the Type is not null.

[nickwasmer]

Apply clang-format suggestions, mostly just silence clang-tidy suggestions.

[nickwasmer]

Ping!

This patch includes a change to FoldingSet. Does it make sense for FoldingSet to have a Contains() method? Was it previously missing because we didn't need it yet, or was it missing because not having it makes for a better API? Should that be broken out into its own patch or

This patch adds "hasParentContext" which is a new way of querying the context. Is this an acceptable way API to add? Do we need to do this unusual API or is there a way we could have added a normal "getParent" method to these instead?

Is verifying the contexts of attributes worth adding the above methods? FWIW, I think that a front-end could have a bug where they generate IR using one LLVMContext per source function, but build the attributes for their builtin functions on the first LLVMContext and cache it. The Verifier won't catch the cross-LLVMContext usage before this patch.

[craig.topper]

Other than it not being "const" is there any reason you couldn't use FindNodeOrInsertPos to implement contains?

[nickwasmer]

Other than it not being "const" is there any reason you couldn't use FindNodeOrInsertPos to implement contains?

That works, I don't recall why I thought it didn't. With that, I can remove the changes to FoldingSet entirely. Thank you!

[nickwasmer]

Ping!

[nickwasmer]

Ping!

Is hasParentContext(LLVMContext &C) an acceptable name for what it does? Is there a better one?

Is there a better way to do this? Is it worth adding an API that is different from the common getContext() just to save the pointer and add the capability to the verifier?

[dexonsmith]

LGTM, assuming @craig.topper is also happy.

[craig.topper]

LGTM

[nikic]

This change has a noticable compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=8f683366afcfd7c03faea615d1529a0014d7dbde&to=244d9d6e41db71e76eeb55e56d84f658b3f56681&stat=instructions

Only LTO is affected, I believe because release builds only run the verifier when importing LTO bitcode. Link time for tramp3d-v4 increases by 1%, which seems rather excessive for a verifier addition.

Something to keep in mind is that FoldingSet lookups are quite expensive, and you're doing a lot of them here, because you will be re-checking the same attributes/sets/lists across many functions.

[dexonsmith]

In D99362#2696039, @nikic wrote:

This change has a noticable compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=8f683366afcfd7c03faea615d1529a0014d7dbde&to=244d9d6e41db71e76eeb55e56d84f658b3f56681&stat=instructions

Only LTO is affected, I believe because release builds only run the verifier when importing LTO bitcode. Link time for tramp3d-v4 increases by 1%, which seems rather excessive for a verifier addition.

Agreed, that seems too high!

Something to keep in mind is that FoldingSet lookups are quite expensive, and you're doing a lot of them here, because you will be re-checking the same attributes/sets/lists across many functions.

I left a comment inline; I think there's a way to reduce the number of lookups.

llvm/lib/IR/Verifier.cpp

1863–1866

Can the verifier remember in a DenseSet if it has already checked this AttrSet / Attr / etc.?

[nickwasmer]

llvm/lib/IR/Verifier.cpp

1863–1866

Sorta. Note that these types are wrapper types that are passed by copy so we can't just address-compare them. Both AttributeList and Attribute have a way to get a void pointer that uniquely identifies the underlying object, but AttributeSet does not (though we can cheat and ask an AttributeSet to Profile itself in which case we get the hash of the pointer).

I think that we can just cache the AttributeList in a SmallPtrSet. The number of unique attribute lists is a little more than the number of "attributes #? = { ..." at the end of the ll file which is usually pretty small.

[nickwasmer]

The compile time regression fix is up for review at https://reviews.llvm.org/D100738 .

llvm/include/llvm/ADT/FoldingSet.h

public:
 
   using const_iterator = FoldingSetIterator<const T>;
 
   const_iterator begin() const { return const_iterator(Buckets); }
   const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
 
   using bucket_iterator = FoldingSetBucketIterator<T>;
 
-  bucket_iterator bucket_begin(unsigned hash) {
-    return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
+  // NOLINTNEXTLINE(readability-identifier-naming)
+  bucket_iterator bucket_begin(unsigned Hash) {
+    return bucket_iterator(Buckets + (Hash & (NumBuckets - 1)));
   }
 
-  bucket_iterator bucket_end(unsigned hash) {
-    return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
+  // NOLINTNEXTLINE(readability-identifier-naming)
+  bucket_iterator bucket_end(unsigned Hash) {
+    return bucket_iterator(Buckets + (Hash & (NumBuckets - 1)), true);
+  }
+
+  using const_bucket_iterator = FoldingSetBucketIterator<const T>;
+
+  // NOLINTNEXTLINE(readability-identifier-naming)
+  const_bucket_iterator bucket_begin(unsigned Hash) const {
+    return const_bucket_iterator(Buckets + (Hash & (NumBuckets - 1)));
+  }
+
+  // NOLINTNEXTLINE(readability-identifier-naming)
+  const_bucket_iterator bucket_end(unsigned Hash) const {
+    return const_bucket_iterator(Buckets + (Hash & (NumBuckets - 1)), true);
   }
 
   /// reserve - Increase the number of buckets such that adding the
   /// EltCount-th node won't cause a rebucket operation. reserve is permitted
   /// to allocate more space than requested by EltCount.
   void reserve(unsigned EltCount) {
     return FoldingSetBase::reserve(EltCount, Derived::getFoldingSetInfo());
   }
public:
 
   /// InsertNode - Insert the specified node into the folding set, knowing that
   /// it is not already in the folding set.
   void InsertNode(T *N) {
     T *Inserted = GetOrInsertNode(N);
     (void)Inserted;
     assert(Inserted == N && "Node already inserted!");
   }
+
+  /// Contains - Check whether the node is contained in this folding set. For
+  /// performance reasons, this should not be used as a prelude to a mutation,
+  /// the other methods provide combined operations with better performance.
+  // NOLINTNEXTLINE(readability-identifier-naming)
+  bool Contains(T *N) const {
+    FoldingSetNodeID ID;
+    N->Profile(ID);
+    auto Hash = ID.ComputeHash();
+    for (auto BI = bucket_begin(Hash), BE = bucket_end(Hash); BI != BE; ++BI) {
+      if (&*BI == N)
+        return true;
+    }
+    return false;
+  }
 };
 
 //===----------------------------------------------------------------------===//
 /// FoldingSet - This template class is used to instantiate a specialized
 /// implementation of the folding set to the node class T.  T must be a
 /// subclass of FoldingSetNode and implement a Profile function.
 ///
 /// Note that this set type is movable and move-assignable. However, its
public:
 
   /// InsertNode - Insert the specified node into the folding set, knowing that
   /// it is not already in the folding set.
   void InsertNode(T *N) {
     Set.InsertNode(N);
     Vector.push_back(N);
   }
 
+  /// Contains - Check whether the node is contained in this folding set. For
+  /// performance reasons, this should not be used as a prelude to a mutation,
+  /// the other methods provide combined operations with better performance.
+  // NOLINTNEXTLINE(readability-identifier-naming)
+  bool Contains(T *N) const { return Set.Contains(N); }
+
   /// size - Returns the number of nodes in the folding set.
   unsigned size() const { return Set.size(); }
 
   /// empty - Returns true if there are no nodes in the folding set.
   bool empty() const { return Set.empty(); }
 };
 
 //===----------------------------------------------------------------------===//

llvm/include/llvm/IR/Attributes.h

public:
   /// Returns the argument numbers for the vscale_range attribute (or pair(0, 0)
   /// if not known).
   std::pair<unsigned, unsigned> getVScaleRangeArgs() const;
 
   /// The Attribute is converted to a string of equivalent mnemonic. This
   /// is, presumably, for writing out the mnemonics for the assembly writer.
   std::string getAsString(bool InAttrGrp = false) const;
 
+  /// Return true if this attribute belongs to the LLVMContext.
+  bool hasParentContext(LLVMContext &C) const;
+
   /// Equality and non-equality operators.
   bool operator==(Attribute A) const { return pImpl == A.pImpl; }
   bool operator!=(Attribute A) const { return pImpl != A.pImpl; }
 
   /// Less-than operator. Useful for sorting the attributes list.
   bool operator<(Attribute A) const;
 
   void Profile(FoldingSetNodeID &ID) const;
public:
   Type *getByValType() const;
   Type *getStructRetType() const;
   Type *getByRefType() const;
   Type *getPreallocatedType() const;
   std::pair<unsigned, Optional<unsigned>> getAllocSizeArgs() const;
   std::pair<unsigned, unsigned> getVScaleRangeArgs() const;
   std::string getAsString(bool InAttrGrp = false) const;
 
+  /// Return true if this attribute set belongs to the LLVMContext.
+  bool hasParentContext(LLVMContext &C) const;
+
   using iterator = const Attribute *;
 
   iterator begin() const;
   iterator end() const;
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void dump() const;
 #endif
 };
public:
   getAllocSizeArgs(unsigned Index) const;
 
   /// Get the vscale_range argument numbers (or pair(0, 0) if unknown).
   std::pair<unsigned, unsigned> getVScaleRangeArgs(unsigned Index) const;
 
   /// Return the attributes at the index as a string.
   std::string getAsString(unsigned Index, bool InAttrGrp = false) const;
 
+  /// Return true if this attribute list belongs to the LLVMContext.
+  bool hasParentContext(LLVMContext &C) const;
+
   //===--------------------------------------------------------------------===//
   // AttributeList Introspection
   //===--------------------------------------------------------------------===//
 
   using iterator = const AttributeSet *;
 
   iterator begin() const;
   iterator end() const;
public:
   /// Return a raw pointer that uniquely identifies this attribute list.
   void *getRawPointer() const {
     return pImpl;
   }
 
   /// Return true if there are no attributes.
   bool isEmpty() const { return pImpl == nullptr; }
 
+  void print(raw_ostream &O) const;
+
   void dump() const;
 };
 
 //===----------------------------------------------------------------------===//
 /// \class
 /// Provide DenseMapInfo for AttributeList.
 template <> struct DenseMapInfo<AttributeList> {
   static AttributeList getEmptyKey() {

llvm/lib/IR/Attributes.cpp

std::string Result;
       }
     }
     return Result;
   }
 
   llvm_unreachable("Unknown attribute");
 }
 
+bool Attribute::hasParentContext(LLVMContext &C) const {
+  assert(isValid() && "invalid Attribute doesn't refer to any context");
+  return C.pImpl->AttrsSet.Contains(pImpl);
+}
+
 bool Attribute::operator<(Attribute A) const {
   if (!pImpl && !A.pImpl) return false;
   if (!pImpl) return true;
   if (!A.pImpl) return false;
   return *pImpl < *A.pImpl;
 }
 
 void Attribute::Profile(FoldingSetNodeID &ID) const {
std::pair<unsigned, unsigned> AttributeSet::getVScaleRangeArgs() const {
   return SetNode ? SetNode->getVScaleRangeArgs()
                  : std::pair<unsigned, unsigned>(0, 0);
 }
 
 std::string AttributeSet::getAsString(bool InAttrGrp) const {
   return SetNode ? SetNode->getAsString(InAttrGrp) : "";
 }
 
+bool AttributeSet::hasParentContext(LLVMContext &C) const {
+  assert(hasAttributes() && "empty AttributeSet doesn't refer to any context");
+  return C.pImpl->AttrsSetNodes.Contains(SetNode);
+}
+
 AttributeSet::iterator AttributeSet::begin() const {
   return SetNode ? SetNode->begin() : nullptr;
 }
 
 AttributeSet::iterator AttributeSet::end() const {
   return SetNode ? SetNode->end() : nullptr;
 }
 

 
 AttributeSet AttributeList::getAttributes(unsigned Index) const {
   Index = attrIdxToArrayIdx(Index);
   if (!pImpl || Index >= getNumAttrSets())
     return {};
   return pImpl->begin()[Index];
 }
 
+bool AttributeList::hasParentContext(LLVMContext &C) const {
+  assert(!isEmpty() && "an empty attribute list has no parent context");
+  return C.pImpl->AttrsLists.Contains(pImpl);
+}
+
 AttributeList::iterator AttributeList::begin() const {
   return pImpl ? pImpl->begin() : nullptr;
 }
 
 AttributeList::iterator AttributeList::end() const {
   return pImpl ? pImpl->end() : nullptr;
 }
 
 //===----------------------------------------------------------------------===//
 // AttributeList Introspection Methods
 //===----------------------------------------------------------------------===//
 
 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";
+void AttributeList::print(raw_ostream &O) const {
+  O << "PAL[\n";
 
   for (unsigned i = index_begin(), e = index_end(); i != e; ++i) {
     if (getAttributes(i).hasAttributes())
-      dbgs() << "  { " << i << " => " << getAsString(i) << " }\n";
+      O << "  { " << i << " => " << getAsString(i) << " }\n";
   }
 
-  dbgs() << "]\n";
+  O << "]\n";
 }
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void AttributeList::dump() const { print(dbgs()); }
 #endif
 
 //===----------------------------------------------------------------------===//
 // AttrBuilder Method Implementations
 //===----------------------------------------------------------------------===//
 
 // FIXME: Remove this ctor, use AttributeSet.
 AttrBuilder::AttrBuilder(AttributeList AL, unsigned Index) {

llvm/lib/IR/Verifier.cpp

private:
   void Write(const APInt *AI) {
     if (!AI)
       return;
     *OS << *AI << '\n';
   }
 
   void Write(const unsigned i) { *OS << i << '\n'; }
 
+  // NOLINTNEXTLINE(readability-identifier-naming)
+  void Write(const Attribute *A) {
+    if (!A)
+      return;
+    *OS << A->getAsString() << '\n';
+  }
+
+  // NOLINTNEXTLINE(readability-identifier-naming)
+  void Write(const AttributeSet *AS) {
+    if (!AS)
+      return;
+    *OS << AS->getAsString() << '\n';
+  }
+
+  // NOLINTNEXTLINE(readability-identifier-naming)
+  void Write(const AttributeList *AL) {
+    if (!AL)
+      return;
+    AL->print(*OS);
+  }
+
   template <typename T> void Write(ArrayRef<T> Vs) {
     for (const T &V : Vs)
       Write(V);
   }
 
   template <typename T1, typename... Ts>
   void WriteTs(const T1 &V1, const Ts &... Vs) {
     Write(V1);

 
 // Check parameter attributes against a function type.
 // The value V is printed in error messages.
 void Verifier::verifyFunctionAttrs(FunctionType *FT, AttributeList Attrs,
                                    const Value *V, bool IsIntrinsic) {
   if (Attrs.isEmpty())
     return;
 
+  Assert(Attrs.hasParentContext(Context),
+         "Attribute list does not match Module context!", &Attrs);
+  for (const auto &AttrSet : Attrs) {
+    Assert(!AttrSet.hasAttributes() || AttrSet.hasParentContext(Context),
+           "Attribute set does not match Module context!", &AttrSet);
+    for (const auto &A : AttrSet) {
+      Assert(A.hasParentContext(Context),
+             "Attribute does not match Module context!", &A);
+    }
+  }
+
   bool SawNest = false;
   bool SawReturned = false;
   bool SawSRet = false;
   bool SawSwiftSelf = false;
   bool SawSwiftError = false;
 
   // Verify return value attributes.
   AttributeSet RetAttrs = Attrs.getRetAttributes();

llvm/unittests/ADT/FoldingSet.cpp

 
 TEST(FoldingSetTest, SmallReserveChangesNothing) {
   FoldingSet<TrivialPair> Trivial;
   auto OldCapacity = Trivial.capacity();
   Trivial.reserve(OldCapacity - 1);
   EXPECT_EQ(Trivial.capacity(), OldCapacity);
 }
 
+TEST(FoldingSetTest, Contains) {
+  FoldingSet<TrivialPair> Trivial;
+  TrivialPair T(99, 42);
+  EXPECT_FALSE(Trivial.Contains(&T));
+  Trivial.InsertNode(&T);
+  EXPECT_TRUE(Trivial.Contains(&T));
+  TrivialPair T2(99, 42);
+  EXPECT_FALSE(Trivial.Contains(&T2));
+  Trivial.clear();
+  EXPECT_FALSE(Trivial.Contains(&T));
 }
 
+} // end anonymous namespace

llvm/unittests/IR/AttributesTest.cpp

TEST(Attributes, StringRepresentation) {
 
   A = Attribute::getWithByValType(C, nullptr);
   EXPECT_EQ(A.getAsString(), "byval");
 
   A = Attribute::getWithByValType(C, Type::getInt32Ty(C));
   EXPECT_EQ(A.getAsString(), "byval(i32)");
 }
 
+TEST(Attributes, HasParentContext) {
+  LLVMContext C1, C2;
+
+  {
+    Attribute Attr1 = Attribute::get(C1, Attribute::AlwaysInline);
+    Attribute Attr2 = Attribute::get(C2, Attribute::AlwaysInline);
+    EXPECT_TRUE(Attr1.hasParentContext(C1));
+    EXPECT_FALSE(Attr1.hasParentContext(C2));
+    EXPECT_FALSE(Attr2.hasParentContext(C1));
+    EXPECT_TRUE(Attr2.hasParentContext(C2));
+  }
+
+  {
+    AttributeSet AS1 = AttributeSet::get(
+        C1, makeArrayRef(Attribute::get(C1, Attribute::NoReturn)));
+    AttributeSet AS2 = AttributeSet::get(
+        C2, makeArrayRef(Attribute::get(C2, Attribute::NoReturn)));
+    EXPECT_TRUE(AS1.hasParentContext(C1));
+    EXPECT_FALSE(AS1.hasParentContext(C2));
+    EXPECT_FALSE(AS2.hasParentContext(C1));
+    EXPECT_TRUE(AS2.hasParentContext(C2));
+  }
+
+  {
+    AttributeList AL1 = AttributeList::get(C1, 1, Attribute::ZExt);
+    AttributeList AL2 = AttributeList::get(C2, 1, Attribute::ZExt);
+    EXPECT_TRUE(AL1.hasParentContext(C1));
+    EXPECT_FALSE(AL1.hasParentContext(C2));
+    EXPECT_FALSE(AL2.hasParentContext(C1));
+    EXPECT_TRUE(AL2.hasParentContext(C2));
+  }
+}
+
 } // end anonymous namespace

llvm/unittests/IR/VerifierTest.cpp

TEST(VerifierTest, MDNodeWrongContext) {
 
   std::string Error;
   raw_string_ostream ErrorOS(Error);
   EXPECT_TRUE(verifyModule(M, &ErrorOS));
   EXPECT_TRUE(StringRef(ErrorOS.str())
                   .startswith("MDNode context does not match Module context!"));
 }
 
+TEST(VerifierTest, AttributesWrongContext) {
+  LLVMContext C1, C2;
+  Module M1("M", C1);
+  FunctionType *FTy1 =
+      FunctionType::get(Type::getVoidTy(C1), /*isVarArg=*/false);
+  Function *F1 = Function::Create(FTy1, Function::ExternalLinkage, "foo", M1);
+  F1->setDoesNotReturn();
+
+  Module M2("M", C2);
+  FunctionType *FTy2 =
+      FunctionType::get(Type::getVoidTy(C2), /*isVarArg=*/false);
+  Function *F2 = Function::Create(FTy2, Function::ExternalLinkage, "foo", M2);
+  F2->copyAttributesFrom(F1);
+
+  EXPECT_TRUE(verifyFunction(*F2));
+}
+
 } // end anonymous namespace
 } // end namespace llvm