Go to the documentation of this file.
36 #define DEBUG_TYPE "loop-delete"
38 STATISTIC(NumDeleted,
"Number of loops deleted");
40 "Number of loops for which we managed to break the backedge");
44 cl::desc(
"Break backedge through symbolic execution of 1st iteration "
45 "attempting to prove that the backedge is never taken"));
74 bool AllEntriesInvariant =
true;
75 bool AllOutgoingValuesSame =
true;
78 Value *incoming =
P.getIncomingValueForBlock(ExitingBlocks[0]);
84 AllOutgoingValuesSame =
86 return incoming ==
P.getIncomingValueForBlock(
BB);
89 if (!AllOutgoingValuesSame)
95 AllEntriesInvariant =
false;
102 if (!AllEntriesInvariant || !AllOutgoingValuesSame)
108 for (
const auto &
I : L->
blocks())
110 return I.mayHaveSideEffects() && !
I.isDroppable();
124 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
128 WorkList.push_back(L);
129 while (!WorkList.empty()) {
135 if (isa<SCEVCouldNotCompute>(
S)) {
137 dbgs() <<
"Could not compute SCEV MaxBackedgeTakenCount and was "
138 "not required to make progress.\n");
150 using namespace PatternMatch;
155 assert(Preheader &&
"Needs preheader!");
157 if (Preheader->isEntryBlock())
164 if (!
match(Pred->getTerminator(),
167 if (!
Cond->getZExtValue())
169 if (Taken == Preheader)
173 "Preheader should have predecessors at this point!");
182 if (!isa<Instruction>(V))
185 auto Existing = FirstIterValue.
find(V);
186 if (Existing != FirstIterValue.
end())
187 return Existing->second;
188 Value *FirstIterV =
nullptr;
189 if (
auto *BO = dyn_cast<BinaryOperator>(V)) {
195 }
else if (
auto *Cmp = dyn_cast<ICmpInst>(V)) {
201 }
else if (
auto *
Select = dyn_cast<SelectInst>(V)) {
204 if (
auto *
C = dyn_cast<ConstantInt>(
Cond)) {
205 auto *Selected =
C->isAllOnesValue() ?
Select->getTrueValue()
206 :
Select->getFalseValue();
212 FirstIterValue[V] = FirstIterV;
227 if (!Predecessor || !Latch)
238 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
246 LiveBlocks.
insert(Header);
252 "Only canonical backedges are allowed. Irreducible CFG?");
254 "We already discarded this block as dead!");
261 MarkLiveEdge(
BB, Succ);
267 auto GetSoleInputOnFirstIteration = [&](
PHINode & PN)->
Value * {
269 bool HasLivePreds =
false;
272 return PN.getIncomingValueForBlock(Predecessor);
273 Value *OnlyInput =
nullptr;
275 if (LiveEdges.
count({ Pred,
BB })) {
277 Value *Incoming = PN.getIncomingValueForBlock(Pred);
280 if (isa<UndefValue>(Incoming))
283 if (OnlyInput && OnlyInput != Incoming)
285 OnlyInput = Incoming;
288 assert(HasLivePreds &&
"No live predecessors?");
304 auto &
DL = Header->getModule()->getDataLayout();
306 for (
auto *
BB : RPOT) {
310 if (!LiveBlocks.count(
BB))
314 if (LI.getLoopFor(
BB) != L) {
315 MarkAllSuccessorsLive(
BB);
320 for (
auto &PN :
BB->phis()) {
321 if (!PN.getType()->isIntegerTy())
323 auto *Incoming = GetSoleInputOnFirstIteration(PN);
324 if (Incoming && DT.dominates(Incoming,
BB->getTerminator())) {
327 FirstIterValue[&PN] = FirstIterV;
331 using namespace PatternMatch;
334 auto *
Term =
BB->getTerminator();
337 auto *ICmp = dyn_cast<ICmpInst>(
Cond);
338 if (!ICmp || !ICmp->getType()->isIntegerTy()) {
339 MarkAllSuccessorsLive(
BB);
345 if (KnownCondition == ICmp) {
347 MarkAllSuccessorsLive(
BB);
350 if (isa<UndefValue>(KnownCondition)) {
362 if (L->contains(IfTrue) && L->contains(IfFalse))
363 MarkLiveEdge(
BB, IfTrue);
366 auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
367 if (!ConstCondition) {
369 MarkAllSuccessorsLive(
BB);
372 if (ConstCondition->isAllOnesValue())
373 MarkLiveEdge(
BB, IfTrue);
375 MarkLiveEdge(
BB, IfFalse);
377 auto *SwitchValue =
SI->getCondition();
378 auto *SwitchValueOnFirstIter =
380 auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter);
381 if (!ConstSwitchValue) {
382 MarkAllSuccessorsLive(
BB);
385 auto CaseIterator =
SI->findCaseValue(ConstSwitchValue);
386 MarkLiveEdge(
BB, CaseIterator->getCaseSuccessor());
388 MarkAllSuccessorsLive(
BB);
394 return !LiveEdges.count({ Latch, Header });
410 if (!BTCMax->isZero()) {
412 if (!BTC->isZero()) {
419 ++NumBackedgesBroken;
451 <<
"Deletion requires Loop with preheader and dedicated exits.\n");
458 LLVM_DEBUG(
dbgs() <<
"Loop is proven to never execute, delete it!\n");
465 std::fill(
P.incoming_values().begin(),
P.incoming_values().end(),
471 <<
"Loop deleted because it never executes";
488 LLVM_DEBUG(
dbgs() <<
"Deletion requires at most one exit block.\n");
492 bool Changed =
false;
493 if (!
isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
503 <<
"Loop deleted because it is invariant";
517 std::string LoopName = std::string(L.
getName());
544 class LoopDeletionLegacyPass :
public LoopPass {
563 "Delete dead loops",
false,
false)
573 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
574 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
575 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
576 auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
579 MSSA = &MSSAAnalysis->getMSSA();
A set of analyses that are preserved following a run of a transformation pass.
This is an optimization pass for GlobalISel generic memory operations.
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
const Function * getParent() const
Return the enclosing method, or null if none.
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA, OptimizationRemarkEmitter &ORE)
Remove a loop if it is dead.
Represents a single loop in the control flow graph.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT, LoopInfo &LI)
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
auto successors(const MachineBasicBlock *BB)
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
The main scalar evolution driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion", "Delete dead loops", false, false) INITIALIZE_PASS_END(LoopDeletionLegacyPass
static LoopDeletionResult breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA, OptimizationRemarkEmitter &ORE)
If we can prove the backedge is untaken, remove it.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
LLVM Basic Block Representation.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
This is the shared class of boolean and integer constants.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Legacy analysis pass which computes MemorySSA.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
(vector float) vec_cmpeq(*A, *B) C
Represent the analysis usage information of a pass.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
iterator_range< block_iterator > blocks() const
static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
STATISTIC(NumFunctions, "Total number of functions")
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
static bool isLoopNeverExecuted(Loop *L)
This function returns true if there is no viable path from the entry block to the header of L.
StringRef getName() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
auto predecessors(const MachineBasicBlock *BB)
Implements a dense probed hash-table based set.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
This class represents an analyzed expression in the program.
Value * simplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an ICmpInst, fold the result or return null.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Encapsulates MemorySSA, including all data associated with memory accesses.
initializer< Ty > init(const Ty &Val)
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
iterator find(const_arg_type_t< KeyT > Val)
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
An analysis that produces MemorySSA for a function.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
SmallVector< MachineOperand, 4 > Cond
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void initializeLoopDeletionLegacyPassPass(PassRegistry &)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
bool pred_empty(const BasicBlock *BB)
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr, ScalarEvolution *SE=nullptr) const
If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivi...
bool isLoopHeader(const BlockT *BB) const
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
void markLoopAsDeleted(Loop &L)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
BlockT * getHeader() const
bool mustProgress() const
Determine if the function is required to make forward progress.
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
Pass interface - Implemented by all 'passes'.
bool hasMustProgress(const Loop *L)
Look for the loop attribute that requires progress within the loop.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const
Return true if the Loop is in LCSSA form.
ArrayRef(const T &OneElt) -> ArrayRef< T >
A container for analyses that lazily runs them and caches their results.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
BlockVerifier::State From
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
static Value * getValueOnFirstIteration(Value *V, DenseMap< Value *, Value * > &FirstIterValue, const SimplifyQuery &SQ)
@ Unmodified
The loop was not modified.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
static bool isLoopDead(Loop *L, ScalarEvolution &SE, SmallVectorImpl< BasicBlock * > &ExitingBlocks, BasicBlock *ExitBlock, bool &Changed, BasicBlock *Preheader, LoopInfo &LI)
Determines if a loop is dead.
Pass * createLoopDeletionPass()
LLVM Value Representation.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
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"))
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.