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