Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

Differential D63477 Diff 205493 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

Changeset View

Standalone View

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

Show First 20 Lines • Show All 1,903 Lines • ▼ Show 20 Lines
};		};

/// This class holds state for the main loop strength reduction logic.		/// This class holds state for the main loop strength reduction logic.
class LSRInstance {		class LSRInstance {
IVUsers &IU;		IVUsers &IU;
ScalarEvolution &SE;		ScalarEvolution &SE;
DominatorTree &DT;		DominatorTree &DT;
LoopInfo &LI;		LoopInfo &LI;
		AssumptionCache &AC;
		TargetLibraryInfo &LibInfo;
const TargetTransformInfo &TTI;		const TargetTransformInfo &TTI;
Loop *const L;		Loop *const L;
bool FavorBackedgeIndex = false;		bool FavorBackedgeIndex = false;
bool Changed = false;		bool Changed = false;

/// This is the insert position that the current loop's induction variable		/// This is the insert position that the current loop's induction variable
/// increment should be placed. In simple loops, this is the latch block's		/// increment should be placed. In simple loops, this is the latch block's
/// terminator. But in more complicated cases, this is a position which will		/// terminator. But in more complicated cases, this is a position which will
▲ Show 20 Lines • Show All 122 Lines • ▼ Show 20 Lines	void RewriteForPHI(PHINode *PN, const LSRUse &LU, const LSRFixup &LF,
SmallVectorImpl<WeakTrackingVH> &DeadInsts) const;		SmallVectorImpl<WeakTrackingVH> &DeadInsts) const;
void Rewrite(const LSRUse &LU, const LSRFixup &LF, const Formula &F,		void Rewrite(const LSRUse &LU, const LSRFixup &LF, const Formula &F,
SCEVExpander &Rewriter,		SCEVExpander &Rewriter,
SmallVectorImpl<WeakTrackingVH> &DeadInsts) const;		SmallVectorImpl<WeakTrackingVH> &DeadInsts) const;
void ImplementSolution(const SmallVectorImpl<const Formula *> &Solution);		void ImplementSolution(const SmallVectorImpl<const Formula *> &Solution);

public:		public:
LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE, DominatorTree &DT,		LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE, DominatorTree &DT,
LoopInfo &LI, const TargetTransformInfo &TTI);		LoopInfo &LI, const TargetTransformInfo &TTI, AssumptionCache &AC,
		TargetLibraryInfo &LibInfo);

bool getChanged() const { return Changed; }		bool getChanged() const { return Changed; }

void print_factors_and_types(raw_ostream &OS) const;		void print_factors_and_types(raw_ostream &OS) const;
void print_fixups(raw_ostream &OS) const;		void print_fixups(raw_ostream &OS) const;
void print_uses(raw_ostream &OS) const;		void print_uses(raw_ostream &OS) const;
void print(raw_ostream &OS) const;		void print(raw_ostream &OS) const;
void dump() const;		void dump() const;
▲ Show 20 Lines • Show All 1,168 Lines • ▼ Show 20 Lines	for (PHINode &Phi : L->getHeader()->phis()) {
}		}
Phi.replaceUsesOfWith(PostIncV, IVOper);		Phi.replaceUsesOfWith(PostIncV, IVOper);
DeadInsts.emplace_back(PostIncV);		DeadInsts.emplace_back(PostIncV);
}		}
}		}
}		}

void LSRInstance::CollectFixupsAndInitialFormulae() {		void LSRInstance::CollectFixupsAndInitialFormulae() {
		BranchInst *ExitBranch = nullptr;

for (const IVStrideUse &U : IU) {		for (const IVStrideUse &U : IU) {
Instruction *UserInst = U.getUser();		Instruction *UserInst = U.getUser();
// Skip IV users that are part of profitable IV Chains.		// Skip IV users that are part of profitable IV Chains.
User::op_iterator UseI =		User::op_iterator UseI =
find(UserInst->operands(), U.getOperandValToReplace());		find(UserInst->operands(), U.getOperandValToReplace());
assert(UseI != UserInst->op_end() && "cannot find IV operand");		assert(UseI != UserInst->op_end() && "cannot find IV operand");
if (IVIncSet.count(UseI)) {		if (IVIncSet.count(UseI)) {
LLVM_DEBUG(dbgs() << "Use is in profitable chain: " << **UseI << '\n');		LLVM_DEBUG(dbgs() << "Use is in profitable chain: " << **UseI << '\n');
Show All 13 Lines	for (const IVStrideUse &U : IU) {
// Equality (== and !=) ICmps are special. We can rewrite (i == N) as		// Equality (== and !=) ICmps are special. We can rewrite (i == N) as
// (N - i == 0), and this allows (N - i) to be the expression that we work		// (N - i == 0), and this allows (N - i) to be the expression that we work
// with rather than just N or i, so we can consider the register		// with rather than just N or i, so we can consider the register
// requirements for both N and i at the same time. Limiting this code to		// requirements for both N and i at the same time. Limiting this code to
// equality icmps is not a problem because all interesting loops use		// equality icmps is not a problem because all interesting loops use
// equality icmps, thanks to IndVarSimplify.		// equality icmps, thanks to IndVarSimplify.
if (ICmpInst *CI = dyn_cast<ICmpInst>(UserInst))		if (ICmpInst *CI = dyn_cast<ICmpInst>(UserInst))
if (CI->isEquality()) {		if (CI->isEquality()) {
		// If CI can be saved in some target, like replaced inside hardware loop
		// in PowerPC, no need to generate initial formulae for it.
		bool saveCmp = false;
		hfinkelUnsubmitted Not Done Reply Inline Actions saveCmp -> SaveCmp hfinkel: saveCmp -> SaveCmp
		if (!ExitBranch)
		saveCmp =
		TTI.canSaveCmp(L, &ExitBranch, &SE, &LI, &DT, &AC, &LibInfo);
		if (saveCmp && CI == cast<ICmpInst>(ExitBranch->getCondition()))
		continue;
// Swap the operands if needed to put the OperandValToReplace on the		// Swap the operands if needed to put the OperandValToReplace on the
// left, for consistency.		// left, for consistency.
Value *NV = CI->getOperand(1);		Value *NV = CI->getOperand(1);
if (NV == U.getOperandValToReplace()) {		if (NV == U.getOperandValToReplace()) {
CI->setOperand(1, CI->getOperand(0));		CI->setOperand(1, CI->getOperand(0));
CI->setOperand(0, NV);		CI->setOperand(0, NV);
NV = CI->getOperand(1);		NV = CI->getOperand(1);
Changed = true;		Changed = true;
▲ Show 20 Lines • Show All 2,202 Lines • ▼ Show 20 Lines	#endif
// instructions.		// instructions.
Rewriter.clear();		Rewriter.clear();

Changed \|= DeleteTriviallyDeadInstructions(DeadInsts);		Changed \|= DeleteTriviallyDeadInstructions(DeadInsts);
}		}

LSRInstance::LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE,		LSRInstance::LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE,
DominatorTree &DT, LoopInfo &LI,		DominatorTree &DT, LoopInfo &LI,
const TargetTransformInfo &TTI)		const TargetTransformInfo &TTI, AssumptionCache &AC,
: IU(IU), SE(SE), DT(DT), LI(LI), TTI(TTI), L(L),		TargetLibraryInfo &LibInfo)
		: IU(IU), SE(SE), DT(DT), LI(LI), AC(AC), LibInfo(LibInfo), TTI(TTI), L(L),
FavorBackedgeIndex(EnableBackedgeIndexing &&		FavorBackedgeIndex(EnableBackedgeIndexing &&
TTI.shouldFavorBackedgeIndex(L)) {		TTI.shouldFavorBackedgeIndex(L)) {
// If LoopSimplify form is not available, stay out of trouble.		// If LoopSimplify form is not available, stay out of trouble.
if (!L->isLoopSimplifyForm())		if (!L->isLoopSimplifyForm())
return;		return;

// If there's no interesting work to be done, bail early.		// If there's no interesting work to be done, bail early.
if (IU.empty()) return;		if (IU.empty()) return;
▲ Show 20 Lines • Show All 180 Lines • ▼ Show 20 Lines	void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const {

AU.addRequired<LoopInfoWrapperPass>();		AU.addRequired<LoopInfoWrapperPass>();
AU.addPreserved<LoopInfoWrapperPass>();		AU.addPreserved<LoopInfoWrapperPass>();
AU.addRequiredID(LoopSimplifyID);		AU.addRequiredID(LoopSimplifyID);
AU.addRequired<DominatorTreeWrapperPass>();		AU.addRequired<DominatorTreeWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();		AU.addPreserved<DominatorTreeWrapperPass>();
AU.addRequired<ScalarEvolutionWrapperPass>();		AU.addRequired<ScalarEvolutionWrapperPass>();
AU.addPreserved<ScalarEvolutionWrapperPass>();		AU.addPreserved<ScalarEvolutionWrapperPass>();
		AU.addRequired<AssumptionCacheTracker>();
		AU.addRequired<TargetLibraryInfoWrapperPass>();
// Requiring LoopSimplify a second time here prevents IVUsers from running		// Requiring LoopSimplify a second time here prevents IVUsers from running
// twice, since LoopSimplify was invalidated by running ScalarEvolution.		// twice, since LoopSimplify was invalidated by running ScalarEvolution.
AU.addRequiredID(LoopSimplifyID);		AU.addRequiredID(LoopSimplifyID);
AU.addRequired<IVUsersWrapperPass>();		AU.addRequired<IVUsersWrapperPass>();
AU.addPreserved<IVUsersWrapperPass>();		AU.addPreserved<IVUsersWrapperPass>();
AU.addRequired<TargetTransformInfoWrapperPass>();		AU.addRequired<TargetTransformInfoWrapperPass>();
}		}

static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE,		static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE,
DominatorTree &DT, LoopInfo &LI,		DominatorTree &DT, LoopInfo &LI,
const TargetTransformInfo &TTI) {		const TargetTransformInfo &TTI,
		AssumptionCache &AC,
		TargetLibraryInfo &LibInfo) {

bool Changed = false;		bool Changed = false;

// Run the main LSR transformation.		// Run the main LSR transformation.
Changed \|= LSRInstance(L, IU, SE, DT, LI, TTI).getChanged();		Changed \|= LSRInstance(L, IU, SE, DT, LI, TTI, AC, LibInfo).getChanged();

// Remove any extra phis created by processing inner loops.		// Remove any extra phis created by processing inner loops.
Changed \|= DeleteDeadPHIs(L->getHeader());		Changed \|= DeleteDeadPHIs(L->getHeader());
if (EnablePhiElim && L->isLoopSimplifyForm()) {		if (EnablePhiElim && L->isLoopSimplifyForm()) {
SmallVector<WeakTrackingVH, 16> DeadInsts;		SmallVector<WeakTrackingVH, 16> DeadInsts;
const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();		const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
SCEVExpander Rewriter(SE, DL, "lsr");		SCEVExpander Rewriter(SE, DL, "lsr");
#ifndef NDEBUG		#ifndef NDEBUG
Show All 14 Lines	if (skipLoop(L))
return false;		return false;

auto &IU = getAnalysis<IVUsersWrapperPass>().getIU();		auto &IU = getAnalysis<IVUsersWrapperPass>().getIU();
auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();		auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();		auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();		auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(		const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
*L->getHeader()->getParent());		*L->getHeader()->getParent());
return ReduceLoopStrength(L, IU, SE, DT, LI, TTI);		auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
		*L->getHeader()->getParent());
		auto &LibInfo = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
		return ReduceLoopStrength(L, IU, SE, DT, LI, TTI, AC, LibInfo);
}		}

PreservedAnalyses LoopStrengthReducePass::run(Loop &L, LoopAnalysisManager &AM,		PreservedAnalyses LoopStrengthReducePass::run(Loop &L, LoopAnalysisManager &AM,
LoopStandardAnalysisResults &AR,		LoopStandardAnalysisResults &AR,
LPMUpdater &) {		LPMUpdater &) {
if (!ReduceLoopStrength(&L, AM.getResult<IVUsersAnalysis>(L, AR), AR.SE,		if (!ReduceLoopStrength(&L, AM.getResult<IVUsersAnalysis>(L, AR), AR.SE,
AR.DT, AR.LI, AR.TTI))		AR.DT, AR.LI, AR.TTI, AR.AC, AR.TLI))
return PreservedAnalyses::all();		return PreservedAnalyses::all();

return getLoopPassPreservedAnalyses();		return getLoopPassPreservedAnalyses();
}		}

char LoopStrengthReduce::ID = 0;		char LoopStrengthReduce::ID = 0;

INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce",		INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce",
Show All 11 Lines