ValueMapper.cpp revision 363496 
1//===- ValueMapper.cpp - Interface shared by lib/Transforms/Utils ---------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the MapValue function, which is shared by various parts of
10// the lib/Transforms/Utils library.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Utils/ValueMapper.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/None.h"
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/IR/Argument.h"
23#include "llvm/IR/BasicBlock.h"
24#include "llvm/IR/CallSite.h"
25#include "llvm/IR/Constant.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/DebugInfoMetadata.h"
28#include "llvm/IR/DerivedTypes.h"
29#include "llvm/IR/Function.h"
30#include "llvm/IR/GlobalObject.h"
31#include "llvm/IR/GlobalIndirectSymbol.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
46using namespace llvm;
47
48// Out of line method to get vtable etc for class.
49void ValueMapTypeRemapper::anchor() {}
50void ValueMaterializer::anchor() {}
51
52namespace {
53
54/// A basic block used in a BlockAddress whose function body is not yet
55/// materialized.
56struct 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
65struct WorklistEntry {
66  enum EntryKind {
67    MapGlobalInit,
68    MapAppendingVar,
69    MapGlobalIndirectSymbol,
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 GlobalIndirectSymbolTy {
81    GlobalIndirectSymbol *GIS;
82    Constant *Target;
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    GlobalIndirectSymbolTy GlobalIndirectSymbol;
93    Function *RemapF;
94  } Data;
95};
96
97struct 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
107class 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
122public:
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 scheduleMapGlobalIndirectSymbol(GlobalIndirectSymbol &GIS, Constant &Target,
165                                       unsigned MCID);
166  void scheduleRemapFunction(Function &F, unsigned MCID);
167
168  void flush();
169
170private:
171  void mapGlobalInitializer(GlobalVariable &GV, Constant &Init);
172  void mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
173                            bool IsOldCtorDtor,
174                            ArrayRef<Constant *> NewMembers);
175  void mapGlobalIndirectSymbol(GlobalIndirectSymbol &GIS, Constant &Target);
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
190class 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
222public:
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
245private:
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
339Value *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                           IA->getDialect());
374    }
375
376    return getVM()[V] = const_cast<Value *>(V);
377  }
378
379  if (const auto *MDV = dyn_cast<MetadataAsValue>(V)) {
380    const Metadata *MD = MDV->getMetadata();
381
382    if (auto *LAM = dyn_cast<LocalAsMetadata>(MD)) {
383      // Look through to grab the local value.
384      if (Value *LV = mapValue(LAM->getValue())) {
385        if (V == LAM->getValue())
386          return const_cast<Value *>(V);
387        return MetadataAsValue::get(V->getContext(), ValueAsMetadata::get(LV));
388      }
389
390      // FIXME: always return nullptr once Verifier::verifyDominatesUse()
391      // ensures metadata operands only reference defined SSA values.
392      return (Flags & RF_IgnoreMissingLocals)
393                 ? nullptr
394                 : MetadataAsValue::get(V->getContext(),
395                                        MDTuple::get(V->getContext(), None));
396    }
397
398    // If this is a module-level metadata and we know that nothing at the module
399    // level is changing, then use an identity mapping.
400    if (Flags & RF_NoModuleLevelChanges)
401      return getVM()[V] = const_cast<Value *>(V);
402
403    // Map the metadata and turn it into a value.
404    auto *MappedMD = mapMetadata(MD);
405    if (MD == MappedMD)
406      return getVM()[V] = const_cast<Value *>(V);
407    return getVM()[V] = MetadataAsValue::get(V->getContext(), MappedMD);
408  }
409
410  // Okay, this either must be a constant (which may or may not be mappable) or
411  // is something that is not in the mapping table.
412  Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V));
413  if (!C)
414    return nullptr;
415
416  if (BlockAddress *BA = dyn_cast<BlockAddress>(C))
417    return mapBlockAddress(*BA);
418
419  auto mapValueOrNull = [this](Value *V) {
420    auto Mapped = mapValue(V);
421    assert((Mapped || (Flags & RF_NullMapMissingGlobalValues)) &&
422           "Unexpected null mapping for constant operand without "
423           "NullMapMissingGlobalValues flag");
424    return Mapped;
425  };
426
427  // Otherwise, we have some other constant to remap.  Start by checking to see
428  // if all operands have an identity remapping.
429  unsigned OpNo = 0, NumOperands = C->getNumOperands();
430  Value *Mapped = nullptr;
431  for (; OpNo != NumOperands; ++OpNo) {
432    Value *Op = C->getOperand(OpNo);
433    Mapped = mapValueOrNull(Op);
434    if (!Mapped)
435      return nullptr;
436    if (Mapped != Op)
437      break;
438  }
439
440  // See if the type mapper wants to remap the type as well.
441  Type *NewTy = C->getType();
442  if (TypeMapper)
443    NewTy = TypeMapper->remapType(NewTy);
444
445  // If the result type and all operands match up, then just insert an identity
446  // mapping.
447  if (OpNo == NumOperands && NewTy == C->getType())
448    return getVM()[V] = C;
449
450  // Okay, we need to create a new constant.  We've already processed some or
451  // all of the operands, set them all up now.
452  SmallVector<Constant*, 8> Ops;
453  Ops.reserve(NumOperands);
454  for (unsigned j = 0; j != OpNo; ++j)
455    Ops.push_back(cast<Constant>(C->getOperand(j)));
456
457  // If one of the operands mismatch, push it and the other mapped operands.
458  if (OpNo != NumOperands) {
459    Ops.push_back(cast<Constant>(Mapped));
460
461    // Map the rest of the operands that aren't processed yet.
462    for (++OpNo; OpNo != NumOperands; ++OpNo) {
463      Mapped = mapValueOrNull(C->getOperand(OpNo));
464      if (!Mapped)
465        return nullptr;
466      Ops.push_back(cast<Constant>(Mapped));
467    }
468  }
469  Type *NewSrcTy = nullptr;
470  if (TypeMapper)
471    if (auto *GEPO = dyn_cast<GEPOperator>(C))
472      NewSrcTy = TypeMapper->remapType(GEPO->getSourceElementType());
473
474  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
475    return getVM()[V] = CE->getWithOperands(Ops, NewTy, false, NewSrcTy);
476  if (isa<ConstantArray>(C))
477    return getVM()[V] = ConstantArray::get(cast<ArrayType>(NewTy), Ops);
478  if (isa<ConstantStruct>(C))
479    return getVM()[V] = ConstantStruct::get(cast<StructType>(NewTy), Ops);
480  if (isa<ConstantVector>(C))
481    return getVM()[V] = ConstantVector::get(Ops);
482  // If this is a no-operand constant, it must be because the type was remapped.
483  if (isa<UndefValue>(C))
484    return getVM()[V] = UndefValue::get(NewTy);
485  if (isa<ConstantAggregateZero>(C))
486    return getVM()[V] = ConstantAggregateZero::get(NewTy);
487  assert(isa<ConstantPointerNull>(C));
488  return getVM()[V] = ConstantPointerNull::get(cast<PointerType>(NewTy));
489}
490
491Value *Mapper::mapBlockAddress(const BlockAddress &BA) {
492  Function *F = cast<Function>(mapValue(BA.getFunction()));
493
494  // F may not have materialized its initializer.  In that case, create a
495  // dummy basic block for now, and replace it once we've materialized all
496  // the initializers.
497  BasicBlock *BB;
498  if (F->empty()) {
499    DelayedBBs.push_back(DelayedBasicBlock(BA));
500    BB = DelayedBBs.back().TempBB.get();
501  } else {
502    BB = cast_or_null<BasicBlock>(mapValue(BA.getBasicBlock()));
503  }
504
505  return getVM()[&BA] = BlockAddress::get(F, BB ? BB : BA.getBasicBlock());
506}
507
508Metadata *Mapper::mapToMetadata(const Metadata *Key, Metadata *Val) {
509  getVM().MD()[Key].reset(Val);
510  return Val;
511}
512
513Metadata *Mapper::mapToSelf(const Metadata *MD) {
514  return mapToMetadata(MD, const_cast<Metadata *>(MD));
515}
516
517Optional<Metadata *> MDNodeMapper::tryToMapOperand(const Metadata *Op) {
518  if (!Op)
519    return nullptr;
520
521  if (Optional<Metadata *> MappedOp = M.mapSimpleMetadata(Op)) {
522#ifndef NDEBUG
523    if (auto *CMD = dyn_cast<ConstantAsMetadata>(Op))
524      assert((!*MappedOp || M.getVM().count(CMD->getValue()) ||
525              M.getVM().getMappedMD(Op)) &&
526             "Expected Value to be memoized");
527    else
528      assert((isa<MDString>(Op) || M.getVM().getMappedMD(Op)) &&
529             "Expected result to be memoized");
530#endif
531    return *MappedOp;
532  }
533
534  const MDNode &N = *cast<MDNode>(Op);
535  if (N.isDistinct())
536    return mapDistinctNode(N);
537  return None;
538}
539
540static Metadata *cloneOrBuildODR(const MDNode &N) {
541  auto *CT = dyn_cast<DICompositeType>(&N);
542  // If ODR type uniquing is enabled, we would have uniqued composite types
543  // with identifiers during bitcode reading, so we can just use CT.
544  if (CT && CT->getContext().isODRUniquingDebugTypes() &&
545      CT->getIdentifier() != "")
546    return const_cast<DICompositeType *>(CT);
547  return MDNode::replaceWithDistinct(N.clone());
548}
549
550MDNode *MDNodeMapper::mapDistinctNode(const MDNode &N) {
551  assert(N.isDistinct() && "Expected a distinct node");
552  assert(!M.getVM().getMappedMD(&N) && "Expected an unmapped node");
553  DistinctWorklist.push_back(
554      cast<MDNode>((M.Flags & RF_MoveDistinctMDs)
555                       ? M.mapToSelf(&N)
556                       : M.mapToMetadata(&N, cloneOrBuildODR(N))));
557  return DistinctWorklist.back();
558}
559
560static ConstantAsMetadata *wrapConstantAsMetadata(const ConstantAsMetadata &CMD,
561                                                  Value *MappedV) {
562  if (CMD.getValue() == MappedV)
563    return const_cast<ConstantAsMetadata *>(&CMD);
564  return MappedV ? ConstantAsMetadata::getConstant(MappedV) : nullptr;
565}
566
567Optional<Metadata *> MDNodeMapper::getMappedOp(const Metadata *Op) const {
568  if (!Op)
569    return nullptr;
570
571  if (Optional<Metadata *> MappedOp = M.getVM().getMappedMD(Op))
572    return *MappedOp;
573
574  if (isa<MDString>(Op))
575    return const_cast<Metadata *>(Op);
576
577  if (auto *CMD = dyn_cast<ConstantAsMetadata>(Op))
578    return wrapConstantAsMetadata(*CMD, M.getVM().lookup(CMD->getValue()));
579
580  return None;
581}
582
583Metadata &MDNodeMapper::UniquedGraph::getFwdReference(MDNode &Op) {
584  auto Where = Info.find(&Op);
585  assert(Where != Info.end() && "Expected a valid reference");
586
587  auto &OpD = Where->second;
588  if (!OpD.HasChanged)
589    return Op;
590
591  // Lazily construct a temporary node.
592  if (!OpD.Placeholder)
593    OpD.Placeholder = Op.clone();
594
595  return *OpD.Placeholder;
596}
597
598template <class OperandMapper>
599void MDNodeMapper::remapOperands(MDNode &N, OperandMapper mapOperand) {
600  assert(!N.isUniqued() && "Expected distinct or temporary nodes");
601  for (unsigned I = 0, E = N.getNumOperands(); I != E; ++I) {
602    Metadata *Old = N.getOperand(I);
603    Metadata *New = mapOperand(Old);
604
605    if (Old != New)
606      N.replaceOperandWith(I, New);
607  }
608}
609
610namespace {
611
612/// An entry in the worklist for the post-order traversal.
613struct POTWorklistEntry {
614  MDNode *N;              ///< Current node.
615  MDNode::op_iterator Op; ///< Current operand of \c N.
616
617  /// Keep a flag of whether operands have changed in the worklist to avoid
618  /// hitting the map in \a UniquedGraph.
619  bool HasChanged = false;
620
621  POTWorklistEntry(MDNode &N) : N(&N), Op(N.op_begin()) {}
622};
623
624} // end anonymous namespace
625
626bool MDNodeMapper::createPOT(UniquedGraph &G, const MDNode &FirstN) {
627  assert(G.Info.empty() && "Expected a fresh traversal");
628  assert(FirstN.isUniqued() && "Expected uniqued node in POT");
629
630  // Construct a post-order traversal of the uniqued subgraph under FirstN.
631  bool AnyChanges = false;
632  SmallVector<POTWorklistEntry, 16> Worklist;
633  Worklist.push_back(POTWorklistEntry(const_cast<MDNode &>(FirstN)));
634  (void)G.Info[&FirstN];
635  while (!Worklist.empty()) {
636    // Start or continue the traversal through the this node's operands.
637    auto &WE = Worklist.back();
638    if (MDNode *N = visitOperands(G, WE.Op, WE.N->op_end(), WE.HasChanged)) {
639      // Push a new node to traverse first.
640      Worklist.push_back(POTWorklistEntry(*N));
641      continue;
642    }
643
644    // Push the node onto the POT.
645    assert(WE.N->isUniqued() && "Expected only uniqued nodes");
646    assert(WE.Op == WE.N->op_end() && "Expected to visit all operands");
647    auto &D = G.Info[WE.N];
648    AnyChanges |= D.HasChanged = WE.HasChanged;
649    D.ID = G.POT.size();
650    G.POT.push_back(WE.N);
651
652    // Pop the node off the worklist.
653    Worklist.pop_back();
654  }
655  return AnyChanges;
656}
657
658MDNode *MDNodeMapper::visitOperands(UniquedGraph &G, MDNode::op_iterator &I,
659                                    MDNode::op_iterator E, bool &HasChanged) {
660  while (I != E) {
661    Metadata *Op = *I++; // Increment even on early return.
662    if (Optional<Metadata *> MappedOp = tryToMapOperand(Op)) {
663      // Check if the operand changes.
664      HasChanged |= Op != *MappedOp;
665      continue;
666    }
667
668    // A uniqued metadata node.
669    MDNode &OpN = *cast<MDNode>(Op);
670    assert(OpN.isUniqued() &&
671           "Only uniqued operands cannot be mapped immediately");
672    if (G.Info.insert(std::make_pair(&OpN, Data())).second)
673      return &OpN; // This is a new one.  Return it.
674  }
675  return nullptr;
676}
677
678void MDNodeMapper::UniquedGraph::propagateChanges() {
679  bool AnyChanges;
680  do {
681    AnyChanges = false;
682    for (MDNode *N : POT) {
683      auto &D = Info[N];
684      if (D.HasChanged)
685        continue;
686
687      if (llvm::none_of(N->operands(), [&](const Metadata *Op) {
688            auto Where = Info.find(Op);
689            return Where != Info.end() && Where->second.HasChanged;
690          }))
691        continue;
692
693      AnyChanges = D.HasChanged = true;
694    }
695  } while (AnyChanges);
696}
697
698void MDNodeMapper::mapNodesInPOT(UniquedGraph &G) {
699  // Construct uniqued nodes, building forward references as necessary.
700  SmallVector<MDNode *, 16> CyclicNodes;
701  for (auto *N : G.POT) {
702    auto &D = G.Info[N];
703    if (!D.HasChanged) {
704      // The node hasn't changed.
705      M.mapToSelf(N);
706      continue;
707    }
708
709    // Remember whether this node had a placeholder.
710    bool HadPlaceholder(D.Placeholder);
711
712    // Clone the uniqued node and remap the operands.
713    TempMDNode ClonedN = D.Placeholder ? std::move(D.Placeholder) : N->clone();
714    remapOperands(*ClonedN, [this, &D, &G](Metadata *Old) {
715      if (Optional<Metadata *> MappedOp = getMappedOp(Old))
716        return *MappedOp;
717      (void)D;
718      assert(G.Info[Old].ID > D.ID && "Expected a forward reference");
719      return &G.getFwdReference(*cast<MDNode>(Old));
720    });
721
722    auto *NewN = MDNode::replaceWithUniqued(std::move(ClonedN));
723    M.mapToMetadata(N, NewN);
724
725    // Nodes that were referenced out of order in the POT are involved in a
726    // uniquing cycle.
727    if (HadPlaceholder)
728      CyclicNodes.push_back(NewN);
729  }
730
731  // Resolve cycles.
732  for (auto *N : CyclicNodes)
733    if (!N->isResolved())
734      N->resolveCycles();
735}
736
737Metadata *MDNodeMapper::map(const MDNode &N) {
738  assert(DistinctWorklist.empty() && "MDNodeMapper::map is not recursive");
739  assert(!(M.Flags & RF_NoModuleLevelChanges) &&
740         "MDNodeMapper::map assumes module-level changes");
741
742  // Require resolved nodes whenever metadata might be remapped.
743  assert(N.isResolved() && "Unexpected unresolved node");
744
745  Metadata *MappedN =
746      N.isUniqued() ? mapTopLevelUniquedNode(N) : mapDistinctNode(N);
747  while (!DistinctWorklist.empty())
748    remapOperands(*DistinctWorklist.pop_back_val(), [this](Metadata *Old) {
749      if (Optional<Metadata *> MappedOp = tryToMapOperand(Old))
750        return *MappedOp;
751      return mapTopLevelUniquedNode(*cast<MDNode>(Old));
752    });
753  return MappedN;
754}
755
756Metadata *MDNodeMapper::mapTopLevelUniquedNode(const MDNode &FirstN) {
757  assert(FirstN.isUniqued() && "Expected uniqued node");
758
759  // Create a post-order traversal of uniqued nodes under FirstN.
760  UniquedGraph G;
761  if (!createPOT(G, FirstN)) {
762    // Return early if no nodes have changed.
763    for (const MDNode *N : G.POT)
764      M.mapToSelf(N);
765    return &const_cast<MDNode &>(FirstN);
766  }
767
768  // Update graph with all nodes that have changed.
769  G.propagateChanges();
770
771  // Map all the nodes in the graph.
772  mapNodesInPOT(G);
773
774  // Return the original node, remapped.
775  return *getMappedOp(&FirstN);
776}
777
778Optional<Metadata *> Mapper::mapSimpleMetadata(const Metadata *MD) {
779  // If the value already exists in the map, use it.
780  if (Optional<Metadata *> NewMD = getVM().getMappedMD(MD))
781    return *NewMD;
782
783  if (isa<MDString>(MD))
784    return const_cast<Metadata *>(MD);
785
786  // This is a module-level metadata.  If nothing at the module level is
787  // changing, use an identity mapping.
788  if ((Flags & RF_NoModuleLevelChanges))
789    return const_cast<Metadata *>(MD);
790
791  if (auto *CMD = dyn_cast<ConstantAsMetadata>(MD)) {
792    // Don't memoize ConstantAsMetadata.  Instead of lasting until the
793    // LLVMContext is destroyed, they can be deleted when the GlobalValue they
794    // reference is destructed.  These aren't super common, so the extra
795    // indirection isn't that expensive.
796    return wrapConstantAsMetadata(*CMD, mapValue(CMD->getValue()));
797  }
798
799  assert(isa<MDNode>(MD) && "Expected a metadata node");
800
801  return None;
802}
803
804Metadata *Mapper::mapMetadata(const Metadata *MD) {
805  assert(MD && "Expected valid metadata");
806  assert(!isa<LocalAsMetadata>(MD) && "Unexpected local metadata");
807
808  if (Optional<Metadata *> NewMD = mapSimpleMetadata(MD))
809    return *NewMD;
810
811  return MDNodeMapper(*this).map(*cast<MDNode>(MD));
812}
813
814void Mapper::flush() {
815  // Flush out the worklist of global values.
816  while (!Worklist.empty()) {
817    WorklistEntry E = Worklist.pop_back_val();
818    CurrentMCID = E.MCID;
819    switch (E.Kind) {
820    case WorklistEntry::MapGlobalInit:
821      E.Data.GVInit.GV->setInitializer(mapConstant(E.Data.GVInit.Init));
822      remapGlobalObjectMetadata(*E.Data.GVInit.GV);
823      break;
824    case WorklistEntry::MapAppendingVar: {
825      unsigned PrefixSize = AppendingInits.size() - E.AppendingGVNumNewMembers;
826      mapAppendingVariable(*E.Data.AppendingGV.GV,
827                           E.Data.AppendingGV.InitPrefix,
828                           E.AppendingGVIsOldCtorDtor,
829                           makeArrayRef(AppendingInits).slice(PrefixSize));
830      AppendingInits.resize(PrefixSize);
831      break;
832    }
833    case WorklistEntry::MapGlobalIndirectSymbol:
834      E.Data.GlobalIndirectSymbol.GIS->setIndirectSymbol(
835          mapConstant(E.Data.GlobalIndirectSymbol.Target));
836      break;
837    case WorklistEntry::RemapFunction:
838      remapFunction(*E.Data.RemapF);
839      break;
840    }
841  }
842  CurrentMCID = 0;
843
844  // Finish logic for block addresses now that all global values have been
845  // handled.
846  while (!DelayedBBs.empty()) {
847    DelayedBasicBlock DBB = DelayedBBs.pop_back_val();
848    BasicBlock *BB = cast_or_null<BasicBlock>(mapValue(DBB.OldBB));
849    DBB.TempBB->replaceAllUsesWith(BB ? BB : DBB.OldBB);
850  }
851}
852
853void Mapper::remapInstruction(Instruction *I) {
854  // Remap operands.
855  for (Use &Op : I->operands()) {
856    Value *V = mapValue(Op);
857    // If we aren't ignoring missing entries, assert that something happened.
858    if (V)
859      Op = V;
860    else
861      assert((Flags & RF_IgnoreMissingLocals) &&
862             "Referenced value not in value map!");
863  }
864
865  // Remap phi nodes' incoming blocks.
866  if (PHINode *PN = dyn_cast<PHINode>(I)) {
867    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
868      Value *V = mapValue(PN->getIncomingBlock(i));
869      // If we aren't ignoring missing entries, assert that something happened.
870      if (V)
871        PN->setIncomingBlock(i, cast<BasicBlock>(V));
872      else
873        assert((Flags & RF_IgnoreMissingLocals) &&
874               "Referenced block not in value map!");
875    }
876  }
877
878  // Remap attached metadata.
879  SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
880  I->getAllMetadata(MDs);
881  for (const auto &MI : MDs) {
882    MDNode *Old = MI.second;
883    MDNode *New = cast_or_null<MDNode>(mapMetadata(Old));
884    if (New != Old)
885      I->setMetadata(MI.first, New);
886  }
887
888  if (!TypeMapper)
889    return;
890
891  // If the instruction's type is being remapped, do so now.
892  if (auto CS = CallSite(I)) {
893    SmallVector<Type *, 3> Tys;
894    FunctionType *FTy = CS.getFunctionType();
895    Tys.reserve(FTy->getNumParams());
896    for (Type *Ty : FTy->params())
897      Tys.push_back(TypeMapper->remapType(Ty));
898    CS.mutateFunctionType(FunctionType::get(
899        TypeMapper->remapType(I->getType()), Tys, FTy->isVarArg()));
900
901    LLVMContext &C = CS->getContext();
902    AttributeList Attrs = CS.getAttributes();
903    for (unsigned i = 0; i < Attrs.getNumAttrSets(); ++i) {
904      if (Attrs.hasAttribute(i, Attribute::ByVal)) {
905        Type *Ty = Attrs.getAttribute(i, Attribute::ByVal).getValueAsType();
906        if (!Ty)
907          continue;
908
909        Attrs = Attrs.removeAttribute(C, i, Attribute::ByVal);
910        Attrs = Attrs.addAttribute(
911            C, i, Attribute::getWithByValType(C, TypeMapper->remapType(Ty)));
912      }
913    }
914    CS.setAttributes(Attrs);
915    return;
916  }
917  if (auto *AI = dyn_cast<AllocaInst>(I))
918    AI->setAllocatedType(TypeMapper->remapType(AI->getAllocatedType()));
919  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
920    GEP->setSourceElementType(
921        TypeMapper->remapType(GEP->getSourceElementType()));
922    GEP->setResultElementType(
923        TypeMapper->remapType(GEP->getResultElementType()));
924  }
925  I->mutateType(TypeMapper->remapType(I->getType()));
926}
927
928void Mapper::remapGlobalObjectMetadata(GlobalObject &GO) {
929  SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
930  GO.getAllMetadata(MDs);
931  GO.clearMetadata();
932  for (const auto &I : MDs)
933    GO.addMetadata(I.first, *cast<MDNode>(mapMetadata(I.second)));
934}
935
936void Mapper::remapFunction(Function &F) {
937  // Remap the operands.
938  for (Use &Op : F.operands())
939    if (Op)
940      Op = mapValue(Op);
941
942  // Remap the metadata attachments.
943  remapGlobalObjectMetadata(F);
944
945  // Remap the argument types.
946  if (TypeMapper)
947    for (Argument &A : F.args())
948      A.mutateType(TypeMapper->remapType(A.getType()));
949
950  // Remap the instructions.
951  for (BasicBlock &BB : F)
952    for (Instruction &I : BB)
953      remapInstruction(&I);
954}
955
956void Mapper::mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
957                                  bool IsOldCtorDtor,
958                                  ArrayRef<Constant *> NewMembers) {
959  SmallVector<Constant *, 16> Elements;
960  if (InitPrefix) {
961    unsigned NumElements =
962        cast<ArrayType>(InitPrefix->getType())->getNumElements();
963    for (unsigned I = 0; I != NumElements; ++I)
964      Elements.push_back(InitPrefix->getAggregateElement(I));
965  }
966
967  PointerType *VoidPtrTy;
968  Type *EltTy;
969  if (IsOldCtorDtor) {
970    // FIXME: This upgrade is done during linking to support the C API.  See
971    // also IRLinker::linkAppendingVarProto() in IRMover.cpp.
972    VoidPtrTy = Type::getInt8Ty(GV.getContext())->getPointerTo();
973    auto &ST = *cast<StructType>(NewMembers.front()->getType());
974    Type *Tys[3] = {ST.getElementType(0), ST.getElementType(1), VoidPtrTy};
975    EltTy = StructType::get(GV.getContext(), Tys, false);
976  }
977
978  for (auto *V : NewMembers) {
979    Constant *NewV;
980    if (IsOldCtorDtor) {
981      auto *S = cast<ConstantStruct>(V);
982      auto *E1 = cast<Constant>(mapValue(S->getOperand(0)));
983      auto *E2 = cast<Constant>(mapValue(S->getOperand(1)));
984      Constant *Null = Constant::getNullValue(VoidPtrTy);
985      NewV = ConstantStruct::get(cast<StructType>(EltTy), E1, E2, Null);
986    } else {
987      NewV = cast_or_null<Constant>(mapValue(V));
988    }
989    Elements.push_back(NewV);
990  }
991
992  GV.setInitializer(ConstantArray::get(
993      cast<ArrayType>(GV.getType()->getElementType()), Elements));
994}
995
996void Mapper::scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
997                                          unsigned MCID) {
998  assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
999  assert(MCID < MCs.size() && "Invalid mapping context");
1000
1001  WorklistEntry WE;
1002  WE.Kind = WorklistEntry::MapGlobalInit;
1003  WE.MCID = MCID;
1004  WE.Data.GVInit.GV = &GV;
1005  WE.Data.GVInit.Init = &Init;
1006  Worklist.push_back(WE);
1007}
1008
1009void Mapper::scheduleMapAppendingVariable(GlobalVariable &GV,
1010                                          Constant *InitPrefix,
1011                                          bool IsOldCtorDtor,
1012                                          ArrayRef<Constant *> NewMembers,
1013                                          unsigned MCID) {
1014  assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
1015  assert(MCID < MCs.size() && "Invalid mapping context");
1016
1017  WorklistEntry WE;
1018  WE.Kind = WorklistEntry::MapAppendingVar;
1019  WE.MCID = MCID;
1020  WE.Data.AppendingGV.GV = &GV;
1021  WE.Data.AppendingGV.InitPrefix = InitPrefix;
1022  WE.AppendingGVIsOldCtorDtor = IsOldCtorDtor;
1023  WE.AppendingGVNumNewMembers = NewMembers.size();
1024  Worklist.push_back(WE);
1025  AppendingInits.append(NewMembers.begin(), NewMembers.end());
1026}
1027
1028void Mapper::scheduleMapGlobalIndirectSymbol(GlobalIndirectSymbol &GIS,
1029                                             Constant &Target, unsigned MCID) {
1030  assert(AlreadyScheduled.insert(&GIS).second && "Should not reschedule");
1031  assert(MCID < MCs.size() && "Invalid mapping context");
1032
1033  WorklistEntry WE;
1034  WE.Kind = WorklistEntry::MapGlobalIndirectSymbol;
1035  WE.MCID = MCID;
1036  WE.Data.GlobalIndirectSymbol.GIS = &GIS;
1037  WE.Data.GlobalIndirectSymbol.Target = &Target;
1038  Worklist.push_back(WE);
1039}
1040
1041void Mapper::scheduleRemapFunction(Function &F, unsigned MCID) {
1042  assert(AlreadyScheduled.insert(&F).second && "Should not reschedule");
1043  assert(MCID < MCs.size() && "Invalid mapping context");
1044
1045  WorklistEntry WE;
1046  WE.Kind = WorklistEntry::RemapFunction;
1047  WE.MCID = MCID;
1048  WE.Data.RemapF = &F;
1049  Worklist.push_back(WE);
1050}
1051
1052void Mapper::addFlags(RemapFlags Flags) {
1053  assert(!hasWorkToDo() && "Expected to have flushed the worklist");
1054  this->Flags = this->Flags | Flags;
1055}
1056
1057static Mapper *getAsMapper(void *pImpl) {
1058  return reinterpret_cast<Mapper *>(pImpl);
1059}
1060
1061namespace {
1062
1063class FlushingMapper {
1064  Mapper &M;
1065
1066public:
1067  explicit FlushingMapper(void *pImpl) : M(*getAsMapper(pImpl)) {
1068    assert(!M.hasWorkToDo() && "Expected to be flushed");
1069  }
1070
1071  ~FlushingMapper() { M.flush(); }
1072
1073  Mapper *operator->() const { return &M; }
1074};
1075
1076} // end anonymous namespace
1077
1078ValueMapper::ValueMapper(ValueToValueMapTy &VM, RemapFlags Flags,
1079                         ValueMapTypeRemapper *TypeMapper,
1080                         ValueMaterializer *Materializer)
1081    : pImpl(new Mapper(VM, Flags, TypeMapper, Materializer)) {}
1082
1083ValueMapper::~ValueMapper() { delete getAsMapper(pImpl); }
1084
1085unsigned
1086ValueMapper::registerAlternateMappingContext(ValueToValueMapTy &VM,
1087                                             ValueMaterializer *Materializer) {
1088  return getAsMapper(pImpl)->registerAlternateMappingContext(VM, Materializer);
1089}
1090
1091void ValueMapper::addFlags(RemapFlags Flags) {
1092  FlushingMapper(pImpl)->addFlags(Flags);
1093}
1094
1095Value *ValueMapper::mapValue(const Value &V) {
1096  return FlushingMapper(pImpl)->mapValue(&V);
1097}
1098
1099Constant *ValueMapper::mapConstant(const Constant &C) {
1100  return cast_or_null<Constant>(mapValue(C));
1101}
1102
1103Metadata *ValueMapper::mapMetadata(const Metadata &MD) {
1104  return FlushingMapper(pImpl)->mapMetadata(&MD);
1105}
1106
1107MDNode *ValueMapper::mapMDNode(const MDNode &N) {
1108  return cast_or_null<MDNode>(mapMetadata(N));
1109}
1110
1111void ValueMapper::remapInstruction(Instruction &I) {
1112  FlushingMapper(pImpl)->remapInstruction(&I);
1113}
1114
1115void ValueMapper::remapFunction(Function &F) {
1116  FlushingMapper(pImpl)->remapFunction(F);
1117}
1118
1119void ValueMapper::scheduleMapGlobalInitializer(GlobalVariable &GV,
1120                                               Constant &Init,
1121                                               unsigned MCID) {
1122  getAsMapper(pImpl)->scheduleMapGlobalInitializer(GV, Init, MCID);
1123}
1124
1125void ValueMapper::scheduleMapAppendingVariable(GlobalVariable &GV,
1126                                               Constant *InitPrefix,
1127                                               bool IsOldCtorDtor,
1128                                               ArrayRef<Constant *> NewMembers,
1129                                               unsigned MCID) {
1130  getAsMapper(pImpl)->scheduleMapAppendingVariable(
1131      GV, InitPrefix, IsOldCtorDtor, NewMembers, MCID);
1132}
1133
1134void ValueMapper::scheduleMapGlobalIndirectSymbol(GlobalIndirectSymbol &GIS,
1135                                                  Constant &Target,
1136                                                  unsigned MCID) {
1137  getAsMapper(pImpl)->scheduleMapGlobalIndirectSymbol(GIS, Target, MCID);
1138}
1139
1140void ValueMapper::scheduleRemapFunction(Function &F, unsigned MCID) {
1141  getAsMapper(pImpl)->scheduleRemapFunction(F, MCID);
1142}
1143