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