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