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