LLVM  9.0.0svn
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 
17 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/MDBuilder.h"
23 
24 using namespace llvm;
25 
26 static cl::opt<bool>
27  AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
28  cl::Hidden,
29  cl::desc("Add no-alias annotation for instructions that "
30  "are disambiguated by memchecks"));
31 
34  bool UseLAIChecks)
35  : VersionedLoop(L), NonVersionedLoop(nullptr), LAI(LAI), LI(LI), DT(DT),
36  SE(SE) {
37  assert(L->getExitBlock() && "No single exit block");
38  assert(L->isLoopSimplifyForm() && "Loop is not in loop-simplify form");
39  if (UseLAIChecks) {
42  }
43 }
44 
47  AliasChecks = std::move(Checks);
48 }
49 
51  Preds = std::move(Check);
52 }
53 
55  const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
56  Instruction *FirstCheckInst;
57  Instruction *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  std::tie(FirstCheckInst, MemRuntimeCheck) =
64  LAI.addRuntimeChecks(RuntimeCheckBB->getTerminator(), AliasChecks);
65 
66  const SCEVUnionPredicate &Pred = LAI.getPSE().getUnionPredicate();
67  SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
68  "scev.check");
69  SCEVRuntimeCheck =
70  Exp.expandCodeForPredicate(&Pred, RuntimeCheckBB->getTerminator());
71  auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck);
72 
73  // Discard the SCEV runtime check if it is always true.
74  if (CI && CI->isZero())
75  SCEVRuntimeCheck = nullptr;
76 
77  if (MemRuntimeCheck && SCEVRuntimeCheck) {
78  RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
79  SCEVRuntimeCheck, "lver.safe");
80  if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
81  I->insertBefore(RuntimeCheckBB->getTerminator());
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(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI);
96  PH->setName(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(PH, RuntimeCheckBB, VersionedLoop, VMap,
105  ".lver.orig", LI, DT, NonVersionedLoopBlocks);
106  remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
107 
108  // Insert the conditional branch based on the result of the memchecks.
109  Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
110  BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
111  VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
112  OrigTerm->eraseFromParent();
113 
114  // The loops merge in the original exit block. This is now dominated by the
115  // memchecking block.
116  DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
117 
118  // Adds the necessary PHI nodes for the versioned loops based on the
119  // loop-defined values used outside of the loop.
120  addPHINodes(DefsUsedOutside);
121 }
122 
123 void LoopVersioning::addPHINodes(
124  const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
125  BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
126  assert(PHIBlock && "No single successor to loop exit block");
127  PHINode *PN;
128 
129  // First add a single-operand PHI for each DefsUsedOutside if one does not
130  // exists yet.
131  for (auto *Inst : DefsUsedOutside) {
132  // See if we have a single-operand PHI with the value defined by the
133  // original loop.
134  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
135  if (PN->getIncomingValue(0) == Inst)
136  break;
137  }
138  // If not create it.
139  if (!PN) {
140  PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
141  &PHIBlock->front());
142  SmallVector<User*, 8> UsersToUpdate;
143  for (User *U : Inst->users())
144  if (!VersionedLoop->contains(cast<Instruction>(U)->getParent()))
145  UsersToUpdate.push_back(U);
146  for (User *U : UsersToUpdate)
147  U->replaceUsesOfWith(Inst, PN);
148  PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
149  }
150  }
151 
152  // Then for each PHI add the operand for the edge from the cloned loop.
153  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
154  assert(PN->getNumOperands() == 1 &&
155  "Exit block should only have on predecessor");
156 
157  // If the definition was cloned used that otherwise use the same value.
158  Value *ClonedValue = PN->getIncomingValue(0);
159  auto Mapped = VMap.find(ClonedValue);
160  if (Mapped != VMap.end())
161  ClonedValue = Mapped->second;
162 
163  PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
164  }
165 }
166 
168  // We need to turn the no-alias relation between pointer checking groups into
169  // no-aliasing annotations between instructions.
170  //
171  // We accomplish this by mapping each pointer checking group (a set of
172  // pointers memchecked together) to an alias scope and then also mapping each
173  // group to the list of scopes it can't alias.
174 
175  const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
176  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
177 
178  // First allocate an aliasing scope for each pointer checking group.
179  //
180  // While traversing through the checking groups in the loop, also create a
181  // reverse map from pointers to the pointer checking group they were assigned
182  // to.
183  MDBuilder MDB(Context);
184  MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
185 
186  for (const auto &Group : RtPtrChecking->CheckingGroups) {
187  GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
188 
189  for (unsigned PtrIdx : Group.Members)
190  PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
191  }
192 
193  // Go through the checks and for each pointer group, collect the scopes for
194  // each non-aliasing pointer group.
197  GroupToNonAliasingScopes;
198 
199  for (const auto &Check : AliasChecks)
200  GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
201 
202  // Finally, transform the above to actually map to scope list which is what
203  // the metadata uses.
204 
205  for (auto Pair : GroupToNonAliasingScopes)
206  GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
207 }
208 
210  if (!AnnotateNoAlias)
211  return;
212 
213  // First prepare the maps.
215 
216  // Add the scope and no-alias metadata to the instructions.
219  }
220 }
221 
223  const Instruction *OrigInst) {
224  if (!AnnotateNoAlias)
225  return;
226 
227  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
228  const Value *Ptr = isa<LoadInst>(OrigInst)
229  ? cast<LoadInst>(OrigInst)->getPointerOperand()
230  : cast<StoreInst>(OrigInst)->getPointerOperand();
231 
232  // Find the group for the pointer and then add the scope metadata.
233  auto Group = PtrToGroup.find(Ptr);
234  if (Group != PtrToGroup.end()) {
235  VersionedInst->setMetadata(
239  MDNode::get(Context, GroupToScope[Group->second])));
240 
241  // Add the no-alias metadata.
242  auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
243  if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
244  VersionedInst->setMetadata(
247  VersionedInst->getMetadata(LLVMContext::MD_noalias),
248  NonAliasingScopeList->second));
249  }
250 }
251 
252 namespace {
253 /// Also expose this is a pass. Currently this is only used for
254 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing
255 /// array accesses from the loop.
256 class LoopVersioningPass : public FunctionPass {
257 public:
258  LoopVersioningPass() : FunctionPass(ID) {
260  }
261 
262  bool runOnFunction(Function &F) override {
263  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
264  auto *LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
265  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
266  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
267 
268  // Build up a worklist of inner-loops to version. This is necessary as the
269  // act of versioning a loop creates new loops and can invalidate iterators
270  // across the loops.
271  SmallVector<Loop *, 8> Worklist;
272 
273  for (Loop *TopLevelLoop : *LI)
274  for (Loop *L : depth_first(TopLevelLoop))
275  // We only handle inner-most loops.
276  if (L->empty())
277  Worklist.push_back(L);
278 
279  // Now walk the identified inner loops.
280  bool Changed = false;
281  for (Loop *L : Worklist) {
282  const LoopAccessInfo &LAI = LAA->getInfo(L);
283  if (L->isLoopSimplifyForm() && (LAI.getNumRuntimePointerChecks() ||
284  !LAI.getPSE().getUnionPredicate().isAlwaysTrue())) {
285  LoopVersioning LVer(LAI, L, LI, DT, SE);
286  LVer.versionLoop();
288  Changed = true;
289  }
290  }
291 
292  return Changed;
293  }
294 
295  void getAnalysisUsage(AnalysisUsage &AU) const override {
302  }
303 
304  static char ID;
305 };
306 }
307 
308 #define LVER_OPTION "loop-versioning"
309 #define DEBUG_TYPE LVER_OPTION
310 
312 static const char LVer_name[] = "Loop Versioning";
313 
314 INITIALIZE_PASS_BEGIN(LoopVersioningPass, LVER_OPTION, LVer_name, false, false)
319 INITIALIZE_PASS_END(LoopVersioningPass, LVER_OPTION, LVer_name, false, false)
320 
321 namespace llvm {
323  return new LoopVersioningPass();
324 }
325 }
static bool Check(DecodeStatus &Out, DecodeStatus In)
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
SmallVector< CheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Value * getPointerOperand(Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
LLVMContext & Context
This class represents lattice values for constants.
Definition: AllocatorList.h:23
MDNode * createAnonymousAliasScope(MDNode *Domain, StringRef Name=StringRef())
Return metadata appropriate for an alias scope root node.
Definition: MDBuilder.h:136
void push_back(const T &Elt)
Definition: SmallVector.h:211
const RuntimePointerChecking * getRuntimePointerChecking() const
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
#define LVER_OPTION
Metadata node.
Definition: Metadata.h:863
F(f)
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.cpp:137
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
AnalysisUsage & addRequired()
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:133
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:285
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"))
BlockT * getHeader() const
Definition: LoopInfo.h:99
static const char LVer_name[]
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
iterator find(const KeyT &Val)
Definition: ValueMap.h:161
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:234
void versionLoop()
Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
std::pair< Instruction *, Instruction * > addRuntimeChecks(Instruction *Loc) const
Add code that checks at runtime if the accessed arrays overlap.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
This analysis provides dependence information for the memory accesses of a loop.
const Instruction & front() const
Definition: BasicBlock.h:280
Represent the analysis usage information of a pass.
void annotateLoopWithNoAlias()
Annotate memory instructions in the versioned loop with no-alias metadata based on the memchecks issu...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:75
void setAliasChecks(SmallVector< RuntimePointerChecking::PointerCheck, 4 > Checks)
Sets the runtime alias checks for versioning the loop.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
void setSCEVChecks(SCEVUnionPredicate Check)
Sets the runtime SCEV checks for versioning the loop.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1225
MDNode * createAnonymousAliasScopeDomain(StringRef Name=StringRef())
Return metadata appropriate for an alias scope domain node.
Definition: MDBuilder.h:129
iterator end()
Definition: ValueMap.h:141
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:109
unsigned getNumOperands() const
Definition: User.h:191
FunctionPass * createLoopVersioningPass()
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
const SCEVUnionPredicate & getUnionPredicate() const
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:47
Drive the analysis of memory accesses in the loop.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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...
This class emits a version of the loop where run-time checks ensure that may-alias pointers can&#39;t ove...
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
iterator_range< user_iterator > users()
Definition: Value.h:399
This class uses information about analyze scalars to rewrite expressions in canonical form...
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:192
void initializeLoopVersioningPassPass(PassRegistry &)
void prepareNoAliasMetadata()
Set up the aliasing scopes based on the memchecks.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
Definition: Metadata.cpp:895
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:322
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class represents a composition of other SCEV predicates, and is the class that most clients will...
LLVM Value Representation.
Definition: Value.h:72
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock *> &Blocks)
Clones a loop OrigLoop.
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:969
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
const SmallVector< PointerCheck, 4 > & getChecks() const
Returns the checks that generateChecks created.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE, bool UseLAIChecks=true)
Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock *> &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.