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