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
14#include "llvm/Transforms/Scalar/Sink.h"
15#include "llvm/ADT/Statistic.h"
16#include "llvm/Analysis/AliasAnalysis.h"
17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/IR/Dominators.h"
19#include "llvm/InitializePasses.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/raw_ostream.h"
22#include "llvm/Transforms/Scalar.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,
31 SmallPtrSetImpl<Instruction *> &Stores) {
32
33 if (Inst->mayWriteToMemory()) {
34 Stores.insert(Ptr: Inst);
35 return false;
36 }
37
38 if (LoadInst *L = dyn_cast<LoadInst>(Val: Inst)) {
39 MemoryLocation Loc = MemoryLocation::get(LI: L);
40 for (Instruction *S : Stores)
41 if (isModSet(MRI: AA.getModRefInfo(I: S, OptLoc: Loc)))
42 return false;
43 }
44
45 if (Inst->isTerminator() || isa<PHINode>(Val: Inst) || Inst->isEHPad() ||
46 Inst->mayThrow() || !Inst->willReturn())
47 return false;
48
49 if (auto *Call = dyn_cast<CallBase>(Val: 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(MRI: AA.getModRefInfo(I: 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(KindID: 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(A: Inst->getParent(), B: SuccToSinkTo))
88 return false;
89
90 // Don't sink instructions into a loop.
91 Loop *succ = LI.getLoopFor(BB: SuccToSinkTo);
92 Loop *cur = LI.getLoopFor(BB: 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,
103 SmallPtrSetImpl<Instruction *> &Stores,
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>(Val: 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>(Val: U.getUser());
132 BasicBlock *UseBlock = UseInst->getParent();
133 if (PHINode *PN = dyn_cast<PHINode>(Val: UseInst)) {
134 // PHI nodes use the operand in the predecessor block, not the block with
135 // the PHI.
136 unsigned Num = PHINode::getIncomingValueNumForOperand(i: U.getOperandNo());
137 UseBlock = PN->getIncomingBlock(i: Num);
138 }
139 // Don't worry about dead users.
140 if (!DT.isReachableFromEntry(A: UseBlock))
141 continue;
142
143 if (SuccToSinkTo)
144 SuccToSinkTo = DT.findNearestCommonDominator(A: SuccToSinkTo, B: UseBlock);
145 else
146 SuccToSinkTo = UseBlock;
147 // The current basic block needs to dominate the candidate.
148 if (!DT.dominates(A: BB, B: 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(BB: 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(MovePos: &*SuccToSinkTo->getFirstInsertionPt());
172 return true;
173}
174
175static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI,
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(A: &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;
188 SmallPtrSet<Instruction *, 8> Stores;
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
212static bool iterativelySinkInstructions(Function &F, DominatorTree &DT,
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(BB&: I, DT, LI, AA);
222 EverMadeChange |= MadeChange;
223 NumSinkIter++;
224 } while (MadeChange);
225
226 return EverMadeChange;
227}
228
229PreservedAnalyses SinkingPass::run(Function &F, FunctionAnalysisManager &AM) {
230 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
231 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
232 auto &AA = AM.getResult<AAManager>(IR&: F);
233
234 if (!iterativelySinkInstructions(F, DT, LI, AA))
235 return PreservedAnalyses::all();
236
237 PreservedAnalyses PA;
238 PA.preserveSet<CFGAnalyses>();
239 return PA;
240}
241
242namespace {
243 class SinkingLegacyPass : public FunctionPass {
244 public:
245 static char ID; // Pass identification
246 SinkingLegacyPass() : FunctionPass(ID) {
247 initializeSinkingLegacyPassPass(*PassRegistry::getPassRegistry());
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);
261 AU.addRequired<AAResultsWrapperPass>();
262 AU.addRequired<DominatorTreeWrapperPass>();
263 AU.addRequired<LoopInfoWrapperPass>();
264 AU.addPreserved<DominatorTreeWrapperPass>();
265 AU.addPreserved<LoopInfoWrapperPass>();
266 }
267 };
268} // end anonymous namespace
269
270char SinkingLegacyPass::ID = 0;
271INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false)
272INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
273INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
274INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
275INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false)
276
277FunctionPass *llvm::createSinkingPass() { return new SinkingLegacyPass(); }
278