contrib/llvm/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/SmallVector.h"
  64 #include "llvm/ADT/StringRef.h"
  65 #include "llvm/Analysis/AliasAnalysis.h"
  66 #include "llvm/Analysis/AliasSetTracker.h"
  67 #include "llvm/Analysis/GlobalsModRef.h"
  68 #include "llvm/Analysis/LoopAccessAnalysis.h"
  69 #include "llvm/Analysis/LoopInfo.h"
  70 #include "llvm/Analysis/LoopPass.h"
  71 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  72 #include "llvm/Analysis/ScalarEvolution.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"
  85 #include "llvm/Support/CommandLine.h"
  86 #include "llvm/Support/Debug.h"
  87 #include "llvm/Support/raw_ostream.h"
  88 #include "llvm/Transforms/Scalar.h"
  89 #include "llvm/Transforms/Utils.h"
  90 #include "llvm/Transforms/Utils/LoopUtils.h"
  91 #include "llvm/Transforms/Utils/LoopVersioning.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
 110 static cl::opt<unsigned> LVLoopDepthThreshold(
 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),
 121       ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context), V))};
 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) {
 128   SmallVector<Metadata *, 4> MDs(1);
 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) {
 155     initializeLoopVersioningLICMPass(*PassRegistry::getPassRegistry());
 156   }
 157
 158   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 159
 160   void getAnalysisUsage(AnalysisUsage &AU) const override {
 161     AU.setPreservesCFG();
 162     AU.addRequired<AAResultsWrapperPass>();
 163     AU.addRequired<DominatorTreeWrapperPass>();
 164     AU.addRequiredID(LCSSAID);
 165     AU.addRequired<LoopAccessLegacyAnalysis>();
 166     AU.addRequired<LoopInfoWrapperPass>();
 167     AU.addRequiredID(LoopSimplifyID);
 168     AU.addRequired<ScalarEvolutionWrapperPass>();
 169     AU.addPreserved<AAResultsWrapperPass>();
 170     AU.addPreserved<GlobalsAAWrapperPass>();
 171     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
 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
 232   OptimizationRemarkEmitter *ORE;
 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() >
 435       VectorizerParams::RuntimeMemoryCheckThreshold) {
 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 "
 445              << NV("Threshold", VectorizerParams::RuntimeMemoryCheckThreshold);
 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";
 565   SmallVector<Metadata *, 4> Scopes, NoAliases;
 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(
 578           LLVMContext::MD_noalias,
 579           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_noalias),
 580                               MDNode::get(Inst.getContext(), NoAliases)));
 581       // set alias-scope for current instruction.
 582       Inst.setMetadata(
 583           LLVMContext::MD_alias_scope,
 584           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_alias_scope),
 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.
 627     addStringMetadataToLoop(LVer.getNonVersionedLoop(), LICMVersioningMetaData);
 628     // Set Loop Versioning metaData for version loop.
 629     addStringMetadataToLoop(LVer.getVersionedLoop(), LICMVersioningMetaData);
 630     // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
 631     addStringMetadataToLoop(LVer.getVersionedLoop(),
 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)
 644 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 645 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 646 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 647 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 648 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
 649 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 650 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 651 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 652 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 653 INITIALIZE_PASS_END(LoopVersioningLICM, "loop-versioning-licm",
 654                     "Loop Versioning For LICM", false, false)
 655
 656 Pass *llvm::createLoopVersioningLICMPass() { return new LoopVersioningLICM(); }