[Coverage] Speed up function record iteration (#122050)

When iterating over function records, filtered by file name, currently,
the iteration goes over all the function records, repeatedly for each

[Coverage] Speed up function record iteration (#122050)

When iterating over function records, filtered by file name, currently,
the iteration goes over all the function records, repeatedly for each
source file, essentially giving quadratic behavior.

413647d730972eac9675f695c2ea63fb393a5531 sped up some cases by keeping
track of the indices of the function records corresponding to each file
name. This change expands the use of that map to FunctionRecordIterator.

On a test case with Firefox's libxul.so and a 2.5MB profile, this brings
down the runtime of `llvm-cov export $lib --instr-profile $prof -t lcov`
from 12 minutes with 90% spent in skipOtherFiles to 19 seconds with no
samples in skipOtherFiles at all under a sampling profiler (with a
sampling interval of 1ms).

Fixes #62079

show more ...

Introduce CounterExpressionBuilder::subst(C, Map) (#112698)

This return a counter for each term in the expression replaced by
ReplaceMap.

At the moment, this doesn't update the Map, so Map is marke

Introduce CounterExpressionBuilder::subst(C, Map) (#112698)

This return a counter for each term in the expression replaced by
ReplaceMap.

At the moment, this doesn't update the Map, so Map is marked as `const`.

show more ...

[Coverage] MCDC: Move findIndependencePairs deferred into MCDCRecord (#121188)

The result of "Independence pairs" is not mergeable. This change makes
defers re-calculation of "Independence pairs" af

[Coverage] MCDC: Move findIndependencePairs deferred into MCDCRecord (#121188)

The result of "Independence pairs" is not mergeable. This change makes
defers re-calculation of "Independence pairs" after merging test
vectors.

No apparent behavior changes.

show more ...

[Coverage] Make `MCDCRecord::Folded` as `[false/true]` with BitVector. NFC. (#121190)

For merging `MCDCRecord`s, `Folded` is expected to be promoted as
"Non-folded".

[Coverage] Move SingleByteCoverage out of CountedRegion (#110966)

`SingleByteCoverage` is not per-region attribute at least.
Move it into `CoverageData` since it comes from `profdata`.

Depends o

[Coverage] Move SingleByteCoverage out of CountedRegion (#110966)

`SingleByteCoverage` is not per-region attribute at least.
Move it into `CoverageData` since it comes from `profdata`.

Depends on: #120841

show more ...

Introduce CounterMappingRegion::isBranch(). NFC.

Make MCDCRecord::getNumConditions() `const&`

Some users were trying to get a reference to the return value.

[Coverage] Introduce "partial fold" on BranchRegion (#112694)

Currently both True/False counts were folded. It lost the information,
"It is True or False before folding." It prevented recalling bra

[Coverage] Introduce "partial fold" on BranchRegion (#112694)

Currently both True/False counts were folded. It lost the information,
"It is True or False before folding." It prevented recalling branch
counts in merging template instantiations.

In `llvm-cov`, a folded branch is shown as:

- `[True: n, Folded]`
- `[Folded, False n]`

In the case If `n` is zero, a branch is reported as "uncovered". This is
distinguished from "folded" branch. When folded branches are merged,
`Folded` may be dissolved.

In the coverage map, either `Counter` is `Zero`. Currently both were
`Zero`.

Since "partial fold" has been introduced, either case in `switch` is
omitted as `Folded`.

Each `case:` in `switch` is reported as `[True: n, Folded]`, since
`False` count doesn't show meaningful value.

When `switch` doesn't have `default:`, `switch (Cond)` is reported as
`[Folded, False: n]`, since `True` count was just the sum of `case`(s).
`switch` with `default` can be considered as "the statement that doesn't
have any `False`(s)".

show more ...

[LLVM] Use {} instead of std::nullopt to initialize empty ArrayRef (#109133)

It is almost always simpler to use {} instead of std::nullopt to
initialize an empty ArrayRef. This patch changes all oc

[LLVM] Use {} instead of std::nullopt to initialize empty ArrayRef (#109133)

It is almost always simpler to use {} instead of std::nullopt to
initialize an empty ArrayRef. This patch changes all occurrences I could
find in LLVM itself. In future the ArrayRef(std::nullopt_t) constructor
could be deprecated or removed.

show more ...

Reapply: [MC/DC][Coverage] Loosen the limit of NumConds from 6 (#82448)

By storing possible test vectors instead of combinations of conditions,
the restriction is dramatically relaxed.

This introdu

Reapply: [MC/DC][Coverage] Loosen the limit of NumConds from 6 (#82448)

By storing possible test vectors instead of combinations of conditions,
the restriction is dramatically relaxed.

This introduces two options to `cc1`:

* `-fmcdc-max-conditions=32767`
* `-fmcdc-max-test-vectors=2147483646`

This change makes coverage mapping, profraw, and profdata incompatible
with Clang-18.

- Bitmap semantics changed. It is incompatible with previous format.
- `BitmapIdx` in `Decision` points to the end of the bitmap.
- Bitmap is packed per function.
- `llvm-cov` can understand `profdata` generated by `llvm-profdata-18`.

RFC:
https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798

--
Change(s) since llvmorg-19-init-14288-g7ead2d8c7e91

- Update compiler-rt/test/profile/ContinuousSyncMode/image-with-mcdc.c

show more ...

Revert "[MC/DC][Coverage] Loosen the limit of NumConds from 6 (#82448)"

This broke the lit tests on Mac:
https://green.lab.llvm.org/job/llvm.org/job/clang-stage1-RA/1096/

> By storing possible test

Revert "[MC/DC][Coverage] Loosen the limit of NumConds from 6 (#82448)"

This broke the lit tests on Mac:
https://green.lab.llvm.org/job/llvm.org/job/clang-stage1-RA/1096/

> By storing possible test vectors instead of combinations of conditions,
> the restriction is dramatically relaxed.
>
> This introduces two options to `cc1`:
>
> * `-fmcdc-max-conditions=32767`
> * `-fmcdc-max-test-vectors=2147483646`
>
> This change makes coverage mapping, profraw, and profdata incompatible
> with Clang-18.
>
> - Bitmap semantics changed. It is incompatible with previous format.
> - `BitmapIdx` in `Decision` points to the end of the bitmap.
> - Bitmap is packed per function.
> - `llvm-cov` can understand `profdata` generated by `llvm-profdata-18`.
>
> RFC:
> https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798

This reverts commit 7ead2d8c7e9114b3f23666209a1654939987cb30.

show more ...

[MC/DC][Coverage] Loosen the limit of NumConds from 6 (#82448)

By storing possible test vectors instead of combinations of conditions,
the restriction is dramatically relaxed.

This introduces tw

[MC/DC][Coverage] Loosen the limit of NumConds from 6 (#82448)

By storing possible test vectors instead of combinations of conditions,
the restriction is dramatically relaxed.

This introduces two options to `cc1`:

* `-fmcdc-max-conditions=32767`
* `-fmcdc-max-test-vectors=2147483646`

This change makes coverage mapping, profraw, and profdata incompatible
with Clang-18.

- Bitmap semantics changed. It is incompatible with previous format.
- `BitmapIdx` in `Decision` points to the end of the bitmap.
- Bitmap is packed per function.
- `llvm-cov` can understand `profdata` generated by `llvm-profdata-18`.

RFC:
https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798

show more ...

Cleanup asserts in BranchParameters and DecisionParameters

[MC/DC] Introduce `class TestVector` with a pair of `BitVector` (#82174)

This replaces `SmallVector<CondState>` and emulates it.

- -------- True False DontCare
- Values: True False False
- V

[MC/DC] Introduce `class TestVector` with a pair of `BitVector` (#82174)

This replaces `SmallVector<CondState>` and emulates it.

- -------- True False DontCare
- Values: True False False
- Visited: True True False

`findIndependencePairs()` can be optimized with logical ops.

FIXME: Specialize `findIndependencePairs()` for the single word.

show more ...

[MC/DC] Refactor: Isolate the final result out of TestVector (#82282)

To reduce conditional judges in the loop in `findIndependencePairs()`, I
have tried a couple of tweaks.

* Isolate the final

[MC/DC] Refactor: Isolate the final result out of TestVector (#82282)

To reduce conditional judges in the loop in `findIndependencePairs()`, I
have tried a couple of tweaks.

* Isolate the final result in `TestVectors`

`using TestVectors = llvm::SmallVector<std::pair<TestVector,
CondState>>;`
The final result was just piggybacked on `TestVector`, so it has been
isolated.

* Filter out and sort `ExecVectors` by the final result

It will cost more in constructing `ExecVectors`, but it can reduce at
least one conditional judgement in the loop.

show more ...

[InstrProf] Single byte counters in coverage (#75425)

This patch inserts 1-byte counters instead of an 8-byte counters into
llvm profiles for source-based code coverage. The origial idea was
propo

[InstrProf] Single byte counters in coverage (#75425)

This patch inserts 1-byte counters instead of an 8-byte counters into
llvm profiles for source-based code coverage. The origial idea was
proposed as block-cov for PGO, and this patch repurposes that idea for
coverage: https://groups.google.com/g/llvm-dev/c/r03Z6JoN7d4

The current 8-byte counters mechanism add counters to minimal regions,
and infer the counters in the remaining regions via adding or
subtracting counters. For example, it infers the counter in the if.else
region by subtracting the counters between if.entry and if.then regions
in an if statement. Whenever there is a control-flow merge, it adds the
counters from all the incoming regions. However, we are not going to be
able to infer counters by subtracting two execution counts when using
single-byte counters. Therefore, this patch conservatively inserts
additional counters for the cases where we need to add or subtract
counters.

RFC:
https://discourse.llvm.org/t/rfc-single-byte-counters-for-source-based-code-coverage/75685

show more ...

Introduce mcdc::TVIdxBuilder (LLVM side, NFC) (#80676)

This is a preparation of incoming Clang changes (#82448) and just checks
`TVIdx` is calculated correctly. NFC.

`TVIdxBuilder` calculates de

Introduce mcdc::TVIdxBuilder (LLVM side, NFC) (#80676)

This is a preparation of incoming Clang changes (#82448) and just checks
`TVIdx` is calculated correctly. NFC.

`TVIdxBuilder` calculates deterministic Indices for each Condition Node.
It is used for `clang` to emit `TestVector` indices (aka ID) and for
`llvm-cov` to reconstruct `TestVectors`.

This includes the unittest `CoverageMappingTest.TVIdxBuilder`.

See also
https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798

show more ...

CoverageMapping: Move `getParams<InnerParamTy>(MCDCParams)` into `mcdc::`

Fixup for #81227

[MC/DC] Refactor: Introduce `ConditionIDs` as `std::array<2>` (#81221)

Its 0th element corresponds to `FalseID` and 1st to `TrueID`.

CoverageMappingGen.cpp: `DecisionIDPair` is replaced with `Con

[MC/DC] Refactor: Introduce `ConditionIDs` as `std::array<2>` (#81221)

Its 0th element corresponds to `FalseID` and 1st to `TrueID`.

CoverageMappingGen.cpp: `DecisionIDPair` is replaced with `ConditionIDs`

show more ...

[MC/DC] Refactor: Make `MCDCParams` as `std::variant` (#81227)

Introduce `mcdc::DecisionParameters` and `mcdc::BranchParameters` and make
sure them not initialized as zero.

FIXME: Could we make

[MC/DC] Refactor: Make `MCDCParams` as `std::variant` (#81227)

Introduce `mcdc::DecisionParameters` and `mcdc::BranchParameters` and make
sure them not initialized as zero.

FIXME: Could we make `CoverageMappingRegion` as a smart tagged union?

show more ...

CoverageMapping.cpp: Apply std::move to MCDCRecord (#81220)

[MC/DC] Refactor: Introduce `MCDCTypes.h` for `coverage::mcdc` (#81459)

They can be also used in `clang`.
Introduce the lightweight header instead of `CoverageMapping.h`.

This includes for now:

[MC/DC] Refactor: Introduce `MCDCTypes.h` for `coverage::mcdc` (#81459)

They can be also used in `clang`.
Introduce the lightweight header instead of `CoverageMapping.h`.

This includes for now:
* `mcdc::ConditionID`
* `mcdc::Parameters`

show more ...

[Coverage] ProfileData: Handle MC/DC Bitmap as BitVector. NFC. (#80608)

* `getFunctionBitmap()` stores not `std::vector<uint8_t>` but
`BitVector`.
* `CounterMappingContext` holds `Bitmap` (instead

[Coverage] ProfileData: Handle MC/DC Bitmap as BitVector. NFC. (#80608)

* `getFunctionBitmap()` stores not `std::vector<uint8_t>` but
`BitVector`.
* `CounterMappingContext` holds `Bitmap` (instead of the ref of bytes)
* `Bitmap` and `BitmapIdx` are used instead of `evaluateBitmap()`.

FIXME: `InstrProfRecord` itself should handle `Bitmap` as `BitVector`.

show more ...

[Coverage] Const-ize `MCDCRecordProcessor` stuff (#78918)

The life of `MCDCRecordProcessor`'s instance is short. It may accept
`const` objects to process.

On the other hand, the life of `MCDCBra

[Coverage] Const-ize `MCDCRecordProcessor` stuff (#78918)

The life of `MCDCRecordProcessor`'s instance is short. It may accept
`const` objects to process.

On the other hand, the life of `MCDCBranches` is shorter than `Record`.
It may be rewritten with reference, rather than copying.

show more ...

[Profile][CoverageMapping] MC/DC Fix passing FileID for DecisionRegion

Fixes oversight in commit 8ecbb0404d740d1ab173554e47cef39cd5e3ef8c in which
FileID was not being set when creating a new MC/DC

[Profile][CoverageMapping] MC/DC Fix passing FileID for DecisionRegion

Fixes oversight in commit 8ecbb0404d740d1ab173554e47cef39cd5e3ef8c in which
FileID was not being set when creating a new MC/DC DecisionRegion.

show more ...