Extend RemapInstruction and friends to take an optional new parameter, a ValueMaterializer.

Extend LinkModules to pass a ValueMaterializer to RemapInstruction and friends to lazily create Functions for lazily linked globals. This is a big win when linking small modules with large (mostly unused) library modules.

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

6 files changed, 141 insertions, 69 deletions

diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h
index 14212f622b..3ec132937c 100644
--- a/include/llvm/Transforms/Utils/Cloning.h
+++ b/include/llvm/Transforms/Utils/Cloning.h
@@ -131,7 +131,8 @@ void CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
                        SmallVectorImpl<ReturnInst*> &Returns,
                        const char *NameSuffix = "", 
                        ClonedCodeInfo *CodeInfo = 0,
-                       ValueMapTypeRemapper *TypeMapper = 0);
+                       ValueMapTypeRemapper *TypeMapper = 0,
+                       ValueMaterializer *Materializer = 0);
 
 /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
 /// except that it does some simple constant prop and DCE on the fly.  The
diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h
index 5390c5e8ed..d56ac07690 100644
--- a/include/llvm/Transforms/Utils/ValueMapper.h
+++ b/include/llvm/Transforms/Utils/ValueMapper.h
@@ -33,6 +33,19 @@ namespace llvm {
     /// remap types while mapping values.
     virtual Type *remapType(Type *SrcTy) = 0;
   };
+
+  /// ValueMaterializer - This is a class that can be implemented by clients
+  /// to materialize Values on demand.
+  class ValueMaterializer {
+    virtual void anchor(); // Out of line method.
+  public:
+    virtual ~ValueMaterializer() {}
+
+    /// materializeValueFor - The client should implement this method if they
+    /// want to generate a mapped Value on demand. For example, if linking
+    /// lazily.
+    virtual Value *materializeValueFor(Value *V) = 0;
+  };
   
   /// RemapFlags - These are flags that the value mapping APIs allow.
   enum RemapFlags {
@@ -55,23 +68,29 @@ namespace llvm {
   
   Value *MapValue(const Value *V, ValueToValueMapTy &VM,
                   RemapFlags Flags = RF_None,
-                  ValueMapTypeRemapper *TypeMapper = 0);
+                  ValueMapTypeRemapper *TypeMapper = 0,
+                  ValueMaterializer *Materializer = 0);
 
   void RemapInstruction(Instruction *I, ValueToValueMapTy &VM,
                         RemapFlags Flags = RF_None,
-                        ValueMapTypeRemapper *TypeMapper = 0);
+                        ValueMapTypeRemapper *TypeMapper = 0,
+                        ValueMaterializer *Materializer = 0);
   
   /// MapValue - provide versions that preserve type safety for MDNode and
   /// Constants.
   inline MDNode *MapValue(const MDNode *V, ValueToValueMapTy &VM,
                           RemapFlags Flags = RF_None,
-                          ValueMapTypeRemapper *TypeMapper = 0) {
-    return cast<MDNode>(MapValue((const Value*)V, VM, Flags, TypeMapper));
+                          ValueMapTypeRemapper *TypeMapper = 0,
+                          ValueMaterializer *Materializer = 0) {
+    return cast<MDNode>(MapValue((const Value*)V, VM, Flags, TypeMapper,
+                                 Materializer));
   }
   inline Constant *MapValue(const Constant *V, ValueToValueMapTy &VM,
                             RemapFlags Flags = RF_None,
-                            ValueMapTypeRemapper *TypeMapper = 0) {
-    return cast<Constant>(MapValue((const Value*)V, VM, Flags, TypeMapper));
+                            ValueMapTypeRemapper *TypeMapper = 0,
+                            ValueMaterializer *Materializer = 0) {
+    return cast<Constant>(MapValue((const Value*)V, VM, Flags, TypeMapper,
+                                   Materializer));
   }
   
 
diff --git a/lib/Linker/LinkModules.cpp b/lib/Linker/LinkModules.cpp
index d2e13c91c4..f32211245f 100644
--- a/lib/Linker/LinkModules.cpp
+++ b/lib/Linker/LinkModules.cpp
@@ -353,12 +353,32 @@ Type *TypeMapTy::getImpl(Type *Ty) {
 //===----------------------------------------------------------------------===//
 
 namespace {
+  class ModuleLinker;
+
+  /// ValueMaterializerTy - Creates prototypes for functions that are lazily
+  /// linked on the fly. This speeds up linking for modules with many
+  /// lazily linked functions of which few get used.
+  class ValueMaterializerTy : public ValueMaterializer {
+    TypeMapTy &TypeMap;
+    Module *DstM;
+    std::vector<Function*> &LazilyLinkFunctions;
+  public:
+    ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM,
+                        std::vector<Function*> &LazilyLinkFunctions) :
+      ValueMaterializer(), TypeMap(TypeMap), DstM(DstM),
+      LazilyLinkFunctions(LazilyLinkFunctions) {
+    }
+
+    virtual Value *materializeValueFor(Value *V);
+  };
+
   /// ModuleLinker - This is an implementation class for the LinkModules
   /// function, which is the entrypoint for this file.
   class ModuleLinker {
     Module *DstM, *SrcM;
     
     TypeMapTy TypeMap; 
+    ValueMaterializerTy ValMaterializer;
 
     /// ValueMap - Mapping of values from what they used to be in Src, to what
     /// they are now in DstM.  ValueToValueMapTy is a ValueMap, which involves
@@ -386,7 +406,9 @@ namespace {
     std::string ErrorMsg;
     
     ModuleLinker(Module *dstM, TypeSet &Set, Module *srcM, unsigned mode)
-      : DstM(dstM), SrcM(srcM), TypeMap(Set), Mode(mode) { }
+      : DstM(dstM), SrcM(srcM), TypeMap(Set),
+        ValMaterializer(TypeMap, DstM, LazilyLinkFunctions),
+        Mode(mode) { }
     
     bool run();
     
@@ -487,6 +509,20 @@ static bool isLessConstraining(GlobalValue::VisibilityTypes a,
   return false;
 }
 
+Value *ValueMaterializerTy::materializeValueFor(Value *V) {
+  Function *SF = dyn_cast<Function>(V);
+  if (!SF)
+    return NULL;
+
+  Function *DF = Function::Create(TypeMap.get(SF->getFunctionType()),
+                                  SF->getLinkage(), SF->getName(), DstM);
+  copyGVAttributes(DF, SF);
+
+  LazilyLinkFunctions.push_back(SF);
+  return DF;
+}
+
+
 /// getLinkageResult - This analyzes the two global values and determines what
 /// the result will look like in the destination module.  In particular, it
 /// computes the resultant linkage type and visibility, computes whether the
@@ -802,6 +838,14 @@ bool ModuleLinker::linkFunctionProto(Function *SF) {
     }
   }
   
+  // If the function is to be lazily linked, don't create it just yet.
+  // The ValueMaterializerTy will deal with creating it if it's used.
+  if (!DGV && (SF->hasLocalLinkage() || SF->hasLinkOnceLinkage() ||
+               SF->hasAvailableExternallyLinkage())) {
+    DoNotLinkFromSource.insert(SF);
+    return false;
+  }
+
   // If there is no linkage to be performed or we are linking from the source,
   // bring SF over.
   Function *NewDF = Function::Create(TypeMap.get(SF->getFunctionType()),
@@ -814,13 +858,6 @@ 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;
@@ -887,7 +924,7 @@ void ModuleLinker::linkAppendingVarInit(const AppendingVarInfo &AVI) {
   SmallVector<Constant*, 16> Elements;
   getArrayElements(AVI.DstInit, Elements);
   
-  Constant *SrcInit = MapValue(AVI.SrcInit, ValueMap, RF_None, &TypeMap);
+  Constant *SrcInit = MapValue(AVI.SrcInit, ValueMap, RF_None, &TypeMap, &ValMaterializer);
   getArrayElements(SrcInit, Elements);
   
   ArrayType *NewType = cast<ArrayType>(AVI.NewGV->getType()->getElementType());
@@ -908,7 +945,7 @@ void ModuleLinker::linkGlobalInits() {
     GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[I]);
     // Figure out what the initializer looks like in the dest module.
     DGV->setInitializer(MapValue(I->getInitializer(), ValueMap,
-                                 RF_None, &TypeMap));
+                                 RF_None, &TypeMap, &ValMaterializer));
   }
 }
 
@@ -938,12 +975,14 @@ void ModuleLinker::linkFunctionBody(Function *Dst, Function *Src) {
     // functions and patch them up to point to the local versions.
     for (Function::iterator BB = Dst->begin(), BE = Dst->end(); BB != BE; ++BB)
       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
-        RemapInstruction(I, ValueMap, RF_IgnoreMissingEntries, &TypeMap);
+        RemapInstruction(I, ValueMap, RF_IgnoreMissingEntries,
+                         &TypeMap, &ValMaterializer);
     
   } else {
     // Clone the body of the function into the dest function.
     SmallVector<ReturnInst*, 8> Returns; // Ignore returns.
-    CloneFunctionInto(Dst, Src, ValueMap, false, Returns, "", NULL, &TypeMap);
+    CloneFunctionInto(Dst, Src, ValueMap, false, Returns, "", NULL,
+                      &TypeMap, &ValMaterializer);
   }
   
   // There is no need to map the arguments anymore.
@@ -961,7 +1000,8 @@ void ModuleLinker::linkAliasBodies() {
       continue;
     if (Constant *Aliasee = I->getAliasee()) {
       GlobalAlias *DA = cast<GlobalAlias>(ValueMap[I]);
-      DA->setAliasee(MapValue(Aliasee, ValueMap, RF_None, &TypeMap));
+      DA->setAliasee(MapValue(Aliasee, ValueMap, RF_None,
+                              &TypeMap, &ValMaterializer));
     }
   }
 }
@@ -978,7 +1018,7 @@ void ModuleLinker::linkNamedMDNodes() {
     // Add Src elements into Dest node.
     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
       DestNMD->addOperand(MapValue(I->getOperand(i), ValueMap,
-                                   RF_None, &TypeMap));
+                                   RF_None, &TypeMap, &ValMaterializer));
   }
 }
 
@@ -1238,49 +1278,36 @@ bool ModuleLinker::run() {
     LinkedInAnyFunctions = false;
     
     for(std::vector<Function*>::iterator I = LazilyLinkFunctions.begin(),
-        E = LazilyLinkFunctions.end(); I != E; ++I) {
-      if (!*I)
-        continue;
-      
+        E = LazilyLinkFunctions.end(); I != E; ++I) {      
       Function *SF = *I;
+      if (!SF)
+        continue;
+
       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);
-        SF->Dematerialize();
 
-        // "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;
+      // Materialize if necessary.
+      if (SF->isDeclaration()) {
+        if (!SF->isMaterializable())
+          continue;
+        if (SF->Materialize(&ErrorMsg))
+          return true;
       }
+      
+      // Erase from vector *before* the function body is linked - linkFunctionBody could
+      // invalidate I.
+      LazilyLinkFunctions.erase(I);
+
+      // Link in function body.
+      linkFunctionBody(DF, SF);
+      SF->Dematerialize();
+
+      // Set flag to indicate we may have more functions to lazily link in
+      // since we linked in a function.
+      LinkedInAnyFunctions = true;
+      break;
     }
   } 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();
diff --git a/lib/Transforms/Utils/CloneFunction.cpp b/lib/Transforms/Utils/CloneFunction.cpp
index be8d39e128..d105f5e24a 100644
--- a/lib/Transforms/Utils/CloneFunction.cpp
+++ b/lib/Transforms/Utils/CloneFunction.cpp
@@ -78,7 +78,8 @@ void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
                              bool ModuleLevelChanges,
                              SmallVectorImpl<ReturnInst*> &Returns,
                              const char *NameSuffix, ClonedCodeInfo *CodeInfo,
-                             ValueMapTypeRemapper *TypeMapper) {
+                             ValueMapTypeRemapper *TypeMapper,
+                             ValueMaterializer *Materializer) {
   assert(NameSuffix && "NameSuffix cannot be null!");
 
 #ifndef NDEBUG
@@ -147,7 +148,7 @@ void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
     for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
       RemapInstruction(II, VMap,
                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
-                       TypeMapper);
+                       TypeMapper, Materializer);
 }
 
 /// CloneFunction - Return a copy of the specified function, but without
diff --git a/lib/Transforms/Utils/ValueMapper.cpp b/lib/Transforms/Utils/ValueMapper.cpp
index 544c5eed7e..457fc80e1e 100644
--- a/lib/Transforms/Utils/ValueMapper.cpp
+++ b/lib/Transforms/Utils/ValueMapper.cpp
@@ -22,14 +22,22 @@ using namespace llvm;
 
 // Out of line method to get vtable etc for class.
 void ValueMapTypeRemapper::anchor() {}
+void ValueMaterializer::anchor() {}
 
 Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags,
-                      ValueMapTypeRemapper *TypeMapper) {
+                      ValueMapTypeRemapper *TypeMapper,
+                      ValueMaterializer *Materializer) {
   ValueToValueMapTy::iterator I = VM.find(V);
   
   // If the value already exists in the map, use it.
   if (I != VM.end() && I->second) return I->second;
   
+  // If we have a materializer and it can materialize a value, use that.
+  if (Materializer) {
+    if (Value *NewV = Materializer->materializeValueFor(const_cast<Value*>(V)))
+      return VM[V] = NewV;
+  }
+
   // Global values do not need to be seeded into the VM if they
   // are using the identity mapping.
   if (isa<GlobalValue>(V) || isa<MDString>(V))
@@ -64,7 +72,7 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags,
     for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) {
       Value *OP = MD->getOperand(i);
       if (OP == 0) continue;
-      Value *Mapped_OP = MapValue(OP, VM, Flags, TypeMapper);
+      Value *Mapped_OP = MapValue(OP, VM, Flags, TypeMapper, Materializer);
       // Use identity map if Mapped_Op is null and we can ignore missing
       // entries.
       if (Mapped_OP == OP ||
@@ -79,7 +87,7 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags,
         if (Op == 0)
           Elts.push_back(0);
         else {
-          Value *Mapped_Op = MapValue(Op, VM, Flags, TypeMapper);
+          Value *Mapped_Op = MapValue(Op, VM, Flags, TypeMapper, Materializer);
           // Use identity map if Mapped_Op is null and we can ignore missing
           // entries.
           if (Mapped_Op == 0 && (Flags & RF_IgnoreMissingEntries))
@@ -109,9 +117,9 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags,
   
   if (BlockAddress *BA = dyn_cast<BlockAddress>(C)) {
     Function *F = 
-      cast<Function>(MapValue(BA->getFunction(), VM, Flags, TypeMapper));
+      cast<Function>(MapValue(BA->getFunction(), VM, Flags, TypeMapper, Materializer));
     BasicBlock *BB = cast_or_null<BasicBlock>(MapValue(BA->getBasicBlock(), VM,
-                                                       Flags, TypeMapper));
+                                                       Flags, TypeMapper, Materializer));
     return VM[V] = BlockAddress::get(F, BB ? BB : BA->getBasicBlock());
   }
   
@@ -121,7 +129,7 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags,
   Value *Mapped = 0;
   for (; OpNo != NumOperands; ++OpNo) {
     Value *Op = C->getOperand(OpNo);
-    Mapped = MapValue(Op, VM, Flags, TypeMapper);
+    Mapped = MapValue(Op, VM, Flags, TypeMapper, Materializer);
     if (Mapped != C) break;
   }
   
@@ -149,7 +157,7 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags,
     // Map the rest of the operands that aren't processed yet.
     for (++OpNo; OpNo != NumOperands; ++OpNo)
       Ops.push_back(MapValue(cast<Constant>(C->getOperand(OpNo)), VM,
-                             Flags, TypeMapper));
+                             Flags, TypeMapper, Materializer));
   }
   
   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
@@ -173,10 +181,11 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags,
 /// current values into those specified by VMap.
 ///
 void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap,
-                            RemapFlags Flags, ValueMapTypeRemapper *TypeMapper){
+                            RemapFlags Flags, ValueMapTypeRemapper *TypeMapper,
+                            ValueMaterializer *Materializer){
   // Remap operands.
   for (User::op_iterator op = I->op_begin(), E = I->op_end(); op != E; ++op) {
-    Value *V = MapValue(*op, VMap, Flags, TypeMapper);
+    Value *V = MapValue(*op, VMap, Flags, TypeMapper, Materializer);
     // If we aren't ignoring missing entries, assert that something happened.
     if (V != 0)
       *op = V;
@@ -204,7 +213,7 @@ void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap,
   for (SmallVectorImpl<std::pair<unsigned, MDNode *> >::iterator
        MI = MDs.begin(), ME = MDs.end(); MI != ME; ++MI) {
     MDNode *Old = MI->second;
-    MDNode *New = MapValue(Old, VMap, Flags, TypeMapper);
+    MDNode *New = MapValue(Old, VMap, Flags, TypeMapper, Materializer);
     if (New != Old)
       I->setMetadata(MI->first, New);
   }
diff --git a/test/Linker/transitive-lazy-link.ll b/test/Linker/transitive-lazy-link.ll
new file mode 100644
index 0000000000..32b9d219ae
--- /dev/null
+++ b/test/Linker/transitive-lazy-link.ll
@@ -0,0 +1,15 @@
+; @f and @g are lazily linked. @f requires @g - ensure @g is correctly linked.
+
+; RUN: echo -e "declare i32 @f(i32)\ndefine i32 @h(i32 %x) {\n%1 = call i32 @f(i32 %x)\nret i32 %1\n}" | llvm-as >%t.1.bc
+; RUN: llvm-as < %s > %t.2.bc
+; RUN: llvm-link %t.1.bc %t.2.bc
+
+define available_externally i32 @f(i32 %x) {
+  %1 = call i32 @g(i32 %x)
+  ret i32 %1
+}
+
+define available_externally i32 @g(i32 %x) {
+  ret i32 5
+}
+