1 //===-- BlockCoverageInference.cpp - Minimal Execution Coverage -*- C++ -*-===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
13 // In general a node v is ambiguous if there exists two entry-to-terminal paths
26 // Details on this algorithm can be found in https://arxiv.org/abs/2208.13907
28 //===----------------------------------------------------------------------===//
41 #define DEBUG_TYPE "pgo-block-coverage"
70     Dependencies.set_union(It->second);  in getDependencies()
73     Dependencies.set_union(It->second);  in getDependencies()
94   if (It != PredecessorDependencies.end() && It->second.size())  in shouldInstrumentBlock()
97   if (It != SuccessorDependencies.end() && It->second.size())  in shouldInstrumentBlock()
131   // in https://arxiv.org/abs/2208.13907 we do not know if it will give a  in findDependencies()
187   auto getNextOnPath = [&](BlockSet &Path) -> const BasicBlock * {  in findDependencies()
241     auto Range = depth_first_ext(&Start, Visited);  in getReachableAvoiding()  local
242     Reachable.insert(Range.begin(), Range.end());  in getReachableAvoiding()
244     auto Range = inverse_depth_first_ext(&Start, Visited);  in getReachableAvoiding()  local
245     Reachable.insert(Range.begin(), Range.end());  in getReachableAvoiding()
260   const Function &getFunction() { return BCI->F; }  in getFunction()
263     return BCI->shouldInstrumentBlock(*BB);  in isInstrumented()
267     return Coverage && Coverage->lookup(BB);  in isCovered()
271     return BCI->getDependencies(*Src).count(Dest);  in isDependent()
278     return &(Info->getFunction().getEntryBlock());  in getEntryNode()
281   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
285     return nodes_iterator(Info->getFunction().begin());  in nodes_begin()
289     return nodes_iterator(Info->getFunction().end());  in nodes_end()
293     return Info->getFunction().size();  in size()
303     return "BCI CFG for " + Info->getFunction().getName().str();  in getGraphName()
307     return Node->getName().str();  in getNodeLabel()
313     if (Info->isDependent(Src, Dest))  in getEdgeAttributes()
315     if (Info->isDependent(Dest, Src))  in getEdgeAttributes()
322     if (Info->isInstrumented(Node))  in getNodeAttributes()
324     if (Info->isCovered(Node))  in getNodeAttributes()
345     if (It != PredecessorDependencies.end() && It->second.size())  in dump()
346       OS << "    PredDeps = " << getBlockNames(It->second) << "\n";  in dump()
348     if (It != SuccessorDependencies.end() && It->second.size())  in dump()
349       OS << "    SuccDeps = " << getBlockNames(It->second) << "\n";  in dump()
361     OS << BBs.front()->getName();  in getBlockNames()
365     OS << ", " << BB->getName();  in getBlockNames()