LLVM  13.0.0git
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/InitializePasses.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 static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA,
37 
38  if (Inst->mayWriteToMemory()) {
39  Stores.insert(Inst);
40  return false;
41  }
42 
43  if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
45  for (Instruction *S : Stores)
46  if (isModSet(AA.getModRefInfo(S, Loc)))
47  return false;
48  }
49 
50  if (Inst->isTerminator() || isa<PHINode>(Inst) || Inst->isEHPad() ||
51  Inst->mayThrow())
52  return false;
53 
54  if (auto *Call = dyn_cast<CallBase>(Inst)) {
55  // Convergent operations cannot be made control-dependent on additional
56  // values.
57  if (Call->isConvergent())
58  return false;
59 
60  for (Instruction *S : Stores)
61  if (isModSet(AA.getModRefInfo(S, Call)))
62  return false;
63  }
64 
65  return true;
66 }
67 
68 /// IsAcceptableTarget - Return true if it is possible to sink the instruction
69 /// in the specified basic block.
70 static bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo,
71  DominatorTree &DT, LoopInfo &LI) {
72  assert(Inst && "Instruction to be sunk is null");
73  assert(SuccToSinkTo && "Candidate sink target is null");
74 
75  // It's never legal to sink an instruction into a block which terminates in an
76  // EH-pad.
77  if (SuccToSinkTo->getTerminator()->isExceptionalTerminator())
78  return false;
79 
80  // If the block has multiple predecessors, this would introduce computation
81  // on different code paths. We could split the critical edge, but for now we
82  // just punt.
83  // FIXME: Split critical edges if not backedges.
84  if (SuccToSinkTo->getUniquePredecessor() != Inst->getParent()) {
85  // We cannot sink a load across a critical edge - there may be stores in
86  // other code paths.
87  if (Inst->mayReadFromMemory())
88  return false;
89 
90  // We don't want to sink across a critical edge if we don't dominate the
91  // successor. We could be introducing calculations to new code paths.
92  if (!DT.dominates(Inst->getParent(), SuccToSinkTo))
93  return false;
94 
95  // Don't sink instructions into a loop.
96  Loop *succ = LI.getLoopFor(SuccToSinkTo);
97  Loop *cur = LI.getLoopFor(Inst->getParent());
98  if (succ != nullptr && succ != cur)
99  return false;
100  }
101 
102  return true;
103 }
104 
105 /// SinkInstruction - Determine whether it is safe to sink the specified machine
106 /// instruction out of its current block into a successor.
107 static bool SinkInstruction(Instruction *Inst,
109  DominatorTree &DT, LoopInfo &LI, AAResults &AA) {
110 
111  // Don't sink static alloca instructions. CodeGen assumes allocas outside the
112  // entry block are dynamically sized stack objects.
113  if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst))
114  if (AI->isStaticAlloca())
115  return false;
116 
117  // Check if it's safe to move the instruction.
118  if (!isSafeToMove(Inst, AA, Stores))
119  return false;
120 
121  // FIXME: This should include support for sinking instructions within the
122  // block they are currently in to shorten the live ranges. We often get
123  // instructions sunk into the top of a large block, but it would be better to
124  // also sink them down before their first use in the block. This xform has to
125  // be careful not to *increase* register pressure though, e.g. sinking
126  // "x = y + z" down if it kills y and z would increase the live ranges of y
127  // and z and only shrink the live range of x.
128 
129  // SuccToSinkTo - This is the successor to sink this instruction to, once we
130  // decide.
131  BasicBlock *SuccToSinkTo = nullptr;
132 
133  // Find the nearest common dominator of all users as the candidate.
134  BasicBlock *BB = Inst->getParent();
135  for (Use &U : Inst->uses()) {
136  Instruction *UseInst = cast<Instruction>(U.getUser());
137  BasicBlock *UseBlock = UseInst->getParent();
138  // Don't worry about dead users.
139  if (!DT.isReachableFromEntry(UseBlock))
140  continue;
141  if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
142  // PHI nodes use the operand in the predecessor block, not the block with
143  // the PHI.
144  unsigned Num = PHINode::getIncomingValueNumForOperand(U.getOperandNo());
145  UseBlock = PN->getIncomingBlock(Num);
146  }
147  if (SuccToSinkTo)
148  SuccToSinkTo = DT.findNearestCommonDominator(SuccToSinkTo, UseBlock);
149  else
150  SuccToSinkTo = UseBlock;
151  // The current basic block needs to dominate the candidate.
152  if (!DT.dominates(BB, SuccToSinkTo))
153  return false;
154  }
155 
156  if (SuccToSinkTo) {
157  // The nearest common dominator may be in a parent loop of BB, which may not
158  // be beneficial. Find an ancestor.
159  while (SuccToSinkTo != BB &&
160  !IsAcceptableTarget(Inst, SuccToSinkTo, DT, LI))
161  SuccToSinkTo = DT.getNode(SuccToSinkTo)->getIDom()->getBlock();
162  if (SuccToSinkTo == BB)
163  SuccToSinkTo = nullptr;
164  }
165 
166  // If we couldn't find a block to sink to, ignore this instruction.
167  if (!SuccToSinkTo)
168  return false;
169 
170  LLVM_DEBUG(dbgs() << "Sink" << *Inst << " (";
171  Inst->getParent()->printAsOperand(dbgs(), false); dbgs() << " -> ";
172  SuccToSinkTo->printAsOperand(dbgs(), false); dbgs() << ")\n");
173 
174  // Move the instruction.
175  Inst->moveBefore(&*SuccToSinkTo->getFirstInsertionPt());
176  return true;
177 }
178 
180  AAResults &AA) {
181  // Can't sink anything out of a block that has less than two successors.
182  if (BB.getTerminator()->getNumSuccessors() <= 1) return false;
183 
184  // Don't bother sinking code out of unreachable blocks. In addition to being
185  // unprofitable, it can also lead to infinite looping, because in an
186  // unreachable loop there may be nowhere to stop.
187  if (!DT.isReachableFromEntry(&BB)) return false;
188 
189  bool MadeChange = false;
190 
191  // Walk the basic block bottom-up. Remember if we saw a store.
192  BasicBlock::iterator I = BB.end();
193  --I;
194  bool ProcessedBegin = false;
196  do {
197  Instruction *Inst = &*I; // The instruction to sink.
198 
199  // Predecrement I (if it's not begin) so that it isn't invalidated by
200  // sinking.
201  ProcessedBegin = I == BB.begin();
202  if (!ProcessedBegin)
203  --I;
204 
205  if (Inst->isDebugOrPseudoInst())
206  continue;
207 
208  if (SinkInstruction(Inst, Stores, DT, LI, AA)) {
209  ++NumSunk;
210  MadeChange = true;
211  }
212 
213  // If we just processed the first instruction in the block, we're done.
214  } while (!ProcessedBegin);
215 
216  return MadeChange;
217 }
218 
220  LoopInfo &LI, AAResults &AA) {
221  bool MadeChange, EverMadeChange = false;
222 
223  do {
224  MadeChange = false;
225  LLVM_DEBUG(dbgs() << "Sinking iteration " << NumSinkIter << "\n");
226  // Process all basic blocks.
227  for (BasicBlock &I : F)
228  MadeChange |= ProcessBlock(I, DT, LI, AA);
229  EverMadeChange |= MadeChange;
230  NumSinkIter++;
231  } while (MadeChange);
232 
233  return EverMadeChange;
234 }
235 
237  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
238  auto &LI = AM.getResult<LoopAnalysis>(F);
239  auto &AA = AM.getResult<AAManager>(F);
240 
241  if (!iterativelySinkInstructions(F, DT, LI, AA))
242  return PreservedAnalyses::all();
243 
245  PA.preserveSet<CFGAnalyses>();
246  return PA;
247 }
248 
249 namespace {
250  class SinkingLegacyPass : public FunctionPass {
251  public:
252  static char ID; // Pass identification
253  SinkingLegacyPass() : FunctionPass(ID) {
255  }
256 
257  bool runOnFunction(Function &F) override {
258  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
259  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
260  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
261 
262  return iterativelySinkInstructions(F, DT, LI, AA);
263  }
264 
265  void getAnalysisUsage(AnalysisUsage &AU) const override {
266  AU.setPreservesCFG();
273  }
274  };
275 } // end anonymous namespace
276 
277 char SinkingLegacyPass::ID = 0;
278 INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false)
282 INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false)
283 
284 FunctionPass *llvm::createSinkingPass() { return new SinkingLegacyPass(); }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:163
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1221
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:37
llvm
Definition: AllocatorList.h:23
llvm::DominatorTreeBase::findNearestCommonDominator
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
Definition: GenericDomTree.h:468
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
Scalar.h
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Statistic.h
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
Module.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1258
SinkInstruction
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:107
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::Instruction::mayThrow
bool mayThrow() const
Return true if this instruction may throw an exception.
Definition: Instruction.cpp:652
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::Instruction::isExceptionalTerminator
bool isExceptionalTerminator() const
Definition: Instruction.h:170
sinking
Machine code sinking
Definition: MachineSink.cpp:265
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::AAResults
Definition: AliasAnalysis.h:456
IsAcceptableTarget
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:70
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:389
iterativelySinkInstructions
static bool iterativelySinkInstructions(Function &F, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:219
llvm::BasicBlock::getFirstInsertionPt
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:249
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::createSinkingPass
FunctionPass * createSinkingPass()
Definition: Sink.cpp:284
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:563
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
LoopInfo.h
llvm::PHINode::getIncomingValueNumForOperand
static unsigned getIncomingValueNumForOperand(unsigned i)
Definition: Instructions.h:2682
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:964
I
#define I(x, y, z)
Definition: MD5.cpp:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::SinkingPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Sink.cpp:236
llvm::Value::printAsOperand
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:4691
sink
gvn sink
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
Definition: GVNSink.cpp:927
llvm::LoopInfo
Definition: LoopInfo.h:1080
DataLayout.h
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:272
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::Instruction::mayReadFromMemory
bool mayReadFromMemory() const
Return true if this instruction may read memory.
Definition: Instruction.cpp:543
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::BasicBlock::getTerminator
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:148
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:644
Sink.h
isSafeToMove
static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA, SmallPtrSetImpl< Instruction * > &Stores)
Definition: Sink.cpp:35
llvm::Instruction::isDebugOrPseudoInst
bool isDebugOrPseudoInst() const
Return true if the instruction is a DbgInfoIntrinsic or PseudoProbeInst.
Definition: Instruction.cpp:694
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:51
Dominators.h
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1269
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode
Definition: Instructions.h:2572
llvm::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
llvm::SmallPtrSetImpl< Instruction * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:61
ProcessBlock
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:179
raw_ostream.h
InitializePasses.h
Debug.h
llvm::AAResults::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
Definition: AliasAnalysis.cpp:217
llvm::initializeSinkingLegacyPassPass
void initializeSinkingLegacyPassPass(PassRegistry &)
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1233
llvm::Instruction::moveBefore
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:97
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38