LLVM  16.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"
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/Analysis/LoopPass.h"
26 #include "llvm/IR/BasicBlock.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/IR/PassManager.h"
32 #include "llvm/InitializePasses.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/Casting.h"
35 #include "llvm/Transforms/Scalar.h"
38 #include <utility>
39 
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "loop-instsimplify"
43 
44 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
45 
46 static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
47  AssumptionCache &AC, const TargetLibraryInfo &TLI,
48  MemorySSAUpdater *MSSAU) {
49  const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
50  SimplifyQuery SQ(DL, &TLI, &DT, &AC);
51 
52  // On the first pass over the loop body we try to simplify every instruction.
53  // On subsequent passes, we can restrict this to only simplifying instructions
54  // where the inputs have been updated. We end up needing two sets: one
55  // containing the instructions we are simplifying in *this* pass, and one for
56  // the instructions we will want to simplify in the *next* pass. We use
57  // pointers so we can swap between two stably allocated sets.
58  SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
59 
60  // Track the PHI nodes that have already been visited during each iteration so
61  // that we can identify when it is necessary to iterate.
62  SmallPtrSet<PHINode *, 4> VisitedPHIs;
63 
64  // While simplifying we may discover dead code or cause code to become dead.
65  // Keep track of all such instructions and we will delete them at the end.
67 
68  // First we want to create an RPO traversal of the loop body. By processing in
69  // RPO we can ensure that definitions are processed prior to uses (for non PHI
70  // uses) in all cases. This ensures we maximize the simplifications in each
71  // iteration over the loop and minimizes the possible causes for continuing to
72  // iterate.
73  LoopBlocksRPO RPOT(&L);
74  RPOT.perform(&LI);
75  MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
76 
77  bool Changed = false;
78  for (;;) {
79  if (MSSAU && VerifyMemorySSA)
80  MSSA->verifyMemorySSA();
81  for (BasicBlock *BB : RPOT) {
82  for (Instruction &I : *BB) {
83  if (auto *PI = dyn_cast<PHINode>(&I))
84  VisitedPHIs.insert(PI);
85 
86  if (I.use_empty()) {
87  if (isInstructionTriviallyDead(&I, &TLI))
88  DeadInsts.push_back(&I);
89  continue;
90  }
91 
92  // We special case the first iteration which we can detect due to the
93  // empty `ToSimplify` set.
94  bool IsFirstIteration = ToSimplify->empty();
95 
96  if (!IsFirstIteration && !ToSimplify->count(&I))
97  continue;
98 
100  if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
101  continue;
102 
103  for (Use &U : llvm::make_early_inc_range(I.uses())) {
104  auto *UserI = cast<Instruction>(U.getUser());
105  U.set(V);
106 
107  // Do not bother dealing with unreachable code.
108  if (!DT.isReachableFromEntry(UserI->getParent()))
109  continue;
110 
111  // If the instruction is used by a PHI node we have already processed
112  // we'll need to iterate on the loop body to converge, so add it to
113  // the next set.
114  if (auto *UserPI = dyn_cast<PHINode>(UserI))
115  if (VisitedPHIs.count(UserPI)) {
116  Next->insert(UserPI);
117  continue;
118  }
119 
120  // If we are only simplifying targeted instructions and the user is an
121  // instruction in the loop body, add it to our set of targeted
122  // instructions. Because we process defs before uses (outside of PHIs)
123  // we won't have visited it yet.
124  //
125  // We also skip any uses outside of the loop being simplified. Those
126  // should always be PHI nodes due to LCSSA form, and we don't want to
127  // try to simplify those away.
128  assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
129  "Uses outside the loop should be PHI nodes due to LCSSA!");
130  if (!IsFirstIteration && L.contains(UserI))
131  ToSimplify->insert(UserI);
132  }
133 
134  if (MSSAU)
135  if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V))
136  if (MemoryAccess *MA = MSSA->getMemoryAccess(&I))
137  if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI))
138  MA->replaceAllUsesWith(ReplacementMA);
139 
140  assert(I.use_empty() && "Should always have replaced all uses!");
141  if (isInstructionTriviallyDead(&I, &TLI))
142  DeadInsts.push_back(&I);
143  ++NumSimplified;
144  Changed = true;
145  }
146  }
147 
148  // Delete any dead instructions found thus far now that we've finished an
149  // iteration over all instructions in all the loop blocks.
150  if (!DeadInsts.empty()) {
151  Changed = true;
152  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
153  }
154 
155  if (MSSAU && VerifyMemorySSA)
156  MSSA->verifyMemorySSA();
157 
158  // If we never found a PHI that needs to be simplified in the next
159  // iteration, we're done.
160  if (Next->empty())
161  break;
162 
163  // Otherwise, put the next set in place for the next iteration and reset it
164  // and the visited PHIs for that iteration.
165  std::swap(Next, ToSimplify);
166  Next->clear();
167  VisitedPHIs.clear();
168  DeadInsts.clear();
169  }
170 
171  return Changed;
172 }
173 
174 namespace {
175 
176 class LoopInstSimplifyLegacyPass : public LoopPass {
177 public:
178  static char ID; // Pass ID, replacement for typeid
179 
180  LoopInstSimplifyLegacyPass() : LoopPass(ID) {
182  }
183 
184  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
185  if (skipLoop(L))
186  return false;
187  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
188  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
189  AssumptionCache &AC =
190  getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
191  *L->getHeader()->getParent());
192  const TargetLibraryInfo &TLI =
193  getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
194  *L->getHeader()->getParent());
195  MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
196  MemorySSAUpdater MSSAU(MSSA);
197 
198  return simplifyLoopInst(*L, DT, LI, AC, TLI, &MSSAU);
199  }
200 
201  void getAnalysisUsage(AnalysisUsage &AU) const override {
205  AU.setPreservesCFG();
209  }
210 };
211 
212 } // end anonymous namespace
213 
216  LPMUpdater &) {
218  if (AR.MSSA) {
219  MSSAU = MemorySSAUpdater(AR.MSSA);
220  if (VerifyMemorySSA)
221  AR.MSSA->verifyMemorySSA();
222  }
223  if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI,
224  MSSAU ? MSSAU.getPointer() : nullptr))
225  return PreservedAnalyses::all();
226 
227  auto PA = getLoopPassPreservedAnalyses();
228  PA.preserveSet<CFGAnalyses>();
229  if (AR.MSSA)
230  PA.preserve<MemorySSAAnalysis>();
231  return PA;
232 }
233 
235 
236 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
237  "Simplify instructions in loops", false, false)
242 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
244 
246  return new LoopInstSimplifyLegacyPass();
247 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::RecursivelyDeleteTriviallyDeadInstructions
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:518
AssumptionCache.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::MemorySSA::verifyMemorySSA
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:1861
llvm::LoopStandardAnalysisResults::AC
AssumptionCache & AC
Definition: LoopAnalysisManager.h:53
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::LoopInstSimplifyPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopInstSimplify.cpp:214
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
Scalar.h
MemorySSAUpdater.h
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1181
Statistic.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:142
Module.h
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
STLExtras.h
LoopInstSimplify.h
loops
loop Simplify instructions in loops
Definition: LoopInstSimplify.cpp:243
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:54
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::Optional::getPointer
constexpr const T * getPointer() const
Definition: Optional.h:311
llvm::LoopBlocksRPO
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
Instruction.h
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:984
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify", "Simplify instructions in loops", false, false) INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass
TargetLibraryInfo.h
llvm::LoopInfo::replacementPreservesLCSSAForm
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:1137
false
Definition: StackSlotColoring.cpp:141
in
The object format emitted by the WebAssembly backed is documented in
Definition: README.txt:11
llvm::Instruction
Definition: Instruction.h:42
simplifyLoopInst
static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, const TargetLibraryInfo &TLI, MemorySSAUpdater *MSSAU)
Definition: LoopInstSimplify.cpp:46
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
LoopUtils.h
llvm::LPPassManager
Definition: LoopPass.h:76
SmallPtrSet.h
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:147
LoopIterator.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::SmallPtrSetImplBase::empty
bool empty() const
Definition: SmallPtrSet.h:92
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:137
BasicBlock.h
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:468
llvm::LoopPass
Definition: LoopPass.h:28
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:242
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
llvm::make_early_inc_range
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:596
llvm::simplifyInstruction
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6510
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::SimplifyQuery::getWithInstruction
SimplifyQuery getWithInstruction(Instruction *I) const
Definition: InstructionSimplify.h:120
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:934
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::isInstructionTriviallyDead
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:395
llvm::LoopInfo
Definition: LoopInfo.h:1105
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
Simplify
assume Assume Simplify
Definition: AssumeBundleBuilder.cpp:604
LoopPass.h
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:55
llvm::MemoryAccess
Definition: MemorySSA.h:142
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::initializeLoopInstSimplifyLegacyPassPass
void initializeLoopInstSimplifyLegacyPassPass(PassRegistry &)
Casting.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:596
instsimplify
loop instsimplify
Definition: LoopInstSimplify.cpp:242
llvm::createLoopInstSimplifyPass
Pass * createLoopInstSimplifyPass()
Definition: LoopInstSimplify.cpp:245
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
MemorySSA.h
Instructions.h
SmallVector.h
Dominators.h
InstructionSimplify.h
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
BB
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
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
llvm::LoopBlocksRPO::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
llvm::LoopStandardAnalysisResults::TLI
TargetLibraryInfo & TLI
Definition: LoopAnalysisManager.h:57
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
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
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38