Differential D93734 Diff 319447 llvm/lib/Transforms/Scalar/LoopDeletion.cpp

Changeset View

Standalone View

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

Show All 26 Lines
#include "llvm/Transforms/Scalar/LoopPassManager.h"		#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/LoopUtils.h"		#include "llvm/Transforms/Utils/LoopUtils.h"

using namespace llvm;		using namespace llvm;

#define DEBUG_TYPE "loop-delete"		#define DEBUG_TYPE "loop-delete"

STATISTIC(NumDeleted, "Number of loops deleted");		STATISTIC(NumDeleted, "Number of loops deleted");
		STATISTIC(NumEarlyExits, "Number of early exits inserted");
		STATISTIC(NumLoopsElim, "Number of loops eliminated (no remaining blocks)");
		STATISTIC(NumSCEV0Skipped, "Number of skipped loops (SCEV 0)");

enum class LoopDeletionResult {		enum class LoopDeletionResult {
Unmodified,		Unmodified,
Modified,		Modified,
Deleted,		Deleted,
};		};


static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) {		static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) {
if (A == LoopDeletionResult::Deleted \|\| B == LoopDeletionResult::Deleted)		if (A == LoopDeletionResult::Deleted \|\| B == LoopDeletionResult::Deleted)
return LoopDeletionResult::Deleted;		return LoopDeletionResult::Deleted;
if (A == LoopDeletionResult::Modified \|\| B == LoopDeletionResult::Modified)		if (A == LoopDeletionResult::Modified \|\| B == LoopDeletionResult::Modified)
return LoopDeletionResult::Modified;		return LoopDeletionResult::Modified;
return LoopDeletionResult::Unmodified;		return LoopDeletionResult::Unmodified;
}		}

		static bool BBHasSideEffects(const BasicBlock *BB) {
		if (any_of(*BB, [](const Instruction &I) {
		return I.mayHaveSideEffects() && !I.isDroppable();
		}))
		return true;
		return false;
		}

/// Determines if a loop is dead.		/// Determines if a loop is dead.
///		///
/// This assumes that we've already checked for unique exit and exiting blocks,		/// This assumes that we've already checked for unique exit and exiting blocks,
/// and that the code is in LCSSA form.		/// and that the code is in LCSSA form.
static bool isLoopDead(Loop *L, ScalarEvolution &SE,		static bool isLoopDead(Loop *L, ScalarEvolution &SE,
SmallVectorImpl<BasicBlock *> &ExitingBlocks,		SmallVectorImpl<BasicBlock *> &ExitingBlocks,
BasicBlock *ExitBlock, bool &Changed,		BasicBlock *ExitBlock, bool &Changed,
BasicBlock *Preheader) {		BasicBlock *Preheader) {
Show All 33 Lines	static bool isLoopDead(Loop *L, ScalarEvolution &SE,

if (!AllEntriesInvariant \|\| !AllOutgoingValuesSame)		if (!AllEntriesInvariant \|\| !AllOutgoingValuesSame)
return false;		return false;

// Make sure that no instructions in the block have potential side-effects.		// Make sure that no instructions in the block have potential side-effects.
// This includes instructions that could write to memory, and loads that are		// This includes instructions that could write to memory, and loads that are
// marked volatile.		// marked volatile.
for (auto &I : L->blocks())		for (auto &I : L->blocks())
if (any_of(*I, [](Instruction &I) {		if (BBHasSideEffects(I))
		jdoerfertUnsubmitted Not Done Reply Inline Actions DriveBy: This hurts. I know it was there before but `auto &I` is `BasicBlock `... argh. Could we please change that if we commit this to a `auto ` at least with a sensible variable name. jdoerfert: DriveBy: This hurts. I know it was there before but `auto &I` is `BasicBlock *`... argh. Could…
		jonpaAuthorUnsubmitted Done Reply Inline Actions I think it's better in that case perhaps to just commit such an NFC change separately beforehand? jonpa: I think it's better in that case perhaps to just commit such an NFC change separately…
		jdoerfertUnsubmitted Not Done Reply Inline Actions Yeah, stuff like that can be committed directly as NFC. jdoerfert: Yeah, stuff like that can be committed directly as NFC.
return I.mayHaveSideEffects() && !I.isDroppable();
}))
return false;		return false;
return true;		return true;
}		}

/// This function returns true if there is no viable path from the		/// This function returns true if there is no viable path from the
/// entry block to the header of \p L. Right now, it only does		/// entry block to the header of \p L. Right now, it only does
/// a local search to save compile time.		/// a local search to save compile time.
static bool isLoopNeverExecuted(Loop *L) {		static bool isLoopNeverExecuted(Loop *L) {
Show All 20 Lines	if (Taken == Preheader)
return false;		return false;
}		}
assert(!pred_empty(Preheader) &&		assert(!pred_empty(Preheader) &&
"Preheader should have predecessors at this point!");		"Preheader should have predecessors at this point!");
// All the predecessors have the loop preheader as not-taken target.		// All the predecessors have the loop preheader as not-taken target.
return true;		return true;
}		}

		static bool loopMustProgress(Loop *L) {
		return L->getHeader()->getParent()->mustProgress() \|\| hasMustProgress(L);
		}
		jdoerfertUnsubmitted Not Done Reply Inline Actions Nit: Unrelated and misses documentation. A useful helper though, could be added to D86844 directly (if you don't mind). jdoerfert: Nit: Unrelated and misses documentation. A useful helper though, could be added to D86844…

/// If we can prove the backedge is untaken, remove it. This destroys the		/// If we can prove the backedge is untaken, remove it. This destroys the
/// loop, but leaves the (now trivially loop invariant) control flow and		/// loop, but leaves the (now trivially loop invariant) control flow and
/// side effects (if any) in place.		/// side effects (if any) in place.
static LoopDeletionResult		static LoopDeletionResult
breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE,		breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
LoopInfo &LI, MemorySSA *MSSA,		LoopInfo &LI, MemorySSA *MSSA,
OptimizationRemarkEmitter &ORE) {		OptimizationRemarkEmitter &ORE) {
assert(L->isLCSSAForm(DT) && "Expected LCSSA!");		assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
▲ Show 20 Lines • Show All 82 Lines • ▼ Show 20 Lines	if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {
LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");		LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
return Changed ? LoopDeletionResult::Modified		return Changed ? LoopDeletionResult::Modified
: LoopDeletionResult::Unmodified;		: LoopDeletionResult::Unmodified;
}		}

// Don't remove loops for which we can't solve the trip count unless the loop		// Don't remove loops for which we can't solve the trip count unless the loop
// was required to make progress but has been determined to be dead.		// was required to make progress but has been determined to be dead.
const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);		const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(S) &&		if (isa<SCEVCouldNotCompute>(S) && !loopMustProgress(L)) {
!L->getHeader()->getParent()->mustProgress() && !hasMustProgress(L)) {
LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "		LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
"not required to make progress.\n");		"not required to make progress.\n");
return Changed ? LoopDeletionResult::Modified		return Changed ? LoopDeletionResult::Modified
: LoopDeletionResult::Unmodified;		: LoopDeletionResult::Unmodified;
}		}

LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");		LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
ORE.emit([&]() {		ORE.emit([&]() {
return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),		return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
L->getHeader())		L->getHeader())
<< "Loop deleted because it is invariant";		<< "Loop deleted because it is invariant";
});		});
deleteDeadLoop(L, &DT, &SE, &LI, MSSA);		deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
++NumDeleted;		++NumDeleted;

return LoopDeletionResult::Deleted;		return LoopDeletionResult::Deleted;
}		}

		static bool usesLoopPHI(const Instruction I, const Loop L) {
		if (!L->contains(I->getParent()))
		return false;
		if (isa<PHINode>(I))
		return true;
		for (auto &Op : I->operands())
		if (const Instruction *OpI = dyn_cast<Instruction>(&Op))
		if (usesLoopPHI(OpI, L))
		return true;
		return false;
		}

		static bool BBHasLIVCondOnDeadPath(const BasicBlock BB, Loop L) {
		// Check if the condition might change after an iteration across a dead
		// path. TODO: worth checking if incoming value from preheader/latch are
		// the same and allow that case?
		const Instruction *TI = BB->getTerminator();
		const Instruction *Cond = nullptr;
		if (const BranchInst *BI = dyn_cast<BranchInst>(TI)) {
		if (BI->isConditional())
		Cond = dyn_cast<Instruction>(BI->getCondition());
		} else if (const SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
		Cond = dyn_cast<Instruction>(SI->getCondition());
		} else
		return false;
		return (Cond == nullptr \|\| !usesLoopPHI(Cond, L));
		}

		static bool hasPredecessorInLoop(const BasicBlock BB, Loop L) {
		for (auto *Pred: predecessors(BB))
		if (L->contains(Pred))
		return true;
		return false;
		}

		static bool hasSuccessorInLoop(const BasicBlock BB, Loop L) {
		for (auto *Succ: successors(BB))
		if (L->contains(Succ))
		return true;
		return false;
		}

		static void findNoSEBlocks(SmallPtrSet<BasicBlock *, 4> &NoSEBBs,
		jdoerfertUnsubmitted Not Done Reply Inline Actions that reminds me, we really need to make `llvm.assume` side-effect free... D89054 jdoerfert: that reminds me, we really need to make `llvm.assume` side-effect free... D89054
		Loop *L, bool Forward) {
		auto takeBlock = [&L, &Forward](BasicBlock *BB) -> bool {
		return !BBHasSideEffects(BB) && (!Forward \|\| BBHasLIVCondOnDeadPath(BB, L));
		};

		BasicBlock *Header = L->getHeader();
		BasicBlock *Latch = L->getLoopLatch();
		BasicBlock *Start = Forward ? Header : Latch;
		if (!takeBlock(Start))
		return;
		NoSEBBs.insert(Start);

		bool Change = true;
		while (Change) {
		Change = false;
		for (auto BB : L->getBlocks()) {
		if (NoSEBBs.count(BB) \|\| !takeBlock(BB))
		continue;

		bool All = true;
		if (Forward) {
		for (auto *Pred: predecessors(BB))
		if (!NoSEBBs.count(Pred)) {
		All = false;
		break;
		}
		} else {
		for (auto *Succ: successors(BB))
		if (L->contains(Succ) && !NoSEBBs.count(Succ)) {
		All = false;
		break;
		}
		}
		if (All) {
		NoSEBBs.insert(BB);
		Change = true;
		}
		}
		}
		}

		// Return the exit block on the path from BB to the backedge. If there is
		// none, return the unique exit block if it exists. If there are more than
		// one, return null. Make sure there are no live-out values.
		static BasicBlock findExitBlock(const BasicBlock BB, Loop *L) {
		BasicBlock *ExitBB = L->getUniqueExitBlock();

		if (!ExitBB) {
		SmallVector<const BasicBlock *, 4> WorkList;
		WorkList.push_back(BB);
		SmallPtrSet<const BasicBlock *, 4> Visited;
		while (!WorkList.empty()) {
		const BasicBlock *CurrBB = WorkList.pop_back_val();
		if (!Visited.insert(CurrBB).second)
		continue;

		const Instruction *TI = CurrBB->getTerminator();
		for (unsigned i = 0, e = TI->getNumOperands(); i != e; ++i)
		if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(TI->getOperand(i))) {
		if (!L->contains(SuccBB)) {
		if (ExitBB != nullptr && ExitBB != SuccBB)
		return nullptr;
		ExitBB = SuccBB;
		} else if (SuccBB != L->getHeader()){
		WorkList.push_back(SuccBB);
		}
		}
		}
		}

		return (ExitBB && !isa<PHINode>(ExitBB->begin())) ? ExitBB : nullptr;
		}

		#ifndef NDEBUG
		static void dumpBBSet(std::string Msg, SmallPtrSet<BasicBlock *, 4> &S) {
		dbgs() << Msg << ": ";
		for (const BasicBlock *BB : S)
		dbgs() << BB->getName() << ", ";
		dbgs() << "\n";
		}
		#endif

		static LoopDeletionResult tryInsertEarlyExit(Loop *L, DominatorTree &DT,
		ScalarEvolution &SE, LoopInfo &LI,
		MemorySSA *MSSA,
		OptimizationRemarkEmitter &ORE) {
		assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
		BasicBlock *LatchBB = L->getLoopLatch();
		if (!LatchBB \|\| L->getNumBlocks() == 1)
		return LoopDeletionResult::Unmodified;

		// Check for a known trip count or a forward progress gurantee.
		const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
		if (isa<SCEVCouldNotCompute>(S) && !loopMustProgress(L))
		return LoopDeletionResult::Unmodified;

		if (S->isZero()) {
		// This should be handled by D93906 "Break backedge of loops when known
		// not taken".
		NumSCEV0Skipped++;
		return LoopDeletionResult::Unmodified;
		}

		// Compute two sets of blocks which are free of side-effets. Top starts
		// from header, and Bot starts from latch.
		SmallPtrSet<BasicBlock *, 4> NoSEBBsTop, NoSEBBsBot;
		findNoSEBlocks(NoSEBBsTop, L, true /Forward/);
		findNoSEBlocks(NoSEBBsBot, L, false /Forward/);
		LLVM_DEBUG(dbgs() << "Trying to insert early exits:\n";
		dumpBBSet("Top region", NoSEBBsTop);
		dumpBBSet("Bot region", NoSEBBsBot););

		bool Change = false;
		for (auto BB : NoSEBBsTop) {
		Instruction *TI = BB->getTerminator();
		// We can replace an edge if the conditions will always evaluate the same
		// on the dead path from header to BB, with only one possible exit block
		// from the target BB in the bottom region.
		for (unsigned i = 0, e = TI->getNumOperands(); i != e; ++i)
		if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(TI->getOperand(i)))
		if (NoSEBBsBot.count(SuccBB))
		if (BasicBlock *ExitBB = findExitBlock(SuccBB, L)) {
		LLVM_DEBUG(dbgs() << "Inserting early exit in " << BB->getName() << ":\n";);
		LLVM_DEBUG(TI->dump(); dbgs() << " =>\n";);
		TI->setOperand(i, ExitBB);
		for (PHINode &Phi : SuccBB->phis())
		Phi.removeIncomingValue(BB);
		LLVM_DEBUG(TI->dump(););
		Change = true;
		NumEarlyExits++;
		}
		}

		if (!Change)
		return LoopDeletionResult::Unmodified;

		// Update data structures.
		// NB! Did not yet manage to update everything correctly, so relying on
		// recomputation of the analyses (see getAnalysisUsage()).
		SE.forgetLoop(L);
		DT.recalculate(const_cast<Function >(LatchBB->getParent()));
		Loop *CurrLoop = L;
		while (CurrLoop != nullptr) {
		// Iteratively remove disconnected blocks from CurrLoop.
		Change = true;
		while (Change) {
		Change = false;
		std::vector<BasicBlock*> LoopBlocks(CurrLoop->block_begin(),
		CurrLoop->block_end());
		for (auto BB : LoopBlocks)
		if (!hasPredecessorInLoop(BB, CurrLoop) \|\|
		!hasSuccessorInLoop(BB, CurrLoop)) {
		CurrLoop->removeBlockFromLoop(BB);
		Change = true;
		}
		}
		CurrLoop = CurrLoop->getParentLoop();
		}

		// If all blocks have been removed, return 'Deleted', or LoopPass will try
		// to dump it which doesn't work with an emtpy loop.
		LoopDeletionResult Result = L->getNumBlocks() ? LoopDeletionResult::Modified
		: LoopDeletionResult::Deleted;
		if (Result == LoopDeletionResult::Deleted) {
		LI.erase(L);
		NumLoopsElim++;
		LLVM_DEBUG(dbgs() << "Loop eliminated: all blocks removed.\n"; );
		}
		return Result;
		}

PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,		PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
LoopStandardAnalysisResults &AR,		LoopStandardAnalysisResults &AR,
LPMUpdater &Updater) {		LPMUpdater &Updater) {

LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");		LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
LLVM_DEBUG(L.dump());		LLVM_DEBUG(L.dump());
std::string LoopName = std::string(L.getName());		std::string LoopName = std::string(L.getName());
// For the new PM, we can't use OptimizationRemarkEmitter as an analysis		// For the new PM, we can't use OptimizationRemarkEmitter as an analysis
Show All 29 Lines	LoopDeletionLegacyPass() : LoopPass(ID) {
initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry());		initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry());
}		}

// Possibly eliminate loop L if it is dead.		// Possibly eliminate loop L if it is dead.
bool runOnLoop(Loop *L, LPPassManager &) override;		bool runOnLoop(Loop *L, LPPassManager &) override;

void getAnalysisUsage(AnalysisUsage &AU) const override {		void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addPreserved<MemorySSAWrapperPass>();		AU.addPreserved<MemorySSAWrapperPass>();
getLoopAnalysisUsage(AU);		getLoopAnalysisUsage(AU, false/Preserve: Experimental/);
}		}
};		};
}		}

char LoopDeletionLegacyPass::ID = 0;		char LoopDeletionLegacyPass::ID = 0;
INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",		INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
"Delete dead loops", false, false)		"Delete dead loops", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopPass)		INITIALIZE_PASS_DEPENDENCY(LoopPass)
Show All 16 Lines	bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
// pass. Function analyses need to be preserved across loop transformations		// pass. Function analyses need to be preserved across loop transformations
// but ORE cannot be preserved (see comment before the pass definition).		// but ORE cannot be preserved (see comment before the pass definition).
OptimizationRemarkEmitter ORE(L->getHeader()->getParent());		OptimizationRemarkEmitter ORE(L->getHeader()->getParent());

LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");		LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
LLVM_DEBUG(L->dump());		LLVM_DEBUG(L->dump());

LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE);		LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE);

// If we can prove the backedge isn't taken, just break it and be done. This		// If we can prove the backedge isn't taken, just break it and be done. This
// leaves the loop structure in place which means it can handle dispatching		// leaves the loop structure in place which means it can handle dispatching
// to the right exit based on whatever loop invariant structure remains.		// to the right exit based on whatever loop invariant structure remains.
if (Result != LoopDeletionResult::Deleted)		if (Result != LoopDeletionResult::Deleted)
Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE));		Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE));
		if (Result != LoopDeletionResult::Deleted)
		Result = merge(Result, tryInsertEarlyExit(L, DT, SE, LI, MSSA, ORE));

if (Result == LoopDeletionResult::Deleted)		if (Result == LoopDeletionResult::Deleted)
LPM.markLoopAsDeleted(*L);		LPM.markLoopAsDeleted(*L);

return Result != LoopDeletionResult::Unmodified;		return Result != LoopDeletionResult::Unmodified;
}		}