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