From 9af37a3de8c8688adae383471379f0216287ce28 Mon Sep 17 00:00:00 2001
From: Tanya Lattner <tonic@nondot.org>
Date: Wed, 2 Nov 2011 00:24:56 +0000
Subject: [PATCH] Add support to the linker to lazily link in functions. This
 change only links functions marked with specific linkage (internal, private,
 linker_private, linker_private_weak, linker_private_weak_def_auto, linkonce,
 linkonce_odr, and available_externally) if they have uses in the destination
 module. Instead of automatically linking, these functions are placed onto a
 worklist to be processed in the final stage of linking. We iterate over the
 list and if any functions on the list have uses in the destination module, we
 link them in and repeat the process until no changes in the state (uses) has
 changed. This means that any functions in the LazilyLink worklist that have a
 use in the destination module will be linked in and none that don't.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143524 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Linker/LinkModules.cpp | 58 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)

diff --git a/lib/Linker/LinkModules.cpp b/lib/Linker/LinkModules.cpp
index bcc6782129c..ab099bbfaf8 100644
--- a/lib/Linker/LinkModules.cpp
+++ b/lib/Linker/LinkModules.cpp
@@ -341,6 +341,9 @@ namespace {
     // Set of items not to link in from source.
     SmallPtrSet<const Value*, 16> DoNotLinkFromSource;
     
+    // Vector of functions to lazily link in.
+    std::vector<Function*> LazilyLinkFunctions;
+    
   public:
     std::string ErrorMsg;
     
@@ -708,6 +711,13 @@ bool ModuleLinker::linkFunctionProto(Function *SF) {
     // Any uses of DF need to change to NewDF, with cast.
     DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDF, DGV->getType()));
     DGV->eraseFromParent();
+  } else {
+    // Internal, LO_ODR, or LO linkage - stick in set to ignore and lazily link.
+    if (SF->hasLocalLinkage() || SF->hasLinkOnceLinkage() ||
+        SF->hasAvailableExternallyLinkage()) {
+      DoNotLinkFromSource.insert(SF);
+      LazilyLinkFunctions.push_back(SF);
+    }
   }
   
   ValueMap[SF] = NewDF;
@@ -974,6 +984,54 @@ bool ModuleLinker::run() {
   // are properly remapped.
   linkNamedMDNodes();
 
+  // Process vector of lazily linked in functions.
+  bool LinkedInAnyFunctions;
+  do {
+    LinkedInAnyFunctions = false;
+    
+    for(std::vector<Function*>::iterator I = LazilyLinkFunctions.begin(),
+        E = LazilyLinkFunctions.end(); I != E; ++I) {
+      if (!*I)
+        continue;
+      
+      Function *SF = *I;
+      Function *DF = cast<Function>(ValueMap[SF]);
+      
+      if (!DF->use_empty()) {
+        
+        // Materialize if necessary.
+        if (SF->isDeclaration()) {
+          if (!SF->isMaterializable())
+            continue;
+          if (SF->Materialize(&ErrorMsg))
+            return true;
+        }
+        
+        // Link in function body.
+        linkFunctionBody(DF, SF);
+        
+        // "Remove" from vector by setting the element to 0.
+        *I = 0;
+        
+        // Set flag to indicate we may have more functions to lazily link in
+        // since we linked in a function.
+        LinkedInAnyFunctions = true;
+      }
+    }
+  } while (LinkedInAnyFunctions);
+  
+  // Remove any prototypes of functions that were not actually linked in.
+  for(std::vector<Function*>::iterator I = LazilyLinkFunctions.begin(),
+      E = LazilyLinkFunctions.end(); I != E; ++I) {
+    if (!*I)
+      continue;
+    
+    Function *SF = *I;
+    Function *DF = cast<Function>(ValueMap[SF]);
+    if (DF->use_empty())
+      DF->eraseFromParent();
+  }
+  
   // Now that all of the types from the source are used, resolve any structs
   // copied over to the dest that didn't exist there.
   TypeMap.linkDefinedTypeBodies();
-- 
2.34.1