[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

451

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

453

Start function names with a lowercase letter.

456

Factor TheUse.getUser() to a variable.

[loladiro]

lib/IR/Verifier.cpp

451

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

455

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)?

460

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

492

This can also iterate over users, no?

[loladiro]

lib/IR/Verifier.cpp

455

Yep.

460

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

503

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

lib/IR/Verifier.cpp

#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 CB1, typename CB2>
+static void
+ForEachInstructionAndFunctionUser(const Use &TheUse,
+                                  SmallPtrSet<const Value *, 32> &Visited,
+                                  CB1 &&callback1, CB2 &&callback2) {
+  if (!Visited.insert(TheUse.getUser()).second)
+    return;
+  if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser()))
+    callback1(I);
+  else if (Function *F = dyn_cast<Function>(TheUse.getUser()))
+    callback2(F);
+  else
+    for (const Use &TheNextUse : TheUse.getUser()->uses())
+      ForEachInstructionAndFunctionUser(TheNextUse, Visited, callback1,
+                                        callback2);
+}
 
 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())
+    ForEachInstructionAndFunctionUser(
+        TheUse, Visited,
+        [&](Instruction *I) {
+          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());
+        },
+        [&](Function *F) {
+          Assert(F->getParent() == GV.getParent(),
+                 "Global is used by function in a different module", &GV,
+                 GV.getParent(), F, F->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, InvalidRetAttribute) {
   EXPECT_TRUE(StringRef(ErrorOS.str()).startswith(
       "Attribute 'uwtable' only applies to functions!"));
 }
 
 TEST(VerifierTest, CrossModuleRef) {
   LLVMContext &C = getGlobalContext();
   Module M1("M1", C);
   Module M2("M2", C);
-  Module M3("M2", C);
+  Module M3("M3", C);
   FunctionType *FTy = FunctionType::get(Type::getInt32Ty(C), /*isVarArg=*/false);
   Function *F1 = cast<Function>(M1.getOrInsertFunction("foo1", FTy));
   Function *F2 = cast<Function>(M2.getOrInsertFunction("foo2", FTy));
   Function *F3 = cast<Function>(M3.getOrInsertFunction("foo3", FTy));
 
   BasicBlock *Entry1 = BasicBlock::Create(C, "entry", F1);
   BasicBlock *Entry3 = BasicBlock::Create(C, "entry", F3);
 
   // BAD: Referencing function in another module
   CallInst::Create(F2,"call",Entry1);
 
   // BAD: Referencing personality routine in another module
   F3->setPersonalityFn(F2);
 
   // 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())
+                  .equals("Global is used by function in a different module\n"
+                          "i32 ()* @foo2\n"
+                          "; ModuleID = 'M2'\n"
+                          "i32 ()* @foo3\n"
+                          "; ModuleID = 'M3'\n"
+                          "Global is referenced in a different module!\n"
+                          "i32 ()* @foo2\n"
+                          "; ModuleID = 'M2'\n"
+                          "  %call = call i32 @foo2()\n"
+                          "i32 ()* @foo1\n"
+                          "; ModuleID = 'M1'\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"));