Differential D133404 Diff 461810 llvm/lib/Analysis/MemorySSA.cpp

Changeset View

Standalone View

llvm/lib/Analysis/MemorySSA.cpp

Show First 20 Lines • Show All 522 Lines • ▼ Show 20 Lines	template <class AliasAnalysisType> class ClobberWalker {
unsigned *UpwardWalkLimit;		unsigned *UpwardWalkLimit;

// Phi optimization bookkeeping:		// Phi optimization bookkeeping:
// List of DefPath to process during the current phi optimization walk.		// List of DefPath to process during the current phi optimization walk.
SmallVector<DefPath, 32> Paths;		SmallVector<DefPath, 32> Paths;
// List of visited <Access, Location> pairs; we can skip paths already		// List of visited <Access, Location> pairs; we can skip paths already
// visited with the same memory location.		// visited with the same memory location.
DenseSet<ConstMemoryAccessPair> VisitedPhis;		DenseSet<ConstMemoryAccessPair> VisitedPhis;
// Record if phi translation has been performed during the current phi
// optimization walk, as merging alias results after phi translation can
// yield incorrect results. Context in PR46156.
bool PerformedPhiTranslation = false;

/// Find the nearest def or phi that `From` can legally be optimized to.		/// Find the nearest def or phi that `From` can legally be optimized to.
const MemoryAccess getWalkTarget(const MemoryPhi From) const {		const MemoryAccess getWalkTarget(const MemoryPhi From) const {
assert(From->getNumOperands() && "Phi with no operands?");		assert(From->getNumOperands() && "Phi with no operands?");

BasicBlock *BB = From->getBlock();		BasicBlock *BB = From->getBlock();
MemoryAccess *Result = MSSA.getLiveOnEntryDef();		MemoryAccess *Result = MSSA.getLiveOnEntryDef();
DomTreeNode *Node = DT.getNode(BB);		DomTreeNode *Node = DT.getNode(BB);
▲ Show 20 Lines • Show All 55 Lines • ▼ Show 20 Lines	walkToPhiOrClobber(DefPath &Desc, const MemoryAccess *StopAt = nullptr,

assert(isa<MemoryPhi>(Desc.Last) &&		assert(isa<MemoryPhi>(Desc.Last) &&
"Ended at a non-clobber that's not a phi?");		"Ended at a non-clobber that's not a phi?");
return {Desc.Last, false};		return {Desc.Last, false};
}		}

void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,		void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
ListIndex PriorNode) {		ListIndex PriorNode) {
auto UpwardDefsBegin = upward_defs_begin({Phi, Paths[PriorNode].Loc}, DT,		auto UpwardDefsBegin = upward_defs_begin({Phi, Paths[PriorNode].Loc}, DT);
&PerformedPhiTranslation);
auto UpwardDefs = make_range(UpwardDefsBegin, upward_defs_end());		auto UpwardDefs = make_range(UpwardDefsBegin, upward_defs_end());
for (const MemoryAccessPair &P : UpwardDefs) {		for (const MemoryAccessPair &P : UpwardDefs) {
PausedSearches.push_back(Paths.size());		PausedSearches.push_back(Paths.size());
Paths.emplace_back(P.second, P.first, PriorNode);		Paths.emplace_back(P.second, P.first, PriorNode);
}		}
}		}

/// Represents a search that terminated after finding a clobber. This clobber		/// Represents a search that terminated after finding a clobber. This clobber
Show All 38 Lines	while (!PausedSearches.empty()) {
// optimization for A, B, and D; C will be skipped because it dies here.		// optimization for A, B, and D; C will be skipped because it dies here.
// This arguably isn't the worst thing ever, since:		// This arguably isn't the worst thing ever, since:
// - We generally query things in a top-down order, so if we got below D		// - We generally query things in a top-down order, so if we got below D
// without needing cache entries for {C, MemLoc}, then chances are		// without needing cache entries for {C, MemLoc}, then chances are
// that those cache entries would end up ultimately unused.		// that those cache entries would end up ultimately unused.
// - We still cache things for A, so C only needs to walk up a bit.		// - We still cache things for A, so C only needs to walk up a bit.
// If this behavior becomes problematic, we can fix without a ton of extra		// If this behavior becomes problematic, we can fix without a ton of extra
// work.		// work.
if (!VisitedPhis.insert({Node.Last, Node.Loc}).second) {		if (!VisitedPhis.insert({Node.Last, Node.Loc}).second)
if (PerformedPhiTranslation) {
// If visiting this path performed Phi translation, don't continue,
// since it may not be correct to merge results from two paths if one
// relies on the phi translation.
TerminatedPath Term{Node.Last, PathIndex};
return Term;
}
continue;		continue;
}

const MemoryAccess *SkipStopWhere = nullptr;		const MemoryAccess *SkipStopWhere = nullptr;
if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {		if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
assert(isa<MemoryDef>(Query->OriginalAccess));		assert(isa<MemoryDef>(Query->OriginalAccess));
SkipStopWhere = Query->OriginalAccess;		SkipStopWhere = Query->OriginalAccess;
}		}

UpwardsWalkResult Res = walkToPhiOrClobber(Node,		UpwardsWalkResult Res = walkToPhiOrClobber(Node,
▲ Show 20 Lines • Show All 96 Lines • ▼ Show 20 Lines	template <class AliasAnalysisType> class ClobberWalker {
/// - Otherwise, walk from A to another clobber or phi, A'.		/// - Otherwise, walk from A to another clobber or phi, A'.
/// - If A' is a def, we're done.		/// - If A' is a def, we're done.
/// - If A' is a phi, try to optimize it.		/// - If A' is a phi, try to optimize it.
///		///
/// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path		/// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path
/// terminates when a MemoryAccess that clobbers said MemoryLocation is found.		/// terminates when a MemoryAccess that clobbers said MemoryLocation is found.
OptznResult tryOptimizePhi(MemoryPhi Phi, MemoryAccess Start,		OptznResult tryOptimizePhi(MemoryPhi Phi, MemoryAccess Start,
const MemoryLocation &Loc) {		const MemoryLocation &Loc) {
assert(Paths.empty() && VisitedPhis.empty() && !PerformedPhiTranslation &&		assert(Paths.empty() && VisitedPhis.empty() &&
"Reset the optimization state.");		"Reset the optimization state.");

Paths.emplace_back(Loc, Start, Phi, None);		Paths.emplace_back(Loc, Start, Phi, None);
// Stores how many "valid" optimization nodes we had prior to calling		// Stores how many "valid" optimization nodes we had prior to calling
// addSearches/getBlockingAccess. Necessary for caching if we had a blocker.		// addSearches/getBlockingAccess. Necessary for caching if we had a blocker.
auto PriorPathsSize = Paths.size();		auto PriorPathsSize = Paths.size();

SmallVector<ListIndex, 16> PausedSearches;		SmallVector<ListIndex, 16> PausedSearches;
▲ Show 20 Lines • Show All 139 Lines • ▼ Show 20 Lines	void verifyOptResult(const OptznResult &R) const {
assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) {		assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) {
return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);		return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);
}));		}));
}		}

void resetPhiOptznState() {		void resetPhiOptznState() {
Paths.clear();		Paths.clear();
VisitedPhis.clear();		VisitedPhis.clear();
PerformedPhiTranslation = false;
}		}

public:		public:
ClobberWalker(const MemorySSA &MSSA, AliasAnalysisType &AA, DominatorTree &DT)		ClobberWalker(const MemorySSA &MSSA, AliasAnalysisType &AA, DominatorTree &DT)
: MSSA(MSSA), AA(AA), DT(DT) {}		: MSSA(MSSA), AA(AA), DT(DT) {}

AliasAnalysisType *getAA() { return &AA; }		AliasAnalysisType *getAA() { return &AA; }
/// Finds the nearest clobber for the given query, optimizing phis if		/// Finds the nearest clobber for the given query, optimizing phis if
▲ Show 20 Lines • Show All 1,711 Lines • Show Last 20 Lines