now that all the decl reference and creation stuff is going through two

very simple places, reimplement the deferred decl emission logic to not be O(N^2),
fixing PR3810.


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

2 files changed, 74 insertions, 41 deletions

diff --git a/lib/CodeGen/CodeGenModule.cpp b/lib/CodeGen/CodeGenModule.cpp
index 109344b9c6..93bf6dd8f0 100644
--- a/lib/CodeGen/CodeGenModule.cpp
+++ b/lib/CodeGen/CodeGenModule.cpp
@@ -441,38 +441,26 @@ void CodeGenModule::EmitLLVMUsed() {
 }
 
 void CodeGenModule::EmitDeferred() {
-  // Emit code for any deferred decl which was used.  Since a
-  // previously unused static decl may become used during the
-  // generation of code for a static function, iterate until no
-  // changes are made.
-  bool Changed;
-  do {
-    Changed = false;
+  // Emit code for any potentially referenced deferred decls.  Since a
+  // previously unused static decl may become used during the generation of code
+  // for a static function, iterate until no  changes are made.
+  while (!DeferredDeclsToEmit.empty()) {
+    const ValueDecl *D = DeferredDeclsToEmit.back();
+    DeferredDeclsToEmit.pop_back();
+
+    // The mangled name for the decl must have been emitted in GlobalDeclMap.
+    // Look it up to see if it was defined with a stronger definition (e.g. an
+    // extern inline function with a strong function redefinition).  If so,
+    // just ignore the deferred decl.
+    llvm::GlobalValue *CGRef = GlobalDeclMap[getMangledName(D)];
+    assert(CGRef && "Deferred decl wasn't referenced?");
     
-    for (std::list<const ValueDecl*>::iterator i = DeferredDecls.begin(),
-         e = DeferredDecls.end(); i != e; ) {
-      const ValueDecl *D = *i;
-      
-      // Check if we have used a decl with the same name
-      // FIXME: The AST should have some sort of aggregate decls or
-      // global symbol map.
-      // FIXME: This is missing some important cases. For example, we
-      // need to check for uses in an alias.
-      if (!GlobalDeclMap.count(getMangledName(D))) {
-        ++i;
-        continue;
-      }
-      
-      // Emit the definition.
-      EmitGlobalDefinition(D);
-
-      // Erase the used decl from the list.
-      i = DeferredDecls.erase(i);
-
-      // Remember that we made a change.
-      Changed = true;
-    }
-  } while (Changed);
+    if (!CGRef->isDeclaration())
+      continue;
+    
+    // Otherwise, emit the definition and move on to the next one.
+    EmitGlobalDefinition(D);
+  }
 }
 
 /// EmitAnnotateAttr - Generate the llvm::ConstantStruct which contains the 
@@ -552,6 +540,7 @@ void CodeGenModule::EmitGlobal(const ValueDecl *Global) {
     return;
   }
 
+  // Ignore declarations, they will be emitted on their first use.
   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(Global)) {
     // Forward declarations are emitted lazily on first use.
     if (!FD->isThisDeclarationADefinition())
@@ -565,9 +554,20 @@ void CodeGenModule::EmitGlobal(const ValueDecl *Global) {
       return;
   }
 
-  // Defer code generation when possible.
+  // Defer code generation when possible if this is a static definition, inline
+  // function etc.  These we only want to emit if they are used.
   if (MayDeferGeneration(Global)) {
-    DeferredDecls.push_back(Global);
+    // If the value has already been used, add it directly to the
+    // DeferredDeclsToEmit list.
+    const char *MangledName = getMangledName(Global);
+    if (GlobalDeclMap.count(MangledName))
+      DeferredDeclsToEmit.push_back(Global);
+    else {
+      // Otherwise, remember that we saw a deferred decl with this name.  The
+      // first use of the mangled name will cause it to move into
+      // DeferredDeclsToEmit.
+      DeferredDecls[MangledName] = Global;
+    }
     return;
   }
 
@@ -606,6 +606,19 @@ llvm::Constant *CodeGenModule::GetAddrOfFunction(const FunctionDecl *D,
     return llvm::ConstantExpr::getBitCast(Entry, PTy);
   }
   
+  // This is the first use or definition of a mangled name.  If there is a
+  // deferred decl with this name, remember that we need to emit it at the end
+  // of the file.
+  llvm::DenseMap<const char*, const ValueDecl*>::iterator DDI = 
+    DeferredDecls.find(MangledName);
+  if (DDI != DeferredDecls.end()) {
+    // Move the potentially referenced deferred decl to the DeferredDeclsToEmit
+    // list, and remove it from DeferredDecls (since we don't need it anymore).
+    DeferredDeclsToEmit.push_back(DDI->second);
+    DeferredDecls.erase(DDI);
+  }
+  
+  
   // This function doesn't have a complete type (for example, the return
   // type is an incomplete struct). Use a fake type instead, and make
   // sure not to try to set attributes.
@@ -648,7 +661,19 @@ llvm::Constant *CodeGenModule::GetAddrOfGlobalVar(const VarDecl *D,
     const llvm::Type *PTy = llvm::PointerType::get(Ty, ASTTy.getAddressSpace());
     return llvm::ConstantExpr::getBitCast(Entry, PTy);
   }
-   
+  
+  // This is the first use or definition of a mangled name.  If there is a
+  // deferred decl with this name, remember that we need to emit it at the end
+  // of the file.
+  llvm::DenseMap<const char*, const ValueDecl*>::iterator DDI = 
+    DeferredDecls.find(MangledName);
+  if (DDI != DeferredDecls.end()) {
+    // Move the potentially referenced deferred decl to the DeferredDeclsToEmit
+    // list, and remove it from DeferredDecls (since we don't need it anymore).
+    DeferredDeclsToEmit.push_back(DDI->second);
+    DeferredDecls.erase(DDI);
+  }
+  
   llvm::GlobalVariable *GV = 
     new llvm::GlobalVariable(Ty, false, 
                              llvm::GlobalValue::ExternalLinkage,
diff --git a/lib/CodeGen/CodeGenModule.h b/lib/CodeGen/CodeGenModule.h
index 47456804d3..91030e7aa3 100644
--- a/lib/CodeGen/CodeGenModule.h
+++ b/lib/CodeGen/CodeGenModule.h
@@ -95,8 +95,12 @@ class CodeGenModule : public BlockModule {
   /// globals and therefore may not be of the same type as the decl,
   /// they should be bitcasted on retrieval. Also note that the
   /// globals are keyed on their source mangled name, not the global name
-  /// (which may change with attributes such as asm-labels).  This key
+  /// (which may change with attributes such as asm-labels).  The key
   /// to this map should be generated using getMangledName().
+  ///
+  /// Note that this map always lines up exactly with the contents of the LLVM
+  /// IR symbol table, but this is quicker to query since it is doing uniqued
+  /// pointer lookups instead of full string lookups.
   llvm::DenseMap<const char*, llvm::GlobalValue*> GlobalDeclMap;
 
   /// \brief Contains the strings used for mangled names.
@@ -111,13 +115,17 @@ class CodeGenModule : public BlockModule {
   /// and may reference forward.
   std::vector<const ValueDecl*> Aliases;
 
-  /// DeferredDecls - List of decls for which code generation has been
-  /// deferred. When the translation unit has been fully processed we
-  /// will lazily emit definitions for only the decls that were
-  /// actually used.  This should contain only Function and Var decls,
-  /// and only those which actually define something.
-  std::list<const ValueDecl*> DeferredDecls;
+  /// DeferredDecls - This contains all the decls which have definitions but
+  /// which are deferred for emission and therefore should only be output if
+  /// they are actually used.  If a decl is in this, then it is known to have
+  /// not been referenced yet.  The key to this map is a uniqued mangled name.
+  llvm::DenseMap<const char*, const ValueDecl*> DeferredDecls;
 
+  /// DeferredDeclsToEmit - This is a list of deferred decls which we have seen
+  /// that *are* actually referenced.  These get code generated when the module
+  /// is done.
+  std::vector<const ValueDecl*> DeferredDeclsToEmit;
+  
   /// LLVMUsed - List of global values which are required to be
   /// present in the object file; bitcast to i8*. This is used for
   /// forcing visibility of symbols which may otherwise be optimized