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/InstSimplifyFolder.h" 19 #include "llvm/Analysis/LoopAccessAnalysis.h" 20 #include "llvm/Analysis/LoopInfo.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/Support/CommandLine.h" 27 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 28 #include "llvm/Transforms/Utils/Cloning.h" 29 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 30 31 using namespace llvm; 32 33 #define DEBUG_TYPE "loop-versioning" 34 35 static cl::opt<bool> 36 AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true), 37 cl::Hidden, 38 cl::desc("Add no-alias annotation for instructions that " 39 "are disambiguated by memchecks")); 40 41 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, 42 ArrayRef<RuntimePointerCheck> Checks, Loop *L, 43 LoopInfo *LI, DominatorTree *DT, 44 ScalarEvolution *SE) 45 : VersionedLoop(L), AliasChecks(Checks), Preds(LAI.getPSE().getPredicate()), 46 LAI(LAI), LI(LI), DT(DT), SE(SE) {} 47 48 void LoopVersioning::versionLoop( 49 const SmallVectorImpl<Instruction *> &DefsUsedOutside) { 50 assert(VersionedLoop->getUniqueExitBlock() && "No single exit block"); 51 assert(VersionedLoop->isLoopSimplifyForm() && 52 "Loop is not in loop-simplify form"); 53 54 Value *MemRuntimeCheck; 55 Value *SCEVRuntimeCheck; 56 Value *RuntimeCheck = nullptr; 57 58 // Add the memcheck in the original preheader (this is empty initially). 59 BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader(); 60 const auto &RtPtrChecking = *LAI.getRuntimePointerChecking(); 61 62 SCEVExpander Exp2(*RtPtrChecking.getSE(), 63 VersionedLoop->getHeader()->getDataLayout(), 64 "induction"); 65 MemRuntimeCheck = addRuntimeChecks(RuntimeCheckBB->getTerminator(), 66 VersionedLoop, AliasChecks, Exp2); 67 68 SCEVExpander Exp(*SE, RuntimeCheckBB->getDataLayout(), 69 "scev.check"); 70 SCEVRuntimeCheck = 71 Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator()); 72 73 IRBuilder<InstSimplifyFolder> Builder( 74 RuntimeCheckBB->getContext(), 75 InstSimplifyFolder(RuntimeCheckBB->getDataLayout())); 76 if (MemRuntimeCheck && SCEVRuntimeCheck) { 77 Builder.SetInsertPoint(RuntimeCheckBB->getTerminator()); 78 RuntimeCheck = 79 Builder.CreateOr(MemRuntimeCheck, SCEVRuntimeCheck, "lver.safe"); 80 } else 81 RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck; 82 83 assert(RuntimeCheck && "called even though we don't need " 84 "any runtime checks"); 85 86 // Rename the block to make the IR more readable. 87 RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() + 88 ".lver.check"); 89 90 // Create empty preheader for the loop (and after cloning for the 91 // non-versioned loop). 92 BasicBlock *PH = 93 SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI, 94 nullptr, VersionedLoop->getHeader()->getName() + ".ph"); 95 96 // Clone the loop including the preheader. 97 // 98 // FIXME: This does not currently preserve SimplifyLoop because the exit 99 // block is a join between the two loops. 100 SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks; 101 NonVersionedLoop = 102 cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap, 103 ".lver.orig", LI, DT, NonVersionedLoopBlocks); 104 remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap); 105 106 // Insert the conditional branch based on the result of the memchecks. 107 Instruction *OrigTerm = RuntimeCheckBB->getTerminator(); 108 Builder.SetInsertPoint(OrigTerm); 109 Builder.CreateCondBr(RuntimeCheck, NonVersionedLoop->getLoopPreheader(), 110 VersionedLoop->getLoopPreheader()); 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 SE->forgetValue(PN); 141 break; 142 } 143 } 144 // If not create it. 145 if (!PN) { 146 PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver"); 147 PN->insertBefore(PHIBlock->begin()); 148 SmallVector<User*, 8> UsersToUpdate; 149 for (User *U : Inst->users()) 150 if (!VersionedLoop->contains(cast<Instruction>(U)->getParent())) 151 UsersToUpdate.push_back(U); 152 for (User *U : UsersToUpdate) 153 U->replaceUsesOfWith(Inst, PN); 154 PN->addIncoming(Inst, VersionedLoop->getExitingBlock()); 155 } 156 } 157 158 // Then for each PHI add the operand for the edge from the cloned loop. 159 for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) { 160 assert(PN->getNumOperands() == 1 && 161 "Exit block should only have on predecessor"); 162 163 // If the definition was cloned used that otherwise use the same value. 164 Value *ClonedValue = PN->getIncomingValue(0); 165 auto Mapped = VMap.find(ClonedValue); 166 if (Mapped != VMap.end()) 167 ClonedValue = Mapped->second; 168 169 PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock()); 170 } 171 } 172 173 void LoopVersioning::prepareNoAliasMetadata() { 174 // We need to turn the no-alias relation between pointer checking groups into 175 // no-aliasing annotations between instructions. 176 // 177 // We accomplish this by mapping each pointer checking group (a set of 178 // pointers memchecked together) to an alias scope and then also mapping each 179 // group to the list of scopes it can't alias. 180 181 const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking(); 182 LLVMContext &Context = VersionedLoop->getHeader()->getContext(); 183 184 // First allocate an aliasing scope for each pointer checking group. 185 // 186 // While traversing through the checking groups in the loop, also create a 187 // reverse map from pointers to the pointer checking group they were assigned 188 // to. 189 MDBuilder MDB(Context); 190 MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain"); 191 192 for (const auto &Group : RtPtrChecking->CheckingGroups) { 193 GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain); 194 195 for (unsigned PtrIdx : Group.Members) 196 PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group; 197 } 198 199 // Go through the checks and for each pointer group, collect the scopes for 200 // each non-aliasing pointer group. 201 DenseMap<const RuntimeCheckingPtrGroup *, SmallVector<Metadata *, 4>> 202 GroupToNonAliasingScopes; 203 204 for (const auto &Check : AliasChecks) 205 GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]); 206 207 // Finally, transform the above to actually map to scope list which is what 208 // the metadata uses. 209 210 for (const auto &Pair : GroupToNonAliasingScopes) 211 GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second); 212 } 213 214 void LoopVersioning::annotateLoopWithNoAlias() { 215 if (!AnnotateNoAlias) 216 return; 217 218 // First prepare the maps. 219 prepareNoAliasMetadata(); 220 221 // Add the scope and no-alias metadata to the instructions. 222 for (Instruction *I : LAI.getDepChecker().getMemoryInstructions()) { 223 annotateInstWithNoAlias(I); 224 } 225 } 226 227 void LoopVersioning::annotateInstWithNoAlias(Instruction *VersionedInst, 228 const Instruction *OrigInst) { 229 if (!AnnotateNoAlias) 230 return; 231 232 LLVMContext &Context = VersionedLoop->getHeader()->getContext(); 233 const Value *Ptr = isa<LoadInst>(OrigInst) 234 ? cast<LoadInst>(OrigInst)->getPointerOperand() 235 : cast<StoreInst>(OrigInst)->getPointerOperand(); 236 237 // Find the group for the pointer and then add the scope metadata. 238 auto Group = PtrToGroup.find(Ptr); 239 if (Group != PtrToGroup.end()) { 240 VersionedInst->setMetadata( 241 LLVMContext::MD_alias_scope, 242 MDNode::concatenate( 243 VersionedInst->getMetadata(LLVMContext::MD_alias_scope), 244 MDNode::get(Context, GroupToScope[Group->second]))); 245 246 // Add the no-alias metadata. 247 auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second); 248 if (NonAliasingScopeList != GroupToNonAliasingScopeList.end()) 249 VersionedInst->setMetadata( 250 LLVMContext::MD_noalias, 251 MDNode::concatenate( 252 VersionedInst->getMetadata(LLVMContext::MD_noalias), 253 NonAliasingScopeList->second)); 254 } 255 } 256 257 namespace { 258 bool runImpl(LoopInfo *LI, LoopAccessInfoManager &LAIs, DominatorTree *DT, 259 ScalarEvolution *SE) { 260 // Build up a worklist of inner-loops to version. This is necessary as the 261 // act of versioning a loop creates new loops and can invalidate iterators 262 // across the loops. 263 SmallVector<Loop *, 8> Worklist; 264 265 for (Loop *TopLevelLoop : *LI) 266 for (Loop *L : depth_first(TopLevelLoop)) 267 // We only handle inner-most loops. 268 if (L->isInnermost()) 269 Worklist.push_back(L); 270 271 // Now walk the identified inner loops. 272 bool Changed = false; 273 for (Loop *L : Worklist) { 274 if (!L->isLoopSimplifyForm() || !L->isRotatedForm() || 275 !L->getExitingBlock()) 276 continue; 277 const LoopAccessInfo &LAI = LAIs.getInfo(*L); 278 if (!LAI.hasConvergentOp() && 279 (LAI.getNumRuntimePointerChecks() || 280 !LAI.getPSE().getPredicate().isAlwaysTrue())) { 281 LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L, 282 LI, DT, SE); 283 LVer.versionLoop(); 284 LVer.annotateLoopWithNoAlias(); 285 Changed = true; 286 LAIs.clear(); 287 } 288 } 289 290 return Changed; 291 } 292 } 293 294 PreservedAnalyses LoopVersioningPass::run(Function &F, 295 FunctionAnalysisManager &AM) { 296 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 297 auto &LI = AM.getResult<LoopAnalysis>(F); 298 LoopAccessInfoManager &LAIs = AM.getResult<LoopAccessAnalysis>(F); 299 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 300 301 if (runImpl(&LI, LAIs, &DT, &SE)) 302 return PreservedAnalyses::none(); 303 return PreservedAnalyses::all(); 304 } 305