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 ReciprocalDivisor->setDebugLoc(I.getDebugLoc());
937
938 auto Product =
939 BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
940 Product->setFastMathFlags(I.getFastMathFlags());
941 SafetyInfo->insertInstructionTo(Product, I.getParent());
942 Product->insertAfter(&I);
943 Product->setDebugLoc(I.getDebugLoc());
944 I.replaceAllUsesWith(Product);
945 eraseInstruction(I, *SafetyInfo, MSSAU);
946
947 hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
948 SafetyInfo, MSSAU, SE, ORE);
949 HoistedInstructions.push_back(ReciprocalDivisor);
950 Changed = true;
951 continue;
952 }
953
954 auto IsInvariantStart = [&](Instruction &I) {
955 using namespace PatternMatch;
956 return I.use_empty() &&
957 match(&I, m_Intrinsic<Intrinsic::invariant_start>());
958 };
959 auto MustExecuteWithoutWritesBefore = [&](Instruction &I) {
960 return SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop) &&
961 SafetyInfo->doesNotWriteMemoryBefore(I, CurLoop);
962 };
963 if ((IsInvariantStart(I) || isGuard(&I)) &&
964 CurLoop->hasLoopInvariantOperands(&I) &&
965 MustExecuteWithoutWritesBefore(I)) {
966 hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
967 MSSAU, SE, ORE);
968 HoistedInstructions.push_back(&I);
969 Changed = true;
970 continue;
971 }
972
973 if (PHINode *PN = dyn_cast<PHINode>(&I)) {
974 if (CFH.canHoistPHI(PN)) {
975 // Redirect incoming blocks first to ensure that we create hoisted
976 // versions of those blocks before we hoist the phi.
977 for (unsigned int i = 0; i < PN->getNumIncomingValues(); ++i)
979 i, CFH.getOrCreateHoistedBlock(PN->getIncomingBlock(i)));
980 hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
981 MSSAU, SE, ORE);
982 assert(DT->dominates(PN, BB) && "Conditional PHIs not expected");
983 Changed = true;
984 continue;
985 }
986 }
987
988 // Try to reassociate instructions so that part of computations can be
989 // done out of loop.
990 if (hoistArithmetics(I, *CurLoop, *SafetyInfo, MSSAU, AC, DT)) {
991 Changed = true;
992 continue;
993 }
994
995 // Remember possibly hoistable branches so we can actually hoist them
996 // later if needed.
997 if (BranchInst *BI = dyn_cast<BranchInst>(&I))
998 CFH.registerPossiblyHoistableBranch(BI);
999 }
1000 }
1001
1002 // If we hoisted instructions to a conditional block they may not dominate
1003 // their uses that weren't hoisted (such as phis where some operands are not
1004 // loop invariant). If so make them unconditional by moving them to their
1005 // immediate dominator. We iterate through the instructions in reverse order
1006 // which ensures that when we rehoist an instruction we rehoist its operands,
1007 // and also keep track of where in the block we are rehoisting to make sure
1008 // that we rehoist instructions before the instructions that use them.
1009 Instruction *HoistPoint = nullptr;
1010 if (ControlFlowHoisting) {
1011 for (Instruction *I : reverse(HoistedInstructions)) {
1012 if (!llvm::all_of(I->uses(),
1013 [&](Use &U) { return DT->dominates(I, U); })) {
1014 BasicBlock *Dominator =
1015 DT->getNode(I->getParent())->getIDom()->getBlock();
1016 if (!HoistPoint || !DT->dominates(HoistPoint->getParent(), Dominator)) {
1017 if (HoistPoint)
1018 assert(DT->dominates(Dominator, HoistPoint->getParent()) &&
1019 "New hoist point expected to dominate old hoist point");
1020 HoistPoint = Dominator->getTerminator();
1021 }
1022 LLVM_DEBUG(dbgs() << "LICM rehoisting to "
1023 << HoistPoint->getParent()->getNameOrAsOperand()
1024 << ": " << *I << "\n");
1025 moveInstructionBefore(*I, HoistPoint->getIterator(), *SafetyInfo, MSSAU,
1026 SE);
1027 HoistPoint = I;
1028 Changed = true;
1029 }
1030 }
1031 }
1032 if (VerifyMemorySSA)
1033 MSSAU.getMemorySSA()->verifyMemorySSA();
1034
1035 // Now that we've finished hoisting make sure that LI and DT are still
1036 // valid.
1037#ifdef EXPENSIVE_CHECKS
1038 if (Changed) {
1039 assert(DT->verify(DominatorTree::VerificationLevel::Fast) &&
1040 "Dominator tree verification failed");
1041 LI->verify(*DT);
1042 }
1043#endif
1044
1045 return Changed;
1046}
1047
1048// Return true if LI is invariant within scope of the loop. LI is invariant if
1049// CurLoop is dominated by an invariant.start representing the same memory
1050// location and size as the memory location LI loads from, and also the
1051// invariant.start has no uses.
1053 Loop *CurLoop) {
1054 Value *Addr = LI->getPointerOperand();
1055 const DataLayout &DL = LI->getModule()->getDataLayout();
1056 const TypeSize LocSizeInBits = DL.getTypeSizeInBits(LI->getType());
1057
1058 // It is not currently possible for clang to generate an invariant.start
1059 // intrinsic with scalable vector types because we don't support thread local
1060 // sizeless types and we don't permit sizeless types in structs or classes.
1061 // Furthermore, even if support is added for this in future the intrinsic
1062 // itself is defined to have a size of -1 for variable sized objects. This
1063 // makes it impossible to verify if the intrinsic envelops our region of
1064 // interest. For example, both <vscale x 32 x i8> and <vscale x 16 x i8>
1065 // types would have a -1 parameter, but the former is clearly double the size
1066 // of the latter.
1067 if (LocSizeInBits.isScalable())
1068 return false;
1069
1070 // If we've ended up at a global/constant, bail. We shouldn't be looking at
1071 // uselists for non-local Values in a loop pass.
1072 if (isa<Constant>(Addr))
1073 return false;
1074
1075 unsigned UsesVisited = 0;
1076 // Traverse all uses of the load operand value, to see if invariant.start is
1077 // one of the uses, and whether it dominates the load instruction.
1078 for (auto *U : Addr->users()) {
1079 // Avoid traversing for Load operand with high number of users.
1080 if (++UsesVisited > MaxNumUsesTraversed)
1081 return false;
1082 IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
1083 // If there are escaping uses of invariant.start instruction, the load maybe
1084 // non-invariant.
1085 if (!II || II->getIntrinsicID() != Intrinsic::invariant_start ||
1086 !II->use_empty())
1087 continue;
1088 ConstantInt *InvariantSize = cast<ConstantInt>(II->getArgOperand(0));
1089 // The intrinsic supports having a -1 argument for variable sized objects
1090 // so we should check for that here.
1091 if (InvariantSize->isNegative())
1092 continue;
1093 uint64_t InvariantSizeInBits = InvariantSize->getSExtValue() * 8;
1094 // Confirm the invariant.start location size contains the load operand size
1095 // in bits. Also, the invariant.start should dominate the load, and we
1096 // should not hoist the load out of a loop that contains this dominating
1097 // invariant.start.
1098 if (LocSizeInBits.getFixedValue() <= InvariantSizeInBits &&
1099 DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
1100 return true;
1101 }
1102
1103 return false;
1104}
1105
1106namespace {
1107/// Return true if-and-only-if we know how to (mechanically) both hoist and
1108/// sink a given instruction out of a loop. Does not address legality
1109/// concerns such as aliasing or speculation safety.
1110bool isHoistableAndSinkableInst(Instruction &I) {
1111 // Only these instructions are hoistable/sinkable.
1112 return (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
1113 isa<FenceInst>(I) || isa<CastInst>(I) || isa<UnaryOperator>(I) ||
1114 isa<BinaryOperator>(I) || isa<SelectInst>(I) ||
1115 isa<GetElementPtrInst>(I) || isa<CmpInst>(I) ||
1116 isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
1117 isa<ShuffleVectorInst>(I) || isa<ExtractValueInst>(I) ||
1118 isa<InsertValueInst>(I) || isa<FreezeInst>(I));
1119}
1120/// Return true if MSSA knows there are no MemoryDefs in the loop.
1121bool isReadOnly(const MemorySSAUpdater &MSSAU, const Loop *L) {
1122 for (auto *BB : L->getBlocks())
1123 if (MSSAU.getMemorySSA()->getBlockDefs(BB))
1124 return false;
1125 return true;
1126}
1127
1128/// Return true if I is the only Instruction with a MemoryAccess in L.
1129bool isOnlyMemoryAccess(const Instruction *I, const Loop *L,
1130 const MemorySSAUpdater &MSSAU) {
1131 for (auto *BB : L->getBlocks())
1132 if (auto *Accs = MSSAU.getMemorySSA()->getBlockAccesses(BB)) {
1133 int NotAPhi = 0;
1134 for (const auto &Acc : *Accs) {
1135 if (isa<MemoryPhi>(&Acc))
1136 continue;
1137 const auto *MUD = cast<MemoryUseOrDef>(&Acc);
1138 if (MUD->getMemoryInst() != I || NotAPhi++ == 1)
1139 return false;
1140 }
1141 }
1142 return true;
1143}
1144}
1145
1147 BatchAAResults &BAA,
1148 SinkAndHoistLICMFlags &Flags,
1149 MemoryUseOrDef *MA) {
1150 // See declaration of SetLicmMssaOptCap for usage details.
1151 if (Flags.tooManyClobberingCalls())
1152 return MA->getDefiningAccess();
1153
1154 MemoryAccess *Source =
1156 Flags.incrementClobberingCalls();
1157 return Source;
1158}
1159
1161 Loop *CurLoop, MemorySSAUpdater &MSSAU,
1162 bool TargetExecutesOncePerLoop,
1163 SinkAndHoistLICMFlags &Flags,
1165 // If we don't understand the instruction, bail early.
1166 if (!isHoistableAndSinkableInst(I))
1167 return false;
1168
1169 MemorySSA *MSSA = MSSAU.getMemorySSA();
1170 // Loads have extra constraints we have to verify before we can hoist them.
1171 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
1172 if (!LI->isUnordered())
1173 return false; // Don't sink/hoist volatile or ordered atomic loads!
1174
1175 // Loads from constant memory are always safe to move, even if they end up
1176 // in the same alias set as something that ends up being modified.
1177 if (!isModSet(AA->getModRefInfoMask(LI->getOperand(0))))
1178 return true;
1179 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1180 return true;
1181
1182 if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1183 return false; // Don't risk duplicating unordered loads
1184
1185 // This checks for an invariant.start dominating the load.
1186 if (isLoadInvariantInLoop(LI, DT, CurLoop))
1187 return true;
1188
1189 auto MU = cast<MemoryUse>(MSSA->getMemoryAccess(LI));
1190
1191 bool InvariantGroup = LI->hasMetadata(LLVMContext::MD_invariant_group);
1192
1194 MSSA, MU, CurLoop, I, Flags, InvariantGroup);
1195 // Check loop-invariant address because this may also be a sinkable load
1196 // whose address is not necessarily loop-invariant.
1197 if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1198 ORE->emit([&]() {
1200 DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
1201 << "failed to move load with loop-invariant address "
1202 "because the loop may invalidate its value";
1203 });
1204
1205 return !Invalidated;
1206 } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1207 // Don't sink or hoist dbg info; it's legal, but not useful.
1208 if (isa<DbgInfoIntrinsic>(I))
1209 return false;
1210
1211 // Don't sink calls which can throw.
1212 if (CI->mayThrow())
1213 return false;
1214
1215 // Convergent attribute has been used on operations that involve
1216 // inter-thread communication which results are implicitly affected by the
1217 // enclosing control flows. It is not safe to hoist or sink such operations
1218 // across control flow.
1219 if (CI->isConvergent())
1220 return false;
1221
1222 // FIXME: Current LLVM IR semantics don't work well with coroutines and
1223 // thread local globals. We currently treat getting the address of a thread
1224 // local global as not accessing memory, even though it may not be a
1225 // constant throughout a function with coroutines. Remove this check after
1226 // we better model semantics of thread local globals.
1227 if (CI->getFunction()->isPresplitCoroutine())
1228 return false;
1229
1230 using namespace PatternMatch;
1231 if (match(CI, m_Intrinsic<Intrinsic::assume>()))
1232 // Assumes don't actually alias anything or throw
1233 return true;
1234
1235 // Handle simple cases by querying alias analysis.
1236 MemoryEffects Behavior = AA->getMemoryEffects(CI);
1237
1238 if (Behavior.doesNotAccessMemory())
1239 return true;
1240 if (Behavior.onlyReadsMemory()) {
1241 // A readonly argmemonly function only reads from memory pointed to by
1242 // it's arguments with arbitrary offsets. If we can prove there are no
1243 // writes to this memory in the loop, we can hoist or sink.
1244 if (Behavior.onlyAccessesArgPointees()) {
1245 // TODO: expand to writeable arguments
1246 for (Value *Op : CI->args())
1247 if (Op->getType()->isPointerTy() &&
1249 MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(CI)), CurLoop, I,
1250 Flags, /*InvariantGroup=*/false))
1251 return false;
1252 return true;
1253 }
1254
1255 // If this call only reads from memory and there are no writes to memory
1256 // in the loop, we can hoist or sink the call as appropriate.
1257 if (isReadOnly(MSSAU, CurLoop))
1258 return true;
1259 }
1260
1261 // FIXME: This should use mod/ref information to see if we can hoist or
1262 // sink the call.
1263
1264 return false;
1265 } else if (auto *FI = dyn_cast<FenceInst>(&I)) {
1266 // Fences alias (most) everything to provide ordering. For the moment,
1267 // just give up if there are any other memory operations in the loop.
1268 return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
1269 } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
1270 if (!SI->isUnordered())
1271 return false; // Don't sink/hoist volatile or ordered atomic store!
1272
1273 // We can only hoist a store that we can prove writes a value which is not
1274 // read or overwritten within the loop. For those cases, we fallback to
1275 // load store promotion instead. TODO: We can extend this to cases where
1276 // there is exactly one write to the location and that write dominates an
1277 // arbitrary number of reads in the loop.
1278 if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
1279 return true;
1280 // If there are more accesses than the Promotion cap, then give up as we're
1281 // not walking a list that long.
1282 if (Flags.tooManyMemoryAccesses())
1283 return false;
1284
1285 auto *SIMD = MSSA->getMemoryAccess(SI);
1286 BatchAAResults BAA(*AA);
1287 auto *Source = getClobberingMemoryAccess(*MSSA, BAA, Flags, SIMD);
1288 // Make sure there are no clobbers inside the loop.
1289 if (!MSSA->isLiveOnEntryDef(Source) &&
1290 CurLoop->contains(Source->getBlock()))
1291 return false;
1292
1293 // If there are interfering Uses (i.e. their defining access is in the
1294 // loop), or ordered loads (stored as Defs!), don't move this store.
1295 // Could do better here, but this is conservatively correct.
1296 // TODO: Cache set of Uses on the first walk in runOnLoop, update when
1297 // moving accesses. Can also extend to dominating uses.
1298 for (auto *BB : CurLoop->getBlocks())
1299 if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
1300 for (const auto &MA : *Accesses)
1301 if (const auto *MU = dyn_cast<MemoryUse>(&MA)) {
1302 auto *MD = getClobberingMemoryAccess(*MSSA, BAA, Flags,
1303 const_cast<MemoryUse *>(MU));
1304 if (!MSSA->isLiveOnEntryDef(MD) &&
1305 CurLoop->contains(MD->getBlock()))
1306 return false;
1307 // Disable hoisting past potentially interfering loads. Optimized
1308 // Uses may point to an access outside the loop, as getClobbering
1309 // checks the previous iteration when walking the backedge.
1310 // FIXME: More precise: no Uses that alias SI.
1311 if (!Flags.getIsSink() && !MSSA->dominates(SIMD, MU))
1312 return false;
1313 } else if (const auto *MD = dyn_cast<MemoryDef>(&MA)) {
1314 if (auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
1315 (void)LI; // Silence warning.
1316 assert(!LI->isUnordered() && "Expected unordered load");
1317 return false;
1318 }
1319 // Any call, while it may not be clobbering SI, it may be a use.
1320 if (auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
1321 // Check if the call may read from the memory location written
1322 // to by SI. Check CI's attributes and arguments; the number of
1323 // such checks performed is limited above by NoOfMemAccTooLarge.
1325 if (isModOrRefSet(MRI))
1326 return false;
1327 }
1328 }
1329 }
1330 return true;
1331 }
1332
1333 assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
1334
1335 // We've established mechanical ability and aliasing, it's up to the caller
1336 // to check fault safety
1337 return true;
1338}
1339
1340/// Returns true if a PHINode is a trivially replaceable with an
1341/// Instruction.
1342/// This is true when all incoming values are that instruction.
1343/// This pattern occurs most often with LCSSA PHI nodes.
1344///
1345static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I) {
1346 for (const Value *IncValue : PN.incoming_values())
1347 if (IncValue != &I)
1348 return false;
1349
1350 return true;
1351}
1352
1353/// Return true if the instruction is foldable in the loop.
1354static bool isFoldableInLoop(const Instruction &I, const Loop *CurLoop,
1355 const TargetTransformInfo *TTI) {
1356 if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1357 InstructionCost CostI =
1359 if (CostI != TargetTransformInfo::TCC_Free)
1360 return false;
1361 // For a GEP, we cannot simply use getInstructionCost because currently
1362 // it optimistically assumes that a GEP will fold into addressing mode
1363 // regardless of its users.
1364 const BasicBlock *BB = GEP->getParent();
1365 for (const User *U : GEP->users()) {
1366 const Instruction *UI = cast<Instruction>(U);
1367 if (CurLoop->contains(UI) &&
1368 (BB != UI->getParent() ||
1369 (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1370 return false;
1371 }
1372 return true;
1373 }
1374
1375 return false;
1376}
1377
1378/// Return true if the only users of this instruction are outside of
1379/// the loop. If this is true, we can sink the instruction to the exit
1380/// blocks of the loop.
1381///
1382/// We also return true if the instruction could be folded away in lowering.
1383/// (e.g., a GEP can be folded into a load as an addressing mode in the loop).
1384static bool isNotUsedOrFoldableInLoop(const Instruction &I, const Loop *CurLoop,
1385 const LoopSafetyInfo *SafetyInfo,
1387 bool &FoldableInLoop, bool LoopNestMode) {
1388 const auto &BlockColors = SafetyInfo->getBlockColors();
1389 bool IsFoldable = isFoldableInLoop(I, CurLoop, TTI);
1390 for (const User *U : I.users()) {
1391 const Instruction *UI = cast<Instruction>(U);
1392 if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
1393 const BasicBlock *BB = PN->getParent();
1394 // We cannot sink uses in catchswitches.
1395 if (isa<CatchSwitchInst>(BB->getTerminator()))
1396 return false;
1397
1398 // We need to sink a callsite to a unique funclet. Avoid sinking if the
1399 // phi use is too muddled.
1400 if (isa<CallInst>(I))
1401 if (!BlockColors.empty() &&
1402 BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
1403 return false;
1404
1405 if (LoopNestMode) {
1406 while (isa<PHINode>(UI) && UI->hasOneUser() &&
1407 UI->getNumOperands() == 1) {
1408 if (!CurLoop->contains(UI))
1409 break;
1410 UI = cast<Instruction>(UI->user_back());
1411 }
1412 }
1413 }
1414
1415 if (CurLoop->contains(UI)) {
1416 if (IsFoldable) {
1417 FoldableInLoop = true;
1418 continue;
1419 }
1420 return false;
1421 }
1422 }
1423 return true;
1424}
1425
1427 Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
1428 const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU) {
1429 Instruction *New;
1430 if (auto *CI = dyn_cast<CallInst>(&I)) {
1431 const auto &BlockColors = SafetyInfo->getBlockColors();
1432
1433 // Sinking call-sites need to be handled differently from other
1434 // instructions. The cloned call-site needs a funclet bundle operand
1435 // appropriate for its location in the CFG.
1437 for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1438 BundleIdx != BundleEnd; ++BundleIdx) {
1439 OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
1440 if (Bundle.getTagID() == LLVMContext::OB_funclet)
1441 continue;
1442
1443 OpBundles.emplace_back(Bundle);
1444 }
1445
1446 if (!BlockColors.empty()) {
1447 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1448 assert(CV.size() == 1 && "non-unique color for exit block!");
1449 BasicBlock *BBColor = CV.front();
1450 Instruction *EHPad = BBColor->getFirstNonPHI();
1451 if (EHPad->isEHPad())
1452 OpBundles.emplace_back("funclet", EHPad);
1453 }
1454
1455 New = CallInst::Create(CI, OpBundles);
1456 } else {
1457 New = I.clone();
1458 }
1459
1460 New->insertInto(&ExitBlock, ExitBlock.getFirstInsertionPt());
1461 if (!I.getName().empty())
1462 New->setName(I.getName() + ".le");
1463
1464 if (MSSAU.getMemorySSA()->getMemoryAccess(&I)) {
1465 // Create a new MemoryAccess and let MemorySSA set its defining access.
1466 MemoryAccess *NewMemAcc = MSSAU.createMemoryAccessInBB(
1467 New, nullptr, New->getParent(), MemorySSA::Beginning);
1468 if (NewMemAcc) {
1469 if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1470 MSSAU.insertDef(MemDef, /*RenameUses=*/true);
1471 else {
1472 auto *MemUse = cast<MemoryUse>(NewMemAcc);
1473 MSSAU.insertUse(MemUse, /*RenameUses=*/true);
1474 }
1475 }
1476 }
1477
1478 // Build LCSSA PHI nodes for any in-loop operands (if legal). Note that
1479 // this is particularly cheap because we can rip off the PHI node that we're
1480 // replacing for the number and blocks of the predecessors.
1481 // OPT: If this shows up in a profile, we can instead finish sinking all
1482 // invariant instructions, and then walk their operands to re-establish
1483 // LCSSA. That will eliminate creating PHI nodes just to nuke them when
1484 // sinking bottom-up.
1485 for (Use &Op : New->operands())
1486 if (LI->wouldBeOutOfLoopUseRequiringLCSSA(Op.get(), PN.getParent())) {
1487 auto *OInst = cast<Instruction>(Op.get());
1488 PHINode *OpPN =
1489 PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
1490 OInst->getName() + ".lcssa");
1491 OpPN->insertBefore(ExitBlock.begin());
1492 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1493 OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
1494 Op = OpPN;
1495 }
1496 return New;
1497}
1498
1500 MemorySSAUpdater &MSSAU) {
1501 MSSAU.removeMemoryAccess(&I);
1502 SafetyInfo.removeInstruction(&I);
1503 I.eraseFromParent();
1504}
1505
1507 ICFLoopSafetyInfo &SafetyInfo,
1508 MemorySSAUpdater &MSSAU,
1509 ScalarEvolution *SE) {
1510 SafetyInfo.removeInstruction(&I);
1511 SafetyInfo.insertInstructionTo(&I, Dest->getParent());
1512 I.moveBefore(*Dest->getParent(), Dest);
1513 if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
1514 MSSAU.getMemorySSA()->getMemoryAccess(&I)))
1515 MSSAU.moveToPlace(OldMemAcc, Dest->getParent(),
1517 if (SE)
1519}
1520
1522 PHINode *TPN, Instruction *I, LoopInfo *LI,
1524 const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop,
1525 MemorySSAUpdater &MSSAU) {
1527 "Expect only trivially replaceable PHI");
1528 BasicBlock *ExitBlock = TPN->getParent();
1529 Instruction *New;
1530 auto It = SunkCopies.find(ExitBlock);
1531 if (It != SunkCopies.end())
1532 New = It->second;
1533 else
1534 New = SunkCopies[ExitBlock] = cloneInstructionInExitBlock(
1535 *I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1536 return New;
1537}
1538
1539static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo) {
1540 BasicBlock *BB = PN->getParent();
1541 if (!BB->canSplitPredecessors())
1542 return false;
1543 // It's not impossible to split EHPad blocks, but if BlockColors already exist
1544 // it require updating BlockColors for all offspring blocks accordingly. By
1545 // skipping such corner case, we can make updating BlockColors after splitting
1546 // predecessor fairly simple.
1547 if (!SafetyInfo->getBlockColors().empty() && BB->getFirstNonPHI()->isEHPad())
1548 return false;
1549 for (BasicBlock *BBPred : predecessors(BB)) {
1550 if (isa<IndirectBrInst>(BBPred->getTerminator()))
1551 return false;
1552 }
1553 return true;
1554}
1555
1557 LoopInfo *LI, const Loop *CurLoop,
1558 LoopSafetyInfo *SafetyInfo,
1559 MemorySSAUpdater *MSSAU) {
1560#ifndef NDEBUG
1562 CurLoop->getUniqueExitBlocks(ExitBlocks);
1563 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1564 ExitBlocks.end());
1565#endif
1566 BasicBlock *ExitBB = PN->getParent();
1567 assert(ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block.");
1568
1569 // Split predecessors of the loop exit to make instructions in the loop are
1570 // exposed to exit blocks through trivially replaceable PHIs while keeping the
1571 // loop in the canonical form where each predecessor of each exit block should
1572 // be contained within the loop. For example, this will convert the loop below
1573 // from
1574 //
1575 // LB1:
1576 // %v1 =
1577 // br %LE, %LB2
1578 // LB2:
1579 // %v2 =
1580 // br %LE, %LB1
1581 // LE:
1582 // %p = phi [%v1, %LB1], [%v2, %LB2] <-- non-trivially replaceable
1583 //
1584 // to
1585 //
1586 // LB1:
1587 // %v1 =
1588 // br %LE.split, %LB2
1589 // LB2:
1590 // %v2 =
1591 // br %LE.split2, %LB1
1592 // LE.split:
1593 // %p1 = phi [%v1, %LB1] <-- trivially replaceable
1594 // br %LE
1595 // LE.split2:
1596 // %p2 = phi [%v2, %LB2] <-- trivially replaceable
1597 // br %LE
1598 // LE:
1599 // %p = phi [%p1, %LE.split], [%p2, %LE.split2]
1600 //
1601 const auto &BlockColors = SafetyInfo->getBlockColors();
1602 SmallSetVector<BasicBlock *, 8> PredBBs(pred_begin(ExitBB), pred_end(ExitBB));
1603 while (!PredBBs.empty()) {
1604 BasicBlock *PredBB = *PredBBs.begin();
1605 assert(CurLoop->contains(PredBB) &&
1606 "Expect all predecessors are in the loop");
1607 if (PN->getBasicBlockIndex(PredBB) >= 0) {
1609 ExitBB, PredBB, ".split.loop.exit", DT, LI, MSSAU, true);
1610 // Since we do not allow splitting EH-block with BlockColors in
1611 // canSplitPredecessors(), we can simply assign predecessor's color to
1612 // the new block.
1613 if (!BlockColors.empty())
1614 // Grab a reference to the ColorVector to be inserted before getting the
1615 // reference to the vector we are copying because inserting the new
1616 // element in BlockColors might cause the map to be reallocated.
1617 SafetyInfo->copyColors(NewPred, PredBB);
1618 }
1619 PredBBs.remove(PredBB);
1620 }
1621}
1622
1623/// When an instruction is found to only be used outside of the loop, this
1624/// function moves it to the exit blocks and patches up SSA form as needed.
1625/// This method is guaranteed to remove the original instruction from its
1626/// position, and may either delete it or move it to outside of the loop.
1627///
1628static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
1629 const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
1631 bool Changed = false;
1632 LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
1633
1634 // Iterate over users to be ready for actual sinking. Replace users via
1635 // unreachable blocks with undef and make all user PHIs trivially replaceable.
1636 SmallPtrSet<Instruction *, 8> VisitedUsers;
1637 for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
1638 auto *User = cast<Instruction>(*UI);
1639 Use &U = UI.getUse();
1640 ++UI;
1641
1642 if (VisitedUsers.count(User) || CurLoop->contains(User))
1643 continue;
1644
1645 if (!DT->isReachableFromEntry(User->getParent())) {
1646 U = PoisonValue::get(I.getType());
1647 Changed = true;
1648 continue;
1649 }
1650
1651 // The user must be a PHI node.
1652 PHINode *PN = cast<PHINode>(User);
1653
1654 // Surprisingly, instructions can be used outside of loops without any
1655 // exits. This can only happen in PHI nodes if the incoming block is
1656 // unreachable.
1657 BasicBlock *BB = PN->getIncomingBlock(U);
1658 if (!DT->isReachableFromEntry(BB)) {
1659 U = PoisonValue::get(I.getType());
1660 Changed = true;
1661 continue;
1662 }
1663
1664 VisitedUsers.insert(PN);
1665 if (isTriviallyReplaceablePHI(*PN, I))
1666 continue;
1667
1668 if (!canSplitPredecessors(PN, SafetyInfo))
1669 return Changed;
1670
1671 // Split predecessors of the PHI so that we can make users trivially
1672 // replaceable.
1673 splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo, &MSSAU);
1674
1675 // Should rebuild the iterators, as they may be invalidated by
1676 // splitPredecessorsOfLoopExit().
1677 UI = I.user_begin();
1678 UE = I.user_end();
1679 }
1680
1681 if (VisitedUsers.empty())
1682 return Changed;
1683
1684 ORE->emit([&]() {
1685 return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
1686 << "sinking " << ore::NV("Inst", &I);
1687 });
1688 if (isa<LoadInst>(I))
1689 ++NumMovedLoads;
1690 else if (isa<CallInst>(I))
1691 ++NumMovedCalls;
1692 ++NumSunk;
1693
1694#ifndef NDEBUG
1696 CurLoop->getUniqueExitBlocks(ExitBlocks);
1697 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1698 ExitBlocks.end());
1699#endif
1700
1701 // Clones of this instruction. Don't create more than one per exit block!
1703
1704 // If this instruction is only used outside of the loop, then all users are
1705 // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
1706 // the instruction.
1707 // First check if I is worth sinking for all uses. Sink only when it is worth
1708 // across all uses.
1709 SmallSetVector<User*, 8> Users(I.user_begin(), I.user_end());
1710 for (auto *UI : Users) {
1711 auto *User = cast<Instruction>(UI);
1712
1713 if (CurLoop->contains(User))
1714 continue;
1715
1716 PHINode *PN = cast<PHINode>(User);
1717 assert(ExitBlockSet.count(PN->getParent()) &&
1718 "The LCSSA PHI is not in an exit block!");
1719
1720 // The PHI must be trivially replaceable.
1722 PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1723 // As we sink the instruction out of the BB, drop its debug location.
1724 New->dropLocation();
1725 PN->replaceAllUsesWith(New);
1726 eraseInstruction(*PN, *SafetyInfo, MSSAU);
1727 Changed = true;
1728 }
1729 return Changed;
1730}
1731
1732/// When an instruction is found to only use loop invariant operands that
1733/// is safe to hoist, this instruction is called to do the dirty work.
1734///
1735static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
1736 BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
1739 LLVM_DEBUG(dbgs() << "LICM hoisting to " << Dest->getNameOrAsOperand() << ": "
1740 << I << "\n");
1741 ORE->emit([&]() {
1742 return OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting "
1743 << ore::NV("Inst", &I);
1744 });
1745
1746 // Metadata can be dependent on conditions we are hoisting above.
1747 // Conservatively strip all metadata on the instruction unless we were
1748 // guaranteed to execute I if we entered the loop, in which case the metadata
1749 // is valid in the loop preheader.
1750 // Similarly, If I is a call and it is not guaranteed to execute in the loop,
1751 // then moving to the preheader means we should strip attributes on the call
1752 // that can cause UB since we may be hoisting above conditions that allowed
1753 // inferring those attributes. They may not be valid at the preheader.
1754 if ((I.hasMetadataOtherThanDebugLoc() || isa<CallInst>(I)) &&
1755 // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
1756 // time in isGuaranteedToExecute if we don't actually have anything to
1757 // drop. It is a compile time optimization, not required for correctness.
1758 !SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop))
1759 I.dropUBImplyingAttrsAndMetadata();
1760
1761 if (isa<PHINode>(I))
1762 // Move the new node to the end of the phi list in the destination block.
1763 moveInstructionBefore(I, Dest->getFirstNonPHIIt(), *SafetyInfo, MSSAU, SE);
1764 else
1765 // Move the new node to the destination block, before its terminator.
1766 moveInstructionBefore(I, Dest->getTerminator()->getIterator(), *SafetyInfo,
1767 MSSAU, SE);
1768
1769 I.updateLocationAfterHoist();
1770
1771 if (isa<LoadInst>(I))
1772 ++NumMovedLoads;
1773 else if (isa<CallInst>(I))
1774 ++NumMovedCalls;
1775 ++NumHoisted;
1776}
1777
1778/// Only sink or hoist an instruction if it is not a trapping instruction,
1779/// or if the instruction is known not to trap when moved to the preheader.
1780/// or if it is a trapping instruction and is guaranteed to execute.
1782 Instruction &Inst, const DominatorTree *DT, const TargetLibraryInfo *TLI,
1783 const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo,
1784 OptimizationRemarkEmitter *ORE, const Instruction *CtxI,
1785 AssumptionCache *AC, bool AllowSpeculation) {
1786 if (AllowSpeculation &&
1787 isSafeToSpeculativelyExecute(&Inst, CtxI, AC, DT, TLI))
1788 return true;
1789
1790 bool GuaranteedToExecute =
1791 SafetyInfo->isGuaranteedToExecute(Inst, DT, CurLoop);
1792
1793 if (!GuaranteedToExecute) {
1794 auto *LI = dyn_cast<LoadInst>(&Inst);
1795 if (LI && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1796 ORE->emit([&]() {
1798 DEBUG_TYPE, "LoadWithLoopInvariantAddressCondExecuted", LI)
1799 << "failed to hoist load with loop-invariant address "
1800 "because load is conditionally executed";
1801 });
1802 }
1803
1804 return GuaranteedToExecute;
1805}
1806
1807namespace {
1808class LoopPromoter : public LoadAndStorePromoter {
1809 Value *SomePtr; // Designated pointer to store to.
1810 SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
1812 SmallVectorImpl<MemoryAccess *> &MSSAInsertPts;
1813 PredIteratorCache &PredCache;
1814 MemorySSAUpdater &MSSAU;
1815 LoopInfo &LI;
1816 DebugLoc DL;
1817 Align Alignment;
1818 bool UnorderedAtomic;
1819 AAMDNodes AATags;
1820 ICFLoopSafetyInfo &SafetyInfo;
1821 bool CanInsertStoresInExitBlocks;
1823
1824 // We're about to add a use of V in a loop exit block. Insert an LCSSA phi
1825 // (if legal) if doing so would add an out-of-loop use to an instruction
1826 // defined in-loop.
1827 Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
1828 if (!LI.wouldBeOutOfLoopUseRequiringLCSSA(V, BB))
1829 return V;
1830
1831 Instruction *I = cast<Instruction>(V);
1832 // We need to create an LCSSA PHI node for the incoming value and
1833 // store that.
1834 PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
1835 I->getName() + ".lcssa");
1836 PN->insertBefore(BB->begin());
1837 for (BasicBlock *Pred : PredCache.get(BB))
1838 PN->addIncoming(I, Pred);
1839 return PN;
1840 }
1841
1842public:
1843 LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
1847 MemorySSAUpdater &MSSAU, LoopInfo &li, DebugLoc dl,
1848 Align Alignment, bool UnorderedAtomic, const AAMDNodes &AATags,
1849 ICFLoopSafetyInfo &SafetyInfo, bool CanInsertStoresInExitBlocks)
1850 : LoadAndStorePromoter(Insts, S), SomePtr(SP), LoopExitBlocks(LEB),
1851 LoopInsertPts(LIP), MSSAInsertPts(MSSAIP), PredCache(PIC), MSSAU(MSSAU),
1852 LI(li), DL(std::move(dl)), Alignment(Alignment),
1853 UnorderedAtomic(UnorderedAtomic), AATags(AATags),
1854 SafetyInfo(SafetyInfo),
1855 CanInsertStoresInExitBlocks(CanInsertStoresInExitBlocks), Uses(Insts) {}
1856
1857 void insertStoresInLoopExitBlocks() {
1858 // Insert stores after in the loop exit blocks. Each exit block gets a
1859 // store of the live-out values that feed them. Since we've already told
1860 // the SSA updater about the defs in the loop and the preheader
1861 // definition, it is all set and we can start using it.
1862 DIAssignID *NewID = nullptr;
1863 for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
1864 BasicBlock *ExitBlock = LoopExitBlocks[i];
1865 Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
1866 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1867 Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1868 BasicBlock::iterator InsertPos = LoopInsertPts[i];
1869 StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
1870 if (UnorderedAtomic)
1871 NewSI->setOrdering(AtomicOrdering::Unordered);
1872 NewSI->setAlignment(Alignment);
1873 NewSI->setDebugLoc(DL);
1874 // Attach DIAssignID metadata to the new store, generating it on the
1875 // first loop iteration.
1876 if (i == 0) {
1877 // NewSI will have its DIAssignID set here if there are any stores in
1878 // Uses with a DIAssignID attachment. This merged ID will then be
1879 // attached to the other inserted stores (in the branch below).
1880 NewSI->mergeDIAssignID(Uses);
1881 NewID = cast_or_null<DIAssignID>(
1882 NewSI->getMetadata(LLVMContext::MD_DIAssignID));
1883 } else {
1884 // Attach the DIAssignID (or nullptr) merged from Uses in the branch
1885 // above.
1886 NewSI->setMetadata(LLVMContext::MD_DIAssignID, NewID);
1887 }
1888
1889 if (AATags)
1890 NewSI->setAAMetadata(AATags);
1891
1892 MemoryAccess *MSSAInsertPoint = MSSAInsertPts[i];
1893 MemoryAccess *NewMemAcc;
1894 if (!MSSAInsertPoint) {
1895 NewMemAcc = MSSAU.createMemoryAccessInBB(
1896 NewSI, nullptr, NewSI->getParent(), MemorySSA::Beginning);
1897 } else {
1898 NewMemAcc =
1899 MSSAU.createMemoryAccessAfter(NewSI, nullptr, MSSAInsertPoint);
1900 }
1901 MSSAInsertPts[i] = NewMemAcc;
1902 MSSAU.insertDef(cast<MemoryDef>(NewMemAcc), true);
1903 // FIXME: true for safety, false may still be correct.
1904 }
1905 }
1906
1907 void doExtraRewritesBeforeFinalDeletion() override {
1908 if (CanInsertStoresInExitBlocks)
1909 insertStoresInLoopExitBlocks();
1910 }
1911
1912 void instructionDeleted(Instruction *I) const override {
1913 SafetyInfo.removeInstruction(I);
1914 MSSAU.removeMemoryAccess(I);
1915 }
1916
1917 bool shouldDelete(Instruction *I) const override {
1918 if (isa<StoreInst>(I))
1919 return CanInsertStoresInExitBlocks;
1920 return true;
1921 }
1922};
1923
1924bool isNotCapturedBeforeOrInLoop(const Value *V, const Loop *L,
1925 DominatorTree *DT) {
1926 // We can perform the captured-before check against any instruction in the
1927 // loop header, as the loop header is reachable from any instruction inside
1928 // the loop.
1929 // TODO: ReturnCaptures=true shouldn't be necessary here.
1930 return !PointerMayBeCapturedBefore(V, /* ReturnCaptures */ true,
1931 /* StoreCaptures */ true,
1932 L->getHeader()->getTerminator(), DT);
1933}
1934
1935/// Return true if we can prove that a caller cannot inspect the object if an
1936/// unwind occurs inside the loop.
1937bool isNotVisibleOnUnwindInLoop(const Value *Object, const Loop *L,
1938 DominatorTree *DT) {
1939 bool RequiresNoCaptureBeforeUnwind;
1940 if (!isNotVisibleOnUnwind(Object, RequiresNoCaptureBeforeUnwind))
1941 return false;
1942
1943 return !RequiresNoCaptureBeforeUnwind ||
1944 isNotCapturedBeforeOrInLoop(Object, L, DT);
1945}
1946
1947bool isThreadLocalObject(const Value *Object, const Loop *L, DominatorTree *DT,
1949 // The object must be function-local to start with, and then not captured
1950 // before/in the loop.
1951 return (isIdentifiedFunctionLocal(Object) &&
1952 isNotCapturedBeforeOrInLoop(Object, L, DT)) ||
1954}
1955
1956} // namespace
1957
1958/// Try to promote memory values to scalars by sinking stores out of the
1959/// loop and moving loads to before the loop. We do this by looping over
1960/// the stores in the loop, looking for stores to Must pointers which are
1961/// loop invariant.
1962///
1964 const SmallSetVector<Value *, 8> &PointerMustAliases,
1969 const TargetLibraryInfo *TLI, TargetTransformInfo *TTI, Loop *CurLoop,
1970 MemorySSAUpdater &MSSAU, ICFLoopSafetyInfo *SafetyInfo,
1971 OptimizationRemarkEmitter *ORE, bool AllowSpeculation,
1972 bool HasReadsOutsideSet) {
1973 // Verify inputs.
1974 assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
1975 SafetyInfo != nullptr &&
1976 "Unexpected Input to promoteLoopAccessesToScalars");
1977
1978 LLVM_DEBUG({
1979 dbgs() << "Trying to promote set of must-aliased pointers:\n";
1980 for (Value *Ptr : PointerMustAliases)
1981 dbgs() << " " << *Ptr << "\n";
1982 });
1983 ++NumPromotionCandidates;
1984
1985 Value *SomePtr = *PointerMustAliases.begin();
1986 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1987
1988 // It is not safe to promote a load/store from the loop if the load/store is
1989 // conditional. For example, turning:
1990 //
1991 // for () { if (c) *P += 1; }
1992 //
1993 // into:
1994 //
1995 // tmp = *P; for () { if (c) tmp +=1; } *P = tmp;
1996 //
1997 // is not safe, because *P may only be valid to access if 'c' is true.
1998 //
1999 // The safety property divides into two parts:
2000 // p1) The memory may not be dereferenceable on entry to the loop. In this
2001 // case, we can't insert the required load in the preheader.
2002 // p2) The memory model does not allow us to insert a store along any dynamic
2003 // path which did not originally have one.
2004 //
2005 // If at least one store is guaranteed to execute, both properties are
2006 // satisfied, and promotion is legal.
2007 //
2008 // This, however, is not a necessary condition. Even if no store/load is
2009 // guaranteed to execute, we can still establish these properties.
2010 // We can establish (p1) by proving that hoisting the load into the preheader
2011 // is safe (i.e. proving dereferenceability on all paths through the loop). We
2012 // can use any access within the alias set to prove dereferenceability,
2013 // since they're all must alias.
2014 //
2015 // There are two ways establish (p2):
2016 // a) Prove the location is thread-local. In this case the memory model
2017 // requirement does not apply, and stores are safe to insert.
2018 // b) Prove a store dominates every exit block. In this case, if an exit
2019 // blocks is reached, the original dynamic path would have taken us through
2020 // the store, so inserting a store into the exit block is safe. Note that this
2021 // is different from the store being guaranteed to execute. For instance,
2022 // if an exception is thrown on the first iteration of the loop, the original
2023 // store is never executed, but the exit blocks are not executed either.
2024
2025 bool DereferenceableInPH = false;
2026 bool StoreIsGuanteedToExecute = false;
2027 bool FoundLoadToPromote = false;
2028 // Goes from Unknown to either Safe or Unsafe, but can't switch between them.
2029 enum {
2030 StoreSafe,
2031 StoreUnsafe,
2032 StoreSafetyUnknown,
2033 } StoreSafety = StoreSafetyUnknown;
2034
2036
2037 // We start with an alignment of one and try to find instructions that allow
2038 // us to prove better alignment.
2039 Align Alignment;
2040 // Keep track of which types of access we see
2041 bool SawUnorderedAtomic = false;
2042 bool SawNotAtomic = false;
2043 AAMDNodes AATags;
2044
2045 const DataLayout &MDL = Preheader->getModule()->getDataLayout();
2046
2047 // If there are reads outside the promoted set, then promoting stores is
2048 // definitely not safe.
2049 if (HasReadsOutsideSet)
2050 StoreSafety = StoreUnsafe;
2051
2052 if (StoreSafety == StoreSafetyUnknown && SafetyInfo->anyBlockMayThrow()) {
2053 // If a loop can throw, we have to insert a store along each unwind edge.
2054 // That said, we can't actually make the unwind edge explicit. Therefore,
2055 // we have to prove that the store is dead along the unwind edge. We do
2056 // this by proving that the caller can't have a reference to the object
2057 // after return and thus can't possibly load from the object.
2058 Value *Object = getUnderlyingObject(SomePtr);
2059 if (!isNotVisibleOnUnwindInLoop(Object, CurLoop, DT))
2060 StoreSafety = StoreUnsafe;
2061 }
2062
2063 // Check that all accesses to pointers in the alias set use the same type.
2064 // We cannot (yet) promote a memory location that is loaded and stored in
2065 // different sizes. While we are at it, collect alignment and AA info.
2066 Type *AccessTy = nullptr;
2067 for (Value *ASIV : PointerMustAliases) {
2068 for (Use &U : ASIV->uses()) {
2069 // Ignore instructions that are outside the loop.
2070 Instruction *UI = dyn_cast<Instruction>(U.getUser());
2071 if (!UI || !CurLoop->contains(UI))
2072 continue;
2073
2074 // If there is an non-load/store instruction in the loop, we can't promote
2075 // it.
2076 if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
2077 if (!Load->isUnordered())
2078 return false;
2079
2080 SawUnorderedAtomic |= Load->isAtomic();
2081 SawNotAtomic |= !Load->isAtomic();
2082 FoundLoadToPromote = true;
2083
2084 Align InstAlignment = Load->getAlign();
2085
2086 // Note that proving a load safe to speculate requires proving
2087 // sufficient alignment at the target location. Proving it guaranteed
2088 // to execute does as well. Thus we can increase our guaranteed
2089 // alignment as well.
2090 if (!DereferenceableInPH || (InstAlignment > Alignment))
2092 *Load, DT, TLI, CurLoop, SafetyInfo, ORE,
2093 Preheader->getTerminator(), AC, AllowSpeculation)) {
2094 DereferenceableInPH = true;
2095 Alignment = std::max(Alignment, InstAlignment);
2096 }
2097 } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
2098 // Stores *of* the pointer are not interesting, only stores *to* the
2099 // pointer.
2100 if (U.getOperandNo() != StoreInst::getPointerOperandIndex())
2101 continue;
2102 if (!Store->isUnordered())
2103 return false;
2104
2105 SawUnorderedAtomic |= Store->isAtomic();
2106 SawNotAtomic |= !Store->isAtomic();
2107
2108 // If the store is guaranteed to execute, both properties are satisfied.
2109 // We may want to check if a store is guaranteed to execute even if we
2110 // already know that promotion is safe, since it may have higher
2111 // alignment than any other guaranteed stores, in which case we can
2112 // raise the alignment on the promoted store.
2113 Align InstAlignment = Store->getAlign();
2114 bool GuaranteedToExecute =
2115 SafetyInfo->isGuaranteedToExecute(*UI, DT, CurLoop);
2116 StoreIsGuanteedToExecute |= GuaranteedToExecute;
2117 if (GuaranteedToExecute) {
2118 DereferenceableInPH = true;
2119 if (StoreSafety == StoreSafetyUnknown)
2120 StoreSafety = StoreSafe;
2121 Alignment = std::max(Alignment, InstAlignment);
2122 }
2123
2124 // If a store dominates all exit blocks, it is safe to sink.
2125 // As explained above, if an exit block was executed, a dominating
2126 // store must have been executed at least once, so we are not
2127 // introducing stores on paths that did not have them.
2128 // Note that this only looks at explicit exit blocks. If we ever
2129 // start sinking stores into unwind edges (see above), this will break.
2130 if (StoreSafety == StoreSafetyUnknown &&
2131 llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
2132 return DT->dominates(Store->getParent(), Exit);
2133 }))
2134 StoreSafety = StoreSafe;
2135
2136 // If the store is not guaranteed to execute, we may still get
2137 // deref info through it.
2138 if (!DereferenceableInPH) {
2139 DereferenceableInPH = isDereferenceableAndAlignedPointer(
2140 Store->getPointerOperand(), Store->getValueOperand()->getType(),
2141 Store->getAlign(), MDL, Preheader->getTerminator(), AC, DT, TLI);
2142 }
2143 } else
2144 continue; // Not a load or store.
2145
2146 if (!AccessTy)
2147 AccessTy = getLoadStoreType(UI);
2148 else if (AccessTy != getLoadStoreType(UI))
2149 return false;
2150
2151 // Merge the AA tags.
2152 if (LoopUses.empty()) {
2153 // On the first load/store, just take its AA tags.
2154 AATags = UI->getAAMetadata();
2155 } else if (AATags) {
2156 AATags = AATags.merge(UI->getAAMetadata());
2157 }
2158
2159 LoopUses.push_back(UI);
2160 }
2161 }
2162
2163 // If we found both an unordered atomic instruction and a non-atomic memory
2164 // access, bail. We can't blindly promote non-atomic to atomic since we
2165 // might not be able to lower the result. We can't downgrade since that
2166 // would violate memory model. Also, align 0 is an error for atomics.
2167 if (SawUnorderedAtomic && SawNotAtomic)
2168 return false;
2169
2170 // If we're inserting an atomic load in the preheader, we must be able to
2171 // lower it. We're only guaranteed to be able to lower naturally aligned
2172 // atomics.
2173 if (SawUnorderedAtomic && Alignment < MDL.getTypeStoreSize(AccessTy))
2174 return false;
2175
2176 // If we couldn't prove we can hoist the load, bail.
2177 if (!DereferenceableInPH) {
2178 LLVM_DEBUG(dbgs() << "Not promoting: Not dereferenceable in preheader\n");
2179 return false;
2180 }
2181
2182 // We know we can hoist the load, but don't have a guaranteed store.
2183 // Check whether the location is writable and thread-local. If it is, then we
2184 // can insert stores along paths which originally didn't have them without
2185 // violating the memory model.
2186 if (StoreSafety == StoreSafetyUnknown) {
2187 Value *Object = getUnderlyingObject(SomePtr);
2188 bool ExplicitlyDereferenceableOnly;
2189 if (isWritableObject(Object, ExplicitlyDereferenceableOnly) &&
2190 (!ExplicitlyDereferenceableOnly ||
2191 isDereferenceablePointer(SomePtr, AccessTy, MDL)) &&
2192 isThreadLocalObject(Object, CurLoop, DT, TTI))
2193 StoreSafety = StoreSafe;
2194 }
2195
2196 // If we've still failed to prove we can sink the store, hoist the load
2197 // only, if possible.
2198 if (StoreSafety != StoreSafe && !FoundLoadToPromote)
2199 // If we cannot hoist the load either, give up.
2200 return false;
2201
2202 // Lets do the promotion!
2203 if (StoreSafety == StoreSafe) {
2204 LLVM_DEBUG(dbgs() << "LICM: Promoting load/store of the value: " << *SomePtr
2205 << '\n');
2206 ++NumLoadStorePromoted;
2207 } else {
2208 LLVM_DEBUG(dbgs() << "LICM: Promoting load of the value: " << *SomePtr
2209 << '\n');
2210 ++NumLoadPromoted;
2211 }
2212
2213 ORE->emit([&]() {
2214 return OptimizationRemark(DEBUG_TYPE, "PromoteLoopAccessesToScalar",
2215 LoopUses[0])
2216 << "Moving accesses to memory location out of the loop";
2217 });
2218
2219 // Look at all the loop uses, and try to merge their locations.
2220 std::vector<DILocation *> LoopUsesLocs;
2221 for (auto *U : LoopUses)
2222 LoopUsesLocs.push_back(U->getDebugLoc().get());
2223 auto DL = DebugLoc(DILocation::getMergedLocations(LoopUsesLocs));
2224
2225 // We use the SSAUpdater interface to insert phi nodes as required.
2227 SSAUpdater SSA(&NewPHIs);
2228 LoopPromoter Promoter(SomePtr, LoopUses, SSA, ExitBlocks, InsertPts,
2229 MSSAInsertPts, PIC, MSSAU, *LI, DL, Alignment,
2230 SawUnorderedAtomic, AATags, *SafetyInfo,
2231 StoreSafety == StoreSafe);
2232
2233 // Set up the preheader to have a definition of the value. It is the live-out
2234 // value from the preheader that uses in the loop will use.
2235 LoadInst *PreheaderLoad = nullptr;
2236 if (FoundLoadToPromote || !StoreIsGuanteedToExecute) {
2237 PreheaderLoad =
2238 new LoadInst(AccessTy, SomePtr, SomePtr->getName() + ".promoted",
2239 Preheader->getTerminator()->getIterator());
2240 if (SawUnorderedAtomic)
2241 PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
2242 PreheaderLoad->setAlignment(Alignment);
2243 PreheaderLoad->setDebugLoc(DebugLoc());
2244 if (AATags)
2245 PreheaderLoad->setAAMetadata(AATags);
2246
2247 MemoryAccess *PreheaderLoadMemoryAccess = MSSAU.createMemoryAccessInBB(
2248 PreheaderLoad, nullptr, PreheaderLoad->getParent(), MemorySSA::End);
2249 MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
2250 MSSAU.insertUse(NewMemUse, /*RenameUses=*/true);
2251 SSA.AddAvailableValue(Preheader, PreheaderLoad);
2252 } else {
2253 SSA.AddAvailableValue(Preheader, PoisonValue::get(AccessTy));
2254 }
2255
2256 if (VerifyMemorySSA)
2257 MSSAU.getMemorySSA()->verifyMemorySSA();
2258 // Rewrite all the loads in the loop and remember all the definitions from
2259 // stores in the loop.
2260 Promoter.run(LoopUses);
2261
2262 if (VerifyMemorySSA)
2263 MSSAU.getMemorySSA()->verifyMemorySSA();
2264 // If the SSAUpdater didn't use the load in the preheader, just zap it now.
2265 if (PreheaderLoad && PreheaderLoad->use_empty())
2266 eraseInstruction(*PreheaderLoad, *SafetyInfo, MSSAU);
2267
2268 return true;
2269}
2270
2271static void foreachMemoryAccess(MemorySSA *MSSA, Loop *L,
2272 function_ref<void(Instruction *)> Fn) {
2273 for (const BasicBlock *BB : L->blocks())
2274 if (const auto *Accesses = MSSA->getBlockAccesses(BB))
2275 for (const auto &Access : *Accesses)
2276 if (const auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
2277 Fn(MUD->getMemoryInst());
2278}
2279
2280// The bool indicates whether there might be reads outside the set, in which
2281// case only loads may be promoted.
2284 BatchAAResults BatchAA(*AA);
2285 AliasSetTracker AST(BatchAA);
2286
2287 auto IsPotentiallyPromotable = [L](const Instruction *I) {
2288 if (const auto *SI = dyn_cast<StoreInst>(I))
2289 return L->isLoopInvariant(SI->getPointerOperand());
2290 if (const auto *LI = dyn_cast<LoadInst>(I))
2291 return L->isLoopInvariant(LI->getPointerOperand());
2292 return false;
2293 };
2294
2295 // Populate AST with potentially promotable accesses.
2296 SmallPtrSet<Value *, 16> AttemptingPromotion;
2297 foreachMemoryAccess(MSSA, L, [&](Instruction *I) {
2298 if (IsPotentiallyPromotable(I)) {
2299 AttemptingPromotion.insert(I);
2300 AST.add(I);
2301 }
2302 });
2303
2304 // We're only interested in must-alias sets that contain a mod.
2306 for (AliasSet &AS : AST)
2307 if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
2308 Sets.push_back({&AS, false});
2309
2310 if (Sets.empty())
2311 return {}; // Nothing to promote...
2312
2313 // Discard any sets for which there is an aliasing non-promotable access.
2314 foreachMemoryAccess(MSSA, L, [&](Instruction *I) {
2315 if (AttemptingPromotion.contains(I))
2316 return;
2317
2319 ModRefInfo MR = Pair.getPointer()->aliasesUnknownInst(I, BatchAA);
2320 // Cannot promote if there are writes outside the set.
2321 if (isModSet(MR))
2322 return true;
2323 if (isRefSet(MR)) {
2324 // Remember reads outside the set.
2325 Pair.setInt(true);
2326 // If this is a mod-only set and there are reads outside the set,
2327 // we will not be able to promote, so bail out early.
2328 return !Pair.getPointer()->isRef();
2329 }
2330 return false;
2331 });
2332 });
2333
2335 for (auto [Set, HasReadsOutsideSet] : Sets) {
2336 SmallSetVector<Value *, 8> PointerMustAliases;
2337 for (const auto &MemLoc : *Set)
2338 PointerMustAliases.insert(const_cast<Value *>(MemLoc.Ptr));
2339 Result.emplace_back(std::move(PointerMustAliases), HasReadsOutsideSet);
2340 }
2341
2342 return Result;
2343}
2344
2346 Loop *CurLoop, Instruction &I,
2347 SinkAndHoistLICMFlags &Flags,
2348 bool InvariantGroup) {
2349 // For hoisting, use the walker to determine safety
2350 if (!Flags.getIsSink()) {
2351 // If hoisting an invariant group, we only need to check that there
2352 // is no store to the loaded pointer between the start of the loop,
2353 // and the load (since all values must be the same).
2354
2355 // This can be checked in two conditions:
2356 // 1) if the memoryaccess is outside the loop
2357 // 2) the earliest access is at the loop header,
2358 // if the memory loaded is the phi node
2359
2360 BatchAAResults BAA(MSSA->getAA());
2361 MemoryAccess *Source = getClobberingMemoryAccess(*MSSA, BAA, Flags, MU);
2362 return !MSSA->isLiveOnEntryDef(Source) &&
2363 CurLoop->contains(Source->getBlock()) &&
2364 !(InvariantGroup && Source->getBlock() == CurLoop->getHeader() && isa<MemoryPhi>(Source));
2365 }
2366
2367 // For sinking, we'd need to check all Defs below this use. The getClobbering
2368 // call will look on the backedge of the loop, but will check aliasing with
2369 // the instructions on the previous iteration.
2370 // For example:
2371 // for (i ... )
2372 // load a[i] ( Use (LoE)
2373 // store a[i] ( 1 = Def (2), with 2 = Phi for the loop.
2374 // i++;
2375 // The load sees no clobbering inside the loop, as the backedge alias check
2376 // does phi translation, and will check aliasing against store a[i-1].
2377 // However sinking the load outside the loop, below the store is incorrect.
2378
2379 // For now, only sink if there are no Defs in the loop, and the existing ones
2380 // precede the use and are in the same block.
2381 // FIXME: Increase precision: Safe to sink if Use post dominates the Def;
2382 // needs PostDominatorTreeAnalysis.
2383 // FIXME: More precise: no Defs that alias this Use.
2384 if (Flags.tooManyMemoryAccesses())
2385 return true;
2386 for (auto *BB : CurLoop->getBlocks())
2387 if (pointerInvalidatedByBlock(*BB, *MSSA, *MU))
2388 return true;
2389 // When sinking, the source block may not be part of the loop so check it.
2390 if (!CurLoop->contains(&I))
2391 return pointerInvalidatedByBlock(*I.getParent(), *MSSA, *MU);
2392
2393 return false;
2394}
2395
2397 if (const auto *Accesses = MSSA.getBlockDefs(&BB))
2398 for (const auto &MA : *Accesses)
2399 if (const auto *MD = dyn_cast<MemoryDef>(&MA))
2400 if (MU.getBlock() != MD->getBlock() || !MSSA.locallyDominates(MD, &MU))
2401 return true;
2402 return false;
2403}
2404
2405/// Try to simplify things like (A < INV_1 AND icmp A < INV_2) into (A <
2406/// min(INV_1, INV_2)), if INV_1 and INV_2 are both loop invariants and their
2407/// minimun can be computed outside of loop, and X is not a loop-invariant.
2408static bool hoistMinMax(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
2409 MemorySSAUpdater &MSSAU) {
2410 bool Inverse = false;
2411 using namespace PatternMatch;
2412 Value *Cond1, *Cond2;
2413 if (match(&I, m_LogicalOr(m_Value(Cond1), m_Value(Cond2)))) {
2414 Inverse = true;
2415 } else if (match(&I, m_LogicalAnd(m_Value(Cond1), m_Value(Cond2)))) {
2416 // Do nothing
2417 } else
2418 return false;
2419
2420 auto MatchICmpAgainstInvariant = [&](Value *C, ICmpInst::Predicate &P,
2421 Value *&LHS, Value *&RHS) {
2422 if (!match(C, m_OneUse(m_ICmp(P, m_Value(LHS), m_Value(RHS)))))
2423 return false;
2424 if (!LHS->getType()->isIntegerTy())
2425 return false;
2427 return false;
2428 if (L.isLoopInvariant(LHS)) {
2429 std::swap(LHS, RHS);
2431 }
2432 if (L.isLoopInvariant(LHS) || !L.isLoopInvariant(RHS))
2433 return false;
2434 if (Inverse)
2436 return true;
2437 };
2438 ICmpInst::Predicate P1, P2;
2439 Value *LHS1, *LHS2, *RHS1, *RHS2;
2440 if (!MatchICmpAgainstInvariant(Cond1, P1, LHS1, RHS1) ||
2441 !MatchICmpAgainstInvariant(Cond2, P2, LHS2, RHS2))
2442 return false;
2443 if (P1 != P2 || LHS1 != LHS2)
2444 return false;
2445
2446 // Everything is fine, we can do the transform.
2447 bool UseMin = ICmpInst::isLT(P1) || ICmpInst::isLE(P1);
2448 assert(
2449 (UseMin || ICmpInst::isGT(P1) || ICmpInst::isGE(P1)) &&
2450 "Relational predicate is either less (or equal) or greater (or equal)!");
2452 ? (UseMin ? Intrinsic::smin : Intrinsic::smax)
2453 : (UseMin ? Intrinsic::umin : Intrinsic::umax);
2454 auto *Preheader = L.getLoopPreheader();
2455 assert(Preheader && "Loop is not in simplify form?");
2456 IRBuilder<> Builder(Preheader->getTerminator());
2457 // We are about to create a new guaranteed use for RHS2 which might not exist
2458 // before (if it was a non-taken input of logical and/or instruction). If it
2459 // was poison, we need to freeze it. Note that no new use for LHS and RHS1 are
2460 // introduced, so they don't need this.
2461 if (isa<SelectInst>(I))
2462 RHS2 = Builder.CreateFreeze(RHS2, RHS2->getName() + ".fr");
2463 Value *NewRHS = Builder.CreateBinaryIntrinsic(
2464 id, RHS1, RHS2, nullptr, StringRef("invariant.") +
2465 (ICmpInst::isSigned(P1) ? "s" : "u") +
2466 (UseMin ? "min" : "max"));
2467 Builder.SetInsertPoint(&I);
2469 if (Inverse)
2471 Value *NewCond = Builder.CreateICmp(P, LHS1, NewRHS);
2472 NewCond->takeName(&I);
2473 I.replaceAllUsesWith(NewCond);
2474 eraseInstruction(I, SafetyInfo, MSSAU);
2475 eraseInstruction(*cast<Instruction>(Cond1), SafetyInfo, MSSAU);
2476 eraseInstruction(*cast<Instruction>(Cond2), SafetyInfo, MSSAU);
2477 return true;
2478}
2479
2480/// Reassociate gep (gep ptr, idx1), idx2 to gep (gep ptr, idx2), idx1 if
2481/// this allows hoisting the inner GEP.
2482static bool hoistGEP(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
2484 DominatorTree *DT) {
2485 auto *GEP = dyn_cast<GetElementPtrInst>(&I);
2486 if (!GEP)
2487 return false;
2488
2489 auto *Src = dyn_cast<GetElementPtrInst>(GEP->getPointerOperand());
2490 if (!Src || !Src->hasOneUse() || !L.contains(Src))
2491 return false;
2492
2493 Value *SrcPtr = Src->getPointerOperand();
2494 auto LoopInvariant = [&](Value *V) { return L.isLoopInvariant(V); };
2495 if (!L.isLoopInvariant(SrcPtr) || !all_of(GEP->indices(), LoopInvariant))
2496 return false;
2497
2498 // This can only happen if !AllowSpeculation, otherwise this would already be
2499 // handled.
2500 // FIXME: Should we respect AllowSpeculation in these reassociation folds?
2501 // The flag exists to prevent metadata dropping, which is not relevant here.
2502 if (all_of(Src->indices(), LoopInvariant))
2503 return false;
2504
2505 // The swapped GEPs are inbounds if both original GEPs are inbounds
2506 // and the sign of the offsets is the same. For simplicity, only
2507 // handle both offsets being non-negative.
2508 const DataLayout &DL = GEP->getModule()->getDataLayout();
2509 auto NonNegative = [&](Value *V) {
2510 return isKnownNonNegative(V, SimplifyQuery(DL, DT, AC, GEP));
2511 };
2512 bool IsInBounds = Src->isInBounds() && GEP->isInBounds() &&
2513 all_of(Src->indices(), NonNegative) &&
2514 all_of(GEP->indices(), NonNegative);
2515
2516 BasicBlock *Preheader = L.getLoopPreheader();
2517 IRBuilder<> Builder(Preheader->getTerminator());
2518 Value *NewSrc = Builder.CreateGEP(GEP->getSourceElementType(), SrcPtr,
2519 SmallVector<Value *>(GEP->indices()),
2520 "invariant.gep", IsInBounds);
2521 Builder.SetInsertPoint(GEP);
2522 Value *NewGEP = Builder.CreateGEP(Src->getSourceElementType(), NewSrc,
2523 SmallVector<Value *>(Src->indices()), "gep",
2524 IsInBounds);
2525 GEP->replaceAllUsesWith(NewGEP);
2526 eraseInstruction(*GEP, SafetyInfo, MSSAU);
2527 eraseInstruction(*Src, SafetyInfo, MSSAU);
2528 return true;
2529}
2530
2531/// Try to turn things like "LV + C1 < C2" into "LV < C2 - C1". Here
2532/// C1 and C2 are loop invariants and LV is a loop-variant.
2533static bool hoistAdd(ICmpInst::Predicate Pred, Value *VariantLHS,
2534 Value *InvariantRHS, ICmpInst &ICmp, Loop &L,
2535 ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU,
2536 AssumptionCache *AC, DominatorTree *DT) {
2537 assert(ICmpInst::isSigned(Pred) && "Not supported yet!");
2538 assert(!L.isLoopInvariant(VariantLHS) && "Precondition.");
2539 assert(L.isLoopInvariant(InvariantRHS) && "Precondition.");
2540
2541 // Try to represent VariantLHS as sum of invariant and variant operands.
2542 using namespace PatternMatch;
2543 Value *VariantOp, *InvariantOp;
2544 if (!match(VariantLHS, m_NSWAdd(m_Value(VariantOp), m_Value(InvariantOp))))
2545 return false;
2546
2547 // LHS itself is a loop-variant, try to represent it in the form:
2548 // "VariantOp + InvariantOp". If it is possible, then we can reassociate.
2549 if (L.isLoopInvariant(VariantOp))
2550 std::swap(VariantOp, InvariantOp);
2551 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2552 return false;
2553
2554 // In order to turn "LV + C1 < C2" into "LV < C2 - C1", we need to be able to
2555 // freely move values from left side of inequality to right side (just as in
2556 // normal linear arithmetics). Overflows make things much more complicated, so
2557 // we want to avoid this.
2558 auto &DL = L.getHeader()->getModule()->getDataLayout();
2559 bool ProvedNoOverflowAfterReassociate =
2560 computeOverflowForSignedSub(InvariantRHS, InvariantOp,
2561 SimplifyQuery(DL, DT, AC, &ICmp)) ==
2563 if (!ProvedNoOverflowAfterReassociate)
2564 return false;
2565 auto *Preheader = L.getLoopPreheader();
2566 assert(Preheader && "Loop is not in simplify form?");
2567 IRBuilder<> Builder(Preheader->getTerminator());
2568 Value *NewCmpOp = Builder.CreateSub(InvariantRHS, InvariantOp, "invariant.op",
2569 /*HasNUW*/ false, /*HasNSW*/ true);
2570 ICmp.setPredicate(Pred);
2571 ICmp.setOperand(0, VariantOp);
2572 ICmp.setOperand(1, NewCmpOp);
2573 eraseInstruction(cast<Instruction>(*VariantLHS), SafetyInfo, MSSAU);
2574 return true;
2575}
2576
2577/// Try to reassociate and hoist the following two patterns:
2578/// LV - C1 < C2 --> LV < C1 + C2,
2579/// C1 - LV < C2 --> LV > C1 - C2.
2580static bool hoistSub(ICmpInst::Predicate Pred, Value *VariantLHS,
2581 Value *InvariantRHS, ICmpInst &ICmp, Loop &L,
2582 ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU,
2583 AssumptionCache *AC, DominatorTree *DT) {
2584 assert(ICmpInst::isSigned(Pred) && "Not supported yet!");
2585 assert(!L.isLoopInvariant(VariantLHS) && "Precondition.");
2586 assert(L.isLoopInvariant(InvariantRHS) && "Precondition.");
2587
2588 // Try to represent VariantLHS as sum of invariant and variant operands.
2589 using namespace PatternMatch;
2590 Value *VariantOp, *InvariantOp;
2591 if (!match(VariantLHS, m_NSWSub(m_Value(VariantOp), m_Value(InvariantOp))))
2592 return false;
2593
2594 bool VariantSubtracted = false;
2595 // LHS itself is a loop-variant, try to represent it in the form:
2596 // "VariantOp + InvariantOp". If it is possible, then we can reassociate. If
2597 // the variant operand goes with minus, we use a slightly different scheme.
2598 if (L.isLoopInvariant(VariantOp)) {
2599 std::swap(VariantOp, InvariantOp);
2600 VariantSubtracted = true;
2601 Pred = ICmpInst::getSwappedPredicate(Pred);
2602 }
2603 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2604 return false;
2605
2606 // In order to turn "LV - C1 < C2" into "LV < C2 + C1", we need to be able to
2607 // freely move values from left side of inequality to right side (just as in
2608 // normal linear arithmetics). Overflows make things much more complicated, so
2609 // we want to avoid this. Likewise, for "C1 - LV < C2" we need to prove that
2610 // "C1 - C2" does not overflow.
2611 auto &DL = L.getHeader()->getModule()->getDataLayout();
2612 SimplifyQuery SQ(DL, DT, AC, &ICmp);
2613 if (VariantSubtracted) {
2614 // C1 - LV < C2 --> LV > C1 - C2
2615 if (computeOverflowForSignedSub(InvariantOp, InvariantRHS, SQ) !=
2617 return false;
2618 } else {
2619 // LV - C1 < C2 --> LV < C1 + C2
2620 if (computeOverflowForSignedAdd(InvariantOp, InvariantRHS, SQ) !=
2622 return false;
2623 }
2624 auto *Preheader = L.getLoopPreheader();
2625 assert(Preheader && "Loop is not in simplify form?");
2626 IRBuilder<> Builder(Preheader->getTerminator());
2627 Value *NewCmpOp =
2628 VariantSubtracted
2629 ? Builder.CreateSub(InvariantOp, InvariantRHS, "invariant.op",
2630 /*HasNUW*/ false, /*HasNSW*/ true)
2631 : Builder.CreateAdd(InvariantOp, InvariantRHS, "invariant.op",
2632 /*HasNUW*/ false, /*HasNSW*/ true);
2633 ICmp.setPredicate(Pred);
2634 ICmp.setOperand(0, VariantOp);
2635 ICmp.setOperand(1, NewCmpOp);
2636 eraseInstruction(cast<Instruction>(*VariantLHS), SafetyInfo, MSSAU);
2637 return true;
2638}
2639
2640/// Reassociate and hoist add/sub expressions.
2641static bool hoistAddSub(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo,
2643 DominatorTree *DT) {
2644 using namespace PatternMatch;
2646 Value *LHS, *RHS;
2647 if (!match(&I, m_ICmp(Pred, m_Value(LHS), m_Value(RHS))))
2648 return false;
2649
2650 // TODO: Support unsigned predicates?
2651 if (!ICmpInst::isSigned(Pred))
2652 return false;
2653
2654 // Put variant operand to LHS position.
2655 if (L.isLoopInvariant(LHS)) {
2656 std::swap(LHS, RHS);
2657 Pred = ICmpInst::getSwappedPredicate(Pred);
2658 }
2659 // We want to delete the initial operation after reassociation, so only do it
2660 // if it has no other uses.
2661 if (L.isLoopInvariant(LHS) || !L.isLoopInvariant(RHS) || !LHS->hasOneUse())
2662 return false;
2663
2664 // TODO: We could go with smarter context, taking common dominator of all I's
2665 // users instead of I itself.
2666 if (hoistAdd(Pred, LHS, RHS, cast<ICmpInst>(I), L, SafetyInfo, MSSAU, AC, DT))
2667 return true;
2668
2669 if (hoistSub(Pred, LHS, RHS, cast<ICmpInst>(I), L, SafetyInfo, MSSAU, AC, DT))
2670 return true;
2671
2672 return false;
2673}
2674
2675static bool isReassociableOp(Instruction *I, unsigned IntOpcode,
2676 unsigned FPOpcode) {
2677 if (I->getOpcode() == IntOpcode)
2678 return true;
2679 if (I->getOpcode() == FPOpcode && I->hasAllowReassoc() &&
2680 I->hasNoSignedZeros())
2681 return true;
2682 return false;
2683}
2684
2685/// Try to reassociate expressions like ((A1 * B1) + (A2 * B2) + ...) * C where
2686/// A1, A2, ... and C are loop invariants into expressions like
2687/// ((A1 * C * B1) + (A2 * C * B2) + ...) and hoist the (A1 * C), (A2 * C), ...
2688/// invariant expressions. This functions returns true only if any hoisting has
2689/// actually occured.
2691 ICFLoopSafetyInfo &SafetyInfo,
2693 DominatorTree *DT) {
2694 if (!isReassociableOp(&I, Instruction::Mul, Instruction::FMul))
2695 return false;
2696 Value *VariantOp = I.getOperand(0);
2697 Value *InvariantOp = I.getOperand(1);
2698 if (L.isLoopInvariant(VariantOp))
2699 std::swap(VariantOp, InvariantOp);
2700 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2701 return false;
2702 Value *Factor = InvariantOp;
2703
2704 // First, we need to make sure we should do the transformation.
2705 SmallVector<Use *> Changes;
2708 if (BinaryOperator *VariantBinOp = dyn_cast<BinaryOperator>(VariantOp))
2709 Worklist.push_back(VariantBinOp);
2710 while (!Worklist.empty()) {
2711 BinaryOperator *BO = Worklist.pop_back_val();
2712 if (!BO->hasOneUse())
2713 return false;
2714 if (isReassociableOp(BO, Instruction::Add, Instruction::FAdd) &&
2715 isa<BinaryOperator>(BO->getOperand(0)) &&
2716 isa<BinaryOperator>(BO->getOperand(1))) {
2717 Worklist.push_back(cast<BinaryOperator>(BO->getOperand(0)));
2718 Worklist.push_back(cast<BinaryOperator>(BO->getOperand(1)));
2719 Adds.push_back(BO);
2720 continue;
2721 }
2722 if (!isReassociableOp(BO, Instruction::Mul, Instruction::FMul) ||
2723 L.isLoopInvariant(BO))
2724 return false;
2725 Use &U0 = BO->getOperandUse(0);
2726 Use &U1 = BO->getOperandUse(1);
2727 if (L.isLoopInvariant(U0))
2728 Changes.push_back(&U0);
2729 else if (L.isLoopInvariant(U1))
2730 Changes.push_back(&U1);
2731 else
2732 return false;
2733 unsigned Limit = I.getType()->isIntOrIntVectorTy()
2736 if (Changes.size() > Limit)
2737 return false;
2738 }
2739 if (Changes.empty())
2740 return false;
2741
2742 // Drop the poison flags for any adds we looked through.
2743 if (I.getType()->isIntOrIntVectorTy()) {
2744 for (auto *Add : Adds)
2745 Add->dropPoisonGeneratingFlags();
2746 }
2747
2748 // We know we should do it so let's do the transformation.
2749 auto *Preheader = L.getLoopPreheader();
2750 assert(Preheader && "Loop is not in simplify form?");
2751 IRBuilder<> Builder(Preheader->getTerminator());
2752 for (auto *U : Changes) {
2753 assert(L.isLoopInvariant(U->get()));
2754 Instruction *Ins = cast<Instruction>(U->getUser());
2755 Value *Mul;
2756 if (I.getType()->isIntOrIntVectorTy()) {
2757 Mul = Builder.CreateMul(U->get(), Factor, "factor.op.mul");
2758 // Drop the poison flags on the original multiply.
2759 Ins->dropPoisonGeneratingFlags();
2760 } else
2761 Mul = Builder.CreateFMulFMF(U->get(), Factor, Ins, "factor.op.fmul");
2762 U->set(Mul);
2763 }
2764 I.replaceAllUsesWith(VariantOp);
2765 eraseInstruction(I, SafetyInfo, MSSAU);
2766 return true;
2767}
2768
2770 ICFLoopSafetyInfo &SafetyInfo,
2772 DominatorTree *DT) {
2773 // Optimize complex patterns, such as (x < INV1 && x < INV2), turning them
2774 // into (x < min(INV1, INV2)), and hoisting the invariant part of this
2775 // expression out of the loop.
2776 if (hoistMinMax(I, L, SafetyInfo, MSSAU)) {
2777 ++NumHoisted;
2778 ++NumMinMaxHoisted;
2779 return true;
2780 }
2781
2782 // Try to hoist GEPs by reassociation.
2783 if (hoistGEP(I, L, SafetyInfo, MSSAU, AC, DT)) {
2784 ++NumHoisted;
2785 ++NumGEPsHoisted;
2786 return true;
2787 }
2788
2789 // Try to hoist add/sub's by reassociation.
2790 if (hoistAddSub(I, L, SafetyInfo, MSSAU, AC, DT)) {
2791 ++NumHoisted;
2792 ++NumAddSubHoisted;
2793 return true;
2794 }
2795
2796 bool IsInt = I.getType()->isIntOrIntVectorTy();
2797 if (hoistMulAddAssociation(I, L, SafetyInfo, MSSAU, AC, DT)) {
2798 ++NumHoisted;
2799 if (IsInt)
2800 ++NumIntAssociationsHoisted;
2801 else
2802 ++NumFPAssociationsHoisted;
2803 return true;
2804 }
2805
2806 return false;
2807}
2808
2809/// Little predicate that returns true if the specified basic block is in
2810/// a subloop of the current one, not the current one itself.
2811///
2812static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
2813 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
2814 return LI->getLoopFor(BB) != CurLoop;
2815}
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:2675
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:1384
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:2482
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:1556
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:1354
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:2408
static void moveInstructionBefore(Instruction &I, BasicBlock::iterator Dest, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution *SE)
Definition: LICM.cpp:1506
static Instruction * cloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU)
Definition: LICM.cpp:1426
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:2345
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:2533
static MemoryAccess * getClobberingMemoryAccess(MemorySSA &MSSA, BatchAAResults &BAA, SinkAndHoistLICMFlags &Flags, MemoryUseOrDef *MA)
Definition: LICM.cpp:1146
static SmallVector< PointersAndHasReadsOutsideSet, 0 > collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L)
Definition: LICM.cpp:2283
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:1735
static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo)
Definition: LICM.cpp:1539
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:1628
static bool hoistAddSub(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache *AC, DominatorTree *DT)
Reassociate and hoist add/sub expressions.
Definition: LICM.cpp:2641
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:2690
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:2271
static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT, Loop *CurLoop)
Definition: LICM.cpp:1052
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:1521
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:2812
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:2580
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
Definition: LICM.cpp:1499
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:1781
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:2769
static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I)
Returns true if a PHINode is a trivially replaceable with an Instruction.
Definition: LICM.cpp:1345
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:2396
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:72
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:321
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:657
iterator end()
Definition: BasicBlock.h:443
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:430
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:409
InstListType::const_iterator getFirstNonPHIIt() const
Iterator returning form of getFirstNonPHI.
Definition: BasicBlock.cpp:367
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:360
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:199
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:482
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:165
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:168
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
Definition: BasicBlock.h:358
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:221
bool canSplitPredecessors() const
Definition: BasicBlock.cpp:538
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:289
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:1687
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:1108
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:993
bool isSigned() const
Definition: InstrTypes.h:1265
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:1167
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:1129
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
bool isNegative() const
Definition: Constants.h:201
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:161
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:1601
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2536
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1344
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1327
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:1866
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2352
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1361
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2667
void mergeDIAssignID(ArrayRef< const Instruction * > SourceInstructions)
Merge the DIAssignID metadata from this instruction and those attached to instructions in SourceInstr...
Definition: DebugInfo.cpp:936
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:83
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1720
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:812
const BasicBlock * getParent() const
Definition: Instruction.h:152
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:149
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:359
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1635
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
Definition: Metadata.cpp:1706
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:451
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:151
An instruction for reading from memory.
Definition: Instructions.h:185
void setAlignment(Align Align)
Definition: Instructions.h:241
Value * getPointerOperand()
Definition: Instructions.h:281
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this load instruction.
Definition: Instructions.h:251
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:165
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:928
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:1045
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:985
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:701
AliasAnalysis & getAA()
Definition: MemorySSA.h:799
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
Definition: MemorySSA.h:759
MemorySSAWalker * getSkipSelfWalker()
Definition: MemorySSA.cpp:1603
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:2173
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:1905
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:719
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
Definition: MemorySSA.h:767
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:2142
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:739
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:253
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:263
Represents read-only accesses to memory.
Definition: MemorySSA.h:313
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:293
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:1830
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:318
void setAlignment(Align Align)
Definition: Instructions.h:374
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this store instruction.
Definition: Instructions.h:385
static unsigned getPointerOperandIndex()
Definition: Instructions.h:420
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:199
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.
pred_iterator pred_end(BasicBlock *BB)
Definition: CFG.h:114
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
@ 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:1722
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:1160
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:1664
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:201
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...
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
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:656
Pass * createLICMPass()
Definition: LICM.cpp:379
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:1729
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:400
pred_iterator pred_begin(BasicBlock *BB)
Definition: CFG.h:110
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:419
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
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:159
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
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
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:84
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
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.
@ Add
Sum of integers.
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1669
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:221
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:1849
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:1749
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:2051
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:1963
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:1389
uint32_t getTagID() const
Return the tag of this operand bundle as an integer.
Definition: InstrTypes.h:1417
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:74