LLVM  10.0.0svn
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/ScopeExit.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/LoopPass.h"
30 #include "llvm/IR/DIBuilder.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/IR/PatternMatch.h"
36 #include "llvm/IR/ValueHandle.h"
37 #include "llvm/Pass.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/KnownBits.h"
41 
42 using namespace llvm;
43 using namespace llvm::PatternMatch;
44 
45 #define DEBUG_TYPE "loop-utils"
46 
47 static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
48 static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
49 
51  MemorySSAUpdater *MSSAU,
52  bool PreserveLCSSA) {
53  bool Changed = false;
54 
55  // We re-use a vector for the in-loop predecesosrs.
56  SmallVector<BasicBlock *, 4> InLoopPredecessors;
57 
58  auto RewriteExit = [&](BasicBlock *BB) {
59  assert(InLoopPredecessors.empty() &&
60  "Must start with an empty predecessors list!");
61  auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
62 
63  // See if there are any non-loop predecessors of this exit block and
64  // keep track of the in-loop predecessors.
65  bool IsDedicatedExit = true;
66  for (auto *PredBB : predecessors(BB))
67  if (L->contains(PredBB)) {
68  if (isa<IndirectBrInst>(PredBB->getTerminator()))
69  // We cannot rewrite exiting edges from an indirectbr.
70  return false;
71  if (isa<CallBrInst>(PredBB->getTerminator()))
72  // We cannot rewrite exiting edges from a callbr.
73  return false;
74 
75  InLoopPredecessors.push_back(PredBB);
76  } else {
77  IsDedicatedExit = false;
78  }
79 
80  assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
81 
82  // Nothing to do if this is already a dedicated exit.
83  if (IsDedicatedExit)
84  return false;
85 
86  auto *NewExitBB = SplitBlockPredecessors(
87  BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA);
88 
89  if (!NewExitBB)
90  LLVM_DEBUG(
91  dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
92  << *L << "\n");
93  else
94  LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
95  << NewExitBB->getName() << "\n");
96  return true;
97  };
98 
99  // Walk the exit blocks directly rather than building up a data structure for
100  // them, but only visit each one once.
102  for (auto *BB : L->blocks())
103  for (auto *SuccBB : successors(BB)) {
104  // We're looking for exit blocks so skip in-loop successors.
105  if (L->contains(SuccBB))
106  continue;
107 
108  // Visit each exit block exactly once.
109  if (!Visited.insert(SuccBB).second)
110  continue;
111 
112  Changed |= RewriteExit(SuccBB);
113  }
114 
115  return Changed;
116 }
117 
118 /// Returns the instructions that use values defined in the loop.
120  SmallVector<Instruction *, 8> UsedOutside;
121 
122  for (auto *Block : L->getBlocks())
123  // FIXME: I believe that this could use copy_if if the Inst reference could
124  // be adapted into a pointer.
125  for (auto &Inst : *Block) {
126  auto Users = Inst.users();
127  if (any_of(Users, [&](User *U) {
128  auto *Use = cast<Instruction>(U);
129  return !L->contains(Use->getParent());
130  }))
131  UsedOutside.push_back(&Inst);
132  }
133 
134  return UsedOutside;
135 }
136 
138  // By definition, all loop passes need the LoopInfo analysis and the
139  // Dominator tree it depends on. Because they all participate in the loop
140  // pass manager, they must also preserve these.
145 
146  // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
147  // here because users shouldn't directly get them from this header.
148  extern char &LoopSimplifyID;
149  extern char &LCSSAID;
150  AU.addRequiredID(LoopSimplifyID);
151  AU.addPreservedID(LoopSimplifyID);
152  AU.addRequiredID(LCSSAID);
153  AU.addPreservedID(LCSSAID);
154  // This is used in the LPPassManager to perform LCSSA verification on passes
155  // which preserve lcssa form
158 
159  // Loop passes are designed to run inside of a loop pass manager which means
160  // that any function analyses they require must be required by the first loop
161  // pass in the manager (so that it is computed before the loop pass manager
162  // runs) and preserved by all loop pasess in the manager. To make this
163  // reasonably robust, the set needed for most loop passes is maintained here.
164  // If your loop pass requires an analysis not listed here, you will need to
165  // carefully audit the loop pass manager nesting structure that results.
173 }
174 
175 /// Manually defined generic "LoopPass" dependency initialization. This is used
176 /// to initialize the exact set of passes from above in \c
177 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
178 /// with:
179 ///
180 /// INITIALIZE_PASS_DEPENDENCY(LoopPass)
181 ///
182 /// As-if "LoopPass" were a pass.
186  INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
187  INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
193 }
194 
195 /// Create MDNode for input string.
196 static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
197  LLVMContext &Context = TheLoop->getHeader()->getContext();
198  Metadata *MDs[] = {
199  MDString::get(Context, Name),
201  return MDNode::get(Context, MDs);
202 }
203 
204 /// Set input string into loop metadata by keeping other values intact.
205 /// If the string is already in loop metadata update value if it is
206 /// different.
207 void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *StringMD,
208  unsigned V) {
210  // If the loop already has metadata, retain it.
211  MDNode *LoopID = TheLoop->getLoopID();
212  if (LoopID) {
213  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
214  MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
215  // If it is of form key = value, try to parse it.
216  if (Node->getNumOperands() == 2) {
217  MDString *S = dyn_cast<MDString>(Node->getOperand(0));
218  if (S && S->getString().equals(StringMD)) {
219  ConstantInt *IntMD =
220  mdconst::extract_or_null<ConstantInt>(Node->getOperand(1));
221  if (IntMD && IntMD->getSExtValue() == V)
222  // It is already in place. Do nothing.
223  return;
224  // We need to update the value, so just skip it here and it will
225  // be added after copying other existed nodes.
226  continue;
227  }
228  }
229  MDs.push_back(Node);
230  }
231  }
232  // Add new metadata.
233  MDs.push_back(createStringMetadata(TheLoop, StringMD, V));
234  // Replace current metadata node with new one.
235  LLVMContext &Context = TheLoop->getHeader()->getContext();
236  MDNode *NewLoopID = MDNode::get(Context, MDs);
237  // Set operand 0 to refer to the loop id itself.
238  NewLoopID->replaceOperandWith(0, NewLoopID);
239  TheLoop->setLoopID(NewLoopID);
240 }
241 
242 /// Find string metadata for loop
243 ///
244 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
245 /// operand or null otherwise. If the string metadata is not found return
246 /// Optional's not-a-value.
248  StringRef Name) {
249  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
250  if (!MD)
251  return None;
252  switch (MD->getNumOperands()) {
253  case 1:
254  return nullptr;
255  case 2:
256  return &MD->getOperand(1);
257  default:
258  llvm_unreachable("loop metadata has 0 or 1 operand");
259  }
260 }
261 
263  StringRef Name) {
264  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
265  if (!MD)
266  return None;
267  switch (MD->getNumOperands()) {
268  case 1:
269  // When the value is absent it is interpreted as 'attribute set'.
270  return true;
271  case 2:
272  if (ConstantInt *IntMD =
273  mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
274  return IntMD->getZExtValue();
275  return true;
276  }
277  llvm_unreachable("unexpected number of options");
278 }
279 
280 static bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) {
281  return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false);
282 }
283 
285  StringRef Name) {
286  const MDOperand *AttrMD =
287  findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr);
288  if (!AttrMD)
289  return None;
290 
291  ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
292  if (!IntMD)
293  return None;
294 
295  return IntMD->getSExtValue();
296 }
297 
299  MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions,
300  const char *InheritOptionsExceptPrefix, bool AlwaysNew) {
301  if (!OrigLoopID) {
302  if (AlwaysNew)
303  return nullptr;
304  return None;
305  }
306 
307  assert(OrigLoopID->getOperand(0) == OrigLoopID);
308 
309  bool InheritAllAttrs = !InheritOptionsExceptPrefix;
310  bool InheritSomeAttrs =
311  InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] != '\0';
313  MDs.push_back(nullptr);
314 
315  bool Changed = false;
316  if (InheritAllAttrs || InheritSomeAttrs) {
317  for (const MDOperand &Existing : drop_begin(OrigLoopID->operands(), 1)) {
318  MDNode *Op = cast<MDNode>(Existing.get());
319 
320  auto InheritThisAttribute = [InheritSomeAttrs,
321  InheritOptionsExceptPrefix](MDNode *Op) {
322  if (!InheritSomeAttrs)
323  return false;
324 
325  // Skip malformatted attribute metadata nodes.
326  if (Op->getNumOperands() == 0)
327  return true;
328  Metadata *NameMD = Op->getOperand(0).get();
329  if (!isa<MDString>(NameMD))
330  return true;
331  StringRef AttrName = cast<MDString>(NameMD)->getString();
332 
333  // Do not inherit excluded attributes.
334  return !AttrName.startswith(InheritOptionsExceptPrefix);
335  };
336 
337  if (InheritThisAttribute(Op))
338  MDs.push_back(Op);
339  else
340  Changed = true;
341  }
342  } else {
343  // Modified if we dropped at least one attribute.
344  Changed = OrigLoopID->getNumOperands() > 1;
345  }
346 
347  bool HasAnyFollowup = false;
348  for (StringRef OptionName : FollowupOptions) {
349  MDNode *FollowupNode = findOptionMDForLoopID(OrigLoopID, OptionName);
350  if (!FollowupNode)
351  continue;
352 
353  HasAnyFollowup = true;
354  for (const MDOperand &Option : drop_begin(FollowupNode->operands(), 1)) {
355  MDs.push_back(Option.get());
356  Changed = true;
357  }
358  }
359 
360  // Attributes of the followup loop not specified explicity, so signal to the
361  // transformation pass to add suitable attributes.
362  if (!AlwaysNew && !HasAnyFollowup)
363  return None;
364 
365  // If no attributes were added or remove, the previous loop Id can be reused.
366  if (!AlwaysNew && !Changed)
367  return OrigLoopID;
368 
369  // No attributes is equivalent to having no !llvm.loop metadata at all.
370  if (MDs.size() == 1)
371  return nullptr;
372 
373  // Build the new loop ID.
374  MDTuple *FollowupLoopID = MDNode::get(OrigLoopID->getContext(), MDs);
375  FollowupLoopID->replaceOperandWith(0, FollowupLoopID);
376  return FollowupLoopID;
377 }
378 
380  return getBooleanLoopAttribute(L, LLVMLoopDisableNonforced);
381 }
382 
384  return getBooleanLoopAttribute(L, LLVMLoopDisableLICM);
385 }
386 
388  if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable"))
389  return TM_SuppressedByUser;
390 
391  Optional<int> Count =
392  getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
393  if (Count.hasValue())
394  return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
395 
396  if (getBooleanLoopAttribute(L, "llvm.loop.unroll.enable"))
397  return TM_ForcedByUser;
398 
399  if (getBooleanLoopAttribute(L, "llvm.loop.unroll.full"))
400  return TM_ForcedByUser;
401 
403  return TM_Disable;
404 
405  return TM_Unspecified;
406 }
407 
409  if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.disable"))
410  return TM_SuppressedByUser;
411 
412  Optional<int> Count =
413  getOptionalIntLoopAttribute(L, "llvm.loop.unroll_and_jam.count");
414  if (Count.hasValue())
415  return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
416 
417  if (getBooleanLoopAttribute(L, "llvm.loop.unroll_and_jam.enable"))
418  return TM_ForcedByUser;
419 
421  return TM_Disable;
422 
423  return TM_Unspecified;
424 }
425 
428  getOptionalBoolLoopAttribute(L, "llvm.loop.vectorize.enable");
429 
430  if (Enable == false)
431  return TM_SuppressedByUser;
432 
433  Optional<int> VectorizeWidth =
434  getOptionalIntLoopAttribute(L, "llvm.loop.vectorize.width");
435  Optional<int> InterleaveCount =
436  getOptionalIntLoopAttribute(L, "llvm.loop.interleave.count");
437 
438  // 'Forcing' vector width and interleave count to one effectively disables
439  // this tranformation.
440  if (Enable == true && VectorizeWidth == 1 && InterleaveCount == 1)
441  return TM_SuppressedByUser;
442 
443  if (getBooleanLoopAttribute(L, "llvm.loop.isvectorized"))
444  return TM_Disable;
445 
446  if (Enable == true)
447  return TM_ForcedByUser;
448 
449  if (VectorizeWidth == 1 && InterleaveCount == 1)
450  return TM_Disable;
451 
452  if (VectorizeWidth > 1 || InterleaveCount > 1)
453  return TM_Enable;
454 
456  return TM_Disable;
457 
458  return TM_Unspecified;
459 }
460 
462  if (getBooleanLoopAttribute(L, "llvm.loop.distribute.enable"))
463  return TM_ForcedByUser;
464 
466  return TM_Disable;
467 
468  return TM_Unspecified;
469 }
470 
472  if (getBooleanLoopAttribute(L, "llvm.loop.licm_versioning.disable"))
473  return TM_SuppressedByUser;
474 
476  return TM_Disable;
477 
478  return TM_Unspecified;
479 }
480 
481 /// Does a BFS from a given node to all of its children inside a given loop.
482 /// The returned vector of nodes includes the starting point.
486  auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
487  // Only include subregions in the top level loop.
488  BasicBlock *BB = DTN->getBlock();
489  if (CurLoop->contains(BB))
490  Worklist.push_back(DTN);
491  };
492 
493  AddRegionToWorklist(N);
494 
495  for (size_t I = 0; I < Worklist.size(); I++)
496  for (DomTreeNode *Child : Worklist[I]->getChildren())
497  AddRegionToWorklist(Child);
498 
499  return Worklist;
500 }
501 
502 void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
503  ScalarEvolution *SE = nullptr,
504  LoopInfo *LI = nullptr) {
505  assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
506  auto *Preheader = L->getLoopPreheader();
507  assert(Preheader && "Preheader should exist!");
508 
509  // Now that we know the removal is safe, remove the loop by changing the
510  // branch from the preheader to go to the single exit block.
511  //
512  // Because we're deleting a large chunk of code at once, the sequence in which
513  // we remove things is very important to avoid invalidation issues.
514 
515  // Tell ScalarEvolution that the loop is deleted. Do this before
516  // deleting the loop so that ScalarEvolution can look at the loop
517  // to determine what it needs to clean up.
518  if (SE)
519  SE->forgetLoop(L);
520 
521  auto *ExitBlock = L->getUniqueExitBlock();
522  assert(ExitBlock && "Should have a unique exit block!");
523  assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
524 
525  auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
526  assert(OldBr && "Preheader must end with a branch");
527  assert(OldBr->isUnconditional() && "Preheader must have a single successor");
528  // Connect the preheader to the exit block. Keep the old edge to the header
529  // around to perform the dominator tree update in two separate steps
530  // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
531  // preheader -> header.
532  //
533  //
534  // 0. Preheader 1. Preheader 2. Preheader
535  // | | | |
536  // V | V |
537  // Header <--\ | Header <--\ | Header <--\
538  // | | | | | | | | | | |
539  // | V | | | V | | | V |
540  // | Body --/ | | Body --/ | | Body --/
541  // V V V V V
542  // Exit Exit Exit
543  //
544  // By doing this is two separate steps we can perform the dominator tree
545  // update without using the batch update API.
546  //
547  // Even when the loop is never executed, we cannot remove the edge from the
548  // source block to the exit block. Consider the case where the unexecuted loop
549  // branches back to an outer loop. If we deleted the loop and removed the edge
550  // coming to this inner loop, this will break the outer loop structure (by
551  // deleting the backedge of the outer loop). If the outer loop is indeed a
552  // non-loop, it will be deleted in a future iteration of loop deletion pass.
553  IRBuilder<> Builder(OldBr);
554  Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
555  // Remove the old branch. The conditional branch becomes a new terminator.
556  OldBr->eraseFromParent();
557 
558  // Rewrite phis in the exit block to get their inputs from the Preheader
559  // instead of the exiting block.
560  for (PHINode &P : ExitBlock->phis()) {
561  // Set the zero'th element of Phi to be from the preheader and remove all
562  // other incoming values. Given the loop has dedicated exits, all other
563  // incoming values must be from the exiting blocks.
564  int PredIndex = 0;
565  P.setIncomingBlock(PredIndex, Preheader);
566  // Removes all incoming values from all other exiting blocks (including
567  // duplicate values from an exiting block).
568  // Nuke all entries except the zero'th entry which is the preheader entry.
569  // NOTE! We need to remove Incoming Values in the reverse order as done
570  // below, to keep the indices valid for deletion (removeIncomingValues
571  // updates getNumIncomingValues and shifts all values down into the operand
572  // being deleted).
573  for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i)
574  P.removeIncomingValue(e - i, false);
575 
576  assert((P.getNumIncomingValues() == 1 &&
577  P.getIncomingBlock(PredIndex) == Preheader) &&
578  "Should have exactly one value and that's from the preheader!");
579  }
580 
581  // Disconnect the loop body by branching directly to its exit.
582  Builder.SetInsertPoint(Preheader->getTerminator());
583  Builder.CreateBr(ExitBlock);
584  // Remove the old branch.
585  Preheader->getTerminator()->eraseFromParent();
586 
588  if (DT) {
589  // Update the dominator tree by informing it about the new edge from the
590  // preheader to the exit and the removed edge.
591  DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock},
592  {DominatorTree::Delete, Preheader, L->getHeader()}});
593  }
594 
595  // Use a map to unique and a vector to guarantee deterministic ordering.
598 
599  // Given LCSSA form is satisfied, we should not have users of instructions
600  // within the dead loop outside of the loop. However, LCSSA doesn't take
601  // unreachable uses into account. We handle them here.
602  // We could do it after drop all references (in this case all users in the
603  // loop will be already eliminated and we have less work to do but according
604  // to API doc of User::dropAllReferences only valid operation after dropping
605  // references, is deletion. So let's substitute all usages of
606  // instruction from the loop with undef value of corresponding type first.
607  for (auto *Block : L->blocks())
608  for (Instruction &I : *Block) {
609  auto *Undef = UndefValue::get(I.getType());
610  for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
611  Use &U = *UI;
612  ++UI;
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(Undef);
622  }
623  auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);
624  if (!DVI)
625  continue;
626  auto Key = DeadDebugSet.find({DVI->getVariable(), DVI->getExpression()});
627  if (Key != DeadDebugSet.end())
628  continue;
629  DeadDebugSet.insert({DVI->getVariable(), DVI->getExpression()});
630  DeadDebugInst.push_back(DVI);
631  }
632 
633  // After the loop has been deleted all the values defined and modified
634  // inside the loop are going to be unavailable.
635  // Since debug values in the loop have been deleted, inserting an undef
636  // dbg.value truncates the range of any dbg.value before the loop where the
637  // loop used to be. This is particularly important for constant values.
638  DIBuilder DIB(*ExitBlock->getModule());
639  Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI();
640  assert(InsertDbgValueBefore &&
641  "There should be a non-PHI instruction in exit block, else these "
642  "instructions will have no parent.");
643  for (auto *DVI : DeadDebugInst)
644  DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()),
645  DVI->getVariable(), DVI->getExpression(),
646  DVI->getDebugLoc(), InsertDbgValueBefore);
647 
648  // Remove the block from the reference counting scheme, so that we can
649  // delete it freely later.
650  for (auto *Block : L->blocks())
651  Block->dropAllReferences();
652 
653  if (LI) {
654  // Erase the instructions and the blocks without having to worry
655  // about ordering because we already dropped the references.
656  // NOTE: This iteration is safe because erasing the block does not remove
657  // its entry from the loop's block list. We do that in the next section.
658  for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
659  LpI != LpE; ++LpI)
660  (*LpI)->eraseFromParent();
661 
662  // Finally, the blocks from loopinfo. This has to happen late because
663  // otherwise our loop iterators won't work.
664 
666  blocks.insert(L->block_begin(), L->block_end());
667  for (BasicBlock *BB : blocks)
668  LI->removeBlock(BB);
669 
670  // The last step is to update LoopInfo now that we've eliminated this loop.
671  LI->erase(L);
672  }
673 }
674 
676  // Support loops with an exiting latch and other existing exists only
677  // deoptimize.
678 
679  // Get the branch weights for the loop's backedge.
680  BasicBlock *Latch = L->getLoopLatch();
681  if (!Latch)
682  return None;
683  BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
684  if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
685  return None;
686 
687  assert((LatchBR->getSuccessor(0) == L->getHeader() ||
688  LatchBR->getSuccessor(1) == L->getHeader()) &&
689  "At least one edge out of the latch must go to the header");
690 
691  SmallVector<BasicBlock *, 4> ExitBlocks;
692  L->getUniqueNonLatchExitBlocks(ExitBlocks);
693  if (any_of(ExitBlocks, [](const BasicBlock *EB) {
694  return !EB->getTerminatingDeoptimizeCall();
695  }))
696  return None;
697 
698  // To estimate the number of times the loop body was executed, we want to
699  // know the number of times the backedge was taken, vs. the number of times
700  // we exited the loop.
701  uint64_t TrueVal, FalseVal;
702  if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
703  return None;
704 
705  if (!TrueVal || !FalseVal)
706  return 0;
707 
708  // Divide the count of the backedge by the count of the edge exiting the loop,
709  // rounding to nearest.
710  if (LatchBR->getSuccessor(0) == L->getHeader())
711  return (TrueVal + (FalseVal / 2)) / FalseVal;
712  else
713  return (FalseVal + (TrueVal / 2)) / TrueVal;
714 }
715 
717  ScalarEvolution &SE) {
718  Loop *OuterL = InnerLoop->getParentLoop();
719  if (!OuterL)
720  return true;
721 
722  // Get the backedge taken count for the inner loop
723  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
724  const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
725  if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
726  !InnerLoopBECountSC->getType()->isIntegerTy())
727  return false;
728 
729  // Get whether count is invariant to the outer loop
731  SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
733  return false;
734 
735  return true;
736 }
737 
740  Value *Left, Value *Right) {
742  switch (RK) {
743  default:
744  llvm_unreachable("Unknown min/max recurrence kind");
746  P = CmpInst::ICMP_ULT;
747  break;
749  P = CmpInst::ICMP_UGT;
750  break;
752  P = CmpInst::ICMP_SLT;
753  break;
755  P = CmpInst::ICMP_SGT;
756  break;
758  P = CmpInst::FCMP_OLT;
759  break;
761  P = CmpInst::FCMP_OGT;
762  break;
763  }
764 
765  // We only match FP sequences that are 'fast', so we can unconditionally
766  // set it on any generated instructions.
767  IRBuilder<>::FastMathFlagGuard FMFG(Builder);
768  FastMathFlags FMF;
769  FMF.setFast();
770  Builder.setFastMathFlags(FMF);
771 
772  Value *Cmp;
775  Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
776  else
777  Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
778 
779  Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
780  return Select;
781 }
782 
783 // Helper to generate an ordered reduction.
784 Value *
786  unsigned Op,
788  ArrayRef<Value *> RedOps) {
789  unsigned VF = Src->getType()->getVectorNumElements();
790 
791  // Extract and apply reduction ops in ascending order:
792  // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
793  Value *Result = Acc;
794  for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
795  Value *Ext =
796  Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
797 
798  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
799  Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
800  "bin.rdx");
801  } else {
803  "Invalid min/max");
804  Result = createMinMaxOp(Builder, MinMaxKind, Result, Ext);
805  }
806 
807  if (!RedOps.empty())
808  propagateIRFlags(Result, RedOps);
809  }
810 
811  return Result;
812 }
813 
814 // Helper to generate a log2 shuffle reduction.
815 Value *
818  ArrayRef<Value *> RedOps) {
819  unsigned VF = Src->getType()->getVectorNumElements();
820  // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
821  // and vector ops, reducing the set of values being computed by half each
822  // round.
823  assert(isPowerOf2_32(VF) &&
824  "Reduction emission only supported for pow2 vectors!");
825  Value *TmpVec = Src;
826  SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
827  for (unsigned i = VF; i != 1; i >>= 1) {
828  // Move the upper half of the vector to the lower half.
829  for (unsigned j = 0; j != i / 2; ++j)
830  ShuffleMask[j] = Builder.getInt32(i / 2 + j);
831 
832  // Fill the rest of the mask with undef.
833  std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
834  UndefValue::get(Builder.getInt32Ty()));
835 
836  Value *Shuf = Builder.CreateShuffleVector(
837  TmpVec, UndefValue::get(TmpVec->getType()),
838  ConstantVector::get(ShuffleMask), "rdx.shuf");
839 
840  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
841  // The builder propagates its fast-math-flags setting.
842  TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
843  "bin.rdx");
844  } else {
846  "Invalid min/max");
847  TmpVec = createMinMaxOp(Builder, MinMaxKind, TmpVec, Shuf);
848  }
849  if (!RedOps.empty())
850  propagateIRFlags(TmpVec, RedOps);
851  }
852  // The result is in the first element of the vector.
853  return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
854 }
855 
856 /// Create a simple vector reduction specified by an opcode and some
857 /// flags (if generating min/max reductions).
859  IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
861  ArrayRef<Value *> RedOps) {
862  assert(isa<VectorType>(Src->getType()) && "Type must be a vector");
863 
864  std::function<Value *()> BuildFunc;
865  using RD = RecurrenceDescriptor;
866  RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
867 
868  switch (Opcode) {
869  case Instruction::Add:
870  BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
871  break;
872  case Instruction::Mul:
873  BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
874  break;
875  case Instruction::And:
876  BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
877  break;
878  case Instruction::Or:
879  BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
880  break;
881  case Instruction::Xor:
882  BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
883  break;
884  case Instruction::FAdd:
885  BuildFunc = [&]() {
886  auto Rdx = Builder.CreateFAddReduce(
888  return Rdx;
889  };
890  break;
891  case Instruction::FMul:
892  BuildFunc = [&]() {
893  Type *Ty = Src->getType()->getVectorElementType();
894  auto Rdx = Builder.CreateFMulReduce(ConstantFP::get(Ty, 1.0), Src);
895  return Rdx;
896  };
897  break;
898  case Instruction::ICmp:
899  if (Flags.IsMaxOp) {
900  MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
901  BuildFunc = [&]() {
902  return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
903  };
904  } else {
905  MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
906  BuildFunc = [&]() {
907  return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
908  };
909  }
910  break;
911  case Instruction::FCmp:
912  if (Flags.IsMaxOp) {
913  MinMaxKind = RD::MRK_FloatMax;
914  BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
915  } else {
916  MinMaxKind = RD::MRK_FloatMin;
917  BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
918  }
919  break;
920  default:
921  llvm_unreachable("Unhandled opcode");
922  break;
923  }
924  if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
925  return BuildFunc();
926  return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
927 }
928 
929 /// Create a vector reduction using a given recurrence descriptor.
931  const TargetTransformInfo *TTI,
932  RecurrenceDescriptor &Desc, Value *Src,
933  bool NoNaN) {
934  // TODO: Support in-order reductions based on the recurrence descriptor.
935  using RD = RecurrenceDescriptor;
936  RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
938  Flags.NoNaN = NoNaN;
939 
940  // All ops in the reduction inherit fast-math-flags from the recurrence
941  // descriptor.
942  IRBuilder<>::FastMathFlagGuard FMFGuard(B);
944 
945  switch (RecKind) {
946  case RD::RK_FloatAdd:
947  return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
948  case RD::RK_FloatMult:
949  return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
950  case RD::RK_IntegerAdd:
951  return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
952  case RD::RK_IntegerMult:
953  return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
954  case RD::RK_IntegerAnd:
955  return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
956  case RD::RK_IntegerOr:
957  return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
958  case RD::RK_IntegerXor:
959  return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
960  case RD::RK_IntegerMinMax: {
961  RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
962  Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_UIntMax);
963  Flags.IsSigned = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_SIntMin);
964  return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
965  }
966  case RD::RK_FloatMinMax: {
967  Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
968  return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
969  }
970  default:
971  llvm_unreachable("Unhandled RecKind");
972  }
973 }
974 
976  auto *VecOp = dyn_cast<Instruction>(I);
977  if (!VecOp)
978  return;
979  auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
980  : dyn_cast<Instruction>(OpValue);
981  if (!Intersection)
982  return;
983  const unsigned Opcode = Intersection->getOpcode();
984  VecOp->copyIRFlags(Intersection);
985  for (auto *V : VL) {
986  auto *Instr = dyn_cast<Instruction>(V);
987  if (!Instr)
988  continue;
989  if (OpValue == nullptr || Opcode == Instr->getOpcode())
990  VecOp->andIRFlags(V);
991  }
992 }
993 
994 bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
995  ScalarEvolution &SE) {
996  const SCEV *Zero = SE.getZero(S->getType());
997  return SE.isAvailableAtLoopEntry(S, L) &&
999 }
1000 
1001 bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
1002  ScalarEvolution &SE) {
1003  const SCEV *Zero = SE.getZero(S->getType());
1004  return SE.isAvailableAtLoopEntry(S, L) &&
1006 }
1007 
1008 bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1009  bool Signed) {
1010  unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1011  APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) :
1012  APInt::getMinValue(BitWidth);
1014  return SE.isAvailableAtLoopEntry(S, L) &&
1016  SE.getConstant(Min));
1017 }
1018 
1019 bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
1020  bool Signed) {
1021  unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
1022  APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) :
1023  APInt::getMaxValue(BitWidth);
1025  return SE.isAvailableAtLoopEntry(S, L) &&
1027  SE.getConstant(Max));
1028 }
Legacy wrapper pass to provide the GlobalsAAResult object.
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Type * getVectorElementType() const
Definition: Type.h:371
const NoneType None
Definition: None.h:23
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:710
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2198
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:211
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1458
LLVMContext & Context
void setFast(bool B=true)
Definition: Operator.h:236
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Definition: LoopUtils.cpp:383
const SCEV * getConstant(ConstantInt *V)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:858
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:453
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:85
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:444
LLVM_NODISCARD bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:256
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:1008
The main scalar evolution driver.
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION
Definition: Optional.h:266
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:1001
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:160
unsigned less than
Definition: InstrTypes.h:757
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop&#39;s entry.
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:738
Value * createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, unsigned Opcode, Value *Src, TargetTransformInfo::ReductionFlags Flags=TargetTransformInfo::ReductionFlags(), ArrayRef< Value *> RedOps=None)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:858
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:58
BasicBlock * getSuccessor(unsigned i) const
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:716
MinMaxRecurrenceKind getMinMaxRecurrenceKind()
Metadata node.
Definition: Metadata.h:863
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
Value * getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=None)
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:816
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
iv Induction Variable Users
Definition: IVUsers.cpp:51
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
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:994
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:534
Tuple of metadata.
Definition: Metadata.h:1105
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:274
static MDNode * createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V)
Create MDNode for input string.
Definition: LoopUtils.cpp:196
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
IntegerType * getInt32Ty()
Fetch the type representing a 32-bit integer.
Definition: IRBuilder.h:383
The SCEV is loop-invariant.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
Definition: BasicBlock.cpp:174
This is the interface for a SCEV-based alias analysis.
void initializeLoopPassPass(PassRegistry &)
Manually defined generic "LoopPass" dependency initialization.
Definition: LoopUtils.cpp:183
unsigned getNumSuccessors() const
CallInst * CreateFAddReduce(Value *Acc, Value *Src)
Create a vector fadd reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:321
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
TransformationMode hasUnrollAndJamTransformation(Loop *L)
Definition: LoopUtils.cpp:408
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:196
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:119
BlockT * getHeader() const
Definition: LoopInfo.h:105
The transformation should be applied without considering a cost model.
Definition: LoopUtils.h:228
CallInst * CreateFPMinReduce(Value *Src, bool NoNaN=false)
Create a vector float min reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:387
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI)
This function deletes dead loops.
Definition: LoopUtils.cpp:502
Value * getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=None)
Generates an ordered vector reduction using extracts to reduce the value.
Definition: LoopUtils.cpp:785
Key
PAL metadata keys.
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:40
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
op_range operands() const
Definition: Metadata.h:1066
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:509
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:255
LLVMContext & getContext() const
Definition: Metadata.h:923
This is the common base class for debug info intrinsics for variables.
Definition: IntrinsicInst.h:87
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:998
void andIRFlags(const Value *V)
Logical &#39;and&#39; of any supported wrapping, exact, and fast-math flags of V and this instruction...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
AnalysisUsage & addPreservedID(const void *ID)
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:409
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
Definition: LoopUtils.cpp:207
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
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:50
The transformation must not be applied.
Definition: LoopUtils.h:245
use_iterator_impl< Use > use_iterator
Definition: Value.h:351
CallInst * CreateXorReduce(Value *Src)
Create a vector int XOR reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:359
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. ...
StringRef getString() const
Definition: Metadata.cpp:463
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2206
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
#define P(N)
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, 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...
static Optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
Definition: LoopUtils.cpp:262
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Optional< int > getOptionalIntLoopAttribute(Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
Definition: LoopUtils.cpp:284
void set(Value *Val)
Definition: Value.h:730
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:428
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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:208
Flags describing the kind of vector reduction.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.h:2271
Value * createMinMaxOp(IRBuilder<> &Builder, RecurrenceDescriptor::MinMaxRecurrenceKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:738
static const char * LLVMLoopDisableNonforced
Definition: LoopUtils.cpp:47
char & LCSSAID
Definition: LCSSA.cpp:467
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:370
Represent the analysis usage information of a pass.
TransformationMode hasDistributeTransformation(Loop *L)
Definition: LoopUtils.cpp:461
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:1184
TransformationMode hasVectorizeTransformation(Loop *L)
Definition: LoopUtils.cpp:426
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
Optional< unsigned > getLoopEstimatedTripCount(Loop *L)
Get a loop&#39;s estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:675
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2293
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1433
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:131
iterator_range< decltype(adl_begin(std::declval< T >)))> drop_begin(T &&t, int n)
size_t size() const
Definition: SmallVector.h:52
bool IsMaxOp
If the op a min/max kind, true if it&#39;s a max operation.
RecurrenceKind getRecurrenceKind()
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
Definition: LoopInfoImpl.h:122
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void propagateIRFlags(Value *I, ArrayRef< Value *> VL, Value *OpValue=nullptr)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
Definition: LoopUtils.cpp:975
signed greater than
Definition: InstrTypes.h:759
char & LoopSimplifyID
The transformation should not be applied.
Definition: LoopUtils.h:231
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:62
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:736
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
The pass can use heuristics to determine whether a transformation should be applied.
Definition: LoopUtils.h:225
CallInst * CreateAddReduce(Value *Src)
Create a vector int add reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:339
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
Legacy wrapper pass to provide the SCEVAAResult object.
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:239
Type * getType() const
Return the LLVM type of this SCEV expression.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
CallInst * CreateIntMaxReduce(Value *Src, bool IsSigned=false)
Create a vector integer max reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:364
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:314
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
static bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Definition: LoopUtils.cpp:280
Module.h This file contains the declarations for the Module class.
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:972
signed less than
Definition: InstrTypes.h:761
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:343
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:2320
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:541
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:640
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
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:703
CallInst * CreateFMulReduce(Value *Acc, Value *Src)
Create a vector fmul reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:330
Value * createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, RecurrenceDescriptor &Desc, Value *Src, bool NoNaN=false)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
Definition: LoopUtils.cpp:930
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:267
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:298
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:535
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
Class for arbitrary precision integers.
Definition: APInt.h:69
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:529
LLVM_NODISCARD bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:160
LoopT * getParentLoop() const
Definition: LoopInfo.h:106
CallInst * CreateAndReduce(Value *Src)
Create a vector int AND reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:349
bool hasValue() const
Definition: Optional.h:259
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:485
CallInst * CreateOrReduce(Value *Src)
Create a vector int OR reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:354
CallInst * CreateIntMinReduce(Value *Src, bool IsSigned=false)
Create a vector integer min reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:370
This class represents an analyzed expression in the program.
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:154
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
Optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopUtils.cpp:247
TransformationMode hasUnrollTransformation(Loop *L)
Definition: LoopUtils.cpp:387
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:137
CallInst * CreateMulReduce(Value *Src)
Create a vector int mul reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:344
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:222
block_iterator block_end() const
Definition: LoopInfo.h:160
FastMathFlags getFastMathFlags()
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:484
TransformationMode hasLICMVersioningTransformation(Loop *L)
Definition: LoopUtils.cpp:471
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:544
LLVM Value Representation.
Definition: Value.h:73
static const char * LLVMLoopDisableLICM
Definition: LoopUtils.cpp:48
bool useReductionIntrinsic(unsigned Opcode, Type *Ty, ReductionFlags Flags) const
succ_range successors(Instruction *I)
Definition: CFG.h:259
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition: IRBuilder.h:225
Metadata * get() const
Definition: Metadata.h:721
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1208
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:159
unsigned greater than
Definition: InstrTypes.h:755
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
A single uniqued string.
Definition: Metadata.h:603
const SCEV * getExitCount(const Loop *L, BasicBlock *ExitingBlock)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
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:1019
This pass exposes codegen information to IR-level passes.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
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:156
bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
Definition: LoopUtils.cpp:379
CallInst * CreateFPMaxReduce(Value *Src, bool NoNaN=false)
Create a vector float max reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:376
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
Definition: Metadata.cpp:1311
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:161
block_iterator block_begin() const
Definition: LoopInfo.h:159
Root of the metadata hierarchy.
Definition: Metadata.h:57
bool NoNaN
If op is an fp min/max, whether NaNs may be present.
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1097
signed greater or equal
Definition: InstrTypes.h:760
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:143
Legacy wrapper pass to provide the BasicAAResult object.
bool IsSigned
Whether the operation is a signed int reduction.