LLVM  15.0.0git
LoopUtils.cpp
Go to the documentation of this file.
1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
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 defines common loop utility functions.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/DenseSet.h"
15 #include "llvm/ADT/Optional.h"
17 #include "llvm/ADT/ScopeExit.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/Analysis/LoopPass.h"
34 #include "llvm/IR/DIBuilder.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Instructions.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/MDBuilder.h"
39 #include "llvm/IR/Module.h"
40 #include "llvm/IR/PatternMatch.h"
41 #include "llvm/IR/ValueHandle.h"
42 #include "llvm/InitializePasses.h"
43 #include "llvm/Pass.h"
44 #include "llvm/Support/Debug.h"
48 
49 using namespace llvm;
50 using namespace llvm::PatternMatch;
51 
52 #define DEBUG_TYPE "loop-utils"
53 
54 static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
55 static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
56 
58  MemorySSAUpdater *MSSAU,
59  bool PreserveLCSSA) {
60  bool Changed = false;
61 
62  // We re-use a vector for the in-loop predecesosrs.
63  SmallVector<BasicBlock *, 4> InLoopPredecessors;
64 
65  auto RewriteExit = [&](BasicBlock *BB) {
66  assert(InLoopPredecessors.empty() &&
67  "Must start with an empty predecessors list!");
68  auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
69 
70  // See if there are any non-loop predecessors of this exit block and
71  // keep track of the in-loop predecessors.
72  bool IsDedicatedExit = true;
73  for (auto *PredBB : predecessors(BB))
74  if (L->contains(PredBB)) {
75  if (isa<IndirectBrInst>(PredBB->getTerminator()))
76  // We cannot rewrite exiting edges from an indirectbr.
77  return false;
78  if (isa<CallBrInst>(PredBB->getTerminator()))
79  // We cannot rewrite exiting edges from a callbr.
80  return false;
81 
82  InLoopPredecessors.push_back(PredBB);
83  } else {
84  IsDedicatedExit = false;
85  }
86 
87  assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
88 
89  // Nothing to do if this is already a dedicated exit.
90  if (IsDedicatedExit)
91  return false;
92 
93  auto *NewExitBB = SplitBlockPredecessors(
94  BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA);
95 
96  if (!NewExitBB)
97  LLVM_DEBUG(
98  dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
99  << *L << "\n");
100  else
101  LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
102  << NewExitBB->getName() << "\n");
103  return true;
104  };
105 
106  // Walk the exit blocks directly rather than building up a data structure for
107  // them, but only visit each one once.
109  for (auto *BB : L->blocks())
110  for (auto *SuccBB : successors(BB)) {
111  // We're looking for exit blocks so skip in-loop successors.
112  if (L->contains(SuccBB))
113  continue;
114 
115  // Visit each exit block exactly once.
116  if (!Visited.insert(SuccBB).second)
117  continue;
118 
119  Changed |= RewriteExit(SuccBB);
120  }
121 
122  return Changed;
123 }
124 
125 /// Returns the instructions that use values defined in the loop.
127  SmallVector<Instruction *, 8> UsedOutside;
128 
129  for (auto *Block : L->getBlocks())
130  // FIXME: I believe that this could use copy_if if the Inst reference could
131  // be adapted into a pointer.
132  for (auto &Inst : *Block) {
133  auto Users = Inst.users();
134  if (any_of(Users, [&](User *U) {
135  auto *Use = cast<Instruction>(U);
136  return !L->contains(Use->getParent());
137  }))
138  UsedOutside.push_back(&Inst);
139  }
140 
141  return UsedOutside;
142 }
143 
145  // By definition, all loop passes need the LoopInfo analysis and the
146  // Dominator tree it depends on. Because they all participate in the loop
147  // pass manager, they must also preserve these.
152 
153  // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
154  // here because users shouldn't directly get them from this header.
155  extern char &LoopSimplifyID;
156  extern char &LCSSAID;
161  // This is used in the LPPassManager to perform LCSSA verification on passes
162  // which preserve lcssa form
165 
166  // Loop passes are designed to run inside of a loop pass manager which means
167  // that any function analyses they require must be required by the first loop
168  // pass in the manager (so that it is computed before the loop pass manager
169  // runs) and preserved by all loop pasess in the manager. To make this
170  // reasonably robust, the set needed for most loop passes is maintained here.
171  // If your loop pass requires an analysis not listed here, you will need to
172  // carefully audit the loop pass manager nesting structure that results.
180  // FIXME: When all loop passes preserve MemorySSA, it can be required and
181  // preserved here instead of the individual handling in each pass.
182 }
183 
184 /// Manually defined generic "LoopPass" dependency initialization. This is used
185 /// to initialize the exact set of passes from above in \c
186 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
187 /// with:
188 ///
189 /// INITIALIZE_PASS_DEPENDENCY(LoopPass)
190 ///
191 /// As-if "LoopPass" were a pass.
195  INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
196  INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
203 }
204 
205 /// Create MDNode for input string.
206 static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
207  LLVMContext &Context = TheLoop->getHeader()->getContext();
208  Metadata *MDs[] = {
211  return MDNode::get(Context, MDs);
212 }
213 
214 /// Set input string into loop metadata by keeping other values intact.
215 /// If the string is already in loop metadata update value if it is
216 /// different.
217 void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *StringMD,
218  unsigned V) {
220  // If the loop already has metadata, retain it.
221  MDNode *LoopID = TheLoop->getLoopID();
222  if (LoopID) {
223  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
224  MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
225  // If it is of form key = value, try to parse it.
226  if (Node->getNumOperands() == 2) {
227  MDString *S = dyn_cast<MDString>(Node->getOperand(0));
228  if (S && S->getString().equals(StringMD)) {
229  ConstantInt *IntMD =
230  mdconst::extract_or_null<ConstantInt>(Node->getOperand(1));
231  if (IntMD && IntMD->getSExtValue() == V)
232  // It is already in place. Do nothing.
233  return;
234  // We need to update the value, so just skip it here and it will
235  // be added after copying other existed nodes.
236  continue;
237  }
238  }
239  MDs.push_back(Node);
240  }
241  }
242  // Add new metadata.
243  MDs.push_back(createStringMetadata(TheLoop, StringMD, V));
244  // Replace current metadata node with new one.
245  LLVMContext &Context = TheLoop->getHeader()->getContext();
246  MDNode *NewLoopID = MDNode::get(Context, MDs);
247  // Set operand 0 to refer to the loop id itself.
248  NewLoopID->replaceOperandWith(0, NewLoopID);
249  TheLoop->setLoopID(NewLoopID);
250 }
251 
255  getOptionalIntLoopAttribute(TheLoop, "llvm.loop.vectorize.width");
256 
257  if (Width) {
259  TheLoop, "llvm.loop.vectorize.scalable.enable");
260  return ElementCount::get(*Width, IsScalable.value_or(false));
261  }
262 
263  return None;
264 }
265 
267  MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions,
268  const char *InheritOptionsExceptPrefix, bool AlwaysNew) {
269  if (!OrigLoopID) {
270  if (AlwaysNew)
271  return nullptr;
272  return None;
273  }
274 
275  assert(OrigLoopID->getOperand(0) == OrigLoopID);
276 
277  bool InheritAllAttrs = !InheritOptionsExceptPrefix;
278  bool InheritSomeAttrs =
279  InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] != '\0';
281  MDs.push_back(nullptr);
282 
283  bool Changed = false;
284  if (InheritAllAttrs || InheritSomeAttrs) {
285  for (const MDOperand &Existing : drop_begin(OrigLoopID->operands())) {
286  MDNode *Op = cast<MDNode>(Existing.get());
287 
288  auto InheritThisAttribute = [InheritSomeAttrs,
289  InheritOptionsExceptPrefix](MDNode *Op) {
290  if (!InheritSomeAttrs)
291  return false;
292 
293  // Skip malformatted attribute metadata nodes.
294  if (Op->getNumOperands() == 0)
295  return true;
296  Metadata *NameMD = Op->getOperand(0).get();
297  if (!isa<MDString>(NameMD))
298  return true;
299  StringRef AttrName = cast<MDString>(NameMD)->getString();
300 
301  // Do not inherit excluded attributes.
302  return !AttrName.startswith(InheritOptionsExceptPrefix);
303  };
304 
305  if (InheritThisAttribute(Op))
306  MDs.push_back(Op);
307  else
308  Changed = true;
309  }
310  } else {
311  // Modified if we dropped at least one attribute.
312  Changed = OrigLoopID->getNumOperands() > 1;
313  }
314 
315  bool HasAnyFollowup = false;
316  for (StringRef OptionName : FollowupOptions) {
317  MDNode *FollowupNode = findOptionMDForLoopID(OrigLoopID, OptionName);
318  if (!FollowupNode)
319  continue;
320 
321  HasAnyFollowup = true;
322  for (const MDOperand &Option : drop_begin(FollowupNode->operands())) {
323  MDs.push_back(Option.get());
324  Changed = true;
325  }
326  }
327 
328  // Attributes of the followup loop not specified explicity, so signal to the
329  // transformation pass to add suitable attributes.
330  if (!AlwaysNew && !HasAnyFollowup)
331  return None;
332 
333  // If no attributes were added or remove, the previous loop Id can be reused.
334  if (!AlwaysNew && !Changed)
335  return OrigLoopID;
336 
337  // No attributes is equivalent to having no !llvm.loop metadata at all.
338  if (MDs.size() == 1)
339  return nullptr;
340 
341  // Build the new loop ID.
342  MDTuple *FollowupLoopID = MDNode::get(OrigLoopID->getContext(), MDs);
343  FollowupLoopID->replaceOperandWith(0, FollowupLoopID);
344  return FollowupLoopID;
345 }
346 
349 }
350 
353 }
354 
356  if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable"))
357  return TM_SuppressedByUser;
358 
359  Optional<int> Count =
360  getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
361  if (Count.hasValue())
362  return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
363 
364  if (getBooleanLoopAttribute(L, "llvm.loop.unroll.enable"))
365  return TM_ForcedByUser;
366 
367  if (getBooleanLoopAttribute(L, "llvm.loop.unroll.full"))
368  return TM_ForcedByUser;
369 
371  return TM_Disable;
372 
373  return TM_Unspecified;
374 }
375 
377  if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.disable"))
378  return TM_SuppressedByUser;
379 
380  Optional<int> Count =
381  getOptionalIntLoopAttribute(L, "llvm.loop.unroll_and_jam.count");
382  if (Count.hasValue())
383  return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
384 
385  if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.enable"))
386  return TM_ForcedByUser;
387 
389  return TM_Disable;
390 
391  return TM_Unspecified;
392 }
393 
396  getOptionalBoolLoopAttribute(L, "llvm.loop.vectorize.enable");
397 
398  if (Enable == false)
399  return TM_SuppressedByUser;
400 
401  Optional<ElementCount> VectorizeWidth =
403  Optional<int> InterleaveCount =
404  getOptionalIntLoopAttribute(L, "llvm.loop.interleave.count");
405 
406  // 'Forcing' vector width and interleave count to one effectively disables
407  // this tranformation.
408  if (Enable == true && VectorizeWidth && VectorizeWidth->isScalar() &&
409  InterleaveCount == 1)
410  return TM_SuppressedByUser;
411 
412  if (getBooleanLoopAttribute(L, "llvm.loop.isvectorized"))
413  return TM_Disable;
414 
415  if (Enable == true)
416  return TM_ForcedByUser;
417 
418  if ((VectorizeWidth && VectorizeWidth->isScalar()) && InterleaveCount == 1)
419  return TM_Disable;
420 
421  if ((VectorizeWidth && VectorizeWidth->isVector()) || InterleaveCount > 1)
422  return TM_Enable;
423 
425  return TM_Disable;
426 
427  return TM_Unspecified;
428 }
429 
431  if (getBooleanLoopAttribute(L, "llvm.loop.distribute.enable"))
432  return TM_ForcedByUser;
433 
435  return TM_Disable;
436 
437  return TM_Unspecified;
438 }
439 
441  if (getBooleanLoopAttribute(L, "llvm.loop.licm_versioning.disable"))
442  return TM_SuppressedByUser;
443 
445  return TM_Disable;
446 
447  return TM_Unspecified;
448 }
449 
450 /// Does a BFS from a given node to all of its children inside a given loop.
451 /// The returned vector of nodes includes the starting point.
455  auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
456  // Only include subregions in the top level loop.
457  BasicBlock *BB = DTN->getBlock();
458  if (CurLoop->contains(BB))
459  Worklist.push_back(DTN);
460  };
461 
462  AddRegionToWorklist(N);
463 
464  for (size_t I = 0; I < Worklist.size(); I++) {
465  for (DomTreeNode *Child : Worklist[I]->children())
466  AddRegionToWorklist(Child);
467  }
468 
469  return Worklist;
470 }
471 
473  LoopInfo *LI, MemorySSA *MSSA) {
474  assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
475  auto *Preheader = L->getLoopPreheader();
476  assert(Preheader && "Preheader should exist!");
477 
478  std::unique_ptr<MemorySSAUpdater> MSSAU;
479  if (MSSA)
480  MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
481 
482  // Now that we know the removal is safe, remove the loop by changing the
483  // branch from the preheader to go to the single exit block.
484  //
485  // Because we're deleting a large chunk of code at once, the sequence in which
486  // we remove things is very important to avoid invalidation issues.
487 
488  // Tell ScalarEvolution that the loop is deleted. Do this before
489  // deleting the loop so that ScalarEvolution can look at the loop
490  // to determine what it needs to clean up.
491  if (SE)
492  SE->forgetLoop(L);
493 
494  auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
495  assert(OldBr && "Preheader must end with a branch");
496  assert(OldBr->isUnconditional() && "Preheader must have a single successor");
497  // Connect the preheader to the exit block. Keep the old edge to the header
498  // around to perform the dominator tree update in two separate steps
499  // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
500  // preheader -> header.
501  //
502  //
503  // 0. Preheader 1. Preheader 2. Preheader
504  // | | | |
505  // V | V |
506  // Header <--\ | Header <--\ | Header <--\
507  // | | | | | | | | | | |
508  // | V | | | V | | | V |
509  // | Body --/ | | Body --/ | | Body --/
510  // V V V V V
511  // Exit Exit Exit
512  //
513  // By doing this is two separate steps we can perform the dominator tree
514  // update without using the batch update API.
515  //
516  // Even when the loop is never executed, we cannot remove the edge from the
517  // source block to the exit block. Consider the case where the unexecuted loop
518  // branches back to an outer loop. If we deleted the loop and removed the edge
519  // coming to this inner loop, this will break the outer loop structure (by
520  // deleting the backedge of the outer loop). If the outer loop is indeed a
521  // non-loop, it will be deleted in a future iteration of loop deletion pass.
522  IRBuilder<> Builder(OldBr);
523 
524  auto *ExitBlock = L->getUniqueExitBlock();
526  if (ExitBlock) {
527  assert(ExitBlock && "Should have a unique exit block!");
528  assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
529 
530  Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
531  // Remove the old branch. The conditional branch becomes a new terminator.
532  OldBr->eraseFromParent();
533 
534  // Rewrite phis in the exit block to get their inputs from the Preheader
535  // instead of the exiting block.
536  for (PHINode &P : ExitBlock->phis()) {
537  // Set the zero'th element of Phi to be from the preheader and remove all
538  // other incoming values. Given the loop has dedicated exits, all other
539  // incoming values must be from the exiting blocks.
540  int PredIndex = 0;
541  P.setIncomingBlock(PredIndex, Preheader);
542  // Removes all incoming values from all other exiting blocks (including
543  // duplicate values from an exiting block).
544  // Nuke all entries except the zero'th entry which is the preheader entry.
545  // NOTE! We need to remove Incoming Values in the reverse order as done
546  // below, to keep the indices valid for deletion (removeIncomingValues
547  // updates getNumIncomingValues and shifts all values down into the
548  // operand being deleted).
549  for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i)
550  P.removeIncomingValue(e - i, false);
551 
552  assert((P.getNumIncomingValues() == 1 &&
553  P.getIncomingBlock(PredIndex) == Preheader) &&
554  "Should have exactly one value and that's from the preheader!");
555  }
556 
557  if (DT) {
558  DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}});
559  if (MSSA) {
560  MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}},
561  *DT);
562  if (VerifyMemorySSA)
563  MSSA->verifyMemorySSA();
564  }
565  }
566 
567  // Disconnect the loop body by branching directly to its exit.
568  Builder.SetInsertPoint(Preheader->getTerminator());
569  Builder.CreateBr(ExitBlock);
570  // Remove the old branch.
571  Preheader->getTerminator()->eraseFromParent();
572  } else {
573  assert(L->hasNoExitBlocks() &&
574  "Loop should have either zero or one exit blocks.");
575 
576  Builder.SetInsertPoint(OldBr);
577  Builder.CreateUnreachable();
578  Preheader->getTerminator()->eraseFromParent();
579  }
580 
581  if (DT) {
582  DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}});
583  if (MSSA) {
584  MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}},
585  *DT);
587  L->block_end());
588  MSSAU->removeBlocks(DeadBlockSet);
589  if (VerifyMemorySSA)
590  MSSA->verifyMemorySSA();
591  }
592  }
593 
594  // Use a map to unique and a vector to guarantee deterministic ordering.
597 
598  if (ExitBlock) {
599  // Given LCSSA form is satisfied, we should not have users of instructions
600  // within the dead loop outside of the loop. However, LCSSA doesn't take
601  // unreachable uses into account. We handle them here.
602  // We could do it after drop all references (in this case all users in the
603  // loop will be already eliminated and we have less work to do but according
604  // to API doc of User::dropAllReferences only valid operation after dropping
605  // references, is deletion. So let's substitute all usages of
606  // instruction from the loop with undef value of corresponding type first.
607  for (auto *Block : L->blocks())
608  for (Instruction &I : *Block) {
609  auto *Undef = UndefValue::get(I.getType());
610  for (Use &U : llvm::make_early_inc_range(I.uses())) {
611  if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
612  if (L->contains(Usr->getParent()))
613  continue;
614  // If we have a DT then we can check that uses outside a loop only in
615  // unreachable block.
616  if (DT)
617  assert(!DT->isReachableFromEntry(U) &&
618  "Unexpected user in reachable block");
619  U.set(Undef);
620  }
621  auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);
622  if (!DVI)
623  continue;
624  auto Key =
625  DeadDebugSet.find({DVI->getVariable(), DVI->getExpression()});
626  if (Key != DeadDebugSet.end())
627  continue;
628  DeadDebugSet.insert({DVI->getVariable(), DVI->getExpression()});
629  DeadDebugInst.push_back(DVI);
630  }
631 
632  // After the loop has been deleted all the values defined and modified
633  // inside the loop are going to be unavailable.
634  // Since debug values in the loop have been deleted, inserting an undef
635  // dbg.value truncates the range of any dbg.value before the loop where the
636  // loop used to be. This is particularly important for constant values.
637  DIBuilder DIB(*ExitBlock->getModule());
638  Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI();
639  assert(InsertDbgValueBefore &&
640  "There should be a non-PHI instruction in exit block, else these "
641  "instructions will have no parent.");
642  for (auto *DVI : DeadDebugInst)
643  DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()),
644  DVI->getVariable(), DVI->getExpression(),
645  DVI->getDebugLoc(), InsertDbgValueBefore);
646  }
647 
648  // Remove the block from the reference counting scheme, so that we can
649  // delete it freely later.
650  for (auto *Block : L->blocks())
651  Block->dropAllReferences();
652 
653  if (MSSA && VerifyMemorySSA)
654  MSSA->verifyMemorySSA();
655 
656  if (LI) {
657  // Erase the instructions and the blocks without having to worry
658  // about ordering because we already dropped the references.
659  // NOTE: This iteration is safe because erasing the block does not remove
660  // its entry from the loop's block list. We do that in the next section.
661  for (BasicBlock *BB : L->blocks())
662  BB->eraseFromParent();
663 
664  // Finally, the blocks from loopinfo. This has to happen late because
665  // otherwise our loop iterators won't work.
666 
668  blocks.insert(L->block_begin(), L->block_end());
669  for (BasicBlock *BB : blocks)
670  LI->removeBlock(BB);
671 
672  // The last step is to update LoopInfo now that we've eliminated this loop.
673  // Note: LoopInfo::erase remove the given loop and relink its subloops with
674  // its parent. While removeLoop/removeChildLoop remove the given loop but
675  // not relink its subloops, which is what we want.
676  if (Loop *ParentLoop = L->getParentLoop()) {
677  Loop::iterator I = find(*ParentLoop, L);
678  assert(I != ParentLoop->end() && "Couldn't find loop");
679  ParentLoop->removeChildLoop(I);
680  } else {
681  Loop::iterator I = find(*LI, L);
682  assert(I != LI->end() && "Couldn't find loop");
683  LI->removeLoop(I);
684  }
685  LI->destroy(L);
686  }
687 }
688 
690  LoopInfo &LI, MemorySSA *MSSA) {
691  auto *Latch = L->getLoopLatch();
692  assert(Latch && "multiple latches not yet supported");
693  auto *Header = L->getHeader();
694  Loop *OutermostLoop = L->getOutermostLoop();
695 
696  SE.forgetLoop(L);
697 
698  std::unique_ptr<MemorySSAUpdater> MSSAU;
699  if (MSSA)
700  MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
701 
702  // Update the CFG and domtree. We chose to special case a couple of
703  // of common cases for code quality and test readability reasons.
704  [&]() -> void {
705  if (auto *BI = dyn_cast<BranchInst>(Latch->getTerminator())) {
706  if (!BI->isConditional()) {
708  (void)changeToUnreachable(BI, /*PreserveLCSSA*/ true, &DTU,
709  MSSAU.get());
710  return;
711  }
712 
713  // Conditional latch/exit - note that latch can be shared by inner
714  // and outer loop so the other target doesn't need to an exit
715  if (L->isLoopExiting(Latch)) {
716  // TODO: Generalize ConstantFoldTerminator so that it can be used
717  // here without invalidating LCSSA or MemorySSA. (Tricky case for
718  // LCSSA: header is an exit block of a preceeding sibling loop w/o
719  // dedicated exits.)
720  const unsigned ExitIdx = L->contains(BI->getSuccessor(0)) ? 1 : 0;
721  BasicBlock *ExitBB = BI->getSuccessor(ExitIdx);
722 
724  Header->removePredecessor(Latch, true);
725 
726  IRBuilder<> Builder(BI);
727  auto *NewBI = Builder.CreateBr(ExitBB);
728  // Transfer the metadata to the new branch instruction (minus the
729  // loop info since this is no longer a loop)
730  NewBI->copyMetadata(*BI, {LLVMContext::MD_dbg,
731  LLVMContext::MD_annotation});
732 
733  BI->eraseFromParent();
734  DTU.applyUpdates({{DominatorTree::Delete, Latch, Header}});
735  if (MSSA)
736  MSSAU->applyUpdates({{DominatorTree::Delete, Latch, Header}}, DT);
737  return;
738  }
739  }
740 
741  // General case. By splitting the backedge, and then explicitly making it
742  // unreachable we gracefully handle corner cases such as switch and invoke
743  // termiantors.
744  auto *BackedgeBB = SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());
745 
747  (void)changeToUnreachable(BackedgeBB->getTerminator(),
748  /*PreserveLCSSA*/ true, &DTU, MSSAU.get());
749  }();
750 
751  // Erase (and destroy) this loop instance. Handles relinking sub-loops
752  // and blocks within the loop as needed.
753  LI.erase(L);
754 
755  // If the loop we broke had a parent, then changeToUnreachable might have
756  // caused a block to be removed from the parent loop (see loop_nest_lcssa
757  // test case in zero-btc.ll for an example), thus changing the parent's
758  // exit blocks. If that happened, we need to rebuild LCSSA on the outermost
759  // loop which might have a had a block removed.
760  if (OutermostLoop != L)
761  formLCSSARecursively(*OutermostLoop, DT, &LI, &SE);
762 }
763 
764 
765 /// Checks if \p L has an exiting latch branch. There may also be other
766 /// exiting blocks. Returns branch instruction terminating the loop
767 /// latch if above check is successful, nullptr otherwise.
769  BasicBlock *Latch = L->getLoopLatch();
770  if (!Latch)
771  return nullptr;
772 
773  BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
774  if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
775  return nullptr;
776 
777  assert((LatchBR->getSuccessor(0) == L->getHeader() ||
778  LatchBR->getSuccessor(1) == L->getHeader()) &&
779  "At least one edge out of the latch must go to the header");
780 
781  return LatchBR;
782 }
783 
784 /// Return the estimated trip count for any exiting branch which dominates
785 /// the loop latch.
786 static Optional<uint64_t>
788  uint64_t &OrigExitWeight) {
789  // To estimate the number of times the loop body was executed, we want to
790  // know the number of times the backedge was taken, vs. the number of times
791  // we exited the loop.
792  uint64_t LoopWeight, ExitWeight;
793  if (!ExitingBranch->extractProfMetadata(LoopWeight, ExitWeight))
794  return None;
795 
796  if (L->contains(ExitingBranch->getSuccessor(1)))
797  std::swap(LoopWeight, ExitWeight);
798 
799  if (!ExitWeight)
800  // Don't have a way to return predicated infinite
801  return None;
802 
803  OrigExitWeight = ExitWeight;
804 
805  // Estimated exit count is a ratio of the loop weight by the weight of the
806  // edge exiting the loop, rounded to nearest.
807  uint64_t ExitCount = llvm::divideNearest(LoopWeight, ExitWeight);
808  // Estimated trip count is one plus estimated exit count.
809  return ExitCount + 1;
810 }
811 
814  unsigned *EstimatedLoopInvocationWeight) {
815  // Currently we take the estimate exit count only from the loop latch,
816  // ignoring other exiting blocks. This can overestimate the trip count
817  // if we exit through another exit, but can never underestimate it.
818  // TODO: incorporate information from other exits
819  if (BranchInst *LatchBranch = getExpectedExitLoopLatchBranch(L)) {
820  uint64_t ExitWeight;
821  if (Optional<uint64_t> EstTripCount =
822  getEstimatedTripCount(LatchBranch, L, ExitWeight)) {
823  if (EstimatedLoopInvocationWeight)
824  *EstimatedLoopInvocationWeight = ExitWeight;
825  return *EstTripCount;
826  }
827  }
828  return None;
829 }
830 
831 bool llvm::setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,
832  unsigned EstimatedloopInvocationWeight) {
833  // At the moment, we currently support changing the estimate trip count of
834  // the latch branch only. We could extend this API to manipulate estimated
835  // trip counts for any exit.
836  BranchInst *LatchBranch = getExpectedExitLoopLatchBranch(L);
837  if (!LatchBranch)
838  return false;
839 
840  // Calculate taken and exit weights.
841  unsigned LatchExitWeight = 0;
842  unsigned BackedgeTakenWeight = 0;
843 
844  if (EstimatedTripCount > 0) {
845  LatchExitWeight = EstimatedloopInvocationWeight;
846  BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight;
847  }
848 
849  // Make a swap if back edge is taken when condition is "false".
850  if (LatchBranch->getSuccessor(0) != L->getHeader())
851  std::swap(BackedgeTakenWeight, LatchExitWeight);
852 
853  MDBuilder MDB(LatchBranch->getContext());
854 
855  // Set/Update profile metadata.
856  LatchBranch->setMetadata(
857  LLVMContext::MD_prof,
858  MDB.createBranchWeights(BackedgeTakenWeight, LatchExitWeight));
859 
860  return true;
861 }
862 
864  ScalarEvolution &SE) {
865  Loop *OuterL = InnerLoop->getParentLoop();
866  if (!OuterL)
867  return true;
868 
869  // Get the backedge taken count for the inner loop
870  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
871  const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
872  if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
873  !InnerLoopBECountSC->getType()->isIntegerTy())
874  return false;
875 
876  // Get whether count is invariant to the outer loop
878  SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
880  return false;
881 
882  return true;
883 }
884 
886  switch (RK) {
887  default:
888  llvm_unreachable("Unknown min/max recurrence kind");
889  case RecurKind::UMin:
890  return CmpInst::ICMP_ULT;
891  case RecurKind::UMax:
892  return CmpInst::ICMP_UGT;
893  case RecurKind::SMin:
894  return CmpInst::ICMP_SLT;
895  case RecurKind::SMax:
896  return CmpInst::ICMP_SGT;
897  case RecurKind::FMin:
898  return CmpInst::FCMP_OLT;
899  case RecurKind::FMax:
900  return CmpInst::FCMP_OGT;
901  }
902 }
903 
905  RecurKind RK, Value *Left, Value *Right) {
906  if (auto VTy = dyn_cast<VectorType>(Left->getType()))
907  StartVal = Builder.CreateVectorSplat(VTy->getElementCount(), StartVal);
908  Value *Cmp =
909  Builder.CreateCmp(CmpInst::ICMP_NE, Left, StartVal, "rdx.select.cmp");
910  return Builder.CreateSelect(Cmp, Left, Right, "rdx.select");
911 }
912 
914  Value *Right) {
916  Value *Cmp = Builder.CreateCmp(Pred, Left, Right, "rdx.minmax.cmp");
917  Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
918  return Select;
919 }
920 
921 // Helper to generate an ordered reduction.
923  unsigned Op, RecurKind RdxKind) {
924  unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
925 
926  // Extract and apply reduction ops in ascending order:
927  // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
928  Value *Result = Acc;
929  for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
930  Value *Ext =
931  Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
932 
933  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
934  Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
935  "bin.rdx");
936  } else {
938  "Invalid min/max");
939  Result = createMinMaxOp(Builder, RdxKind, Result, Ext);
940  }
941  }
942 
943  return Result;
944 }
945 
946 // Helper to generate a log2 shuffle reduction.
948  unsigned Op, RecurKind RdxKind) {
949  unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
950  // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
951  // and vector ops, reducing the set of values being computed by half each
952  // round.
953  assert(isPowerOf2_32(VF) &&
954  "Reduction emission only supported for pow2 vectors!");
955  // Note: fast-math-flags flags are controlled by the builder configuration
956  // and are assumed to apply to all generated arithmetic instructions. Other
957  // poison generating flags (nsw/nuw/inbounds/inrange/exact) are not part
958  // of the builder configuration, and since they're not passed explicitly,
959  // will never be relevant here. Note that it would be generally unsound to
960  // propagate these from an intrinsic call to the expansion anyways as we/
961  // change the order of operations.
962  Value *TmpVec = Src;
963  SmallVector<int, 32> ShuffleMask(VF);
964  for (unsigned i = VF; i != 1; i >>= 1) {
965  // Move the upper half of the vector to the lower half.
966  for (unsigned j = 0; j != i / 2; ++j)
967  ShuffleMask[j] = i / 2 + j;
968 
969  // Fill the rest of the mask with undef.
970  std::fill(&ShuffleMask[i / 2], ShuffleMask.end(), -1);
971 
972  Value *Shuf = Builder.CreateShuffleVector(TmpVec, ShuffleMask, "rdx.shuf");
973 
974  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
975  TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
976  "bin.rdx");
977  } else {
979  "Invalid min/max");
980  TmpVec = createMinMaxOp(Builder, RdxKind, TmpVec, Shuf);
981  }
982  }
983  // The result is in the first element of the vector.
984  return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
985 }
986 
988  const TargetTransformInfo *TTI,
989  Value *Src,
990  const RecurrenceDescriptor &Desc,
991  PHINode *OrigPhi) {
993  Desc.getRecurrenceKind()) &&
994  "Unexpected reduction kind");
995  Value *InitVal = Desc.getRecurrenceStartValue();
996  Value *NewVal = nullptr;
997 
998  // First use the original phi to determine the new value we're trying to
999  // select from in the loop.
1000  SelectInst *SI = nullptr;
1001  for (auto *U : OrigPhi->users()) {
1002  if ((SI = dyn_cast<SelectInst>(U)))
1003  break;
1004  }
1005  assert(SI && "One user of the original phi should be a select");
1006 
1007  if (SI->getTrueValue() == OrigPhi)
1008  NewVal = SI->getFalseValue();
1009  else {
1010  assert(SI->getFalseValue() == OrigPhi &&
1011  "At least one input to the select should be the original Phi");
1012  NewVal = SI->getTrueValue();
1013  }
1014 
1015  // Create a splat vector with the new value and compare this to the vector
1016  // we want to reduce.
1017  ElementCount EC = cast<VectorType>(Src->getType())->getElementCount();
1018  Value *Right = Builder.CreateVectorSplat(EC, InitVal);
1019  Value *Cmp =
1020  Builder.CreateCmp(CmpInst::ICMP_NE, Src, Right, "rdx.select.cmp");
1021 
1022  // If any predicate is true it means that we want to select the new value.
1023  Cmp = Builder.CreateOrReduce(Cmp);
1024  return Builder.CreateSelect(Cmp, NewVal, InitVal, "rdx.select");
1025 }
1026 
1028  const TargetTransformInfo *TTI,
1029  Value *Src, RecurKind RdxKind) {
1030  auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
1031  switch (RdxKind) {
1032  case RecurKind::Add:
1033  return Builder.CreateAddReduce(Src);
1034  case RecurKind::Mul:
1035  return Builder.CreateMulReduce(Src);
1036  case RecurKind::And:
1037  return Builder.CreateAndReduce(Src);
1038  case RecurKind::Or:
1039  return Builder.CreateOrReduce(Src);
1040  case RecurKind::Xor:
1041  return Builder.CreateXorReduce(Src);
1042  case RecurKind::FMulAdd:
1043  case RecurKind::FAdd:
1044  return Builder.CreateFAddReduce(ConstantFP::getNegativeZero(SrcVecEltTy),
1045  Src);
1046  case RecurKind::FMul:
1047  return Builder.CreateFMulReduce(ConstantFP::get(SrcVecEltTy, 1.0), Src);
1048  case RecurKind::SMax:
1049  return Builder.CreateIntMaxReduce(Src, true);
1050  case RecurKind::SMin:
1051  return Builder.CreateIntMinReduce(Src, true);
1052  case RecurKind::UMax:
1053  return Builder.CreateIntMaxReduce(Src, false);
1054  case RecurKind::UMin:
1055  return Builder.CreateIntMinReduce(Src, false);
1056  case RecurKind::FMax:
1057  return Builder.CreateFPMaxReduce(Src);
1058  case RecurKind::FMin:
1059  return Builder.CreateFPMinReduce(Src);
1060  default:
1061  llvm_unreachable("Unhandled opcode");
1062  }
1063 }
1064 
1066  const TargetTransformInfo *TTI,
1067  const RecurrenceDescriptor &Desc, Value *Src,
1068  PHINode *OrigPhi) {
1069  // TODO: Support in-order reductions based on the recurrence descriptor.
1070  // All ops in the reduction inherit fast-math-flags from the recurrence
1071  // descriptor.
1073  B.setFastMathFlags(Desc.getFastMathFlags());
1074 
1075  RecurKind RK = Desc.getRecurrenceKind();
1077  return createSelectCmpTargetReduction(B, TTI, Src, Desc, OrigPhi);
1078 
1079  return createSimpleTargetReduction(B, TTI, Src, RK);
1080 }
1081 
1083  const RecurrenceDescriptor &Desc,
1084  Value *Src, Value *Start) {
1087  "Unexpected reduction kind");
1088  assert(Src->getType()->isVectorTy() && "Expected a vector type");
1089  assert(!Start->getType()->isVectorTy() && "Expected a scalar type");
1090 
1091  return B.CreateFAddReduce(Start, Src);
1092 }
1093 
1095  bool IncludeWrapFlags) {
1096  auto *VecOp = dyn_cast<Instruction>(I);
1097  if (!VecOp)
1098  return;
1099  auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
1100  : dyn_cast<Instruction>(OpValue);
1101  if (!Intersection)
1102  return;
1103  const unsigned Opcode = Intersection->getOpcode();
1104  VecOp->copyIRFlags(Intersection, IncludeWrapFlags);
1105  for (auto *V : VL) {
1106  auto *Instr = dyn_cast<Instruction>(V);
1107  if (!Instr)
1108  continue;
1109  if (OpValue == nullptr || Opcode == Instr->getOpcode())
1110  VecOp->andIRFlags(V);
1111  }
1112 }
1113 
1114 bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
1115  ScalarEvolution &SE) {
1116  const SCEV *Zero = SE.getZero(S->getType());
1117  return SE.isAvailableAtLoopEntry(S, L) &&
1119 }
1120 
1122  ScalarEvolution &SE) {
1123  const SCEV *Zero = SE.getZero(S->getType());
1124  return SE.isAvailableAtLoopEntry(S, L) &&
1126 }
1127 
1129  bool Signed) {
1130  unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1134  return SE.isAvailableAtLoopEntry(S, L) &&
1136  SE.getConstant(Min));
1137 }
1138 
1140  bool Signed) {
1141  unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1145  return SE.isAvailableAtLoopEntry(S, L) &&
1147  SE.getConstant(Max));
1148 }
1149 
1150 //===----------------------------------------------------------------------===//
1151 // rewriteLoopExitValues - Optimize IV users outside the loop.
1152 // As a side effect, reduces the amount of IV processing within the loop.
1153 //===----------------------------------------------------------------------===//
1154 
1155 static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) {
1158  Visited.insert(I);
1159  WorkList.push_back(I);
1160  while (!WorkList.empty()) {
1161  const Instruction *Curr = WorkList.pop_back_val();
1162  // This use is outside the loop, nothing to do.
1163  if (!L->contains(Curr))
1164  continue;
1165  // Do we assume it is a "hard" use which will not be eliminated easily?
1166  if (Curr->mayHaveSideEffects())
1167  return true;
1168  // Otherwise, add all its users to worklist.
1169  for (auto U : Curr->users()) {
1170  auto *UI = cast<Instruction>(U);
1171  if (Visited.insert(UI).second)
1172  WorkList.push_back(UI);
1173  }
1174  }
1175  return false;
1176 }
1177 
1178 // Collect information about PHI nodes which can be transformed in
1179 // rewriteLoopExitValues.
1180 struct RewritePhi {
1181  PHINode *PN; // For which PHI node is this replacement?
1182  unsigned Ith; // For which incoming value?
1183  const SCEV *ExpansionSCEV; // The SCEV of the incoming value we are rewriting.
1184  Instruction *ExpansionPoint; // Where we'd like to expand that SCEV?
1185  bool HighCost; // Is this expansion a high-cost?
1186 
1187  RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt,
1188  bool H)
1189  : PN(P), Ith(I), ExpansionSCEV(Val), ExpansionPoint(ExpansionPt),
1190  HighCost(H) {}
1191 };
1192 
1193 // Check whether it is possible to delete the loop after rewriting exit
1194 // value. If it is possible, ignore ReplaceExitValue and do rewriting
1195 // aggressively.
1196 static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
1197  BasicBlock *Preheader = L->getLoopPreheader();
1198  // If there is no preheader, the loop will not be deleted.
1199  if (!Preheader)
1200  return false;
1201 
1202  // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
1203  // We obviate multiple ExitingBlocks case for simplicity.
1204  // TODO: If we see testcase with multiple ExitingBlocks can be deleted
1205  // after exit value rewriting, we can enhance the logic here.
1206  SmallVector<BasicBlock *, 4> ExitingBlocks;
1207  L->getExitingBlocks(ExitingBlocks);
1208  SmallVector<BasicBlock *, 8> ExitBlocks;
1209  L->getUniqueExitBlocks(ExitBlocks);
1210  if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1)
1211  return false;
1212 
1213  BasicBlock *ExitBlock = ExitBlocks[0];
1214  BasicBlock::iterator BI = ExitBlock->begin();
1215  while (PHINode *P = dyn_cast<PHINode>(BI)) {
1216  Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
1217 
1218  // If the Incoming value of P is found in RewritePhiSet, we know it
1219  // could be rewritten to use a loop invariant value in transformation
1220  // phase later. Skip it in the loop invariant check below.
1221  bool found = false;
1222  for (const RewritePhi &Phi : RewritePhiSet) {
1223  unsigned i = Phi.Ith;
1224  if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
1225  found = true;
1226  break;
1227  }
1228  }
1229 
1230  Instruction *I;
1231  if (!found && (I = dyn_cast<Instruction>(Incoming)))
1232  if (!L->hasLoopInvariantOperands(I))
1233  return false;
1234 
1235  ++BI;
1236  }
1237 
1238  for (auto *BB : L->blocks())
1239  if (llvm::any_of(*BB, [](Instruction &I) {
1240  return I.mayHaveSideEffects();
1241  }))
1242  return false;
1243 
1244  return true;
1245 }
1246 
1248  ScalarEvolution *SE,
1249  const TargetTransformInfo *TTI,
1252  SmallVector<WeakTrackingVH, 16> &DeadInsts) {
1253  // Check a pre-condition.
1254  assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1255  "Indvars did not preserve LCSSA!");
1256 
1257  SmallVector<BasicBlock*, 8> ExitBlocks;
1258  L->getUniqueExitBlocks(ExitBlocks);
1259 
1260  SmallVector<RewritePhi, 8> RewritePhiSet;
1261  // Find all values that are computed inside the loop, but used outside of it.
1262  // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
1263  // the exit blocks of the loop to find them.
1264  for (BasicBlock *ExitBB : ExitBlocks) {
1265  // If there are no PHI nodes in this exit block, then no values defined
1266  // inside the loop are used on this path, skip it.
1267  PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1268  if (!PN) continue;
1269 
1270  unsigned NumPreds = PN->getNumIncomingValues();
1271 
1272  // Iterate over all of the PHI nodes.
1273  BasicBlock::iterator BBI = ExitBB->begin();
1274  while ((PN = dyn_cast<PHINode>(BBI++))) {
1275  if (PN->use_empty())
1276  continue; // dead use, don't replace it
1277 
1278  if (!SE->isSCEVable(PN->getType()))
1279  continue;
1280 
1281  // Iterate over all of the values in all the PHI nodes.
1282  for (unsigned i = 0; i != NumPreds; ++i) {
1283  // If the value being merged in is not integer or is not defined
1284  // in the loop, skip it.
1285  Value *InVal = PN->getIncomingValue(i);
1286  if (!isa<Instruction>(InVal))
1287  continue;
1288 
1289  // If this pred is for a subloop, not L itself, skip it.
1290  if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
1291  continue; // The Block is in a subloop, skip it.
1292 
1293  // Check that InVal is defined in the loop.
1294  Instruction *Inst = cast<Instruction>(InVal);
1295  if (!L->contains(Inst))
1296  continue;
1297 
1298  // Okay, this instruction has a user outside of the current loop
1299  // and varies predictably *inside* the loop. Evaluate the value it
1300  // contains when the loop exits, if possible. We prefer to start with
1301  // expressions which are true for all exits (so as to maximize
1302  // expression reuse by the SCEVExpander), but resort to per-exit
1303  // evaluation if that fails.
1304  const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
1305  if (isa<SCEVCouldNotCompute>(ExitValue) ||
1306  !SE->isLoopInvariant(ExitValue, L) ||
1307  !isSafeToExpand(ExitValue, *SE)) {
1308  // TODO: This should probably be sunk into SCEV in some way; maybe a
1309  // getSCEVForExit(SCEV*, L, ExitingBB)? It can be generalized for
1310  // most SCEV expressions and other recurrence types (e.g. shift
1311  // recurrences). Is there existing code we can reuse?
1312  const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i));
1313  if (isa<SCEVCouldNotCompute>(ExitCount))
1314  continue;
1315  if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Inst)))
1316  if (AddRec->getLoop() == L)
1317  ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1318  if (isa<SCEVCouldNotCompute>(ExitValue) ||
1319  !SE->isLoopInvariant(ExitValue, L) ||
1320  !isSafeToExpand(ExitValue, *SE))
1321  continue;
1322  }
1323 
1324  // Computing the value outside of the loop brings no benefit if it is
1325  // definitely used inside the loop in a way which can not be optimized
1326  // away. Avoid doing so unless we know we have a value which computes
1327  // the ExitValue already. TODO: This should be merged into SCEV
1328  // expander to leverage its knowledge of existing expressions.
1329  if (ReplaceExitValue != AlwaysRepl && !isa<SCEVConstant>(ExitValue) &&
1330  !isa<SCEVUnknown>(ExitValue) && hasHardUserWithinLoop(L, Inst))
1331  continue;
1332 
1333  // Check if expansions of this SCEV would count as being high cost.
1334  bool HighCost = Rewriter.isHighCostExpansion(
1335  ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst);
1336 
1337  // Note that we must not perform expansions until after
1338  // we query *all* the costs, because if we perform temporary expansion
1339  // inbetween, one that we might not intend to keep, said expansion
1340  // *may* affect cost calculation of the the next SCEV's we'll query,
1341  // and next SCEV may errneously get smaller cost.
1342 
1343  // Collect all the candidate PHINodes to be rewritten.
1344  RewritePhiSet.emplace_back(PN, i, ExitValue, Inst, HighCost);
1345  }
1346  }
1347  }
1348 
1349  // TODO: evaluate whether it is beneficial to change how we calculate
1350  // high-cost: if we have SCEV 'A' which we know we will expand, should we
1351  // calculate the cost of other SCEV's after expanding SCEV 'A', thus
1352  // potentially giving cost bonus to those other SCEV's?
1353 
1354  bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
1355  int NumReplaced = 0;
1356 
1357  // Transformation.
1358  for (const RewritePhi &Phi : RewritePhiSet) {
1359  PHINode *PN = Phi.PN;
1360 
1361  // Only do the rewrite when the ExitValue can be expanded cheaply.
1362  // If LoopCanBeDel is true, rewrite exit value aggressively.
1363  if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost)
1364  continue;
1365 
1366  Value *ExitVal = Rewriter.expandCodeFor(
1367  Phi.ExpansionSCEV, Phi.PN->getType(), Phi.ExpansionPoint);
1368 
1369  LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
1370  << '\n'
1371  << " LoopVal = " << *(Phi.ExpansionPoint) << "\n");
1372 
1373 #ifndef NDEBUG
1374  // If we reuse an instruction from a loop which is neither L nor one of
1375  // its containing loops, we end up breaking LCSSA form for this loop by
1376  // creating a new use of its instruction.
1377  if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
1378  if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
1379  if (EVL != L)
1380  assert(EVL->contains(L) && "LCSSA breach detected!");
1381 #endif
1382 
1383  NumReplaced++;
1384  Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
1385  PN->setIncomingValue(Phi.Ith, ExitVal);
1386  // It's necessary to tell ScalarEvolution about this explicitly so that
1387  // it can walk the def-use list and forget all SCEVs, as it may not be
1388  // watching the PHI itself. Once the new exit value is in place, there
1389  // may not be a def-use connection between the loop and every instruction
1390  // which got a SCEVAddRecExpr for that loop.
1391  SE->forgetValue(PN);
1392 
1393  // If this instruction is dead now, delete it. Don't do it now to avoid
1394  // invalidating iterators.
1395  if (isInstructionTriviallyDead(Inst, TLI))
1396  DeadInsts.push_back(Inst);
1397 
1398  // Replace PN with ExitVal if that is legal and does not break LCSSA.
1399  if (PN->getNumIncomingValues() == 1 &&
1400  LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
1401  PN->replaceAllUsesWith(ExitVal);
1402  PN->eraseFromParent();
1403  }
1404  }
1405 
1406  // The insertion point instruction may have been deleted; clear it out
1407  // so that the rewriter doesn't trip over it later.
1408  Rewriter.clearInsertPoint();
1409  return NumReplaced;
1410 }
1411 
1412 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
1413 /// \p OrigLoop.
1414 void llvm::setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
1415  Loop *RemainderLoop, uint64_t UF) {
1416  assert(UF > 0 && "Zero unrolled factor is not supported");
1417  assert(UnrolledLoop != RemainderLoop &&
1418  "Unrolled and Remainder loops are expected to distinct");
1419 
1420  // Get number of iterations in the original scalar loop.
1421  unsigned OrigLoopInvocationWeight = 0;
1422  Optional<unsigned> OrigAverageTripCount =
1423  getLoopEstimatedTripCount(OrigLoop, &OrigLoopInvocationWeight);
1424  if (!OrigAverageTripCount)
1425  return;
1426 
1427  // Calculate number of iterations in unrolled loop.
1428  unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1429  // Calculate number of iterations for remainder loop.
1430  unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1431 
1432  setLoopEstimatedTripCount(UnrolledLoop, UnrolledAverageTripCount,
1433  OrigLoopInvocationWeight);
1434  setLoopEstimatedTripCount(RemainderLoop, RemainderAverageTripCount,
1435  OrigLoopInvocationWeight);
1436 }
1437 
1438 /// Utility that implements appending of loops onto a worklist.
1439 /// Loops are added in preorder (analogous for reverse postorder for trees),
1440 /// and the worklist is processed LIFO.
1441 template <typename RangeT>
1443  RangeT &&Loops, SmallPriorityWorklist<Loop *, 4> &Worklist) {
1444  // We use an internal worklist to build up the preorder traversal without
1445  // recursion.
1446  SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
1447 
1448  // We walk the initial sequence of loops in reverse because we generally want
1449  // to visit defs before uses and the worklist is LIFO.
1450  for (Loop *RootL : Loops) {
1451  assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
1452  assert(PreOrderWorklist.empty() &&
1453  "Must start with an empty preorder walk worklist.");
1454  PreOrderWorklist.push_back(RootL);
1455  do {
1456  Loop *L = PreOrderWorklist.pop_back_val();
1457  PreOrderWorklist.append(L->begin(), L->end());
1458  PreOrderLoops.push_back(L);
1459  } while (!PreOrderWorklist.empty());
1460 
1461  Worklist.insert(std::move(PreOrderLoops));
1462  PreOrderLoops.clear();
1463  }
1464 }
1465 
1466 template <typename RangeT>
1470 }
1471 
1472 template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1474 
1475 template void
1476 llvm::appendLoopsToWorklist<Loop &>(Loop &L,
1478 
1481  appendReversedLoopsToWorklist(LI, Worklist);
1482 }
1483 
1485  LoopInfo *LI, LPPassManager *LPM) {
1486  Loop &New = *LI->AllocateLoop();
1487  if (PL)
1488  PL->addChildLoop(&New);
1489  else
1490  LI->addTopLevelLoop(&New);
1491 
1492  if (LPM)
1493  LPM->addLoop(New);
1494 
1495  // Add all of the blocks in L to the new loop.
1496  for (BasicBlock *BB : L->blocks())
1497  if (LI->getLoopFor(BB) == L)
1498  New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), *LI);
1499 
1500  // Add all of the subloops to the new loop.
1501  for (Loop *I : *L)
1502  cloneLoop(I, &New, VM, LI, LPM);
1503 
1504  return &New;
1505 }
1506 
1507 /// IR Values for the lower and upper bounds of a pointer evolution. We
1508 /// need to use value-handles because SCEV expansion can invalidate previously
1509 /// expanded values. Thus expansion of a pointer can invalidate the bounds for
1510 /// a previous one.
1514 };
1515 
1516 /// Expand code for the lower and upper bound of the pointer group \p CG
1517 /// in \p TheLoop. \return the values for the bounds.
1519  Loop *TheLoop, Instruction *Loc,
1520  SCEVExpander &Exp) {
1521  LLVMContext &Ctx = Loc->getContext();
1522  Type *PtrArithTy = Type::getInt8PtrTy(Ctx, CG->AddressSpace);
1523 
1524  Value *Start = nullptr, *End = nullptr;
1525  LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
1526  Start = Exp.expandCodeFor(CG->Low, PtrArithTy, Loc);
1527  End = Exp.expandCodeFor(CG->High, PtrArithTy, Loc);
1528  if (CG->NeedsFreeze) {
1529  IRBuilder<> Builder(Loc);
1530  Start = Builder.CreateFreeze(Start, Start->getName() + ".fr");
1531  End = Builder.CreateFreeze(End, End->getName() + ".fr");
1532  }
1533  LLVM_DEBUG(dbgs() << "Start: " << *CG->Low << " End: " << *CG->High << "\n");
1534  return {Start, End};
1535 }
1536 
1537 /// Turns a collection of checks into a collection of expanded upper and
1538 /// lower bounds for both pointers in the check.
1541  Instruction *Loc, SCEVExpander &Exp) {
1543 
1544  // Here we're relying on the SCEV Expander's cache to only emit code for the
1545  // same bounds once.
1546  transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1547  [&](const RuntimePointerCheck &Check) {
1548  PointerBounds First = expandBounds(Check.first, L, Loc, Exp),
1549  Second = expandBounds(Check.second, L, Loc, Exp);
1550  return std::make_pair(First, Second);
1551  });
1552 
1553  return ChecksWithBounds;
1554 }
1555 
1557  Instruction *Loc, Loop *TheLoop,
1558  const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
1559  SCEVExpander &Exp) {
1560  // TODO: Move noalias annotation code from LoopVersioning here and share with LV if possible.
1561  // TODO: Pass RtPtrChecking instead of PointerChecks and SE separately, if possible
1562  auto ExpandedChecks = expandBounds(PointerChecks, TheLoop, Loc, Exp);
1563 
1564  LLVMContext &Ctx = Loc->getContext();
1565  IRBuilder<InstSimplifyFolder> ChkBuilder(Ctx,
1566  Loc->getModule()->getDataLayout());
1567  ChkBuilder.SetInsertPoint(Loc);
1568  // Our instructions might fold to a constant.
1569  Value *MemoryRuntimeCheck = nullptr;
1570 
1571  for (const auto &Check : ExpandedChecks) {
1572  const PointerBounds &A = Check.first, &B = Check.second;
1573  // Check if two pointers (A and B) conflict where conflict is computed as:
1574  // start(A) <= end(B) && start(B) <= end(A)
1575  unsigned AS0 = A.Start->getType()->getPointerAddressSpace();
1576  unsigned AS1 = B.Start->getType()->getPointerAddressSpace();
1577 
1578  assert((AS0 == B.End->getType()->getPointerAddressSpace()) &&
1579  (AS1 == A.End->getType()->getPointerAddressSpace()) &&
1580  "Trying to bounds check pointers with different address spaces");
1581 
1582  Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
1583  Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
1584 
1585  Value *Start0 = ChkBuilder.CreateBitCast(A.Start, PtrArithTy0, "bc");
1586  Value *Start1 = ChkBuilder.CreateBitCast(B.Start, PtrArithTy1, "bc");
1587  Value *End0 = ChkBuilder.CreateBitCast(A.End, PtrArithTy1, "bc");
1588  Value *End1 = ChkBuilder.CreateBitCast(B.End, PtrArithTy0, "bc");
1589 
1590  // [A|B].Start points to the first accessed byte under base [A|B].
1591  // [A|B].End points to the last accessed byte, plus one.
1592  // There is no conflict when the intervals are disjoint:
1593  // NoConflict = (B.Start >= A.End) || (A.Start >= B.End)
1594  //
1595  // bound0 = (B.Start < A.End)
1596  // bound1 = (A.Start < B.End)
1597  // IsConflict = bound0 & bound1
1598  Value *Cmp0 = ChkBuilder.CreateICmpULT(Start0, End1, "bound0");
1599  Value *Cmp1 = ChkBuilder.CreateICmpULT(Start1, End0, "bound1");
1600  Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
1601  if (MemoryRuntimeCheck) {
1602  IsConflict =
1603  ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
1604  }
1605  MemoryRuntimeCheck = IsConflict;
1606  }
1607 
1608  return MemoryRuntimeCheck;
1609 }
1610 
1612  Instruction *Loc, Loop *TheLoop, ArrayRef<PointerDiffInfo> Checks,
1613  SCEVExpander &Expander,
1614  function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC) {
1615 
1616  LLVMContext &Ctx = Loc->getContext();
1617  IRBuilder<InstSimplifyFolder> ChkBuilder(Ctx,
1618  Loc->getModule()->getDataLayout());
1619  ChkBuilder.SetInsertPoint(Loc);
1620  // Our instructions might fold to a constant.
1621  Value *MemoryRuntimeCheck = nullptr;
1622 
1623  for (auto &C : Checks) {
1624  Type *Ty = C.SinkStart->getType();
1625  // Compute VF * IC * AccessSize.
1626  auto *VFTimesUFTimesSize =
1627  ChkBuilder.CreateMul(GetVF(ChkBuilder, Ty->getScalarSizeInBits()),
1628  ConstantInt::get(Ty, IC * C.AccessSize));
1629  Value *Sink = Expander.expandCodeFor(C.SinkStart, Ty, Loc);
1630  Value *Src = Expander.expandCodeFor(C.SrcStart, Ty, Loc);
1631  if (C.NeedsFreeze) {
1632  IRBuilder<> Builder(Loc);
1633  Sink = Builder.CreateFreeze(Sink, Sink->getName() + ".fr");
1634  Src = Builder.CreateFreeze(Src, Src->getName() + ".fr");
1635  }
1636  Value *Diff = ChkBuilder.CreateSub(Sink, Src);
1637  Value *IsConflict =
1638  ChkBuilder.CreateICmpULT(Diff, VFTimesUFTimesSize, "diff.check");
1639 
1640  if (MemoryRuntimeCheck) {
1641  IsConflict =
1642  ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
1643  }
1644  MemoryRuntimeCheck = IsConflict;
1645  }
1646 
1647  return MemoryRuntimeCheck;
1648 }
1649 
1651  unsigned MSSAThreshold,
1652  MemorySSA &MSSA,
1653  AAResults &AA) {
1654  auto *TI = dyn_cast<BranchInst>(L.getHeader()->getTerminator());
1655  if (!TI || !TI->isConditional())
1656  return {};
1657 
1658  auto *CondI = dyn_cast<CmpInst>(TI->getCondition());
1659  // The case with the condition outside the loop should already be handled
1660  // earlier.
1661  if (!CondI || !L.contains(CondI))
1662  return {};
1663 
1664  SmallVector<Instruction *> InstToDuplicate;
1665  InstToDuplicate.push_back(CondI);
1666 
1667  SmallVector<Value *, 4> WorkList;
1668  WorkList.append(CondI->op_begin(), CondI->op_end());
1669 
1670  SmallVector<MemoryAccess *, 4> AccessesToCheck;
1671  SmallVector<MemoryLocation, 4> AccessedLocs;
1672  while (!WorkList.empty()) {
1673  Instruction *I = dyn_cast<Instruction>(WorkList.pop_back_val());
1674  if (!I || !L.contains(I))
1675  continue;
1676 
1677  // TODO: support additional instructions.
1678  if (!isa<LoadInst>(I) && !isa<GetElementPtrInst>(I))
1679  return {};
1680 
1681  // Do not duplicate volatile and atomic loads.
1682  if (auto *LI = dyn_cast<LoadInst>(I))
1683  if (LI->isVolatile() || LI->isAtomic())
1684  return {};
1685 
1686  InstToDuplicate.push_back(I);
1687  if (MemoryAccess *MA = MSSA.getMemoryAccess(I)) {
1688  if (auto *MemUse = dyn_cast_or_null<MemoryUse>(MA)) {
1689  // Queue the defining access to check for alias checks.
1690  AccessesToCheck.push_back(MemUse->getDefiningAccess());
1691  AccessedLocs.push_back(MemoryLocation::get(I));
1692  } else {
1693  // MemoryDefs may clobber the location or may be atomic memory
1694  // operations. Bail out.
1695  return {};
1696  }
1697  }
1698  WorkList.append(I->op_begin(), I->op_end());
1699  }
1700 
1701  if (InstToDuplicate.empty())
1702  return {};
1703 
1704  SmallVector<BasicBlock *, 4> ExitingBlocks;
1705  L.getExitingBlocks(ExitingBlocks);
1706  auto HasNoClobbersOnPath =
1707  [&L, &AA, &AccessedLocs, &ExitingBlocks, &InstToDuplicate,
1708  MSSAThreshold](BasicBlock *Succ, BasicBlock *Header,
1709  SmallVector<MemoryAccess *, 4> AccessesToCheck)
1712  // First, collect all blocks in the loop that are on a patch from Succ
1713  // to the header.
1715  WorkList.push_back(Succ);
1716  WorkList.push_back(Header);
1718  Seen.insert(Header);
1719  Info.PathIsNoop &=
1720  all_of(*Header, [](Instruction &I) { return !I.mayHaveSideEffects(); });
1721 
1722  while (!WorkList.empty()) {
1723  BasicBlock *Current = WorkList.pop_back_val();
1724  if (!L.contains(Current))
1725  continue;
1726  const auto &SeenIns = Seen.insert(Current);
1727  if (!SeenIns.second)
1728  continue;
1729 
1730  Info.PathIsNoop &= all_of(
1731  *Current, [](Instruction &I) { return !I.mayHaveSideEffects(); });
1732  WorkList.append(succ_begin(Current), succ_end(Current));
1733  }
1734 
1735  // Require at least 2 blocks on a path through the loop. This skips
1736  // paths that directly exit the loop.
1737  if (Seen.size() < 2)
1738  return {};
1739 
1740  // Next, check if there are any MemoryDefs that are on the path through
1741  // the loop (in the Seen set) and they may-alias any of the locations in
1742  // AccessedLocs. If that is the case, they may modify the condition and
1743  // partial unswitching is not possible.
1744  SmallPtrSet<MemoryAccess *, 4> SeenAccesses;
1745  while (!AccessesToCheck.empty()) {
1746  MemoryAccess *Current = AccessesToCheck.pop_back_val();
1747  auto SeenI = SeenAccesses.insert(Current);
1748  if (!SeenI.second || !Seen.contains(Current->getBlock()))
1749  continue;
1750 
1751  // Bail out if exceeded the threshold.
1752  if (SeenAccesses.size() >= MSSAThreshold)
1753  return {};
1754 
1755  // MemoryUse are read-only accesses.
1756  if (isa<MemoryUse>(Current))
1757  continue;
1758 
1759  // For a MemoryDef, check if is aliases any of the location feeding
1760  // the original condition.
1761  if (auto *CurrentDef = dyn_cast<MemoryDef>(Current)) {
1762  if (any_of(AccessedLocs, [&AA, CurrentDef](MemoryLocation &Loc) {
1763  return isModSet(
1764  AA.getModRefInfo(CurrentDef->getMemoryInst(), Loc));
1765  }))
1766  return {};
1767  }
1768 
1769  for (Use &U : Current->uses())
1770  AccessesToCheck.push_back(cast<MemoryAccess>(U.getUser()));
1771  }
1772 
1773  // We could also allow loops with known trip counts without mustprogress,
1774  // but ScalarEvolution may not be available.
1775  Info.PathIsNoop &= isMustProgress(&L);
1776 
1777  // If the path is considered a no-op so far, check if it reaches a
1778  // single exit block without any phis. This ensures no values from the
1779  // loop are used outside of the loop.
1780  if (Info.PathIsNoop) {
1781  for (auto *Exiting : ExitingBlocks) {
1782  if (!Seen.contains(Exiting))
1783  continue;
1784  for (auto *Succ : successors(Exiting)) {
1785  if (L.contains(Succ))
1786  continue;
1787 
1788  Info.PathIsNoop &= llvm::empty(Succ->phis()) &&
1789  (!Info.ExitForPath || Info.ExitForPath == Succ);
1790  if (!Info.PathIsNoop)
1791  break;
1792  assert((!Info.ExitForPath || Info.ExitForPath == Succ) &&
1793  "cannot have multiple exit blocks");
1794  Info.ExitForPath = Succ;
1795  }
1796  }
1797  }
1798  if (!Info.ExitForPath)
1799  Info.PathIsNoop = false;
1800 
1801  Info.InstToDuplicate = InstToDuplicate;
1802  return Info;
1803  };
1804 
1805  // If we branch to the same successor, partial unswitching will not be
1806  // beneficial.
1807  if (TI->getSuccessor(0) == TI->getSuccessor(1))
1808  return {};
1809 
1810  if (auto Info = HasNoClobbersOnPath(TI->getSuccessor(0), L.getHeader(),
1811  AccessesToCheck)) {
1812  Info->KnownValue = ConstantInt::getTrue(TI->getContext());
1813  return Info;
1814  }
1815  if (auto Info = HasNoClobbersOnPath(TI->getSuccessor(1), L.getHeader(),
1816  AccessesToCheck)) {
1817  Info->KnownValue = ConstantInt::getFalse(TI->getContext());
1818  return Info;
1819  }
1820 
1821  return {};
1822 }
i
i
Definition: README.txt:29
LLVMLoopDisableLICM
static const char * LLVMLoopDisableLICM
Definition: LoopUtils.cpp:55
llvm::initializeLoopPassPass
void initializeLoopPassPass(PassRegistry &)
Manually defined generic "LoopPass" dependency initialization.
Definition: LoopUtils.cpp:192
llvm::hasUnrollTransformation
TransformationMode hasUnrollTransformation(const Loop *L)
Definition: LoopUtils.cpp:355
llvm::StringRef::startswith
LLVM_NODISCARD bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:290
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4637
llvm::rewriteLoopExitValues
int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)
If the final value of any expressions that are recurrent in the loop can be computed,...
Definition: LoopUtils.cpp:1247
llvm::ScalarEvolution::isLoopEntryGuardedByCond
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
Definition: ScalarEvolution.cpp:11031
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:35
llvm::IRBuilderBase::SetInsertPoint
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:179
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:137
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1906
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:65
llvm::RuntimePointerCheck
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
Definition: LoopAccessAnalysis.h:366
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:280
Optional.h
llvm::RecurKind::Or
@ Or
Bitwise or logical OR of integers.
llvm::isSafeToExpand
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE, bool CanonicalMode=true)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
Definition: ScalarEvolutionExpander.cpp:2616
PointerBounds::End
TrackingVH< Value > End
Definition: LoopUtils.cpp:1513
llvm::ReplaceExitVal
ReplaceExitVal
Definition: LoopUtils.h:438
llvm::RecurKind::FMul
@ FMul
Product of floats.
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:291
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::getShuffleReduction
Value * getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:947
IntrinsicInst.h
ScalarEvolutionExpander.h
llvm::DIBuilder
Definition: DIBuilder.h:41
llvm::ElementCount
Definition: TypeSize.h:404
llvm::LoopBase::getOutermostLoop
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
Definition: LoopInfo.h:117
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::hasDisableAllTransformsHint
bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
Definition: LoopUtils.cpp:347
MemorySSAUpdater.h
llvm::OnlyCheapRepl
@ OnlyCheapRepl
Definition: LoopUtils.h:438
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
llvm::setProfileInfoAfterUnrolling
void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, Loop *RemainderLoop, uint64_t UF)
Set weights for UnrolledLoop and RemainderLoop based on weights for OrigLoop and the following distri...
Definition: LoopUtils.cpp:1414
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:63
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::ARM_MB::LD
@ LD
Definition: ARMBaseInfo.h:72
llvm::propagateIRFlags
void propagateIRFlags(Value *I, ArrayRef< Value * > VL, Value *OpValue=nullptr, bool IncludeWrapFlags=true)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
Definition: LoopUtils.cpp:1094
llvm::PriorityWorklist< T, SmallVector< T, N >, SmallDenseMap< T, ptrdiff_t > >::insert
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
Definition: PriorityWorklist.h:90
llvm::deleteDeadLoop
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Definition: LoopUtils.cpp:472
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::APInt::getMinValue
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:196
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::find
iterator find(const_arg_type_t< ValueT > V)
Definition: DenseSet.h:179
llvm::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
LoopAccessAnalysis.h
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
llvm::IRBuilder<>
DomTreeUpdater.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:741
llvm::makeFollowupLoopID
Optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
Definition: LoopUtils.cpp:266
Local.h
llvm::IRBuilderBase::CreateOr
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1378
createStringMetadata
static MDNode * createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V)
Create MDNode for input string.
Definition: LoopUtils.cpp:206
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:144
Right
Vector Shift Left Right
Definition: README_P9.txt:118
llvm::SCEVExpander::expandCodeFor
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
Definition: ScalarEvolutionExpander.h:275
GlobalsModRef.h
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:746
llvm::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
ScalarEvolution.h
llvm::findDefsUsedOutsideOfLoop
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:126
llvm::LoopInfoBase::removeBlock
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: LoopInfo.h:1051
llvm::ScalarEvolution::LoopInvariant
@ LoopInvariant
The SCEV is loop-invariant.
Definition: ScalarEvolution.h:456
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1287
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::hasDisableLICMTransformsHint
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Definition: LoopUtils.cpp:351
llvm::Optional
Definition: APInt.h:33
llvm::formLCSSARecursively
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:404
llvm::LoopBase::begin
iterator begin() const
Definition: LoopInfo.h:170
llvm::BranchInst::getNumSuccessors
unsigned getNumSuccessors() const
Definition: Instructions.h:3177
llvm::ConstantAsMetadata::get
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:420
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::createSelectCmpOp
Value * createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, Value *Left, Value *Right)
See RecurrenceDescriptor::isSelectCmpPattern for a description of the pattern we are trying to match.
Definition: LoopUtils.cpp:904
RewritePhi
Definition: LoopUtils.cpp:1180
getExpectedExitLoopLatchBranch
static BranchInst * getExpectedExitLoopLatchBranch(Loop *L)
Checks if L has an exiting latch branch.
Definition: LoopUtils.cpp:768
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:491
llvm::RecurKind::SMin
@ SMin
Signed integer min implemented in terms of select(cmp()).
llvm::ConstantFP::getNegativeZero
static Constant * getNegativeZero(Type *Ty)
Definition: Constants.h:293
llvm::getMinMaxReductionPredicate
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
Definition: LoopUtils.cpp:885
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::CmpInst::FCMP_OGT
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:723
llvm::findOptionMDForLoopID
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:1016
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2750
llvm::createSimpleTargetReduction
Value * createSimpleTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1027
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:239
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::LPPassManager::addLoop
void addLoop(Loop &L)
Definition: LoopPass.cpp:76
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1300
llvm::Instruction::mayHaveSideEffects
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.cpp:695
llvm::MDNode::operands
op_range operands() const
Definition: Metadata.h:1202
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1366
llvm::LoopBase::block_end
block_iterator block_end() const
Definition: LoopInfo.h:193
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1210
RewritePhi::RewritePhi
RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt, bool H)
Definition: LoopUtils.cpp:1187
AliasAnalysis.h
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:312
llvm::RecurKind
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:35
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
llvm::ElementCount::isScalar
bool isScalar() const
Counting predicates.
Definition: TypeSize.h:414
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::end
iterator end()
Definition: DenseSet.h:174
PriorityWorklist.h
llvm::AlignStyle::Left
@ Left
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::TM_Enable
@ TM_Enable
The transformation should be applied without considering a cost model.
Definition: LoopUtils.h:274
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1617
llvm::IRBuilderBase::CreateMul
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1240
llvm::hasDistributeTransformation
TransformationMode hasDistributeTransformation(const Loop *L)
Definition: LoopUtils.cpp:430
llvm::LinearPolySize< ElementCount >::get
static ElementCount get(ScalarTy MinVal, bool Scalable)
Definition: TypeSize.h:289
llvm::RecurKind::And
@ And
Bitwise or logical AND of integers.
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
llvm::getOptionalIntLoopAttribute
llvm::Optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1088
Rewriter
Virtual Register Rewriter
Definition: VirtRegMap.cpp:237
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2747
llvm::AAResults
Definition: AliasAnalysis.h:511
llvm::getOrderedReduction
Value * getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates an ordered vector reduction using extracts to reduce the value.
Definition: LoopUtils.cpp:922
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:667
llvm::User
Definition: User.h:44
llvm::RecurrenceDescriptor::isSelectCmpRecurrenceKind
static bool isSelectCmpRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
Definition: IVDescriptors.h:239
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::isKnownNegativeInLoop
bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always negative in loop L.
Definition: LoopUtils.cpp:1114
llvm::cannotBeMinInLoop
bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned min.
Definition: LoopUtils.cpp:1128
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::MDBuilder::createBranchWeights
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Definition: MDBuilder.cpp:37
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MDTuple
Tuple of metadata.
Definition: Metadata.h:1241
llvm::LoopInfoBase::addTopLevelLoop
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1043
llvm::cloneLoop
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
Definition: LoopUtils.cpp:1484
Check
#define Check(C,...)
Definition: Lint.cpp:170
llvm::LoopBase::end
iterator end() const
Definition: LoopInfo.h:171
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:194
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::RuntimeCheckingPtrGroup::AddressSpace
unsigned AddressSpace
Address space of the involved pointers.
Definition: LoopAccessAnalysis.h:357
llvm::LoopInfoBase::destroy
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
Definition: LoopInfo.h:1090
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
llvm::LoopInfo::replacementPreservesLCSSAForm
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:1134
DenseSet.h
llvm::getOptionalBoolLoopAttribute
Optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
Definition: LoopInfo.cpp:1066
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:187
llvm::make_scope_exit
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
llvm::Instruction
Definition: Instruction.h:42
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:189
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
MDBuilder.h
llvm::TM_SuppressedByUser
@ TM_SuppressedByUser
The transformation must not be applied.
Definition: LoopUtils.h:291
RewritePhi::Ith
unsigned Ith
Definition: LoopUtils.cpp:1182
llvm::RecurrenceDescriptor::getRecurrenceKind
RecurKind getRecurrenceKind() const
Definition: IVDescriptors.h:195
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:33
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1777
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:928
llvm::isMustProgress
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
Definition: LoopInfo.cpp:1117
LoopUtils.h
llvm::AArch64CC::PL
@ PL
Definition: AArch64BaseInfo.h:260
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2145
llvm::LPPassManager
Definition: LoopPass.h:76
SmallPtrSet.h
llvm::SplitBlockPredecessors
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
Definition: BasicBlockUtils.cpp:1176
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::CmpInst::FCMP_OLT
@ FCMP_OLT
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:725
PatternMatch.h
llvm::hasLICMVersioningTransformation
TransformationMode hasLICMVersioningTransformation(const Loop *L)
Definition: LoopUtils.cpp:440
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
llvm::addRuntimeChecks
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
Definition: LoopUtils.cpp:1556
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2743
llvm::Instruction::extractProfMetadata
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
Definition: Metadata.cpp:1435
llvm::None
const NoneType None
Definition: None.h:24
llvm::MemoryAccess::getBlock
BasicBlock * getBlock() const
Definition: MemorySSA.h:164
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::IRBuilderBase::CreateAnd
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1356
llvm::RecurKind::UMin
@ UMin
Unisgned integer min implemented in terms of select(cmp()).
llvm::isKnownNonNegativeInLoop
bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-negative in loop L.
Definition: LoopUtils.cpp:1121
LoopInfo.h
llvm::LoopInfoBase::AllocateLoop
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:950
llvm::breakLoopBackedge
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:689
hasHardUserWithinLoop
static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I)
Definition: LoopUtils.cpp:1155
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4406
llvm::LoopBase::block_begin
block_iterator block_begin() const
Definition: LoopInfo.h:192
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:191
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1204
llvm::IRBuilderBase::FastMathFlagGuard
Definition: IRBuilder.h:372
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::hasIterationCountInvariantInParent
bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)
Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop.
Definition: LoopUtils.cpp:863
llvm::IRBuilderBase::CreateBitCast
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1958
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::MipsISD::Ext
@ Ext
Definition: MipsISelLowering.h:159
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::SCEVAAWrapperPass
Legacy wrapper pass to provide the SCEVAAResult object.
Definition: ScalarEvolutionAliasAnalysis.h:56
uint64_t
llvm::hasUnrollAndJamTransformation
TransformationMode hasUnrollAndJamTransformation(const Loop *L)
Definition: LoopUtils.cpp:376
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
InstSimplifyFolder.h
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1637
llvm::LoopBase::getUniqueExitBlocks
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:121
canLoopBeDeleted
static bool canLoopBeDeleted(Loop *L, SmallVector< RewritePhi, 8 > &RewritePhiSet)
Definition: LoopUtils.cpp:1196
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::SmallPriorityWorklist
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
Definition: PriorityWorklist.h:255
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:173
llvm::addStringMetadataToLoop
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
Definition: LoopUtils.cpp:217
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::RuntimeCheckingPtrGroup
A grouping of pointers.
Definition: LoopAccessAnalysis.h:334
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:714
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:986
llvm::ScalarEvolution::LoopDisposition
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
Definition: ScalarEvolution.h:454
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:731
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
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:618
DIBuilder.h
llvm::RecurKind::Add
@ Add
Sum of integers.
llvm::SCEVCheapExpansionBudget
cl::opt< unsigned > SCEVCheapExpansionBudget
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
llvm::LCSSAVerificationPass
Definition: LoopPass.h:124
LLVMLoopDisableNonforced
static const char * LLVMLoopDisableNonforced
Definition: LoopUtils.cpp:54
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:8091
llvm::AlwaysRepl
@ AlwaysRepl
Definition: LoopUtils.h:438
llvm::TrackingVH< Value >
llvm::MDString::get
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:497
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
Enable
@ Enable
Definition: DwarfDebug.cpp:85
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:91
llvm::TM_Disable
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:277
llvm::createTargetReduction
Value * createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, const RecurrenceDescriptor &Desc, Value *Src, PHINode *OrigPhi=nullptr)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
Definition: LoopUtils.cpp:1065
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
PointerBounds
IR Values for the lower and upper bounds of a pointer evolution.
Definition: LoopUtils.cpp:1511
llvm::Optional::getValue
constexpr const T & getValue() const &
Definition: Optional.h:306
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
llvm::cannotBeMaxInLoop
bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned max.
Definition: LoopUtils.cpp:1139
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::TM_Unspecified
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
Definition: LoopUtils.h:271
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1724
PreferPredicateTy::Option
Option
Definition: LoopVectorize.cpp:210
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:875
RewritePhi::PN
PHINode * PN
Definition: LoopUtils.cpp:1181
PointerBounds::Start
TrackingVH< Value > Start
Definition: LoopUtils.cpp:1512
llvm::MDNode
Metadata node.
Definition: Metadata.h:937
llvm::collectChildrenInLoop
SmallVector< DomTreeNode *, 16 > collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop)
Does a BFS from a given node to all of its children inside a given loop.
Definition: LoopUtils.cpp:453
llvm::RuntimeCheckingPtrGroup::High
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
Definition: LoopAccessAnalysis.h:350
Cleanup
static const HTTPClientCleanup Cleanup
Definition: HTTPClient.cpp:42
llvm::ElementCount::isVector
bool isVector() const
One or more elements.
Definition: TypeSize.h:416
llvm::RuntimeCheckingPtrGroup::Low
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.
Definition: LoopAccessAnalysis.h:353
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:748
llvm::RecurKind::UMax
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:395
llvm::LoopInfo
Definition: LoopInfo.h:1102
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:1624
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
getEstimatedTripCount
static Optional< uint64_t > getEstimatedTripCount(BranchInst *ExitingBranch, Loop *L, uint64_t &OrigExitWeight)
Return the estimated trip count for any exiting branch which dominates the loop latch.
Definition: LoopUtils.cpp:787
llvm::RecurrenceDescriptor::getFastMathFlags
FastMathFlags getFastMathFlags() const
Definition: IVDescriptors.h:199
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:461
llvm::TM_ForcedByUser
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:285
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:744
LoopPass.h
llvm::getOptionalElementCountLoopAttribute
Optional< ElementCount > getOptionalElementCountLoopAttribute(const Loop *TheLoop)
Find a combination of metadata ("llvm.loop.vectorize.width" and "llvm.loop.vectorize....
Definition: LoopUtils.cpp:253
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::transform
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition: STLExtras.h:1723
llvm::appendLoopsToWorklist
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1467
llvm::cl::Sink
@ Sink
Definition: CommandLine.h:167
llvm::setLoopEstimatedTripCount
bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)
Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...
Definition: LoopUtils.cpp:831
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:529
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:93
RewritePhi::HighCost
bool HighCost
Definition: LoopUtils.cpp:1185
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::RecurKind::Mul
@ Mul
Product of integers.
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::RecurKind::FMax
@ FMax
FP max implemented in terms of select(cmp()).
llvm::ConstantInt::getSExtValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:148
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:66
llvm::MemoryAccess
Definition: MemorySSA.h:142
llvm::DomTreeNodeBase< BasicBlock >
llvm::ValueMap< const Value *, WeakTrackingVH >
ValueHandle.h
RewritePhi::ExpansionSCEV
const SCEV * ExpansionSCEV
Definition: LoopUtils.cpp:1183
llvm::LoopInfoBase::removeLoop
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
Definition: LoopInfo.h:1013
llvm::RecurrenceDescriptor::getRecurrenceStartValue
TrackingVH< Value > getRecurrenceStartValue() const
Definition: IVDescriptors.h:201
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:883
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:13240
llvm::MDNode::getContext
LLVMContext & getContext() const
Definition: Metadata.h:1031
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
llvm::RecurKind::FMulAdd
@ FMulAdd
Fused multiply-add of floats (a * b + c).
j
return j(j<< 16)
llvm::LCSSAID
char & LCSSAID
Definition: LCSSA.cpp:486
llvm::SplitEdge
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Definition: BasicBlockUtils.cpp:516
llvm::formDedicatedExitBlocks
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:57
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:794
llvm::ScalarEvolution::forgetLoop
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
Definition: ScalarEvolution.cpp:8031
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:268
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:876
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
H
#define H(x, y, z)
Definition: MD5.cpp:57
llvm::Loop::setLoopID
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:524
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:458
MSSAThreshold
static cl::opt< unsigned > MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)
llvm::appendReversedLoopsToWorklist
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1442
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::IRBuilderBase::CreateICmpULT
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2088
llvm::ConstantFP::get
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:975
llvm::Loop::getLoopID
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:500
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:4292
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::IVConditionInfo
Struct to hold information about a partially invariant condition.
Definition: LoopUtils.h:512
llvm::Loop::isRecursivelyLCSSAForm
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:465
llvm::hasPartialIVCondition
Optional< IVConditionInfo > hasPartialIVCondition(Loop &L, unsigned MSSAThreshold, MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
Definition: LoopUtils.cpp:1650
ScalarEvolutionAliasAnalysis.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:747
llvm::ScalarEvolution::isAvailableAtLoopEntry
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
Definition: ScalarEvolution.cpp:2448
llvm::createMinMaxOp
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:913
llvm::APInt::getSignedMinValue
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:436
llvm::MDNode::replaceOperandWith
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:907
llvm::MDBuilder
Definition: MDBuilder.h:35
AA
ReplaceExitValue
static cl::opt< ReplaceExitVal > ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
llvm::LoopBase::hasNoExitBlocks
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
Definition: LoopInfoImpl.h:72
ScalarEvolutionExpressions.h
llvm::createOrderedReduction
Value * createOrderedReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, Value *Start)
Create an ordered reduction intrinsic using the given recurrence descriptor Desc.
Definition: LoopUtils.cpp:1082
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:786
llvm::RecurrenceDescriptor
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:69
llvm::changeToUnreachable
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2122
llvm::LoopInfoBase::end
iterator end() const
Definition: LoopInfo.h:962
MemorySSA.h
llvm::RecurKind::FAdd
@ FAdd
Sum of floats.
Instructions.h
llvm::hasVectorizeTransformation
TransformationMode hasVectorizeTransformation(const Loop *L)
Definition: LoopUtils.cpp:394
llvm::Registry
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
SmallVector.h
llvm::ScalarEvolution::getLoopDisposition
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
Definition: ScalarEvolution.cpp:13140
llvm::LoopBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
Definition: LoopInfo.h:167
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:742
Dominators.h
N
#define N
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1351
llvm::getBooleanLoopAttribute
bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Returns true if Name is applied to TheLoop and enabled.
Definition: LoopInfo.cpp:1084
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:148
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2767
llvm::ScalarEvolution::getZero
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
Definition: ScalarEvolution.h:642
Users
iv Induction Variable Users
Definition: IVUsers.cpp:48
llvm::PHINode
Definition: Instructions.h:2651
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.h:119
llvm::PatternMatch
Definition: PatternMatch.h:47
ScopeExit.h
expandBounds
static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG, Loop *TheLoop, Instruction *Loc, SCEVExpander &Exp)
Expand code for the lower and upper bound of the pointer group CG in TheLoop.
Definition: LoopUtils.cpp:1518
llvm::SmallVectorImpl< RuntimePointerCheck >
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:392
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
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:241
llvm::RecurKind::FMin
@ FMin
FP min implemented in terms of select(cmp()).
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:277
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::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
llvm::IRBuilderBase::CreateSub
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1223
llvm::RecurrenceDescriptor::isMinMaxRecurrenceKind
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
Definition: IVDescriptors.h:233
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3086
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
BasicBlockUtils.h
llvm::MDString
A single uniqued string.
Definition: Metadata.h:612
llvm::Optional::value_or
constexpr T value_or(U &&alt) const &
Definition: Optional.h:318
llvm::divideNearest
uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator)
Returns the integer nearest(Numerator / Denominator).
Definition: MathExtras.h:781
llvm::getLoopEstimatedTripCount
Optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:813
InitializePasses.h
llvm::ScalarEvolution::getSCEVAtScope
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
Definition: ScalarEvolution.cpp:9237
llvm::RecurKind::SMax
@ SMax
Signed integer max implemented in terms of select(cmp()).
RewritePhi::ExpansionPoint
Instruction * ExpansionPoint
Definition: LoopUtils.cpp:1184
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::addDiffRuntimeChecks
Value * addDiffRuntimeChecks(Instruction *Loc, Loop *TheLoop, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
Definition: LoopUtils.cpp:1611
llvm::ScalarEvolution::getExitCount
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
Definition: ScalarEvolution.cpp:7882
llvm::TransformationMode
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:268
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::RuntimeCheckingPtrGroup::NeedsFreeze
bool NeedsFreeze
Whether the pointer needs to be frozen after expansion, e.g.
Definition: LoopAccessAnalysis.h:360
llvm::MDOperand
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:773
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3179
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::RecurKind::Xor
@ Xor
Bitwise or logical XOR of integers.
SetVector.h
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927
llvm::createSelectCmpTargetReduction
Value * createSelectCmpTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, const RecurrenceDescriptor &Desc, PHINode *OrigPhi)
Create a target reduction of the given vector Src for a reduction of the kind RecurKind::SelectICmp o...
Definition: LoopUtils.cpp:987
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::RegState::Undef
@ Undef
Value of the register doesn't matter.
Definition: MachineInstrBuilder.h:52