LLVM  16.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"
20 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/MDBuilder.h"
25 #include "llvm/IR/PassManager.h"
26 #include "llvm/InitializePasses.h"
31 
32 using namespace llvm;
33 
34 static cl::opt<bool>
35  AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
36  cl::Hidden,
37  cl::desc("Add no-alias annotation for instructions that "
38  "are disambiguated by memchecks"));
39 
42  LoopInfo *LI, DominatorTree *DT,
43  ScalarEvolution *SE)
44  : VersionedLoop(L), AliasChecks(Checks.begin(), Checks.end()),
45  Preds(LAI.getPSE().getPredicate()), LAI(LAI), LI(LI), DT(DT),
46  SE(SE) {
47 }
48 
50  const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
51  assert(VersionedLoop->getUniqueExitBlock() && "No single exit block");
52  assert(VersionedLoop->isLoopSimplifyForm() &&
53  "Loop is not in loop-simplify form");
54 
55  Value *MemRuntimeCheck;
56  Value *SCEVRuntimeCheck;
57  Value *RuntimeCheck = nullptr;
58 
59  // Add the memcheck in the original preheader (this is empty initially).
60  BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
61  const auto &RtPtrChecking = *LAI.getRuntimePointerChecking();
62 
63  SCEVExpander Exp2(*RtPtrChecking.getSE(),
64  VersionedLoop->getHeader()->getModule()->getDataLayout(),
65  "induction");
66  MemRuntimeCheck = addRuntimeChecks(RuntimeCheckBB->getTerminator(),
67  VersionedLoop, AliasChecks, Exp2);
68 
69  SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
70  "scev.check");
71  SCEVRuntimeCheck =
72  Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator());
73 
75  RuntimeCheckBB->getContext(),
76  InstSimplifyFolder(RuntimeCheckBB->getModule()->getDataLayout()));
77  if (MemRuntimeCheck && SCEVRuntimeCheck) {
78  Builder.SetInsertPoint(RuntimeCheckBB->getTerminator());
79  RuntimeCheck =
80  Builder.CreateOr(MemRuntimeCheck, SCEVRuntimeCheck, "lver.safe");
81  } else
82  RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
83 
84  assert(RuntimeCheck && "called even though we don't need "
85  "any runtime checks");
86 
87  // Rename the block to make the IR more readable.
88  RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
89  ".lver.check");
90 
91  // Create empty preheader for the loop (and after cloning for the
92  // non-versioned loop).
93  BasicBlock *PH =
94  SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI,
95  nullptr, VersionedLoop->getHeader()->getName() + ".ph");
96 
97  // Clone the loop including the preheader.
98  //
99  // FIXME: This does not currently preserve SimplifyLoop because the exit
100  // block is a join between the two loops.
101  SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
102  NonVersionedLoop =
103  cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
104  ".lver.orig", LI, DT, NonVersionedLoopBlocks);
105  remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
106 
107  // Insert the conditional branch based on the result of the memchecks.
108  Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
109  Builder.SetInsertPoint(OrigTerm);
110  Builder.CreateCondBr(RuntimeCheck, NonVersionedLoop->getLoopPreheader(),
111  VersionedLoop->getLoopPreheader());
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  formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true);
122  formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true);
123  assert(NonVersionedLoop->isLoopSimplifyForm() &&
124  VersionedLoop->isLoopSimplifyForm() &&
125  "The versioned loops should be in simplify form.");
126 }
127 
128 void LoopVersioning::addPHINodes(
129  const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
130  BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
131  assert(PHIBlock && "No single successor to loop exit block");
132  PHINode *PN;
133 
134  // First add a single-operand PHI for each DefsUsedOutside if one does not
135  // exists yet.
136  for (auto *Inst : DefsUsedOutside) {
137  // See if we have a single-operand PHI with the value defined by the
138  // original loop.
139  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
140  if (PN->getIncomingValue(0) == Inst) {
141  SE->forgetValue(PN);
142  break;
143  }
144  }
145  // If not create it.
146  if (!PN) {
147  PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
148  &PHIBlock->front());
149  SmallVector<User*, 8> UsersToUpdate;
150  for (User *U : Inst->users())
151  if (!VersionedLoop->contains(cast<Instruction>(U)->getParent()))
152  UsersToUpdate.push_back(U);
153  for (User *U : UsersToUpdate)
154  U->replaceUsesOfWith(Inst, PN);
155  PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
156  }
157  }
158 
159  // Then for each PHI add the operand for the edge from the cloned loop.
160  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
161  assert(PN->getNumOperands() == 1 &&
162  "Exit block should only have on predecessor");
163 
164  // If the definition was cloned used that otherwise use the same value.
165  Value *ClonedValue = PN->getIncomingValue(0);
166  auto Mapped = VMap.find(ClonedValue);
167  if (Mapped != VMap.end())
168  ClonedValue = Mapped->second;
169 
170  PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
171  }
172 }
173 
175  // We need to turn the no-alias relation between pointer checking groups into
176  // no-aliasing annotations between instructions.
177  //
178  // We accomplish this by mapping each pointer checking group (a set of
179  // pointers memchecked together) to an alias scope and then also mapping each
180  // group to the list of scopes it can't alias.
181 
182  const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
183  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
184 
185  // First allocate an aliasing scope for each pointer checking group.
186  //
187  // While traversing through the checking groups in the loop, also create a
188  // reverse map from pointers to the pointer checking group they were assigned
189  // to.
190  MDBuilder MDB(Context);
191  MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
192 
193  for (const auto &Group : RtPtrChecking->CheckingGroups) {
194  GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
195 
196  for (unsigned PtrIdx : Group.Members)
197  PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
198  }
199 
200  // Go through the checks and for each pointer group, collect the scopes for
201  // each non-aliasing pointer group.
203  GroupToNonAliasingScopes;
204 
205  for (const auto &Check : AliasChecks)
206  GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
207 
208  // Finally, transform the above to actually map to scope list which is what
209  // the metadata uses.
210 
211  for (auto Pair : GroupToNonAliasingScopes)
212  GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
213 }
214 
216  if (!AnnotateNoAlias)
217  return;
218 
219  // First prepare the maps.
221 
222  // Add the scope and no-alias metadata to the instructions.
225  }
226 }
227 
229  const Instruction *OrigInst) {
230  if (!AnnotateNoAlias)
231  return;
232 
233  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
234  const Value *Ptr = isa<LoadInst>(OrigInst)
235  ? cast<LoadInst>(OrigInst)->getPointerOperand()
236  : cast<StoreInst>(OrigInst)->getPointerOperand();
237 
238  // Find the group for the pointer and then add the scope metadata.
239  auto Group = PtrToGroup.find(Ptr);
240  if (Group != PtrToGroup.end()) {
241  VersionedInst->setMetadata(
242  LLVMContext::MD_alias_scope,
244  VersionedInst->getMetadata(LLVMContext::MD_alias_scope),
245  MDNode::get(Context, GroupToScope[Group->second])));
246 
247  // Add the no-alias metadata.
248  auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
249  if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
250  VersionedInst->setMetadata(
251  LLVMContext::MD_noalias,
253  VersionedInst->getMetadata(LLVMContext::MD_noalias),
254  NonAliasingScopeList->second));
255  }
256 }
257 
258 namespace {
260  ScalarEvolution *SE) {
261  // Build up a worklist of inner-loops to version. This is necessary as the
262  // act of versioning a loop creates new loops and can invalidate iterators
263  // across the loops.
264  SmallVector<Loop *, 8> Worklist;
265 
266  for (Loop *TopLevelLoop : *LI)
267  for (Loop *L : depth_first(TopLevelLoop))
268  // We only handle inner-most loops.
269  if (L->isInnermost())
270  Worklist.push_back(L);
271 
272  // Now walk the identified inner loops.
273  bool Changed = false;
274  for (Loop *L : Worklist) {
275  if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||
276  !L->getExitingBlock())
277  continue;
278  const LoopAccessInfo &LAI = LAIs.getInfo(*L);
279  if (!LAI.hasConvergentOp() &&
281  !LAI.getPSE().getPredicate().isAlwaysTrue())) {
282  LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L,
283  LI, DT, SE);
284  LVer.versionLoop();
285  LVer.annotateLoopWithNoAlias();
286  Changed = true;
287  LAIs.clear();
288  }
289  }
290 
291  return Changed;
292 }
293 
294 /// Also expose this is a pass. Currently this is only used for
295 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing
296 /// array accesses from the loop.
297 class LoopVersioningLegacyPass : public FunctionPass {
298 public:
299  LoopVersioningLegacyPass() : FunctionPass(ID) {
301  }
302 
303  bool runOnFunction(Function &F) override {
304  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
305  auto &LAIs = getAnalysis<LoopAccessLegacyAnalysis>().getLAIs();
306  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
307  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
308 
309  return runImpl(LI, LAIs, DT, SE);
310  }
311 
312  void getAnalysisUsage(AnalysisUsage &AU) const override {
319  }
320 
321  static char ID;
322 };
323 }
324 
325 #define LVER_OPTION "loop-versioning"
326 #define DEBUG_TYPE LVER_OPTION
327 
329 static const char LVer_name[] = "Loop Versioning";
330 
331 INITIALIZE_PASS_BEGIN(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
332  false)
337 INITIALIZE_PASS_END(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
338  false)
339 
340 namespace llvm {
342  return new LoopVersioningLegacyPass();
343 }
344 
347  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
348  auto &LI = AM.getResult<LoopAnalysis>(F);
350  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
351 
352  if (runImpl(&LI, LAIs, &DT, &SE))
353  return PreservedAnalyses::none();
354  return PreservedAnalyses::all();
355 }
356 } // namespace llvm
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2158
llvm::LoopAccessLegacyAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:796
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:158
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:107
llvm::PredicatedScalarEvolution::getPredicate
const SCEVPredicate & getPredicate() const
Definition: ScalarEvolution.cpp:14603
llvm::LoopAccessInfoManager
Definition: LoopAccessAnalysis.h:768
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::cloneLoopWithPreheader
Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock * > &Blocks)
Clones a loop OrigLoop.
Definition: CloneFunction.cpp:940
ScalarEvolutionExpander.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
llvm::ValueMap::end
iterator end()
Definition: ValueMap.h:136
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:50
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
LoopAccessAnalysis.h
llvm::IRBuilder
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2525
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::LoopAccessAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:828
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
ScalarEvolution.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
llvm::MDBuilder::createAnonymousAliasScope
MDNode * createAnonymousAliasScope(MDNode *Domain, StringRef Name=StringRef())
Return metadata appropriate for an alias scope root node.
Definition: MDBuilder.h:159
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1400
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1456
llvm::LoopVersioning::annotateInstWithNoAlias
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
Definition: LoopVersioning.cpp:228
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
CommandLine.h
LVER_OPTION
#define LVER_OPTION
Definition: LoopVersioning.cpp:325
LVer_name
static const char LVer_name[]
Definition: LoopVersioning.cpp:329
llvm::LoopVersioning::prepareNoAliasMetadata
void prepareNoAliasMetadata()
Set up the aliasing scopes based on the memchecks.
Definition: LoopVersioning.cpp:174
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2795
llvm::User
Definition: User.h:44
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
llvm::remapInstructionsInBlocks
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
Definition: CloneFunction.cpp:926
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
Domain
Domain
Definition: CorrelatedValuePropagation.cpp:709
Check
#define Check(C,...)
Definition: Lint.cpp:170
TargetLibraryInfo.h
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
MDBuilder.h
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2188
llvm::BasicBlock::getModule
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:147
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
llvm::addRuntimeChecks
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:1614
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::LoopAccessInfo::hasConvergentOp
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Definition: LoopAccessAnalysis.h:574
llvm::MDBuilder::createAnonymousAliasScopeDomain
MDNode * createAnonymousAliasScopeDomain(StringRef Name=StringRef())
Return metadata appropriate for an alias scope domain node.
Definition: MDBuilder.h:152
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:271
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::LoopAccessInfoManager::clear
void clear()
Definition: LoopAccessAnalysis.h:786
LoopInfo.h
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:479
llvm::cl::opt< bool >
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::RuntimePointerChecking
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
Definition: LoopAccessAnalysis.h:385
InstSimplifyFolder.h
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LoopVersioning
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
Definition: LoopVersioning.h:41
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2849
llvm::RuntimePointerChecking::getChecks
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
Definition: LoopAccessAnalysis.h:447
llvm::RuntimePointerChecking::CheckingGroups
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
Definition: LoopAccessAnalysis.h:486
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::DenseMap
Definition: DenseMap.h:714
llvm::LoopAccessInfo::getRuntimePointerChecking
const RuntimePointerChecking * getRuntimePointerChecking() const
Definition: LoopAccessAnalysis.h:576
I
#define I(x, y, z)
Definition: MD5.cpp:58
Cloning.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:562
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
ArrayRef.h
llvm::ScalarEvolution::forgetValue
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...
Definition: ScalarEvolution.cpp:8432
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MemoryDepChecker::getMemoryInstructions
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
Definition: LoopAccessAnalysis.h:229
llvm::SCEVPredicate::isAlwaysTrue
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::LoopAccessInfo::getDepChecker
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
Definition: LoopAccessAnalysis.h:604
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::InstSimplifyFolder
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
Definition: InstSimplifyFolder.h:34
llvm::MDNode::concatenate
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
Definition: Metadata.cpp:1006
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
AnnotateNoAlias
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"))
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:318
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false, false) INITIALIZE_PASS_END(LoopVersioningLegacyPass
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::LoopVersioningPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopVersioning.cpp:345
llvm::formDedicatedExitBlocks
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:58
llvm::PPC::getPredicate
Predicate getPredicate(unsigned Condition, unsigned Hint)
Return predicate consisting of specified condition and hint bits.
Definition: PPCPredicates.h:87
llvm::RuntimePointerChecking::PointerInfo::PointerValue
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.
Definition: LoopAccessAnalysis.h:391
llvm::LoopVersioning::LoopVersioning
LoopVersioning(const LoopAccessInfo &LAI, ArrayRef< RuntimePointerCheck > Checks, Loop *L, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
Definition: LoopVersioning.cpp:40
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::PHINode::Create
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...
Definition: Instructions.h:2741
llvm::LoopVersioning::versionLoop
void versionLoop()
Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...
Definition: LoopVersioning.h:64
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
PassManager.h
llvm::ValueMap::find
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
llvm::LoopAccessInfo::getNumRuntimePointerChecks
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
Definition: LoopAccessAnalysis.h:582
runImpl
static bool runImpl(Function &F, const TargetLowering &TLI)
Definition: ExpandLargeDivRem.cpp:56
LoopVersioning.h
llvm::MDBuilder
Definition: MDBuilder.h:36
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::createLoopVersioningLegacyPass
FunctionPass * createLoopVersioningLegacyPass()
Definition: LoopVersioning.cpp:341
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
Dominators.h
llvm::PHINode
Definition: Instructions.h:2699
llvm::BasicBlock::getTerminator
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:119
llvm::RuntimePointerChecking::getPointerInfo
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
Definition: LoopAccessAnalysis.h:501
llvm::SmallVectorImpl< Instruction * >
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:399
llvm::initializeLoopVersioningLegacyPassPass
void initializeLoopVersioningLegacyPassPass(PassRegistry &)
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::LoopVersioning::annotateLoopWithNoAlias
void annotateLoopWithNoAlias()
Annotate memory instructions in the versioned loop with no-alias metadata based on the memchecks issu...
Definition: LoopVersioning.cpp:215
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::cl::desc
Definition: CommandLine.h:413
llvm::LoopAccessInfo::getPSE
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
Definition: LoopAccessAnalysis.h:639
BasicBlockUtils.h
llvm::LoopAccessInfoManager::getInfo
const LoopAccessInfo & getInfo(Loop &L)
Definition: LoopAccessAnalysis.cpp:2672
llvm::SplitBlock
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.
Definition: BasicBlockUtils.cpp:918
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268