LLVM 19.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"
18#include "llvm/IR/Dominators.h"
20#include "llvm/Support/Debug.h"
23using namespace llvm;
24
25#define DEBUG_TYPE "sink"
26
27STATISTIC(NumSunk, "Number of instructions sunk");
28STATISTIC(NumSinkIter, "Number of sinking iterations");
29
30static 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.
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");
69
70 // It's never legal to sink an instruction into an EH-pad block.
71 if (SuccToSinkTo->isEHPad())
72 return false;
73
74 // If the block has multiple predecessors, this would introduce computation
75 // on different code paths. We could split the critical edge, but for now we
76 // just punt.
77 // FIXME: Split critical edges if not backedges.
78 if (SuccToSinkTo->getUniquePredecessor() != Inst->getParent()) {
79 // We cannot sink a load across a critical edge - there may be stores in
80 // other code paths.
81 if (Inst->mayReadFromMemory() &&
82 !Inst->hasMetadata(LLVMContext::MD_invariant_load))
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.
102static 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 if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
134 // PHI nodes use the operand in the predecessor block, not the block with
135 // the PHI.
136 unsigned Num = PHINode::getIncomingValueNumForOperand(U.getOperandNo());
137 UseBlock = PN->getIncomingBlock(Num);
138 }
139 // Don't worry about dead users.
140 if (!DT.isReachableFromEntry(UseBlock))
141 continue;
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.
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
239 return PA;
240}
241
242namespace {
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();
260 FunctionPass::getAnalysisUsage(AU);
266 }
267 };
268} // end anonymous namespace
269
270char SinkingLegacyPass::ID = 0;
271INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false)
275INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false)
276
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:1626
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Machine code sinking
#define INITIALIZE_PASS_DEPENDENCY(depName)
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:102
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
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:59
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
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:269
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:451
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:438
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:452
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:503
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:173
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:665
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
DomTreeNodeBase * getIDom() const
NodeT * getBlock() const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:275
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:313
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
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:311
bool mayThrow(bool IncludePhaseOneUnwind=false) const LLVM_READONLY
Return true if this instruction may throw an exception.
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:339
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:800
const BasicBlock * getParent() const
Definition: Instruction.h:150
bool isTerminator() const
Definition: Instruction.h:253
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...
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:178
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:593
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
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: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
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:321
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
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:4990
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