This is an archive of the discontinued LLVM Phabricator instance.

[clang][analyzer][ctu] Traverse the ctu CallEnter nodes in reverse order
AbandonedPublic

Authored by martong on Apr 14 2022, 5:00 AM.

Details

Summary

This change reverses the traverse order of those nodes that had been added to
the ctu worklist during the first phase of the analysis. By reversing the order
of these nodes, we start in the ctu phase with the nodes that are closer to the
root node. Measurements show that this way the length of the bug-paths are
decreasing with roughly by 10%.

Diff Detail

Event Timeline

martong created this revision.Apr 14 2022, 5:00 AM
Herald added a project: Restricted Project. · View Herald Transcript
martong requested review of this revision.Apr 14 2022, 5:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 14 2022, 5:00 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
steakhal added inline comments.Apr 19 2022, 2:30 AM
clang/lib/StaticAnalyzer/Core/WorkList.cpp
204–207

Please leave a note there, of what the negative values are used for.

216–218

It seems like you are not exploiting the signedness of this variable. And a counter should never be negative anyway.

255

Raw enum would make it more convenient, and the scope is already private - thus it won't affect readability elsewhere.

This approach fixes the worklist for the second phase. Would it be possible to create a wrapper that reverses the order of any worklist instead of committing to one and hardcode that?

This approach fixes the worklist for the second phase. Would it be possible to create a wrapper that reverses the order of any worklist instead of committing to one and hardcode that?

We don't want to reverse the worklist completely. We could reverse if we want to, by popping all elements and adding them to another queue which has the negated ordering function.

We'd like to have a reversed order only for those nodes that are added to the CTUWorklist during the first phase. In all other cases the normal ordering is the desired. Why? Because we'd like to keep the original algorithm once we are evaluating an inlined foreign function. The only thing we'd like to change is that which foreign function to choose for evaluation next. And we'd like that to be the one that is closer to the root node in the exploded graph (this way the overall path lengths can decrease).

Would it be possible to create a wrapper that reverses the order of any worklist instead of committing to one and hardcode that?

I don't think this is possible. I mean how could we reverse the DFS, would that be a BFS? The set of the visited nodes might change at the moment when we choose an other node as next. The only way it could work, if we first collect all the nodes that we want to visit. But the graph is being built as we do the visitation.

martong marked an inline comment as done.May 6 2022, 1:36 PM
martong added inline comments.
clang/lib/StaticAnalyzer/Core/WorkList.cpp
216–218

It is used in the descendant class.

martong abandoned this revision.May 17 2022, 6:29 AM
martong marked an inline comment as done.

Abandoning because by using a bool in ctuBifurcate, the CTUWorklist will not have more than one elements during the first phase. Details: https://reviews.llvm.org/D123773?id=426037#inline-1206493