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

Changeset View

Standalone View

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

Show First 20 Lines • Show All 83 Lines • ▼ Show 20 Lines	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 (any_of(*I, [](Instruction &I) {
return I.mayHaveSideEffects() && !I.isDroppable();		return I.mayHaveSideEffects() && !I.isDroppable();
}))		}))
		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 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…

/// Remove a loop if it is dead.		/// Remove a loop if it is dead.
///		///
/// A loop is considered dead if it does not impact the observable behavior of		/// A loop is considered dead if it does not impact the observable behavior of
/// the program other than finite running time. This never removes a loop that		/// the program other than finite running time. This never removes a loop that
/// might be infinite (unless it is never executed), as doing so could change		/// might be infinite (unless it is never executed), as doing so could change
/// the halting/non-halting nature of a program.		/// the halting/non-halting nature of a program.
///		///
/// This entire process relies pretty heavily on LoopSimplify form and LCSSA in		/// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
▲ Show 20 Lines • Show All 68 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.		// Don't remove loops for which we can't solve the trip count.
// They could be infinite, in which case we'd be changing program behavior.		// They could be infinite, in which case we'd be changing program behavior.
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(Instruction I, Loop L) {
		if (!L->contains(I->getParent()))
		return false;
		if (isa<PHINode>(I))
		return true;
		for (auto &Op : I->operands())
		if (Instruction *OpI = dyn_cast<Instruction>(&Op))
		if (usesLoopPHI(OpI, L))
		return true;
		return false;
		}

		static bool tryInsertEarlyExit(Loop *L, DominatorTree &DT,
		ScalarEvolution &SE, LoopInfo &LI,
		MemorySSA *MSSA,
		OptimizationRemarkEmitter &ORE) {
		using namespace PatternMatch;
		assert(L->isLCSSAForm(DT) && "Expected LCSSA!");

		// Only with a forward progress gurantee is it legal to exit early from a
		// dead path of the loop. Do early exit if only one or two blocks.
		if (!loopMustProgress(L) \|\| L->getNumBlocks() < 3)
		return false;

		BasicBlock *HeaderBlock = L->getHeader();
		BasicBlock *LatchBlock = L->getLoopLatch();
		Instruction *HeaderBr = HeaderBlock->getTerminator();
		Instruction *CmpI = nullptr;
		BasicBlock Taken, NotTaken;
		if (!match(HeaderBr, m_Br(m_Instruction(CmpI), Taken, NotTaken)))
		return false;

		// See if header branches to latch.
		if (Taken != LatchBlock && NotTaken != LatchBlock)
		return false;

		// Check that both header and latch are free of side-effects.
		for (auto &I : *HeaderBlock)
		if (I.mayHaveSideEffects() && !I.isDroppable())
		return false;
		for (auto &I : *LatchBlock)
		if (I.mayHaveSideEffects() && !I.isDroppable())
		return false;
		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

		// Check that the comparison is not based on any value redefined in the
		// loop. It was not possible to hoist it out of the loop but here it is
		// sufficient that it is constant on the dead path. TODO: worth checking
		// if incoming value from preheader/latch are the same and allow that case?
		if (usesLoopPHI(CmpI, L))
		return false;

		// The header takes a branch across the main body of the loop directly to
		// the latch. This path is dead, so turn this into an early exit.
		Instruction *LatchBr = LatchBlock->getTerminator();
		if (!match(LatchBr, m_Br(m_Value(), Taken, NotTaken)))
		return false;
		BasicBlock *ExitBlock = (Taken != HeaderBlock ? Taken : NotTaken);
		unsigned OpNo = HeaderBr->getOperand(1) == LatchBlock ? 1 : 2;
		HeaderBr->setOperand(OpNo, ExitBlock);
		return true;
		}

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 20 Lines • Show All 57 Lines • ▼ Show 20 Lines	bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {

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 (Result == LoopDeletionResult::Deleted)		if (Result == LoopDeletionResult::Deleted)
LPM.markLoopAsDeleted(*L);		LPM.markLoopAsDeleted(*L);
		else if (tryInsertEarlyExit(L, DT, SE, LI, MSSA, ORE))
		Result = LoopDeletionResult::Modified;

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