33#define DEBUG_TYPE "loop-versioning"
38 cl::desc(
"Add no-alias annotation for instructions that "
39 "are disambiguated by memchecks"));
45 : VersionedLoop(L), AliasChecks(Checks.begin(), Checks.end()),
46 Preds(LAI.getPSE().getPredicate()), LAI(LAI), LI(LI), DT(DT),
54 "Loop is not in loop-simplify form");
56 Value *MemRuntimeCheck;
57 Value *SCEVRuntimeCheck;
58 Value *RuntimeCheck =
nullptr;
68 VersionedLoop, AliasChecks, Exp2);
73 Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->
getTerminator());
78 if (MemRuntimeCheck && SCEVRuntimeCheck) {
81 Builder.CreateOr(MemRuntimeCheck, SCEVRuntimeCheck,
"lver.safe");
83 RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
85 assert(RuntimeCheck &&
"called even though we don't need "
86 "any runtime checks");
105 ".lver.orig", LI, DT, NonVersionedLoopBlocks);
110 Builder.SetInsertPoint(OrigTerm);
121 addPHINodes(DefsUsedOutside);
126 "The versioned loops should be in simplify form.");
129void LoopVersioning::addPHINodes(
132 assert(PHIBlock &&
"No single successor to loop exit block");
137 for (
auto *Inst : DefsUsedOutside) {
140 for (
auto I = PHIBlock->
begin(); (PN = dyn_cast<PHINode>(
I)); ++
I) {
152 if (!VersionedLoop->
contains(cast<Instruction>(U)->getParent()))
154 for (
User *U : UsersToUpdate)
155 U->replaceUsesOfWith(Inst, PN);
161 for (
auto I = PHIBlock->
begin(); (PN = dyn_cast<PHINode>(
I)); ++
I) {
163 "Exit block should only have on predecessor");
167 auto Mapped = VMap.
find(ClonedValue);
168 if (Mapped != VMap.
end())
169 ClonedValue = Mapped->second;
197 for (
unsigned PtrIdx : Group.Members)
204 GroupToNonAliasingScopes;
206 for (
const auto &
Check : AliasChecks)
207 GroupToNonAliasingScopes[
Check.first].push_back(GroupToScope[
Check.second]);
212 for (
const auto &Pair : GroupToNonAliasingScopes)
235 const Value *
Ptr = isa<LoadInst>(OrigInst)
236 ? cast<LoadInst>(OrigInst)->getPointerOperand()
237 : cast<StoreInst>(OrigInst)->getPointerOperand();
240 auto Group = PtrToGroup.find(
Ptr);
241 if (Group != PtrToGroup.end()) {
243 LLVMContext::MD_alias_scope,
245 VersionedInst->
getMetadata(LLVMContext::MD_alias_scope),
249 auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
250 if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
252 LLVMContext::MD_noalias,
254 VersionedInst->
getMetadata(LLVMContext::MD_noalias),
255 NonAliasingScopeList->second));
267 for (
Loop *TopLevelLoop : *LI)
270 if (L->isInnermost())
274 bool Changed =
false;
275 for (
Loop *L : Worklist) {
276 if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||
277 !L->getExitingBlock())
286 LVer.annotateLoopWithNoAlias();
303 if (
runImpl(&LI, LAIs, &DT, &SE))
static bool runImpl(Function &F, const TargetLowering &TLI)
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"))
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
LLVMContext & getContext() const
Get the context in which this basic block lives.
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...
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Analysis pass which computes a DominatorTree.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
This is an important class for using LLVM in a threaded context.
This analysis provides dependence information for the memory accesses of a loop.
const LoopAccessInfo & getInfo(Loop &L)
Drive the analysis of memory accesses in the loop.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
const RuntimePointerChecking * getRuntimePointerChecking() const
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
void annotateLoopWithNoAlias()
Annotate memory instructions in the versioned loop with no-alias metadata based on the memchecks issu...
void prepareNoAliasMetadata()
Set up the aliasing scopes based on the memchecks.
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
void versionLoop()
Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...
LoopVersioning(const LoopAccessInfo &LAI, ArrayRef< RuntimePointerCheck > Checks, Loop *L, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
Represents a single loop in the control flow graph.
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
MDNode * createAnonymousAliasScope(MDNode *Domain, StringRef Name=StringRef())
Return metadata appropriate for an alias scope root node.
MDNode * createAnonymousAliasScopeDomain(StringRef Name=StringRef())
Return metadata appropriate for an alias scope domain node.
static MDNode * concatenate(MDNode *A, MDNode *B)
Methods for metadata merging.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
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...
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
const SCEVPredicate & getPredicate() const
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
This class uses information about analyze scalars to rewrite expressions in canonical form.
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
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...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
unsigned getNumOperands() const
iterator find(const KeyT &Val)
LLVM Value Representation.
void setName(const Twine &Name)
Change the name of the value.
iterator_range< user_iterator > users()
StringRef getName() const
Return a constant reference to the value's name.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander, bool HoistRuntimeChecks=false)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock * > &Blocks)
Clones a loop OrigLoop.
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
iterator_range< df_iterator< T > > depth_first(const T &G)
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.