aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Transforms/Scalar/TailDuplication.cpp
blob: 95226a2503effb58a5f9ed5693579120d1d8c3c9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
//===- TailDuplication.cpp - Simplify CFG through tail duplication --------===//
// 
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
// 
//===----------------------------------------------------------------------===//
//
// This pass performs a limited form of tail duplication, intended to simplify
// CFGs by removing some unconditional branches.  This pass is necessary to
// straighten out loops created by the C front-end, but also is capable of
// making other code nicer.  After this pass is run, the CFG simplify pass
// should be run to clean up the mess.
//
// This pass could be enhanced in the future to use profile information to be
// more aggressive.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constant.h"
#include "llvm/Function.h"
#include "llvm/iPHINode.h"
#include "llvm/iTerminators.h"
#include "llvm/Pass.h"
#include "llvm/Type.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/ValueHolder.h"
#include "llvm/Transforms/Utils/Local.h"
#include "Support/Debug.h"
#include "Support/Statistic.h"
using namespace llvm;

namespace {
  Statistic<> NumEliminated("tailduplicate",
                            "Number of unconditional branches eliminated");
  Statistic<> NumPHINodes("tailduplicate", "Number of phi nodes inserted");

  class TailDup : public FunctionPass {
    bool runOnFunction(Function &F);
  private:
    inline bool shouldEliminateUnconditionalBranch(TerminatorInst *TI);
    inline void eliminateUnconditionalBranch(BranchInst *BI);
    inline void InsertPHINodesIfNecessary(Instruction *OrigInst, Value *NewInst,
                                          BasicBlock *NewBlock);
    inline Value *GetValueInBlock(BasicBlock *BB, Value *OrigVal,
                                  std::map<BasicBlock*, ValueHolder> &ValueMap,
                              std::map<BasicBlock*, ValueHolder> &OutValueMap);
    inline Value *GetValueOutBlock(BasicBlock *BB, Value *OrigVal,
                                   std::map<BasicBlock*, ValueHolder> &ValueMap,
                               std::map<BasicBlock*, ValueHolder> &OutValueMap);
  };
  RegisterOpt<TailDup> X("tailduplicate", "Tail Duplication");
}

// Public interface to the Tail Duplication pass
Pass *llvm::createTailDuplicationPass() { return new TailDup(); }

/// runOnFunction - Top level algorithm - Loop over each unconditional branch in
/// the function, eliminating it if it looks attractive enough.
///
bool TailDup::runOnFunction(Function &F) {
  bool Changed = false;
  for (Function::iterator I = F.begin(), E = F.end(); I != E; )
    if (shouldEliminateUnconditionalBranch(I->getTerminator())) {
      eliminateUnconditionalBranch(cast<BranchInst>(I->getTerminator()));
      Changed = true;
    } else {
      ++I;
    }
  return Changed;
}

/// shouldEliminateUnconditionalBranch - Return true if this branch looks
/// attractive to eliminate.  We eliminate the branch if the destination basic
/// block has <= 5 instructions in it, not counting PHI nodes.  In practice,
/// since one of these is a terminator instruction, this means that we will add
/// up to 4 instructions to the new block.
///
/// We don't count PHI nodes in the count since they will be removed when the
/// contents of the block are copied over.
///
bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI) {
  BranchInst *BI = dyn_cast<BranchInst>(TI);
  if (!BI || !BI->isUnconditional()) return false;  // Not an uncond branch!

  BasicBlock *Dest = BI->getSuccessor(0);
  if (Dest == BI->getParent()) return false;        // Do not loop infinitely!

  // Do not inline a block if we will just get another branch to the same block!
  if (BranchInst *DBI = dyn_cast<BranchInst>(Dest->getTerminator()))
    if (DBI->isUnconditional() && DBI->getSuccessor(0) == Dest)
      return false;                                 // Do not loop infinitely!

  // Do not bother working on dead blocks...
  pred_iterator PI = pred_begin(Dest), PE = pred_end(Dest);
  if (PI == PE && Dest != Dest->getParent()->begin())
    return false;   // It's just a dead block, ignore it...

  // Also, do not bother with blocks with only a single predecessor: simplify
  // CFG will fold these two blocks together!
  ++PI;
  if (PI == PE) return false;  // Exactly one predecessor!

  BasicBlock::iterator I = Dest->begin();
  while (isa<PHINode>(*I)) ++I;

  for (unsigned Size = 0; I != Dest->end(); ++Size, ++I)
    if (Size == 6) return false;  // The block is too large...
  return true;  
}


/// eliminateUnconditionalBranch - Clone the instructions from the destination
/// block into the source block, eliminating the specified unconditional branch.
/// If the destination block defines values used by successors of the dest
/// block, we may need to insert PHI nodes.
///
void TailDup::eliminateUnconditionalBranch(BranchInst *Branch) {
  BasicBlock *SourceBlock = Branch->getParent();
  BasicBlock *DestBlock = Branch->getSuccessor(0);
  assert(SourceBlock != DestBlock && "Our predicate is broken!");

  DEBUG(std::cerr << "TailDuplication[" << SourceBlock->getParent()->getName()
                  << "]: Eliminating branch: " << *Branch);

  // We are going to have to map operands from the original block B to the new
  // copy of the block B'.  If there are PHI nodes in the DestBlock, these PHI
  // nodes also define part of this mapping.  Loop over these PHI nodes, adding
  // them to our mapping.
  //
  std::map<Value*, Value*> ValueMapping;

  BasicBlock::iterator BI = DestBlock->begin();
  bool HadPHINodes = isa<PHINode>(BI);
  for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
    ValueMapping[PN] = PN->getIncomingValueForBlock(SourceBlock);

  // Clone the non-phi instructions of the dest block into the source block,
  // keeping track of the mapping...
  //
  for (; BI != DestBlock->end(); ++BI) {
    Instruction *New = BI->clone();
    New->setName(BI->getName());
    SourceBlock->getInstList().push_back(New);
    ValueMapping[BI] = New;
  }

  // Now that we have built the mapping information and cloned all of the
  // instructions (giving us a new terminator, among other things), walk the new
  // instructions, rewriting references of old instructions to use new
  // instructions.
  //
  BI = Branch; ++BI;  // Get an iterator to the first new instruction
  for (; BI != SourceBlock->end(); ++BI)
    for (unsigned i = 0, e = BI->getNumOperands(); i != e; ++i)
      if (Value *Remapped = ValueMapping[BI->getOperand(i)])
        BI->setOperand(i, Remapped);

  // Next we check to see if any of the successors of DestBlock had PHI nodes.
  // If so, we need to add entries to the PHI nodes for SourceBlock now.
  for (succ_iterator SI = succ_begin(DestBlock), SE = succ_end(DestBlock);
       SI != SE; ++SI) {
    BasicBlock *Succ = *SI;
    for (BasicBlock::iterator PNI = Succ->begin();
         PHINode *PN = dyn_cast<PHINode>(PNI); ++PNI) {
      // Ok, we have a PHI node.  Figure out what the incoming value was for the
      // DestBlock.
      Value *IV = PN->getIncomingValueForBlock(DestBlock);
      
      // Remap the value if necessary...
      if (Value *MappedIV = ValueMapping[IV])
        IV = MappedIV;
      PN->addIncoming(IV, SourceBlock);
    }
  }
  
  // Now that all of the instructions are correctly copied into the SourceBlock,
  // we have one more minor problem: the successors of the original DestBB may
  // use the values computed in DestBB either directly (if DestBB dominated the
  // block), or through a PHI node.  In either case, we need to insert PHI nodes
  // into any successors of DestBB (which are now our successors) for each value
  // that is computed in DestBB, but is used outside of it.  All of these uses
  // we have to rewrite with the new PHI node.
  //
  if (succ_begin(SourceBlock) != succ_end(SourceBlock)) // Avoid wasting time...
    for (BI = DestBlock->begin(); BI != DestBlock->end(); ++BI)
      if (BI->getType() != Type::VoidTy)
        InsertPHINodesIfNecessary(BI, ValueMapping[BI], SourceBlock);

  // Final step: now that we have finished everything up, walk the cloned
  // instructions one last time, constant propagating and DCE'ing them, because
  // they may not be needed anymore.
  //
  BI = Branch; ++BI;  // Get an iterator to the first new instruction
  if (HadPHINodes)
    while (BI != SourceBlock->end())
      if (!dceInstruction(BI) && !doConstantPropagation(BI))
        ++BI;

  DestBlock->removePredecessor(SourceBlock); // Remove entries in PHI nodes...
  SourceBlock->getInstList().erase(Branch);  // Destroy the uncond branch...
  
  ++NumEliminated;  // We just killed a branch!
}

/// InsertPHINodesIfNecessary - So at this point, we cloned the OrigInst
/// instruction into the NewBlock with the value of NewInst.  If OrigInst was
/// used outside of its defining basic block, we need to insert a PHI nodes into
/// the successors.
///
void TailDup::InsertPHINodesIfNecessary(Instruction *OrigInst, Value *NewInst,
                                        BasicBlock *NewBlock) {
  // Loop over all of the uses of OrigInst, rewriting them to be newly inserted
  // PHI nodes, unless they are in the same basic block as OrigInst.
  BasicBlock *OrigBlock = OrigInst->getParent();
  std::vector<Instruction*> Users;
  Users.reserve(OrigInst->use_size());
  for (Value::use_iterator I = OrigInst->use_begin(), E = OrigInst->use_end();
       I != E; ++I) {
    Instruction *In = cast<Instruction>(*I);
    if (In->getParent() != OrigBlock ||  // Don't modify uses in the orig block!
        isa<PHINode>(In))
      Users.push_back(In);
  }

  // The common case is that the instruction is only used within the block that
  // defines it.  If we have this case, quick exit.
  //
  if (Users.empty()) return; 

  // Otherwise, we have a more complex case, handle it now.  This requires the
  // construction of a mapping between a basic block and the value to use when
  // in the scope of that basic block.  This map will map to the original and
  // new values when in the original or new block, but will map to inserted PHI
  // nodes when in other blocks.
  //
  std::map<BasicBlock*, ValueHolder> ValueMap;
  std::map<BasicBlock*, ValueHolder> OutValueMap;   // The outgoing value map
  OutValueMap[OrigBlock] = OrigInst;
  OutValueMap[NewBlock ] = NewInst;    // Seed the initial values...

  DEBUG(std::cerr << "  ** Inserting PHI nodes for " << OrigInst);
  while (!Users.empty()) {
    Instruction *User = Users.back(); Users.pop_back();

    if (PHINode *PN = dyn_cast<PHINode>(User)) {
      // PHI nodes must be handled specially here, because their operands are
      // actually defined in predecessor basic blocks, NOT in the block that the
      // PHI node lives in.  Note that we have already added entries to PHI nods
      // which are in blocks that are immediate successors of OrigBlock, so
      // don't modify them again.
      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
        if (PN->getIncomingValue(i) == OrigInst &&
            PN->getIncomingBlock(i) != OrigBlock) {
          Value *V = GetValueOutBlock(PN->getIncomingBlock(i), OrigInst,
                                      ValueMap, OutValueMap);
          PN->setIncomingValue(i, V);
        }
      
    } else {
      // Any other user of the instruction can just replace any uses with the
      // new value defined in the block it resides in.
      Value *V = GetValueInBlock(User->getParent(), OrigInst, ValueMap,
                                 OutValueMap);
      User->replaceUsesOfWith(OrigInst, V);
    }
  }
}

/// GetValueInBlock - This is a recursive method which inserts PHI nodes into
/// the function until there is a value available in basic block BB.
///
Value *TailDup::GetValueInBlock(BasicBlock *BB, Value *OrigVal,
                                std::map<BasicBlock*, ValueHolder> &ValueMap,
                                std::map<BasicBlock*,ValueHolder> &OutValueMap){
  ValueHolder &BBVal = ValueMap[BB];
  if (BBVal) return BBVal;       // Value already computed for this block?

  // If this block has no predecessors, then it must be unreachable, thus, it
  // doesn't matter which value we use.
  if (pred_begin(BB) == pred_end(BB))
    return BBVal = Constant::getNullValue(OrigVal->getType());

  // If there is no value already available in this basic block, we need to
  // either reuse a value from an incoming, dominating, basic block, or we need
  // to create a new PHI node to merge in different incoming values.  Because we
  // don't know if we're part of a loop at this point or not, we create a PHI
  // node, even if we will ultimately eliminate it.
  PHINode *PN = new PHINode(OrigVal->getType(), OrigVal->getName()+".pn",
                            BB->begin());
  BBVal = PN;   // Insert this into the BBVal slot in case of cycles...

  ValueHolder &BBOutVal = OutValueMap[BB];
  if (BBOutVal == 0) BBOutVal = PN;

  // Now that we have created the PHI node, loop over all of the predecessors of
  // this block, computing an incoming value for the predecessor.
  std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
  for (unsigned i = 0, e = Preds.size(); i != e; ++i)
    PN->addIncoming(GetValueOutBlock(Preds[i], OrigVal, ValueMap, OutValueMap),
                    Preds[i]);

  // The PHI node is complete.  In many cases, however the PHI node was
  // ultimately unnecessary: we could have just reused a dominating incoming
  // value.  If this is the case, nuke the PHI node and replace the map entry
  // with the dominating value.
  //
  assert(PN->getNumIncomingValues() > 0 && "No predecessors?");

  // Check to see if all of the elements in the PHI node are either the PHI node
  // itself or ONE particular value.
  unsigned i = 0;
  Value *ReplVal = PN->getIncomingValue(i);
  for (; ReplVal == PN && i != PN->getNumIncomingValues(); ++i)
    ReplVal = PN->getIncomingValue(i);  // Skip values equal to the PN

  for (; i != PN->getNumIncomingValues(); ++i)
    if (PN->getIncomingValue(i) != PN && PN->getIncomingValue(i) != ReplVal) {
      ReplVal = 0;
      break;
    }

  // Found a value to replace the PHI node with?
  if (ReplVal && ReplVal != PN) {
    PN->replaceAllUsesWith(ReplVal);
    BB->getInstList().erase(PN);   // Erase the PHI node...
  } else {
    ++NumPHINodes;
  }

  return BBVal;
}

Value *TailDup::GetValueOutBlock(BasicBlock *BB, Value *OrigVal,
                                 std::map<BasicBlock*, ValueHolder> &ValueMap,
                              std::map<BasicBlock*, ValueHolder> &OutValueMap) {
  ValueHolder &BBVal = OutValueMap[BB];
  if (BBVal) return BBVal;       // Value already computed for this block?

  return GetValueInBlock(BB, OrigVal, ValueMap, OutValueMap);
}