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