Differential D114650 Diff 424873 llvm/lib/Analysis/ScalarEvolution.cpp

Changeset View

Standalone View

llvm/lib/Analysis/ScalarEvolution.cpp

This file is larger than 256 KB, so syntax highlighting is disabled by default.

Show First 20 Lines • Show All 4,318 Lines • ▼ Show 20 Lines	void ScalarEvolution::insertValueToMap(Value V, const SCEV S) {
}		}
}		}

/// Return an existing SCEV if it exists, otherwise analyze the expression and		/// Return an existing SCEV if it exists, otherwise analyze the expression and
/// create a new one.		/// create a new one.
const SCEV ScalarEvolution::getSCEV(Value V) {		const SCEV ScalarEvolution::getSCEV(Value V) {
assert(isSCEVable(V->getType()) && "Value is not SCEVable!");		assert(isSCEVable(V->getType()) && "Value is not SCEVable!");

const SCEV *S = getExistingSCEV(V);		if (const SCEV *S = getExistingSCEV(V))
if (S == nullptr) {
S = createSCEV(V);
// During PHI resolution, it is possible to create two SCEVs for the same
// V, so it is needed to double check whether V->S is inserted into
// ValueExprMap before insert S->{V, 0} into ExprValueMap.
std::pair<ValueExprMapType::iterator, bool> Pair =
ValueExprMap.insert({SCEVCallbackVH(V, this), S});
if (Pair.second)
ExprValueMap[S].insert(V);
}
return S;		return S;
		return createSCEVIter(V);
}		}

const SCEV ScalarEvolution::getExistingSCEV(Value V) {		const SCEV ScalarEvolution::getExistingSCEV(Value V) {
assert(isSCEVable(V->getType()) && "Value is not SCEVable!");		assert(isSCEVable(V->getType()) && "Value is not SCEVable!");

ValueExprMapType::iterator I = ValueExprMap.find_as(V);		ValueExprMapType::iterator I = ValueExprMap.find_as(V);
if (I != ValueExprMap.end()) {		if (I != ValueExprMap.end()) {
const SCEV *S = I->second;		const SCEV *S = I->second;
▲ Show 20 Lines • Show All 1,143 Lines • ▼ Show 20 Lines	const SCEV ScalarEvolution::createSimpleAffineAddRec(PHINode PN,
auto BO = MatchBinaryOp(BEValueV, DT);		auto BO = MatchBinaryOp(BEValueV, DT);
if (!BO)		if (!BO)
return nullptr;		return nullptr;

if (BO->Opcode != Instruction::Add)		if (BO->Opcode != Instruction::Add)
return nullptr;		return nullptr;

const SCEV *Accum = nullptr;		const SCEV *Accum = nullptr;
if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))		if (BO->LHS == PN && L->isLoopInvariant(BO->RHS)) {
Accum = getSCEV(BO->RHS);		Accum = getSCEV(BO->RHS);
else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))		assert(Accum);
		} else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS)) {
Accum = getSCEV(BO->LHS);		Accum = getSCEV(BO->LHS);
		assert(Accum);
		}

if (!Accum)		if (!Accum)
return nullptr;		return nullptr;

SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;		SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
if (BO->IsNUW)		if (BO->IsNUW)
Flags = setFlags(Flags, SCEV::FlagNUW);		Flags = setFlags(Flags, SCEV::FlagNUW);
if (BO->IsNSW)		if (BO->IsNSW)
Flags = setFlags(Flags, SCEV::FlagNSW);		Flags = setFlags(Flags, SCEV::FlagNSW);

const SCEV *StartVal = getSCEV(StartValueV);		const SCEV *StartVal = getExistingSCEV(StartValueV);
const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);		const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
insertValueToMap(PN, PHISCEV);		insertValueToMap(PN, PHISCEV);

// We can add Flags to the post-inc expression only if we		// We can add Flags to the post-inc expression only if we
// know that it is undefined behavior for BEValueV to		// know that it is undefined behavior for BEValueV to
// overflow.		// overflow.
if (auto *BEInst = dyn_cast<Instruction>(BEValueV)) {		if (auto *BEInst = dyn_cast<Instruction>(BEValueV)) {
assert(isLoopInvariant(Accum, L) &&		assert(isLoopInvariant(Accum, L) &&
"Accum is defined outside L, but is not invariant?");		"Accum is defined outside L, but is not invariant?");
if (isAddRecNeverPoison(BEInst, L))		if (isAddRecNeverPoison(BEInst, L))
(void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);		(void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
}		}

return PHISCEV;		return PHISCEV;
}		}

const SCEV ScalarEvolution::createAddRecFromPHI(PHINode PN) {		static std::pair<Value , Value > classifyPhiValues(PHINode *PN,
const Loop *L = LI.getLoopFor(PN->getParent());		const Loop *L) {
if (!L \|\| L->getHeader() != PN->getParent())		if (!L \|\| L->getHeader() != PN->getParent())
return nullptr;		return {nullptr, nullptr};

// The loop may have multiple entrances or multiple exits; we can analyze		// The loop may have multiple entrances or multiple exits; we can analyze
// this phi as an addrec if it has a unique entry value and a unique		// this phi as an addrec if it has a unique entry value and a unique
// backedge value.		// backedge value.
Value BEValueV = nullptr, StartValueV = nullptr;		Value BEValueV = nullptr, StartValueV = nullptr;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {		for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
Value *V = PN->getIncomingValue(i);		Value *V = PN->getIncomingValue(i);
if (L->contains(PN->getIncomingBlock(i))) {		if (L->contains(PN->getIncomingBlock(i))) {
if (!BEValueV) {		if (!BEValueV) {
BEValueV = V;		BEValueV = V;
} else if (BEValueV != V) {		} else if (BEValueV != V) {
BEValueV = nullptr;		BEValueV = nullptr;
break;		break;
}		}
} else if (!StartValueV) {		} else if (!StartValueV) {
StartValueV = V;		StartValueV = V;
} else if (StartValueV != V) {		} else if (StartValueV != V) {
StartValueV = nullptr;		StartValueV = nullptr;
break;		break;
}		}
}		}
		return {StartValueV, BEValueV};
		}

		const SCEV ScalarEvolution::createAddRecFromPHI(PHINode PN) {
		const Loop *L = LI.getLoopFor(PN->getParent());
		Value BEValueV, StartValueV;
		std::tie(StartValueV, BEValueV) = classifyPhiValues(PN, L);
if (!BEValueV \|\| !StartValueV)		if (!BEValueV \|\| !StartValueV)
return nullptr;		return nullptr;

assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&		assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
"PHI node already processed?");		"PHI node already processed?");

// First, try to find AddRec expression without creating a fictituos symbolic		// First, try to find AddRec expression without creating a fictituos symbolic
// value for PN.		// value for PN.
▲ Show 20 Lines • Show All 232 Lines • ▼ Show 20 Lines	if (DT.dominates(LeftEdge, RightUse) && DT.dominates(RightEdge, LeftUse)) {
LHS = RightUse;		LHS = RightUse;
RHS = LeftUse;		RHS = LeftUse;
return true;		return true;
}		}

return false;		return false;
}		}

const SCEV ScalarEvolution::createNodeFromSelectLikePHI(PHINode PN) {		static BranchInst getSelectPhiBr(PHINode PN, const Loop *L, DominatorTree &DT,
		LoopInfo &LI) {
auto IsReachable =		auto IsReachable =
[&](BasicBlock *BB) { return DT.isReachableFromEntry(BB); };		[&](BasicBlock *BB) { return DT.isReachableFromEntry(BB); };

if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) {		if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) {
const Loop *L = LI.getLoopFor(PN->getParent());

// We don't want to break LCSSA, even in a SCEV expression tree.		// We don't want to break LCSSA, even in a SCEV expression tree.
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)		for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
if (LI.getLoopFor(PN->getIncomingBlock(i)) != L)		if (LI.getLoopFor(PN->getIncomingBlock(i)) != L)
return nullptr;		return nullptr;

// Try to match		// Try to match
//		//
// br %cond, label %left, label %right		// br %cond, label %left, label %right
// left:		// left:
// br label %merge		// br label %merge
// right:		// right:
// br label %merge		// br label %merge
// merge:		// merge:
// V = phi [ %x, %left ], [ %y, %right ]		// V = phi [ %x, %left ], [ %y, %right ]
//		//
// as "select %cond, %x, %y"		// as "select %cond, %x, %y"

BasicBlock *IDom = DT[PN->getParent()]->getIDom()->getBlock();		BasicBlock *IDom = DT[PN->getParent()]->getIDom()->getBlock();
assert(IDom && "At least the entry block should dominate PN");		assert(IDom && "At least the entry block should dominate PN");

auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());		return dyn_cast<BranchInst>(IDom->getTerminator());
Value Cond = nullptr, LHS = nullptr, *RHS = nullptr;		}
		return nullptr;
		}

if (BI && BI->isConditional() &&		const SCEV ScalarEvolution::createNodeFromSelectLikePHI(PHINode PN) {
BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) &&		const Loop *L = LI.getLoopFor(PN->getParent());
		BranchInst *BI = getSelectPhiBr(PN, L, DT, LI);
		Value Cond = nullptr, LHS = nullptr, *RHS = nullptr;
		if (BI && BI->isConditional() && BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) &&
IsAvailableOnEntry(L, DT, getSCEV(LHS), PN->getParent()) &&		IsAvailableOnEntry(L, DT, getSCEV(LHS), PN->getParent()) &&
IsAvailableOnEntry(L, DT, getSCEV(RHS), PN->getParent()))		IsAvailableOnEntry(L, DT, getSCEV(RHS), PN->getParent()))
return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);		return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);
}

return nullptr;		return nullptr;
}		}

const SCEV ScalarEvolution::createNodeForPHI(PHINode PN) {		const SCEV ScalarEvolution::createNodeForPHI(PHINode PN) {
if (const SCEV *S = createAddRecFromPHI(PN))		if (const SCEV *S = createAddRecFromPHI(PN))
return S;		return S;

▲ Show 20 Lines • Show All 66 Lines • ▼ Show 20 Lines	const SCEV *ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
case ICmpInst::ICMP_SGT:		case ICmpInst::ICMP_SGT:
case ICmpInst::ICMP_SGE:		case ICmpInst::ICMP_SGE:
case ICmpInst::ICMP_UGT:		case ICmpInst::ICMP_UGT:
case ICmpInst::ICMP_UGE:		case ICmpInst::ICMP_UGE:
// a > b ? a+x : b+x -> max(a, b)+x		// a > b ? a+x : b+x -> max(a, b)+x
// a > b ? b+x : a+x -> min(a, b)+x		// a > b ? b+x : a+x -> min(a, b)+x
if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType())) {		if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType())) {
bool Signed = ICI->isSigned();		bool Signed = ICI->isSigned();
		// TODO: Use getExistingSCEV!
const SCEV *LA = getSCEV(TrueVal);		const SCEV *LA = getSCEV(TrueVal);
const SCEV *RA = getSCEV(FalseVal);		const SCEV *RA = getSCEV(FalseVal);
const SCEV *LS = getSCEV(LHS);		const SCEV *LS = getSCEV(LHS);
const SCEV *RS = getSCEV(RHS);		const SCEV *RS = getSCEV(RHS);
if (LA->getType()->isPointerTy()) {		if (LA->getType()->isPointerTy()) {
// FIXME: Handle cases where LS/RS are pointers not equal to LA/RA.		// FIXME: Handle cases where LS/RS are pointers not equal to LA/RA.
// Need to make sure we can't produce weird expressions involving		// Need to make sure we can't produce weird expressions involving
// negated pointers.		// negated pointers.
▲ Show 20 Lines • Show All 1,147 Lines • ▼ Show 20 Lines

bool ScalarEvolution::loopIsFiniteByAssumption(const Loop *L) {		bool ScalarEvolution::loopIsFiniteByAssumption(const Loop *L) {
// A mustprogress loop without side effects must be finite.		// A mustprogress loop without side effects must be finite.
// TODO: The check used here is very conservative. It's only specific		// TODO: The check used here is very conservative. It's only specific
// side effects which are well defined in infinite loops.		// side effects which are well defined in infinite loops.
return isFinite(L) \|\| (isMustProgress(L) && loopHasNoSideEffects(L));		return isFinite(L) \|\| (isMustProgress(L) && loopHasNoSideEffects(L));
}		}

		const SCEV ScalarEvolution::createSCEVIter(Value V) {
		SmallVector<std::pair<Value *, bool>> Stack;
		SmallVector<Value *> Worklist;
		SmallPtrSet<Value *, 8> Visited;

		Stack.emplace_back(V, true);
		Stack.emplace_back(V, false);
		while (!Stack.empty()) {
		std::pair<Value *, bool> E = Stack.pop_back_val();
		if (E.second) {
		auto *S = getExistingSCEV(E.first);
		if (!S) {
		S = createSCEV(E.first);
		// During PHI resolution, it is possible to create two SCEVs for the
		// same V, so it is needed to double check whether V->S is inserted into
		// ValueExprMap before insert S->{V, 0} into ExprValueMap.
		std::pair<ValueExprMapType::iterator, bool> Pair =
		ValueExprMap.insert({SCEVCallbackVH(E.first, this), S});
		if (Pair.second)
		ExprValueMap[S].insert(E.first);
		}
		} else {
		if (!Visited.insert(E.first).second \|\| getExistingSCEV(E.first))
		continue;
		SmallVector<Value *> Ops;
		getOperandsToCreate(E.first, Ops);
		Stack.emplace_back(E.first, true);
		for (Value *Op : Ops) {
		Stack.emplace_back(Op, false);
		}
		}
		}

		return getExistingSCEV(V);
		}
		void ScalarEvolution::getOperandsToCreate(Value *V,
		SmallVectorImpl<Value *> &Ops) {
		if (!isSCEVable(V->getType()))
		return;

		if (Instruction *I = dyn_cast<Instruction>(V)) {
		// Don't attempt to analyze instructions in blocks that aren't
		// reachable. Such instructions don't matter, and they aren't required
		// to obey basic rules for definitions dominating uses which this
		// analysis depends on.
		if (!DT.isReachableFromEntry(I->getParent()))
		return;
		} else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
		return;
		else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
		if (!GA->isInterposable())
		Ops.push_back(GA->getAliasee());
		return;
		nlopesUnsubmitted Done Reply Inline Actions Poison, poison! :) nlopes: Poison, poison! :)
		fhahnAuthorUnsubmitted Done Reply Inline Actions This is unrelated to this patch, I created D128586. I'll update things here once/if D128586 goes in fhahn: This is unrelated to this patch, I created D128586. I'll update things here once/if D128586…
		} else if (!isa<ConstantExpr>(V))
		return;

		Operator *U = cast<Operator>(V);
		if (auto BO = MatchBinaryOp(U, DT)) {
		Ops.push_back(BO->LHS);
		Ops.push_back(BO->RHS);
		return;
		}

		switch (U->getOpcode()) {
		case Instruction::Trunc:
		case Instruction::ZExt:
		case Instruction::SExt:
		case Instruction::PtrToInt:
		Ops.push_back(U->getOperand(0));
		return;

		case Instruction::BitCast:
		if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) {
		Ops.push_back(U->getOperand(0));
		return;
		}
		break;

		case Instruction::SDiv:
		case Instruction::SRem:
		Ops.push_back(U->getOperand(0));
		Ops.push_back(U->getOperand(1));
		return;

		case Instruction::GetElementPtr:
		nikicUnsubmitted Done Reply Inline Actions Add and mul currently have special code that tries to combine multiple sequential adds/mul into one getAddExpr/getMulExpr call. This is effectively lost here (or maybe worse, we end up doing both -- each add individually here, and then a multiple-add variant in getSCEV). I think if we're going to change this (which might well make sense), we should probably change that separately, and also in the createSCEV() code as well. I suspect that this might account for both some of the codegen changes and some of the compile-time impact. nikic: Add and mul currently have special code that tries to combine multiple sequential adds/mul into…
		fhahnAuthorUnsubmitted Done Reply Inline Actions Thanks, I updated `getOperandsToCreate` to also traverse mul/add chains. This indeed removed the `IndVarSimplify` changes and improved compile-time a bit. We could go even further and enqueue (Opcode, Operands) tuples to create directly, instead of going through `createSCEV`, but this would require a way to encode at least negations for the Add case. fhahn: Thanks, I updated `getOperandsToCreate` to also traverse mul/add chains. This indeed removed…
		if (cast<GEPOperator>(U)->getSourceElementType()->isSized()) {
		for (Value *Index : U->operands())
		Ops.push_back(Index);
		}
		return;

		case Instruction::IntToPtr:
		return;

		case Instruction::PHI: {
		auto *PN = cast<PHINode>(U);
		const Loop *L = LI.getLoopFor(PN->getParent());
		Value BEValueV, StartValueV;
		std::tie(StartValueV, BEValueV) = classifyPhiValues(PN, L);

		auto GetFoo = [&]() -> Value * {
		if (!BEValueV \|\| !StartValueV)
		return nullptr;
		auto BO = MatchBinaryOp(BEValueV, DT);
		if (!BO)
		return nullptr;

		if (BO->Opcode != Instruction::Add)
		return nullptr;

		if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
		nikicUnsubmitted Done Reply Inline Actions https://github.com/llvm/llvm-project/commit/327307d9d4da0045f762f75343fe66b0f10ecc63 ;) nikic: https://github.com/llvm/llvm-project/commit/327307d9d4da0045f762f75343fe66b0f10ecc63 ;)
		fhahnAuthorUnsubmitted Done Reply Inline Actions Replace with an assert fhahn: Replace with an assert
		return BO->RHS;
		else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
		return BO->LHS;
		return nullptr;
		};

		if (auto *Acc = GetFoo()) {
		Ops.push_back(StartValueV);
		Ops.push_back(Acc);
		return;
		}
		BranchInst *BI = getSelectPhiBr(PN, L, DT, LI);
		Value Cond = nullptr, LHS = nullptr, *RHS = nullptr;
		if (BI && BI->isConditional() &&
		BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS)) {
		Ops.push_back(LHS);
		Ops.push_back(RHS);
		return;
		}
		return;
		}

		case Instruction::Select:
		// U can also be a select constant expr, which let fall through. Since
		// createNodeForSelect only works for a condition that is an `ICmpInst`, and
		// constant expressions cannot have instructions as operands, we'd have
		// returned getUnknown for a select constant expressions anyway.
		if (isa<Instruction>(U)) {
		for (Value *Inc : cast<Instruction>(U)->operands())
		Ops.push_back(Inc);
		return;
		}
		break;

		case Instruction::Call:
		case Instruction::Invoke:
		if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand()) {
		Ops.push_back(RV);
		return;
		}

		if (auto *II = dyn_cast<IntrinsicInst>(U)) {
		switch (II->getIntrinsicID()) {
		case Intrinsic::abs:
		Ops.push_back(II->getArgOperand(0));
		return;
		case Intrinsic::umax:
		case Intrinsic::umin:
		case Intrinsic::smax:
		case Intrinsic::smin:
		case Intrinsic::usub_sat:
		case Intrinsic::uadd_sat:
		Ops.push_back(II->getArgOperand(0));
		Ops.push_back(II->getArgOperand(1));
		return;
		case Intrinsic::start_loop_iterations:
		Ops.push_back(II->getArgOperand(0));
		return;
		default:
		break;
		nikicUnsubmitted Done Reply Inline Actions I don't think this is strictly true due to the createNodeForSelectViaUMinSeq() code. And either way, I don't think we need to handle it this precisely here. nikic: I don't think this is strictly true due to the createNodeForSelectViaUMinSeq() code. And either…
		fhahnAuthorUnsubmitted Done Reply Inline Actions Thanks, I removed the check for Instruction to simplify things here. fhahn: Thanks, I removed the check for Instruction to simplify things here.
		}
		}
		break;
		}

		return;
		}

const SCEV ScalarEvolution::createSCEV(Value V) {		const SCEV ScalarEvolution::createSCEV(Value V) {
if (!isSCEVable(V->getType()))		if (!isSCEVable(V->getType()))
return getUnknown(V);		return getUnknown(V);

if (Instruction *I = dyn_cast<Instruction>(V)) {		if (Instruction *I = dyn_cast<Instruction>(V)) {
// Don't attempt to analyze instructions in blocks that aren't		// Don't attempt to analyze instructions in blocks that aren't
// reachable. Such instructions don't matter, and they aren't required		// reachable. Such instructions don't matter, and they aren't required
// to obey basic rules for definitions dominating uses which this		// to obey basic rules for definitions dominating uses which this
▲ Show 20 Lines • Show All 7,362 Lines • Show Last 20 Lines