This is an archive of the discontinued LLVM Phabricator instance.

Disable postdominator coverage optimizations
AbandonedPublic

Authored by george.karpenkov on May 22 2017, 6:21 PM.

Details

Reviewers
kcc
Summary

Coverage instrumentation has an optimization not to instrument extra blocks, if the pass is already "accounted for" by a successor/predecessor basic block.
Two cases are considered: full-post-dominators and post-dominators are not instrumented, as in those cases the instrumentation is applied to the nodes predecessors/successors respectively.
However (https://github.com/google/sanitizers/issues/783) unfortunately this reasoning may become circular, which stops valid paths from having coverage.
In worst case this can block fuzzing entirely.

I propose to have for now a simpler optimization which will not apply the optimization to full post-dominators. Then the logic is trivially sound, and losing valid paths does not seem like a good trade-off for a ~15% decrease in the # of optimized nodes.

Diff Detail

Event Timeline

Is it possible to add a regression test that demonstrates the IR pattern this diff is fixing?

Updated tests: without this patch, the left branch of the test is not instrumented at all.

LGTM. Thank you!

kcc accepted this revision.May 23 2017, 2:34 PM

LGTM with a nit. Thanks!

test/Instrumentation/SanitizerCoverage/chains.ll
1 ↗(On Diff #99994)

do you need --check-prefix here (CHECK is the default)

This revision is now accepted and ready to land.May 23 2017, 2:34 PM

@kcc embarrassingly, I have forgotten about tests.
https://reviews.llvm.org/rL303701 should have been added to review.
We do insert extra unneeded instrumentation for last nodes in diamond patterns: e.g. for

   A
 /   \
B     C
 \   /
   D

we have that B and C are not full-dominators, are instrumented, and therefore D should not be instrumented.

Yet for

     A
   /   \
  B     C
 /       \
D         E

blocks B and C are full-dominators, and therefore D and E should be instrumented.
I am not sure of the best way to distinguish one situation from the other
(apart from having a post-processing path, which goes through all blocks, and disables instrumentation if all parents are instrumented).

@kcc what about the following hard'n fast rule: do not instrument basic blocks which have no successors, but have multiple predecessors.
If the block has multiple predecessors, they can not be full-dominators by definition, and therefore should have coverage.

kcc added a comment.May 23 2017, 4:30 PM

@kcc what about the following hard'n fast rule: do not instrument basic blocks which have no successors, but have multiple predecessors.

This will solve only the simplest of the cases and only make things more confusing.

If the block has multiple predecessors, they can not be full-dominators by definition, and therefore should have coverage.

@kcc it has a nice property that tests remain the same. Actually, do you have examples for cases which the new instrumentation misses?

kcc added a comment.May 23 2017, 4:35 PM

@kcc it has a nice property that tests remain the same.

Weak reason. As I said: this will only increase the confusion.
The tests will look as we are doing something reasonable, while in fact we are doing something simple to please the existing tests.

Actually, do you have examples for cases which the new instrumentation misses?

You could get such examples somewhat easily by comparing the results with the optimization using PDOM.

@kcc yes, but by looking @ 100k LOC examples I do not understand anything, and I can not actually find counterexamples on small pen-and-paper ones.

george.karpenkov abandoned this revision.May 24 2017, 11:15 AM

Abandoned in favor of D33511