[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

129

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.

187

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:
   /// \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);
   llvm::Expected<const VarDecl *>
   getCrossTUDefinition(const VarDecl *VD, StringRef CrossTUDir,
                        StringRef IndexName, bool DisplayCTUProgress = false);
 
   /// This function loads a definition from an external AST file.
   ///
   /// A 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 name 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,
private:
   llvm::StringMap<std::unique_ptr<clang::ASTUnit>> FileASTUnitMap;
   llvm::StringMap<clang::ASTUnit *> NameASTUnitMap;
   llvm::StringMap<std::string> NameFileMap;
   llvm::DenseMap<TranslationUnitDecl *, std::unique_ptr<ASTImporter>>
       ASTUnitImporterMap;
   CompilerInstance &CI;
   ASTContext &Context;
   std::unique_ptr<ASTImporterLookupTable> LookupTable;
+  /// \p CTULoadTreshold should serve as an upper limit to the number of TUs
+  /// imported in order to reduce the memory footprint of CTU analysis.
+  const unsigned CTULoadThreshold;
+  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
 
static bool hasBodyOrInit(const VarDecl *D, const VarDecl *&DefD) {
   return D->getAnyInitializer(DefD);
 }
 template <typename T> static bool hasBodyOrInit(const T *D) {
   const T *Unused;
   return hasBodyOrInit(D, Unused);
 }
 
 CrossTranslationUnitContext::CrossTranslationUnitContext(CompilerInstance &CI)
-    : CI(CI), Context(CI.getASTContext()) {}
+    : CI(CI), Context(CI.getASTContext()),
+      CTULoadThreshold(CI.getAnalyzerOpts()->CTUImportThreshold) {}
 
 CrossTranslationUnitContext::~CrossTranslationUnitContext() {}
 
 std::string CrossTranslationUnitContext::getLookupName(const NamedDecl *ND) {
   SmallString<128> DeclUSR;
   bool Ret = index::generateUSRForDecl(ND, DeclUSR);
   (void)Ret;
   assert(!Ret && "Unable to generate USR");
llvm::Expected<const T *> CrossTranslationUnitContext::getCrossTUDefinitionImpl(
   assert(D && "D is missing, bad call to this function!");
   assert(!hasBodyOrInit(D) &&
          "D has a body or init in current translation unit!");
   ++NumGetCTUCalled;
   const std::string LookupName = getLookupName(D);
   if (LookupName.empty())
     return llvm::make_error<IndexError>(
         index_error_code::failed_to_generate_usr);
-  llvm::Expected<ASTUnit *> ASTUnitOrError =
-      loadExternalAST(LookupName, CrossTUDir, IndexName, DisplayCTUProgress);
+  llvm::Expected<ASTUnit *> ASTUnitOrError = loadExternalAST(
+      LookupName, CrossTUDir, IndexName, DisplayCTUProgress);
   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 =

 
 llvm::Expected<ASTUnit *> CrossTranslationUnitContext::loadExternalAST(
     StringRef LookupName, StringRef CrossTUDir, StringRef IndexName,
     bool DisplayCTUProgress) {
   // FIXME: The current implementation only supports loading decls with
   //        a lookup name from a single translation unit. If multiple
   //        translation units contains decls 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 NameUnitCacheEntry = NameASTUnitMap.find(LookupName);
   if (NameUnitCacheEntry == NameASTUnitMap.end()) {
     if (NameFileMap.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();
     }
     NameASTUnitMap[LookupName] = Unit;

lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp

public:
   AnalysisConsumer(CompilerInstance &CI, const std::string &outdir,
                    AnalyzerOptionsRef opts, ArrayRef<std::string> plugins,
                    CodeInjector *injector)
       : RecVisitorMode(0), RecVisitorBR(nullptr), Ctx(nullptr),
         PP(CI.getPreprocessor()), OutDir(outdir), Opts(std::move(opts)),
         Plugins(plugins), Injector(injector), CTU(CI) {
     DigestAnalyzerOptions();
     if (Opts->PrintStats || Opts->ShouldSerializeStats) {
-      AnalyzerTimers = llvm::make_unique<llvm::TimerGroup>(
-          "analyzer", "Analyzer timers");
+      AnalyzerTimers =
+          llvm::make_unique<llvm::TimerGroup>("analyzer", "Analyzer timers");
       TUTotalTimer = llvm::make_unique<llvm::Timer>(
           "time", "Analyzer total time", *AnalyzerTimers);
       llvm::EnableStatistics(/* PrintOnExit= */ false);
     }
   }
 
   ~AnalysisConsumer() override {
     if (Opts->PrintStats) {

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

 //===- unittest/Tooling/CrossTranslationUnitTest.cpp - Tooling unit tests -===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/CrossTU/CrossTranslationUnit.h"
+#include "clang/Frontend/CompilerInstance.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/Frontend/FrontendAction.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "gtest/gtest.h"
 #include <cassert>
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),
+        []() { return nullptr; }, [](IndexError &) {});
 
+    if (NewFDorError) {
+      const FunctionDecl *NewFD = *NewFDorError;
       *Success = NewFD && NewFD->hasBody() && !OrigFDHasBody;
     }
+  }
 
 private:
   CrossTranslationUnitContext CTU;
   bool *Success;
 };
 
 class CTUAction : public clang::ASTFrontendAction {
 public:
-  CTUAction(bool *Success) : Success(Success) {}
+  CTUAction(bool *Success, unsigned OverrideLimit)
+      : Success(Success), OverrideLimit(OverrideLimit) {}
 
 protected:
   std::unique_ptr<clang::ASTConsumer>
   CreateASTConsumer(clang::CompilerInstance &CI, StringRef) override {
+    CI.getAnalyzerOpts()->CTUImportThreshold = OverrideLimit;
     return llvm::make_unique<CTUASTConsumer>(CI, Success);
   }
 
 private:
   bool *Success;
+  const unsigned OverrideLimit;
 };
 
 } // 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;