Index: llvm/include/llvm/Passes/StandardInstrumentations.h
===================================================================
--- llvm/include/llvm/Passes/StandardInstrumentations.h
+++ llvm/include/llvm/Passes/StandardInstrumentations.h
@@ -15,10 +15,12 @@
 #ifndef LLVM_PASSES_STANDARDINSTRUMENTATIONS_H
 #define LLVM_PASSES_STANDARDINSTRUMENTATIONS_H
 
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/PassInstrumentation.h"
 #include "llvm/IR/PassTimingInfo.h"
+#include "llvm/Support/CommandLine.h"
 
 #include <string>
 #include <utility>
@@ -65,12 +67,34 @@
   bool DebugLogging;
 };
 
+class BasicBlock;
+class Function;
+
+class PreservedCFGCheckerInstrumentation {
+public:
+  // CFG is a map from BasicBlock to a set of its successors. It is important
+  // that the set is unordered because order of succesors may be changed.
+  using CFG = DenseMap<const BasicBlock *, SmallSet<const BasicBlock *, 4>>;
+
+private:
+  SmallVector<Optional<CFG>, 8> GraphStackBefore;
+  SmallVector<StringRef, 8> PassStack;
+
+  CFG buildGraph(const Function *F);
+  void printCFGdiff(const CFG &Before, const CFG &After) const;
+
+public:
+  static cl::opt<bool> VerifyPreservedCFG;
+  void registerCallbacks(PassInstrumentationCallbacks &PIC);
+};
+
 /// This class provides an interface to register all the standard pass
 /// instrumentations and manages their state (if any).
 class StandardInstrumentations {
   PrintIRInstrumentation PrintIR;
   TimePassesHandler TimePasses;
   OptNoneInstrumentation OptNone;
+  PreservedCFGCheckerInstrumentation PreservedCFGChecker;
 
 public:
   StandardInstrumentations(bool DebugLogging)
Index: llvm/lib/Passes/StandardInstrumentations.cpp
===================================================================
--- llvm/lib/Passes/StandardInstrumentations.cpp
+++ llvm/lib/Passes/StandardInstrumentations.cpp
@@ -29,12 +29,22 @@
 
 using namespace llvm;
 
+#define DEBUG_TYPE "stdinstrumentations"
+
 // TODO: remove once all required passes are marked as such.
 static cl::opt<bool>
     EnableOptnone("enable-npm-optnone", cl::init(false),
                   cl::desc("Enable skipping optional passes optnone functions "
                            "under new pass manager"));
 
+cl::opt<bool> PreservedCFGCheckerInstrumentation::VerifyPreservedCFG(
+    "verify-cfg-preserved", cl::Hidden,
+#ifdef NDEBUG
+    cl::init(false));
+#else
+    cl::init(true));
+#endif
+
 namespace {
 
 /// Extracting Module out of \p IR unit. Also fills a textual description
@@ -278,9 +288,104 @@
   return true;
 }
 
+PreservedCFGCheckerInstrumentation::CFG
+PreservedCFGCheckerInstrumentation::buildGraph(const Function *F) {
+  CFG Result;
+  for (const auto &BB : *F)
+    Result[&BB].insert(succ_begin(&BB), succ_end(&BB));
+  return Result;
+}
+
+void PreservedCFGCheckerInstrumentation::printCFGdiff(
+    const PreservedCFGCheckerInstrumentation::CFG &Before,
+    const PreservedCFGCheckerInstrumentation::CFG &After) const {
+  if (Before.size() != After.size())
+    dbgs() << "Different number of basic blocks: before=" << Before.size()
+           << ", after=" << After.size() << "\n";
+  for (auto &BB : Before) {
+    auto BA = After.find(BB.first);
+    if (BA == After.end())
+      // Must not access BB as it is likely to be deleted. Just print its ptr.
+      dbgs() << "Block @" << BB.first << " is removed\n";
+  }
+
+  for (auto &BA : After) {
+    auto BB = Before.find(BA.first);
+    if (BB == Before.end()) {
+      dbgs() << "Block " << BA.first->getName() << " is added\n";
+      continue;
+    }
+
+    if (BB->second == BA.second)
+      continue;
+
+    dbgs() << "Different successors of block " << BA.first->getName() << ":\n";
+    dbgs() << "- before: ";
+    for (auto Succ : BB->second)
+      dbgs() << Succ->getName() << ", ";
+    dbgs() << "\n";
+    dbgs() << "-  after: ";
+    for (auto Succ : BA.second)
+      dbgs() << Succ->getName() << ", ";
+    dbgs() << "\n";
+  }
+}
+
+void PreservedCFGCheckerInstrumentation::registerCallbacks(
+    PassInstrumentationCallbacks &PIC) {
+  if (!VerifyPreservedCFG)
+    return;
+
+  PIC.registerBeforePassCallback([this](StringRef P, Any IR) {
+    PassStack.emplace_back(P);
+    if (any_isa<const Function *>(IR))
+      GraphStackBefore.emplace_back(buildGraph(any_cast<const Function *>(IR)));
+    else
+      GraphStackBefore.emplace_back(None);
+    return true;
+  });
+
+  PIC.registerAfterPassSkippedCallback([this](StringRef P, Any IR) {
+    (void)GraphStackBefore.pop_back_val();
+    auto PassName = PassStack.pop_back_val();
+    assert(PassName == P && "Before and After callbacks must correspond");
+  });
+
+  PIC.registerAfterPassInvalidatedCallback(
+      [this](StringRef P, const PreservedAnalyses &PassPA) {
+        (void)GraphStackBefore.pop_back_val();
+        auto PassName = PassStack.pop_back_val();
+        assert(PassName == P && "Before and After callbacks must correspond");
+      });
+
+  PIC.registerAfterPassCallback([this](StringRef P, Any IR,
+                                       const PreservedAnalyses &PassPA) {
+    auto PassName = PassStack.pop_back_val();
+    auto GraphBefore = GraphStackBefore.pop_back_val();
+    assert(PassName == P && "Before and After callbacks must correspond");
+
+    if (!PassPA.allAnalysesInSetPreserved(CFGAnalyses::ID()))
+      return;
+
+    if (any_isa<const Function *>(IR)) {
+      assert(GraphBefore && "Must be built in BeforePassCallback");
+      CFG GraphAfter = buildGraph(any_cast<const Function *>(IR));
+      if (GraphAfter == *GraphBefore)
+        return;
+
+      LLVM_DEBUG(
+          dbgs() << "Error: " << P
+                 << " reported it preserved CFG, but a change is detected:\n");
+      LLVM_DEBUG(printCFGdiff(*GraphBefore, GraphAfter));
+      report_fatal_error(Twine("Preserved CFG changed by ", P));
+    }
+  });
+}
+
 void StandardInstrumentations::registerCallbacks(
     PassInstrumentationCallbacks &PIC) {
   PrintIR.registerCallbacks(PIC);
   TimePasses.registerCallbacks(PIC);
   OptNone.registerCallbacks(PIC);
+  PreservedCFGChecker.registerCallbacks(PIC);
 }