LLVM 17.0.0git
Go to the documentation of this file.
1//===-- Sink.cpp - Code Sinking -------------------------------------------===//
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
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.
15#include "llvm/ADT/Statistic.h"
18#include "llvm/IR/Dominators.h"
20#include "llvm/Support/Debug.h"
23using namespace llvm;
25#define DEBUG_TYPE "sink"
27STATISTIC(NumSunk, "Number of instructions sunk");
28STATISTIC(NumSinkIter, "Number of sinking iterations");
30static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA,
33 if (Inst->mayWriteToMemory()) {
34 Stores.insert(Inst);
35 return false;
36 }
38 if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
40 for (Instruction *S : Stores)
41 if (isModSet(AA.getModRefInfo(S, Loc)))
42 return false;
43 }
45 if (Inst->isTerminator() || isa<PHINode>(Inst) || Inst->isEHPad() ||
46 Inst->mayThrow() || !Inst->willReturn())
47 return false;
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;
55 for (Instruction *S : Stores)
56 if (isModSet(AA.getModRefInfo(S, Call)))
57 return false;
58 }
60 return true;
63/// IsAcceptableTarget - Return true if it is possible to sink the instruction
64/// in the specified basic block.
65static 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");
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;
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;
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;
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 }
98 return true;
101/// SinkInstruction - Determine whether it is safe to sink the specified machine
102/// instruction out of its current block into a successor.
103static bool SinkInstruction(Instruction *Inst,
105 DominatorTree &DT, LoopInfo &LI, AAResults &AA) {
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;
113 // Check if it's safe to move the instruction.
114 if (!isSafeToMove(Inst, AA, Stores))
115 return false;
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.
125 // SuccToSinkTo - This is the successor to sink this instruction to, once we
126 // decide.
127 BasicBlock *SuccToSinkTo = nullptr;
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 }
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 }
162 // If we couldn't find a block to sink to, ignore this instruction.
163 if (!SuccToSinkTo)
164 return false;
166 LLVM_DEBUG(dbgs() << "Sink" << *Inst << " (";
167 Inst->getParent()->printAsOperand(dbgs(), false); dbgs() << " -> ";
168 SuccToSinkTo->printAsOperand(dbgs(), false); dbgs() << ")\n");
170 // Move the instruction.
171 Inst->moveBefore(&*SuccToSinkTo->getFirstInsertionPt());
172 return true;
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;
182 bool MadeChange = false;
184 // Walk the basic block bottom-up. Remember if we saw a store.
186 --I;
187 bool ProcessedBegin = false;
189 do {
190 Instruction *Inst = &*I; // The instruction to sink.
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;
198 if (Inst->isDebugOrPseudoInst())
199 continue;
201 if (SinkInstruction(Inst, Stores, DT, LI, AA)) {
202 ++NumSunk;
203 MadeChange = true;
204 }
206 // If we just processed the first instruction in the block, we're done.
207 } while (!ProcessedBegin);
209 return MadeChange;
213 LoopInfo &LI, AAResults &AA) {
214 bool MadeChange, EverMadeChange = false;
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);
226 return EverMadeChange;
230 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
231 auto &LI = AM.getResult<LoopAnalysis>(F);
232 auto &AA = AM.getResult<AAManager>(F);
234 if (!iterativelySinkInstructions(F, DT, LI, AA))
235 return PreservedAnalyses::all();
239 return PA;
242namespace {
243 class SinkingLegacyPass : public FunctionPass {
244 public:
245 static char ID; // Pass identification
246 SinkingLegacyPass() : FunctionPass(ID) {
248 }
250 bool runOnFunction(Function &F) override {
251 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
252 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
253 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
255 return iterativelySinkInstructions(F, DT, LI, AA);
256 }
258 void getAnalysisUsage(AnalysisUsage &AU) const override {
259 AU.setPreservesCFG();
260 FunctionPass::getAnalysisUsage(AU);
266 }
267 };
268} // end anonymous namespace
270char SinkingLegacyPass::ID = 0;
271INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false)
275INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false)
277FunctionPass *llvm::createSinkingPass() { return new SinkingLegacyPass(); }
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static bool runOnFunction(Function &F, bool PostInlining)
static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU, OptimizationRemarkEmitter *ORE)
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
Definition: LICM.cpp:1622
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Machine code sinking
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool iterativelySinkInstructions(Function &F, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:212
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
static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA, SmallPtrSetImpl< Instruction * > &Stores)
Definition: Sink.cpp:30
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:175
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
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
Definition: Statistic.h:167
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
an instruction to allocate memory on the stack
Definition: Instructions.h:58
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:316
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:314
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:245
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:292
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
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:127
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
DomTreeNodeBase * getIDom() const
NodeT * getBlock() const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
Definition: Dominators.cpp:344
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
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
bool isDebugOrPseudoInst() const LLVM_READONLY
Return true if the instruction is a DbgInfoIntrinsic or PseudoProbeInst.
bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
Definition: Instruction.h:257
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:685
const BasicBlock * getParent() const
Definition: Instruction.h:90
bool isTerminator() const
Definition: Instruction.h:171
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
bool willReturn() const LLVM_READONLY
Return true if the instruction will return (unwinding is considered as a form of returning control fl...
bool mayThrow() const LLVM_READONLY
Return true if this instruction may throw an exception.
bool isExceptionalTerminator() const
Definition: Instruction.h:178
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
An instruction for reading from memory.
Definition: Instructions.h:177
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static unsigned getIncomingValueNumForOperand(unsigned i)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Sink.cpp:229
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
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
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
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:4781
iterator_range< use_iterator > uses()
Definition: Value.h:376
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void initializeSinkingLegacyPassPass(PassRegistry &)
FunctionPass * createSinkingPass()
Definition: Sink.cpp:277
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163