LLVM  15.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  break;
142  }
143  // If not create it.
144  if (!PN) {
145  PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
146  &PHIBlock->front());
147  SmallVector<User*, 8> UsersToUpdate;
148  for (User *U : Inst->users())
149  if (!VersionedLoop->contains(cast<Instruction>(U)->getParent()))
150  UsersToUpdate.push_back(U);
151  for (User *U : UsersToUpdate)
152  U->replaceUsesOfWith(Inst, PN);
153  PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
154  }
155  }
156 
157  // Then for each PHI add the operand for the edge from the cloned loop.
158  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
159  assert(PN->getNumOperands() == 1 &&
160  "Exit block should only have on predecessor");
161 
162  // If the definition was cloned used that otherwise use the same value.
163  Value *ClonedValue = PN->getIncomingValue(0);
164  auto Mapped = VMap.find(ClonedValue);
165  if (Mapped != VMap.end())
166  ClonedValue = Mapped->second;
167 
168  PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
169  }
170 }
171 
173  // We need to turn the no-alias relation between pointer checking groups into
174  // no-aliasing annotations between instructions.
175  //
176  // We accomplish this by mapping each pointer checking group (a set of
177  // pointers memchecked together) to an alias scope and then also mapping each
178  // group to the list of scopes it can't alias.
179 
180  const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
181  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
182 
183  // First allocate an aliasing scope for each pointer checking group.
184  //
185  // While traversing through the checking groups in the loop, also create a
186  // reverse map from pointers to the pointer checking group they were assigned
187  // to.
188  MDBuilder MDB(Context);
189  MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
190 
191  for (const auto &Group : RtPtrChecking->CheckingGroups) {
192  GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
193 
194  for (unsigned PtrIdx : Group.Members)
195  PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
196  }
197 
198  // Go through the checks and for each pointer group, collect the scopes for
199  // each non-aliasing pointer group.
201  GroupToNonAliasingScopes;
202 
203  for (const auto &Check : AliasChecks)
204  GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
205 
206  // Finally, transform the above to actually map to scope list which is what
207  // the metadata uses.
208 
209  for (auto Pair : GroupToNonAliasingScopes)
210  GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
211 }
212 
214  if (!AnnotateNoAlias)
215  return;
216 
217  // First prepare the maps.
219 
220  // Add the scope and no-alias metadata to the instructions.
223  }
224 }
225 
227  const Instruction *OrigInst) {
228  if (!AnnotateNoAlias)
229  return;
230 
231  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
232  const Value *Ptr = isa<LoadInst>(OrigInst)
233  ? cast<LoadInst>(OrigInst)->getPointerOperand()
234  : cast<StoreInst>(OrigInst)->getPointerOperand();
235 
236  // Find the group for the pointer and then add the scope metadata.
237  auto Group = PtrToGroup.find(Ptr);
238  if (Group != PtrToGroup.end()) {
239  VersionedInst->setMetadata(
240  LLVMContext::MD_alias_scope,
242  VersionedInst->getMetadata(LLVMContext::MD_alias_scope),
243  MDNode::get(Context, GroupToScope[Group->second])));
244 
245  // Add the no-alias metadata.
246  auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
247  if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
248  VersionedInst->setMetadata(
249  LLVMContext::MD_noalias,
251  VersionedInst->getMetadata(LLVMContext::MD_noalias),
252  NonAliasingScopeList->second));
253  }
254 }
255 
256 namespace {
257 bool runImpl(LoopInfo *LI, function_ref<const LoopAccessInfo &(Loop &)> GetLAA,
258  DominatorTree *DT, ScalarEvolution *SE) {
259  // Build up a worklist of inner-loops to version. This is necessary as the
260  // act of versioning a loop creates new loops and can invalidate iterators
261  // across the loops.
262  SmallVector<Loop *, 8> Worklist;
263 
264  for (Loop *TopLevelLoop : *LI)
265  for (Loop *L : depth_first(TopLevelLoop))
266  // We only handle inner-most loops.
267  if (L->isInnermost())
268  Worklist.push_back(L);
269 
270  // Now walk the identified inner loops.
271  bool Changed = false;
272  for (Loop *L : Worklist) {
273  if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||
274  !L->getExitingBlock())
275  continue;
276  const LoopAccessInfo &LAI = GetLAA(*L);
277  if (!LAI.hasConvergentOp() &&
279  !LAI.getPSE().getPredicate().isAlwaysTrue())) {
280  LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L,
281  LI, DT, SE);
282  LVer.versionLoop();
283  LVer.annotateLoopWithNoAlias();
284  Changed = true;
285  }
286  }
287 
288  return Changed;
289 }
290 
291 /// Also expose this is a pass. Currently this is only used for
292 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing
293 /// array accesses from the loop.
294 class LoopVersioningLegacyPass : public FunctionPass {
295 public:
296  LoopVersioningLegacyPass() : FunctionPass(ID) {
298  }
299 
300  bool runOnFunction(Function &F) override {
301  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
302  auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
303  return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(&L);
304  };
305 
306  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
307  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
308 
309  return runImpl(LI, GetLAA, 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);
349  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
350  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
351  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
352  auto &AA = AM.getResult<AAManager>(F);
353  auto &AC = AM.getResult<AssumptionAnalysis>(F);
354 
355  auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
356  auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
357  LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE,
358  TLI, TTI, nullptr, nullptr, nullptr};
359  return LAM.getResult<LoopAccessAnalysis>(L, AR);
360  };
361 
362  if (runImpl(&LI, GetLAA, &DT, &SE))
363  return PreservedAnalyses::none();
364  return PreservedAnalyses::all();
365 }
366 } // namespace llvm
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1303
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2479
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2115
llvm::LoopAccessLegacyAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:771
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:137
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:81
llvm::PredicatedScalarEvolution::getPredicate
const SCEVPredicate & getPredicate() const
Definition: ScalarEvolution.cpp:14167
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:896
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:780
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:546
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:63
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
LoopAccessAnalysis.h
llvm::IRBuilder
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2495
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:139
llvm::LoopAccessAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:813
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:1287
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::MDBuilder::createAnonymousAliasScope
MDNode * createAnonymousAliasScope(MDNode *Domain, StringRef Name=StringRef())
Return metadata appropriate for an alias scope root node.
Definition: MDBuilder.h:140
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1300
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:1366
llvm::LoopVersioning::annotateInstWithNoAlias
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
Definition: LoopVersioning.cpp:226
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:172
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2747
llvm::User
Definition: User.h:44
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::remapInstructionsInBlocks
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
Definition: CloneFunction.cpp:882
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
runImpl
static bool runImpl(const TargetLibraryInfo &TLI, Function &F)
Definition: ReplaceWithVeclib.cpp:176
Domain
Domain
Definition: CorrelatedValuePropagation.cpp:710
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:372
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2145
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:1556
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:571
llvm::MDBuilder::createAnonymousAliasScopeDomain
MDNode * createAnonymousAliasScopeDomain(StringRef Name=StringRef())
Return metadata appropriate for an alias scope domain node.
Definition: MDBuilder.h:133
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:279
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
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:475
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:77
llvm::RuntimePointerChecking
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
Definition: LoopAccessAnalysis.h:382
InstSimplifyFolder.h
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
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:2801
llvm::RuntimePointerChecking::getChecks
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
Definition: LoopAccessAnalysis.h:444
llvm::RuntimePointerChecking::CheckingGroups
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
Definition: LoopAccessAnalysis.h:483
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::DenseMap
Definition: DenseMap.h:716
llvm::LoopAccessInfo::getRuntimePointerChecking
const RuntimePointerChecking * getRuntimePointerChecking() const
Definition: LoopAccessAnalysis.h:573
I
#define I(x, y, z)
Definition: MD5.cpp:58
Cloning.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:559
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
ArrayRef.h
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:228
llvm::SCEVPredicate::isAlwaysTrue
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:163
llvm::MDNode
Metadata node.
Definition: Metadata.h:937
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:601
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:1102
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:944
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:305
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"))
LAM
LoopAnalysisManager LAM
Definition: PassBuilderBindings.cpp:58
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:309
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:69
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:57
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:388
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:2693
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:104
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:579
LoopVersioning.h
llvm::MDBuilder
Definition: MDBuilder.h:35
AA
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:2651
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:498
llvm::SmallVectorImpl< Instruction * >
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
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:213
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:937
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:405
llvm::LoopAccessInfo::getPSE
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
Definition: LoopAccessAnalysis.h:636
BasicBlockUtils.h
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:837
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:443
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:1262
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38