[Verifier] Verifier that a GlobalValue is only used in this Module

[loladiro]

Summary

We already have the inverse verification that we only use globals
that are defined in this module. This essentially catches the
same mistake, but when verifying the module that contains the
definition. There is a moderately annoying corner case caused by
our usage of a parentless ReturnInst to hold prefix/prologue data.
In order to perform correct diagnostics, we need to construct the
inverse map for this on demand. Since that can be expensive, this
inverse mapping is cached in the Verifier class and only constructed
when needed.

[loladiro]

Clang-format everything (sorry forgot before submitting)

[loladiro]

Now that the ReturnInst hack is removed, this can be done much more cleanly.

[loladiro]

Bump @dexonsmith, does this look ok now?

[• rafael]

lib/IR/Verifier.cpp

456

Why do you need a template? Looks like the callbacks always have the name type, no?

458

Start function names with a lowercase letter.

461

Factor TheUse.getUser() to a variable.

[loladiro]

lib/IR/Verifier.cpp

456

Is there a good way to name a C++ lambda (I know about std::function, but AFAIK that has performance implications, so I tend to avoid it)?

[loladiro]

Address review comments and rebase. Rebasing required changing a few uses() to
materialized_uses(). I hope that's the correct thing.

[• rafael]

lib/IR/Verifier.cpp

460

The user is the only thing this function uses.

Can you pass a "Value *User" instead and in the recursive call iterate over users() instead of uses()?
Can you add a comment describing what the function does (recursively wall every indirect user)?

465

How about having a single callback that takes a Value and do the cast in the callback?

493

This can also iterate over users, no?

[loladiro]

lib/IR/Verifier.cpp

460

Yep.

465

My concern was that I already have to check for the type here in order to see whether to call the callback or recurse, so I thought it was cleaner to have two callbacks, but I don't feel very strongly about that.

[• rafael]

How about having a single callback that takes a Value and do the cast

in the callback?

My concern was that I already have to check for the type here in order to

see whether to call the callback or recurse, so I thought it was cleaner to
have two callbacks, but I don't feel very strongly about that.

Why not always call the callback? We have a set to avoid a loop.

Cheers, Rafael

[loladiro]

Switch uses() -> users() and add a comment to explain what the foreach helper is for.

[loladiro]

Make the indirect user walker generic

[loladiro]

Any more comments or is this good to go?

[loladiro]

Bump.

[• rafael]

LGTM with a nit.

lib/IR/Verifier.cpp

504

Nit: There are many calls to GV.getParent(). Don't you have the module being verified handy somewhere?

lib/IR/Verifier.cpp

 //  * A landingpad instruction must be the first non-PHI instruction in the
 //    block.
 //  * Landingpad instructions must be in a function with a personality function.
 //  * All other things that are tested by asserts spread about the code...
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/Verifier.h"
+#include "LLVMContextImpl.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/CallingConv.h"
class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   SmallPtrSet<Instruction *, 16> InstsInThisBlock;
 
   /// \brief Keep track of the metadata nodes that have been checked already.
   SmallPtrSet<const Metadata *, 32> MDNodes;
 
   /// \brief Track unresolved string-based type references.
   SmallDenseMap<const MDString *, const MDNode *, 32> UnresolvedTypeRefs;
 
+  /// \brief Cache the inverse FunctionData map, to avoid having to reconstruct
+  /// it from the forward map every time it's needed.
+  typedef DenseMap<const ReturnInst *, const Function *>
+      InverseFunctionDataMapTy;
+  InverseFunctionDataMapTy InverseFunctionDataMap;
+
   /// \brief The result type for a landingpad.
   Type *LandingPadResultTy;
 
   /// \brief Whether we've seen a call to @llvm.localescape in this function
   /// already.
   bool SawFrameEscape;
 
   /// Stores the count of how many objects were passed to llvm.localescape for a
bool verify(const Function &F) {
     // run this code outside of a pass manager.
     // FIXME: It's really gross that we have to cast away constness here.
     DT.recalculate(const_cast<Function &>(F));
 
     Broken = false;
     // FIXME: We strip const here because the inst visitor strips const.
     visit(const_cast<Function &>(F));
     InstsInThisBlock.clear();
+    InverseFunctionDataMap.clear();
     LandingPadResultTy = nullptr;
     SawFrameEscape = false;
 
     return !Broken;
   }
 
   bool verify(const Module &M) {
     this->M = &M;
for (const StringMapEntry<Comdat> &SMEC : M.getComdatSymbolTable())
       visitComdat(SMEC.getValue());
 
     visitModuleFlags(M);
     visitModuleIdents(M);
 
     // Verify type referneces last.
     verifyTypeRefs();
 
+    InverseFunctionDataMap.clear();
+
     return !Broken;
   }
 
 private:
   // Verification methods...
   void visitGlobalValue(const GlobalValue &GV);
   void visitGlobalVariable(const GlobalVariable &GV);
   void visitGlobalAlias(const GlobalAlias &GA);
#define Assert(C, ...) \
   do { if (!(C)) { CheckFailed(__VA_ARGS__); return; } } while (0)
 
 void Verifier::visit(Instruction &I) {
   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
     Assert(I.getOperand(i) != nullptr, "Operand is null", &I);
   InstVisitor<Verifier>::visit(I);
 }
 
+template <typename CB>
+static void ForEachInstructionUser(const Use &TheUse,
+                                   SmallPtrSet<const Value *, 32> &Visited,
+                                   CB &&callback) {
+  if (!Visited.insert(TheUse.getUser()).second)
+    return;
+  if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser()))
+    callback(I);
+  else
+    for (const Use &TheNextUse : TheUse.getUser()->uses())
+      ForEachInstructionUser(TheNextUse, Visited, callback);
+}
 
 void Verifier::visitGlobalValue(const GlobalValue &GV) {
   Assert(!GV.isDeclaration() || GV.hasExternalLinkage() ||
              GV.hasExternalWeakLinkage(),
          "Global is external, but doesn't have external or weak linkage!", &GV);
 
   Assert(GV.getAlignment() <= Value::MaximumAlignment,
          "huge alignment values are unsupported", &GV);
   Assert(!GV.hasAppendingLinkage() || isa<GlobalVariable>(GV),
          "Only global variables can have appending linkage!", &GV);
 
   if (GV.hasAppendingLinkage()) {
     const GlobalVariable *GVar = dyn_cast<GlobalVariable>(&GV);
     Assert(GVar && GVar->getValueType()->isArrayTy(),
            "Only global arrays can have appending linkage!", GVar);
   }
 
   if (GV.isDeclarationForLinker())
     Assert(!GV.hasComdat(), "Declaration may not be in a Comdat!", &GV);
+
+  // Verify that this GlobalValue is only used in this module.
+  // This map is used to avoid visiting uses twice. We can arrive at a user
+  // twice, if they have multiple operands. In particular for very large
+  // constant expressions, we can arrive at a particular user many times.
+  SmallPtrSet<const Value *, 32> Visited;
+  for (const Use &TheUse : GV.uses())
+    ForEachInstructionUser(TheUse, Visited, [&](Instruction *I) {
+      if (isa<ReturnInst>(I) && !I->getParent()) {
+        // This could be one of the ReturnInsts used to track prefix/prologue
+        // data. However, to be able to tell we need to construct the inverse
+        // mapping. Since it is expensive to construct, we cache it in the
+        // Verifier.
+        if (InverseFunctionDataMap.empty()) {
+          for (auto &F : M->functions()) {
+            if (F.hasPrefixData())
+              InverseFunctionDataMap[&*F.getContext()
+                                           .pImpl->PrefixDataMap[&F]] = &F;
+            if (F.hasPrologueData())
+              InverseFunctionDataMap[&*F.getContext()
+                                           .pImpl->PrologueDataMap[&F]] = &F;
+          }
+        }
+        const Function *F = InverseFunctionDataMap[cast<ReturnInst>(I)];
+        if (F) {
+          Assert(F->getParent() == GV.getParent(), "Global is referenced in "
+                                                   "function data of function "
+                                                   "in a different module",
+                 &GV, GV.getParent(), F, F->getParent());
+          return;
+        }
+      }
+      Assert(I->getParent() && I->getParent()->getParent(),
+             "Global is referenced by parentless instruction!", &GV,
+             GV.getParent(), I);
+      Assert(I->getParent()->getParent()->getParent() == GV.getParent(),
+             "Global is referenced in a different module!", &GV, GV.getParent(),
+             I, I->getParent()->getParent(),
+             I->getParent()->getParent()->getParent());
+    });
 }
 
 void Verifier::visitGlobalVariable(const GlobalVariable &GV) {
   if (GV.hasInitializer()) {
     Assert(GV.getInitializer()->getType() == GV.getType()->getElementType(),
            "Global variable initializer type does not match global "
            "variable type!",
            &GV);

unittests/IR/VerifierTest.cpp

TEST(VerifierTest, CrossModuleRef) {
 
   // Fill in the body
   Constant *ConstZero = ConstantInt::get(Type::getInt32Ty(C), 0);
   ReturnInst::Create(C, ConstZero, Entry1);
   ReturnInst::Create(C, ConstZero, Entry3);
 
   std::string Error;
   raw_string_ostream ErrorOS(Error);
-  EXPECT_FALSE(verifyModule(M2, &ErrorOS));
+  EXPECT_TRUE(verifyModule(M2, &ErrorOS));
+  EXPECT_TRUE(StringRef(ErrorOS.str())
+                  .startswith("Global is referenced in a different module!\n"));
+
+  Error.clear();
   EXPECT_TRUE(verifyModule(M1, &ErrorOS));
   EXPECT_TRUE(StringRef(ErrorOS.str()).equals(
       "Referencing function in another module!\n"
       "  %call = call i32 @foo2()\n"
       "; ModuleID = 'M1'\n"
       "i32 ()* @foo2\n"
       "; ModuleID = 'M2'\n"));