LLVM  9.0.0svn
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 
62 #include "llvm/ADT/SmallVector.h"
63 #include "llvm/ADT/StringRef.h"
68 #include "llvm/Analysis/LoopInfo.h"
69 #include "llvm/Analysis/LoopPass.h"
72 #include "llvm/IR/CallSite.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/Pass.h"
83 #include "llvm/Support/Casting.h"
85 #include "llvm/Support/Debug.h"
87 #include "llvm/Transforms/Scalar.h"
88 #include "llvm/Transforms/Utils.h"
91 #include <cassert>
92 #include <memory>
93 
94 using namespace llvm;
95 
96 #define DEBUG_TYPE "loop-versioning-licm"
97 
98 static const char *LICMVersioningMetaData = "llvm.loop.licm_versioning.disable";
99 
100 /// Threshold minimum allowed percentage for possible
101 /// invariant instructions in a loop.
102 static cl::opt<float>
103  LVInvarThreshold("licm-versioning-invariant-threshold",
104  cl::desc("LoopVersioningLICM's minimum allowed percentage"
105  "of possible invariant instructions per loop"),
106  cl::init(25), cl::Hidden);
107 
108 /// Threshold for maximum allowed loop nest/depth
110  "licm-versioning-max-depth-threshold",
111  cl::desc(
112  "LoopVersioningLICM's threshold for maximum allowed loop nest/depth"),
113  cl::init(2), cl::Hidden);
114 
115 /// Create MDNode for input string.
116 static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
117  LLVMContext &Context = TheLoop->getHeader()->getContext();
118  Metadata *MDs[] = {
119  MDString::get(Context, Name),
121  return MDNode::get(Context, MDs);
122 }
123 
124 /// Set input string into loop metadata by keeping other values intact.
125 void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
126  unsigned V) {
128  // If the loop already has metadata, retain it.
129  MDNode *LoopID = TheLoop->getLoopID();
130  if (LoopID) {
131  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
132  MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
133  MDs.push_back(Node);
134  }
135  }
136  // Add new metadata.
137  MDs.push_back(createStringMetadata(TheLoop, MDString, V));
138  // Replace current metadata node with new one.
139  LLVMContext &Context = TheLoop->getHeader()->getContext();
140  MDNode *NewLoopID = MDNode::get(Context, MDs);
141  // Set operand 0 to refer to the loop id itself.
142  NewLoopID->replaceOperandWith(0, NewLoopID);
143  TheLoop->setLoopID(NewLoopID);
144 }
145 
146 namespace {
147 
148 struct LoopVersioningLICM : public LoopPass {
149  static char ID;
150 
151  LoopVersioningLICM()
152  : LoopPass(ID), LoopDepthThreshold(LVLoopDepthThreshold),
153  InvariantThreshold(LVInvarThreshold) {
155  }
156 
157  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
158 
159  void getAnalysisUsage(AnalysisUsage &AU) const override {
160  AU.setPreservesCFG();
171  }
172 
173  StringRef getPassName() const override { return "Loop Versioning for LICM"; }
174 
175  void reset() {
176  AA = nullptr;
177  SE = nullptr;
178  LAA = nullptr;
179  CurLoop = nullptr;
180  LoadAndStoreCounter = 0;
181  InvariantCounter = 0;
182  IsReadOnlyLoop = true;
183  ORE = nullptr;
184  CurAST.reset();
185  }
186 
187  class AutoResetter {
188  public:
189  AutoResetter(LoopVersioningLICM &LVLICM) : LVLICM(LVLICM) {}
190  ~AutoResetter() { LVLICM.reset(); }
191 
192  private:
193  LoopVersioningLICM &LVLICM;
194  };
195 
196 private:
197  // Current AliasAnalysis information
198  AliasAnalysis *AA = nullptr;
199 
200  // Current ScalarEvolution
201  ScalarEvolution *SE = nullptr;
202 
203  // Current LoopAccessAnalysis
204  LoopAccessLegacyAnalysis *LAA = nullptr;
205 
206  // Current Loop's LoopAccessInfo
207  const LoopAccessInfo *LAI = nullptr;
208 
209  // The current loop we are working on.
210  Loop *CurLoop = nullptr;
211 
212  // AliasSet information for the current loop.
213  std::unique_ptr<AliasSetTracker> CurAST;
214 
215  // Maximum loop nest threshold
216  unsigned LoopDepthThreshold;
217 
218  // Minimum invariant threshold
219  float InvariantThreshold;
220 
221  // Counter to track num of load & store
222  unsigned LoadAndStoreCounter = 0;
223 
224  // Counter to track num of invariant
225  unsigned InvariantCounter = 0;
226 
227  // Read only loop marker.
228  bool IsReadOnlyLoop = true;
229 
230  // OptimizationRemarkEmitter
232 
233  bool isLegalForVersioning();
234  bool legalLoopStructure();
235  bool legalLoopInstructions();
236  bool legalLoopMemoryAccesses();
237  bool isLoopAlreadyVisited();
238  void setNoAliasToLoop(Loop *VerLoop);
239  bool instructionSafeForVersioning(Instruction *I);
240 };
241 
242 } // end anonymous namespace
243 
244 /// Check loop structure and confirms it's good for LoopVersioningLICM.
245 bool LoopVersioningLICM::legalLoopStructure() {
246  // Loop must be in loop simplify form.
247  if (!CurLoop->isLoopSimplifyForm()) {
248  LLVM_DEBUG(dbgs() << " loop is not in loop-simplify form.\n");
249  return false;
250  }
251  // Loop should be innermost loop, if not return false.
252  if (!CurLoop->getSubLoops().empty()) {
253  LLVM_DEBUG(dbgs() << " loop is not innermost\n");
254  return false;
255  }
256  // Loop should have a single backedge, if not return false.
257  if (CurLoop->getNumBackEdges() != 1) {
258  LLVM_DEBUG(dbgs() << " loop has multiple backedges\n");
259  return false;
260  }
261  // Loop must have a single exiting block, if not return false.
262  if (!CurLoop->getExitingBlock()) {
263  LLVM_DEBUG(dbgs() << " loop has multiple exiting block\n");
264  return false;
265  }
266  // We only handle bottom-tested loop, i.e. loop in which the condition is
267  // checked at the end of each iteration. With that we can assume that all
268  // instructions in the loop are executed the same number of times.
269  if (CurLoop->getExitingBlock() != CurLoop->getLoopLatch()) {
270  LLVM_DEBUG(dbgs() << " loop is not bottom tested\n");
271  return false;
272  }
273  // Parallel loops must not have aliasing loop-invariant memory accesses.
274  // Hence we don't need to version anything in this case.
275  if (CurLoop->isAnnotatedParallel()) {
276  LLVM_DEBUG(dbgs() << " Parallel loop is not worth versioning\n");
277  return false;
278  }
279  // Loop depth more then LoopDepthThreshold are not allowed
280  if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
281  LLVM_DEBUG(dbgs() << " loop depth is more then threshold\n");
282  return false;
283  }
284  // We need to be able to compute the loop trip count in order
285  // to generate the bound checks.
286  const SCEV *ExitCount = SE->getBackedgeTakenCount(CurLoop);
287  if (ExitCount == SE->getCouldNotCompute()) {
288  LLVM_DEBUG(dbgs() << " loop does not has trip count\n");
289  return false;
290  }
291  return true;
292 }
293 
294 /// Check memory accesses in loop and confirms it's good for
295 /// LoopVersioningLICM.
296 bool LoopVersioningLICM::legalLoopMemoryAccesses() {
297  bool HasMayAlias = false;
298  bool TypeSafety = false;
299  bool HasMod = false;
300  // Memory check:
301  // Transform phase will generate a versioned loop and also a runtime check to
302  // ensure the pointers are independent and they don’t alias.
303  // In version variant of loop, alias meta data asserts that all access are
304  // mutually independent.
305  //
306  // Pointers aliasing in alias domain are avoided because with multiple
307  // aliasing domains we may not be able to hoist potential loop invariant
308  // access out of the loop.
309  //
310  // Iterate over alias tracker sets, and confirm AliasSets doesn't have any
311  // must alias set.
312  for (const auto &I : *CurAST) {
313  const AliasSet &AS = I;
314  // Skip Forward Alias Sets, as this should be ignored as part of
315  // the AliasSetTracker object.
316  if (AS.isForwardingAliasSet())
317  continue;
318  // With MustAlias its not worth adding runtime bound check.
319  if (AS.isMustAlias())
320  return false;
321  Value *SomePtr = AS.begin()->getValue();
322  bool TypeCheck = true;
323  // Check for Mod & MayAlias
324  HasMayAlias |= AS.isMayAlias();
325  HasMod |= AS.isMod();
326  for (const auto &A : AS) {
327  Value *Ptr = A.getValue();
328  // Alias tracker should have pointers of same data type.
329  TypeCheck = (TypeCheck && (SomePtr->getType() == Ptr->getType()));
330  }
331  // At least one alias tracker should have pointers of same data type.
332  TypeSafety |= TypeCheck;
333  }
334  // Ensure types should be of same type.
335  if (!TypeSafety) {
336  LLVM_DEBUG(dbgs() << " Alias tracker type safety failed!\n");
337  return false;
338  }
339  // Ensure loop body shouldn't be read only.
340  if (!HasMod) {
341  LLVM_DEBUG(dbgs() << " No memory modified in loop body\n");
342  return false;
343  }
344  // Make sure alias set has may alias case.
345  // If there no alias memory ambiguity, return false.
346  if (!HasMayAlias) {
347  LLVM_DEBUG(dbgs() << " No ambiguity in memory access.\n");
348  return false;
349  }
350  return true;
351 }
352 
353 /// Check loop instructions safe for Loop versioning.
354 /// It returns true if it's safe else returns false.
355 /// Consider following:
356 /// 1) Check all load store in loop body are non atomic & non volatile.
357 /// 2) Check function call safety, by ensuring its not accessing memory.
358 /// 3) Loop body shouldn't have any may throw instruction.
359 /// 4) Loop body shouldn't have any convergent or noduplicate instructions.
360 bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
361  assert(I != nullptr && "Null instruction found!");
362  // Check function call safety
363  if (auto *Call = dyn_cast<CallBase>(I)) {
364  if (Call->isConvergent() || Call->cannotDuplicate()) {
365  LLVM_DEBUG(dbgs() << " Convergent call site found.\n");
366  return false;
367  }
368 
369  if (!AA->doesNotAccessMemory(Call)) {
370  LLVM_DEBUG(dbgs() << " Unsafe call site found.\n");
371  return false;
372  }
373  }
374 
375  // Avoid loops with possiblity of throw
376  if (I->mayThrow()) {
377  LLVM_DEBUG(dbgs() << " May throw instruction found in loop body\n");
378  return false;
379  }
380  // If current instruction is load instructions
381  // make sure it's a simple load (non atomic & non volatile)
382  if (I->mayReadFromMemory()) {
383  LoadInst *Ld = dyn_cast<LoadInst>(I);
384  if (!Ld || !Ld->isSimple()) {
385  LLVM_DEBUG(dbgs() << " Found a non-simple load.\n");
386  return false;
387  }
388  LoadAndStoreCounter++;
389  Value *Ptr = Ld->getPointerOperand();
390  // Check loop invariant.
391  if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
392  InvariantCounter++;
393  }
394  // If current instruction is store instruction
395  // make sure it's a simple store (non atomic & non volatile)
396  else if (I->mayWriteToMemory()) {
397  StoreInst *St = dyn_cast<StoreInst>(I);
398  if (!St || !St->isSimple()) {
399  LLVM_DEBUG(dbgs() << " Found a non-simple store.\n");
400  return false;
401  }
402  LoadAndStoreCounter++;
403  Value *Ptr = St->getPointerOperand();
404  // Check loop invariant.
405  if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
406  InvariantCounter++;
407 
408  IsReadOnlyLoop = false;
409  }
410  return true;
411 }
412 
413 /// Check loop instructions and confirms it's good for
414 /// LoopVersioningLICM.
415 bool LoopVersioningLICM::legalLoopInstructions() {
416  // Resetting counters.
417  LoadAndStoreCounter = 0;
418  InvariantCounter = 0;
419  IsReadOnlyLoop = true;
420  using namespace ore;
421  // Iterate over loop blocks and instructions of each block and check
422  // instruction safety.
423  for (auto *Block : CurLoop->getBlocks())
424  for (auto &Inst : *Block) {
425  // If instruction is unsafe just return false.
426  if (!instructionSafeForVersioning(&Inst)) {
427  ORE->emit([&]() {
428  return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)
429  << " Unsafe Loop Instruction";
430  });
431  return false;
432  }
433  }
434  // Get LoopAccessInfo from current loop.
435  LAI = &LAA->getInfo(CurLoop);
436  // Check LoopAccessInfo for need of runtime check.
437  if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
438  LLVM_DEBUG(dbgs() << " LAA: Runtime check not found !!\n");
439  return false;
440  }
441  // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
442  if (LAI->getNumRuntimePointerChecks() >
444  LLVM_DEBUG(
445  dbgs() << " LAA: Runtime checks are more than threshold !!\n");
446  ORE->emit([&]() {
447  return OptimizationRemarkMissed(DEBUG_TYPE, "RuntimeCheck",
448  CurLoop->getStartLoc(),
449  CurLoop->getHeader())
450  << "Number of runtime checks "
451  << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks())
452  << " exceeds threshold "
454  });
455  return false;
456  }
457  // Loop should have at least one invariant load or store instruction.
458  if (!InvariantCounter) {
459  LLVM_DEBUG(dbgs() << " Invariant not found !!\n");
460  return false;
461  }
462  // Read only loop not allowed.
463  if (IsReadOnlyLoop) {
464  LLVM_DEBUG(dbgs() << " Found a read-only loop!\n");
465  return false;
466  }
467  // Profitablity check:
468  // Check invariant threshold, should be in limit.
469  if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
470  LLVM_DEBUG(
471  dbgs()
472  << " Invariant load & store are less then defined threshold\n");
473  LLVM_DEBUG(dbgs() << " Invariant loads & stores: "
474  << ((InvariantCounter * 100) / LoadAndStoreCounter)
475  << "%\n");
476  LLVM_DEBUG(dbgs() << " Invariant loads & store threshold: "
477  << InvariantThreshold << "%\n");
478  ORE->emit([&]() {
479  return OptimizationRemarkMissed(DEBUG_TYPE, "InvariantThreshold",
480  CurLoop->getStartLoc(),
481  CurLoop->getHeader())
482  << "Invariant load & store "
483  << NV("LoadAndStoreCounter",
484  ((InvariantCounter * 100) / LoadAndStoreCounter))
485  << " are less then defined threshold "
486  << NV("Threshold", InvariantThreshold);
487  });
488  return false;
489  }
490  return true;
491 }
492 
493 /// It checks loop is already visited or not.
494 /// check loop meta data, if loop revisited return true
495 /// else false.
496 bool LoopVersioningLICM::isLoopAlreadyVisited() {
497  // Check LoopVersioningLICM metadata into loop
498  if (findStringMetadataForLoop(CurLoop, LICMVersioningMetaData)) {
499  return true;
500  }
501  return false;
502 }
503 
504 /// Checks legality for LoopVersioningLICM by considering following:
505 /// a) loop structure legality b) loop instruction legality
506 /// c) loop memory access legality.
507 /// Return true if legal else returns false.
508 bool LoopVersioningLICM::isLegalForVersioning() {
509  using namespace ore;
510  LLVM_DEBUG(dbgs() << "Loop: " << *CurLoop);
511  // Make sure not re-visiting same loop again.
512  if (isLoopAlreadyVisited()) {
513  LLVM_DEBUG(
514  dbgs() << " Revisiting loop in LoopVersioningLICM not allowed.\n\n");
515  return false;
516  }
517  // Check loop structure leagality.
518  if (!legalLoopStructure()) {
519  LLVM_DEBUG(
520  dbgs() << " Loop structure not suitable for LoopVersioningLICM\n\n");
521  ORE->emit([&]() {
522  return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopStruct",
523  CurLoop->getStartLoc(),
524  CurLoop->getHeader())
525  << " Unsafe Loop structure";
526  });
527  return false;
528  }
529  // Check loop instruction leagality.
530  if (!legalLoopInstructions()) {
531  LLVM_DEBUG(
532  dbgs()
533  << " Loop instructions not suitable for LoopVersioningLICM\n\n");
534  return false;
535  }
536  // Check loop memory access leagality.
537  if (!legalLoopMemoryAccesses()) {
538  LLVM_DEBUG(
539  dbgs()
540  << " Loop memory access not suitable for LoopVersioningLICM\n\n");
541  ORE->emit([&]() {
542  return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopMemoryAccess",
543  CurLoop->getStartLoc(),
544  CurLoop->getHeader())
545  << " Unsafe Loop memory access";
546  });
547  return false;
548  }
549  // Loop versioning is feasible, return true.
550  LLVM_DEBUG(dbgs() << " Loop Versioning found to be beneficial\n\n");
551  ORE->emit([&]() {
552  return OptimizationRemark(DEBUG_TYPE, "IsLegalForVersioning",
553  CurLoop->getStartLoc(), CurLoop->getHeader())
554  << " Versioned loop for LICM."
555  << " Number of runtime checks we had to insert "
556  << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks());
557  });
558  return true;
559 }
560 
561 /// Update loop with aggressive aliasing assumptions.
562 /// It marks no-alias to any pairs of memory operations by assuming
563 /// loop should not have any must-alias memory accesses pairs.
564 /// During LoopVersioningLICM legality we ignore loops having must
565 /// aliasing memory accesses.
566 void LoopVersioningLICM::setNoAliasToLoop(Loop *VerLoop) {
567  // Get latch terminator instruction.
568  Instruction *I = VerLoop->getLoopLatch()->getTerminator();
569  // Create alias scope domain.
570  MDBuilder MDB(I->getContext());
571  MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("LVDomain");
572  StringRef Name = "LVAliasScope";
574  MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
575  // Iterate over each instruction of loop.
576  // set no-alias for all load & store instructions.
577  for (auto *Block : CurLoop->getBlocks()) {
578  for (auto &Inst : *Block) {
579  // Only interested in instruction that may modify or read memory.
580  if (!Inst.mayReadFromMemory() && !Inst.mayWriteToMemory())
581  continue;
582  Scopes.push_back(NewScope);
583  NoAliases.push_back(NewScope);
584  // Set no-alias for current instruction.
585  Inst.setMetadata(
588  MDNode::get(Inst.getContext(), NoAliases)));
589  // set alias-scope for current instruction.
590  Inst.setMetadata(
593  MDNode::get(Inst.getContext(), Scopes)));
594  }
595  }
596 }
597 
598 bool LoopVersioningLICM::runOnLoop(Loop *L, LPPassManager &LPM) {
599  // This will automatically release all resources hold by the current
600  // LoopVersioningLICM object.
601  AutoResetter Resetter(*this);
602 
603  if (skipLoop(L))
604  return false;
605 
606  // Do not do the transformation if disabled by metadata.
608  return false;
609 
610  // Get Analysis information.
611  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
612  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
613  LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
614  ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
615  LAI = nullptr;
616  // Set Current Loop
617  CurLoop = L;
618  CurAST.reset(new AliasSetTracker(*AA));
619 
620  // Loop over the body of this loop, construct AST.
621  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
622  for (auto *Block : L->getBlocks()) {
623  if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
624  CurAST->add(*Block); // Incorporate the specified basic block
625  }
626 
627  bool Changed = false;
628 
629  // Check feasiblity of LoopVersioningLICM.
630  // If versioning found to be feasible and beneficial then proceed
631  // else simply return, by cleaning up memory.
632  if (isLegalForVersioning()) {
633  // Do loop versioning.
634  // Create memcheck for memory accessed inside loop.
635  // Clone original loop, and set blocks properly.
636  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
637  LoopVersioning LVer(*LAI, CurLoop, LI, DT, SE, true);
638  LVer.versionLoop();
639  // Set Loop Versioning metaData for original loop.
641  // Set Loop Versioning metaData for version loop.
643  // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
644  // FIXME: "llvm.mem.parallel_loop_access" annotates memory access
645  // instructions, not loops.
647  "llvm.mem.parallel_loop_access");
648  // Update version loop with aggressive aliasing assumption.
649  setNoAliasToLoop(LVer.getVersionedLoop());
650  Changed = true;
651  }
652  return Changed;
653 }
654 
655 char LoopVersioningLICM::ID = 0;
656 
657 INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm",
658  "Loop Versioning For LICM", false, false)
662 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
665 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
668 INITIALIZE_PASS_END(LoopVersioningLICM, "loop-versioning-licm",
669  "Loop Versioning For LICM", false, false)
670 
671 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:80
static unsigned RuntimeMemoryCheckThreshold
performing memory disambiguation checks at runtime do not make more than this number of comparisons...
bool isSimple() const
Definition: Instructions.h:276
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:224
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
LLVMContext & Context
DiagnosticInfoOptimizationBase::Argument NV
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:858
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:453
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:720
Metadata node.
Definition: Metadata.h:863
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
An instruction for reading from memory.
Definition: Instructions.h:167
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
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:858
static const char * LICMVersioningMetaData
bool isMustAlias() const
BlockT * getHeader() const
Definition: LoopInfo.h:102
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
iterator begin() const
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:471
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:320
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:409
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:144
Loop * getVersionedLoop()
Returns the versioned loop.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
#define DEBUG_TYPE
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
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:467
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:284
bool isMod() const
Pass * createLoopVersioningLICMPass()
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
char & LoopSimplifyID
The transformation should not be applied.
Definition: LoopUtils.h:227
void initializeLoopVersioningLICMPass(PassRegistry &)
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:314
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
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:631
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
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:132
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:447
This class represents an analyzed expression in the program.
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:467
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:151
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
Definition: Metadata.cpp:895
#define I(x, y, z)
Definition: MD5.cpp:58
bool mayReadFromMemory() const
Return true if this instruction may read memory.
Optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopUtils.cpp:199
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:332
TransformationMode hasLICMVersioningTransformation(Loop *L)
Definition: LoopUtils.cpp:419
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:72
OptimizationRemarkEmitter legacy analysis pass.
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1138
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
A single uniqued string.
Definition: Metadata.h:603
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
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:401
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Root of the metadata hierarchy.
Definition: Metadata.h:57
Value * getPointerOperand()
Definition: Instructions.h:412
Loop * getNonVersionedLoop()
Returns the fall-back loop.
The optimization diagnostic interface.
loop versioning Loop Versioning For LICM