[StandardInstrumentations] Verify function doesn't change if analyses are preserved

[aeubanks]

Summary

Reuse StructuralHash and allow it to be used in non-expensive checks builds.

Move PreservedAnalysisChecker further down StandardInstrumentations so other Instrumentations (e.g. printing) have a chance to run before PreservedAnalysisChecker crashes.

[yrouban]

Looks good in general, but it would be better to have this patch split into several smaller patches: renaming NFC, InstructionCounter intro, one for each particular pass fix.

llvm/lib/Passes/StandardInstrumentations.cpp

1076

may be rename to Value?

2201

I think the time profiling pass has to be the last one.

[nikic]

Please split out the fixes to individual passes.

llvm/lib/Passes/StandardInstrumentations.cpp

46–47

Better move the default behind EXPENSIVE_CHECKS.

1072

Instead of instruction count, it would be better to use StructuralHash. It exists for exactly this purpose.

llvm/lib/Transforms/Coroutines/CoroCleanup.cpp

133 ↗

(On Diff #504895)

Can preserve CFG here.

llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp

568 ↗

(On Diff #504895)

Can preserve CFG here.

616 ↗

(On Diff #504895)

Should return from salvageKnowledge whether something was salvaged...

[aeubanks]

split out other changes, use StructuralHash instead

[nikic]

nontrivial-unswitch-markloopasdeleted.ll failure looks legit.

llvm/lib/Passes/StandardInstrumentations.cpp

1121–1131

Hm, aren't we going to skip the CFG check below if only CFGAnalyses are preserved (but not AllAnalyses)?

[aeubanks]

rebase after cleanups
fix tests

[aeubanks]

llvm/lib/Passes/StandardInstrumentations.cpp

1121–1131

no longer a worry after D146096

[nikic]

LG

[uabelho]

The improved verification found this: https://github.com/llvm/llvm-project/issues/61574

llvm/include/llvm/IR/StructuralHash.h

-//===- llvm/IR/StructuralHash.h - IR Hash for expensive checks --*- C++ -*-===//
+//===- llvm/IR/StructuralHash.h - IR Hashing --------------------*- 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/IR/StructuralHash.cpp

-//===-- StructuralHash.cpp - IR Hash for expensive checks -------*- C++ -*-===//
+//===-- StructuralHash.cpp - IR Hashing -------------------------*- 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 {
uint64_t llvm::StructuralHash(const Function &F) {
   return H.getHash();
 }
 
 uint64_t llvm::StructuralHash(const Module &M) {
   StructuralHashImpl H;
   H.update(M);
   return H.getHash();
 }
-
-#endif

llvm/lib/Passes/StandardInstrumentations.cpp

 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassInstrumentation.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PrintPasses.h"
+#include "llvm/IR/StructuralHash.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/CrashRecoveryContext.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/GraphWriter.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/raw_ostream.h"
 #include <unordered_map>
 #include <unordered_set>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 static cl::opt<bool> VerifyAnalysisInvalidation("verify-analysis-invalidation",
                                                 cl::Hidden,
 #ifdef EXPENSIVE_CHECKS
                                                 cl::init(true)
 #else
                                                 cl::init(false)
 #endif
 );
 
public:
   /// Run the analysis pass over a function and produce CFG.
   Result run(Function &F, FunctionAnalysisManager &FAM) {
     return Result(&F, /* TrackBBLifetime */ true);
   }
 };
 
 AnalysisKey PreservedCFGCheckerAnalysis::Key;
 
+struct PreservedFunctionHashAnalysis
+    : public AnalysisInfoMixin<PreservedFunctionHashAnalysis> {
+  static AnalysisKey Key;
+
+  struct FunctionHash {
+    uint64_t Hash;
+  };
+
+  using Result = FunctionHash;
+
+  Result run(Function &F, FunctionAnalysisManager &FAM) {
+    return Result{StructuralHash(F)};
+  }
+};
+
+AnalysisKey PreservedFunctionHashAnalysis::Key;
+
 bool PreservedCFGCheckerInstrumentation::CFG::invalidate(
     Function &F, const PreservedAnalyses &PA,
     FunctionAnalysisManager::Invalidator &) {
   auto PAC = PA.getChecker<PreservedCFGCheckerAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
            PAC.preservedSet<CFGAnalyses>());
 }
 
 void PreservedCFGCheckerInstrumentation::registerCallbacks(
     PassInstrumentationCallbacks &PIC, FunctionAnalysisManager &FAM) {
   if (!VerifyAnalysisInvalidation)
     return;
 
   FAM.registerPass([&] { return PreservedCFGCheckerAnalysis(); });
+  FAM.registerPass([&] { return PreservedFunctionHashAnalysis(); });
 
   PIC.registerBeforeNonSkippedPassCallback(
       [this, &FAM](StringRef P, Any IR) {
 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
         assert(&PassStack.emplace_back(P));
 #endif
         (void)this;
         const auto **F = any_cast<const Function *>(&IR);
         if (!F)
           return;
 
         // Make sure a fresh CFG snapshot is available before the pass.
         FAM.getResult<PreservedCFGCheckerAnalysis>(*const_cast<Function *>(*F));
+        FAM.getResult<PreservedFunctionHashAnalysis>(
+            *const_cast<Function *>(*F));
       });
 
   PIC.registerAfterPassInvalidatedCallback(
       [this](StringRef P, const PreservedAnalyses &PassPA) {
 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
         assert(PassStack.pop_back_val() == P &&
                "Before and After callbacks must correspond");
 #endif
         (void)this;
       });
 
   PIC.registerAfterPassCallback([this, &FAM](StringRef P, Any IR,
                                              const PreservedAnalyses &PassPA) {
 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
     assert(PassStack.pop_back_val() == P &&
            "Before and After callbacks must correspond");
 #endif
     (void)this;
 
-    const auto **F = any_cast<const Function *>(&IR);
-    if (!F)
+    const auto **MaybeF = any_cast<const Function *>(&IR);
+    if (!MaybeF)
       return;
+    Function &F = *const_cast<Function *>(*MaybeF);
+
+    if (auto *HashBefore =
+            FAM.getCachedResult<PreservedFunctionHashAnalysis>(F)) {
+      if (HashBefore->Hash != StructuralHash(F)) {
+        report_fatal_error(formatv(
+            "Function @{0} changed by {1} without invalidating analyses",
+            F.getName(), P));
+      }
+    }
 
     auto CheckCFG = [](StringRef Pass, StringRef FuncName,
                        const CFG &GraphBefore, const CFG &GraphAfter) {
       if (GraphAfter == GraphBefore)
         return;
 
       dbgs() << "Error: " << Pass
              << " does not invalidate CFG analyses but CFG changes detected in "
                 "function @"
              << FuncName << ":\n";
       CFG::printDiff(dbgs(), GraphBefore, GraphAfter);
       report_fatal_error(Twine("CFG unexpectedly changed by ", Pass));
     };
 
-    if (auto *GraphBefore = FAM.getCachedResult<PreservedCFGCheckerAnalysis>(
-            *const_cast<Function *>(*F)))
-      CheckCFG(P, (*F)->getName(), *GraphBefore,
-               CFG(*F, /* TrackBBLifetime */ false));
+    if (auto *GraphBefore = FAM.getCachedResult<PreservedCFGCheckerAnalysis>(F))
+      CheckCFG(P, F.getName(), *GraphBefore,
+               CFG(&F, /* TrackBBLifetime */ false));
   });
 }
 
 void VerifyInstrumentation::registerCallbacks(
     PassInstrumentationCallbacks &PIC) {
   PIC.registerAfterPassCallback(
       [this](StringRef P, Any IR, const PreservedAnalyses &PassPA) {
         if (isIgnored(P) || P == "VerifierPass")

 
 void StandardInstrumentations::registerCallbacks(
     PassInstrumentationCallbacks &PIC, FunctionAnalysisManager *FAM) {
   PrintIR.registerCallbacks(PIC);
   PrintPass.registerCallbacks(PIC);
   TimePasses.registerCallbacks(PIC);
   OptNone.registerCallbacks(PIC);
   OptPassGate.registerCallbacks(PIC);
-  if (FAM)
-    PreservedCFGChecker.registerCallbacks(PIC, *FAM);
   PrintChangedIR.registerCallbacks(PIC);
   PseudoProbeVerification.registerCallbacks(PIC);
   if (VerifyEach)
     Verify.registerCallbacks(PIC);
   PrintChangedDiff.registerCallbacks(PIC);
   WebsiteChangeReporter.registerCallbacks(PIC);
-
   ChangeTester.registerCallbacks(PIC);
-
   PrintCrashIR.registerCallbacks(PIC);
+  if (FAM)
+    PreservedCFGChecker.registerCallbacks(PIC, *FAM);
+
   // TimeProfiling records the pass running time cost.
   // Its 'BeforePassCallback' can be appended at the tail of all the
   // BeforeCallbacks by calling `registerCallbacks` in the end.
   // Its 'AfterPassCallback' is put at the front of all the
   // AfterCallbacks by its `registerCallbacks`. This is necessary
   // to ensure that other callbacks are not included in the timings.
   TimeProfilingPasses.registerCallbacks(PIC);
 }
 
 template class ChangeReporter<std::string>;
 template class TextChangeReporter<std::string>;
 
 template class BlockDataT<EmptyData>;
 template class FuncDataT<EmptyData>;
 template class IRDataT<EmptyData>;
 template class ChangeReporter<IRDataT<EmptyData>>;
 template class TextChangeReporter<IRDataT<EmptyData>>;
 template class IRComparer<EmptyData>;
 
 } // namespace llvm

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-markloopasdeleted.ll

-; RUN: opt < %s -enable-loop-distribute -passes='loop-distribute,loop-mssa(simple-loop-unswitch<nontrivial>),loop-distribute' -o /dev/null -S -verify-analysis-invalidation -debug-pass-manager=verbose 2>&1 | FileCheck %s
+; RUN: opt < %s -enable-loop-distribute -passes='loop-distribute,loop-mssa(simple-loop-unswitch<nontrivial>),loop-distribute' -o /dev/null -S -verify-analysis-invalidation=0 -debug-pass-manager=verbose 2>&1 | FileCheck %s
 
 
 ; Running loop-distribute will result in LoopAccessAnalysis being required and
 ; cached in the LoopAnalysisManagerFunctionProxy.
 ;
 ; CHECK: Running analysis: LoopAccessAnalysis on test6
 
 

 
 ; When running loop-distribute the second time we can see that loop_a_inner
 ; isn't analysed because the loop no longer exists (instead we find a new loop,
 ; loop_a_inner.us). This kind of verifies that it was correct to remove the
 ; loop_a_inner related analysis above.
 ;
 ; CHECK: Invalidating analysis: LoopAccessAnalysis on test6
 ; CHECK-NEXT: Running pass: LoopDistributePass on test6
-; CHECK-NEXT: Running analysis: PreservedCFGCheckerAnalysis on test6
 ; CHECK-NEXT: Running analysis: LoopAccessAnalysis on test6
 
 
 define i32 @test6(ptr %ptr, i1 %cond1, ptr %a.ptr, ptr %b.ptr) {
 entry:
   br label %loop_begin
 
 loop_begin:

llvm/unittests/IR/PassManagerTest.cpp

TEST_F(PassManagerTest, FunctionPassCFGCheckerWrapped) {
   FAM.registerPass([&] { return TargetIRAnalysis(); });
 
   FunctionPassManager InnerFPM;
   InnerFPM.addPass(SimplifyCFGPass());
 
   FPM.addPass(TestSimplifyCFGWrapperPass(InnerFPM));
   FPM.run(*F, FAM);
 }
+
+#ifdef EXPENSIVE_CHECKS
+
+struct WrongFunctionPass : PassInfoMixin<WrongFunctionPass> {
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM) {
+    F.getEntryBlock().begin()->eraseFromParent();
+    return PreservedAnalyses::all();
+  }
+  static StringRef name() { return "WrongFunctionPass"; }
+};
+
+TEST_F(PassManagerTest, FunctionAnalysisMissedInvalidation) {
+  LLVMContext Context;
+  auto M = parseIR(Context, "define void @foo() {\n"
+                            "  %a = add i32 0, 0\n"
+                            "  ret void\n"
+                            "}\n");
+
+  FunctionAnalysisManager FAM;
+  PassInstrumentationCallbacks PIC;
+  StandardInstrumentations SI(M->getContext(), /*DebugLogging*/ false);
+  SI.registerCallbacks(PIC, &FAM);
+  FAM.registerPass([&] { return PassInstrumentationAnalysis(&PIC); });
+
+  FunctionPassManager FPM;
+  FPM.addPass(WrongFunctionPass());
+
+  auto *F = M->getFunction("foo");
+  EXPECT_DEATH(FPM.run(*F, FAM), "Function @foo changed by WrongFunctionPass without invalidating analyses");
+}
+
+#endif
+
 }