class Value;
class DataLayout;
-class AliasAnalysis;
class ScalarEvolution;
class Loop;
class SCEV;
+class SCEVUnionPredicate;
/// Optimization analysis message produced during vectorization. Messages inform
/// the user why vectorization did not occur.
const SmallVectorImpl<Instruction *> &Instrs) const;
};
- MemoryDepChecker(ScalarEvolution *Se, const Loop *L)
+ MemoryDepChecker(ScalarEvolution *Se, const Loop *L,
+ SCEVUnionPredicate &Preds)
: SE(Se), InnermostLoop(L), AccessIdx(0),
ShouldRetryWithRuntimeCheck(false), SafeForVectorization(true),
- RecordInterestingDependences(true) {}
+ RecordInterestingDependences(true), Preds(Preds) {}
/// \brief Register the location (instructions are given increasing numbers)
/// of a write access.
return RecordInterestingDependences ? &InterestingDependences : nullptr;
}
+ void clearInterestingDependences() { InterestingDependences.clear(); }
+
/// \brief The vector of memory access instructions. The indices are used as
/// instruction identifiers in the Dependence class.
const SmallVectorImpl<Instruction *> &getMemoryInstructions() const {
return InstMap;
}
+ /// \brief Find the set of instructions that read or write via \p Ptr.
+ SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
+ bool isWrite) const;
+
private:
ScalarEvolution *SE;
const Loop *InnermostLoop;
/// \brief Check whether the data dependence could prevent store-load
/// forwarding.
bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
+
+ /// The SCEV predicate containing all the SCEV-related assumptions.
+ /// The dependence checker needs this in order to convert SCEVs of pointers
+ /// to more accurate expressions in the context of existing assumptions.
+ /// We also need this in case assumptions about SCEV expressions need to
+ /// be made in order to avoid unknown dependences. For example we might
+ /// assume a unit stride for a pointer in order to prove that a memory access
+ /// is strided and doesn't wrap.
+ SCEVUnionPredicate &Preds;
+};
+
+/// \brief Holds information about the memory runtime legality checks to verify
+/// that a group of pointers do not overlap.
+class RuntimePointerChecking {
+public:
+ struct PointerInfo {
+ /// Holds the pointer value that we need to check.
+ TrackingVH<Value> PointerValue;
+ /// Holds the pointer value at the beginning of the loop.
+ const SCEV *Start;
+ /// Holds the pointer value at the end of the loop.
+ const SCEV *End;
+ /// Holds the information if this pointer is used for writing to memory.
+ bool IsWritePtr;
+ /// Holds the id of the set of pointers that could be dependent because of a
+ /// shared underlying object.
+ unsigned DependencySetId;
+ /// Holds the id of the disjoint alias set to which this pointer belongs.
+ unsigned AliasSetId;
+ /// SCEV for the access.
+ const SCEV *Expr;
+
+ PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End,
+ bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
+ const SCEV *Expr)
+ : PointerValue(PointerValue), Start(Start), End(End),
+ IsWritePtr(IsWritePtr), DependencySetId(DependencySetId),
+ AliasSetId(AliasSetId), Expr(Expr) {}
+ };
+
+ RuntimePointerChecking(ScalarEvolution *SE) : Need(false), SE(SE) {}
+
+ /// Reset the state of the pointer runtime information.
+ void reset() {
+ Need = false;
+ Pointers.clear();
+ Checks.clear();
+ }
+
+ /// Insert a pointer and calculate the start and end SCEVs.
+ /// \p We need Preds in order to compute the SCEV expression of the pointer
+ /// according to the assumptions that we've made during the analysis.
+ /// The method might also version the pointer stride according to \p Strides,
+ /// and change \p Preds.
+ void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
+ unsigned ASId, const ValueToValueMap &Strides,
+ SCEVUnionPredicate &Preds);
+
+ /// \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.Pointers[Index].End),
+ Low(RtCheck.Pointers[Index].Start) {
+ 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 A memcheck which made up of a pair of grouped pointers.
+ ///
+ /// These *have* to be const for now, since checks are generated from
+ /// CheckingPtrGroups in LAI::addRuntimeChecks which is a const member
+ /// function. FIXME: once check-generation is moved inside this class (after
+ /// the PtrPartition hack is removed), we could drop const.
+ typedef std::pair<const CheckingPtrGroup *, const CheckingPtrGroup *>
+ PointerCheck;
+
+ /// \brief Generate the checks and store it. This also performs the grouping
+ /// of pointers to reduce the number of memchecks necessary.
+ void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
+ bool UseDependencies);
+
+ /// \brief Returns the checks that generateChecks created.
+ const SmallVector<PointerCheck, 4> &getChecks() const { return Checks; }
+
+ /// \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;
+
+ /// \brief Returns the number of run-time checks required according to
+ /// needsChecking.
+ unsigned getNumberOfChecks() const { return Checks.size(); }
+
+ /// \brief Print the list run-time memory checks necessary.
+ void print(raw_ostream &OS, unsigned Depth = 0) const;
+
+ /// Print \p Checks.
+ void printChecks(raw_ostream &OS, const SmallVectorImpl<PointerCheck> &Checks,
+ unsigned Depth = 0) const;
+
+ /// This flag indicates if we need to add the runtime check.
+ bool Need;
+
+ /// Information about the pointers that may require checking.
+ SmallVector<PointerInfo, 2> Pointers;
+
+ /// Holds a partitioning of pointers into "check groups".
+ SmallVector<CheckingPtrGroup, 2> CheckingGroups;
+
+ /// \brief Check if pointers are in the same partition
+ ///
+ /// \p PtrToPartition contains the partition number for pointers (-1 if the
+ /// pointer belongs to multiple partitions).
+ static bool
+ arePointersInSamePartition(const SmallVectorImpl<int> &PtrToPartition,
+ unsigned PtrIdx1, unsigned PtrIdx2);
+
+ /// \brief Decide whether we need to issue a run-time check for pointer at
+ /// index \p I and \p J to prove their independence.
+ bool needsChecking(unsigned I, unsigned J) const;
+
+private:
+ /// \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);
+
+ /// Generate the checks and return them.
+ SmallVector<PointerCheck, 4>
+ generateChecks() const;
+
+ /// Holds a pointer to the ScalarEvolution analysis.
+ ScalarEvolution *SE;
+
+ /// \brief Set of run-time checks required to establish independence of
+ /// otherwise may-aliasing pointers in the loop.
+ SmallVector<PointerCheck, 4> Checks;
};
/// \brief Drive the analysis of memory accesses in the loop
/// 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() : Need(false) {}
-
- /// Reset the state of the pointer runtime information.
- void reset() {
- Need = false;
- Pointers.clear();
- Starts.clear();
- Ends.clear();
- IsWritePtr.clear();
- DependencySetId.clear();
- AliasSetId.clear();
- }
-
- /// Insert a pointer and calculate the start and end SCEVs.
- void insert(ScalarEvolution *SE, 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(); }
-
- /// \brief Decide whether we need to issue a run-time check for pointer at
- /// index \p I and \p J to prove their independence.
- bool needsChecking(unsigned I, unsigned J) const;
-
- /// \brief Print the list run-time memory checks necessary.
- void print(raw_ostream &OS, unsigned Depth = 0) 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;
- };
-
LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL,
const TargetLibraryInfo *TLI, AliasAnalysis *AA,
- DominatorTree *DT, const ValueToValueMap &Strides);
+ DominatorTree *DT, LoopInfo *LI,
+ const ValueToValueMap &Strides);
/// Return true we can analyze the memory accesses in the loop and there are
/// 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 { return NumComparisons; }
+ unsigned getNumRuntimePointerChecks() const {
+ return PtrRtChecking.getNumberOfChecks();
+ }
/// Return true if the block BB needs to be predicated in order for the loop
/// to be vectorized.
/// instruction generated in possibly a sequence of instructions and the
/// second value is the final comparator value or NULL if no check is needed.
std::pair<Instruction *, Instruction *>
- addRuntimeCheck(Instruction *Loc) const;
+ addRuntimeChecks(Instruction *Loc) const;
+
+ /// \brief Generete the instructions for the checks in \p PointerChecks.
+ ///
+ /// Returns a pair of instructions where the first element is the first
+ /// instruction generated in possibly a sequence of instructions and the
+ /// second value is the final comparator value or NULL if no check is needed.
+ std::pair<Instruction *, Instruction *>
+ addRuntimeChecks(Instruction *Loc,
+ const SmallVectorImpl<RuntimePointerChecking::PointerCheck>
+ &PointerChecks) const;
/// \brief The diagnostics report generated for the analysis. E.g. why we
/// couldn't analyze the loop.
/// loop-independent and loop-carried dependences between memory accesses.
const MemoryDepChecker &getDepChecker() const { return DepChecker; }
+ /// \brief Return the list of instructions that use \p Ptr to read or write
+ /// memory.
+ SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
+ bool isWrite) const {
+ return DepChecker.getInstructionsForAccess(Ptr, isWrite);
+ }
+
/// \brief Print the information about the memory accesses in the loop.
void print(raw_ostream &OS, unsigned Depth = 0) const;
/// Only used in DEBUG build but we don't want NDEBUG-dependent ABI.
unsigned NumSymbolicStrides;
+ /// \brief Checks existence of store to invariant address inside loop.
+ /// If the loop has any store to invariant address, then it returns true,
+ /// else returns false.
+ bool hasStoreToLoopInvariantAddress() const {
+ return StoreToLoopInvariantAddress;
+ }
+
+ /// The SCEV predicate contains all the SCEV-related assumptions.
+ /// The is used to keep track of the minimal set of assumptions on SCEV
+ /// expressions that the analysis needs to make in order to return a
+ /// meaningful result. All SCEV expressions during the analysis should be
+ /// re-written (and therefore simplified) according to Preds.
+ /// A user of LoopAccessAnalysis will need to emit the runtime checks
+ /// associated with this predicate.
+ SCEVUnionPredicate Preds;
+
private:
/// \brief Analyze the loop. Substitute symbolic strides using Strides.
void analyzeLoop(const ValueToValueMap &Strides);
/// 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.
MemoryDepChecker DepChecker;
- /// \brief Number of memchecks required to prove independence of otherwise
- /// may-alias pointers
- unsigned NumComparisons;
-
Loop *TheLoop;
ScalarEvolution *SE;
const DataLayout &DL;
const TargetLibraryInfo *TLI;
AliasAnalysis *AA;
DominatorTree *DT;
+ LoopInfo *LI;
unsigned NumLoads;
unsigned NumStores;
/// \brief Cache the result of analyzeLoop.
bool CanVecMem;
+ /// \brief Indicator for storing to uniform addresses.
+ /// If a loop has write to a loop invariant address then it should be true.
+ bool StoreToLoopInvariantAddress;
+
/// \brief The diagnostics report generated for the analysis. E.g. why we
/// couldn't analyze the loop.
Optional<LoopAccessReport> Report;
Value *stripIntegerCast(Value *V);
///\brief Return the SCEV corresponding to a pointer with the symbolic stride
-///replaced with constant one.
+/// replaced with constant one, assuming \p Preds is true.
+///
+/// If necessary this method will version the stride of the pointer according
+/// to \p PtrToStride and therefore add a new predicate to \p Preds.
///
/// If \p OrigPtr is not null, use it to look up the stride value instead of \p
/// Ptr. \p PtrToStride provides the mapping between the pointer value and its
/// stride as collected by LoopVectorizationLegality::collectStridedAccess.
const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE,
const ValueToValueMap &PtrToStride,
- Value *Ptr, Value *OrigPtr = nullptr);
+ SCEVUnionPredicate &Preds, Value *Ptr,
+ Value *OrigPtr = nullptr);
+
+/// \brief Check the stride of the pointer and ensure that it does not wrap in
+/// the address space, assuming \p Preds is true.
+///
+/// If necessary this method will version the stride of the pointer according
+/// to \p PtrToStride and therefore add a new predicate to \p Preds.
+int isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp,
+ const ValueToValueMap &StridesMap, SCEVUnionPredicate &Preds);
/// \brief This analysis provides dependence information for the memory accesses
/// of a loop.
const TargetLibraryInfo *TLI;
AliasAnalysis *AA;
DominatorTree *DT;
+ LoopInfo *LI;
};
} // End llvm namespace
projects / oota-llvm.git / blobdiff