LLVM  15.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  // Retrieve AliasResult type of the optimized access. Ideally this would be
276  // returned by the caching walker and may go away in the future.
278  return isOptimized() ? OptimizedAccessAlias : None;
279  }
280 
281  /// Reset the ID of what this MemoryUse was optimized to, causing it to
282  /// be rewalked by the walker if necessary.
283  /// This really should only be called by tests.
284  inline void resetOptimized();
285 
286 protected:
287  friend class MemorySSA;
288  friend class MemorySSAUpdater;
289 
290  MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
291  DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,
292  unsigned NumOperands)
293  : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands),
294  MemoryInstruction(MI), OptimizedAccessAlias(AliasResult::MayAlias) {
295  setDefiningAccess(DMA);
296  }
297 
298  // Use deleteValue() to delete a generic MemoryUseOrDef.
299  ~MemoryUseOrDef() = default;
300 
302  OptimizedAccessAlias = AR;
303  }
304 
306  MemoryAccess *DMA, bool Optimized = false,
308  if (!Optimized) {
309  setOperand(0, DMA);
310  return;
311  }
312  setOptimized(DMA);
314  }
315 
316 private:
317  Instruction *MemoryInstruction;
318  Optional<AliasResult> OptimizedAccessAlias;
319 };
320 
321 /// Represents read-only accesses to memory
322 ///
323 /// In particular, the set of Instructions that will be represented by
324 /// MemoryUse's is exactly the set of Instructions for which
325 /// AliasAnalysis::getModRefInfo returns "Ref".
326 class MemoryUse final : public MemoryUseOrDef {
327 public:
329 
331  : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB,
332  /*NumOperands=*/1) {}
333 
334  // allocate space for exactly one operand
335  void *operator new(size_t S) { return User::operator new(S, 1); }
336  void operator delete(void *Ptr) { User::operator delete(Ptr); }
337 
338  static bool classof(const Value *MA) {
339  return MA->getValueID() == MemoryUseVal;
340  }
341 
342  void print(raw_ostream &OS) const;
343 
345  OptimizedID = DMA->getID();
346  setOperand(0, DMA);
347  }
348 
349  /// Whether the MemoryUse is optimized. If ensureOptimizedUses() was called,
350  /// uses will usually be optimized, but this is not guaranteed (e.g. due to
351  /// invalidation and optimization limits.)
352  bool isOptimized() const {
353  return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
354  }
355 
357  return getDefiningAccess();
358  }
359 
360  void resetOptimized() {
361  OptimizedID = INVALID_MEMORYACCESS_ID;
362  }
363 
364 protected:
365  friend class MemorySSA;
366 
367 private:
368  static void deleteMe(DerivedUser *Self);
369 
370  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
371 };
372 
373 template <>
374 struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {};
376 
377 /// Represents a read-write access to memory, whether it is a must-alias,
378 /// or a may-alias.
379 ///
380 /// In particular, the set of Instructions that will be represented by
381 /// MemoryDef's is exactly the set of Instructions for which
382 /// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".
383 /// Note that, in order to provide def-def chains, all defs also have a use
384 /// associated with them. This use points to the nearest reaching
385 /// MemoryDef/MemoryPhi.
386 class MemoryDef final : public MemoryUseOrDef {
387 public:
388  friend class MemorySSA;
389 
391 
393  unsigned Ver)
394  : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB,
395  /*NumOperands=*/2),
396  ID(Ver) {}
397 
398  // allocate space for exactly two operands
399  void *operator new(size_t S) { return User::operator new(S, 2); }
400  void operator delete(void *Ptr) { User::operator delete(Ptr); }
401 
402  static bool classof(const Value *MA) {
403  return MA->getValueID() == MemoryDefVal;
404  }
405 
407  setOperand(1, MA);
408  OptimizedID = MA->getID();
409  }
410 
412  return cast_or_null<MemoryAccess>(getOperand(1));
413  }
414 
415  bool isOptimized() const {
416  return getOptimized() && OptimizedID == getOptimized()->getID();
417  }
418 
419  void resetOptimized() {
420  OptimizedID = INVALID_MEMORYACCESS_ID;
421  setOperand(1, nullptr);
422  }
423 
424  void print(raw_ostream &OS) const;
425 
426  unsigned getID() const { return ID; }
427 
428 private:
429  static void deleteMe(DerivedUser *Self);
430 
431  const unsigned ID;
432  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
433 };
434 
435 template <>
436 struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};
438 
439 template <>
441  static Use *op_begin(MemoryUseOrDef *MUD) {
442  if (auto *MU = dyn_cast<MemoryUse>(MUD))
444  return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
445  }
446 
447  static Use *op_end(MemoryUseOrDef *MUD) {
448  if (auto *MU = dyn_cast<MemoryUse>(MUD))
450  return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));
451  }
452 
453  static unsigned operands(const MemoryUseOrDef *MUD) {
454  if (const auto *MU = dyn_cast<MemoryUse>(MUD))
456  return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));
457  }
458 };
459 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)
460 
461 /// Represents phi nodes for memory accesses.
462 ///
463 /// These have the same semantic as regular phi nodes, with the exception that
464 /// only one phi will ever exist in a given basic block.
465 /// Guaranteeing one phi per block means guaranteeing there is only ever one
466 /// valid reaching MemoryDef/MemoryPHI along each path to the phi node.
467 /// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or
468 /// a MemoryPhi's operands.
469 /// That is, given
470 /// if (a) {
471 /// store %a
472 /// store %b
473 /// }
474 /// it *must* be transformed into
475 /// if (a) {
476 /// 1 = MemoryDef(liveOnEntry)
477 /// store %a
478 /// 2 = MemoryDef(1)
479 /// store %b
480 /// }
481 /// and *not*
482 /// if (a) {
483 /// 1 = MemoryDef(liveOnEntry)
484 /// store %a
485 /// 2 = MemoryDef(liveOnEntry)
486 /// store %b
487 /// }
488 /// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the
489 /// end of the branch, and if there are not two phi nodes, one will be
490 /// disconnected completely from the SSA graph below that point.
491 /// Because MemoryUse's do not generate new definitions, they do not have this
492 /// issue.
493 class MemoryPhi final : public MemoryAccess {
494  // allocate space for exactly zero operands
495  void *operator new(size_t S) { return User::operator new(S); }
496 
497 public:
498  void operator delete(void *Ptr) { User::operator delete(Ptr); }
499 
500  /// Provide fast operand accessors
502 
503  MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
504  : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),
505  ReservedSpace(NumPreds) {
506  allocHungoffUses(ReservedSpace);
507  }
508 
509  // Block iterator interface. This provides access to the list of incoming
510  // basic blocks, which parallels the list of incoming values.
513 
515  return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);
516  }
517 
519  return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);
520  }
521 
522  block_iterator block_end() { return block_begin() + getNumOperands(); }
523 
525  return block_begin() + getNumOperands();
526  }
527 
529  return make_range(block_begin(), block_end());
530  }
531 
533  return make_range(block_begin(), block_end());
534  }
535 
536  op_range incoming_values() { return operands(); }
537 
538  const_op_range incoming_values() const { return operands(); }
539 
540  /// Return the number of incoming edges
541  unsigned getNumIncomingValues() const { return getNumOperands(); }
542 
543  /// Return incoming value number x
544  MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
545  void setIncomingValue(unsigned I, MemoryAccess *V) {
546  assert(V && "PHI node got a null value!");
547  setOperand(I, V);
548  }
549 
550  static unsigned getOperandNumForIncomingValue(unsigned I) { return I; }
551  static unsigned getIncomingValueNumForOperand(unsigned I) { return I; }
552 
553  /// Return incoming basic block number @p i.
554  BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }
555 
556  /// Return incoming basic block corresponding
557  /// to an operand of the PHI.
558  BasicBlock *getIncomingBlock(const Use &U) const {
559  assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?");
560  return getIncomingBlock(unsigned(&U - op_begin()));
561  }
562 
563  /// Return incoming basic block corresponding
564  /// to value use iterator.
566  return getIncomingBlock(I.getUse());
567  }
568 
569  void setIncomingBlock(unsigned I, BasicBlock *BB) {
570  assert(BB && "PHI node got a null basic block!");
571  block_begin()[I] = BB;
572  }
573 
574  /// Add an incoming value to the end of the PHI list
576  if (getNumOperands() == ReservedSpace)
577  growOperands(); // Get more space!
578  // Initialize some new operands.
579  setNumHungOffUseOperands(getNumOperands() + 1);
580  setIncomingValue(getNumOperands() - 1, V);
581  setIncomingBlock(getNumOperands() - 1, BB);
582  }
583 
584  /// Return the first index of the specified basic
585  /// block in the value list for this PHI. Returns -1 if no instance.
586  int getBasicBlockIndex(const BasicBlock *BB) const {
587  for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
588  if (block_begin()[I] == BB)
589  return I;
590  return -1;
591  }
592 
594  int Idx = getBasicBlockIndex(BB);
595  assert(Idx >= 0 && "Invalid basic block argument!");
596  return getIncomingValue(Idx);
597  }
598 
599  // After deleting incoming position I, the order of incoming may be changed.
600  void unorderedDeleteIncoming(unsigned I) {
601  unsigned E = getNumOperands();
602  assert(I < E && "Cannot remove out of bounds Phi entry.");
603  // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
604  // itself should be deleted.
605  assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
606  "at least 2 values.");
607  setIncomingValue(I, getIncomingValue(E - 1));
608  setIncomingBlock(I, block_begin()[E - 1]);
609  setOperand(E - 1, nullptr);
610  block_begin()[E - 1] = nullptr;
611  setNumHungOffUseOperands(getNumOperands() - 1);
612  }
613 
614  // After deleting entries that satisfy Pred, remaining entries may have
615  // changed order.
616  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
617  for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
618  if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
619  unorderedDeleteIncoming(I);
620  E = getNumOperands();
621  --I;
622  }
623  assert(getNumOperands() >= 1 &&
624  "Cannot remove all incoming blocks in a MemoryPhi.");
625  }
626 
627  // After deleting incoming block BB, the incoming blocks order may be changed.
629  unorderedDeleteIncomingIf(
630  [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
631  }
632 
633  // After deleting incoming memory access MA, the incoming accesses order may
634  // be changed.
636  unorderedDeleteIncomingIf(
637  [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
638  }
639 
640  static bool classof(const Value *V) {
641  return V->getValueID() == MemoryPhiVal;
642  }
643 
644  void print(raw_ostream &OS) const;
645 
646  unsigned getID() const { return ID; }
647 
648 protected:
649  friend class MemorySSA;
650 
651  /// this is more complicated than the generic
652  /// User::allocHungoffUses, because we have to allocate Uses for the incoming
653  /// values and pointers to the incoming blocks, all in one allocation.
654  void allocHungoffUses(unsigned N) {
655  User::allocHungoffUses(N, /* IsPhi */ true);
656  }
657 
658 private:
659  // For debugging only
660  const unsigned ID;
661  unsigned ReservedSpace;
662 
663  /// This grows the operand list in response to a push_back style of
664  /// operation. This grows the number of ops by 1.5 times.
665  void growOperands() {
666  unsigned E = getNumOperands();
667  // 2 op PHI nodes are VERY common, so reserve at least enough for that.
668  ReservedSpace = std::max(E + E / 2, 2u);
669  growHungoffUses(ReservedSpace, /* IsPhi */ true);
670  }
671 
672  static void deleteMe(DerivedUser *Self);
673 };
674 
675 inline unsigned MemoryAccess::getID() const {
676  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
677  "only memory defs and phis have ids");
678  if (const auto *MD = dyn_cast<MemoryDef>(this))
679  return MD->getID();
680  return cast<MemoryPhi>(this)->getID();
681 }
682 
683 inline bool MemoryUseOrDef::isOptimized() const {
684  if (const auto *MD = dyn_cast<MemoryDef>(this))
685  return MD->isOptimized();
686  return cast<MemoryUse>(this)->isOptimized();
687 }
688 
690  if (const auto *MD = dyn_cast<MemoryDef>(this))
691  return MD->getOptimized();
692  return cast<MemoryUse>(this)->getOptimized();
693 }
694 
696  if (auto *MD = dyn_cast<MemoryDef>(this))
697  MD->setOptimized(MA);
698  else
699  cast<MemoryUse>(this)->setOptimized(MA);
700 }
701 
703  if (auto *MD = dyn_cast<MemoryDef>(this))
704  MD->resetOptimized();
705  else
706  cast<MemoryUse>(this)->resetOptimized();
707 }
708 
709 template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
711 
712 /// Encapsulates MemorySSA, including all data associated with memory
713 /// accesses.
714 class MemorySSA {
715 public:
717 
718  // MemorySSA must remain where it's constructed; Walkers it creates store
719  // pointers to it.
720  MemorySSA(MemorySSA &&) = delete;
721 
722  ~MemorySSA();
723 
724  MemorySSAWalker *getWalker();
725  MemorySSAWalker *getSkipSelfWalker();
726 
727  /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
728  /// access associated with it. If passed a basic block gets the memory phi
729  /// node that exists for that block, if there is one. Otherwise, this will get
730  /// a MemoryUseOrDef.
732  return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
733  }
734 
736  return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
737  }
738 
739  DominatorTree &getDomTree() const { return *DT; }
740 
741  void dump() const;
742  void print(raw_ostream &) const;
743 
744  /// Return true if \p MA represents the live on entry value
745  ///
746  /// Loads and stores from pointer arguments and other global values may be
747  /// defined by memory operations that do not occur in the current function, so
748  /// they may be live on entry to the function. MemorySSA represents such
749  /// memory state by the live on entry definition, which is guaranteed to occur
750  /// before any other memory access in the function.
751  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
752  return MA == LiveOnEntryDef.get();
753  }
754 
755  inline MemoryAccess *getLiveOnEntryDef() const {
756  return LiveOnEntryDef.get();
757  }
758 
759  // Sadly, iplists, by default, owns and deletes pointers added to the
760  // list. It's not currently possible to have two iplists for the same type,
761  // where one owns the pointers, and one does not. This is because the traits
762  // are per-type, not per-tag. If this ever changes, we should make the
763  // DefList an iplist.
765  using DefsList =
767 
768  /// Return the list of MemoryAccess's for a given basic block.
769  ///
770  /// This list is not modifiable by the user.
771  const AccessList *getBlockAccesses(const BasicBlock *BB) const {
772  return getWritableBlockAccesses(BB);
773  }
774 
775  /// Return the list of MemoryDef's and MemoryPhi's for a given basic
776  /// block.
777  ///
778  /// This list is not modifiable by the user.
779  const DefsList *getBlockDefs(const BasicBlock *BB) const {
780  return getWritableBlockDefs(BB);
781  }
782 
783  /// Given two memory accesses in the same basic block, determine
784  /// whether MemoryAccess \p A dominates MemoryAccess \p B.
785  bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
786 
787  /// Given two memory accesses in potentially different blocks,
788  /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.
789  bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;
790 
791  /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
792  /// dominates Use \p B.
793  bool dominates(const MemoryAccess *A, const Use &B) const;
794 
795  enum class VerificationLevel { Fast, Full };
796  /// Verify that MemorySSA is self consistent (IE definitions dominate
797  /// all uses, uses appear in the right places). This is used by unit tests.
798  void verifyMemorySSA(VerificationLevel = VerificationLevel::Fast) const;
799 
800  /// Used in various insertion functions to specify whether we are talking
801  /// about the beginning or end of a block.
802  enum InsertionPlace { Beginning, End, BeforeTerminator };
803 
804  /// By default, uses are *not* optimized during MemorySSA construction.
805  /// Calling this method will attempt to optimize all MemoryUses, if this has
806  /// not happened yet for this MemorySSA instance. This should be done if you
807  /// plan to query the clobbering access for most uses, or if you walk the
808  /// def-use chain of uses.
809  void ensureOptimizedUses();
810 
811 protected:
812  // Used by Memory SSA dumpers and wrapper pass
814  friend class MemorySSAUpdater;
815 
816  void verifyOrderingDominationAndDefUses(
818  void verifyDominationNumbers(const Function &F) const;
819  void verifyPrevDefInPhis(Function &F) const;
820 
821  // This is used by the use optimizer and updater.
823  auto It = PerBlockAccesses.find(BB);
824  return It == PerBlockAccesses.end() ? nullptr : It->second.get();
825  }
826 
827  // This is used by the use optimizer and updater.
829  auto It = PerBlockDefs.find(BB);
830  return It == PerBlockDefs.end() ? nullptr : It->second.get();
831  }
832 
833  // These is used by the updater to perform various internal MemorySSA
834  // machinsations. They do not always leave the IR in a correct state, and
835  // relies on the updater to fixup what it breaks, so it is not public.
836 
837  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
838  void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
839 
840  // Rename the dominator tree branch rooted at BB.
841  void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
843  renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
844  }
845 
846  void removeFromLookups(MemoryAccess *);
847  void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
848  void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
849  InsertionPlace);
850  void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
851  AccessList::iterator);
852  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
853  const MemoryUseOrDef *Template = nullptr,
854  bool CreationMustSucceed = true);
855 
856 private:
857  template <class AliasAnalysisType> class ClobberWalkerBase;
858  template <class AliasAnalysisType> class CachingWalker;
859  template <class AliasAnalysisType> class SkipSelfWalker;
860  class OptimizeUses;
861 
862  CachingWalker<AliasAnalysis> *getWalkerImpl();
863  void buildMemorySSA(BatchAAResults &BAA);
864 
865  void prepareForMoveTo(MemoryAccess *, BasicBlock *);
866  void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
867 
870 
871  void markUnreachableAsLiveOnEntry(BasicBlock *BB);
872  MemoryPhi *createMemoryPhi(BasicBlock *BB);
873  template <typename AliasAnalysisType>
874  MemoryUseOrDef *createNewAccess(Instruction *, AliasAnalysisType *,
875  const MemoryUseOrDef *Template = nullptr);
876  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
877  MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
878  void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
879  void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
881  bool SkipVisited = false, bool RenameAllUses = false);
882  AccessList *getOrCreateAccessList(const BasicBlock *);
883  DefsList *getOrCreateDefsList(const BasicBlock *);
884  void renumberBlock(const BasicBlock *) const;
885  AliasAnalysis *AA = nullptr;
886  DominatorTree *DT;
887  Function &F;
888 
889  // Memory SSA mappings
890  DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
891 
892  // These two mappings contain the main block to access/def mappings for
893  // MemorySSA. The list contained in PerBlockAccesses really owns all the
894  // MemoryAccesses.
895  // Both maps maintain the invariant that if a block is found in them, the
896  // corresponding list is not empty, and if a block is not found in them, the
897  // corresponding list is empty.
898  AccessMap PerBlockAccesses;
899  DefsMap PerBlockDefs;
900  std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef;
901 
902  // Domination mappings
903  // Note that the numbering is local to a block, even though the map is
904  // global.
905  mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
906  mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
907 
908  // Memory SSA building info
909  std::unique_ptr<ClobberWalkerBase<AliasAnalysis>> WalkerBase;
910  std::unique_ptr<CachingWalker<AliasAnalysis>> Walker;
911  std::unique_ptr<SkipSelfWalker<AliasAnalysis>> SkipWalker;
912  unsigned NextID = 0;
913  bool IsOptimized = false;
914 };
915 
916 /// Enables verification of MemorySSA.
917 ///
918 /// The checks which this flag enables is exensive and disabled by default
919 /// unless `EXPENSIVE_CHECKS` is defined. The flag `-verify-memoryssa` can be
920 /// used to selectively enable the verification without re-compilation.
921 extern bool VerifyMemorySSA;
922 
923 // Internal MemorySSA utils, for use by MemorySSA classes and walkers
925 protected:
926  friend class GVNHoist;
927  friend class MemorySSAWalker;
928 
929  // This function should not be used by new passes.
930  static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
931  AliasAnalysis &AA);
932 };
933 
934 // This pass does eager building and then printing of MemorySSA. It is used by
935 // the tests to be able to build, dump, and verify Memory SSA.
937 public:
939 
940  bool runOnFunction(Function &) override;
941  void getAnalysisUsage(AnalysisUsage &AU) const override;
942 
943  static char ID;
944 };
945 
946 /// An analysis that produces \c MemorySSA for a function.
947 ///
948 class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> {
950 
951  static AnalysisKey Key;
952 
953 public:
954  // Wrap MemorySSA result to ensure address stability of internal MemorySSA
955  // pointers after construction. Use a wrapper class instead of plain
956  // unique_ptr<MemorySSA> to avoid build breakage on MSVC.
957  struct Result {
958  Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
959 
960  MemorySSA &getMSSA() { return *MSSA.get(); }
961 
962  std::unique_ptr<MemorySSA> MSSA;
963 
964  bool invalidate(Function &F, const PreservedAnalyses &PA,
966  };
967 
969 };
970 
971 /// Printer pass for \c MemorySSA.
972 class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> {
973  raw_ostream &OS;
974 
975 public:
976  explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {}
977 
979 };
980 
981 /// Printer pass for \c MemorySSA via the walker.
983  : public PassInfoMixin<MemorySSAWalkerPrinterPass> {
984  raw_ostream &OS;
985 
986 public:
987  explicit MemorySSAWalkerPrinterPass(raw_ostream &OS) : OS(OS) {}
988 
990 };
991 
992 /// Verifier pass for \c MemorySSA.
993 struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
995 };
996 
997 /// Legacy analysis pass which computes \c MemorySSA.
999 public:
1001 
1002  static char ID;
1003 
1004  bool runOnFunction(Function &) override;
1005  void releaseMemory() override;
1006  MemorySSA &getMSSA() { return *MSSA; }
1007  const MemorySSA &getMSSA() const { return *MSSA; }
1008 
1009  void getAnalysisUsage(AnalysisUsage &AU) const override;
1010 
1011  void verifyAnalysis() const override;
1012  void print(raw_ostream &OS, const Module *M = nullptr) const override;
1013 
1014 private:
1015  std::unique_ptr<MemorySSA> MSSA;
1016 };
1017 
1018 /// This is the generic walker interface for walkers of MemorySSA.
1019 /// Walkers are used to be able to further disambiguate the def-use chains
1020 /// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
1021 /// you.
1022 /// In particular, while the def-use chains provide basic information, and are
1023 /// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
1024 /// MemoryUse as AliasAnalysis considers it, a user mant want better or other
1025 /// information. In particular, they may want to use SCEV info to further
1026 /// disambiguate memory accesses, or they may want the nearest dominating
1027 /// may-aliasing MemoryDef for a call or a store. This API enables a
1028 /// standardized interface to getting and using that info.
1030 public:
1032  virtual ~MemorySSAWalker() = default;
1033 
1035 
1036  /// Given a memory Mod/Ref/ModRef'ing instruction, calling this
1037  /// will give you the nearest dominating MemoryAccess that Mod's the location
1038  /// the instruction accesses (by skipping any def which AA can prove does not
1039  /// alias the location(s) accessed by the instruction given).
1040  ///
1041  /// Note that this will return a single access, and it must dominate the
1042  /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
1043  /// this will return the MemoryPhi, not the operand. This means that
1044  /// given:
1045  /// if (a) {
1046  /// 1 = MemoryDef(liveOnEntry)
1047  /// store %a
1048  /// } else {
1049  /// 2 = MemoryDef(liveOnEntry)
1050  /// store %b
1051  /// }
1052  /// 3 = MemoryPhi(2, 1)
1053  /// MemoryUse(3)
1054  /// load %a
1055  ///
1056  /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
1057  /// in the if (a) branch.
1060  assert(MA && "Handed an instruction that MemorySSA doesn't recognize?");
1061  return getClobberingMemoryAccess(MA);
1062  }
1063 
1064  /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
1065  /// but takes a MemoryAccess instead of an Instruction.
1067 
1068  /// Given a potentially clobbering memory access and a new location,
1069  /// calling this will give you the nearest dominating clobbering MemoryAccess
1070  /// (by skipping non-aliasing def links).
1071  ///
1072  /// This version of the function is mainly used to disambiguate phi translated
1073  /// pointers, where the value of a pointer may have changed from the initial
1074  /// memory access. Note that this expects to be handed either a MemoryUse,
1075  /// or an already potentially clobbering access. Unlike the above API, if
1076  /// given a MemoryDef that clobbers the pointer as the starting access, it
1077  /// will return that MemoryDef, whereas the above would return the clobber
1078  /// starting from the use side of the memory def.
1080  const MemoryLocation &) = 0;
1081 
1082  /// Given a memory access, invalidate anything this walker knows about
1083  /// that access.
1084  /// This API is used by walkers that store information to perform basic cache
1085  /// invalidation. This will be called by MemorySSA at appropriate times for
1086  /// the walker it uses or returns.
1087  virtual void invalidateInfo(MemoryAccess *) {}
1088 
1089 protected:
1090  friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
1091  // constructor.
1093 };
1094 
1095 /// A MemorySSAWalker that does no alias queries, or anything else. It
1096 /// simply returns the links as they were constructed by the builder.
1098 public:
1099  // Keep the overrides below from hiding the Instruction overload of
1100  // getClobberingMemoryAccess.
1102 
1105  const MemoryLocation &) override;
1106 };
1107 
1108 using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
1109 using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
1110 
1111 /// Iterator base class used to implement const and non-const iterators
1112 /// over the defining accesses of a MemoryAccess.
1113 template <class T>
1115  : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
1116  std::forward_iterator_tag, T, ptrdiff_t, T *,
1117  T *> {
1118  using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base;
1119 
1120 public:
1121  memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
1122  memoryaccess_def_iterator_base() = default;
1123 
1124  bool operator==(const memoryaccess_def_iterator_base &Other) const {
1125  return Access == Other.Access && (!Access || ArgNo == Other.ArgNo);
1126  }
1127 
1128  // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
1129  // block from the operand in constant time (In a PHINode, the uselist has
1130  // both, so it's just subtraction). We provide it as part of the
1131  // iterator to avoid callers having to linear walk to get the block.
1132  // If the operation becomes constant time on MemoryPHI's, this bit of
1133  // abstraction breaking should be removed.
1135  MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
1136  assert(MP && "Tried to get phi arg block when not iterating over a PHI");
1137  return MP->getIncomingBlock(ArgNo);
1138  }
1139 
1141  assert(Access && "Tried to access past the end of our iterator");
1142  // Go to the first argument for phis, and the defining access for everything
1143  // else.
1144  if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
1145  return MP->getIncomingValue(ArgNo);
1146  return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1147  }
1148 
1149  using BaseT::operator++;
1151  assert(Access && "Hit end of iterator");
1152  if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
1153  if (++ArgNo >= MP->getNumIncomingValues()) {
1154  ArgNo = 0;
1155  Access = nullptr;
1156  }
1157  } else {
1158  Access = nullptr;
1159  }
1160  return *this;
1161  }
1162 
1163 private:
1164  T *Access = nullptr;
1165  unsigned ArgNo = 0;
1166 };
1167 
1169  return memoryaccess_def_iterator(this);
1170 }
1171 
1173  return const_memoryaccess_def_iterator(this);
1174 }
1175 
1177  return memoryaccess_def_iterator();
1178 }
1179 
1182 }
1183 
1184 /// GraphTraits for a MemoryAccess, which walks defs in the normal case,
1185 /// and uses in the inverse case.
1186 template <> struct GraphTraits<MemoryAccess *> {
1189 
1190  static NodeRef getEntryNode(NodeRef N) { return N; }
1191  static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); }
1192  static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
1193 };
1194 
1195 template <> struct GraphTraits<Inverse<MemoryAccess *>> {
1198 
1199  static NodeRef getEntryNode(NodeRef N) { return N; }
1200  static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
1201  static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
1202 };
1203 
1204 /// Provide an iterator that walks defs, giving both the memory access,
1205 /// and the current pointer location, updating the pointer location as it
1206 /// changes due to phi node translation.
1207 ///
1208 /// This iterator, while somewhat specialized, is what most clients actually
1209 /// want when walking upwards through MemorySSA def chains. It takes a pair of
1210 /// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
1211 /// memory location through phi nodes for the user.
1213  : public iterator_facade_base<upward_defs_iterator,
1214  std::forward_iterator_tag,
1215  const MemoryAccessPair> {
1216  using BaseT = upward_defs_iterator::iterator_facade_base;
1217 
1218 public:
1220  bool *PerformedPhiTranslation = nullptr)
1221  : DefIterator(Info.first), Location(Info.second),
1222  OriginalAccess(Info.first), DT(DT),
1223  PerformedPhiTranslation(PerformedPhiTranslation) {
1224  CurrentPair.first = nullptr;
1225 
1226  WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
1227  fillInCurrentPair();
1228  }
1229 
1230  upward_defs_iterator() { CurrentPair.first = nullptr; }
1231 
1232  bool operator==(const upward_defs_iterator &Other) const {
1233  return DefIterator == Other.DefIterator;
1234  }
1235 
1236  typename std::iterator_traits<BaseT>::reference operator*() const {
1237  assert(DefIterator != OriginalAccess->defs_end() &&
1238  "Tried to access past the end of our iterator");
1239  return CurrentPair;
1240  }
1241 
1242  using BaseT::operator++;
1244  assert(DefIterator != OriginalAccess->defs_end() &&
1245  "Tried to access past the end of the iterator");
1246  ++DefIterator;
1247  if (DefIterator != OriginalAccess->defs_end())
1248  fillInCurrentPair();
1249  return *this;
1250  }
1251 
1252  BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
1253 
1254 private:
1255  /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1256  /// loop. In particular, this guarantees that it only references a single
1257  /// MemoryLocation during execution of the containing function.
1258  bool IsGuaranteedLoopInvariant(Value *Ptr) const;
1259 
1260  void fillInCurrentPair() {
1261  CurrentPair.first = *DefIterator;
1262  CurrentPair.second = Location;
1263  if (WalkingPhi && Location.Ptr) {
1264  // Mark size as unknown, if the location is not guaranteed to be
1265  // loop-invariant for any possible loop in the function. Setting the size
1266  // to unknown guarantees that any memory accesses that access locations
1267  // after the pointer are considered as clobbers, which is important to
1268  // catch loop carried dependences.
1269  if (Location.Ptr &&
1270  !IsGuaranteedLoopInvariant(const_cast<Value *>(Location.Ptr)))
1271  CurrentPair.second =
1273  PHITransAddr Translator(
1274  const_cast<Value *>(Location.Ptr),
1275  OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
1276 
1277  if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
1278  DefIterator.getPhiArgBlock(), DT,
1279  true)) {
1280  Value *TransAddr = Translator.getAddr();
1281  if (TransAddr != Location.Ptr) {
1282  CurrentPair.second = CurrentPair.second.getWithNewPtr(TransAddr);
1283 
1284  if (TransAddr &&
1285  !IsGuaranteedLoopInvariant(const_cast<Value *>(TransAddr)))
1286  CurrentPair.second = CurrentPair.second.getWithNewSize(
1288 
1289  if (PerformedPhiTranslation)
1290  *PerformedPhiTranslation = true;
1291  }
1292  }
1293  }
1294  }
1295 
1296  MemoryAccessPair CurrentPair;
1297  memoryaccess_def_iterator DefIterator;
1298  MemoryLocation Location;
1299  MemoryAccess *OriginalAccess = nullptr;
1300  DominatorTree *DT = nullptr;
1301  bool WalkingPhi = false;
1302  bool *PerformedPhiTranslation = nullptr;
1303 };
1304 
1305 inline upward_defs_iterator
1307  bool *PerformedPhiTranslation = nullptr) {
1308  return upward_defs_iterator(Pair, &DT, PerformedPhiTranslation);
1309 }
1310 
1312 
1313 inline iterator_range<upward_defs_iterator>
1315  return make_range(upward_defs_begin(Pair, DT), upward_defs_end());
1316 }
1317 
1318 /// Walks the defining accesses of MemoryDefs. Stops after we hit something that
1319 /// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when
1320 /// comparing against a null def_chain_iterator, this will compare equal only
1321 /// after walking said Phi/liveOnEntry.
1322 ///
1323 /// The UseOptimizedChain flag specifies whether to walk the clobbering
1324 /// access chain, or all the accesses.
1325 ///
1326 /// Normally, MemoryDef are all just def/use linked together, so a def_chain on
1327 /// a MemoryDef will walk all MemoryDefs above it in the program until it hits
1328 /// a phi node. The optimized chain walks the clobbering access of a store.
1329 /// So if you are just trying to find, given a store, what the next
1330 /// thing that would clobber the same memory is, you want the optimized chain.
1331 template <class T, bool UseOptimizedChain = false>
1333  : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>,
1334  std::forward_iterator_tag, MemoryAccess *> {
1335  def_chain_iterator() : MA(nullptr) {}
1336  def_chain_iterator(T MA) : MA(MA) {}
1337 
1338  T operator*() const { return MA; }
1339 
1341  // N.B. liveOnEntry has a null defining access.
1342  if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1343  if (UseOptimizedChain && MUD->isOptimized())
1344  MA = MUD->getOptimized();
1345  else
1346  MA = MUD->getDefiningAccess();
1347  } else {
1348  MA = nullptr;
1349  }
1350 
1351  return *this;
1352  }
1353 
1354  bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
1355 
1356 private:
1357  T MA;
1358 };
1359 
1360 template <class T>
1361 inline iterator_range<def_chain_iterator<T>>
1362 def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1363 #ifdef EXPENSIVE_CHECKS
1364  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
1365  "UpTo isn't in the def chain!");
1366 #endif
1368 }
1369 
1370 template <class T>
1373  def_chain_iterator<T, true>(nullptr));
1374 }
1375 
1376 } // end namespace llvm
1377 
1378 #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:951
llvm::MemoryPhi::classof
static bool classof(const Value *V)
Definition: MemorySSA.h:640
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:1097
llvm::Value::const_user_iterator
user_iterator_impl< const User > const_user_iterator
Definition: Value.h:391
llvm::AliasResult::MayAlias
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:102
llvm::MemoryPhi::unorderedDeleteIncomingIf
void unorderedDeleteIncomingIf(Fn &&Pred)
Definition: MemorySSA.h:616
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:689
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:828
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:565
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
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:512
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:1371
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:1212
Pass.h
llvm::MemoryDef::resetOptimized
void resetOptimized()
Definition: MemorySSA.h:419
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
TemplateParamKind::Template
@ Template
llvm::def_chain_iterator::def_chain_iterator
def_chain_iterator()
Definition: MemorySSA.h:1335
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:1168
llvm::MemorySSAPrinterPass
Printer pass for MemorySSA.
Definition: MemorySSA.h:972
llvm::MemoryLocation::getWithNewSize
MemoryLocation getWithNewSize(LocationSize NewSize) const
Definition: MemoryLocation.h:300
llvm::MemoryAccess::getID
unsigned getID() const
Used for debugging and tracking things about MemoryAccesses.
Definition: MemorySSA.h:675
llvm::MemoryAccess::~MemoryAccess
~MemoryAccess()=default
llvm::MemorySSA::renamePass
void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, SmallPtrSetImpl< BasicBlock * > &Visited)
Definition: MemorySSA.h:841
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:1340
llvm::MemorySSAWalker::MemorySSAWalker
MemorySSAWalker(MemorySSA *)
Definition: MemorySSA.cpp:2461
llvm::MemoryPhi::unorderedDeleteIncomingValue
void unorderedDeleteIncomingValue(const MemoryAccess *MA)
Definition: MemorySSA.h:635
llvm::MemoryAccess::getReverseIterator
AllAccessType::reverse_self_iterator getReverseIterator()
Definition: MemorySSA.h:189
llvm::MemorySSAWrapperPass::ID
static char ID
Definition: MemorySSA.h:1002
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:755
llvm::MemorySSAAnalysis::Result::getMSSA
MemorySSA & getMSSA()
Definition: MemorySSA.h:960
llvm::MemorySSA::VerificationLevel
VerificationLevel
Definition: MemorySSA.h:795
llvm::Optional
Definition: APInt.h:33
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
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:493
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:2251
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:958
llvm::MemoryDef::getID
unsigned getID() const
Definition: MemorySSA.h:426
llvm::MemoryUse
Represents read-only accesses to memory.
Definition: MemorySSA.h:326
DerivedUser.h
llvm::MemoryPhi::getOperandNumForIncomingValue
static unsigned getOperandNumForIncomingValue(unsigned I)
Definition: MemorySSA.h:550
llvm::DoNothingMemorySSAWalker::getClobberingMemoryAccess
MemoryAccess * getClobberingMemoryAccess(MemoryAccess *) override
Does the same thing as getClobberingMemoryAccess(const Instruction *I), but takes a MemoryAccess inst...
Definition: MemorySSA.cpp:2660
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:104
llvm::upward_defs_iterator::upward_defs_iterator
upward_defs_iterator()
Definition: MemorySSA.h:1230
llvm::upward_defs
iterator_range< upward_defs_iterator > upward_defs(const MemoryAccessPair &Pair, DominatorTree &DT)
Definition: MemorySSA.h:1314
llvm::MemoryUse::classof
static bool classof(const Value *MA)
Definition: MemorySSA.h:338
llvm::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:391
llvm::MemoryUseOrDef::setOptimizedAccessType
void setOptimizedAccessType(Optional< AliasResult > AR)
Definition: MemorySSA.h:301
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:554
size_t
llvm::MemoryUseOrDef::classof
static bool classof(const Value *MA)
Definition: MemorySSA.h:264
llvm::MemorySSAPrinterLegacyPass::ID
static char ID
Definition: MemorySSA.h:943
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:586
AliasAnalysis.h
llvm::MemoryPhi::block_end
const_block_iterator block_end() const
Definition: MemorySSA.h:524
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:290
PHITransAddr.h
llvm::OperandTraits< MemoryUseOrDef >::operands
static unsigned operands(const MemoryUseOrDef *MUD)
Definition: MemorySSA.h:453
llvm::MemoryAccess::iterator
user_iterator iterator
The user iterators for a memory access.
Definition: MemorySSA.h:170
llvm::MemorySSAWrapperPass::MemorySSAWrapperPass
MemorySSAWrapperPass()
Definition: MemorySSA.cpp:2433
llvm::MemorySSA::getMemoryAccess
MemoryPhi * getMemoryAccess(const BasicBlock *BB) const
Definition: MemorySSA.h:735
llvm::GraphTraits< Inverse< MemoryAccess * > >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MemorySSA.h:1201
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
llvm::MemorySSAPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2399
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:1338
llvm::MemorySSAWalker::MSSA
MemorySSA * MSSA
Definition: MemorySSA.h:1092
llvm::MemoryPhi::block_begin
const_block_iterator block_begin() const
Definition: MemorySSA.h:518
llvm::MemoryAccess::defs_end
memoryaccess_def_iterator defs_end()
Definition: MemorySSA.h:1176
llvm::AAResults
Definition: AliasAnalysis.h:511
llvm::MemorySSA::isLiveOnEntryDef
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:751
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:2437
llvm::MemorySSAAnalysis::Result
Definition: MemorySSA.h:957
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:402
llvm::upward_defs_iterator::upward_defs_iterator
upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT, bool *PerformedPhiTranslation=nullptr)
Definition: MemorySSA.h:1219
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:2367
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:2457
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:415
llvm::MemorySSAWalker::invalidateInfo
virtual void invalidateInfo(MemoryAccess *)
Given a memory access, invalidate anything this walker knows about that access.
Definition: MemorySSA.h:1087
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:2278
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:1199
llvm::Instruction
Definition: Instruction.h:42
llvm::MemorySSAAnalysis::run
Result run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2383
llvm::MemoryPhi::addIncoming
void addIncoming(MemoryAccess *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: MemorySSA.h:575
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
dominates
static bool dominates(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator B)
Definition: RegAllocFast.cpp:336
llvm::MemorySSA::getBlockAccesses
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
Definition: MemorySSA.h:771
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
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:976
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
llvm::MemoryPhi::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: MemorySSA.h:541
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:551
llvm::MemoryPhi::unorderedDeleteIncoming
void unorderedDeleteIncoming(unsigned I)
Definition: MemorySSA.h:600
llvm::upward_defs_iterator::operator*
std::iterator_traits< BaseT >::reference operator*() const
Definition: MemorySSA.h:1236
llvm::None
const NoneType None
Definition: None.h:24
llvm::MemoryAccess::getBlock
BasicBlock * getBlock() const
Definition: MemorySSA.h:164
llvm::MemorySSAPrinterLegacyPass
Definition: MemorySSA.h:936
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:1134
llvm::MemorySSAVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2424
llvm::MemoryPhi::block_begin
block_iterator block_begin()
Definition: MemorySSA.h:514
llvm::upward_defs_iterator::operator++
upward_defs_iterator & operator++()
Definition: MemorySSA.h:1243
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:1058
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:2445
llvm::def_chain_iterator::def_chain_iterator
def_chain_iterator(T MA)
Definition: MemorySSA.h:1336
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:240
llvm::MemoryUseOrDef::getOptimizedAccessType
Optional< AliasResult > getOptimizedAccessType() const
Definition: MemorySSA.h:277
llvm::MemorySSAUtil
Definition: MemorySSA.h:924
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:2197
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:1637
llvm::MemorySSAWrapperPass::getMSSA
const MemorySSA & getMSSA() const
Definition: MemorySSA.h:1007
llvm::MemoryPhi::blocks
iterator_range< const_block_iterator > blocks() const
Definition: MemorySSA.h:532
llvm::MemoryAccess::operator=
MemoryAccess & operator=(const MemoryAccess &)=delete
llvm::MemorySSAVerifierPass
Verifier pass for MemorySSA.
Definition: MemorySSA.h:993
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::upward_defs_iterator::operator==
bool operator==(const upward_defs_iterator &Other) const
Definition: MemorySSA.h:1232
llvm::def_chain
iterator_range< def_chain_iterator< T > > def_chain(T MA, MemoryAccess *UpTo=nullptr)
Definition: MemorySSA.h:1362
llvm::memoryaccess_def_iterator_base::operator==
bool operator==(const memoryaccess_def_iterator_base &Other) const
Definition: MemorySSA.h:1124
MemoryLocation.h
llvm::DenseMap
Definition: DenseMap.h:716
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:538
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:714
llvm::MemoryPhi::getIncomingBlock
BasicBlock * getIncomingBlock(const Use &U) const
Return incoming basic block corresponding to an operand of the PHI.
Definition: MemorySSA.h:558
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:731
llvm::MemorySSAWalkerPrinterPass::MemorySSAWalkerPrinterPass
MemorySSAWalkerPrinterPass(raw_ostream &OS)
Definition: MemorySSA.h:987
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:962
llvm::GraphTraits< Inverse< MemoryAccess * > >::ChildIteratorType
MemoryAccess::iterator ChildIteratorType
Definition: MemorySSA.h:1197
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:386
llvm::MSSAHelpers::DefsOnlyTag
Definition: MemorySSA.h:125
llvm::MemorySSA::getDomTree
DominatorTree & getDomTree() const
Definition: MemorySSA.h:739
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:802
llvm::GraphTraits< Inverse< MemoryAccess * > >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MemorySSA.h:1200
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:1675
llvm::MemoryAccess::const_iterator
const_user_iterator const_iterator
Definition: MemorySSA.h:171
llvm::upward_defs_begin
upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT, bool *PerformedPhiTranslation=nullptr)
Definition: MemorySSA.h:1306
llvm::upward_defs_iterator::getPhiArgBlock
BasicBlock * getPhiArgBlock() const
Definition: MemorySSA.h:1252
llvm::MemoryPhi::incoming_values
op_range incoming_values()
Definition: MemorySSA.h:536
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:392
llvm::MemoryPhi::unorderedDeleteIncomingBlock
void unorderedDeleteIncomingBlock(const BasicBlock *BB)
Definition: MemorySSA.h:628
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:948
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:544
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:2439
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::MemoryAccessPair
std::pair< MemoryAccess *, MemoryLocation > MemoryAccessPair
Definition: MemorySSA.h:1108
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:779
llvm::MemoryPhi::block_end
block_iterator block_end()
Definition: MemorySSA.h:522
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:654
llvm::memoryaccess_def_iterator_base::operator*
std::iterator_traits< BaseT >::pointer operator*() const
Definition: MemorySSA.h:1140
llvm::MemoryPhi::setIncomingValue
void setIncomingValue(unsigned I, MemoryAccess *V)
Definition: MemorySSA.h:545
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:646
llvm::MemoryPhi::setIncomingBlock
void setIncomingBlock(unsigned I, BasicBlock *BB)
Definition: MemorySSA.h:569
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:330
llvm::ConstMemoryAccessPair
std::pair< const MemoryAccess *, MemoryLocation > ConstMemoryAccessPair
Definition: MemorySSA.h:1109
llvm::memoryaccess_def_iterator_base::operator++
memoryaccess_def_iterator_base & operator++()
Definition: MemorySSA.h:1150
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:406
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:702
llvm::MemoryUseOrDef::isOptimized
bool isOptimized() const
Do we have an optimized use?
Definition: MemorySSA.h:683
llvm::MemoryUseOrDef::setOptimized
void setOptimized(MemoryAccess *)
Sets the optimized use for a MemoryDef.
Definition: MemorySSA.h:695
llvm::MemoryUse::resetOptimized
void resetOptimized()
Definition: MemorySSA.h:360
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:2452
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::MemoryPhi::MemoryPhi
MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds=0)
Definition: MemorySSA.h:503
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:1191
llvm::OperandTraits< MemoryUseOrDef >::op_end
static Use * op_end(MemoryUseOrDef *MUD)
Definition: MemorySSA.h:447
llvm::MemoryAccess::dump
void dump() const
Definition: MemorySSA.cpp:2264
llvm::MemorySSA::getWritableBlockAccesses
AccessList * getWritableBlockAccesses(const BasicBlock *BB) const
Definition: MemorySSA.h:822
llvm::Inverse
Definition: GraphTraits.h:97
llvm::MemorySSAWrapperPass::getMSSA
MemorySSA & getMSSA()
Definition: MemorySSA.h:1006
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:982
AA
llvm::MemoryPhi::blocks
iterator_range< block_iterator > blocks()
Definition: MemorySSA.h:528
llvm::simple_ilist::end
iterator end()
Definition: simple_ilist.h:119
llvm::MemorySSAWalkerPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2414
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:106
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:593
llvm::MemorySSAAnalysis::Result::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Definition: LoopAnalysisManager.cpp:28
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
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:344
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:352
llvm::upward_defs_end
upward_defs_iterator upward_defs_end()
Definition: MemorySSA.h:1311
llvm::MemorySSAUtil::defClobbersUseOrDef
static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, AliasAnalysis &AA)
Definition: MemorySSA.cpp:361
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:1029
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::MemorySSAPrinterLegacyPass::MemorySSAPrinterLegacyPass
MemorySSAPrinterLegacyPass()
Definition: MemorySSA.cpp:2274
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:1190
llvm::def_chain_iterator::operator==
bool operator==(const def_chain_iterator &O) const
Definition: MemorySSA.h:1354
llvm::memoryaccess_def_iterator_base::memoryaccess_def_iterator_base
memoryaccess_def_iterator_base(T *Start)
Definition: MemorySSA.h:1121
llvm::MemoryUseOrDef::setDefiningAccess
void setDefiningAccess(MemoryAccess *DMA, bool Optimized=false, Optional< AliasResult > AR=AliasResult(AliasResult::MayAlias))
Definition: MemorySSA.h:305
MemorySSA
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1775
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:356
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:1332
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1237
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:1192
llvm::OperandTraits< MemoryUseOrDef >::op_begin
static Use * op_begin(MemoryUseOrDef *MUD)
Definition: MemorySSA.h:441
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::MemoryDef::getOptimized
MemoryAccess * getOptimized() const
Definition: MemorySSA.h:411