325 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines a utility class to perform loop versioning. The versioned10// loop speculates that otherwise may-aliasing memory accesses don't overlap and11// 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/IR/ProfDataUtils.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/LoopUtils.h"31#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"32 33using namespace llvm;34 35#define DEBUG_TYPE "loop-versioning"36 37static cl::opt<bool>38 AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),39 cl::Hidden,40 cl::desc("Add no-alias annotation for instructions that "41 "are disambiguated by memchecks"));42 43LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI,44 ArrayRef<RuntimePointerCheck> Checks, Loop *L,45 LoopInfo *LI, DominatorTree *DT,46 ScalarEvolution *SE)47 : VersionedLoop(L), AliasChecks(Checks), Preds(LAI.getPSE().getPredicate()),48 LAI(LAI), LI(LI), DT(DT), SE(SE) {}49 50void 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()->getDataLayout(),66 "induction");67 MemRuntimeCheck = addRuntimeChecks(RuntimeCheckBB->getTerminator(),68 VersionedLoop, AliasChecks, Exp2);69 70 SCEVExpander Exp(*SE, RuntimeCheckBB->getDataLayout(),71 "scev.check");72 SCEVRuntimeCheck =73 Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator());74 75 IRBuilder<InstSimplifyFolder> Builder(76 RuntimeCheckBB->getContext(),77 InstSimplifyFolder(RuntimeCheckBB->getDataLayout()));78 if (MemRuntimeCheck && SCEVRuntimeCheck) {79 Builder.SetInsertPoint(RuntimeCheckBB->getTerminator());80 RuntimeCheck =81 Builder.CreateOr(MemRuntimeCheck, SCEVRuntimeCheck, "lver.safe");82 } else83 RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;84 85 Exp.eraseDeadInstructions(SCEVRuntimeCheck);86 87 assert(RuntimeCheck && "called even though we don't need "88 "any runtime checks");89 90 // Rename the block to make the IR more readable.91 RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +92 ".lver.check");93 94 // Create empty preheader for the loop (and after cloning for the95 // non-versioned loop).96 BasicBlock *PH =97 SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI,98 nullptr, VersionedLoop->getHeader()->getName() + ".ph");99 100 // Clone the loop including the preheader.101 //102 // FIXME: This does not currently preserve SimplifyLoop because the exit103 // block is a join between the two loops.104 SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;105 NonVersionedLoop =106 cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,107 ".lver.orig", LI, DT, NonVersionedLoopBlocks);108 remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);109 110 // Insert the conditional branch based on the result of the memchecks.111 Instruction *OrigTerm = RuntimeCheckBB->getTerminator();112 Builder.SetInsertPoint(OrigTerm);113 auto *BI =114 Builder.CreateCondBr(RuntimeCheck, NonVersionedLoop->getLoopPreheader(),115 VersionedLoop->getLoopPreheader());116 // We don't know what the probability of executing the versioned vs the117 // unversioned variants is.118 setExplicitlyUnknownBranchWeightsIfProfiled(*BI, DEBUG_TYPE);119 OrigTerm->eraseFromParent();120 121 // The loops merge in the original exit block. This is now dominated by the122 // memchecking block.123 DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);124 125 // Adds the necessary PHI nodes for the versioned loops based on the126 // loop-defined values used outside of the loop.127 addPHINodes(DefsUsedOutside);128 formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true);129 formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true);130 assert(NonVersionedLoop->isLoopSimplifyForm() &&131 VersionedLoop->isLoopSimplifyForm() &&132 "The versioned loops should be in simplify form.");133}134 135void LoopVersioning::addPHINodes(136 const SmallVectorImpl<Instruction *> &DefsUsedOutside) {137 BasicBlock *PHIBlock = VersionedLoop->getExitBlock();138 assert(PHIBlock && "No single successor to loop exit block");139 PHINode *PN;140 141 // First add a single-operand PHI for each DefsUsedOutside if one does not142 // exists yet.143 for (auto *Inst : DefsUsedOutside) {144 // See if we have a single-operand PHI with the value defined by the145 // original loop.146 for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {147 if (PN->getIncomingValue(0) == Inst) {148 SE->forgetLcssaPhiWithNewPredecessor(VersionedLoop, PN);149 break;150 }151 }152 // If not create it.153 if (!PN) {154 PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver");155 PN->insertBefore(PHIBlock->begin());156 SmallVector<User*, 8> UsersToUpdate;157 for (User *U : Inst->users())158 if (!VersionedLoop->contains(cast<Instruction>(U)->getParent()))159 UsersToUpdate.push_back(U);160 for (User *U : UsersToUpdate)161 U->replaceUsesOfWith(Inst, PN);162 PN->addIncoming(Inst, VersionedLoop->getExitingBlock());163 }164 }165 166 // Then for each PHI add the operand for the edge from the cloned loop.167 for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {168 assert(PN->getNumOperands() == 1 &&169 "Exit block should only have on predecessor");170 171 // If the definition was cloned used that otherwise use the same value.172 Value *ClonedValue = PN->getIncomingValue(0);173 auto Mapped = VMap.find(ClonedValue);174 if (Mapped != VMap.end())175 ClonedValue = Mapped->second;176 177 PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());178 }179}180 181void LoopVersioning::prepareNoAliasMetadata() {182 // We need to turn the no-alias relation between pointer checking groups into183 // no-aliasing annotations between instructions.184 //185 // We accomplish this by mapping each pointer checking group (a set of186 // pointers memchecked together) to an alias scope and then also mapping each187 // group to the list of scopes it can't alias.188 189 const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();190 LLVMContext &Context = VersionedLoop->getHeader()->getContext();191 192 // First allocate an aliasing scope for each pointer checking group.193 //194 // While traversing through the checking groups in the loop, also create a195 // reverse map from pointers to the pointer checking group they were assigned196 // to.197 MDBuilder MDB(Context);198 MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");199 200 for (const auto &Group : RtPtrChecking->CheckingGroups) {201 GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);202 203 for (unsigned PtrIdx : Group.Members)204 PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;205 }206 207 // Go through the checks and for each pointer group, collect the scopes for208 // each non-aliasing pointer group.209 DenseMap<const RuntimeCheckingPtrGroup *, SmallVector<Metadata *, 4>>210 GroupToNonAliasingScopes;211 212 for (const auto &Check : AliasChecks)213 GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);214 215 // Finally, transform the above to actually map to scope list which is what216 // the metadata uses.217 218 for (const auto &Pair : GroupToNonAliasingScopes)219 GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);220}221 222void LoopVersioning::annotateLoopWithNoAlias() {223 if (!AnnotateNoAlias)224 return;225 226 // First prepare the maps.227 prepareNoAliasMetadata();228 229 // Add the scope and no-alias metadata to the instructions.230 for (Instruction *I : LAI.getDepChecker().getMemoryInstructions()) {231 annotateInstWithNoAlias(I);232 }233}234 235std::pair<MDNode *, MDNode *>236LoopVersioning::getNoAliasMetadataFor(const Instruction *OrigInst) const {237 if (!AnnotateNoAlias)238 return {nullptr, nullptr};239 240 LLVMContext &Context = VersionedLoop->getHeader()->getContext();241 const Value *Ptr = isa<LoadInst>(OrigInst)242 ? cast<LoadInst>(OrigInst)->getPointerOperand()243 : cast<StoreInst>(OrigInst)->getPointerOperand();244 245 MDNode *AliasScope = nullptr;246 MDNode *NoAlias = nullptr;247 // Find the group for the pointer and then add the scope metadata.248 auto Group = PtrToGroup.find(Ptr);249 if (Group != PtrToGroup.end()) {250 AliasScope = MDNode::concatenate(251 OrigInst->getMetadata(LLVMContext::MD_alias_scope),252 MDNode::get(Context, GroupToScope.lookup(Group->second)));253 254 // Add the no-alias metadata.255 auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);256 if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())257 NoAlias =258 MDNode::concatenate(OrigInst->getMetadata(LLVMContext::MD_noalias),259 NonAliasingScopeList->second);260 }261 return {AliasScope, NoAlias};262}263 264void LoopVersioning::annotateInstWithNoAlias(Instruction *VersionedInst,265 const Instruction *OrigInst) {266 const auto &[AliasScopeMD, NoAliasMD] = getNoAliasMetadataFor(OrigInst);267 if (AliasScopeMD)268 VersionedInst->setMetadata(LLVMContext::MD_alias_scope, AliasScopeMD);269 270 if (NoAliasMD)271 VersionedInst->setMetadata(LLVMContext::MD_noalias, NoAliasMD);272}273 274namespace {275bool runImpl(LoopInfo *LI, LoopAccessInfoManager &LAIs, DominatorTree *DT,276 ScalarEvolution *SE) {277 // Build up a worklist of inner-loops to version. This is necessary as the278 // act of versioning a loop creates new loops and can invalidate iterators279 // across the loops.280 SmallVector<Loop *, 8> Worklist;281 282 for (Loop *TopLevelLoop : *LI)283 for (Loop *L : depth_first(TopLevelLoop))284 // We only handle inner-most loops.285 if (L->isInnermost())286 Worklist.push_back(L);287 288 // Now walk the identified inner loops.289 bool Changed = false;290 for (Loop *L : Worklist) {291 if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||292 !L->getExitingBlock())293 continue;294 const LoopAccessInfo &LAI = LAIs.getInfo(*L);295 if (!LAI.hasConvergentOp() &&296 (LAI.getNumRuntimePointerChecks() ||297 !LAI.getPSE().getPredicate().isAlwaysTrue())) {298 if (!L->isLCSSAForm(*DT))299 formLCSSARecursively(*L, *DT, LI, SE);300 301 LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L,302 LI, DT, SE);303 LVer.versionLoop();304 LVer.annotateLoopWithNoAlias();305 Changed = true;306 LAIs.clear();307 }308 }309 310 return Changed;311}312}313 314PreservedAnalyses LoopVersioningPass::run(Function &F,315 FunctionAnalysisManager &AM) {316 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);317 auto &LI = AM.getResult<LoopAnalysis>(F);318 LoopAccessInfoManager &LAIs = AM.getResult<LoopAccessAnalysis>(F);319 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);320 321 if (runImpl(&LI, LAIs, &DT, &SE))322 return PreservedAnalyses::none();323 return PreservedAnalyses::all();324}325