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