src/llvm-project/llvm/lib/Transforms/Instrumentation/BlockCoverageInference.cpp - toolchain/rustc - Git at Google

 //===-- BlockCoverageInference.cpp - Minimal Execution Coverage -*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Our algorithm works by first identifying a subset of nodes that must always
 // be instrumented. We call these nodes ambiguous because knowing the coverage
 // of all remaining nodes is not enough to infer their coverage status.
 //
 // In general a node v is ambiguous if there exists two entry-to-terminal paths
 // P_1 and P_2 such that:
 //   1. v not in P_1 but P_1 visits a predecessor of v, and
 //   2. v not in P_2 but P_2 visits a successor of v.
 //
 // If a node v is not ambiguous, then if condition 1 fails, we can infer v’s
 // coverage from the coverage of its predecessors, or if condition 2 fails, we
 // can infer v’s coverage from the coverage of its successors.
 //
 // Sadly, there are example CFGs where it is not possible to infer all nodes
 // from the ambiguous nodes alone. Our algorithm selects a minimum number of
 // extra nodes to add to the ambiguous nodes to form a valid instrumentation S.
 //
 // Details on this algorithm can be found in https://arxiv.org/abs/2208.13907
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/Transforms/Instrumentation/BlockCoverageInference.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/CRC.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GraphWriter.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"

 using namespace llvm;

 #define DEBUG_TYPE "pgo-block-coverage"

 STATISTIC(NumFunctions, "Number of total functions that BCI has processed");
 STATISTIC(NumIneligibleFunctions,
           "Number of functions for which BCI cannot run on");
 STATISTIC(NumBlocks, "Number of total basic blocks that BCI has processed");
 STATISTIC(NumInstrumentedBlocks,
           "Number of basic blocks instrumented for coverage");

 BlockCoverageInference::BlockCoverageInference(const Function &F,
                                                bool ForceInstrumentEntry)
     : F(F), ForceInstrumentEntry(ForceInstrumentEntry) {
   findDependencies();
   assert(!ForceInstrumentEntry || shouldInstrumentBlock(F.getEntryBlock()));

   ++NumFunctions;
   for (auto &BB : F) {
     ++NumBlocks;
     if (shouldInstrumentBlock(BB))
       ++NumInstrumentedBlocks;
   }
 }

 BlockCoverageInference::BlockSet
 BlockCoverageInference::getDependencies(const BasicBlock &BB) const {
   assert(BB.getParent() == &F);
   BlockSet Dependencies;
   auto It = PredecessorDependencies.find(&BB);
   if (It != PredecessorDependencies.end())
     Dependencies.set_union(It->second);
   It = SuccessorDependencies.find(&BB);
   if (It != SuccessorDependencies.end())
     Dependencies.set_union(It->second);
   return Dependencies;
 }

 uint64_t BlockCoverageInference::getInstrumentedBlocksHash() const {
   JamCRC JC;
   uint64_t Index = 0;
   for (auto &BB : F) {
     if (shouldInstrumentBlock(BB)) {
       uint8_t Data[8];
       support::endian::write64le(Data, Index);
       JC.update(Data);
     }
     Index++;
   }
   return JC.getCRC();
 }

 bool BlockCoverageInference::shouldInstrumentBlock(const BasicBlock &BB) const {
   assert(BB.getParent() == &F);
   auto It = PredecessorDependencies.find(&BB);
   if (It != PredecessorDependencies.end() && It->second.size())
     return false;
   It = SuccessorDependencies.find(&BB);
   if (It != SuccessorDependencies.end() && It->second.size())
     return false;
   return true;
 }

 void BlockCoverageInference::findDependencies() {
   assert(PredecessorDependencies.empty() && SuccessorDependencies.empty());
   // Empirical analysis shows that this algorithm finishes within 5 seconds for
   // functions with fewer than 1.5K blocks.
   if (F.hasFnAttribute(Attribute::NoReturn) || F.size() > 1500) {
     ++NumIneligibleFunctions;
     return;
   }

   SmallVector<const BasicBlock *, 4> TerminalBlocks;
   for (auto &BB : F)
     if (succ_empty(&BB))
       TerminalBlocks.push_back(&BB);

   // Traverse the CFG backwards from the terminal blocks to make sure every
   // block can reach some terminal block. Otherwise this algorithm will not work
   // and we must fall back to instrumenting every block.
   df_iterator_default_set<const BasicBlock *> Visited;
   for (auto *BB : TerminalBlocks)
     for (auto *N : inverse_depth_first_ext(BB, Visited))
       (void)N;
   if (F.size() != Visited.size()) {
     ++NumIneligibleFunctions;
     return;
   }

   // The current implementation for computing `PredecessorDependencies` and
   // `SuccessorDependencies` runs in quadratic time with respect to the number
   // of basic blocks. While we do have a more complicated linear time algorithm
   // in https://arxiv.org/abs/2208.13907 we do not know if it will give a
   // significant speedup in practice given that most functions tend to be
   // relatively small in size for intended use cases.
   auto &EntryBlock = F.getEntryBlock();
   for (auto &BB : F) {
     // The set of blocks that are reachable while avoiding BB.
     BlockSet ReachableFromEntry, ReachableFromTerminal;
     getReachableAvoiding(EntryBlock, BB, /*IsForward=*/true,
                          ReachableFromEntry);
     for (auto *TerminalBlock : TerminalBlocks)
       getReachableAvoiding(*TerminalBlock, BB, /*IsForward=*/false,
                            ReachableFromTerminal);

     auto Preds = predecessors(&BB);
     bool HasSuperReachablePred = llvm::any_of(Preds, [&](auto *Pred) {
       return ReachableFromEntry.count(Pred) &&
              ReachableFromTerminal.count(Pred);
     });
     if (!HasSuperReachablePred)
       for (auto *Pred : Preds)
         if (ReachableFromEntry.count(Pred))
           PredecessorDependencies[&BB].insert(Pred);

     auto Succs = successors(&BB);
     bool HasSuperReachableSucc = llvm::any_of(Succs, [&](auto *Succ) {
       return ReachableFromEntry.count(Succ) &&
              ReachableFromTerminal.count(Succ);
     });
     if (!HasSuperReachableSucc)
       for (auto *Succ : Succs)
         if (ReachableFromTerminal.count(Succ))
           SuccessorDependencies[&BB].insert(Succ);
   }

   if (ForceInstrumentEntry) {
     // Force the entry block to be instrumented by clearing the blocks it can
     // infer coverage from.
     PredecessorDependencies[&EntryBlock].clear();
     SuccessorDependencies[&EntryBlock].clear();
   }

   // Construct a graph where blocks are connected if there is a mutual
   // dependency between them. This graph has a special property that it contains
   // only paths.
   DenseMap<const BasicBlock *, BlockSet> AdjacencyList;
   for (auto &BB : F) {
     for (auto *Succ : successors(&BB)) {
       if (SuccessorDependencies[&BB].count(Succ) &&
           PredecessorDependencies[Succ].count(&BB)) {
         AdjacencyList[&BB].insert(Succ);
         AdjacencyList[Succ].insert(&BB);
       }
     }
   }

   // Given a path with at least one node, return the next node on the path.
   auto getNextOnPath = [&](BlockSet &Path) -> const BasicBlock * {
     assert(Path.size());
     auto &Neighbors = AdjacencyList[Path.back()];
     if (Path.size() == 1) {
       // This is the first node on the path, return its neighbor.
       assert(Neighbors.size() == 1);
       return Neighbors.front();
     } else if (Neighbors.size() == 2) {
       // This is the middle of the path, find the neighbor that is not on the
       // path already.
       assert(Path.size() >= 2);
       return Path.count(Neighbors[0]) ? Neighbors[1] : Neighbors[0];
     }
     // This is the end of the path.
     assert(Neighbors.size() == 1);
     return nullptr;
   };

   // Remove all cycles in the inferencing graph.
   for (auto &BB : F) {
     if (AdjacencyList[&BB].size() == 1) {
       // We found the head of some path.
       BlockSet Path;
       Path.insert(&BB);
       while (const BasicBlock *Next = getNextOnPath(Path))
         Path.insert(Next);
       LLVM_DEBUG(dbgs() << "Found path: " << getBlockNames(Path) << "\n");

       // Remove these nodes from the graph so we don't discover this path again.
       for (auto *BB : Path)
         AdjacencyList[BB].clear();

       // Finally, remove the cycles.
       if (PredecessorDependencies[Path.front()].size()) {
         for (auto *BB : Path)
           if (BB != Path.back())
             SuccessorDependencies[BB].clear();
       } else {
         for (auto *BB : Path)
           if (BB != Path.front())
             PredecessorDependencies[BB].clear();
       }
     }
   }
   LLVM_DEBUG(dump(dbgs()));
 }

 void BlockCoverageInference::getReachableAvoiding(const BasicBlock &Start,
                                                   const BasicBlock &Avoid,
                                                   bool IsForward,
                                                   BlockSet &Reachable) const {
   df_iterator_default_set<const BasicBlock *> Visited;
   Visited.insert(&Avoid);
   if (IsForward) {
     auto Range = depth_first_ext(&Start, Visited);
     Reachable.insert(Range.begin(), Range.end());
   } else {
     auto Range = inverse_depth_first_ext(&Start, Visited);
     Reachable.insert(Range.begin(), Range.end());
   }
 }

 namespace llvm {
 class DotFuncBCIInfo {
 private:
   const BlockCoverageInference *BCI;
   const DenseMap<const BasicBlock *, bool> *Coverage;

 public:
   DotFuncBCIInfo(const BlockCoverageInference *BCI,
                  const DenseMap<const BasicBlock *, bool> *Coverage)
       : BCI(BCI), Coverage(Coverage) {}

   const Function &getFunction() { return BCI->F; }

   bool isInstrumented(const BasicBlock *BB) const {
     return BCI->shouldInstrumentBlock(*BB);
   }

   bool isCovered(const BasicBlock *BB) const {
     return Coverage && Coverage->lookup(BB);
   }

   bool isDependent(const BasicBlock *Src, const BasicBlock *Dest) const {
     return BCI->getDependencies(*Src).count(Dest);
   }
 };

 template <>
 struct GraphTraits<DotFuncBCIInfo *> : public GraphTraits<const BasicBlock *> {
   static NodeRef getEntryNode(DotFuncBCIInfo *Info) {
     return &(Info->getFunction().getEntryBlock());
   }

   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   using nodes_iterator = pointer_iterator<Function::const_iterator>;

   static nodes_iterator nodes_begin(DotFuncBCIInfo *Info) {
     return nodes_iterator(Info->getFunction().begin());
   }

   static nodes_iterator nodes_end(DotFuncBCIInfo *Info) {
     return nodes_iterator(Info->getFunction().end());
   }

   static size_t size(DotFuncBCIInfo *Info) {
     return Info->getFunction().size();
   }
 };

 template <>
 struct DOTGraphTraits<DotFuncBCIInfo *> : public DefaultDOTGraphTraits {

   DOTGraphTraits(bool IsSimple = false) : DefaultDOTGraphTraits(IsSimple) {}

   static std::string getGraphName(DotFuncBCIInfo *Info) {
     return "BCI CFG for " + Info->getFunction().getName().str();
   }

   std::string getNodeLabel(const BasicBlock *Node, DotFuncBCIInfo *Info) {
     return Node->getName().str();
   }

   std::string getEdgeAttributes(const BasicBlock *Src, const_succ_iterator I,
                                 DotFuncBCIInfo *Info) {
     const BasicBlock *Dest = *I;
     if (Info->isDependent(Src, Dest))
       return "color=red";
     if (Info->isDependent(Dest, Src))
       return "color=blue";
     return "";
   }

   std::string getNodeAttributes(const BasicBlock *Node, DotFuncBCIInfo *Info) {
     std::string Result;
     if (Info->isInstrumented(Node))
       Result += "style=filled,fillcolor=gray";
     if (Info->isCovered(Node))
       Result += std::string(Result.empty() ? "" : ",") + "color=red";
     return Result;
   }
 };

 } // namespace llvm

 void BlockCoverageInference::viewBlockCoverageGraph(
     const DenseMap<const BasicBlock *, bool> *Coverage) const {
   DotFuncBCIInfo Info(this, Coverage);
   WriteGraph(&Info, "BCI", false,
              "Block Coverage Inference for " + F.getName());
 }

 void BlockCoverageInference::dump(raw_ostream &OS) const {
   OS << "Minimal block coverage for function \'" << F.getName()
      << "\' (Instrumented=*)\n";
   for (auto &BB : F) {
     OS << (shouldInstrumentBlock(BB) ? "* " : "  ") << BB.getName() << "\n";
     auto It = PredecessorDependencies.find(&BB);
     if (It != PredecessorDependencies.end() && It->second.size())
       OS << "    PredDeps = " << getBlockNames(It->second) << "\n";
     It = SuccessorDependencies.find(&BB);
     if (It != SuccessorDependencies.end() && It->second.size())
       OS << "    SuccDeps = " << getBlockNames(It->second) << "\n";
   }
   OS << "  Instrumented Blocks Hash = 0x"
      << Twine::utohexstr(getInstrumentedBlocksHash()) << "\n";
 }

 std::string
 BlockCoverageInference::getBlockNames(ArrayRef<const BasicBlock *> BBs) {
   std::string Result;
   raw_string_ostream OS(Result);
   OS << "[";
   if (!BBs.empty()) {
     OS << BBs.front()->getName();
     BBs = BBs.drop_front();
   }
   for (auto *BB : BBs)
     OS << ", " << BB->getName();
   OS << "]";
   return OS.str();
 }
	//===-- BlockCoverageInference.cpp - Minimal Execution Coverage -- C++ --===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	// Our algorithm works by first identifying a subset of nodes that must always
	// be instrumented. We call these nodes ambiguous because knowing the coverage
	// of all remaining nodes is not enough to infer their coverage status.
	//
	// In general a node v is ambiguous if there exists two entry-to-terminal paths
	// P_1 and P_2 such that:
	// 1. v not in P_1 but P_1 visits a predecessor of v, and
	// 2. v not in P_2 but P_2 visits a successor of v.
	//
	// If a node v is not ambiguous, then if condition 1 fails, we can infer v’s
	// coverage from the coverage of its predecessors, or if condition 2 fails, we
	// can infer v’s coverage from the coverage of its successors.
	//
	// Sadly, there are example CFGs where it is not possible to infer all nodes
	// from the ambiguous nodes alone. Our algorithm selects a minimum number of
	// extra nodes to add to the ambiguous nodes to form a valid instrumentation S.
	//
	// Details on this algorithm can be found in https://arxiv.org/abs/2208.13907
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/Transforms/Instrumentation/BlockCoverageInference.h"
	#include "llvm/ADT/DepthFirstIterator.h"
	#include "llvm/ADT/Statistic.h"
	#include "llvm/Support/CRC.h"
	#include "llvm/Support/Debug.h"
	#include "llvm/Support/GraphWriter.h"
	#include "llvm/Support/raw_ostream.h"
	#include "llvm/Transforms/Utils/BasicBlockUtils.h"

	using namespace llvm;

	#define DEBUG_TYPE "pgo-block-coverage"

	STATISTIC(NumFunctions, "Number of total functions that BCI has processed");
	STATISTIC(NumIneligibleFunctions,
	"Number of functions for which BCI cannot run on");
	STATISTIC(NumBlocks, "Number of total basic blocks that BCI has processed");
	STATISTIC(NumInstrumentedBlocks,
	"Number of basic blocks instrumented for coverage");

	BlockCoverageInference::BlockCoverageInference(const Function &F,
	bool ForceInstrumentEntry)
	: F(F), ForceInstrumentEntry(ForceInstrumentEntry) {
	findDependencies();
	assert(!ForceInstrumentEntry \|\| shouldInstrumentBlock(F.getEntryBlock()));

	++NumFunctions;
	for (auto &BB : F) {
	++NumBlocks;
	if (shouldInstrumentBlock(BB))
	++NumInstrumentedBlocks;
	}
	}

	BlockCoverageInference::BlockSet
	BlockCoverageInference::getDependencies(const BasicBlock &BB) const {
	assert(BB.getParent() == &F);
	BlockSet Dependencies;
	auto It = PredecessorDependencies.find(&BB);
	if (It != PredecessorDependencies.end())
	Dependencies.set_union(It->second);
	It = SuccessorDependencies.find(&BB);
	if (It != SuccessorDependencies.end())
	Dependencies.set_union(It->second);
	return Dependencies;
	}

	uint64_t BlockCoverageInference::getInstrumentedBlocksHash() const {
	JamCRC JC;
	uint64_t Index = 0;
	for (auto &BB : F) {
	if (shouldInstrumentBlock(BB)) {
	uint8_t Data[8];
	support::endian::write64le(Data, Index);
	JC.update(Data);
	}
	Index++;
	}
	return JC.getCRC();
	}

	bool BlockCoverageInference::shouldInstrumentBlock(const BasicBlock &BB) const {
	assert(BB.getParent() == &F);
	auto It = PredecessorDependencies.find(&BB);
	if (It != PredecessorDependencies.end() && It->second.size())
	return false;
	It = SuccessorDependencies.find(&BB);
	if (It != SuccessorDependencies.end() && It->second.size())
	return false;
	return true;
	}

	void BlockCoverageInference::findDependencies() {
	assert(PredecessorDependencies.empty() && SuccessorDependencies.empty());
	// Empirical analysis shows that this algorithm finishes within 5 seconds for
	// functions with fewer than 1.5K blocks.
	if (F.hasFnAttribute(Attribute::NoReturn) \|\| F.size() > 1500) {
	++NumIneligibleFunctions;
	return;
	}

	SmallVector<const BasicBlock *, 4> TerminalBlocks;
	for (auto &BB : F)
	if (succ_empty(&BB))
	TerminalBlocks.push_back(&BB);

	// Traverse the CFG backwards from the terminal blocks to make sure every
	// block can reach some terminal block. Otherwise this algorithm will not work
	// and we must fall back to instrumenting every block.
	df_iterator_default_set<const BasicBlock *> Visited;
	for (auto *BB : TerminalBlocks)
	for (auto *N : inverse_depth_first_ext(BB, Visited))
	(void)N;
	if (F.size() != Visited.size()) {
	++NumIneligibleFunctions;
	return;
	}

	// The current implementation for computing `PredecessorDependencies` and
	// `SuccessorDependencies` runs in quadratic time with respect to the number
	// of basic blocks. While we do have a more complicated linear time algorithm
	// in https://arxiv.org/abs/2208.13907 we do not know if it will give a
	// significant speedup in practice given that most functions tend to be
	// relatively small in size for intended use cases.
	auto &EntryBlock = F.getEntryBlock();
	for (auto &BB : F) {
	// The set of blocks that are reachable while avoiding BB.
	BlockSet ReachableFromEntry, ReachableFromTerminal;
	getReachableAvoiding(EntryBlock, BB, /IsForward=/true,
	ReachableFromEntry);
	for (auto *TerminalBlock : TerminalBlocks)
	getReachableAvoiding(TerminalBlock, BB, /IsForward=*/false,
	ReachableFromTerminal);

	auto Preds = predecessors(&BB);
	bool HasSuperReachablePred = llvm::any_of(Preds, [&](auto *Pred) {
	return ReachableFromEntry.count(Pred) &&
	ReachableFromTerminal.count(Pred);
	});
	if (!HasSuperReachablePred)
	for (auto *Pred : Preds)
	if (ReachableFromEntry.count(Pred))
	PredecessorDependencies[&BB].insert(Pred);

	auto Succs = successors(&BB);
	bool HasSuperReachableSucc = llvm::any_of(Succs, [&](auto *Succ) {
	return ReachableFromEntry.count(Succ) &&
	ReachableFromTerminal.count(Succ);
	});
	if (!HasSuperReachableSucc)
	for (auto *Succ : Succs)
	if (ReachableFromTerminal.count(Succ))
	SuccessorDependencies[&BB].insert(Succ);
	}

	if (ForceInstrumentEntry) {
	// Force the entry block to be instrumented by clearing the blocks it can
	// infer coverage from.
	PredecessorDependencies[&EntryBlock].clear();
	SuccessorDependencies[&EntryBlock].clear();
	}

	// Construct a graph where blocks are connected if there is a mutual
	// dependency between them. This graph has a special property that it contains
	// only paths.
	DenseMap<const BasicBlock *, BlockSet> AdjacencyList;
	for (auto &BB : F) {
	for (auto *Succ : successors(&BB)) {
	if (SuccessorDependencies[&BB].count(Succ) &&
	PredecessorDependencies[Succ].count(&BB)) {
	AdjacencyList[&BB].insert(Succ);
	AdjacencyList[Succ].insert(&BB);
	}
	}
	}

	// Given a path with at least one node, return the next node on the path.
	auto getNextOnPath = [&](BlockSet &Path) -> const BasicBlock * {
	assert(Path.size());
	auto &Neighbors = AdjacencyList[Path.back()];
	if (Path.size() == 1) {
	// This is the first node on the path, return its neighbor.
	assert(Neighbors.size() == 1);
	return Neighbors.front();
	} else if (Neighbors.size() == 2) {
	// This is the middle of the path, find the neighbor that is not on the
	// path already.
	assert(Path.size() >= 2);
	return Path.count(Neighbors[0]) ? Neighbors[1] : Neighbors[0];
	}
	// This is the end of the path.
	assert(Neighbors.size() == 1);
	return nullptr;
	};

	// Remove all cycles in the inferencing graph.
	for (auto &BB : F) {
	if (AdjacencyList[&BB].size() == 1) {
	// We found the head of some path.
	BlockSet Path;
	Path.insert(&BB);
	while (const BasicBlock *Next = getNextOnPath(Path))
	Path.insert(Next);
	LLVM_DEBUG(dbgs() << "Found path: " << getBlockNames(Path) << "\n");

	// Remove these nodes from the graph so we don't discover this path again.
	for (auto *BB : Path)
	AdjacencyList[BB].clear();

	// Finally, remove the cycles.
	if (PredecessorDependencies[Path.front()].size()) {
	for (auto *BB : Path)
	if (BB != Path.back())
	SuccessorDependencies[BB].clear();
	} else {
	for (auto *BB : Path)
	if (BB != Path.front())
	PredecessorDependencies[BB].clear();
	}
	}
	}
	LLVM_DEBUG(dump(dbgs()));
	}

	void BlockCoverageInference::getReachableAvoiding(const BasicBlock &Start,
	const BasicBlock &Avoid,
	bool IsForward,
	BlockSet &Reachable) const {
	df_iterator_default_set<const BasicBlock *> Visited;
	Visited.insert(&Avoid);
	if (IsForward) {
	auto Range = depth_first_ext(&Start, Visited);
	Reachable.insert(Range.begin(), Range.end());
	} else {
	auto Range = inverse_depth_first_ext(&Start, Visited);
	Reachable.insert(Range.begin(), Range.end());
	}
	}

	namespace llvm {
	class DotFuncBCIInfo {
	private:
	const BlockCoverageInference *BCI;
	const DenseMap<const BasicBlock , bool> Coverage;

	public:
	DotFuncBCIInfo(const BlockCoverageInference *BCI,
	const DenseMap<const BasicBlock , bool> Coverage)
	: BCI(BCI), Coverage(Coverage) {}

	const Function &getFunction() { return BCI->F; }

	bool isInstrumented(const BasicBlock *BB) const {
	return BCI->shouldInstrumentBlock(*BB);
	}

	bool isCovered(const BasicBlock *BB) const {
	return Coverage && Coverage->lookup(BB);
	}

	bool isDependent(const BasicBlock Src, const BasicBlock Dest) const {
	return BCI->getDependencies(*Src).count(Dest);
	}
	};

	template <>
	struct GraphTraits<DotFuncBCIInfo > : public GraphTraits<const BasicBlock > {
	static NodeRef getEntryNode(DotFuncBCIInfo *Info) {
	return &(Info->getFunction().getEntryBlock());
	}

	// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
	using nodes_iterator = pointer_iterator<Function::const_iterator>;

	static nodes_iterator nodes_begin(DotFuncBCIInfo *Info) {
	return nodes_iterator(Info->getFunction().begin());
	}

	static nodes_iterator nodes_end(DotFuncBCIInfo *Info) {
	return nodes_iterator(Info->getFunction().end());
	}

	static size_t size(DotFuncBCIInfo *Info) {
	return Info->getFunction().size();
	}
	};

	template <>
	struct DOTGraphTraits<DotFuncBCIInfo *> : public DefaultDOTGraphTraits {

	DOTGraphTraits(bool IsSimple = false) : DefaultDOTGraphTraits(IsSimple) {}

	static std::string getGraphName(DotFuncBCIInfo *Info) {
	return "BCI CFG for " + Info->getFunction().getName().str();
	}

	std::string getNodeLabel(const BasicBlock Node, DotFuncBCIInfo Info) {
	return Node->getName().str();
	}

	std::string getEdgeAttributes(const BasicBlock *Src, const_succ_iterator I,
	DotFuncBCIInfo *Info) {
	const BasicBlock Dest = I;
	if (Info->isDependent(Src, Dest))
	return "color=red";
	if (Info->isDependent(Dest, Src))
	return "color=blue";
	return "";
	}

	std::string getNodeAttributes(const BasicBlock Node, DotFuncBCIInfo Info) {
	std::string Result;
	if (Info->isInstrumented(Node))
	Result += "style=filled,fillcolor=gray";
	if (Info->isCovered(Node))
	Result += std::string(Result.empty() ? "" : ",") + "color=red";
	return Result;
	}
	};

	} // namespace llvm

	void BlockCoverageInference::viewBlockCoverageGraph(
	const DenseMap<const BasicBlock , bool> Coverage) const {
	DotFuncBCIInfo Info(this, Coverage);
	WriteGraph(&Info, "BCI", false,
	"Block Coverage Inference for " + F.getName());
	}

	void BlockCoverageInference::dump(raw_ostream &OS) const {
	OS << "Minimal block coverage for function \'" << F.getName()
	<< "\' (Instrumented=*)\n";
	for (auto &BB : F) {
	OS << (shouldInstrumentBlock(BB) ? "* " : " ") << BB.getName() << "\n";
	auto It = PredecessorDependencies.find(&BB);
	if (It != PredecessorDependencies.end() && It->second.size())
	OS << " PredDeps = " << getBlockNames(It->second) << "\n";
	It = SuccessorDependencies.find(&BB);
	if (It != SuccessorDependencies.end() && It->second.size())
	OS << " SuccDeps = " << getBlockNames(It->second) << "\n";
	}
	OS << " Instrumented Blocks Hash = 0x"
	<< Twine::utohexstr(getInstrumentedBlocksHash()) << "\n";
	}

	std::string
	BlockCoverageInference::getBlockNames(ArrayRef<const BasicBlock *> BBs) {
	std::string Result;
	raw_string_ostream OS(Result);
	OS << "[";
	if (!BBs.empty()) {
	OS << BBs.front()->getName();
	BBs = BBs.drop_front();
	}
	for (auto *BB : BBs)
	OS << ", " << BB->getName();
	OS << "]";
	return OS.str();
	}