Rebase

Hi @MaskRay do you have any more concerns?

Bail if the function has >1.5K blocks.

In D124490#4153293, @MaskRay wrote:

In BlockCoverageInference.cpp , for (auto &BB : F) { ... getReachableAvoiding is strictly quadratic and I think that may be problematic.
There are quite a few programs (e.g. Chisel genrerated C++) which contain functions with many basic blocks (say, >1000).
Also see D137184: a workaround for some programs with too many critical edges.

Applying a strict quadratic algorithm is a compile time pitfall. I understand that it may be fine for some mobile applications.
There are certainly other quadratic algorithms such as an O((V+E)*c) algorithm in GCC gcov (V: number of vertices; E: number of edges; c: number of elementary circuits),
an O(V^2) implementation of Semi-NCA algorithm.
For them, the quadratic time complexity is a theoretic upper bound which is really really difficult to achieve in practice (if ever achievable considering that in practice most CFGs are reducible).

Note that the optimality in the number of instrumented basic blocks is not required.
It does not necessarily lead to optimal performance since we have discarded execution count information.
Is it possible to use a faster algorithm which may instrument a few more basic blocks (let's arbitrarily say 1.2-approximation is good enough in practice)?

Use flood-fill algorithm to infer block coverage and rename some compiler-rt tests.

Just did another quick pass of this diff and I'll take a look at the other diffs soon.

Rebase, use the std::optional() API, and initialize region counters for cover instructions as well as increment instructions.

In D141579#4065615, @KuiChou wrote:

Thank you for the reviews! Could one of you commit this revision for me as I do not have commit access?

In D141579#4061009, @KuiChou wrote:

In D141579#4058984, @tejohnson wrote:

Thanks for adding a test, couple questions below, but generally lgtm.

In D141579#4057747, @KuiChou wrote:

In D141579#4047994, @ellis wrote:

Ah, I see the dyn_cast you are talking about is here. I think this is only a problem if InstrProfIncrementInstStep is the only InstrProf instruction in a function and it has an llvm.instrprof.value.profile instruction, which explains why we didn't catch this bug for so long. In that case, the later call to getOrCreateRegionCounters() will be skipped and, according to the comment, this is required for value profiling. Is that what you observed? If so it should be easy to add a small test case, probably similar to llvm/test/Instrumentation/InstrProfiling/early-exit.ll, but this could be followed up in another patch. Thanks for fixing!

Yes. But even if InstrProfIncrementInstStep is the only InstrProf instruction in a function, getOrCreateRegionCounters will still be called through InstrProfiling::run -> lowerIntrinsics -> lowerIncrement -> getCounterAddress -> getOrCreateRegionCounters. So, to reproduce this problem, we should satisfy two conditions:

1. InstrProfIncrementInstStep is the only InstrProf instruction in a function and it has InstrProfValueProfileInst instruction

I assume this should be "is the only InstrProfIncrement instruction" (since there is another InstrProf instruction in the function (InstrProfValueProfileInst)?

2. InstrProfValueProfileInst must be in front of InstrProfIncrementInstStep instruction

PGO will always generate an InstrProfIncrementInst instruction in the front of a function so normally, this bug cannot happen

Out of curiosity, how was this encountered?

1. Yes, you are right. It should be "InstrProfIncrementInstStep is the only InstrProfIncrement instruction in a function and it has InstrProfValueProfileInst instruction"
2. I have been trying to implement function reordering in LLVM PGO which will modify current PGO code, this cause a bug in my code.

In D141579#4048018, @tejohnson wrote:

In D141579#4047994, @ellis wrote:

Ah, I see the dyn_cast you are talking about is here. I think this is only a problem if InstrProfIncrementInstStep is the only InstrProf instruction in a function and it has an llvm.instrprof.value.profile instruction, which explains why we didn't catch this bug for so long. In that case, the later call to getOrCreateRegionCounters() will be skipped and, according to the comment, this is required for value profiling. Is that what you observed? If so it should be easy to add a small test case, probably similar to llvm/test/Instrumentation/InstrProfiling/early-exit.ll, but this could be followed up in another patch. Thanks for fixing!

Why not include the suggested test in this patch?

Ah, I see the dyn_cast you are talking about is here. I think this is only a problem if InstrProfIncrementInstStep is the only InstrProf instruction in a function and it has an llvm.instrprof.value.profile instruction, which explains why we didn't catch this bug for so long. In that case, the later call to getOrCreateRegionCounters() will be skipped and, according to the comment, this is required for value profiling. Is that what you observed? If so it should be easy to add a small test case, probably similar to llvm/test/Instrumentation/InstrProfiling/early-exit.ll, but this could be followed up in another patch. Thanks for fixing!

Rebase.

In D138846#3958331, @alanphipps wrote:

Hi @ellis, thank you for looking at this deeper! I'll update based on your comments below, but I want to respond to your primary question first:

Please correct me if I'm wrong, but my understanding is that we have a single bitvector per expression (or function?) to track coverage. And that these bitvectors are at most 64 bits long. Is the number of these bitvectors per function known at compile time? I think yes because you are allocating the IPSK_bitmap section at compile time.

Yes, a bitvector (or bitmap) is allocated per expression for each function, and this is known at compile time. Each one can be at minimum 8 bits and 64bits max, although the max value could be extended in the future.

If this is the case then I would suggest extending the IPSK_cnts rather than creating a new IPSK_bitmap section. There is lots of logic to track the location of the IPSK_cnts and correlate its values to the correct functions (this is the main feature of Debug Info Correlation). Instead, we could allocate more data for function counters and say the last N bytes are for the MC/DC bitvectors. The lowered code would know where to write the data because they are given the address and the raw profile readers would know when to expect this data at the end of the counters because they know N.

I totally understand the desire to avoid modifying the raw header and the additional complexity, and so I'm glad you honed in on it so we could explore how best to simplify this.

I did consider extending IPSK_cnts, and what you describe ought to work functionally just fine, but the reason I opted not to do that was because of considerations for efficient memory utilization at link time (I expect MC/DC will be getting the most utilization for embedded, where this is most important). With the alignment of IPSK_cnts being driven by the size of the counters (up to 64bits, as you know, and for good reason), even 1 byte of additional MC/DC data at the end of a function's IPSK_cnts would yield large gaps during linker aggregation of these sections across functions due to alignment constraints. With one of the goals behind MC/DC being to avoid unnecessary memory consumption, it didn't make sense philosophically to have anything related to memory efficient bitmap bits be impacted by the alignment and size of the counters, which, at least conceptually, is an altogether different thing. Keeping the bitmaps in a separate, 1-byte aligned section IPSK_bits yields the most granularity and flexibility. I tried to abstract a lot of the overlap for how the sections are created as much as possible.

With respect to modifying the raw header, I agree there is reluctance to changing this, and if there is a way to derive the needed information without having to do this, I would definitely consider it.

Please correct me if I'm wrong, but my understanding is that we have a single bitvector per expression (or function?) to track coverage. And that these bitvectors are at most 64 bits long. Is the number of these bitvectors per function known at compile time? I think yes because you are allocating the IPSK_bitmap section at compile time.

Seems good to me! I just have some minor nits.

Rebase.

Seems fine to me!

Friendly ping :)

Can we get another review of this? CC @MaskRay

Rebase and add comment discussing the runtime.

Rename OFormat to SFormat.

Sorry, forgot to run clang-format

Rebase

Rebase

In D135237#3840909, @aeubanks wrote:

sorry to be late to reviewing this, but I think this is overly aggressive. I see verifier failures like scope must have two or three operands after this patch.

https://reviews.llvm.org/D132077 was in the process of being reviewed and basically does this but more targeted with a specific focus on not creating verifier failures (since that's the direction we'd like to take llvm-reduce, not producing verifier failures since that slows down reduction a lot and dumps a lot of output). could we revert this and use the other patch?

I decided to just stick with --output-format=<json|yaml> and removed changes to the --text option to make things cleaner.

Rebase.

Don't add text and text-encoding to output-format type.

Remove extra {{ }} in tests

fix whitespace

In D135127#3835933, @davidxl wrote:

2. what is the use case of splitting text and text-encoding?

Move test to DebugInfo/Generic and add checks to verify dwarfdump output.

Add the "Probes" key to Yaml output so that we can add more keys in the future. Also add D135127 as a parent diff to use the --output-format=yaml option.

I like the idea of --output-format=yaml since it easily allows us to preserve the original behavior. I'll add this in another diff and update this.

Add link to paper

Fix warning with Optional<BlockCoverageInference>

Rebase

In D132094#3750842, @gulfem wrote:

In D132094#3733666, @ellis wrote:

When using the -fprofile-function-groups option we could hit the case where one of the groups has no profiled functions. In that case it would be more surprising to not find a raw profile, rather than an empty raw profile. If we do go with option 1, maybe we could emit a warning explaining why no profile was emitted. Or if we go with option 2, maybe a warning would also be good to alert the user that it's an empty profile.

What kind of warning do you have in mind @ellis? Are you suggesting to put some text like Empty Profile when we read a profile via llvm-profdata show (which happens to contain only a header)?

Oops, this actually breaks a test and I need to think about this more. Closing.