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