LLVM  15.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"
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/InitializePasses.h"
20 #include "llvm/Support/Debug.h"
22 #include "llvm/Transforms/Scalar.h"
23 using namespace llvm;
24 
25 #define DEBUG_TYPE "sink"
26 
27 STATISTIC(NumSunk, "Number of instructions sunk");
28 STATISTIC(NumSinkIter, "Number of sinking iterations");
29 
32 
33  if (Inst->mayWriteToMemory()) {
34  Stores.insert(Inst);
35  return false;
36  }
37 
38  if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
40  for (Instruction *S : Stores)
41  if (isModSet(AA.getModRefInfo(S, Loc)))
42  return false;
43  }
44 
45  if (Inst->isTerminator() || isa<PHINode>(Inst) || Inst->isEHPad() ||
46  Inst->mayThrow() || !Inst->willReturn())
47  return false;
48 
49  if (auto *Call = dyn_cast<CallBase>(Inst)) {
50  // Convergent operations cannot be made control-dependent on additional
51  // values.
52  if (Call->isConvergent())
53  return false;
54 
55  for (Instruction *S : Stores)
56  if (isModSet(AA.getModRefInfo(S, Call)))
57  return false;
58  }
59 
60  return true;
61 }
62 
63 /// IsAcceptableTarget - Return true if it is possible to sink the instruction
64 /// in the specified basic block.
65 static bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo,
66  DominatorTree &DT, LoopInfo &LI) {
67  assert(Inst && "Instruction to be sunk is null");
68  assert(SuccToSinkTo && "Candidate sink target is null");
69 
70  // It's never legal to sink an instruction into a block which terminates in an
71  // EH-pad.
72  if (SuccToSinkTo->getTerminator()->isExceptionalTerminator())
73  return false;
74 
75  // If the block has multiple predecessors, this would introduce computation
76  // on different code paths. We could split the critical edge, but for now we
77  // just punt.
78  // FIXME: Split critical edges if not backedges.
79  if (SuccToSinkTo->getUniquePredecessor() != Inst->getParent()) {
80  // We cannot sink a load across a critical edge - there may be stores in
81  // other code paths.
82  if (Inst->mayReadFromMemory())
83  return false;
84 
85  // We don't want to sink across a critical edge if we don't dominate the
86  // successor. We could be introducing calculations to new code paths.
87  if (!DT.dominates(Inst->getParent(), SuccToSinkTo))
88  return false;
89 
90  // Don't sink instructions into a loop.
91  Loop *succ = LI.getLoopFor(SuccToSinkTo);
92  Loop *cur = LI.getLoopFor(Inst->getParent());
93  if (succ != nullptr && succ != cur)
94  return false;
95  }
96 
97  return true;
98 }
99 
100 /// SinkInstruction - Determine whether it is safe to sink the specified machine
101 /// instruction out of its current block into a successor.
102 static bool SinkInstruction(Instruction *Inst,
104  DominatorTree &DT, LoopInfo &LI, AAResults &AA) {
105 
106  // Don't sink static alloca instructions. CodeGen assumes allocas outside the
107  // entry block are dynamically sized stack objects.
108  if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst))
109  if (AI->isStaticAlloca())
110  return false;
111 
112  // Check if it's safe to move the instruction.
113  if (!isSafeToMove(Inst, AA, Stores))
114  return false;
115 
116  // FIXME: This should include support for sinking instructions within the
117  // block they are currently in to shorten the live ranges. We often get
118  // instructions sunk into the top of a large block, but it would be better to
119  // also sink them down before their first use in the block. This xform has to
120  // be careful not to *increase* register pressure though, e.g. sinking
121  // "x = y + z" down if it kills y and z would increase the live ranges of y
122  // and z and only shrink the live range of x.
123 
124  // SuccToSinkTo - This is the successor to sink this instruction to, once we
125  // decide.
126  BasicBlock *SuccToSinkTo = nullptr;
127 
128  // Find the nearest common dominator of all users as the candidate.
129  BasicBlock *BB = Inst->getParent();
130  for (Use &U : Inst->uses()) {
131  Instruction *UseInst = cast<Instruction>(U.getUser());
132  BasicBlock *UseBlock = UseInst->getParent();
133  // Don't worry about dead users.
134  if (!DT.isReachableFromEntry(UseBlock))
135  continue;
136  if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
137  // PHI nodes use the operand in the predecessor block, not the block with
138  // the PHI.
139  unsigned Num = PHINode::getIncomingValueNumForOperand(U.getOperandNo());
140  UseBlock = PN->getIncomingBlock(Num);
141  }
142  if (SuccToSinkTo)
143  SuccToSinkTo = DT.findNearestCommonDominator(SuccToSinkTo, UseBlock);
144  else
145  SuccToSinkTo = UseBlock;
146  // The current basic block needs to dominate the candidate.
147  if (!DT.dominates(BB, SuccToSinkTo))
148  return false;
149  }
150 
151  if (SuccToSinkTo) {
152  // The nearest common dominator may be in a parent loop of BB, which may not
153  // be beneficial. Find an ancestor.
154  while (SuccToSinkTo != BB &&
155  !IsAcceptableTarget(Inst, SuccToSinkTo, DT, LI))
156  SuccToSinkTo = DT.getNode(SuccToSinkTo)->getIDom()->getBlock();
157  if (SuccToSinkTo == BB)
158  SuccToSinkTo = nullptr;
159  }
160 
161  // If we couldn't find a block to sink to, ignore this instruction.
162  if (!SuccToSinkTo)
163  return false;
164 
165  LLVM_DEBUG(dbgs() << "Sink" << *Inst << " (";
166  Inst->getParent()->printAsOperand(dbgs(), false); dbgs() << " -> ";
167  SuccToSinkTo->printAsOperand(dbgs(), false); dbgs() << ")\n");
168 
169  // Move the instruction.
170  Inst->moveBefore(&*SuccToSinkTo->getFirstInsertionPt());
171  return true;
172 }
173 
175  AAResults &AA) {
176  // Can't sink anything out of a block that has less than two successors.
177  if (BB.getTerminator()->getNumSuccessors() <= 1) return false;
178 
179  // Don't bother sinking code out of unreachable blocks. In addition to being
180  // unprofitable, it can also lead to infinite looping, because in an
181  // unreachable loop there may be nowhere to stop.
182  if (!DT.isReachableFromEntry(&BB)) return false;
183 
184  bool MadeChange = false;
185 
186  // Walk the basic block bottom-up. Remember if we saw a store.
187  BasicBlock::iterator I = BB.end();
188  --I;
189  bool ProcessedBegin = false;
191  do {
192  Instruction *Inst = &*I; // The instruction to sink.
193 
194  // Predecrement I (if it's not begin) so that it isn't invalidated by
195  // sinking.
196  ProcessedBegin = I == BB.begin();
197  if (!ProcessedBegin)
198  --I;
199 
200  if (Inst->isDebugOrPseudoInst())
201  continue;
202 
203  if (SinkInstruction(Inst, Stores, DT, LI, AA)) {
204  ++NumSunk;
205  MadeChange = true;
206  }
207 
208  // If we just processed the first instruction in the block, we're done.
209  } while (!ProcessedBegin);
210 
211  return MadeChange;
212 }
213 
215  LoopInfo &LI, AAResults &AA) {
216  bool MadeChange, EverMadeChange = false;
217 
218  do {
219  MadeChange = false;
220  LLVM_DEBUG(dbgs() << "Sinking iteration " << NumSinkIter << "\n");
221  // Process all basic blocks.
222  for (BasicBlock &I : F)
223  MadeChange |= ProcessBlock(I, DT, LI, AA);
224  EverMadeChange |= MadeChange;
225  NumSinkIter++;
226  } while (MadeChange);
227 
228  return EverMadeChange;
229 }
230 
232  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
233  auto &LI = AM.getResult<LoopAnalysis>(F);
234  auto &AA = AM.getResult<AAManager>(F);
235 
236  if (!iterativelySinkInstructions(F, DT, LI, AA))
237  return PreservedAnalyses::all();
238 
240  PA.preserveSet<CFGAnalyses>();
241  return PA;
242 }
243 
244 namespace {
245  class SinkingLegacyPass : public FunctionPass {
246  public:
247  static char ID; // Pass identification
248  SinkingLegacyPass() : FunctionPass(ID) {
250  }
251 
252  bool runOnFunction(Function &F) override {
253  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
254  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
255  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
256 
257  return iterativelySinkInstructions(F, DT, LI, AA);
258  }
259 
260  void getAnalysisUsage(AnalysisUsage &AU) const override {
261  AU.setPreservesCFG();
268  }
269  };
270 } // end anonymous namespace
271 
272 char SinkingLegacyPass::ID = 0;
273 INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false)
277 INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false)
278 
279 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:152
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:160
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1303
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:35
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:87
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:780
Scalar.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
Statistic.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1287
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:102
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:450
llvm::Instruction::mayThrow
bool mayThrow() const
Return true if this instruction may throw an exception.
Definition: Instruction.cpp:685
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::Instruction::isExceptionalTerminator
bool isExceptionalTerminator() const
Definition: Instruction.h:167
sinking
Machine code sinking
Definition: MachineSink.cpp:269
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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:122
llvm::Instruction::willReturn
bool willReturn() const
Return true if the instruction will return (unwinding is considered as a form of returning control fl...
Definition: Instruction.cpp:704
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:511
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:65
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:376
iterativelySinkInstructions
static bool iterativelySinkInstructions(Function &F, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:214
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:246
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::createSinkingPass
FunctionPass * createSinkingPass()
Definition: Sink.cpp:279
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:596
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::PHINode::getIncomingValueNumForOperand
static unsigned getIncomingValueNumForOperand(unsigned i)
Definition: Instructions.h:2761
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:986
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:335
llvm::SinkingPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Sink.cpp:231
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:4673
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:926
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:269
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:576
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
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:158
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:662
Sink.h
isSafeToMove
static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA, SmallPtrSetImpl< Instruction * > &Stores)
Definition: Sink.cpp:30
llvm::Instruction::isDebugOrPseudoInst
bool isDebugOrPseudoInst() const
Return true if the instruction is a DbgInfoIntrinsic or PseudoProbeInst.
Definition: Instruction.cpp:735
AA
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
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:1351
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode
Definition: Instructions.h:2651
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.h:119
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:97
llvm::SmallPtrSetImpl< Instruction * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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:58
ProcessBlock
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:174
raw_ostream.h
InitializePasses.h
Debug.h
llvm::initializeSinkingLegacyPassPass
void initializeSinkingLegacyPassPass(PassRegistry &)
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1262
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:96
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
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:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38