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