X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FLoopAccessAnalysis.h;h=13fe49942cbb966e013f54230700b6fda5ffdc76;hb=ea0f5e21081fe9147ad6bb2364238ea471e74a92;hp=7b635a8b49602bf83831af630ed10a370a1d4731;hpb=a420a142769d5d86ce55f9027668861d04238366;p=oota-llvm.git diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h index 7b635a8b496..13fe49942cb 100644 --- a/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/include/llvm/Analysis/LoopAccessAnalysis.h @@ -292,6 +292,159 @@ private: bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize); }; +/// \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 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(); + } + + /// 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.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 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::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 + PointerCheck; + + /// \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 + generateChecks(const SmallVectorImpl *PtrPartition = nullptr) 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 *PtrPartition) const; + + /// \brief Returns the number of run-time checks required according to + /// needsChecking. + unsigned getNumberOfChecks(const SmallVectorImpl *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 *PtrPartition = nullptr) const; + + /// Print \p Checks. + void printChecks(raw_ostream &OS, const SmallVectorImpl &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 Pointers; + + /// Holds a partitioning of pointers into "check groups". + SmallVector 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 &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 *PtrPartition = nullptr) const; + +private: + /// 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 @@ -308,72 +461,6 @@ private: /// 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. - /// - /// 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 *PtrPartition) const; - - /// \brief Return true if any pointer requires run-time checking according - /// to needsChecking. - bool needsAnyChecking(const SmallVectorImpl *PtrPartition) const; - - /// \brief Returns the number of run-time checks required according to - /// needsChecking. - unsigned getNumberOfChecks(const SmallVectorImpl *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 *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, 2> Pointers; - /// Holds the pointer value at the beginning of the loop. - SmallVector Starts; - /// Holds the pointer value at the end of the loop. - SmallVector Ends; - /// Holds the information if this pointer is used for writing to memory. - SmallVector IsWritePtr; - /// Holds the id of the set of pointers that could be dependent because of a - /// shared underlying object. - SmallVector DependencySetId; - /// Holds the id of the disjoint alias set to which this pointer belongs. - SmallVector AliasSetId; - }; - LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL, const TargetLibraryInfo *TLI, AliasAnalysis *AA, DominatorTree *DT, LoopInfo *LI, @@ -383,15 +470,15 @@ public: /// 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 *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 @@ -419,6 +506,16 @@ public: addRuntimeCheck(Instruction *Loc, const SmallVectorImpl *PtrPartition = nullptr) 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 + addRuntimeCheck(Instruction *Loc, + const SmallVectorImpl + &PointerChecks) const; + /// \brief The diagnostics report generated for the analysis. E.g. why we /// couldn't analyze the loop. const Optional &getReport() const { return Report; } @@ -461,7 +558,7 @@ private: /// 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.