1 //===- ValueMapper.cpp - Interface shared by lib/Transforms/Utils ---------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines the MapValue function, which is shared by various parts of
10 // the lib/Transforms/Utils library.
12 //===----------------------------------------------------------------------===//
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"
48 // Out of line method to get vtable etc for class.
49 void ValueMapTypeRemapper::anchor() {}
50 void ValueMaterializer::anchor() {}
54 /// A basic block used in a BlockAddress whose function body is not yet
56 struct DelayedBasicBlock {
58 std::unique_ptr<BasicBlock> TempBB;
60 DelayedBasicBlock(const BlockAddress &Old)
61 : OldBB(Old.getBasicBlock()),
62 TempBB(BasicBlock::Create(Old.getContext())) {}
65 struct WorklistEntry {
69 MapGlobalIndirectSymbol,
76 struct AppendingGVTy {
80 struct GlobalIndirectSymbolTy {
81 GlobalIndirectSymbol *GIS;
87 unsigned AppendingGVIsOldCtorDtor : 1;
88 unsigned AppendingGVNumNewMembers;
91 AppendingGVTy AppendingGV;
92 GlobalIndirectSymbolTy GlobalIndirectSymbol;
97 struct MappingContext {
98 ValueToValueMapTy *VM;
99 ValueMaterializer *Materializer = nullptr;
101 /// Construct a MappingContext with a value map and materializer.
102 explicit MappingContext(ValueToValueMapTy &VM,
103 ValueMaterializer *Materializer = nullptr)
104 : VM(&VM), Materializer(Materializer) {}
108 friend class MDNodeMapper;
111 DenseSet<GlobalValue *> AlreadyScheduled;
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;
123 Mapper(ValueToValueMapTy &VM, RemapFlags Flags,
124 ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer)
125 : Flags(Flags), TypeMapper(TypeMapper),
126 MCs(1, MappingContext(VM, Materializer)) {}
128 /// ValueMapper should explicitly call \a flush() before destruction.
129 ~Mapper() { assert(!hasWorkToDo() && "Expected to be flushed"); }
131 bool hasWorkToDo() const { return !Worklist.empty(); }
134 registerAlternateMappingContext(ValueToValueMapTy &VM,
135 ValueMaterializer *Materializer = nullptr) {
136 MCs.push_back(MappingContext(VM, Materializer));
137 return MCs.size() - 1;
140 void addFlags(RemapFlags Flags);
142 void remapGlobalObjectMetadata(GlobalObject &GO);
144 Value *mapValue(const Value *V);
145 void remapInstruction(Instruction *I);
146 void remapFunction(Function &F);
148 Constant *mapConstant(const Constant *C) {
149 return cast_or_null<Constant>(mapValue(C));
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);
158 void scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
160 void scheduleMapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
162 ArrayRef<Constant *> NewMembers,
164 void scheduleMapGlobalIndirectSymbol(GlobalIndirectSymbol &GIS, Constant &Target,
166 void scheduleRemapFunction(Function &F, unsigned MCID);
171 void mapGlobalInitializer(GlobalVariable &GV, Constant &Init);
172 void mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
174 ArrayRef<Constant *> NewMembers);
175 void mapGlobalIndirectSymbol(GlobalIndirectSymbol &GIS, Constant &Target);
176 void remapFunction(Function &F, ValueToValueMapTy &VM);
178 ValueToValueMapTy &getVM() { return *MCs[CurrentMCID].VM; }
179 ValueMaterializer *getMaterializer() { return MCs[CurrentMCID].Materializer; }
181 Value *mapBlockAddress(const BlockAddress &BA);
183 /// Map metadata that doesn't require visiting operands.
184 Optional<Metadata *> mapSimpleMetadata(const Metadata *MD);
186 Metadata *mapToMetadata(const Metadata *Key, Metadata *Val);
187 Metadata *mapToSelf(const Metadata *MD);
193 /// Data about a node in \a UniquedGraph.
195 bool HasChanged = false;
196 unsigned ID = std::numeric_limits<unsigned>::max();
197 TempMDNode Placeholder;
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.
205 /// Propagate changed operands through the post-order traversal.
207 /// Iteratively update \a Data::HasChanged for each node based on \a
208 /// Data::HasChanged of its operands, until fixed point.
209 void propagateChanges();
211 /// Get a forward reference to a node to use as an operand.
212 Metadata &getFwdReference(MDNode &Op);
215 /// Worklist of distinct nodes whose operands need to be remapped.
216 SmallVector<MDNode *, 16> DistinctWorklist;
218 // Storage for a UniquedGraph.
219 SmallDenseMap<const Metadata *, Data, 32> InfoStorage;
220 SmallVector<MDNode *, 16> POTStorage;
223 MDNodeMapper(Mapper &M) : M(M) {}
225 /// Map a metadata node (and its transitive operands).
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.
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.
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().
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);
246 /// Map a top-level uniqued node and the uniqued subgraph underneath it.
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.
253 /// The algorithm works as follows:
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.
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.
263 /// 3. \a mapNodesInPOT(): map the uniqued nodes, creating new uniqued nodes
264 /// (referencing new operands) where necessary.
265 Metadata *mapTopLevelUniquedNode(const MDNode &FirstN);
267 /// Try to map the operand of an \a MDNode.
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().
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);
277 /// Map a distinct node.
279 /// Return the mapping for the distinct node \c N, saving the result in \a
280 /// DistinctWorklist for later remapping.
282 /// \pre \c N is not yet mapped.
283 /// \pre \c N.isDistinct().
284 MDNode *mapDistinctNode(const MDNode &N);
286 /// Get a previously mapped node.
287 Optional<Metadata *> getMappedOp(const Metadata *Op) const;
289 /// Create a post-order traversal of an unmapped uniqued node subgraph.
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.
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.
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);
305 /// Visit the operands of a uniqued node in the POT.
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.
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);
315 /// Map all the nodes in the given uniqued graph.
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.
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);
327 /// Remap a node's operands using the given functor.
329 /// Iterate through the operands of \c N and update them in place using \c
332 /// \pre N.isDistinct() or N.isTemporary().
333 template <class OperandMapper>
334 void remapOperands(MDNode &N, OperandMapper mapOperand);
337 } // end anonymous namespace
339 Value *Mapper::mapValue(const Value *V) {
340 ValueToValueMapTy::iterator I = getVM().find(V);
342 // If the value already exists in the map, use it.
343 if (I != getVM().end()) {
344 assert(I->second && "Unexpected null mapping");
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))) {
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)
361 return getVM()[V] = const_cast<Value *>(V);
364 if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
365 // Inline asm may need *type* remapping.
366 FunctionType *NewTy = IA->getFunctionType();
368 NewTy = cast<FunctionType>(TypeMapper->remapType(NewTy));
370 if (NewTy != IA->getFunctionType())
371 V = InlineAsm::get(NewTy, IA->getAsmString(), IA->getConstraintString(),
372 IA->hasSideEffects(), IA->isAlignStack(),
376 return getVM()[V] = const_cast<Value *>(V);
379 if (const auto *MDV = dyn_cast<MetadataAsValue>(V)) {
380 const Metadata *MD = MDV->getMetadata();
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));
390 // FIXME: always return nullptr once Verifier::verifyDominatesUse()
391 // ensures metadata operands only reference defined SSA values.
392 return (Flags & RF_IgnoreMissingLocals)
394 : MetadataAsValue::get(V->getContext(),
395 MDTuple::get(V->getContext(), None));
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);
403 // Map the metadata and turn it into a value.
404 auto *MappedMD = mapMetadata(MD);
406 return getVM()[V] = const_cast<Value *>(V);
407 return getVM()[V] = MetadataAsValue::get(V->getContext(), MappedMD);
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));
416 if (BlockAddress *BA = dyn_cast<BlockAddress>(C))
417 return mapBlockAddress(*BA);
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");
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);
440 // See if the type mapper wants to remap the type as well.
441 Type *NewTy = C->getType();
443 NewTy = TypeMapper->remapType(NewTy);
445 // If the result type and all operands match up, then just insert an identity
447 if (OpNo == NumOperands && NewTy == C->getType())
448 return getVM()[V] = C;
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)));
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));
461 // Map the rest of the operands that aren't processed yet.
462 for (++OpNo; OpNo != NumOperands; ++OpNo) {
463 Mapped = mapValueOrNull(C->getOperand(OpNo));
466 Ops.push_back(cast<Constant>(Mapped));
469 Type *NewSrcTy = nullptr;
471 if (auto *GEPO = dyn_cast<GEPOperator>(C))
472 NewSrcTy = TypeMapper->remapType(GEPO->getSourceElementType());
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));
491 Value *Mapper::mapBlockAddress(const BlockAddress &BA) {
492 Function *F = cast<Function>(mapValue(BA.getFunction()));
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
499 DelayedBBs.push_back(DelayedBasicBlock(BA));
500 BB = DelayedBBs.back().TempBB.get();
502 BB = cast_or_null<BasicBlock>(mapValue(BA.getBasicBlock()));
505 return getVM()[&BA] = BlockAddress::get(F, BB ? BB : BA.getBasicBlock());
508 Metadata *Mapper::mapToMetadata(const Metadata *Key, Metadata *Val) {
509 getVM().MD()[Key].reset(Val);
513 Metadata *Mapper::mapToSelf(const Metadata *MD) {
514 return mapToMetadata(MD, const_cast<Metadata *>(MD));
517 Optional<Metadata *> MDNodeMapper::tryToMapOperand(const Metadata *Op) {
521 if (Optional<Metadata *> MappedOp = M.mapSimpleMetadata(Op)) {
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");
528 assert((isa<MDString>(Op) || M.getVM().getMappedMD(Op)) &&
529 "Expected result to be memoized");
534 const MDNode &N = *cast<MDNode>(Op);
536 return mapDistinctNode(N);
540 static 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());
550 MDNode *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)
556 : M.mapToMetadata(&N, cloneOrBuildODR(N))));
557 return DistinctWorklist.back();
560 static ConstantAsMetadata *wrapConstantAsMetadata(const ConstantAsMetadata &CMD,
562 if (CMD.getValue() == MappedV)
563 return const_cast<ConstantAsMetadata *>(&CMD);
564 return MappedV ? ConstantAsMetadata::getConstant(MappedV) : nullptr;
567 Optional<Metadata *> MDNodeMapper::getMappedOp(const Metadata *Op) const {
571 if (Optional<Metadata *> MappedOp = M.getVM().getMappedMD(Op))
574 if (isa<MDString>(Op))
575 return const_cast<Metadata *>(Op);
577 if (auto *CMD = dyn_cast<ConstantAsMetadata>(Op))
578 return wrapConstantAsMetadata(*CMD, M.getVM().lookup(CMD->getValue()));
583 Metadata &MDNodeMapper::UniquedGraph::getFwdReference(MDNode &Op) {
584 auto Where = Info.find(&Op);
585 assert(Where != Info.end() && "Expected a valid reference");
587 auto &OpD = Where->second;
591 // Lazily construct a temporary node.
592 if (!OpD.Placeholder)
593 OpD.Placeholder = Op.clone();
595 return *OpD.Placeholder;
598 template <class OperandMapper>
599 void 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);
606 N.replaceOperandWith(I, New);
612 /// An entry in the worklist for the post-order traversal.
613 struct POTWorklistEntry {
614 MDNode *N; ///< Current node.
615 MDNode::op_iterator Op; ///< Current operand of \c N.
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;
621 POTWorklistEntry(MDNode &N) : N(&N), Op(N.op_begin()) {}
624 } // end anonymous namespace
626 bool 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");
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));
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;
650 G.POT.push_back(WE.N);
652 // Pop the node off the worklist.
658 MDNode *MDNodeMapper::visitOperands(UniquedGraph &G, MDNode::op_iterator &I,
659 MDNode::op_iterator E, bool &HasChanged) {
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;
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.
678 void MDNodeMapper::UniquedGraph::propagateChanges() {
682 for (MDNode *N : POT) {
687 if (llvm::none_of(N->operands(), [&](const Metadata *Op) {
688 auto Where = Info.find(Op);
689 return Where != Info.end() && Where->second.HasChanged;
693 AnyChanges = D.HasChanged = true;
695 } while (AnyChanges);
698 void MDNodeMapper::mapNodesInPOT(UniquedGraph &G) {
699 // Construct uniqued nodes, building forward references as necessary.
700 SmallVector<MDNode *, 16> CyclicNodes;
701 for (auto *N : G.POT) {
704 // The node hasn't changed.
709 // Remember whether this node had a placeholder.
710 bool HadPlaceholder(D.Placeholder);
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))
718 assert(G.Info[Old].ID > D.ID && "Expected a forward reference");
719 return &G.getFwdReference(*cast<MDNode>(Old));
722 auto *NewN = MDNode::replaceWithUniqued(std::move(ClonedN));
723 M.mapToMetadata(N, NewN);
725 // Nodes that were referenced out of order in the POT are involved in a
728 CyclicNodes.push_back(NewN);
732 for (auto *N : CyclicNodes)
733 if (!N->isResolved())
737 Metadata *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");
742 // Require resolved nodes whenever metadata might be remapped.
743 assert(N.isResolved() && "Unexpected unresolved node");
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))
751 return mapTopLevelUniquedNode(*cast<MDNode>(Old));
756 Metadata *MDNodeMapper::mapTopLevelUniquedNode(const MDNode &FirstN) {
757 assert(FirstN.isUniqued() && "Expected uniqued node");
759 // Create a post-order traversal of uniqued nodes under FirstN.
761 if (!createPOT(G, FirstN)) {
762 // Return early if no nodes have changed.
763 for (const MDNode *N : G.POT)
765 return &const_cast<MDNode &>(FirstN);
768 // Update graph with all nodes that have changed.
769 G.propagateChanges();
771 // Map all the nodes in the graph.
774 // Return the original node, remapped.
775 return *getMappedOp(&FirstN);
778 Optional<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))
783 if (isa<MDString>(MD))
784 return const_cast<Metadata *>(MD);
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);
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()));
799 assert(isa<MDNode>(MD) && "Expected a metadata node");
804 Metadata *Mapper::mapMetadata(const Metadata *MD) {
805 assert(MD && "Expected valid metadata");
806 assert(!isa<LocalAsMetadata>(MD) && "Unexpected local metadata");
808 if (Optional<Metadata *> NewMD = mapSimpleMetadata(MD))
811 return MDNodeMapper(*this).map(*cast<MDNode>(MD));
814 void 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;
820 case WorklistEntry::MapGlobalInit:
821 E.Data.GVInit.GV->setInitializer(mapConstant(E.Data.GVInit.Init));
822 remapGlobalObjectMetadata(*E.Data.GVInit.GV);
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);
833 case WorklistEntry::MapGlobalIndirectSymbol:
834 E.Data.GlobalIndirectSymbol.GIS->setIndirectSymbol(
835 mapConstant(E.Data.GlobalIndirectSymbol.Target));
837 case WorklistEntry::RemapFunction:
838 remapFunction(*E.Data.RemapF);
844 // Finish logic for block addresses now that all global values have been
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);
853 void Mapper::remapInstruction(Instruction *I) {
855 for (Use &Op : I->operands()) {
856 Value *V = mapValue(Op);
857 // If we aren't ignoring missing entries, assert that something happened.
861 assert((Flags & RF_IgnoreMissingLocals) &&
862 "Referenced value not in value map!");
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.
871 PN->setIncomingBlock(i, cast<BasicBlock>(V));
873 assert((Flags & RF_IgnoreMissingLocals) &&
874 "Referenced block not in value map!");
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));
885 I->setMetadata(MI.first, New);
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()));
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();
909 Attrs = Attrs.removeAttribute(C, i, Attribute::ByVal);
910 Attrs = Attrs.addAttribute(
911 C, i, Attribute::getWithByValType(C, TypeMapper->remapType(Ty)));
914 CS.setAttributes(Attrs);
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()));
925 I->mutateType(TypeMapper->remapType(I->getType()));
928 void Mapper::remapGlobalObjectMetadata(GlobalObject &GO) {
929 SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
930 GO.getAllMetadata(MDs);
932 for (const auto &I : MDs)
933 GO.addMetadata(I.first, *cast<MDNode>(mapMetadata(I.second)));
936 void Mapper::remapFunction(Function &F) {
937 // Remap the operands.
938 for (Use &Op : F.operands())
942 // Remap the metadata attachments.
943 remapGlobalObjectMetadata(F);
945 // Remap the argument types.
947 for (Argument &A : F.args())
948 A.mutateType(TypeMapper->remapType(A.getType()));
950 // Remap the instructions.
951 for (BasicBlock &BB : F)
952 for (Instruction &I : BB)
953 remapInstruction(&I);
956 void Mapper::mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
958 ArrayRef<Constant *> NewMembers) {
959 SmallVector<Constant *, 16> Elements;
961 unsigned NumElements =
962 cast<ArrayType>(InitPrefix->getType())->getNumElements();
963 for (unsigned I = 0; I != NumElements; ++I)
964 Elements.push_back(InitPrefix->getAggregateElement(I));
967 PointerType *VoidPtrTy;
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);
978 for (auto *V : NewMembers) {
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);
987 NewV = cast_or_null<Constant>(mapValue(V));
989 Elements.push_back(NewV);
992 GV.setInitializer(ConstantArray::get(
993 cast<ArrayType>(GV.getType()->getElementType()), Elements));
996 void Mapper::scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
998 assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
999 assert(MCID < MCs.size() && "Invalid mapping context");
1002 WE.Kind = WorklistEntry::MapGlobalInit;
1004 WE.Data.GVInit.GV = &GV;
1005 WE.Data.GVInit.Init = &Init;
1006 Worklist.push_back(WE);
1009 void Mapper::scheduleMapAppendingVariable(GlobalVariable &GV,
1010 Constant *InitPrefix,
1012 ArrayRef<Constant *> NewMembers,
1014 assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
1015 assert(MCID < MCs.size() && "Invalid mapping context");
1018 WE.Kind = WorklistEntry::MapAppendingVar;
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());
1028 void 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");
1034 WE.Kind = WorklistEntry::MapGlobalIndirectSymbol;
1036 WE.Data.GlobalIndirectSymbol.GIS = &GIS;
1037 WE.Data.GlobalIndirectSymbol.Target = &Target;
1038 Worklist.push_back(WE);
1041 void Mapper::scheduleRemapFunction(Function &F, unsigned MCID) {
1042 assert(AlreadyScheduled.insert(&F).second && "Should not reschedule");
1043 assert(MCID < MCs.size() && "Invalid mapping context");
1046 WE.Kind = WorklistEntry::RemapFunction;
1048 WE.Data.RemapF = &F;
1049 Worklist.push_back(WE);
1052 void Mapper::addFlags(RemapFlags Flags) {
1053 assert(!hasWorkToDo() && "Expected to have flushed the worklist");
1054 this->Flags = this->Flags | Flags;
1057 static Mapper *getAsMapper(void *pImpl) {
1058 return reinterpret_cast<Mapper *>(pImpl);
1063 class FlushingMapper {
1067 explicit FlushingMapper(void *pImpl) : M(*getAsMapper(pImpl)) {
1068 assert(!M.hasWorkToDo() && "Expected to be flushed");
1071 ~FlushingMapper() { M.flush(); }
1073 Mapper *operator->() const { return &M; }
1076 } // end anonymous namespace
1078 ValueMapper::ValueMapper(ValueToValueMapTy &VM, RemapFlags Flags,
1079 ValueMapTypeRemapper *TypeMapper,
1080 ValueMaterializer *Materializer)
1081 : pImpl(new Mapper(VM, Flags, TypeMapper, Materializer)) {}
1083 ValueMapper::~ValueMapper() { delete getAsMapper(pImpl); }
1086 ValueMapper::registerAlternateMappingContext(ValueToValueMapTy &VM,
1087 ValueMaterializer *Materializer) {
1088 return getAsMapper(pImpl)->registerAlternateMappingContext(VM, Materializer);
1091 void ValueMapper::addFlags(RemapFlags Flags) {
1092 FlushingMapper(pImpl)->addFlags(Flags);
1095 Value *ValueMapper::mapValue(const Value &V) {
1096 return FlushingMapper(pImpl)->mapValue(&V);
1099 Constant *ValueMapper::mapConstant(const Constant &C) {
1100 return cast_or_null<Constant>(mapValue(C));
1103 Metadata *ValueMapper::mapMetadata(const Metadata &MD) {
1104 return FlushingMapper(pImpl)->mapMetadata(&MD);
1107 MDNode *ValueMapper::mapMDNode(const MDNode &N) {
1108 return cast_or_null<MDNode>(mapMetadata(N));
1111 void ValueMapper::remapInstruction(Instruction &I) {
1112 FlushingMapper(pImpl)->remapInstruction(&I);
1115 void ValueMapper::remapFunction(Function &F) {
1116 FlushingMapper(pImpl)->remapFunction(F);
1119 void ValueMapper::scheduleMapGlobalInitializer(GlobalVariable &GV,
1122 getAsMapper(pImpl)->scheduleMapGlobalInitializer(GV, Init, MCID);
1125 void ValueMapper::scheduleMapAppendingVariable(GlobalVariable &GV,
1126 Constant *InitPrefix,
1128 ArrayRef<Constant *> NewMembers,
1130 getAsMapper(pImpl)->scheduleMapAppendingVariable(
1131 GV, InitPrefix, IsOldCtorDtor, NewMembers, MCID);
1134 void ValueMapper::scheduleMapGlobalIndirectSymbol(GlobalIndirectSymbol &GIS,
1137 getAsMapper(pImpl)->scheduleMapGlobalIndirectSymbol(GIS, Target, MCID);
1140 void ValueMapper::scheduleRemapFunction(Function &F, unsigned MCID) {
1141 getAsMapper(pImpl)->scheduleRemapFunction(F, MCID);