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
23namespace llvm {
24
25class Function;
26class BasicBlock;
27class DotFuncBCIInfo;
28
29class BlockCoverageInference {
30 friend class DotFuncBCIInfo;
31
32public:
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
58private:
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(BBs: ArrayRef<const BasicBlock *>(BBs.begin(), BBs.end()));
81 }
82};
83
84} // end namespace llvm
85
86#endif // LLVM_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H
87