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