LLVM 20.0.0git
BlockCoverageInference.h
Go to the documentation of this file.
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"
22
23namespace llvm {
24
25class Function;
26class BasicBlock;
27class DotFuncBCIInfo;
28
30 friend class DotFuncBCIInfo;
31
32public:
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.
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.
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(ArrayRef<const BasicBlock *>(BBs.begin(), BBs.end()));
81 }
82};
83
84} // end namespace llvm
85
86#endif // LLVM_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H
This file defines the DenseMap class.
static bool findDependencies(DependenceKind Flavor, const Value *Arg, BasicBlock *StartBB, Instruction *StartInst, SmallPtrSetImpl< Instruction * > &DependingInsts, ProvenanceAnalysis &PA)
Walk up the CFG from StartPos (which is in StartBB) and find local and non-local dependencies on Arg.
#define F(x, y, z)
Definition: MD5.cpp:55
raw_pwrite_stream & OS
This file implements a set that has insertion order iteration characteristics.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
void dump(raw_ostream &OS) const
Dump the inference graph.
bool shouldInstrumentBlock(const BasicBlock &BB) const
void viewBlockCoverageGraph(const DenseMap< const BasicBlock *, bool > *Coverage=nullptr) const
View the inferred block coverage as a dot file.
BlockSet getDependencies(const BasicBlock &BB) const
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:113
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:103
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18