Skip to content

Commit d168e0c

Browse files
chapunichapuni
committed
Implement MCDCTVIdxBuilder and MCDCTestVectorBuilder (LLVM side)
This accept current version of profdata. The output might be different. See also https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798
1 parent f035c01 commit d168e0c

File tree

4 files changed

+214
-80
lines changed

4 files changed

+214
-80
lines changed

‎llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h

+24
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@
3232
#include "llvm/Support/raw_ostream.h"
3333
#include <cassert>
3434
#include <cstdint>
35+
#include <functional>
3536
#include <iterator>
3637
#include <memory>
3738
#include <sstream>
@@ -557,6 +558,29 @@ struct MCDCRecord {
557558
}
558559
};
559560

561+
class MCDCTVIdxBuilder {
562+
public:
563+
struct MCDCNode {
564+
int InCount = 0;
565+
unsigned Width;
566+
struct {
567+
int ID;
568+
int Idx;
569+
} Conds[2];
570+
};
571+
572+
SmallVector<MCDCNode> Nodes;
573+
unsigned NumTestVectors;
574+
575+
public:
576+
using NodeIDs = std::tuple<unsigned, // ID1 (ends with 0)
577+
unsigned, // ID1 for False
578+
unsigned // ID1 for True
579+
>;
580+
581+
MCDCTVIdxBuilder(std::function<NodeIDs(bool TellSize)> Fetcher);
582+
};
583+
560584
/// A Counter mapping context is used to connect the counters, expressions
561585
/// and the obtained counter values.
562586
class CounterMappingContext {

‎llvm/lib/ProfileData/Coverage/CoverageMapping.cpp

+168-58
Original file line numberDiff line numberDiff line change
@@ -223,6 +223,171 @@ Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
223223
return LastPoppedValue;
224224
}
225225

226+
MCDCTVIdxBuilder::MCDCTVIdxBuilder(
227+
std::function<NodeIDs(bool TellSize)> Fetcher) {
228+
// Build Nodes and set up each InCount
229+
int MaxID = -1;
230+
Nodes.resize(std::get<0>(Fetcher(true)));
231+
while (true) {
232+
auto [ID1, FalseID1, TrueID1] = Fetcher(false);
233+
if (ID1 == 0)
234+
break;
235+
if (Nodes.size() < ID1)
236+
Nodes.resize(ID1);
237+
int ID = ID1 - 1;
238+
MaxID = std::max(MaxID, ID);
239+
auto &Node = Nodes[ID];
240+
Node.Conds[0].ID = FalseID1 - 1;
241+
Node.Conds[1].ID = TrueID1 - 1;
242+
for (unsigned I = 0; I < 2; ++I) {
243+
int NextID = Node.Conds[I].ID;
244+
if (NextID >= 0)
245+
++Nodes[NextID].InCount;
246+
}
247+
}
248+
249+
if (MaxID < 0)
250+
return;
251+
252+
// Sort key ordered by <-Width, Ord>
253+
SmallVector<std::tuple<int, /// -Width
254+
unsigned, /// Ord
255+
int, /// ID
256+
unsigned /// Cond (0 or 1)
257+
>>
258+
Decisions;
259+
260+
// Traverse Nodes to assign Idx
261+
SmallVector<int> Q;
262+
assert(Nodes[0].InCount == 0);
263+
Nodes[0].Width = 1;
264+
Q.push_back(0);
265+
266+
unsigned Ord = 0;
267+
while (!Q.empty()) {
268+
int ID = *Q.begin();
269+
Q.erase(Q.begin());
270+
auto &Node = Nodes[ID];
271+
assert(Node.Width > 0);
272+
273+
for (unsigned I = 0; I < 2; ++I) {
274+
int NextID = Node.Conds[I].ID;
275+
assert(NextID != 0);
276+
if (NextID < 0) {
277+
Decisions.emplace_back(-Node.Width, Ord++, ID, I);
278+
assert(Ord == Decisions.size());
279+
continue;
280+
}
281+
282+
auto &NextNode = Nodes[NextID];
283+
assert(NextNode.InCount > 0);
284+
Node.Conds[I].Idx = NextNode.Width; // ???
285+
NextNode.Width += Node.Width;
286+
if (--NextNode.InCount == 0)
287+
Q.push_back(NextID);
288+
}
289+
}
290+
291+
std::sort(Decisions.begin(), Decisions.end());
292+
293+
// Assign TestVector Index
294+
unsigned CurIdx = 0;
295+
for (auto [NegWidth, Ord, ID, C] : Decisions) {
296+
unsigned Width = -NegWidth;
297+
auto &Node = Nodes[ID];
298+
assert(Node.Width == Width);
299+
assert(Node.Conds[C].Idx == 0);
300+
assert(Node.Conds[C].ID < 0);
301+
Node.Conds[C].Idx = CurIdx;
302+
CurIdx += Width;
303+
}
304+
NumTestVectors = CurIdx;
305+
}
306+
307+
namespace {
308+
309+
class MCDCTestVectorBuilder : public MCDCTVIdxBuilder {
310+
MCDCRecord::TestVectors TestVectors;
311+
const BitVector &Bitmap;
312+
unsigned BitmapIdx;
313+
#ifndef NDEBUG
314+
DenseSet<unsigned> TVIDs;
315+
#endif
316+
317+
class BranchProvider {
318+
ArrayRef<const CounterMappingRegion *> Branches;
319+
unsigned BranchIdx = 0;
320+
321+
public:
322+
BranchProvider(ArrayRef<const CounterMappingRegion *> Branches)
323+
: Branches(Branches) {}
324+
325+
std::function<NodeIDs(bool)> getFetcher() {
326+
return [this](bool TellSize) {
327+
if (TellSize)
328+
return NodeIDs(Branches.size(), 0, 0);
329+
if (BranchIdx >= Branches.size())
330+
return NodeIDs(0, 0, 0);
331+
const auto *B = Branches[BranchIdx++];
332+
return NodeIDs(B->MCDCParams.ID, B->MCDCParams.FalseID,
333+
B->MCDCParams.TrueID);
334+
};
335+
}
336+
};
337+
338+
public:
339+
MCDCTestVectorBuilder(ArrayRef<const CounterMappingRegion *> Branches,
340+
const BitVector &Bitmap, unsigned BitmapIdx)
341+
: MCDCTVIdxBuilder(BranchProvider(Branches).getFetcher()), Bitmap(Bitmap),
342+
BitmapIdx(BitmapIdx) {}
343+
344+
protected:
345+
MCDCRecord::TestVector TempTV;
346+
347+
void buildTestVector(int ID = 0, unsigned TVIdx = 0, unsigned Index = 0) {
348+
const auto &Node = Nodes[ID];
349+
350+
for (unsigned I = 0; I < 2; ++I) {
351+
auto MCDCCond = (I ? MCDCRecord::MCDC_True : MCDCRecord::MCDC_False);
352+
const auto &Cond = Node.Conds[I];
353+
auto NextID = Cond.ID;
354+
Index |= I << ID;
355+
TempTV[ID] = MCDCCond;
356+
if (NextID >= 0) {
357+
buildTestVector(NextID, TVIdx + Cond.Idx, Index);
358+
continue;
359+
}
360+
361+
auto FinalTVIdx = Cond.Idx + TVIdx;
362+
assert(TVIdx < Node.Width);
363+
#ifndef NDEBUG
364+
assert(!TVIDs.contains(FinalTVIdx));
365+
TVIDs.insert(FinalTVIdx);
366+
#endif
367+
368+
assert(BitmapIdx + Index < Bitmap.size() && "Bitmap overrun");
369+
if (!Bitmap[BitmapIdx + Index])
370+
continue;
371+
372+
TestVectors.push_back(TempTV);
373+
TestVectors.back().push_back(MCDCCond);
374+
}
375+
376+
// Reset back to DontCare.
377+
TempTV[ID] = MCDCRecord::MCDC_DontCare;
378+
}
379+
380+
public:
381+
MCDCRecord::TestVectors findExecutedTestVectors() {
382+
TempTV.resize(Nodes.size(), MCDCRecord::MCDC_DontCare);
383+
buildTestVector();
384+
assert(TVIDs.size() == NumTestVectors);
385+
return std::move(TestVectors);
386+
}
387+
};
388+
389+
} // namespace
390+
226391
class MCDCRecordProcessor {
227392
/// A bitmap representing the executed test vectors for a boolean expression.
228393
/// Each index of the bitmap corresponds to a possible test vector. An index
@@ -251,9 +416,6 @@ class MCDCRecordProcessor {
251416
/// Mapping of calculated MC/DC Independence Pairs for each condition.
252417
MCDCRecord::TVPairMap IndependencePairs;
253418

254-
/// Total number of possible Test Vectors for the boolean expression.
255-
MCDCRecord::TestVectors TestVectors;
256-
257419
/// Actual executed Test Vectors for the boolean expression, based on
258420
/// ExecutedTestVectorBitmap.
259421
MCDCRecord::TestVectors ExecVectors;
@@ -265,56 +427,9 @@ class MCDCRecordProcessor {
265427
: Bitmap(Bitmap), Region(Region), Branches(Branches),
266428
NumConditions(Region.MCDCParams.NumConditions),
267429
BitmapIdx(Region.MCDCParams.BitmapIdx * CHAR_BIT),
268-
Folded(NumConditions, false), IndependencePairs(NumConditions),
269-
TestVectors((size_t)1 << NumConditions) {}
430+
Folded(NumConditions, false), IndependencePairs(NumConditions) {}
270431

271432
private:
272-
void recordTestVector(MCDCRecord::TestVector &TV, unsigned Index,
273-
MCDCRecord::CondState Result) {
274-
// Copy the completed test vector to the vector of testvectors.
275-
TestVectors[Index] = TV;
276-
277-
// The final value (T,F) is equal to the last non-dontcare state on the
278-
// path (in a short-circuiting system).
279-
TestVectors[Index].push_back(Result);
280-
}
281-
282-
// Walk the binary decision diagram and try assigning both false and true to
283-
// each node. When a terminal node (ID == 0) is reached, fill in the value in
284-
// the truth table.
285-
void buildTestVector(MCDCRecord::TestVector &TV, unsigned ID,
286-
unsigned Index) {
287-
const CounterMappingRegion *Branch = Map[ID];
288-
289-
TV[ID - 1] = MCDCRecord::MCDC_False;
290-
if (Branch->MCDCParams.FalseID > 0)
291-
buildTestVector(TV, Branch->MCDCParams.FalseID, Index);
292-
else
293-
recordTestVector(TV, Index, MCDCRecord::MCDC_False);
294-
295-
Index |= 1 << (ID - 1);
296-
TV[ID - 1] = MCDCRecord::MCDC_True;
297-
if (Branch->MCDCParams.TrueID > 0)
298-
buildTestVector(TV, Branch->MCDCParams.TrueID, Index);
299-
else
300-
recordTestVector(TV, Index, MCDCRecord::MCDC_True);
301-
302-
// Reset back to DontCare.
303-
TV[ID - 1] = MCDCRecord::MCDC_DontCare;
304-
}
305-
306-
/// Walk the bits in the bitmap. A bit set to '1' indicates that the test
307-
/// vector at the corresponding index was executed during a test run.
308-
void findExecutedTestVectors() {
309-
for (unsigned Idx = 0; Idx < (1u << NumConditions); ++Idx) {
310-
assert(BitmapIdx + Idx < Bitmap.size() && "Bitmap overrun");
311-
if (Bitmap[BitmapIdx + Idx] == 0)
312-
continue;
313-
assert(!TestVectors[Idx].empty() && "Test Vector doesn't exist.");
314-
ExecVectors.push_back(TestVectors[Idx]);
315-
}
316-
}
317-
318433
// Find an independence pair for each condition:
319434
// - The condition is true in one test and false in the other.
320435
// - The decision outcome is true one test and false in the other.
@@ -378,14 +493,9 @@ class MCDCRecordProcessor {
378493
Folded[I++] = (B->Count.isZero() && B->FalseCount.isZero());
379494
}
380495

381-
// Walk the binary decision diagram to enumerate all possible test vectors.
382-
// We start at the root node (ID == 1) with all values being DontCare.
383-
// `Index` encodes the bitmask of true values and is initially 0.
384-
MCDCRecord::TestVector TV(NumConditions, MCDCRecord::MCDC_DontCare);
385-
buildTestVector(TV, 1, 0);
386-
387496
// Using Profile Bitmap from runtime, mark the executed test vectors.
388-
findExecutedTestVectors();
497+
ExecVectors = MCDCTestVectorBuilder(Branches, Bitmap, BitmapIdx)
498+
.findExecutedTestVectors();
389499

390500
// Compare executed test vectors against each other to find an independence
391501
// pairs for each condition. This processing takes the most time.

‎llvm/test/tools/llvm-cov/mcdc-const.test

+14-14
Original file line numberDiff line numberDiff line change
@@ -61,8 +61,8 @@
6161
// CHECKFULLCASE: | C1-Pair: constant folded
6262
// CHECKFULLCASE-NEXT: | C2-Pair: not covered
6363
// CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00%
64-
// CHECKFULLCASE: | 1 { T, C = T }
65-
// CHECKFULLCASE-NEXT: | 2 { F, C = T }
64+
// CHECKFULLCASE: | 1 { F, C = T }
65+
// CHECKFULLCASE-NEXT: | 2 { T, C = T }
6666
// CHECKFULLCASE: | C1-Pair: not covered
6767
// CHECKFULLCASE-NEXT: | C2-Pair: constant folded
6868
// CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00%
@@ -106,8 +106,8 @@
106106
// CHECKFULLCASE-NEXT: | C2-Pair: not covered
107107
// CHECKFULLCASE-NEXT: | C3-Pair: not covered
108108
// CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00%
109-
// CHECKFULLCASE: | 1 { T, C, - = T }
110-
// CHECKFULLCASE-NEXT: | 2 { F, C, - = T }
109+
// CHECKFULLCASE: | 1 { F, C, - = T }
110+
// CHECKFULLCASE-NEXT: | 2 { T, C, - = T }
111111
// CHECKFULLCASE: | C1-Pair: not covered
112112
// CHECKFULLCASE-NEXT: | C2-Pair: constant folded
113113
// CHECKFULLCASE-NEXT: | C3-Pair: not covered
@@ -118,8 +118,8 @@
118118
// CHECKFULLCASE-NEXT: | C2-Pair: not covered
119119
// CHECKFULLCASE-NEXT: | C3-Pair: not covered
120120
// CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00%
121-
// CHECKFULLCASE: | 1 { T, C, - = T }
122-
// CHECKFULLCASE-NEXT: | 2 { F, C, T = T }
121+
// CHECKFULLCASE: | 1 { F, C, T = T }
122+
// CHECKFULLCASE-NEXT: | 2 { T, C, - = T }
123123
// CHECKFULLCASE: | C1-Pair: not covered
124124
// CHECKFULLCASE-NEXT: | C2-Pair: constant folded
125125
// CHECKFULLCASE-NEXT: | C3-Pair: not covered
@@ -151,26 +151,26 @@
151151
// CHECKFULLCASE-NEXT: | C2-Pair: constant folded
152152
// CHECKFULLCASE-NEXT: | C3-Pair: covered: (2,3)
153153
// CHECKFULLCASE: | MC/DC Coverage for Decision: 100.00%
154-
// CHECKFULLCASE: | 1 { T, -, C = T }
155-
// CHECKFULLCASE-NEXT: | 2 { F, T, C = T }
154+
// CHECKFULLCASE: | 1 { F, T, C = T }
155+
// CHECKFULLCASE-NEXT: | 2 { T, -, C = T }
156156
// CHECKFULLCASE: | C1-Pair: not covered
157157
// CHECKFULLCASE-NEXT: | C2-Pair: not covered
158158
// CHECKFULLCASE-NEXT: | C3-Pair: constant folded
159159
// CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00%
160-
// CHECKFULLCASE: | 1 { T, C, - = T }
161-
// CHECKFULLCASE-NEXT: | 2 { F, C, - = T }
160+
// CHECKFULLCASE: | 1 { F, C, - = T }
161+
// CHECKFULLCASE-NEXT: | 2 { T, C, - = T }
162162
// CHECKFULLCASE: | C1-Pair: not covered
163163
// CHECKFULLCASE-NEXT: | C2-Pair: constant folded
164164
// CHECKFULLCASE-NEXT: | C3-Pair: not covered
165165
// CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00%
166-
// CHECKFULLCASE: | 1 { T, -, C = T }
167-
// CHECKFULLCASE-NEXT: | 2 { F, T, C = T }
166+
// CHECKFULLCASE: | 1 { F, T, C = T }
167+
// CHECKFULLCASE-NEXT: | 2 { T, -, C = T }
168168
// CHECKFULLCASE: | C1-Pair: not covered
169169
// CHECKFULLCASE-NEXT: | C2-Pair: not covered
170170
// CHECKFULLCASE-NEXT: | C3-Pair: constant folded
171171
// CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00%
172-
// CHECKFULLCASE: | 1 { T, C, - = T }
173-
// CHECKFULLCASE-NEXT: | 2 { F, C, T = T }
172+
// CHECKFULLCASE: | 1 { F, C, T = T }
173+
// CHECKFULLCASE-NEXT: | 2 { T, C, - = T }
174174
// CHECKFULLCASE: | C1-Pair: not covered
175175
// CHECKFULLCASE-NEXT: | C2-Pair: constant folded
176176
// CHECKFULLCASE-NEXT: | C3-Pair: not covered

‎llvm/test/tools/llvm-cov/mcdc-general.test

+8-8
Original file line numberDiff line numberDiff line change
@@ -19,16 +19,16 @@
1919
// CHECK-NEXT: |
2020
// CHECK-NEXT: | C1, C2, C3, C4 Result
2121
// CHECK-NEXT: | 1 { F, -, F, - = F }
22-
// CHECK-NEXT: | 2 { T, F, F, - = F }
23-
// CHECK-NEXT: | 3 { F, -, T, F = F }
22+
// CHECK-NEXT: | 2 { F, -, T, F = F }
23+
// CHECK-NEXT: | 3 { T, F, F, - = F }
2424
// CHECK-NEXT: | 4 { T, F, T, F = F }
25-
// CHECK-NEXT: | 5 { T, T, -, - = T }
26-
// CHECK-NEXT: | 6 { T, F, T, T = T }
25+
// CHECK-NEXT: | 5 { T, F, T, T = T }
26+
// CHECK-NEXT: | 6 { T, T, -, - = T }
2727
// CHECK-NEXT: |
28-
// CHECK-NEXT: | C1-Pair: covered: (1,5)
29-
// CHECK-NEXT: | C2-Pair: covered: (2,5)
30-
// CHECK-NEXT: | C3-Pair: covered: (2,6)
31-
// CHECK-NEXT: | C4-Pair: covered: (4,6)
28+
// CHECK-NEXT: | C1-Pair: covered: (1,6)
29+
// CHECK-NEXT: | C2-Pair: covered: (3,6)
30+
// CHECK-NEXT: | C3-Pair: covered: (3,5)
31+
// CHECK-NEXT: | C4-Pair: covered: (4,5)
3232
// CHECK-NEXT: | MC/DC Coverage for Decision: 100.00%
3333
// CHECK-NEXT: |
3434
// CHECK-NEXT: ------------------

0 commit comments

Comments
 (0)