LLVM  6.0.0svn
LICM.cpp
Go to the documentation of this file.
1 //===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass performs loop invariant code motion, attempting to remove as much
11 // code from the body of a loop as possible. It does this by either hoisting
12 // code into the preheader block, or by sinking code to the exit blocks if it is
13 // safe. This pass also promotes must-aliased memory locations in the loop to
14 // live in registers, thus hoisting and sinking "invariant" loads and stores.
15 //
16 // This pass uses alias analysis for two purposes:
17 //
18 // 1. Moving loop invariant loads and calls out of loops. If we can determine
19 // that a load or call inside of a loop never aliases anything stored to,
20 // we can hoist it or sink it like any other instruction.
21 // 2. Scalar Promotion of Memory - If there is a store instruction inside of
22 // the loop, we try to move the store to happen AFTER the loop instead of
23 // inside of the loop. This can only happen if a few conditions are true:
24 // A. The pointer stored through is loop invariant
25 // B. There are no stores or loads in the loop which _may_ alias the
26 // pointer. There are no calls in the loop which mod/ref the pointer.
27 // If these conditions are true, we can promote the loads and stores in the
28 // loop of the pointer to use a temporary alloca'd variable. We then use
29 // the SSAUpdater to construct the appropriate SSA form for the value.
30 //
31 //===----------------------------------------------------------------------===//
32 
34 #include "llvm/ADT/Statistic.h"
41 #include "llvm/Analysis/Loads.h"
42 #include "llvm/Analysis/LoopInfo.h"
43 #include "llvm/Analysis/LoopPass.h"
50 #include "llvm/IR/CFG.h"
51 #include "llvm/IR/Constants.h"
52 #include "llvm/IR/DataLayout.h"
53 #include "llvm/IR/DerivedTypes.h"
54 #include "llvm/IR/Dominators.h"
55 #include "llvm/IR/Instructions.h"
56 #include "llvm/IR/IntrinsicInst.h"
57 #include "llvm/IR/LLVMContext.h"
58 #include "llvm/IR/Metadata.h"
61 #include "llvm/Support/Debug.h"
63 #include "llvm/Transforms/Scalar.h"
68 #include <algorithm>
69 #include <utility>
70 using namespace llvm;
71 
72 #define DEBUG_TYPE "licm"
73 
74 STATISTIC(NumSunk, "Number of instructions sunk out of loop");
75 STATISTIC(NumHoisted, "Number of instructions hoisted out of loop");
76 STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
77 STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
78 STATISTIC(NumPromoted, "Number of memory locations promoted to registers");
79 
80 /// Memory promotion is enabled by default.
81 static cl::opt<bool>
82  DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
83  cl::desc("Disable memory promotion in LICM pass"));
84 
86  "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
87  cl::desc("Max num uses visited for identifying load "
88  "invariance in loop using invariant start (default = 8)"));
89 
90 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
91 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
92  const LoopSafetyInfo *SafetyInfo);
93 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
94  const LoopSafetyInfo *SafetyInfo,
96 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
97  const Loop *CurLoop, AliasSetTracker *CurAST,
98  const LoopSafetyInfo *SafetyInfo,
101  const DominatorTree *DT,
102  const Loop *CurLoop,
103  const LoopSafetyInfo *SafetyInfo,
105  const Instruction *CtxI = nullptr);
106 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
107  const AAMDNodes &AAInfo,
108  AliasSetTracker *CurAST);
109 static Instruction *
111  const LoopInfo *LI,
112  const LoopSafetyInfo *SafetyInfo);
113 
114 namespace {
115 struct LoopInvariantCodeMotion {
116  bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
118  OptimizationRemarkEmitter *ORE, bool DeleteAST);
119 
120  DenseMap<Loop *, AliasSetTracker *> &getLoopToAliasSetMap() {
121  return LoopToAliasSetMap;
122  }
123 
124 private:
125  DenseMap<Loop *, AliasSetTracker *> LoopToAliasSetMap;
126 
127  AliasSetTracker *collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
128  AliasAnalysis *AA);
129 };
130 
131 struct LegacyLICMPass : public LoopPass {
132  static char ID; // Pass identification, replacement for typeid
133  LegacyLICMPass() : LoopPass(ID) {
135  }
136 
137  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
138  if (skipLoop(L)) {
139  // If we have run LICM on a previous loop but now we are skipping
140  // (because we've hit the opt-bisect limit), we need to clear the
141  // loop alias information.
142  for (auto &LTAS : LICM.getLoopToAliasSetMap())
143  delete LTAS.second;
144  LICM.getLoopToAliasSetMap().clear();
145  return false;
146  }
147 
148  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
149  // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
150  // pass. Function analyses need to be preserved across loop transformations
151  // but ORE cannot be preserved (see comment before the pass definition).
153  return LICM.runOnLoop(L,
154  &getAnalysis<AAResultsWrapperPass>().getAAResults(),
155  &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
156  &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
157  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
158  SE ? &SE->getSE() : nullptr, &ORE, false);
159  }
160 
161  /// This transformation requires natural loop information & requires that
162  /// loop preheaders be inserted into the CFG...
163  ///
164  void getAnalysisUsage(AnalysisUsage &AU) const override {
165  AU.setPreservesCFG();
168  }
169 
171 
172  bool doFinalization() override {
173  assert(LICM.getLoopToAliasSetMap().empty() &&
174  "Didn't free loop alias sets");
175  return false;
176  }
177 
178 private:
179  LoopInvariantCodeMotion LICM;
180 
181  /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info.
182  void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
183  Loop *L) override;
184 
185  /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
186  /// set.
187  void deleteAnalysisValue(Value *V, Loop *L) override;
188 
189  /// Simple Analysis hook. Delete loop L from alias set map.
190  void deleteAnalysisLoop(Loop *L) override;
191 };
192 } // namespace
193 
196  const auto &FAM =
197  AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
198  Function *F = L.getHeader()->getParent();
199 
200  auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
201  // FIXME: This should probably be optional rather than required.
202  if (!ORE)
203  report_fatal_error("LICM: OptimizationRemarkEmitterAnalysis not "
204  "cached at a higher level");
205 
206  LoopInvariantCodeMotion LICM;
207  if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.SE, ORE, true))
208  return PreservedAnalyses::all();
209 
210  auto PA = getLoopPassPreservedAnalyses();
211  PA.preserveSet<CFGAnalyses>();
212  return PA;
213 }
214 
215 char LegacyLICMPass::ID = 0;
216 INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
217  false, false)
220 INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
221  false)
222 
223 Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
224 
225 /// Hoist expressions out of the specified loop. Note, alias info for inner
226 /// loop is not preserved so it is not a good idea to run LICM multiple
227 /// times on one loop.
228 /// We should delete AST for inner loops in the new pass manager to avoid
229 /// memory leak.
230 ///
231 bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AliasAnalysis *AA,
232  LoopInfo *LI, DominatorTree *DT,
233  TargetLibraryInfo *TLI,
234  ScalarEvolution *SE,
236  bool DeleteAST) {
237  bool Changed = false;
238 
239  assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
240 
241  AliasSetTracker *CurAST = collectAliasInfoForLoop(L, LI, AA);
242 
243  // Get the preheader block to move instructions into...
244  BasicBlock *Preheader = L->getLoopPreheader();
245 
246  // Compute loop safety information.
247  LoopSafetyInfo SafetyInfo;
248  computeLoopSafetyInfo(&SafetyInfo, L);
249 
250  // We want to visit all of the instructions in this loop... that are not parts
251  // of our subloops (they have already had their invariants hoisted out of
252  // their loop, into this loop, so there is no need to process the BODIES of
253  // the subloops).
254  //
255  // Traverse the body of the loop in depth first order on the dominator tree so
256  // that we are guaranteed to see definitions before we see uses. This allows
257  // us to sink instructions in one pass, without iteration. After sinking
258  // instructions, we perform another pass to hoist them out of the loop.
259  //
260  if (L->hasDedicatedExits())
261  Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
262  CurAST, &SafetyInfo, ORE);
263  if (Preheader)
264  Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
265  CurAST, &SafetyInfo, ORE);
266 
267  // Now that all loop invariants have been removed from the loop, promote any
268  // memory references to scalars that we can.
269  // Don't sink stores from loops without dedicated block exits. Exits
270  // containing indirect branches are not transformed by loop simplify,
271  // make sure we catch that. An additional load may be generated in the
272  // preheader for SSA updater, so also avoid sinking when no preheader
273  // is available.
274  if (!DisablePromotion && Preheader && L->hasDedicatedExits()) {
275  // Figure out the loop exits and their insertion points
276  SmallVector<BasicBlock *, 8> ExitBlocks;
277  L->getUniqueExitBlocks(ExitBlocks);
278 
279  // We can't insert into a catchswitch.
280  bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
281  return isa<CatchSwitchInst>(Exit->getTerminator());
282  });
283 
284  if (!HasCatchSwitch) {
286  InsertPts.reserve(ExitBlocks.size());
287  for (BasicBlock *ExitBlock : ExitBlocks)
288  InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
289 
290  PredIteratorCache PIC;
291 
292  bool Promoted = false;
293 
294  // Loop over all of the alias sets in the tracker object.
295  for (AliasSet &AS : *CurAST) {
296  // We can promote this alias set if it has a store, if it is a "Must"
297  // alias set, if the pointer is loop invariant, and if we are not
298  // eliminating any volatile loads or stores.
299  if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
300  AS.isVolatile() || !L->isLoopInvariant(AS.begin()->getValue()))
301  continue;
302 
303  assert(
304  !AS.empty() &&
305  "Must alias set should have at least one pointer element in it!");
306 
307  SmallSetVector<Value *, 8> PointerMustAliases;
308  for (const auto &ASI : AS)
309  PointerMustAliases.insert(ASI.getValue());
310 
311  Promoted |= promoteLoopAccessesToScalars(PointerMustAliases, ExitBlocks,
312  InsertPts, PIC, LI, DT, TLI, L,
313  CurAST, &SafetyInfo, ORE);
314  }
315 
316  // Once we have promoted values across the loop body we have to
317  // recursively reform LCSSA as any nested loop may now have values defined
318  // within the loop used in the outer loop.
319  // FIXME: This is really heavy handed. It would be a bit better to use an
320  // SSAUpdater strategy during promotion that was LCSSA aware and reformed
321  // it as it went.
322  if (Promoted)
323  formLCSSARecursively(*L, *DT, LI, SE);
324 
325  Changed |= Promoted;
326  }
327  }
328 
329  // Check that neither this loop nor its parent have had LCSSA broken. LICM is
330  // specifically moving instructions across the loop boundary and so it is
331  // especially in need of sanity checking here.
332  assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
333  assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
334  "Parent loop not left in LCSSA form after LICM!");
335 
336  // If this loop is nested inside of another one, save the alias information
337  // for when we process the outer loop.
338  if (L->getParentLoop() && !DeleteAST)
339  LoopToAliasSetMap[L] = CurAST;
340  else
341  delete CurAST;
342 
343  if (Changed && SE)
344  SE->forgetLoopDispositions(L);
345  return Changed;
346 }
347 
348 /// Walk the specified region of the CFG (defined by all blocks dominated by
349 /// the specified block, and that are in the current loop) in reverse depth
350 /// first order w.r.t the DominatorTree. This allows us to visit uses before
351 /// definitions, allowing us to sink a loop body in one pass without iteration.
352 ///
354  DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
355  AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
357 
358  // Verify inputs.
359  assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
360  CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
361  "Unexpected input to sinkRegion");
362 
363  // We want to visit children before parents. We will enque all the parents
364  // before their children in the worklist and process the worklist in reverse
365  // order.
367 
368  bool Changed = false;
369  for (DomTreeNode *DTN : reverse(Worklist)) {
370  BasicBlock *BB = DTN->getBlock();
371  // Only need to process the contents of this block if it is not part of a
372  // subloop (which would already have been processed).
373  if (inSubLoop(BB, CurLoop, LI))
374  continue;
375 
376  for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
377  Instruction &I = *--II;
378 
379  // If the instruction is dead, we would try to sink it because it isn't
380  // used in the loop, instead, just delete it.
381  if (isInstructionTriviallyDead(&I, TLI)) {
382  DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
383  ++II;
384  CurAST->deleteValue(&I);
385  I.eraseFromParent();
386  Changed = true;
387  continue;
388  }
389 
390  // Check to see if we can sink this instruction to the exit blocks
391  // of the loop. We can do this if the all users of the instruction are
392  // outside of the loop. In this case, it doesn't even matter if the
393  // operands of the instruction are loop invariant.
394  //
395  if (isNotUsedInLoop(I, CurLoop, SafetyInfo) &&
396  canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE)) {
397  ++II;
398  Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo, ORE);
399  }
400  }
401  }
402  return Changed;
403 }
404 
405 /// Walk the specified region of the CFG (defined by all blocks dominated by
406 /// the specified block, and that are in the current loop) in depth first
407 /// order w.r.t the DominatorTree. This allows us to visit definitions before
408 /// uses, allowing us to hoist a loop body in one pass without iteration.
409 ///
411  DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
412  AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
414  // Verify inputs.
415  assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
416  CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
417  "Unexpected input to hoistRegion");
418 
419  // We want to visit parents before children. We will enque all the parents
420  // before their children in the worklist and process the worklist in order.
422 
423  bool Changed = false;
424  for (DomTreeNode *DTN : Worklist) {
425  BasicBlock *BB = DTN->getBlock();
426  // Only need to process the contents of this block if it is not part of a
427  // subloop (which would already have been processed).
428  if (!inSubLoop(BB, CurLoop, LI))
429  for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
430  Instruction &I = *II++;
431  // Try constant folding this instruction. If all the operands are
432  // constants, it is technically hoistable, but it would be better to
433  // just fold it.
435  &I, I.getModule()->getDataLayout(), TLI)) {
436  DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n');
437  CurAST->copyValue(&I, C);
439  if (isInstructionTriviallyDead(&I, TLI)) {
440  CurAST->deleteValue(&I);
441  I.eraseFromParent();
442  }
443  Changed = true;
444  continue;
445  }
446 
447  // Attempt to remove floating point division out of the loop by
448  // converting it to a reciprocal multiplication.
449  if (I.getOpcode() == Instruction::FDiv &&
450  CurLoop->isLoopInvariant(I.getOperand(1)) &&
451  I.hasAllowReciprocal()) {
452  auto Divisor = I.getOperand(1);
453  auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
454  auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
455  ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
456  ReciprocalDivisor->insertBefore(&I);
457 
458  auto Product =
459  BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
460  Product->setFastMathFlags(I.getFastMathFlags());
461  Product->insertAfter(&I);
462  I.replaceAllUsesWith(Product);
463  I.eraseFromParent();
464 
465  hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
466  Changed = true;
467  continue;
468  }
469 
470  // Try hoisting the instruction out to the preheader. We can only do
471  // this if all of the operands of the instruction are loop invariant and
472  // if it is safe to hoist the instruction.
473  //
474  if (CurLoop->hasLoopInvariantOperands(&I) &&
475  canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE) &&
477  I, DT, CurLoop, SafetyInfo, ORE,
478  CurLoop->getLoopPreheader()->getTerminator()))
479  Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
480  }
481  }
482 
483  return Changed;
484 }
485 
486 /// Computes loop safety information, checks loop body & header
487 /// for the possibility of may throw exception.
488 ///
489 void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
490  assert(CurLoop != nullptr && "CurLoop cant be null");
491  BasicBlock *Header = CurLoop->getHeader();
492  // Setting default safety values.
493  SafetyInfo->MayThrow = false;
494  SafetyInfo->HeaderMayThrow = false;
495  // Iterate over header and compute safety info.
496  for (BasicBlock::iterator I = Header->begin(), E = Header->end();
497  (I != E) && !SafetyInfo->HeaderMayThrow; ++I)
498  SafetyInfo->HeaderMayThrow |=
500 
501  SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
502  // Iterate over loop instructions and compute safety info.
503  // Skip header as it has been computed and stored in HeaderMayThrow.
504  // The first block in loopinfo.Blocks is guaranteed to be the header.
505  assert(Header == *CurLoop->getBlocks().begin() &&
506  "First block must be header");
507  for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
508  BBE = CurLoop->block_end();
509  (BB != BBE) && !SafetyInfo->MayThrow; ++BB)
510  for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
511  (I != E) && !SafetyInfo->MayThrow; ++I)
513 
514  // Compute funclet colors if we might sink/hoist in a function with a funclet
515  // personality routine.
516  Function *Fn = CurLoop->getHeader()->getParent();
517  if (Fn->hasPersonalityFn())
518  if (Constant *PersonalityFn = Fn->getPersonalityFn())
519  if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
520  SafetyInfo->BlockColors = colorEHFunclets(*Fn);
521 }
522 
523 // Return true if LI is invariant within scope of the loop. LI is invariant if
524 // CurLoop is dominated by an invariant.start representing the same memory
525 // location and size as the memory location LI loads from, and also the
526 // invariant.start has no uses.
528  Loop *CurLoop) {
529  Value *Addr = LI->getOperand(0);
530  const DataLayout &DL = LI->getModule()->getDataLayout();
531  const uint32_t LocSizeInBits = DL.getTypeSizeInBits(
532  cast<PointerType>(Addr->getType())->getElementType());
533 
534  // if the type is i8 addrspace(x)*, we know this is the type of
535  // llvm.invariant.start operand
536  auto *PtrInt8Ty = PointerType::get(Type::getInt8Ty(LI->getContext()),
537  LI->getPointerAddressSpace());
538  unsigned BitcastsVisited = 0;
539  // Look through bitcasts until we reach the i8* type (this is invariant.start
540  // operand type).
541  while (Addr->getType() != PtrInt8Ty) {
542  auto *BC = dyn_cast<BitCastInst>(Addr);
543  // Avoid traversing high number of bitcast uses.
544  if (++BitcastsVisited > MaxNumUsesTraversed || !BC)
545  return false;
546  Addr = BC->getOperand(0);
547  }
548 
549  unsigned UsesVisited = 0;
550  // Traverse all uses of the load operand value, to see if invariant.start is
551  // one of the uses, and whether it dominates the load instruction.
552  for (auto *U : Addr->users()) {
553  // Avoid traversing for Load operand with high number of users.
554  if (++UsesVisited > MaxNumUsesTraversed)
555  return false;
557  // If there are escaping uses of invariant.start instruction, the load maybe
558  // non-invariant.
559  if (!II || II->getIntrinsicID() != Intrinsic::invariant_start ||
560  !II->use_empty())
561  continue;
562  unsigned InvariantSizeInBits =
563  cast<ConstantInt>(II->getArgOperand(0))->getSExtValue() * 8;
564  // Confirm the invariant.start location size contains the load operand size
565  // in bits. Also, the invariant.start should dominate the load, and we
566  // should not hoist the load out of a loop that contains this dominating
567  // invariant.start.
568  if (LocSizeInBits <= InvariantSizeInBits &&
569  DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
570  return true;
571  }
572 
573  return false;
574 }
575 
577  Loop *CurLoop, AliasSetTracker *CurAST,
578  LoopSafetyInfo *SafetyInfo,
580  // SafetyInfo is nullptr if we are checking for sinking from preheader to
581  // loop body.
582  const bool SinkingToLoopBody = !SafetyInfo;
583  // Loads have extra constraints we have to verify before we can hoist them.
584  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
585  if (!LI->isUnordered())
586  return false; // Don't sink/hoist volatile or ordered atomic loads!
587 
588  // Loads from constant memory are always safe to move, even if they end up
589  // in the same alias set as something that ends up being modified.
590  if (AA->pointsToConstantMemory(LI->getOperand(0)))
591  return true;
592  if (LI->getMetadata(LLVMContext::MD_invariant_load))
593  return true;
594 
595  if (LI->isAtomic() && SinkingToLoopBody)
596  return false; // Don't sink unordered atomic loads to loop body.
597 
598  // This checks for an invariant.start dominating the load.
599  if (isLoadInvariantInLoop(LI, DT, CurLoop))
600  return true;
601 
602  // Don't hoist loads which have may-aliased stores in loop.
603  uint64_t Size = 0;
604  if (LI->getType()->isSized())
605  Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType());
606 
607  AAMDNodes AAInfo;
608  LI->getAAMetadata(AAInfo);
609 
610  bool Invalidated =
611  pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
612  // Check loop-invariant address because this may also be a sinkable load
613  // whose address is not necessarily loop-invariant.
614  if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
615  ORE->emit([&]() {
617  DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
618  << "failed to move load with loop-invariant address "
619  "because the loop may invalidate its value";
620  });
621 
622  return !Invalidated;
623  } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
624  // Don't sink or hoist dbg info; it's legal, but not useful.
625  if (isa<DbgInfoIntrinsic>(I))
626  return false;
627 
628  // Don't sink calls which can throw.
629  if (CI->mayThrow())
630  return false;
631 
632  // Handle simple cases by querying alias analysis.
633  FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
634  if (Behavior == FMRB_DoesNotAccessMemory)
635  return true;
636  if (AliasAnalysis::onlyReadsMemory(Behavior)) {
637  // A readonly argmemonly function only reads from memory pointed to by
638  // it's arguments with arbitrary offsets. If we can prove there are no
639  // writes to this memory in the loop, we can hoist or sink.
641  for (Value *Op : CI->arg_operands())
642  if (Op->getType()->isPointerTy() &&
644  AAMDNodes(), CurAST))
645  return false;
646  return true;
647  }
648  // If this call only reads from memory and there are no writes to memory
649  // in the loop, we can hoist or sink the call as appropriate.
650  bool FoundMod = false;
651  for (AliasSet &AS : *CurAST) {
652  if (!AS.isForwardingAliasSet() && AS.isMod()) {
653  FoundMod = true;
654  break;
655  }
656  }
657  if (!FoundMod)
658  return true;
659  }
660 
661  // FIXME: This should use mod/ref information to see if we can hoist or
662  // sink the call.
663 
664  return false;
665  }
666 
667  // Only these instructions are hoistable/sinkable.
668  if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
669  !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
670  !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
671  !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
672  !isa<InsertValueInst>(I))
673  return false;
674 
675  // If we are checking for sinking from preheader to loop body it will be
676  // always safe as there is no speculative execution.
677  if (SinkingToLoopBody)
678  return true;
679 
680  // TODO: Plumb the context instruction through to make hoisting and sinking
681  // more powerful. Hoisting of loads already works due to the special casing
682  // above.
683  return isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo, nullptr);
684 }
685 
686 /// Returns true if a PHINode is a trivially replaceable with an
687 /// Instruction.
688 /// This is true when all incoming values are that instruction.
689 /// This pattern occurs most often with LCSSA PHI nodes.
690 ///
691 static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {
692  for (const Value *IncValue : PN.incoming_values())
693  if (IncValue != &I)
694  return false;
695 
696  return true;
697 }
698 
699 /// Return true if the only users of this instruction are outside of
700 /// the loop. If this is true, we can sink the instruction to the exit
701 /// blocks of the loop.
702 ///
703 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
704  const LoopSafetyInfo *SafetyInfo) {
705  const auto &BlockColors = SafetyInfo->BlockColors;
706  for (const User *U : I.users()) {
707  const Instruction *UI = cast<Instruction>(U);
708  if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
709  const BasicBlock *BB = PN->getParent();
710  // We cannot sink uses in catchswitches.
711  if (isa<CatchSwitchInst>(BB->getTerminator()))
712  return false;
713 
714  // We need to sink a callsite to a unique funclet. Avoid sinking if the
715  // phi use is too muddled.
716  if (isa<CallInst>(I))
717  if (!BlockColors.empty() &&
718  BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
719  return false;
720 
721  // A PHI node where all of the incoming values are this instruction are
722  // special -- they can just be RAUW'ed with the instruction and thus
723  // don't require a use in the predecessor. This is a particular important
724  // special case because it is the pattern found in LCSSA form.
725  if (isTriviallyReplacablePHI(*PN, I)) {
726  if (CurLoop->contains(PN))
727  return false;
728  else
729  continue;
730  }
731 
732  // Otherwise, PHI node uses occur in predecessor blocks if the incoming
733  // values. Check for such a use being inside the loop.
734  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
735  if (PN->getIncomingValue(i) == &I)
736  if (CurLoop->contains(PN->getIncomingBlock(i)))
737  return false;
738 
739  continue;
740  }
741 
742  if (CurLoop->contains(UI))
743  return false;
744  }
745  return true;
746 }
747 
748 static Instruction *
750  const LoopInfo *LI,
751  const LoopSafetyInfo *SafetyInfo) {
752  Instruction *New;
753  if (auto *CI = dyn_cast<CallInst>(&I)) {
754  const auto &BlockColors = SafetyInfo->BlockColors;
755 
756  // Sinking call-sites need to be handled differently from other
757  // instructions. The cloned call-site needs a funclet bundle operand
758  // appropriate for it's location in the CFG.
760  for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
761  BundleIdx != BundleEnd; ++BundleIdx) {
762  OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
763  if (Bundle.getTagID() == LLVMContext::OB_funclet)
764  continue;
765 
766  OpBundles.emplace_back(Bundle);
767  }
768 
769  if (!BlockColors.empty()) {
770  const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
771  assert(CV.size() == 1 && "non-unique color for exit block!");
772  BasicBlock *BBColor = CV.front();
773  Instruction *EHPad = BBColor->getFirstNonPHI();
774  if (EHPad->isEHPad())
775  OpBundles.emplace_back("funclet", EHPad);
776  }
777 
778  New = CallInst::Create(CI, OpBundles);
779  } else {
780  New = I.clone();
781  }
782 
783  ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
784  if (!I.getName().empty())
785  New->setName(I.getName() + ".le");
786 
787  // Build LCSSA PHI nodes for any in-loop operands. Note that this is
788  // particularly cheap because we can rip off the PHI node that we're
789  // replacing for the number and blocks of the predecessors.
790  // OPT: If this shows up in a profile, we can instead finish sinking all
791  // invariant instructions, and then walk their operands to re-establish
792  // LCSSA. That will eliminate creating PHI nodes just to nuke them when
793  // sinking bottom-up.
794  for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
795  ++OI)
796  if (Instruction *OInst = dyn_cast<Instruction>(*OI))
797  if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
798  if (!OLoop->contains(&PN)) {
799  PHINode *OpPN =
800  PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
801  OInst->getName() + ".lcssa", &ExitBlock.front());
802  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
803  OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
804  *OI = OpPN;
805  }
806  return New;
807 }
808 
809 /// When an instruction is found to only be used outside of the loop, this
810 /// function moves it to the exit blocks and patches up SSA form as needed.
811 /// This method is guaranteed to remove the original instruction from its
812 /// position, and may either delete it or move it to outside of the loop.
813 ///
814 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
815  const Loop *CurLoop, AliasSetTracker *CurAST,
816  const LoopSafetyInfo *SafetyInfo,
818  DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
819  ORE->emit([&]() {
820  return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
821  << "sinking " << ore::NV("Inst", &I);
822  });
823  bool Changed = false;
824  if (isa<LoadInst>(I))
825  ++NumMovedLoads;
826  else if (isa<CallInst>(I))
827  ++NumMovedCalls;
828  ++NumSunk;
829  Changed = true;
830 
831 #ifndef NDEBUG
833  CurLoop->getUniqueExitBlocks(ExitBlocks);
834  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
835  ExitBlocks.end());
836 #endif
837 
838  // Clones of this instruction. Don't create more than one per exit block!
840 
841  // If this instruction is only used outside of the loop, then all users are
842  // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
843  // the instruction.
844  while (!I.use_empty()) {
846  auto *User = cast<Instruction>(*UI);
847  if (!DT->isReachableFromEntry(User->getParent())) {
849  continue;
850  }
851  // The user must be a PHI node.
852  PHINode *PN = cast<PHINode>(User);
853 
854  // Surprisingly, instructions can be used outside of loops without any
855  // exits. This can only happen in PHI nodes if the incoming block is
856  // unreachable.
857  Use &U = UI.getUse();
858  BasicBlock *BB = PN->getIncomingBlock(U);
859  if (!DT->isReachableFromEntry(BB)) {
860  U = UndefValue::get(I.getType());
861  continue;
862  }
863 
864  BasicBlock *ExitBlock = PN->getParent();
865  assert(ExitBlockSet.count(ExitBlock) &&
866  "The LCSSA PHI is not in an exit block!");
867 
868  Instruction *New;
869  auto It = SunkCopies.find(ExitBlock);
870  if (It != SunkCopies.end())
871  New = It->second;
872  else
873  New = SunkCopies[ExitBlock] =
874  CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo);
875 
876  PN->replaceAllUsesWith(New);
877  PN->eraseFromParent();
878  }
879 
880  CurAST->deleteValue(&I);
881  I.eraseFromParent();
882  return Changed;
883 }
884 
885 /// When an instruction is found to only use loop invariant operands that
886 /// is safe to hoist, this instruction is called to do the dirty work.
887 ///
888 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
889  const LoopSafetyInfo *SafetyInfo,
891  auto *Preheader = CurLoop->getLoopPreheader();
892  DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
893  << "\n");
894  ORE->emit([&]() {
895  return OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting "
896  << ore::NV("Inst", &I);
897  });
898 
899  // Metadata can be dependent on conditions we are hoisting above.
900  // Conservatively strip all metadata on the instruction unless we were
901  // guaranteed to execute I if we entered the loop, in which case the metadata
902  // is valid in the loop preheader.
904  // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
905  // time in isGuaranteedToExecute if we don't actually have anything to
906  // drop. It is a compile time optimization, not required for correctness.
907  !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
909 
910  // Move the new node to the Preheader, before its terminator.
911  I.moveBefore(Preheader->getTerminator());
912 
913  // Do not retain debug locations when we are moving instructions to different
914  // basic blocks, because we want to avoid jumpy line tables. Calls, however,
915  // need to retain their debug locs because they may be inlined.
916  // FIXME: How do we retain source locations without causing poor debugging
917  // behavior?
918  if (!isa<CallInst>(I))
919  I.setDebugLoc(DebugLoc());
920 
921  if (isa<LoadInst>(I))
922  ++NumMovedLoads;
923  else if (isa<CallInst>(I))
924  ++NumMovedCalls;
925  ++NumHoisted;
926  return true;
927 }
928 
929 /// Only sink or hoist an instruction if it is not a trapping instruction,
930 /// or if the instruction is known not to trap when moved to the preheader.
931 /// or if it is a trapping instruction and is guaranteed to execute.
933  const DominatorTree *DT,
934  const Loop *CurLoop,
935  const LoopSafetyInfo *SafetyInfo,
937  const Instruction *CtxI) {
938  if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
939  return true;
940 
941  bool GuaranteedToExecute =
942  isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
943 
944  if (!GuaranteedToExecute) {
945  auto *LI = dyn_cast<LoadInst>(&Inst);
946  if (LI && CurLoop->isLoopInvariant(LI->getPointerOperand()))
947  ORE->emit([&]() {
949  DEBUG_TYPE, "LoadWithLoopInvariantAddressCondExecuted", LI)
950  << "failed to hoist load with loop-invariant address "
951  "because load is conditionally executed";
952  });
953  }
954 
955  return GuaranteedToExecute;
956 }
957 
958 namespace {
959 class LoopPromoter : public LoadAndStorePromoter {
960  Value *SomePtr; // Designated pointer to store to.
961  const SmallSetVector<Value *, 8> &PointerMustAliases;
962  SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
963  SmallVectorImpl<Instruction *> &LoopInsertPts;
964  PredIteratorCache &PredCache;
965  AliasSetTracker &AST;
966  LoopInfo &LI;
967  DebugLoc DL;
968  int Alignment;
969  bool UnorderedAtomic;
970  AAMDNodes AATags;
971 
972  Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
973  if (Instruction *I = dyn_cast<Instruction>(V))
974  if (Loop *L = LI.getLoopFor(I->getParent()))
975  if (!L->contains(BB)) {
976  // We need to create an LCSSA PHI node for the incoming value and
977  // store that.
978  PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
979  I->getName() + ".lcssa", &BB->front());
980  for (BasicBlock *Pred : PredCache.get(BB))
981  PN->addIncoming(I, Pred);
982  return PN;
983  }
984  return V;
985  }
986 
987 public:
988  LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
989  const SmallSetVector<Value *, 8> &PMA,
992  AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
993  bool UnorderedAtomic, const AAMDNodes &AATags)
994  : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
995  LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
996  LI(li), DL(std::move(dl)), Alignment(alignment),
997  UnorderedAtomic(UnorderedAtomic), AATags(AATags) {}
998 
999  bool isInstInList(Instruction *I,
1000  const SmallVectorImpl<Instruction *> &) const override {
1001  Value *Ptr;
1002  if (LoadInst *LI = dyn_cast<LoadInst>(I))
1003  Ptr = LI->getOperand(0);
1004  else
1005  Ptr = cast<StoreInst>(I)->getPointerOperand();
1006  return PointerMustAliases.count(Ptr);
1007  }
1008 
1009  void doExtraRewritesBeforeFinalDeletion() const override {
1010  // Insert stores after in the loop exit blocks. Each exit block gets a
1011  // store of the live-out values that feed them. Since we've already told
1012  // the SSA updater about the defs in the loop and the preheader
1013  // definition, it is all set and we can start using it.
1014  for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
1015  BasicBlock *ExitBlock = LoopExitBlocks[i];
1016  Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
1017  LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1018  Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1019  Instruction *InsertPos = LoopInsertPts[i];
1020  StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
1021  if (UnorderedAtomic)
1023  NewSI->setAlignment(Alignment);
1024  NewSI->setDebugLoc(DL);
1025  if (AATags)
1026  NewSI->setAAMetadata(AATags);
1027  }
1028  }
1029 
1030  void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
1031  // Update alias analysis.
1032  AST.copyValue(LI, V);
1033  }
1034  void instructionDeleted(Instruction *I) const override { AST.deleteValue(I); }
1035 };
1036 } // namespace
1037 
1038 /// Try to promote memory values to scalars by sinking stores out of the
1039 /// loop and moving loads to before the loop. We do this by looping over
1040 /// the stores in the loop, looking for stores to Must pointers which are
1041 /// loop invariant.
1042 ///
1044  const SmallSetVector<Value *, 8> &PointerMustAliases,
1045  SmallVectorImpl<BasicBlock *> &ExitBlocks,
1047  LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
1048  Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
1050  // Verify inputs.
1051  assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
1052  CurAST != nullptr && SafetyInfo != nullptr &&
1053  "Unexpected Input to promoteLoopAccessesToScalars");
1054 
1055  Value *SomePtr = *PointerMustAliases.begin();
1056  BasicBlock *Preheader = CurLoop->getLoopPreheader();
1057 
1058  // It isn't safe to promote a load/store from the loop if the load/store is
1059  // conditional. For example, turning:
1060  //
1061  // for () { if (c) *P += 1; }
1062  //
1063  // into:
1064  //
1065  // tmp = *P; for () { if (c) tmp +=1; } *P = tmp;
1066  //
1067  // is not safe, because *P may only be valid to access if 'c' is true.
1068  //
1069  // The safety property divides into two parts:
1070  // p1) The memory may not be dereferenceable on entry to the loop. In this
1071  // case, we can't insert the required load in the preheader.
1072  // p2) The memory model does not allow us to insert a store along any dynamic
1073  // path which did not originally have one.
1074  //
1075  // If at least one store is guaranteed to execute, both properties are
1076  // satisfied, and promotion is legal.
1077  //
1078  // This, however, is not a necessary condition. Even if no store/load is
1079  // guaranteed to execute, we can still establish these properties.
1080  // We can establish (p1) by proving that hoisting the load into the preheader
1081  // is safe (i.e. proving dereferenceability on all paths through the loop). We
1082  // can use any access within the alias set to prove dereferenceability,
1083  // since they're all must alias.
1084  //
1085  // There are two ways establish (p2):
1086  // a) Prove the location is thread-local. In this case the memory model
1087  // requirement does not apply, and stores are safe to insert.
1088  // b) Prove a store dominates every exit block. In this case, if an exit
1089  // blocks is reached, the original dynamic path would have taken us through
1090  // the store, so inserting a store into the exit block is safe. Note that this
1091  // is different from the store being guaranteed to execute. For instance,
1092  // if an exception is thrown on the first iteration of the loop, the original
1093  // store is never executed, but the exit blocks are not executed either.
1094 
1095  bool DereferenceableInPH = false;
1096  bool SafeToInsertStore = false;
1097 
1099 
1100  // We start with an alignment of one and try to find instructions that allow
1101  // us to prove better alignment.
1102  unsigned Alignment = 1;
1103  // Keep track of which types of access we see
1104  bool SawUnorderedAtomic = false;
1105  bool SawNotAtomic = false;
1106  AAMDNodes AATags;
1107 
1108  const DataLayout &MDL = Preheader->getModule()->getDataLayout();
1109 
1110  // Do we know this object does not escape ?
1111  bool IsKnownNonEscapingObject = false;
1112  if (SafetyInfo->MayThrow) {
1113  // If a loop can throw, we have to insert a store along each unwind edge.
1114  // That said, we can't actually make the unwind edge explicit. Therefore,
1115  // we have to prove that the store is dead along the unwind edge.
1116  //
1117  // If the underlying object is not an alloca, nor a pointer that does not
1118  // escape, then we can not effectively prove that the store is dead along
1119  // the unwind edge. i.e. the caller of this function could have ways to
1120  // access the pointed object.
1121  Value *Object = GetUnderlyingObject(SomePtr, MDL);
1122  // If this is a base pointer we do not understand, simply bail.
1123  // We only handle alloca and return value from alloc-like fn right now.
1124  if (!isa<AllocaInst>(Object)) {
1125  if (!isAllocLikeFn(Object, TLI))
1126  return false;
1127  // If this is an alloc like fn. There are more constraints we need to
1128  // verify. More specifically, we must make sure that the pointer can not
1129  // escape.
1130  //
1131  // NOTE: PointerMayBeCaptured is not enough as the pointer may have
1132  // escaped even though its not captured by the enclosing function.
1133  // Standard allocation functions like malloc, calloc, and operator new
1134  // return values which can be assumed not to have previously escaped.
1135  if (PointerMayBeCaptured(Object, true, true))
1136  return false;
1137  IsKnownNonEscapingObject = true;
1138  }
1139  }
1140 
1141  // Check that all of the pointers in the alias set have the same type. We
1142  // cannot (yet) promote a memory location that is loaded and stored in
1143  // different sizes. While we are at it, collect alignment and AA info.
1144  for (Value *ASIV : PointerMustAliases) {
1145  // Check that all of the pointers in the alias set have the same type. We
1146  // cannot (yet) promote a memory location that is loaded and stored in
1147  // different sizes.
1148  if (SomePtr->getType() != ASIV->getType())
1149  return false;
1150 
1151  for (User *U : ASIV->users()) {
1152  // Ignore instructions that are outside the loop.
1153  Instruction *UI = dyn_cast<Instruction>(U);
1154  if (!UI || !CurLoop->contains(UI))
1155  continue;
1156 
1157  // If there is an non-load/store instruction in the loop, we can't promote
1158  // it.
1159  if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
1160  assert(!Load->isVolatile() && "AST broken");
1161  if (!Load->isUnordered())
1162  return false;
1163 
1164  SawUnorderedAtomic |= Load->isAtomic();
1165  SawNotAtomic |= !Load->isAtomic();
1166 
1167  if (!DereferenceableInPH)
1168  DereferenceableInPH = isSafeToExecuteUnconditionally(
1169  *Load, DT, CurLoop, SafetyInfo, ORE, Preheader->getTerminator());
1170  } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
1171  // Stores *of* the pointer are not interesting, only stores *to* the
1172  // pointer.
1173  if (UI->getOperand(1) != ASIV)
1174  continue;
1175  assert(!Store->isVolatile() && "AST broken");
1176  if (!Store->isUnordered())
1177  return false;
1178 
1179  SawUnorderedAtomic |= Store->isAtomic();
1180  SawNotAtomic |= !Store->isAtomic();
1181 
1182  // If the store is guaranteed to execute, both properties are satisfied.
1183  // We may want to check if a store is guaranteed to execute even if we
1184  // already know that promotion is safe, since it may have higher
1185  // alignment than any other guaranteed stores, in which case we can
1186  // raise the alignment on the promoted store.
1187  unsigned InstAlignment = Store->getAlignment();
1188  if (!InstAlignment)
1189  InstAlignment =
1190  MDL.getABITypeAlignment(Store->getValueOperand()->getType());
1191 
1192  if (!DereferenceableInPH || !SafeToInsertStore ||
1193  (InstAlignment > Alignment)) {
1194  if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
1195  DereferenceableInPH = true;
1196  SafeToInsertStore = true;
1197  Alignment = std::max(Alignment, InstAlignment);
1198  }
1199  }
1200 
1201  // If a store dominates all exit blocks, it is safe to sink.
1202  // As explained above, if an exit block was executed, a dominating
1203  // store must have been been executed at least once, so we are not
1204  // introducing stores on paths that did not have them.
1205  // Note that this only looks at explicit exit blocks. If we ever
1206  // start sinking stores into unwind edges (see above), this will break.
1207  if (!SafeToInsertStore)
1208  SafeToInsertStore = llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
1209  return DT->dominates(Store->getParent(), Exit);
1210  });
1211 
1212  // If the store is not guaranteed to execute, we may still get
1213  // deref info through it.
1214  if (!DereferenceableInPH) {
1215  DereferenceableInPH = isDereferenceableAndAlignedPointer(
1216  Store->getPointerOperand(), Store->getAlignment(), MDL,
1217  Preheader->getTerminator(), DT);
1218  }
1219  } else
1220  return false; // Not a load or store.
1221 
1222  // Merge the AA tags.
1223  if (LoopUses.empty()) {
1224  // On the first load/store, just take its AA tags.
1225  UI->getAAMetadata(AATags);
1226  } else if (AATags) {
1227  UI->getAAMetadata(AATags, /* Merge = */ true);
1228  }
1229 
1230  LoopUses.push_back(UI);
1231  }
1232  }
1233 
1234  // If we found both an unordered atomic instruction and a non-atomic memory
1235  // access, bail. We can't blindly promote non-atomic to atomic since we
1236  // might not be able to lower the result. We can't downgrade since that
1237  // would violate memory model. Also, align 0 is an error for atomics.
1238  if (SawUnorderedAtomic && SawNotAtomic)
1239  return false;
1240 
1241  // If we couldn't prove we can hoist the load, bail.
1242  if (!DereferenceableInPH)
1243  return false;
1244 
1245  // We know we can hoist the load, but don't have a guaranteed store.
1246  // Check whether the location is thread-local. If it is, then we can insert
1247  // stores along paths which originally didn't have them without violating the
1248  // memory model.
1249  if (!SafeToInsertStore) {
1250  // If this is a known non-escaping object, it is safe to insert the stores.
1251  if (IsKnownNonEscapingObject)
1252  SafeToInsertStore = true;
1253  else {
1254  Value *Object = GetUnderlyingObject(SomePtr, MDL);
1255  SafeToInsertStore =
1256  (isAllocLikeFn(Object, TLI) || isa<AllocaInst>(Object)) &&
1257  !PointerMayBeCaptured(Object, true, true);
1258  }
1259  }
1260 
1261  // If we've still failed to prove we can sink the store, give up.
1262  if (!SafeToInsertStore)
1263  return false;
1264 
1265  // Otherwise, this is safe to promote, lets do it!
1266  DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr
1267  << '\n');
1268  ORE->emit([&]() {
1269  return OptimizationRemark(DEBUG_TYPE, "PromoteLoopAccessesToScalar",
1270  LoopUses[0])
1271  << "Moving accesses to memory location out of the loop";
1272  });
1273  ++NumPromoted;
1274 
1275  // Grab a debug location for the inserted loads/stores; given that the
1276  // inserted loads/stores have little relation to the original loads/stores,
1277  // this code just arbitrarily picks a location from one, since any debug
1278  // location is better than none.
1279  DebugLoc DL = LoopUses[0]->getDebugLoc();
1280 
1281  // We use the SSAUpdater interface to insert phi nodes as required.
1283  SSAUpdater SSA(&NewPHIs);
1284  LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
1285  InsertPts, PIC, *CurAST, *LI, DL, Alignment,
1286  SawUnorderedAtomic, AATags);
1287 
1288  // Set up the preheader to have a definition of the value. It is the live-out
1289  // value from the preheader that uses in the loop will use.
1290  LoadInst *PreheaderLoad = new LoadInst(
1291  SomePtr, SomePtr->getName() + ".promoted", Preheader->getTerminator());
1292  if (SawUnorderedAtomic)
1293  PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
1294  PreheaderLoad->setAlignment(Alignment);
1295  PreheaderLoad->setDebugLoc(DL);
1296  if (AATags)
1297  PreheaderLoad->setAAMetadata(AATags);
1298  SSA.AddAvailableValue(Preheader, PreheaderLoad);
1299 
1300  // Rewrite all the loads in the loop and remember all the definitions from
1301  // stores in the loop.
1302  Promoter.run(LoopUses);
1303 
1304  // If the SSAUpdater didn't use the load in the preheader, just zap it now.
1305  if (PreheaderLoad->use_empty())
1306  PreheaderLoad->eraseFromParent();
1307 
1308  return true;
1309 }
1310 
1311 /// Returns an owning pointer to an alias set which incorporates aliasing info
1312 /// from L and all subloops of L.
1313 /// FIXME: In new pass manager, there is no helper function to handle loop
1314 /// analysis such as cloneBasicBlockAnalysis, so the AST needs to be recomputed
1315 /// from scratch for every loop. Hook up with the helper functions when
1316 /// available in the new pass manager to avoid redundant computation.
1318 LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
1319  AliasAnalysis *AA) {
1320  AliasSetTracker *CurAST = nullptr;
1321  SmallVector<Loop *, 4> RecomputeLoops;
1322  for (Loop *InnerL : L->getSubLoops()) {
1323  auto MapI = LoopToAliasSetMap.find(InnerL);
1324  // If the AST for this inner loop is missing it may have been merged into
1325  // some other loop's AST and then that loop unrolled, and so we need to
1326  // recompute it.
1327  if (MapI == LoopToAliasSetMap.end()) {
1328  RecomputeLoops.push_back(InnerL);
1329  continue;
1330  }
1331  AliasSetTracker *InnerAST = MapI->second;
1332 
1333  if (CurAST != nullptr) {
1334  // What if InnerLoop was modified by other passes ?
1335  CurAST->add(*InnerAST);
1336 
1337  // Once we've incorporated the inner loop's AST into ours, we don't need
1338  // the subloop's anymore.
1339  delete InnerAST;
1340  } else {
1341  CurAST = InnerAST;
1342  }
1343  LoopToAliasSetMap.erase(MapI);
1344  }
1345  if (CurAST == nullptr)
1346  CurAST = new AliasSetTracker(*AA);
1347 
1348  auto mergeLoop = [&](Loop *L) {
1349  // Loop over the body of this loop, looking for calls, invokes, and stores.
1350  for (BasicBlock *BB : L->blocks())
1351  CurAST->add(*BB); // Incorporate the specified basic block
1352  };
1353 
1354  // Add everything from the sub loops that are no longer directly available.
1355  for (Loop *InnerL : RecomputeLoops)
1356  mergeLoop(InnerL);
1357 
1358  // And merge in this loop.
1359  mergeLoop(L);
1360 
1361  return CurAST;
1362 }
1363 
1364 /// Simple analysis hook. Clone alias set info.
1365 ///
1366 void LegacyLICMPass::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
1367  Loop *L) {
1368  AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
1369  if (!AST)
1370  return;
1371 
1372  AST->copyValue(From, To);
1373 }
1374 
1375 /// Simple Analysis hook. Delete value V from alias set
1376 ///
1377 void LegacyLICMPass::deleteAnalysisValue(Value *V, Loop *L) {
1378  AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
1379  if (!AST)
1380  return;
1381 
1382  AST->deleteValue(V);
1383 }
1384 
1385 /// Simple Analysis hook. Delete value L from alias set map.
1386 ///
1387 void LegacyLICMPass::deleteAnalysisLoop(Loop *L) {
1388  AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
1389  if (!AST)
1390  return;
1391 
1392  delete AST;
1393  LICM.getLoopToAliasSetMap().erase(L);
1394 }
1395 
1396 /// Return true if the body of this loop may store into the memory
1397 /// location pointed to by V.
1398 ///
1399 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
1400  const AAMDNodes &AAInfo,
1401  AliasSetTracker *CurAST) {
1402  // Check to see if any of the basic blocks in CurLoop invalidate *V.
1403  return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
1404 }
1405 
1406 /// Little predicate that returns true if the specified basic block is in
1407 /// a subloop of the current one, not the current one itself.
1408 ///
1409 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
1410  assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
1411  return LI->getLoopFor(BB) != CurLoop;
1412 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
uint64_t CallInst * C
DomTreeNodeBase< NodeT > * getNode(NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:39
Diagnostic information for missed-optimization remarks.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
DiagnosticInfoOptimizationBase::Argument NV
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:103
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This header provides classes for managing a pipeline of passes over loops in LLVM IR...
This is the interface for a simple mod/ref and alias analysis over globals.
EltTy front() const
bool hasMetadataOtherThanDebugLoc() const
Return true if this instruction has metadata attached to it other than a debug location.
Definition: Instruction.h:188
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1187
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:175
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value...
Definition: SSAUpdater.cpp:67
The main scalar evolution driver.
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this load instruction.
Definition: Instructions.h:239
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:106
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space...
Definition: Type.cpp:617
bool onlyReadsMemory(ImmutableCallSite CS)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:697
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:816
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:34
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
F(f)
static CallInst * Create(Value *Func, ArrayRef< Value *> Args, ArrayRef< OperandBundleDef > Bundles=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
An instruction for reading from memory.
Definition: Instructions.h:164
void reserve(size_type N)
Definition: SmallVector.h:380
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:31
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:290
op_iterator op_begin()
Definition: User.h:214
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:62
static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I)
Returns true if a PHINode is a trivially replaceable with an Instruction.
Definition: LICM.cpp:691
DenseMap< BasicBlock *, ColorVector > BlockColors
Definition: LoopUtils.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
Loop Invariant Code Motion
Definition: LICM.cpp:220
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:332
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
ArrayRef< BasicBlock * > get(BasicBlock *BB)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
This is the interface for a SCEV-based alias analysis.
static Value * getPointerOperand(Instruction &Inst)
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:659
static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE)
When an instruction is found to only use loop invariant operands that is safe to hoist, this instruction is called to do the dirty work.
Definition: LICM.cpp:888
bool hasAllowReciprocal() const
Determine whether the allow-reciprocal flag is set.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
iterator find(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:383
virtual bool doFinalization(Module &)
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Definition: Pass.h:110
uint32_t getTagID() const
Return the tag of this operand bundle as an integer.
Definition: InstrTypes.h:1190
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:284
BlockT * getHeader() const
Definition: LoopInfo.h:100
void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: LICM.cpp:489
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfo.cpp:380
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:248
INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false, false) INITIALIZE_PASS_END(LegacyLICMPass
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
static bool pointerInvalidatedByLoop(Value *V, uint64_t Size, const AAMDNodes &AAInfo, AliasSetTracker *CurAST)
Return true if the body of this loop may store into the memory location pointed to by V...
Definition: LICM.cpp:1399
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries...
FunctionModRefBehavior
Summary of how a function affects memory in the program.
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:83
This class represents a no-op cast from one type to another.
Memory SSA
Definition: MemorySSA.cpp:65
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
An instruction for storing to memory.
Definition: Instructions.h:306
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:634
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.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock *> &, SmallVectorImpl< Instruction *> &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *)
Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before ...
Definition: LICM.cpp:1043
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
Value * getOperand(unsigned i) const
Definition: User.h:154
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
void getUniqueExitBlocks(SmallVectorImpl< BasicBlock *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfo.cpp:393
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:22
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal=false)
Checks whether the given location points to constant memory, or if OrLocal is true whether it points ...
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
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:200
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:281
void setAAMetadata(const AAMDNodes &N)
Sets the metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1253
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
size_t size(BasicBlock *BB) const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:264
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
const std::vector< BlockT * > & getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:149
Diagnostic information for applied optimization remarks.
Pass * createLICMPass()
Definition: LICM.cpp:223
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
Return the behavior of the given call site.
Represent the analysis usage information of a pass.
op_iterator op_end()
Definition: User.h:216
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:823
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LICM.cpp:194
std::vector< BasicBlock *>::const_iterator block_iterator
Definition: LoopInfo.h:153
static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT, const Loop *CurLoop, AliasSetTracker *CurAST, const LoopSafetyInfo *SafetyInfo, 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:814
bool isMod() const
void setAlignment(unsigned Align)
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1320
const AMDGPUAS & AS
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT, Loop *CurLoop)
Definition: LICM.cpp:527
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This function does not perform any non-local loads or stores to memory.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:56
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)"))
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:51
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:317
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
#define DEBUG_TYPE
Definition: LICM.cpp:72
bool isFuncletEHPersonality(EHPersonality Pers)
Returns true if this is a personality function that invokes handler funclets (which must return to it...
iterator end()
Definition: BasicBlock.h:254
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1062
Helper class for promoting a collection of loads and stores into SSA Form using the SSAUpdater...
Definition: SSAUpdater.h:133
void copyValue(Value *From, Value *To)
This method should be used whenever a preexisting value in the program is copied or cloned...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:239
Provides information about what library functions are available for the current target.
unsigned getABITypeAlignment(Type *Ty) const
Returns the minimum ABI-required alignment for the specified type.
Definition: DataLayout.cpp:682
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo)
Return true if the only users of this instruction are outside of the loop.
Definition: LICM.cpp:703
bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *ORE)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block...
Definition: LICM.cpp:410
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...
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
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:623
unsigned getNumIncomingValues() const
Return the number of incoming edges.
void add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *ORE)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block...
Definition: LICM.cpp:353
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:57
A lightweight accessor for an operand bundle meant to be passed around by value.
Definition: InstrTypes.h:1162
iterator_range< user_iterator > users()
Definition: Value.h:395
static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, const Instruction *CtxI=nullptr)
Only sink or hoist an instruction if it is not a trapping instruction, or if the instruction is known...
Definition: LICM.cpp:932
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:532
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
Definition: LoopInfo.h:131
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this store instruction.
Definition: Instructions.h:364
static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from objects poin...
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
iterator insert(iterator where, pointer New)
Definition: ilist.h:241
Captures loop safety information.
Definition: LoopUtils.h:51
AliasSet & getAliasSetForPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo)
Return the alias set that the specified pointer lives in.
static Instruction * CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo)
Definition: LICM.cpp:749
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:656
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:420
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
user_iterator_impl< User > user_iterator
Definition: Value.h:364
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc...
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:1023
licm
Definition: LICM.cpp:220
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
block_iterator block_end() const
Definition: LoopInfo.h:155
iterator end() const
Definition: SmallPtrSet.h:402
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:1122
bool empty() const
Definition: LoopInfo.h:146
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:276
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:1409
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:371
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:324
LLVM Value Representation.
Definition: Value.h:73
void setAlignment(unsigned Align)
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1260
uint64_t getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:388
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:88
void initializeLegacyLICMPassPass(PassRegistry &)
#define DEBUG(X)
Definition: Debug.h:118
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:522
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
A container for analyses that lazily runs them and caches their results.
bool isDereferenceableAndAlignedPointer(const Value *V, unsigned Align, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Returns true if V is always a dereferenceable pointer with alignment greater or equal than requested...
Definition: Loads.cpp:129
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if the hoister and sinker can handle this instruction.
Definition: LICM.cpp:576
const TerminatorInst * 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.cpp:120
DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
op_range incoming_values()
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo)
Returns true if the instruction in a loop is guaranteed to execute at least once. ...
Definition: LoopUtils.cpp:1264
block_iterator block_begin() const
Definition: LoopInfo.h:154
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:174
The optimization diagnostic interface.
bool use_empty() const
Definition: Value.h:322
unsigned size() const
void deleteValue(Value *PtrVal)
This method is used to remove a pointer value from the AliasSetTracker entirely.
loop versioning Loop Versioning For LICM
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:66