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