LLVM  10.0.0svn
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 
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/Analysis/LoopPass.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/CFG.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/Module.h"
34 #include "llvm/IR/PassManager.h"
35 #include "llvm/IR/User.h"
36 #include "llvm/Pass.h"
37 #include "llvm/Support/Casting.h"
38 #include "llvm/Transforms/Scalar.h"
41 #include <algorithm>
42 #include <utility>
43 
44 using namespace llvm;
45 
46 #define DEBUG_TYPE "loop-instsimplify"
47 
48 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
49 
50 static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
51  AssumptionCache &AC, const TargetLibraryInfo &TLI,
52  MemorySSAUpdater *MSSAU) {
53  const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
54  SimplifyQuery SQ(DL, &TLI, &DT, &AC);
55 
56  // On the first pass over the loop body we try to simplify every instruction.
57  // On subsequent passes, we can restrict this to only simplifying instructions
58  // where the inputs have been updated. We end up needing two sets: one
59  // containing the instructions we are simplifying in *this* pass, and one for
60  // the instructions we will want to simplify in the *next* pass. We use
61  // pointers so we can swap between two stably allocated sets.
62  SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
63 
64  // Track the PHI nodes that have already been visited during each iteration so
65  // that we can identify when it is necessary to iterate.
66  SmallPtrSet<PHINode *, 4> VisitedPHIs;
67 
68  // While simplifying we may discover dead code or cause code to become dead.
69  // Keep track of all such instructions and we will delete them at the end.
71 
72  // First we want to create an RPO traversal of the loop body. By processing in
73  // RPO we can ensure that definitions are processed prior to uses (for non PHI
74  // uses) in all cases. This ensures we maximize the simplifications in each
75  // iteration over the loop and minimizes the possible causes for continuing to
76  // iterate.
77  LoopBlocksRPO RPOT(&L);
78  RPOT.perform(&LI);
79  MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
80 
81  bool Changed = false;
82  for (;;) {
83  if (MSSAU && VerifyMemorySSA)
84  MSSA->verifyMemorySSA();
85  for (BasicBlock *BB : RPOT) {
86  for (Instruction &I : *BB) {
87  if (auto *PI = dyn_cast<PHINode>(&I))
88  VisitedPHIs.insert(PI);
89 
90  if (I.use_empty()) {
91  if (isInstructionTriviallyDead(&I, &TLI))
92  DeadInsts.push_back(&I);
93  continue;
94  }
95 
96  // We special case the first iteration which we can detect due to the
97  // empty `ToSimplify` set.
98  bool IsFirstIteration = ToSimplify->empty();
99 
100  if (!IsFirstIteration && !ToSimplify->count(&I))
101  continue;
102 
104  if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
105  continue;
106 
107  for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
108  UI != UE;) {
109  Use &U = *UI++;
110  auto *UserI = cast<Instruction>(U.getUser());
111  U.set(V);
112 
113  // If the instruction is used by a PHI node we have already processed
114  // we'll need to iterate on the loop body to converge, so add it to
115  // the next set.
116  if (auto *UserPI = dyn_cast<PHINode>(UserI))
117  if (VisitedPHIs.count(UserPI)) {
118  Next->insert(UserPI);
119  continue;
120  }
121 
122  // If we are only simplifying targeted instructions and the user is an
123  // instruction in the loop body, add it to our set of targeted
124  // instructions. Because we process defs before uses (outside of PHIs)
125  // we won't have visited it yet.
126  //
127  // We also skip any uses outside of the loop being simplified. Those
128  // should always be PHI nodes due to LCSSA form, and we don't want to
129  // try to simplify those away.
130  assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
131  "Uses outside the loop should be PHI nodes due to LCSSA!");
132  if (!IsFirstIteration && L.contains(UserI))
133  ToSimplify->insert(UserI);
134  }
135 
136  if (MSSAU)
137  if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V))
138  if (MemoryAccess *MA = MSSA->getMemoryAccess(&I))
139  if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI))
140  MA->replaceAllUsesWith(ReplacementMA);
141 
142  assert(I.use_empty() && "Should always have replaced all uses!");
143  if (isInstructionTriviallyDead(&I, &TLI))
144  DeadInsts.push_back(&I);
145  ++NumSimplified;
146  Changed = true;
147  }
148  }
149 
150  // Delete any dead instructions found thus far now that we've finished an
151  // iteration over all instructions in all the loop blocks.
152  if (!DeadInsts.empty()) {
153  Changed = true;
154  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
155  }
156 
157  if (MSSAU && VerifyMemorySSA)
158  MSSA->verifyMemorySSA();
159 
160  // If we never found a PHI that needs to be simplified in the next
161  // iteration, we're done.
162  if (Next->empty())
163  break;
164 
165  // Otherwise, put the next set in place for the next iteration and reset it
166  // and the visited PHIs for that iteration.
167  std::swap(Next, ToSimplify);
168  Next->clear();
169  VisitedPHIs.clear();
170  DeadInsts.clear();
171  }
172 
173  return Changed;
174 }
175 
176 namespace {
177 
178 class LoopInstSimplifyLegacyPass : public LoopPass {
179 public:
180  static char ID; // Pass ID, replacement for typeid
181 
182  LoopInstSimplifyLegacyPass() : LoopPass(ID) {
184  }
185 
186  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
187  if (skipLoop(L))
188  return false;
189  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
190  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
191  AssumptionCache &AC =
192  getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
193  *L->getHeader()->getParent());
194  const TargetLibraryInfo &TLI =
195  getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
196  MemorySSA *MSSA = nullptr;
199  MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
200  MSSAU = MemorySSAUpdater(MSSA);
201  }
202 
203  return simplifyLoopInst(*L, DT, LI, AC, TLI,
204  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr);
205  }
206 
207  void getAnalysisUsage(AnalysisUsage &AU) const override {
211  AU.setPreservesCFG();
215  }
217  }
218 };
219 
220 } // end anonymous namespace
221 
224  LPMUpdater &) {
226  if (AR.MSSA) {
227  MSSAU = MemorySSAUpdater(AR.MSSA);
228  AR.MSSA->verifyMemorySSA();
229  }
230  if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI,
231  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr))
232  return PreservedAnalyses::all();
233 
234  auto PA = getLoopPassPreservedAnalyses();
235  PA.preserveSet<CFGAnalyses>();
237  PA.preserve<MemorySSAAnalysis>();
238  return PA;
239 }
240 
242 
243 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
244  "Simplify instructions in loops", false, false)
249 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
250  "Simplify instructions in loops", false, false)
251 
253  return new LoopInstSimplifyLegacyPass();
254 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:82
This class represents lattice values for constants.
Definition: AllocatorList.h:23
SimplifyQuery getWithInstruction(Instruction *I) const
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
STATISTIC(NumFunctions, "Total number of functions")
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
AnalysisUsage & addRequired()
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:133
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:963
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:703
static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, const TargetLibraryInfo &TLI, MemorySSAUpdater *MSSAU)
BlockT * getHeader() const
Definition: LoopInfo.h:102
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:40
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref&#39;ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:720
Pass * createLoopInstSimplifyPass()
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
loop instsimplify
use_iterator_impl< Use > use_iterator
Definition: Value.h:331
void initializeLoopInstSimplifyLegacyPassPass(PassRegistry &)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify", "Simplify instructions in loops", false, false) INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass
void set(Value *Val)
Definition: Value.h:710
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
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:370
Represent the analysis usage information of a pass.
const T * getPointer() const
Definition: Optional.h:253
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:440
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:112
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
loop Simplify instructions in loops
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1848
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:924
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
bool hasValue() const
Definition: Optional.h:259
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:506
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:136
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:359
LLVM Value Representation.
Definition: Value.h:72
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
inst_range instructions(Function *F)
Definition: InstIterator.h:133
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form...
Definition: LoopInfo.h:1039
This header defines various interfaces for pass management in LLVM.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.