LLVM  8.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"
42 #include "llvm/Analysis/Loads.h"
43 #include "llvm/Analysis/LoopInfo.h"
44 #include "llvm/Analysis/LoopPass.h"
53 #include "llvm/IR/CFG.h"
54 #include "llvm/IR/Constants.h"
55 #include "llvm/IR/DataLayout.h"
56 #include "llvm/IR/DerivedTypes.h"
57 #include "llvm/IR/Dominators.h"
58 #include "llvm/IR/Instructions.h"
59 #include "llvm/IR/IntrinsicInst.h"
60 #include "llvm/IR/LLVMContext.h"
61 #include "llvm/IR/Metadata.h"
62 #include "llvm/IR/PatternMatch.h"
65 #include "llvm/Support/Debug.h"
67 #include "llvm/Transforms/Scalar.h"
72 #include <algorithm>
73 #include <utility>
74 using namespace llvm;
75 
76 #define DEBUG_TYPE "licm"
77 
78 STATISTIC(NumSunk, "Number of instructions sunk out of loop");
79 STATISTIC(NumHoisted, "Number of instructions hoisted out of loop");
80 STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
81 STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
82 STATISTIC(NumPromoted, "Number of memory locations promoted to registers");
83 
84 /// Memory promotion is enabled by default.
85 static cl::opt<bool>
86  DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
87  cl::desc("Disable memory promotion in LICM pass"));
88 
90  "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
91  cl::desc("Max num uses visited for identifying load "
92  "invariance in loop using invariant start (default = 8)"));
93 
94 // Default value of zero implies we use the regular alias set tracker mechanism
95 // instead of the cross product using AA to identify aliasing of the memory
96 // location we are interested in.
97 static cl::opt<int>
98 LICMN2Theshold("licm-n2-threshold", cl::Hidden, cl::init(0),
99  cl::desc("How many instruction to cross product using AA"));
100 
101 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
102 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
103  const LoopSafetyInfo *SafetyInfo,
104  TargetTransformInfo *TTI, bool &FreeInLoop);
105 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
106  LoopSafetyInfo *SafetyInfo,
108 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
109  const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
110  OptimizationRemarkEmitter *ORE, bool FreeInLoop);
112  const DominatorTree *DT,
113  const Loop *CurLoop,
114  const LoopSafetyInfo *SafetyInfo,
116  const Instruction *CtxI = nullptr);
117 static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
118  AliasSetTracker *CurAST, Loop *CurLoop,
119  AliasAnalysis *AA);
120 
121 static Instruction *
123  const LoopInfo *LI,
124  const LoopSafetyInfo *SafetyInfo);
125 
126 namespace {
127 struct LoopInvariantCodeMotion {
129  bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
131  ScalarEvolution *SE, MemorySSA *MSSA,
132  OptimizationRemarkEmitter *ORE, bool DeleteAST);
133 
134  ASTrackerMapTy &getLoopToAliasSetMap() { return LoopToAliasSetMap; }
135 
136 private:
137  ASTrackerMapTy LoopToAliasSetMap;
138 
139  std::unique_ptr<AliasSetTracker>
140  collectAliasInfoForLoop(Loop *L, LoopInfo *LI, AliasAnalysis *AA);
141 };
142 
143 struct LegacyLICMPass : public LoopPass {
144  static char ID; // Pass identification, replacement for typeid
145  LegacyLICMPass() : LoopPass(ID) {
147  }
148 
149  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
150  if (skipLoop(L)) {
151  // If we have run LICM on a previous loop but now we are skipping
152  // (because we've hit the opt-bisect limit), we need to clear the
153  // loop alias information.
154  LICM.getLoopToAliasSetMap().clear();
155  return false;
156  }
157 
158  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
160  ? (&getAnalysis<MemorySSAWrapperPass>().getMSSA())
161  : nullptr;
162  // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
163  // pass. Function analyses need to be preserved across loop transformations
164  // but ORE cannot be preserved (see comment before the pass definition).
166  return LICM.runOnLoop(L,
167  &getAnalysis<AAResultsWrapperPass>().getAAResults(),
168  &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
169  &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
170  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
171  &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
172  *L->getHeader()->getParent()),
173  SE ? &SE->getSE() : nullptr, MSSA, &ORE, false);
174  }
175 
176  /// This transformation requires natural loop information & requires that
177  /// loop preheaders be inserted into the CFG...
178  ///
179  void getAnalysisUsage(AnalysisUsage &AU) const override {
187  }
188 
190 
191  bool doFinalization() override {
192  assert(LICM.getLoopToAliasSetMap().empty() &&
193  "Didn't free loop alias sets");
194  return false;
195  }
196 
197 private:
198  LoopInvariantCodeMotion LICM;
199 
200  /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info.
201  void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
202  Loop *L) override;
203 
204  /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
205  /// set.
206  void deleteAnalysisValue(Value *V, Loop *L) override;
207 
208  /// Simple Analysis hook. Delete loop L from alias set map.
209  void deleteAnalysisLoop(Loop *L) override;
210 };
211 } // namespace
212 
215  const auto &FAM =
216  AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
217  Function *F = L.getHeader()->getParent();
218 
219  auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
220  // FIXME: This should probably be optional rather than required.
221  if (!ORE)
222  report_fatal_error("LICM: OptimizationRemarkEmitterAnalysis not "
223  "cached at a higher level");
224 
225  LoopInvariantCodeMotion LICM;
226  if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.TTI, &AR.SE,
227  AR.MSSA, ORE, true))
228  return PreservedAnalyses::all();
229 
230  auto PA = getLoopPassPreservedAnalyses();
231 
232  PA.preserve<DominatorTreeAnalysis>();
233  PA.preserve<LoopAnalysis>();
234 
235  return PA;
236 }
237 
238 char LegacyLICMPass::ID = 0;
239 INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
240  false, false)
245 INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
246  false)
247 
248 Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
249 
250 /// Hoist expressions out of the specified loop. Note, alias info for inner
251 /// loop is not preserved so it is not a good idea to run LICM multiple
252 /// times on one loop.
253 /// We should delete AST for inner loops in the new pass manager to avoid
254 /// memory leak.
255 ///
256 bool LoopInvariantCodeMotion::runOnLoop(
257  Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
259  MemorySSA *MSSA, OptimizationRemarkEmitter *ORE, bool DeleteAST) {
260  bool Changed = false;
261 
262  assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
263 
264  std::unique_ptr<AliasSetTracker> CurAST = collectAliasInfoForLoop(L, LI, AA);
265 
266  // Get the preheader block to move instructions into...
267  BasicBlock *Preheader = L->getLoopPreheader();
268 
269  // Compute loop safety information.
270  LoopSafetyInfo SafetyInfo;
271  SafetyInfo.computeLoopSafetyInfo(L);
272 
273  // We want to visit all of the instructions in this loop... that are not parts
274  // of our subloops (they have already had their invariants hoisted out of
275  // their loop, into this loop, so there is no need to process the BODIES of
276  // the subloops).
277  //
278  // Traverse the body of the loop in depth first order on the dominator tree so
279  // that we are guaranteed to see definitions before we see uses. This allows
280  // us to sink instructions in one pass, without iteration. After sinking
281  // instructions, we perform another pass to hoist them out of the loop.
282  //
283  if (L->hasDedicatedExits())
284  Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L,
285  CurAST.get(), &SafetyInfo, ORE);
286  if (Preheader)
287  Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
288  CurAST.get(), &SafetyInfo, ORE);
289 
290  // Now that all loop invariants have been removed from the loop, promote any
291  // memory references to scalars that we can.
292  // Don't sink stores from loops without dedicated block exits. Exits
293  // containing indirect branches are not transformed by loop simplify,
294  // make sure we catch that. An additional load may be generated in the
295  // preheader for SSA updater, so also avoid sinking when no preheader
296  // is available.
297  if (!DisablePromotion && Preheader && L->hasDedicatedExits()) {
298  // Figure out the loop exits and their insertion points
299  SmallVector<BasicBlock *, 8> ExitBlocks;
300  L->getUniqueExitBlocks(ExitBlocks);
301 
302  // We can't insert into a catchswitch.
303  bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
304  return isa<CatchSwitchInst>(Exit->getTerminator());
305  });
306 
307  if (!HasCatchSwitch) {
309  InsertPts.reserve(ExitBlocks.size());
310  for (BasicBlock *ExitBlock : ExitBlocks)
311  InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
312 
313  PredIteratorCache PIC;
314 
315  bool Promoted = false;
316 
317  // Loop over all of the alias sets in the tracker object.
318  for (AliasSet &AS : *CurAST) {
319  // We can promote this alias set if it has a store, if it is a "Must"
320  // alias set, if the pointer is loop invariant, and if we are not
321  // eliminating any volatile loads or stores.
322  if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
323  !L->isLoopInvariant(AS.begin()->getValue()))
324  continue;
325 
326  assert(
327  !AS.empty() &&
328  "Must alias set should have at least one pointer element in it!");
329 
330  SmallSetVector<Value *, 8> PointerMustAliases;
331  for (const auto &ASI : AS)
332  PointerMustAliases.insert(ASI.getValue());
333 
334  Promoted |= promoteLoopAccessesToScalars(
335  PointerMustAliases, ExitBlocks, InsertPts, PIC, LI, DT, TLI, L,
336  CurAST.get(), &SafetyInfo, ORE);
337  }
338 
339  // Once we have promoted values across the loop body we have to
340  // recursively reform LCSSA as any nested loop may now have values defined
341  // within the loop used in the outer loop.
342  // FIXME: This is really heavy handed. It would be a bit better to use an
343  // SSAUpdater strategy during promotion that was LCSSA aware and reformed
344  // it as it went.
345  if (Promoted)
346  formLCSSARecursively(*L, *DT, LI, SE);
347 
348  Changed |= Promoted;
349  }
350  }
351 
352  // Check that neither this loop nor its parent have had LCSSA broken. LICM is
353  // specifically moving instructions across the loop boundary and so it is
354  // especially in need of sanity checking here.
355  assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
356  assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
357  "Parent loop not left in LCSSA form after LICM!");
358 
359  // If this loop is nested inside of another one, save the alias information
360  // for when we process the outer loop.
361  if (L->getParentLoop() && !DeleteAST)
362  LoopToAliasSetMap[L] = std::move(CurAST);
363 
364  if (Changed && SE)
365  SE->forgetLoopDispositions(L);
366  return Changed;
367 }
368 
369 /// Walk the specified region of the CFG (defined by all blocks dominated by
370 /// the specified block, and that are in the current loop) in reverse depth
371 /// first order w.r.t the DominatorTree. This allows us to visit uses before
372 /// definitions, allowing us to sink a loop body in one pass without iteration.
373 ///
376  TargetTransformInfo *TTI, Loop *CurLoop,
377  AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
379 
380  // Verify inputs.
381  assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
382  CurLoop != nullptr && CurAST && SafetyInfo != nullptr &&
383  "Unexpected input to sinkRegion");
384 
385  // We want to visit children before parents. We will enque all the parents
386  // before their children in the worklist and process the worklist in reverse
387  // order.
389 
390  bool Changed = false;
391  for (DomTreeNode *DTN : reverse(Worklist)) {
392  BasicBlock *BB = DTN->getBlock();
393  // Only need to process the contents of this block if it is not part of a
394  // subloop (which would already have been processed).
395  if (inSubLoop(BB, CurLoop, LI))
396  continue;
397 
398  for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
399  Instruction &I = *--II;
400 
401  // If the instruction is dead, we would try to sink it because it isn't
402  // used in the loop, instead, just delete it.
403  if (isInstructionTriviallyDead(&I, TLI)) {
404  LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
405  salvageDebugInfo(I);
406  ++II;
407  CurAST->deleteValue(&I);
408  I.eraseFromParent();
409  Changed = true;
410  continue;
411  }
412 
413  // Check to see if we can sink this instruction to the exit blocks
414  // of the loop. We can do this if the all users of the instruction are
415  // outside of the loop. In this case, it doesn't even matter if the
416  // operands of the instruction are loop invariant.
417  //
418  bool FreeInLoop = false;
419  if (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
420  canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, true, ORE) &&
421  !I.mayHaveSideEffects()) {
422  if (sink(I, LI, DT, CurLoop, SafetyInfo, ORE, FreeInLoop)) {
423  if (!FreeInLoop) {
424  ++II;
425  CurAST->deleteValue(&I);
426  I.eraseFromParent();
427  }
428  Changed = true;
429  }
430  }
431  }
432  }
433  return Changed;
434 }
435 
436 /// Walk the specified region of the CFG (defined by all blocks dominated by
437 /// the specified block, and that are in the current loop) in depth first
438 /// order w.r.t the DominatorTree. This allows us to visit definitions before
439 /// uses, allowing us to hoist a loop body in one pass without iteration.
440 ///
442  DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
443  AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
445  // Verify inputs.
446  assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
447  CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
448  "Unexpected input to hoistRegion");
449 
450  // We want to visit parents before children. We will enque all the parents
451  // before their children in the worklist and process the worklist in order.
453 
454  bool Changed = false;
455  for (DomTreeNode *DTN : Worklist) {
456  BasicBlock *BB = DTN->getBlock();
457  // Only need to process the contents of this block if it is not part of a
458  // subloop (which would already have been processed).
459  if (inSubLoop(BB, CurLoop, LI))
460  continue;
461 
462  // Keep track of whether the prefix of instructions visited so far are such
463  // that the next instruction visited is guaranteed to execute if the loop
464  // is entered.
465  bool IsMustExecute = CurLoop->getHeader() == BB;
466  // Keep track of whether the prefix instructions could have written memory.
467  // TODO: This and IsMustExecute may be done smarter if we keep track of all
468  // throwing and mem-writing operations in every block, e.g. using something
469  // similar to isGuaranteedToExecute.
470  bool IsMemoryNotModified = CurLoop->getHeader() == BB;
471 
472  for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
473  Instruction &I = *II++;
474  // Try constant folding this instruction. If all the operands are
475  // constants, it is technically hoistable, but it would be better to
476  // just fold it.
478  &I, I.getModule()->getDataLayout(), TLI)) {
479  LLVM_DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C
480  << '\n');
481  CurAST->copyValue(&I, C);
483  if (isInstructionTriviallyDead(&I, TLI)) {
484  CurAST->deleteValue(&I);
485  I.eraseFromParent();
486  }
487  Changed = true;
488  continue;
489  }
490 
491  // Try hoisting the instruction out to the preheader. We can only do
492  // this if all of the operands of the instruction are loop invariant and
493  // if it is safe to hoist the instruction.
494  //
495  if (CurLoop->hasLoopInvariantOperands(&I) &&
496  canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, true, ORE) &&
497  (IsMustExecute ||
499  I, DT, CurLoop, SafetyInfo, ORE,
500  CurLoop->getLoopPreheader()->getTerminator()))) {
501  hoist(I, DT, CurLoop, SafetyInfo, ORE);
502  Changed = true;
503  continue;
504  }
505 
506  // Attempt to remove floating point division out of the loop by
507  // converting it to a reciprocal multiplication.
508  if (I.getOpcode() == Instruction::FDiv &&
509  CurLoop->isLoopInvariant(I.getOperand(1)) &&
510  I.hasAllowReciprocal()) {
511  auto Divisor = I.getOperand(1);
512  auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
513  auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
514  ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
515  ReciprocalDivisor->insertBefore(&I);
516 
517  auto Product =
518  BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
519  Product->setFastMathFlags(I.getFastMathFlags());
520  Product->insertAfter(&I);
521  I.replaceAllUsesWith(Product);
522  I.eraseFromParent();
523 
524  hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
525  Changed = true;
526  continue;
527  }
528 
529  using namespace PatternMatch;
530  if (((I.use_empty() &&
531  match(&I, m_Intrinsic<Intrinsic::invariant_start>())) ||
532  isGuard(&I)) &&
533  IsMustExecute && IsMemoryNotModified &&
534  CurLoop->hasLoopInvariantOperands(&I)) {
535  hoist(I, DT, CurLoop, SafetyInfo, ORE);
536  Changed = true;
537  continue;
538  }
539 
540  if (IsMustExecute)
541  IsMustExecute = isGuaranteedToTransferExecutionToSuccessor(&I);
542  if (IsMemoryNotModified)
543  IsMemoryNotModified = !I.mayWriteToMemory();
544  }
545  }
546 
547  return Changed;
548 }
549 
550 // Return true if LI is invariant within scope of the loop. LI is invariant if
551 // CurLoop is dominated by an invariant.start representing the same memory
552 // location and size as the memory location LI loads from, and also the
553 // invariant.start has no uses.
555  Loop *CurLoop) {
556  Value *Addr = LI->getOperand(0);
557  const DataLayout &DL = LI->getModule()->getDataLayout();
558  const uint32_t LocSizeInBits = DL.getTypeSizeInBits(
559  cast<PointerType>(Addr->getType())->getElementType());
560 
561  // if the type is i8 addrspace(x)*, we know this is the type of
562  // llvm.invariant.start operand
563  auto *PtrInt8Ty = PointerType::get(Type::getInt8Ty(LI->getContext()),
564  LI->getPointerAddressSpace());
565  unsigned BitcastsVisited = 0;
566  // Look through bitcasts until we reach the i8* type (this is invariant.start
567  // operand type).
568  while (Addr->getType() != PtrInt8Ty) {
569  auto *BC = dyn_cast<BitCastInst>(Addr);
570  // Avoid traversing high number of bitcast uses.
571  if (++BitcastsVisited > MaxNumUsesTraversed || !BC)
572  return false;
573  Addr = BC->getOperand(0);
574  }
575 
576  unsigned UsesVisited = 0;
577  // Traverse all uses of the load operand value, to see if invariant.start is
578  // one of the uses, and whether it dominates the load instruction.
579  for (auto *U : Addr->users()) {
580  // Avoid traversing for Load operand with high number of users.
581  if (++UsesVisited > MaxNumUsesTraversed)
582  return false;
584  // If there are escaping uses of invariant.start instruction, the load maybe
585  // non-invariant.
586  if (!II || II->getIntrinsicID() != Intrinsic::invariant_start ||
587  !II->use_empty())
588  continue;
589  unsigned InvariantSizeInBits =
590  cast<ConstantInt>(II->getArgOperand(0))->getSExtValue() * 8;
591  // Confirm the invariant.start location size contains the load operand size
592  // in bits. Also, the invariant.start should dominate the load, and we
593  // should not hoist the load out of a loop that contains this dominating
594  // invariant.start.
595  if (LocSizeInBits <= InvariantSizeInBits &&
596  DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
597  return true;
598  }
599 
600  return false;
601 }
602 
603 namespace {
604 /// Return true if-and-only-if we know how to (mechanically) both hoist and
605 /// sink a given instruction out of a loop. Does not address legality
606 /// concerns such as aliasing or speculation safety.
607 bool isHoistableAndSinkableInst(Instruction &I) {
608  // Only these instructions are hoistable/sinkable.
609  return (isa<LoadInst>(I) || isa<StoreInst>(I) ||
610  isa<CallInst>(I) || isa<FenceInst>(I) ||
611  isa<BinaryOperator>(I) || isa<CastInst>(I) ||
612  isa<SelectInst>(I) || isa<GetElementPtrInst>(I) ||
613  isa<CmpInst>(I) || isa<InsertElementInst>(I) ||
614  isa<ExtractElementInst>(I) || isa<ShuffleVectorInst>(I) ||
615  isa<ExtractValueInst>(I) || isa<InsertValueInst>(I));
616 }
617 /// Return true if all of the alias sets within this AST are known not to
618 /// contain a Mod.
619 bool isReadOnly(AliasSetTracker *CurAST) {
620  for (AliasSet &AS : *CurAST) {
621  if (!AS.isForwardingAliasSet() && AS.isMod()) {
622  return false;
623  }
624  }
625  return true;
626 }
627 }
628 
630  Loop *CurLoop, AliasSetTracker *CurAST,
631  bool TargetExecutesOncePerLoop,
633  // If we don't understand the instruction, bail early.
634  if (!isHoistableAndSinkableInst(I))
635  return false;
636 
637  // Loads have extra constraints we have to verify before we can hoist them.
638  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
639  if (!LI->isUnordered())
640  return false; // Don't sink/hoist volatile or ordered atomic loads!
641 
642  // Loads from constant memory are always safe to move, even if they end up
643  // in the same alias set as something that ends up being modified.
644  if (AA->pointsToConstantMemory(LI->getOperand(0)))
645  return true;
646  if (LI->getMetadata(LLVMContext::MD_invariant_load))
647  return true;
648 
649  if (LI->isAtomic() && !TargetExecutesOncePerLoop)
650  return false; // Don't risk duplicating unordered loads
651 
652  // This checks for an invariant.start dominating the load.
653  if (isLoadInvariantInLoop(LI, DT, CurLoop))
654  return true;
655 
656  bool Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI),
657  CurAST, CurLoop, AA);
658  // Check loop-invariant address because this may also be a sinkable load
659  // whose address is not necessarily loop-invariant.
660  if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
661  ORE->emit([&]() {
663  DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
664  << "failed to move load with loop-invariant address "
665  "because the loop may invalidate its value";
666  });
667 
668  return !Invalidated;
669  } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
670  // Don't sink or hoist dbg info; it's legal, but not useful.
671  if (isa<DbgInfoIntrinsic>(I))
672  return false;
673 
674  // Don't sink calls which can throw.
675  if (CI->mayThrow())
676  return false;
677 
678  using namespace PatternMatch;
679  if (match(CI, m_Intrinsic<Intrinsic::assume>()))
680  // Assumes don't actually alias anything or throw
681  return true;
682 
683  // Handle simple cases by querying alias analysis.
684  FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
685  if (Behavior == FMRB_DoesNotAccessMemory)
686  return true;
687  if (AliasAnalysis::onlyReadsMemory(Behavior)) {
688  // A readonly argmemonly function only reads from memory pointed to by
689  // it's arguments with arbitrary offsets. If we can prove there are no
690  // writes to this memory in the loop, we can hoist or sink.
692  // TODO: expand to writeable arguments
693  for (Value *Op : CI->arg_operands())
694  if (Op->getType()->isPointerTy() &&
697  CurAST, CurLoop, AA))
698  return false;
699  return true;
700  }
701 
702  // If this call only reads from memory and there are no writes to memory
703  // in the loop, we can hoist or sink the call as appropriate.
704  if (isReadOnly(CurAST))
705  return true;
706  }
707 
708  // FIXME: This should use mod/ref information to see if we can hoist or
709  // sink the call.
710 
711  return false;
712  } else if (auto *FI = dyn_cast<FenceInst>(&I)) {
713  // Fences alias (most) everything to provide ordering. For the moment,
714  // just give up if there are any other memory operations in the loop.
715  auto Begin = CurAST->begin();
716  assert(Begin != CurAST->end() && "must contain FI");
717  if (std::next(Begin) != CurAST->end())
718  // constant memory for instance, TODO: handle better
719  return false;
720  auto *UniqueI = Begin->getUniqueInstruction();
721  if (!UniqueI)
722  // other memory op, give up
723  return false;
724  (void)FI; //suppress unused variable warning
725  assert(UniqueI == FI && "AS must contain FI");
726  return true;
727  } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
728  if (!SI->isUnordered())
729  return false; // Don't sink/hoist volatile or ordered atomic store!
730 
731  // We can only hoist a store that we can prove writes a value which is not
732  // read or overwritten within the loop. For those cases, we fallback to
733  // load store promotion instead. TODO: We can extend this to cases where
734  // there is exactly one write to the location and that write dominates an
735  // arbitrary number of reads in the loop.
736  auto &AS = CurAST->getAliasSetFor(MemoryLocation::get(SI));
737 
738  if (AS.isRef() || !AS.isMustAlias())
739  // Quick exit test, handled by the full path below as well.
740  return false;
741  auto *UniqueI = AS.getUniqueInstruction();
742  if (!UniqueI)
743  // other memory op, give up
744  return false;
745  assert(UniqueI == SI && "AS must contain SI");
746  return true;
747  }
748 
749  assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
750 
751  // We've established mechanical ability and aliasing, it's up to the caller
752  // to check fault safety
753  return true;
754 }
755 
756 /// Returns true if a PHINode is a trivially replaceable with an
757 /// Instruction.
758 /// This is true when all incoming values are that instruction.
759 /// This pattern occurs most often with LCSSA PHI nodes.
760 ///
761 static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I) {
762  for (const Value *IncValue : PN.incoming_values())
763  if (IncValue != &I)
764  return false;
765 
766  return true;
767 }
768 
769 /// Return true if the instruction is free in the loop.
770 static bool isFreeInLoop(const Instruction &I, const Loop *CurLoop,
771  const TargetTransformInfo *TTI) {
772 
773  if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I)) {
775  return false;
776  // For a GEP, we cannot simply use getUserCost because currently it
777  // optimistically assume that a GEP will fold into addressing mode
778  // regardless of its users.
779  const BasicBlock *BB = GEP->getParent();
780  for (const User *U : GEP->users()) {
781  const Instruction *UI = cast<Instruction>(U);
782  if (CurLoop->contains(UI) &&
783  (BB != UI->getParent() ||
784  (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
785  return false;
786  }
787  return true;
788  } else
789  return TTI->getUserCost(&I) == TargetTransformInfo::TCC_Free;
790 }
791 
792 /// Return true if the only users of this instruction are outside of
793 /// the loop. If this is true, we can sink the instruction to the exit
794 /// blocks of the loop.
795 ///
796 /// We also return true if the instruction could be folded away in lowering.
797 /// (e.g., a GEP can be folded into a load as an addressing mode in the loop).
798 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
799  const LoopSafetyInfo *SafetyInfo,
800  TargetTransformInfo *TTI, bool &FreeInLoop) {
801  const auto &BlockColors = SafetyInfo->BlockColors;
802  bool IsFree = isFreeInLoop(I, CurLoop, TTI);
803  for (const User *U : I.users()) {
804  const Instruction *UI = cast<Instruction>(U);
805  if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
806  const BasicBlock *BB = PN->getParent();
807  // We cannot sink uses in catchswitches.
808  if (isa<CatchSwitchInst>(BB->getTerminator()))
809  return false;
810 
811  // We need to sink a callsite to a unique funclet. Avoid sinking if the
812  // phi use is too muddled.
813  if (isa<CallInst>(I))
814  if (!BlockColors.empty() &&
815  BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
816  return false;
817  }
818 
819  if (CurLoop->contains(UI)) {
820  if (IsFree) {
821  FreeInLoop = true;
822  continue;
823  }
824  return false;
825  }
826  }
827  return true;
828 }
829 
830 static Instruction *
832  const LoopInfo *LI,
833  const LoopSafetyInfo *SafetyInfo) {
834  Instruction *New;
835  if (auto *CI = dyn_cast<CallInst>(&I)) {
836  const auto &BlockColors = SafetyInfo->BlockColors;
837 
838  // Sinking call-sites need to be handled differently from other
839  // instructions. The cloned call-site needs a funclet bundle operand
840  // appropriate for it's location in the CFG.
842  for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
843  BundleIdx != BundleEnd; ++BundleIdx) {
844  OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
845  if (Bundle.getTagID() == LLVMContext::OB_funclet)
846  continue;
847 
848  OpBundles.emplace_back(Bundle);
849  }
850 
851  if (!BlockColors.empty()) {
852  const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
853  assert(CV.size() == 1 && "non-unique color for exit block!");
854  BasicBlock *BBColor = CV.front();
855  Instruction *EHPad = BBColor->getFirstNonPHI();
856  if (EHPad->isEHPad())
857  OpBundles.emplace_back("funclet", EHPad);
858  }
859 
860  New = CallInst::Create(CI, OpBundles);
861  } else {
862  New = I.clone();
863  }
864 
865  ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
866  if (!I.getName().empty())
867  New->setName(I.getName() + ".le");
868 
869  // Build LCSSA PHI nodes for any in-loop operands. Note that this is
870  // particularly cheap because we can rip off the PHI node that we're
871  // replacing for the number and blocks of the predecessors.
872  // OPT: If this shows up in a profile, we can instead finish sinking all
873  // invariant instructions, and then walk their operands to re-establish
874  // LCSSA. That will eliminate creating PHI nodes just to nuke them when
875  // sinking bottom-up.
876  for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
877  ++OI)
878  if (Instruction *OInst = dyn_cast<Instruction>(*OI))
879  if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
880  if (!OLoop->contains(&PN)) {
881  PHINode *OpPN =
882  PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
883  OInst->getName() + ".lcssa", &ExitBlock.front());
884  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
885  OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
886  *OI = OpPN;
887  }
888  return New;
889 }
890 
892  PHINode *TPN, Instruction *I, LoopInfo *LI,
894  const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop) {
895  assert(isTriviallyReplaceablePHI(*TPN, *I) &&
896  "Expect only trivially replaceable PHI");
897  BasicBlock *ExitBlock = TPN->getParent();
898  Instruction *New;
899  auto It = SunkCopies.find(ExitBlock);
900  if (It != SunkCopies.end())
901  New = It->second;
902  else
903  New = SunkCopies[ExitBlock] =
904  CloneInstructionInExitBlock(*I, *ExitBlock, *TPN, LI, SafetyInfo);
905  return New;
906 }
907 
908 static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo) {
909  BasicBlock *BB = PN->getParent();
910  if (!BB->canSplitPredecessors())
911  return false;
912  // It's not impossible to split EHPad blocks, but if BlockColors already exist
913  // it require updating BlockColors for all offspring blocks accordingly. By
914  // skipping such corner case, we can make updating BlockColors after splitting
915  // predecessor fairly simple.
916  if (!SafetyInfo->BlockColors.empty() && BB->getFirstNonPHI()->isEHPad())
917  return false;
918  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
919  BasicBlock *BBPred = *PI;
920  if (isa<IndirectBrInst>(BBPred->getTerminator()))
921  return false;
922  }
923  return true;
924 }
925 
927  LoopInfo *LI, const Loop *CurLoop,
928  LoopSafetyInfo *SafetyInfo) {
929 #ifndef NDEBUG
931  CurLoop->getUniqueExitBlocks(ExitBlocks);
932  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
933  ExitBlocks.end());
934 #endif
935  BasicBlock *ExitBB = PN->getParent();
936  assert(ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block.");
937 
938  // Split predecessors of the loop exit to make instructions in the loop are
939  // exposed to exit blocks through trivially replaceable PHIs while keeping the
940  // loop in the canonical form where each predecessor of each exit block should
941  // be contained within the loop. For example, this will convert the loop below
942  // from
943  //
944  // LB1:
945  // %v1 =
946  // br %LE, %LB2
947  // LB2:
948  // %v2 =
949  // br %LE, %LB1
950  // LE:
951  // %p = phi [%v1, %LB1], [%v2, %LB2] <-- non-trivially replaceable
952  //
953  // to
954  //
955  // LB1:
956  // %v1 =
957  // br %LE.split, %LB2
958  // LB2:
959  // %v2 =
960  // br %LE.split2, %LB1
961  // LE.split:
962  // %p1 = phi [%v1, %LB1] <-- trivially replaceable
963  // br %LE
964  // LE.split2:
965  // %p2 = phi [%v2, %LB2] <-- trivially replaceable
966  // br %LE
967  // LE:
968  // %p = phi [%p1, %LE.split], [%p2, %LE.split2]
969  //
970  auto &BlockColors = SafetyInfo->BlockColors;
971  SmallSetVector<BasicBlock *, 8> PredBBs(pred_begin(ExitBB), pred_end(ExitBB));
972  while (!PredBBs.empty()) {
973  BasicBlock *PredBB = *PredBBs.begin();
974  assert(CurLoop->contains(PredBB) &&
975  "Expect all predecessors are in the loop");
976  if (PN->getBasicBlockIndex(PredBB) >= 0) {
978  ExitBB, PredBB, ".split.loop.exit", DT, LI, nullptr, true);
979  // Since we do not allow splitting EH-block with BlockColors in
980  // canSplitPredecessors(), we can simply assign predecessor's color to
981  // the new block.
982  if (!BlockColors.empty()) {
983  // Grab a reference to the ColorVector to be inserted before getting the
984  // reference to the vector we are copying because inserting the new
985  // element in BlockColors might cause the map to be reallocated.
986  ColorVector &ColorsForNewBlock = BlockColors[NewPred];
987  ColorVector &ColorsForOldBlock = BlockColors[PredBB];
988  ColorsForNewBlock = ColorsForOldBlock;
989  }
990  }
991  PredBBs.remove(PredBB);
992  }
993 }
994 
995 /// When an instruction is found to only be used outside of the loop, this
996 /// function moves it to the exit blocks and patches up SSA form as needed.
997 /// This method is guaranteed to remove the original instruction from its
998 /// position, and may either delete it or move it to outside of the loop.
999 ///
1000 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
1001  const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
1002  OptimizationRemarkEmitter *ORE, bool FreeInLoop) {
1003  LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
1004  ORE->emit([&]() {
1005  return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
1006  << "sinking " << ore::NV("Inst", &I);
1007  });
1008  bool Changed = false;
1009  if (isa<LoadInst>(I))
1010  ++NumMovedLoads;
1011  else if (isa<CallInst>(I))
1012  ++NumMovedCalls;
1013  ++NumSunk;
1014 
1015  // Iterate over users to be ready for actual sinking. Replace users via
1016  // unrechable blocks with undef and make all user PHIs trivially replcable.
1017  SmallPtrSet<Instruction *, 8> VisitedUsers;
1018  for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
1019  auto *User = cast<Instruction>(*UI);
1020  Use &U = UI.getUse();
1021  ++UI;
1022 
1023  if (VisitedUsers.count(User) || CurLoop->contains(User))
1024  continue;
1025 
1026  if (!DT->isReachableFromEntry(User->getParent())) {
1027  U = UndefValue::get(I.getType());
1028  Changed = true;
1029  continue;
1030  }
1031 
1032  // The user must be a PHI node.
1033  PHINode *PN = cast<PHINode>(User);
1034 
1035  // Surprisingly, instructions can be used outside of loops without any
1036  // exits. This can only happen in PHI nodes if the incoming block is
1037  // unreachable.
1038  BasicBlock *BB = PN->getIncomingBlock(U);
1039  if (!DT->isReachableFromEntry(BB)) {
1040  U = UndefValue::get(I.getType());
1041  Changed = true;
1042  continue;
1043  }
1044 
1045  VisitedUsers.insert(PN);
1046  if (isTriviallyReplaceablePHI(*PN, I))
1047  continue;
1048 
1049  if (!canSplitPredecessors(PN, SafetyInfo))
1050  return Changed;
1051 
1052  // Split predecessors of the PHI so that we can make users trivially
1053  // replaceable.
1054  splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo);
1055 
1056  // Should rebuild the iterators, as they may be invalidated by
1057  // splitPredecessorsOfLoopExit().
1058  UI = I.user_begin();
1059  UE = I.user_end();
1060  }
1061 
1062  if (VisitedUsers.empty())
1063  return Changed;
1064 
1065 #ifndef NDEBUG
1066  SmallVector<BasicBlock *, 32> ExitBlocks;
1067  CurLoop->getUniqueExitBlocks(ExitBlocks);
1068  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1069  ExitBlocks.end());
1070 #endif
1071 
1072  // Clones of this instruction. Don't create more than one per exit block!
1074 
1075  // If this instruction is only used outside of the loop, then all users are
1076  // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
1077  // the instruction.
1079  for (auto *UI : Users) {
1080  auto *User = cast<Instruction>(UI);
1081 
1082  if (CurLoop->contains(User))
1083  continue;
1084 
1085  PHINode *PN = cast<PHINode>(User);
1086  assert(ExitBlockSet.count(PN->getParent()) &&
1087  "The LCSSA PHI is not in an exit block!");
1088  // The PHI must be trivially replaceable.
1089  Instruction *New = sinkThroughTriviallyReplaceablePHI(PN, &I, LI, SunkCopies,
1090  SafetyInfo, CurLoop);
1091  PN->replaceAllUsesWith(New);
1092  PN->eraseFromParent();
1093  Changed = true;
1094  }
1095  return Changed;
1096 }
1097 
1098 /// When an instruction is found to only use loop invariant operands that
1099 /// is safe to hoist, this instruction is called to do the dirty work.
1100 ///
1101 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
1102  LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) {
1103  auto *Preheader = CurLoop->getLoopPreheader();
1104  LLVM_DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
1105  << "\n");
1106  ORE->emit([&]() {
1107  return OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting "
1108  << ore::NV("Inst", &I);
1109  });
1110 
1111  // Metadata can be dependent on conditions we are hoisting above.
1112  // Conservatively strip all metadata on the instruction unless we were
1113  // guaranteed to execute I if we entered the loop, in which case the metadata
1114  // is valid in the loop preheader.
1115  if (I.hasMetadataOtherThanDebugLoc() &&
1116  // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
1117  // time in isGuaranteedToExecute if we don't actually have anything to
1118  // drop. It is a compile time optimization, not required for correctness.
1119  !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
1121 
1122  // Move the new node to the Preheader, before its terminator.
1123  I.moveBefore(Preheader->getTerminator());
1124 
1125  // Do not retain debug locations when we are moving instructions to different
1126  // basic blocks, because we want to avoid jumpy line tables. Calls, however,
1127  // need to retain their debug locs because they may be inlined.
1128  // FIXME: How do we retain source locations without causing poor debugging
1129  // behavior?
1130  if (!isa<CallInst>(I))
1131  I.setDebugLoc(DebugLoc());
1132 
1133  if (isa<LoadInst>(I))
1134  ++NumMovedLoads;
1135  else if (isa<CallInst>(I))
1136  ++NumMovedCalls;
1137  ++NumHoisted;
1138 }
1139 
1140 /// Only sink or hoist an instruction if it is not a trapping instruction,
1141 /// or if the instruction is known not to trap when moved to the preheader.
1142 /// or if it is a trapping instruction and is guaranteed to execute.
1144  const DominatorTree *DT,
1145  const Loop *CurLoop,
1146  const LoopSafetyInfo *SafetyInfo,
1148  const Instruction *CtxI) {
1149  if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
1150  return true;
1151 
1152  bool GuaranteedToExecute =
1153  isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
1154 
1155  if (!GuaranteedToExecute) {
1156  auto *LI = dyn_cast<LoadInst>(&Inst);
1157  if (LI && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1158  ORE->emit([&]() {
1159  return OptimizationRemarkMissed(
1160  DEBUG_TYPE, "LoadWithLoopInvariantAddressCondExecuted", LI)
1161  << "failed to hoist load with loop-invariant address "
1162  "because load is conditionally executed";
1163  });
1164  }
1165 
1166  return GuaranteedToExecute;
1167 }
1168 
1169 namespace {
1170 class LoopPromoter : public LoadAndStorePromoter {
1171  Value *SomePtr; // Designated pointer to store to.
1172  const SmallSetVector<Value *, 8> &PointerMustAliases;
1173  SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
1174  SmallVectorImpl<Instruction *> &LoopInsertPts;
1175  PredIteratorCache &PredCache;
1176  AliasSetTracker &AST;
1177  LoopInfo &LI;
1178  DebugLoc DL;
1179  int Alignment;
1180  bool UnorderedAtomic;
1181  AAMDNodes AATags;
1182 
1183  Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
1184  if (Instruction *I = dyn_cast<Instruction>(V))
1185  if (Loop *L = LI.getLoopFor(I->getParent()))
1186  if (!L->contains(BB)) {
1187  // We need to create an LCSSA PHI node for the incoming value and
1188  // store that.
1189  PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
1190  I->getName() + ".lcssa", &BB->front());
1191  for (BasicBlock *Pred : PredCache.get(BB))
1192  PN->addIncoming(I, Pred);
1193  return PN;
1194  }
1195  return V;
1196  }
1197 
1198 public:
1199  LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
1200  const SmallSetVector<Value *, 8> &PMA,
1203  AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
1204  bool UnorderedAtomic, const AAMDNodes &AATags)
1205  : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
1206  LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
1207  LI(li), DL(std::move(dl)), Alignment(alignment),
1208  UnorderedAtomic(UnorderedAtomic), AATags(AATags) {}
1209 
1210  bool isInstInList(Instruction *I,
1211  const SmallVectorImpl<Instruction *> &) const override {
1212  Value *Ptr;
1213  if (LoadInst *LI = dyn_cast<LoadInst>(I))
1214  Ptr = LI->getOperand(0);
1215  else
1216  Ptr = cast<StoreInst>(I)->getPointerOperand();
1217  return PointerMustAliases.count(Ptr);
1218  }
1219 
1220  void doExtraRewritesBeforeFinalDeletion() const override {
1221  // Insert stores after in the loop exit blocks. Each exit block gets a
1222  // store of the live-out values that feed them. Since we've already told
1223  // the SSA updater about the defs in the loop and the preheader
1224  // definition, it is all set and we can start using it.
1225  for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
1226  BasicBlock *ExitBlock = LoopExitBlocks[i];
1227  Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
1228  LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1229  Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1230  Instruction *InsertPos = LoopInsertPts[i];
1231  StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
1232  if (UnorderedAtomic)
1234  NewSI->setAlignment(Alignment);
1235  NewSI->setDebugLoc(DL);
1236  if (AATags)
1237  NewSI->setAAMetadata(AATags);
1238  }
1239  }
1240 
1241  void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
1242  // Update alias analysis.
1243  AST.copyValue(LI, V);
1244  }
1245  void instructionDeleted(Instruction *I) const override { AST.deleteValue(I); }
1246 };
1247 
1248 
1249 /// Return true iff we can prove that a caller of this function can not inspect
1250 /// the contents of the provided object in a well defined program.
1251 bool isKnownNonEscaping(Value *Object, const TargetLibraryInfo *TLI) {
1252  if (isa<AllocaInst>(Object))
1253  // Since the alloca goes out of scope, we know the caller can't retain a
1254  // reference to it and be well defined. Thus, we don't need to check for
1255  // capture.
1256  return true;
1257 
1258  // For all other objects we need to know that the caller can't possibly
1259  // have gotten a reference to the object. There are two components of
1260  // that:
1261  // 1) Object can't be escaped by this function. This is what
1262  // PointerMayBeCaptured checks.
1263  // 2) Object can't have been captured at definition site. For this, we
1264  // need to know the return value is noalias. At the moment, we use a
1265  // weaker condition and handle only AllocLikeFunctions (which are
1266  // known to be noalias). TODO
1267  return isAllocLikeFn(Object, TLI) &&
1268  !PointerMayBeCaptured(Object, true, true);
1269 }
1270 
1271 } // namespace
1272 
1273 /// Try to promote memory values to scalars by sinking stores out of the
1274 /// loop and moving loads to before the loop. We do this by looping over
1275 /// the stores in the loop, looking for stores to Must pointers which are
1276 /// loop invariant.
1277 ///
1279  const SmallSetVector<Value *, 8> &PointerMustAliases,
1280  SmallVectorImpl<BasicBlock *> &ExitBlocks,
1282  LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
1283  Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
1285  // Verify inputs.
1286  assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
1287  CurAST != nullptr && SafetyInfo != nullptr &&
1288  "Unexpected Input to promoteLoopAccessesToScalars");
1289 
1290  Value *SomePtr = *PointerMustAliases.begin();
1291  BasicBlock *Preheader = CurLoop->getLoopPreheader();
1292 
1293  // It is not safe to promote a load/store from the loop if the load/store is
1294  // conditional. For example, turning:
1295  //
1296  // for () { if (c) *P += 1; }
1297  //
1298  // into:
1299  //
1300  // tmp = *P; for () { if (c) tmp +=1; } *P = tmp;
1301  //
1302  // is not safe, because *P may only be valid to access if 'c' is true.
1303  //
1304  // The safety property divides into two parts:
1305  // p1) The memory may not be dereferenceable on entry to the loop. In this
1306  // case, we can't insert the required load in the preheader.
1307  // p2) The memory model does not allow us to insert a store along any dynamic
1308  // path which did not originally have one.
1309  //
1310  // If at least one store is guaranteed to execute, both properties are
1311  // satisfied, and promotion is legal.
1312  //
1313  // This, however, is not a necessary condition. Even if no store/load is
1314  // guaranteed to execute, we can still establish these properties.
1315  // We can establish (p1) by proving that hoisting the load into the preheader
1316  // is safe (i.e. proving dereferenceability on all paths through the loop). We
1317  // can use any access within the alias set to prove dereferenceability,
1318  // since they're all must alias.
1319  //
1320  // There are two ways establish (p2):
1321  // a) Prove the location is thread-local. In this case the memory model
1322  // requirement does not apply, and stores are safe to insert.
1323  // b) Prove a store dominates every exit block. In this case, if an exit
1324  // blocks is reached, the original dynamic path would have taken us through
1325  // the store, so inserting a store into the exit block is safe. Note that this
1326  // is different from the store being guaranteed to execute. For instance,
1327  // if an exception is thrown on the first iteration of the loop, the original
1328  // store is never executed, but the exit blocks are not executed either.
1329 
1330  bool DereferenceableInPH = false;
1331  bool SafeToInsertStore = false;
1332 
1334 
1335  // We start with an alignment of one and try to find instructions that allow
1336  // us to prove better alignment.
1337  unsigned Alignment = 1;
1338  // Keep track of which types of access we see
1339  bool SawUnorderedAtomic = false;
1340  bool SawNotAtomic = false;
1341  AAMDNodes AATags;
1342 
1343  const DataLayout &MDL = Preheader->getModule()->getDataLayout();
1344 
1345  bool IsKnownThreadLocalObject = false;
1346  if (SafetyInfo->anyBlockMayThrow()) {
1347  // If a loop can throw, we have to insert a store along each unwind edge.
1348  // That said, we can't actually make the unwind edge explicit. Therefore,
1349  // we have to prove that the store is dead along the unwind edge. We do
1350  // this by proving that the caller can't have a reference to the object
1351  // after return and thus can't possibly load from the object.
1352  Value *Object = GetUnderlyingObject(SomePtr, MDL);
1353  if (!isKnownNonEscaping(Object, TLI))
1354  return false;
1355  // Subtlety: Alloca's aren't visible to callers, but *are* potentially
1356  // visible to other threads if captured and used during their lifetimes.
1357  IsKnownThreadLocalObject = !isa<AllocaInst>(Object);
1358  }
1359 
1360  // Check that all of the pointers in the alias set have the same type. We
1361  // cannot (yet) promote a memory location that is loaded and stored in
1362  // different sizes. While we are at it, collect alignment and AA info.
1363  for (Value *ASIV : PointerMustAliases) {
1364  // Check that all of the pointers in the alias set have the same type. We
1365  // cannot (yet) promote a memory location that is loaded and stored in
1366  // different sizes.
1367  if (SomePtr->getType() != ASIV->getType())
1368  return false;
1369 
1370  for (User *U : ASIV->users()) {
1371  // Ignore instructions that are outside the loop.
1372  Instruction *UI = dyn_cast<Instruction>(U);
1373  if (!UI || !CurLoop->contains(UI))
1374  continue;
1375 
1376  // If there is an non-load/store instruction in the loop, we can't promote
1377  // it.
1378  if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
1379  if (!Load->isUnordered())
1380  return false;
1381 
1382  SawUnorderedAtomic |= Load->isAtomic();
1383  SawNotAtomic |= !Load->isAtomic();
1384 
1385  if (!DereferenceableInPH)
1386  DereferenceableInPH = isSafeToExecuteUnconditionally(
1387  *Load, DT, CurLoop, SafetyInfo, ORE, Preheader->getTerminator());
1388  } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
1389  // Stores *of* the pointer are not interesting, only stores *to* the
1390  // pointer.
1391  if (UI->getOperand(1) != ASIV)
1392  continue;
1393  if (!Store->isUnordered())
1394  return false;
1395 
1396  SawUnorderedAtomic |= Store->isAtomic();
1397  SawNotAtomic |= !Store->isAtomic();
1398 
1399  // If the store is guaranteed to execute, both properties are satisfied.
1400  // We may want to check if a store is guaranteed to execute even if we
1401  // already know that promotion is safe, since it may have higher
1402  // alignment than any other guaranteed stores, in which case we can
1403  // raise the alignment on the promoted store.
1404  unsigned InstAlignment = Store->getAlignment();
1405  if (!InstAlignment)
1406  InstAlignment =
1407  MDL.getABITypeAlignment(Store->getValueOperand()->getType());
1408 
1409  if (!DereferenceableInPH || !SafeToInsertStore ||
1410  (InstAlignment > Alignment)) {
1411  if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
1412  DereferenceableInPH = true;
1413  SafeToInsertStore = true;
1414  Alignment = std::max(Alignment, InstAlignment);
1415  }
1416  }
1417 
1418  // If a store dominates all exit blocks, it is safe to sink.
1419  // As explained above, if an exit block was executed, a dominating
1420  // store must have been executed at least once, so we are not
1421  // introducing stores on paths that did not have them.
1422  // Note that this only looks at explicit exit blocks. If we ever
1423  // start sinking stores into unwind edges (see above), this will break.
1424  if (!SafeToInsertStore)
1425  SafeToInsertStore = llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
1426  return DT->dominates(Store->getParent(), Exit);
1427  });
1428 
1429  // If the store is not guaranteed to execute, we may still get
1430  // deref info through it.
1431  if (!DereferenceableInPH) {
1432  DereferenceableInPH = isDereferenceableAndAlignedPointer(
1433  Store->getPointerOperand(), Store->getAlignment(), MDL,
1434  Preheader->getTerminator(), DT);
1435  }
1436  } else
1437  return false; // Not a load or store.
1438 
1439  // Merge the AA tags.
1440  if (LoopUses.empty()) {
1441  // On the first load/store, just take its AA tags.
1442  UI->getAAMetadata(AATags);
1443  } else if (AATags) {
1444  UI->getAAMetadata(AATags, /* Merge = */ true);
1445  }
1446 
1447  LoopUses.push_back(UI);
1448  }
1449  }
1450 
1451  // If we found both an unordered atomic instruction and a non-atomic memory
1452  // access, bail. We can't blindly promote non-atomic to atomic since we
1453  // might not be able to lower the result. We can't downgrade since that
1454  // would violate memory model. Also, align 0 is an error for atomics.
1455  if (SawUnorderedAtomic && SawNotAtomic)
1456  return false;
1457 
1458  // If we couldn't prove we can hoist the load, bail.
1459  if (!DereferenceableInPH)
1460  return false;
1461 
1462  // We know we can hoist the load, but don't have a guaranteed store.
1463  // Check whether the location is thread-local. If it is, then we can insert
1464  // stores along paths which originally didn't have them without violating the
1465  // memory model.
1466  if (!SafeToInsertStore) {
1467  if (IsKnownThreadLocalObject)
1468  SafeToInsertStore = true;
1469  else {
1470  Value *Object = GetUnderlyingObject(SomePtr, MDL);
1471  SafeToInsertStore =
1472  (isAllocLikeFn(Object, TLI) || isa<AllocaInst>(Object)) &&
1473  !PointerMayBeCaptured(Object, true, true);
1474  }
1475  }
1476 
1477  // If we've still failed to prove we can sink the store, give up.
1478  if (!SafeToInsertStore)
1479  return false;
1480 
1481  // Otherwise, this is safe to promote, lets do it!
1482  LLVM_DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr
1483  << '\n');
1484  ORE->emit([&]() {
1485  return OptimizationRemark(DEBUG_TYPE, "PromoteLoopAccessesToScalar",
1486  LoopUses[0])
1487  << "Moving accesses to memory location out of the loop";
1488  });
1489  ++NumPromoted;
1490 
1491  // Grab a debug location for the inserted loads/stores; given that the
1492  // inserted loads/stores have little relation to the original loads/stores,
1493  // this code just arbitrarily picks a location from one, since any debug
1494  // location is better than none.
1495  DebugLoc DL = LoopUses[0]->getDebugLoc();
1496 
1497  // We use the SSAUpdater interface to insert phi nodes as required.
1499  SSAUpdater SSA(&NewPHIs);
1500  LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
1501  InsertPts, PIC, *CurAST, *LI, DL, Alignment,
1502  SawUnorderedAtomic, AATags);
1503 
1504  // Set up the preheader to have a definition of the value. It is the live-out
1505  // value from the preheader that uses in the loop will use.
1506  LoadInst *PreheaderLoad = new LoadInst(
1507  SomePtr, SomePtr->getName() + ".promoted", Preheader->getTerminator());
1508  if (SawUnorderedAtomic)
1509  PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
1510  PreheaderLoad->setAlignment(Alignment);
1511  PreheaderLoad->setDebugLoc(DL);
1512  if (AATags)
1513  PreheaderLoad->setAAMetadata(AATags);
1514  SSA.AddAvailableValue(Preheader, PreheaderLoad);
1515 
1516  // Rewrite all the loads in the loop and remember all the definitions from
1517  // stores in the loop.
1518  Promoter.run(LoopUses);
1519 
1520  // If the SSAUpdater didn't use the load in the preheader, just zap it now.
1521  if (PreheaderLoad->use_empty())
1522  PreheaderLoad->eraseFromParent();
1523 
1524  return true;
1525 }
1526 
1527 /// Returns an owning pointer to an alias set which incorporates aliasing info
1528 /// from L and all subloops of L.
1529 /// FIXME: In new pass manager, there is no helper function to handle loop
1530 /// analysis such as cloneBasicBlockAnalysis, so the AST needs to be recomputed
1531 /// from scratch for every loop. Hook up with the helper functions when
1532 /// available in the new pass manager to avoid redundant computation.
1533 std::unique_ptr<AliasSetTracker>
1534 LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
1535  AliasAnalysis *AA) {
1536  std::unique_ptr<AliasSetTracker> CurAST;
1537  SmallVector<Loop *, 4> RecomputeLoops;
1538  for (Loop *InnerL : L->getSubLoops()) {
1539  auto MapI = LoopToAliasSetMap.find(InnerL);
1540  // If the AST for this inner loop is missing it may have been merged into
1541  // some other loop's AST and then that loop unrolled, and so we need to
1542  // recompute it.
1543  if (MapI == LoopToAliasSetMap.end()) {
1544  RecomputeLoops.push_back(InnerL);
1545  continue;
1546  }
1547  std::unique_ptr<AliasSetTracker> InnerAST = std::move(MapI->second);
1548 
1549  if (CurAST) {
1550  // What if InnerLoop was modified by other passes ?
1551  // Once we've incorporated the inner loop's AST into ours, we don't need
1552  // the subloop's anymore.
1553  CurAST->add(*InnerAST);
1554  } else {
1555  CurAST = std::move(InnerAST);
1556  }
1557  LoopToAliasSetMap.erase(MapI);
1558  }
1559  if (!CurAST)
1560  CurAST = make_unique<AliasSetTracker>(*AA);
1561 
1562  // Add everything from the sub loops that are no longer directly available.
1563  for (Loop *InnerL : RecomputeLoops)
1564  for (BasicBlock *BB : InnerL->blocks())
1565  CurAST->add(*BB);
1566 
1567  // And merge in this loop (without anything from inner loops).
1568  for (BasicBlock *BB : L->blocks())
1569  if (LI->getLoopFor(BB) == L)
1570  CurAST->add(*BB);
1571 
1572  return CurAST;
1573 }
1574 
1575 /// Simple analysis hook. Clone alias set info.
1576 ///
1577 void LegacyLICMPass::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
1578  Loop *L) {
1579  auto ASTIt = LICM.getLoopToAliasSetMap().find(L);
1580  if (ASTIt == LICM.getLoopToAliasSetMap().end())
1581  return;
1582 
1583  ASTIt->second->copyValue(From, To);
1584 }
1585 
1586 /// Simple Analysis hook. Delete value V from alias set
1587 ///
1588 void LegacyLICMPass::deleteAnalysisValue(Value *V, Loop *L) {
1589  auto ASTIt = LICM.getLoopToAliasSetMap().find(L);
1590  if (ASTIt == LICM.getLoopToAliasSetMap().end())
1591  return;
1592 
1593  ASTIt->second->deleteValue(V);
1594 }
1595 
1596 /// Simple Analysis hook. Delete value L from alias set map.
1597 ///
1598 void LegacyLICMPass::deleteAnalysisLoop(Loop *L) {
1599  if (!LICM.getLoopToAliasSetMap().count(L))
1600  return;
1601 
1602  LICM.getLoopToAliasSetMap().erase(L);
1603 }
1604 
1606  AliasSetTracker *CurAST, Loop *CurLoop,
1607  AliasAnalysis *AA) {
1608  // First check to see if any of the basic blocks in CurLoop invalidate *V.
1609  bool isInvalidatedAccordingToAST = CurAST->getAliasSetFor(MemLoc).isMod();
1610 
1611  if (!isInvalidatedAccordingToAST || !LICMN2Theshold)
1612  return isInvalidatedAccordingToAST;
1613 
1614  // Check with a diagnostic analysis if we can refine the information above.
1615  // This is to identify the limitations of using the AST.
1616  // The alias set mechanism used by LICM has a major weakness in that it
1617  // combines all things which may alias into a single set *before* asking
1618  // modref questions. As a result, a single readonly call within a loop will
1619  // collapse all loads and stores into a single alias set and report
1620  // invalidation if the loop contains any store. For example, readonly calls
1621  // with deopt states have this form and create a general alias set with all
1622  // loads and stores. In order to get any LICM in loops containing possible
1623  // deopt states we need a more precise invalidation of checking the mod ref
1624  // info of each instruction within the loop and LI. This has a complexity of
1625  // O(N^2), so currently, it is used only as a diagnostic tool since the
1626  // default value of LICMN2Threshold is zero.
1627 
1628  // Don't look at nested loops.
1629  if (CurLoop->begin() != CurLoop->end())
1630  return true;
1631 
1632  int N = 0;
1633  for (BasicBlock *BB : CurLoop->getBlocks())
1634  for (Instruction &I : *BB) {
1635  if (N >= LICMN2Theshold) {
1636  LLVM_DEBUG(dbgs() << "Alasing N2 threshold exhausted for "
1637  << *(MemLoc.Ptr) << "\n");
1638  return true;
1639  }
1640  N++;
1641  auto Res = AA->getModRefInfo(&I, MemLoc);
1642  if (isModSet(Res)) {
1643  LLVM_DEBUG(dbgs() << "Aliasing failed on " << I << " for "
1644  << *(MemLoc.Ptr) << "\n");
1645  return true;
1646  }
1647  }
1648  LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n");
1649  return false;
1650 }
1651 
1652 /// Little predicate that returns true if the specified basic block is in
1653 /// a subloop of the current one, not the current one itself.
1654 ///
1655 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
1656  assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
1657  return LI->getLoopFor(BB) != CurLoop;
1658 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
bool canSplitPredecessors() const
Definition: BasicBlock.cpp:365
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I)
Returns true if a PHINode is a trivially replaceable with an Instruction.
Definition: LICM.cpp:761
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...
Value * getPointerOperand(Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
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:770
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:139
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.
const_iterator end() const
EltTy front() const
bool hasMetadataOtherThanDebugLoc() const
Return true if this instruction has metadata attached to it other than a debug location.
Definition: Instruction.h:211
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1199
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:86
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:177
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:243
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:174
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 mayWriteToMemory() const
Return true if this instruction may modify memory.
bool salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1609
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, bool TargetExecutesOncePerLoop, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
Definition: LICM.cpp:629
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:714
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:1042
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
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:770
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...
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
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:168
Hexagon Common GEP
iv Induction Variable Users
Definition: IVUsers.cpp:52
void reserve(size_type N)
Definition: SmallVector.h:376
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:300
op_iterator op_begin()
Definition: User.h:230
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:64
static bool pointerInvalidatedByLoop(MemoryLocation MemLoc, AliasSetTracker *CurAST, Loop *CurLoop, AliasAnalysis *AA)
Definition: LICM.cpp:1605
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
Loop Invariant Code Motion
Definition: LICM.cpp:245
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:344
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
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:134
ArrayRef< BasicBlock * > get(BasicBlock *BB)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:950
This is the interface for a SCEV-based alias analysis.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:364
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
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
virtual bool doFinalization(Module &)
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Definition: Pass.h:110
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
uint32_t getTagID() const
Return the tag of this operand bundle as an integer.
Definition: InstrTypes.h:1050
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:295
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:939
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:158
BlockT * getHeader() const
Definition: LoopInfo.h:100
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:251
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: ...
static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, 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:1101
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
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
Instruction * getUniqueInstruction()
If this alias set is known to contain a single instruction and only a single unique instruction...
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:66
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:126
An instruction for storing to memory.
Definition: Instructions.h:310
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:439
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:1278
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
Value * getOperand(unsigned i) const
Definition: User.h:170
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 forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
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 ...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:841
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, 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...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< int > LICMN2Theshold("licm-n2-threshold", cl::Hidden, cl::init(0), cl::desc("How many instruction to cross product using AA"))
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:189
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
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:218
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:304
void setAAMetadata(const AAMDNodes &N)
Sets the metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1265
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
size_t size(BasicBlock *BB) const
bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, AliasSetTracker *, LoopSafetyInfo *, OptimizationRemarkEmitter *ORE)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block...
Definition: LICM.cpp:374
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:276
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:371
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:558
Expected to fold away in lowering.
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
Diagnostic information for applied optimization remarks.
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:113
Pass * createLICMPass()
Definition: LICM.cpp:248
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:232
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:1049
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LICM.cpp:213
AliasSet & getAliasSetFor(const MemoryLocation &MemLoc)
Return the alias set which contains the specified memory location.
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo)
Definition: LICM.cpp:908
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
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:1392
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
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:554
size_t size() const
Definition: SmallVector.h:53
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
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:58
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
bool anyBlockMayThrow() const
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:29
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
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:329
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:76
BlockVerifier::State From
static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT, LoopInfo *LI, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo)
Definition: LICM.cpp:926
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
DenseMap< BasicBlock *, ColorVector > BlockColors
Definition: MustExecute.h:61
iterator end()
Definition: BasicBlock.h:266
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1154
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:847
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:249
Provides information about what library functions are available for the current target.
iterator begin() const
Definition: LoopInfo.h:142
unsigned getABITypeAlignment(Type *Ty) const
Returns the minimum ABI-required alignment for the specified type.
Definition: DataLayout.cpp:722
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:644
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:441
static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, TargetTransformInfo *TTI, bool &FreeInLoop)
Return true if the only users of this instruction are outside of the loop.
Definition: LICM.cpp:798
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...
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:684
unsigned getNumIncomingValues() const
Return the number of incoming edges.
bool isGuard(const User *U)
Returns true iff U has semantics of a guard.
Definition: GuardUtils.cpp:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
A lightweight accessor for an operand bundle meant to be passed around by value.
Definition: InstrTypes.h:1022
iterator_range< user_iterator > users()
Definition: Value.h:400
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:1143
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:560
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
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this store instruction.
Definition: Instructions.h:368
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
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:133
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
static Instruction * CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo)
Definition: LICM.cpp:831
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:652
int getUserCost(const User *U, ArrayRef< const Value *> Operands) const
Estimate the cost of a given IR user when lowered.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:149
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
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
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:73
user_iterator_impl< User > user_iterator
Definition: Value.h:369
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:128
licm
Definition: LICM.cpp:245
iterator end() const
Definition: LoopInfo.h:143
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
Captures loop safety information.
Definition: MustExecute.h:47
void computeLoopSafetyInfo(Loop *)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:33
const_iterator begin() const
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:227
bool empty() const
Definition: LoopInfo.h:146
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:280
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:1655
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:376
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
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:348
LLVM Value Representation.
Definition: Value.h:73
void setAlignment(unsigned Align)
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:87
void initializeLegacyLICMPassPass(PassRegistry &)
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:569
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
void getUniqueExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:100
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.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
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
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:138
#define LLVM_DEBUG(X)
Definition: Debug.h:123
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 (under the assumptio...
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:174
The optimization diagnostic interface.
static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, bool FreeInLoop)
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
Definition: LICM.cpp:1000
bool use_empty() const
Definition: Value.h:323
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:67
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.
user_iterator user_end()
Definition: Value.h:384
bool mayReadOrWriteMemory() const
Return true if this instruction may read or write memory.
Definition: Instruction.h:518
static Instruction * sinkThroughTriviallyReplaceablePHI(PHINode *TPN, Instruction *I, LoopInfo *LI, SmallDenseMap< BasicBlock *, Instruction *, 32 > &SunkCopies, const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop)
Definition: LICM.cpp:891