[LegacyPM] Double check that passes correctly set their Modified status

[serge-sans-paille]

Summary

The approach is simple: if a pass reports that it's not modifying a
Function/Module, compute a loose hash of that Function/Module and compare it
with the original one. If we report no change but there's a hash change, then we
have an error.

This approach misses a lot of change but it's not super intrusive and can
detect most of the simple mistakes.

[foad]

llvm/lib/IR/LegacyPassManager.cpp

1499

This doesn't even compile because the definition of FunctionHash has a capital F.

1557

This is the wrong way round. You want to assert that LocalChanged || RefHash == FunctionHash(F).

[serge-sans-paille]

Fixed and tested implementation

[serge-sans-paille]

Sorry for uploading the previous patch. This one should be OK.

[foad]

llvm/lib/IR/LegacyPassManager.cpp

1668

==

[foad]

I like this and it is certainly useful for finding bugs. I'd like to see it for Loop, Region and SCC passes too. But I don't know if it's fast and/or robust enough to commit and have it enabled as-is.

Is there any other code for hashing Functions and Modules that we could use here instead of rolling our own?

[serge-sans-paille]

In D80916#2071583, @foad wrote:

I like this and it is certainly useful for finding bugs. I'd like to see it for Loop, Region and SCC passes too. But I don't know if it's fast and/or robust enough to commit and have it enabled as-is.

It currently finds a bunch of bugs (passes not correctly reporting modification), I'm trying to fix them iteratively :-)

Is there any other code for hashing Functions and Modules that we could use here instead of rolling our own?

The code is ostly borrowed from the transform utils. We can't have Core depend on Transform, but it's 100% possible to moe them around. I'll do that and update the patch.

[nikic]

In D80916#2071584, @serge-sans-paille wrote:

The code is ostly borrowed from the transform utils. We can't have Core depend on Transform, but it's 100% possible to moe them around. I'll do that and update the patch.

I'm not sure it makes sense to share this code. The hashing in the transform utils is used for function merging, and as such is intentionally rather weak (in the sense that it will let many functions that are different hash to the same value, as the notion of equality in that pass is not that strict). This code on the other hand could hash in more information, to catch more possible issues. (It doesn't have to, but it wouldn't be incorrect to do so.)

[serge-sans-paille]

Use EXPENSIVE_CHECKS.
Fix a test case that was incorrectly adding instruction after the terminator.

[jdoerfert]

I think having a separate hashing here is fine as we will most likely diverge as well. We should, for example, check attributes here to at some point (maybe worth a FIXME). Other than that, I think this looks good.

@nikic I let you finish your review :)

[serge-sans-paille]

All the reviews required to land this without breaking the validation have landed, @jdoerfert / @nikic / @foad I'd be super-happy to land this one before branching.

[foad]

llvm/unittests/IR/LegacyPassManagerTest.cpp

683

Is this change related to the rest of the patch somehow?

[serge-sans-paille]

llvm/unittests/IR/LegacyPassManagerTest.cpp

683

Yes, without this change, the call is added at the end of the entryblock, i.e. after the terminator. It happens that hash computation triggers an assert (indirectly) on that (bad) situation.

[foad]

Looks good to me apart from the comments inline, but I'd like someone else to approve it too.

As a follow-up can we have the same checking for Loop, Region and SCC passes?

llvm/lib/IR/LegacyPassManager.cpp

1492

I don't like having both functionHash and FunctionHash. How about having FunctionHash take the initial hash value as an optional argument that defaults to StructuralHash() ?

[serge-sans-paille]

Take final review into account

[jdoerfert]

LGTM. Thanks for all the hard work on making this possible :)

[serge-sans-paille]

Note: I had to revert this becasue I only tested X86 targe, and other targets suffer from a lot of « don't update return status » error. cc @fhahn

[fhahn]

In D80916#2140861, @serge-sans-paille wrote:

Note: I had to revert this becasue I only tested X86 targe, and other targets suffer from a lot of « don't update return status » error. cc @fhahn

Hmm, where do other targets suffer from those errors? In the various backend pipelines/passes?

[serge-sans-paille]

Hmm, where do other targets suffer from those errors? In the various backend pipelines/passes?

Yes, the culprits where https://reviews.llvm.org/D83457 https://reviews.llvm.org/D83459 and https://reviews.llvm.org/D83460

[fhahn]

In D80916#2141194, @serge-sans-paille wrote:

Hmm, where do other targets suffer from those errors? In the various backend pipelines/passes?

Yes, the culprits where https://reviews.llvm.org/D83457 https://reviews.llvm.org/D83459 and https://reviews.llvm.org/D83460

Sounds good. I can try a build on AArch64 in a bit.

Cross-compiling the test-suite for example should be relatively straight-forward, if you have a linker & libraries for the target architecture (e.g. on linux it should be easy to get the required toolchains for platforms like ARM and AArch64) https://llvm.org/docs/lnt/tests.html#cross-compiling

[serge-sans-paille]

Sounds good. I can try a build on AArch64 in a bit.

Cross-compiling the test-suite for example should be relatively straight-forward, if you have a linker & libraries for the target architecture (e.g. on linux it should be easy to get the required toolchains for platforms like ARM and AArch64) https://llvm.org/docs/lnt/tests.html#cross-compiling

Well, I can trigger the failure locally, it's just that I didn't enable all LLVM_TARGETS during my local builds. I hope cross compiling won't unveil more issues :-)

llvm/lib/IR/LegacyPassManager.cpp

void FPPassManager::dumpPassStructure(unsigned Offset) {
   dbgs().indent(Offset*2) << "FunctionPass Manager\n";
   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     FunctionPass *FP = getContainedPass(Index);
     FP->dumpPassStructure(Offset + 1);
     dumpLastUses(FP, Offset+1);
   }
 }
 
+#ifdef EXPENSIVE_CHECKS
+namespace {
+namespace details {
+
+// Basic hashing mechanism to detect structural change to the IR, used to verify
+// pass return status consistency with actual change. Loosely copied from
+// llvm/lib/Transforms/Utils/FunctionComparator.cpp
+
+class StructuralHash {
+  uint64_t Hash = 0x6acaa36bef8325c5ULL;
+
+  void update(uint64_t V) { Hash = hashing::detail::hash_16_bytes(Hash, V); }
+
+public:
+  StructuralHash() = default;
+
+  void update(Function &F) {
+    if (F.empty())
+      return;
+
+    update(F.isVarArg());
+    update(F.arg_size());
+
+    SmallVector<const BasicBlock *, 8> BBs;
+    SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
+
+    BBs.push_back(&F.getEntryBlock());
+    VisitedBBs.insert(BBs[0]);
+    while (!BBs.empty()) {
+      const BasicBlock *BB = BBs.pop_back_val();
+      update(45798); // Block header
+      for (auto &Inst : *BB)
+        update(Inst.getOpcode());
+
+      const Instruction *Term = BB->getTerminator();
+      for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
+        if (!VisitedBBs.insert(Term->getSuccessor(i)).second)
+          continue;
+        BBs.push_back(Term->getSuccessor(i));
+      }
+    }
+  }
+
+  void update(Module &M) {
+    for (Function &F : M)
+      update(F);
+  }
+
+  uint64_t getHash() const { return Hash; }
+};
+
+} // namespace details
+
+uint64_t StructuralHash(Function &F) {
+  details::StructuralHash H;
+  H.update(F);
+  return H.getHash();
+}
+
+uint64_t StructuralHash(Module &M) {
+  details::StructuralHash H;
+  H.update(M);
+  return H.getHash();
+}
+
+} // end anonymous namespace
+
+#endif
 
 /// Execute all of the passes scheduled for execution by invoking
 /// runOnFunction method.  Keep track of whether any of the passes modifies
 /// the function, and if so, return true.
 bool FPPassManager::runOnFunction(Function &F) {
   if (F.isDeclaration())
     return false;
 
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
     dumpRequiredSet(FP);
 
     initializeAnalysisImpl(FP);
 
     {
       PassManagerPrettyStackEntry X(FP, F);
       TimeRegion PassTimer(getPassTimer(FP));
+#ifdef EXPENSIVE_CHECKS
+      uint64_t RefHash = StructuralHash(F);
+#endif
       LocalChanged |= FP->runOnFunction(F);
+
+#ifdef EXPENSIVE_CHECKS
+      assert((LocalChanged || (RefHash == StructuralHash(F))) &&
+             "Pass modifies its input and doesn't report it.");
+#endif
+
       if (EmitICRemark) {
         unsigned NewSize = F.getInstructionCount();
 
         // Update the size of the function, emit a remark, and update the size
         // of the module.
         if (NewSize != FunctionSize) {
           int64_t Delta = static_cast<int64_t>(NewSize) -
                           static_cast<int64_t>(FunctionSize);
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     dumpRequiredSet(MP);
 
     initializeAnalysisImpl(MP);
 
     {
       PassManagerPrettyStackEntry X(MP, M);
       TimeRegion PassTimer(getPassTimer(MP));
 
+#ifdef EXPENSIVE_CHECKS
+      uint64_t RefHash = StructuralHash(M);
+#endif
+
       LocalChanged |= MP->runOnModule(M);
+
+#ifdef EXPENSIVE_CHECKS
+      assert((LocalChanged || (RefHash == StructuralHash(M))) &&
+             "Pass modifies its input and doesn't report it.");
+#endif
+
       if (EmitICRemark) {
         // Update the size of the module.
         unsigned ModuleCount = M.getInstructionCount();
         if (ModuleCount != InstrCount) {
           int64_t Delta = static_cast<int64_t>(ModuleCount) -
                           static_cast<int64_t>(InstrCount);
           emitInstrCountChangedRemark(MP, M, Delta, InstrCount,
                                       FunctionToInstrCount);

llvm/unittests/IR/LegacyPassManagerTest.cpp

TEST(PassManager, CallGraphUpdater0) {
       //                        these functions when we visited SCC#1)
       // SCC#5: indirect call node
 
       LLVMContext Context;
       std::unique_ptr<Module> M(makeLLVMModule(Context));
       ASSERT_EQ(M->getFunctionList().size(), 4U);
       Function *F = M->getFunction("test2");
       Function *SF = splitSimpleFunction(*F);
-      CallInst::Create(F, "", &SF->getEntryBlock());
+      CallInst::Create(F, "", &*SF->getEntryBlock().getFirstInsertionPt());
       ASSERT_EQ(M->getFunctionList().size(), 5U);
       CGModifierPass *P = new CGModifierPass();
       legacy::PassManager Passes;
       Passes.add(P);
       Passes.run(*M);
       ASSERT_EQ(P->SetupWorked, 1U);
       ASSERT_EQ(P->NumSCCs, 4U);
       ASSERT_EQ(P->NumFns, 6U);