LLVM 17.0.0git
LoopInstSimplify.cpp
Go to the documentation of this file.
1//===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass performs lightweight instruction simplification on loop bodies.
10//
11//===----------------------------------------------------------------------===//
12
14#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/Statistic.h"
26#include "llvm/IR/BasicBlock.h"
27#include "llvm/IR/Dominators.h"
28#include "llvm/IR/Instruction.h"
30#include "llvm/IR/Module.h"
31#include "llvm/IR/PassManager.h"
33#include "llvm/Pass.h"
38#include <optional>
39#include <utility>
40
41using namespace llvm;
42
43#define DEBUG_TYPE "loop-instsimplify"
44
45STATISTIC(NumSimplified, "Number of redundant instructions simplified");
46
48 AssumptionCache &AC, const TargetLibraryInfo &TLI,
49 MemorySSAUpdater *MSSAU) {
50 const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
51 SimplifyQuery SQ(DL, &TLI, &DT, &AC);
52
53 // On the first pass over the loop body we try to simplify every instruction.
54 // On subsequent passes, we can restrict this to only simplifying instructions
55 // where the inputs have been updated. We end up needing two sets: one
56 // containing the instructions we are simplifying in *this* pass, and one for
57 // the instructions we will want to simplify in the *next* pass. We use
58 // pointers so we can swap between two stably allocated sets.
59 SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
60
61 // Track the PHI nodes that have already been visited during each iteration so
62 // that we can identify when it is necessary to iterate.
63 SmallPtrSet<PHINode *, 4> VisitedPHIs;
64
65 // While simplifying we may discover dead code or cause code to become dead.
66 // Keep track of all such instructions and we will delete them at the end.
68
69 // First we want to create an RPO traversal of the loop body. By processing in
70 // RPO we can ensure that definitions are processed prior to uses (for non PHI
71 // uses) in all cases. This ensures we maximize the simplifications in each
72 // iteration over the loop and minimizes the possible causes for continuing to
73 // iterate.
74 LoopBlocksRPO RPOT(&L);
75 RPOT.perform(&LI);
76 MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
77
78 bool Changed = false;
79 for (;;) {
80 if (MSSAU && VerifyMemorySSA)
81 MSSA->verifyMemorySSA();
82 for (BasicBlock *BB : RPOT) {
83 for (Instruction &I : *BB) {
84 if (auto *PI = dyn_cast<PHINode>(&I))
85 VisitedPHIs.insert(PI);
86
87 if (I.use_empty()) {
88 if (isInstructionTriviallyDead(&I, &TLI))
89 DeadInsts.push_back(&I);
90 continue;
91 }
92
93 // We special case the first iteration which we can detect due to the
94 // empty `ToSimplify` set.
95 bool IsFirstIteration = ToSimplify->empty();
96
97 if (!IsFirstIteration && !ToSimplify->count(&I))
98 continue;
99
101 if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
102 continue;
103
104 for (Use &U : llvm::make_early_inc_range(I.uses())) {
105 auto *UserI = cast<Instruction>(U.getUser());
106 U.set(V);
107
108 // Do not bother dealing with unreachable code.
109 if (!DT.isReachableFromEntry(UserI->getParent()))
110 continue;
111
112 // If the instruction is used by a PHI node we have already processed
113 // we'll need to iterate on the loop body to converge, so add it to
114 // the next set.
115 if (auto *UserPI = dyn_cast<PHINode>(UserI))
116 if (VisitedPHIs.count(UserPI)) {
117 Next->insert(UserPI);
118 continue;
119 }
120
121 // If we are only simplifying targeted instructions and the user is an
122 // instruction in the loop body, add it to our set of targeted
123 // instructions. Because we process defs before uses (outside of PHIs)
124 // we won't have visited it yet.
125 //
126 // We also skip any uses outside of the loop being simplified. Those
127 // should always be PHI nodes due to LCSSA form, and we don't want to
128 // try to simplify those away.
129 assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
130 "Uses outside the loop should be PHI nodes due to LCSSA!");
131 if (!IsFirstIteration && L.contains(UserI))
132 ToSimplify->insert(UserI);
133 }
134
135 if (MSSAU)
136 if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V))
137 if (MemoryAccess *MA = MSSA->getMemoryAccess(&I))
138 if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI))
139 MA->replaceAllUsesWith(ReplacementMA);
140
141 assert(I.use_empty() && "Should always have replaced all uses!");
142 if (isInstructionTriviallyDead(&I, &TLI))
143 DeadInsts.push_back(&I);
144 ++NumSimplified;
145 Changed = true;
146 }
147 }
148
149 // Delete any dead instructions found thus far now that we've finished an
150 // iteration over all instructions in all the loop blocks.
151 if (!DeadInsts.empty()) {
152 Changed = true;
153 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
154 }
155
156 if (MSSAU && VerifyMemorySSA)
157 MSSA->verifyMemorySSA();
158
159 // If we never found a PHI that needs to be simplified in the next
160 // iteration, we're done.
161 if (Next->empty())
162 break;
163
164 // Otherwise, put the next set in place for the next iteration and reset it
165 // and the visited PHIs for that iteration.
166 std::swap(Next, ToSimplify);
167 Next->clear();
168 VisitedPHIs.clear();
169 DeadInsts.clear();
170 }
171
172 return Changed;
173}
174
175namespace {
176
177class LoopInstSimplifyLegacyPass : public LoopPass {
178public:
179 static char ID; // Pass ID, replacement for typeid
180
181 LoopInstSimplifyLegacyPass() : LoopPass(ID) {
183 }
184
185 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
186 if (skipLoop(L))
187 return false;
188 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
189 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
190 AssumptionCache &AC =
191 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
192 *L->getHeader()->getParent());
193 const TargetLibraryInfo &TLI =
194 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
195 *L->getHeader()->getParent());
196 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
197 MemorySSAUpdater MSSAU(MSSA);
198
199 return simplifyLoopInst(*L, DT, LI, AC, TLI, &MSSAU);
200 }
201
202 void getAnalysisUsage(AnalysisUsage &AU) const override {
206 AU.setPreservesCFG();
210 }
211};
212
213} // end anonymous namespace
214
217 LPMUpdater &) {
218 std::optional<MemorySSAUpdater> MSSAU;
219 if (AR.MSSA) {
220 MSSAU = MemorySSAUpdater(AR.MSSA);
221 if (VerifyMemorySSA)
222 AR.MSSA->verifyMemorySSA();
223 }
224 if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI,
225 MSSAU ? &*MSSAU : nullptr))
226 return PreservedAnalyses::all();
227
229 PA.preserveSet<CFGAnalyses>();
230 if (AR.MSSA)
231 PA.preserve<MemorySSAAnalysis>();
232 return PA;
233}
234
235char LoopInstSimplifyLegacyPass::ID = 0;
236
237INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
238 "Simplify instructions in loops", false, false)
243INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
244 "Simplify instructions in loops", false, false)
245
247 return new LoopInstSimplifyLegacyPass();
248}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
instsimplify
loops
Definition: LoopInfo.cpp:1176
static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, const TargetLibraryInfo &TLI, MemorySSAUpdater *MSSAU)
#define I(x, y, z)
Definition: MD5.cpp:58
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
print must be executed print the must be executed context for all instructions
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
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)
Definition: Statistic.h:167
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
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...
Definition: LoopIterator.h:172
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:442
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
virtual bool runOnLoop(Loop *L, LPPassManager &LPM)=0
bool skipLoop(const Loop *L) const
Optional passes call this function to check whether the pass should be skipped.
Definition: LoopPass.cpp:370
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:936
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:986
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1862
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Provides information about what library functions are available for the current target.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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.
Definition: Local.cpp:529
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...
Definition: STLExtras.h:748
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
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.
Definition: Local.cpp:398
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:141
void initializeLoopInstSimplifyLegacyPassPass(PassRegistry &)
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:89
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Pass * createLoopInstSimplifyPass()
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
SimplifyQuery getWithInstruction(Instruction *I) const