contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp

   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"
  64 #include "llvm/Analysis/AliasAnalysis.h"
  65 #include "llvm/Analysis/AliasSetTracker.h"
  66 #include "llvm/Analysis/GlobalsModRef.h"
  67 #include "llvm/Analysis/LoopAccessAnalysis.h"
  68 #include "llvm/Analysis/LoopInfo.h"
  69 #include "llvm/Analysis/LoopPass.h"
  70 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  71 #include "llvm/Analysis/ScalarEvolution.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/InitializePasses.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 namespace {
 117
 118 struct LoopVersioningLICM : public LoopPass {
 119   static char ID;
 120
 121   LoopVersioningLICM()
 122       : LoopPass(ID), LoopDepthThreshold(LVLoopDepthThreshold),
 123         InvariantThreshold(LVInvarThreshold) {
 124     initializeLoopVersioningLICMPass(*PassRegistry::getPassRegistry());
 125   }
 126
 127   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 128
 129   void getAnalysisUsage(AnalysisUsage &AU) const override {
 130     AU.setPreservesCFG();
 131     AU.addRequired<AAResultsWrapperPass>();
 132     AU.addRequired<DominatorTreeWrapperPass>();
 133     AU.addRequiredID(LCSSAID);
 134     AU.addRequired<LoopAccessLegacyAnalysis>();
 135     AU.addRequired<LoopInfoWrapperPass>();
 136     AU.addRequiredID(LoopSimplifyID);
 137     AU.addRequired<ScalarEvolutionWrapperPass>();
 138     AU.addPreserved<AAResultsWrapperPass>();
 139     AU.addPreserved<GlobalsAAWrapperPass>();
 140     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
 141   }
 142
 143   StringRef getPassName() const override { return "Loop Versioning for LICM"; }
 144
 145   void reset() {
 146     AA = nullptr;
 147     SE = nullptr;
 148     LAA = nullptr;
 149     CurLoop = nullptr;
 150     LoadAndStoreCounter = 0;
 151     InvariantCounter = 0;
 152     IsReadOnlyLoop = true;
 153     ORE = nullptr;
 154     CurAST.reset();
 155   }
 156
 157   class AutoResetter {
 158   public:
 159     AutoResetter(LoopVersioningLICM &LVLICM) : LVLICM(LVLICM) {}
 160     ~AutoResetter() { LVLICM.reset(); }
 161
 162   private:
 163     LoopVersioningLICM &LVLICM;
 164   };
 165
 166 private:
 167   // Current AliasAnalysis information
 168   AliasAnalysis *AA = nullptr;
 169
 170   // Current ScalarEvolution
 171   ScalarEvolution *SE = nullptr;
 172
 173   // Current LoopAccessAnalysis
 174   LoopAccessLegacyAnalysis *LAA = nullptr;
 175
 176   // Current Loop's LoopAccessInfo
 177   const LoopAccessInfo *LAI = nullptr;
 178
 179   // The current loop we are working on.
 180   Loop *CurLoop = nullptr;
 181
 182   // AliasSet information for the current loop.
 183   std::unique_ptr<AliasSetTracker> CurAST;
 184
 185   // Maximum loop nest threshold
 186   unsigned LoopDepthThreshold;
 187
 188   // Minimum invariant threshold
 189   float InvariantThreshold;
 190
 191   // Counter to track num of load & store
 192   unsigned LoadAndStoreCounter = 0;
 193
 194   // Counter to track num of invariant
 195   unsigned InvariantCounter = 0;
 196
 197   // Read only loop marker.
 198   bool IsReadOnlyLoop = true;
 199
 200   // OptimizationRemarkEmitter
 201   OptimizationRemarkEmitter *ORE;
 202
 203   bool isLegalForVersioning();
 204   bool legalLoopStructure();
 205   bool legalLoopInstructions();
 206   bool legalLoopMemoryAccesses();
 207   bool isLoopAlreadyVisited();
 208   void setNoAliasToLoop(Loop *VerLoop);
 209   bool instructionSafeForVersioning(Instruction *I);
 210 };
 211
 212 } // end anonymous namespace
 213
 214 /// Check loop structure and confirms it's good for LoopVersioningLICM.
 215 bool LoopVersioningLICM::legalLoopStructure() {
 216   // Loop must be in loop simplify form.
 217   if (!CurLoop->isLoopSimplifyForm()) {
 218     LLVM_DEBUG(dbgs() << "    loop is not in loop-simplify form.\n");
 219     return false;
 220   }
 221   // Loop should be innermost loop, if not return false.
 222   if (!CurLoop->getSubLoops().empty()) {
 223     LLVM_DEBUG(dbgs() << "    loop is not innermost\n");
 224     return false;
 225   }
 226   // Loop should have a single backedge, if not return false.
 227   if (CurLoop->getNumBackEdges() != 1) {
 228     LLVM_DEBUG(dbgs() << "    loop has multiple backedges\n");
 229     return false;
 230   }
 231   // Loop must have a single exiting block, if not return false.
 232   if (!CurLoop->getExitingBlock()) {
 233     LLVM_DEBUG(dbgs() << "    loop has multiple exiting block\n");
 234     return false;
 235   }
 236   // We only handle bottom-tested loop, i.e. loop in which the condition is
 237   // checked at the end of each iteration. With that we can assume that all
 238   // instructions in the loop are executed the same number of times.
 239   if (CurLoop->getExitingBlock() != CurLoop->getLoopLatch()) {
 240     LLVM_DEBUG(dbgs() << "    loop is not bottom tested\n");
 241     return false;
 242   }
 243   // Parallel loops must not have aliasing loop-invariant memory accesses.
 244   // Hence we don't need to version anything in this case.
 245   if (CurLoop->isAnnotatedParallel()) {
 246     LLVM_DEBUG(dbgs() << "    Parallel loop is not worth versioning\n");
 247     return false;
 248   }
 249   // Loop depth more then LoopDepthThreshold are not allowed
 250   if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
 251     LLVM_DEBUG(dbgs() << "    loop depth is more then threshold\n");
 252     return false;
 253   }
 254   // We need to be able to compute the loop trip count in order
 255   // to generate the bound checks.
 256   const SCEV *ExitCount = SE->getBackedgeTakenCount(CurLoop);
 257   if (ExitCount == SE->getCouldNotCompute()) {
 258     LLVM_DEBUG(dbgs() << "    loop does not has trip count\n");
 259     return false;
 260   }
 261   return true;
 262 }
 263
 264 /// Check memory accesses in loop and confirms it's good for
 265 /// LoopVersioningLICM.
 266 bool LoopVersioningLICM::legalLoopMemoryAccesses() {
 267   bool HasMayAlias = false;
 268   bool TypeSafety = false;
 269   bool HasMod = false;
 270   // Memory check:
 271   // Transform phase will generate a versioned loop and also a runtime check to
 272   // ensure the pointers are independent and they don’t alias.
 273   // In version variant of loop, alias meta data asserts that all access are
 274   // mutually independent.
 275   //
 276   // Pointers aliasing in alias domain are avoided because with multiple
 277   // aliasing domains we may not be able to hoist potential loop invariant
 278   // access out of the loop.
 279   //
 280   // Iterate over alias tracker sets, and confirm AliasSets doesn't have any
 281   // must alias set.
 282   for (const auto &I : *CurAST) {
 283     const AliasSet &AS = I;
 284     // Skip Forward Alias Sets, as this should be ignored as part of
 285     // the AliasSetTracker object.
 286     if (AS.isForwardingAliasSet())
 287       continue;
 288     // With MustAlias its not worth adding runtime bound check.
 289     if (AS.isMustAlias())
 290       return false;
 291     Value *SomePtr = AS.begin()->getValue();
 292     bool TypeCheck = true;
 293     // Check for Mod & MayAlias
 294     HasMayAlias |= AS.isMayAlias();
 295     HasMod |= AS.isMod();
 296     for (const auto &A : AS) {
 297       Value *Ptr = A.getValue();
 298       // Alias tracker should have pointers of same data type.
 299       TypeCheck = (TypeCheck && (SomePtr->getType() == Ptr->getType()));
 300     }
 301     // At least one alias tracker should have pointers of same data type.
 302     TypeSafety |= TypeCheck;
 303   }
 304   // Ensure types should be of same type.
 305   if (!TypeSafety) {
 306     LLVM_DEBUG(dbgs() << "    Alias tracker type safety failed!\n");
 307     return false;
 308   }
 309   // Ensure loop body shouldn't be read only.
 310   if (!HasMod) {
 311     LLVM_DEBUG(dbgs() << "    No memory modified in loop body\n");
 312     return false;
 313   }
 314   // Make sure alias set has may alias case.
 315   // If there no alias memory ambiguity, return false.
 316   if (!HasMayAlias) {
 317     LLVM_DEBUG(dbgs() << "    No ambiguity in memory access.\n");
 318     return false;
 319   }
 320   return true;
 321 }
 322
 323 /// Check loop instructions safe for Loop versioning.
 324 /// It returns true if it's safe else returns false.
 325 /// Consider following:
 326 /// 1) Check all load store in loop body are non atomic & non volatile.
 327 /// 2) Check function call safety, by ensuring its not accessing memory.
 328 /// 3) Loop body shouldn't have any may throw instruction.
 329 /// 4) Loop body shouldn't have any convergent or noduplicate instructions.
 330 bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
 331   assert(I != nullptr && "Null instruction found!");
 332   // Check function call safety
 333   if (auto *Call = dyn_cast<CallBase>(I)) {
 334     if (Call->isConvergent() || Call->cannotDuplicate()) {
 335       LLVM_DEBUG(dbgs() << "    Convergent call site found.\n");
 336       return false;
 337     }
 338
 339     if (!AA->doesNotAccessMemory(Call)) {
 340       LLVM_DEBUG(dbgs() << "    Unsafe call site found.\n");
 341       return false;
 342     }
 343   }
 344
 345   // Avoid loops with possiblity of throw
 346   if (I->mayThrow()) {
 347     LLVM_DEBUG(dbgs() << "    May throw instruction found in loop body\n");
 348     return false;
 349   }
 350   // If current instruction is load instructions
 351   // make sure it's a simple load (non atomic & non volatile)
 352   if (I->mayReadFromMemory()) {
 353     LoadInst *Ld = dyn_cast<LoadInst>(I);
 354     if (!Ld || !Ld->isSimple()) {
 355       LLVM_DEBUG(dbgs() << "    Found a non-simple load.\n");
 356       return false;
 357     }
 358     LoadAndStoreCounter++;
 359     Value *Ptr = Ld->getPointerOperand();
 360     // Check loop invariant.
 361     if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
 362       InvariantCounter++;
 363   }
 364   // If current instruction is store instruction
 365   // make sure it's a simple store (non atomic & non volatile)
 366   else if (I->mayWriteToMemory()) {
 367     StoreInst *St = dyn_cast<StoreInst>(I);
 368     if (!St || !St->isSimple()) {
 369       LLVM_DEBUG(dbgs() << "    Found a non-simple store.\n");
 370       return false;
 371     }
 372     LoadAndStoreCounter++;
 373     Value *Ptr = St->getPointerOperand();
 374     // Check loop invariant.
 375     if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
 376       InvariantCounter++;
 377
 378     IsReadOnlyLoop = false;
 379   }
 380   return true;
 381 }
 382
 383 /// Check loop instructions and confirms it's good for
 384 /// LoopVersioningLICM.
 385 bool LoopVersioningLICM::legalLoopInstructions() {
 386   // Resetting counters.
 387   LoadAndStoreCounter = 0;
 388   InvariantCounter = 0;
 389   IsReadOnlyLoop = true;
 390   using namespace ore;
 391   // Iterate over loop blocks and instructions of each block and check
 392   // instruction safety.
 393   for (auto *Block : CurLoop->getBlocks())
 394     for (auto &Inst : *Block) {
 395       // If instruction is unsafe just return false.
 396       if (!instructionSafeForVersioning(&Inst)) {
 397         ORE->emit([&]() {
 398           return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)
 399                  << " Unsafe Loop Instruction";
 400         });
 401         return false;
 402       }
 403     }
 404   // Get LoopAccessInfo from current loop.
 405   LAI = &LAA->getInfo(CurLoop);
 406   // Check LoopAccessInfo for need of runtime check.
 407   if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
 408     LLVM_DEBUG(dbgs() << "    LAA: Runtime check not found !!\n");
 409     return false;
 410   }
 411   // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
 412   if (LAI->getNumRuntimePointerChecks() >
 413       VectorizerParams::RuntimeMemoryCheckThreshold) {
 414     LLVM_DEBUG(
 415         dbgs() << "    LAA: Runtime checks are more than threshold !!\n");
 416     ORE->emit([&]() {
 417       return OptimizationRemarkMissed(DEBUG_TYPE, "RuntimeCheck",
 418                                       CurLoop->getStartLoc(),
 419                                       CurLoop->getHeader())
 420              << "Number of runtime checks "
 421              << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks())
 422              << " exceeds threshold "
 423              << NV("Threshold", VectorizerParams::RuntimeMemoryCheckThreshold);
 424     });
 425     return false;
 426   }
 427   // Loop should have at least one invariant load or store instruction.
 428   if (!InvariantCounter) {
 429     LLVM_DEBUG(dbgs() << "    Invariant not found !!\n");
 430     return false;
 431   }
 432   // Read only loop not allowed.
 433   if (IsReadOnlyLoop) {
 434     LLVM_DEBUG(dbgs() << "    Found a read-only loop!\n");
 435     return false;
 436   }
 437   // Profitablity check:
 438   // Check invariant threshold, should be in limit.
 439   if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
 440     LLVM_DEBUG(
 441         dbgs()
 442         << "    Invariant load & store are less then defined threshold\n");
 443     LLVM_DEBUG(dbgs() << "    Invariant loads & stores: "
 444                       << ((InvariantCounter * 100) / LoadAndStoreCounter)
 445                       << "%\n");
 446     LLVM_DEBUG(dbgs() << "    Invariant loads & store threshold: "
 447                       << InvariantThreshold << "%\n");
 448     ORE->emit([&]() {
 449       return OptimizationRemarkMissed(DEBUG_TYPE, "InvariantThreshold",
 450                                       CurLoop->getStartLoc(),
 451                                       CurLoop->getHeader())
 452              << "Invariant load & store "
 453              << NV("LoadAndStoreCounter",
 454                    ((InvariantCounter * 100) / LoadAndStoreCounter))
 455              << " are less then defined threshold "
 456              << NV("Threshold", InvariantThreshold);
 457     });
 458     return false;
 459   }
 460   return true;
 461 }
 462
 463 /// It checks loop is already visited or not.
 464 /// check loop meta data, if loop revisited return true
 465 /// else false.
 466 bool LoopVersioningLICM::isLoopAlreadyVisited() {
 467   // Check LoopVersioningLICM metadata into loop
 468   if (findStringMetadataForLoop(CurLoop, LICMVersioningMetaData)) {
 469     return true;
 470   }
 471   return false;
 472 }
 473
 474 /// Checks legality for LoopVersioningLICM by considering following:
 475 /// a) loop structure legality   b) loop instruction legality
 476 /// c) loop memory access legality.
 477 /// Return true if legal else returns false.
 478 bool LoopVersioningLICM::isLegalForVersioning() {
 479   using namespace ore;
 480   LLVM_DEBUG(dbgs() << "Loop: " << *CurLoop);
 481   // Make sure not re-visiting same loop again.
 482   if (isLoopAlreadyVisited()) {
 483     LLVM_DEBUG(
 484         dbgs() << "    Revisiting loop in LoopVersioningLICM not allowed.\n\n");
 485     return false;
 486   }
 487   // Check loop structure leagality.
 488   if (!legalLoopStructure()) {
 489     LLVM_DEBUG(
 490         dbgs() << "    Loop structure not suitable for LoopVersioningLICM\n\n");
 491     ORE->emit([&]() {
 492       return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopStruct",
 493                                       CurLoop->getStartLoc(),
 494                                       CurLoop->getHeader())
 495              << " Unsafe Loop structure";
 496     });
 497     return false;
 498   }
 499   // Check loop instruction leagality.
 500   if (!legalLoopInstructions()) {
 501     LLVM_DEBUG(
 502         dbgs()
 503         << "    Loop instructions not suitable for LoopVersioningLICM\n\n");
 504     return false;
 505   }
 506   // Check loop memory access leagality.
 507   if (!legalLoopMemoryAccesses()) {
 508     LLVM_DEBUG(
 509         dbgs()
 510         << "    Loop memory access not suitable for LoopVersioningLICM\n\n");
 511     ORE->emit([&]() {
 512       return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopMemoryAccess",
 513                                       CurLoop->getStartLoc(),
 514                                       CurLoop->getHeader())
 515              << " Unsafe Loop memory access";
 516     });
 517     return false;
 518   }
 519   // Loop versioning is feasible, return true.
 520   LLVM_DEBUG(dbgs() << "    Loop Versioning found to be beneficial\n\n");
 521   ORE->emit([&]() {
 522     return OptimizationRemark(DEBUG_TYPE, "IsLegalForVersioning",
 523                               CurLoop->getStartLoc(), CurLoop->getHeader())
 524            << " Versioned loop for LICM."
 525            << " Number of runtime checks we had to insert "
 526            << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks());
 527   });
 528   return true;
 529 }
 530
 531 /// Update loop with aggressive aliasing assumptions.
 532 /// It marks no-alias to any pairs of memory operations by assuming
 533 /// loop should not have any must-alias memory accesses pairs.
 534 /// During LoopVersioningLICM legality we ignore loops having must
 535 /// aliasing memory accesses.
 536 void LoopVersioningLICM::setNoAliasToLoop(Loop *VerLoop) {
 537   // Get latch terminator instruction.
 538   Instruction *I = VerLoop->getLoopLatch()->getTerminator();
 539   // Create alias scope domain.
 540   MDBuilder MDB(I->getContext());
 541   MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("LVDomain");
 542   StringRef Name = "LVAliasScope";
 543   SmallVector<Metadata *, 4> Scopes, NoAliases;
 544   MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
 545   // Iterate over each instruction of loop.
 546   // set no-alias for all load & store instructions.
 547   for (auto *Block : CurLoop->getBlocks()) {
 548     for (auto &Inst : *Block) {
 549       // Only interested in instruction that may modify or read memory.
 550       if (!Inst.mayReadFromMemory() && !Inst.mayWriteToMemory())
 551         continue;
 552       Scopes.push_back(NewScope);
 553       NoAliases.push_back(NewScope);
 554       // Set no-alias for current instruction.
 555       Inst.setMetadata(
 556           LLVMContext::MD_noalias,
 557           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_noalias),
 558                               MDNode::get(Inst.getContext(), NoAliases)));
 559       // set alias-scope for current instruction.
 560       Inst.setMetadata(
 561           LLVMContext::MD_alias_scope,
 562           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_alias_scope),
 563                               MDNode::get(Inst.getContext(), Scopes)));
 564     }
 565   }
 566 }
 567
 568 bool LoopVersioningLICM::runOnLoop(Loop *L, LPPassManager &LPM) {
 569   // This will automatically release all resources hold by the current
 570   // LoopVersioningLICM object.
 571   AutoResetter Resetter(*this);
 572
 573   if (skipLoop(L))
 574     return false;
 575
 576   // Do not do the transformation if disabled by metadata.
 577   if (hasLICMVersioningTransformation(L) & TM_Disable)
 578     return false;
 579
 580   // Get Analysis information.
 581   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 582   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 583   LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
 584   ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
 585   LAI = nullptr;
 586   // Set Current Loop
 587   CurLoop = L;
 588   CurAST.reset(new AliasSetTracker(*AA));
 589
 590   // Loop over the body of this loop, construct AST.
 591   LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 592   for (auto *Block : L->getBlocks()) {
 593     if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
 594       CurAST->add(*Block);          // Incorporate the specified basic block
 595   }
 596
 597   bool Changed = false;
 598
 599   // Check feasiblity of LoopVersioningLICM.
 600   // If versioning found to be feasible and beneficial then proceed
 601   // else simply return, by cleaning up memory.
 602   if (isLegalForVersioning()) {
 603     // Do loop versioning.
 604     // Create memcheck for memory accessed inside loop.
 605     // Clone original loop, and set blocks properly.
 606     DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 607     LoopVersioning LVer(*LAI, CurLoop, LI, DT, SE, true);
 608     LVer.versionLoop();
 609     // Set Loop Versioning metaData for original loop.
 610     addStringMetadataToLoop(LVer.getNonVersionedLoop(), LICMVersioningMetaData);
 611     // Set Loop Versioning metaData for version loop.
 612     addStringMetadataToLoop(LVer.getVersionedLoop(), LICMVersioningMetaData);
 613     // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
 614     // FIXME: "llvm.mem.parallel_loop_access" annotates memory access
 615     // instructions, not loops.
 616     addStringMetadataToLoop(LVer.getVersionedLoop(),
 617                             "llvm.mem.parallel_loop_access");
 618     // Update version loop with aggressive aliasing assumption.
 619     setNoAliasToLoop(LVer.getVersionedLoop());
 620     Changed = true;
 621   }
 622   return Changed;
 623 }
 624
 625 char LoopVersioningLICM::ID = 0;
 626
 627 INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm",
 628                       "Loop Versioning For LICM", false, false)
 629 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 630 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 631 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 632 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 633 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
 634 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 635 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 636 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 637 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 638 INITIALIZE_PASS_END(LoopVersioningLICM, "loop-versioning-licm",
 639                     "Loop Versioning For LICM", false, false)
 640
 641 Pass *llvm::createLoopVersioningLICMPass() { return new LoopVersioningLICM(); }