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  SmallVectorImpl<PHINode*> *InsertedPHIs) {
107  // Remove PHI node entries that are no longer live.
108  BasicBlock::iterator I, E = OrigHeader->end();
109  for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
110  PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
111 
112  // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
113  // as necessary.
114  SSAUpdater SSA(InsertedPHIs);
115  for (I = OrigHeader->begin(); I != E; ++I) {
116  Value *OrigHeaderVal = &*I;
117 
118  // If there are no uses of the value (e.g. because it returns void), there
119  // is nothing to rewrite.
120  if (OrigHeaderVal->use_empty())
121  continue;
122 
123  Value *OrigPreHeaderVal = ValueMap.lookup(OrigHeaderVal);
124 
125  // The value now exits in two versions: the initial value in the preheader
126  // and the loop "next" value in the original header.
127  SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
128  SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
129  SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);
130 
131  // Visit each use of the OrigHeader instruction.
132  for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
133  UE = OrigHeaderVal->use_end();
134  UI != UE;) {
135  // Grab the use before incrementing the iterator.
136  Use &U = *UI;
137 
138  // Increment the iterator before removing the use from the list.
139  ++UI;
140 
141  // SSAUpdater can't handle a non-PHI use in the same block as an
142  // earlier def. We can easily handle those cases manually.
143  Instruction *UserInst = cast<Instruction>(U.getUser());
144  if (!isa<PHINode>(UserInst)) {
145  BasicBlock *UserBB = UserInst->getParent();
146 
147  // The original users in the OrigHeader are already using the
148  // original definitions.
149  if (UserBB == OrigHeader)
150  continue;
151 
152  // Users in the OrigPreHeader need to use the value to which the
153  // original definitions are mapped.
154  if (UserBB == OrigPreheader) {
155  U = OrigPreHeaderVal;
156  continue;
157  }
158  }
159 
160  // Anything else can be handled by SSAUpdater.
161  SSA.RewriteUse(U);
162  }
163 
164  // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug
165  // intrinsics.
167  llvm::findDbgValues(DbgValues, OrigHeaderVal);
168  for (auto &DbgValue : DbgValues) {
169  // The original users in the OrigHeader are already using the original
170  // definitions.
171  BasicBlock *UserBB = DbgValue->getParent();
172  if (UserBB == OrigHeader)
173  continue;
174 
175  // Users in the OrigPreHeader need to use the value to which the
176  // original definitions are mapped and anything else can be handled by
177  // the SSAUpdater. To avoid adding PHINodes, check if the value is
178  // available in UserBB, if not substitute undef.
179  Value *NewVal;
180  if (UserBB == OrigPreheader)
181  NewVal = OrigPreHeaderVal;
182  else if (SSA.HasValueForBlock(UserBB))
183  NewVal = SSA.GetValueInMiddleOfBlock(UserBB);
184  else
185  NewVal = UndefValue::get(OrigHeaderVal->getType());
186  DbgValue->replaceVariableLocationOp(OrigHeaderVal, NewVal);
187  }
188  }
189 }
190 
191 // Assuming both header and latch are exiting, look for a phi which is only
192 // used outside the loop (via a LCSSA phi) in the exit from the header.
193 // This means that rotating the loop can remove the phi.
195  BasicBlock *Header = L->getHeader();
196  BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator());
197  assert(BI && BI->isConditional() && "need header with conditional exit");
198  BasicBlock *HeaderExit = BI->getSuccessor(0);
199  if (L->contains(HeaderExit))
200  HeaderExit = BI->getSuccessor(1);
201 
202  for (auto &Phi : Header->phis()) {
203  // Look for uses of this phi in the loop/via exits other than the header.
204  if (llvm::any_of(Phi.users(), [HeaderExit](const User *U) {
205  return cast<Instruction>(U)->getParent() != HeaderExit;
206  }))
207  continue;
208  return true;
209  }
210  return false;
211 }
212 
213 // Check that latch exit is deoptimizing (which means - very unlikely to happen)
214 // and there is another exit from the loop which is non-deoptimizing.
215 // If we rotate latch to that exit our loop has a better chance of being fully
216 // canonical.
217 //
218 // It can give false positives in some rare cases.
220  BasicBlock *Latch = L->getLoopLatch();
221  assert(Latch && "need latch");
222  BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
223  // Need normal exiting latch.
224  if (!BI || !BI->isConditional())
225  return false;
226 
227  BasicBlock *Exit = BI->getSuccessor(1);
228  if (L->contains(Exit))
229  Exit = BI->getSuccessor(0);
230 
231  // Latch exit is non-deoptimizing, no need to rotate.
232  if (!Exit->getPostdominatingDeoptimizeCall())
233  return false;
234 
236  L->getUniqueExitBlocks(Exits);
237  if (!Exits.empty()) {
238  // There is at least one non-deoptimizing exit.
239  //
240  // Note, that BasicBlock::getPostdominatingDeoptimizeCall is not exact,
241  // as it can conservatively return false for deoptimizing exits with
242  // complex enough control flow down to deoptimize call.
243  //
244  // That means here we can report success for a case where
245  // all exits are deoptimizing but one of them has complex enough
246  // control flow (e.g. with loops).
247  //
248  // That should be a very rare case and false positives for this function
249  // have compile-time effect only.
250  return any_of(Exits, [](const BasicBlock *BB) {
251  return !BB->getPostdominatingDeoptimizeCall();
252  });
253  }
254  return false;
255 }
256 
257 /// Rotate loop LP. Return true if the loop is rotated.
258 ///
259 /// \param SimplifiedLatch is true if the latch was just folded into the final
260 /// loop exit. In this case we may want to rotate even though the new latch is
261 /// now an exiting branch. This rotation would have happened had the latch not
262 /// been simplified. However, if SimplifiedLatch is false, then we avoid
263 /// rotating loops in which the latch exits to avoid excessive or endless
264 /// rotation. LoopRotate should be repeatable and converge to a canonical
265 /// form. This property is satisfied because simplifying the loop latch can only
266 /// happen once across multiple invocations of the LoopRotate pass.
267 ///
268 /// If -loop-rotate-multi is enabled we can do multiple rotations in one go
269 /// so to reach a suitable (non-deoptimizing) exit.
270 bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
271  // If the loop has only one block then there is not much to rotate.
272  if (L->getBlocks().size() == 1)
273  return false;
274 
275  bool Rotated = false;
276  do {
277  BasicBlock *OrigHeader = L->getHeader();
278  BasicBlock *OrigLatch = L->getLoopLatch();
279 
280  BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
281  if (!BI || BI->isUnconditional())
282  return Rotated;
283 
284  // If the loop header is not one of the loop exiting blocks then
285  // either this loop is already rotated or it is not
286  // suitable for loop rotation transformations.
287  if (!L->isLoopExiting(OrigHeader))
288  return Rotated;
289 
290  // If the loop latch already contains a branch that leaves the loop then the
291  // loop is already rotated.
292  if (!OrigLatch)
293  return Rotated;
294 
295  // Rotate if either the loop latch does *not* exit the loop, or if the loop
296  // latch was just simplified. Or if we think it will be profitable.
297  if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode == false &&
300  return Rotated;
301 
302  // Check size of original header and reject loop if it is very big or we can't
303  // duplicate blocks inside it.
304  {
306  CodeMetrics::collectEphemeralValues(L, AC, EphValues);
307 
309  Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues, PrepareForLTO);
310  if (Metrics.notDuplicatable) {
311  LLVM_DEBUG(
312  dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable"
313  << " instructions: ";
314  L->dump());
315  return Rotated;
316  }
317  if (Metrics.convergent) {
318  LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "
319  "instructions: ";
320  L->dump());
321  return Rotated;
322  }
323  if (Metrics.NumInsts > MaxHeaderSize) {
324  LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains "
325  << Metrics.NumInsts
326  << " instructions, which is more than the threshold ("
327  << MaxHeaderSize << " instructions): ";
328  L->dump());
329  ++NumNotRotatedDueToHeaderSize;
330  return Rotated;
331  }
332 
333  // When preparing for LTO, avoid rotating loops with calls that could be
334  // inlined during the LTO stage.
335  if (PrepareForLTO && Metrics.NumInlineCandidates > 0)
336  return Rotated;
337  }
338 
339  // Now, this loop is suitable for rotation.
340  BasicBlock *OrigPreheader = L->getLoopPreheader();
341 
342  // If the loop could not be converted to canonical form, it must have an
343  // indirectbr in it, just give up.
344  if (!OrigPreheader || !L->hasDedicatedExits())
345  return Rotated;
346 
347  // Anything ScalarEvolution may know about this loop or the PHI nodes
348  // in its header will soon be invalidated. We should also invalidate
349  // all outer loops because insertion and deletion of blocks that happens
350  // during the rotation may violate invariants related to backedge taken
351  // infos in them.
352  if (SE)
353  SE->forgetTopmostLoop(L);
354 
355  LLVM_DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
356  if (MSSAU && VerifyMemorySSA)
357  MSSAU->getMemorySSA()->verifyMemorySSA();
358 
359  // Find new Loop header. NewHeader is a Header's one and only successor
360  // that is inside loop. Header's other successor is outside the
361  // loop. Otherwise loop is not suitable for rotation.
362  BasicBlock *Exit = BI->getSuccessor(0);
363  BasicBlock *NewHeader = BI->getSuccessor(1);
364  if (L->contains(Exit))
365  std::swap(Exit, NewHeader);
366  assert(NewHeader && "Unable to determine new loop header");
367  assert(L->contains(NewHeader) && !L->contains(Exit) &&
368  "Unable to determine loop header and exit blocks");
369 
370  // This code assumes that the new header has exactly one predecessor.
371  // Remove any single-entry PHI nodes in it.
372  assert(NewHeader->getSinglePredecessor() &&
373  "New header doesn't have one pred!");
374  FoldSingleEntryPHINodes(NewHeader);
375 
376  // Begin by walking OrigHeader and populating ValueMap with an entry for
377  // each Instruction.
378  BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
379  ValueToValueMapTy ValueMap, ValueMapMSSA;
380 
381  // For PHI nodes, the value available in OldPreHeader is just the
382  // incoming value from OldPreHeader.
383  for (; PHINode *PN = dyn_cast<PHINode>(I); ++I)
385  PN->getIncomingValueForBlock(OrigPreheader));
386 
387  // For the rest of the instructions, either hoist to the OrigPreheader if
388  // possible or create a clone in the OldPreHeader if not.
389  Instruction *LoopEntryBranch = OrigPreheader->getTerminator();
390 
391  // Record all debug intrinsics preceding LoopEntryBranch to avoid
392  // duplication.
393  using DbgIntrinsicHash =
394  std::pair<std::pair<hash_code, DILocalVariable *>, DIExpression *>;
395  auto makeHash = [](DbgVariableIntrinsic *D) -> DbgIntrinsicHash {
396  auto VarLocOps = D->location_ops();
397  return {{hash_combine_range(VarLocOps.begin(), VarLocOps.end()),
398  D->getVariable()},
399  D->getExpression()};
400  };
402  for (auto I = std::next(OrigPreheader->rbegin()), E = OrigPreheader->rend();
403  I != E; ++I) {
404  if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&*I))
405  DbgIntrinsics.insert(makeHash(DII));
406  else
407  break;
408  }
409 
410  // Remember the local noalias scope declarations in the header. After the
411  // rotation, they must be duplicated and the scope must be cloned. This
412  // avoids unwanted interaction across iterations.
413  SmallVector<NoAliasScopeDeclInst *, 6> NoAliasDeclInstructions;
414  for (Instruction &I : *OrigHeader)
415  if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I))
416  NoAliasDeclInstructions.push_back(Decl);
417 
418  while (I != E) {
419  Instruction *Inst = &*I++;
420 
421  // If the instruction's operands are invariant and it doesn't read or write
422  // memory, then it is safe to hoist. Doing this doesn't change the order of
423  // execution in the preheader, but does prevent the instruction from
424  // executing in each iteration of the loop. This means it is safe to hoist
425  // something that might trap, but isn't safe to hoist something that reads
426  // memory (without proving that the loop doesn't write).
427  if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&
428  !Inst->mayWriteToMemory() && !Inst->isTerminator() &&
429  !isa<DbgInfoIntrinsic>(Inst) && !isa<AllocaInst>(Inst)) {
430  Inst->moveBefore(LoopEntryBranch);
431  ++NumInstrsHoisted;
432  continue;
433  }
434 
435  // Otherwise, create a duplicate of the instruction.
436  Instruction *C = Inst->clone();
437  ++NumInstrsDuplicated;
438 
439  // Eagerly remap the operands of the instruction.
442 
443  // Avoid inserting the same intrinsic twice.
444  if (auto *DII = dyn_cast<DbgVariableIntrinsic>(C))
445  if (DbgIntrinsics.count(makeHash(DII))) {
446  C->deleteValue();
447  continue;
448  }
449 
450  // With the operands remapped, see if the instruction constant folds or is
451  // otherwise simplifyable. This commonly occurs because the entry from PHI
452  // nodes allows icmps and other instructions to fold.
453  Value *V = SimplifyInstruction(C, SQ);
454  if (V && LI->replacementPreservesLCSSAForm(C, V)) {
455  // If so, then delete the temporary instruction and stick the folded value
456  // in the map.
458  if (!C->mayHaveSideEffects()) {
459  C->deleteValue();
460  C = nullptr;
461  }
462  } else {
464  }
465  if (C) {
466  // Otherwise, stick the new instruction into the new block!
467  C->setName(Inst->getName());
468  C->insertBefore(LoopEntryBranch);
469 
470  if (auto *II = dyn_cast<AssumeInst>(C))
471  AC->registerAssumption(II);
472  // MemorySSA cares whether the cloned instruction was inserted or not, and
473  // not whether it can be remapped to a simplified value.
474  if (MSSAU)
475  InsertNewValueIntoMap(ValueMapMSSA, Inst, C);
476  }
477  }
478 
479  if (!NoAliasDeclInstructions.empty()) {
480  // There are noalias scope declarations:
481  // (general):
482  // Original: OrigPre { OrigHeader NewHeader ... Latch }
483  // after: (OrigPre+OrigHeader') { NewHeader ... Latch OrigHeader }
484  //
485  // with D: llvm.experimental.noalias.scope.decl,
486  // U: !noalias or !alias.scope depending on D
487  // ... { D U1 U2 } can transform into:
488  // (0) : ... { D U1 U2 } // no relevant rotation for this part
489  // (1) : ... D' { U1 U2 D } // D is part of OrigHeader
490  // (2) : ... D' U1' { U2 D U1 } // D, U1 are part of OrigHeader
491  //
492  // We now want to transform:
493  // (1) -> : ... D' { D U1 U2 D'' }
494  // (2) -> : ... D' U1' { D U2 D'' U1'' }
495  // D: original llvm.experimental.noalias.scope.decl
496  // D', U1': duplicate with replaced scopes
497  // D'', U1'': different duplicate with replaced scopes
498  // This ensures a safe fallback to 'may_alias' introduced by the rotate,
499  // as U1'' and U1' scopes will not be compatible wrt to the local restrict
500 
501  // Clone the llvm.experimental.noalias.decl again for the NewHeader.
502  Instruction *NewHeaderInsertionPoint = &(*NewHeader->getFirstNonPHI());
503  for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions) {
504  LLVM_DEBUG(dbgs() << " Cloning llvm.experimental.noalias.scope.decl:"
505  << *NAD << "\n");
506  Instruction *NewNAD = NAD->clone();
507  NewNAD->insertBefore(NewHeaderInsertionPoint);
508  }
509 
510  // Scopes must now be duplicated, once for OrigHeader and once for
511  // OrigPreHeader'.
512  {
513  auto &Context = NewHeader->getContext();
514 
515  SmallVector<MDNode *, 8> NoAliasDeclScopes;
516  for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions)
517  NoAliasDeclScopes.push_back(NAD->getScopeList());
518 
519  LLVM_DEBUG(dbgs() << " Updating OrigHeader scopes\n");
520  cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, {OrigHeader}, Context,
521  "h.rot");
522  LLVM_DEBUG(OrigHeader->dump());
523 
524  // Keep the compile time impact low by only adapting the inserted block
525  // of instructions in the OrigPreHeader. This might result in slightly
526  // more aliasing between these instructions and those that were already
527  // present, but it will be much faster when the original PreHeader is
528  // large.
529  LLVM_DEBUG(dbgs() << " Updating part of OrigPreheader scopes\n");
530  auto *FirstDecl =
531  cast<Instruction>(ValueMap[*NoAliasDeclInstructions.begin()]);
532  auto *LastInst = &OrigPreheader->back();
533  cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, FirstDecl, LastInst,
534  Context, "pre.rot");
535  LLVM_DEBUG(OrigPreheader->dump());
536 
537  LLVM_DEBUG(dbgs() << " Updated NewHeader:\n");
538  LLVM_DEBUG(NewHeader->dump());
539  }
540  }
541 
542  // Along with all the other instructions, we just cloned OrigHeader's
543  // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's
544  // successors by duplicating their incoming values for OrigHeader.
545  for (BasicBlock *SuccBB : successors(OrigHeader))
546  for (BasicBlock::iterator BI = SuccBB->begin();
547  PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
548  PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
549 
550  // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
551  // OrigPreHeader's old terminator (the original branch into the loop), and
552  // remove the corresponding incoming values from the PHI nodes in OrigHeader.
553  LoopEntryBranch->eraseFromParent();
554 
555  // Update MemorySSA before the rewrite call below changes the 1:1
556  // instruction:cloned_instruction_or_value mapping.
557  if (MSSAU) {
558  InsertNewValueIntoMap(ValueMapMSSA, OrigHeader, OrigPreheader);
559  MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader,
560  ValueMapMSSA);
561  }
562 
563  SmallVector<PHINode*, 2> InsertedPHIs;
564  // If there were any uses of instructions in the duplicated block outside the
565  // loop, update them, inserting PHI nodes as required
566  RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap,
567  &InsertedPHIs);
568 
569  // Attach dbg.value intrinsics to the new phis if that phi uses a value that
570  // previously had debug metadata attached. This keeps the debug info
571  // up-to-date in the loop body.
572  if (!InsertedPHIs.empty())
573  insertDebugValuesForPHIs(OrigHeader, InsertedPHIs);
574 
575  // NewHeader is now the header of the loop.
576  L->moveToHeader(NewHeader);
577  assert(L->getHeader() == NewHeader && "Latch block is our new header");
578 
579  // Inform DT about changes to the CFG.
580  if (DT) {
581  // The OrigPreheader branches to the NewHeader and Exit now. Then, inform
582  // the DT about the removed edge to the OrigHeader (that got removed).
584  Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});
585  Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});
586  Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});
587 
588  if (MSSAU) {
589  MSSAU->applyUpdates(Updates, *DT, /*UpdateDT=*/true);
590  if (VerifyMemorySSA)
591  MSSAU->getMemorySSA()->verifyMemorySSA();
592  } else {
593  DT->applyUpdates(Updates);
594  }
595  }
596 
597  // At this point, we've finished our major CFG changes. As part of cloning
598  // the loop into the preheader we've simplified instructions and the
599  // duplicated conditional branch may now be branching on a constant. If it is
600  // branching on a constant and if that constant means that we enter the loop,
601  // then we fold away the cond branch to an uncond branch. This simplifies the
602  // loop in cases important for nested loops, and it also means we don't have
603  // to split as many edges.
604  BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
605  assert(PHBI->isConditional() && "Should be clone of BI condbr!");
606  if (!isa<ConstantInt>(PHBI->getCondition()) ||
607  PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) !=
608  NewHeader) {
609  // The conditional branch can't be folded, handle the general case.
610  // Split edges as necessary to preserve LoopSimplify form.
611 
612  // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
613  // thus is not a preheader anymore.
614  // Split the edge to form a real preheader.
615  BasicBlock *NewPH = SplitCriticalEdge(
616  OrigPreheader, NewHeader,
617  CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
618  NewPH->setName(NewHeader->getName() + ".lr.ph");
619 
620  // Preserve canonical loop form, which means that 'Exit' should have only
621  // one predecessor. Note that Exit could be an exit block for multiple
622  // nested loops, causing both of the edges to now be critical and need to
623  // be split.
624  SmallVector<BasicBlock *, 4> ExitPreds(pred_begin(Exit), pred_end(Exit));
625  bool SplitLatchEdge = false;
626  for (BasicBlock *ExitPred : ExitPreds) {
627  // We only need to split loop exit edges.
628  Loop *PredLoop = LI->getLoopFor(ExitPred);
629  if (!PredLoop || PredLoop->contains(Exit) ||
630  ExitPred->getTerminator()->isIndirectTerminator())
631  continue;
632  SplitLatchEdge |= L->getLoopLatch() == ExitPred;
633  BasicBlock *ExitSplit = SplitCriticalEdge(
634  ExitPred, Exit,
635  CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
636  ExitSplit->moveBefore(Exit);
637  }
638  assert(SplitLatchEdge &&
639  "Despite splitting all preds, failed to split latch exit?");
640  (void)SplitLatchEdge;
641  } else {
642  // We can fold the conditional branch in the preheader, this makes things
643  // simpler. The first step is to remove the extra edge to the Exit block.
644  Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);
645  BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI);
646  NewBI->setDebugLoc(PHBI->getDebugLoc());
647  PHBI->eraseFromParent();
648 
649  // With our CFG finalized, update DomTree if it is available.
650  if (DT) DT->deleteEdge(OrigPreheader, Exit);
651 
652  // Update MSSA too, if available.
653  if (MSSAU)
654  MSSAU->removeEdge(OrigPreheader, Exit);
655  }
656 
657  assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
658  assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
659 
660  if (MSSAU && VerifyMemorySSA)
661  MSSAU->getMemorySSA()->verifyMemorySSA();
662 
663  // Now that the CFG and DomTree are in a consistent state again, try to merge
664  // the OrigHeader block into OrigLatch. This will succeed if they are
665  // connected by an unconditional branch. This is just a cleanup so the
666  // emitted code isn't too gross in this common case.
668  BasicBlock *PredBB = OrigHeader->getUniquePredecessor();
669  bool DidMerge = MergeBlockIntoPredecessor(OrigHeader, &DTU, LI, MSSAU);
670  if (DidMerge)
671  RemoveRedundantDbgInstrs(PredBB);
672 
673  if (MSSAU && VerifyMemorySSA)
674  MSSAU->getMemorySSA()->verifyMemorySSA();
675 
676  LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump());
677 
678  ++NumRotated;
679 
680  Rotated = true;
681  SimplifiedLatch = false;
682 
683  // Check that new latch is a deoptimizing exit and then repeat rotation if possible.
684  // Deoptimizing latch exit is not a generally typical case, so we just loop over.
685  // TODO: if it becomes a performance bottleneck extend rotation algorithm
686  // to handle multiple rotations in one go.
688 
689 
690  return true;
691 }
692 
693 /// Determine whether the instructions in this range may be safely and cheaply
694 /// speculated. This is not an important enough situation to develop complex
695 /// heuristics. We handle a single arithmetic instruction along with any type
696 /// conversions.
698  BasicBlock::iterator End, Loop *L) {
699  bool seenIncrement = false;
700  bool MultiExitLoop = false;
701 
702  if (!L->getExitingBlock())
703  MultiExitLoop = true;
704 
705  for (BasicBlock::iterator I = Begin; I != End; ++I) {
706 
708  return false;
709 
710  if (isa<DbgInfoIntrinsic>(I))
711  continue;
712 
713  switch (I->getOpcode()) {
714  default:
715  return false;
716  case Instruction::GetElementPtr:
717  // GEPs are cheap if all indices are constant.
718  if (!cast<GEPOperator>(I)->hasAllConstantIndices())
719  return false;
720  // fall-thru to increment case
722  case Instruction::Add:
723  case Instruction::Sub:
724  case Instruction::And:
725  case Instruction::Or:
726  case Instruction::Xor:
727  case Instruction::Shl:
728  case Instruction::LShr:
729  case Instruction::AShr: {
730  Value *IVOpnd =
731  !isa<Constant>(I->getOperand(0))
732  ? I->getOperand(0)
733  : !isa<Constant>(I->getOperand(1)) ? I->getOperand(1) : nullptr;
734  if (!IVOpnd)
735  return false;
736 
737  // If increment operand is used outside of the loop, this speculation
738  // could cause extra live range interference.
739  if (MultiExitLoop) {
740  for (User *UseI : IVOpnd->users()) {
741  auto *UserInst = cast<Instruction>(UseI);
742  if (!L->contains(UserInst))
743  return false;
744  }
745  }
746 
747  if (seenIncrement)
748  return false;
749  seenIncrement = true;
750  break;
751  }
752  case Instruction::Trunc:
753  case Instruction::ZExt:
754  case Instruction::SExt:
755  // ignore type conversions
756  break;
757  }
758  }
759  return true;
760 }
761 
762 /// Fold the loop tail into the loop exit by speculating the loop tail
763 /// instructions. Typically, this is a single post-increment. In the case of a
764 /// simple 2-block loop, hoisting the increment can be much better than
765 /// duplicating the entire loop header. In the case of loops with early exits,
766 /// rotation will not work anyway, but simplifyLoopLatch will put the loop in
767 /// canonical form so downstream passes can handle it.
768 ///
769 /// I don't believe this invalidates SCEV.
770 bool LoopRotate::simplifyLoopLatch(Loop *L) {
771  BasicBlock *Latch = L->getLoopLatch();
772  if (!Latch || Latch->hasAddressTaken())
773  return false;
774 
775  BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator());
776  if (!Jmp || !Jmp->isUnconditional())
777  return false;
778 
779  BasicBlock *LastExit = Latch->getSinglePredecessor();
780  if (!LastExit || !L->isLoopExiting(LastExit))
781  return false;
782 
783  BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator());
784  if (!BI)
785  return false;
786 
787  if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L))
788  return false;
789 
790  LLVM_DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
791  << LastExit->getName() << "\n");
792 
794  MergeBlockIntoPredecessor(Latch, &DTU, LI, MSSAU, nullptr,
795  /*PredecessorWithTwoSuccessors=*/true);
796 
797  if (MSSAU && VerifyMemorySSA)
798  MSSAU->getMemorySSA()->verifyMemorySSA();
799 
800  return true;
801 }
802 
803 /// Rotate \c L, and return true if any modification was made.
804 bool LoopRotate::processLoop(Loop *L) {
805  // Save the loop metadata.
806  MDNode *LoopMD = L->getLoopID();
807 
808  bool SimplifiedLatch = false;
809 
810  // Simplify the loop latch before attempting to rotate the header
811  // upward. Rotation may not be needed if the loop tail can be folded into the
812  // loop exit.
813  if (!RotationOnly)
814  SimplifiedLatch = simplifyLoopLatch(L);
815 
816  bool MadeChange = rotateLoop(L, SimplifiedLatch);
817  assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&
818  "Loop latch should be exiting after loop-rotate.");
819 
820  // Restore the loop metadata.
821  // NB! We presume LoopRotation DOESN'T ADD its own metadata.
822  if ((MadeChange || SimplifiedLatch) && LoopMD)
823  L->setLoopID(LoopMD);
824 
825  return MadeChange || SimplifiedLatch;
826 }
827 
828 
829 /// The utility to convert a loop into a loop with bottom test.
832  ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
833  const SimplifyQuery &SQ, bool RotationOnly = true,
834  unsigned Threshold = unsigned(-1),
835  bool IsUtilMode = true, bool PrepareForLTO) {
836  LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
837  IsUtilMode, PrepareForLTO);
838  return LR.processLoop(L);
839 }
llvm::NoAliasScopeDeclInst
Definition: IntrinsicInst.h:1205
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:163
AssumptionCache.h
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:4583
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
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:697
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:4754
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:167
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:443
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:194
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::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:264
llvm::DIExpression
DWARF expression.
Definition: DebugInfoMetadata.h:2557
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::BasicBlock::rend
reverse_iterator rend()
Definition: BasicBlock.h:303
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
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"))
RewriteUsesOfClonedInstructions
static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader, BasicBlock *OrigPreheader, ValueToValueMapTy &ValueMap, SmallVectorImpl< PHINode * > *InsertedPHIs)
RewriteUsesOfClonedInstructions - We just cloned the instructions from the old header into the prehea...
Definition: LoopRotationUtils.cpp:103
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
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:253
llvm::Value::use_iterator
use_iterator_impl< Use > use_iterator
Definition: Value.h:354
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:136
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2782
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:6246
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:364
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1784
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
LoopUtils.h
llvm::BasicBlock::rbegin
reverse_iterator rbegin()
Definition: BasicBlock.h:301
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:70
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:212
llvm::RemoveRedundantDbgInstrs
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
Definition: BasicBlockUtils.cpp:432
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:584
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:72
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
llvm::BasicBlock::getPostdominatingDeoptimizeCall
const CallInst * getPostdominatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...
Definition: BasicBlock.cpp:200
CFG.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3113
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
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:2747
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3088
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:443
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
llvm::insertDebugValuesForPHIs
void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode * > &InsertedPHIs)
Propagate dbg.value intrinsics through the newly inserted PHIs.
Definition: Local.cpp:1614
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:369
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::Value::use_begin
use_iterator use_begin()
Definition: Value.h:361
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:162
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
canRotateDeoptimizingLatchExit
static bool canRotateDeoptimizingLatchExit(Loop *L)
Definition: LoopRotationUtils.cpp:219
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3110
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:850
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:173
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:1554
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
LoopPass.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
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:272
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::Value::use_end
use_iterator use_end()
Definition: Value.h:369
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
SSAUpdater.h
llvm::Instruction::mayReadFromMemory
bool mayReadFromMemory() const
Return true if this instruction may read memory.
Definition: Instruction.cpp:564
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:273
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
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:148
llvm::RF_IgnoreMissingLocals
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:90
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
llvm::Loop::setLoopID
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:527
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::Loop::getLoopID
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:503
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:830
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:669
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:138
llvm::BasicBlock::back
const Instruction & back() const
Definition: BasicBlock.h:310
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
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:133
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:372
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:482
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2597
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:321
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:414
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3032
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:75
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3111
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3125
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