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/LoopAccessAnalysis.h" 18 #include "llvm/Analysis/LoopInfo.h" 19 #include "llvm/IR/Dominators.h" 20 #include "llvm/IR/MDBuilder.h" 21 #include "llvm/InitializePasses.h" 22 #include "llvm/Support/CommandLine.h" 23 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 24 #include "llvm/Transforms/Utils/Cloning.h" 25 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 26 27 using namespace llvm; 28 29 static cl::opt<bool> 30 AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true), 31 cl::Hidden, 32 cl::desc("Add no-alias annotation for instructions that " 33 "are disambiguated by memchecks")); 34 35 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, 36 DominatorTree *DT, ScalarEvolution *SE, 37 bool UseLAIChecks) 38 : VersionedLoop(L), NonVersionedLoop(nullptr), LAI(LAI), LI(LI), DT(DT), 39 SE(SE) { 40 assert(L->getExitBlock() && "No single exit block"); 41 assert(L->isLoopSimplifyForm() && "Loop is not in loop-simplify form"); 42 if (UseLAIChecks) { 43 setAliasChecks(LAI.getRuntimePointerChecking()->getChecks()); 44 setSCEVChecks(LAI.getPSE().getUnionPredicate()); 45 } 46 } 47 48 void LoopVersioning::setAliasChecks(ArrayRef<RuntimePointerCheck> Checks) { 49 AliasChecks = {Checks.begin(), Checks.end()}; 50 } 51 52 void LoopVersioning::setSCEVChecks(SCEVUnionPredicate Check) { 53 Preds = std::move(Check); 54 } 55 56 void LoopVersioning::versionLoop( 57 const SmallVectorImpl<Instruction *> &DefsUsedOutside) { 58 Instruction *FirstCheckInst; 59 Instruction *MemRuntimeCheck; 60 Value *SCEVRuntimeCheck; 61 Value *RuntimeCheck = nullptr; 62 63 // Add the memcheck in the original preheader (this is empty initially). 64 BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader(); 65 const auto &RtPtrChecking = *LAI.getRuntimePointerChecking(); 66 std::tie(FirstCheckInst, MemRuntimeCheck) = 67 addRuntimeChecks(RuntimeCheckBB->getTerminator(), VersionedLoop, 68 AliasChecks, RtPtrChecking.getSE()); 69 70 const SCEVUnionPredicate &Pred = LAI.getPSE().getUnionPredicate(); 71 SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(), 72 "scev.check"); 73 SCEVRuntimeCheck = 74 Exp.expandCodeForPredicate(&Pred, RuntimeCheckBB->getTerminator()); 75 auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck); 76 77 // Discard the SCEV runtime check if it is always true. 78 if (CI && CI->isZero()) 79 SCEVRuntimeCheck = nullptr; 80 81 if (MemRuntimeCheck && SCEVRuntimeCheck) { 82 RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck, 83 SCEVRuntimeCheck, "lver.safe"); 84 if (auto *I = dyn_cast<Instruction>(RuntimeCheck)) 85 I->insertBefore(RuntimeCheckBB->getTerminator()); 86 } else 87 RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck; 88 89 assert(RuntimeCheck && "called even though we don't need " 90 "any runtime checks"); 91 92 // Rename the block to make the IR more readable. 93 RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() + 94 ".lver.check"); 95 96 // Create empty preheader for the loop (and after cloning for the 97 // non-versioned loop). 98 BasicBlock *PH = 99 SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI, 100 nullptr, VersionedLoop->getHeader()->getName() + ".ph"); 101 102 // Clone the loop including the preheader. 103 // 104 // FIXME: This does not currently preserve SimplifyLoop because the exit 105 // block is a join between the two loops. 106 SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks; 107 NonVersionedLoop = 108 cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap, 109 ".lver.orig", LI, DT, NonVersionedLoopBlocks); 110 remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap); 111 112 // Insert the conditional branch based on the result of the memchecks. 113 Instruction *OrigTerm = RuntimeCheckBB->getTerminator(); 114 BranchInst::Create(NonVersionedLoop->getLoopPreheader(), 115 VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm); 116 OrigTerm->eraseFromParent(); 117 118 // The loops merge in the original exit block. This is now dominated by the 119 // memchecking block. 120 DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB); 121 122 // Adds the necessary PHI nodes for the versioned loops based on the 123 // loop-defined values used outside of the loop. 124 addPHINodes(DefsUsedOutside); 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 /// Also expose this is a pass. Currently this is only used for 257 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing 258 /// array accesses from the loop. 259 class LoopVersioningPass : public FunctionPass { 260 public: 261 LoopVersioningPass() : FunctionPass(ID) { 262 initializeLoopVersioningPassPass(*PassRegistry::getPassRegistry()); 263 } 264 265 bool runOnFunction(Function &F) override { 266 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 267 auto *LAA = &getAnalysis<LoopAccessLegacyAnalysis>(); 268 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 269 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 270 271 // Build up a worklist of inner-loops to version. This is necessary as the 272 // act of versioning a loop creates new loops and can invalidate iterators 273 // across the loops. 274 SmallVector<Loop *, 8> Worklist; 275 276 for (Loop *TopLevelLoop : *LI) 277 for (Loop *L : depth_first(TopLevelLoop)) 278 // We only handle inner-most loops. 279 if (L->empty()) 280 Worklist.push_back(L); 281 282 // Now walk the identified inner loops. 283 bool Changed = false; 284 for (Loop *L : Worklist) { 285 const LoopAccessInfo &LAI = LAA->getInfo(L); 286 if (L->isLoopSimplifyForm() && !LAI.hasConvergentOp() && 287 (LAI.getNumRuntimePointerChecks() || 288 !LAI.getPSE().getUnionPredicate().isAlwaysTrue())) { 289 LoopVersioning LVer(LAI, L, LI, DT, SE); 290 LVer.versionLoop(); 291 LVer.annotateLoopWithNoAlias(); 292 Changed = true; 293 } 294 } 295 296 return Changed; 297 } 298 299 void getAnalysisUsage(AnalysisUsage &AU) const override { 300 AU.addRequired<LoopInfoWrapperPass>(); 301 AU.addPreserved<LoopInfoWrapperPass>(); 302 AU.addRequired<LoopAccessLegacyAnalysis>(); 303 AU.addRequired<DominatorTreeWrapperPass>(); 304 AU.addPreserved<DominatorTreeWrapperPass>(); 305 AU.addRequired<ScalarEvolutionWrapperPass>(); 306 } 307 308 static char ID; 309 }; 310 } 311 312 #define LVER_OPTION "loop-versioning" 313 #define DEBUG_TYPE LVER_OPTION 314 315 char LoopVersioningPass::ID; 316 static const char LVer_name[] = "Loop Versioning"; 317 318 INITIALIZE_PASS_BEGIN(LoopVersioningPass, LVER_OPTION, LVer_name, false, false) 319 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 320 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis) 321 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 322 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 323 INITIALIZE_PASS_END(LoopVersioningPass, LVER_OPTION, LVer_name, false, false) 324 325 namespace llvm { 326 FunctionPass *createLoopVersioningPass() { 327 return new LoopVersioningPass(); 328 } 329 } 330