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