LLVM  14.0.0git
LoopVersioningLICM.cpp
Go to the documentation of this file.
1 //===- LoopVersioningLICM.cpp - LICM Loop Versioning ----------------------===//
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 // When alias analysis is uncertain about the aliasing between any two accesses,
10 // it will return MayAlias. This uncertainty from alias analysis restricts LICM
11 // from proceeding further. In cases where alias analysis is uncertain we might
12 // use loop versioning as an alternative.
13 //
14 // Loop Versioning will create a version of the loop with aggressive aliasing
15 // assumptions in addition to the original with conservative (default) aliasing
16 // assumptions. The version of the loop making aggressive aliasing assumptions
17 // will have all the memory accesses marked as no-alias. These two versions of
18 // loop will be preceded by a memory runtime check. This runtime check consists
19 // of bound checks for all unique memory accessed in loop, and it ensures the
20 // lack of memory aliasing. The result of the runtime check determines which of
21 // the loop versions is executed: If the runtime check detects any memory
22 // aliasing, then the original loop is executed. Otherwise, the version with
23 // aggressive aliasing assumptions is used.
24 //
25 // Following are the top level steps:
26 //
27 // a) Perform LoopVersioningLICM's feasibility check.
28 // b) If loop is a candidate for versioning then create a memory bound check,
29 // by considering all the memory accesses in loop body.
30 // c) Clone original loop and set all memory accesses as no-alias in new loop.
31 // d) Set original loop & versioned loop as a branch target of the runtime check
32 // result.
33 //
34 // It transforms loop as shown below:
35 //
36 // +----------------+
37 // |Runtime Memcheck|
38 // +----------------+
39 // |
40 // +----------+----------------+----------+
41 // | |
42 // +---------+----------+ +-----------+----------+
43 // |Orig Loop Preheader | |Cloned Loop Preheader |
44 // +--------------------+ +----------------------+
45 // | |
46 // +--------------------+ +----------------------+
47 // |Orig Loop Body | |Cloned Loop Body |
48 // +--------------------+ +----------------------+
49 // | |
50 // +--------------------+ +----------------------+
51 // |Orig Loop Exit Block| |Cloned Loop Exit Block|
52 // +--------------------+ +-----------+----------+
53 // | |
54 // +----------+--------------+-----------+
55 // |
56 // +-----+----+
57 // |Join Block|
58 // +----------+
59 //
60 //===----------------------------------------------------------------------===//
61 
63 #include "llvm/ADT/SmallVector.h"
64 #include "llvm/ADT/StringRef.h"
69 #include "llvm/Analysis/LoopInfo.h"
70 #include "llvm/Analysis/LoopPass.h"
73 #include "llvm/IR/Constants.h"
74 #include "llvm/IR/Dominators.h"
75 #include "llvm/IR/Instruction.h"
76 #include "llvm/IR/Instructions.h"
77 #include "llvm/IR/LLVMContext.h"
78 #include "llvm/IR/MDBuilder.h"
79 #include "llvm/IR/Metadata.h"
80 #include "llvm/IR/Type.h"
81 #include "llvm/IR/Value.h"
82 #include "llvm/InitializePasses.h"
83 #include "llvm/Pass.h"
84 #include "llvm/Support/Casting.h"
86 #include "llvm/Support/Debug.h"
88 #include "llvm/Transforms/Scalar.h"
89 #include "llvm/Transforms/Utils.h"
92 #include <cassert>
93 #include <memory>
94 
95 using namespace llvm;
96 
97 #define DEBUG_TYPE "loop-versioning-licm"
98 
99 static const char *LICMVersioningMetaData = "llvm.loop.licm_versioning.disable";
100 
101 /// Threshold minimum allowed percentage for possible
102 /// invariant instructions in a loop.
103 static cl::opt<float>
104  LVInvarThreshold("licm-versioning-invariant-threshold",
105  cl::desc("LoopVersioningLICM's minimum allowed percentage"
106  "of possible invariant instructions per loop"),
107  cl::init(25), cl::Hidden);
108 
109 /// Threshold for maximum allowed loop nest/depth
111  "licm-versioning-max-depth-threshold",
112  cl::desc(
113  "LoopVersioningLICM's threshold for maximum allowed loop nest/depth"),
114  cl::init(2), cl::Hidden);
115 
116 namespace {
117 
118 struct LoopVersioningLICMLegacyPass : public LoopPass {
119  static char ID;
120 
121  LoopVersioningLICMLegacyPass() : LoopPass(ID) {
124  }
125 
126  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
127 
128  StringRef getPassName() const override { return "Loop Versioning for LICM"; }
129 
130  void getAnalysisUsage(AnalysisUsage &AU) const override {
131  AU.setPreservesCFG();
142  }
143 };
144 
145 struct LoopVersioningLICM {
146  // We don't explicitly pass in LoopAccessInfo to the constructor since the
147  // loop versioning might return early due to instructions that are not safe
148  // for versioning. By passing the proxy instead the construction of
149  // LoopAccessInfo will take place only when it's necessary.
150  LoopVersioningLICM(AliasAnalysis *AA, ScalarEvolution *SE,
152  function_ref<const LoopAccessInfo &(Loop *)> GetLAI)
153  : AA(AA), SE(SE), GetLAI(GetLAI),
154  LoopDepthThreshold(LVLoopDepthThreshold),
155  InvariantThreshold(LVInvarThreshold), ORE(ORE) {}
156 
157  bool runOnLoop(Loop *L, LoopInfo *LI, DominatorTree *DT);
158 
159  void reset() {
160  AA = nullptr;
161  SE = nullptr;
162  CurLoop = nullptr;
163  LoadAndStoreCounter = 0;
164  InvariantCounter = 0;
165  IsReadOnlyLoop = true;
166  ORE = nullptr;
167  CurAST.reset();
168  }
169 
170  class AutoResetter {
171  public:
172  AutoResetter(LoopVersioningLICM &LVLICM) : LVLICM(LVLICM) {}
173  ~AutoResetter() { LVLICM.reset(); }
174 
175  private:
176  LoopVersioningLICM &LVLICM;
177  };
178 
179 private:
180  // Current AliasAnalysis information
181  AliasAnalysis *AA = nullptr;
182 
183  // Current ScalarEvolution
184  ScalarEvolution *SE = nullptr;
185 
186  // Current Loop's LoopAccessInfo
187  const LoopAccessInfo *LAI = nullptr;
188 
189  // Proxy for retrieving LoopAccessInfo.
190  function_ref<const LoopAccessInfo &(Loop *)> GetLAI;
191 
192  // The current loop we are working on.
193  Loop *CurLoop = nullptr;
194 
195  // AliasSet information for the current loop.
196  std::unique_ptr<AliasSetTracker> CurAST;
197 
198  // Maximum loop nest threshold
199  unsigned LoopDepthThreshold;
200 
201  // Minimum invariant threshold
202  float InvariantThreshold;
203 
204  // Counter to track num of load & store
205  unsigned LoadAndStoreCounter = 0;
206 
207  // Counter to track num of invariant
208  unsigned InvariantCounter = 0;
209 
210  // Read only loop marker.
211  bool IsReadOnlyLoop = true;
212 
213  // OptimizationRemarkEmitter
215 
216  bool isLegalForVersioning();
217  bool legalLoopStructure();
218  bool legalLoopInstructions();
219  bool legalLoopMemoryAccesses();
220  bool isLoopAlreadyVisited();
221  void setNoAliasToLoop(Loop *VerLoop);
222  bool instructionSafeForVersioning(Instruction *I);
223 };
224 
225 } // end anonymous namespace
226 
227 /// Check loop structure and confirms it's good for LoopVersioningLICM.
228 bool LoopVersioningLICM::legalLoopStructure() {
229  // Loop must be in loop simplify form.
230  if (!CurLoop->isLoopSimplifyForm()) {
231  LLVM_DEBUG(dbgs() << " loop is not in loop-simplify form.\n");
232  return false;
233  }
234  // Loop should be innermost loop, if not return false.
235  if (!CurLoop->getSubLoops().empty()) {
236  LLVM_DEBUG(dbgs() << " loop is not innermost\n");
237  return false;
238  }
239  // Loop should have a single backedge, if not return false.
240  if (CurLoop->getNumBackEdges() != 1) {
241  LLVM_DEBUG(dbgs() << " loop has multiple backedges\n");
242  return false;
243  }
244  // Loop must have a single exiting block, if not return false.
245  if (!CurLoop->getExitingBlock()) {
246  LLVM_DEBUG(dbgs() << " loop has multiple exiting block\n");
247  return false;
248  }
249  // We only handle bottom-tested loop, i.e. loop in which the condition is
250  // checked at the end of each iteration. With that we can assume that all
251  // instructions in the loop are executed the same number of times.
252  if (CurLoop->getExitingBlock() != CurLoop->getLoopLatch()) {
253  LLVM_DEBUG(dbgs() << " loop is not bottom tested\n");
254  return false;
255  }
256  // Parallel loops must not have aliasing loop-invariant memory accesses.
257  // Hence we don't need to version anything in this case.
258  if (CurLoop->isAnnotatedParallel()) {
259  LLVM_DEBUG(dbgs() << " Parallel loop is not worth versioning\n");
260  return false;
261  }
262  // Loop depth more then LoopDepthThreshold are not allowed
263  if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
264  LLVM_DEBUG(dbgs() << " loop depth is more then threshold\n");
265  return false;
266  }
267  // We need to be able to compute the loop trip count in order
268  // to generate the bound checks.
269  const SCEV *ExitCount = SE->getBackedgeTakenCount(CurLoop);
270  if (isa<SCEVCouldNotCompute>(ExitCount)) {
271  LLVM_DEBUG(dbgs() << " loop does not has trip count\n");
272  return false;
273  }
274  return true;
275 }
276 
277 /// Check memory accesses in loop and confirms it's good for
278 /// LoopVersioningLICM.
279 bool LoopVersioningLICM::legalLoopMemoryAccesses() {
280  bool HasMayAlias = false;
281  bool TypeSafety = false;
282  bool HasMod = false;
283  // Memory check:
284  // Transform phase will generate a versioned loop and also a runtime check to
285  // ensure the pointers are independent and they don’t alias.
286  // In version variant of loop, alias meta data asserts that all access are
287  // mutually independent.
288  //
289  // Pointers aliasing in alias domain are avoided because with multiple
290  // aliasing domains we may not be able to hoist potential loop invariant
291  // access out of the loop.
292  //
293  // Iterate over alias tracker sets, and confirm AliasSets doesn't have any
294  // must alias set.
295  for (const auto &I : *CurAST) {
296  const AliasSet &AS = I;
297  // Skip Forward Alias Sets, as this should be ignored as part of
298  // the AliasSetTracker object.
299  if (AS.isForwardingAliasSet())
300  continue;
301  // With MustAlias its not worth adding runtime bound check.
302  if (AS.isMustAlias())
303  return false;
304  Value *SomePtr = AS.begin()->getValue();
305  bool TypeCheck = true;
306  // Check for Mod & MayAlias
307  HasMayAlias |= AS.isMayAlias();
308  HasMod |= AS.isMod();
309  for (const auto &A : AS) {
310  Value *Ptr = A.getValue();
311  // Alias tracker should have pointers of same data type.
312  TypeCheck = (TypeCheck && (SomePtr->getType() == Ptr->getType()));
313  }
314  // At least one alias tracker should have pointers of same data type.
315  TypeSafety |= TypeCheck;
316  }
317  // Ensure types should be of same type.
318  if (!TypeSafety) {
319  LLVM_DEBUG(dbgs() << " Alias tracker type safety failed!\n");
320  return false;
321  }
322  // Ensure loop body shouldn't be read only.
323  if (!HasMod) {
324  LLVM_DEBUG(dbgs() << " No memory modified in loop body\n");
325  return false;
326  }
327  // Make sure alias set has may alias case.
328  // If there no alias memory ambiguity, return false.
329  if (!HasMayAlias) {
330  LLVM_DEBUG(dbgs() << " No ambiguity in memory access.\n");
331  return false;
332  }
333  return true;
334 }
335 
336 /// Check loop instructions safe for Loop versioning.
337 /// It returns true if it's safe else returns false.
338 /// Consider following:
339 /// 1) Check all load store in loop body are non atomic & non volatile.
340 /// 2) Check function call safety, by ensuring its not accessing memory.
341 /// 3) Loop body shouldn't have any may throw instruction.
342 /// 4) Loop body shouldn't have any convergent or noduplicate instructions.
343 bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
344  assert(I != nullptr && "Null instruction found!");
345  // Check function call safety
346  if (auto *Call = dyn_cast<CallBase>(I)) {
347  if (Call->isConvergent() || Call->cannotDuplicate()) {
348  LLVM_DEBUG(dbgs() << " Convergent call site found.\n");
349  return false;
350  }
351 
352  if (!AA->doesNotAccessMemory(Call)) {
353  LLVM_DEBUG(dbgs() << " Unsafe call site found.\n");
354  return false;
355  }
356  }
357 
358  // Avoid loops with possiblity of throw
359  if (I->mayThrow()) {
360  LLVM_DEBUG(dbgs() << " May throw instruction found in loop body\n");
361  return false;
362  }
363  // If current instruction is load instructions
364  // make sure it's a simple load (non atomic & non volatile)
365  if (I->mayReadFromMemory()) {
366  LoadInst *Ld = dyn_cast<LoadInst>(I);
367  if (!Ld || !Ld->isSimple()) {
368  LLVM_DEBUG(dbgs() << " Found a non-simple load.\n");
369  return false;
370  }
371  LoadAndStoreCounter++;
372  Value *Ptr = Ld->getPointerOperand();
373  // Check loop invariant.
374  if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
375  InvariantCounter++;
376  }
377  // If current instruction is store instruction
378  // make sure it's a simple store (non atomic & non volatile)
379  else if (I->mayWriteToMemory()) {
380  StoreInst *St = dyn_cast<StoreInst>(I);
381  if (!St || !St->isSimple()) {
382  LLVM_DEBUG(dbgs() << " Found a non-simple store.\n");
383  return false;
384  }
385  LoadAndStoreCounter++;
386  Value *Ptr = St->getPointerOperand();
387  // Check loop invariant.
388  if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
389  InvariantCounter++;
390 
391  IsReadOnlyLoop = false;
392  }
393  return true;
394 }
395 
396 /// Check loop instructions and confirms it's good for
397 /// LoopVersioningLICM.
398 bool LoopVersioningLICM::legalLoopInstructions() {
399  // Resetting counters.
400  LoadAndStoreCounter = 0;
401  InvariantCounter = 0;
402  IsReadOnlyLoop = true;
403  using namespace ore;
404  // Iterate over loop blocks and instructions of each block and check
405  // instruction safety.
406  for (auto *Block : CurLoop->getBlocks())
407  for (auto &Inst : *Block) {
408  // If instruction is unsafe just return false.
409  if (!instructionSafeForVersioning(&Inst)) {
410  ORE->emit([&]() {
411  return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)
412  << " Unsafe Loop Instruction";
413  });
414  return false;
415  }
416  }
417  // Get LoopAccessInfo from current loop via the proxy.
418  LAI = &GetLAI(CurLoop);
419  // Check LoopAccessInfo for need of runtime check.
420  if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
421  LLVM_DEBUG(dbgs() << " LAA: Runtime check not found !!\n");
422  return false;
423  }
424  // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
425  if (LAI->getNumRuntimePointerChecks() >
427  LLVM_DEBUG(
428  dbgs() << " LAA: Runtime checks are more than threshold !!\n");
429  ORE->emit([&]() {
430  return OptimizationRemarkMissed(DEBUG_TYPE, "RuntimeCheck",
431  CurLoop->getStartLoc(),
432  CurLoop->getHeader())
433  << "Number of runtime checks "
434  << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks())
435  << " exceeds threshold "
437  });
438  return false;
439  }
440  // Loop should have at least one invariant load or store instruction.
441  if (!InvariantCounter) {
442  LLVM_DEBUG(dbgs() << " Invariant not found !!\n");
443  return false;
444  }
445  // Read only loop not allowed.
446  if (IsReadOnlyLoop) {
447  LLVM_DEBUG(dbgs() << " Found a read-only loop!\n");
448  return false;
449  }
450  // Profitablity check:
451  // Check invariant threshold, should be in limit.
452  if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
453  LLVM_DEBUG(
454  dbgs()
455  << " Invariant load & store are less then defined threshold\n");
456  LLVM_DEBUG(dbgs() << " Invariant loads & stores: "
457  << ((InvariantCounter * 100) / LoadAndStoreCounter)
458  << "%\n");
459  LLVM_DEBUG(dbgs() << " Invariant loads & store threshold: "
460  << InvariantThreshold << "%\n");
461  ORE->emit([&]() {
462  return OptimizationRemarkMissed(DEBUG_TYPE, "InvariantThreshold",
463  CurLoop->getStartLoc(),
464  CurLoop->getHeader())
465  << "Invariant load & store "
466  << NV("LoadAndStoreCounter",
467  ((InvariantCounter * 100) / LoadAndStoreCounter))
468  << " are less then defined threshold "
469  << NV("Threshold", InvariantThreshold);
470  });
471  return false;
472  }
473  return true;
474 }
475 
476 /// It checks loop is already visited or not.
477 /// check loop meta data, if loop revisited return true
478 /// else false.
479 bool LoopVersioningLICM::isLoopAlreadyVisited() {
480  // Check LoopVersioningLICM metadata into loop
482  return true;
483  }
484  return false;
485 }
486 
487 /// Checks legality for LoopVersioningLICM by considering following:
488 /// a) loop structure legality b) loop instruction legality
489 /// c) loop memory access legality.
490 /// Return true if legal else returns false.
491 bool LoopVersioningLICM::isLegalForVersioning() {
492  using namespace ore;
493  LLVM_DEBUG(dbgs() << "Loop: " << *CurLoop);
494  // Make sure not re-visiting same loop again.
495  if (isLoopAlreadyVisited()) {
496  LLVM_DEBUG(
497  dbgs() << " Revisiting loop in LoopVersioningLICM not allowed.\n\n");
498  return false;
499  }
500  // Check loop structure leagality.
501  if (!legalLoopStructure()) {
502  LLVM_DEBUG(
503  dbgs() << " Loop structure not suitable for LoopVersioningLICM\n\n");
504  ORE->emit([&]() {
505  return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopStruct",
506  CurLoop->getStartLoc(),
507  CurLoop->getHeader())
508  << " Unsafe Loop structure";
509  });
510  return false;
511  }
512  // Check loop instruction leagality.
513  if (!legalLoopInstructions()) {
514  LLVM_DEBUG(
515  dbgs()
516  << " Loop instructions not suitable for LoopVersioningLICM\n\n");
517  return false;
518  }
519  // Check loop memory access leagality.
520  if (!legalLoopMemoryAccesses()) {
521  LLVM_DEBUG(
522  dbgs()
523  << " Loop memory access not suitable for LoopVersioningLICM\n\n");
524  ORE->emit([&]() {
525  return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopMemoryAccess",
526  CurLoop->getStartLoc(),
527  CurLoop->getHeader())
528  << " Unsafe Loop memory access";
529  });
530  return false;
531  }
532  // Loop versioning is feasible, return true.
533  LLVM_DEBUG(dbgs() << " Loop Versioning found to be beneficial\n\n");
534  ORE->emit([&]() {
535  return OptimizationRemark(DEBUG_TYPE, "IsLegalForVersioning",
536  CurLoop->getStartLoc(), CurLoop->getHeader())
537  << " Versioned loop for LICM."
538  << " Number of runtime checks we had to insert "
539  << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks());
540  });
541  return true;
542 }
543 
544 /// Update loop with aggressive aliasing assumptions.
545 /// It marks no-alias to any pairs of memory operations by assuming
546 /// loop should not have any must-alias memory accesses pairs.
547 /// During LoopVersioningLICM legality we ignore loops having must
548 /// aliasing memory accesses.
549 void LoopVersioningLICM::setNoAliasToLoop(Loop *VerLoop) {
550  // Get latch terminator instruction.
551  Instruction *I = VerLoop->getLoopLatch()->getTerminator();
552  // Create alias scope domain.
553  MDBuilder MDB(I->getContext());
554  MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("LVDomain");
555  StringRef Name = "LVAliasScope";
556  MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
557  SmallVector<Metadata *, 4> Scopes{NewScope}, NoAliases{NewScope};
558  // Iterate over each instruction of loop.
559  // set no-alias for all load & store instructions.
560  for (auto *Block : CurLoop->getBlocks()) {
561  for (auto &Inst : *Block) {
562  // Only interested in instruction that may modify or read memory.
563  if (!Inst.mayReadFromMemory() && !Inst.mayWriteToMemory())
564  continue;
565  // Set no-alias for current instruction.
566  Inst.setMetadata(
567  LLVMContext::MD_noalias,
568  MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_noalias),
569  MDNode::get(Inst.getContext(), NoAliases)));
570  // set alias-scope for current instruction.
571  Inst.setMetadata(
572  LLVMContext::MD_alias_scope,
573  MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_alias_scope),
574  MDNode::get(Inst.getContext(), Scopes)));
575  }
576  }
577 }
578 
579 bool LoopVersioningLICMLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
580  if (skipLoop(L))
581  return false;
582 
583  AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
584  ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
586  &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
587  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
588  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
589 
590  auto GetLAI = [&](Loop *L) -> const LoopAccessInfo & {
591  return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(L);
592  };
593 
594  return LoopVersioningLICM(AA, SE, ORE, GetLAI).runOnLoop(L, LI, DT);
595 }
596 
597 bool LoopVersioningLICM::runOnLoop(Loop *L, LoopInfo *LI, DominatorTree *DT) {
598  // This will automatically release all resources hold by the current
599  // LoopVersioningLICM object.
600  AutoResetter Resetter(*this);
601 
602  // Do not do the transformation if disabled by metadata.
604  return false;
605 
606  // Set Current Loop
607  CurLoop = L;
608  CurAST.reset(new AliasSetTracker(*AA));
609 
610  // Loop over the body of this loop, construct AST.
611  for (auto *Block : L->getBlocks()) {
612  if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
613  CurAST->add(*Block); // Incorporate the specified basic block
614  }
615 
616  bool Changed = false;
617 
618  // Check feasiblity of LoopVersioningLICM.
619  // If versioning found to be feasible and beneficial then proceed
620  // else simply return, by cleaning up memory.
621  if (isLegalForVersioning()) {
622  // Do loop versioning.
623  // Create memcheck for memory accessed inside loop.
624  // Clone original loop, and set blocks properly.
625  LoopVersioning LVer(*LAI, LAI->getRuntimePointerChecking()->getChecks(),
626  CurLoop, LI, DT, SE);
627  LVer.versionLoop();
628  // Set Loop Versioning metaData for original loop.
629  addStringMetadataToLoop(LVer.getNonVersionedLoop(), LICMVersioningMetaData);
630  // Set Loop Versioning metaData for version loop.
631  addStringMetadataToLoop(LVer.getVersionedLoop(), LICMVersioningMetaData);
632  // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
633  // FIXME: "llvm.mem.parallel_loop_access" annotates memory access
634  // instructions, not loops.
635  addStringMetadataToLoop(LVer.getVersionedLoop(),
636  "llvm.mem.parallel_loop_access");
637  // Update version loop with aggressive aliasing assumption.
638  setNoAliasToLoop(LVer.getVersionedLoop());
639  Changed = true;
640  }
641  return Changed;
642 }
643 
645 
646 INITIALIZE_PASS_BEGIN(LoopVersioningLICMLegacyPass, "loop-versioning-licm",
647  "Loop Versioning For LICM", false, false)
651 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
654 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
657 INITIALIZE_PASS_END(LoopVersioningLICMLegacyPass, "loop-versioning-licm",
658  "Loop Versioning For LICM", false, false)
659 
661  return new LoopVersioningLICMLegacyPass();
662 }
663 
664 namespace llvm {
665 
668  LPMUpdater &U) {
669  AliasAnalysis *AA = &LAR.AA;
670  ScalarEvolution *SE = &LAR.SE;
671  DominatorTree *DT = &LAR.DT;
672  LoopInfo *LI = &LAR.LI;
673  const Function *F = L.getHeader()->getParent();
675 
676  auto GetLAI = [&](Loop *L) -> const LoopAccessInfo & {
677  return AM.getResult<LoopAccessAnalysis>(*L, LAR);
678  };
679 
680  if (!LoopVersioningLICM(AA, SE, &ORE, GetLAI).runOnLoop(&L, LI, DT))
681  return PreservedAnalyses::all();
683 }
684 } // namespace llvm
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::OptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: DiagnosticInfo.h:729
llvm::LoopAccessLegacyAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:714
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopVersioningLICMLegacyPass, "loop-versioning-licm", "Loop Versioning For LICM", false, false) INITIALIZE_PASS_END(LoopVersioningLICMLegacyPass
Metadata.h
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
Scalar.h
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
StringRef.h
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::AliasSet::isMod
bool isMod() const
Definition: AliasSetTracker.h:205
LoopAccessAnalysis.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
GlobalsModRef.h
llvm::AliasSetTracker
Definition: AliasSetTracker.h:329
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::LoopAccessAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:756
ScalarEvolution.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::LoopVersioningLICMPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &LAR, LPMUpdater &U)
Definition: LoopVersioningLICM.cpp:666
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:267
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1208
F
#define F(x, y, z)
Definition: MD5.cpp:56
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
CommandLine.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::AAResults
Definition: AliasAnalysis.h:508
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::createLoopVersioningLICMPass
Pass * createLoopVersioningLICMPass()
Definition: LoopVersioningLICM.cpp:660
LVLoopDepthThreshold
static cl::opt< unsigned > LVLoopDepthThreshold("licm-versioning-max-depth-threshold", cl::desc("LoopVersioningLICM's threshold for maximum allowed loop nest/depth"), cl::init(2), cl::Hidden)
Threshold for maximum allowed loop nest/depth.
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::AliasSet
Definition: AliasSetTracker.h:49
llvm::StoreInst::isSimple
bool isSimple() const
Definition: Instructions.h:390
false
Definition: StackSlotColoring.cpp:142
llvm::AliasSet::isForwardingAliasSet
bool isForwardingAliasSet() const
Return true if this alias set should be ignored as part of the AliasSetTracker object.
Definition: AliasSetTracker.h:211
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:171
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
MDBuilder.h
llvm::initializeLoopVersioningLICMLegacyPassPass
void initializeLoopVersioningLICMLegacyPassPass(PassRegistry &)
LoopUtils.h
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2066
llvm::LPPassManager
Definition: LoopPass.h:75
llvm::hasLICMVersioningTransformation
TransformationMode hasLICMVersioningTransformation(const Loop *L)
Definition: LoopUtils.cpp:445
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
Utils.h
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4066
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:140
llvm::findStringMetadataForLoop
Optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopInfo.cpp:1054
llvm::cl::opt
Definition: CommandLine.h:1434
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
LICM
loop versioning Loop Versioning For LICM
Definition: LoopVersioningLICM.cpp:658
llvm::LoopPass
Definition: LoopPass.h:27
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:249
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LoopVersioning
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
Definition: LoopVersioning.h:40
llvm::addStringMetadataToLoop
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
Definition: LoopUtils.cpp:222
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:515
llvm::AliasSet::isMayAlias
bool isMayAlias() const
Definition: AliasSetTracker.h:207
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::TM_Disable
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:275
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
llvm::VectorizerParams::RuntimeMemoryCheckThreshold
static unsigned RuntimeMemoryCheckThreshold
\When performing memory disambiguation checks at runtime do not make more than this number of compari...
Definition: LoopAccessAnalysis.h:50
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
LICMVersioningMetaData
static const char * LICMVersioningMetaData
Definition: LoopVersioningLICM.cpp:99
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::LoadInst::isSimple
bool isSimple() const
Definition: Instructions.h:259
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LoopVersioningLICM.cpp:97
LoopPass.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::MDNode::concatenate
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
Definition: Metadata.cpp:914
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:56
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:148
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:12614
LoopVersioningLICM.h
llvm::LCSSAID
char & LCSSAID
Definition: LCSSA.cpp:485
llvm::OptimizationRemarkEmitterWrapperPass
OptimizationRemarkEmitter legacy analysis pass.
Definition: OptimizationRemarkEmitter.h:146
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:800
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Casting.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
LoopVersioning.h
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::LoopStandardAnalysisResults::AA
AAResults & AA
Definition: LoopAnalysisManager.h:53
llvm::MDBuilder
Definition: MDBuilder.h:35
licm
loop versioning licm
Definition: LoopVersioningLICM.cpp:657
llvm::AliasSet::begin
iterator begin() const
Definition: AliasSetTracker.h:219
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:684
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
llvm::AAResults::doesNotAccessMemory
bool doesNotAccessMemory(const CallBase *Call)
Checks if the specified call is known to never read or write memory.
Definition: AliasAnalysis.h:629
SmallVector.h
llvm::StoreInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:401
Dominators.h
NoAliases
static cl::opt< bool > NoAliases("csky-no-aliases", cl::desc("Disable the emission of assembler pseudo instructions"), cl::init(false), cl::Hidden)
llvm::AliasSet::isMustAlias
bool isMustAlias() const
Definition: AliasSetTracker.h:206
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1336
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
AliasSetTracker.h
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:267
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
llvm::cl::desc
Definition: CommandLine.h:414
raw_ostream.h
llvm::ScalarEvolution::getBackedgeTakenCount
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
Definition: ScalarEvolution.cpp:7279
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
LVInvarThreshold
static cl::opt< float > LVInvarThreshold("licm-versioning-invariant-threshold", cl::desc("LoopVersioningLICM's minimum allowed percentage" "of possible invariant instructions per loop"), cl::init(25), cl::Hidden)
Threshold minimum allowed percentage for possible invariant instructions in a loop.
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37