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