1//===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10/// This file exposes an interface to building/using memory SSA to
11/// walk memory instructions using a use/def graph.
12///
13/// Memory SSA class builds an SSA form that links together memory access
14/// instructions such as loads, stores, atomics, and calls. Additionally, it
15/// does a trivial form of "heap versioning" Every time the memory state changes
16/// in the program, we generate a new heap version. It generates
17/// MemoryDef/Uses/Phis that are overlayed on top of the existing instructions.
18///
19/// As a trivial example,
20/// define i32 @main() #0 {
21/// entry:
22/// %call = call noalias i8* @_Znwm(i64 4) #2
23/// %0 = bitcast i8* %call to i32*
24/// %call1 = call noalias i8* @_Znwm(i64 4) #2
25/// %1 = bitcast i8* %call1 to i32*
26/// store i32 5, i32* %0, align 4
27/// store i32 7, i32* %1, align 4
28/// %2 = load i32* %0, align 4
29/// %3 = load i32* %1, align 4
30/// %add = add nsw i32 %2, %3
31/// ret i32 %add
32/// }
33///
34/// Will become
35/// define i32 @main() #0 {
36/// entry:
37/// ; 1 = MemoryDef(0)
38/// %call = call noalias i8* @_Znwm(i64 4) #3
39/// %2 = bitcast i8* %call to i32*
40/// ; 2 = MemoryDef(1)
41/// %call1 = call noalias i8* @_Znwm(i64 4) #3
42/// %4 = bitcast i8* %call1 to i32*
43/// ; 3 = MemoryDef(2)
44/// store i32 5, i32* %2, align 4
45/// ; 4 = MemoryDef(3)
46/// store i32 7, i32* %4, align 4
47/// ; MemoryUse(3)
48/// %7 = load i32* %2, align 4
49/// ; MemoryUse(4)
50/// %8 = load i32* %4, align 4
51/// %add = add nsw i32 %7, %8
52/// ret i32 %add
53/// }
54///
55/// Given this form, all the stores that could ever effect the load at %8 can be
56/// gotten by using the MemoryUse associated with it, and walking from use to
57/// def until you hit the top of the function.
58///
59/// Each def also has a list of users associated with it, so you can walk from
60/// both def to users, and users to defs. Note that we disambiguate MemoryUses,
61/// but not the RHS of MemoryDefs. You can see this above at %7, which would
62/// otherwise be a MemoryUse(4). Being disambiguated means that for a given
63/// store, all the MemoryUses on its use lists are may-aliases of that store
64/// (but the MemoryDefs on its use list may not be).
65///
66/// MemoryDefs are not disambiguated because it would require multiple reaching
67/// definitions, which would require multiple phis, and multiple memoryaccesses
68/// per instruction.
69///
70/// In addition to the def/use graph described above, MemoryDefs also contain
71/// an "optimized" definition use. The "optimized" use points to some def
72/// reachable through the memory def chain. The optimized def *may* (but is
73/// not required to) alias the original MemoryDef, but no def *closer* to the
74/// source def may alias it. As the name implies, the purpose of the optimized
75/// use is to allow caching of clobber searches for memory defs. The optimized
76/// def may be nullptr, in which case clients must walk the defining access
77/// chain.
78///
79/// When iterating the uses of a MemoryDef, both defining uses and optimized
80/// uses will be encountered. If only one type is needed, the client must
81/// filter the use walk.
82//
83//===----------------------------------------------------------------------===//
84
85#ifndef LLVM_ANALYSIS_MEMORYSSA_H
86#define LLVM_ANALYSIS_MEMORYSSA_H
87
88#include "llvm/ADT/DenseMap.h"
89#include "llvm/ADT/SmallPtrSet.h"
90#include "llvm/ADT/SmallVector.h"
91#include "llvm/ADT/ilist_node.h"
92#include "llvm/ADT/iterator_range.h"
93#include "llvm/Analysis/AliasAnalysis.h"
94#include "llvm/Analysis/MemoryLocation.h"
95#include "llvm/Analysis/PHITransAddr.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()
132 INVALID_MEMORYACCESS_ID = -1U
133};
134
135template <class T> class memoryaccess_def_iterator_base;
136using memoryaccess_def_iterator = memoryaccess_def_iterator_base<MemoryAccess>;
137using const_memoryaccess_def_iterator =
138 memoryaccess_def_iterator_base<const MemoryAccess>;
139
140// The base for all memory accesses. All memory accesses in a block are
141// linked together using an intrusive list.
142class MemoryAccess
143 : public DerivedUser,
144 public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,
145 public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {
146public:
147 using AllAccessType =
148 ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
149 using DefsOnlyType =
150 ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
151
152 MemoryAccess(const MemoryAccess &) = delete;
153 MemoryAccess &operator=(const MemoryAccess &) = delete;
154
155 void *operator new(size_t) = delete;
156
157 // Methods for support type inquiry through isa, cast, and
158 // dyn_cast
159 static bool classof(const Value *V) {
160 unsigned ID = V->getValueID();
161 return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal;
162 }
163
164 BasicBlock *getBlock() const { return Block; }
165
166 void print(raw_ostream &OS) const;
167 void dump() const;
168
169 /// The user iterators for a memory access
170 using iterator = user_iterator;
171 using const_iterator = const_user_iterator;
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.
176 memoryaccess_def_iterator defs_begin();
177 const_memoryaccess_def_iterator defs_begin() const;
178 memoryaccess_def_iterator defs_end();
179 const_memoryaccess_def_iterator defs_end() const;
180
181 /// Get the iterators for the all access list and the defs only list
182 /// We default to the all access list.
183 AllAccessType::self_iterator getIterator() {
184 return this->AllAccessType::getIterator();
185 }
186 AllAccessType::const_self_iterator getIterator() const {
187 return this->AllAccessType::getIterator();
188 }
189 AllAccessType::reverse_self_iterator getReverseIterator() {
190 return this->AllAccessType::getReverseIterator();
191 }
192 AllAccessType::const_reverse_self_iterator getReverseIterator() const {
193 return this->AllAccessType::getReverseIterator();
194 }
195 DefsOnlyType::self_iterator getDefsIterator() {
196 return this->DefsOnlyType::getIterator();
197 }
198 DefsOnlyType::const_self_iterator getDefsIterator() const {
199 return this->DefsOnlyType::getIterator();
200 }
201 DefsOnlyType::reverse_self_iterator getReverseDefsIterator() {
202 return this->DefsOnlyType::getReverseIterator();
203 }
204 DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const {
205 return this->DefsOnlyType::getReverseIterator();
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 <>
236struct ilist_alloc_traits<MemoryAccess> {
237 static void deleteNode(MemoryAccess *MA) { MA->deleteValue(); }
238};
239
240inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) {
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.
252class MemoryUseOrDef : public MemoryAccess {
253public:
254 void *operator new(size_t) = delete;
255
256 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
257
258 /// Get the instruction that this MemoryUse represents.
259 Instruction *getMemoryInst() const { return MemoryInstruction; }
260
261 /// Get the access that produces the memory state used by this Use.
262 MemoryAccess *getDefiningAccess() const { return getOperand(0); }
263
264 static bool classof(const Value *MA) {
265 return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal;
266 }
267
268 /// Do we have an optimized use?
269 inline bool isOptimized() const;
270 /// Return the MemoryAccess associated with the optimized use, or nullptr.
271 inline MemoryAccess *getOptimized() const;
272 /// Sets the optimized use for a MemoryDef.
273 inline void setOptimized(MemoryAccess *);
274
275 /// 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
284 MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
285 DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,
286 unsigned NumOperands)
287 : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands),
288 MemoryInstruction(MI) {
289 setDefiningAccess(DMA);
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:
314 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
315
316 MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
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(Size: S, Us: 1); }
322 void operator delete(void *Ptr) { User::operator delete(Usr: Ptr); }
323
324 static bool classof(const Value *MA) {
325 return MA->getValueID() == MemoryUseVal;
326 }
327
328 void print(raw_ostream &OS) const;
329
330 void setOptimized(MemoryAccess *DMA) {
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
342 MemoryAccess *getOptimized() const {
343 return getDefiningAccess();
344 }
345
346 void resetOptimized() {
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> {};
361DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUse, MemoryAccess)
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
376 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
377
378 MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
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(Size: S, Us: 2); }
386 void operator delete(void *Ptr) { User::operator delete(Usr: Ptr); }
387
388 static bool classof(const Value *MA) {
389 return MA->getValueID() == MemoryDefVal;
390 }
391
392 void setOptimized(MemoryAccess *MA) {
393 setOperand(1, MA);
394 OptimizedID = MA->getID();
395 }
396
397 MemoryAccess *getOptimized() const {
398 return cast_or_null<MemoryAccess>(Val: getOperand(1));
399 }
400
401 bool isOptimized() const {
402 return getOptimized() && OptimizedID == getOptimized()->getID();
403 }
404
405 void resetOptimized() {
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> {};
423DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess)
424
425template <>
426struct OperandTraits<MemoryUseOrDef> {
427 static Use *op_begin(MemoryUseOrDef *MUD) {
428 if (auto *MU = dyn_cast<MemoryUse>(Val: MUD))
429 return OperandTraits<MemoryUse>::op_begin(U: MU);
430 return OperandTraits<MemoryDef>::op_begin(U: cast<MemoryDef>(Val: MUD));
431 }
432
433 static Use *op_end(MemoryUseOrDef *MUD) {
434 if (auto *MU = dyn_cast<MemoryUse>(Val: MUD))
435 return OperandTraits<MemoryUse>::op_end(U: MU);
436 return OperandTraits<MemoryDef>::op_end(U: cast<MemoryDef>(Val: MUD));
437 }
438
439 static unsigned operands(const MemoryUseOrDef *MUD) {
440 if (const auto *MU = dyn_cast<MemoryUse>(Val: MUD))
441 return OperandTraits<MemoryUse>::operands(MU);
442 return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(Val: 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(Size: S); }
482
483public:
484 void operator delete(void *Ptr) { User::operator delete(Usr: Ptr); }
485
486 /// Provide fast operand accessors
487 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
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(N: 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.
497 using block_iterator = BasicBlock **;
498 using const_block_iterator = BasicBlock *const *;
499
500 block_iterator block_begin() {
501 return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);
502 }
503
504 const_block_iterator block_begin() const {
505 return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);
506 }
507
508 block_iterator block_end() { return block_begin() + getNumOperands(); }
509
510 const_block_iterator block_end() const {
511 return block_begin() + getNumOperands();
512 }
513
514 iterator_range<block_iterator> blocks() {
515 return make_range(x: block_begin(), y: block_end());
516 }
517
518 iterator_range<const_block_iterator> blocks() const {
519 return make_range(x: block_begin(), y: 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(I: unsigned(&U - op_begin()));
547 }
548
549 /// Return incoming basic block corresponding
550 /// to value use iterator.
551 BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const {
552 return getIncomingBlock(U: 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
561 void addIncoming(MemoryAccess *V, BasicBlock *BB) {
562 if (getNumOperands() == ReservedSpace)
563 growOperands(); // Get more space!
564 // Initialize some new operands.
565 setNumHungOffUseOperands(getNumOperands() + 1);
566 setIncomingValue(I: getNumOperands() - 1, V);
567 setIncomingBlock(I: 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
579 MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const {
580 int Idx = getBasicBlockIndex(BB);
581 assert(Idx >= 0 && "Invalid basic block argument!");
582 return getIncomingValue(I: 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, V: getIncomingValue(I: E - 1));
594 setIncomingBlock(I, BB: 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.
614 void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
615 unorderedDeleteIncomingIf(
616 Pred: [&](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.
621 void unorderedDeleteIncomingValue(const MemoryAccess *MA) {
622 unorderedDeleteIncomingIf(
623 Pred: [&](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 */ 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(a: E + E / 2, b: 2u);
655 growHungoffUses(N: ReservedSpace, /* IsPhi */ 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>(Val: this))
665 return MD->getID();
666 return cast<MemoryPhi>(Val: this)->getID();
667}
668
669inline bool MemoryUseOrDef::isOptimized() const {
670 if (const auto *MD = dyn_cast<MemoryDef>(Val: this))
671 return MD->isOptimized();
672 return cast<MemoryUse>(Val: this)->isOptimized();
673}
674
675inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
676 if (const auto *MD = dyn_cast<MemoryDef>(Val: this))
677 return MD->getOptimized();
678 return cast<MemoryUse>(Val: this)->getOptimized();
679}
680
681inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
682 if (auto *MD = dyn_cast<MemoryDef>(Val: this))
683 MD->setOptimized(MA);
684 else
685 cast<MemoryUse>(Val: this)->setOptimized(MA);
686}
687
688inline void MemoryUseOrDef::resetOptimized() {
689 if (auto *MD = dyn_cast<MemoryDef>(Val: this))
690 MD->resetOptimized();
691 else
692 cast<MemoryUse>(Val: this)->resetOptimized();
693}
694
695template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
696DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)
697
698/// Encapsulates MemorySSA, including all data associated with memory
699/// accesses.
700class MemorySSA {
701public:
702 MemorySSA(Function &, AliasAnalysis *, DominatorTree *);
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.
717 MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
718 return cast_or_null<MemoryUseOrDef>(Val: ValueToMemoryAccess.lookup(Val: I));
719 }
720
721 MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
722 return cast_or_null<MemoryPhi>(Val: ValueToMemoryAccess.lookup(Val: cast<Value>(Val: 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
741 inline MemoryAccess *getLiveOnEntryDef() const {
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.
750 using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
751 using DefsList =
752 simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
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.
809 AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
810 auto It = PerBlockAccesses.find(Val: BB);
811 return It == PerBlockAccesses.end() ? nullptr : It->second.get();
812 }
813
814 // This is used by the use optimizer and updater.
815 DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
816 auto It = PerBlockDefs.find(Val: 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,
829 SmallPtrSetImpl<BasicBlock *> &Visited) {
830 renamePass(DT->getNode(BB), IncomingVal, Visited, SkipVisited: true, RenameAllUses: 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
855 using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
856 using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
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,
867 SmallPtrSetImpl<BasicBlock *> &Visited,
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;
893 mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
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
911class MemorySSAUtil {
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> {
924 friend 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,
940 FunctionAnalysisManager::Invalidator &Inv);
941 };
942
943 Result run(Function &F, FunctionAnalysisManager &AM);
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
955 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
956
957 static bool isRequired() { return true; }
958};
959
960/// Printer pass for \c MemorySSA via the walker.
961class MemorySSAWalkerPrinterPass
962 : public PassInfoMixin<MemorySSAWalkerPrinterPass> {
963 raw_ostream &OS;
964
965public:
966 explicit MemorySSAWalkerPrinterPass(raw_ostream &OS) : OS(OS) {}
967
968 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
969
970 static bool isRequired() { return true; }
971};
972
973/// Verifier pass for \c MemorySSA.
974struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
975 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
976 static bool isRequired() { return true; }
977};
978
979/// Legacy analysis pass which computes \c MemorySSA.
980class MemorySSAWrapperPass : public FunctionPass {
981public:
982 MemorySSAWrapperPass();
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.
1011class MemorySSAWalker {
1012public:
1013 MemorySSAWalker(MemorySSA *);
1014 virtual ~MemorySSAWalker() = default;
1015
1016 using MemoryAccessSet = SmallVector<MemoryAccess *, 8>;
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.
1040 MemoryAccess *getClobberingMemoryAccess(const Instruction *I,
1041 BatchAAResults &AA) {
1042 MemoryAccess *MA = MSSA->getMemoryAccess(I);
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.
1049 virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
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.
1063 virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1064 const MemoryLocation &,
1065 BatchAAResults &AA) = 0;
1066
1067 MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
1068 BatchAAResults BAA(MSSA->getAA());
1069 return getClobberingMemoryAccess(I, AA&: BAA);
1070 }
1071
1072 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) {
1073 BatchAAResults BAA(MSSA->getAA());
1074 return getClobberingMemoryAccess(MA, AA&: BAA);
1075 }
1076
1077 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1078 const MemoryLocation &Loc) {
1079 BatchAAResults BAA(MSSA->getAA());
1080 return getClobberingMemoryAccess(MA, Loc, AA&: 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.
1093 MemorySSA *MSSA;
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.
1098class DoNothingMemorySSAWalker final : public MemorySSAWalker {
1099public:
1100 // Keep the overrides below from hiding the Instruction overload of
1101 // getClobberingMemoryAccess.
1102 using MemorySSAWalker::getClobberingMemoryAccess;
1103
1104 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1105 BatchAAResults &) override;
1106 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
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>
1117class memoryaccess_def_iterator_base
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) {}
1125 memoryaccess_def_iterator_base() = default;
1126
1127 bool operator==(const memoryaccess_def_iterator_base &Other) const {
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.
1137 BasicBlock *getPhiArgBlock() const {
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(I: 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(I: ArgNo);
1149 return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1150 }
1151
1152 using BaseT::operator++;
1153 memoryaccess_def_iterator_base &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
1171inline memoryaccess_def_iterator MemoryAccess::defs_begin() {
1172 return memoryaccess_def_iterator(this);
1173}
1174
1175inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const {
1176 return const_memoryaccess_def_iterator(this);
1177}
1178
1179inline memoryaccess_def_iterator MemoryAccess::defs_end() {
1180 return memoryaccess_def_iterator();
1181}
1182
1183inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
1184 return const_memoryaccess_def_iterator();
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 *> {
1190 using NodeRef = MemoryAccess *;
1191 using ChildIteratorType = memoryaccess_def_iterator;
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 *>> {
1199 using NodeRef = MemoryAccess *;
1200 using ChildIteratorType = MemoryAccess::iterator;
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.
1215class upward_defs_iterator
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:
1222 upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT)
1223 : DefIterator(Info.first), Location(Info.second),
1224 OriginalAccess(Info.first), DT(DT) {
1225 CurrentPair.first = nullptr;
1226
1227 WalkingPhi = Info.first && isa<MemoryPhi>(Val: Info.first);
1228 fillInCurrentPair();
1229 }
1230
1231 upward_defs_iterator() { CurrentPair.first = nullptr; }
1232
1233 bool operator==(const upward_defs_iterator &Other) const {
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++;
1244 upward_defs_iterator &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(CurBB: OriginalAccess->getBlock(),
1271 PredBB: DefIterator.getPhiArgBlock(), DT, MustDominate: true))
1272 if (Addr != CurrentPair.second.Ptr)
1273 CurrentPair.second = CurrentPair.second.getWithNewPtr(NewPtr: 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(Ptr: CurrentPair.second.Ptr))
1281 CurrentPair.second = CurrentPair.second.getWithNewSize(
1282 NewSize: LocationSize::beforeOrAfterPointer());
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
1295upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT) {
1296 return upward_defs_iterator(Pair, &DT);
1297}
1298
1299inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
1300
1301inline iterator_range<upward_defs_iterator>
1302upward_defs(const MemoryAccessPair &Pair, DominatorTree &DT) {
1303 return make_range(x: upward_defs_begin(Pair, DT), y: 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>
1320struct def_chain_iterator
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
1328 def_chain_iterator &operator++() {
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
1355 return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1356}
1357
1358template <class T>
1359inline iterator_range<def_chain_iterator<T, true>> optimized_def_chain(T MA) {
1360 return make_range(def_chain_iterator<T, true>(MA),
1361 def_chain_iterator<T, true>(nullptr));
1362}
1363
1364} // end namespace llvm
1365
1366#endif // LLVM_ANALYSIS_MEMORYSSA_H
1367

source code of llvm/include/llvm/Analysis/MemorySSA.h