bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
};
+/// This struct holds information about the memory runtime legality check that
+/// a group of pointers do not overlap.
+struct RuntimePointerChecking {
+ RuntimePointerChecking(ScalarEvolution *SE) : Need(false), SE(SE) {}
+
+ /// Reset the state of the pointer runtime information.
+ void reset() {
+ Need = false;
+ Pointers.clear();
+ Starts.clear();
+ Ends.clear();
+ IsWritePtr.clear();
+ DependencySetId.clear();
+ AliasSetId.clear();
+ Exprs.clear();
+ }
+
+ /// Insert a pointer and calculate the start and end SCEVs.
+ void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
+ unsigned ASId, const ValueToValueMap &Strides);
+
+ /// \brief No run-time memory checking is necessary.
+ bool empty() const { return Pointers.empty(); }
+
+ /// A grouping of pointers. A single memcheck is required between
+ /// two groups.
+ struct CheckingPtrGroup {
+ /// \brief Create a new pointer checking group containing a single
+ /// pointer, with index \p Index in RtCheck.
+ CheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck)
+ : RtCheck(RtCheck), High(RtCheck.Ends[Index]),
+ Low(RtCheck.Starts[Index]) {
+ Members.push_back(Index);
+ }
+
+ /// \brief Tries to add the pointer recorded in RtCheck at index
+ /// \p Index to this pointer checking group. We can only add a pointer
+ /// to a checking group if we will still be able to get
+ /// the upper and lower bounds of the check. Returns true in case
+ /// of success, false otherwise.
+ bool addPointer(unsigned Index);
+
+ /// Constitutes the context of this pointer checking group. For each
+ /// pointer that is a member of this group we will retain the index
+ /// at which it appears in RtCheck.
+ RuntimePointerChecking &RtCheck;
+ /// The SCEV expression which represents the upper bound of all the
+ /// pointers in this group.
+ const SCEV *High;
+ /// The SCEV expression which represents the lower bound of all the
+ /// pointers in this group.
+ const SCEV *Low;
+ /// Indices of all the pointers that constitute this grouping.
+ SmallVector<unsigned, 2> Members;
+ };
+
+ /// \brief Groups pointers such that a single memcheck is required
+ /// between two different groups. This will clear the CheckingGroups vector
+ /// and re-compute it. We will only group dependecies if \p UseDependencies
+ /// is true, otherwise we will create a separate group for each pointer.
+ void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
+ bool UseDependencies);
+
+ /// \brief Decide whether we need to issue a run-time check for pointer at
+ /// index \p I and \p J to prove their independence.
+ ///
+ /// If \p PtrPartition is set, it contains the partition number for
+ /// pointers (-1 if the pointer belongs to multiple partitions). In this
+ /// case omit checks between pointers belonging to the same partition.
+ bool needsChecking(unsigned I, unsigned J,
+ const SmallVectorImpl<int> *PtrPartition) const;
+
+ /// \brief Decide if we need to add a check between two groups of pointers,
+ /// according to needsChecking.
+ bool needsChecking(const CheckingPtrGroup &M, const CheckingPtrGroup &N,
+ const SmallVectorImpl<int> *PtrPartition) const;
+
+ /// \brief Return true if any pointer requires run-time checking according
+ /// to needsChecking.
+ bool needsAnyChecking(const SmallVectorImpl<int> *PtrPartition) const;
+
+ /// \brief Returns the number of run-time checks required according to
+ /// needsChecking.
+ unsigned getNumberOfChecks(const SmallVectorImpl<int> *PtrPartition) const;
+
+ /// \brief Print the list run-time memory checks necessary.
+ ///
+ /// If \p PtrPartition is set, it contains the partition number for
+ /// pointers (-1 if the pointer belongs to multiple partitions). In this
+ /// case omit checks between pointers belonging to the same partition.
+ void print(raw_ostream &OS, unsigned Depth = 0,
+ const SmallVectorImpl<int> *PtrPartition = nullptr) const;
+
+ /// This flag indicates if we need to add the runtime check.
+ bool Need;
+ /// Holds the pointers that we need to check.
+ SmallVector<TrackingVH<Value>, 2> Pointers;
+ /// Holds the pointer value at the beginning of the loop.
+ SmallVector<const SCEV *, 2> Starts;
+ /// Holds the pointer value at the end of the loop.
+ SmallVector<const SCEV *, 2> Ends;
+ /// Holds the information if this pointer is used for writing to memory.
+ SmallVector<bool, 2> IsWritePtr;
+ /// Holds the id of the set of pointers that could be dependent because of a
+ /// shared underlying object.
+ SmallVector<unsigned, 2> DependencySetId;
+ /// Holds the id of the disjoint alias set to which this pointer belongs.
+ SmallVector<unsigned, 2> AliasSetId;
+ /// Holds at position i the SCEV for the access i
+ SmallVector<const SCEV *, 2> Exprs;
+ /// Holds a partitioning of pointers into "check groups".
+ SmallVector<CheckingPtrGroup, 2> CheckingGroups;
+ /// Holds a pointer to the ScalarEvolution analysis.
+ ScalarEvolution *SE;
+};
+
/// \brief Drive the analysis of memory accesses in the loop
///
/// This class is responsible for analyzing the memory accesses of a loop. It
/// RuntimePointerCheck class.
class LoopAccessInfo {
public:
- /// This struct holds information about the memory runtime legality check that
- /// a group of pointers do not overlap.
- struct RuntimePointerCheck {
- RuntimePointerCheck(ScalarEvolution *SE) : Need(false), SE(SE) {}
-
- /// Reset the state of the pointer runtime information.
- void reset() {
- Need = false;
- Pointers.clear();
- Starts.clear();
- Ends.clear();
- IsWritePtr.clear();
- DependencySetId.clear();
- AliasSetId.clear();
- Exprs.clear();
- }
-
- /// Insert a pointer and calculate the start and end SCEVs.
- void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
- unsigned ASId, const ValueToValueMap &Strides);
-
- /// \brief No run-time memory checking is necessary.
- bool empty() const { return Pointers.empty(); }
-
- /// A grouping of pointers. A single memcheck is required between
- /// two groups.
- struct CheckingPtrGroup {
- /// \brief Create a new pointer checking group containing a single
- /// pointer, with index \p Index in RtCheck.
- CheckingPtrGroup(unsigned Index, RuntimePointerCheck &RtCheck)
- : RtCheck(RtCheck), High(RtCheck.Ends[Index]),
- Low(RtCheck.Starts[Index]) {
- Members.push_back(Index);
- }
-
- /// \brief Tries to add the pointer recorded in RtCheck at index
- /// \p Index to this pointer checking group. We can only add a pointer
- /// to a checking group if we will still be able to get
- /// the upper and lower bounds of the check. Returns true in case
- /// of success, false otherwise.
- bool addPointer(unsigned Index);
-
- /// Constitutes the context of this pointer checking group. For each
- /// pointer that is a member of this group we will retain the index
- /// at which it appears in RtCheck.
- RuntimePointerCheck &RtCheck;
- /// The SCEV expression which represents the upper bound of all the
- /// pointers in this group.
- const SCEV *High;
- /// The SCEV expression which represents the lower bound of all the
- /// pointers in this group.
- const SCEV *Low;
- /// Indices of all the pointers that constitute this grouping.
- SmallVector<unsigned, 2> Members;
- };
-
- /// \brief Groups pointers such that a single memcheck is required
- /// between two different groups. This will clear the CheckingGroups vector
- /// and re-compute it. We will only group dependecies if \p UseDependencies
- /// is true, otherwise we will create a separate group for each pointer.
- void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
- bool UseDependencies);
-
- /// \brief Decide whether we need to issue a run-time check for pointer at
- /// index \p I and \p J to prove their independence.
- ///
- /// If \p PtrPartition is set, it contains the partition number for
- /// pointers (-1 if the pointer belongs to multiple partitions). In this
- /// case omit checks between pointers belonging to the same partition.
- bool needsChecking(unsigned I, unsigned J,
- const SmallVectorImpl<int> *PtrPartition) const;
-
- /// \brief Decide if we need to add a check between two groups of pointers,
- /// according to needsChecking.
- bool needsChecking(const CheckingPtrGroup &M,
- const CheckingPtrGroup &N,
- const SmallVectorImpl<int> *PtrPartition) const;
-
- /// \brief Return true if any pointer requires run-time checking according
- /// to needsChecking.
- bool needsAnyChecking(const SmallVectorImpl<int> *PtrPartition) const;
-
- /// \brief Returns the number of run-time checks required according to
- /// needsChecking.
- unsigned getNumberOfChecks(const SmallVectorImpl<int> *PtrPartition) const;
-
- /// \brief Print the list run-time memory checks necessary.
- ///
- /// If \p PtrPartition is set, it contains the partition number for
- /// pointers (-1 if the pointer belongs to multiple partitions). In this
- /// case omit checks between pointers belonging to the same partition.
- void print(raw_ostream &OS, unsigned Depth = 0,
- const SmallVectorImpl<int> *PtrPartition = nullptr) const;
-
- /// This flag indicates if we need to add the runtime check.
- bool Need;
- /// Holds the pointers that we need to check.
- SmallVector<TrackingVH<Value>, 2> Pointers;
- /// Holds the pointer value at the beginning of the loop.
- SmallVector<const SCEV*, 2> Starts;
- /// Holds the pointer value at the end of the loop.
- SmallVector<const SCEV*, 2> Ends;
- /// Holds the information if this pointer is used for writing to memory.
- SmallVector<bool, 2> IsWritePtr;
- /// Holds the id of the set of pointers that could be dependent because of a
- /// shared underlying object.
- SmallVector<unsigned, 2> DependencySetId;
- /// Holds the id of the disjoint alias set to which this pointer belongs.
- SmallVector<unsigned, 2> AliasSetId;
- /// Holds at position i the SCEV for the access i
- SmallVector<const SCEV *, 2> Exprs;
- /// Holds a partitioning of pointers into "check groups".
- SmallVector<CheckingPtrGroup, 2> CheckingGroups;
- /// Holds a pointer to the ScalarEvolution analysis.
- ScalarEvolution *SE;
- };
-
LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL,
const TargetLibraryInfo *TLI, AliasAnalysis *AA,
DominatorTree *DT, LoopInfo *LI,
/// no memory dependence cycles.
bool canVectorizeMemory() const { return CanVecMem; }
- const RuntimePointerCheck *getRuntimePointerCheck() const {
- return &PtrRtCheck;
+ const RuntimePointerChecking *getRuntimePointerChecking() const {
+ return &PtrRtChecking;
}
/// \brief Number of memchecks required to prove independence of otherwise
/// may-alias pointers.
unsigned getNumRuntimePointerChecks(
const SmallVectorImpl<int> *PtrPartition = nullptr) const {
- return PtrRtCheck.getNumberOfChecks(PtrPartition);
+ return PtrRtChecking.getNumberOfChecks(PtrPartition);
}
/// Return true if the block BB needs to be predicated in order for the loop
/// We need to check that all of the pointers in this list are disjoint
/// at runtime.
- RuntimePointerCheck PtrRtCheck;
+ RuntimePointerChecking PtrRtChecking;
/// \brief the Memory Dependence Checker which can determine the
/// loop-independent and loop-carried dependences between memory accesses.
return SE->getSCEV(Ptr);
}
-void LoopAccessInfo::RuntimePointerCheck::insert(
- Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId, unsigned ASId,
- const ValueToValueMap &Strides) {
+void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, bool WritePtr,
+ unsigned DepSetId, unsigned ASId,
+ const ValueToValueMap &Strides) {
// Get the stride replaced scev.
const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
Exprs.push_back(Sc);
}
-bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
+bool RuntimePointerChecking::needsChecking(
const CheckingPtrGroup &M, const CheckingPtrGroup &N,
const SmallVectorImpl<int> *PtrPartition) const {
for (unsigned I = 0, EI = M.Members.size(); EI != I; ++I)
return I;
}
-bool LoopAccessInfo::RuntimePointerCheck::CheckingPtrGroup::addPointer(
- unsigned Index) {
+bool RuntimePointerChecking::CheckingPtrGroup::addPointer(unsigned Index) {
// Compare the starts and ends with the known minimum and maximum
// of this set. We need to know how we compare against the min/max
// of the set in order to be able to emit memchecks.
return true;
}
-void LoopAccessInfo::RuntimePointerCheck::groupChecks(
- MemoryDepChecker::DepCandidates &DepCands,
- bool UseDependencies) {
+void RuntimePointerChecking::groupChecks(
+ MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies) {
// We build the groups from dependency candidates equivalence classes
// because:
// - We know that pointers in the same equivalence class share
}
}
-bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
+bool RuntimePointerChecking::needsChecking(
unsigned I, unsigned J, const SmallVectorImpl<int> *PtrPartition) const {
// No need to check if two readonly pointers intersect.
if (!IsWritePtr[I] && !IsWritePtr[J])
return true;
}
-void LoopAccessInfo::RuntimePointerCheck::print(
+void RuntimePointerChecking::print(
raw_ostream &OS, unsigned Depth,
const SmallVectorImpl<int> *PtrPartition) const {
}
}
-unsigned LoopAccessInfo::RuntimePointerCheck::getNumberOfChecks(
+unsigned RuntimePointerChecking::getNumberOfChecks(
const SmallVectorImpl<int> *PtrPartition) const {
unsigned NumPartitions = CheckingGroups.size();
return CheckCount;
}
-bool LoopAccessInfo::RuntimePointerCheck::needsAnyChecking(
+bool RuntimePointerChecking::needsAnyChecking(
const SmallVectorImpl<int> *PtrPartition) const {
unsigned NumPointers = Pointers.size();
///
/// Returns true if we need no check or if we do and we can generate them
/// (i.e. the pointers have computable bounds).
- bool canCheckPtrAtRT(LoopAccessInfo::RuntimePointerCheck &RtCheck,
- ScalarEvolution *SE, Loop *TheLoop,
- const ValueToValueMap &Strides,
+ bool canCheckPtrAtRT(RuntimePointerChecking &RtCheck, ScalarEvolution *SE,
+ Loop *TheLoop, const ValueToValueMap &Strides,
bool ShouldCheckStride = false);
/// \brief Goes over all memory accesses, checks whether a RT check is needed
return AR->isAffine();
}
-bool AccessAnalysis::canCheckPtrAtRT(
- LoopAccessInfo::RuntimePointerCheck &RtCheck, ScalarEvolution *SE,
- Loop *TheLoop, const ValueToValueMap &StridesMap, bool ShouldCheckStride) {
+bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
+ ScalarEvolution *SE, Loop *TheLoop,
+ const ValueToValueMap &StridesMap,
+ bool ShouldCheckStride) {
// Find pointers with computable bounds. We are going to use this information
// to place a runtime bound check.
bool CanDoRT = true;
unsigned NumReads = 0;
unsigned NumReadWrites = 0;
- PtrRtCheck.Pointers.clear();
- PtrRtCheck.Need = false;
+ PtrRtChecking.Pointers.clear();
+ PtrRtChecking.Need = false;
const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
// Find pointers with computable bounds. We are going to use this information
// to place a runtime bound check.
bool CanDoRTIfNeeded =
- Accesses.canCheckPtrAtRT(PtrRtCheck, SE, TheLoop, Strides);
+ Accesses.canCheckPtrAtRT(PtrRtChecking, SE, TheLoop, Strides);
if (!CanDoRTIfNeeded) {
emitAnalysis(LoopAccessReport() << "cannot identify array bounds");
DEBUG(dbgs() << "LAA: We can't vectorize because we can't find "
// Clear the dependency checks. We assume they are not needed.
Accesses.resetDepChecks(DepChecker);
- PtrRtCheck.reset();
- PtrRtCheck.Need = true;
+ PtrRtChecking.reset();
+ PtrRtChecking.Need = true;
CanDoRTIfNeeded =
- Accesses.canCheckPtrAtRT(PtrRtCheck, SE, TheLoop, Strides, true);
+ Accesses.canCheckPtrAtRT(PtrRtChecking, SE, TheLoop, Strides, true);
// Check that we found the bounds for the pointer.
if (!CanDoRTIfNeeded) {
if (CanVecMem)
DEBUG(dbgs() << "LAA: No unsafe dependent memory operations in loop. We"
- << (PtrRtCheck.Need ? "" : " don't")
+ << (PtrRtChecking.Need ? "" : " don't")
<< " need runtime memory checks.\n");
else {
emitAnalysis(LoopAccessReport() <<
std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeCheck(
Instruction *Loc, const SmallVectorImpl<int> *PtrPartition) const {
- if (!PtrRtCheck.Need)
+ if (!PtrRtChecking.Need)
return std::make_pair(nullptr, nullptr);
SmallVector<TrackingVH<Value>, 2> Starts;
SCEVExpander Exp(*SE, DL, "induction");
Instruction *FirstInst = nullptr;
- for (unsigned i = 0; i < PtrRtCheck.CheckingGroups.size(); ++i) {
- const RuntimePointerCheck::CheckingPtrGroup &CG =
- PtrRtCheck.CheckingGroups[i];
- Value *Ptr = PtrRtCheck.Pointers[CG.Members[0]];
+ for (unsigned i = 0; i < PtrRtChecking.CheckingGroups.size(); ++i) {
+ const RuntimePointerChecking::CheckingPtrGroup &CG =
+ PtrRtChecking.CheckingGroups[i];
+ Value *Ptr = PtrRtChecking.Pointers[CG.Members[0]];
const SCEV *Sc = SE->getSCEV(Ptr);
if (SE->isLoopInvariant(Sc, TheLoop)) {
IRBuilder<> ChkBuilder(Loc);
// Our instructions might fold to a constant.
Value *MemoryRuntimeCheck = nullptr;
- for (unsigned i = 0; i < PtrRtCheck.CheckingGroups.size(); ++i) {
- for (unsigned j = i + 1; j < PtrRtCheck.CheckingGroups.size(); ++j) {
- const RuntimePointerCheck::CheckingPtrGroup &CGI =
- PtrRtCheck.CheckingGroups[i];
- const RuntimePointerCheck::CheckingPtrGroup &CGJ =
- PtrRtCheck.CheckingGroups[j];
-
- if (!PtrRtCheck.needsChecking(CGI, CGJ, PtrPartition))
+ for (unsigned i = 0; i < PtrRtChecking.CheckingGroups.size(); ++i) {
+ for (unsigned j = i + 1; j < PtrRtChecking.CheckingGroups.size(); ++j) {
+ const RuntimePointerChecking::CheckingPtrGroup &CGI =
+ PtrRtChecking.CheckingGroups[i];
+ const RuntimePointerChecking::CheckingPtrGroup &CGJ =
+ PtrRtChecking.CheckingGroups[j];
+
+ if (!PtrRtChecking.needsChecking(CGI, CGJ, PtrPartition))
continue;
unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace();
const TargetLibraryInfo *TLI, AliasAnalysis *AA,
DominatorTree *DT, LoopInfo *LI,
const ValueToValueMap &Strides)
- : PtrRtCheck(SE), DepChecker(SE, L), TheLoop(L), SE(SE), DL(DL), TLI(TLI),
- AA(AA), DT(DT), LI(LI), NumLoads(0), NumStores(0),
+ : PtrRtChecking(SE), DepChecker(SE, L), TheLoop(L), SE(SE), DL(DL),
+ TLI(TLI), AA(AA), DT(DT), LI(LI), NumLoads(0), NumStores(0),
MaxSafeDepDistBytes(-1U), CanVecMem(false),
StoreToLoopInvariantAddress(false) {
if (canAnalyzeLoop())
void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
if (CanVecMem) {
- if (PtrRtCheck.Need)
+ if (PtrRtChecking.Need)
OS.indent(Depth) << "Memory dependences are safe with run-time checks\n";
else
OS.indent(Depth) << "Memory dependences are safe\n";
OS.indent(Depth) << "Too many interesting dependences, not recorded\n";
// List the pair of accesses need run-time checks to prove independence.
- PtrRtCheck.print(OS, Depth);
+ PtrRtChecking.print(OS, Depth);
OS << "\n";
OS.indent(Depth) << "Store to invariant address was "
/// partitions its entry is set to -1.
SmallVector<int, 8>
computePartitionSetForPointers(const LoopAccessInfo &LAI) {
- const LoopAccessInfo::RuntimePointerCheck *RtPtrCheck =
- LAI.getRuntimePointerCheck();
+ const RuntimePointerChecking *RtPtrCheck = LAI.getRuntimePointerChecking();
unsigned N = RtPtrCheck->Pointers.size();
SmallVector<int, 8> PtrToPartitions(N);
LoopVersioning LVer(LAI, L, LI, DT, &PtrToPartition);
if (LVer.needsRuntimeChecks()) {
DEBUG(dbgs() << "\nPointers:\n");
- DEBUG(LAI.getRuntimePointerCheck()->print(dbgs(), 0, &PtrToPartition));
+ DEBUG(LAI.getRuntimePointerChecking()->print(dbgs(), 0, &PtrToPartition));
LVer.versionLoop(this);
LVer.addPHINodes(DefsUsedOutside);
}
}
bool LoopVersioning::needsRuntimeChecks() const {
- return LAI.getRuntimePointerCheck()->needsAnyChecking(PtrToPartition);
+ return LAI.getRuntimePointerChecking()->needsAnyChecking(PtrToPartition);
}
void LoopVersioning::versionLoop(Pass *P) {
bool isUniformAfterVectorization(Instruction* I) { return Uniforms.count(I); }
/// Returns the information that we collected about runtime memory check.
- const LoopAccessInfo::RuntimePointerCheck *getRuntimePointerCheck() const {
- return LAI->getRuntimePointerCheck();
+ const RuntimePointerChecking *getRuntimePointerChecking() const {
+ return LAI->getRuntimePointerChecking();
}
const LoopAccessInfo *getLAI() const {
// Collect all of the variables that remain uniform after vectorization.
collectLoopUniforms();
- DEBUG(dbgs() << "LV: We can vectorize this loop" <<
- (LAI->getRuntimePointerCheck()->Need ? " (with a runtime bound check)" :
- "")
- <<"!\n");
+ DEBUG(dbgs() << "LV: We can vectorize this loop"
+ << (LAI->getRuntimePointerChecking()->Need
+ ? " (with a runtime bound check)"
+ : "")
+ << "!\n");
// Analyze interleaved memory accesses.
if (EnableInterleavedMemAccesses)
LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize) {
// Width 1 means no vectorize
VectorizationFactor Factor = { 1U, 0U };
- if (OptForSize && Legal->getRuntimePointerCheck()->Need) {
+ if (OptForSize && Legal->getRuntimePointerChecking()->Need) {
emitAnalysis(VectorizationReport() <<
"runtime pointer checks needed. Enable vectorization of this "
"loop with '#pragma clang loop vectorize(enable)' when "
// Note that if we've already vectorized the loop we will have done the
// runtime check and so interleaving won't require further checks.
bool InterleavingRequiresRuntimePointerCheck =
- (VF == 1 && Legal->getRuntimePointerCheck()->Need);
+ (VF == 1 && Legal->getRuntimePointerChecking()->Need);
// We want to interleave small loops in order to reduce the loop overhead and
// potentially expose ILP opportunities.
projects / oota-llvm.git / commitdiff