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 {
+/// \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();
- Starts.clear();
- Ends.clear();
- IsWritePtr.clear();
- DependencySetId.clear();
- AliasSetId.clear();
- Exprs.clear();
+ Checks.clear();
}
/// Insert a pointer and calculate the start and end SCEVs.
/// \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]) {
+ : RtCheck(RtCheck), High(RtCheck.Pointers[Index].End),
+ Low(RtCheck.Pointers[Index].Start) {
Members.push_back(Index);
}
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.
+ /// \brief A memcheck which made up of a pair of grouped pointers.
///
- /// 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;
+ /// These *have* to be const for now, since checks are generated from
+ /// CheckingPtrGroups in LAI::addRuntimeCheck 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 SmallVectorImpl<PointerCheck> &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 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;
+ unsigned getNumberOfChecks() const { return Checks.size(); }
/// \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;
+ 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;
- /// 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;
+
+ /// 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.
+ ///
+ /// 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 = nullptr) 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.
+ ///
+ /// \p PtrToPartition contains the partition number for pointers. If passed,
+ /// omit checks between pointers belonging to the same partition. Partition
+ /// number -1 means that the pointer is used in multiple partitions. In this
+ /// case we can't safely omit the check.
+ SmallVector<PointerCheck, 4>
+ generateChecks(const SmallVectorImpl<int> *PtrPartition = nullptr) 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
/// \brief Number of memchecks required to prove independence of otherwise
/// may-alias pointers.
- unsigned getNumRuntimePointerChecks(
- const SmallVectorImpl<int> *PtrPartition = nullptr) const {
- return PtrRtChecking.getNumberOfChecks(PtrPartition);
+ unsigned getNumRuntimePointerChecks() const {
+ return PtrRtChecking.getNumberOfChecks();
}
/// Return true if the block BB needs to be predicated in order for the loop
/// 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 *>
+ addRuntimeCheck(Instruction *Loc) const;
+
+ /// \brief Generete the instructions for the checks in \p PointerChecks.
///
- /// 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.
+ /// 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 *>
addRuntimeCheck(Instruction *Loc,
- const SmallVectorImpl<int> *PtrPartition = nullptr) const;
+ const SmallVectorImpl<RuntimePointerChecking::PointerCheck>
+ &PointerChecks) const;
/// \brief The diagnostics report generated for the analysis. E.g. why we
/// couldn't analyze the loop.
projects / oota-llvm.git / blobdiff