/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/Sink.cpp
Line | Count | Source (jump to first uncovered line) |
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/Analysis/ValueTracking.h" |
19 | | #include "llvm/IR/CFG.h" |
20 | | #include "llvm/IR/DataLayout.h" |
21 | | #include "llvm/IR/Dominators.h" |
22 | | #include "llvm/IR/IntrinsicInst.h" |
23 | | #include "llvm/IR/Module.h" |
24 | | #include "llvm/Support/Debug.h" |
25 | | #include "llvm/Support/raw_ostream.h" |
26 | | #include "llvm/Transforms/Scalar.h" |
27 | | using namespace llvm; |
28 | | |
29 | | #define DEBUG_TYPE "sink" |
30 | | |
31 | | STATISTIC(NumSunk, "Number of instructions sunk"); |
32 | | STATISTIC(NumSinkIter, "Number of sinking iterations"); |
33 | | |
34 | | /// AllUsesDominatedByBlock - Return true if all uses of the specified value |
35 | | /// occur in blocks dominated by the specified block. |
36 | | static bool AllUsesDominatedByBlock(Instruction *Inst, BasicBlock *BB, |
37 | 59.9k | DominatorTree &DT) { |
38 | 59.9k | // Ignoring debug uses is necessary so debug info doesn't affect the code. |
39 | 59.9k | // This may leave a referencing dbg_value in the original block, before |
40 | 59.9k | // the definition of the vreg. Dwarf generator handles this although the |
41 | 59.9k | // user might not get the right info at runtime. |
42 | 63.6k | for (Use &U : Inst->uses()) { |
43 | 63.6k | // Determine the block of the use. |
44 | 63.6k | Instruction *UseInst = cast<Instruction>(U.getUser()); |
45 | 63.6k | BasicBlock *UseBlock = UseInst->getParent(); |
46 | 63.6k | if (PHINode *PN = dyn_cast<PHINode>(UseInst)) { |
47 | 979 | // PHI nodes use the operand in the predecessor block, not the block with |
48 | 979 | // the PHI. |
49 | 979 | unsigned Num = PHINode::getIncomingValueNumForOperand(U.getOperandNo()); |
50 | 979 | UseBlock = PN->getIncomingBlock(Num); |
51 | 979 | } |
52 | 63.6k | // Check that it dominates. |
53 | 63.6k | if (!DT.dominates(BB, UseBlock)) |
54 | 56.3k | return false; |
55 | 63.6k | } |
56 | 59.9k | return true3.57k ; |
57 | 59.9k | } |
58 | | |
59 | | static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA, |
60 | 25.6k | SmallPtrSetImpl<Instruction *> &Stores) { |
61 | 25.6k | |
62 | 25.6k | if (Inst->mayWriteToMemory()) { |
63 | 547 | Stores.insert(Inst); |
64 | 547 | return false; |
65 | 547 | } |
66 | 25.0k | |
67 | 25.0k | if (LoadInst *L = dyn_cast<LoadInst>(Inst)) { |
68 | 2.08k | MemoryLocation Loc = MemoryLocation::get(L); |
69 | 2.08k | for (Instruction *S : Stores) |
70 | 450 | if (isModSet(AA.getModRefInfo(S, Loc))) |
71 | 62 | return false; |
72 | 2.08k | } |
73 | 25.0k | |
74 | 25.0k | if (24.9k Inst->isTerminator()24.9k || isa<PHINode>(Inst)22.7k || Inst->isEHPad()19.7k || |
75 | 24.9k | Inst->mayThrow()19.7k ) |
76 | 5.29k | return false; |
77 | 19.7k | |
78 | 19.7k | if (auto *Call = dyn_cast<CallBase>(Inst)) { |
79 | 3.57k | // Convergent operations cannot be made control-dependent on additional |
80 | 3.57k | // values. |
81 | 3.57k | if (Call->hasFnAttr(Attribute::Convergent)) |
82 | 797 | return false; |
83 | 2.77k | |
84 | 2.77k | for (Instruction *S : Stores) |
85 | 466 | if (isModSet(AA.getModRefInfo(S, Call))) |
86 | 9 | return false; |
87 | 2.77k | } |
88 | 19.7k | |
89 | 19.7k | return true18.8k ; |
90 | 19.7k | } |
91 | | |
92 | | /// IsAcceptableTarget - Return true if it is possible to sink the instruction |
93 | | /// in the specified basic block. |
94 | | static bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo, |
95 | 65.1k | DominatorTree &DT, LoopInfo &LI) { |
96 | 65.1k | assert(Inst && "Instruction to be sunk is null"); |
97 | 65.1k | assert(SuccToSinkTo && "Candidate sink target is null"); |
98 | 65.1k | |
99 | 65.1k | // It is not possible to sink an instruction into its own block. This can |
100 | 65.1k | // happen with loops. |
101 | 65.1k | if (Inst->getParent() == SuccToSinkTo) |
102 | 1.37k | return false; |
103 | 63.7k | |
104 | 63.7k | // It's never legal to sink an instruction into a block which terminates in an |
105 | 63.7k | // EH-pad. |
106 | 63.7k | if (SuccToSinkTo->getTerminator()->isExceptionalTerminator()) |
107 | 0 | return false; |
108 | 63.7k | |
109 | 63.7k | // If the block has multiple predecessors, this would introduce computation |
110 | 63.7k | // on different code paths. We could split the critical edge, but for now we |
111 | 63.7k | // just punt. |
112 | 63.7k | // FIXME: Split critical edges if not backedges. |
113 | 63.7k | if (SuccToSinkTo->getUniquePredecessor() != Inst->getParent()) { |
114 | 27.7k | // We cannot sink a load across a critical edge - there may be stores in |
115 | 27.7k | // other code paths. |
116 | 27.7k | if (Inst->mayReadFromMemory()) |
117 | 3.17k | return false; |
118 | 24.5k | |
119 | 24.5k | // We don't want to sink across a critical edge if we don't dominate the |
120 | 24.5k | // successor. We could be introducing calculations to new code paths. |
121 | 24.5k | if (!DT.dominates(Inst->getParent(), SuccToSinkTo)) |
122 | 543 | return false; |
123 | 24.0k | |
124 | 24.0k | // Don't sink instructions into a loop. |
125 | 24.0k | Loop *succ = LI.getLoopFor(SuccToSinkTo); |
126 | 24.0k | Loop *cur = LI.getLoopFor(Inst->getParent()); |
127 | 24.0k | if (succ != nullptr && succ != cur520 ) |
128 | 64 | return false; |
129 | 59.9k | } |
130 | 59.9k | |
131 | 59.9k | // Finally, check that all the uses of the instruction are actually |
132 | 59.9k | // dominated by the candidate |
133 | 59.9k | return AllUsesDominatedByBlock(Inst, SuccToSinkTo, DT); |
134 | 59.9k | } |
135 | | |
136 | | /// SinkInstruction - Determine whether it is safe to sink the specified machine |
137 | | /// instruction out of its current block into a successor. |
138 | | static bool SinkInstruction(Instruction *Inst, |
139 | | SmallPtrSetImpl<Instruction *> &Stores, |
140 | 25.6k | DominatorTree &DT, LoopInfo &LI, AAResults &AA) { |
141 | 25.6k | |
142 | 25.6k | // Don't sink static alloca instructions. CodeGen assumes allocas outside the |
143 | 25.6k | // entry block are dynamically sized stack objects. |
144 | 25.6k | if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst)) |
145 | 58 | if (AI->isStaticAlloca()) |
146 | 54 | return false; |
147 | 25.6k | |
148 | 25.6k | // Check if it's safe to move the instruction. |
149 | 25.6k | if (!isSafeToMove(Inst, AA, Stores)) |
150 | 6.71k | return false; |
151 | 18.8k | |
152 | 18.8k | // FIXME: This should include support for sinking instructions within the |
153 | 18.8k | // block they are currently in to shorten the live ranges. We often get |
154 | 18.8k | // instructions sunk into the top of a large block, but it would be better to |
155 | 18.8k | // also sink them down before their first use in the block. This xform has to |
156 | 18.8k | // be careful not to *increase* register pressure though, e.g. sinking |
157 | 18.8k | // "x = y + z" down if it kills y and z would increase the live ranges of y |
158 | 18.8k | // and z and only shrink the live range of x. |
159 | 18.8k | |
160 | 18.8k | // SuccToSinkTo - This is the successor to sink this instruction to, once we |
161 | 18.8k | // decide. |
162 | 18.8k | BasicBlock *SuccToSinkTo = nullptr; |
163 | 18.8k | |
164 | 18.8k | // Instructions can only be sunk if all their uses are in blocks |
165 | 18.8k | // dominated by one of the successors. |
166 | 18.8k | // Look at all the dominated blocks and see if we can sink it in one. |
167 | 18.8k | DomTreeNode *DTN = DT.getNode(Inst->getParent()); |
168 | 18.8k | for (DomTreeNode::iterator I = DTN->begin(), E = DTN->end(); |
169 | 53.3k | I != E && SuccToSinkTo == nullptr37.1k ; ++I34.4k ) { |
170 | 34.4k | BasicBlock *Candidate = (*I)->getBlock(); |
171 | 34.4k | // A node always immediate-dominates its children on the dominator |
172 | 34.4k | // tree. |
173 | 34.4k | if (IsAcceptableTarget(Inst, Candidate, DT, LI)) |
174 | 3.57k | SuccToSinkTo = Candidate; |
175 | 34.4k | } |
176 | 18.8k | |
177 | 18.8k | // If no suitable postdominator was found, look at all the successors and |
178 | 18.8k | // decide which one we should sink to, if any. |
179 | 18.8k | for (succ_iterator I = succ_begin(Inst->getParent()), |
180 | 49.5k | E = succ_end(Inst->getParent()); I != E && !SuccToSinkTo34.2k ; ++I30.6k ) { |
181 | 30.6k | if (IsAcceptableTarget(Inst, *I, DT, LI)) |
182 | 0 | SuccToSinkTo = *I; |
183 | 30.6k | } |
184 | 18.8k | |
185 | 18.8k | // If we couldn't find a block to sink to, ignore this instruction. |
186 | 18.8k | if (!SuccToSinkTo) |
187 | 15.3k | return false; |
188 | 3.57k | |
189 | 3.57k | LLVM_DEBUG(dbgs() << "Sink" << *Inst << " ("; |
190 | 3.57k | Inst->getParent()->printAsOperand(dbgs(), false); dbgs() << " -> "; |
191 | 3.57k | SuccToSinkTo->printAsOperand(dbgs(), false); dbgs() << ")\n"); |
192 | 3.57k | |
193 | 3.57k | // Move the instruction. |
194 | 3.57k | Inst->moveBefore(&*SuccToSinkTo->getFirstInsertionPt()); |
195 | 3.57k | return true; |
196 | 3.57k | } |
197 | | |
198 | | static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, |
199 | 30.5k | AAResults &AA) { |
200 | 30.5k | // Can't sink anything out of a block that has less than two successors. |
201 | 30.5k | if (BB.getTerminator()->getNumSuccessors() <= 1) return false28.2k ; |
202 | 2.25k | |
203 | 2.25k | // Don't bother sinking code out of unreachable blocks. In addition to being |
204 | 2.25k | // unprofitable, it can also lead to infinite looping, because in an |
205 | 2.25k | // unreachable loop there may be nowhere to stop. |
206 | 2.25k | if (!DT.isReachableFromEntry(&BB)) return false0 ; |
207 | 2.25k | |
208 | 2.25k | bool MadeChange = false; |
209 | 2.25k | |
210 | 2.25k | // Walk the basic block bottom-up. Remember if we saw a store. |
211 | 2.25k | BasicBlock::iterator I = BB.end(); |
212 | 2.25k | --I; |
213 | 2.25k | bool ProcessedBegin = false; |
214 | 2.25k | SmallPtrSet<Instruction *, 8> Stores; |
215 | 25.6k | do { |
216 | 25.6k | Instruction *Inst = &*I; // The instruction to sink. |
217 | 25.6k | |
218 | 25.6k | // Predecrement I (if it's not begin) so that it isn't invalidated by |
219 | 25.6k | // sinking. |
220 | 25.6k | ProcessedBegin = I == BB.begin(); |
221 | 25.6k | if (!ProcessedBegin) |
222 | 23.4k | --I; |
223 | 25.6k | |
224 | 25.6k | if (isa<DbgInfoIntrinsic>(Inst)) |
225 | 9 | continue; |
226 | 25.6k | |
227 | 25.6k | if (SinkInstruction(Inst, Stores, DT, LI, AA)) { |
228 | 3.57k | ++NumSunk; |
229 | 3.57k | MadeChange = true; |
230 | 3.57k | } |
231 | 25.6k | |
232 | 25.6k | // If we just processed the first instruction in the block, we're done. |
233 | 25.6k | } while (!ProcessedBegin); |
234 | 2.25k | |
235 | 2.25k | return MadeChange; |
236 | 2.25k | } |
237 | | |
238 | | static bool iterativelySinkInstructions(Function &F, DominatorTree &DT, |
239 | 25.2k | LoopInfo &LI, AAResults &AA) { |
240 | 25.2k | bool MadeChange, EverMadeChange = false; |
241 | 25.2k | |
242 | 25.7k | do { |
243 | 25.7k | MadeChange = false; |
244 | 25.7k | LLVM_DEBUG(dbgs() << "Sinking iteration " << NumSinkIter << "\n"); |
245 | 25.7k | // Process all basic blocks. |
246 | 25.7k | for (BasicBlock &I : F) |
247 | 30.5k | MadeChange |= ProcessBlock(I, DT, LI, AA); |
248 | 25.7k | EverMadeChange |= MadeChange; |
249 | 25.7k | NumSinkIter++; |
250 | 25.7k | } while (MadeChange); |
251 | 25.2k | |
252 | 25.2k | return EverMadeChange; |
253 | 25.2k | } |
254 | | |
255 | 6 | PreservedAnalyses SinkingPass::run(Function &F, FunctionAnalysisManager &AM) { |
256 | 6 | auto &DT = AM.getResult<DominatorTreeAnalysis>(F); |
257 | 6 | auto &LI = AM.getResult<LoopAnalysis>(F); |
258 | 6 | auto &AA = AM.getResult<AAManager>(F); |
259 | 6 | |
260 | 6 | if (!iterativelySinkInstructions(F, DT, LI, AA)) |
261 | 2 | return PreservedAnalyses::all(); |
262 | 4 | |
263 | 4 | PreservedAnalyses PA; |
264 | 4 | PA.preserveSet<CFGAnalyses>(); |
265 | 4 | return PA; |
266 | 4 | } |
267 | | |
268 | | namespace { |
269 | | class SinkingLegacyPass : public FunctionPass { |
270 | | public: |
271 | | static char ID; // Pass identification |
272 | 2.45k | SinkingLegacyPass() : FunctionPass(ID) { |
273 | 2.45k | initializeSinkingLegacyPassPass(*PassRegistry::getPassRegistry()); |
274 | 2.45k | } |
275 | | |
276 | 25.2k | bool runOnFunction(Function &F) override { |
277 | 25.2k | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
278 | 25.2k | auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
279 | 25.2k | auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); |
280 | 25.2k | |
281 | 25.2k | return iterativelySinkInstructions(F, DT, LI, AA); |
282 | 25.2k | } |
283 | | |
284 | 2.43k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
285 | 2.43k | AU.setPreservesCFG(); |
286 | 2.43k | FunctionPass::getAnalysisUsage(AU); |
287 | 2.43k | AU.addRequired<AAResultsWrapperPass>(); |
288 | 2.43k | AU.addRequired<DominatorTreeWrapperPass>(); |
289 | 2.43k | AU.addRequired<LoopInfoWrapperPass>(); |
290 | 2.43k | AU.addPreserved<DominatorTreeWrapperPass>(); |
291 | 2.43k | AU.addPreserved<LoopInfoWrapperPass>(); |
292 | 2.43k | } |
293 | | }; |
294 | | } // end anonymous namespace |
295 | | |
296 | | char SinkingLegacyPass::ID = 0; |
297 | 36.0k | INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false) |
298 | 36.0k | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) |
299 | 36.0k | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
300 | 36.0k | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) |
301 | 36.0k | INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false) |
302 | | |
303 | 2.44k | FunctionPass *llvm::createSinkingPass() { return new SinkingLegacyPass(); } |