blob: c7ea283da791037685060276ba8009413e7202a8 [file] [log] [blame]
Andrew Trickd04d15292011-12-09 06:19:40 +00001//===-- 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//
Jakub Staszak1b1d5232011-12-18 21:52:30 +000014// The functions in this file are used to generate extra code when the
Andrew Trickd04d15292011-12-09 06:19:40 +000015// 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//
Jakub Staszak1b1d5232011-12-18 21:52:30 +000018// The current strategy generates an if-then-else sequence prior to the
Andrew Trickd04d15292011-12-09 06:19:40 +000019// unrolled loop to execute the 'left over' iterations. Other strategies
20// include generate a loop before or after the unrolled loop.
21//
22//===----------------------------------------------------------------------===//
23
Andrew Trickd04d15292011-12-09 06:19:40 +000024#include "llvm/Transforms/Utils/UnrollLoop.h"
Andrew Trickd04d15292011-12-09 06:19:40 +000025#include "llvm/ADT/Statistic.h"
26#include "llvm/Analysis/LoopIterator.h"
27#include "llvm/Analysis/LoopPass.h"
28#include "llvm/Analysis/ScalarEvolution.h"
29#include "llvm/Analysis/ScalarEvolutionExpander.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000030#include "llvm/IR/BasicBlock.h"
Kevin Qinfc02e3c2014-09-29 11:15:00 +000031#include "llvm/IR/Metadata.h"
Andrew Trickd04d15292011-12-09 06:19:40 +000032#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
38using namespace llvm;
39
Chandler Carruth964daaa2014-04-22 02:55:47 +000040#define DEBUG_TYPE "loop-unroll"
41
Jakub Staszak1b1d5232011-12-18 21:52:30 +000042STATISTIC(NumRuntimeUnrolled,
Andrew Trickd04d15292011-12-09 06:19:40 +000043 "Number of loops unrolled with run-time trip counts");
44
45/// Connect the unrolling prolog code to the original loop.
46/// The unrolling prolog code contains code to execute the
47/// 'extra' iterations if the run-time trip count modulo the
48/// unroll count is non-zero.
49///
50/// This function performs the following:
51/// - Create PHI nodes at prolog end block to combine values
52/// that exit the prolog code and jump around the prolog.
53/// - Add a PHI operand to a PHI node at the loop exit block
54/// for values that exit the prolog and go around the loop.
55/// - Branch around the original loop if the trip count is less
56/// than the unroll factor.
57///
58static void ConnectProlog(Loop *L, Value *TripCount, unsigned Count,
59 BasicBlock *LastPrologBB, BasicBlock *PrologEnd,
60 BasicBlock *OrigPH, BasicBlock *NewPH,
Kevin Qinfc02e3c2014-09-29 11:15:00 +000061 ValueToValueMapTy &VMap, Pass *P) {
Andrew Trickd04d15292011-12-09 06:19:40 +000062 BasicBlock *Latch = L->getLoopLatch();
Craig Toppere73658d2014-04-28 04:05:08 +000063 assert(Latch && "Loop must have a latch");
Andrew Trickd04d15292011-12-09 06:19:40 +000064
65 // Create a PHI node for each outgoing value from the original loop
66 // (which means it is an outgoing value from the prolog code too).
67 // The new PHI node is inserted in the prolog end basic block.
68 // The new PHI name is added as an operand of a PHI node in either
69 // the loop header or the loop exit block.
Duncan P. N. Exon Smith6c990152014-07-21 17:06:51 +000070 for (succ_iterator SBI = succ_begin(Latch), SBE = succ_end(Latch);
71 SBI != SBE; ++SBI) {
72 for (BasicBlock::iterator BBI = (*SBI)->begin();
Andrew Trickd04d15292011-12-09 06:19:40 +000073 PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) {
74
75 // Add a new PHI node to the prolog end block and add the
76 // appropriate incoming values.
77 PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName()+".unr",
78 PrologEnd->getTerminator());
79 // Adding a value to the new PHI node from the original loop preheader.
80 // This is the value that skips all the prolog code.
81 if (L->contains(PN)) {
82 NewPN->addIncoming(PN->getIncomingValueForBlock(NewPH), OrigPH);
83 } else {
84 NewPN->addIncoming(Constant::getNullValue(PN->getType()), OrigPH);
85 }
Jakub Staszak1b1d5232011-12-18 21:52:30 +000086
87 Value *V = PN->getIncomingValueForBlock(Latch);
Andrew Trickd04d15292011-12-09 06:19:40 +000088 if (Instruction *I = dyn_cast<Instruction>(V)) {
89 if (L->contains(I)) {
Kevin Qinfc02e3c2014-09-29 11:15:00 +000090 V = VMap[I];
Andrew Trickd04d15292011-12-09 06:19:40 +000091 }
92 }
93 // Adding a value to the new PHI node from the last prolog block
94 // that was created.
95 NewPN->addIncoming(V, LastPrologBB);
96
97 // Update the existing PHI node operand with the value from the
98 // new PHI node. How this is done depends on if the existing
99 // PHI node is in the original loop block, or the exit block.
100 if (L->contains(PN)) {
101 PN->setIncomingValue(PN->getBasicBlockIndex(NewPH), NewPN);
102 } else {
103 PN->addIncoming(NewPN, PrologEnd);
104 }
105 }
106 }
107
108 // Create a branch around the orignal loop, which is taken if the
109 // trip count is less than the unroll factor.
110 Instruction *InsertPt = PrologEnd->getTerminator();
111 Instruction *BrLoopExit =
112 new ICmpInst(InsertPt, ICmpInst::ICMP_ULT, TripCount,
113 ConstantInt::get(TripCount->getType(), Count));
114 BasicBlock *Exit = L->getUniqueExitBlock();
Craig Toppere73658d2014-04-28 04:05:08 +0000115 assert(Exit && "Loop must have a single exit block only");
Andrew Trickd04d15292011-12-09 06:19:40 +0000116 // Split the exit to maintain loop canonicalization guarantees
117 SmallVector<BasicBlock*, 4> Preds(pred_begin(Exit), pred_end(Exit));
118 if (!Exit->isLandingPad()) {
Jakub Staszakf5b32e52011-12-09 21:19:53 +0000119 SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", P);
Andrew Trickd04d15292011-12-09 06:19:40 +0000120 } else {
121 SmallVector<BasicBlock*, 2> NewBBs;
122 SplitLandingPadPredecessors(Exit, Preds, ".unr1-lcssa", ".unr2-lcssa",
123 P, NewBBs);
124 }
125 // Add the branch to the exit block (around the unrolled loop)
126 BranchInst::Create(Exit, NewPH, BrLoopExit, InsertPt);
127 InsertPt->eraseFromParent();
128}
129
130/// Create a clone of the blocks in a loop and connect them together.
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000131/// If UnrollProlog is true, loop structure will not be cloned, otherwise a new
132/// loop will be created including all cloned blocks, and the iterator of it
133/// switches to count NewIter down to 0.
Andrew Trickd04d15292011-12-09 06:19:40 +0000134///
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000135static void CloneLoopBlocks(Loop *L, Value *NewIter, const bool UnrollProlog,
136 BasicBlock *InsertTop, BasicBlock *InsertBot,
Andrew Trickd04d15292011-12-09 06:19:40 +0000137 std::vector<BasicBlock *> &NewBlocks,
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000138 LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,
Andrew Trickd04d15292011-12-09 06:19:40 +0000139 LoopInfo *LI) {
Andrew Trickd04d15292011-12-09 06:19:40 +0000140 BasicBlock *Preheader = L->getLoopPreheader();
141 BasicBlock *Header = L->getHeader();
142 BasicBlock *Latch = L->getLoopLatch();
143 Function *F = Header->getParent();
144 LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
145 LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000146 Loop *NewLoop = 0;
147 Loop *ParentLoop = L->getParentLoop();
148 if (!UnrollProlog) {
149 NewLoop = new Loop();
150 if (ParentLoop)
151 ParentLoop->addChildLoop(NewLoop);
152 else
153 LI->addTopLevelLoop(NewLoop);
154 }
155
Andrew Trickd04d15292011-12-09 06:19:40 +0000156 // For each block in the original loop, create a new copy,
157 // and update the value map with the newly created values.
158 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000159 BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".prol", F);
Andrew Trickd04d15292011-12-09 06:19:40 +0000160 NewBlocks.push_back(NewBB);
161
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000162 if (NewLoop)
Chandler Carruth691addc2015-01-18 01:25:51 +0000163 NewLoop->addBasicBlockToLoop(NewBB, *LI);
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000164 else if (ParentLoop)
Chandler Carruth691addc2015-01-18 01:25:51 +0000165 ParentLoop->addBasicBlockToLoop(NewBB, *LI);
Andrew Trickd04d15292011-12-09 06:19:40 +0000166
167 VMap[*BB] = NewBB;
168 if (Header == *BB) {
169 // For the first block, add a CFG connection to this newly
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000170 // created block.
Andrew Trickd04d15292011-12-09 06:19:40 +0000171 InsertTop->getTerminator()->setSuccessor(0, NewBB);
172
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000173 }
174 if (Latch == *BB) {
175 // For the last block, if UnrollProlog is true, create a direct jump to
176 // InsertBot. If not, create a loop back to cloned head.
177 VMap.erase((*BB)->getTerminator());
178 BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
179 BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
180 if (UnrollProlog) {
181 LatchBR->eraseFromParent();
182 BranchInst::Create(InsertBot, NewBB);
183 } else {
184 PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2, "prol.iter",
185 FirstLoopBB->getFirstNonPHI());
186 IRBuilder<> Builder(LatchBR);
187 Value *IdxSub =
188 Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
189 NewIdx->getName() + ".sub");
190 Value *IdxCmp =
191 Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
192 BranchInst::Create(FirstLoopBB, InsertBot, IdxCmp, NewBB);
193 NewIdx->addIncoming(NewIter, InsertTop);
194 NewIdx->addIncoming(IdxSub, NewBB);
195 LatchBR->eraseFromParent();
196 }
197 }
198 }
199
200 // Change the incoming values to the ones defined in the preheader or
201 // cloned loop.
202 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
203 PHINode *NewPHI = cast<PHINode>(VMap[I]);
204 if (UnrollProlog) {
205 VMap[I] = NewPHI->getIncomingValueForBlock(Preheader);
206 cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
207 } else {
208 unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
209 NewPHI->setIncomingBlock(idx, InsertTop);
210 BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
211 idx = NewPHI->getBasicBlockIndex(Latch);
212 Value *InVal = NewPHI->getIncomingValue(idx);
213 NewPHI->setIncomingBlock(idx, NewLatch);
214 if (VMap[InVal])
215 NewPHI->setIncomingValue(idx, VMap[InVal]);
216 }
217 }
218 if (NewLoop) {
219 // Add unroll disable metadata to disable future unrolling for this loop.
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000220 SmallVector<Metadata *, 4> MDs;
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000221 // Reserve first location for self reference to the LoopID metadata node.
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000222 MDs.push_back(nullptr);
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000223 MDNode *LoopID = NewLoop->getLoopID();
224 if (LoopID) {
225 // First remove any existing loop unrolling metadata.
226 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
227 bool IsUnrollMetadata = false;
228 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
229 if (MD) {
230 const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
231 IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
Andrew Trickd04d15292011-12-09 06:19:40 +0000232 }
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000233 if (!IsUnrollMetadata)
234 MDs.push_back(LoopID->getOperand(i));
Andrew Trickd04d15292011-12-09 06:19:40 +0000235 }
236 }
237
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000238 LLVMContext &Context = NewLoop->getHeader()->getContext();
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000239 SmallVector<Metadata *, 1> DisableOperands;
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000240 DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
241 MDNode *DisableNode = MDNode::get(Context, DisableOperands);
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000242 MDs.push_back(DisableNode);
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000243
Duncan P. N. Exon Smith5bf8fef2014-12-09 18:38:53 +0000244 MDNode *NewLoopID = MDNode::get(Context, MDs);
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000245 // Set operand 0 to refer to the loop id itself.
246 NewLoopID->replaceOperandWith(0, NewLoopID);
247 NewLoop->setLoopID(NewLoopID);
Andrew Trickd04d15292011-12-09 06:19:40 +0000248 }
249}
250
251/// Insert code in the prolog code when unrolling a loop with a
252/// run-time trip-count.
253///
254/// This method assumes that the loop unroll factor is total number
255/// of loop bodes in the loop after unrolling. (Some folks refer
256/// to the unroll factor as the number of *extra* copies added).
257/// We assume also that the loop unroll factor is a power-of-two. So, after
258/// unrolling the loop, the number of loop bodies executed is 2,
Jakub Staszak1b1d5232011-12-18 21:52:30 +0000259/// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
Andrew Trickd04d15292011-12-09 06:19:40 +0000260/// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
261/// the switch instruction is generated.
262///
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000263/// extraiters = tripcount % loopfactor
264/// if (extraiters == 0) jump Loop:
265/// else jump Prol
266/// Prol: LoopBody;
267/// extraiters -= 1 // Omitted if unroll factor is 2.
268/// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
269/// if (tripcount < loopfactor) jump End
270/// Loop:
271/// ...
272/// End:
Andrew Trickd04d15292011-12-09 06:19:40 +0000273///
274bool llvm::UnrollRuntimeLoopProlog(Loop *L, unsigned Count, LoopInfo *LI,
275 LPPassManager *LPM) {
276 // for now, only unroll loops that contain a single exit
Jakub Staszak1b1d5232011-12-18 21:52:30 +0000277 if (!L->getExitingBlock())
Andrew Trickd04d15292011-12-09 06:19:40 +0000278 return false;
279
280 // Make sure the loop is in canonical form, and there is a single
281 // exit block only.
Craig Topperf40110f2014-04-25 05:29:35 +0000282 if (!L->isLoopSimplifyForm() || !L->getUniqueExitBlock())
Andrew Trickd04d15292011-12-09 06:19:40 +0000283 return false;
284
285 // Use Scalar Evolution to compute the trip count. This allows more
286 // loops to be unrolled than relying on induction var simplification
Andrew Trickd29cd732012-05-08 02:52:09 +0000287 if (!LPM)
288 return false;
Andrew Trickd04d15292011-12-09 06:19:40 +0000289 ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>();
Craig Topperf40110f2014-04-25 05:29:35 +0000290 if (!SE)
Andrew Trickd04d15292011-12-09 06:19:40 +0000291 return false;
292
293 // Only unroll loops with a computable trip count and the trip count needs
294 // to be an int value (allowing a pointer type is a TODO item)
295 const SCEV *BECount = SE->getBackedgeTakenCount(L);
296 if (isa<SCEVCouldNotCompute>(BECount) || !BECount->getType()->isIntegerTy())
297 return false;
298
Michael Zolotukhin0dcae712014-11-20 20:19:55 +0000299 // If BECount is INT_MAX, we can't compute trip-count without overflow.
300 if (BECount->isAllOnesValue())
301 return false;
302
Andrew Trickd04d15292011-12-09 06:19:40 +0000303 // Add 1 since the backedge count doesn't include the first loop iteration
Jakub Staszak1b1d5232011-12-18 21:52:30 +0000304 const SCEV *TripCountSC =
Andrew Trickd04d15292011-12-09 06:19:40 +0000305 SE->getAddExpr(BECount, SE->getConstant(BECount->getType(), 1));
306 if (isa<SCEVCouldNotCompute>(TripCountSC))
307 return false;
308
309 // We only handle cases when the unroll factor is a power of 2.
310 // Count is the loop unroll factor, the number of extra copies added + 1.
311 if ((Count & (Count-1)) != 0)
312 return false;
313
314 // If this loop is nested, then the loop unroller changes the code in
315 // parent loop, so the Scalar Evolution pass needs to be run again
316 if (Loop *ParentLoop = L->getParentLoop())
317 SE->forgetLoop(ParentLoop);
318
319 BasicBlock *PH = L->getLoopPreheader();
320 BasicBlock *Header = L->getHeader();
321 BasicBlock *Latch = L->getLoopLatch();
322 // It helps to splits the original preheader twice, one for the end of the
323 // prolog code and one for a new loop preheader
324 BasicBlock *PEnd = SplitEdge(PH, Header, LPM->getAsPass());
325 BasicBlock *NewPH = SplitBlock(PEnd, PEnd->getTerminator(), LPM->getAsPass());
326 BranchInst *PreHeaderBR = cast<BranchInst>(PH->getTerminator());
327
328 // Compute the number of extra iterations required, which is:
329 // extra iterations = run-time trip count % (loop unroll factor + 1)
330 SCEVExpander Expander(*SE, "loop-unroll");
331 Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
332 PreHeaderBR);
Andrew Trickd04d15292011-12-09 06:19:40 +0000333
Benjamin Kramer0bf086f2014-06-21 13:46:25 +0000334 IRBuilder<> B(PreHeaderBR);
335 Value *ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
336
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000337 // Check if for no extra iterations, then jump to cloned/unrolled loop.
338 // We have to check that the trip count computation didn't overflow when
339 // adding one to the backedge taken count.
Benjamin Kramer0bf086f2014-06-21 13:46:25 +0000340 Value *LCmp = B.CreateIsNotNull(ModVal, "lcmp.mod");
341 Value *OverflowCheck = B.CreateIsNull(TripCount, "lcmp.overflow");
342 Value *BranchVal = B.CreateOr(OverflowCheck, LCmp, "lcmp.or");
343
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000344 // Branch to either the extra iterations or the cloned/unrolled loop
Andrew Trickd04d15292011-12-09 06:19:40 +0000345 // We will fix up the true branch label when adding loop body copies
346 BranchInst::Create(PEnd, PEnd, BranchVal, PreHeaderBR);
Jakub Staszak1b1d5232011-12-18 21:52:30 +0000347 assert(PreHeaderBR->isUnconditional() &&
348 PreHeaderBR->getSuccessor(0) == PEnd &&
Andrew Trickd04d15292011-12-09 06:19:40 +0000349 "CFG edges in Preheader are not correct");
350 PreHeaderBR->eraseFromParent();
Andrew Trickd04d15292011-12-09 06:19:40 +0000351 Function *F = Header->getParent();
Andrew Trickd04d15292011-12-09 06:19:40 +0000352 // Get an ordered list of blocks in the loop to help with the ordering of the
353 // cloned blocks in the prolog code
354 LoopBlocksDFS LoopBlocks(L);
355 LoopBlocks.perform(LI);
356
357 //
358 // For each extra loop iteration, create a copy of the loop's basic blocks
359 // and generate a condition that branches to the copy depending on the
360 // number of 'left over' iterations.
361 //
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000362 std::vector<BasicBlock *> NewBlocks;
363 ValueToValueMapTy VMap;
Andrew Trickd04d15292011-12-09 06:19:40 +0000364
Michael Zolotukhin0dcae712014-11-20 20:19:55 +0000365 // If unroll count is 2 and we can't overflow in tripcount computation (which
366 // is BECount + 1), then we don't need a loop for prologue, and we can unroll
367 // it. We can be sure that we don't overflow only if tripcount is a constant.
368 bool UnrollPrologue = (Count == 2 && isa<ConstantInt>(TripCount));
369
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000370 // Clone all the basic blocks in the loop. If Count is 2, we don't clone
371 // the loop, otherwise we create a cloned loop to execute the extra
372 // iterations. This function adds the appropriate CFG connections.
Michael Zolotukhin0dcae712014-11-20 20:19:55 +0000373 CloneLoopBlocks(L, ModVal, UnrollPrologue, PH, PEnd, NewBlocks, LoopBlocks,
374 VMap, LI);
Andrew Trickd04d15292011-12-09 06:19:40 +0000375
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000376 // Insert the cloned blocks into function just before the original loop
377 F->getBasicBlockList().splice(PEnd, F->getBasicBlockList(), NewBlocks[0],
378 F->end());
Andrew Trickd04d15292011-12-09 06:19:40 +0000379
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000380 // Rewrite the cloned instruction operands to use the values
381 // created when the clone is created.
382 for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) {
383 for (BasicBlock::iterator I = NewBlocks[i]->begin(),
384 E = NewBlocks[i]->end();
385 I != E; ++I) {
386 RemapInstruction(I, VMap,
387 RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
Andrew Trickd04d15292011-12-09 06:19:40 +0000388 }
389 }
390
391 // Connect the prolog code to the original loop and update the
392 // PHI functions.
Kevin Qinfc02e3c2014-09-29 11:15:00 +0000393 BasicBlock *LastLoopBB = cast<BasicBlock>(VMap[Latch]);
394 ConnectProlog(L, TripCount, Count, LastLoopBB, PEnd, PH, NewPH, VMap,
Andrew Trickd04d15292011-12-09 06:19:40 +0000395 LPM->getAsPass());
396 NumRuntimeUnrolled++;
397 return true;
398}