1 //===- ValueMapper.cpp - Interface shared by lib/Transforms/Utils ---------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the MapValue function, which is shared by various parts of
11 // the lib/Transforms/Utils library.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/Utils/ValueMapper.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/IR/CallSite.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/DebugInfoMetadata.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/IR/GlobalAlias.h"
22 #include "llvm/IR/GlobalVariable.h"
23 #include "llvm/IR/InlineAsm.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/Metadata.h"
26 #include "llvm/IR/Operator.h"
29 // Out of line method to get vtable etc for class.
30 void ValueMapTypeRemapper::anchor() {}
31 void ValueMaterializer::anchor() {}
35 /// A basic block used in a BlockAddress whose function body is not yet
37 struct DelayedBasicBlock {
39 std::unique_ptr<BasicBlock> TempBB;
41 DelayedBasicBlock(const BlockAddress &Old)
42 : OldBB(Old.getBasicBlock()),
43 TempBB(BasicBlock::Create(Old.getContext())) {}
46 struct WorklistEntry {
57 struct AppendingGVTy {
61 struct GlobalAliaseeTy {
68 unsigned AppendingGVIsOldCtorDtor : 1;
69 unsigned AppendingGVNumNewMembers;
72 AppendingGVTy AppendingGV;
73 GlobalAliaseeTy GlobalAliasee;
78 struct MappingContext {
79 ValueToValueMapTy *VM;
80 ValueMaterializer *Materializer = nullptr;
82 /// Construct a MappingContext with a value map and materializer.
83 explicit MappingContext(ValueToValueMapTy &VM,
84 ValueMaterializer *Materializer = nullptr)
85 : VM(&VM), Materializer(Materializer) {}
90 friend class MDNodeMapper;
93 DenseSet<GlobalValue *> AlreadyScheduled;
97 ValueMapTypeRemapper *TypeMapper;
98 unsigned CurrentMCID = 0;
99 SmallVector<MappingContext, 2> MCs;
100 SmallVector<WorklistEntry, 4> Worklist;
101 SmallVector<DelayedBasicBlock, 1> DelayedBBs;
102 SmallVector<Constant *, 16> AppendingInits;
105 Mapper(ValueToValueMapTy &VM, RemapFlags Flags,
106 ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer)
107 : Flags(Flags), TypeMapper(TypeMapper),
108 MCs(1, MappingContext(VM, Materializer)) {}
110 /// ValueMapper should explicitly call \a flush() before destruction.
111 ~Mapper() { assert(!hasWorkToDo() && "Expected to be flushed"); }
113 bool hasWorkToDo() const { return !Worklist.empty(); }
116 registerAlternateMappingContext(ValueToValueMapTy &VM,
117 ValueMaterializer *Materializer = nullptr) {
118 MCs.push_back(MappingContext(VM, Materializer));
119 return MCs.size() - 1;
122 void addFlags(RemapFlags Flags);
124 void remapGlobalObjectMetadata(GlobalObject &GO);
126 Value *mapValue(const Value *V);
127 void remapInstruction(Instruction *I);
128 void remapFunction(Function &F);
130 Constant *mapConstant(const Constant *C) {
131 return cast_or_null<Constant>(mapValue(C));
136 /// Find the mapping for MD. Guarantees that the return will be resolved
137 /// (not an MDNode, or MDNode::isResolved() returns true).
138 Metadata *mapMetadata(const Metadata *MD);
140 void scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
142 void scheduleMapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
144 ArrayRef<Constant *> NewMembers,
146 void scheduleMapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee,
148 void scheduleRemapFunction(Function &F, unsigned MCID);
153 void mapGlobalInitializer(GlobalVariable &GV, Constant &Init);
154 void mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
156 ArrayRef<Constant *> NewMembers);
157 void mapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee);
158 void remapFunction(Function &F, ValueToValueMapTy &VM);
160 ValueToValueMapTy &getVM() { return *MCs[CurrentMCID].VM; }
161 ValueMaterializer *getMaterializer() { return MCs[CurrentMCID].Materializer; }
163 Value *mapBlockAddress(const BlockAddress &BA);
165 /// Map metadata that doesn't require visiting operands.
166 Optional<Metadata *> mapSimpleMetadata(const Metadata *MD);
168 Metadata *mapToMetadata(const Metadata *Key, Metadata *Val);
169 Metadata *mapToSelf(const Metadata *MD);
175 /// Data about a node in \a UniquedGraph.
177 bool HasChanged = false;
179 TempMDNode Placeholder;
182 /// A graph of uniqued nodes.
183 struct UniquedGraph {
184 SmallDenseMap<const Metadata *, Data, 32> Info; // Node properties.
185 SmallVector<MDNode *, 16> POT; // Post-order traversal.
187 /// Propagate changed operands through the post-order traversal.
189 /// Iteratively update \a Data::HasChanged for each node based on \a
190 /// Data::HasChanged of its operands, until fixed point.
191 void propagateChanges();
193 /// Get a forward reference to a node to use as an operand.
194 Metadata &getFwdReference(MDNode &Op);
197 /// Worklist of distinct nodes whose operands need to be remapped.
198 SmallVector<MDNode *, 16> DistinctWorklist;
200 // Storage for a UniquedGraph.
201 SmallDenseMap<const Metadata *, Data, 32> InfoStorage;
202 SmallVector<MDNode *, 16> POTStorage;
205 MDNodeMapper(Mapper &M) : M(M) {}
207 /// Map a metadata node (and its transitive operands).
209 /// Map all the (unmapped) nodes in the subgraph under \c N. The iterative
210 /// algorithm handles distinct nodes and uniqued node subgraphs using
211 /// different strategies.
213 /// Distinct nodes are immediately mapped and added to \a DistinctWorklist
214 /// using \a mapDistinctNode(). Their mapping can always be computed
215 /// immediately without visiting operands, even if their operands change.
217 /// The mapping for uniqued nodes depends on whether their operands change.
218 /// \a mapTopLevelUniquedNode() traverses the transitive uniqued subgraph of
219 /// a node to calculate uniqued node mappings in bulk. Distinct leafs are
220 /// added to \a DistinctWorklist with \a mapDistinctNode().
222 /// After mapping \c N itself, this function remaps the operands of the
223 /// distinct nodes in \a DistinctWorklist until the entire subgraph under \c
224 /// N has been mapped.
225 Metadata *map(const MDNode &N);
228 /// Map a top-level uniqued node and the uniqued subgraph underneath it.
230 /// This builds up a post-order traversal of the (unmapped) uniqued subgraph
231 /// underneath \c FirstN and calculates the nodes' mapping. Each node uses
232 /// the identity mapping (\a Mapper::mapToSelf()) as long as all of its
233 /// operands uses the identity mapping.
235 /// The algorithm works as follows:
237 /// 1. \a createPOT(): traverse the uniqued subgraph under \c FirstN and
238 /// save the post-order traversal in the given \a UniquedGraph, tracking
239 /// nodes' operands change.
241 /// 2. \a UniquedGraph::propagateChanges(): propagate changed operands
242 /// through the \a UniquedGraph until fixed point, following the rule
243 /// that if a node changes, any node that references must also change.
245 /// 3. \a mapNodesInPOT(): map the uniqued nodes, creating new uniqued nodes
246 /// (referencing new operands) where necessary.
247 Metadata *mapTopLevelUniquedNode(const MDNode &FirstN);
249 /// Try to map the operand of an \a MDNode.
251 /// If \c Op is already mapped, return the mapping. If it's not an \a
252 /// MDNode, compute and return the mapping. If it's a distinct \a MDNode,
253 /// return the result of \a mapDistinctNode().
255 /// \return None if \c Op is an unmapped uniqued \a MDNode.
256 /// \post getMappedOp(Op) only returns None if this returns None.
257 Optional<Metadata *> tryToMapOperand(const Metadata *Op);
259 /// Map a distinct node.
261 /// Return the mapping for the distinct node \c N, saving the result in \a
262 /// DistinctWorklist for later remapping.
264 /// \pre \c N is not yet mapped.
265 /// \pre \c N.isDistinct().
266 MDNode *mapDistinctNode(const MDNode &N);
268 /// Get a previously mapped node.
269 Optional<Metadata *> getMappedOp(const Metadata *Op) const;
271 /// Create a post-order traversal of an unmapped uniqued node subgraph.
273 /// This traverses the metadata graph deeply enough to map \c FirstN. It
274 /// uses \a tryToMapOperand() (via \a Mapper::mapSimplifiedNode()), so any
275 /// metadata that has already been mapped will not be part of the POT.
277 /// Each node that has a changed operand from outside the graph (e.g., a
278 /// distinct node, an already-mapped uniqued node, or \a ConstantAsMetadata)
279 /// is marked with \a Data::HasChanged.
281 /// \return \c true if any nodes in \c G have \a Data::HasChanged.
282 /// \post \c G.POT is a post-order traversal ending with \c FirstN.
283 /// \post \a Data::hasChanged in \c G.Info indicates whether any node needs
284 /// to change because of operands outside the graph.
285 bool createPOT(UniquedGraph &G, const MDNode &FirstN);
287 /// Visit the operands of a uniqued node in the POT.
289 /// Visit the operands in the range from \c I to \c E, returning the first
290 /// uniqued node we find that isn't yet in \c G. \c I is always advanced to
291 /// where to continue the loop through the operands.
293 /// This sets \c HasChanged if any of the visited operands change.
294 MDNode *visitOperands(UniquedGraph &G, MDNode::op_iterator &I,
295 MDNode::op_iterator E, bool &HasChanged);
297 /// Map all the nodes in the given uniqued graph.
299 /// This visits all the nodes in \c G in post-order, using the identity
300 /// mapping or creating a new node depending on \a Data::HasChanged.
302 /// \pre \a getMappedOp() returns None for nodes in \c G, but not for any of
303 /// their operands outside of \c G.
304 /// \pre \a Data::HasChanged is true for a node in \c G iff any of its
305 /// operands have changed.
306 /// \post \a getMappedOp() returns the mapped node for every node in \c G.
307 void mapNodesInPOT(UniquedGraph &G);
309 /// Remap a node's operands using the given functor.
311 /// Iterate through the operands of \c N and update them in place using \c
314 /// \pre N.isDistinct() or N.isTemporary().
315 template <class OperandMapper>
316 void remapOperands(MDNode &N, OperandMapper mapOperand);
321 Value *Mapper::mapValue(const Value *V) {
322 ValueToValueMapTy::iterator I = getVM().find(V);
324 // If the value already exists in the map, use it.
325 if (I != getVM().end()) {
326 assert(I->second && "Unexpected null mapping");
330 // If we have a materializer and it can materialize a value, use that.
331 if (auto *Materializer = getMaterializer()) {
332 if (Value *NewV = Materializer->materialize(const_cast<Value *>(V))) {
338 // Global values do not need to be seeded into the VM if they
339 // are using the identity mapping.
340 if (isa<GlobalValue>(V)) {
341 if (Flags & RF_NullMapMissingGlobalValues)
343 return getVM()[V] = const_cast<Value *>(V);
346 if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
347 // Inline asm may need *type* remapping.
348 FunctionType *NewTy = IA->getFunctionType();
350 NewTy = cast<FunctionType>(TypeMapper->remapType(NewTy));
352 if (NewTy != IA->getFunctionType())
353 V = InlineAsm::get(NewTy, IA->getAsmString(), IA->getConstraintString(),
354 IA->hasSideEffects(), IA->isAlignStack());
357 return getVM()[V] = const_cast<Value *>(V);
360 if (const auto *MDV = dyn_cast<MetadataAsValue>(V)) {
361 const Metadata *MD = MDV->getMetadata();
363 if (auto *LAM = dyn_cast<LocalAsMetadata>(MD)) {
364 // Look through to grab the local value.
365 if (Value *LV = mapValue(LAM->getValue())) {
366 if (V == LAM->getValue())
367 return const_cast<Value *>(V);
368 return MetadataAsValue::get(V->getContext(), ValueAsMetadata::get(LV));
371 // FIXME: always return nullptr once Verifier::verifyDominatesUse()
372 // ensures metadata operands only reference defined SSA values.
373 return (Flags & RF_IgnoreMissingLocals)
375 : MetadataAsValue::get(V->getContext(),
376 MDTuple::get(V->getContext(), None));
379 // If this is a module-level metadata and we know that nothing at the module
380 // level is changing, then use an identity mapping.
381 if (Flags & RF_NoModuleLevelChanges)
382 return getVM()[V] = const_cast<Value *>(V);
384 // Map the metadata and turn it into a value.
385 auto *MappedMD = mapMetadata(MD);
387 return getVM()[V] = const_cast<Value *>(V);
388 return getVM()[V] = MetadataAsValue::get(V->getContext(), MappedMD);
391 // Okay, this either must be a constant (which may or may not be mappable) or
392 // is something that is not in the mapping table.
393 Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V));
397 if (BlockAddress *BA = dyn_cast<BlockAddress>(C))
398 return mapBlockAddress(*BA);
400 auto mapValueOrNull = [this](Value *V) {
401 auto Mapped = mapValue(V);
402 assert((Mapped || (Flags & RF_NullMapMissingGlobalValues)) &&
403 "Unexpected null mapping for constant operand without "
404 "NullMapMissingGlobalValues flag");
408 // Otherwise, we have some other constant to remap. Start by checking to see
409 // if all operands have an identity remapping.
410 unsigned OpNo = 0, NumOperands = C->getNumOperands();
411 Value *Mapped = nullptr;
412 for (; OpNo != NumOperands; ++OpNo) {
413 Value *Op = C->getOperand(OpNo);
414 Mapped = mapValueOrNull(Op);
421 // See if the type mapper wants to remap the type as well.
422 Type *NewTy = C->getType();
424 NewTy = TypeMapper->remapType(NewTy);
426 // If the result type and all operands match up, then just insert an identity
428 if (OpNo == NumOperands && NewTy == C->getType())
429 return getVM()[V] = C;
431 // Okay, we need to create a new constant. We've already processed some or
432 // all of the operands, set them all up now.
433 SmallVector<Constant*, 8> Ops;
434 Ops.reserve(NumOperands);
435 for (unsigned j = 0; j != OpNo; ++j)
436 Ops.push_back(cast<Constant>(C->getOperand(j)));
438 // If one of the operands mismatch, push it and the other mapped operands.
439 if (OpNo != NumOperands) {
440 Ops.push_back(cast<Constant>(Mapped));
442 // Map the rest of the operands that aren't processed yet.
443 for (++OpNo; OpNo != NumOperands; ++OpNo) {
444 Mapped = mapValueOrNull(C->getOperand(OpNo));
447 Ops.push_back(cast<Constant>(Mapped));
450 Type *NewSrcTy = nullptr;
452 if (auto *GEPO = dyn_cast<GEPOperator>(C))
453 NewSrcTy = TypeMapper->remapType(GEPO->getSourceElementType());
455 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
456 return getVM()[V] = CE->getWithOperands(Ops, NewTy, false, NewSrcTy);
457 if (isa<ConstantArray>(C))
458 return getVM()[V] = ConstantArray::get(cast<ArrayType>(NewTy), Ops);
459 if (isa<ConstantStruct>(C))
460 return getVM()[V] = ConstantStruct::get(cast<StructType>(NewTy), Ops);
461 if (isa<ConstantVector>(C))
462 return getVM()[V] = ConstantVector::get(Ops);
463 // If this is a no-operand constant, it must be because the type was remapped.
464 if (isa<UndefValue>(C))
465 return getVM()[V] = UndefValue::get(NewTy);
466 if (isa<ConstantAggregateZero>(C))
467 return getVM()[V] = ConstantAggregateZero::get(NewTy);
468 assert(isa<ConstantPointerNull>(C));
469 return getVM()[V] = ConstantPointerNull::get(cast<PointerType>(NewTy));
472 Value *Mapper::mapBlockAddress(const BlockAddress &BA) {
473 Function *F = cast<Function>(mapValue(BA.getFunction()));
475 // F may not have materialized its initializer. In that case, create a
476 // dummy basic block for now, and replace it once we've materialized all
480 DelayedBBs.push_back(DelayedBasicBlock(BA));
481 BB = DelayedBBs.back().TempBB.get();
483 BB = cast_or_null<BasicBlock>(mapValue(BA.getBasicBlock()));
486 return getVM()[&BA] = BlockAddress::get(F, BB ? BB : BA.getBasicBlock());
489 Metadata *Mapper::mapToMetadata(const Metadata *Key, Metadata *Val) {
490 getVM().MD()[Key].reset(Val);
494 Metadata *Mapper::mapToSelf(const Metadata *MD) {
495 return mapToMetadata(MD, const_cast<Metadata *>(MD));
498 Optional<Metadata *> MDNodeMapper::tryToMapOperand(const Metadata *Op) {
502 if (Optional<Metadata *> MappedOp = M.mapSimpleMetadata(Op)) {
504 if (auto *CMD = dyn_cast<ConstantAsMetadata>(Op))
505 assert((!*MappedOp || M.getVM().count(CMD->getValue()) ||
506 M.getVM().getMappedMD(Op)) &&
507 "Expected Value to be memoized");
509 assert((isa<MDString>(Op) || M.getVM().getMappedMD(Op)) &&
510 "Expected result to be memoized");
515 const MDNode &N = *cast<MDNode>(Op);
517 return mapDistinctNode(N);
521 MDNode *MDNodeMapper::mapDistinctNode(const MDNode &N) {
522 assert(N.isDistinct() && "Expected a distinct node");
523 assert(!M.getVM().getMappedMD(&N) && "Expected an unmapped node");
524 DistinctWorklist.push_back(cast<MDNode>(
525 (M.Flags & RF_MoveDistinctMDs)
527 : M.mapToMetadata(&N, MDNode::replaceWithDistinct(N.clone()))));
528 return DistinctWorklist.back();
531 static ConstantAsMetadata *wrapConstantAsMetadata(const ConstantAsMetadata &CMD,
533 if (CMD.getValue() == MappedV)
534 return const_cast<ConstantAsMetadata *>(&CMD);
535 return MappedV ? ConstantAsMetadata::getConstant(MappedV) : nullptr;
538 Optional<Metadata *> MDNodeMapper::getMappedOp(const Metadata *Op) const {
542 if (Optional<Metadata *> MappedOp = M.getVM().getMappedMD(Op))
545 if (isa<MDString>(Op))
546 return const_cast<Metadata *>(Op);
548 if (auto *CMD = dyn_cast<ConstantAsMetadata>(Op))
549 return wrapConstantAsMetadata(*CMD, M.getVM().lookup(CMD->getValue()));
554 Metadata &MDNodeMapper::UniquedGraph::getFwdReference(MDNode &Op) {
555 auto Where = Info.find(&Op);
556 assert(Where != Info.end() && "Expected a valid reference");
558 auto &OpD = Where->second;
562 // Lazily construct a temporary node.
563 if (!OpD.Placeholder)
564 OpD.Placeholder = Op.clone();
566 return *OpD.Placeholder;
569 template <class OperandMapper>
570 void MDNodeMapper::remapOperands(MDNode &N, OperandMapper mapOperand) {
571 assert(!N.isUniqued() && "Expected distinct or temporary nodes");
572 for (unsigned I = 0, E = N.getNumOperands(); I != E; ++I) {
573 Metadata *Old = N.getOperand(I);
574 Metadata *New = mapOperand(Old);
577 N.replaceOperandWith(I, New);
582 /// An entry in the worklist for the post-order traversal.
583 struct POTWorklistEntry {
584 MDNode *N; ///< Current node.
585 MDNode::op_iterator Op; ///< Current operand of \c N.
587 /// Keep a flag of whether operands have changed in the worklist to avoid
588 /// hitting the map in \a UniquedGraph.
589 bool HasChanged = false;
591 POTWorklistEntry(MDNode &N) : N(&N), Op(N.op_begin()) {}
595 bool MDNodeMapper::createPOT(UniquedGraph &G, const MDNode &FirstN) {
596 assert(G.Info.empty() && "Expected a fresh traversal");
597 assert(FirstN.isUniqued() && "Expected uniqued node in POT");
599 // Construct a post-order traversal of the uniqued subgraph under FirstN.
600 bool AnyChanges = false;
601 SmallVector<POTWorklistEntry, 16> Worklist;
602 Worklist.push_back(POTWorklistEntry(const_cast<MDNode &>(FirstN)));
603 (void)G.Info[&FirstN];
604 while (!Worklist.empty()) {
605 // Start or continue the traversal through the this node's operands.
606 auto &WE = Worklist.back();
607 if (MDNode *N = visitOperands(G, WE.Op, WE.N->op_end(), WE.HasChanged)) {
608 // Push a new node to traverse first.
609 Worklist.push_back(POTWorklistEntry(*N));
613 // Push the node onto the POT.
614 assert(WE.N->isUniqued() && "Expected only uniqued nodes");
615 assert(WE.Op == WE.N->op_end() && "Expected to visit all operands");
616 auto &D = G.Info[WE.N];
617 AnyChanges |= D.HasChanged = WE.HasChanged;
619 G.POT.push_back(WE.N);
621 // Pop the node off the worklist.
627 MDNode *MDNodeMapper::visitOperands(UniquedGraph &G, MDNode::op_iterator &I,
628 MDNode::op_iterator E, bool &HasChanged) {
630 Metadata *Op = *I++; // Increment even on early return.
631 if (Optional<Metadata *> MappedOp = tryToMapOperand(Op)) {
632 // Check if the operand changes.
633 HasChanged |= Op != *MappedOp;
637 // A uniqued metadata node.
638 MDNode &OpN = *cast<MDNode>(Op);
639 assert(OpN.isUniqued() &&
640 "Only uniqued operands cannot be mapped immediately");
641 if (G.Info.insert(std::make_pair(&OpN, Data())).second)
642 return &OpN; // This is a new one. Return it.
647 void MDNodeMapper::UniquedGraph::propagateChanges() {
651 for (MDNode *N : POT) {
656 if (none_of(N->operands(), [&](const Metadata *Op) {
657 auto Where = Info.find(Op);
658 return Where != Info.end() && Where->second.HasChanged;
662 AnyChanges = D.HasChanged = true;
664 } while (AnyChanges);
667 void MDNodeMapper::mapNodesInPOT(UniquedGraph &G) {
668 // Construct uniqued nodes, building forward references as necessary.
669 SmallVector<MDNode *, 16> CyclicNodes;
670 for (auto *N : G.POT) {
673 // The node hasn't changed.
678 // Remember whether this node had a placeholder.
679 bool HadPlaceholder(D.Placeholder);
681 // Clone the uniqued node and remap the operands.
682 TempMDNode ClonedN = D.Placeholder ? std::move(D.Placeholder) : N->clone();
683 remapOperands(*ClonedN, [this, &D, &G](Metadata *Old) {
684 if (Optional<Metadata *> MappedOp = getMappedOp(Old))
687 assert(G.Info[Old].ID > D.ID && "Expected a forward reference");
688 return &G.getFwdReference(*cast<MDNode>(Old));
691 auto *NewN = MDNode::replaceWithUniqued(std::move(ClonedN));
692 M.mapToMetadata(N, NewN);
694 // Nodes that were referenced out of order in the POT are involved in a
697 CyclicNodes.push_back(NewN);
701 for (auto *N : CyclicNodes)
702 if (!N->isResolved())
706 Metadata *MDNodeMapper::map(const MDNode &N) {
707 assert(DistinctWorklist.empty() && "MDNodeMapper::map is not recursive");
708 assert(!(M.Flags & RF_NoModuleLevelChanges) &&
709 "MDNodeMapper::map assumes module-level changes");
711 // Require resolved nodes whenever metadata might be remapped.
712 assert(N.isResolved() && "Unexpected unresolved node");
715 N.isUniqued() ? mapTopLevelUniquedNode(N) : mapDistinctNode(N);
716 while (!DistinctWorklist.empty())
717 remapOperands(*DistinctWorklist.pop_back_val(), [this](Metadata *Old) {
718 if (Optional<Metadata *> MappedOp = tryToMapOperand(Old))
720 return mapTopLevelUniquedNode(*cast<MDNode>(Old));
725 Metadata *MDNodeMapper::mapTopLevelUniquedNode(const MDNode &FirstN) {
726 assert(FirstN.isUniqued() && "Expected uniqued node");
728 // Create a post-order traversal of uniqued nodes under FirstN.
730 if (!createPOT(G, FirstN)) {
731 // Return early if no nodes have changed.
732 for (const MDNode *N : G.POT)
734 return &const_cast<MDNode &>(FirstN);
737 // Update graph with all nodes that have changed.
738 G.propagateChanges();
740 // Map all the nodes in the graph.
743 // Return the original node, remapped.
744 return *getMappedOp(&FirstN);
749 struct MapMetadataDisabler {
750 ValueToValueMapTy &VM;
752 MapMetadataDisabler(ValueToValueMapTy &VM) : VM(VM) {
753 VM.disableMapMetadata();
755 ~MapMetadataDisabler() { VM.enableMapMetadata(); }
760 Optional<Metadata *> Mapper::mapSimpleMetadata(const Metadata *MD) {
761 // If the value already exists in the map, use it.
762 if (Optional<Metadata *> NewMD = getVM().getMappedMD(MD))
765 if (isa<MDString>(MD))
766 return const_cast<Metadata *>(MD);
768 // This is a module-level metadata. If nothing at the module level is
769 // changing, use an identity mapping.
770 if ((Flags & RF_NoModuleLevelChanges))
771 return const_cast<Metadata *>(MD);
773 if (auto *CMD = dyn_cast<ConstantAsMetadata>(MD)) {
774 // Disallow recursion into metadata mapping through mapValue.
775 MapMetadataDisabler MMD(getVM());
777 // Don't memoize ConstantAsMetadata. Instead of lasting until the
778 // LLVMContext is destroyed, they can be deleted when the GlobalValue they
779 // reference is destructed. These aren't super common, so the extra
780 // indirection isn't that expensive.
781 return wrapConstantAsMetadata(*CMD, mapValue(CMD->getValue()));
784 assert(isa<MDNode>(MD) && "Expected a metadata node");
789 Metadata *Mapper::mapMetadata(const Metadata *MD) {
790 assert(MD && "Expected valid metadata");
791 assert(!isa<LocalAsMetadata>(MD) && "Unexpected local metadata");
793 if (Optional<Metadata *> NewMD = mapSimpleMetadata(MD))
796 return MDNodeMapper(*this).map(*cast<MDNode>(MD));
799 void Mapper::flush() {
800 // Flush out the worklist of global values.
801 while (!Worklist.empty()) {
802 WorklistEntry E = Worklist.pop_back_val();
803 CurrentMCID = E.MCID;
805 case WorklistEntry::MapGlobalInit:
806 E.Data.GVInit.GV->setInitializer(mapConstant(E.Data.GVInit.Init));
807 remapGlobalObjectMetadata(*E.Data.GVInit.GV);
809 case WorklistEntry::MapAppendingVar: {
810 unsigned PrefixSize = AppendingInits.size() - E.AppendingGVNumNewMembers;
811 mapAppendingVariable(*E.Data.AppendingGV.GV,
812 E.Data.AppendingGV.InitPrefix,
813 E.AppendingGVIsOldCtorDtor,
814 makeArrayRef(AppendingInits).slice(PrefixSize));
815 AppendingInits.resize(PrefixSize);
818 case WorklistEntry::MapGlobalAliasee:
819 E.Data.GlobalAliasee.GA->setAliasee(
820 mapConstant(E.Data.GlobalAliasee.Aliasee));
822 case WorklistEntry::RemapFunction:
823 remapFunction(*E.Data.RemapF);
829 // Finish logic for block addresses now that all global values have been
831 while (!DelayedBBs.empty()) {
832 DelayedBasicBlock DBB = DelayedBBs.pop_back_val();
833 BasicBlock *BB = cast_or_null<BasicBlock>(mapValue(DBB.OldBB));
834 DBB.TempBB->replaceAllUsesWith(BB ? BB : DBB.OldBB);
838 void Mapper::remapInstruction(Instruction *I) {
840 for (Use &Op : I->operands()) {
841 Value *V = mapValue(Op);
842 // If we aren't ignoring missing entries, assert that something happened.
846 assert((Flags & RF_IgnoreMissingLocals) &&
847 "Referenced value not in value map!");
850 // Remap phi nodes' incoming blocks.
851 if (PHINode *PN = dyn_cast<PHINode>(I)) {
852 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
853 Value *V = mapValue(PN->getIncomingBlock(i));
854 // If we aren't ignoring missing entries, assert that something happened.
856 PN->setIncomingBlock(i, cast<BasicBlock>(V));
858 assert((Flags & RF_IgnoreMissingLocals) &&
859 "Referenced block not in value map!");
863 // Remap attached metadata.
864 SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
865 I->getAllMetadata(MDs);
866 for (const auto &MI : MDs) {
867 MDNode *Old = MI.second;
868 MDNode *New = cast_or_null<MDNode>(mapMetadata(Old));
870 I->setMetadata(MI.first, New);
876 // If the instruction's type is being remapped, do so now.
877 if (auto CS = CallSite(I)) {
878 SmallVector<Type *, 3> Tys;
879 FunctionType *FTy = CS.getFunctionType();
880 Tys.reserve(FTy->getNumParams());
881 for (Type *Ty : FTy->params())
882 Tys.push_back(TypeMapper->remapType(Ty));
883 CS.mutateFunctionType(FunctionType::get(
884 TypeMapper->remapType(I->getType()), Tys, FTy->isVarArg()));
887 if (auto *AI = dyn_cast<AllocaInst>(I))
888 AI->setAllocatedType(TypeMapper->remapType(AI->getAllocatedType()));
889 if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
890 GEP->setSourceElementType(
891 TypeMapper->remapType(GEP->getSourceElementType()));
892 GEP->setResultElementType(
893 TypeMapper->remapType(GEP->getResultElementType()));
895 I->mutateType(TypeMapper->remapType(I->getType()));
898 void Mapper::remapGlobalObjectMetadata(GlobalObject &GO) {
899 SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
900 GO.getAllMetadata(MDs);
902 for (const auto &I : MDs)
903 GO.addMetadata(I.first, *cast<MDNode>(mapMetadata(I.second)));
906 void Mapper::remapFunction(Function &F) {
907 // Remap the operands.
908 for (Use &Op : F.operands())
912 // Remap the metadata attachments.
913 remapGlobalObjectMetadata(F);
915 // Remap the argument types.
917 for (Argument &A : F.args())
918 A.mutateType(TypeMapper->remapType(A.getType()));
920 // Remap the instructions.
921 for (BasicBlock &BB : F)
922 for (Instruction &I : BB)
923 remapInstruction(&I);
926 void Mapper::mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
928 ArrayRef<Constant *> NewMembers) {
929 SmallVector<Constant *, 16> Elements;
931 unsigned NumElements =
932 cast<ArrayType>(InitPrefix->getType())->getNumElements();
933 for (unsigned I = 0; I != NumElements; ++I)
934 Elements.push_back(InitPrefix->getAggregateElement(I));
937 PointerType *VoidPtrTy;
940 // FIXME: This upgrade is done during linking to support the C API. See
941 // also IRLinker::linkAppendingVarProto() in IRMover.cpp.
942 VoidPtrTy = Type::getInt8Ty(GV.getContext())->getPointerTo();
943 auto &ST = *cast<StructType>(NewMembers.front()->getType());
944 Type *Tys[3] = {ST.getElementType(0), ST.getElementType(1), VoidPtrTy};
945 EltTy = StructType::get(GV.getContext(), Tys, false);
948 for (auto *V : NewMembers) {
951 auto *S = cast<ConstantStruct>(V);
952 auto *E1 = cast<Constant>(mapValue(S->getOperand(0)));
953 auto *E2 = cast<Constant>(mapValue(S->getOperand(1)));
954 Constant *Null = Constant::getNullValue(VoidPtrTy);
955 NewV = ConstantStruct::get(cast<StructType>(EltTy), E1, E2, Null);
957 NewV = cast_or_null<Constant>(mapValue(V));
959 Elements.push_back(NewV);
962 GV.setInitializer(ConstantArray::get(
963 cast<ArrayType>(GV.getType()->getElementType()), Elements));
966 void Mapper::scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
968 assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
969 assert(MCID < MCs.size() && "Invalid mapping context");
972 WE.Kind = WorklistEntry::MapGlobalInit;
974 WE.Data.GVInit.GV = &GV;
975 WE.Data.GVInit.Init = &Init;
976 Worklist.push_back(WE);
979 void Mapper::scheduleMapAppendingVariable(GlobalVariable &GV,
980 Constant *InitPrefix,
982 ArrayRef<Constant *> NewMembers,
984 assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
985 assert(MCID < MCs.size() && "Invalid mapping context");
988 WE.Kind = WorklistEntry::MapAppendingVar;
990 WE.Data.AppendingGV.GV = &GV;
991 WE.Data.AppendingGV.InitPrefix = InitPrefix;
992 WE.AppendingGVIsOldCtorDtor = IsOldCtorDtor;
993 WE.AppendingGVNumNewMembers = NewMembers.size();
994 Worklist.push_back(WE);
995 AppendingInits.append(NewMembers.begin(), NewMembers.end());
998 void Mapper::scheduleMapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee,
1000 assert(AlreadyScheduled.insert(&GA).second && "Should not reschedule");
1001 assert(MCID < MCs.size() && "Invalid mapping context");
1004 WE.Kind = WorklistEntry::MapGlobalAliasee;
1006 WE.Data.GlobalAliasee.GA = &GA;
1007 WE.Data.GlobalAliasee.Aliasee = &Aliasee;
1008 Worklist.push_back(WE);
1011 void Mapper::scheduleRemapFunction(Function &F, unsigned MCID) {
1012 assert(AlreadyScheduled.insert(&F).second && "Should not reschedule");
1013 assert(MCID < MCs.size() && "Invalid mapping context");
1016 WE.Kind = WorklistEntry::RemapFunction;
1018 WE.Data.RemapF = &F;
1019 Worklist.push_back(WE);
1022 void Mapper::addFlags(RemapFlags Flags) {
1023 assert(!hasWorkToDo() && "Expected to have flushed the worklist");
1024 this->Flags = this->Flags | Flags;
1027 static Mapper *getAsMapper(void *pImpl) {
1028 return reinterpret_cast<Mapper *>(pImpl);
1033 class FlushingMapper {
1037 explicit FlushingMapper(void *pImpl) : M(*getAsMapper(pImpl)) {
1038 assert(!M.hasWorkToDo() && "Expected to be flushed");
1040 ~FlushingMapper() { M.flush(); }
1041 Mapper *operator->() const { return &M; }
1046 ValueMapper::ValueMapper(ValueToValueMapTy &VM, RemapFlags Flags,
1047 ValueMapTypeRemapper *TypeMapper,
1048 ValueMaterializer *Materializer)
1049 : pImpl(new Mapper(VM, Flags, TypeMapper, Materializer)) {}
1051 ValueMapper::~ValueMapper() { delete getAsMapper(pImpl); }
1054 ValueMapper::registerAlternateMappingContext(ValueToValueMapTy &VM,
1055 ValueMaterializer *Materializer) {
1056 return getAsMapper(pImpl)->registerAlternateMappingContext(VM, Materializer);
1059 void ValueMapper::addFlags(RemapFlags Flags) {
1060 FlushingMapper(pImpl)->addFlags(Flags);
1063 Value *ValueMapper::mapValue(const Value &V) {
1064 return FlushingMapper(pImpl)->mapValue(&V);
1067 Constant *ValueMapper::mapConstant(const Constant &C) {
1068 return cast_or_null<Constant>(mapValue(C));
1071 Metadata *ValueMapper::mapMetadata(const Metadata &MD) {
1072 return FlushingMapper(pImpl)->mapMetadata(&MD);
1075 MDNode *ValueMapper::mapMDNode(const MDNode &N) {
1076 return cast_or_null<MDNode>(mapMetadata(N));
1079 void ValueMapper::remapInstruction(Instruction &I) {
1080 FlushingMapper(pImpl)->remapInstruction(&I);
1083 void ValueMapper::remapFunction(Function &F) {
1084 FlushingMapper(pImpl)->remapFunction(F);
1087 void ValueMapper::scheduleMapGlobalInitializer(GlobalVariable &GV,
1090 getAsMapper(pImpl)->scheduleMapGlobalInitializer(GV, Init, MCID);
1093 void ValueMapper::scheduleMapAppendingVariable(GlobalVariable &GV,
1094 Constant *InitPrefix,
1096 ArrayRef<Constant *> NewMembers,
1098 getAsMapper(pImpl)->scheduleMapAppendingVariable(
1099 GV, InitPrefix, IsOldCtorDtor, NewMembers, MCID);
1102 void ValueMapper::scheduleMapGlobalAliasee(GlobalAlias &GA, Constant &Aliasee,
1104 getAsMapper(pImpl)->scheduleMapGlobalAliasee(GA, Aliasee, MCID);
1107 void ValueMapper::scheduleRemapFunction(Function &F, unsigned MCID) {
1108 getAsMapper(pImpl)->scheduleRemapFunction(F, MCID);