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
31using namespace llvm;
32
33#define DEBUG_TYPE "loop-versioning"
34
35static cl::opt<bool>
36 AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(Val: true),
37 cl::Hidden,
38 cl::desc("Add no-alias annotation for instructions that "
39 "are disambiguated by memchecks"));
40
41LoopVersioning::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
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(Loc: RuntimeCheckBB->getTerminator(),
68 TheLoop: VersionedLoop, PointerChecks: AliasChecks, Expander&: Exp2);
69
70 SCEVExpander Exp(*SE, RuntimeCheckBB->getDataLayout(),
71 "scev.check");
72 SCEVRuntimeCheck =
73 Exp.expandCodeForPredicate(Pred: &Preds, Loc: 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(LHS: MemRuntimeCheck, RHS: SCEVRuntimeCheck, Name: "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(Old: RuntimeCheckBB, SplitPt: RuntimeCheckBB->getTerminator(), DT, LI,
96 MSSAU: nullptr, BBName: 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(Before: PH, LoopDomBB: RuntimeCheckBB, OrigLoop: VersionedLoop, VMap,
105 NameSuffix: ".lver.orig", LI, DT, Blocks&: NonVersionedLoopBlocks);
106 remapInstructionsInBlocks(Blocks: 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(Cond: RuntimeCheck, True: NonVersionedLoop->getLoopPreheader(),
112 False: 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(BB: VersionedLoop->getExitBlock(), NewBB: 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(L: NonVersionedLoop, DT, LI, MSSAU: nullptr, PreserveLCSSA: true);
123 formDedicatedExitBlocks(L: VersionedLoop, DT, LI, MSSAU: nullptr, PreserveLCSSA: true);
124 assert(NonVersionedLoop->isLoopSimplifyForm() &&
125 VersionedLoop->isLoopSimplifyForm() &&
126 "The versioned loops should be in simplify form.");
127}
128
129void 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>(Val&: I)); ++I) {
141 if (PN->getIncomingValue(i: 0) == Inst) {
142 SE->forgetValue(V: PN);
143 break;
144 }
145 }
146 // If not create it.
147 if (!PN) {
148 PN = PHINode::Create(Ty: Inst->getType(), NumReservedValues: 2, NameStr: Inst->getName() + ".lver");
149 PN->insertBefore(InsertPos: PHIBlock->begin());
150 SmallVector<User*, 8> UsersToUpdate;
151 for (User *U : Inst->users())
152 if (!VersionedLoop->contains(BB: cast<Instruction>(Val: U)->getParent()))
153 UsersToUpdate.push_back(Elt: U);
154 for (User *U : UsersToUpdate)
155 U->replaceUsesOfWith(From: Inst, To: PN);
156 PN->addIncoming(V: Inst, BB: 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>(Val&: 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(i: 0);
167 auto Mapped = VMap.find(Val: ClonedValue);
168 if (Mapped != VMap.end())
169 ClonedValue = Mapped->second;
170
171 PN->addIncoming(V: ClonedValue, BB: NonVersionedLoop->getExitingBlock());
172 }
173}
174
175void 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(Name: "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(Elt: 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, MDs: Pair.second);
214}
215
216void 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
229void 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>(Val: OrigInst)
236 ? cast<LoadInst>(Val: OrigInst)->getPointerOperand()
237 : cast<StoreInst>(Val: OrigInst)->getPointerOperand();
238
239 // Find the group for the pointer and then add the scope metadata.
240 auto Group = PtrToGroup.find(Val: Ptr);
241 if (Group != PtrToGroup.end()) {
242 VersionedInst->setMetadata(
243 KindID: LLVMContext::MD_alias_scope,
244 Node: MDNode::concatenate(
245 A: VersionedInst->getMetadata(KindID: LLVMContext::MD_alias_scope),
246 B: MDNode::get(Context, MDs: GroupToScope[Group->second])));
247
248 // Add the no-alias metadata.
249 auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Val: Group->second);
250 if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
251 VersionedInst->setMetadata(
252 KindID: LLVMContext::MD_noalias,
253 Node: MDNode::concatenate(
254 A: VersionedInst->getMetadata(KindID: LLVMContext::MD_noalias),
255 B: NonAliasingScopeList->second));
256 }
257}
258
259namespace {
260bool 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(G: TopLevelLoop))
269 // We only handle inner-most loops.
270 if (L->isInnermost())
271 Worklist.push_back(Elt: 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&: *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
296PreservedAnalyses LoopVersioningPass::run(Function &F,
297 FunctionAnalysisManager &AM) {
298 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
299 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
300 LoopAccessInfoManager &LAIs = AM.getResult<LoopAccessAnalysis>(IR&: F);
301 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
302
303 if (runImpl(LI: &LI, LAIs, DT: &DT, SE: &SE))
304 return PreservedAnalyses::none();
305 return PreservedAnalyses::all();
306}
307