[sancov] do not instrument nodes that are full post-dominators

[aizatsky]

Summary

Without tree pruning clang has 2,667,552 points.
Wiht only dominators pruning: 1,515,586.
With both dominators & post-dominators pruning: 1,340,534.

[aizatsky]

formatting

[kcc]

LGTM

llvm/trunk/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

 // it only tells if a given function (block) was ever executed. No counters.
 // But for many use cases this is what we need and the added slowdown small.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/EHPersonalities.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InlineAsm.h"
SanitizerCoverageModule(
       const SanitizerCoverageOptions &Options = SanitizerCoverageOptions())
       : ModulePass(ID), Options(OverrideFromCL(Options)) {}
   bool runOnModule(Module &M) override;
   bool runOnFunction(Function &F);
   static char ID;  // Pass identification, replacement for typeid
   const char *getPassName() const override {
     return "SanitizerCoverageModule";
   }
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<PostDominatorTreeWrapperPass>();
+  }
 
- private:
   void InjectCoverageForIndirectCalls(Function &F,
                                       ArrayRef<Instruction *> IndirCalls);
   void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets);
   void InjectTraceForSwitch(Function &F,
                             ArrayRef<Instruction *> SwitchTraceTargets);
   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks);
   void SetNoSanitizeMetadata(Instruction *I);
   void InjectCoverageAtBlock(Function &F, BasicBlock &BB, bool UseCalls);
std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
            : Constant::getNullValue(Int8PtrTy),
        IRB.CreatePointerCast(ModuleName, Int8PtrTy)});
 
   appendToGlobalCtors(M, CtorFunc, kSanCtorAndDtorPriority);
 
   return true;
 }
 
-static bool shouldInstrumentBlock(const BasicBlock *BB,
-                                  const DominatorTree *DT) {
+static bool shouldInstrumentBlock(const BasicBlock *BB, const DominatorTree *DT,
+                                  const PostDominatorTree *PDT) {
   if (!ClPruneBlocks)
     return true;
-  if (succ_begin(BB) == succ_end(BB))
-    return true;
 
   // Check if BB dominates all its successors.
+  bool DominatesAll = succ_begin(BB) != succ_end(BB);
   for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) {
-    if (!DT->dominates(BB, SUCC))
-      return true;
+    DominatesAll &= DT->dominates(BB, SUCC);
   }
 
-  return false;
+  // Check if BB pre-dominates all predecessors.
+  bool PreDominatesAll = pred_begin(BB) != pred_end(BB);
+  for (const BasicBlock *PRED : make_range(pred_begin(BB), pred_end(BB))) {
+    PreDominatesAll &= PDT->dominates(BB, PRED);
+  }
+
+  return !(DominatesAll || PreDominatesAll);
 }
 
 bool SanitizerCoverageModule::runOnFunction(Function &F) {
   if (F.empty()) return false;
   if (F.getName().find(".module_ctor") != std::string::npos)
     return false;  // Should not instrument sanitizer init functions.
   // Don't instrument functions using SEH for now. Splitting basic blocks like
   // we do for coverage breaks WinEHPrepare.
   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
   if (F.hasPersonalityFn() &&
       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
     return false;
   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge)
     SplitAllCriticalEdges(F);
   SmallVector<Instruction*, 8> IndirCalls;
   SmallVector<BasicBlock *, 16> BlocksToInstrument;
   SmallVector<Instruction*, 8> CmpTraceTargets;
   SmallVector<Instruction*, 8> SwitchTraceTargets;
 
-  DominatorTree DT;
-  DT.recalculate(F);
+  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
+  PostDominatorTree *PDT =
+      &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree();
+
   for (auto &BB : F) {
-    if (shouldInstrumentBlock(&BB, &DT))
+    if (shouldInstrumentBlock(&BB, DT, PDT))
       BlocksToInstrument.push_back(&BB);
     for (auto &Inst : BB) {
       if (Options.IndirectCalls) {
         CallSite CS(&Inst);
         if (CS && !CS.getCalledFunction())
           IndirCalls.push_back(&Inst);
       }
       if (Options.TraceCmp) {