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