BlockCoverageInference.cpp Source File (original) (raw)

39using namespace llvm;

41#define DEBUG_TYPE "pgo-block-coverage"

43 STATISTIC(NumFunctions, "Number of total functions that BCI has processed");

45 "Number of functions for which BCI cannot run on");

46 STATISTIC(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) {

53 findDependencies();

56 ++NumFunctions;

57 for (auto &BB : F) {

58 ++NumBlocks;

60 ++NumInstrumentedBlocks;

61 }

62}

68 auto It = PredecessorDependencies.find(&BB);

69 if (It != PredecessorDependencies.end())

70 Dependencies.set_union(It->second);

71 It = SuccessorDependencies.find(&BB);

72 if (It != SuccessorDependencies.end())

73 Dependencies.set_union(It->second);

74 return Dependencies;

75}

80 for (auto &BB : F) {

85 }

86 Index++;

87 }

89}

93 auto It = PredecessorDependencies.find(&BB);

94 if (It != PredecessorDependencies.end() && It->second.size())

95 return false;

96 It = SuccessorDependencies.find(&BB);

97 if (It != SuccessorDependencies.end() && It->second.size())

98 return false;

99 return true;

100}

101

102void BlockCoverageInference::findDependencies() {

103 assert(PredecessorDependencies.empty() && SuccessorDependencies.empty());

104

105

106 if (F.hasFnAttribute(Attribute::NoReturn) || F.size() > 1500) {

107 ++NumIneligibleFunctions;

108 return;

109 }

110

112 for (auto &BB : F)

115

116

117

118

120 for (auto *BB : TerminalBlocks)

122 (void)N;

123 if (F.size() != Visited.size()) {

124 ++NumIneligibleFunctions;

125 return;

126 }

127

128

129

130

131

132

133

134 auto &EntryBlock = F.getEntryBlock();

135 for (auto &BB : F) {

136

137 BlockSet ReachableFromEntry, ReachableFromTerminal;

138 getReachableAvoiding(EntryBlock, BB, true,

139 ReachableFromEntry);

140 for (auto *TerminalBlock : TerminalBlocks)

141 getReachableAvoiding(*TerminalBlock, BB, false,

142 ReachableFromTerminal);

143

145 bool HasSuperReachablePred = llvm::any_of(Preds, [&](auto *Pred) {

146 return ReachableFromEntry.count(Pred) &&

147 ReachableFromTerminal.count(Pred);

148 });

149 if (!HasSuperReachablePred)

150 for (auto *Pred : Preds)

151 if (ReachableFromEntry.count(Pred))

152 PredecessorDependencies[&BB].insert(Pred);

153

155 bool HasSuperReachableSucc = llvm::any_of(Succs, [&](auto *Succ) {

156 return ReachableFromEntry.count(Succ) &&

157 ReachableFromTerminal.count(Succ);

158 });

159 if (!HasSuperReachableSucc)

160 for (auto *Succ : Succs)

161 if (ReachableFromTerminal.count(Succ))

162 SuccessorDependencies[&BB].insert(Succ);

163 }

164

165 if (ForceInstrumentEntry) {

166

167

168 PredecessorDependencies[&EntryBlock].clear();

169 SuccessorDependencies[&EntryBlock].clear();

170 }

171

172

173

174

175 DenseMap<const BasicBlock *, BlockSet> AdjacencyList;

176 for (auto &BB : F) {

178 if (SuccessorDependencies[&BB].count(Succ) &&

179 PredecessorDependencies[Succ].count(&BB)) {

180 AdjacencyList[&BB].insert(Succ);

181 AdjacencyList[Succ].insert(&BB);

182 }

183 }

184 }

185

186

187 auto getNextOnPath = [&](BlockSet &Path) -> const BasicBlock * {

189 auto &Neighbors = AdjacencyList[Path.back()];

190 if (Path.size() == 1) {

191

192 assert(Neighbors.size() == 1);

193 return Neighbors.front();

194 } else if (Neighbors.size() == 2) {

195

196

198 return Path.count(Neighbors[0]) ? Neighbors[1] : Neighbors[0];

199 }

200

201 assert(Neighbors.size() == 1);

202 return nullptr;

203 };

204

205

206 for (auto &BB : F) {

207 if (AdjacencyList[&BB].size() == 1) {

208

210 Path.insert(&BB);

211 while (const BasicBlock *Next = getNextOnPath(Path))

213 LLVM_DEBUG(dbgs() << "Found path: " << getBlockNames(Path) << "\n");

214

215

216 for (auto *BB : Path)

217 AdjacencyList[BB].clear();

218

219

220 if (PredecessorDependencies[Path.front()].size()) {

221 for (auto *BB : Path)

222 if (BB != Path.back())

223 SuccessorDependencies[BB].clear();

224 } else {

225 for (auto *BB : Path)

226 if (BB != Path.front())

227 PredecessorDependencies[BB].clear();

228 }

229 }

230 }

232}

233

234void BlockCoverageInference::getReachableAvoiding(const BasicBlock &Start,

236 bool IsForward,

238 df_iterator_default_set<const BasicBlock *> Visited;

239 Visited.insert(&Avoid);

240 if (IsForward) {

242 Reachable.insert_range(Range);

243 } else {

245 Reachable.insert_range(Range);

246 }

247}

248

249namespace llvm {

251private:

254

255public:

258 : BCI(BCI), Coverage(Coverage) {}

259

261

263 return BCI->shouldInstrumentBlock(*BB);

264 }

265

267 return Coverage && Coverage->lookup(BB);

268 }

269

271 return BCI->getDependencies(*Src).count(Dest);

272 }

273};

274

275template <>

278 return &(Info->getFunction().getEntryBlock());

279 }

280

281

283

287

291

293 return Info->getFunction().size();

294 }

295};

296

297template <>

299

301

303 return "BCI CFG for " + Info->getFunction().getName().str();

304 }

305

307 return Node->getName().str();

308 }

309

313 if (Info->isDependent(Src, Dest))

314 return "color=red";

315 if (Info->isDependent(Dest, Src))

316 return "color=blue";

317 return "";

318 }

319

321 std::string Result;

322 if (Info->isInstrumented(Node))

323 Result += "style=filled,fillcolor=gray";

324 if (Info->isCovered(Node))

325 Result += std::string(Result.empty() ? "" : ",") + "color=red";

326 return Result;

327 }

328};

329

330}

331

336 "Block Coverage Inference for " + F.getName());

337}

338

340 OS << "Minimal block coverage for function \'" << F.getName()

341 << "\' (Instrumented=*)\n";

342 for (auto &BB : F) {

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";

350 }

351 OS << " Instrumented Blocks Hash = 0x"

353}

354

355std::string

357 std::string Result;

359 OS << "[";

360 if (!BBs.empty()) {

361 OS << BBs.front()->getName();

363 }

364 for (auto *BB : BBs)

365 OS << ", " << BB->getName();

366 OS << "]";

367 return OS.str();

368}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

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))

std::unordered_set< BasicBlock * > BlockSet

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.

Definition BlockCoverageInference.cpp:339

uint64_t getInstrumentedBlocksHash() const

Definition BlockCoverageInference.cpp:77

bool shouldInstrumentBlock(const BasicBlock &BB) const

Definition BlockCoverageInference.cpp:91

void viewBlockCoverageGraph(const DenseMap< const BasicBlock *, bool > *Coverage=nullptr) const

View the inferred block coverage as a dot file.

Definition BlockCoverageInference.cpp:332

BlockCoverageInference(const Function &F, bool ForceInstrumentEntry)

Definition BlockCoverageInference.cpp:50

friend class DotFuncBCIInfo

BlockSet getDependencies(const BasicBlock &BB) const

Definition BlockCoverageInference.cpp:65

SmallSetVector< const BasicBlock *, 4 > BlockSet

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

bool isInstrumented(const BasicBlock *BB) const

Definition BlockCoverageInference.cpp:262

const Function & getFunction()

Definition BlockCoverageInference.cpp:260

bool isCovered(const BasicBlock *BB) const

Definition BlockCoverageInference.cpp:266

bool isDependent(const BasicBlock *Src, const BasicBlock *Dest) const

Definition BlockCoverageInference.cpp:270

DotFuncBCIInfo(const BlockCoverageInference *BCI, const DenseMap< const BasicBlock *, bool > *Coverage)

Definition BlockCoverageInference.cpp:256

LLVM_ABI void update(ArrayRef< uint8_t > Data)

bool set_union(const STy &S)

Compute This := This u S, return whether 'This' changed.

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(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.

LLVM_ABI 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)

FunctionAddr VTableAddr uintptr_t uintptr_t Data

FunctionAddr VTableAddr Next

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)

SuccIterator< const Instruction, const BasicBlock > const_succ_iterator

DOTGraphTraits(bool IsSimple=false)

Definition BlockCoverageInference.cpp:300

static std::string getGraphName(DotFuncBCIInfo *Info)

Definition BlockCoverageInference.cpp:302

std::string getNodeLabel(const BasicBlock *Node, DotFuncBCIInfo *Info)

Definition BlockCoverageInference.cpp:306

std::string getNodeAttributes(const BasicBlock *Node, DotFuncBCIInfo *Info)

Definition BlockCoverageInference.cpp:320

std::string getEdgeAttributes(const BasicBlock *Src, const_succ_iterator I, DotFuncBCIInfo *Info)

Definition BlockCoverageInference.cpp:310

DefaultDOTGraphTraits(bool simple=false)

static nodes_iterator nodes_end(DotFuncBCIInfo *Info)

Definition BlockCoverageInference.cpp:288

static NodeRef getEntryNode(DotFuncBCIInfo *Info)

Definition BlockCoverageInference.cpp:277

pointer_iterator< Function::const_iterator > nodes_iterator

Definition BlockCoverageInference.cpp:282

static nodes_iterator nodes_begin(DotFuncBCIInfo *Info)

Definition BlockCoverageInference.cpp:284

static size_t size(DotFuncBCIInfo *Info)

Definition BlockCoverageInference.cpp:292

typename DotFuncBCIInfo *::UnknownGraphTypeError NodeRef

std::pair< iterator, bool > insert(NodeRef N)