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 /// 4) Loop body shouldn't have any convergent or noduplicate instructions.
 360 bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
 361   assert(I != nullptr && "Null instruction found!");
 362   // Check function call safety
 363   if (auto *Call = dyn_cast<CallBase>(I)) {
 364     if (Call->isConvergent() || Call->cannotDuplicate()) {
 365       LLVM_DEBUG(dbgs() << "    Convergent call site found.\n");
 366       return false;
 367     }
 368
 369     if (!AA->doesNotAccessMemory(Call)) {
 370       LLVM_DEBUG(dbgs() << "    Unsafe call site found.\n");
 371       return false;
 372     }
 373   }
 374
 375   // Avoid loops with possiblity of throw
 376   if (I->mayThrow()) {
 377     LLVM_DEBUG(dbgs() << "    May throw instruction found in loop body\n");
 378     return false;
 379   }
 380   // If current instruction is load instructions
 381   // make sure it's a simple load (non atomic & non volatile)
 382   if (I->mayReadFromMemory()) {
 383     LoadInst *Ld = dyn_cast<LoadInst>(I);
 384     if (!Ld || !Ld->isSimple()) {
 385       LLVM_DEBUG(dbgs() << "    Found a non-simple load.\n");
 386       return false;
 387     }
 388     LoadAndStoreCounter++;
 389     Value *Ptr = Ld->getPointerOperand();
 390     // Check loop invariant.
 391     if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
 392       InvariantCounter++;
 393   }
 394   // If current instruction is store instruction
 395   // make sure it's a simple store (non atomic & non volatile)
 396   else if (I->mayWriteToMemory()) {
 397     StoreInst *St = dyn_cast<StoreInst>(I);
 398     if (!St || !St->isSimple()) {
 399       LLVM_DEBUG(dbgs() << "    Found a non-simple store.\n");
 400       return false;
 401     }
 402     LoadAndStoreCounter++;
 403     Value *Ptr = St->getPointerOperand();
 404     // Check loop invariant.
 405     if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
 406       InvariantCounter++;
 407
 408     IsReadOnlyLoop = false;
 409   }
 410   return true;
 411 }
 412
 413 /// Check loop instructions and confirms it's good for
 414 /// LoopVersioningLICM.
 415 bool LoopVersioningLICM::legalLoopInstructions() {
 416   // Resetting counters.
 417   LoadAndStoreCounter = 0;
 418   InvariantCounter = 0;
 419   IsReadOnlyLoop = true;
 420   using namespace ore;
 421   // Iterate over loop blocks and instructions of each block and check
 422   // instruction safety.
 423   for (auto *Block : CurLoop->getBlocks())
 424     for (auto &Inst : *Block) {
 425       // If instruction is unsafe just return false.
 426       if (!instructionSafeForVersioning(&Inst)) {
 427         ORE->emit([&]() {
 428           return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)
 429                  << " Unsafe Loop Instruction";
 430         });
 431         return false;
 432       }
 433     }
 434   // Get LoopAccessInfo from current loop.
 435   LAI = &LAA->getInfo(CurLoop);
 436   // Check LoopAccessInfo for need of runtime check.
 437   if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
 438     LLVM_DEBUG(dbgs() << "    LAA: Runtime check not found !!\n");
 439     return false;
 440   }
 441   // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
 442   if (LAI->getNumRuntimePointerChecks() >
 443       VectorizerParams::RuntimeMemoryCheckThreshold) {
 444     LLVM_DEBUG(
 445         dbgs() << "    LAA: Runtime checks are more than threshold !!\n");
 446     ORE->emit([&]() {
 447       return OptimizationRemarkMissed(DEBUG_TYPE, "RuntimeCheck",
 448                                       CurLoop->getStartLoc(),
 449                                       CurLoop->getHeader())
 450              << "Number of runtime checks "
 451              << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks())
 452              << " exceeds threshold "
 453              << NV("Threshold", VectorizerParams::RuntimeMemoryCheckThreshold);
 454     });
 455     return false;
 456   }
 457   // Loop should have at least one invariant load or store instruction.
 458   if (!InvariantCounter) {
 459     LLVM_DEBUG(dbgs() << "    Invariant not found !!\n");
 460     return false;
 461   }
 462   // Read only loop not allowed.
 463   if (IsReadOnlyLoop) {
 464     LLVM_DEBUG(dbgs() << "    Found a read-only loop!\n");
 465     return false;
 466   }
 467   // Profitablity check:
 468   // Check invariant threshold, should be in limit.
 469   if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
 470     LLVM_DEBUG(
 471         dbgs()
 472         << "    Invariant load & store are less then defined threshold\n");
 473     LLVM_DEBUG(dbgs() << "    Invariant loads & stores: "
 474                       << ((InvariantCounter * 100) / LoadAndStoreCounter)
 475                       << "%\n");
 476     LLVM_DEBUG(dbgs() << "    Invariant loads & store threshold: "
 477                       << InvariantThreshold << "%\n");
 478     ORE->emit([&]() {
 479       return OptimizationRemarkMissed(DEBUG_TYPE, "InvariantThreshold",
 480                                       CurLoop->getStartLoc(),
 481                                       CurLoop->getHeader())
 482              << "Invariant load & store "
 483              << NV("LoadAndStoreCounter",
 484                    ((InvariantCounter * 100) / LoadAndStoreCounter))
 485              << " are less then defined threshold "
 486              << NV("Threshold", InvariantThreshold);
 487     });
 488     return false;
 489   }
 490   return true;
 491 }
 492
 493 /// It checks loop is already visited or not.
 494 /// check loop meta data, if loop revisited return true
 495 /// else false.
 496 bool LoopVersioningLICM::isLoopAlreadyVisited() {
 497   // Check LoopVersioningLICM metadata into loop
 498   if (findStringMetadataForLoop(CurLoop, LICMVersioningMetaData)) {
 499     return true;
 500   }
 501   return false;
 502 }
 503
 504 /// Checks legality for LoopVersioningLICM by considering following:
 505 /// a) loop structure legality   b) loop instruction legality
 506 /// c) loop memory access legality.
 507 /// Return true if legal else returns false.
 508 bool LoopVersioningLICM::isLegalForVersioning() {
 509   using namespace ore;
 510   LLVM_DEBUG(dbgs() << "Loop: " << *CurLoop);
 511   // Make sure not re-visiting same loop again.
 512   if (isLoopAlreadyVisited()) {
 513     LLVM_DEBUG(
 514         dbgs() << "    Revisiting loop in LoopVersioningLICM not allowed.\n\n");
 515     return false;
 516   }
 517   // Check loop structure leagality.
 518   if (!legalLoopStructure()) {
 519     LLVM_DEBUG(
 520         dbgs() << "    Loop structure not suitable for LoopVersioningLICM\n\n");
 521     ORE->emit([&]() {
 522       return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopStruct",
 523                                       CurLoop->getStartLoc(),
 524                                       CurLoop->getHeader())
 525              << " Unsafe Loop structure";
 526     });
 527     return false;
 528   }
 529   // Check loop instruction leagality.
 530   if (!legalLoopInstructions()) {
 531     LLVM_DEBUG(
 532         dbgs()
 533         << "    Loop instructions not suitable for LoopVersioningLICM\n\n");
 534     return false;
 535   }
 536   // Check loop memory access leagality.
 537   if (!legalLoopMemoryAccesses()) {
 538     LLVM_DEBUG(
 539         dbgs()
 540         << "    Loop memory access not suitable for LoopVersioningLICM\n\n");
 541     ORE->emit([&]() {
 542       return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopMemoryAccess",
 543                                       CurLoop->getStartLoc(),
 544                                       CurLoop->getHeader())
 545              << " Unsafe Loop memory access";
 546     });
 547     return false;
 548   }
 549   // Loop versioning is feasible, return true.
 550   LLVM_DEBUG(dbgs() << "    Loop Versioning found to be beneficial\n\n");
 551   ORE->emit([&]() {
 552     return OptimizationRemark(DEBUG_TYPE, "IsLegalForVersioning",
 553                               CurLoop->getStartLoc(), CurLoop->getHeader())
 554            << " Versioned loop for LICM."
 555            << " Number of runtime checks we had to insert "
 556            << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks());
 557   });
 558   return true;
 559 }
 560
 561 /// Update loop with aggressive aliasing assumptions.
 562 /// It marks no-alias to any pairs of memory operations by assuming
 563 /// loop should not have any must-alias memory accesses pairs.
 564 /// During LoopVersioningLICM legality we ignore loops having must
 565 /// aliasing memory accesses.
 566 void LoopVersioningLICM::setNoAliasToLoop(Loop *VerLoop) {
 567   // Get latch terminator instruction.
 568   Instruction *I = VerLoop->getLoopLatch()->getTerminator();
 569   // Create alias scope domain.
 570   MDBuilder MDB(I->getContext());
 571   MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("LVDomain");
 572   StringRef Name = "LVAliasScope";
 573   SmallVector<Metadata *, 4> Scopes, NoAliases;
 574   MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
 575   // Iterate over each instruction of loop.
 576   // set no-alias for all load & store instructions.
 577   for (auto *Block : CurLoop->getBlocks()) {
 578     for (auto &Inst : *Block) {
 579       // Only interested in instruction that may modify or read memory.
 580       if (!Inst.mayReadFromMemory() && !Inst.mayWriteToMemory())
 581         continue;
 582       Scopes.push_back(NewScope);
 583       NoAliases.push_back(NewScope);
 584       // Set no-alias for current instruction.
 585       Inst.setMetadata(
 586           LLVMContext::MD_noalias,
 587           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_noalias),
 588                               MDNode::get(Inst.getContext(), NoAliases)));
 589       // set alias-scope for current instruction.
 590       Inst.setMetadata(
 591           LLVMContext::MD_alias_scope,
 592           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_alias_scope),
 593                               MDNode::get(Inst.getContext(), Scopes)));
 594     }
 595   }
 596 }
 597
 598 bool LoopVersioningLICM::runOnLoop(Loop *L, LPPassManager &LPM) {
 599   // This will automatically release all resources hold by the current
 600   // LoopVersioningLICM object.
 601   AutoResetter Resetter(*this);
 602
 603   if (skipLoop(L))
 604     return false;
 605
 606   // Do not do the transformation if disabled by metadata.
 607   if (hasLICMVersioningTransformation(L) & TM_Disable)
 608     return false;
 609
 610   // Get Analysis information.
 611   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 612   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 613   LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
 614   ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
 615   LAI = nullptr;
 616   // Set Current Loop
 617   CurLoop = L;
 618   CurAST.reset(new AliasSetTracker(*AA));
 619
 620   // Loop over the body of this loop, construct AST.
 621   LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 622   for (auto *Block : L->getBlocks()) {
 623     if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
 624       CurAST->add(*Block);          // Incorporate the specified basic block
 625   }
 626
 627   bool Changed = false;
 628
 629   // Check feasiblity of LoopVersioningLICM.
 630   // If versioning found to be feasible and beneficial then proceed
 631   // else simply return, by cleaning up memory.
 632   if (isLegalForVersioning()) {
 633     // Do loop versioning.
 634     // Create memcheck for memory accessed inside loop.
 635     // Clone original loop, and set blocks properly.
 636     DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 637     LoopVersioning LVer(*LAI, CurLoop, LI, DT, SE, true);
 638     LVer.versionLoop();
 639     // Set Loop Versioning metaData for original loop.
 640     addStringMetadataToLoop(LVer.getNonVersionedLoop(), LICMVersioningMetaData);
 641     // Set Loop Versioning metaData for version loop.
 642     addStringMetadataToLoop(LVer.getVersionedLoop(), LICMVersioningMetaData);
 643     // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
 644     // FIXME: "llvm.mem.parallel_loop_access" annotates memory access
 645     // instructions, not loops.
 646     addStringMetadataToLoop(LVer.getVersionedLoop(),
 647                             "llvm.mem.parallel_loop_access");
 648     // Update version loop with aggressive aliasing assumption.
 649     setNoAliasToLoop(LVer.getVersionedLoop());
 650     Changed = true;
 651   }
 652   return Changed;
 653 }
 654
 655 char LoopVersioningLICM::ID = 0;
 656
 657 INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm",
 658                       "Loop Versioning For LICM", false, false)
 659 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 660 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 661 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 662 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 663 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
 664 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 665 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 666 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 667 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 668 INITIALIZE_PASS_END(LoopVersioningLICM, "loop-versioning-licm",
 669                     "Loop Versioning For LICM", false, false)
 670
 671 Pass *llvm::createLoopVersioningLICMPass() { return new LoopVersioningLICM(); }