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