[analyzer] Support for naive cross translational unit analysis
AbandonedPublic

Authored by xazax.hun on Mar 7 2017, 4:47 AM.

Details

Summary

This patch adds support for naive cross translational unit analysis.

The aim of this patch is to be minimal to enable incremental development of the feature on the top of the tree. This patch should be an NFC in case CTUDir is not provided by the user.

When CTUDir is provided:

  • In case a function definition is not available it will be looked up from a textual index, whether it was available in another TU.
  • The AST dump of the other TU will be loaded and the function definition will be inlined.

One of the main limitations is that the coverage pattern of the analysis will change when this feature is enabled. For this reason, in the future, it might be better to include some heuristics to prefer examining shorter execution paths to the longer ones. Until then this feature is not recommended to be turned on by users unless they already fixed the important issues with this feature turned off.

We will cover more detailed analysis of this patch soon in our EuroLLVM talk: http://llvm.org/devmtg/2017-03//2017/02/20/accepted-sessions.html#7
We will talk about how this works and the memory usage, analysis time, coverage pattern change, limitations of the ASTImporter, how the length of the bug paths changed and a lot more.

Feel free to skip the review after the talk, but we wanted to make the code available in an easy to review format before the conference.

Note that the initial prototype was done by A. Sidorin et al.: http://lists.llvm.org/pipermail/cfe-dev/2015-October/045730.html

Contributions to the measurements and the new version of the code: Peter Szecsi, Zoltan Gera, Daniel Krupp, Kareem Khazem.

Diff Detail

Repository
rC Clang
There are a very large number of changes, so older changes are hidden. Show Older Changes
gerazo added inline comments.Dec 6 2017, 7:17 AM
tools/scan-build-py/libscanbuild/analyze.py
146

The reason for the previous is that we need to count the occurence number ofdifferent mappings only let those pass through which don't have multiple variations.

190

Finally, I came to the conclusion that mkdtemp would not be better than the current solution. In order to find our created dir by other threads, we need a designated name. Suffixing it by generated name would further complicate things as we need not to allow multiple concurrent runs here. The current solution is more robust from this point of view.

243

I've checked it through. The only place for an early exit now would be before the else. The 1st and 2nd ifs are in fact non-orthogonal.

255

Th previous call for data removal happens because the user asked for a collect run, so we clean data to do a recollection. This second one happens because the user asked for a full recollection and anaylsis run all in one. So here we destroy the temp data for user's convenience. This happens after, not before like previously. The default behavior is to do this when the user uses the tool the easy way (collect and analyze all in one) and we intentionally keep collection data if the user only asks for a collect or an analyze run. So with this, the user can use a collect run's results for multiple analyze runs. This is written in the command line help. I will definitely put comments here to explain.

319

There is an other thing against changing this. Currently the interface here using env variables is used by intercept-build, analyze-build and scan-build tool as well. In order to drop json, we need to change those tools too. It would be a separate patch definitely.

584

Here the folders are created on demand. Because these are created parallel by multiple processes, there is small chance that an other process already created the folder between the isdir check and the makedirs call. This is why the the pass is needed to make it always run correctly. I will add a comment.

590

After several iterations of the code, I find it easier to version control such multiline constructs. If someone changes a data source, it is clear which one (which line) was modified. The succint notation does not allow clean VCS annotations.

tools/scan-build-py/libscanbuild/analyze.py
45

However, multiple collect phases launched on a system does not make sense

Why not? What about a system with multiple users, where code is in the shared directory? Or even simpler: I've launched a background process, forgot about it, and then launched it again?

In this case, the later one would write over the previous results with the same data.

That is probably fine, I am more worried about racing, where process B would be reading a partially overriden file (not completely sure whether it is possible)

104

Sure, but that separate PR can also include tests.

121

Right, but instead of doing (1) and (2) can we have a separate (maybe hidden from user) param called e.g. ctu_enabled which would explicitly communicate that?

145

In this case, we deliberately leave such functions out to avoid potential problems

We probably want to log it, don't we?

146

ah, OK!

190

OK

244

OK!

319

OK I didn't know that the JSON interface was used by other tools. In that case, ignore my comment.

590

OK. Though you could still use split addition across multiple lines with \

632

OK so opts['ctu'] is a tuple or a named tuple depending on how this function is entered? BTW could you point me to the analyze_cc entry point?

For the purpose of having more uniform code with less cases to care about, do you think we could just use ordinary tuples instead of constructing a named one, since we have to deconstruct an ordinary tuple in any case?

tools/scan-build-py/libscanbuild/arguments.py
376

BTW can we also explicitly add dest='ctu_dir' here, as otherwise I was initially very confused as to where the variable is set.

tools/scan-build-py/libscanbuild/clang.py
168

so the whole toolset will still throw an error later on not having a clang binary.

Of course, but I think that would be easier to debug, and the error would mean that Clang is not available, not that CTU is not working.

xazax.hun updated this revision to Diff 125986.Dec 7 2017, 9:54 AM
  • @gerazo addressed some review comments in scan-build-py.

Python part looks good to me. I don't know whether @dcoughlin or @NoQ would want to insert additional comments on C++ parts.

gerazo added inline comments.Dec 11 2017, 5:30 AM
tools/scan-build-py/libscanbuild/analyze.py
45

I see your point. In order to create the multiple user scenario you've mentioned, those users need to give the exact same output folders for their jobs. Our original bet was that our users are not doing this as the scan-build tool itself is also cannot be used this way. Still the process left there is something to consider. I will plan some kind of locking mechanism to avoid situations like this.

632

Using a NamedTuple improves readability of the code a lot with less comments. It is unfortunate that serializing it is not solved by Python. I think moving this code to the entry point would make the whole thing much nicer. The entry point is at analyze_compiler_wrapper

tools/scan-build-py/libscanbuild/arguments.py
376

Yes, of course.

xazax.hun updated this revision to Diff 126543.Dec 12 2017, 6:31 AM
  • Further improvements to python script part.
tools/scan-build-py/libscanbuild/report.py
257

Minor nitpicking: type comments are semi-standardized with Sphinx-style auto-generated documentation, and should be a part of the docstring.

george.karpenkov requested changes to this revision.Dec 13 2017, 5:26 PM

I've tried using the patch, and I got blocked at the following: CTU options are only exposed when one goes through analyze-build frontend, which requires compile_commands.json to be present. I've used libear to generate compile_commands.json, but the generated JSON does not contain the command field, which causes @require before run to die (also, due to the passing style this error was unnecessarily difficult to debug).
So could you write a short documentation somewhere how all pieces fit together? What entry point should be used, what should people do who don't have a build system-generated compile_commands.jsonetc. etc.

This revision now requires changes to proceed.Dec 13 2017, 5:26 PM

Some comments on the C++ inline.

include/clang/AST/ASTContext.h
82 ↗(On Diff #126543)

Is this forward declaration needed?

include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
81

I don't think CrossTranslationUnitContext belongs in ExprEngine (it doesn't really have much to do with transfer functions and graph construction.

Can you move it to AnalysisDeclContextManager instead?

Also, when you move it to AnalysisManager can you make it a pointer that is NULL when naive cross-translation support is not enabled? This will make it more clear that the cross-translation unit support will not always be available.

lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
441

Can you also add an analyzer option that is something like 'enable-naive-cross-translation-unit-analysis' and defaults to false?

I'd like to avoid using the presence of 'ctu-dir' as an indication that the analyzer should use the naive CTU analysis. This way when if add a less naive CTU analysis we'll be able to the CTUDir for analysis artifacts (such as summaries) for the less naive CTU analysis as well.

lib/StaticAnalyzer/Core/CallEvent.cpp
415

This downcast is an indication that the CTUContext is living in the wrong class.

422

Can this logic be moved to AnalysisDeclContext->getBody()?

CallEvent::getRuntimeDefinition() is really all about modeling function dispatch at run time. It seems odd to have the cross-translation-unit loading (which is about compiler book-keeping rather than semantics) here.

432

I don't think it makes sense to diagnose index errors here.

Doing it when during analysis means that, for example, the parse error could be emitted or not emitted depending on whether the analyzer thinks a particular call site is reached.

It would be better to validate/parse the index before starting analysis rather than during analysis itself.

lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
202

There is no need for AnalysisConsumer to take both a CompilerInstance and a Preprocessor. You can just call getPreprocessor() to get the preprocessor from the CompilerInstance

I've tried using the patch, and I got blocked at the following: CTU options are only exposed when one goes through analyze-build frontend, which requires compile_commands.json to be present. I've used libear to generate compile_commands.json, but the generated JSON does not contain the command field, which causes @require before run to die (also, due to the passing style this error was unnecessarily difficult to debug).
So could you write a short documentation somewhere how all pieces fit together? What entry point should be used, what should people do who don't have a build system-generated compile_commands.jsonetc. etc.

Basically this patch does not change the way scan-build-py is working. So you can either create a compile_commands.json using intercept-build and than use analyze-build to use the result. Or you can do the two together using scan-build. We only offer the CTU functionality in analyze-build, because CTU needs multiple runs anyway, so on the spot build action capture and analyze is not possible with CTU. The general usage of scan-build-py is written in clang/tools/scan-build-py/README.md

xazax.hun marked 6 inline comments as done.Dec 19 2017, 5:29 AM
xazax.hun added inline comments.
lib/StaticAnalyzer/Core/CallEvent.cpp
422

I just tried that and unfortunately, that introduces cyclic dependencies.
CrossTU depends on Frontend. Frontend depends on Sema. Sema depends on Analysis. Making Analysis depending on CrossTU introduces the cycle.

432

While I agree, right now this validation is not the part of the analyzer but the responsibility of the "driver" script for example CodeChecker. It is useful to have this diagnostics to catch bugs in the driver.

xazax.hun updated this revision to Diff 127525.Dec 19 2017, 7:10 AM
xazax.hun marked an inline comment as not done.
  • Address some review comments
  • Rebased on ToT
xazax.hun added inline comments.Dec 19 2017, 7:11 AM
lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
448

This option might not be the most readable but this way experimental is a prefix. Do you prefer this way or something like enable-experimental-naive-ctu-analysis?

NoQ added a comment.Jan 10 2018, 11:17 AM

Had a fresh look on the C++ part, it is super clean now, i'm very impressed :)

lib/StaticAnalyzer/Core/CallEvent.cpp
409–430

*Humbly suggests to refactor whatever we need here into SubEngine's virtual method(s).

getAnalysisManager() is already there, so i guess we only need to expose getCrossTranslationUnitContext().

421

I think CallEvent is the last place where i'd prefer to hardcode this filename. Maybe hardcode it in CrossTranslationUnitContext or get from AnalyzerOptions? (the former, i guess, because i doubt anybody would ever want to change it).

lib/StaticAnalyzer/Core/PathDiagnostic.cpp
416–422

It seems to me that XDL and YDL are exactly the same as XL and YL we've seen at the beginning of the function.

...we still have only one SourceManager, right?

xazax.hun added inline comments.Jan 11 2018, 1:12 PM
lib/StaticAnalyzer/Core/PathDiagnostic.cpp
416–422

Is this true?
One is the location associated with the PathDiagnostic the other is the location of the Decl associated with the issue. I do not have deep understanding of this part of the code but not sure if these are guaranteed to be the same.

NoQ added inline comments.Jan 11 2018, 1:25 PM
lib/StaticAnalyzer/Core/PathDiagnostic.cpp
416–422

Whoops, you're totally right, never mind.

Comments might have probably helped me understand that faster.

xazax.hun updated this revision to Diff 129509.Jan 11 2018, 1:31 PM
xazax.hun marked 5 inline comments as done.
  • Fixed review comments
xazax.hun added inline comments.Jan 11 2018, 1:32 PM
lib/StaticAnalyzer/Core/PathDiagnostic.cpp
416–422

Sure, comments might help, but I want to keep the changes in this patch focused and minimal, so I prefer to do such modifications in a separate patch.

nikhgupt added inline comments.Jan 25 2018, 3:43 PM
lib/StaticAnalyzer/Core/PathDiagnostic.cpp
393

getName could yield incorrect results if two files in the project have the same name. This might break the assert for PathDiagnostics 'total ordering' and 'uniqueness'.
Maybe replacing FileEntry's getName with FullSourceLoc's getFileID could resolve this.

xazax.hun marked 71 inline comments as done.Feb 9 2018, 4:19 AM

Python code looks OK to me, I have one last request: could we have a small documentation how the whole thing is supposed work in integration, preferably on an available open-source project any reader could check out?
I am asking because I have actually tried and failed to launch this CTU patch on a project I was analyzing.

hintonda removed a subscriber: hintonda.Feb 10 2018, 3:18 AM
gerazo added inline comments.Feb 12 2018, 6:38 AM
tools/scan-build-py/libscanbuild/analyze.py
718

Scheduled to be done.

tools/scan-build-py/libscanbuild/report.py
270

After careful investigation, I have to say, it would be very hard to tell that we've done this right in the current setup. Unlike the the rest of clang, ASTImporter.cpp is not a strong part of the system. It has a lot of ongoing fixes and probably more problems (missing CXX functionality) on the way. This is the part which makes CTU less reliable than clang generally. In order to elegantly survive a problem of this unit, we need to leave the other things intact and fix ASTImporter instead (this is an ongoing effort). Until then, this fix seems good enough.

xazax.hun updated this revision to Diff 134431.Feb 15 2018, 7:48 AM
  • Rebased to current ToT
  • Fixed a problem that the scan-build-py used an old version of the ctu configuration option
  • Added a short guide how to use CTU

Python code looks OK to me, I have one last request: could we have a small documentation how the whole thing is supposed work in integration, preferably on an available open-source project any reader could check out?
I am asking because I have actually tried and failed to launch this CTU patch on a project I was analyzing.

We added the documentation. Could you recheck? Thanks in advance!

lib/StaticAnalyzer/Core/PathDiagnostic.cpp
393

Thank you, this is a known problem that we plan to address in a follow-up patch.

dcoughlin accepted this revision.Feb 27 2018, 8:13 PM

Thanks Gabor, this looks good to me. Please commit!

This revision was not accepted when it landed; it landed in state Needs Review.Feb 28 2018, 5:25 AM
Closed by commit rL326323: [analyzer] Support for naive cross translation unit analysis (authored by xazax, committed by ). · Explain Why
This revision was automatically updated to reflect the committed changes.
This revision was not accepted when it landed; it landed in state Needs Review.Feb 28 2018, 5:25 AM
Closed by commit rC326323: [analyzer] Support for naive cross translation unit analysis (authored by xazax, committed by ). · Explain Why
This revision was automatically updated to reflect the committed changes.
a.sidorin reopened this revision.Mar 1 2018, 4:51 AM

The changes were reverted: http://llvm.org/viewvc/llvm-project?rev=326432&view=rev
Gabor, could you take a look?

xazax.hun added a subscriber: ilya-biryukov.

@ilya-biryukov

Could you please provide some more details where the cyclic dependency is? I cannot reproduce the problem and usually cmake fails when there is a cyclic dependency and you are building shared libraries.

xazax.hun abandoned this revision.Mar 2 2018, 6:28 AM

Resubmitted in https://reviews.llvm.org/rL326439

Phabricator did not display the mailing list conversation. The point is, the circular dependency does not exist in the upstream version of clang. The reason is that CMake does not track the header includes as dependencies. There might be some layering violations with the header includes but those are independent of this patch and need to be fixed separately.

NoQ added a comment.Jul 16 2018, 2:57 PM

Just noticed: getRuntimeDefinition() has a lot of overrides in CallEvent sub-classes, and there paths that don't defer to AnyFunctionCall::getRuntimeDefinition(), eg., CXXInstanceCall::getRuntimeDefinition() => if (MD->isVirtual()) .... Which means that for some calls we aren't even trying to make a CTU lookup.

Which means that for some calls we aren't even trying to make a CTU lookup.

Thanks @NoQ, we will take a look at it!

@NoQ , @dkrupp

CallEvent::getRuntimeDefinition is overwritten in

  • AnyFunctionCall
  • CXXInstanceCall
  • CXXMemberCall
  • CXXDestructorCall
  • ObjCMethodCall

AnyFunctionCall handles the CTU logic.
CXXInstanceCall calls into AnyFunctionCall if the function is not virtual.
If the function is virtual then we try to find the Decl of it via the dynamic type info.
At this point, we could get the definition of that function via the CTU logic, indeed.
This is something we should implement in the future.

However, it seems like this is the only case (not considering ObjC).
CXXMemberCall calls back to AnyFunctionCall or to CXXInstanceCall.
CXXDestructorCall does the same.

NoQ added a comment.Jul 18 2018, 8:05 AM

Aha, cool, so it's probably just virtual functions.