This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Do not run visitors until the fixpoint, run only once
ClosedPublic

Authored by george.karpenkov on Jun 6 2018, 4:53 PM.

Details

Summary

In the current implementation, we run visitors until the fixed point is reached.
That is, if a visitor adds another visitor, the currently processed path is destroyed, all diagnostics is discarded, and it is regenerated again, until it's no longer modified.
This pattern has a few negative implications:

  • This loop does not even guarantee to terminate. E.g. just imagine two visitors bouncing a diagnostics around.
  • Performance-wise, e.g. for sqlite3 all visitors are being re-run at least 10 times for some bugs. We have already seen a few reports where it leads to timeouts.
  • If we want to add more computationally intense visitors, this will become worse
  • From architectural standpoint, the current layout requires copying visitors, which is conceptually wrong, and can be annoying (e.g. no unique_ptr on visitors allowed)

The proposed change is a much simpler architecture: the outer loop processes nodes upwards, and whenever the visitor is added it only processes current nodes and above, thus guaranteeing termination.

Diff Detail

Repository
rL LLVM

Event Timeline

Just a heads-up: FalsePositiveRefutationBRVisitor in BugReporterVisitors.h needs to be updated as well, as per the current master.

Fix the test crash associated with last piece of diagnostic.

Only let the visitors added initially (with the report generation) change the last piece.

Current problem: visitors are reused across different consumers, so the current code does not work for plist/html/etc, as the second invocation of the visitor will be incorrect (as state has changed by then).

Now the code *really* runs each visitor only once, even when multiple consumers are present.
5 tests still failing.

george.karpenkov retitled this revision from [analyzer] [WIP] Do not run visitors until the fixpoint, run only once to [analyzer] Do not run visitors until the fixpoint, run only once.
george.karpenkov edited the summary of this revision. (Show Details)

All tests are passing now. The diff is larger then necessary due to a few functions which I had to move around.

Rebased, minor cleanup.

Updated, another cleanup.

NoQ added inline comments.Jun 25 2018, 6:26 PM
clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h
477–481 ↗(On Diff #152815)

Maybe just remove the implementation?

clang/lib/StaticAnalyzer/Core/BugReporter.cpp
1884–1890 ↗(On Diff #152815)

I suggest:

This function is responsible for generating diagnostic pieces that are *not* provided by bug report visitors, once visitors populate VisitorsCache with their diagnostics for every node. These diagnostics may differ depending on the consumer's settings, and are therefore constructed separately for each consumer. Namely, there are two path diagnostics generation modes: ...

Then probably rename VisitorsCache to VisitorDiagnostics because it doesn't really act like a cache (i.e. we won't invoke the visitor if the diagnostic is missing in the cache).

george.karpenkov marked an inline comment as done.Jun 26 2018, 11:49 AM
george.karpenkov added inline comments.
clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h
477–481 ↗(On Diff #152815)

This cannot be done. BugReporter is actually not an abstract class, but a bug reporter class used for path-insenstive diagnostics.

NoQ accepted this revision.EditedJun 26 2018, 11:57 AM

Let's make BugReporter great again. One bug report at a time.

This revision is now accepted and ready to land.Jun 26 2018, 11:57 AM
This revision was automatically updated to reflect the committed changes.