LLVM  13.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"
18 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/MDBuilder.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/InitializePasses.h"
30 
31 using namespace llvm;
32 
33 static cl::opt<bool>
34  AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
35  cl::Hidden,
36  cl::desc("Add no-alias annotation for instructions that "
37  "are disambiguated by memchecks"));
38 
41  LoopInfo *LI, DominatorTree *DT,
42  ScalarEvolution *SE)
43  : VersionedLoop(L), NonVersionedLoop(nullptr),
44  AliasChecks(Checks.begin(), Checks.end()),
45  Preds(LAI.getPSE().getUnionPredicate()), LAI(LAI), LI(LI), DT(DT),
46  SE(SE) {
47  assert(L->getUniqueExitBlock() && "No single exit block");
48 }
49 
51  const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
52  assert(VersionedLoop->isLoopSimplifyForm() &&
53  "Loop is not in loop-simplify form");
54 
55  Instruction *FirstCheckInst;
56  Instruction *MemRuntimeCheck;
57  Value *SCEVRuntimeCheck;
58  Value *RuntimeCheck = nullptr;
59 
60  // Add the memcheck in the original preheader (this is empty initially).
61  BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
62  const auto &RtPtrChecking = *LAI.getRuntimePointerChecking();
63 
64  SCEVExpander Exp2(*RtPtrChecking.getSE(),
65  VersionedLoop->getHeader()->getModule()->getDataLayout(),
66  "induction");
67  std::tie(FirstCheckInst, MemRuntimeCheck) = addRuntimeChecks(
68  RuntimeCheckBB->getTerminator(), VersionedLoop, AliasChecks, Exp2);
69 
70  SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
71  "scev.check");
72  SCEVRuntimeCheck =
73  Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator());
74  auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck);
75 
76  // Discard the SCEV runtime check if it is always true.
77  if (CI && CI->isZero())
78  SCEVRuntimeCheck = nullptr;
79 
80  if (MemRuntimeCheck && SCEVRuntimeCheck) {
81  RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
82  SCEVRuntimeCheck, "lver.safe");
83  if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
84  I->insertBefore(RuntimeCheckBB->getTerminator());
85  } else
86  RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
87 
88  assert(RuntimeCheck && "called even though we don't need "
89  "any runtime checks");
90 
91  // Rename the block to make the IR more readable.
92  RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
93  ".lver.check");
94 
95  // Create empty preheader for the loop (and after cloning for the
96  // non-versioned loop).
97  BasicBlock *PH =
98  SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI,
99  nullptr, VersionedLoop->getHeader()->getName() + ".ph");
100 
101  // Clone the loop including the preheader.
102  //
103  // FIXME: This does not currently preserve SimplifyLoop because the exit
104  // block is a join between the two loops.
105  SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
106  NonVersionedLoop =
107  cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
108  ".lver.orig", LI, DT, NonVersionedLoopBlocks);
109  remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
110 
111  // Insert the conditional branch based on the result of the memchecks.
112  Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
113  BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
114  VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
115  OrigTerm->eraseFromParent();
116 
117  // The loops merge in the original exit block. This is now dominated by the
118  // memchecking block.
119  DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
120 
121  // Adds the necessary PHI nodes for the versioned loops based on the
122  // loop-defined values used outside of the loop.
123  addPHINodes(DefsUsedOutside);
124  formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true);
125  formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true);
126  assert(NonVersionedLoop->isLoopSimplifyForm() &&
127  VersionedLoop->isLoopSimplifyForm() &&
128  "The versioned loops should be in simplify form.");
129 }
130 
131 void LoopVersioning::addPHINodes(
132  const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
133  BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
134  assert(PHIBlock && "No single successor to loop exit block");
135  PHINode *PN;
136 
137  // First add a single-operand PHI for each DefsUsedOutside if one does not
138  // exists yet.
139  for (auto *Inst : DefsUsedOutside) {
140  // See if we have a single-operand PHI with the value defined by the
141  // original loop.
142  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
143  if (PN->getIncomingValue(0) == Inst)
144  break;
145  }
146  // If not create it.
147  if (!PN) {
148  PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
149  &PHIBlock->front());
150  SmallVector<User*, 8> UsersToUpdate;
151  for (User *U : Inst->users())
152  if (!VersionedLoop->contains(cast<Instruction>(U)->getParent()))
153  UsersToUpdate.push_back(U);
154  for (User *U : UsersToUpdate)
155  U->replaceUsesOfWith(Inst, PN);
156  PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
157  }
158  }
159 
160  // Then for each PHI add the operand for the edge from the cloned loop.
161  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
162  assert(PN->getNumOperands() == 1 &&
163  "Exit block should only have on predecessor");
164 
165  // If the definition was cloned used that otherwise use the same value.
166  Value *ClonedValue = PN->getIncomingValue(0);
167  auto Mapped = VMap.find(ClonedValue);
168  if (Mapped != VMap.end())
169  ClonedValue = Mapped->second;
170 
171  PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
172  }
173 }
174 
176  // We need to turn the no-alias relation between pointer checking groups into
177  // no-aliasing annotations between instructions.
178  //
179  // We accomplish this by mapping each pointer checking group (a set of
180  // pointers memchecked together) to an alias scope and then also mapping each
181  // group to the list of scopes it can't alias.
182 
183  const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
184  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
185 
186  // First allocate an aliasing scope for each pointer checking group.
187  //
188  // While traversing through the checking groups in the loop, also create a
189  // reverse map from pointers to the pointer checking group they were assigned
190  // to.
191  MDBuilder MDB(Context);
192  MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
193 
194  for (const auto &Group : RtPtrChecking->CheckingGroups) {
195  GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
196 
197  for (unsigned PtrIdx : Group.Members)
198  PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
199  }
200 
201  // Go through the checks and for each pointer group, collect the scopes for
202  // each non-aliasing pointer group.
204  GroupToNonAliasingScopes;
205 
206  for (const auto &Check : AliasChecks)
207  GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
208 
209  // Finally, transform the above to actually map to scope list which is what
210  // the metadata uses.
211 
212  for (auto Pair : GroupToNonAliasingScopes)
213  GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
214 }
215 
217  if (!AnnotateNoAlias)
218  return;
219 
220  // First prepare the maps.
222 
223  // Add the scope and no-alias metadata to the instructions.
226  }
227 }
228 
230  const Instruction *OrigInst) {
231  if (!AnnotateNoAlias)
232  return;
233 
234  LLVMContext &Context = VersionedLoop->getHeader()->getContext();
235  const Value *Ptr = isa<LoadInst>(OrigInst)
236  ? cast<LoadInst>(OrigInst)->getPointerOperand()
237  : cast<StoreInst>(OrigInst)->getPointerOperand();
238 
239  // Find the group for the pointer and then add the scope metadata.
240  auto Group = PtrToGroup.find(Ptr);
241  if (Group != PtrToGroup.end()) {
242  VersionedInst->setMetadata(
243  LLVMContext::MD_alias_scope,
245  VersionedInst->getMetadata(LLVMContext::MD_alias_scope),
246  MDNode::get(Context, GroupToScope[Group->second])));
247 
248  // Add the no-alias metadata.
249  auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
250  if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
251  VersionedInst->setMetadata(
252  LLVMContext::MD_noalias,
254  VersionedInst->getMetadata(LLVMContext::MD_noalias),
255  NonAliasingScopeList->second));
256  }
257 }
258 
259 namespace {
260 bool runImpl(LoopInfo *LI, function_ref<const LoopAccessInfo &(Loop &)> GetLAA,
261  DominatorTree *DT, ScalarEvolution *SE) {
262  // Build up a worklist of inner-loops to version. This is necessary as the
263  // act of versioning a loop creates new loops and can invalidate iterators
264  // across the loops.
265  SmallVector<Loop *, 8> Worklist;
266 
267  for (Loop *TopLevelLoop : *LI)
268  for (Loop *L : depth_first(TopLevelLoop))
269  // We only handle inner-most loops.
270  if (L->isInnermost())
271  Worklist.push_back(L);
272 
273  // Now walk the identified inner loops.
274  bool Changed = false;
275  for (Loop *L : Worklist) {
276  if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||
277  !L->getExitingBlock())
278  continue;
279  const LoopAccessInfo &LAI = GetLAA(*L);
280  if (!LAI.hasConvergentOp() &&
282  !LAI.getPSE().getUnionPredicate().isAlwaysTrue())) {
283  LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L,
284  LI, DT, SE);
285  LVer.versionLoop();
286  LVer.annotateLoopWithNoAlias();
287  Changed = true;
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 GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
306  return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(&L);
307  };
308 
309  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
310  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
311 
312  return runImpl(LI, GetLAA, DT, SE);
313  }
314 
315  void getAnalysisUsage(AnalysisUsage &AU) const override {
322  }
323 
324  static char ID;
325 };
326 }
327 
328 #define LVER_OPTION "loop-versioning"
329 #define DEBUG_TYPE LVER_OPTION
330 
332 static const char LVer_name[] = "Loop Versioning";
333 
334 INITIALIZE_PASS_BEGIN(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
335  false)
340 INITIALIZE_PASS_END(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
341  false)
342 
343 namespace llvm {
345  return new LoopVersioningLegacyPass();
346 }
347 
350  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
351  auto &LI = AM.getResult<LoopAnalysis>(F);
352  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
353  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
354  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
355  auto &AA = AM.getResult<AAManager>(F);
356  auto &AC = AM.getResult<AssumptionAnalysis>(F);
358  ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA()
359  : nullptr;
360 
361  auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
362  auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
363  LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE,
364  TLI, TTI, nullptr, MSSA};
365  return LAM.getResult<LoopAccessAnalysis>(L, AR);
366  };
367 
368  if (runImpl(&LI, GetLAA, &DT, &SE))
369  return PreservedAnalyses::none();
370  return PreservedAnalyses::all();
371 }
372 } // namespace llvm
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1233
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2320
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2105
llvm::LoopAccessLegacyAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:717
llvm
Definition: AllocatorList.h:23
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:138
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:82
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:797
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:769
llvm::ValueMap::end
iterator end()
Definition: ValueMap.h:136
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
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:1167
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
LoopAccessAnalysis.h
llvm::PredicatedScalarEvolution::getUnionPredicate
const SCEVUnionPredicate & getUnionPredicate() const
Definition: ScalarEvolution.cpp:13348
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::LoopAccessAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:759
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
ScalarEvolution.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1258
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::EnableMSSALoopDependency
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.
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:1198
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1330
llvm::LoopVersioning::annotateInstWithNoAlias
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
Definition: LoopVersioning.cpp:229
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
CommandLine.h
LVER_OPTION
#define LVER_OPTION
Definition: LoopVersioning.cpp:328
LVer_name
static const char LVer_name[]
Definition: LoopVersioning.cpp:332
llvm::LoopVersioning::prepareNoAliasMetadata
void prepareNoAliasMetadata()
Set up the aliasing scopes based on the memchecks.
Definition: LoopVersioning.cpp:175
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:2696
llvm::User
Definition: User.h:44
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::remapInstructionsInBlocks
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
Definition: CloneFunction.cpp:783
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:177
Domain
Domain
Definition: CorrelatedValuePropagation.cpp:660
TargetLibraryInfo.h
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
MDBuilder.h
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:361
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2135
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:144
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:49
llvm::LoopAccessInfo::hasConvergentOp
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Definition: LoopAccessAnalysis.h:531
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:282
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: STLExtras.h:168
Check
static bool Check(DecodeStatus &Out, DecodeStatus In)
Definition: AArch64Disassembler.cpp:230
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:478
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:78
llvm::RuntimePointerChecking
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
Definition: LoopAccessAnalysis.h:372
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
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:40
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2750
llvm::RuntimePointerChecking::getChecks
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
Definition: LoopAccessAnalysis.h:430
llvm::RuntimePointerChecking::CheckingGroups
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
Definition: LoopAccessAnalysis.h:458
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3091
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:704
llvm::LoopAccessInfo::getRuntimePointerChecking
const RuntimePointerChecking * getRuntimePointerChecking() const
Definition: LoopAccessAnalysis.h:533
I
#define I(x, y, z)
Definition: MD5.cpp:59
Cloning.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:519
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
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:242
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:162
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:922
llvm::SCEVUnionPredicate::isAlwaysTrue
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:13257
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:561
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:1080
llvm::MDNode::concatenate
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
Definition: Metadata.cpp:908
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:294
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.cpp:148
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:308
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:32
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LoopVersioningPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopVersioning.cpp:348
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:63
llvm::RuntimePointerChecking::PointerInfo::PointerValue
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.
Definition: LoopAccessAnalysis.h:378
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:39
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
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:2642
llvm::addRuntimeChecks
std::pair< Instruction *, Instruction * > 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:1641
llvm::LoopVersioning::versionLoop
void versionLoop()
Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...
Definition: LoopVersioning.h:63
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:539
LoopVersioning.h
llvm::MDBuilder
Definition: MDBuilder.h:35
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
MemorySSA.h
llvm::createLoopVersioningLegacyPass
FunctionPass * createLoopVersioningLegacyPass()
Definition: LoopVersioning.cpp:344
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
Dominators.h
llvm::PHINode
Definition: Instructions.h:2600
llvm::RuntimePointerChecking::getPointerInfo
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
Definition: LoopAccessAnalysis.h:473
llvm::SmallVectorImpl< Instruction * >
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:397
llvm::initializeLoopVersioningLegacyPassPass
void initializeLoopVersioningLegacyPassPass(PassRegistry &)
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::LoopVersioning::annotateLoopWithNoAlias
void annotateLoopWithNoAlias()
Annotate memory instructions in the versioned loop with no-alias metadata based on the memchecks issu...
Definition: LoopVersioning.cpp:216
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:926
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::cl::desc
Definition: CommandLine.h:414
llvm::LoopAccessInfo::getPSE
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
Definition: LoopAccessAnalysis.h:591
llvm::BinaryOperator::Create
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.
Definition: Instructions.cpp:2550
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:814
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:438
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1233
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38