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