1 //===- LoopVersioning.cpp - Utility to version a loop ---------------------===// 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 // This file defines a utility class to perform loop versioning. The versioned 10 // loop speculates that otherwise may-aliasing memory accesses don't overlap and 11 // emits checks to prove this. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Transforms/Utils/LoopVersioning.h" 16 #include "llvm/ADT/ArrayRef.h" 17 #include "llvm/Analysis/AliasAnalysis.h" 18 #include "llvm/Analysis/LoopAccessAnalysis.h" 19 #include "llvm/Analysis/LoopInfo.h" 20 #include "llvm/Analysis/MemorySSA.h" 21 #include "llvm/Analysis/ScalarEvolution.h" 22 #include "llvm/Analysis/TargetLibraryInfo.h" 23 #include "llvm/IR/Dominators.h" 24 #include "llvm/IR/MDBuilder.h" 25 #include "llvm/IR/PassManager.h" 26 #include "llvm/InitializePasses.h" 27 #include "llvm/Support/CommandLine.h" 28 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 29 #include "llvm/Transforms/Utils/Cloning.h" 30 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 31 32 using namespace llvm; 33 34 static cl::opt<bool> 35 AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true), 36 cl::Hidden, 37 cl::desc("Add no-alias annotation for instructions that " 38 "are disambiguated by memchecks")); 39 40 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, 41 ArrayRef<RuntimePointerCheck> Checks, Loop *L, 42 LoopInfo *LI, DominatorTree *DT, 43 ScalarEvolution *SE) 44 : VersionedLoop(L), NonVersionedLoop(nullptr), 45 AliasChecks(Checks.begin(), Checks.end()), 46 Preds(LAI.getPSE().getUnionPredicate()), LAI(LAI), LI(LI), DT(DT), 47 SE(SE) { 48 assert(L->getExitBlock() && "No single exit block"); 49 assert(L->isLoopSimplifyForm() && "Loop is not in loop-simplify form"); 50 } 51 52 void LoopVersioning::versionLoop( 53 const SmallVectorImpl<Instruction *> &DefsUsedOutside) { 54 Instruction *FirstCheckInst; 55 Instruction *MemRuntimeCheck; 56 Value *SCEVRuntimeCheck; 57 Value *RuntimeCheck = nullptr; 58 59 // Add the memcheck in the original preheader (this is empty initially). 60 BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader(); 61 const auto &RtPtrChecking = *LAI.getRuntimePointerChecking(); 62 std::tie(FirstCheckInst, MemRuntimeCheck) = 63 addRuntimeChecks(RuntimeCheckBB->getTerminator(), VersionedLoop, 64 AliasChecks, RtPtrChecking.getSE()); 65 66 SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(), 67 "scev.check"); 68 SCEVRuntimeCheck = 69 Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator()); 70 auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck); 71 72 // Discard the SCEV runtime check if it is always true. 73 if (CI && CI->isZero()) 74 SCEVRuntimeCheck = nullptr; 75 76 if (MemRuntimeCheck && SCEVRuntimeCheck) { 77 RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck, 78 SCEVRuntimeCheck, "lver.safe"); 79 if (auto *I = dyn_cast<Instruction>(RuntimeCheck)) 80 I->insertBefore(RuntimeCheckBB->getTerminator()); 81 } else 82 RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck; 83 84 assert(RuntimeCheck && "called even though we don't need " 85 "any runtime checks"); 86 87 // Rename the block to make the IR more readable. 88 RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() + 89 ".lver.check"); 90 91 // Create empty preheader for the loop (and after cloning for the 92 // non-versioned loop). 93 BasicBlock *PH = 94 SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI, 95 nullptr, VersionedLoop->getHeader()->getName() + ".ph"); 96 97 // Clone the loop including the preheader. 98 // 99 // FIXME: This does not currently preserve SimplifyLoop because the exit 100 // block is a join between the two loops. 101 SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks; 102 NonVersionedLoop = 103 cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap, 104 ".lver.orig", LI, DT, NonVersionedLoopBlocks); 105 remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap); 106 107 // Insert the conditional branch based on the result of the memchecks. 108 Instruction *OrigTerm = RuntimeCheckBB->getTerminator(); 109 BranchInst::Create(NonVersionedLoop->getLoopPreheader(), 110 VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm); 111 OrigTerm->eraseFromParent(); 112 113 // The loops merge in the original exit block. This is now dominated by the 114 // memchecking block. 115 DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB); 116 117 // Adds the necessary PHI nodes for the versioned loops based on the 118 // loop-defined values used outside of the loop. 119 addPHINodes(DefsUsedOutside); 120 formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true); 121 formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true); 122 assert(NonVersionedLoop->isLoopSimplifyForm() && 123 VersionedLoop->isLoopSimplifyForm() && 124 "The versioned loops should be in simplify form."); 125 } 126 127 void LoopVersioning::addPHINodes( 128 const SmallVectorImpl<Instruction *> &DefsUsedOutside) { 129 BasicBlock *PHIBlock = VersionedLoop->getExitBlock(); 130 assert(PHIBlock && "No single successor to loop exit block"); 131 PHINode *PN; 132 133 // First add a single-operand PHI for each DefsUsedOutside if one does not 134 // exists yet. 135 for (auto *Inst : DefsUsedOutside) { 136 // See if we have a single-operand PHI with the value defined by the 137 // original loop. 138 for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) { 139 if (PN->getIncomingValue(0) == Inst) 140 break; 141 } 142 // If not create it. 143 if (!PN) { 144 PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver", 145 &PHIBlock->front()); 146 SmallVector<User*, 8> UsersToUpdate; 147 for (User *U : Inst->users()) 148 if (!VersionedLoop->contains(cast<Instruction>(U)->getParent())) 149 UsersToUpdate.push_back(U); 150 for (User *U : UsersToUpdate) 151 U->replaceUsesOfWith(Inst, PN); 152 PN->addIncoming(Inst, VersionedLoop->getExitingBlock()); 153 } 154 } 155 156 // Then for each PHI add the operand for the edge from the cloned loop. 157 for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) { 158 assert(PN->getNumOperands() == 1 && 159 "Exit block should only have on predecessor"); 160 161 // If the definition was cloned used that otherwise use the same value. 162 Value *ClonedValue = PN->getIncomingValue(0); 163 auto Mapped = VMap.find(ClonedValue); 164 if (Mapped != VMap.end()) 165 ClonedValue = Mapped->second; 166 167 PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock()); 168 } 169 } 170 171 void LoopVersioning::prepareNoAliasMetadata() { 172 // We need to turn the no-alias relation between pointer checking groups into 173 // no-aliasing annotations between instructions. 174 // 175 // We accomplish this by mapping each pointer checking group (a set of 176 // pointers memchecked together) to an alias scope and then also mapping each 177 // group to the list of scopes it can't alias. 178 179 const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking(); 180 LLVMContext &Context = VersionedLoop->getHeader()->getContext(); 181 182 // First allocate an aliasing scope for each pointer checking group. 183 // 184 // While traversing through the checking groups in the loop, also create a 185 // reverse map from pointers to the pointer checking group they were assigned 186 // to. 187 MDBuilder MDB(Context); 188 MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain"); 189 190 for (const auto &Group : RtPtrChecking->CheckingGroups) { 191 GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain); 192 193 for (unsigned PtrIdx : Group.Members) 194 PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group; 195 } 196 197 // Go through the checks and for each pointer group, collect the scopes for 198 // each non-aliasing pointer group. 199 DenseMap<const RuntimeCheckingPtrGroup *, SmallVector<Metadata *, 4>> 200 GroupToNonAliasingScopes; 201 202 for (const auto &Check : AliasChecks) 203 GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]); 204 205 // Finally, transform the above to actually map to scope list which is what 206 // the metadata uses. 207 208 for (auto Pair : GroupToNonAliasingScopes) 209 GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second); 210 } 211 212 void LoopVersioning::annotateLoopWithNoAlias() { 213 if (!AnnotateNoAlias) 214 return; 215 216 // First prepare the maps. 217 prepareNoAliasMetadata(); 218 219 // Add the scope and no-alias metadata to the instructions. 220 for (Instruction *I : LAI.getDepChecker().getMemoryInstructions()) { 221 annotateInstWithNoAlias(I); 222 } 223 } 224 225 void LoopVersioning::annotateInstWithNoAlias(Instruction *VersionedInst, 226 const Instruction *OrigInst) { 227 if (!AnnotateNoAlias) 228 return; 229 230 LLVMContext &Context = VersionedLoop->getHeader()->getContext(); 231 const Value *Ptr = isa<LoadInst>(OrigInst) 232 ? cast<LoadInst>(OrigInst)->getPointerOperand() 233 : cast<StoreInst>(OrigInst)->getPointerOperand(); 234 235 // Find the group for the pointer and then add the scope metadata. 236 auto Group = PtrToGroup.find(Ptr); 237 if (Group != PtrToGroup.end()) { 238 VersionedInst->setMetadata( 239 LLVMContext::MD_alias_scope, 240 MDNode::concatenate( 241 VersionedInst->getMetadata(LLVMContext::MD_alias_scope), 242 MDNode::get(Context, GroupToScope[Group->second]))); 243 244 // Add the no-alias metadata. 245 auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second); 246 if (NonAliasingScopeList != GroupToNonAliasingScopeList.end()) 247 VersionedInst->setMetadata( 248 LLVMContext::MD_noalias, 249 MDNode::concatenate( 250 VersionedInst->getMetadata(LLVMContext::MD_noalias), 251 NonAliasingScopeList->second)); 252 } 253 } 254 255 namespace { 256 bool runImpl(LoopInfo *LI, function_ref<const LoopAccessInfo &(Loop &)> GetLAA, 257 DominatorTree *DT, ScalarEvolution *SE) { 258 // Build up a worklist of inner-loops to version. This is necessary as the 259 // act of versioning a loop creates new loops and can invalidate iterators 260 // across the loops. 261 SmallVector<Loop *, 8> Worklist; 262 263 for (Loop *TopLevelLoop : *LI) 264 for (Loop *L : depth_first(TopLevelLoop)) 265 // We only handle inner-most loops. 266 if (L->isInnermost()) 267 Worklist.push_back(L); 268 269 // Now walk the identified inner loops. 270 bool Changed = false; 271 for (Loop *L : Worklist) { 272 const LoopAccessInfo &LAI = GetLAA(*L); 273 if (L->isLoopSimplifyForm() && !LAI.hasConvergentOp() && 274 (LAI.getNumRuntimePointerChecks() || 275 !LAI.getPSE().getUnionPredicate().isAlwaysTrue())) { 276 LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L, 277 LI, DT, SE); 278 LVer.versionLoop(); 279 LVer.annotateLoopWithNoAlias(); 280 Changed = true; 281 } 282 } 283 284 return Changed; 285 } 286 287 /// Also expose this is a pass. Currently this is only used for 288 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing 289 /// array accesses from the loop. 290 class LoopVersioningLegacyPass : public FunctionPass { 291 public: 292 LoopVersioningLegacyPass() : FunctionPass(ID) { 293 initializeLoopVersioningLegacyPassPass(*PassRegistry::getPassRegistry()); 294 } 295 296 bool runOnFunction(Function &F) override { 297 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 298 auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & { 299 return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(&L); 300 }; 301 302 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 303 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 304 305 return runImpl(LI, GetLAA, DT, SE); 306 } 307 308 void getAnalysisUsage(AnalysisUsage &AU) const override { 309 AU.addRequired<LoopInfoWrapperPass>(); 310 AU.addPreserved<LoopInfoWrapperPass>(); 311 AU.addRequired<LoopAccessLegacyAnalysis>(); 312 AU.addRequired<DominatorTreeWrapperPass>(); 313 AU.addPreserved<DominatorTreeWrapperPass>(); 314 AU.addRequired<ScalarEvolutionWrapperPass>(); 315 } 316 317 static char ID; 318 }; 319 } 320 321 #define LVER_OPTION "loop-versioning" 322 #define DEBUG_TYPE LVER_OPTION 323 324 char LoopVersioningLegacyPass::ID; 325 static const char LVer_name[] = "Loop Versioning"; 326 327 INITIALIZE_PASS_BEGIN(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false, 328 false) 329 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 330 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis) 331 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 332 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 333 INITIALIZE_PASS_END(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false, 334 false) 335 336 namespace llvm { 337 FunctionPass *createLoopVersioningLegacyPass() { 338 return new LoopVersioningLegacyPass(); 339 } 340 341 PreservedAnalyses LoopVersioningPass::run(Function &F, 342 FunctionAnalysisManager &AM) { 343 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 344 auto &LI = AM.getResult<LoopAnalysis>(F); 345 auto &TTI = AM.getResult<TargetIRAnalysis>(F); 346 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 347 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 348 auto &AA = AM.getResult<AAManager>(F); 349 auto &AC = AM.getResult<AssumptionAnalysis>(F); 350 MemorySSA *MSSA = EnableMSSALoopDependency 351 ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() 352 : nullptr; 353 354 auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager(); 355 auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & { 356 LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, 357 TLI, TTI, nullptr, MSSA}; 358 return LAM.getResult<LoopAccessAnalysis>(L, AR); 359 }; 360 361 if (runImpl(&LI, GetLAA, &DT, &SE)) 362 return PreservedAnalyses::none(); 363 return PreservedAnalyses::all(); 364 } 365 } // namespace llvm 366