This is an archive of the discontinued LLVM Phabricator instance.

[RFC][StaticAnalyser] fix unreachable code false positives when block numbers mismatch
ClosedPublic

Authored by danielmarjamaki on Sep 20 2016, 5:53 AM.

Details

Summary

This is a RFC mostly.

There are false positives from the unreachable code check when the block numbers in the ExplodedGraph and CFG mismatch.

If it should be allowed that they mismatch then this patch can handle such situations.

If the block numbers should match, then I'll investigate why they mismatch. Is it guaranteed what block numbers there will be for the CFG blocks for such code:

void test12(int x) {
  switch (x) {
  case 1:
    break;
  case 2:
    do { } while (0);
    break;
  }
}

If so.. what is the correct block numbers?

Diff Detail

Event Timeline

danielmarjamaki retitled this revision from to [RFC][StaticAnalyser] fix unreachable code false positives when block numbers mismatch.
danielmarjamaki updated this object.
danielmarjamaki added subscribers: zaks.anna, a.sidorin, NoQ and 2 others.

Sorry, I do not understand the question. What are block numbers?

@danielmarjamaki I see what you mean -- thanks for providing the patch.

I don't think this is the right approach. It should be sufficient to reason about blocks and not individual statements; further some blocks may be non-empty but not have any statements.

Instead, I think the better approach is make sure the optimized and unoptimized CFGs match block IDs. It looks like the only situation where there is currently a mismatch is do { } while (0);.

I sketched out an approach on cfe-dev for hoisting block creation (but not edge creation) in CFGBuilder::VisitDoStmt() during CFG construction to match the other control flow constructs. That is the approach I would recommend taking.

Here is the discussion on cfe-dev. http://lists.llvm.org/pipermail/cfe-dev/2016-September/050800.html

What's going on is that the path-sensitive unreachable code checker traverses blocks in the unoptimized CFG and emits a diagnostic if a block in that CFG is not reachable. But it decides whether a block is reachable by using the exploded node graph, which itself refers to the *optimized* CFG.

Normally this isn't a problem because the difference between the unoptimized and optimized CFGs is that the latter prunes edges that are trivially false (but the two CFGs have the same blocks). Unfortunately, there is a bug in CFG construction for do-while loops that also prunes a block. Since the block ids are constructed sequentially, the block IDs between the two CFGs don't match up and so the unreachable code checker gets confused.

I think the best fix here is to change construction of the optimized CFG to not prune the block in VisitDoStmt(). This matches what I think is the expected meaning of the 'PruneTriviallyFalseEdges' CFG option.

Thanks!

I somehow missed your answer in cfe-dev.

I will continue working on this and hopefully have a proper patch soon.

Updated CFGBuilder::VisitDoStmt

My change is causing a false negative in the test/Analysis/uninit-sometimes.cpp. As far as I see my change anyway makes the unoptimized CFG better.

dcoughlin requested changes to this revision.Sep 23 2016, 7:22 AM
dcoughlin added a reviewer: dcoughlin.
dcoughlin added inline comments.
lib/Analysis/CFG.cpp
2986 ↗(On Diff #72252)

You need to keep this check so that the optimized CFG still removes edges that are trivially known to be false.

2994 ↗(On Diff #72252)

To keep the unoptimized and optimized blocks in sync, this block creation needs to be done regardless of whether the branch condition is known to be false. My advice would be to hoist the creation (and the FIXME comments) to above the check for whether KnownVal is false.

This revision now requires changes to proceed.Sep 23 2016, 7:22 AM
danielmarjamaki edited edge metadata.
danielmarjamaki marked 2 inline comments as done.

Fixed review comments by Devin. It works better now!

lib/Analysis/CFG.cpp
2986 ↗(On Diff #72252)

Thanks

2994 ↗(On Diff #72252)

Thanks

dcoughlin accepted this revision.Sep 30 2016, 11:34 AM
dcoughlin edited edge metadata.

LGTM. Please commit!

This revision is now accepted and ready to land.Sep 30 2016, 11:34 AM