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