This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Exploration strategy prioritizing unexplored coverage first
ClosedPublic

Authored by george.karpenkov on Jan 31 2018, 5:54 PM.

Diff Detail

Event Timeline

MTC added a subscriber: MTC.Feb 1 2018, 10:53 PM
george.karpenkov edited the summary of this revision. (Show Details)

Switching to CFGBlocks made # of bug reports / % coverage slightly worse compared to the version using Stmt *, I am still confused as to why.
Removing StackFrameContext* from location identifier makes everything considerably worse.

@NoQ I think this version can go in.

NoQ added a comment.Feb 2 2018, 5:10 PM

I think you should add a test with foo() in else-branch as well, which has always passed, just to demonstrate that regardless of accidental if-branch analysis order we're doing the right thing.

NoQ added a comment.Feb 2 2018, 5:18 PM

More minor nits, but yeah, this is great :)

lib/StaticAnalyzer/Core/CoreEngine.cpp
137

Does this invariant keep holding after we put the node here? Like, what if it wasn't traversed when we were putting it here, but while it's in the stack we've traversed it on a different path?

Suggests: NormalPriorityStack, LowPriorityStack. Explaining that the latter contains beginnings of paths that were down-prioritized because they lead into blocks that we've already visited in this function.

145

Capitalize?

157

Essentially we assume that we made the right choice on the block edge and the node is now being explored for a good reason, and now that we went down this path, there's no need to downprioritize other elements in this block.

lib/StaticAnalyzer/Core/CoreEngine.cpp
137

Like, what if it wasn't traversed when we were putting it here, but while it's in the stack we've traversed it on a different path?

Surprisingly, it does: the key here is that we check exploration at the push-time, not at the pop-time. That is, the block is added to "reachable" not when we explore it, but when we put the corresponding node into queue.
Thus it's not possible for the node in stackUnexplored to become explored via some other path.

george.karpenkov marked 2 inline comments as done.
NoQ accepted this revision.Feb 7 2018, 6:26 PM

All right, so for now it is under the flag (-analyzer-config exploration_strategy=unexplored_first), it already makes a huge lot of sense, and it has tests, so i think we should land it now and flip the flag when we're ready.

It'd be great to have more direct tests for the exploration order, not just for the bugs. Probably dump CFG blocks in the traversal order, or even dump whole worklist snapshots for every analysis step - the latter seemed very useful while understanding the issue (we did it on the whiteboard, but i've no idea how huge would it be in practice, even if we still dump only CFG blocks of worklist units), because, as the original issue has demonstrated, even our simple DFS exploration may be completely counter-intuitive sometimes.

This revision is now accepted and ready to land.Feb 7 2018, 6:26 PM

@NoQ

but i've no idea how huge would it be in practice

It's actually pretty small if we only do it for BlockEntrance edges.
Do you have any concrete ideas on how such dumping could be done? I could debug it by printing to llvm::errs(), but that's obviously not optimal.
I could use DEBUG(), but that's hacky, fragile, and would not even work in release builds.
I don't think I have good ideas left.

This revision was automatically updated to reflect the committed changes.