llvm/llvm/lib/Transforms/Instrumentation/BlockCoverageInference.cpp

//===-- 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"

usingnamespacellvm;

#define DEBUG_TYPE …

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)
    : … { … }

BlockCoverageInference::BlockSet
BlockCoverageInference::getDependencies(const BasicBlock &BB) const { … }

uint64_t BlockCoverageInference::getInstrumentedBlocksHash() const { … }

bool BlockCoverageInference::shouldInstrumentBlock(const BasicBlock &BB) const { … }

void BlockCoverageInference::findDependencies() { … }

void BlockCoverageInference::getReachableAvoiding(const BasicBlock &Start,
                                                  const BasicBlock &Avoid,
                                                  bool IsForward,
                                                  BlockSet &Reachable) const { … }

namespace llvm {
class DotFuncBCIInfo { … };

template <>
struct GraphTraits<DotFuncBCIInfo *> : public GraphTraits<const BasicBlock *> { … };

template <>
struct DOTGraphTraits<DotFuncBCIInfo *> : public DefaultDOTGraphTraits { … };

} // namespace llvm

void BlockCoverageInference::viewBlockCoverageGraph(
    const DenseMap<const BasicBlock *, bool> *Coverage) const { … }

void BlockCoverageInference::dump(raw_ostream &OS) const { … }

std::string
BlockCoverageInference::getBlockNames(ArrayRef<const BasicBlock *> BBs) { … }