LLVM  6.0.0svn
Sink.cpp
Go to the documentation of this file.
1 //===-- Sink.cpp - Code Sinking -------------------------------------------===//
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 moves instructions into successor blocks, when possible, so that
11 // they aren't executed on paths where their results aren't needed.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/Statistic.h"
18 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/IR/CFG.h"
21 #include "llvm/IR/DataLayout.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/IntrinsicInst.h"
24 #include "llvm/IR/Module.h"
25 #include "llvm/Support/Debug.h"
27 #include "llvm/Transforms/Scalar.h"
28 using namespace llvm;
29 
30 #define DEBUG_TYPE "sink"
31 
32 STATISTIC(NumSunk, "Number of instructions sunk");
33 STATISTIC(NumSinkIter, "Number of sinking iterations");
34 
35 /// AllUsesDominatedByBlock - Return true if all uses of the specified value
36 /// occur in blocks dominated by the specified block.
38  DominatorTree &DT) {
39  // Ignoring debug uses is necessary so debug info doesn't affect the code.
40  // This may leave a referencing dbg_value in the original block, before
41  // the definition of the vreg. Dwarf generator handles this although the
42  // user might not get the right info at runtime.
43  for (Use &U : Inst->uses()) {
44  // Determine the block of the use.
45  Instruction *UseInst = cast<Instruction>(U.getUser());
46  BasicBlock *UseBlock = UseInst->getParent();
47  if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
48  // PHI nodes use the operand in the predecessor block, not the block with
49  // the PHI.
50  unsigned Num = PHINode::getIncomingValueNumForOperand(U.getOperandNo());
51  UseBlock = PN->getIncomingBlock(Num);
52  }
53  // Check that it dominates.
54  if (!DT.dominates(BB, UseBlock))
55  return false;
56  }
57  return true;
58 }
59 
60 static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA,
62 
63  if (Inst->mayWriteToMemory()) {
64  Stores.insert(Inst);
65  return false;
66  }
67 
68  if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
70  for (Instruction *S : Stores)
71  if (AA.getModRefInfo(S, Loc) & MRI_Mod)
72  return false;
73  }
74 
75  if (isa<TerminatorInst>(Inst) || isa<PHINode>(Inst) || Inst->isEHPad() ||
76  Inst->mayThrow())
77  return false;
78 
79  if (auto CS = CallSite(Inst)) {
80  // Convergent operations cannot be made control-dependent on additional
81  // values.
82  if (CS.hasFnAttr(Attribute::Convergent))
83  return false;
84 
85  for (Instruction *S : Stores)
86  if (AA.getModRefInfo(S, CS) & MRI_Mod)
87  return false;
88  }
89 
90  return true;
91 }
92 
93 /// IsAcceptableTarget - Return true if it is possible to sink the instruction
94 /// in the specified basic block.
95 static bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo,
96  DominatorTree &DT, LoopInfo &LI) {
97  assert(Inst && "Instruction to be sunk is null");
98  assert(SuccToSinkTo && "Candidate sink target is null");
99 
100  // It is not possible to sink an instruction into its own block. This can
101  // happen with loops.
102  if (Inst->getParent() == SuccToSinkTo)
103  return false;
104 
105  // It's never legal to sink an instruction into a block which terminates in an
106  // EH-pad.
107  if (SuccToSinkTo->getTerminator()->isExceptional())
108  return false;
109 
110  // If the block has multiple predecessors, this would introduce computation
111  // on different code paths. We could split the critical edge, but for now we
112  // just punt.
113  // FIXME: Split critical edges if not backedges.
114  if (SuccToSinkTo->getUniquePredecessor() != Inst->getParent()) {
115  // We cannot sink a load across a critical edge - there may be stores in
116  // other code paths.
117  if (isa<LoadInst>(Inst))
118  return false;
119 
120  // We don't want to sink across a critical edge if we don't dominate the
121  // successor. We could be introducing calculations to new code paths.
122  if (!DT.dominates(Inst->getParent(), SuccToSinkTo))
123  return false;
124 
125  // Don't sink instructions into a loop.
126  Loop *succ = LI.getLoopFor(SuccToSinkTo);
127  Loop *cur = LI.getLoopFor(Inst->getParent());
128  if (succ != nullptr && succ != cur)
129  return false;
130  }
131 
132  // Finally, check that all the uses of the instruction are actually
133  // dominated by the candidate
134  return AllUsesDominatedByBlock(Inst, SuccToSinkTo, DT);
135 }
136 
137 /// SinkInstruction - Determine whether it is safe to sink the specified machine
138 /// instruction out of its current block into a successor.
139 static bool SinkInstruction(Instruction *Inst,
141  DominatorTree &DT, LoopInfo &LI, AAResults &AA) {
142 
143  // Don't sink static alloca instructions. CodeGen assumes allocas outside the
144  // entry block are dynamically sized stack objects.
145  if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst))
146  if (AI->isStaticAlloca())
147  return false;
148 
149  // Check if it's safe to move the instruction.
150  if (!isSafeToMove(Inst, AA, Stores))
151  return false;
152 
153  // FIXME: This should include support for sinking instructions within the
154  // block they are currently in to shorten the live ranges. We often get
155  // instructions sunk into the top of a large block, but it would be better to
156  // also sink them down before their first use in the block. This xform has to
157  // be careful not to *increase* register pressure though, e.g. sinking
158  // "x = y + z" down if it kills y and z would increase the live ranges of y
159  // and z and only shrink the live range of x.
160 
161  // SuccToSinkTo - This is the successor to sink this instruction to, once we
162  // decide.
163  BasicBlock *SuccToSinkTo = nullptr;
164 
165  // Instructions can only be sunk if all their uses are in blocks
166  // dominated by one of the successors.
167  // Look at all the dominated blocks and see if we can sink it in one.
168  DomTreeNode *DTN = DT.getNode(Inst->getParent());
169  for (DomTreeNode::iterator I = DTN->begin(), E = DTN->end();
170  I != E && SuccToSinkTo == nullptr; ++I) {
171  BasicBlock *Candidate = (*I)->getBlock();
172  // A node always immediate-dominates its children on the dominator
173  // tree.
174  if (IsAcceptableTarget(Inst, Candidate, DT, LI))
175  SuccToSinkTo = Candidate;
176  }
177 
178  // If no suitable postdominator was found, look at all the successors and
179  // decide which one we should sink to, if any.
180  for (succ_iterator I = succ_begin(Inst->getParent()),
181  E = succ_end(Inst->getParent()); I != E && !SuccToSinkTo; ++I) {
182  if (IsAcceptableTarget(Inst, *I, DT, LI))
183  SuccToSinkTo = *I;
184  }
185 
186  // If we couldn't find a block to sink to, ignore this instruction.
187  if (!SuccToSinkTo)
188  return false;
189 
190  DEBUG(dbgs() << "Sink" << *Inst << " (";
191  Inst->getParent()->printAsOperand(dbgs(), false);
192  dbgs() << " -> ";
193  SuccToSinkTo->printAsOperand(dbgs(), false);
194  dbgs() << ")\n");
195 
196  // Move the instruction.
197  Inst->moveBefore(&*SuccToSinkTo->getFirstInsertionPt());
198  return true;
199 }
200 
201 static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI,
202  AAResults &AA) {
203  // Can't sink anything out of a block that has less than two successors.
204  if (BB.getTerminator()->getNumSuccessors() <= 1) return false;
205 
206  // Don't bother sinking code out of unreachable blocks. In addition to being
207  // unprofitable, it can also lead to infinite looping, because in an
208  // unreachable loop there may be nowhere to stop.
209  if (!DT.isReachableFromEntry(&BB)) return false;
210 
211  bool MadeChange = false;
212 
213  // Walk the basic block bottom-up. Remember if we saw a store.
214  BasicBlock::iterator I = BB.end();
215  --I;
216  bool ProcessedBegin = false;
218  do {
219  Instruction *Inst = &*I; // The instruction to sink.
220 
221  // Predecrement I (if it's not begin) so that it isn't invalidated by
222  // sinking.
223  ProcessedBegin = I == BB.begin();
224  if (!ProcessedBegin)
225  --I;
226 
227  if (isa<DbgInfoIntrinsic>(Inst))
228  continue;
229 
230  if (SinkInstruction(Inst, Stores, DT, LI, AA)) {
231  ++NumSunk;
232  MadeChange = true;
233  }
234 
235  // If we just processed the first instruction in the block, we're done.
236  } while (!ProcessedBegin);
237 
238  return MadeChange;
239 }
240 
242  LoopInfo &LI, AAResults &AA) {
243  bool MadeChange, EverMadeChange = false;
244 
245  do {
246  MadeChange = false;
247  DEBUG(dbgs() << "Sinking iteration " << NumSinkIter << "\n");
248  // Process all basic blocks.
249  for (BasicBlock &I : F)
250  MadeChange |= ProcessBlock(I, DT, LI, AA);
251  EverMadeChange |= MadeChange;
252  NumSinkIter++;
253  } while (MadeChange);
254 
255  return EverMadeChange;
256 }
257 
259  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
260  auto &LI = AM.getResult<LoopAnalysis>(F);
261  auto &AA = AM.getResult<AAManager>(F);
262 
263  if (!iterativelySinkInstructions(F, DT, LI, AA))
264  return PreservedAnalyses::all();
265 
267  PA.preserveSet<CFGAnalyses>();
268  return PA;
269 }
270 
271 namespace {
272  class SinkingLegacyPass : public FunctionPass {
273  public:
274  static char ID; // Pass identification
275  SinkingLegacyPass() : FunctionPass(ID) {
277  }
278 
279  bool runOnFunction(Function &F) override {
280  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
281  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
282  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
283 
284  return iterativelySinkInstructions(F, DT, LI, AA);
285  }
286 
287  void getAnalysisUsage(AnalysisUsage &AU) const override {
288  AU.setPreservesCFG();
295  }
296  };
297 } // end anonymous namespace
298 
299 char SinkingLegacyPass::ID = 0;
300 INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false)
304 INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false)
305 
306 FunctionPass *llvm::createSinkingPass() { return new SinkingLegacyPass(); }
DomTreeNodeBase< NodeT > * getNode(NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
iterator_range< use_iterator > uses()
Definition: Value.h:350
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...
static bool AllUsesDominatedByBlock(Instruction *Inst, BasicBlock *BB, DominatorTree &DT)
AllUsesDominatedByBlock - Return true if all uses of the specified value occur in blocks dominated by...
Definition: Sink.cpp:37
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Sink.cpp:258
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:232
An instruction for reading from memory.
Definition: Instructions.h:164
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:285
The access modifies the value stored in memory.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:585
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
FunctionPass * createSinkingPass()
Definition: Sink.cpp:306
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:820
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:106
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:84
#define F(x, y, z)
Definition: MD5.cpp:55
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:230
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:201
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:134
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:109
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
A manager for alias analyses.
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:372
bool mayThrow() const
Return true if this instruction may throw an exception.
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
void initializeSinkingLegacyPassPass(PassRegistry &)
static bool SinkInstruction(Instruction *Inst, SmallPtrSetImpl< Instruction *> &Stores, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
SinkInstruction - Determine whether it is safe to sink the specified machine instruction out of its c...
Definition: Sink.cpp:139
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
static unsigned getIncomingValueNumForOperand(unsigned i)
static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA, SmallPtrSetImpl< Instruction *> &Stores)
Definition: Sink.cpp:60
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:3538
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Representation for a specific memory location.
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:423
#define E
Definition: LargeTest.cpp:27
iterator end()
Definition: BasicBlock.h:254
bool isExceptional() const
Definition: InstrTypes.h:84
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:234
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:48
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:278
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
static bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo, DominatorTree &DT, LoopInfo &LI)
IsAcceptableTarget - Return true if it is possible to sink the instruction in the specified basic blo...
Definition: Sink.cpp:95
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:360
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
#define I(x, y, z)
Definition: MD5.cpp:58
static bool iterativelySinkInstructions(Function &F, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:241
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
typename std::vector< DomTreeNodeBase *>::iterator iterator
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:88
#define DEBUG(X)
Definition: Debug.h:118
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:503
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:845
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:261
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:60