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