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