Transforms/Instrumentation/BlockCoverageInference.h

0001 //===-- BlockCoverageInference.h - Minimal Execution Coverage ---*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file finds the minimum set of blocks on a CFG that must be instrumented
0011 /// to infer execution coverage for the whole graph.
0012 ///
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H
0016 #define LLVM_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H
0017
0018 #include "llvm/ADT/ArrayRef.h"
0019 #include "llvm/ADT/DenseMap.h"
0020 #include "llvm/ADT/SetVector.h"
0021 #include "llvm/Support/raw_ostream.h"
0022
0023 namespace llvm {
0024
0025 class Function;
0026 class BasicBlock;
0027 class DotFuncBCIInfo;
0028
0029 class BlockCoverageInference {
0030   friend class DotFuncBCIInfo;
0031
0032 public:
0033   using BlockSet = SmallSetVector<const BasicBlock *, 4>;
0034
0035   BlockCoverageInference(const Function &F, bool ForceInstrumentEntry);
0036
0037   /// \return true if \p BB should be instrumented for coverage.
0038   bool shouldInstrumentBlock(const BasicBlock &BB) const;
0039
0040   /// \return the set of blocks \p Deps such that \p BB is covered iff any
0041   /// blocks in \p Deps are covered.
0042   BlockSet getDependencies(const BasicBlock &BB) const;
0043
0044   /// \return a hash that depends on the set of instrumented blocks.
0045   uint64_t getInstrumentedBlocksHash() const;
0046
0047   /// Dump the inference graph.
0048   void dump(raw_ostream &OS) const;
0049
0050   /// View the inferred block coverage as a dot file.
0051   /// Filled gray blocks are instrumented, red outlined blocks are found to be
0052   /// covered, red edges show that a block's coverage can be inferred from its
0053   /// successors, and blue edges show that a block's coverage can be inferred
0054   /// from its predecessors.
0055   void viewBlockCoverageGraph(
0056       const DenseMap<const BasicBlock *, bool> *Coverage = nullptr) const;
0057
0058 private:
0059   const Function &F;
0060   bool ForceInstrumentEntry;
0061
0062   /// Maps blocks to a minimal list of predecessors that can be used to infer
0063   /// this block's coverage.
0064   DenseMap<const BasicBlock *, BlockSet> PredecessorDependencies;
0065
0066   /// Maps blocks to a minimal list of successors that can be used to infer
0067   /// this block's coverage.
0068   DenseMap<const BasicBlock *, BlockSet> SuccessorDependencies;
0069
0070   /// Compute \p PredecessorDependencies and \p SuccessorDependencies.
0071   void findDependencies();
0072
0073   /// Find the set of basic blocks that are reachable from \p Start without the
0074   /// basic block \p Avoid.
0075   void getReachableAvoiding(const BasicBlock &Start, const BasicBlock &Avoid,
0076                             bool IsForward, BlockSet &Reachable) const;
0077
0078   static std::string getBlockNames(ArrayRef<const BasicBlock *> BBs);
0079   static std::string getBlockNames(BlockSet BBs) {
0080     return getBlockNames(ArrayRef<const BasicBlock *>(BBs.begin(), BBs.end()));
0081   }
0082 };
0083
0084 } // end namespace llvm
0085
0086 #endif // LLVM_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H