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