blob: 5814e2f043d50802b1abcbadfe454e3b458bd3f2 [file] [log] [blame]
//===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the Dead Loop Deletion Pass. This pass is responsible
// for eliminating loops with non-infinite computable trip counts that have no
// side effects or volatile instructions, and do not contribute to the
// computation of the function's return value.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar/LoopDeletion.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/InitializePasses.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
using namespace llvm;
#define DEBUG_TYPE "loop-delete"
STATISTIC(NumDeleted, "Number of loops deleted");
STATISTIC(NumBackedgesBroken,
"Number of loops for which we managed to break the backedge");
static cl::opt<bool> EnableSymbolicExecution(
"loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true),
cl::desc("Break backedge through symbolic execution of 1st iteration "
"attempting to prove that the backedge is never taken"));
enum class LoopDeletionResult {
Unmodified,
Modified,
Deleted,
};
static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) {
if (A == LoopDeletionResult::Deleted || B == LoopDeletionResult::Deleted)
return LoopDeletionResult::Deleted;
if (A == LoopDeletionResult::Modified || B == LoopDeletionResult::Modified)
return LoopDeletionResult::Modified;
return LoopDeletionResult::Unmodified;
}
/// Determines if a loop is dead.
///
/// This assumes that we've already checked for unique exit and exiting blocks,
/// and that the code is in LCSSA form.
static bool isLoopDead(Loop *L, ScalarEvolution &SE,
SmallVectorImpl<BasicBlock *> &ExitingBlocks,
BasicBlock *ExitBlock, bool &Changed,
BasicBlock *Preheader, LoopInfo &LI) {
// Make sure that all PHI entries coming from the loop are loop invariant.
// Because the code is in LCSSA form, any values used outside of the loop
// must pass through a PHI in the exit block, meaning that this check is
// sufficient to guarantee that no loop-variant values are used outside
// of the loop.
bool AllEntriesInvariant = true;
bool AllOutgoingValuesSame = true;
if (!L->hasNoExitBlocks()) {
for (PHINode &P : ExitBlock->phis()) {
Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
// Make sure all exiting blocks produce the same incoming value for the
// block. If there are different incoming values for different exiting
// blocks, then it is impossible to statically determine which value
// should be used.
AllOutgoingValuesSame =
all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
return incoming == P.getIncomingValueForBlock(BB);
});
if (!AllOutgoingValuesSame)
break;
if (Instruction *I = dyn_cast<Instruction>(incoming))
if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
AllEntriesInvariant = false;
break;
}
}
}
if (Changed)
SE.forgetLoopDispositions(L);
if (!AllEntriesInvariant || !AllOutgoingValuesSame)
return false;
// Make sure that no instructions in the block have potential side-effects.
// This includes instructions that could write to memory, and loads that are
// marked volatile.
for (auto &I : L->blocks())
if (any_of(*I, [](Instruction &I) {
return I.mayHaveSideEffects() && !I.isDroppable();
}))
return false;
// The loop or any of its sub-loops looping infinitely is legal. The loop can
// only be considered dead if either
// a. the function is mustprogress.
// b. all (sub-)loops are mustprogress or have a known trip-count.
if (L->getHeader()->getParent()->mustProgress())
return true;
LoopBlocksRPO RPOT(L);
RPOT.perform(&LI);
// If the loop contains an irreducible cycle, it may loop infinitely.
if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
return false;
SmallVector<Loop *, 8> WorkList;
WorkList.push_back(L);
while (!WorkList.empty()) {
Loop *Current = WorkList.pop_back_val();
if (hasMustProgress(Current))
continue;
const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current);
if (isa<SCEVCouldNotCompute>(S)) {
LLVM_DEBUG(
dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
"not required to make progress.\n");
return false;
}
WorkList.append(Current->begin(), Current->end());
}
return true;
}
/// 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
/// a local search to save compile time.
static bool isLoopNeverExecuted(Loop *L) {
using namespace PatternMatch;
auto *Preheader = L->getLoopPreheader();
// TODO: We can relax this constraint, since we just need a loop
// predecessor.
assert(Preheader && "Needs preheader!");
if (Preheader->isEntryBlock())
return false;
// All predecessors of the preheader should have a constant conditional
// branch, with the loop's preheader as not-taken.
for (auto *Pred: predecessors(Preheader)) {
BasicBlock *Taken, *NotTaken;
ConstantInt *Cond;
if (!match(Pred->getTerminator(),
m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
return false;
if (!Cond->getZExtValue())
std::swap(Taken, NotTaken);
if (Taken == Preheader)
return false;
}
assert(!pred_empty(Preheader) &&
"Preheader should have predecessors at this point!");
// All the predecessors have the loop preheader as not-taken target.
return true;
}
static Value *
getValueOnFirstIteration(Value *V, DenseMap<Value *, Value *> &FirstIterValue,
const SimplifyQuery &SQ) {
// Quick hack: do not flood cache with non-instruction values.
if (!isa<Instruction>(V))
return V;
// Do we already know cached result?
auto Existing = FirstIterValue.find(V);
if (Existing != FirstIterValue.end())
return Existing->second;
Value *FirstIterV = nullptr;
if (auto *BO = dyn_cast<BinaryOperator>(V)) {
Value *LHS =
getValueOnFirstIteration(BO->getOperand(0), FirstIterValue, SQ);
Value *RHS =
getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ);
FirstIterV = SimplifyBinOp(BO->getOpcode(), LHS, RHS, SQ);
} else if (auto *Cmp = dyn_cast<ICmpInst>(V)) {
Value *LHS =
getValueOnFirstIteration(Cmp->getOperand(0), FirstIterValue, SQ);
Value *RHS =
getValueOnFirstIteration(Cmp->getOperand(1), FirstIterValue, SQ);
FirstIterV = SimplifyICmpInst(Cmp->getPredicate(), LHS, RHS, SQ);
} else if (auto *Select = dyn_cast<SelectInst>(V)) {
Value *Cond =
getValueOnFirstIteration(Select->getCondition(), FirstIterValue, SQ);
if (auto *C = dyn_cast<ConstantInt>(Cond)) {
auto *Selected = C->isAllOnesValue() ? Select->getTrueValue()
: Select->getFalseValue();
FirstIterV = getValueOnFirstIteration(Selected, FirstIterValue, SQ);
}
}
if (!FirstIterV)
FirstIterV = V;
FirstIterValue[V] = FirstIterV;
return FirstIterV;
}
// Try to prove that one of conditions that dominates the latch must exit on 1st
// iteration.
static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT,
LoopInfo &LI) {
// Disabled by option.
if (!EnableSymbolicExecution)
return false;
BasicBlock *Predecessor = L->getLoopPredecessor();
BasicBlock *Latch = L->getLoopLatch();
if (!Predecessor || !Latch)
return false;
LoopBlocksRPO RPOT(L);
RPOT.perform(&LI);
// For the optimization to be correct, we need RPOT to have a property that
// each block is processed after all its predecessors, which may only be
// violated for headers of the current loop and all nested loops. Irreducible
// CFG provides multiple ways to break this assumption, so we do not want to
// deal with it.
if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
return false;
BasicBlock *Header = L->getHeader();
// Blocks that are reachable on the 1st iteration.
SmallPtrSet<BasicBlock *, 4> LiveBlocks;
// Edges that are reachable on the 1st iteration.
DenseSet<BasicBlockEdge> LiveEdges;
LiveBlocks.insert(Header);
SmallPtrSet<BasicBlock *, 4> Visited;
auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) {
assert(LiveBlocks.count(From) && "Must be live!");
assert((LI.isLoopHeader(To) || !Visited.count(To)) &&
"Only canonical backedges are allowed. Irreducible CFG?");
assert((LiveBlocks.count(To) || !Visited.count(To)) &&
"We already discarded this block as dead!");
LiveBlocks.insert(To);
LiveEdges.insert({ From, To });
};
auto MarkAllSuccessorsLive = [&](BasicBlock *BB) {
for (auto *Succ : successors(BB))
MarkLiveEdge(BB, Succ);
};
// Check if there is only one value coming from all live predecessor blocks.
// Note that because we iterate in RPOT, we have already visited all its
// (non-latch) predecessors.
auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
BasicBlock *BB = PN.getParent();
bool HasLivePreds = false;
(void)HasLivePreds;
if (BB == Header)
return PN.getIncomingValueForBlock(Predecessor);
Value *OnlyInput = nullptr;
for (auto *Pred : predecessors(BB))
if (LiveEdges.count({ Pred, BB })) {
HasLivePreds = true;
Value *Incoming = PN.getIncomingValueForBlock(Pred);
// Skip undefs. If they are present, we can assume they are equal to
// the non-undef input.
if (isa<UndefValue>(Incoming))
continue;
// Two inputs.
if (OnlyInput && OnlyInput != Incoming)
return nullptr;
OnlyInput = Incoming;
}
assert(HasLivePreds && "No live predecessors?");
// If all incoming live value were undefs, return undef.
return OnlyInput ? OnlyInput : UndefValue::get(PN.getType());
};
DenseMap<Value *, Value *> FirstIterValue;
// Use the following algorithm to prove we never take the latch on the 1st
// iteration:
// 1. Traverse in topological order, so that whenever we visit a block, all
// its predecessors are already visited.
// 2. If we can prove that the block may have only 1 predecessor on the 1st
// iteration, map all its phis onto input from this predecessor.
// 3a. If we can prove which successor of out block is taken on the 1st
// iteration, mark this successor live.
// 3b. If we cannot prove it, conservatively assume that all successors are
// live.
auto &DL = Header->getModule()->getDataLayout();
const SimplifyQuery SQ(DL);
for (auto *BB : RPOT) {
Visited.insert(BB);
// This block is not reachable on the 1st iterations.
if (!LiveBlocks.count(BB))
continue;
// Skip inner loops.
if (LI.getLoopFor(BB) != L) {
MarkAllSuccessorsLive(BB);
continue;
}
// If Phi has only one input from all live input blocks, use it.
for (auto &PN : BB->phis()) {
if (!PN.getType()->isIntegerTy())
continue;
auto *Incoming = GetSoleInputOnFirstIteration(PN);
if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
Value *FirstIterV =
getValueOnFirstIteration(Incoming, FirstIterValue, SQ);
FirstIterValue[&PN] = FirstIterV;
}
}
using namespace PatternMatch;
Value *Cond;
BasicBlock *IfTrue, *IfFalse;
auto *Term = BB->getTerminator();
if (match(Term, m_Br(m_Value(Cond),
m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) {
auto *ICmp = dyn_cast<ICmpInst>(Cond);
if (!ICmp || !ICmp->getType()->isIntegerTy()) {
MarkAllSuccessorsLive(BB);
continue;
}
// Can we prove constant true or false for this condition?
auto *KnownCondition = getValueOnFirstIteration(ICmp, FirstIterValue, SQ);
if (KnownCondition == ICmp) {
// Failed to simplify.
MarkAllSuccessorsLive(BB);
continue;
}
if (isa<UndefValue>(KnownCondition)) {
// TODO: According to langref, branching by undef is undefined behavior.
// It means that, theoretically, we should be able to just continue
// without marking any successors as live. However, we are not certain
// how correct our compiler is at handling such cases. So we are being
// very conservative here.
//
// If there is a non-loop successor, always assume this branch leaves the
// loop. Otherwise, arbitrarily take IfTrue.
//
// Once we are certain that branching by undef is handled correctly by
// other transforms, we should not mark any successors live here.
if (L->contains(IfTrue) && L->contains(IfFalse))
MarkLiveEdge(BB, IfTrue);
continue;
}
auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
if (!ConstCondition) {
// Non-constant condition, cannot analyze any further.
MarkAllSuccessorsLive(BB);
continue;
}
if (ConstCondition->isAllOnesValue())
MarkLiveEdge(BB, IfTrue);
else
MarkLiveEdge(BB, IfFalse);
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
auto *SwitchValue = SI->getCondition();
auto *SwitchValueOnFirstIter =
getValueOnFirstIteration(SwitchValue, FirstIterValue, SQ);
auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter);
if (!ConstSwitchValue) {
MarkAllSuccessorsLive(BB);
continue;
}
auto CaseIterator = SI->findCaseValue(ConstSwitchValue);
MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());
} else {
MarkAllSuccessorsLive(BB);
continue;
}
}
// We can break the latch if it wasn't live.
return !LiveEdges.count({ Latch, Header });
}
/// If we can prove the backedge is untaken, remove it. This destroys the
/// loop, but leaves the (now trivially loop invariant) control flow and
/// side effects (if any) in place.
static LoopDeletionResult
breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
LoopInfo &LI, MemorySSA *MSSA,
OptimizationRemarkEmitter &ORE) {
assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
if (!L->getLoopLatch())
return LoopDeletionResult::Unmodified;
auto *BTC = SE.getSymbolicMaxBackedgeTakenCount(L);
if (BTC->isZero()) {
// SCEV knows this backedge isn't taken!
breakLoopBackedge(L, DT, SE, LI, MSSA);
++NumBackedgesBroken;
return LoopDeletionResult::Deleted;
}
// If SCEV leaves open the possibility of a zero trip count, see if
// symbolically evaluating the first iteration lets us prove the backedge
// unreachable.
if (isa<SCEVCouldNotCompute>(BTC) || !SE.isKnownNonZero(BTC))
if (canProveExitOnFirstIteration(L, DT, LI)) {
breakLoopBackedge(L, DT, SE, LI, MSSA);
++NumBackedgesBroken;
return LoopDeletionResult::Deleted;
}
return LoopDeletionResult::Unmodified;
}
/// Remove a loop if it is dead.
///
/// A loop is considered dead either if it does not impact the observable
/// behavior of the program other than finite running time, or if it is
/// required to make progress by an attribute such as 'mustprogress' or
/// 'llvm.loop.mustprogress' and does not make any. This may remove
/// infinite loops that have been required to make progress.
///
/// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
/// order to make various safety checks work.
///
/// \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
/// instructions out of the loop.
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
ScalarEvolution &SE, LoopInfo &LI,
MemorySSA *MSSA,
OptimizationRemarkEmitter &ORE) {
assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
// We can only remove the loop if there is a preheader that we can branch from
// after removing it. Also, if LoopSimplify form is not available, stay out
// of trouble.
BasicBlock *Preheader = L->getLoopPreheader();
if (!Preheader || !L->hasDedicatedExits()) {
LLVM_DEBUG(
dbgs()
<< "Deletion requires Loop with preheader and dedicated exits.\n");
return LoopDeletionResult::Unmodified;
}
BasicBlock *ExitBlock = L->getUniqueExitBlock();
if (ExitBlock && isLoopNeverExecuted(L)) {
LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
// We need to forget the loop before setting the incoming values of the exit
// phis to undef, so we properly invalidate the SCEV expressions for those
// phis.
SE.forgetLoop(L);
// Set incoming value to undef for phi nodes in the exit block.
for (PHINode &P : ExitBlock->phis()) {
std::fill(P.incoming_values().begin(), P.incoming_values().end(),
UndefValue::get(P.getType()));
}
ORE.emit([&]() {
return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
L->getHeader())
<< "Loop deleted because it never executes";
});
deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
++NumDeleted;
return LoopDeletionResult::Deleted;
}
// The remaining checks below are for a loop being dead because all statements
// in the loop are invariant.
SmallVector<BasicBlock *, 4> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks);
// We require that the loop has at most one exit block. Otherwise, we'd be in
// the situation of needing to be able to solve statically which exit block
// will be branched to, or trying to preserve the branching logic in a loop
// invariant manner.
if (!ExitBlock && !L->hasNoExitBlocks()) {
LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");
return LoopDeletionResult::Unmodified;
}
// Finally, we have to check that the loop really is dead.
bool Changed = false;
if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
return Changed ? LoopDeletionResult::Modified
: LoopDeletionResult::Unmodified;
}
LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
ORE.emit([&]() {
return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
L->getHeader())
<< "Loop deleted because it is invariant";
});
deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
++NumDeleted;
return LoopDeletionResult::Deleted;
}
PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
LoopStandardAnalysisResults &AR,
LPMUpdater &Updater) {
LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
LLVM_DEBUG(L.dump());
std::string LoopName = std::string(L.getName());
// For the new PM, we can't use OptimizationRemarkEmitter as an analysis
// pass. Function analyses need to be preserved across loop transformations
// but ORE cannot be preserved (see comment before the pass definition).
OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE);
// 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
// to the right exit based on whatever loop invariant structure remains.
if (Result != LoopDeletionResult::Deleted)
Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI,
AR.MSSA, ORE));
if (Result == LoopDeletionResult::Unmodified)
return PreservedAnalyses::all();
if (Result == LoopDeletionResult::Deleted)
Updater.markLoopAsDeleted(L, LoopName);
auto PA = getLoopPassPreservedAnalyses();
if (AR.MSSA)
PA.preserve<MemorySSAAnalysis>();
return PA;
}
namespace {
class LoopDeletionLegacyPass : public LoopPass {
public:
static char ID; // Pass ID, replacement for typeid
LoopDeletionLegacyPass() : LoopPass(ID) {
initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry());
}
// Possibly eliminate loop L if it is dead.
bool runOnLoop(Loop *L, LPPassManager &) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addPreserved<MemorySSAWrapperPass>();
getLoopAnalysisUsage(AU);
}
};
}
char LoopDeletionLegacyPass::ID = 0;
INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
"Delete dead loops", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopPass)
INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
"Delete dead loops", false, false)
Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
if (skipLoop(L))
return false;
DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
MemorySSA *MSSA = nullptr;
if (MSSAAnalysis)
MSSA = &MSSAAnalysis->getMSSA();
// For the old PM, we can't use OptimizationRemarkEmitter as an analysis
// pass. Function analyses need to be preserved across loop transformations
// but ORE cannot be preserved (see comment before the pass definition).
OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
LLVM_DEBUG(L->dump());
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
// leaves the loop structure in place which means it can handle dispatching
// to the right exit based on whatever loop invariant structure remains.
if (Result != LoopDeletionResult::Deleted)
Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE));
if (Result == LoopDeletionResult::Deleted)
LPM.markLoopAsDeleted(*L);
return Result != LoopDeletionResult::Unmodified;
}