← Back to branch summary

~ubuntu-branches/ubuntu/quantal/llvm-3.1/quantal

« back to all changes in this revision

Viewing changes to lib/Transforms/Utils/LoopUnrollRuntime.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2012-03-29 19:09:51 UTC
  • Revision ID: package-import@ubuntu.com-20120329190951-aq83ivog4cg8bxun
Tags: upstream-3.1~svn153643
Import upstream version 3.1~svn153643

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/Transforms/Utils/LoopUnrollRuntime.cpp
 
1
//===-- UnrollLoopRuntime.cpp - Runtime Loop unrolling utilities ----------===//
 
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 file implements some loop unrolling utilities for loops with run-time
 
11
// trip counts.  See LoopUnroll.cpp for unrolling loops with compile-time
 
12
// trip counts.
 
13
//
 
14
// The functions in this file are used to generate extra code when the
 
15
// run-time trip count modulo the unroll factor is not 0.  When this is the
 
16
// case, we need to generate code to execute these 'left over' iterations.
 
17
//
 
18
// The current strategy generates an if-then-else sequence prior to the
 
19
// unrolled loop to execute the 'left over' iterations.  Other strategies
 
20
// include generate a loop before or after the unrolled loop.
 
21
//
 
22
//===----------------------------------------------------------------------===//
 
23
 
 
24
#define DEBUG_TYPE "loop-unroll"
 
25
#include "llvm/Transforms/Utils/UnrollLoop.h"
 
26
#include "llvm/BasicBlock.h"
 
27
#include "llvm/ADT/Statistic.h"
 
28
#include "llvm/Analysis/LoopIterator.h"
 
29
#include "llvm/Analysis/LoopPass.h"
 
30
#include "llvm/Analysis/ScalarEvolution.h"
 
31
#include "llvm/Analysis/ScalarEvolutionExpander.h"
 
32
#include "llvm/Support/Debug.h"
 
33
#include "llvm/Support/raw_ostream.h"
 
34
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
35
#include "llvm/Transforms/Utils/Cloning.h"
 
36
#include <algorithm>
 
37
 
 
38
using namespace llvm;
 
39
 
 
40
STATISTIC(NumRuntimeUnrolled,
 
41
          "Number of loops unrolled with run-time trip counts");
 
42
 
 
43
/// Connect the unrolling prolog code to the original loop.
 
44
/// The unrolling prolog code contains code to execute the
 
45
/// 'extra' iterations if the run-time trip count modulo the
 
46
/// unroll count is non-zero.
 
47
///
 
48
/// This function performs the following:
 
49
/// - Create PHI nodes at prolog end block to combine values
 
50
///   that exit the prolog code and jump around the prolog.
 
51
/// - Add a PHI operand to a PHI node at the loop exit block
 
52
///   for values that exit the prolog and go around the loop.
 
53
/// - Branch around the original loop if the trip count is less
 
54
///   than the unroll factor.
 
55
///
 
56
static void ConnectProlog(Loop *L, Value *TripCount, unsigned Count,
 
57
                          BasicBlock *LastPrologBB, BasicBlock *PrologEnd,
 
58
                          BasicBlock *OrigPH, BasicBlock *NewPH,
 
59
                          ValueToValueMapTy &LVMap, Pass *P) {
 
60
  BasicBlock *Latch = L->getLoopLatch();
 
61
  assert(Latch != 0 && "Loop must have a latch");
 
62
 
 
63
  // Create a PHI node for each outgoing value from the original loop
 
64
  // (which means it is an outgoing value from the prolog code too).
 
65
  // The new PHI node is inserted in the prolog end basic block.
 
66
  // The new PHI name is added as an operand of a PHI node in either
 
67
  // the loop header or the loop exit block.
 
68
  for (succ_iterator SBI = succ_begin(Latch), SBE = succ_end(Latch);
 
69
       SBI != SBE; ++SBI) {
 
70
    for (BasicBlock::iterator BBI = (*SBI)->begin();
 
71
         PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) {
 
72
 
 
73
      // Add a new PHI node to the prolog end block and add the
 
74
      // appropriate incoming values.
 
75
      PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName()+".unr",
 
76
                                       PrologEnd->getTerminator());
 
77
      // Adding a value to the new PHI node from the original loop preheader.
 
78
      // This is the value that skips all the prolog code.
 
79
      if (L->contains(PN)) {
 
80
        NewPN->addIncoming(PN->getIncomingValueForBlock(NewPH), OrigPH);
 
81
      } else {
 
82
        NewPN->addIncoming(Constant::getNullValue(PN->getType()), OrigPH);
 
83
      }
 
84
 
 
85
      Value *V = PN->getIncomingValueForBlock(Latch);
 
86
      if (Instruction *I = dyn_cast<Instruction>(V)) {
 
87
        if (L->contains(I)) {
 
88
          V = LVMap[I];
 
89
        }
 
90
      }
 
91
      // Adding a value to the new PHI node from the last prolog block
 
92
      // that was created.
 
93
      NewPN->addIncoming(V, LastPrologBB);
 
94
 
 
95
      // Update the existing PHI node operand with the value from the
 
96
      // new PHI node.  How this is done depends on if the existing
 
97
      // PHI node is in the original loop block, or the exit block.
 
98
      if (L->contains(PN)) {
 
99
        PN->setIncomingValue(PN->getBasicBlockIndex(NewPH), NewPN);
 
100
      } else {
 
101
        PN->addIncoming(NewPN, PrologEnd);
 
102
      }
 
103
    }
 
104
  }
 
105
 
 
106
  // Create a branch around the orignal loop, which is taken if the
 
107
  // trip count is less than the unroll factor.
 
108
  Instruction *InsertPt = PrologEnd->getTerminator();
 
109
  Instruction *BrLoopExit =
 
110
    new ICmpInst(InsertPt, ICmpInst::ICMP_ULT, TripCount,
 
111
                 ConstantInt::get(TripCount->getType(), Count));
 
112
  BasicBlock *Exit = L->getUniqueExitBlock();
 
113
  assert(Exit != 0 && "Loop must have a single exit block only");
 
114
  // Split the exit to maintain loop canonicalization guarantees
 
115
  SmallVector<BasicBlock*, 4> Preds(pred_begin(Exit), pred_end(Exit));
 
116
  if (!Exit->isLandingPad()) {
 
117
    SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", P);
 
118
  } else {
 
119
    SmallVector<BasicBlock*, 2> NewBBs;
 
120
    SplitLandingPadPredecessors(Exit, Preds, ".unr1-lcssa", ".unr2-lcssa",
 
121
                                P, NewBBs);
 
122
  }
 
123
  // Add the branch to the exit block (around the unrolled loop)
 
124
  BranchInst::Create(Exit, NewPH, BrLoopExit, InsertPt);
 
125
  InsertPt->eraseFromParent();
 
126
}
 
127
 
 
128
/// Create a clone of the blocks in a loop and connect them together.
 
129
/// This function doesn't create a clone of the loop structure.
 
130
///
 
131
/// There are two value maps that are defined and used.  VMap is
 
132
/// for the values in the current loop instance.  LVMap contains
 
133
/// the values from the last loop instance.  We need the LVMap values
 
134
/// to update the inital values for the current loop instance.
 
135
///
 
136
static void CloneLoopBlocks(Loop *L,
 
137
                            bool FirstCopy,
 
138
                            BasicBlock *InsertTop,
 
139
                            BasicBlock *InsertBot,
 
140
                            std::vector<BasicBlock *> &NewBlocks,
 
141
                            LoopBlocksDFS &LoopBlocks,
 
142
                            ValueToValueMapTy &VMap,
 
143
                            ValueToValueMapTy &LVMap,
 
144
                            LoopInfo *LI) {
 
145
 
 
146
  BasicBlock *Preheader = L->getLoopPreheader();
 
147
  BasicBlock *Header = L->getHeader();
 
148
  BasicBlock *Latch = L->getLoopLatch();
 
149
  Function *F = Header->getParent();
 
150
  LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
 
151
  LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
 
152
  // For each block in the original loop, create a new copy,
 
153
  // and update the value map with the newly created values.
 
154
  for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
 
155
    BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".unr", F);
 
156
    NewBlocks.push_back(NewBB);
 
157
 
 
158
    if (Loop *ParentLoop = L->getParentLoop())
 
159
      ParentLoop->addBasicBlockToLoop(NewBB, LI->getBase());
 
160
 
 
161
    VMap[*BB] = NewBB;
 
162
    if (Header == *BB) {
 
163
      // For the first block, add a CFG connection to this newly
 
164
      // created block
 
165
      InsertTop->getTerminator()->setSuccessor(0, NewBB);
 
166
 
 
167
      // Change the incoming values to the ones defined in the
 
168
      // previously cloned loop.
 
169
      for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 
170
        PHINode *NewPHI = cast<PHINode>(VMap[I]);
 
171
        if (FirstCopy) {
 
172
          // We replace the first phi node with the value from the preheader
 
173
          VMap[I] = NewPHI->getIncomingValueForBlock(Preheader);
 
174
          NewBB->getInstList().erase(NewPHI);
 
175
        } else {
 
176
          // Update VMap with values from the previous block
 
177
          unsigned idx = NewPHI->getBasicBlockIndex(Latch);
 
178
          Value *InVal = NewPHI->getIncomingValue(idx);
 
179
          if (Instruction *I = dyn_cast<Instruction>(InVal))
 
180
            if (L->contains(I))
 
181
              InVal = LVMap[InVal];
 
182
          NewPHI->setIncomingValue(idx, InVal);
 
183
          NewPHI->setIncomingBlock(idx, InsertTop);
 
184
        }
 
185
      }
 
186
    }
 
187
 
 
188
    if (Latch == *BB) {
 
189
      VMap.erase((*BB)->getTerminator());
 
190
      NewBB->getTerminator()->eraseFromParent();
 
191
      BranchInst::Create(InsertBot, NewBB);
 
192
    }
 
193
  }
 
194
  // LastValueMap is updated with the values for the current loop
 
195
  // which are used the next time this function is called.
 
196
  for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
 
197
       VI != VE; ++VI) {
 
198
    LVMap[VI->first] = VI->second;
 
199
  }
 
200
}
 
201
 
 
202
/// Insert code in the prolog code when unrolling a loop with a
 
203
/// run-time trip-count.
 
204
///
 
205
/// This method assumes that the loop unroll factor is total number
 
206
/// of loop bodes in the loop after unrolling. (Some folks refer
 
207
/// to the unroll factor as the number of *extra* copies added).
 
208
/// We assume also that the loop unroll factor is a power-of-two. So, after
 
209
/// unrolling the loop, the number of loop bodies executed is 2,
 
210
/// 4, 8, etc.  Note - LLVM converts the if-then-sequence to a switch
 
211
/// instruction in SimplifyCFG.cpp.  Then, the backend decides how code for
 
212
/// the switch instruction is generated.
 
213
///
 
214
///    extraiters = tripcount % loopfactor
 
215
///    if (extraiters == 0) jump Loop:
 
216
///    if (extraiters == loopfactor) jump L1
 
217
///    if (extraiters == loopfactor-1) jump L2
 
218
///    ...
 
219
///    L1:  LoopBody;
 
220
///    L2:  LoopBody;
 
221
///    ...
 
222
///    if tripcount < loopfactor jump End
 
223
///    Loop:
 
224
///    ...
 
225
///    End:
 
226
///
 
227
bool llvm::UnrollRuntimeLoopProlog(Loop *L, unsigned Count, LoopInfo *LI,
 
228
                                   LPPassManager *LPM) {
 
229
  // for now, only unroll loops that contain a single exit
 
230
  if (!L->getExitingBlock())
 
231
    return false;
 
232
 
 
233
  // Make sure the loop is in canonical form, and there is a single
 
234
  // exit block only.
 
235
  if (!L->isLoopSimplifyForm() || L->getUniqueExitBlock() == 0)
 
236
    return false;
 
237
 
 
238
  // Use Scalar Evolution to compute the trip count.  This allows more
 
239
  // loops to be unrolled than relying on induction var simplification
 
240
  ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>();
 
241
  if (SE == 0)
 
242
    return false;
 
243
 
 
244
  // Only unroll loops with a computable trip count and the trip count needs
 
245
  // to be an int value (allowing a pointer type is a TODO item)
 
246
  const SCEV *BECount = SE->getBackedgeTakenCount(L);
 
247
  if (isa<SCEVCouldNotCompute>(BECount) || !BECount->getType()->isIntegerTy())
 
248
    return false;
 
249
 
 
250
  // Add 1 since the backedge count doesn't include the first loop iteration
 
251
  const SCEV *TripCountSC =
 
252
    SE->getAddExpr(BECount, SE->getConstant(BECount->getType(), 1));
 
253
  if (isa<SCEVCouldNotCompute>(TripCountSC))
 
254
    return false;
 
255
 
 
256
  // We only handle cases when the unroll factor is a power of 2.
 
257
  // Count is the loop unroll factor, the number of extra copies added + 1.
 
258
  if ((Count & (Count-1)) != 0)
 
259
    return false;
 
260
 
 
261
  // If this loop is nested, then the loop unroller changes the code in
 
262
  // parent loop, so the Scalar Evolution pass needs to be run again
 
263
  if (Loop *ParentLoop = L->getParentLoop())
 
264
    SE->forgetLoop(ParentLoop);
 
265
 
 
266
  BasicBlock *PH = L->getLoopPreheader();
 
267
  BasicBlock *Header = L->getHeader();
 
268
  BasicBlock *Latch = L->getLoopLatch();
 
269
  // It helps to splits the original preheader twice, one for the end of the
 
270
  // prolog code and one for a new loop preheader
 
271
  BasicBlock *PEnd = SplitEdge(PH, Header, LPM->getAsPass());
 
272
  BasicBlock *NewPH = SplitBlock(PEnd, PEnd->getTerminator(), LPM->getAsPass());
 
273
  BranchInst *PreHeaderBR = cast<BranchInst>(PH->getTerminator());
 
274
 
 
275
  // Compute the number of extra iterations required, which is:
 
276
  //  extra iterations = run-time trip count % (loop unroll factor + 1)
 
277
  SCEVExpander Expander(*SE, "loop-unroll");
 
278
  Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
 
279
                                            PreHeaderBR);
 
280
  Type *CountTy = TripCount->getType();
 
281
  BinaryOperator *ModVal =
 
282
    BinaryOperator::CreateURem(TripCount,
 
283
                               ConstantInt::get(CountTy, Count),
 
284
                               "xtraiter");
 
285
  ModVal->insertBefore(PreHeaderBR);
 
286
 
 
287
  // Check if for no extra iterations, then jump to unrolled loop
 
288
  Value *BranchVal = new ICmpInst(PreHeaderBR,
 
289
                                  ICmpInst::ICMP_NE, ModVal,
 
290
                                  ConstantInt::get(CountTy, 0), "lcmp");
 
291
  // Branch to either the extra iterations or the unrolled loop
 
292
  // We will fix up the true branch label when adding loop body copies
 
293
  BranchInst::Create(PEnd, PEnd, BranchVal, PreHeaderBR);
 
294
  assert(PreHeaderBR->isUnconditional() &&
 
295
         PreHeaderBR->getSuccessor(0) == PEnd &&
 
296
         "CFG edges in Preheader are not correct");
 
297
  PreHeaderBR->eraseFromParent();
 
298
 
 
299
  ValueToValueMapTy LVMap;
 
300
  Function *F = Header->getParent();
 
301
  // These variables are used to update the CFG links in each iteration
 
302
  BasicBlock *CompareBB = 0;
 
303
  BasicBlock *LastLoopBB = PH;
 
304
  // Get an ordered list of blocks in the loop to help with the ordering of the
 
305
  // cloned blocks in the prolog code
 
306
  LoopBlocksDFS LoopBlocks(L);
 
307
  LoopBlocks.perform(LI);
 
308
 
 
309
  //
 
310
  // For each extra loop iteration, create a copy of the loop's basic blocks
 
311
  // and generate a condition that branches to the copy depending on the
 
312
  // number of 'left over' iterations.
 
313
  //
 
314
  for (unsigned leftOverIters = Count-1; leftOverIters > 0; --leftOverIters) {
 
315
    std::vector<BasicBlock*> NewBlocks;
 
316
    ValueToValueMapTy VMap;
 
317
 
 
318
    // Clone all the basic blocks in the loop, but we don't clone the loop
 
319
    // This function adds the appropriate CFG connections.
 
320
    CloneLoopBlocks(L, (leftOverIters == Count-1), LastLoopBB, PEnd, NewBlocks,
 
321
                    LoopBlocks, VMap, LVMap, LI);
 
322
    LastLoopBB = cast<BasicBlock>(VMap[Latch]);
 
323
 
 
324
    // Insert the cloned blocks into function just before the original loop
 
325
    F->getBasicBlockList().splice(PEnd, F->getBasicBlockList(),
 
326
                                  NewBlocks[0], F->end());
 
327
 
 
328
    // Generate the code for the comparison which determines if the loop
 
329
    // prolog code needs to be executed.
 
330
    if (leftOverIters == Count-1) {
 
331
      // There is no compare block for the fall-thru case when for the last
 
332
      // left over iteration
 
333
      CompareBB = NewBlocks[0];
 
334
    } else {
 
335
      // Create a new block for the comparison
 
336
      BasicBlock *NewBB = BasicBlock::Create(CompareBB->getContext(), "unr.cmp",
 
337
                                             F, CompareBB);
 
338
      if (Loop *ParentLoop = L->getParentLoop()) {
 
339
        // Add the new block to the parent loop, if needed
 
340
        ParentLoop->addBasicBlockToLoop(NewBB, LI->getBase());
 
341
      }
 
342
 
 
343
      // The comparison w/ the extra iteration value and branch
 
344
      Value *BranchVal = new ICmpInst(*NewBB, ICmpInst::ICMP_EQ, ModVal,
 
345
                                      ConstantInt::get(CountTy, leftOverIters),
 
346
                                      "un.tmp");
 
347
      // Branch to either the extra iterations or the unrolled loop
 
348
      BranchInst::Create(NewBlocks[0], CompareBB,
 
349
                         BranchVal, NewBB);
 
350
      CompareBB = NewBB;
 
351
      PH->getTerminator()->setSuccessor(0, NewBB);
 
352
      VMap[NewPH] = CompareBB;
 
353
    }
 
354
 
 
355
    // Rewrite the cloned instruction operands to use the values
 
356
    // created when the clone is created.
 
357
    for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) {
 
358
      for (BasicBlock::iterator I = NewBlocks[i]->begin(),
 
359
             E = NewBlocks[i]->end(); I != E; ++I) {
 
360
        RemapInstruction(I, VMap,
 
361
                         RF_NoModuleLevelChanges|RF_IgnoreMissingEntries);
 
362
      }
 
363
    }
 
364
  }
 
365
 
 
366
  // Connect the prolog code to the original loop and update the
 
367
  // PHI functions.
 
368
  ConnectProlog(L, TripCount, Count, LastLoopBB, PEnd, PH, NewPH, LVMap,
 
369
                LPM->getAsPass());
 
370
  NumRuntimeUnrolled++;
 
371
  return true;
 
372
}