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