[analyzer] Add analyzer option to limit the number of imported TUs

[gamesh411]

Summary

During CTU analysis of complex projects, the loaded AST-contents of
imported TUs can grow bigger than available system memory. This option
introduces a threshold on the number of TUs to be imported for a single
TU in order to prevent such cases.

[gamesh411]

Updated option handling location to use AnalyzerOptions instead of CC1

[martong]

@xazax.hun Could you please take a look?

[xazax.hun]

Mostly looks good, I have two slightly related nits.

include/clang/CrossTU/CrossTranslationUnit.h

127

I would prefer to keep the default argument for DisplayCTUProgress. You could do this either by swapping the arguments or adding a default argument to CTULoadThreshold as well. I think I might prefer the latter.

176

Does it make sense to call getCrossTUDefinition with different thresholds for the same CTUContext? I suspect it is not, so it might make more sense to set the threshold in the context's constructor.

[gamesh411]

Apply review suggestions by Xazax

[gamesh411]

I could greatly simplify the API of getCrossTUDefinition by injecting the threshold value in the constructor. A minor drawback with this approach is that testing code is a bit more complicated, as I had to patch the CompilerInstance to override the AnalyzerOption value for CTUImportThreshold. Thanks for the suggestion!

[gamesh411]

Revert unnecessary clang-formating of AnalysisConsumer.cpp

[gamesh411]

Rebase onto current master

[gamesh411]

Rebase again

[martong]

include/clang/StaticAnalyzer/Core/AnalyzerOptions.def

293

burder -> burden ?

[Szelethus]

test/Analysis/ctu-import-threshold.c

2–6

There's no need for such validation, AnalyzerOptions' interface is very well guarded against misuse.

If you insist, prefer modifying clang/test/Analysis/invalid-analyzer-config-value.c.

include/clang/CrossTU/CrossTranslationUnit.h

enum class index_error_code {
   invalid_index_format,
   multiple_definitions,
   missing_definition,
   failed_import,
   failed_to_get_external_ast,
   failed_to_generate_usr,
   triple_mismatch,
   lang_mismatch,
-  lang_dialect_mismatch
+  lang_dialect_mismatch,
+  load_threshold_reached
 };
 
 class IndexError : public llvm::ErrorInfo<IndexError> {
 public:
   static char ID;
   IndexError(index_error_code C) : Code(C), LineNo(0) {}
   IndexError(index_error_code C, std::string FileName, int LineNo = 0)
       : Code(C), FileName(std::move(FileName)), LineNo(LineNo) {}
public:
   ///        file and merge it into the original AST.
   ///
   /// This method should only be used on functions that have no definitions in
   /// the current translation unit. A function definition with the same
   /// declaration will be looked up in the index file which should be in the
   /// \p CrossTUDir directory, called \p IndexName. In case the declaration is
   /// found in the index the corresponding AST file will be loaded and the
   /// definition of the function will be merged into the original AST using
-  /// the AST Importer.
+  /// the AST Importer. \p CTULoadTreshold should serve as an upper limit to the
+  /// number of TUs imported in order to reduce the memory footprint of CTU
+  /// analysis.
   ///
   /// \return The declaration with the definition will be returned.
   /// If no suitable definition is found in the index file or multiple
   /// definitions found error will be returned.
   ///
   /// Note that the AST files should also be in the \p CrossTUDir.
   llvm::Expected<const FunctionDecl *>
   getCrossTUDefinition(const FunctionDecl *FD, StringRef CrossTUDir,
-                       StringRef IndexName, bool DisplayCTUProgress = false);
+                       StringRef IndexName, bool DisplayCTUProgress,
+                       unsigned CTULoadThreshold);
 
   /// This function loads a function definition from an external AST
   ///        file.
   ///
   /// A function definition with the same declaration will be looked up in the
   /// index file which should be in the \p CrossTUDir directory, called
   /// \p IndexName. In case the declaration is found in the index the
-  /// corresponding AST file will be loaded.
+  /// corresponding AST file will be loaded. If the number of TUs imported
+  /// reaches \p CTULoadTreshold, no loading is performed.
   ///
   /// \return Returns a pointer to the ASTUnit that contains the definition of
   /// the looked up function or an Error.
   /// The returned pointer is never a nullptr.
   ///
   /// Note that the AST files should also be in the \p CrossTUDir.
   llvm::Expected<ASTUnit *> loadExternalAST(StringRef LookupName,
                                             StringRef CrossTUDir,
                                             StringRef IndexName,
-                                            bool DisplayCTUProgress = false);
+                                            bool DisplayCTUProgress,
+                                            unsigned CTULoadThreshold);
 
   /// This function merges a definition from a separate AST Unit into
   ///        the current one which was created by the compiler instance that
   ///        was passed to the constructor.
   ///
   /// \return Returns the resulting definition or an error.
   llvm::Expected<const FunctionDecl *> importDefinition(const FunctionDecl *FD);
 
private:
   llvm::StringMap<std::unique_ptr<clang::ASTUnit>> FileASTUnitMap;
   llvm::StringMap<clang::ASTUnit *> FunctionASTUnitMap;
   llvm::StringMap<std::string> FunctionFileMap;
   llvm::DenseMap<TranslationUnitDecl *, std::unique_ptr<ASTImporter>>
       ASTUnitImporterMap;
   CompilerInstance &CI;
   ASTContext &Context;
   std::unique_ptr<ASTImporterLookupTable> LookupTable;
+  unsigned NumASTLoaded{0u};
 };
 
 } // namespace cross_tu
 } // namespace clang
 
 #endif // LLVM_CLANG_CROSSTU_CROSSTRANSLATIONUNIT_H

include/clang/StaticAnalyzer/Core/AnalyzerOptions.def

ANALYZER_OPTION(bool, ShouldDisplayMacroExpansions, "expand-macros",
                 "expanded and included in the plist output.",
                 false)
 
 ANALYZER_OPTION(bool, DisplayCTUProgress, "display-ctu-progress",
                 "Whether to emit verbose output about "
                 "the analyzer's progress related to ctu.",
                 false)
 
+ANALYZER_OPTION(unsigned, CTUImportThreshold, "ctu-import-threshold",
+                "The maximal amount of translation units that is considered "
+                "for import when inlining functions during CTU analysis. "
+                "Lowering this threshold can alleviate the memory burder of "
+                "analysis with many interdependent definitions located in "
+                "various translation units.",
+                100u)
+
 //===----------------------------------------------------------------------===//
 // Unsinged analyzer options.
 //===----------------------------------------------------------------------===//
 
 ANALYZER_OPTION(
     unsigned, AlwaysInlineSize, "ipa-always-inline-size",
     "The size of the functions (in basic blocks), which should be considered "
     "to be small enough to always inline.",

lib/CrossTU/CrossTranslationUnit.cpp

STATISTIC(
     NumNotInOtherTU,
     "The # of getCTUDefinition called but the function is not in any other TU");
 STATISTIC(NumGetCTUSuccess,
           "The # of getCTUDefinition successfully returned the "
           "requested function's body");
 STATISTIC(NumTripleMismatch, "The # of triple mismatches");
 STATISTIC(NumLangMismatch, "The # of language mismatches");
 STATISTIC(NumLangDialectMismatch, "The # of language dialect mismatches");
+STATISTIC(NumASTLoadThresholdReached,
+          "The # of ASTs not loaded because of threshold");
 
 // Same as Triple's equality operator, but we check a field only if that is
 // known in both instances.
 bool hasEqualKnownFields(const llvm::Triple &Lhs, const llvm::Triple &Rhs) {
   using llvm::Triple;
   if (Lhs.getArch() != Triple::UnknownArch &&
       Rhs.getArch() != Triple::UnknownArch && Lhs.getArch() != Rhs.getArch())
     return false;
std::string message(int Condition) const override {
     case index_error_code::failed_to_generate_usr:
       return "Failed to generate USR.";
     case index_error_code::triple_mismatch:
       return "Triple mismatch";
     case index_error_code::lang_mismatch:
       return "Language mismatch";
     case index_error_code::lang_dialect_mismatch:
       return "Language dialect mismatch";
+    case index_error_code::load_threshold_reached:
+      return "Load threshold reached";
     }
     llvm_unreachable("Unrecognized index_error_code.");
   }
 };
 
 static llvm::ManagedStatic<IndexErrorCategory> Category;
 } // end anonymous namespace
 
CrossTranslationUnitContext::findFunctionInDeclContext(const DeclContext *DC,
   }
   return nullptr;
 }
 
 llvm::Expected<const FunctionDecl *>
 CrossTranslationUnitContext::getCrossTUDefinition(const FunctionDecl *FD,
                                                   StringRef CrossTUDir,
                                                   StringRef IndexName,
-                                                  bool DisplayCTUProgress) {
+                                                  bool DisplayCTUProgress,
+                                                  unsigned CTULoadThreshold) {
   assert(FD && "FD is missing, bad call to this function!");
   assert(!FD->hasBody() && "FD has a definition in current translation unit!");
   ++NumGetCTUCalled;
   const std::string LookupFnName = getLookupName(FD);
   if (LookupFnName.empty())
     return llvm::make_error<IndexError>(
         index_error_code::failed_to_generate_usr);
   llvm::Expected<ASTUnit *> ASTUnitOrError =
-      loadExternalAST(LookupFnName, CrossTUDir, IndexName, DisplayCTUProgress);
+      loadExternalAST(LookupFnName, CrossTUDir, IndexName, DisplayCTUProgress,
+                      CTULoadThreshold);
   if (!ASTUnitOrError)
     return ASTUnitOrError.takeError();
   ASTUnit *Unit = *ASTUnitOrError;
   assert(&Unit->getFileManager() ==
          &Unit->getASTContext().getSourceManager().getFileManager());
 
   const llvm::Triple &TripleTo = Context.getTargetInfo().getTriple();
   const llvm::Triple &TripleFrom =
case index_error_code::triple_mismatch:
     break;
   default:
     break;
   }
 }
 
 llvm::Expected<ASTUnit *> CrossTranslationUnitContext::loadExternalAST(
     StringRef LookupName, StringRef CrossTUDir, StringRef IndexName,
-    bool DisplayCTUProgress) {
+    bool DisplayCTUProgress, unsigned CTULoadThreshold) {
   // FIXME: The current implementation only supports loading functions with
   //        a lookup name from a single translation unit. If multiple
   //        translation units contains functions with the same lookup name an
   //        error will be returned.
+
+  if (NumASTLoaded >= CTULoadThreshold) {
+    ++NumASTLoadThresholdReached;
+    return llvm::make_error<IndexError>(
+        index_error_code::load_threshold_reached);
+  }
+
   ASTUnit *Unit = nullptr;
   auto FnUnitCacheEntry = FunctionASTUnitMap.find(LookupName);
   if (FnUnitCacheEntry == FunctionASTUnitMap.end()) {
     if (FunctionFileMap.empty()) {
       SmallString<256> IndexFile = CrossTUDir;
       if (llvm::sys::path::is_absolute(IndexName))
         IndexFile = IndexName;
       else
if (ASTCacheEntry == FileASTUnitMap.end()) {
       IntrusiveRefCntPtr<DiagnosticsEngine> Diags(
           new DiagnosticsEngine(DiagID, &*DiagOpts, DiagClient));
 
       std::unique_ptr<ASTUnit> LoadedUnit(ASTUnit::LoadFromASTFile(
           ASTFileName, CI.getPCHContainerOperations()->getRawReader(),
           ASTUnit::LoadEverything, Diags, CI.getFileSystemOpts()));
       Unit = LoadedUnit.get();
       FileASTUnitMap[ASTFileName] = std::move(LoadedUnit);
+      ++NumASTLoaded;
       if (DisplayCTUProgress) {
         llvm::errs() << "CTU loaded AST file: "
                      << ASTFileName << "\n";
       }
     } else {
       Unit = ASTCacheEntry->second.get();
     }
     FunctionASTUnitMap[LookupName] = Unit;

lib/StaticAnalyzer/Core/CallEvent.cpp

RuntimeDefinition AnyFunctionCall::getRuntimeDefinition() const {
   // 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);
+                                  Opts.DisplayCTUProgress,
+                                  Opts.CTUImportThreshold);
 
   if (!CTUDeclOrError) {
     handleAllErrors(CTUDeclOrError.takeError(),
                     [&](const cross_tu::IndexError &IE) {
                       CTUCtx.emitCrossTUDiagnostics(IE);
                     });
     return {};
   }

test/Analysis/analyzer-config.c

 // CHECK-NEXT: cfg-implicit-dtors = true
 // CHECK-NEXT: cfg-lifetime = false
 // CHECK-NEXT: cfg-loopexit = false
 // CHECK-NEXT: cfg-rich-constructors = true
 // CHECK-NEXT: cfg-scopes = false
 // CHECK-NEXT: cfg-temporary-dtors = true
 // CHECK-NEXT: crosscheck-with-z3 = false
 // CHECK-NEXT: ctu-dir = ""
+// CHECK-NEXT: ctu-import-threshold = 100
 // CHECK-NEXT: ctu-index-name = externalDefMap.txt
 // CHECK-NEXT: display-ctu-progress = false
 // CHECK-NEXT: eagerly-assume = true
 // CHECK-NEXT: elide-constructors = true
 // CHECK-NEXT: expand-macros = false
 // CHECK-NEXT: experimental-enable-naive-ctu-analysis = false
 // CHECK-NEXT: exploration_strategy = unexplored_first_queue
 // CHECK-NEXT: faux-bodies = true

 // CHECK-NEXT: serialize-stats = false
 // CHECK-NEXT: stable-report-filename = false
 // CHECK-NEXT: suppress-c++-stdlib = true
 // CHECK-NEXT: suppress-inlined-defensive-checks = true
 // CHECK-NEXT: suppress-null-return-paths = true
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 49
+// CHECK-NEXT: num-entries = 50

test/Analysis/ctu-import-threshold.c

+// Ensure analyzer option 'ctu-import-threshold' is a recognized option.
+//
+// RUN: %clang_cc1 -analyze -analyzer-config ctu-import-threshold=30 -verify %s
+//
+// expected-no-diagnostics

unittests/CrossTU/CrossTranslationUnitTest.cpp

 
 namespace clang {
 namespace cross_tu {
 
 namespace {
 
 class CTUASTConsumer : public clang::ASTConsumer {
 public:
-  explicit CTUASTConsumer(clang::CompilerInstance &CI, bool *Success)
-      : CTU(CI), Success(Success) {}
+  explicit CTUASTConsumer(clang::CompilerInstance &CI, bool *Success,
+                          unsigned ImportLimit)
+      : CTU(CI), Success(Success), ImportLimit(ImportLimit) {}
 
   void HandleTranslationUnit(ASTContext &Ctx) {
     const TranslationUnitDecl *TU = Ctx.getTranslationUnitDecl();
     const FunctionDecl *FD = nullptr;
     for (const Decl *D : TU->decls()) {
       FD = dyn_cast<FunctionDecl>(D);
       if (FD && FD->getName() == "f")
         break;
void HandleTranslationUnit(ASTContext &Ctx) {
     EXPECT_TRUE(llvm::sys::fs::exists(SourceFileName));
 
     std::unique_ptr<ASTUnit> ASTWithDefinition =
         tooling::buildASTFromCode(SourceText, SourceFileName);
     ASTWithDefinition->Save(ASTFileName.str());
     EXPECT_TRUE(llvm::sys::fs::exists(ASTFileName));
 
     // Load the definition from the AST file.
-    llvm::Expected<const FunctionDecl *> NewFDorError =
-        CTU.getCrossTUDefinition(FD, "", IndexFileName);
-    EXPECT_TRUE((bool)NewFDorError);
-    const FunctionDecl *NewFD = *NewFDorError;
+    llvm::Expected<const FunctionDecl *> NewFDorError = handleExpected(
+        CTU.getCrossTUDefinition(FD, "", IndexFileName, false, ImportLimit),
+        []() { return nullptr; }, [](IndexError &) {});
 
+    if (NewFDorError) {
+      const FunctionDecl *NewFD = *NewFDorError;
       *Success = NewFD && NewFD->hasBody() && !OrigFDHasBody;
     }
+  }
 
 private:
   CrossTranslationUnitContext CTU;
   bool *Success;
+  unsigned ImportLimit;
 };
 
 class CTUAction : public clang::ASTFrontendAction {
 public:
-  CTUAction(bool *Success) : Success(Success) {}
+  CTUAction(bool *Success, unsigned ImportLimit)
+      : Success(Success), ImportLimit(ImportLimit) {}
 
 protected:
   std::unique_ptr<clang::ASTConsumer>
   CreateASTConsumer(clang::CompilerInstance &CI, StringRef) override {
-    return llvm::make_unique<CTUASTConsumer>(CI, Success);
+    return llvm::make_unique<CTUASTConsumer>(CI, Success, ImportLimit);
   }
 
 private:
   bool *Success;
+  unsigned ImportLimit;
 };
 
 } // end namespace
 
 TEST(CrossTranslationUnit, CanLoadFunctionDefinition) {
   bool Success = false;
-  EXPECT_TRUE(tooling::runToolOnCode(new CTUAction(&Success), "int f(int);"));
+  EXPECT_TRUE(
+      tooling::runToolOnCode(new CTUAction(&Success, 1u), "int f(int);"));
   EXPECT_TRUE(Success);
 }
 
+TEST(CrossTranslationUnit, RespectsLoadThreshold) {
+  bool Success = false;
+  EXPECT_TRUE(
+      tooling::runToolOnCode(new CTUAction(&Success, 0u), "int f(int);"));
+  EXPECT_FALSE(Success);
+}
+
 TEST(CrossTranslationUnit, IndexFormatCanBeParsed) {
   llvm::StringMap<std::string> Index;
   Index["a"] = "/b/f1";
   Index["c"] = "/d/f2";
   Index["e"] = "/f/f3";
   std::string IndexText = createCrossTUIndexString(Index);
 
   int IndexFD;