1 //===-- BlockCoverageInference.h - Minimal Execution Coverage ---*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file finds the minimum set of blocks on a CFG that must be instrumented 11 /// to infer execution coverage for the whole graph. 12 /// 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H 16 #define LLVM_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H 17 18 #include "llvm/ADT/ArrayRef.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/Support/raw_ostream.h" 22 23 namespace llvm { 24 25 class Function; 26 class BasicBlock; 27 class DotFuncBCIInfo; 28 29 class BlockCoverageInference { 30 friend class DotFuncBCIInfo; 31 32 public: 33 using BlockSet = SmallSetVector<const BasicBlock *, 4>; 34 35 BlockCoverageInference(const Function &F, bool ForceInstrumentEntry); 36 37 /// \return true if \p BB should be instrumented for coverage. 38 bool shouldInstrumentBlock(const BasicBlock &BB) const; 39 40 /// \return the set of blocks \p Deps such that \p BB is covered iff any 41 /// blocks in \p Deps are covered. 42 BlockSet getDependencies(const BasicBlock &BB) const; 43 44 /// \return a hash that depends on the set of instrumented blocks. 45 uint64_t getInstrumentedBlocksHash() const; 46 47 /// Dump the inference graph. 48 void dump(raw_ostream &OS) const; 49 50 /// View the inferred block coverage as a dot file. 51 /// Filled gray blocks are instrumented, red outlined blocks are found to be 52 /// covered, red edges show that a block's coverage can be inferred from its 53 /// successors, and blue edges show that a block's coverage can be inferred 54 /// from its predecessors. 55 void viewBlockCoverageGraph( 56 const DenseMap<const BasicBlock *, bool> *Coverage = nullptr) const; 57 58 private: 59 const Function &F; 60 bool ForceInstrumentEntry; 61 62 /// Maps blocks to a minimal list of predecessors that can be used to infer 63 /// this block's coverage. 64 DenseMap<const BasicBlock *, BlockSet> PredecessorDependencies; 65 66 /// Maps blocks to a minimal list of successors that can be used to infer 67 /// this block's coverage. 68 DenseMap<const BasicBlock *, BlockSet> SuccessorDependencies; 69 70 /// Compute \p PredecessorDependencies and \p SuccessorDependencies. 71 void findDependencies(); 72 73 /// Find the set of basic blocks that are reachable from \p Start without the 74 /// basic block \p Avoid. 75 void getReachableAvoiding(const BasicBlock &Start, const BasicBlock &Avoid, 76 bool IsForward, BlockSet &Reachable) const; 77 78 static std::string getBlockNames(ArrayRef<const BasicBlock *> BBs); 79 static std::string getBlockNames(BlockSet BBs) { 80 return getBlockNames(ArrayRef<const BasicBlock *>(BBs.begin(), BBs.end())); 81 } 82 }; 83 84 } // end namespace llvm 85 86 #endif // LLVM_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H 87