LLVM  8.0.0svn
LoopVersioningLICM.cpp
Go to the documentation of this file.
1 //===- LoopVersioningLICM.cpp - LICM Loop Versioning ----------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // When alias analysis is uncertain about the aliasing between any two accesses,
11 // it will return MayAlias. This uncertainty from alias analysis restricts LICM
12 // from proceeding further. In cases where alias analysis is uncertain we might
13 // use loop versioning as an alternative.
14 //
15 // Loop Versioning will create a version of the loop with aggressive aliasing
16 // assumptions in addition to the original with conservative (default) aliasing
17 // assumptions. The version of the loop making aggressive aliasing assumptions
18 // will have all the memory accesses marked as no-alias. These two versions of
19 // loop will be preceded by a memory runtime check. This runtime check consists
20 // of bound checks for all unique memory accessed in loop, and it ensures the
21 // lack of memory aliasing. The result of the runtime check determines which of
22 // the loop versions is executed: If the runtime check detects any memory
23 // aliasing, then the original loop is executed. Otherwise, the version with
24 // aggressive aliasing assumptions is used.
25 //
26 // Following are the top level steps:
27 //
28 // a) Perform LoopVersioningLICM's feasibility check.
29 // b) If loop is a candidate for versioning then create a memory bound check,
30 // by considering all the memory accesses in loop body.
31 // c) Clone original loop and set all memory accesses as no-alias in new loop.
32 // d) Set original loop & versioned loop as a branch target of the runtime check
33 // result.
34 //
35 // It transforms loop as shown below:
36 //
37 // +----------------+
38 // |Runtime Memcheck|
39 // +----------------+
40 // |
41 // +----------+----------------+----------+
42 // | |
43 // +---------+----------+ +-----------+----------+
44 // |Orig Loop Preheader | |Cloned Loop Preheader |
45 // +--------------------+ +----------------------+
46 // | |
47 // +--------------------+ +----------------------+
48 // |Orig Loop Body | |Cloned Loop Body |
49 // +--------------------+ +----------------------+
50 // | |
51 // +--------------------+ +----------------------+
52 // |Orig Loop Exit Block| |Cloned Loop Exit Block|
53 // +--------------------+ +-----------+----------+
54 // | |
55 // +----------+--------------+-----------+
56 // |
57 // +-----+----+
58 // |Join Block|
59 // +----------+
60 //
61 //===----------------------------------------------------------------------===//
62 
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/CallSite.h"
74 #include "llvm/IR/Constants.h"
75 #include "llvm/IR/Dominators.h"
76 #include "llvm/IR/Instruction.h"
77 #include "llvm/IR/Instructions.h"
78 #include "llvm/IR/LLVMContext.h"
79 #include "llvm/IR/MDBuilder.h"
80 #include "llvm/IR/Metadata.h"
81 #include "llvm/IR/Type.h"
82 #include "llvm/IR/Value.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 /// Create MDNode for input string.
117 static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
118  LLVMContext &Context = TheLoop->getHeader()->getContext();
119  Metadata *MDs[] = {
120  MDString::get(Context, Name),
122  return MDNode::get(Context, MDs);
123 }
124 
125 /// Set input string into loop metadata by keeping other values intact.
126 void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
127  unsigned V) {
129  // If the loop already has metadata, retain it.
130  MDNode *LoopID = TheLoop->getLoopID();
131  if (LoopID) {
132  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
133  MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
134  MDs.push_back(Node);
135  }
136  }
137  // Add new metadata.
138  MDs.push_back(createStringMetadata(TheLoop, MDString, V));
139  // Replace current metadata node with new one.
140  LLVMContext &Context = TheLoop->getHeader()->getContext();
141  MDNode *NewLoopID = MDNode::get(Context, MDs);
142  // Set operand 0 to refer to the loop id itself.
143  NewLoopID->replaceOperandWith(0, NewLoopID);
144  TheLoop->setLoopID(NewLoopID);
145 }
146 
147 namespace {
148 
149 struct LoopVersioningLICM : public LoopPass {
150  static char ID;
151 
152  LoopVersioningLICM()
153  : LoopPass(ID), LoopDepthThreshold(LVLoopDepthThreshold),
154  InvariantThreshold(LVInvarThreshold) {
156  }
157 
158  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
159 
160  void getAnalysisUsage(AnalysisUsage &AU) const override {
161  AU.setPreservesCFG();
172  }
173 
174  StringRef getPassName() const override { return "Loop Versioning for LICM"; }
175 
176  void reset() {
177  AA = nullptr;
178  SE = nullptr;
179  LAA = nullptr;
180  CurLoop = nullptr;
181  LoadAndStoreCounter = 0;
182  InvariantCounter = 0;
183  IsReadOnlyLoop = true;
184  ORE = nullptr;
185  CurAST.reset();
186  }
187 
188  class AutoResetter {
189  public:
190  AutoResetter(LoopVersioningLICM &LVLICM) : LVLICM(LVLICM) {}
191  ~AutoResetter() { LVLICM.reset(); }
192 
193  private:
194  LoopVersioningLICM &LVLICM;
195  };
196 
197 private:
198  // Current AliasAnalysis information
199  AliasAnalysis *AA = nullptr;
200 
201  // Current ScalarEvolution
202  ScalarEvolution *SE = nullptr;
203 
204  // Current LoopAccessAnalysis
205  LoopAccessLegacyAnalysis *LAA = nullptr;
206 
207  // Current Loop's LoopAccessInfo
208  const LoopAccessInfo *LAI = nullptr;
209 
210  // The current loop we are working on.
211  Loop *CurLoop = nullptr;
212 
213  // AliasSet information for the current loop.
214  std::unique_ptr<AliasSetTracker> CurAST;
215 
216  // Maximum loop nest threshold
217  unsigned LoopDepthThreshold;
218 
219  // Minimum invariant threshold
220  float InvariantThreshold;
221 
222  // Counter to track num of load & store
223  unsigned LoadAndStoreCounter = 0;
224 
225  // Counter to track num of invariant
226  unsigned InvariantCounter = 0;
227 
228  // Read only loop marker.
229  bool IsReadOnlyLoop = true;
230 
231  // OptimizationRemarkEmitter
233 
234  bool isLegalForVersioning();
235  bool legalLoopStructure();
236  bool legalLoopInstructions();
237  bool legalLoopMemoryAccesses();
238  bool isLoopAlreadyVisited();
239  void setNoAliasToLoop(Loop *VerLoop);
240  bool instructionSafeForVersioning(Instruction *I);
241 };
242 
243 } // end anonymous namespace
244 
245 /// Check loop structure and confirms it's good for LoopVersioningLICM.
246 bool LoopVersioningLICM::legalLoopStructure() {
247  // Loop must be in loop simplify form.
248  if (!CurLoop->isLoopSimplifyForm()) {
249  LLVM_DEBUG(dbgs() << " loop is not in loop-simplify form.\n");
250  return false;
251  }
252  // Loop should be innermost loop, if not return false.
253  if (!CurLoop->getSubLoops().empty()) {
254  LLVM_DEBUG(dbgs() << " loop is not innermost\n");
255  return false;
256  }
257  // Loop should have a single backedge, if not return false.
258  if (CurLoop->getNumBackEdges() != 1) {
259  LLVM_DEBUG(dbgs() << " loop has multiple backedges\n");
260  return false;
261  }
262  // Loop must have a single exiting block, if not return false.
263  if (!CurLoop->getExitingBlock()) {
264  LLVM_DEBUG(dbgs() << " loop has multiple exiting block\n");
265  return false;
266  }
267  // We only handle bottom-tested loop, i.e. loop in which the condition is
268  // checked at the end of each iteration. With that we can assume that all
269  // instructions in the loop are executed the same number of times.
270  if (CurLoop->getExitingBlock() != CurLoop->getLoopLatch()) {
271  LLVM_DEBUG(dbgs() << " loop is not bottom tested\n");
272  return false;
273  }
274  // Parallel loops must not have aliasing loop-invariant memory accesses.
275  // Hence we don't need to version anything in this case.
276  if (CurLoop->isAnnotatedParallel()) {
277  LLVM_DEBUG(dbgs() << " Parallel loop is not worth versioning\n");
278  return false;
279  }
280  // Loop depth more then LoopDepthThreshold are not allowed
281  if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
282  LLVM_DEBUG(dbgs() << " loop depth is more then threshold\n");
283  return false;
284  }
285  // We need to be able to compute the loop trip count in order
286  // to generate the bound checks.
287  const SCEV *ExitCount = SE->getBackedgeTakenCount(CurLoop);
288  if (ExitCount == SE->getCouldNotCompute()) {
289  LLVM_DEBUG(dbgs() << " loop does not has trip count\n");
290  return false;
291  }
292  return true;
293 }
294 
295 /// Check memory accesses in loop and confirms it's good for
296 /// LoopVersioningLICM.
297 bool LoopVersioningLICM::legalLoopMemoryAccesses() {
298  bool HasMayAlias = false;
299  bool TypeSafety = false;
300  bool HasMod = false;
301  // Memory check:
302  // Transform phase will generate a versioned loop and also a runtime check to
303  // ensure the pointers are independent and they don’t alias.
304  // In version variant of loop, alias meta data asserts that all access are
305  // mutually independent.
306  //
307  // Pointers aliasing in alias domain are avoided because with multiple
308  // aliasing domains we may not be able to hoist potential loop invariant
309  // access out of the loop.
310  //
311  // Iterate over alias tracker sets, and confirm AliasSets doesn't have any
312  // must alias set.
313  for (const auto &I : *CurAST) {
314  const AliasSet &AS = I;
315  // Skip Forward Alias Sets, as this should be ignored as part of
316  // the AliasSetTracker object.
317  if (AS.isForwardingAliasSet())
318  continue;
319  // With MustAlias its not worth adding runtime bound check.
320  if (AS.isMustAlias())
321  return false;
322  Value *SomePtr = AS.begin()->getValue();
323  bool TypeCheck = true;
324  // Check for Mod & MayAlias
325  HasMayAlias |= AS.isMayAlias();
326  HasMod |= AS.isMod();
327  for (const auto &A : AS) {
328  Value *Ptr = A.getValue();
329  // Alias tracker should have pointers of same data type.
330  TypeCheck = (TypeCheck && (SomePtr->getType() == Ptr->getType()));
331  }
332  // At least one alias tracker should have pointers of same data type.
333  TypeSafety |= TypeCheck;
334  }
335  // Ensure types should be of same type.
336  if (!TypeSafety) {
337  LLVM_DEBUG(dbgs() << " Alias tracker type safety failed!\n");
338  return false;
339  }
340  // Ensure loop body shouldn't be read only.
341  if (!HasMod) {
342  LLVM_DEBUG(dbgs() << " No memory modified in loop body\n");
343  return false;
344  }
345  // Make sure alias set has may alias case.
346  // If there no alias memory ambiguity, return false.
347  if (!HasMayAlias) {
348  LLVM_DEBUG(dbgs() << " No ambiguity in memory access.\n");
349  return false;
350  }
351  return true;
352 }
353 
354 /// Check loop instructions safe for Loop versioning.
355 /// It returns true if it's safe else returns false.
356 /// Consider following:
357 /// 1) Check all load store in loop body are non atomic & non volatile.
358 /// 2) Check function call safety, by ensuring its not accessing memory.
359 /// 3) Loop body shouldn't have any may throw instruction.
360 bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
361  assert(I != nullptr && "Null instruction found!");
362  // Check function call safety
363  if (isa<CallInst>(I) && !AA->doesNotAccessMemory(CallSite(I))) {
364  LLVM_DEBUG(dbgs() << " Unsafe call site found.\n");
365  return false;
366  }
367  // Avoid loops with possiblity of throw
368  if (I->mayThrow()) {
369  LLVM_DEBUG(dbgs() << " May throw instruction found in loop body\n");
370  return false;
371  }
372  // If current instruction is load instructions
373  // make sure it's a simple load (non atomic & non volatile)
374  if (I->mayReadFromMemory()) {
375  LoadInst *Ld = dyn_cast<LoadInst>(I);
376  if (!Ld || !Ld->isSimple()) {
377  LLVM_DEBUG(dbgs() << " Found a non-simple load.\n");
378  return false;
379  }
380  LoadAndStoreCounter++;
381  Value *Ptr = Ld->getPointerOperand();
382  // Check loop invariant.
383  if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
384  InvariantCounter++;
385  }
386  // If current instruction is store instruction
387  // make sure it's a simple store (non atomic & non volatile)
388  else if (I->mayWriteToMemory()) {
389  StoreInst *St = dyn_cast<StoreInst>(I);
390  if (!St || !St->isSimple()) {
391  LLVM_DEBUG(dbgs() << " Found a non-simple store.\n");
392  return false;
393  }
394  LoadAndStoreCounter++;
395  Value *Ptr = St->getPointerOperand();
396  // Check loop invariant.
397  if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
398  InvariantCounter++;
399 
400  IsReadOnlyLoop = false;
401  }
402  return true;
403 }
404 
405 /// Check loop instructions and confirms it's good for
406 /// LoopVersioningLICM.
407 bool LoopVersioningLICM::legalLoopInstructions() {
408  // Resetting counters.
409  LoadAndStoreCounter = 0;
410  InvariantCounter = 0;
411  IsReadOnlyLoop = true;
412  using namespace ore;
413  // Iterate over loop blocks and instructions of each block and check
414  // instruction safety.
415  for (auto *Block : CurLoop->getBlocks())
416  for (auto &Inst : *Block) {
417  // If instruction is unsafe just return false.
418  if (!instructionSafeForVersioning(&Inst)) {
419  ORE->emit([&]() {
420  return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)
421  << " Unsafe Loop Instruction";
422  });
423  return false;
424  }
425  }
426  // Get LoopAccessInfo from current loop.
427  LAI = &LAA->getInfo(CurLoop);
428  // Check LoopAccessInfo for need of runtime check.
429  if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
430  LLVM_DEBUG(dbgs() << " LAA: Runtime check not found !!\n");
431  return false;
432  }
433  // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
434  if (LAI->getNumRuntimePointerChecks() >
436  LLVM_DEBUG(
437  dbgs() << " LAA: Runtime checks are more than threshold !!\n");
438  ORE->emit([&]() {
439  return OptimizationRemarkMissed(DEBUG_TYPE, "RuntimeCheck",
440  CurLoop->getStartLoc(),
441  CurLoop->getHeader())
442  << "Number of runtime checks "
443  << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks())
444  << " exceeds threshold "
446  });
447  return false;
448  }
449  // Loop should have at least one invariant load or store instruction.
450  if (!InvariantCounter) {
451  LLVM_DEBUG(dbgs() << " Invariant not found !!\n");
452  return false;
453  }
454  // Read only loop not allowed.
455  if (IsReadOnlyLoop) {
456  LLVM_DEBUG(dbgs() << " Found a read-only loop!\n");
457  return false;
458  }
459  // Profitablity check:
460  // Check invariant threshold, should be in limit.
461  if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
462  LLVM_DEBUG(
463  dbgs()
464  << " Invariant load & store are less then defined threshold\n");
465  LLVM_DEBUG(dbgs() << " Invariant loads & stores: "
466  << ((InvariantCounter * 100) / LoadAndStoreCounter)
467  << "%\n");
468  LLVM_DEBUG(dbgs() << " Invariant loads & store threshold: "
469  << InvariantThreshold << "%\n");
470  ORE->emit([&]() {
471  return OptimizationRemarkMissed(DEBUG_TYPE, "InvariantThreshold",
472  CurLoop->getStartLoc(),
473  CurLoop->getHeader())
474  << "Invariant load & store "
475  << NV("LoadAndStoreCounter",
476  ((InvariantCounter * 100) / LoadAndStoreCounter))
477  << " are less then defined threshold "
478  << NV("Threshold", InvariantThreshold);
479  });
480  return false;
481  }
482  return true;
483 }
484 
485 /// It checks loop is already visited or not.
486 /// check loop meta data, if loop revisited return true
487 /// else false.
488 bool LoopVersioningLICM::isLoopAlreadyVisited() {
489  // Check LoopVersioningLICM metadata into loop
490  if (findStringMetadataForLoop(CurLoop, LICMVersioningMetaData)) {
491  return true;
492  }
493  return false;
494 }
495 
496 /// Checks legality for LoopVersioningLICM by considering following:
497 /// a) loop structure legality b) loop instruction legality
498 /// c) loop memory access legality.
499 /// Return true if legal else returns false.
500 bool LoopVersioningLICM::isLegalForVersioning() {
501  using namespace ore;
502  LLVM_DEBUG(dbgs() << "Loop: " << *CurLoop);
503  // Make sure not re-visiting same loop again.
504  if (isLoopAlreadyVisited()) {
505  LLVM_DEBUG(
506  dbgs() << " Revisiting loop in LoopVersioningLICM not allowed.\n\n");
507  return false;
508  }
509  // Check loop structure leagality.
510  if (!legalLoopStructure()) {
511  LLVM_DEBUG(
512  dbgs() << " Loop structure not suitable for LoopVersioningLICM\n\n");
513  ORE->emit([&]() {
514  return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopStruct",
515  CurLoop->getStartLoc(),
516  CurLoop->getHeader())
517  << " Unsafe Loop structure";
518  });
519  return false;
520  }
521  // Check loop instruction leagality.
522  if (!legalLoopInstructions()) {
523  LLVM_DEBUG(
524  dbgs()
525  << " Loop instructions not suitable for LoopVersioningLICM\n\n");
526  return false;
527  }
528  // Check loop memory access leagality.
529  if (!legalLoopMemoryAccesses()) {
530  LLVM_DEBUG(
531  dbgs()
532  << " Loop memory access not suitable for LoopVersioningLICM\n\n");
533  ORE->emit([&]() {
534  return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopMemoryAccess",
535  CurLoop->getStartLoc(),
536  CurLoop->getHeader())
537  << " Unsafe Loop memory access";
538  });
539  return false;
540  }
541  // Loop versioning is feasible, return true.
542  LLVM_DEBUG(dbgs() << " Loop Versioning found to be beneficial\n\n");
543  ORE->emit([&]() {
544  return OptimizationRemark(DEBUG_TYPE, "IsLegalForVersioning",
545  CurLoop->getStartLoc(), CurLoop->getHeader())
546  << " Versioned loop for LICM."
547  << " Number of runtime checks we had to insert "
548  << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks());
549  });
550  return true;
551 }
552 
553 /// Update loop with aggressive aliasing assumptions.
554 /// It marks no-alias to any pairs of memory operations by assuming
555 /// loop should not have any must-alias memory accesses pairs.
556 /// During LoopVersioningLICM legality we ignore loops having must
557 /// aliasing memory accesses.
558 void LoopVersioningLICM::setNoAliasToLoop(Loop *VerLoop) {
559  // Get latch terminator instruction.
560  Instruction *I = VerLoop->getLoopLatch()->getTerminator();
561  // Create alias scope domain.
562  MDBuilder MDB(I->getContext());
563  MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("LVDomain");
564  StringRef Name = "LVAliasScope";
566  MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
567  // Iterate over each instruction of loop.
568  // set no-alias for all load & store instructions.
569  for (auto *Block : CurLoop->getBlocks()) {
570  for (auto &Inst : *Block) {
571  // Only interested in instruction that may modify or read memory.
572  if (!Inst.mayReadFromMemory() && !Inst.mayWriteToMemory())
573  continue;
574  Scopes.push_back(NewScope);
575  NoAliases.push_back(NewScope);
576  // Set no-alias for current instruction.
577  Inst.setMetadata(
580  MDNode::get(Inst.getContext(), NoAliases)));
581  // set alias-scope for current instruction.
582  Inst.setMetadata(
585  MDNode::get(Inst.getContext(), Scopes)));
586  }
587  }
588 }
589 
590 bool LoopVersioningLICM::runOnLoop(Loop *L, LPPassManager &LPM) {
591  // This will automatically release all resources hold by the current
592  // LoopVersioningLICM object.
593  AutoResetter Resetter(*this);
594 
595  if (skipLoop(L))
596  return false;
597  // Get Analysis information.
598  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
599  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
600  LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
601  ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
602  LAI = nullptr;
603  // Set Current Loop
604  CurLoop = L;
605  CurAST.reset(new AliasSetTracker(*AA));
606 
607  // Loop over the body of this loop, construct AST.
608  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
609  for (auto *Block : L->getBlocks()) {
610  if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
611  CurAST->add(*Block); // Incorporate the specified basic block
612  }
613 
614  bool Changed = false;
615 
616  // Check feasiblity of LoopVersioningLICM.
617  // If versioning found to be feasible and beneficial then proceed
618  // else simply return, by cleaning up memory.
619  if (isLegalForVersioning()) {
620  // Do loop versioning.
621  // Create memcheck for memory accessed inside loop.
622  // Clone original loop, and set blocks properly.
623  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
624  LoopVersioning LVer(*LAI, CurLoop, LI, DT, SE, true);
625  LVer.versionLoop();
626  // Set Loop Versioning metaData for original loop.
628  // Set Loop Versioning metaData for version loop.
630  // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
632  "llvm.mem.parallel_loop_access");
633  // Update version loop with aggressive aliasing assumption.
634  setNoAliasToLoop(LVer.getVersionedLoop());
635  Changed = true;
636  }
637  return Changed;
638 }
639 
640 char LoopVersioningLICM::ID = 0;
641 
642 INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm",
643  "Loop Versioning For LICM", false, false)
647 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
650 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
653 INITIALIZE_PASS_END(LoopVersioningLICM, "loop-versioning-licm",
654  "Loop Versioning For LICM", false, false)
655 
656 Pass *llvm::createLoopVersioningLICMPass() { return new LoopVersioningLICM(); }
Legacy wrapper pass to provide the GlobalsAAResult object.
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
static unsigned RuntimeMemoryCheckThreshold
performing memory disambiguation checks at runtime do not make more than this number of comparisons...
bool isSimple() const
Definition: Instructions.h:266
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Diagnostic information for missed-optimization remarks.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:225
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
LLVMContext & Context
DiagnosticInfoOptimizationBase::Argument NV
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool isMayAlias() const
This is the interface for a simple mod/ref and alias analysis over globals.
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:859
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:454
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.
The main scalar evolution driver.
This file contains the declarations for metadata subclasses.
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm", "Loop Versioning For LICM", false, false) INITIALIZE_PASS_END(LoopVersioningLICM
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:714
Metadata node.
Definition: Metadata.h:864
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1069
An instruction for reading from memory.
Definition: Instructions.h:168
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
static const char * LICMVersioningMetaData
bool isMustAlias() const
BlockT * getHeader() const
Definition: LoopInfo.h:100
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
iterator begin() const
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:239
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.
An instruction for storing to memory.
Definition: Instructions.h:310
void versionLoop()
Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:410
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
Loop * getVersionedLoop()
Returns the versioned loop.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1166
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
#define DEBUG_TYPE
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
This analysis provides dependence information for the memory accesses of a loop.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
char & LCSSAID
Definition: LCSSA.cpp:424
bool mayThrow() const
Return true if this instruction may throw an exception.
Diagnostic information for applied optimization remarks.
Represent the analysis usage information of a pass.
Value * getPointerOperand()
Definition: Instructions.h:274
bool isMod() const
Pass * createLoopVersioningLICMPass()
Optional< const MDOperand * > findStringMetadataForLoop(Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopUtils.cpp:191
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
char & LoopSimplifyID
void initializeLoopVersioningLICMPass(PassRegistry &)
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:299
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
loop versioning licm
Drive the analysis of memory accesses in the loop.
static cl::opt< bool > NoAliases("riscv-no-aliases", cl::desc("Disable the emission of assembler pseudo instructions"), cl::init(false), cl::Hidden)
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
This class emits a version of the loop where run-time checks ensure that may-alias pointers can&#39;t ove...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:215
This class represents an analyzed expression in the program.
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:149
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
Definition: Metadata.cpp:896
#define I(x, y, z)
Definition: MD5.cpp:58
bool mayReadFromMemory() const
Return true if this instruction may read memory.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static MDNode * createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V)
Create MDNode for input string.
LLVM Value Representation.
Definition: Value.h:73
OptimizationRemarkEmitter legacy analysis pass.
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
A single uniqued string.
Definition: Metadata.h:604
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
bool isForwardingAliasSet() const
Return true if this alias set should be ignored as part of the AliasSetTracker object.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
bool isSimple() const
Definition: Instructions.h:391
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1075
#define LLVM_DEBUG(X)
Definition: Debug.h:123
Root of the metadata hierarchy.
Definition: Metadata.h:58
Value * getPointerOperand()
Definition: Instructions.h:402
Loop * getNonVersionedLoop()
Returns the fall-back loop.
The optimization diagnostic interface.
loop versioning Loop Versioning For LICM