X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FLoopAccessAnalysis.h;h=c4a9dc42cc8f1ce783c3dd993c76bd1b5e849c65;hp=a4393bba2321c18fafa71dcab6c9b7dbab058c07;hb=20c9ab5fe6a097a4f8f7da745dffa39d830d4d6e;hpb=a0834f1d8771ccc41f135ffcfd93c1044daa9d4d diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h index a4393bba232..c4a9dc42cc8 100644 --- a/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/include/llvm/Analysis/LoopAccessAnalysis.h @@ -225,6 +225,8 @@ public: 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 &getMemoryInstructions() const { @@ -290,6 +292,157 @@ 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(); + Checks.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::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 + 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 &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 &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. + 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 + 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 Checks; +}; + /// \brief Drive the analysis of memory accesses in the loop /// /// This class is responsible for analyzing the memory accesses of a loop. It @@ -306,83 +459,24 @@ 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 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, 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. @@ -401,13 +495,18 @@ public: /// 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 + addRuntimeChecks(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 - addRuntimeCheck(Instruction *Loc, - const SmallVectorImpl *PtrPartition = nullptr) const; + addRuntimeChecks(Instruction *Loc, + const SmallVectorImpl + &PointerChecks) const; /// \brief The diagnostics report generated for the analysis. E.g. why we /// couldn't analyze the loop. @@ -451,22 +550,19 @@ 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. 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; @@ -497,6 +593,11 @@ const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE, const ValueToValueMap &PtrToStride, Value *Ptr, Value *OrigPtr = nullptr); +/// \brief Check the stride of the pointer and ensure that it does not wrap in +/// the address space. +int isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp, + const ValueToValueMap &StridesMap); + /// \brief This analysis provides dependence information for the memory accesses /// of a loop. /// @@ -541,6 +642,7 @@ private: const TargetLibraryInfo *TLI; AliasAnalysis *AA; DominatorTree *DT; + LoopInfo *LI; }; } // End llvm namespace