Differential D87494 Diff 293657 llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

Changeset View

Standalone View

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

Show First 20 Lines • Show All 53 Lines • ▼ Show 20 Lines

#include "llvm/Transforms/Scalar/LoopStrengthReduce.h"		#include "llvm/Transforms/Scalar/LoopStrengthReduce.h"
#include "llvm/ADT/APInt.h"		#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"		#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"		#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Hashing.h"		#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/PointerIntPair.h"		#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"		#include "llvm/ADT/STLExtras.h"
		#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"		#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallBitVector.h"		#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallPtrSet.h"		#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"		#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"		#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"		#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AssumptionCache.h"		#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/IVUsers.h"		#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/LoopAnalysisManager.h"		#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"		#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"		#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"		#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"		#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"		#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"		#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionNormalization.h"		#include "llvm/Analysis/ScalarEvolutionNormalization.h"
#include "llvm/Analysis/TargetTransformInfo.h"		#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Config/llvm-config.h"		#include "llvm/Config/llvm-config.h"
#include "llvm/IR/BasicBlock.h"		#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"		#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"		#include "llvm/IR/Constants.h"
		#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DerivedTypes.h"		#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"		#include "llvm/IR/Dominators.h"
#include "llvm/IR/GlobalValue.h"		#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/IRBuilder.h"		#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"		#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"		#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"		#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"		#include "llvm/IR/IntrinsicInst.h"
▲ Show 20 Lines • Show All 5,679 Lines • ▼ Show 20 Lines	static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE,
AssumptionCache &AC, TargetLibraryInfo &TLI,		AssumptionCache &AC, TargetLibraryInfo &TLI,
MemorySSA *MSSA) {		MemorySSA *MSSA) {

bool Changed = false;		bool Changed = false;
std::unique_ptr<MemorySSAUpdater> MSSAU;		std::unique_ptr<MemorySSAUpdater> MSSAU;
if (MSSA)		if (MSSA)
MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);		MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);

		// Debug preservation - record all llvm.dbg.value from the loop as well as
		// the SCEV of their variable location. Since salvageDebugInfo may change the
		// DIExpression we need to store the original here as well (i.e. it needs to
		// be in sync with the SCEV).
		SmallVector<std::tuple<DbgValueInst , const SCEV , DIExpression *>, 32>
		DbgValues;
		for (auto &B : L->getBlocks()) {
		for (auto &I : *B) {
		Lint: Pre-merge checks Inline Actions clang-tidy: warning: 'auto &B' can be declared as 'const auto &B' [llvm-qualified-auto] not useful Lint: Pre-merge checks: clang-tidy: warning: 'auto &B' can be declared as 'const auto &B' [llvm-qualified-auto] [[https…
		if (DbgValueInst *D = dyn_cast<DbgValueInst>(&I)) {
		auto V = D->getVariableLocation();
		if (!SE.isSCEVable(V->getType()))
		Lint: Pre-merge checks Inline Actions clang-tidy: warning: 'auto V' can be declared as 'auto V' [llvm-qualified-auto] not useful Lint: Pre-merge checks:* clang-tidy: warning: 'auto V' can be declared as 'auto *V' [llvm-qualified-auto] [[https…
		continue;
		auto DS = SE.getSCEV(V);
		DbgValues.push_back(std::make_tuple(D, DS, D->getExpression()));
		Lint: Pre-merge checks Inline Actions clang-tidy: warning: 'auto DS' can be declared as 'const auto DS' [llvm-qualified-auto] not useful Lint: Pre-merge checks:* clang-tidy: warning: 'auto DS' can be declared as 'const auto *DS' [llvm-qualified-auto]…
		}
		jmorseUnsubmitted Not Done Reply Inline Actions Can this be brace initialized? jmorse: Can this be brace initialized?
		markusAuthorUnsubmitted Done Reply Inline Actions Quite possibly but I seem to be unable to pull it off :) markus: Quite possibly but I seem to be unable to pull it off :)
		}
		}
		saugustineUnsubmitted Not Done Reply Inline Actions Someone reverted this change while I was tracking down a segfault related to it, but the problem is with this line. Sometimes D->getVariableLocation() returns null because a variable's location has been lost or can't be found. A simple fix would be a null check on this line: if (!V \|\| !SE.isSCEVable(V->getType()))) saugustine: Someone reverted this change while I was tracking down a segfault related to it, but the…

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

// Remove any extra phis created by processing inner loops.		// Remove any extra phis created by processing inner loops.
Changed \|= DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get());		Changed \|= DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get());
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", false);		SCEVExpander Rewriter(SE, DL, "lsr", false);
#ifndef NDEBUG		#ifndef NDEBUG
Rewriter.setDebugType(DEBUG_TYPE);		Rewriter.setDebugType(DEBUG_TYPE);
#endif		#endif
unsigned numFolded = Rewriter.replaceCongruentIVs(L, &DT, DeadInsts, &TTI);		unsigned numFolded = Rewriter.replaceCongruentIVs(L, &DT, DeadInsts, &TTI);
if (numFolded) {		if (numFolded) {
Changed = true;		Changed = true;
RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts, &TLI,		RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts, &TLI,
MSSAU.get());		MSSAU.get());
DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get());		DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get());
}		}
		aprantlUnsubmitted Not Done Reply Inline Actions either we check the result or this should be `auto UseOfI = cast<Instruction>()` aprantl:* either we check the result or this should be `auto *UseOfI = cast<Instruction>()`
}		}
		// Debug preservation - go through all recorded llvm.dbg.value and for those
		// that now have an undef variable location use the recorded SCEV to try and
		// update it. Compare with SCEV of Phi-nodes of loop header to find a
		// suitable update candidate. SCEV match with constant offset is allowed and
		// will be compensated for in the DIExpression.
		if (Changed) {
		for (auto &D : DbgValues) {
		auto DbgValue = std::get<DbgValueInst *>(D);
		auto DbgValueSCEV = std::get<const SCEV *>(D);
		Lint: Pre-merge checks Inline Actions clang-tidy: warning: 'auto DbgValue' can be declared as 'auto DbgValue' [llvm-qualified-auto] not useful Lint: Pre-merge checks:* clang-tidy: warning: 'auto DbgValue' can be declared as 'auto *DbgValue' [llvm-qualified-auto]…
		auto DbgDIExpr = std::get<DIExpression *>(D);
		Lint: Pre-merge checks Inline Actions clang-tidy: warning: 'auto DbgValueSCEV' can be declared as 'const auto DbgValueSCEV' [llvm-qualified-auto] not useful Lint: Pre-merge checks:* clang-tidy: warning: 'auto DbgValueSCEV' can be declared as 'const auto *DbgValueSCEV' [llvm…
		if (!isa<UndefValue>(DbgValue->getVariableLocation()))
		Lint: Pre-merge checks Inline Actions clang-tidy: warning: 'auto DbgDIExpr' can be declared as 'auto DbgDIExpr' [llvm-qualified-auto] not useful Lint: Pre-merge checks:* clang-tidy: warning: 'auto DbgDIExpr' can be declared as 'auto *DbgDIExpr' [llvm-qualified…
		continue;
		jmorseUnsubmitted Done Reply Inline Actions if (!isa<...>(...)) continue;` To save some indentation. jmorse: if (!isa<...>(...)) continue;` To save some indentation.
		for (PHINode &Phi : L->getHeader()->phis()) {
		if (!SE.isSCEVable(Phi.getType()))
		continue;
		auto PhiSCEV = SE.getSCEV(&Phi);
		if (Optional<APInt> Offset =
		Lint: Pre-merge checks Inline Actions clang-tidy: warning: 'auto PhiSCEV' can be declared as 'const auto PhiSCEV' [llvm-qualified-auto] not useful Lint: Pre-merge checks:* clang-tidy: warning: 'auto PhiSCEV' can be declared as 'const auto *PhiSCEV' [llvm-qualified…
		SE.computeConstantDifference(DbgValueSCEV, PhiSCEV)) {
		auto &Ctx = DbgValue->getContext();
		DbgValue->setOperand(
		0, MetadataAsValue::get(Ctx, ValueAsMetadata::get(&Phi)));
		if (Offset.getValue().getSExtValue()) {
		SmallVector<uint64_t, 8> Ops;
		DIExpression::appendOffset(Ops, Offset.getValue().getSExtValue());
		DbgDIExpr = DIExpression::prependOpcodes(DbgDIExpr, Ops, true);
		}
		DbgValue->setOperand(2, MetadataAsValue::get(Ctx, DbgDIExpr));
		}
		}
		}
		}
return Changed;		return Changed;
}		}

bool LoopStrengthReduce::runOnLoop(Loop L, LPPassManager & /LPM*/) {		bool LoopStrengthReduce::runOnLoop(Loop L, LPPassManager & /LPM*/) {
if (skipLoop(L))		if (skipLoop(L))
return false;		return false;

auto &IU = getAnalysis<IVUsersWrapperPass>().getIU();		auto &IU = getAnalysis<IVUsersWrapperPass>().getIU();
Show All 12 Lines	if (MSSAAnalysis)
MSSA = &MSSAAnalysis->getMSSA();		MSSA = &MSSAAnalysis->getMSSA();
return ReduceLoopStrength(L, IU, SE, DT, LI, TTI, AC, TLI, MSSA);		return ReduceLoopStrength(L, IU, SE, DT, LI, TTI, AC, TLI, MSSA);
}		}

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.AC, AR.TLI, AR.MSSA))		AR.DT, AR.LI, AR.TTI, AR.AC, AR.TLI, AR.MSSA))
		markusAuthorUnsubmitted Done Reply Inline Actions There must be a better way to get hold of these. I would assume that LSR itself keeps track of the phi-node instructions it builds markus: There must be a better way to get hold of these. I would assume that LSR itself keeps track of…
return PreservedAnalyses::all();		return PreservedAnalyses::all();

auto PA = getLoopPassPreservedAnalyses();		auto PA = getLoopPassPreservedAnalyses();
if (AR.MSSA)		if (AR.MSSA)
PA.preserve<MemorySSAAnalysis>();		PA.preserve<MemorySSAAnalysis>();
return PA;		return PA;
		markusAuthorUnsubmitted Done Reply Inline Actions There must be a better way to do this. Perhaps we can modify `DeleteDeadPHIs` to accept an additional `std::function` argument that replaces the `salvageDebugInfo` call. It would still default to `salvageDebugInfo` but would allow us to pass a lambda here that does the SCEV comparison (and possible replace) on the dbg-uses right before an instruction is about to be removed. markus: There must be a better way to do this. Perhaps we can modify `DeleteDeadPHIs` to accept an…
		markusAuthorUnsubmitted Done Reply Inline Actions Actually I see that commit `37b96d51d0cfc82a64598aaae2a567fa77e44de9` introduced a `AboutToDeleteCallback` that seem to serve exactly this purpose. We just need to expose it a bit further up in `DeleteDeadPHIs`. markus: Actually I see that commit `37b96d51d0cfc82a64598aaae2a567fa77e44de9` introduced a…
}		}

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

INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce",		INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce",
"Loop Strength Reduction", false, false)		"Loop Strength Reduction", false, false)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)		INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)		INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)		INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_DEPENDENCY(IVUsersWrapperPass)		INITIALIZE_PASS_DEPENDENCY(IVUsersWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)		INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)		INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_END(LoopStrengthReduce, "loop-reduce",		INITIALIZE_PASS_END(LoopStrengthReduce, "loop-reduce",
"Loop Strength Reduction", false, false)		"Loop Strength Reduction", false, false)

Pass *llvm::createLoopStrengthReducePass() { return new LoopStrengthReduce(); }		Pass *llvm::createLoopStrengthReducePass() { return new LoopStrengthReduce(); }