diff --git a/llvm/include/llvm/Passes/StandardInstrumentations.h b/llvm/include/llvm/Passes/StandardInstrumentations.h --- a/llvm/include/llvm/Passes/StandardInstrumentations.h +++ b/llvm/include/llvm/Passes/StandardInstrumentations.h @@ -17,8 +17,11 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" +#include "llvm/IR/BasicBlock.h" #include "llvm/IR/PassInstrumentation.h" #include "llvm/IR/PassTimingInfo.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/CommandLine.h" #include #include @@ -26,6 +29,7 @@ namespace llvm { class Module; +class Function; /// Instrumentation to print IR before/after passes. /// @@ -73,6 +77,53 @@ bool DebugLogging; }; +class PreservedCFGCheckerInstrumentation { +private: + // 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 { + struct BBGuard final : public CallbackVH { + BBGuard(const BasicBlock *BB) : CallbackVH(BB) {} + void deleted() override { CallbackVH::deleted(); } + void allUsesReplacedWith(Value *) override { CallbackVH::deleted(); } + bool isPoisoned() const { return !getValPtr(); } + }; + + Optional> BBGuards; + DenseMap> Graph; + + CFG(const Function *F, bool TrackBBLifetime = false); + + bool operator==(const CFG &G) const { + return !isPoisoned() && !G.isPoisoned() && Graph == G.Graph; + } + + bool isPoisoned() const { + if (BBGuards) + for (auto &BB : *BBGuards) { + if (BB.second.isPoisoned()) + return true; + } + return false; + } + + static void printDiff(raw_ostream &out, const CFG &Before, + const CFG &After); + }; + + SmallVector>, 8> GraphStackBefore; + +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 +131,7 @@ PrintPassInstrumentation PrintPass; TimePassesHandler TimePasses; OptNoneInstrumentation OptNone; + PreservedCFGCheckerInstrumentation PreservedCFGChecker; public: StandardInstrumentations(bool DebugLogging) : PrintPass(DebugLogging) {} diff --git a/llvm/lib/Passes/StandardInstrumentations.cpp b/llvm/lib/Passes/StandardInstrumentations.cpp --- a/llvm/lib/Passes/StandardInstrumentations.cpp +++ b/llvm/lib/Passes/StandardInstrumentations.cpp @@ -36,6 +36,14 @@ 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 +346,166 @@ }); } +PreservedCFGCheckerInstrumentation::CFG::CFG(const Function *F, + bool TrackBBLifetime) { + if (TrackBBLifetime) + BBGuards = DenseMap(F->size()); + for (const auto &BB : *F) { + if (BBGuards) + BBGuards->try_emplace(intptr_t(&BB), &BB); + for (auto *Succ : successors(&BB)) { + Graph[&BB][Succ]++; + if (BBGuards) + BBGuards->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 PreservedCFGCheckerInstrumentation::CFG::printDiff(raw_ostream &out, + const CFG &Before, + const CFG &After) { + assert(!After.isPoisoned()); + + // Print function name. + const CFG *FuncGraph = nullptr; + if (!After.Graph.empty()) + FuncGraph = &After; + else if (!Before.isPoisoned() && !Before.Graph.empty()) + 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) { + if (any_isa(IR)) + GraphStackBefore.emplace_back(P, CFG(any_cast(IR))); + else + GraphStackBefore.emplace_back(P, None); + }); + + PIC.registerAfterPassInvalidatedCallback( + [this](StringRef P, const PreservedAnalyses &PassPA) { + auto Before = GraphStackBefore.pop_back_val(); + assert(Before.first == P && + "Before and After callbacks must correspond"); + (void)Before; + }); + + PIC.registerAfterPassCallback([this](StringRef P, Any IR, + const PreservedAnalyses &PassPA) { + auto Before = GraphStackBefore.pop_back_val(); + assert(Before.first == P && "Before and After callbacks must correspond"); + auto &GraphBefore = Before.second; + + if (!PassPA.allAnalysesInSetPreserved()) + return; + + if (any_isa(IR)) { + assert(GraphBefore && "Must be built in BeforePassCallback"); + CFG GraphAfter(any_cast(IR), false /* NeedsGuard */); + if (GraphAfter == *GraphBefore) + return; + + 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); }