This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Support for naive cross translational unit analysis
AbandonedPublic

Authored by xazax.hun on Mar 7 2017, 4:47 AM.
Tokens
"Party Time" token, awarded by whisperity.

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
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
xazax.hun marked 2 inline comments as done.Jun 7 2017, 5:10 AM

I agree that scan-build or scan-build-py integration is an important issue to resolve here. What I envision is that users will just call scan-build and pass -whole-project as an option to it. Everything else will happen automagically:)

We contacted Laszlo and we have a pull request into scan-build that is under review. He is very helpful and supports the idea of scan-build-py supporting CTU analysis.

I do not quite understand why AST serialization is needed at all. Can we instead recompile the translation units on demand into a separate ASTContext and then ASTImport?

We did a prototype implementation of on-demand reparsing. On the C projects we tested, the runtime is increased by 10-30% compared to dumping the ASTs. Note that, it is relatively fast to parse C, I would expect a much bigger delta in case of C++ projects. Unfortunately, we weren't able to test that setting due to the ASTImporter limitations.

include/clang/AST/Mangle.h
59 ↗(On Diff #94814)

Note that the newest version of this patch does not use name mangling, it uses USRs instead. This turned out to be a perfectly viable alternative and we did not see any behavioral changes on the project we tested after the transition.

Thanks for the reviews so far.
I think we have addressed all major concerns regarding this patch:

-(Anna) Scan-build-py integration of the functionality is nearly finished (see https://github.com/rizsotto/scan-build/issues/83) (--ctu switch performs both analysis phases at once). This I think could go in a different patch, but until we could keep the ctu-build.py and ctu-analyze.py scripts. Do you agree?

-(Devin,NoQ) In the externalFnMap.txt (which contains which function definitions is located where) Unified Symbol Resolution (USR) is used to identify functions instead of mangled names, which seems to work equally well for C and C++

-(Anna) Dumping the ASTs to the disk. We tried a version where, ASTs are not dumped in the 1st phase, but is recreated each time a function definition is needed from an external TU. It works fine, but the analysis time went up by 20-30% on open source C projects. Is it OK to add this functionality in a next patch? Or should we it as an optional feature right now?

Do you see anything else that would prevent this patch to get in?

a.sidorin accepted this revision.Jun 14 2017, 8:52 AM

Hello Daniel & Gabor,
Thank you very much for your work. This patch looks good to me but I think such a change should also be approved by maintainers.

-(Anna) Scan-build-py integration of the functionality is nearly finished (see https://github.com/rizsotto/scan-build/issues/83) (--ctu switch performs both analysis phases at once). This I think could go in a different patch, but until we could keep the ctu-build.py and ctu-analyze.py scripts. Do you agree?

It's important to bring this patch into the LLVM repo so that it becomes part of the clang/llvm project and is used. The whole point of adding CTU integration to scan-build-py is to make sure that there is a single tool that all/most users could use; adding the patch to a fork does not accomplish that goal. Also, I am not a fan of developing on downstream branches and that is against the LLVM Developer policy due to all the reasons described here: http://www.llvm.org/docs/DeveloperPolicy.html#incremental-development. This development style leads to fragmentation of the community and the project. Unfortunately, we often see cases where large patches developed out of tree never make it in as a result of not following this policy and it would be great to avoid this in the future.

This I think could go in a different patch, but until we could keep the ctu-build.py and ctu-analyze.py scripts. Do you agree?

It would be best to just add the scan-build-py support to the tree, especially, since the new scrips are not tested.

-(Anna) Dumping the ASTs to the disk. We tried a version where, ASTs are not dumped in the 1st phase, but is recreated each time a function definition is needed from an external TU. It works fine, but the analysis time went up by 20-30% on open source C projects.

I am curious which optimization strategies you considered. An idea that @NoQ came up with was to serialize only the most used translation units. Another idea is to choose the TUs that a particular file has most dependencies on and only inline functions from those.

What mode would you prefer? Would you pay the 20%-30% in speed but reduce the huge disk consumption? That might be a good option, especially, if you have not exhausted the ideas on how to optimize.

Is it OK to add this functionality in a next patch? Or should we it as an optional feature right now?

This depends on what the plan for going forward is. Specifically, if we do not need the serialization mode, you could remove that from this patch and add the new mode. If you think the serialization mode is essential going forward, we could have the other mode in a separate patch. (It would be useful to split out the serialization mode work into a separate patch so that we could revert it later on if we see that the other mode is better.)

I see some changes to the compiler proper, such as ASTImporter, ASTContext, SourceManager. We should split those changes into a separate patch and ask for review from people working on those components. You can point back to this patch, which would contain the analyzer related changes, and state that the other patch is blocking this work.

Thanks.

It would be best to just add the scan-build-py support to the tree, especially, since the new scrips are not tested.

OK. We will update this patch with the scan-build-py changes and remove the ctu-build.py and ctu-analyze.py scripts.

I am curious which optimization strategies you considered. An idea that @NoQ came up with was to serialize only the most used translation units. Another idea is to choose the TUs that a particular file has most dependencies on and only inline functions from those.

Both of these strategies could work in practice, we did not try them. We implemented the two extremes: serialize all TUs/don't serialize any of the TUs. Both of them could can be useful in practice as is (depending if the user is cpu/memory/disk space bound). I think we could try with the above suggested optimizations as an incremental improvement (and keep this initial patch as simple as possible).

What mode would you prefer? Would you pay the 20%-30% in speed but reduce the huge disk consumption? That might be a good option, especially, if you have not exhausted the ideas on how to optimize.

In this initial version I think we should keep the serializing mode. We just measured that the heap consumption of the non-serializing mode and it seems to be ~50% larger. Probably because the serializing mode only loads those AST fragments from the disk that is imported. But I can imagine that some user still want to use the non-serializing version which is not using extra disk space. So we will add the non-serializing mode in a next patch as an Analyzer option first (which we can turn into default behaviour later on). OK?

I see some changes to the compiler proper, such as ASTImporter, ASTContext, SourceManager. We should split those changes into a separate patch and ask for review from people working on those components. You can point back to this patch, which would contain the analyzer related changes, and state that the other patch is blocking this work.

Allright, we will do that.

So is it OK to proceed like this?

Some of the CTU related analyzer independent parts are being factored out.
The review is ongoing here: https://reviews.llvm.org/D34512

Another small and independent part is under review here: https://reviews.llvm.org/D34506

NoQ added a comment.Jun 22 2017, 7:30 AM

Regarding serializing vs not serializing and now vs later.

  1. I think we eventually need to provide a reasonable default approach presented to the user. This approach shouldn't be hurting the user dramatically in any sense. Because serializing hurts the user's disk space dramatically, and not-serializing may be slower and a bit more memory-intensive but isn't too bad in all senses, out of these two options not-serializing is definitely preferable as a default approach.
  1. Later we should definitely consider the alternative approaches that serialize only some ASTs, with the hope that one of them would turn out to be a better default approach.
  1. From 2. it follows that for now it's better to keep both approaches around - as we believe that the ideal approach may be a combination of the two. Therefore it doesn't really matter in what order they land.

tl;dr: I propose to land serialization-based approach first, then land non-serialization-based approach later and make it default, then consider taking the best of the two and making it a new default.

klimek added a subscriber: klimek.

Richard (added as reviewer) usually owns decisions around clang itself. Writing an email to cfe-dev with the numbers and wait for whether others have concerns would probably also be good.

xazax.hun updated this revision to Diff 105053.Jul 3 2017, 4:58 AM
  • Patch scan-build instead of using custom scripts
  • Rebase patch based on the proposed LibTooling CTU code
tools/scan-build-py/libscanbuild/analyze.py
165 ↗(On Diff #105053)

I believe you can write:

for line in open(filename, 'r'):
172 ↗(On Diff #105053)

this 'with' seems redundant. I suggest an assignment and then less indentation will be needed below

223 ↗(On Diff #105053)

not a big deal but I would use early exits in this function

tools/scan-build-py/libscanbuild/clang.py
177 ↗(On Diff #105053)

I am guessing that you can use cmd.find() instead of the loop

The Python code here still uses mangled name in their wording. Does this mean this patch is yet to be updated with the USR management in the parent patch?

tools/scan-build-py/libscanbuild/analyze.py
165 ↗(On Diff #105053)

Do we want to rely on the interpreter implementation on when the file is closed.

If

for line in open(filename, 'r'):
   something()

is used, the file handle will be closed based on garbage collection rules. Having this handle disposed after the iteration is true for the stock CPython implementation, but it is still nontheless an implementation specific approach.

Whereas using with will explicitly close the file handle on the spot, no matter what.

172 ↗(On Diff #105053)

I don't seem to understand what do you want to assign to what.

danielmarjamaki accepted this revision.Sep 1 2017, 1:07 AM
danielmarjamaki added inline comments.
tools/scan-build-py/libscanbuild/analyze.py
165 ↗(On Diff #105053)

ok I did not know that. feel free to ignore my comment.

172 ↗(On Diff #105053)

I did not consider the garbage collection. I assumed that out_file would Always be closed when it Went out of scope and then this would require less indentation:

out_file = open(extern_fns_map_file, 'w')
for mangled_name, ast_file in mangled_ast_pairs:
    out_file.write('%s %s\n' % (mangled_name, ast_file))
223 ↗(On Diff #105053)

with "not a big deal" I mean; feel free to ignore my comment if you want to have it this way.

This revision is now accepted and ready to land.Sep 1 2017, 1:07 AM

While testing this I stumbled upon a crash with the following test case:

inc.h

#define BASE ((int*)0)
void foo();

main.c:

#include "inc.h"
void moo()
{
    int a = BASE[0];
    foo();
}

other.c

#include "inc.h"
void foo()
{
    int a = BASE[0];
}

Note that I used a custom checker that did not stop on the path like the DerefChecker would here. I did not know how to reproduce it with official checkers, but the issue should be understandable without reproduction.

With the given test a checker may produce two results for the null dereference in moo() and foo(). When analyzing main.c they will both be found and therefore sorted with PathDiagnostic.cpp "compareCrossTUSourceLocs".

If either of the FullSourceLocs is a MacroID, the call SM.getFileEntryForID(XL.getFileID()) will return a null pointer. The null pointer will crash the program when attempting to call ->getName() on it.

My solution was to add the following lines before the .getFileID() calls:

XL = XL.getExpansionLoc();
YL = YL.getExpansionLoc();
lib/StaticAnalyzer/Core/PathDiagnostic.cpp
391 ↗(On Diff #105053)

see comment

In a similar case, static inline functions are an issue.

inc.h

void foo();
static inline void wow()
{
    int a = *(int*)0;
}

main.c

#include "inc.h"
void moo()
{
    foo();
    wow();
}

other.c

#include "inc.h"
void foo()
{
    wow();
}

The inline function is inlined into each calling AST as different AST objects. This causes the PathDiagnostics to be distinct, while pointing to the exact same source location.

When the compareCrossTUSourceLocs function tries to compare the FullSourceLocs, it cannot find a difference and FlushDiagnostics will assert on an erroneous compare function.

For my purposes I replaced the return statement of the compareCrossTUSourceLocs function with:

return XL.getFileID() < YL.getFileID();

A more correct fix would create only one unique diagnostic for both cases.

xazax.hun updated this revision to Diff 116502.Sep 25 2017, 2:35 AM
  • Fixed an issue with source locations
  • Updated to latest trunk

If either of the FullSourceLocs is a MacroID, the call SM.getFileEntryForID(XL.getFileID()) will return a null pointer. The null pointer will crash the program when attempting to call ->getName() on it.

Thank you for the report and the detailed analysis!
I did not want to get the expansion location since the original code did not query that either, so for now I just handle the case when I can not query a file entry. This case can occur even when no macros are in the code, for example when a PCH is referring to a nonexistent file.

For my purposes I replaced the return statement of the compareCrossTUSourceLocs function with:

return XL.getFileID() < YL.getFileID();

A more correct fix would create only one unique diagnostic for both cases.

Thank you for the report, I could reproduce this after modifying the null dereference checker. My fear of using file IDs is that I don't know whether they are stable. So in subsequent runs, different paths might be chosen by the analyzer and this could be confusing to the user. I will think about a workaround that both stable and solves this assertion.

I see two possible ways to do the proper fix. One is to check explicitly for this case when the same function appears in multiple translation units. A better approach would be to have the ASTImporter handle this case. I think the proper fix is better addressed in a separate patch.

dkrupp requested changes to this revision.Oct 15 2017, 7:28 AM

Please fix the incompatibility between analyze-build and lib/CrossTU in the format of externalFnMap.txt mappfing file.

tools/scan-build-py/libscanbuild/analyze.py
535 ↗(On Diff #116502)

There is a incompatibility between this scan-build (analyze-build actually) implementation and new lib/CrossTU library.

CrossTranslationUnitContext::loadExternalAST(

StringRef LookupName, StringRef CrossTUDir, StringRef IndexName)

expects the externalFnMap.txt to be in
"functionName astFilename" format.
however currently we generate here
"functionName@arch astFilename" lines.

One possible fix could be to
create one externalFnMap.txt indexes per arch
<collect-dir>/ast/x86_64/externalFnMap.txt
<collect-dir>/ast/ppc64/externalFnMap.txt
etc.
and call clang analyze with the architecture specific map directory:
e.g. ctu-dir=<collect-dir>/ast/x86_64

This would then work if the "to-be-analyzed" source-code is cross-compiled into multiple architectures.

Would be useful to add a test-case too to check if the map file and ctu-dir content generated by analyze-build is compatible.

585 ↗(On Diff #116502)

Maybe we could use the full target-triple for distinguishing the AST binaries, not only the architecture part. The sys part for example is probably important too and a "win32" AST may not be compatible with a "linux" AST.

This revision now requires changes to proceed.Oct 15 2017, 7:28 AM
xazax.hun updated this revision to Diff 119458.Oct 18 2017, 4:22 AM
xazax.hun edited edge metadata.
xazax.hun marked an inline comment as done.
  • Update the scan-build part to work correctly with the accepted version of libCrossTU
xazax.hun updated this revision to Diff 121700.Nov 6 2017, 2:15 AM
  • Rebased on ToT
george.karpenkov requested changes to this revision.Nov 27 2017, 2:34 PM
george.karpenkov added inline comments.
tools/scan-build-py/libscanbuild/analyze.py
44 ↗(On Diff #121700)

What would happen when multiple analyzer runs are launched concurrently in the same directory? Would they race on this file?

64 ↗(On Diff #121700)

run_analyzer_with_ctu is an unfortunate function name, since it may or may not launch CTU depending on the passed arguments. Could we just call it run_analyzer?

103 ↗(On Diff #121700)

Actually I would prefer a separate NFC PR just moving this function. This PR is already too complicated as it is.

120 ↗(On Diff #121700)

Extensive hasattr usage is often a codesmell, and it hinders understanding.
Firstly, shouldn't args.ctu_phases.dir be always available, judging from the code in arguments.py?
Secondly, in what cases args.ctu_phases is not available when we are already going down the CTU code path? Shouldn't we throw an error at that point instead of creating a default configuration? (default-configurations-instead-of-crashing is also another way to introduce very subtle and hard-to-catch error modes)

128 ↗(On Diff #121700)

Could you also specify what func_map_lines is (file? list? of strings?) in the docstring? There's specific Sphinx syntax for that. Otherwise it is hard to follow.

138 ↗(On Diff #121700)

Could be improved with defaultdict:

mangled_to_asts = defaultdict(set)
...
   mangled_to_asts[mangled_name].add(ast_file)
144 ↗(On Diff #121700)

Firstly, no need to modify the set in order to get the first element, just use next(iter(ast_files)).
Secondly, when exactly do conflicting names happen? Is it a bug? Shouldn't the tool log such cases?

145 ↗(On Diff #121700)

Overall, instead of creating a dictionary with multiple elements, and then converting to a list, it's much simper to only add an element to mangled_to_asts when it is not already mapped to something (probably logging a message otherwise), and then just return mangled_to_asts.items()

160 ↗(On Diff #121700)

Firstly, is glob.glob actually random, as the docstring is saying?
If yes, can we make it not to be random (e.g. with sorted), as dealing with randomized input makes tracking down bugs so much harder?

168 ↗(On Diff #121700)

If write_global_map is a closure, please use the fact that it would capture ctudir from the outer scope, and remove it from the argument list.
That would make it more obvious that it does not change between invocations.

189 ↗(On Diff #121700)

Having an analysis tool remove files is scary, what if (maybe not in this revision, but in a future iteration) a bug is introduced, and the tool removes user code instead?
Why not just create a temporary directory with tempfile.mkdtemp, put all temporary files there, and then simply iterate through them?
Then you would be able to get rid of the constant CPU_TEMP_FNMAP_FOLDER entirely, and OS would be responsible for cleanup.

230 ↗(On Diff #121700)

Similarly to the comment above, I would prefer if analysis tool would not remove files (and I assume those are not huge ones?)
Can we just use temporary directories?

241 ↗(On Diff #121700)

Same as the comment above about removing folders. Also it seems like there should be a way to remove redundancy in if collect / remove tree block repeated twice.

262 ↗(On Diff #121700)

Using JSON-serialization-over-environment-variables is very unorthodox, and would give very bizarre error messages if the user would try to customize settings (I assume that is the intent, right?)
I think that separating those options into separate ENV variables (if they _have_ to be customizable) would be much better.

296 ↗(On Diff #121700)

Again, is it possible to avoid JSON-over-environment-variables?

534 ↗(On Diff #121700)

mangled_name, path = fn_src_txt.split(" ", 1) ?

561 ↗(On Diff #121700)

try/except/pass is almost always bad.
When can the error occur? Why are we ignoring it?

567 ↗(On Diff #121700)

The above can be written more succinctly as:
ast_command = [opts['clang'], ...] + args + ['-w', ...]

578 ↗(On Diff #121700)

Similarly here, funcmap_command can be generated in one line using +

588 ↗(On Diff #121700)

Again, why is this error ignored?

609 ↗(On Diff #121700)

In which case is this branch hit? Isn't improperly formed input argument indicative of an internal error at this stage?

702 ↗(On Diff #121700)

This blank line should not be in this PR.

tools/scan-build-py/libscanbuild/clang.py
168 ↗(On Diff #121700)

I might be missing something here, but why is the ability to call --version indicative of CTU support?
At worst, this can lead to obscuring real bugs: imagine if the user has args.clang pointed to broken/non-existent binary, then is_ctu_capable would simply return False (hiding the original error!), which would show a completely misleading error message.

Just checking func_map_cmd seems better, but even in this case we should probably log any errors occurring on -version call (such messages would really aid debugging)

177 ↗(On Diff #121700)

Seconded, would prefer this rewritten using separator = cmd.find('-triple')

tools/scan-build-py/libscanbuild/report.py
270 ↗(On Diff #121700)

I understand the intent here, but it seems it should be handled at a different level: would it be hard to change Clang to only write the report file at the very end, when no crash should be encountered? Or make parsers not choke on empty fields?

tools/scan-build-py/tests/unit/test_analyze.py
338 ↗(On Diff #121700)

Probably more tests are required for almost 400 lines of functional Python code in this PR.
Would it be hard to have a full LIT-style integration test? E.g. have a dummy script emulating Clang with a dummy directory structure, which would show how all pieces are meant to fit together?

This revision now requires changes to proceed.Nov 27 2017, 2:34 PM

Thanks George for the review. I will start working on the code right away. I've tried to answer the simpler cases.

tools/scan-build-py/libscanbuild/analyze.py
44 ↗(On Diff #121700)

Yes and no. The 1st, collect part of CTU creates this file by aggregating all data from the build system, while the 2nd part which does the analysis itself only reads it. Multiple analysis can use this file simultaneously without problem. However, multiple collect phases launched on a system does not make sense. In this case, the later one would write over the previous results with the same data.

64 ↗(On Diff #121700)

We have an other run_analyzer method but still, it is a good idead, I will make something better up.

103 ↗(On Diff #121700)

Yes. The only reason was for the move to make it testable. However, we need more tests as you wrote down below.

120 ↗(On Diff #121700)

It definitely needs more comments, so thanks, I will put them here.
There are two separate possibilities here for this code part:

  1. The user does not want CTU at all. In this case, no CTU phases are switched on (collect and analyze), so no CTU code will run. This is why dir has no importance in this case.
  2. CTU capabilities were not even detected, so the help and available arguments about CTU are also missing. In this case we create a dummy config telling that everything is switched off.

The reason for using hasattr was that not having CTU capabilities is not an exceptional condition, rather a matter of configuration. I felt that handling this with an exception would be misleading.

128 ↗(On Diff #121700)

Thanks, I'll do it.

144 ↗(On Diff #121700)

Nice catch, thanks.
For your second question: Unfortunately, it is not a bug, rather a misfeature which we can't handle yet. There can be tricky build-systems where a single file with different configurations is built multiple times, so the same function signature will be present in multiple link units. The other option is when two separate compile units have an exact same function signature, but they are never linked together, so it is not a problem in the build itself. In this case, the cross compilation unit functionality cannot tell exactly which compilation unit to turn to for the function, because there are multiple valid choices. In this case, we deliberately leave such functions out to avoid potential problems. It deserves a comment I think.

160 ↗(On Diff #121700)

"random" here means we don't care. So you are right. glob.glob doc says it is arbitrary but I couldn't find that it is deterministic or not. Probably sorting it will not do harm.

189 ↗(On Diff #121700)

Yes, you are right. We are essentially using a temp dir. Because of the size we first had to put it next to the project (not on tmp drive for instance) and for debugging purposes we gave a name to it. Still it can be done with mkdtemp as well.

230 ↗(On Diff #121700)

Unlike above, here we do remove non-temporary data intentionally. The user asks here to do the recollection of CTU data for a fresh start. Because there is no "clean" functionality in the analyzer interface itself, this seemed to be the easiest-on-user solution to save him/her an extra effort or a new command.

262 ↗(On Diff #121700)

To be honest, I could never make a decision over this. The previous version of scan-build-py used extensively environment variables for everything which ended up in a huge mess and env contamination. There was an effort to reduce this to only a few, well-designated ones. Still there is the need of adding new data to the environment.

561 ↗(On Diff #121700)

I think this code is redundant with the if above.

609 ↗(On Diff #121700)

An other part of scan-build-py, analyze_cc uses namedtuple to json format to communicate. However, the names are not coming back from json, so this code helps in this. This is the case when someone uses the whole toolset with compiler wrapping. All the environment variable hassle is also happening because of this. So these env vars are not for user modification (as you've suggested earlier).

tools/scan-build-py/libscanbuild/clang.py
168 ↗(On Diff #121700)

The original idea was that clang can give information about CTU support itself. However, it never happened because the analyzer is so deep down in the system. So I am open to remove the clang binary check here. However, clang binary is needed anyway, so the whole toolset will still throw an error later on not having a clang binary.

gerazo added a comment.Dec 6 2017, 7:17 AM

The code modifications are coming soon (after doing some extensive testing) for the scan-build part.

tools/scan-build-py/tests/unit/test_analyze.py
338 ↗(On Diff #121700)

You are right. The testing infra in scan-build-py is not right anyway (uses nosetests). However, this should be a new patch as you've mentioned earlier.

gerazo added inline comments.Dec 6 2017, 7:17 AM
tools/scan-build-py/libscanbuild/analyze.py
145 ↗(On Diff #121700)

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.

189 ↗(On Diff #121700)

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.

241 ↗(On Diff #121700)

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.

296 ↗(On Diff #121700)

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.

561 ↗(On Diff #121700)

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.

567 ↗(On Diff #121700)

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.

223 ↗(On Diff #105053)

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.

tools/scan-build-py/libscanbuild/analyze.py
44 ↗(On Diff #121700)

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)

103 ↗(On Diff #121700)

Sure, but that separate PR can also include tests.

120 ↗(On Diff #121700)

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?

144 ↗(On Diff #121700)

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

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

145 ↗(On Diff #121700)

ah, OK!

189 ↗(On Diff #121700)

OK

230 ↗(On Diff #121700)

OK!

296 ↗(On Diff #121700)

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

567 ↗(On Diff #121700)

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

609 ↗(On Diff #121700)

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 ↗(On Diff #121700)

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 ↗(On Diff #121700)

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
xazax.hun edited edge metadata.
  • @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
44 ↗(On Diff #121700)

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.

609 ↗(On Diff #121700)

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 ↗(On Diff #121700)

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 ↗(On Diff #126543)

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
63 ↗(On Diff #126543)

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
400 ↗(On Diff #126543)

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
365 ↗(On Diff #126543)

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

372 ↗(On Diff #126543)

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.

382 ↗(On Diff #126543)

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
197 ↗(On Diff #126543)

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
372 ↗(On Diff #126543)

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.

382 ↗(On Diff #126543)

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
407 ↗(On Diff #127525)

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
373–374 ↗(On Diff #127525)

*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().

385 ↗(On Diff #127525)

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
418–423 ↗(On Diff #127525)

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
418–423 ↗(On Diff #127525)

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
418–423 ↗(On Diff #127525)

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
418–423 ↗(On Diff #127525)

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
395 ↗(On Diff #129509)

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
702 ↗(On Diff #121700)

Scheduled to be done.

tools/scan-build-py/libscanbuild/report.py
270 ↗(On Diff #121700)

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
395 ↗(On Diff #129509)

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
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
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.