Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- UnrollLoopRuntime.cpp - Runtime Loop unrolling utilities ----------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements some loop unrolling utilities for loops with run-time
10
// trip counts.  See LoopUnroll.cpp for unrolling loops with compile-time
11
// trip counts.
12
//
13
// The functions in this file are used to generate extra code when the
14
// run-time trip count modulo the unroll factor is not 0.  When this is the
15
// case, we need to generate code to execute these 'left over' iterations.
16
//
17
// The current strategy generates an if-then-else sequence prior to the
18
// unrolled loop to execute the 'left over' iterations before or after the
19
// unrolled loop.
20
//
21
//===----------------------------------------------------------------------===//
22
23
#include "llvm/ADT/SmallPtrSet.h"
24
#include "llvm/ADT/Statistic.h"
25
#include "llvm/Analysis/AliasAnalysis.h"
26
#include "llvm/Analysis/LoopIterator.h"
27
#include "llvm/Analysis/ScalarEvolution.h"
28
#include "llvm/Analysis/ScalarEvolutionExpander.h"
29
#include "llvm/IR/BasicBlock.h"
30
#include "llvm/IR/Dominators.h"
31
#include "llvm/IR/Metadata.h"
32
#include "llvm/IR/Module.h"
33
#include "llvm/Support/Debug.h"
34
#include "llvm/Support/raw_ostream.h"
35
#include "llvm/Transforms/Utils.h"
36
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
37
#include "llvm/Transforms/Utils/Cloning.h"
38
#include "llvm/Transforms/Utils/LoopUtils.h"
39
#include "llvm/Transforms/Utils/UnrollLoop.h"
40
#include <algorithm>
41
42
using namespace llvm;
43
44
#define DEBUG_TYPE "loop-unroll"
45
46
STATISTIC(NumRuntimeUnrolled,
47
          "Number of loops unrolled with run-time trip counts");
48
static cl::opt<bool> UnrollRuntimeMultiExit(
49
    "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,
50
    cl::desc("Allow runtime unrolling for loops with multiple exits, when "
51
             "epilog is generated"));
52
53
/// Connect the unrolling prolog code to the original loop.
54
/// The unrolling prolog code contains code to execute the
55
/// 'extra' iterations if the run-time trip count modulo the
56
/// unroll count is non-zero.
57
///
58
/// This function performs the following:
59
/// - Create PHI nodes at prolog end block to combine values
60
///   that exit the prolog code and jump around the prolog.
61
/// - Add a PHI operand to a PHI node at the loop exit block
62
///   for values that exit the prolog and go around the loop.
63
/// - Branch around the original loop if the trip count is less
64
///   than the unroll factor.
65
///
66
static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
67
                          BasicBlock *PrologExit,
68
                          BasicBlock *OriginalLoopLatchExit,
69
                          BasicBlock *PreHeader, BasicBlock *NewPreHeader,
70
                          ValueToValueMapTy &VMap, DominatorTree *DT,
71
486
                          LoopInfo *LI, bool PreserveLCSSA) {
72
486
  // Loop structure should be the following:
73
486
  // Preheader
74
486
  //  PrologHeader
75
486
  //  ...
76
486
  //  PrologLatch
77
486
  //  PrologExit
78
486
  //   NewPreheader
79
486
  //    Header
80
486
  //    ...
81
486
  //    Latch
82
486
  //      LatchExit
83
486
  BasicBlock *Latch = L->getLoopLatch();
84
486
  assert(Latch && "Loop must have a latch");
85
486
  BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
86
486
87
486
  // Create a PHI node for each outgoing value from the original loop
88
486
  // (which means it is an outgoing value from the prolog code too).
89
486
  // The new PHI node is inserted in the prolog end basic block.
90
486
  // The new PHI node value is added as an operand of a PHI node in either
91
486
  // the loop header or the loop exit block.
92
972
  for (BasicBlock *Succ : successors(Latch)) {
93
981
    for (PHINode &PN : Succ->phis()) {
94
981
      // Add a new PHI node to the prolog end block and add the
95
981
      // appropriate incoming values.
96
981
      // TODO: This code assumes that the PrologExit (or the LatchExit block for
97
981
      // prolog loop) contains only one predecessor from the loop, i.e. the
98
981
      // PrologLatch. When supporting multiple-exiting block loops, we can have
99
981
      // two or more blocks that have the LatchExit as the target in the
100
981
      // original loop.
101
981
      PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
102
981
                                       PrologExit->getFirstNonPHI());
103
981
      // Adding a value to the new PHI node from the original loop preheader.
104
981
      // This is the value that skips all the prolog code.
105
981
      if (L->contains(&PN)) {
106
770
        // Succ is loop header.
107
770
        NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),
108
770
                           PreHeader);
109
770
      } else {
110
211
        // Succ is LatchExit.
111
211
        NewPN->addIncoming(UndefValue::get(PN.getType()), PreHeader);
112
211
      }
113
981
114
981
      Value *V = PN.getIncomingValueForBlock(Latch);
115
981
      if (Instruction *I = dyn_cast<Instruction>(V)) {
116
981
        if (L->contains(I)) {
117
981
          V = VMap.lookup(I);
118
981
        }
119
981
      }
120
981
      // Adding a value to the new PHI node from the last prolog block
121
981
      // that was created.
122
981
      NewPN->addIncoming(V, PrologLatch);
123
981
124
981
      // Update the existing PHI node operand with the value from the
125
981
      // new PHI node.  How this is done depends on if the existing
126
981
      // PHI node is in the original loop block, or the exit block.
127
981
      if (L->contains(&PN))
128
770
        PN.setIncomingValueForBlock(NewPreHeader, NewPN);
129
211
      else
130
211
        PN.addIncoming(NewPN, PrologExit);
131
981
    }
132
972
  }
133
486
134
486
  // Make sure that created prolog loop is in simplified form
135
486
  SmallVector<BasicBlock *, 4> PrologExitPreds;
136
486
  Loop *PrologLoop = LI->getLoopFor(PrologLatch);
137
486
  if (PrologLoop) {
138
450
    for (BasicBlock *PredBB : predecessors(PrologExit))
139
900
      if (PrologLoop->contains(PredBB))
140
460
        PrologExitPreds.push_back(PredBB);
141
450
142
450
    SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
143
450
                           nullptr, PreserveLCSSA);
144
450
  }
145
486
146
486
  // Create a branch around the original loop, which is taken if there are no
147
486
  // iterations remaining to be executed after running the prologue.
148
486
  Instruction *InsertPt = PrologExit->getTerminator();
149
486
  IRBuilder<> B(InsertPt);
150
486
151
486
  assert(Count != 0 && "nonsensical Count!");
152
486
153
486
  // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
154
486
  // This means %xtraiter is (BECount + 1) and all of the iterations of this
155
486
  // loop were executed by the prologue.  Note that if BECount <u (Count - 1)
156
486
  // then (BECount + 1) cannot unsigned-overflow.
157
486
  Value *BrLoopExit =
158
486
      B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));
159
486
  // Split the exit to maintain loop canonicalization guarantees
160
486
  SmallVector<BasicBlock *, 4> Preds(predecessors(OriginalLoopLatchExit));
161
486
  SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI,
162
486
                         nullptr, PreserveLCSSA);
163
486
  // Add the branch to the exit block (around the unrolled loop)
164
486
  B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader);
165
486
  InsertPt->eraseFromParent();
166
486
  if (DT)
167
486
    DT->changeImmediateDominator(OriginalLoopLatchExit, PrologExit);
168
486
}
169
170
/// Connect the unrolling epilog code to the original loop.
171
/// The unrolling epilog code contains code to execute the
172
/// 'extra' iterations if the run-time trip count modulo the
173
/// unroll count is non-zero.
174
///
175
/// This function performs the following:
176
/// - Update PHI nodes at the unrolling loop exit and epilog loop exit
177
/// - Create PHI nodes at the unrolling loop exit to combine
178
///   values that exit the unrolling loop code and jump around it.
179
/// - Update PHI operands in the epilog loop by the new PHI nodes
180
/// - Branch around the epilog loop if extra iters (ModVal) is zero.
181
///
182
static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
183
                          BasicBlock *Exit, BasicBlock *PreHeader,
184
                          BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
185
                          ValueToValueMapTy &VMap, DominatorTree *DT,
186
984
                          LoopInfo *LI, bool PreserveLCSSA)  {
187
984
  BasicBlock *Latch = L->getLoopLatch();
188
984
  assert(Latch && "Loop must have a latch");
189
984
  BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);
190
984
191
984
  // Loop structure should be the following:
192
984
  //
193
984
  // PreHeader
194
984
  // NewPreHeader
195
984
  //   Header
196
984
  //   ...
197
984
  //   Latch
198
984
  // NewExit (PN)
199
984
  // EpilogPreHeader
200
984
  //   EpilogHeader
201
984
  //   ...
202
984
  //   EpilogLatch
203
984
  // Exit (EpilogPN)
204
984
205
984
  // Update PHI nodes at NewExit and Exit.
206
984
  for (PHINode &PN : NewExit->phis()) {
207
380
    // PN should be used in another PHI located in Exit block as
208
380
    // Exit was split by SplitBlockPredecessors into Exit and NewExit
209
380
    // Basicaly it should look like:
210
380
    // NewExit:
211
380
    //   PN = PHI [I, Latch]
212
380
    // ...
213
380
    // Exit:
214
380
    //   EpilogPN = PHI [PN, EpilogPreHeader]
215
380
    //
216
380
    // There is EpilogPreHeader incoming block instead of NewExit as
217
380
    // NewExit was spilt 1 more time to get EpilogPreHeader.
218
380
    assert(PN.hasOneUse() && "The phi should have 1 use");
219
380
    PHINode *EpilogPN = cast<PHINode>(PN.use_begin()->getUser());
220
380
    assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");
221
380
222
380
    // Add incoming PreHeader from branch around the Loop
223
380
    PN.addIncoming(UndefValue::get(PN.getType()), PreHeader);
224
380
225
380
    Value *V = PN.getIncomingValueForBlock(Latch);
226
380
    Instruction *I = dyn_cast<Instruction>(V);
227
380
    if (I && 
L->contains(I)377
)
228
377
      // If value comes from an instruction in the loop add VMap value.
229
377
      V = VMap.lookup(I);
230
380
    // For the instruction out of the loop, constant or undefined value
231
380
    // insert value itself.
232
380
    EpilogPN->addIncoming(V, EpilogLatch);
233
380
234
380
    assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&
235
380
          "EpilogPN should have EpilogPreHeader incoming block");
236
380
    // Change EpilogPreHeader incoming block to NewExit.
237
380
    EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
238
380
                               NewExit);
239
380
    // Now PHIs should look like:
240
380
    // NewExit:
241
380
    //   PN = PHI [I, Latch], [undef, PreHeader]
242
380
    // ...
243
380
    // Exit:
244
380
    //   EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
245
380
  }
246
984
247
984
  // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
248
984
  // Update corresponding PHI nodes in epilog loop.
249
1.96k
  for (BasicBlock *Succ : successors(Latch)) {
250
1.96k
    // Skip this as we already updated phis in exit blocks.
251
1.96k
    if (!L->contains(Succ))
252
984
      continue;
253
1.45k
    
for (PHINode &PN : Succ->phis())984
{
254
1.45k
      // Add new PHI nodes to the loop exit block and update epilog
255
1.45k
      // PHIs with the new PHI values.
256
1.45k
      PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
257
1.45k
                                       NewExit->getFirstNonPHI());
258
1.45k
      // Adding a value to the new PHI node from the unrolling loop preheader.
259
1.45k
      NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);
260
1.45k
      // Adding a value to the new PHI node from the unrolling loop latch.
261
1.45k
      NewPN->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);
262
1.45k
263
1.45k
      // Update the existing PHI node operand with the value from the new PHI
264
1.45k
      // node.  Corresponding instruction in epilog loop should be PHI.
265
1.45k
      PHINode *VPN = cast<PHINode>(VMap[&PN]);
266
1.45k
      VPN->setIncomingValueForBlock(EpilogPreHeader, NewPN);
267
1.45k
    }
268
984
  }
269
984
270
984
  Instruction *InsertPt = NewExit->getTerminator();
271
984
  IRBuilder<> B(InsertPt);
272
984
  Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
273
984
  assert(Exit && "Loop must have a single exit block only");
274
984
  // Split the epilogue exit to maintain loop canonicalization guarantees
275
984
  SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
276
984
  SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI, nullptr,
277
984
                         PreserveLCSSA);
278
984
  // Add the branch to the exit block (around the unrolling loop)
279
984
  B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
280
984
  InsertPt->eraseFromParent();
281
984
  if (DT)
282
984
    DT->changeImmediateDominator(Exit, NewExit);
283
984
284
984
  // Split the main loop exit to maintain canonicalization guarantees.
285
984
  SmallVector<BasicBlock*, 4> NewExitPreds{Latch};
286
984
  SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, nullptr,
287
984
                         PreserveLCSSA);
288
984
}
289
290
/// Create a clone of the blocks in a loop and connect them together.
291
/// If CreateRemainderLoop is false, loop structure will not be cloned,
292
/// otherwise a new loop will be created including all cloned blocks, and the
293
/// iterator of it switches to count NewIter down to 0.
294
/// The cloned blocks should be inserted between InsertTop and InsertBot.
295
/// If loop structure is cloned InsertTop should be new preheader, InsertBot
296
/// new loop exit.
297
/// Return the new cloned loop that is created when CreateRemainderLoop is true.
298
static Loop *
299
CloneLoopBlocks(Loop *L, Value *NewIter, const bool CreateRemainderLoop,
300
                const bool UseEpilogRemainder, const bool UnrollRemainder,
301
                BasicBlock *InsertTop,
302
                BasicBlock *InsertBot, BasicBlock *Preheader,
303
                std::vector<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
304
1.47k
                ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI) {
305
1.47k
  StringRef suffix = UseEpilogRemainder ? 
"epil"984
:
"prol"486
;
306
1.47k
  BasicBlock *Header = L->getHeader();
307
1.47k
  BasicBlock *Latch = L->getLoopLatch();
308
1.47k
  Function *F = Header->getParent();
309
1.47k
  LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
310
1.47k
  LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
311
1.47k
  Loop *ParentLoop = L->getParentLoop();
312
1.47k
  NewLoopsMap NewLoops;
313
1.47k
  NewLoops[ParentLoop] = ParentLoop;
314
1.47k
  if (!CreateRemainderLoop)
315
377
    NewLoops[L] = ParentLoop;
316
1.47k
317
1.47k
  // For each block in the original loop, create a new copy,
318
1.47k
  // and update the value map with the newly created values.
319
3.31k
  for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; 
++BB1.84k
) {
320
1.84k
    BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
321
1.84k
    NewBlocks.push_back(NewBB);
322
1.84k
323
1.84k
    // If we're unrolling the outermost loop, there's no remainder loop,
324
1.84k
    // and this block isn't in a nested loop, then the new block is not
325
1.84k
    // in any loop. Otherwise, add it to loopinfo.
326
1.84k
    if (CreateRemainderLoop || 
LI->getLoopFor(*BB) != L623
||
ParentLoop557
)
327
1.40k
      addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);
328
1.84k
329
1.84k
    VMap[*BB] = NewBB;
330
1.84k
    if (Header == *BB) {
331
1.47k
      // For the first block, add a CFG connection to this newly
332
1.47k
      // created block.
333
1.47k
      InsertTop->getTerminator()->setSuccessor(0, NewBB);
334
1.47k
    }
335
1.84k
336
1.84k
    if (DT) {
337
1.84k
      if (Header == *BB) {
338
1.47k
        // The header is dominated by the preheader.
339
1.47k
        DT->addNewBlock(NewBB, InsertTop);
340
1.47k
      } else {
341
373
        // Copy information from original loop to unrolled loop.
342
373
        BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();
343
373
        DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));
344
373
      }
345
1.84k
    }
346
1.84k
347
1.84k
    if (Latch == *BB) {
348
1.47k
      // For the last block, if CreateRemainderLoop is false, create a direct
349
1.47k
      // jump to InsertBot. If not, create a loop back to cloned head.
350
1.47k
      VMap.erase((*BB)->getTerminator());
351
1.47k
      BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
352
1.47k
      BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
353
1.47k
      IRBuilder<> Builder(LatchBR);
354
1.47k
      if (!CreateRemainderLoop) {
355
377
        Builder.CreateBr(InsertBot);
356
1.09k
      } else {
357
1.09k
        PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
358
1.09k
                                          suffix + ".iter",
359
1.09k
                                          FirstLoopBB->getFirstNonPHI());
360
1.09k
        Value *IdxSub =
361
1.09k
            Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
362
1.09k
                              NewIdx->getName() + ".sub");
363
1.09k
        Value *IdxCmp =
364
1.09k
            Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
365
1.09k
        Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
366
1.09k
        NewIdx->addIncoming(NewIter, InsertTop);
367
1.09k
        NewIdx->addIncoming(IdxSub, NewBB);
368
1.09k
      }
369
1.47k
      LatchBR->eraseFromParent();
370
1.47k
    }
371
1.84k
  }
372
1.47k
373
1.47k
  // Change the incoming values to the ones defined in the preheader or
374
1.47k
  // cloned loop.
375
3.69k
  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); 
++I2.22k
) {
376
2.22k
    PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
377
2.22k
    if (!CreateRemainderLoop) {
378
639
      if (UseEpilogRemainder) {
379
547
        unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
380
547
        NewPHI->setIncomingBlock(idx, InsertTop);
381
547
        NewPHI->removeIncomingValue(Latch, false);
382
547
      } else {
383
92
        VMap[&*I] = NewPHI->getIncomingValueForBlock(Preheader);
384
92
        cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
385
92
      }
386
1.58k
    } else {
387
1.58k
      unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
388
1.58k
      NewPHI->setIncomingBlock(idx, InsertTop);
389
1.58k
      BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
390
1.58k
      idx = NewPHI->getBasicBlockIndex(Latch);
391
1.58k
      Value *InVal = NewPHI->getIncomingValue(idx);
392
1.58k
      NewPHI->setIncomingBlock(idx, NewLatch);
393
1.58k
      if (Value *V = VMap.lookup(InVal))
394
1.58k
        NewPHI->setIncomingValue(idx, V);
395
1.58k
    }
396
2.22k
  }
397
1.47k
  if (CreateRemainderLoop) {
398
1.09k
    Loop *NewLoop = NewLoops[L];
399
1.09k
    MDNode *LoopID = NewLoop->getLoopID();
400
1.09k
    assert(NewLoop && "L should have been cloned");
401
1.09k
402
1.09k
    // Only add loop metadata if the loop is not going to be completely
403
1.09k
    // unrolled.
404
1.09k
    if (UnrollRemainder)
405
20
      return NewLoop;
406
1.07k
407
1.07k
    Optional<MDNode *> NewLoopID = makeFollowupLoopID(
408
1.07k
        LoopID, {LLVMLoopUnrollFollowupAll, LLVMLoopUnrollFollowupRemainder});
409
1.07k
    if (NewLoopID.hasValue()) {
410
0
      NewLoop->setLoopID(NewLoopID.getValue());
411
0
412
0
      // Do not setLoopAlreadyUnrolled if loop attributes have been defined
413
0
      // explicitly.
414
0
      return NewLoop;
415
0
    }
416
1.07k
417
1.07k
    // Add unroll disable metadata to disable future unrolling for this loop.
418
1.07k
    NewLoop->setLoopAlreadyUnrolled();
419
1.07k
    return NewLoop;
420
1.07k
  }
421
377
  else
422
377
    return nullptr;
423
1.47k
}
424
425
/// Returns true if we can safely unroll a multi-exit/exiting loop. OtherExits
426
/// is populated with all the loop exit blocks other than the LatchExit block.
427
static bool canSafelyUnrollMultiExitLoop(Loop *L, BasicBlock *LatchExit,
428
                                         bool PreserveLCSSA,
429
3.82k
                                         bool UseEpilogRemainder) {
430
3.82k
431
3.82k
  // We currently have some correctness constrains in unrolling a multi-exit
432
3.82k
  // loop. Check for these below.
433
3.82k
434
3.82k
  // We rely on LCSSA form being preserved when the exit blocks are transformed.
435
3.82k
  if (!PreserveLCSSA)
436
0
    return false;
437
3.82k
438
3.82k
  // TODO: Support multiple exiting blocks jumping to the `LatchExit` when
439
3.82k
  // UnrollRuntimeMultiExit is true. This will need updating the logic in
440
3.82k
  // connectEpilog/connectProlog.
441
3.82k
  if (!LatchExit->getSinglePredecessor()) {
442
417
    LLVM_DEBUG(
443
417
        dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
444
417
                  "predecessor.\n");
445
417
    return false;
446
417
  }
447
3.40k
  // FIXME: We bail out of multi-exit unrolling when epilog loop is generated
448
3.40k
  // and L is an inner loop. This is because in presence of multiple exits, the
449
3.40k
  // outer loop is incorrect: we do not add the EpilogPreheader and exit to the
450
3.40k
  // outer loop. This is automatically handled in the prolog case, so we do not
451
3.40k
  // have that bug in prolog generation.
452
3.40k
  if (UseEpilogRemainder && 
L->getParentLoop()1.84k
)
453
342
    return false;
454
3.06k
455
3.06k
  // All constraints have been satisfied.
456
3.06k
  return true;
457
3.06k
}
458
459
/// Returns true if we can profitably unroll the multi-exit loop L. Currently,
460
/// we return true only if UnrollRuntimeMultiExit is set to true.
461
static bool canProfitablyUnrollMultiExitLoop(
462
    Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
463
3.06k
    bool PreserveLCSSA, bool UseEpilogRemainder) {
464
3.06k
465
#if !defined(NDEBUG)
466
  assert(canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA,
467
                                      UseEpilogRemainder) &&
468
         "Should be safe to unroll before checking profitability!");
469
#endif
470
471
3.06k
  // Priority goes to UnrollRuntimeMultiExit if it's supplied.
472
3.06k
  if (UnrollRuntimeMultiExit.getNumOccurrences())
473
2
    return UnrollRuntimeMultiExit;
474
3.06k
475
3.06k
  // The main pain point with multi-exit loop unrolling is that once unrolled,
476
3.06k
  // we will not be able to merge all blocks into a straight line code.
477
3.06k
  // There are branches within the unrolled loop that go to the OtherExits.
478
3.06k
  // The second point is the increase in code size, but this is true
479
3.06k
  // irrespective of multiple exits.
480
3.06k
481
3.06k
  // Note: Both the heuristics below are coarse grained. We are essentially
482
3.06k
  // enabling unrolling of loops that have a single side exit other than the
483
3.06k
  // normal LatchExit (i.e. exiting into a deoptimize block).
484
3.06k
  // The heuristics considered are:
485
3.06k
  // 1. low number of branches in the unrolled version.
486
3.06k
  // 2. high predictability of these extra branches.
487
3.06k
  // We avoid unrolling loops that have more than two exiting blocks. This
488
3.06k
  // limits the total number of branches in the unrolled loop to be atmost
489
3.06k
  // the unroll factor (since one of the exiting blocks is the latch block).
490
3.06k
  SmallVector<BasicBlock*, 4> ExitingBlocks;
491
3.06k
  L->getExitingBlocks(ExitingBlocks);
492
3.06k
  if (ExitingBlocks.size() > 2)
493
51
    return false;
494
3.01k
495
3.01k
  // The second heuristic is that L has one exit other than the latchexit and
496
3.01k
  // that exit is a deoptimize block. We know that deoptimize blocks are rarely
497
3.01k
  // taken, which also implies the branch leading to the deoptimize block is
498
3.01k
  // highly predictable.
499
3.01k
  return (OtherExits.size() == 1 &&
500
3.01k
          
OtherExits[0]->getTerminatingDeoptimizeCall()656
);
501
3.01k
  // TODO: These can be fine-tuned further to consider code size or deopt states
502
3.01k
  // that are captured by the deoptimize exit block.
503
3.01k
  // Also, we can extend this to support more cases, if we actually
504
3.01k
  // know of kinds of multiexit loops that would benefit from unrolling.
505
3.01k
}
506
507
/// Insert code in the prolog/epilog code when unrolling a loop with a
508
/// run-time trip-count.
509
///
510
/// This method assumes that the loop unroll factor is total number
511
/// of loop bodies in the loop after unrolling. (Some folks refer
512
/// to the unroll factor as the number of *extra* copies added).
513
/// We assume also that the loop unroll factor is a power-of-two. So, after
514
/// unrolling the loop, the number of loop bodies executed is 2,
515
/// 4, 8, etc.  Note - LLVM converts the if-then-sequence to a switch
516
/// instruction in SimplifyCFG.cpp.  Then, the backend decides how code for
517
/// the switch instruction is generated.
518
///
519
/// ***Prolog case***
520
///        extraiters = tripcount % loopfactor
521
///        if (extraiters == 0) jump Loop:
522
///        else jump Prol:
523
/// Prol:  LoopBody;
524
///        extraiters -= 1                 // Omitted if unroll factor is 2.
525
///        if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
526
///        if (tripcount < loopfactor) jump End:
527
/// Loop:
528
/// ...
529
/// End:
530
///
531
/// ***Epilog case***
532
///        extraiters = tripcount % loopfactor
533
///        if (tripcount < loopfactor) jump LoopExit:
534
///        unroll_iters = tripcount - extraiters
535
/// Loop:  LoopBody; (executes unroll_iter times);
536
///        unroll_iter -= 1
537
///        if (unroll_iter != 0) jump Loop:
538
/// LoopExit:
539
///        if (extraiters == 0) jump EpilExit:
540
/// Epil:  LoopBody; (executes extraiters times)
541
///        extraiters -= 1                 // Omitted if unroll factor is 2.
542
///        if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
543
/// EpilExit:
544
545
bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
546
                                      bool AllowExpensiveTripCount,
547
                                      bool UseEpilogRemainder,
548
                                      bool UnrollRemainder, bool ForgetAllSCEV,
549
                                      LoopInfo *LI, ScalarEvolution *SE,
550
                                      DominatorTree *DT, AssumptionCache *AC,
551
3.82k
                                      bool PreserveLCSSA, Loop **ResultLoop) {
552
3.82k
  LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
553
3.82k
  LLVM_DEBUG(L->dump());
554
3.82k
  LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
555
3.82k
                                : dbgs() << "Using prolog remainder.\n");
556
3.82k
557
3.82k
  // Make sure the loop is in canonical form.
558
3.82k
  if (!L->isLoopSimplifyForm()) {
559
0
    LLVM_DEBUG(dbgs() << "Not in simplify form!\n");
560
0
    return false;
561
0
  }
562
3.82k
563
3.82k
  // Guaranteed by LoopSimplifyForm.
564
3.82k
  BasicBlock *Latch = L->getLoopLatch();
565
3.82k
  BasicBlock *Header = L->getHeader();
566
3.82k
567
3.82k
  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
568
3.82k
569
3.82k
  if (!LatchBR || LatchBR->isUnconditional()) {
570
4
    // The loop-rotate pass can be helpful to avoid this in many cases.
571
4
    LLVM_DEBUG(
572
4
        dbgs()
573
4
        << "Loop latch not terminated by a conditional branch.\n");
574
4
    return false;
575
4
  }
576
3.82k
577
3.82k
  unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 
1920
:
02.90k
;
578
3.82k
  BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
579
3.82k
580
3.82k
  if (L->contains(LatchExit)) {
581
0
    // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
582
0
    // targets of the Latch be an exit block out of the loop.
583
0
    LLVM_DEBUG(
584
0
        dbgs()
585
0
        << "One of the loop latch successors must be the exit block.\n");
586
0
    return false;
587
0
  }
588
3.82k
589
3.82k
  // These are exit blocks other than the target of the latch exiting block.
590
3.82k
  SmallVector<BasicBlock *, 4> OtherExits;
591
3.82k
  L->getUniqueNonLatchExitBlocks(OtherExits);
592
3.82k
  bool isMultiExitUnrollingEnabled =
593
3.82k
      canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA,
594
3.82k
                                   UseEpilogRemainder) &&
595
3.82k
      canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
596
3.06k
                                       UseEpilogRemainder);
597
3.82k
  // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
598
3.82k
  if (!isMultiExitUnrollingEnabled &&
599
3.82k
      
(3.82k
!L->getExitingBlock()3.82k
||
OtherExits.size()2.57k
)) {
600
1.24k
    LLVM_DEBUG(
601
1.24k
        dbgs()
602
1.24k
        << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
603
1.24k
           "enabled!\n");
604
1.24k
    return false;
605
1.24k
  }
606
2.57k
  // Use Scalar Evolution to compute the trip count. This allows more loops to
607
2.57k
  // be unrolled than relying on induction var simplification.
608
2.57k
  if (!SE)
609
0
    return false;
610
2.57k
611
2.57k
  // Only unroll loops with a computable trip count, and the trip count needs
612
2.57k
  // to be an int value (allowing a pointer type is a TODO item).
613
2.57k
  // We calculate the backedge count by using getExitCount on the Latch block,
614
2.57k
  // which is proven to be the only exiting block in this loop. This is same as
615
2.57k
  // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
616
2.57k
  // exiting blocks).
617
2.57k
  const SCEV *BECountSC = SE->getExitCount(L, Latch);
618
2.57k
  if (isa<SCEVCouldNotCompute>(BECountSC) ||
619
2.57k
      
!BECountSC->getType()->isIntegerTy()1.81k
) {
620
839
    LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");
621
839
    return false;
622
839
  }
623
1.73k
624
1.73k
  unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
625
1.73k
626
1.73k
  // Add 1 since the backedge count doesn't include the first loop iteration.
627
1.73k
  const SCEV *TripCountSC =
628
1.73k
      SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
629
1.73k
  if (isa<SCEVCouldNotCompute>(TripCountSC)) {
630
0
    LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
631
0
    return false;
632
0
  }
633
1.73k
634
1.73k
  BasicBlock *PreHeader = L->getLoopPreheader();
635
1.73k
  BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
636
1.73k
  const DataLayout &DL = Header->getModule()->getDataLayout();
637
1.73k
  SCEVExpander Expander(*SE, DL, "loop-unroll");
638
1.73k
  if (!AllowExpensiveTripCount &&
639
1.73k
      
Expander.isHighCostExpansion(TripCountSC, L, PreHeaderBR)1.70k
) {
640
265
    LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
641
265
    return false;
642
265
  }
643
1.47k
644
1.47k
  // This constraint lets us deal with an overflowing trip count easily; see the
645
1.47k
  // comment on ModVal below.
646
1.47k
  if (Log2_32(Count) > BEWidth) {
647
2
    LLVM_DEBUG(
648
2
        dbgs()
649
2
        << "Count failed constraint on overflow trip count calculation.\n");
650
2
    return false;
651
2
  }
652
1.47k
653
1.47k
  // Loop structure is the following:
654
1.47k
  //
655
1.47k
  // PreHeader
656
1.47k
  //   Header
657
1.47k
  //   ...
658
1.47k
  //   Latch
659
1.47k
  // LatchExit
660
1.47k
661
1.47k
  BasicBlock *NewPreHeader;
662
1.47k
  BasicBlock *NewExit = nullptr;
663
1.47k
  BasicBlock *PrologExit = nullptr;
664
1.47k
  BasicBlock *EpilogPreHeader = nullptr;
665
1.47k
  BasicBlock *PrologPreHeader = nullptr;
666
1.47k
667
1.47k
  if (UseEpilogRemainder) {
668
984
    // If epilog remainder
669
984
    // Split PreHeader to insert a branch around loop for unrolling.
670
984
    NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
671
984
    NewPreHeader->setName(PreHeader->getName() + ".new");
672
984
    // Split LatchExit to create phi nodes from branch above.
673
984
    SmallVector<BasicBlock*, 4> Preds(predecessors(LatchExit));
674
984
    NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa", DT, LI,
675
984
                                     nullptr, PreserveLCSSA);
676
984
    // NewExit gets its DebugLoc from LatchExit, which is not part of the
677
984
    // original Loop.
678
984
    // Fix this by setting Loop's DebugLoc to NewExit.
679
984
    auto *NewExitTerminator = NewExit->getTerminator();
680
984
    NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
681
984
    // Split NewExit to insert epilog remainder loop.
682
984
    EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);
683
984
    EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
684
984
  } else {
685
486
    // If prolog remainder
686
486
    // Split the original preheader twice to insert prolog remainder loop
687
486
    PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
688
486
    PrologPreHeader->setName(Header->getName() + ".prol.preheader");
689
486
    PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
690
486
                            DT, LI);
691
486
    PrologExit->setName(Header->getName() + ".prol.loopexit");
692
486
    // Split PrologExit to get NewPreHeader.
693
486
    NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
694
486
    NewPreHeader->setName(PreHeader->getName() + ".new");
695
486
  }
696
1.47k
  // Loop structure should be the following:
697
1.47k
  //  Epilog             Prolog
698
1.47k
  //
699
1.47k
  // PreHeader         PreHeader
700
1.47k
  // *NewPreHeader     *PrologPreHeader
701
1.47k
  //   Header          *PrologExit
702
1.47k
  //   ...             *NewPreHeader
703
1.47k
  //   Latch             Header
704
1.47k
  // *NewExit            ...
705
1.47k
  // *EpilogPreHeader    Latch
706
1.47k
  // LatchExit              LatchExit
707
1.47k
708
1.47k
  // Calculate conditions for branch around loop for unrolling
709
1.47k
  // in epilog case and around prolog remainder loop in prolog case.
710
1.47k
  // Compute the number of extra iterations required, which is:
711
1.47k
  //  extra iterations = run-time trip count % loop unroll factor
712
1.47k
  PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
713
1.47k
  Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
714
1.47k
                                            PreHeaderBR);
715
1.47k
  Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
716
1.47k
                                          PreHeaderBR);
717
1.47k
  IRBuilder<> B(PreHeaderBR);
718
1.47k
  Value *ModVal;
719
1.47k
  // Calculate ModVal = (BECount + 1) % Count.
720
1.47k
  // Note that TripCount is BECount + 1.
721
1.47k
  if (isPowerOf2_32(Count)) {
722
1.46k
    // When Count is power of 2 we don't BECount for epilog case, however we'll
723
1.46k
    // need it for a branch around unrolling loop for prolog case.
724
1.46k
    ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
725
1.46k
    //  1. There are no iterations to be run in the prolog/epilog loop.
726
1.46k
    // OR
727
1.46k
    //  2. The addition computing TripCount overflowed.
728
1.46k
    //
729
1.46k
    // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
730
1.46k
    // the number of iterations that remain to be run in the original loop is a
731
1.46k
    // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
732
1.46k
    // explicitly check this above).
733
1.46k
  } else {
734
3
    // As (BECount + 1) can potentially unsigned overflow we count
735
3
    // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
736
3
    Value *ModValTmp = B.CreateURem(BECount,
737
3
                                    ConstantInt::get(BECount->getType(),
738
3
                                                     Count));
739
3
    Value *ModValAdd = B.CreateAdd(ModValTmp,
740
3
                                   ConstantInt::get(ModValTmp->getType(), 1));
741
3
    // At that point (BECount % Count) + 1 could be equal to Count.
742
3
    // To handle this case we need to take mod by Count one more time.
743
3
    ModVal = B.CreateURem(ModValAdd,
744
3
                          ConstantInt::get(BECount->getType(), Count),
745
3
                          "xtraiter");
746
3
  }
747
1.47k
  Value *BranchVal =
748
1.47k
      UseEpilogRemainder ? B.CreateICmpULT(BECount,
749
984
                                           ConstantInt::get(BECount->getType(),
750
984
                                                            Count - 1)) :
751
1.47k
                           
B.CreateIsNotNull(ModVal, "lcmp.mod")486
;
752
1.47k
  BasicBlock *RemainderLoop = UseEpilogRemainder ? 
NewExit984
:
PrologPreHeader486
;
753
1.47k
  BasicBlock *UnrollingLoop = UseEpilogRemainder ? 
NewPreHeader984
:
PrologExit486
;
754
1.47k
  // Branch to either remainder (extra iterations) loop or unrolling loop.
755
1.47k
  B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
756
1.47k
  PreHeaderBR->eraseFromParent();
757
1.47k
  if (DT) {
758
1.47k
    if (UseEpilogRemainder)
759
984
      DT->changeImmediateDominator(NewExit, PreHeader);
760
486
    else
761
486
      DT->changeImmediateDominator(PrologExit, PreHeader);
762
1.47k
  }
763
1.47k
  Function *F = Header->getParent();
764
1.47k
  // Get an ordered list of blocks in the loop to help with the ordering of the
765
1.47k
  // cloned blocks in the prolog/epilog code
766
1.47k
  LoopBlocksDFS LoopBlocks(L);
767
1.47k
  LoopBlocks.perform(LI);
768
1.47k
769
1.47k
  //
770
1.47k
  // For each extra loop iteration, create a copy of the loop's basic blocks
771
1.47k
  // and generate a condition that branches to the copy depending on the
772
1.47k
  // number of 'left over' iterations.
773
1.47k
  //
774
1.47k
  std::vector<BasicBlock *> NewBlocks;
775
1.47k
  ValueToValueMapTy VMap;
776
1.47k
777
1.47k
  // For unroll factor 2 remainder loop will have 1 iterations.
778
1.47k
  // Do not create 1 iteration loop.
779
1.47k
  bool CreateRemainderLoop = (Count != 2);
780
1.47k
781
1.47k
  // Clone all the basic blocks in the loop. If Count is 2, we don't clone
782
1.47k
  // the loop, otherwise we create a cloned loop to execute the extra
783
1.47k
  // iterations. This function adds the appropriate CFG connections.
784
1.47k
  BasicBlock *InsertBot = UseEpilogRemainder ? 
LatchExit984
:
PrologExit486
;
785
1.47k
  BasicBlock *InsertTop = UseEpilogRemainder ? 
EpilogPreHeader984
:
PrologPreHeader486
;
786
1.47k
  Loop *remainderLoop = CloneLoopBlocks(
787
1.47k
      L, ModVal, CreateRemainderLoop, UseEpilogRemainder, UnrollRemainder,
788
1.47k
      InsertTop, InsertBot,
789
1.47k
      NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
790
1.47k
791
1.47k
  // Insert the cloned blocks into the function.
792
1.47k
  F->getBasicBlockList().splice(InsertBot->getIterator(),
793
1.47k
                                F->getBasicBlockList(),
794
1.47k
                                NewBlocks[0]->getIterator(),
795
1.47k
                                F->end());
796
1.47k
797
1.47k
  // Now the loop blocks are cloned and the other exiting blocks from the
798
1.47k
  // remainder are connected to the original Loop's exit blocks. The remaining
799
1.47k
  // work is to update the phi nodes in the original loop, and take in the
800
1.47k
  // values from the cloned region.
801
1.47k
  for (auto *BB : OtherExits) {
802
2
   for (auto &II : *BB) {
803
2
804
2
     // Given we preserve LCSSA form, we know that the values used outside the
805
2
     // loop will be used through these phi nodes at the exit blocks that are
806
2
     // transformed below.
807
2
     if (!isa<PHINode>(II))
808
1
       break;
809
1
     PHINode *Phi = cast<PHINode>(&II);
810
1
     unsigned oldNumOperands = Phi->getNumIncomingValues();
811
1
     // Add the incoming values from the remainder code to the end of the phi
812
1
     // node.
813
2
     for (unsigned i =0; i < oldNumOperands; 
i++1
){
814
1
       Value *newVal = VMap.lookup(Phi->getIncomingValue(i));
815
1
       // newVal can be a constant or derived from values outside the loop, and
816
1
       // hence need not have a VMap value. Also, since lookup already generated
817
1
       // a default "null" VMap entry for this value, we need to populate that
818
1
       // VMap entry correctly, with the mapped entry being itself.
819
1
       if (!newVal) {
820
0
         newVal = Phi->getIncomingValue(i);
821
0
         VMap[Phi->getIncomingValue(i)] = Phi->getIncomingValue(i);
822
0
       }
823
1
       Phi->addIncoming(newVal,
824
1
                           cast<BasicBlock>(VMap[Phi->getIncomingBlock(i)]));
825
1
     }
826
1
   }
827
#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
828
    for (BasicBlock *SuccBB : successors(BB)) {
829
      assert(!(any_of(OtherExits,
830
                      [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||
831
               SuccBB == LatchExit) &&
832
             "Breaks the definition of dedicated exits!");
833
    }
834
#endif
835
  }
836
1.47k
837
1.47k
  // Update the immediate dominator of the exit blocks and blocks that are
838
1.47k
  // reachable from the exit blocks. This is needed because we now have paths
839
1.47k
  // from both the original loop and the remainder code reaching the exit
840
1.47k
  // blocks. While the IDom of these exit blocks were from the original loop,
841
1.47k
  // now the IDom is the preheader (which decides whether the original loop or
842
1.47k
  // remainder code should run).
843
1.47k
  if (DT && !L->getExitingBlock()) {
844
1
    SmallVector<BasicBlock *, 16> ChildrenToUpdate;
845
1
    // NB! We have to examine the dom children of all loop blocks, not just
846
1
    // those which are the IDom of the exit blocks. This is because blocks
847
1
    // reachable from the exit blocks can have their IDom as the nearest common
848
1
    // dominator of the exit blocks.
849
3
    for (auto *BB : L->blocks()) {
850
3
      auto *DomNodeBB = DT->getNode(BB);
851
3
      for (auto *DomChild : DomNodeBB->getChildren()) {
852
3
        auto *DomChildBB = DomChild->getBlock();
853
3
        if (!L->contains(LI->getLoopFor(DomChildBB)))
854
1
          ChildrenToUpdate.push_back(DomChildBB);
855
3
      }
856
3
    }
857
1
    for (auto *BB : ChildrenToUpdate)
858
1
      DT->changeImmediateDominator(BB, PreHeader);
859
1
  }
860
1.47k
861
1.47k
  // Loop structure should be the following:
862
1.47k
  //  Epilog             Prolog
863
1.47k
  //
864
1.47k
  // PreHeader         PreHeader
865
1.47k
  // NewPreHeader      PrologPreHeader
866
1.47k
  //   Header            PrologHeader
867
1.47k
  //   ...               ...
868
1.47k
  //   Latch             PrologLatch
869
1.47k
  // NewExit           PrologExit
870
1.47k
  // EpilogPreHeader   NewPreHeader
871
1.47k
  //   EpilogHeader      Header
872
1.47k
  //   ...               ...
873
1.47k
  //   EpilogLatch       Latch
874
1.47k
  // LatchExit              LatchExit
875
1.47k
876
1.47k
  // Rewrite the cloned instruction operands to use the values created when the
877
1.47k
  // clone is created.
878
1.84k
  for (BasicBlock *BB : NewBlocks) {
879
26.2k
    for (Instruction &I : *BB) {
880
26.2k
      RemapInstruction(&I, VMap,
881
26.2k
                       RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
882
26.2k
    }
883
1.84k
  }
884
1.47k
885
1.47k
  if (UseEpilogRemainder) {
886
984
    // Connect the epilog code to the original loop and update the
887
984
    // PHI functions.
888
984
    ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
889
984
                  EpilogPreHeader, NewPreHeader, VMap, DT, LI,
890
984
                  PreserveLCSSA);
891
984
892
984
    // Update counter in loop for unrolling.
893
984
    // I should be multiply of Count.
894
984
    IRBuilder<> B2(NewPreHeader->getTerminator());
895
984
    Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
896
984
    BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
897
984
    B2.SetInsertPoint(LatchBR);
898
984
    PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
899
984
                                      Header->getFirstNonPHI());
900
984
    Value *IdxSub =
901
984
        B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
902
984
                     NewIdx->getName() + ".nsub");
903
984
    Value *IdxCmp;
904
984
    if (LatchBR->getSuccessor(0) == Header)
905
79
      IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
906
905
    else
907
905
      IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
908
984
    NewIdx->addIncoming(TestVal, NewPreHeader);
909
984
    NewIdx->addIncoming(IdxSub, Latch);
910
984
    LatchBR->setCondition(IdxCmp);
911
984
  } else {
912
486
    // Connect the prolog code to the original loop and update the
913
486
    // PHI functions.
914
486
    ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
915
486
                  NewPreHeader, VMap, DT, LI, PreserveLCSSA);
916
486
  }
917
1.47k
918
1.47k
  // If this loop is nested, then the loop unroller changes the code in the any
919
1.47k
  // of its parent loops, so the Scalar Evolution pass needs to be run again.
920
1.47k
  SE->forgetTopmostLoop(L);
921
1.47k
922
1.47k
  // Verify that the Dom Tree is correct.
923
#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
924
  if (DT)
925
    assert(DT->verify(DominatorTree::VerificationLevel::Full));
926
#endif
927
928
1.47k
  // Canonicalize to LoopSimplifyForm both original and remainder loops. We
929
1.47k
  // cannot rely on the LoopUnrollPass to do this because it only does
930
1.47k
  // canonicalization for parent/subloops and not the sibling loops.
931
1.47k
  if (OtherExits.size() > 0) {
932
1
    // Generate dedicated exit blocks for the original loop, to preserve
933
1
    // LoopSimplifyForm.
934
1
    formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);
935
1
    // Generate dedicated exit blocks for the remainder loop if one exists, to
936
1
    // preserve LoopSimplifyForm.
937
1
    if (remainderLoop)
938
1
      formDedicatedExitBlocks(remainderLoop, DT, LI, nullptr, PreserveLCSSA);
939
1
  }
940
1.47k
941
1.47k
  auto UnrollResult = LoopUnrollResult::Unmodified;
942
1.47k
  if (remainderLoop && 
UnrollRemainder1.09k
) {
943
20
    LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
944
20
    UnrollResult =
945
20
        UnrollLoop(remainderLoop,
946
20
                   {/*Count*/ Count - 1, /*TripCount*/ Count - 1,
947
20
                    /*Force*/ false, /*AllowRuntime*/ false,
948
20
                    /*AllowExpensiveTripCount*/ false, /*PreserveCondBr*/ true,
949
20
                    /*PreserveOnlyFirst*/ false, /*TripMultiple*/ 1,
950
20
                    /*PeelCount*/ 0, /*UnrollRemainder*/ false, ForgetAllSCEV},
951
20
                   LI, SE, DT, AC, /*ORE*/ nullptr, PreserveLCSSA);
952
20
  }
953
1.47k
954
1.47k
  if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)
955
1.45k
    *ResultLoop = remainderLoop;
956
1.47k
  NumRuntimeUnrolled++;
957
1.47k
  return true;
958
1.47k
}