Vendor import of clang release_30 branch r142614:

http://llvm.org/svn/llvm-project/cfe/branches/release_30@142614

1 files changed, 515 insertions, 282 deletions

diff --git a/lib/Basic/SourceManager.cpp b/lib/Basic/SourceManager.cpp
index 45922c1..364663e 100644
--- a/lib/Basic/SourceManager.cpp
+++ b/lib/Basic/SourceManager.cpp
@@ -17,10 +17,12 @@
 #include "clang/Basic/FileManager.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/Capacity.h"
 #include <algorithm>
 #include <string>
 #include <cstring>
@@ -39,9 +41,8 @@ ContentCache::~ContentCache() {
     delete Buffer.getPointer();
 }
 
-/// getSizeBytesMapped - Returns the number of bytes actually mapped for
-///  this ContentCache.  This can be 0 if the MemBuffer was not actually
-///  instantiated.
+/// getSizeBytesMapped - Returns the number of bytes actually mapped for this
+/// ContentCache. This can be 0 if the MemBuffer was not actually expanded.
 unsigned ContentCache::getSizeBytesMapped() const {
   return Buffer.getPointer() ? Buffer.getPointer()->getBufferSize() : 0;
 }
@@ -78,7 +79,7 @@ void ContentCache::replaceBuffer(const llvm::MemoryBuffer *B,
   Buffer.setInt(DoNotFree? DoNotFreeFlag : 0);
 }
 
-const llvm::MemoryBuffer *ContentCache::getBuffer(Diagnostic &Diag,
+const llvm::MemoryBuffer *ContentCache::getBuffer(DiagnosticsEngine &Diag,
                                                   const SourceManager &SM,
                                                   SourceLocation Loc,
                                                   bool *Invalid) const {
@@ -105,7 +106,7 @@ const llvm::MemoryBuffer *ContentCache::getBuffer(Diagnostic &Diag,
   // that we are in an inconsistent situation and error out as quickly as
   // possible.
   if (!Buffer.getPointer()) {
-    const llvm::StringRef FillStr("<<<MISSING SOURCE FILE>>>\n");
+    const StringRef FillStr("<<<MISSING SOURCE FILE>>>\n");
     Buffer.setPointer(MemoryBuffer::getNewMemBuffer(ContentsEntry->getSize(), 
                                                     "<invalid>"));
     char *Ptr = const_cast<char*>(Buffer.getPointer()->getBufferStart());
@@ -143,7 +144,7 @@ const llvm::MemoryBuffer *ContentCache::getBuffer(Diagnostic &Diag,
   // If the buffer is valid, check to see if it has a UTF Byte Order Mark
   // (BOM).  We only support UTF-8 with and without a BOM right now.  See
   // http://en.wikipedia.org/wiki/Byte_order_mark for more information.
-  llvm::StringRef BufStr = Buffer.getPointer()->getBuffer();
+  StringRef BufStr = Buffer.getPointer()->getBuffer();
   const char *InvalidBOM = llvm::StringSwitch<const char *>(BufStr)
     .StartsWith("\xFE\xFF", "UTF-16 (BE)")
     .StartsWith("\xFF\xFE", "UTF-16 (LE)")
@@ -169,7 +170,7 @@ const llvm::MemoryBuffer *ContentCache::getBuffer(Diagnostic &Diag,
   return Buffer.getPointer();
 }
 
-unsigned LineTableInfo::getLineTableFilenameID(llvm::StringRef Name) {
+unsigned LineTableInfo::getLineTableFilenameID(StringRef Name) {
   // Look up the filename in the string table, returning the pre-existing value
   // if it exists.
   llvm::StringMapEntry<unsigned> &Entry =
@@ -186,7 +187,7 @@ unsigned LineTableInfo::getLineTableFilenameID(llvm::StringRef Name) {
 /// AddLineNote - Add a line note to the line table that indicates that there
 /// is a #line at the specified FID/Offset location which changes the presumed
 /// location to LineNo/FilenameID.
-void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset,
+void LineTableInfo::AddLineNote(int FID, unsigned Offset,
                                 unsigned LineNo, int FilenameID) {
   std::vector<LineEntry> &Entries = LineEntries[FID];
 
@@ -217,7 +218,7 @@ void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset,
 /// presumed #include stack.  If it is 1, this is a file entry, if it is 2 then
 /// this is a file exit.  FileKind specifies whether this is a system header or
 /// extern C system header.
-void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset,
+void LineTableInfo::AddLineNote(int FID, unsigned Offset,
                                 unsigned LineNo, int FilenameID,
                                 unsigned EntryExit,
                                 SrcMgr::CharacteristicKind FileKind) {
@@ -251,7 +252,7 @@ void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset,
 
 /// FindNearestLineEntry - Find the line entry nearest to FID that is before
 /// it.  If there is no line entry before Offset in FID, return null.
-const LineEntry *LineTableInfo::FindNearestLineEntry(unsigned FID,
+const LineEntry *LineTableInfo::FindNearestLineEntry(int FID,
                                                      unsigned Offset) {
   const std::vector<LineEntry> &Entries = LineEntries[FID];
   assert(!Entries.empty() && "No #line entries for this FID after all!");
@@ -270,14 +271,14 @@ const LineEntry *LineTableInfo::FindNearestLineEntry(unsigned FID,
 
 /// \brief Add a new line entry that has already been encoded into
 /// the internal representation of the line table.
-void LineTableInfo::AddEntry(unsigned FID,
+void LineTableInfo::AddEntry(int FID,
                              const std::vector<LineEntry> &Entries) {
   LineEntries[FID] = Entries;
 }
 
 /// getLineTableFilenameID - Return the uniqued ID for the specified filename.
 ///
-unsigned SourceManager::getLineTableFilenameID(llvm::StringRef Name) {
+unsigned SourceManager::getLineTableFilenameID(StringRef Name) {
   if (LineTable == 0)
     LineTable = new LineTableInfo();
   return LineTable->getLineTableFilenameID(Name);
@@ -289,7 +290,7 @@ unsigned SourceManager::getLineTableFilenameID(llvm::StringRef Name) {
 /// unspecified.
 void SourceManager::AddLineNote(SourceLocation Loc, unsigned LineNo,
                                 int FilenameID) {
-  std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc);
+  std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
 
   bool Invalid = false;
   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid);
@@ -319,7 +320,7 @@ void SourceManager::AddLineNote(SourceLocation Loc, unsigned LineNo,
     return AddLineNote(Loc, LineNo, FilenameID);
   }
 
-  std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc);
+  std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
 
   bool Invalid = false;
   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid);
@@ -362,7 +363,7 @@ LineTableInfo &SourceManager::getLineTable() {
 // Private 'Create' methods.
 //===----------------------------------------------------------------------===//
 
-SourceManager::SourceManager(Diagnostic &Diag, FileManager &FileMgr)
+SourceManager::SourceManager(DiagnosticsEngine &Diag, FileManager &FileMgr)
   : Diag(Diag), FileMgr(FileMgr), OverridenFilesKeepOriginalName(true),
     ExternalSLocEntries(0), LineTable(0), NumLinearScans(0),
     NumBinaryProbes(0), FakeBufferForRecovery(0) {
@@ -387,11 +388,18 @@ SourceManager::~SourceManager() {
   }
   
   delete FakeBufferForRecovery;
+
+  for (llvm::DenseMap<FileID, MacroArgsMap *>::iterator
+         I = MacroArgsCacheMap.begin(),E = MacroArgsCacheMap.end(); I!=E; ++I) {
+    delete I->second;
+  }
 }
 
 void SourceManager::clearIDTables() {
   MainFileID = FileID();
-  SLocEntryTable.clear();
+  LocalSLocEntryTable.clear();
+  LoadedSLocEntryTable.clear();
+  SLocEntryLoaded.clear();
   LastLineNoFileIDQuery = FileID();
   LastLineNoContentCache = 0;
   LastFileIDLookup = FileID();
@@ -399,9 +407,10 @@ void SourceManager::clearIDTables() {
   if (LineTable)
     LineTable->clear();
 
-  // Use up FileID #0 as an invalid instantiation.
-  NextOffset = 0;
-  createInstantiationLoc(SourceLocation(),SourceLocation(),SourceLocation(), 1);
+  // Use up FileID #0 as an invalid expansion.
+  NextLocalOffset = 0;
+  CurrentLoadedOffset = MaxLoadedOffset;
+  createExpansionLoc(SourceLocation(),SourceLocation(),SourceLocation(), 1);
 }
 
 /// getOrCreateContentCache - Create or return a cached ContentCache for the
@@ -452,33 +461,16 @@ SourceManager::createMemBufferContentCache(const MemoryBuffer *Buffer) {
   return Entry;
 }
 
-void SourceManager::PreallocateSLocEntries(ExternalSLocEntrySource *Source,
-                                           unsigned NumSLocEntries,
-                                           unsigned NextOffset) {
-  ExternalSLocEntries = Source;
-  this->NextOffset = NextOffset;
-  unsigned CurPrealloc = SLocEntryLoaded.size();
-  // If we've ever preallocated, we must not count the dummy entry.
-  if (CurPrealloc) --CurPrealloc;
-  SLocEntryLoaded.resize(NumSLocEntries + 1);
-  SLocEntryLoaded[0] = true;
-  SLocEntryTable.resize(SLocEntryTable.size() + NumSLocEntries - CurPrealloc);
-}
-
-void SourceManager::ClearPreallocatedSLocEntries() {
-  unsigned I = 0;
-  for (unsigned N = SLocEntryLoaded.size(); I != N; ++I)
-    if (!SLocEntryLoaded[I])
-      break;
-
-  // We've already loaded all preallocated source location entries.
-  if (I == SLocEntryLoaded.size())
-    return;
-
-  // Remove everything from location I onward.
-  SLocEntryTable.resize(I);
-  SLocEntryLoaded.clear();
-  ExternalSLocEntries = 0;
+std::pair<int, unsigned>
+SourceManager::AllocateLoadedSLocEntries(unsigned NumSLocEntries,
+                                         unsigned TotalSize) {
+  assert(ExternalSLocEntries && "Don't have an external sloc source");
+  LoadedSLocEntryTable.resize(LoadedSLocEntryTable.size() + NumSLocEntries);
+  SLocEntryLoaded.resize(LoadedSLocEntryTable.size());
+  CurrentLoadedOffset -= TotalSize;
+  assert(CurrentLoadedOffset >= NextLocalOffset && "Out of source locations");
+  int ID = LoadedSLocEntryTable.size();
+  return std::make_pair(-ID - 1, CurrentLoadedOffset);
 }
 
 /// \brief As part of recovering from missing or changed content, produce a
@@ -492,7 +484,7 @@ const llvm::MemoryBuffer *SourceManager::getFakeBufferForRecovery() const {
 }
 
 //===----------------------------------------------------------------------===//
-// Methods to create new FileID's and instantiations.
+// Methods to create new FileID's and macro expansions.
 //===----------------------------------------------------------------------===//
 
 /// createFileID - Create a new FileID for the specified ContentCache and
@@ -501,77 +493,76 @@ const llvm::MemoryBuffer *SourceManager::getFakeBufferForRecovery() const {
 FileID SourceManager::createFileID(const ContentCache *File,
                                    SourceLocation IncludePos,
                                    SrcMgr::CharacteristicKind FileCharacter,
-                                   unsigned PreallocatedID,
-                                   unsigned Offset) {
-  if (PreallocatedID) {
-    // If we're filling in a preallocated ID, just load in the file
-    // entry and return.
-    assert(PreallocatedID < SLocEntryLoaded.size() &&
-           "Preallocate ID out-of-range");
-    assert(!SLocEntryLoaded[PreallocatedID] &&
-           "Source location entry already loaded");
-    assert(Offset && "Preallocate source location cannot have zero offset");
-    SLocEntryTable[PreallocatedID]
-      = SLocEntry::get(Offset, FileInfo::get(IncludePos, File, FileCharacter));
-    SLocEntryLoaded[PreallocatedID] = true;
-    FileID FID = FileID::get(PreallocatedID);
-    return FID;
+                                   int LoadedID, unsigned LoadedOffset) {
+  if (LoadedID < 0) {
+    assert(LoadedID != -1 && "Loading sentinel FileID");
+    unsigned Index = unsigned(-LoadedID) - 2;
+    assert(Index < LoadedSLocEntryTable.size() && "FileID out of range");
+    assert(!SLocEntryLoaded[Index] && "FileID already loaded");
+    LoadedSLocEntryTable[Index] = SLocEntry::get(LoadedOffset,
+        FileInfo::get(IncludePos, File, FileCharacter));
+    SLocEntryLoaded[Index] = true;
+    return FileID::get(LoadedID);
   }
-
-  SLocEntryTable.push_back(SLocEntry::get(NextOffset,
-                                          FileInfo::get(IncludePos, File,
-                                                        FileCharacter)));
+  LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset,
+                                               FileInfo::get(IncludePos, File,
+                                                             FileCharacter)));
   unsigned FileSize = File->getSize();
-  assert(NextOffset+FileSize+1 > NextOffset && "Ran out of source locations!");
-  NextOffset += FileSize+1;
+  assert(NextLocalOffset + FileSize + 1 > NextLocalOffset &&
+         NextLocalOffset + FileSize + 1 <= CurrentLoadedOffset &&
+         "Ran out of source locations!");
+  // We do a +1 here because we want a SourceLocation that means "the end of the
+  // file", e.g. for the "no newline at the end of the file" diagnostic.
+  NextLocalOffset += FileSize + 1;
 
   // Set LastFileIDLookup to the newly created file.  The next getFileID call is
   // almost guaranteed to be from that file.
-  FileID FID = FileID::get(SLocEntryTable.size()-1);
+  FileID FID = FileID::get(LocalSLocEntryTable.size()-1);
   return LastFileIDLookup = FID;
 }
 
 SourceLocation
-SourceManager::createMacroArgInstantiationLoc(SourceLocation SpellingLoc,
-                                              SourceLocation ILoc,
-                                              unsigned TokLength) {
-  InstantiationInfo II =
-    InstantiationInfo::createForMacroArg(SpellingLoc, ILoc);
-  return createInstantiationLocImpl(II, TokLength);
-}
-
-SourceLocation SourceManager::createInstantiationLoc(SourceLocation SpellingLoc,
-                                                     SourceLocation ILocStart,
-                                                     SourceLocation ILocEnd,
-                                                     unsigned TokLength,
-                                                     unsigned PreallocatedID,
-                                                     unsigned Offset) {
-  InstantiationInfo II =
-    InstantiationInfo::create(SpellingLoc, ILocStart, ILocEnd);
-  return createInstantiationLocImpl(II, TokLength, PreallocatedID, Offset);
+SourceManager::createMacroArgExpansionLoc(SourceLocation SpellingLoc,
+                                          SourceLocation ExpansionLoc,
+                                          unsigned TokLength) {
+  ExpansionInfo Info = ExpansionInfo::createForMacroArg(SpellingLoc,
+                                                        ExpansionLoc);
+  return createExpansionLocImpl(Info, TokLength);
 }
 
 SourceLocation
-SourceManager::createInstantiationLocImpl(const InstantiationInfo &II,
-                                          unsigned TokLength,
-                                          unsigned PreallocatedID,
-                                          unsigned Offset) {
-  if (PreallocatedID) {
-    // If we're filling in a preallocated ID, just load in the
-    // instantiation entry and return.
-    assert(PreallocatedID < SLocEntryLoaded.size() &&
-           "Preallocate ID out-of-range");
-    assert(!SLocEntryLoaded[PreallocatedID] &&
-           "Source location entry already loaded");
-    assert(Offset && "Preallocate source location cannot have zero offset");
-    SLocEntryTable[PreallocatedID] = SLocEntry::get(Offset, II);
-    SLocEntryLoaded[PreallocatedID] = true;
-    return SourceLocation::getMacroLoc(Offset);
+SourceManager::createExpansionLoc(SourceLocation SpellingLoc,
+                                  SourceLocation ExpansionLocStart,
+                                  SourceLocation ExpansionLocEnd,
+                                  unsigned TokLength,
+                                  int LoadedID,
+                                  unsigned LoadedOffset) {
+  ExpansionInfo Info = ExpansionInfo::create(SpellingLoc, ExpansionLocStart,
+                                             ExpansionLocEnd);
+  return createExpansionLocImpl(Info, TokLength, LoadedID, LoadedOffset);
+}
+
+SourceLocation
+SourceManager::createExpansionLocImpl(const ExpansionInfo &Info,
+                                      unsigned TokLength,
+                                      int LoadedID,
+                                      unsigned LoadedOffset) {
+  if (LoadedID < 0) {
+    assert(LoadedID != -1 && "Loading sentinel FileID");
+    unsigned Index = unsigned(-LoadedID) - 2;
+    assert(Index < LoadedSLocEntryTable.size() && "FileID out of range");
+    assert(!SLocEntryLoaded[Index] && "FileID already loaded");
+    LoadedSLocEntryTable[Index] = SLocEntry::get(LoadedOffset, Info);
+    SLocEntryLoaded[Index] = true;
+    return SourceLocation::getMacroLoc(LoadedOffset);
   }
-  SLocEntryTable.push_back(SLocEntry::get(NextOffset, II));
-  assert(NextOffset+TokLength+1 > NextOffset && "Ran out of source locations!");
-  NextOffset += TokLength+1;
-  return SourceLocation::getMacroLoc(NextOffset-(TokLength+1));
+  LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset, Info));
+  assert(NextLocalOffset + TokLength + 1 > NextLocalOffset &&
+         NextLocalOffset + TokLength + 1 <= CurrentLoadedOffset &&
+         "Ran out of source locations!");
+  // See createFileID for that +1.
+  NextLocalOffset += TokLength + 1;
+  return SourceLocation::getMacroLoc(NextLocalOffset - (TokLength + 1));
 }
 
 const llvm::MemoryBuffer *
@@ -602,9 +593,9 @@ void SourceManager::overrideFileContents(const FileEntry *SourceFile,
   OverriddenFiles[SourceFile] = NewFile;
 }
 
-llvm::StringRef SourceManager::getBufferData(FileID FID, bool *Invalid) const {
+StringRef SourceManager::getBufferData(FileID FID, bool *Invalid) const {
   bool MyInvalid = false;
-  const SLocEntry &SLoc = getSLocEntry(FID.ID, &MyInvalid);
+  const SLocEntry &SLoc = getSLocEntry(FID, &MyInvalid);
   if (!SLoc.isFile() || MyInvalid) {
     if (Invalid) 
       *Invalid = true;
@@ -627,18 +618,32 @@ llvm::StringRef SourceManager::getBufferData(FileID FID, bool *Invalid) const {
 // SourceLocation manipulation methods.
 //===----------------------------------------------------------------------===//
 
-/// getFileIDSlow - Return the FileID for a SourceLocation.  This is a very hot
-/// method that is used for all SourceManager queries that start with a
-/// SourceLocation object.  It is responsible for finding the entry in
-/// SLocEntryTable which contains the specified location.
+/// \brief Return the FileID for a SourceLocation.
 ///
+/// This is the cache-miss path of getFileID. Not as hot as that function, but
+/// still very important. It is responsible for finding the entry in the
+/// SLocEntry tables that contains the specified location.
 FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
   if (!SLocOffset)
     return FileID::get(0);
 
+  // Now it is time to search for the correct file. See where the SLocOffset
+  // sits in the global view and consult local or loaded buffers for it.
+  if (SLocOffset < NextLocalOffset)
+    return getFileIDLocal(SLocOffset);
+  return getFileIDLoaded(SLocOffset);
+}
+
+/// \brief Return the FileID for a SourceLocation with a low offset.
+///
+/// This function knows that the SourceLocation is in a local buffer, not a
+/// loaded one.
+FileID SourceManager::getFileIDLocal(unsigned SLocOffset) const {
+  assert(SLocOffset < NextLocalOffset && "Bad function choice");
+
   // After the first and second level caches, I see two common sorts of
-  // behavior: 1) a lot of searched FileID's are "near" the cached file location
-  // or are "near" the cached instantiation location.  2) others are just
+  // behavior: 1) a lot of searched FileID's are "near" the cached file
+  // location or are "near" the cached expansion location. 2) others are just
   // completely random and may be a very long way away.
   //
   // To handle this, we do a linear search for up to 8 steps to catch #1 quickly
@@ -649,12 +654,13 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
   // most newly created FileID.
   std::vector<SrcMgr::SLocEntry>::const_iterator I;
 
-  if (SLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) {
+  if (LastFileIDLookup.ID < 0 ||
+      LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) {
     // Neither loc prunes our search.
-    I = SLocEntryTable.end();
+    I = LocalSLocEntryTable.end();
   } else {
     // Perhaps it is near the file point.
-    I = SLocEntryTable.begin()+LastFileIDLookup.ID;
+    I = LocalSLocEntryTable.begin()+LastFileIDLookup.ID;
   }
 
   // Find the FileID that contains this.  "I" is an iterator that points to a
@@ -662,25 +668,12 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
   unsigned NumProbes = 0;
   while (1) {
     --I;
-    if (ExternalSLocEntries) {
-      bool Invalid = false;
-      getSLocEntry(FileID::get(I - SLocEntryTable.begin()), &Invalid);
-      if (Invalid)
-        return FileID::get(0);
-    }
-    
     if (I->getOffset() <= SLocOffset) {
-#if 0
-      printf("lin %d -> %d [%s] %d %d\n", SLocOffset,
-             I-SLocEntryTable.begin(),
-             I->isInstantiation() ? "inst" : "file",
-             LastFileIDLookup.ID,  int(SLocEntryTable.end()-I));
-#endif
-      FileID Res = FileID::get(I-SLocEntryTable.begin());
-
-      // If this isn't an instantiation, remember it.  We have good locality
-      // across FileID lookups.
-      if (!I->isInstantiation())
+      FileID Res = FileID::get(int(I - LocalSLocEntryTable.begin()));
+
+      // If this isn't an expansion, remember it.  We have good locality across
+      // FileID lookups.
+      if (!I->isExpansion())
         LastFileIDLookup = Res;
       NumLinearScans += NumProbes+1;
       return Res;
@@ -691,7 +684,7 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
 
   // Convert "I" back into an index.  We know that it is an entry whose index is
   // larger than the offset we are looking for.
-  unsigned GreaterIndex = I-SLocEntryTable.begin();
+  unsigned GreaterIndex = I - LocalSLocEntryTable.begin();
   // LessIndex - This is the lower bound of the range that we're searching.
   // We know that the offset corresponding to the FileID is is less than
   // SLocOffset.
@@ -700,8 +693,7 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
   while (1) {
     bool Invalid = false;
     unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex;
-    unsigned MidOffset = getSLocEntry(FileID::get(MiddleIndex), &Invalid)
-                                                                  .getOffset();
+    unsigned MidOffset = getLocalSLocEntry(MiddleIndex, &Invalid).getOffset();
     if (Invalid)
       return FileID::get(0);
     
@@ -715,18 +707,14 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
     }
 
     // If the middle index contains the value, succeed and return.
+    // FIXME: This could be made faster by using a function that's aware of
+    // being in the local area.
     if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) {
-#if 0
-      printf("bin %d -> %d [%s] %d %d\n", SLocOffset,
-             I-SLocEntryTable.begin(),
-             I->isInstantiation() ? "inst" : "file",
-             LastFileIDLookup.ID, int(SLocEntryTable.end()-I));
-#endif
       FileID Res = FileID::get(MiddleIndex);
 
-      // If this isn't an instantiation, remember it.  We have good locality
+      // If this isn't a macro expansion, remember it.  We have good locality
       // across FileID lookups.
-      if (!I->isInstantiation())
+      if (!LocalSLocEntryTable[MiddleIndex].isExpansion())
         LastFileIDLookup = Res;
       NumBinaryProbes += NumProbes;
       return Res;
@@ -737,17 +725,82 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
   }
 }
 
+/// \brief Return the FileID for a SourceLocation with a high offset.
+///
+/// This function knows that the SourceLocation is in a loaded buffer, not a
+/// local one.
+FileID SourceManager::getFileIDLoaded(unsigned SLocOffset) const {
+  assert(SLocOffset >= CurrentLoadedOffset && "Bad function choice");
+
+  // Sanity checking, otherwise a bug may lead to hanging in release build.
+  if (SLocOffset < CurrentLoadedOffset)
+    return FileID();
+
+  // Essentially the same as the local case, but the loaded array is sorted
+  // in the other direction.
+
+  // First do a linear scan from the last lookup position, if possible.
+  unsigned I;
+  int LastID = LastFileIDLookup.ID;
+  if (LastID >= 0 || getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset)
+    I = 0;
+  else
+    I = (-LastID - 2) + 1;
+
+  unsigned NumProbes;
+  for (NumProbes = 0; NumProbes < 8; ++NumProbes, ++I) {
+    // Make sure the entry is loaded!
+    const SrcMgr::SLocEntry &E = getLoadedSLocEntry(I);
+    if (E.getOffset() <= SLocOffset) {
+      FileID Res = FileID::get(-int(I) - 2);
+
+      if (!E.isExpansion())
+        LastFileIDLookup = Res;
+      NumLinearScans += NumProbes + 1;
+      return Res;
+    }
+  }
+
+  // Linear scan failed. Do the binary search. Note the reverse sorting of the
+  // table: GreaterIndex is the one where the offset is greater, which is
+  // actually a lower index!
+  unsigned GreaterIndex = I;
+  unsigned LessIndex = LoadedSLocEntryTable.size();
+  NumProbes = 0;
+  while (1) {
+    ++NumProbes;
+    unsigned MiddleIndex = (LessIndex - GreaterIndex) / 2 + GreaterIndex;
+    const SrcMgr::SLocEntry &E = getLoadedSLocEntry(MiddleIndex);
+
+    ++NumProbes;
+
+    if (E.getOffset() > SLocOffset) {
+      GreaterIndex = MiddleIndex;
+      continue;
+    }
+
+    if (isOffsetInFileID(FileID::get(-int(MiddleIndex) - 2), SLocOffset)) {
+      FileID Res = FileID::get(-int(MiddleIndex) - 2);
+      if (!E.isExpansion())
+        LastFileIDLookup = Res;
+      NumBinaryProbes += NumProbes;
+      return Res;
+    }
+
+    LessIndex = MiddleIndex;
+  }
+}
+
 SourceLocation SourceManager::
-getInstantiationLocSlowCase(SourceLocation Loc) const {
+getExpansionLocSlowCase(SourceLocation Loc) const {
   do {
     // Note: If Loc indicates an offset into a token that came from a macro
     // expansion (e.g. the 5th character of the token) we do not want to add
-    // this offset when going to the instantiation location.  The instatiation
+    // this offset when going to the expansion location.  The expansion
     // location is the macro invocation, which the offset has nothing to do
     // with.  This is unlike when we get the spelling loc, because the offset
     // directly correspond to the token whose spelling we're inspecting.
-    Loc = getSLocEntry(getFileID(Loc)).getInstantiation()
-                   .getInstantiationLocStart();
+    Loc = getSLocEntry(getFileID(Loc)).getExpansion().getExpansionLocStart();
   } while (!Loc.isFileID());
 
   return Loc;
@@ -756,23 +809,32 @@ getInstantiationLocSlowCase(SourceLocation Loc) const {
 SourceLocation SourceManager::getSpellingLocSlowCase(SourceLocation Loc) const {
   do {
     std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
-    Loc = getSLocEntry(LocInfo.first).getInstantiation().getSpellingLoc();
-    Loc = Loc.getFileLocWithOffset(LocInfo.second);
+    Loc = getSLocEntry(LocInfo.first).getExpansion().getSpellingLoc();
+    Loc = Loc.getLocWithOffset(LocInfo.second);
+  } while (!Loc.isFileID());
+  return Loc;
+}
+
+SourceLocation SourceManager::getFileLocSlowCase(SourceLocation Loc) const {
+  do {
+    if (isMacroArgExpansion(Loc))
+      Loc = getImmediateSpellingLoc(Loc);
+    else
+      Loc = getImmediateExpansionRange(Loc).first;
   } while (!Loc.isFileID());
   return Loc;
 }
 
 
 std::pair<FileID, unsigned>
-SourceManager::getDecomposedInstantiationLocSlowCase(
+SourceManager::getDecomposedExpansionLocSlowCase(
                                              const SrcMgr::SLocEntry *E) const {
-  // If this is an instantiation record, walk through all the instantiation
-  // points.
+  // If this is an expansion record, walk through all the expansion points.
   FileID FID;
   SourceLocation Loc;
   unsigned Offset;
   do {
-    Loc = E->getInstantiation().getInstantiationLocStart();
+    Loc = E->getExpansion().getExpansionLocStart();
 
     FID = getFileID(Loc);
     E = &getSLocEntry(FID);
@@ -785,16 +847,16 @@ SourceManager::getDecomposedInstantiationLocSlowCase(
 std::pair<FileID, unsigned>
 SourceManager::getDecomposedSpellingLocSlowCase(const SrcMgr::SLocEntry *E,
                                                 unsigned Offset) const {
-  // If this is an instantiation record, walk through all the instantiation
-  // points.
+  // If this is an expansion record, walk through all the expansion points.
   FileID FID;
   SourceLocation Loc;
   do {
-    Loc = E->getInstantiation().getSpellingLoc();
+    Loc = E->getExpansion().getSpellingLoc();
+    Loc = Loc.getLocWithOffset(Offset);
 
     FID = getFileID(Loc);
     E = &getSLocEntry(FID);
-    Offset += Loc.getOffset()-E->getOffset();
+    Offset = Loc.getOffset()-E->getOffset();
   } while (!Loc.isFileID());
 
   return std::make_pair(FID, Offset);
@@ -807,45 +869,45 @@ SourceManager::getDecomposedSpellingLocSlowCase(const SrcMgr::SLocEntry *E,
 SourceLocation SourceManager::getImmediateSpellingLoc(SourceLocation Loc) const{
   if (Loc.isFileID()) return Loc;
   std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
-  Loc = getSLocEntry(LocInfo.first).getInstantiation().getSpellingLoc();
-  return Loc.getFileLocWithOffset(LocInfo.second);
+  Loc = getSLocEntry(LocInfo.first).getExpansion().getSpellingLoc();
+  return Loc.getLocWithOffset(LocInfo.second);
 }
 
 
-/// getImmediateInstantiationRange - Loc is required to be an instantiation
-/// location.  Return the start/end of the instantiation information.
+/// getImmediateExpansionRange - Loc is required to be an expansion location.
+/// Return the start/end of the expansion information.
 std::pair<SourceLocation,SourceLocation>
-SourceManager::getImmediateInstantiationRange(SourceLocation Loc) const {
-  assert(Loc.isMacroID() && "Not an instantiation loc!");
-  const InstantiationInfo &II = getSLocEntry(getFileID(Loc)).getInstantiation();
-  return II.getInstantiationLocRange();
+SourceManager::getImmediateExpansionRange(SourceLocation Loc) const {
+  assert(Loc.isMacroID() && "Not a macro expansion loc!");
+  const ExpansionInfo &Expansion = getSLocEntry(getFileID(Loc)).getExpansion();
+  return Expansion.getExpansionLocRange();
 }
 
-/// getInstantiationRange - Given a SourceLocation object, return the
-/// range of tokens covered by the instantiation in the ultimate file.
+/// getExpansionRange - Given a SourceLocation object, return the range of
+/// tokens covered by the expansion in the ultimate file.
 std::pair<SourceLocation,SourceLocation>
-SourceManager::getInstantiationRange(SourceLocation Loc) const {
+SourceManager::getExpansionRange(SourceLocation Loc) const {
   if (Loc.isFileID()) return std::make_pair(Loc, Loc);
 
   std::pair<SourceLocation,SourceLocation> Res =
-    getImmediateInstantiationRange(Loc);
+    getImmediateExpansionRange(Loc);
 
-  // Fully resolve the start and end locations to their ultimate instantiation
+  // Fully resolve the start and end locations to their ultimate expansion
   // points.
   while (!Res.first.isFileID())
-    Res.first = getImmediateInstantiationRange(Res.first).first;
+    Res.first = getImmediateExpansionRange(Res.first).first;
   while (!Res.second.isFileID())
-    Res.second = getImmediateInstantiationRange(Res.second).second;
+    Res.second = getImmediateExpansionRange(Res.second).second;
   return Res;
 }
 
-bool SourceManager::isMacroArgInstantiation(SourceLocation Loc) const {
+bool SourceManager::isMacroArgExpansion(SourceLocation Loc) const {
   if (!Loc.isMacroID()) return false;
 
   FileID FID = getFileID(Loc);
   const SrcMgr::SLocEntry *E = &getSLocEntry(FID);
-  const SrcMgr::InstantiationInfo &II = E->getInstantiation();
-  return II.isMacroArgInstantiation();
+  const SrcMgr::ExpansionInfo &Expansion = E->getExpansion();
+  return Expansion.isMacroArgExpansion();
 }
 
 
@@ -913,10 +975,10 @@ unsigned SourceManager::getSpellingColumnNumber(SourceLocation Loc,
   return getColumnNumber(LocInfo.first, LocInfo.second, Invalid);
 }
 
-unsigned SourceManager::getInstantiationColumnNumber(SourceLocation Loc,
-                                                     bool *Invalid) const {
+unsigned SourceManager::getExpansionColumnNumber(SourceLocation Loc,
+                                                 bool *Invalid) const {
   if (isInvalid(Loc, Invalid)) return 0;
-  std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc);
+  std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
   return getColumnNumber(LocInfo.first, LocInfo.second, Invalid);
 }
 
@@ -927,10 +989,10 @@ unsigned SourceManager::getPresumedColumnNumber(SourceLocation Loc,
 }
 
 static LLVM_ATTRIBUTE_NOINLINE void
-ComputeLineNumbers(Diagnostic &Diag, ContentCache *FI,
+ComputeLineNumbers(DiagnosticsEngine &Diag, ContentCache *FI,
                    llvm::BumpPtrAllocator &Alloc,
                    const SourceManager &SM, bool &Invalid);
-static void ComputeLineNumbers(Diagnostic &Diag, ContentCache *FI, 
+static void ComputeLineNumbers(DiagnosticsEngine &Diag, ContentCache *FI,
                                llvm::BumpPtrAllocator &Alloc,
                                const SourceManager &SM, bool &Invalid) {
   // Note that calling 'getBuffer()' may lazily page in the file.
@@ -941,7 +1003,7 @@ static void ComputeLineNumbers(Diagnostic &Diag, ContentCache *FI,
 
   // Find the file offsets of all of the *physical* source lines.  This does
   // not look at trigraphs, escaped newlines, or anything else tricky.
-  llvm::SmallVector<unsigned, 256> LineOffsets;
+  SmallVector<unsigned, 256> LineOffsets;
 
   // Line #1 starts at char 0.
   LineOffsets.push_back(0);
@@ -1108,10 +1170,10 @@ unsigned SourceManager::getSpellingLineNumber(SourceLocation Loc,
   std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(Loc);
   return getLineNumber(LocInfo.first, LocInfo.second);
 }
-unsigned SourceManager::getInstantiationLineNumber(SourceLocation Loc, 
-                                                   bool *Invalid) const {
+unsigned SourceManager::getExpansionLineNumber(SourceLocation Loc,
+                                               bool *Invalid) const {
   if (isInvalid(Loc, Invalid)) return 0;
-  std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc);
+  std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
   return getLineNumber(LocInfo.first, LocInfo.second);
 }
 unsigned SourceManager::getPresumedLineNumber(SourceLocation Loc,
@@ -1131,7 +1193,7 @@ unsigned SourceManager::getPresumedLineNumber(SourceLocation Loc,
 SrcMgr::CharacteristicKind
 SourceManager::getFileCharacteristic(SourceLocation Loc) const {
   assert(!Loc.isInvalid() && "Can't get file characteristic of invalid loc!");
-  std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc);
+  std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
   bool Invalid = false;
   const SLocEntry &SEntry = getSLocEntry(LocInfo.first, &Invalid);
   if (Invalid || !SEntry.isFile())
@@ -1172,13 +1234,13 @@ const char *SourceManager::getBufferName(SourceLocation Loc,
 /// or GNU line marker directives.  This provides a view on the data that a
 /// user should see in diagnostics, for example.
 ///
-/// Note that a presumed location is always given as the instantiation point
-/// of an instantiation location, not at the spelling location.
+/// Note that a presumed location is always given as the expansion point of an
+/// expansion location, not at the spelling location.
 PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc) const {
   if (Loc.isInvalid()) return PresumedLoc();
 
-  // Presumed locations are always for instantiation points.
-  std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc);
+  // Presumed locations are always for expansion points.
+  std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
 
   bool Invalid = false;
   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid);
@@ -1229,7 +1291,7 @@ PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc) const {
       // Handle virtual #include manipulation.
       if (Entry->IncludeOffset) {
         IncludeLoc = getLocForStartOfFile(LocInfo.first);
-        IncludeLoc = IncludeLoc.getFileLocWithOffset(Entry->IncludeOffset);
+        IncludeLoc = IncludeLoc.getLocWithOffset(Entry->IncludeOffset);
       }
     }
   }
@@ -1237,6 +1299,25 @@ PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc) const {
   return PresumedLoc(Filename, LineNo, ColNo, IncludeLoc);
 }
 
+/// \brief The size of the SLocEnty that \arg FID represents.
+unsigned SourceManager::getFileIDSize(FileID FID) const {
+  bool Invalid = false;
+  const SrcMgr::SLocEntry &Entry = getSLocEntry(FID, &Invalid);
+  if (Invalid)
+    return 0;
+
+  int ID = FID.ID;
+  unsigned NextOffset;
+  if ((ID > 0 && unsigned(ID+1) == local_sloc_entry_size()))
+    NextOffset = getNextLocalOffset();
+  else if (ID+1 == -1)
+    NextOffset = MaxLoadedOffset;
+  else
+    NextOffset = getSLocEntry(FileID::get(ID+1)).getOffset();
+
+  return NextOffset - Entry.getOffset() - 1;
+}
+
 //===----------------------------------------------------------------------===//
 // Other miscellaneous methods.
 //===----------------------------------------------------------------------===//
@@ -1259,24 +1340,36 @@ static llvm::Optional<ino_t> getActualFileInode(const FileEntry *File) {
 /// \brief Get the source location for the given file:line:col triplet.
 ///
 /// If the source file is included multiple times, the source location will
-/// be based upon the first inclusion.
-SourceLocation SourceManager::getLocation(const FileEntry *SourceFile,
-                                          unsigned Line, unsigned Col) {
+/// be based upon an arbitrary inclusion.
+SourceLocation SourceManager::translateFileLineCol(const FileEntry *SourceFile,
+                                                  unsigned Line,
+                                                  unsigned Col) const {
   assert(SourceFile && "Null source file!");
   assert(Line && Col && "Line and column should start from 1!");
 
+  FileID FirstFID = translateFile(SourceFile);
+  return translateLineCol(FirstFID, Line, Col);
+}
+
+/// \brief Get the FileID for the given file.
+///
+/// If the source file is included multiple times, the FileID will be the
+/// first inclusion.
+FileID SourceManager::translateFile(const FileEntry *SourceFile) const {
+  assert(SourceFile && "Null source file!");
+
   // Find the first file ID that corresponds to the given file.
   FileID FirstFID;
 
   // First, check the main file ID, since it is common to look for a
   // location in the main file.
   llvm::Optional<ino_t> SourceFileInode;
-  llvm::Optional<llvm::StringRef> SourceFileName;
+  llvm::Optional<StringRef> SourceFileName;
   if (!MainFileID.isInvalid()) {
     bool Invalid = false;
     const SLocEntry &MainSLoc = getSLocEntry(MainFileID, &Invalid);
     if (Invalid)
-      return SourceLocation();
+      return FileID();
     
     if (MainSLoc.isFile()) {
       const ContentCache *MainContentCache
@@ -1308,12 +1401,12 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile,
 
   if (FirstFID.isInvalid()) {
     // The location we're looking for isn't in the main file; look
-    // through all of the source locations.
-    for (unsigned I = 0, N = sloc_entry_size(); I != N; ++I) {
+    // through all of the local source locations.
+    for (unsigned I = 0, N = local_sloc_entry_size(); I != N; ++I) {
       bool Invalid = false;
-      const SLocEntry &SLoc = getSLocEntry(I, &Invalid);
+      const SLocEntry &SLoc = getLocalSLocEntry(I, &Invalid);
       if (Invalid)
-        return SourceLocation();
+        return FileID();
       
       if (SLoc.isFile() && 
           SLoc.getFile().getContentCache() &&
@@ -1322,6 +1415,18 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile,
         break;
       }
     }
+    // If that still didn't help, try the modules.
+    if (FirstFID.isInvalid()) {
+      for (unsigned I = 0, N = loaded_sloc_entry_size(); I != N; ++I) {
+        const SLocEntry &SLoc = getLoadedSLocEntry(I);
+        if (SLoc.isFile() && 
+            SLoc.getFile().getContentCache() &&
+            SLoc.getFile().getContentCache()->OrigEntry == SourceFile) {
+          FirstFID = FileID::get(-int(I) - 2);
+          break;
+        }
+      }
+    }
   }
 
   // If we haven't found what we want yet, try again, but this time stat()
@@ -1333,10 +1438,12 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile,
       (SourceFileInode ||
        (SourceFileInode = getActualFileInode(SourceFile)))) {
     bool Invalid = false;
-    for (unsigned I = 0, N = sloc_entry_size(); I != N; ++I) {
-      const SLocEntry &SLoc = getSLocEntry(I, &Invalid);
+    for (unsigned I = 0, N = local_sloc_entry_size(); I != N; ++I) {
+      FileID IFileID;
+      IFileID.ID = I;
+      const SLocEntry &SLoc = getSLocEntry(IFileID, &Invalid);
       if (Invalid)
-        return SourceLocation();
+        return FileID();
       
       if (SLoc.isFile()) { 
         const ContentCache *FileContentCache 
@@ -1355,20 +1462,38 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile,
       }
     }      
   }
-    
-  if (FirstFID.isInvalid())
+  
+  return FirstFID;
+}
+
+/// \brief Get the source location in \arg FID for the given line:col.
+/// Returns null location if \arg FID is not a file SLocEntry.
+SourceLocation SourceManager::translateLineCol(FileID FID,
+                                               unsigned Line,
+                                               unsigned Col) const {
+  if (FID.isInvalid())
+    return SourceLocation();
+
+  bool Invalid = false;
+  const SLocEntry &Entry = getSLocEntry(FID, &Invalid);
+  if (Invalid)
+    return SourceLocation();
+  
+  if (!Entry.isFile())
     return SourceLocation();
 
+  SourceLocation FileLoc = SourceLocation::getFileLoc(Entry.getOffset());
+
   if (Line == 1 && Col == 1)
-    return getLocForStartOfFile(FirstFID);
+    return FileLoc;
 
   ContentCache *Content
-    = const_cast<ContentCache *>(getOrCreateContentCache(SourceFile));
+    = const_cast<ContentCache *>(Entry.getFile().getContentCache());
   if (!Content)
     return SourceLocation();
     
   // If this is the first use of line information for this buffer, compute the
-  /// SourceLineCache for it on demand.
+  // SourceLineCache for it on demand.
   if (Content->SourceLineCache == 0) {
     bool MyInvalid = false;
     ComputeLineNumbers(Diag, Content, ContentCacheAlloc, *this, MyInvalid);
@@ -1380,33 +1505,150 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile,
     unsigned Size = Content->getBuffer(Diag, *this)->getBufferSize();
     if (Size > 0)
       --Size;
-    return getLocForStartOfFile(FirstFID).getFileLocWithOffset(Size);
+    return FileLoc.getLocWithOffset(Size);
   }
 
   unsigned FilePos = Content->SourceLineCache[Line - 1];
   const char *Buf = Content->getBuffer(Diag, *this)->getBufferStart() + FilePos;
   unsigned BufLength = Content->getBuffer(Diag, *this)->getBufferEnd() - Buf;
+  if (BufLength == 0)
+    return FileLoc.getLocWithOffset(FilePos);
+
   unsigned i = 0;
 
   // Check that the given column is valid.
   while (i < BufLength-1 && i < Col-1 && Buf[i] != '\n' && Buf[i] != '\r')
     ++i;
   if (i < Col-1)
-    return getLocForStartOfFile(FirstFID).getFileLocWithOffset(FilePos + i);
+    return FileLoc.getLocWithOffset(FilePos + i);
 
-  return getLocForStartOfFile(FirstFID).getFileLocWithOffset(FilePos + Col - 1);
+  return FileLoc.getLocWithOffset(FilePos + Col - 1);
 }
 
-/// Given a decomposed source location, move it up the include/instantiation
-/// stack to the parent source location.  If this is possible, return the
-/// decomposed version of the parent in Loc and return false.  If Loc is the
-/// top-level entry, return true and don't modify it.
+/// \brief Compute a map of macro argument chunks to their expanded source
+/// location. Chunks that are not part of a macro argument will map to an
+/// invalid source location. e.g. if a file contains one macro argument at
+/// offset 100 with length 10, this is how the map will be formed:
+///     0   -> SourceLocation()
+///     100 -> Expanded macro arg location
+///     110 -> SourceLocation()
+void SourceManager::computeMacroArgsCache(MacroArgsMap *&CachePtr,
+                                          FileID FID) const {
+  assert(!FID.isInvalid());
+  assert(!CachePtr);
+
+  CachePtr = new MacroArgsMap();
+  MacroArgsMap &MacroArgsCache = *CachePtr;
+  // Initially no macro argument chunk is present.
+  MacroArgsCache.insert(std::make_pair(0, SourceLocation()));
+
+  int ID = FID.ID;
+  while (1) {
+    ++ID;
+    // Stop if there are no more FileIDs to check.
+    if (ID > 0) {
+      if (unsigned(ID) >= local_sloc_entry_size())
+        return;
+    } else if (ID == -1) {
+      return;
+    }
+
+    const SrcMgr::SLocEntry &Entry = getSLocEntryByID(ID);
+    if (Entry.isFile()) {
+      SourceLocation IncludeLoc = Entry.getFile().getIncludeLoc();
+      if (IncludeLoc.isInvalid())
+        continue;
+      if (!isInFileID(IncludeLoc, FID))
+        return; // No more files/macros that may be "contained" in this file.
+
+      // Skip the files/macros of the #include'd file, we only care about macros
+      // that lexed macro arguments from our file.
+      if (Entry.getFile().NumCreatedFIDs)
+        ID += Entry.getFile().NumCreatedFIDs - 1/*because of next ++ID*/;
+      continue;
+    }
+
+    if (!Entry.getExpansion().isMacroArgExpansion())
+      continue;
+ 
+    SourceLocation SpellLoc =
+        getSpellingLoc(Entry.getExpansion().getSpellingLoc());
+    unsigned BeginOffs;
+    if (!isInFileID(SpellLoc, FID, &BeginOffs))
+      return; // No more files/macros that may be "contained" in this file.
+    unsigned EndOffs = BeginOffs + getFileIDSize(FileID::get(ID));
+
+    // Add a new chunk for this macro argument. A previous macro argument chunk
+    // may have been lexed again, so e.g. if the map is
+    //     0   -> SourceLocation()
+    //     100 -> Expanded loc #1
+    //     110 -> SourceLocation()
+    // and we found a new macro FileID that lexed from offet 105 with length 3,
+    // the new map will be:
+    //     0   -> SourceLocation()
+    //     100 -> Expanded loc #1
+    //     105 -> Expanded loc #2
+    //     108 -> Expanded loc #1
+    //     110 -> SourceLocation()
+    //
+    // Since re-lexed macro chunks will always be the same size or less of
+    // previous chunks, we only need to find where the ending of the new macro
+    // chunk is mapped to and update the map with new begin/end mappings.
+
+    MacroArgsMap::iterator I = MacroArgsCache.upper_bound(EndOffs);
+    --I;
+    SourceLocation EndOffsMappedLoc = I->second;
+    MacroArgsCache[BeginOffs] = SourceLocation::getMacroLoc(Entry.getOffset());
+    MacroArgsCache[EndOffs] = EndOffsMappedLoc;
+  }
+}
+
+/// \brief If \arg Loc points inside a function macro argument, the returned
+/// location will be the macro location in which the argument was expanded.
+/// If a macro argument is used multiple times, the expanded location will
+/// be at the first expansion of the argument.
+/// e.g.
+///   MY_MACRO(foo);
+///             ^
+/// Passing a file location pointing at 'foo', will yield a macro location
+/// where 'foo' was expanded into.
+SourceLocation
+SourceManager::getMacroArgExpandedLocation(SourceLocation Loc) const {
+  if (Loc.isInvalid() || !Loc.isFileID())
+    return Loc;
+
+  FileID FID;
+  unsigned Offset;
+  llvm::tie(FID, Offset) = getDecomposedLoc(Loc);
+  if (FID.isInvalid())
+    return Loc;
+
+  MacroArgsMap *&MacroArgsCache = MacroArgsCacheMap[FID];
+  if (!MacroArgsCache)
+    computeMacroArgsCache(MacroArgsCache, FID);
+
+  assert(!MacroArgsCache->empty());
+  MacroArgsMap::iterator I = MacroArgsCache->upper_bound(Offset);
+  --I;
+  
+  unsigned MacroArgBeginOffs = I->first;
+  SourceLocation MacroArgExpandedLoc = I->second;
+  if (MacroArgExpandedLoc.isValid())
+    return MacroArgExpandedLoc.getLocWithOffset(Offset - MacroArgBeginOffs);
+
+  return Loc;
+}
+
+/// Given a decomposed source location, move it up the include/expansion stack
+/// to the parent source location.  If this is possible, return the decomposed
+/// version of the parent in Loc and return false.  If Loc is the top-level
+/// entry, return true and don't modify it.
 static bool MoveUpIncludeHierarchy(std::pair<FileID, unsigned> &Loc,
                                    const SourceManager &SM) {
   SourceLocation UpperLoc;
   const SrcMgr::SLocEntry &Entry = SM.getSLocEntry(Loc.first);
-  if (Entry.isInstantiation())
-    UpperLoc = Entry.getInstantiation().getInstantiationLocStart();
+  if (Entry.isExpansion())
+    UpperLoc = Entry.getExpansion().getExpansionLocEnd();
   else
     UpperLoc = Entry.getFile().getIncludeLoc();
   
@@ -1427,11 +1669,6 @@ bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS,
   if (LHS == RHS)
     return false;
 
-  // If both locations are macro instantiations, the order of their offsets
-  // reflect the order that the tokens, pointed to by these locations, were
-  // instantiated (during parsing each token that is instantiated by a macro,
-  // expands the SLocEntries).
-
   std::pair<FileID, unsigned> LOffs = getDecomposedLoc(LHS);
   std::pair<FileID, unsigned> ROffs = getDecomposedLoc(RHS);
 
@@ -1445,41 +1682,28 @@ bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS,
     return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second);
 
   // Okay, we missed in the cache, start updating the cache for this query.
-  IsBeforeInTUCache.setQueryFIDs(LOffs.first, ROffs.first);
-
-  // "Traverse" the include/instantiation stacks of both locations and try to
-  // find a common "ancestor".  FileIDs build a tree-like structure that
-  // reflects the #include hierarchy, and this algorithm needs to find the
-  // nearest common ancestor between the two locations.  For example, if you
-  // have a.c that includes b.h and c.h, and are comparing a location in b.h to
-  // a location in c.h, we need to find that their nearest common ancestor is
-  // a.c, and compare the locations of the two #includes to find their relative
-  // ordering.
-  //
-  // SourceManager assigns FileIDs in order of parsing.  This means that an
-  // includee always has a larger FileID than an includer.  While you might
-  // think that we could just compare the FileID's here, that doesn't work to
-  // compare a point at the end of a.c with a point within c.h.  Though c.h has
-  // a larger FileID, we have to compare the include point of c.h to the
-  // location in a.c.
-  //
-  // Despite not being able to directly compare FileID's, we can tell that a
-  // larger FileID is necessarily more deeply nested than a lower one and use
-  // this information to walk up the tree to the nearest common ancestor.
+  IsBeforeInTUCache.setQueryFIDs(LOffs.first, ROffs.first,
+                          /*isLFIDBeforeRFID=*/LOffs.first.ID < ROffs.first.ID);
+
+  // We need to find the common ancestor. The only way of doing this is to
+  // build the complete include chain for one and then walking up the chain
+  // of the other looking for a match.
+  // We use a map from FileID to Offset to store the chain. Easier than writing
+  // a custom set hash info that only depends on the first part of a pair.
+  typedef llvm::DenseMap<FileID, unsigned> LocSet;
+  LocSet LChain;
   do {
-    // If LOffs is larger than ROffs, then LOffs must be more deeply nested than
-    // ROffs, walk up the #include chain.
-    if (LOffs.first.ID > ROffs.first.ID) {
-      if (MoveUpIncludeHierarchy(LOffs, *this))
-        break; // We reached the top.
-      
-    } else {
-      // Otherwise, ROffs is larger than LOffs, so ROffs must be more deeply
-      // nested than LOffs, walk up the #include chain.
-      if (MoveUpIncludeHierarchy(ROffs, *this))
-        break; // We reached the top.
-    }
-  } while (LOffs.first != ROffs.first);
+    LChain.insert(LOffs);
+    // We catch the case where LOffs is in a file included by ROffs and
+    // quit early. The other way round unfortunately remains suboptimal.
+  } while (LOffs.first != ROffs.first && !MoveUpIncludeHierarchy(LOffs, *this));
+  LocSet::iterator I;
+  while((I = LChain.find(ROffs.first)) == LChain.end()) {
+    if (MoveUpIncludeHierarchy(ROffs, *this))
+      break; // Met at topmost file.
+  }
+  if (I != LChain.end())
+    LOffs = *I;
 
   // If we exited because we found a nearest common ancestor, compare the
   // locations within the common file and cache them.
@@ -1488,26 +1712,21 @@ bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS,
     return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second);
   }
 
-  // There is no common ancestor, most probably because one location is in the
-  // predefines buffer or an AST file.
-  // FIXME: We should rearrange the external interface so this simply never
-  // happens; it can't conceptually happen. Also see PR5662.
-  IsBeforeInTUCache.setQueryFIDs(FileID(), FileID()); // Don't try caching.
-
-  // Zip both entries up to the top level record.
-  while (!MoveUpIncludeHierarchy(LOffs, *this)) /*empty*/;
-  while (!MoveUpIncludeHierarchy(ROffs, *this)) /*empty*/;
-  
-  // If exactly one location is a memory buffer, assume it precedes the other.
-  
-  // Strip off macro instantation locations, going up to the top-level File
-  // SLocEntry.
-  bool LIsMB = getFileEntryForID(LOffs.first) == 0;
-  bool RIsMB = getFileEntryForID(ROffs.first) == 0;
-  if (LIsMB != RIsMB)
-    return LIsMB;
-
-  // Otherwise, just assume FileIDs were created in order.
+  // This can happen if a location is in a built-ins buffer.
+  // But see PR5662.
+  // Clear the lookup cache, it depends on a common location.
+  IsBeforeInTUCache.clear();
+  bool LIsBuiltins = strcmp("<built-in>",
+                            getBuffer(LOffs.first)->getBufferIdentifier()) == 0;
+  bool RIsBuiltins = strcmp("<built-in>",
+                            getBuffer(ROffs.first)->getBufferIdentifier()) == 0;
+  // built-in is before non-built-in
+  if (LIsBuiltins != RIsBuiltins)
+    return LIsBuiltins;
+  assert(LIsBuiltins && RIsBuiltins &&
+         "Non-built-in locations must be rooted in the main file");
+  // Both are in built-in buffers, but from different files. We just claim that
+  // lower IDs come first.
   return LOffs.first < ROffs.first;
 }
 
@@ -1517,20 +1736,26 @@ void SourceManager::PrintStats() const {
   llvm::errs() << "\n*** Source Manager Stats:\n";
   llvm::errs() << FileInfos.size() << " files mapped, " << MemBufferInfos.size()
                << " mem buffers mapped.\n";
-  llvm::errs() << SLocEntryTable.size() << " SLocEntry's allocated ("
-               << SLocEntryTable.capacity()*sizeof(SrcMgr::SLocEntry)
+  llvm::errs() << LocalSLocEntryTable.size() << " local SLocEntry's allocated ("
+               << llvm::capacity_in_bytes(LocalSLocEntryTable)
                << " bytes of capacity), "
-               << NextOffset << "B of Sloc address space used.\n";
-
+               << NextLocalOffset << "B of Sloc address space used.\n";
+  llvm::errs() << LoadedSLocEntryTable.size()
+               << " loaded SLocEntries allocated, "
+               << MaxLoadedOffset - CurrentLoadedOffset
+               << "B of Sloc address space used.\n";
+  
   unsigned NumLineNumsComputed = 0;
   unsigned NumFileBytesMapped = 0;
   for (fileinfo_iterator I = fileinfo_begin(), E = fileinfo_end(); I != E; ++I){
     NumLineNumsComputed += I->second->SourceLineCache != 0;
     NumFileBytesMapped  += I->second->getSizeBytesMapped();
   }
+  unsigned NumMacroArgsComputed = MacroArgsCacheMap.size();
 
   llvm::errs() << NumFileBytesMapped << " bytes of files mapped, "
-               << NumLineNumsComputed << " files with line #'s computed.\n";
+               << NumLineNumsComputed << " files with line #'s computed, "
+               << NumMacroArgsComputed << " files with macro args computed.\n";
   llvm::errs() << "FileID scans: " << NumLinearScans << " linear, "
                << NumBinaryProbes << " binary.\n";
 }
@@ -1557,3 +1782,11 @@ SourceManager::MemoryBufferSizes SourceManager::getMemoryBufferSizes() const {
   return MemoryBufferSizes(malloc_bytes, mmap_bytes);
 }
 
+size_t SourceManager::getDataStructureSizes() const {
+  return llvm::capacity_in_bytes(MemBufferInfos)
+    + llvm::capacity_in_bytes(LocalSLocEntryTable)
+    + llvm::capacity_in_bytes(LoadedSLocEntryTable)
+    + llvm::capacity_in_bytes(SLocEntryLoaded)
+    + llvm::capacity_in_bytes(FileInfos)
+    + llvm::capacity_in_bytes(OverriddenFiles);
+}