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(); } 664