LLVM 17.0.0git
LoopVersioning.cpp
Go to the documentation of this file.
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
16#include "llvm/ADT/ArrayRef.h"
23#include "llvm/IR/Dominators.h"
24#include "llvm/IR/MDBuilder.h"
25#include "llvm/IR/PassManager.h"
31
32using namespace llvm;
33
34#define DEBUG_TYPE "loop-versioning"
35
36static cl::opt<bool>
37 AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
39 cl::desc("Add no-alias annotation for instructions that "
40 "are disambiguated by memchecks"));
41
44 LoopInfo *LI, DominatorTree *DT,
46 : VersionedLoop(L), AliasChecks(Checks.begin(), Checks.end()),
47 Preds(LAI.getPSE().getPredicate()), LAI(LAI), LI(LI), DT(DT),
48 SE(SE) {
49}
50
52 const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
53 assert(VersionedLoop->getUniqueExitBlock() && "No single exit block");
54 assert(VersionedLoop->isLoopSimplifyForm() &&
55 "Loop is not in loop-simplify form");
56
57 Value *MemRuntimeCheck;
58 Value *SCEVRuntimeCheck;
59 Value *RuntimeCheck = nullptr;
60
61 // Add the memcheck in the original preheader (this is empty initially).
62 BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
63 const auto &RtPtrChecking = *LAI.getRuntimePointerChecking();
64
65 SCEVExpander Exp2(*RtPtrChecking.getSE(),
66 VersionedLoop->getHeader()->getModule()->getDataLayout(),
67 "induction");
68 MemRuntimeCheck = addRuntimeChecks(RuntimeCheckBB->getTerminator(),
69 VersionedLoop, AliasChecks, Exp2);
70
71 SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
72 "scev.check");
73 SCEVRuntimeCheck =
74 Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator());
75
77 RuntimeCheckBB->getContext(),
78 InstSimplifyFolder(RuntimeCheckBB->getModule()->getDataLayout()));
79 if (MemRuntimeCheck && SCEVRuntimeCheck) {
80 Builder.SetInsertPoint(RuntimeCheckBB->getTerminator());
81 RuntimeCheck =
82 Builder.CreateOr(MemRuntimeCheck, SCEVRuntimeCheck, "lver.safe");
83 } else
84 RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
85
86 assert(RuntimeCheck && "called even though we don't need "
87 "any runtime checks");
88
89 // Rename the block to make the IR more readable.
90 RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
91 ".lver.check");
92
93 // Create empty preheader for the loop (and after cloning for the
94 // non-versioned loop).
95 BasicBlock *PH =
96 SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI,
97 nullptr, VersionedLoop->getHeader()->getName() + ".ph");
98
99 // Clone the loop including the preheader.
100 //
101 // FIXME: This does not currently preserve SimplifyLoop because the exit
102 // block is a join between the two loops.
103 SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
104 NonVersionedLoop =
105 cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
106 ".lver.orig", LI, DT, NonVersionedLoopBlocks);
107 remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
108
109 // Insert the conditional branch based on the result of the memchecks.
110 Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
111 Builder.SetInsertPoint(OrigTerm);
112 Builder.CreateCondBr(RuntimeCheck, NonVersionedLoop->getLoopPreheader(),
113 VersionedLoop->getLoopPreheader());
114 OrigTerm->eraseFromParent();
115
116 // The loops merge in the original exit block. This is now dominated by the
117 // memchecking block.
118 DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
119
120 // Adds the necessary PHI nodes for the versioned loops based on the
121 // loop-defined values used outside of the loop.
122 addPHINodes(DefsUsedOutside);
123 formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true);
124 formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true);
125 assert(NonVersionedLoop->isLoopSimplifyForm() &&
126 VersionedLoop->isLoopSimplifyForm() &&
127 "The versioned loops should be in simplify form.");
128}
129
130void LoopVersioning::addPHINodes(
131 const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
132 BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
133 assert(PHIBlock && "No single successor to loop exit block");
134 PHINode *PN;
135
136 // First add a single-operand PHI for each DefsUsedOutside if one does not
137 // exists yet.
138 for (auto *Inst : DefsUsedOutside) {
139 // See if we have a single-operand PHI with the value defined by the
140 // original loop.
141 for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
142 if (PN->getIncomingValue(0) == Inst) {
143 SE->forgetValue(PN);
144 break;
145 }
146 }
147 // If not create it.
148 if (!PN) {
149 PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
150 &PHIBlock->front());
151 SmallVector<User*, 8> UsersToUpdate;
152 for (User *U : Inst->users())
153 if (!VersionedLoop->contains(cast<Instruction>(U)->getParent()))
154 UsersToUpdate.push_back(U);
155 for (User *U : UsersToUpdate)
156 U->replaceUsesOfWith(Inst, PN);
157 PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
158 }
159 }
160
161 // Then for each PHI add the operand for the edge from the cloned loop.
162 for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
163 assert(PN->getNumOperands() == 1 &&
164 "Exit block should only have on predecessor");
165
166 // If the definition was cloned used that otherwise use the same value.
167 Value *ClonedValue = PN->getIncomingValue(0);
168 auto Mapped = VMap.find(ClonedValue);
169 if (Mapped != VMap.end())
170 ClonedValue = Mapped->second;
171
172 PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
173 }
174}
175
177 // We need to turn the no-alias relation between pointer checking groups into
178 // no-aliasing annotations between instructions.
179 //
180 // We accomplish this by mapping each pointer checking group (a set of
181 // pointers memchecked together) to an alias scope and then also mapping each
182 // group to the list of scopes it can't alias.
183
184 const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
185 LLVMContext &Context = VersionedLoop->getHeader()->getContext();
186
187 // First allocate an aliasing scope for each pointer checking group.
188 //
189 // While traversing through the checking groups in the loop, also create a
190 // reverse map from pointers to the pointer checking group they were assigned
191 // to.
192 MDBuilder MDB(Context);
193 MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
194
195 for (const auto &Group : RtPtrChecking->CheckingGroups) {
196 GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
197
198 for (unsigned PtrIdx : Group.Members)
199 PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
200 }
201
202 // Go through the checks and for each pointer group, collect the scopes for
203 // each non-aliasing pointer group.
205 GroupToNonAliasingScopes;
206
207 for (const auto &Check : AliasChecks)
208 GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
209
210 // Finally, transform the above to actually map to scope list which is what
211 // the metadata uses.
212
213 for (auto Pair : GroupToNonAliasingScopes)
214 GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
215}
216
218 if (!AnnotateNoAlias)
219 return;
220
221 // First prepare the maps.
223
224 // Add the scope and no-alias metadata to the instructions.
227 }
228}
229
231 const Instruction *OrigInst) {
232 if (!AnnotateNoAlias)
233 return;
234
235 LLVMContext &Context = VersionedLoop->getHeader()->getContext();
236 const Value *Ptr = isa<LoadInst>(OrigInst)
237 ? cast<LoadInst>(OrigInst)->getPointerOperand()
238 : cast<StoreInst>(OrigInst)->getPointerOperand();
239
240 // Find the group for the pointer and then add the scope metadata.
241 auto Group = PtrToGroup.find(Ptr);
242 if (Group != PtrToGroup.end()) {
243 VersionedInst->setMetadata(
244 LLVMContext::MD_alias_scope,
246 VersionedInst->getMetadata(LLVMContext::MD_alias_scope),
247 MDNode::get(Context, GroupToScope[Group->second])));
248
249 // Add the no-alias metadata.
250 auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
251 if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
252 VersionedInst->setMetadata(
253 LLVMContext::MD_noalias,
255 VersionedInst->getMetadata(LLVMContext::MD_noalias),
256 NonAliasingScopeList->second));
257 }
258}
259
260namespace {
262 ScalarEvolution *SE) {
263 // Build up a worklist of inner-loops to version. This is necessary as the
264 // act of versioning a loop creates new loops and can invalidate iterators
265 // across the loops.
266 SmallVector<Loop *, 8> Worklist;
267
268 for (Loop *TopLevelLoop : *LI)
269 for (Loop *L : depth_first(TopLevelLoop))
270 // We only handle inner-most loops.
271 if (L->isInnermost())
272 Worklist.push_back(L);
273
274 // Now walk the identified inner loops.
275 bool Changed = false;
276 for (Loop *L : Worklist) {
277 if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||
278 !L->getExitingBlock())
279 continue;
280 const LoopAccessInfo &LAI = LAIs.getInfo(*L);
281 if (!LAI.hasConvergentOp() &&
283 !LAI.getPSE().getPredicate().isAlwaysTrue())) {
285 LI, DT, SE);
286 LVer.versionLoop();
287 LVer.annotateLoopWithNoAlias();
288 Changed = true;
289 LAIs.clear();
290 }
291 }
292
293 return Changed;
294}
295}
296
299 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
300 auto &LI = AM.getResult<LoopAnalysis>(F);
302 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
303
304 if (runImpl(&LI, LAIs, &DT, &SE))
306 return PreservedAnalyses::all();
307}
assume Assume Builder
static bool runImpl(Function &F, const TargetLowering &TLI)
#define Check(C,...)
Definition: Lint.cpp:170
static cl::opt< bool > AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true), cl::Hidden, cl::desc("Add no-alias annotation for instructions that " "are disambiguated by memchecks"))
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
LLVMContext & Context
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:323
const Instruction & front() const
Definition: BasicBlock.h:335
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:146
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2564
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:275
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1455
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
This analysis provides dependence information for the memory accesses of a loop.
const LoopAccessInfo & getInfo(Loop &L)
Drive the analysis of memory accesses in the loop.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
const RuntimePointerChecking * getRuntimePointerChecking() const
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
BlockT * getHeader() const
Definition: LoopInfo.h:105
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:107
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:158
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
void annotateLoopWithNoAlias()
Annotate memory instructions in the versioned loop with no-alias metadata based on the memchecks issu...
void prepareNoAliasMetadata()
Set up the aliasing scopes based on the memchecks.
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
void versionLoop()
Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...
LoopVersioning(const LoopAccessInfo &LAI, ArrayRef< RuntimePointerCheck > Checks, Loop *L, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:479
MDNode * createAnonymousAliasScope(MDNode *Domain, StringRef Name=StringRef())
Return metadata appropriate for an alias scope root node.
Definition: MDBuilder.h:159
MDNode * createAnonymousAliasScopeDomain(StringRef Name=StringRef())
Return metadata appropriate for an alias scope domain node.
Definition: MDBuilder.h:152
Metadata node.
Definition: Metadata.h:943
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
Definition: Metadata.cpp:1005
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1399
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
const SCEVPredicate & getPredicate() const
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
This class uses information about analyze scalars to rewrite expressions in canonical form.
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
unsigned getNumOperands() const
Definition: User.h:191
iterator find(const KeyT &Val)
Definition: ValueMap.h:155
iterator end()
Definition: ValueMap.h:135
LLVM Value Representation.
Definition: Value.h:74
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
iterator_range< user_iterator > users()
Definition: Value.h:421
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock * > &Blocks)
Clones a loop OrigLoop.
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
Definition: LoopUtils.cpp:1626
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:57
void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
iterator_range< df_iterator< T > > depth_first(const T &G)
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.