(Expensive) Check for Loop, SCC and Region pass return status

[serge-sans-paille]

Summary

This generalizes the logic introduced in https://reviews.llvm.org/D80916 to other passes.
It's needed by https://reviews.llvm.org/D86442 to assert passes correctly report their status.

[foad]

Thanks. I don't see anything wrong with this, but I think it needs some more eyes on it.

[jdoerfert]

LGTM

llvm/include/llvm/IR/StructuralHash.h

3

Nit: ^

llvm/lib/IR/StructuralHash.cpp

3

Nit ^

[nikic]

llvm/lib/Analysis/CallGraphSCCPass.cpp

470

This will probably cause an unused variable warning in NDEBUG builds.

[serge-sans-paille]

Take review into account

[nikic]

llvm/include/llvm/IR/StructuralHash.h

29–30

Style nit: I believe LLVM uses leading const where possible.

llvm/lib/Analysis/CallGraphSCCPass.cpp

480

There is a mismatch between #if checks here. Above only EXPENSIVE_CHECKS is checked, here !NDEBUG is checked as well.

Aren't we guaranteed that !NDEBUG if EXPENSIVE_CHECKS is set? In any case, both should be consistent.

484

Style nit: Typically llvm_unreachable() is used instead of assert(false).

[serge-sans-paille]

Take into account @nikic review.

[nikic]

LGTM

[MaskRay]

llvm/lib/IR/StructuralHash.cpp

72

Probably not worth changing now.... many older functions are capitalized but they are in conflict with the lowerCase style for new functions

[uabelho]

llvm/lib/IR/StructuralHash.cpp

51

Hi!
What if the BB doesn't have a terminator at all? Then Term will be nullptr which I don't think is good..

(This happens for us in the unit test PassManager.CallGraphUpdater0 with expensive checks when we run in our downstream clone)

[fhahn]

llvm/lib/IR/StructuralHash.cpp

51

I'd assume this should only be called for valid IR, which means there must be terminator?

Unrelated, but could this just be something like for (auto &Succ : successors(BB)) {?

[jdoerfert]

llvm/lib/IR/StructuralHash.cpp

51

I'd assume this should only be called for valid IR, which means there must be terminator?

Yes. We cannot harden this for broken IR (without good reason). @uabelho What pass breaks the IR?

[uabelho]

llvm/lib/IR/StructuralHash.cpp

51

I see. Thanks!

(The testcase was originally not behaving well (it inserted a non-terminator after the terminator in a bb), but that was fixed in 3667d87. Unfortunately we have lost that fix downstream during some EXPENSIVE_CHECKS fiddling we've done and then ran into this problem.)

No need to change the successor iteration then.

Thanks again!

llvm/include/llvm/IR/StructuralHash.h

+//===- llvm/IR/StructuralHash.h - IR Hash for expensive checks --*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides hashing of the LLVM IR structure to be used to check
+// Passes modification status.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_STRUCTURALHASH_H
+#define LLVM_IR_STRUCTURALHASH_H
+
+#ifdef EXPENSIVE_CHECKS
+
+#include <cstdint>
+
+// This header is only meant to be used when -DEXPENSIVE_CHECKS is set
+namespace llvm {
+
+class Function;
+class Module;
+
+uint64_t StructuralHash(const Function &F);
+uint64_t StructuralHash(const Module &M);
+
+} // end namespace llvm
+
+#endif
+
+#endif // LLVM_IR_STRUCTURALHASH_H

llvm/lib/Analysis/CallGraphSCCPass.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManagers.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OptBisect.h"
 #include "llvm/IR/PassTimingInfo.h"
+#include "llvm/IR/StructuralHash.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <string>
 #include <utility>
#ifndef NDEBUG
       OS.flush();
   #endif
       dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
     }
     dumpRequiredSet(P);
 
     initializeAnalysisImpl(P);
 
+#ifdef EXPENSIVE_CHECKS
+    uint64_t RefHash = StructuralHash(CG.getModule());
+#endif
+
     // Actually run this pass on the current SCC.
-    Changed |= RunPassOnSCC(P, CurSCC, CG,
-                            CallGraphUpToDate, DevirtualizedCall);
+    bool LocalChanged =
+        RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall);
 
-    if (Changed)
+    Changed |= LocalChanged;
+
+#ifdef EXPENSIVE_CHECKS
+    if (!LocalChanged && (RefHash != StructuralHash(CG.getModule()))) {
+      llvm::errs() << "Pass modifies its input and doesn't report it: "
+                   << P->getPassName() << "\n";
+      llvm_unreachable("Pass modifies its input and doesn't report it");
+    }
+#endif
+    if (LocalChanged)
       dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
     dumpPreservedSet(P);
 
     verifyPreservedAnalysis(P);
     removeNotPreservedAnalysis(P);
     recordAvailableAnalysis(P);
     removeDeadPasses(P, "", ON_CG_MSG);
   }

llvm/lib/Analysis/LoopPass.cpp

 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/OptBisect.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PassTimingInfo.h"
+#include "llvm/IR/StructuralHash.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-pass-manager"
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       dumpRequiredSet(P);
 
       initializeAnalysisImpl(P);
 
       bool LocalChanged = false;
       {
         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
         TimeRegion PassTimer(getPassTimer(P));
+#ifdef EXPENSIVE_CHECKS
+        uint64_t RefHash = StructuralHash(F);
+#endif
         LocalChanged = P->runOnLoop(CurrentLoop, *this);
+
+#ifdef EXPENSIVE_CHECKS
+        if (!LocalChanged && (RefHash != StructuralHash(F))) {
+          llvm::errs() << "Pass modifies its input and doesn't report it: "
+                       << P->getPassName() << "\n";
+          llvm_unreachable("Pass modifies its input and doesn't report it");
+        }
+#endif
+
         Changed |= LocalChanged;
         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);

llvm/lib/Analysis/RegionPass.cpp

 // and transformation passes are derived from RegionPass. RGPassManager is
 // responsible for managing RegionPasses.
 // Most of this code has been COPIED from LoopPass.cpp
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/Analysis/RegionPass.h"
 #include "llvm/IR/OptBisect.h"
 #include "llvm/IR/PassTimingInfo.h"
+#include "llvm/IR/StructuralHash.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "regionpassmgr"
 
 //===----------------------------------------------------------------------===//
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       if (isPassDebuggingExecutionsOrMore()) {
         dumpPassInfo(P, EXECUTION_MSG, ON_REGION_MSG,
                      CurrentRegion->getNameStr());
         dumpRequiredSet(P);
       }
 
       initializeAnalysisImpl(P);
 
+      bool LocalChanged = false;
       {
         PassManagerPrettyStackEntry X(P, *CurrentRegion->getEntry());
 
         TimeRegion PassTimer(getPassTimer(P));
-        Changed |= P->runOnRegion(CurrentRegion, *this);
+#ifdef EXPENSIVE_CHECKS
+        uint64_t RefHash = StructuralHash(F);
+#endif
+        LocalChanged = P->runOnRegion(CurrentRegion, *this);
+
+#ifdef EXPENSIVE_CHECKS
+        if (!LocalChanged && (RefHash != StructuralHash(F))) {
+          llvm::errs() << "Pass modifies its input and doesn't report it: "
+                       << P->getPassName() << "\n";
+          llvm_unreachable("Pass modifies its input and doesn't report it");
+        }
+#endif
+
+        Changed |= LocalChanged;
       }
 
       if (isPassDebuggingExecutionsOrMore()) {
-        if (Changed)
+        if (LocalChanged)
           dumpPassInfo(P, MODIFICATION_MSG, ON_REGION_MSG,
                        skipThisRegion ? "<deleted>" :
                                       CurrentRegion->getNameStr());
         dumpPreservedSet(P);
       }
 
       if (!skipThisRegion) {
         // Manually check that this region is still healthy. This is done

llvm/lib/IR/CMakeLists.txt

add_llvm_component_library(LLVMCore
   Pass.cpp
   PassInstrumentation.cpp
   PassManager.cpp
   PassRegistry.cpp
   PassTimingInfo.cpp
   SafepointIRVerifier.cpp
   ProfileSummary.cpp
   Statepoint.cpp
+  StructuralHash.cpp
   Type.cpp
   TypeFinder.cpp
   Use.cpp
   User.cpp
   Value.cpp
   ValueSymbolTable.cpp
   Verifier.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/IR
 
   LINK_LIBS ${LLVM_PTHREAD_LIB}
 
   DEPENDS
   intrinsics_gen
   )

llvm/lib/IR/LegacyPassManager.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManagers.h"
 #include "llvm/IR/LegacyPassNameParser.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassTimingInfo.h"
+#include "llvm/IR/StructuralHash.h"
 #include "llvm/Support/Chrono.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/Mutex.h"
 #include "llvm/Support/TimeProfiler.h"
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;
 
   bool Changed = false;
#ifdef EXPENSIVE_CHECKS
       uint64_t RefHash = StructuralHash(F);
 #endif
       LocalChanged |= FP->runOnFunction(F);
 
 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
       if (!LocalChanged && (RefHash != StructuralHash(F))) {
         llvm::errs() << "Pass modifies its input and doesn't report it: "
                      << FP->getPassName() << "\n";
-        assert(false && "Pass modifies its input and doesn't report it.");
+        llvm_unreachable("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.

llvm/lib/IR/StructuralHash.cpp

+//===-- StructuralHash.cpp - IR Hash for expensive checks -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+
+#ifdef EXPENSIVE_CHECKS
+
+#include "llvm/IR/StructuralHash.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+
+using namespace llvm;
+
+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(const 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(const Module &M) {
+    for (const Function &F : M)
+      update(F);
+  }
+
+  uint64_t getHash() const { return Hash; }
+};
+
+} // namespace details
+
+} // namespace
+
+uint64_t llvm::StructuralHash(const Function &F) {
+  details::StructuralHash H;
+  H.update(F);
+  return H.getHash();
+}
+
+uint64_t llvm::StructuralHash(const Module &M) {
+  details::StructuralHash H;
+  H.update(M);
+  return H.getHash();
+}
+
+#endif