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

[martong]

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

[martong]

clang/test/Analysis/ctu-main.cpp

161

This FIXME is outdated, got here during rebase.

[martong]

clang/lib/StaticAnalyzer/Core/CoreEngine.cpp

167

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

[xazax.hun]

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

• 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]

• Chosing the correct baseline this time

[martong]

clang/test/Analysis/ctu-on-demand-parsing.c

23

[martong]

• 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]

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]

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]

• 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]

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]

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]

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]

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]

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.

[martong]

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]

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]

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]

• 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]

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]

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.

stats.html226 KBDownload

[martong]

• Change ctuBifurcate to use bool in GDM

[martong]

• Update ReleaseNotes.rst

[xazax.hun]

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp

446

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

[xazax.hun]

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]

clang/docs/ReleaseNotes.rst

487

Yes, I do, thanks.

clang/docs/ReleaseNotes.rst

 
 libclang
 --------
 
 - ...
 
 Static Analyzer
 ---------------
+- `New CTU implementation
+  <https://discourse.llvm.org/t/rfc-much-faster-cross-translation-unit-ctu-analysis-implementation/61728>`_
+  that keeps the slow-down around 2x compared to the single-TU analysis, even
+  in case of complex C++ projects. Still, it finds the majority of the "old"
+  CTU findings. Besides, not more than ~3% of the bug reports are lost compared
+  to single-TU analysis, the lost reports are highly likely to be false
+  positives.
 
 - Added a new checker ``alpha.unix.cstring.UninitializedRead`` this will check for uninitialized reads
   from common memory copy/manipulation functions such as ``memcpy``, ``mempcpy``, ``memmove``, ``memcmp``, `
   `strcmp``, ``strncmp``, ``strcpy``, ``strlen``, ``strsep`` and many more. Although 
   this checker currently is in list of alpha checkers due to a false positive.
 
 .. _release-notes-ubsan:
 

clang/include/clang/CrossTU/CrossTranslationUnit.h

public:
   /// \note If any error happens such as \p ToLoc is a non-imported
   ///       source-location, empty is returned.
   /// \note Macro expansion tracking for imported TUs is not implemented yet.
   ///       It returns empty unconditionally.
   llvm::Optional<clang::MacroExpansionContext>
   getMacroExpansionContextForSourceLocation(
       const clang::SourceLocation &ToLoc) const;
 
+  /// Returns true if the given Decl is newly created during the import.
+  bool isImportedAsNew(const Decl *ToDecl) const;
+
+  /// Returns true if the given Decl is mapped (or created) during an import
+  /// but there was an unrecoverable error (the AST node cannot be erased, it
+  /// is marked with an Error object in this case).
+  bool hasError(const Decl *ToDecl) const;
+
 private:
   void lazyInitImporterSharedSt(TranslationUnitDecl *ToTU);
   ASTImporter &getOrCreateASTImporter(ASTUnit *Unit);
   template <typename T>
   llvm::Expected<const T *> getCrossTUDefinitionImpl(const T *D,
                                                      StringRef CrossTUDir,
                                                      StringRef IndexName,
                                                      bool DisplayCTUProgress);

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

 enum UserModeKind {
   /// Perform shallow but fast analyzes.
   UMK_Shallow = 1,
 
   /// Perform deep analyzes.
   UMK_Deep = 2
 };
 
+enum class CTUPhase1InliningKind { None, Small, All };
+
 /// Stores options for the analyzer from the command line.
 ///
 /// Some options are frontend flags (e.g.: -analyzer-output), but some are
 /// analyzer configuration options, which are preceded by -analyzer-config
 /// (e.g.: -analyzer-config notes-as-events=true).
 ///
 /// If you'd like to add a new frontend flag, add it to
 /// include/clang/Driver/CC1Options.td, add a new field to store the value of
StringRef getCheckerStringOption(const ento::CheckerBase *C,
                                    bool SearchInParents = false) const;
 
   /// Retrieves and sets the UserMode. This is a high-level option,
   /// which is used to set other low-level options. It is not accessible
   /// outside of AnalyzerOptions.
   UserModeKind getUserMode() const;
 
   ExplorationStrategyKind getExplorationStrategy() const;
+  CTUPhase1InliningKind getCTUPhase1Inlining() const;
 
   /// Returns the inter-procedural analysis mode.
   IPAKind getIPAMode() const;
 
   /// Returns the option controlling which C++ member functions will be
   /// considered for inlining.
   ///
   /// This is controlled by the 'c++-inlining' config option.

clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def

 
 ANALYZER_OPTION_DEPENDS_ON_USER_MODE(
     unsigned, MaxNodesPerTopLevelFunction, "max-nodes",
     "The maximum number of nodes the analyzer can generate while exploring a "
     "top level function (for each exploded graph). 0 means no limit.",
     /* SHALLOW_VAL */ 75000, /* DEEP_VAL */ 225000)
 
 ANALYZER_OPTION(
+    unsigned, CTUMaxNodesPercentage, "ctu-max-nodes-pct",
+    "The percentage of single-TU analysed nodes that the CTU analysis is "
+    "allowed to visit.", 50)
+
+ANALYZER_OPTION(
+    unsigned, CTUMaxNodesMin, "ctu-max-nodes-min",
+    "The maximum number of nodes in CTU mode is determinded by "
+    "'ctu-max-nodes-pct'. However, if the number of nodes in single-TU "
+    "analysis is too low, it is meaningful to provide a minimum value that "
+    "serves as an upper bound instead.", 10000)
+
+ANALYZER_OPTION(
+    StringRef, CTUPhase1InliningMode, "ctu-phase1-inlining",
+    "Controls which functions will be inlined during the first phase of the ctu "
+    "analysis. "
+    "If the value is set to 'all' then all foreign functions are inlinied "
+    "immediately during the first phase, thus rendering the second phase a noop. "
+    "The 'ctu-max-nodes-*' budge has no effect in this case. "
+    "If the value is 'small' then only functions with a linear CFG and with a "
+    "limited number of statements would be inlined during the first phase. The "
+    "long and/or nontrivial functions are handled in the second phase and are "
+    "controlled by the 'ctu-max-nodes-*' budge. "
+    "The value 'none' means that all foreign functions are inlined only in the "
+    "second phase, 'ctu-max-nodes-*' budge limits the second phase. "
+    "Value: \"none\", \"small\", \"all\".",
+    "small")
+
+ANALYZER_OPTION(
     unsigned, RegionStoreSmallStructLimit, "region-store-small-struct-limit",
     "The largest number of fields a struct can have and still be considered "
     "small This is currently used to decide whether or not it is worth forcing "
     "a LazyCompoundVal on bind. To disable all small-struct-dependent "
     "behavior, set the option to 0.",
     2)
 
 //===----------------------------------------------------------------------===//

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

class RuntimeDefinition {
   const Decl *D = nullptr;
 
   /// The region representing an object (ObjC/C++) on which the method is
   /// called. With dynamic dispatch, the method definition depends on the
   /// runtime type of this object. NULL when the DynamicTypeInfo is
   /// precise.
   const MemRegion *R = nullptr;
 
+  /// A definition is foreign if it has been imported and newly created by the
+  /// ASTImporter. This can be true only if CTU is enabled.
+  const bool Foreign = false;
+
 public:
   RuntimeDefinition() = default;
   RuntimeDefinition(const Decl *InD): D(InD) {}
+  RuntimeDefinition(const Decl *InD, bool Foreign) : D(InD), Foreign(Foreign) {}
   RuntimeDefinition(const Decl *InD, const MemRegion *InR): D(InD), R(InR) {}
 
   const Decl *getDecl() { return D; }
+  bool isForeign() const { return Foreign; }
 
   /// Check if the definition we have is precise.
   /// If not, it is possible that the call dispatches to another definition at
   /// execution time.
   bool mayHaveOtherDefinitions() { return R != nullptr; }
 
   /// When other definitions are possible, returns the region whose runtime type
   /// determines the method definition.

 class CallEvent {
 public:
   using Kind = CallEventKind;
 
 private:
   ProgramStateRef State;
   const LocationContext *LCtx;
   llvm::PointerUnion<const Expr *, const Decl *> Origin;
+  mutable Optional<bool> Foreign; // Set by CTU analysis.
 
 protected:
   // This is user data for subclasses.
   const void *Data;
 
   // This is user data for subclasses.
   // This should come right before RefCount, so that the two fields can be
   // packed together on LP64 platforms.
public:
   virtual StringRef getKindAsString() const = 0;
 
   /// Returns the declaration of the function or method that will be
   /// called. May be null.
   virtual const Decl *getDecl() const {
     return Origin.dyn_cast<const Decl *>();
   }
 
+  bool isForeign() const {
+    assert(Foreign.hasValue() && "Foreign must be set before querying");
+    return *Foreign;
+  }
+  void setForeign(bool B) const { Foreign = B; }
+
   /// The state in which the call is being evaluated.
   const ProgramStateRef &getState() const {
     return State;
   }
 
   /// The context in which the call is being evaluated.
   const LocationContext *getLocationContext() const {
     return LCtx;

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

private:
 
   /// G - The simulation graph.  Each node is a (location,state) pair.
   mutable ExplodedGraph G;
 
   /// WList - A set of queued nodes that need to be processed by the
   ///  worklist algorithm.  It is up to the implementation of WList to decide
   ///  the order that nodes are processed.
   std::unique_ptr<WorkList> WList;
+  std::unique_ptr<WorkList> CTUWList;
 
   /// BCounterFactory - A factory object for created BlockCounter objects.
   ///   These are used to record for key nodes in the ExplodedGraph the
   ///   number of times different CFGBlocks have been visited along a path.
   BlockCounter::Factory BCounterFactory;
 
   /// The locations where we stopped doing work because we visited a location
   ///  too many times.
   BlocksExhausted blocksExhausted;
 
   /// The locations where we stopped because the engine aborted analysis,
   /// usually because it could not reason about something.
   BlocksAborted blocksAborted;
 
   /// The information about functions shared by the whole translation unit.
   /// (This data is owned by AnalysisConsumer.)
   FunctionSummariesTy *FunctionSummaries;
 
   /// Add path tags with some useful data along the path when we see that
   /// something interesting is happening. This field is the allocator for such
   /// tags.
   DataTag::Factory DataTags;
 
+  void setBlockCounter(BlockCounter C);
+
   void generateNode(const ProgramPoint &Loc,
                     ProgramStateRef State,
                     ExplodedNode *Pred);
 
   void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
   void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
   void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
 
public:
 
   /// Inform the CoreEngine that a basic block was aborted because
   /// it could not be completely analyzed.
   void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
     blocksAborted.push_back(std::make_pair(block, node));
   }
 
   WorkList *getWorkList() const { return WList.get(); }
+  WorkList *getCTUWorkList() const { return CTUWList.get(); }
 
   BlocksExhausted::const_iterator blocks_exhausted_begin() const {
     return blocksExhausted.begin();
   }
 
   BlocksExhausted::const_iterator blocks_exhausted_end() const {
     return blocksExhausted.end();
   }

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

enum InliningModes {
     Inline_Regular = 0,
 
     /// Do minimal inlining of callees.
     Inline_Minimal = 0x1
   };
 
 private:
   cross_tu::CrossTranslationUnitContext &CTU;
+  bool IsCTUEnabled;
 
   AnalysisManager &AMgr;
 
   AnalysisDeclContextManager &AnalysisDeclContexts;
 
   CoreEngine Engine;
 
   /// G - the simulation graph.
private:
   /// should inline, just by looking at the declaration of the function.
   bool mayInlineDecl(AnalysisDeclContext *ADC) const;
 
   /// Checks our policies and decides weither the given call should be inlined.
   bool shouldInlineCall(const CallEvent &Call, const Decl *D,
                         const ExplodedNode *Pred,
                         const EvalCallOptions &CallOpts = {});
 
-  bool inlineCall(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
+  void inlineCall(WorkList *WList, const CallEvent &Call, const Decl *D,
+                  NodeBuilder &Bldr, ExplodedNode *Pred, ProgramStateRef State);
+
+  void ctuBifurcate(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
                     ExplodedNode *Pred, ProgramStateRef State);
 
+  /// Returns true if the CTU analysis is running its second phase.
+  bool isSecondPhaseCTU() { return IsCTUEnabled && !Engine.getCTUWorkList(); }
+
   /// Conservatively evaluate call by invalidating regions and binding
   /// a conjured return value.
   void conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr,
                             ExplodedNode *Pred, ProgramStateRef State);
 
   /// Either inline or process the call conservatively (or both), based
   /// on DynamicDispatchBifurcation data.
   void BifurcateCall(const MemRegion *BifurReg,

clang/lib/CrossTU/CrossTranslationUnit.cpp

 
 llvm::Optional<clang::MacroExpansionContext>
 CrossTranslationUnitContext::getMacroExpansionContextForSourceLocation(
     const clang::SourceLocation &ToLoc) const {
   // FIXME: Implement: Record such a context for every imported ASTUnit; lookup.
   return llvm::None;
 }
 
+bool CrossTranslationUnitContext::isImportedAsNew(const Decl *ToDecl) const {
+  if (!ImporterSharedSt)
+    return false;
+  return ImporterSharedSt->isNewDecl(const_cast<Decl *>(ToDecl));
+}
+
+bool CrossTranslationUnitContext::hasError(const Decl *ToDecl) const {
+  if (!ImporterSharedSt)
+    return false;
+  return static_cast<bool>(
+      ImporterSharedSt->getImportDeclErrorIfAny(const_cast<Decl *>(ToDecl)));
+}
+
 } // namespace cross_tu
 } // namespace clang

clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

llvm::StringSwitch<llvm::Optional<ExplorationStrategyKind>>(
                 ExplorationStrategyKind::UnexploredFirstLocationQueue)
           .Case("bfs_block_dfs_contents",
                 ExplorationStrategyKind::BFSBlockDFSContents)
           .Default(None);
   assert(K.hasValue() && "User mode is invalid.");
   return K.getValue();
 }
 
+CTUPhase1InliningKind AnalyzerOptions::getCTUPhase1Inlining() const {
+  auto K = llvm::StringSwitch<llvm::Optional<CTUPhase1InliningKind>>(
+               CTUPhase1InliningMode)
+               .Case("none", CTUPhase1InliningKind::None)
+               .Case("small", CTUPhase1InliningKind::Small)
+               .Case("all", CTUPhase1InliningKind::All)
+               .Default(None);
+  assert(K.hasValue() && "CTU inlining mode is invalid.");
+  return K.getValue();
+}
+
 IPAKind AnalyzerOptions::getIPAMode() const {
   auto K = llvm::StringSwitch<llvm::Optional<IPAKind>>(IPAMode)
           .Case("none", IPAK_None)
           .Case("basic-inlining", IPAK_BasicInlining)
           .Case("inlining", IPAK_Inlining)
           .Case("dynamic", IPAK_DynamicDispatch)
           .Case("dynamic-bifurcate", IPAK_DynamicDispatchBifurcate)
           .Default(None);

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

AnalysisDeclContext *AD =
     getManager()->getContext(FD);
   bool IsAutosynthesized;
   Stmt* Body = AD->getBody(IsAutosynthesized);
   LLVM_DEBUG({
     if (IsAutosynthesized)
       llvm::dbgs() << "Using autosynthesized body for " << FD->getName()
                    << "\n";
   });
-  if (Body) {
-    const Decl* Decl = AD->getDecl();
-    return RuntimeDefinition(Decl);
-  }
 
   ExprEngine &Engine = getState()->getStateManager().getOwningEngine();
+  cross_tu::CrossTranslationUnitContext &CTUCtx =
+      *Engine.getCrossTranslationUnitContext();
+
   AnalyzerOptions &Opts = Engine.getAnalysisManager().options;
 
+  if (Body) {
+    const Decl* Decl = AD->getDecl();
+    if (Opts.IsNaiveCTUEnabled && CTUCtx.isImportedAsNew(Decl)) {
+      // A newly created definition, but we had error(s) during the import.
+      if (CTUCtx.hasError(Decl))
+        return {};
+      return RuntimeDefinition(Decl, /*Foreign=*/true);
+    }
+    return RuntimeDefinition(Decl, /*Foreign=*/false);
+  }
+
   // Try to get CTU definition only if CTUDir is provided.
   if (!Opts.IsNaiveCTUEnabled)
     return {};
 
-  cross_tu::CrossTranslationUnitContext &CTUCtx =
-      *Engine.getCrossTranslationUnitContext();
   llvm::Expected<const FunctionDecl *> CTUDeclOrError =
       CTUCtx.getCrossTUDefinition(FD, Opts.CTUDir, Opts.CTUIndexName,
                                   Opts.DisplayCTUProgress);
 
   if (!CTUDeclOrError) {
     handleAllErrors(CTUDeclOrError.takeError(),
                     [&](const cross_tu::IndexError &IE) {
                       CTUCtx.emitCrossTUDiagnostics(IE);
                     });
     return {};
   }
 
-  return RuntimeDefinition(*CTUDeclOrError);
+  return RuntimeDefinition(*CTUDeclOrError, /*Foreign=*/true);
 }
 
 void AnyFunctionCall::getInitialStackFrameContents(
                                         const StackFrameContext *CalleeCtx,
                                         BindingsTy &Bindings) const {
   const auto *D = cast<FunctionDecl>(CalleeCtx->getDecl());
   SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
   addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,

clang/lib/StaticAnalyzer/Core/CoreEngine.cpp

 
 using namespace clang;
 using namespace ento;
 
 #define DEBUG_TYPE "CoreEngine"
 
 STATISTIC(NumSteps,
             "The # of steps executed.");
+STATISTIC(NumSTUSteps, "The # of STU steps executed.");
+STATISTIC(NumCTUSteps, "The # of CTU steps executed.");
 STATISTIC(NumReachedMaxSteps,
             "The # of times we reached the max number of steps.");
 STATISTIC(NumPathsExplored,
             "The # of paths explored by the analyzer.");
 
 //===----------------------------------------------------------------------===//
 // Core analysis engine.
 //===----------------------------------------------------------------------===//
case ExplorationStrategyKind::UnexploredFirstLocationQueue:
       return WorkList::makeUnexploredFirstPriorityLocationQueue();
   }
   llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind");
 }
 
 CoreEngine::CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS,
                        AnalyzerOptions &Opts)
     : ExprEng(exprengine), WList(generateWorkList(Opts)),
+      CTUWList(Opts.IsNaiveCTUEnabled ? generateWorkList(Opts) : nullptr),
       BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
 
+void CoreEngine::setBlockCounter(BlockCounter C) {
+  WList->setBlockCounter(C);
+  if (CTUWList)
+    CTUWList->setBlockCounter(C);
+}
+
 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
-bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
-                                   ProgramStateRef InitState) {
+bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned MaxSteps,
   if (G.num_roots() == 0) { // Initialize the analysis by constructing
     // the root if none exists.
 
     const CFGBlock *Entry = &(L->getCFG()->getEntry());
 
     assert(Entry->empty() && "Entry block must be empty.");
 
     assert(Entry->succ_size() == 1 && "Entry block must have 1 successor.");
 
     // Mark the entry block as visited.
     FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),
                                              L->getDecl(),
                                              L->getCFG()->getNumBlockIDs());
 
     // Get the solitary successor.
     const CFGBlock *Succ = *(Entry->succ_begin());
 
     // Construct an edge representing the
     // starting location in the function.
     BlockEdge StartLoc(Entry, Succ, L);
 
     // Set the current block counter to being empty.
-    WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
+    setBlockCounter(BCounterFactory.GetEmptyCounter());
 
     if (!InitState)
       InitState = ExprEng.getInitialState(L);
 
     bool IsNew;
     ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);
     assert(IsNew);
     G.addRoot(Node);
 
     NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
     ExplodedNodeSet DstBegin;
     ExprEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);
 
     enqueue(DstBegin);
   }
 
   // Check if we have a steps limit
-  bool UnlimitedSteps = Steps == 0;
+  bool UnlimitedSteps = MaxSteps == 0;
+
   // Cap our pre-reservation in the event that the user specifies
   // a very large number of maximum steps.
   const unsigned PreReservationCap = 4000000;
   if(!UnlimitedSteps)
-    G.reserve(std::min(Steps,PreReservationCap));
+    G.reserve(std::min(MaxSteps, PreReservationCap));
 
+  auto ProcessWList = [this, UnlimitedSteps](unsigned MaxSteps) {
+    unsigned Steps = MaxSteps;
     while (WList->hasWork()) {
       if (!UnlimitedSteps) {
         if (Steps == 0) {
           NumReachedMaxSteps++;
           break;
         }
         --Steps;
       }
 
       NumSteps++;
 
-    const WorkListUnit& WU = WList->dequeue();
+      const WorkListUnit &WU = WList->dequeue();
 
       // Set the current block counter.
-    WList->setBlockCounter(WU.getBlockCounter());
+      setBlockCounter(WU.getBlockCounter());
 
       // Retrieve the node.
       ExplodedNode *Node = WU.getNode();
 
       dispatchWorkItem(Node, Node->getLocation(), WU);
     }
+    return MaxSteps - Steps;
+  };
+  const unsigned STUSteps = ProcessWList(MaxSteps);
+
+  if (CTUWList) {
+    NumSTUSteps += STUSteps;
+    const unsigned MinCTUSteps =
+        this->ExprEng.getAnalysisManager().options.CTUMaxNodesMin;
+    const unsigned Pct =
+        this->ExprEng.getAnalysisManager().options.CTUMaxNodesPercentage;
+    unsigned MaxCTUSteps = std::max(STUSteps * Pct / 100, MinCTUSteps);
+
+    WList = std::move(CTUWList);
+    const unsigned CTUSteps = ProcessWList(MaxCTUSteps);
+    NumCTUSteps += CTUSteps;
+  }
+
   ExprEng.processEndWorklist();
   return WList->hasWork();
 }
 
 void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
                                   const WorkListUnit& WU) {
   // Dispatch on the location type.
   switch (Loc.getKind()) {

 void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
                                        ExplodedNode *Pred) {
   // Increment the block counter.
   const LocationContext *LC = Pred->getLocationContext();
   unsigned BlockId = L.getBlock()->getBlockID();
   BlockCounter Counter = WList->getBlockCounter();
   Counter = BCounterFactory.IncrementCount(Counter, LC->getStackFrame(),
                                            BlockId);
-  WList->setBlockCounter(Counter);
+  setBlockCounter(Counter);
 
   // Process the entrance of the block.
   if (Optional<CFGElement> E = L.getFirstElement()) {
     NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
     ExprEng.processCFGElement(*E, Pred, 0, &Ctx);
   }
   else
     HandleBlockExit(L.getBlock(), Pred);

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

 
 //===----------------------------------------------------------------------===//
 // Engine construction and deletion.
 //===----------------------------------------------------------------------===//
 
 static const char* TagProviderName = "ExprEngine";
 
 ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU,
-                       AnalysisManager &mgr,
-                       SetOfConstDecls *VisitedCalleesIn,
-                       FunctionSummariesTy *FS,
-                       InliningModes HowToInlineIn)
-    : CTU(CTU), AMgr(mgr),
-      AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
+                       AnalysisManager &mgr, SetOfConstDecls *VisitedCalleesIn,
+                       FunctionSummariesTy *FS, InliningModes HowToInlineIn)
+    : CTU(CTU), IsCTUEnabled(mgr.getAnalyzerOptions().IsNaiveCTUEnabled),
+      AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
       Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()),
       StateMgr(getContext(), mgr.getStoreManagerCreator(),
-               mgr.getConstraintManagerCreator(), G.getAllocator(),
-               this),
-      SymMgr(StateMgr.getSymbolManager()),
-      MRMgr(StateMgr.getRegionManager()),
-      svalBuilder(StateMgr.getSValBuilder()),
-      ObjCNoRet(mgr.getASTContext()),
-      BR(mgr, *this),
-      VisitedCallees(VisitedCalleesIn),
-      HowToInline(HowToInlineIn)
-  {
+               mgr.getConstraintManagerCreator(), G.getAllocator(), this),
+      SymMgr(StateMgr.getSymbolManager()), MRMgr(StateMgr.getRegionManager()),
+      svalBuilder(StateMgr.getSValBuilder()), ObjCNoRet(mgr.getASTContext()),
+      BR(mgr, *this), VisitedCallees(VisitedCalleesIn),
+      HowToInline(HowToInlineIn) {
   unsigned TrimInterval = mgr.options.GraphTrimInterval;
   if (TrimInterval != 0) {
     // Enable eager node reclamation when constructing the ExplodedGraph.
     G.enableNodeReclamation(TrimInterval);
   }
 }
 
 //===----------------------------------------------------------------------===//

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp

namespace {
   enum DynamicDispatchMode {
     DynamicDispatchModeInlined = 1,
     DynamicDispatchModeConservative
   };
 } // end anonymous namespace
 
 REGISTER_MAP_WITH_PROGRAMSTATE(DynamicDispatchBifurcationMap,
                                const MemRegion *, unsigned)
+REGISTER_TRAIT_WITH_PROGRAMSTATE(CTUDispatchBifurcation, bool)
 
-bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D,
+void ExprEngine::ctuBifurcate(const CallEvent &Call, const Decl *D,
                               NodeBuilder &Bldr, ExplodedNode *Pred,
                               ProgramStateRef State) {
+  ProgramStateRef ConservativeEvalState = nullptr;
+  if (Call.isForeign() && !isSecondPhaseCTU()) {
+    const auto IK = AMgr.options.getCTUPhase1Inlining();
+    const bool DoInline = IK == CTUPhase1InliningKind::All ||
+                          (IK == CTUPhase1InliningKind::Small &&
+                           isSmall(AMgr.getAnalysisDeclContext(D)));
+    if (DoInline) {
+      inlineCall(Engine.getWorkList(), Call, D, Bldr, Pred, State);
+      return;
+    }
+    const bool BState = State->get<CTUDispatchBifurcation>();
+    if (!BState) { // This is the first time we see this foreign function.
+      // Enqueue it to be analyzed in the second (ctu) phase.
+      inlineCall(Engine.getCTUWorkList(), Call, D, Bldr, Pred, State);
+      // Conservatively evaluate in the first phase.
+      ConservativeEvalState = State->set<CTUDispatchBifurcation>(true);
+      conservativeEvalCall(Call, Bldr, Pred, ConservativeEvalState);
+    } else {
+      conservativeEvalCall(Call, Bldr, Pred, State);
+    }
+    return;
+  }
+  inlineCall(Engine.getWorkList(), Call, D, Bldr, Pred, State);
+}
+
+void ExprEngine::inlineCall(WorkList *WList, const CallEvent &Call,
+                            const Decl *D, NodeBuilder &Bldr,
+                            ExplodedNode *Pred, ProgramStateRef State) {
   assert(D);
 
   const LocationContext *CurLC = Pred->getLocationContext();
   const StackFrameContext *CallerSFC = CurLC->getStackFrame();
   const LocationContext *ParentOfCallee = CallerSFC;
   if (Call.getKind() == CE_Block &&
       !cast<BlockCall>(Call).isConversionFromLambda()) {
     const BlockDataRegion *BR = cast<BlockCall>(Call).getBlockRegion();
void ExprEngine::inlineCall(WorkList *WList, const CallEvent &Call,
   // Construct a new state which contains the mapping from actual to
   // formal arguments.
   State = State->enterStackFrame(Call, CalleeSFC);
 
   bool isNew;
   if (ExplodedNode *N = G.getNode(Loc, State, false, &isNew)) {
     N->addPredecessor(Pred, G);
     if (isNew)
-      Engine.getWorkList()->enqueue(N);
+      WList->enqueue(N);
   }
 
   // If we decided to inline the call, the successor has been manually
   // added onto the work list so remove it from the node builder.
   Bldr.takeNodes(Pred);
 
   NumInlinedCalls++;
   Engine.FunctionSummaries->bumpNumTimesInlined(D);
 
+  // Do not mark as visited in the 2nd run (CTUWList), so the function will
+  // be visited as top-level, this way we won't loose reports in non-ctu
+  // mode. Considering the case when a function in a foreign TU calls back
+  // into the main TU.
+  // Note, during the 1st run, it doesn't matter if we mark the foreign
+  // functions as visited (or not) because they can never appear as a top level
+  // function in the main TU.
+  if (!isSecondPhaseCTU())
     // Mark the decl as visited.
     if (VisitedCallees)
       VisitedCallees->insert(D);
-
-  return true;
 }
 
 static ProgramStateRef getInlineFailedState(ProgramStateRef State,
                                             const Stmt *CallE) {
   const void *ReplayState = State->get<ReplayWithoutInlining>();
   if (!ReplayState)
     return nullptr;
 
void ExprEngine::defaultEvalCall(NodeBuilder &Bldr, ExplodedNode *Pred,
   const Expr *E = Call->getOriginExpr();
 
   ProgramStateRef InlinedFailedState = getInlineFailedState(State, E);
   if (InlinedFailedState) {
     // If we already tried once and failed, make sure we don't retry later.
     State = InlinedFailedState;
   } else {
     RuntimeDefinition RD = Call->getRuntimeDefinition();
+    Call->setForeign(RD.isForeign());
     const Decl *D = RD.getDecl();
     if (shouldInlineCall(*Call, D, Pred, CallOpts)) {
       if (RD.mayHaveOtherDefinitions()) {
         AnalyzerOptions &Options = getAnalysisManager().options;
 
         // Explore with and without inlining the call.
         if (Options.getIPAMode() == IPAK_DynamicDispatchBifurcate) {
           BifurcateCall(RD.getDispatchRegion(), *Call, D, Bldr, Pred);
           return;
         }
 
         // Don't inline if we're not in any dynamic dispatch mode.
         if (Options.getIPAMode() != IPAK_DynamicDispatch) {
           conservativeEvalCall(*Call, Bldr, Pred, State);
           return;
         }
       }
-
-      // We are not bifurcating and we do have a Decl, so just inline.
-      if (inlineCall(*Call, D, Bldr, Pred, State))
-        return;
+      ctuBifurcate(*Call, D, Bldr, Pred, State);
     }
   }
 
   // If we can't inline it, handle the return value and invalidate the regions.
   conservativeEvalCall(*Call, Bldr, Pred, State);
 }
 
 void ExprEngine::BifurcateCall(const MemRegion *BifurReg,
                                const CallEvent &Call, const Decl *D,
                                NodeBuilder &Bldr, ExplodedNode *Pred) {
   assert(BifurReg);
   BifurReg = BifurReg->StripCasts();
 
   // Check if we've performed the split already - note, we only want
   // to split the path once per memory region.
   ProgramStateRef State = Pred->getState();
   const unsigned *BState =
                         State->get<DynamicDispatchBifurcationMap>(BifurReg);
   if (BState) {
     // If we are on "inline path", keep inlining if possible.
     if (*BState == DynamicDispatchModeInlined)
-      if (inlineCall(Call, D, Bldr, Pred, State))
-        return;
+      ctuBifurcate(Call, D, Bldr, Pred, State);
     // If inline failed, or we are on the path where we assume we
     // don't have enough info about the receiver to inline, conjure the
     // return value and invalidate the regions.
     conservativeEvalCall(Call, Bldr, Pred, State);
     return;
   }
 
   // If we got here, this is the first time we process a message to this
   // region, so split the path.
   ProgramStateRef IState =
       State->set<DynamicDispatchBifurcationMap>(BifurReg,
                                                DynamicDispatchModeInlined);
-  inlineCall(Call, D, Bldr, Pred, IState);
+  ctuBifurcate(Call, D, Bldr, Pred, IState);
 
   ProgramStateRef NoIState =
       State->set<DynamicDispatchBifurcationMap>(BifurReg,
                                                DynamicDispatchModeConservative);
   conservativeEvalCall(Call, Bldr, Pred, NoIState);
 
   NumOfDynamicDispatchPathSplits++;
 }

clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp

for (auto &N : RPOT) {
     if (!D)
       continue;
 
     // Skip the functions which have been processed already or previously
     // inlined.
     if (shouldSkipFunction(D, Visited, VisitedAsTopLevel))
       continue;
 
+    // The CallGraph might have declarations as callees. However, during CTU
+    // the declaration might form a declaration chain with the newly imported
+    // definition from another TU. In this case we don't want to analyze the
+    // function definition as toplevel.
+    if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
+      // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl
+      // that has the body.
+      FD->hasBody(FD);
+      if (CTU.isImportedAsNew(FD))
+        continue;
+    }
+
     // Analyze the function.
     SetOfConstDecls VisitedCallees;
 
     HandleCode(D, AM_Path, getInliningModeForFunction(D, Visited),
                (Mgr->options.InliningMode == All ? nullptr : &VisitedCallees));
 
     // Add the visited callees to the global visited set.
     for (const Decl *Callee : VisitedCallees)

clang/test/Analysis/Inputs/ctu-onego-existingdef-other.cpp

+int bar() {
+  return 0;
+}
+
+void other() {
+  bar();
+}

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

+9:c:@F@bar# ctu-onego-existingdef-other.cpp.ast
+11:c:@F@other# ctu-onego-existingdef-other.cpp.ast

clang/test/Analysis/Inputs/ctu-onego-indirect-other.cpp

+int bar() {
+  return 0;
+}
+
+void other() {
+  bar();
+}

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

+11:c:@F@other# ctu-onego-indirect-other.cpp.ast
+9:c:@F@bar# ctu-onego-indirect-other.cpp.ast

clang/test/Analysis/Inputs/ctu-onego-small-other.cpp

+int bar() {
+  return 0;
+}

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

+9:c:@F@bar# ctu-onego-small-other.cpp.ast

clang/test/Analysis/Inputs/ctu-onego-toplevel-other.cpp

+void b(int x);
+void other(int y) {
+  b(1);
+}

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

+13:c:@F@other#I# ctu-onego-toplevel-other.cpp.ast

clang/test/Analysis/analyzer-config.c

 // CHECK-NEXT: cplusplus.Move:WarnOn = KnownsAndLocals
 // CHECK-NEXT: cplusplus.SmartPtrModeling:ModelSmartPtrDereference = false
 // CHECK-NEXT: crosscheck-with-z3 = false
 // CHECK-NEXT: ctu-dir = ""
 // CHECK-NEXT: ctu-import-cpp-threshold = 8
 // CHECK-NEXT: ctu-import-threshold = 24
 // CHECK-NEXT: ctu-index-name = externalDefMap.txt
 // CHECK-NEXT: ctu-invocation-list = invocations.yaml
+// CHECK-NEXT: ctu-max-nodes-min = 10000
+// CHECK-NEXT: ctu-max-nodes-pct = 50
+// CHECK-NEXT: ctu-phase1-inlining = small
 // CHECK-NEXT: deadcode.DeadStores:ShowFixIts = false
 // CHECK-NEXT: deadcode.DeadStores:WarnForDeadNestedAssignments = true
 // CHECK-NEXT: debug.AnalysisOrder:* = false
 // CHECK-NEXT: debug.AnalysisOrder:Bind = false
 // CHECK-NEXT: debug.AnalysisOrder:EndAnalysis = false
 // CHECK-NEXT: debug.AnalysisOrder:EndFunction = false
 // CHECK-NEXT: debug.AnalysisOrder:EvalCall = false
 // CHECK-NEXT: debug.AnalysisOrder:LiveSymbols = false

clang/test/Analysis/ctu-implicit.c

 // RUN: rm -rf %t && mkdir %t
 // RUN: mkdir -p %t/ctudir2
 // RUN: %clang_cc1  \
 // RUN:   -emit-pch -o %t/ctudir2/ctu-import.c.ast %S/Inputs/ctu-import.c
 // RUN: cp %S/Inputs/ctu-import.c.externalDefMap.ast-dump.txt %t/ctudir2/externalDefMap.txt
 // RUN: %clang_cc1 -analyze \
 // RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
 // RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
 // RUN:   -analyzer-config  display-ctu-progress=true \
 // RUN:   -analyzer-config ctu-dir=%t/ctudir2 \
 // RUN:   -verify %s
 
 void clang_analyzer_eval(int);
 
 int testStaticImplicit(void);
 int func(void) {
   int ret = testStaticImplicit();
-  clang_analyzer_eval(ret == 4); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ret == 4); // expected-warning{{TRUE}} ctu
+                                 // expected-warning@-1{{UNKNOWN}} stu
   return testStaticImplicit();
 }

clang/test/Analysis/ctu-main.c

 // RUN: rm -rf %t && mkdir %t
 // RUN: mkdir -p %t/ctudir2
 // RUN: %clang_cc1 -triple x86_64-pc-linux-gnu \
 // RUN:   -emit-pch -o %t/ctudir2/ctu-other.c.ast %S/Inputs/ctu-other.c
 // RUN: cp %S/Inputs/ctu-other.c.externalDefMap.ast-dump.txt %t/ctudir2/externalDefMap.txt
+
+// RUN: %clang_cc1 -triple x86_64-pc-linux-gnu -fsyntax-only -std=c89 -analyze \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir2 \
+// RUN:   -analyzer-config ctu-phase1-inlining=none \
+// RUN:   -verify=newctu %s
+
+// Simulate the behavior of the previous CTU implementation by inlining all
+// functions during the first phase. This way, the second phase is a noop.
 // RUN: %clang_cc1 -triple x86_64-pc-linux-gnu -fsyntax-only -std=c89 -analyze \
 // RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
 // RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
 // RUN:   -analyzer-config ctu-dir=%t/ctudir2 \
-// RUN:   -verify %s
+// RUN:   -analyzer-config ctu-phase1-inlining=all \
+// RUN:   -verify=oldctu %s
 
 void clang_analyzer_eval(int);
 
+// A function that's definition is unknown both for single-tu (stu) and ctu
+// mode.
+int unknown(int);
+void test_unknown() {
+  int res = unknown(6);
+  clang_analyzer_eval(res == 6); // newctu-warning{{UNKNOWN}}
+                                 // oldctu-warning@-1{{UNKNOWN}}
+}
+
 // Test typedef and global variable in function.
 typedef struct {
   int a;
   int b;
 } FooBar;
 extern FooBar fb;
 int f(int);
-void testGlobalVariable(void) {
-  clang_analyzer_eval(f(5) == 1);         // expected-warning{{TRUE}}
+void testGlobalVariable() {
+  clang_analyzer_eval(f(5) == 1);         // newctu-warning{{TRUE}} ctu
+                                          // newctu-warning@-1{{UNKNOWN}} stu
+                                          // oldctu-warning@-2{{TRUE}}
 }
 
 // Test enums.
 int enumCheck(void);
 enum A { x,
          y,
          z };
 void testEnum(void) {
-  clang_analyzer_eval(x == 0);            // expected-warning{{TRUE}}
-  clang_analyzer_eval(enumCheck() == 42); // expected-warning{{TRUE}}
+  clang_analyzer_eval(x == 0);            // newctu-warning{{TRUE}}
+                                          // oldctu-warning@-1{{TRUE}}
+  clang_analyzer_eval(enumCheck() == 42); // newctu-warning{{TRUE}} ctu
+                                          // newctu-warning@-1{{UNKNOWN}} stu
+                                          // oldctu-warning@-2{{TRUE}}
 }
 
 // Test that asm import does not fail.
 int inlineAsm(void);
 int testInlineAsm(void) {
   return inlineAsm();
 }
 
 // Test reporting error in a macro.
 struct S;
 int g(struct S *);
 void testMacro(void) {
-  g(0); // expected-warning@Inputs/ctu-other.c:29 {{Access to field 'a' results in a dereference of a null pointer (loaded from variable 'ctx')}}
+  g(0); // newctu-warning@Inputs/ctu-other.c:29 {{Access to field 'a' results in a dereference of a null pointer (loaded from variable 'ctx')}}
+        // oldctu-warning@Inputs/ctu-other.c:29 {{Access to field 'a' results in a dereference of a null pointer (loaded from variable 'ctx')}}
 }
 
 // The external function prototype is incomplete.
 // warning:implicit functions are prohibited by c99
 void testImplicit(void) {
   int res = identImplicit(6);   // external implicit functions are not inlined
-  clang_analyzer_eval(res == 6); // expected-warning{{TRUE}}
+  clang_analyzer_eval(res == 6); // newctu-warning{{TRUE}} ctu
+                                 // newctu-warning@-1{{UNKNOWN}} stu
+                                 // oldctu-warning@-2{{TRUE}}
   // Call something with uninitialized from the same function in which the implicit was called.
   // This is necessary to reproduce a special bug in NoStoreFuncVisitor.
   int uninitialized;
-  h(uninitialized); // expected-warning{{1st function call argument is an uninitialized value}}
+  h(uninitialized); // newctu-warning{{1st function call argument is an uninitialized value}}
+                    // oldctu-warning@-1{{1st function call argument is an uninitialized value}}
 }
 
 // Tests the import of functions that have a struct parameter
 // defined in its prototype.
 struct DataType {
   int a;
   int b;
 };
 int structInProto(struct DataType *d);
 void testStructDefInArgument(void) {
   struct DataType d;
   d.a = 1;
   d.b = 0;
-  clang_analyzer_eval(structInProto(&d) == 0); // expected-warning{{TRUE}} expected-warning{{FALSE}}
+  // Not imported, thus remains unknown both in stu and ctu.
+  clang_analyzer_eval(structInProto(&d) == 0); // newctu-warning{{UNKNOWN}}
+                                               // oldctu-warning@-1{{UNKNOWN}}
 }
 
 int switchWithoutCases(int);
 void testSwitchStmtCrash(int x) {
   switchWithoutCases(x);
 }

clang/test/Analysis/ctu-main.cpp

 // RUN: rm -rf %t && mkdir %t
 // RUN: mkdir -p %t/ctudir
 // RUN: %clang_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
 // RUN:   -emit-pch -o %t/ctudir/ctu-other.cpp.ast %S/Inputs/ctu-other.cpp
 // RUN: %clang_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
 // RUN:   -emit-pch -o %t/ctudir/ctu-chain.cpp.ast %S/Inputs/ctu-chain.cpp
 // RUN: cp %S/Inputs/ctu-other.cpp.externalDefMap.ast-dump.txt %t/ctudir/externalDefMap.txt
+
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -analyzer-config ctu-phase1-inlining=none \
+// RUN:   -verify=newctu %s
+
+// Simulate the behavior of the previous CTU implementation by inlining all
+// functions during the first phase. This way, the second phase is a noop.
 // RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
 // RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
 // RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
 // RUN:   -analyzer-config ctu-dir=%t/ctudir \
-// RUN:   -verify %s
+// RUN:   -analyzer-config ctu-phase1-inlining=all \
+// RUN:   -verify=oldctu %s
+
 // RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
 // RUN:   -analyzer-checker=core,debug.ExprInspection \
 // RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
 // RUN:   -analyzer-config ctu-dir=%t/ctudir \
 // RUN:   -analyzer-config display-ctu-progress=true 2>&1 %s | FileCheck %s
 
 // CHECK: CTU loaded AST file: {{.*}}ctu-other.cpp.ast
 // CHECK: CTU loaded AST file: {{.*}}ctu-chain.cpp.ast

 union U {
   const int a;
   const unsigned int b;
 };
 extern const U extU;
 
 void test_virtual_functions(mycls* obj) {
   // The dynamic type is known.
-  clang_analyzer_eval(mycls().fvcl(1) == 8);   // expected-warning{{TRUE}}
-  clang_analyzer_eval(derived().fvcl(1) == 9); // expected-warning{{TRUE}}
+  clang_analyzer_eval(mycls().fvcl(1) == 8);   // newctu-warning{{TRUE}} ctu
+                                               // newctu-warning@-1{{UNKNOWN}} stu
+                                               // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(derived().fvcl(1) == 9); // newctu-warning{{TRUE}} ctu
+                                               // newctu-warning@-1{{UNKNOWN}} stu
+                                               // oldctu-warning@-2{{TRUE}}
   // We cannot decide about the dynamic type.
-  clang_analyzer_eval(obj->fvcl(1) == 8);      // expected-warning{{FALSE}} expected-warning{{TRUE}}
+  clang_analyzer_eval(obj->fvcl(1) == 8);      // newctu-warning{{TRUE}} ctu
+                                               // newctu-warning@-1{{UNKNOWN}} ctu, stu
+                                               // oldctu-warning@-2{{TRUE}}
+                                               // oldctu-warning@-3{{UNKNOWN}}
 }
 
 class TestAnonUnionUSR {
 public:
   inline float f(int value) {
     union {
       float f;
       int i;
     };
     i = value;
     return f;
   }
   static const int Test;
 };
 
 extern int testImportOfIncompleteDefaultParmDuringImport(int);
 
 extern int testImportOfDelegateConstructor(int);
 
 int main() {
-  clang_analyzer_eval(f(3) == 2); // expected-warning{{TRUE}}
-  clang_analyzer_eval(f(4) == 3); // expected-warning{{TRUE}}
-  clang_analyzer_eval(f(5) == 3); // expected-warning{{FALSE}}
-  clang_analyzer_eval(g(4) == 6); // expected-warning{{TRUE}}
-  clang_analyzer_eval(h(2) == 8); // expected-warning{{TRUE}}
-
-  clang_analyzer_eval(myns::fns(2) == 9);                   // expected-warning{{TRUE}}
-  clang_analyzer_eval(myns::embed_ns::fens(2) == -1);       // expected-warning{{TRUE}}
-  clang_analyzer_eval(mycls().fcl(1) == 6);                 // expected-warning{{TRUE}}
-  clang_analyzer_eval(mycls::fscl(1) == 7);                 // expected-warning{{TRUE}}
-  clang_analyzer_eval(myns::embed_cls().fecl(1) == -6);     // expected-warning{{TRUE}}
-  clang_analyzer_eval(mycls::embed_cls2().fecl2(0) == -11); // expected-warning{{TRUE}}
-
-  clang_analyzer_eval(chns::chf1(4) == 12); // expected-warning{{TRUE}}
-  clang_analyzer_eval(fun_using_anon_struct(8) == 8); // expected-warning{{TRUE}}
-
-  clang_analyzer_eval(other_macro_diag(1) == 1); // expected-warning{{TRUE}}
-  // expected-warning@Inputs/ctu-other.cpp:93{{REACHABLE}}
-  MACRODIAG(); // expected-warning{{REACHABLE}}
-
-  clang_analyzer_eval(extInt == 2); // expected-warning{{TRUE}}
-  clang_analyzer_eval(intns::extInt == 3); // expected-warning{{TRUE}}
-  clang_analyzer_eval(extS.a == 4); // expected-warning{{TRUE}}
-  clang_analyzer_eval(extNonConstS.a == 4); // expected-warning{{TRUE}} expected-warning{{FALSE}}
+  clang_analyzer_eval(f(3) == 2); // newctu-warning{{TRUE}} ctu
+                                  // newctu-warning@-1{{UNKNOWN}} stu
+                                  // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(f(4) == 3); // newctu-warning{{TRUE}} ctu
+                                  // newctu-warning@-1{{UNKNOWN}} stu
+                                  // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(f(5) == 3); // newctu-warning{{FALSE}} ctu
+                                  // newctu-warning@-1{{UNKNOWN}} stu
+                                  // oldctu-warning@-2{{FALSE}}
+  clang_analyzer_eval(g(4) == 6); // newctu-warning{{TRUE}} ctu
+                                  // newctu-warning@-1{{UNKNOWN}} stu
+                                  // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(h(2) == 8); // newctu-warning{{TRUE}} ctu
+                                  // newctu-warning@-1{{UNKNOWN}} stu
+                                  // oldctu-warning@-2{{TRUE}}
+
+  clang_analyzer_eval(myns::fns(2) == 9);                   // newctu-warning{{TRUE}} ctu
+                                                            // newctu-warning@-1{{UNKNOWN}} stu
+                                                            // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(myns::embed_ns::fens(2) == -1);       // newctu-warning{{TRUE}} ctu
+                                                            // newctu-warning@-1{{UNKNOWN}} stu
+                                                            // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(mycls().fcl(1) == 6);                 // newctu-warning{{TRUE}} ctu
+                                                            // newctu-warning@-1{{UNKNOWN}} stu
+                                                            // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(mycls::fscl(1) == 7);                 // newctu-warning{{TRUE}} ctu
+                                                            // newctu-warning@-1{{UNKNOWN}} stu
+                                                            // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(myns::embed_cls().fecl(1) == -6);     // newctu-warning{{TRUE}} ctu
+                                                            // newctu-warning@-1{{UNKNOWN}} stu
+                                                            // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(mycls::embed_cls2().fecl2(0) == -11); // newctu-warning{{TRUE}} ctu
+                                                            // newctu-warning@-1{{UNKNOWN}} stu
+                                                            // oldctu-warning@-2{{TRUE}}
+
+  clang_analyzer_eval(chns::chf1(4) == 12); // newctu-warning{{TRUE}} ctu
+                                            // newctu-warning@-1{{UNKNOWN}} stu
+                                            // oldctu-warning@-2{{TRUE}}
+  clang_analyzer_eval(fun_using_anon_struct(8) == 8); // newctu-warning{{TRUE}} ctu
+                                                      // newctu-warning@-1{{UNKNOWN}} stu
+                                                      // oldctu-warning@-2{{TRUE}}
+
+  clang_analyzer_eval(other_macro_diag(1) == 1); // newctu-warning{{TRUE}} ctu
+                                                 // newctu-warning@-1{{UNKNOWN}} stu
+                                                 // oldctu-warning@-2{{TRUE}}
+  // newctu-warning@Inputs/ctu-other.cpp:93{{REACHABLE}}
+  // oldctu-warning@Inputs/ctu-other.cpp:93{{REACHABLE}}
+  MACRODIAG(); // newctu-warning{{REACHABLE}}
+               // oldctu-warning@-1{{REACHABLE}}
+
+  // FIXME we should report an UNKNOWN as well for all external variables!
+  clang_analyzer_eval(extInt == 2); // newctu-warning{{TRUE}}
+                                    // oldctu-warning@-1{{TRUE}}
+  clang_analyzer_eval(intns::extInt == 3); // newctu-warning{{TRUE}}
+                                           // oldctu-warning@-1{{TRUE}}
+  clang_analyzer_eval(extS.a == 4); // newctu-warning{{TRUE}}
+                                    // oldctu-warning@-1{{TRUE}}
+  clang_analyzer_eval(extNonConstS.a == 4); // newctu-warning{{UNKNOWN}}
+                                            // oldctu-warning@-1{{UNKNOWN}}
   // Do not import non-trivial classes' initializers.
-  clang_analyzer_eval(extNTS.a == 4); // expected-warning{{TRUE}} expected-warning{{FALSE}}
-  clang_analyzer_eval(extHere == 6); // expected-warning{{TRUE}}
-  clang_analyzer_eval(A::a == 3); // expected-warning{{TRUE}}
-  clang_analyzer_eval(extSC.a == 8); // expected-warning{{TRUE}}
-  clang_analyzer_eval(ST::sc.a == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(extNTS.a == 4); // newctu-warning{{UNKNOWN}}
+                                      // oldctu-warning@-1{{UNKNOWN}}
+  clang_analyzer_eval(extHere == 6); // newctu-warning{{TRUE}}
+                                     // oldctu-warning@-1{{TRUE}}
+  clang_analyzer_eval(A::a == 3); // newctu-warning{{TRUE}}
+                                  // oldctu-warning@-1{{TRUE}}
+  clang_analyzer_eval(extSC.a == 8); // newctu-warning{{TRUE}}
+                                     // oldctu-warning@-1{{TRUE}}
+  clang_analyzer_eval(ST::sc.a == 2); // newctu-warning{{TRUE}}
+                                      // oldctu-warning@-1{{TRUE}}
   // clang_analyzer_eval(extSCN.scn.a == 9); // TODO
-  clang_analyzer_eval(extSubSCN.a == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(extSubSCN.a == 1); // newctu-warning{{TRUE}}
+                                         // oldctu-warning@-1{{TRUE}}
   // clang_analyzer_eval(extSCC.a == 7); // TODO
-  clang_analyzer_eval(extU.a == 4); // expected-warning{{TRUE}}
-
-  clang_analyzer_eval(TestAnonUnionUSR::Test == 5); // expected-warning{{TRUE}}
-
-  clang_analyzer_eval(testImportOfIncompleteDefaultParmDuringImport(9) == 9); // expected-warning{{TRUE}}
-
-  clang_analyzer_eval(testImportOfDelegateConstructor(10) == 10); // expected-warning{{TRUE}}
+  clang_analyzer_eval(extU.a == 4); // newctu-warning{{TRUE}}
+                                    // oldctu-warning@-1{{TRUE}}
+  clang_analyzer_eval(TestAnonUnionUSR::Test == 5); // newctu-warning{{TRUE}}
+                                                    // oldctu-warning@-1{{TRUE}}
+
+  clang_analyzer_eval(testImportOfIncompleteDefaultParmDuringImport(9) == 9);
+  // newctu-warning@-1{{TRUE}} ctu
+  // newctu-warning@-2{{UNKNOWN}} stu
+  // oldctu-warning@-3{{TRUE}}
+
+  clang_analyzer_eval(testImportOfDelegateConstructor(10) == 10);
+  // newctu-warning@-1{{TRUE}} ctu
+  // newctu-warning@-2{{UNKNOWN}} stu
+  // oldctu-warning@-3{{TRUE}}
 }

clang/test/Analysis/ctu-on-demand-parsing.c

 //
 // RUN: cd "%t" && %clang_extdef_map "%t/ctu-other.c" > externalDefMap.txt
 //
 // RUN: cd "%t" && %clang_cc1 -fsyntax-only -std=c89 -analyze \
 // RUN:   -analyzer-checker=core,debug.ExprInspection \
 // RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
 // RUN:   -analyzer-config ctu-dir=. \
 // RUN:   -analyzer-config ctu-invocation-list=invocations.yaml \
+// RUN:   -analyzer-config ctu-phase1-inlining=all \
 // RUN:   -verify ctu-on-demand-parsing.c
 //
+// FIXME: On-demand ctu should be tested in the same file that we have for the
+// PCH version, but with a different verify prefix (e.g. -verfiy=on-demand-ctu)
+//
 // FIXME: Path handling should work on all platforms.
 // REQUIRES: system-linux
 
 void clang_analyzer_eval(int);
 
 // Test typedef and global variable in function.
 typedef struct {
   int a;

clang/test/Analysis/ctu-on-demand-parsing.cpp

 //
 // RUN: cd "%t" && %clang_extdef_map Inputs/ctu-chain.cpp Inputs/ctu-other.cpp > externalDefMap.txt
 //
 // RUN: cd "%t" && %clang_analyze_cc1 \
 // RUN:   -analyzer-checker=core,debug.ExprInspection \
 // RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
 // RUN:   -analyzer-config ctu-dir=. \
 // RUN:   -analyzer-config ctu-invocation-list=invocations.yaml \
+// RUN:   -analyzer-config ctu-phase1-inlining=all \
 // RUN:   -verify ctu-on-demand-parsing.cpp
 // RUN: cd "%t" && %clang_analyze_cc1 \
 // RUN:   -analyzer-checker=core,debug.ExprInspection \
 // RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
 // RUN:   -analyzer-config ctu-dir=. \
 // RUN:   -analyzer-config ctu-invocation-list=invocations.yaml \
 // RUN:   -analyzer-config display-ctu-progress=true ctu-on-demand-parsing.cpp 2>&1 | FileCheck %t/ctu-on-demand-parsing.cpp
 //
 // CHECK: CTU loaded AST file: {{.*}}ctu-other.cpp
 // CHECK: CTU loaded AST file: {{.*}}ctu-chain.cpp
+
+// FIXME: On-demand ctu should be tested in the same file that we have for the
+// PCH version, but with a different verify prefix (e.g. -verfiy=on-demand-ctu)
 //
 // FIXME: Path handling should work on all platforms.
 // REQUIRES: system-linux
 
 #include "ctu-hdr.h"
 
 void clang_analyzer_eval(int);
 

clang/test/Analysis/ctu-onego-existingdef.cpp

+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyze-function='baruser(int)' -x c++ \
+// RUN:   -verify=nonctu %s
+
+// RUN: rm -rf %t && mkdir %t
+// RUN: mkdir -p %t/ctudir
+// RUN: %clang_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -emit-pch -o %t/ctudir/ctu-onego-existingdef-other.cpp.ast %S/Inputs/ctu-onego-existingdef-other.cpp
+// RUN: cp %S/Inputs/ctu-onego-existingdef-other.cpp.externalDefMap.ast-dump.txt %t/ctudir/externalDefMap.txt
+
+// Existing and equal function definition in both TU. `other` calls `bar` thus
+// `bar` will be indirectly imported. During the import we recognize that there
+// is an existing definition in the main TU, so we don't create a new Decl.
+// Thus, ctu should not bifurcate on the call of `bar` it should directly
+// inlinie that as in the case of nonctu.
+// Note, we would not get a warning below, if `bar` is conservatively evaluated.
+int bar() {
+  return 0;
+}
+
+//Here we completely supress the CTU work list execution. We should not
+//bifurcate on the call of `bar`. (We do not load the foreign AST at all.)
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -verify=stu %s \
+// RUN:   -analyze-function='baruser(int)' -x c++ \
+// RUN:   -analyzer-config ctu-max-nodes-pct=0 \
+// RUN:   -analyzer-config ctu-max-nodes-min=0
+
+//Here we enable the CTU work list execution. We should not bifurcate on the
+//call of `bar`.
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -verify=ctu %s \
+// RUN:   -analyze-function='baruser(int)' -x c++ \
+// RUN:   -analyzer-config ctu-max-nodes-pct=100 \
+// RUN:   -analyzer-config ctu-max-nodes-min=1000
+//Check that the AST file is loaded.
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -analyze-function='baruser(int)' -x c++ \
+// RUN:   -analyzer-config ctu-max-nodes-pct=100 \
+// RUN:   -analyzer-config display-ctu-progress=true \
+// RUN:   -analyzer-config ctu-max-nodes-min=1000 2>&1 %s | FileCheck %s
+// CHECK: CTU loaded AST file
+
+void other(); // Defined in the other TU.
+
+void baruser(int) {
+  other();
+  int x = bar();
+  (void)(1 / x);
+  // ctu-warning@-1{{Division by zero}}
+  // stu-warning@-2{{Division by zero}}
+  // nonctu-warning@-3{{Division by zero}}
+}

clang/test/Analysis/ctu-onego-indirect.cpp

+// RUN: rm -rf %t && mkdir %t
+// RUN: mkdir -p %t/ctudir
+// RUN: %clang_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -emit-pch -o %t/ctudir/ctu-onego-indirect-other.cpp.ast %S/Inputs/ctu-onego-indirect-other.cpp
+// RUN: cp %S/Inputs/ctu-onego-indirect-other.cpp.externalDefMap.ast-dump.txt %t/ctudir/externalDefMap.txt
+
+int bar();
+
+// Here we have a foreign function `bar` that is imported when we analyze
+// `adirectbaruser`. During the subsequent toplevel analysis of `baruser` we
+// should bifurcate on the call of `bar`.
+
+//Ensure the order of the toplevel analyzed functions.
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -analyzer-display-progress \
+// RUN:   -analyzer-inlining-mode=all \
+// RUN:   -analyzer-config ctu-phase1-inlining=none \
+// RUN:   -analyzer-config ctu-max-nodes-pct=100 \
+// RUN:   -analyzer-config ctu-max-nodes-min=1000 2>&1 %s | FileCheck %s
+// CHECK: ANALYZE (Path,  Inline_Regular):{{.*}}adirectbaruser(int)
+// CHECK: ANALYZE (Path,  Inline_Regular):{{.*}}baruser(int)
+
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -analyzer-display-progress \
+// RUN:   -analyzer-inlining-mode=all \
+// RUN:   -analyzer-config ctu-phase1-inlining=none \
+// RUN:   -verify %s \
+// RUN:   -analyzer-config ctu-max-nodes-pct=100 \
+// RUN:   -analyzer-config ctu-max-nodes-min=1000
+
+
+void other(); // Defined in the other TU.
+
+void clang_analyzer_eval(int);
+
+void baruser(int x) {
+  if (x == 1)
+    return;
+  int y = bar();
+  clang_analyzer_eval(y == 0); // expected-warning{{TRUE}}
+                               // expected-warning@-1{{UNKNOWN}}
+  other();
+}
+
+void adirectbaruser(int) {
+  int y = bar();
+  (void)y;
+  baruser(1);
+}
+

clang/test/Analysis/ctu-onego-small.cpp

+// RUN: rm -rf %t && mkdir %t
+// RUN: mkdir -p %t/ctudir
+// RUN: %clang_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -emit-pch -o %t/ctudir/ctu-onego-small-other.cpp.ast %S/Inputs/ctu-onego-small-other.cpp
+// RUN: cp %S/Inputs/ctu-onego-small-other.cpp.externalDefMap.ast-dump.txt %t/ctudir/externalDefMap.txt
+
+// Small function defined in another TU.
+int bar();
+
+// Here we limit the ctu analysis to the first phase only (via the
+// ctu-max-nodes config options). And we check whether the small foreign
+// function `bar` is inlined.
+
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -analyzer-config display-ctu-progress=true \
+// RUN:   -analyzer-display-progress \
+// RUN:   -analyzer-config ctu-max-nodes-pct=0 \
+// RUN:   -analyzer-config ctu-max-nodes-min=0 2>&1 %s | FileCheck %s
+// CHECK: ANALYZE (Path,  Inline_Regular): {{.*}} baruser(int){{.*}}CTU loaded AST file
+
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -analyzer-config ctu-max-nodes-pct=0 \
+// RUN:   -analyzer-config ctu-phase1-inlining=none \
+// RUN:   -analyzer-config ctu-max-nodes-min=0 -verify=inline-none %s
+
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -analyzer-config ctu-max-nodes-pct=0 \
+// RUN:   -analyzer-config ctu-phase1-inlining=small \
+// RUN:   -analyzer-config ctu-max-nodes-min=0 -verify=inline-small %s
+
+
+void clang_analyzer_eval(int);
+
+void baruser(int x) {
+  int y = bar();
+  // inline-none-warning@+2{{UNKNOWN}}
+  // inline-small-warning@+1{{TRUE}}
+  clang_analyzer_eval(y == 0);
+}

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

+// RUN: rm -rf %t && mkdir %t
+// RUN: mkdir -p %t/ctudir
+// RUN: %clang_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -emit-pch -o %t/ctudir/ctu-onego-toplevel-other.cpp.ast %S/Inputs/ctu-onego-toplevel-other.cpp
+// RUN: cp %S/Inputs/ctu-onego-toplevel-other.cpp.externalDefMap.ast-dump.txt %t/ctudir/externalDefMap.txt
+
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -analyzer-config ctu-phase1-inlining=none \
+// RUN:   -verify=ctu %s
+
+// RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=%t/ctudir \
+// RUN:   -analyzer-config ctu-phase1-inlining=none \
+// RUN:   -analyzer-config display-ctu-progress=true \
+// RUN:   -analyzer-display-progress \
+// RUN:   -verify=ctu %s 2>&1 | FileCheck %s
+
+// CallGraph: c->b
+// topological sort: c, b
+// Note that `other` calls into `b` but that is not visible in the CallGraph
+// because that happens in another TU.
+
+// During the onego CTU analysis, we start with c() as top level function.
+// Then we visit b() as non-toplevel during the processing of the FWList, thus
+// that would not be visited as toplevel without special care.
+
+// `c` is analyzed as toplevel and during that the other TU is loaded:
+// CHECK: ANALYZE (Path,  Inline_Regular): {{.*}} c(int){{.*}}CTU loaded AST file
+// next, `b` is analyzed as toplevel:
+// CHECK: ANALYZE (Path,  Inline_Regular): {{.*}} b(int)
+
+void b(int x);
+void other(int y);
+void c(int y) {
+  other(y);
+  return;
+  // The below call is here to form the proper CallGraph, but will not be
+  // analyzed.
+  b(1);
+}
+
+void b(int x) {
+  if (x == 0)
+    (void)(1 / x);
+    // ctu-warning@-1{{Division by zero}}
+    // We receive the above warning only if `b` is analyzed as top-level.
+}