1 //=-- CoverageMapping.cpp - Code coverage mapping support ---------*- C++ -*-=// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains support for clang's and llvm's instrumentation based 11 // code coverage. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/ProfileData/CoverageMapping.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/Optional.h" 18 #include "llvm/ADT/SmallBitVector.h" 19 #include "llvm/ProfileData/CoverageMappingReader.h" 20 #include "llvm/ProfileData/InstrProfReader.h" 21 #include "llvm/Support/Debug.h" 22 #include "llvm/Support/ErrorHandling.h" 23 #include "llvm/Support/raw_ostream.h" 24 25 using namespace llvm; 26 using namespace coverage; 27 28 #define DEBUG_TYPE "coverage-mapping" 29 30 Counter CounterExpressionBuilder::get(const CounterExpression &E) { 31 auto It = ExpressionIndices.find(E); 32 if (It != ExpressionIndices.end()) 33 return Counter::getExpression(It->second); 34 unsigned I = Expressions.size(); 35 Expressions.push_back(E); 36 ExpressionIndices[E] = I; 37 return Counter::getExpression(I); 38 } 39 40 void CounterExpressionBuilder::extractTerms( 41 Counter C, int Sign, SmallVectorImpl<std::pair<unsigned, int>> &Terms) { 42 switch (C.getKind()) { 43 case Counter::Zero: 44 break; 45 case Counter::CounterValueReference: 46 Terms.push_back(std::make_pair(C.getCounterID(), Sign)); 47 break; 48 case Counter::Expression: 49 const auto &E = Expressions[C.getExpressionID()]; 50 extractTerms(E.LHS, Sign, Terms); 51 extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign, 52 Terms); 53 break; 54 } 55 } 56 57 Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) { 58 // Gather constant terms. 59 llvm::SmallVector<std::pair<unsigned, int>, 32> Terms; 60 extractTerms(ExpressionTree, +1, Terms); 61 62 // If there are no terms, this is just a zero. The algorithm below assumes at 63 // least one term. 64 if (Terms.size() == 0) 65 return Counter::getZero(); 66 67 // Group the terms by counter ID. 68 std::sort(Terms.begin(), Terms.end(), 69 [](const std::pair<unsigned, int> &LHS, 70 const std::pair<unsigned, int> &RHS) { 71 return LHS.first < RHS.first; 72 }); 73 74 // Combine terms by counter ID to eliminate counters that sum to zero. 75 auto Prev = Terms.begin(); 76 for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) { 77 if (I->first == Prev->first) { 78 Prev->second += I->second; 79 continue; 80 } 81 ++Prev; 82 *Prev = *I; 83 } 84 Terms.erase(++Prev, Terms.end()); 85 86 Counter C; 87 // Create additions. We do this before subtractions to avoid constructs like 88 // ((0 - X) + Y), as opposed to (Y - X). 89 for (auto Term : Terms) { 90 if (Term.second <= 0) 91 continue; 92 for (int I = 0; I < Term.second; ++I) 93 if (C.isZero()) 94 C = Counter::getCounter(Term.first); 95 else 96 C = get(CounterExpression(CounterExpression::Add, C, 97 Counter::getCounter(Term.first))); 98 } 99 100 // Create subtractions. 101 for (auto Term : Terms) { 102 if (Term.second >= 0) 103 continue; 104 for (int I = 0; I < -Term.second; ++I) 105 C = get(CounterExpression(CounterExpression::Subtract, C, 106 Counter::getCounter(Term.first))); 107 } 108 return C; 109 } 110 111 Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) { 112 return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS))); 113 } 114 115 Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) { 116 return simplify( 117 get(CounterExpression(CounterExpression::Subtract, LHS, RHS))); 118 } 119 120 void CounterMappingContext::dump(const Counter &C, 121 llvm::raw_ostream &OS) const { 122 switch (C.getKind()) { 123 case Counter::Zero: 124 OS << '0'; 125 return; 126 case Counter::CounterValueReference: 127 OS << '#' << C.getCounterID(); 128 break; 129 case Counter::Expression: { 130 if (C.getExpressionID() >= Expressions.size()) 131 return; 132 const auto &E = Expressions[C.getExpressionID()]; 133 OS << '('; 134 dump(E.LHS, OS); 135 OS << (E.Kind == CounterExpression::Subtract ? " - " : " + "); 136 dump(E.RHS, OS); 137 OS << ')'; 138 break; 139 } 140 } 141 if (CounterValues.empty()) 142 return; 143 ErrorOr<int64_t> Value = evaluate(C); 144 if (!Value) 145 return; 146 OS << '[' << *Value << ']'; 147 } 148 149 ErrorOr<int64_t> CounterMappingContext::evaluate(const Counter &C) const { 150 switch (C.getKind()) { 151 case Counter::Zero: 152 return 0; 153 case Counter::CounterValueReference: 154 if (C.getCounterID() >= CounterValues.size()) 155 return std::make_error_code(std::errc::argument_out_of_domain); 156 return CounterValues[C.getCounterID()]; 157 case Counter::Expression: { 158 if (C.getExpressionID() >= Expressions.size()) 159 return std::make_error_code(std::errc::argument_out_of_domain); 160 const auto &E = Expressions[C.getExpressionID()]; 161 ErrorOr<int64_t> LHS = evaluate(E.LHS); 162 if (!LHS) 163 return LHS; 164 ErrorOr<int64_t> RHS = evaluate(E.RHS); 165 if (!RHS) 166 return RHS; 167 return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS; 168 } 169 } 170 llvm_unreachable("Unhandled CounterKind"); 171 } 172 173 void FunctionRecordIterator::skipOtherFiles() { 174 while (Current != Records.end() && !Filename.empty() && 175 Filename != Current->Filenames[0]) 176 ++Current; 177 if (Current == Records.end()) 178 *this = FunctionRecordIterator(); 179 } 180 181 ErrorOr<std::unique_ptr<CoverageMapping>> 182 CoverageMapping::load(CoverageMappingReader &CoverageReader, 183 IndexedInstrProfReader &ProfileReader) { 184 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); 185 186 std::vector<uint64_t> Counts; 187 for (const auto &Record : CoverageReader) { 188 CounterMappingContext Ctx(Record.Expressions); 189 190 Counts.clear(); 191 if (std::error_code EC = ProfileReader.getFunctionCounts( 192 Record.FunctionName, Record.FunctionHash, Counts)) { 193 if (EC == instrprof_error::hash_mismatch) { 194 Coverage->MismatchedFunctionCount++; 195 continue; 196 } else if (EC != instrprof_error::unknown_function) 197 return EC; 198 } else 199 Ctx.setCounts(Counts); 200 201 assert(!Record.MappingRegions.empty() && "Function has no regions"); 202 FunctionRecord Function(Record.FunctionName, Record.Filenames); 203 for (const auto &Region : Record.MappingRegions) { 204 ErrorOr<int64_t> ExecutionCount = Ctx.evaluate(Region.Count); 205 if (!ExecutionCount) 206 break; 207 Function.pushRegion(Region, *ExecutionCount); 208 } 209 if (Function.CountedRegions.size() != Record.MappingRegions.size()) { 210 Coverage->MismatchedFunctionCount++; 211 continue; 212 } 213 214 Coverage->Functions.push_back(std::move(Function)); 215 } 216 217 return std::move(Coverage); 218 } 219 220 ErrorOr<std::unique_ptr<CoverageMapping>> 221 CoverageMapping::load(StringRef ObjectFilename, StringRef ProfileFilename, 222 Triple::ArchType Arch) { 223 auto CounterMappingBuff = MemoryBuffer::getFileOrSTDIN(ObjectFilename); 224 if (std::error_code EC = CounterMappingBuff.getError()) 225 return EC; 226 auto CoverageReaderOrErr = 227 BinaryCoverageReader::create(CounterMappingBuff.get(), Arch); 228 if (std::error_code EC = CoverageReaderOrErr.getError()) 229 return EC; 230 auto CoverageReader = std::move(CoverageReaderOrErr.get()); 231 auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename); 232 if (auto EC = ProfileReaderOrErr.getError()) 233 return EC; 234 auto ProfileReader = std::move(ProfileReaderOrErr.get()); 235 return load(*CoverageReader, *ProfileReader); 236 } 237 238 namespace { 239 /// \brief Distributes functions into instantiation sets. 240 /// 241 /// An instantiation set is a collection of functions that have the same source 242 /// code, ie, template functions specializations. 243 class FunctionInstantiationSetCollector { 244 typedef DenseMap<std::pair<unsigned, unsigned>, 245 std::vector<const FunctionRecord *>> MapT; 246 MapT InstantiatedFunctions; 247 248 public: 249 void insert(const FunctionRecord &Function, unsigned FileID) { 250 auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end(); 251 while (I != E && I->FileID != FileID) 252 ++I; 253 assert(I != E && "function does not cover the given file"); 254 auto &Functions = InstantiatedFunctions[I->startLoc()]; 255 Functions.push_back(&Function); 256 } 257 258 MapT::iterator begin() { return InstantiatedFunctions.begin(); } 259 260 MapT::iterator end() { return InstantiatedFunctions.end(); } 261 }; 262 263 class SegmentBuilder { 264 std::vector<CoverageSegment> Segments; 265 SmallVector<const CountedRegion *, 8> ActiveRegions; 266 267 /// Start a segment with no count specified. 268 void startSegment(unsigned Line, unsigned Col) { 269 DEBUG(dbgs() << "Top level segment at " << Line << ":" << Col << "\n"); 270 Segments.emplace_back(Line, Col, /*IsRegionEntry=*/false); 271 } 272 273 /// Start a segment with the given Region's count. 274 void startSegment(unsigned Line, unsigned Col, bool IsRegionEntry, 275 const CountedRegion &Region) { 276 if (Segments.empty()) 277 Segments.emplace_back(Line, Col, IsRegionEntry); 278 CoverageSegment S = Segments.back(); 279 // Avoid creating empty regions. 280 if (S.Line != Line || S.Col != Col) { 281 Segments.emplace_back(Line, Col, IsRegionEntry); 282 S = Segments.back(); 283 } 284 DEBUG(dbgs() << "Segment at " << Line << ":" << Col); 285 // Set this region's count. 286 if (Region.Kind != coverage::CounterMappingRegion::SkippedRegion) { 287 DEBUG(dbgs() << " with count " << Region.ExecutionCount); 288 Segments.back().setCount(Region.ExecutionCount); 289 } 290 DEBUG(dbgs() << "\n"); 291 } 292 293 /// Start a segment for the given region. 294 void startSegment(const CountedRegion &Region) { 295 startSegment(Region.LineStart, Region.ColumnStart, true, Region); 296 } 297 298 /// Pop the top region off of the active stack, starting a new segment with 299 /// the containing Region's count. 300 void popRegion() { 301 const CountedRegion *Active = ActiveRegions.back(); 302 unsigned Line = Active->LineEnd, Col = Active->ColumnEnd; 303 ActiveRegions.pop_back(); 304 if (ActiveRegions.empty()) 305 startSegment(Line, Col); 306 else 307 startSegment(Line, Col, false, *ActiveRegions.back()); 308 } 309 310 public: 311 /// Build a list of CoverageSegments from a sorted list of Regions. 312 std::vector<CoverageSegment> buildSegments(ArrayRef<CountedRegion> Regions) { 313 const CountedRegion *PrevRegion = nullptr; 314 for (const auto &Region : Regions) { 315 // Pop any regions that end before this one starts. 316 while (!ActiveRegions.empty() && 317 ActiveRegions.back()->endLoc() <= Region.startLoc()) 318 popRegion(); 319 if (PrevRegion && PrevRegion->startLoc() == Region.startLoc() && 320 PrevRegion->endLoc() == Region.endLoc()) { 321 if (Region.Kind == coverage::CounterMappingRegion::CodeRegion) 322 Segments.back().addCount(Region.ExecutionCount); 323 } else { 324 // Add this region to the stack. 325 ActiveRegions.push_back(&Region); 326 startSegment(Region); 327 } 328 PrevRegion = &Region; 329 } 330 // Pop any regions that are left in the stack. 331 while (!ActiveRegions.empty()) 332 popRegion(); 333 return Segments; 334 } 335 }; 336 } 337 338 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const { 339 std::vector<StringRef> Filenames; 340 for (const auto &Function : getCoveredFunctions()) 341 Filenames.insert(Filenames.end(), Function.Filenames.begin(), 342 Function.Filenames.end()); 343 std::sort(Filenames.begin(), Filenames.end()); 344 auto Last = std::unique(Filenames.begin(), Filenames.end()); 345 Filenames.erase(Last, Filenames.end()); 346 return Filenames; 347 } 348 349 static SmallBitVector gatherFileIDs(StringRef SourceFile, 350 const FunctionRecord &Function) { 351 SmallBitVector FilenameEquivalence(Function.Filenames.size(), false); 352 for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I) 353 if (SourceFile == Function.Filenames[I]) 354 FilenameEquivalence[I] = true; 355 return FilenameEquivalence; 356 } 357 358 static Optional<unsigned> findMainViewFileID(StringRef SourceFile, 359 const FunctionRecord &Function) { 360 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); 361 SmallBitVector FilenameEquivalence = gatherFileIDs(SourceFile, Function); 362 for (const auto &CR : Function.CountedRegions) 363 if (CR.Kind == CounterMappingRegion::ExpansionRegion && 364 FilenameEquivalence[CR.FileID]) 365 IsNotExpandedFile[CR.ExpandedFileID] = false; 366 IsNotExpandedFile &= FilenameEquivalence; 367 int I = IsNotExpandedFile.find_first(); 368 if (I == -1) 369 return None; 370 return I; 371 } 372 373 static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) { 374 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); 375 for (const auto &CR : Function.CountedRegions) 376 if (CR.Kind == CounterMappingRegion::ExpansionRegion) 377 IsNotExpandedFile[CR.ExpandedFileID] = false; 378 int I = IsNotExpandedFile.find_first(); 379 if (I == -1) 380 return None; 381 return I; 382 } 383 384 /// Sort a nested sequence of regions from a single file. 385 template <class It> static void sortNestedRegions(It First, It Last) { 386 std::sort(First, Last, 387 [](const CountedRegion &LHS, const CountedRegion &RHS) { 388 if (LHS.startLoc() == RHS.startLoc()) 389 // When LHS completely contains RHS, we sort LHS first. 390 return RHS.endLoc() < LHS.endLoc(); 391 return LHS.startLoc() < RHS.startLoc(); 392 }); 393 } 394 395 static bool isExpansion(const CountedRegion &R, unsigned FileID) { 396 return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID; 397 } 398 399 CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) { 400 CoverageData FileCoverage(Filename); 401 std::vector<coverage::CountedRegion> Regions; 402 403 for (const auto &Function : Functions) { 404 auto MainFileID = findMainViewFileID(Filename, Function); 405 if (!MainFileID) 406 continue; 407 auto FileIDs = gatherFileIDs(Filename, Function); 408 for (const auto &CR : Function.CountedRegions) 409 if (FileIDs.test(CR.FileID)) { 410 Regions.push_back(CR); 411 if (isExpansion(CR, *MainFileID)) 412 FileCoverage.Expansions.emplace_back(CR, Function); 413 } 414 } 415 416 sortNestedRegions(Regions.begin(), Regions.end()); 417 DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); 418 FileCoverage.Segments = SegmentBuilder().buildSegments(Regions); 419 420 return FileCoverage; 421 } 422 423 std::vector<const FunctionRecord *> 424 CoverageMapping::getInstantiations(StringRef Filename) { 425 FunctionInstantiationSetCollector InstantiationSetCollector; 426 for (const auto &Function : Functions) { 427 auto MainFileID = findMainViewFileID(Filename, Function); 428 if (!MainFileID) 429 continue; 430 InstantiationSetCollector.insert(Function, *MainFileID); 431 } 432 433 std::vector<const FunctionRecord *> Result; 434 for (const auto &InstantiationSet : InstantiationSetCollector) { 435 if (InstantiationSet.second.size() < 2) 436 continue; 437 Result.insert(Result.end(), InstantiationSet.second.begin(), 438 InstantiationSet.second.end()); 439 } 440 return Result; 441 } 442 443 CoverageData 444 CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) { 445 auto MainFileID = findMainViewFileID(Function); 446 if (!MainFileID) 447 return CoverageData(); 448 449 CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); 450 std::vector<coverage::CountedRegion> Regions; 451 for (const auto &CR : Function.CountedRegions) 452 if (CR.FileID == *MainFileID) { 453 Regions.push_back(CR); 454 if (isExpansion(CR, *MainFileID)) 455 FunctionCoverage.Expansions.emplace_back(CR, Function); 456 } 457 458 sortNestedRegions(Regions.begin(), Regions.end()); 459 DEBUG(dbgs() << "Emitting segments for function: " << Function.Name << "\n"); 460 FunctionCoverage.Segments = SegmentBuilder().buildSegments(Regions); 461 462 return FunctionCoverage; 463 } 464 465 CoverageData 466 CoverageMapping::getCoverageForExpansion(const ExpansionRecord &Expansion) { 467 CoverageData ExpansionCoverage( 468 Expansion.Function.Filenames[Expansion.FileID]); 469 std::vector<coverage::CountedRegion> Regions; 470 for (const auto &CR : Expansion.Function.CountedRegions) 471 if (CR.FileID == Expansion.FileID) { 472 Regions.push_back(CR); 473 if (isExpansion(CR, Expansion.FileID)) 474 ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function); 475 } 476 477 sortNestedRegions(Regions.begin(), Regions.end()); 478 DEBUG(dbgs() << "Emitting segments for expansion of file " << Expansion.FileID 479 << "\n"); 480 ExpansionCoverage.Segments = SegmentBuilder().buildSegments(Regions); 481 482 return ExpansionCoverage; 483 } 484