1//===- ValueMapper.cpp - Interface shared by lib/Transforms/Utils ---------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the MapValue function, which is shared by various parts of
11// the lib/Transforms/Utils library.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/Utils/ValueMapper.h"
16#include "llvm/IR/Constants.h"
17#include "llvm/IR/Function.h"
18#include "llvm/IR/InlineAsm.h"
19#include "llvm/IR/Instructions.h"
20#include "llvm/IR/Metadata.h"
21using namespace llvm;
22
23// Out of line method to get vtable etc for class.
24void ValueMapTypeRemapper::anchor() {}
25void ValueMaterializer::anchor() {}
26
27Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags,
28                      ValueMapTypeRemapper *TypeMapper,
29                      ValueMaterializer *Materializer) {
30  ValueToValueMapTy::iterator I = VM.find(V);
31
32  // If the value already exists in the map, use it.
33  if (I != VM.end() && I->second) return I->second;
34
35  // If we have a materializer and it can materialize a value, use that.
36  if (Materializer) {
37    if (Value *NewV = Materializer->materializeValueFor(const_cast<Value*>(V)))
38      return VM[V] = NewV;
39  }
40
41  // Global values do not need to be seeded into the VM if they
42  // are using the identity mapping.
43  if (isa<GlobalValue>(V))
44    return VM[V] = const_cast<Value*>(V);
45
46  if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
47    // Inline asm may need *type* remapping.
48    FunctionType *NewTy = IA->getFunctionType();
49    if (TypeMapper) {
50      NewTy = cast<FunctionType>(TypeMapper->remapType(NewTy));
51
52      if (NewTy != IA->getFunctionType())
53        V = InlineAsm::get(NewTy, IA->getAsmString(), IA->getConstraintString(),
54                           IA->hasSideEffects(), IA->isAlignStack());
55    }
56
57    return VM[V] = const_cast<Value*>(V);
58  }
59
60  if (const auto *MDV = dyn_cast<MetadataAsValue>(V)) {
61    const Metadata *MD = MDV->getMetadata();
62    // If this is a module-level metadata and we know that nothing at the module
63    // level is changing, then use an identity mapping.
64    if (!isa<LocalAsMetadata>(MD) && (Flags & RF_NoModuleLevelChanges))
65      return VM[V] = const_cast<Value *>(V);
66
67    auto *MappedMD = MapMetadata(MD, VM, Flags, TypeMapper, Materializer);
68    if (MD == MappedMD || (!MappedMD && (Flags & RF_IgnoreMissingEntries)))
69      return VM[V] = const_cast<Value *>(V);
70
71    // FIXME: This assert crashes during bootstrap, but I think it should be
72    // correct.  For now, just match behaviour from before the metadata/value
73    // split.
74    //
75    //    assert(MappedMD && "Referenced metadata value not in value map");
76    return VM[V] = MetadataAsValue::get(V->getContext(), MappedMD);
77  }
78
79  // Okay, this either must be a constant (which may or may not be mappable) or
80  // is something that is not in the mapping table.
81  Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V));
82  if (!C)
83    return nullptr;
84
85  if (BlockAddress *BA = dyn_cast<BlockAddress>(C)) {
86    Function *F =
87      cast<Function>(MapValue(BA->getFunction(), VM, Flags, TypeMapper, Materializer));
88    BasicBlock *BB = cast_or_null<BasicBlock>(MapValue(BA->getBasicBlock(), VM,
89                                                       Flags, TypeMapper, Materializer));
90    return VM[V] = BlockAddress::get(F, BB ? BB : BA->getBasicBlock());
91  }
92
93  // Otherwise, we have some other constant to remap.  Start by checking to see
94  // if all operands have an identity remapping.
95  unsigned OpNo = 0, NumOperands = C->getNumOperands();
96  Value *Mapped = nullptr;
97  for (; OpNo != NumOperands; ++OpNo) {
98    Value *Op = C->getOperand(OpNo);
99    Mapped = MapValue(Op, VM, Flags, TypeMapper, Materializer);
100    if (Mapped != C) break;
101  }
102
103  // See if the type mapper wants to remap the type as well.
104  Type *NewTy = C->getType();
105  if (TypeMapper)
106    NewTy = TypeMapper->remapType(NewTy);
107
108  // If the result type and all operands match up, then just insert an identity
109  // mapping.
110  if (OpNo == NumOperands && NewTy == C->getType())
111    return VM[V] = C;
112
113  // Okay, we need to create a new constant.  We've already processed some or
114  // all of the operands, set them all up now.
115  SmallVector<Constant*, 8> Ops;
116  Ops.reserve(NumOperands);
117  for (unsigned j = 0; j != OpNo; ++j)
118    Ops.push_back(cast<Constant>(C->getOperand(j)));
119
120  // If one of the operands mismatch, push it and the other mapped operands.
121  if (OpNo != NumOperands) {
122    Ops.push_back(cast<Constant>(Mapped));
123
124    // Map the rest of the operands that aren't processed yet.
125    for (++OpNo; OpNo != NumOperands; ++OpNo)
126      Ops.push_back(MapValue(cast<Constant>(C->getOperand(OpNo)), VM,
127                             Flags, TypeMapper, Materializer));
128  }
129
130  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
131    return VM[V] = CE->getWithOperands(Ops, NewTy);
132  if (isa<ConstantArray>(C))
133    return VM[V] = ConstantArray::get(cast<ArrayType>(NewTy), Ops);
134  if (isa<ConstantStruct>(C))
135    return VM[V] = ConstantStruct::get(cast<StructType>(NewTy), Ops);
136  if (isa<ConstantVector>(C))
137    return VM[V] = ConstantVector::get(Ops);
138  // If this is a no-operand constant, it must be because the type was remapped.
139  if (isa<UndefValue>(C))
140    return VM[V] = UndefValue::get(NewTy);
141  if (isa<ConstantAggregateZero>(C))
142    return VM[V] = ConstantAggregateZero::get(NewTy);
143  assert(isa<ConstantPointerNull>(C));
144  return VM[V] = ConstantPointerNull::get(cast<PointerType>(NewTy));
145}
146
147static Metadata *mapToMetadata(ValueToValueMapTy &VM, const Metadata *Key,
148                     Metadata *Val) {
149  VM.MD()[Key].reset(Val);
150  return Val;
151}
152
153static Metadata *mapToSelf(ValueToValueMapTy &VM, const Metadata *MD) {
154  return mapToMetadata(VM, MD, const_cast<Metadata *>(MD));
155}
156
157static Metadata *MapMetadataImpl(const Metadata *MD,
158                                 SmallVectorImpl<MDNode *> &Cycles,
159                                 ValueToValueMapTy &VM, RemapFlags Flags,
160                                 ValueMapTypeRemapper *TypeMapper,
161                                 ValueMaterializer *Materializer);
162
163static Metadata *mapMetadataOp(Metadata *Op, SmallVectorImpl<MDNode *> &Cycles,
164                               ValueToValueMapTy &VM, RemapFlags Flags,
165                               ValueMapTypeRemapper *TypeMapper,
166                               ValueMaterializer *Materializer) {
167  if (!Op)
168    return nullptr;
169  if (Metadata *MappedOp =
170          MapMetadataImpl(Op, Cycles, VM, Flags, TypeMapper, Materializer))
171    return MappedOp;
172  // Use identity map if MappedOp is null and we can ignore missing entries.
173  if (Flags & RF_IgnoreMissingEntries)
174    return Op;
175
176  // FIXME: This assert crashes during bootstrap, but I think it should be
177  // correct.  For now, just match behaviour from before the metadata/value
178  // split.
179  //
180  //    llvm_unreachable("Referenced metadata not in value map!");
181  return nullptr;
182}
183
184/// \brief Remap nodes.
185///
186/// Insert \c NewNode in the value map, and then remap \c OldNode's operands.
187/// Assumes that \c NewNode is already a clone of \c OldNode.
188///
189/// \pre \c NewNode is a clone of \c OldNode.
190static bool remap(const MDNode *OldNode, MDNode *NewNode,
191                  SmallVectorImpl<MDNode *> &Cycles, ValueToValueMapTy &VM,
192                  RemapFlags Flags, ValueMapTypeRemapper *TypeMapper,
193                  ValueMaterializer *Materializer) {
194  assert(OldNode->getNumOperands() == NewNode->getNumOperands() &&
195         "Expected nodes to match");
196  assert(OldNode->isResolved() && "Expected resolved node");
197  assert(!NewNode->isUniqued() && "Expected non-uniqued node");
198
199  // Map the node upfront so it's available for cyclic references.
200  mapToMetadata(VM, OldNode, NewNode);
201  bool AnyChanged = false;
202  for (unsigned I = 0, E = OldNode->getNumOperands(); I != E; ++I) {
203    Metadata *Old = OldNode->getOperand(I);
204    assert(NewNode->getOperand(I) == Old &&
205           "Expected old operands to already be in place");
206
207    Metadata *New = mapMetadataOp(OldNode->getOperand(I), Cycles, VM, Flags,
208                                  TypeMapper, Materializer);
209    if (Old != New) {
210      AnyChanged = true;
211      NewNode->replaceOperandWith(I, New);
212    }
213  }
214
215  return AnyChanged;
216}
217
218/// \brief Map a distinct MDNode.
219///
220/// Distinct nodes are not uniqued, so they must always recreated.
221static Metadata *mapDistinctNode(const MDNode *Node,
222                                 SmallVectorImpl<MDNode *> &Cycles,
223                                 ValueToValueMapTy &VM, RemapFlags Flags,
224                                 ValueMapTypeRemapper *TypeMapper,
225                                 ValueMaterializer *Materializer) {
226  assert(Node->isDistinct() && "Expected distinct node");
227
228  MDNode *NewMD = MDNode::replaceWithDistinct(Node->clone());
229  remap(Node, NewMD, Cycles, VM, Flags, TypeMapper, Materializer);
230
231  // Track any cycles beneath this node.
232  for (Metadata *Op : NewMD->operands())
233    if (auto *Node = dyn_cast_or_null<MDNode>(Op))
234      if (!Node->isResolved())
235        Cycles.push_back(Node);
236
237  return NewMD;
238}
239
240/// \brief Map a uniqued MDNode.
241///
242/// Uniqued nodes may not need to be recreated (they may map to themselves).
243static Metadata *mapUniquedNode(const MDNode *Node,
244                                SmallVectorImpl<MDNode *> &Cycles,
245                                ValueToValueMapTy &VM, RemapFlags Flags,
246                                ValueMapTypeRemapper *TypeMapper,
247                                ValueMaterializer *Materializer) {
248  assert(Node->isUniqued() && "Expected uniqued node");
249
250  // Create a temporary node upfront in case we have a metadata cycle.
251  auto ClonedMD = Node->clone();
252  if (!remap(Node, ClonedMD.get(), Cycles, VM, Flags, TypeMapper, Materializer))
253    // No operands changed, so use the identity mapping.
254    return mapToSelf(VM, Node);
255
256  // At least one operand has changed, so uniquify the cloned node.
257  return mapToMetadata(VM, Node,
258                       MDNode::replaceWithUniqued(std::move(ClonedMD)));
259}
260
261static Metadata *MapMetadataImpl(const Metadata *MD,
262                                 SmallVectorImpl<MDNode *> &Cycles,
263                                 ValueToValueMapTy &VM, RemapFlags Flags,
264                                 ValueMapTypeRemapper *TypeMapper,
265                                 ValueMaterializer *Materializer) {
266  // If the value already exists in the map, use it.
267  if (Metadata *NewMD = VM.MD().lookup(MD).get())
268    return NewMD;
269
270  if (isa<MDString>(MD))
271    return mapToSelf(VM, MD);
272
273  if (isa<ConstantAsMetadata>(MD))
274    if ((Flags & RF_NoModuleLevelChanges))
275      return mapToSelf(VM, MD);
276
277  if (const auto *VMD = dyn_cast<ValueAsMetadata>(MD)) {
278    Value *MappedV =
279        MapValue(VMD->getValue(), VM, Flags, TypeMapper, Materializer);
280    if (VMD->getValue() == MappedV ||
281        (!MappedV && (Flags & RF_IgnoreMissingEntries)))
282      return mapToSelf(VM, MD);
283
284    // FIXME: This assert crashes during bootstrap, but I think it should be
285    // correct.  For now, just match behaviour from before the metadata/value
286    // split.
287    //
288    //    assert(MappedV && "Referenced metadata not in value map!");
289    if (MappedV)
290      return mapToMetadata(VM, MD, ValueAsMetadata::get(MappedV));
291    return nullptr;
292  }
293
294  // Note: this cast precedes the Flags check so we always get its associated
295  // assertion.
296  const MDNode *Node = cast<MDNode>(MD);
297
298  // If this is a module-level metadata and we know that nothing at the
299  // module level is changing, then use an identity mapping.
300  if (Flags & RF_NoModuleLevelChanges)
301    return mapToSelf(VM, MD);
302
303  // Require resolved nodes whenever metadata might be remapped.
304  assert(Node->isResolved() && "Unexpected unresolved node");
305
306  if (Node->isDistinct())
307    return mapDistinctNode(Node, Cycles, VM, Flags, TypeMapper, Materializer);
308
309  return mapUniquedNode(Node, Cycles, VM, Flags, TypeMapper, Materializer);
310}
311
312Metadata *llvm::MapMetadata(const Metadata *MD, ValueToValueMapTy &VM,
313                            RemapFlags Flags, ValueMapTypeRemapper *TypeMapper,
314                            ValueMaterializer *Materializer) {
315  SmallVector<MDNode *, 8> Cycles;
316  Metadata *NewMD =
317      MapMetadataImpl(MD, Cycles, VM, Flags, TypeMapper, Materializer);
318
319  // Resolve cycles underneath MD.
320  if (NewMD && NewMD != MD) {
321    if (auto *N = dyn_cast<MDNode>(NewMD))
322      if (!N->isResolved())
323        N->resolveCycles();
324
325    for (MDNode *N : Cycles)
326      if (!N->isResolved())
327        N->resolveCycles();
328  } else {
329    // Shouldn't get unresolved cycles if nothing was remapped.
330    assert(Cycles.empty() && "Expected no unresolved cycles");
331  }
332
333  return NewMD;
334}
335
336MDNode *llvm::MapMetadata(const MDNode *MD, ValueToValueMapTy &VM,
337                          RemapFlags Flags, ValueMapTypeRemapper *TypeMapper,
338                          ValueMaterializer *Materializer) {
339  return cast<MDNode>(MapMetadata(static_cast<const Metadata *>(MD), VM, Flags,
340                                  TypeMapper, Materializer));
341}
342
343/// RemapInstruction - Convert the instruction operands from referencing the
344/// current values into those specified by VMap.
345///
346void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap,
347                            RemapFlags Flags, ValueMapTypeRemapper *TypeMapper,
348                            ValueMaterializer *Materializer){
349  // Remap operands.
350  for (User::op_iterator op = I->op_begin(), E = I->op_end(); op != E; ++op) {
351    Value *V = MapValue(*op, VMap, Flags, TypeMapper, Materializer);
352    // If we aren't ignoring missing entries, assert that something happened.
353    if (V)
354      *op = V;
355    else
356      assert((Flags & RF_IgnoreMissingEntries) &&
357             "Referenced value not in value map!");
358  }
359
360  // Remap phi nodes' incoming blocks.
361  if (PHINode *PN = dyn_cast<PHINode>(I)) {
362    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
363      Value *V = MapValue(PN->getIncomingBlock(i), VMap, Flags);
364      // If we aren't ignoring missing entries, assert that something happened.
365      if (V)
366        PN->setIncomingBlock(i, cast<BasicBlock>(V));
367      else
368        assert((Flags & RF_IgnoreMissingEntries) &&
369               "Referenced block not in value map!");
370    }
371  }
372
373  // Remap attached metadata.
374  SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
375  I->getAllMetadata(MDs);
376  for (SmallVectorImpl<std::pair<unsigned, MDNode *>>::iterator
377           MI = MDs.begin(),
378           ME = MDs.end();
379       MI != ME; ++MI) {
380    MDNode *Old = MI->second;
381    MDNode *New = MapMetadata(Old, VMap, Flags, TypeMapper, Materializer);
382    if (New != Old)
383      I->setMetadata(MI->first, New);
384  }
385
386  // If the instruction's type is being remapped, do so now.
387  if (TypeMapper)
388    I->mutateType(TypeMapper->remapType(I->getType()));
389}
390