lib/Transforms/Scalar/LoopVersioningLICM.cpp

   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/MapVector.h"
  64 #include "llvm/ADT/SmallPtrSet.h"
  65 #include "llvm/ADT/Statistic.h"
  66 #include "llvm/ADT/StringExtras.h"
  67 #include "llvm/Analysis/AliasAnalysis.h"
  68 #include "llvm/Analysis/AliasSetTracker.h"
  69 #include "llvm/Analysis/ConstantFolding.h"
  70 #include "llvm/Analysis/GlobalsModRef.h"
  71 #include "llvm/Analysis/LoopAccessAnalysis.h"
  72 #include "llvm/Analysis/LoopInfo.h"
  73 #include "llvm/Analysis/LoopPass.h"
  74 #include "llvm/Analysis/ScalarEvolution.h"
  75 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  76 #include "llvm/Analysis/TargetLibraryInfo.h"
  77 #include "llvm/Analysis/ValueTracking.h"
  78 #include "llvm/Analysis/VectorUtils.h"
  79 #include "llvm/IR/Dominators.h"
  80 #include "llvm/IR/IntrinsicInst.h"
  81 #include "llvm/IR/MDBuilder.h"
  82 #include "llvm/IR/PatternMatch.h"
  83 #include "llvm/IR/PredIteratorCache.h"
  84 #include "llvm/IR/Type.h"
  85 #include "llvm/Support/Debug.h"
  86 #include "llvm/Support/raw_ostream.h"
  87 #include "llvm/Transforms/Scalar.h"
  88 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  89 #include "llvm/Transforms/Utils/Cloning.h"
  90 #include "llvm/Transforms/Utils/LoopUtils.h"
  91 #include "llvm/Transforms/Utils/LoopVersioning.h"
  92 #include "llvm/Transforms/Utils/ValueMapper.h"
  93
  94 #define DEBUG_TYPE "loop-versioning-licm"
  95 static const char* LICMVersioningMetaData =
  96     "llvm.loop.licm_versioning.disable";
  97
  98 using namespace llvm;
  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
 109 static cl::opt<unsigned> LVLoopDepthThreshold(
 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 /// \brief 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),
 120       ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context), V))};
 121   return MDNode::get(Context, MDs);
 122 }
 123
 124 /// \brief Set input string into loop metadata by keeping other values intact.
 125 void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
 126                                    unsigned V) {
 127   SmallVector<Metadata *, 4> MDs(1);
 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 struct LoopVersioningLICM : public LoopPass {
 148   static char ID;
 149
 150   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 151
 152   void getAnalysisUsage(AnalysisUsage &AU) const override {
 153     AU.setPreservesCFG();
 154     AU.addRequired<AAResultsWrapperPass>();
 155     AU.addRequired<DominatorTreeWrapperPass>();
 156     AU.addRequiredID(LCSSAID);
 157     AU.addRequired<LoopAccessLegacyAnalysis>();
 158     AU.addRequired<LoopInfoWrapperPass>();
 159     AU.addRequiredID(LoopSimplifyID);
 160     AU.addRequired<ScalarEvolutionWrapperPass>();
 161     AU.addRequired<TargetLibraryInfoWrapperPass>();
 162     AU.addPreserved<AAResultsWrapperPass>();
 163     AU.addPreserved<GlobalsAAWrapperPass>();
 164   }
 165
 166   LoopVersioningLICM()
 167       : LoopPass(ID), AA(nullptr), SE(nullptr), LI(nullptr), DT(nullptr),
 168         TLI(nullptr), LAA(nullptr), LAI(nullptr), Changed(false),
 169         Preheader(nullptr), CurLoop(nullptr), CurAST(nullptr),
 170         LoopDepthThreshold(LVLoopDepthThreshold),
 171         InvariantThreshold(LVInvarThreshold), LoadAndStoreCounter(0),
 172         InvariantCounter(0), IsReadOnlyLoop(true) {
 173     initializeLoopVersioningLICMPass(*PassRegistry::getPassRegistry());
 174   }
 175
 176   AliasAnalysis *AA;         // Current AliasAnalysis information
 177   ScalarEvolution *SE;       // Current ScalarEvolution
 178   LoopInfo *LI;              // Current LoopInfo
 179   DominatorTree *DT;         // Dominator Tree for the current Loop.
 180   TargetLibraryInfo *TLI;    // TargetLibraryInfo for constant folding.
 181   LoopAccessLegacyAnalysis *LAA;   // Current LoopAccessAnalysis
 182   const LoopAccessInfo *LAI; // Current Loop's LoopAccessInfo
 183
 184   bool Changed;            // Set to true when we change anything.
 185   BasicBlock *Preheader;   // The preheader block of the current loop.
 186   Loop *CurLoop;           // The current loop we are working on.
 187   AliasSetTracker *CurAST; // AliasSet information for the current loop.
 188   ValueToValueMap Strides;
 189
 190   unsigned LoopDepthThreshold;  // Maximum loop nest threshold
 191   float InvariantThreshold;     // Minimum invariant threshold
 192   unsigned LoadAndStoreCounter; // Counter to track num of load & store
 193   unsigned InvariantCounter;    // Counter to track num of invariant
 194   bool IsReadOnlyLoop;          // Read only loop marker.
 195
 196   bool isLegalForVersioning();
 197   bool legalLoopStructure();
 198   bool legalLoopInstructions();
 199   bool legalLoopMemoryAccesses();
 200   bool isLoopAlreadyVisited();
 201   void setNoAliasToLoop(Loop *);
 202   bool instructionSafeForVersioning(Instruction *);
 203   const char *getPassName() const override { return "Loop Versioning"; }
 204 };
 205 }
 206
 207 /// \brief Check loop structure and confirms it's good for LoopVersioningLICM.
 208 bool LoopVersioningLICM::legalLoopStructure() {
 209   // Loop must have a preheader, if not return false.
 210   if (!CurLoop->getLoopPreheader()) {
 211     DEBUG(dbgs() << "    loop preheader is missing\n");
 212     return false;
 213   }
 214   // Loop should be innermost loop, if not return false.
 215   if (CurLoop->getSubLoops().size()) {
 216     DEBUG(dbgs() << "    loop is not innermost\n");
 217     return false;
 218   }
 219   // Loop should have a single backedge, if not return false.
 220   if (CurLoop->getNumBackEdges() != 1) {
 221     DEBUG(dbgs() << "    loop has multiple backedges\n");
 222     return false;
 223   }
 224   // Loop must have a single exiting block, if not return false.
 225   if (!CurLoop->getExitingBlock()) {
 226     DEBUG(dbgs() << "    loop has multiple exiting block\n");
 227     return false;
 228   }
 229   // We only handle bottom-tested loop, i.e. loop in which the condition is
 230   // checked at the end of each iteration. With that we can assume that all
 231   // instructions in the loop are executed the same number of times.
 232   if (CurLoop->getExitingBlock() != CurLoop->getLoopLatch()) {
 233     DEBUG(dbgs() << "    loop is not bottom tested\n");
 234     return false;
 235   }
 236   // Parallel loops must not have aliasing loop-invariant memory accesses.
 237   // Hence we don't need to version anything in this case.
 238   if (CurLoop->isAnnotatedParallel()) {
 239     DEBUG(dbgs() << "    Parallel loop is not worth versioning\n");
 240     return false;
 241   }
 242   // Loop depth more then LoopDepthThreshold are not allowed
 243   if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
 244     DEBUG(dbgs() << "    loop depth is more then threshold\n");
 245     return false;
 246   }
 247   // Loop should have a dedicated exit block, if not return false.
 248   if (!CurLoop->hasDedicatedExits()) {
 249     DEBUG(dbgs() << "    loop does not has dedicated exit blocks\n");
 250     return false;
 251   }
 252   // We need to be able to compute the loop trip count in order
 253   // to generate the bound checks.
 254   const SCEV *ExitCount = SE->getBackedgeTakenCount(CurLoop);
 255   if (ExitCount == SE->getCouldNotCompute()) {
 256     DEBUG(dbgs() << "    loop does not has trip count\n");
 257     return false;
 258   }
 259   return true;
 260 }
 261
 262 /// \brief Check memory accesses in loop and confirms it's good for
 263 /// LoopVersioningLICM.
 264 bool LoopVersioningLICM::legalLoopMemoryAccesses() {
 265   bool HasMayAlias = false;
 266   bool TypeSafety = false;
 267   bool HasMod = false;
 268   // Memory check:
 269   // Transform phase will generate a versioned loop and also a runtime check to
 270   // ensure the pointers are independent and they don’t alias.
 271   // In version variant of loop, alias meta data asserts that all access are
 272   // mutually independent.
 273   //
 274   // Pointers aliasing in alias domain are avoided because with multiple
 275   // aliasing domains we may not be able to hoist potential loop invariant
 276   // access out of the loop.
 277   //
 278   // Iterate over alias tracker sets, and confirm AliasSets doesn't have any
 279   // must alias set.
 280   for (const auto &I : *CurAST) {
 281     const AliasSet &AS = I;
 282     // Skip Forward Alias Sets, as this should be ignored as part of
 283     // the AliasSetTracker object.
 284     if (AS.isForwardingAliasSet())
 285       continue;
 286     // With MustAlias its not worth adding runtime bound check.
 287     if (AS.isMustAlias())
 288       return false;
 289     Value *SomePtr = AS.begin()->getValue();
 290     bool TypeCheck = true;
 291     // Check for Mod & MayAlias
 292     HasMayAlias |= AS.isMayAlias();
 293     HasMod |= AS.isMod();
 294     for (const auto &A : AS) {
 295       Value *Ptr = A.getValue();
 296       // Alias tracker should have pointers of same data type.
 297       TypeCheck = (TypeCheck && (SomePtr->getType() == Ptr->getType()));
 298     }
 299     // At least one alias tracker should have pointers of same data type.
 300     TypeSafety |= TypeCheck;
 301   }
 302   // Ensure types should be of same type.
 303   if (!TypeSafety) {
 304     DEBUG(dbgs() << "    Alias tracker type safety failed!\n");
 305     return false;
 306   }
 307   // Ensure loop body shouldn't be read only.
 308   if (!HasMod) {
 309     DEBUG(dbgs() << "    No memory modified in loop body\n");
 310     return false;
 311   }
 312   // Make sure alias set has may alias case.
 313   // If there no alias memory ambiguity, return false.
 314   if (!HasMayAlias) {
 315     DEBUG(dbgs() << "    No ambiguity in memory access.\n");
 316     return false;
 317   }
 318   return true;
 319 }
 320
 321 /// \brief Check loop instructions safe for Loop versioning.
 322 /// It returns true if it's safe else returns false.
 323 /// Consider following:
 324 /// 1) Check all load store in loop body are non atomic & non volatile.
 325 /// 2) Check function call safety, by ensuring its not accessing memory.
 326 /// 3) Loop body shouldn't have any may throw instruction.
 327 bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
 328   assert(I != nullptr && "Null instruction found!");
 329   // Check function call safety
 330   if (isa<CallInst>(I) && !AA->doesNotAccessMemory(CallSite(I))) {
 331     DEBUG(dbgs() << "    Unsafe call site found.\n");
 332     return false;
 333   }
 334   // Avoid loops with possiblity of throw
 335   if (I->mayThrow()) {
 336     DEBUG(dbgs() << "    May throw instruction found in loop body\n");
 337     return false;
 338   }
 339   // If current instruction is load instructions
 340   // make sure it's a simple load (non atomic & non volatile)
 341   if (I->mayReadFromMemory()) {
 342     LoadInst *Ld = dyn_cast<LoadInst>(I);
 343     if (!Ld || !Ld->isSimple()) {
 344       DEBUG(dbgs() << "    Found a non-simple load.\n");
 345       return false;
 346     }
 347     LoadAndStoreCounter++;
 348     Value *Ptr = Ld->getPointerOperand();
 349     // Check loop invariant.
 350     if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
 351       InvariantCounter++;
 352   }
 353   // If current instruction is store instruction
 354   // make sure it's a simple store (non atomic & non volatile)
 355   else if (I->mayWriteToMemory()) {
 356     StoreInst *St = dyn_cast<StoreInst>(I);
 357     if (!St || !St->isSimple()) {
 358       DEBUG(dbgs() << "    Found a non-simple store.\n");
 359       return false;
 360     }
 361     LoadAndStoreCounter++;
 362     Value *Ptr = St->getPointerOperand();
 363     // Check loop invariant.
 364     if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
 365       InvariantCounter++;
 366
 367     IsReadOnlyLoop = false;
 368   }
 369   return true;
 370 }
 371
 372 /// \brief Check loop instructions and confirms it's good for
 373 /// LoopVersioningLICM.
 374 bool LoopVersioningLICM::legalLoopInstructions() {
 375   // Resetting counters.
 376   LoadAndStoreCounter = 0;
 377   InvariantCounter = 0;
 378   IsReadOnlyLoop = true;
 379   // Iterate over loop blocks and instructions of each block and check
 380   // instruction safety.
 381   for (auto *Block : CurLoop->getBlocks())
 382     for (auto &Inst : *Block) {
 383       // If instruction is unsafe just return false.
 384       if (!instructionSafeForVersioning(&Inst))
 385         return false;
 386     }
 387   // Get LoopAccessInfo from current loop.
 388   LAI = &LAA->getInfo(CurLoop);
 389   // Check LoopAccessInfo for need of runtime check.
 390   if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
 391     DEBUG(dbgs() << "    LAA: Runtime check not found !!\n");
 392     return false;
 393   }
 394   // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
 395   if (LAI->getNumRuntimePointerChecks() >
 396       VectorizerParams::RuntimeMemoryCheckThreshold) {
 397     DEBUG(dbgs() << "    LAA: Runtime checks are more than threshold !!\n");
 398     return false;
 399   }
 400   // Loop should have at least one invariant load or store instruction.
 401   if (!InvariantCounter) {
 402     DEBUG(dbgs() << "    Invariant not found !!\n");
 403     return false;
 404   }
 405   // Read only loop not allowed.
 406   if (IsReadOnlyLoop) {
 407     DEBUG(dbgs() << "    Found a read-only loop!\n");
 408     return false;
 409   }
 410   // Profitablity check:
 411   // Check invariant threshold, should be in limit.
 412   if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
 413     DEBUG(dbgs()
 414           << "    Invariant load & store are less then defined threshold\n");
 415     DEBUG(dbgs() << "    Invariant loads & stores: "
 416                  << ((InvariantCounter * 100) / LoadAndStoreCounter) << "%\n");
 417     DEBUG(dbgs() << "    Invariant loads & store threshold: "
 418                  << InvariantThreshold << "%\n");
 419     return false;
 420   }
 421   return true;
 422 }
 423
 424 /// \brief It checks loop is already visited or not.
 425 /// check loop meta data, if loop revisited return true
 426 /// else false.
 427 bool LoopVersioningLICM::isLoopAlreadyVisited() {
 428   // Check LoopVersioningLICM metadata into loop
 429   if (findStringMetadataForLoop(CurLoop, LICMVersioningMetaData)) {
 430     return true;
 431   }
 432   return false;
 433 }
 434
 435 /// \brief Checks legality for LoopVersioningLICM by considering following:
 436 /// a) loop structure legality   b) loop instruction legality
 437 /// c) loop memory access legality.
 438 /// Return true if legal else returns false.
 439 bool LoopVersioningLICM::isLegalForVersioning() {
 440   DEBUG(dbgs() << "Loop: " << *CurLoop);
 441   // Make sure not re-visiting same loop again.
 442   if (isLoopAlreadyVisited()) {
 443     DEBUG(
 444         dbgs() << "    Revisiting loop in LoopVersioningLICM not allowed.\n\n");
 445     return false;
 446   }
 447   // Check loop structure leagality.
 448   if (!legalLoopStructure()) {
 449     DEBUG(
 450         dbgs() << "    Loop structure not suitable for LoopVersioningLICM\n\n");
 451     return false;
 452   }
 453   // Check loop instruction leagality.
 454   if (!legalLoopInstructions()) {
 455     DEBUG(dbgs()
 456           << "    Loop instructions not suitable for LoopVersioningLICM\n\n");
 457     return false;
 458   }
 459   // Check loop memory access leagality.
 460   if (!legalLoopMemoryAccesses()) {
 461     DEBUG(dbgs()
 462           << "    Loop memory access not suitable for LoopVersioningLICM\n\n");
 463     return false;
 464   }
 465   // Loop versioning is feasible, return true.
 466   DEBUG(dbgs() << "    Loop Versioning found to be beneficial\n\n");
 467   return true;
 468 }
 469
 470 /// \brief Update loop with aggressive aliasing assumptions.
 471 /// It marks no-alias to any pairs of memory operations by assuming
 472 /// loop should not have any must-alias memory accesses pairs.
 473 /// During LoopVersioningLICM legality we ignore loops having must
 474 /// aliasing memory accesses.
 475 void LoopVersioningLICM::setNoAliasToLoop(Loop *VerLoop) {
 476   // Get latch terminator instruction.
 477   Instruction *I = VerLoop->getLoopLatch()->getTerminator();
 478   // Create alias scope domain.
 479   MDBuilder MDB(I->getContext());
 480   MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("LVDomain");
 481   StringRef Name = "LVAliasScope";
 482   SmallVector<Metadata *, 4> Scopes, NoAliases;
 483   MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
 484   // Iterate over each instruction of loop.
 485   // set no-alias for all load & store instructions.
 486   for (auto *Block : CurLoop->getBlocks()) {
 487     for (auto &Inst : *Block) {
 488       // Only interested in instruction that may modify or read memory.
 489       if (!Inst.mayReadFromMemory() && !Inst.mayWriteToMemory())
 490         continue;
 491       Scopes.push_back(NewScope);
 492       NoAliases.push_back(NewScope);
 493       // Set no-alias for current instruction.
 494       Inst.setMetadata(
 495           LLVMContext::MD_noalias,
 496           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_noalias),
 497                               MDNode::get(Inst.getContext(), NoAliases)));
 498       // set alias-scope for current instruction.
 499       Inst.setMetadata(
 500           LLVMContext::MD_alias_scope,
 501           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_alias_scope),
 502                               MDNode::get(Inst.getContext(), Scopes)));
 503     }
 504   }
 505 }
 506
 507 bool LoopVersioningLICM::runOnLoop(Loop *L, LPPassManager &LPM) {
 508   if (skipLoop(L))
 509     return false;
 510   Changed = false;
 511   // Get Analysis information.
 512   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 513   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 514   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 515   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 516   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 517   LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
 518   LAI = nullptr;
 519   // Set Current Loop
 520   CurLoop = L;
 521   // Get the preheader block.
 522   Preheader = L->getLoopPreheader();
 523   // Initial allocation
 524   CurAST = new AliasSetTracker(*AA);
 525
 526   // Loop over the body of this loop, construct AST.
 527   for (auto *Block : L->getBlocks()) {
 528     if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
 529       CurAST->add(*Block);          // Incorporate the specified basic block
 530   }
 531   // Check feasiblity of LoopVersioningLICM.
 532   // If versioning found to be feasible and beneficial then proceed
 533   // else simply return, by cleaning up memory.
 534   if (isLegalForVersioning()) {
 535     // Do loop versioning.
 536     // Create memcheck for memory accessed inside loop.
 537     // Clone original loop, and set blocks properly.
 538     LoopVersioning LVer(*LAI, CurLoop, LI, DT, SE, true);
 539     LVer.versionLoop();
 540     // Set Loop Versioning metaData for original loop.
 541     addStringMetadataToLoop(LVer.getNonVersionedLoop(), LICMVersioningMetaData);
 542     // Set Loop Versioning metaData for version loop.
 543     addStringMetadataToLoop(LVer.getVersionedLoop(), LICMVersioningMetaData);
 544     // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
 545     addStringMetadataToLoop(LVer.getVersionedLoop(),
 546                             "llvm.mem.parallel_loop_access");
 547     // Update version loop with aggressive aliasing assumption.
 548     setNoAliasToLoop(LVer.getVersionedLoop());
 549     Changed = true;
 550   }
 551   // Delete allocated memory.
 552   delete CurAST;
 553   return Changed;
 554 }
 555
 556 char LoopVersioningLICM::ID = 0;
 557 INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm",
 558                       "Loop Versioning For LICM", false, false)
 559 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 560 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 561 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 562 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 563 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
 564 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 565 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 566 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 567 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 568 INITIALIZE_PASS_END(LoopVersioningLICM, "loop-versioning-licm",
 569                     "Loop Versioning For LICM", false, false)
 570
 571 Pass *llvm::createLoopVersioningLICMPass() { return new LoopVersioningLICM(); }