This is an archive of the discontinued LLVM Phabricator instance.

[clang][analyzer][ctu] Make CTU a two phase analysis
ClosedPublic

Authored by martong on Apr 14 2022, 2:40 AM.

Details

Summary

This new CTU implementation is the natural extension of the normal single TU
analysis. The approach consists of two analysis phases. During the first phase,
we do a normal single TU analysis. During this phase, if we find a foreign
function (that could be inlined from another TU) then we don’t inline that
immediately, we rather mark that to be analysed later.
When the first phase is finished then we start the second phase, the CTU phase.
In this phase, we continue the analysis from those points (exploded nodes)
which had been enqueued during the first phase. We gradually extend the
exploded graph of the single TU analysis with new nodes that are created by the
inlining of foreign functions.

We count the number of analysis steps of the first phase and we limit the
second (ctu) phase with this number.

This new implementation makes it convenient for the users to run the single-TU
and the CTU analysis in one go, they don't need to run the two analysis separately.
Thus, we name this new implementation as onego CTU.

Discussion:
https://discourse.llvm.org/t/rfc-much-faster-cross-translation-unit-ctu-analysis-implementation/61728

Diff Detail

Event Timeline

martong created this revision.Apr 14 2022, 2:40 AM
Herald added a project: Restricted Project. · View Herald Transcript
martong requested review of this revision.Apr 14 2022, 2:40 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 14 2022, 2:40 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
martong added inline comments.Apr 14 2022, 2:48 AM
clang/test/Analysis/ctu-main.cpp
161

This FIXME is outdated, got here during rebase.

martong added inline comments.Apr 14 2022, 2:48 AM
clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
167

Well, not just for lit tests, I'll update the comment.

> Make CTU a two phase analysis

At this point maybe it will be a three phase, as we might dump the ASTs/create index in phase 1 :)

During this phase, if we find a foreign function (that could be inlined from another TU) then we don’t inline that immediately, we rather mark that to be analysed later.

I wonder whether this is the right approach. Not inlining a function can also introduce false positives. While I do see why we do not want to inline ALL functions upfront, I wonder if we actually want to inline small functions. The CSA already has heuristics like this, to always inline really small functions (defined by the number of nodes in the Cfg) despite other cut heuristics and it was found to improve the quality of the results overall. I think doing something similar for CTU might ultimately improve the precision of the analysis. What do you think?

martong updated this revision to Diff 425782.Apr 28 2022, 8:04 AM
  • Add an option to config the inlining mode during the first phase
  • Change the ctu-main.c[pp] tests to have a RUN line with this new config option that mimics the old ctu implementation's behavor.
  • Change the on-demand-parsing tests back as they were in the baseline. Those files are sheer copies of the ctu-main files, actually, the on demand testing should be done in the ctu-main test files as well (added a fixme for that).
martong updated this revision to Diff 425784.Apr 28 2022, 8:06 AM
  • Chosing the correct baseline this time
martong added inline comments.Apr 28 2022, 8:10 AM
clang/test/Analysis/ctu-on-demand-parsing.c
23
martong updated this revision to Diff 426037.Apr 29 2022, 6:18 AM
  • Add more explanatory comments to the values of ctu-phase1-inlining
  • Fix typo in comments in ctu-on-demand-parsing tests
  • Remove stale comment, config options are desribed elsewhere
xazax.hun added inline comments.May 6 2022, 9:08 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
116

I feel that we use different terms for the imported declarations. Sometimes we call them new, sometimes imported, sometimes foreign. In case all of these means the same thing, it would be nice to standardize on a single way of naming. If there is a subtle difference between them, let's document that in a comment. It would be nice if we did not need the comment after the declaration but it would be obvious from the variable name.

156

Why do we need this to be mutable? Shouldn't we have this information when the CallEvent is created?

clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
176

I think we do not expect the STU WorkList to ever be null, maybe it is time to clean this up and return a reference.

clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
91

The CTUPhase1InliningMode is coming from the user, right? Unless we have some validation in place before this code get called, I think it might not be a good idea to assert fail on certain user inputs.

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
432

What is the meaning if the return value? It looks like the function always returns true.

446

So if we see the same foreign function called in multiple contexts, we will only queue one of the contexts for the CTU. Is this the intended design?

So if I see:

foreign(true);
foreign(false);

The new CTU will only evaluate foreign(true) but not foreign(false).

513

So getCTUWorkList will return nullptr in the second phase? Reading this code first I had the impression we will skip doing marking them visited in the first phase. I think having a helper like IsSecondCTUPhase or something would make this a bit less confusing.

1123–1124

I think this is getting really confusing here. The comment saying we are not bifurcating and we call ctuBifurcate. While I do understand these are two different kinds of bifurcation but I think we should rethink how to name some of these functions.

martong marked 4 inline comments as done.May 6 2022, 1:09 PM

Thanks for the review Gabor, I'll update soon and hope I could answer your questions.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
116

Yes, I agree that this should deserver some more explanation. Maybe right above this declaration?

So, new means that a declaration is created newly by the ASTImporter.
imported means it has been imported, but not necessarily new. Think about this case, we import foo's definition.

// to.cpp
void bar() {} // from a.h
// from.cpp
void bar() {} // from a.h
void foo() {
  bar();
}

Then foo will be new and imported, bar will be imported and not new.
foreign basically means imported and new.

156

Unfortunately, we get this from the RuntimeDefinition which is not available during the creation of the CallEvent. We use getRuntimeDefinition() to retrieve the definition and attach that to the already existent CallEvent.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
176

I'd rather do that independently, so this patch can be focused and kept minimal, if you don't mind.
(I mean WorkList &getWorkList would introduce irrelevant scattered changes.)

clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
91

Yeah, I've copied this from below assert(K.hasValue() && "IPA Mode is invalid.");. Seems like the pattern we have everywhere. I suggest to get rid of this wrong pattern independently, but I'd not deviate from the pattern here, making it easier to do a bulk update once we do it.

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
432

Nothing. It is being used by inlineCall but there are no callers of inlineCall that would use it because inlineCall does return true on all paths as well. Good point, this is again a rotten legacy. I am going update this soon.

446

This is intentional.

foreign(true);
foreign(false);

The new CTU will evaluate the following paths in the exploded graph:

foreign(true); // conservative evaluated
foreign(false); // conservative evaluated
foreign(true); // inlined
foreign(false); // inlined

The point is to keep bifurcation to a minimum and avoid the exponential blow up.
So, we will never have a path like this:

foreign(true); // conservative evaluated
foreign(false); // inlined

Actually, this is the same strategy that we use during the dynamic dispatch of C++ virtual calls. See DynamicDispatchBifurcationMap.

The conservative evaluation happens in the first phase, the inlining in the second phase (assuming the phase1 inlining option is set to none).

513

Fair enough. I am going to update.

1123–1124

Yeah, good point, the comment is meaningless and confusing from this point, I'll just delete it.

martong updated this revision to Diff 428055.May 9 2022, 6:05 AM
martong marked 8 inline comments as done.
  • Add explanatory comment to RuntimeDefinition::Foreign field
  • Changed the return value from bool to void in ctuBifurcate and in inlineCall
  • Add isCTUInFirtstPhase()
  • Remove stale comment
martong added inline comments.May 9 2022, 6:09 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
116

I've just added an explanatory comment for this field.

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
432

I've changed the return value from bool to void, both in ctuBifurcate and in inlineCall.

513

I've added isCTUInFirtstPhase().

1123–1124

I removed the comment.

xazax.hun added inline comments.May 11 2022, 9:49 AM
clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
446

The new CTU will evaluate the following paths in the exploded graph:

foreign(true); // conservative evaluated
foreign(false); // conservative evaluated
foreign(true); // inlined
foreign(false); // inlined

When we encounter foreign(true), we would add the decl to CTUDispatchBifurcationSet. So the second time we see a call to the function foreign(false);, we will just do the conservative evaluation and will not add the call to the CTU worklist. So how will foreign(false); be inlined in the second pass? Do I miss something?

xazax.hun added inline comments.May 11 2022, 9:51 AM
clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
446

Oh, I think I now understand. Do you expect foreign(false); to be inlined after we return from foreign(true); in the second pass? Sorry for the confusion, in that case it looks good to me.

xazax.hun added inline comments.May 11 2022, 9:56 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
116

Foreign means new and imported. But is there a way for a declaration to be new and not to be imported? If no, in that case it feels like new and foreign are actually the same and we should standardize on a single name.

xazax.hun accepted this revision.May 11 2022, 10:08 AM

Overall looks good to me. I wish some parts would be simpler but it looks like sometimes it is not easy to extend the current code and we might need to do some refactoring at some point.

This revision is now accepted and ready to land.May 11 2022, 10:08 AM
martong marked 3 inline comments as done.May 12 2022, 1:36 AM
martong added inline comments.
clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
116

Yeah, you are right, new and foreign are the same in this sense. However, I think the term foreign is more expressive in the sense that is suggests that the definition is coming from another translation unit.

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
446

Oh, I think I now understand. Do you expect foreign(false); to be inlined after we return from foreign(true); in the second pass?

Yes, that's right.

whisperity added inline comments.
clang/include/clang/AST/ASTImporterSharedState.h
83 ↗(On Diff #428055)

(The naming of this function feels a bit odd. markAsNewDecl or just markNewDecl?)

clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def
414
414–420

Couldn't this description here be simplified to say something along the lines of "the percentage of single-TU analysed nodes that the CTU analysis is allowed to visit"? Is the calculation method needed from the user's perspective? The examples talk about percentage too.

clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
141

Is this configuration inherent to the static analyser, and not the CrossTU library?

141

(Documentation for the options are missing.)

clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
156
clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
815–817

How and why is this needed? Could you call it isSingleTUOr1stPhaseCTU instead?

Rather, if this is used as a distinction input in conditionals, could you invert the branches and have a function isSecondPhaseCTU, and do the inverted logic where this function is consumed?

clang/test/Analysis/Inputs/ctu-onego-existingdef-other.cpp.externalDefMap.ast-dump.txt
2

Why is there only 1 symbol in this file, when the file above contains two function definitions?

clang/test/Analysis/ctu-on-demand-parsing.c
22
clang/test/Analysis/ctu-on-demand-parsing.cpp
33
clang/test/Analysis/ctu-onego-toplevel.cpp
25

Are the lines below related to the execution of the command above? If not, could you please break the comment?

29
31

One-go? And what does that refer to? Is "Onego" analysis the one this patch is introducing?

martong edited the summary of this revision. (Show Details)May 13 2022, 2:26 AM
martong marked 15 inline comments as done.
martong added inline comments.
clang/include/clang/AST/ASTImporterSharedState.h
83 ↗(On Diff #428055)

Good point, markAsNewDecl sounds better. I'll update this in the parent patch https://reviews.llvm.org/D123685 though (and rebase this).

clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def
414–420

Thanks, this is so true, very good point. I've changed it. And also changed the name to suffix -pct instead of -mul to reflect this.

clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
141

Yes, this is only for the analyzer.

141

This is the direct representation of the analyzer option ctu-phase1-inlining and there is a bulky documentation for that in AnalyzerOptions.def. I'd rather not repeat that documentation here.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
815–817

Yep, very good point, thanks again. Changed it with the inverted branch version.

clang/test/Analysis/Inputs/ctu-onego-existingdef-other.cpp.externalDefMap.ast-dump.txt
2

Good catch. I've added the other function. Besides, I had the wrong filename provided, it should have been ctu-onego-existingdef-other.cpp.ast, the existingdef was missing. Fixed that too, plus added and extra FileCheck to the existingdef test that detects if the ast file is not loaded.

clang/test/Analysis/ctu-onego-toplevel.cpp
31

Yes. I've updated the summary of the patch to make this clear.

martong updated this revision to Diff 429172.May 13 2022, 2:28 AM
martong marked 7 inline comments as done.
  • Change -mul to -pct
  • Change default values to ctu-max-nodes-pct = 50 and ctu-max-nodes-min = 10000
  • Rename isCTUInFirtstPhase to isSecondPhaseCTU and invert the condition
  • Check that the AST file is loaded in existingdef test file
  • Set CTUWlist as nullptr in single-TU mode
  • Add bar to ctu-onego-existingdef-other.cpp.externalDefMap.ast-dump.txt
  • Changes in comments of test files
xazax.hun added inline comments.May 13 2022, 8:38 AM
clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
446

Actually, in this case I wonder whether we really need a set of declarations. Wouldn't a boolean be sufficient for each path?

So in case of:

foreign1(true);
foreign2(false);

Why would we want to add foreign2 to the CTU worklist? More specifically, why is it important whether a foreign call is actually the same declaration that we saw earlier on the path? Isn't being foreign the only important information in this case?

martong marked an inline comment as done.May 17 2022, 6:15 AM
martong added inline comments.
clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
446

Good point.

By using the set of declarations we might have a path where foreign1 is conservatively evaluated and then foreign2 is inlined. I was having a hard time to find any use-cases where this would be useful, but could not find one.

On the other hand, by using a bool, as you suggest, no such superfluous path would exist. Plus, the dependent child patch (D123784) is becoming unnecessary because the CTUWorklist will have at most one element during the first phase.

Besides, I've made measurements comparing the bool and the set implementation. The results are quite similar. Both have lost the same amount of bugreports compared to the single-tu analysis and the average length of the bugpaths are also similar.

martong updated this revision to Diff 430023.May 17 2022, 6:24 AM
martong marked an inline comment as done.
  • Change ctuBifurcate to use bool in GDM
martong updated this revision to Diff 430047.May 17 2022, 7:04 AM
  • Update ReleaseNotes.rst
xazax.hun accepted this revision.May 17 2022, 9:00 AM
xazax.hun added inline comments.
clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
446

Great news! :) Looks like this was a nice simplification, thanks for looking into it!

xazax.hun added inline comments.May 17 2022, 9:02 AM
clang/docs/ReleaseNotes.rst
487

I wonder if you also want to mention that this still finds most of the CTU findings in most cases.

martong marked an inline comment as done.May 18 2022, 1:25 AM
martong added inline comments.
clang/docs/ReleaseNotes.rst
487

Yes, I do, thanks.

This revision was landed with ongoing or failed builds.May 18 2022, 1:37 AM
This revision was automatically updated to reflect the committed changes.
martong marked an inline comment as done.