LLVM  9.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/SetOperations.h"
35 #include "llvm/ADT/Statistic.h"
43 #include "llvm/Analysis/Loads.h"
44 #include "llvm/Analysis/LoopInfo.h"
46 #include "llvm/Analysis/LoopPass.h"
55 #include "llvm/IR/CFG.h"
56 #include "llvm/IR/Constants.h"
57 #include "llvm/IR/DataLayout.h"
58 #include "llvm/IR/DerivedTypes.h"
59 #include "llvm/IR/Dominators.h"
60 #include "llvm/IR/Instructions.h"
61 #include "llvm/IR/IntrinsicInst.h"
62 #include "llvm/IR/LLVMContext.h"
63 #include "llvm/IR/Metadata.h"
64 #include "llvm/IR/PatternMatch.h"
67 #include "llvm/Support/Debug.h"
69 #include "llvm/Transforms/Scalar.h"
75 #include <algorithm>
76 #include <utility>
77 using namespace llvm;
78 
79 #define DEBUG_TYPE "licm"
80 
81 STATISTIC(NumCreatedBlocks, "Number of blocks created");
82 STATISTIC(NumClonedBranches, "Number of branches cloned");
83 STATISTIC(NumSunk, "Number of instructions sunk out of loop");
84 STATISTIC(NumHoisted, "Number of instructions hoisted out of loop");
85 STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
86 STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
87 STATISTIC(NumPromoted, "Number of memory locations promoted to registers");
88 
89 /// Memory promotion is enabled by default.
90 static cl::opt<bool>
91  DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
92  cl::desc("Disable memory promotion in LICM pass"));
93 
95  "licm-control-flow-hoisting", cl::Hidden, cl::init(false),
96  cl::desc("Enable control flow (and PHI) hoisting in LICM"));
97 
99  "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
100  cl::desc("Max num uses visited for identifying load "
101  "invariance in loop using invariant start (default = 8)"));
102 
103 // Default value of zero implies we use the regular alias set tracker mechanism
104 // instead of the cross product using AA to identify aliasing of the memory
105 // location we are interested in.
106 static cl::opt<int>
107 LICMN2Theshold("licm-n2-threshold", cl::Hidden, cl::init(0),
108  cl::desc("How many instruction to cross product using AA"));
109 
110 // Experimental option to allow imprecision in LICM (use MemorySSA cap) in
111 // pathological cases, in exchange for faster compile. This is to be removed
112 // if MemorySSA starts to address the same issue. This flag applies only when
113 // LICM uses MemorySSA instead on AliasSetTracker. When the flag is disabled
114 // (default), LICM calls MemorySSAWalker's getClobberingMemoryAccess, which
115 // gets perfect accuracy. When flag is enabled, LICM will call into MemorySSA's
116 // getDefiningAccess, which may not be precise, since optimizeUses is capped.
118  "enable-licm-cap", cl::init(false), cl::Hidden,
119  cl::desc("Enable imprecision in LICM (uses MemorySSA cap) in "
120  "pathological cases, in exchange for faster compile"));
121 
122 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
123 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
124  const LoopSafetyInfo *SafetyInfo,
125  TargetTransformInfo *TTI, bool &FreeInLoop);
126 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
127  BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
129 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
130  const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
132  bool FreeInLoop);
134  const DominatorTree *DT,
135  const Loop *CurLoop,
136  const LoopSafetyInfo *SafetyInfo,
138  const Instruction *CtxI = nullptr);
139 static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
140  AliasSetTracker *CurAST, Loop *CurLoop,
141  AliasAnalysis *AA);
143  Loop *CurLoop);
145  Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
146  const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU);
147 
148 static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
149  AliasSetTracker *AST, MemorySSAUpdater *MSSAU);
150 
151 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
152  ICFLoopSafetyInfo &SafetyInfo);
153 
154 namespace {
155 struct LoopInvariantCodeMotion {
157  bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
159  ScalarEvolution *SE, MemorySSA *MSSA,
160  OptimizationRemarkEmitter *ORE, bool DeleteAST);
161 
162  ASTrackerMapTy &getLoopToAliasSetMap() { return LoopToAliasSetMap; }
163 
164 private:
165  ASTrackerMapTy LoopToAliasSetMap;
166 
167  std::unique_ptr<AliasSetTracker>
168  collectAliasInfoForLoop(Loop *L, LoopInfo *LI, AliasAnalysis *AA);
169 };
170 
171 struct LegacyLICMPass : public LoopPass {
172  static char ID; // Pass identification, replacement for typeid
173  LegacyLICMPass() : LoopPass(ID) {
175  }
176 
177  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
178  if (skipLoop(L)) {
179  // If we have run LICM on a previous loop but now we are skipping
180  // (because we've hit the opt-bisect limit), we need to clear the
181  // loop alias information.
182  LICM.getLoopToAliasSetMap().clear();
183  return false;
184  }
185 
186  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
188  ? (&getAnalysis<MemorySSAWrapperPass>().getMSSA())
189  : nullptr;
190  // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
191  // pass. Function analyses need to be preserved across loop transformations
192  // but ORE cannot be preserved (see comment before the pass definition).
194  return LICM.runOnLoop(L,
195  &getAnalysis<AAResultsWrapperPass>().getAAResults(),
196  &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
197  &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
198  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
199  &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
200  *L->getHeader()->getParent()),
201  SE ? &SE->getSE() : nullptr, MSSA, &ORE, false);
202  }
203 
204  /// This transformation requires natural loop information & requires that
205  /// loop preheaders be inserted into the CFG...
206  ///
207  void getAnalysisUsage(AnalysisUsage &AU) const override {
214  }
217  }
218 
220 
221  bool doFinalization() override {
222  assert(LICM.getLoopToAliasSetMap().empty() &&
223  "Didn't free loop alias sets");
224  return false;
225  }
226 
227 private:
228  LoopInvariantCodeMotion LICM;
229 
230  /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info.
231  void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
232  Loop *L) override;
233 
234  /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
235  /// set.
236  void deleteAnalysisValue(Value *V, Loop *L) override;
237 
238  /// Simple Analysis hook. Delete loop L from alias set map.
239  void deleteAnalysisLoop(Loop *L) override;
240 };
241 } // namespace
242 
245  const auto &FAM =
246  AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
247  Function *F = L.getHeader()->getParent();
248 
249  auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
250  // FIXME: This should probably be optional rather than required.
251  if (!ORE)
252  report_fatal_error("LICM: OptimizationRemarkEmitterAnalysis not "
253  "cached at a higher level");
254 
255  LoopInvariantCodeMotion LICM;
256  if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.TTI, &AR.SE,
257  AR.MSSA, ORE, true))
258  return PreservedAnalyses::all();
259 
260  auto PA = getLoopPassPreservedAnalyses();
261 
262  PA.preserve<DominatorTreeAnalysis>();
263  PA.preserve<LoopAnalysis>();
264 
265  return PA;
266 }
267 
268 char LegacyLICMPass::ID = 0;
269 INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
270  false, false)
275 INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
276  false)
277 
278 Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
279 
280 /// Hoist expressions out of the specified loop. Note, alias info for inner
281 /// loop is not preserved so it is not a good idea to run LICM multiple
282 /// times on one loop.
283 /// We should delete AST for inner loops in the new pass manager to avoid
284 /// memory leak.
285 ///
286 bool LoopInvariantCodeMotion::runOnLoop(
287  Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
289  MemorySSA *MSSA, OptimizationRemarkEmitter *ORE, bool DeleteAST) {
290  bool Changed = false;
291 
292  assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
293 
294  std::unique_ptr<AliasSetTracker> CurAST;
295  std::unique_ptr<MemorySSAUpdater> MSSAU;
296  if (!MSSA) {
297  LLVM_DEBUG(dbgs() << "LICM: Using Alias Set Tracker.\n");
298  CurAST = collectAliasInfoForLoop(L, LI, AA);
299  } else {
300  LLVM_DEBUG(dbgs() << "LICM: Using MemorySSA. Promotion disabled.\n");
301  MSSAU = make_unique<MemorySSAUpdater>(MSSA);
302  }
303 
304  // Get the preheader block to move instructions into...
305  BasicBlock *Preheader = L->getLoopPreheader();
306 
307  // Compute loop safety information.
308  ICFLoopSafetyInfo SafetyInfo(DT);
309  SafetyInfo.computeLoopSafetyInfo(L);
310 
311  // We want to visit all of the instructions in this loop... that are not parts
312  // of our subloops (they have already had their invariants hoisted out of
313  // their loop, into this loop, so there is no need to process the BODIES of
314  // the subloops).
315  //
316  // Traverse the body of the loop in depth first order on the dominator tree so
317  // that we are guaranteed to see definitions before we see uses. This allows
318  // us to sink instructions in one pass, without iteration. After sinking
319  // instructions, we perform another pass to hoist them out of the loop.
320  //
321  if (L->hasDedicatedExits())
322  Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L,
323  CurAST.get(), MSSAU.get(), &SafetyInfo, ORE);
324  if (Preheader)
325  Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
326  CurAST.get(), MSSAU.get(), &SafetyInfo, ORE);
327 
328  // Now that all loop invariants have been removed from the loop, promote any
329  // memory references to scalars that we can.
330  // Don't sink stores from loops without dedicated block exits. Exits
331  // containing indirect branches are not transformed by loop simplify,
332  // make sure we catch that. An additional load may be generated in the
333  // preheader for SSA updater, so also avoid sinking when no preheader
334  // is available.
335  if (!DisablePromotion && Preheader && L->hasDedicatedExits()) {
336  // Figure out the loop exits and their insertion points
337  SmallVector<BasicBlock *, 8> ExitBlocks;
338  L->getUniqueExitBlocks(ExitBlocks);
339 
340  // We can't insert into a catchswitch.
341  bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
342  return isa<CatchSwitchInst>(Exit->getTerminator());
343  });
344 
345  if (!HasCatchSwitch) {
347  InsertPts.reserve(ExitBlocks.size());
348  for (BasicBlock *ExitBlock : ExitBlocks)
349  InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
350 
351  PredIteratorCache PIC;
352 
353  bool Promoted = false;
354 
355  if (CurAST.get()) {
356  // Loop over all of the alias sets in the tracker object.
357  for (AliasSet &AS : *CurAST) {
358  // We can promote this alias set if it has a store, if it is a "Must"
359  // alias set, if the pointer is loop invariant, and if we are not
360  // eliminating any volatile loads or stores.
361  if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
362  !L->isLoopInvariant(AS.begin()->getValue()))
363  continue;
364 
365  assert(
366  !AS.empty() &&
367  "Must alias set should have at least one pointer element in it!");
368 
369  SmallSetVector<Value *, 8> PointerMustAliases;
370  for (const auto &ASI : AS)
371  PointerMustAliases.insert(ASI.getValue());
372 
373  Promoted |= promoteLoopAccessesToScalars(
374  PointerMustAliases, ExitBlocks, InsertPts, PIC, LI, DT, TLI, L,
375  CurAST.get(), &SafetyInfo, ORE);
376  }
377  }
378  // FIXME: Promotion initially disabled when using MemorySSA.
379 
380  // Once we have promoted values across the loop body we have to
381  // recursively reform LCSSA as any nested loop may now have values defined
382  // within the loop used in the outer loop.
383  // FIXME: This is really heavy handed. It would be a bit better to use an
384  // SSAUpdater strategy during promotion that was LCSSA aware and reformed
385  // it as it went.
386  if (Promoted)
387  formLCSSARecursively(*L, *DT, LI, SE);
388 
389  Changed |= Promoted;
390  }
391  }
392 
393  // Check that neither this loop nor its parent have had LCSSA broken. LICM is
394  // specifically moving instructions across the loop boundary and so it is
395  // especially in need of sanity checking here.
396  assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
397  assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
398  "Parent loop not left in LCSSA form after LICM!");
399 
400  // If this loop is nested inside of another one, save the alias information
401  // for when we process the outer loop.
402  if (CurAST.get() && L->getParentLoop() && !DeleteAST)
403  LoopToAliasSetMap[L] = std::move(CurAST);
404 
405  if (MSSAU.get() && VerifyMemorySSA)
406  MSSAU->getMemorySSA()->verifyMemorySSA();
407 
408  if (Changed && SE)
409  SE->forgetLoopDispositions(L);
410  return Changed;
411 }
412 
413 /// Walk the specified region of the CFG (defined by all blocks dominated by
414 /// the specified block, and that are in the current loop) in reverse depth
415 /// first order w.r.t the DominatorTree. This allows us to visit uses before
416 /// definitions, allowing us to sink a loop body in one pass without iteration.
417 ///
420  TargetTransformInfo *TTI, Loop *CurLoop,
421  AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
422  ICFLoopSafetyInfo *SafetyInfo,
424 
425  // Verify inputs.
426  assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
427  CurLoop != nullptr && SafetyInfo != nullptr &&
428  "Unexpected input to sinkRegion.");
429  assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
430  "Either AliasSetTracker or MemorySSA should be initialized.");
431 
432  // We want to visit children before parents. We will enque all the parents
433  // before their children in the worklist and process the worklist in reverse
434  // order.
436 
437  bool Changed = false;
438  for (DomTreeNode *DTN : reverse(Worklist)) {
439  BasicBlock *BB = DTN->getBlock();
440  // Only need to process the contents of this block if it is not part of a
441  // subloop (which would already have been processed).
442  if (inSubLoop(BB, CurLoop, LI))
443  continue;
444 
445  for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
446  Instruction &I = *--II;
447 
448  // If the instruction is dead, we would try to sink it because it isn't
449  // used in the loop, instead, just delete it.
450  if (isInstructionTriviallyDead(&I, TLI)) {
451  LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
452  salvageDebugInfo(I);
453  ++II;
454  eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
455  Changed = true;
456  continue;
457  }
458 
459  // Check to see if we can sink this instruction to the exit blocks
460  // of the loop. We can do this if the all users of the instruction are
461  // outside of the loop. In this case, it doesn't even matter if the
462  // operands of the instruction are loop invariant.
463  //
464  bool FreeInLoop = false;
465  if (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
466  canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, ORE) &&
467  !I.mayHaveSideEffects()) {
468  if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE, FreeInLoop)) {
469  if (!FreeInLoop) {
470  ++II;
471  eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
472  }
473  Changed = true;
474  }
475  }
476  }
477  }
478  if (MSSAU && VerifyMemorySSA)
479  MSSAU->getMemorySSA()->verifyMemorySSA();
480  return Changed;
481 }
482 
483 namespace {
484 // This is a helper class for hoistRegion to make it able to hoist control flow
485 // in order to be able to hoist phis. The way this works is that we initially
486 // start hoisting to the loop preheader, and when we see a loop invariant branch
487 // we make note of this. When we then come to hoist an instruction that's
488 // conditional on such a branch we duplicate the branch and the relevant control
489 // flow, then hoist the instruction into the block corresponding to its original
490 // block in the duplicated control flow.
491 class ControlFlowHoister {
492 private:
493  // Information about the loop we are hoisting from
494  LoopInfo *LI;
495  DominatorTree *DT;
496  Loop *CurLoop;
497  MemorySSAUpdater *MSSAU;
498 
499  // A map of blocks in the loop to the block their instructions will be hoisted
500  // to.
501  DenseMap<BasicBlock *, BasicBlock *> HoistDestinationMap;
502 
503  // The branches that we can hoist, mapped to the block that marks a
504  // convergence point of their control flow.
505  DenseMap<BranchInst *, BasicBlock *> HoistableBranches;
506 
507 public:
508  ControlFlowHoister(LoopInfo *LI, DominatorTree *DT, Loop *CurLoop,
509  MemorySSAUpdater *MSSAU)
510  : LI(LI), DT(DT), CurLoop(CurLoop), MSSAU(MSSAU) {}
511 
512  void registerPossiblyHoistableBranch(BranchInst *BI) {
513  // We can only hoist conditional branches with loop invariant operands.
514  if (!ControlFlowHoisting || !BI->isConditional() ||
515  !CurLoop->hasLoopInvariantOperands(BI))
516  return;
517 
518  // The branch destinations need to be in the loop, and we don't gain
519  // anything by duplicating conditional branches with duplicate successors,
520  // as it's essentially the same as an unconditional branch.
521  BasicBlock *TrueDest = BI->getSuccessor(0);
522  BasicBlock *FalseDest = BI->getSuccessor(1);
523  if (!CurLoop->contains(TrueDest) || !CurLoop->contains(FalseDest) ||
524  TrueDest == FalseDest)
525  return;
526 
527  // We can hoist BI if one branch destination is the successor of the other,
528  // or both have common successor which we check by seeing if the
529  // intersection of their successors is non-empty.
530  // TODO: This could be expanded to allowing branches where both ends
531  // eventually converge to a single block.
532  SmallPtrSet<BasicBlock *, 4> TrueDestSucc, FalseDestSucc;
533  TrueDestSucc.insert(succ_begin(TrueDest), succ_end(TrueDest));
534  FalseDestSucc.insert(succ_begin(FalseDest), succ_end(FalseDest));
535  BasicBlock *CommonSucc = nullptr;
536  if (TrueDestSucc.count(FalseDest)) {
537  CommonSucc = FalseDest;
538  } else if (FalseDestSucc.count(TrueDest)) {
539  CommonSucc = TrueDest;
540  } else {
541  set_intersect(TrueDestSucc, FalseDestSucc);
542  // If there's one common successor use that.
543  if (TrueDestSucc.size() == 1)
544  CommonSucc = *TrueDestSucc.begin();
545  // If there's more than one pick whichever appears first in the block list
546  // (we can't use the value returned by TrueDestSucc.begin() as it's
547  // unpredicatable which element gets returned).
548  else if (!TrueDestSucc.empty()) {
549  Function *F = TrueDest->getParent();
550  auto IsSucc = [&](BasicBlock &BB) { return TrueDestSucc.count(&BB); };
551  auto It = std::find_if(F->begin(), F->end(), IsSucc);
552  assert(It != F->end() && "Could not find successor in function");
553  CommonSucc = &*It;
554  }
555  }
556  // The common successor has to be dominated by the branch, as otherwise
557  // there will be some other path to the successor that will not be
558  // controlled by this branch so any phi we hoist would be controlled by the
559  // wrong condition. This also takes care of avoiding hoisting of loop back
560  // edges.
561  // TODO: In some cases this could be relaxed if the successor is dominated
562  // by another block that's been hoisted and we can guarantee that the
563  // control flow has been replicated exactly.
564  if (CommonSucc && DT->dominates(BI, CommonSucc))
565  HoistableBranches[BI] = CommonSucc;
566  }
567 
568  bool canHoistPHI(PHINode *PN) {
569  // The phi must have loop invariant operands.
570  if (!ControlFlowHoisting || !CurLoop->hasLoopInvariantOperands(PN))
571  return false;
572  // We can hoist phis if the block they are in is the target of hoistable
573  // branches which cover all of the predecessors of the block.
574  SmallPtrSet<BasicBlock *, 8> PredecessorBlocks;
575  BasicBlock *BB = PN->getParent();
576  for (BasicBlock *PredBB : predecessors(BB))
577  PredecessorBlocks.insert(PredBB);
578  // If we have less predecessor blocks than predecessors then the phi will
579  // have more than one incoming value for the same block which we can't
580  // handle.
581  // TODO: This could be handled be erasing some of the duplicate incoming
582  // values.
583  if (PredecessorBlocks.size() != pred_size(BB))
584  return false;
585  for (auto &Pair : HoistableBranches) {
586  if (Pair.second == BB) {
587  // Which blocks are predecessors via this branch depends on if the
588  // branch is triangle-like or diamond-like.
589  if (Pair.first->getSuccessor(0) == BB) {
590  PredecessorBlocks.erase(Pair.first->getParent());
591  PredecessorBlocks.erase(Pair.first->getSuccessor(1));
592  } else if (Pair.first->getSuccessor(1) == BB) {
593  PredecessorBlocks.erase(Pair.first->getParent());
594  PredecessorBlocks.erase(Pair.first->getSuccessor(0));
595  } else {
596  PredecessorBlocks.erase(Pair.first->getSuccessor(0));
597  PredecessorBlocks.erase(Pair.first->getSuccessor(1));
598  }
599  }
600  }
601  // PredecessorBlocks will now be empty if for every predecessor of BB we
602  // found a hoistable branch source.
603  return PredecessorBlocks.empty();
604  }
605 
606  BasicBlock *getOrCreateHoistedBlock(BasicBlock *BB) {
607  if (!ControlFlowHoisting)
608  return CurLoop->getLoopPreheader();
609  // If BB has already been hoisted, return that
610  if (HoistDestinationMap.count(BB))
611  return HoistDestinationMap[BB];
612 
613  // Check if this block is conditional based on a pending branch
614  auto HasBBAsSuccessor =
616  return BB != Pair.second && (Pair.first->getSuccessor(0) == BB ||
617  Pair.first->getSuccessor(1) == BB);
618  };
619  auto It = std::find_if(HoistableBranches.begin(), HoistableBranches.end(),
620  HasBBAsSuccessor);
621 
622  // If not involved in a pending branch, hoist to preheader
623  BasicBlock *InitialPreheader = CurLoop->getLoopPreheader();
624  if (It == HoistableBranches.end()) {
625  LLVM_DEBUG(dbgs() << "LICM using " << InitialPreheader->getName()
626  << " as hoist destination for " << BB->getName()
627  << "\n");
628  HoistDestinationMap[BB] = InitialPreheader;
629  return InitialPreheader;
630  }
631  BranchInst *BI = It->first;
632  assert(std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) ==
633  HoistableBranches.end() &&
634  "BB is expected to be the target of at most one branch");
635 
636  LLVMContext &C = BB->getContext();
637  BasicBlock *TrueDest = BI->getSuccessor(0);
638  BasicBlock *FalseDest = BI->getSuccessor(1);
639  BasicBlock *CommonSucc = HoistableBranches[BI];
640  BasicBlock *HoistTarget = getOrCreateHoistedBlock(BI->getParent());
641 
642  // Create hoisted versions of blocks that currently don't have them
643  auto CreateHoistedBlock = [&](BasicBlock *Orig) {
644  if (HoistDestinationMap.count(Orig))
645  return HoistDestinationMap[Orig];
646  BasicBlock *New =
647  BasicBlock::Create(C, Orig->getName() + ".licm", Orig->getParent());
648  HoistDestinationMap[Orig] = New;
649  DT->addNewBlock(New, HoistTarget);
650  if (CurLoop->getParentLoop())
651  CurLoop->getParentLoop()->addBasicBlockToLoop(New, *LI);
652  ++NumCreatedBlocks;
653  LLVM_DEBUG(dbgs() << "LICM created " << New->getName()
654  << " as hoist destination for " << Orig->getName()
655  << "\n");
656  return New;
657  };
658  BasicBlock *HoistTrueDest = CreateHoistedBlock(TrueDest);
659  BasicBlock *HoistFalseDest = CreateHoistedBlock(FalseDest);
660  BasicBlock *HoistCommonSucc = CreateHoistedBlock(CommonSucc);
661 
662  // Link up these blocks with branches.
663  if (!HoistCommonSucc->getTerminator()) {
664  // The new common successor we've generated will branch to whatever that
665  // hoist target branched to.
666  BasicBlock *TargetSucc = HoistTarget->getSingleSuccessor();
667  assert(TargetSucc && "Expected hoist target to have a single successor");
668  HoistCommonSucc->moveBefore(TargetSucc);
669  BranchInst::Create(TargetSucc, HoistCommonSucc);
670  }
671  if (!HoistTrueDest->getTerminator()) {
672  HoistTrueDest->moveBefore(HoistCommonSucc);
673  BranchInst::Create(HoistCommonSucc, HoistTrueDest);
674  }
675  if (!HoistFalseDest->getTerminator()) {
676  HoistFalseDest->moveBefore(HoistCommonSucc);
677  BranchInst::Create(HoistCommonSucc, HoistFalseDest);
678  }
679 
680  // If BI is being cloned to what was originally the preheader then
681  // HoistCommonSucc will now be the new preheader.
682  if (HoistTarget == InitialPreheader) {
683  // Phis in the loop header now need to use the new preheader.
684  InitialPreheader->replaceSuccessorsPhiUsesWith(HoistCommonSucc);
685  if (MSSAU)
687  HoistTarget->getSingleSuccessor(), HoistCommonSucc, {HoistTarget});
688  // The new preheader dominates the loop header.
689  DomTreeNode *PreheaderNode = DT->getNode(HoistCommonSucc);
690  DomTreeNode *HeaderNode = DT->getNode(CurLoop->getHeader());
691  DT->changeImmediateDominator(HeaderNode, PreheaderNode);
692  // The preheader hoist destination is now the new preheader, with the
693  // exception of the hoist destination of this branch.
694  for (auto &Pair : HoistDestinationMap)
695  if (Pair.second == InitialPreheader && Pair.first != BI->getParent())
696  Pair.second = HoistCommonSucc;
697  }
698 
699  // Now finally clone BI.
701  HoistTarget->getTerminator(),
702  BranchInst::Create(HoistTrueDest, HoistFalseDest, BI->getCondition()));
703  ++NumClonedBranches;
704 
705  assert(CurLoop->getLoopPreheader() &&
706  "Hoisting blocks should not have destroyed preheader");
707  return HoistDestinationMap[BB];
708  }
709 };
710 } // namespace
711 
712 /// Walk the specified region of the CFG (defined by all blocks dominated by
713 /// the specified block, and that are in the current loop) in depth first
714 /// order w.r.t the DominatorTree. This allows us to visit definitions before
715 /// uses, allowing us to hoist a loop body in one pass without iteration.
716 ///
718  DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
719  AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
720  ICFLoopSafetyInfo *SafetyInfo,
722  // Verify inputs.
723  assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
724  CurLoop != nullptr && SafetyInfo != nullptr &&
725  "Unexpected input to hoistRegion.");
726  assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
727  "Either AliasSetTracker or MemorySSA should be initialized.");
728 
729  ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
730 
731  // Keep track of instructions that have been hoisted, as they may need to be
732  // re-hoisted if they end up not dominating all of their uses.
733  SmallVector<Instruction *, 16> HoistedInstructions;
734 
735  // For PHI hoisting to work we need to hoist blocks before their successors.
736  // We can do this by iterating through the blocks in the loop in reverse
737  // post-order.
738  LoopBlocksRPO Worklist(CurLoop);
739  Worklist.perform(LI);
740  bool Changed = false;
741  for (BasicBlock *BB : Worklist) {
742  // Only need to process the contents of this block if it is not part of a
743  // subloop (which would already have been processed).
744  if (inSubLoop(BB, CurLoop, LI))
745  continue;
746 
747  for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
748  Instruction &I = *II++;
749  // Try constant folding this instruction. If all the operands are
750  // constants, it is technically hoistable, but it would be better to
751  // just fold it.
753  &I, I.getModule()->getDataLayout(), TLI)) {
754  LLVM_DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C
755  << '\n');
756  if (CurAST)
757  CurAST->copyValue(&I, C);
758  // FIXME MSSA: Such replacements may make accesses unoptimized (D51960).
760  if (isInstructionTriviallyDead(&I, TLI))
761  eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
762  Changed = true;
763  continue;
764  }
765 
766  // Try hoisting the instruction out to the preheader. We can only do
767  // this if all of the operands of the instruction are loop invariant and
768  // if it is safe to hoist the instruction.
769  // TODO: It may be safe to hoist if we are hoisting to a conditional block
770  // and we have accurately duplicated the control flow from the loop header
771  // to that block.
772  if (CurLoop->hasLoopInvariantOperands(&I) &&
773  canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, ORE) &&
775  I, DT, CurLoop, SafetyInfo, ORE,
776  CurLoop->getLoopPreheader()->getTerminator())) {
777  hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
778  MSSAU, ORE);
779  HoistedInstructions.push_back(&I);
780  Changed = true;
781  continue;
782  }
783 
784  // Attempt to remove floating point division out of the loop by
785  // converting it to a reciprocal multiplication.
786  if (I.getOpcode() == Instruction::FDiv &&
787  CurLoop->isLoopInvariant(I.getOperand(1)) &&
788  I.hasAllowReciprocal()) {
789  auto Divisor = I.getOperand(1);
790  auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
791  auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
792  ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
793  SafetyInfo->insertInstructionTo(ReciprocalDivisor, I.getParent());
794  ReciprocalDivisor->insertBefore(&I);
795 
796  auto Product =
797  BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
798  Product->setFastMathFlags(I.getFastMathFlags());
799  SafetyInfo->insertInstructionTo(Product, I.getParent());
800  Product->insertAfter(&I);
801  I.replaceAllUsesWith(Product);
802  eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
803 
804  hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
805  SafetyInfo, MSSAU, ORE);
806  HoistedInstructions.push_back(ReciprocalDivisor);
807  Changed = true;
808  continue;
809  }
810 
811  using namespace PatternMatch;
812  if (((I.use_empty() &&
813  match(&I, m_Intrinsic<Intrinsic::invariant_start>())) ||
814  isGuard(&I)) &&
815  CurLoop->hasLoopInvariantOperands(&I) &&
816  SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop) &&
817  SafetyInfo->doesNotWriteMemoryBefore(I, CurLoop)) {
818  hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
819  MSSAU, ORE);
820  HoistedInstructions.push_back(&I);
821  Changed = true;
822  continue;
823  }
824 
825  if (PHINode *PN = dyn_cast<PHINode>(&I)) {
826  if (CFH.canHoistPHI(PN)) {
827  // Redirect incoming blocks first to ensure that we create hoisted
828  // versions of those blocks before we hoist the phi.
829  for (unsigned int i = 0; i < PN->getNumIncomingValues(); ++i)
830  PN->setIncomingBlock(
831  i, CFH.getOrCreateHoistedBlock(PN->getIncomingBlock(i)));
832  hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
833  MSSAU, ORE);
834  assert(DT->dominates(PN, BB) && "Conditional PHIs not expected");
835  Changed = true;
836  continue;
837  }
838  }
839 
840  // Remember possibly hoistable branches so we can actually hoist them
841  // later if needed.
842  if (BranchInst *BI = dyn_cast<BranchInst>(&I))
843  CFH.registerPossiblyHoistableBranch(BI);
844  }
845  }
846 
847  // If we hoisted instructions to a conditional block they may not dominate
848  // their uses that weren't hoisted (such as phis where some operands are not
849  // loop invariant). If so make them unconditional by moving them to their
850  // immediate dominator. We iterate through the instructions in reverse order
851  // which ensures that when we rehoist an instruction we rehoist its operands,
852  // and also keep track of where in the block we are rehoisting to to make sure
853  // that we rehoist instructions before the instructions that use them.
854  Instruction *HoistPoint = nullptr;
855  if (ControlFlowHoisting) {
856  for (Instruction *I : reverse(HoistedInstructions)) {
857  if (!llvm::all_of(I->uses(),
858  [&](Use &U) { return DT->dominates(I, U); })) {
859  BasicBlock *Dominator =
860  DT->getNode(I->getParent())->getIDom()->getBlock();
861  if (!HoistPoint || !DT->dominates(HoistPoint->getParent(), Dominator)) {
862  if (HoistPoint)
863  assert(DT->dominates(Dominator, HoistPoint->getParent()) &&
864  "New hoist point expected to dominate old hoist point");
865  HoistPoint = Dominator->getTerminator();
866  }
867  LLVM_DEBUG(dbgs() << "LICM rehoisting to "
868  << HoistPoint->getParent()->getName()
869  << ": " << *I << "\n");
870  moveInstructionBefore(*I, *HoistPoint, *SafetyInfo);
871  HoistPoint = I;
872  Changed = true;
873  }
874  }
875  }
876  if (MSSAU && VerifyMemorySSA)
877  MSSAU->getMemorySSA()->verifyMemorySSA();
878 
879  // Now that we've finished hoisting make sure that LI and DT are still
880  // valid.
881 #ifndef NDEBUG
882  if (Changed) {
884  "Dominator tree verification failed");
885  LI->verify(*DT);
886  }
887 #endif
888 
889  return Changed;
890 }
891 
892 // Return true if LI is invariant within scope of the loop. LI is invariant if
893 // CurLoop is dominated by an invariant.start representing the same memory
894 // location and size as the memory location LI loads from, and also the
895 // invariant.start has no uses.
897  Loop *CurLoop) {
898  Value *Addr = LI->getOperand(0);
899  const DataLayout &DL = LI->getModule()->getDataLayout();
900  const uint32_t LocSizeInBits = DL.getTypeSizeInBits(
901  cast<PointerType>(Addr->getType())->getElementType());
902 
903  // if the type is i8 addrspace(x)*, we know this is the type of
904  // llvm.invariant.start operand
905  auto *PtrInt8Ty = PointerType::get(Type::getInt8Ty(LI->getContext()),
906  LI->getPointerAddressSpace());
907  unsigned BitcastsVisited = 0;
908  // Look through bitcasts until we reach the i8* type (this is invariant.start
909  // operand type).
910  while (Addr->getType() != PtrInt8Ty) {
911  auto *BC = dyn_cast<BitCastInst>(Addr);
912  // Avoid traversing high number of bitcast uses.
913  if (++BitcastsVisited > MaxNumUsesTraversed || !BC)
914  return false;
915  Addr = BC->getOperand(0);
916  }
917 
918  unsigned UsesVisited = 0;
919  // Traverse all uses of the load operand value, to see if invariant.start is
920  // one of the uses, and whether it dominates the load instruction.
921  for (auto *U : Addr->users()) {
922  // Avoid traversing for Load operand with high number of users.
923  if (++UsesVisited > MaxNumUsesTraversed)
924  return false;
926  // If there are escaping uses of invariant.start instruction, the load maybe
927  // non-invariant.
928  if (!II || II->getIntrinsicID() != Intrinsic::invariant_start ||
929  !II->use_empty())
930  continue;
931  unsigned InvariantSizeInBits =
932  cast<ConstantInt>(II->getArgOperand(0))->getSExtValue() * 8;
933  // Confirm the invariant.start location size contains the load operand size
934  // in bits. Also, the invariant.start should dominate the load, and we
935  // should not hoist the load out of a loop that contains this dominating
936  // invariant.start.
937  if (LocSizeInBits <= InvariantSizeInBits &&
938  DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
939  return true;
940  }
941 
942  return false;
943 }
944 
945 namespace {
946 /// Return true if-and-only-if we know how to (mechanically) both hoist and
947 /// sink a given instruction out of a loop. Does not address legality
948 /// concerns such as aliasing or speculation safety.
949 bool isHoistableAndSinkableInst(Instruction &I) {
950  // Only these instructions are hoistable/sinkable.
951  return (isa<LoadInst>(I) || isa<StoreInst>(I) ||
952  isa<CallInst>(I) || isa<FenceInst>(I) ||
953  isa<BinaryOperator>(I) || isa<CastInst>(I) ||
954  isa<SelectInst>(I) || isa<GetElementPtrInst>(I) ||
955  isa<CmpInst>(I) || isa<InsertElementInst>(I) ||
956  isa<ExtractElementInst>(I) || isa<ShuffleVectorInst>(I) ||
957  isa<ExtractValueInst>(I) || isa<InsertValueInst>(I));
958 }
959 /// Return true if all of the alias sets within this AST are known not to
960 /// contain a Mod, or if MSSA knows thare are no MemoryDefs in the loop.
961 bool isReadOnly(AliasSetTracker *CurAST, const MemorySSAUpdater *MSSAU,
962  const Loop *L) {
963  if (CurAST) {
964  for (AliasSet &AS : *CurAST) {
965  if (!AS.isForwardingAliasSet() && AS.isMod()) {
966  return false;
967  }
968  }
969  return true;
970  } else { /*MSSAU*/
971  for (auto *BB : L->getBlocks())
972  if (MSSAU->getMemorySSA()->getBlockDefs(BB))
973  return false;
974  return true;
975  }
976 }
977 
978 /// Return true if I is the only Instruction with a MemoryAccess in L.
979 bool isOnlyMemoryAccess(const Instruction *I, const Loop *L,
980  const MemorySSAUpdater *MSSAU) {
981  for (auto *BB : L->getBlocks())
982  if (auto *Accs = MSSAU->getMemorySSA()->getBlockAccesses(BB)) {
983  int NotAPhi = 0;
984  for (const auto &Acc : *Accs) {
985  if (isa<MemoryPhi>(&Acc))
986  continue;
987  const auto *MUD = cast<MemoryUseOrDef>(&Acc);
988  if (MUD->getMemoryInst() != I || NotAPhi++ == 1)
989  return false;
990  }
991  }
992  return true;
993 }
994 }
995 
997  Loop *CurLoop, AliasSetTracker *CurAST,
998  MemorySSAUpdater *MSSAU,
999  bool TargetExecutesOncePerLoop,
1001  // If we don't understand the instruction, bail early.
1002  if (!isHoistableAndSinkableInst(I))
1003  return false;
1004 
1005  MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
1006 
1007  // Loads have extra constraints we have to verify before we can hoist them.
1008  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
1009  if (!LI->isUnordered())
1010  return false; // Don't sink/hoist volatile or ordered atomic loads!
1011 
1012  // Loads from constant memory are always safe to move, even if they end up
1013  // in the same alias set as something that ends up being modified.
1014  if (AA->pointsToConstantMemory(LI->getOperand(0)))
1015  return true;
1016  if (LI->getMetadata(LLVMContext::MD_invariant_load))
1017  return true;
1018 
1019  if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1020  return false; // Don't risk duplicating unordered loads
1021 
1022  // This checks for an invariant.start dominating the load.
1023  if (isLoadInvariantInLoop(LI, DT, CurLoop))
1024  return true;
1025 
1026  bool Invalidated;
1027  if (CurAST)
1028  Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI), CurAST,
1029  CurLoop, AA);
1030  else
1031  Invalidated = pointerInvalidatedByLoopWithMSSA(
1032  MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)), CurLoop);
1033  // Check loop-invariant address because this may also be a sinkable load
1034  // whose address is not necessarily loop-invariant.
1035  if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1036  ORE->emit([&]() {
1037  return OptimizationRemarkMissed(
1038  DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
1039  << "failed to move load with loop-invariant address "
1040  "because the loop may invalidate its value";
1041  });
1042 
1043  return !Invalidated;
1044  } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1045  // Don't sink or hoist dbg info; it's legal, but not useful.
1046  if (isa<DbgInfoIntrinsic>(I))
1047  return false;
1048 
1049  // Don't sink calls which can throw.
1050  if (CI->mayThrow())
1051  return false;
1052 
1053  using namespace PatternMatch;
1054  if (match(CI, m_Intrinsic<Intrinsic::assume>()))
1055  // Assumes don't actually alias anything or throw
1056  return true;
1057 
1058  // Handle simple cases by querying alias analysis.
1059  FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
1060  if (Behavior == FMRB_DoesNotAccessMemory)
1061  return true;
1062  if (AliasAnalysis::onlyReadsMemory(Behavior)) {
1063  // A readonly argmemonly function only reads from memory pointed to by
1064  // it's arguments with arbitrary offsets. If we can prove there are no
1065  // writes to this memory in the loop, we can hoist or sink.
1067  // TODO: expand to writeable arguments
1068  for (Value *Op : CI->arg_operands())
1069  if (Op->getType()->isPointerTy()) {
1070  bool Invalidated;
1071  if (CurAST)
1072  Invalidated = pointerInvalidatedByLoop(
1074  CurAST, CurLoop, AA);
1075  else
1076  Invalidated = pointerInvalidatedByLoopWithMSSA(
1077  MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(CI)), CurLoop);
1078  if (Invalidated)
1079  return false;
1080  }
1081  return true;
1082  }
1083 
1084  // If this call only reads from memory and there are no writes to memory
1085  // in the loop, we can hoist or sink the call as appropriate.
1086  if (isReadOnly(CurAST, MSSAU, CurLoop))
1087  return true;
1088  }
1089 
1090  // FIXME: This should use mod/ref information to see if we can hoist or
1091  // sink the call.
1092 
1093  return false;
1094  } else if (auto *FI = dyn_cast<FenceInst>(&I)) {
1095  // Fences alias (most) everything to provide ordering. For the moment,
1096  // just give up if there are any other memory operations in the loop.
1097  if (CurAST) {
1098  auto Begin = CurAST->begin();
1099  assert(Begin != CurAST->end() && "must contain FI");
1100  if (std::next(Begin) != CurAST->end())
1101  // constant memory for instance, TODO: handle better
1102  return false;
1103  auto *UniqueI = Begin->getUniqueInstruction();
1104  if (!UniqueI)
1105  // other memory op, give up
1106  return false;
1107  (void)FI; // suppress unused variable warning
1108  assert(UniqueI == FI && "AS must contain FI");
1109  return true;
1110  } else // MSSAU
1111  return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
1112  } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
1113  if (!SI->isUnordered())
1114  return false; // Don't sink/hoist volatile or ordered atomic store!
1115 
1116  // We can only hoist a store that we can prove writes a value which is not
1117  // read or overwritten within the loop. For those cases, we fallback to
1118  // load store promotion instead. TODO: We can extend this to cases where
1119  // there is exactly one write to the location and that write dominates an
1120  // arbitrary number of reads in the loop.
1121  if (CurAST) {
1122  auto &AS = CurAST->getAliasSetFor(MemoryLocation::get(SI));
1123 
1124  if (AS.isRef() || !AS.isMustAlias())
1125  // Quick exit test, handled by the full path below as well.
1126  return false;
1127  auto *UniqueI = AS.getUniqueInstruction();
1128  if (!UniqueI)
1129  // other memory op, give up
1130  return false;
1131  assert(UniqueI == SI && "AS must contain SI");
1132  return true;
1133  } else { // MSSAU
1134  if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
1135  return true;
1136  if (!EnableLicmCap) {
1138  if (MSSA->isLiveOnEntryDef(Source) ||
1139  !CurLoop->contains(Source->getBlock()))
1140  return true;
1141  }
1142  return false;
1143  }
1144  }
1145 
1146  assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
1147 
1148  // We've established mechanical ability and aliasing, it's up to the caller
1149  // to check fault safety
1150  return true;
1151 }
1152 
1153 /// Returns true if a PHINode is a trivially replaceable with an
1154 /// Instruction.
1155 /// This is true when all incoming values are that instruction.
1156 /// This pattern occurs most often with LCSSA PHI nodes.
1157 ///
1158 static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I) {
1159  for (const Value *IncValue : PN.incoming_values())
1160  if (IncValue != &I)
1161  return false;
1162 
1163  return true;
1164 }
1165 
1166 /// Return true if the instruction is free in the loop.
1167 static bool isFreeInLoop(const Instruction &I, const Loop *CurLoop,
1168  const TargetTransformInfo *TTI) {
1169 
1170  if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1172  return false;
1173  // For a GEP, we cannot simply use getUserCost because currently it
1174  // optimistically assume that a GEP will fold into addressing mode
1175  // regardless of its users.
1176  const BasicBlock *BB = GEP->getParent();
1177  for (const User *U : GEP->users()) {
1178  const Instruction *UI = cast<Instruction>(U);
1179  if (CurLoop->contains(UI) &&
1180  (BB != UI->getParent() ||
1181  (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1182  return false;
1183  }
1184  return true;
1185  } else
1186  return TTI->getUserCost(&I) == TargetTransformInfo::TCC_Free;
1187 }
1188 
1189 /// Return true if the only users of this instruction are outside of
1190 /// the loop. If this is true, we can sink the instruction to the exit
1191 /// blocks of the loop.
1192 ///
1193 /// We also return true if the instruction could be folded away in lowering.
1194 /// (e.g., a GEP can be folded into a load as an addressing mode in the loop).
1195 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
1196  const LoopSafetyInfo *SafetyInfo,
1197  TargetTransformInfo *TTI, bool &FreeInLoop) {
1198  const auto &BlockColors = SafetyInfo->getBlockColors();
1199  bool IsFree = isFreeInLoop(I, CurLoop, TTI);
1200  for (const User *U : I.users()) {
1201  const Instruction *UI = cast<Instruction>(U);
1202  if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
1203  const BasicBlock *BB = PN->getParent();
1204  // We cannot sink uses in catchswitches.
1205  if (isa<CatchSwitchInst>(BB->getTerminator()))
1206  return false;
1207 
1208  // We need to sink a callsite to a unique funclet. Avoid sinking if the
1209  // phi use is too muddled.
1210  if (isa<CallInst>(I))
1211  if (!BlockColors.empty() &&
1212  BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
1213  return false;
1214  }
1215 
1216  if (CurLoop->contains(UI)) {
1217  if (IsFree) {
1218  FreeInLoop = true;
1219  continue;
1220  }
1221  return false;
1222  }
1223  }
1224  return true;
1225 }
1226 
1228  Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
1229  const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU) {
1230  Instruction *New;
1231  if (auto *CI = dyn_cast<CallInst>(&I)) {
1232  const auto &BlockColors = SafetyInfo->getBlockColors();
1233 
1234  // Sinking call-sites need to be handled differently from other
1235  // instructions. The cloned call-site needs a funclet bundle operand
1236  // appropriate for it's location in the CFG.
1238  for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1239  BundleIdx != BundleEnd; ++BundleIdx) {
1240  OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
1241  if (Bundle.getTagID() == LLVMContext::OB_funclet)
1242  continue;
1243 
1244  OpBundles.emplace_back(Bundle);
1245  }
1246 
1247  if (!BlockColors.empty()) {
1248  const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1249  assert(CV.size() == 1 && "non-unique color for exit block!");
1250  BasicBlock *BBColor = CV.front();
1251  Instruction *EHPad = BBColor->getFirstNonPHI();
1252  if (EHPad->isEHPad())
1253  OpBundles.emplace_back("funclet", EHPad);
1254  }
1255 
1256  New = CallInst::Create(CI, OpBundles);
1257  } else {
1258  New = I.clone();
1259  }
1260 
1261  ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
1262  if (!I.getName().empty())
1263  New->setName(I.getName() + ".le");
1264 
1265  MemoryAccess *OldMemAcc;
1266  if (MSSAU && (OldMemAcc = MSSAU->getMemorySSA()->getMemoryAccess(&I))) {
1267  // Create a new MemoryAccess and let MemorySSA set its defining access.
1268  MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
1269  New, nullptr, New->getParent(), MemorySSA::Beginning);
1270  if (NewMemAcc) {
1271  if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1272  MSSAU->insertDef(MemDef, /*RenameUses=*/true);
1273  else {
1274  auto *MemUse = cast<MemoryUse>(NewMemAcc);
1275  MSSAU->insertUse(MemUse);
1276  }
1277  }
1278  }
1279 
1280  // Build LCSSA PHI nodes for any in-loop operands. Note that this is
1281  // particularly cheap because we can rip off the PHI node that we're
1282  // replacing for the number and blocks of the predecessors.
1283  // OPT: If this shows up in a profile, we can instead finish sinking all
1284  // invariant instructions, and then walk their operands to re-establish
1285  // LCSSA. That will eliminate creating PHI nodes just to nuke them when
1286  // sinking bottom-up.
1287  for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
1288  ++OI)
1289  if (Instruction *OInst = dyn_cast<Instruction>(*OI))
1290  if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
1291  if (!OLoop->contains(&PN)) {
1292  PHINode *OpPN =
1293  PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
1294  OInst->getName() + ".lcssa", &ExitBlock.front());
1295  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1296  OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
1297  *OI = OpPN;
1298  }
1299  return New;
1300 }
1301 
1303  AliasSetTracker *AST, MemorySSAUpdater *MSSAU) {
1304  if (AST)
1305  AST->deleteValue(&I);
1306  if (MSSAU)
1307  MSSAU->removeMemoryAccess(&I);
1308  SafetyInfo.removeInstruction(&I);
1309  I.eraseFromParent();
1310 }
1311 
1313  ICFLoopSafetyInfo &SafetyInfo) {
1314  SafetyInfo.removeInstruction(&I);
1315  SafetyInfo.insertInstructionTo(&I, Dest.getParent());
1316  I.moveBefore(&Dest);
1317 }
1318 
1320  PHINode *TPN, Instruction *I, LoopInfo *LI,
1322  const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop,
1323  MemorySSAUpdater *MSSAU) {
1324  assert(isTriviallyReplaceablePHI(*TPN, *I) &&
1325  "Expect only trivially replaceable PHI");
1326  BasicBlock *ExitBlock = TPN->getParent();
1327  Instruction *New;
1328  auto It = SunkCopies.find(ExitBlock);
1329  if (It != SunkCopies.end())
1330  New = It->second;
1331  else
1332  New = SunkCopies[ExitBlock] = CloneInstructionInExitBlock(
1333  *I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1334  return New;
1335 }
1336 
1337 static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo) {
1338  BasicBlock *BB = PN->getParent();
1339  if (!BB->canSplitPredecessors())
1340  return false;
1341  // It's not impossible to split EHPad blocks, but if BlockColors already exist
1342  // it require updating BlockColors for all offspring blocks accordingly. By
1343  // skipping such corner case, we can make updating BlockColors after splitting
1344  // predecessor fairly simple.
1345  if (!SafetyInfo->getBlockColors().empty() && BB->getFirstNonPHI()->isEHPad())
1346  return false;
1347  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
1348  BasicBlock *BBPred = *PI;
1349  if (isa<IndirectBrInst>(BBPred->getTerminator()))
1350  return false;
1351  }
1352  return true;
1353 }
1354 
1356  LoopInfo *LI, const Loop *CurLoop,
1357  LoopSafetyInfo *SafetyInfo,
1358  MemorySSAUpdater *MSSAU) {
1359 #ifndef NDEBUG
1360  SmallVector<BasicBlock *, 32> ExitBlocks;
1361  CurLoop->getUniqueExitBlocks(ExitBlocks);
1362  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1363  ExitBlocks.end());
1364 #endif
1365  BasicBlock *ExitBB = PN->getParent();
1366  assert(ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block.");
1367 
1368  // Split predecessors of the loop exit to make instructions in the loop are
1369  // exposed to exit blocks through trivially replaceable PHIs while keeping the
1370  // loop in the canonical form where each predecessor of each exit block should
1371  // be contained within the loop. For example, this will convert the loop below
1372  // from
1373  //
1374  // LB1:
1375  // %v1 =
1376  // br %LE, %LB2
1377  // LB2:
1378  // %v2 =
1379  // br %LE, %LB1
1380  // LE:
1381  // %p = phi [%v1, %LB1], [%v2, %LB2] <-- non-trivially replaceable
1382  //
1383  // to
1384  //
1385  // LB1:
1386  // %v1 =
1387  // br %LE.split, %LB2
1388  // LB2:
1389  // %v2 =
1390  // br %LE.split2, %LB1
1391  // LE.split:
1392  // %p1 = phi [%v1, %LB1] <-- trivially replaceable
1393  // br %LE
1394  // LE.split2:
1395  // %p2 = phi [%v2, %LB2] <-- trivially replaceable
1396  // br %LE
1397  // LE:
1398  // %p = phi [%p1, %LE.split], [%p2, %LE.split2]
1399  //
1400  const auto &BlockColors = SafetyInfo->getBlockColors();
1401  SmallSetVector<BasicBlock *, 8> PredBBs(pred_begin(ExitBB), pred_end(ExitBB));
1402  while (!PredBBs.empty()) {
1403  BasicBlock *PredBB = *PredBBs.begin();
1404  assert(CurLoop->contains(PredBB) &&
1405  "Expect all predecessors are in the loop");
1406  if (PN->getBasicBlockIndex(PredBB) >= 0) {
1408  ExitBB, PredBB, ".split.loop.exit", DT, LI, MSSAU, true);
1409  // Since we do not allow splitting EH-block with BlockColors in
1410  // canSplitPredecessors(), we can simply assign predecessor's color to
1411  // the new block.
1412  if (!BlockColors.empty())
1413  // Grab a reference to the ColorVector to be inserted before getting the
1414  // reference to the vector we are copying because inserting the new
1415  // element in BlockColors might cause the map to be reallocated.
1416  SafetyInfo->copyColors(NewPred, PredBB);
1417  }
1418  PredBBs.remove(PredBB);
1419  }
1420 }
1421 
1422 /// When an instruction is found to only be used outside of the loop, this
1423 /// function moves it to the exit blocks and patches up SSA form as needed.
1424 /// This method is guaranteed to remove the original instruction from its
1425 /// position, and may either delete it or move it to outside of the loop.
1426 ///
1427 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
1428  const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
1430  bool FreeInLoop) {
1431  LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
1432  ORE->emit([&]() {
1433  return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
1434  << "sinking " << ore::NV("Inst", &I);
1435  });
1436  bool Changed = false;
1437  if (isa<LoadInst>(I))
1438  ++NumMovedLoads;
1439  else if (isa<CallInst>(I))
1440  ++NumMovedCalls;
1441  ++NumSunk;
1442 
1443  // Iterate over users to be ready for actual sinking. Replace users via
1444  // unrechable blocks with undef and make all user PHIs trivially replcable.
1445  SmallPtrSet<Instruction *, 8> VisitedUsers;
1446  for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
1447  auto *User = cast<Instruction>(*UI);
1448  Use &U = UI.getUse();
1449  ++UI;
1450 
1451  if (VisitedUsers.count(User) || CurLoop->contains(User))
1452  continue;
1453 
1454  if (!DT->isReachableFromEntry(User->getParent())) {
1455  U = UndefValue::get(I.getType());
1456  Changed = true;
1457  continue;
1458  }
1459 
1460  // The user must be a PHI node.
1461  PHINode *PN = cast<PHINode>(User);
1462 
1463  // Surprisingly, instructions can be used outside of loops without any
1464  // exits. This can only happen in PHI nodes if the incoming block is
1465  // unreachable.
1466  BasicBlock *BB = PN->getIncomingBlock(U);
1467  if (!DT->isReachableFromEntry(BB)) {
1468  U = UndefValue::get(I.getType());
1469  Changed = true;
1470  continue;
1471  }
1472 
1473  VisitedUsers.insert(PN);
1474  if (isTriviallyReplaceablePHI(*PN, I))
1475  continue;
1476 
1477  if (!canSplitPredecessors(PN, SafetyInfo))
1478  return Changed;
1479 
1480  // Split predecessors of the PHI so that we can make users trivially
1481  // replaceable.
1482  splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo, MSSAU);
1483 
1484  // Should rebuild the iterators, as they may be invalidated by
1485  // splitPredecessorsOfLoopExit().
1486  UI = I.user_begin();
1487  UE = I.user_end();
1488  }
1489 
1490  if (VisitedUsers.empty())
1491  return Changed;
1492 
1493 #ifndef NDEBUG
1494  SmallVector<BasicBlock *, 32> ExitBlocks;
1495  CurLoop->getUniqueExitBlocks(ExitBlocks);
1496  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1497  ExitBlocks.end());
1498 #endif
1499 
1500  // Clones of this instruction. Don't create more than one per exit block!
1502 
1503  // If this instruction is only used outside of the loop, then all users are
1504  // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
1505  // the instruction.
1507  for (auto *UI : Users) {
1508  auto *User = cast<Instruction>(UI);
1509 
1510  if (CurLoop->contains(User))
1511  continue;
1512 
1513  PHINode *PN = cast<PHINode>(User);
1514  assert(ExitBlockSet.count(PN->getParent()) &&
1515  "The LCSSA PHI is not in an exit block!");
1516  // The PHI must be trivially replaceable.
1518  PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1519  PN->replaceAllUsesWith(New);
1520  eraseInstruction(*PN, *SafetyInfo, nullptr, nullptr);
1521  Changed = true;
1522  }
1523  return Changed;
1524 }
1525 
1526 /// When an instruction is found to only use loop invariant operands that
1527 /// is safe to hoist, this instruction is called to do the dirty work.
1528 ///
1529 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
1530  BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
1532  LLVM_DEBUG(dbgs() << "LICM hoisting to " << Dest->getName() << ": " << I
1533  << "\n");
1534  ORE->emit([&]() {
1535  return OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting "
1536  << ore::NV("Inst", &I);
1537  });
1538 
1539  // Metadata can be dependent on conditions we are hoisting above.
1540  // Conservatively strip all metadata on the instruction unless we were
1541  // guaranteed to execute I if we entered the loop, in which case the metadata
1542  // is valid in the loop preheader.
1543  if (I.hasMetadataOtherThanDebugLoc() &&
1544  // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
1545  // time in isGuaranteedToExecute if we don't actually have anything to
1546  // drop. It is a compile time optimization, not required for correctness.
1547  !SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop))
1549 
1550  if (isa<PHINode>(I))
1551  // Move the new node to the end of the phi list in the destination block.
1552  moveInstructionBefore(I, *Dest->getFirstNonPHI(), *SafetyInfo);
1553  else
1554  // Move the new node to the destination block, before its terminator.
1555  moveInstructionBefore(I, *Dest->getTerminator(), *SafetyInfo);
1556  if (MSSAU) {
1557  // If moving, I just moved a load or store, so update MemorySSA.
1558  MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
1559  MSSAU->getMemorySSA()->getMemoryAccess(&I));
1560  if (OldMemAcc)
1561  MSSAU->moveToPlace(OldMemAcc, Dest, MemorySSA::End);
1562  }
1563 
1564  // Do not retain debug locations when we are moving instructions to different
1565  // basic blocks, because we want to avoid jumpy line tables. Calls, however,
1566  // need to retain their debug locs because they may be inlined.
1567  // FIXME: How do we retain source locations without causing poor debugging
1568  // behavior?
1569  if (!isa<CallInst>(I))
1570  I.setDebugLoc(DebugLoc());
1571 
1572  if (isa<LoadInst>(I))
1573  ++NumMovedLoads;
1574  else if (isa<CallInst>(I))
1575  ++NumMovedCalls;
1576  ++NumHoisted;
1577 }
1578 
1579 /// Only sink or hoist an instruction if it is not a trapping instruction,
1580 /// or if the instruction is known not to trap when moved to the preheader.
1581 /// or if it is a trapping instruction and is guaranteed to execute.
1583  const DominatorTree *DT,
1584  const Loop *CurLoop,
1585  const LoopSafetyInfo *SafetyInfo,
1587  const Instruction *CtxI) {
1588  if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
1589  return true;
1590 
1591  bool GuaranteedToExecute =
1592  SafetyInfo->isGuaranteedToExecute(Inst, DT, CurLoop);
1593 
1594  if (!GuaranteedToExecute) {
1595  auto *LI = dyn_cast<LoadInst>(&Inst);
1596  if (LI && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1597  ORE->emit([&]() {
1598  return OptimizationRemarkMissed(
1599  DEBUG_TYPE, "LoadWithLoopInvariantAddressCondExecuted", LI)
1600  << "failed to hoist load with loop-invariant address "
1601  "because load is conditionally executed";
1602  });
1603  }
1604 
1605  return GuaranteedToExecute;
1606 }
1607 
1608 namespace {
1609 class LoopPromoter : public LoadAndStorePromoter {
1610  Value *SomePtr; // Designated pointer to store to.
1611  const SmallSetVector<Value *, 8> &PointerMustAliases;
1612  SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
1613  SmallVectorImpl<Instruction *> &LoopInsertPts;
1614  PredIteratorCache &PredCache;
1615  AliasSetTracker &AST;
1616  LoopInfo &LI;
1617  DebugLoc DL;
1618  int Alignment;
1619  bool UnorderedAtomic;
1620  AAMDNodes AATags;
1621  ICFLoopSafetyInfo &SafetyInfo;
1622 
1623  Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
1624  if (Instruction *I = dyn_cast<Instruction>(V))
1625  if (Loop *L = LI.getLoopFor(I->getParent()))
1626  if (!L->contains(BB)) {
1627  // We need to create an LCSSA PHI node for the incoming value and
1628  // store that.
1629  PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
1630  I->getName() + ".lcssa", &BB->front());
1631  for (BasicBlock *Pred : PredCache.get(BB))
1632  PN->addIncoming(I, Pred);
1633  return PN;
1634  }
1635  return V;
1636  }
1637 
1638 public:
1639  LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
1640  const SmallSetVector<Value *, 8> &PMA,
1643  AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
1644  bool UnorderedAtomic, const AAMDNodes &AATags,
1645  ICFLoopSafetyInfo &SafetyInfo)
1646  : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
1647  LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
1648  LI(li), DL(std::move(dl)), Alignment(alignment),
1649  UnorderedAtomic(UnorderedAtomic), AATags(AATags), SafetyInfo(SafetyInfo)
1650  {}
1651 
1652  bool isInstInList(Instruction *I,
1653  const SmallVectorImpl<Instruction *> &) const override {
1654  Value *Ptr;
1655  if (LoadInst *LI = dyn_cast<LoadInst>(I))
1656  Ptr = LI->getOperand(0);
1657  else
1658  Ptr = cast<StoreInst>(I)->getPointerOperand();
1659  return PointerMustAliases.count(Ptr);
1660  }
1661 
1662  void doExtraRewritesBeforeFinalDeletion() const override {
1663  // Insert stores after in the loop exit blocks. Each exit block gets a
1664  // store of the live-out values that feed them. Since we've already told
1665  // the SSA updater about the defs in the loop and the preheader
1666  // definition, it is all set and we can start using it.
1667  for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
1668  BasicBlock *ExitBlock = LoopExitBlocks[i];
1669  Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
1670  LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1671  Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1672  Instruction *InsertPos = LoopInsertPts[i];
1673  StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
1674  if (UnorderedAtomic)
1676  NewSI->setAlignment(Alignment);
1677  NewSI->setDebugLoc(DL);
1678  if (AATags)
1679  NewSI->setAAMetadata(AATags);
1680  }
1681  }
1682 
1683  void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
1684  // Update alias analysis.
1685  AST.copyValue(LI, V);
1686  }
1687  void instructionDeleted(Instruction *I) const override {
1688  SafetyInfo.removeInstruction(I);
1689  AST.deleteValue(I);
1690  }
1691 };
1692 
1693 
1694 /// Return true iff we can prove that a caller of this function can not inspect
1695 /// the contents of the provided object in a well defined program.
1696 bool isKnownNonEscaping(Value *Object, const TargetLibraryInfo *TLI) {
1697  if (isa<AllocaInst>(Object))
1698  // Since the alloca goes out of scope, we know the caller can't retain a
1699  // reference to it and be well defined. Thus, we don't need to check for
1700  // capture.
1701  return true;
1702 
1703  // For all other objects we need to know that the caller can't possibly
1704  // have gotten a reference to the object. There are two components of
1705  // that:
1706  // 1) Object can't be escaped by this function. This is what
1707  // PointerMayBeCaptured checks.
1708  // 2) Object can't have been captured at definition site. For this, we
1709  // need to know the return value is noalias. At the moment, we use a
1710  // weaker condition and handle only AllocLikeFunctions (which are
1711  // known to be noalias). TODO
1712  return isAllocLikeFn(Object, TLI) &&
1713  !PointerMayBeCaptured(Object, true, true);
1714 }
1715 
1716 } // namespace
1717 
1718 /// Try to promote memory values to scalars by sinking stores out of the
1719 /// loop and moving loads to before the loop. We do this by looping over
1720 /// the stores in the loop, looking for stores to Must pointers which are
1721 /// loop invariant.
1722 ///
1724  const SmallSetVector<Value *, 8> &PointerMustAliases,
1725  SmallVectorImpl<BasicBlock *> &ExitBlocks,
1727  LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
1728  Loop *CurLoop, AliasSetTracker *CurAST, ICFLoopSafetyInfo *SafetyInfo,
1730  // Verify inputs.
1731  assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
1732  CurAST != nullptr && SafetyInfo != nullptr &&
1733  "Unexpected Input to promoteLoopAccessesToScalars");
1734 
1735  Value *SomePtr = *PointerMustAliases.begin();
1736  BasicBlock *Preheader = CurLoop->getLoopPreheader();
1737 
1738  // It is not safe to promote a load/store from the loop if the load/store is
1739  // conditional. For example, turning:
1740  //
1741  // for () { if (c) *P += 1; }
1742  //
1743  // into:
1744  //
1745  // tmp = *P; for () { if (c) tmp +=1; } *P = tmp;
1746  //
1747  // is not safe, because *P may only be valid to access if 'c' is true.
1748  //
1749  // The safety property divides into two parts:
1750  // p1) The memory may not be dereferenceable on entry to the loop. In this
1751  // case, we can't insert the required load in the preheader.
1752  // p2) The memory model does not allow us to insert a store along any dynamic
1753  // path which did not originally have one.
1754  //
1755  // If at least one store is guaranteed to execute, both properties are
1756  // satisfied, and promotion is legal.
1757  //
1758  // This, however, is not a necessary condition. Even if no store/load is
1759  // guaranteed to execute, we can still establish these properties.
1760  // We can establish (p1) by proving that hoisting the load into the preheader
1761  // is safe (i.e. proving dereferenceability on all paths through the loop). We
1762  // can use any access within the alias set to prove dereferenceability,
1763  // since they're all must alias.
1764  //
1765  // There are two ways establish (p2):
1766  // a) Prove the location is thread-local. In this case the memory model
1767  // requirement does not apply, and stores are safe to insert.
1768  // b) Prove a store dominates every exit block. In this case, if an exit
1769  // blocks is reached, the original dynamic path would have taken us through
1770  // the store, so inserting a store into the exit block is safe. Note that this
1771  // is different from the store being guaranteed to execute. For instance,
1772  // if an exception is thrown on the first iteration of the loop, the original
1773  // store is never executed, but the exit blocks are not executed either.
1774 
1775  bool DereferenceableInPH = false;
1776  bool SafeToInsertStore = false;
1777 
1779 
1780  // We start with an alignment of one and try to find instructions that allow
1781  // us to prove better alignment.
1782  unsigned Alignment = 1;
1783  // Keep track of which types of access we see
1784  bool SawUnorderedAtomic = false;
1785  bool SawNotAtomic = false;
1786  AAMDNodes AATags;
1787 
1788  const DataLayout &MDL = Preheader->getModule()->getDataLayout();
1789 
1790  bool IsKnownThreadLocalObject = false;
1791  if (SafetyInfo->anyBlockMayThrow()) {
1792  // If a loop can throw, we have to insert a store along each unwind edge.
1793  // That said, we can't actually make the unwind edge explicit. Therefore,
1794  // we have to prove that the store is dead along the unwind edge. We do
1795  // this by proving that the caller can't have a reference to the object
1796  // after return and thus can't possibly load from the object.
1797  Value *Object = GetUnderlyingObject(SomePtr, MDL);
1798  if (!isKnownNonEscaping(Object, TLI))
1799  return false;
1800  // Subtlety: Alloca's aren't visible to callers, but *are* potentially
1801  // visible to other threads if captured and used during their lifetimes.
1802  IsKnownThreadLocalObject = !isa<AllocaInst>(Object);
1803  }
1804 
1805  // Check that all of the pointers in the alias set have the same type. We
1806  // cannot (yet) promote a memory location that is loaded and stored in
1807  // different sizes. While we are at it, collect alignment and AA info.
1808  for (Value *ASIV : PointerMustAliases) {
1809  // Check that all of the pointers in the alias set have the same type. We
1810  // cannot (yet) promote a memory location that is loaded and stored in
1811  // different sizes.
1812  if (SomePtr->getType() != ASIV->getType())
1813  return false;
1814 
1815  for (User *U : ASIV->users()) {
1816  // Ignore instructions that are outside the loop.
1817  Instruction *UI = dyn_cast<Instruction>(U);
1818  if (!UI || !CurLoop->contains(UI))
1819  continue;
1820 
1821  // If there is an non-load/store instruction in the loop, we can't promote
1822  // it.
1823  if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
1824  if (!Load->isUnordered())
1825  return false;
1826 
1827  SawUnorderedAtomic |= Load->isAtomic();
1828  SawNotAtomic |= !Load->isAtomic();
1829 
1830  if (!DereferenceableInPH)
1831  DereferenceableInPH = isSafeToExecuteUnconditionally(
1832  *Load, DT, CurLoop, SafetyInfo, ORE, Preheader->getTerminator());
1833  } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
1834  // Stores *of* the pointer are not interesting, only stores *to* the
1835  // pointer.
1836  if (UI->getOperand(1) != ASIV)
1837  continue;
1838  if (!Store->isUnordered())
1839  return false;
1840 
1841  SawUnorderedAtomic |= Store->isAtomic();
1842  SawNotAtomic |= !Store->isAtomic();
1843 
1844  // If the store is guaranteed to execute, both properties are satisfied.
1845  // We may want to check if a store is guaranteed to execute even if we
1846  // already know that promotion is safe, since it may have higher
1847  // alignment than any other guaranteed stores, in which case we can
1848  // raise the alignment on the promoted store.
1849  unsigned InstAlignment = Store->getAlignment();
1850  if (!InstAlignment)
1851  InstAlignment =
1852  MDL.getABITypeAlignment(Store->getValueOperand()->getType());
1853 
1854  if (!DereferenceableInPH || !SafeToInsertStore ||
1855  (InstAlignment > Alignment)) {
1856  if (SafetyInfo->isGuaranteedToExecute(*UI, DT, CurLoop)) {
1857  DereferenceableInPH = true;
1858  SafeToInsertStore = true;
1859  Alignment = std::max(Alignment, InstAlignment);
1860  }
1861  }
1862 
1863  // If a store dominates all exit blocks, it is safe to sink.
1864  // As explained above, if an exit block was executed, a dominating
1865  // store must have been executed at least once, so we are not
1866  // introducing stores on paths that did not have them.
1867  // Note that this only looks at explicit exit blocks. If we ever
1868  // start sinking stores into unwind edges (see above), this will break.
1869  if (!SafeToInsertStore)
1870  SafeToInsertStore = llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
1871  return DT->dominates(Store->getParent(), Exit);
1872  });
1873 
1874  // If the store is not guaranteed to execute, we may still get
1875  // deref info through it.
1876  if (!DereferenceableInPH) {
1877  DereferenceableInPH = isDereferenceableAndAlignedPointer(
1878  Store->getPointerOperand(), Store->getAlignment(), MDL,
1879  Preheader->getTerminator(), DT);
1880  }
1881  } else
1882  return false; // Not a load or store.
1883 
1884  // Merge the AA tags.
1885  if (LoopUses.empty()) {
1886  // On the first load/store, just take its AA tags.
1887  UI->getAAMetadata(AATags);
1888  } else if (AATags) {
1889  UI->getAAMetadata(AATags, /* Merge = */ true);
1890  }
1891 
1892  LoopUses.push_back(UI);
1893  }
1894  }
1895 
1896  // If we found both an unordered atomic instruction and a non-atomic memory
1897  // access, bail. We can't blindly promote non-atomic to atomic since we
1898  // might not be able to lower the result. We can't downgrade since that
1899  // would violate memory model. Also, align 0 is an error for atomics.
1900  if (SawUnorderedAtomic && SawNotAtomic)
1901  return false;
1902 
1903  // If we couldn't prove we can hoist the load, bail.
1904  if (!DereferenceableInPH)
1905  return false;
1906 
1907  // We know we can hoist the load, but don't have a guaranteed store.
1908  // Check whether the location is thread-local. If it is, then we can insert
1909  // stores along paths which originally didn't have them without violating the
1910  // memory model.
1911  if (!SafeToInsertStore) {
1912  if (IsKnownThreadLocalObject)
1913  SafeToInsertStore = true;
1914  else {
1915  Value *Object = GetUnderlyingObject(SomePtr, MDL);
1916  SafeToInsertStore =
1917  (isAllocLikeFn(Object, TLI) || isa<AllocaInst>(Object)) &&
1918  !PointerMayBeCaptured(Object, true, true);
1919  }
1920  }
1921 
1922  // If we've still failed to prove we can sink the store, give up.
1923  if (!SafeToInsertStore)
1924  return false;
1925 
1926  // Otherwise, this is safe to promote, lets do it!
1927  LLVM_DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr
1928  << '\n');
1929  ORE->emit([&]() {
1930  return OptimizationRemark(DEBUG_TYPE, "PromoteLoopAccessesToScalar",
1931  LoopUses[0])
1932  << "Moving accesses to memory location out of the loop";
1933  });
1934  ++NumPromoted;
1935 
1936  // Grab a debug location for the inserted loads/stores; given that the
1937  // inserted loads/stores have little relation to the original loads/stores,
1938  // this code just arbitrarily picks a location from one, since any debug
1939  // location is better than none.
1940  DebugLoc DL = LoopUses[0]->getDebugLoc();
1941 
1942  // We use the SSAUpdater interface to insert phi nodes as required.
1944  SSAUpdater SSA(&NewPHIs);
1945  LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
1946  InsertPts, PIC, *CurAST, *LI, DL, Alignment,
1947  SawUnorderedAtomic, AATags, *SafetyInfo);
1948 
1949  // Set up the preheader to have a definition of the value. It is the live-out
1950  // value from the preheader that uses in the loop will use.
1951  LoadInst *PreheaderLoad = new LoadInst(
1952  SomePtr, SomePtr->getName() + ".promoted", Preheader->getTerminator());
1953  if (SawUnorderedAtomic)
1954  PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
1955  PreheaderLoad->setAlignment(Alignment);
1956  PreheaderLoad->setDebugLoc(DL);
1957  if (AATags)
1958  PreheaderLoad->setAAMetadata(AATags);
1959  SSA.AddAvailableValue(Preheader, PreheaderLoad);
1960 
1961  // Rewrite all the loads in the loop and remember all the definitions from
1962  // stores in the loop.
1963  Promoter.run(LoopUses);
1964 
1965  // If the SSAUpdater didn't use the load in the preheader, just zap it now.
1966  if (PreheaderLoad->use_empty())
1967  eraseInstruction(*PreheaderLoad, *SafetyInfo, CurAST, nullptr);
1968 
1969  return true;
1970 }
1971 
1972 /// Returns an owning pointer to an alias set which incorporates aliasing info
1973 /// from L and all subloops of L.
1974 /// FIXME: In new pass manager, there is no helper function to handle loop
1975 /// analysis such as cloneBasicBlockAnalysis, so the AST needs to be recomputed
1976 /// from scratch for every loop. Hook up with the helper functions when
1977 /// available in the new pass manager to avoid redundant computation.
1978 std::unique_ptr<AliasSetTracker>
1979 LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
1980  AliasAnalysis *AA) {
1981  std::unique_ptr<AliasSetTracker> CurAST;
1982  SmallVector<Loop *, 4> RecomputeLoops;
1983  for (Loop *InnerL : L->getSubLoops()) {
1984  auto MapI = LoopToAliasSetMap.find(InnerL);
1985  // If the AST for this inner loop is missing it may have been merged into
1986  // some other loop's AST and then that loop unrolled, and so we need to
1987  // recompute it.
1988  if (MapI == LoopToAliasSetMap.end()) {
1989  RecomputeLoops.push_back(InnerL);
1990  continue;
1991  }
1992  std::unique_ptr<AliasSetTracker> InnerAST = std::move(MapI->second);
1993 
1994  if (CurAST) {
1995  // What if InnerLoop was modified by other passes ?
1996  // Once we've incorporated the inner loop's AST into ours, we don't need
1997  // the subloop's anymore.
1998  CurAST->add(*InnerAST);
1999  } else {
2000  CurAST = std::move(InnerAST);
2001  }
2002  LoopToAliasSetMap.erase(MapI);
2003  }
2004  if (!CurAST)
2005  CurAST = make_unique<AliasSetTracker>(*AA);
2006 
2007  // Add everything from the sub loops that are no longer directly available.
2008  for (Loop *InnerL : RecomputeLoops)
2009  for (BasicBlock *BB : InnerL->blocks())
2010  CurAST->add(*BB);
2011 
2012  // And merge in this loop (without anything from inner loops).
2013  for (BasicBlock *BB : L->blocks())
2014  if (LI->getLoopFor(BB) == L)
2015  CurAST->add(*BB);
2016 
2017  return CurAST;
2018 }
2019 
2020 /// Simple analysis hook. Clone alias set info.
2021 ///
2022 void LegacyLICMPass::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
2023  Loop *L) {
2024  auto ASTIt = LICM.getLoopToAliasSetMap().find(L);
2025  if (ASTIt == LICM.getLoopToAliasSetMap().end())
2026  return;
2027 
2028  ASTIt->second->copyValue(From, To);
2029 }
2030 
2031 /// Simple Analysis hook. Delete value V from alias set
2032 ///
2033 void LegacyLICMPass::deleteAnalysisValue(Value *V, Loop *L) {
2034  auto ASTIt = LICM.getLoopToAliasSetMap().find(L);
2035  if (ASTIt == LICM.getLoopToAliasSetMap().end())
2036  return;
2037 
2038  ASTIt->second->deleteValue(V);
2039 }
2040 
2041 /// Simple Analysis hook. Delete value L from alias set map.
2042 ///
2043 void LegacyLICMPass::deleteAnalysisLoop(Loop *L) {
2044  if (!LICM.getLoopToAliasSetMap().count(L))
2045  return;
2046 
2047  LICM.getLoopToAliasSetMap().erase(L);
2048 }
2049 
2051  AliasSetTracker *CurAST, Loop *CurLoop,
2052  AliasAnalysis *AA) {
2053  // First check to see if any of the basic blocks in CurLoop invalidate *V.
2054  bool isInvalidatedAccordingToAST = CurAST->getAliasSetFor(MemLoc).isMod();
2055 
2056  if (!isInvalidatedAccordingToAST || !LICMN2Theshold)
2057  return isInvalidatedAccordingToAST;
2058 
2059  // Check with a diagnostic analysis if we can refine the information above.
2060  // This is to identify the limitations of using the AST.
2061  // The alias set mechanism used by LICM has a major weakness in that it
2062  // combines all things which may alias into a single set *before* asking
2063  // modref questions. As a result, a single readonly call within a loop will
2064  // collapse all loads and stores into a single alias set and report
2065  // invalidation if the loop contains any store. For example, readonly calls
2066  // with deopt states have this form and create a general alias set with all
2067  // loads and stores. In order to get any LICM in loops containing possible
2068  // deopt states we need a more precise invalidation of checking the mod ref
2069  // info of each instruction within the loop and LI. This has a complexity of
2070  // O(N^2), so currently, it is used only as a diagnostic tool since the
2071  // default value of LICMN2Threshold is zero.
2072 
2073  // Don't look at nested loops.
2074  if (CurLoop->begin() != CurLoop->end())
2075  return true;
2076 
2077  int N = 0;
2078  for (BasicBlock *BB : CurLoop->getBlocks())
2079  for (Instruction &I : *BB) {
2080  if (N >= LICMN2Theshold) {
2081  LLVM_DEBUG(dbgs() << "Alasing N2 threshold exhausted for "
2082  << *(MemLoc.Ptr) << "\n");
2083  return true;
2084  }
2085  N++;
2086  auto Res = AA->getModRefInfo(&I, MemLoc);
2087  if (isModSet(Res)) {
2088  LLVM_DEBUG(dbgs() << "Aliasing failed on " << I << " for "
2089  << *(MemLoc.Ptr) << "\n");
2090  return true;
2091  }
2092  }
2093  LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n");
2094  return false;
2095 }
2096 
2098  Loop *CurLoop) {
2100  // See declaration of EnableLicmCap for usage details.
2101  if (EnableLicmCap)
2102  Source = MU->getDefiningAccess();
2103  else
2104  Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(MU);
2105  return !MSSA->isLiveOnEntryDef(Source) &&
2106  CurLoop->contains(Source->getBlock());
2107 }
2108 
2109 /// Little predicate that returns true if the specified basic block is in
2110 /// a subloop of the current one, not the current one itself.
2111 ///
2112 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
2113  assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
2114  return LI->getLoopFor(BB) != CurLoop;
2115 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, AliasSetTracker *AST, MemorySSAUpdater *MSSAU)
Definition: LICM.cpp:1302
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:372
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Inform the safety info that we are planning to insert a new instruction Inst into the basic block BB...
Definition: MustExecute.cpp:86
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
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:1158
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
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
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:140
This class represents lattice values for constants.
Definition: AllocatorList.h:24
This header provides classes for managing a pipeline of passes over loops in LLVM IR...
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:255
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:215
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1199
iterator end()
Definition: Function.h:658
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static constexpr LocationSize unknown()
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
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess&#39;s for a given basic block.
Definition: MemorySSA.h:751
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value...
Definition: SSAUpdater.cpp:72
The main scalar evolution driver.
static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT, LoopInfo *LI, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU)
Definition: LICM.cpp:1355
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:254
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:630
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:1591
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:705
void insertUse(MemoryUse *Use)
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:1186
BasicBlock * getSuccessor(unsigned i) const
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:1167
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)
An instruction for reading from memory.
Definition: Instructions.h:168
Hexagon Common GEP
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
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
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
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
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:704
static bool pointerInvalidatedByLoop(MemoryLocation MemLoc, AliasSetTracker *CurAST, Loop *CurLoop, AliasAnalysis *AA)
Definition: LICM.cpp:2050
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
Loop Invariant Code Motion
Definition: LICM.cpp:275
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1135
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:364
Represents read-only accesses to memory.
Definition: MemorySSA.h:317
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:48
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:956
virtual void computeLoopSafetyInfo(const Loop *CurLoop)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:72
This is the interface for a SCEV-based alias analysis.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:371
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
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:690
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
Definition: MustExecute.h:124
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:701
static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU, Loop *CurLoop)
Definition: LICM.cpp:2097
uint32_t getTagID() const
Return the tag of this operand bundle as an integer.
Definition: InstrTypes.h:942
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef&#39;s and MemoryPhi&#39;s for a given basic block.
Definition: MemorySSA.h:759
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:285
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:945
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:158
virtual 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:68
BlockT * getHeader() const
Definition: LoopInfo.h:100
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Return the behavior of the given call site.
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:267
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: ...
void removeMemoryAccess(MemoryAccess *)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:43
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
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref&#39;ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:713
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:251
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries...
FunctionModRefBehavior
Summary of how a function affects memory in the program.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:269
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:65
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
An instruction for storing to memory.
Definition: Instructions.h:321
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:429
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
Definition: MustExecute.cpp:30
iterator begin()
Definition: Function.h:656
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.
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
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:854
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
NodeT * getBlock() const
static Instruction * sinkThroughTriviallyReplaceablePHI(PHINode *TPN, Instruction *I, LoopInfo *LI, SmallDenseMap< BasicBlock *, Instruction *, 32 > &SunkCopies, const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop, MemorySSAUpdater *MSSAU)
Definition: LICM.cpp:1319
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:423
virtual bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
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:190
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:217
virtual bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const =0
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:308
MemorySSAWalker * getSkipSelfWalker()
Definition: MemorySSA.cpp:1496
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
Definition: SetOperations.h:40
void 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:58
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
static cl::opt< bool > EnableLicmCap("enable-licm-cap", cl::init(false), cl::Hidden, cl::desc("Enable imprecision in LICM (uses MemorySSA cap) in " "pathological cases, in exchange for faster compile"))
Conditional or Unconditional Branch instruction.
size_t size(BasicBlock *BB) const
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
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:281
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:562
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:278
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:1193
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LICM.cpp:243
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
Definition: LICM.cpp:996
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 BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo)
Definition: LICM.cpp:1337
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1214
bool isMod() const
void setAlignment(unsigned Align)
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1415
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering defin...
bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *ORE)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block...
Definition: LICM.cpp:418
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT, Loop *CurLoop)
Definition: LICM.cpp:896
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.
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
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
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
size_type size() const
Definition: SmallPtrSet.h:93
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:334
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
static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU, 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:1529
Iterator for intrusive lists based on ilist_node.
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
Definition: MustExecute.cpp:92
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop) const
Returns true if we could not execute a memory-modifying instruction before we enter BB under assumpti...
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
#define DEBUG_TYPE
Definition: LICM.cpp:79
BlockVerifier::State From
static cl::opt< bool > ControlFlowHoisting("licm-control-flow-hoisting", cl::Hidden, cl::init(false), cl::desc("Enable control flow (and PHI) hoisting in LICM"))
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1776
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:378
iterator end()
Definition: BasicBlock.h:271
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:137
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:730
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock *> Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:644
BasicBlock * getBlock() const
Definition: MemorySSA.h:157
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
bool isConditional() const
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:1195
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...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:125
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:685
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU, 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:1427
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
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:245
A lightweight accessor for an operand bundle meant to be passed around by value.
Definition: InstrTypes.h:914
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:1582
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:568
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:379
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
iterator begin() const
Definition: SmallPtrSet.h:397
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:465
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:214
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:107
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:122
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
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:132
licm
Definition: LICM.cpp:275
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
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:731
Captures loop safety information.
Definition: MustExecute.h:48
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
const_iterator begin() const
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:173
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:425
bool empty() const
Definition: LoopInfo.h:146
bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *ORE)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block...
Definition: LICM.cpp:717
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:291
MemoryAccess * getClobberingMemoryAccess(const Instruction *I)
Given a memory Mod/Ref/ModRef&#39;ing instruction, calling this will give you the nearest dominating Memo...
Definition: MemorySSA.h:1016
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:2112
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock *> &, SmallVectorImpl< Instruction *> &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, Loop *, AliasSetTracker *, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *)
Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before ...
Definition: LICM.cpp:1723
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:376
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 ...
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
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:349
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:573
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:970
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.
static Instruction * CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU)
Definition: LICM.cpp:1227
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
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:181
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
#define LLVM_DEBUG(X)
Definition: Debug.h:123
op_range incoming_values()
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:174
The optimization diagnostic interface.
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
Definition: BasicBlock.cpp:121
bool use_empty() const
Definition: Value.h:323
static void moveInstructionBefore(Instruction &I, Instruction &Dest, ICFLoopSafetyInfo &SafetyInfo)
Definition: LICM.cpp:1312
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.
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=DefaultMaxUsesToExplore)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
user_iterator user_end()
Definition: Value.h:384
bool mayReadOrWriteMemory() const
Return true if this instruction may read or write memory.
Definition: Instruction.h:522
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
Definition: MustExecute.cpp:26