LLVM  16.0.0git
MemorySSA.h
Go to the documentation of this file.
1 //===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===//
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 /// \file
10 /// This file exposes an interface to building/using memory SSA to
11 /// walk memory instructions using a use/def graph.
12 ///
13 /// Memory SSA class builds an SSA form that links together memory access
14 /// instructions such as loads, stores, atomics, and calls. Additionally, it
15 /// does a trivial form of "heap versioning" Every time the memory state changes
16 /// in the program, we generate a new heap version. It generates
17 /// MemoryDef/Uses/Phis that are overlayed on top of the existing instructions.
18 ///
19 /// As a trivial example,
20 /// define i32 @main() #0 {
21 /// entry:
22 /// %call = call noalias i8* @_Znwm(i64 4) #2
23 /// %0 = bitcast i8* %call to i32*
24 /// %call1 = call noalias i8* @_Znwm(i64 4) #2
25 /// %1 = bitcast i8* %call1 to i32*
26 /// store i32 5, i32* %0, align 4
27 /// store i32 7, i32* %1, align 4
28 /// %2 = load i32* %0, align 4
29 /// %3 = load i32* %1, align 4
30 /// %add = add nsw i32 %2, %3
31 /// ret i32 %add
32 /// }
33 ///
34 /// Will become
35 /// define i32 @main() #0 {
36 /// entry:
37 /// ; 1 = MemoryDef(0)
38 /// %call = call noalias i8* @_Znwm(i64 4) #3
39 /// %2 = bitcast i8* %call to i32*
40 /// ; 2 = MemoryDef(1)
41 /// %call1 = call noalias i8* @_Znwm(i64 4) #3
42 /// %4 = bitcast i8* %call1 to i32*
43 /// ; 3 = MemoryDef(2)
44 /// store i32 5, i32* %2, align 4
45 /// ; 4 = MemoryDef(3)
46 /// store i32 7, i32* %4, align 4
47 /// ; MemoryUse(3)
48 /// %7 = load i32* %2, align 4
49 /// ; MemoryUse(4)
50 /// %8 = load i32* %4, align 4
51 /// %add = add nsw i32 %7, %8
52 /// ret i32 %add
53 /// }
54 ///
55 /// Given this form, all the stores that could ever effect the load at %8 can be
56 /// gotten by using the MemoryUse associated with it, and walking from use to
57 /// def until you hit the top of the function.
58 ///
59 /// Each def also has a list of users associated with it, so you can walk from
60 /// both def to users, and users to defs. Note that we disambiguate MemoryUses,
61 /// but not the RHS of MemoryDefs. You can see this above at %7, which would
62 /// otherwise be a MemoryUse(4). Being disambiguated means that for a given
63 /// store, all the MemoryUses on its use lists are may-aliases of that store
64 /// (but the MemoryDefs on its use list may not be).
65 ///
66 /// MemoryDefs are not disambiguated because it would require multiple reaching
67 /// definitions, which would require multiple phis, and multiple memoryaccesses
68 /// per instruction.
69 ///
70 /// In addition to the def/use graph described above, MemoryDefs also contain
71 /// an "optimized" definition use. The "optimized" use points to some def
72 /// reachable through the memory def chain. The optimized def *may* (but is
73 /// not required to) alias the original MemoryDef, but no def *closer* to the
74 /// source def may alias it. As the name implies, the purpose of the optimized
75 /// use is to allow caching of clobber searches for memory defs. The optimized
76 /// def may be nullptr, in which case clients must walk the defining access
77 /// chain.
78 ///
79 /// When iterating the uses of a MemoryDef, both defining uses and optimized
80 /// uses will be encountered. If only one type is needed, the client must
81 /// filter the use walk.
82 //
83 //===----------------------------------------------------------------------===//
84 
85 #ifndef LLVM_ANALYSIS_MEMORYSSA_H
86 #define LLVM_ANALYSIS_MEMORYSSA_H
87 
88 #include "llvm/ADT/DenseMap.h"
89 #include "llvm/ADT/SmallPtrSet.h"
90 #include "llvm/ADT/SmallVector.h"
91 #include "llvm/ADT/ilist_node.h"
96 #include "llvm/IR/DerivedUser.h"
97 #include "llvm/IR/Dominators.h"
98 #include "llvm/IR/Type.h"
99 #include "llvm/IR/User.h"
100 #include "llvm/Pass.h"
101 #include <algorithm>
102 #include <cassert>
103 #include <cstddef>
104 #include <iterator>
105 #include <memory>
106 #include <utility>
107 
108 namespace llvm {
109 
110 template <class GraphType> struct GraphTraits;
111 class BasicBlock;
112 class Function;
113 class Instruction;
114 class LLVMContext;
115 class MemoryAccess;
116 class MemorySSAWalker;
117 class Module;
118 class Use;
119 class Value;
120 class raw_ostream;
121 
122 namespace MSSAHelpers {
123 
124 struct AllAccessTag {};
125 struct DefsOnlyTag {};
126 
127 } // end namespace MSSAHelpers
128 
129 enum : unsigned {
130  // Used to signify what the default invalid ID is for MemoryAccess's
131  // getID()
133 };
134 
135 template <class T> class memoryaccess_def_iterator_base;
139 
140 // The base for all memory accesses. All memory accesses in a block are
141 // linked together using an intrusive list.
143  : public DerivedUser,
144  public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,
145  public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {
146 public:
147  using AllAccessType =
149  using DefsOnlyType =
151 
152  MemoryAccess(const MemoryAccess &) = delete;
153  MemoryAccess &operator=(const MemoryAccess &) = delete;
154 
155  void *operator new(size_t) = delete;
156 
157  // Methods for support type inquiry through isa, cast, and
158  // dyn_cast
159  static bool classof(const Value *V) {
160  unsigned ID = V->getValueID();
161  return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal;
162  }
163 
164  BasicBlock *getBlock() const { return Block; }
165 
166  void print(raw_ostream &OS) const;
167  void dump() const;
168 
169  /// The user iterators for a memory access
172 
173  /// This iterator walks over all of the defs in a given
174  /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For
175  /// MemoryUse/MemoryDef, this walks the defining access.
180 
181  /// Get the iterators for the all access list and the defs only list
182  /// We default to the all access list.
184  return this->AllAccessType::getIterator();
185  }
187  return this->AllAccessType::getIterator();
188  }
190  return this->AllAccessType::getReverseIterator();
191  }
193  return this->AllAccessType::getReverseIterator();
194  }
196  return this->DefsOnlyType::getIterator();
197  }
199  return this->DefsOnlyType::getIterator();
200  }
202  return this->DefsOnlyType::getReverseIterator();
203  }
205  return this->DefsOnlyType::getReverseIterator();
206  }
207 
208 protected:
209  friend class MemoryDef;
210  friend class MemoryPhi;
211  friend class MemorySSA;
212  friend class MemoryUse;
213  friend class MemoryUseOrDef;
214 
215  /// Used by MemorySSA to change the block of a MemoryAccess when it is
216  /// moved.
217  void setBlock(BasicBlock *BB) { Block = BB; }
218 
219  /// Used for debugging and tracking things about MemoryAccesses.
220  /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
221  inline unsigned getID() const;
222 
223  MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,
224  BasicBlock *BB, unsigned NumOperands)
225  : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue),
226  Block(BB) {}
227 
228  // Use deleteValue() to delete a generic MemoryAccess.
229  ~MemoryAccess() = default;
230 
231 private:
232  BasicBlock *Block;
233 };
234 
235 template <>
237  static void deleteNode(MemoryAccess *MA) { MA->deleteValue(); }
238 };
239 
241  MA.print(OS);
242  return OS;
243 }
244 
245 /// Class that has the common methods + fields of memory uses/defs. It's
246 /// a little awkward to have, but there are many cases where we want either a
247 /// use or def, and there are many cases where uses are needed (defs aren't
248 /// acceptable), and vice-versa.
249 ///
250 /// This class should never be instantiated directly; make a MemoryUse or
251 /// MemoryDef instead.
252 class MemoryUseOrDef : public MemoryAccess {
253 public:
254  void *operator new(size_t) = delete;
255 
257 
258  /// Get the instruction that this MemoryUse represents.
259  Instruction *getMemoryInst() const { return MemoryInstruction; }
260 
261  /// Get the access that produces the memory state used by this Use.
262  MemoryAccess *getDefiningAccess() const { return getOperand(0); }
263 
264  static bool classof(const Value *MA) {
265  return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal;
266  }
267 
268  /// Do we have an optimized use?
269  inline bool isOptimized() const;
270  /// Return the MemoryAccess associated with the optimized use, or nullptr.
271  inline MemoryAccess *getOptimized() const;
272  /// Sets the optimized use for a MemoryDef.
273  inline void setOptimized(MemoryAccess *);
274 
275  /// Reset the ID of what this MemoryUse was optimized to, causing it to
276  /// be rewalked by the walker if necessary.
277  /// This really should only be called by tests.
278  inline void resetOptimized();
279 
280 protected:
281  friend class MemorySSA;
282  friend class MemorySSAUpdater;
283 
284  MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
285  DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,
286  unsigned NumOperands)
287  : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands),
288  MemoryInstruction(MI) {
289  setDefiningAccess(DMA);
290  }
291 
292  // Use deleteValue() to delete a generic MemoryUseOrDef.
293  ~MemoryUseOrDef() = default;
294 
295  void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false) {
296  if (!Optimized) {
297  setOperand(0, DMA);
298  return;
299  }
300  setOptimized(DMA);
301  }
302 
303 private:
304  Instruction *MemoryInstruction;
305 };
306 
307 /// Represents read-only accesses to memory
308 ///
309 /// In particular, the set of Instructions that will be represented by
310 /// MemoryUse's is exactly the set of Instructions for which
311 /// AliasAnalysis::getModRefInfo returns "Ref".
312 class MemoryUse final : public MemoryUseOrDef {
313 public:
315 
317  : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB,
318  /*NumOperands=*/1) {}
319 
320  // allocate space for exactly one operand
321  void *operator new(size_t S) { return User::operator new(S, 1); }
322  void operator delete(void *Ptr) { User::operator delete(Ptr); }
323 
324  static bool classof(const Value *MA) {
325  return MA->getValueID() == MemoryUseVal;
326  }
327 
328  void print(raw_ostream &OS) const;
329 
331  OptimizedID = DMA->getID();
332  setOperand(0, DMA);
333  }
334 
335  /// Whether the MemoryUse is optimized. If ensureOptimizedUses() was called,
336  /// uses will usually be optimized, but this is not guaranteed (e.g. due to
337  /// invalidation and optimization limits.)
338  bool isOptimized() const {
339  return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
340  }
341 
343  return getDefiningAccess();
344  }
345 
346  void resetOptimized() {
347  OptimizedID = INVALID_MEMORYACCESS_ID;
348  }
349 
350 protected:
351  friend class MemorySSA;
352 
353 private:
354  static void deleteMe(DerivedUser *Self);
355 
356  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
357 };
358 
359 template <>
360 struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {};
362 
363 /// Represents a read-write access to memory, whether it is a must-alias,
364 /// or a may-alias.
365 ///
366 /// In particular, the set of Instructions that will be represented by
367 /// MemoryDef's is exactly the set of Instructions for which
368 /// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".
369 /// Note that, in order to provide def-def chains, all defs also have a use
370 /// associated with them. This use points to the nearest reaching
371 /// MemoryDef/MemoryPhi.
372 class MemoryDef final : public MemoryUseOrDef {
373 public:
374  friend class MemorySSA;
375 
377 
379  unsigned Ver)
380  : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB,
381  /*NumOperands=*/2),
382  ID(Ver) {}
383 
384  // allocate space for exactly two operands
385  void *operator new(size_t S) { return User::operator new(S, 2); }
386  void operator delete(void *Ptr) { User::operator delete(Ptr); }
387 
388  static bool classof(const Value *MA) {
389  return MA->getValueID() == MemoryDefVal;
390  }
391 
393  setOperand(1, MA);
394  OptimizedID = MA->getID();
395  }
396 
398  return cast_or_null<MemoryAccess>(getOperand(1));
399  }
400 
401  bool isOptimized() const {
402  return getOptimized() && OptimizedID == getOptimized()->getID();
403  }
404 
405  void resetOptimized() {
406  OptimizedID = INVALID_MEMORYACCESS_ID;
407  setOperand(1, nullptr);
408  }
409 
410  void print(raw_ostream &OS) const;
411 
412  unsigned getID() const { return ID; }
413 
414 private:
415  static void deleteMe(DerivedUser *Self);
416 
417  const unsigned ID;
418  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
419 };
420 
421 template <>
422 struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};
424 
425 template <>
427  static Use *op_begin(MemoryUseOrDef *MUD) {
428  if (auto *MU = dyn_cast<MemoryUse>(MUD))
430  return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
431  }
432 
433  static Use *op_end(MemoryUseOrDef *MUD) {
434  if (auto *MU = dyn_cast<MemoryUse>(MUD))
436  return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));
437  }
438 
439  static unsigned operands(const MemoryUseOrDef *MUD) {
440  if (const auto *MU = dyn_cast<MemoryUse>(MUD))
442  return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));
443  }
444 };
445 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)
446 
447 /// Represents phi nodes for memory accesses.
448 ///
449 /// These have the same semantic as regular phi nodes, with the exception that
450 /// only one phi will ever exist in a given basic block.
451 /// Guaranteeing one phi per block means guaranteeing there is only ever one
452 /// valid reaching MemoryDef/MemoryPHI along each path to the phi node.
453 /// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or
454 /// a MemoryPhi's operands.
455 /// That is, given
456 /// if (a) {
457 /// store %a
458 /// store %b
459 /// }
460 /// it *must* be transformed into
461 /// if (a) {
462 /// 1 = MemoryDef(liveOnEntry)
463 /// store %a
464 /// 2 = MemoryDef(1)
465 /// store %b
466 /// }
467 /// and *not*
468 /// if (a) {
469 /// 1 = MemoryDef(liveOnEntry)
470 /// store %a
471 /// 2 = MemoryDef(liveOnEntry)
472 /// store %b
473 /// }
474 /// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the
475 /// end of the branch, and if there are not two phi nodes, one will be
476 /// disconnected completely from the SSA graph below that point.
477 /// Because MemoryUse's do not generate new definitions, they do not have this
478 /// issue.
479 class MemoryPhi final : public MemoryAccess {
480  // allocate space for exactly zero operands
481  void *operator new(size_t S) { return User::operator new(S); }
482 
483 public:
484  void operator delete(void *Ptr) { User::operator delete(Ptr); }
485 
486  /// Provide fast operand accessors
488 
489  MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
490  : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),
491  ReservedSpace(NumPreds) {
492  allocHungoffUses(ReservedSpace);
493  }
494 
495  // Block iterator interface. This provides access to the list of incoming
496  // basic blocks, which parallels the list of incoming values.
499 
501  return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);
502  }
503 
505  return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);
506  }
507 
508  block_iterator block_end() { return block_begin() + getNumOperands(); }
509 
511  return block_begin() + getNumOperands();
512  }
513 
515  return make_range(block_begin(), block_end());
516  }
517 
519  return make_range(block_begin(), block_end());
520  }
521 
522  op_range incoming_values() { return operands(); }
523 
524  const_op_range incoming_values() const { return operands(); }
525 
526  /// Return the number of incoming edges
527  unsigned getNumIncomingValues() const { return getNumOperands(); }
528 
529  /// Return incoming value number x
530  MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
531  void setIncomingValue(unsigned I, MemoryAccess *V) {
532  assert(V && "PHI node got a null value!");
533  setOperand(I, V);
534  }
535 
536  static unsigned getOperandNumForIncomingValue(unsigned I) { return I; }
537  static unsigned getIncomingValueNumForOperand(unsigned I) { return I; }
538 
539  /// Return incoming basic block number @p i.
540  BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }
541 
542  /// Return incoming basic block corresponding
543  /// to an operand of the PHI.
544  BasicBlock *getIncomingBlock(const Use &U) const {
545  assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?");
546  return getIncomingBlock(unsigned(&U - op_begin()));
547  }
548 
549  /// Return incoming basic block corresponding
550  /// to value use iterator.
552  return getIncomingBlock(I.getUse());
553  }
554 
555  void setIncomingBlock(unsigned I, BasicBlock *BB) {
556  assert(BB && "PHI node got a null basic block!");
557  block_begin()[I] = BB;
558  }
559 
560  /// Add an incoming value to the end of the PHI list
562  if (getNumOperands() == ReservedSpace)
563  growOperands(); // Get more space!
564  // Initialize some new operands.
565  setNumHungOffUseOperands(getNumOperands() + 1);
566  setIncomingValue(getNumOperands() - 1, V);
567  setIncomingBlock(getNumOperands() - 1, BB);
568  }
569 
570  /// Return the first index of the specified basic
571  /// block in the value list for this PHI. Returns -1 if no instance.
572  int getBasicBlockIndex(const BasicBlock *BB) const {
573  for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
574  if (block_begin()[I] == BB)
575  return I;
576  return -1;
577  }
578 
580  int Idx = getBasicBlockIndex(BB);
581  assert(Idx >= 0 && "Invalid basic block argument!");
582  return getIncomingValue(Idx);
583  }
584 
585  // After deleting incoming position I, the order of incoming may be changed.
586  void unorderedDeleteIncoming(unsigned I) {
587  unsigned E = getNumOperands();
588  assert(I < E && "Cannot remove out of bounds Phi entry.");
589  // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
590  // itself should be deleted.
591  assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
592  "at least 2 values.");
593  setIncomingValue(I, getIncomingValue(E - 1));
594  setIncomingBlock(I, block_begin()[E - 1]);
595  setOperand(E - 1, nullptr);
596  block_begin()[E - 1] = nullptr;
597  setNumHungOffUseOperands(getNumOperands() - 1);
598  }
599 
600  // After deleting entries that satisfy Pred, remaining entries may have
601  // changed order.
602  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603  for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
604  if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605  unorderedDeleteIncoming(I);
606  E = getNumOperands();
607  --I;
608  }
609  assert(getNumOperands() >= 1 &&
610  "Cannot remove all incoming blocks in a MemoryPhi.");
611  }
612 
613  // After deleting incoming block BB, the incoming blocks order may be changed.
615  unorderedDeleteIncomingIf(
616  [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
617  }
618 
619  // After deleting incoming memory access MA, the incoming accesses order may
620  // be changed.
622  unorderedDeleteIncomingIf(
623  [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
624  }
625 
626  static bool classof(const Value *V) {
627  return V->getValueID() == MemoryPhiVal;
628  }
629 
630  void print(raw_ostream &OS) const;
631 
632  unsigned getID() const { return ID; }
633 
634 protected:
635  friend class MemorySSA;
636 
637  /// this is more complicated than the generic
638  /// User::allocHungoffUses, because we have to allocate Uses for the incoming
639  /// values and pointers to the incoming blocks, all in one allocation.
640  void allocHungoffUses(unsigned N) {
641  User::allocHungoffUses(N, /* IsPhi */ true);
642  }
643 
644 private:
645  // For debugging only
646  const unsigned ID;
647  unsigned ReservedSpace;
648 
649  /// This grows the operand list in response to a push_back style of
650  /// operation. This grows the number of ops by 1.5 times.
651  void growOperands() {
652  unsigned E = getNumOperands();
653  // 2 op PHI nodes are VERY common, so reserve at least enough for that.
654  ReservedSpace = std::max(E + E / 2, 2u);
655  growHungoffUses(ReservedSpace, /* IsPhi */ true);
656  }
657 
658  static void deleteMe(DerivedUser *Self);
659 };
660 
661 inline unsigned MemoryAccess::getID() const {
662  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
663  "only memory defs and phis have ids");
664  if (const auto *MD = dyn_cast<MemoryDef>(this))
665  return MD->getID();
666  return cast<MemoryPhi>(this)->getID();
667 }
668 
669 inline bool MemoryUseOrDef::isOptimized() const {
670  if (const auto *MD = dyn_cast<MemoryDef>(this))
671  return MD->isOptimized();
672  return cast<MemoryUse>(this)->isOptimized();
673 }
674 
676  if (const auto *MD = dyn_cast<MemoryDef>(this))
677  return MD->getOptimized();
678  return cast<MemoryUse>(this)->getOptimized();
679 }
680 
682  if (auto *MD = dyn_cast<MemoryDef>(this))
683  MD->setOptimized(MA);
684  else
685  cast<MemoryUse>(this)->setOptimized(MA);
686 }
687 
689  if (auto *MD = dyn_cast<MemoryDef>(this))
690  MD->resetOptimized();
691  else
692  cast<MemoryUse>(this)->resetOptimized();
693 }
694 
695 template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
697 
698 /// Encapsulates MemorySSA, including all data associated with memory
699 /// accesses.
700 class MemorySSA {
701 public:
703 
704  // MemorySSA must remain where it's constructed; Walkers it creates store
705  // pointers to it.
706  MemorySSA(MemorySSA &&) = delete;
707 
708  ~MemorySSA();
709 
710  MemorySSAWalker *getWalker();
711  MemorySSAWalker *getSkipSelfWalker();
712 
713  /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
714  /// access associated with it. If passed a basic block gets the memory phi
715  /// node that exists for that block, if there is one. Otherwise, this will get
716  /// a MemoryUseOrDef.
718  return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
719  }
720 
722  return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
723  }
724 
725  DominatorTree &getDomTree() const { return *DT; }
726 
727  void dump() const;
728  void print(raw_ostream &) const;
729 
730  /// Return true if \p MA represents the live on entry value
731  ///
732  /// Loads and stores from pointer arguments and other global values may be
733  /// defined by memory operations that do not occur in the current function, so
734  /// they may be live on entry to the function. MemorySSA represents such
735  /// memory state by the live on entry definition, which is guaranteed to occur
736  /// before any other memory access in the function.
737  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
738  return MA == LiveOnEntryDef.get();
739  }
740 
741  inline MemoryAccess *getLiveOnEntryDef() const {
742  return LiveOnEntryDef.get();
743  }
744 
745  // Sadly, iplists, by default, owns and deletes pointers added to the
746  // list. It's not currently possible to have two iplists for the same type,
747  // where one owns the pointers, and one does not. This is because the traits
748  // are per-type, not per-tag. If this ever changes, we should make the
749  // DefList an iplist.
751  using DefsList =
753 
754  /// Return the list of MemoryAccess's for a given basic block.
755  ///
756  /// This list is not modifiable by the user.
757  const AccessList *getBlockAccesses(const BasicBlock *BB) const {
758  return getWritableBlockAccesses(BB);
759  }
760 
761  /// Return the list of MemoryDef's and MemoryPhi's for a given basic
762  /// block.
763  ///
764  /// This list is not modifiable by the user.
765  const DefsList *getBlockDefs(const BasicBlock *BB) const {
766  return getWritableBlockDefs(BB);
767  }
768 
769  /// Given two memory accesses in the same basic block, determine
770  /// whether MemoryAccess \p A dominates MemoryAccess \p B.
771  bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
772 
773  /// Given two memory accesses in potentially different blocks,
774  /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.
775  bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;
776 
777  /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
778  /// dominates Use \p B.
779  bool dominates(const MemoryAccess *A, const Use &B) const;
780 
781  enum class VerificationLevel { Fast, Full };
782  /// Verify that MemorySSA is self consistent (IE definitions dominate
783  /// all uses, uses appear in the right places). This is used by unit tests.
784  void verifyMemorySSA(VerificationLevel = VerificationLevel::Fast) const;
785 
786  /// Used in various insertion functions to specify whether we are talking
787  /// about the beginning or end of a block.
788  enum InsertionPlace { Beginning, End, BeforeTerminator };
789 
790  /// By default, uses are *not* optimized during MemorySSA construction.
791  /// Calling this method will attempt to optimize all MemoryUses, if this has
792  /// not happened yet for this MemorySSA instance. This should be done if you
793  /// plan to query the clobbering access for most uses, or if you walk the
794  /// def-use chain of uses.
795  void ensureOptimizedUses();
796 
797 protected:
798  // Used by Memory SSA dumpers and wrapper pass
800  friend class MemorySSAUpdater;
801 
802  void verifyOrderingDominationAndDefUses(
804  void verifyDominationNumbers(const Function &F) const;
805  void verifyPrevDefInPhis(Function &F) const;
806 
807  // This is used by the use optimizer and updater.
809  auto It = PerBlockAccesses.find(BB);
810  return It == PerBlockAccesses.end() ? nullptr : It->second.get();
811  }
812 
813  // This is used by the use optimizer and updater.
815  auto It = PerBlockDefs.find(BB);
816  return It == PerBlockDefs.end() ? nullptr : It->second.get();
817  }
818 
819  // These is used by the updater to perform various internal MemorySSA
820  // machinsations. They do not always leave the IR in a correct state, and
821  // relies on the updater to fixup what it breaks, so it is not public.
822 
823  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
824  void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
825 
826  // Rename the dominator tree branch rooted at BB.
827  void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
829  renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
830  }
831 
832  void removeFromLookups(MemoryAccess *);
833  void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
834  void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
835  InsertionPlace);
836  void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
837  AccessList::iterator);
838  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
839  const MemoryUseOrDef *Template = nullptr,
840  bool CreationMustSucceed = true);
841 
842 private:
843  template <class AliasAnalysisType> class ClobberWalkerBase;
844  template <class AliasAnalysisType> class CachingWalker;
845  template <class AliasAnalysisType> class SkipSelfWalker;
846  class OptimizeUses;
847 
848  CachingWalker<AliasAnalysis> *getWalkerImpl();
849  void buildMemorySSA(BatchAAResults &BAA);
850 
851  void prepareForMoveTo(MemoryAccess *, BasicBlock *);
852  void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
853 
856 
857  void markUnreachableAsLiveOnEntry(BasicBlock *BB);
858  MemoryPhi *createMemoryPhi(BasicBlock *BB);
859  template <typename AliasAnalysisType>
860  MemoryUseOrDef *createNewAccess(Instruction *, AliasAnalysisType *,
861  const MemoryUseOrDef *Template = nullptr);
862  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
863  MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
864  void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
865  void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
867  bool SkipVisited = false, bool RenameAllUses = false);
868  AccessList *getOrCreateAccessList(const BasicBlock *);
869  DefsList *getOrCreateDefsList(const BasicBlock *);
870  void renumberBlock(const BasicBlock *) const;
871  AliasAnalysis *AA = nullptr;
872  DominatorTree *DT;
873  Function &F;
874 
875  // Memory SSA mappings
876  DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
877 
878  // These two mappings contain the main block to access/def mappings for
879  // MemorySSA. The list contained in PerBlockAccesses really owns all the
880  // MemoryAccesses.
881  // Both maps maintain the invariant that if a block is found in them, the
882  // corresponding list is not empty, and if a block is not found in them, the
883  // corresponding list is empty.
884  AccessMap PerBlockAccesses;
885  DefsMap PerBlockDefs;
886  std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef;
887 
888  // Domination mappings
889  // Note that the numbering is local to a block, even though the map is
890  // global.
891  mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
892  mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
893 
894  // Memory SSA building info
895  std::unique_ptr<ClobberWalkerBase<AliasAnalysis>> WalkerBase;
896  std::unique_ptr<CachingWalker<AliasAnalysis>> Walker;
897  std::unique_ptr<SkipSelfWalker<AliasAnalysis>> SkipWalker;
898  unsigned NextID = 0;
899  bool IsOptimized = false;
900 };
901 
902 /// Enables verification of MemorySSA.
903 ///
904 /// The checks which this flag enables is exensive and disabled by default
905 /// unless `EXPENSIVE_CHECKS` is defined. The flag `-verify-memoryssa` can be
906 /// used to selectively enable the verification without re-compilation.
907 extern bool VerifyMemorySSA;
908 
909 // Internal MemorySSA utils, for use by MemorySSA classes and walkers
911 protected:
912  friend class GVNHoist;
913  friend class MemorySSAWalker;
914 
915  // This function should not be used by new passes.
916  static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
917  AliasAnalysis &AA);
918 };
919 
920 // This pass does eager building and then printing of MemorySSA. It is used by
921 // the tests to be able to build, dump, and verify Memory SSA.
923 public:
925 
926  bool runOnFunction(Function &) override;
927  void getAnalysisUsage(AnalysisUsage &AU) const override;
928 
929  static char ID;
930 };
931 
932 /// An analysis that produces \c MemorySSA for a function.
933 ///
934 class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> {
936 
937  static AnalysisKey Key;
938 
939 public:
940  // Wrap MemorySSA result to ensure address stability of internal MemorySSA
941  // pointers after construction. Use a wrapper class instead of plain
942  // unique_ptr<MemorySSA> to avoid build breakage on MSVC.
943  struct Result {
944  Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
945 
946  MemorySSA &getMSSA() { return *MSSA.get(); }
947 
948  std::unique_ptr<MemorySSA> MSSA;
949 
950  bool invalidate(Function &F, const PreservedAnalyses &PA,
952  };
953 
955 };
956 
957 /// Printer pass for \c MemorySSA.
958 class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> {
959  raw_ostream &OS;
960 
961 public:
962  explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {}
963 
965 };
966 
967 /// Printer pass for \c MemorySSA via the walker.
969  : public PassInfoMixin<MemorySSAWalkerPrinterPass> {
970  raw_ostream &OS;
971 
972 public:
973  explicit MemorySSAWalkerPrinterPass(raw_ostream &OS) : OS(OS) {}
974 
976 };
977 
978 /// Verifier pass for \c MemorySSA.
979 struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
981 };
982 
983 /// Legacy analysis pass which computes \c MemorySSA.
985 public:
987 
988  static char ID;
989 
990  bool runOnFunction(Function &) override;
991  void releaseMemory() override;
992  MemorySSA &getMSSA() { return *MSSA; }
993  const MemorySSA &getMSSA() const { return *MSSA; }
994 
995  void getAnalysisUsage(AnalysisUsage &AU) const override;
996 
997  void verifyAnalysis() const override;
998  void print(raw_ostream &OS, const Module *M = nullptr) const override;
999 
1000 private:
1001  std::unique_ptr<MemorySSA> MSSA;
1002 };
1003 
1004 /// This is the generic walker interface for walkers of MemorySSA.
1005 /// Walkers are used to be able to further disambiguate the def-use chains
1006 /// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
1007 /// you.
1008 /// In particular, while the def-use chains provide basic information, and are
1009 /// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
1010 /// MemoryUse as AliasAnalysis considers it, a user mant want better or other
1011 /// information. In particular, they may want to use SCEV info to further
1012 /// disambiguate memory accesses, or they may want the nearest dominating
1013 /// may-aliasing MemoryDef for a call or a store. This API enables a
1014 /// standardized interface to getting and using that info.
1016 public:
1018  virtual ~MemorySSAWalker() = default;
1019 
1021 
1022  /// Given a memory Mod/Ref/ModRef'ing instruction, calling this
1023  /// will give you the nearest dominating MemoryAccess that Mod's the location
1024  /// the instruction accesses (by skipping any def which AA can prove does not
1025  /// alias the location(s) accessed by the instruction given).
1026  ///
1027  /// Note that this will return a single access, and it must dominate the
1028  /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
1029  /// this will return the MemoryPhi, not the operand. This means that
1030  /// given:
1031  /// if (a) {
1032  /// 1 = MemoryDef(liveOnEntry)
1033  /// store %a
1034  /// } else {
1035  /// 2 = MemoryDef(liveOnEntry)
1036  /// store %b
1037  /// }
1038  /// 3 = MemoryPhi(2, 1)
1039  /// MemoryUse(3)
1040  /// load %a
1041  ///
1042  /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
1043  /// in the if (a) branch.
1046  assert(MA && "Handed an instruction that MemorySSA doesn't recognize?");
1047  return getClobberingMemoryAccess(MA);
1048  }
1049 
1050  /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
1051  /// but takes a MemoryAccess instead of an Instruction.
1053 
1054  /// Given a potentially clobbering memory access and a new location,
1055  /// calling this will give you the nearest dominating clobbering MemoryAccess
1056  /// (by skipping non-aliasing def links).
1057  ///
1058  /// This version of the function is mainly used to disambiguate phi translated
1059  /// pointers, where the value of a pointer may have changed from the initial
1060  /// memory access. Note that this expects to be handed either a MemoryUse,
1061  /// or an already potentially clobbering access. Unlike the above API, if
1062  /// given a MemoryDef that clobbers the pointer as the starting access, it
1063  /// will return that MemoryDef, whereas the above would return the clobber
1064  /// starting from the use side of the memory def.
1066  const MemoryLocation &) = 0;
1067 
1068  /// Given a memory access, invalidate anything this walker knows about
1069  /// that access.
1070  /// This API is used by walkers that store information to perform basic cache
1071  /// invalidation. This will be called by MemorySSA at appropriate times for
1072  /// the walker it uses or returns.
1073  virtual void invalidateInfo(MemoryAccess *) {}
1074 
1075 protected:
1076  friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
1077  // constructor.
1079 };
1080 
1081 /// A MemorySSAWalker that does no alias queries, or anything else. It
1082 /// simply returns the links as they were constructed by the builder.
1084 public:
1085  // Keep the overrides below from hiding the Instruction overload of
1086  // getClobberingMemoryAccess.
1088 
1091  const MemoryLocation &) override;
1092 };
1093 
1094 using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
1095 using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
1096 
1097 /// Iterator base class used to implement const and non-const iterators
1098 /// over the defining accesses of a MemoryAccess.
1099 template <class T>
1101  : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
1102  std::forward_iterator_tag, T, ptrdiff_t, T *,
1103  T *> {
1104  using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base;
1105 
1106 public:
1107  memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
1108  memoryaccess_def_iterator_base() = default;
1109 
1110  bool operator==(const memoryaccess_def_iterator_base &Other) const {
1111  return Access == Other.Access && (!Access || ArgNo == Other.ArgNo);
1112  }
1113 
1114  // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
1115  // block from the operand in constant time (In a PHINode, the uselist has
1116  // both, so it's just subtraction). We provide it as part of the
1117  // iterator to avoid callers having to linear walk to get the block.
1118  // If the operation becomes constant time on MemoryPHI's, this bit of
1119  // abstraction breaking should be removed.
1121  MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
1122  assert(MP && "Tried to get phi arg block when not iterating over a PHI");
1123  return MP->getIncomingBlock(ArgNo);
1124  }
1125 
1127  assert(Access && "Tried to access past the end of our iterator");
1128  // Go to the first argument for phis, and the defining access for everything
1129  // else.
1130  if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
1131  return MP->getIncomingValue(ArgNo);
1132  return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1133  }
1134 
1135  using BaseT::operator++;
1137  assert(Access && "Hit end of iterator");
1138  if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
1139  if (++ArgNo >= MP->getNumIncomingValues()) {
1140  ArgNo = 0;
1141  Access = nullptr;
1142  }
1143  } else {
1144  Access = nullptr;
1145  }
1146  return *this;
1147  }
1148 
1149 private:
1150  T *Access = nullptr;
1151  unsigned ArgNo = 0;
1152 };
1153 
1155  return memoryaccess_def_iterator(this);
1156 }
1157 
1159  return const_memoryaccess_def_iterator(this);
1160 }
1161 
1163  return memoryaccess_def_iterator();
1164 }
1165 
1168 }
1169 
1170 /// GraphTraits for a MemoryAccess, which walks defs in the normal case,
1171 /// and uses in the inverse case.
1172 template <> struct GraphTraits<MemoryAccess *> {
1175 
1176  static NodeRef getEntryNode(NodeRef N) { return N; }
1177  static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); }
1178  static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
1179 };
1180 
1181 template <> struct GraphTraits<Inverse<MemoryAccess *>> {
1184 
1185  static NodeRef getEntryNode(NodeRef N) { return N; }
1186  static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
1187  static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
1188 };
1189 
1190 /// Provide an iterator that walks defs, giving both the memory access,
1191 /// and the current pointer location, updating the pointer location as it
1192 /// changes due to phi node translation.
1193 ///
1194 /// This iterator, while somewhat specialized, is what most clients actually
1195 /// want when walking upwards through MemorySSA def chains. It takes a pair of
1196 /// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
1197 /// memory location through phi nodes for the user.
1199  : public iterator_facade_base<upward_defs_iterator,
1200  std::forward_iterator_tag,
1201  const MemoryAccessPair> {
1202  using BaseT = upward_defs_iterator::iterator_facade_base;
1203 
1204 public:
1206  : DefIterator(Info.first), Location(Info.second),
1207  OriginalAccess(Info.first), DT(DT) {
1208  CurrentPair.first = nullptr;
1209 
1210  WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
1211  fillInCurrentPair();
1212  }
1213 
1214  upward_defs_iterator() { CurrentPair.first = nullptr; }
1215 
1216  bool operator==(const upward_defs_iterator &Other) const {
1217  return DefIterator == Other.DefIterator;
1218  }
1219 
1220  typename std::iterator_traits<BaseT>::reference operator*() const {
1221  assert(DefIterator != OriginalAccess->defs_end() &&
1222  "Tried to access past the end of our iterator");
1223  return CurrentPair;
1224  }
1225 
1226  using BaseT::operator++;
1228  assert(DefIterator != OriginalAccess->defs_end() &&
1229  "Tried to access past the end of the iterator");
1230  ++DefIterator;
1231  if (DefIterator != OriginalAccess->defs_end())
1232  fillInCurrentPair();
1233  return *this;
1234  }
1235 
1236  BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
1237 
1238 private:
1239  /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1240  /// loop. In particular, this guarantees that it only references a single
1241  /// MemoryLocation during execution of the containing function.
1242  bool IsGuaranteedLoopInvariant(const Value *Ptr) const;
1243 
1244  void fillInCurrentPair() {
1245  CurrentPair.first = *DefIterator;
1246  CurrentPair.second = Location;
1247  if (WalkingPhi && Location.Ptr) {
1248  PHITransAddr Translator(
1249  const_cast<Value *>(Location.Ptr),
1250  OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
1251 
1252  if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
1253  DefIterator.getPhiArgBlock(), DT, true))
1254  if (Translator.getAddr() != CurrentPair.second.Ptr)
1255  CurrentPair.second =
1256  CurrentPair.second.getWithNewPtr(Translator.getAddr());
1257 
1258  // Mark size as unknown, if the location is not guaranteed to be
1259  // loop-invariant for any possible loop in the function. Setting the size
1260  // to unknown guarantees that any memory accesses that access locations
1261  // after the pointer are considered as clobbers, which is important to
1262  // catch loop carried dependences.
1263  if (!IsGuaranteedLoopInvariant(CurrentPair.second.Ptr))
1264  CurrentPair.second = CurrentPair.second.getWithNewSize(
1266  }
1267  }
1268 
1269  MemoryAccessPair CurrentPair;
1270  memoryaccess_def_iterator DefIterator;
1271  MemoryLocation Location;
1272  MemoryAccess *OriginalAccess = nullptr;
1273  DominatorTree *DT = nullptr;
1274  bool WalkingPhi = false;
1275 };
1276 
1277 inline upward_defs_iterator
1279  return upward_defs_iterator(Pair, &DT);
1280 }
1281 
1283 
1284 inline iterator_range<upward_defs_iterator>
1286  return make_range(upward_defs_begin(Pair, DT), upward_defs_end());
1287 }
1288 
1289 /// Walks the defining accesses of MemoryDefs. Stops after we hit something that
1290 /// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when
1291 /// comparing against a null def_chain_iterator, this will compare equal only
1292 /// after walking said Phi/liveOnEntry.
1293 ///
1294 /// The UseOptimizedChain flag specifies whether to walk the clobbering
1295 /// access chain, or all the accesses.
1296 ///
1297 /// Normally, MemoryDef are all just def/use linked together, so a def_chain on
1298 /// a MemoryDef will walk all MemoryDefs above it in the program until it hits
1299 /// a phi node. The optimized chain walks the clobbering access of a store.
1300 /// So if you are just trying to find, given a store, what the next
1301 /// thing that would clobber the same memory is, you want the optimized chain.
1302 template <class T, bool UseOptimizedChain = false>
1304  : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>,
1305  std::forward_iterator_tag, MemoryAccess *> {
1306  def_chain_iterator() : MA(nullptr) {}
1307  def_chain_iterator(T MA) : MA(MA) {}
1308 
1309  T operator*() const { return MA; }
1310 
1312  // N.B. liveOnEntry has a null defining access.
1313  if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1314  if (UseOptimizedChain && MUD->isOptimized())
1315  MA = MUD->getOptimized();
1316  else
1317  MA = MUD->getDefiningAccess();
1318  } else {
1319  MA = nullptr;
1320  }
1321 
1322  return *this;
1323  }
1324 
1325  bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
1326 
1327 private:
1328  T MA;
1329 };
1330 
1331 template <class T>
1332 inline iterator_range<def_chain_iterator<T>>
1333 def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1334 #ifdef EXPENSIVE_CHECKS
1335  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
1336  "UpTo isn't in the def chain!");
1337 #endif
1339 }
1340 
1341 template <class T>
1344  def_chain_iterator<T, true>(nullptr));
1345 }
1346 
1347 } // end namespace llvm
1348 
1349 #endif // LLVM_ANALYSIS_MEMORYSSA_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::BatchAAResults
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
Definition: AliasAnalysis.h:609
llvm::MemoryPhi::classof
static bool classof(const Value *V)
Definition: MemorySSA.h:626
llvm::MemoryAccess::getReverseDefsIterator
DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const
Definition: MemorySSA.h:204
llvm::DoNothingMemorySSAWalker
A MemorySSAWalker that does no alias queries, or anything else.
Definition: MemorySSA.h:1083
llvm::Value::const_user_iterator
user_iterator_impl< const User > const_user_iterator
Definition: Value.h:391
llvm::MemoryPhi::unorderedDeleteIncomingIf
void unorderedDeleteIncomingIf(Fn &&Pred)
Definition: MemorySSA.h:602
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::ilist_alloc_traits< MemoryAccess >::deleteNode
static void deleteNode(MemoryAccess *MA)
Definition: MemorySSA.h:237
llvm::MemoryUseOrDef::getOptimized
MemoryAccess * getOptimized() const
Return the MemoryAccess associated with the optimized use, or nullptr.
Definition: MemorySSA.h:675
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::MemorySSA::getWritableBlockDefs
DefsList * getWritableBlockDefs(const BasicBlock *BB) const
Definition: MemorySSA.h:814
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::MemoryAccess::MemoryAccess
MemoryAccess(const MemoryAccess &)=delete
llvm::MemoryPhi::getIncomingBlock
BasicBlock * getIncomingBlock(MemoryAccess::const_user_iterator I) const
Return incoming basic block corresponding to value use iterator.
Definition: MemorySSA.h:551
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::PHITransAddr
PHITransAddr - An address value which tracks and handles phi translation.
Definition: PHITransAddr.h:35
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:218
llvm::MemoryPhi::const_block_iterator
BasicBlock *const * const_block_iterator
Definition: MemorySSA.h:498
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::memoryaccess_def_iterator_base
Iterator base class used to implement const and non-const iterators over the defining accesses of a M...
Definition: MemorySSA.h:135
llvm::Function
Definition: Function.h:60
llvm::optimized_def_chain
iterator_range< def_chain_iterator< T, true > > optimized_def_chain(T MA)
Definition: MemorySSA.h:1342
llvm::upward_defs_begin
upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT)
Definition: MemorySSA.h:1278
pointer
Replace within non kernel function use of LDS with pointer
Definition: AMDGPUReplaceLDSUseWithPointer.cpp:631
llvm::upward_defs_iterator
Provide an iterator that walks defs, giving both the memory access, and the current pointer location,...
Definition: MemorySSA.h:1198
Pass.h
llvm::MemoryDef::resetOptimized
void resetOptimized()
Definition: MemorySSA.h:405
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
TemplateParamKind::Template
@ Template
llvm::def_chain_iterator::def_chain_iterator
def_chain_iterator()
Definition: MemorySSA.h:1306
llvm::INVALID_MEMORYACCESS_ID
@ INVALID_MEMORYACCESS_ID
Definition: MemorySSA.h:132
llvm::MemoryAccess::defs_begin
memoryaccess_def_iterator defs_begin()
This iterator walks over all of the defs in a given MemoryAccess.
Definition: MemorySSA.h:1154
llvm::MemorySSAPrinterPass
Printer pass for MemorySSA.
Definition: MemorySSA.h:958
llvm::MemoryAccess::getID
unsigned getID() const
Used for debugging and tracking things about MemoryAccesses.
Definition: MemorySSA.h:661
llvm::MemoryAccess::~MemoryAccess
~MemoryAccess()=default
llvm::MemorySSA::renamePass
void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, SmallPtrSetImpl< BasicBlock * > &Visited)
Definition: MemorySSA.h:827
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::def_chain_iterator::operator++
def_chain_iterator & operator++()
Definition: MemorySSA.h:1311
llvm::MemorySSAWalker::MemorySSAWalker
MemorySSAWalker(MemorySSA *)
Definition: MemorySSA.cpp:2414
llvm::MemoryPhi::unorderedDeleteIncomingValue
void unorderedDeleteIncomingValue(const MemoryAccess *MA)
Definition: MemorySSA.h:621
llvm::MemoryAccess::getReverseIterator
AllAccessType::reverse_self_iterator getReverseIterator()
Definition: MemorySSA.h:189
llvm::MemorySSAWrapperPass::ID
static char ID
Definition: MemorySSA.h:988
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::ilist_node_impl< ilist_detail::compute_node_options< MemoryAccess, Options... >::type >::getReverseIterator
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:85
DEFINE_TRANSPARENT_OPERAND_ACCESSORS
#define DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CLASS, VALUECLASS)
Macro for generating out-of-class operand accessor definitions.
Definition: OperandTraits.h:125
llvm::MemorySSA::getLiveOnEntryDef
MemoryAccess * getLiveOnEntryDef() const
Definition: MemorySSA.h:741
llvm::MemorySSAAnalysis::Result::getMSSA
MemorySSA & getMSSA()
Definition: MemorySSA.h:946
llvm::MemorySSA::VerificationLevel
VerificationLevel
Definition: MemorySSA.h:781
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::MemoryPhi
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:479
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::MemoryUse::print
void print(raw_ostream &OS) const
Definition: MemorySSA.cpp:2207
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::MemorySSAAnalysis::Result::Result
Result(std::unique_ptr< MemorySSA > &&MSSA)
Definition: MemorySSA.h:944
llvm::MemoryDef::getID
unsigned getID() const
Definition: MemorySSA.h:412
llvm::MemoryUse
Represents read-only accesses to memory.
Definition: MemorySSA.h:312
DerivedUser.h
llvm::MemoryPhi::getOperandNumForIncomingValue
static unsigned getOperandNumForIncomingValue(unsigned I)
Definition: MemorySSA.h:536
llvm::DoNothingMemorySSAWalker::getClobberingMemoryAccess
MemoryAccess * getClobberingMemoryAccess(MemoryAccess *) override
Does the same thing as getClobberingMemoryAccess(const Instruction *I), but takes a MemoryAccess inst...
Definition: MemorySSA.cpp:2606
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:104
llvm::upward_defs_iterator::upward_defs_iterator
upward_defs_iterator()
Definition: MemorySSA.h:1214
llvm::upward_defs
iterator_range< upward_defs_iterator > upward_defs(const MemoryAccessPair &Pair, DominatorTree &DT)
Definition: MemorySSA.h:1285
llvm::MemoryUse::classof
static bool classof(const Value *MA)
Definition: MemorySSA.h:324
llvm::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:391
llvm::DerivedUser::DeleteValueTy
void(*)(DerivedUser *) DeleteValueTy
Definition: DerivedUser.h:29
llvm::MemoryPhi::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
Definition: MemorySSA.h:540
size_t
llvm::MemoryUseOrDef::classof
static bool classof(const Value *MA)
Definition: MemorySSA.h:264
llvm::MemorySSAPrinterLegacyPass::ID
static char ID
Definition: MemorySSA.h:929
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::MemoryPhi::getBasicBlockIndex
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: MemorySSA.h:572
AliasAnalysis.h
llvm::MemoryPhi::block_end
const_block_iterator block_end() const
Definition: MemorySSA.h:510
llvm::upward_defs_iterator::upward_defs_iterator
upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT)
Definition: MemorySSA.h:1205
llvm::MemoryAccess::getDefsIterator
DefsOnlyType::const_self_iterator getDefsIterator() const
Definition: MemorySSA.h:198
llvm::MemoryUseOrDef::MemoryUseOrDef
MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty, DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB, unsigned NumOperands)
Definition: MemorySSA.h:284
PHITransAddr.h
llvm::OperandTraits< MemoryUseOrDef >::operands
static unsigned operands(const MemoryUseOrDef *MUD)
Definition: MemorySSA.h:439
llvm::MemoryAccess::iterator
user_iterator iterator
The user iterators for a memory access.
Definition: MemorySSA.h:170
llvm::MemorySSAWrapperPass::MemorySSAWrapperPass
MemorySSAWrapperPass()
Definition: MemorySSA.cpp:2386
llvm::MemorySSA::getMemoryAccess
MemoryPhi * getMemoryAccess(const BasicBlock *BB) const
Definition: MemorySSA.h:721
llvm::GraphTraits< Inverse< MemoryAccess * > >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MemorySSA.h:1187
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:984
llvm::MemorySSAPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2352
llvm::OperandTraits
Compile-time customization of User operands.
Definition: User.h:42
llvm::MemoryAccess::getIterator
AllAccessType::self_iterator getIterator()
Get the iterators for the all access list and the defs only list We default to the all access list.
Definition: MemorySSA.h:183
llvm::def_chain_iterator::operator*
T operator*() const
Definition: MemorySSA.h:1309
llvm::MemorySSAWalker::MSSA
MemorySSA * MSSA
Definition: MemorySSA.h:1078
llvm::MemoryPhi::block_begin
const_block_iterator block_begin() const
Definition: MemorySSA.h:504
llvm::MemoryAccess::defs_end
memoryaccess_def_iterator defs_end()
Definition: MemorySSA.h:1162
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::MemorySSA::isLiveOnEntryDef
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:737
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MemorySSAWrapperPass::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: MemorySSA.cpp:2390
llvm::MemorySSAAnalysis::Result
Definition: MemorySSA.h:943
llvm::GVNHoist
Definition: GVNHoist.cpp:259
llvm::MemoryUseOrDef::~MemoryUseOrDef
~MemoryUseOrDef()=default
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MemoryDef::classof
static bool classof(const Value *MA)
Definition: MemorySSA.h:388
llvm::MemorySSAPrinterLegacyPass::runOnFunction
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: MemorySSA.cpp:2320
llvm::MemorySSAWrapperPass::print
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: MemorySSA.cpp:2410
llvm::memoryaccess_def_iterator
memoryaccess_def_iterator_base< MemoryAccess > memoryaccess_def_iterator
Definition: MemorySSA.h:136
llvm::MemoryAccess::classof
static bool classof(const Value *V)
Definition: MemorySSA.h:159
llvm::MemorySSAWalker::~MemorySSAWalker
virtual ~MemorySSAWalker()=default
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MemoryDef::isOptimized
bool isOptimized() const
Definition: MemorySSA.h:401
llvm::MemorySSAWalker::invalidateInfo
virtual void invalidateInfo(MemoryAccess *)
Given a memory access, invalidate anything this walker knows about that access.
Definition: MemorySSA.h:1073
llvm::MemorySSAPrinterLegacyPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: MemorySSA.cpp:2231
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MemoryAccess::getReverseDefsIterator
DefsOnlyType::reverse_self_iterator getReverseDefsIterator()
Definition: MemorySSA.h:201
llvm::Value::getValueID
unsigned getValueID() const
Return an ID for the concrete type of this object.
Definition: Value.h:532
llvm::GraphTraits< Inverse< MemoryAccess * > >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: MemorySSA.h:1185
llvm::Instruction
Definition: Instruction.h:42
llvm::MemorySSAAnalysis::run
Result run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2336
llvm::MemoryPhi::addIncoming
void addIncoming(MemoryAccess *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: MemorySSA.h:561
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
dominates
static bool dominates(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator B)
Definition: RegAllocFast.cpp:343
llvm::MemorySSA::getBlockAccesses
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
Definition: MemorySSA.h:757
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:291
llvm::MSSAHelpers::AllAccessTag
Definition: MemorySSA.h:124
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
SmallPtrSet.h
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::MemoryUseOrDef::DECLARE_TRANSPARENT_OPERAND_ACCESSORS
DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:147
llvm::MemorySSAPrinterPass::MemorySSAPrinterPass
MemorySSAPrinterPass(raw_ostream &OS)
Definition: MemorySSA.h:962
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
llvm::MemoryPhi::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: MemorySSA.h:527
llvm::MemoryUseOrDef::getMemoryInst
Instruction * getMemoryInst() const
Get the instruction that this MemoryUse represents.
Definition: MemorySSA.h:259
llvm::MemoryPhi::getIncomingValueNumForOperand
static unsigned getIncomingValueNumForOperand(unsigned I)
Definition: MemorySSA.h:537
llvm::MemoryPhi::unorderedDeleteIncoming
void unorderedDeleteIncoming(unsigned I)
Definition: MemorySSA.h:586
llvm::upward_defs_iterator::operator*
std::iterator_traits< BaseT >::reference operator*() const
Definition: MemorySSA.h:1220
llvm::MemoryAccess::getBlock
BasicBlock * getBlock() const
Definition: MemorySSA.h:164
llvm::MemorySSAPrinterLegacyPass
Definition: MemorySSA.h:922
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
llvm::MemoryAccess::getReverseIterator
AllAccessType::const_reverse_self_iterator getReverseIterator() const
Definition: MemorySSA.h:192
llvm::memoryaccess_def_iterator_base::getPhiArgBlock
BasicBlock * getPhiArgBlock() const
Definition: MemorySSA.h:1120
llvm::MemorySSAVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2377
llvm::MemoryPhi::block_begin
block_iterator block_begin()
Definition: MemorySSA.h:500
llvm::MemoryUseOrDef::setDefiningAccess
void setDefiningAccess(MemoryAccess *DMA, bool Optimized=false)
Definition: MemorySSA.h:295
llvm::upward_defs_iterator::operator++
upward_defs_iterator & operator++()
Definition: MemorySSA.h:1227
llvm::MemorySSAWalker::getClobberingMemoryAccess
MemoryAccess * getClobberingMemoryAccess(const Instruction *I)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition: MemorySSA.h:1044
llvm::MemoryAccess::MemoryAccess
MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue, BasicBlock *BB, unsigned NumOperands)
Definition: MemorySSA.h:223
llvm::MemorySSAWrapperPass::runOnFunction
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: MemorySSA.cpp:2398
llvm::def_chain_iterator::def_chain_iterator
def_chain_iterator(T MA)
Definition: MemorySSA.h:1307
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
llvm::MemorySSAUtil
Definition: MemorySSA.h:910
llvm::User::allocHungoffUses
void allocHungoffUses(unsigned N, bool IsPhi=false)
Allocate the array of Uses, followed by a pointer (with bottom bit set) to the User.
Definition: User.cpp:50
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::MemoryAccess::print
void print(raw_ostream &OS) const
Definition: MemorySSA.cpp:2156
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1754
llvm::MemorySSAWrapperPass::getMSSA
const MemorySSA & getMSSA() const
Definition: MemorySSA.h:993
llvm::MemoryPhi::blocks
iterator_range< const_block_iterator > blocks() const
Definition: MemorySSA.h:518
llvm::MemoryAccess::operator=
MemoryAccess & operator=(const MemoryAccess &)=delete
llvm::MemorySSAVerifierPass
Verifier pass for MemorySSA.
Definition: MemorySSA.h:979
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::upward_defs_iterator::operator==
bool operator==(const upward_defs_iterator &Other) const
Definition: MemorySSA.h:1216
llvm::def_chain
iterator_range< def_chain_iterator< T > > def_chain(T MA, MemoryAccess *UpTo=nullptr)
Definition: MemorySSA.h:1333
llvm::memoryaccess_def_iterator_base::operator==
bool operator==(const memoryaccess_def_iterator_base &Other) const
Definition: MemorySSA.h:1110
MemoryLocation.h
llvm::DenseMap
Definition: DenseMap.h:714
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::MemoryPhi::incoming_values
const_op_range incoming_values() const
Definition: MemorySSA.h:524
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
llvm::MemoryPhi::getIncomingBlock
BasicBlock * getIncomingBlock(const Use &U) const
Return incoming basic block corresponding to an operand of the PHI.
Definition: MemorySSA.h:544
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
llvm::MemorySSAWalkerPrinterPass::MemorySSAWalkerPrinterPass
MemorySSAWalkerPrinterPass(raw_ostream &OS)
Definition: MemorySSA.h:973
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
llvm::MemorySSAAnalysis::Result::MSSA
std::unique_ptr< MemorySSA > MSSA
Definition: MemorySSA.h:948
llvm::GraphTraits< Inverse< MemoryAccess * > >::ChildIteratorType
MemoryAccess::iterator ChildIteratorType
Definition: MemorySSA.h:1183
llvm::ilist_alloc_traits
Use delete by default for iplist and ilist.
Definition: ilist.h:41
llvm::MemoryDef
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:372
llvm::MSSAHelpers::DefsOnlyTag
Definition: MemorySSA.h:125
llvm::MemorySSA::getDomTree
DominatorTree & getDomTree() const
Definition: MemorySSA.h:725
llvm::MemorySSA::InsertionPlace
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:788
llvm::GraphTraits< Inverse< MemoryAccess * > >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MemorySSA.h:1186
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1861
llvm::MemoryAccess::const_iterator
const_user_iterator const_iterator
Definition: MemorySSA.h:171
llvm::upward_defs_iterator::getPhiArgBlock
BasicBlock * getPhiArgBlock() const
Definition: MemorySSA.h:1236
llvm::MemoryPhi::incoming_values
op_range incoming_values()
Definition: MemorySSA.h:522
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
iterator_range.h
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::MemoryUse::DECLARE_TRANSPARENT_OPERAND_ACCESSORS
DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)
llvm::MemoryDef::MemoryDef
MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB, unsigned Ver)
Definition: MemorySSA.h:378
llvm::MemoryPhi::unorderedDeleteIncomingBlock
void unorderedDeleteIncomingBlock(const BasicBlock *BB)
Definition: MemorySSA.h:614
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::memoryaccess_def_iterator_base::memoryaccess_def_iterator_base
memoryaccess_def_iterator_base()=default
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:934
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::MemoryPhi::getIncomingValue
MemoryAccess * getIncomingValue(unsigned I) const
Return incoming value number x.
Definition: MemorySSA.h:530
llvm::MemorySSAWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: MemorySSA.cpp:2392
llvm::const_memoryaccess_def_iterator
memoryaccess_def_iterator_base< const MemoryAccess > const_memoryaccess_def_iterator
Definition: MemorySSA.h:138
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
llvm::MemoryAccessPair
std::pair< MemoryAccess *, MemoryLocation > MemoryAccessPair
Definition: MemorySSA.h:1094
llvm::MemorySSA::getBlockDefs
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
Definition: MemorySSA.h:765
llvm::MemoryPhi::block_end
block_iterator block_end()
Definition: MemorySSA.h:508
llvm::ilist_node_impl< ilist_detail::compute_node_options< MemoryAccess, Options... >::type >::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::MemoryPhi::allocHungoffUses
void allocHungoffUses(unsigned N)
this is more complicated than the generic User::allocHungoffUses, because we have to allocate Uses fo...
Definition: MemorySSA.h:640
llvm::memoryaccess_def_iterator_base::operator*
std::iterator_traits< BaseT >::pointer operator*() const
Definition: MemorySSA.h:1126
llvm::MemoryPhi::setIncomingValue
void setIncomingValue(unsigned I, MemoryAccess *V)
Definition: MemorySSA.h:531
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
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::MemoryAccess
Definition: MemorySSA.h:142
llvm::DomTreeNodeBase< BasicBlock >
llvm::MemoryPhi::getID
unsigned getID() const
Definition: MemorySSA.h:632
llvm::MemoryPhi::setIncomingBlock
void setIncomingBlock(unsigned I, BasicBlock *BB)
Definition: MemorySSA.h:555
llvm::ilist_node
Definition: ilist_node.h:149
llvm::MemoryAccess::setBlock
void setBlock(BasicBlock *BB)
Used by MemorySSA to change the block of a MemoryAccess when it is moved.
Definition: MemorySSA.h:217
llvm::MemoryUse::MemoryUse
MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
Definition: MemorySSA.h:316
llvm::ConstMemoryAccessPair
std::pair< const MemoryAccess *, MemoryLocation > ConstMemoryAccessPair
Definition: MemorySSA.h:1095
llvm::memoryaccess_def_iterator_base::operator++
memoryaccess_def_iterator_base & operator++()
Definition: MemorySSA.h:1136
std
Definition: BitVector.h:851
llvm::Value::user_iterator
user_iterator_impl< User > user_iterator
Definition: Value.h:390
llvm::MemoryUseOrDef::getDefiningAccess
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:262
llvm::LocationSize::beforeOrAfterPointer
constexpr static LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:130
llvm::MemoryDef::setOptimized
void setOptimized(MemoryAccess *MA)
Definition: MemorySSA.h:392
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::MemoryAccess::getIterator
AllAccessType::const_self_iterator getIterator() const
Definition: MemorySSA.h:186
llvm::MemoryUseOrDef::resetOptimized
void resetOptimized()
Reset the ID of what this MemoryUse was optimized to, causing it to be rewalked by the walker if nece...
Definition: MemorySSA.h:688
llvm::MemoryUseOrDef::isOptimized
bool isOptimized() const
Do we have an optimized use?
Definition: MemorySSA.h:669
llvm::MemoryUseOrDef::setOptimized
void setOptimized(MemoryAccess *)
Sets the optimized use for a MemoryDef.
Definition: MemorySSA.h:681
llvm::MemoryUse::resetOptimized
void resetOptimized()
Definition: MemorySSA.h:346
llvm::MemorySSAWrapperPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: MemorySSA.cpp:2405
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::MemoryPhi::MemoryPhi
MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds=0)
Definition: MemorySSA.h:489
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
llvm::GraphTraits< MemoryAccess * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MemorySSA.h:1177
llvm::OperandTraits< MemoryUseOrDef >::op_end
static Use * op_end(MemoryUseOrDef *MUD)
Definition: MemorySSA.h:433
llvm::MemoryAccess::dump
void dump() const
Definition: MemorySSA.cpp:2217
llvm::MemorySSA::getWritableBlockAccesses
AccessList * getWritableBlockAccesses(const BasicBlock *BB) const
Definition: MemorySSA.h:808
llvm::Inverse
Definition: GraphTraits.h:97
llvm::MemorySSAWrapperPass::getMSSA
MemorySSA & getMSSA()
Definition: MemorySSA.h:992
DECLARE_TRANSPARENT_OPERAND_ACCESSORS
#define DECLARE_TRANSPARENT_OPERAND_ACCESSORS(VALUECLASS)
Macro for generating in-class operand accessor declarations.
Definition: OperandTraits.h:110
llvm::MemorySSAWalkerPrinterPass
Printer pass for MemorySSA via the walker.
Definition: MemorySSA.h:968
llvm::MemoryPhi::blocks
iterator_range< block_iterator > blocks()
Definition: MemorySSA.h:514
llvm::simple_ilist::end
iterator end()
Definition: simple_ilist.h:119
llvm::MemorySSAWalkerPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2367
SmallVector.h
User.h
llvm::MemoryAccess::getDefsIterator
DefsOnlyType::self_iterator getDefsIterator()
Definition: MemorySSA.h:195
Dominators.h
N
#define N
llvm::Value::deleteValue
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:109
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::FixedNumOperandTraits
FixedNumOperandTraits - determine the allocation regime of the Use array when it is a prefix to the U...
Definition: OperandTraits.h:30
llvm::simple_ilist
A simple intrusive list implementation.
Definition: simple_ilist.h:78
ilist_node.h
llvm::MemoryPhi::getIncomingValueForBlock
MemoryAccess * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: MemorySSA.h:579
llvm::MemorySSAAnalysis::Result::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Definition: LoopAnalysisManager.cpp:29
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:399
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::MemoryUse::setOptimized
void setOptimized(MemoryAccess *DMA)
Definition: MemorySSA.h:330
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
llvm::MemoryUse::isOptimized
bool isOptimized() const
Whether the MemoryUse is optimized.
Definition: MemorySSA.h:338
llvm::upward_defs_end
upward_defs_iterator upward_defs_end()
Definition: MemorySSA.h:1282
llvm::MemorySSAUtil::defClobbersUseOrDef
static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, AliasAnalysis &AA)
Definition: MemorySSA.cpp:345
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
llvm::MemorySSAWalker
This is the generic walker interface for walkers of MemorySSA.
Definition: MemorySSA.h:1015
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::MemorySSAPrinterLegacyPass::MemorySSAPrinterLegacyPass
MemorySSAPrinterLegacyPass()
Definition: MemorySSA.cpp:2227
llvm::HungoffOperandTraits
HungoffOperandTraits - determine the allocation regime of the Use array when it is not a prefix to th...
Definition: OperandTraits.h:95
llvm::GraphTraits< MemoryAccess * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: MemorySSA.h:1176
llvm::def_chain_iterator::operator==
bool operator==(const def_chain_iterator &O) const
Definition: MemorySSA.h:1325
llvm::memoryaccess_def_iterator_base::memoryaccess_def_iterator_base
memoryaccess_def_iterator_base(T *Start)
Definition: MemorySSA.h:1107
MemorySSA
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1806
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::DerivedUser
Extension point for the Value hierarchy.
Definition: DerivedUser.h:27
llvm::MemoryUse::getOptimized
MemoryAccess * getOptimized() const
Definition: MemorySSA.h:342
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::def_chain_iterator
Walks the defining accesses of MemoryDefs.
Definition: MemorySSA.h:1303
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1251
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::GraphTraits< MemoryAccess * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MemorySSA.h:1178
llvm::OperandTraits< MemoryUseOrDef >::op_begin
static Use * op_begin(MemoryUseOrDef *MUD)
Definition: MemorySSA.h:427
llvm::MemoryDef::getOptimized
MemoryAccess * getOptimized() const
Definition: MemorySSA.h:397