LLVM  14.0.0git
IVDescriptors.cpp
Go to the documentation of this file.
1 //===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===//
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 "describes" induction and recurrence variables.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/ScopeExit.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/LoopPass.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/IR/ValueHandle.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/KnownBits.h"
36 
37 #include <set>
38 
39 using namespace llvm;
40 using namespace llvm::PatternMatch;
41 
42 #define DEBUG_TYPE "iv-descriptors"
43 
46  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
47  if (!Set.count(dyn_cast<Instruction>(*Use)))
48  return false;
49  return true;
50 }
51 
53  switch (Kind) {
54  default:
55  break;
56  case RecurKind::Add:
57  case RecurKind::Mul:
58  case RecurKind::Or:
59  case RecurKind::And:
60  case RecurKind::Xor:
61  case RecurKind::SMax:
62  case RecurKind::SMin:
63  case RecurKind::UMax:
64  case RecurKind::UMin:
67  return true;
68  }
69  return false;
70 }
71 
73  return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind);
74 }
75 
77  switch (Kind) {
78  default:
79  break;
80  case RecurKind::Add:
81  case RecurKind::Mul:
82  case RecurKind::FAdd:
83  case RecurKind::FMul:
84  return true;
85  }
86  return false;
87 }
88 
89 /// Determines if Phi may have been type-promoted. If Phi has a single user
90 /// that ANDs the Phi with a type mask, return the user. RT is updated to
91 /// account for the narrower bit width represented by the mask, and the AND
92 /// instruction is added to CI.
96  if (!Phi->hasOneUse())
97  return Phi;
98 
99  const APInt *M = nullptr;
100  Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
101 
102  // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
103  // with a new integer type of the corresponding bit width.
104  if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
105  int32_t Bits = (*M + 1).exactLogBase2();
106  if (Bits > 0) {
107  RT = IntegerType::get(Phi->getContext(), Bits);
108  Visited.insert(Phi);
109  CI.insert(J);
110  return J;
111  }
112  }
113  return Phi;
114 }
115 
116 /// Compute the minimal bit width needed to represent a reduction whose exit
117 /// instruction is given by Exit.
118 static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
119  DemandedBits *DB,
120  AssumptionCache *AC,
121  DominatorTree *DT) {
122  bool IsSigned = false;
123  const DataLayout &DL = Exit->getModule()->getDataLayout();
124  uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
125 
126  if (DB) {
127  // Use the demanded bits analysis to determine the bits that are live out
128  // of the exit instruction, rounding up to the nearest power of two. If the
129  // use of demanded bits results in a smaller bit width, we know the value
130  // must be positive (i.e., IsSigned = false), because if this were not the
131  // case, the sign bit would have been demanded.
132  auto Mask = DB->getDemandedBits(Exit);
133  MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
134  }
135 
136  if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
137  // If demanded bits wasn't able to limit the bit width, we can try to use
138  // value tracking instead. This can be the case, for example, if the value
139  // may be negative.
140  auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
141  auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
142  MaxBitWidth = NumTypeBits - NumSignBits;
144  if (!Bits.isNonNegative()) {
145  // If the value is not known to be non-negative, we set IsSigned to true,
146  // meaning that we will use sext instructions instead of zext
147  // instructions to restore the original type.
148  IsSigned = true;
149  if (!Bits.isNegative())
150  // If the value is not known to be negative, we don't known what the
151  // upper bit is, and therefore, we don't know what kind of extend we
152  // will need. In this case, just increase the bit width by one bit and
153  // use sext.
154  ++MaxBitWidth;
155  }
156  }
157  if (!isPowerOf2_64(MaxBitWidth))
158  MaxBitWidth = NextPowerOf2(MaxBitWidth);
159 
160  return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
161  IsSigned);
162 }
163 
164 /// Collect cast instructions that can be ignored in the vectorizer's cost
165 /// model, given a reduction exit value and the minimal type in which the
166 /// reduction can be represented.
167 static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
168  Type *RecurrenceType,
170 
173  Worklist.push_back(Exit);
174 
175  while (!Worklist.empty()) {
176  Instruction *Val = Worklist.pop_back_val();
177  Visited.insert(Val);
178  if (auto *Cast = dyn_cast<CastInst>(Val))
179  if (Cast->getSrcTy() == RecurrenceType) {
180  // If the source type of a cast instruction is equal to the recurrence
181  // type, it will be eliminated, and should be ignored in the vectorizer
182  // cost model.
183  Casts.insert(Cast);
184  continue;
185  }
186 
187  // Add all operands to the work list if they are loop-varying values that
188  // we haven't yet visited.
189  for (Value *O : cast<User>(Val)->operands())
190  if (auto *I = dyn_cast<Instruction>(O))
191  if (TheLoop->contains(I) && !Visited.count(I))
192  Worklist.push_back(I);
193  }
194 }
195 
196 // Check if a given Phi node can be recognized as an ordered reduction for
197 // vectorizing floating point operations without unsafe math.
198 static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst,
199  Instruction *Exit, PHINode *Phi) {
200  // Currently only FAdd is supported
201  if (Kind != RecurKind::FAdd)
202  return false;
203 
204  if (Exit->getOpcode() != Instruction::FAdd || Exit != ExactFPMathInst)
205  return false;
206 
207  // The only pattern accepted is the one in which the reduction PHI
208  // is used as one of the operands of the exit instruction
209  auto *LHS = Exit->getOperand(0);
210  auto *RHS = Exit->getOperand(1);
211  if (LHS != Phi && RHS != Phi)
212  return false;
213 
214  LLVM_DEBUG(dbgs() << "LV: Found an ordered reduction: Phi: " << *Phi
215  << ", ExitInst: " << *Exit << "\n");
216 
217  return true;
218 }
219 
221  Loop *TheLoop, FastMathFlags FuncFMF,
222  RecurrenceDescriptor &RedDes,
223  DemandedBits *DB,
224  AssumptionCache *AC,
225  DominatorTree *DT) {
226  if (Phi->getNumIncomingValues() != 2)
227  return false;
228 
229  // Reduction variables are only found in the loop header block.
230  if (Phi->getParent() != TheLoop->getHeader())
231  return false;
232 
233  // Obtain the reduction start value from the value that comes from the loop
234  // preheader.
235  Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
236 
237  // ExitInstruction is the single value which is used outside the loop.
238  // We only allow for a single reduction value to be used outside the loop.
239  // This includes users of the reduction, variables (which form a cycle
240  // which ends in the phi node).
241  Instruction *ExitInstruction = nullptr;
242  // Indicates that we found a reduction operation in our scan.
243  bool FoundReduxOp = false;
244 
245  // We start with the PHI node and scan for all of the users of this
246  // instruction. All users must be instructions that can be used as reduction
247  // variables (such as ADD). We must have a single out-of-block user. The cycle
248  // must include the original PHI.
249  bool FoundStartPHI = false;
250 
251  // To recognize min/max patterns formed by a icmp select sequence, we store
252  // the number of instruction we saw from the recognized min/max pattern,
253  // to make sure we only see exactly the two instructions.
254  unsigned NumCmpSelectPatternInst = 0;
255  InstDesc ReduxDesc(false, nullptr);
256 
257  // Data used for determining if the recurrence has been type-promoted.
258  Type *RecurrenceType = Phi->getType();
260  Instruction *Start = Phi;
261  bool IsSigned = false;
262 
263  SmallPtrSet<Instruction *, 8> VisitedInsts;
265 
266  // Return early if the recurrence kind does not match the type of Phi. If the
267  // recurrence kind is arithmetic, we attempt to look through AND operations
268  // resulting from the type promotion performed by InstCombine. Vector
269  // operations are not limited to the legal integer widths, so we may be able
270  // to evaluate the reduction in the narrower width.
271  if (RecurrenceType->isFloatingPointTy()) {
272  if (!isFloatingPointRecurrenceKind(Kind))
273  return false;
274  } else if (RecurrenceType->isIntegerTy()) {
275  if (!isIntegerRecurrenceKind(Kind))
276  return false;
277  if (!isMinMaxRecurrenceKind(Kind))
278  Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
279  } else {
280  // Pointer min/max may exist, but it is not supported as a reduction op.
281  return false;
282  }
283 
284  Worklist.push_back(Start);
285  VisitedInsts.insert(Start);
286 
287  // Start with all flags set because we will intersect this with the reduction
288  // flags from all the reduction operations.
290 
291  // A value in the reduction can be used:
292  // - By the reduction:
293  // - Reduction operation:
294  // - One use of reduction value (safe).
295  // - Multiple use of reduction value (not safe).
296  // - PHI:
297  // - All uses of the PHI must be the reduction (safe).
298  // - Otherwise, not safe.
299  // - By instructions outside of the loop (safe).
300  // * One value may have several outside users, but all outside
301  // uses must be of the same value.
302  // - By an instruction that is not part of the reduction (not safe).
303  // This is either:
304  // * An instruction type other than PHI or the reduction operation.
305  // * A PHI in the header other than the initial PHI.
306  while (!Worklist.empty()) {
307  Instruction *Cur = Worklist.pop_back_val();
308 
309  // No Users.
310  // If the instruction has no users then this is a broken chain and can't be
311  // a reduction variable.
312  if (Cur->use_empty())
313  return false;
314 
315  bool IsAPhi = isa<PHINode>(Cur);
316 
317  // A header PHI use other than the original PHI.
318  if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
319  return false;
320 
321  // Reductions of instructions such as Div, and Sub is only possible if the
322  // LHS is the reduction variable.
323  if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
324  !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
325  !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
326  return false;
327 
328  // Any reduction instruction must be of one of the allowed kinds. We ignore
329  // the starting value (the Phi or an AND instruction if the Phi has been
330  // type-promoted).
331  if (Cur != Start) {
332  ReduxDesc =
333  isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF);
334  if (!ReduxDesc.isRecurrence())
335  return false;
336  // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
337  if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi) {
338  FastMathFlags CurFMF = ReduxDesc.getPatternInst()->getFastMathFlags();
339  if (auto *Sel = dyn_cast<SelectInst>(ReduxDesc.getPatternInst())) {
340  // Accept FMF on either fcmp or select of a min/max idiom.
341  // TODO: This is a hack to work-around the fact that FMF may not be
342  // assigned/propagated correctly. If that problem is fixed or we
343  // standardize on fmin/fmax via intrinsics, this can be removed.
344  if (auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))
345  CurFMF |= FCmp->getFastMathFlags();
346  }
347  FMF &= CurFMF;
348  }
349  // Update this reduction kind if we matched a new instruction.
350  // TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind'
351  // state accurate while processing the worklist?
352  if (ReduxDesc.getRecKind() != RecurKind::None)
353  Kind = ReduxDesc.getRecKind();
354  }
355 
356  bool IsASelect = isa<SelectInst>(Cur);
357 
358  // A conditional reduction operation must only have 2 or less uses in
359  // VisitedInsts.
360  if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) &&
361  hasMultipleUsesOf(Cur, VisitedInsts, 2))
362  return false;
363 
364  // A reduction operation must only have one use of the reduction value.
365  if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) &&
366  !isSelectCmpRecurrenceKind(Kind) &&
367  hasMultipleUsesOf(Cur, VisitedInsts, 1))
368  return false;
369 
370  // All inputs to a PHI node must be a reduction value.
371  if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
372  return false;
373 
374  if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectICmp) &&
375  (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
376  ++NumCmpSelectPatternInst;
377  if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectFCmp) &&
378  (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
379  ++NumCmpSelectPatternInst;
380 
381  // Check whether we found a reduction operator.
382  FoundReduxOp |= !IsAPhi && Cur != Start;
383 
384  // Process users of current instruction. Push non-PHI nodes after PHI nodes
385  // onto the stack. This way we are going to have seen all inputs to PHI
386  // nodes once we get to them.
389  for (User *U : Cur->users()) {
390  Instruction *UI = cast<Instruction>(U);
391 
392  // Check if we found the exit user.
393  BasicBlock *Parent = UI->getParent();
394  if (!TheLoop->contains(Parent)) {
395  // If we already know this instruction is used externally, move on to
396  // the next user.
397  if (ExitInstruction == Cur)
398  continue;
399 
400  // Exit if you find multiple values used outside or if the header phi
401  // node is being used. In this case the user uses the value of the
402  // previous iteration, in which case we would loose "VF-1" iterations of
403  // the reduction operation if we vectorize.
404  if (ExitInstruction != nullptr || Cur == Phi)
405  return false;
406 
407  // The instruction used by an outside user must be the last instruction
408  // before we feed back to the reduction phi. Otherwise, we loose VF-1
409  // operations on the value.
410  if (!is_contained(Phi->operands(), Cur))
411  return false;
412 
413  ExitInstruction = Cur;
414  continue;
415  }
416 
417  // Process instructions only once (termination). Each reduction cycle
418  // value must only be used once, except by phi nodes and min/max
419  // reductions which are represented as a cmp followed by a select.
420  InstDesc IgnoredVal(false, nullptr);
421  if (VisitedInsts.insert(UI).second) {
422  if (isa<PHINode>(UI))
423  PHIs.push_back(UI);
424  else
425  NonPHIs.push_back(UI);
426  } else if (!isa<PHINode>(UI) &&
427  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
428  !isa<SelectInst>(UI)) ||
429  (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
430  !isSelectCmpPattern(TheLoop, Phi, UI, IgnoredVal)
431  .isRecurrence() &&
432  !isMinMaxPattern(UI, Kind, IgnoredVal).isRecurrence())))
433  return false;
434 
435  // Remember that we completed the cycle.
436  if (UI == Phi)
437  FoundStartPHI = true;
438  }
439  Worklist.append(PHIs.begin(), PHIs.end());
440  Worklist.append(NonPHIs.begin(), NonPHIs.end());
441  }
442 
443  // This means we have seen one but not the other instruction of the
444  // pattern or more than just a select and cmp. Zero implies that we saw a
445  // llvm.min/max instrinsic, which is always OK.
446  if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2 &&
447  NumCmpSelectPatternInst != 0)
448  return false;
449 
450  if (isSelectCmpRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1)
451  return false;
452 
453  if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
454  return false;
455 
456  const bool IsOrdered = checkOrderedReduction(
457  Kind, ReduxDesc.getExactFPMathInst(), ExitInstruction, Phi);
458 
459  if (Start != Phi) {
460  // If the starting value is not the same as the phi node, we speculatively
461  // looked through an 'and' instruction when evaluating a potential
462  // arithmetic reduction to determine if it may have been type-promoted.
463  //
464  // We now compute the minimal bit width that is required to represent the
465  // reduction. If this is the same width that was indicated by the 'and', we
466  // can represent the reduction in the smaller type. The 'and' instruction
467  // will be eliminated since it will essentially be a cast instruction that
468  // can be ignore in the cost model. If we compute a different type than we
469  // did when evaluating the 'and', the 'and' will not be eliminated, and we
470  // will end up with different kinds of operations in the recurrence
471  // expression (e.g., IntegerAND, IntegerADD). We give up if this is
472  // the case.
473  //
474  // The vectorizer relies on InstCombine to perform the actual
475  // type-shrinking. It does this by inserting instructions to truncate the
476  // exit value of the reduction to the width indicated by RecurrenceType and
477  // then extend this value back to the original width. If IsSigned is false,
478  // a 'zext' instruction will be generated; otherwise, a 'sext' will be
479  // used.
480  //
481  // TODO: We should not rely on InstCombine to rewrite the reduction in the
482  // smaller type. We should just generate a correctly typed expression
483  // to begin with.
484  Type *ComputedType;
485  std::tie(ComputedType, IsSigned) =
486  computeRecurrenceType(ExitInstruction, DB, AC, DT);
487  if (ComputedType != RecurrenceType)
488  return false;
489 
490  // The recurrence expression will be represented in a narrower type. If
491  // there are any cast instructions that will be unnecessary, collect them
492  // in CastInsts. Note that the 'and' instruction was already included in
493  // this list.
494  //
495  // TODO: A better way to represent this may be to tag in some way all the
496  // instructions that are a part of the reduction. The vectorizer cost
497  // model could then apply the recurrence type to these instructions,
498  // without needing a white list of instructions to ignore.
499  // This may also be useful for the inloop reductions, if it can be
500  // kept simple enough.
501  collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
502  }
503 
504  // We found a reduction var if we have reached the original phi node and we
505  // only have a single instruction with out-of-loop users.
506 
507  // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
508  // is saved as part of the RecurrenceDescriptor.
509 
510  // Save the description of this reduction variable.
511  RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind, FMF,
512  ReduxDesc.getExactFPMathInst(), RecurrenceType,
513  IsSigned, IsOrdered, CastInsts);
514  RedDes = RD;
515 
516  return true;
517 }
518 
519 // We are looking for loops that do something like this:
520 // int r = 0;
521 // for (int i = 0; i < n; i++) {
522 // if (src[i] > 3)
523 // r = 3;
524 // }
525 // where the reduction value (r) only has two states, in this example 0 or 3.
526 // The generated LLVM IR for this type of loop will be like this:
527 // for.body:
528 // %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ]
529 // ...
530 // %cmp = icmp sgt i32 %5, 3
531 // %spec.select = select i1 %cmp, i32 3, i32 %r
532 // ...
533 // In general we can support vectorization of loops where 'r' flips between
534 // any two non-constants, provided they are loop invariant. The only thing
535 // we actually care about at the end of the loop is whether or not any lane
536 // in the selected vector is different from the start value. The final
537 // across-vector reduction after the loop simply involves choosing the start
538 // value if nothing changed (0 in the example above) or the other selected
539 // value (3 in the example above).
542  Instruction *I, InstDesc &Prev) {
543  // We must handle the select(cmp(),x,y) as a single instruction. Advance to
544  // the select.
545  CmpInst::Predicate Pred;
546  if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
547  if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
548  return InstDesc(Select, Prev.getRecKind());
549  }
550 
551  // Only match select with single use cmp condition.
552  if (!match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
553  m_Value())))
554  return InstDesc(false, I);
555 
556  SelectInst *SI = cast<SelectInst>(I);
557  Value *NonPhi = nullptr;
558 
559  if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue()))
560  NonPhi = SI->getFalseValue();
561  else if (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue()))
562  NonPhi = SI->getTrueValue();
563  else
564  return InstDesc(false, I);
565 
566  // We are looking for selects of the form:
567  // select(cmp(), phi, loop_invariant) or
568  // select(cmp(), loop_invariant, phi)
569  if (!Loop->isLoopInvariant(NonPhi))
570  return InstDesc(false, I);
571 
572  return InstDesc(I, isa<ICmpInst>(I->getOperand(0)) ? RecurKind::SelectICmp
574 }
575 
578  const InstDesc &Prev) {
579  assert((isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) &&
580  "Expected a cmp or select or call instruction");
581  if (!isMinMaxRecurrenceKind(Kind))
582  return InstDesc(false, I);
583 
584  // We must handle the select(cmp()) as a single instruction. Advance to the
585  // select.
586  CmpInst::Predicate Pred;
587  if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
588  if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
589  return InstDesc(Select, Prev.getRecKind());
590  }
591 
592  // Only match select with single use cmp condition, or a min/max intrinsic.
593  if (!isa<IntrinsicInst>(I) &&
594  !match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
595  m_Value())))
596  return InstDesc(false, I);
597 
598  // Look for a min/max pattern.
599  if (match(I, m_UMin(m_Value(), m_Value())))
600  return InstDesc(Kind == RecurKind::UMin, I);
601  if (match(I, m_UMax(m_Value(), m_Value())))
602  return InstDesc(Kind == RecurKind::UMax, I);
603  if (match(I, m_SMax(m_Value(), m_Value())))
604  return InstDesc(Kind == RecurKind::SMax, I);
605  if (match(I, m_SMin(m_Value(), m_Value())))
606  return InstDesc(Kind == RecurKind::SMin, I);
607  if (match(I, m_OrdFMin(m_Value(), m_Value())))
608  return InstDesc(Kind == RecurKind::FMin, I);
609  if (match(I, m_OrdFMax(m_Value(), m_Value())))
610  return InstDesc(Kind == RecurKind::FMax, I);
611  if (match(I, m_UnordFMin(m_Value(), m_Value())))
612  return InstDesc(Kind == RecurKind::FMin, I);
613  if (match(I, m_UnordFMax(m_Value(), m_Value())))
614  return InstDesc(Kind == RecurKind::FMax, I);
615  if (match(I, m_Intrinsic<Intrinsic::minnum>(m_Value(), m_Value())))
616  return InstDesc(Kind == RecurKind::FMin, I);
617  if (match(I, m_Intrinsic<Intrinsic::maxnum>(m_Value(), m_Value())))
618  return InstDesc(Kind == RecurKind::FMax, I);
619 
620  return InstDesc(false, I);
621 }
622 
623 /// Returns true if the select instruction has users in the compare-and-add
624 /// reduction pattern below. The select instruction argument is the last one
625 /// in the sequence.
626 ///
627 /// %sum.1 = phi ...
628 /// ...
629 /// %cmp = fcmp pred %0, %CFP
630 /// %add = fadd %0, %sum.1
631 /// %sum.2 = select %cmp, %add, %sum.1
634  SelectInst *SI = dyn_cast<SelectInst>(I);
635  if (!SI)
636  return InstDesc(false, I);
637 
638  CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
639  // Only handle single use cases for now.
640  if (!CI || !CI->hasOneUse())
641  return InstDesc(false, I);
642 
643  Value *TrueVal = SI->getTrueValue();
644  Value *FalseVal = SI->getFalseValue();
645  // Handle only when either of operands of select instruction is a PHI
646  // node for now.
647  if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
648  (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
649  return InstDesc(false, I);
650 
651  Instruction *I1 =
652  isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
653  : dyn_cast<Instruction>(TrueVal);
654  if (!I1 || !I1->isBinaryOp())
655  return InstDesc(false, I);
656 
657  Value *Op1, *Op2;
658  if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) ||
659  m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) &&
660  I1->isFast())
661  return InstDesc(Kind == RecurKind::FAdd, SI);
662 
663  if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
664  return InstDesc(Kind == RecurKind::FMul, SI);
665 
666  return InstDesc(false, I);
667 }
668 
672  InstDesc &Prev, FastMathFlags FuncFMF) {
673  assert(Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind);
674  switch (I->getOpcode()) {
675  default:
676  return InstDesc(false, I);
677  case Instruction::PHI:
678  return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst());
679  case Instruction::Sub:
680  case Instruction::Add:
681  return InstDesc(Kind == RecurKind::Add, I);
682  case Instruction::Mul:
683  return InstDesc(Kind == RecurKind::Mul, I);
684  case Instruction::And:
685  return InstDesc(Kind == RecurKind::And, I);
686  case Instruction::Or:
687  return InstDesc(Kind == RecurKind::Or, I);
688  case Instruction::Xor:
689  return InstDesc(Kind == RecurKind::Xor, I);
690  case Instruction::FDiv:
691  case Instruction::FMul:
692  return InstDesc(Kind == RecurKind::FMul, I,
693  I->hasAllowReassoc() ? nullptr : I);
694  case Instruction::FSub:
695  case Instruction::FAdd:
696  return InstDesc(Kind == RecurKind::FAdd, I,
697  I->hasAllowReassoc() ? nullptr : I);
698  case Instruction::Select:
700  return isConditionalRdxPattern(Kind, I);
702  case Instruction::FCmp:
703  case Instruction::ICmp:
704  case Instruction::Call:
705  if (isSelectCmpRecurrenceKind(Kind))
706  return isSelectCmpPattern(L, OrigPhi, I, Prev);
707  if (isIntMinMaxRecurrenceKind(Kind) ||
708  (((FuncFMF.noNaNs() && FuncFMF.noSignedZeros()) ||
709  (isa<FPMathOperator>(I) && I->hasNoNaNs() &&
710  I->hasNoSignedZeros())) &&
711  isFPMinMaxRecurrenceKind(Kind)))
712  return isMinMaxPattern(I, Kind, Prev);
713  return InstDesc(false, I);
714  }
715 }
716 
719  unsigned MaxNumUses) {
720  unsigned NumUses = 0;
721  for (const Use &U : I->operands()) {
722  if (Insts.count(dyn_cast<Instruction>(U)))
723  ++NumUses;
724  if (NumUses > MaxNumUses)
725  return true;
726  }
727 
728  return false;
729 }
730 
732  RecurrenceDescriptor &RedDes,
733  DemandedBits *DB, AssumptionCache *AC,
734  DominatorTree *DT) {
735  BasicBlock *Header = TheLoop->getHeader();
736  Function &F = *Header->getParent();
737  FastMathFlags FMF;
738  FMF.setNoNaNs(
739  F.getFnAttribute("no-nans-fp-math").getValueAsBool());
740  FMF.setNoSignedZeros(
741  F.getFnAttribute("no-signed-zeros-fp-math").getValueAsBool());
742 
743  if (AddReductionVar(Phi, RecurKind::Add, TheLoop, FMF, RedDes, DB, AC, DT)) {
744  LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
745  return true;
746  }
747  if (AddReductionVar(Phi, RecurKind::Mul, TheLoop, FMF, RedDes, DB, AC, DT)) {
748  LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
749  return true;
750  }
751  if (AddReductionVar(Phi, RecurKind::Or, TheLoop, FMF, RedDes, DB, AC, DT)) {
752  LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
753  return true;
754  }
755  if (AddReductionVar(Phi, RecurKind::And, TheLoop, FMF, RedDes, DB, AC, DT)) {
756  LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
757  return true;
758  }
759  if (AddReductionVar(Phi, RecurKind::Xor, TheLoop, FMF, RedDes, DB, AC, DT)) {
760  LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
761  return true;
762  }
763  if (AddReductionVar(Phi, RecurKind::SMax, TheLoop, FMF, RedDes, DB, AC, DT)) {
764  LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n");
765  return true;
766  }
767  if (AddReductionVar(Phi, RecurKind::SMin, TheLoop, FMF, RedDes, DB, AC, DT)) {
768  LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n");
769  return true;
770  }
771  if (AddReductionVar(Phi, RecurKind::UMax, TheLoop, FMF, RedDes, DB, AC, DT)) {
772  LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n");
773  return true;
774  }
775  if (AddReductionVar(Phi, RecurKind::UMin, TheLoop, FMF, RedDes, DB, AC, DT)) {
776  LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n");
777  return true;
778  }
779  if (AddReductionVar(Phi, RecurKind::SelectICmp, TheLoop, FMF, RedDes, DB, AC,
780  DT)) {
781  LLVM_DEBUG(dbgs() << "Found an integer conditional select reduction PHI."
782  << *Phi << "\n");
783  return true;
784  }
785  if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, FMF, RedDes, DB, AC, DT)) {
786  LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
787  return true;
788  }
789  if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, FMF, RedDes, DB, AC, DT)) {
790  LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
791  return true;
792  }
793  if (AddReductionVar(Phi, RecurKind::FMax, TheLoop, FMF, RedDes, DB, AC, DT)) {
794  LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n");
795  return true;
796  }
797  if (AddReductionVar(Phi, RecurKind::FMin, TheLoop, FMF, RedDes, DB, AC, DT)) {
798  LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n");
799  return true;
800  }
801  if (AddReductionVar(Phi, RecurKind::SelectFCmp, TheLoop, FMF, RedDes, DB, AC,
802  DT)) {
803  LLVM_DEBUG(dbgs() << "Found a float conditional select reduction PHI."
804  << " PHI." << *Phi << "\n");
805  return true;
806  }
807  // Not a reduction of known type.
808  return false;
809 }
810 
812  PHINode *Phi, Loop *TheLoop,
814 
815  // Ensure the phi node is in the loop header and has two incoming values.
816  if (Phi->getParent() != TheLoop->getHeader() ||
817  Phi->getNumIncomingValues() != 2)
818  return false;
819 
820  // Ensure the loop has a preheader and a single latch block. The loop
821  // vectorizer will need the latch to set up the next iteration of the loop.
822  auto *Preheader = TheLoop->getLoopPreheader();
823  auto *Latch = TheLoop->getLoopLatch();
824  if (!Preheader || !Latch)
825  return false;
826 
827  // Ensure the phi node's incoming blocks are the loop preheader and latch.
828  if (Phi->getBasicBlockIndex(Preheader) < 0 ||
829  Phi->getBasicBlockIndex(Latch) < 0)
830  return false;
831 
832  // Get the previous value. The previous value comes from the latch edge while
833  // the initial value comes form the preheader edge.
834  auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
835  if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
836  SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
837  return false;
838 
839  // Ensure every user of the phi node (recursively) is dominated by the
840  // previous value. The dominance requirement ensures the loop vectorizer will
841  // not need to vectorize the initial value prior to the first iteration of the
842  // loop.
843  // TODO: Consider extending this sinking to handle memory instructions.
844 
845  // We optimistically assume we can sink all users after Previous. Keep a set
846  // of instructions to sink after Previous ordered by dominance in the common
847  // basic block. It will be applied to SinkAfter if all users can be sunk.
848  auto CompareByComesBefore = [](const Instruction *A, const Instruction *B) {
849  return A->comesBefore(B);
850  };
851  std::set<Instruction *, decltype(CompareByComesBefore)> InstrsToSink(
852  CompareByComesBefore);
853 
854  BasicBlock *PhiBB = Phi->getParent();
856  auto TryToPushSinkCandidate = [&](Instruction *SinkCandidate) {
857  // Already sunk SinkCandidate.
858  if (SinkCandidate->getParent() == PhiBB &&
859  InstrsToSink.find(SinkCandidate) != InstrsToSink.end())
860  return true;
861 
862  // Cyclic dependence.
863  if (Previous == SinkCandidate)
864  return false;
865 
866  if (DT->dominates(Previous,
867  SinkCandidate)) // We already are good w/o sinking.
868  return true;
869 
870  if (SinkCandidate->getParent() != PhiBB ||
871  SinkCandidate->mayHaveSideEffects() ||
872  SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
873  return false;
874 
875  // Do not try to sink an instruction multiple times (if multiple operands
876  // are first order recurrences).
877  // TODO: We can support this case, by sinking the instruction after the
878  // 'deepest' previous instruction.
879  if (SinkAfter.find(SinkCandidate) != SinkAfter.end())
880  return false;
881 
882  // If we reach a PHI node that is not dominated by Previous, we reached a
883  // header PHI. No need for sinking.
884  if (isa<PHINode>(SinkCandidate))
885  return true;
886 
887  // Sink User tentatively and check its users
888  InstrsToSink.insert(SinkCandidate);
889  WorkList.push_back(SinkCandidate);
890  return true;
891  };
892 
893  WorkList.push_back(Phi);
894  // Try to recursively sink instructions and their users after Previous.
895  while (!WorkList.empty()) {
896  Instruction *Current = WorkList.pop_back_val();
897  for (User *User : Current->users()) {
898  if (!TryToPushSinkCandidate(cast<Instruction>(User)))
899  return false;
900  }
901  }
902 
903  // We can sink all users of Phi. Update the mapping.
904  for (Instruction *I : InstrsToSink) {
905  SinkAfter[I] = Previous;
906  Previous = I;
907  }
908  return true;
909 }
910 
911 /// This function returns the identity element (or neutral element) for
912 /// the operation K.
914  FastMathFlags FMF) {
915  switch (K) {
916  case RecurKind::Xor:
917  case RecurKind::Add:
918  case RecurKind::Or:
919  // Adding, Xoring, Oring zero to a number does not change it.
920  return ConstantInt::get(Tp, 0);
921  case RecurKind::Mul:
922  // Multiplying a number by 1 does not change it.
923  return ConstantInt::get(Tp, 1);
924  case RecurKind::And:
925  // AND-ing a number with an all-1 value does not change it.
926  return ConstantInt::get(Tp, -1, true);
927  case RecurKind::FMul:
928  // Multiplying a number by 1 does not change it.
929  return ConstantFP::get(Tp, 1.0L);
930  case RecurKind::FAdd:
931  // Adding zero to a number does not change it.
932  // FIXME: Ideally we should not need to check FMF for FAdd and should always
933  // use -0.0. However, this will currently result in mixed vectors of 0.0/-0.0.
934  // Instead, we should ensure that 1) the FMF from FAdd are propagated to the PHI
935  // nodes where possible, and 2) PHIs with the nsz flag + -0.0 use 0.0. This would
936  // mean we can then remove the check for noSignedZeros() below (see D98963).
937  if (FMF.noSignedZeros())
938  return ConstantFP::get(Tp, 0.0L);
939  return ConstantFP::get(Tp, -0.0L);
940  case RecurKind::UMin:
941  return ConstantInt::get(Tp, -1);
942  case RecurKind::UMax:
943  return ConstantInt::get(Tp, 0);
944  case RecurKind::SMin:
945  return ConstantInt::get(Tp,
947  case RecurKind::SMax:
948  return ConstantInt::get(Tp,
950  case RecurKind::FMin:
951  return ConstantFP::getInfinity(Tp, true);
952  case RecurKind::FMax:
953  return ConstantFP::getInfinity(Tp, false);
956  return getRecurrenceStartValue();
957  break;
958  default:
959  llvm_unreachable("Unknown recurrence kind");
960  }
961 }
962 
964  switch (Kind) {
965  case RecurKind::Add:
966  return Instruction::Add;
967  case RecurKind::Mul:
968  return Instruction::Mul;
969  case RecurKind::Or:
970  return Instruction::Or;
971  case RecurKind::And:
972  return Instruction::And;
973  case RecurKind::Xor:
974  return Instruction::Xor;
975  case RecurKind::FMul:
976  return Instruction::FMul;
977  case RecurKind::FAdd:
978  return Instruction::FAdd;
979  case RecurKind::SMax:
980  case RecurKind::SMin:
981  case RecurKind::UMax:
982  case RecurKind::UMin:
984  return Instruction::ICmp;
985  case RecurKind::FMax:
986  case RecurKind::FMin:
988  return Instruction::FCmp;
989  default:
990  llvm_unreachable("Unknown recurrence operation");
991  }
992 }
993 
996  SmallVector<Instruction *, 4> ReductionOperations;
997  unsigned RedOp = getOpcode(Kind);
998 
999  // Search down from the Phi to the LoopExitInstr, looking for instructions
1000  // with a single user of the correct type for the reduction.
1001 
1002  // Note that we check that the type of the operand is correct for each item in
1003  // the chain, including the last (the loop exit value). This can come up from
1004  // sub, which would otherwise be treated as an add reduction. MinMax also need
1005  // to check for a pair of icmp/select, for which we use getNextInstruction and
1006  // isCorrectOpcode functions to step the right number of instruction, and
1007  // check the icmp/select pair.
1008  // FIXME: We also do not attempt to look through Phi/Select's yet, which might
1009  // be part of the reduction chain, or attempt to looks through And's to find a
1010  // smaller bitwidth. Subs are also currently not allowed (which are usually
1011  // treated as part of a add reduction) as they are expected to generally be
1012  // more expensive than out-of-loop reductions, and need to be costed more
1013  // carefully.
1014  unsigned ExpectedUses = 1;
1015  if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp)
1016  ExpectedUses = 2;
1017 
1018  auto getNextInstruction = [&](Instruction *Cur) {
1019  if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1020  // We are expecting a icmp/select pair, which we go to the next select
1021  // instruction if we can. We already know that Cur has 2 uses.
1022  if (isa<SelectInst>(*Cur->user_begin()))
1023  return cast<Instruction>(*Cur->user_begin());
1024  else
1025  return cast<Instruction>(*std::next(Cur->user_begin()));
1026  }
1027  return cast<Instruction>(*Cur->user_begin());
1028  };
1029  auto isCorrectOpcode = [&](Instruction *Cur) {
1030  if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
1031  Value *LHS, *RHS;
1033  matchSelectPattern(Cur, LHS, RHS).Flavor);
1034  }
1035  return Cur->getOpcode() == RedOp;
1036  };
1037 
1038  // The loop exit instruction we check first (as a quick test) but add last. We
1039  // check the opcode is correct (and dont allow them to be Subs) and that they
1040  // have expected to have the expected number of uses. They will have one use
1041  // from the phi and one from a LCSSA value, no matter the type.
1042  if (!isCorrectOpcode(LoopExitInstr) || !LoopExitInstr->hasNUses(2))
1043  return {};
1044 
1045  // Check that the Phi has one (or two for min/max) uses.
1046  if (!Phi->hasNUses(ExpectedUses))
1047  return {};
1048  Instruction *Cur = getNextInstruction(Phi);
1049 
1050  // Each other instruction in the chain should have the expected number of uses
1051  // and be the correct opcode.
1052  while (Cur != LoopExitInstr) {
1053  if (!isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses))
1054  return {};
1055 
1056  ReductionOperations.push_back(Cur);
1057  Cur = getNextInstruction(Cur);
1058  }
1059 
1060  ReductionOperations.push_back(Cur);
1061  return ReductionOperations;
1062 }
1063 
1064 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
1065  const SCEV *Step, BinaryOperator *BOp,
1066  Type *ElementType,
1068  : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp),
1069  ElementType(ElementType) {
1070  assert(IK != IK_NoInduction && "Not an induction");
1071 
1072  // Start value type should match the induction kind and the value
1073  // itself should not be null.
1074  assert(StartValue && "StartValue is null");
1075  assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
1076  "StartValue is not a pointer for pointer induction");
1077  assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
1078  "StartValue is not an integer for integer induction");
1079 
1080  // Check the Step Value. It should be non-zero integer value.
1081  assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
1082  "Step value is zero");
1083 
1084  assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
1085  "Step value should be constant for pointer induction");
1086  assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
1087  "StepValue is not an integer");
1088 
1089  assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
1090  "StepValue is not FP for FpInduction");
1091  assert((IK != IK_FpInduction ||
1092  (InductionBinOp &&
1093  (InductionBinOp->getOpcode() == Instruction::FAdd ||
1094  InductionBinOp->getOpcode() == Instruction::FSub))) &&
1095  "Binary opcode should be specified for FP induction");
1096 
1097  if (IK == IK_PtrInduction)
1098  assert(ElementType && "Pointer induction must have element type");
1099  else
1100  assert(!ElementType && "Non-pointer induction cannot have element type");
1101 
1102  if (Casts) {
1103  for (auto &Inst : *Casts) {
1104  RedundantCasts.push_back(Inst);
1105  }
1106  }
1107 }
1108 
1110  if (isa<SCEVConstant>(Step))
1111  return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
1112  return nullptr;
1113 }
1114 
1116  ScalarEvolution *SE,
1118 
1119  // Here we only handle FP induction variables.
1120  assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
1121 
1122  if (TheLoop->getHeader() != Phi->getParent())
1123  return false;
1124 
1125  // The loop may have multiple entrances or multiple exits; we can analyze
1126  // this phi if it has a unique entry value and a unique backedge value.
1127  if (Phi->getNumIncomingValues() != 2)
1128  return false;
1129  Value *BEValue = nullptr, *StartValue = nullptr;
1130  if (TheLoop->contains(Phi->getIncomingBlock(0))) {
1131  BEValue = Phi->getIncomingValue(0);
1132  StartValue = Phi->getIncomingValue(1);
1133  } else {
1134  assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
1135  "Unexpected Phi node in the loop");
1136  BEValue = Phi->getIncomingValue(1);
1137  StartValue = Phi->getIncomingValue(0);
1138  }
1139 
1140  BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
1141  if (!BOp)
1142  return false;
1143 
1144  Value *Addend = nullptr;
1145  if (BOp->getOpcode() == Instruction::FAdd) {
1146  if (BOp->getOperand(0) == Phi)
1147  Addend = BOp->getOperand(1);
1148  else if (BOp->getOperand(1) == Phi)
1149  Addend = BOp->getOperand(0);
1150  } else if (BOp->getOpcode() == Instruction::FSub)
1151  if (BOp->getOperand(0) == Phi)
1152  Addend = BOp->getOperand(1);
1153 
1154  if (!Addend)
1155  return false;
1156 
1157  // The addend should be loop invariant
1158  if (auto *I = dyn_cast<Instruction>(Addend))
1159  if (TheLoop->contains(I))
1160  return false;
1161 
1162  // FP Step has unknown SCEV
1163  const SCEV *Step = SE->getUnknown(Addend);
1164  D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
1165  return true;
1166 }
1167 
1168 /// This function is called when we suspect that the update-chain of a phi node
1169 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
1170 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
1171 /// predicate P under which the SCEV expression for the phi can be the
1172 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
1173 /// cast instructions that are involved in the update-chain of this induction.
1174 /// A caller that adds the required runtime predicate can be free to drop these
1175 /// cast instructions, and compute the phi using \p AR (instead of some scev
1176 /// expression with casts).
1177 ///
1178 /// For example, without a predicate the scev expression can take the following
1179 /// form:
1180 /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
1181 ///
1182 /// It corresponds to the following IR sequence:
1183 /// %for.body:
1184 /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
1185 /// %casted_phi = "ExtTrunc i64 %x"
1186 /// %add = add i64 %casted_phi, %step
1187 ///
1188 /// where %x is given in \p PN,
1189 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
1190 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
1191 /// several forms, for example, such as:
1192 /// ExtTrunc1: %casted_phi = and %x, 2^n-1
1193 /// or:
1194 /// ExtTrunc2: %t = shl %x, m
1195 /// %casted_phi = ashr %t, m
1196 ///
1197 /// If we are able to find such sequence, we return the instructions
1198 /// we found, namely %casted_phi and the instructions on its use-def chain up
1199 /// to the phi (not including the phi).
1201  const SCEVUnknown *PhiScev,
1202  const SCEVAddRecExpr *AR,
1203  SmallVectorImpl<Instruction *> &CastInsts) {
1204 
1205  assert(CastInsts.empty() && "CastInsts is expected to be empty.");
1206  auto *PN = cast<PHINode>(PhiScev->getValue());
1207  assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
1208  const Loop *L = AR->getLoop();
1209 
1210  // Find any cast instructions that participate in the def-use chain of
1211  // PhiScev in the loop.
1212  // FORNOW/TODO: We currently expect the def-use chain to include only
1213  // two-operand instructions, where one of the operands is an invariant.
1214  // createAddRecFromPHIWithCasts() currently does not support anything more
1215  // involved than that, so we keep the search simple. This can be
1216  // extended/generalized as needed.
1217 
1218  auto getDef = [&](const Value *Val) -> Value * {
1219  const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
1220  if (!BinOp)
1221  return nullptr;
1222  Value *Op0 = BinOp->getOperand(0);
1223  Value *Op1 = BinOp->getOperand(1);
1224  Value *Def = nullptr;
1225  if (L->isLoopInvariant(Op0))
1226  Def = Op1;
1227  else if (L->isLoopInvariant(Op1))
1228  Def = Op0;
1229  return Def;
1230  };
1231 
1232  // Look for the instruction that defines the induction via the
1233  // loop backedge.
1234  BasicBlock *Latch = L->getLoopLatch();
1235  if (!Latch)
1236  return false;
1237  Value *Val = PN->getIncomingValueForBlock(Latch);
1238  if (!Val)
1239  return false;
1240 
1241  // Follow the def-use chain until the induction phi is reached.
1242  // If on the way we encounter a Value that has the same SCEV Expr as the
1243  // phi node, we can consider the instructions we visit from that point
1244  // as part of the cast-sequence that can be ignored.
1245  bool InCastSequence = false;
1246  auto *Inst = dyn_cast<Instruction>(Val);
1247  while (Val != PN) {
1248  // If we encountered a phi node other than PN, or if we left the loop,
1249  // we bail out.
1250  if (!Inst || !L->contains(Inst)) {
1251  return false;
1252  }
1253  auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
1254  if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
1255  InCastSequence = true;
1256  if (InCastSequence) {
1257  // Only the last instruction in the cast sequence is expected to have
1258  // uses outside the induction def-use chain.
1259  if (!CastInsts.empty())
1260  if (!Inst->hasOneUse())
1261  return false;
1262  CastInsts.push_back(Inst);
1263  }
1264  Val = getDef(Val);
1265  if (!Val)
1266  return false;
1267  Inst = dyn_cast<Instruction>(Val);
1268  }
1269 
1270  return InCastSequence;
1271 }
1272 
1275  InductionDescriptor &D, bool Assume) {
1276  Type *PhiTy = Phi->getType();
1277 
1278  // Handle integer and pointer inductions variables.
1279  // Now we handle also FP induction but not trying to make a
1280  // recurrent expression from the PHI node in-place.
1281 
1282  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
1283  !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
1284  return false;
1285 
1286  if (PhiTy->isFloatingPointTy())
1287  return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
1288 
1289  const SCEV *PhiScev = PSE.getSCEV(Phi);
1290  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1291 
1292  // We need this expression to be an AddRecExpr.
1293  if (Assume && !AR)
1294  AR = PSE.getAsAddRec(Phi);
1295 
1296  if (!AR) {
1297  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1298  return false;
1299  }
1300 
1301  // Record any Cast instructions that participate in the induction update
1302  const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1303  // If we started from an UnknownSCEV, and managed to build an addRecurrence
1304  // only after enabling Assume with PSCEV, this means we may have encountered
1305  // cast instructions that required adding a runtime check in order to
1306  // guarantee the correctness of the AddRecurrence respresentation of the
1307  // induction.
1308  if (PhiScev != AR && SymbolicPhi) {
1310  if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1311  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1312  }
1313 
1314  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1315 }
1316 
1318  PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1319  InductionDescriptor &D, const SCEV *Expr,
1320  SmallVectorImpl<Instruction *> *CastsToIgnore) {
1321  Type *PhiTy = Phi->getType();
1322  // We only handle integer and pointer inductions variables.
1323  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1324  return false;
1325 
1326  // Check that the PHI is consecutive.
1327  const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1328  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1329 
1330  if (!AR) {
1331  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1332  return false;
1333  }
1334 
1335  if (AR->getLoop() != TheLoop) {
1336  // FIXME: We should treat this as a uniform. Unfortunately, we
1337  // don't currently know how to handled uniform PHIs.
1338  LLVM_DEBUG(
1339  dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1340  return false;
1341  }
1342 
1343  Value *StartValue =
1345 
1346  BasicBlock *Latch = AR->getLoop()->getLoopLatch();
1347  if (!Latch)
1348  return false;
1349 
1350  const SCEV *Step = AR->getStepRecurrence(*SE);
1351  // Calculate the pointer stride and check if it is consecutive.
1352  // The stride may be a constant or a loop invariant integer value.
1353  const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1354  if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1355  return false;
1356 
1357  if (PhiTy->isIntegerTy()) {
1358  BinaryOperator *BOp =
1359  dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
1360  D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1361  /* ElementType */ nullptr, CastsToIgnore);
1362  return true;
1363  }
1364 
1365  assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1366  // Pointer induction should be a constant.
1367  if (!ConstStep)
1368  return false;
1369 
1370  // Always use i8 element type for opaque pointer inductions.
1371  PointerType *PtrTy = cast<PointerType>(PhiTy);
1372  Type *ElementType = PtrTy->isOpaque() ? Type::getInt8Ty(PtrTy->getContext())
1373  : PtrTy->getElementType();
1374  if (!ElementType->isSized())
1375  return false;
1376 
1377  ConstantInt *CV = ConstStep->getValue();
1378  const DataLayout &DL = Phi->getModule()->getDataLayout();
1379  int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(ElementType));
1380  if (!Size)
1381  return false;
1382 
1383  int64_t CVSize = CV->getSExtValue();
1384  if (CVSize % Size)
1385  return false;
1386  auto *StepValue =
1387  SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1388  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue,
1389  /* BinOp */ nullptr, ElementType);
1390  return true;
1391 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::NextPowerOf2
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:683
set
We currently generate a but we really shouldn eax ecx xorl edx divl ecx eax divl ecx movl eax ret A similar code sequence works for division We currently compile i32 v2 eax eax jo LBB1_2 atomic and others It is also currently not done for read modify write instructions It is also current not done if the OF or CF flags are needed The shift operators have the complication that when the shift count is EFLAGS is not set
Definition: README.txt:1277
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:263
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:64
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::FastMathFlags::getFast
static FastMathFlags getFast()
Definition: Operator.h:192
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:66
llvm::RecurKind::Or
@ Or
Bitwise or logical OR of integers.
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
llvm::RecurKind::FMul
@ FMul
Product of floats.
llvm::RecurrenceDescriptor::isReductionPHI
static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Returns true if Phi is a reduction in TheLoop.
Definition: IVDescriptors.cpp:731
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::ConstantInt::getType
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:173
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:217
llvm::FastMathFlags::setNoSignedZeros
void setNoSignedZeros(bool B=true)
Definition: Operator.h:226
llvm::PointerType::getElementType
Type * getElementType() const
Definition: DerivedTypes.h:673
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::PredicatedScalarEvolution
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Definition: ScalarEvolution.h:2122
llvm::SmallVector< Instruction *, 8 >
llvm::RecurrenceDescriptor::InstDesc::getPatternInst
Instruction * getPatternInst() const
Definition: IVDescriptors.h:104
DomTreeUpdater.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
ValueTracking.h
llvm::ConstantFP::getInfinity
static Constant * getInfinity(Type *Ty, bool Negative=false)
Definition: Constants.cpp:1080
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
GlobalsModRef.h
llvm::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
ScalarEvolution.h
llvm::InductionDescriptor::IK_IntInduction
@ IK_IntInduction
Integer induction variable. Step = C.
Definition: IVDescriptors.h:294
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::PatternMatch::m_UnordFMin
MaxMin_match< FCmpInst, LHS, RHS, ufmin_pred_ty > m_UnordFMin(const LHS &L, const RHS &R)
Match an 'unordered' floating point minimum function.
Definition: PatternMatch.h:1953
llvm::InductionDescriptor::isFPInductionPHI
static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D)
Returns true if Phi is a floating point induction in the loop L.
Definition: IVDescriptors.cpp:1115
llvm::FastMathFlags::noSignedZeros
bool noSignedZeros() const
Definition: Operator.h:209
llvm::RecurKind::SelectFCmp
@ SelectFCmp
Integer select(fcmp(),x,y) where one of (x,y) is loop invariant.
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet< Instruction *, 8 >
llvm::ComputeNumSignBits
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
Definition: ValueTracking.cpp:391
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:61
llvm::ScalarEvolution::getUnknown
const SCEV * getUnknown(Value *V)
Definition: ScalarEvolution.cpp:3936
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::matchSelectPattern
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
Definition: ValueTracking.cpp:6242
llvm::PatternMatch::m_c_And
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
Definition: PatternMatch.h:2242
collectCastsToIgnore
static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit, Type *RecurrenceType, SmallPtrSetImpl< Instruction * > &Casts)
Collect cast instructions that can be ignored in the vectorizer's cost model, given a reduction exit ...
Definition: IVDescriptors.cpp:167
llvm::SCEVConstant::getValue
ConstantInt * getValue() const
Definition: ScalarEvolutionExpressions.h:56
llvm::FastMathFlags
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:161
llvm::RecurKind::SMin
@ SMin
Signed integer min implemented in terms of select(cmp()).
llvm::FastMathFlags::noNaNs
bool noNaNs() const
Definition: Operator.h:207
llvm::Type::isFloatingPointTy
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:162
BasicAliasAnalysis.h
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::PredicatedScalarEvolution::getAsAddRec
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
Definition: ScalarEvolution.cpp:13414
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:239
MustExecute.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
checkOrderedReduction
static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst, Instruction *Exit, PHINode *Phi)
Definition: IVDescriptors.cpp:198
llvm::PatternMatch::m_FAdd
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1014
KnownBits.h
llvm::PatternMatch::m_FSub
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1026
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PatternMatch::m_OneUse
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
llvm::RecurKind
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:38
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:270
llvm::PatternMatch::m_UMax
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty > m_UMax(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1875
llvm::PatternMatch::m_OrdFMin
MaxMin_match< FCmpInst, LHS, RHS, ofmin_pred_ty > m_OrdFMin(const LHS &L, const RHS &R)
Match an 'ordered' floating point minimum function.
Definition: PatternMatch.h:1922
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::InductionDescriptor
A struct for saving information about induction variables.
Definition: IVDescriptors.h:289
llvm::RecurKind::And
@ And
Bitwise or logical AND of integers.
llvm::PatternMatch::m_Select
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Definition: PatternMatch.h:1472
llvm::RecurrenceDescriptor::getReductionOpChain
SmallVector< Instruction *, 4 > getReductionOpChain(PHINode *Phi, Loop *L) const
Attempts to find a chain of operations from Phi to LoopExitInst that can be treated as a set of reduc...
Definition: IVDescriptors.cpp:995
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
isZero
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:519
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2729
llvm::InductionDescriptor::IK_PtrInduction
@ IK_PtrInduction
Pointer induction var. Step = C / sizeof(elem).
Definition: IVDescriptors.h:295
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::User
Definition: User.h:44
llvm::RecurrenceDescriptor::InstDesc::getExactFPMathInst
Instruction * getExactFPMathInst() const
Definition: IVDescriptors.h:100
llvm::SelectPatternResult::isMinOrMax
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
Definition: ValueTracking.h:708
llvm::RecurrenceDescriptor::hasMultipleUsesOf
static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction * > &Insts, unsigned MaxNumUses)
Returns true if instruction I has multiple uses in Insts.
Definition: IVDescriptors.cpp:717
getOpcode
static Optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:199
llvm::RecurrenceDescriptor::getOpcode
unsigned getOpcode() const
Definition: IVDescriptors.h:198
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:748
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::RecurrenceDescriptor::isSelectCmpPattern
static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi, Instruction *I, InstDesc &Prev)
Returns a struct describing whether the instruction is either a Select(ICmp(A, B),...
Definition: IVDescriptors.cpp:541
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2818
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:393
llvm::Instruction
Definition: Instruction.h:45
llvm::PatternMatch::m_UMin
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1881
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:925
llvm::RecurKind::None
@ None
Not a recurrence.
llvm::PatternMatch::m_UnordFMax
MaxMin_match< FCmpInst, LHS, RHS, ufmax_pred_ty > m_UnordFMax(const LHS &L, const RHS &R)
Match an 'unordered' floating point maximum function.
Definition: PatternMatch.h:1938
llvm::RecurrenceDescriptor::getRecurrenceIdentity
Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF)
Returns identity corresponding to the RecurrenceKind.
Definition: IVDescriptors.cpp:913
PatternMatch.h
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::PointerType::isOpaque
bool isOpaque() const
Definition: DerivedTypes.h:678
IVDescriptors.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2725
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::SCEVUnknown::getValue
Value * getValue() const
Definition: ScalarEvolutionExpressions.h:551
llvm::RecurKind::UMin
@ UMin
Unisgned integer min implemented in terms of select(cmp()).
llvm::Instruction::isCommutative
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
Definition: Instruction.cpp:758
LoopInfo.h
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4082
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:190
llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
Definition: ScalarEvolution.cpp:5266
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
llvm::MapVector::find
iterator find(const KeyT &Key)
Definition: MapVector.h:147
uint64_t
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::InductionDescriptor::InductionDescriptor
InductionDescriptor()=default
Default constructor - creates an invalid induction.
llvm::DemandedBits
Definition: DemandedBits.h:40
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::PHINode::getBasicBlockIndex
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: Instructions.h:2811
llvm::RecurKind::Add
@ Add
Sum of integers.
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1616
llvm::SCEVConstant
This class represents a constant integer value.
Definition: ScalarEvolutionExpressions.h:47
llvm::Type::isHalfTy
bool isHalfTy() const
Return true if this is 'half', a 16-bit IEEE fp type.
Definition: Type.h:141
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:224
llvm::InductionDescriptor::getConstIntStepValue
ConstantInt * getConstIntStepValue() const
Definition: IVDescriptors.cpp:1109
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PredicatedScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
Definition: ScalarEvolution.cpp:13333
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::Instruction::isFast
bool isFast() const
Determine whether all fast-math-flags are set.
Definition: Instruction.cpp:240
llvm::InductionDescriptor::IK_FpInduction
@ IK_FpInduction
Floating point induction variable.
Definition: IVDescriptors.h:296
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:360
llvm::Instruction::isBinaryOp
bool isBinaryOp() const
Definition: Instruction.h:165
llvm::PatternMatch::m_SMin
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1869
lookThroughAnd
static Instruction * lookThroughAnd(PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction * > &Visited, SmallPtrSetImpl< Instruction * > &CI)
Determines if Phi may have been type-promoted.
Definition: IVDescriptors.cpp:93
llvm::RecurrenceDescriptor::isArithmeticRecurrenceKind
static bool isArithmeticRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an arithmetic kind.
Definition: IVDescriptors.cpp:76
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::RecurKind::UMax
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
llvm::RecurrenceDescriptor::AddReductionVar
static bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.
Definition: IVDescriptors.cpp:220
llvm::Instruction::getFastMathFlags
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Definition: Instruction.cpp:280
llvm::BinaryOperator
Definition: InstrTypes.h:189
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:444
LoopPass.h
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::RecurrenceDescriptor::InstDesc::isRecurrence
bool isRecurrence() const
Definition: IVDescriptors.h:96
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:993
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::RecurrenceDescriptor::isConditionalRdxPattern
static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I)
Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode),...
Definition: IVDescriptors.cpp:633
llvm::RecurKind::Mul
@ Mul
Product of integers.
llvm::RecurKind::FMax
@ FMax
FP max implemented in terms of select(cmp()).
llvm::ConstantInt::getSExtValue
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:148
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:286
llvm::PatternMatch::m_SMax
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1863
getCastsForInductionPHI
static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE, const SCEVUnknown *PhiScev, const SCEVAddRecExpr *AR, SmallVectorImpl< Instruction * > &CastInsts)
This function is called when we suspect that the update-chain of a phi node (whose symbolic SCEV expr...
Definition: IVDescriptors.cpp:1200
llvm::Type::getContext
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:127
ValueHandle.h
llvm::RecurrenceDescriptor::InstDesc
This POD struct holds information about a potential recurrence operation.
Definition: IVDescriptors.h:86
llvm::PatternMatch::m_OrdFMax
MaxMin_match< FCmpInst, LHS, RHS, ofmax_pred_ty > m_OrdFMax(const LHS &L, const RHS &R)
Match an 'ordered' floating point maximum function.
Definition: PatternMatch.h:1907
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:12633
llvm::MapVector::end
iterator end()
Definition: MapVector.h:71
DemandedBits.h
llvm::RecurrenceDescriptor::InstDesc::getRecKind
RecurKind getRecKind() const
Definition: IVDescriptors.h:102
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
llvm::RecurrenceDescriptor::isFloatingPointRecurrenceKind
static bool isFloatingPointRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating point kind.
Definition: IVDescriptors.cpp:72
llvm::InductionDescriptor::isInductionPHI
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
Definition: IVDescriptors.cpp:1317
llvm::MapVector::count
size_type count(const KeyT &Key) const
Definition: MapVector.h:142
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:364
llvm::KnownBits
Definition: KnownBits.h:23
llvm::Type::getIntNTy
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:245
llvm::RecurrenceDescriptor::areAllUsesIn
static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction * > &Set)
Returns true if all uses of the instruction I is within the Set.
Definition: IVDescriptors.cpp:44
llvm::Type::isFloatTy
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
Definition: Type.h:147
llvm::ConstantFP::get
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:972
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
llvm::RecurrenceDescriptor::isFirstOrderRecurrence
static bool isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, MapVector< Instruction *, Instruction * > &SinkAfter, DominatorTree *DT)
Returns true if Phi is a first-order recurrence.
Definition: IVDescriptors.cpp:811
llvm::Value::hasNUses
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
Definition: Value.cpp:149
llvm::SCEVUnknown
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
Definition: ScalarEvolutionExpressions.h:530
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::Type::isDoubleTy
bool isDoubleTy() const
Return true if this is 'double', a 64-bit IEEE fp type.
Definition: Type.h:150
ScalarEvolutionAliasAnalysis.h
llvm::DemandedBits::getDemandedBits
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
Definition: DemandedBits.cpp:443
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::APInt::getSignedMinValue
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
ScalarEvolutionExpressions.h
llvm::RecurrenceDescriptor
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:71
llvm::RecurKind::SelectICmp
@ SelectICmp
Integer select(icmp(),x,y) where one of (x,y) is loop invariant.
llvm::RecurKind::FAdd
@ FAdd
Sum of floats.
Instructions.h
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2749
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2633
llvm::PatternMatch
Definition: PatternMatch.h:47
ScopeExit.h
llvm::RecurrenceDescriptor::isIntegerRecurrenceKind
static bool isIntegerRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer kind.
Definition: IVDescriptors.cpp:52
llvm::SmallVectorImpl< Instruction * >
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
llvm::SmallPtrSetImpl< Instruction * >
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:377
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:313
llvm::RecurKind::FMin
@ FMin
FP min implemented in terms of select(cmp()).
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::PredicatedScalarEvolution::getSE
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
Definition: ScalarEvolution.h:2154
llvm::PatternMatch::m_FMul
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1081
llvm::isPowerOf2_64
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:496
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:61
llvm::RecurrenceDescriptor::isRecurrenceInstr
static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I, RecurKind Kind, InstDesc &Prev, FastMathFlags FuncFMF)
Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind' for a ...
Definition: IVDescriptors.cpp:670
llvm::PatternMatch::m_Cmp
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:89
llvm::RecurrenceDescriptor::isMinMaxPattern
static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind, const InstDesc &Prev)
Returns a struct describing if the instruction is a llvm.
Definition: IVDescriptors.cpp:577
computeRecurrenceType
static std::pair< Type *, bool > computeRecurrenceType(Instruction *Exit, DemandedBits *DB, AssumptionCache *AC, DominatorTree *DT)
Compute the minimal bit width needed to represent a reduction whose exit instruction is given by Exit...
Definition: IVDescriptors.cpp:118
llvm::RecurKind::SMax
@ SMax
Signed integer max implemented in terms of select(cmp()).
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::FastMathFlags::setNoNaNs
void setNoNaNs(bool B=true)
Definition: Operator.h:220
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::SCEVAddRecExpr::getStepRecurrence
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Definition: ScalarEvolutionExpressions.h:370
llvm::RecurKind::Xor
@ Xor
Bitwise or logical XOR of integers.
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
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:364
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:773