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:
65  return true;
66  }
67  return false;
68 }
69 
71  return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind);
72 }
73 
75  switch (Kind) {
76  default:
77  break;
78  case RecurKind::Add:
79  case RecurKind::Mul:
80  case RecurKind::FAdd:
81  case RecurKind::FMul:
82  return true;
83  }
84  return false;
85 }
86 
87 /// Determines if Phi may have been type-promoted. If Phi has a single user
88 /// that ANDs the Phi with a type mask, return the user. RT is updated to
89 /// account for the narrower bit width represented by the mask, and the AND
90 /// instruction is added to CI.
94  if (!Phi->hasOneUse())
95  return Phi;
96 
97  const APInt *M = nullptr;
98  Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
99 
100  // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
101  // with a new integer type of the corresponding bit width.
102  if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
103  int32_t Bits = (*M + 1).exactLogBase2();
104  if (Bits > 0) {
105  RT = IntegerType::get(Phi->getContext(), Bits);
106  Visited.insert(Phi);
107  CI.insert(J);
108  return J;
109  }
110  }
111  return Phi;
112 }
113 
114 /// Compute the minimal bit width needed to represent a reduction whose exit
115 /// instruction is given by Exit.
116 static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
117  DemandedBits *DB,
118  AssumptionCache *AC,
119  DominatorTree *DT) {
120  bool IsSigned = false;
121  const DataLayout &DL = Exit->getModule()->getDataLayout();
122  uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
123 
124  if (DB) {
125  // Use the demanded bits analysis to determine the bits that are live out
126  // of the exit instruction, rounding up to the nearest power of two. If the
127  // use of demanded bits results in a smaller bit width, we know the value
128  // must be positive (i.e., IsSigned = false), because if this were not the
129  // case, the sign bit would have been demanded.
130  auto Mask = DB->getDemandedBits(Exit);
131  MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
132  }
133 
134  if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
135  // If demanded bits wasn't able to limit the bit width, we can try to use
136  // value tracking instead. This can be the case, for example, if the value
137  // may be negative.
138  auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
139  auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
140  MaxBitWidth = NumTypeBits - NumSignBits;
142  if (!Bits.isNonNegative()) {
143  // If the value is not known to be non-negative, we set IsSigned to true,
144  // meaning that we will use sext instructions instead of zext
145  // instructions to restore the original type.
146  IsSigned = true;
147  if (!Bits.isNegative())
148  // If the value is not known to be negative, we don't known what the
149  // upper bit is, and therefore, we don't know what kind of extend we
150  // will need. In this case, just increase the bit width by one bit and
151  // use sext.
152  ++MaxBitWidth;
153  }
154  }
155  if (!isPowerOf2_64(MaxBitWidth))
156  MaxBitWidth = NextPowerOf2(MaxBitWidth);
157 
158  return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
159  IsSigned);
160 }
161 
162 /// Collect cast instructions that can be ignored in the vectorizer's cost
163 /// model, given a reduction exit value and the minimal type in which the
164 /// reduction can be represented.
165 static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
166  Type *RecurrenceType,
168 
171  Worklist.push_back(Exit);
172 
173  while (!Worklist.empty()) {
174  Instruction *Val = Worklist.pop_back_val();
175  Visited.insert(Val);
176  if (auto *Cast = dyn_cast<CastInst>(Val))
177  if (Cast->getSrcTy() == RecurrenceType) {
178  // If the source type of a cast instruction is equal to the recurrence
179  // type, it will be eliminated, and should be ignored in the vectorizer
180  // cost model.
181  Casts.insert(Cast);
182  continue;
183  }
184 
185  // Add all operands to the work list if they are loop-varying values that
186  // we haven't yet visited.
187  for (Value *O : cast<User>(Val)->operands())
188  if (auto *I = dyn_cast<Instruction>(O))
189  if (TheLoop->contains(I) && !Visited.count(I))
190  Worklist.push_back(I);
191  }
192 }
193 
194 // Check if a given Phi node can be recognized as an ordered reduction for
195 // vectorizing floating point operations without unsafe math.
196 static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst,
197  Instruction *Exit, PHINode *Phi) {
198  // Currently only FAdd is supported
199  if (Kind != RecurKind::FAdd)
200  return false;
201 
202  if (Exit->getOpcode() != Instruction::FAdd || Exit != ExactFPMathInst)
203  return false;
204 
205  // The only pattern accepted is the one in which the reduction PHI
206  // is used as one of the operands of the exit instruction
207  auto *LHS = Exit->getOperand(0);
208  auto *RHS = Exit->getOperand(1);
209  if (LHS != Phi && RHS != Phi)
210  return false;
211 
212  LLVM_DEBUG(dbgs() << "LV: Found an ordered reduction: Phi: " << *Phi
213  << ", ExitInst: " << *Exit << "\n");
214 
215  return true;
216 }
217 
219  Loop *TheLoop, FastMathFlags FuncFMF,
220  RecurrenceDescriptor &RedDes,
221  DemandedBits *DB,
222  AssumptionCache *AC,
223  DominatorTree *DT) {
224  if (Phi->getNumIncomingValues() != 2)
225  return false;
226 
227  // Reduction variables are only found in the loop header block.
228  if (Phi->getParent() != TheLoop->getHeader())
229  return false;
230 
231  // Obtain the reduction start value from the value that comes from the loop
232  // preheader.
233  Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
234 
235  // ExitInstruction is the single value which is used outside the loop.
236  // We only allow for a single reduction value to be used outside the loop.
237  // This includes users of the reduction, variables (which form a cycle
238  // which ends in the phi node).
239  Instruction *ExitInstruction = nullptr;
240  // Indicates that we found a reduction operation in our scan.
241  bool FoundReduxOp = false;
242 
243  // We start with the PHI node and scan for all of the users of this
244  // instruction. All users must be instructions that can be used as reduction
245  // variables (such as ADD). We must have a single out-of-block user. The cycle
246  // must include the original PHI.
247  bool FoundStartPHI = false;
248 
249  // To recognize min/max patterns formed by a icmp select sequence, we store
250  // the number of instruction we saw from the recognized min/max pattern,
251  // to make sure we only see exactly the two instructions.
252  unsigned NumCmpSelectPatternInst = 0;
253  InstDesc ReduxDesc(false, nullptr);
254 
255  // Data used for determining if the recurrence has been type-promoted.
256  Type *RecurrenceType = Phi->getType();
258  Instruction *Start = Phi;
259  bool IsSigned = false;
260 
261  SmallPtrSet<Instruction *, 8> VisitedInsts;
263 
264  // Return early if the recurrence kind does not match the type of Phi. If the
265  // recurrence kind is arithmetic, we attempt to look through AND operations
266  // resulting from the type promotion performed by InstCombine. Vector
267  // operations are not limited to the legal integer widths, so we may be able
268  // to evaluate the reduction in the narrower width.
269  if (RecurrenceType->isFloatingPointTy()) {
270  if (!isFloatingPointRecurrenceKind(Kind))
271  return false;
272  } else if (RecurrenceType->isIntegerTy()) {
273  if (!isIntegerRecurrenceKind(Kind))
274  return false;
275  if (!isMinMaxRecurrenceKind(Kind))
276  Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
277  } else {
278  // Pointer min/max may exist, but it is not supported as a reduction op.
279  return false;
280  }
281 
282  Worklist.push_back(Start);
283  VisitedInsts.insert(Start);
284 
285  // Start with all flags set because we will intersect this with the reduction
286  // flags from all the reduction operations.
288 
289  // A value in the reduction can be used:
290  // - By the reduction:
291  // - Reduction operation:
292  // - One use of reduction value (safe).
293  // - Multiple use of reduction value (not safe).
294  // - PHI:
295  // - All uses of the PHI must be the reduction (safe).
296  // - Otherwise, not safe.
297  // - By instructions outside of the loop (safe).
298  // * One value may have several outside users, but all outside
299  // uses must be of the same value.
300  // - By an instruction that is not part of the reduction (not safe).
301  // This is either:
302  // * An instruction type other than PHI or the reduction operation.
303  // * A PHI in the header other than the initial PHI.
304  while (!Worklist.empty()) {
305  Instruction *Cur = Worklist.pop_back_val();
306 
307  // No Users.
308  // If the instruction has no users then this is a broken chain and can't be
309  // a reduction variable.
310  if (Cur->use_empty())
311  return false;
312 
313  bool IsAPhi = isa<PHINode>(Cur);
314 
315  // A header PHI use other than the original PHI.
316  if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
317  return false;
318 
319  // Reductions of instructions such as Div, and Sub is only possible if the
320  // LHS is the reduction variable.
321  if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
322  !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
323  !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
324  return false;
325 
326  // Any reduction instruction must be of one of the allowed kinds. We ignore
327  // the starting value (the Phi or an AND instruction if the Phi has been
328  // type-promoted).
329  if (Cur != Start) {
330  ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, FuncFMF);
331  if (!ReduxDesc.isRecurrence())
332  return false;
333  // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
334  if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi) {
335  FastMathFlags CurFMF = ReduxDesc.getPatternInst()->getFastMathFlags();
336  if (auto *Sel = dyn_cast<SelectInst>(ReduxDesc.getPatternInst())) {
337  // Accept FMF on either fcmp or select of a min/max idiom.
338  // TODO: This is a hack to work-around the fact that FMF may not be
339  // assigned/propagated correctly. If that problem is fixed or we
340  // standardize on fmin/fmax via intrinsics, this can be removed.
341  if (auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))
342  CurFMF |= FCmp->getFastMathFlags();
343  }
344  FMF &= CurFMF;
345  }
346  // Update this reduction kind if we matched a new instruction.
347  // TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind'
348  // state accurate while processing the worklist?
349  if (ReduxDesc.getRecKind() != RecurKind::None)
350  Kind = ReduxDesc.getRecKind();
351  }
352 
353  bool IsASelect = isa<SelectInst>(Cur);
354 
355  // A conditional reduction operation must only have 2 or less uses in
356  // VisitedInsts.
357  if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) &&
358  hasMultipleUsesOf(Cur, VisitedInsts, 2))
359  return false;
360 
361  // A reduction operation must only have one use of the reduction value.
362  if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) &&
363  hasMultipleUsesOf(Cur, VisitedInsts, 1))
364  return false;
365 
366  // All inputs to a PHI node must be a reduction value.
367  if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
368  return false;
369 
370  if (isIntMinMaxRecurrenceKind(Kind) &&
371  (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
372  ++NumCmpSelectPatternInst;
373  if (isFPMinMaxRecurrenceKind(Kind) &&
374  (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
375  ++NumCmpSelectPatternInst;
376 
377  // Check whether we found a reduction operator.
378  FoundReduxOp |= !IsAPhi && Cur != Start;
379 
380  // Process users of current instruction. Push non-PHI nodes after PHI nodes
381  // onto the stack. This way we are going to have seen all inputs to PHI
382  // nodes once we get to them.
385  for (User *U : Cur->users()) {
386  Instruction *UI = cast<Instruction>(U);
387 
388  // Check if we found the exit user.
389  BasicBlock *Parent = UI->getParent();
390  if (!TheLoop->contains(Parent)) {
391  // If we already know this instruction is used externally, move on to
392  // the next user.
393  if (ExitInstruction == Cur)
394  continue;
395 
396  // Exit if you find multiple values used outside or if the header phi
397  // node is being used. In this case the user uses the value of the
398  // previous iteration, in which case we would loose "VF-1" iterations of
399  // the reduction operation if we vectorize.
400  if (ExitInstruction != nullptr || Cur == Phi)
401  return false;
402 
403  // The instruction used by an outside user must be the last instruction
404  // before we feed back to the reduction phi. Otherwise, we loose VF-1
405  // operations on the value.
406  if (!is_contained(Phi->operands(), Cur))
407  return false;
408 
409  ExitInstruction = Cur;
410  continue;
411  }
412 
413  // Process instructions only once (termination). Each reduction cycle
414  // value must only be used once, except by phi nodes and min/max
415  // reductions which are represented as a cmp followed by a select.
416  InstDesc IgnoredVal(false, nullptr);
417  if (VisitedInsts.insert(UI).second) {
418  if (isa<PHINode>(UI))
419  PHIs.push_back(UI);
420  else
421  NonPHIs.push_back(UI);
422  } else if (!isa<PHINode>(UI) &&
423  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
424  !isa<SelectInst>(UI)) ||
425  (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
426  !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())))
427  return false;
428 
429  // Remember that we completed the cycle.
430  if (UI == Phi)
431  FoundStartPHI = true;
432  }
433  Worklist.append(PHIs.begin(), PHIs.end());
434  Worklist.append(NonPHIs.begin(), NonPHIs.end());
435  }
436 
437  // This means we have seen one but not the other instruction of the
438  // pattern or more than just a select and cmp.
439  if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2)
440  return false;
441 
442  if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
443  return false;
444 
445  const bool IsOrdered = checkOrderedReduction(
446  Kind, ReduxDesc.getExactFPMathInst(), ExitInstruction, Phi);
447 
448  if (Start != Phi) {
449  // If the starting value is not the same as the phi node, we speculatively
450  // looked through an 'and' instruction when evaluating a potential
451  // arithmetic reduction to determine if it may have been type-promoted.
452  //
453  // We now compute the minimal bit width that is required to represent the
454  // reduction. If this is the same width that was indicated by the 'and', we
455  // can represent the reduction in the smaller type. The 'and' instruction
456  // will be eliminated since it will essentially be a cast instruction that
457  // can be ignore in the cost model. If we compute a different type than we
458  // did when evaluating the 'and', the 'and' will not be eliminated, and we
459  // will end up with different kinds of operations in the recurrence
460  // expression (e.g., IntegerAND, IntegerADD). We give up if this is
461  // the case.
462  //
463  // The vectorizer relies on InstCombine to perform the actual
464  // type-shrinking. It does this by inserting instructions to truncate the
465  // exit value of the reduction to the width indicated by RecurrenceType and
466  // then extend this value back to the original width. If IsSigned is false,
467  // a 'zext' instruction will be generated; otherwise, a 'sext' will be
468  // used.
469  //
470  // TODO: We should not rely on InstCombine to rewrite the reduction in the
471  // smaller type. We should just generate a correctly typed expression
472  // to begin with.
473  Type *ComputedType;
474  std::tie(ComputedType, IsSigned) =
475  computeRecurrenceType(ExitInstruction, DB, AC, DT);
476  if (ComputedType != RecurrenceType)
477  return false;
478 
479  // The recurrence expression will be represented in a narrower type. If
480  // there are any cast instructions that will be unnecessary, collect them
481  // in CastInsts. Note that the 'and' instruction was already included in
482  // this list.
483  //
484  // TODO: A better way to represent this may be to tag in some way all the
485  // instructions that are a part of the reduction. The vectorizer cost
486  // model could then apply the recurrence type to these instructions,
487  // without needing a white list of instructions to ignore.
488  // This may also be useful for the inloop reductions, if it can be
489  // kept simple enough.
490  collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
491  }
492 
493  // We found a reduction var if we have reached the original phi node and we
494  // only have a single instruction with out-of-loop users.
495 
496  // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
497  // is saved as part of the RecurrenceDescriptor.
498 
499  // Save the description of this reduction variable.
500  RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind, FMF,
501  ReduxDesc.getExactFPMathInst(), RecurrenceType,
502  IsSigned, IsOrdered, CastInsts);
503  RedDes = RD;
504 
505  return true;
506 }
507 
510  const InstDesc &Prev) {
511  assert((isa<CmpInst>(I) || isa<SelectInst>(I)) &&
512  "Expected a cmp or select instruction");
513 
514  // We must handle the select(cmp()) as a single instruction. Advance to the
515  // select.
516  CmpInst::Predicate Pred;
517  if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
518  if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
519  return InstDesc(Select, Prev.getRecKind());
520  }
521 
522  // Only match select with single use cmp condition.
523  if (!match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
524  m_Value())))
525  return InstDesc(false, I);
526 
527  // Look for a min/max pattern.
528  if (match(I, m_UMin(m_Value(), m_Value())))
529  return InstDesc(I, RecurKind::UMin);
530  if (match(I, m_UMax(m_Value(), m_Value())))
531  return InstDesc(I, RecurKind::UMax);
532  if (match(I, m_SMax(m_Value(), m_Value())))
533  return InstDesc(I, RecurKind::SMax);
534  if (match(I, m_SMin(m_Value(), m_Value())))
535  return InstDesc(I, RecurKind::SMin);
536  if (match(I, m_OrdFMin(m_Value(), m_Value())))
537  return InstDesc(I, RecurKind::FMin);
538  if (match(I, m_OrdFMax(m_Value(), m_Value())))
539  return InstDesc(I, RecurKind::FMax);
540  if (match(I, m_UnordFMin(m_Value(), m_Value())))
541  return InstDesc(I, RecurKind::FMin);
542  if (match(I, m_UnordFMax(m_Value(), m_Value())))
543  return InstDesc(I, RecurKind::FMax);
544 
545  return InstDesc(false, I);
546 }
547 
548 /// Returns true if the select instruction has users in the compare-and-add
549 /// reduction pattern below. The select instruction argument is the last one
550 /// in the sequence.
551 ///
552 /// %sum.1 = phi ...
553 /// ...
554 /// %cmp = fcmp pred %0, %CFP
555 /// %add = fadd %0, %sum.1
556 /// %sum.2 = select %cmp, %add, %sum.1
559  SelectInst *SI = dyn_cast<SelectInst>(I);
560  if (!SI)
561  return InstDesc(false, I);
562 
563  CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
564  // Only handle single use cases for now.
565  if (!CI || !CI->hasOneUse())
566  return InstDesc(false, I);
567 
568  Value *TrueVal = SI->getTrueValue();
569  Value *FalseVal = SI->getFalseValue();
570  // Handle only when either of operands of select instruction is a PHI
571  // node for now.
572  if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
573  (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
574  return InstDesc(false, I);
575 
576  Instruction *I1 =
577  isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
578  : dyn_cast<Instruction>(TrueVal);
579  if (!I1 || !I1->isBinaryOp())
580  return InstDesc(false, I);
581 
582  Value *Op1, *Op2;
583  if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) ||
584  m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) &&
585  I1->isFast())
586  return InstDesc(Kind == RecurKind::FAdd, SI);
587 
588  if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
589  return InstDesc(Kind == RecurKind::FMul, SI);
590 
591  return InstDesc(false, I);
592 }
593 
596  InstDesc &Prev, FastMathFlags FMF) {
597  switch (I->getOpcode()) {
598  default:
599  return InstDesc(false, I);
600  case Instruction::PHI:
601  return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst());
602  case Instruction::Sub:
603  case Instruction::Add:
604  return InstDesc(Kind == RecurKind::Add, I);
605  case Instruction::Mul:
606  return InstDesc(Kind == RecurKind::Mul, I);
607  case Instruction::And:
608  return InstDesc(Kind == RecurKind::And, I);
609  case Instruction::Or:
610  return InstDesc(Kind == RecurKind::Or, I);
611  case Instruction::Xor:
612  return InstDesc(Kind == RecurKind::Xor, I);
613  case Instruction::FDiv:
614  case Instruction::FMul:
615  return InstDesc(Kind == RecurKind::FMul, I,
616  I->hasAllowReassoc() ? nullptr : I);
617  case Instruction::FSub:
618  case Instruction::FAdd:
619  return InstDesc(Kind == RecurKind::FAdd, I,
620  I->hasAllowReassoc() ? nullptr : I);
621  case Instruction::Select:
623  return isConditionalRdxPattern(Kind, I);
625  case Instruction::FCmp:
626  case Instruction::ICmp:
627  if (isIntMinMaxRecurrenceKind(Kind) ||
628  (FMF.noNaNs() && FMF.noSignedZeros() && isFPMinMaxRecurrenceKind(Kind)))
629  return isMinMaxSelectCmpPattern(I, Prev);
630  return InstDesc(false, I);
631  }
632 }
633 
636  unsigned MaxNumUses) {
637  unsigned NumUses = 0;
638  for (const Use &U : I->operands()) {
639  if (Insts.count(dyn_cast<Instruction>(U)))
640  ++NumUses;
641  if (NumUses > MaxNumUses)
642  return true;
643  }
644 
645  return false;
646 }
647 
649  RecurrenceDescriptor &RedDes,
650  DemandedBits *DB, AssumptionCache *AC,
651  DominatorTree *DT) {
652 
653  BasicBlock *Header = TheLoop->getHeader();
654  Function &F = *Header->getParent();
655  FastMathFlags FMF;
656  FMF.setNoNaNs(
657  F.getFnAttribute("no-nans-fp-math").getValueAsBool());
658  FMF.setNoSignedZeros(
659  F.getFnAttribute("no-signed-zeros-fp-math").getValueAsBool());
660 
661  if (AddReductionVar(Phi, RecurKind::Add, TheLoop, FMF, RedDes, DB, AC, DT)) {
662  LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
663  return true;
664  }
665  if (AddReductionVar(Phi, RecurKind::Mul, TheLoop, FMF, RedDes, DB, AC, DT)) {
666  LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
667  return true;
668  }
669  if (AddReductionVar(Phi, RecurKind::Or, TheLoop, FMF, RedDes, DB, AC, DT)) {
670  LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
671  return true;
672  }
673  if (AddReductionVar(Phi, RecurKind::And, TheLoop, FMF, RedDes, DB, AC, DT)) {
674  LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
675  return true;
676  }
677  if (AddReductionVar(Phi, RecurKind::Xor, TheLoop, FMF, RedDes, DB, AC, DT)) {
678  LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
679  return true;
680  }
681  if (AddReductionVar(Phi, RecurKind::SMax, TheLoop, FMF, RedDes, DB, AC, DT)) {
682  LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n");
683  return true;
684  }
685  if (AddReductionVar(Phi, RecurKind::SMin, TheLoop, FMF, RedDes, DB, AC, DT)) {
686  LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n");
687  return true;
688  }
689  if (AddReductionVar(Phi, RecurKind::UMax, TheLoop, FMF, RedDes, DB, AC, DT)) {
690  LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n");
691  return true;
692  }
693  if (AddReductionVar(Phi, RecurKind::UMin, TheLoop, FMF, RedDes, DB, AC, DT)) {
694  LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n");
695  return true;
696  }
697  if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, FMF, RedDes, DB, AC, DT)) {
698  LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
699  return true;
700  }
701  if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, FMF, RedDes, DB, AC, DT)) {
702  LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
703  return true;
704  }
705  if (AddReductionVar(Phi, RecurKind::FMax, TheLoop, FMF, RedDes, DB, AC, DT)) {
706  LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n");
707  return true;
708  }
709  if (AddReductionVar(Phi, RecurKind::FMin, TheLoop, FMF, RedDes, DB, AC, DT)) {
710  LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n");
711  return true;
712  }
713  // Not a reduction of known type.
714  return false;
715 }
716 
718  PHINode *Phi, Loop *TheLoop,
720 
721  // Ensure the phi node is in the loop header and has two incoming values.
722  if (Phi->getParent() != TheLoop->getHeader() ||
723  Phi->getNumIncomingValues() != 2)
724  return false;
725 
726  // Ensure the loop has a preheader and a single latch block. The loop
727  // vectorizer will need the latch to set up the next iteration of the loop.
728  auto *Preheader = TheLoop->getLoopPreheader();
729  auto *Latch = TheLoop->getLoopLatch();
730  if (!Preheader || !Latch)
731  return false;
732 
733  // Ensure the phi node's incoming blocks are the loop preheader and latch.
734  if (Phi->getBasicBlockIndex(Preheader) < 0 ||
735  Phi->getBasicBlockIndex(Latch) < 0)
736  return false;
737 
738  // Get the previous value. The previous value comes from the latch edge while
739  // the initial value comes form the preheader edge.
740  auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
741  if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
742  SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
743  return false;
744 
745  // Ensure every user of the phi node (recursively) is dominated by the
746  // previous value. The dominance requirement ensures the loop vectorizer will
747  // not need to vectorize the initial value prior to the first iteration of the
748  // loop.
749  // TODO: Consider extending this sinking to handle memory instructions.
750 
751  // We optimistically assume we can sink all users after Previous. Keep a set
752  // of instructions to sink after Previous ordered by dominance in the common
753  // basic block. It will be applied to SinkAfter if all users can be sunk.
754  auto CompareByComesBefore = [](const Instruction *A, const Instruction *B) {
755  return A->comesBefore(B);
756  };
757  std::set<Instruction *, decltype(CompareByComesBefore)> InstrsToSink(
758  CompareByComesBefore);
759 
760  BasicBlock *PhiBB = Phi->getParent();
762  auto TryToPushSinkCandidate = [&](Instruction *SinkCandidate) {
763  // Already sunk SinkCandidate.
764  if (SinkCandidate->getParent() == PhiBB &&
765  InstrsToSink.find(SinkCandidate) != InstrsToSink.end())
766  return true;
767 
768  // Cyclic dependence.
769  if (Previous == SinkCandidate)
770  return false;
771 
772  if (DT->dominates(Previous,
773  SinkCandidate)) // We already are good w/o sinking.
774  return true;
775 
776  if (SinkCandidate->getParent() != PhiBB ||
777  SinkCandidate->mayHaveSideEffects() ||
778  SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
779  return false;
780 
781  // Do not try to sink an instruction multiple times (if multiple operands
782  // are first order recurrences).
783  // TODO: We can support this case, by sinking the instruction after the
784  // 'deepest' previous instruction.
785  if (SinkAfter.find(SinkCandidate) != SinkAfter.end())
786  return false;
787 
788  // If we reach a PHI node that is not dominated by Previous, we reached a
789  // header PHI. No need for sinking.
790  if (isa<PHINode>(SinkCandidate))
791  return true;
792 
793  // Sink User tentatively and check its users
794  InstrsToSink.insert(SinkCandidate);
795  WorkList.push_back(SinkCandidate);
796  return true;
797  };
798 
799  WorkList.push_back(Phi);
800  // Try to recursively sink instructions and their users after Previous.
801  while (!WorkList.empty()) {
802  Instruction *Current = WorkList.pop_back_val();
803  for (User *User : Current->users()) {
804  if (!TryToPushSinkCandidate(cast<Instruction>(User)))
805  return false;
806  }
807  }
808 
809  // We can sink all users of Phi. Update the mapping.
810  for (Instruction *I : InstrsToSink) {
811  SinkAfter[I] = Previous;
812  Previous = I;
813  }
814  return true;
815 }
816 
817 /// This function returns the identity element (or neutral element) for
818 /// the operation K.
820  FastMathFlags FMF) {
821  switch (K) {
822  case RecurKind::Xor:
823  case RecurKind::Add:
824  case RecurKind::Or:
825  // Adding, Xoring, Oring zero to a number does not change it.
826  return ConstantInt::get(Tp, 0);
827  case RecurKind::Mul:
828  // Multiplying a number by 1 does not change it.
829  return ConstantInt::get(Tp, 1);
830  case RecurKind::And:
831  // AND-ing a number with an all-1 value does not change it.
832  return ConstantInt::get(Tp, -1, true);
833  case RecurKind::FMul:
834  // Multiplying a number by 1 does not change it.
835  return ConstantFP::get(Tp, 1.0L);
836  case RecurKind::FAdd:
837  // Adding zero to a number does not change it.
838  // FIXME: Ideally we should not need to check FMF for FAdd and should always
839  // use -0.0. However, this will currently result in mixed vectors of 0.0/-0.0.
840  // Instead, we should ensure that 1) the FMF from FAdd are propagated to the PHI
841  // nodes where possible, and 2) PHIs with the nsz flag + -0.0 use 0.0. This would
842  // mean we can then remove the check for noSignedZeros() below (see D98963).
843  if (FMF.noSignedZeros())
844  return ConstantFP::get(Tp, 0.0L);
845  return ConstantFP::get(Tp, -0.0L);
846  case RecurKind::UMin:
847  return ConstantInt::get(Tp, -1);
848  case RecurKind::UMax:
849  return ConstantInt::get(Tp, 0);
850  case RecurKind::SMin:
851  return ConstantInt::get(Tp,
853  case RecurKind::SMax:
854  return ConstantInt::get(Tp,
856  case RecurKind::FMin:
857  return ConstantFP::getInfinity(Tp, true);
858  case RecurKind::FMax:
859  return ConstantFP::getInfinity(Tp, false);
860  default:
861  llvm_unreachable("Unknown recurrence kind");
862  }
863 }
864 
866  switch (Kind) {
867  case RecurKind::Add:
868  return Instruction::Add;
869  case RecurKind::Mul:
870  return Instruction::Mul;
871  case RecurKind::Or:
872  return Instruction::Or;
873  case RecurKind::And:
874  return Instruction::And;
875  case RecurKind::Xor:
876  return Instruction::Xor;
877  case RecurKind::FMul:
878  return Instruction::FMul;
879  case RecurKind::FAdd:
880  return Instruction::FAdd;
881  case RecurKind::SMax:
882  case RecurKind::SMin:
883  case RecurKind::UMax:
884  case RecurKind::UMin:
885  return Instruction::ICmp;
886  case RecurKind::FMax:
887  case RecurKind::FMin:
888  return Instruction::FCmp;
889  default:
890  llvm_unreachable("Unknown recurrence operation");
891  }
892 }
893 
896  SmallVector<Instruction *, 4> ReductionOperations;
897  unsigned RedOp = getOpcode(Kind);
898 
899  // Search down from the Phi to the LoopExitInstr, looking for instructions
900  // with a single user of the correct type for the reduction.
901 
902  // Note that we check that the type of the operand is correct for each item in
903  // the chain, including the last (the loop exit value). This can come up from
904  // sub, which would otherwise be treated as an add reduction. MinMax also need
905  // to check for a pair of icmp/select, for which we use getNextInstruction and
906  // isCorrectOpcode functions to step the right number of instruction, and
907  // check the icmp/select pair.
908  // FIXME: We also do not attempt to look through Phi/Select's yet, which might
909  // be part of the reduction chain, or attempt to looks through And's to find a
910  // smaller bitwidth. Subs are also currently not allowed (which are usually
911  // treated as part of a add reduction) as they are expected to generally be
912  // more expensive than out-of-loop reductions, and need to be costed more
913  // carefully.
914  unsigned ExpectedUses = 1;
915  if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp)
916  ExpectedUses = 2;
917 
918  auto getNextInstruction = [&](Instruction *Cur) {
919  if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
920  // We are expecting a icmp/select pair, which we go to the next select
921  // instruction if we can. We already know that Cur has 2 uses.
922  if (isa<SelectInst>(*Cur->user_begin()))
923  return cast<Instruction>(*Cur->user_begin());
924  else
925  return cast<Instruction>(*std::next(Cur->user_begin()));
926  }
927  return cast<Instruction>(*Cur->user_begin());
928  };
929  auto isCorrectOpcode = [&](Instruction *Cur) {
930  if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
931  Value *LHS, *RHS;
933  matchSelectPattern(Cur, LHS, RHS).Flavor);
934  }
935  return Cur->getOpcode() == RedOp;
936  };
937 
938  // The loop exit instruction we check first (as a quick test) but add last. We
939  // check the opcode is correct (and dont allow them to be Subs) and that they
940  // have expected to have the expected number of uses. They will have one use
941  // from the phi and one from a LCSSA value, no matter the type.
942  if (!isCorrectOpcode(LoopExitInstr) || !LoopExitInstr->hasNUses(2))
943  return {};
944 
945  // Check that the Phi has one (or two for min/max) uses.
946  if (!Phi->hasNUses(ExpectedUses))
947  return {};
948  Instruction *Cur = getNextInstruction(Phi);
949 
950  // Each other instruction in the chain should have the expected number of uses
951  // and be the correct opcode.
952  while (Cur != LoopExitInstr) {
953  if (!isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses))
954  return {};
955 
956  ReductionOperations.push_back(Cur);
957  Cur = getNextInstruction(Cur);
958  }
959 
960  ReductionOperations.push_back(Cur);
961  return ReductionOperations;
962 }
963 
964 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
965  const SCEV *Step, BinaryOperator *BOp,
967  : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
968  assert(IK != IK_NoInduction && "Not an induction");
969 
970  // Start value type should match the induction kind and the value
971  // itself should not be null.
972  assert(StartValue && "StartValue is null");
973  assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
974  "StartValue is not a pointer for pointer induction");
975  assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
976  "StartValue is not an integer for integer induction");
977 
978  // Check the Step Value. It should be non-zero integer value.
979  assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
980  "Step value is zero");
981 
982  assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
983  "Step value should be constant for pointer induction");
984  assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
985  "StepValue is not an integer");
986 
987  assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
988  "StepValue is not FP for FpInduction");
989  assert((IK != IK_FpInduction ||
990  (InductionBinOp &&
991  (InductionBinOp->getOpcode() == Instruction::FAdd ||
992  InductionBinOp->getOpcode() == Instruction::FSub))) &&
993  "Binary opcode should be specified for FP induction");
994 
995  if (Casts) {
996  for (auto &Inst : *Casts) {
997  RedundantCasts.push_back(Inst);
998  }
999  }
1000 }
1001 
1003  if (isa<SCEVConstant>(Step))
1004  return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
1005  return nullptr;
1006 }
1007 
1009  ScalarEvolution *SE,
1011 
1012  // Here we only handle FP induction variables.
1013  assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
1014 
1015  if (TheLoop->getHeader() != Phi->getParent())
1016  return false;
1017 
1018  // The loop may have multiple entrances or multiple exits; we can analyze
1019  // this phi if it has a unique entry value and a unique backedge value.
1020  if (Phi->getNumIncomingValues() != 2)
1021  return false;
1022  Value *BEValue = nullptr, *StartValue = nullptr;
1023  if (TheLoop->contains(Phi->getIncomingBlock(0))) {
1024  BEValue = Phi->getIncomingValue(0);
1025  StartValue = Phi->getIncomingValue(1);
1026  } else {
1027  assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
1028  "Unexpected Phi node in the loop");
1029  BEValue = Phi->getIncomingValue(1);
1030  StartValue = Phi->getIncomingValue(0);
1031  }
1032 
1033  BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
1034  if (!BOp)
1035  return false;
1036 
1037  Value *Addend = nullptr;
1038  if (BOp->getOpcode() == Instruction::FAdd) {
1039  if (BOp->getOperand(0) == Phi)
1040  Addend = BOp->getOperand(1);
1041  else if (BOp->getOperand(1) == Phi)
1042  Addend = BOp->getOperand(0);
1043  } else if (BOp->getOpcode() == Instruction::FSub)
1044  if (BOp->getOperand(0) == Phi)
1045  Addend = BOp->getOperand(1);
1046 
1047  if (!Addend)
1048  return false;
1049 
1050  // The addend should be loop invariant
1051  if (auto *I = dyn_cast<Instruction>(Addend))
1052  if (TheLoop->contains(I))
1053  return false;
1054 
1055  // FP Step has unknown SCEV
1056  const SCEV *Step = SE->getUnknown(Addend);
1057  D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
1058  return true;
1059 }
1060 
1061 /// This function is called when we suspect that the update-chain of a phi node
1062 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
1063 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
1064 /// predicate P under which the SCEV expression for the phi can be the
1065 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
1066 /// cast instructions that are involved in the update-chain of this induction.
1067 /// A caller that adds the required runtime predicate can be free to drop these
1068 /// cast instructions, and compute the phi using \p AR (instead of some scev
1069 /// expression with casts).
1070 ///
1071 /// For example, without a predicate the scev expression can take the following
1072 /// form:
1073 /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
1074 ///
1075 /// It corresponds to the following IR sequence:
1076 /// %for.body:
1077 /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
1078 /// %casted_phi = "ExtTrunc i64 %x"
1079 /// %add = add i64 %casted_phi, %step
1080 ///
1081 /// where %x is given in \p PN,
1082 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
1083 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
1084 /// several forms, for example, such as:
1085 /// ExtTrunc1: %casted_phi = and %x, 2^n-1
1086 /// or:
1087 /// ExtTrunc2: %t = shl %x, m
1088 /// %casted_phi = ashr %t, m
1089 ///
1090 /// If we are able to find such sequence, we return the instructions
1091 /// we found, namely %casted_phi and the instructions on its use-def chain up
1092 /// to the phi (not including the phi).
1094  const SCEVUnknown *PhiScev,
1095  const SCEVAddRecExpr *AR,
1096  SmallVectorImpl<Instruction *> &CastInsts) {
1097 
1098  assert(CastInsts.empty() && "CastInsts is expected to be empty.");
1099  auto *PN = cast<PHINode>(PhiScev->getValue());
1100  assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
1101  const Loop *L = AR->getLoop();
1102 
1103  // Find any cast instructions that participate in the def-use chain of
1104  // PhiScev in the loop.
1105  // FORNOW/TODO: We currently expect the def-use chain to include only
1106  // two-operand instructions, where one of the operands is an invariant.
1107  // createAddRecFromPHIWithCasts() currently does not support anything more
1108  // involved than that, so we keep the search simple. This can be
1109  // extended/generalized as needed.
1110 
1111  auto getDef = [&](const Value *Val) -> Value * {
1112  const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
1113  if (!BinOp)
1114  return nullptr;
1115  Value *Op0 = BinOp->getOperand(0);
1116  Value *Op1 = BinOp->getOperand(1);
1117  Value *Def = nullptr;
1118  if (L->isLoopInvariant(Op0))
1119  Def = Op1;
1120  else if (L->isLoopInvariant(Op1))
1121  Def = Op0;
1122  return Def;
1123  };
1124 
1125  // Look for the instruction that defines the induction via the
1126  // loop backedge.
1127  BasicBlock *Latch = L->getLoopLatch();
1128  if (!Latch)
1129  return false;
1130  Value *Val = PN->getIncomingValueForBlock(Latch);
1131  if (!Val)
1132  return false;
1133 
1134  // Follow the def-use chain until the induction phi is reached.
1135  // If on the way we encounter a Value that has the same SCEV Expr as the
1136  // phi node, we can consider the instructions we visit from that point
1137  // as part of the cast-sequence that can be ignored.
1138  bool InCastSequence = false;
1139  auto *Inst = dyn_cast<Instruction>(Val);
1140  while (Val != PN) {
1141  // If we encountered a phi node other than PN, or if we left the loop,
1142  // we bail out.
1143  if (!Inst || !L->contains(Inst)) {
1144  return false;
1145  }
1146  auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
1147  if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
1148  InCastSequence = true;
1149  if (InCastSequence) {
1150  // Only the last instruction in the cast sequence is expected to have
1151  // uses outside the induction def-use chain.
1152  if (!CastInsts.empty())
1153  if (!Inst->hasOneUse())
1154  return false;
1155  CastInsts.push_back(Inst);
1156  }
1157  Val = getDef(Val);
1158  if (!Val)
1159  return false;
1160  Inst = dyn_cast<Instruction>(Val);
1161  }
1162 
1163  return InCastSequence;
1164 }
1165 
1168  InductionDescriptor &D, bool Assume) {
1169  Type *PhiTy = Phi->getType();
1170 
1171  // Handle integer and pointer inductions variables.
1172  // Now we handle also FP induction but not trying to make a
1173  // recurrent expression from the PHI node in-place.
1174 
1175  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
1176  !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
1177  return false;
1178 
1179  if (PhiTy->isFloatingPointTy())
1180  return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
1181 
1182  const SCEV *PhiScev = PSE.getSCEV(Phi);
1183  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1184 
1185  // We need this expression to be an AddRecExpr.
1186  if (Assume && !AR)
1187  AR = PSE.getAsAddRec(Phi);
1188 
1189  if (!AR) {
1190  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1191  return false;
1192  }
1193 
1194  // Record any Cast instructions that participate in the induction update
1195  const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1196  // If we started from an UnknownSCEV, and managed to build an addRecurrence
1197  // only after enabling Assume with PSCEV, this means we may have encountered
1198  // cast instructions that required adding a runtime check in order to
1199  // guarantee the correctness of the AddRecurrence respresentation of the
1200  // induction.
1201  if (PhiScev != AR && SymbolicPhi) {
1203  if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1204  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1205  }
1206 
1207  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1208 }
1209 
1211  PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1212  InductionDescriptor &D, const SCEV *Expr,
1213  SmallVectorImpl<Instruction *> *CastsToIgnore) {
1214  Type *PhiTy = Phi->getType();
1215  // We only handle integer and pointer inductions variables.
1216  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1217  return false;
1218 
1219  // Check that the PHI is consecutive.
1220  const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1221  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1222 
1223  if (!AR) {
1224  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1225  return false;
1226  }
1227 
1228  if (AR->getLoop() != TheLoop) {
1229  // FIXME: We should treat this as a uniform. Unfortunately, we
1230  // don't currently know how to handled uniform PHIs.
1231  LLVM_DEBUG(
1232  dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1233  return false;
1234  }
1235 
1236  Value *StartValue =
1238 
1239  BasicBlock *Latch = AR->getLoop()->getLoopLatch();
1240  if (!Latch)
1241  return false;
1242  BinaryOperator *BOp =
1243  dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
1244 
1245  const SCEV *Step = AR->getStepRecurrence(*SE);
1246  // Calculate the pointer stride and check if it is consecutive.
1247  // The stride may be a constant or a loop invariant integer value.
1248  const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1249  if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1250  return false;
1251 
1252  if (PhiTy->isIntegerTy()) {
1253  D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1254  CastsToIgnore);
1255  return true;
1256  }
1257 
1258  assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1259  // Pointer induction should be a constant.
1260  if (!ConstStep)
1261  return false;
1262 
1263  ConstantInt *CV = ConstStep->getValue();
1264  Type *PointerElementType = PhiTy->getPointerElementType();
1265  // The pointer stride cannot be determined if the pointer element type is not
1266  // sized.
1267  if (!PointerElementType->isSized())
1268  return false;
1269 
1270  const DataLayout &DL = Phi->getModule()->getDataLayout();
1271  int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1272  if (!Size)
1273  return false;
1274 
1275  int64_t CVSize = CV->getSExtValue();
1276  if (CVSize % Size)
1277  return false;
1278  auto *StepValue =
1279  SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1280  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp);
1281  return true;
1282 }
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:274
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:64
llvm
---------------------— PointerInfo ------------------------------------—
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:112
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:435
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:648
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:228
llvm::FastMathFlags::setNoSignedZeros
void setNoSignedZeros(bool B=true)
Definition: Operator.h:226
llvm::Function
Definition: Function.h:61
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:2175
llvm::SmallVector< Instruction *, 8 >
llvm::RecurrenceDescriptor::InstDesc::getPatternInst
Instruction * getPatternInst() const
Definition: IVDescriptors.h:100
llvm::RecurrenceDescriptor::AddReductionVar
static bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FMF, 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:218
DomTreeUpdater.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
ValueTracking.h
llvm::ConstantFP::getInfinity
static Constant * getInfinity(Type *Ty, bool Negative=false)
Definition: Constants.cpp:1054
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:540
ScalarEvolution.h
llvm::InductionDescriptor::IK_IntInduction
@ IK_IntInduction
Integer induction variable. Step = C.
Definition: IVDescriptors.h:273
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:1008
llvm::FastMathFlags::noSignedZeros
bool noSignedZeros() const
Definition: Operator.h:209
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:385
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:61
llvm::ScalarEvolution::getUnknown
const SCEV * getUnknown(Value *V)
Definition: ScalarEvolution.cpp:3884
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:6164
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:165
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:13769
MustExecute.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
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:196
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:268
llvm::RecurKind::And
@ And
Bitwise or logical AND of integers.
llvm::RecurrenceDescriptor::isMinMaxSelectCmpPattern
static InstDesc isMinMaxSelectCmpPattern(Instruction *I, const InstDesc &Prev)
Returns a struct describing if the instruction is a Select(ICmp(X, Y), X, Y) instruction pattern corr...
Definition: IVDescriptors.cpp:509
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:895
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:2723
llvm::InductionDescriptor::IK_PtrInduction
@ IK_PtrInduction
Pointer induction var. Step = C / sizeof(elem).
Definition: IVDescriptors.h:274
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:96
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:689
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:634
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:183
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::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2812
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:899
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
PatternMatch.h
IVDescriptors.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2719
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:96
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
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:4048
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:201
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:5236
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:179
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
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:2805
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::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:1612
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:213
llvm::InductionDescriptor::getConstIntStepValue
ConstantInt * getConstIntStepValue() const
Definition: IVDescriptors.cpp:1002
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:13688
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:275
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1740
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:361
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:91
llvm::RecurrenceDescriptor::isArithmeticRecurrenceKind
static bool isArithmeticRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an arithmetic kind.
Definition: IVDescriptors.cpp:74
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:70
llvm::RecurKind::UMax
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
llvm::RecurrenceDescriptor::getRecurrenceIdentity
static Constant * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF)
Returns identity corresponding to the RecurrenceKind.
Definition: IVDescriptors.cpp:819
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:446
LoopPass.h
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::RecurrenceDescriptor::InstDesc::isRecurrence
bool isRecurrence() const
Definition: IVDescriptors.h:92
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:979
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:558
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:273
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:1093
ValueHandle.h
llvm::RecurrenceDescriptor::InstDesc
This POD struct holds information about a potential recurrence operation.
Definition: IVDescriptors.h:82
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:13027
llvm::MapVector::end
iterator end()
Definition: MapVector.h:71
DemandedBits.h
llvm::RecurrenceDescriptor::InstDesc::getRecKind
RecurKind getRecKind() const
Definition: IVDescriptors.h:98
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:70
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:1210
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:207
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::RecurrenceDescriptor::isRecurrenceInstr
static InstDesc isRecurrenceInstr(Instruction *I, RecurKind Kind, InstDesc &Prev, FastMathFlags FMF)
Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind'.
Definition: IVDescriptors.cpp:595
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:946
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:717
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:550
ScalarEvolutionExpressions.h
llvm::RecurrenceDescriptor
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:67
llvm::RecurKind::FAdd
@ FAdd
Sum of floats.
Instructions.h
Dominators.h
llvm::Type::getPointerElementType
Type * getPointerElementType() const
Definition: Type.h:380
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:2743
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2627
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:379
llvm::IntegerType::get
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:275
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:2207
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::PatternMatch::m_Cmp
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:89
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:116
llvm::RecurKind::SMax
@ SMax
Signed integer max implemented in terms of select(cmp()).
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:422
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