LLVM  15.0.0git
ValueMapper.cpp
Go to the documentation of this file.
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 
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"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/Function.h"
29 #include "llvm/IR/GlobalAlias.h"
30 #include "llvm/IR/GlobalIFunc.h"
31 #include "llvm/IR/GlobalObject.h"
32 #include "llvm/IR/GlobalVariable.h"
33 #include "llvm/IR/InlineAsm.h"
34 #include "llvm/IR/Instruction.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/Metadata.h"
37 #include "llvm/IR/Operator.h"
38 #include "llvm/IR/Type.h"
39 #include "llvm/IR/Value.h"
40 #include "llvm/Support/Casting.h"
41 #include "llvm/Support/Debug.h"
42 #include <cassert>
43 #include <limits>
44 #include <memory>
45 #include <utility>
46 
47 using namespace llvm;
48 
49 #define DEBUG_TYPE "value-mapper"
50 
51 // Out of line method to get vtable etc for class.
52 void ValueMapTypeRemapper::anchor() {}
53 void ValueMaterializer::anchor() {}
54 
55 namespace {
56 
57 /// A basic block used in a BlockAddress whose function body is not yet
58 /// materialized.
59 struct DelayedBasicBlock {
60  BasicBlock *OldBB;
61  std::unique_ptr<BasicBlock> TempBB;
62 
63  DelayedBasicBlock(const BlockAddress &Old)
64  : OldBB(Old.getBasicBlock()),
65  TempBB(BasicBlock::Create(Old.getContext())) {}
66 };
67 
68 struct WorklistEntry {
69  enum EntryKind {
70  MapGlobalInit,
71  MapAppendingVar,
72  MapAliasOrIFunc,
74  };
75  struct GVInitTy {
76  GlobalVariable *GV;
77  Constant *Init;
78  };
79  struct AppendingGVTy {
80  GlobalVariable *GV;
81  Constant *InitPrefix;
82  };
83  struct AliasOrIFuncTy {
84  GlobalValue *GV;
86  };
87 
88  unsigned Kind : 2;
89  unsigned MCID : 29;
90  unsigned AppendingGVIsOldCtorDtor : 1;
91  unsigned AppendingGVNumNewMembers;
92  union {
93  GVInitTy GVInit;
94  AppendingGVTy AppendingGV;
95  AliasOrIFuncTy AliasOrIFunc;
96  Function *RemapF;
97  } Data;
98 };
99 
100 struct MappingContext {
101  ValueToValueMapTy *VM;
102  ValueMaterializer *Materializer = nullptr;
103 
104  /// Construct a MappingContext with a value map and materializer.
105  explicit MappingContext(ValueToValueMapTy &VM,
106  ValueMaterializer *Materializer = nullptr)
107  : VM(&VM), Materializer(Materializer) {}
108 };
109 
110 class Mapper {
111  friend class MDNodeMapper;
112 
113 #ifndef NDEBUG
114  DenseSet<GlobalValue *> AlreadyScheduled;
115 #endif
116 
117  RemapFlags Flags;
118  ValueMapTypeRemapper *TypeMapper;
119  unsigned CurrentMCID = 0;
123  SmallVector<Constant *, 16> AppendingInits;
124 
125 public:
126  Mapper(ValueToValueMapTy &VM, RemapFlags Flags,
127  ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer)
128  : Flags(Flags), TypeMapper(TypeMapper),
129  MCs(1, MappingContext(VM, Materializer)) {}
130 
131  /// ValueMapper should explicitly call \a flush() before destruction.
132  ~Mapper() { assert(!hasWorkToDo() && "Expected to be flushed"); }
133 
134  bool hasWorkToDo() const { return !Worklist.empty(); }
135 
136  unsigned
137  registerAlternateMappingContext(ValueToValueMapTy &VM,
138  ValueMaterializer *Materializer = nullptr) {
139  MCs.push_back(MappingContext(VM, Materializer));
140  return MCs.size() - 1;
141  }
142 
143  void addFlags(RemapFlags Flags);
144 
145  void remapGlobalObjectMetadata(GlobalObject &GO);
146 
147  Value *mapValue(const Value *V);
148  void remapInstruction(Instruction *I);
149  void remapFunction(Function &F);
150 
151  Constant *mapConstant(const Constant *C) {
152  return cast_or_null<Constant>(mapValue(C));
153  }
154 
155  /// Map metadata.
156  ///
157  /// Find the mapping for MD. Guarantees that the return will be resolved
158  /// (not an MDNode, or MDNode::isResolved() returns true).
159  Metadata *mapMetadata(const Metadata *MD);
160 
161  void scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
162  unsigned MCID);
163  void scheduleMapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
164  bool IsOldCtorDtor,
165  ArrayRef<Constant *> NewMembers,
166  unsigned MCID);
167  void scheduleMapAliasOrIFunc(GlobalValue &GV, Constant &Target,
168  unsigned MCID);
169  void scheduleRemapFunction(Function &F, unsigned MCID);
170 
171  void flush();
172 
173 private:
174  void mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
175  bool IsOldCtorDtor,
176  ArrayRef<Constant *> NewMembers);
177 
178  ValueToValueMapTy &getVM() { return *MCs[CurrentMCID].VM; }
179  ValueMaterializer *getMaterializer() { return MCs[CurrentMCID].Materializer; }
180 
181  Value *mapBlockAddress(const BlockAddress &BA);
182 
183  /// Map metadata that doesn't require visiting operands.
184  Optional<Metadata *> mapSimpleMetadata(const Metadata *MD);
185 
186  Metadata *mapToMetadata(const Metadata *Key, Metadata *Val);
187  Metadata *mapToSelf(const Metadata *MD);
188 };
189 
190 class MDNodeMapper {
191  Mapper &M;
192 
193  /// Data about a node in \a UniquedGraph.
194  struct Data {
195  bool HasChanged = false;
197  TempMDNode Placeholder;
198  };
199 
200  /// A graph of uniqued nodes.
201  struct UniquedGraph {
203  SmallVector<MDNode *, 16> POT; // Post-order traversal.
204 
205  /// Propagate changed operands through the post-order traversal.
206  ///
207  /// Iteratively update \a Data::HasChanged for each node based on \a
208  /// Data::HasChanged of its operands, until fixed point.
209  void propagateChanges();
210 
211  /// Get a forward reference to a node to use as an operand.
212  Metadata &getFwdReference(MDNode &Op);
213  };
214 
215  /// Worklist of distinct nodes whose operands need to be remapped.
216  SmallVector<MDNode *, 16> DistinctWorklist;
217 
218  // Storage for a UniquedGraph.
220  SmallVector<MDNode *, 16> POTStorage;
221 
222 public:
223  MDNodeMapper(Mapper &M) : M(M) {}
224 
225  /// Map a metadata node (and its transitive operands).
226  ///
227  /// Map all the (unmapped) nodes in the subgraph under \c N. The iterative
228  /// algorithm handles distinct nodes and uniqued node subgraphs using
229  /// different strategies.
230  ///
231  /// Distinct nodes are immediately mapped and added to \a DistinctWorklist
232  /// using \a mapDistinctNode(). Their mapping can always be computed
233  /// immediately without visiting operands, even if their operands change.
234  ///
235  /// The mapping for uniqued nodes depends on whether their operands change.
236  /// \a mapTopLevelUniquedNode() traverses the transitive uniqued subgraph of
237  /// a node to calculate uniqued node mappings in bulk. Distinct leafs are
238  /// added to \a DistinctWorklist with \a mapDistinctNode().
239  ///
240  /// After mapping \c N itself, this function remaps the operands of the
241  /// distinct nodes in \a DistinctWorklist until the entire subgraph under \c
242  /// N has been mapped.
243  Metadata *map(const MDNode &N);
244 
245 private:
246  /// Map a top-level uniqued node and the uniqued subgraph underneath it.
247  ///
248  /// This builds up a post-order traversal of the (unmapped) uniqued subgraph
249  /// underneath \c FirstN and calculates the nodes' mapping. Each node uses
250  /// the identity mapping (\a Mapper::mapToSelf()) as long as all of its
251  /// operands uses the identity mapping.
252  ///
253  /// The algorithm works as follows:
254  ///
255  /// 1. \a createPOT(): traverse the uniqued subgraph under \c FirstN and
256  /// save the post-order traversal in the given \a UniquedGraph, tracking
257  /// nodes' operands change.
258  ///
259  /// 2. \a UniquedGraph::propagateChanges(): propagate changed operands
260  /// through the \a UniquedGraph until fixed point, following the rule
261  /// that if a node changes, any node that references must also change.
262  ///
263  /// 3. \a mapNodesInPOT(): map the uniqued nodes, creating new uniqued nodes
264  /// (referencing new operands) where necessary.
265  Metadata *mapTopLevelUniquedNode(const MDNode &FirstN);
266 
267  /// Try to map the operand of an \a MDNode.
268  ///
269  /// If \c Op is already mapped, return the mapping. If it's not an \a
270  /// MDNode, compute and return the mapping. If it's a distinct \a MDNode,
271  /// return the result of \a mapDistinctNode().
272  ///
273  /// \return None if \c Op is an unmapped uniqued \a MDNode.
274  /// \post getMappedOp(Op) only returns None if this returns None.
275  Optional<Metadata *> tryToMapOperand(const Metadata *Op);
276 
277  /// Map a distinct node.
278  ///
279  /// Return the mapping for the distinct node \c N, saving the result in \a
280  /// DistinctWorklist for later remapping.
281  ///
282  /// \pre \c N is not yet mapped.
283  /// \pre \c N.isDistinct().
284  MDNode *mapDistinctNode(const MDNode &N);
285 
286  /// Get a previously mapped node.
288 
289  /// Create a post-order traversal of an unmapped uniqued node subgraph.
290  ///
291  /// This traverses the metadata graph deeply enough to map \c FirstN. It
292  /// uses \a tryToMapOperand() (via \a Mapper::mapSimplifiedNode()), so any
293  /// metadata that has already been mapped will not be part of the POT.
294  ///
295  /// Each node that has a changed operand from outside the graph (e.g., a
296  /// distinct node, an already-mapped uniqued node, or \a ConstantAsMetadata)
297  /// is marked with \a Data::HasChanged.
298  ///
299  /// \return \c true if any nodes in \c G have \a Data::HasChanged.
300  /// \post \c G.POT is a post-order traversal ending with \c FirstN.
301  /// \post \a Data::hasChanged in \c G.Info indicates whether any node needs
302  /// to change because of operands outside the graph.
303  bool createPOT(UniquedGraph &G, const MDNode &FirstN);
304 
305  /// Visit the operands of a uniqued node in the POT.
306  ///
307  /// Visit the operands in the range from \c I to \c E, returning the first
308  /// uniqued node we find that isn't yet in \c G. \c I is always advanced to
309  /// where to continue the loop through the operands.
310  ///
311  /// This sets \c HasChanged if any of the visited operands change.
312  MDNode *visitOperands(UniquedGraph &G, MDNode::op_iterator &I,
313  MDNode::op_iterator E, bool &HasChanged);
314 
315  /// Map all the nodes in the given uniqued graph.
316  ///
317  /// This visits all the nodes in \c G in post-order, using the identity
318  /// mapping or creating a new node depending on \a Data::HasChanged.
319  ///
320  /// \pre \a getMappedOp() returns None for nodes in \c G, but not for any of
321  /// their operands outside of \c G.
322  /// \pre \a Data::HasChanged is true for a node in \c G iff any of its
323  /// operands have changed.
324  /// \post \a getMappedOp() returns the mapped node for every node in \c G.
325  void mapNodesInPOT(UniquedGraph &G);
326 
327  /// Remap a node's operands using the given functor.
328  ///
329  /// Iterate through the operands of \c N and update them in place using \c
330  /// mapOperand.
331  ///
332  /// \pre N.isDistinct() or N.isTemporary().
333  template <class OperandMapper>
334  void remapOperands(MDNode &N, OperandMapper mapOperand);
335 };
336 
337 } // end anonymous namespace
338 
339 Value *Mapper::mapValue(const Value *V) {
340  ValueToValueMapTy::iterator I = getVM().find(V);
341 
342  // If the value already exists in the map, use it.
343  if (I != getVM().end()) {
344  assert(I->second && "Unexpected null mapping");
345  return I->second;
346  }
347 
348  // If we have a materializer and it can materialize a value, use that.
349  if (auto *Materializer = getMaterializer()) {
350  if (Value *NewV = Materializer->materialize(const_cast<Value *>(V))) {
351  getVM()[V] = NewV;
352  return NewV;
353  }
354  }
355 
356  // Global values do not need to be seeded into the VM if they
357  // are using the identity mapping.
358  if (isa<GlobalValue>(V)) {
359  if (Flags & RF_NullMapMissingGlobalValues)
360  return nullptr;
361  return getVM()[V] = const_cast<Value *>(V);
362  }
363 
364  if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
365  // Inline asm may need *type* remapping.
366  FunctionType *NewTy = IA->getFunctionType();
367  if (TypeMapper) {
368  NewTy = cast<FunctionType>(TypeMapper->remapType(NewTy));
369 
370  if (NewTy != IA->getFunctionType())
371  V = InlineAsm::get(NewTy, IA->getAsmString(), IA->getConstraintString(),
372  IA->hasSideEffects(), IA->isAlignStack(),
373  IA->getDialect(), IA->canThrow());
374  }
375 
376  return getVM()[V] = const_cast<Value *>(V);
377  }
378 
379  if (const auto *MDV = dyn_cast<MetadataAsValue>(V)) {
380  const Metadata *MD = MDV->getMetadata();
381 
382  if (auto *LAM = dyn_cast<LocalAsMetadata>(MD)) {
383  // Look through to grab the local value.
384  if (Value *LV = mapValue(LAM->getValue())) {
385  if (V == LAM->getValue())
386  return const_cast<Value *>(V);
388  }
389 
390  // FIXME: always return nullptr once Verifier::verifyDominatesUse()
391  // ensures metadata operands only reference defined SSA values.
392  return (Flags & RF_IgnoreMissingLocals)
393  ? nullptr
395  MDTuple::get(V->getContext(), None));
396  }
397  if (auto *AL = dyn_cast<DIArgList>(MD)) {
399  for (auto *VAM : AL->getArgs()) {
400  // Map both Local and Constant VAMs here; they will both ultimately
401  // be mapped via mapValue. The exceptions are constants when we have no
402  // module level changes and locals when they have no existing mapped
403  // value and RF_IgnoreMissingLocals is set; these have identity
404  // mappings.
405  if ((Flags & RF_NoModuleLevelChanges) && isa<ConstantAsMetadata>(VAM)) {
406  MappedArgs.push_back(VAM);
407  } else if (Value *LV = mapValue(VAM->getValue())) {
408  MappedArgs.push_back(
409  LV == VAM->getValue() ? VAM : ValueAsMetadata::get(LV));
410  } else if ((Flags & RF_IgnoreMissingLocals) && isa<LocalAsMetadata>(VAM)) {
411  MappedArgs.push_back(VAM);
412  } else {
413  // If we cannot map the value, set the argument as undef.
414  MappedArgs.push_back(ValueAsMetadata::get(
415  UndefValue::get(VAM->getValue()->getType())));
416  }
417  }
418  return MetadataAsValue::get(V->getContext(),
419  DIArgList::get(V->getContext(), MappedArgs));
420  }
421 
422  // If this is a module-level metadata and we know that nothing at the module
423  // level is changing, then use an identity mapping.
424  if (Flags & RF_NoModuleLevelChanges)
425  return getVM()[V] = const_cast<Value *>(V);
426 
427  // Map the metadata and turn it into a value.
428  auto *MappedMD = mapMetadata(MD);
429  if (MD == MappedMD)
430  return getVM()[V] = const_cast<Value *>(V);
431  return getVM()[V] = MetadataAsValue::get(V->getContext(), MappedMD);
432  }
433 
434  // Okay, this either must be a constant (which may or may not be mappable) or
435  // is something that is not in the mapping table.
436  Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V));
437  if (!C)
438  return nullptr;
439 
440  if (BlockAddress *BA = dyn_cast<BlockAddress>(C))
441  return mapBlockAddress(*BA);
442 
443  if (const auto *E = dyn_cast<DSOLocalEquivalent>(C)) {
444  auto *Val = mapValue(E->getGlobalValue());
445  GlobalValue *GV = dyn_cast<GlobalValue>(Val);
446  if (GV)
447  return getVM()[E] = DSOLocalEquivalent::get(GV);
448 
449  auto *Func = cast<Function>(Val->stripPointerCastsAndAliases());
450  Type *NewTy = E->getType();
451  if (TypeMapper)
452  NewTy = TypeMapper->remapType(NewTy);
453  return getVM()[E] = llvm::ConstantExpr::getBitCast(
454  DSOLocalEquivalent::get(Func), NewTy);
455  }
456 
457  if (const auto *NC = dyn_cast<NoCFIValue>(C)) {
458  auto *Val = mapValue(NC->getGlobalValue());
459  GlobalValue *GV = cast<GlobalValue>(Val);
460  return getVM()[NC] = NoCFIValue::get(GV);
461  }
462 
463  auto mapValueOrNull = [this](Value *V) {
464  auto Mapped = mapValue(V);
465  assert((Mapped || (Flags & RF_NullMapMissingGlobalValues)) &&
466  "Unexpected null mapping for constant operand without "
467  "NullMapMissingGlobalValues flag");
468  return Mapped;
469  };
470 
471  // Otherwise, we have some other constant to remap. Start by checking to see
472  // if all operands have an identity remapping.
473  unsigned OpNo = 0, NumOperands = C->getNumOperands();
474  Value *Mapped = nullptr;
475  for (; OpNo != NumOperands; ++OpNo) {
476  Value *Op = C->getOperand(OpNo);
477  Mapped = mapValueOrNull(Op);
478  if (!Mapped)
479  return nullptr;
480  if (Mapped != Op)
481  break;
482  }
483 
484  // See if the type mapper wants to remap the type as well.
485  Type *NewTy = C->getType();
486  if (TypeMapper)
487  NewTy = TypeMapper->remapType(NewTy);
488 
489  // If the result type and all operands match up, then just insert an identity
490  // mapping.
491  if (OpNo == NumOperands && NewTy == C->getType())
492  return getVM()[V] = C;
493 
494  // Okay, we need to create a new constant. We've already processed some or
495  // all of the operands, set them all up now.
497  Ops.reserve(NumOperands);
498  for (unsigned j = 0; j != OpNo; ++j)
499  Ops.push_back(cast<Constant>(C->getOperand(j)));
500 
501  // If one of the operands mismatch, push it and the other mapped operands.
502  if (OpNo != NumOperands) {
503  Ops.push_back(cast<Constant>(Mapped));
504 
505  // Map the rest of the operands that aren't processed yet.
506  for (++OpNo; OpNo != NumOperands; ++OpNo) {
507  Mapped = mapValueOrNull(C->getOperand(OpNo));
508  if (!Mapped)
509  return nullptr;
510  Ops.push_back(cast<Constant>(Mapped));
511  }
512  }
513  Type *NewSrcTy = nullptr;
514  if (TypeMapper)
515  if (auto *GEPO = dyn_cast<GEPOperator>(C))
516  NewSrcTy = TypeMapper->remapType(GEPO->getSourceElementType());
517 
518  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
519  return getVM()[V] = CE->getWithOperands(Ops, NewTy, false, NewSrcTy);
520  if (isa<ConstantArray>(C))
521  return getVM()[V] = ConstantArray::get(cast<ArrayType>(NewTy), Ops);
522  if (isa<ConstantStruct>(C))
523  return getVM()[V] = ConstantStruct::get(cast<StructType>(NewTy), Ops);
524  if (isa<ConstantVector>(C))
525  return getVM()[V] = ConstantVector::get(Ops);
526  // If this is a no-operand constant, it must be because the type was remapped.
527  if (isa<UndefValue>(C))
528  return getVM()[V] = UndefValue::get(NewTy);
529  if (isa<ConstantAggregateZero>(C))
530  return getVM()[V] = ConstantAggregateZero::get(NewTy);
531  assert(isa<ConstantPointerNull>(C));
532  return getVM()[V] = ConstantPointerNull::get(cast<PointerType>(NewTy));
533 }
534 
535 Value *Mapper::mapBlockAddress(const BlockAddress &BA) {
536  Function *F = cast<Function>(mapValue(BA.getFunction()));
537 
538  // F may not have materialized its initializer. In that case, create a
539  // dummy basic block for now, and replace it once we've materialized all
540  // the initializers.
541  BasicBlock *BB;
542  if (F->empty()) {
543  DelayedBBs.push_back(DelayedBasicBlock(BA));
544  BB = DelayedBBs.back().TempBB.get();
545  } else {
546  BB = cast_or_null<BasicBlock>(mapValue(BA.getBasicBlock()));
547  }
548 
549  return getVM()[&BA] = BlockAddress::get(F, BB ? BB : BA.getBasicBlock());
550 }
551 
552 Metadata *Mapper::mapToMetadata(const Metadata *Key, Metadata *Val) {
553  getVM().MD()[Key].reset(Val);
554  return Val;
555 }
556 
557 Metadata *Mapper::mapToSelf(const Metadata *MD) {
558  return mapToMetadata(MD, const_cast<Metadata *>(MD));
559 }
560 
561 Optional<Metadata *> MDNodeMapper::tryToMapOperand(const Metadata *Op) {
562  if (!Op)
563  return nullptr;
564 
565  if (Optional<Metadata *> MappedOp = M.mapSimpleMetadata(Op)) {
566 #ifndef NDEBUG
567  if (auto *CMD = dyn_cast<ConstantAsMetadata>(Op))
568  assert((!*MappedOp || M.getVM().count(CMD->getValue()) ||
569  M.getVM().getMappedMD(Op)) &&
570  "Expected Value to be memoized");
571  else
572  assert((isa<MDString>(Op) || M.getVM().getMappedMD(Op)) &&
573  "Expected result to be memoized");
574 #endif
575  return *MappedOp;
576  }
577 
578  const MDNode &N = *cast<MDNode>(Op);
579  if (N.isDistinct())
580  return mapDistinctNode(N);
581  return None;
582 }
583 
584 MDNode *MDNodeMapper::mapDistinctNode(const MDNode &N) {
585  assert(N.isDistinct() && "Expected a distinct node");
586  assert(!M.getVM().getMappedMD(&N) && "Expected an unmapped node");
587  Metadata *NewM = nullptr;
588 
589  if (M.Flags & RF_ReuseAndMutateDistinctMDs) {
590  NewM = M.mapToSelf(&N);
591  } else {
592  NewM = MDNode::replaceWithDistinct(N.clone());
593  LLVM_DEBUG(dbgs() << "\nMap " << N << "\n"
594  << "To " << *NewM << "\n\n");
595  M.mapToMetadata(&N, NewM);
596  }
597  DistinctWorklist.push_back(cast<MDNode>(NewM));
598 
599  return DistinctWorklist.back();
600 }
601 
603  Value *MappedV) {
604  if (CMD.getValue() == MappedV)
605  return const_cast<ConstantAsMetadata *>(&CMD);
606  return MappedV ? ConstantAsMetadata::getConstant(MappedV) : nullptr;
607 }
608 
610  if (!Op)
611  return nullptr;
612 
613  if (Optional<Metadata *> MappedOp = M.getVM().getMappedMD(Op))
614  return *MappedOp;
615 
616  if (isa<MDString>(Op))
617  return const_cast<Metadata *>(Op);
618 
619  if (auto *CMD = dyn_cast<ConstantAsMetadata>(Op))
620  return wrapConstantAsMetadata(*CMD, M.getVM().lookup(CMD->getValue()));
621 
622  return None;
623 }
624 
625 Metadata &MDNodeMapper::UniquedGraph::getFwdReference(MDNode &Op) {
626  auto Where = Info.find(&Op);
627  assert(Where != Info.end() && "Expected a valid reference");
628 
629  auto &OpD = Where->second;
630  if (!OpD.HasChanged)
631  return Op;
632 
633  // Lazily construct a temporary node.
634  if (!OpD.Placeholder)
635  OpD.Placeholder = Op.clone();
636 
637  return *OpD.Placeholder;
638 }
639 
640 template <class OperandMapper>
641 void MDNodeMapper::remapOperands(MDNode &N, OperandMapper mapOperand) {
642  assert(!N.isUniqued() && "Expected distinct or temporary nodes");
643  for (unsigned I = 0, E = N.getNumOperands(); I != E; ++I) {
644  Metadata *Old = N.getOperand(I);
645  Metadata *New = mapOperand(Old);
646  if (Old != New)
647  LLVM_DEBUG(dbgs() << "Replacing Op " << Old << " with " << New << " in "
648  << N << "\n");
649 
650  if (Old != New)
651  N.replaceOperandWith(I, New);
652  }
653 }
654 
655 namespace {
656 
657 /// An entry in the worklist for the post-order traversal.
658 struct POTWorklistEntry {
659  MDNode *N; ///< Current node.
660  MDNode::op_iterator Op; ///< Current operand of \c N.
661 
662  /// Keep a flag of whether operands have changed in the worklist to avoid
663  /// hitting the map in \a UniquedGraph.
664  bool HasChanged = false;
665 
666  POTWorklistEntry(MDNode &N) : N(&N), Op(N.op_begin()) {}
667 };
668 
669 } // end anonymous namespace
670 
671 bool MDNodeMapper::createPOT(UniquedGraph &G, const MDNode &FirstN) {
672  assert(G.Info.empty() && "Expected a fresh traversal");
673  assert(FirstN.isUniqued() && "Expected uniqued node in POT");
674 
675  // Construct a post-order traversal of the uniqued subgraph under FirstN.
676  bool AnyChanges = false;
678  Worklist.push_back(POTWorklistEntry(const_cast<MDNode &>(FirstN)));
679  (void)G.Info[&FirstN];
680  while (!Worklist.empty()) {
681  // Start or continue the traversal through the this node's operands.
682  auto &WE = Worklist.back();
683  if (MDNode *N = visitOperands(G, WE.Op, WE.N->op_end(), WE.HasChanged)) {
684  // Push a new node to traverse first.
685  Worklist.push_back(POTWorklistEntry(*N));
686  continue;
687  }
688 
689  // Push the node onto the POT.
690  assert(WE.N->isUniqued() && "Expected only uniqued nodes");
691  assert(WE.Op == WE.N->op_end() && "Expected to visit all operands");
692  auto &D = G.Info[WE.N];
693  AnyChanges |= D.HasChanged = WE.HasChanged;
694  D.ID = G.POT.size();
695  G.POT.push_back(WE.N);
696 
697  // Pop the node off the worklist.
698  Worklist.pop_back();
699  }
700  return AnyChanges;
701 }
702 
703 MDNode *MDNodeMapper::visitOperands(UniquedGraph &G, MDNode::op_iterator &I,
704  MDNode::op_iterator E, bool &HasChanged) {
705  while (I != E) {
706  Metadata *Op = *I++; // Increment even on early return.
707  if (Optional<Metadata *> MappedOp = tryToMapOperand(Op)) {
708  // Check if the operand changes.
709  HasChanged |= Op != *MappedOp;
710  continue;
711  }
712 
713  // A uniqued metadata node.
714  MDNode &OpN = *cast<MDNode>(Op);
715  assert(OpN.isUniqued() &&
716  "Only uniqued operands cannot be mapped immediately");
717  if (G.Info.insert(std::make_pair(&OpN, Data())).second)
718  return &OpN; // This is a new one. Return it.
719  }
720  return nullptr;
721 }
722 
723 void MDNodeMapper::UniquedGraph::propagateChanges() {
724  bool AnyChanges;
725  do {
726  AnyChanges = false;
727  for (MDNode *N : POT) {
728  auto &D = Info[N];
729  if (D.HasChanged)
730  continue;
731 
732  if (llvm::none_of(N->operands(), [&](const Metadata *Op) {
733  auto Where = Info.find(Op);
734  return Where != Info.end() && Where->second.HasChanged;
735  }))
736  continue;
737 
738  AnyChanges = D.HasChanged = true;
739  }
740  } while (AnyChanges);
741 }
742 
743 void MDNodeMapper::mapNodesInPOT(UniquedGraph &G) {
744  // Construct uniqued nodes, building forward references as necessary.
745  SmallVector<MDNode *, 16> CyclicNodes;
746  for (auto *N : G.POT) {
747  auto &D = G.Info[N];
748  if (!D.HasChanged) {
749  // The node hasn't changed.
750  M.mapToSelf(N);
751  continue;
752  }
753 
754  // Remember whether this node had a placeholder.
755  bool HadPlaceholder(D.Placeholder);
756 
757  // Clone the uniqued node and remap the operands.
758  TempMDNode ClonedN = D.Placeholder ? std::move(D.Placeholder) : N->clone();
759  remapOperands(*ClonedN, [this, &D, &G](Metadata *Old) {
760  if (Optional<Metadata *> MappedOp = getMappedOp(Old))
761  return *MappedOp;
762  (void)D;
763  assert(G.Info[Old].ID > D.ID && "Expected a forward reference");
764  return &G.getFwdReference(*cast<MDNode>(Old));
765  });
766 
767  auto *NewN = MDNode::replaceWithUniqued(std::move(ClonedN));
768  if (N && NewN && N != NewN) {
769  LLVM_DEBUG(dbgs() << "\nMap " << *N << "\n"
770  << "To " << *NewN << "\n\n");
771  }
772 
773  M.mapToMetadata(N, NewN);
774 
775  // Nodes that were referenced out of order in the POT are involved in a
776  // uniquing cycle.
777  if (HadPlaceholder)
778  CyclicNodes.push_back(NewN);
779  }
780 
781  // Resolve cycles.
782  for (auto *N : CyclicNodes)
783  if (!N->isResolved())
784  N->resolveCycles();
785 }
786 
787 Metadata *MDNodeMapper::map(const MDNode &N) {
788  assert(DistinctWorklist.empty() && "MDNodeMapper::map is not recursive");
789  assert(!(M.Flags & RF_NoModuleLevelChanges) &&
790  "MDNodeMapper::map assumes module-level changes");
791 
792  // Require resolved nodes whenever metadata might be remapped.
793  assert(N.isResolved() && "Unexpected unresolved node");
794 
795  Metadata *MappedN =
796  N.isUniqued() ? mapTopLevelUniquedNode(N) : mapDistinctNode(N);
797  while (!DistinctWorklist.empty())
798  remapOperands(*DistinctWorklist.pop_back_val(), [this](Metadata *Old) {
799  if (Optional<Metadata *> MappedOp = tryToMapOperand(Old))
800  return *MappedOp;
801  return mapTopLevelUniquedNode(*cast<MDNode>(Old));
802  });
803  return MappedN;
804 }
805 
806 Metadata *MDNodeMapper::mapTopLevelUniquedNode(const MDNode &FirstN) {
807  assert(FirstN.isUniqued() && "Expected uniqued node");
808 
809  // Create a post-order traversal of uniqued nodes under FirstN.
810  UniquedGraph G;
811  if (!createPOT(G, FirstN)) {
812  // Return early if no nodes have changed.
813  for (const MDNode *N : G.POT)
814  M.mapToSelf(N);
815  return &const_cast<MDNode &>(FirstN);
816  }
817 
818  // Update graph with all nodes that have changed.
819  G.propagateChanges();
820 
821  // Map all the nodes in the graph.
822  mapNodesInPOT(G);
823 
824  // Return the original node, remapped.
825  return *getMappedOp(&FirstN);
826 }
827 
828 Optional<Metadata *> Mapper::mapSimpleMetadata(const Metadata *MD) {
829  // If the value already exists in the map, use it.
830  if (Optional<Metadata *> NewMD = getVM().getMappedMD(MD))
831  return *NewMD;
832 
833  if (isa<MDString>(MD))
834  return const_cast<Metadata *>(MD);
835 
836  // This is a module-level metadata. If nothing at the module level is
837  // changing, use an identity mapping.
838  if ((Flags & RF_NoModuleLevelChanges))
839  return const_cast<Metadata *>(MD);
840 
841  if (auto *CMD = dyn_cast<ConstantAsMetadata>(MD)) {
842  // Don't memoize ConstantAsMetadata. Instead of lasting until the
843  // LLVMContext is destroyed, they can be deleted when the GlobalValue they
844  // reference is destructed. These aren't super common, so the extra
845  // indirection isn't that expensive.
846  return wrapConstantAsMetadata(*CMD, mapValue(CMD->getValue()));
847  }
848 
849  assert(isa<MDNode>(MD) && "Expected a metadata node");
850 
851  return None;
852 }
853 
854 Metadata *Mapper::mapMetadata(const Metadata *MD) {
855  assert(MD && "Expected valid metadata");
856  assert(!isa<LocalAsMetadata>(MD) && "Unexpected local metadata");
857 
858  if (Optional<Metadata *> NewMD = mapSimpleMetadata(MD))
859  return *NewMD;
860 
861  return MDNodeMapper(*this).map(*cast<MDNode>(MD));
862 }
863 
864 void Mapper::flush() {
865  // Flush out the worklist of global values.
866  while (!Worklist.empty()) {
867  WorklistEntry E = Worklist.pop_back_val();
868  CurrentMCID = E.MCID;
869  switch (E.Kind) {
870  case WorklistEntry::MapGlobalInit:
871  E.Data.GVInit.GV->setInitializer(mapConstant(E.Data.GVInit.Init));
872  remapGlobalObjectMetadata(*E.Data.GVInit.GV);
873  break;
874  case WorklistEntry::MapAppendingVar: {
875  unsigned PrefixSize = AppendingInits.size() - E.AppendingGVNumNewMembers;
876  // mapAppendingVariable call can change AppendingInits if initalizer for
877  // the variable depends on another appending global, because of that inits
878  // need to be extracted and updated before the call.
880  drop_begin(AppendingInits, PrefixSize));
881  AppendingInits.resize(PrefixSize);
882  mapAppendingVariable(*E.Data.AppendingGV.GV,
883  E.Data.AppendingGV.InitPrefix,
884  E.AppendingGVIsOldCtorDtor, makeArrayRef(NewInits));
885  break;
886  }
887  case WorklistEntry::MapAliasOrIFunc: {
888  GlobalValue *GV = E.Data.AliasOrIFunc.GV;
889  Constant *Target = mapConstant(E.Data.AliasOrIFunc.Target);
890  if (auto *GA = dyn_cast<GlobalAlias>(GV))
891  GA->setAliasee(Target);
892  else if (auto *GI = dyn_cast<GlobalIFunc>(GV))
893  GI->setResolver(Target);
894  else
895  llvm_unreachable("Not alias or ifunc");
896  break;
897  }
899  remapFunction(*E.Data.RemapF);
900  break;
901  }
902  }
903  CurrentMCID = 0;
904 
905  // Finish logic for block addresses now that all global values have been
906  // handled.
907  while (!DelayedBBs.empty()) {
908  DelayedBasicBlock DBB = DelayedBBs.pop_back_val();
909  BasicBlock *BB = cast_or_null<BasicBlock>(mapValue(DBB.OldBB));
910  DBB.TempBB->replaceAllUsesWith(BB ? BB : DBB.OldBB);
911  }
912 }
913 
914 void Mapper::remapInstruction(Instruction *I) {
915  // Remap operands.
916  for (Use &Op : I->operands()) {
917  Value *V = mapValue(Op);
918  // If we aren't ignoring missing entries, assert that something happened.
919  if (V)
920  Op = V;
921  else
922  assert((Flags & RF_IgnoreMissingLocals) &&
923  "Referenced value not in value map!");
924  }
925 
926  // Remap phi nodes' incoming blocks.
927  if (PHINode *PN = dyn_cast<PHINode>(I)) {
928  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
929  Value *V = mapValue(PN->getIncomingBlock(i));
930  // If we aren't ignoring missing entries, assert that something happened.
931  if (V)
932  PN->setIncomingBlock(i, cast<BasicBlock>(V));
933  else
934  assert((Flags & RF_IgnoreMissingLocals) &&
935  "Referenced block not in value map!");
936  }
937  }
938 
939  // Remap attached metadata.
941  I->getAllMetadata(MDs);
942  for (const auto &MI : MDs) {
943  MDNode *Old = MI.second;
944  MDNode *New = cast_or_null<MDNode>(mapMetadata(Old));
945  if (New != Old)
946  I->setMetadata(MI.first, New);
947  }
948 
949  if (!TypeMapper)
950  return;
951 
952  // If the instruction's type is being remapped, do so now.
953  if (auto *CB = dyn_cast<CallBase>(I)) {
955  FunctionType *FTy = CB->getFunctionType();
956  Tys.reserve(FTy->getNumParams());
957  for (Type *Ty : FTy->params())
958  Tys.push_back(TypeMapper->remapType(Ty));
959  CB->mutateFunctionType(FunctionType::get(
960  TypeMapper->remapType(I->getType()), Tys, FTy->isVarArg()));
961 
962  LLVMContext &C = CB->getContext();
964  for (unsigned i = 0; i < Attrs.getNumAttrSets(); ++i) {
965  for (int AttrIdx = Attribute::FirstTypeAttr;
966  AttrIdx <= Attribute::LastTypeAttr; AttrIdx++) {
967  Attribute::AttrKind TypedAttr = (Attribute::AttrKind)AttrIdx;
968  if (Type *Ty =
969  Attrs.getAttributeAtIndex(i, TypedAttr).getValueAsType()) {
970  Attrs = Attrs.replaceAttributeTypeAtIndex(C, i, TypedAttr,
971  TypeMapper->remapType(Ty));
972  break;
973  }
974  }
975  }
976  CB->setAttributes(Attrs);
977  return;
978  }
979  if (auto *AI = dyn_cast<AllocaInst>(I))
980  AI->setAllocatedType(TypeMapper->remapType(AI->getAllocatedType()));
981  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
982  GEP->setSourceElementType(
983  TypeMapper->remapType(GEP->getSourceElementType()));
984  GEP->setResultElementType(
985  TypeMapper->remapType(GEP->getResultElementType()));
986  }
987  I->mutateType(TypeMapper->remapType(I->getType()));
988 }
989 
990 void Mapper::remapGlobalObjectMetadata(GlobalObject &GO) {
992  GO.getAllMetadata(MDs);
993  GO.clearMetadata();
994  for (const auto &I : MDs)
995  GO.addMetadata(I.first, *cast<MDNode>(mapMetadata(I.second)));
996 }
997 
998 void Mapper::remapFunction(Function &F) {
999  // Remap the operands.
1000  for (Use &Op : F.operands())
1001  if (Op)
1002  Op = mapValue(Op);
1003 
1004  // Remap the metadata attachments.
1005  remapGlobalObjectMetadata(F);
1006 
1007  // Remap the argument types.
1008  if (TypeMapper)
1009  for (Argument &A : F.args())
1010  A.mutateType(TypeMapper->remapType(A.getType()));
1011 
1012  // Remap the instructions.
1013  for (BasicBlock &BB : F)
1014  for (Instruction &I : BB)
1015  remapInstruction(&I);
1016 }
1017 
1018 void Mapper::mapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix,
1019  bool IsOldCtorDtor,
1020  ArrayRef<Constant *> NewMembers) {
1021  SmallVector<Constant *, 16> Elements;
1022  if (InitPrefix) {
1023  unsigned NumElements =
1024  cast<ArrayType>(InitPrefix->getType())->getNumElements();
1025  for (unsigned I = 0; I != NumElements; ++I)
1026  Elements.push_back(InitPrefix->getAggregateElement(I));
1027  }
1028 
1029  PointerType *VoidPtrTy;
1030  Type *EltTy;
1031  if (IsOldCtorDtor) {
1032  // FIXME: This upgrade is done during linking to support the C API. See
1033  // also IRLinker::linkAppendingVarProto() in IRMover.cpp.
1034  VoidPtrTy = Type::getInt8Ty(GV.getContext())->getPointerTo();
1035  auto &ST = *cast<StructType>(NewMembers.front()->getType());
1036  Type *Tys[3] = {ST.getElementType(0), ST.getElementType(1), VoidPtrTy};
1037  EltTy = StructType::get(GV.getContext(), Tys, false);
1038  }
1039 
1040  for (auto *V : NewMembers) {
1041  Constant *NewV;
1042  if (IsOldCtorDtor) {
1043  auto *S = cast<ConstantStruct>(V);
1044  auto *E1 = cast<Constant>(mapValue(S->getOperand(0)));
1045  auto *E2 = cast<Constant>(mapValue(S->getOperand(1)));
1046  Constant *Null = Constant::getNullValue(VoidPtrTy);
1047  NewV = ConstantStruct::get(cast<StructType>(EltTy), E1, E2, Null);
1048  } else {
1049  NewV = cast_or_null<Constant>(mapValue(V));
1050  }
1051  Elements.push_back(NewV);
1052  }
1053 
1054  GV.setInitializer(
1055  ConstantArray::get(cast<ArrayType>(GV.getValueType()), Elements));
1056 }
1057 
1058 void Mapper::scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init,
1059  unsigned MCID) {
1060  assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
1061  assert(MCID < MCs.size() && "Invalid mapping context");
1062 
1063  WorklistEntry WE;
1064  WE.Kind = WorklistEntry::MapGlobalInit;
1065  WE.MCID = MCID;
1066  WE.Data.GVInit.GV = &GV;
1067  WE.Data.GVInit.Init = &Init;
1068  Worklist.push_back(WE);
1069 }
1070 
1071 void Mapper::scheduleMapAppendingVariable(GlobalVariable &GV,
1072  Constant *InitPrefix,
1073  bool IsOldCtorDtor,
1074  ArrayRef<Constant *> NewMembers,
1075  unsigned MCID) {
1076  assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
1077  assert(MCID < MCs.size() && "Invalid mapping context");
1078 
1079  WorklistEntry WE;
1080  WE.Kind = WorklistEntry::MapAppendingVar;
1081  WE.MCID = MCID;
1082  WE.Data.AppendingGV.GV = &GV;
1083  WE.Data.AppendingGV.InitPrefix = InitPrefix;
1084  WE.AppendingGVIsOldCtorDtor = IsOldCtorDtor;
1085  WE.AppendingGVNumNewMembers = NewMembers.size();
1086  Worklist.push_back(WE);
1087  AppendingInits.append(NewMembers.begin(), NewMembers.end());
1088 }
1089 
1090 void Mapper::scheduleMapAliasOrIFunc(GlobalValue &GV, Constant &Target,
1091  unsigned MCID) {
1092  assert(AlreadyScheduled.insert(&GV).second && "Should not reschedule");
1093  assert((isa<GlobalAlias>(GV) || isa<GlobalIFunc>(GV)) &&
1094  "Should be alias or ifunc");
1095  assert(MCID < MCs.size() && "Invalid mapping context");
1096 
1097  WorklistEntry WE;
1098  WE.Kind = WorklistEntry::MapAliasOrIFunc;
1099  WE.MCID = MCID;
1100  WE.Data.AliasOrIFunc.GV = &GV;
1101  WE.Data.AliasOrIFunc.Target = &Target;
1102  Worklist.push_back(WE);
1103 }
1104 
1105 void Mapper::scheduleRemapFunction(Function &F, unsigned MCID) {
1106  assert(AlreadyScheduled.insert(&F).second && "Should not reschedule");
1107  assert(MCID < MCs.size() && "Invalid mapping context");
1108 
1109  WorklistEntry WE;
1110  WE.Kind = WorklistEntry::RemapFunction;
1111  WE.MCID = MCID;
1112  WE.Data.RemapF = &F;
1113  Worklist.push_back(WE);
1114 }
1115 
1116 void Mapper::addFlags(RemapFlags Flags) {
1117  assert(!hasWorkToDo() && "Expected to have flushed the worklist");
1118  this->Flags = this->Flags | Flags;
1119 }
1120 
1121 static Mapper *getAsMapper(void *pImpl) {
1122  return reinterpret_cast<Mapper *>(pImpl);
1123 }
1124 
1125 namespace {
1126 
1127 class FlushingMapper {
1128  Mapper &M;
1129 
1130 public:
1131  explicit FlushingMapper(void *pImpl) : M(*getAsMapper(pImpl)) {
1132  assert(!M.hasWorkToDo() && "Expected to be flushed");
1133  }
1134 
1135  ~FlushingMapper() { M.flush(); }
1136 
1137  Mapper *operator->() const { return &M; }
1138 };
1139 
1140 } // end anonymous namespace
1141 
1143  ValueMapTypeRemapper *TypeMapper,
1144  ValueMaterializer *Materializer)
1145  : pImpl(new Mapper(VM, Flags, TypeMapper, Materializer)) {}
1146 
1148 
1149 unsigned
1151  ValueMaterializer *Materializer) {
1152  return getAsMapper(pImpl)->registerAlternateMappingContext(VM, Materializer);
1153 }
1154 
1156  FlushingMapper(pImpl)->addFlags(Flags);
1157 }
1158 
1160  return FlushingMapper(pImpl)->mapValue(&V);
1161 }
1162 
1164  return cast_or_null<Constant>(mapValue(C));
1165 }
1166 
1168  return FlushingMapper(pImpl)->mapMetadata(&MD);
1169 }
1170 
1172  return cast_or_null<MDNode>(mapMetadata(N));
1173 }
1174 
1176  FlushingMapper(pImpl)->remapInstruction(&I);
1177 }
1178 
1180  FlushingMapper(pImpl)->remapFunction(F);
1181 }
1182 
1184  Constant &Init,
1185  unsigned MCID) {
1186  getAsMapper(pImpl)->scheduleMapGlobalInitializer(GV, Init, MCID);
1187 }
1188 
1190  Constant *InitPrefix,
1191  bool IsOldCtorDtor,
1192  ArrayRef<Constant *> NewMembers,
1193  unsigned MCID) {
1194  getAsMapper(pImpl)->scheduleMapAppendingVariable(
1195  GV, InitPrefix, IsOldCtorDtor, NewMembers, MCID);
1196 }
1197 
1199  unsigned MCID) {
1200  getAsMapper(pImpl)->scheduleMapAliasOrIFunc(GA, Aliasee, MCID);
1201 }
1202 
1204  unsigned MCID) {
1205  getAsMapper(pImpl)->scheduleMapAliasOrIFunc(GI, Resolver, MCID);
1206 }
1207 
1209  getAsMapper(pImpl)->scheduleRemapFunction(F, MCID);
1210 }
i
i
Definition: README.txt:29
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
Attrs
Function Attrs
Definition: README_ALTIVEC.txt:215
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
GlobalIFunc.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::ValueMapper::scheduleMapAppendingVariable
void scheduleMapAppendingVariable(GlobalVariable &GV, Constant *InitPrefix, bool IsOldCtorDtor, ArrayRef< Constant * > NewMembers, unsigned MappingContextID=0)
Definition: ValueMapper.cpp:1189
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:269
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1619
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:280
Optional.h
ValueMapper.h
llvm::StructType::get
static StructType * get(LLVMContext &Context, ArrayRef< Type * > Elements, bool isPacked=false)
This static method is the primary way to create a literal StructType.
Definition: Type.cpp:406
Metadata.h
DebugInfoMetadata.h
while
while(!ItemsToConvert.empty())
Definition: NVPTXLowerArgs.cpp:202
llvm::RF_NullMapMissingGlobalValues
@ RF_NullMapMissingGlobalValues
Any global values not in value map are mapped to null instead of mapping to self.
Definition: ValueMapper.h:99
llvm::Function
Definition: Function.h:60
llvm::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1347
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:140
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
InlineAsm.h
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::SmallDenseMap
Definition: DenseMap.h:882
llvm::ConstantExpr::getBitCast
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2258
llvm::FunctionType::get
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:361
llvm::BlockAddress::getBasicBlock
BasicBlock * getBasicBlock() const
Definition: Constants.h:877
llvm::GlobalAlias
Definition: GlobalAlias.h:28
llvm::ValueMapper::ValueMapper
ValueMapper(ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Definition: ValueMapper.cpp:1142
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::AttributeList
Definition: Attributes.h:408
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::ValueMapper::mapMDNode
MDNode * mapMDNode(const MDNode &N)
Definition: ValueMapper.cpp:1171
llvm::Optional
Definition: APInt.h:33
GlobalObject.h
Operator.h
llvm::ValueMapper::scheduleMapGlobalInitializer
void scheduleMapGlobalInitializer(GlobalVariable &GV, Constant &Init, unsigned MappingContextID=0)
Definition: ValueMapper.cpp:1183
llvm::ValueMapTypeRemapper
This is a class that can be implemented by clients to remap types when cloning constants and instruct...
Definition: ValueMapper.h:36
llvm::FunctionType::getNumParams
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
Definition: DerivedTypes.h:139
llvm::ValueAsMetadata::get
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:394
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:237
llvm::ValueMapper::mapMetadata
Metadata * mapMetadata(const Metadata &MD)
Definition: ValueMapper.cpp:1167
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::ValueMapper::registerAlternateMappingContext
unsigned registerAlternateMappingContext(ValueToValueMapTy &VM, ValueMaterializer *Materializer=nullptr)
Register an alternate mapping context.
Definition: ValueMapper.cpp:1150
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
new
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n y store obj * new
Definition: README.txt:125
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1289
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::FunctionType::isVarArg
bool isVarArg() const
Definition: DerivedTypes.h:123
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::ConstantAsMetadata::getValue
Constant * getValue() const
Definition: Metadata.h:428
wrapConstantAsMetadata
static ConstantAsMetadata * wrapConstantAsMetadata(const ConstantAsMetadata &CMD, Value *MappedV)
Definition: ValueMapper.cpp:602
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::Resolver
Interface for looking up the initializer for a variable name, used by Init::resolveReferences.
Definition: Record.h:2052
llvm::RF_ReuseAndMutateDistinctMDs
@ RF_ReuseAndMutateDistinctMDs
Instruct the remapper to reuse and mutate distinct metadata (remapping them in place) instead of clon...
Definition: ValueMapper.h:95
Instruction.h
llvm::ValueMapper::scheduleRemapFunction
void scheduleRemapFunction(Function &F, unsigned MappingContextID=0)
Definition: ValueMapper.cpp:1208
llvm::pdb::PDB_LocType::Null
@ Null
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:667
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::RemapFlags
RemapFlags
These are flags that the value mapping APIs allow.
Definition: ValueMapper.h:65
llvm::GlobalObject
Definition: GlobalObject.h:27
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
DenseSet.h
getMappedOp
static unsigned getMappedOp(unsigned PseudoOp)
Definition: ARCExpandPseudos.cpp:49
llvm::Instruction
Definition: Instruction.h:42
llvm::ValueMapper::~ValueMapper
~ValueMapper()
Definition: ValueMapper.cpp:1147
llvm::ValueMapper::mapValue
Value * mapValue(const Value &V)
Definition: ValueMapper.cpp:1159
llvm::GlobalObject::addMetadata
void addMetadata(unsigned KindID, MDNode &MD)
Add a metadata attachment.
Definition: Metadata.cpp:1300
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:619
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1769
llvm::FunctionType::params
ArrayRef< Type * > params() const
Definition: DerivedTypes.h:130
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::RF_NoModuleLevelChanges
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:71
llvm::None
const NoneType None
Definition: None.h:24
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::InlineAsm::get
static InlineAsm * get(FunctionType *Ty, StringRef AsmString, StringRef Constraints, bool hasSideEffects, bool isAlignStack=false, AsmDialect asmDialect=AD_ATT, bool canThrow=false)
InlineAsm::get - Return the specified uniqued inline asm string.
Definition: InlineAsm.cpp:41
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:314
getAsMapper
static Mapper * getAsMapper(void *pImpl)
Definition: ValueMapper.cpp:1121
llvm::InlineAsm
Definition: InlineAsm.h:31
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::ValueMapper::remapFunction
void remapFunction(Function &F)
Definition: ValueMapper.cpp:1179
BasicBlock.h
llvm::Function::getAttributeAtIndex
Attribute getAttributeAtIndex(unsigned i, Attribute::AttrKind Kind) const
gets the attribute from the list of attributes.
Definition: Function.cpp:642
llvm::GlobalValue
Definition: GlobalValue.h:44
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::ValueMapper::remapInstruction
void remapInstruction(Instruction &I)
Definition: ValueMapper.cpp:1175
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::RemapFunction
void RemapFunction(Function &F, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the operands, metadata, arguments, and instructions of a function.
Definition: ValueMapper.h:267
llvm::ConstantPointerNull::get
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1755
llvm::ValueMapTypeRemapper::remapType
virtual Type * remapType(Type *SrcTy)=0
The client should implement this method if they want to remap types while mapping values.
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::MDNode::replaceWithUniqued
static std::enable_if_t< std::is_base_of< MDNode, T >::value, T * > replaceWithUniqued(std::unique_ptr< T, TempMDNodeDeleter > N)
Replace a temporary node with a uniqued one.
Definition: Metadata.h:1080
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::Attribute::AttrKind
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:71
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MDTuple::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1256
llvm::WinEH::EncodingType::CE
@ CE
Windows NT (Windows on ARM)
llvm::MDNode
Metadata node.
Definition: Metadata.h:926
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:848
llvm::ValueMapper::addFlags
void addFlags(RemapFlags Flags)
Add to the current RemapFlags.
Definition: ValueMapper.cpp:1155
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
None.h
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Constant::getAggregateElement
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:410
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::MDNode::isUniqued
bool isUniqued() const
Definition: Metadata.h:1038
llvm::ms_demangle::IntrinsicFunctionKind::New
@ New
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
llvm::ValueMapper::mapConstant
Constant * mapConstant(const Constant &C)
Definition: ValueMapper.cpp:1163
llvm::ValueAsMetadata::getConstant
static ConstantAsMetadata * getConstant(Value *C)
Definition: Metadata.h:367
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1389
llvm::ifs::IFSSymbolType::Func
@ Func
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::ArrayRef::front
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:167
llvm::Init
Definition: Record.h:281
LAM
LoopAnalysisManager LAM
Definition: PassBuilderBindings.cpp:58
Argument.h
llvm::RF_IgnoreMissingLocals
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:89
llvm::NoCFIValue::get
static NoCFIValue * get(GlobalValue *GV)
Return a NoCFIValue for the specified function.
Definition: Constants.cpp:1938
llvm::ConstantAsMetadata
Definition: Metadata.h:413
j
return j(j<< 16)
llvm::BlockAddress::getFunction
Function * getFunction() const
Definition: Constants.h:876
Constant.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:971
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::ValueMapIterator
Definition: ValueMap.h:49
NC
#define NC
Definition: regutils.h:42
llvm::MetadataAsValue::get
static MetadataAsValue * get(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:102
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:338
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
GlobalVariable.h
Casting.h
llvm::Attribute::getValueAsType
Type * getValueAsType() const
Return the attribute's value as a Type.
Definition: Attributes.cpp:312
Function.h
llvm::Type::getPointerTo
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Definition: Type.cpp:774
llvm::ConstantArray::get
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1282
GlobalAlias.h
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
llvm::MDNode::replaceWithDistinct
static std::enable_if_t< std::is_base_of< MDNode, T >::value, T * > replaceWithDistinct(std::unique_ptr< T, TempMDNodeDeleter > N)
Replace a temporary node with a distinct one.
Definition: Metadata.h:1090
llvm::ValueMapper::scheduleMapGlobalIFunc
void scheduleMapGlobalIFunc(GlobalIFunc &GI, Constant &Resolver, unsigned MappingContextID=0)
Definition: ValueMapper.cpp:1203
Instructions.h
SmallVector.h
N
#define N
llvm::BlockAddress::get
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1807
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::PHINode
Definition: Instructions.h:2664
llvm::GlobalObject::getAllMetadata
void getAllMetadata(SmallVectorImpl< std::pair< unsigned, MDNode * >> &MDs) const
Appends all metadata attached to this value to MDs, sorting by KindID.
Definition: Metadata.cpp:1255
DerivedTypes.h
llvm::GlobalValue::getValueType
Type * getValueType() const
Definition: GlobalValue.h:272
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::ConstantAggregateZero::get
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1648
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
llvm::ValueMaterializer
This is a class that can be implemented by clients to materialize Values on demand.
Definition: ValueMapper.h:49
Value.h
llvm::GlobalIFunc
Definition: GlobalIFunc.h:34
llvm::Function::setAttributes
void setAttributes(AttributeList Attrs)
Set the attribute list for this Function.
Definition: Function.h:317
llvm::DSOLocalEquivalent::get
static DSOLocalEquivalent * get(GlobalValue *GV)
Return a DSOLocalEquivalent for the specified global value.
Definition: Constants.cpp:1880
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::MDOperand
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:773
llvm::GlobalVariable::setInitializer
void setInitializer(Constant *InitVal)
setInitializer - Sets the initializer for this global variable, removing any existing initializer if ...
Definition: Globals.cpp:432
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:103
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::GlobalObject::clearMetadata
void clearMetadata()
Erase all metadata attached to this Value.
Definition: Metadata.cpp:1323
llvm::ValueMapper::scheduleMapGlobalAlias
void scheduleMapGlobalAlias(GlobalAlias &GA, Constant &Aliasee, unsigned MappingContextID=0)
Definition: ValueMapper.cpp:1198