blob: 0071428354e6f62f8766b4ca9ab48ea75e8f61af [file] [log] [blame]
Dan Gohman28a193e2010-05-07 15:40:13 +00001//===-- Sink.cpp - Code Sinking -------------------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass moves instructions into successor blocks, when possible, so that
11// they aren't executed on paths where their results aren't needed.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "sink"
16#include "llvm/Transforms/Scalar.h"
17#include "llvm/IntrinsicInst.h"
18#include "llvm/Analysis/Dominators.h"
19#include "llvm/Analysis/LoopInfo.h"
20#include "llvm/Analysis/AliasAnalysis.h"
21#include "llvm/Assembly/Writer.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/Support/CFG.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/raw_ostream.h"
26using namespace llvm;
27
28STATISTIC(NumSunk, "Number of instructions sunk");
29
30namespace {
31 class Sinking : public FunctionPass {
32 DominatorTree *DT;
33 LoopInfo *LI;
34 AliasAnalysis *AA;
35
36 public:
37 static char ID; // Pass identification
Owen Anderson90c579d2010-08-06 18:33:48 +000038 Sinking() : FunctionPass(ID) {}
Dan Gohman28a193e2010-05-07 15:40:13 +000039
40 virtual bool runOnFunction(Function &F);
41
42 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
43 AU.setPreservesCFG();
44 FunctionPass::getAnalysisUsage(AU);
45 AU.addRequired<AliasAnalysis>();
46 AU.addRequired<DominatorTree>();
47 AU.addRequired<LoopInfo>();
48 AU.addPreserved<DominatorTree>();
49 AU.addPreserved<LoopInfo>();
50 }
51 private:
52 bool ProcessBlock(BasicBlock &BB);
53 bool SinkInstruction(Instruction *I, SmallPtrSet<Instruction *, 8> &Stores);
54 bool AllUsesDominatedByBlock(Instruction *Inst, BasicBlock *BB) const;
55 };
56} // end anonymous namespace
57
58char Sinking::ID = 0;
Owen Anderson2ab36d32010-10-12 19:48:12 +000059INITIALIZE_PASS_BEGIN(Sinking, "sink", "Code sinking", false, false)
60INITIALIZE_PASS_DEPENDENCY(LoopInfo)
61INITIALIZE_PASS_DEPENDENCY(DominatorTree)
62INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
63INITIALIZE_PASS_END(Sinking, "sink", "Code sinking", false, false)
Dan Gohman28a193e2010-05-07 15:40:13 +000064
65FunctionPass *llvm::createSinkingPass() { return new Sinking(); }
66
67/// AllUsesDominatedByBlock - Return true if all uses of the specified value
68/// occur in blocks dominated by the specified block.
69bool Sinking::AllUsesDominatedByBlock(Instruction *Inst,
70 BasicBlock *BB) const {
71 // Ignoring debug uses is necessary so debug info doesn't affect the code.
72 // This may leave a referencing dbg_value in the original block, before
73 // the definition of the vreg. Dwarf generator handles this although the
74 // user might not get the right info at runtime.
75 for (Value::use_iterator I = Inst->use_begin(),
76 E = Inst->use_end(); I != E; ++I) {
77 // Determine the block of the use.
78 Instruction *UseInst = cast<Instruction>(*I);
79 BasicBlock *UseBlock = UseInst->getParent();
80 if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
81 // PHI nodes use the operand in the predecessor block, not the block with
82 // the PHI.
83 unsigned Num = PHINode::getIncomingValueNumForOperand(I.getOperandNo());
84 UseBlock = PN->getIncomingBlock(Num);
85 }
86 // Check that it dominates.
87 if (!DT->dominates(BB, UseBlock))
88 return false;
89 }
90 return true;
91}
92
93bool Sinking::runOnFunction(Function &F) {
94 DT = &getAnalysis<DominatorTree>();
95 LI = &getAnalysis<LoopInfo>();
96 AA = &getAnalysis<AliasAnalysis>();
97
98 bool EverMadeChange = false;
99
100 while (1) {
101 bool MadeChange = false;
102
103 // Process all basic blocks.
104 for (Function::iterator I = F.begin(), E = F.end();
105 I != E; ++I)
106 MadeChange |= ProcessBlock(*I);
107
108 // If this iteration over the code changed anything, keep iterating.
109 if (!MadeChange) break;
110 EverMadeChange = true;
111 }
112 return EverMadeChange;
113}
114
115bool Sinking::ProcessBlock(BasicBlock &BB) {
116 // Can't sink anything out of a block that has less than two successors.
117 if (BB.getTerminator()->getNumSuccessors() <= 1 || BB.empty()) return false;
118
119 // Don't bother sinking code out of unreachable blocks. In addition to being
120 // unprofitable, it can also lead to infinite looping, because in an unreachable
121 // loop there may be nowhere to stop.
122 if (!DT->isReachableFromEntry(&BB)) return false;
123
124 bool MadeChange = false;
125
126 // Walk the basic block bottom-up. Remember if we saw a store.
127 BasicBlock::iterator I = BB.end();
128 --I;
129 bool ProcessedBegin = false;
130 SmallPtrSet<Instruction *, 8> Stores;
131 do {
132 Instruction *Inst = I; // The instruction to sink.
133
134 // Predecrement I (if it's not begin) so that it isn't invalidated by
135 // sinking.
136 ProcessedBegin = I == BB.begin();
137 if (!ProcessedBegin)
138 --I;
139
140 if (isa<DbgInfoIntrinsic>(Inst))
141 continue;
142
143 if (SinkInstruction(Inst, Stores))
144 ++NumSunk, MadeChange = true;
145
146 // If we just processed the first instruction in the block, we're done.
147 } while (!ProcessedBegin);
148
149 return MadeChange;
150}
151
152static bool isSafeToMove(Instruction *Inst, AliasAnalysis *AA,
153 SmallPtrSet<Instruction *, 8> &Stores) {
154 if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
155 if (L->isVolatile()) return false;
156
157 Value *Ptr = L->getPointerOperand();
158 unsigned Size = AA->getTypeStoreSize(L->getType());
159 for (SmallPtrSet<Instruction *, 8>::iterator I = Stores.begin(),
160 E = Stores.end(); I != E; ++I)
161 if (AA->getModRefInfo(*I, Ptr, Size) & AliasAnalysis::Mod)
162 return false;
163 }
164
165 if (Inst->mayWriteToMemory()) {
166 Stores.insert(Inst);
167 return false;
168 }
169
170 return Inst->isSafeToSpeculativelyExecute();
171}
172
173/// SinkInstruction - Determine whether it is safe to sink the specified machine
174/// instruction out of its current block into a successor.
175bool Sinking::SinkInstruction(Instruction *Inst,
176 SmallPtrSet<Instruction *, 8> &Stores) {
177 // Check if it's safe to move the instruction.
178 if (!isSafeToMove(Inst, AA, Stores))
179 return false;
180
181 // FIXME: This should include support for sinking instructions within the
182 // block they are currently in to shorten the live ranges. We often get
183 // instructions sunk into the top of a large block, but it would be better to
184 // also sink them down before their first use in the block. This xform has to
185 // be careful not to *increase* register pressure though, e.g. sinking
186 // "x = y + z" down if it kills y and z would increase the live ranges of y
187 // and z and only shrink the live range of x.
188
189 // Loop over all the operands of the specified instruction. If there is
190 // anything we can't handle, bail out.
191 BasicBlock *ParentBlock = Inst->getParent();
192
193 // SuccToSinkTo - This is the successor to sink this instruction to, once we
194 // decide.
195 BasicBlock *SuccToSinkTo = 0;
196
197 // FIXME: This picks a successor to sink into based on having one
198 // successor that dominates all the uses. However, there are cases where
199 // sinking can happen but where the sink point isn't a successor. For
200 // example:
201 // x = computation
202 // if () {} else {}
203 // use x
204 // the instruction could be sunk over the whole diamond for the
205 // if/then/else (or loop, etc), allowing it to be sunk into other blocks
206 // after that.
207
208 // Instructions can only be sunk if all their uses are in blocks
209 // dominated by one of the successors.
210 // Look at all the successors and decide which one
211 // we should sink to.
212 for (succ_iterator SI = succ_begin(ParentBlock),
213 E = succ_end(ParentBlock); SI != E; ++SI) {
214 if (AllUsesDominatedByBlock(Inst, *SI)) {
215 SuccToSinkTo = *SI;
216 break;
217 }
218 }
219
220 // If we couldn't find a block to sink to, ignore this instruction.
221 if (SuccToSinkTo == 0)
222 return false;
223
224 // It is not possible to sink an instruction into its own block. This can
225 // happen with loops.
226 if (Inst->getParent() == SuccToSinkTo)
227 return false;
228
229 DEBUG(dbgs() << "Sink instr " << *Inst);
230 DEBUG(dbgs() << "to block ";
231 WriteAsOperand(dbgs(), SuccToSinkTo, false));
232
233 // If the block has multiple predecessors, this would introduce computation on
234 // a path that it doesn't already exist. We could split the critical edge,
235 // but for now we just punt.
236 // FIXME: Split critical edges if not backedges.
237 if (SuccToSinkTo->getUniquePredecessor() != ParentBlock) {
238 // We cannot sink a load across a critical edge - there may be stores in
239 // other code paths.
240 if (!Inst->isSafeToSpeculativelyExecute()) {
241 DEBUG(dbgs() << " *** PUNTING: Wont sink load along critical edge.\n");
242 return false;
243 }
244
245 // We don't want to sink across a critical edge if we don't dominate the
246 // successor. We could be introducing calculations to new code paths.
247 if (!DT->dominates(ParentBlock, SuccToSinkTo)) {
248 DEBUG(dbgs() << " *** PUNTING: Critical edge found\n");
249 return false;
250 }
251
252 // Don't sink instructions into a loop.
253 if (LI->isLoopHeader(SuccToSinkTo)) {
254 DEBUG(dbgs() << " *** PUNTING: Loop header found\n");
255 return false;
256 }
257
258 // Otherwise we are OK with sinking along a critical edge.
259 DEBUG(dbgs() << "Sinking along critical edge.\n");
260 }
261
262 // Determine where to insert into. Skip phi nodes.
263 BasicBlock::iterator InsertPos = SuccToSinkTo->begin();
264 while (InsertPos != SuccToSinkTo->end() && isa<PHINode>(InsertPos))
265 ++InsertPos;
266
267 // Move the instruction.
268 Inst->moveBefore(InsertPos);
269 return true;
270}