Add Cross Translation Unit support library

This patch introduces a class that can help to build tools that require cross
translation unit facilities. This class allows function definitions to be loaded
from external AST files based on an index. In order to use this functionality an
index is required. The index format is a flat text file but it might be
replaced with a different solution in the near future. USRs are used as names to
look up the functions definitions. This class also does caching to avoid
redundant loading of AST files.

Right now only function defnitions can be loaded using this API because this is
what the in progress cross translation unit feature of the Static Analyzer
requires. In to future this might be extended to classes, types etc.

Differential Revision: https://reviews.llvm.org/D34512


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@313975 91177308-0d34-0410-b5e6-96231b3b80d8

22 files changed, 827 insertions, 2 deletions

diff --git a/include/clang/Basic/AllDiagnostics.h b/include/clang/Basic/AllDiagnostics.h
index fc861a1952..3bbab923e0 100644
--- a/include/clang/Basic/AllDiagnostics.h
+++ b/include/clang/Basic/AllDiagnostics.h
@@ -18,6 +18,7 @@
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/CommentDiagnostic.h"
 #include "clang/Analysis/AnalysisDiagnostic.h"
+#include "clang/CrossTU/CrossTUDiagnostic.h"
 #include "clang/Driver/DriverDiagnostic.h"
 #include "clang/Frontend/FrontendDiagnostic.h"
 #include "clang/Lex/LexDiagnostic.h"
diff --git a/include/clang/Basic/CMakeLists.txt b/include/clang/Basic/CMakeLists.txt
index 3e0fb8728c..decfdfde16 100644
--- a/include/clang/Basic/CMakeLists.txt
+++ b/include/clang/Basic/CMakeLists.txt
@@ -9,6 +9,7 @@ clang_diag_gen(Analysis)
 clang_diag_gen(AST)
 clang_diag_gen(Comment)
 clang_diag_gen(Common)
+clang_diag_gen(CrossTU)
 clang_diag_gen(Driver)
 clang_diag_gen(Frontend)
 clang_diag_gen(Lex)
diff --git a/include/clang/Basic/Diagnostic.td b/include/clang/Basic/Diagnostic.td
index f25068eca1..54bd1489e3 100644
--- a/include/clang/Basic/Diagnostic.td
+++ b/include/clang/Basic/Diagnostic.td
@@ -133,6 +133,7 @@ include "DiagnosticASTKinds.td"
 include "DiagnosticAnalysisKinds.td"
 include "DiagnosticCommentKinds.td"
 include "DiagnosticCommonKinds.td"
+include "DiagnosticCrossTUKinds.td"
 include "DiagnosticDriverKinds.td"
 include "DiagnosticFrontendKinds.td"
 include "DiagnosticLexKinds.td"
diff --git a/include/clang/Basic/DiagnosticCrossTUKinds.td b/include/clang/Basic/DiagnosticCrossTUKinds.td
new file mode 100644
index 0000000000..8b6d8b6814
--- /dev/null
+++ b/include/clang/Basic/DiagnosticCrossTUKinds.td
@@ -0,0 +1,18 @@
+//==--- DiagnosticCrossTUKinds.td - Cross Translation Unit diagnostics ----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+let Component = "CrossTU" in {
+
+def err_fnmap_parsing : Error<
+  "error parsing index file: '%0' line: %1 'UniqueID filename' format "
+  "expected">;
+
+def err_multiple_def_index : Error<
+  "multiple definitions are found for the same key in index ">;
+}
diff --git a/include/clang/Basic/DiagnosticIDs.h b/include/clang/Basic/DiagnosticIDs.h
index 0ec6886626..5ebed9435b 100644
--- a/include/clang/Basic/DiagnosticIDs.h
+++ b/include/clang/Basic/DiagnosticIDs.h
@@ -36,6 +36,7 @@ namespace clang {
       DIAG_SIZE_PARSE         =  500,
       DIAG_SIZE_AST           =  110,
       DIAG_SIZE_COMMENT       =  100,
+      DIAG_SIZE_CROSSTU       =  100,
       DIAG_SIZE_SEMA          = 3500,
       DIAG_SIZE_ANALYSIS      =  100
     };
@@ -49,7 +50,8 @@ namespace clang {
       DIAG_START_PARSE         = DIAG_START_LEX           + DIAG_SIZE_LEX,
       DIAG_START_AST           = DIAG_START_PARSE         + DIAG_SIZE_PARSE,
       DIAG_START_COMMENT       = DIAG_START_AST           + DIAG_SIZE_AST,
-      DIAG_START_SEMA          = DIAG_START_COMMENT       + DIAG_SIZE_COMMENT,
+      DIAG_START_CROSSTU       = DIAG_START_COMMENT       + DIAG_SIZE_CROSSTU,
+      DIAG_START_SEMA          = DIAG_START_CROSSTU       + DIAG_SIZE_COMMENT,
       DIAG_START_ANALYSIS      = DIAG_START_SEMA          + DIAG_SIZE_SEMA,
       DIAG_UPPER_LIMIT         = DIAG_START_ANALYSIS      + DIAG_SIZE_ANALYSIS
     };
diff --git a/include/clang/CrossTU/CrossTUDiagnostic.h b/include/clang/CrossTU/CrossTUDiagnostic.h
new file mode 100644
index 0000000000..dad38309fd
--- /dev/null
+++ b/include/clang/CrossTU/CrossTUDiagnostic.h
@@ -0,0 +1,29 @@
+//===--- CrossTUDiagnostic.h - Diagnostics for Cross TU ---------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_CROSSTU_CROSSTUDIAGNOSTIC_H
+#define LLVM_CLANG_CROSSTU_CROSSTUDIAGNOSTIC_H
+
+#include "clang/Basic/Diagnostic.h"
+
+namespace clang {
+namespace diag {
+enum {
+#define DIAG(ENUM, FLAGS, DEFAULT_MAPPING, DESC, GROUP, SFINAE, NOWERROR,      \
+             SHOWINSYSHEADER, CATEGORY)                                        \
+  ENUM,
+#define CROSSTUSTART
+#include "clang/Basic/DiagnosticCrossTUKinds.inc"
+#undef DIAG
+  NUM_BUILTIN_CROSSTU_DIAGNOSTICS
+};
+} // end namespace diag
+} // end namespace clang
+
+#endif // LLVM_CLANG_FRONTEND_FRONTENDDIAGNOSTIC_H
diff --git a/include/clang/CrossTU/CrossTranslationUnit.h b/include/clang/CrossTU/CrossTranslationUnit.h
new file mode 100644
index 0000000000..f2a1690250
--- /dev/null
+++ b/include/clang/CrossTU/CrossTranslationUnit.h
@@ -0,0 +1,159 @@
+//===--- CrossTranslationUnit.h - -------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file provides an interface to load binary AST dumps on demand. This
+//  feature can be utilized for tools that require cross translation unit
+//  support.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_CROSSTU_CROSSTRANSLATIONUNIT_H
+#define LLVM_CLANG_CROSSTU_CROSSTRANSLATIONUNIT_H
+
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/Error.h"
+
+namespace clang {
+class CompilerInstance;
+class ASTContext;
+class ASTImporter;
+class ASTUnit;
+class DeclContext;
+class FunctionDecl;
+class NamedDecl;
+class TranslationUnitDecl;
+
+namespace cross_tu {
+
+enum class index_error_code {
+  unspecified = 1,
+  missing_index_file,
+  invalid_index_format,
+  multiple_definitions,
+  missing_definition,
+  failed_import,
+  failed_to_get_external_ast,
+  failed_to_generate_usr
+};
+
+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) {}
+  void log(raw_ostream &OS) const override;
+  std::error_code convertToErrorCode() const override;
+  index_error_code getCode() const { return Code; }
+  int getLineNum() const { return LineNo; }
+  std::string getFileName() const { return FileName; }
+
+private:
+  index_error_code Code;
+  std::string FileName;
+  int LineNo;
+};
+
+/// \brief This function parses an index file that determines which
+///        translation unit contains which definition.
+///
+/// The index file format is the following:
+/// each line consists of an USR and a filepath separated by a space.
+///
+/// \return Returns a map where the USR is the key and the filepath is the value
+///         or an error.
+llvm::Expected<llvm::StringMap<std::string>>
+parseCrossTUIndex(StringRef IndexPath, StringRef CrossTUDir);
+
+std::string createCrossTUIndexString(const llvm::StringMap<std::string> &Index);
+
+/// \brief This class is used for tools that requires cross translation
+///        unit capability.
+///
+/// This class can load function definitions from external AST files.
+/// The loaded definition will be merged back to the original AST using the
+/// AST Importer.
+/// In order to use this class, an index file is required that describes
+/// the locations of the AST files for each function definition.
+///
+/// Note that this class also implements caching.
+class CrossTranslationUnitContext {
+public:
+  CrossTranslationUnitContext(CompilerInstance &CI);
+  ~CrossTranslationUnitContext();
+
+  /// \brief This function loads a function definition from an external AST
+  ///        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.
+  ///
+  /// \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);
+
+  /// \brief 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.
+  ///
+  /// \return Returns an ASTUnit that contains the definition of the looked up
+  /// function.
+  ///
+  /// Note that the AST files should also be in the \p CrossTUDir.
+  llvm::Expected<ASTUnit *> loadExternalAST(StringRef LookupName,
+                                            StringRef CrossTUDir,
+                                            StringRef IndexName);
+
+  /// \brief 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);
+
+  /// \brief Get a name to identify a function.
+  static std::string getLookupName(const NamedDecl *ND);
+
+  /// \brief Emit diagnostics for the user for potential configuration errors.
+  void emitCrossTUDiagnostics(const IndexError &IE);
+
+private:
+  ASTImporter &getOrCreateASTImporter(ASTContext &From);
+  const FunctionDecl *findFunctionInDeclContext(const DeclContext *DC,
+                                                StringRef LookupFnName);
+
+  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;
+};
+
+} // namespace cross_tu
+} // namespace clang
+
+#endif // LLVM_CLANG_CROSSTU_CROSSTRANSLATIONUNIT_H
diff --git a/lib/AST/ASTImporter.cpp b/lib/AST/ASTImporter.cpp
index 2c0bb11cc4..49e8321953 100644
--- a/lib/AST/ASTImporter.cpp
+++ b/lib/AST/ASTImporter.cpp
@@ -1846,6 +1846,8 @@ Decl *ASTNodeImporter::VisitFunctionDecl(FunctionDecl *D) {
   if (ToD)
     return ToD;
 
+  const FunctionDecl *FoundWithoutBody = nullptr;
+
   // Try to find a function in our own ("to") context with the same name, same
   // type, and in the same context as the function we're importing.
   if (!LexicalDC->isFunctionOrMethod()) {
@@ -1863,6 +1865,13 @@ Decl *ASTNodeImporter::VisitFunctionDecl(FunctionDecl *D) {
           if (Importer.IsStructurallyEquivalent(D->getType(), 
                                                 FoundFunction->getType())) {
             // FIXME: Actually try to merge the body and other attributes.
+            const FunctionDecl *FromBodyDecl = nullptr;
+            D->hasBody(FromBodyDecl);
+            if (D == FromBodyDecl && !FoundFunction->hasBody()) {
+              // This function is needed to merge completely.
+              FoundWithoutBody = FoundFunction;
+              break;
+            }
             return Importer.Imported(D, FoundFunction);
           }
 
@@ -2013,6 +2022,12 @@ Decl *ASTNodeImporter::VisitFunctionDecl(FunctionDecl *D) {
   }
   ToFunction->setParams(Parameters);
 
+  if (FoundWithoutBody) {
+    auto *Recent = const_cast<FunctionDecl *>(
+          FoundWithoutBody->getMostRecentDecl());
+    ToFunction->setPreviousDecl(Recent);
+  }
+
   if (usedDifferentExceptionSpec) {
     // Update FunctionProtoType::ExtProtoInfo.
     QualType T = Importer.Import(D->getType());
diff --git a/lib/Basic/DiagnosticIDs.cpp b/lib/Basic/DiagnosticIDs.cpp
index b74047a4d1..1a7b835ebc 100644
--- a/lib/Basic/DiagnosticIDs.cpp
+++ b/lib/Basic/DiagnosticIDs.cpp
@@ -109,6 +109,7 @@ static const StaticDiagInfoRec StaticDiagInfo[] = {
 #include "clang/Basic/DiagnosticParseKinds.inc"
 #include "clang/Basic/DiagnosticASTKinds.inc"
 #include "clang/Basic/DiagnosticCommentKinds.inc"
+#include "clang/Basic/DiagnosticCrossTUKinds.inc"
 #include "clang/Basic/DiagnosticSemaKinds.inc"
 #include "clang/Basic/DiagnosticAnalysisKinds.inc"
 #undef DIAG
@@ -146,7 +147,8 @@ CATEGORY(LEX, SERIALIZATION)
 CATEGORY(PARSE, LEX)
 CATEGORY(AST, PARSE)
 CATEGORY(COMMENT, AST)
-CATEGORY(SEMA, COMMENT)
+CATEGORY(CROSSTU, COMMENT)
+CATEGORY(SEMA, CROSSTU)
 CATEGORY(ANALYSIS, SEMA)
 #undef CATEGORY
 
diff --git a/lib/CMakeLists.txt b/lib/CMakeLists.txt
index dfd819a407..b3fa93555b 100644
--- a/lib/CMakeLists.txt
+++ b/lib/CMakeLists.txt
@@ -4,6 +4,7 @@ add_subdirectory(Lex)
 add_subdirectory(Parse)
 add_subdirectory(AST)
 add_subdirectory(ASTMatchers)
+add_subdirectory(CrossTU)
 add_subdirectory(Sema)
 add_subdirectory(CodeGen)
 add_subdirectory(Analysis)
diff --git a/lib/CrossTU/CMakeLists.txt b/lib/CrossTU/CMakeLists.txt
new file mode 100644
index 0000000000..632b5072ad
--- /dev/null
+++ b/lib/CrossTU/CMakeLists.txt
@@ -0,0 +1,13 @@
+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_clang_library(clangCrossTU
+  CrossTranslationUnit.cpp
+
+  LINK_LIBS
+  clangAST
+  clangBasic
+  clangFrontend
+  clangIndex
+  )
diff --git a/lib/CrossTU/CrossTranslationUnit.cpp b/lib/CrossTU/CrossTranslationUnit.cpp
new file mode 100644
index 0000000000..833fb57860
--- /dev/null
+++ b/lib/CrossTU/CrossTranslationUnit.cpp
@@ -0,0 +1,271 @@
+//===--- CrossTranslationUnit.cpp - -----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file implements the CrossTranslationUnit interface.
+//
+//===----------------------------------------------------------------------===//
+#include "clang/CrossTU/CrossTranslationUnit.h"
+#include "clang/AST/ASTImporter.h"
+#include "clang/AST/Decl.h"
+#include "clang/Basic/TargetInfo.h"
+#include "clang/CrossTU/CrossTUDiagnostic.h"
+#include "clang/Frontend/ASTUnit.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/FrontendDiagnostic.h"
+#include "clang/Frontend/TextDiagnosticPrinter.h"
+#include "clang/Index/USRGeneration.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/raw_ostream.h"
+#include <fstream>
+#include <sstream>
+
+namespace clang {
+namespace cross_tu {
+
+namespace {
+// FIXME: This class is will be removed after the transition to llvm::Error.
+class IndexErrorCategory : public std::error_category {
+public:
+  const char *name() const noexcept override { return "clang.index"; }
+
+  std::string message(int Condition) const override {
+    switch (static_cast<index_error_code>(Condition)) {
+    case index_error_code::unspecified:
+      return "An unknown error has occurred.";
+    case index_error_code::missing_index_file:
+      return "The index file is missing.";
+    case index_error_code::invalid_index_format:
+      return "Invalid index file format.";
+    case index_error_code::multiple_definitions:
+      return "Multiple definitions in the index file.";
+    case index_error_code::missing_definition:
+      return "Missing definition from the index file.";
+    case index_error_code::failed_import:
+      return "Failed to import the definition.";
+    case index_error_code::failed_to_get_external_ast:
+      return "Failed to load external AST source.";
+    case index_error_code::failed_to_generate_usr:
+      return "Failed to generate USR.";
+    }
+    llvm_unreachable("Unrecognized index_error_code.");
+  }
+};
+
+static llvm::ManagedStatic<IndexErrorCategory> Category;
+} // end anonymous namespace
+
+char IndexError::ID;
+
+void IndexError::log(raw_ostream &OS) const {
+  OS << Category->message(static_cast<int>(Code)) << '\n';
+}
+
+std::error_code IndexError::convertToErrorCode() const {
+  return std::error_code(static_cast<int>(Code), *Category);
+}
+
+llvm::Expected<llvm::StringMap<std::string>>
+parseCrossTUIndex(StringRef IndexPath, StringRef CrossTUDir) {
+  std::ifstream ExternalFnMapFile(IndexPath);
+  if (!ExternalFnMapFile)
+    return llvm::make_error<IndexError>(index_error_code::missing_index_file,
+                                        IndexPath.str());
+
+  llvm::StringMap<std::string> Result;
+  std::string Line;
+  unsigned LineNo = 1;
+  while (std::getline(ExternalFnMapFile, Line)) {
+    const size_t Pos = Line.find(" ");
+    if (Pos > 0 && Pos != std::string::npos) {
+      StringRef LineRef{Line};
+      StringRef FunctionLookupName = LineRef.substr(0, Pos);
+      if (Result.count(FunctionLookupName))
+        return llvm::make_error<IndexError>(
+            index_error_code::multiple_definitions, IndexPath.str(), LineNo);
+      StringRef FileName = LineRef.substr(Pos + 1);
+      SmallString<256> FilePath = CrossTUDir;
+      if (llvm::sys::path::is_absolute(FileName))
+        FilePath = FileName;
+      else
+        llvm::sys::path::append(FilePath, FileName);
+      Result[FunctionLookupName] = FilePath.str().str();
+    } else
+      return llvm::make_error<IndexError>(
+          index_error_code::invalid_index_format, IndexPath.str(), LineNo);
+    LineNo++;
+  }
+  return Result;
+}
+
+std::string
+createCrossTUIndexString(const llvm::StringMap<std::string> &Index) {
+  std::ostringstream Result;
+  for (const auto &E : Index)
+    Result << E.getKey().str() << " " << E.getValue() << '\n';
+  return Result.str();
+}
+
+CrossTranslationUnitContext::CrossTranslationUnitContext(CompilerInstance &CI)
+    : CI(CI), Context(CI.getASTContext()) {}
+
+CrossTranslationUnitContext::~CrossTranslationUnitContext() {}
+
+std::string CrossTranslationUnitContext::getLookupName(const NamedDecl *ND) {
+  SmallString<128> DeclUSR;
+  bool Ret = index::generateUSRForDecl(ND, DeclUSR);
+  assert(!Ret && "Unable to generate USR");
+  return DeclUSR.str();
+}
+
+/// Recursively visits the function decls of a DeclContext, and looks up a
+/// function based on USRs.
+const FunctionDecl *
+CrossTranslationUnitContext::findFunctionInDeclContext(const DeclContext *DC,
+                                                       StringRef LookupFnName) {
+  assert(DC && "Declaration Context must not be null");
+  for (const Decl *D : DC->decls()) {
+    const auto *SubDC = dyn_cast<DeclContext>(D);
+    if (SubDC)
+      if (const auto *FD = findFunctionInDeclContext(SubDC, LookupFnName))
+        return FD;
+
+    const auto *ND = dyn_cast<FunctionDecl>(D);
+    const FunctionDecl *ResultDecl;
+    if (!ND || !ND->hasBody(ResultDecl))
+      continue;
+    if (getLookupName(ResultDecl) != LookupFnName)
+      continue;
+    return ResultDecl;
+  }
+  return nullptr;
+}
+
+llvm::Expected<const FunctionDecl *>
+CrossTranslationUnitContext::getCrossTUDefinition(const FunctionDecl *FD,
+                                                  StringRef CrossTUDir,
+                                                  StringRef IndexName) {
+  assert(!FD->hasBody() && "FD has a definition in current translation unit!");
+  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);
+  if (!ASTUnitOrError)
+    return ASTUnitOrError.takeError();
+  ASTUnit *Unit = *ASTUnitOrError;
+  if (!Unit)
+    return llvm::make_error<IndexError>(
+        index_error_code::failed_to_get_external_ast);
+  assert(&Unit->getFileManager() ==
+         &Unit->getASTContext().getSourceManager().getFileManager());
+
+  TranslationUnitDecl *TU = Unit->getASTContext().getTranslationUnitDecl();
+  if (const FunctionDecl *ResultDecl =
+          findFunctionInDeclContext(TU, LookupFnName))
+    return importDefinition(ResultDecl);
+  return llvm::make_error<IndexError>(index_error_code::failed_import);
+}
+
+void CrossTranslationUnitContext::emitCrossTUDiagnostics(const IndexError &IE) {
+  switch (IE.getCode()) {
+  case index_error_code::missing_index_file:
+    Context.getDiagnostics().Report(diag::err_fe_error_opening)
+        << IE.getFileName() << "required by the CrossTU functionality";
+    break;
+  case index_error_code::invalid_index_format:
+    Context.getDiagnostics().Report(diag::err_fnmap_parsing)
+        << IE.getFileName() << IE.getLineNum();
+  case index_error_code::multiple_definitions:
+    Context.getDiagnostics().Report(diag::err_multiple_def_index)
+        << IE.getLineNum();
+    break;
+  default:
+    break;
+  }
+}
+
+llvm::Expected<ASTUnit *> CrossTranslationUnitContext::loadExternalAST(
+    StringRef LookupName, StringRef CrossTUDir, StringRef IndexName) {
+  // 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.
+  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
+        llvm::sys::path::append(IndexFile, IndexName);
+      llvm::Expected<llvm::StringMap<std::string>> IndexOrErr =
+          parseCrossTUIndex(IndexFile, CrossTUDir);
+      if (IndexOrErr)
+        FunctionFileMap = *IndexOrErr;
+      else
+        return IndexOrErr.takeError();
+    }
+
+    auto It = FunctionFileMap.find(LookupName);
+    if (It == FunctionFileMap.end())
+      return llvm::make_error<IndexError>(index_error_code::missing_definition);
+    StringRef ASTFileName = It->second;
+    auto ASTCacheEntry = FileASTUnitMap.find(ASTFileName);
+    if (ASTCacheEntry == FileASTUnitMap.end()) {
+      IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions();
+      TextDiagnosticPrinter *DiagClient =
+          new TextDiagnosticPrinter(llvm::errs(), &*DiagOpts);
+      IntrusiveRefCntPtr<DiagnosticIDs> DiagID(new DiagnosticIDs());
+      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);
+    } else {
+      Unit = ASTCacheEntry->second.get();
+    }
+    FunctionASTUnitMap[LookupName] = Unit;
+  } else {
+    Unit = FnUnitCacheEntry->second;
+  }
+  return Unit;
+}
+
+llvm::Expected<const FunctionDecl *>
+CrossTranslationUnitContext::importDefinition(const FunctionDecl *FD) {
+  ASTImporter &Importer = getOrCreateASTImporter(FD->getASTContext());
+  auto *ToDecl =
+      cast<FunctionDecl>(Importer.Import(const_cast<FunctionDecl *>(FD)));
+  assert(ToDecl->hasBody());
+  assert(FD->hasBody() && "Functions already imported should have body.");
+  return ToDecl;
+}
+
+ASTImporter &
+CrossTranslationUnitContext::getOrCreateASTImporter(ASTContext &From) {
+  auto I = ASTUnitImporterMap.find(From.getTranslationUnitDecl());
+  if (I != ASTUnitImporterMap.end())
+    return *I->second;
+  ASTImporter *NewImporter =
+      new ASTImporter(Context, Context.getSourceManager().getFileManager(),
+                      From, From.getSourceManager().getFileManager(), false);
+  ASTUnitImporterMap[From.getTranslationUnitDecl()].reset(NewImporter);
+  return *NewImporter;
+}
+
+} // namespace cross_tu
+} // namespace clang
diff --git a/test/Analysis/func-mapping-test.cpp b/test/Analysis/func-mapping-test.cpp
new file mode 100644
index 0000000000..37e653882b
--- /dev/null
+++ b/test/Analysis/func-mapping-test.cpp
@@ -0,0 +1,7 @@
+// RUN: %clang_func_map %s -- | FileCheck %s
+
+int f(int) {
+  return 0;
+}
+
+// CHECK: c:@F@f#I#
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 9bc733bc77..5fd6b11f9f 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -54,6 +54,7 @@ list(APPEND CLANG_TEST_DEPS
   clang-rename
   clang-refactor
   clang-diff
+  clang-func-mapping
   )
   
 if(CLANG_ENABLE_STATIC_ANALYZER)
diff --git a/test/lit.cfg.py b/test/lit.cfg.py
index 0f1733c73b..4f419f11e2 100644
--- a/test/lit.cfg.py
+++ b/test/lit.cfg.py
@@ -125,6 +125,7 @@ config.substitutions.append( ('%clang_cl', ' ' + config.clang +
                               ' --driver-mode=cl '))
 config.substitutions.append( ('%clangxx', ' ' + config.clang +
                               ' --driver-mode=g++ '))
+config.substitutions.append( ('%clang_func_map', ' ' + lit.util.which('clang-func-mapping', config.environment['PATH']) + ' ') )
 config.substitutions.append( ('%clang', ' ' + config.clang + ' ') )
 config.substitutions.append( ('%test_debuginfo',
                              ' ' + config.llvm_src_root +  '/utils/test_debuginfo.pl ') )
diff --git a/tools/CMakeLists.txt b/tools/CMakeLists.txt
index 6e18724a32..9f76d36dba 100644
--- a/tools/CMakeLists.txt
+++ b/tools/CMakeLists.txt
@@ -21,6 +21,7 @@ endif()
 
 if(CLANG_ENABLE_STATIC_ANALYZER)
   add_clang_subdirectory(clang-check)
+  add_clang_subdirectory(clang-func-mapping)
   add_clang_subdirectory(scan-build)
   add_clang_subdirectory(scan-view)
 endif()
diff --git a/tools/clang-func-mapping/CMakeLists.txt b/tools/clang-func-mapping/CMakeLists.txt
new file mode 100644
index 0000000000..8c10fcd757
--- /dev/null
+++ b/tools/clang-func-mapping/CMakeLists.txt
@@ -0,0 +1,22 @@
+set(LLVM_LINK_COMPONENTS
+  ${LLVM_TARGETS_TO_BUILD}
+  asmparser
+  support
+  mc
+  )
+
+add_clang_executable(clang-func-mapping
+  ClangFnMapGen.cpp
+  )
+
+target_link_libraries(clang-func-mapping
+  clangAST
+  clangBasic
+  clangCrossTU
+  clangFrontend
+  clangIndex
+  clangTooling
+  )
+
+install(TARGETS clang-func-mapping
+  RUNTIME DESTINATION bin)
diff --git a/tools/clang-func-mapping/ClangFnMapGen.cpp b/tools/clang-func-mapping/ClangFnMapGen.cpp
new file mode 100644
index 0000000000..4bf812fffe
--- /dev/null
+++ b/tools/clang-func-mapping/ClangFnMapGen.cpp
@@ -0,0 +1,124 @@
+//===- ClangFnMapGen.cpp -----------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--------------------------------------------------------------------===//
+//
+// Clang tool which creates a list of defined functions and the files in which
+// they are defined.
+//
+//===--------------------------------------------------------------------===//
+
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/GlobalDecl.h"
+#include "clang/AST/Mangle.h"
+#include "clang/AST/StmtVisitor.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Basic/TargetInfo.h"
+#include "clang/CrossTU/CrossTranslationUnit.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/FrontendActions.h"
+#include "clang/Index/USRGeneration.h"
+#include "clang/Tooling/CommonOptionsParser.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/Signals.h"
+#include <sstream>
+#include <string>
+#include <vector>
+
+using namespace llvm;
+using namespace clang;
+using namespace clang::cross_tu;
+using namespace clang::tooling;
+
+static cl::OptionCategory ClangFnMapGenCategory("clang-fnmapgen options");
+
+class MapFunctionNamesConsumer : public ASTConsumer {
+public:
+  MapFunctionNamesConsumer(ASTContext &Context) : Ctx(Context) {}
+
+  ~MapFunctionNamesConsumer() {
+    // Flush results to standard output.
+    llvm::outs() << createCrossTUIndexString(Index);
+  }
+
+  virtual void HandleTranslationUnit(ASTContext &Ctx) {
+    handleDecl(Ctx.getTranslationUnitDecl());
+  }
+
+private:
+  void handleDecl(const Decl *D);
+
+  ASTContext &Ctx;
+  llvm::StringMap<std::string> Index;
+  std::string CurrentFileName;
+};
+
+void MapFunctionNamesConsumer::handleDecl(const Decl *D) {
+  if (!D)
+    return;
+
+  if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
+    if (FD->isThisDeclarationADefinition()) {
+      if (const Stmt *Body = FD->getBody()) {
+        std::string LookupName = CrossTranslationUnitContext::getLookupName(FD);
+        const SourceManager &SM = Ctx.getSourceManager();
+        if (CurrentFileName.empty()) {
+          CurrentFileName =
+              SM.getFileEntryForID(SM.getMainFileID())->tryGetRealPathName();
+          if (CurrentFileName.empty())
+            CurrentFileName = "invalid_file";
+        }
+
+        switch (FD->getLinkageInternal()) {
+        case ExternalLinkage:
+        case VisibleNoLinkage:
+        case UniqueExternalLinkage:
+          if (SM.isInMainFile(Body->getLocStart()))
+            Index[LookupName] = CurrentFileName;
+        default:
+          break;
+        }
+      }
+    }
+  }
+
+  if (const auto *DC = dyn_cast<DeclContext>(D))
+    for (const Decl *D : DC->decls())
+      handleDecl(D);
+}
+
+class MapFunctionNamesAction : public ASTFrontendAction {
+protected:
+  std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &CI,
+                                                 llvm::StringRef) {
+    std::unique_ptr<ASTConsumer> PFC(
+        new MapFunctionNamesConsumer(CI.getASTContext()));
+    return PFC;
+  }
+};
+
+static cl::extrahelp CommonHelp(CommonOptionsParser::HelpMessage);
+
+int main(int argc, const char **argv) {
+  // Print a stack trace if we signal out.
+  sys::PrintStackTraceOnErrorSignal(argv[0], false);
+  PrettyStackTraceProgram X(argc, argv);
+
+  const char *Overview = "\nThis tool collects the USR name and location "
+                         "of all functions definitions in the source files "
+                         "(excluding headers).\n";
+  CommonOptionsParser OptionsParser(argc, argv, ClangFnMapGenCategory,
+                                    cl::ZeroOrMore, Overview);
+
+  ClangTool Tool(OptionsParser.getCompilations(),
+                 OptionsParser.getSourcePathList());
+  Tool.run(newFrontendActionFactory<MapFunctionNamesAction>().get());
+  return 0;
+}
diff --git a/tools/diagtool/DiagnosticNames.cpp b/tools/diagtool/DiagnosticNames.cpp
index c0bc4ecf62..4701f8e61c 100644
--- a/tools/diagtool/DiagnosticNames.cpp
+++ b/tools/diagtool/DiagnosticNames.cpp
@@ -32,6 +32,7 @@ static const DiagnosticRecord BuiltinDiagnosticsByID[] = {
              SFINAE,NOWERROR,SHOWINSYSHEADER,CATEGORY)            \
   { #ENUM, diag::ENUM, STR_SIZE(#ENUM, uint8_t) },
 #include "clang/Basic/DiagnosticCommonKinds.inc"
+#include "clang/Basic/DiagnosticCrossTUKinds.inc"
 #include "clang/Basic/DiagnosticDriverKinds.inc"
 #include "clang/Basic/DiagnosticFrontendKinds.inc"
 #include "clang/Basic/DiagnosticSerializationKinds.inc"
diff --git a/unittests/CMakeLists.txt b/unittests/CMakeLists.txt
index b622d66af4..090de3b06e 100644
--- a/unittests/CMakeLists.txt
+++ b/unittests/CMakeLists.txt
@@ -19,6 +19,7 @@ if(CLANG_ENABLE_STATIC_ANALYZER)
 endif()
 add_subdirectory(ASTMatchers)
 add_subdirectory(AST)
+add_subdirectory(CrossTU)
 add_subdirectory(Tooling)
 add_subdirectory(Format)
 add_subdirectory(Rewrite)
diff --git a/unittests/CrossTU/CMakeLists.txt b/unittests/CrossTU/CMakeLists.txt
new file mode 100644
index 0000000000..3c479c4473
--- /dev/null
+++ b/unittests/CrossTU/CMakeLists.txt
@@ -0,0 +1,16 @@
+set(LLVM_LINK_COMPONENTS
+  ${LLVM_TARGETS_TO_BUILD}
+  Support
+  )
+
+add_clang_unittest(CrossTUTests
+  CrossTranslationUnitTest.cpp
+  )
+
+target_link_libraries(CrossTUTests
+  clangAST
+  clangBasic
+  clangCrossTU
+  clangFrontend
+  clangTooling
+  )
diff --git a/unittests/CrossTU/CrossTranslationUnitTest.cpp b/unittests/CrossTU/CrossTranslationUnitTest.cpp
new file mode 100644
index 0000000000..6b9158445d
--- /dev/null
+++ b/unittests/CrossTU/CrossTranslationUnitTest.cpp
@@ -0,0 +1,138 @@
+//===- unittest/Tooling/CrossTranslationUnitTest.cpp - Tooling unit tests -===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/CrossTU/CrossTranslationUnit.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/Frontend/FrontendAction.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/Config/llvm-config.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "gtest/gtest.h"
+#include <cassert>
+
+namespace clang {
+namespace cross_tu {
+
+namespace {
+
+class CTUASTConsumer : public clang::ASTConsumer {
+public:
+  explicit CTUASTConsumer(clang::CompilerInstance &CI, bool *Success)
+      : CTU(CI), Success(Success) {}
+
+  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;
+    }
+    assert(FD && FD->getName() == "f");
+    bool OrigFDHasBody = FD->hasBody();
+
+    // Prepare the index file and the AST file.
+    int ASTFD;
+    llvm::SmallString<256> ASTFileName;
+    ASSERT_FALSE(
+        llvm::sys::fs::createTemporaryFile("f_ast", "ast", ASTFD, ASTFileName));
+    llvm::tool_output_file ASTFile(ASTFileName, ASTFD);
+
+    int IndexFD;
+    llvm::SmallString<256> IndexFileName;
+    ASSERT_FALSE(llvm::sys::fs::createTemporaryFile("index", "txt", IndexFD,
+                                                    IndexFileName));
+    llvm::tool_output_file IndexFile(IndexFileName, IndexFD);
+    IndexFile.os() << "c:@F@f#I# " << ASTFileName << "\n";
+    IndexFile.os().flush();
+    EXPECT_TRUE(llvm::sys::fs::exists(IndexFileName));
+
+    StringRef SourceText = "int f(int) { return 0; }\n";
+    // This file must exist since the saved ASTFile will reference it.
+    int SourceFD;
+    llvm::SmallString<256> SourceFileName;
+    ASSERT_FALSE(llvm::sys::fs::createTemporaryFile("input", "cpp", SourceFD,
+                                                    SourceFileName));
+    llvm::tool_output_file SourceFile(SourceFileName, SourceFD);
+    SourceFile.os() << SourceText;
+    SourceFile.os().flush();
+    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;
+
+    *Success = NewFD && NewFD->hasBody() && !OrigFDHasBody;
+  }
+
+private:
+  CrossTranslationUnitContext CTU;
+  bool *Success;
+};
+
+class CTUAction : public clang::ASTFrontendAction {
+public:
+  CTUAction(bool *Success) : Success(Success) {}
+
+protected:
+  std::unique_ptr<clang::ASTConsumer>
+  CreateASTConsumer(clang::CompilerInstance &CI, StringRef) override {
+    return llvm::make_unique<CTUASTConsumer>(CI, Success);
+  }
+
+private:
+  bool *Success;
+};
+
+} // end namespace
+
+TEST(CrossTranslationUnit, CanLoadFunctionDefinition) {
+  bool Success = false;
+  EXPECT_TRUE(tooling::runToolOnCode(new CTUAction(&Success), "int f(int);"));
+  EXPECT_TRUE(Success);
+}
+
+TEST(CrossTranslationUnit, IndexFormatCanBeParsed) {
+  llvm::StringMap<std::string> Index;
+  Index["a"] = "b";
+  Index["c"] = "d";
+  Index["e"] = "f";
+  std::string IndexText = createCrossTUIndexString(Index);
+
+  int IndexFD;
+  llvm::SmallString<256> IndexFileName;
+  ASSERT_FALSE(llvm::sys::fs::createTemporaryFile("index", "txt", IndexFD,
+                                                  IndexFileName));
+  llvm::tool_output_file IndexFile(IndexFileName, IndexFD);
+  IndexFile.os() << IndexText;
+  IndexFile.os().flush();
+  EXPECT_TRUE(llvm::sys::fs::exists(IndexFileName));
+  llvm::Expected<llvm::StringMap<std::string>> IndexOrErr =
+      parseCrossTUIndex(IndexFileName, "");
+  EXPECT_TRUE((bool)IndexOrErr);
+  llvm::StringMap<std::string> ParsedIndex = IndexOrErr.get();
+  for (const auto &E : Index) {
+    EXPECT_TRUE(ParsedIndex.count(E.getKey()));
+    EXPECT_EQ(ParsedIndex[E.getKey()], E.getValue());
+  }
+  for (const auto &E : ParsedIndex)
+    EXPECT_TRUE(Index.count(E.getKey()));
+}
+
+} // end namespace cross_tu
+} // end namespace clang