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