Keep history of macro definitions and #undefs

Summary:
Summary: Keep history of macro definitions and #undefs with corresponding source locations, so that we can later find out all macros active in a specified source location. We don't save the history in PCH (no need currently). Memory overhead is about sizeof(void*)*3*<number of macro definitions and #undefs>+<in-memory size of all #undef'd macros>

I've run a test on a file composed of 109 .h files from boost 1.49 on x86-64 linux.
Stats before this patch:
*** Preprocessor Stats:
73222 directives found:
  19171 #define.
  4345 #undef.
  #include/#include_next/#import:
    5233 source files entered.
    27 max include stack depth
  19210 #if/#ifndef/#ifdef.
  2384 #else/#elif.
  6891 #endif.
  408 #pragma.
14466 #if/#ifndef#ifdef regions skipped
80023/451669/1270 obj/fn/builtin macros expanded, 85724 on the fast path.
127145 token paste (##) operations performed, 11008 on the fast path.

Preprocessor Memory: 5874615B total
  BumpPtr: 4399104
  Macro Expanded Tokens: 417768
  Predefines Buffer: 8135
  Macros: 1048576
  #pragma push_macro Info: 0
  Poison Reasons: 1024
  Comment Handlers: 8

Stats with this patch:
...
Preprocessor Memory: 7541687B total
  BumpPtr: 6066176
  Macro Expanded Tokens: 417768
  Predefines Buffer: 8135
  Macros: 1048576
  #pragma push_macro Info: 0
  Poison Reasons: 1024
  Comment Handlers: 8

In my test increase in memory usage is about 1.7Mb, which is ~28% of initial preprocessor's memory usage and about 0.8% of clang's total VMM allocation.

As for CPU overhead, it should only be noticeable when iterating over all macros, and should mostly consist of couple extra dereferences and one comparison per macro + skipping of #undef'd macros. It's less trivial to measure, though, as the preprocessor consumes a very small fraction of compilation time.


Reviewers: doug.gregor, klimek, rsmith, djasper

Reviewed By: doug.gregor

CC: cfe-commits, chandlerc

Differential Revision: http://llvm-reviews.chandlerc.com/D28

llvm-svn: 162810

7 files changed, 72 insertions, 66 deletions

diff --git a/clang/lib/Frontend/PrintPreprocessedOutput.cpp b/clang/lib/Frontend/PrintPreprocessedOutput.cpp
index 5311ed52cd2..30707dc0c00 100644
--- a/clang/lib/Frontend/PrintPreprocessedOutput.cpp
+++ b/clang/lib/Frontend/PrintPreprocessedOutput.cpp
@@ -570,8 +570,12 @@ static void DoPrintMacros(Preprocessor &PP, raw_ostream *OS) {
   do PP.Lex(Tok);
   while (Tok.isNot(tok::eof));
 
-  SmallVector<id_macro_pair, 128>
-    MacrosByID(PP.macro_begin(), PP.macro_end());
+  SmallVector<id_macro_pair, 128> MacrosByID;
+  for (Preprocessor::macro_iterator I = PP.macro_begin(), E = PP.macro_end();
+       I != E; ++I) {
+    if (I->first->hasMacroDefinition())
+      MacrosByID.push_back(id_macro_pair(I->first, I->second));
+  }
   llvm::array_pod_sort(MacrosByID.begin(), MacrosByID.end(), MacroIDCompare);
 
   for (unsigned i = 0, e = MacrosByID.size(); i != e; ++i) {
diff --git a/clang/lib/Lex/MacroInfo.cpp b/clang/lib/Lex/MacroInfo.cpp
index 3d0c9a1c2b5..7a4964f7d26 100644
--- a/clang/lib/Lex/MacroInfo.cpp
+++ b/clang/lib/Lex/MacroInfo.cpp
@@ -15,44 +15,46 @@
 #include "clang/Lex/Preprocessor.h"
 using namespace clang;
 
-MacroInfo::MacroInfo(SourceLocation DefLoc) : Location(DefLoc) {
-  IsFunctionLike = false;
-  IsC99Varargs = false;
-  IsGNUVarargs = false;
-  IsBuiltinMacro = false;
-  IsFromAST = false;
-  ChangedAfterLoad = false;
-  IsDisabled = false;
-  IsUsed = false;
-  IsAllowRedefinitionsWithoutWarning = false;
-  IsWarnIfUnused = false;
-  IsDefinitionLengthCached = false;
-  IsPublic = true;
-  
-  ArgumentList = 0;
-  NumArguments = 0;
+MacroInfo::MacroInfo(SourceLocation DefLoc)
+  : Location(DefLoc),
+    PreviousDefinition(0),
+    ArgumentList(0),
+    NumArguments(0),
+    IsDefinitionLengthCached(false),
+    IsFunctionLike(false),
+    IsC99Varargs(false),
+    IsGNUVarargs(false),
+    IsBuiltinMacro(false),
+    IsFromAST(false),
+    ChangedAfterLoad(false),
+    IsDisabled(false),
+    IsUsed(false),
+    IsAllowRedefinitionsWithoutWarning(false),
+    IsWarnIfUnused(false),
+    IsPublic(true) {
 }
 
-MacroInfo::MacroInfo(const MacroInfo &MI, llvm::BumpPtrAllocator &PPAllocator) {
-  Location = MI.Location;
-  EndLocation = MI.EndLocation;
-  ReplacementTokens = MI.ReplacementTokens;
-  IsFunctionLike = MI.IsFunctionLike;
-  IsC99Varargs = MI.IsC99Varargs;
-  IsGNUVarargs = MI.IsGNUVarargs;
-  IsBuiltinMacro = MI.IsBuiltinMacro;
-  IsFromAST = MI.IsFromAST;
-  ChangedAfterLoad = MI.ChangedAfterLoad;
-  IsDisabled = MI.IsDisabled;
-  IsUsed = MI.IsUsed;
-  IsAllowRedefinitionsWithoutWarning = MI.IsAllowRedefinitionsWithoutWarning;
-  IsWarnIfUnused = MI.IsWarnIfUnused;
-  IsDefinitionLengthCached = MI.IsDefinitionLengthCached;
-  DefinitionLength = MI.DefinitionLength;
-  IsPublic = MI.IsPublic;
-  
-  ArgumentList = 0;
-  NumArguments = 0;
+MacroInfo::MacroInfo(const MacroInfo &MI, llvm::BumpPtrAllocator &PPAllocator)
+  : Location(MI.Location),
+    EndLocation(MI.EndLocation),
+    UndefLocation(MI.UndefLocation),
+    PreviousDefinition(0),
+    ArgumentList(0),
+    NumArguments(0),
+    ReplacementTokens(MI.ReplacementTokens),
+    DefinitionLength(MI.DefinitionLength),
+    IsDefinitionLengthCached(MI.IsDefinitionLengthCached),
+    IsFunctionLike(MI.IsFunctionLike),
+    IsC99Varargs(MI.IsC99Varargs),
+    IsGNUVarargs(MI.IsGNUVarargs),
+    IsBuiltinMacro(MI.IsBuiltinMacro),
+    IsFromAST(MI.IsFromAST),
+    ChangedAfterLoad(MI.ChangedAfterLoad),
+    IsDisabled(MI.IsDisabled),
+    IsUsed(MI.IsUsed),
+    IsAllowRedefinitionsWithoutWarning(MI.IsAllowRedefinitionsWithoutWarning),
+    IsWarnIfUnused(MI.IsWarnIfUnused),
+    IsPublic(MI.IsPublic) {
   setArgumentList(MI.ArgumentList, MI.NumArguments, PPAllocator);
 }
 
diff --git a/clang/lib/Lex/PPDirectives.cpp b/clang/lib/Lex/PPDirectives.cpp
index 74b9cbc881a..6de0e4a9f36 100644
--- a/clang/lib/Lex/PPDirectives.cpp
+++ b/clang/lib/Lex/PPDirectives.cpp
@@ -1849,7 +1849,7 @@ void Preprocessor::HandleDefineDirective(Token &DefineTok) {
   MI->setDefinitionEndLoc(LastTok.getLocation());
 
   // Finally, if this identifier already had a macro defined for it, verify that
-  // the macro bodies are identical and free the old definition.
+  // the macro bodies are identical, and issue diagnostics if they are not.
   if (MacroInfo *OtherMI = getMacroInfo(MacroNameTok.getIdentifierInfo())) {
     // It is very common for system headers to have tons of macro redefinitions
     // and for warnings to be disabled in system headers.  If this is the case,
@@ -1870,7 +1870,6 @@ void Preprocessor::HandleDefineDirective(Token &DefineTok) {
     }
     if (OtherMI->isWarnIfUnused())
       WarnUnusedMacroLocs.erase(OtherMI->getDefinitionLoc());
-    ReleaseMacroInfo(OtherMI);
   }
 
   setMacroInfo(MacroNameTok.getIdentifierInfo(), MI);
@@ -1921,9 +1920,11 @@ void Preprocessor::HandleUndefDirective(Token &UndefTok) {
   if (MI->isWarnIfUnused())
     WarnUnusedMacroLocs.erase(MI->getDefinitionLoc());
 
-  // Free macro definition.
-  ReleaseMacroInfo(MI);
-  setMacroInfo(MacroNameTok.getIdentifierInfo(), 0);
+  MI->setUndefLoc(MacroNameTok.getLocation());
+  IdentifierInfo *II = MacroNameTok.getIdentifierInfo();
+  II->setHasMacroDefinition(false);
+  if (II->isFromAST())
+    II->setChangedSinceDeserialization();
 }
 
 
diff --git a/clang/lib/Lex/PPMacroExpansion.cpp b/clang/lib/Lex/PPMacroExpansion.cpp
index 96d6b2c7297..936b37009c1 100644
--- a/clang/lib/Lex/PPMacroExpansion.cpp
+++ b/clang/lib/Lex/PPMacroExpansion.cpp
@@ -33,15 +33,15 @@ using namespace clang;
 
 MacroInfo *Preprocessor::getInfoForMacro(IdentifierInfo *II) const {
   assert(II->hasMacroDefinition() && "Identifier is not a macro!");
-  
-  llvm::DenseMap<IdentifierInfo*, MacroInfo*>::const_iterator Pos
-    = Macros.find(II);
+
+  macro_iterator Pos = Macros.find(II);
   if (Pos == Macros.end()) {
     // Load this macro from the external source.
     getExternalSource()->LoadMacroDefinition(II);
     Pos = Macros.find(II);
   }
   assert(Pos != Macros.end() && "Identifier macro info is missing!");
+  assert(Pos->second->getUndefLoc().isInvalid() && "Macro is undefined!");
   return Pos->second;
 }
 
@@ -49,17 +49,12 @@ MacroInfo *Preprocessor::getInfoForMacro(IdentifierInfo *II) const {
 ///
 void Preprocessor::setMacroInfo(IdentifierInfo *II, MacroInfo *MI,
                                 bool LoadedFromAST) {
-  if (MI) {
-    Macros[II] = MI;
-    II->setHasMacroDefinition(true);
-    if (II->isFromAST() && !LoadedFromAST)
-      II->setChangedSinceDeserialization();
-  } else if (II->hasMacroDefinition()) {
-    Macros.erase(II);
-    II->setHasMacroDefinition(false);
-    if (II->isFromAST() && !LoadedFromAST)
-      II->setChangedSinceDeserialization();
-  }
+  assert(MI && "MacroInfo should be non-zero!");
+  MI->setPreviousDefinition(Macros[II]);
+  Macros[II] = MI;
+  II->setHasMacroDefinition(true);
+  if (II->isFromAST() && !LoadedFromAST)
+    II->setChangedSinceDeserialization();
 }
 
 /// RegisterBuiltinMacro - Register the specified identifier in the identifier
diff --git a/clang/lib/Lex/Pragma.cpp b/clang/lib/Lex/Pragma.cpp
index b7f7d1d4a90..acf5c74556f 100644
--- a/clang/lib/Lex/Pragma.cpp
+++ b/clang/lib/Lex/Pragma.cpp
@@ -733,12 +733,10 @@ void Preprocessor::HandlePragmaPopMacro(Token &PopMacroTok) {
   llvm::DenseMap<IdentifierInfo*, std::vector<MacroInfo*> >::iterator iter =
     PragmaPushMacroInfo.find(IdentInfo);
   if (iter != PragmaPushMacroInfo.end()) {
-    // Release the MacroInfo currently associated with IdentInfo.
-    MacroInfo *CurrentMI = getMacroInfo(IdentInfo);
-    if (CurrentMI) {
+    // Forget the MacroInfo currently associated with IdentInfo.
+    if (MacroInfo *CurrentMI = getMacroInfo(IdentInfo)) {
       if (CurrentMI->isWarnIfUnused())
         WarnUnusedMacroLocs.erase(CurrentMI->getDefinitionLoc());
-      ReleaseMacroInfo(CurrentMI);
     }
 
     // Get the MacroInfo we want to reinstall.
diff --git a/clang/lib/Sema/SemaCodeComplete.cpp b/clang/lib/Sema/SemaCodeComplete.cpp
index 93413da00d8..05b22fa5371 100644
--- a/clang/lib/Sema/SemaCodeComplete.cpp
+++ b/clang/lib/Sema/SemaCodeComplete.cpp
@@ -2904,7 +2904,11 @@ static void AddMacroResults(Preprocessor &PP, ResultBuilder &Results,
   for (Preprocessor::macro_iterator M = PP.macro_begin(), 
                                  MEnd = PP.macro_end();
        M != MEnd; ++M) {
-    Results.AddResult(Result(M->first, 
+    // FIXME: Eventually, we'd want to be able to look back to the macro
+    // definition that was actually active at the point of code completion (even
+    // if that macro has since been #undef'd).
+    if (M->first->hasMacroDefinition())
+      Results.AddResult(Result(M->first, 
                              getMacroUsagePriority(M->first->getName(),
                                                    PP.getLangOpts(),
                                                    TargetTypeIsPointer)));
diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp
index a64e0d35795..4a3987cbdc7 100644
--- a/clang/lib/Serialization/ASTWriter.cpp
+++ b/clang/lib/Serialization/ASTWriter.cpp
@@ -1677,10 +1677,12 @@ void ASTWriter::WritePreprocessor(const Preprocessor &PP, bool IsModule) {
   for (Preprocessor::macro_iterator I = PP.macro_begin(Chain == 0), 
                                     E = PP.macro_end(Chain == 0);
        I != E; ++I) {
-    const IdentifierInfo *Name = I->first;
-    if (!IsModule || I->second->isPublic()) {
-      MacroDefinitionsSeen.insert(Name);
-      MacrosToEmit.push_back(std::make_pair(I->first, I->second));
+    // FIXME: We'll need to store macro history in PCH.
+    if (I->first->hasMacroDefinition()) {
+      if (!IsModule || I->second->isPublic()) {
+        MacroDefinitionsSeen.insert(I->first);
+        MacrosToEmit.push_back(std::make_pair(I->first, I->second));
+      }
     }
   }