This is an archive of the discontinued LLVM Phabricator instance.

Fix coverage optimization
ClosedPublic

Authored by george.karpenkov on May 24 2017, 11:14 AM.

Details

Summary

Coverage instrumentation which does not instrument full post-dominators and full-dominators may skip valid paths, as the reasoning for skipping blocks may become circular.
This patch fixes that, by only skipping full post-dominators with multiple predecessors, as such predecessors by definition can not be full-dominators.

Diff Detail

Event Timeline

@kcc any pro tips on what tests are likely to be affected? I'm currently running check-all, but this is somewhat time consuming.

Also, multiple edges (A, E1, B), (A, E2, B) are not possible as resulting edges are critical and will be split by coverage preprocessing.

kcc edited edge metadata.May 24 2017, 6:12 PM

LGTM with a nit

I usually run

ninja check-llvm check-clang check-sanitizer check-asan check-tsan check-msan check-lsan check-ubsan check-dfsan

(since indeed, check-all is often much slower than the above, and contains failures I don't want to see)

Note that some of the coverage-related tests are linux only (disabled on mac for historical reasons. I guess some of them could be enabled now in a separate patch)

BTW: Thanks!

test/Instrumentation/SanitizerCoverage/postdominator_check.ll
1

Please also add a second set of CHECKs and a RUN with pruning turned off.

george.karpenkov accepted this revision.May 24 2017, 6:56 PM
This revision is now accepted and ready to land.May 24 2017, 6:56 PM

@kcc BTW I find the logic in this function very hard to read, I think it would be more readable if we invert it (use shouldSkipBlock, and invert all statements).
Complicated NOTs would be gone, and last statement would be simply (isFullDominator || isFullPostDominator && getSingleSuccessor(BB)).

kcc added a comment.May 24 2017, 7:05 PM

No objections.
Just remember to not mix refactoring/NFC patches and actual changes in logic.

george.karpenkov reopened this revision.May 30 2017, 3:48 PM

@kcc just thought again about this:
isn't trivially optimal and correct coverage instrumentation is instead "instrument node IFF parent has more than one outgoing edge" (+ usual logic on always instrumenting function entry points, and not instrumenting unreachable code)?
Soundness: LLVM bytecode is deterministic, so for any set of instructions without branches it is sufficient to instrument only a single top-level instruction (which is a func entry point, or a block just after the branch).
Optimality: after each branching block, at least one instruction in each branch needs to be instrumented (generalizable by induction to nested branches).

This revision is now accepted and ready to land.May 30 2017, 3:48 PM
kcc added a comment.May 30 2017, 3:49 PM

dunno :) / :(