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/Pass.h"
  83 #include "llvm/Support/Casting.h"
  84 #include "llvm/Support/CommandLine.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.h"
  89 #include "llvm/Transforms/Utils/LoopUtils.h"
  90 #include "llvm/Transforms/Utils/LoopVersioning.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
 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 /// 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 /// 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
 148 struct LoopVersioningLICM : public LoopPass {
 149   static char ID;
 150
 151   LoopVersioningLICM()
 152       : LoopPass(ID), LoopDepthThreshold(LVLoopDepthThreshold),
 153         InvariantThreshold(LVInvarThreshold) {
 154     initializeLoopVersioningLICMPass(*PassRegistry::getPassRegistry());
 155   }
 156
 157   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 158
 159   void getAnalysisUsage(AnalysisUsage &AU) const override {
 160     AU.setPreservesCFG();
 161     AU.addRequired<AAResultsWrapperPass>();
 162     AU.addRequired<DominatorTreeWrapperPass>();
 163     AU.addRequiredID(LCSSAID);
 164     AU.addRequired<LoopAccessLegacyAnalysis>();
 165     AU.addRequired<LoopInfoWrapperPass>();
 166     AU.addRequiredID(LoopSimplifyID);
 167     AU.addRequired<ScalarEvolutionWrapperPass>();
 168     AU.addPreserved<AAResultsWrapperPass>();
 169     AU.addPreserved<GlobalsAAWrapperPass>();
 170     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
 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
 231   OptimizationRemarkEmitter *ORE;
 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 bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
 360   assert(I != nullptr && "Null instruction found!");
 361   // Check function call safety
 362   if (auto *Call = dyn_cast<CallBase>(I))
 363     if (!AA->doesNotAccessMemory(Call)) {
 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
 598   // Do not do the transformation if disabled by metadata.
 599   if (hasLICMVersioningTransformation(L) & TM_Disable)
 600     return false;
 601
 602   // Get Analysis information.
 603   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 604   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 605   LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
 606   ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
 607   LAI = nullptr;
 608   // Set Current Loop
 609   CurLoop = L;
 610   CurAST.reset(new AliasSetTracker(*AA));
 611
 612   // Loop over the body of this loop, construct AST.
 613   LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 614   for (auto *Block : L->getBlocks()) {
 615     if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
 616       CurAST->add(*Block);          // Incorporate the specified basic block
 617   }
 618
 619   bool Changed = false;
 620
 621   // Check feasiblity of LoopVersioningLICM.
 622   // If versioning found to be feasible and beneficial then proceed
 623   // else simply return, by cleaning up memory.
 624   if (isLegalForVersioning()) {
 625     // Do loop versioning.
 626     // Create memcheck for memory accessed inside loop.
 627     // Clone original loop, and set blocks properly.
 628     DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 629     LoopVersioning LVer(*LAI, CurLoop, LI, DT, SE, true);
 630     LVer.versionLoop();
 631     // Set Loop Versioning metaData for original loop.
 632     addStringMetadataToLoop(LVer.getNonVersionedLoop(), LICMVersioningMetaData);
 633     // Set Loop Versioning metaData for version loop.
 634     addStringMetadataToLoop(LVer.getVersionedLoop(), LICMVersioningMetaData);
 635     // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
 636     // FIXME: "llvm.mem.parallel_loop_access" annotates memory access
 637     // instructions, not loops.
 638     addStringMetadataToLoop(LVer.getVersionedLoop(),
 639                             "llvm.mem.parallel_loop_access");
 640     // Update version loop with aggressive aliasing assumption.
 641     setNoAliasToLoop(LVer.getVersionedLoop());
 642     Changed = true;
 643   }
 644   return Changed;
 645 }
 646
 647 char LoopVersioningLICM::ID = 0;
 648
 649 INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm",
 650                       "Loop Versioning For LICM", false, false)
 651 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 652 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 653 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 654 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 655 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
 656 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 657 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 658 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 659 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 660 INITIALIZE_PASS_END(LoopVersioningLICM, "loop-versioning-licm",
 661                     "Loop Versioning For LICM", false, false)
 662
 663 Pass *llvm::createLoopVersioningLICMPass() { return new LoopVersioningLICM(); }