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