LLVM 19.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"
36#include <optional>
37#include <utility>
38
39using namespace llvm;
40
41#define DEBUG_TYPE "loop-instsimplify"
42
43STATISTIC(NumSimplified, "Number of redundant instructions simplified");
44
46 AssumptionCache &AC, const TargetLibraryInfo &TLI,
47 MemorySSAUpdater *MSSAU) {
48 const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
49 SimplifyQuery SQ(DL, &TLI, &DT, &AC);
50
51 // On the first pass over the loop body we try to simplify every instruction.
52 // On subsequent passes, we can restrict this to only simplifying instructions
53 // where the inputs have been updated. We end up needing two sets: one
54 // containing the instructions we are simplifying in *this* pass, and one for
55 // the instructions we will want to simplify in the *next* pass. We use
56 // pointers so we can swap between two stably allocated sets.
58
59 // Track the PHI nodes that have already been visited during each iteration so
60 // that we can identify when it is necessary to iterate.
61 SmallPtrSet<PHINode *, 4> VisitedPHIs;
62
63 // While simplifying we may discover dead code or cause code to become dead.
64 // Keep track of all such instructions and we will delete them at the end.
66
67 // First we want to create an RPO traversal of the loop body. By processing in
68 // RPO we can ensure that definitions are processed prior to uses (for non PHI
69 // uses) in all cases. This ensures we maximize the simplifications in each
70 // iteration over the loop and minimizes the possible causes for continuing to
71 // iterate.
72 LoopBlocksRPO RPOT(&L);
73 RPOT.perform(&LI);
74 MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
75
76 bool Changed = false;
77 for (;;) {
78 if (MSSAU && VerifyMemorySSA)
79 MSSA->verifyMemorySSA();
80 for (BasicBlock *BB : RPOT) {
81 for (Instruction &I : *BB) {
82 if (auto *PI = dyn_cast<PHINode>(&I))
83 VisitedPHIs.insert(PI);
84
85 if (I.use_empty()) {
86 if (isInstructionTriviallyDead(&I, &TLI))
87 DeadInsts.push_back(&I);
88 continue;
89 }
90
91 // We special case the first iteration which we can detect due to the
92 // empty `ToSimplify` set.
93 bool IsFirstIteration = ToSimplify->empty();
94
95 if (!IsFirstIteration && !ToSimplify->count(&I))
96 continue;
97
99 if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
100 continue;
101
102 for (Use &U : llvm::make_early_inc_range(I.uses())) {
103 auto *UserI = cast<Instruction>(U.getUser());
104 U.set(V);
105
106 // Do not bother dealing with unreachable code.
107 if (!DT.isReachableFromEntry(UserI->getParent()))
108 continue;
109
110 // If the instruction is used by a PHI node we have already processed
111 // we'll need to iterate on the loop body to converge, so add it to
112 // the next set.
113 if (auto *UserPI = dyn_cast<PHINode>(UserI))
114 if (VisitedPHIs.count(UserPI)) {
115 Next->insert(UserPI);
116 continue;
117 }
118
119 // If we are only simplifying targeted instructions and the user is an
120 // instruction in the loop body, add it to our set of targeted
121 // instructions. Because we process defs before uses (outside of PHIs)
122 // we won't have visited it yet.
123 //
124 // We also skip any uses outside of the loop being simplified. Those
125 // should always be PHI nodes due to LCSSA form, and we don't want to
126 // try to simplify those away.
127 assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
128 "Uses outside the loop should be PHI nodes due to LCSSA!");
129 if (!IsFirstIteration && L.contains(UserI))
130 ToSimplify->insert(UserI);
131 }
132
133 if (MSSAU)
134 if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V))
135 if (MemoryAccess *MA = MSSA->getMemoryAccess(&I))
136 if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI))
137 MA->replaceAllUsesWith(ReplacementMA);
138
139 assert(I.use_empty() && "Should always have replaced all uses!");
140 if (isInstructionTriviallyDead(&I, &TLI))
141 DeadInsts.push_back(&I);
142 ++NumSimplified;
143 Changed = true;
144 }
145 }
146
147 // Delete any dead instructions found thus far now that we've finished an
148 // iteration over all instructions in all the loop blocks.
149 if (!DeadInsts.empty()) {
150 Changed = true;
151 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
152 }
153
154 if (MSSAU && VerifyMemorySSA)
155 MSSA->verifyMemorySSA();
156
157 // If we never found a PHI that needs to be simplified in the next
158 // iteration, we're done.
159 if (Next->empty())
160 break;
161
162 // Otherwise, put the next set in place for the next iteration and reset it
163 // and the visited PHIs for that iteration.
164 std::swap(Next, ToSimplify);
165 Next->clear();
166 VisitedPHIs.clear();
167 DeadInsts.clear();
168 }
169
170 return Changed;
171}
172
175 LPMUpdater &) {
176 std::optional<MemorySSAUpdater> MSSAU;
177 if (AR.MSSA) {
178 MSSAU = MemorySSAUpdater(AR.MSSA);
179 if (VerifyMemorySSA)
180 AR.MSSA->verifyMemorySSA();
181 }
182 if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI,
183 MSSAU ? &*MSSAU : nullptr))
184 return PreservedAnalyses::all();
185
187 PA.preserveSet<CFGAnalyses>();
188 if (AR.MSSA)
189 PA.preserve<MemorySSAAnalysis>();
190 return PA;
191}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const LLT S1
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.
SmallVector< Instruction *, 4 > ToSimplify
Definition: NVVMReflect.cpp:94
This header defines various interfaces for pass management in LLVM.
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:348
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
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(const 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:439
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:923
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
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:1857
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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
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:533
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:665
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:399
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
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.
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(const Instruction *I) const
Definition: SimplifyQuery.h:96