LLVM  16.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 
30 static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA,
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  !Inst->hasMetadata(LLVMContext::MD_invariant_load))
84  return false;
85 
86  // We don't want to sink across a critical edge if we don't dominate the
87  // successor. We could be introducing calculations to new code paths.
88  if (!DT.dominates(Inst->getParent(), SuccToSinkTo))
89  return false;
90 
91  // Don't sink instructions into a loop.
92  Loop *succ = LI.getLoopFor(SuccToSinkTo);
93  Loop *cur = LI.getLoopFor(Inst->getParent());
94  if (succ != nullptr && succ != cur)
95  return false;
96  }
97 
98  return true;
99 }
100 
101 /// SinkInstruction - Determine whether it is safe to sink the specified machine
102 /// instruction out of its current block into a successor.
103 static bool SinkInstruction(Instruction *Inst,
105  DominatorTree &DT, LoopInfo &LI, AAResults &AA) {
106 
107  // Don't sink static alloca instructions. CodeGen assumes allocas outside the
108  // entry block are dynamically sized stack objects.
109  if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst))
110  if (AI->isStaticAlloca())
111  return false;
112 
113  // Check if it's safe to move the instruction.
114  if (!isSafeToMove(Inst, AA, Stores))
115  return false;
116 
117  // FIXME: This should include support for sinking instructions within the
118  // block they are currently in to shorten the live ranges. We often get
119  // instructions sunk into the top of a large block, but it would be better to
120  // also sink them down before their first use in the block. This xform has to
121  // be careful not to *increase* register pressure though, e.g. sinking
122  // "x = y + z" down if it kills y and z would increase the live ranges of y
123  // and z and only shrink the live range of x.
124 
125  // SuccToSinkTo - This is the successor to sink this instruction to, once we
126  // decide.
127  BasicBlock *SuccToSinkTo = nullptr;
128 
129  // Find the nearest common dominator of all users as the candidate.
130  BasicBlock *BB = Inst->getParent();
131  for (Use &U : Inst->uses()) {
132  Instruction *UseInst = cast<Instruction>(U.getUser());
133  BasicBlock *UseBlock = UseInst->getParent();
134  // Don't worry about dead users.
135  if (!DT.isReachableFromEntry(UseBlock))
136  continue;
137  if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
138  // PHI nodes use the operand in the predecessor block, not the block with
139  // the PHI.
140  unsigned Num = PHINode::getIncomingValueNumForOperand(U.getOperandNo());
141  UseBlock = PN->getIncomingBlock(Num);
142  }
143  if (SuccToSinkTo)
144  SuccToSinkTo = DT.findNearestCommonDominator(SuccToSinkTo, UseBlock);
145  else
146  SuccToSinkTo = UseBlock;
147  // The current basic block needs to dominate the candidate.
148  if (!DT.dominates(BB, SuccToSinkTo))
149  return false;
150  }
151 
152  if (SuccToSinkTo) {
153  // The nearest common dominator may be in a parent loop of BB, which may not
154  // be beneficial. Find an ancestor.
155  while (SuccToSinkTo != BB &&
156  !IsAcceptableTarget(Inst, SuccToSinkTo, DT, LI))
157  SuccToSinkTo = DT.getNode(SuccToSinkTo)->getIDom()->getBlock();
158  if (SuccToSinkTo == BB)
159  SuccToSinkTo = nullptr;
160  }
161 
162  // If we couldn't find a block to sink to, ignore this instruction.
163  if (!SuccToSinkTo)
164  return false;
165 
166  LLVM_DEBUG(dbgs() << "Sink" << *Inst << " (";
167  Inst->getParent()->printAsOperand(dbgs(), false); dbgs() << " -> ";
168  SuccToSinkTo->printAsOperand(dbgs(), false); dbgs() << ")\n");
169 
170  // Move the instruction.
171  Inst->moveBefore(&*SuccToSinkTo->getFirstInsertionPt());
172  return true;
173 }
174 
176  AAResults &AA) {
177  // Don't bother sinking code out of unreachable blocks. In addition to being
178  // unprofitable, it can also lead to infinite looping, because in an
179  // unreachable loop there may be nowhere to stop.
180  if (!DT.isReachableFromEntry(&BB)) return false;
181 
182  bool MadeChange = false;
183 
184  // Walk the basic block bottom-up. Remember if we saw a store.
185  BasicBlock::iterator I = BB.end();
186  --I;
187  bool ProcessedBegin = false;
189  do {
190  Instruction *Inst = &*I; // The instruction to sink.
191 
192  // Predecrement I (if it's not begin) so that it isn't invalidated by
193  // sinking.
194  ProcessedBegin = I == BB.begin();
195  if (!ProcessedBegin)
196  --I;
197 
198  if (Inst->isDebugOrPseudoInst())
199  continue;
200 
201  if (SinkInstruction(Inst, Stores, DT, LI, AA)) {
202  ++NumSunk;
203  MadeChange = true;
204  }
205 
206  // If we just processed the first instruction in the block, we're done.
207  } while (!ProcessedBegin);
208 
209  return MadeChange;
210 }
211 
213  LoopInfo &LI, AAResults &AA) {
214  bool MadeChange, EverMadeChange = false;
215 
216  do {
217  MadeChange = false;
218  LLVM_DEBUG(dbgs() << "Sinking iteration " << NumSinkIter << "\n");
219  // Process all basic blocks.
220  for (BasicBlock &I : F)
221  MadeChange |= ProcessBlock(I, DT, LI, AA);
222  EverMadeChange |= MadeChange;
223  NumSinkIter++;
224  } while (MadeChange);
225 
226  return EverMadeChange;
227 }
228 
230  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
231  auto &LI = AM.getResult<LoopAnalysis>(F);
232  auto &AA = AM.getResult<AAManager>(F);
233 
234  if (!iterativelySinkInstructions(F, DT, LI, AA))
235  return PreservedAnalyses::all();
236 
238  PA.preserveSet<CFGAnalyses>();
239  return PA;
240 }
241 
242 namespace {
243  class SinkingLegacyPass : public FunctionPass {
244  public:
245  static char ID; // Pass identification
246  SinkingLegacyPass() : FunctionPass(ID) {
248  }
249 
250  bool runOnFunction(Function &F) override {
251  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
252  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
253  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
254 
255  return iterativelySinkInstructions(F, DT, LI, AA);
256  }
257 
258  void getAnalysisUsage(AnalysisUsage &AU) const override {
259  AU.setPreservesCFG();
266  }
267  };
268 } // end anonymous namespace
269 
270 char SinkingLegacyPass::ID = 0;
271 INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false)
275 INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false)
276 
277 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:167
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:876
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:18
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::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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:774
Scalar.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
Statistic.h
llvm::isModSet
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
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:1293
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:103
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::Instruction::mayWriteToMemory
bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
Definition: Instruction.cpp:626
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::Instruction::isExceptionalTerminator
bool isExceptionalTerminator() const
Definition: Instruction.h:174
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::Instruction::mayReadFromMemory
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
Definition: Instruction.cpp:606
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::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::AAResults
Definition: AliasAnalysis.h:294
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:212
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:277
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:2808
llvm::Instruction::willReturn
bool willReturn() const LLVM_READONLY
Return true if the instruction will return (unwinding is considered as a form of returning control fl...
Definition: Instruction.cpp:734
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:992
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::AAResults::getModRefInfo
ModRefInfo getModRefInfo(const Instruction *I, const Optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Definition: AliasAnalysis.h:488
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Instruction::hasMetadata
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
Definition: Instruction.h:253
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:229
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:4758
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:1108
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
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:293
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::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::Instruction::isDebugOrPseudoInst
bool isDebugOrPseudoInst() const LLVM_READONLY
Return true if the instruction is a DbgInfoIntrinsic or PseudoProbeInst.
Definition: Instruction.cpp:765
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
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:664
Sink.h
isSafeToMove
static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA, SmallPtrSetImpl< Instruction * > &Stores)
Definition: Sink.cpp:30
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:924
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode
Definition: Instructions.h:2698
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::Instruction::mayThrow
bool mayThrow() const LLVM_READONLY
Return true if this instruction may throw an exception.
Definition: Instruction.cpp:715
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:98
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:175
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:1268
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:100
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