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