LLVM  6.0.0svn
Classes | Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
llvm::RuntimePointerChecking Class Reference

Holds information about the memory runtime legality checks to verify that a group of pointers do not overlap. More...

#include "llvm/Analysis/LoopAccessAnalysis.h"

Collaboration diagram for llvm::RuntimePointerChecking:
Collaboration graph
[legend]

Classes

struct  CheckingPtrGroup
 A grouping of pointers. More...
 
struct  PointerInfo
 

Public Types

typedef std::pair< const CheckingPtrGroup *, const CheckingPtrGroup * > PointerCheck
 A memcheck which made up of a pair of grouped pointers. More...
 

Public Member Functions

 RuntimePointerChecking (ScalarEvolution *SE)
 
void reset ()
 Reset the state of the pointer runtime information. More...
 
void insert (Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId, unsigned ASId, const ValueToValueMap &Strides, PredicatedScalarEvolution &PSE)
 Insert a pointer and calculate the start and end SCEVs. More...
 
bool empty () const
 No run-time memory checking is necessary. More...
 
void generateChecks (MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies)
 Generate the checks and store it. More...
 
const SmallVector< PointerCheck, 4 > & getChecks () const
 Returns the checks that generateChecks created. More...
 
bool needsChecking (const CheckingPtrGroup &M, const CheckingPtrGroup &N) const
 Decide if we need to add a check between two groups of pointers, according to needsChecking. More...
 
unsigned getNumberOfChecks () const
 Returns the number of run-time checks required according to needsChecking. More...
 
void print (raw_ostream &OS, unsigned Depth=0) const
 Print the list run-time memory checks necessary. More...
 
void printChecks (raw_ostream &OS, const SmallVectorImpl< PointerCheck > &Checks, unsigned Depth=0) const
 Print Checks. More...
 
bool needsChecking (unsigned I, unsigned J) const
 Decide whether we need to issue a run-time check for pointer at index I and J to prove their independence. More...
 
const PointerInfogetPointerInfo (unsigned PtrIdx) const
 Return PointerInfo for pointer at index PtrIdx. More...
 

Static Public Member Functions

static bool arePointersInSamePartition (const SmallVectorImpl< int > &PtrToPartition, unsigned PtrIdx1, unsigned PtrIdx2)
 Check if pointers are in the same partition. More...
 

Public Attributes

bool Need
 This flag indicates if we need to add the runtime check. More...
 
SmallVector< PointerInfo, 2 > Pointers
 Information about the pointers that may require checking. More...
 
SmallVector< CheckingPtrGroup, 2 > CheckingGroups
 Holds a partitioning of pointers into "check groups". More...
 

Detailed Description

Holds information about the memory runtime legality checks to verify that a group of pointers do not overlap.

Definition at line 311 of file LoopAccessAnalysis.h.

Member Typedef Documentation

◆ PointerCheck

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.

Definition at line 400 of file LoopAccessAnalysis.h.

Constructor & Destructor Documentation

◆ RuntimePointerChecking()

llvm::RuntimePointerChecking::RuntimePointerChecking ( ScalarEvolution SE)
inline

Definition at line 340 of file LoopAccessAnalysis.h.

Member Function Documentation

◆ arePointersInSamePartition()

bool RuntimePointerChecking::arePointersInSamePartition ( const SmallVectorImpl< int > &  PtrToPartition,
unsigned  PtrIdx1,
unsigned  PtrIdx2 
)
static

Check if pointers are in the same partition.

PtrToPartition contains the partition number for pointers (-1 if the pointer belongs to multiple partitions).

Definition at line 427 of file LoopAccessAnalysis.cpp.

◆ empty()

bool llvm::RuntimePointerChecking::empty ( ) const
inline

No run-time memory checking is necessary.

Definition at line 359 of file LoopAccessAnalysis.h.

◆ generateChecks()

void RuntimePointerChecking::generateChecks ( MemoryDepChecker::DepCandidates DepCands,
bool  UseDependencies 
)

Generate the checks and store it.

This also performs the grouping of pointers to reduce the number of memchecks necessary.

Definition at line 250 of file LoopAccessAnalysis.cpp.

References assert().

Referenced by isNoWrap().

◆ getChecks()

const SmallVector<PointerCheck, 4>& llvm::RuntimePointerChecking::getChecks ( ) const
inline

Returns the checks that generateChecks created.

Definition at line 408 of file LoopAccessAnalysis.h.

References N.

Referenced by isLoadConditional(), and llvm::LoopVersioning::LoopVersioning().

◆ getNumberOfChecks()

unsigned llvm::RuntimePointerChecking::getNumberOfChecks ( ) const
inline

Returns the number of run-time checks required according to needsChecking.

Definition at line 417 of file LoopAccessAnalysis.h.

References llvm::Depth, and print().

Referenced by isNoWrap().

◆ getPointerInfo()

const PointerInfo& llvm::RuntimePointerChecking::getPointerInfo ( unsigned  PtrIdx) const
inline

Return PointerInfo for pointer at index PtrIdx.

Definition at line 448 of file LoopAccessAnalysis.h.

Referenced by isLoadConditional(), and llvm::LoopVersioning::prepareNoAliasMetadata().

◆ insert()

void RuntimePointerChecking::insert ( Loop Lp,
Value Ptr,
bool  WritePtr,
unsigned  DepSetId,
unsigned  ASId,
const ValueToValueMap Strides,
PredicatedScalarEvolution PSE 
)

Insert a pointer and calculate the start and end SCEVs.

Calculate Start and End points of memory access.

We need PSE 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 Strides, and add new predicates to PSE.

Let's assume A is the first access and B is a memory access on N-th loop iteration. Then B is calculated as: B = A + Step*N . Step value may be positive or negative. N is a calculated back-edge taken count: N = (TripCount > 0) ? RoundDown(TripCount -1 , VF) : 0 Start and End points are calculated in the following way: Start = UMIN(A, B) ; End = UMAX(A, B) + SizeOfElt, where SizeOfElt is the size of single memory access in bytes.

There is no conflict when the intervals are disjoint: NoConflict = (P2.Start >= P1.End) || (P1.Start >= P2.End)

Definition at line 190 of file LoopAccessAnalysis.cpp.

References assert(), llvm::dyn_cast(), llvm::SCEVAddRecExpr::evaluateAtIteration(), llvm::ScalarEvolution::getAddExpr(), llvm::PredicatedScalarEvolution::getBackedgeTakenCount(), llvm::ScalarEvolution::getConstant(), llvm::Type::getPointerElementType(), llvm::Type::getScalarSizeInBits(), llvm::PredicatedScalarEvolution::getSE(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::ScalarEvolution::getUMaxExpr(), llvm::ScalarEvolution::getUMinExpr(), I, llvm::ScalarEvolution::isLoopInvariant(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::replaceSymbolicStrideSCEV(), and std::swap().

Referenced by isNoWrap().

◆ needsChecking() [1/2]

bool RuntimePointerChecking::needsChecking ( const CheckingPtrGroup M,
const CheckingPtrGroup N 
) const

Decide if we need to add a check between two groups of pointers, according to needsChecking.

Definition at line 257 of file LoopAccessAnalysis.cpp.

References I, llvm::RuntimePointerChecking::CheckingPtrGroup::Members, and llvm::SmallVectorTemplateCommon< T, typename >::size().

◆ needsChecking() [2/2]

bool RuntimePointerChecking::needsChecking ( unsigned  I,
unsigned  J 
) const

Decide whether we need to issue a run-time check for pointer at index I and J to prove their independence.

Definition at line 434 of file LoopAccessAnalysis.cpp.

References llvm::RuntimePointerChecking::PointerInfo::AliasSetId, llvm::RuntimePointerChecking::PointerInfo::DependencySetId, I, and llvm::RuntimePointerChecking::PointerInfo::IsWritePtr.

◆ print()

void RuntimePointerChecking::print ( raw_ostream OS,
unsigned  Depth = 0 
) const

◆ printChecks()

void RuntimePointerChecking::printChecks ( raw_ostream OS,
const SmallVectorImpl< PointerCheck > &  Checks,
unsigned  Depth = 0 
) const

Print Checks.

Definition at line 453 of file LoopAccessAnalysis.cpp.

References Check(), llvm::raw_ostream::indent(), and N.

Referenced by isLoadConditional().

◆ reset()

void llvm::RuntimePointerChecking::reset ( )
inline

Reset the state of the pointer runtime information.

Definition at line 343 of file LoopAccessAnalysis.h.

Referenced by isNoWrap().

Member Data Documentation

◆ CheckingGroups

SmallVector<CheckingPtrGroup, 2> llvm::RuntimePointerChecking::CheckingGroups

Holds a partitioning of pointers into "check groups".

Definition at line 433 of file LoopAccessAnalysis.h.

Referenced by llvm::LoopVersioning::prepareNoAliasMetadata().

◆ Need

bool llvm::RuntimePointerChecking::Need

This flag indicates if we need to add the runtime check.

Definition at line 427 of file LoopAccessAnalysis.h.

Referenced by isNoWrap().

◆ Pointers

SmallVector<PointerInfo, 2> llvm::RuntimePointerChecking::Pointers

Information about the pointers that may require checking.

Definition at line 430 of file LoopAccessAnalysis.h.

Referenced by expandBounds(), and isNoWrap().


The documentation for this class was generated from the following files: