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