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

494

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

505

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

include/llvm/IR/Value.h

#endif
   User *user_back() {
     assertModuleIsMaterialized();
     return *materialized_user_begin();
   }
   const User *user_back() const {
     assertModuleIsMaterialized();
     return *materialized_user_begin();
   }
+  iterator_range<user_iterator> materialized_users() {
+    return make_range(materialized_user_begin(), user_end());
+  }
+  iterator_range<const_user_iterator> materialized_users() const {
+    return make_range(materialized_user_begin(), user_end());
+  }
   iterator_range<user_iterator> users() {
     assertModuleIsMaterialized();
-    return make_range(materialized_user_begin(), user_end());
+    return materialized_users();
   }
   iterator_range<const_user_iterator> users() const {
     assertModuleIsMaterialized();
-    return make_range(materialized_user_begin(), user_end());
+    return materialized_users();
   }
 
   /// \brief Return true if there is exactly one user of this value.
   ///
   /// This is specialized because it is a common request and does not require
   /// traversing the whole use list.
   bool hasOneUse() const {
     const_use_iterator I = use_begin(), E = use_end();

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);
 }
 
+// Helper to recursively iterate over indirect users that are
+// associated to a given module (i.e. we pass through constants, etc.
+// but stop at Instructions and Functions)
+static void forEachInstructionAndFunctionUser(
+    const Value *User, SmallPtrSet<const Value *, 32> &Visited,
+    llvm::function_ref<void(const Instruction *)> InstCallback,
+    llvm::function_ref<void(const Function *)> FuncCallback) {
+  if (!Visited.insert(User).second)
+    return;
+  if (const Instruction *I = dyn_cast<Instruction>(User))
+    InstCallback(I);
+  else if (const Function *F = dyn_cast<Function>(User))
+    FuncCallback(F);
+  else
+    for (const Value *TheNextUser : User->materialized_users())
+      forEachInstructionAndFunctionUser(TheNextUser, Visited, InstCallback,
+                                        FuncCallback);
+}
 
 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 Value *TheUser : GV.materialized_users())
+    forEachInstructionAndFunctionUser(
+        TheUser, Visited,
+        [&](const 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());
+        },
+        [&](const 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"));