LLVM  9.0.0svn
LoopUnrollRuntime.cpp
Go to the documentation of this file.
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"
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"
35 #include "llvm/Transforms/Utils.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");
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,
71  LoopInfo *LI, bool PreserveLCSSA) {
72  // Loop structure should be the following:
73  // Preheader
74  // PrologHeader
75  // ...
76  // PrologLatch
77  // PrologExit
78  // NewPreheader
79  // Header
80  // ...
81  // Latch
82  // LatchExit
83  BasicBlock *Latch = L->getLoopLatch();
84  assert(Latch && "Loop must have a latch");
85  BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
86 
87  // Create a PHI node for each outgoing value from the original loop
88  // (which means it is an outgoing value from the prolog code too).
89  // The new PHI node is inserted in the prolog end basic block.
90  // The new PHI node value is added as an operand of a PHI node in either
91  // the loop header or the loop exit block.
92  for (BasicBlock *Succ : successors(Latch)) {
93  for (PHINode &PN : Succ->phis()) {
94  // Add a new PHI node to the prolog end block and add the
95  // appropriate incoming values.
96  // TODO: This code assumes that the PrologExit (or the LatchExit block for
97  // prolog loop) contains only one predecessor from the loop, i.e. the
98  // PrologLatch. When supporting multiple-exiting block loops, we can have
99  // two or more blocks that have the LatchExit as the target in the
100  // original loop.
101  PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
102  PrologExit->getFirstNonPHI());
103  // Adding a value to the new PHI node from the original loop preheader.
104  // This is the value that skips all the prolog code.
105  if (L->contains(&PN)) {
106  // Succ is loop header.
107  NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),
108  PreHeader);
109  } else {
110  // Succ is LatchExit.
111  NewPN->addIncoming(UndefValue::get(PN.getType()), PreHeader);
112  }
113 
114  Value *V = PN.getIncomingValueForBlock(Latch);
115  if (Instruction *I = dyn_cast<Instruction>(V)) {
116  if (L->contains(I)) {
117  V = VMap.lookup(I);
118  }
119  }
120  // Adding a value to the new PHI node from the last prolog block
121  // that was created.
122  NewPN->addIncoming(V, PrologLatch);
123 
124  // Update the existing PHI node operand with the value from the
125  // new PHI node. How this is done depends on if the existing
126  // PHI node is in the original loop block, or the exit block.
127  if (L->contains(&PN)) {
128  PN.setIncomingValue(PN.getBasicBlockIndex(NewPreHeader), NewPN);
129  } else {
130  PN.addIncoming(NewPN, PrologExit);
131  }
132  }
133  }
134 
135  // Make sure that created prolog loop is in simplified form
136  SmallVector<BasicBlock *, 4> PrologExitPreds;
137  Loop *PrologLoop = LI->getLoopFor(PrologLatch);
138  if (PrologLoop) {
139  for (BasicBlock *PredBB : predecessors(PrologExit))
140  if (PrologLoop->contains(PredBB))
141  PrologExitPreds.push_back(PredBB);
142 
143  SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
144  nullptr, PreserveLCSSA);
145  }
146 
147  // Create a branch around the original loop, which is taken if there are no
148  // iterations remaining to be executed after running the prologue.
149  Instruction *InsertPt = PrologExit->getTerminator();
150  IRBuilder<> B(InsertPt);
151 
152  assert(Count != 0 && "nonsensical Count!");
153 
154  // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
155  // This means %xtraiter is (BECount + 1) and all of the iterations of this
156  // loop were executed by the prologue. Note that if BECount <u (Count - 1)
157  // then (BECount + 1) cannot unsigned-overflow.
158  Value *BrLoopExit =
159  B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));
160  // Split the exit to maintain loop canonicalization guarantees
161  SmallVector<BasicBlock *, 4> Preds(predecessors(OriginalLoopLatchExit));
162  SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI,
163  nullptr, PreserveLCSSA);
164  // Add the branch to the exit block (around the unrolled loop)
165  B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader);
166  InsertPt->eraseFromParent();
167  if (DT)
168  DT->changeImmediateDominator(OriginalLoopLatchExit, PrologExit);
169 }
170 
171 /// Connect the unrolling epilog code to the original loop.
172 /// The unrolling epilog code contains code to execute the
173 /// 'extra' iterations if the run-time trip count modulo the
174 /// unroll count is non-zero.
175 ///
176 /// This function performs the following:
177 /// - Update PHI nodes at the unrolling loop exit and epilog loop exit
178 /// - Create PHI nodes at the unrolling loop exit to combine
179 /// values that exit the unrolling loop code and jump around it.
180 /// - Update PHI operands in the epilog loop by the new PHI nodes
181 /// - Branch around the epilog loop if extra iters (ModVal) is zero.
182 ///
183 static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
184  BasicBlock *Exit, BasicBlock *PreHeader,
185  BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
186  ValueToValueMapTy &VMap, DominatorTree *DT,
187  LoopInfo *LI, bool PreserveLCSSA) {
188  BasicBlock *Latch = L->getLoopLatch();
189  assert(Latch && "Loop must have a latch");
190  BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);
191 
192  // Loop structure should be the following:
193  //
194  // PreHeader
195  // NewPreHeader
196  // Header
197  // ...
198  // Latch
199  // NewExit (PN)
200  // EpilogPreHeader
201  // EpilogHeader
202  // ...
203  // EpilogLatch
204  // Exit (EpilogPN)
205 
206  // Update PHI nodes at NewExit and Exit.
207  for (PHINode &PN : NewExit->phis()) {
208  // PN should be used in another PHI located in Exit block as
209  // Exit was split by SplitBlockPredecessors into Exit and NewExit
210  // Basicaly it should look like:
211  // NewExit:
212  // PN = PHI [I, Latch]
213  // ...
214  // Exit:
215  // EpilogPN = PHI [PN, EpilogPreHeader]
216  //
217  // There is EpilogPreHeader incoming block instead of NewExit as
218  // NewExit was spilt 1 more time to get EpilogPreHeader.
219  assert(PN.hasOneUse() && "The phi should have 1 use");
220  PHINode *EpilogPN = cast<PHINode>(PN.use_begin()->getUser());
221  assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");
222 
223  // Add incoming PreHeader from branch around the Loop
224  PN.addIncoming(UndefValue::get(PN.getType()), PreHeader);
225 
226  Value *V = PN.getIncomingValueForBlock(Latch);
228  if (I && L->contains(I))
229  // If value comes from an instruction in the loop add VMap value.
230  V = VMap.lookup(I);
231  // For the instruction out of the loop, constant or undefined value
232  // insert value itself.
233  EpilogPN->addIncoming(V, EpilogLatch);
234 
235  assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&
236  "EpilogPN should have EpilogPreHeader incoming block");
237  // Change EpilogPreHeader incoming block to NewExit.
238  EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
239  NewExit);
240  // Now PHIs should look like:
241  // NewExit:
242  // PN = PHI [I, Latch], [undef, PreHeader]
243  // ...
244  // Exit:
245  // EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
246  }
247 
248  // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
249  // Update corresponding PHI nodes in epilog loop.
250  for (BasicBlock *Succ : successors(Latch)) {
251  // Skip this as we already updated phis in exit blocks.
252  if (!L->contains(Succ))
253  continue;
254  for (PHINode &PN : Succ->phis()) {
255  // Add new PHI nodes to the loop exit block and update epilog
256  // PHIs with the new PHI values.
257  PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
258  NewExit->getFirstNonPHI());
259  // Adding a value to the new PHI node from the unrolling loop preheader.
260  NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);
261  // Adding a value to the new PHI node from the unrolling loop latch.
262  NewPN->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);
263 
264  // Update the existing PHI node operand with the value from the new PHI
265  // node. Corresponding instruction in epilog loop should be PHI.
266  PHINode *VPN = cast<PHINode>(VMap[&PN]);
267  VPN->setIncomingValue(VPN->getBasicBlockIndex(EpilogPreHeader), NewPN);
268  }
269  }
270 
271  Instruction *InsertPt = NewExit->getTerminator();
272  IRBuilder<> B(InsertPt);
273  Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
274  assert(Exit && "Loop must have a single exit block only");
275  // Split the epilogue exit to maintain loop canonicalization guarantees
277  SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI, nullptr,
278  PreserveLCSSA);
279  // Add the branch to the exit block (around the unrolling loop)
280  B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
281  InsertPt->eraseFromParent();
282  if (DT)
283  DT->changeImmediateDominator(Exit, NewExit);
284 
285  // Split the main loop exit to maintain canonicalization guarantees.
286  SmallVector<BasicBlock*, 4> NewExitPreds{Latch};
287  SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, nullptr,
288  PreserveLCSSA);
289 }
290 
291 /// Create a clone of the blocks in a loop and connect them together.
292 /// If CreateRemainderLoop is false, loop structure will not be cloned,
293 /// otherwise a new loop will be created including all cloned blocks, and the
294 /// iterator of it switches to count NewIter down to 0.
295 /// The cloned blocks should be inserted between InsertTop and InsertBot.
296 /// If loop structure is cloned InsertTop should be new preheader, InsertBot
297 /// new loop exit.
298 /// Return the new cloned loop that is created when CreateRemainderLoop is true.
299 static Loop *
300 CloneLoopBlocks(Loop *L, Value *NewIter, const bool CreateRemainderLoop,
301  const bool UseEpilogRemainder, const bool UnrollRemainder,
302  BasicBlock *InsertTop,
303  BasicBlock *InsertBot, BasicBlock *Preheader,
304  std::vector<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
305  ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI) {
306  StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
307  BasicBlock *Header = L->getHeader();
308  BasicBlock *Latch = L->getLoopLatch();
309  Function *F = Header->getParent();
310  LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
311  LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
312  Loop *ParentLoop = L->getParentLoop();
313  NewLoopsMap NewLoops;
314  NewLoops[ParentLoop] = ParentLoop;
315  if (!CreateRemainderLoop)
316  NewLoops[L] = ParentLoop;
317 
318  // For each block in the original loop, create a new copy,
319  // and update the value map with the newly created values.
320  for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
321  BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
322  NewBlocks.push_back(NewBB);
323 
324  // If we're unrolling the outermost loop, there's no remainder loop,
325  // and this block isn't in a nested loop, then the new block is not
326  // in any loop. Otherwise, add it to loopinfo.
327  if (CreateRemainderLoop || LI->getLoopFor(*BB) != L || ParentLoop)
328  addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);
329 
330  VMap[*BB] = NewBB;
331  if (Header == *BB) {
332  // For the first block, add a CFG connection to this newly
333  // created block.
334  InsertTop->getTerminator()->setSuccessor(0, NewBB);
335  }
336 
337  if (DT) {
338  if (Header == *BB) {
339  // The header is dominated by the preheader.
340  DT->addNewBlock(NewBB, InsertTop);
341  } else {
342  // Copy information from original loop to unrolled loop.
343  BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();
344  DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));
345  }
346  }
347 
348  if (Latch == *BB) {
349  // For the last block, if CreateRemainderLoop is false, create a direct
350  // jump to InsertBot. If not, create a loop back to cloned head.
351  VMap.erase((*BB)->getTerminator());
352  BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
353  BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
354  IRBuilder<> Builder(LatchBR);
355  if (!CreateRemainderLoop) {
356  Builder.CreateBr(InsertBot);
357  } else {
358  PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
359  suffix + ".iter",
360  FirstLoopBB->getFirstNonPHI());
361  Value *IdxSub =
362  Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
363  NewIdx->getName() + ".sub");
364  Value *IdxCmp =
365  Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
366  Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
367  NewIdx->addIncoming(NewIter, InsertTop);
368  NewIdx->addIncoming(IdxSub, NewBB);
369  }
370  LatchBR->eraseFromParent();
371  }
372  }
373 
374  // Change the incoming values to the ones defined in the preheader or
375  // cloned loop.
376  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
377  PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
378  if (!CreateRemainderLoop) {
379  if (UseEpilogRemainder) {
380  unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
381  NewPHI->setIncomingBlock(idx, InsertTop);
382  NewPHI->removeIncomingValue(Latch, false);
383  } else {
384  VMap[&*I] = NewPHI->getIncomingValueForBlock(Preheader);
385  cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
386  }
387  } else {
388  unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
389  NewPHI->setIncomingBlock(idx, InsertTop);
390  BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
391  idx = NewPHI->getBasicBlockIndex(Latch);
392  Value *InVal = NewPHI->getIncomingValue(idx);
393  NewPHI->setIncomingBlock(idx, NewLatch);
394  if (Value *V = VMap.lookup(InVal))
395  NewPHI->setIncomingValue(idx, V);
396  }
397  }
398  if (CreateRemainderLoop) {
399  Loop *NewLoop = NewLoops[L];
400  MDNode *LoopID = NewLoop->getLoopID();
401  assert(NewLoop && "L should have been cloned");
402 
403  // Only add loop metadata if the loop is not going to be completely
404  // unrolled.
405  if (UnrollRemainder)
406  return NewLoop;
407 
410  if (NewLoopID.hasValue()) {
411  NewLoop->setLoopID(NewLoopID.getValue());
412 
413  // Do not setLoopAlreadyUnrolled if loop attributes have been defined
414  // explicitly.
415  return NewLoop;
416  }
417 
418  // Add unroll disable metadata to disable future unrolling for this loop.
419  NewLoop->setLoopAlreadyUnrolled();
420  return NewLoop;
421  }
422  else
423  return nullptr;
424 }
425 
426 /// Returns true if we can safely unroll a multi-exit/exiting loop. OtherExits
427 /// is populated with all the loop exit blocks other than the LatchExit block.
428 static bool
430  BasicBlock *LatchExit, bool PreserveLCSSA,
431  bool UseEpilogRemainder) {
432 
433  // We currently have some correctness constrains in unrolling a multi-exit
434  // loop. Check for these below.
435 
436  // We rely on LCSSA form being preserved when the exit blocks are transformed.
437  if (!PreserveLCSSA)
438  return false;
440  L->getUniqueExitBlocks(Exits);
441  for (auto *BB : Exits)
442  if (BB != LatchExit)
443  OtherExits.push_back(BB);
444 
445  // TODO: Support multiple exiting blocks jumping to the `LatchExit` when
446  // UnrollRuntimeMultiExit is true. This will need updating the logic in
447  // connectEpilog/connectProlog.
448  if (!LatchExit->getSinglePredecessor()) {
449  LLVM_DEBUG(
450  dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
451  "predecessor.\n");
452  return false;
453  }
454  // FIXME: We bail out of multi-exit unrolling when epilog loop is generated
455  // and L is an inner loop. This is because in presence of multiple exits, the
456  // outer loop is incorrect: we do not add the EpilogPreheader and exit to the
457  // outer loop. This is automatically handled in the prolog case, so we do not
458  // have that bug in prolog generation.
459  if (UseEpilogRemainder && L->getParentLoop())
460  return false;
461 
462  // All constraints have been satisfied.
463  return true;
464 }
465 
466 /// Returns true if we can profitably unroll the multi-exit loop L. Currently,
467 /// we return true only if UnrollRuntimeMultiExit is set to true.
469  Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
470  bool PreserveLCSSA, bool UseEpilogRemainder) {
471 
472 #if !defined(NDEBUG)
473  SmallVector<BasicBlock *, 8> OtherExitsDummyCheck;
474  assert(canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit,
475  PreserveLCSSA, UseEpilogRemainder) &&
476  "Should be safe to unroll before checking profitability!");
477 #endif
478 
479  // Priority goes to UnrollRuntimeMultiExit if it's supplied.
480  if (UnrollRuntimeMultiExit.getNumOccurrences())
481  return UnrollRuntimeMultiExit;
482 
483  // The main pain point with multi-exit loop unrolling is that once unrolled,
484  // we will not be able to merge all blocks into a straight line code.
485  // There are branches within the unrolled loop that go to the OtherExits.
486  // The second point is the increase in code size, but this is true
487  // irrespective of multiple exits.
488 
489  // Note: Both the heuristics below are coarse grained. We are essentially
490  // enabling unrolling of loops that have a single side exit other than the
491  // normal LatchExit (i.e. exiting into a deoptimize block).
492  // The heuristics considered are:
493  // 1. low number of branches in the unrolled version.
494  // 2. high predictability of these extra branches.
495  // We avoid unrolling loops that have more than two exiting blocks. This
496  // limits the total number of branches in the unrolled loop to be atmost
497  // the unroll factor (since one of the exiting blocks is the latch block).
498  SmallVector<BasicBlock*, 4> ExitingBlocks;
499  L->getExitingBlocks(ExitingBlocks);
500  if (ExitingBlocks.size() > 2)
501  return false;
502 
503  // The second heuristic is that L has one exit other than the latchexit and
504  // that exit is a deoptimize block. We know that deoptimize blocks are rarely
505  // taken, which also implies the branch leading to the deoptimize block is
506  // highly predictable.
507  return (OtherExits.size() == 1 &&
508  OtherExits[0]->getTerminatingDeoptimizeCall());
509  // TODO: These can be fine-tuned further to consider code size or deopt states
510  // that are captured by the deoptimize exit block.
511  // Also, we can extend this to support more cases, if we actually
512  // know of kinds of multiexit loops that would benefit from unrolling.
513 }
514 
515 /// Insert code in the prolog/epilog code when unrolling a loop with a
516 /// run-time trip-count.
517 ///
518 /// This method assumes that the loop unroll factor is total number
519 /// of loop bodies in the loop after unrolling. (Some folks refer
520 /// to the unroll factor as the number of *extra* copies added).
521 /// We assume also that the loop unroll factor is a power-of-two. So, after
522 /// unrolling the loop, the number of loop bodies executed is 2,
523 /// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
524 /// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
525 /// the switch instruction is generated.
526 ///
527 /// ***Prolog case***
528 /// extraiters = tripcount % loopfactor
529 /// if (extraiters == 0) jump Loop:
530 /// else jump Prol:
531 /// Prol: LoopBody;
532 /// extraiters -= 1 // Omitted if unroll factor is 2.
533 /// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
534 /// if (tripcount < loopfactor) jump End:
535 /// Loop:
536 /// ...
537 /// End:
538 ///
539 /// ***Epilog case***
540 /// extraiters = tripcount % loopfactor
541 /// if (tripcount < loopfactor) jump LoopExit:
542 /// unroll_iters = tripcount - extraiters
543 /// Loop: LoopBody; (executes unroll_iter times);
544 /// unroll_iter -= 1
545 /// if (unroll_iter != 0) jump Loop:
546 /// LoopExit:
547 /// if (extraiters == 0) jump EpilExit:
548 /// Epil: LoopBody; (executes extraiters times)
549 /// extraiters -= 1 // Omitted if unroll factor is 2.
550 /// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
551 /// EpilExit:
552 
553 bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
554  bool AllowExpensiveTripCount,
555  bool UseEpilogRemainder,
556  bool UnrollRemainder, bool ForgetAllSCEV,
557  LoopInfo *LI, ScalarEvolution *SE,
559  bool PreserveLCSSA, Loop **ResultLoop) {
560  LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
561  LLVM_DEBUG(L->dump());
562  LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
563  : dbgs() << "Using prolog remainder.\n");
564 
565  // Make sure the loop is in canonical form.
566  if (!L->isLoopSimplifyForm()) {
567  LLVM_DEBUG(dbgs() << "Not in simplify form!\n");
568  return false;
569  }
570 
571  // Guaranteed by LoopSimplifyForm.
572  BasicBlock *Latch = L->getLoopLatch();
573  BasicBlock *Header = L->getHeader();
574 
575  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
576 
577  if (!LatchBR || LatchBR->isUnconditional()) {
578  // The loop-rotate pass can be helpful to avoid this in many cases.
579  LLVM_DEBUG(
580  dbgs()
581  << "Loop latch not terminated by a conditional branch.\n");
582  return false;
583  }
584 
585  unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;
586  BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
587 
588  if (L->contains(LatchExit)) {
589  // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
590  // targets of the Latch be an exit block out of the loop.
591  LLVM_DEBUG(
592  dbgs()
593  << "One of the loop latch successors must be the exit block.\n");
594  return false;
595  }
596 
597  // These are exit blocks other than the target of the latch exiting block.
598  SmallVector<BasicBlock *, 4> OtherExits;
599  bool isMultiExitUnrollingEnabled =
600  canSafelyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
601  UseEpilogRemainder) &&
602  canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
603  UseEpilogRemainder);
604  // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
605  if (!isMultiExitUnrollingEnabled &&
606  (!L->getExitingBlock() || OtherExits.size())) {
607  LLVM_DEBUG(
608  dbgs()
609  << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
610  "enabled!\n");
611  return false;
612  }
613  // Use Scalar Evolution to compute the trip count. This allows more loops to
614  // be unrolled than relying on induction var simplification.
615  if (!SE)
616  return false;
617 
618  // Only unroll loops with a computable trip count, and the trip count needs
619  // to be an int value (allowing a pointer type is a TODO item).
620  // We calculate the backedge count by using getExitCount on the Latch block,
621  // which is proven to be the only exiting block in this loop. This is same as
622  // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
623  // exiting blocks).
624  const SCEV *BECountSC = SE->getExitCount(L, Latch);
625  if (isa<SCEVCouldNotCompute>(BECountSC) ||
626  !BECountSC->getType()->isIntegerTy()) {
627  LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");
628  return false;
629  }
630 
631  unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
632 
633  // Add 1 since the backedge count doesn't include the first loop iteration.
634  const SCEV *TripCountSC =
635  SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
636  if (isa<SCEVCouldNotCompute>(TripCountSC)) {
637  LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
638  return false;
639  }
640 
641  BasicBlock *PreHeader = L->getLoopPreheader();
642  BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
643  const DataLayout &DL = Header->getModule()->getDataLayout();
644  SCEVExpander Expander(*SE, DL, "loop-unroll");
645  if (!AllowExpensiveTripCount &&
646  Expander.isHighCostExpansion(TripCountSC, L, PreHeaderBR)) {
647  LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
648  return false;
649  }
650 
651  // This constraint lets us deal with an overflowing trip count easily; see the
652  // comment on ModVal below.
653  if (Log2_32(Count) > BEWidth) {
654  LLVM_DEBUG(
655  dbgs()
656  << "Count failed constraint on overflow trip count calculation.\n");
657  return false;
658  }
659 
660  // Loop structure is the following:
661  //
662  // PreHeader
663  // Header
664  // ...
665  // Latch
666  // LatchExit
667 
668  BasicBlock *NewPreHeader;
669  BasicBlock *NewExit = nullptr;
670  BasicBlock *PrologExit = nullptr;
671  BasicBlock *EpilogPreHeader = nullptr;
672  BasicBlock *PrologPreHeader = nullptr;
673 
674  if (UseEpilogRemainder) {
675  // If epilog remainder
676  // Split PreHeader to insert a branch around loop for unrolling.
677  NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
678  NewPreHeader->setName(PreHeader->getName() + ".new");
679  // Split LatchExit to create phi nodes from branch above.
680  SmallVector<BasicBlock*, 4> Preds(predecessors(LatchExit));
681  NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa", DT, LI,
682  nullptr, PreserveLCSSA);
683  // NewExit gets its DebugLoc from LatchExit, which is not part of the
684  // original Loop.
685  // Fix this by setting Loop's DebugLoc to NewExit.
686  auto *NewExitTerminator = NewExit->getTerminator();
687  NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
688  // Split NewExit to insert epilog remainder loop.
689  EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);
690  EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
691  } else {
692  // If prolog remainder
693  // Split the original preheader twice to insert prolog remainder loop
694  PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
695  PrologPreHeader->setName(Header->getName() + ".prol.preheader");
696  PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
697  DT, LI);
698  PrologExit->setName(Header->getName() + ".prol.loopexit");
699  // Split PrologExit to get NewPreHeader.
700  NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
701  NewPreHeader->setName(PreHeader->getName() + ".new");
702  }
703  // Loop structure should be the following:
704  // Epilog Prolog
705  //
706  // PreHeader PreHeader
707  // *NewPreHeader *PrologPreHeader
708  // Header *PrologExit
709  // ... *NewPreHeader
710  // Latch Header
711  // *NewExit ...
712  // *EpilogPreHeader Latch
713  // LatchExit LatchExit
714 
715  // Calculate conditions for branch around loop for unrolling
716  // in epilog case and around prolog remainder loop in prolog case.
717  // Compute the number of extra iterations required, which is:
718  // extra iterations = run-time trip count % loop unroll factor
719  PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
720  Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
721  PreHeaderBR);
722  Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
723  PreHeaderBR);
724  IRBuilder<> B(PreHeaderBR);
725  Value *ModVal;
726  // Calculate ModVal = (BECount + 1) % Count.
727  // Note that TripCount is BECount + 1.
728  if (isPowerOf2_32(Count)) {
729  // When Count is power of 2 we don't BECount for epilog case, however we'll
730  // need it for a branch around unrolling loop for prolog case.
731  ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
732  // 1. There are no iterations to be run in the prolog/epilog loop.
733  // OR
734  // 2. The addition computing TripCount overflowed.
735  //
736  // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
737  // the number of iterations that remain to be run in the original loop is a
738  // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
739  // explicitly check this above).
740  } else {
741  // As (BECount + 1) can potentially unsigned overflow we count
742  // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
743  Value *ModValTmp = B.CreateURem(BECount,
744  ConstantInt::get(BECount->getType(),
745  Count));
746  Value *ModValAdd = B.CreateAdd(ModValTmp,
747  ConstantInt::get(ModValTmp->getType(), 1));
748  // At that point (BECount % Count) + 1 could be equal to Count.
749  // To handle this case we need to take mod by Count one more time.
750  ModVal = B.CreateURem(ModValAdd,
751  ConstantInt::get(BECount->getType(), Count),
752  "xtraiter");
753  }
754  Value *BranchVal =
755  UseEpilogRemainder ? B.CreateICmpULT(BECount,
756  ConstantInt::get(BECount->getType(),
757  Count - 1)) :
758  B.CreateIsNotNull(ModVal, "lcmp.mod");
759  BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
760  BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
761  // Branch to either remainder (extra iterations) loop or unrolling loop.
762  B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
763  PreHeaderBR->eraseFromParent();
764  if (DT) {
765  if (UseEpilogRemainder)
766  DT->changeImmediateDominator(NewExit, PreHeader);
767  else
768  DT->changeImmediateDominator(PrologExit, PreHeader);
769  }
770  Function *F = Header->getParent();
771  // Get an ordered list of blocks in the loop to help with the ordering of the
772  // cloned blocks in the prolog/epilog code
773  LoopBlocksDFS LoopBlocks(L);
774  LoopBlocks.perform(LI);
775 
776  //
777  // For each extra loop iteration, create a copy of the loop's basic blocks
778  // and generate a condition that branches to the copy depending on the
779  // number of 'left over' iterations.
780  //
781  std::vector<BasicBlock *> NewBlocks;
782  ValueToValueMapTy VMap;
783 
784  // For unroll factor 2 remainder loop will have 1 iterations.
785  // Do not create 1 iteration loop.
786  bool CreateRemainderLoop = (Count != 2);
787 
788  // Clone all the basic blocks in the loop. If Count is 2, we don't clone
789  // the loop, otherwise we create a cloned loop to execute the extra
790  // iterations. This function adds the appropriate CFG connections.
791  BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
792  BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
793  Loop *remainderLoop = CloneLoopBlocks(
794  L, ModVal, CreateRemainderLoop, UseEpilogRemainder, UnrollRemainder,
795  InsertTop, InsertBot,
796  NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
797 
798  // Insert the cloned blocks into the function.
799  F->getBasicBlockList().splice(InsertBot->getIterator(),
800  F->getBasicBlockList(),
801  NewBlocks[0]->getIterator(),
802  F->end());
803 
804  // Now the loop blocks are cloned and the other exiting blocks from the
805  // remainder are connected to the original Loop's exit blocks. The remaining
806  // work is to update the phi nodes in the original loop, and take in the
807  // values from the cloned region.
808  for (auto *BB : OtherExits) {
809  for (auto &II : *BB) {
810 
811  // Given we preserve LCSSA form, we know that the values used outside the
812  // loop will be used through these phi nodes at the exit blocks that are
813  // transformed below.
814  if (!isa<PHINode>(II))
815  break;
816  PHINode *Phi = cast<PHINode>(&II);
817  unsigned oldNumOperands = Phi->getNumIncomingValues();
818  // Add the incoming values from the remainder code to the end of the phi
819  // node.
820  for (unsigned i =0; i < oldNumOperands; i++){
821  Value *newVal = VMap.lookup(Phi->getIncomingValue(i));
822  // newVal can be a constant or derived from values outside the loop, and
823  // hence need not have a VMap value. Also, since lookup already generated
824  // a default "null" VMap entry for this value, we need to populate that
825  // VMap entry correctly, with the mapped entry being itself.
826  if (!newVal) {
827  newVal = Phi->getIncomingValue(i);
828  VMap[Phi->getIncomingValue(i)] = Phi->getIncomingValue(i);
829  }
830  Phi->addIncoming(newVal,
831  cast<BasicBlock>(VMap[Phi->getIncomingBlock(i)]));
832  }
833  }
834 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
835  for (BasicBlock *SuccBB : successors(BB)) {
836  assert(!(any_of(OtherExits,
837  [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||
838  SuccBB == LatchExit) &&
839  "Breaks the definition of dedicated exits!");
840  }
841 #endif
842  }
843 
844  // Update the immediate dominator of the exit blocks and blocks that are
845  // reachable from the exit blocks. This is needed because we now have paths
846  // from both the original loop and the remainder code reaching the exit
847  // blocks. While the IDom of these exit blocks were from the original loop,
848  // now the IDom is the preheader (which decides whether the original loop or
849  // remainder code should run).
850  if (DT && !L->getExitingBlock()) {
851  SmallVector<BasicBlock *, 16> ChildrenToUpdate;
852  // NB! We have to examine the dom children of all loop blocks, not just
853  // those which are the IDom of the exit blocks. This is because blocks
854  // reachable from the exit blocks can have their IDom as the nearest common
855  // dominator of the exit blocks.
856  for (auto *BB : L->blocks()) {
857  auto *DomNodeBB = DT->getNode(BB);
858  for (auto *DomChild : DomNodeBB->getChildren()) {
859  auto *DomChildBB = DomChild->getBlock();
860  if (!L->contains(LI->getLoopFor(DomChildBB)))
861  ChildrenToUpdate.push_back(DomChildBB);
862  }
863  }
864  for (auto *BB : ChildrenToUpdate)
865  DT->changeImmediateDominator(BB, PreHeader);
866  }
867 
868  // Loop structure should be the following:
869  // Epilog Prolog
870  //
871  // PreHeader PreHeader
872  // NewPreHeader PrologPreHeader
873  // Header PrologHeader
874  // ... ...
875  // Latch PrologLatch
876  // NewExit PrologExit
877  // EpilogPreHeader NewPreHeader
878  // EpilogHeader Header
879  // ... ...
880  // EpilogLatch Latch
881  // LatchExit LatchExit
882 
883  // Rewrite the cloned instruction operands to use the values created when the
884  // clone is created.
885  for (BasicBlock *BB : NewBlocks) {
886  for (Instruction &I : *BB) {
887  RemapInstruction(&I, VMap,
889  }
890  }
891 
892  if (UseEpilogRemainder) {
893  // Connect the epilog code to the original loop and update the
894  // PHI functions.
895  ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
896  EpilogPreHeader, NewPreHeader, VMap, DT, LI,
897  PreserveLCSSA);
898 
899  // Update counter in loop for unrolling.
900  // I should be multiply of Count.
901  IRBuilder<> B2(NewPreHeader->getTerminator());
902  Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
903  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
904  B2.SetInsertPoint(LatchBR);
905  PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
906  Header->getFirstNonPHI());
907  Value *IdxSub =
908  B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
909  NewIdx->getName() + ".nsub");
910  Value *IdxCmp;
911  if (LatchBR->getSuccessor(0) == Header)
912  IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
913  else
914  IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
915  NewIdx->addIncoming(TestVal, NewPreHeader);
916  NewIdx->addIncoming(IdxSub, Latch);
917  LatchBR->setCondition(IdxCmp);
918  } else {
919  // Connect the prolog code to the original loop and update the
920  // PHI functions.
921  ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
922  NewPreHeader, VMap, DT, LI, PreserveLCSSA);
923  }
924 
925  // If this loop is nested, then the loop unroller changes the code in the any
926  // of its parent loops, so the Scalar Evolution pass needs to be run again.
927  SE->forgetTopmostLoop(L);
928 
929  // Verify that the Dom Tree is correct.
930 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
931  if (DT)
933 #endif
934 
935  // Canonicalize to LoopSimplifyForm both original and remainder loops. We
936  // cannot rely on the LoopUnrollPass to do this because it only does
937  // canonicalization for parent/subloops and not the sibling loops.
938  if (OtherExits.size() > 0) {
939  // Generate dedicated exit blocks for the original loop, to preserve
940  // LoopSimplifyForm.
941  formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);
942  // Generate dedicated exit blocks for the remainder loop if one exists, to
943  // preserve LoopSimplifyForm.
944  if (remainderLoop)
945  formDedicatedExitBlocks(remainderLoop, DT, LI, nullptr, PreserveLCSSA);
946  }
947 
948  auto UnrollResult = LoopUnrollResult::Unmodified;
949  if (remainderLoop && UnrollRemainder) {
950  LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
951  UnrollResult =
952  UnrollLoop(remainderLoop,
953  {/*Count*/ Count - 1, /*TripCount*/ Count - 1,
954  /*Force*/ false, /*AllowRuntime*/ false,
955  /*AllowExpensiveTripCount*/ false, /*PreserveCondBr*/ true,
956  /*PreserveOnlyFirst*/ false, /*TripMultiple*/ 1,
957  /*PeelCount*/ 0, /*UnrollRemainder*/ false, ForgetAllSCEV},
958  LI, SE, DT, AC, /*ORE*/ nullptr, PreserveLCSSA);
959  }
960 
961  if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)
962  *ResultLoop = remainderLoop;
963  NumRuntimeUnrolled++;
964  return true;
965 }
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional &#39;br Cond, TrueDest, FalseDest&#39; instruction.
Definition: IRBuilder.h:853
static bool canSafelyUnrollMultiExitLoop(Loop *L, SmallVectorImpl< BasicBlock *> &OtherExits, BasicBlock *LatchExit, bool PreserveLCSSA, bool UseEpilogRemainder)
Returns true if we can safely unroll a multi-exit/exiting loop.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:224
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return an i1 value testing if Arg is not null.
Definition: IRBuilder.h:2152
const SCEV * getConstant(ConstantInt *V)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1890
iterator end()
Definition: Function.h:663
The main scalar evolution driver.
This file contains the declarations for metadata subclasses.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
bool isHighCostExpansion(const SCEV *Expr, Loop *L, const Instruction *At=nullptr)
Return true for expressions that may incur non-trivial cost to evaluate at runtime.
A cache of @llvm.assume calls within a function.
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:863
F(f)
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the edge connecting specified block.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:133
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:697
static Loop * CloneLoopBlocks(Loop *L, Value *NewIter, const bool CreateRemainderLoop, const bool UseEpilogRemainder, const bool UnrollRemainder, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *Preheader, std::vector< BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI)
Create a clone of the blocks in a loop and connect them together.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:196
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:742
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1049
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:285
RPOIterator endRPO() const
Definition: LoopIterator.h:140
BlockT * getHeader() const
Definition: LoopInfo.h:100
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:257
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:255
const char *const LLVMLoopUnrollFollowupRemainder
Definition: UnrollLoop.h:44
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: ValueMap.h:170
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:847
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:72
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:49
static void ConnectProlog(Loop *L, Value *BECount, unsigned Count, BasicBlock *PrologExit, BasicBlock *OriginalLoopLatchExit, BasicBlock *PreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Connect the unrolling prolog code to the original loop.
The loop was fully unrolled into straight-line code.
NodeT * getBlock() const
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static cl::opt< bool > UnrollRuntimeMultiExit("unroll-runtime-multi-exit", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolling for loops with multiple exits, when " "epilog is generated"))
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:189
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:318
void dump() const
Definition: LoopInfo.cpp:391
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:428
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Conditional or Unconditional Branch instruction.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
DomTreeNodeBase * getIDom() const
Value * getIncomingValueForBlock(const BasicBlock *BB) const
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop&#39;s loop id metadata.
Definition: LoopInfo.cpp:269
const SCEV * getAddExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
static bool canProfitablyUnrollMultiExitLoop(Loop *L, SmallVectorImpl< BasicBlock *> &OtherExits, BasicBlock *LatchExit, bool PreserveLCSSA, bool UseEpilogRemainder)
Returns true if we can profitably unroll the multi-exit loop L.
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:327
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1192
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
self_iterator getIterator()
Definition: ilist_node.h:81
void getExitingBlocks(SmallVectorImpl< BlockT *> &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
size_t size() const
Definition: SmallVector.h:52
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit, BasicBlock *Exit, BasicBlock *PreHeader, BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Connect the unrolling epilog code to the original loop.
const char *const LLVMLoopUnrollFollowupAll
Definition: UnrollLoop.h:41
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Iterator for intrusive lists based on ilist_node.
Type * getType() const
Return the LLVM type of this SCEV expression.
void setIncomingBlock(unsigned i, BasicBlock *BB)
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:631
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Value * CreateURem(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1128
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
Definition: LoopUtils.cpp:250
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:538
const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)
Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...
Definition: LoopUnroll.cpp:189
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:97
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM...
Definition: ValueMapper.h:250
This class uses information about analyze scalars to rewrite expressions in canonical form...
If this flag is set, the remapper ignores missing function-local entries (Argument, Instruction, BasicBlock) that are not in the value map.
Definition: ValueMapper.h:90
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
bool hasValue() const
Definition: Optional.h:259
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:211
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:233
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:321
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:465
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:334
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:638
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:324
bool isUnconditional() const
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1199
void setCondition(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
succ_range successors(Instruction *I)
Definition: CFG.h:259
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
The loop was not modified.
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
void getUniqueExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:99
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
const SCEV * getExitCount(const Loop *L, BasicBlock *ExitingBlock)
Get the expression for the number of loop iterations for which this loop is guaranteed not to exit vi...
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
bool erase(const KeyT &Val)
Definition: ValueMap.h:196
void forgetTopmostLoop(const Loop *L)