Differential D114480 Diff 389327 llvm/lib/Analysis/LoopAccessAnalysis.cpp

Changeset View

Standalone View

llvm/lib/Analysis/LoopAccessAnalysis.cpp

Show First 20 Lines • Show All 138 Lines • ▼ Show 20 Lines	if (CI->getOperand(0)->getType()->isIntegerTy())
return CI->getOperand(0);		return CI->getOperand(0);
return V;		return V;
}		}

const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,		const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
const ValueToValueMap &PtrToStride,		const ValueToValueMap &PtrToStride,
Value *Ptr) {		Value *Ptr) {
const SCEV *OrigSCEV = PSE.getSCEV(Ptr);		const SCEV *OrigSCEV = PSE.getSCEV(Ptr);

// If there is an entry in the map return the SCEV of the pointer with the		// If there is an entry in the map return the SCEV of the pointer with the
// symbolic stride replaced by one.		// symbolic stride replaced by one.
ValueToValueMap::const_iterator SI = PtrToStride.find(Ptr);		ValueToValueMap::const_iterator SI = PtrToStride.find(Ptr);
if (SI == PtrToStride.end())		if (SI == PtrToStride.end())
// For a non-symbolic stride, just return the original expression.		// For a non-symbolic stride, just return the original expression.
return OrigSCEV;		return OrigSCEV;

Value *StrideVal = stripIntegerCast(SI->second);		Value *StrideVal = stripIntegerCast(SI->second);
▲ Show 20 Lines • Show All 510 Lines • ▼ Show 20 Lines
visitPointers(Value *StartPtr, const Loop &InnermostLoop,		visitPointers(Value *StartPtr, const Loop &InnermostLoop,
PredicatedScalarEvolution &PSE,		PredicatedScalarEvolution &PSE,
const ValueToValueMap &SymbolicStrides,		const ValueToValueMap &SymbolicStrides,
function_ref<void(Value , const SCEV )> AddPointer) {		function_ref<void(Value , const SCEV )> AddPointer) {
SmallPtrSet<Value *, 8> Visited;		SmallPtrSet<Value *, 8> Visited;
SmallVector<Value *> WorkList;		SmallVector<Value *> WorkList;
WorkList.push_back(StartPtr);		WorkList.push_back(StartPtr);

		ScalarEvolution &SE = *PSE.getSE();
while (!WorkList.empty()) {		while (!WorkList.empty()) {
Value *Ptr = WorkList.pop_back_val();		Value *Ptr = WorkList.pop_back_val();
if (!Visited.insert(Ptr).second)		if (!Visited.insert(Ptr).second)
continue;		continue;
auto *PN = dyn_cast<PHINode>(Ptr);		auto *PN = dyn_cast<PHINode>(Ptr);
// SCEV does not look through non-header PHIs inside the loop. Such phis		// SCEV does not look through non-header PHIs inside the loop. Such phis
// can be analyzed by adding separate accesses for each incoming pointer		// can be analyzed by adding separate accesses for each incoming pointer
// value.		// value.
if (PN && InnermostLoop.contains(PN->getParent()) &&		if (PN && InnermostLoop.contains(PN->getParent()) &&
PN->getParent() != InnermostLoop.getHeader()) {		PN->getParent() != InnermostLoop.getHeader()) {
for (const Use &Inc : PN->incoming_values())		for (const Use &Inc : PN->incoming_values())
WorkList.push_back(Inc);		WorkList.push_back(Inc);
} else		} else {
		auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);
		if (GEP && GEP->getNumOperands() == 2) {
		if (auto *SI = dyn_cast<SelectInst>(GEP->getOperand(0))) {
		const SCEV *BaseA = SE.getSCEV(SI->getOperand(1));
		const SCEV *BaseB = SE.getSCEV(SI->getOperand(2));
		const SCEV *Offset = SE.getSCEV(GEP->getOperand(1));
		if (SE.getTypeSizeInBits(Offset->getType()) <
		SE.getTypeSizeInBits(BaseA->getType()))
		Offset = SE.getSignExtendExpr(
		Offset, SE.getEffectiveSCEVType(BaseA->getType()));
		auto *PtrA = SE.getAddExpr(BaseA, Offset, SCEV::FlagNUW);
		auto *PtrB = SE.getAddExpr(BaseB, Offset, SCEV::FlagNUW);
		AddPointer(Ptr, PtrA);
		AddPointer(Ptr, PtrB);
		continue;
		}
		}
AddPointer(Ptr, replaceSymbolicStrideSCEV(PSE, SymbolicStrides, Ptr));		AddPointer(Ptr, replaceSymbolicStrideSCEV(PSE, SymbolicStrides, Ptr));
}		}
}		}
		}

bool AccessAnalysis::createCheckForAccess(		bool AccessAnalysis::createCheckForAccess(
RuntimePointerChecking &RtCheck, MemAccessInfo Access,		RuntimePointerChecking &RtCheck, MemAccessInfo Access,
DenseMap<const SCEV , unsigned> &DepSetId, Loop TheLoop,		DenseMap<const SCEV , unsigned> &DepSetId, Loop TheLoop,
unsigned &RunningDepId, unsigned ASId, bool ShouldCheckWrap, bool Assume) {		unsigned &RunningDepId, unsigned ASId, bool ShouldCheckWrap, bool Assume) {
Value *Ptr = Access.getPointer();		Value *Ptr = Access.getPointer();
const SCEV *PtrScev =		const SCEV *PtrScev =
hasComputableBounds(PSE, Ptr, Access.getPtrExpr(), TheLoop, Assume);		hasComputableBounds(PSE, Ptr, Access.getPtrExpr(), TheLoop, Assume);
▲ Show 20 Lines • Show All 60 Lines • ▼ Show 20 Lines	for (auto &AS : AST) {

SmallVector<MemAccessInfo, 4> Retries;		SmallVector<MemAccessInfo, 4> Retries;

// First, count how many write and read accesses are in the alias set. Also		// First, count how many write and read accesses are in the alias set. Also
// collect MemAccessInfos for later.		// collect MemAccessInfos for later.
SmallVector<MemAccessInfo, 4> AccessInfos;		SmallVector<MemAccessInfo, 4> AccessInfos;
for (const auto &A : AS) {		for (const auto &A : AS) {
Value *Ptr = A.getValue();		Value *Ptr = A.getValue();
const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);		SmallVector<MemAccessInfo> Infos;
bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true, PtrScev));		visitPointers(Ptr, *TheLoop, PSE, StridesMap,
		[&Infos](Value Ptr, const SCEV PtrExpr) {
		Infos.emplace_back(Ptr, true, PtrExpr);
		});
		for (auto &Tmp : Infos) {
		bool IsWrite = Accesses.count(Tmp);

if (IsWrite)		if (IsWrite)
++NumWritePtrChecks;		++NumWritePtrChecks;
else		else
++NumReadPtrChecks;		++NumReadPtrChecks;
AccessInfos.emplace_back(Ptr, IsWrite, PtrScev);		AccessInfos.emplace_back(Ptr, IsWrite, Tmp.getPtrExpr());
		}
}		}

// We do not need runtime checks for this alias set, if there are no writes		// We do not need runtime checks for this alias set, if there are no writes
// or a single write and no reads.		// or a single write and no reads.
if (NumWritePtrChecks == 0 \|\|		if (NumWritePtrChecks == 0 \|\|
(NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {		(NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
assert((AS.size() <= 1 \|\| all_of(AccessInfos,		assert((AS.size() <= 1 \|\| all_of(AccessInfos,
[](const MemAccessInfo &Info) {		[](const MemAccessInfo &Info) {
▲ Show 20 Lines • Show All 146 Lines • ▼ Show 20 Lines	for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
bool IsWrite = AC.isWrite();		bool IsWrite = AC.isWrite();

// If we're using the deferred access set, then it contains only		// If we're using the deferred access set, then it contains only
// reads.		// reads.
bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;		bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
if (UseDeferred && !IsReadOnlyPtr)		if (UseDeferred && !IsReadOnlyPtr)
continue;		continue;

const SCEV *PtrExpr =		visitPointers(
replaceSymbolicStrideSCEV(PSE, SymbolicStrides, Ptr);		Ptr, *TheLoop, PSE, SymbolicStrides,
// Otherwise, the pointer must be in the PtrAccessSet, either as a		[&](Value Ptr, const SCEV PtrExpr) {
// read or a write.		MemAccessInfo Access(Ptr, IsWrite, PtrExpr);
		// Otherwise, the pointer must be in the PtrAccessSet, either as
		// a read or a write.
assert(((IsReadOnlyPtr && UseDeferred) \|\| IsWrite \|\|		assert(((IsReadOnlyPtr && UseDeferred) \|\| IsWrite \|\|
S.count(MemAccessInfo(Ptr, false, PtrExpr))) &&		S.count(Access)) &&
"Alias-set pointer not in the access set?");		"Alias-set pointer not in the access set?");

MemAccessInfo Access(Ptr, IsWrite, PtrExpr);
DepCands.insert(Access);		DepCands.insert(Access);

// Memorize read-only pointers for later processing and skip them in		// Memorize read-only pointers for later processing and skip
// the first round (they need to be checked after we have seen all		// them in the first round (they need to be checked after we
// write pointers). Note: we also mark pointer that are not		// have seen all write pointers). Note: we also mark pointer
// consecutive as "read-only" pointers (so that we check		// that are not consecutive as "read-only" pointers (so that we
// "a[b[i]] +="). Hence, we need the second check for "!IsWrite".		// check "a[b[i]] +="). Hence, we need the second check for
		// "!IsWrite".
if (!UseDeferred && IsReadOnlyPtr) {		if (!UseDeferred && IsReadOnlyPtr) {
DeferredAccesses.insert(Access);		DeferredAccesses.insert(Access);
continue;		return;
}		}

// If this is a write - check other reads and writes for conflicts. If		// If this is a write - check other reads and writes for
// this is a read only check other writes for conflicts (but only if		// conflicts. If this is a read only check other writes for
// there is no other write to the ptr - this is an optimization to		// conflicts (but only if there is no other write to the ptr -
// catch "a[i] = a[i] + " without having to do a dependence check).		// this is an optimization to catch "a[i] = a[i] + " without
		// having to do a dependence check).
if ((IsWrite \|\| IsReadOnlyPtr) && SetHasWrite) {		if ((IsWrite \|\| IsReadOnlyPtr) && SetHasWrite) {
CheckDeps.push_back(Access);		CheckDeps.push_back(Access);
IsRTCheckAnalysisNeeded = true;		IsRTCheckAnalysisNeeded = true;
}		}

if (IsWrite)		if (IsWrite)
SetHasWrite = true;		SetHasWrite = true;

// Create sets of pointers connected by a shared alias set and		// Create sets of pointers connected by a shared alias set and
// underlying object.		// underlying object.
typedef SmallVector<const Value *, 16> ValueVector;		typedef SmallVector<const Value *, 16> ValueVector;
ValueVector TempObjects;		ValueVector TempObjects;

getUnderlyingObjects(Ptr, TempObjects, LI);		getUnderlyingObjects(Ptr, TempObjects, LI);
LLVM_DEBUG(dbgs()		LLVM_DEBUG(dbgs() << "Underlying objects for pointer " << *Ptr
<< "Underlying objects for pointer " << *Ptr << "\n");		<< "\n");
for (const Value *UnderlyingObj : TempObjects) {		for (const Value *UnderlyingObj : TempObjects) {
// nullptr never alias, don't join sets for pointer that have "null"		// nullptr never alias, don't join sets for pointer that have
// in their UnderlyingObjects list.		// "null" in their UnderlyingObjects list.
if (isa<ConstantPointerNull>(UnderlyingObj) &&		if (isa<ConstantPointerNull>(UnderlyingObj) &&
!NullPointerIsDefined(		!NullPointerIsDefined(
TheLoop->getHeader()->getParent(),		TheLoop->getHeader()->getParent(),
UnderlyingObj->getType()->getPointerAddressSpace()))		UnderlyingObj->getType()->getPointerAddressSpace()))
continue;		continue;

UnderlyingObjToAccessMap::iterator Prev =		UnderlyingObjToAccessMap::iterator Prev =
ObjToLastAccess.find(UnderlyingObj);		ObjToLastAccess.find(UnderlyingObj);
if (Prev != ObjToLastAccess.end())		if (Prev != ObjToLastAccess.end())
DepCands.unionSets(Access, Prev->second);		DepCands.unionSets(Access, Prev->second);

ObjToLastAccess[UnderlyingObj] = Access;		ObjToLastAccess[UnderlyingObj] = Access;
LLVM_DEBUG(dbgs() << " " << *UnderlyingObj << "\n");		LLVM_DEBUG(dbgs() << " " << *UnderlyingObj << "\n");
}		}
		});
}		}
}		}
}		}
}		}
}		}

static bool isInBoundsGep(Value *Ptr) {		static bool isInBoundsGep(Value *Ptr) {
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))		if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
▲ Show 20 Lines • Show All 1,394 Lines • Show Last 20 Lines