LLVM  14.0.0git
LoopRotationUtils.cpp
Go to the documentation of this file.
1 //===----------------- LoopRotationUtils.cpp -----------------------------===//
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 provides utilities to convert a loop into a loop with bottom test.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Analysis/LoopPass.h"
28 #include "llvm/IR/CFG.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Module.h"
35 #include "llvm/Support/Debug.h"
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "loop-rotate"
46 
47 STATISTIC(NumNotRotatedDueToHeaderSize,
48  "Number of loops not rotated due to the header size");
49 STATISTIC(NumInstrsHoisted,
50  "Number of instructions hoisted into loop preheader");
51 STATISTIC(NumInstrsDuplicated,
52  "Number of instructions cloned into loop preheader");
53 STATISTIC(NumRotated, "Number of loops rotated");
54 
55 static cl::opt<bool>
56  MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden,
57  cl::desc("Allow loop rotation multiple times in order to reach "
58  "a better latch exit"));
59 
60 namespace {
61 /// A simple loop rotation transformation.
62 class LoopRotate {
63  const unsigned MaxHeaderSize;
64  LoopInfo *LI;
65  const TargetTransformInfo *TTI;
66  AssumptionCache *AC;
67  DominatorTree *DT;
68  ScalarEvolution *SE;
69  MemorySSAUpdater *MSSAU;
70  const SimplifyQuery &SQ;
71  bool RotationOnly;
72  bool IsUtilMode;
73  bool PrepareForLTO;
74 
75 public:
76  LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
79  const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode,
80  bool PrepareForLTO)
81  : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),
82  MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),
83  IsUtilMode(IsUtilMode), PrepareForLTO(PrepareForLTO) {}
84  bool processLoop(Loop *L);
85 
86 private:
87  bool rotateLoop(Loop *L, bool SimplifiedLatch);
88  bool simplifyLoopLatch(Loop *L);
89 };
90 } // end anonymous namespace
91 
92 /// Insert (K, V) pair into the ValueToValueMap, and verify the key did not
93 /// previously exist in the map, and the value was inserted.
95  bool Inserted = VM.insert({K, V}).second;
96  assert(Inserted);
97  (void)Inserted;
98 }
99 /// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
100 /// old header into the preheader. If there were uses of the values produced by
101 /// these instruction that were outside of the loop, we have to insert PHI nodes
102 /// to merge the two values. Do this now.
104  BasicBlock *OrigPreheader,
106  ScalarEvolution *SE,
107  SmallVectorImpl<PHINode*> *InsertedPHIs) {
108  // Remove PHI node entries that are no longer live.
109  BasicBlock::iterator I, E = OrigHeader->end();
110  for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
111  PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
112 
113  // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
114  // as necessary.
115  SSAUpdater SSA(InsertedPHIs);
116  for (I = OrigHeader->begin(); I != E; ++I) {
117  Value *OrigHeaderVal = &*I;
118 
119  // If there are no uses of the value (e.g. because it returns void), there
120  // is nothing to rewrite.
121  if (OrigHeaderVal->use_empty())
122  continue;
123 
124  Value *OrigPreHeaderVal = ValueMap.lookup(OrigHeaderVal);
125 
126  // The value now exits in two versions: the initial value in the preheader
127  // and the loop "next" value in the original header.
128  SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
129  // Force re-computation of OrigHeaderVal, as some users now need to use the
130  // new PHI node.
131  if (SE)
132  SE->forgetValue(OrigHeaderVal);
133  SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
134  SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);
135 
136  // Visit each use of the OrigHeader instruction.
137  for (Use &U : llvm::make_early_inc_range(OrigHeaderVal->uses())) {
138  // SSAUpdater can't handle a non-PHI use in the same block as an
139  // earlier def. We can easily handle those cases manually.
140  Instruction *UserInst = cast<Instruction>(U.getUser());
141  if (!isa<PHINode>(UserInst)) {
142  BasicBlock *UserBB = UserInst->getParent();
143 
144  // The original users in the OrigHeader are already using the
145  // original definitions.
146  if (UserBB == OrigHeader)
147  continue;
148 
149  // Users in the OrigPreHeader need to use the value to which the
150  // original definitions are mapped.
151  if (UserBB == OrigPreheader) {
152  U = OrigPreHeaderVal;
153  continue;
154  }
155  }
156 
157  // Anything else can be handled by SSAUpdater.
158  SSA.RewriteUse(U);
159  }
160 
161  // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug
162  // intrinsics.
164  llvm::findDbgValues(DbgValues, OrigHeaderVal);
165  for (auto &DbgValue : DbgValues) {
166  // The original users in the OrigHeader are already using the original
167  // definitions.
168  BasicBlock *UserBB = DbgValue->getParent();
169  if (UserBB == OrigHeader)
170  continue;
171 
172  // Users in the OrigPreHeader need to use the value to which the
173  // original definitions are mapped and anything else can be handled by
174  // the SSAUpdater. To avoid adding PHINodes, check if the value is
175  // available in UserBB, if not substitute undef.
176  Value *NewVal;
177  if (UserBB == OrigPreheader)
178  NewVal = OrigPreHeaderVal;
179  else if (SSA.HasValueForBlock(UserBB))
180  NewVal = SSA.GetValueInMiddleOfBlock(UserBB);
181  else
182  NewVal = UndefValue::get(OrigHeaderVal->getType());
183  DbgValue->replaceVariableLocationOp(OrigHeaderVal, NewVal);
184  }
185  }
186 }
187 
188 // Assuming both header and latch are exiting, look for a phi which is only
189 // used outside the loop (via a LCSSA phi) in the exit from the header.
190 // This means that rotating the loop can remove the phi.
192  BasicBlock *Header = L->getHeader();
193  BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator());
194  assert(BI && BI->isConditional() && "need header with conditional exit");
195  BasicBlock *HeaderExit = BI->getSuccessor(0);
196  if (L->contains(HeaderExit))
197  HeaderExit = BI->getSuccessor(1);
198 
199  for (auto &Phi : Header->phis()) {
200  // Look for uses of this phi in the loop/via exits other than the header.
201  if (llvm::any_of(Phi.users(), [HeaderExit](const User *U) {
202  return cast<Instruction>(U)->getParent() != HeaderExit;
203  }))
204  continue;
205  return true;
206  }
207  return false;
208 }
209 
210 // Check that latch exit is deoptimizing (which means - very unlikely to happen)
211 // and there is another exit from the loop which is non-deoptimizing.
212 // If we rotate latch to that exit our loop has a better chance of being fully
213 // canonical.
214 //
215 // It can give false positives in some rare cases.
217  BasicBlock *Latch = L->getLoopLatch();
218  assert(Latch && "need latch");
219  BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
220  // Need normal exiting latch.
221  if (!BI || !BI->isConditional())
222  return false;
223 
224  BasicBlock *Exit = BI->getSuccessor(1);
225  if (L->contains(Exit))
226  Exit = BI->getSuccessor(0);
227 
228  // Latch exit is non-deoptimizing, no need to rotate.
229  if (!Exit->getPostdominatingDeoptimizeCall())
230  return false;
231 
233  L->getUniqueExitBlocks(Exits);
234  if (!Exits.empty()) {
235  // There is at least one non-deoptimizing exit.
236  //
237  // Note, that BasicBlock::getPostdominatingDeoptimizeCall is not exact,
238  // as it can conservatively return false for deoptimizing exits with
239  // complex enough control flow down to deoptimize call.
240  //
241  // That means here we can report success for a case where
242  // all exits are deoptimizing but one of them has complex enough
243  // control flow (e.g. with loops).
244  //
245  // That should be a very rare case and false positives for this function
246  // have compile-time effect only.
247  return any_of(Exits, [](const BasicBlock *BB) {
248  return !BB->getPostdominatingDeoptimizeCall();
249  });
250  }
251  return false;
252 }
253 
254 /// Rotate loop LP. Return true if the loop is rotated.
255 ///
256 /// \param SimplifiedLatch is true if the latch was just folded into the final
257 /// loop exit. In this case we may want to rotate even though the new latch is
258 /// now an exiting branch. This rotation would have happened had the latch not
259 /// been simplified. However, if SimplifiedLatch is false, then we avoid
260 /// rotating loops in which the latch exits to avoid excessive or endless
261 /// rotation. LoopRotate should be repeatable and converge to a canonical
262 /// form. This property is satisfied because simplifying the loop latch can only
263 /// happen once across multiple invocations of the LoopRotate pass.
264 ///
265 /// If -loop-rotate-multi is enabled we can do multiple rotations in one go
266 /// so to reach a suitable (non-deoptimizing) exit.
267 bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
268  // If the loop has only one block then there is not much to rotate.
269  if (L->getBlocks().size() == 1)
270  return false;
271 
272  bool Rotated = false;
273  do {
274  BasicBlock *OrigHeader = L->getHeader();
275  BasicBlock *OrigLatch = L->getLoopLatch();
276 
277  BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
278  if (!BI || BI->isUnconditional())
279  return Rotated;
280 
281  // If the loop header is not one of the loop exiting blocks then
282  // either this loop is already rotated or it is not
283  // suitable for loop rotation transformations.
284  if (!L->isLoopExiting(OrigHeader))
285  return Rotated;
286 
287  // If the loop latch already contains a branch that leaves the loop then the
288  // loop is already rotated.
289  if (!OrigLatch)
290  return Rotated;
291 
292  // Rotate if either the loop latch does *not* exit the loop, or if the loop
293  // latch was just simplified. Or if we think it will be profitable.
294  if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode == false &&
297  return Rotated;
298 
299  // Check size of original header and reject loop if it is very big or we can't
300  // duplicate blocks inside it.
301  {
303  CodeMetrics::collectEphemeralValues(L, AC, EphValues);
304 
306  Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues, PrepareForLTO);
307  if (Metrics.notDuplicatable) {
308  LLVM_DEBUG(
309  dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable"
310  << " instructions: ";
311  L->dump());
312  return Rotated;
313  }
314  if (Metrics.convergent) {
315  LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "
316  "instructions: ";
317  L->dump());
318  return Rotated;
319  }
320  if (Metrics.NumInsts > MaxHeaderSize) {
321  LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains "
322  << Metrics.NumInsts
323  << " instructions, which is more than the threshold ("
324  << MaxHeaderSize << " instructions): ";
325  L->dump());
326  ++NumNotRotatedDueToHeaderSize;
327  return Rotated;
328  }
329 
330  // When preparing for LTO, avoid rotating loops with calls that could be
331  // inlined during the LTO stage.
332  if (PrepareForLTO && Metrics.NumInlineCandidates > 0)
333  return Rotated;
334  }
335 
336  // Now, this loop is suitable for rotation.
337  BasicBlock *OrigPreheader = L->getLoopPreheader();
338 
339  // If the loop could not be converted to canonical form, it must have an
340  // indirectbr in it, just give up.
341  if (!OrigPreheader || !L->hasDedicatedExits())
342  return Rotated;
343 
344  // Anything ScalarEvolution may know about this loop or the PHI nodes
345  // in its header will soon be invalidated. We should also invalidate
346  // all outer loops because insertion and deletion of blocks that happens
347  // during the rotation may violate invariants related to backedge taken
348  // infos in them.
349  if (SE)
350  SE->forgetTopmostLoop(L);
351 
352  LLVM_DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
353  if (MSSAU && VerifyMemorySSA)
354  MSSAU->getMemorySSA()->verifyMemorySSA();
355 
356  // Find new Loop header. NewHeader is a Header's one and only successor
357  // that is inside loop. Header's other successor is outside the
358  // loop. Otherwise loop is not suitable for rotation.
359  BasicBlock *Exit = BI->getSuccessor(0);
360  BasicBlock *NewHeader = BI->getSuccessor(1);
361  if (L->contains(Exit))
362  std::swap(Exit, NewHeader);
363  assert(NewHeader && "Unable to determine new loop header");
364  assert(L->contains(NewHeader) && !L->contains(Exit) &&
365  "Unable to determine loop header and exit blocks");
366 
367  // This code assumes that the new header has exactly one predecessor.
368  // Remove any single-entry PHI nodes in it.
369  assert(NewHeader->getSinglePredecessor() &&
370  "New header doesn't have one pred!");
371  FoldSingleEntryPHINodes(NewHeader);
372 
373  // Begin by walking OrigHeader and populating ValueMap with an entry for
374  // each Instruction.
375  BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
376  ValueToValueMapTy ValueMap, ValueMapMSSA;
377 
378  // For PHI nodes, the value available in OldPreHeader is just the
379  // incoming value from OldPreHeader.
380  for (; PHINode *PN = dyn_cast<PHINode>(I); ++I)
382  PN->getIncomingValueForBlock(OrigPreheader));
383 
384  // For the rest of the instructions, either hoist to the OrigPreheader if
385  // possible or create a clone in the OldPreHeader if not.
386  Instruction *LoopEntryBranch = OrigPreheader->getTerminator();
387 
388  // Record all debug intrinsics preceding LoopEntryBranch to avoid
389  // duplication.
390  using DbgIntrinsicHash =
391  std::pair<std::pair<hash_code, DILocalVariable *>, DIExpression *>;
392  auto makeHash = [](DbgVariableIntrinsic *D) -> DbgIntrinsicHash {
393  auto VarLocOps = D->location_ops();
394  return {{hash_combine_range(VarLocOps.begin(), VarLocOps.end()),
395  D->getVariable()},
396  D->getExpression()};
397  };
399  for (Instruction &I : llvm::drop_begin(llvm::reverse(*OrigPreheader))) {
400  if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I))
401  DbgIntrinsics.insert(makeHash(DII));
402  else
403  break;
404  }
405 
406  // Remember the local noalias scope declarations in the header. After the
407  // rotation, they must be duplicated and the scope must be cloned. This
408  // avoids unwanted interaction across iterations.
409  SmallVector<NoAliasScopeDeclInst *, 6> NoAliasDeclInstructions;
410  for (Instruction &I : *OrigHeader)
411  if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I))
412  NoAliasDeclInstructions.push_back(Decl);
413 
414  while (I != E) {
415  Instruction *Inst = &*I++;
416 
417  // If the instruction's operands are invariant and it doesn't read or write
418  // memory, then it is safe to hoist. Doing this doesn't change the order of
419  // execution in the preheader, but does prevent the instruction from
420  // executing in each iteration of the loop. This means it is safe to hoist
421  // something that might trap, but isn't safe to hoist something that reads
422  // memory (without proving that the loop doesn't write).
423  if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&
424  !Inst->mayWriteToMemory() && !Inst->isTerminator() &&
425  !isa<DbgInfoIntrinsic>(Inst) && !isa<AllocaInst>(Inst)) {
426  Inst->moveBefore(LoopEntryBranch);
427  ++NumInstrsHoisted;
428  continue;
429  }
430 
431  // Otherwise, create a duplicate of the instruction.
432  Instruction *C = Inst->clone();
433  ++NumInstrsDuplicated;
434 
435  // Eagerly remap the operands of the instruction.
438 
439  // Avoid inserting the same intrinsic twice.
440  if (auto *DII = dyn_cast<DbgVariableIntrinsic>(C))
441  if (DbgIntrinsics.count(makeHash(DII))) {
442  C->deleteValue();
443  continue;
444  }
445 
446  // With the operands remapped, see if the instruction constant folds or is
447  // otherwise simplifyable. This commonly occurs because the entry from PHI
448  // nodes allows icmps and other instructions to fold.
449  Value *V = SimplifyInstruction(C, SQ);
450  if (V && LI->replacementPreservesLCSSAForm(C, V)) {
451  // If so, then delete the temporary instruction and stick the folded value
452  // in the map.
454  if (!C->mayHaveSideEffects()) {
455  C->deleteValue();
456  C = nullptr;
457  }
458  } else {
460  }
461  if (C) {
462  // Otherwise, stick the new instruction into the new block!
463  C->setName(Inst->getName());
464  C->insertBefore(LoopEntryBranch);
465 
466  if (auto *II = dyn_cast<AssumeInst>(C))
467  AC->registerAssumption(II);
468  // MemorySSA cares whether the cloned instruction was inserted or not, and
469  // not whether it can be remapped to a simplified value.
470  if (MSSAU)
471  InsertNewValueIntoMap(ValueMapMSSA, Inst, C);
472  }
473  }
474 
475  if (!NoAliasDeclInstructions.empty()) {
476  // There are noalias scope declarations:
477  // (general):
478  // Original: OrigPre { OrigHeader NewHeader ... Latch }
479  // after: (OrigPre+OrigHeader') { NewHeader ... Latch OrigHeader }
480  //
481  // with D: llvm.experimental.noalias.scope.decl,
482  // U: !noalias or !alias.scope depending on D
483  // ... { D U1 U2 } can transform into:
484  // (0) : ... { D U1 U2 } // no relevant rotation for this part
485  // (1) : ... D' { U1 U2 D } // D is part of OrigHeader
486  // (2) : ... D' U1' { U2 D U1 } // D, U1 are part of OrigHeader
487  //
488  // We now want to transform:
489  // (1) -> : ... D' { D U1 U2 D'' }
490  // (2) -> : ... D' U1' { D U2 D'' U1'' }
491  // D: original llvm.experimental.noalias.scope.decl
492  // D', U1': duplicate with replaced scopes
493  // D'', U1'': different duplicate with replaced scopes
494  // This ensures a safe fallback to 'may_alias' introduced by the rotate,
495  // as U1'' and U1' scopes will not be compatible wrt to the local restrict
496 
497  // Clone the llvm.experimental.noalias.decl again for the NewHeader.
498  Instruction *NewHeaderInsertionPoint = &(*NewHeader->getFirstNonPHI());
499  for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions) {
500  LLVM_DEBUG(dbgs() << " Cloning llvm.experimental.noalias.scope.decl:"
501  << *NAD << "\n");
502  Instruction *NewNAD = NAD->clone();
503  NewNAD->insertBefore(NewHeaderInsertionPoint);
504  }
505 
506  // Scopes must now be duplicated, once for OrigHeader and once for
507  // OrigPreHeader'.
508  {
509  auto &Context = NewHeader->getContext();
510 
511  SmallVector<MDNode *, 8> NoAliasDeclScopes;
512  for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions)
513  NoAliasDeclScopes.push_back(NAD->getScopeList());
514 
515  LLVM_DEBUG(dbgs() << " Updating OrigHeader scopes\n");
516  cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, {OrigHeader}, Context,
517  "h.rot");
518  LLVM_DEBUG(OrigHeader->dump());
519 
520  // Keep the compile time impact low by only adapting the inserted block
521  // of instructions in the OrigPreHeader. This might result in slightly
522  // more aliasing between these instructions and those that were already
523  // present, but it will be much faster when the original PreHeader is
524  // large.
525  LLVM_DEBUG(dbgs() << " Updating part of OrigPreheader scopes\n");
526  auto *FirstDecl =
527  cast<Instruction>(ValueMap[*NoAliasDeclInstructions.begin()]);
528  auto *LastInst = &OrigPreheader->back();
529  cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, FirstDecl, LastInst,
530  Context, "pre.rot");
531  LLVM_DEBUG(OrigPreheader->dump());
532 
533  LLVM_DEBUG(dbgs() << " Updated NewHeader:\n");
534  LLVM_DEBUG(NewHeader->dump());
535  }
536  }
537 
538  // Along with all the other instructions, we just cloned OrigHeader's
539  // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's
540  // successors by duplicating their incoming values for OrigHeader.
541  for (BasicBlock *SuccBB : successors(OrigHeader))
542  for (BasicBlock::iterator BI = SuccBB->begin();
543  PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
544  PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
545 
546  // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
547  // OrigPreHeader's old terminator (the original branch into the loop), and
548  // remove the corresponding incoming values from the PHI nodes in OrigHeader.
549  LoopEntryBranch->eraseFromParent();
550 
551  // Update MemorySSA before the rewrite call below changes the 1:1
552  // instruction:cloned_instruction_or_value mapping.
553  if (MSSAU) {
554  InsertNewValueIntoMap(ValueMapMSSA, OrigHeader, OrigPreheader);
555  MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader,
556  ValueMapMSSA);
557  }
558 
559  SmallVector<PHINode*, 2> InsertedPHIs;
560  // If there were any uses of instructions in the duplicated block outside the
561  // loop, update them, inserting PHI nodes as required
562  RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap, SE,
563  &InsertedPHIs);
564 
565  // Attach dbg.value intrinsics to the new phis if that phi uses a value that
566  // previously had debug metadata attached. This keeps the debug info
567  // up-to-date in the loop body.
568  if (!InsertedPHIs.empty())
569  insertDebugValuesForPHIs(OrigHeader, InsertedPHIs);
570 
571  // NewHeader is now the header of the loop.
572  L->moveToHeader(NewHeader);
573  assert(L->getHeader() == NewHeader && "Latch block is our new header");
574 
575  // Inform DT about changes to the CFG.
576  if (DT) {
577  // The OrigPreheader branches to the NewHeader and Exit now. Then, inform
578  // the DT about the removed edge to the OrigHeader (that got removed).
580  Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});
581  Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});
582  Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});
583 
584  if (MSSAU) {
585  MSSAU->applyUpdates(Updates, *DT, /*UpdateDT=*/true);
586  if (VerifyMemorySSA)
587  MSSAU->getMemorySSA()->verifyMemorySSA();
588  } else {
589  DT->applyUpdates(Updates);
590  }
591  }
592 
593  // At this point, we've finished our major CFG changes. As part of cloning
594  // the loop into the preheader we've simplified instructions and the
595  // duplicated conditional branch may now be branching on a constant. If it is
596  // branching on a constant and if that constant means that we enter the loop,
597  // then we fold away the cond branch to an uncond branch. This simplifies the
598  // loop in cases important for nested loops, and it also means we don't have
599  // to split as many edges.
600  BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
601  assert(PHBI->isConditional() && "Should be clone of BI condbr!");
602  if (!isa<ConstantInt>(PHBI->getCondition()) ||
603  PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) !=
604  NewHeader) {
605  // The conditional branch can't be folded, handle the general case.
606  // Split edges as necessary to preserve LoopSimplify form.
607 
608  // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
609  // thus is not a preheader anymore.
610  // Split the edge to form a real preheader.
611  BasicBlock *NewPH = SplitCriticalEdge(
612  OrigPreheader, NewHeader,
613  CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
614  NewPH->setName(NewHeader->getName() + ".lr.ph");
615 
616  // Preserve canonical loop form, which means that 'Exit' should have only
617  // one predecessor. Note that Exit could be an exit block for multiple
618  // nested loops, causing both of the edges to now be critical and need to
619  // be split.
621  bool SplitLatchEdge = false;
622  for (BasicBlock *ExitPred : ExitPreds) {
623  // We only need to split loop exit edges.
624  Loop *PredLoop = LI->getLoopFor(ExitPred);
625  if (!PredLoop || PredLoop->contains(Exit) ||
626  ExitPred->getTerminator()->isIndirectTerminator())
627  continue;
628  SplitLatchEdge |= L->getLoopLatch() == ExitPred;
629  BasicBlock *ExitSplit = SplitCriticalEdge(
630  ExitPred, Exit,
631  CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
632  ExitSplit->moveBefore(Exit);
633  }
634  assert(SplitLatchEdge &&
635  "Despite splitting all preds, failed to split latch exit?");
636  (void)SplitLatchEdge;
637  } else {
638  // We can fold the conditional branch in the preheader, this makes things
639  // simpler. The first step is to remove the extra edge to the Exit block.
640  Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);
641  BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI);
642  NewBI->setDebugLoc(PHBI->getDebugLoc());
643  PHBI->eraseFromParent();
644 
645  // With our CFG finalized, update DomTree if it is available.
646  if (DT) DT->deleteEdge(OrigPreheader, Exit);
647 
648  // Update MSSA too, if available.
649  if (MSSAU)
650  MSSAU->removeEdge(OrigPreheader, Exit);
651  }
652 
653  assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
654  assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
655 
656  if (MSSAU && VerifyMemorySSA)
657  MSSAU->getMemorySSA()->verifyMemorySSA();
658 
659  // Now that the CFG and DomTree are in a consistent state again, try to merge
660  // the OrigHeader block into OrigLatch. This will succeed if they are
661  // connected by an unconditional branch. This is just a cleanup so the
662  // emitted code isn't too gross in this common case.
664  BasicBlock *PredBB = OrigHeader->getUniquePredecessor();
665  bool DidMerge = MergeBlockIntoPredecessor(OrigHeader, &DTU, LI, MSSAU);
666  if (DidMerge)
667  RemoveRedundantDbgInstrs(PredBB);
668 
669  if (MSSAU && VerifyMemorySSA)
670  MSSAU->getMemorySSA()->verifyMemorySSA();
671 
672  LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump());
673 
674  ++NumRotated;
675 
676  Rotated = true;
677  SimplifiedLatch = false;
678 
679  // Check that new latch is a deoptimizing exit and then repeat rotation if possible.
680  // Deoptimizing latch exit is not a generally typical case, so we just loop over.
681  // TODO: if it becomes a performance bottleneck extend rotation algorithm
682  // to handle multiple rotations in one go.
684 
685 
686  return true;
687 }
688 
689 /// Determine whether the instructions in this range may be safely and cheaply
690 /// speculated. This is not an important enough situation to develop complex
691 /// heuristics. We handle a single arithmetic instruction along with any type
692 /// conversions.
694  BasicBlock::iterator End, Loop *L) {
695  bool seenIncrement = false;
696  bool MultiExitLoop = false;
697 
698  if (!L->getExitingBlock())
699  MultiExitLoop = true;
700 
701  for (BasicBlock::iterator I = Begin; I != End; ++I) {
702 
704  return false;
705 
706  if (isa<DbgInfoIntrinsic>(I))
707  continue;
708 
709  switch (I->getOpcode()) {
710  default:
711  return false;
712  case Instruction::GetElementPtr:
713  // GEPs are cheap if all indices are constant.
714  if (!cast<GEPOperator>(I)->hasAllConstantIndices())
715  return false;
716  // fall-thru to increment case
718  case Instruction::Add:
719  case Instruction::Sub:
720  case Instruction::And:
721  case Instruction::Or:
722  case Instruction::Xor:
723  case Instruction::Shl:
724  case Instruction::LShr:
725  case Instruction::AShr: {
726  Value *IVOpnd =
727  !isa<Constant>(I->getOperand(0))
728  ? I->getOperand(0)
729  : !isa<Constant>(I->getOperand(1)) ? I->getOperand(1) : nullptr;
730  if (!IVOpnd)
731  return false;
732 
733  // If increment operand is used outside of the loop, this speculation
734  // could cause extra live range interference.
735  if (MultiExitLoop) {
736  for (User *UseI : IVOpnd->users()) {
737  auto *UserInst = cast<Instruction>(UseI);
738  if (!L->contains(UserInst))
739  return false;
740  }
741  }
742 
743  if (seenIncrement)
744  return false;
745  seenIncrement = true;
746  break;
747  }
748  case Instruction::Trunc:
749  case Instruction::ZExt:
750  case Instruction::SExt:
751  // ignore type conversions
752  break;
753  }
754  }
755  return true;
756 }
757 
758 /// Fold the loop tail into the loop exit by speculating the loop tail
759 /// instructions. Typically, this is a single post-increment. In the case of a
760 /// simple 2-block loop, hoisting the increment can be much better than
761 /// duplicating the entire loop header. In the case of loops with early exits,
762 /// rotation will not work anyway, but simplifyLoopLatch will put the loop in
763 /// canonical form so downstream passes can handle it.
764 ///
765 /// I don't believe this invalidates SCEV.
766 bool LoopRotate::simplifyLoopLatch(Loop *L) {
767  BasicBlock *Latch = L->getLoopLatch();
768  if (!Latch || Latch->hasAddressTaken())
769  return false;
770 
771  BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator());
772  if (!Jmp || !Jmp->isUnconditional())
773  return false;
774 
775  BasicBlock *LastExit = Latch->getSinglePredecessor();
776  if (!LastExit || !L->isLoopExiting(LastExit))
777  return false;
778 
779  BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator());
780  if (!BI)
781  return false;
782 
783  if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L))
784  return false;
785 
786  LLVM_DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
787  << LastExit->getName() << "\n");
788 
790  MergeBlockIntoPredecessor(Latch, &DTU, LI, MSSAU, nullptr,
791  /*PredecessorWithTwoSuccessors=*/true);
792 
793  if (MSSAU && VerifyMemorySSA)
794  MSSAU->getMemorySSA()->verifyMemorySSA();
795 
796  return true;
797 }
798 
799 /// Rotate \c L, and return true if any modification was made.
800 bool LoopRotate::processLoop(Loop *L) {
801  // Save the loop metadata.
802  MDNode *LoopMD = L->getLoopID();
803 
804  bool SimplifiedLatch = false;
805 
806  // Simplify the loop latch before attempting to rotate the header
807  // upward. Rotation may not be needed if the loop tail can be folded into the
808  // loop exit.
809  if (!RotationOnly)
810  SimplifiedLatch = simplifyLoopLatch(L);
811 
812  bool MadeChange = rotateLoop(L, SimplifiedLatch);
813  assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&
814  "Loop latch should be exiting after loop-rotate.");
815 
816  // Restore the loop metadata.
817  // NB! We presume LoopRotation DOESN'T ADD its own metadata.
818  if ((MadeChange || SimplifiedLatch) && LoopMD)
819  L->setLoopID(LoopMD);
820 
821  return MadeChange || SimplifiedLatch;
822 }
823 
824 
825 /// The utility to convert a loop into a loop with bottom test.
828  ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
829  const SimplifyQuery &SQ, bool RotationOnly = true,
830  unsigned Threshold = unsigned(-1),
831  bool IsUtilMode = true, bool PrepareForLTO) {
832  LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
833  IsUtilMode, PrepareForLTO);
834  return LR.processLoop(L);
835 }
llvm::NoAliasScopeDeclInst
Definition: IntrinsicInst.h:1227
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:163
AssumptionCache.h
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:266
ValueMapper.h
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4630
IntrinsicInst.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
MemorySSAUpdater.h
shouldSpeculateInstrs
static bool shouldSpeculateInstrs(BasicBlock::iterator Begin, BasicBlock::iterator End, Loop *L)
Determine whether the instructions in this range may be safely and cheaply speculated.
Definition: LoopRotationUtils.cpp:693
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::Value::dump
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4814
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::CodeMetrics
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Definition: CodeMetrics.h:30
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:169
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
DomTreeUpdater.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
ValueTracking.h
Local.h
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:84
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
profitableToRotateLoopExitingLatch
static bool profitableToRotateLoopExitingLatch(Loop *L)
Definition: LoopRotationUtils.cpp:191
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
ScalarEvolution.h
llvm::SplitCriticalEdge
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
Definition: BreakCriticalEdges.cpp:103
Module.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:359
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:268
llvm::DIExpression
DWARF expression.
Definition: DebugInfoMetadata.h:2596
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
BasicAliasAnalysis.h
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
MultiRotate
static cl::opt< bool > MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden, cl::desc("Allow loop rotation multiple times in order to reach " "a better latch exit"))
Context
ManagedStatic< detail::RecordContext > Context
Definition: Record.cpp:96
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
CodeMetrics.h
llvm::RemapInstruction
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:254
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::CriticalEdgeSplittingOptions
Option class for critical edge splitting.
Definition: BasicBlockUtils.h:143
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2851
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:171
llvm::Instruction
Definition: Instruction.h:45
llvm::SimplifyInstruction
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6328
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:376
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1796
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
LoopUtils.h
llvm::CodeMetrics::collectEphemeralValues
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Definition: CodeMetrics.cpp:71
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:216
llvm::RemoveRedundantDbgInstrs
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
Definition: BasicBlockUtils.cpp:439
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:590
llvm::RF_NoModuleLevelChanges
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:71
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::BasicBlock::getPostdominatingDeoptimizeCall
const CallInst * getPostdominatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...
Definition: BasicBlock.cpp:204
CFG.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3182
llvm::cloneAndAdaptNoAliasScopes
void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)
Clone the specified noalias decl scopes.
Definition: CloneFunction.cpp:991
llvm::BasicBlock::hasAddressTaken
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:448
llvm::cl::opt< bool >
llvm::DbgVariableIntrinsic
This is the common base class for debug info intrinsics for variables.
Definition: IntrinsicInst.h:148
SSA
Memory SSA
Definition: MemorySSA.cpp:73
LiveDebugValues::DbgValue
Class recording the (high level) value of a variable.
Definition: InstrRefBasedImpl.h:225
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::LoopBase::moveToHeader
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
Definition: LoopInfo.h:443
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:56
llvm::LoopBase::getUniqueExitBlocks
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:122
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2816
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3157
DebugInfo.h
I
#define I(x, y, z)
Definition: MD5.cpp:59
Cloning.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:593
Metrics
Machine Trace Metrics
Definition: MachineTraceMetrics.cpp:53
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
RewriteUsesOfClonedInstructions
static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader, BasicBlock *OrigPreheader, ValueToValueMapTy &ValueMap, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *InsertedPHIs)
RewriteUsesOfClonedInstructions - We just cloned the instructions from the old header into the prehea...
Definition: LoopRotationUtils.cpp:103
llvm::insertDebugValuesForPHIs
void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode * > &InsertedPHIs)
Propagate dbg.value intrinsics through the newly inserted PHIs.
Definition: Local.cpp:1612
llvm::findDbgValues
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:76
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::ScalarEvolution::forgetValue
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
Definition: ScalarEvolution.cpp:7684
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::LoopBase::hasDedicatedExits
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:92
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::ValueMap::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: ValueMap.h:173
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:164
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
canRotateDeoptimizingLatchExit
static bool canRotateDeoptimizingLatchExit(Loop *L)
Definition: LoopRotationUtils.cpp:216
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3179
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:856
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::MergeBlockIntoPredecessor
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
Definition: BasicBlockUtils.cpp:180
llvm::any_of
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:1588
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
LoopPass.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
LoopRotationUtils.h
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:276
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
SSAUpdater.h
llvm::Instruction::mayReadFromMemory
bool mayReadFromMemory() const
Return true if this instruction may read memory.
Definition: Instruction.cpp:570
llvm::Loop::hasLoopInvariantOperands
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:70
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:286
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::BasicBlock::getTerminator
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:152
llvm::RF_IgnoreMissingLocals
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:89
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:36
llvm::Loop::setLoopID
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:528
llvm::Loop::getLoopID
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:504
llvm::LoopRotation
bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ, bool RotationOnly, unsigned Threshold, bool IsUtilMode, bool PrepareForLTO=false)
Convert a loop into a loop with bottom test.
Definition: LoopRotationUtils.cpp:826
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:670
ScalarEvolutionAliasAnalysis.h
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::FoldSingleEntryPHINodes
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
Definition: BasicBlockUtils.cpp:145
llvm::BasicBlock::back
const Instruction & back() const
Definition: BasicBlock.h:310
MemorySSA.h
llvm::BasicBlock::moveBefore
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
Definition: BasicBlock.cpp:137
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:370
Dominators.h
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2666
Threshold
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:325
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
InsertNewValueIntoMap
static void InsertNewValueIntoMap(ValueToValueMapTy &VM, Value *K, Value *V)
Insert (K, V) pair into the ValueToValueMap, and verify the key did not previously exist in the map,...
Definition: LoopRotationUtils.cpp:94
llvm::LoopBase::isLoopExiting
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
Definition: LoopInfo.h:225
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::ValueMap::lookup
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
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
llvm::cl::desc
Definition: CommandLine.h:412
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3101
raw_ostream.h
llvm::SSAUpdater
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:38
BasicBlockUtils.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3180
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3194
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::Instruction::moveBefore
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:97
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44