contrib/llvm/lib/Transforms/Utils/ValueMapper.cpp

   1 //===- ValueMapper.cpp - Interface shared by lib/Transforms/Utils ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the MapValue function, which is shared by various parts of
  11 // the lib/Transforms/Utils library.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Utils/ValueMapper.h"
  16 #include "llvm/ADT/ArrayRef.h"
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/DenseSet.h"
  19 #include "llvm/ADT/None.h"
  20 #include "llvm/ADT/Optional.h"
  21 #include "llvm/ADT/STLExtras.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/IR/Argument.h"
  24 #include "llvm/IR/BasicBlock.h"
  25 #include "llvm/IR/CallSite.h"
  26 #include "llvm/IR/Constant.h"
  27 #include "llvm/IR/Constants.h"
  28 #include "llvm/IR/DerivedTypes.h"
  29 #include "llvm/IR/Function.h"
  30 #include "llvm/IR/GlobalAlias.h"
  31 #include "llvm/IR/GlobalObject.h"
  32 #include "llvm/IR/GlobalVariable.h"
  33 #include "llvm/IR/InlineAsm.h"
  34 #include "llvm/IR/Instruction.h"
  35 #include "llvm/IR/Instructions.h"
  36 #include "llvm/IR/Metadata.h"
  37 #include "llvm/IR/Operator.h"
  38 #include "llvm/IR/Type.h"
  39 #include "llvm/IR/Value.h"
  40 #include "llvm/Support/Casting.h"
  41 #include <cassert>
  42 #include <limits>
  43 #include <memory>
  44 #include <utility>
  45
  46 using namespace llvm;
  47
  48 // Out of line method to get vtable etc for class.
  49 void ValueMapTypeRemapper::anchor() {}
  50 void ValueMaterializer::anchor() {}
  51
  52 namespace {
  53
  54 /// A basic block used in a BlockAddress whose function body is not yet
  55 /// materialized.
  56 struct DelayedBasicBlock {
  57   BasicBlock *OldBB;
  58   std::unique_ptr<BasicBlock> TempBB;
  59
  60   DelayedBasicBlock(const BlockAddress &Old)
  61       : OldBB(Old.getBasicBlock()),
  62         TempBB(BasicBlock::Create(Old.getContext())) {}
  63 };
  64
  65 struct WorklistEntry {
  66   enum EntryKind {
  67     MapGlobalInit,
  68     MapAppendingVar,
  69     MapGlobalAliasee,
  70     RemapFunction
  71   };
  72   struct GVInitTy {
  73     GlobalVariable *GV;
  74     Constant *Init;
  75   };
  76   struct AppendingGVTy {
  77     GlobalVariable *GV;
  78     Constant *InitPrefix;
  79   };
  80   struct GlobalAliaseeTy {
  81     GlobalAlias *GA;
  82     Constant *Aliasee;
  83   };
  84
  85   unsigned Kind : 2;
  86   unsigned MCID : 29;
  87   unsigned AppendingGVIsOldCtorDtor : 1;
  88   unsigned AppendingGVNumNewMembers;
  89   union {
  90     GVInitTy GVInit;
  91     AppendingGVTy AppendingGV;
  92     GlobalAliaseeTy GlobalAliasee;
  93     Function *RemapF;
  94   } Data;
  95 };
  96
  97 struct MappingContext {
  98   ValueToValueMapTy *VM;
  99   ValueMaterializer *Materializer = nullptr;
 100
 101   /// Construct a MappingContext with a value map and materializer.
 102   explicit MappingContext(ValueToValueMapTy &VM,
 103                           ValueMaterializer *Materializer = nullptr)
 104       : VM(&VM), Materializer(Materializer) {}
 105 };
 106
 107 class Mapper {
 108   friend class MDNodeMapper;
 109
 110 #ifndef NDEBUG
 111   DenseSet<GlobalValue *> AlreadyScheduled;
 112 #endif
 113
 114   RemapFlags Flags;
 115   ValueMapTypeRemapper *TypeMapper;
 116   unsigned CurrentMCID = 0;
 117   SmallVector<MappingContext, 2> MCs;
 118   SmallVector<WorklistEntry, 4> Worklist;
 119   SmallVector<DelayedBasicBlock, 1> DelayedBBs;
 120   SmallVector<Constant *, 16> AppendingInits;
 121
 122 public:
 123   Mapper(ValueToValueMapTy &VM, RemapFlags Flags,
 124          ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer)
 125       : Flags(Flags), TypeMapper(TypeMapper),
 126         MCs(1, MappingContext(VM, Materializer)) {}
 127
 128   /// ValueMapper should explicitly call \a flush() before destruction.
 129   ~Mapper() { assert(!hasWorkToDo() && "Expected to be flushed"); }
 130
 131   bool hasWorkToDo() const { return !Worklist.empty(); }
 132
 133   unsigned
 134   registerAlternateMappingContext(ValueToValueMapTy &VM,
 135                                   ValueMaterializer *Materializer = nullptr) {
 136     MCs.push_back(MappingContext(VM, Materializer));
 137     return MCs.size() - 1;
 138   }
 139
 140   void addFlags(RemapFlags Flags);
 141
 142   void remapGlobalObjectMetadata(GlobalObject &GO);
 143
 144   Value *mapValue(const Value *V);
 145   void remapInstruction(Instruction *I);
 146   void remapFunction(Function &F);
 147
 148   Constant *mapConstant(const Constant *C) {
 149     return cast_or_null<Constant>(mapValue(C));
 150   }
 151
 152   /// Map metadata.
 153   ///
 154   /// Find the mapping for MD.  Guarantees that the return will be resolved
 155   /// (not an MDNode, or MDNode::isResolved() returns true).
 156   Metadata *mapMetadata(const Metadata *MD);
 157
 158   void scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
 159                                     unsigned MCID);
 160   void scheduleMapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
 161                                     bool IsOldCtorDtor,
 162                                     ArrayRef<Constant *> NewMembers,
 163                                     unsigned MCID);
 164   void scheduleMapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee,
 165                                 unsigned MCID);
 166   void scheduleRemapFunction(Function &F, unsigned MCID);
 167
 168   void flush();
 169
 170 private:
 171   void mapGlobalInitializer(GlobalVariable &GV, Constant &Init);
 172   void mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
 173                             bool IsOldCtorDtor,
 174                             ArrayRef<Constant *> NewMembers);
 175   void mapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee);
 176   void remapFunction(Function &F, ValueToValueMapTy &VM);
 177
 178   ValueToValueMapTy &getVM() { return *MCs[CurrentMCID].VM; }
 179   ValueMaterializer *getMaterializer() { return MCs[CurrentMCID].Materializer; }
 180
 181   Value *mapBlockAddress(const BlockAddress &BA);
 182
 183   /// Map metadata that doesn't require visiting operands.
 184   Optional<Metadata *> mapSimpleMetadata(const Metadata *MD);
 185
 186   Metadata *mapToMetadata(const Metadata *Key, Metadata *Val);
 187   Metadata *mapToSelf(const Metadata *MD);
 188 };
 189
 190 class MDNodeMapper {
 191   Mapper &M;
 192
 193   /// Data about a node in \a UniquedGraph.
 194   struct Data {
 195     bool HasChanged = false;
 196     unsigned ID = std::numeric_limits<unsigned>::max();
 197     TempMDNode Placeholder;
 198   };
 199
 200   /// A graph of uniqued nodes.
 201   struct UniquedGraph {
 202     SmallDenseMap<const Metadata *, Data, 32> Info; // Node properties.
 203     SmallVector<MDNode *, 16> POT;                  // Post-order traversal.
 204
 205     /// Propagate changed operands through the post-order traversal.
 206     ///
 207     /// Iteratively update \a Data::HasChanged for each node based on \a
 208     /// Data::HasChanged of its operands, until fixed point.
 209     void propagateChanges();
 210
 211     /// Get a forward reference to a node to use as an operand.
 212     Metadata &getFwdReference(MDNode &Op);
 213   };
 214
 215   /// Worklist of distinct nodes whose operands need to be remapped.
 216   SmallVector<MDNode *, 16> DistinctWorklist;
 217
 218   // Storage for a UniquedGraph.
 219   SmallDenseMap<const Metadata *, Data, 32> InfoStorage;
 220   SmallVector<MDNode *, 16> POTStorage;
 221
 222 public:
 223   MDNodeMapper(Mapper &M) : M(M) {}
 224
 225   /// Map a metadata node (and its transitive operands).
 226   ///
 227   /// Map all the (unmapped) nodes in the subgraph under \c N.  The iterative
 228   /// algorithm handles distinct nodes and uniqued node subgraphs using
 229   /// different strategies.
 230   ///
 231   /// Distinct nodes are immediately mapped and added to \a DistinctWorklist
 232   /// using \a mapDistinctNode().  Their mapping can always be computed
 233   /// immediately without visiting operands, even if their operands change.
 234   ///
 235   /// The mapping for uniqued nodes depends on whether their operands change.
 236   /// \a mapTopLevelUniquedNode() traverses the transitive uniqued subgraph of
 237   /// a node to calculate uniqued node mappings in bulk.  Distinct leafs are
 238   /// added to \a DistinctWorklist with \a mapDistinctNode().
 239   ///
 240   /// After mapping \c N itself, this function remaps the operands of the
 241   /// distinct nodes in \a DistinctWorklist until the entire subgraph under \c
 242   /// N has been mapped.
 243   Metadata *map(const MDNode &N);
 244
 245 private:
 246   /// Map a top-level uniqued node and the uniqued subgraph underneath it.
 247   ///
 248   /// This builds up a post-order traversal of the (unmapped) uniqued subgraph
 249   /// underneath \c FirstN and calculates the nodes' mapping.  Each node uses
 250   /// the identity mapping (\a Mapper::mapToSelf()) as long as all of its
 251   /// operands uses the identity mapping.
 252   ///
 253   /// The algorithm works as follows:
 254   ///
 255   ///  1. \a createPOT(): traverse the uniqued subgraph under \c FirstN and
 256   ///     save the post-order traversal in the given \a UniquedGraph, tracking
 257   ///     nodes' operands change.
 258   ///
 259   ///  2. \a UniquedGraph::propagateChanges(): propagate changed operands
 260   ///     through the \a UniquedGraph until fixed point, following the rule
 261   ///     that if a node changes, any node that references must also change.
 262   ///
 263   ///  3. \a mapNodesInPOT(): map the uniqued nodes, creating new uniqued nodes
 264   ///     (referencing new operands) where necessary.
 265   Metadata *mapTopLevelUniquedNode(const MDNode &FirstN);
 266
 267   /// Try to map the operand of an \a MDNode.
 268   ///
 269   /// If \c Op is already mapped, return the mapping.  If it's not an \a
 270   /// MDNode, compute and return the mapping.  If it's a distinct \a MDNode,
 271   /// return the result of \a mapDistinctNode().
 272   ///
 273   /// \return None if \c Op is an unmapped uniqued \a MDNode.
 274   /// \post getMappedOp(Op) only returns None if this returns None.
 275   Optional<Metadata *> tryToMapOperand(const Metadata *Op);
 276
 277   /// Map a distinct node.
 278   ///
 279   /// Return the mapping for the distinct node \c N, saving the result in \a
 280   /// DistinctWorklist for later remapping.
 281   ///
 282   /// \pre \c N is not yet mapped.
 283   /// \pre \c N.isDistinct().
 284   MDNode *mapDistinctNode(const MDNode &N);
 285
 286   /// Get a previously mapped node.
 287   Optional<Metadata *> getMappedOp(const Metadata *Op) const;
 288
 289   /// Create a post-order traversal of an unmapped uniqued node subgraph.
 290   ///
 291   /// This traverses the metadata graph deeply enough to map \c FirstN.  It
 292   /// uses \a tryToMapOperand() (via \a Mapper::mapSimplifiedNode()), so any
 293   /// metadata that has already been mapped will not be part of the POT.
 294   ///
 295   /// Each node that has a changed operand from outside the graph (e.g., a
 296   /// distinct node, an already-mapped uniqued node, or \a ConstantAsMetadata)
 297   /// is marked with \a Data::HasChanged.
 298   ///
 299   /// \return \c true if any nodes in \c G have \a Data::HasChanged.
 300   /// \post \c G.POT is a post-order traversal ending with \c FirstN.
 301   /// \post \a Data::hasChanged in \c G.Info indicates whether any node needs
 302   /// to change because of operands outside the graph.
 303   bool createPOT(UniquedGraph &G, const MDNode &FirstN);
 304
 305   /// Visit the operands of a uniqued node in the POT.
 306   ///
 307   /// Visit the operands in the range from \c I to \c E, returning the first
 308   /// uniqued node we find that isn't yet in \c G.  \c I is always advanced to
 309   /// where to continue the loop through the operands.
 310   ///
 311   /// This sets \c HasChanged if any of the visited operands change.
 312   MDNode *visitOperands(UniquedGraph &G, MDNode::op_iterator &I,
 313                         MDNode::op_iterator E, bool &HasChanged);
 314
 315   /// Map all the nodes in the given uniqued graph.
 316   ///
 317   /// This visits all the nodes in \c G in post-order, using the identity
 318   /// mapping or creating a new node depending on \a Data::HasChanged.
 319   ///
 320   /// \pre \a getMappedOp() returns None for nodes in \c G, but not for any of
 321   /// their operands outside of \c G.
 322   /// \pre \a Data::HasChanged is true for a node in \c G iff any of its
 323   /// operands have changed.
 324   /// \post \a getMappedOp() returns the mapped node for every node in \c G.
 325   void mapNodesInPOT(UniquedGraph &G);
 326
 327   /// Remap a node's operands using the given functor.
 328   ///
 329   /// Iterate through the operands of \c N and update them in place using \c
 330   /// mapOperand.
 331   ///
 332   /// \pre N.isDistinct() or N.isTemporary().
 333   template <class OperandMapper>
 334   void remapOperands(MDNode &N, OperandMapper mapOperand);
 335 };
 336
 337 } // end anonymous namespace
 338
 339 Value *Mapper::mapValue(const Value *V) {
 340   ValueToValueMapTy::iterator I = getVM().find(V);
 341
 342   // If the value already exists in the map, use it.
 343   if (I != getVM().end()) {
 344     assert(I->second && "Unexpected null mapping");
 345     return I->second;
 346   }
 347
 348   // If we have a materializer and it can materialize a value, use that.
 349   if (auto *Materializer = getMaterializer()) {
 350     if (Value *NewV = Materializer->materialize(const_cast<Value *>(V))) {
 351       getVM()[V] = NewV;
 352       return NewV;
 353     }
 354   }
 355
 356   // Global values do not need to be seeded into the VM if they
 357   // are using the identity mapping.
 358   if (isa<GlobalValue>(V)) {
 359     if (Flags & RF_NullMapMissingGlobalValues)
 360       return nullptr;
 361     return getVM()[V] = const_cast<Value *>(V);
 362   }
 363
 364   if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
 365     // Inline asm may need *type* remapping.
 366     FunctionType *NewTy = IA->getFunctionType();
 367     if (TypeMapper) {
 368       NewTy = cast<FunctionType>(TypeMapper->remapType(NewTy));
 369
 370       if (NewTy != IA->getFunctionType())
 371         V = InlineAsm::get(NewTy, IA->getAsmString(), IA->getConstraintString(),
 372                            IA->hasSideEffects(), IA->isAlignStack());
 373     }
 374
 375     return getVM()[V] = const_cast<Value *>(V);
 376   }
 377
 378   if (const auto *MDV = dyn_cast<MetadataAsValue>(V)) {
 379     const Metadata *MD = MDV->getMetadata();
 380
 381     if (auto *LAM = dyn_cast<LocalAsMetadata>(MD)) {
 382       // Look through to grab the local value.
 383       if (Value *LV = mapValue(LAM->getValue())) {
 384         if (V == LAM->getValue())
 385           return const_cast<Value *>(V);
 386         return MetadataAsValue::get(V->getContext(), ValueAsMetadata::get(LV));
 387       }
 388
 389       // FIXME: always return nullptr once Verifier::verifyDominatesUse()
 390       // ensures metadata operands only reference defined SSA values.
 391       return (Flags & RF_IgnoreMissingLocals)
 392                  ? nullptr
 393                  : MetadataAsValue::get(V->getContext(),
 394                                         MDTuple::get(V->getContext(), None));
 395     }
 396
 397     // If this is a module-level metadata and we know that nothing at the module
 398     // level is changing, then use an identity mapping.
 399     if (Flags & RF_NoModuleLevelChanges)
 400       return getVM()[V] = const_cast<Value *>(V);
 401
 402     // Map the metadata and turn it into a value.
 403     auto *MappedMD = mapMetadata(MD);
 404     if (MD == MappedMD)
 405       return getVM()[V] = const_cast<Value *>(V);
 406     return getVM()[V] = MetadataAsValue::get(V->getContext(), MappedMD);
 407   }
 408
 409   // Okay, this either must be a constant (which may or may not be mappable) or
 410   // is something that is not in the mapping table.
 411   Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V));
 412   if (!C)
 413     return nullptr;
 414
 415   if (BlockAddress *BA = dyn_cast<BlockAddress>(C))
 416     return mapBlockAddress(*BA);
 417
 418   auto mapValueOrNull = [this](Value *V) {
 419     auto Mapped = mapValue(V);
 420     assert((Mapped || (Flags & RF_NullMapMissingGlobalValues)) &&
 421            "Unexpected null mapping for constant operand without "
 422            "NullMapMissingGlobalValues flag");
 423     return Mapped;
 424   };
 425
 426   // Otherwise, we have some other constant to remap.  Start by checking to see
 427   // if all operands have an identity remapping.
 428   unsigned OpNo = 0, NumOperands = C->getNumOperands();
 429   Value *Mapped = nullptr;
 430   for (; OpNo != NumOperands; ++OpNo) {
 431     Value *Op = C->getOperand(OpNo);
 432     Mapped = mapValueOrNull(Op);
 433     if (!Mapped)
 434       return nullptr;
 435     if (Mapped != Op)
 436       break;
 437   }
 438
 439   // See if the type mapper wants to remap the type as well.
 440   Type *NewTy = C->getType();
 441   if (TypeMapper)
 442     NewTy = TypeMapper->remapType(NewTy);
 443
 444   // If the result type and all operands match up, then just insert an identity
 445   // mapping.
 446   if (OpNo == NumOperands && NewTy == C->getType())
 447     return getVM()[V] = C;
 448
 449   // Okay, we need to create a new constant.  We've already processed some or
 450   // all of the operands, set them all up now.
 451   SmallVector<Constant*, 8> Ops;
 452   Ops.reserve(NumOperands);
 453   for (unsigned j = 0; j != OpNo; ++j)
 454     Ops.push_back(cast<Constant>(C->getOperand(j)));
 455
 456   // If one of the operands mismatch, push it and the other mapped operands.
 457   if (OpNo != NumOperands) {
 458     Ops.push_back(cast<Constant>(Mapped));
 459
 460     // Map the rest of the operands that aren't processed yet.
 461     for (++OpNo; OpNo != NumOperands; ++OpNo) {
 462       Mapped = mapValueOrNull(C->getOperand(OpNo));
 463       if (!Mapped)
 464         return nullptr;
 465       Ops.push_back(cast<Constant>(Mapped));
 466     }
 467   }
 468   Type *NewSrcTy = nullptr;
 469   if (TypeMapper)
 470     if (auto *GEPO = dyn_cast<GEPOperator>(C))
 471       NewSrcTy = TypeMapper->remapType(GEPO->getSourceElementType());
 472
 473   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
 474     return getVM()[V] = CE->getWithOperands(Ops, NewTy, false, NewSrcTy);
 475   if (isa<ConstantArray>(C))
 476     return getVM()[V] = ConstantArray::get(cast<ArrayType>(NewTy), Ops);
 477   if (isa<ConstantStruct>(C))
 478     return getVM()[V] = ConstantStruct::get(cast<StructType>(NewTy), Ops);
 479   if (isa<ConstantVector>(C))
 480     return getVM()[V] = ConstantVector::get(Ops);
 481   // If this is a no-operand constant, it must be because the type was remapped.
 482   if (isa<UndefValue>(C))
 483     return getVM()[V] = UndefValue::get(NewTy);
 484   if (isa<ConstantAggregateZero>(C))
 485     return getVM()[V] = ConstantAggregateZero::get(NewTy);
 486   assert(isa<ConstantPointerNull>(C));
 487   return getVM()[V] = ConstantPointerNull::get(cast<PointerType>(NewTy));
 488 }
 489
 490 Value *Mapper::mapBlockAddress(const BlockAddress &BA) {
 491   Function *F = cast<Function>(mapValue(BA.getFunction()));
 492
 493   // F may not have materialized its initializer.  In that case, create a
 494   // dummy basic block for now, and replace it once we've materialized all
 495   // the initializers.
 496   BasicBlock *BB;
 497   if (F->empty()) {
 498     DelayedBBs.push_back(DelayedBasicBlock(BA));
 499     BB = DelayedBBs.back().TempBB.get();
 500   } else {
 501     BB = cast_or_null<BasicBlock>(mapValue(BA.getBasicBlock()));
 502   }
 503
 504   return getVM()[&BA] = BlockAddress::get(F, BB ? BB : BA.getBasicBlock());
 505 }
 506
 507 Metadata *Mapper::mapToMetadata(const Metadata *Key, Metadata *Val) {
 508   getVM().MD()[Key].reset(Val);
 509   return Val;
 510 }
 511
 512 Metadata *Mapper::mapToSelf(const Metadata *MD) {
 513   return mapToMetadata(MD, const_cast<Metadata *>(MD));
 514 }
 515
 516 Optional<Metadata *> MDNodeMapper::tryToMapOperand(const Metadata *Op) {
 517   if (!Op)
 518     return nullptr;
 519
 520   if (Optional<Metadata *> MappedOp = M.mapSimpleMetadata(Op)) {
 521 #ifndef NDEBUG
 522     if (auto *CMD = dyn_cast<ConstantAsMetadata>(Op))
 523       assert((!*MappedOp || M.getVM().count(CMD->getValue()) ||
 524               M.getVM().getMappedMD(Op)) &&
 525              "Expected Value to be memoized");
 526     else
 527       assert((isa<MDString>(Op) || M.getVM().getMappedMD(Op)) &&
 528              "Expected result to be memoized");
 529 #endif
 530     return *MappedOp;
 531   }
 532
 533   const MDNode &N = *cast<MDNode>(Op);
 534   if (N.isDistinct())
 535     return mapDistinctNode(N);
 536   return None;
 537 }
 538
 539 MDNode *MDNodeMapper::mapDistinctNode(const MDNode &N) {
 540   assert(N.isDistinct() && "Expected a distinct node");
 541   assert(!M.getVM().getMappedMD(&N) && "Expected an unmapped node");
 542   DistinctWorklist.push_back(cast<MDNode>(
 543       (M.Flags & RF_MoveDistinctMDs)
 544           ? M.mapToSelf(&N)
 545           : M.mapToMetadata(&N, MDNode::replaceWithDistinct(N.clone()))));
 546   return DistinctWorklist.back();
 547 }
 548
 549 static ConstantAsMetadata *wrapConstantAsMetadata(const ConstantAsMetadata &CMD,
 550                                                   Value *MappedV) {
 551   if (CMD.getValue() == MappedV)
 552     return const_cast<ConstantAsMetadata *>(&CMD);
 553   return MappedV ? ConstantAsMetadata::getConstant(MappedV) : nullptr;
 554 }
 555
 556 Optional<Metadata *> MDNodeMapper::getMappedOp(const Metadata *Op) const {
 557   if (!Op)
 558     return nullptr;
 559
 560   if (Optional<Metadata *> MappedOp = M.getVM().getMappedMD(Op))
 561     return *MappedOp;
 562
 563   if (isa<MDString>(Op))
 564     return const_cast<Metadata *>(Op);
 565
 566   if (auto *CMD = dyn_cast<ConstantAsMetadata>(Op))
 567     return wrapConstantAsMetadata(*CMD, M.getVM().lookup(CMD->getValue()));
 568
 569   return None;
 570 }
 571
 572 Metadata &MDNodeMapper::UniquedGraph::getFwdReference(MDNode &Op) {
 573   auto Where = Info.find(&Op);
 574   assert(Where != Info.end() && "Expected a valid reference");
 575
 576   auto &OpD = Where->second;
 577   if (!OpD.HasChanged)
 578     return Op;
 579
 580   // Lazily construct a temporary node.
 581   if (!OpD.Placeholder)
 582     OpD.Placeholder = Op.clone();
 583
 584   return *OpD.Placeholder;
 585 }
 586
 587 template <class OperandMapper>
 588 void MDNodeMapper::remapOperands(MDNode &N, OperandMapper mapOperand) {
 589   assert(!N.isUniqued() && "Expected distinct or temporary nodes");
 590   for (unsigned I = 0, E = N.getNumOperands(); I != E; ++I) {
 591     Metadata *Old = N.getOperand(I);
 592     Metadata *New = mapOperand(Old);
 593
 594     if (Old != New)
 595       N.replaceOperandWith(I, New);
 596   }
 597 }
 598
 599 namespace {
 600
 601 /// An entry in the worklist for the post-order traversal.
 602 struct POTWorklistEntry {
 603   MDNode *N;              ///< Current node.
 604   MDNode::op_iterator Op; ///< Current operand of \c N.
 605
 606   /// Keep a flag of whether operands have changed in the worklist to avoid
 607   /// hitting the map in \a UniquedGraph.
 608   bool HasChanged = false;
 609
 610   POTWorklistEntry(MDNode &N) : N(&N), Op(N.op_begin()) {}
 611 };
 612
 613 } // end anonymous namespace
 614
 615 bool MDNodeMapper::createPOT(UniquedGraph &G, const MDNode &FirstN) {
 616   assert(G.Info.empty() && "Expected a fresh traversal");
 617   assert(FirstN.isUniqued() && "Expected uniqued node in POT");
 618
 619   // Construct a post-order traversal of the uniqued subgraph under FirstN.
 620   bool AnyChanges = false;
 621   SmallVector<POTWorklistEntry, 16> Worklist;
 622   Worklist.push_back(POTWorklistEntry(const_cast<MDNode &>(FirstN)));
 623   (void)G.Info[&FirstN];
 624   while (!Worklist.empty()) {
 625     // Start or continue the traversal through the this node's operands.
 626     auto &WE = Worklist.back();
 627     if (MDNode *N = visitOperands(G, WE.Op, WE.N->op_end(), WE.HasChanged)) {
 628       // Push a new node to traverse first.
 629       Worklist.push_back(POTWorklistEntry(*N));
 630       continue;
 631     }
 632
 633     // Push the node onto the POT.
 634     assert(WE.N->isUniqued() && "Expected only uniqued nodes");
 635     assert(WE.Op == WE.N->op_end() && "Expected to visit all operands");
 636     auto &D = G.Info[WE.N];
 637     AnyChanges |= D.HasChanged = WE.HasChanged;
 638     D.ID = G.POT.size();
 639     G.POT.push_back(WE.N);
 640
 641     // Pop the node off the worklist.
 642     Worklist.pop_back();
 643   }
 644   return AnyChanges;
 645 }
 646
 647 MDNode *MDNodeMapper::visitOperands(UniquedGraph &G, MDNode::op_iterator &I,
 648                                     MDNode::op_iterator E, bool &HasChanged) {
 649   while (I != E) {
 650     Metadata *Op = *I++; // Increment even on early return.
 651     if (Optional<Metadata *> MappedOp = tryToMapOperand(Op)) {
 652       // Check if the operand changes.
 653       HasChanged |= Op != *MappedOp;
 654       continue;
 655     }
 656
 657     // A uniqued metadata node.
 658     MDNode &OpN = *cast<MDNode>(Op);
 659     assert(OpN.isUniqued() &&
 660            "Only uniqued operands cannot be mapped immediately");
 661     if (G.Info.insert(std::make_pair(&OpN, Data())).second)
 662       return &OpN; // This is a new one.  Return it.
 663   }
 664   return nullptr;
 665 }
 666
 667 void MDNodeMapper::UniquedGraph::propagateChanges() {
 668   bool AnyChanges;
 669   do {
 670     AnyChanges = false;
 671     for (MDNode *N : POT) {
 672       auto &D = Info[N];
 673       if (D.HasChanged)
 674         continue;
 675
 676       if (llvm::none_of(N->operands(), [&](const Metadata *Op) {
 677             auto Where = Info.find(Op);
 678             return Where != Info.end() && Where->second.HasChanged;
 679           }))
 680         continue;
 681
 682       AnyChanges = D.HasChanged = true;
 683     }
 684   } while (AnyChanges);
 685 }
 686
 687 void MDNodeMapper::mapNodesInPOT(UniquedGraph &G) {
 688   // Construct uniqued nodes, building forward references as necessary.
 689   SmallVector<MDNode *, 16> CyclicNodes;
 690   for (auto *N : G.POT) {
 691     auto &D = G.Info[N];
 692     if (!D.HasChanged) {
 693       // The node hasn't changed.
 694       M.mapToSelf(N);
 695       continue;
 696     }
 697
 698     // Remember whether this node had a placeholder.
 699     bool HadPlaceholder(D.Placeholder);
 700
 701     // Clone the uniqued node and remap the operands.
 702     TempMDNode ClonedN = D.Placeholder ? std::move(D.Placeholder) : N->clone();
 703     remapOperands(*ClonedN, [this, &D, &G](Metadata *Old) {
 704       if (Optional<Metadata *> MappedOp = getMappedOp(Old))
 705         return *MappedOp;
 706       (void)D;
 707       assert(G.Info[Old].ID > D.ID && "Expected a forward reference");
 708       return &G.getFwdReference(*cast<MDNode>(Old));
 709     });
 710
 711     auto *NewN = MDNode::replaceWithUniqued(std::move(ClonedN));
 712     M.mapToMetadata(N, NewN);
 713
 714     // Nodes that were referenced out of order in the POT are involved in a
 715     // uniquing cycle.
 716     if (HadPlaceholder)
 717       CyclicNodes.push_back(NewN);
 718   }
 719
 720   // Resolve cycles.
 721   for (auto *N : CyclicNodes)
 722     if (!N->isResolved())
 723       N->resolveCycles();
 724 }
 725
 726 Metadata *MDNodeMapper::map(const MDNode &N) {
 727   assert(DistinctWorklist.empty() && "MDNodeMapper::map is not recursive");
 728   assert(!(M.Flags & RF_NoModuleLevelChanges) &&
 729          "MDNodeMapper::map assumes module-level changes");
 730
 731   // Require resolved nodes whenever metadata might be remapped.
 732   assert(N.isResolved() && "Unexpected unresolved node");
 733
 734   Metadata *MappedN =
 735       N.isUniqued() ? mapTopLevelUniquedNode(N) : mapDistinctNode(N);
 736   while (!DistinctWorklist.empty())
 737     remapOperands(*DistinctWorklist.pop_back_val(), [this](Metadata *Old) {
 738       if (Optional<Metadata *> MappedOp = tryToMapOperand(Old))
 739         return *MappedOp;
 740       return mapTopLevelUniquedNode(*cast<MDNode>(Old));
 741     });
 742   return MappedN;
 743 }
 744
 745 Metadata *MDNodeMapper::mapTopLevelUniquedNode(const MDNode &FirstN) {
 746   assert(FirstN.isUniqued() && "Expected uniqued node");
 747
 748   // Create a post-order traversal of uniqued nodes under FirstN.
 749   UniquedGraph G;
 750   if (!createPOT(G, FirstN)) {
 751     // Return early if no nodes have changed.
 752     for (const MDNode *N : G.POT)
 753       M.mapToSelf(N);
 754     return &const_cast<MDNode &>(FirstN);
 755   }
 756
 757   // Update graph with all nodes that have changed.
 758   G.propagateChanges();
 759
 760   // Map all the nodes in the graph.
 761   mapNodesInPOT(G);
 762
 763   // Return the original node, remapped.
 764   return *getMappedOp(&FirstN);
 765 }
 766
 767 namespace {
 768
 769 struct MapMetadataDisabler {
 770   ValueToValueMapTy &VM;
 771
 772   MapMetadataDisabler(ValueToValueMapTy &VM) : VM(VM) {
 773     VM.disableMapMetadata();
 774   }
 775
 776   ~MapMetadataDisabler() { VM.enableMapMetadata(); }
 777 };
 778
 779 } // end anonymous namespace
 780
 781 Optional<Metadata *> Mapper::mapSimpleMetadata(const Metadata *MD) {
 782   // If the value already exists in the map, use it.
 783   if (Optional<Metadata *> NewMD = getVM().getMappedMD(MD))
 784     return *NewMD;
 785
 786   if (isa<MDString>(MD))
 787     return const_cast<Metadata *>(MD);
 788
 789   // This is a module-level metadata.  If nothing at the module level is
 790   // changing, use an identity mapping.
 791   if ((Flags & RF_NoModuleLevelChanges))
 792     return const_cast<Metadata *>(MD);
 793
 794   if (auto *CMD = dyn_cast<ConstantAsMetadata>(MD)) {
 795     // Disallow recursion into metadata mapping through mapValue.
 796     MapMetadataDisabler MMD(getVM());
 797
 798     // Don't memoize ConstantAsMetadata.  Instead of lasting until the
 799     // LLVMContext is destroyed, they can be deleted when the GlobalValue they
 800     // reference is destructed.  These aren't super common, so the extra
 801     // indirection isn't that expensive.
 802     return wrapConstantAsMetadata(*CMD, mapValue(CMD->getValue()));
 803   }
 804
 805   assert(isa<MDNode>(MD) && "Expected a metadata node");
 806
 807   return None;
 808 }
 809
 810 Metadata *Mapper::mapMetadata(const Metadata *MD) {
 811   assert(MD && "Expected valid metadata");
 812   assert(!isa<LocalAsMetadata>(MD) && "Unexpected local metadata");
 813
 814   if (Optional<Metadata *> NewMD = mapSimpleMetadata(MD))
 815     return *NewMD;
 816
 817   return MDNodeMapper(*this).map(*cast<MDNode>(MD));
 818 }
 819
 820 void Mapper::flush() {
 821   // Flush out the worklist of global values.
 822   while (!Worklist.empty()) {
 823     WorklistEntry E = Worklist.pop_back_val();
 824     CurrentMCID = E.MCID;
 825     switch (E.Kind) {
 826     case WorklistEntry::MapGlobalInit:
 827       E.Data.GVInit.GV->setInitializer(mapConstant(E.Data.GVInit.Init));
 828       remapGlobalObjectMetadata(*E.Data.GVInit.GV);
 829       break;
 830     case WorklistEntry::MapAppendingVar: {
 831       unsigned PrefixSize = AppendingInits.size() - E.AppendingGVNumNewMembers;
 832       mapAppendingVariable(*E.Data.AppendingGV.GV,
 833                            E.Data.AppendingGV.InitPrefix,
 834                            E.AppendingGVIsOldCtorDtor,
 835                            makeArrayRef(AppendingInits).slice(PrefixSize));
 836       AppendingInits.resize(PrefixSize);
 837       break;
 838     }
 839     case WorklistEntry::MapGlobalAliasee:
 840       E.Data.GlobalAliasee.GA->setAliasee(
 841           mapConstant(E.Data.GlobalAliasee.Aliasee));
 842       break;
 843     case WorklistEntry::RemapFunction:
 844       remapFunction(*E.Data.RemapF);
 845       break;
 846     }
 847   }
 848   CurrentMCID = 0;
 849
 850   // Finish logic for block addresses now that all global values have been
 851   // handled.
 852   while (!DelayedBBs.empty()) {
 853     DelayedBasicBlock DBB = DelayedBBs.pop_back_val();
 854     BasicBlock *BB = cast_or_null<BasicBlock>(mapValue(DBB.OldBB));
 855     DBB.TempBB->replaceAllUsesWith(BB ? BB : DBB.OldBB);
 856   }
 857 }
 858
 859 void Mapper::remapInstruction(Instruction *I) {
 860   // Remap operands.
 861   for (Use &Op : I->operands()) {
 862     Value *V = mapValue(Op);
 863     // If we aren't ignoring missing entries, assert that something happened.
 864     if (V)
 865       Op = V;
 866     else
 867       assert((Flags & RF_IgnoreMissingLocals) &&
 868              "Referenced value not in value map!");
 869   }
 870
 871   // Remap phi nodes' incoming blocks.
 872   if (PHINode *PN = dyn_cast<PHINode>(I)) {
 873     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 874       Value *V = mapValue(PN->getIncomingBlock(i));
 875       // If we aren't ignoring missing entries, assert that something happened.
 876       if (V)
 877         PN->setIncomingBlock(i, cast<BasicBlock>(V));
 878       else
 879         assert((Flags & RF_IgnoreMissingLocals) &&
 880                "Referenced block not in value map!");
 881     }
 882   }
 883
 884   // Remap attached metadata.
 885   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
 886   I->getAllMetadata(MDs);
 887   for (const auto &MI : MDs) {
 888     MDNode *Old = MI.second;
 889     MDNode *New = cast_or_null<MDNode>(mapMetadata(Old));
 890     if (New != Old)
 891       I->setMetadata(MI.first, New);
 892   }
 893
 894   if (!TypeMapper)
 895     return;
 896
 897   // If the instruction's type is being remapped, do so now.
 898   if (auto CS = CallSite(I)) {
 899     SmallVector<Type *, 3> Tys;
 900     FunctionType *FTy = CS.getFunctionType();
 901     Tys.reserve(FTy->getNumParams());
 902     for (Type *Ty : FTy->params())
 903       Tys.push_back(TypeMapper->remapType(Ty));
 904     CS.mutateFunctionType(FunctionType::get(
 905         TypeMapper->remapType(I->getType()), Tys, FTy->isVarArg()));
 906     return;
 907   }
 908   if (auto *AI = dyn_cast<AllocaInst>(I))
 909     AI->setAllocatedType(TypeMapper->remapType(AI->getAllocatedType()));
 910   if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
 911     GEP->setSourceElementType(
 912         TypeMapper->remapType(GEP->getSourceElementType()));
 913     GEP->setResultElementType(
 914         TypeMapper->remapType(GEP->getResultElementType()));
 915   }
 916   I->mutateType(TypeMapper->remapType(I->getType()));
 917 }
 918
 919 void Mapper::remapGlobalObjectMetadata(GlobalObject &GO) {
 920   SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
 921   GO.getAllMetadata(MDs);
 922   GO.clearMetadata();
 923   for (const auto &I : MDs)
 924     GO.addMetadata(I.first, *cast<MDNode>(mapMetadata(I.second)));
 925 }
 926
 927 void Mapper::remapFunction(Function &F) {
 928   // Remap the operands.
 929   for (Use &Op : F.operands())
 930     if (Op)
 931       Op = mapValue(Op);
 932
 933   // Remap the metadata attachments.
 934   remapGlobalObjectMetadata(F);
 935
 936   // Remap the argument types.
 937   if (TypeMapper)
 938     for (Argument &A : F.args())
 939       A.mutateType(TypeMapper->remapType(A.getType()));
 940
 941   // Remap the instructions.
 942   for (BasicBlock &BB : F)
 943     for (Instruction &I : BB)
 944       remapInstruction(&I);
 945 }
 946
 947 void Mapper::mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
 948                                   bool IsOldCtorDtor,
 949                                   ArrayRef<Constant *> NewMembers) {
 950   SmallVector<Constant *, 16> Elements;
 951   if (InitPrefix) {
 952     unsigned NumElements =
 953         cast<ArrayType>(InitPrefix->getType())->getNumElements();
 954     for (unsigned I = 0; I != NumElements; ++I)
 955       Elements.push_back(InitPrefix->getAggregateElement(I));
 956   }
 957
 958   PointerType *VoidPtrTy;
 959   Type *EltTy;
 960   if (IsOldCtorDtor) {
 961     // FIXME: This upgrade is done during linking to support the C API.  See
 962     // also IRLinker::linkAppendingVarProto() in IRMover.cpp.
 963     VoidPtrTy = Type::getInt8Ty(GV.getContext())->getPointerTo();
 964     auto &ST = *cast<StructType>(NewMembers.front()->getType());
 965     Type *Tys[3] = {ST.getElementType(0), ST.getElementType(1), VoidPtrTy};
 966     EltTy = StructType::get(GV.getContext(), Tys, false);
 967   }
 968
 969   for (auto *V : NewMembers) {
 970     Constant *NewV;
 971     if (IsOldCtorDtor) {
 972       auto *S = cast<ConstantStruct>(V);
 973       auto *E1 = cast<Constant>(mapValue(S->getOperand(0)));
 974       auto *E2 = cast<Constant>(mapValue(S->getOperand(1)));
 975       Constant *Null = Constant::getNullValue(VoidPtrTy);
 976       NewV = ConstantStruct::get(cast<StructType>(EltTy), E1, E2, Null);
 977     } else {
 978       NewV = cast_or_null<Constant>(mapValue(V));
 979     }
 980     Elements.push_back(NewV);
 981   }
 982
 983   GV.setInitializer(ConstantArray::get(
 984       cast<ArrayType>(GV.getType()->getElementType()), Elements));
 985 }
 986
 987 void Mapper::scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
 988                                           unsigned MCID) {
 989   assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
 990   assert(MCID < MCs.size() && "Invalid mapping context");
 991
 992   WorklistEntry WE;
 993   WE.Kind = WorklistEntry::MapGlobalInit;
 994   WE.MCID = MCID;
 995   WE.Data.GVInit.GV = &GV;
 996   WE.Data.GVInit.Init = &Init;
 997   Worklist.push_back(WE);
 998 }
 999
1000 void Mapper::scheduleMapAppendingVariable(GlobalVariable &GV,
1001                                           Constant *InitPrefix,
1002                                           bool IsOldCtorDtor,
1003                                           ArrayRef<Constant *> NewMembers,
1004                                           unsigned MCID) {
1005   assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
1006   assert(MCID < MCs.size() && "Invalid mapping context");
1007
1008   WorklistEntry WE;
1009   WE.Kind = WorklistEntry::MapAppendingVar;
1010   WE.MCID = MCID;
1011   WE.Data.AppendingGV.GV = &GV;
1012   WE.Data.AppendingGV.InitPrefix = InitPrefix;
1013   WE.AppendingGVIsOldCtorDtor = IsOldCtorDtor;
1014   WE.AppendingGVNumNewMembers = NewMembers.size();
1015   Worklist.push_back(WE);
1016   AppendingInits.append(NewMembers.begin(), NewMembers.end());
1017 }
1018
1019 void Mapper::scheduleMapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee,
1020                                       unsigned MCID) {
1021   assert(AlreadyScheduled.insert(&GA).second && "Should not reschedule");
1022   assert(MCID < MCs.size() && "Invalid mapping context");
1023
1024   WorklistEntry WE;
1025   WE.Kind = WorklistEntry::MapGlobalAliasee;
1026   WE.MCID = MCID;
1027   WE.Data.GlobalAliasee.GA = &GA;
1028   WE.Data.GlobalAliasee.Aliasee = &Aliasee;
1029   Worklist.push_back(WE);
1030 }
1031
1032 void Mapper::scheduleRemapFunction(Function &F, unsigned MCID) {
1033   assert(AlreadyScheduled.insert(&F).second && "Should not reschedule");
1034   assert(MCID < MCs.size() && "Invalid mapping context");
1035
1036   WorklistEntry WE;
1037   WE.Kind = WorklistEntry::RemapFunction;
1038   WE.MCID = MCID;
1039   WE.Data.RemapF = &F;
1040   Worklist.push_back(WE);
1041 }
1042
1043 void Mapper::addFlags(RemapFlags Flags) {
1044   assert(!hasWorkToDo() && "Expected to have flushed the worklist");
1045   this->Flags = this->Flags | Flags;
1046 }
1047
1048 static Mapper *getAsMapper(void *pImpl) {
1049   return reinterpret_cast<Mapper *>(pImpl);
1050 }
1051
1052 namespace {
1053
1054 class FlushingMapper {
1055   Mapper &M;
1056
1057 public:
1058   explicit FlushingMapper(void *pImpl) : M(*getAsMapper(pImpl)) {
1059     assert(!M.hasWorkToDo() && "Expected to be flushed");
1060   }
1061
1062   ~FlushingMapper() { M.flush(); }
1063
1064   Mapper *operator->() const { return &M; }
1065 };
1066
1067 } // end anonymous namespace
1068
1069 ValueMapper::ValueMapper(ValueToValueMapTy &VM, RemapFlags Flags,
1070                          ValueMapTypeRemapper *TypeMapper,
1071                          ValueMaterializer *Materializer)
1072     : pImpl(new Mapper(VM, Flags, TypeMapper, Materializer)) {}
1073
1074 ValueMapper::~ValueMapper() { delete getAsMapper(pImpl); }
1075
1076 unsigned
1077 ValueMapper::registerAlternateMappingContext(ValueToValueMapTy &VM,
1078                                              ValueMaterializer *Materializer) {
1079   return getAsMapper(pImpl)->registerAlternateMappingContext(VM, Materializer);
1080 }
1081
1082 void ValueMapper::addFlags(RemapFlags Flags) {
1083   FlushingMapper(pImpl)->addFlags(Flags);
1084 }
1085
1086 Value *ValueMapper::mapValue(const Value &V) {
1087   return FlushingMapper(pImpl)->mapValue(&V);
1088 }
1089
1090 Constant *ValueMapper::mapConstant(const Constant &C) {
1091   return cast_or_null<Constant>(mapValue(C));
1092 }
1093
1094 Metadata *ValueMapper::mapMetadata(const Metadata &MD) {
1095   return FlushingMapper(pImpl)->mapMetadata(&MD);
1096 }
1097
1098 MDNode *ValueMapper::mapMDNode(const MDNode &N) {
1099   return cast_or_null<MDNode>(mapMetadata(N));
1100 }
1101
1102 void ValueMapper::remapInstruction(Instruction &I) {
1103   FlushingMapper(pImpl)->remapInstruction(&I);
1104 }
1105
1106 void ValueMapper::remapFunction(Function &F) {
1107   FlushingMapper(pImpl)->remapFunction(F);
1108 }
1109
1110 void ValueMapper::scheduleMapGlobalInitializer(GlobalVariable &GV,
1111                                                Constant &Init,
1112                                                unsigned MCID) {
1113   getAsMapper(pImpl)->scheduleMapGlobalInitializer(GV, Init, MCID);
1114 }
1115
1116 void ValueMapper::scheduleMapAppendingVariable(GlobalVariable &GV,
1117                                                Constant *InitPrefix,
1118                                                bool IsOldCtorDtor,
1119                                                ArrayRef<Constant *> NewMembers,
1120                                                unsigned MCID) {
1121   getAsMapper(pImpl)->scheduleMapAppendingVariable(
1122       GV, InitPrefix, IsOldCtorDtor, NewMembers, MCID);
1123 }
1124
1125 void ValueMapper::scheduleMapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee,
1126                                            unsigned MCID) {
1127   getAsMapper(pImpl)->scheduleMapGlobalAliasee(GA, Aliasee, MCID);
1128 }
1129
1130 void ValueMapper::scheduleRemapFunction(Function &F, unsigned MCID) {
1131   getAsMapper(pImpl)->scheduleRemapFunction(F, MCID);
1132 }