Differential D86844 Diff 308249 llvm/lib/Transforms/Scalar/LoopDeletion.cpp

Changeset View

Standalone View

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

Show First 20 Lines • Show All 60 Lines • ▼ Show 20 Lines	for (PHINode &P : ExitBlock->phis()) {
// block. If there are different incoming values for different exiting		// block. If there are different incoming values for different exiting
// blocks, then it is impossible to statically determine which value		// blocks, then it is impossible to statically determine which value
// should be used.		// should be used.
AllOutgoingValuesSame =		AllOutgoingValuesSame =
all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {		all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
return incoming == P.getIncomingValueForBlock(BB);		return incoming == P.getIncomingValueForBlock(BB);
});		});

if (!AllOutgoingValuesSame)		if (!AllOutgoingValuesSame)
		jdoerfertUnsubmitted Not Done Reply Inline Actions Nit: add the word back. jdoerfert: Nit: add the word back.
break;		break;

if (Instruction *I = dyn_cast<Instruction>(incoming))		if (Instruction *I = dyn_cast<Instruction>(incoming))
		jdoerfertUnsubmitted Not Done Reply Inline Actions Early exists "always". Though I feel this is not the right place for this. Do you need it here at all when u check it also later? jdoerfert: Early exists "always". Though I feel this is not the right place for this. Do you need it here…
if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {		if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
AllEntriesInvariant = false;		AllEntriesInvariant = false;
break;		break;
}		}
}		}
}		}

if (Changed)		if (Changed)
SE.forgetLoopDispositions(L);		SE.forgetLoopDispositions(L);

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 (any_of(*I, [](Instruction &I) {
return I.mayHaveSideEffects() && !I.isDroppable();		return I.mayHaveSideEffects() && !I.isDroppable();
}))		}))
return false;		return false;
return true;		return true;
		jdoerfertUnsubmitted Not Done Reply Inline Actions Check this earlier. It is cheaper than the check before. jdoerfert: Check this earlier. It is cheaper than the check before.
}		}

/// 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) {
using namespace PatternMatch;		using namespace PatternMatch;

Show All 21 Lines	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;
}		}

/// 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
		jonpaUnsubmitted Not Done Reply Inline Actions Seems like it would be nice to update this comment. jonpa: Seems like it would be nice to update this comment.
/// 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
/// order to make various safety checks work.		/// order to make various safety checks work.
///		///
/// \returns true if any changes were made. This may mutate the loop even if it		/// \returns true if any changes were made. This may mutate the loop even if it
/// is unable to delete it due to hoisting trivially loop invariant		/// is unable to delete it due to hoisting trivially loop invariant
▲ Show 20 Lines • Show All 57 Lines • ▼ Show 20 Lines	static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
if (!ExitBlock && !L->hasNoExitBlocks()) {		if (!ExitBlock && !L->hasNoExitBlocks()) {
LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");		LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");
return LoopDeletionResult::Unmodified;		return LoopDeletionResult::Unmodified;
}		}
// Finally, we have to check that the loop really is dead.		// Finally, we have to check that the loop really is dead.
bool Changed = false;		bool Changed = false;
if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {		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
		jdoerfertUnsubmitted Not Done Reply Inline Actions not accurate anymore, just go back to the old version, also in the comment above. jdoerfert: not accurate anymore, just go back to the old version, also in the comment above.
: 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.
		jonpaUnsubmitted Not Done Reply Inline Actions and also this comment..? jonpa: and also this comment..?
const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);		const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(S)) {		if (isa<SCEVCouldNotCompute>(S) &&
		jdoerfertUnsubmitted Not Done Reply Inline Actions This seems to be the only change we need, isn't it? jdoerfert: This seems to be the only change we need, isn't it?
LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");		!L->getHeader()->getParent()->mustProgress() && !hasMustProgress(L)) {
		LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
		"not required to make progress.\n");
		jdoerfertUnsubmitted Not Done Reply Inline Actions -or +and jdoerfert: -or +and
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())
▲ Show 20 Lines • Show All 84 Lines • Show Last 20 Lines