1	//===- MemorySSA.cpp - Memory SSA Builder ---------------------------------===//
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	// This file implements the MemorySSA class.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "llvm/Analysis/MemorySSA.h"
14	#include "llvm/ADT/DenseMap.h"
15	#include "llvm/ADT/DenseMapInfo.h"
16	#include "llvm/ADT/DenseSet.h"
17	#include "llvm/ADT/DepthFirstIterator.h"
18	#include "llvm/ADT/Hashing.h"
19	#include "llvm/ADT/STLExtras.h"
20	#include "llvm/ADT/SmallPtrSet.h"
21	#include "llvm/ADT/SmallVector.h"
22	#include "llvm/ADT/StringExtras.h"
23	#include "llvm/ADT/iterator.h"
24	#include "llvm/ADT/iterator_range.h"
25	#include "llvm/Analysis/AliasAnalysis.h"
26	#include "llvm/Analysis/CFGPrinter.h"
27	#include "llvm/Analysis/IteratedDominanceFrontier.h"
28	#include "llvm/Analysis/MemoryLocation.h"
29	#include "llvm/Config/llvm-config.h"
30	#include "llvm/IR/AssemblyAnnotationWriter.h"
31	#include "llvm/IR/BasicBlock.h"
32	#include "llvm/IR/Dominators.h"
33	#include "llvm/IR/Function.h"
34	#include "llvm/IR/Instruction.h"
35	#include "llvm/IR/Instructions.h"
36	#include "llvm/IR/IntrinsicInst.h"
37	#include "llvm/IR/LLVMContext.h"
38	#include "llvm/IR/Operator.h"
39	#include "llvm/IR/PassManager.h"
40	#include "llvm/IR/Use.h"
41	#include "llvm/InitializePasses.h"
42	#include "llvm/Pass.h"
43	#include "llvm/Support/AtomicOrdering.h"
44	#include "llvm/Support/Casting.h"
45	#include "llvm/Support/CommandLine.h"
46	#include "llvm/Support/Compiler.h"
47	#include "llvm/Support/Debug.h"
48	#include "llvm/Support/ErrorHandling.h"
49	#include "llvm/Support/FormattedStream.h"
50	#include "llvm/Support/GraphWriter.h"
51	#include "llvm/Support/raw_ostream.h"
52	#include <algorithm>
53	#include <cassert>
54	#include <iterator>
55	#include <memory>
56	#include <utility>
57
58	using namespace llvm;
59
60	#define DEBUG_TYPE "memoryssa"
61
62	static cl::opt<std::string>
63	DotCFGMSSA("dot-cfg-mssa",
64	cl::value_desc("file name for generated dot file"),
65	cl::desc("file name for generated dot file"), cl::init(Val: ""));
66
67	INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
68	true)
69	INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
70	INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
71	INITIALIZE_PASS_END(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
72	true)
73
74	static cl::opt<unsigned> MaxCheckLimit(
75	"memssa-check-limit", cl::Hidden, cl::init(Val: 100),
76	cl::desc("The maximum number of stores/phis MemorySSA"
77	"will consider trying to walk past (default = 100)"));
78
79	// Always verify MemorySSA if expensive checking is enabled.
80	#ifdef EXPENSIVE_CHECKS
81	bool llvm::VerifyMemorySSA = true;
82	#else
83	bool llvm::VerifyMemorySSA = false;
84	#endif
85
86	static cl::opt<bool, true>
87	VerifyMemorySSAX("verify-memoryssa", cl::location(L&: VerifyMemorySSA),
88	cl::Hidden, cl::desc("Enable verification of MemorySSA."));
89
90	const static char LiveOnEntryStr[] = "liveOnEntry";
91
92	namespace {
93
94	/// An assembly annotator class to print Memory SSA information in
95	/// comments.
96	class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter {
97	const MemorySSA *MSSA;
98
99	public:
100	MemorySSAAnnotatedWriter(const MemorySSA *M) : MSSA(M) {}
101
102	void emitBasicBlockStartAnnot(const BasicBlock *BB,
103	formatted_raw_ostream &OS) override {
104	if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
105	OS << "; " << *MA << "\n";
106	}
107
108	void emitInstructionAnnot(const Instruction *I,
109	formatted_raw_ostream &OS) override {
110	if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
111	OS << "; " << *MA << "\n";
112	}
113	};
114
115	/// An assembly annotator class to print Memory SSA information in
116	/// comments.
117	class MemorySSAWalkerAnnotatedWriter : public AssemblyAnnotationWriter {
118	MemorySSA *MSSA;
119	MemorySSAWalker *Walker;
120	BatchAAResults BAA;
121
122	public:
123	MemorySSAWalkerAnnotatedWriter(MemorySSA *M)
124	: MSSA(M), Walker(M->getWalker()), BAA(M->getAA()) {}
125
126	void emitBasicBlockStartAnnot(const BasicBlock *BB,
127	formatted_raw_ostream &OS) override {
128	if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
129	OS << "; " << *MA << "\n";
130	}
131
132	void emitInstructionAnnot(const Instruction *I,
133	formatted_raw_ostream &OS) override {
134	if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) {
135	MemoryAccess *Clobber = Walker->getClobberingMemoryAccess(MA, AA&: BAA);
136	OS << "; " << *MA;
137	if (Clobber) {
138	OS << " - clobbered by ";
139	if (MSSA->isLiveOnEntryDef(MA: Clobber))
140	OS << LiveOnEntryStr;
141	else
142	OS << *Clobber;
143	}
144	OS << "\n";
145	}
146	}
147	};
148
149	} // namespace
150
151	namespace {
152
153	/// Our current alias analysis API differentiates heavily between calls and
154	/// non-calls, and functions called on one usually assert on the other.
155	/// This class encapsulates the distinction to simplify other code that wants
156	/// "Memory affecting instructions and related data" to use as a key.
157	/// For example, this class is used as a densemap key in the use optimizer.
158	class MemoryLocOrCall {
159	public:
160	bool IsCall = false;
161
162	MemoryLocOrCall(MemoryUseOrDef *MUD)
163	: MemoryLocOrCall(MUD->getMemoryInst()) {}
164	MemoryLocOrCall(const MemoryUseOrDef *MUD)
165	: MemoryLocOrCall(MUD->getMemoryInst()) {}
166
167	MemoryLocOrCall(Instruction *Inst) {
168	if (auto *C = dyn_cast<CallBase>(Val: Inst)) {
169	IsCall = true;
170	Call = C;
171	} else {
172	IsCall = false;
173	// There is no such thing as a memorylocation for a fence inst, and it is
174	// unique in that regard.
175	if (!isa<FenceInst>(Val: Inst))
176	Loc = MemoryLocation::get(Inst);
177	}
178	}
179
180	explicit MemoryLocOrCall(const MemoryLocation &Loc) : Loc(Loc) {}
181
182	const CallBase *getCall() const {
183	assert(IsCall);
184	return Call;
185	}
186
187	MemoryLocation getLoc() const {
188	assert(!IsCall);
189	return Loc;
190	}
191
192	bool operator==(const MemoryLocOrCall &Other) const {
193	if (IsCall != Other.IsCall)
194	return false;
195
196	if (!IsCall)
197	return Loc == Other.Loc;
198
199	if (Call->getCalledOperand() != Other.Call->getCalledOperand())
200	return false;
201
202	return Call->arg_size() == Other.Call->arg_size() &&
203	std::equal(first1: Call->arg_begin(), last1: Call->arg_end(),
204	first2: Other.Call->arg_begin());
205	}
206
207	private:
208	union {
209	const CallBase *Call;
210	MemoryLocation Loc;
211	};
212	};
213
214	} // end anonymous namespace
215
216	namespace llvm {
217
218	template <> struct DenseMapInfo<MemoryLocOrCall> {
219	static inline MemoryLocOrCall getEmptyKey() {
220	return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getEmptyKey());
221	}
222
223	static inline MemoryLocOrCall getTombstoneKey() {
224	return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getTombstoneKey());
225	}
226
227	static unsigned getHashValue(const MemoryLocOrCall &MLOC) {
228	if (!MLOC.IsCall)
229	return hash_combine(
230	args: MLOC.IsCall,
231	args: DenseMapInfo<MemoryLocation>::getHashValue(Val: MLOC.getLoc()));
232
233	hash_code hash =
234	hash_combine(args: MLOC.IsCall, args: DenseMapInfo<const Value *>::getHashValue(
235	PtrVal: MLOC.getCall()->getCalledOperand()));
236
237	for (const Value *Arg : MLOC.getCall()->args())
238	hash = hash_combine(args: hash, args: DenseMapInfo<const Value *>::getHashValue(PtrVal: Arg));
239	return hash;
240	}
241
242	static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) {
243	return LHS == RHS;
244	}
245	};
246
247	} // end namespace llvm
248
249	/// This does one-way checks to see if Use could theoretically be hoisted above
250	/// MayClobber. This will not check the other way around.
251	///
252	/// This assumes that, for the purposes of MemorySSA, Use comes directly after
253	/// MayClobber, with no potentially clobbering operations in between them.
254	/// (Where potentially clobbering ops are memory barriers, aliased stores, etc.)
255	static bool areLoadsReorderable(const LoadInst *Use,
256	const LoadInst *MayClobber) {
257	bool VolatileUse = Use->isVolatile();
258	bool VolatileClobber = MayClobber->isVolatile();
259	// Volatile operations may never be reordered with other volatile operations.
260	if (VolatileUse && VolatileClobber)
261	return false;
262	// Otherwise, volatile doesn't matter here. From the language reference:
263	// 'optimizers may change the order of volatile operations relative to
264	// non-volatile operations.'"
265
266	// If a load is seq_cst, it cannot be moved above other loads. If its ordering
267	// is weaker, it can be moved above other loads. We just need to be sure that
268	// MayClobber isn't an acquire load, because loads can't be moved above
269	// acquire loads.
270	//
271	// Note that this explicitly *does* allow the free reordering of monotonic (or
272	// weaker) loads of the same address.
273	bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent;
274	bool MayClobberIsAcquire = isAtLeastOrStrongerThan(AO: MayClobber->getOrdering(),
275	Other: AtomicOrdering::Acquire);
276	return !(SeqCstUse || MayClobberIsAcquire);
277	}
278
279	template <typename AliasAnalysisType>
280	static bool
281	instructionClobbersQuery(const MemoryDef *MD, const MemoryLocation &UseLoc,
282	const Instruction *UseInst, AliasAnalysisType &AA) {
283	Instruction *DefInst = MD->getMemoryInst();
284	assert(DefInst && "Defining instruction not actually an instruction");
285
286	if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: DefInst)) {
287	// These intrinsics will show up as affecting memory, but they are just
288	// markers, mostly.
289	//
290	// FIXME: We probably don't actually want MemorySSA to model these at all
291	// (including creating MemoryAccesses for them): we just end up inventing
292	// clobbers where they don't really exist at all. Please see D43269 for
293	// context.
294	switch (II->getIntrinsicID()) {
295	case Intrinsic::allow_runtime_check:
296	case Intrinsic::allow_ubsan_check:
297	case Intrinsic::invariant_start:
298	case Intrinsic::invariant_end:
299	case Intrinsic::assume:
300	case Intrinsic::experimental_noalias_scope_decl:
301	case Intrinsic::pseudoprobe:
302	return false;
303	case Intrinsic::dbg_declare:
304	case Intrinsic::dbg_label:
305	case Intrinsic::dbg_value:
306	llvm_unreachable("debuginfo shouldn't have associated defs!");
307	default:
308	break;
309	}
310	}
311
312	if (auto *CB = dyn_cast_or_null<CallBase>(Val: UseInst)) {
313	ModRefInfo I = AA.getModRefInfo(DefInst, CB);
314	return isModOrRefSet(MRI: I);
315	}
316
317	if (auto *DefLoad = dyn_cast<LoadInst>(Val: DefInst))
318	if (auto *UseLoad = dyn_cast_or_null<LoadInst>(Val: UseInst))
319	return !areLoadsReorderable(Use: UseLoad, MayClobber: DefLoad);
320
321	ModRefInfo I = AA.getModRefInfo(DefInst, UseLoc);
322	return isModSet(MRI: I);
323	}
324
325	template <typename AliasAnalysisType>
326	static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU,
327	const MemoryLocOrCall &UseMLOC,
328	AliasAnalysisType &AA) {
329	// FIXME: This is a temporary hack to allow a single instructionClobbersQuery
330	// to exist while MemoryLocOrCall is pushed through places.
331	if (UseMLOC.IsCall)
332	return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(),
333	AA);
334	return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(),
335	AA);
336	}
337
338	// Return true when MD may alias MU, return false otherwise.
339	bool MemorySSAUtil::defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
340	AliasAnalysis &AA) {
341	return instructionClobbersQuery(MD, MU, UseMLOC: MemoryLocOrCall(MU), AA);
342	}
343
344	namespace {
345
346	struct UpwardsMemoryQuery {
347	// True if our original query started off as a call
348	bool IsCall = false;
349	// The pointer location we started the query with. This will be empty if
350	// IsCall is true.
351	MemoryLocation StartingLoc;
352	// This is the instruction we were querying about.
353	const Instruction *Inst = nullptr;
354	// The MemoryAccess we actually got called with, used to test local domination
355	const MemoryAccess *OriginalAccess = nullptr;
356	bool SkipSelfAccess = false;
357
358	UpwardsMemoryQuery() = default;
359
360	UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
361	: IsCall(isa<CallBase>(Val: Inst)), Inst(Inst), OriginalAccess(Access) {
362	if (!IsCall)
363	StartingLoc = MemoryLocation::get(Inst);
364	}
365	};
366
367	} // end anonymous namespace
368
369	template <typename AliasAnalysisType>
370	static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysisType &AA,
371	const Instruction *I) {
372	// If the memory can't be changed, then loads of the memory can't be
373	// clobbered.
374	if (auto *LI = dyn_cast<LoadInst>(Val: I)) {
375	return I->hasMetadata(KindID: LLVMContext::MD_invariant_load) ||
376	!isModSet(AA.getModRefInfoMask(MemoryLocation::get(LI)));
377	}
378	return false;
379	}
380
381	/// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing
382	/// inbetween `Start` and `ClobberAt` can clobbers `Start`.
383	///
384	/// This is meant to be as simple and self-contained as possible. Because it
385	/// uses no cache, etc., it can be relatively expensive.
386	///
387	/// \param Start The MemoryAccess that we want to walk from.
388	/// \param ClobberAt A clobber for Start.
389	/// \param StartLoc The MemoryLocation for Start.
390	/// \param MSSA The MemorySSA instance that Start and ClobberAt belong to.
391	/// \param Query The UpwardsMemoryQuery we used for our search.
392	/// \param AA The AliasAnalysis we used for our search.
393	/// \param AllowImpreciseClobber Always false, unless we do relaxed verify.
394
395	LLVM_ATTRIBUTE_UNUSED static void
396	checkClobberSanity(const MemoryAccess *Start, MemoryAccess *ClobberAt,
397	const MemoryLocation &StartLoc, const MemorySSA &MSSA,
398	const UpwardsMemoryQuery &Query, BatchAAResults &AA,
399	bool AllowImpreciseClobber = false) {
400	assert(MSSA.dominates(ClobberAt, Start) && "Clobber doesn't dominate start?");
401
402	if (MSSA.isLiveOnEntryDef(MA: Start)) {
403	assert(MSSA.isLiveOnEntryDef(ClobberAt) &&
404	"liveOnEntry must clobber itself");
405	return;
406	}
407
408	bool FoundClobber = false;
409	DenseSet<ConstMemoryAccessPair> VisitedPhis;
410	SmallVector<ConstMemoryAccessPair, 8> Worklist;
411	Worklist.emplace_back(Args&: Start, Args: StartLoc);
412	// Walk all paths from Start to ClobberAt, while looking for clobbers. If one
413	// is found, complain.
414	while (!Worklist.empty()) {
415	auto MAP = Worklist.pop_back_val();
416	// All we care about is that nothing from Start to ClobberAt clobbers Start.
417	// We learn nothing from revisiting nodes.
418	if (!VisitedPhis.insert(V: MAP).second)
419	continue;
420
421	for (const auto *MA : def_chain(MA: MAP.first)) {
422	if (MA == ClobberAt) {
423	if (const auto *MD = dyn_cast<MemoryDef>(Val: MA)) {
424	// instructionClobbersQuery isn't essentially free, so don't use `|=`,
425	// since it won't let us short-circuit.
426	//
427	// Also, note that this can't be hoisted out of the `Worklist` loop,
428	// since MD may only act as a clobber for 1 of N MemoryLocations.
429	FoundClobber = FoundClobber || MSSA.isLiveOnEntryDef(MA: MD);
430	if (!FoundClobber) {
431	if (instructionClobbersQuery(MD, UseLoc: MAP.second, UseInst: Query.Inst, AA))
432	FoundClobber = true;
433	}
434	}
435	break;
436	}
437
438	// We should never hit liveOnEntry, unless it's the clobber.
439	assert(!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?");
440
441	if (const auto *MD = dyn_cast<MemoryDef>(Val: MA)) {
442	// If Start is a Def, skip self.
443	if (MD == Start)
444	continue;
445
446	assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) &&
447	"Found clobber before reaching ClobberAt!");
448	continue;
449	}
450
451	if (const auto *MU = dyn_cast<MemoryUse>(Val: MA)) {
452	(void)MU;
453	assert (MU == Start &&
454	"Can only find use in def chain if Start is a use");
455	continue;
456	}
457
458	assert(isa<MemoryPhi>(MA));
459
460	// Add reachable phi predecessors
461	for (auto ItB = upward_defs_begin(
462	Pair: {const_cast<MemoryAccess *>(MA), MAP.second},
463	DT&: MSSA.getDomTree()),
464	ItE = upward_defs_end();
465	ItB != ItE; ++ItB)
466	if (MSSA.getDomTree().isReachableFromEntry(A: ItB.getPhiArgBlock()))
467	Worklist.emplace_back(Args: *ItB);
468	}
469	}
470
471	// If the verify is done following an optimization, it's possible that
472	// ClobberAt was a conservative clobbering, that we can now infer is not a
473	// true clobbering access. Don't fail the verify if that's the case.
474	// We do have accesses that claim they're optimized, but could be optimized
475	// further. Updating all these can be expensive, so allow it for now (FIXME).
476	if (AllowImpreciseClobber)
477	return;
478
479	// If ClobberAt is a MemoryPhi, we can assume something above it acted as a
480	// clobber. Otherwise, `ClobberAt` should've acted as a clobber at some point.
481	assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) &&
482	"ClobberAt never acted as a clobber");
483	}
484
485	namespace {
486
487	/// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up
488	/// in one class.
489	class ClobberWalker {
490	/// Save a few bytes by using unsigned instead of size_t.
491	using ListIndex = unsigned;
492
493	/// Represents a span of contiguous MemoryDefs, potentially ending in a
494	/// MemoryPhi.
495	struct DefPath {
496	MemoryLocation Loc;
497	// Note that, because we always walk in reverse, Last will always dominate
498	// First. Also note that First and Last are inclusive.
499	MemoryAccess *First;
500	MemoryAccess *Last;
501	std::optional<ListIndex> Previous;
502
503	DefPath(const MemoryLocation &Loc, MemoryAccess *First, MemoryAccess *Last,
504	std::optional<ListIndex> Previous)
505	: Loc(Loc), First(First), Last(Last), Previous(Previous) {}
506
507	DefPath(const MemoryLocation &Loc, MemoryAccess *Init,
508	std::optional<ListIndex> Previous)
509	: DefPath(Loc, Init, Init, Previous) {}
510	};
511
512	const MemorySSA &MSSA;
513	DominatorTree &DT;
514	BatchAAResults *AA;
515	UpwardsMemoryQuery *Query;
516	unsigned *UpwardWalkLimit;
517
518	// Phi optimization bookkeeping:
519	// List of DefPath to process during the current phi optimization walk.
520	SmallVector<DefPath, 32> Paths;
521	// List of visited <Access, Location> pairs; we can skip paths already
522	// visited with the same memory location.
523	DenseSet<ConstMemoryAccessPair> VisitedPhis;
524
525	/// Find the nearest def or phi that `From` can legally be optimized to.
526	const MemoryAccess *getWalkTarget(const MemoryPhi *From) const {
527	assert(From->getNumOperands() && "Phi with no operands?");
528
529	BasicBlock *BB = From->getBlock();
530	MemoryAccess *Result = MSSA.getLiveOnEntryDef();
531	DomTreeNode *Node = DT.getNode(BB);
532	while ((Node = Node->getIDom())) {
533	auto *Defs = MSSA.getBlockDefs(BB: Node->getBlock());
534	if (Defs)
535	return &*Defs->rbegin();
536	}
537	return Result;
538	}
539
540	/// Result of calling walkToPhiOrClobber.
541	struct UpwardsWalkResult {
542	/// The "Result" of the walk. Either a clobber, the last thing we walked, or
543	/// both. Include alias info when clobber found.
544	MemoryAccess *Result;
545	bool IsKnownClobber;
546	};
547
548	/// Walk to the next Phi or Clobber in the def chain starting at Desc.Last.
549	/// This will update Desc.Last as it walks. It will (optionally) also stop at
550	/// StopAt.
551	///
552	/// This does not test for whether StopAt is a clobber
553	UpwardsWalkResult
554	walkToPhiOrClobber(DefPath &Desc, const MemoryAccess *StopAt = nullptr,
555	const MemoryAccess *SkipStopAt = nullptr) const {
556	assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
557	assert(UpwardWalkLimit && "Need a valid walk limit");
558	bool LimitAlreadyReached = false;
559	// (*UpwardWalkLimit) may be 0 here, due to the loop in tryOptimizePhi. Set
560	// it to 1. This will not do any alias() calls. It either returns in the
561	// first iteration in the loop below, or is set back to 0 if all def chains
562	// are free of MemoryDefs.
563	if (!*UpwardWalkLimit) {
564	*UpwardWalkLimit = 1;
565	LimitAlreadyReached = true;
566	}
567
568	for (MemoryAccess *Current : def_chain(MA: Desc.Last)) {
569	Desc.Last = Current;
570	if (Current == StopAt || Current == SkipStopAt)
571	return {.Result: Current, .IsKnownClobber: false};
572
573	if (auto *MD = dyn_cast<MemoryDef>(Val: Current)) {
574	if (MSSA.isLiveOnEntryDef(MA: MD))
575	return {.Result: MD, .IsKnownClobber: true};
576
577	if (!--*UpwardWalkLimit)
578	return {.Result: Current, .IsKnownClobber: true};
579
580	if (instructionClobbersQuery(MD, UseLoc: Desc.Loc, UseInst: Query->Inst, AA&: *AA))
581	return {.Result: MD, .IsKnownClobber: true};
582	}
583	}
584
585	if (LimitAlreadyReached)
586	*UpwardWalkLimit = 0;
587
588	assert(isa<MemoryPhi>(Desc.Last) &&
589	"Ended at a non-clobber that's not a phi?");
590	return {.Result: Desc.Last, .IsKnownClobber: false};
591	}
592
593	void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
594	ListIndex PriorNode) {
595	auto UpwardDefsBegin = upward_defs_begin(Pair: {Phi, Paths[PriorNode].Loc}, DT);
596	auto UpwardDefs = make_range(x: UpwardDefsBegin, y: upward_defs_end());
597	for (const MemoryAccessPair &P : UpwardDefs) {
598	PausedSearches.push_back(Elt: Paths.size());
599	Paths.emplace_back(Args: P.second, Args: P.first, Args&: PriorNode);
600	}
601	}
602
603	/// Represents a search that terminated after finding a clobber. This clobber
604	/// may or may not be present in the path of defs from LastNode..SearchStart,
605	/// since it may have been retrieved from cache.
606	struct TerminatedPath {
607	MemoryAccess *Clobber;
608	ListIndex LastNode;
609	};
610
611	/// Get an access that keeps us from optimizing to the given phi.
612	///
613	/// PausedSearches is an array of indices into the Paths array. Its incoming
614	/// value is the indices of searches that stopped at the last phi optimization
615	/// target. It's left in an unspecified state.
616	///
617	/// If this returns std::nullopt, NewPaused is a vector of searches that
618	/// terminated at StopWhere. Otherwise, NewPaused is left in an unspecified
619	/// state.
620	std::optional<TerminatedPath>
621	getBlockingAccess(const MemoryAccess *StopWhere,
622	SmallVectorImpl<ListIndex> &PausedSearches,
623	SmallVectorImpl<ListIndex> &NewPaused,
624	SmallVectorImpl<TerminatedPath> &Terminated) {
625	assert(!PausedSearches.empty() && "No searches to continue?");
626
627	// BFS vs DFS really doesn't make a difference here, so just do a DFS with
628	// PausedSearches as our stack.
629	while (!PausedSearches.empty()) {
630	ListIndex PathIndex = PausedSearches.pop_back_val();
631	DefPath &Node = Paths[PathIndex];
632
633	// If we've already visited this path with this MemoryLocation, we don't
634	// need to do so again.
635	//
636	// NOTE: That we just drop these paths on the ground makes caching
637	// behavior sporadic. e.g. given a diamond:
638	// A
639	// B C
640	// D
641	//
642	// ...If we walk D, B, A, C, we'll only cache the result of phi
643	// optimization for A, B, and D; C will be skipped because it dies here.
644	// This arguably isn't the worst thing ever, since:
645	// - We generally query things in a top-down order, so if we got below D
646	// without needing cache entries for {C, MemLoc}, then chances are
647	// that those cache entries would end up ultimately unused.
648	// - We still cache things for A, so C only needs to walk up a bit.
649	// If this behavior becomes problematic, we can fix without a ton of extra
650	// work.
651	if (!VisitedPhis.insert(V: {Node.Last, Node.Loc}).second)
652	continue;
653
654	const MemoryAccess *SkipStopWhere = nullptr;
655	if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
656	assert(isa<MemoryDef>(Query->OriginalAccess));
657	SkipStopWhere = Query->OriginalAccess;
658	}
659
660	UpwardsWalkResult Res = walkToPhiOrClobber(Desc&: Node,
661	/*StopAt=*/StopWhere,
662	/*SkipStopAt=*/SkipStopWhere);
663	if (Res.IsKnownClobber) {
664	assert(Res.Result != StopWhere && Res.Result != SkipStopWhere);
665
666	// If this wasn't a cache hit, we hit a clobber when walking. That's a
667	// failure.
668	TerminatedPath Term{.Clobber: Res.Result, .LastNode: PathIndex};
669	if (!MSSA.dominates(A: Res.Result, B: StopWhere))
670	return Term;
671
672	// Otherwise, it's a valid thing to potentially optimize to.
673	Terminated.push_back(Elt: Term);
674	continue;
675	}
676
677	if (Res.Result == StopWhere || Res.Result == SkipStopWhere) {
678	// We've hit our target. Save this path off for if we want to continue
679	// walking. If we are in the mode of skipping the OriginalAccess, and
680	// we've reached back to the OriginalAccess, do not save path, we've
681	// just looped back to self.
682	if (Res.Result != SkipStopWhere)
683	NewPaused.push_back(Elt: PathIndex);
684	continue;
685	}
686
687	assert(!MSSA.isLiveOnEntryDef(Res.Result) && "liveOnEntry is a clobber");
688	addSearches(Phi: cast<MemoryPhi>(Val: Res.Result), PausedSearches, PriorNode: PathIndex);
689	}
690
691	return std::nullopt;
692	}
693
694	template <typename T, typename Walker>
695	struct generic_def_path_iterator
696	: public iterator_facade_base<generic_def_path_iterator<T, Walker>,
697	std::forward_iterator_tag, T *> {
698	generic_def_path_iterator() = default;
699	generic_def_path_iterator(Walker *W, ListIndex N) : W(W), N(N) {}
700
701	T &operator*() const { return curNode(); }
702
703	generic_def_path_iterator &operator++() {
704	N = curNode().Previous;
705	return *this;
706	}
707
708	bool operator==(const generic_def_path_iterator &O) const {
709	if (N.has_value() != O.N.has_value())
710	return false;
711	return !N || *N == *O.N;
712	}
713
714	private:
715	T &curNode() const { return W->Paths[*N]; }
716
717	Walker *W = nullptr;
718	std::optional<ListIndex> N;
719	};
720
721	using def_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>;
722	using const_def_path_iterator =
723	generic_def_path_iterator<const DefPath, const ClobberWalker>;
724
725	iterator_range<def_path_iterator> def_path(ListIndex From) {
726	return make_range(x: def_path_iterator(this, From), y: def_path_iterator());
727	}
728
729	iterator_range<const_def_path_iterator> const_def_path(ListIndex From) const {
730	return make_range(x: const_def_path_iterator(this, From),
731	y: const_def_path_iterator());
732	}
733
734	struct OptznResult {
735	/// The path that contains our result.
736	TerminatedPath PrimaryClobber;
737	/// The paths that we can legally cache back from, but that aren't
738	/// necessarily the result of the Phi optimization.
739	SmallVector<TerminatedPath, 4> OtherClobbers;
740	};
741
742	ListIndex defPathIndex(const DefPath &N) const {
743	// The assert looks nicer if we don't need to do &N
744	const DefPath *NP = &N;
745	assert(!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() &&
746	"Out of bounds DefPath!");
747	return NP - &Paths.front();
748	}
749
750	/// Try to optimize a phi as best as we can. Returns a SmallVector of Paths
751	/// that act as legal clobbers. Note that this won't return *all* clobbers.
752	///
753	/// Phi optimization algorithm tl;dr:
754	/// - Find the earliest def/phi, A, we can optimize to
755	/// - Find if all paths from the starting memory access ultimately reach A
756	/// - If not, optimization isn't possible.
757	/// - Otherwise, walk from A to another clobber or phi, A'.
758	/// - If A' is a def, we're done.
759	/// - If A' is a phi, try to optimize it.
760	///
761	/// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path
762	/// terminates when a MemoryAccess that clobbers said MemoryLocation is found.
763	OptznResult tryOptimizePhi(MemoryPhi *Phi, MemoryAccess *Start,
764	const MemoryLocation &Loc) {
765	assert(Paths.empty() && VisitedPhis.empty() &&
766	"Reset the optimization state.");
767
768	Paths.emplace_back(Args: Loc, Args&: Start, Args&: Phi, Args: std::nullopt);
769	// Stores how many "valid" optimization nodes we had prior to calling
770	// addSearches/getBlockingAccess. Necessary for caching if we had a blocker.
771	auto PriorPathsSize = Paths.size();
772
773	SmallVector<ListIndex, 16> PausedSearches;
774	SmallVector<ListIndex, 8> NewPaused;
775	SmallVector<TerminatedPath, 4> TerminatedPaths;
776
777	addSearches(Phi, PausedSearches, PriorNode: 0);
778
779	// Moves the TerminatedPath with the "most dominated" Clobber to the end of
780	// Paths.
781	auto MoveDominatedPathToEnd = [&](SmallVectorImpl<TerminatedPath> &Paths) {
782	assert(!Paths.empty() && "Need a path to move");
783	auto Dom = Paths.begin();
784	for (auto I = std::next(x: Dom), E = Paths.end(); I != E; ++I)
785	if (!MSSA.dominates(A: I->Clobber, B: Dom->Clobber))
786	Dom = I;
787	auto Last = Paths.end() - 1;
788	if (Last != Dom)
789	std::iter_swap(a: Last, b: Dom);
790	};
791
792	MemoryPhi *Current = Phi;
793	while (true) {
794	assert(!MSSA.isLiveOnEntryDef(Current) &&
795	"liveOnEntry wasn't treated as a clobber?");
796
797	const auto *Target = getWalkTarget(From: Current);
798	// If a TerminatedPath doesn't dominate Target, then it wasn't a legal
799	// optimization for the prior phi.
800	assert(all_of(TerminatedPaths, [&](const TerminatedPath &P) {
801	return MSSA.dominates(P.Clobber, Target);
802	}));
803
804	// FIXME: This is broken, because the Blocker may be reported to be
805	// liveOnEntry, and we'll happily wait for that to disappear (read: never)
806	// For the moment, this is fine, since we do nothing with blocker info.
807	if (std::optional<TerminatedPath> Blocker = getBlockingAccess(
808	StopWhere: Target, PausedSearches, NewPaused, Terminated&: TerminatedPaths)) {
809
810	// Find the node we started at. We can't search based on N->Last, since
811	// we may have gone around a loop with a different MemoryLocation.
812	auto Iter = find_if(Range: def_path(From: Blocker->LastNode), P: [&](const DefPath &N) {
813	return defPathIndex(N) < PriorPathsSize;
814	});
815	assert(Iter != def_path_iterator());
816
817	DefPath &CurNode = *Iter;
818	assert(CurNode.Last == Current);
819
820	// Two things:
821	// A. We can't reliably cache all of NewPaused back. Consider a case
822	// where we have two paths in NewPaused; one of which can't optimize
823	// above this phi, whereas the other can. If we cache the second path
824	// back, we'll end up with suboptimal cache entries. We can handle
825	// cases like this a bit better when we either try to find all
826	// clobbers that block phi optimization, or when our cache starts
827	// supporting unfinished searches.
828	// B. We can't reliably cache TerminatedPaths back here without doing
829	// extra checks; consider a case like:
830	// T
831	// / \
832	// D C
833	// \ /
834	// S
835	// Where T is our target, C is a node with a clobber on it, D is a
836	// diamond (with a clobber *only* on the left or right node, N), and
837	// S is our start. Say we walk to D, through the node opposite N
838	// (read: ignoring the clobber), and see a cache entry in the top
839	// node of D. That cache entry gets put into TerminatedPaths. We then
840	// walk up to C (N is later in our worklist), find the clobber, and
841	// quit. If we append TerminatedPaths to OtherClobbers, we'll cache
842	// the bottom part of D to the cached clobber, ignoring the clobber
843	// in N. Again, this problem goes away if we start tracking all
844	// blockers for a given phi optimization.
845	TerminatedPath Result{.Clobber: CurNode.Last, .LastNode: defPathIndex(N: CurNode)};
846	return {.PrimaryClobber: Result, .OtherClobbers: {}};
847	}
848
849	// If there's nothing left to search, then all paths led to valid clobbers
850	// that we got from our cache; pick the nearest to the start, and allow
851	// the rest to be cached back.
852	if (NewPaused.empty()) {
853	MoveDominatedPathToEnd(TerminatedPaths);
854	TerminatedPath Result = TerminatedPaths.pop_back_val();
855	return {.PrimaryClobber: Result, .OtherClobbers: std::move(TerminatedPaths)};
856	}
857
858	MemoryAccess *DefChainEnd = nullptr;
859	SmallVector<TerminatedPath, 4> Clobbers;
860	for (ListIndex Paused : NewPaused) {
861	UpwardsWalkResult WR = walkToPhiOrClobber(Desc&: Paths[Paused]);
862	if (WR.IsKnownClobber)
863	Clobbers.push_back(Elt: {.Clobber: WR.Result, .LastNode: Paused});
864	else
865	// Micro-opt: If we hit the end of the chain, save it.
866	DefChainEnd = WR.Result;
867	}
868
869	if (!TerminatedPaths.empty()) {
870	// If we couldn't find the dominating phi/liveOnEntry in the above loop,
871	// do it now.
872	if (!DefChainEnd)
873	for (auto *MA : def_chain(MA: const_cast<MemoryAccess *>(Target)))
874	DefChainEnd = MA;
875	assert(DefChainEnd && "Failed to find dominating phi/liveOnEntry");
876
877	// If any of the terminated paths don't dominate the phi we'll try to
878	// optimize, we need to figure out what they are and quit.
879	const BasicBlock *ChainBB = DefChainEnd->getBlock();
880	for (const TerminatedPath &TP : TerminatedPaths) {
881	// Because we know that DefChainEnd is as "high" as we can go, we
882	// don't need local dominance checks; BB dominance is sufficient.
883	if (DT.dominates(A: ChainBB, B: TP.Clobber->getBlock()))
884	Clobbers.push_back(Elt: TP);
885	}
886	}
887
888	// If we have clobbers in the def chain, find the one closest to Current
889	// and quit.
890	if (!Clobbers.empty()) {
891	MoveDominatedPathToEnd(Clobbers);
892	TerminatedPath Result = Clobbers.pop_back_val();
893	return {.PrimaryClobber: Result, .OtherClobbers: std::move(Clobbers)};
894	}
895
896	assert(all_of(NewPaused,
897	[&](ListIndex I) { return Paths[I].Last == DefChainEnd; }));
898
899	// Because liveOnEntry is a clobber, this must be a phi.
900	auto *DefChainPhi = cast<MemoryPhi>(Val: DefChainEnd);
901
902	PriorPathsSize = Paths.size();
903	PausedSearches.clear();
904	for (ListIndex I : NewPaused)
905	addSearches(Phi: DefChainPhi, PausedSearches, PriorNode: I);
906	NewPaused.clear();
907
908	Current = DefChainPhi;
909	}
910	}
911
912	void verifyOptResult(const OptznResult &R) const {
913	assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) {
914	return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);
915	}));
916	}
917
918	void resetPhiOptznState() {
919	Paths.clear();
920	VisitedPhis.clear();
921	}
922
923	public:
924	ClobberWalker(const MemorySSA &MSSA, DominatorTree &DT)
925	: MSSA(MSSA), DT(DT) {}
926
927	/// Finds the nearest clobber for the given query, optimizing phis if
928	/// possible.
929	MemoryAccess *findClobber(BatchAAResults &BAA, MemoryAccess *Start,
930	UpwardsMemoryQuery &Q, unsigned &UpWalkLimit) {
931	AA = &BAA;
932	Query = &Q;
933	UpwardWalkLimit = &UpWalkLimit;
934	// Starting limit must be > 0.
935	if (!UpWalkLimit)
936	UpWalkLimit++;
937
938	MemoryAccess *Current = Start;
939	// This walker pretends uses don't exist. If we're handed one, silently grab
940	// its def. (This has the nice side-effect of ensuring we never cache uses)
941	if (auto *MU = dyn_cast<MemoryUse>(Val: Start))
942	Current = MU->getDefiningAccess();
943
944	DefPath FirstDesc(Q.StartingLoc, Current, Current, std::nullopt);
945	// Fast path for the overly-common case (no crazy phi optimization
946	// necessary)
947	UpwardsWalkResult WalkResult = walkToPhiOrClobber(Desc&: FirstDesc);
948	MemoryAccess *Result;
949	if (WalkResult.IsKnownClobber) {
950	Result = WalkResult.Result;
951	} else {
952	OptznResult OptRes = tryOptimizePhi(Phi: cast<MemoryPhi>(Val: FirstDesc.Last),
953	Start: Current, Loc: Q.StartingLoc);
954	verifyOptResult(R: OptRes);
955	resetPhiOptznState();
956	Result = OptRes.PrimaryClobber.Clobber;
957	}
958
959	#ifdef EXPENSIVE_CHECKS
960	if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0)
961	checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, BAA);
962	#endif
963	return Result;
964	}
965	};
966
967	struct RenamePassData {
968	DomTreeNode *DTN;
969	DomTreeNode::const_iterator ChildIt;
970	MemoryAccess *IncomingVal;
971
972	RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It,
973	MemoryAccess *M)
974	: DTN(D), ChildIt(It), IncomingVal(M) {}
975
976	void swap(RenamePassData &RHS) {
977	std::swap(a&: DTN, b&: RHS.DTN);
978	std::swap(a&: ChildIt, b&: RHS.ChildIt);
979	std::swap(a&: IncomingVal, b&: RHS.IncomingVal);
980	}
981	};
982
983	} // end anonymous namespace
984
985	namespace llvm {
986
987	class MemorySSA::ClobberWalkerBase {
988	ClobberWalker Walker;
989	MemorySSA *MSSA;
990
991	public:
992	ClobberWalkerBase(MemorySSA *M, DominatorTree *D) : Walker(*M, *D), MSSA(M) {}
993
994	MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *,
995	const MemoryLocation &,
996	BatchAAResults &, unsigned &);
997	// Third argument (bool), defines whether the clobber search should skip the
998	// original queried access. If true, there will be a follow-up query searching
999	// for a clobber access past "self". Note that the Optimized access is not
1000	// updated if a new clobber is found by this SkipSelf search. If this
1001	// additional query becomes heavily used we may decide to cache the result.
1002	// Walker instantiations will decide how to set the SkipSelf bool.
1003	MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, BatchAAResults &,
1004	unsigned &, bool,
1005	bool UseInvariantGroup = true);
1006	};
1007
1008	/// A MemorySSAWalker that does AA walks to disambiguate accesses. It no
1009	/// longer does caching on its own, but the name has been retained for the
1010	/// moment.
1011	class MemorySSA::CachingWalker final : public MemorySSAWalker {
1012	ClobberWalkerBase *Walker;
1013
1014	public:
1015	CachingWalker(MemorySSA *M, ClobberWalkerBase *W)
1016	: MemorySSAWalker(M), Walker(W) {}
1017	~CachingWalker() override = default;
1018
1019	using MemorySSAWalker::getClobberingMemoryAccess;
1020
1021	MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, BatchAAResults &BAA,
1022	unsigned &UWL) {
1023	return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, false);
1024	}
1025	MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1026	const MemoryLocation &Loc,
1027	BatchAAResults &BAA, unsigned &UWL) {
1028	return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1029	}
1030	// This method is not accessible outside of this file.
1031	MemoryAccess *getClobberingMemoryAccessWithoutInvariantGroup(
1032	MemoryAccess *MA, BatchAAResults &BAA, unsigned &UWL) {
1033	return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, false, UseInvariantGroup: false);
1034	}
1035
1036	MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1037	BatchAAResults &BAA) override {
1038	unsigned UpwardWalkLimit = MaxCheckLimit;
1039	return getClobberingMemoryAccess(MA, BAA, UWL&: UpwardWalkLimit);
1040	}
1041	MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1042	const MemoryLocation &Loc,
1043	BatchAAResults &BAA) override {
1044	unsigned UpwardWalkLimit = MaxCheckLimit;
1045	return getClobberingMemoryAccess(MA, Loc, BAA, UWL&: UpwardWalkLimit);
1046	}
1047
1048	void invalidateInfo(MemoryAccess *MA) override {
1049	if (auto *MUD = dyn_cast<MemoryUseOrDef>(Val: MA))
1050	MUD->resetOptimized();
1051	}
1052	};
1053
1054	class MemorySSA::SkipSelfWalker final : public MemorySSAWalker {
1055	ClobberWalkerBase *Walker;
1056
1057	public:
1058	SkipSelfWalker(MemorySSA *M, ClobberWalkerBase *W)
1059	: MemorySSAWalker(M), Walker(W) {}
1060	~SkipSelfWalker() override = default;
1061
1062	using MemorySSAWalker::getClobberingMemoryAccess;
1063
1064	MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, BatchAAResults &BAA,
1065	unsigned &UWL) {
1066	return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, true);
1067	}
1068	MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1069	const MemoryLocation &Loc,
1070	BatchAAResults &BAA, unsigned &UWL) {
1071	return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1072	}
1073
1074	MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1075	BatchAAResults &BAA) override {
1076	unsigned UpwardWalkLimit = MaxCheckLimit;
1077	return getClobberingMemoryAccess(MA, BAA, UWL&: UpwardWalkLimit);
1078	}
1079	MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1080	const MemoryLocation &Loc,
1081	BatchAAResults &BAA) override {
1082	unsigned UpwardWalkLimit = MaxCheckLimit;
1083	return getClobberingMemoryAccess(MA, Loc, BAA, UWL&: UpwardWalkLimit);
1084	}
1085
1086	void invalidateInfo(MemoryAccess *MA) override {
1087	if (auto *MUD = dyn_cast<MemoryUseOrDef>(Val: MA))
1088	MUD->resetOptimized();
1089	}
1090	};
1091
1092	} // end namespace llvm
1093
1094	void MemorySSA::renameSuccessorPhis(BasicBlock *BB, MemoryAccess *IncomingVal,
1095	bool RenameAllUses) {
1096	// Pass through values to our successors
1097	for (const BasicBlock *S : successors(BB)) {
1098	auto It = PerBlockAccesses.find(Val: S);
1099	// Rename the phi nodes in our successor block
1100	if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(Val: It->second->front()))
1101	continue;
1102	AccessList *Accesses = It->second.get();
1103	auto *Phi = cast<MemoryPhi>(Val: &Accesses->front());
1104	if (RenameAllUses) {
1105	bool ReplacementDone = false;
1106	for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I)
1107	if (Phi->getIncomingBlock(I) == BB) {
1108	Phi->setIncomingValue(I, V: IncomingVal);
1109	ReplacementDone = true;
1110	}
1111	(void) ReplacementDone;
1112	assert(ReplacementDone && "Incomplete phi during partial rename");
1113	} else
1114	Phi->addIncoming(V: IncomingVal, BB);
1115	}
1116	}
1117
1118	/// Rename a single basic block into MemorySSA form.
1119	/// Uses the standard SSA renaming algorithm.
1120	/// \returns The new incoming value.
1121	MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB, MemoryAccess *IncomingVal,
1122	bool RenameAllUses) {
1123	auto It = PerBlockAccesses.find(Val: BB);
1124	// Skip most processing if the list is empty.
1125	if (It != PerBlockAccesses.end()) {
1126	AccessList *Accesses = It->second.get();
1127	for (MemoryAccess &L : *Accesses) {
1128	if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(Val: &L)) {
1129	if (MUD->getDefiningAccess() == nullptr || RenameAllUses)
1130	MUD->setDefiningAccess(DMA: IncomingVal);
1131	if (isa<MemoryDef>(Val: &L))
1132	IncomingVal = &L;
1133	} else {
1134	IncomingVal = &L;
1135	}
1136	}
1137	}
1138	return IncomingVal;
1139	}
1140
1141	/// This is the standard SSA renaming algorithm.
1142	///
1143	/// We walk the dominator tree in preorder, renaming accesses, and then filling
1144	/// in phi nodes in our successors.
1145	void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal,
1146	SmallPtrSetImpl<BasicBlock *> &Visited,
1147	bool SkipVisited, bool RenameAllUses) {
1148	assert(Root && "Trying to rename accesses in an unreachable block");
1149
1150	SmallVector<RenamePassData, 32> WorkStack;
1151	// Skip everything if we already renamed this block and we are skipping.
1152	// Note: You can't sink this into the if, because we need it to occur
1153	// regardless of whether we skip blocks or not.
1154	bool AlreadyVisited = !Visited.insert(Ptr: Root->getBlock()).second;
1155	if (SkipVisited && AlreadyVisited)
1156	return;
1157
1158	IncomingVal = renameBlock(BB: Root->getBlock(), IncomingVal, RenameAllUses);
1159	renameSuccessorPhis(BB: Root->getBlock(), IncomingVal, RenameAllUses);
1160	WorkStack.push_back(Elt: {Root, Root->begin(), IncomingVal});
1161
1162	while (!WorkStack.empty()) {
1163	DomTreeNode *Node = WorkStack.back().DTN;
1164	DomTreeNode::const_iterator ChildIt = WorkStack.back().ChildIt;
1165	IncomingVal = WorkStack.back().IncomingVal;
1166
1167	if (ChildIt == Node->end()) {
1168	WorkStack.pop_back();
1169	} else {
1170	DomTreeNode *Child = *ChildIt;
1171	++WorkStack.back().ChildIt;
1172	BasicBlock *BB = Child->getBlock();
1173	// Note: You can't sink this into the if, because we need it to occur
1174	// regardless of whether we skip blocks or not.
1175	AlreadyVisited = !Visited.insert(Ptr: BB).second;
1176	if (SkipVisited && AlreadyVisited) {
1177	// We already visited this during our renaming, which can happen when
1178	// being asked to rename multiple blocks. Figure out the incoming val,
1179	// which is the last def.
1180	// Incoming value can only change if there is a block def, and in that
1181	// case, it's the last block def in the list.
1182	if (auto *BlockDefs = getWritableBlockDefs(BB))
1183	IncomingVal = &*BlockDefs->rbegin();
1184	} else
1185	IncomingVal = renameBlock(BB, IncomingVal, RenameAllUses);
1186	renameSuccessorPhis(BB, IncomingVal, RenameAllUses);
1187	WorkStack.push_back(Elt: {Child, Child->begin(), IncomingVal});
1188	}
1189	}
1190	}
1191
1192	/// This handles unreachable block accesses by deleting phi nodes in
1193	/// unreachable blocks, and marking all other unreachable MemoryAccess's as
1194	/// being uses of the live on entry definition.
1195	void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) {
1196	assert(!DT->isReachableFromEntry(BB) &&
1197	"Reachable block found while handling unreachable blocks");
1198
1199	// Make sure phi nodes in our reachable successors end up with a
1200	// LiveOnEntryDef for our incoming edge, even though our block is forward
1201	// unreachable. We could just disconnect these blocks from the CFG fully,
1202	// but we do not right now.
1203	for (const BasicBlock *S : successors(BB)) {
1204	if (!DT->isReachableFromEntry(A: S))
1205	continue;
1206	auto It = PerBlockAccesses.find(Val: S);
1207	// Rename the phi nodes in our successor block
1208	if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(Val: It->second->front()))
1209	continue;
1210	AccessList *Accesses = It->second.get();
1211	auto *Phi = cast<MemoryPhi>(Val: &Accesses->front());
1212	Phi->addIncoming(V: LiveOnEntryDef.get(), BB);
1213	}
1214
1215	auto It = PerBlockAccesses.find(Val: BB);
1216	if (It == PerBlockAccesses.end())
1217	return;
1218
1219	auto &Accesses = It->second;
1220	for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
1221	auto Next = std::next(x: AI);
1222	// If we have a phi, just remove it. We are going to replace all
1223	// users with live on entry.
1224	if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(Val&: AI))
1225	UseOrDef->setDefiningAccess(DMA: LiveOnEntryDef.get());
1226	else
1227	Accesses->erase(where: AI);
1228	AI = Next;
1229	}
1230	}
1231
1232	MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT)
1233	: DT(DT), F(Func), LiveOnEntryDef(nullptr), Walker(nullptr),
1234	SkipWalker(nullptr) {
1235	// Build MemorySSA using a batch alias analysis. This reuses the internal
1236	// state that AA collects during an alias()/getModRefInfo() call. This is
1237	// safe because there are no CFG changes while building MemorySSA and can
1238	// significantly reduce the time spent by the compiler in AA, because we will
1239	// make queries about all the instructions in the Function.
1240	assert(AA && "No alias analysis?");
1241	BatchAAResults BatchAA(*AA);
1242	buildMemorySSA(BAA&: BatchAA);
1243	// Intentionally leave AA to nullptr while building so we don't accidently
1244	// use non-batch AliasAnalysis.
1245	this->AA = AA;
1246	// Also create the walker here.
1247	getWalker();
1248	}
1249
1250	MemorySSA::~MemorySSA() {
1251	// Drop all our references
1252	for (const auto &Pair : PerBlockAccesses)
1253	for (MemoryAccess &MA : *Pair.second)
1254	MA.dropAllReferences();
1255	}
1256
1257	MemorySSA::AccessList *MemorySSA::getOrCreateAccessList(const BasicBlock *BB) {
1258	auto Res = PerBlockAccesses.insert(KV: std::make_pair(x&: BB, y: nullptr));
1259
1260	if (Res.second)
1261	Res.first->second = std::make_unique<AccessList>();
1262	return Res.first->second.get();
1263	}
1264
1265	MemorySSA::DefsList *MemorySSA::getOrCreateDefsList(const BasicBlock *BB) {
1266	auto Res = PerBlockDefs.insert(KV: std::make_pair(x&: BB, y: nullptr));
1267
1268	if (Res.second)
1269	Res.first->second = std::make_unique<DefsList>();
1270	return Res.first->second.get();
1271	}
1272
1273	namespace llvm {
1274
1275	/// This class is a batch walker of all MemoryUse's in the program, and points
1276	/// their defining access at the thing that actually clobbers them. Because it
1277	/// is a batch walker that touches everything, it does not operate like the
1278	/// other walkers. This walker is basically performing a top-down SSA renaming
1279	/// pass, where the version stack is used as the cache. This enables it to be
1280	/// significantly more time and memory efficient than using the regular walker,
1281	/// which is walking bottom-up.
1282	class MemorySSA::OptimizeUses {
1283	public:
1284	OptimizeUses(MemorySSA *MSSA, CachingWalker *Walker, BatchAAResults *BAA,
1285	DominatorTree *DT)
1286	: MSSA(MSSA), Walker(Walker), AA(BAA), DT(DT) {}
1287
1288	void optimizeUses();
1289
1290	private:
1291	/// This represents where a given memorylocation is in the stack.
1292	struct MemlocStackInfo {
1293	// This essentially is keeping track of versions of the stack. Whenever
1294	// the stack changes due to pushes or pops, these versions increase.
1295	unsigned long StackEpoch;
1296	unsigned long PopEpoch;
1297	// This is the lower bound of places on the stack to check. It is equal to
1298	// the place the last stack walk ended.
1299	// Note: Correctness depends on this being initialized to 0, which densemap
1300	// does
1301	unsigned long LowerBound;
1302	const BasicBlock *LowerBoundBlock;
1303	// This is where the last walk for this memory location ended.
1304	unsigned long LastKill;
1305	bool LastKillValid;
1306	};
1307
1308	void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
1309	SmallVectorImpl<MemoryAccess *> &,
1310	DenseMap<MemoryLocOrCall, MemlocStackInfo> &);
1311
1312	MemorySSA *MSSA;
1313	CachingWalker *Walker;
1314	BatchAAResults *AA;
1315	DominatorTree *DT;
1316	};
1317
1318	} // end namespace llvm
1319
1320	/// Optimize the uses in a given block This is basically the SSA renaming
1321	/// algorithm, with one caveat: We are able to use a single stack for all
1322	/// MemoryUses. This is because the set of *possible* reaching MemoryDefs is
1323	/// the same for every MemoryUse. The *actual* clobbering MemoryDef is just
1324	/// going to be some position in that stack of possible ones.
1325	///
1326	/// We track the stack positions that each MemoryLocation needs
1327	/// to check, and last ended at. This is because we only want to check the
1328	/// things that changed since last time. The same MemoryLocation should
1329	/// get clobbered by the same store (getModRefInfo does not use invariantness or
1330	/// things like this, and if they start, we can modify MemoryLocOrCall to
1331	/// include relevant data)
1332	void MemorySSA::OptimizeUses::optimizeUsesInBlock(
1333	const BasicBlock *BB, unsigned long &StackEpoch, unsigned long &PopEpoch,
1334	SmallVectorImpl<MemoryAccess *> &VersionStack,
1335	DenseMap<MemoryLocOrCall, MemlocStackInfo> &LocStackInfo) {
1336
1337	/// If no accesses, nothing to do.
1338	MemorySSA::AccessList *Accesses = MSSA->getWritableBlockAccesses(BB);
1339	if (Accesses == nullptr)
1340	return;
1341
1342	// Pop everything that doesn't dominate the current block off the stack,
1343	// increment the PopEpoch to account for this.
1344	while (true) {
1345	assert(
1346	!VersionStack.empty() &&
1347	"Version stack should have liveOnEntry sentinel dominating everything");
1348	BasicBlock *BackBlock = VersionStack.back()->getBlock();
1349	if (DT->dominates(A: BackBlock, B: BB))
1350	break;
1351	while (VersionStack.back()->getBlock() == BackBlock)
1352	VersionStack.pop_back();
1353	++PopEpoch;
1354	}
1355
1356	for (MemoryAccess &MA : *Accesses) {
1357	auto *MU = dyn_cast<MemoryUse>(Val: &MA);
1358	if (!MU) {
1359	VersionStack.push_back(Elt: &MA);
1360	++StackEpoch;
1361	continue;
1362	}
1363
1364	if (MU->isOptimized())
1365	continue;
1366
1367	MemoryLocOrCall UseMLOC(MU);
1368	auto &LocInfo = LocStackInfo[UseMLOC];
1369	// If the pop epoch changed, it means we've removed stuff from top of
1370	// stack due to changing blocks. We may have to reset the lower bound or
1371	// last kill info.
1372	if (LocInfo.PopEpoch != PopEpoch) {
1373	LocInfo.PopEpoch = PopEpoch;
1374	LocInfo.StackEpoch = StackEpoch;
1375	// If the lower bound was in something that no longer dominates us, we
1376	// have to reset it.
1377	// We can't simply track stack size, because the stack may have had
1378	// pushes/pops in the meantime.
1379	// XXX: This is non-optimal, but only is slower cases with heavily
1380	// branching dominator trees. To get the optimal number of queries would
1381	// be to make lowerbound and lastkill a per-loc stack, and pop it until
1382	// the top of that stack dominates us. This does not seem worth it ATM.
1383	// A much cheaper optimization would be to always explore the deepest
1384	// branch of the dominator tree first. This will guarantee this resets on
1385	// the smallest set of blocks.
1386	if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB &&
1387	!DT->dominates(A: LocInfo.LowerBoundBlock, B: BB)) {
1388	// Reset the lower bound of things to check.
1389	// TODO: Some day we should be able to reset to last kill, rather than
1390	// 0.
1391	LocInfo.LowerBound = 0;
1392	LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
1393	LocInfo.LastKillValid = false;
1394	}
1395	} else if (LocInfo.StackEpoch != StackEpoch) {
1396	// If all that has changed is the StackEpoch, we only have to check the
1397	// new things on the stack, because we've checked everything before. In
1398	// this case, the lower bound of things to check remains the same.
1399	LocInfo.PopEpoch = PopEpoch;
1400	LocInfo.StackEpoch = StackEpoch;
1401	}
1402	if (!LocInfo.LastKillValid) {
1403	LocInfo.LastKill = VersionStack.size() - 1;
1404	LocInfo.LastKillValid = true;
1405	}
1406
1407	// At this point, we should have corrected last kill and LowerBound to be
1408	// in bounds.
1409	assert(LocInfo.LowerBound < VersionStack.size() &&
1410	"Lower bound out of range");
1411	assert(LocInfo.LastKill < VersionStack.size() &&
1412	"Last kill info out of range");
1413	// In any case, the new upper bound is the top of the stack.
1414	unsigned long UpperBound = VersionStack.size() - 1;
1415
1416	if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) {
1417	LLVM_DEBUG(dbgs() << "MemorySSA skipping optimization of " << *MU << " ("
1418	<< *(MU->getMemoryInst()) << ")"
1419	<< " because there are "
1420	<< UpperBound - LocInfo.LowerBound
1421	<< " stores to disambiguate\n");
1422	// Because we did not walk, LastKill is no longer valid, as this may
1423	// have been a kill.
1424	LocInfo.LastKillValid = false;
1425	continue;
1426	}
1427	bool FoundClobberResult = false;
1428	unsigned UpwardWalkLimit = MaxCheckLimit;
1429	while (UpperBound > LocInfo.LowerBound) {
1430	if (isa<MemoryPhi>(Val: VersionStack[UpperBound])) {
1431	// For phis, use the walker, see where we ended up, go there.
1432	// The invariant.group handling in MemorySSA is ad-hoc and doesn't
1433	// support updates, so don't use it to optimize uses.
1434	MemoryAccess *Result =
1435	Walker->getClobberingMemoryAccessWithoutInvariantGroup(
1436	MA: MU, BAA&: *AA, UWL&: UpwardWalkLimit);
1437	// We are guaranteed to find it or something is wrong.
1438	while (VersionStack[UpperBound] != Result) {
1439	assert(UpperBound != 0);
1440	--UpperBound;
1441	}
1442	FoundClobberResult = true;
1443	break;
1444	}
1445
1446	MemoryDef *MD = cast<MemoryDef>(Val: VersionStack[UpperBound]);
1447	if (instructionClobbersQuery(MD, MU, UseMLOC, AA&: *AA)) {
1448	FoundClobberResult = true;
1449	break;
1450	}
1451	--UpperBound;
1452	}
1453
1454	// At the end of this loop, UpperBound is either a clobber, or lower bound
1455	// PHI walking may cause it to be < LowerBound, and in fact, < LastKill.
1456	if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
1457	MU->setDefiningAccess(DMA: VersionStack[UpperBound], Optimized: true);
1458	LocInfo.LastKill = UpperBound;
1459	} else {
1460	// Otherwise, we checked all the new ones, and now we know we can get to
1461	// LastKill.
1462	MU->setDefiningAccess(DMA: VersionStack[LocInfo.LastKill], Optimized: true);
1463	}
1464	LocInfo.LowerBound = VersionStack.size() - 1;
1465	LocInfo.LowerBoundBlock = BB;
1466	}
1467	}
1468
1469	/// Optimize uses to point to their actual clobbering definitions.
1470	void MemorySSA::OptimizeUses::optimizeUses() {
1471	SmallVector<MemoryAccess *, 16> VersionStack;
1472	DenseMap<MemoryLocOrCall, MemlocStackInfo> LocStackInfo;
1473	VersionStack.push_back(Elt: MSSA->getLiveOnEntryDef());
1474
1475	unsigned long StackEpoch = 1;
1476	unsigned long PopEpoch = 1;
1477	// We perform a non-recursive top-down dominator tree walk.
1478	for (const auto *DomNode : depth_first(G: DT->getRootNode()))
1479	optimizeUsesInBlock(BB: DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
1480	LocStackInfo);
1481	}
1482
1483	void MemorySSA::placePHINodes(
1484	const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks) {
1485	// Determine where our MemoryPhi's should go
1486	ForwardIDFCalculator IDFs(*DT);
1487	IDFs.setDefiningBlocks(DefiningBlocks);
1488	SmallVector<BasicBlock *, 32> IDFBlocks;
1489	IDFs.calculate(IDFBlocks);
1490
1491	// Now place MemoryPhi nodes.
1492	for (auto &BB : IDFBlocks)
1493	createMemoryPhi(BB);
1494	}
1495
1496	void MemorySSA::buildMemorySSA(BatchAAResults &BAA) {
1497	// We create an access to represent "live on entry", for things like
1498	// arguments or users of globals, where the memory they use is defined before
1499	// the beginning of the function. We do not actually insert it into the IR.
1500	// We do not define a live on exit for the immediate uses, and thus our
1501	// semantics do *not* imply that something with no immediate uses can simply
1502	// be removed.
1503	BasicBlock &StartingPoint = F.getEntryBlock();
1504	LiveOnEntryDef.reset(p: new MemoryDef(F.getContext(), nullptr, nullptr,
1505	&StartingPoint, NextID++));
1506
1507	// We maintain lists of memory accesses per-block, trading memory for time. We
1508	// could just look up the memory access for every possible instruction in the
1509	// stream.
1510	SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
1511	// Go through each block, figure out where defs occur, and chain together all
1512	// the accesses.
1513	for (BasicBlock &B : F) {
1514	bool InsertIntoDef = false;
1515	AccessList *Accesses = nullptr;
1516	DefsList *Defs = nullptr;
1517	for (Instruction &I : B) {
1518	MemoryUseOrDef *MUD = createNewAccess(I: &I, AAP: &BAA);
1519	if (!MUD)
1520	continue;
1521
1522	if (!Accesses)
1523	Accesses = getOrCreateAccessList(BB: &B);
1524	Accesses->push_back(val: MUD);
1525	if (isa<MemoryDef>(Val: MUD)) {
1526	InsertIntoDef = true;
1527	if (!Defs)
1528	Defs = getOrCreateDefsList(BB: &B);
1529	Defs->push_back(Node&: *MUD);
1530	}
1531	}
1532	if (InsertIntoDef)
1533	DefiningBlocks.insert(Ptr: &B);
1534	}
1535	placePHINodes(DefiningBlocks);
1536
1537	// Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
1538	// filled in with all blocks.
1539	SmallPtrSet<BasicBlock *, 16> Visited;
1540	renamePass(Root: DT->getRootNode(), IncomingVal: LiveOnEntryDef.get(), Visited);
1541
1542	// Mark the uses in unreachable blocks as live on entry, so that they go
1543	// somewhere.
1544	for (auto &BB : F)
1545	if (!Visited.count(Ptr: &BB))
1546	markUnreachableAsLiveOnEntry(BB: &BB);
1547	}
1548
1549	MemorySSAWalker *MemorySSA::getWalker() { return getWalkerImpl(); }
1550
1551	MemorySSA::CachingWalker *MemorySSA::getWalkerImpl() {
1552	if (Walker)
1553	return Walker.get();
1554
1555	if (!WalkerBase)
1556	WalkerBase = std::make_unique<ClobberWalkerBase>(args: this, args&: DT);
1557
1558	Walker = std::make_unique<CachingWalker>(args: this, args: WalkerBase.get());
1559	return Walker.get();
1560	}
1561
1562	MemorySSAWalker *MemorySSA::getSkipSelfWalker() {
1563	if (SkipWalker)
1564	return SkipWalker.get();
1565
1566	if (!WalkerBase)
1567	WalkerBase = std::make_unique<ClobberWalkerBase>(args: this, args&: DT);
1568
1569	SkipWalker = std::make_unique<SkipSelfWalker>(args: this, args: WalkerBase.get());
1570	return SkipWalker.get();
1571	}
1572
1573
1574	// This is a helper function used by the creation routines. It places NewAccess
1575	// into the access and defs lists for a given basic block, at the given
1576	// insertion point.
1577	void MemorySSA::insertIntoListsForBlock(MemoryAccess *NewAccess,
1578	const BasicBlock *BB,
1579	InsertionPlace Point) {
1580	auto *Accesses = getOrCreateAccessList(BB);
1581	if (Point == Beginning) {
1582	// If it's a phi node, it goes first, otherwise, it goes after any phi
1583	// nodes.
1584	if (isa<MemoryPhi>(Val: NewAccess)) {
1585	Accesses->push_front(val: NewAccess);
1586	auto *Defs = getOrCreateDefsList(BB);
1587	Defs->push_front(Node&: *NewAccess);
1588	} else {
1589	auto AI = find_if_not(
1590	Range&: *Accesses, P: [](const MemoryAccess &MA) { return isa<MemoryPhi>(Val: MA); });
1591	Accesses->insert(where: AI, New: NewAccess);
1592	if (!isa<MemoryUse>(Val: NewAccess)) {
1593	auto *Defs = getOrCreateDefsList(BB);
1594	auto DI = find_if_not(
1595	Range&: *Defs, P: [](const MemoryAccess &MA) { return isa<MemoryPhi>(Val: MA); });
1596	Defs->insert(I: DI, Node&: *NewAccess);
1597	}
1598	}
1599	} else {
1600	Accesses->push_back(val: NewAccess);
1601	if (!isa<MemoryUse>(Val: NewAccess)) {
1602	auto *Defs = getOrCreateDefsList(BB);
1603	Defs->push_back(Node&: *NewAccess);
1604	}
1605	}
1606	BlockNumberingValid.erase(Ptr: BB);
1607	}
1608
1609	void MemorySSA::insertIntoListsBefore(MemoryAccess *What, const BasicBlock *BB,
1610	AccessList::iterator InsertPt) {
1611	auto *Accesses = getWritableBlockAccesses(BB);
1612	bool WasEnd = InsertPt == Accesses->end();
1613	Accesses->insert(where: AccessList::iterator(InsertPt), New: What);
1614	if (!isa<MemoryUse>(Val: What)) {
1615	auto *Defs = getOrCreateDefsList(BB);
1616	// If we got asked to insert at the end, we have an easy job, just shove it
1617	// at the end. If we got asked to insert before an existing def, we also get
1618	// an iterator. If we got asked to insert before a use, we have to hunt for
1619	// the next def.
1620	if (WasEnd) {
1621	Defs->push_back(Node&: *What);
1622	} else if (isa<MemoryDef>(Val: InsertPt)) {
1623	Defs->insert(I: InsertPt->getDefsIterator(), Node&: *What);
1624	} else {
1625	while (InsertPt != Accesses->end() && !isa<MemoryDef>(Val: InsertPt))
1626	++InsertPt;
1627	// Either we found a def, or we are inserting at the end
1628	if (InsertPt == Accesses->end())
1629	Defs->push_back(Node&: *What);
1630	else
1631	Defs->insert(I: InsertPt->getDefsIterator(), Node&: *What);
1632	}
1633	}
1634	BlockNumberingValid.erase(Ptr: BB);
1635	}
1636
1637	void MemorySSA::prepareForMoveTo(MemoryAccess *What, BasicBlock *BB) {
1638	// Keep it in the lookup tables, remove from the lists
1639	removeFromLists(What, ShouldDelete: false);
1640
1641	// Note that moving should implicitly invalidate the optimized state of a
1642	// MemoryUse (and Phis can't be optimized). However, it doesn't do so for a
1643	// MemoryDef.
1644	if (auto *MD = dyn_cast<MemoryDef>(Val: What))
1645	MD->resetOptimized();
1646	What->setBlock(BB);
1647	}
1648
1649	// Move What before Where in the IR. The end result is that What will belong to
1650	// the right lists and have the right Block set, but will not otherwise be
1651	// correct. It will not have the right defining access, and if it is a def,
1652	// things below it will not properly be updated.
1653	void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1654	AccessList::iterator Where) {
1655	prepareForMoveTo(What, BB);
1656	insertIntoListsBefore(What, BB, InsertPt: Where);
1657	}
1658
1659	void MemorySSA::moveTo(MemoryAccess *What, BasicBlock *BB,
1660	InsertionPlace Point) {
1661	if (isa<MemoryPhi>(Val: What)) {
1662	assert(Point == Beginning &&
1663	"Can only move a Phi at the beginning of the block");
1664	// Update lookup table entry
1665	ValueToMemoryAccess.erase(Val: What->getBlock());
1666	bool Inserted = ValueToMemoryAccess.insert(KV: {BB, What}).second;
1667	(void)Inserted;
1668	assert(Inserted && "Cannot move a Phi to a block that already has one");
1669	}
1670
1671	prepareForMoveTo(What, BB);
1672	insertIntoListsForBlock(NewAccess: What, BB, Point);
1673	}
1674
1675	MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
1676	assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB");
1677	MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
1678	// Phi's always are placed at the front of the block.
1679	insertIntoListsForBlock(NewAccess: Phi, BB, Point: Beginning);
1680	ValueToMemoryAccess[BB] = Phi;
1681	return Phi;
1682	}
1683
1684	MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I,
1685	MemoryAccess *Definition,
1686	const MemoryUseOrDef *Template,
1687	bool CreationMustSucceed) {
1688	assert(!isa<PHINode>(I) && "Cannot create a defined access for a PHI");
1689	MemoryUseOrDef *NewAccess = createNewAccess(I, AAP: AA, Template);
1690	if (CreationMustSucceed)
1691	assert(NewAccess != nullptr && "Tried to create a memory access for a "
1692	"non-memory touching instruction");
1693	if (NewAccess) {
1694	assert((!Definition || !isa<MemoryUse>(Definition)) &&
1695	"A use cannot be a defining access");
1696	NewAccess->setDefiningAccess(DMA: Definition);
1697	}
1698	return NewAccess;
1699	}
1700
1701	// Return true if the instruction has ordering constraints.
1702	// Note specifically that this only considers stores and loads
1703	// because others are still considered ModRef by getModRefInfo.
1704	static inline bool isOrdered(const Instruction *I) {
1705	if (auto *SI = dyn_cast<StoreInst>(Val: I)) {
1706	if (!SI->isUnordered())
1707	return true;
1708	} else if (auto *LI = dyn_cast<LoadInst>(Val: I)) {
1709	if (!LI->isUnordered())
1710	return true;
1711	}
1712	return false;
1713	}
1714
1715	/// Helper function to create new memory accesses
1716	template <typename AliasAnalysisType>
1717	MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I,
1718	AliasAnalysisType *AAP,
1719	const MemoryUseOrDef *Template) {
1720	// The assume intrinsic has a control dependency which we model by claiming
1721	// that it writes arbitrarily. Debuginfo intrinsics may be considered
1722	// clobbers when we have a nonstandard AA pipeline. Ignore these fake memory
1723	// dependencies here.
1724	// FIXME: Replace this special casing with a more accurate modelling of
1725	// assume's control dependency.
1726	if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I)) {
1727	switch (II->getIntrinsicID()) {
1728	default:
1729	break;
1730	case Intrinsic::allow_runtime_check:
1731	case Intrinsic::allow_ubsan_check:
1732	case Intrinsic::assume:
1733	case Intrinsic::experimental_noalias_scope_decl:
1734	case Intrinsic::pseudoprobe:
1735	return nullptr;
1736	}
1737	}
1738
1739	// Using a nonstandard AA pipelines might leave us with unexpected modref
1740	// results for I, so add a check to not model instructions that may not read
1741	// from or write to memory. This is necessary for correctness.
1742	if (!I->mayReadFromMemory() && !I->mayWriteToMemory())
1743	return nullptr;
1744
1745	bool Def, Use;
1746	if (Template) {
1747	Def = isa<MemoryDef>(Val: Template);
1748	Use = isa<MemoryUse>(Val: Template);
1749	#if !defined(NDEBUG)
1750	ModRefInfo ModRef = AAP->getModRefInfo(I, std::nullopt);
1751	bool DefCheck, UseCheck;
1752	DefCheck = isModSet(MRI: ModRef) || isOrdered(I);
1753	UseCheck = isRefSet(MRI: ModRef);
1754	// Memory accesses should only be reduced and can not be increased since AA
1755	// just might return better results as a result of some transformations.
1756	assert((Def == DefCheck || !DefCheck) &&
1757	"Memory accesses should only be reduced");
1758	if (!Def && Use != UseCheck) {
1759	// New Access should not have more power than template access
1760	assert(!UseCheck && "Invalid template");
1761	}
1762	#endif
1763	} else {
1764	// Find out what affect this instruction has on memory.
1765	ModRefInfo ModRef = AAP->getModRefInfo(I, std::nullopt);
1766	// The isOrdered check is used to ensure that volatiles end up as defs
1767	// (atomics end up as ModRef right now anyway). Until we separate the
1768	// ordering chain from the memory chain, this enables people to see at least
1769	// some relative ordering to volatiles. Note that getClobberingMemoryAccess
1770	// will still give an answer that bypasses other volatile loads. TODO:
1771	// Separate memory aliasing and ordering into two different chains so that
1772	// we can precisely represent both "what memory will this read/write/is
1773	// clobbered by" and "what instructions can I move this past".
1774	Def = isModSet(MRI: ModRef) || isOrdered(I);
1775	Use = isRefSet(MRI: ModRef);
1776	}
1777
1778	// It's possible for an instruction to not modify memory at all. During
1779	// construction, we ignore them.
1780	if (!Def && !Use)
1781	return nullptr;
1782
1783	MemoryUseOrDef *MUD;
1784	if (Def) {
1785	MUD = new MemoryDef(I->getContext(), nullptr, I, I->getParent(), NextID++);
1786	} else {
1787	MUD = new MemoryUse(I->getContext(), nullptr, I, I->getParent());
1788	if (isUseTriviallyOptimizableToLiveOnEntry(*AAP, I)) {
1789	MemoryAccess *LiveOnEntry = getLiveOnEntryDef();
1790	MUD->setOptimized(LiveOnEntry);
1791	}
1792	}
1793	ValueToMemoryAccess[I] = MUD;
1794	return MUD;
1795	}
1796
1797	/// Properly remove \p MA from all of MemorySSA's lookup tables.
1798	void MemorySSA::removeFromLookups(MemoryAccess *MA) {
1799	assert(MA->use_empty() &&
1800	"Trying to remove memory access that still has uses");
1801	BlockNumbering.erase(Val: MA);
1802	if (auto *MUD = dyn_cast<MemoryUseOrDef>(Val: MA))
1803	MUD->setDefiningAccess(DMA: nullptr);
1804	// Invalidate our walker's cache if necessary
1805	if (!isa<MemoryUse>(Val: MA))
1806	getWalker()->invalidateInfo(MA);
1807
1808	Value *MemoryInst;
1809	if (const auto *MUD = dyn_cast<MemoryUseOrDef>(Val: MA))
1810	MemoryInst = MUD->getMemoryInst();
1811	else
1812	MemoryInst = MA->getBlock();
1813
1814	auto VMA = ValueToMemoryAccess.find(Val: MemoryInst);
1815	if (VMA->second == MA)
1816	ValueToMemoryAccess.erase(I: VMA);
1817	}
1818
1819	/// Properly remove \p MA from all of MemorySSA's lists.
1820	///
1821	/// Because of the way the intrusive list and use lists work, it is important to
1822	/// do removal in the right order.
1823	/// ShouldDelete defaults to true, and will cause the memory access to also be
1824	/// deleted, not just removed.
1825	void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) {
1826	BasicBlock *BB = MA->getBlock();
1827	// The access list owns the reference, so we erase it from the non-owning list
1828	// first.
1829	if (!isa<MemoryUse>(Val: MA)) {
1830	auto DefsIt = PerBlockDefs.find(Val: BB);
1831	std::unique_ptr<DefsList> &Defs = DefsIt->second;
1832	Defs->remove(N&: *MA);
1833	if (Defs->empty())
1834	PerBlockDefs.erase(I: DefsIt);
1835	}
1836
1837	// The erase call here will delete it. If we don't want it deleted, we call
1838	// remove instead.
1839	auto AccessIt = PerBlockAccesses.find(Val: BB);
1840	std::unique_ptr<AccessList> &Accesses = AccessIt->second;
1841	if (ShouldDelete)
1842	Accesses->erase(IT: MA);
1843	else
1844	Accesses->remove(IT: MA);
1845
1846	if (Accesses->empty()) {
1847	PerBlockAccesses.erase(I: AccessIt);
1848	BlockNumberingValid.erase(Ptr: BB);
1849	}
1850	}
1851
1852	void MemorySSA::print(raw_ostream &OS) const {
1853	MemorySSAAnnotatedWriter Writer(this);
1854	F.print(OS, AAW: &Writer);
1855	}
1856
1857	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1858	LLVM_DUMP_METHOD void MemorySSA::dump() const { print(OS&: dbgs()); }
1859	#endif
1860
1861	void MemorySSA::verifyMemorySSA(VerificationLevel VL) const {
1862	#if !defined(NDEBUG) && defined(EXPENSIVE_CHECKS)
1863	VL = VerificationLevel::Full;
1864	#endif
1865
1866	#ifndef NDEBUG
1867	verifyOrderingDominationAndDefUses(F, VL);
1868	verifyDominationNumbers(F);
1869	if (VL == VerificationLevel::Full)
1870	verifyPrevDefInPhis(F);
1871	#endif
1872	// Previously, the verification used to also verify that the clobberingAccess
1873	// cached by MemorySSA is the same as the clobberingAccess found at a later
1874	// query to AA. This does not hold true in general due to the current fragility
1875	// of BasicAA which has arbitrary caps on the things it analyzes before giving
1876	// up. As a result, transformations that are correct, will lead to BasicAA
1877	// returning different Alias answers before and after that transformation.
1878	// Invalidating MemorySSA is not an option, as the results in BasicAA can be so
1879	// random, in the worst case we'd need to rebuild MemorySSA from scratch after
1880	// every transformation, which defeats the purpose of using it. For such an
1881	// example, see test4 added in D51960.
1882	}
1883
1884	void MemorySSA::verifyPrevDefInPhis(Function &F) const {
1885	for (const BasicBlock &BB : F) {
1886	if (MemoryPhi *Phi = getMemoryAccess(BB: &BB)) {
1887	for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
1888	auto *Pred = Phi->getIncomingBlock(I);
1889	auto *IncAcc = Phi->getIncomingValue(I);
1890	// If Pred has no unreachable predecessors, get last def looking at
1891	// IDoms. If, while walkings IDoms, any of these has an unreachable
1892	// predecessor, then the incoming def can be any access.
1893	if (auto *DTNode = DT->getNode(BB: Pred)) {
1894	while (DTNode) {
1895	if (auto *DefList = getBlockDefs(BB: DTNode->getBlock())) {
1896	auto *LastAcc = &*(--DefList->end());
1897	assert(LastAcc == IncAcc &&
1898	"Incorrect incoming access into phi.");
1899	(void)IncAcc;
1900	(void)LastAcc;
1901	break;
1902	}
1903	DTNode = DTNode->getIDom();
1904	}
1905	} else {
1906	// If Pred has unreachable predecessors, but has at least a Def, the
1907	// incoming access can be the last Def in Pred, or it could have been
1908	// optimized to LoE. After an update, though, the LoE may have been
1909	// replaced by another access, so IncAcc may be any access.
1910	// If Pred has unreachable predecessors and no Defs, incoming access
1911	// should be LoE; However, after an update, it may be any access.
1912	}
1913	}
1914	}
1915	}
1916	}
1917
1918	/// Verify that all of the blocks we believe to have valid domination numbers
1919	/// actually have valid domination numbers.
1920	void MemorySSA::verifyDominationNumbers(const Function &F) const {
1921	if (BlockNumberingValid.empty())
1922	return;
1923
1924	SmallPtrSet<const BasicBlock *, 16> ValidBlocks = BlockNumberingValid;
1925	for (const BasicBlock &BB : F) {
1926	if (!ValidBlocks.count(Ptr: &BB))
1927	continue;
1928
1929	ValidBlocks.erase(Ptr: &BB);
1930
1931	const AccessList *Accesses = getBlockAccesses(BB: &BB);
1932	// It's correct to say an empty block has valid numbering.
1933	if (!Accesses)
1934	continue;
1935
1936	// Block numbering starts at 1.
1937	unsigned long LastNumber = 0;
1938	for (const MemoryAccess &MA : *Accesses) {
1939	auto ThisNumberIter = BlockNumbering.find(Val: &MA);
1940	assert(ThisNumberIter != BlockNumbering.end() &&
1941	"MemoryAccess has no domination number in a valid block!");
1942
1943	unsigned long ThisNumber = ThisNumberIter->second;
1944	assert(ThisNumber > LastNumber &&
1945	"Domination numbers should be strictly increasing!");
1946	(void)LastNumber;
1947	LastNumber = ThisNumber;
1948	}
1949	}
1950
1951	assert(ValidBlocks.empty() &&
1952	"All valid BasicBlocks should exist in F -- dangling pointers?");
1953	}
1954
1955	/// Verify ordering: the order and existence of MemoryAccesses matches the
1956	/// order and existence of memory affecting instructions.
1957	/// Verify domination: each definition dominates all of its uses.
1958	/// Verify def-uses: the immediate use information - walk all the memory
1959	/// accesses and verifying that, for each use, it appears in the appropriate
1960	/// def's use list
1961	void MemorySSA::verifyOrderingDominationAndDefUses(Function &F,
1962	VerificationLevel VL) const {
1963	// Walk all the blocks, comparing what the lookups think and what the access
1964	// lists think, as well as the order in the blocks vs the order in the access
1965	// lists.
1966	SmallVector<MemoryAccess *, 32> ActualAccesses;
1967	SmallVector<MemoryAccess *, 32> ActualDefs;
1968	for (BasicBlock &B : F) {
1969	const AccessList *AL = getBlockAccesses(BB: &B);
1970	const auto *DL = getBlockDefs(BB: &B);
1971	MemoryPhi *Phi = getMemoryAccess(BB: &B);
1972	if (Phi) {
1973	// Verify ordering.
1974	ActualAccesses.push_back(Elt: Phi);
1975	ActualDefs.push_back(Elt: Phi);
1976	// Verify domination
1977	for (const Use &U : Phi->uses()) {
1978	assert(dominates(Phi, U) && "Memory PHI does not dominate it's uses");
1979	(void)U;
1980	}
1981	// Verify def-uses for full verify.
1982	if (VL == VerificationLevel::Full) {
1983	assert(Phi->getNumOperands() == pred_size(&B) &&
1984	"Incomplete MemoryPhi Node");
1985	for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
1986	verifyUseInDefs(Phi->getIncomingValue(I), Phi);
1987	assert(is_contained(predecessors(&B), Phi->getIncomingBlock(I)) &&
1988	"Incoming phi block not a block predecessor");
1989	}
1990	}
1991	}
1992
1993	for (Instruction &I : B) {
1994	MemoryUseOrDef *MA = getMemoryAccess(I: &I);
1995	assert((!MA || (AL && (isa<MemoryUse>(MA) || DL))) &&
1996	"We have memory affecting instructions "
1997	"in this block but they are not in the "
1998	"access list or defs list");
1999	if (MA) {
2000	// Verify ordering.
2001	ActualAccesses.push_back(Elt: MA);
2002	if (MemoryAccess *MD = dyn_cast<MemoryDef>(Val: MA)) {
2003	// Verify ordering.
2004	ActualDefs.push_back(Elt: MA);
2005	// Verify domination.
2006	for (const Use &U : MD->uses()) {
2007	assert(dominates(MD, U) &&
2008	"Memory Def does not dominate it's uses");
2009	(void)U;
2010	}
2011	}
2012	// Verify def-uses for full verify.
2013	if (VL == VerificationLevel::Full)
2014	verifyUseInDefs(MA->getDefiningAccess(), MA);
2015	}
2016	}
2017	// Either we hit the assert, really have no accesses, or we have both
2018	// accesses and an access list. Same with defs.
2019	if (!AL && !DL)
2020	continue;
2021	// Verify ordering.
2022	assert(AL->size() == ActualAccesses.size() &&
2023	"We don't have the same number of accesses in the block as on the "
2024	"access list");
2025	assert((DL || ActualDefs.size() == 0) &&
2026	"Either we should have a defs list, or we should have no defs");
2027	assert((!DL || DL->size() == ActualDefs.size()) &&
2028	"We don't have the same number of defs in the block as on the "
2029	"def list");
2030	auto ALI = AL->begin();
2031	auto AAI = ActualAccesses.begin();
2032	while (ALI != AL->end() && AAI != ActualAccesses.end()) {
2033	assert(&*ALI == *AAI && "Not the same accesses in the same order");
2034	++ALI;
2035	++AAI;
2036	}
2037	ActualAccesses.clear();
2038	if (DL) {
2039	auto DLI = DL->begin();
2040	auto ADI = ActualDefs.begin();
2041	while (DLI != DL->end() && ADI != ActualDefs.end()) {
2042	assert(&*DLI == *ADI && "Not the same defs in the same order");
2043	++DLI;
2044	++ADI;
2045	}
2046	}
2047	ActualDefs.clear();
2048	}
2049	}
2050
2051	/// Verify the def-use lists in MemorySSA, by verifying that \p Use
2052	/// appears in the use list of \p Def.
2053	void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) const {
2054	// The live on entry use may cause us to get a NULL def here
2055	if (!Def)
2056	assert(isLiveOnEntryDef(Use) &&
2057	"Null def but use not point to live on entry def");
2058	else
2059	assert(is_contained(Def->users(), Use) &&
2060	"Did not find use in def's use list");
2061	}
2062
2063	/// Perform a local numbering on blocks so that instruction ordering can be
2064	/// determined in constant time.
2065	/// TODO: We currently just number in order. If we numbered by N, we could
2066	/// allow at least N-1 sequences of insertBefore or insertAfter (and at least
2067	/// log2(N) sequences of mixed before and after) without needing to invalidate
2068	/// the numbering.
2069	void MemorySSA::renumberBlock(const BasicBlock *B) const {
2070	// The pre-increment ensures the numbers really start at 1.
2071	unsigned long CurrentNumber = 0;
2072	const AccessList *AL = getBlockAccesses(BB: B);
2073	assert(AL != nullptr && "Asking to renumber an empty block");
2074	for (const auto &I : *AL)
2075	BlockNumbering[&I] = ++CurrentNumber;
2076	BlockNumberingValid.insert(Ptr: B);
2077	}
2078
2079	/// Determine, for two memory accesses in the same block,
2080	/// whether \p Dominator dominates \p Dominatee.
2081	/// \returns True if \p Dominator dominates \p Dominatee.
2082	bool MemorySSA::locallyDominates(const MemoryAccess *Dominator,
2083	const MemoryAccess *Dominatee) const {
2084	const BasicBlock *DominatorBlock = Dominator->getBlock();
2085
2086	assert((DominatorBlock == Dominatee->getBlock()) &&
2087	"Asking for local domination when accesses are in different blocks!");
2088	// A node dominates itself.
2089	if (Dominatee == Dominator)
2090	return true;
2091
2092	// When Dominatee is defined on function entry, it is not dominated by another
2093	// memory access.
2094	if (isLiveOnEntryDef(MA: Dominatee))
2095	return false;
2096
2097	// When Dominator is defined on function entry, it dominates the other memory
2098	// access.
2099	if (isLiveOnEntryDef(MA: Dominator))
2100	return true;
2101
2102	if (!BlockNumberingValid.count(Ptr: DominatorBlock))
2103	renumberBlock(B: DominatorBlock);
2104
2105	unsigned long DominatorNum = BlockNumbering.lookup(Val: Dominator);
2106	// All numbers start with 1
2107	assert(DominatorNum != 0 && "Block was not numbered properly");
2108	unsigned long DominateeNum = BlockNumbering.lookup(Val: Dominatee);
2109	assert(DominateeNum != 0 && "Block was not numbered properly");
2110	return DominatorNum < DominateeNum;
2111	}
2112
2113	bool MemorySSA::dominates(const MemoryAccess *Dominator,
2114	const MemoryAccess *Dominatee) const {
2115	if (Dominator == Dominatee)
2116	return true;
2117
2118	if (isLiveOnEntryDef(MA: Dominatee))
2119	return false;
2120
2121	if (Dominator->getBlock() != Dominatee->getBlock())
2122	return DT->dominates(A: Dominator->getBlock(), B: Dominatee->getBlock());
2123	return locallyDominates(Dominator, Dominatee);
2124	}
2125
2126	bool MemorySSA::dominates(const MemoryAccess *Dominator,
2127	const Use &Dominatee) const {
2128	if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Val: Dominatee.getUser())) {
2129	BasicBlock *UseBB = MP->getIncomingBlock(U: Dominatee);
2130	// The def must dominate the incoming block of the phi.
2131	if (UseBB != Dominator->getBlock())
2132	return DT->dominates(A: Dominator->getBlock(), B: UseBB);
2133	// If the UseBB and the DefBB are the same, compare locally.
2134	return locallyDominates(Dominator, Dominatee: cast<MemoryAccess>(Val: Dominatee));
2135	}
2136	// If it's not a PHI node use, the normal dominates can already handle it.
2137	return dominates(Dominator, Dominatee: cast<MemoryAccess>(Val: Dominatee.getUser()));
2138	}
2139
2140	void MemorySSA::ensureOptimizedUses() {
2141	if (IsOptimized)
2142	return;
2143
2144	BatchAAResults BatchAA(*AA);
2145	ClobberWalkerBase WalkerBase(this, DT);
2146	CachingWalker WalkerLocal(this, &WalkerBase);
2147	OptimizeUses(this, &WalkerLocal, &BatchAA, DT).optimizeUses();
2148	IsOptimized = true;
2149	}
2150
2151	void MemoryAccess::print(raw_ostream &OS) const {
2152	switch (getValueID()) {
2153	case MemoryPhiVal: return static_cast<const MemoryPhi *>(this)->print(OS);
2154	case MemoryDefVal: return static_cast<const MemoryDef *>(this)->print(OS);
2155	case MemoryUseVal: return static_cast<const MemoryUse *>(this)->print(OS);
2156	}
2157	llvm_unreachable("invalid value id");
2158	}
2159
2160	void MemoryDef::print(raw_ostream &OS) const {
2161	MemoryAccess *UO = getDefiningAccess();
2162
2163	auto printID = [&OS](MemoryAccess *A) {
2164	if (A && A->getID())
2165	OS << A->getID();
2166	else
2167	OS << LiveOnEntryStr;
2168	};
2169
2170	OS << getID() << " = MemoryDef(";
2171	printID(UO);
2172	OS << ")";
2173
2174	if (isOptimized()) {
2175	OS << "->";
2176	printID(getOptimized());
2177	}
2178	}
2179
2180	void MemoryPhi::print(raw_ostream &OS) const {
2181	ListSeparator LS(",");
2182	OS << getID() << " = MemoryPhi(";
2183	for (const auto &Op : operands()) {
2184	BasicBlock *BB = getIncomingBlock(U: Op);
2185	MemoryAccess *MA = cast<MemoryAccess>(Val: Op);
2186
2187	OS << LS << '{';
2188	if (BB->hasName())
2189	OS << BB->getName();
2190	else
2191	BB->printAsOperand(O&: OS, PrintType: false);
2192	OS << ',';
2193	if (unsigned ID = MA->getID())
2194	OS << ID;
2195	else
2196	OS << LiveOnEntryStr;
2197	OS << '}';
2198	}
2199	OS << ')';
2200	}
2201
2202	void MemoryUse::print(raw_ostream &OS) const {
2203	MemoryAccess *UO = getDefiningAccess();
2204	OS << "MemoryUse(";
2205	if (UO && UO->getID())
2206	OS << UO->getID();
2207	else
2208	OS << LiveOnEntryStr;
2209	OS << ')';
2210	}
2211
2212	void MemoryAccess::dump() const {
2213	// Cannot completely remove virtual function even in release mode.
2214	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2215	print(OS&: dbgs());
2216	dbgs() << "\n";
2217	#endif
2218	}
2219
2220	class DOTFuncMSSAInfo {
2221	private:
2222	const Function &F;
2223	MemorySSAAnnotatedWriter MSSAWriter;
2224
2225	public:
2226	DOTFuncMSSAInfo(const Function &F, MemorySSA &MSSA)
2227	: F(F), MSSAWriter(&MSSA) {}
2228
2229	const Function *getFunction() { return &F; }
2230	MemorySSAAnnotatedWriter &getWriter() { return MSSAWriter; }
2231	};
2232
2233	namespace llvm {
2234
2235	template <>
2236	struct GraphTraits<DOTFuncMSSAInfo *> : public GraphTraits<const BasicBlock *> {
2237	static NodeRef getEntryNode(DOTFuncMSSAInfo *CFGInfo) {
2238	return &(CFGInfo->getFunction()->getEntryBlock());
2239	}
2240
2241	// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
2242	using nodes_iterator = pointer_iterator<Function::const_iterator>;
2243
2244	static nodes_iterator nodes_begin(DOTFuncMSSAInfo *CFGInfo) {
2245	return nodes_iterator(CFGInfo->getFunction()->begin());
2246	}
2247
2248	static nodes_iterator nodes_end(DOTFuncMSSAInfo *CFGInfo) {
2249	return nodes_iterator(CFGInfo->getFunction()->end());
2250	}
2251
2252	static size_t size(DOTFuncMSSAInfo *CFGInfo) {
2253	return CFGInfo->getFunction()->size();
2254	}
2255	};
2256
2257	template <>
2258	struct DOTGraphTraits<DOTFuncMSSAInfo *> : public DefaultDOTGraphTraits {
2259
2260	DOTGraphTraits(bool IsSimple = false) : DefaultDOTGraphTraits(IsSimple) {}
2261
2262	static std::string getGraphName(DOTFuncMSSAInfo *CFGInfo) {
2263	return "MSSA CFG for '" + CFGInfo->getFunction()->getName().str() +
2264	"' function";
2265	}
2266
2267	std::string getNodeLabel(const BasicBlock *Node, DOTFuncMSSAInfo *CFGInfo) {
2268	return DOTGraphTraits<DOTFuncInfo *>::getCompleteNodeLabel(
2269	Node, nullptr,
2270	HandleBasicBlock: [CFGInfo](raw_string_ostream &OS, const BasicBlock &BB) -> void {
2271	BB.print(OS, AAW: &CFGInfo->getWriter(), ShouldPreserveUseListOrder: true, IsForDebug: true);
2272	},
2273	HandleComment: [](std::string &S, unsigned &I, unsigned Idx) -> void {
2274	std::string Str = S.substr(pos: I, n: Idx - I);
2275	StringRef SR = Str;
2276	if (SR.count(Str: " = MemoryDef(") || SR.count(Str: " = MemoryPhi(") ||
2277	SR.count(Str: "MemoryUse("))
2278	return;
2279	DOTGraphTraits<DOTFuncInfo *>::eraseComment(OutStr&: S, I, Idx);
2280	});
2281	}
2282
2283	static std::string getEdgeSourceLabel(const BasicBlock *Node,
2284	const_succ_iterator I) {
2285	return DOTGraphTraits<DOTFuncInfo *>::getEdgeSourceLabel(Node, I);
2286	}
2287
2288	/// Display the raw branch weights from PGO.
2289	std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I,
2290	DOTFuncMSSAInfo *CFGInfo) {
2291	return "";
2292	}
2293
2294	std::string getNodeAttributes(const BasicBlock *Node,
2295	DOTFuncMSSAInfo *CFGInfo) {
2296	return getNodeLabel(Node, CFGInfo).find(c: ';') != std::string::npos
2297	? "style=filled, fillcolor=lightpink"
2298	: "";
2299	}
2300	};
2301
2302	} // namespace llvm
2303
2304	AnalysisKey MemorySSAAnalysis::Key;
2305
2306	MemorySSAAnalysis::Result MemorySSAAnalysis::run(Function &F,
2307	FunctionAnalysisManager &AM) {
2308	auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
2309	auto &AA = AM.getResult<AAManager>(IR&: F);
2310	return MemorySSAAnalysis::Result(std::make_unique<MemorySSA>(args&: F, args: &AA, args: &DT));
2311	}
2312
2313	bool MemorySSAAnalysis::Result::invalidate(
2314	Function &F, const PreservedAnalyses &PA,
2315	FunctionAnalysisManager::Invalidator &Inv) {
2316	auto PAC = PA.getChecker<MemorySSAAnalysis>();
2317	return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
2318	Inv.invalidate<AAManager>(IR&: F, PA) ||
2319	Inv.invalidate<DominatorTreeAnalysis>(IR&: F, PA);
2320	}
2321
2322	PreservedAnalyses MemorySSAPrinterPass::run(Function &F,
2323	FunctionAnalysisManager &AM) {
2324	auto &MSSA = AM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA();
2325	if (EnsureOptimizedUses)
2326	MSSA.ensureOptimizedUses();
2327	if (DotCFGMSSA != "") {
2328	DOTFuncMSSAInfo CFGInfo(F, MSSA);
2329	WriteGraph(G: &CFGInfo, Name: "", ShortNames: false, Title: "MSSA", Filename: DotCFGMSSA);
2330	} else {
2331	OS << "MemorySSA for function: " << F.getName() << "\n";
2332	MSSA.print(OS);
2333	}
2334
2335	return PreservedAnalyses::all();
2336	}
2337
2338	PreservedAnalyses MemorySSAWalkerPrinterPass::run(Function &F,
2339	FunctionAnalysisManager &AM) {
2340	auto &MSSA = AM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA();
2341	OS << "MemorySSA (walker) for function: " << F.getName() << "\n";
2342	MemorySSAWalkerAnnotatedWriter Writer(&MSSA);
2343	F.print(OS, AAW: &Writer);
2344
2345	return PreservedAnalyses::all();
2346	}
2347
2348	PreservedAnalyses MemorySSAVerifierPass::run(Function &F,
2349	FunctionAnalysisManager &AM) {
2350	AM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA().verifyMemorySSA();
2351
2352	return PreservedAnalyses::all();
2353	}
2354
2355	char MemorySSAWrapperPass::ID = 0;
2356
2357	MemorySSAWrapperPass::MemorySSAWrapperPass() : FunctionPass(ID) {
2358	initializeMemorySSAWrapperPassPass(Registry&: *PassRegistry::getPassRegistry());
2359	}
2360
2361	void MemorySSAWrapperPass::releaseMemory() { MSSA.reset(); }
2362
2363	void MemorySSAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
2364	AU.setPreservesAll();
2365	AU.addRequiredTransitive<DominatorTreeWrapperPass>();
2366	AU.addRequiredTransitive<AAResultsWrapperPass>();
2367	}
2368
2369	bool MemorySSAWrapperPass::runOnFunction(Function &F) {
2370	auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2371	auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2372	MSSA.reset(p: new MemorySSA(F, &AA, &DT));
2373	return false;
2374	}
2375
2376	void MemorySSAWrapperPass::verifyAnalysis() const {
2377	if (VerifyMemorySSA)
2378	MSSA->verifyMemorySSA();
2379	}
2380
2381	void MemorySSAWrapperPass::print(raw_ostream &OS, const Module *M) const {
2382	MSSA->print(OS);
2383	}
2384
2385	MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {}
2386
2387	/// Walk the use-def chains starting at \p StartingAccess and find
2388	/// the MemoryAccess that actually clobbers Loc.
2389	///
2390	/// \returns our clobbering memory access
2391	MemoryAccess *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
2392	MemoryAccess *StartingAccess, const MemoryLocation &Loc,
2393	BatchAAResults &BAA, unsigned &UpwardWalkLimit) {
2394	assert(!isa<MemoryUse>(StartingAccess) && "Use cannot be defining access");
2395
2396	// If location is undefined, conservatively return starting access.
2397	if (Loc.Ptr == nullptr)
2398	return StartingAccess;
2399
2400	Instruction *I = nullptr;
2401	if (auto *StartingUseOrDef = dyn_cast<MemoryUseOrDef>(Val: StartingAccess)) {
2402	if (MSSA->isLiveOnEntryDef(MA: StartingUseOrDef))
2403	return StartingUseOrDef;
2404
2405	I = StartingUseOrDef->getMemoryInst();
2406
2407	// Conservatively, fences are always clobbers, so don't perform the walk if
2408	// we hit a fence.
2409	if (!isa<CallBase>(Val: I) && I->isFenceLike())
2410	return StartingUseOrDef;
2411	}
2412
2413	UpwardsMemoryQuery Q;
2414	Q.OriginalAccess = StartingAccess;
2415	Q.StartingLoc = Loc;
2416	Q.Inst = nullptr;
2417	Q.IsCall = false;
2418
2419	// Unlike the other function, do not walk to the def of a def, because we are
2420	// handed something we already believe is the clobbering access.
2421	// We never set SkipSelf to true in Q in this method.
2422	MemoryAccess *Clobber =
2423	Walker.findClobber(BAA, Start: StartingAccess, Q, UpWalkLimit&: UpwardWalkLimit);
2424	LLVM_DEBUG({
2425	dbgs() << "Clobber starting at access " << *StartingAccess << "\n";
2426	if (I)
2427	dbgs() << " for instruction " << *I << "\n";
2428	dbgs() << " is " << *Clobber << "\n";
2429	});
2430	return Clobber;
2431	}
2432
2433	static const Instruction *
2434	getInvariantGroupClobberingInstruction(Instruction &I, DominatorTree &DT) {
2435	if (!I.hasMetadata(KindID: LLVMContext::MD_invariant_group) || I.isVolatile())
2436	return nullptr;
2437
2438	// We consider bitcasts and zero GEPs to be the same pointer value. Start by
2439	// stripping bitcasts and zero GEPs, then we will recursively look at loads
2440	// and stores through bitcasts and zero GEPs.
2441	Value *PointerOperand = getLoadStorePointerOperand(V: &I)->stripPointerCasts();
2442
2443	// It's not safe to walk the use list of a global value because function
2444	// passes aren't allowed to look outside their functions.
2445	// FIXME: this could be fixed by filtering instructions from outside of
2446	// current function.
2447	if (isa<Constant>(Val: PointerOperand))
2448	return nullptr;
2449
2450	// Queue to process all pointers that are equivalent to load operand.
2451	SmallVector<const Value *, 8> PointerUsesQueue;
2452	PointerUsesQueue.push_back(Elt: PointerOperand);
2453
2454	const Instruction *MostDominatingInstruction = &I;
2455
2456	// FIXME: This loop is O(n^2) because dominates can be O(n) and in worst case
2457	// we will see all the instructions. It may not matter in practice. If it
2458	// does, we will have to support MemorySSA construction and updates.
2459	while (!PointerUsesQueue.empty()) {
2460	const Value *Ptr = PointerUsesQueue.pop_back_val();
2461	assert(Ptr && !isa<GlobalValue>(Ptr) &&
2462	"Null or GlobalValue should not be inserted");
2463
2464	for (const User *Us : Ptr->users()) {
2465	auto *U = dyn_cast<Instruction>(Val: Us);
2466	if (!U || U == &I || !DT.dominates(Def: U, User: MostDominatingInstruction))
2467	continue;
2468
2469	// Add bitcasts and zero GEPs to queue.
2470	if (isa<BitCastInst>(Val: U)) {
2471	PointerUsesQueue.push_back(Elt: U);
2472	continue;
2473	}
2474	if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: U)) {
2475	if (GEP->hasAllZeroIndices())
2476	PointerUsesQueue.push_back(Elt: U);
2477	continue;
2478	}
2479
2480	// If we hit a load/store with an invariant.group metadata and the same
2481	// pointer operand, we can assume that value pointed to by the pointer
2482	// operand didn't change.
2483	if (U->hasMetadata(KindID: LLVMContext::MD_invariant_group) &&
2484	getLoadStorePointerOperand(V: U) == Ptr && !U->isVolatile()) {
2485	MostDominatingInstruction = U;
2486	}
2487	}
2488	}
2489	return MostDominatingInstruction == &I ? nullptr : MostDominatingInstruction;
2490	}
2491
2492	MemoryAccess *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
2493	MemoryAccess *MA, BatchAAResults &BAA, unsigned &UpwardWalkLimit,
2494	bool SkipSelf, bool UseInvariantGroup) {
2495	auto *StartingAccess = dyn_cast<MemoryUseOrDef>(Val: MA);
2496	// If this is a MemoryPhi, we can't do anything.
2497	if (!StartingAccess)
2498	return MA;
2499
2500	if (UseInvariantGroup) {
2501	if (auto *I = getInvariantGroupClobberingInstruction(
2502	I&: *StartingAccess->getMemoryInst(), DT&: MSSA->getDomTree())) {
2503	assert(isa<LoadInst>(I) || isa<StoreInst>(I));
2504
2505	auto *ClobberMA = MSSA->getMemoryAccess(I);
2506	assert(ClobberMA);
2507	if (isa<MemoryUse>(Val: ClobberMA))
2508	return ClobberMA->getDefiningAccess();
2509	return ClobberMA;
2510	}
2511	}
2512
2513	bool IsOptimized = false;
2514
2515	// If this is an already optimized use or def, return the optimized result.
2516	// Note: Currently, we store the optimized def result in a separate field,
2517	// since we can't use the defining access.
2518	if (StartingAccess->isOptimized()) {
2519	if (!SkipSelf || !isa<MemoryDef>(Val: StartingAccess))
2520	return StartingAccess->getOptimized();
2521	IsOptimized = true;
2522	}
2523
2524	const Instruction *I = StartingAccess->getMemoryInst();
2525	// We can't sanely do anything with a fence, since they conservatively clobber
2526	// all memory, and have no locations to get pointers from to try to
2527	// disambiguate.
2528	if (!isa<CallBase>(Val: I) && I->isFenceLike())
2529	return StartingAccess;
2530
2531	UpwardsMemoryQuery Q(I, StartingAccess);
2532
2533	if (isUseTriviallyOptimizableToLiveOnEntry(AA&: BAA, I)) {
2534	MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef();
2535	StartingAccess->setOptimized(LiveOnEntry);
2536	return LiveOnEntry;
2537	}
2538
2539	MemoryAccess *OptimizedAccess;
2540	if (!IsOptimized) {
2541	// Start with the thing we already think clobbers this location
2542	MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
2543
2544	// At this point, DefiningAccess may be the live on entry def.
2545	// If it is, we will not get a better result.
2546	if (MSSA->isLiveOnEntryDef(MA: DefiningAccess)) {
2547	StartingAccess->setOptimized(DefiningAccess);
2548	return DefiningAccess;
2549	}
2550
2551	OptimizedAccess =
2552	Walker.findClobber(BAA, Start: DefiningAccess, Q, UpWalkLimit&: UpwardWalkLimit);
2553	StartingAccess->setOptimized(OptimizedAccess);
2554	} else
2555	OptimizedAccess = StartingAccess->getOptimized();
2556
2557	LLVM_DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
2558	LLVM_DEBUG(dbgs() << *StartingAccess << "\n");
2559	LLVM_DEBUG(dbgs() << "Optimized Memory SSA clobber for " << *I << " is ");
2560	LLVM_DEBUG(dbgs() << *OptimizedAccess << "\n");
2561
2562	MemoryAccess *Result;
2563	if (SkipSelf && isa<MemoryPhi>(Val: OptimizedAccess) &&
2564	isa<MemoryDef>(Val: StartingAccess) && UpwardWalkLimit) {
2565	assert(isa<MemoryDef>(Q.OriginalAccess));
2566	Q.SkipSelfAccess = true;
2567	Result = Walker.findClobber(BAA, Start: OptimizedAccess, Q, UpWalkLimit&: UpwardWalkLimit);
2568	} else
2569	Result = OptimizedAccess;
2570
2571	LLVM_DEBUG(dbgs() << "Result Memory SSA clobber [SkipSelf = " << SkipSelf);
2572	LLVM_DEBUG(dbgs() << "] for " << *I << " is " << *Result << "\n");
2573
2574	return Result;
2575	}
2576
2577	MemoryAccess *
2578	DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA,
2579	BatchAAResults &) {
2580	if (auto *Use = dyn_cast<MemoryUseOrDef>(Val: MA))
2581	return Use->getDefiningAccess();
2582	return MA;
2583	}
2584
2585	MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
2586	MemoryAccess *StartingAccess, const MemoryLocation &, BatchAAResults &) {
2587	if (auto *Use = dyn_cast<MemoryUseOrDef>(Val: StartingAccess))
2588	return Use->getDefiningAccess();
2589	return StartingAccess;
2590	}
2591
2592	void MemoryPhi::deleteMe(DerivedUser *Self) {
2593	delete static_cast<MemoryPhi *>(Self);
2594	}
2595
2596	void MemoryDef::deleteMe(DerivedUser *Self) {
2597	delete static_cast<MemoryDef *>(Self);
2598	}
2599
2600	void MemoryUse::deleteMe(DerivedUser *Self) {
2601	delete static_cast<MemoryUse *>(Self);
2602	}
2603
2604	bool upward_defs_iterator::IsGuaranteedLoopInvariant(const Value *Ptr) const {
2605	auto IsGuaranteedLoopInvariantBase = [](const Value *Ptr) {
2606	Ptr = Ptr->stripPointerCasts();
2607	if (!isa<Instruction>(Val: Ptr))
2608	return true;
2609	return isa<AllocaInst>(Val: Ptr);
2610	};
2611
2612	Ptr = Ptr->stripPointerCasts();
2613	if (auto *I = dyn_cast<Instruction>(Val: Ptr)) {
2614	if (I->getParent()->isEntryBlock())
2615	return true;
2616	}
2617	if (auto *GEP = dyn_cast<GEPOperator>(Val: Ptr)) {
2618	return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
2619	GEP->hasAllConstantIndices();
2620	}
2621	return IsGuaranteedLoopInvariantBase(Ptr);
2622	}
2623