CoverageMapping.cpp Source File (original) (raw)

32#include

33#include

34#include

35#include

36#include

37#include

38#include

39#include

40#include

41#include

42#include <system_error>

43#include

44#include

46using namespace llvm;

47using namespace coverage;

49#define DEBUG_TYPE "coverage-mapping"

52 auto [It, Inserted] = ExpressionIndices.try_emplace(E, Expressions.size());

53 if (Inserted)

54 Expressions.push_back(E);

56}

58void CounterExpressionBuilder::extractTerms(Counter C, int Factor,

60 switch (C.getKind()) {

62 break;

65 break;

67 const auto &E = Expressions[C.getExpressionID()];

68 extractTerms(E.LHS, Factor, Terms);

69 extractTerms(

71 break;

72 }

73}

75Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {

78 extractTerms(ExpressionTree, +1, Terms);

82 if (Terms.size() == 0)

86 llvm::sort(Terms, [](const Term &LHS, const Term &RHS) {

87 return LHS.CounterID < RHS.CounterID;

88 });

91 auto Prev = Terms.begin();

92 for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {

93 if (I->CounterID == Prev->CounterID) {

94 Prev->Factor += I->Factor;

95 continue;

96 }

97 ++Prev;

98 *Prev = *I;

99 }

100 Terms.erase(++Prev, Terms.end());

101

103

104

105 for (auto T : Terms) {

106 if (T.Factor <= 0)

107 continue;

108 for (int I = 0; I < T.Factor; ++I)

109 if (C.isZero())

111 else

114 }

115

116

117 for (auto T : Terms) {

118 if (T.Factor >= 0)

119 continue;

120 for (int I = 0; I < -T.Factor; ++I)

123 }

124 return C;

125}

126

129 return Simplify ? simplify(Cnt) : Cnt;

130}

131

133 bool Simplify) {

135 return Simplify ? simplify(Cnt) : Cnt;

136}

137

139

140 if (auto I = Map.find(C); I != Map.end())

141 return I->second;

142

143 if (.isExpression())

144 return C;

145

146 auto CE = Expressions[C.getExpressionID()];

147 auto NewLHS = subst(CE.LHS, Map);

148 auto NewRHS = subst(CE.RHS, Map);

149

150

151 switch (CE.Kind) {

153 C = add(NewLHS, NewRHS);

154 break;

157 break;

158 }

159

160 return C;

161}

162

164 switch (C.getKind()) {

166 OS << '0';

167 return;

169 OS << '#' << C.getCounterID();

170 break;

172 if (C.getExpressionID() >= Expressions.size())

173 return;

174 const auto &E = Expressions[C.getExpressionID()];

175 OS << '(';

179 OS << ')';

180 break;

181 }

182 }

183 if (CounterValues.empty())

184 return;

186 if (auto E = Value.takeError()) {

188 return;

189 }

190 OS << '[' << *Value << ']';

191}

192

194 struct StackElem {

196 int64_t LHS = 0;

197 enum {

198 KNeverVisited = 0,

199 KVisitedOnce = 1,

200 KVisitedTwice = 2,

201 } VisitCount = KNeverVisited;

202 };

203

204 std::stack CounterStack;

205 CounterStack.push({C});

206

207 int64_t LastPoppedValue;

208

209 while (!CounterStack.empty()) {

210 StackElem &Current = CounterStack.top();

211

212 switch (Current.ICounter.getKind()) {

214 LastPoppedValue = 0;

215 CounterStack.pop();

216 break;

218 if (Current.ICounter.getCounterID() >= CounterValues.size())

220 LastPoppedValue = CounterValues[Current.ICounter.getCounterID()];

221 CounterStack.pop();

222 break;

224 if (Current.ICounter.getExpressionID() >= Expressions.size())

226 const auto &E = Expressions[Current.ICounter.getExpressionID()];

227 if (Current.VisitCount == StackElem::KNeverVisited) {

228 CounterStack.push(StackElem{E.LHS});

229 Current.VisitCount = StackElem::KVisitedOnce;

230 } else if (Current.VisitCount == StackElem::KVisitedOnce) {

231 Current.LHS = LastPoppedValue;

232 CounterStack.push(StackElem{E.RHS});

233 Current.VisitCount = StackElem::KVisitedTwice;

234 } else {

235 int64_t LHS = Current.LHS;

236 int64_t RHS = LastPoppedValue;

237 LastPoppedValue =

239 CounterStack.pop();

240 }

241 break;

242 }

243 }

244 }

245

246 return LastPoppedValue;

247}

248

249

250

251

252

254 if (IndependencePairs)

255 return;

256

257 IndependencePairs.emplace();

258

259 unsigned NumTVs = TV.size();

260

261 unsigned TVTrueIdx = std::distance(

263 std::find_if(TV.begin(), TV.end(),

264 [&](auto I) { return (I.second == MCDCRecord::MCDC_True); })

265

266 );

267 for (unsigned I = TVTrueIdx; I < NumTVs; ++I) {

268 const auto &[A, ACond] = TV[I];

270 for (unsigned J = 0; J < TVTrueIdx; ++J) {

271 const auto &[B, BCond] = TV[J];

273

274

275 auto AB = A.getDifferences(B);

276 if (AB.count() == 1)

277 IndependencePairs->insert(

278 {AB.find_first(), std::make_pair(J + 1, I + 1)});

279 }

280 }

281}

282

285 : Indices(NextIDs.size()) {

286

287 auto N = NextIDs.size();

289 for (unsigned ID = 0; ID < N; ++ID) {

290 for (unsigned C = 0; C < 2; ++C) {

291#ifndef NDEBUG

293#endif

294 auto NextID = NextIDs[ID][C];

295 Nodes[ID].NextIDs[C] = NextID;

296 if (NextID >= 0)

297 ++Nodes[NextID].InCount;

298 }

299 }

300

301

304 int,

305 unsigned

306 >>

307 Decisions;

308

309

311 assert(Nodes[0].InCount == 0);

312 Nodes[0].Width = 1;

314

315 unsigned Ord = 0;

316 while (!Q.empty()) {

317 auto IID = Q.begin();

318 int ID = *IID;

320 auto &Node = Nodes[ID];

321 assert(Node.Width > 0);

322

323 for (unsigned I = 0; I < 2; ++I) {

324 auto NextID = Node.NextIDs[I];

325 assert(NextID != 0 && "NextID should not point to the top");

326 if (NextID < 0) {

327

328 Decisions.emplace_back(-Node.Width, Ord++, ID, I);

329 assert(Ord == Decisions.size());

330 continue;

331 }

332

333

334 auto &NextNode = Nodes[NextID];

335 assert(NextNode.InCount > 0);

336

337

340 auto NextWidth = int64_t(NextNode.Width) + Node.Width;

343 return;

344 }

345 NextNode.Width = NextWidth;

346

347

348

349 if (--NextNode.InCount == 0)

351 }

352 }

353

355

356

357 int64_t CurIdx = 0;

358 for (auto [NegWidth, Ord, ID, C] : Decisions) {

359 int Width = -NegWidth;

360 assert(Nodes[ID].Width == Width);

361 assert(Nodes[ID].NextIDs[C] < 0);

364 CurIdx += Width;

367 return;

368 }

369 }

370

373

374#ifndef NDEBUG

375 for (const auto &Idxs : Indices)

376 for (auto Idx : Idxs)

379#endif

380}

381

382namespace {

383

384

385

386class NextIDsBuilder {

387protected:

389

390public:

392 : NextIDs(Branches.size()) {

393#ifndef NDEBUG

395#endif

396 for (const auto *Branch : Branches) {

397 const auto &BranchParams = Branch->getBranchParams();

398 assert(SeenIDs.insert(BranchParams.ID).second && "Duplicate CondID");

399 NextIDs[BranchParams.ID] = BranchParams.Conds;

400 }

401 assert(SeenIDs.size() == Branches.size());

402 }

403};

404

406

407

408

409

411

412

415

416

417

419

420

421 unsigned NumConditions;

422

423

425

426

428

429

430

431 std::array<MCDCRecord::TestVectors, 2> ExecVectorsByCond;

432

433

434

436

437#ifndef NDEBUG

439#endif

440

441 bool IsVersion11;

442

443public:

444 MCDCRecordProcessor(const BitVector &Bitmap,

447 bool IsVersion11)

448 : NextIDsBuilder(Branches), TVIdxBuilder(this->NextIDs), Bitmap(Bitmap),

450 Branches(Branches), NumConditions(DecisionParams.NumConditions),

452 IndependencePairs(NumConditions), ExecVectors(ExecVectorsByCond[false]),

453 IsVersion11(IsVersion11) {}

454

455private:

456

457

458

460 int TVIdx) {

464 TV.set(ID, MCDCCond);

465 auto NextID = NextIDs[ID][MCDCCond];

466 auto NextTVIdx = TVIdx + Indices[ID][MCDCCond];

467 assert(NextID == SavedNodes[ID].NextIDs[MCDCCond]);

468 if (NextID >= 0) {

469 buildTestVector(TV, NextID, NextTVIdx);

470 continue;

471 }

472

473 assert(TVIdx < SavedNodes[ID].Width);

474 assert(TVIdxs.insert(NextTVIdx).second && "Duplicate TVIdx");

475

476 if (!Bitmap[IsVersion11

477 ? DecisionParams.BitmapIdx * CHAR_BIT + TV.getIndex()

478 : DecisionParams.BitmapIdx - NumTestVectors + NextTVIdx])

479 continue;

480

481

482

483

484 ExecVectorsByCond[MCDCCond].push_back({TV, MCDCCond});

485 }

486

487

489 }

490

491

492

493 void findExecutedTestVectors() {

494

495

496

497

499 buildTestVector(TV, 0, 0);

500 assert(TVIdxs.size() == unsigned(NumTestVectors) &&

501 "TVIdxs wasn't fulfilled");

502

503

504

505

506 auto &ExecVectorsT = ExecVectorsByCond[true];

507 ExecVectors.append(std::make_move_iterator(ExecVectorsT.begin()),

508 std::make_move_iterator(ExecVectorsT.end()));

509 }

510

511public:

512

513

514

515

516

517

518

519

520

524

525

526

527

528

529

530

531

532

533

534

535 for (auto [I, B] : enumerate(Branches)) {

536 const auto &BranchParams = B->getBranchParams();

537 PosToID[I] = BranchParams.ID;

538 CondLoc[I] = B->startLoc();

539 Folded[false][I] = B->FalseCount.isZero();

540 Folded[true][I] = B->Count.isZero();

541 }

542

543

544 findExecutedTestVectors();

545

546

547 return MCDCRecord(Region, std::move(ExecVectors), std::move(Folded),

548 std::move(PosToID), std::move(CondLoc));

549 }

550};

551

552}

553

557

558 MCDCRecordProcessor MCDCProcessor(Bitmap, Region, Branches, IsVersion11);

559 return MCDCProcessor.processMCDCRecord();

560}

561

563 struct StackElem {

565 int64_t LHS = 0;

566 enum {

567 KNeverVisited = 0,

568 KVisitedOnce = 1,

569 KVisitedTwice = 2,

570 } VisitCount = KNeverVisited;

571 };

572

573 std::stack CounterStack;

574 CounterStack.push({C});

575

576 int64_t LastPoppedValue;

577

578 while (!CounterStack.empty()) {

579 StackElem &Current = CounterStack.top();

580

581 switch (Current.ICounter.getKind()) {

583 LastPoppedValue = 0;

584 CounterStack.pop();

585 break;

587 LastPoppedValue = Current.ICounter.getCounterID();

588 CounterStack.pop();

589 break;

591 if (Current.ICounter.getExpressionID() >= Expressions.size()) {

592 LastPoppedValue = 0;

593 CounterStack.pop();

594 } else {

595 const auto &E = Expressions[Current.ICounter.getExpressionID()];

596 if (Current.VisitCount == StackElem::KNeverVisited) {

597 CounterStack.push(StackElem{E.LHS});

598 Current.VisitCount = StackElem::KVisitedOnce;

599 } else if (Current.VisitCount == StackElem::KVisitedOnce) {

600 Current.LHS = LastPoppedValue;

601 CounterStack.push(StackElem{E.RHS});

602 Current.VisitCount = StackElem::KVisitedTwice;

603 } else {

604 int64_t LHS = Current.LHS;

605 int64_t RHS = LastPoppedValue;

606 LastPoppedValue = std::max(LHS, RHS);

607 CounterStack.pop();

608 }

609 }

610 break;

611 }

612 }

613 }

614

615 return LastPoppedValue;

616}

617

618void FunctionRecordIterator::skipOtherFiles() {

619 while (Current != Records.end() && !Filename.empty() &&

620 Filename != Current->Filenames[0])

621 advanceOne();

622 if (Current == Records.end())

624}

625

626ArrayRef CoverageMapping::getImpreciseRecordIndicesForFilename(

628 size_t FilenameHash = hash_value(Filename);

629 auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash);

630 if (RecordIt == FilenameHash2RecordIndices.end())

631 return {};

632 return RecordIt->second;

633}

634

637 unsigned MaxCounterID = 0;

638 for (const auto &Region : Record.MappingRegions) {

640 }

641 return MaxCounterID;

642}

643

644

646 bool IsVersion11) {

647 unsigned MaxBitmapIdx = 0;

648 unsigned NumConditions = 0;

649

650

651

654 continue;

655 const auto &DecisionParams = Region.getDecisionParams();

656 if (MaxBitmapIdx <= DecisionParams.BitmapIdx) {

657 MaxBitmapIdx = DecisionParams.BitmapIdx;

658 NumConditions = DecisionParams.NumConditions;

659 }

660 }

661

662 if (IsVersion11)

663 MaxBitmapIdx = MaxBitmapIdx * CHAR_BIT +

665

666 return MaxBitmapIdx;

667}

668

669namespace {

670

671

672class MCDCDecisionRecorder {

673private:

674

675

676

677

678 struct DecisionRecord {

680

681

685

686

687

689

690

691

693

694

695

696

697

699

701 : DecisionRegion(&Decision),

702 DecisionParams(Decision.getDecisionParams()),

703 DecisionStartLoc(Decision.startLoc()),

704 DecisionEndLoc(Decision.endLoc()) {

706 }

707

708

710

711 if (R.FileID == DecisionRegion->FileID &&

712 R.startLoc() >= DecisionStartLoc && R.endLoc() <= DecisionEndLoc)

713 return true;

714

715

716 return ExpandedFileIDs.contains(R.FileID);

717 }

718

720 NotProcessed = 0,

721 Processed,

722 Completed,

723 };

724

725

726

727

730

732

735 return NotProcessed;

736

738 return NotProcessed;

739

741

742

743

744 if (ConditionID == 0)

745 MCDCBranches.insert(MCDCBranches.begin(), &Branch);

746 else

748

749

751

752

753 return (MCDCBranches.size() == DecisionParams.NumConditions ? Completed

754 : Processed);

755 }

756

757

758

759

762 return false;

763

765 return true;

766 }

767 };

768

769private:

770

771

772

774

775public:

776 ~MCDCDecisionRecorder() {

777 assert(Decisions.empty() && "All Decisions have not been resolved");

778 }

779

780

783 }

784

787 return Decision.recordExpansion(Expansion);

788 });

789 }

790

791 using DecisionAndBranches =

794 >;

795

796

797

798

799

800 std::optional

802

803 for (auto DecisionIter = Decisions.begin(), DecisionEnd = Decisions.end();

804 DecisionIter != DecisionEnd; ++DecisionIter)

805 switch (DecisionIter->addBranch(Branch)) {

806 case DecisionRecord::NotProcessed:

807 continue;

808 case DecisionRecord::Processed:

809 return std::nullopt;

810 case DecisionRecord::Completed:

811 DecisionAndBranches Result =

812 std::make_pair(DecisionIter->DecisionRegion,

813 std::move(DecisionIter->MCDCBranches));

814 Decisions.erase(DecisionIter);

816 }

817

819 }

820};

821

822}

823

824Error CoverageMapping::loadFunctionRecord(

828 if (OrigFuncName.empty())

830 "record function name is empty");

831

832 if (Record.Filenames.empty())

834 else

836

838

839 std::vector<uint64_t> Counts;

841 Record.FunctionHash, Counts)) {

844 FuncHashMismatches.emplace_back(std::string(Record.FunctionName),

845 Record.FunctionHash);

847 }

849 return make_error(IPE);

851 }

852 Ctx.setCounts(Counts);

853

854 bool IsVersion11 =

856

859 Record.FunctionHash, Bitmap)) {

862 FuncHashMismatches.emplace_back(std::string(Record.FunctionName),

863 Record.FunctionHash);

865 }

867 return make_error(IPE);

869 }

870 Ctx.setBitmap(std::move(Bitmap));

871

872 assert( Record .MappingRegions.empty() && "Function has no regions");

873

874

875

876

877

878

879 if (Record.MappingRegions.size() == 1 &&

880 Record.MappingRegions[0].Count.isZero() && Counts[0] > 0)

882

883 MCDCDecisionRecorder MCDCDecisions;

885 for (const auto &Region : Record.MappingRegions) {

886

887

889 MCDCDecisions.registerDecision(Region);

890 continue;

891 }

893 if (auto E = ExecutionCount.takeError()) {

896 }

898 if (auto E = AltExecutionCount.takeError()) {

901 }

902 Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount);

903

904

906 MCDCDecisions.recordExpansion(Region);

907 continue;

908 }

909

910

912 continue;

913

914 auto Result = MCDCDecisions.processBranch(Region);

915 if (!Result)

916 continue;

917

918 auto MCDCDecision = Result->first;

919 auto &MCDCBranches = Result->second;

920

921

922

923

925 Ctx.evaluateMCDCRegion(*MCDCDecision, MCDCBranches, IsVersion11);

926 if (auto E = Record.takeError()) {

929 }

930

931

933 }

934

935

937 Record.Filenames.end());

938 if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second)

940

941 Functions.push_back(std::move(Function));

942

943

944

945

946 unsigned RecordIndex = Functions.size() - 1;

948 auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)];

949

950

951

952 if (RecordIndices.empty() || RecordIndices.back() != RecordIndex)

953 RecordIndices.push_back(RecordIndex);

954 }

955

957}

958

959

960

961Error CoverageMapping::loadFromReaders(

962 ArrayRef<std::unique_ptr> CoverageReaders,

967 for (const auto &CoverageReader : CoverageReaders) {

968 for (auto RecordOrErr : *CoverageReader) {

969 if (Error E = RecordOrErr.takeError())

970 return E;

971 const auto &Record = *RecordOrErr;

973 return E;

974 }

975 }

977}

978

980 ArrayRef<std::unique_ptr> CoverageReaders,

982 auto Coverage = std::unique_ptr(new CoverageMapping());

983 if (Error E = loadFromReaders(CoverageReaders, ProfileReader, *Coverage))

984 return std::move(E);

985 return std::move(Coverage);

986}

987

988

994 return make_error(CME.get(), CME.getMessage());

995 });

996}

997

998Error CoverageMapping::loadFromFile(

1003 Filename, false, false);

1004 if (std::error_code EC = CovMappingBufOrErr.getError())

1007 CovMappingBufOrErr.get()->getMemBufferRef();

1009

1012 CovMappingBufRef, Arch, Buffers, CompilationDir,

1013 FoundBinaryIDs ? &BinaryIDs : nullptr);

1014 if (Error E = CoverageReadersOrErr.takeError()) {

1016 if (E)

1018 return E;

1019 }

1020

1022 for (auto &Reader : CoverageReadersOrErr.get())

1023 Readers.push_back(std::move(Reader));

1024 if (FoundBinaryIDs && !Readers.empty()) {

1028 }));

1029 }

1030 DataFound |= !Readers.empty();

1031 if (Error E = loadFromReaders(Readers, ProfileReader, Coverage))

1034}

1035

1041 if (Error E = ProfileReaderOrErr.takeError())

1043 auto ProfileReader = std::move(ProfileReaderOrErr.get());

1044 auto Coverage = std::unique_ptr(new CoverageMapping());

1045 bool DataFound = false;

1046

1047 auto GetArch = [&](size_t Idx) {

1048 if (Arches.empty())

1050 if (Arches.size() == 1)

1051 return Arches.front();

1052 return Arches[Idx];

1053 };

1054

1056 for (const auto &File : llvm::enumerate(ObjectFilenames)) {

1058 loadFromFile(File.value(), GetArch(File.index()), CompilationDir,

1059 *ProfileReader, *Coverage, DataFound, &FoundBinaryIDs))

1060 return std::move(E);

1061 }

1062

1063 if (BIDFetcher) {

1064 std::vectorobject::BuildID ProfileBinaryIDs;

1067

1069 if (!ProfileBinaryIDs.empty()) {

1071 return std::lexicographical_compare(A.begin(), A.end(), B.begin(),

1072 B.end());

1073 };

1074 llvm::sort(FoundBinaryIDs, Compare);

1075 std::set_difference(

1076 ProfileBinaryIDs.begin(), ProfileBinaryIDs.end(),

1077 FoundBinaryIDs.begin(), FoundBinaryIDs.end(),

1078 std::inserter(BinaryIDsToFetch, BinaryIDsToFetch.end()), Compare);

1079 }

1080

1082 std::optionalstd::string PathOpt = BIDFetcher->fetch(BinaryID);

1083 if (PathOpt) {

1084 std::string Path = std::move(*PathOpt);

1086 if (Error E = loadFromFile(Path, Arch, CompilationDir, *ProfileReader,

1087 *Coverage, DataFound))

1088 return std::move(E);

1089 } else if (CheckBinaryIDs) {

1091 ProfileFilename,

1093 "Missing binary ID: " +

1094 llvm::toHex(BinaryID, true)));

1095 }

1096 }

1097 }

1098

1099 if (!DataFound)

1101 join(ObjectFilenames.begin(), ObjectFilenames.end(), ", "),

1103 return std::move(Coverage);

1104}

1105

1106namespace {

1107

1108

1109

1110

1111

1112class FunctionInstantiationSetCollector {

1113 using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>;

1114 MapT InstantiatedFunctions;

1115

1116public:

1119 while (I != E && I->FileID != FileID)

1120 ++I;

1121 assert(I != E && "function does not cover the given file");

1122 auto &Functions = InstantiatedFunctions[I->startLoc()];

1123 Functions.push_back(&Function);

1124 }

1125

1126 MapT::iterator begin() { return InstantiatedFunctions.begin(); }

1127 MapT::iterator end() { return InstantiatedFunctions.end(); }

1128};

1129

1130class SegmentBuilder {

1131 std::vector &Segments;

1133

1134 SegmentBuilder(std::vector &Segments) : Segments(Segments) {}

1135

1136

1137

1138

1139

1141 bool IsRegionEntry, bool EmitSkippedRegion = false) {

1142 bool HasCount = !EmitSkippedRegion &&

1144

1145

1146 if ( Segments .empty() && !IsRegionEntry && !EmitSkippedRegion) {

1148 if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount &&

1149 Last .IsRegionEntry)

1150 return;

1151 }

1152

1153 if (HasCount)

1154 Segments.emplace_back(StartLoc.first, StartLoc.second,

1155 Region.ExecutionCount, IsRegionEntry,

1157 else

1158 Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry);

1159

1162 dbgs() << "Segment at " << Last.Line << ":" << Last.Col

1163 << " (count = " << Last.Count << ")"

1164 << (Last.IsRegionEntry ? ", RegionEntry" : "")

1165 << ( Last .HasCount ? ", Skipped" : "")

1166 << (Last.IsGapRegion ? ", Gap" : "") << "\n";

1167 });

1168 }

1169

1170

1171

1172

1173

1174

1175 void completeRegionsUntil(std::optional Loc,

1176 unsigned FirstCompletedRegion) {

1177

1178

1179 auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;

1180 std::stable_sort(CompletedRegionsIt, ActiveRegions.end(),

1182 return L->endLoc() < R->endLoc();

1183 });

1184

1185

1186 for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;

1187 ++I) {

1188 const auto *CompletedRegion = ActiveRegions[I];

1189 assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&

1190 "Completed region ends after start of new region");

1191

1192 const auto *PrevCompletedRegion = ActiveRegions[I - 1];

1193 auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();

1194

1195

1196 if (Loc && CompletedSegmentLoc == *Loc)

1197 break;

1198

1199

1200

1201 if (CompletedSegmentLoc == CompletedRegion->endLoc())

1202 continue;

1203

1204

1205 for (unsigned J = I + 1; J < E; ++J)

1206 if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc())

1207 CompletedRegion = ActiveRegions[J];

1208

1209 startSegment(*CompletedRegion, CompletedSegmentLoc, false);

1210 }

1211

1212 auto Last = ActiveRegions.back();

1213 if (FirstCompletedRegion && Last->endLoc() != *Loc) {

1214

1215

1216 startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(),

1217 false);

1218 } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) {

1219

1220

1221 startSegment(*Last, Last->endLoc(), false, true);

1222 }

1223

1224

1225 ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end());

1226 }

1227

1229 for (const auto &CR : enumerate(Regions)) {

1230 auto CurStartLoc = CR.value().startLoc();

1231

1232

1233 auto CompletedRegions =

1234 std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(),

1236 return !(Region->endLoc() <= CurStartLoc);

1237 });

1238 if (CompletedRegions != ActiveRegions.end()) {

1239 unsigned FirstCompletedRegion =

1240 std::distance(ActiveRegions.begin(), CompletedRegions);

1241 completeRegionsUntil(CurStartLoc, FirstCompletedRegion);

1242 }

1243

1245

1246

1247 if (CurStartLoc == CR.value().endLoc()) {

1248

1249

1250 const bool Skipped =

1251 (CR.index() + 1) == Regions.size() ||

1253 startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(),

1254 CurStartLoc, !GapRegion, Skipped);

1255

1256

1257 if (Skipped && !ActiveRegions.empty())

1258 startSegment(*ActiveRegions.back(), CurStartLoc, false);

1259 continue;

1260 }

1261 if (CR.index() + 1 == Regions.size() ||

1262 CurStartLoc != Regions[CR.index() + 1].startLoc()) {

1263

1264

1265 startSegment(CR.value(), CurStartLoc, !GapRegion);

1266 }

1267

1268

1269 ActiveRegions.push_back(&CR.value());

1270 }

1271

1272

1273 if (!ActiveRegions.empty())

1274 completeRegionsUntil(std::nullopt, 0);

1275 }

1276

1277

1280 if (LHS.startLoc() != RHS.startLoc())

1281 return LHS.startLoc() < RHS.startLoc();

1282 if (LHS.endLoc() != RHS.endLoc())

1283

1284 return RHS.endLoc() < LHS.endLoc();

1285

1286

1287

1288

1289

1294 "Unexpected order of region kind values");

1295 return LHS.Kind < RHS.Kind;

1296 });

1297 }

1298

1299

1302 if (Regions.empty())

1303 return Regions;

1305 auto End = Regions.end();

1306 for (auto I = Regions.begin() + 1; I != End; ++I) {

1307 if (Active->startLoc() != I->startLoc() ||

1308 Active->endLoc() != I->endLoc()) {

1309

1311 if (Active != I)

1313 continue;

1314 }

1315

1316

1317

1318

1319

1320

1321

1322

1323

1324

1325

1326

1327 if (I->Kind == Active->Kind)

1328 Active->ExecutionCount += I->ExecutionCount;

1329 }

1330 return Regions.drop_back(std::distance(++Active, End));

1331 }

1332

1333public:

1334

1335 static std::vector

1337 std::vector Segments;

1338 SegmentBuilder Builder(Segments);

1339

1340 sortNestedRegions(Regions);

1342

1344 dbgs() << "Combined regions:\n";

1345 for (const auto &CR : CombinedRegions)

1346 dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> "

1347 << CR.LineEnd << ":" << CR.ColumnEnd

1348 << " (count=" << CR.ExecutionCount << ")\n";

1349 });

1350

1351 Builder.buildSegmentsImpl(CombinedRegions);

1352

1353#ifndef NDEBUG

1354 for (unsigned I = 1, E = Segments.size(); I < E; ++I) {

1357 if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {

1358 if (L.Line == R.Line && L.Col == R.Col && .HasCount)

1359 continue;

1360 LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col

1361 << " followed by " << R.Line << ":" << R.Col << "\n");

1362 assert(false && "Coverage segments not unique or sorted");

1363 }

1364 }

1365#endif

1366

1368 }

1369};

1370

1371}

1372

1374 std::vector Filenames;

1375 for (const auto &Function : getCoveredFunctions())

1379 Filenames.erase(Last, Filenames.end());

1380 return Filenames;

1381}

1382

1386 for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)

1387 if (SourceFile == Function.Filenames[I])

1388 FilenameEquivalence[I] = true;

1389 return FilenameEquivalence;

1390}

1391

1392

1393static std::optional

1396 for (const auto &CR : Function.CountedRegions)

1398 IsNotExpandedFile[CR.ExpandedFileID] = false;

1400 if (I == -1)

1401 return std::nullopt;

1402 return I;

1403}

1404

1405

1406

1407

1408static std::optional

1411 if (I && SourceFile == Function.Filenames[*I])

1412 return I;

1413 return std::nullopt;

1414}

1415

1418}

1419

1423 std::vector Regions;

1424

1425

1426

1428 getImpreciseRecordIndicesForFilename(Filename);

1429 for (unsigned RecordIndex : RecordIndices) {

1433 for (const auto &CR : Function.CountedRegions)

1434 if (FileIDs.test(CR.FileID)) {

1435 Regions.push_back(CR);

1436 if (MainFileID && isExpansion(CR, *MainFileID))

1437 FileCoverage.Expansions.emplace_back(CR, Function);

1438 }

1439

1440 for (const auto &CR : Function.CountedBranchRegions)

1441 if (FileIDs.test(CR.FileID))

1442 FileCoverage.BranchRegions.push_back(CR);

1443

1444 for (const auto &MR : Function.MCDCRecords)

1445 if (FileIDs.test(MR.getDecisionRegion().FileID))

1446 FileCoverage.MCDCRecords.push_back(MR);

1447 }

1448

1449 LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");

1450 FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);

1451

1452 return FileCoverage;

1453}

1454

1455std::vector

1457 FunctionInstantiationSetCollector InstantiationSetCollector;

1458

1459

1461 getImpreciseRecordIndicesForFilename(Filename);

1462 for (unsigned RecordIndex : RecordIndices) {

1465 if (!MainFileID)

1466 continue;

1467 InstantiationSetCollector.insert(Function, *MainFileID);

1468 }

1469

1470 std::vector Result;

1471 for (auto &InstantiationSet : InstantiationSetCollector) {

1473 InstantiationSet.first.second,

1474 std::move(InstantiationSet.second)};

1475 Result.emplace_back(std::move(IG));

1476 }

1477 return Result;

1478}

1479

1483 if (!MainFileID)

1485

1488 Function.Filenames[*MainFileID]);

1489 std::vector Regions;

1490 for (const auto &CR : Function.CountedRegions)

1491 if (CR.FileID == *MainFileID) {

1492 Regions.push_back(CR);

1494 FunctionCoverage.Expansions.emplace_back(CR, Function);

1495 }

1496

1497 for (const auto &CR : Function.CountedBranchRegions)

1498 if (CR.FileID == *MainFileID)

1499 FunctionCoverage.BranchRegions.push_back(CR);

1500

1501

1502 for (const auto &MR : Function.MCDCRecords)

1503 if (MR.getDecisionRegion().FileID == *MainFileID)

1504 FunctionCoverage.MCDCRecords.push_back(MR);

1505

1507 << "\n");

1508 FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);

1509

1510 return FunctionCoverage;

1511}

1512

1518 std::vector Regions;

1519 for (const auto &CR : Expansion.Function.CountedRegions)

1520 if (CR.FileID == Expansion.FileID) {

1521 Regions.push_back(CR);

1523 ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);

1524 }

1525 for (const auto &CR : Expansion.Function.CountedBranchRegions)

1526

1527 if (CR.FileID == Expansion.FileID)

1528 ExpansionCoverage.BranchRegions.push_back(CR);

1529

1530 LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file "

1532 ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);

1533

1534 return ExpansionCoverage;

1535}

1536

1537LineCoverageStats::LineCoverageStats(

1540 : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line),

1541 LineSegments(LineSegments), WrappedSegment(WrappedSegment) {

1542

1543 unsigned MinRegionCount = 0;

1545 return !S->IsGapRegion && S->HasCount && S->IsRegionEntry;

1546 };

1547 for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I)

1548 if (isStartOfRegion(LineSegments[I]))

1549 ++MinRegionCount;

1550

1551 bool StartOfSkippedRegion = !LineSegments.empty() &&

1552 !LineSegments.front()->HasCount &&

1553 LineSegments.front()->IsRegionEntry;

1554

1555 HasMultipleRegions = MinRegionCount > 1;

1556 Mapped =

1557 !StartOfSkippedRegion &&

1558 ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0));

1559

1560

1561

1562 Mapped |= any_of(LineSegments, [](const auto *Seq) {

1563 return Seq->IsRegionEntry && Seq->HasCount;

1564 });

1565

1566 if (!Mapped) {

1567 return;

1568 }

1569

1570

1571

1572 if (WrappedSegment)

1573 ExecutionCount = WrappedSegment->Count;

1574 if (!MinRegionCount)

1575 return;

1576 for (const auto *LS : LineSegments)

1577 if (isStartOfRegion(LS))

1578 ExecutionCount = std::max(ExecutionCount, LS->Count);

1579}

1580

1582 if (Next == CD.end()) {

1584 Ended = true;

1585 return *this;

1586 }

1587 if (Segments.size())

1588 WrappedSegment = Segments.back();

1589 Segments.clear();

1590 while (Next != CD.end() && Next->Line == Line)

1591 Segments.push_back(&*Next++);

1593 ++Line;

1594 return *this;

1595}

1596

1598 const std::string &ErrMsg = "") {

1599 std::string Msg;

1601

1602 switch (Err) {

1604 OS << "success";

1605 break;

1607 OS << "end of File";

1608 break;

1610 OS << "no coverage data found";

1611 break;

1613 OS << "unsupported coverage format version";

1614 break;

1616 OS << "truncated coverage data";

1617 break;

1619 OS << "malformed coverage data";

1620 break;

1622 OS << "failed to decompress coverage data (zlib)";

1623 break;

1625 OS << "`-arch` specifier is invalid or missing for universal binary";

1626 break;

1627 }

1628

1629

1630 if (!ErrMsg.empty())

1631 OS << ": " << ErrMsg;

1632

1633 return Msg;

1634}

1635

1636namespace {

1637

1638

1639

1640

1641class CoverageMappingErrorCategoryType : public std::error_category {

1642 const char *name() const noexcept override { return "llvm.coveragemap"; }

1643 std::string message(int IE) const override {

1645 }

1646};

1647

1648}

1649

1652}

1653

1655 static CoverageMappingErrorCategoryType ErrorCategory;

1656 return ErrorCategory;

1657}

1658

This file declares a library for handling Build IDs and using them to find debug info.

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static SmallBitVector gatherFileIDs(StringRef SourceFile, const FunctionRecord &Function)

static std::optional< unsigned > findMainViewFileID(const FunctionRecord &Function)

Return the ID of the file where the definition of the function is located.

static bool isExpansion(const CountedRegion &R, unsigned FileID)

static Error handleMaybeNoDataFoundError(Error E)

static unsigned getMaxBitmapSize(const CoverageMappingRecord &Record, bool IsVersion11)

Returns the bit count.

static std::string getCoverageMapErrString(coveragemap_error Err, const std::string &ErrMsg="")

static unsigned getMaxCounterID(const CounterMappingContext &Ctx, const CoverageMappingRecord &Record)

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

This file defines the DenseMap class.

static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file implements the SmallBitVector class.

This file defines the SmallVector class.

Defines the virtual file system interface vfs::FileSystem.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

const T & front() const

front - Get the first element.

size_t size() const

size - Get the array size.

bool empty() const

empty - Check if the array is empty.

Implements a dense probed hash-table based set.

Lightweight error class with error context and mandatory checking.

static ErrorSuccess success()

Create a success value.

Tagged union holding either a T or a Error.

Error takeError()

Take ownership of the stored error.

Reader for the indexed binary instrprof format.

uint64_t getVersion() const override

Return the profile version.

static Expected< std::unique_ptr< IndexedInstrProfReader > > create(const Twine &Path, vfs::FileSystem &FS, const Twine &RemappingPath="")

Factory method to create an indexed reader.

Error getFunctionBitmap(StringRef FuncName, uint64_t FuncHash, BitVector &Bitmap)

Fill Bitmap with the profile data for the given function name.

bool hasSingleByteCoverage() const override

Return true if the profile has single byte counters representing coverage.

Error getFunctionCounts(StringRef FuncName, uint64_t FuncHash, std::vector< uint64_t > &Counts)

Fill Counts with the profile data for the given function name.

Error readBinaryIds(std::vector< llvm::object::BuildID > &BinaryIds) override

Read a list of binary ids.

static std::pair< instrprof_error, std::string > take(Error E)

Consume an Error and return the raw enum value contained within it, and the optional error message.

static ErrorOr< std::unique_ptr< MemoryBuffer > > getFileOrSTDIN(const Twine &Filename, bool IsText=false, bool RequiresNullTerminator=true, std::optional< Align > Alignment=std::nullopt)

Open the specified file as a MemoryBuffer, or open stdin if the Filename is "-".

MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...

MutableArrayRef< T > drop_back(size_t N=1) const

This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...

int find_first() const

Returns the index of the first set bit, -1 if none of the bits are set.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

reference emplace_back(ArgTypes &&... Args)

iterator erase(const_iterator CI)

iterator insert(iterator I, T &&Elt)

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

constexpr bool empty() const

empty - Check if the string is empty.

LLVM Value Representation.

static Expected< std::vector< std::unique_ptr< BinaryCoverageReader > > > create(MemoryBufferRef ObjectBuffer, StringRef Arch, SmallVectorImpl< std::unique_ptr< MemoryBuffer > > &ObjectFileBuffers, StringRef CompilationDir="", SmallVectorImpl< object::BuildIDRef > *BinaryIDs=nullptr)

Counter subtract(Counter LHS, Counter RHS, bool Simplify=true)

Return a counter that represents the expression that subtracts RHS from LHS.

Counter add(Counter LHS, Counter RHS, bool Simplify=true)

Return a counter that represents the expression that adds LHS and RHS.

Counter subst(Counter C, const SubstMap &Map)

std::map< Counter, Counter > SubstMap

K to V map.

A Counter mapping context is used to connect the counters, expressions and the obtained counter value...

Expected< MCDCRecord > evaluateMCDCRegion(const CounterMappingRegion &Region, ArrayRef< const CounterMappingRegion * > Branches, bool IsVersion11)

Return an MCDC record that indicates executed test vectors and condition pairs.

Expected< int64_t > evaluate(const Counter &C) const

Return the number of times that a region of code associated with this counter was executed.

unsigned getMaxCounterID(const Counter &C) const

void dump(const Counter &C, raw_ostream &OS) const

Coverage information to be processed or displayed.

std::vector< CoverageSegment >::const_iterator end() const

std::string message() const override

Return the error message as a string.

coveragemap_error get() const

const std::string & getMessage() const

The mapping of profile information to coverage data.

std::vector< StringRef > getUniqueSourceFiles() const

Returns a lexicographically sorted, unique list of files that are covered.

CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion) const

Get the coverage for an expansion within a coverage set.

CoverageData getCoverageForFunction(const FunctionRecord &Function) const

Get the coverage for a particular function.

std::vector< InstantiationGroup > getInstantiationGroups(StringRef Filename) const

Get the list of function instantiation groups in a particular file.

CoverageData getCoverageForFile(StringRef Filename) const

Get the coverage for a particular file.

static Expected< std::unique_ptr< CoverageMapping > > load(ArrayRef< std::unique_ptr< CoverageMappingReader > > CoverageReaders, IndexedInstrProfReader &ProfileReader)

Load the coverage mapping using the given readers.

Iterator over Functions, optionally filtered to a single file.

An instantiation group contains a FunctionRecord list, such that each record corresponds to a distinc...

An iterator over the LineCoverageStats objects for lines described by a CoverageData instance.

LineCoverageIterator & operator++()

Coverage statistics for a single line.

Emulate SmallVector with a pair of BitVector.

auto getIndex() const

Equivalent to buildTestVector's Index.

void set(int I, CondState Val)

Set the condition Val at position I.

Compute TestVector Indices "TVIdx" from the Conds graph.

static constexpr auto HardMaxTVs

Hard limit of test vectors.

TVIdxBuilder(const SmallVectorImpl< ConditionIDs > &NextIDs, int Offset=0)

Calculate and assign Indices.

SmallVector< std::array< int, 2 > > Indices

Output: Index for TestVectors bitmap (These are not CondIDs)

int NumTestVectors

Output: The number of test vectors.

SmallVector< MCDCNode > SavedNodes

This is no longer needed after the assignment.

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

bool contains(const_arg_type_t< ValueT > V) const

Check if the set contains the given element.

BuildIDFetcher searches local cache directories for debug info.

virtual std::optional< std::string > fetch(BuildIDRef BuildID) const

Returns the path to the debug file with the given build ID.

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.

The virtual file system interface.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

@ C

The default llvm calling convention, compatible with C.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

int16_t ConditionID

The ID for MCDCBranch.

std::array< ConditionID, 2 > ConditionIDs

const std::error_category & coveragemap_category()

@ invalid_or_missing_arch_specifier

std::pair< unsigned, unsigned > LineColPair

SmallVector< uint8_t, 10 > BuildID

A build ID in binary form.

This is an optimization pass for GlobalISel generic memory operations.

hash_code hash_value(const FixedPointSemantics &Val)

Error createFileError(const Twine &F, Error E)

Concatenate a source file path and/or name with an Error.

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.

auto enumerate(FirstRange &&First, RestRanges &&...Rest)

Given two or more input ranges, returns a new range whose values are tuples (A, B,...

StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, StringRef FileName="")

Given a PGO function name, remove the filename prefix and return the original (static) function name.

Error handleErrors(Error E, HandlerTs &&... Hs)

Pass the ErrorInfo(s) contained in E to their respective handlers.

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

auto unique(Range &&R, Predicate P)

Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)

Create formatted StringError object.

auto map_range(ContainerTy &&C, FuncTy F)

@ no_such_file_or_directory

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

auto reverse(ContainerTy &&C)

void sort(IteratorTy Start, IteratorTy End)

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

uint64_t alignTo(uint64_t Size, Align A)

Returns a multiple of A needed to store Size bytes.

Error errorCodeToError(std::error_code EC)

Helper for converting an std::error_code to a Error.

void consumeError(Error Err)

Consume a Error without doing anything.

hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)

Compute a hash_code for a sequence of values.

Associates a source range with an execution count.

A Counter expression is a value that represents an arithmetic operation with two counters.

A Counter mapping region associates a source range with a specific counter.

@ ExpansionRegion

An ExpansionRegion represents a file expansion region that associates a source range with the expansi...

@ MCDCDecisionRegion

A DecisionRegion represents a top-level boolean expression and is associated with a variable length b...

@ MCDCBranchRegion

A Branch Region can be extended to include IDs to facilitate MC/DC.

@ SkippedRegion

A SkippedRegion represents a source range with code that was skipped by a preprocessor or similar mea...

@ GapRegion

A GapRegion is like a CodeRegion, but its count is only set as the line execution count when its the ...

@ CodeRegion

A CodeRegion associates some code with a counter.

A Counter is an abstract value that describes how to compute the execution count for a region of code...

static Counter getZero()

Return the counter that represents the number zero.

static Counter getCounter(unsigned CounterId)

Return the counter that corresponds to a specific profile counter.

static Counter getExpression(unsigned ExpressionId)

Return the counter that corresponds to a specific addition counter expression.

Coverage mapping information for a single function.

The execution count information starting at a point in a file.

bool HasCount

When false, the segment was uninstrumented or skipped.

uint64_t Count

The execution count, or zero if no count was recorded.

bool IsGapRegion

Whether this enters a gap region.

Coverage information for a macro expansion or #included file.

Code coverage information for a single function.

MCDC Record grouping all information together.

void findIndependencePairs()

std::array< BitVector, 2 > BoolVector

uint16_t NumConditions

Number of Conditions used for a Decision Region.