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