1 //===- CoverageMapping.cpp - Code coverage mapping support ----------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains support for clang's and llvm's instrumentation based 10 // code coverage. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/ProfileData/Coverage/CoverageMapping.h" 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/SmallBitVector.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/StringExtras.h" 21 #include "llvm/ADT/StringRef.h" 22 #include "llvm/Object/BuildID.h" 23 #include "llvm/ProfileData/Coverage/CoverageMappingReader.h" 24 #include "llvm/ProfileData/InstrProfReader.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/Errc.h" 27 #include "llvm/Support/Error.h" 28 #include "llvm/Support/ErrorHandling.h" 29 #include "llvm/Support/MemoryBuffer.h" 30 #include "llvm/Support/VirtualFileSystem.h" 31 #include "llvm/Support/raw_ostream.h" 32 #include <algorithm> 33 #include <cassert> 34 #include <cmath> 35 #include <cstdint> 36 #include <iterator> 37 #include <map> 38 #include <memory> 39 #include <optional> 40 #include <string> 41 #include <system_error> 42 #include <utility> 43 #include <vector> 44 45 using namespace llvm; 46 using namespace coverage; 47 48 #define DEBUG_TYPE "coverage-mapping" 49 50 Counter CounterExpressionBuilder::get(const CounterExpression &E) { 51 auto It = ExpressionIndices.find(E); 52 if (It != ExpressionIndices.end()) 53 return Counter::getExpression(It->second); 54 unsigned I = Expressions.size(); 55 Expressions.push_back(E); 56 ExpressionIndices[E] = I; 57 return Counter::getExpression(I); 58 } 59 60 void CounterExpressionBuilder::extractTerms(Counter C, int Factor, 61 SmallVectorImpl<Term> &Terms) { 62 switch (C.getKind()) { 63 case Counter::Zero: 64 break; 65 case Counter::CounterValueReference: 66 Terms.emplace_back(C.getCounterID(), Factor); 67 break; 68 case Counter::Expression: 69 const auto &E = Expressions[C.getExpressionID()]; 70 extractTerms(E.LHS, Factor, Terms); 71 extractTerms( 72 E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms); 73 break; 74 } 75 } 76 77 Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) { 78 // Gather constant terms. 79 SmallVector<Term, 32> Terms; 80 extractTerms(ExpressionTree, +1, Terms); 81 82 // If there are no terms, this is just a zero. The algorithm below assumes at 83 // least one term. 84 if (Terms.size() == 0) 85 return Counter::getZero(); 86 87 // Group the terms by counter ID. 88 llvm::sort(Terms, [](const Term &LHS, const Term &RHS) { 89 return LHS.CounterID < RHS.CounterID; 90 }); 91 92 // Combine terms by counter ID to eliminate counters that sum to zero. 93 auto Prev = Terms.begin(); 94 for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) { 95 if (I->CounterID == Prev->CounterID) { 96 Prev->Factor += I->Factor; 97 continue; 98 } 99 ++Prev; 100 *Prev = *I; 101 } 102 Terms.erase(++Prev, Terms.end()); 103 104 Counter C; 105 // Create additions. We do this before subtractions to avoid constructs like 106 // ((0 - X) + Y), as opposed to (Y - X). 107 for (auto T : Terms) { 108 if (T.Factor <= 0) 109 continue; 110 for (int I = 0; I < T.Factor; ++I) 111 if (C.isZero()) 112 C = Counter::getCounter(T.CounterID); 113 else 114 C = get(CounterExpression(CounterExpression::Add, C, 115 Counter::getCounter(T.CounterID))); 116 } 117 118 // Create subtractions. 119 for (auto T : Terms) { 120 if (T.Factor >= 0) 121 continue; 122 for (int I = 0; I < -T.Factor; ++I) 123 C = get(CounterExpression(CounterExpression::Subtract, C, 124 Counter::getCounter(T.CounterID))); 125 } 126 return C; 127 } 128 129 Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS, bool Simplify) { 130 auto Cnt = get(CounterExpression(CounterExpression::Add, LHS, RHS)); 131 return Simplify ? simplify(Cnt) : Cnt; 132 } 133 134 Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS, 135 bool Simplify) { 136 auto Cnt = get(CounterExpression(CounterExpression::Subtract, LHS, RHS)); 137 return Simplify ? simplify(Cnt) : Cnt; 138 } 139 140 void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const { 141 switch (C.getKind()) { 142 case Counter::Zero: 143 OS << '0'; 144 return; 145 case Counter::CounterValueReference: 146 OS << '#' << C.getCounterID(); 147 break; 148 case Counter::Expression: { 149 if (C.getExpressionID() >= Expressions.size()) 150 return; 151 const auto &E = Expressions[C.getExpressionID()]; 152 OS << '('; 153 dump(E.LHS, OS); 154 OS << (E.Kind == CounterExpression::Subtract ? " - " : " + "); 155 dump(E.RHS, OS); 156 OS << ')'; 157 break; 158 } 159 } 160 if (CounterValues.empty()) 161 return; 162 Expected<int64_t> Value = evaluate(C); 163 if (auto E = Value.takeError()) { 164 consumeError(std::move(E)); 165 return; 166 } 167 OS << '[' << *Value << ']'; 168 } 169 170 Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { 171 struct StackElem { 172 Counter ICounter; 173 int64_t LHS = 0; 174 enum { 175 KNeverVisited = 0, 176 KVisitedOnce = 1, 177 KVisitedTwice = 2, 178 } VisitCount = KNeverVisited; 179 }; 180 181 std::stack<StackElem> CounterStack; 182 CounterStack.push({C}); 183 184 int64_t LastPoppedValue; 185 186 while (!CounterStack.empty()) { 187 StackElem &Current = CounterStack.top(); 188 189 switch (Current.ICounter.getKind()) { 190 case Counter::Zero: 191 LastPoppedValue = 0; 192 CounterStack.pop(); 193 break; 194 case Counter::CounterValueReference: 195 if (Current.ICounter.getCounterID() >= CounterValues.size()) 196 return errorCodeToError(errc::argument_out_of_domain); 197 LastPoppedValue = CounterValues[Current.ICounter.getCounterID()]; 198 CounterStack.pop(); 199 break; 200 case Counter::Expression: { 201 if (Current.ICounter.getExpressionID() >= Expressions.size()) 202 return errorCodeToError(errc::argument_out_of_domain); 203 const auto &E = Expressions[Current.ICounter.getExpressionID()]; 204 if (Current.VisitCount == StackElem::KNeverVisited) { 205 CounterStack.push(StackElem{E.LHS}); 206 Current.VisitCount = StackElem::KVisitedOnce; 207 } else if (Current.VisitCount == StackElem::KVisitedOnce) { 208 Current.LHS = LastPoppedValue; 209 CounterStack.push(StackElem{E.RHS}); 210 Current.VisitCount = StackElem::KVisitedTwice; 211 } else { 212 int64_t LHS = Current.LHS; 213 int64_t RHS = LastPoppedValue; 214 LastPoppedValue = 215 E.Kind == CounterExpression::Subtract ? LHS - RHS : LHS + RHS; 216 CounterStack.pop(); 217 } 218 break; 219 } 220 } 221 } 222 223 return LastPoppedValue; 224 } 225 226 mcdc::TVIdxBuilder::TVIdxBuilder(const SmallVectorImpl<ConditionIDs> &NextIDs, 227 int Offset) 228 : Indices(NextIDs.size()) { 229 // Construct Nodes and set up each InCount 230 auto N = NextIDs.size(); 231 SmallVector<MCDCNode> Nodes(N); 232 for (unsigned ID = 0; ID < N; ++ID) { 233 for (unsigned C = 0; C < 2; ++C) { 234 #ifndef NDEBUG 235 Indices[ID][C] = INT_MIN; 236 #endif 237 auto NextID = NextIDs[ID][C]; 238 Nodes[ID].NextIDs[C] = NextID; 239 if (NextID >= 0) 240 ++Nodes[NextID].InCount; 241 } 242 } 243 244 // Sort key ordered by <-Width, Ord> 245 SmallVector<std::tuple<int, /// -Width 246 unsigned, /// Ord 247 int, /// ID 248 unsigned /// Cond (0 or 1) 249 >> 250 Decisions; 251 252 // Traverse Nodes to assign Idx 253 SmallVector<int> Q; 254 assert(Nodes[0].InCount == 0); 255 Nodes[0].Width = 1; 256 Q.push_back(0); 257 258 unsigned Ord = 0; 259 while (!Q.empty()) { 260 auto IID = Q.begin(); 261 int ID = *IID; 262 Q.erase(IID); 263 auto &Node = Nodes[ID]; 264 assert(Node.Width > 0); 265 266 for (unsigned I = 0; I < 2; ++I) { 267 auto NextID = Node.NextIDs[I]; 268 assert(NextID != 0 && "NextID should not point to the top"); 269 if (NextID < 0) { 270 // Decision 271 Decisions.emplace_back(-Node.Width, Ord++, ID, I); 272 assert(Ord == Decisions.size()); 273 continue; 274 } 275 276 // Inter Node 277 auto &NextNode = Nodes[NextID]; 278 assert(NextNode.InCount > 0); 279 280 // Assign Idx 281 assert(Indices[ID][I] == INT_MIN); 282 Indices[ID][I] = NextNode.Width; 283 auto NextWidth = int64_t(NextNode.Width) + Node.Width; 284 if (NextWidth > HardMaxTVs) { 285 NumTestVectors = HardMaxTVs; // Overflow 286 return; 287 } 288 NextNode.Width = NextWidth; 289 290 // Ready if all incomings are processed. 291 // Or NextNode.Width hasn't been confirmed yet. 292 if (--NextNode.InCount == 0) 293 Q.push_back(NextID); 294 } 295 } 296 297 llvm::sort(Decisions); 298 299 // Assign TestVector Indices in Decision Nodes 300 int64_t CurIdx = 0; 301 for (auto [NegWidth, Ord, ID, C] : Decisions) { 302 int Width = -NegWidth; 303 assert(Nodes[ID].Width == Width); 304 assert(Nodes[ID].NextIDs[C] < 0); 305 assert(Indices[ID][C] == INT_MIN); 306 Indices[ID][C] = Offset + CurIdx; 307 CurIdx += Width; 308 if (CurIdx > HardMaxTVs) { 309 NumTestVectors = HardMaxTVs; // Overflow 310 return; 311 } 312 } 313 314 assert(CurIdx < HardMaxTVs); 315 NumTestVectors = CurIdx; 316 317 #ifndef NDEBUG 318 for (const auto &Idxs : Indices) 319 for (auto Idx : Idxs) 320 assert(Idx != INT_MIN); 321 SavedNodes = std::move(Nodes); 322 #endif 323 } 324 325 namespace { 326 327 /// Construct this->NextIDs with Branches for TVIdxBuilder to use it 328 /// before MCDCRecordProcessor(). 329 class NextIDsBuilder { 330 protected: 331 SmallVector<mcdc::ConditionIDs> NextIDs; 332 333 public: 334 NextIDsBuilder(const ArrayRef<const CounterMappingRegion *> Branches) 335 : NextIDs(Branches.size()) { 336 #ifndef NDEBUG 337 DenseSet<mcdc::ConditionID> SeenIDs; 338 #endif 339 for (const auto *Branch : Branches) { 340 const auto &BranchParams = Branch->getBranchParams(); 341 assert(SeenIDs.insert(BranchParams.ID).second && "Duplicate CondID"); 342 NextIDs[BranchParams.ID] = BranchParams.Conds; 343 } 344 assert(SeenIDs.size() == Branches.size()); 345 } 346 }; 347 348 class MCDCRecordProcessor : NextIDsBuilder, mcdc::TVIdxBuilder { 349 /// A bitmap representing the executed test vectors for a boolean expression. 350 /// Each index of the bitmap corresponds to a possible test vector. An index 351 /// with a bit value of '1' indicates that the corresponding Test Vector 352 /// identified by that index was executed. 353 const BitVector &Bitmap; 354 355 /// Decision Region to which the ExecutedTestVectorBitmap applies. 356 const CounterMappingRegion &Region; 357 const mcdc::DecisionParameters &DecisionParams; 358 359 /// Array of branch regions corresponding each conditions in the boolean 360 /// expression. 361 ArrayRef<const CounterMappingRegion *> Branches; 362 363 /// Total number of conditions in the boolean expression. 364 unsigned NumConditions; 365 366 /// Vector used to track whether a condition is constant folded. 367 MCDCRecord::BoolVector Folded; 368 369 /// Mapping of calculated MC/DC Independence Pairs for each condition. 370 MCDCRecord::TVPairMap IndependencePairs; 371 372 /// Storage for ExecVectors 373 /// ExecVectors is the alias of its 0th element. 374 std::array<MCDCRecord::TestVectors, 2> ExecVectorsByCond; 375 376 /// Actual executed Test Vectors for the boolean expression, based on 377 /// ExecutedTestVectorBitmap. 378 MCDCRecord::TestVectors &ExecVectors; 379 380 /// Number of False items in ExecVectors 381 unsigned NumExecVectorsF; 382 383 #ifndef NDEBUG 384 DenseSet<unsigned> TVIdxs; 385 #endif 386 387 bool IsVersion11; 388 389 public: 390 MCDCRecordProcessor(const BitVector &Bitmap, 391 const CounterMappingRegion &Region, 392 ArrayRef<const CounterMappingRegion *> Branches, 393 bool IsVersion11) 394 : NextIDsBuilder(Branches), TVIdxBuilder(this->NextIDs), Bitmap(Bitmap), 395 Region(Region), DecisionParams(Region.getDecisionParams()), 396 Branches(Branches), NumConditions(DecisionParams.NumConditions), 397 Folded(NumConditions, false), IndependencePairs(NumConditions), 398 ExecVectors(ExecVectorsByCond[false]), IsVersion11(IsVersion11) {} 399 400 private: 401 // Walk the binary decision diagram and try assigning both false and true to 402 // each node. When a terminal node (ID == 0) is reached, fill in the value in 403 // the truth table. 404 void buildTestVector(MCDCRecord::TestVector &TV, mcdc::ConditionID ID, 405 int TVIdx) { 406 for (auto MCDCCond : {MCDCRecord::MCDC_False, MCDCRecord::MCDC_True}) { 407 static_assert(MCDCRecord::MCDC_False == 0); 408 static_assert(MCDCRecord::MCDC_True == 1); 409 TV.set(ID, MCDCCond); 410 auto NextID = NextIDs[ID][MCDCCond]; 411 auto NextTVIdx = TVIdx + Indices[ID][MCDCCond]; 412 assert(NextID == SavedNodes[ID].NextIDs[MCDCCond]); 413 if (NextID >= 0) { 414 buildTestVector(TV, NextID, NextTVIdx); 415 continue; 416 } 417 418 assert(TVIdx < SavedNodes[ID].Width); 419 assert(TVIdxs.insert(NextTVIdx).second && "Duplicate TVIdx"); 420 421 if (!Bitmap[IsVersion11 422 ? DecisionParams.BitmapIdx * CHAR_BIT + TV.getIndex() 423 : DecisionParams.BitmapIdx - NumTestVectors + NextTVIdx]) 424 continue; 425 426 // Copy the completed test vector to the vector of testvectors. 427 // The final value (T,F) is equal to the last non-dontcare state on the 428 // path (in a short-circuiting system). 429 ExecVectorsByCond[MCDCCond].push_back({TV, MCDCCond}); 430 } 431 432 // Reset back to DontCare. 433 TV.set(ID, MCDCRecord::MCDC_DontCare); 434 } 435 436 /// Walk the bits in the bitmap. A bit set to '1' indicates that the test 437 /// vector at the corresponding index was executed during a test run. 438 void findExecutedTestVectors() { 439 // Walk the binary decision diagram to enumerate all possible test vectors. 440 // We start at the root node (ID == 0) with all values being DontCare. 441 // `TVIdx` starts with 0 and is in the traversal. 442 // `Index` encodes the bitmask of true values and is initially 0. 443 MCDCRecord::TestVector TV(NumConditions); 444 buildTestVector(TV, 0, 0); 445 assert(TVIdxs.size() == unsigned(NumTestVectors) && 446 "TVIdxs wasn't fulfilled"); 447 448 // Fill ExecVectors order by False items and True items. 449 // ExecVectors is the alias of ExecVectorsByCond[false], so 450 // Append ExecVectorsByCond[true] on it. 451 NumExecVectorsF = ExecVectors.size(); 452 auto &ExecVectorsT = ExecVectorsByCond[true]; 453 ExecVectors.append(std::make_move_iterator(ExecVectorsT.begin()), 454 std::make_move_iterator(ExecVectorsT.end())); 455 } 456 457 // Find an independence pair for each condition: 458 // - The condition is true in one test and false in the other. 459 // - The decision outcome is true one test and false in the other. 460 // - All other conditions' values must be equal or marked as "don't care". 461 void findIndependencePairs() { 462 unsigned NumTVs = ExecVectors.size(); 463 for (unsigned I = NumExecVectorsF; I < NumTVs; ++I) { 464 const auto &[A, ACond] = ExecVectors[I]; 465 assert(ACond == MCDCRecord::MCDC_True); 466 for (unsigned J = 0; J < NumExecVectorsF; ++J) { 467 const auto &[B, BCond] = ExecVectors[J]; 468 assert(BCond == MCDCRecord::MCDC_False); 469 // If the two vectors differ in exactly one condition, ignoring DontCare 470 // conditions, we have found an independence pair. 471 auto AB = A.getDifferences(B); 472 if (AB.count() == 1) 473 IndependencePairs.insert( 474 {AB.find_first(), std::make_pair(J + 1, I + 1)}); 475 } 476 } 477 } 478 479 public: 480 /// Process the MC/DC Record in order to produce a result for a boolean 481 /// expression. This process includes tracking the conditions that comprise 482 /// the decision region, calculating the list of all possible test vectors, 483 /// marking the executed test vectors, and then finding an Independence Pair 484 /// out of the executed test vectors for each condition in the boolean 485 /// expression. A condition is tracked to ensure that its ID can be mapped to 486 /// its ordinal position in the boolean expression. The condition's source 487 /// location is also tracked, as well as whether it is constant folded (in 488 /// which case it is excuded from the metric). 489 MCDCRecord processMCDCRecord() { 490 unsigned I = 0; 491 MCDCRecord::CondIDMap PosToID; 492 MCDCRecord::LineColPairMap CondLoc; 493 494 // Walk the Record's BranchRegions (representing Conditions) in order to: 495 // - Hash the condition based on its corresponding ID. This will be used to 496 // calculate the test vectors. 497 // - Keep a map of the condition's ordinal position (1, 2, 3, 4) to its 498 // actual ID. This will be used to visualize the conditions in the 499 // correct order. 500 // - Keep track of the condition source location. This will be used to 501 // visualize where the condition is. 502 // - Record whether the condition is constant folded so that we exclude it 503 // from being measured. 504 for (const auto *B : Branches) { 505 const auto &BranchParams = B->getBranchParams(); 506 PosToID[I] = BranchParams.ID; 507 CondLoc[I] = B->startLoc(); 508 Folded[I++] = (B->Count.isZero() && B->FalseCount.isZero()); 509 } 510 511 // Using Profile Bitmap from runtime, mark the executed test vectors. 512 findExecutedTestVectors(); 513 514 // Compare executed test vectors against each other to find an independence 515 // pairs for each condition. This processing takes the most time. 516 findIndependencePairs(); 517 518 // Record Test vectors, executed vectors, and independence pairs. 519 return MCDCRecord(Region, std::move(ExecVectors), 520 std::move(IndependencePairs), std::move(Folded), 521 std::move(PosToID), std::move(CondLoc)); 522 } 523 }; 524 525 } // namespace 526 527 Expected<MCDCRecord> CounterMappingContext::evaluateMCDCRegion( 528 const CounterMappingRegion &Region, 529 ArrayRef<const CounterMappingRegion *> Branches, bool IsVersion11) { 530 531 MCDCRecordProcessor MCDCProcessor(Bitmap, Region, Branches, IsVersion11); 532 return MCDCProcessor.processMCDCRecord(); 533 } 534 535 unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const { 536 struct StackElem { 537 Counter ICounter; 538 int64_t LHS = 0; 539 enum { 540 KNeverVisited = 0, 541 KVisitedOnce = 1, 542 KVisitedTwice = 2, 543 } VisitCount = KNeverVisited; 544 }; 545 546 std::stack<StackElem> CounterStack; 547 CounterStack.push({C}); 548 549 int64_t LastPoppedValue; 550 551 while (!CounterStack.empty()) { 552 StackElem &Current = CounterStack.top(); 553 554 switch (Current.ICounter.getKind()) { 555 case Counter::Zero: 556 LastPoppedValue = 0; 557 CounterStack.pop(); 558 break; 559 case Counter::CounterValueReference: 560 LastPoppedValue = Current.ICounter.getCounterID(); 561 CounterStack.pop(); 562 break; 563 case Counter::Expression: { 564 if (Current.ICounter.getExpressionID() >= Expressions.size()) { 565 LastPoppedValue = 0; 566 CounterStack.pop(); 567 } else { 568 const auto &E = Expressions[Current.ICounter.getExpressionID()]; 569 if (Current.VisitCount == StackElem::KNeverVisited) { 570 CounterStack.push(StackElem{E.LHS}); 571 Current.VisitCount = StackElem::KVisitedOnce; 572 } else if (Current.VisitCount == StackElem::KVisitedOnce) { 573 Current.LHS = LastPoppedValue; 574 CounterStack.push(StackElem{E.RHS}); 575 Current.VisitCount = StackElem::KVisitedTwice; 576 } else { 577 int64_t LHS = Current.LHS; 578 int64_t RHS = LastPoppedValue; 579 LastPoppedValue = std::max(LHS, RHS); 580 CounterStack.pop(); 581 } 582 } 583 break; 584 } 585 } 586 } 587 588 return LastPoppedValue; 589 } 590 591 void FunctionRecordIterator::skipOtherFiles() { 592 while (Current != Records.end() && !Filename.empty() && 593 Filename != Current->Filenames[0]) 594 ++Current; 595 if (Current == Records.end()) 596 *this = FunctionRecordIterator(); 597 } 598 599 ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename( 600 StringRef Filename) const { 601 size_t FilenameHash = hash_value(Filename); 602 auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash); 603 if (RecordIt == FilenameHash2RecordIndices.end()) 604 return {}; 605 return RecordIt->second; 606 } 607 608 static unsigned getMaxCounterID(const CounterMappingContext &Ctx, 609 const CoverageMappingRecord &Record) { 610 unsigned MaxCounterID = 0; 611 for (const auto &Region : Record.MappingRegions) { 612 MaxCounterID = std::max(MaxCounterID, Ctx.getMaxCounterID(Region.Count)); 613 } 614 return MaxCounterID; 615 } 616 617 /// Returns the bit count 618 static unsigned getMaxBitmapSize(const CoverageMappingRecord &Record, 619 bool IsVersion11) { 620 unsigned MaxBitmapIdx = 0; 621 unsigned NumConditions = 0; 622 // Scan max(BitmapIdx). 623 // Note that `<=` is used insted of `<`, because `BitmapIdx == 0` is valid 624 // and `MaxBitmapIdx is `unsigned`. `BitmapIdx` is unique in the record. 625 for (const auto &Region : reverse(Record.MappingRegions)) { 626 if (Region.Kind != CounterMappingRegion::MCDCDecisionRegion) 627 continue; 628 const auto &DecisionParams = Region.getDecisionParams(); 629 if (MaxBitmapIdx <= DecisionParams.BitmapIdx) { 630 MaxBitmapIdx = DecisionParams.BitmapIdx; 631 NumConditions = DecisionParams.NumConditions; 632 } 633 } 634 635 if (IsVersion11) 636 MaxBitmapIdx = MaxBitmapIdx * CHAR_BIT + 637 llvm::alignTo(uint64_t(1) << NumConditions, CHAR_BIT); 638 639 return MaxBitmapIdx; 640 } 641 642 namespace { 643 644 /// Collect Decisions, Branchs, and Expansions and associate them. 645 class MCDCDecisionRecorder { 646 private: 647 /// This holds the DecisionRegion and MCDCBranches under it. 648 /// Also traverses Expansion(s). 649 /// The Decision has the number of MCDCBranches and will complete 650 /// when it is filled with unique ConditionID of MCDCBranches. 651 struct DecisionRecord { 652 const CounterMappingRegion *DecisionRegion; 653 654 /// They are reflected from DecisionRegion for convenience. 655 mcdc::DecisionParameters DecisionParams; 656 LineColPair DecisionStartLoc; 657 LineColPair DecisionEndLoc; 658 659 /// This is passed to `MCDCRecordProcessor`, so this should be compatible 660 /// to`ArrayRef<const CounterMappingRegion *>`. 661 SmallVector<const CounterMappingRegion *> MCDCBranches; 662 663 /// IDs that are stored in MCDCBranches 664 /// Complete when all IDs (1 to NumConditions) are met. 665 DenseSet<mcdc::ConditionID> ConditionIDs; 666 667 /// Set of IDs of Expansion(s) that are relevant to DecisionRegion 668 /// and its children (via expansions). 669 /// FileID pointed by ExpandedFileID is dedicated to the expansion, so 670 /// the location in the expansion doesn't matter. 671 DenseSet<unsigned> ExpandedFileIDs; 672 673 DecisionRecord(const CounterMappingRegion &Decision) 674 : DecisionRegion(&Decision), 675 DecisionParams(Decision.getDecisionParams()), 676 DecisionStartLoc(Decision.startLoc()), 677 DecisionEndLoc(Decision.endLoc()) { 678 assert(Decision.Kind == CounterMappingRegion::MCDCDecisionRegion); 679 } 680 681 /// Determine whether DecisionRecord dominates `R`. 682 bool dominates(const CounterMappingRegion &R) const { 683 // Determine whether `R` is included in `DecisionRegion`. 684 if (R.FileID == DecisionRegion->FileID && 685 R.startLoc() >= DecisionStartLoc && R.endLoc() <= DecisionEndLoc) 686 return true; 687 688 // Determine whether `R` is pointed by any of Expansions. 689 return ExpandedFileIDs.contains(R.FileID); 690 } 691 692 enum Result { 693 NotProcessed = 0, /// Irrelevant to this Decision 694 Processed, /// Added to this Decision 695 Completed, /// Added and filled this Decision 696 }; 697 698 /// Add Branch into the Decision 699 /// \param Branch expects MCDCBranchRegion 700 /// \returns NotProcessed/Processed/Completed 701 Result addBranch(const CounterMappingRegion &Branch) { 702 assert(Branch.Kind == CounterMappingRegion::MCDCBranchRegion); 703 704 auto ConditionID = Branch.getBranchParams().ID; 705 706 if (ConditionIDs.contains(ConditionID) || 707 ConditionID >= DecisionParams.NumConditions) 708 return NotProcessed; 709 710 if (!this->dominates(Branch)) 711 return NotProcessed; 712 713 assert(MCDCBranches.size() < DecisionParams.NumConditions); 714 715 // Put `ID=0` in front of `MCDCBranches` for convenience 716 // even if `MCDCBranches` is not topological. 717 if (ConditionID == 0) 718 MCDCBranches.insert(MCDCBranches.begin(), &Branch); 719 else 720 MCDCBranches.push_back(&Branch); 721 722 // Mark `ID` as `assigned`. 723 ConditionIDs.insert(ConditionID); 724 725 // `Completed` when `MCDCBranches` is full 726 return (MCDCBranches.size() == DecisionParams.NumConditions ? Completed 727 : Processed); 728 } 729 730 /// Record Expansion if it is relevant to this Decision. 731 /// Each `Expansion` may nest. 732 /// \returns true if recorded. 733 bool recordExpansion(const CounterMappingRegion &Expansion) { 734 if (!this->dominates(Expansion)) 735 return false; 736 737 ExpandedFileIDs.insert(Expansion.ExpandedFileID); 738 return true; 739 } 740 }; 741 742 private: 743 /// Decisions in progress 744 /// DecisionRecord is added for each MCDCDecisionRegion. 745 /// DecisionRecord is removed when Decision is completed. 746 SmallVector<DecisionRecord> Decisions; 747 748 public: 749 ~MCDCDecisionRecorder() { 750 assert(Decisions.empty() && "All Decisions have not been resolved"); 751 } 752 753 /// Register Region and start recording. 754 void registerDecision(const CounterMappingRegion &Decision) { 755 Decisions.emplace_back(Decision); 756 } 757 758 void recordExpansion(const CounterMappingRegion &Expansion) { 759 any_of(Decisions, [&Expansion](auto &Decision) { 760 return Decision.recordExpansion(Expansion); 761 }); 762 } 763 764 using DecisionAndBranches = 765 std::pair<const CounterMappingRegion *, /// Decision 766 SmallVector<const CounterMappingRegion *> /// Branches 767 >; 768 769 /// Add MCDCBranchRegion to DecisionRecord. 770 /// \param Branch to be processed 771 /// \returns DecisionsAndBranches if DecisionRecord completed. 772 /// Or returns nullopt. 773 std::optional<DecisionAndBranches> 774 processBranch(const CounterMappingRegion &Branch) { 775 // Seek each Decision and apply Region to it. 776 for (auto DecisionIter = Decisions.begin(), DecisionEnd = Decisions.end(); 777 DecisionIter != DecisionEnd; ++DecisionIter) 778 switch (DecisionIter->addBranch(Branch)) { 779 case DecisionRecord::NotProcessed: 780 continue; 781 case DecisionRecord::Processed: 782 return std::nullopt; 783 case DecisionRecord::Completed: 784 DecisionAndBranches Result = 785 std::make_pair(DecisionIter->DecisionRegion, 786 std::move(DecisionIter->MCDCBranches)); 787 Decisions.erase(DecisionIter); // No longer used. 788 return Result; 789 } 790 791 llvm_unreachable("Branch not found in Decisions"); 792 } 793 }; 794 795 } // namespace 796 797 Error CoverageMapping::loadFunctionRecord( 798 const CoverageMappingRecord &Record, 799 IndexedInstrProfReader &ProfileReader) { 800 StringRef OrigFuncName = Record.FunctionName; 801 if (OrigFuncName.empty()) 802 return make_error<CoverageMapError>(coveragemap_error::malformed, 803 "record function name is empty"); 804 805 if (Record.Filenames.empty()) 806 OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName); 807 else 808 OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]); 809 810 CounterMappingContext Ctx(Record.Expressions); 811 812 std::vector<uint64_t> Counts; 813 if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName, 814 Record.FunctionHash, Counts)) { 815 instrprof_error IPE = std::get<0>(InstrProfError::take(std::move(E))); 816 if (IPE == instrprof_error::hash_mismatch) { 817 FuncHashMismatches.emplace_back(std::string(Record.FunctionName), 818 Record.FunctionHash); 819 return Error::success(); 820 } 821 if (IPE != instrprof_error::unknown_function) 822 return make_error<InstrProfError>(IPE); 823 Counts.assign(getMaxCounterID(Ctx, Record) + 1, 0); 824 } 825 Ctx.setCounts(Counts); 826 827 bool IsVersion11 = 828 ProfileReader.getVersion() < IndexedInstrProf::ProfVersion::Version12; 829 830 BitVector Bitmap; 831 if (Error E = ProfileReader.getFunctionBitmap(Record.FunctionName, 832 Record.FunctionHash, Bitmap)) { 833 instrprof_error IPE = std::get<0>(InstrProfError::take(std::move(E))); 834 if (IPE == instrprof_error::hash_mismatch) { 835 FuncHashMismatches.emplace_back(std::string(Record.FunctionName), 836 Record.FunctionHash); 837 return Error::success(); 838 } 839 if (IPE != instrprof_error::unknown_function) 840 return make_error<InstrProfError>(IPE); 841 Bitmap = BitVector(getMaxBitmapSize(Record, IsVersion11)); 842 } 843 Ctx.setBitmap(std::move(Bitmap)); 844 845 assert(!Record.MappingRegions.empty() && "Function has no regions"); 846 847 // This coverage record is a zero region for a function that's unused in 848 // some TU, but used in a different TU. Ignore it. The coverage maps from the 849 // the other TU will either be loaded (providing full region counts) or they 850 // won't (in which case we don't unintuitively report functions as uncovered 851 // when they have non-zero counts in the profile). 852 if (Record.MappingRegions.size() == 1 && 853 Record.MappingRegions[0].Count.isZero() && Counts[0] > 0) 854 return Error::success(); 855 856 MCDCDecisionRecorder MCDCDecisions; 857 FunctionRecord Function(OrigFuncName, Record.Filenames); 858 for (const auto &Region : Record.MappingRegions) { 859 // MCDCDecisionRegion should be handled first since it overlaps with 860 // others inside. 861 if (Region.Kind == CounterMappingRegion::MCDCDecisionRegion) { 862 MCDCDecisions.registerDecision(Region); 863 continue; 864 } 865 Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count); 866 if (auto E = ExecutionCount.takeError()) { 867 consumeError(std::move(E)); 868 return Error::success(); 869 } 870 Expected<int64_t> AltExecutionCount = Ctx.evaluate(Region.FalseCount); 871 if (auto E = AltExecutionCount.takeError()) { 872 consumeError(std::move(E)); 873 return Error::success(); 874 } 875 Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount, 876 ProfileReader.hasSingleByteCoverage()); 877 878 // Record ExpansionRegion. 879 if (Region.Kind == CounterMappingRegion::ExpansionRegion) { 880 MCDCDecisions.recordExpansion(Region); 881 continue; 882 } 883 884 // Do nothing unless MCDCBranchRegion. 885 if (Region.Kind != CounterMappingRegion::MCDCBranchRegion) 886 continue; 887 888 auto Result = MCDCDecisions.processBranch(Region); 889 if (!Result) // Any Decision doesn't complete. 890 continue; 891 892 auto MCDCDecision = Result->first; 893 auto &MCDCBranches = Result->second; 894 895 // Since the bitmap identifies the executed test vectors for an MC/DC 896 // DecisionRegion, all of the information is now available to process. 897 // This is where the bulk of the MC/DC progressing takes place. 898 Expected<MCDCRecord> Record = 899 Ctx.evaluateMCDCRegion(*MCDCDecision, MCDCBranches, IsVersion11); 900 if (auto E = Record.takeError()) { 901 consumeError(std::move(E)); 902 return Error::success(); 903 } 904 905 // Save the MC/DC Record so that it can be visualized later. 906 Function.pushMCDCRecord(std::move(*Record)); 907 } 908 909 // Don't create records for (filenames, function) pairs we've already seen. 910 auto FilenamesHash = hash_combine_range(Record.Filenames.begin(), 911 Record.Filenames.end()); 912 if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second) 913 return Error::success(); 914 915 Functions.push_back(std::move(Function)); 916 917 // Performance optimization: keep track of the indices of the function records 918 // which correspond to each filename. This can be used to substantially speed 919 // up queries for coverage info in a file. 920 unsigned RecordIndex = Functions.size() - 1; 921 for (StringRef Filename : Record.Filenames) { 922 auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)]; 923 // Note that there may be duplicates in the filename set for a function 924 // record, because of e.g. macro expansions in the function in which both 925 // the macro and the function are defined in the same file. 926 if (RecordIndices.empty() || RecordIndices.back() != RecordIndex) 927 RecordIndices.push_back(RecordIndex); 928 } 929 930 return Error::success(); 931 } 932 933 // This function is for memory optimization by shortening the lifetimes 934 // of CoverageMappingReader instances. 935 Error CoverageMapping::loadFromReaders( 936 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, 937 IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage) { 938 for (const auto &CoverageReader : CoverageReaders) { 939 for (auto RecordOrErr : *CoverageReader) { 940 if (Error E = RecordOrErr.takeError()) 941 return E; 942 const auto &Record = *RecordOrErr; 943 if (Error E = Coverage.loadFunctionRecord(Record, ProfileReader)) 944 return E; 945 } 946 } 947 return Error::success(); 948 } 949 950 Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( 951 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, 952 IndexedInstrProfReader &ProfileReader) { 953 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); 954 if (Error E = loadFromReaders(CoverageReaders, ProfileReader, *Coverage)) 955 return std::move(E); 956 return std::move(Coverage); 957 } 958 959 // If E is a no_data_found error, returns success. Otherwise returns E. 960 static Error handleMaybeNoDataFoundError(Error E) { 961 return handleErrors( 962 std::move(E), [](const CoverageMapError &CME) { 963 if (CME.get() == coveragemap_error::no_data_found) 964 return static_cast<Error>(Error::success()); 965 return make_error<CoverageMapError>(CME.get(), CME.getMessage()); 966 }); 967 } 968 969 Error CoverageMapping::loadFromFile( 970 StringRef Filename, StringRef Arch, StringRef CompilationDir, 971 IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage, 972 bool &DataFound, SmallVectorImpl<object::BuildID> *FoundBinaryIDs) { 973 auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN( 974 Filename, /*IsText=*/false, /*RequiresNullTerminator=*/false); 975 if (std::error_code EC = CovMappingBufOrErr.getError()) 976 return createFileError(Filename, errorCodeToError(EC)); 977 MemoryBufferRef CovMappingBufRef = 978 CovMappingBufOrErr.get()->getMemBufferRef(); 979 SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers; 980 981 SmallVector<object::BuildIDRef> BinaryIDs; 982 auto CoverageReadersOrErr = BinaryCoverageReader::create( 983 CovMappingBufRef, Arch, Buffers, CompilationDir, 984 FoundBinaryIDs ? &BinaryIDs : nullptr); 985 if (Error E = CoverageReadersOrErr.takeError()) { 986 E = handleMaybeNoDataFoundError(std::move(E)); 987 if (E) 988 return createFileError(Filename, std::move(E)); 989 return E; 990 } 991 992 SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers; 993 for (auto &Reader : CoverageReadersOrErr.get()) 994 Readers.push_back(std::move(Reader)); 995 if (FoundBinaryIDs && !Readers.empty()) { 996 llvm::append_range(*FoundBinaryIDs, 997 llvm::map_range(BinaryIDs, [](object::BuildIDRef BID) { 998 return object::BuildID(BID); 999 })); 1000 } 1001 DataFound |= !Readers.empty(); 1002 if (Error E = loadFromReaders(Readers, ProfileReader, Coverage)) 1003 return createFileError(Filename, std::move(E)); 1004 return Error::success(); 1005 } 1006 1007 Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( 1008 ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename, 1009 vfs::FileSystem &FS, ArrayRef<StringRef> Arches, StringRef CompilationDir, 1010 const object::BuildIDFetcher *BIDFetcher, bool CheckBinaryIDs) { 1011 auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename, FS); 1012 if (Error E = ProfileReaderOrErr.takeError()) 1013 return createFileError(ProfileFilename, std::move(E)); 1014 auto ProfileReader = std::move(ProfileReaderOrErr.get()); 1015 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); 1016 bool DataFound = false; 1017 1018 auto GetArch = [&](size_t Idx) { 1019 if (Arches.empty()) 1020 return StringRef(); 1021 if (Arches.size() == 1) 1022 return Arches.front(); 1023 return Arches[Idx]; 1024 }; 1025 1026 SmallVector<object::BuildID> FoundBinaryIDs; 1027 for (const auto &File : llvm::enumerate(ObjectFilenames)) { 1028 if (Error E = 1029 loadFromFile(File.value(), GetArch(File.index()), CompilationDir, 1030 *ProfileReader, *Coverage, DataFound, &FoundBinaryIDs)) 1031 return std::move(E); 1032 } 1033 1034 if (BIDFetcher) { 1035 std::vector<object::BuildID> ProfileBinaryIDs; 1036 if (Error E = ProfileReader->readBinaryIds(ProfileBinaryIDs)) 1037 return createFileError(ProfileFilename, std::move(E)); 1038 1039 SmallVector<object::BuildIDRef> BinaryIDsToFetch; 1040 if (!ProfileBinaryIDs.empty()) { 1041 const auto &Compare = [](object::BuildIDRef A, object::BuildIDRef B) { 1042 return std::lexicographical_compare(A.begin(), A.end(), B.begin(), 1043 B.end()); 1044 }; 1045 llvm::sort(FoundBinaryIDs, Compare); 1046 std::set_difference( 1047 ProfileBinaryIDs.begin(), ProfileBinaryIDs.end(), 1048 FoundBinaryIDs.begin(), FoundBinaryIDs.end(), 1049 std::inserter(BinaryIDsToFetch, BinaryIDsToFetch.end()), Compare); 1050 } 1051 1052 for (object::BuildIDRef BinaryID : BinaryIDsToFetch) { 1053 std::optional<std::string> PathOpt = BIDFetcher->fetch(BinaryID); 1054 if (PathOpt) { 1055 std::string Path = std::move(*PathOpt); 1056 StringRef Arch = Arches.size() == 1 ? Arches.front() : StringRef(); 1057 if (Error E = loadFromFile(Path, Arch, CompilationDir, *ProfileReader, 1058 *Coverage, DataFound)) 1059 return std::move(E); 1060 } else if (CheckBinaryIDs) { 1061 return createFileError( 1062 ProfileFilename, 1063 createStringError(errc::no_such_file_or_directory, 1064 "Missing binary ID: " + 1065 llvm::toHex(BinaryID, /*LowerCase=*/true))); 1066 } 1067 } 1068 } 1069 1070 if (!DataFound) 1071 return createFileError( 1072 join(ObjectFilenames.begin(), ObjectFilenames.end(), ", "), 1073 make_error<CoverageMapError>(coveragemap_error::no_data_found)); 1074 return std::move(Coverage); 1075 } 1076 1077 namespace { 1078 1079 /// Distributes functions into instantiation sets. 1080 /// 1081 /// An instantiation set is a collection of functions that have the same source 1082 /// code, ie, template functions specializations. 1083 class FunctionInstantiationSetCollector { 1084 using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; 1085 MapT InstantiatedFunctions; 1086 1087 public: 1088 void insert(const FunctionRecord &Function, unsigned FileID) { 1089 auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end(); 1090 while (I != E && I->FileID != FileID) 1091 ++I; 1092 assert(I != E && "function does not cover the given file"); 1093 auto &Functions = InstantiatedFunctions[I->startLoc()]; 1094 Functions.push_back(&Function); 1095 } 1096 1097 MapT::iterator begin() { return InstantiatedFunctions.begin(); } 1098 MapT::iterator end() { return InstantiatedFunctions.end(); } 1099 }; 1100 1101 class SegmentBuilder { 1102 std::vector<CoverageSegment> &Segments; 1103 SmallVector<const CountedRegion *, 8> ActiveRegions; 1104 1105 SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {} 1106 1107 /// Emit a segment with the count from \p Region starting at \p StartLoc. 1108 // 1109 /// \p IsRegionEntry: The segment is at the start of a new non-gap region. 1110 /// \p EmitSkippedRegion: The segment must be emitted as a skipped region. 1111 void startSegment(const CountedRegion &Region, LineColPair StartLoc, 1112 bool IsRegionEntry, bool EmitSkippedRegion = false) { 1113 bool HasCount = !EmitSkippedRegion && 1114 (Region.Kind != CounterMappingRegion::SkippedRegion); 1115 1116 // If the new segment wouldn't affect coverage rendering, skip it. 1117 if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) { 1118 const auto &Last = Segments.back(); 1119 if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount && 1120 !Last.IsRegionEntry) 1121 return; 1122 } 1123 1124 if (HasCount) 1125 Segments.emplace_back(StartLoc.first, StartLoc.second, 1126 Region.ExecutionCount, IsRegionEntry, 1127 Region.Kind == CounterMappingRegion::GapRegion); 1128 else 1129 Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry); 1130 1131 LLVM_DEBUG({ 1132 const auto &Last = Segments.back(); 1133 dbgs() << "Segment at " << Last.Line << ":" << Last.Col 1134 << " (count = " << Last.Count << ")" 1135 << (Last.IsRegionEntry ? ", RegionEntry" : "") 1136 << (!Last.HasCount ? ", Skipped" : "") 1137 << (Last.IsGapRegion ? ", Gap" : "") << "\n"; 1138 }); 1139 } 1140 1141 /// Emit segments for active regions which end before \p Loc. 1142 /// 1143 /// \p Loc: The start location of the next region. If std::nullopt, all active 1144 /// regions are completed. 1145 /// \p FirstCompletedRegion: Index of the first completed region. 1146 void completeRegionsUntil(std::optional<LineColPair> Loc, 1147 unsigned FirstCompletedRegion) { 1148 // Sort the completed regions by end location. This makes it simple to 1149 // emit closing segments in sorted order. 1150 auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion; 1151 std::stable_sort(CompletedRegionsIt, ActiveRegions.end(), 1152 [](const CountedRegion *L, const CountedRegion *R) { 1153 return L->endLoc() < R->endLoc(); 1154 }); 1155 1156 // Emit segments for all completed regions. 1157 for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E; 1158 ++I) { 1159 const auto *CompletedRegion = ActiveRegions[I]; 1160 assert((!Loc || CompletedRegion->endLoc() <= *Loc) && 1161 "Completed region ends after start of new region"); 1162 1163 const auto *PrevCompletedRegion = ActiveRegions[I - 1]; 1164 auto CompletedSegmentLoc = PrevCompletedRegion->endLoc(); 1165 1166 // Don't emit any more segments if they start where the new region begins. 1167 if (Loc && CompletedSegmentLoc == *Loc) 1168 break; 1169 1170 // Don't emit a segment if the next completed region ends at the same 1171 // location as this one. 1172 if (CompletedSegmentLoc == CompletedRegion->endLoc()) 1173 continue; 1174 1175 // Use the count from the last completed region which ends at this loc. 1176 for (unsigned J = I + 1; J < E; ++J) 1177 if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc()) 1178 CompletedRegion = ActiveRegions[J]; 1179 1180 startSegment(*CompletedRegion, CompletedSegmentLoc, false); 1181 } 1182 1183 auto Last = ActiveRegions.back(); 1184 if (FirstCompletedRegion && Last->endLoc() != *Loc) { 1185 // If there's a gap after the end of the last completed region and the 1186 // start of the new region, use the last active region to fill the gap. 1187 startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(), 1188 false); 1189 } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) { 1190 // Emit a skipped segment if there are no more active regions. This 1191 // ensures that gaps between functions are marked correctly. 1192 startSegment(*Last, Last->endLoc(), false, true); 1193 } 1194 1195 // Pop the completed regions. 1196 ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end()); 1197 } 1198 1199 void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) { 1200 for (const auto &CR : enumerate(Regions)) { 1201 auto CurStartLoc = CR.value().startLoc(); 1202 1203 // Active regions which end before the current region need to be popped. 1204 auto CompletedRegions = 1205 std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(), 1206 [&](const CountedRegion *Region) { 1207 return !(Region->endLoc() <= CurStartLoc); 1208 }); 1209 if (CompletedRegions != ActiveRegions.end()) { 1210 unsigned FirstCompletedRegion = 1211 std::distance(ActiveRegions.begin(), CompletedRegions); 1212 completeRegionsUntil(CurStartLoc, FirstCompletedRegion); 1213 } 1214 1215 bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion; 1216 1217 // Try to emit a segment for the current region. 1218 if (CurStartLoc == CR.value().endLoc()) { 1219 // Avoid making zero-length regions active. If it's the last region, 1220 // emit a skipped segment. Otherwise use its predecessor's count. 1221 const bool Skipped = 1222 (CR.index() + 1) == Regions.size() || 1223 CR.value().Kind == CounterMappingRegion::SkippedRegion; 1224 startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(), 1225 CurStartLoc, !GapRegion, Skipped); 1226 // If it is skipped segment, create a segment with last pushed 1227 // regions's count at CurStartLoc. 1228 if (Skipped && !ActiveRegions.empty()) 1229 startSegment(*ActiveRegions.back(), CurStartLoc, false); 1230 continue; 1231 } 1232 if (CR.index() + 1 == Regions.size() || 1233 CurStartLoc != Regions[CR.index() + 1].startLoc()) { 1234 // Emit a segment if the next region doesn't start at the same location 1235 // as this one. 1236 startSegment(CR.value(), CurStartLoc, !GapRegion); 1237 } 1238 1239 // This region is active (i.e not completed). 1240 ActiveRegions.push_back(&CR.value()); 1241 } 1242 1243 // Complete any remaining active regions. 1244 if (!ActiveRegions.empty()) 1245 completeRegionsUntil(std::nullopt, 0); 1246 } 1247 1248 /// Sort a nested sequence of regions from a single file. 1249 static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) { 1250 llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) { 1251 if (LHS.startLoc() != RHS.startLoc()) 1252 return LHS.startLoc() < RHS.startLoc(); 1253 if (LHS.endLoc() != RHS.endLoc()) 1254 // When LHS completely contains RHS, we sort LHS first. 1255 return RHS.endLoc() < LHS.endLoc(); 1256 // If LHS and RHS cover the same area, we need to sort them according 1257 // to their kinds so that the most suitable region will become "active" 1258 // in combineRegions(). Because we accumulate counter values only from 1259 // regions of the same kind as the first region of the area, prefer 1260 // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion. 1261 static_assert(CounterMappingRegion::CodeRegion < 1262 CounterMappingRegion::ExpansionRegion && 1263 CounterMappingRegion::ExpansionRegion < 1264 CounterMappingRegion::SkippedRegion, 1265 "Unexpected order of region kind values"); 1266 return LHS.Kind < RHS.Kind; 1267 }); 1268 } 1269 1270 /// Combine counts of regions which cover the same area. 1271 static ArrayRef<CountedRegion> 1272 combineRegions(MutableArrayRef<CountedRegion> Regions) { 1273 if (Regions.empty()) 1274 return Regions; 1275 auto Active = Regions.begin(); 1276 auto End = Regions.end(); 1277 for (auto I = Regions.begin() + 1; I != End; ++I) { 1278 if (Active->startLoc() != I->startLoc() || 1279 Active->endLoc() != I->endLoc()) { 1280 // Shift to the next region. 1281 ++Active; 1282 if (Active != I) 1283 *Active = *I; 1284 continue; 1285 } 1286 // Merge duplicate region. 1287 // If CodeRegions and ExpansionRegions cover the same area, it's probably 1288 // a macro which is fully expanded to another macro. In that case, we need 1289 // to accumulate counts only from CodeRegions, or else the area will be 1290 // counted twice. 1291 // On the other hand, a macro may have a nested macro in its body. If the 1292 // outer macro is used several times, the ExpansionRegion for the nested 1293 // macro will also be added several times. These ExpansionRegions cover 1294 // the same source locations and have to be combined to reach the correct 1295 // value for that area. 1296 // We add counts of the regions of the same kind as the active region 1297 // to handle the both situations. 1298 if (I->Kind == Active->Kind) { 1299 assert(I->HasSingleByteCoverage == Active->HasSingleByteCoverage && 1300 "Regions are generated in different coverage modes"); 1301 if (I->HasSingleByteCoverage) 1302 Active->ExecutionCount = Active->ExecutionCount || I->ExecutionCount; 1303 else 1304 Active->ExecutionCount += I->ExecutionCount; 1305 } 1306 } 1307 return Regions.drop_back(std::distance(++Active, End)); 1308 } 1309 1310 public: 1311 /// Build a sorted list of CoverageSegments from a list of Regions. 1312 static std::vector<CoverageSegment> 1313 buildSegments(MutableArrayRef<CountedRegion> Regions) { 1314 std::vector<CoverageSegment> Segments; 1315 SegmentBuilder Builder(Segments); 1316 1317 sortNestedRegions(Regions); 1318 ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions); 1319 1320 LLVM_DEBUG({ 1321 dbgs() << "Combined regions:\n"; 1322 for (const auto &CR : CombinedRegions) 1323 dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " 1324 << CR.LineEnd << ":" << CR.ColumnEnd 1325 << " (count=" << CR.ExecutionCount << ")\n"; 1326 }); 1327 1328 Builder.buildSegmentsImpl(CombinedRegions); 1329 1330 #ifndef NDEBUG 1331 for (unsigned I = 1, E = Segments.size(); I < E; ++I) { 1332 const auto &L = Segments[I - 1]; 1333 const auto &R = Segments[I]; 1334 if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) { 1335 if (L.Line == R.Line && L.Col == R.Col && !L.HasCount) 1336 continue; 1337 LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col 1338 << " followed by " << R.Line << ":" << R.Col << "\n"); 1339 assert(false && "Coverage segments not unique or sorted"); 1340 } 1341 } 1342 #endif 1343 1344 return Segments; 1345 } 1346 }; 1347 1348 } // end anonymous namespace 1349 1350 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const { 1351 std::vector<StringRef> Filenames; 1352 for (const auto &Function : getCoveredFunctions()) 1353 llvm::append_range(Filenames, Function.Filenames); 1354 llvm::sort(Filenames); 1355 auto Last = std::unique(Filenames.begin(), Filenames.end()); 1356 Filenames.erase(Last, Filenames.end()); 1357 return Filenames; 1358 } 1359 1360 static SmallBitVector gatherFileIDs(StringRef SourceFile, 1361 const FunctionRecord &Function) { 1362 SmallBitVector FilenameEquivalence(Function.Filenames.size(), false); 1363 for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I) 1364 if (SourceFile == Function.Filenames[I]) 1365 FilenameEquivalence[I] = true; 1366 return FilenameEquivalence; 1367 } 1368 1369 /// Return the ID of the file where the definition of the function is located. 1370 static std::optional<unsigned> 1371 findMainViewFileID(const FunctionRecord &Function) { 1372 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); 1373 for (const auto &CR : Function.CountedRegions) 1374 if (CR.Kind == CounterMappingRegion::ExpansionRegion) 1375 IsNotExpandedFile[CR.ExpandedFileID] = false; 1376 int I = IsNotExpandedFile.find_first(); 1377 if (I == -1) 1378 return std::nullopt; 1379 return I; 1380 } 1381 1382 /// Check if SourceFile is the file that contains the definition of 1383 /// the Function. Return the ID of the file in that case or std::nullopt 1384 /// otherwise. 1385 static std::optional<unsigned> 1386 findMainViewFileID(StringRef SourceFile, const FunctionRecord &Function) { 1387 std::optional<unsigned> I = findMainViewFileID(Function); 1388 if (I && SourceFile == Function.Filenames[*I]) 1389 return I; 1390 return std::nullopt; 1391 } 1392 1393 static bool isExpansion(const CountedRegion &R, unsigned FileID) { 1394 return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID; 1395 } 1396 1397 CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const { 1398 CoverageData FileCoverage(Filename); 1399 std::vector<CountedRegion> Regions; 1400 1401 // Look up the function records in the given file. Due to hash collisions on 1402 // the filename, we may get back some records that are not in the file. 1403 ArrayRef<unsigned> RecordIndices = 1404 getImpreciseRecordIndicesForFilename(Filename); 1405 for (unsigned RecordIndex : RecordIndices) { 1406 const FunctionRecord &Function = Functions[RecordIndex]; 1407 auto MainFileID = findMainViewFileID(Filename, Function); 1408 auto FileIDs = gatherFileIDs(Filename, Function); 1409 for (const auto &CR : Function.CountedRegions) 1410 if (FileIDs.test(CR.FileID)) { 1411 Regions.push_back(CR); 1412 if (MainFileID && isExpansion(CR, *MainFileID)) 1413 FileCoverage.Expansions.emplace_back(CR, Function); 1414 } 1415 // Capture branch regions specific to the function (excluding expansions). 1416 for (const auto &CR : Function.CountedBranchRegions) 1417 if (FileIDs.test(CR.FileID) && (CR.FileID == CR.ExpandedFileID)) 1418 FileCoverage.BranchRegions.push_back(CR); 1419 // Capture MCDC records specific to the function. 1420 for (const auto &MR : Function.MCDCRecords) 1421 if (FileIDs.test(MR.getDecisionRegion().FileID)) 1422 FileCoverage.MCDCRecords.push_back(MR); 1423 } 1424 1425 LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); 1426 FileCoverage.Segments = SegmentBuilder::buildSegments(Regions); 1427 1428 return FileCoverage; 1429 } 1430 1431 std::vector<InstantiationGroup> 1432 CoverageMapping::getInstantiationGroups(StringRef Filename) const { 1433 FunctionInstantiationSetCollector InstantiationSetCollector; 1434 // Look up the function records in the given file. Due to hash collisions on 1435 // the filename, we may get back some records that are not in the file. 1436 ArrayRef<unsigned> RecordIndices = 1437 getImpreciseRecordIndicesForFilename(Filename); 1438 for (unsigned RecordIndex : RecordIndices) { 1439 const FunctionRecord &Function = Functions[RecordIndex]; 1440 auto MainFileID = findMainViewFileID(Filename, Function); 1441 if (!MainFileID) 1442 continue; 1443 InstantiationSetCollector.insert(Function, *MainFileID); 1444 } 1445 1446 std::vector<InstantiationGroup> Result; 1447 for (auto &InstantiationSet : InstantiationSetCollector) { 1448 InstantiationGroup IG{InstantiationSet.first.first, 1449 InstantiationSet.first.second, 1450 std::move(InstantiationSet.second)}; 1451 Result.emplace_back(std::move(IG)); 1452 } 1453 return Result; 1454 } 1455 1456 CoverageData 1457 CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { 1458 auto MainFileID = findMainViewFileID(Function); 1459 if (!MainFileID) 1460 return CoverageData(); 1461 1462 CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); 1463 std::vector<CountedRegion> Regions; 1464 for (const auto &CR : Function.CountedRegions) 1465 if (CR.FileID == *MainFileID) { 1466 Regions.push_back(CR); 1467 if (isExpansion(CR, *MainFileID)) 1468 FunctionCoverage.Expansions.emplace_back(CR, Function); 1469 } 1470 // Capture branch regions specific to the function (excluding expansions). 1471 for (const auto &CR : Function.CountedBranchRegions) 1472 if (CR.FileID == *MainFileID) 1473 FunctionCoverage.BranchRegions.push_back(CR); 1474 1475 // Capture MCDC records specific to the function. 1476 for (const auto &MR : Function.MCDCRecords) 1477 if (MR.getDecisionRegion().FileID == *MainFileID) 1478 FunctionCoverage.MCDCRecords.push_back(MR); 1479 1480 LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name 1481 << "\n"); 1482 FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 1483 1484 return FunctionCoverage; 1485 } 1486 1487 CoverageData CoverageMapping::getCoverageForExpansion( 1488 const ExpansionRecord &Expansion) const { 1489 CoverageData ExpansionCoverage( 1490 Expansion.Function.Filenames[Expansion.FileID]); 1491 std::vector<CountedRegion> Regions; 1492 for (const auto &CR : Expansion.Function.CountedRegions) 1493 if (CR.FileID == Expansion.FileID) { 1494 Regions.push_back(CR); 1495 if (isExpansion(CR, Expansion.FileID)) 1496 ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function); 1497 } 1498 for (const auto &CR : Expansion.Function.CountedBranchRegions) 1499 // Capture branch regions that only pertain to the corresponding expansion. 1500 if (CR.FileID == Expansion.FileID) 1501 ExpansionCoverage.BranchRegions.push_back(CR); 1502 1503 LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file " 1504 << Expansion.FileID << "\n"); 1505 ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 1506 1507 return ExpansionCoverage; 1508 } 1509 1510 LineCoverageStats::LineCoverageStats( 1511 ArrayRef<const CoverageSegment *> LineSegments, 1512 const CoverageSegment *WrappedSegment, unsigned Line) 1513 : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line), 1514 LineSegments(LineSegments), WrappedSegment(WrappedSegment) { 1515 // Find the minimum number of regions which start in this line. 1516 unsigned MinRegionCount = 0; 1517 auto isStartOfRegion = [](const CoverageSegment *S) { 1518 return !S->IsGapRegion && S->HasCount && S->IsRegionEntry; 1519 }; 1520 for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I) 1521 if (isStartOfRegion(LineSegments[I])) 1522 ++MinRegionCount; 1523 1524 bool StartOfSkippedRegion = !LineSegments.empty() && 1525 !LineSegments.front()->HasCount && 1526 LineSegments.front()->IsRegionEntry; 1527 1528 HasMultipleRegions = MinRegionCount > 1; 1529 Mapped = 1530 !StartOfSkippedRegion && 1531 ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0)); 1532 1533 // if there is any starting segment at this line with a counter, it must be 1534 // mapped 1535 Mapped |= std::any_of( 1536 LineSegments.begin(), LineSegments.end(), 1537 [](const auto *Seq) { return Seq->IsRegionEntry && Seq->HasCount; }); 1538 1539 if (!Mapped) { 1540 return; 1541 } 1542 1543 // Pick the max count from the non-gap, region entry segments and the 1544 // wrapped count. 1545 if (WrappedSegment) 1546 ExecutionCount = WrappedSegment->Count; 1547 if (!MinRegionCount) 1548 return; 1549 for (const auto *LS : LineSegments) 1550 if (isStartOfRegion(LS)) 1551 ExecutionCount = std::max(ExecutionCount, LS->Count); 1552 } 1553 1554 LineCoverageIterator &LineCoverageIterator::operator++() { 1555 if (Next == CD.end()) { 1556 Stats = LineCoverageStats(); 1557 Ended = true; 1558 return *this; 1559 } 1560 if (Segments.size()) 1561 WrappedSegment = Segments.back(); 1562 Segments.clear(); 1563 while (Next != CD.end() && Next->Line == Line) 1564 Segments.push_back(&*Next++); 1565 Stats = LineCoverageStats(Segments, WrappedSegment, Line); 1566 ++Line; 1567 return *this; 1568 } 1569 1570 static std::string getCoverageMapErrString(coveragemap_error Err, 1571 const std::string &ErrMsg = "") { 1572 std::string Msg; 1573 raw_string_ostream OS(Msg); 1574 1575 switch (Err) { 1576 case coveragemap_error::success: 1577 OS << "success"; 1578 break; 1579 case coveragemap_error::eof: 1580 OS << "end of File"; 1581 break; 1582 case coveragemap_error::no_data_found: 1583 OS << "no coverage data found"; 1584 break; 1585 case coveragemap_error::unsupported_version: 1586 OS << "unsupported coverage format version"; 1587 break; 1588 case coveragemap_error::truncated: 1589 OS << "truncated coverage data"; 1590 break; 1591 case coveragemap_error::malformed: 1592 OS << "malformed coverage data"; 1593 break; 1594 case coveragemap_error::decompression_failed: 1595 OS << "failed to decompress coverage data (zlib)"; 1596 break; 1597 case coveragemap_error::invalid_or_missing_arch_specifier: 1598 OS << "`-arch` specifier is invalid or missing for universal binary"; 1599 break; 1600 } 1601 1602 // If optional error message is not empty, append it to the message. 1603 if (!ErrMsg.empty()) 1604 OS << ": " << ErrMsg; 1605 1606 return Msg; 1607 } 1608 1609 namespace { 1610 1611 // FIXME: This class is only here to support the transition to llvm::Error. It 1612 // will be removed once this transition is complete. Clients should prefer to 1613 // deal with the Error value directly, rather than converting to error_code. 1614 class CoverageMappingErrorCategoryType : public std::error_category { 1615 const char *name() const noexcept override { return "llvm.coveragemap"; } 1616 std::string message(int IE) const override { 1617 return getCoverageMapErrString(static_cast<coveragemap_error>(IE)); 1618 } 1619 }; 1620 1621 } // end anonymous namespace 1622 1623 std::string CoverageMapError::message() const { 1624 return getCoverageMapErrString(Err, Msg); 1625 } 1626 1627 const std::error_category &llvm::coverage::coveragemap_category() { 1628 static CoverageMappingErrorCategoryType ErrorCategory; 1629 return ErrorCategory; 1630 } 1631 1632 char CoverageMapError::ID = 0; 1633