Index: llvm/include/llvm/IR/ValueHandle.h =================================================================== --- llvm/include/llvm/IR/ValueHandle.h +++ llvm/include/llvm/IR/ValueHandle.h @@ -503,6 +503,8 @@ clearValPtr(); } + bool isPoisoned() const { return Poisoned; } + PoisoningVH &operator=(const PoisoningVH &RHS) { if (Poisoned) clearValPtr(); Index: llvm/include/llvm/Passes/StandardInstrumentations.h =================================================================== --- llvm/include/llvm/Passes/StandardInstrumentations.h +++ llvm/include/llvm/Passes/StandardInstrumentations.h @@ -19,6 +19,8 @@ #include "llvm/ADT/StringRef.h" #include "llvm/IR/PassInstrumentation.h" #include "llvm/IR/PassTimingInfo.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/CommandLine.h" #include #include @@ -73,6 +75,50 @@ bool DebugLogging; }; +class BasicBlock; +class Function; + +// CFG is a map BB -> {(Succ, Multiplicity)}, where BB is a non-leaf basic +// block, {(Succ, Multiplicity)} set of all pairs of the block's successors and +// the multiplicity of the edge (BB->Succ). As the mapped sets are unordered the +// order of successors is not tracked by the CFG. In other words this allows +// basic block successors to be swapped by a pass without reporting a CFG +// change. +// CFG can be guarded by basic block tracking pointers in the Graph (BBGuard). +// That is if any of the block is deleted or RAUWed then the CFG is treated +// poisoned and no block pointer of the Graph is used. +struct CFG { + Optional>> BBGuard; + DenseMap> Graph; + + CFG(const Function *F, bool NeedsGuard = false); + + bool operator==(const CFG &G) const { + return !isPoisoned() && !G.isPoisoned() && Graph == G.Graph; + } + + bool isPoisoned() const { + if (BBGuard) + for (auto &BB : *BBGuard) { + if (BB.second.isPoisoned()) + return true; + } + return false; + } + + static void printDiff(raw_ostream &out, const CFG &Before, const CFG &After); +}; + +class PreservedCFGCheckerInstrumentation { +private: + SmallVector, 8> GraphStackBefore; + SmallVector PassStack; + +public: + static cl::opt 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 { @@ -80,6 +126,7 @@ PrintPassInstrumentation PrintPass; TimePassesHandler TimePasses; OptNoneInstrumentation OptNone; + PreservedCFGCheckerInstrumentation PreservedCFGChecker; public: StandardInstrumentations(bool DebugLogging) : PrintPass(DebugLogging) {} Index: llvm/lib/Passes/StandardInstrumentations.cpp =================================================================== --- llvm/lib/Passes/StandardInstrumentations.cpp +++ llvm/lib/Passes/StandardInstrumentations.cpp @@ -30,12 +30,22 @@ using namespace llvm; +#define DEBUG_TYPE "stdinstrumentations" + // TODO: remove once all required passes are marked as such. static cl::opt EnableOptnone("enable-npm-optnone", cl::init(false), cl::desc("Enable skipping optional passes optnone functions " "under new pass manager")); +cl::opt PreservedCFGCheckerInstrumentation::VerifyPreservedCFG( + "verify-cfg-preserved", cl::Hidden, +#ifdef NDEBUG + cl::init(false)); +#else + cl::init(true)); +#endif + // FIXME: Change `-debug-pass-manager` from boolean to enum type. Similar to // `-debug-pass` in legacy PM. static cl::opt @@ -338,10 +348,164 @@ }); } +CFG::CFG(const Function *F, bool NeedsGuard) { + if (NeedsGuard) + BBGuard = DenseMap>(F->size()); + for (const auto &BB : *F) { + if (BBGuard) + BBGuard->try_emplace(intptr_t(&BB), &BB); + for (auto *Succ : successors(&BB)) { + Graph[&BB][Succ]++; + if (BBGuard) + BBGuard->try_emplace(intptr_t(Succ), Succ); + } + } +} + +static void printBBName(raw_ostream &out, const BasicBlock *BB) { + if (BB->hasName()) { + out << BB->getName() << "<" << BB << ">"; + return; + } + + if (!BB->getParent()) { + out << "unnamed_removed<" << BB << ">"; + return; + } + + if (BB == &BB->getParent()->getEntryBlock()) { + out << "entry" + << "<" << BB << ">"; + return; + } + + unsigned FuncOrderBlockNum = 0; + for (auto &FuncBB : *BB->getParent()) { + if (&FuncBB == BB) + break; + FuncOrderBlockNum++; + } + out << "unnamed_" << FuncOrderBlockNum << "<" << BB << ">"; +} + +void CFG::printDiff(raw_ostream &out, const CFG &Before, const CFG &After) { + assert(!After.isPoisoned()); + + // Print function name. + const CFG *FuncGraph = nullptr; + if (After.Graph.size()) + FuncGraph = &After; + else if (!Before.isPoisoned() && Before.Graph.size()) + FuncGraph = &Before; + + if (FuncGraph) + out << "In function @" + << FuncGraph->Graph.begin()->first->getParent()->getName() << "\n"; + + if (Before.isPoisoned()) { + out << "Some blocks were deleted\n"; + return; + } + + // Find and print graph differences. + if (Before.Graph.size() != After.Graph.size()) + out << "Different number of non-leaf basic blocks: before=" + << Before.Graph.size() << ", after=" << After.Graph.size() << "\n"; + + for (auto &BB : Before.Graph) { + auto BA = After.Graph.find(BB.first); + if (BA == After.Graph.end()) { + out << "Non-leaf block "; + printBBName(out, BB.first); + out << " is removed (" << BB.second.size() << " successors)\n"; + } + } + + for (auto &BA : After.Graph) { + auto BB = Before.Graph.find(BA.first); + if (BB == Before.Graph.end()) { + out << "Non-leaf block "; + printBBName(out, BA.first); + out << " is added (" << BA.second.size() << " successors)\n"; + continue; + } + + if (BB->second == BA.second) + continue; + + out << "Different successors of block "; + printBBName(out, BA.first); + out << " (unordered):\n"; + out << "- before (" << BB->second.size() << "): "; + for (auto &SuccB : BB->second) { + printBBName(out, SuccB.first); + if (SuccB.second != 1) + out << "(" << SuccB.second << "), "; + else + out << ", "; + } + out << "\n"; + out << "- after (" << BA.second.size() << "): "; + for (auto &SuccA : BA.second) { + printBBName(out, SuccA.first); + if (SuccA.second != 1) + out << "(" << SuccA.second << "), "; + else + out << ", "; + } + out << "\n"; + } +} + +void PreservedCFGCheckerInstrumentation::registerCallbacks( + PassInstrumentationCallbacks &PIC) { + if (!VerifyPreservedCFG) + return; + + PIC.registerBeforeNonSkippedPassCallback([this](StringRef P, Any IR) { + PassStack.emplace_back(P); + if (any_isa(IR)) + GraphStackBefore.emplace_back(CFG(any_cast(IR))); + else + GraphStackBefore.emplace_back(None); + }); + + 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(IR)) { + assert(GraphBefore && "Must be built in BeforePassCallback"); + CFG GraphAfter(any_cast(IR), false /* NeedsGuard */); + if (GraphAfter == *GraphBefore) + return; + + LLVM_DEBUG( + dbgs() << "Error: " << P + << " reported it preserved CFG, but changes detected:\n"; + CFG::printDiff(dbgs(), *GraphBefore, GraphAfter)); + report_fatal_error(Twine("Preserved CFG changed by ", P)); + } + }); +} + void StandardInstrumentations::registerCallbacks( PassInstrumentationCallbacks &PIC) { PrintIR.registerCallbacks(PIC); PrintPass.registerCallbacks(PIC); TimePasses.registerCallbacks(PIC); OptNone.registerCallbacks(PIC); + PreservedCFGChecker.registerCallbacks(PIC); }