LLVM  14.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"
19 #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 }
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  auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck);
74 
75  // Discard the SCEV runtime check if it is always true.
76  if (CI && CI->isZero())
77  SCEVRuntimeCheck = nullptr;
78 
79  if (MemRuntimeCheck && SCEVRuntimeCheck) {
80  RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
81  SCEVRuntimeCheck, "lver.safe");
82  if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
83  I->insertBefore(RuntimeCheckBB->getTerminator());
84  } else
85  RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
86 
87  assert(RuntimeCheck && "called even though we don't need "
88  "any runtime checks");
89 
90  // Rename the block to make the IR more readable.
91  RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
92  ".lver.check");
93 
94  // Create empty preheader for the loop (and after cloning for the
95  // non-versioned loop).
96  BasicBlock *PH =
97  SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI,
98  nullptr, VersionedLoop->getHeader()->getName() + ".ph");
99 
100  // Clone the loop including the preheader.
101  //
102  // FIXME: This does not currently preserve SimplifyLoop because the exit
103  // block is a join between the two loops.
104  SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
105  NonVersionedLoop =
106  cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
107  ".lver.orig", LI, DT, NonVersionedLoopBlocks);
108  remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
109 
110  // Insert the conditional branch based on the result of the memchecks.
111  Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
112  BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
113  VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
114  OrigTerm->eraseFromParent();
115 
116  // The loops merge in the original exit block. This is now dominated by the
117  // memchecking block.
118  DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
119 
120  // Adds the necessary PHI nodes for the versioned loops based on the
121  // loop-defined values used outside of the loop.
122  addPHINodes(DefsUsedOutside);
123  formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true);
124  formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true);
125  assert(NonVersionedLoop->isLoopSimplifyForm() &&
126  VersionedLoop->isLoopSimplifyForm() &&
127  "The versioned loops should be in simplify form.");
128 }
129 
130 void LoopVersioning::addPHINodes(
131  const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
132  BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
133  assert(PHIBlock && "No single successor to loop exit block");
134  PHINode *PN;
135 
136  // First add a single-operand PHI for each DefsUsedOutside if one does not
137  // exists yet.
138  for (auto *Inst : DefsUsedOutside) {
139  // See if we have a single-operand PHI with the value defined by the
140  // original loop.
141  for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
142  if (PN->getIncomingValue(0) == Inst)
143  break;
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 {
259 bool runImpl(LoopInfo *LI, function_ref<const LoopAccessInfo &(Loop &)> GetLAA,
260  DominatorTree *DT, 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 = GetLAA(*L);
279  if (!LAI.hasConvergentOp() &&
281  !LAI.getPSE().getUnionPredicate().isAlwaysTrue())) {
282  LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L,
283  LI, DT, SE);
284  LVer.versionLoop();
285  LVer.annotateLoopWithNoAlias();
286  Changed = true;
287  }
288  }
289 
290  return Changed;
291 }
292 
293 /// Also expose this is a pass. Currently this is only used for
294 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing
295 /// array accesses from the loop.
296 class LoopVersioningLegacyPass : public FunctionPass {
297 public:
298  LoopVersioningLegacyPass() : FunctionPass(ID) {
300  }
301 
302  bool runOnFunction(Function &F) override {
303  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
304  auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
305  return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(&L);
306  };
307 
308  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
309  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
310 
311  return runImpl(LI, GetLAA, DT, SE);
312  }
313 
314  void getAnalysisUsage(AnalysisUsage &AU) const override {
321  }
322 
323  static char ID;
324 };
325 }
326 
327 #define LVER_OPTION "loop-versioning"
328 #define DEBUG_TYPE LVER_OPTION
329 
331 static const char LVer_name[] = "Loop Versioning";
332 
333 INITIALIZE_PASS_BEGIN(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
334  false)
339 INITIALIZE_PASS_END(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
340  false)
341 
342 namespace llvm {
344  return new LoopVersioningLegacyPass();
345 }
346 
349  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
350  auto &LI = AM.getResult<LoopAnalysis>(F);
351  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
352  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
353  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
354  auto &AA = AM.getResult<AAManager>(F);
355  auto &AC = AM.getResult<AssumptionAnalysis>(F);
356 
357  auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
358  auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
359  LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE,
360  TLI, TTI, nullptr, nullptr, nullptr};
361  return LAM.getResult<LoopAccessAnalysis>(L, AR);
362  };
363 
364  if (runImpl(&LI, GetLAA, &DT, &SE))
365  return PreservedAnalyses::none();
366  return PreservedAnalyses::all();
367 }
368 } // 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:1295
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2420
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2118
llvm::LoopAccessLegacyAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:710
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
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:801
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:783
llvm::ValueMap::end
iterator end()
Definition: ValueMap.h:136
llvm::Function
Definition: Function.h:62
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:66
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1176
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
LoopAccessAnalysis.h
llvm::PredicatedScalarEvolution::getUnionPredicate
const SCEVUnionPredicate & getUnionPredicate() const
Definition: ScalarEvolution.cpp:13891
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
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:752
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:236
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:227
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1271
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::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:1233
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:1336
llvm::LoopVersioning::annotateInstWithNoAlias
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
Definition: LoopVersioning.cpp:228
Context
ManagedStatic< detail::RecordContext > Context
Definition: Record.cpp:96
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
AliasAnalysis.h
CommandLine.h
LVER_OPTION
#define LVER_OPTION
Definition: LoopVersioning.cpp:327
LVer_name
static const char LVer_name[]
Definition: LoopVersioning.cpp:331
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:31
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2753
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:787
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:704
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:287
MDBuilder.h
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:376
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2148
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:148
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::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:1562
llvm::LoopAccessInfo::hasConvergentOp
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Definition: LoopAccessAnalysis.h:523
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: STLFunctionalExtras.h:36
Check
static bool Check(DecodeStatus &Out, DecodeStatus In)
Definition: AArch64Disassembler.cpp:248
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:78
llvm::RuntimePointerChecking
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
Definition: LoopAccessAnalysis.h:364
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:40
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2807
llvm::RuntimePointerChecking::getChecks
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
Definition: LoopAccessAnalysis.h:422
llvm::RuntimePointerChecking::CheckingGroups
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
Definition: LoopAccessAnalysis.h:450
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:3148
llvm::DenseMap
Definition: DenseMap.h:714
llvm::LoopAccessInfo::getRuntimePointerChecking
const RuntimePointerChecking * getRuntimePointerChecking() const
Definition: LoopAccessAnalysis.h:525
I
#define I(x, y, z)
Definition: MD5.cpp:58
Cloning.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:511
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:228
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:163
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::SCEVUnionPredicate::isAlwaysTrue
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:13790
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:553
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:1086
llvm::MDNode::concatenate
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
Definition: Metadata.cpp:914
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:309
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:152
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:36
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:228
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LoopVersioningPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopVersioning.cpp:347
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:370
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:2699
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:531
LoopVersioning.h
llvm::MDBuilder
Definition: MDBuilder.h:35
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::createLoopVersioningLegacyPass
FunctionPass * createLoopVersioningLegacyPass()
Definition: LoopVersioning.cpp:343
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
Dominators.h
llvm::PHINode
Definition: Instructions.h:2657
llvm::RuntimePointerChecking::getPointerInfo
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
Definition: LoopAccessAnalysis.h:465
llvm::SmallVectorImpl< Instruction * >
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
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:215
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:940
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:412
llvm::LoopAccessInfo::getPSE
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
Definition: LoopAccessAnalysis.h:583
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:2750
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:839
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:440
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:1246
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38