41#define DEBUG_TYPE "pgo-block-coverage"
43STATISTIC(NumFunctions,
"Number of total functions that BCI has processed");
45 "Number of functions for which BCI cannot run on");
46STATISTIC(NumBlocks,
"Number of total basic blocks that BCI has processed");
48 "Number of basic blocks instrumented for coverage");
51 bool ForceInstrumentEntry)
52 :
F(
F), ForceInstrumentEntry(ForceInstrumentEntry) {
60 ++NumInstrumentedBlocks;
68 auto It = PredecessorDependencies.find(&BB);
69 if (It != PredecessorDependencies.end())
71 It = SuccessorDependencies.find(&BB);
72 if (It != SuccessorDependencies.end())
93 auto It = PredecessorDependencies.find(&BB);
94 if (It != PredecessorDependencies.end() && It->second.size())
96 It = SuccessorDependencies.find(&BB);
97 if (It != SuccessorDependencies.end() && It->second.size())
102void BlockCoverageInference::findDependencies() {
103 assert(PredecessorDependencies.empty() && SuccessorDependencies.empty());
107 ++NumIneligibleFunctions;
120 for (
auto *BB : TerminalBlocks)
123 if (
F.size() != Visited.
size()) {
124 ++NumIneligibleFunctions;
134 auto &EntryBlock =
F.getEntryBlock();
137 BlockSet ReachableFromEntry, ReachableFromTerminal;
138 getReachableAvoiding(EntryBlock, BB,
true,
140 for (
auto *TerminalBlock : TerminalBlocks)
141 getReachableAvoiding(*TerminalBlock, BB,
false,
142 ReachableFromTerminal);
145 bool HasSuperReachablePred =
llvm::any_of(Preds, [&](
auto *Pred) {
146 return ReachableFromEntry.count(Pred) &&
147 ReachableFromTerminal.count(Pred);
149 if (!HasSuperReachablePred)
150 for (
auto *Pred : Preds)
151 if (ReachableFromEntry.count(Pred))
152 PredecessorDependencies[&BB].insert(Pred);
155 bool HasSuperReachableSucc =
llvm::any_of(Succs, [&](
auto *Succ) {
156 return ReachableFromEntry.count(Succ) &&
157 ReachableFromTerminal.count(Succ);
159 if (!HasSuperReachableSucc)
160 for (
auto *Succ : Succs)
161 if (ReachableFromTerminal.count(Succ))
162 SuccessorDependencies[&BB].insert(Succ);
165 if (ForceInstrumentEntry) {
168 PredecessorDependencies[&EntryBlock].clear();
169 SuccessorDependencies[&EntryBlock].clear();
178 if (SuccessorDependencies[&BB].
count(Succ) &&
179 PredecessorDependencies[Succ].
count(&BB)) {
180 AdjacencyList[&BB].
insert(Succ);
181 AdjacencyList[Succ].
insert(&BB);
189 auto &Neighbors = AdjacencyList[
Path.back()];
190 if (
Path.size() == 1) {
192 assert(Neighbors.size() == 1);
193 return Neighbors.front();
194 }
else if (Neighbors.size() == 2) {
198 return Path.count(Neighbors[0]) ? Neighbors[1] : Neighbors[0];
201 assert(Neighbors.size() == 1);
207 if (AdjacencyList[&BB].
size() == 1) {
211 while (
const BasicBlock *Next = getNextOnPath(Path))
213 LLVM_DEBUG(
dbgs() <<
"Found path: " << getBlockNames(Path) <<
"\n");
216 for (
auto *BB : Path)
217 AdjacencyList[BB].
clear();
220 if (PredecessorDependencies[
Path.front()].size()) {
221 for (
auto *BB : Path)
222 if (BB !=
Path.back())
223 SuccessorDependencies[BB].clear();
225 for (
auto *BB : Path)
226 if (BB !=
Path.front())
227 PredecessorDependencies[BB].clear();
234void BlockCoverageInference::getReachableAvoiding(
const BasicBlock &Start,
237 BlockSet &Reachable)
const {
258 : BCI(BCI), Coverage(Coverage) {}
267 return Coverage && Coverage->lookup(BB);
278 return &(
Info->getFunction().getEntryBlock());
293 return Info->getFunction().size();
303 return "BCI CFG for " +
Info->getFunction().getName().str();
307 return Node->getName().str();
313 if (
Info->isDependent(Src, Dest))
315 if (
Info->isDependent(Dest, Src))
322 if (
Info->isInstrumented(Node))
323 Result +=
"style=filled,fillcolor=gray";
324 if (
Info->isCovered(Node))
325 Result += std::string(Result.empty() ?
"" :
",") +
"color=red";
336 "Block Coverage Inference for " +
F.getName());
340 OS <<
"Minimal block coverage for function \'" <<
F.getName()
341 <<
"\' (Instrumented=*)\n";
344 auto It = PredecessorDependencies.find(&BB);
345 if (It != PredecessorDependencies.end() && It->second.size())
346 OS <<
" PredDeps = " << getBlockNames(It->second) <<
"\n";
347 It = SuccessorDependencies.find(&BB);
348 if (It != SuccessorDependencies.end() && It->second.size())
349 OS <<
" SuccDeps = " << getBlockNames(It->second) <<
"\n";
351 OS <<
" Instrumented Blocks Hash = 0x"
365 OS <<
", " << BB->getName();
This file finds the minimum set of blocks on a CFG that must be instrumented to infer execution cover...
Analysis containing CSE Info
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
const T & front() const
front - Get the first element.
bool empty() const
empty - Check if the array is empty.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
void dump(raw_ostream &OS) const
Dump the inference graph.
uint64_t getInstrumentedBlocksHash() const
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.
BlockCoverageInference(const Function &F, bool ForceInstrumentEntry)
BlockSet getDependencies(const BasicBlock &BB) const
SmallSetVector< const BasicBlock *, 4 > BlockSet
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
bool isInstrumented(const BasicBlock *BB) const
const Function & getFunction()
bool isCovered(const BasicBlock *BB) const
bool isDependent(const BasicBlock *Src, const BasicBlock *Dest) const
DotFuncBCIInfo(const BlockCoverageInference *BCI, const DenseMap< const BasicBlock *, bool > *Coverage)
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void update(ArrayRef< uint8_t > Data)
bool set_union(const STy &S)
Compute This := This u S, return whether 'This' changed.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
A SetVector that performs no allocations if smaller than a certain size.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static Twine utohexstr(const uint64_t &Val)
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
void write64le(void *P, uint64_t V)
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
bool succ_empty(const Instruction *I)
auto successors(const MachineBasicBlock *BB)
raw_ostream & WriteGraph(raw_ostream &O, const GraphType &G, bool ShortNames=false, const Twine &Title="")
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
auto predecessors(const MachineBasicBlock *BB)
DOTGraphTraits(bool IsSimple=false)
static std::string getGraphName(DotFuncBCIInfo *Info)
std::string getNodeLabel(const BasicBlock *Node, DotFuncBCIInfo *Info)
std::string getNodeAttributes(const BasicBlock *Node, DotFuncBCIInfo *Info)
std::string getEdgeAttributes(const BasicBlock *Src, const_succ_iterator I, DotFuncBCIInfo *Info)
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
static nodes_iterator nodes_end(DotFuncBCIInfo *Info)
static NodeRef getEntryNode(DotFuncBCIInfo *Info)
static nodes_iterator nodes_begin(DotFuncBCIInfo *Info)
static size_t size(DotFuncBCIInfo *Info)
std::pair< iterator, bool > insert(NodeRef N)