1//===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//===----------------------------------------------------------------------===//
9// This pass performs lightweight instruction simplification on loop bodies.
11//===----------------------------------------------------------------------===//
38 #define DEBUG_TYPE "loop-instsimplify"
40 STATISTIC(NumSimplified,
"Number of redundant instructions simplified");
48 // On the first pass over the loop body we try to simplify every instruction.
49 // On subsequent passes, we can restrict this to only simplifying instructions
50 // where the inputs have been updated. We end up needing two sets: one
51 // containing the instructions we are simplifying in *this* pass, and one for
52 // the instructions we will want to simplify in the *next* pass. We use
53 // pointers so we can swap between two stably allocated sets.
56 // Track the PHI nodes that have already been visited during each iteration so
57 // that we can identify when it is necessary to iterate.
60 // While simplifying we may discover dead code or cause code to become dead.
61 // Keep track of all such instructions and we will delete them at the end.
64 // First we want to create an RPO traversal of the loop body. By processing in
65 // RPO we can ensure that definitions are processed prior to uses (for non PHI
66 // uses) in all cases. This ensures we maximize the simplifications in each
67 // iteration over the loop and minimizes the possible causes for continuing to
88 // We special case the first iteration which we can detect due to the
89 // empty `ToSimplify` set.
90 bool IsFirstIteration = ToSimplify->
empty();
92 if (!IsFirstIteration && !ToSimplify->
count(&
I))
103 // Do not bother dealing with unreachable code.
107 // If the instruction is used by a PHI node we have already processed
108 // we'll need to iterate on the loop body to converge, so add it to
111 if (VisitedPHIs.
count(UserPI)) {
112 Next->insert(UserPI);
116 // If we are only simplifying targeted instructions and the user is an
117 // instruction in the loop body, add it to our set of targeted
118 // instructions. Because we process defs before uses (outside of PHIs)
119 // we won't have visited it yet.
121 // We also skip any uses outside of the loop being simplified. Those
122 // should always be PHI nodes due to LCSSA form, and we don't want to
123 // try to simplify those away.
125 "Uses outside the loop should be PHI nodes due to LCSSA!");
126 if (!IsFirstIteration && L.contains(UserI))
127 ToSimplify->
insert(UserI);
134 MA->replaceAllUsesWith(ReplacementMA);
136 assert(
I.use_empty() &&
"Should always have replaced all uses!");
144 // Delete any dead instructions found thus far now that we've finished an
145 // iteration over all instructions in all the loop blocks.
146 if (!DeadInsts.
empty()) {
154 // If we never found a PHI that needs to be simplified in the next
155 // iteration, we're done.
159 // Otherwise, put the next set in place for the next iteration and reset it
160 // and the visited PHIs for that iteration.
173 std::optional<MemorySSAUpdater> MSSAU;
180 MSSAU ? &*MSSAU :
nullptr))
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, const TargetLibraryInfo &TLI, MemorySSAUpdater *MSSAU)
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Represents analyses that only rely on functions' control flow.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
void perform(const LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Represents a single loop in the control flow graph.
An analysis that produces MemorySSA for a function.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Encapsulates MemorySSA, including all data associated with memory accesses.
LLVM_ABI void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Provides information about what library functions are available for the current target.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
auto dyn_cast_or_null(const Y &Val)
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
FunctionAddr VTableAddr Next
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
SimplifyQuery getWithInstruction(const Instruction *I) const