LLVM  6.0.0svn
LoopVersioning.cpp
Go to the documentation of this file.
1 //===- LoopVersioning.cpp - Utility to version a loop ---------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines a utility class to perform loop versioning. The versioned
11 // loop speculates that otherwise may-aliasing memory accesses don't overlap and
12 // emits checks to prove this.
13 //
14 //===----------------------------------------------------------------------===//
15 
18 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/IR/Dominators.h"
21 #include "llvm/IR/MDBuilder.h"
24 
25 using namespace llvm;
26 
27 static cl::opt<bool>
28  AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
29  cl::Hidden,
30  cl::desc("Add no-alias annotation for instructions that "
31  "are disambiguated by memchecks"));
32 
35  bool UseLAIChecks)
36  : VersionedLoop(L), NonVersionedLoop(nullptr), LAI(LAI), LI(LI), DT(DT),
37  SE(SE) {
38  assert(L->getExitBlock() && "No single exit block");
39  assert(L->isLoopSimplifyForm() && "Loop is not in loop-simplify form");
40  if (UseLAIChecks) {
43  }
44 }
45 
48  AliasChecks = std::move(Checks);
49 }
50 
52  Preds = std::move(Check);
53 }
54 
56  const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
57  Instruction *FirstCheckInst;
58  Instruction *MemRuntimeCheck;
59  Value *SCEVRuntimeCheck;
60  Value *RuntimeCheck = nullptr;
61 
62  // Add the memcheck in the original preheader (this is empty initially).
63  BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
64  std::tie(FirstCheckInst, MemRuntimeCheck) =
65  LAI.addRuntimeChecks(RuntimeCheckBB->getTerminator(), AliasChecks);
66 
67  const SCEVUnionPredicate &Pred = LAI.getPSE().getUnionPredicate();
68  SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
69  "scev.check");
70  SCEVRuntimeCheck =
71  Exp.expandCodeForPredicate(&Pred, RuntimeCheckBB->getTerminator());
72  auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck);
73 
74  // Discard the SCEV runtime check if it is always true.
75  if (CI && CI->isZero())
76  SCEVRuntimeCheck = nullptr;
77 
78  if (MemRuntimeCheck && SCEVRuntimeCheck) {
79  RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
80  SCEVRuntimeCheck, "lver.safe");
81  if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
82  I->insertBefore(RuntimeCheckBB->getTerminator());
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  PH->setName(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  BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
112  VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
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(VersionedLoop->getExitBlock(), 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 }
123 
124 void LoopVersioning::addPHINodes(
125  const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
126  BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
127  assert(PHIBlock && "No single successor to loop exit block");
128  PHINode *PN;
129 
130  // First add a single-operand PHI for each DefsUsedOutside if one does not
131  // exists yet.
132  for (auto *Inst : DefsUsedOutside) {
133  // See if we have a single-operand PHI with the value defined by the
134  // original loop.
135  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
136  if (PN->getIncomingValue(0) == Inst)
137  break;
138  }
139  // If not create it.
140  if (!PN) {
141  PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
142  &PHIBlock->front());
143  for (auto *User : Inst->users())
144  if (!VersionedLoop->contains(cast<Instruction>(User)->getParent()))
145  User->replaceUsesOfWith(Inst, PN);
146  PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
147  }
148  }
149 
150  // Then for each PHI add the operand for the edge from the cloned loop.
151  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
152  assert(PN->getNumOperands() == 1 &&
153  "Exit block should only have on predecessor");
154 
155  // If the definition was cloned used that otherwise use the same value.
156  Value *ClonedValue = PN->getIncomingValue(0);
157  auto Mapped = VMap.find(ClonedValue);
158  if (Mapped != VMap.end())
159  ClonedValue = Mapped->second;
160 
161  PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
162  }
163 }
164 
166  // We need to turn the no-alias relation between pointer checking groups into
167  // no-aliasing annotations between instructions.
168  //
169  // We accomplish this by mapping each pointer checking group (a set of
170  // pointers memchecked together) to an alias scope and then also mapping each
171  // group to the list of scopes it can't alias.
172 
173  const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
174  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
175 
176  // First allocate an aliasing scope for each pointer checking group.
177  //
178  // While traversing through the checking groups in the loop, also create a
179  // reverse map from pointers to the pointer checking group they were assigned
180  // to.
181  MDBuilder MDB(Context);
182  MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
183 
184  for (const auto &Group : RtPtrChecking->CheckingGroups) {
185  GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
186 
187  for (unsigned PtrIdx : Group.Members)
188  PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
189  }
190 
191  // Go through the checks and for each pointer group, collect the scopes for
192  // each non-aliasing pointer group.
195  GroupToNonAliasingScopes;
196 
197  for (const auto &Check : AliasChecks)
198  GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
199 
200  // Finally, transform the above to actually map to scope list which is what
201  // the metadata uses.
202 
203  for (auto Pair : GroupToNonAliasingScopes)
204  GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
205 }
206 
208  if (!AnnotateNoAlias)
209  return;
210 
211  // First prepare the maps.
213 
214  // Add the scope and no-alias metadata to the instructions.
217  }
218 }
219 
221  const Instruction *OrigInst) {
222  if (!AnnotateNoAlias)
223  return;
224 
225  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
226  const Value *Ptr = isa<LoadInst>(OrigInst)
227  ? cast<LoadInst>(OrigInst)->getPointerOperand()
228  : cast<StoreInst>(OrigInst)->getPointerOperand();
229 
230  // Find the group for the pointer and then add the scope metadata.
231  auto Group = PtrToGroup.find(Ptr);
232  if (Group != PtrToGroup.end()) {
233  VersionedInst->setMetadata(
237  MDNode::get(Context, GroupToScope[Group->second])));
238 
239  // Add the no-alias metadata.
240  auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
241  if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
242  VersionedInst->setMetadata(
245  VersionedInst->getMetadata(LLVMContext::MD_noalias),
246  NonAliasingScopeList->second));
247  }
248 }
249 
250 namespace {
251 /// \brief Also expose this is a pass. Currently this is only used for
252 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing
253 /// array accesses from the loop.
254 class LoopVersioningPass : public FunctionPass {
255 public:
256  LoopVersioningPass() : FunctionPass(ID) {
258  }
259 
260  bool runOnFunction(Function &F) override {
261  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
262  auto *LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
263  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
264  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
265 
266  // Build up a worklist of inner-loops to version. This is necessary as the
267  // act of versioning a loop creates new loops and can invalidate iterators
268  // across the loops.
269  SmallVector<Loop *, 8> Worklist;
270 
271  for (Loop *TopLevelLoop : *LI)
272  for (Loop *L : depth_first(TopLevelLoop))
273  // We only handle inner-most loops.
274  if (L->empty())
275  Worklist.push_back(L);
276 
277  // Now walk the identified inner loops.
278  bool Changed = false;
279  for (Loop *L : Worklist) {
280  const LoopAccessInfo &LAI = LAA->getInfo(L);
281  if (L->isLoopSimplifyForm() && (LAI.getNumRuntimePointerChecks() ||
282  !LAI.getPSE().getUnionPredicate().isAlwaysTrue())) {
283  LoopVersioning LVer(LAI, L, LI, DT, SE);
284  LVer.versionLoop();
286  Changed = true;
287  }
288  }
289 
290  return Changed;
291  }
292 
293  void getAnalysisUsage(AnalysisUsage &AU) const override {
300  }
301 
302  static char ID;
303 };
304 }
305 
306 #define LVER_OPTION "loop-versioning"
307 #define DEBUG_TYPE LVER_OPTION
308 
310 static const char LVer_name[] = "Loop Versioning";
311 
312 INITIALIZE_PASS_BEGIN(LoopVersioningPass, LVER_OPTION, LVer_name, false, false)
317 INITIALIZE_PASS_END(LoopVersioningPass, LVER_OPTION, LVer_name, false, false)
318 
319 namespace llvm {
321  return new LoopVersioningPass();
322 }
323 }
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:69
void push_back(const T &Elt)
Definition: SmallVector.h:212
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...
LLVMContext & Context
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
MDNode * createAnonymousAliasScope(MDNode *Domain, StringRef Name=StringRef())
Return metadata appropriate for an alias scope root node.
Definition: MDBuilder.h:124
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:106
#define LVER_OPTION
Metadata node.
Definition: Metadata.h:862
F(f)
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static Value * getPointerOperand(Instruction &Inst)
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
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:286
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:100
static const char LVer_name[]
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
iterator find(const KeyT &Val)
Definition: ValueMap.h:158
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:194
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:140
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:22
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:1164
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
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:264
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:285
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:76
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:1214
MDNode * createAnonymousAliasScopeDomain(StringRef Name=StringRef())
Return metadata appropriate for an alias scope domain node.
Definition: MDBuilder.h:117
iterator end()
Definition: ValueMap.h:138
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
unsigned getNumOperands() const
Definition: User.h:176
FunctionPass * createLoopVersioningPass()
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
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:48
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:401
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:191
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:439
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
Definition: Metadata.cpp:888
#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:323
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:73
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:958
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
const TerminatorInst * 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:120
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:50
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.