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