diff --git a/compiler-rt/test/profile/instrprof-coverage.c b/compiler-rt/test/profile/instrprof-coverage.c --- a/compiler-rt/test/profile/instrprof-coverage.c +++ b/compiler-rt/test/profile/instrprof-coverage.c @@ -1,19 +1,28 @@ // XFAIL: aix -// RUN: %clang_pgogen -mllvm -pgo-function-entry-coverage %s -o %t.out -// RUN: env LLVM_PROFILE_FILE=%t.profraw %run %t.out -// RUN: llvm-profdata merge -o %t.profdata %t.profraw -// RUN: llvm-profdata show --covered %t.profdata | FileCheck %s --check-prefix CHECK --implicit-check-not goo +// RUN: %clang_pgogen -mllvm -pgo-block-coverage %s -o %t.out +// RUN: env LLVM_PROFILE_FILE=%t1.profraw %run %t.out 1 +// RUN: env LLVM_PROFILE_FILE=%t2.profraw %run %t.out 2 +// RUN: llvm-profdata merge -o %t.profdata %t1.profraw %t2.profraw +// RUN: %clang_profuse_gcc=%t.profdata -o - -S -emit-llvm %s | FileCheck %s -int foo(int i) { return 4 * i + 1; } -int bar(int i) { return 4 * i + 2; } -int goo(int i) { return 4 * i + 3; } +#include +// CHECK: @main({{.*}}) +// CHECK-SAME: !prof ![[PROF0:[0-9]+]] int main(int argc, char *argv[]) { - foo(5); - argc ? bar(6) : goo(7); + // CHECK: br i1 %{{.*}}, label %{{.*}}, label %{{.*}}, !prof ![[PROF1:[0-9]+]] + if (argc != 2) { + return -1; + } else { + int i = atoi(argv[1]); + // CHECK: br i1 %{{.*}}, label %{{.*}}, label %{{.*}}, !prof ![[PROF2:[0-9]+]] + if (i % 2) { + return 0; + } + } return 0; } -// CHECK: main -// CHECK: foo -// CHECK: bar +// CHECK: ![[PROF0]] = !{!"function_entry_count", i64 1} +// CHECK: ![[PROF1]] = !{!"branch_weights", i32 0, i32 1} +// CHECK: ![[PROF2]] = !{!"branch_weights", i32 1, i32 1} diff --git a/compiler-rt/test/profile/instrprof-coverage.c b/compiler-rt/test/profile/instrprof-entry-coverage.c copy from compiler-rt/test/profile/instrprof-coverage.c copy to compiler-rt/test/profile/instrprof-entry-coverage.c diff --git a/llvm/include/llvm/Analysis/BlockFrequencyInfo.h b/llvm/include/llvm/Analysis/BlockFrequencyInfo.h --- a/llvm/include/llvm/Analysis/BlockFrequencyInfo.h +++ b/llvm/include/llvm/Analysis/BlockFrequencyInfo.h @@ -64,6 +64,10 @@ /// floating points. BlockFrequency getBlockFreq(const BasicBlock *BB) const; + /// Returns true if this block is rarely executed or dead. + Optional isBlockRarelyExecuted(const BasicBlock *BB, + bool AllowSynthetic = false) const; + /// Returns the estimated profile count of \p BB. /// This computes the relative block frequency of \p BB and multiplies it by /// the enclosing function's count (if available) and returns the value. diff --git a/llvm/include/llvm/Transforms/Instrumentation/BlockCoverageInference.h b/llvm/include/llvm/Transforms/Instrumentation/BlockCoverageInference.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/Instrumentation/BlockCoverageInference.h @@ -0,0 +1,99 @@ +//===-- BlockCoverageInference.h - 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 +// +//===----------------------------------------------------------------------===// +// +// This file finds the minimum set of blocks on a CFG that must be instrumented +// to infer execution coverage for the whole graph. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H +#define LLVM_LIB_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SetVector.h" +#include +#include + +namespace llvm { + +class Function; +class BasicBlock; +class DotFuncBCIInfo; + +class BlockCoverageInference { + friend class DotFuncBCIInfo; + +public: + using BlockList = SmallVector; + using BlockSet = SmallSetVector; + + BlockCoverageInference(Function *F, bool ForceInstrumentEntry); + + /// Finds the minimal set of basic blocks needed to instrument block coverage. + void getBlocksToInstrument(std::vector &Blocks) const; + + /// Return the set of blocks such that BB is covered iff any of them are + /// covered. + BlockSet getDependencies(BasicBlock *BB) const; + + /// Return a hash that depends on the set of instrumented blocks. + uint64_t getInstrumentedBlocksHash() const; + + /// Dump the inference graph. + void dump(raw_ostream &OS) const; + + /// View the inferred block coverage as a dot file. + /// Filled gray blocks are instrumented, red outlined blocks are found to be + /// covered, red edges show that a block's coverage can be inferred from + /// successors, and blue edges show that a block's coverage can be inferred + /// from predecessors. + void + viewBlockCoverageGraph(const DenseMap &Coverage) const; + +private: + Function *F; + bool ForceInstrumentEntry; + + /// Maps blocks to a minimal list of predecessors that can be used to infer + /// this block's coverage. + std::map PredecessorDependencies; + + /// Maps blocks to a minimal list of successors that can be used to infer + /// this block's coverage. + std::map SuccessorDependencies; + + /// A helper function to lookup the dependencies of a basic block. + const BlockSet &get(const std::map &Dependencies, + BasicBlock *BB) const; + + /// Returns true if this block should be instrumented for coverage. + bool shouldInstrumentBlock(BasicBlock *BB) const; + + // Returns true if ever block in the function can reach some exit block, + // otherwise this algorithm will not work. + bool canFindMinimalCoverage(Function *F) const; + + /// Compute `PredecessorDependencies`, `SuccessorDependencies`, and + /// `Dependencies`. + void findDependencies(); + + /// Find the set of basic blocks that are reachable from `Entry`/`Exit` + /// without the basic block `Avoid`. + void getReachableAvoiding(BasicBlock *Start, BasicBlock *Avoid, + bool IsForward, BlockSet &Reachable) const; + + static std::string getBlockNames(ArrayRef BBs); + static std::string getBlockNames(BlockSet BBs) { + return getBlockNames(ArrayRef(BBs.begin(), BBs.end())); + } +}; + +} // end namespace llvm + +#endif // LLVM_LIB_TRANSFORMS_INSTRUMENTATION_BLOCKCOVERAGEINFERENCE_H diff --git a/llvm/lib/Analysis/BlockFrequencyInfo.cpp b/llvm/lib/Analysis/BlockFrequencyInfo.cpp --- a/llvm/lib/Analysis/BlockFrequencyInfo.cpp +++ b/llvm/lib/Analysis/BlockFrequencyInfo.cpp @@ -204,6 +204,26 @@ return BFI ? BFI->getBlockFreq(BB) : 0; } +Optional +BlockFrequencyInfo::isBlockRarelyExecuted(const BasicBlock *BB, + bool AllowSynthetic) const { + if (!BFI) + return None; + + Optional IsEntryCountZero = + BB->getParent()->getEntryCount(AllowSynthetic).map([](auto C) { + return C.getCount() == 0; + }); + if (BB->isEntryBlock()) + return IsEntryCountZero; + + if (IsEntryCountZero.hasValue() && IsEntryCountZero.getValue()) + return true; + + auto Epsilon = BlockFrequencyInfoImplBase::Scaled64::getInverse(10000); + return BFI->getFloatingBlockFreq(BB) < Epsilon; +} + Optional BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB, bool AllowSynthetic) const { diff --git a/llvm/lib/Transforms/Instrumentation/BlockCoverageInference.cpp b/llvm/lib/Transforms/Instrumentation/BlockCoverageInference.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Instrumentation/BlockCoverageInference.cpp @@ -0,0 +1,374 @@ +//===-- 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. +// +//===----------------------------------------------------------------------===// + +#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(NumIneligibleFunctions, + "Number of functions for which BCI cannot run on"); +STATISTIC(NumInstrumentedBlocks, + "Number of basic blocks instrumented for coverage"); + +namespace llvm { + +BlockCoverageInference::BlockCoverageInference(Function *F, + bool ForceInstrumentEntry) + : F(F), ForceInstrumentEntry(ForceInstrumentEntry) { + assert(F); + findDependencies(); + assert(!ForceInstrumentEntry || shouldInstrumentBlock(&F->getEntryBlock())); + + for (auto &BB : *F) + if (shouldInstrumentBlock(&BB)) + NumInstrumentedBlocks++; +} + +void BlockCoverageInference::getBlocksToInstrument( + std::vector &Blocks) const { + for (auto &BB : *F) + if (shouldInstrumentBlock(&BB)) + Blocks.push_back(&BB); +} + +BlockCoverageInference::BlockSet +BlockCoverageInference::getDependencies(BasicBlock *BB) const { + assert(BB && BB->getParent() == F); + BlockSet Dependencies; + Dependencies.set_union(get(PredecessorDependencies, BB)); + Dependencies.set_union(get(SuccessorDependencies, BB)); + 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(BasicBlock *BB) const { + assert(BB && BB->getParent() == F); + return get(PredecessorDependencies, BB).size() == 0 && + get(SuccessorDependencies, BB).size() == 0; +} + +bool BlockCoverageInference::canFindMinimalCoverage(Function *F) const { + if (F->hasFnAttribute(Attribute::NoReturn)) + return false; + // Traverse the CFG backwards from the exit blocks to make sure every block + // can reach some exit block. + df_iterator_default_set Visited; + for (auto &BB : *F) + if (succ_empty(&BB)) + for (auto *N : inverse_depth_first_ext(&BB, Visited)) + (void)N; + if (std::distance(F->begin(), F->end()) == + std::distance(Visited.begin(), Visited.end())) + return true; + return false; +} + +void BlockCoverageInference::findDependencies() { + assert(!PredecessorDependencies.size() && !SuccessorDependencies.size()); + // Fallback to instrumenting every block for functions that we cannot run this + // algorithm on. + if (!canFindMinimalCoverage(F)) { + NumIneligibleFunctions++; + return; + } + + auto &EntryBlock = F->getEntryBlock(); + BlockList ExitBlocks; + for (auto &BB : *F) + if (succ_empty(&BB)) + ExitBlocks.push_back(&BB); + + for (auto &BB : *F) { + // The set of blocks that are reachable while avoiding BB. + BlockSet ReachableFromEntry, ReachableFromExit; + getReachableAvoiding(&EntryBlock, &BB, /*IsForward=*/true, + ReachableFromEntry); + for (auto *ExitBlock : ExitBlocks) + getReachableAvoiding(ExitBlock, &BB, /*IsForward=*/false, + ReachableFromExit); + + auto Preds = predecessors(&BB); + bool HasSuperReachablePred = + std::any_of(Preds.begin(), Preds.end(), [&](auto *Pred) { + return ReachableFromEntry.count(Pred) && + ReachableFromExit.count(Pred); + }); + if (!HasSuperReachablePred) + for (auto *Pred : Preds) + if (ReachableFromEntry.count(Pred)) + PredecessorDependencies[&BB].insert(Pred); + + auto Succs = successors(&BB); + bool HasSuperReachableSucc = + std::any_of(Succs.begin(), Succs.end(), [&](auto *Succ) { + return ReachableFromEntry.count(Succ) && + ReachableFromExit.count(Succ); + }); + if (!HasSuperReachableSucc) + for (auto *Succ : Succs) + if (ReachableFromExit.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[&F->getEntryBlock()].clear(); + SuccessorDependencies[&F->getEntryBlock()].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 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) -> 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.front()) ? Neighbors.front() + : Neighbors.back(); + } + // 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 (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(); + } + } + } + + // If we have a choice to infer coverage from a block's predecessor or + // successor, choose its predecessor. + for (auto &BB : *F) + if (PredecessorDependencies[&BB].size() && + SuccessorDependencies[&BB].size()) + SuccessorDependencies[&BB].clear(); + LLVM_DEBUG(dump(dbgs())); +} + +void BlockCoverageInference::getReachableAvoiding(BasicBlock *Start, + BasicBlock *Avoid, + bool IsForward, + BlockSet &Reachable) const { + df_iterator_default_set Visited; + Visited.insert(Avoid); + if (IsForward) { + for (auto *BB : depth_first_ext(Start, Visited)) + Reachable.insert(BB); + } else { + for (auto *BB : inverse_depth_first_ext(Start, Visited)) + Reachable.insert(BB); + } +} + +const BlockCoverageInference::BlockSet &BlockCoverageInference::get( + const std::map &Dependencies, + BasicBlock *BB) const { + static const BlockSet EmptyBlockSet; + if (!Dependencies.count(BB)) + return EmptyBlockSet; + return Dependencies.at(BB); +} + +class DotFuncBCIInfo { +private: + const BlockCoverageInference *BCI; + const DenseMap &Coverage; + +public: + DotFuncBCIInfo(const BlockCoverageInference *BCI, + const DenseMap &Coverage) + : BCI(BCI), Coverage(Coverage) {} + + const Function *getFunction() { return BCI->F; } + + bool isInstrumented(const BasicBlock *BB) const { + return BCI->shouldInstrumentBlock(const_cast(BB)); + } + + bool isCovered(const BasicBlock *BB) const { return Coverage.lookup(BB); } + + bool isDependent(const BasicBlock *Src, const BasicBlock *Dest) const { + return BCI->getDependencies(const_cast(Src)) + .count(const_cast(Dest)); + } +}; + +template <> +struct GraphTraits : public GraphTraits { + 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; + + 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 : 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; + } +}; + +void BlockCoverageInference::viewBlockCoverageGraph( + const DenseMap &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() << "\n"; + for (auto &BB : *F) + OS << " Dependencies[" << BB.getName() << "] = {\n Preds: " + << getBlockNames(get(PredecessorDependencies, &BB)) + << ",\n Succs: " << getBlockNames(get(SuccessorDependencies, &BB)) + << "\n }\n"; + OS << " Instrumented Blocks Hash = 0x" + << Twine::utohexstr(getInstrumentedBlocksHash()) << "\n"; + std::vector Blocks; + getBlocksToInstrument(Blocks); + OS << " Instrumented Blocks = " << getBlockNames(Blocks) << "\n"; +} + +std::string BlockCoverageInference::getBlockNames(ArrayRef 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(); +} + +} // namespace llvm diff --git a/llvm/lib/Transforms/Instrumentation/CMakeLists.txt b/llvm/lib/Transforms/Instrumentation/CMakeLists.txt --- a/llvm/lib/Transforms/Instrumentation/CMakeLists.txt +++ b/llvm/lib/Transforms/Instrumentation/CMakeLists.txt @@ -5,6 +5,7 @@ ControlHeightReduction.cpp DataFlowSanitizer.cpp GCOVProfiling.cpp + BlockCoverageInference.cpp MemProfiler.cpp MemorySanitizer.cpp IndirectCallPromotion.cpp diff --git a/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp b/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp --- a/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp +++ b/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp @@ -107,6 +107,7 @@ #include "llvm/Support/GraphWriter.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Instrumentation.h" +#include "llvm/Transforms/Instrumentation/BlockCoverageInference.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/MisExpect.h" #include "llvm/Transforms/Utils/ModuleUtils.h" @@ -149,6 +150,7 @@ STATISTIC(NumOfCSPGOMismatch, "Number of functions having mismatch profile in CSPGO."); STATISTIC(NumOfCSPGOMissing, "Number of functions without profile in CSPGO."); +STATISTIC(NumCoveredBlocks, "Number of basic blocks that were executed"); // Command line option to specify the file to read profile from. This is // mainly used for testing. @@ -259,6 +261,17 @@ cl::desc( "Use this option to enable function entry coverage instrumentation.")); +static cl::opt PGOBlockCoverage( + "pgo-block-coverage", cl::init(false), cl::Hidden, cl::ZeroOrMore, + cl::desc( + "Use this option to enable basic block coverage instrumentation.")); + +static cl::opt + PGOViewBlockCoverageGraph("pgo-view-block-coverage-graph", cl::init(false), + cl::Hidden, cl::ZeroOrMore, + cl::desc("Create a dot file of CFGs with block " + "coverage inference information.")); + static cl::opt PGOFixEntryCount("pgo-fix-entry-count", cl::init(true), cl::Hidden, cl::desc("Fix function entry count in profile use.")); @@ -356,6 +369,8 @@ if (PGOFunctionEntryCoverage) ProfileVersion |= VARIANT_MASK_BYTE_COVERAGE | VARIANT_MASK_FUNCTION_ENTRY_ONLY; + if (PGOBlockCoverage) + ProfileVersion |= VARIANT_MASK_BYTE_COVERAGE; auto IRLevelVersionVariable = new GlobalVariable( M, IntTy64, true, GlobalValue::WeakAnyLinkage, Constant::getIntegerValue(IntTy64, APInt(64, ProfileVersion)), VarName); @@ -388,8 +403,10 @@ GlobalVariable *FuncNameVar = nullptr; uint64_t FuncHash = 0; PGOUseFunc *UseFunc = nullptr; + bool HasSingleByteCoverage; - SelectInstVisitor(Function &Func) : F(Func) {} + SelectInstVisitor(Function &Func, bool HasSingleByteCoverage) + : F(Func), HasSingleByteCoverage(HasSingleByteCoverage) {} void countSelects(Function &Func) { NSIs = 0; @@ -506,6 +523,10 @@ // The Minimum Spanning Tree of function CFG. CFGMST MST; + bool HasSingleByteCoverage; + + Optional BCI; + // Collect all the BBs that will be instrumented, and store them in // InstrumentBBs. void getInstrumentBBs(std::vector &InstrumentBBs); @@ -531,16 +552,22 @@ std::unordered_multimap &ComdatMembers, bool CreateGlobalVar = false, BranchProbabilityInfo *BPI = nullptr, BlockFrequencyInfo *BFI = nullptr, bool IsCS = false, - bool InstrumentFuncEntry = true) + bool InstrumentFuncEntry = true, bool HasSingleByteCoverage = false) : F(Func), IsCS(IsCS), ComdatMembers(ComdatMembers), VPC(Func, TLI), - ValueSites(IPVK_Last + 1), SIVisitor(Func), - MST(F, InstrumentFuncEntry, BPI, BFI) { + ValueSites(IPVK_Last + 1), SIVisitor(Func, HasSingleByteCoverage), + MST(F, InstrumentFuncEntry, BPI, BFI), + HasSingleByteCoverage(HasSingleByteCoverage) { + if (HasSingleByteCoverage) { + // TODO: We can actually avoid constructing the MST in this case. + BCI.emplace(&Func, InstrumentFuncEntry); + } // This should be done before CFG hash computation. SIVisitor.countSelects(Func); ValueSites[IPVK_MemOPSize] = VPC.get(IPVK_MemOPSize); if (!IsCS) { NumOfPGOSelectInsts += SIVisitor.getNumOfSelectInsts(); NumOfPGOMemIntrinsics += ValueSites[IPVK_MemOPSize].size(); + // FIXME: BBInfos include fake nodes which inflates this statistic. NumOfPGOBB += MST.BBInfos.size(); ValueSites[IPVK_IndirectCallTarget] = VPC.get(IPVK_IndirectCallTarget); } else { @@ -609,7 +636,11 @@ updateJCH((uint64_t)SIVisitor.getNumOfSelectInsts()); updateJCH((uint64_t)ValueSites[IPVK_IndirectCallTarget].size()); updateJCH((uint64_t)ValueSites[IPVK_MemOPSize].size()); - updateJCH((uint64_t)MST.AllEdges.size()); + if (HasSingleByteCoverage) { + updateJCH(BCI->getInstrumentedBlocksHash()); + } else { + updateJCH((uint64_t)MST.AllEdges.size()); + } // Hash format for context sensitive profile. Reserve 4 bits for other // information. @@ -698,6 +729,11 @@ template void FuncPGOInstrumentation::getInstrumentBBs( std::vector &InstrumentBBs) { + if (HasSingleByteCoverage) { + BCI->getBlocksToInstrument(InstrumentBBs); + return; + } + // Use a worklist as we will update the vector during the iteration. std::vector EdgeList; EdgeList.reserve(MST.AllEdges.size()); @@ -820,12 +856,15 @@ BlockFrequencyInfo *BFI, std::unordered_multimap &ComdatMembers, bool IsCS) { - // Split indirectbr critical edges here before computing the MST rather than - // later in getInstrBB() to avoid invalidating it. - SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/false, BPI, BFI); + if (!PGOBlockCoverage) { + // Split indirectbr critical edges here before computing the MST rather than + // later in getInstrBB() to avoid invalidating it. + SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/false, BPI, BFI); + } FuncPGOInstrumentation FuncInfo( - F, TLI, ComdatMembers, true, BPI, BFI, IsCS, PGOInstrumentEntry); + F, TLI, ComdatMembers, true, BPI, BFI, IsCS, PGOInstrumentEntry, + PGOBlockCoverage); Type *I8PtrTy = Type::getInt8PtrTy(M->getContext()); auto Name = ConstantExpr::getBitCast(FuncInfo.FuncNameVar, I8PtrTy); @@ -857,7 +896,9 @@ // llvm.instrprof.increment(i8* , i64 , i32 , // i32 ) Builder.CreateCall( - Intrinsic::getDeclaration(M, Intrinsic::instrprof_increment), + Intrinsic::getDeclaration(M, PGOBlockCoverage + ? Intrinsic::instrprof_cover + : Intrinsic::instrprof_increment), {Name, CFGHash, Builder.getInt32(NumCounters), Builder.getInt32(I++)}); } @@ -1000,12 +1041,15 @@ PGOUseFunc(Function &Func, Module *Modu, TargetLibraryInfo &TLI, std::unordered_multimap &ComdatMembers, BranchProbabilityInfo *BPI, BlockFrequencyInfo *BFIin, - ProfileSummaryInfo *PSI, bool IsCS, bool InstrumentFuncEntry) + ProfileSummaryInfo *PSI, bool IsCS, bool InstrumentFuncEntry, + bool HasSingleByteCoverage) : F(Func), M(Modu), BFI(BFIin), PSI(PSI), FuncInfo(Func, TLI, ComdatMembers, false, BPI, BFIin, IsCS, - InstrumentFuncEntry), + InstrumentFuncEntry, HasSingleByteCoverage), FreqAttr(FFA_Normal), IsCS(IsCS) {} + void handleInstrProfError(Error Err); + // Read counts for the instrumented BB from profile. bool readCounters(IndexedInstrProfReader *PGOReader, bool &AllZeros, bool &AllMinusOnes); @@ -1013,6 +1057,9 @@ // Populate the counts for all BBs. void populateCounters(); + // Set block coverage based on profile coverage values. + void populateCoverage(IndexedInstrProfReader *PGOReader); + // Set the branch weights based on the count values. void setBranchWeights(); @@ -1210,6 +1257,43 @@ F.setMetadata(LLVMContext::MD_annotation, MD); } +void PGOUseFunc::handleInstrProfError(Error Err) { + handleAllErrors(std::move(Err), [&](const InstrProfError &IPE) { + auto &Ctx = M->getContext(); + auto Err = IPE.get(); + bool SkipWarning = false; + LLVM_DEBUG(dbgs() << "Error in reading profile for Func " + << FuncInfo.FuncName << ": "); + if (Err == instrprof_error::unknown_function) { + IsCS ? NumOfCSPGOMissing++ : NumOfPGOMissing++; + SkipWarning = !PGOWarnMissing; + LLVM_DEBUG(dbgs() << "unknown function"); + } else if (Err == instrprof_error::hash_mismatch || + Err == instrprof_error::malformed) { + IsCS ? NumOfCSPGOMismatch++ : NumOfPGOMismatch++; + SkipWarning = + NoPGOWarnMismatch || + (NoPGOWarnMismatchComdat && + (F.hasComdat() || + F.getLinkage() == GlobalValue::AvailableExternallyLinkage)); + LLVM_DEBUG(dbgs() << "hash mismatch (skip=" << SkipWarning << ")"); + // Emit function metadata indicating PGO profile mismatch. + annotateFunctionWithHashMismatch(F, Ctx); + } + + LLVM_DEBUG(dbgs() << " IsCS=" << IsCS << "\n"); + if (SkipWarning) + return; + + std::string Msg = IPE.message() + std::string(" ") + F.getName().str() + + std::string(" Hash = ") + + std::to_string(FuncInfo.FunctionHash); + + Ctx.diagnose( + DiagnosticInfoPGOProfile(M->getName().data(), Msg, DS_Warning)); + }); +} + // Read the profile from ProfileFileName and assign the value to the // instrumented BB and the edges. This function also updates ProgramMaxCount. // Return true if the profile are successfully read, and false on errors. @@ -1219,39 +1303,7 @@ Expected Result = PGOReader->getInstrProfRecord(FuncInfo.FuncName, FuncInfo.FunctionHash); if (Error E = Result.takeError()) { - handleAllErrors(std::move(E), [&](const InstrProfError &IPE) { - auto Err = IPE.get(); - bool SkipWarning = false; - LLVM_DEBUG(dbgs() << "Error in reading profile for Func " - << FuncInfo.FuncName << ": "); - if (Err == instrprof_error::unknown_function) { - IsCS ? NumOfCSPGOMissing++ : NumOfPGOMissing++; - SkipWarning = !PGOWarnMissing; - LLVM_DEBUG(dbgs() << "unknown function"); - } else if (Err == instrprof_error::hash_mismatch || - Err == instrprof_error::malformed) { - IsCS ? NumOfCSPGOMismatch++ : NumOfPGOMismatch++; - SkipWarning = - NoPGOWarnMismatch || - (NoPGOWarnMismatchComdat && - (F.hasComdat() || - F.getLinkage() == GlobalValue::AvailableExternallyLinkage)); - LLVM_DEBUG(dbgs() << "hash mismatch (skip=" << SkipWarning << ")"); - // Emit function metadata indicating PGO profile mismatch. - annotateFunctionWithHashMismatch(F, M->getContext()); - } - - LLVM_DEBUG(dbgs() << " IsCS=" << IsCS << "\n"); - if (SkipWarning) - return; - - std::string Msg = IPE.message() + std::string(" ") + F.getName().str() + - std::string(" Hash = ") + - std::to_string(FuncInfo.FunctionHash); - - Ctx.diagnose( - DiagnosticInfoPGOProfile(M->getName().data(), Msg, DS_Warning)); - }); + handleInstrProfError(std::move(E)); return false; } ProfileRecord = std::move(Result.get()); @@ -1288,6 +1340,105 @@ return true; } +void PGOUseFunc::populateCoverage(IndexedInstrProfReader *PGOReader) { + Expected Result = + PGOReader->getInstrProfRecord(FuncInfo.FuncName, FuncInfo.FunctionHash); + if (auto Err = Result.takeError()) { + handleInstrProfError(std::move(Err)); + return; + } + DenseMap Coverage; + for (auto &BB : F) + Coverage[&BB] = false; + + // Set coverage of instrumented blocks. + std::vector &CountsFromProfile = Result.get().Counts; + std::vector InstrumentedBlocks; + FuncInfo.BCI->getBlocksToInstrument(InstrumentedBlocks); + assert(CountsFromProfile.size() == InstrumentedBlocks.size()); + for (unsigned i = 0; i < InstrumentedBlocks.size(); i++) + Coverage[InstrumentedBlocks[i]] = (CountsFromProfile[i] != 0); + + // Infer coverage of the non-instrumented blocks. + bool WasChanged = true; + while (WasChanged) { + WasChanged = false; + // It is possible to infer coverage in one pass, but the speedup might not + // be impactful for small CFGs. + for (auto &BB : F) { + if (Coverage[&BB]) + continue; + for (auto *Dep : FuncInfo.BCI->getDependencies(&BB)) { + if (Coverage[Dep]) { + Coverage[&BB] = true; + WasChanged = true; + } + } + } + } + + // Annotate block coverage. + MDBuilder MDB(F.getContext()); + // We set the entry count to 1 if the entry block is covered to indicate + // function coverage. Note that BFI will not be able to propagate counts + // through all covered blocks when there are branches since BFI does not track + // fractional counts. This means `BFI.getBlockProfileCount(BB)` cannot + // indicate coverage unless we set a large "fake" entry count, e.g., 1000 + // instead of 1. + F.setEntryCount( + ProfileCount(Coverage[&F.getEntryBlock()] ? 1 : 0, Function::PCT_Real)); + for (auto &BB : F) { + // For a block A and its successor B, we set the edge weight as follows: + // If A is covered and B is covered, set weight=1. + // If A is covered and B is uncovered, set weight=0. + // If A is uncovered, set weight=1. + // This setup will allow us to query BFI for dead blocks using + // `BFI.isBlockRarelyExecuted(&BB)`. + SmallVector Weights; + for (auto *Succ : successors(&BB)) + Weights.push_back((Coverage[Succ] || !Coverage[&BB]) ? 1 : 0); + if (Weights.size() >= 2) + BB.getTerminator()->setMetadata(LLVMContext::MD_prof, + MDB.createBranchWeights(Weights)); + } + + unsigned NumCorruptCoverage = 0; + DominatorTree DT(F); + LoopInfo LI(DT); + BranchProbabilityInfo BPI(F, LI); + BlockFrequencyInfo BFI(F, BPI, LI); + LLVM_DEBUG(dbgs() << "Block Coverage: (Instrumented=*, Covered=X)\n"); + for (auto &BB : F) { + LLVM_DEBUG(dbgs() << (std::count(InstrumentedBlocks.begin(), + InstrumentedBlocks.end(), &BB) + ? "* " + : " ") + << (Coverage[&BB] ? "X " : " ") << " " << BB.getName() + << "\n"); + // In some cases it is possible to find that a covered block has no covered + // successors, e.g., when a block calls a function that calls exit(). In + // those cases, BFI will assume its successors are covered. + if (Coverage[&BB] == BFI.isBlockRarelyExecuted(&BB).getValue()) { + LLVM_DEBUG(dbgs() << "Found inconsistent block covearge for " + << BB.getName() << ": BCI=" << Coverage[&BB] << " BFI=" + << !BFI.isBlockRarelyExecuted(&BB).getValue() << "\n"); + NumCorruptCoverage++; + } + if (Coverage[&BB]) + NumCoveredBlocks++; + } + if (PGOVerifyBFI && NumCorruptCoverage) { + auto &Ctx = M->getContext(); + Ctx.diagnose(DiagnosticInfoPGOProfile( + M->getName().data(), + Twine("Found inconsistent block coverage for function ") + F.getName() + + " in " + Twine(NumCorruptCoverage) + " blocks.", + DS_Warning)); + } + if (PGOViewBlockCoverageGraph) + FuncInfo.BCI->viewBlockCoverageGraph(Coverage); +} + // Populate the counters from instrumented BBs to all BBs. // In the end of this operation, all BBs should have a valid count value. void PGOUseFunc::populateCounters() { @@ -1432,8 +1583,6 @@ } void SelectInstVisitor::instrumentOneSelectInst(SelectInst &SI) { - if (PGOFunctionEntryCoverage) - return; Module *M = F.getParent(); IRBuilder<> Builder(&SI); Type *Int64Ty = Builder.getInt64Ty(); @@ -1466,7 +1615,9 @@ } void SelectInstVisitor::visitSelectInst(SelectInst &SI) { - if (!PGOInstrSelect) + // TODO: We can instrument coverage on selects by adding a new + // llvm.instrprof.cover.select intrinsic. + if (!PGOInstrSelect || PGOFunctionEntryCoverage || HasSingleByteCoverage) return; // FIXME: do not handle this yet. if (SI.getCondition()->getType()->isVectorTy()) @@ -1757,12 +1908,6 @@ ProfileFileName.data(), "Not an IR level instrumentation profile")); return false; } - if (PGOReader->hasSingleByteCoverage()) { - Ctx.diagnose(DiagnosticInfoPGOProfile( - ProfileFileName.data(), - "Cannot use coverage profiles for optimization")); - return false; - } if (PGOReader->functionEntryOnly()) { Ctx.diagnose(DiagnosticInfoPGOProfile( ProfileFileName.data(), @@ -1788,17 +1933,25 @@ bool InstrumentFuncEntry = PGOReader->instrEntryBBEnabled(); if (PGOInstrumentEntry.getNumOccurrences() > 0) InstrumentFuncEntry = PGOInstrumentEntry; + bool HasSingleByteCoverage = PGOReader->hasSingleByteCoverage(); for (auto &F : M) { if (F.isDeclaration()) continue; auto &TLI = LookupTLI(F); auto *BPI = LookupBPI(F); auto *BFI = LookupBFI(F); - // Split indirectbr critical edges here before computing the MST rather than - // later in getInstrBB() to avoid invalidating it. - SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/false, BPI, BFI); + if (!HasSingleByteCoverage) { + // Split indirectbr critical edges here before computing the MST rather + // than later in getInstrBB() to avoid invalidating it. + SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/false, BPI, + BFI); + } PGOUseFunc Func(F, &M, TLI, ComdatMembers, BPI, BFI, PSI, IsCS, - InstrumentFuncEntry); + InstrumentFuncEntry, HasSingleByteCoverage); + if (HasSingleByteCoverage) { + Func.populateCoverage(PGOReader.get()); + continue; + } // When AllMinusOnes is true, it means the profile for the function // is unrepresentative and this function is actually hot. Set the // entry count of the function to be multiple times of hot threshold diff --git a/llvm/test/Transforms/PGOProfile/coverage.ll b/llvm/test/Transforms/PGOProfile/coverage.ll --- a/llvm/test/Transforms/PGOProfile/coverage.ll +++ b/llvm/test/Transforms/PGOProfile/coverage.ll @@ -1,26 +1,65 @@ -; RUN: opt < %s -passes=pgo-instr-gen -pgo-function-entry-coverage -S | FileCheck %s +; RUN: opt < %s -passes=pgo-instr-gen -pgo-function-entry-coverage -S | FileCheck %s --implicit-check-not="instrprof.cover" --check-prefixes=CHECK,ENTRY +; RUN: opt < %s -passes=pgo-instr-gen -pgo-block-coverage -S | FileCheck %s --implicit-check-not="instrprof.cover" --check-prefixes=CHECK,BLOCK target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" -define i32 @foo(i32 %i) { +define void @foo() { +; CHECK-LABEL: entry: entry: - ; CHECK: call void @llvm.instrprof.cover({{.*}}) - %cmp = icmp sgt i32 %i, 0 - br i1 %cmp, label %if.then, label %if.else + ; ENTRY: call void @llvm.instrprof.cover({{.*}}) + %c = call i1 @choice() + br i1 %c, label %if.then, label %if.else +; CHECK-LABEL: if.then: if.then: - ; CHECK-NOT: llvm.instrprof.cover( - %add = add nsw i32 %i, 2 - %s = select i1 %cmp, i32 %add, i32 0 + ; BLOCK: call void @llvm.instrprof.cover({{.*}}) br label %if.end +; CHECK-LABEL: if.else: if.else: - %sub = sub nsw i32 %i, 2 + ; BLOCK: call void @llvm.instrprof.cover({{.*}}) + br label %if.end + +; CHECK-LABEL: if.end: +if.end: + ret void +} + +define void @bar() { +; CHECK-LABEL: entry: +entry: + ; ENTRY: call void @llvm.instrprof.cover({{.*}}) + %c = call i1 @choice() + br i1 %c, label %if.then, label %if.end + +; CHECK-LABEL: if.then: +if.then: + ; BLOCK: call void @llvm.instrprof.cover({{.*}}) br label %if.end +; CHECK-LABEL: if.end: if.end: - %retv = phi i32 [ %add, %if.then ], [ %sub, %if.else ] - ret i32 %retv + ; BLOCK: call void @llvm.instrprof.cover({{.*}}) + ret void } -; CHECK: declare void @llvm.instrprof.cover( +define void @goo() { +; CHECK-LABEL: entry: +entry: + ; CHECK: call void @llvm.instrprof.cover({{.*}}) + ret void +} + +define void @loop() { +; CHECK-LABEL: entry: +entry: + ; CHECK: call void @llvm.instrprof.cover({{.*}}) + br label %while +while: + ; BLOCK: call void @llvm.instrprof.cover({{.*}}) + br label %while +} + +declare i1 @choice() + +; CHECK: declare void @llvm.instrprof.cover({{.*}})