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