LICM.cpp source code [llvm_projects/llvm/lib/Transforms/Scalar/LICM.cpp]

1	//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
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 pass performs loop invariant code motion, attempting to remove as much
10	// code from the body of a loop as possible. It does this by either hoisting
11	// code into the preheader block, or by sinking code to the exit blocks if it is
12	// safe. This pass also promotes must-aliased memory locations in the loop to
13	// live in registers, thus hoisting and sinking "invariant" loads and stores.
14	//
15	// Hoisting operations out of loops is a canonicalization transform. It
16	// enables and simplifies subsequent optimizations in the middle-end.
17	// Rematerialization of hoisted instructions to reduce register pressure is the
18	// responsibility of the back-end, which has more accurate information about
19	// register pressure and also handles other optimizations than LICM that
20	// increase live-ranges.
21	//
22	// This pass uses alias analysis for two purposes:
23	//
24	// 1. Moving loop invariant loads and calls out of loops. If we can determine
25	// that a load or call inside of a loop never aliases anything stored to,
26	// we can hoist it or sink it like any other instruction.
27	// 2. Scalar Promotion of Memory - If there is a store instruction inside of
28	// the loop, we try to move the store to happen AFTER the loop instead of
29	// inside of the loop. This can only happen if a few conditions are true:
30	// A. The pointer stored through is loop invariant
31	// B. There are no stores or loads in the loop which _may_ alias the
32	// pointer. There are no calls in the loop which mod/ref the pointer.
33	// If these conditions are true, we can promote the loads and stores in the
34	// loop of the pointer to use a temporary alloca'd variable. We then use
35	// the SSAUpdater to construct the appropriate SSA form for the value.
36	//
37	//===----------------------------------------------------------------------===//
38
39	#include "llvm/Transforms/Scalar/LICM.h"
40	#include "llvm/ADT/PriorityWorklist.h"
41	#include "llvm/ADT/SetOperations.h"
42	#include "llvm/ADT/Statistic.h"
43	#include "llvm/Analysis/AliasAnalysis.h"
44	#include "llvm/Analysis/AliasSetTracker.h"
45	#include "llvm/Analysis/AssumptionCache.h"
46	#include "llvm/Analysis/CaptureTracking.h"
47	#include "llvm/Analysis/DomTreeUpdater.h"
48	#include "llvm/Analysis/GuardUtils.h"
49	#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
50	#include "llvm/Analysis/Loads.h"
51	#include "llvm/Analysis/LoopInfo.h"
52	#include "llvm/Analysis/LoopIterator.h"
53	#include "llvm/Analysis/LoopNestAnalysis.h"
54	#include "llvm/Analysis/LoopPass.h"
55	#include "llvm/Analysis/MemorySSA.h"
56	#include "llvm/Analysis/MemorySSAUpdater.h"
57	#include "llvm/Analysis/MustExecute.h"
58	#include "llvm/Analysis/OptimizationRemarkEmitter.h"
59	#include "llvm/Analysis/ScalarEvolution.h"
60	#include "llvm/Analysis/TargetLibraryInfo.h"
61	#include "llvm/Analysis/TargetTransformInfo.h"
62	#include "llvm/Analysis/ValueTracking.h"
63	#include "llvm/IR/CFG.h"
64	#include "llvm/IR/Constants.h"
65	#include "llvm/IR/DataLayout.h"
66	#include "llvm/IR/DebugInfoMetadata.h"
67	#include "llvm/IR/DerivedTypes.h"
68	#include "llvm/IR/Dominators.h"
69	#include "llvm/IR/IRBuilder.h"
70	#include "llvm/IR/Instructions.h"
71	#include "llvm/IR/IntrinsicInst.h"
72	#include "llvm/IR/LLVMContext.h"
73	#include "llvm/IR/Metadata.h"
74	#include "llvm/IR/PatternMatch.h"
75	#include "llvm/IR/PredIteratorCache.h"
76	#include "llvm/InitializePasses.h"
77	#include "llvm/Support/CommandLine.h"
78	#include "llvm/Support/Debug.h"
79	#include "llvm/Support/raw_ostream.h"
80	#include "llvm/Transforms/Scalar.h"
81	#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
82	#include "llvm/Transforms/Utils/BasicBlockUtils.h"
83	#include "llvm/Transforms/Utils/Local.h"
84	#include "llvm/Transforms/Utils/LoopUtils.h"
85	#include "llvm/Transforms/Utils/SSAUpdater.h"
86	#include <algorithm>
87	#include <utility>
88	using namespace llvm;
89
90	namespace llvm {
91	class LPMUpdater;
92	} // namespace llvm
93
94	#define DEBUG_TYPE "licm"
95
96	STATISTIC(NumCreatedBlocks, "Number of blocks created");
97	STATISTIC(NumClonedBranches, "Number of branches cloned");
98	STATISTIC(NumSunk, "Number of instructions sunk out of loop");
99	STATISTIC(NumHoisted, "Number of instructions hoisted out of loop");
100	STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
101	STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
102	STATISTIC(NumPromotionCandidates, "Number of promotion candidates");
103	STATISTIC(NumLoadPromoted, "Number of load-only promotions");
104	STATISTIC(NumLoadStorePromoted, "Number of load and store promotions");
105	STATISTIC(NumMinMaxHoisted,
106	"Number of min/max expressions hoisted out of the loop");
107	STATISTIC(NumGEPsHoisted,
108	"Number of geps reassociated and hoisted out of the loop");
109	STATISTIC(NumAddSubHoisted, "Number of add/subtract expressions reassociated "
110	"and hoisted out of the loop");
111	STATISTIC(NumFPAssociationsHoisted, "Number of invariant FP expressions "
112	"reassociated and hoisted out of the loop");
113	STATISTIC(NumIntAssociationsHoisted,
114	"Number of invariant int expressions "
115	"reassociated and hoisted out of the loop");
116	STATISTIC(NumBOAssociationsHoisted, "Number of invariant BinaryOp expressions "
117	"reassociated and hoisted out of the loop");
118
119	/// Memory promotion is enabled by default.
120	static cl::opt<bool>
121	DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(Val: false),
122	cl::desc("Disable memory promotion in LICM pass"));
123
124	static cl::opt<bool> ControlFlowHoisting(
125	"licm-control-flow-hoisting", cl::Hidden, cl::init(Val: false),
126	cl::desc("Enable control flow (and PHI) hoisting in LICM"));
127
128	static cl::opt<bool>
129	SingleThread("licm-force-thread-model-single", cl::Hidden, cl::init(Val: false),
130	cl::desc("Force thread model single in LICM pass"));
131
132	static cl::opt<uint32_t> MaxNumUsesTraversed(
133	"licm-max-num-uses-traversed", cl::Hidden, cl::init(Val: `8`),
134	cl::desc("Max num uses visited for identifying load "
135	"invariance in loop using invariant start (default = 8)"));
136
137	static cl::opt<unsigned> FPAssociationUpperLimit(
138	"licm-max-num-fp-reassociations", cl::init(Val: `5U`), cl::Hidden,
139	cl::desc(
140	"Set upper limit for the number of transformations performed "
141	"during a single round of hoisting the reassociated expressions."));
142
143	static cl::opt<unsigned> IntAssociationUpperLimit(
144	"licm-max-num-int-reassociations", cl::init(Val: `5U`), cl::Hidden,
145	cl::desc(
146	"Set upper limit for the number of transformations performed "
147	"during a single round of hoisting the reassociated expressions."));
148
149	// Experimental option to allow imprecision in LICM in pathological cases, in
150	// exchange for faster compile. This is to be removed if MemorySSA starts to
151	// address the same issue. LICM calls MemorySSAWalker's
152	// getClobberingMemoryAccess, up to the value of the Cap, getting perfect
153	// accuracy. Afterwards, LICM will call into MemorySSA's getDefiningAccess,
154	// which may not be precise, since optimizeUses is capped. The result is
155	// correct, but we may not get as "far up" as possible to get which access is
156	// clobbering the one queried.
157	cl::opt<unsigned> llvm::SetLicmMssaOptCap(
158	"licm-mssa-optimization-cap", cl::init(Val: `100`), cl::Hidden,
159	cl::desc("Enable imprecision in LICM in pathological cases, in exchange "
160	"for faster compile. Caps the MemorySSA clobbering calls."));
161
162	// Experimentally, memory promotion carries less importance than sinking and
163	// hoisting. Limit when we do promotion when using MemorySSA, in order to save
164	// compile time.
165	cl::opt<unsigned> llvm::SetLicmMssaNoAccForPromotionCap(
166	"licm-mssa-max-acc-promotion", cl::init(Val: `250`), cl::Hidden,
167	cl::desc("[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
168	"effect. When MSSA in LICM is enabled, then this is the maximum "
169	"number of accesses allowed to be present in a loop in order to "
170	"enable memory promotion."));
171
172	namespace llvm {
173	extern cl::opt<bool> ProfcheckDisableMetadataFixes;
174	} // end namespace llvm
175
176	static bool inSubLoop(BasicBlock BB, Loop CurLoop, LoopInfo *LI);
177	static bool isNotUsedOrFoldableInLoop(const Instruction &I, const Loop *CurLoop,
178	const LoopSafetyInfo *SafetyInfo,
179	TargetTransformInfo *TTI,
180	bool &FoldableInLoop, bool LoopNestMode);
181	static void hoist(Instruction &I, const DominatorTree DT, const* Loop *CurLoop,
182	BasicBlock Dest, ICFLoopSafetyInfo SafetyInfo,
183	MemorySSAUpdater &MSSAU, ScalarEvolution *SE,
184	OptimizationRemarkEmitter *ORE);
185	static bool sink(Instruction &I, LoopInfo LI, DominatorTree DT,
186	const Loop CurLoop, ICFLoopSafetyInfo SafetyInfo,
187	MemorySSAUpdater &MSSAU, OptimizationRemarkEmitter *ORE);
188	static bool isSafeToExecuteUnconditionally(
189	Instruction &Inst, const DominatorTree DT, const* TargetLibraryInfo *TLI,
190	const Loop CurLoop, const* LoopSafetyInfo *SafetyInfo,
191	OptimizationRemarkEmitter ORE, const* Instruction *CtxI,
192	AssumptionCache AC, bool* AllowSpeculation);
193	static bool noConflictingReadWrites(Instruction I, MemorySSA MSSA,
194	AAResults AA, Loop CurLoop,
195	SinkAndHoistLICMFlags &Flags);
196	static bool pointerInvalidatedByLoop(MemorySSA MSSA, MemoryUse MU,
197	Loop *CurLoop, Instruction &I,
198	SinkAndHoistLICMFlags &Flags,
199	bool InvariantGroup);
200	static bool pointerInvalidatedByBlock(BasicBlock &BB, MemorySSA &MSSA,
201	MemoryUse &MU);
202	/// Aggregates various functions for hoisting computations out of loop.
203	static bool hoistArithmetics(Instruction &I, Loop &L,
204	ICFLoopSafetyInfo &SafetyInfo,
205	MemorySSAUpdater &MSSAU, AssumptionCache *AC,
206	DominatorTree *DT);
207	static bool
208	hoistInsertPastInsert(InsertElementInst Ins, Loop CurLoop, DominatorTree *DT,
209	BasicBlock HoistDest, ICFLoopSafetyInfo SafetyInfo,
210	MemorySSAUpdater &MSSAU, ScalarEvolution *SE,
211	OptimizationRemarkEmitter *ORE,
212	SmallVectorImpl<Instruction *> &HoistedInstructions);
213	static Instruction *cloneInstructionInExitBlock(
214	Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
215	const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU);
216
217	static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
218	MemorySSAUpdater &MSSAU);
219
220	static void moveInstructionBefore(Instruction &I, BasicBlock::iterator Dest,
221	ICFLoopSafetyInfo &SafetyInfo,
222	MemorySSAUpdater &MSSAU, ScalarEvolution *SE);
223
224	static void foreachMemoryAccess(MemorySSA MSSA, Loop L,
225	function_ref<void(Instruction *)> Fn);
226	using PointersAndHasReadsOutsideSet =
227	std::pair<SmallSetVector<Value , `8`>, bool*>;
228	static SmallVector<PointersAndHasReadsOutsideSet, `0`>
229	collectPromotionCandidates(MemorySSA MSSA, AliasAnalysis AA,
230	DominatorTree DT, ICFLoopSafetyInfo SafetyInfo,
231	Loop *L);
232
233	namespace {
234	struct LoopInvariantCodeMotion {
235	bool runOnLoop(Loop L, AAResults AA, LoopInfo LI, DominatorTree DT,
236	AssumptionCache AC, TargetLibraryInfo TLI,
237	TargetTransformInfo TTI, ScalarEvolution SE, MemorySSA *MSSA,
238	OptimizationRemarkEmitter ORE, bool* LoopNestMode = false);
239
240	LoopInvariantCodeMotion(unsigned LicmMssaOptCap,
241	unsigned LicmMssaNoAccForPromotionCap,
242	bool LicmAllowSpeculation)
243	: LicmMssaOptCap(LicmMssaOptCap),
244	LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
245	LicmAllowSpeculation(LicmAllowSpeculation) {}
246
247	private:
248	unsigned LicmMssaOptCap;
249	unsigned LicmMssaNoAccForPromotionCap;
250	bool LicmAllowSpeculation;
251	};
252
253	struct LegacyLICMPass : public LoopPass {
254	static char ID; // Pass identification, replacement for typeid
255	LegacyLICMPass(
256	unsigned LicmMssaOptCap = SetLicmMssaOptCap,
257	unsigned LicmMssaNoAccForPromotionCap = SetLicmMssaNoAccForPromotionCap,
258	bool LicmAllowSpeculation = true)
259	: LoopPass (ID), LICM (LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
260	LicmAllowSpeculation) {
261	initializeLegacyLICMPassPass(*PassRegistry::getPassRegistry());
262	}
263
264	bool runOnLoop(Loop *L, LPPassManager &LPM) override {
265	if (skipLoop(L))
266	return false;
267
268	LLVM_DEBUG(dbgs() << "Perform LICM on Loop with header at block "
269	<< L->getHeader()->getNameOrAsOperand() << "\n");
270
271	Function *F = L->getHeader()->getParent();
272
273	auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
274	MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
275	// For the old PM, we can't use OptimizationRemarkEmitter as an analysis
276	// pass. Function analyses need to be preserved across loop transformations
277	// but ORE cannot be preserved (see comment before the pass definition).
278	OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
279	return LICM.runOnLoop(
280	L, AA: &getAnalysis<AAResultsWrapperPass>().getAAResults(),
281	LI: &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
282	DT: &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
283	AC: &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F&: *F),
284	TLI: &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F: *F),
285	TTI: &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F: *F),
286	SE: SE ? &SE->getSE() : nullptr, MSSA, ORE: &ORE);
287	}
288
289	/// This transformation requires natural loop information & requires that
290	/// loop preheaders be inserted into the CFG...
291	///
292	void getAnalysisUsage(AnalysisUsage &AU) const override {
293	AU.addPreserved<DominatorTreeWrapperPass>();
294	AU.addPreserved<LoopInfoWrapperPass>();
295	AU.addRequired<TargetLibraryInfoWrapperPass>();
296	AU.addRequired<MemorySSAWrapperPass>();
297	AU.addPreserved<MemorySSAWrapperPass>();
298	AU.addRequired<TargetTransformInfoWrapperPass>();
299	AU.addRequired<AssumptionCacheTracker>();
300	getLoopAnalysisUsage(AU);
301	LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
302	AU.addPreserved<LazyBlockFrequencyInfoPass>();
303	AU.addPreserved<LazyBranchProbabilityInfoPass>();
304	}
305
306	private:
307	LoopInvariantCodeMotion LICM;
308	};
309	} // namespace
310
311	PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM,
312	LoopStandardAnalysisResults &AR, LPMUpdater &) {
313	if (!AR.MSSA)
314	reportFatalUsageError(reason: "LICM requires MemorySSA (loop-mssa)");
315
316	// For the new PM, we also can't use OptimizationRemarkEmitter as an analysis
317	// pass. Function analyses need to be preserved across loop transformations
318	// but ORE cannot be preserved (see comment before the pass definition).
319	OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
320
321	LoopInvariantCodeMotion LICM(Opts.MssaOptCap, Opts.MssaNoAccForPromotionCap,
322	Opts.AllowSpeculation);
323	if (!LICM.runOnLoop(L: &L, AA: &AR.AA, LI: &AR.LI, DT: &AR.DT, AC: &AR.AC, TLI: &AR.TLI, TTI: &AR.TTI,
324	SE: &AR.SE, MSSA: AR.MSSA, ORE: &ORE))
325	return PreservedAnalyses::all();
326
327	auto PA = getLoopPassPreservedAnalyses();
328	PA.preserve<MemorySSAAnalysis>();
329
330	return PA;
331	}
332
333	void LICMPass::printPipeline(
334	raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
335	static_cast<PassInfoMixin<LICMPass> >(this*)->printPipeline(
336	OS, MapClassName2PassName);
337
338	OS << `'<'`;
339	OS << (Opts.AllowSpeculation ? "" : "no-") << "allowspeculation";
340	OS << `'>'`;
341	}
342
343	PreservedAnalyses LNICMPass::run(LoopNest &LN, LoopAnalysisManager &AM,
344	LoopStandardAnalysisResults &AR,
345	LPMUpdater &) {
346	if (!AR.MSSA)
347	reportFatalUsageError(reason: "LNICM requires MemorySSA (loop-mssa)");
348
349	// For the new PM, we also can't use OptimizationRemarkEmitter as an analysis
350	// pass. Function analyses need to be preserved across loop transformations
351	// but ORE cannot be preserved (see comment before the pass definition).
352	OptimizationRemarkEmitter ORE(LN.getParent());
353
354	LoopInvariantCodeMotion LICM(Opts.MssaOptCap, Opts.MssaNoAccForPromotionCap,
355	Opts.AllowSpeculation);
356
357	Loop &OutermostLoop = LN.getOutermostLoop();
358	bool Changed = LICM.runOnLoop(L: &OutermostLoop, AA: &AR.AA, LI: &AR.LI, DT: &AR.DT, AC: &AR.AC,
359	TLI: &AR.TLI, TTI: &AR.TTI, SE: &AR.SE, MSSA: AR.MSSA, ORE: &ORE, LoopNestMode: true);
360
361	if (!Changed)
362	return PreservedAnalyses::all();
363
364	auto PA = getLoopPassPreservedAnalyses();
365
366	PA.preserve<DominatorTreeAnalysis>();
367	PA.preserve<LoopAnalysis>();
368	PA.preserve<MemorySSAAnalysis>();
369
370	return PA;
371	}
372
373	void LNICMPass::printPipeline(
374	raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
375	static_cast<PassInfoMixin<LNICMPass> >(this*)->printPipeline(
376	OS, MapClassName2PassName);
377
378	OS << `'<'`;
379	OS << (Opts.AllowSpeculation ? "" : "no-") << "allowspeculation";
380	OS << `'>'`;
381	}
382
383	char LegacyLICMPass::ID = `0`;
384	INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
385	false, false)
386	INITIALIZE_PASS_DEPENDENCY(LoopPass)
387	INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
388	INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
389	INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
390	INITIALIZE_PASS_DEPENDENCY(LazyBFIPass)
391	INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
392	false)
393
394	Pass llvm::createLICMPass() { return* new LegacyLICMPass (); }
395
396	llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags(bool IsSink, Loop &L,
397	MemorySSA &MSSA)
398	: SinkAndHoistLICMFlags (SetLicmMssaOptCap, SetLicmMssaNoAccForPromotionCap,
399	IsSink, L, MSSA) {}
400
401	llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags(
402	unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink,
403	Loop &L, MemorySSA &MSSA)
404	: LicmMssaOptCap(LicmMssaOptCap),
405	LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
406	IsSink(IsSink) {
407	unsigned AccessCapCount = `0`;
408	for (auto *BB : L.getBlocks())
409	if (const auto *Accesses = MSSA.getBlockAccesses(BB))
410	for (const auto &MA : *Accesses) {
411	(void)MA;
412	++AccessCapCount;
413	if (AccessCapCount > LicmMssaNoAccForPromotionCap) {
414	NoOfMemAccTooLarge = true;
415	return;
416	}
417	}
418	}
419
420	/// Hoist expressions out of the specified loop. Note, alias info for inner
421	/// loop is not preserved so it is not a good idea to run LICM multiple
422	/// times on one loop.
423	bool LoopInvariantCodeMotion::runOnLoop(Loop L, AAResults AA, LoopInfo *LI,
424	DominatorTree DT, AssumptionCache AC,
425	TargetLibraryInfo *TLI,
426	TargetTransformInfo *TTI,
427	ScalarEvolution SE, MemorySSA MSSA,
428	OptimizationRemarkEmitter *ORE,
429	bool LoopNestMode) {
430	bool Changed = false;
431
432	assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
433
434	// If this loop has metadata indicating that LICM is not to be performed then
435	// just exit.
436	if (hasDisableLICMTransformsHint(L)) {
437	return false;
438	}
439
440	// Don't sink stores from loops with coroutine suspend instructions.
441	// LICM would sink instructions into the default destination of
442	// the coroutine switch. The default destination of the switch is to
443	// handle the case where the coroutine is suspended, by which point the
444	// coroutine frame may have been destroyed. No instruction can be sunk there.
445	// FIXME: This would unfortunately hurt the performance of coroutines, however
446	// there is currently no general solution for this. Similar issues could also
447	// potentially happen in other passes where instructions are being moved
448	// across that edge.
449	bool HasCoroSuspendInst = llvm::any_of(Range: L->getBlocks(), P: [](BasicBlock *BB) {
450	using namespace PatternMatch;
451	return any_of(Range: make_pointer_range(Range&: *BB),
452	P: match_fn(P: m_Intrinsic<Intrinsic::coro_suspend>()));
453	});
454
455	MemorySSAUpdater MSSAU(MSSA);
456	SinkAndHoistLICMFlags Flags(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
457	/IsSink=/true, L, MSSA);
458
459	// Get the preheader block to move instructions into...
460	BasicBlock *Preheader = L->getLoopPreheader();
461
462	// Compute loop safety information.
463	ICFLoopSafetyInfo SafetyInfo;
464	SafetyInfo.computeLoopSafetyInfo(CurLoop: L);
465
466	// We want to visit all of the instructions in this loop... that are not parts
467	// of our subloops (they have already had their invariants hoisted out of
468	// their loop, into this loop, so there is no need to process the BODIES of
469	// the subloops).
470	//
471	// Traverse the body of the loop in depth first order on the dominator tree so
472	// that we are guaranteed to see definitions before we see uses. This allows
473	// us to sink instructions in one pass, without iteration. After sinking
474	// instructions, we perform another pass to hoist them out of the loop.
475	if (L->hasDedicatedExits())
476	Changed \|=
477	LoopNestMode
478	? sinkRegionForLoopNest(DT->getNode(BB: L->getHeader()), AA, LI, DT,
479	TLI, TTI, L, MSSAU, &SafetyInfo, Flags, ORE)
480	: sinkRegion(DT->getNode(BB: L->getHeader()), AA, LI, DT, TLI, TTI, CurLoop: L,
481	MSSAU, &SafetyInfo, Flags, ORE);
482	Flags.setIsSink(false);
483	if (Preheader)
484	Changed \|= hoistRegion(DT->getNode(BB: L->getHeader()), AA, LI, DT, AC, TLI, L,
485	MSSAU, SE, &SafetyInfo, Flags, ORE, LoopNestMode,
486	AllowSpeculation: LicmAllowSpeculation);
487
488	// Now that all loop invariants have been removed from the loop, promote any
489	// memory references to scalars that we can.
490	// Don't sink stores from loops without dedicated block exits. Exits
491	// containing indirect branches are not transformed by loop simplify,
492	// make sure we catch that. An additional load may be generated in the
493	// preheader for SSA updater, so also avoid sinking when no preheader
494	// is available.
495	if (!DisablePromotion && Preheader && L->hasDedicatedExits() &&
496	!Flags.tooManyMemoryAccesses() && !HasCoroSuspendInst) {
497	// Figure out the loop exits and their insertion points
498	SmallVector<BasicBlock *, `8`> ExitBlocks;
499	L->getUniqueExitBlocks(ExitBlocks);
500
501	// We can't insert into a catchswitch.
502	bool HasCatchSwitch = llvm::any_of(Range&: ExitBlocks, P: [](BasicBlock *Exit) {
503	return isa<CatchSwitchInst>(Val: Exit->getTerminator());
504	});
505
506	if (!HasCatchSwitch) {
507	SmallVector<BasicBlock::iterator, `8`> InsertPts;
508	SmallVector<MemoryAccess *, `8`> MSSAInsertPts;
509	InsertPts.reserve(N: ExitBlocks.size());
510	MSSAInsertPts.reserve(N: ExitBlocks.size());
511	for (BasicBlock *ExitBlock : ExitBlocks) {
512	InsertPts.push_back(Elt: ExitBlock->getFirstInsertionPt());
513	MSSAInsertPts.push_back(Elt: nullptr);
514	}
515
516	PredIteratorCache PIC;
517
518	// Promoting one set of accesses may make the pointers for another set
519	// loop invariant, so run this in a loop.
520	bool Promoted = false;
521	bool LocalPromoted;
522	do {
523	LocalPromoted = false;
524	for (auto [PointerMustAliases, HasReadsOutsideSet] :
525	collectPromotionCandidates(MSSA, AA, DT, SafetyInfo: &SafetyInfo, L)) {
526	LocalPromoted \|= promoteLoopAccessesToScalars(
527	PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts, PIC, LI,
528	DT, AC, TLI, TTI, L, MSSAU, &SafetyInfo, ORE,
529	AllowSpeculation: LicmAllowSpeculation, HasReadsOutsideSet);
530	}
531	Promoted \|= LocalPromoted;
532	} while (LocalPromoted);
533
534	// Once we have promoted values across the loop body we have to
535	// recursively reform LCSSA as any nested loop may now have values defined
536	// within the loop used in the outer loop.
537	// FIXME: This is really heavy handed. It would be a bit better to use an
538	// SSAUpdater strategy during promotion that was LCSSA aware and reformed
539	// it as it went.
540	if (Promoted)
541	formLCSSARecursively(L&: L, DT: DT, LI, SE);
542
543	Changed \|= Promoted;
544	}
545	}
546
547	// Check that neither this loop nor its parent have had LCSSA broken. LICM is
548	// specifically moving instructions across the loop boundary and so it is
549	// especially in need of basic functional correctness checking here.
550	assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
551	assert((L->isOutermost() \|\| L->getParentLoop()->isLCSSAForm(*DT)) &&
552	"Parent loop not left in LCSSA form after LICM!");
553
554	if (VerifyMemorySSA)
555	MSSA->verifyMemorySSA();
556
557	if (Changed && SE)
558	SE->forgetLoopDispositions();
559	return Changed;
560	}
561
562	/// Walk the specified region of the CFG (defined by all blocks dominated by
563	/// the specified block, and that are in the current loop) in reverse depth
564	/// first order w.r.t the DominatorTree. This allows us to visit uses before
565	/// definitions, allowing us to sink a loop body in one pass without iteration.
566	///
567	bool llvm::sinkRegion(DomTreeNode N, AAResults AA, LoopInfo *LI,
568	DominatorTree DT, TargetLibraryInfo TLI,
569	TargetTransformInfo TTI, Loop CurLoop,
570	MemorySSAUpdater &MSSAU, ICFLoopSafetyInfo *SafetyInfo,
571	SinkAndHoistLICMFlags &Flags,
572	OptimizationRemarkEmitter ORE, Loop OutermostLoop) {
573
574	// Verify inputs.
575	assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
576	CurLoop != nullptr && SafetyInfo != nullptr &&
577	"Unexpected input to sinkRegion.");
578
579	// We want to visit children before parents. We will enqueue all the parents
580	// before their children in the worklist and process the worklist in reverse
581	// order.
582	SmallVector<BasicBlock *, `16`> Worklist =
583	collectChildrenInLoop(DT, N, CurLoop);
584
585	bool Changed = false;
586	for (BasicBlock *BB : reverse(C&: Worklist)) {
587	// subloop (which would already have been processed).
588	if (inSubLoop(BB, CurLoop, LI))
589	continue;
590
591	for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
592	Instruction &I = *--II;
593
594	// The instruction is not used in the loop if it is dead. In this case,
595	// we just delete it instead of sinking it.
596	if (isInstructionTriviallyDead(I: &I, TLI)) {
597	LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << `'\n'`);
598	salvageKnowledge(I: &I);
599	salvageDebugInfo(I);
600	++II;
601	eraseInstruction(I, SafetyInfo&: *SafetyInfo, MSSAU);
602	Changed = true;
603	continue;
604	}
605
606	// Check to see if we can sink this instruction to the exit blocks
607	// of the loop. We can do this if the all users of the instruction are
608	// outside of the loop. In this case, it doesn't even matter if the
609	// operands of the instruction are loop invariant.
610	//
611	bool FoldableInLoop = false;
612	bool LoopNestMode = OutermostLoop != nullptr;
613	if (!I.mayHaveSideEffects() &&
614	isNotUsedOrFoldableInLoop(I, CurLoop: LoopNestMode ? OutermostLoop : CurLoop,
615	SafetyInfo, TTI, FoldableInLoop,
616	LoopNestMode) &&
617	canSinkOrHoistInst(I, AA, DT, CurLoop, MSSAU, TargetExecutesOncePerLoop: true, LICMFlags&: Flags, ORE)) {
618	if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
619	if (!FoldableInLoop) {
620	++II;
621	salvageDebugInfo(I);
622	eraseInstruction(I, SafetyInfo&: *SafetyInfo, MSSAU);
623	}
624	Changed = true;
625	}
626	}
627	}
628	}
629	if (VerifyMemorySSA)
630	MSSAU.getMemorySSA()->verifyMemorySSA();
631	return Changed;
632	}
633
634	bool llvm::sinkRegionForLoopNest(DomTreeNode N, AAResults AA, LoopInfo *LI,
635	DominatorTree DT, TargetLibraryInfo TLI,
636	TargetTransformInfo TTI, Loop CurLoop,
637	MemorySSAUpdater &MSSAU,
638	ICFLoopSafetyInfo *SafetyInfo,
639	SinkAndHoistLICMFlags &Flags,
640	OptimizationRemarkEmitter *ORE) {
641
642	bool Changed = false;
643	SmallPriorityWorklist<Loop *, `4`> Worklist;
644	Worklist.insert(X: CurLoop);
645	appendLoopsToWorklist(*CurLoop, Worklist);
646	while (!Worklist.empty()) {
647	Loop *L = Worklist.pop_back_val();
648	Changed \|= sinkRegion(N: DT->getNode(BB: L->getHeader()), AA, LI, DT, TLI, TTI, CurLoop: L,
649	MSSAU, SafetyInfo, Flags, ORE, OutermostLoop: CurLoop);
650	}
651	return Changed;
652	}
653
654	namespace {
655	// This is a helper class for hoistRegion to make it able to hoist control flow
656	// in order to be able to hoist phis. The way this works is that we initially
657	// start hoisting to the loop preheader, and when we see a loop invariant branch
658	// we make note of this. When we then come to hoist an instruction that's
659	// conditional on such a branch we duplicate the branch and the relevant control
660	// flow, then hoist the instruction into the block corresponding to its original
661	// block in the duplicated control flow.
662	class ControlFlowHoister {
663	private:
664	// Information about the loop we are hoisting from
665	LoopInfo *LI;
666	DominatorTree *DT;
667	Loop *CurLoop;
668	MemorySSAUpdater &MSSAU;
669
670	// A map of blocks in the loop to the block their instructions will be hoisted
671	// to.
672	DenseMap<BasicBlock , BasicBlock > HoistDestinationMap;
673
674	// The branches that we can hoist, mapped to the block that marks a
675	// convergence point of their control flow.
676	DenseMap<CondBrInst , BasicBlock > HoistableBranches;
677
678	public:
679	ControlFlowHoister(LoopInfo LI, DominatorTree DT, Loop *CurLoop,
680	MemorySSAUpdater &MSSAU)
681	: LI(LI), DT(DT), CurLoop(CurLoop), MSSAU(MSSAU) {}
682
683	void registerPossiblyHoistableBranch(CondBrInst *BI) {
684	// We can only hoist conditional branches with loop invariant operands.
685	if (!ControlFlowHoisting \|\| !CurLoop->hasLoopInvariantOperands(I: BI))
686	return;
687
688	// The branch destinations need to be in the loop, and we don't gain
689	// anything by duplicating conditional branches with duplicate successors,
690	// as it's essentially the same as an unconditional branch.
691	BasicBlock *TrueDest = BI->getSuccessor(i: `0`);
692	BasicBlock *FalseDest = BI->getSuccessor(i: `1`);
693	if (!CurLoop->contains(BB: TrueDest) \|\| !CurLoop->contains(BB: FalseDest) \|\|
694	TrueDest == FalseDest)
695	return;
696
697	// We can hoist BI if one branch destination is the successor of the other,
698	// or both have common successor which we check by seeing if the
699	// intersection of their successors is non-empty.
700	// TODO: This could be expanded to allowing branches where both ends
701	// eventually converge to a single block.
702	SmallPtrSet<BasicBlock *, `4`> TrueDestSucc(llvm::from_range,
703	successors(BB: TrueDest));
704	SmallPtrSet<BasicBlock *, `4`> FalseDestSucc(llvm::from_range,
705	successors(BB: FalseDest));
706	BasicBlock CommonSucc = nullptr*;
707	if (TrueDestSucc.count(Ptr: FalseDest)) {
708	CommonSucc = FalseDest;
709	} else if (FalseDestSucc.count(Ptr: TrueDest)) {
710	CommonSucc = TrueDest;
711	} else {
712	set_intersect(S1&: TrueDestSucc, S2: FalseDestSucc);
713	// If there's one common successor use that.
714	if (TrueDestSucc.size() == `1`)
715	CommonSucc = *TrueDestSucc.begin();
716	// If there's more than one pick whichever appears first in the block list
717	// (we can't use the value returned by TrueDestSucc.begin() as it's
718	// unpredicatable which element gets returned).
719	else if (!TrueDestSucc.empty()) {
720	Function *F = TrueDest->getParent();
721	auto IsSucc = [&](BasicBlock &BB) { return TrueDestSucc.count(Ptr: &BB); };
722	auto It = llvm::find_if(Range&: *F, P: IsSucc);
723	assert(It != F->end() && "Could not find successor in function");
724	CommonSucc = &*It;
725	}
726	}
727	// The common successor has to be dominated by the branch, as otherwise
728	// there will be some other path to the successor that will not be
729	// controlled by this branch so any phi we hoist would be controlled by the
730	// wrong condition. This also takes care of avoiding hoisting of loop back
731	// edges.
732	// TODO: In some cases this could be relaxed if the successor is dominated
733	// by another block that's been hoisted and we can guarantee that the
734	// control flow has been replicated exactly.
735	if (CommonSucc && DT->dominates(Def: BI, BB: CommonSucc))
736	HoistableBranches [BI] = CommonSucc;
737	}
738
739	bool canHoistPHI(PHINode *PN) {
740	// The phi must have loop invariant operands.
741	if (!ControlFlowHoisting \|\| !CurLoop->hasLoopInvariantOperands(I: PN))
742	return false;
743	// We can hoist phis if the block they are in is the target of hoistable
744	// branches which cover all of the predecessors of the block.
745	BasicBlock *BB = PN->getParent();
746	SmallPtrSet<BasicBlock *, `8`> PredecessorBlocks(llvm::from_range,
747	predecessors(BB));
748	// If we have less predecessor blocks than predecessors then the phi will
749	// have more than one incoming value for the same block which we can't
750	// handle.
751	// TODO: This could be handled be erasing some of the duplicate incoming
752	// values.
753	if (PredecessorBlocks.size() != pred_size(BB))
754	return false;
755	for (auto &Pair : HoistableBranches) {
756	if (Pair.second == BB) {
757	// Which blocks are predecessors via this branch depends on if the
758	// branch is triangle-like or diamond-like.
759	if (Pair.first->getSuccessor(i: `0`) == BB) {
760	PredecessorBlocks.erase(Ptr: Pair.first->getParent());
761	PredecessorBlocks.erase(Ptr: Pair.first->getSuccessor(i: `1`));
762	} else if (Pair.first->getSuccessor(i: `1`) == BB) {
763	PredecessorBlocks.erase(Ptr: Pair.first->getParent());
764	PredecessorBlocks.erase(Ptr: Pair.first->getSuccessor(i: `0`));
765	} else {
766	PredecessorBlocks.erase(Ptr: Pair.first->getSuccessor(i: `0`));
767	PredecessorBlocks.erase(Ptr: Pair.first->getSuccessor(i: `1`));
768	}
769	}
770	}
771	// PredecessorBlocks will now be empty if for every predecessor of BB we
772	// found a hoistable branch source.
773	return PredecessorBlocks.empty();
774	}
775
776	BasicBlock getOrCreateHoistedBlock(BasicBlock BB) {
777	if (!ControlFlowHoisting)
778	return CurLoop->getLoopPreheader();
779	// If BB has already been hoisted, return that
780	if (auto It = HoistDestinationMap.find(Val: BB); It != HoistDestinationMap.end())
781	return It ->second;
782
783	// Check if this block is conditional based on a pending branch
784	auto HasBBAsSuccessor =
785	[&](DenseMap<CondBrInst , BasicBlock >::value_type &Pair) {
786	return BB != Pair.second && (Pair.first->getSuccessor(i: `0`) == BB \|\|
787	Pair.first->getSuccessor(i: `1`) == BB);
788	};
789	auto It = llvm::find_if(Range&: HoistableBranches, P: HasBBAsSuccessor);
790
791	// If not involved in a pending branch, hoist to preheader
792	BasicBlock *InitialPreheader = CurLoop->getLoopPreheader();
793	if (It == HoistableBranches.end()) {
794	LLVM_DEBUG(dbgs() << "LICM using "
795	<< InitialPreheader->getNameOrAsOperand()
796	<< " as hoist destination for "
797	<< BB->getNameOrAsOperand() << "\n");
798	HoistDestinationMap [BB] = InitialPreheader;
799	return InitialPreheader;
800	}
801	CondBrInst *BI = It ->first;
802	assert(std::none_of(std::next(It), HoistableBranches.end(),
803	HasBBAsSuccessor) &&
804	"BB is expected to be the target of at most one branch");
805
806	LLVMContext &C = BB->getContext();
807	BasicBlock *TrueDest = BI->getSuccessor(i: `0`);
808	BasicBlock *FalseDest = BI->getSuccessor(i: `1`);
809	BasicBlock *CommonSucc = HoistableBranches [BI];
810	BasicBlock *HoistTarget = getOrCreateHoistedBlock(BB: BI->getParent());
811
812	// Create hoisted versions of blocks that currently don't have them
813	auto CreateHoistedBlock = [&](BasicBlock *Orig) {
814	auto [It, Inserted] = HoistDestinationMap.try_emplace(Key: Orig);
815	if (!Inserted)
816	return It ->second;
817	BasicBlock *New =
818	BasicBlock::Create(Context&: C, Name: Orig->getName() + ".licm", Parent: Orig->getParent());
819	It ->second = New;
820	DT->addNewBlock(BB: New, DomBB: HoistTarget);
821	if (CurLoop->getParentLoop())
822	CurLoop->getParentLoop()->addBasicBlockToLoop(NewBB: New, LI&: *LI);
823	++NumCreatedBlocks;
824	LLVM_DEBUG(dbgs() << "LICM created " << New->getName()
825	<< " as hoist destination for " << Orig->getName()
826	<< "\n");
827	return New;
828	};
829	BasicBlock *HoistTrueDest = CreateHoistedBlock(TrueDest);
830	BasicBlock *HoistFalseDest = CreateHoistedBlock(FalseDest);
831	BasicBlock *HoistCommonSucc = CreateHoistedBlock(CommonSucc);
832
833	// Link up these blocks with branches.
834	if (!HoistCommonSucc->hasTerminator()) {
835	// The new common successor we've generated will branch to whatever that
836	// hoist target branched to.
837	BasicBlock *TargetSucc = HoistTarget->getSingleSuccessor();
838	assert(TargetSucc && "Expected hoist target to have a single successor");
839	HoistCommonSucc->moveBefore(MovePos: TargetSucc);
840	UncondBrInst::Create(Target: TargetSucc, InsertBefore: HoistCommonSucc);
841	}
842	if (!HoistTrueDest->hasTerminator()) {
843	HoistTrueDest->moveBefore(MovePos: HoistCommonSucc);
844	UncondBrInst::Create(Target: HoistCommonSucc, InsertBefore: HoistTrueDest);
845	}
846	if (!HoistFalseDest->hasTerminator()) {
847	HoistFalseDest->moveBefore(MovePos: HoistCommonSucc);
848	UncondBrInst::Create(Target: HoistCommonSucc, InsertBefore: HoistFalseDest);
849	}
850
851	// If BI is being cloned to what was originally the preheader then
852	// HoistCommonSucc will now be the new preheader.
853	if (HoistTarget == InitialPreheader) {
854	// Phis in the loop header now need to use the new preheader.
855	InitialPreheader->replaceSuccessorsPhiUsesWith(New: HoistCommonSucc);
856	MSSAU.wireOldPredecessorsToNewImmediatePredecessor(
857	Old: HoistTarget->getSingleSuccessor(), New: HoistCommonSucc, Preds: {HoistTarget});
858	// The new preheader dominates the loop header.
859	DomTreeNode *PreheaderNode = DT->getNode(BB: HoistCommonSucc);
860	DomTreeNode *HeaderNode = DT->getNode(BB: CurLoop->getHeader());
861	DT->changeImmediateDominator(N: HeaderNode, NewIDom: PreheaderNode);
862	// The preheader hoist destination is now the new preheader, with the
863	// exception of the hoist destination of this branch.
864	for (auto &Pair : HoistDestinationMap)
865	if (Pair.second == InitialPreheader && Pair.first != BI->getParent())
866	Pair.second = HoistCommonSucc;
867	}
868
869	// Now finally clone BI.
870	auto *NewBI =
871	CondBrInst::Create(Cond: BI->getCondition(), IfTrue: HoistTrueDest, IfFalse: HoistFalseDest,
872	InsertBefore: HoistTarget->getTerminator()->getIterator());
873	HoistTarget->getTerminator()->eraseFromParent();
874	// md_prof should also come from the original branch - since the
875	// condition was hoisted, the branch probabilities shouldn't change.
876	if (!ProfcheckDisableMetadataFixes)
877	NewBI->copyMetadata(SrcInst: *BI, WL: {LLVMContext::MD_prof});
878	// FIXME: Issue #152767: debug info should also be the same as the
879	// original branch, if* the user explicitly indicated that.*
880	NewBI->setDebugLoc(HoistTarget->getTerminator()->getDebugLoc());
881
882	++NumClonedBranches;
883
884	assert(CurLoop->getLoopPreheader() &&
885	"Hoisting blocks should not have destroyed preheader");
886	return HoistDestinationMap [BB];
887	}
888	};
889	} // namespace
890
891	/// Walk the specified region of the CFG (defined by all blocks dominated by
892	/// the specified block, and that are in the current loop) in depth first
893	/// order w.r.t the DominatorTree. This allows us to visit definitions before
894	/// uses, allowing us to hoist a loop body in one pass without iteration.
895	///
896	bool llvm::hoistRegion(DomTreeNode N, AAResults AA, LoopInfo *LI,
897	DominatorTree DT, AssumptionCache AC,
898	TargetLibraryInfo TLI, Loop CurLoop,
899	MemorySSAUpdater &MSSAU, ScalarEvolution *SE,
900	ICFLoopSafetyInfo *SafetyInfo,
901	SinkAndHoistLICMFlags &Flags,
902	OptimizationRemarkEmitter ORE, bool* LoopNestMode,
903	bool AllowSpeculation) {
904	// Verify inputs.
905	assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
906	CurLoop != nullptr && SafetyInfo != nullptr &&
907	"Unexpected input to hoistRegion.");
908
909	ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
910
911	// Keep track of instructions that have been hoisted, as they may need to be
912	// re-hoisted if they end up not dominating all of their uses.
913	SmallVector<Instruction *, `16`> HoistedInstructions;
914
915	// For PHI hoisting to work we need to hoist blocks before their successors.
916	// We can do this by iterating through the blocks in the loop in reverse
917	// post-order.
918	LoopBlocksRPO Worklist(CurLoop);
919	Worklist.perform(LI);
920	bool Changed = false;
921	BasicBlock *Preheader = CurLoop->getLoopPreheader();
922	for (BasicBlock *BB : Worklist) {
923	// Only need to process the contents of this block if it is not part of a
924	// subloop (which would already have been processed).
925	if (!LoopNestMode && inSubLoop(BB, CurLoop, LI))
926	continue;
927
928	for (Instruction &I : llvm::make_early_inc_range(Range&: *BB)) {
929	// Try hoisting the instruction out to the preheader. We can only do
930	// this if all of the operands of the instruction are loop invariant and
931	// if it is safe to hoist the instruction.
932	// TODO: It may be safe to hoist if we are hoisting to a conditional block
933	// and we have accurately duplicated the control flow from the loop header
934	// to that block.
935	if (CurLoop->hasLoopInvariantOperands(I: &I) &&
936	canSinkOrHoistInst(I, AA, DT, CurLoop, MSSAU, TargetExecutesOncePerLoop: true, LICMFlags&: Flags, ORE) &&
937	isSafeToExecuteUnconditionally(Inst&: I, DT, TLI, CurLoop, SafetyInfo, ORE,
938	CtxI: Preheader->getTerminator(), AC,
939	AllowSpeculation)) {
940	hoist(I, DT, CurLoop, Dest: CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
941	MSSAU, SE, ORE);
942	HoistedInstructions.push_back(Elt: &I);
943	Changed = true;
944	continue;
945	}
946
947	if (auto *Ins = dyn_cast<InsertElementInst>(Val: &I))
948	if (hoistInsertPastInsert(Ins, CurLoop, DT,
949	HoistDest: CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
950	MSSAU, SE, ORE, HoistedInstructions)) {
951	Changed = true;
952	continue;
953	}
954
955	// Attempt to remove floating point division out of the loop by
956	// converting it to a reciprocal multiplication.
957	if (I.getOpcode() == Instruction::FDiv && I.hasAllowReciprocal() &&
958	CurLoop->isLoopInvariant(V: I.getOperand(i: `1`))) {
959	auto Divisor = I.getOperand(i: `1`);
960	auto One = llvm::ConstantFP::get(Ty: Divisor->getType(), V: `1.0`);
961	auto ReciprocalDivisor = BinaryOperator::CreateFDiv(V1: One, V2: Divisor);
962	ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
963	SafetyInfo->insertInstructionTo(Inst: ReciprocalDivisor, BB: I.getParent());
964	ReciprocalDivisor->insertBefore(InsertPos: I.getIterator());
965	ReciprocalDivisor->setDebugLoc(I.getDebugLoc());
966
967	auto Product =
968	BinaryOperator::CreateFMul(V1: I.getOperand(i: `0`), V2: ReciprocalDivisor);
969	Product->setFastMathFlags(I.getFastMathFlags());
970	SafetyInfo->insertInstructionTo(Inst: Product, BB: I.getParent());
971	Product->insertAfter(InsertPos: I.getIterator());
972	Product->setDebugLoc(I.getDebugLoc());
973	I.replaceAllUsesWith(V: Product);
974	eraseInstruction(I, SafetyInfo&: *SafetyInfo, MSSAU);
975
976	hoist(I&: *ReciprocalDivisor, DT, CurLoop, Dest: CFH.getOrCreateHoistedBlock(BB),
977	SafetyInfo, MSSAU, SE, ORE);
978	HoistedInstructions.push_back(Elt: ReciprocalDivisor);
979	Changed = true;
980	continue;
981	}
982
983	auto IsInvariantStart = [&](Instruction &I) {
984	using namespace PatternMatch;
985	return I.use_empty() &&
986	match(V: &I, P: m_Intrinsic<Intrinsic::invariant_start>());
987	};
988	auto MustExecuteWithoutWritesBefore = [&](Instruction &I) {
989	return SafetyInfo->isGuaranteedToExecute(Inst: I, DT, CurLoop) &&
990	SafetyInfo->doesNotWriteMemoryBefore(I, CurLoop);
991	};
992	if ((IsInvariantStart (I) \|\| isGuard(U: &I)) &&
993	CurLoop->hasLoopInvariantOperands(I: &I) &&
994	MustExecuteWithoutWritesBefore (I)) {
995	hoist(I, DT, CurLoop, Dest: CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
996	MSSAU, SE, ORE);
997	HoistedInstructions.push_back(Elt: &I);
998	Changed = true;
999	continue;
1000	}
1001
1002	if (PHINode *PN = dyn_cast<PHINode>(Val: &I)) {
1003	if (CFH.canHoistPHI(PN)) {
1004	// Redirect incoming blocks first to ensure that we create hoisted
1005	// versions of those blocks before we hoist the phi.
1006	for (unsigned int i = `0`; i < PN->getNumIncomingValues(); ++i)
1007	PN->setIncomingBlock(
1008	i, BB: CFH.getOrCreateHoistedBlock(BB: PN->getIncomingBlock(i)));
1009	hoist(I&: *PN, DT, CurLoop, Dest: CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
1010	MSSAU, SE, ORE);
1011	assert(DT->dominates(PN, BB) && "Conditional PHIs not expected");
1012	Changed = true;
1013	continue;
1014	}
1015	}
1016
1017	// Try to reassociate instructions so that part of computations can be
1018	// done out of loop.
1019	if (hoistArithmetics(I, L&: CurLoop, SafetyInfo&: SafetyInfo, MSSAU, AC, DT)) {
1020	Changed = true;
1021	continue;
1022	}
1023
1024	// Remember possibly hoistable branches so we can actually hoist them
1025	// later if needed.
1026	if (CondBrInst *BI = dyn_cast<CondBrInst>(Val: &I))
1027	CFH.registerPossiblyHoistableBranch(BI);
1028	}
1029	}
1030
1031	// If we hoisted instructions to a conditional block they may not dominate
1032	// their uses that weren't hoisted (such as phis where some operands are not
1033	// loop invariant). If so make them unconditional by moving them to their
1034	// immediate dominator. We iterate through the instructions in reverse order
1035	// which ensures that when we rehoist an instruction we rehoist its operands,
1036	// and also keep track of where in the block we are rehoisting to make sure
1037	// that we rehoist instructions before the instructions that use them.
1038	Instruction HoistPoint = nullptr*;
1039	if (ControlFlowHoisting) {
1040	for (Instruction *I : reverse(C&: HoistedInstructions)) {
1041	if (!llvm::all_of(Range: I->uses(),
1042	P: [&](Use &U) { return DT->dominates(Def: I, U); })) {
1043	BasicBlock *Dominator =
1044	DT->getNode(BB: I->getParent())->getIDom()->getBlock();
1045	if (!HoistPoint \|\| !DT->dominates(A: HoistPoint->getParent(), B: Dominator)) {
1046	if (HoistPoint)
1047	assert(DT->dominates(Dominator, HoistPoint->getParent()) &&
1048	"New hoist point expected to dominate old hoist point");
1049	HoistPoint = Dominator->getTerminator();
1050	}
1051	LLVM_DEBUG(dbgs() << "LICM rehoisting to "
1052	<< HoistPoint->getParent()->getNameOrAsOperand()
1053	<< ": " << *I << "\n");
1054	moveInstructionBefore(I&: I, Dest: HoistPoint->getIterator(), SafetyInfo&: SafetyInfo, MSSAU,
1055	SE);
1056	HoistPoint = I;
1057	Changed = true;
1058	}
1059	}
1060	}
1061	if (VerifyMemorySSA)
1062	MSSAU.getMemorySSA()->verifyMemorySSA();
1063
1064	// Now that we've finished hoisting make sure that LI and DT are still
1065	// valid.
1066	#ifdef EXPENSIVE_CHECKS
1067	if (Changed) {
1068	assert(DT->verify(DominatorTree::VerificationLevel::Fast) &&
1069	"Dominator tree verification failed");
1070	LI->verify();
1071	}
1072	#endif
1073
1074	return Changed;
1075	}
1076
1077	static std::optional<uint64_t>
1078	getConstantInsertionIndex(InsertElementInst *Ins) {
1079	// Must have constant insertion lane.
1080	auto *InsertedIdxCI = dyn_cast<ConstantInt>(Val: Ins->getOperand(i_nocapture: `2`));
1081	if (!InsertedIdxCI)
1082	return std::nullopt;
1083	auto *VecTy = cast<VectorType>(Val: Ins->getType());
1084
1085	// Avoid hoisting past out of bounds inserts.
1086	if (InsertedIdxCI->isNegative() \|\|
1087	InsertedIdxCI->getValue().uge(
1088	RHS: VecTy->getElementCount().getKnownMinValue()))
1089	return std::nullopt;
1090	return InsertedIdxCI->getValue().getLimitedValue();
1091	}
1092
1093	static bool
1094	hoistInsertPastInsert(InsertElementInst Ins, Loop CurLoop, DominatorTree *DT,
1095	BasicBlock HoistDest, ICFLoopSafetyInfo SafetyInfo,
1096	MemorySSAUpdater &MSSAU, ScalarEvolution *SE,
1097	OptimizationRemarkEmitter *ORE,
1098	SmallVectorImpl<Instruction *> &HoistedInstructions) {
1099	// Canonicalize:
1100	// %inner = insertelement %base, %variant, C1
1101	// %outer = insertelement %inner, %invariant, C2
1102	// into:
1103	// %outer = insertelement %base, %invariant, C2
1104	// %inner = insertelement %outer, %variant, C1
1105	// so we can hoist %outer
1106
1107	// The instruction we are hoisting must have invariant insertion data
1108	Value *InsertedElt = Ins->getOperand(i_nocapture: `1`);
1109	if (!CurLoop->isLoopInvariant(V: InsertedElt))
1110	return false;
1111
1112	std::optional<uint64_t> HoistIdx = getConstantInsertionIndex(Ins);
1113	if (!HoistIdx)
1114	return false;
1115
1116	InsertElementInst *Inner = Ins;
1117	while (!CurLoop->isLoopInvariant(V: Inner->getOperand(i_nocapture: `0`))) {
1118	// If the inner value isn't invariant, check to see if it is another insert
1119	// All instructions in the chain must be in the same basic block
1120	auto *InnerIns = dyn_cast<InsertElementInst>(Val: Inner->getOperand(i_nocapture: `0`));
1121	if (!InnerIns \|\| InnerIns->getParent() != Ins->getParent())
1122	return false;
1123
1124	// Make sure not hoisting past insertions into the same lane
1125	std::optional<uint64_t> InsertIdx = getConstantInsertionIndex(Ins: InnerIns);
1126	if (!InsertIdx \|\| InsertIdx == HoistIdx)
1127	return false;
1128
1129	// Instruction being hoisted past must only have one use
1130	if (!InnerIns->hasOneUse())
1131	return false;
1132
1133	Inner = InnerIns;
1134	}
1135
1136	// Base case of `insertelement <4 x i8> %invar0, i8 %invar1, i32 2` handled in
1137	// base LICM logic
1138	if (Inner == Ins)
1139	return false;
1140
1141	Ins->replaceAllUsesWith(V: Ins->getOperand(i_nocapture: `0`));
1142	Ins->moveBefore(InsertPos: Inner->getIterator());
1143	Ins->setOperand(i_nocapture: `0`, Val_nocapture: Inner->getOperand(i_nocapture: `0`));
1144	Inner->setOperand(i_nocapture: `0`, Val_nocapture: Ins);
1145	hoist(I&: *Ins, DT, CurLoop, Dest: HoistDest, SafetyInfo, MSSAU, SE, ORE);
1146	HoistedInstructions.push_back(Elt: Ins);
1147	return true;
1148	}
1149
1150	// Return true if LI is invariant within scope of the loop. LI is invariant if
1151	// CurLoop is dominated by an invariant.start representing the same memory
1152	// location and size as the memory location LI loads from, and also the
1153	// invariant.start has no uses.
1154	static bool isLoadInvariantInLoop(LoadInst LI, DominatorTree DT,
1155	Loop *CurLoop) {
1156	Value *Addr = LI->getPointerOperand();
1157	const DataLayout &DL = LI->getDataLayout();
1158	const TypeSize LocSizeInBits = DL.getTypeSizeInBits(Ty: LI->getType());
1159
1160	// It is not currently possible for clang to generate an invariant.start
1161	// intrinsic with scalable vector types because we don't support thread local
1162	// sizeless types and we don't permit sizeless types in structs or classes.
1163	// Furthermore, even if support is added for this in future the intrinsic
1164	// itself is defined to have a size of -1 for variable sized objects. This
1165	// makes it impossible to verify if the intrinsic envelops our region of
1166	// interest. For example, both <vscale x 32 x i8> and <vscale x 16 x i8>
1167	// types would have a -1 parameter, but the former is clearly double the size
1168	// of the latter.
1169	if (LocSizeInBits.isScalable())
1170	return false;
1171
1172	// If we've ended up at a global/constant, bail. We shouldn't be looking at
1173	// uselists for non-local Values in a loop pass.
1174	if (isa<Constant>(Val: Addr))
1175	return false;
1176
1177	unsigned UsesVisited = `0`;
1178	// Traverse all uses of the load operand value, to see if invariant.start is
1179	// one of the uses, and whether it dominates the load instruction.
1180	for (auto *U : Addr->users()) {
1181	// Avoid traversing for Load operand with high number of users.
1182	if (++UsesVisited > MaxNumUsesTraversed)
1183	return false;
1184	IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: U);
1185	// If there are escaping uses of invariant.start instruction, the load maybe
1186	// non-invariant.
1187	if (!II \|\| II->getIntrinsicID() != Intrinsic::invariant_start \|\|
1188	!II->use_empty())
1189	continue;
1190	ConstantInt *InvariantSize = cast<ConstantInt>(Val: II->getArgOperand(i: `0`));
1191	// The intrinsic supports having a -1 argument for variable sized objects
1192	// so we should check for that here.
1193	if (InvariantSize->isNegative())
1194	continue;
1195	uint64_t InvariantSizeInBits = InvariantSize->getSExtValue() * `8`;
1196	// Confirm the invariant.start location size contains the load operand size
1197	// in bits. Also, the invariant.start should dominate the load, and we
1198	// should not hoist the load out of a loop that contains this dominating
1199	// invariant.start.
1200	if (LocSizeInBits.getFixedValue() <= InvariantSizeInBits &&
1201	DT->properlyDominates(A: II->getParent(), B: CurLoop->getHeader()))
1202	return true;
1203	}
1204
1205	return false;
1206	}
1207
1208	/// Return true if-and-only-if we know how to (mechanically) both hoist and
1209	/// sink a given instruction out of a loop. Does not address legality
1210	/// concerns such as aliasing or speculation safety.
1211	static bool isHoistableAndSinkableInst(Instruction &I) {
1212	// Only these instructions are hoistable/sinkable.
1213	return (isa<LoadInst>(Val: I) \|\| isa<StoreInst>(Val: I) \|\| isa<CallInst>(Val: I) \|\|
1214	isa<FenceInst>(Val: I) \|\| isa<CastInst>(Val: I) \|\| isa<UnaryOperator>(Val: I) \|\|
1215	isa<BinaryOperator>(Val: I) \|\| isa<SelectInst>(Val: I) \|\|
1216	isa<GetElementPtrInst>(Val: I) \|\| isa<CmpInst>(Val: I) \|\|
1217	isa<InsertElementInst>(Val: I) \|\| isa<ExtractElementInst>(Val: I) \|\|
1218	isa<ShuffleVectorInst>(Val: I) \|\| isa<ExtractValueInst>(Val: I) \|\|
1219	isa<InsertValueInst>(Val: I) \|\| isa<FreezeInst>(Val: I));
1220	}
1221
1222	/// Return true if I is the only Instruction with a MemoryAccess in L.
1223	static bool isOnlyMemoryAccess(const Instruction I, const* Loop *L,
1224	const MemorySSAUpdater &MSSAU) {
1225	for (auto *BB : L->getBlocks())
1226	if (auto *Accs = MSSAU.getMemorySSA()->getBlockAccesses(BB)) {
1227	int NotAPhi = `0`;
1228	for (const auto &Acc : *Accs) {
1229	if (isa<MemoryPhi>(Val: &Acc))
1230	continue;
1231	const auto *MUD = cast<MemoryUseOrDef>(Val: &Acc);
1232	if (MUD->getMemoryInst() != I \|\| NotAPhi++ == `1`)
1233	return false;
1234	}
1235	}
1236	return true;
1237	}
1238
1239	static MemoryAccess *getClobberingMemoryAccess(MemorySSA &MSSA,
1240	BatchAAResults &BAA,
1241	SinkAndHoistLICMFlags &Flags,
1242	MemoryUseOrDef *MA) {
1243	// See declaration of SetLicmMssaOptCap for usage details.
1244	if (Flags.tooManyClobberingCalls())
1245	return MA->getDefiningAccess();
1246
1247	MemoryAccess *Source =
1248	MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(MA, AA&: BAA);
1249	Flags.incrementClobberingCalls();
1250	return Source;
1251	}
1252
1253	bool llvm::canHoistLoad(LoadInst &LI, AAResults AA, DominatorTree DT,
1254	Loop *CurLoop, MemorySSA &MSSA,
1255	bool TargetExecutesOncePerLoop,
1256	SinkAndHoistLICMFlags &Flags,
1257	OptimizationRemarkEmitter *ORE) {
1258	if (!LI.isUnordered())
1259	return false; // Don't sink/hoist volatile or ordered atomic loads!
1260
1261	// Loads from constant memory are always safe to move, even if they end up
1262	// in the same alias set as something that ends up being modified.
1263	if (!isModSet(MRI: AA->getModRefInfoMask(P: LI.getOperand(i_nocapture: `0`))))
1264	return true;
1265	if (LI.hasMetadata(KindID: LLVMContext::MD_invariant_load))
1266	return true;
1267
1268	if (LI.isAtomic() && !TargetExecutesOncePerLoop)
1269	return false; // Don't risk duplicating unordered loads
1270
1271	// This checks for an invariant.start dominating the load.
1272	if (isLoadInvariantInLoop(LI: &LI, DT, CurLoop))
1273	return true;
1274
1275	auto *MU = cast<MemoryUse>(Val: MSSA.getMemoryAccess(I: &LI));
1276
1277	bool InvariantGroup = LI.hasMetadata(KindID: LLVMContext::MD_invariant_group);
1278
1279	bool Invalidated =
1280	pointerInvalidatedByLoop(MSSA: &MSSA, MU, CurLoop, I&: LI, Flags, InvariantGroup);
1281	// Check loop-invariant address because this may also be a sinkable load
1282	// whose address is not necessarily loop-invariant.
1283	if (ORE && Invalidated && CurLoop->isLoopInvariant(V: LI.getPointerOperand()))
1284	ORE->emit(RemarkBuilder: [&]() {
1285	return OptimizationRemarkMissed (
1286	DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", &LI)
1287	<< "failed to move load with loop-invariant address "
1288	"because the loop may invalidate its value";
1289	});
1290
1291	return !Invalidated;
1292	}
1293
1294	bool llvm::canSinkOrHoistInst(Instruction &I, AAResults AA, DominatorTree DT,
1295	Loop *CurLoop, MemorySSAUpdater &MSSAU,
1296	bool TargetExecutesOncePerLoop,
1297	SinkAndHoistLICMFlags &Flags,
1298	OptimizationRemarkEmitter *ORE) {
1299	// If we don't understand the instruction, bail early.
1300	if (!isHoistableAndSinkableInst(I))
1301	return false;
1302
1303	MemorySSA *MSSA = MSSAU.getMemorySSA();
1304	// Loads have extra constraints we have to verify before we can hoist them.
1305	if (LoadInst *LI = dyn_cast<LoadInst>(Val: &I)) {
1306	return canHoistLoad(LI&: LI, AA, DT, CurLoop, MSSA&: MSSA, TargetExecutesOncePerLoop,
1307	Flags, ORE);
1308	} else if (CallInst *CI = dyn_cast<CallInst>(Val: &I)) {
1309	// Don't sink calls which can throw.
1310	if (CI->mayThrow())
1311	return false;
1312
1313	// Convergent attribute has been used on operations that involve
1314	// inter-thread communication which results are implicitly affected by the
1315	// enclosing control flows. It is not safe to hoist or sink such operations
1316	// across control flow.
1317	if (CI->isConvergent())
1318	return false;
1319
1320	// FIXME: Current LLVM IR semantics don't work well with coroutines and
1321	// thread local globals. We currently treat getting the address of a thread
1322	// local global as not accessing memory, even though it may not be a
1323	// constant throughout a function with coroutines. Remove this check after
1324	// we better model semantics of thread local globals.
1325	if (CI->getFunction()->isPresplitCoroutine())
1326	return false;
1327
1328	using namespace PatternMatch;
1329	if (match(V: CI, P: m_Intrinsic<Intrinsic::assume>()))
1330	// Assumes don't actually alias anything or throw
1331	return true;
1332
1333	// Handle simple cases by querying alias analysis.
1334	MemoryEffects Behavior = AA->getMemoryEffects(Call: CI);
1335
1336	if (Behavior.doesNotAccessMemory())
1337	return true;
1338	if (Behavior.onlyReadsMemory()) {
1339	// Might have stale MemoryDef for call that was later inferred to be
1340	// read-only.
1341	auto *MU = dyn_cast<MemoryUse>(Val: MSSA->getMemoryAccess(I: CI));
1342	if (!MU)
1343	return false;
1344
1345	// If we can prove there are no writes to the memory read by the call, we
1346	// can hoist or sink.
1347	return !pointerInvalidatedByLoop(
1348	MSSA, MU, CurLoop, I, Flags, /InvariantGroup=/false);
1349	}
1350
1351	if (Behavior.onlyWritesMemory()) {
1352	// can hoist or sink if there are no conflicting read/writes to the
1353	// memory location written to by the call.
1354	return noConflictingReadWrites(I: CI, MSSA, AA, CurLoop, Flags);
1355	}
1356
1357	return false;
1358	} else if (auto *FI = dyn_cast<FenceInst>(Val: &I)) {
1359	// Fences alias (most) everything to provide ordering. For the moment,
1360	// just give up if there are any other memory operations in the loop.
1361	return isOnlyMemoryAccess(I: FI, L: CurLoop, MSSAU);
1362	} else if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
1363	if (!SI->isUnordered())
1364	return false; // Don't sink/hoist volatile or ordered atomic store!
1365
1366	// We can only hoist a store that we can prove writes a value which is not
1367	// read or overwritten within the loop. For those cases, we fallback to
1368	// load store promotion instead. TODO: We can extend this to cases where
1369	// there is exactly one write to the location and that write dominates an
1370	// arbitrary number of reads in the loop.
1371	if (isOnlyMemoryAccess(I: SI, L: CurLoop, MSSAU))
1372	return true;
1373	return noConflictingReadWrites(I: SI, MSSA, AA, CurLoop, Flags);
1374	}
1375
1376	assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
1377
1378	// We've established mechanical ability and aliasing, it's up to the caller
1379	// to check fault safety
1380	return true;
1381	}
1382
1383	/// Returns true if a PHINode is a trivially replaceable with an
1384	/// Instruction.
1385	/// This is true when all incoming values are that instruction.
1386	/// This pattern occurs most often with LCSSA PHI nodes.
1387	///
1388	static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I) {
1389	for (const Value *IncValue : PN.incoming_values())
1390	if (IncValue != &I)
1391	return false;
1392
1393	return true;
1394	}
1395
1396	/// Return true if the instruction is foldable in the loop.
1397	static bool isFoldableInLoop(const Instruction &I, const Loop *CurLoop,
1398	const TargetTransformInfo *TTI) {
1399	if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: &I)) {
1400	InstructionCost CostI =
1401	TTI->getInstructionCost(U: &I, CostKind: TargetTransformInfo::TCK_SizeAndLatency);
1402	if (CostI != TargetTransformInfo::TCC_Free)
1403	return false;
1404	// For a GEP, we cannot simply use getInstructionCost because currently
1405	// it optimistically assumes that a GEP will fold into addressing mode
1406	// regardless of its users.
1407	const BasicBlock *BB = GEP->getParent();
1408	for (const User *U : GEP->users()) {
1409	const Instruction *UI = cast<Instruction>(Val: U);
1410	if (CurLoop->contains(Inst: UI) &&
1411	(BB != UI->getParent() \|\|
1412	(!isa<StoreInst>(Val: UI) && !isa<LoadInst>(Val: UI))))
1413	return false;
1414	}
1415	return true;
1416	}
1417
1418	return false;
1419	}
1420
1421	/// Return true if the only users of this instruction are outside of
1422	/// the loop. If this is true, we can sink the instruction to the exit
1423	/// blocks of the loop.
1424	///
1425	/// We also return true if the instruction could be folded away in lowering.
1426	/// (e.g., a GEP can be folded into a load as an addressing mode in the loop).
1427	static bool isNotUsedOrFoldableInLoop(const Instruction &I, const Loop *CurLoop,
1428	const LoopSafetyInfo *SafetyInfo,
1429	TargetTransformInfo *TTI,
1430	bool &FoldableInLoop, bool LoopNestMode) {
1431	const auto &BlockColors = SafetyInfo->getBlockColors();
1432	bool IsFoldable = isFoldableInLoop(I, CurLoop, TTI);
1433	for (const User *U : I.users()) {
1434	const Instruction *UI = cast<Instruction>(Val: U);
1435	if (const PHINode *PN = dyn_cast<PHINode>(Val: UI)) {
1436	const BasicBlock *BB = PN->getParent();
1437	// We cannot sink uses in catchswitches.
1438	if (isa<CatchSwitchInst>(Val: BB->getTerminator()))
1439	return false;
1440
1441	// We need to sink a callsite to a unique funclet. Avoid sinking if the
1442	// phi use is too muddled.
1443	if (isa<CallInst>(Val: I))
1444	if (!BlockColors.empty() &&
1445	BlockColors.find(Val: const_cast<BasicBlock *>(BB))->second.size() != `1`)
1446	return false;
1447
1448	if (LoopNestMode) {
1449	while (isa<PHINode>(Val: UI) && UI->hasOneUser() &&
1450	UI->getNumOperands() == `1`) {
1451	if (!CurLoop->contains(Inst: UI))
1452	break;
1453	UI = cast<Instruction>(Val: UI->user_back());
1454	}
1455	}
1456	}
1457
1458	if (CurLoop->contains(Inst: UI)) {
1459	if (IsFoldable) {
1460	FoldableInLoop = true;
1461	continue;
1462	}
1463	return false;
1464	}
1465	}
1466	return true;
1467	}
1468
1469	static Instruction *cloneInstructionInExitBlock(
1470	Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
1471	const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU) {
1472	Instruction *New;
1473	if (auto *CI = dyn_cast<CallInst>(Val: &I)) {
1474	const auto &BlockColors = SafetyInfo->getBlockColors();
1475
1476	// Sinking call-sites need to be handled differently from other
1477	// instructions. The cloned call-site needs a funclet bundle operand
1478	// appropriate for its location in the CFG.
1479	SmallVector<OperandBundleDef, `1`> OpBundles;
1480	for (unsigned BundleIdx = `0`, BundleEnd = CI->getNumOperandBundles();
1481	BundleIdx != BundleEnd; ++BundleIdx) {
1482	OperandBundleUse Bundle = CI->getOperandBundleAt(Index: BundleIdx);
1483	if (Bundle.getTagID() == LLVMContext::OB_funclet)
1484	continue;
1485
1486	OpBundles.emplace_back(Args&: Bundle);
1487	}
1488
1489	if (!BlockColors.empty()) {
1490	const ColorVector &CV = BlockColors.find(Val: &ExitBlock)->second;
1491	assert(CV.size() == `1` && "non-unique color for exit block!");
1492	BasicBlock *BBColor = CV.front();
1493	BasicBlock::iterator EHPad = BBColor->getFirstNonPHIIt();
1494	if (EHPad ->isEHPad())
1495	OpBundles.emplace_back(Args: "funclet", Args: &*EHPad);
1496	}
1497
1498	New = CallInst::Create(CI, Bundles: OpBundles);
1499	New->copyMetadata(SrcInst: *CI);
1500	} else {
1501	New = I.clone();
1502	}
1503
1504	New->insertInto(ParentBB: &ExitBlock, It: ExitBlock.getFirstInsertionPt());
1505	if (!I.getName().empty())
1506	New->setName(I.getName() + ".le");
1507
1508	if (MSSAU.getMemorySSA()->getMemoryAccess(I: &I)) {
1509	// Create a new MemoryAccess and let MemorySSA set its defining access.
1510	// After running some passes, MemorySSA might be outdated, and the
1511	// instruction `I` may have become a non-memory touching instruction.
1512	MemoryAccess *NewMemAcc = MSSAU.createMemoryAccessInBB(
1513	I: New, Definition: nullptr, BB: New->getParent(), Point: MemorySSA::Beginning,
1514	/CreationMustSucceed=/false);
1515	if (NewMemAcc) {
1516	if (auto *MemDef = dyn_cast<MemoryDef>(Val: NewMemAcc))
1517	MSSAU.insertDef(Def: MemDef, /RenameUses=/true);
1518	else {
1519	auto *MemUse = cast<MemoryUse>(Val: NewMemAcc);
1520	MSSAU.insertUse(Use: MemUse, /RenameUses=/true);
1521	}
1522	}
1523	}
1524
1525	// Build LCSSA PHI nodes for any in-loop operands (if legal). Note that
1526	// this is particularly cheap because we can rip off the PHI node that we're
1527	// replacing for the number and blocks of the predecessors.
1528	// OPT: If this shows up in a profile, we can instead finish sinking all
1529	// invariant instructions, and then walk their operands to re-establish
1530	// LCSSA. That will eliminate creating PHI nodes just to nuke them when
1531	// sinking bottom-up.
1532	for (Use &Op : New->operands())
1533	if (LI->wouldBeOutOfLoopUseRequiringLCSSA(V: Op.get(), ExitBB: PN.getParent())) {
1534	auto *OInst = cast<Instruction>(Val: Op.get());
1535	PHINode *OpPN =
1536	PHINode::Create(Ty: OInst->getType(), NumReservedValues: PN.getNumIncomingValues(),
1537	NameStr: OInst->getName() + ".lcssa");
1538	OpPN->insertBefore(InsertPos: ExitBlock.begin());
1539	for (unsigned i = `0`, e = PN.getNumIncomingValues(); i != e; ++i)
1540	OpPN->addIncoming(V: OInst, BB: PN.getIncomingBlock(i));
1541	Op = OpPN;
1542	}
1543	return New;
1544	}
1545
1546	static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
1547	MemorySSAUpdater &MSSAU) {
1548	MSSAU.removeMemoryAccess(I: &I);
1549	SafetyInfo.removeInstruction(Inst: &I);
1550	I.eraseFromParent();
1551	}
1552
1553	static void moveInstructionBefore(Instruction &I, BasicBlock::iterator Dest,
1554	ICFLoopSafetyInfo &SafetyInfo,
1555	MemorySSAUpdater &MSSAU,
1556	ScalarEvolution *SE) {
1557	SafetyInfo.removeInstruction(Inst: &I);
1558	SafetyInfo.insertInstructionTo(Inst: &I, BB: Dest ->getParent());
1559	I.moveBefore(BB&: *Dest ->getParent(), I: Dest);
1560	if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
1561	Val: MSSAU.getMemorySSA()->getMemoryAccess(I: &I)))
1562	MSSAU.moveToPlace(What: OldMemAcc, BB: Dest ->getParent(),
1563	Where: MemorySSA::BeforeTerminator);
1564	if (SE)
1565	SE->forgetBlockAndLoopDispositions(V: &I);
1566	}
1567
1568	static Instruction *sinkThroughTriviallyReplaceablePHI(
1569	PHINode TPN, Instruction I, LoopInfo *LI,
1570	SmallDenseMap<BasicBlock , Instruction , `32`> &SunkCopies,
1571	const LoopSafetyInfo SafetyInfo, const* Loop *CurLoop,
1572	MemorySSAUpdater &MSSAU) {
1573	assert(isTriviallyReplaceablePHI(TPN, I) &&
1574	"Expect only trivially replaceable PHI");
1575	BasicBlock *ExitBlock = TPN->getParent();
1576	auto [It, Inserted] = SunkCopies.try_emplace(Key: ExitBlock);
1577	if (Inserted)
1578	It ->second = cloneInstructionInExitBlock(I&: I, ExitBlock&: ExitBlock, PN&: *TPN, LI,
1579	SafetyInfo, MSSAU);
1580	return It ->second;
1581	}
1582
1583	static bool canSplitPredecessors(PHINode PN, LoopSafetyInfo SafetyInfo) {
1584	BasicBlock *BB = PN->getParent();
1585	if (!BB->canSplitPredecessors())
1586	return false;
1587	// It's not impossible to split EHPad blocks, but if BlockColors already exist
1588	// it require updating BlockColors for all offspring blocks accordingly. By
1589	// skipping such corner case, we can make updating BlockColors after splitting
1590	// predecessor fairly simple.
1591	if (!SafetyInfo->getBlockColors().empty() &&
1592	BB->getFirstNonPHIIt()->isEHPad())
1593	return false;
1594	for (BasicBlock *BBPred : predecessors(BB)) {
1595	if (isa<IndirectBrInst>(Val: BBPred->getTerminator()))
1596	return false;
1597	}
1598	return true;
1599	}
1600
1601	static void splitPredecessorsOfLoopExit(PHINode PN, DominatorTree DT,
1602	LoopInfo LI, const* Loop *CurLoop,
1603	LoopSafetyInfo *SafetyInfo,
1604	MemorySSAUpdater *MSSAU) {
1605	#ifndef NDEBUG
1606	SmallVector<BasicBlock *, `32`> ExitBlocks;
1607	CurLoop->getUniqueExitBlocks(ExitBlocks);
1608	SmallPtrSet<BasicBlock *, `32`> ExitBlockSet(llvm::from_range, ExitBlocks);
1609	#endif
1610	BasicBlock *ExitBB = PN->getParent();
1611	assert(ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block.");
1612
1613	// Split predecessors of the loop exit to make instructions in the loop are
1614	// exposed to exit blocks through trivially replaceable PHIs while keeping the
1615	// loop in the canonical form where each predecessor of each exit block should
1616	// be contained within the loop. For example, this will convert the loop below
1617	// from
1618	//
1619	// LB1:
1620	// %v1 =
1621	// br %LE, %LB2
1622	// LB2:
1623	// %v2 =
1624	// br %LE, %LB1
1625	// LE:
1626	// %p = phi [%v1, %LB1], [%v2, %LB2] <-- non-trivially replaceable
1627	//
1628	// to
1629	//
1630	// LB1:
1631	// %v1 =
1632	// br %LE.split, %LB2
1633	// LB2:
1634	// %v2 =
1635	// br %LE.split2, %LB1
1636	// LE.split:
1637	// %p1 = phi [%v1, %LB1] <-- trivially replaceable
1638	// br %LE
1639	// LE.split2:
1640	// %p2 = phi [%v2, %LB2] <-- trivially replaceable
1641	// br %LE
1642	// LE:
1643	// %p = phi [%p1, %LE.split], [%p2, %LE.split2]
1644	//
1645	const auto &BlockColors = SafetyInfo->getBlockColors();
1646	SmallSetVector<BasicBlock *, `8`> PredBBs(pred_begin(BB: ExitBB), pred_end(BB: ExitBB));
1647	DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1648	while (!PredBBs.empty()) {
1649	BasicBlock PredBB = PredBBs.begin();
1650	assert(CurLoop->contains(PredBB) &&
1651	"Expect all predecessors are in the loop");
1652	if (PN->getBasicBlockIndex(BB: PredBB) >= `0`) {
1653	BasicBlock *NewPred = SplitBlockPredecessors(
1654	BB: ExitBB, Preds: PredBB, Suffix: ".split.loop.exit", DTU: &DTU, LI, MSSAU, PreserveLCSSA: true);
1655	// Since we do not allow splitting EH-block with BlockColors in
1656	// canSplitPredecessors(), we can simply assign predecessor's color to
1657	// the new block.
1658	if (!BlockColors.empty())
1659	// Grab a reference to the ColorVector to be inserted before getting the
1660	// reference to the vector we are copying because inserting the new
1661	// element in BlockColors might cause the map to be reallocated.
1662	SafetyInfo->copyColors(New: NewPred, Old: PredBB);
1663	}
1664	PredBBs.remove(X: PredBB);
1665	}
1666	}
1667
1668	/// When an instruction is found to only be used outside of the loop, this
1669	/// function moves it to the exit blocks and patches up SSA form as needed.
1670	/// This method is guaranteed to remove the original instruction from its
1671	/// position, and may either delete it or move it to outside of the loop.
1672	///
1673	static bool sink(Instruction &I, LoopInfo LI, DominatorTree DT,
1674	const Loop CurLoop, ICFLoopSafetyInfo SafetyInfo,
1675	MemorySSAUpdater &MSSAU, OptimizationRemarkEmitter *ORE) {
1676	bool Changed = false;
1677	LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
1678
1679	// Iterate over users to be ready for actual sinking. Replace users via
1680	// unreachable blocks with undef and make all user PHIs trivially replaceable.
1681	SmallPtrSet<Instruction *, `8`> VisitedUsers;
1682	for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
1683	auto User = cast<Instruction>(Val: UI);
1684	Use &U = UI.getUse();
1685	++UI;
1686
1687	if (VisitedUsers.count(Ptr: User) \|\| CurLoop->contains(Inst: User))
1688	continue;
1689
1690	if (!DT->isReachableFromEntry(A: User->getParent())) {
1691	U = PoisonValue::get(T: I.getType());
1692	Changed = true;
1693	continue;
1694	}
1695
1696	// The user must be a PHI node.
1697	PHINode *PN = cast<PHINode>(Val: User);
1698
1699	// Surprisingly, instructions can be used outside of loops without any
1700	// exits. This can only happen in PHI nodes if the incoming block is
1701	// unreachable.
1702	BasicBlock *BB = PN->getIncomingBlock(U);
1703	if (!DT->isReachableFromEntry(A: BB)) {
1704	U = PoisonValue::get(T: I.getType());
1705	Changed = true;
1706	continue;
1707	}
1708
1709	VisitedUsers.insert(Ptr: PN);
1710	if (isTriviallyReplaceablePHI(PN: *PN, I))
1711	continue;
1712
1713	if (!canSplitPredecessors(PN, SafetyInfo))
1714	return Changed;
1715
1716	// Split predecessors of the PHI so that we can make users trivially
1717	// replaceable.
1718	splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo, MSSAU: &MSSAU);
1719
1720	// Should rebuild the iterators, as they may be invalidated by
1721	// splitPredecessorsOfLoopExit().
1722	UI = I.user_begin();
1723	UE = I.user_end();
1724	}
1725
1726	if (VisitedUsers.empty())
1727	return Changed;
1728
1729	ORE->emit(RemarkBuilder: [&]() {
1730	return OptimizationRemark (DEBUG_TYPE, "InstSunk", &I)
1731	<< "sinking " << ore::NV ("Inst", &I);
1732	});
1733	if (isa<LoadInst>(Val: I))
1734	++NumMovedLoads;
1735	else if (isa<CallInst>(Val: I))
1736	++NumMovedCalls;
1737	++NumSunk;
1738
1739	#ifndef NDEBUG
1740	SmallVector<BasicBlock *, `32`> ExitBlocks;
1741	CurLoop->getUniqueExitBlocks(ExitBlocks);
1742	SmallPtrSet<BasicBlock *, `32`> ExitBlockSet(llvm::from_range, ExitBlocks);
1743	#endif
1744
1745	// Clones of this instruction. Don't create more than one per exit block!
1746	SmallDenseMap<BasicBlock , Instruction , `32`> SunkCopies;
1747
1748	// If this instruction is only used outside of the loop, then all users are
1749	// PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
1750	// the instruction.
1751	// First check if I is worth sinking for all uses. Sink only when it is worth
1752	// across all uses.
1753	SmallSetVector<User*, `8`> Users(I.user_begin(), I.user_end());
1754	for (auto *UI : Users) {
1755	auto *User = cast<Instruction>(Val: UI);
1756
1757	if (CurLoop->contains(Inst: User))
1758	continue;
1759
1760	PHINode *PN = cast<PHINode>(Val: User);
1761	assert(ExitBlockSet.count(PN->getParent()) &&
1762	"The LCSSA PHI is not in an exit block!");
1763
1764	// The PHI must be trivially replaceable.
1765	Instruction *New = sinkThroughTriviallyReplaceablePHI(
1766	TPN: PN, I: &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1767	// As we sink the instruction out of the BB, drop its debug location.
1768	New->dropLocation();
1769	PN->replaceAllUsesWith(V: New);
1770	eraseInstruction(I&: PN, SafetyInfo&: SafetyInfo, MSSAU);
1771	Changed = true;
1772	}
1773	return Changed;
1774	}
1775
1776	/// When an instruction is found to only use loop invariant operands that
1777	/// is safe to hoist, this instruction is called to do the dirty work.
1778	///
1779	static void hoist(Instruction &I, const DominatorTree DT, const* Loop *CurLoop,
1780	BasicBlock Dest, ICFLoopSafetyInfo SafetyInfo,
1781	MemorySSAUpdater &MSSAU, ScalarEvolution *SE,
1782	OptimizationRemarkEmitter *ORE) {
1783	LLVM_DEBUG(dbgs() << "LICM hoisting to " << Dest->getNameOrAsOperand() << ": "
1784	<< I << "\n");
1785	ORE->emit(RemarkBuilder: [&]() {
1786	return OptimizationRemark (DEBUG_TYPE, "Hoisted", &I) << "hoisting "
1787	<< ore::NV ("Inst", &I);
1788	});
1789
1790	// Metadata can be dependent on conditions we are hoisting above.
1791	// Conservatively strip all metadata on the instruction unless we were
1792	// guaranteed to execute I if we entered the loop, in which case the metadata
1793	// is valid in the loop preheader.
1794	// Similarly, If I is a call and it is not guaranteed to execute in the loop,
1795	// then moving to the preheader means we should strip attributes on the call
1796	// that can cause UB since we may be hoisting above conditions that allowed
1797	// inferring those attributes. They may not be valid at the preheader.
1798	if ((I.hasMetadataOtherThanDebugLoc() \|\| isa<CallInst>(Val: I)) &&
1799	// The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
1800	// time in isGuaranteedToExecute if we don't actually have anything to
1801	// drop. It is a compile time optimization, not required for correctness.
1802	!SafetyInfo->isGuaranteedToExecute(Inst: I, DT, CurLoop)) {
1803	I.dropUBImplyingAttrsAndMetadata();
1804	}
1805
1806	if (isa<PHINode>(Val: I))
1807	// Move the new node to the end of the phi list in the destination block.
1808	moveInstructionBefore(I, Dest: Dest->getFirstNonPHIIt(), SafetyInfo&: *SafetyInfo, MSSAU, SE);
1809	else
1810	// Move the new node to the destination block, before its terminator.
1811	moveInstructionBefore(I, Dest: Dest->getTerminator()->getIterator(), SafetyInfo&: *SafetyInfo,
1812	MSSAU, SE);
1813
1814	I.updateLocationAfterHoist();
1815
1816	if (isa<LoadInst>(Val: I))
1817	++NumMovedLoads;
1818	else if (isa<CallInst>(Val: I))
1819	++NumMovedCalls;
1820	++NumHoisted;
1821	}
1822
1823	/// Only sink or hoist an instruction if it is not a trapping instruction,
1824	/// or if the instruction is known not to trap when moved to the preheader.
1825	/// or if it is a trapping instruction and is guaranteed to execute.
1826	static bool isSafeToExecuteUnconditionally(
1827	Instruction &Inst, const DominatorTree DT, const* TargetLibraryInfo *TLI,
1828	const Loop CurLoop, const* LoopSafetyInfo *SafetyInfo,
1829	OptimizationRemarkEmitter ORE, const* Instruction *CtxI,
1830	AssumptionCache AC, bool* AllowSpeculation) {
1831	if (AllowSpeculation &&
1832	isSafeToSpeculativelyExecute(I: &Inst, CtxI, AC, DT, TLI))
1833	return true;
1834
1835	bool GuaranteedToExecute =
1836	SafetyInfo->isGuaranteedToExecute(Inst, DT, CurLoop);
1837
1838	if (!GuaranteedToExecute) {
1839	auto *LI = dyn_cast<LoadInst>(Val: &Inst);
1840	if (LI && CurLoop->isLoopInvariant(V: LI->getPointerOperand()))
1841	ORE->emit(RemarkBuilder: [&]() {
1842	return OptimizationRemarkMissed (
1843	DEBUG_TYPE, "LoadWithLoopInvariantAddressCondExecuted", LI)
1844	<< "failed to hoist load with loop-invariant address "
1845	"because load is conditionally executed";
1846	});
1847	}
1848
1849	return GuaranteedToExecute;
1850	}
1851
1852	namespace {
1853	class LoopPromoter : public LoadAndStorePromoter {
1854	Value SomePtr; // Designated pointer to store to.*
1855	SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
1856	SmallVectorImpl<BasicBlock::iterator> &LoopInsertPts;
1857	SmallVectorImpl<MemoryAccess *> &MSSAInsertPts;
1858	PredIteratorCache &PredCache;
1859	MemorySSAUpdater &MSSAU;
1860	LoopInfo &LI;
1861	DebugLoc DL;
1862	Align Alignment;
1863	bool UnorderedAtomic;
1864	AAMDNodes AATags;
1865	ICFLoopSafetyInfo &SafetyInfo;
1866	bool CanInsertStoresInExitBlocks;
1867	ArrayRef<const Instruction *> Uses;
1868
1869	// We're about to add a use of V in a loop exit block. Insert an LCSSA phi
1870	// (if legal) if doing so would add an out-of-loop use to an instruction
1871	// defined in-loop.
1872	Value maybeInsertLCSSAPHI(Value V, BasicBlock BB) const* {
1873	if (!LI.wouldBeOutOfLoopUseRequiringLCSSA(V, ExitBB: BB))
1874	return V;
1875
1876	Instruction *I = cast<Instruction>(Val: V);
1877	// We need to create an LCSSA PHI node for the incoming value and
1878	// store that.
1879	PHINode *PN = PHINode::Create(Ty: I->getType(), NumReservedValues: PredCache.size(BB),
1880	NameStr: I->getName() + ".lcssa");
1881	PN->insertBefore(InsertPos: BB->begin());
1882	for (BasicBlock *Pred : PredCache.get(BB))
1883	PN->addIncoming(V: I, BB: Pred);
1884	return PN;
1885	}
1886
1887	public:
1888	LoopPromoter(Value SP, ArrayRef<const* Instruction *> Insts, SSAUpdater &S,
1889	SmallVectorImpl<BasicBlock *> &LEB,
1890	SmallVectorImpl<BasicBlock::iterator> &LIP,
1891	SmallVectorImpl<MemoryAccess *> &MSSAIP, PredIteratorCache &PIC,
1892	MemorySSAUpdater &MSSAU, LoopInfo &li, DebugLoc dl,
1893	Align Alignment, bool UnorderedAtomic, const AAMDNodes &AATags,
1894	ICFLoopSafetyInfo &SafetyInfo, bool CanInsertStoresInExitBlocks)
1895	: LoadAndStorePromoter (Insts, S), SomePtr(SP), LoopExitBlocks(LEB),
1896	LoopInsertPts(LIP), MSSAInsertPts(MSSAIP), PredCache(PIC), MSSAU(MSSAU),
1897	LI(li), DL (std::move(dl)), Alignment (Alignment),
1898	UnorderedAtomic(UnorderedAtomic), AATags (AATags),
1899	SafetyInfo(SafetyInfo),
1900	CanInsertStoresInExitBlocks(CanInsertStoresInExitBlocks), Uses (Insts) {}
1901
1902	void insertStoresInLoopExitBlocks() {
1903	// Insert stores after in the loop exit blocks. Each exit block gets a
1904	// store of the live-out values that feed them. Since we've already told
1905	// the SSA updater about the defs in the loop and the preheader
1906	// definition, it is all set and we can start using it.
1907	DIAssignID NewID = nullptr*;
1908	for (unsigned i = `0`, e = LoopExitBlocks.size(); i != e; ++i) {
1909	BasicBlock *ExitBlock = LoopExitBlocks [i];
1910	Value *LiveInValue = SSA.GetValueInMiddleOfBlock(BB: ExitBlock);
1911	LiveInValue = maybeInsertLCSSAPHI(V: LiveInValue, BB: ExitBlock);
1912	Value *Ptr = maybeInsertLCSSAPHI(V: SomePtr, BB: ExitBlock);
1913	BasicBlock::iterator InsertPos = LoopInsertPts [i];
1914	StoreInst NewSI = new* StoreInst (LiveInValue, Ptr, InsertPos);
1915	if (UnorderedAtomic)
1916	NewSI->setOrdering(AtomicOrdering::Unordered);
1917	NewSI->setAlignment(Alignment);
1918	NewSI->setDebugLoc(DL);
1919	// Attach DIAssignID metadata to the new store, generating it on the
1920	// first loop iteration.
1921	if (i == `0`) {
1922	// NewSI will have its DIAssignID set here if there are any stores in
1923	// Uses with a DIAssignID attachment. This merged ID will then be
1924	// attached to the other inserted stores (in the branch below).
1925	NewSI->mergeDIAssignID(SourceInstructions: Uses);
1926	NewID = cast_or_null<DIAssignID>(
1927	Val: NewSI->getMetadata(KindID: LLVMContext::MD_DIAssignID));
1928	} else {
1929	// Attach the DIAssignID (or nullptr) merged from Uses in the branch
1930	// above.
1931	NewSI->setMetadata(KindID: LLVMContext::MD_DIAssignID, Node: NewID);
1932	}
1933
1934	if (AATags)
1935	NewSI->setAAMetadata(AATags);
1936
1937	MemoryAccess *MSSAInsertPoint = MSSAInsertPts [i];
1938	MemoryAccess *NewMemAcc;
1939	if (!MSSAInsertPoint) {
1940	NewMemAcc = MSSAU.createMemoryAccessInBB(
1941	I: NewSI, Definition: nullptr, BB: NewSI->getParent(), Point: MemorySSA::Beginning);
1942	} else {
1943	NewMemAcc =
1944	MSSAU.createMemoryAccessAfter(I: NewSI, Definition: nullptr, InsertPt: MSSAInsertPoint);
1945	}
1946	MSSAInsertPts [i] = NewMemAcc;
1947	MSSAU.insertDef(Def: cast<MemoryDef>(Val: NewMemAcc), RenameUses: true);
1948	// FIXME: true for safety, false may still be correct.
1949	}
1950	}
1951
1952	void doExtraRewritesBeforeFinalDeletion() override {
1953	if (CanInsertStoresInExitBlocks)
1954	insertStoresInLoopExitBlocks();
1955	}
1956
1957	void instructionDeleted(Instruction I) const* override {
1958	SafetyInfo.removeInstruction(Inst: I);
1959	MSSAU.removeMemoryAccess(I);
1960	}
1961
1962	bool shouldDelete(Instruction I) const* override {
1963	if (isa<StoreInst>(Val: I))
1964	return CanInsertStoresInExitBlocks;
1965	return true;
1966	}
1967	};
1968
1969	bool isNotCapturedBeforeOrInLoop(const Value V, const* Loop *L,
1970	DominatorTree *DT) {
1971	// We can perform the captured-before check against any instruction in the
1972	// loop header, as the loop header is reachable from any instruction inside
1973	// the loop.
1974	// TODO: ReturnCaptures=true shouldn't be necessary here.
1975	return capturesNothing(CC: PointerMayBeCapturedBefore(
1976	V, /ReturnCaptures=/true, I: L->getHeader()->getTerminator(), DT,
1977	/IncludeI=/false, Mask: CaptureComponents::Provenance));
1978	}
1979
1980	/// Return true if we can prove that a caller cannot inspect the object if an
1981	/// unwind occurs inside the loop.
1982	bool isNotVisibleOnUnwindInLoop(const Value Object, const* Loop *L,
1983	DominatorTree *DT) {
1984	bool RequiresNoCaptureBeforeUnwind;
1985	if (!isNotVisibleOnUnwind(Object, RequiresNoCaptureBeforeUnwind))
1986	return false;
1987
1988	return !RequiresNoCaptureBeforeUnwind \|\|
1989	isNotCapturedBeforeOrInLoop(V: Object, L, DT);
1990	}
1991
1992	bool isThreadLocalObject(const Value Object, const* Loop L, DominatorTree DT,
1993	TargetTransformInfo *TTI) {
1994	// The object must be function-local to start with, and then not captured
1995	// before/in the loop.
1996	return (isIdentifiedFunctionLocal(V: Object) &&
1997	isNotCapturedBeforeOrInLoop(V: Object, L, DT)) \|\|
1998	(TTI->isSingleThreaded() \|\| SingleThread);
1999	}
2000
2001	} // namespace
2002
2003	/// Try to promote memory values to scalars by sinking stores out of the
2004	/// loop and moving loads to before the loop. We do this by looping over
2005	/// the stores in the loop, looking for stores to Must pointers which are
2006	/// loop invariant.
2007	///
2008	bool llvm::promoteLoopAccessesToScalars(
2009	const SmallSetVector<Value *, `8`> &PointerMustAliases,
2010	SmallVectorImpl<BasicBlock *> &ExitBlocks,
2011	SmallVectorImpl<BasicBlock::iterator> &InsertPts,
2012	SmallVectorImpl<MemoryAccess *> &MSSAInsertPts, PredIteratorCache &PIC,
2013	LoopInfo LI, DominatorTree DT, AssumptionCache *AC,
2014	const TargetLibraryInfo TLI, TargetTransformInfo TTI, Loop *CurLoop,
2015	MemorySSAUpdater &MSSAU, ICFLoopSafetyInfo *SafetyInfo,
2016	OptimizationRemarkEmitter ORE, bool* AllowSpeculation,
2017	bool HasReadsOutsideSet) {
2018	// Verify inputs.
2019	assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
2020	SafetyInfo != nullptr &&
2021	"Unexpected Input to promoteLoopAccessesToScalars");
2022
2023	LLVM_DEBUG({
2024	dbgs() << "Trying to promote set of must-aliased pointers:\n";
2025	for (Value *Ptr : PointerMustAliases)
2026	dbgs() << " " << *Ptr << "\n";
2027	});
2028	++NumPromotionCandidates;
2029
2030	Value SomePtr = PointerMustAliases.begin();
2031	BasicBlock *Preheader = CurLoop->getLoopPreheader();
2032
2033	// It is not safe to promote a load/store from the loop if the load/store is
2034	// conditional. For example, turning:
2035	//
2036	// for () { if (c) P += 1; }*
2037	//
2038	// into:
2039	//
2040	// tmp = P; for () { if (c) tmp +=1; } P = tmp;
2041	//
2042	// is not safe, because P may only be valid to access if 'c' is true.*
2043	//
2044	// The safety property divides into two parts:
2045	// p1) The memory may not be dereferenceable on entry to the loop. In this
2046	// case, we can't insert the required load in the preheader.
2047	// p2) The memory model does not allow us to insert a store along any dynamic
2048	// path which did not originally have one.
2049	//
2050	// If at least one store is guaranteed to execute, both properties are
2051	// satisfied, and promotion is legal.
2052	//
2053	// This, however, is not a necessary condition. Even if no store/load is
2054	// guaranteed to execute, we can still establish these properties.
2055	// We can establish (p1) by proving that hoisting the load into the preheader
2056	// is safe (i.e. proving dereferenceability on all paths through the loop). We
2057	// can use any access within the alias set to prove dereferenceability,
2058	// since they're all must alias.
2059	//
2060	// There are two ways establish (p2):
2061	// a) Prove the location is thread-local. In this case the memory model
2062	// requirement does not apply, and stores are safe to insert.
2063	// b) Prove a store dominates every exit block. In this case, if an exit
2064	// blocks is reached, the original dynamic path would have taken us through
2065	// the store, so inserting a store into the exit block is safe. Note that this
2066	// is different from the store being guaranteed to execute. For instance,
2067	// if an exception is thrown on the first iteration of the loop, the original
2068	// store is never executed, but the exit blocks are not executed either.
2069
2070	bool DereferenceableInPH = false;
2071	bool StoreIsGuaranteedToExecute = false;
2072	bool LoadIsGuaranteedToExecute = false;
2073	bool FoundLoadToPromote = false;
2074
2075	// Goes from Unknown to either Safe or Unsafe, but can't switch between them.
2076	enum {
2077	StoreSafe,
2078	StoreUnsafe,
2079	StoreSafetyUnknown,
2080	} StoreSafety = StoreSafetyUnknown;
2081
2082	SmallVector<Instruction *, `64`> LoopUses;
2083
2084	// We start with an alignment of one and try to find instructions that allow
2085	// us to prove better alignment.
2086	Align Alignment;
2087	// Keep track of which types of access we see
2088	bool SawUnorderedAtomic = false;
2089	bool SawNotAtomic = false;
2090	AAMDNodes AATags;
2091
2092	const DataLayout &MDL = Preheader->getDataLayout();
2093
2094	// If there are reads outside the promoted set, then promoting stores is
2095	// definitely not safe.
2096	if (HasReadsOutsideSet)
2097	StoreSafety = StoreUnsafe;
2098
2099	if (StoreSafety == StoreSafetyUnknown && SafetyInfo->anyBlockMayThrow()) {
2100	// If a loop can throw, we have to insert a store along each unwind edge.
2101	// That said, we can't actually make the unwind edge explicit. Therefore,
2102	// we have to prove that the store is dead along the unwind edge. We do
2103	// this by proving that the caller can't have a reference to the object
2104	// after return and thus can't possibly load from the object.
2105	Value *Object = getUnderlyingObject(V: SomePtr);
2106	if (!isNotVisibleOnUnwindInLoop(Object, L: CurLoop, DT))
2107	StoreSafety = StoreUnsafe;
2108	}
2109
2110	// Check that all accesses to pointers in the alias set use the same type.
2111	// We cannot (yet) promote a memory location that is loaded and stored in
2112	// different sizes. While we are at it, collect alignment and AA info.
2113	Type AccessTy = nullptr*;
2114	for (Value *ASIV : PointerMustAliases) {
2115	for (Use &U : ASIV->uses()) {
2116	// Ignore instructions that are outside the loop.
2117	Instruction *UI = dyn_cast<Instruction>(Val: U.getUser());
2118	if (!UI \|\| !CurLoop->contains(Inst: UI))
2119	continue;
2120
2121	// If there is an non-load/store instruction in the loop, we can't promote
2122	// it.
2123	if (LoadInst *Load = dyn_cast<LoadInst>(Val: UI)) {
2124	if (!Load->isUnordered())
2125	return false;
2126
2127	SawUnorderedAtomic \|= Load->isAtomic();
2128	SawNotAtomic \|= !Load->isAtomic();
2129	FoundLoadToPromote = true;
2130
2131	Align InstAlignment = Load->getAlign();
2132
2133	if (!LoadIsGuaranteedToExecute)
2134	LoadIsGuaranteedToExecute =
2135	SafetyInfo->isGuaranteedToExecute(Inst: *UI, DT, CurLoop);
2136
2137	// Note that proving a load safe to speculate requires proving
2138	// sufficient alignment at the target location. Proving it guaranteed
2139	// to execute does as well. Thus we can increase our guaranteed
2140	// alignment as well.
2141	if (!DereferenceableInPH \|\| (InstAlignment > Alignment))
2142	if (isSafeToExecuteUnconditionally(
2143	Inst&: *Load, DT, TLI, CurLoop, SafetyInfo, ORE,
2144	CtxI: Preheader->getTerminator(), AC, AllowSpeculation)) {
2145	DereferenceableInPH = true;
2146	Alignment = std::max(a: Alignment, b: InstAlignment);
2147	}
2148	} else if (const StoreInst *Store = dyn_cast<StoreInst>(Val: UI)) {
2149	// Stores of* the pointer are not interesting, only stores to the*
2150	// pointer.
2151	if (U.getOperandNo() != StoreInst::getPointerOperandIndex())
2152	continue;
2153	if (!Store->isUnordered())
2154	return false;
2155
2156	SawUnorderedAtomic \|= Store->isAtomic();
2157	SawNotAtomic \|= !Store->isAtomic();
2158
2159	// If the store is guaranteed to execute, both properties are satisfied.
2160	// We may want to check if a store is guaranteed to execute even if we
2161	// already know that promotion is safe, since it may have higher
2162	// alignment than any other guaranteed stores, in which case we can
2163	// raise the alignment on the promoted store.
2164	Align InstAlignment = Store->getAlign();
2165	bool GuaranteedToExecute =
2166	SafetyInfo->isGuaranteedToExecute(Inst: *UI, DT, CurLoop);
2167	StoreIsGuaranteedToExecute \|= GuaranteedToExecute;
2168	if (GuaranteedToExecute) {
2169	DereferenceableInPH = true;
2170	if (StoreSafety == StoreSafetyUnknown)
2171	StoreSafety = StoreSafe;
2172	Alignment = std::max(a: Alignment, b: InstAlignment);
2173	}
2174
2175	// If a store dominates all exit blocks, it is safe to sink.
2176	// As explained above, if an exit block was executed, a dominating
2177	// store must have been executed at least once, so we are not
2178	// introducing stores on paths that did not have them.
2179	// Note that this only looks at explicit exit blocks. If we ever
2180	// start sinking stores into unwind edges (see above), this will break.
2181	if (StoreSafety == StoreSafetyUnknown &&
2182	llvm::all_of(Range&: ExitBlocks, P: [&](BasicBlock *Exit) {
2183	return DT->dominates(A: Store->getParent(), B: Exit);
2184	}))
2185	StoreSafety = StoreSafe;
2186
2187	// If the store is not guaranteed to execute, we may still get
2188	// deref info through it.
2189	if (!DereferenceableInPH) {
2190	DereferenceableInPH = isDereferenceableAndAlignedPointer(
2191	V: Store->getPointerOperand(), Ty: Store->getValueOperand()->getType(),
2192	Alignment: Store->getAlign(),
2193	Q: SimplifyQuery (MDL, TLI, DT, AC, Preheader->getTerminator()));
2194	}
2195	} else
2196	continue; // Not a load or store.
2197
2198	if (!AccessTy)
2199	AccessTy = getLoadStoreType(I: UI);
2200	else if (AccessTy != getLoadStoreType(I: UI))
2201	return false;
2202
2203	// Merge the AA tags.
2204	if (LoopUses.empty()) {
2205	// On the first load/store, just take its AA tags.
2206	AATags = UI->getAAMetadata();
2207	} else if (AATags) {
2208	AATags = AATags.merge(Other: UI->getAAMetadata());
2209	}
2210
2211	LoopUses.push_back(Elt: UI);
2212	}
2213	}
2214
2215	// If we found both an unordered atomic instruction and a non-atomic memory
2216	// access, bail. We can't blindly promote non-atomic to atomic since we
2217	// might not be able to lower the result. We can't downgrade since that
2218	// would violate memory model. Also, align 0 is an error for atomics.
2219	if (SawUnorderedAtomic && SawNotAtomic)
2220	return false;
2221
2222	// If we're inserting an atomic load in the preheader, we must be able to
2223	// lower it. We're only guaranteed to be able to lower naturally aligned
2224	// atomics.
2225	if (SawUnorderedAtomic && Alignment < MDL.getTypeStoreSize(Ty: AccessTy))
2226	return false;
2227
2228	// If we couldn't prove we can hoist the load, bail.
2229	if (!DereferenceableInPH) {
2230	LLVM_DEBUG(dbgs() << "Not promoting: Not dereferenceable in preheader\n");
2231	return false;
2232	}
2233
2234	// We know we can hoist the load, but don't have a guaranteed store.
2235	// Check whether the location is writable and thread-local. If it is, then we
2236	// can insert stores along paths which originally didn't have them without
2237	// violating the memory model.
2238	if (StoreSafety == StoreSafetyUnknown) {
2239	Value *Object = getUnderlyingObject(V: SomePtr);
2240	bool ExplicitlyDereferenceableOnly;
2241	// The dereferenceability query here is only required to satisfy the
2242	// writable contract, actual dereferenceability has already been proven
2243	// above. As such, we can ignore frees.
2244	if (isWritableObject(Object, ExplicitlyDereferenceableOnly) &&
2245	(!ExplicitlyDereferenceableOnly \|\|
2246	isDereferenceablePointer(V: SomePtr, Ty: AccessTy, Q: MDL,
2247	/IgnoreFree=/true)) &&
2248	isThreadLocalObject(Object, L: CurLoop, DT, TTI))
2249	StoreSafety = StoreSafe;
2250	}
2251
2252	// If we've still failed to prove we can sink the store, hoist the load
2253	// only, if possible.
2254	if (StoreSafety != StoreSafe && !FoundLoadToPromote)
2255	// If we cannot hoist the load either, give up.
2256	return false;
2257
2258	// Lets do the promotion!
2259	if (StoreSafety == StoreSafe) {
2260	LLVM_DEBUG(dbgs() << "LICM: Promoting load/store of the value: " << *SomePtr
2261	<< `'\n'`);
2262	++NumLoadStorePromoted;
2263	} else {
2264	LLVM_DEBUG(dbgs() << "LICM: Promoting load of the value: " << *SomePtr
2265	<< `'\n'`);
2266	++NumLoadPromoted;
2267	}
2268
2269	ORE->emit(RemarkBuilder: [&]() {
2270	return OptimizationRemark (DEBUG_TYPE, "PromoteLoopAccessesToScalar",
2271	LoopUses [`0`])
2272	<< "Moving accesses to memory location out of the loop";
2273	});
2274
2275	// Look at all the loop uses, and try to merge their locations.
2276	std::vector<DebugLoc> LoopUsesLocs;
2277	for (auto U : LoopUses)
2278	LoopUsesLocs.push_back(x: U->getDebugLoc());
2279	auto DL = DebugLoc::getMergedLocations(Locs: LoopUsesLocs);
2280
2281	// We use the SSAUpdater interface to insert phi nodes as required.
2282	SmallVector<PHINode *, `16`> NewPHIs;
2283	SSAUpdater SSA(&NewPHIs);
2284	LoopPromoter Promoter(SomePtr, LoopUses, SSA, ExitBlocks, InsertPts,
2285	MSSAInsertPts, PIC, MSSAU, *LI, DL, Alignment,
2286	SawUnorderedAtomic,
2287	StoreIsGuaranteedToExecute ? AATags : AAMDNodes (),
2288	*SafetyInfo, StoreSafety == StoreSafe);
2289
2290	// Set up the preheader to have a definition of the value. It is the live-out
2291	// value from the preheader that uses in the loop will use.
2292	LoadInst PreheaderLoad = nullptr*;
2293	if (FoundLoadToPromote \|\| !StoreIsGuaranteedToExecute) {
2294	PreheaderLoad =
2295	new LoadInst (AccessTy, SomePtr, SomePtr->getName() + ".promoted",
2296	Preheader->getTerminator()->getIterator());
2297	if (SawUnorderedAtomic)
2298	PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
2299	PreheaderLoad->setAlignment(Alignment);
2300	PreheaderLoad->setDebugLoc(DebugLoc::getDropped());
2301	if (AATags && LoadIsGuaranteedToExecute)
2302	PreheaderLoad->setAAMetadata(AATags);
2303
2304	MemoryAccess *PreheaderLoadMemoryAccess = MSSAU.createMemoryAccessInBB(
2305	I: PreheaderLoad, Definition: nullptr, BB: PreheaderLoad->getParent(), Point: MemorySSA::End);
2306	MemoryUse *NewMemUse = cast<MemoryUse>(Val: PreheaderLoadMemoryAccess);
2307	MSSAU.insertUse(Use: NewMemUse, /RenameUses=/true);
2308	SSA.AddAvailableValue(BB: Preheader, V: PreheaderLoad);
2309	} else {
2310	SSA.AddAvailableValue(BB: Preheader, V: PoisonValue::get(T: AccessTy));
2311	}
2312
2313	if (VerifyMemorySSA)
2314	MSSAU.getMemorySSA()->verifyMemorySSA();
2315	// Rewrite all the loads in the loop and remember all the definitions from
2316	// stores in the loop.
2317	Promoter.run(Insts: LoopUses);
2318
2319	if (VerifyMemorySSA)
2320	MSSAU.getMemorySSA()->verifyMemorySSA();
2321	// If the SSAUpdater didn't use the load in the preheader, just zap it now.
2322	if (PreheaderLoad && PreheaderLoad->use_empty())
2323	eraseInstruction(I&: PreheaderLoad, SafetyInfo&: SafetyInfo, MSSAU);
2324
2325	return true;
2326	}
2327
2328	static void foreachMemoryAccess(MemorySSA MSSA, Loop L,
2329	function_ref<void(Instruction *)> Fn) {
2330	for (const BasicBlock *BB : L->blocks())
2331	if (const auto *Accesses = MSSA->getBlockAccesses(BB))
2332	for (const auto &Access : *Accesses)
2333	if (const auto *MUD = dyn_cast<MemoryUseOrDef>(Val: &Access))
2334	Fn (MUD->getMemoryInst());
2335	}
2336
2337	// The bool indicates whether there might be reads outside the set, in which
2338	// case only loads may be promoted.
2339	static SmallVector<PointersAndHasReadsOutsideSet, `0`>
2340	collectPromotionCandidates(MemorySSA MSSA, AliasAnalysis AA,
2341	DominatorTree DT, ICFLoopSafetyInfo SafetyInfo,
2342	Loop *L) {
2343	BatchAAResults BatchAA(*AA);
2344	AliasSetTracker AST(BatchAA);
2345
2346	auto IsPotentiallyPromotable = [L](const Instruction *I) {
2347	if (const auto *SI = dyn_cast<StoreInst>(Val: I)) {
2348	const Value *PtrOp = SI->getPointerOperand();
2349	if (isStrongerThanMonotonic(AO: SI->getOrdering()))
2350	return false;
2351	return !isa<ConstantData>(Val: PtrOp) && L->isLoopInvariant(V: PtrOp);
2352	}
2353	if (const auto *LI = dyn_cast<LoadInst>(Val: I)) {
2354	const Value *PtrOp = LI->getPointerOperand();
2355	if (isStrongerThanMonotonic(AO: LI->getOrdering()))
2356	return false;
2357	return !isa<ConstantData>(Val: PtrOp) && L->isLoopInvariant(V: PtrOp);
2358	}
2359	return false;
2360	};
2361
2362	// Populate AST with potentially promotable accesses.
2363	SmallPtrSet<Value *, `16`> AttemptingPromotion;
2364	foreachMemoryAccess(MSSA, L, Fn: [&](Instruction *I) {
2365	if (IsPotentiallyPromotable (I)) {
2366	AttemptingPromotion.insert(Ptr: I);
2367	if (StoreInst *SI = dyn_cast<StoreInst>(Val: I);
2368	SI && !SafetyInfo->isGuaranteedToExecute(Inst: *SI, DT, CurLoop: L)) {
2369	// Promotion requires inserting a new store at the loop exits; we need
2370	// to prove that store doesn't alias anything, in addition to proving
2371	// aliasing for the stores we're removing. The new store is executed
2372	// unconditionally, so when we're proving aliasing for that store, we
2373	// can't rely on AA tags for stores which are conditionally executed.
2374	//
2375	// As a future improvement, we could avoid stripping AA tags in more
2376	// cases. isGuaranteedToExecute() is stronger than what we need.
2377	// We only need to prove that every exit from the loop is dominated
2378	// by a store to the same location with the same AA tag.
2379	AST.addWithoutAATags(SI);
2380	} else {
2381	AST.add(I);
2382	}
2383	}
2384	});
2385
2386	// We're only interested in must-alias sets that contain a mod.
2387	SmallVector<PointerIntPair<const AliasSet , `1`, bool*>, `8`> Sets;
2388	for (AliasSet &AS : AST)
2389	if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
2390	Sets.push_back(Elt: {&AS, false});
2391
2392	if (Sets.empty())
2393	return {}; // Nothing to promote...
2394
2395	// Discard any sets for which there is an aliasing non-promotable access.
2396	foreachMemoryAccess(MSSA, L, Fn: [&](Instruction *I) {
2397	if (AttemptingPromotion.contains(Ptr: I))
2398	return;
2399
2400	llvm::erase_if(C&: Sets, P: [&](PointerIntPair<const AliasSet , `1`, bool*> &Pair) {
2401	ModRefInfo MR = Pair.getPointer()->aliasesUnknownInst(Inst: I, AA&: BatchAA);
2402	// Cannot promote if there are writes outside the set.
2403	if (isModSet(MRI: MR))
2404	return true;
2405	if (isRefSet(MRI: MR)) {
2406	// Remember reads outside the set.
2407	Pair.setInt(true);
2408	// If this is a mod-only set and there are reads outside the set,
2409	// we will not be able to promote, so bail out early.
2410	return !Pair.getPointer()->isRef();
2411	}
2412	return false;
2413	});
2414	});
2415
2416	SmallVector<std::pair<SmallSetVector<Value , `8`>, bool*>, `0`> Result;
2417	for (auto [Set, HasReadsOutsideSet] : Sets) {
2418	SmallSetVector<Value *, `8`> PointerMustAliases;
2419	for (const auto &MemLoc : *Set)
2420	PointerMustAliases.insert(X: const_cast<Value *>(MemLoc.Ptr));
2421	Result.emplace_back(Args: std::move(PointerMustAliases), Args&: HasReadsOutsideSet);
2422	}
2423
2424	return Result;
2425	}
2426
2427	// For a given store instruction or writeonly call instruction, this function
2428	// checks that there are no read or writes that conflict with the memory
2429	// access in the instruction
2430	static bool noConflictingReadWrites(Instruction I, MemorySSA MSSA,
2431	AAResults AA, Loop CurLoop,
2432	SinkAndHoistLICMFlags &Flags) {
2433	assert(isa<CallInst>(I) \|\| isa<StoreInst>(I));
2434	// If there are more accesses than the Promotion cap, then give up as we're
2435	// not walking a list that long.
2436	if (Flags.tooManyMemoryAccesses())
2437	return false;
2438
2439	auto *IMD = MSSA->getMemoryAccess(I);
2440	BatchAAResults BAA(*AA);
2441	auto Source = getClobberingMemoryAccess(MSSA&: MSSA, BAA, Flags, MA: IMD);
2442	// Make sure there are no clobbers inside the loop.
2443	if (!MSSA->isLiveOnEntryDef(MA: Source) && CurLoop->contains(BB: Source->getBlock()))
2444	return false;
2445
2446	// If there are interfering Uses don't move this store.
2447	// TODO: Cache set of Uses on the first walk in runOnLoop, update when
2448	// moving accesses. Can also extend to dominating uses.
2449	for (auto *BB : CurLoop->getBlocks()) {
2450	auto *Accesses = MSSA->getBlockAccesses(BB);
2451	if (!Accesses)
2452	continue;
2453	for (const auto &MA : *Accesses) {
2454	// Accesses are ordered. If we find one that I dominates we can stop.
2455	if (!Flags.getIsSink() && MSSA->dominates(A: IMD, B: &MA))
2456	break;
2457
2458	if (const auto *MemUseOrDef = dyn_cast<MemoryUseOrDef>(Val: &MA)) {
2459	// Skip unrelated accesses.
2460	if (isNoModRef(MRI: BAA.getModRefInfo(I: MemUseOrDef->getMemoryInst(), I2: I)))
2461	continue;
2462
2463	return false;
2464	}
2465	}
2466	}
2467	return true;
2468	}
2469
2470	static bool pointerInvalidatedByLoop(MemorySSA MSSA, MemoryUse MU,
2471	Loop *CurLoop, Instruction &I,
2472	SinkAndHoistLICMFlags &Flags,
2473	bool InvariantGroup) {
2474	// For hoisting, use the walker to determine safety
2475	if (!Flags.getIsSink()) {
2476	// If hoisting an invariant group, we only need to check that there
2477	// is no store to the loaded pointer between the start of the loop,
2478	// and the load (since all values must be the same).
2479
2480	// This can be checked in two conditions:
2481	// 1) if the memoryaccess is outside the loop
2482	// 2) the earliest access is at the loop header,
2483	// if the memory loaded is the phi node
2484
2485	BatchAAResults BAA(MSSA->getAA());
2486	MemoryAccess Source = getClobberingMemoryAccess(MSSA&: MSSA, BAA, Flags, MA: MU);
2487	return !MSSA->isLiveOnEntryDef(MA: Source) &&
2488	CurLoop->contains(BB: Source->getBlock()) &&
2489	!(InvariantGroup && Source->getBlock() == CurLoop->getHeader() && isa<MemoryPhi>(Val: Source));
2490	}
2491
2492	// For sinking, we'd need to check all Defs below this use. The getClobbering
2493	// call will look on the backedge of the loop, but will check aliasing with
2494	// the instructions on the previous iteration.
2495	// For example:
2496	// for (i ... )
2497	// load a[i] ( Use (LoE)
2498	// store a[i] ( 1 = Def (2), with 2 = Phi for the loop.
2499	// i++;
2500	// The load sees no clobbering inside the loop, as the backedge alias check
2501	// does phi translation, and will check aliasing against store a[i-1].
2502	// However sinking the load outside the loop, below the store is incorrect.
2503
2504	// For now, only sink if there are no Defs in the loop, and the existing ones
2505	// precede the use and are in the same block.
2506	// FIXME: Increase precision: Safe to sink if Use post dominates the Def;
2507	// needs PostDominatorTreeAnalysis.
2508	// FIXME: More precise: no Defs that alias this Use.
2509	if (Flags.tooManyMemoryAccesses())
2510	return true;
2511	for (auto *BB : CurLoop->getBlocks())
2512	if (pointerInvalidatedByBlock(BB&: BB, MSSA&: MSSA, MU&: *MU))
2513	return true;
2514	// When sinking, the source block may not be part of the loop so check it.
2515	if (!CurLoop->contains(Inst: &I))
2516	return pointerInvalidatedByBlock(BB&: I.getParent(), MSSA&: MSSA, MU&: *MU);
2517
2518	return false;
2519	}
2520
2521	bool pointerInvalidatedByBlock(BasicBlock &BB, MemorySSA &MSSA, MemoryUse &MU) {
2522	if (const auto *Accesses = MSSA.getBlockDefs(BB: &BB))
2523	for (const auto &MA : *Accesses)
2524	if (const auto *MD = dyn_cast<MemoryDef>(Val: &MA))
2525	if (MU.getBlock() != MD->getBlock() \|\| !MSSA.locallyDominates(A: MD, B: &MU))
2526	return true;
2527	return false;
2528	}
2529
2530	/// Try to simplify things like (A < INV_1 AND icmp A < INV_2) into (A <
2531	/// min(INV_1, INV_2)), if INV_1 and INV_2 are both loop invariants and their
2532	/// minimun can be computed outside of loop, and X is not a loop-invariant.
2533	static bool hoistMinMax(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
2534	MemorySSAUpdater &MSSAU) {
2535	bool Inverse = false;
2536	using namespace PatternMatch;
2537	Value Cond1, Cond2;
2538	if (match(V: &I, P: m_LogicalOr(L: m_Value(V&: Cond1), R: m_Value(V&: Cond2)))) {
2539	Inverse = true;
2540	} else if (match(V: &I, P: m_LogicalAnd(L: m_Value(V&: Cond1), R: m_Value(V&: Cond2)))) {
2541	// Do nothing
2542	} else
2543	return false;
2544
2545	auto MatchICmpAgainstInvariant = [&](Value C, CmpPredicate &P, Value &LHS,
2546	Value *&RHS) {
2547	if (!match(V: C, P: m_OneUse(SubPattern: m_ICmp(Pred&: P, L: m_Value(V&: LHS), R: m_Value(V&: RHS)))))
2548	return false;
2549	if (!LHS->getType()->isIntegerTy())
2550	return false;
2551	if (!ICmpInst::isRelational(P))
2552	return false;
2553	if (L.isLoopInvariant(V: LHS)) {
2554	std::swap(a&: LHS, b&: RHS);
2555	P = ICmpInst::getSwappedPredicate(pred: P);
2556	}
2557	if (L.isLoopInvariant(V: LHS) \|\| !L.isLoopInvariant(V: RHS))
2558	return false;
2559	if (Inverse)
2560	P = ICmpInst::getInversePredicate(pred: P);
2561	return true;
2562	};
2563	CmpPredicate P1, P2;
2564	Value LHS1, LHS2, RHS1, RHS2;
2565	if (!MatchICmpAgainstInvariant (Cond1, P1, LHS1, RHS1) \|\|
2566	!MatchICmpAgainstInvariant (Cond2, P2, LHS2, RHS2))
2567	return false;
2568	auto MatchingPred = CmpPredicate::getMatching(A: P1, B: P2);
2569	if (!MatchingPred \|\| LHS1 != LHS2)
2570	return false;
2571
2572	// Everything is fine, we can do the transform.
2573	bool UseMin = ICmpInst::isLT(P: MatchingPred) \|\| ICmpInst::isLE(P: MatchingPred);
2574	assert(
2575	(UseMin \|\| ICmpInst::isGT(*MatchingPred) \|\|
2576	ICmpInst::isGE(*MatchingPred)) &&
2577	"Relational predicate is either less (or equal) or greater (or equal)!");
2578	Intrinsic::ID id = ICmpInst::isSigned(Pred: *MatchingPred)
2579	? (UseMin ? Intrinsic::smin : Intrinsic::smax)
2580	: (UseMin ? Intrinsic::umin : Intrinsic::umax);
2581	auto *Preheader = L.getLoopPreheader();
2582	assert(Preheader && "Loop is not in simplify form?");
2583	IRBuilder<> Builder(Preheader->getTerminator());
2584	// We are about to create a new guaranteed use for RHS2 which might not exist
2585	// before (if it was a non-taken input of logical and/or instruction). If it
2586	// was poison, we need to freeze it. Note that no new use for LHS and RHS1 are
2587	// introduced, so they don't need this.
2588	if (isa<SelectInst>(Val: I))
2589	RHS2 = Builder.CreateFreeze(V: RHS2, Name: RHS2->getName() + ".fr");
2590	Value *NewRHS = Builder.CreateBinaryIntrinsic(
2591	ID: id, LHS: RHS1, RHS: RHS2, FMFSource: nullptr,
2592	Name: StringRef ("invariant.") +
2593	(ICmpInst::isSigned(Pred: *MatchingPred) ? "s" : "u") +
2594	(UseMin ? "min" : "max"));
2595	Builder.SetInsertPoint(&I);
2596	ICmpInst::Predicate P = *MatchingPred;
2597	if (Inverse)
2598	P = ICmpInst::getInversePredicate(pred: P);
2599	Value *NewCond = Builder.CreateICmp(P, LHS: LHS1, RHS: NewRHS);
2600	NewCond->takeName(V: &I);
2601	I.replaceAllUsesWith(V: NewCond);
2602	eraseInstruction(I, SafetyInfo, MSSAU);
2603	Instruction &CondI1 = *cast<Instruction>(Val: Cond1);
2604	Instruction &CondI2 = *cast<Instruction>(Val: Cond2);
2605	salvageDebugInfo(I&: CondI1);
2606	salvageDebugInfo(I&: CondI2);
2607	eraseInstruction(I&: CondI1, SafetyInfo, MSSAU);
2608	eraseInstruction(I&: CondI2, SafetyInfo, MSSAU);
2609	return true;
2610	}
2611
2612	/// Reassociate gep (gep ptr, idx1), idx2 to gep (gep ptr, idx2), idx1 if
2613	/// this allows hoisting the inner GEP.
2614	static bool hoistGEP(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
2615	MemorySSAUpdater &MSSAU, AssumptionCache *AC,
2616	DominatorTree *DT) {
2617	auto *GEP = dyn_cast<GetElementPtrInst>(Val: &I);
2618	if (!GEP)
2619	return false;
2620
2621	// Do not try to hoist a constant GEP out of the loop via reassociation.
2622	// Constant GEPs can often be folded into addressing modes, and reassociating
2623	// them may inhibit CSE of a common base.
2624	if (GEP->hasAllConstantIndices())
2625	return false;
2626
2627	auto *Src = dyn_cast<GetElementPtrInst>(Val: GEP->getPointerOperand());
2628	if (!Src \|\| !Src->hasOneUse() \|\| !L.contains(Inst: Src))
2629	return false;
2630
2631	Value *SrcPtr = Src->getPointerOperand();
2632	auto LoopInvariant = [&](Value V) { return* L.isLoopInvariant(V); };
2633	if (!L.isLoopInvariant(V: SrcPtr) \|\| !all_of(Range: GEP->indices(), P: LoopInvariant))
2634	return false;
2635
2636	// This can only happen if !AllowSpeculation, otherwise this would already be
2637	// handled.
2638	// FIXME: Should we respect AllowSpeculation in these reassociation folds?
2639	// The flag exists to prevent metadata dropping, which is not relevant here.
2640	if (all_of(Range: Src->indices(), P: LoopInvariant))
2641	return false;
2642
2643	// The swapped GEPs are inbounds if both original GEPs are inbounds
2644	// and the sign of the offsets is the same. For simplicity, only
2645	// handle both offsets being non-negative.
2646	const DataLayout &DL = GEP->getDataLayout();
2647	auto NonNegative = [&](Value *V) {
2648	return isKnownNonNegative(V, SQ: SimplifyQuery (DL, DT, AC, GEP));
2649	};
2650	bool IsInBounds = Src->isInBounds() && GEP->isInBounds() &&
2651	all_of(Range: Src->indices(), P: NonNegative) &&
2652	all_of(Range: GEP->indices(), P: NonNegative);
2653
2654	BasicBlock *Preheader = L.getLoopPreheader();
2655	IRBuilder<> Builder(Preheader->getTerminator());
2656	Value *NewSrc = Builder.CreateGEP(Ty: GEP->getSourceElementType(), Ptr: SrcPtr,
2657	IdxList: SmallVector<Value *>(GEP->indices()),
2658	Name: "invariant.gep", NW: IsInBounds);
2659	Builder.SetInsertPoint(GEP);
2660	Value *NewGEP = Builder.CreateGEP(Ty: Src->getSourceElementType(), Ptr: NewSrc,
2661	IdxList: SmallVector<Value *>(Src->indices()), Name: "gep",
2662	NW: IsInBounds);
2663	GEP->replaceAllUsesWith(V: NewGEP);
2664	eraseInstruction(I&: *GEP, SafetyInfo, MSSAU);
2665	salvageDebugInfo(I&: *Src);
2666	eraseInstruction(I&: *Src, SafetyInfo, MSSAU);
2667	return true;
2668	}
2669
2670	/// Try to turn things like "LV + C1 < C2" into "LV < C2 - C1". Here
2671	/// C1 and C2 are loop invariants and LV is a loop-variant.
2672	static bool hoistAdd(ICmpInst::Predicate Pred, Value *VariantLHS,
2673	Value *InvariantRHS, ICmpInst &ICmp, Loop &L,
2674	ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU,
2675	AssumptionCache AC, DominatorTree DT) {
2676	assert(!L.isLoopInvariant(VariantLHS) && "Precondition.");
2677	assert(L.isLoopInvariant(InvariantRHS) && "Precondition.");
2678
2679	bool IsSigned = ICmpInst::isSigned(Pred);
2680
2681	// Try to represent VariantLHS as sum of invariant and variant operands.
2682	using namespace PatternMatch;
2683	Value VariantOp, InvariantOp;
2684	if (IsSigned && !match(V: VariantLHS, P: m_NSWAddLike(L: m_Value(V&: VariantOp),
2685	R: m_Value(V&: InvariantOp))))
2686	return false;
2687	if (!IsSigned && !match(V: VariantLHS, P: m_NUWAddLike(L: m_Value(V&: VariantOp),
2688	R: m_Value(V&: InvariantOp))))
2689	return false;
2690
2691	// LHS itself is a loop-variant, try to represent it in the form:
2692	// "VariantOp + InvariantOp". If it is possible, then we can reassociate.
2693	if (L.isLoopInvariant(V: VariantOp))
2694	std::swap(a&: VariantOp, b&: InvariantOp);
2695	if (L.isLoopInvariant(V: VariantOp) \|\| !L.isLoopInvariant(V: InvariantOp))
2696	return false;
2697
2698	// In order to turn "LV + C1 < C2" into "LV < C2 - C1", we need to be able to
2699	// freely move values from left side of inequality to right side (just as in
2700	// normal linear arithmetics). Overflows make things much more complicated, so
2701	// we want to avoid this.
2702	auto &DL = L.getHeader()->getDataLayout();
2703	SimplifyQuery SQ(DL, DT, AC, &ICmp);
2704	if (IsSigned && computeOverflowForSignedSub(LHS: InvariantRHS, RHS: InvariantOp, SQ) !=
2705	llvm::OverflowResult::NeverOverflows)
2706	return false;
2707	if (!IsSigned &&
2708	computeOverflowForUnsignedSub(LHS: InvariantRHS, RHS: InvariantOp, SQ) !=
2709	llvm::OverflowResult::NeverOverflows)
2710	return false;
2711	auto *Preheader = L.getLoopPreheader();
2712	assert(Preheader && "Loop is not in simplify form?");
2713	IRBuilder<> Builder(Preheader->getTerminator());
2714	Value *NewCmpOp =
2715	Builder.CreateSub(LHS: InvariantRHS, RHS: InvariantOp, Name: "invariant.op",
2716	/HasNUW/ !IsSigned, /HasNSW/ IsSigned);
2717	ICmp.setPredicate(Pred);
2718	ICmp.setOperand(i_nocapture: `0`, Val_nocapture: VariantOp);
2719	ICmp.setOperand(i_nocapture: `1`, Val_nocapture: NewCmpOp);
2720	// The new LHS is a different value, so a samesign (or any other
2721	// poison-generating) flag asserted about the old operands may no longer hold.
2722	ICmp.dropPoisonGeneratingFlags();
2723
2724	Instruction &DeadI = cast<Instruction>(Val&: *VariantLHS);
2725	salvageDebugInfo(I&: DeadI);
2726	eraseInstruction(I&: DeadI, SafetyInfo, MSSAU);
2727	return true;
2728	}
2729
2730	/// Try to reassociate and hoist the following two patterns:
2731	/// LV - C1 < C2 --> LV < C1 + C2,
2732	/// C1 - LV < C2 --> LV > C1 - C2.
2733	static bool hoistSub(ICmpInst::Predicate Pred, Value *VariantLHS,
2734	Value *InvariantRHS, ICmpInst &ICmp, Loop &L,
2735	ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU,
2736	AssumptionCache AC, DominatorTree DT) {
2737	assert(!L.isLoopInvariant(VariantLHS) && "Precondition.");
2738	assert(L.isLoopInvariant(InvariantRHS) && "Precondition.");
2739
2740	bool IsSigned = ICmpInst::isSigned(Pred);
2741
2742	// Try to represent VariantLHS as sum of invariant and variant operands.
2743	using namespace PatternMatch;
2744	Value VariantOp, InvariantOp;
2745	if (IsSigned &&
2746	!match(V: VariantLHS, P: m_NSWSub(L: m_Value(V&: VariantOp), R: m_Value(V&: InvariantOp))))
2747	return false;
2748	if (!IsSigned &&
2749	!match(V: VariantLHS, P: m_NUWSub(L: m_Value(V&: VariantOp), R: m_Value(V&: InvariantOp))))
2750	return false;
2751
2752	bool VariantSubtracted = false;
2753	// LHS itself is a loop-variant, try to represent it in the form:
2754	// "VariantOp + InvariantOp". If it is possible, then we can reassociate. If
2755	// the variant operand goes with minus, we use a slightly different scheme.
2756	if (L.isLoopInvariant(V: VariantOp)) {
2757	std::swap(a&: VariantOp, b&: InvariantOp);
2758	VariantSubtracted = true;
2759	Pred = ICmpInst::getSwappedPredicate(pred: Pred);
2760	}
2761	if (L.isLoopInvariant(V: VariantOp) \|\| !L.isLoopInvariant(V: InvariantOp))
2762	return false;
2763
2764	// In order to turn "LV - C1 < C2" into "LV < C2 + C1", we need to be able to
2765	// freely move values from left side of inequality to right side (just as in
2766	// normal linear arithmetics). Overflows make things much more complicated, so
2767	// we want to avoid this. Likewise, for "C1 - LV < C2" we need to prove that
2768	// "C1 - C2" does not overflow.
2769	auto &DL = L.getHeader()->getDataLayout();
2770	SimplifyQuery SQ(DL, DT, AC, &ICmp);
2771	if (VariantSubtracted && IsSigned) {
2772	// C1 - LV < C2 --> LV > C1 - C2
2773	if (computeOverflowForSignedSub(LHS: InvariantOp, RHS: InvariantRHS, SQ) !=
2774	llvm::OverflowResult::NeverOverflows)
2775	return false;
2776	} else if (VariantSubtracted && !IsSigned) {
2777	// C1 - LV < C2 --> LV > C1 - C2
2778	if (computeOverflowForUnsignedSub(LHS: InvariantOp, RHS: InvariantRHS, SQ) !=
2779	llvm::OverflowResult::NeverOverflows)
2780	return false;
2781	} else if (!VariantSubtracted && IsSigned) {
2782	// LV - C1 < C2 --> LV < C1 + C2
2783	if (computeOverflowForSignedAdd(LHS: InvariantOp, RHS: InvariantRHS, SQ) !=
2784	llvm::OverflowResult::NeverOverflows)
2785	return false;
2786	} else { // !VariantSubtracted && !IsSigned
2787	// LV - C1 < C2 --> LV < C1 + C2
2788	if (computeOverflowForUnsignedAdd(LHS: InvariantOp, RHS: InvariantRHS, SQ) !=
2789	llvm::OverflowResult::NeverOverflows)
2790	return false;
2791	}
2792	auto *Preheader = L.getLoopPreheader();
2793	assert(Preheader && "Loop is not in simplify form?");
2794	IRBuilder<> Builder(Preheader->getTerminator());
2795	Value *NewCmpOp =
2796	VariantSubtracted
2797	? Builder.CreateSub(LHS: InvariantOp, RHS: InvariantRHS, Name: "invariant.op",
2798	/HasNUW/ !IsSigned, /HasNSW/ IsSigned)
2799	: Builder.CreateAdd(LHS: InvariantOp, RHS: InvariantRHS, Name: "invariant.op",
2800	/HasNUW/ !IsSigned, /HasNSW/ IsSigned);
2801	ICmp.setPredicate(Pred);
2802	ICmp.setOperand(i_nocapture: `0`, Val_nocapture: VariantOp);
2803	ICmp.setOperand(i_nocapture: `1`, Val_nocapture: NewCmpOp);
2804	// The new LHS is a different value, so a samesign (or any other
2805	// poison-generating) flag asserted about the old operands may no longer hold.
2806	ICmp.dropPoisonGeneratingFlags();
2807
2808	Instruction &DeadI = cast<Instruction>(Val&: *VariantLHS);
2809	salvageDebugInfo(I&: DeadI);
2810	eraseInstruction(I&: DeadI, SafetyInfo, MSSAU);
2811	return true;
2812	}
2813
2814	/// Reassociate and hoist add/sub expressions.
2815	static bool hoistAddSub(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
2816	MemorySSAUpdater &MSSAU, AssumptionCache *AC,
2817	DominatorTree *DT) {
2818	using namespace PatternMatch;
2819	CmpPredicate Pred;
2820	Value LHS, RHS;
2821	if (!match(V: &I, P: m_ICmp(Pred, L: m_Value(V&: LHS), R: m_Value(V&: RHS))))
2822	return false;
2823
2824	// Put variant operand to LHS position.
2825	if (L.isLoopInvariant(V: LHS)) {
2826	std::swap(a&: LHS, b&: RHS);
2827	Pred = ICmpInst::getSwappedPredicate(pred: Pred);
2828	}
2829	// We want to delete the initial operation after reassociation, so only do it
2830	// if it has no other uses.
2831	if (L.isLoopInvariant(V: LHS) \|\| !L.isLoopInvariant(V: RHS) \|\| !LHS->hasOneUse())
2832	return false;
2833
2834	// TODO: We could go with smarter context, taking common dominator of all I's
2835	// users instead of I itself.
2836	if (hoistAdd(Pred, VariantLHS: LHS, InvariantRHS: RHS, ICmp&: cast<ICmpInst>(Val&: I), L, SafetyInfo, MSSAU, AC, DT))
2837	return true;
2838
2839	if (hoistSub(Pred, VariantLHS: LHS, InvariantRHS: RHS, ICmp&: cast<ICmpInst>(Val&: I), L, SafetyInfo, MSSAU, AC, DT))
2840	return true;
2841
2842	return false;
2843	}
2844
2845	static bool isReassociableOp(Instruction I, unsigned* IntOpcode,
2846	unsigned FPOpcode) {
2847	if (I->getOpcode() == IntOpcode)
2848	return true;
2849	if (I->getOpcode() == FPOpcode && I->hasAllowReassoc() &&
2850	I->hasNoSignedZeros())
2851	return true;
2852	return false;
2853	}
2854
2855	/// Try to reassociate expressions like ((A1 B1) + (A2 * B2) + ...) * C where*
2856	/// A1, A2, ... and C are loop invariants into expressions like
2857	/// ((A1 C * B1) + (A2 * C * B2) + ...) and hoist the (A1 * C), (A2 * C), ...*
2858	/// invariant expressions. This functions returns true only if any hoisting has
2859	/// actually occurred.
2860	static bool hoistMulAddAssociation(Instruction &I, Loop &L,
2861	ICFLoopSafetyInfo &SafetyInfo,
2862	MemorySSAUpdater &MSSAU, AssumptionCache *AC,
2863	DominatorTree *DT) {
2864	if (!isReassociableOp(I: &I, IntOpcode: Instruction::Mul, FPOpcode: Instruction::FMul))
2865	return false;
2866	Value *VariantOp = I.getOperand(i: `0`);
2867	Value *InvariantOp = I.getOperand(i: `1`);
2868	if (L.isLoopInvariant(V: VariantOp))
2869	std::swap(a&: VariantOp, b&: InvariantOp);
2870	if (L.isLoopInvariant(V: VariantOp) \|\| !L.isLoopInvariant(V: InvariantOp))
2871	return false;
2872	Value *Factor = InvariantOp;
2873
2874	// First, we need to make sure we should do the transformation.
2875	SmallVector<Use *> Changes;
2876	SmallVector<BinaryOperator *> Adds;
2877	SmallVector<BinaryOperator *> Worklist;
2878	if (BinaryOperator *VariantBinOp = dyn_cast<BinaryOperator>(Val: VariantOp))
2879	Worklist.push_back(Elt: VariantBinOp);
2880	while (!Worklist.empty()) {
2881	BinaryOperator *BO = Worklist.pop_back_val();
2882	if (!BO->hasOneUse())
2883	return false;
2884	if (isReassociableOp(I: BO, IntOpcode: Instruction::Add, FPOpcode: Instruction::FAdd) &&
2885	isa<BinaryOperator>(Val: BO->getOperand(i_nocapture: `0`)) &&
2886	isa<BinaryOperator>(Val: BO->getOperand(i_nocapture: `1`))) {
2887	Worklist.push_back(Elt: cast<BinaryOperator>(Val: BO->getOperand(i_nocapture: `0`)));
2888	Worklist.push_back(Elt: cast<BinaryOperator>(Val: BO->getOperand(i_nocapture: `1`)));
2889	Adds.push_back(Elt: BO);
2890	continue;
2891	}
2892	if (!isReassociableOp(I: BO, IntOpcode: Instruction::Mul, FPOpcode: Instruction::FMul) \|\|
2893	L.isLoopInvariant(V: BO))
2894	return false;
2895	Use &U0 = BO->getOperandUse(i: `0`);
2896	Use &U1 = BO->getOperandUse(i: `1`);
2897	if (L.isLoopInvariant(V: U0))
2898	Changes.push_back(Elt: &U0);
2899	else if (L.isLoopInvariant(V: U1))
2900	Changes.push_back(Elt: &U1);
2901	else
2902	return false;
2903	unsigned Limit = I.getType()->isIntOrIntVectorTy()
2904	? IntAssociationUpperLimit
2905	: FPAssociationUpperLimit;
2906	if (Changes.size() > Limit)
2907	return false;
2908	}
2909	if (Changes.empty())
2910	return false;
2911
2912	// Drop the poison flags for any adds we looked through.
2913	if (I.getType()->isIntOrIntVectorTy()) {
2914	for (auto *Add : Adds)
2915	Add->dropPoisonGeneratingFlags();
2916	}
2917
2918	// We know we should do it so let's do the transformation.
2919	auto *Preheader = L.getLoopPreheader();
2920	assert(Preheader && "Loop is not in simplify form?");
2921	IRBuilder<> Builder(Preheader->getTerminator());
2922	for (auto *U : Changes) {
2923	assert(L.isLoopInvariant(U->get()));
2924	auto *Ins = cast<BinaryOperator>(Val: U->getUser());
2925	Value *Mul;
2926	if (I.getType()->isIntOrIntVectorTy()) {
2927	Mul = Builder.CreateMul(LHS: U->get(), RHS: Factor, Name: "factor.op.mul");
2928	// Drop the poison flags on the original multiply.
2929	Ins->dropPoisonGeneratingFlags();
2930	} else
2931	Mul = Builder.CreateFMulFMF(L: U->get(), R: Factor, FMFSource: Ins, Name: "factor.op.fmul");
2932
2933	// Rewrite the reassociable instruction.
2934	unsigned OpIdx = U->getOperandNo();
2935	auto *LHS = OpIdx == `0` ? Mul : Ins->getOperand(i_nocapture: `0`);
2936	auto *RHS = OpIdx == `1` ? Mul : Ins->getOperand(i_nocapture: `1`);
2937	auto *NewBO =
2938	BinaryOperator::Create(Op: Ins->getOpcode(), S1: LHS, S2: RHS,
2939	Name: Ins->getName() + ".reass", InsertBefore: Ins->getIterator());
2940	NewBO->setDebugLoc(DebugLoc::getDropped());
2941	NewBO->copyIRFlags(V: Ins);
2942	if (VariantOp == Ins)
2943	VariantOp = NewBO;
2944	Ins->replaceAllUsesWith(V: NewBO);
2945	eraseInstruction(I&: *Ins, SafetyInfo, MSSAU);
2946	}
2947
2948	I.replaceAllUsesWith(V: VariantOp);
2949	eraseInstruction(I, SafetyInfo, MSSAU);
2950	return true;
2951	}
2952
2953	/// Reassociate associative binary expressions of the form
2954	///
2955	/// 1. "(LV op C1) op C2" ==> "LV op (C1 op C2)"
2956	/// 2. "(C1 op LV) op C2" ==> "LV op (C1 op C2)"
2957	/// 3. "C2 op (C1 op LV)" ==> "LV op (C1 op C2)"
2958	/// 4. "C2 op (LV op C1)" ==> "LV op (C1 op C2)"
2959	///
2960	/// where op is an associative BinOp, LV is a loop variant, and C1 and C2 are
2961	/// loop invariants that we want to hoist, noting that associativity implies
2962	/// commutativity.
2963	static bool hoistBOAssociation(Instruction &I, Loop &L,
2964	ICFLoopSafetyInfo &SafetyInfo,
2965	MemorySSAUpdater &MSSAU, AssumptionCache *AC,
2966	DominatorTree *DT) {
2967	auto *BO = dyn_cast<BinaryOperator>(Val: &I);
2968	if (!BO \|\| !BO->isAssociative())
2969	return false;
2970
2971	Instruction::BinaryOps Opcode = BO->getOpcode();
2972	bool LVInRHS = L.isLoopInvariant(V: BO->getOperand(i_nocapture: `0`));
2973	auto *BO0 = dyn_cast<BinaryOperator>(Val: BO->getOperand(i_nocapture: LVInRHS));
2974	if (!BO0 \|\| BO0->getOpcode() != Opcode \|\| !BO0->isAssociative() \|\|
2975	BO0->hasNUsesOrMore(N: BO0->getType()->isIntegerTy() ? `2` : `3`))
2976	return false;
2977
2978	Value *LV = BO0->getOperand(i_nocapture: `0`);
2979	Value *C1 = BO0->getOperand(i_nocapture: `1`);
2980	Value *C2 = BO->getOperand(i_nocapture: !LVInRHS);
2981
2982	assert(BO->isCommutative() && BO0->isCommutative() &&
2983	"Associativity implies commutativity");
2984	if (L.isLoopInvariant(V: LV) && !L.isLoopInvariant(V: C1))
2985	std::swap(a&: LV, b&: C1);
2986	if (L.isLoopInvariant(V: LV) \|\| !L.isLoopInvariant(V: C1) \|\| !L.isLoopInvariant(V: C2))
2987	return false;
2988
2989	auto *Preheader = L.getLoopPreheader();
2990	assert(Preheader && "Loop is not in simplify form?");
2991
2992	IRBuilder<> Builder(Preheader->getTerminator());
2993	auto *Inv = Builder.CreateBinOp(Opc: Opcode, LHS: C1, RHS: C2, Name: "invariant.op");
2994
2995	auto *NewBO = BinaryOperator::Create(
2996	Op: Opcode, S1: LV, S2: Inv, Name: BO->getName() + ".reass", InsertBefore: BO->getIterator());
2997	NewBO->setDebugLoc(DebugLoc::getDropped());
2998
2999	if (Opcode == Instruction::FAdd \|\| Opcode == Instruction::FMul) {
3000	// Intersect FMF flags for FADD and FMUL.
3001	FastMathFlags Intersect = BO->getFastMathFlags() & BO0->getFastMathFlags();
3002	if (auto *I = dyn_cast<Instruction>(Val: Inv))
3003	I->setFastMathFlags(Intersect);
3004	NewBO->setFastMathFlags(Intersect);
3005	} else {
3006	OverflowTracking Flags;
3007	Flags.AllKnownNonNegative = false;
3008	Flags.AllKnownNonZero = false;
3009	Flags.mergeFlags(I&: *BO);
3010	Flags.mergeFlags(I&: *BO0);
3011	// If `Inv` was not constant-folded, a new Instruction has been created.
3012	if (auto *I = dyn_cast<Instruction>(Val: Inv))
3013	Flags.applyFlags(I&: *I);
3014	Flags.applyFlags(I&: *NewBO);
3015	}
3016
3017	BO->replaceAllUsesWith(V: NewBO);
3018	eraseInstruction(I&: *BO, SafetyInfo, MSSAU);
3019
3020	// (LV op C1) might not be erased if it has more uses than the one we just
3021	// replaced.
3022	if (BO0->use_empty()) {
3023	salvageDebugInfo(I&: *BO0);
3024	eraseInstruction(I&: *BO0, SafetyInfo, MSSAU);
3025	}
3026
3027	return true;
3028	}
3029
3030	/// Reassociate add/sub expressions of the form:
3031	///
3032	/// 1. "(LV + C1) - C2" ==> "LV + (C1 - C2)"
3033	/// 2. "(LV - C1) - C2" ==> "LV - (C1 + C2)"
3034	/// 3. "(LV - C1) + C2" ==> "LV + (C2 - C1)"
3035	///
3036	/// where LV is a loop variant, and C1 and C2 are loop invariants.
3037	/// Sub is not associative, but these algebraic identities allow hoisting
3038	/// invariant computations out of the loop.
3039	static bool hoistSubAddAssociation(Instruction &I, Loop &L,
3040	ICFLoopSafetyInfo &SafetyInfo,
3041	MemorySSAUpdater &MSSAU, AssumptionCache *AC,
3042	DominatorTree *DT) {
3043	using namespace PatternMatch;
3044
3045	Instruction *BO;
3046	Value LV, C1, *C2;
3047	Instruction::BinaryOps InvOp, ResultOp;
3048
3049	// Try to match one of three reassociation patterns involving sub.
3050	//
3051	// 1. (LV + C1) - C2 ==> LV + (C1 - C2)
3052	// 2. (LV - C1) - C2 ==> LV - (C1 + C2)
3053	// 3. (LV - C1) + C2 ==> LV + (C2 - C1)
3054	// ^ ^
3055	// \ \___ InvOp
3056	// \
3057	// \____ ResultOp
3058	//
3059	if (match(V: &I,
3060	P: m_Sub(L: m_OneUse(SubPattern: m_Instruction(I&: BO, P: m_Add(L: m_Value(V&: LV), R: m_Value(V&: C1)))),
3061	R: m_Value(V&: C2)))) {
3062	// Case 1.
3063	//
3064	// Depending on which of the addition is invariant, we might need to swap
3065	// the arguments
3066	if (L.isLoopInvariant(V: LV) && !L.isLoopInvariant(V: C1))
3067	std::swap(a&: LV, b&: C1);
3068	InvOp = Instruction::Sub;
3069	ResultOp = Instruction::Add;
3070	} else if (match(V: &I, P: m_Sub(L: m_OneUse(SubPattern: m_Instruction(
3071	I&: BO, P: m_Sub(L: m_Value(V&: LV), R: m_Value(V&: C1)))),
3072	R: m_Value(V&: C2)))) {
3073	// Case 2.
3074	InvOp = Instruction::Add;
3075	ResultOp = Instruction::Sub;
3076	} else if (match(V: &I, P: m_c_Add(L: m_OneUse(SubPattern: m_Instruction(
3077	I&: BO, P: m_Sub(L: m_Value(V&: LV), R: m_Value(V&: C1)))),
3078	R: m_Value(V&: C2)))) {
3079	// Case 3.
3080	//
3081	// We use (C2 - C1) as the invariant as opposed to case 1, but instead of
3082	// adding a special case in invariant creation, we can just swap the
3083	// operands here.
3084	std::swap(a&: C1, b&: C2);
3085	InvOp = Instruction::Sub;
3086	ResultOp = Instruction::Add;
3087	} else {
3088	return false;
3089	}
3090
3091	if (L.isLoopInvariant(V: LV) \|\| !L.isLoopInvariant(V: C1) \|\| !L.isLoopInvariant(V: C2))
3092	return false;
3093
3094	auto *Preheader = L.getLoopPreheader();
3095	assert(Preheader && "Loop is not in simplify form?");
3096
3097	IRBuilder<> Builder(Preheader->getTerminator());
3098	auto *Inv = Builder.CreateBinOp(Opc: InvOp, LHS: C1, RHS: C2, Name: "invariant.op");
3099
3100	auto *NewBO = BinaryOperator::Create(Op: ResultOp, S1: LV, S2: Inv,
3101	Name: I.getName() + ".reass", InsertBefore: I.getIterator());
3102	NewBO->setDebugLoc(DebugLoc::getDropped());
3103
3104	// No overflow flags are set on the new instructions -- reassociation
3105	// involving sub does not preserve nsw/nuw in general.
3106
3107	I.replaceAllUsesWith(V: NewBO);
3108	eraseInstruction(I, SafetyInfo, MSSAU);
3109
3110	salvageDebugInfo(I&: *BO);
3111	eraseInstruction(I&: *BO, SafetyInfo, MSSAU);
3112
3113	return true;
3114	}
3115
3116	static bool hoistArithmetics(Instruction &I, Loop &L,
3117	ICFLoopSafetyInfo &SafetyInfo,
3118	MemorySSAUpdater &MSSAU, AssumptionCache *AC,
3119	DominatorTree *DT) {
3120	// Optimize complex patterns, such as (x < INV1 && x < INV2), turning them
3121	// into (x < min(INV1, INV2)), and hoisting the invariant part of this
3122	// expression out of the loop.
3123	if (hoistMinMax(I, L, SafetyInfo, MSSAU)) {
3124	++NumHoisted;
3125	++NumMinMaxHoisted;
3126	return true;
3127	}
3128
3129	// Try to hoist GEPs by reassociation.
3130	if (hoistGEP(I, L, SafetyInfo, MSSAU, AC, DT)) {
3131	++NumHoisted;
3132	++NumGEPsHoisted;
3133	return true;
3134	}
3135
3136	// Try to hoist add/sub's by reassociation.
3137	if (hoistAddSub(I, L, SafetyInfo, MSSAU, AC, DT)) {
3138	++NumHoisted;
3139	++NumAddSubHoisted;
3140	return true;
3141	}
3142
3143	bool IsInt = I.getType()->isIntOrIntVectorTy();
3144	if (hoistMulAddAssociation(I, L, SafetyInfo, MSSAU, AC, DT)) {
3145	++NumHoisted;
3146	if (IsInt)
3147	++NumIntAssociationsHoisted;
3148	else
3149	++NumFPAssociationsHoisted;
3150	return true;
3151	}
3152
3153	if (hoistBOAssociation(I, L, SafetyInfo, MSSAU, AC, DT)) {
3154	++NumHoisted;
3155	++NumBOAssociationsHoisted;
3156	return true;
3157	}
3158
3159	if (hoistSubAddAssociation(I, L, SafetyInfo, MSSAU, AC, DT)) {
3160	++NumHoisted;
3161	++NumBOAssociationsHoisted;
3162	return true;
3163	}
3164
3165	return false;
3166	}
3167
3168	/// Little predicate that returns true if the specified basic block is in
3169	/// a subloop of the current one, not the current one itself.
3170	///
3171	static bool inSubLoop(BasicBlock BB, Loop CurLoop, LoopInfo *LI) {
3172	assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
3173	return LI->getLoopFor(BB) != CurLoop;
3174	}
3175

Browse the source code of llvm_projects/llvm/lib/Transforms/Scalar/LICM.cpp