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)
94 AllEntriesInvariant =
false;
103 if (!AllEntriesInvariant || !AllOutgoingValuesSame)
111 return I.mayHaveSideEffects() && !
I.isDroppable();
125 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
129 WorkList.push_back(L);
130 while (!WorkList.empty()) {
136 if (isa<SCEVCouldNotCompute>(
S)) {
138 dbgs() <<
"Could not compute SCEV MaxBackedgeTakenCount and was "
139 "not required to make progress.\n");
151 using namespace PatternMatch;
156 assert(Preheader &&
"Needs preheader!");
158 if (Preheader->isEntryBlock())
165 if (!
match(Pred->getTerminator(),
168 if (!
Cond->getZExtValue())
170 if (Taken == Preheader)
174 "Preheader should have predecessors at this point!");
183 if (!isa<Instruction>(V))
186 auto Existing = FirstIterValue.
find(V);
187 if (Existing != FirstIterValue.
end())
188 return Existing->second;
189 Value *FirstIterV =
nullptr;
190 if (
auto *BO = dyn_cast<BinaryOperator>(V)) {
196 }
else if (
auto *Cmp = dyn_cast<ICmpInst>(V)) {
202 }
else if (
auto *
Select = dyn_cast<SelectInst>(V)) {
205 if (
auto *
C = dyn_cast<ConstantInt>(
Cond)) {
206 auto *Selected =
C->isAllOnesValue() ?
Select->getTrueValue()
207 :
Select->getFalseValue();
213 FirstIterValue[V] = FirstIterV;
228 if (!Predecessor || !Latch)
239 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
247 LiveBlocks.
insert(Header);
253 "Only canonical backedges are allowed. Irreducible CFG?");
255 "We already discarded this block as dead!");
262 MarkLiveEdge(
BB, Succ);
268 auto GetSoleInputOnFirstIteration = [&](
PHINode & PN)->
Value * {
270 bool HasLivePreds =
false;
273 return PN.getIncomingValueForBlock(Predecessor);
274 Value *OnlyInput =
nullptr;
276 if (LiveEdges.
count({ Pred,
BB })) {
278 Value *Incoming = PN.getIncomingValueForBlock(Pred);
281 if (isa<UndefValue>(Incoming))
284 if (OnlyInput && OnlyInput != Incoming)
286 OnlyInput = Incoming;
289 assert(HasLivePreds &&
"No live predecessors?");
305 auto &
DL = Header->getModule()->getDataLayout();
307 for (
auto *
BB : RPOT) {
311 if (!LiveBlocks.count(
BB))
315 if (LI.getLoopFor(
BB) != L) {
316 MarkAllSuccessorsLive(
BB);
321 for (
auto &PN :
BB->phis()) {
322 if (!PN.getType()->isIntegerTy())
324 auto *Incoming = GetSoleInputOnFirstIteration(PN);
325 if (Incoming && DT.dominates(Incoming,
BB->getTerminator())) {
328 FirstIterValue[&PN] = FirstIterV;
332 using namespace PatternMatch;
335 auto *
Term =
BB->getTerminator();
338 auto *ICmp = dyn_cast<ICmpInst>(
Cond);
339 if (!ICmp || !ICmp->getType()->isIntegerTy()) {
340 MarkAllSuccessorsLive(
BB);
346 if (KnownCondition == ICmp) {
348 MarkAllSuccessorsLive(
BB);
351 if (isa<UndefValue>(KnownCondition)) {
363 if (L->contains(IfTrue) && L->contains(IfFalse))
364 MarkLiveEdge(
BB, IfTrue);
367 auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
368 if (!ConstCondition) {
370 MarkAllSuccessorsLive(
BB);
373 if (ConstCondition->isAllOnesValue())
374 MarkLiveEdge(
BB, IfTrue);
376 MarkLiveEdge(
BB, IfFalse);
378 auto *SwitchValue =
SI->getCondition();
379 auto *SwitchValueOnFirstIter =
381 auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter);
382 if (!ConstSwitchValue) {
383 MarkAllSuccessorsLive(
BB);
386 auto CaseIterator =
SI->findCaseValue(ConstSwitchValue);
387 MarkLiveEdge(
BB, CaseIterator->getCaseSuccessor());
389 MarkAllSuccessorsLive(
BB);
395 return !LiveEdges.count({ Latch, Header });
411 if (!BTCMax->isZero()) {
413 if (!BTC->isZero()) {
420 ++NumBackedgesBroken;
452 <<
"Deletion requires Loop with preheader and dedicated exits.\n");
459 LLVM_DEBUG(
dbgs() <<
"Loop is proven to never execute, delete it!");
466 std::fill(
P.incoming_values().begin(),
P.incoming_values().end(),
472 <<
"Loop deleted because it never executes";
489 LLVM_DEBUG(
dbgs() <<
"Deletion requires at most one exit block.\n");
493 bool Changed =
false;
494 if (!
isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
504 <<
"Loop deleted because it is invariant";
518 std::string LoopName = std::string(L.
getName());
545 class LoopDeletionLegacyPass :
public LoopPass {
564 "Delete dead loops",
false,
false)
574 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
575 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
576 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
577 auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
580 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.
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
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.
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.
auto successors(MachineBasicBlock *BB)
LLVM_NODISCARD T pop_back_val()
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)
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
(vector float) vec_cmpeq(*A, *B) C
Value * SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an ICmpInst, fold the result or return null.
Represent the analysis usage information of a pass.
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")
auto predecessors(MachineBasicBlock *BB)
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.
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.
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.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
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.
StandardInstrumentations SI(Debug, VerifyEach)
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
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr) const
If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivi...
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 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...
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
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.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
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...
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"))