Reapply r112091 and r111922, support for metadata linking, with a

fix: add a flag to MapValue and friends which indicates whether
any module-level mappings are being made. In the common case of
inlining, no module-level mappings are needed, so MapValue doesn't
need to examine non-function-local metadata, which can be very
expensive in the case of a large module with really deep metadata
(e.g. a large C++ program compiled with -g).

This flag is a little awkward; perhaps eventually it can be moved
into the ClonedCodeInfo class.

llvm-svn: 112190

4 files changed, 84 insertions, 51 deletions

diff --git a/llvm/lib/Transforms/Utils/CloneFunction.cpp b/llvm/lib/Transforms/Utils/CloneFunction.cpp
index c5c62bfd241..f43186edae4 100644
--- a/llvm/lib/Transforms/Utils/CloneFunction.cpp
+++ b/llvm/lib/Transforms/Utils/CloneFunction.cpp
@@ -69,10 +69,11 @@ BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
 }
 
 // Clone OldFunc into NewFunc, transforming the old arguments into references to
-// ArgMap values.
+// VMap values.
 //
 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
                              ValueToValueMapTy &VMap,
+                             bool ModuleLevelChanges,
                              SmallVectorImpl<ReturnInst*> &Returns,
                              const char *NameSuffix, ClonedCodeInfo *CodeInfo) {
   assert(NameSuffix && "NameSuffix cannot be null!");
@@ -126,7 +127,7 @@ void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
          BE = NewFunc->end(); BB != BE; ++BB)
     // Loop over all instructions, fixing each one as we find it...
     for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II)
-      RemapInstruction(II, VMap);
+      RemapInstruction(II, VMap, ModuleLevelChanges);
 }
 
 /// CloneFunction - Return a copy of the specified function, but without
@@ -139,6 +140,7 @@ void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
 ///
 Function *llvm::CloneFunction(const Function *F,
                               ValueToValueMapTy &VMap,
+                              bool ModuleLevelChanges,
                               ClonedCodeInfo *CodeInfo) {
   std::vector<const Type*> ArgTypes;
 
@@ -167,7 +169,7 @@ Function *llvm::CloneFunction(const Function *F,
     }
 
   SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
-  CloneFunctionInto(NewF, F, VMap, Returns, "", CodeInfo);
+  CloneFunctionInto(NewF, F, VMap, ModuleLevelChanges, Returns, "", CodeInfo);
   return NewF;
 }
 
@@ -180,6 +182,7 @@ namespace {
     Function *NewFunc;
     const Function *OldFunc;
     ValueToValueMapTy &VMap;
+    bool ModuleLevelChanges;
     SmallVectorImpl<ReturnInst*> &Returns;
     const char *NameSuffix;
     ClonedCodeInfo *CodeInfo;
@@ -187,12 +190,14 @@ namespace {
   public:
     PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
                           ValueToValueMapTy &valueMap,
+                          bool moduleLevelChanges,
                           SmallVectorImpl<ReturnInst*> &returns,
                           const char *nameSuffix, 
                           ClonedCodeInfo *codeInfo,
                           const TargetData *td)
-    : NewFunc(newFunc), OldFunc(oldFunc), VMap(valueMap), Returns(returns),
-      NameSuffix(nameSuffix), CodeInfo(codeInfo), TD(td) {
+    : NewFunc(newFunc), OldFunc(oldFunc),
+      VMap(valueMap), ModuleLevelChanges(moduleLevelChanges),
+      Returns(returns), NameSuffix(nameSuffix), CodeInfo(codeInfo), TD(td) {
     }
 
     /// CloneBlock - The specified block is found to be reachable, clone it and
@@ -313,7 +318,7 @@ ConstantFoldMappedInstruction(const Instruction *I) {
   SmallVector<Constant*, 8> Ops;
   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
     if (Constant *Op = dyn_cast_or_null<Constant>(MapValue(I->getOperand(i),
-                                                           VMap)))
+                                                   VMap, ModuleLevelChanges)))
       Ops.push_back(Op);
     else
       return 0;  // All operands not constant!
@@ -355,6 +360,7 @@ UpdateInlinedAtInfo(const DebugLoc &InsnDL, const DebugLoc &TheCallDL,
 /// used for things like CloneFunction or CloneModule.
 void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
                                      ValueToValueMapTy &VMap,
+                                     bool ModuleLevelChanges,
                                      SmallVectorImpl<ReturnInst*> &Returns,
                                      const char *NameSuffix, 
                                      ClonedCodeInfo *CodeInfo,
@@ -368,8 +374,8 @@ void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
     assert(VMap.count(II) && "No mapping from source argument specified!");
 #endif
 
-  PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, Returns,
-                            NameSuffix, CodeInfo, TD);
+  PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
+                            Returns, NameSuffix, CodeInfo, TD);
 
   // Clone the entry block, and anything recursively reachable from it.
   std::vector<const BasicBlock*> CloneWorklist;
@@ -449,7 +455,7 @@ void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
           I->setDebugLoc(DebugLoc());
         }
       }
-      RemapInstruction(I, VMap);
+      RemapInstruction(I, VMap, ModuleLevelChanges);
     }
   }
   
@@ -471,7 +477,7 @@ void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
         if (BasicBlock *MappedBlock = 
             cast_or_null<BasicBlock>(VMap[PN->getIncomingBlock(pred)])) {
           Value *InVal = MapValue(PN->getIncomingValue(pred),
-                                  VMap);
+                                  VMap, ModuleLevelChanges);
           assert(InVal && "Unknown input value?");
           PN->setIncomingValue(pred, InVal);
           PN->setIncomingBlock(pred, MappedBlock);
diff --git a/llvm/lib/Transforms/Utils/CloneModule.cpp b/llvm/lib/Transforms/Utils/CloneModule.cpp
index 25083adb7ce..b347bf597f8 100644
--- a/llvm/lib/Transforms/Utils/CloneModule.cpp
+++ b/llvm/lib/Transforms/Utils/CloneModule.cpp
@@ -89,7 +89,8 @@ Module *llvm::CloneModule(const Module *M,
     GlobalVariable *GV = cast<GlobalVariable>(VMap[I]);
     if (I->hasInitializer())
       GV->setInitializer(cast<Constant>(MapValue(I->getInitializer(),
-                                                 VMap)));
+                                                 VMap,
+                                                 true)));
     GV->setLinkage(I->getLinkage());
     GV->setThreadLocal(I->isThreadLocal());
     GV->setConstant(I->isConstant());
@@ -108,7 +109,7 @@ Module *llvm::CloneModule(const Module *M,
       }
 
       SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
-      CloneFunctionInto(F, I, VMap, Returns);
+      CloneFunctionInto(F, I, VMap, /*ModuleLevelChanges=*/true, Returns);
     }
 
     F->setLinkage(I->getLinkage());
@@ -120,7 +121,7 @@ Module *llvm::CloneModule(const Module *M,
     GlobalAlias *GA = cast<GlobalAlias>(VMap[I]);
     GA->setLinkage(I->getLinkage());
     if (const Constant* C = I->getAliasee())
-      GA->setAliasee(cast<Constant>(MapValue(C, VMap)));
+      GA->setAliasee(cast<Constant>(MapValue(C, VMap, true)));
   }
 
   // And named metadata....
@@ -129,23 +130,8 @@ Module *llvm::CloneModule(const Module *M,
     const NamedMDNode &NMD = *I;
     NamedMDNode *NewNMD = New->getOrInsertNamedMetadata(NMD.getName());
     for (unsigned i = 0, e = NMD.getNumOperands(); i != e; ++i)
-      NewNMD->addOperand(cast<MDNode>(MapValue(NMD.getOperand(i), VMap)));
+      NewNMD->addOperand(cast<MDNode>(MapValue(NMD.getOperand(i), VMap, true)));
   }
 
-  // Update metadata attach with instructions.
-  for (Module::iterator MI = New->begin(), ME = New->end(); MI != ME; ++MI)   
-    for (Function::iterator FI = MI->begin(), FE = MI->end(); 
-         FI != FE; ++FI)
-      for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); 
-           BI != BE; ++BI) {
-        SmallVector<std::pair<unsigned, MDNode *>, 4 > MDs;
-        BI->getAllMetadata(MDs);
-        for (SmallVector<std::pair<unsigned, MDNode *>, 4>::iterator 
-               MDI = MDs.begin(), MDE = MDs.end(); MDI != MDE; ++MDI) {
-          Value *MappedValue = MapValue(MDI->second, VMap);
-          if (MDI->second != MappedValue && MappedValue)
-            BI->setMetadata(MDI->first, cast<MDNode>(MappedValue));
-        }
-      }
   return New;
 }
diff --git a/llvm/lib/Transforms/Utils/InlineFunction.cpp b/llvm/lib/Transforms/Utils/InlineFunction.cpp
index b7677b5a3c3..88979e862df 100644
--- a/llvm/lib/Transforms/Utils/InlineFunction.cpp
+++ b/llvm/lib/Transforms/Utils/InlineFunction.cpp
@@ -365,7 +365,8 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) {
     // have no dead or constant instructions leftover after inlining occurs
     // (which can happen, e.g., because an argument was constant), but we'll be
     // happy with whatever the cloner can do.
-    CloneAndPruneFunctionInto(Caller, CalledFunc, VMap, Returns, ".i",
+    CloneAndPruneFunctionInto(Caller, CalledFunc, VMap, 
+                              /*ModuleLevelChanges=*/false, Returns, ".i",
                               &InlinedFunctionInfo, IFI.TD, TheCall);
 
     // Remember the first block that is newly cloned over.
diff --git a/llvm/lib/Transforms/Utils/ValueMapper.cpp b/llvm/lib/Transforms/Utils/ValueMapper.cpp
index 20e7f79b87d..fc4bde77d4f 100644
--- a/llvm/lib/Transforms/Utils/ValueMapper.cpp
+++ b/llvm/lib/Transforms/Utils/ValueMapper.cpp
@@ -20,28 +20,51 @@
 #include "llvm/ADT/SmallVector.h"
 using namespace llvm;
 
-Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM) {
+Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM,
+                      bool ModuleLevelChanges) {
   Value *&VMSlot = VM[V];
   if (VMSlot) return VMSlot;      // Does it exist in the map yet?
   
   // NOTE: VMSlot can be invalidated by any reference to VM, which can grow the
   // DenseMap.  This includes any recursive calls to MapValue.
 
-  // Global values and non-function-local metadata do not need to be seeded into
-  // the VM if they are using the identity mapping.
+  // Global values do not need to be seeded into the VM if they
+  // are using the identity mapping.
   if (isa<GlobalValue>(V) || isa<InlineAsm>(V) || isa<MDString>(V) ||
-      (isa<MDNode>(V) && !cast<MDNode>(V)->isFunctionLocal()))
+      (isa<MDNode>(V) && !cast<MDNode>(V)->isFunctionLocal() &&
+       !ModuleLevelChanges))
     return VMSlot = const_cast<Value*>(V);
 
   if (const MDNode *MD = dyn_cast<MDNode>(V)) {
-    SmallVector<Value*, 4> Elts;
-    for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
-      Elts.push_back(MD->getOperand(i) ? MapValue(MD->getOperand(i), VM) : 0);
-    return VM[V] = MDNode::get(V->getContext(), Elts.data(), Elts.size());
+    // Start by assuming that we'll use the identity mapping.
+    VMSlot = const_cast<Value*>(V);
+
+    // Check all operands to see if any need to be remapped.
+    for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) {
+      Value *OP = MD->getOperand(i);
+      if (!OP || MapValue(OP, VM, ModuleLevelChanges) == OP) continue;
+
+      // Ok, at least one operand needs remapping.
+      MDNode *Dummy = MDNode::getTemporary(V->getContext(), 0, 0);
+      VM[V] = Dummy;
+      SmallVector<Value*, 4> Elts;
+      Elts.reserve(MD->getNumOperands());
+      for (i = 0; i != e; ++i)
+        Elts.push_back(MD->getOperand(i) ? 
+                       MapValue(MD->getOperand(i), VM, ModuleLevelChanges) : 0);
+      MDNode *NewMD = MDNode::get(V->getContext(), Elts.data(), Elts.size());
+      Dummy->replaceAllUsesWith(NewMD);
+      MDNode::deleteTemporary(Dummy);
+      return VM[V] = NewMD;
+    }
+
+    // No operands needed remapping; keep the identity map.
+    return const_cast<Value*>(V);
   }
 
   Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V));
-  if (C == 0) return 0;
+  if (C == 0)
+    return 0;
   
   if (isa<ConstantInt>(C) || isa<ConstantFP>(C) ||
       isa<ConstantPointerNull>(C) || isa<ConstantAggregateZero>(C) ||
@@ -51,7 +74,7 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM) {
   if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
     for (User::op_iterator b = CA->op_begin(), i = b, e = CA->op_end();
          i != e; ++i) {
-      Value *MV = MapValue(*i, VM);
+      Value *MV = MapValue(*i, VM, ModuleLevelChanges);
       if (MV != *i) {
         // This array must contain a reference to a global, make a new array
         // and return it.
@@ -62,7 +85,8 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM) {
           Values.push_back(cast<Constant>(*j));
         Values.push_back(cast<Constant>(MV));
         for (++i; i != e; ++i)
-          Values.push_back(cast<Constant>(MapValue(*i, VM)));
+          Values.push_back(cast<Constant>(MapValue(*i, VM,
+                                                   ModuleLevelChanges)));
         return VM[V] = ConstantArray::get(CA->getType(), Values);
       }
     }
@@ -72,7 +96,7 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM) {
   if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
     for (User::op_iterator b = CS->op_begin(), i = b, e = CS->op_end();
          i != e; ++i) {
-      Value *MV = MapValue(*i, VM);
+      Value *MV = MapValue(*i, VM, ModuleLevelChanges);
       if (MV != *i) {
         // This struct must contain a reference to a global, make a new struct
         // and return it.
@@ -83,7 +107,8 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM) {
           Values.push_back(cast<Constant>(*j));
         Values.push_back(cast<Constant>(MV));
         for (++i; i != e; ++i)
-          Values.push_back(cast<Constant>(MapValue(*i, VM)));
+          Values.push_back(cast<Constant>(MapValue(*i, VM,
+                                                   ModuleLevelChanges)));
         return VM[V] = ConstantStruct::get(CS->getType(), Values);
       }
     }
@@ -93,14 +118,14 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM) {
   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
     std::vector<Constant*> Ops;
     for (User::op_iterator i = CE->op_begin(), e = CE->op_end(); i != e; ++i)
-      Ops.push_back(cast<Constant>(MapValue(*i, VM)));
+      Ops.push_back(cast<Constant>(MapValue(*i, VM, ModuleLevelChanges)));
     return VM[V] = CE->getWithOperands(Ops);
   }
   
   if (ConstantVector *CV = dyn_cast<ConstantVector>(C)) {
     for (User::op_iterator b = CV->op_begin(), i = b, e = CV->op_end();
          i != e; ++i) {
-      Value *MV = MapValue(*i, VM);
+      Value *MV = MapValue(*i, VM, ModuleLevelChanges);
       if (MV != *i) {
         // This vector value must contain a reference to a global, make a new
         // vector constant and return it.
@@ -111,7 +136,8 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM) {
           Values.push_back(cast<Constant>(*j));
         Values.push_back(cast<Constant>(MV));
         for (++i; i != e; ++i)
-          Values.push_back(cast<Constant>(MapValue(*i, VM)));
+          Values.push_back(cast<Constant>(MapValue(*i, VM,
+                                                   ModuleLevelChanges)));
         return VM[V] = ConstantVector::get(Values);
       }
     }
@@ -119,19 +145,33 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM) {
   }
   
   BlockAddress *BA = cast<BlockAddress>(C);
-  Function *F = cast<Function>(MapValue(BA->getFunction(), VM));
-  BasicBlock *BB = cast_or_null<BasicBlock>(MapValue(BA->getBasicBlock(),VM));
+  Function *F = cast<Function>(MapValue(BA->getFunction(), VM,
+                                        ModuleLevelChanges));
+  BasicBlock *BB = cast_or_null<BasicBlock>(MapValue(BA->getBasicBlock(),VM,
+                                             ModuleLevelChanges));
   return VM[V] = BlockAddress::get(F, BB ? BB : BA->getBasicBlock());
 }
 
 /// RemapInstruction - Convert the instruction operands from referencing the
 /// current values into those specified by VMap.
 ///
-void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap) {
+void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap,
+                            bool ModuleLevelChanges) {
+  // Remap operands.
   for (User::op_iterator op = I->op_begin(), E = I->op_end(); op != E; ++op) {
-    Value *V = MapValue(*op, VMap);
+    Value *V = MapValue(*op, VMap, ModuleLevelChanges);
     assert(V && "Referenced value not in value map!");
     *op = V;
   }
-}
 
+  // Remap attached metadata.
+  SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
+  I->getAllMetadata(MDs);
+  for (SmallVectorImpl<std::pair<unsigned, MDNode *> >::iterator
+       MI = MDs.begin(), ME = MDs.end(); MI != ME; ++MI) {
+    Value *Old = MI->second;
+    Value *New = MapValue(Old, VMap, ModuleLevelChanges);
+    if (New != Old)
+      I->setMetadata(MI->first, cast<MDNode>(New));
+  }
+}