xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/Sink.cpp (revision e32fecd0c2c3ee37c47ee100f169e7eb0282a873)
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"
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,
31                          SmallPtrSetImpl<Instruction *> &Stores) {
32 
33   if (Inst->mayWriteToMemory()) {
34     Stores.insert(Inst);
35     return false;
36   }
37 
38   if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
39     MemoryLocation Loc = MemoryLocation::get(L);
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,
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>(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 
174 static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI,
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;
190   SmallPtrSet<Instruction *, 8> Stores;
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 
214 static bool iterativelySinkInstructions(Function &F, DominatorTree &DT,
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 
231 PreservedAnalyses SinkingPass::run(Function &F, FunctionAnalysisManager &AM) {
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 
239   PreservedAnalyses PA;
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) {
249       initializeSinkingLegacyPassPass(*PassRegistry::getPassRegistry());
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();
262       FunctionPass::getAnalysisUsage(AU);
263       AU.addRequired<AAResultsWrapperPass>();
264       AU.addRequired<DominatorTreeWrapperPass>();
265       AU.addRequired<LoopInfoWrapperPass>();
266       AU.addPreserved<DominatorTreeWrapperPass>();
267       AU.addPreserved<LoopInfoWrapperPass>();
268     }
269   };
270 } // end anonymous namespace
271 
272 char SinkingLegacyPass::ID = 0;
273 INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false)
274 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
275 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
276 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
277 INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false)
278 
279 FunctionPass *llvm::createSinkingPass() { return new SinkingLegacyPass(); }
280