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  Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI();
588  assert(InsertDbgValueBefore &&
589  "There should be a non-PHI instruction in exit block, else these "
590  "instructions will have no parent.");
591  for (auto *DVI : DeadDebugInst)
592  DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()),
593  DVI->getVariable(), DVI->getExpression(),
594  DVI->getDebugLoc(), InsertDbgValueBefore);
595 
596  // Remove the block from the reference counting scheme, so that we can
597  // delete it freely later.
598  for (auto *Block : L->blocks())
599  Block->dropAllReferences();
600 
601  if (LI) {
602  // Erase the instructions and the blocks without having to worry
603  // about ordering because we already dropped the references.
604  // NOTE: This iteration is safe because erasing the block does not remove
605  // its entry from the loop's block list. We do that in the next section.
606  for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
607  LpI != LpE; ++LpI)
608  (*LpI)->eraseFromParent();
609 
610  // Finally, the blocks from loopinfo. This has to happen late because
611  // otherwise our loop iterators won't work.
612 
614  blocks.insert(L->block_begin(), L->block_end());
615  for (BasicBlock *BB : blocks)
616  LI->removeBlock(BB);
617 
618  // The last step is to update LoopInfo now that we've eliminated this loop.
619  LI->erase(L);
620  }
621 }
622 
624  // Only support loops with a unique exiting block, and a latch.
625  if (!L->getExitingBlock())
626  return None;
627 
628  // Get the branch weights for the loop's backedge.
629  BranchInst *LatchBR =
631  if (!LatchBR || LatchBR->getNumSuccessors() != 2)
632  return None;
633 
634  assert((LatchBR->getSuccessor(0) == L->getHeader() ||
635  LatchBR->getSuccessor(1) == L->getHeader()) &&
636  "At least one edge out of the latch must go to the header");
637 
638  // To estimate the number of times the loop body was executed, we want to
639  // know the number of times the backedge was taken, vs. the number of times
640  // we exited the loop.
641  uint64_t TrueVal, FalseVal;
642  if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
643  return None;
644 
645  if (!TrueVal || !FalseVal)
646  return 0;
647 
648  // Divide the count of the backedge by the count of the edge exiting the loop,
649  // rounding to nearest.
650  if (LatchBR->getSuccessor(0) == L->getHeader())
651  return (TrueVal + (FalseVal / 2)) / FalseVal;
652  else
653  return (FalseVal + (TrueVal / 2)) / TrueVal;
654 }
655 
657  ScalarEvolution &SE) {
658  Loop *OuterL = InnerLoop->getParentLoop();
659  if (!OuterL)
660  return true;
661 
662  // Get the backedge taken count for the inner loop
663  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
664  const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
665  if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
666  !InnerLoopBECountSC->getType()->isIntegerTy())
667  return false;
668 
669  // Get whether count is invariant to the outer loop
671  SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
673  return false;
674 
675  return true;
676 }
677 
680  Value *Left, Value *Right) {
682  switch (RK) {
683  default:
684  llvm_unreachable("Unknown min/max recurrence kind");
686  P = CmpInst::ICMP_ULT;
687  break;
689  P = CmpInst::ICMP_UGT;
690  break;
692  P = CmpInst::ICMP_SLT;
693  break;
695  P = CmpInst::ICMP_SGT;
696  break;
698  P = CmpInst::FCMP_OLT;
699  break;
701  P = CmpInst::FCMP_OGT;
702  break;
703  }
704 
705  // We only match FP sequences that are 'fast', so we can unconditionally
706  // set it on any generated instructions.
707  IRBuilder<>::FastMathFlagGuard FMFG(Builder);
708  FastMathFlags FMF;
709  FMF.setFast();
710  Builder.setFastMathFlags(FMF);
711 
712  Value *Cmp;
715  Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
716  else
717  Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
718 
719  Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
720  return Select;
721 }
722 
723 // Helper to generate an ordered reduction.
724 Value *
726  unsigned Op,
728  ArrayRef<Value *> RedOps) {
729  unsigned VF = Src->getType()->getVectorNumElements();
730 
731  // Extract and apply reduction ops in ascending order:
732  // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
733  Value *Result = Acc;
734  for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
735  Value *Ext =
736  Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
737 
738  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
739  Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
740  "bin.rdx");
741  } else {
743  "Invalid min/max");
744  Result = createMinMaxOp(Builder, MinMaxKind, Result, Ext);
745  }
746 
747  if (!RedOps.empty())
748  propagateIRFlags(Result, RedOps);
749  }
750 
751  return Result;
752 }
753 
754 // Helper to generate a log2 shuffle reduction.
755 Value *
758  ArrayRef<Value *> RedOps) {
759  unsigned VF = Src->getType()->getVectorNumElements();
760  // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
761  // and vector ops, reducing the set of values being computed by half each
762  // round.
763  assert(isPowerOf2_32(VF) &&
764  "Reduction emission only supported for pow2 vectors!");
765  Value *TmpVec = Src;
766  SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
767  for (unsigned i = VF; i != 1; i >>= 1) {
768  // Move the upper half of the vector to the lower half.
769  for (unsigned j = 0; j != i / 2; ++j)
770  ShuffleMask[j] = Builder.getInt32(i / 2 + j);
771 
772  // Fill the rest of the mask with undef.
773  std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
774  UndefValue::get(Builder.getInt32Ty()));
775 
776  Value *Shuf = Builder.CreateShuffleVector(
777  TmpVec, UndefValue::get(TmpVec->getType()),
778  ConstantVector::get(ShuffleMask), "rdx.shuf");
779 
780  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
781  // The builder propagates its fast-math-flags setting.
782  TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf,
783  "bin.rdx");
784  } else {
786  "Invalid min/max");
787  TmpVec = createMinMaxOp(Builder, MinMaxKind, TmpVec, Shuf);
788  }
789  if (!RedOps.empty())
790  propagateIRFlags(TmpVec, RedOps);
791  }
792  // The result is in the first element of the vector.
793  return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
794 }
795 
796 /// Create a simple vector reduction specified by an opcode and some
797 /// flags (if generating min/max reductions).
799  IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
801  ArrayRef<Value *> RedOps) {
802  assert(isa<VectorType>(Src->getType()) && "Type must be a vector");
803 
804  std::function<Value *()> BuildFunc;
805  using RD = RecurrenceDescriptor;
806  RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
807 
808  switch (Opcode) {
809  case Instruction::Add:
810  BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
811  break;
812  case Instruction::Mul:
813  BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
814  break;
815  case Instruction::And:
816  BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
817  break;
818  case Instruction::Or:
819  BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
820  break;
821  case Instruction::Xor:
822  BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
823  break;
824  case Instruction::FAdd:
825  BuildFunc = [&]() {
826  auto Rdx = Builder.CreateFAddReduce(
828  return Rdx;
829  };
830  break;
831  case Instruction::FMul:
832  BuildFunc = [&]() {
833  Type *Ty = Src->getType()->getVectorElementType();
834  auto Rdx = Builder.CreateFMulReduce(ConstantFP::get(Ty, 1.0), Src);
835  return Rdx;
836  };
837  break;
838  case Instruction::ICmp:
839  if (Flags.IsMaxOp) {
840  MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
841  BuildFunc = [&]() {
842  return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
843  };
844  } else {
845  MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
846  BuildFunc = [&]() {
847  return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
848  };
849  }
850  break;
851  case Instruction::FCmp:
852  if (Flags.IsMaxOp) {
853  MinMaxKind = RD::MRK_FloatMax;
854  BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
855  } else {
856  MinMaxKind = RD::MRK_FloatMin;
857  BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
858  }
859  break;
860  default:
861  llvm_unreachable("Unhandled opcode");
862  break;
863  }
864  if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
865  return BuildFunc();
866  return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
867 }
868 
869 /// Create a vector reduction using a given recurrence descriptor.
871  const TargetTransformInfo *TTI,
872  RecurrenceDescriptor &Desc, Value *Src,
873  bool NoNaN) {
874  // TODO: Support in-order reductions based on the recurrence descriptor.
875  using RD = RecurrenceDescriptor;
876  RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
878  Flags.NoNaN = NoNaN;
879 
880  // All ops in the reduction inherit fast-math-flags from the recurrence
881  // descriptor.
882  IRBuilder<>::FastMathFlagGuard FMFGuard(B);
884 
885  switch (RecKind) {
886  case RD::RK_FloatAdd:
887  return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
888  case RD::RK_FloatMult:
889  return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
890  case RD::RK_IntegerAdd:
891  return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
892  case RD::RK_IntegerMult:
893  return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
894  case RD::RK_IntegerAnd:
895  return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
896  case RD::RK_IntegerOr:
897  return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
898  case RD::RK_IntegerXor:
899  return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
900  case RD::RK_IntegerMinMax: {
901  RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
902  Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_UIntMax);
903  Flags.IsSigned = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_SIntMin);
904  return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
905  }
906  case RD::RK_FloatMinMax: {
907  Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
908  return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
909  }
910  default:
911  llvm_unreachable("Unhandled RecKind");
912  }
913 }
914 
916  auto *VecOp = dyn_cast<Instruction>(I);
917  if (!VecOp)
918  return;
919  auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
920  : dyn_cast<Instruction>(OpValue);
921  if (!Intersection)
922  return;
923  const unsigned Opcode = Intersection->getOpcode();
924  VecOp->copyIRFlags(Intersection);
925  for (auto *V : VL) {
926  auto *Instr = dyn_cast<Instruction>(V);
927  if (!Instr)
928  continue;
929  if (OpValue == nullptr || Opcode == Instr->getOpcode())
930  VecOp->andIRFlags(V);
931  }
932 }
933 
934 bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
935  ScalarEvolution &SE) {
936  const SCEV *Zero = SE.getZero(S->getType());
937  return SE.isAvailableAtLoopEntry(S, L) &&
939 }
940 
941 bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
942  ScalarEvolution &SE) {
943  const SCEV *Zero = SE.getZero(S->getType());
944  return SE.isAvailableAtLoopEntry(S, L) &&
946 }
947 
948 bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
949  bool Signed) {
950  unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
951  APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) :
952  APInt::getMinValue(BitWidth);
954  return SE.isAvailableAtLoopEntry(S, L) &&
956  SE.getConstant(Min));
957 }
958 
959 bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
960  bool Signed) {
961  unsigned BitWidth = cast<IntegerType>(S->getType())->getBitWidth();
962  APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) :
963  APInt::getMaxValue(BitWidth);
965  return SE.isAvailableAtLoopEntry(S, L) &&
967  SE.getConstant(Max));
968 }
Legacy wrapper pass to provide the GlobalsAAResult object.
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Type * getVectorElementType() const
Definition: Type.h:371
const NoneType None
Definition: None.h:23
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:710
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2026
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
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:409
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:948
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:941
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
unsigned less than
Definition: InstrTypes.h:757
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop&#39;s entry.
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:738
Value * createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, unsigned Opcode, Value *Src, TargetTransformInfo::ReductionFlags Flags=TargetTransformInfo::ReductionFlags(), ArrayRef< Value *> RedOps=None)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:798
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:656
MinMaxRecurrenceKind getMinMaxRecurrenceKind()
Metadata node.
Definition: Metadata.h:863
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
Value * getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=None)
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:756
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:934
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:534
Tuple of metadata.
Definition: Metadata.h:1105
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:274
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.
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:102
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:387
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:725
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:960
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:359
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS. ...
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2034
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:681
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.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
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:2099
Value * createMinMaxOp(IRBuilder<> &Builder, RecurrenceDescriptor::MinMaxRecurrenceKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:678
static const char * LLVMLoopDisableNonforced
Definition: LoopUtils.cpp:47
char & LCSSAID
Definition: LCSSA.cpp:467
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Represent the analysis usage information of a pass.
TransformationMode hasDistributeTransformation(Loop *L)
Definition: LoopUtils.cpp: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:1199
TransformationMode hasVectorizeTransformation(Loop *L)
Definition: LoopUtils.cpp:374
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
Optional< unsigned > getLoopEstimatedTripCount(Loop *L)
Get a loop&#39;s estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:623
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2121
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:915
signed greater than
Definition: InstrTypes.h:759
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:736
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:112
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:339
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
Legacy wrapper pass to provide the SCEVAAResult object.
The transformation was directed by the user, e.g.
Definition: LoopUtils.h: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:364
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:314
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
static bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Definition: LoopUtils.cpp: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:934
signed less than
Definition: InstrTypes.h:761
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:2148
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
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:694
CallInst * CreateFMulReduce(Value *Acc, Value *Src)
Create a vector fmul reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:330
Value * createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, RecurrenceDescriptor &Desc, Value *Src, bool NoNaN=false)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
Definition: LoopUtils.cpp:870
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:535
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
Class for arbitrary precision integers.
Definition: APInt.h:69
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:529
LoopT * getParentLoop() const
Definition: LoopInfo.h:103
CallInst * CreateAndReduce(Value *Src)
Create a vector int AND reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:349
bool hasValue() const
Definition: Optional.h:259
CallInst * CreateOrReduce(Value *Src)
Create a vector int OR reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:354
CallInst * CreateIntMinReduce(Value *Src, bool IsSigned=false)
Create a vector integer min reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:370
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:467
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:151
#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:344
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:218
block_iterator block_end() const
Definition: LoopInfo.h:157
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:1138
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:159
unsigned greater than
Definition: InstrTypes.h:755
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
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:959
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:376
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
Definition: Metadata.cpp:1311
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:158
block_iterator block_begin() const
Definition: LoopInfo.h:156
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:760
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:143
Legacy wrapper pass to provide the BasicAAResult object.
bool IsSigned
Whether the operation is a signed int reduction.