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