LLVM  16.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 
41 #include "llvm/ADT/SetOperations.h"
42 #include "llvm/ADT/Statistic.h"
50 #include "llvm/Analysis/Loads.h"
51 #include "llvm/Analysis/LoopInfo.h"
54 #include "llvm/Analysis/LoopPass.h"
63 #include "llvm/IR/CFG.h"
64 #include "llvm/IR/Constants.h"
65 #include "llvm/IR/DataLayout.h"
67 #include "llvm/IR/DerivedTypes.h"
68 #include "llvm/IR/Dominators.h"
69 #include "llvm/IR/Instructions.h"
70 #include "llvm/IR/IntrinsicInst.h"
71 #include "llvm/IR/LLVMContext.h"
72 #include "llvm/IR/Metadata.h"
73 #include "llvm/IR/PatternMatch.h"
75 #include "llvm/InitializePasses.h"
77 #include "llvm/Support/Debug.h"
80 #include "llvm/Transforms/Scalar.h"
86 #include <algorithm>
87 #include <utility>
88 using namespace llvm;
89 
90 namespace llvm {
91 class LPMUpdater;
92 } // namespace llvm
93 
94 #define DEBUG_TYPE "licm"
95 
96 STATISTIC(NumCreatedBlocks, "Number of blocks created");
97 STATISTIC(NumClonedBranches, "Number of branches cloned");
98 STATISTIC(NumSunk, "Number of instructions sunk out of loop");
99 STATISTIC(NumHoisted, "Number of instructions hoisted out of loop");
100 STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
101 STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
102 STATISTIC(NumPromotionCandidates, "Number of promotion candidates");
103 STATISTIC(NumLoadPromoted, "Number of load-only promotions");
104 STATISTIC(NumLoadStorePromoted, "Number of load and store promotions");
105 
106 /// Memory promotion is enabled by default.
107 static cl::opt<bool>
108  DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
109  cl::desc("Disable memory promotion in LICM pass"));
110 
112  "licm-control-flow-hoisting", cl::Hidden, cl::init(false),
113  cl::desc("Enable control flow (and PHI) hoisting in LICM"));
114 
115 static cl::opt<bool>
116  SingleThread("licm-force-thread-model-single", cl::Hidden, cl::init(false),
117  cl::desc("Force thread model single in LICM pass"));
118 
120  "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
121  cl::desc("Max num uses visited for identifying load "
122  "invariance in loop using invariant start (default = 8)"));
123 
124 // Experimental option to allow imprecision in LICM in pathological cases, in
125 // exchange for faster compile. This is to be removed if MemorySSA starts to
126 // address the same issue. LICM calls MemorySSAWalker's
127 // getClobberingMemoryAccess, up to the value of the Cap, getting perfect
128 // accuracy. Afterwards, LICM will call into MemorySSA's getDefiningAccess,
129 // which may not be precise, since optimizeUses is capped. The result is
130 // correct, but we may not get as "far up" as possible to get which access is
131 // clobbering the one queried.
133  "licm-mssa-optimization-cap", cl::init(100), cl::Hidden,
134  cl::desc("Enable imprecision in LICM in pathological cases, in exchange "
135  "for faster compile. Caps the MemorySSA clobbering calls."));
136 
137 // Experimentally, memory promotion carries less importance than sinking and
138 // hoisting. Limit when we do promotion when using MemorySSA, in order to save
139 // compile time.
141  "licm-mssa-max-acc-promotion", cl::init(250), cl::Hidden,
142  cl::desc("[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
143  "effect. When MSSA in LICM is enabled, then this is the maximum "
144  "number of accesses allowed to be present in a loop in order to "
145  "enable memory promotion."));
146 
147 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
148 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
149  const LoopSafetyInfo *SafetyInfo,
150  TargetTransformInfo *TTI, bool &FreeInLoop,
151  bool LoopNestMode);
152 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
153  BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
154  MemorySSAUpdater &MSSAU, ScalarEvolution *SE,
156 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
157  const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
160  Instruction &Inst, const DominatorTree *DT, const TargetLibraryInfo *TLI,
161  const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo,
162  OptimizationRemarkEmitter *ORE, const Instruction *CtxI,
163  AssumptionCache *AC, bool AllowSpeculation);
164 static bool pointerInvalidatedByLoop(MemorySSA *MSSA, MemoryUse *MU,
165  Loop *CurLoop, Instruction &I,
166  SinkAndHoistLICMFlags &Flags);
168  MemoryUse &MU);
170  Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
171  const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU);
172 
173 static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
174  MemorySSAUpdater &MSSAU);
175 
176 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
177  ICFLoopSafetyInfo &SafetyInfo,
178  MemorySSAUpdater &MSSAU, ScalarEvolution *SE);
179 
180 static void foreachMemoryAccess(MemorySSA *MSSA, Loop *L,
181  function_ref<void(Instruction *)> Fn);
184 
185 namespace {
186 struct LoopInvariantCodeMotion {
187  bool runOnLoop(Loop *L, AAResults *AA, LoopInfo *LI, DominatorTree *DT,
190  OptimizationRemarkEmitter *ORE, bool LoopNestMode = false);
191 
192  LoopInvariantCodeMotion(unsigned LicmMssaOptCap,
193  unsigned LicmMssaNoAccForPromotionCap,
194  bool LicmAllowSpeculation)
195  : LicmMssaOptCap(LicmMssaOptCap),
196  LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
197  LicmAllowSpeculation(LicmAllowSpeculation) {}
198 
199 private:
200  unsigned LicmMssaOptCap;
201  unsigned LicmMssaNoAccForPromotionCap;
202  bool LicmAllowSpeculation;
203 };
204 
205 struct LegacyLICMPass : public LoopPass {
206  static char ID; // Pass identification, replacement for typeid
207  LegacyLICMPass(
208  unsigned LicmMssaOptCap = SetLicmMssaOptCap,
209  unsigned LicmMssaNoAccForPromotionCap = SetLicmMssaNoAccForPromotionCap,
210  bool LicmAllowSpeculation = true)
211  : LoopPass(ID), LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
212  LicmAllowSpeculation) {
214  }
215 
216  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
217  if (skipLoop(L))
218  return false;
219 
220  LLVM_DEBUG(dbgs() << "Perform LICM on Loop with header at block "
221  << L->getHeader()->getNameOrAsOperand() << "\n");
222 
223  Function *F = L->getHeader()->getParent();
224 
225  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
226  MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
227  // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
228  // pass. Function analyses need to be preserved across loop transformations
229  // but ORE cannot be preserved (see comment before the pass definition).
231  return LICM.runOnLoop(
232  L, &getAnalysis<AAResultsWrapperPass>().getAAResults(),
233  &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
234  &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
235  &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F),
236  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(*F),
237  &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*F),
238  SE ? &SE->getSE() : nullptr, MSSA, &ORE);
239  }
240 
241  /// This transformation requires natural loop information & requires that
242  /// loop preheaders be inserted into the CFG...
243  ///
244  void getAnalysisUsage(AnalysisUsage &AU) const override {
256  }
257 
258 private:
259  LoopInvariantCodeMotion LICM;
260 };
261 } // namespace
262 
265  if (!AR.MSSA)
266  report_fatal_error("LICM requires MemorySSA (loop-mssa)");
267 
268  // For the new PM, we also can't use OptimizationRemarkEmitter as an analysis
269  // pass. Function analyses need to be preserved across loop transformations
270  // but ORE cannot be preserved (see comment before the pass definition).
272 
273  LoopInvariantCodeMotion LICM(Opts.MssaOptCap, Opts.MssaNoAccForPromotionCap,
274  Opts.AllowSpeculation);
275  if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.AC, &AR.TLI, &AR.TTI,
276  &AR.SE, AR.MSSA, &ORE))
277  return PreservedAnalyses::all();
278 
279  auto PA = getLoopPassPreservedAnalyses();
280 
281  PA.preserve<DominatorTreeAnalysis>();
282  PA.preserve<LoopAnalysis>();
283  PA.preserve<MemorySSAAnalysis>();
284 
285  return PA;
286 }
287 
289  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
290  static_cast<PassInfoMixin<LICMPass> *>(this)->printPipeline(
291  OS, MapClassName2PassName);
292 
293  OS << "<";
294  OS << (Opts.AllowSpeculation ? "" : "no-") << "allowspeculation";
295  OS << ">";
296 }
297 
300  LPMUpdater &) {
301  if (!AR.MSSA)
302  report_fatal_error("LNICM requires MemorySSA (loop-mssa)");
303 
304  // For the new PM, we also can't use OptimizationRemarkEmitter as an analysis
305  // pass. Function analyses need to be preserved across loop transformations
306  // but ORE cannot be preserved (see comment before the pass definition).
308 
309  LoopInvariantCodeMotion LICM(Opts.MssaOptCap, Opts.MssaNoAccForPromotionCap,
310  Opts.AllowSpeculation);
311 
312  Loop &OutermostLoop = LN.getOutermostLoop();
313  bool Changed = LICM.runOnLoop(&OutermostLoop, &AR.AA, &AR.LI, &AR.DT, &AR.AC,
314  &AR.TLI, &AR.TTI, &AR.SE, AR.MSSA, &ORE, true);
315 
316  if (!Changed)
317  return PreservedAnalyses::all();
318 
319  auto PA = getLoopPassPreservedAnalyses();
320 
321  PA.preserve<DominatorTreeAnalysis>();
322  PA.preserve<LoopAnalysis>();
323  PA.preserve<MemorySSAAnalysis>();
324 
325  return PA;
326 }
327 
329  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
330  static_cast<PassInfoMixin<LNICMPass> *>(this)->printPipeline(
331  OS, MapClassName2PassName);
332 
333  OS << "<";
334  OS << (Opts.AllowSpeculation ? "" : "no-") << "allowspeculation";
335  OS << ">";
336 }
337 
338 char LegacyLICMPass::ID = 0;
339 INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
340  false, false)
345 INITIALIZE_PASS_DEPENDENCY(LazyBFIPass)
346 INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
347  false)
348 
349 Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
350 Pass *llvm::createLICMPass(unsigned LicmMssaOptCap,
351  unsigned LicmMssaNoAccForPromotionCap,
352  bool LicmAllowSpeculation) {
353  return new LegacyLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
354  LicmAllowSpeculation);
355 }
356 
358  MemorySSA *MSSA)
360  IsSink, L, MSSA) {}
361 
363  unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink,
364  Loop *L, MemorySSA *MSSA)
365  : LicmMssaOptCap(LicmMssaOptCap),
366  LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
367  IsSink(IsSink) {
368  assert(((L != nullptr) == (MSSA != nullptr)) &&
369  "Unexpected values for SinkAndHoistLICMFlags");
370  if (!MSSA)
371  return;
372 
373  unsigned AccessCapCount = 0;
374  for (auto *BB : L->getBlocks())
375  if (const auto *Accesses = MSSA->getBlockAccesses(BB))
376  for (const auto &MA : *Accesses) {
377  (void)MA;
378  ++AccessCapCount;
379  if (AccessCapCount > LicmMssaNoAccForPromotionCap) {
380  NoOfMemAccTooLarge = true;
381  return;
382  }
383  }
384 }
385 
386 /// Hoist expressions out of the specified loop. Note, alias info for inner
387 /// loop is not preserved so it is not a good idea to run LICM multiple
388 /// times on one loop.
389 bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AAResults *AA, LoopInfo *LI,
391  TargetLibraryInfo *TLI,
393  ScalarEvolution *SE, MemorySSA *MSSA,
395  bool LoopNestMode) {
396  bool Changed = false;
397 
398  assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
399  MSSA->ensureOptimizedUses();
400 
401  // If this loop has metadata indicating that LICM is not to be performed then
402  // just exit.
404  return false;
405  }
406 
407  // Don't sink stores from loops with coroutine suspend instructions.
408  // LICM would sink instructions into the default destination of
409  // the coroutine switch. The default destination of the switch is to
410  // handle the case where the coroutine is suspended, by which point the
411  // coroutine frame may have been destroyed. No instruction can be sunk there.
412  // FIXME: This would unfortunately hurt the performance of coroutines, however
413  // there is currently no general solution for this. Similar issues could also
414  // potentially happen in other passes where instructions are being moved
415  // across that edge.
416  bool HasCoroSuspendInst = llvm::any_of(L->getBlocks(), [](BasicBlock *BB) {
417  return llvm::any_of(*BB, [](Instruction &I) {
418  IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
419  return II && II->getIntrinsicID() == Intrinsic::coro_suspend;
420  });
421  });
422 
423  MemorySSAUpdater MSSAU(MSSA);
424  SinkAndHoistLICMFlags Flags(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
425  /*IsSink=*/true, L, MSSA);
426 
427  // Get the preheader block to move instructions into...
428  BasicBlock *Preheader = L->getLoopPreheader();
429 
430  // Compute loop safety information.
431  ICFLoopSafetyInfo SafetyInfo;
432  SafetyInfo.computeLoopSafetyInfo(L);
433 
434  // We want to visit all of the instructions in this loop... that are not parts
435  // of our subloops (they have already had their invariants hoisted out of
436  // their loop, into this loop, so there is no need to process the BODIES of
437  // the subloops).
438  //
439  // Traverse the body of the loop in depth first order on the dominator tree so
440  // that we are guaranteed to see definitions before we see uses. This allows
441  // us to sink instructions in one pass, without iteration. After sinking
442  // instructions, we perform another pass to hoist them out of the loop.
443  if (L->hasDedicatedExits())
444  Changed |=
445  LoopNestMode
446  ? sinkRegionForLoopNest(DT->getNode(L->getHeader()), AA, LI, DT,
447  TLI, TTI, L, MSSAU, &SafetyInfo, Flags, ORE)
448  : sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L,
449  MSSAU, &SafetyInfo, Flags, ORE);
450  Flags.setIsSink(false);
451  if (Preheader)
452  Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, AC, TLI, L,
453  MSSAU, SE, &SafetyInfo, Flags, ORE, LoopNestMode,
454  LicmAllowSpeculation);
455 
456  // Now that all loop invariants have been removed from the loop, promote any
457  // memory references to scalars that we can.
458  // Don't sink stores from loops without dedicated block exits. Exits
459  // containing indirect branches are not transformed by loop simplify,
460  // make sure we catch that. An additional load may be generated in the
461  // preheader for SSA updater, so also avoid sinking when no preheader
462  // is available.
463  if (!DisablePromotion && Preheader && L->hasDedicatedExits() &&
464  !Flags.tooManyMemoryAccesses() && !HasCoroSuspendInst) {
465  // Figure out the loop exits and their insertion points
466  SmallVector<BasicBlock *, 8> ExitBlocks;
467  L->getUniqueExitBlocks(ExitBlocks);
468 
469  // We can't insert into a catchswitch.
470  bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
471  return isa<CatchSwitchInst>(Exit->getTerminator());
472  });
473 
474  if (!HasCatchSwitch) {
476  SmallVector<MemoryAccess *, 8> MSSAInsertPts;
477  InsertPts.reserve(ExitBlocks.size());
478  MSSAInsertPts.reserve(ExitBlocks.size());
479  for (BasicBlock *ExitBlock : ExitBlocks) {
480  InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
481  MSSAInsertPts.push_back(nullptr);
482  }
483 
485 
486  // Promoting one set of accesses may make the pointers for another set
487  // loop invariant, so run this in a loop.
488  bool Promoted = false;
489  bool LocalPromoted;
490  do {
491  LocalPromoted = false;
492  for (const SmallSetVector<Value *, 8> &PointerMustAliases :
493  collectPromotionCandidates(MSSA, AA, L)) {
494  LocalPromoted |= promoteLoopAccessesToScalars(
495  PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts, PIC, LI,
496  DT, AC, TLI, TTI, L, MSSAU, &SafetyInfo, ORE,
497  LicmAllowSpeculation);
498  }
499  Promoted |= LocalPromoted;
500  } while (LocalPromoted);
501 
502  // Once we have promoted values across the loop body we have to
503  // recursively reform LCSSA as any nested loop may now have values defined
504  // within the loop used in the outer loop.
505  // FIXME: This is really heavy handed. It would be a bit better to use an
506  // SSAUpdater strategy during promotion that was LCSSA aware and reformed
507  // it as it went.
508  if (Promoted)
509  formLCSSARecursively(*L, *DT, LI, SE);
510 
511  Changed |= Promoted;
512  }
513  }
514 
515  // Check that neither this loop nor its parent have had LCSSA broken. LICM is
516  // specifically moving instructions across the loop boundary and so it is
517  // especially in need of basic functional correctness checking here.
518  assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
519  assert((L->isOutermost() || L->getParentLoop()->isLCSSAForm(*DT)) &&
520  "Parent loop not left in LCSSA form after LICM!");
521 
522  if (VerifyMemorySSA)
523  MSSA->verifyMemorySSA();
524 
525  if (Changed && SE)
527  return Changed;
528 }
529 
530 /// Walk the specified region of the CFG (defined by all blocks dominated by
531 /// the specified block, and that are in the current loop) in reverse depth
532 /// first order w.r.t the DominatorTree. This allows us to visit uses before
533 /// definitions, allowing us to sink a loop body in one pass without iteration.
534 ///
537  TargetTransformInfo *TTI, Loop *CurLoop,
538  MemorySSAUpdater &MSSAU, ICFLoopSafetyInfo *SafetyInfo,
539  SinkAndHoistLICMFlags &Flags,
540  OptimizationRemarkEmitter *ORE, Loop *OutermostLoop) {
541 
542  // Verify inputs.
543  assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
544  CurLoop != nullptr && SafetyInfo != nullptr &&
545  "Unexpected input to sinkRegion.");
546 
547  // We want to visit children before parents. We will enqueue all the parents
548  // before their children in the worklist and process the worklist in reverse
549  // order.
551 
552  bool Changed = false;
553  for (DomTreeNode *DTN : reverse(Worklist)) {
554  BasicBlock *BB = DTN->getBlock();
555  // Only need to process the contents of this block if it is not part of a
556  // subloop (which would already have been processed).
557  if (inSubLoop(BB, CurLoop, LI))
558  continue;
559 
560  for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
561  Instruction &I = *--II;
562 
563  // The instruction is not used in the loop if it is dead. In this case,
564  // we just delete it instead of sinking it.
565  if (isInstructionTriviallyDead(&I, TLI)) {
566  LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
569  ++II;
570  eraseInstruction(I, *SafetyInfo, MSSAU);
571  Changed = true;
572  continue;
573  }
574 
575  // Check to see if we can sink this instruction to the exit blocks
576  // of the loop. We can do this if the all users of the instruction are
577  // outside of the loop. In this case, it doesn't even matter if the
578  // operands of the instruction are loop invariant.
579  //
580  bool FreeInLoop = false;
581  bool LoopNestMode = OutermostLoop != nullptr;
582  if (!I.mayHaveSideEffects() &&
583  isNotUsedOrFreeInLoop(I, LoopNestMode ? OutermostLoop : CurLoop,
584  SafetyInfo, TTI, FreeInLoop, LoopNestMode) &&
585  canSinkOrHoistInst(I, AA, DT, CurLoop, MSSAU, true, Flags, ORE)) {
586  if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
587  if (!FreeInLoop) {
588  ++II;
590  eraseInstruction(I, *SafetyInfo, MSSAU);
591  }
592  Changed = true;
593  }
594  }
595  }
596  }
597  if (VerifyMemorySSA)
598  MSSAU.getMemorySSA()->verifyMemorySSA();
599  return Changed;
600 }
601 
604  TargetTransformInfo *TTI, Loop *CurLoop,
605  MemorySSAUpdater &MSSAU,
606  ICFLoopSafetyInfo *SafetyInfo,
607  SinkAndHoistLICMFlags &Flags,
609 
610  bool Changed = false;
612  Worklist.insert(CurLoop);
613  appendLoopsToWorklist(*CurLoop, Worklist);
614  while (!Worklist.empty()) {
615  Loop *L = Worklist.pop_back_val();
616  Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L,
617  MSSAU, SafetyInfo, Flags, ORE, CurLoop);
618  }
619  return Changed;
620 }
621 
622 namespace {
623 // This is a helper class for hoistRegion to make it able to hoist control flow
624 // in order to be able to hoist phis. The way this works is that we initially
625 // start hoisting to the loop preheader, and when we see a loop invariant branch
626 // we make note of this. When we then come to hoist an instruction that's
627 // conditional on such a branch we duplicate the branch and the relevant control
628 // flow, then hoist the instruction into the block corresponding to its original
629 // block in the duplicated control flow.
630 class ControlFlowHoister {
631 private:
632  // Information about the loop we are hoisting from
633  LoopInfo *LI;
634  DominatorTree *DT;
635  Loop *CurLoop;
636  MemorySSAUpdater &MSSAU;
637 
638  // A map of blocks in the loop to the block their instructions will be hoisted
639  // to.
640  DenseMap<BasicBlock *, BasicBlock *> HoistDestinationMap;
641 
642  // The branches that we can hoist, mapped to the block that marks a
643  // convergence point of their control flow.
644  DenseMap<BranchInst *, BasicBlock *> HoistableBranches;
645 
646 public:
647  ControlFlowHoister(LoopInfo *LI, DominatorTree *DT, Loop *CurLoop,
648  MemorySSAUpdater &MSSAU)
649  : LI(LI), DT(DT), CurLoop(CurLoop), MSSAU(MSSAU) {}
650 
651  void registerPossiblyHoistableBranch(BranchInst *BI) {
652  // We can only hoist conditional branches with loop invariant operands.
653  if (!ControlFlowHoisting || !BI->isConditional() ||
654  !CurLoop->hasLoopInvariantOperands(BI))
655  return;
656 
657  // The branch destinations need to be in the loop, and we don't gain
658  // anything by duplicating conditional branches with duplicate successors,
659  // as it's essentially the same as an unconditional branch.
660  BasicBlock *TrueDest = BI->getSuccessor(0);
661  BasicBlock *FalseDest = BI->getSuccessor(1);
662  if (!CurLoop->contains(TrueDest) || !CurLoop->contains(FalseDest) ||
663  TrueDest == FalseDest)
664  return;
665 
666  // We can hoist BI if one branch destination is the successor of the other,
667  // or both have common successor which we check by seeing if the
668  // intersection of their successors is non-empty.
669  // TODO: This could be expanded to allowing branches where both ends
670  // eventually converge to a single block.
671  SmallPtrSet<BasicBlock *, 4> TrueDestSucc, FalseDestSucc;
672  TrueDestSucc.insert(succ_begin(TrueDest), succ_end(TrueDest));
673  FalseDestSucc.insert(succ_begin(FalseDest), succ_end(FalseDest));
674  BasicBlock *CommonSucc = nullptr;
675  if (TrueDestSucc.count(FalseDest)) {
676  CommonSucc = FalseDest;
677  } else if (FalseDestSucc.count(TrueDest)) {
678  CommonSucc = TrueDest;
679  } else {
680  set_intersect(TrueDestSucc, FalseDestSucc);
681  // If there's one common successor use that.
682  if (TrueDestSucc.size() == 1)
683  CommonSucc = *TrueDestSucc.begin();
684  // If there's more than one pick whichever appears first in the block list
685  // (we can't use the value returned by TrueDestSucc.begin() as it's
686  // unpredicatable which element gets returned).
687  else if (!TrueDestSucc.empty()) {
688  Function *F = TrueDest->getParent();
689  auto IsSucc = [&](BasicBlock &BB) { return TrueDestSucc.count(&BB); };
690  auto It = llvm::find_if(*F, IsSucc);
691  assert(It != F->end() && "Could not find successor in function");
692  CommonSucc = &*It;
693  }
694  }
695  // The common successor has to be dominated by the branch, as otherwise
696  // there will be some other path to the successor that will not be
697  // controlled by this branch so any phi we hoist would be controlled by the
698  // wrong condition. This also takes care of avoiding hoisting of loop back
699  // edges.
700  // TODO: In some cases this could be relaxed if the successor is dominated
701  // by another block that's been hoisted and we can guarantee that the
702  // control flow has been replicated exactly.
703  if (CommonSucc && DT->dominates(BI, CommonSucc))
704  HoistableBranches[BI] = CommonSucc;
705  }
706 
707  bool canHoistPHI(PHINode *PN) {
708  // The phi must have loop invariant operands.
709  if (!ControlFlowHoisting || !CurLoop->hasLoopInvariantOperands(PN))
710  return false;
711  // We can hoist phis if the block they are in is the target of hoistable
712  // branches which cover all of the predecessors of the block.
713  SmallPtrSet<BasicBlock *, 8> PredecessorBlocks;
714  BasicBlock *BB = PN->getParent();
715  for (BasicBlock *PredBB : predecessors(BB))
716  PredecessorBlocks.insert(PredBB);
717  // If we have less predecessor blocks than predecessors then the phi will
718  // have more than one incoming value for the same block which we can't
719  // handle.
720  // TODO: This could be handled be erasing some of the duplicate incoming
721  // values.
722  if (PredecessorBlocks.size() != pred_size(BB))
723  return false;
724  for (auto &Pair : HoistableBranches) {
725  if (Pair.second == BB) {
726  // Which blocks are predecessors via this branch depends on if the
727  // branch is triangle-like or diamond-like.
728  if (Pair.first->getSuccessor(0) == BB) {
729  PredecessorBlocks.erase(Pair.first->getParent());
730  PredecessorBlocks.erase(Pair.first->getSuccessor(1));
731  } else if (Pair.first->getSuccessor(1) == BB) {
732  PredecessorBlocks.erase(Pair.first->getParent());
733  PredecessorBlocks.erase(Pair.first->getSuccessor(0));
734  } else {
735  PredecessorBlocks.erase(Pair.first->getSuccessor(0));
736  PredecessorBlocks.erase(Pair.first->getSuccessor(1));
737  }
738  }
739  }
740  // PredecessorBlocks will now be empty if for every predecessor of BB we
741  // found a hoistable branch source.
742  return PredecessorBlocks.empty();
743  }
744 
745  BasicBlock *getOrCreateHoistedBlock(BasicBlock *BB) {
746  if (!ControlFlowHoisting)
747  return CurLoop->getLoopPreheader();
748  // If BB has already been hoisted, return that
749  if (HoistDestinationMap.count(BB))
750  return HoistDestinationMap[BB];
751 
752  // Check if this block is conditional based on a pending branch
753  auto HasBBAsSuccessor =
755  return BB != Pair.second && (Pair.first->getSuccessor(0) == BB ||
756  Pair.first->getSuccessor(1) == BB);
757  };
758  auto It = llvm::find_if(HoistableBranches, HasBBAsSuccessor);
759 
760  // If not involved in a pending branch, hoist to preheader
761  BasicBlock *InitialPreheader = CurLoop->getLoopPreheader();
762  if (It == HoistableBranches.end()) {
763  LLVM_DEBUG(dbgs() << "LICM using "
764  << InitialPreheader->getNameOrAsOperand()
765  << " as hoist destination for "
766  << BB->getNameOrAsOperand() << "\n");
767  HoistDestinationMap[BB] = InitialPreheader;
768  return InitialPreheader;
769  }
770  BranchInst *BI = It->first;
771  assert(std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) ==
772  HoistableBranches.end() &&
773  "BB is expected to be the target of at most one branch");
774 
775  LLVMContext &C = BB->getContext();
776  BasicBlock *TrueDest = BI->getSuccessor(0);
777  BasicBlock *FalseDest = BI->getSuccessor(1);
778  BasicBlock *CommonSucc = HoistableBranches[BI];
779  BasicBlock *HoistTarget = getOrCreateHoistedBlock(BI->getParent());
780 
781  // Create hoisted versions of blocks that currently don't have them
782  auto CreateHoistedBlock = [&](BasicBlock *Orig) {
783  if (HoistDestinationMap.count(Orig))
784  return HoistDestinationMap[Orig];
785  BasicBlock *New =
786  BasicBlock::Create(C, Orig->getName() + ".licm", Orig->getParent());
787  HoistDestinationMap[Orig] = New;
788  DT->addNewBlock(New, HoistTarget);
789  if (CurLoop->getParentLoop())
790  CurLoop->getParentLoop()->addBasicBlockToLoop(New, *LI);
791  ++NumCreatedBlocks;
792  LLVM_DEBUG(dbgs() << "LICM created " << New->getName()
793  << " as hoist destination for " << Orig->getName()
794  << "\n");
795  return New;
796  };
797  BasicBlock *HoistTrueDest = CreateHoistedBlock(TrueDest);
798  BasicBlock *HoistFalseDest = CreateHoistedBlock(FalseDest);
799  BasicBlock *HoistCommonSucc = CreateHoistedBlock(CommonSucc);
800 
801  // Link up these blocks with branches.
802  if (!HoistCommonSucc->getTerminator()) {
803  // The new common successor we've generated will branch to whatever that
804  // hoist target branched to.
805  BasicBlock *TargetSucc = HoistTarget->getSingleSuccessor();
806  assert(TargetSucc && "Expected hoist target to have a single successor");
807  HoistCommonSucc->moveBefore(TargetSucc);
808  BranchInst::Create(TargetSucc, HoistCommonSucc);
809  }
810  if (!HoistTrueDest->getTerminator()) {
811  HoistTrueDest->moveBefore(HoistCommonSucc);
812  BranchInst::Create(HoistCommonSucc, HoistTrueDest);
813  }
814  if (!HoistFalseDest->getTerminator()) {
815  HoistFalseDest->moveBefore(HoistCommonSucc);
816  BranchInst::Create(HoistCommonSucc, HoistFalseDest);
817  }
818 
819  // If BI is being cloned to what was originally the preheader then
820  // HoistCommonSucc will now be the new preheader.
821  if (HoistTarget == InitialPreheader) {
822  // Phis in the loop header now need to use the new preheader.
823  InitialPreheader->replaceSuccessorsPhiUsesWith(HoistCommonSucc);
825  HoistTarget->getSingleSuccessor(), HoistCommonSucc, {HoistTarget});
826  // The new preheader dominates the loop header.
827  DomTreeNode *PreheaderNode = DT->getNode(HoistCommonSucc);
828  DomTreeNode *HeaderNode = DT->getNode(CurLoop->getHeader());
829  DT->changeImmediateDominator(HeaderNode, PreheaderNode);
830  // The preheader hoist destination is now the new preheader, with the
831  // exception of the hoist destination of this branch.
832  for (auto &Pair : HoistDestinationMap)
833  if (Pair.second == InitialPreheader && Pair.first != BI->getParent())
834  Pair.second = HoistCommonSucc;
835  }
836 
837  // Now finally clone BI.
839  HoistTarget->getTerminator(),
840  BranchInst::Create(HoistTrueDest, HoistFalseDest, BI->getCondition()));
841  ++NumClonedBranches;
842 
843  assert(CurLoop->getLoopPreheader() &&
844  "Hoisting blocks should not have destroyed preheader");
845  return HoistDestinationMap[BB];
846  }
847 };
848 } // namespace
849 
850 /// Walk the specified region of the CFG (defined by all blocks dominated by
851 /// the specified block, and that are in the current loop) in depth first
852 /// order w.r.t the DominatorTree. This allows us to visit definitions before
853 /// uses, allowing us to hoist a loop body in one pass without iteration.
854 ///
857  TargetLibraryInfo *TLI, Loop *CurLoop,
858  MemorySSAUpdater &MSSAU, ScalarEvolution *SE,
859  ICFLoopSafetyInfo *SafetyInfo,
860  SinkAndHoistLICMFlags &Flags,
861  OptimizationRemarkEmitter *ORE, bool LoopNestMode,
862  bool AllowSpeculation) {
863  // Verify inputs.
864  assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
865  CurLoop != nullptr && SafetyInfo != nullptr &&
866  "Unexpected input to hoistRegion.");
867 
868  ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
869 
870  // Keep track of instructions that have been hoisted, as they may need to be
871  // re-hoisted if they end up not dominating all of their uses.
872  SmallVector<Instruction *, 16> HoistedInstructions;
873 
874  // For PHI hoisting to work we need to hoist blocks before their successors.
875  // We can do this by iterating through the blocks in the loop in reverse
876  // post-order.
877  LoopBlocksRPO Worklist(CurLoop);
878  Worklist.perform(LI);
879  bool Changed = false;
880  for (BasicBlock *BB : Worklist) {
881  // Only need to process the contents of this block if it is not part of a
882  // subloop (which would already have been processed).
883  if (!LoopNestMode && inSubLoop(BB, CurLoop, LI))
884  continue;
885 
887  // Try constant folding this instruction. If all the operands are
888  // constants, it is technically hoistable, but it would be better to
889  // just fold it.
891  &I, I.getModule()->getDataLayout(), TLI)) {
892  LLVM_DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C
893  << '\n');
894  // FIXME MSSA: Such replacements may make accesses unoptimized (D51960).
895  I.replaceAllUsesWith(C);
896  if (isInstructionTriviallyDead(&I, TLI))
897  eraseInstruction(I, *SafetyInfo, MSSAU);
898  Changed = true;
899  continue;
900  }
901 
902  // Try hoisting the instruction out to the preheader. We can only do
903  // this if all of the operands of the instruction are loop invariant and
904  // if it is safe to hoist the instruction. We also check block frequency
905  // to make sure instruction only gets hoisted into colder blocks.
906  // TODO: It may be safe to hoist if we are hoisting to a conditional block
907  // and we have accurately duplicated the control flow from the loop header
908  // to that block.
909  if (CurLoop->hasLoopInvariantOperands(&I) &&
910  canSinkOrHoistInst(I, AA, DT, CurLoop, MSSAU, true, Flags, ORE) &&
912  I, DT, TLI, CurLoop, SafetyInfo, ORE,
913  CurLoop->getLoopPreheader()->getTerminator(), AC,
914  AllowSpeculation)) {
915  hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
916  MSSAU, SE, ORE);
917  HoistedInstructions.push_back(&I);
918  Changed = true;
919  continue;
920  }
921 
922  // Attempt to remove floating point division out of the loop by
923  // converting it to a reciprocal multiplication.
924  if (I.getOpcode() == Instruction::FDiv && I.hasAllowReciprocal() &&
925  CurLoop->isLoopInvariant(I.getOperand(1))) {
926  auto Divisor = I.getOperand(1);
927  auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
928  auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
929  ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
930  SafetyInfo->insertInstructionTo(ReciprocalDivisor, I.getParent());
931  ReciprocalDivisor->insertBefore(&I);
932 
933  auto Product =
934  BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
935  Product->setFastMathFlags(I.getFastMathFlags());
936  SafetyInfo->insertInstructionTo(Product, I.getParent());
937  Product->insertAfter(&I);
938  I.replaceAllUsesWith(Product);
939  eraseInstruction(I, *SafetyInfo, MSSAU);
940 
941  hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
942  SafetyInfo, MSSAU, SE, ORE);
943  HoistedInstructions.push_back(ReciprocalDivisor);
944  Changed = true;
945  continue;
946  }
947 
948  auto IsInvariantStart = [&](Instruction &I) {
949  using namespace PatternMatch;
950  return I.use_empty() &&
951  match(&I, m_Intrinsic<Intrinsic::invariant_start>());
952  };
953  auto MustExecuteWithoutWritesBefore = [&](Instruction &I) {
954  return SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop) &&
955  SafetyInfo->doesNotWriteMemoryBefore(I, CurLoop);
956  };
957  if ((IsInvariantStart(I) || isGuard(&I)) &&
958  CurLoop->hasLoopInvariantOperands(&I) &&
959  MustExecuteWithoutWritesBefore(I)) {
960  hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
961  MSSAU, SE, ORE);
962  HoistedInstructions.push_back(&I);
963  Changed = true;
964  continue;
965  }
966 
967  if (PHINode *PN = dyn_cast<PHINode>(&I)) {
968  if (CFH.canHoistPHI(PN)) {
969  // Redirect incoming blocks first to ensure that we create hoisted
970  // versions of those blocks before we hoist the phi.
971  for (unsigned int i = 0; i < PN->getNumIncomingValues(); ++i)
972  PN->setIncomingBlock(
973  i, CFH.getOrCreateHoistedBlock(PN->getIncomingBlock(i)));
974  hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
975  MSSAU, SE, ORE);
976  assert(DT->dominates(PN, BB) && "Conditional PHIs not expected");
977  Changed = true;
978  continue;
979  }
980  }
981 
982  // Remember possibly hoistable branches so we can actually hoist them
983  // later if needed.
984  if (BranchInst *BI = dyn_cast<BranchInst>(&I))
985  CFH.registerPossiblyHoistableBranch(BI);
986  }
987  }
988 
989  // If we hoisted instructions to a conditional block they may not dominate
990  // their uses that weren't hoisted (such as phis where some operands are not
991  // loop invariant). If so make them unconditional by moving them to their
992  // immediate dominator. We iterate through the instructions in reverse order
993  // which ensures that when we rehoist an instruction we rehoist its operands,
994  // and also keep track of where in the block we are rehoisting to to make sure
995  // that we rehoist instructions before the instructions that use them.
996  Instruction *HoistPoint = nullptr;
997  if (ControlFlowHoisting) {
998  for (Instruction *I : reverse(HoistedInstructions)) {
999  if (!llvm::all_of(I->uses(),
1000  [&](Use &U) { return DT->dominates(I, U); })) {
1001  BasicBlock *Dominator =
1002  DT->getNode(I->getParent())->getIDom()->getBlock();
1003  if (!HoistPoint || !DT->dominates(HoistPoint->getParent(), Dominator)) {
1004  if (HoistPoint)
1005  assert(DT->dominates(Dominator, HoistPoint->getParent()) &&
1006  "New hoist point expected to dominate old hoist point");
1007  HoistPoint = Dominator->getTerminator();
1008  }
1009  LLVM_DEBUG(dbgs() << "LICM rehoisting to "
1010  << HoistPoint->getParent()->getNameOrAsOperand()
1011  << ": " << *I << "\n");
1012  moveInstructionBefore(*I, *HoistPoint, *SafetyInfo, MSSAU, SE);
1013  HoistPoint = I;
1014  Changed = true;
1015  }
1016  }
1017  }
1018  if (VerifyMemorySSA)
1019  MSSAU.getMemorySSA()->verifyMemorySSA();
1020 
1021  // Now that we've finished hoisting make sure that LI and DT are still
1022  // valid.
1023 #ifdef EXPENSIVE_CHECKS
1024  if (Changed) {
1026  "Dominator tree verification failed");
1027  LI->verify(*DT);
1028  }
1029 #endif
1030 
1031  return Changed;
1032 }
1033 
1034 // Return true if LI is invariant within scope of the loop. LI is invariant if
1035 // CurLoop is dominated by an invariant.start representing the same memory
1036 // location and size as the memory location LI loads from, and also the
1037 // invariant.start has no uses.
1039  Loop *CurLoop) {
1040  Value *Addr = LI->getOperand(0);
1041  const DataLayout &DL = LI->getModule()->getDataLayout();
1042  const TypeSize LocSizeInBits = DL.getTypeSizeInBits(LI->getType());
1043 
1044  // It is not currently possible for clang to generate an invariant.start
1045  // intrinsic with scalable vector types because we don't support thread local
1046  // sizeless types and we don't permit sizeless types in structs or classes.
1047  // Furthermore, even if support is added for this in future the intrinsic
1048  // itself is defined to have a size of -1 for variable sized objects. This
1049  // makes it impossible to verify if the intrinsic envelops our region of
1050  // interest. For example, both <vscale x 32 x i8> and <vscale x 16 x i8>
1051  // types would have a -1 parameter, but the former is clearly double the size
1052  // of the latter.
1053  if (LocSizeInBits.isScalable())
1054  return false;
1055 
1056  // if the type is i8 addrspace(x)*, we know this is the type of
1057  // llvm.invariant.start operand
1058  auto *PtrInt8Ty = PointerType::get(Type::getInt8Ty(LI->getContext()),
1059  LI->getPointerAddressSpace());
1060  unsigned BitcastsVisited = 0;
1061  // Look through bitcasts until we reach the i8* type (this is invariant.start
1062  // operand type).
1063  while (Addr->getType() != PtrInt8Ty) {
1064  auto *BC = dyn_cast<BitCastInst>(Addr);
1065  // Avoid traversing high number of bitcast uses.
1066  if (++BitcastsVisited > MaxNumUsesTraversed || !BC)
1067  return false;
1068  Addr = BC->getOperand(0);
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.getFixedSize() <= InvariantSizeInBits &&
1099  DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
1100  return true;
1101  }
1102 
1103  return false;
1104 }
1105 
1106 namespace {
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.
1110 bool 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.
1121 bool 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.
1129 bool 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  Loop *CurLoop, MemorySSAUpdater &MSSAU,
1148  bool TargetExecutesOncePerLoop,
1149  SinkAndHoistLICMFlags &Flags,
1151  // If we don't understand the instruction, bail early.
1152  if (!isHoistableAndSinkableInst(I))
1153  return false;
1154 
1155  MemorySSA *MSSA = MSSAU.getMemorySSA();
1156  // Loads have extra constraints we have to verify before we can hoist them.
1157  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
1158  if (!LI->isUnordered())
1159  return false; // Don't sink/hoist volatile or ordered atomic loads!
1160 
1161  // Loads from constant memory are always safe to move, even if they end up
1162  // in the same alias set as something that ends up being modified.
1163  if (!isModSet(AA->getModRefInfoMask(LI->getOperand(0))))
1164  return true;
1165  if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1166  return true;
1167 
1168  if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1169  return false; // Don't risk duplicating unordered loads
1170 
1171  // This checks for an invariant.start dominating the load.
1172  if (isLoadInvariantInLoop(LI, DT, CurLoop))
1173  return true;
1174 
1175  bool Invalidated = pointerInvalidatedByLoop(
1176  MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)), CurLoop, I, Flags);
1177  // Check loop-invariant address because this may also be a sinkable load
1178  // whose address is not necessarily loop-invariant.
1179  if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1180  ORE->emit([&]() {
1181  return OptimizationRemarkMissed(
1182  DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
1183  << "failed to move load with loop-invariant address "
1184  "because the loop may invalidate its value";
1185  });
1186 
1187  return !Invalidated;
1188  } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1189  // Don't sink or hoist dbg info; it's legal, but not useful.
1190  if (isa<DbgInfoIntrinsic>(I))
1191  return false;
1192 
1193  // Don't sink calls which can throw.
1194  if (CI->mayThrow())
1195  return false;
1196 
1197  // Convergent attribute has been used on operations that involve
1198  // inter-thread communication which results are implicitly affected by the
1199  // enclosing control flows. It is not safe to hoist or sink such operations
1200  // across control flow.
1201  if (CI->isConvergent())
1202  return false;
1203 
1204  using namespace PatternMatch;
1205  if (match(CI, m_Intrinsic<Intrinsic::assume>()))
1206  // Assumes don't actually alias anything or throw
1207  return true;
1208 
1209  if (match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
1210  // Widenable conditions don't actually alias anything or throw
1211  return true;
1212 
1213  // Handle simple cases by querying alias analysis.
1214  MemoryEffects Behavior = AA->getMemoryEffects(CI);
1215  if (Behavior.doesNotAccessMemory())
1216  return true;
1217  if (Behavior.onlyReadsMemory()) {
1218  // A readonly argmemonly function only reads from memory pointed to by
1219  // it's arguments with arbitrary offsets. If we can prove there are no
1220  // writes to this memory in the loop, we can hoist or sink.
1221  if (Behavior.onlyAccessesArgPointees()) {
1222  // TODO: expand to writeable arguments
1223  for (Value *Op : CI->args())
1224  if (Op->getType()->isPointerTy() &&
1226  MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(CI)), CurLoop, I,
1227  Flags))
1228  return false;
1229  return true;
1230  }
1231 
1232  // If this call only reads from memory and there are no writes to memory
1233  // in the loop, we can hoist or sink the call as appropriate.
1234  if (isReadOnly(MSSAU, CurLoop))
1235  return true;
1236  }
1237 
1238  // FIXME: This should use mod/ref information to see if we can hoist or
1239  // sink the call.
1240 
1241  return false;
1242  } else if (auto *FI = dyn_cast<FenceInst>(&I)) {
1243  // Fences alias (most) everything to provide ordering. For the moment,
1244  // just give up if there are any other memory operations in the loop.
1245  return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
1246  } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
1247  if (!SI->isUnordered())
1248  return false; // Don't sink/hoist volatile or ordered atomic store!
1249 
1250  // We can only hoist a store that we can prove writes a value which is not
1251  // read or overwritten within the loop. For those cases, we fallback to
1252  // load store promotion instead. TODO: We can extend this to cases where
1253  // there is exactly one write to the location and that write dominates an
1254  // arbitrary number of reads in the loop.
1255  if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
1256  return true;
1257  // If there are more accesses than the Promotion cap or no "quota" to
1258  // check clobber, then give up as we're not walking a list that long.
1259  if (Flags.tooManyMemoryAccesses() || Flags.tooManyClobberingCalls())
1260  return false;
1261  // If there are interfering Uses (i.e. their defining access is in the
1262  // loop), or ordered loads (stored as Defs!), don't move this store.
1263  // Could do better here, but this is conservatively correct.
1264  // TODO: Cache set of Uses on the first walk in runOnLoop, update when
1265  // moving accesses. Can also extend to dominating uses.
1266  auto *SIMD = MSSA->getMemoryAccess(SI);
1267  for (auto *BB : CurLoop->getBlocks())
1268  if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
1269  for (const auto &MA : *Accesses)
1270  if (const auto *MU = dyn_cast<MemoryUse>(&MA)) {
1271  auto *MD = MU->getDefiningAccess();
1272  if (!MSSA->isLiveOnEntryDef(MD) &&
1273  CurLoop->contains(MD->getBlock()))
1274  return false;
1275  // Disable hoisting past potentially interfering loads. Optimized
1276  // Uses may point to an access outside the loop, as getClobbering
1277  // checks the previous iteration when walking the backedge.
1278  // FIXME: More precise: no Uses that alias SI.
1279  if (!Flags.getIsSink() && !MSSA->dominates(SIMD, MU))
1280  return false;
1281  } else if (const auto *MD = dyn_cast<MemoryDef>(&MA)) {
1282  if (auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
1283  (void)LI; // Silence warning.
1284  assert(!LI->isUnordered() && "Expected unordered load");
1285  return false;
1286  }
1287  // Any call, while it may not be clobbering SI, it may be a use.
1288  if (auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
1289  // Check if the call may read from the memory location written
1290  // to by SI. Check CI's attributes and arguments; the number of
1291  // such checks performed is limited above by NoOfMemAccTooLarge.
1293  if (isModOrRefSet(MRI))
1294  return false;
1295  }
1296  }
1297  }
1299  Flags.incrementClobberingCalls();
1300  // If there are no clobbering Defs in the loop, store is safe to hoist.
1301  return MSSA->isLiveOnEntryDef(Source) ||
1302  !CurLoop->contains(Source->getBlock());
1303  }
1304 
1305  assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
1306 
1307  // We've established mechanical ability and aliasing, it's up to the caller
1308  // to check fault safety
1309  return true;
1310 }
1311 
1312 /// Returns true if a PHINode is a trivially replaceable with an
1313 /// Instruction.
1314 /// This is true when all incoming values are that instruction.
1315 /// This pattern occurs most often with LCSSA PHI nodes.
1316 ///
1317 static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I) {
1318  for (const Value *IncValue : PN.incoming_values())
1319  if (IncValue != &I)
1320  return false;
1321 
1322  return true;
1323 }
1324 
1325 /// Return true if the instruction is free in the loop.
1326 static bool isFreeInLoop(const Instruction &I, const Loop *CurLoop,
1327  const TargetTransformInfo *TTI) {
1328  InstructionCost CostI =
1329  TTI->getInstructionCost(&I, TargetTransformInfo::TCK_SizeAndLatency);
1330 
1331  if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1332  if (CostI != TargetTransformInfo::TCC_Free)
1333  return false;
1334  // For a GEP, we cannot simply use getInstructionCost because currently
1335  // it optimistically assumes that a GEP will fold into addressing mode
1336  // regardless of its users.
1337  const BasicBlock *BB = GEP->getParent();
1338  for (const User *U : GEP->users()) {
1339  const Instruction *UI = cast<Instruction>(U);
1340  if (CurLoop->contains(UI) &&
1341  (BB != UI->getParent() ||
1342  (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1343  return false;
1344  }
1345  return true;
1346  }
1347 
1348  return CostI == TargetTransformInfo::TCC_Free;
1349 }
1350 
1351 /// Return true if the only users of this instruction are outside of
1352 /// the loop. If this is true, we can sink the instruction to the exit
1353 /// blocks of the loop.
1354 ///
1355 /// We also return true if the instruction could be folded away in lowering.
1356 /// (e.g., a GEP can be folded into a load as an addressing mode in the loop).
1357 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
1358  const LoopSafetyInfo *SafetyInfo,
1359  TargetTransformInfo *TTI, bool &FreeInLoop,
1360  bool LoopNestMode) {
1361  const auto &BlockColors = SafetyInfo->getBlockColors();
1362  bool IsFree = isFreeInLoop(I, CurLoop, TTI);
1363  for (const User *U : I.users()) {
1364  const Instruction *UI = cast<Instruction>(U);
1365  if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
1366  const BasicBlock *BB = PN->getParent();
1367  // We cannot sink uses in catchswitches.
1368  if (isa<CatchSwitchInst>(BB->getTerminator()))
1369  return false;
1370 
1371  // We need to sink a callsite to a unique funclet. Avoid sinking if the
1372  // phi use is too muddled.
1373  if (isa<CallInst>(I))
1374  if (!BlockColors.empty() &&
1375  BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
1376  return false;
1377 
1378  if (LoopNestMode) {
1379  while (isa<PHINode>(UI) && UI->hasOneUser() &&
1380  UI->getNumOperands() == 1) {
1381  if (!CurLoop->contains(UI))
1382  break;
1383  UI = cast<Instruction>(UI->user_back());
1384  }
1385  }
1386  }
1387 
1388  if (CurLoop->contains(UI)) {
1389  if (IsFree) {
1390  FreeInLoop = true;
1391  continue;
1392  }
1393  return false;
1394  }
1395  }
1396  return true;
1397 }
1398 
1400  Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
1401  const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU) {
1402  Instruction *New;
1403  if (auto *CI = dyn_cast<CallInst>(&I)) {
1404  const auto &BlockColors = SafetyInfo->getBlockColors();
1405 
1406  // Sinking call-sites need to be handled differently from other
1407  // instructions. The cloned call-site needs a funclet bundle operand
1408  // appropriate for its location in the CFG.
1410  for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1411  BundleIdx != BundleEnd; ++BundleIdx) {
1412  OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
1413  if (Bundle.getTagID() == LLVMContext::OB_funclet)
1414  continue;
1415 
1416  OpBundles.emplace_back(Bundle);
1417  }
1418 
1419  if (!BlockColors.empty()) {
1420  const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1421  assert(CV.size() == 1 && "non-unique color for exit block!");
1422  BasicBlock *BBColor = CV.front();
1423  Instruction *EHPad = BBColor->getFirstNonPHI();
1424  if (EHPad->isEHPad())
1425  OpBundles.emplace_back("funclet", EHPad);
1426  }
1427 
1428  New = CallInst::Create(CI, OpBundles);
1429  } else {
1430  New = I.clone();
1431  }
1432 
1433  ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
1434  if (!I.getName().empty())
1435  New->setName(I.getName() + ".le");
1436 
1437  if (MSSAU.getMemorySSA()->getMemoryAccess(&I)) {
1438  // Create a new MemoryAccess and let MemorySSA set its defining access.
1439  MemoryAccess *NewMemAcc = MSSAU.createMemoryAccessInBB(
1440  New, nullptr, New->getParent(), MemorySSA::Beginning);
1441  if (NewMemAcc) {
1442  if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1443  MSSAU.insertDef(MemDef, /*RenameUses=*/true);
1444  else {
1445  auto *MemUse = cast<MemoryUse>(NewMemAcc);
1446  MSSAU.insertUse(MemUse, /*RenameUses=*/true);
1447  }
1448  }
1449  }
1450 
1451  // Build LCSSA PHI nodes for any in-loop operands (if legal). Note that
1452  // this is particularly cheap because we can rip off the PHI node that we're
1453  // replacing for the number and blocks of the predecessors.
1454  // OPT: If this shows up in a profile, we can instead finish sinking all
1455  // invariant instructions, and then walk their operands to re-establish
1456  // LCSSA. That will eliminate creating PHI nodes just to nuke them when
1457  // sinking bottom-up.
1458  for (Use &Op : New->operands())
1459  if (LI->wouldBeOutOfLoopUseRequiringLCSSA(Op.get(), PN.getParent())) {
1460  auto *OInst = cast<Instruction>(Op.get());
1461  PHINode *OpPN =
1462  PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
1463  OInst->getName() + ".lcssa", &ExitBlock.front());
1464  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1465  OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
1466  Op = OpPN;
1467  }
1468  return New;
1469 }
1470 
1472  MemorySSAUpdater &MSSAU) {
1473  MSSAU.removeMemoryAccess(&I);
1474  SafetyInfo.removeInstruction(&I);
1475  I.eraseFromParent();
1476 }
1477 
1479  ICFLoopSafetyInfo &SafetyInfo,
1480  MemorySSAUpdater &MSSAU,
1481  ScalarEvolution *SE) {
1482  SafetyInfo.removeInstruction(&I);
1483  SafetyInfo.insertInstructionTo(&I, Dest.getParent());
1484  I.moveBefore(&Dest);
1485  if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
1486  MSSAU.getMemorySSA()->getMemoryAccess(&I)))
1487  MSSAU.moveToPlace(OldMemAcc, Dest.getParent(), MemorySSA::BeforeTerminator);
1488  if (SE)
1489  SE->forgetValue(&I);
1490 }
1491 
1493  PHINode *TPN, Instruction *I, LoopInfo *LI,
1495  const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop,
1496  MemorySSAUpdater &MSSAU) {
1498  "Expect only trivially replaceable PHI");
1499  BasicBlock *ExitBlock = TPN->getParent();
1500  Instruction *New;
1501  auto It = SunkCopies.find(ExitBlock);
1502  if (It != SunkCopies.end())
1503  New = It->second;
1504  else
1505  New = SunkCopies[ExitBlock] = cloneInstructionInExitBlock(
1506  *I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1507  return New;
1508 }
1509 
1510 static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo) {
1511  BasicBlock *BB = PN->getParent();
1512  if (!BB->canSplitPredecessors())
1513  return false;
1514  // It's not impossible to split EHPad blocks, but if BlockColors already exist
1515  // it require updating BlockColors for all offspring blocks accordingly. By
1516  // skipping such corner case, we can make updating BlockColors after splitting
1517  // predecessor fairly simple.
1518  if (!SafetyInfo->getBlockColors().empty() && BB->getFirstNonPHI()->isEHPad())
1519  return false;
1520  for (BasicBlock *BBPred : predecessors(BB)) {
1521  if (isa<IndirectBrInst>(BBPred->getTerminator()))
1522  return false;
1523  }
1524  return true;
1525 }
1526 
1528  LoopInfo *LI, const Loop *CurLoop,
1529  LoopSafetyInfo *SafetyInfo,
1530  MemorySSAUpdater *MSSAU) {
1531 #ifndef NDEBUG
1532  SmallVector<BasicBlock *, 32> ExitBlocks;
1533  CurLoop->getUniqueExitBlocks(ExitBlocks);
1534  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1535  ExitBlocks.end());
1536 #endif
1537  BasicBlock *ExitBB = PN->getParent();
1538  assert(ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block.");
1539 
1540  // Split predecessors of the loop exit to make instructions in the loop are
1541  // exposed to exit blocks through trivially replaceable PHIs while keeping the
1542  // loop in the canonical form where each predecessor of each exit block should
1543  // be contained within the loop. For example, this will convert the loop below
1544  // from
1545  //
1546  // LB1:
1547  // %v1 =
1548  // br %LE, %LB2
1549  // LB2:
1550  // %v2 =
1551  // br %LE, %LB1
1552  // LE:
1553  // %p = phi [%v1, %LB1], [%v2, %LB2] <-- non-trivially replaceable
1554  //
1555  // to
1556  //
1557  // LB1:
1558  // %v1 =
1559  // br %LE.split, %LB2
1560  // LB2:
1561  // %v2 =
1562  // br %LE.split2, %LB1
1563  // LE.split:
1564  // %p1 = phi [%v1, %LB1] <-- trivially replaceable
1565  // br %LE
1566  // LE.split2:
1567  // %p2 = phi [%v2, %LB2] <-- trivially replaceable
1568  // br %LE
1569  // LE:
1570  // %p = phi [%p1, %LE.split], [%p2, %LE.split2]
1571  //
1572  const auto &BlockColors = SafetyInfo->getBlockColors();
1573  SmallSetVector<BasicBlock *, 8> PredBBs(pred_begin(ExitBB), pred_end(ExitBB));
1574  while (!PredBBs.empty()) {
1575  BasicBlock *PredBB = *PredBBs.begin();
1576  assert(CurLoop->contains(PredBB) &&
1577  "Expect all predecessors are in the loop");
1578  if (PN->getBasicBlockIndex(PredBB) >= 0) {
1580  ExitBB, PredBB, ".split.loop.exit", DT, LI, MSSAU, true);
1581  // Since we do not allow splitting EH-block with BlockColors in
1582  // canSplitPredecessors(), we can simply assign predecessor's color to
1583  // the new block.
1584  if (!BlockColors.empty())
1585  // Grab a reference to the ColorVector to be inserted before getting the
1586  // reference to the vector we are copying because inserting the new
1587  // element in BlockColors might cause the map to be reallocated.
1588  SafetyInfo->copyColors(NewPred, PredBB);
1589  }
1590  PredBBs.remove(PredBB);
1591  }
1592 }
1593 
1594 /// When an instruction is found to only be used outside of the loop, this
1595 /// function moves it to the exit blocks and patches up SSA form as needed.
1596 /// This method is guaranteed to remove the original instruction from its
1597 /// position, and may either delete it or move it to outside of the loop.
1598 ///
1599 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
1600  const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
1602  bool Changed = false;
1603  LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
1604 
1605  // Iterate over users to be ready for actual sinking. Replace users via
1606  // unreachable blocks with undef and make all user PHIs trivially replaceable.
1607  SmallPtrSet<Instruction *, 8> VisitedUsers;
1608  for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
1609  auto *User = cast<Instruction>(*UI);
1610  Use &U = UI.getUse();
1611  ++UI;
1612 
1613  if (VisitedUsers.count(User) || CurLoop->contains(User))
1614  continue;
1615 
1616  if (!DT->isReachableFromEntry(User->getParent())) {
1617  U = PoisonValue::get(I.getType());
1618  Changed = true;
1619  continue;
1620  }
1621 
1622  // The user must be a PHI node.
1623  PHINode *PN = cast<PHINode>(User);
1624 
1625  // Surprisingly, instructions can be used outside of loops without any
1626  // exits. This can only happen in PHI nodes if the incoming block is
1627  // unreachable.
1628  BasicBlock *BB = PN->getIncomingBlock(U);
1629  if (!DT->isReachableFromEntry(BB)) {
1630  U = PoisonValue::get(I.getType());
1631  Changed = true;
1632  continue;
1633  }
1634 
1635  VisitedUsers.insert(PN);
1636  if (isTriviallyReplaceablePHI(*PN, I))
1637  continue;
1638 
1639  if (!canSplitPredecessors(PN, SafetyInfo))
1640  return Changed;
1641 
1642  // Split predecessors of the PHI so that we can make users trivially
1643  // replaceable.
1644  splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo, &MSSAU);
1645 
1646  // Should rebuild the iterators, as they may be invalidated by
1647  // splitPredecessorsOfLoopExit().
1648  UI = I.user_begin();
1649  UE = I.user_end();
1650  }
1651 
1652  if (VisitedUsers.empty())
1653  return Changed;
1654 
1655  ORE->emit([&]() {
1656  return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
1657  << "sinking " << ore::NV("Inst", &I);
1658  });
1659  if (isa<LoadInst>(I))
1660  ++NumMovedLoads;
1661  else if (isa<CallInst>(I))
1662  ++NumMovedCalls;
1663  ++NumSunk;
1664 
1665 #ifndef NDEBUG
1666  SmallVector<BasicBlock *, 32> ExitBlocks;
1667  CurLoop->getUniqueExitBlocks(ExitBlocks);
1668  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1669  ExitBlocks.end());
1670 #endif
1671 
1672  // Clones of this instruction. Don't create more than one per exit block!
1674 
1675  // If this instruction is only used outside of the loop, then all users are
1676  // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
1677  // the instruction.
1678  // First check if I is worth sinking for all uses. Sink only when it is worth
1679  // across all uses.
1680  SmallSetVector<User*, 8> Users(I.user_begin(), I.user_end());
1681  for (auto *UI : Users) {
1682  auto *User = cast<Instruction>(UI);
1683 
1684  if (CurLoop->contains(User))
1685  continue;
1686 
1687  PHINode *PN = cast<PHINode>(User);
1688  assert(ExitBlockSet.count(PN->getParent()) &&
1689  "The LCSSA PHI is not in an exit block!");
1690 
1691  // The PHI must be trivially replaceable.
1693  PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1694  PN->replaceAllUsesWith(New);
1695  eraseInstruction(*PN, *SafetyInfo, MSSAU);
1696  Changed = true;
1697  }
1698  return Changed;
1699 }
1700 
1701 /// When an instruction is found to only use loop invariant operands that
1702 /// is safe to hoist, this instruction is called to do the dirty work.
1703 ///
1704 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
1705  BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
1706  MemorySSAUpdater &MSSAU, ScalarEvolution *SE,
1708  LLVM_DEBUG(dbgs() << "LICM hoisting to " << Dest->getNameOrAsOperand() << ": "
1709  << I << "\n");
1710  ORE->emit([&]() {
1711  return OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting "
1712  << ore::NV("Inst", &I);
1713  });
1714 
1715  // Metadata can be dependent on conditions we are hoisting above.
1716  // Conservatively strip all metadata on the instruction unless we were
1717  // guaranteed to execute I if we entered the loop, in which case the metadata
1718  // is valid in the loop preheader.
1719  // Similarly, If I is a call and it is not guaranteed to execute in the loop,
1720  // then moving to the preheader means we should strip attributes on the call
1721  // that can cause UB since we may be hoisting above conditions that allowed
1722  // inferring those attributes. They may not be valid at the preheader.
1723  if ((I.hasMetadataOtherThanDebugLoc() || isa<CallInst>(I)) &&
1724  // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
1725  // time in isGuaranteedToExecute if we don't actually have anything to
1726  // drop. It is a compile time optimization, not required for correctness.
1727  !SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop))
1728  I.dropUndefImplyingAttrsAndUnknownMetadata();
1729 
1730  if (isa<PHINode>(I))
1731  // Move the new node to the end of the phi list in the destination block.
1732  moveInstructionBefore(I, *Dest->getFirstNonPHI(), *SafetyInfo, MSSAU, SE);
1733  else
1734  // Move the new node to the destination block, before its terminator.
1735  moveInstructionBefore(I, *Dest->getTerminator(), *SafetyInfo, MSSAU, SE);
1736 
1737  I.updateLocationAfterHoist();
1738 
1739  if (isa<LoadInst>(I))
1740  ++NumMovedLoads;
1741  else if (isa<CallInst>(I))
1742  ++NumMovedCalls;
1743  ++NumHoisted;
1744 }
1745 
1746 /// Only sink or hoist an instruction if it is not a trapping instruction,
1747 /// or if the instruction is known not to trap when moved to the preheader.
1748 /// or if it is a trapping instruction and is guaranteed to execute.
1750  Instruction &Inst, const DominatorTree *DT, const TargetLibraryInfo *TLI,
1751  const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo,
1752  OptimizationRemarkEmitter *ORE, const Instruction *CtxI,
1753  AssumptionCache *AC, bool AllowSpeculation) {
1754  if (AllowSpeculation &&
1755  isSafeToSpeculativelyExecute(&Inst, CtxI, AC, DT, TLI))
1756  return true;
1757 
1758  bool GuaranteedToExecute =
1759  SafetyInfo->isGuaranteedToExecute(Inst, DT, CurLoop);
1760 
1761  if (!GuaranteedToExecute) {
1762  auto *LI = dyn_cast<LoadInst>(&Inst);
1763  if (LI && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1764  ORE->emit([&]() {
1765  return OptimizationRemarkMissed(
1766  DEBUG_TYPE, "LoadWithLoopInvariantAddressCondExecuted", LI)
1767  << "failed to hoist load with loop-invariant address "
1768  "because load is conditionally executed";
1769  });
1770  }
1771 
1772  return GuaranteedToExecute;
1773 }
1774 
1775 namespace {
1776 class LoopPromoter : public LoadAndStorePromoter {
1777  Value *SomePtr; // Designated pointer to store to.
1778  const SmallSetVector<Value *, 8> &PointerMustAliases;
1779  SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
1780  SmallVectorImpl<Instruction *> &LoopInsertPts;
1781  SmallVectorImpl<MemoryAccess *> &MSSAInsertPts;
1782  PredIteratorCache &PredCache;
1783  MemorySSAUpdater &MSSAU;
1784  LoopInfo &LI;
1785  DebugLoc DL;
1786  Align Alignment;
1787  bool UnorderedAtomic;
1788  AAMDNodes AATags;
1789  ICFLoopSafetyInfo &SafetyInfo;
1790  bool CanInsertStoresInExitBlocks;
1792 
1793  // We're about to add a use of V in a loop exit block. Insert an LCSSA phi
1794  // (if legal) if doing so would add an out-of-loop use to an instruction
1795  // defined in-loop.
1796  Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
1798  return V;
1799 
1800  Instruction *I = cast<Instruction>(V);
1801  // We need to create an LCSSA PHI node for the incoming value and
1802  // store that.
1803  PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
1804  I->getName() + ".lcssa", &BB->front());
1805  for (BasicBlock *Pred : PredCache.get(BB))
1806  PN->addIncoming(I, Pred);
1807  return PN;
1808  }
1809 
1810 public:
1811  LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
1812  const SmallSetVector<Value *, 8> &PMA,
1816  MemorySSAUpdater &MSSAU, LoopInfo &li, DebugLoc dl,
1817  Align Alignment, bool UnorderedAtomic, const AAMDNodes &AATags,
1818  ICFLoopSafetyInfo &SafetyInfo, bool CanInsertStoresInExitBlocks)
1819  : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
1820  LoopExitBlocks(LEB), LoopInsertPts(LIP), MSSAInsertPts(MSSAIP),
1821  PredCache(PIC), MSSAU(MSSAU), LI(li), DL(std::move(dl)),
1822  Alignment(Alignment), UnorderedAtomic(UnorderedAtomic), AATags(AATags),
1823  SafetyInfo(SafetyInfo),
1824  CanInsertStoresInExitBlocks(CanInsertStoresInExitBlocks), Uses(Insts) {}
1825 
1826  bool isInstInList(Instruction *I,
1827  const SmallVectorImpl<Instruction *> &) const override {
1828  Value *Ptr;
1829  if (LoadInst *LI = dyn_cast<LoadInst>(I))
1830  Ptr = LI->getOperand(0);
1831  else
1832  Ptr = cast<StoreInst>(I)->getPointerOperand();
1833  return PointerMustAliases.count(Ptr);
1834  }
1835 
1836  void insertStoresInLoopExitBlocks() {
1837  // Insert stores after in the loop exit blocks. Each exit block gets a
1838  // store of the live-out values that feed them. Since we've already told
1839  // the SSA updater about the defs in the loop and the preheader
1840  // definition, it is all set and we can start using it.
1841  DIAssignID *NewID = nullptr;
1842  for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
1843  BasicBlock *ExitBlock = LoopExitBlocks[i];
1844  Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
1845  LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1846  Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1847  Instruction *InsertPos = LoopInsertPts[i];
1848  StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
1849  if (UnorderedAtomic)
1851  NewSI->setAlignment(Alignment);
1852  NewSI->setDebugLoc(DL);
1853  // Attach DIAssignID metadata to the new store, generating it on the
1854  // first loop iteration.
1855  if (i == 0) {
1856  // NewSI will have its DIAssignID set here if there are any stores in
1857  // Uses with a DIAssignID attachment. This merged ID will then be
1858  // attached to the other inserted stores (in the branch below).
1859  NewSI->mergeDIAssignID(Uses);
1860  NewID = cast_or_null<DIAssignID>(
1861  NewSI->getMetadata(LLVMContext::MD_DIAssignID));
1862  } else {
1863  // Attach the DIAssignID (or nullptr) merged from Uses in the branch
1864  // above.
1865  NewSI->setMetadata(LLVMContext::MD_DIAssignID, NewID);
1866  }
1867 
1868  if (AATags)
1869  NewSI->setAAMetadata(AATags);
1870 
1871  MemoryAccess *MSSAInsertPoint = MSSAInsertPts[i];
1872  MemoryAccess *NewMemAcc;
1873  if (!MSSAInsertPoint) {
1874  NewMemAcc = MSSAU.createMemoryAccessInBB(
1875  NewSI, nullptr, NewSI->getParent(), MemorySSA::Beginning);
1876  } else {
1877  NewMemAcc =
1878  MSSAU.createMemoryAccessAfter(NewSI, nullptr, MSSAInsertPoint);
1879  }
1880  MSSAInsertPts[i] = NewMemAcc;
1881  MSSAU.insertDef(cast<MemoryDef>(NewMemAcc), true);
1882  // FIXME: true for safety, false may still be correct.
1883  }
1884  }
1885 
1886  void doExtraRewritesBeforeFinalDeletion() override {
1887  if (CanInsertStoresInExitBlocks)
1888  insertStoresInLoopExitBlocks();
1889  }
1890 
1891  void instructionDeleted(Instruction *I) const override {
1892  SafetyInfo.removeInstruction(I);
1893  MSSAU.removeMemoryAccess(I);
1894  }
1895 
1896  bool shouldDelete(Instruction *I) const override {
1897  if (isa<StoreInst>(I))
1898  return CanInsertStoresInExitBlocks;
1899  return true;
1900  }
1901 };
1902 
1903 bool isNotCapturedBeforeOrInLoop(const Value *V, const Loop *L,
1904  DominatorTree *DT) {
1905  // We can perform the captured-before check against any instruction in the
1906  // loop header, as the loop header is reachable from any instruction inside
1907  // the loop.
1908  // TODO: ReturnCaptures=true shouldn't be necessary here.
1909  return !PointerMayBeCapturedBefore(V, /* ReturnCaptures */ true,
1910  /* StoreCaptures */ true,
1911  L->getHeader()->getTerminator(), DT);
1912 }
1913 
1914 /// Return true if we can prove that a caller cannot inspect the object if an
1915 /// unwind occurs inside the loop.
1916 bool isNotVisibleOnUnwindInLoop(const Value *Object, const Loop *L,
1917  DominatorTree *DT) {
1918  bool RequiresNoCaptureBeforeUnwind;
1919  if (!isNotVisibleOnUnwind(Object, RequiresNoCaptureBeforeUnwind))
1920  return false;
1921 
1922  return !RequiresNoCaptureBeforeUnwind ||
1923  isNotCapturedBeforeOrInLoop(Object, L, DT);
1924 }
1925 
1926 bool isWritableObject(const Value *Object) {
1927  // TODO: Alloca might not be writable after its lifetime ends.
1928  // See https://github.com/llvm/llvm-project/issues/51838.
1929  if (isa<AllocaInst>(Object))
1930  return true;
1931 
1932  // TODO: Also handle sret.
1933  if (auto *A = dyn_cast<Argument>(Object))
1934  return A->hasByValAttr();
1935 
1936  if (auto *G = dyn_cast<GlobalVariable>(Object))
1937  return !G->isConstant();
1938 
1939  // TODO: Noalias has nothing to do with writability, this should check for
1940  // an allocator function.
1941  return isNoAliasCall(Object);
1942 }
1943 
1944 bool isThreadLocalObject(const Value *Object, const Loop *L, DominatorTree *DT,
1946  // The object must be function-local to start with, and then not captured
1947  // before/in the loop.
1948  return (isIdentifiedFunctionLocal(Object) &&
1949  isNotCapturedBeforeOrInLoop(Object, L, DT)) ||
1951 }
1952 
1953 } // namespace
1954 
1955 /// Try to promote memory values to scalars by sinking stores out of the
1956 /// loop and moving loads to before the loop. We do this by looping over
1957 /// the stores in the loop, looking for stores to Must pointers which are
1958 /// loop invariant.
1959 ///
1961  const SmallSetVector<Value *, 8> &PointerMustAliases,
1962  SmallVectorImpl<BasicBlock *> &ExitBlocks,
1963  SmallVectorImpl<Instruction *> &InsertPts,
1965  LoopInfo *LI, DominatorTree *DT, AssumptionCache *AC,
1966  const TargetLibraryInfo *TLI, TargetTransformInfo *TTI, Loop *CurLoop,
1967  MemorySSAUpdater &MSSAU, ICFLoopSafetyInfo *SafetyInfo,
1968  OptimizationRemarkEmitter *ORE, bool AllowSpeculation) {
1969  // Verify inputs.
1970  assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
1971  SafetyInfo != nullptr &&
1972  "Unexpected Input to promoteLoopAccessesToScalars");
1973 
1974  LLVM_DEBUG({
1975  dbgs() << "Trying to promote set of must-aliased pointers:\n";
1976  for (Value *Ptr : PointerMustAliases)
1977  dbgs() << " " << *Ptr << "\n";
1978  });
1979  ++NumPromotionCandidates;
1980 
1981  Value *SomePtr = *PointerMustAliases.begin();
1982  BasicBlock *Preheader = CurLoop->getLoopPreheader();
1983 
1984  // It is not safe to promote a load/store from the loop if the load/store is
1985  // conditional. For example, turning:
1986  //
1987  // for () { if (c) *P += 1; }
1988  //
1989  // into:
1990  //
1991  // tmp = *P; for () { if (c) tmp +=1; } *P = tmp;
1992  //
1993  // is not safe, because *P may only be valid to access if 'c' is true.
1994  //
1995  // The safety property divides into two parts:
1996  // p1) The memory may not be dereferenceable on entry to the loop. In this
1997  // case, we can't insert the required load in the preheader.
1998  // p2) The memory model does not allow us to insert a store along any dynamic
1999  // path which did not originally have one.
2000  //
2001  // If at least one store is guaranteed to execute, both properties are
2002  // satisfied, and promotion is legal.
2003  //
2004  // This, however, is not a necessary condition. Even if no store/load is
2005  // guaranteed to execute, we can still establish these properties.
2006  // We can establish (p1) by proving that hoisting the load into the preheader
2007  // is safe (i.e. proving dereferenceability on all paths through the loop). We
2008  // can use any access within the alias set to prove dereferenceability,
2009  // since they're all must alias.
2010  //
2011  // There are two ways establish (p2):
2012  // a) Prove the location is thread-local. In this case the memory model
2013  // requirement does not apply, and stores are safe to insert.
2014  // b) Prove a store dominates every exit block. In this case, if an exit
2015  // blocks is reached, the original dynamic path would have taken us through
2016  // the store, so inserting a store into the exit block is safe. Note that this
2017  // is different from the store being guaranteed to execute. For instance,
2018  // if an exception is thrown on the first iteration of the loop, the original
2019  // store is never executed, but the exit blocks are not executed either.
2020 
2021  bool DereferenceableInPH = false;
2022  bool StoreIsGuanteedToExecute = false;
2023  bool FoundLoadToPromote = false;
2024  // Goes from Unknown to either Safe or Unsafe, but can't switch between them.
2025  enum {
2026  StoreSafe,
2027  StoreUnsafe,
2028  StoreSafetyUnknown,
2029  } StoreSafety = StoreSafetyUnknown;
2030 
2032 
2033  // We start with an alignment of one and try to find instructions that allow
2034  // us to prove better alignment.
2035  Align Alignment;
2036  // Keep track of which types of access we see
2037  bool SawUnorderedAtomic = false;
2038  bool SawNotAtomic = false;
2039  AAMDNodes AATags;
2040 
2041  const DataLayout &MDL = Preheader->getModule()->getDataLayout();
2042 
2043  if (SafetyInfo->anyBlockMayThrow()) {
2044  // If a loop can throw, we have to insert a store along each unwind edge.
2045  // That said, we can't actually make the unwind edge explicit. Therefore,
2046  // we have to prove that the store is dead along the unwind edge. We do
2047  // this by proving that the caller can't have a reference to the object
2048  // after return and thus can't possibly load from the object.
2049  Value *Object = getUnderlyingObject(SomePtr);
2050  if (!isNotVisibleOnUnwindInLoop(Object, CurLoop, DT))
2051  StoreSafety = StoreUnsafe;
2052  }
2053 
2054  // Check that all accesses to pointers in the alias set use the same type.
2055  // We cannot (yet) promote a memory location that is loaded and stored in
2056  // different sizes. While we are at it, collect alignment and AA info.
2057  Type *AccessTy = nullptr;
2058  for (Value *ASIV : PointerMustAliases) {
2059  for (Use &U : ASIV->uses()) {
2060  // Ignore instructions that are outside the loop.
2061  Instruction *UI = dyn_cast<Instruction>(U.getUser());
2062  if (!UI || !CurLoop->contains(UI))
2063  continue;
2064 
2065  // If there is an non-load/store instruction in the loop, we can't promote
2066  // it.
2067  if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
2068  if (!Load->isUnordered())
2069  return false;
2070 
2071  SawUnorderedAtomic |= Load->isAtomic();
2072  SawNotAtomic |= !Load->isAtomic();
2073  FoundLoadToPromote = true;
2074 
2075  Align InstAlignment = Load->getAlign();
2076 
2077  // Note that proving a load safe to speculate requires proving
2078  // sufficient alignment at the target location. Proving it guaranteed
2079  // to execute does as well. Thus we can increase our guaranteed
2080  // alignment as well.
2081  if (!DereferenceableInPH || (InstAlignment > Alignment))
2083  *Load, DT, TLI, CurLoop, SafetyInfo, ORE,
2084  Preheader->getTerminator(), AC, AllowSpeculation)) {
2085  DereferenceableInPH = true;
2086  Alignment = std::max(Alignment, InstAlignment);
2087  }
2088  } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
2089  // Stores *of* the pointer are not interesting, only stores *to* the
2090  // pointer.
2091  if (U.getOperandNo() != StoreInst::getPointerOperandIndex())
2092  continue;
2093  if (!Store->isUnordered())
2094  return false;
2095 
2096  SawUnorderedAtomic |= Store->isAtomic();
2097  SawNotAtomic |= !Store->isAtomic();
2098 
2099  // If the store is guaranteed to execute, both properties are satisfied.
2100  // We may want to check if a store is guaranteed to execute even if we
2101  // already know that promotion is safe, since it may have higher
2102  // alignment than any other guaranteed stores, in which case we can
2103  // raise the alignment on the promoted store.
2104  Align InstAlignment = Store->getAlign();
2105  bool GuaranteedToExecute =
2106  SafetyInfo->isGuaranteedToExecute(*UI, DT, CurLoop);
2107  StoreIsGuanteedToExecute |= GuaranteedToExecute;
2108  if (GuaranteedToExecute) {
2109  DereferenceableInPH = true;
2110  if (StoreSafety == StoreSafetyUnknown)
2111  StoreSafety = StoreSafe;
2112  Alignment = std::max(Alignment, InstAlignment);
2113  }
2114 
2115  // If a store dominates all exit blocks, it is safe to sink.
2116  // As explained above, if an exit block was executed, a dominating
2117  // store must have been executed at least once, so we are not
2118  // introducing stores on paths that did not have them.
2119  // Note that this only looks at explicit exit blocks. If we ever
2120  // start sinking stores into unwind edges (see above), this will break.
2121  if (StoreSafety == StoreSafetyUnknown &&
2122  llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
2123  return DT->dominates(Store->getParent(), Exit);
2124  }))
2125  StoreSafety = StoreSafe;
2126 
2127  // If the store is not guaranteed to execute, we may still get
2128  // deref info through it.
2129  if (!DereferenceableInPH) {
2130  DereferenceableInPH = isDereferenceableAndAlignedPointer(
2131  Store->getPointerOperand(), Store->getValueOperand()->getType(),
2132  Store->getAlign(), MDL, Preheader->getTerminator(), AC, DT, TLI);
2133  }
2134  } else
2135  continue; // Not a load or store.
2136 
2137  if (!AccessTy)
2138  AccessTy = getLoadStoreType(UI);
2139  else if (AccessTy != getLoadStoreType(UI))
2140  return false;
2141 
2142  // Merge the AA tags.
2143  if (LoopUses.empty()) {
2144  // On the first load/store, just take its AA tags.
2145  AATags = UI->getAAMetadata();
2146  } else if (AATags) {
2147  AATags = AATags.merge(UI->getAAMetadata());
2148  }
2149 
2150  LoopUses.push_back(UI);
2151  }
2152  }
2153 
2154  // If we found both an unordered atomic instruction and a non-atomic memory
2155  // access, bail. We can't blindly promote non-atomic to atomic since we
2156  // might not be able to lower the result. We can't downgrade since that
2157  // would violate memory model. Also, align 0 is an error for atomics.
2158  if (SawUnorderedAtomic && SawNotAtomic)
2159  return false;
2160 
2161  // If we're inserting an atomic load in the preheader, we must be able to
2162  // lower it. We're only guaranteed to be able to lower naturally aligned
2163  // atomics.
2164  if (SawUnorderedAtomic && Alignment < MDL.getTypeStoreSize(AccessTy))
2165  return false;
2166 
2167  // If we couldn't prove we can hoist the load, bail.
2168  if (!DereferenceableInPH) {
2169  LLVM_DEBUG(dbgs() << "Not promoting: Not dereferenceable in preheader\n");
2170  return false;
2171  }
2172 
2173  // We know we can hoist the load, but don't have a guaranteed store.
2174  // Check whether the location is writable and thread-local. If it is, then we
2175  // can insert stores along paths which originally didn't have them without
2176  // violating the memory model.
2177  if (StoreSafety == StoreSafetyUnknown) {
2178  Value *Object = getUnderlyingObject(SomePtr);
2179  if (isWritableObject(Object) &&
2180  isThreadLocalObject(Object, CurLoop, DT, TTI))
2181  StoreSafety = StoreSafe;
2182  }
2183 
2184  // If we've still failed to prove we can sink the store, hoist the load
2185  // only, if possible.
2186  if (StoreSafety != StoreSafe && !FoundLoadToPromote)
2187  // If we cannot hoist the load either, give up.
2188  return false;
2189 
2190  // Lets do the promotion!
2191  if (StoreSafety == StoreSafe) {
2192  LLVM_DEBUG(dbgs() << "LICM: Promoting load/store of the value: " << *SomePtr
2193  << '\n');
2194  ++NumLoadStorePromoted;
2195  } else {
2196  LLVM_DEBUG(dbgs() << "LICM: Promoting load of the value: " << *SomePtr
2197  << '\n');
2198  ++NumLoadPromoted;
2199  }
2200 
2201  ORE->emit([&]() {
2202  return OptimizationRemark(DEBUG_TYPE, "PromoteLoopAccessesToScalar",
2203  LoopUses[0])
2204  << "Moving accesses to memory location out of the loop";
2205  });
2206 
2207  // Look at all the loop uses, and try to merge their locations.
2208  std::vector<const DILocation *> LoopUsesLocs;
2209  for (auto *U : LoopUses)
2210  LoopUsesLocs.push_back(U->getDebugLoc().get());
2211  auto DL = DebugLoc(DILocation::getMergedLocations(LoopUsesLocs));
2212 
2213  // We use the SSAUpdater interface to insert phi nodes as required.
2215  SSAUpdater SSA(&NewPHIs);
2216  LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
2217  InsertPts, MSSAInsertPts, PIC, MSSAU, *LI, DL,
2218  Alignment, SawUnorderedAtomic, AATags, *SafetyInfo,
2219  StoreSafety == StoreSafe);
2220 
2221  // Set up the preheader to have a definition of the value. It is the live-out
2222  // value from the preheader that uses in the loop will use.
2223  LoadInst *PreheaderLoad = nullptr;
2224  if (FoundLoadToPromote || !StoreIsGuanteedToExecute) {
2225  PreheaderLoad =
2226  new LoadInst(AccessTy, SomePtr, SomePtr->getName() + ".promoted",
2227  Preheader->getTerminator());
2228  if (SawUnorderedAtomic)
2229  PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
2230  PreheaderLoad->setAlignment(Alignment);
2231  PreheaderLoad->setDebugLoc(DebugLoc());
2232  if (AATags)
2233  PreheaderLoad->setAAMetadata(AATags);
2234 
2235  MemoryAccess *PreheaderLoadMemoryAccess = MSSAU.createMemoryAccessInBB(
2236  PreheaderLoad, nullptr, PreheaderLoad->getParent(), MemorySSA::End);
2237  MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
2238  MSSAU.insertUse(NewMemUse, /*RenameUses=*/true);
2239  SSA.AddAvailableValue(Preheader, PreheaderLoad);
2240  } else {
2241  SSA.AddAvailableValue(Preheader, PoisonValue::get(AccessTy));
2242  }
2243 
2244  if (VerifyMemorySSA)
2245  MSSAU.getMemorySSA()->verifyMemorySSA();
2246  // Rewrite all the loads in the loop and remember all the definitions from
2247  // stores in the loop.
2248  Promoter.run(LoopUses);
2249 
2250  if (VerifyMemorySSA)
2251  MSSAU.getMemorySSA()->verifyMemorySSA();
2252  // If the SSAUpdater didn't use the load in the preheader, just zap it now.
2253  if (PreheaderLoad && PreheaderLoad->use_empty())
2254  eraseInstruction(*PreheaderLoad, *SafetyInfo, MSSAU);
2255 
2256  return true;
2257 }
2258 
2259 static void foreachMemoryAccess(MemorySSA *MSSA, Loop *L,
2260  function_ref<void(Instruction *)> Fn) {
2261  for (const BasicBlock *BB : L->blocks())
2262  if (const auto *Accesses = MSSA->getBlockAccesses(BB))
2263  for (const auto &Access : *Accesses)
2264  if (const auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
2265  Fn(MUD->getMemoryInst());
2266 }
2267 
2270  AliasSetTracker AST(*AA);
2271 
2272  auto IsPotentiallyPromotable = [L](const Instruction *I) {
2273  if (const auto *SI = dyn_cast<StoreInst>(I))
2274  return L->isLoopInvariant(SI->getPointerOperand());
2275  if (const auto *LI = dyn_cast<LoadInst>(I))
2276  return L->isLoopInvariant(LI->getPointerOperand());
2277  return false;
2278  };
2279 
2280  // Populate AST with potentially promotable accesses.
2281  SmallPtrSet<Value *, 16> AttemptingPromotion;
2282  foreachMemoryAccess(MSSA, L, [&](Instruction *I) {
2283  if (IsPotentiallyPromotable(I)) {
2284  AttemptingPromotion.insert(I);
2285  AST.add(I);
2286  }
2287  });
2288 
2289  // We're only interested in must-alias sets that contain a mod.
2291  for (AliasSet &AS : AST)
2292  if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
2293  Sets.push_back(&AS);
2294 
2295  if (Sets.empty())
2296  return {}; // Nothing to promote...
2297 
2298  // Discard any sets for which there is an aliasing non-promotable access.
2299  BatchAAResults BatchAA(*AA);
2300  foreachMemoryAccess(MSSA, L, [&](Instruction *I) {
2301  if (AttemptingPromotion.contains(I))
2302  return;
2303 
2304  llvm::erase_if(Sets, [&](const AliasSet *AS) {
2305  return AS->aliasesUnknownInst(I, BatchAA);
2306  });
2307  });
2308 
2310  for (const AliasSet *Set : Sets) {
2311  SmallSetVector<Value *, 8> PointerMustAliases;
2312  for (const auto &ASI : *Set)
2313  PointerMustAliases.insert(ASI.getValue());
2314  Result.push_back(std::move(PointerMustAliases));
2315  }
2316 
2317  return Result;
2318 }
2319 
2321  Loop *CurLoop, Instruction &I,
2322  SinkAndHoistLICMFlags &Flags) {
2323  // For hoisting, use the walker to determine safety
2324  if (!Flags.getIsSink()) {
2326  // See declaration of SetLicmMssaOptCap for usage details.
2327  if (Flags.tooManyClobberingCalls())
2328  Source = MU->getDefiningAccess();
2329  else {
2331  Flags.incrementClobberingCalls();
2332  }
2333  return !MSSA->isLiveOnEntryDef(Source) &&
2334  CurLoop->contains(Source->getBlock());
2335  }
2336 
2337  // For sinking, we'd need to check all Defs below this use. The getClobbering
2338  // call will look on the backedge of the loop, but will check aliasing with
2339  // the instructions on the previous iteration.
2340  // For example:
2341  // for (i ... )
2342  // load a[i] ( Use (LoE)
2343  // store a[i] ( 1 = Def (2), with 2 = Phi for the loop.
2344  // i++;
2345  // The load sees no clobbering inside the loop, as the backedge alias check
2346  // does phi translation, and will check aliasing against store a[i-1].
2347  // However sinking the load outside the loop, below the store is incorrect.
2348 
2349  // For now, only sink if there are no Defs in the loop, and the existing ones
2350  // precede the use and are in the same block.
2351  // FIXME: Increase precision: Safe to sink if Use post dominates the Def;
2352  // needs PostDominatorTreeAnalysis.
2353  // FIXME: More precise: no Defs that alias this Use.
2354  if (Flags.tooManyMemoryAccesses())
2355  return true;
2356  for (auto *BB : CurLoop->getBlocks())
2357  if (pointerInvalidatedByBlock(*BB, *MSSA, *MU))
2358  return true;
2359  // When sinking, the source block may not be part of the loop so check it.
2360  if (!CurLoop->contains(&I))
2361  return pointerInvalidatedByBlock(*I.getParent(), *MSSA, *MU);
2362 
2363  return false;
2364 }
2365 
2367  if (const auto *Accesses = MSSA.getBlockDefs(&BB))
2368  for (const auto &MA : *Accesses)
2369  if (const auto *MD = dyn_cast<MemoryDef>(&MA))
2370  if (MU.getBlock() != MD->getBlock() || !MSSA.locallyDominates(MD, &MU))
2371  return true;
2372  return false;
2373 }
2374 
2375 /// Little predicate that returns true if the specified basic block is in
2376 /// a subloop of the current one, not the current one itself.
2377 ///
2378 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
2379  assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
2380  return LI->getLoopFor(BB) != CurLoop;
2381 }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:30
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::BatchAAResults
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
Definition: AliasAnalysis.h:609
AssumptionCache.h
llvm::LoopSafetyInfo::isGuaranteedToExecute
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...
llvm::OptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: DiagnosticInfo.h:734
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:60
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
hoist
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:1704
llvm::MemorySSA::verifyMemorySSA
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:1869
llvm::TargetTransformInfo::getInstructionCost
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
Definition: TargetTransformInfo.cpp:224
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:69
llvm::LoopStandardAnalysisResults::AC
AssumptionCache & AC
Definition: LoopAnalysisManager.h:53
llvm::initializeLegacyLICMPassPass
void initializeLegacyLICMPassPass(PassRegistry &)
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2784
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
Metadata.h
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
DebugInfoMetadata.h
llvm::LoadAndStorePromoter
Helper class for promoting a collection of loads and stores into SSA Form using the SSAUpdater.
Definition: SSAUpdater.h:136
Scalar.h
SetOperations.h
llvm::PassInfoMixin< LICMPass >
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::TypeSize::getFixedSize
ScalarTy getFixedSize() const
Definition: TypeSize.h:444
Loads.h
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::PredIteratorCache
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
Definition: PredIteratorCache.h:27
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:53
llvm::PriorityWorklist< T, SmallVector< T, N >, SmallDenseMap< T, ptrdiff_t > >::insert
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
Definition: PriorityWorklist.h:90
llvm::SetLicmMssaNoAccForPromotionCap
cl::opt< unsigned > SetLicmMssaNoAccForPromotionCap
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:699
Statistic.h
llvm::pred_size
unsigned pred_size(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:32
CaptureTracking.h
llvm::DataLayout::getTypeStoreSize
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type.
Definition: DataLayout.h:474
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:173
LazyBlockFrequencyInfo.h
llvm::BasicBlock::replaceSuccessorsPhiUsesWith
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:482
llvm::erase_if
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:1972
isLoadInvariantInLoop
static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT, Loop *CurLoop)
Definition: LICM.cpp:1038
llvm::isModSet
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::MemorySSA::dominates
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:2122
eraseInstruction
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
Definition: LICM.cpp:1471
ValueTracking.h
Local.h
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:142
llvm::AliasSetTracker
Definition: AliasSetTracker.h:305
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::getLoadStoreType
Type * getLoadStoreType(Value *I)
A helper function that returns the type of a load or store instruction.
Definition: Instructions.h:5405
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:652
llvm::LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage
static void getLazyBFIAnalysisUsage(AnalysisUsage &AU)
Helper for client passes to set up the analysis usage on behalf of this pass.
Definition: LazyBlockFrequencyInfo.cpp:62
ScalarEvolution.h
MaxNumUsesTraversed
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)"))
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:315
llvm::StoreInst::setAlignment
void setAlignment(Align Align)
Definition: Instructions.h:345
PIC
PassInstrumentationCallbacks PIC
Definition: PassBuilderBindings.cpp:55
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::hasDisableLICMTransformsHint
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Definition: LoopUtils.cpp:349
llvm::isModOrRefSet
bool isModOrRefSet(const ModRefInfo MRI)
Definition: ModRef.h:42
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LICM.cpp:94
llvm::TinyPtrVector::front
EltTy front() const
Definition: TinyPtrVector.h:230
ControlFlowHoisting
static cl::opt< bool > ControlFlowHoisting("licm-control-flow-hoisting", cl::Hidden, cl::init(false), cl::desc("Enable control flow (and PHI) hoisting in LICM"))
llvm::Value::hasOneUser
bool hasOneUser() const
Return true if there is exactly one user of this value.
Definition: Value.cpp:156
llvm::formLCSSARecursively
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:410
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
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:145
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::sinkRegion
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:535
llvm::SinkAndHoistLICMFlags::LicmMssaNoAccForPromotionCap
unsigned LicmMssaNoAccForPromotionCap
Definition: LoopUtils.h:135
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::MemoryUse
Represents read-only accesses to memory.
Definition: MemorySSA.h:312
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:54
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:104
llvm::canSinkOrHoistInst
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:1146
ConstantFolding.h
llvm::LinearPolySize::isScalable
bool isScalable() const
Returns whether the size is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:298
MustExecute.h
llvm::MemorySSAUpdater::createMemoryAccessInBB
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering defin...
Definition: MemorySSAUpdater.cpp:1429
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1456
cloneInstructionInExitBlock
static Instruction * cloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU)
Definition: LICM.cpp:1399
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:590
llvm::LazyBlockFrequencyInfoPass
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
Definition: LazyBlockFrequencyInfo.h:98
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
licm
licm
Definition: LICM.cpp:346
llvm::LoopBlocksRPO
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
llvm::isGuard
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
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MemoryEffects
Summary of how a function affects memory in the program.
Definition: ModRef.h:63
llvm::isIdentifiedFunctionLocal
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
Definition: AliasAnalysis.cpp:903
llvm::DominatorTree::dominates
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
PriorityWorklist.h
CommandLine.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::remove
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:157
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
llvm::MemorySSAUpdater::insertUse
void insertUse(MemoryUse *Use, bool RenameUses=false)
Definition: MemorySSAUpdater.cpp:238
llvm::all_of
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:1709
llvm::StoreInst::setOrdering
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this store instruction.
Definition: Instructions.h:356
llvm::isNoAliasCall
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
Definition: AliasAnalysis.cpp:879
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:984
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::begin
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::LICMOptions::AllowSpeculation
bool AllowSpeculation
Definition: LICM.h:51
Constants.h
collectPromotionCandidates
static SmallVector< SmallSetVector< Value *, 8 >, 0 > collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L)
Definition: LICM.cpp:2269
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
inSubLoop
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:2378
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::LoopSafetyInfo
Captures loop safety information.
Definition: MustExecute.h:60
llvm::MemorySSA::isLiveOnEntryDef
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:737
foreachMemoryAccess
static void foreachMemoryAccess(MemorySSA *MSSA, Loop *L, function_ref< void(Instruction *)> Fn)
Definition: LICM.cpp:2259
llvm::PredIteratorCache::size
size_t size(BasicBlock *BB) const
Definition: PredIteratorCache.h:65
llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags
SinkAndHoistLICMFlags(unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink, Loop *L=nullptr, MemorySSA *MSSA=nullptr)
Definition: LICM.cpp:362
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::SinkAndHoistLICMFlags
Flags controlling how much is checked when sinking or hoisting instructions.
Definition: LoopUtils.h:115
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::AliasSet
Definition: AliasSetTracker.h:49
llvm::LICMOptions::MssaOptCap
unsigned MssaOptCap
Definition: LICM.h:49
llvm::ReplaceInstWithInst
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
Definition: BasicBlockUtils.cpp:559
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:195
llvm::LoopSafetyInfo::getBlockColors
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
Definition: MustExecute.cpp:32
TargetLibraryInfo.h
AssumeBundleBuilder.h
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
llvm::BasicBlock::getFirstInsertionPt
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:246
false
Definition: StackSlotColoring.cpp:141
llvm::MemoryEffects::doesNotAccessMemory
bool doesNotAccessMemory() const
Whether this function accesses no memory.
Definition: ModRef.h:191
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1200
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:188
llvm::AAResults::getMemoryEffects
MemoryEffects getMemoryEffects(const CallBase *Call)
Return the behavior of the given call site.
Definition: AliasAnalysis.cpp:388
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:145
llvm::salvageDebugInfo
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:1361
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::MemorySSA::getBlockAccesses
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
Definition: MemorySSA.h:757
LoopUtils.h
llvm::getUnderlyingObject
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Definition: ValueTracking.cpp:4499
llvm::LPPassManager
Definition: LoopPass.h:76
llvm::Instruction::getAAMetadata
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
Definition: Metadata.cpp:1500
llvm::SplitBlockPredecessors
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...
Definition: BasicBlockUtils.cpp:1255
llvm::BasicBlock::getModule
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:147
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
PatternMatch.h
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:209
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::sinkRegionForLoopNest
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:602
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2790
llvm::MemoryAccess::getBlock
BasicBlock * getBlock() const
Definition: MemorySSA.h:164
LoopIterator.h
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:271
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::MemorySSA::locallyDominates
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:2091
llvm::OperandBundleUse::getTagID
uint32_t getTagID() const
Return the tag of this operand bundle as an integer.
Definition: InstrTypes.h:1097
CFG.h
LoopInfo.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3214
llvm::OutputFileType::Object
@ Object
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::SmallPtrSetImplBase::empty
bool empty() const
Definition: SmallPtrSet.h:92
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
isTriviallyReplaceablePHI
static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I)
Returns true if a PHINode is a trivially replaceable with an Instruction.
Definition: LICM.cpp:1317
llvm::MemorySSAWalker::getClobberingMemoryAccess
MemoryAccess * getClobberingMemoryAccess(const Instruction *I)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition: MemorySSA.h:1044
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:138
llvm::cl::opt< bool >
SSA
Memory SSA
Definition: MemorySSA.cpp:73
llvm::LoadInst::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:266
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::AliasSetTracker::add
void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
Definition: AliasSetTracker.cpp:366
llvm::Value::getNameOrAsOperand
std::string getNameOrAsOperand() const
Definition: Value.cpp:443
LICM
loop versioning Loop Versioning For LICM
Definition: LoopVersioningLICM.cpp:627
llvm::LoadAndStorePromoter::shouldDelete
virtual bool shouldDelete(Instruction *I) const
Return false if a sub-class wants to keep one of the loads/stores after the SSA construction.
Definition: SSAUpdater.h:175
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:475
uint64_t
llvm::LoopPass
Definition: LoopPass.h:28
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2642
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:242
llvm::LoadInst::setOrdering
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this load instruction.
Definition: Instructions.h:230
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:79
llvm::LoopBase::getUniqueExitBlocks
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:142
llvm::Instruction::user_back
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:88
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2833
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::SmallPriorityWorklist
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
Definition: PriorityWorklist.h:255
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2848
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::DenseMap
Definition: DenseMap.h:714
llvm::ICFLoopSafetyInfo::anyBlockMayThrow
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
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
PredIteratorCache.h
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::AAResults::getModRefInfo
ModRefInfo getModRefInfo(const Instruction *I, const Optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Definition: AliasAnalysis.h:488
llvm::LoadInst::setAlignment
void setAlignment(Align Align)
Definition: Instructions.h:220
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::make_early_inc_range
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:716
llvm::PHINode::getBasicBlockIndex
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: Instructions.h:2876
llvm::MemoryEffects::onlyReadsMemory
bool onlyReadsMemory() const
Whether this function only (at most) reads memory.
Definition: ModRef.h:194
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
llvm::ScalarEvolution::forgetValue
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
Definition: ScalarEvolution.cpp:8432
llvm::ICFLoopSafetyInfo::doesNotWriteMemoryBefore
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...
Definition: MustExecute.cpp:284
llvm::PriorityWorklist< T, SmallVector< T, N >, SmallDenseMap< T, ptrdiff_t > >::empty
bool empty() const
Determine if the PriorityWorklist is empty or not.
Definition: PriorityWorklist.h:67
splitPredecessorsOfLoopExit
static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT, LoopInfo *LI, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU)
Definition: LICM.cpp:1527
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
llvm::LoopBase::hasDedicatedExits
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:112
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Instruction::mergeDIAssignID
void mergeDIAssignID(ArrayRef< const Instruction * > SourceInstructions)
Merge the DIAssignID metadata from this instruction and those attached to instructions in SourceInstr...
Definition: DebugInfo.cpp:843
llvm::LNICMPass::run
PreservedAnalyses run(LoopNest &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LICM.cpp:298
SingleThread
static cl::opt< bool > SingleThread("licm-force-thread-model-single", cl::Hidden, cl::init(false), cl::desc("Force thread model single in LICM pass"))
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
llvm::LNICMPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: LICM.cpp:328
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
isFreeInLoop
static bool isFreeInLoop(const Instruction &I, const Loop *CurLoop, const TargetTransformInfo *TTI)
Return true if the instruction is free in the loop.
Definition: LICM.cpp:1326
LoopNestAnalysis.h
llvm::salvageKnowledge
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Definition: AssumeBundleBuilder.cpp:293
llvm::hoistRegion
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:855
pointerInvalidatedByBlock
static bool pointerInvalidatedByBlock(BasicBlock &BB, MemorySSA &MSSA, MemoryUse &MU)
Definition: LICM.cpp:2366
llvm::LoopNest::getOutermostLoop
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
Definition: LoopNestAnalysis.h:80
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:934
llvm::collectChildrenInLoop
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:451
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::SinkAndHoistLICMFlags::NoOfMemAccTooLarge
bool NoOfMemAccTooLarge
Definition: LoopUtils.h:132
llvm::ScalarEvolution::forgetLoopDispositions
void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
Definition: ScalarEvolution.cpp:8459
llvm::promoteLoopAccessesToScalars
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock * > &, SmallVectorImpl< Instruction * > &, SmallVectorImpl< MemoryAccess * > &, PredIteratorCache &, LoopInfo *, DominatorTree *, AssumptionCache *AC, const TargetLibraryInfo *, TargetTransformInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *, bool AllowSpeculation)
Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before ...
Definition: LICM.cpp:1960
TargetOptions.h
llvm::MemorySSAUpdater::createMemoryAccessAfter
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
Definition: MemorySSAUpdater.cpp:1447
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:99
isDereferenceableAndAlignedPointer
static bool isDereferenceableAndAlignedPointer(const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, const Instruction *CtxI, AssumptionCache *AC, const DominatorTree *DT, const TargetLibraryInfo *TLI, SmallPtrSetImpl< const Value * > &Visited, unsigned MaxDepth)
Test if V is always a pointer to allocated and suitably aligned memory for a simple load or store.
Definition: Loads.cpp:39
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::isInstructionTriviallyDead
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:396
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::AAMDNodes::merge
AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
Definition: TypeBasedAliasAnalysis.cpp:524
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::MemorySSAUpdater::insertDef
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
Definition: MemorySSAUpdater.cpp:307
llvm::any_of
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:1716
DataLayout.h
llvm::TinyPtrVector::size
unsigned size() const
Definition: TinyPtrVector.h:172
llvm::MemorySSA::getSkipSelfWalker
MemorySSAWalker * getSkipSelfWalker()
Definition: MemorySSA.cpp:1575
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
LoopPass.h
Motion
Loop Invariant Code Motion
Definition: LICM.cpp:346
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::MemorySSA::getBlockDefs
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
Definition: MemorySSA.h:765
llvm::isNotVisibleOnUnwind
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...
Definition: AliasAnalysis.cpp:929
llvm::appendLoopsToWorklist
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1525
llvm::LoopBase::isOutermost
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
Definition: LoopInfo.h:185
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
A
* A
Definition: README_ALTIVEC.txt:89
llvm::ms_demangle::IntrinsicFunctionKind::New
@ New
llvm::OperandBundleUse
A lightweight accessor for an operand bundle meant to be passed around by value.
Definition: InstrTypes.h:1069
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:55
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::ICFLoopSafetyInfo::insertInstructionTo
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
llvm::DominatorTreeBase::properlyDominates
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Definition: GenericDomTree.h:392
llvm::LoopNest::getParent
Function * getParent() const
Return the function to which the loop-nest belongs.
Definition: LoopNestAnalysis.h:176
SSAUpdater.h
llvm::ConstantInt::getSExtValue
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:148
llvm::Loop::hasLoopInvariantOperands
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:66
llvm::MemoryAccess
Definition: MemorySSA.h:142
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::DominatorTreeBase::addNewBlock
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
Definition: GenericDomTree.h:619
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::find_if
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:1736
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:318
llvm::MemorySSA::ensureOptimizedUses
void ensureOptimizedUses()
By default, uses are not optimized during MemorySSA construction.
Definition: MemorySSA.cpp:2149
llvm::ICFLoopSafetyInfo::removeInstruction
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
Definition: MustExecute.cpp:99
getPointerOperandIndex
static unsigned getPointerOperandIndex(Instruction *I)
Definition: HWAddressSanitizer.cpp:777
std
Definition: BitVector.h:851
llvm::Value::user_iterator
user_iterator_impl< User > user_iterator
Definition: Value.h:390
llvm::MemoryUseOrDef::getDefiningAccess
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:262
llvm::LoopStandardAnalysisResults::TTI
TargetTransformInfo & TTI
Definition: LoopAnalysisManager.h:58
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::ICFLoopSafetyInfo
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
Definition: MustExecute.h:132
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2740
llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
Definition: MemorySSAUpdater.cpp:1268
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::ConstantFP::get
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:926
llvm::TypeSize
Definition: TypeSize.h:435
llvm::Instruction::setAAMetadata
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1514
llvm::LICMPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: LICM.cpp:288
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
llvm::LICMOptions::MssaNoAccForPromotionCap
unsigned MssaNoAccForPromotionCap
Definition: LICM.h:50
sinkThroughTriviallyReplaceablePHI
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:1492
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:664
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
llvm::LoopSafetyInfo::copyColors
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
Definition: MustExecute.cpp:36
Unordered
QP Compare Ordered Unordered
Definition: README_P9.txt:299
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:56
llvm::LoopStandardAnalysisResults::AA
AAResults & AA
Definition: LoopAnalysisManager.h:52
llvm::PriorityWorklist< T, SmallVector< T, N >, SmallDenseMap< T, ptrdiff_t > >::pop_back_val
T pop_back_val()
Definition: PriorityWorklist.h:153
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
GuardUtils.h
DisablePromotion
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.
llvm::MemoryEffects::onlyAccessesArgPointees
bool onlyAccessesArgPointees() const
Whether this function only (at most) accesses argument memory.
Definition: ModRef.h:200
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:373
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:689
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::createLICMPass
Pass * createLICMPass()
Definition: LICM.cpp:349
MemorySSA.h
llvm::AAResults::getModRefInfoMask
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, bool IgnoreLocals=false)
Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.
Definition: AliasAnalysis.cpp:150
Instructions.h
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
llvm::LICMPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LICM.cpp:263
llvm::ConstantInt::isNegative
bool isNegative() const
Definition: Constants.h:189
llvm::BasicBlock::moveBefore
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
Definition: BasicBlock.cpp:136
moveInstructionBefore
static void moveInstructionBefore(Instruction &I, Instruction &Dest, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution *SE)
Definition: LICM.cpp:1478
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:258
llvm::LoadAndStorePromoter::doExtraRewritesBeforeFinalDeletion
virtual void doExtraRewritesBeforeFinalDeletion()
This hook is invoked after all the stores are found and inserted as available values.
Definition: SSAUpdater.h:161
Dominators.h
llvm::DIAssignID
Assignment ID.
Definition: DebugInfoMetadata.h:303
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::ICFLoopSafetyInfo::computeLoopSafetyInfo
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
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2814
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false, false) INITIALIZE_PASS_END(LegacyLICMPass
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
Users
iv Induction Variable Users
Definition: IVUsers.cpp:48
TargetTransformInfo.h
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
llvm::PHINode
Definition: Instructions.h:2698
llvm::BasicBlock::getTerminator
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:119
LICM.h
llvm::set_intersect
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
llvm::SmallVectorImpl< BasicBlock * >
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:462
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
llvm::PredIteratorCache::get
ArrayRef< BasicBlock * > get(BasicBlock *BB)
Definition: PredIteratorCache.h:66
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:399
isNotUsedOrFreeInLoop
static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, TargetTransformInfo *TTI, bool &FreeInLoop, bool LoopNestMode)
Return true if the only users of this instruction are outside of the loop.
Definition: LICM.cpp:1357
DerivedTypes.h
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
pointerInvalidatedByLoop
static bool pointerInvalidatedByLoop(MemorySSA *MSSA, MemoryUse *MU, Loop *CurLoop, Instruction &I, SinkAndHoistLICMFlags &Flags)
Definition: LICM.cpp:2320
AliasSetTracker.h
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1473
llvm::omp::RTLDependInfoFields::Flags
@ Flags
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::ICFLoopSafetyInfo::isGuaranteedToExecute
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...
Definition: MustExecute.cpp:277
isSafeToExecuteUnconditionally
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:1749
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
LLVMContext.h
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::LoadAndStorePromoter::instructionDeleted
virtual void instructionDeleted(Instruction *I) const
Called before each instruction is deleted.
Definition: SSAUpdater.h:168
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:413
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3133
llvm::ConstantFoldInstruction
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
Definition: ConstantFolding.cpp:1159
raw_ostream.h
llvm::LoopBlocksRPO::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
llvm::TinyPtrVector
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
llvm::SSAUpdater
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:38
llvm::TargetTransformInfo::isSingleThreaded
bool isSingleThreaded() const
Definition: TargetTransformInfo.cpp:276
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:667
sink
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:1599
BasicBlockUtils.h
llvm::SetLicmMssaOptCap
cl::opt< unsigned > SetLicmMssaOptCap
llvm::LazyBranchProbabilityInfoPass
This is an alternative analysis pass to BranchProbabilityInfoWrapperPass.
Definition: LazyBranchProbabilityInfo.h:50
llvm::LoopStandardAnalysisResults::TLI
TargetLibraryInfo & TLI
Definition: LoopAnalysisManager.h:57
InitializePasses.h
llvm::PointerMayBeCapturedBefore
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...
Definition: CaptureTracking.cpp:269
llvm::LoopNest
This class represents a loop nest and can be used to query its properties.
Definition: LoopNestAnalysis.h:28
llvm::isSafeToSpeculativelyExecute
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 ...
Definition: ValueTracking.cpp:4731
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3212
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3226
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
llvm::MemorySSAUpdater::removeMemoryAccess
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Definition: MemorySSAUpdater.cpp:1305
llvm::LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA
bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, const BasicBlock *ExitBB) const
Definition: LoopInfo.cpp:933
canSplitPredecessors
static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo)
Definition: LICM.cpp:1510
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
llvm::SmallPtrSetImpl::insert
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:365
llvm::LoadAndStorePromoter::isInstInList
virtual bool isInstInList(Instruction *I, const SmallVectorImpl< Instruction * > &Insts) const
Return true if the specified instruction is in the Inst list.
Definition: SSAUpdater.cpp:478