LLVM  12.0.0git
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"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/MDBuilder.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/Module.h"
33 #include "llvm/Support/Debug.h"
35 #include "llvm/Transforms/Utils.h"
41 #include <algorithm>
42 
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "loop-unroll"
46 
47 STATISTIC(NumRuntimeUnrolled,
48  "Number of loops unrolled with run-time trip counts");
50  "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,
51  cl::desc("Allow runtime unrolling for loops with multiple exits, when "
52  "epilog is generated"));
53 
54 /// Connect the unrolling prolog code to the original loop.
55 /// The unrolling prolog code contains code to execute the
56 /// 'extra' iterations if the run-time trip count modulo the
57 /// unroll count is non-zero.
58 ///
59 /// This function performs the following:
60 /// - Create PHI nodes at prolog end block to combine values
61 /// that exit the prolog code and jump around the prolog.
62 /// - Add a PHI operand to a PHI node at the loop exit block
63 /// for values that exit the prolog and go around the loop.
64 /// - Branch around the original loop if the trip count is less
65 /// than the unroll factor.
66 ///
67 static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
68  BasicBlock *PrologExit,
69  BasicBlock *OriginalLoopLatchExit,
70  BasicBlock *PreHeader, BasicBlock *NewPreHeader,
72  LoopInfo *LI, bool PreserveLCSSA) {
73  // Loop structure should be the following:
74  // Preheader
75  // PrologHeader
76  // ...
77  // PrologLatch
78  // PrologExit
79  // NewPreheader
80  // Header
81  // ...
82  // Latch
83  // LatchExit
84  BasicBlock *Latch = L->getLoopLatch();
85  assert(Latch && "Loop must have a latch");
86  BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
87 
88  // Create a PHI node for each outgoing value from the original loop
89  // (which means it is an outgoing value from the prolog code too).
90  // The new PHI node is inserted in the prolog end basic block.
91  // The new PHI node value is added as an operand of a PHI node in either
92  // the loop header or the loop exit block.
93  for (BasicBlock *Succ : successors(Latch)) {
94  for (PHINode &PN : Succ->phis()) {
95  // Add a new PHI node to the prolog end block and add the
96  // appropriate incoming values.
97  // TODO: This code assumes that the PrologExit (or the LatchExit block for
98  // prolog loop) contains only one predecessor from the loop, i.e. the
99  // PrologLatch. When supporting multiple-exiting block loops, we can have
100  // two or more blocks that have the LatchExit as the target in the
101  // original loop.
102  PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
103  PrologExit->getFirstNonPHI());
104  // Adding a value to the new PHI node from the original loop preheader.
105  // This is the value that skips all the prolog code.
106  if (L->contains(&PN)) {
107  // Succ is loop header.
108  NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),
109  PreHeader);
110  } else {
111  // Succ is LatchExit.
112  NewPN->addIncoming(UndefValue::get(PN.getType()), PreHeader);
113  }
114 
115  Value *V = PN.getIncomingValueForBlock(Latch);
116  if (Instruction *I = dyn_cast<Instruction>(V)) {
117  if (L->contains(I)) {
118  V = VMap.lookup(I);
119  }
120  }
121  // Adding a value to the new PHI node from the last prolog block
122  // that was created.
123  NewPN->addIncoming(V, PrologLatch);
124 
125  // Update the existing PHI node operand with the value from the
126  // new PHI node. How this is done depends on if the existing
127  // PHI node is in the original loop block, or the exit block.
128  if (L->contains(&PN))
129  PN.setIncomingValueForBlock(NewPreHeader, NewPN);
130  else
131  PN.addIncoming(NewPN, PrologExit);
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);
227  Instruction *I = dyn_cast<Instruction>(V);
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->setIncomingValueForBlock(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  assert(NewLoop && "L should have been cloned");
401  MDNode *LoopID = NewLoop->getLoopID();
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 canSafelyUnrollMultiExitLoop(Loop *L, BasicBlock *LatchExit,
429  bool PreserveLCSSA,
430  bool UseEpilogRemainder) {
431 
432  // We currently have some correctness constrains in unrolling a multi-exit
433  // loop. Check for these below.
434 
435  // We rely on LCSSA form being preserved when the exit blocks are transformed.
436  if (!PreserveLCSSA)
437  return false;
438 
439  // TODO: Support multiple exiting blocks jumping to the `LatchExit` when
440  // UnrollRuntimeMultiExit is true. This will need updating the logic in
441  // connectEpilog/connectProlog.
442  if (!LatchExit->getSinglePredecessor()) {
443  LLVM_DEBUG(
444  dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
445  "predecessor.\n");
446  return false;
447  }
448  // FIXME: We bail out of multi-exit unrolling when epilog loop is generated
449  // and L is an inner loop. This is because in presence of multiple exits, the
450  // outer loop is incorrect: we do not add the EpilogPreheader and exit to the
451  // outer loop. This is automatically handled in the prolog case, so we do not
452  // have that bug in prolog generation.
453  if (UseEpilogRemainder && L->getParentLoop())
454  return false;
455 
456  // All constraints have been satisfied.
457  return true;
458 }
459 
460 /// Returns true if we can profitably unroll the multi-exit loop L. Currently,
461 /// we return true only if UnrollRuntimeMultiExit is set to true.
463  Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
464  bool PreserveLCSSA, bool UseEpilogRemainder) {
465 
466 #if !defined(NDEBUG)
467  assert(canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA,
468  UseEpilogRemainder) &&
469  "Should be safe to unroll before checking profitability!");
470 #endif
471 
472  // Priority goes to UnrollRuntimeMultiExit if it's supplied.
474  return UnrollRuntimeMultiExit;
475 
476  // The main pain point with multi-exit loop unrolling is that once unrolled,
477  // we will not be able to merge all blocks into a straight line code.
478  // There are branches within the unrolled loop that go to the OtherExits.
479  // The second point is the increase in code size, but this is true
480  // irrespective of multiple exits.
481 
482  // Note: Both the heuristics below are coarse grained. We are essentially
483  // enabling unrolling of loops that have a single side exit other than the
484  // normal LatchExit (i.e. exiting into a deoptimize block).
485  // The heuristics considered are:
486  // 1. low number of branches in the unrolled version.
487  // 2. high predictability of these extra branches.
488  // We avoid unrolling loops that have more than two exiting blocks. This
489  // limits the total number of branches in the unrolled loop to be atmost
490  // the unroll factor (since one of the exiting blocks is the latch block).
491  SmallVector<BasicBlock*, 4> ExitingBlocks;
492  L->getExitingBlocks(ExitingBlocks);
493  if (ExitingBlocks.size() > 2)
494  return false;
495 
496  // The second heuristic is that L has one exit other than the latchexit and
497  // that exit is a deoptimize block. We know that deoptimize blocks are rarely
498  // taken, which also implies the branch leading to the deoptimize block is
499  // highly predictable.
500  return (OtherExits.size() == 1 &&
501  OtherExits[0]->getTerminatingDeoptimizeCall());
502  // TODO: These can be fine-tuned further to consider code size or deopt states
503  // that are captured by the deoptimize exit block.
504  // Also, we can extend this to support more cases, if we actually
505  // know of kinds of multiexit loops that would benefit from unrolling.
506 }
507 
508 // Assign the maximum possible trip count as the back edge weight for the
509 // remainder loop if the original loop comes with a branch weight.
511  Loop *RemainderLoop,
512  uint64_t UnrollFactor) {
513  uint64_t TrueWeight, FalseWeight;
514  BranchInst *LatchBR =
515  cast<BranchInst>(OrigLoop->getLoopLatch()->getTerminator());
516  if (LatchBR->extractProfMetadata(TrueWeight, FalseWeight)) {
517  uint64_t ExitWeight = LatchBR->getSuccessor(0) == OrigLoop->getHeader()
518  ? FalseWeight
519  : TrueWeight;
520  assert(UnrollFactor > 1);
521  uint64_t BackEdgeWeight = (UnrollFactor - 1) * ExitWeight;
522  BasicBlock *Header = RemainderLoop->getHeader();
523  BasicBlock *Latch = RemainderLoop->getLoopLatch();
524  auto *RemainderLatchBR = cast<BranchInst>(Latch->getTerminator());
525  unsigned HeaderIdx = (RemainderLatchBR->getSuccessor(0) == Header ? 0 : 1);
526  MDBuilder MDB(RemainderLatchBR->getContext());
527  MDNode *WeightNode =
528  HeaderIdx ? MDB.createBranchWeights(ExitWeight, BackEdgeWeight)
529  : MDB.createBranchWeights(BackEdgeWeight, ExitWeight);
530  RemainderLatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
531  }
532 }
533 
534 /// Insert code in the prolog/epilog code when unrolling a loop with a
535 /// run-time trip-count.
536 ///
537 /// This method assumes that the loop unroll factor is total number
538 /// of loop bodies in the loop after unrolling. (Some folks refer
539 /// to the unroll factor as the number of *extra* copies added).
540 /// We assume also that the loop unroll factor is a power-of-two. So, after
541 /// unrolling the loop, the number of loop bodies executed is 2,
542 /// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
543 /// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
544 /// the switch instruction is generated.
545 ///
546 /// ***Prolog case***
547 /// extraiters = tripcount % loopfactor
548 /// if (extraiters == 0) jump Loop:
549 /// else jump Prol:
550 /// Prol: LoopBody;
551 /// extraiters -= 1 // Omitted if unroll factor is 2.
552 /// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
553 /// if (tripcount < loopfactor) jump End:
554 /// Loop:
555 /// ...
556 /// End:
557 ///
558 /// ***Epilog case***
559 /// extraiters = tripcount % loopfactor
560 /// if (tripcount < loopfactor) jump LoopExit:
561 /// unroll_iters = tripcount - extraiters
562 /// Loop: LoopBody; (executes unroll_iter times);
563 /// unroll_iter -= 1
564 /// if (unroll_iter != 0) jump Loop:
565 /// LoopExit:
566 /// if (extraiters == 0) jump EpilExit:
567 /// Epil: LoopBody; (executes extraiters times)
568 /// extraiters -= 1 // Omitted if unroll factor is 2.
569 /// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
570 /// EpilExit:
571 
573  Loop *L, unsigned Count, bool AllowExpensiveTripCount,
574  bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,
576  const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop) {
577  LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
578  LLVM_DEBUG(L->dump());
579  LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
580  : dbgs() << "Using prolog remainder.\n");
581 
582  // Make sure the loop is in canonical form.
583  if (!L->isLoopSimplifyForm()) {
584  LLVM_DEBUG(dbgs() << "Not in simplify form!\n");
585  return false;
586  }
587 
588  // Guaranteed by LoopSimplifyForm.
589  BasicBlock *Latch = L->getLoopLatch();
590  BasicBlock *Header = L->getHeader();
591 
592  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
593 
594  if (!LatchBR || LatchBR->isUnconditional()) {
595  // The loop-rotate pass can be helpful to avoid this in many cases.
596  LLVM_DEBUG(
597  dbgs()
598  << "Loop latch not terminated by a conditional branch.\n");
599  return false;
600  }
601 
602  unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;
603  BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
604 
605  if (L->contains(LatchExit)) {
606  // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
607  // targets of the Latch be an exit block out of the loop.
608  LLVM_DEBUG(
609  dbgs()
610  << "One of the loop latch successors must be the exit block.\n");
611  return false;
612  }
613 
614  // These are exit blocks other than the target of the latch exiting block.
615  SmallVector<BasicBlock *, 4> OtherExits;
616  L->getUniqueNonLatchExitBlocks(OtherExits);
617  bool isMultiExitUnrollingEnabled =
618  canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA,
619  UseEpilogRemainder) &&
620  canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
621  UseEpilogRemainder);
622  // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
623  if (!isMultiExitUnrollingEnabled &&
624  (!L->getExitingBlock() || OtherExits.size())) {
625  LLVM_DEBUG(
626  dbgs()
627  << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
628  "enabled!\n");
629  return false;
630  }
631  // Use Scalar Evolution to compute the trip count. This allows more loops to
632  // be unrolled than relying on induction var simplification.
633  if (!SE)
634  return false;
635 
636  // Only unroll loops with a computable trip count, and the trip count needs
637  // to be an int value (allowing a pointer type is a TODO item).
638  // We calculate the backedge count by using getExitCount on the Latch block,
639  // which is proven to be the only exiting block in this loop. This is same as
640  // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
641  // exiting blocks).
642  const SCEV *BECountSC = SE->getExitCount(L, Latch);
643  if (isa<SCEVCouldNotCompute>(BECountSC) ||
644  !BECountSC->getType()->isIntegerTy()) {
645  LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");
646  return false;
647  }
648 
649  unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
650 
651  // Add 1 since the backedge count doesn't include the first loop iteration.
652  const SCEV *TripCountSC =
653  SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
654  if (isa<SCEVCouldNotCompute>(TripCountSC)) {
655  LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
656  return false;
657  }
658 
659  BasicBlock *PreHeader = L->getLoopPreheader();
660  BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
661  const DataLayout &DL = Header->getModule()->getDataLayout();
662  SCEVExpander Expander(*SE, DL, "loop-unroll");
663  if (!AllowExpensiveTripCount &&
664  Expander.isHighCostExpansion(TripCountSC, L, SCEVCheapExpansionBudget,
665  TTI, PreHeaderBR)) {
666  LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
667  return false;
668  }
669 
670  // This constraint lets us deal with an overflowing trip count easily; see the
671  // comment on ModVal below.
672  if (Log2_32(Count) > BEWidth) {
673  LLVM_DEBUG(
674  dbgs()
675  << "Count failed constraint on overflow trip count calculation.\n");
676  return false;
677  }
678 
679  // Loop structure is the following:
680  //
681  // PreHeader
682  // Header
683  // ...
684  // Latch
685  // LatchExit
686 
687  BasicBlock *NewPreHeader;
688  BasicBlock *NewExit = nullptr;
689  BasicBlock *PrologExit = nullptr;
690  BasicBlock *EpilogPreHeader = nullptr;
691  BasicBlock *PrologPreHeader = nullptr;
692 
693  if (UseEpilogRemainder) {
694  // If epilog remainder
695  // Split PreHeader to insert a branch around loop for unrolling.
696  NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
697  NewPreHeader->setName(PreHeader->getName() + ".new");
698  // Split LatchExit to create phi nodes from branch above.
699  SmallVector<BasicBlock*, 4> Preds(predecessors(LatchExit));
700  NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa", DT, LI,
701  nullptr, PreserveLCSSA);
702  // NewExit gets its DebugLoc from LatchExit, which is not part of the
703  // original Loop.
704  // Fix this by setting Loop's DebugLoc to NewExit.
705  auto *NewExitTerminator = NewExit->getTerminator();
706  NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
707  // Split NewExit to insert epilog remainder loop.
708  EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);
709  EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
710  } else {
711  // If prolog remainder
712  // Split the original preheader twice to insert prolog remainder loop
713  PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
714  PrologPreHeader->setName(Header->getName() + ".prol.preheader");
715  PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
716  DT, LI);
717  PrologExit->setName(Header->getName() + ".prol.loopexit");
718  // Split PrologExit to get NewPreHeader.
719  NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
720  NewPreHeader->setName(PreHeader->getName() + ".new");
721  }
722  // Loop structure should be the following:
723  // Epilog Prolog
724  //
725  // PreHeader PreHeader
726  // *NewPreHeader *PrologPreHeader
727  // Header *PrologExit
728  // ... *NewPreHeader
729  // Latch Header
730  // *NewExit ...
731  // *EpilogPreHeader Latch
732  // LatchExit LatchExit
733 
734  // Calculate conditions for branch around loop for unrolling
735  // in epilog case and around prolog remainder loop in prolog case.
736  // Compute the number of extra iterations required, which is:
737  // extra iterations = run-time trip count % loop unroll factor
738  PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
739  Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
740  PreHeaderBR);
741  Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
742  PreHeaderBR);
743  IRBuilder<> B(PreHeaderBR);
744  Value *ModVal;
745  // Calculate ModVal = (BECount + 1) % Count.
746  // Note that TripCount is BECount + 1.
747  if (isPowerOf2_32(Count)) {
748  // When Count is power of 2 we don't BECount for epilog case, however we'll
749  // need it for a branch around unrolling loop for prolog case.
750  ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
751  // 1. There are no iterations to be run in the prolog/epilog loop.
752  // OR
753  // 2. The addition computing TripCount overflowed.
754  //
755  // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
756  // the number of iterations that remain to be run in the original loop is a
757  // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
758  // explicitly check this above).
759  } else {
760  // As (BECount + 1) can potentially unsigned overflow we count
761  // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
762  Value *ModValTmp = B.CreateURem(BECount,
763  ConstantInt::get(BECount->getType(),
764  Count));
765  Value *ModValAdd = B.CreateAdd(ModValTmp,
766  ConstantInt::get(ModValTmp->getType(), 1));
767  // At that point (BECount % Count) + 1 could be equal to Count.
768  // To handle this case we need to take mod by Count one more time.
769  ModVal = B.CreateURem(ModValAdd,
770  ConstantInt::get(BECount->getType(), Count),
771  "xtraiter");
772  }
773  Value *BranchVal =
774  UseEpilogRemainder ? B.CreateICmpULT(BECount,
775  ConstantInt::get(BECount->getType(),
776  Count - 1)) :
777  B.CreateIsNotNull(ModVal, "lcmp.mod");
778  BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
779  BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
780  // Branch to either remainder (extra iterations) loop or unrolling loop.
781  B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
782  PreHeaderBR->eraseFromParent();
783  if (DT) {
784  if (UseEpilogRemainder)
785  DT->changeImmediateDominator(NewExit, PreHeader);
786  else
787  DT->changeImmediateDominator(PrologExit, PreHeader);
788  }
789  Function *F = Header->getParent();
790  // Get an ordered list of blocks in the loop to help with the ordering of the
791  // cloned blocks in the prolog/epilog code
792  LoopBlocksDFS LoopBlocks(L);
793  LoopBlocks.perform(LI);
794 
795  //
796  // For each extra loop iteration, create a copy of the loop's basic blocks
797  // and generate a condition that branches to the copy depending on the
798  // number of 'left over' iterations.
799  //
800  std::vector<BasicBlock *> NewBlocks;
801  ValueToValueMapTy VMap;
802 
803  // For unroll factor 2 remainder loop will have 1 iterations.
804  // Do not create 1 iteration loop.
805  bool CreateRemainderLoop = (Count != 2);
806 
807  // Clone all the basic blocks in the loop. If Count is 2, we don't clone
808  // the loop, otherwise we create a cloned loop to execute the extra
809  // iterations. This function adds the appropriate CFG connections.
810  BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
811  BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
812  Loop *remainderLoop = CloneLoopBlocks(
813  L, ModVal, CreateRemainderLoop, UseEpilogRemainder, UnrollRemainder,
814  InsertTop, InsertBot,
815  NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
816 
817  // Assign the maximum possible trip count as the back edge weight for the
818  // remainder loop if the original loop comes with a branch weight.
819  if (remainderLoop && !UnrollRemainder)
820  updateLatchBranchWeightsForRemainderLoop(L, remainderLoop, Count);
821 
822  // Insert the cloned blocks into the function.
823  F->getBasicBlockList().splice(InsertBot->getIterator(),
824  F->getBasicBlockList(),
825  NewBlocks[0]->getIterator(),
826  F->end());
827 
828  // Now the loop blocks are cloned and the other exiting blocks from the
829  // remainder are connected to the original Loop's exit blocks. The remaining
830  // work is to update the phi nodes in the original loop, and take in the
831  // values from the cloned region.
832  for (auto *BB : OtherExits) {
833  for (auto &II : *BB) {
834 
835  // Given we preserve LCSSA form, we know that the values used outside the
836  // loop will be used through these phi nodes at the exit blocks that are
837  // transformed below.
838  if (!isa<PHINode>(II))
839  break;
840  PHINode *Phi = cast<PHINode>(&II);
841  unsigned oldNumOperands = Phi->getNumIncomingValues();
842  // Add the incoming values from the remainder code to the end of the phi
843  // node.
844  for (unsigned i =0; i < oldNumOperands; i++){
845  Value *newVal = VMap.lookup(Phi->getIncomingValue(i));
846  // newVal can be a constant or derived from values outside the loop, and
847  // hence need not have a VMap value. Also, since lookup already generated
848  // a default "null" VMap entry for this value, we need to populate that
849  // VMap entry correctly, with the mapped entry being itself.
850  if (!newVal) {
851  newVal = Phi->getIncomingValue(i);
852  VMap[Phi->getIncomingValue(i)] = Phi->getIncomingValue(i);
853  }
854  Phi->addIncoming(newVal,
855  cast<BasicBlock>(VMap[Phi->getIncomingBlock(i)]));
856  }
857  }
858 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
859  for (BasicBlock *SuccBB : successors(BB)) {
860  assert(!(any_of(OtherExits,
861  [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||
862  SuccBB == LatchExit) &&
863  "Breaks the definition of dedicated exits!");
864  }
865 #endif
866  }
867 
868  // Update the immediate dominator of the exit blocks and blocks that are
869  // reachable from the exit blocks. This is needed because we now have paths
870  // from both the original loop and the remainder code reaching the exit
871  // blocks. While the IDom of these exit blocks were from the original loop,
872  // now the IDom is the preheader (which decides whether the original loop or
873  // remainder code should run).
874  if (DT && !L->getExitingBlock()) {
875  SmallVector<BasicBlock *, 16> ChildrenToUpdate;
876  // NB! We have to examine the dom children of all loop blocks, not just
877  // those which are the IDom of the exit blocks. This is because blocks
878  // reachable from the exit blocks can have their IDom as the nearest common
879  // dominator of the exit blocks.
880  for (auto *BB : L->blocks()) {
881  auto *DomNodeBB = DT->getNode(BB);
882  for (auto *DomChild : DomNodeBB->children()) {
883  auto *DomChildBB = DomChild->getBlock();
884  if (!L->contains(LI->getLoopFor(DomChildBB)))
885  ChildrenToUpdate.push_back(DomChildBB);
886  }
887  }
888  for (auto *BB : ChildrenToUpdate)
889  DT->changeImmediateDominator(BB, PreHeader);
890  }
891 
892  // Loop structure should be the following:
893  // Epilog Prolog
894  //
895  // PreHeader PreHeader
896  // NewPreHeader PrologPreHeader
897  // Header PrologHeader
898  // ... ...
899  // Latch PrologLatch
900  // NewExit PrologExit
901  // EpilogPreHeader NewPreHeader
902  // EpilogHeader Header
903  // ... ...
904  // EpilogLatch Latch
905  // LatchExit LatchExit
906 
907  // Rewrite the cloned instruction operands to use the values created when the
908  // clone is created.
909  for (BasicBlock *BB : NewBlocks) {
910  for (Instruction &I : *BB) {
911  RemapInstruction(&I, VMap,
913  }
914  }
915 
916  if (UseEpilogRemainder) {
917  // Connect the epilog code to the original loop and update the
918  // PHI functions.
919  ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
920  EpilogPreHeader, NewPreHeader, VMap, DT, LI,
921  PreserveLCSSA);
922 
923  // Update counter in loop for unrolling.
924  // I should be multiply of Count.
925  IRBuilder<> B2(NewPreHeader->getTerminator());
926  Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
927  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
928  B2.SetInsertPoint(LatchBR);
929  PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
930  Header->getFirstNonPHI());
931  Value *IdxSub =
932  B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
933  NewIdx->getName() + ".nsub");
934  Value *IdxCmp;
935  if (LatchBR->getSuccessor(0) == Header)
936  IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
937  else
938  IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
939  NewIdx->addIncoming(TestVal, NewPreHeader);
940  NewIdx->addIncoming(IdxSub, Latch);
941  LatchBR->setCondition(IdxCmp);
942  } else {
943  // Connect the prolog code to the original loop and update the
944  // PHI functions.
945  ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
946  NewPreHeader, VMap, DT, LI, PreserveLCSSA);
947  }
948 
949  // If this loop is nested, then the loop unroller changes the code in the any
950  // of its parent loops, so the Scalar Evolution pass needs to be run again.
951  SE->forgetTopmostLoop(L);
952 
953  // Verify that the Dom Tree is correct.
954 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
955  if (DT)
957 #endif
958 
959  // Canonicalize to LoopSimplifyForm both original and remainder loops. We
960  // cannot rely on the LoopUnrollPass to do this because it only does
961  // canonicalization for parent/subloops and not the sibling loops.
962  if (OtherExits.size() > 0) {
963  // Generate dedicated exit blocks for the original loop, to preserve
964  // LoopSimplifyForm.
965  formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);
966  // Generate dedicated exit blocks for the remainder loop if one exists, to
967  // preserve LoopSimplifyForm.
968  if (remainderLoop)
969  formDedicatedExitBlocks(remainderLoop, DT, LI, nullptr, PreserveLCSSA);
970  }
971 
972  auto UnrollResult = LoopUnrollResult::Unmodified;
973  if (remainderLoop && UnrollRemainder) {
974  LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
975  UnrollResult =
976  UnrollLoop(remainderLoop,
977  {/*Count*/ Count - 1, /*TripCount*/ Count - 1,
978  /*Force*/ false, /*AllowRuntime*/ false,
979  /*AllowExpensiveTripCount*/ false, /*PreserveCondBr*/ true,
980  /*PreserveOnlyFirst*/ false, /*TripMultiple*/ 1,
981  /*PeelCount*/ 0, /*UnrollRemainder*/ false, ForgetAllSCEV},
982  LI, SE, DT, AC, TTI, /*ORE*/ nullptr, PreserveLCSSA);
983  }
984 
985  if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)
986  *ResultLoop = remainderLoop;
987  NumRuntimeUnrolled++;
988  return true;
989 }
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 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:111
TargetTransformInfo TTI
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:215
const SCEV * getConstant(ConstantInt *V)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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.
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
The main scalar evolution driver.
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
Definition: LoopInfoImpl.h:128
This file contains the declarations for metadata subclasses.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
A cache of @llvm.assume calls within a function.
static bool canSafelyUnrollMultiExitLoop(Loop *L, BasicBlock *LatchExit, bool PreserveLCSSA, bool UseEpilogRemainder)
Returns true if we can safely unroll a multi-exit/exiting loop.
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:870
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:148
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
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:144
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:397
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:963
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:202
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:367
RPOIterator endRPO() const
Definition: LoopIterator.h:140
BlockT * getHeader() const
Definition: LoopInfo.h:104
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
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.
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:520
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:165
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1129
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:68
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
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
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:212
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:362
void dump() const
Definition: LoopInfo.cpp:670
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:492
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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's...
DomTreeNodeBase * getIDom() const
Value * getIncomingValueForBlock(const BasicBlock *BB) const
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop's loop id metadata.
Definition: LoopInfo.cpp:532
int getNumOccurrences() const
Definition: CommandLine.h:388
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:1505
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
self_iterator getIterator()
Definition: ilist_node.h:81
assume Assume Builder
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1742
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:122
Iterator for intrusive lists based on ilist_node.
static void updateLatchBranchWeightsForRemainderLoop(Loop *OrigLoop, Loop *RemainderLoop, uint64_t UnrollFactor)
Type * getType() const
Return the LLVM type of this SCEV expression.
void setIncomingBlock(unsigned i, BasicBlock *BB)
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, 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...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1116
Module.h This file contains the declarations for the Module class.
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:257
constexpr bool hasValue() const
Definition: Optional.h:263
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:867
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:125
unsigned getNumIncomingValues() const
Return the number of incoming edges.
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:333
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:597
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:137
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:251
This class uses information about analyze scalars to rewrite expressions in canonical form.
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:284
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:90
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:471
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:496
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:365
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
cl::opt< unsigned > SCEVCheapExpansionBudget
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:295
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:107
#define I(x, y, z)
Definition: MD5.cpp:59
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
bool isUnconditional() const
void setCondition(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
LLVM Value Representation.
Definition: Value.h:75
succ_range successors(Instruction *I)
Definition: CFG.h:260
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
The loop was not modified.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)
Return true for expressions that can't be evaluated at runtime within given Budget.
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:33
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.
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
Definition: Metadata.cpp:1377
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
bool erase(const KeyT &Val)
Definition: ValueMap.h:191
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
void forgetTopmostLoop(const Loop *L)