blob: 85e1eac267e3b27012128a71d990fddd0bc2d417 [file] [log] [blame]
Chris Lattnera5434ca2003-06-22 20:10:28 +00001//===- TailDuplication.cpp - Simplify CFG through tail duplication --------===//
John Criswell482202a2003-10-20 19:43:21 +00002//
3// The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
Chris Lattnera5434ca2003-06-22 20:10:28 +00009//
10// This pass performs a limited form of tail duplication, intended to simplify
11// CFGs by removing some unconditional branches. This pass is necessary to
12// straighten out loops created by the C front-end, but also is capable of
13// making other code nicer. After this pass is run, the CFG simplify pass
14// should be run to clean up the mess.
15//
16// This pass could be enhanced in the future to use profile information to be
17// more aggressive.
18//
19//===----------------------------------------------------------------------===//
20
21#include "llvm/Transforms/Scalar.h"
Chris Lattner1c884e12003-08-31 21:17:44 +000022#include "llvm/Constant.h"
Chris Lattnera5434ca2003-06-22 20:10:28 +000023#include "llvm/Function.h"
Misha Brukman2b3387a2004-07-29 17:05:13 +000024#include "llvm/Instructions.h"
Chris Lattnera5434ca2003-06-22 20:10:28 +000025#include "llvm/Pass.h"
26#include "llvm/Type.h"
27#include "llvm/Support/CFG.h"
28#include "llvm/Transforms/Utils/Local.h"
Reid Spencer7c16caa2004-09-01 22:55:40 +000029#include "llvm/Support/CommandLine.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/ADT/Statistic.h"
Chris Lattner49525f82004-01-09 06:02:20 +000032using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000033
Chris Lattnera5434ca2003-06-22 20:10:28 +000034namespace {
Chris Lattnerc14da962004-04-18 00:52:43 +000035 cl::opt<unsigned>
36 Threshold("taildup-threshold", cl::desc("Max block size to tail duplicate"),
37 cl::init(6), cl::Hidden);
Chris Lattnera5434ca2003-06-22 20:10:28 +000038 Statistic<> NumEliminated("tailduplicate",
39 "Number of unconditional branches eliminated");
40 Statistic<> NumPHINodes("tailduplicate", "Number of phi nodes inserted");
41
42 class TailDup : public FunctionPass {
43 bool runOnFunction(Function &F);
44 private:
45 inline bool shouldEliminateUnconditionalBranch(TerminatorInst *TI);
46 inline void eliminateUnconditionalBranch(BranchInst *BI);
Chris Lattnera5434ca2003-06-22 20:10:28 +000047 };
48 RegisterOpt<TailDup> X("tailduplicate", "Tail Duplication");
49}
50
Brian Gaeke960707c2003-11-11 22:41:34 +000051// Public interface to the Tail Duplication pass
Chris Lattner3e860842004-09-20 04:43:15 +000052FunctionPass *llvm::createTailDuplicationPass() { return new TailDup(); }
Chris Lattnera5434ca2003-06-22 20:10:28 +000053
54/// runOnFunction - Top level algorithm - Loop over each unconditional branch in
55/// the function, eliminating it if it looks attractive enough.
56///
57bool TailDup::runOnFunction(Function &F) {
58 bool Changed = false;
59 for (Function::iterator I = F.begin(), E = F.end(); I != E; )
Chris Lattner95057f62004-03-16 23:29:09 +000060 if (shouldEliminateUnconditionalBranch(I->getTerminator())) {
Chris Lattnera5434ca2003-06-22 20:10:28 +000061 eliminateUnconditionalBranch(cast<BranchInst>(I->getTerminator()));
62 Changed = true;
63 } else {
64 ++I;
65 }
66 return Changed;
67}
68
69/// shouldEliminateUnconditionalBranch - Return true if this branch looks
70/// attractive to eliminate. We eliminate the branch if the destination basic
71/// block has <= 5 instructions in it, not counting PHI nodes. In practice,
72/// since one of these is a terminator instruction, this means that we will add
73/// up to 4 instructions to the new block.
74///
75/// We don't count PHI nodes in the count since they will be removed when the
76/// contents of the block are copied over.
77///
78bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI) {
79 BranchInst *BI = dyn_cast<BranchInst>(TI);
80 if (!BI || !BI->isUnconditional()) return false; // Not an uncond branch!
81
82 BasicBlock *Dest = BI->getSuccessor(0);
83 if (Dest == BI->getParent()) return false; // Do not loop infinitely!
84
Chris Lattnerd78ebd02003-07-23 03:32:41 +000085 // Do not inline a block if we will just get another branch to the same block!
Chris Lattnera64923a2004-03-16 19:45:22 +000086 TerminatorInst *DTI = Dest->getTerminator();
87 if (BranchInst *DBI = dyn_cast<BranchInst>(DTI))
Chris Lattnerd78ebd02003-07-23 03:32:41 +000088 if (DBI->isUnconditional() && DBI->getSuccessor(0) == Dest)
89 return false; // Do not loop infinitely!
90
Chris Lattner95057f62004-03-16 23:29:09 +000091 // FIXME: DemoteRegToStack cannot yet demote invoke instructions to the stack,
92 // because doing so would require breaking critical edges. This should be
93 // fixed eventually.
94 if (!DTI->use_empty())
95 return false;
96
Chris Lattnera5434ca2003-06-22 20:10:28 +000097 // Do not bother working on dead blocks...
98 pred_iterator PI = pred_begin(Dest), PE = pred_end(Dest);
99 if (PI == PE && Dest != Dest->getParent()->begin())
100 return false; // It's just a dead block, ignore it...
101
102 // Also, do not bother with blocks with only a single predecessor: simplify
103 // CFG will fold these two blocks together!
104 ++PI;
105 if (PI == PE) return false; // Exactly one predecessor!
106
107 BasicBlock::iterator I = Dest->begin();
108 while (isa<PHINode>(*I)) ++I;
109
110 for (unsigned Size = 0; I != Dest->end(); ++Size, ++I)
Chris Lattnerc14da962004-04-18 00:52:43 +0000111 if (Size == Threshold) return false; // The block is too large...
Chris Lattnera64923a2004-03-16 19:45:22 +0000112
113 // Do not tail duplicate a block that has thousands of successors into a block
114 // with a single successor if the block has many other predecessors. This can
115 // cause an N^2 explosion in CFG edges (and PHI node entries), as seen in
116 // cases that have a large number of indirect gotos.
117 if (DTI->getNumSuccessors() > 8)
118 if (std::distance(PI, PE) * DTI->getNumSuccessors() > 128)
119 return false;
120
Chris Lattnera5434ca2003-06-22 20:10:28 +0000121 return true;
122}
123
Chris Lattner2ce32df2004-10-06 03:27:37 +0000124/// FindObviousSharedDomOf - We know there is a branch from SrcBlock to
125/// DestBlock, and that SrcBlock is not the only predecessor of DstBlock. If we
126/// can find a predecessor of SrcBlock that is a dominator of both SrcBlock and
127/// DstBlock, return it.
128static BasicBlock *FindObviousSharedDomOf(BasicBlock *SrcBlock,
129 BasicBlock *DstBlock) {
130 // SrcBlock must have a single predecessor.
131 pred_iterator PI = pred_begin(SrcBlock), PE = pred_end(SrcBlock);
132 if (PI == PE || ++PI != PE) return 0;
133
134 BasicBlock *SrcPred = *pred_begin(SrcBlock);
135
136 // Look at the predecessors of DstBlock. One of them will be SrcBlock. If
137 // there is only one other pred, get it, otherwise we can't handle it.
138 PI = pred_begin(DstBlock); PE = pred_end(DstBlock);
139 BasicBlock *DstOtherPred = 0;
140 if (*PI == SrcBlock) {
141 if (++PI == PE) return 0;
142 DstOtherPred = *PI;
143 if (++PI != PE) return 0;
144 } else {
145 DstOtherPred = *PI;
146 if (++PI == PE || *PI != SrcBlock || ++PI != PE) return 0;
147 }
148
149 // We can handle two situations here: "if then" and "if then else" blocks. An
150 // 'if then' situation is just where DstOtherPred == SrcPred.
151 if (DstOtherPred == SrcPred)
152 return SrcPred;
153
154 // Check to see if we have an "if then else" situation, which means that
155 // DstOtherPred will have a single predecessor and it will be SrcPred.
156 PI = pred_begin(DstOtherPred); PE = pred_end(DstOtherPred);
157 if (PI != PE && *PI == SrcPred) {
158 if (++PI != PE) return 0; // Not a single pred.
159 return SrcPred; // Otherwise, it's an "if then" situation. Return the if.
160 }
161
162 // Otherwise, this is something we can't handle.
163 return 0;
164}
165
Chris Lattnera5434ca2003-06-22 20:10:28 +0000166
167/// eliminateUnconditionalBranch - Clone the instructions from the destination
168/// block into the source block, eliminating the specified unconditional branch.
169/// If the destination block defines values used by successors of the dest
170/// block, we may need to insert PHI nodes.
171///
172void TailDup::eliminateUnconditionalBranch(BranchInst *Branch) {
173 BasicBlock *SourceBlock = Branch->getParent();
174 BasicBlock *DestBlock = Branch->getSuccessor(0);
175 assert(SourceBlock != DestBlock && "Our predicate is broken!");
176
177 DEBUG(std::cerr << "TailDuplication[" << SourceBlock->getParent()->getName()
178 << "]: Eliminating branch: " << *Branch);
179
Chris Lattner2ce32df2004-10-06 03:27:37 +0000180 // See if we can avoid duplicating code by moving it up to a dominator of both
181 // blocks.
182 if (BasicBlock *DomBlock = FindObviousSharedDomOf(SourceBlock, DestBlock)) {
183 DEBUG(std::cerr << "Found shared dominator: " << DomBlock->getName()
184 << "\n");
185
186 // If there are non-phi instructions in DestBlock that have no operands
187 // defined in DestBlock, and if the instruction has no side effects, we can
188 // move the instruction to DomBlock instead of duplicating it.
189 BasicBlock::iterator BBI = DestBlock->begin();
190 while (isa<PHINode>(BBI)) ++BBI;
191 while (!isa<TerminatorInst>(BBI)) {
192 Instruction *I = BBI++;
193
194 bool CanHoist = !I->isTrapping() && !I->mayWriteToMemory();
195 if (CanHoist) {
196 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
197 if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(op)))
198 if (OpI->getParent() == DestBlock ||
199 (isa<InvokeInst>(OpI) && OpI->getParent() == DomBlock)) {
200 CanHoist = false;
201 break;
202 }
203 if (CanHoist) {
204 // Remove from DestBlock, move right before the term in DomBlock.
205 DestBlock->getInstList().remove(I);
206 DomBlock->getInstList().insert(DomBlock->getTerminator(), I);
207 DEBUG(std::cerr << "Hoisted: " << *I);
208 }
209 }
210 }
211 }
212
Chris Lattner95057f62004-03-16 23:29:09 +0000213 // Tail duplication can not update SSA properties correctly if the values
214 // defined in the duplicated tail are used outside of the tail itself. For
215 // this reason, we spill all values that are used outside of the tail to the
216 // stack.
217 for (BasicBlock::iterator I = DestBlock->begin(); I != DestBlock->end(); ++I)
218 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
219 ++UI) {
220 bool ShouldDemote = false;
221 if (cast<Instruction>(*UI)->getParent() != DestBlock) {
222 // We must allow our successors to use tail values in their PHI nodes
223 // (if the incoming value corresponds to the tail block).
224 if (PHINode *PN = dyn_cast<PHINode>(*UI)) {
225 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
226 if (PN->getIncomingValue(i) == I &&
227 PN->getIncomingBlock(i) != DestBlock) {
228 ShouldDemote = true;
229 break;
230 }
231
232 } else {
233 ShouldDemote = true;
234 }
235 } else if (PHINode *PN = dyn_cast<PHINode>(cast<Instruction>(*UI))) {
236 // If the user of this instruction is a PHI node in the current block,
Chris Lattnera3783a52004-03-16 23:36:49 +0000237 // which has an entry from another block using the value, spill it.
238 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
239 if (PN->getIncomingValue(i) == I &&
240 PN->getIncomingBlock(i) != DestBlock) {
241 ShouldDemote = true;
242 break;
243 }
Chris Lattner95057f62004-03-16 23:29:09 +0000244 }
245
246 if (ShouldDemote) {
247 // We found a use outside of the tail. Create a new stack slot to
248 // break this inter-block usage pattern.
249 DemoteRegToStack(*I);
250 break;
251 }
252 }
253
Chris Lattnera5434ca2003-06-22 20:10:28 +0000254 // We are going to have to map operands from the original block B to the new
255 // copy of the block B'. If there are PHI nodes in the DestBlock, these PHI
256 // nodes also define part of this mapping. Loop over these PHI nodes, adding
257 // them to our mapping.
Chris Lattner268c1392003-06-22 20:25:27 +0000258 //
Chris Lattnera5434ca2003-06-22 20:10:28 +0000259 std::map<Value*, Value*> ValueMapping;
260
261 BasicBlock::iterator BI = DestBlock->begin();
262 bool HadPHINodes = isa<PHINode>(BI);
263 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
264 ValueMapping[PN] = PN->getIncomingValueForBlock(SourceBlock);
265
266 // Clone the non-phi instructions of the dest block into the source block,
267 // keeping track of the mapping...
268 //
269 for (; BI != DestBlock->end(); ++BI) {
270 Instruction *New = BI->clone();
271 New->setName(BI->getName());
272 SourceBlock->getInstList().push_back(New);
273 ValueMapping[BI] = New;
274 }
275
276 // Now that we have built the mapping information and cloned all of the
277 // instructions (giving us a new terminator, among other things), walk the new
278 // instructions, rewriting references of old instructions to use new
279 // instructions.
280 //
281 BI = Branch; ++BI; // Get an iterator to the first new instruction
282 for (; BI != SourceBlock->end(); ++BI)
283 for (unsigned i = 0, e = BI->getNumOperands(); i != e; ++i)
284 if (Value *Remapped = ValueMapping[BI->getOperand(i)])
285 BI->setOperand(i, Remapped);
286
287 // Next we check to see if any of the successors of DestBlock had PHI nodes.
288 // If so, we need to add entries to the PHI nodes for SourceBlock now.
289 for (succ_iterator SI = succ_begin(DestBlock), SE = succ_end(DestBlock);
290 SI != SE; ++SI) {
291 BasicBlock *Succ = *SI;
Reid Spencer66149462004-09-15 17:06:42 +0000292 for (BasicBlock::iterator PNI = Succ->begin(); isa<PHINode>(PNI); ++PNI) {
293 PHINode *PN = cast<PHINode>(PNI);
Chris Lattnera5434ca2003-06-22 20:10:28 +0000294 // Ok, we have a PHI node. Figure out what the incoming value was for the
295 // DestBlock.
296 Value *IV = PN->getIncomingValueForBlock(DestBlock);
297
298 // Remap the value if necessary...
299 if (Value *MappedIV = ValueMapping[IV])
300 IV = MappedIV;
301 PN->addIncoming(IV, SourceBlock);
302 }
303 }
Chris Lattner95057f62004-03-16 23:29:09 +0000304
305 // Next, remove the old branch instruction, and any PHI node entries that we
306 // had.
307 BI = Branch; ++BI; // Get an iterator to the first new instruction
308 DestBlock->removePredecessor(SourceBlock); // Remove entries in PHI nodes...
309 SourceBlock->getInstList().erase(Branch); // Destroy the uncond branch...
Chris Lattnera5434ca2003-06-22 20:10:28 +0000310
311 // Final step: now that we have finished everything up, walk the cloned
312 // instructions one last time, constant propagating and DCE'ing them, because
313 // they may not be needed anymore.
314 //
Chris Lattnera5434ca2003-06-22 20:10:28 +0000315 if (HadPHINodes)
316 while (BI != SourceBlock->end())
317 if (!dceInstruction(BI) && !doConstantPropagation(BI))
318 ++BI;
319
Chris Lattnera5434ca2003-06-22 20:10:28 +0000320 ++NumEliminated; // We just killed a branch!
321}