LLVM  6.0.0svn
LoopInstSimplify.cpp
Go to the documentation of this file.
1 //===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass performs lightweight instruction simplification on loop bodies.
11 //
12 //===----------------------------------------------------------------------===//
13 
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/Analysis/LoopPass.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/CFG.h"
27 #include "llvm/IR/DataLayout.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Instruction.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/IR/PassManager.h"
33 #include "llvm/IR/User.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/Casting.h"
36 #include "llvm/Transforms/Scalar.h"
39 #include <algorithm>
40 #include <utility>
41 
42 using namespace llvm;
43 
44 #define DEBUG_TYPE "loop-instsimplify"
45 
46 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
47 
48 static bool SimplifyLoopInst(Loop *L, DominatorTree *DT, LoopInfo *LI,
49  AssumptionCache *AC,
50  const TargetLibraryInfo *TLI) {
52  L->getUniqueExitBlocks(ExitBlocks);
53  array_pod_sort(ExitBlocks.begin(), ExitBlocks.end());
54 
55  SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
56 
57  // The bit we are stealing from the pointer represents whether this basic
58  // block is the header of a subloop, in which case we only process its phis.
59  using WorklistItem = PointerIntPair<BasicBlock *, 1>;
62 
63  bool Changed = false;
64  bool LocalChanged;
65  do {
66  LocalChanged = false;
67 
68  VisitStack.clear();
69  Visited.clear();
70 
71  VisitStack.push_back(WorklistItem(L->getHeader(), false));
72 
73  while (!VisitStack.empty()) {
74  WorklistItem Item = VisitStack.pop_back_val();
75  BasicBlock *BB = Item.getPointer();
76  bool IsSubloopHeader = Item.getInt();
77  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
78 
79  // Simplify instructions in the current basic block.
80  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
81  Instruction *I = &*BI++;
82 
83  // The first time through the loop ToSimplify is empty and we try to
84  // simplify all instructions. On later iterations ToSimplify is not
85  // empty and we only bother simplifying instructions that are in it.
86  if (!ToSimplify->empty() && !ToSimplify->count(I))
87  continue;
88 
89  // Don't bother simplifying unused instructions.
90  if (!I->use_empty()) {
91  Value *V = SimplifyInstruction(I, {DL, TLI, DT, AC});
92  if (V && LI->replacementPreservesLCSSAForm(I, V)) {
93  // Mark all uses for resimplification next time round the loop.
94  for (User *U : I->users())
95  Next->insert(cast<Instruction>(U));
96 
97  I->replaceAllUsesWith(V);
98  LocalChanged = true;
99  ++NumSimplified;
100  }
101  }
103  // RecursivelyDeleteTriviallyDeadInstruction can remove more than one
104  // instruction, so simply incrementing the iterator does not work.
105  // When instructions get deleted re-iterate instead.
106  BI = BB->begin();
107  BE = BB->end();
108  LocalChanged = true;
109  }
110 
111  if (IsSubloopHeader && !isa<PHINode>(I))
112  break;
113  }
114 
115  // Add all successors to the worklist, except for loop exit blocks and the
116  // bodies of subloops. We visit the headers of loops so that we can
117  // process
118  // their phis, but we contract the rest of the subloop body and only
119  // follow
120  // edges leading back to the original loop.
121  for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE;
122  ++SI) {
123  BasicBlock *SuccBB = *SI;
124  if (!Visited.insert(SuccBB).second)
125  continue;
126 
127  const Loop *SuccLoop = LI->getLoopFor(SuccBB);
128  if (SuccLoop && SuccLoop->getHeader() == SuccBB &&
129  L->contains(SuccLoop)) {
130  VisitStack.push_back(WorklistItem(SuccBB, true));
131 
132  SmallVector<BasicBlock *, 8> SubLoopExitBlocks;
133  SuccLoop->getExitBlocks(SubLoopExitBlocks);
134 
135  for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) {
136  BasicBlock *ExitBB = SubLoopExitBlocks[i];
137  if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB).second)
138  VisitStack.push_back(WorklistItem(ExitBB, false));
139  }
140 
141  continue;
142  }
143 
144  bool IsExitBlock =
145  std::binary_search(ExitBlocks.begin(), ExitBlocks.end(), SuccBB);
146  if (IsExitBlock)
147  continue;
148 
149  VisitStack.push_back(WorklistItem(SuccBB, false));
150  }
151  }
152 
153  // Place the list of instructions to simplify on the next loop iteration
154  // into ToSimplify.
155  std::swap(ToSimplify, Next);
156  Next->clear();
157 
158  Changed |= LocalChanged;
159  } while (LocalChanged);
160 
161  return Changed;
162 }
163 
164 namespace {
165 
166 class LoopInstSimplifyLegacyPass : public LoopPass {
167 public:
168  static char ID; // Pass ID, replacement for typeid
169 
170  LoopInstSimplifyLegacyPass() : LoopPass(ID) {
172  }
173 
174  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
175  if (skipLoop(L))
176  return false;
178  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
179  DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
180  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
181  AssumptionCache *AC =
182  &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
183  *L->getHeader()->getParent());
184  const TargetLibraryInfo *TLI =
185  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
186 
187  return SimplifyLoopInst(L, DT, LI, AC, TLI);
188  }
189 
190  void getAnalysisUsage(AnalysisUsage &AU) const override {
193  AU.setPreservesCFG();
195  }
196 };
197 
198 } // end anonymous namespace
199 
202  LPMUpdater &) {
203  if (!SimplifyLoopInst(&L, &AR.DT, &AR.LI, &AR.AC, &AR.TLI))
204  return PreservedAnalyses::all();
205 
206  auto PA = getLoopPassPreservedAnalyses();
207  PA.preserveSet<CFGAnalyses>();
208  return PA;
209 }
210 
212 
213 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
214  "Simplify instructions in loops", false, false)
218 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
219  "Simplify instructions in loops", false, false)
220 
222  return new LoopInstSimplifyLegacyPass();
223 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
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.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
static bool SimplifyLoopInst(Loop *L, DominatorTree *DT, LoopInfo *LI, AssumptionCache *AC, const TargetLibraryInfo *TLI)
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of .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...
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:678
DominatorTree & getDomTree()
Definition: Dominators.h:277
BlockT * getHeader() const
Definition: LoopInfo.h:100
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:63
Pass * createLoopInstSimplifyPass()
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
loop instsimplify
void getUniqueExitBlocks(SmallVectorImpl< BasicBlock *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfo.cpp:393
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
void initializeLoopInstSimplifyLegacyPassPass(PassRegistry &)
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:759
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
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
PointerIntPair - This class implements a pair of a pointer and small integer.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
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:371
Represent the analysis usage information of a pass.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:401
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:110
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
loop Simplify instructions in loops
iterator end()
Definition: BasicBlock.h:254
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
iterator_range< user_iterator > users()
Definition: Value.h:401
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#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:1023
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
LLVM Value Representation.
Definition: Value.h:73
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form...
Definition: LoopInfo.h:820
This header defines various interfaces for pass management in LLVM.
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
bool use_empty() const
Definition: Value.h:328