LLVM  9.0.0svn
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"
29 #include "llvm/IR/Dominators.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/IR/PatternMatch.h"
33 #include "llvm/IR/ValueHandle.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/KnownBits.h"
37 
38 using namespace llvm;
39 using namespace llvm::PatternMatch;
40 
41 #define DEBUG_TYPE "iv-descriptors"
42 
45  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
46  if (!Set.count(dyn_cast<Instruction>(*Use)))
47  return false;
48  return true;
49 }
50 
52  switch (Kind) {
53  default:
54  break;
55  case RK_IntegerAdd:
56  case RK_IntegerMult:
57  case RK_IntegerOr:
58  case RK_IntegerAnd:
59  case RK_IntegerXor:
60  case RK_IntegerMinMax:
61  return true;
62  }
63  return false;
64 }
65 
67  return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
68 }
69 
71  switch (Kind) {
72  default:
73  break;
74  case RK_IntegerAdd:
75  case RK_IntegerMult:
76  case RK_FloatAdd:
77  case RK_FloatMult:
78  return true;
79  }
80  return false;
81 }
82 
83 /// Determines if Phi may have been type-promoted. If Phi has a single user
84 /// that ANDs the Phi with a type mask, return the user. RT is updated to
85 /// account for the narrower bit width represented by the mask, and the AND
86 /// instruction is added to CI.
90  if (!Phi->hasOneUse())
91  return Phi;
92 
93  const APInt *M = nullptr;
94  Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
95 
96  // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
97  // with a new integer type of the corresponding bit width.
98  if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
99  int32_t Bits = (*M + 1).exactLogBase2();
100  if (Bits > 0) {
101  RT = IntegerType::get(Phi->getContext(), Bits);
102  Visited.insert(Phi);
103  CI.insert(J);
104  return J;
105  }
106  }
107  return Phi;
108 }
109 
110 /// Compute the minimal bit width needed to represent a reduction whose exit
111 /// instruction is given by Exit.
112 static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
113  DemandedBits *DB,
114  AssumptionCache *AC,
115  DominatorTree *DT) {
116  bool IsSigned = false;
117  const DataLayout &DL = Exit->getModule()->getDataLayout();
118  uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
119 
120  if (DB) {
121  // Use the demanded bits analysis to determine the bits that are live out
122  // of the exit instruction, rounding up to the nearest power of two. If the
123  // use of demanded bits results in a smaller bit width, we know the value
124  // must be positive (i.e., IsSigned = false), because if this were not the
125  // case, the sign bit would have been demanded.
126  auto Mask = DB->getDemandedBits(Exit);
127  MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
128  }
129 
130  if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
131  // If demanded bits wasn't able to limit the bit width, we can try to use
132  // value tracking instead. This can be the case, for example, if the value
133  // may be negative.
134  auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
135  auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
136  MaxBitWidth = NumTypeBits - NumSignBits;
137  KnownBits Bits = computeKnownBits(Exit, DL);
138  if (!Bits.isNonNegative()) {
139  // If the value is not known to be non-negative, we set IsSigned to true,
140  // meaning that we will use sext instructions instead of zext
141  // instructions to restore the original type.
142  IsSigned = true;
143  if (!Bits.isNegative())
144  // If the value is not known to be negative, we don't known what the
145  // upper bit is, and therefore, we don't know what kind of extend we
146  // will need. In this case, just increase the bit width by one bit and
147  // use sext.
148  ++MaxBitWidth;
149  }
150  }
151  if (!isPowerOf2_64(MaxBitWidth))
152  MaxBitWidth = NextPowerOf2(MaxBitWidth);
153 
154  return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
155  IsSigned);
156 }
157 
158 /// Collect cast instructions that can be ignored in the vectorizer's cost
159 /// model, given a reduction exit value and the minimal type in which the
160 /// reduction can be represented.
161 static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
162  Type *RecurrenceType,
164 
167  Worklist.push_back(Exit);
168 
169  while (!Worklist.empty()) {
170  Instruction *Val = Worklist.pop_back_val();
171  Visited.insert(Val);
172  if (auto *Cast = dyn_cast<CastInst>(Val))
173  if (Cast->getSrcTy() == RecurrenceType) {
174  // If the source type of a cast instruction is equal to the recurrence
175  // type, it will be eliminated, and should be ignored in the vectorizer
176  // cost model.
177  Casts.insert(Cast);
178  continue;
179  }
180 
181  // Add all operands to the work list if they are loop-varying values that
182  // we haven't yet visited.
183  for (Value *O : cast<User>(Val)->operands())
184  if (auto *I = dyn_cast<Instruction>(O))
185  if (TheLoop->contains(I) && !Visited.count(I))
186  Worklist.push_back(I);
187  }
188 }
189 
191  Loop *TheLoop, bool HasFunNoNaNAttr,
192  RecurrenceDescriptor &RedDes,
193  DemandedBits *DB,
194  AssumptionCache *AC,
195  DominatorTree *DT) {
196  if (Phi->getNumIncomingValues() != 2)
197  return false;
198 
199  // Reduction variables are only found in the loop header block.
200  if (Phi->getParent() != TheLoop->getHeader())
201  return false;
202 
203  // Obtain the reduction start value from the value that comes from the loop
204  // preheader.
205  Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
206 
207  // ExitInstruction is the single value which is used outside the loop.
208  // We only allow for a single reduction value to be used outside the loop.
209  // This includes users of the reduction, variables (which form a cycle
210  // which ends in the phi node).
211  Instruction *ExitInstruction = nullptr;
212  // Indicates that we found a reduction operation in our scan.
213  bool FoundReduxOp = false;
214 
215  // We start with the PHI node and scan for all of the users of this
216  // instruction. All users must be instructions that can be used as reduction
217  // variables (such as ADD). We must have a single out-of-block user. The cycle
218  // must include the original PHI.
219  bool FoundStartPHI = false;
220 
221  // To recognize min/max patterns formed by a icmp select sequence, we store
222  // the number of instruction we saw from the recognized min/max pattern,
223  // to make sure we only see exactly the two instructions.
224  unsigned NumCmpSelectPatternInst = 0;
225  InstDesc ReduxDesc(false, nullptr);
226 
227  // Data used for determining if the recurrence has been type-promoted.
228  Type *RecurrenceType = Phi->getType();
230  Instruction *Start = Phi;
231  bool IsSigned = false;
232 
233  SmallPtrSet<Instruction *, 8> VisitedInsts;
235 
236  // Return early if the recurrence kind does not match the type of Phi. If the
237  // recurrence kind is arithmetic, we attempt to look through AND operations
238  // resulting from the type promotion performed by InstCombine. Vector
239  // operations are not limited to the legal integer widths, so we may be able
240  // to evaluate the reduction in the narrower width.
241  if (RecurrenceType->isFloatingPointTy()) {
242  if (!isFloatingPointRecurrenceKind(Kind))
243  return false;
244  } else {
245  if (!isIntegerRecurrenceKind(Kind))
246  return false;
247  if (isArithmeticRecurrenceKind(Kind))
248  Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
249  }
250 
251  Worklist.push_back(Start);
252  VisitedInsts.insert(Start);
253 
254  // Start with all flags set because we will intersect this with the reduction
255  // flags from all the reduction operations.
257 
258  // A value in the reduction can be used:
259  // - By the reduction:
260  // - Reduction operation:
261  // - One use of reduction value (safe).
262  // - Multiple use of reduction value (not safe).
263  // - PHI:
264  // - All uses of the PHI must be the reduction (safe).
265  // - Otherwise, not safe.
266  // - By instructions outside of the loop (safe).
267  // * One value may have several outside users, but all outside
268  // uses must be of the same value.
269  // - By an instruction that is not part of the reduction (not safe).
270  // This is either:
271  // * An instruction type other than PHI or the reduction operation.
272  // * A PHI in the header other than the initial PHI.
273  while (!Worklist.empty()) {
274  Instruction *Cur = Worklist.back();
275  Worklist.pop_back();
276 
277  // No Users.
278  // If the instruction has no users then this is a broken chain and can't be
279  // a reduction variable.
280  if (Cur->use_empty())
281  return false;
282 
283  bool IsAPhi = isa<PHINode>(Cur);
284 
285  // A header PHI use other than the original PHI.
286  if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
287  return false;
288 
289  // Reductions of instructions such as Div, and Sub is only possible if the
290  // LHS is the reduction variable.
291  if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
292  !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
293  !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
294  return false;
295 
296  // Any reduction instruction must be of one of the allowed kinds. We ignore
297  // the starting value (the Phi or an AND instruction if the Phi has been
298  // type-promoted).
299  if (Cur != Start) {
300  ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
301  if (!ReduxDesc.isRecurrence())
302  return false;
303  if (isa<FPMathOperator>(ReduxDesc.getPatternInst()))
304  FMF &= ReduxDesc.getPatternInst()->getFastMathFlags();
305  }
306 
307  bool IsASelect = isa<SelectInst>(Cur);
308 
309  // A conditional reduction operation must only have 2 or less uses in
310  // VisitedInsts.
311  if (IsASelect && (Kind == RK_FloatAdd || Kind == RK_FloatMult) &&
312  hasMultipleUsesOf(Cur, VisitedInsts, 2))
313  return false;
314 
315  // A reduction operation must only have one use of the reduction value.
316  if (!IsAPhi && !IsASelect && Kind != RK_IntegerMinMax &&
317  Kind != RK_FloatMinMax && hasMultipleUsesOf(Cur, VisitedInsts, 1))
318  return false;
319 
320  // All inputs to a PHI node must be a reduction value.
321  if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
322  return false;
323 
324  if (Kind == RK_IntegerMinMax &&
325  (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
326  ++NumCmpSelectPatternInst;
327  if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
328  ++NumCmpSelectPatternInst;
329 
330  // Check whether we found a reduction operator.
331  FoundReduxOp |= !IsAPhi && Cur != Start;
332 
333  // Process users of current instruction. Push non-PHI nodes after PHI nodes
334  // onto the stack. This way we are going to have seen all inputs to PHI
335  // nodes once we get to them.
338  for (User *U : Cur->users()) {
339  Instruction *UI = cast<Instruction>(U);
340 
341  // Check if we found the exit user.
342  BasicBlock *Parent = UI->getParent();
343  if (!TheLoop->contains(Parent)) {
344  // If we already know this instruction is used externally, move on to
345  // the next user.
346  if (ExitInstruction == Cur)
347  continue;
348 
349  // Exit if you find multiple values used outside or if the header phi
350  // node is being used. In this case the user uses the value of the
351  // previous iteration, in which case we would loose "VF-1" iterations of
352  // the reduction operation if we vectorize.
353  if (ExitInstruction != nullptr || Cur == Phi)
354  return false;
355 
356  // The instruction used by an outside user must be the last instruction
357  // before we feed back to the reduction phi. Otherwise, we loose VF-1
358  // operations on the value.
359  if (!is_contained(Phi->operands(), Cur))
360  return false;
361 
362  ExitInstruction = Cur;
363  continue;
364  }
365 
366  // Process instructions only once (termination). Each reduction cycle
367  // value must only be used once, except by phi nodes and min/max
368  // reductions which are represented as a cmp followed by a select.
369  InstDesc IgnoredVal(false, nullptr);
370  if (VisitedInsts.insert(UI).second) {
371  if (isa<PHINode>(UI))
372  PHIs.push_back(UI);
373  else
374  NonPHIs.push_back(UI);
375  } else if (!isa<PHINode>(UI) &&
376  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
377  !isa<SelectInst>(UI)) ||
378  (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
379  !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())))
380  return false;
381 
382  // Remember that we completed the cycle.
383  if (UI == Phi)
384  FoundStartPHI = true;
385  }
386  Worklist.append(PHIs.begin(), PHIs.end());
387  Worklist.append(NonPHIs.begin(), NonPHIs.end());
388  }
389 
390  // This means we have seen one but not the other instruction of the
391  // pattern or more than just a select and cmp.
392  if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
393  NumCmpSelectPatternInst != 2)
394  return false;
395 
396  if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
397  return false;
398 
399  if (Start != Phi) {
400  // If the starting value is not the same as the phi node, we speculatively
401  // looked through an 'and' instruction when evaluating a potential
402  // arithmetic reduction to determine if it may have been type-promoted.
403  //
404  // We now compute the minimal bit width that is required to represent the
405  // reduction. If this is the same width that was indicated by the 'and', we
406  // can represent the reduction in the smaller type. The 'and' instruction
407  // will be eliminated since it will essentially be a cast instruction that
408  // can be ignore in the cost model. If we compute a different type than we
409  // did when evaluating the 'and', the 'and' will not be eliminated, and we
410  // will end up with different kinds of operations in the recurrence
411  // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is
412  // the case.
413  //
414  // The vectorizer relies on InstCombine to perform the actual
415  // type-shrinking. It does this by inserting instructions to truncate the
416  // exit value of the reduction to the width indicated by RecurrenceType and
417  // then extend this value back to the original width. If IsSigned is false,
418  // a 'zext' instruction will be generated; otherwise, a 'sext' will be
419  // used.
420  //
421  // TODO: We should not rely on InstCombine to rewrite the reduction in the
422  // smaller type. We should just generate a correctly typed expression
423  // to begin with.
424  Type *ComputedType;
425  std::tie(ComputedType, IsSigned) =
426  computeRecurrenceType(ExitInstruction, DB, AC, DT);
427  if (ComputedType != RecurrenceType)
428  return false;
429 
430  // The recurrence expression will be represented in a narrower type. If
431  // there are any cast instructions that will be unnecessary, collect them
432  // in CastInsts. Note that the 'and' instruction was already included in
433  // this list.
434  //
435  // TODO: A better way to represent this may be to tag in some way all the
436  // instructions that are a part of the reduction. The vectorizer cost
437  // model could then apply the recurrence type to these instructions,
438  // without needing a white list of instructions to ignore.
439  collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
440  }
441 
442  // We found a reduction var if we have reached the original phi node and we
443  // only have a single instruction with out-of-loop users.
444 
445  // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
446  // is saved as part of the RecurrenceDescriptor.
447 
448  // Save the description of this reduction variable.
450  RdxStart, ExitInstruction, Kind, FMF, ReduxDesc.getMinMaxKind(),
451  ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
452  RedDes = RD;
453 
454  return true;
455 }
456 
457 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
458 /// pattern corresponding to a min(X, Y) or max(X, Y).
461 
462  assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
463  "Expect a select instruction");
464  Instruction *Cmp = nullptr;
465  SelectInst *Select = nullptr;
466 
467  // We must handle the select(cmp()) as a single instruction. Advance to the
468  // select.
469  if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
470  if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
471  return InstDesc(false, I);
472  return InstDesc(Select, Prev.getMinMaxKind());
473  }
474 
475  // Only handle single use cases for now.
476  if (!(Select = dyn_cast<SelectInst>(I)))
477  return InstDesc(false, I);
478  if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
479  !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
480  return InstDesc(false, I);
481  if (!Cmp->hasOneUse())
482  return InstDesc(false, I);
483 
484  Value *CmpLeft;
485  Value *CmpRight;
486 
487  // Look for a min/max pattern.
488  if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
489  return InstDesc(Select, MRK_UIntMin);
490  else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
491  return InstDesc(Select, MRK_UIntMax);
492  else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
493  return InstDesc(Select, MRK_SIntMax);
494  else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
495  return InstDesc(Select, MRK_SIntMin);
496  else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
497  return InstDesc(Select, MRK_FloatMin);
498  else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
499  return InstDesc(Select, MRK_FloatMax);
500  else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
501  return InstDesc(Select, MRK_FloatMin);
502  else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
503  return InstDesc(Select, MRK_FloatMax);
504 
505  return InstDesc(false, I);
506 }
507 
508 /// Returns true if the select instruction has users in the compare-and-add
509 /// reduction pattern below. The select instruction argument is the last one
510 /// in the sequence.
511 ///
512 /// %sum.1 = phi ...
513 /// ...
514 /// %cmp = fcmp pred %0, %CFP
515 /// %add = fadd %0, %sum.1
516 /// %sum.2 = select %cmp, %add, %sum.1
521  if (!SI)
522  return InstDesc(false, I);
523 
524  CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
525  // Only handle single use cases for now.
526  if (!CI || !CI->hasOneUse())
527  return InstDesc(false, I);
528 
529  Value *TrueVal = SI->getTrueValue();
530  Value *FalseVal = SI->getFalseValue();
531  // Handle only when either of operands of select instruction is a PHI
532  // node for now.
533  if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
534  (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
535  return InstDesc(false, I);
536 
537  Instruction *I1 =
538  isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
539  : dyn_cast<Instruction>(TrueVal);
540  if (!I1 || !I1->isBinaryOp())
541  return InstDesc(false, I);
542 
543  Value *Op1, *Op2;
544  if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) ||
545  m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) &&
546  I1->isFast())
547  return InstDesc(Kind == RK_FloatAdd, SI);
548 
549  if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
550  return InstDesc(Kind == RK_FloatMult, SI);
551 
552  return InstDesc(false, I);
553 }
554 
557  InstDesc &Prev, bool HasFunNoNaNAttr) {
558  Instruction *UAI = Prev.getUnsafeAlgebraInst();
559  if (!UAI && isa<FPMathOperator>(I) && !I->hasAllowReassoc())
560  UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
561 
562  switch (I->getOpcode()) {
563  default:
564  return InstDesc(false, I);
565  case Instruction::PHI:
566  return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
567  case Instruction::Sub:
568  case Instruction::Add:
569  return InstDesc(Kind == RK_IntegerAdd, I);
570  case Instruction::Mul:
571  return InstDesc(Kind == RK_IntegerMult, I);
572  case Instruction::And:
573  return InstDesc(Kind == RK_IntegerAnd, I);
574  case Instruction::Or:
575  return InstDesc(Kind == RK_IntegerOr, I);
576  case Instruction::Xor:
577  return InstDesc(Kind == RK_IntegerXor, I);
578  case Instruction::FMul:
579  return InstDesc(Kind == RK_FloatMult, I, UAI);
580  case Instruction::FSub:
581  case Instruction::FAdd:
582  return InstDesc(Kind == RK_FloatAdd, I, UAI);
583  case Instruction::Select:
584  if (Kind == RK_FloatAdd || Kind == RK_FloatMult)
585  return isConditionalRdxPattern(Kind, I);
587  case Instruction::FCmp:
588  case Instruction::ICmp:
589  if (Kind != RK_IntegerMinMax &&
590  (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
591  return InstDesc(false, I);
592  return isMinMaxSelectCmpPattern(I, Prev);
593  }
594 }
595 
598  unsigned MaxNumUses) {
599  unsigned NumUses = 0;
600  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
601  ++Use) {
602  if (Insts.count(dyn_cast<Instruction>(*Use)))
603  ++NumUses;
604  if (NumUses > MaxNumUses)
605  return true;
606  }
607 
608  return false;
609 }
611  RecurrenceDescriptor &RedDes,
612  DemandedBits *DB, AssumptionCache *AC,
613  DominatorTree *DT) {
614 
615  BasicBlock *Header = TheLoop->getHeader();
616  Function &F = *Header->getParent();
617  bool HasFunNoNaNAttr =
618  F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
619 
620  if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
621  AC, DT)) {
622  LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
623  return true;
624  }
625  if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
626  AC, DT)) {
627  LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
628  return true;
629  }
630  if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB,
631  AC, DT)) {
632  LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
633  return true;
634  }
635  if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
636  AC, DT)) {
637  LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
638  return true;
639  }
640  if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
641  AC, DT)) {
642  LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
643  return true;
644  }
645  if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes,
646  DB, AC, DT)) {
647  LLVM_DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
648  return true;
649  }
650  if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
651  AC, DT)) {
652  LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
653  return true;
654  }
655  if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
656  AC, DT)) {
657  LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
658  return true;
659  }
660  if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
661  AC, DT)) {
662  LLVM_DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi
663  << "\n");
664  return true;
665  }
666  // Not a reduction of known type.
667  return false;
668 }
669 
671  PHINode *Phi, Loop *TheLoop,
673 
674  // Ensure the phi node is in the loop header and has two incoming values.
675  if (Phi->getParent() != TheLoop->getHeader() ||
676  Phi->getNumIncomingValues() != 2)
677  return false;
678 
679  // Ensure the loop has a preheader and a single latch block. The loop
680  // vectorizer will need the latch to set up the next iteration of the loop.
681  auto *Preheader = TheLoop->getLoopPreheader();
682  auto *Latch = TheLoop->getLoopLatch();
683  if (!Preheader || !Latch)
684  return false;
685 
686  // Ensure the phi node's incoming blocks are the loop preheader and latch.
687  if (Phi->getBasicBlockIndex(Preheader) < 0 ||
688  Phi->getBasicBlockIndex(Latch) < 0)
689  return false;
690 
691  // Get the previous value. The previous value comes from the latch edge while
692  // the initial value comes form the preheader edge.
693  auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
694  if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
695  SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
696  return false;
697 
698  // Ensure every user of the phi node is dominated by the previous value.
699  // The dominance requirement ensures the loop vectorizer will not need to
700  // vectorize the initial value prior to the first iteration of the loop.
701  // TODO: Consider extending this sinking to handle other kinds of instructions
702  // and expressions, beyond sinking a single cast past Previous.
703  if (Phi->hasOneUse()) {
704  auto *I = Phi->user_back();
705  if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() &&
706  DT->dominates(Previous, I->user_back())) {
707  if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
708  SinkAfter[I] = Previous;
709  return true;
710  }
711  }
712 
713  for (User *U : Phi->users())
714  if (auto *I = dyn_cast<Instruction>(U)) {
715  if (!DT->dominates(Previous, I))
716  return false;
717  }
718 
719  return true;
720 }
721 
722 /// This function returns the identity element (or neutral element) for
723 /// the operation K.
725  Type *Tp) {
726  switch (K) {
727  case RK_IntegerXor:
728  case RK_IntegerAdd:
729  case RK_IntegerOr:
730  // Adding, Xoring, Oring zero to a number does not change it.
731  return ConstantInt::get(Tp, 0);
732  case RK_IntegerMult:
733  // Multiplying a number by 1 does not change it.
734  return ConstantInt::get(Tp, 1);
735  case RK_IntegerAnd:
736  // AND-ing a number with an all-1 value does not change it.
737  return ConstantInt::get(Tp, -1, true);
738  case RK_FloatMult:
739  // Multiplying a number by 1 does not change it.
740  return ConstantFP::get(Tp, 1.0L);
741  case RK_FloatAdd:
742  // Adding zero to a number does not change it.
743  return ConstantFP::get(Tp, 0.0L);
744  default:
745  llvm_unreachable("Unknown recurrence kind");
746  }
747 }
748 
749 /// This function translates the recurrence kind to an LLVM binary operator.
751  switch (Kind) {
752  case RK_IntegerAdd:
753  return Instruction::Add;
754  case RK_IntegerMult:
755  return Instruction::Mul;
756  case RK_IntegerOr:
757  return Instruction::Or;
758  case RK_IntegerAnd:
759  return Instruction::And;
760  case RK_IntegerXor:
761  return Instruction::Xor;
762  case RK_FloatMult:
763  return Instruction::FMul;
764  case RK_FloatAdd:
765  return Instruction::FAdd;
766  case RK_IntegerMinMax:
767  return Instruction::ICmp;
768  case RK_FloatMinMax:
769  return Instruction::FCmp;
770  default:
771  llvm_unreachable("Unknown recurrence operation");
772  }
773 }
774 
775 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
776  const SCEV *Step, BinaryOperator *BOp,
778  : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
779  assert(IK != IK_NoInduction && "Not an induction");
780 
781  // Start value type should match the induction kind and the value
782  // itself should not be null.
783  assert(StartValue && "StartValue is null");
784  assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
785  "StartValue is not a pointer for pointer induction");
786  assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
787  "StartValue is not an integer for integer induction");
788 
789  // Check the Step Value. It should be non-zero integer value.
790  assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
791  "Step value is zero");
792 
793  assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
794  "Step value should be constant for pointer induction");
795  assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
796  "StepValue is not an integer");
797 
798  assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
799  "StepValue is not FP for FpInduction");
800  assert((IK != IK_FpInduction ||
801  (InductionBinOp &&
802  (InductionBinOp->getOpcode() == Instruction::FAdd ||
803  InductionBinOp->getOpcode() == Instruction::FSub))) &&
804  "Binary opcode should be specified for FP induction");
805 
806  if (Casts) {
807  for (auto &Inst : *Casts) {
808  RedundantCasts.push_back(Inst);
809  }
810  }
811 }
812 
814  ConstantInt *ConstStep = getConstIntStepValue();
815  if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
816  return ConstStep->getSExtValue();
817  return 0;
818 }
819 
821  if (isa<SCEVConstant>(Step))
822  return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
823  return nullptr;
824 }
825 
827  ScalarEvolution *SE,
829 
830  // Here we only handle FP induction variables.
831  assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
832 
833  if (TheLoop->getHeader() != Phi->getParent())
834  return false;
835 
836  // The loop may have multiple entrances or multiple exits; we can analyze
837  // this phi if it has a unique entry value and a unique backedge value.
838  if (Phi->getNumIncomingValues() != 2)
839  return false;
840  Value *BEValue = nullptr, *StartValue = nullptr;
841  if (TheLoop->contains(Phi->getIncomingBlock(0))) {
842  BEValue = Phi->getIncomingValue(0);
843  StartValue = Phi->getIncomingValue(1);
844  } else {
845  assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
846  "Unexpected Phi node in the loop");
847  BEValue = Phi->getIncomingValue(1);
848  StartValue = Phi->getIncomingValue(0);
849  }
850 
851  BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
852  if (!BOp)
853  return false;
854 
855  Value *Addend = nullptr;
856  if (BOp->getOpcode() == Instruction::FAdd) {
857  if (BOp->getOperand(0) == Phi)
858  Addend = BOp->getOperand(1);
859  else if (BOp->getOperand(1) == Phi)
860  Addend = BOp->getOperand(0);
861  } else if (BOp->getOpcode() == Instruction::FSub)
862  if (BOp->getOperand(0) == Phi)
863  Addend = BOp->getOperand(1);
864 
865  if (!Addend)
866  return false;
867 
868  // The addend should be loop invariant
869  if (auto *I = dyn_cast<Instruction>(Addend))
870  if (TheLoop->contains(I))
871  return false;
872 
873  // FP Step has unknown SCEV
874  const SCEV *Step = SE->getUnknown(Addend);
875  D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
876  return true;
877 }
878 
879 /// This function is called when we suspect that the update-chain of a phi node
880 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
881 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
882 /// predicate P under which the SCEV expression for the phi can be the
883 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
884 /// cast instructions that are involved in the update-chain of this induction.
885 /// A caller that adds the required runtime predicate can be free to drop these
886 /// cast instructions, and compute the phi using \p AR (instead of some scev
887 /// expression with casts).
888 ///
889 /// For example, without a predicate the scev expression can take the following
890 /// form:
891 /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
892 ///
893 /// It corresponds to the following IR sequence:
894 /// %for.body:
895 /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
896 /// %casted_phi = "ExtTrunc i64 %x"
897 /// %add = add i64 %casted_phi, %step
898 ///
899 /// where %x is given in \p PN,
900 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
901 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
902 /// several forms, for example, such as:
903 /// ExtTrunc1: %casted_phi = and %x, 2^n-1
904 /// or:
905 /// ExtTrunc2: %t = shl %x, m
906 /// %casted_phi = ashr %t, m
907 ///
908 /// If we are able to find such sequence, we return the instructions
909 /// we found, namely %casted_phi and the instructions on its use-def chain up
910 /// to the phi (not including the phi).
912  const SCEVUnknown *PhiScev,
913  const SCEVAddRecExpr *AR,
914  SmallVectorImpl<Instruction *> &CastInsts) {
915 
916  assert(CastInsts.empty() && "CastInsts is expected to be empty.");
917  auto *PN = cast<PHINode>(PhiScev->getValue());
918  assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
919  const Loop *L = AR->getLoop();
920 
921  // Find any cast instructions that participate in the def-use chain of
922  // PhiScev in the loop.
923  // FORNOW/TODO: We currently expect the def-use chain to include only
924  // two-operand instructions, where one of the operands is an invariant.
925  // createAddRecFromPHIWithCasts() currently does not support anything more
926  // involved than that, so we keep the search simple. This can be
927  // extended/generalized as needed.
928 
929  auto getDef = [&](const Value *Val) -> Value * {
930  const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
931  if (!BinOp)
932  return nullptr;
933  Value *Op0 = BinOp->getOperand(0);
934  Value *Op1 = BinOp->getOperand(1);
935  Value *Def = nullptr;
936  if (L->isLoopInvariant(Op0))
937  Def = Op1;
938  else if (L->isLoopInvariant(Op1))
939  Def = Op0;
940  return Def;
941  };
942 
943  // Look for the instruction that defines the induction via the
944  // loop backedge.
945  BasicBlock *Latch = L->getLoopLatch();
946  if (!Latch)
947  return false;
948  Value *Val = PN->getIncomingValueForBlock(Latch);
949  if (!Val)
950  return false;
951 
952  // Follow the def-use chain until the induction phi is reached.
953  // If on the way we encounter a Value that has the same SCEV Expr as the
954  // phi node, we can consider the instructions we visit from that point
955  // as part of the cast-sequence that can be ignored.
956  bool InCastSequence = false;
957  auto *Inst = dyn_cast<Instruction>(Val);
958  while (Val != PN) {
959  // If we encountered a phi node other than PN, or if we left the loop,
960  // we bail out.
961  if (!Inst || !L->contains(Inst)) {
962  return false;
963  }
964  auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
965  if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
966  InCastSequence = true;
967  if (InCastSequence) {
968  // Only the last instruction in the cast sequence is expected to have
969  // uses outside the induction def-use chain.
970  if (!CastInsts.empty())
971  if (!Inst->hasOneUse())
972  return false;
973  CastInsts.push_back(Inst);
974  }
975  Val = getDef(Val);
976  if (!Val)
977  return false;
978  Inst = dyn_cast<Instruction>(Val);
979  }
980 
981  return InCastSequence;
982 }
983 
986  InductionDescriptor &D, bool Assume) {
987  Type *PhiTy = Phi->getType();
988 
989  // Handle integer and pointer inductions variables.
990  // Now we handle also FP induction but not trying to make a
991  // recurrent expression from the PHI node in-place.
992 
993  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
994  !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
995  return false;
996 
997  if (PhiTy->isFloatingPointTy())
998  return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
999 
1000  const SCEV *PhiScev = PSE.getSCEV(Phi);
1001  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1002 
1003  // We need this expression to be an AddRecExpr.
1004  if (Assume && !AR)
1005  AR = PSE.getAsAddRec(Phi);
1006 
1007  if (!AR) {
1008  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1009  return false;
1010  }
1011 
1012  // Record any Cast instructions that participate in the induction update
1013  const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1014  // If we started from an UnknownSCEV, and managed to build an addRecurrence
1015  // only after enabling Assume with PSCEV, this means we may have encountered
1016  // cast instructions that required adding a runtime check in order to
1017  // guarantee the correctness of the AddRecurrence respresentation of the
1018  // induction.
1019  if (PhiScev != AR && SymbolicPhi) {
1021  if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1022  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1023  }
1024 
1025  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1026 }
1027 
1029  PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1030  InductionDescriptor &D, const SCEV *Expr,
1031  SmallVectorImpl<Instruction *> *CastsToIgnore) {
1032  Type *PhiTy = Phi->getType();
1033  // We only handle integer and pointer inductions variables.
1034  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1035  return false;
1036 
1037  // Check that the PHI is consecutive.
1038  const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1039  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1040 
1041  if (!AR) {
1042  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1043  return false;
1044  }
1045 
1046  if (AR->getLoop() != TheLoop) {
1047  // FIXME: We should treat this as a uniform. Unfortunately, we
1048  // don't currently know how to handled uniform PHIs.
1049  LLVM_DEBUG(
1050  dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1051  return false;
1052  }
1053 
1054  Value *StartValue =
1056 
1057  BasicBlock *Latch = AR->getLoop()->getLoopLatch();
1058  if (!Latch)
1059  return false;
1060  BinaryOperator *BOp =
1062 
1063  const SCEV *Step = AR->getStepRecurrence(*SE);
1064  // Calculate the pointer stride and check if it is consecutive.
1065  // The stride may be a constant or a loop invariant integer value.
1066  const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1067  if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1068  return false;
1069 
1070  if (PhiTy->isIntegerTy()) {
1071  D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1072  CastsToIgnore);
1073  return true;
1074  }
1075 
1076  assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1077  // Pointer induction should be a constant.
1078  if (!ConstStep)
1079  return false;
1080 
1081  ConstantInt *CV = ConstStep->getValue();
1082  Type *PointerElementType = PhiTy->getPointerElementType();
1083  // The pointer stride cannot be determined if the pointer element type is not
1084  // sized.
1085  if (!PointerElementType->isSized())
1086  return false;
1087 
1088  const DataLayout &DL = Phi->getModule()->getDataLayout();
1089  int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1090  if (!Size)
1091  return false;
1092 
1093  int64_t CVSize = CV->getSExtValue();
1094  if (CVSize % Size)
1095  return false;
1096  auto *StepValue =
1097  SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1098  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp);
1099  return true;
1100 }
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
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...
static bool isArithmeticRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is an arithmetic kind.
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:171
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:224
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.
InductionDescriptor()=default
Default constructor - creates an invalid induction.
const SCEV * getConstant(ConstantInt *V)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:402
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:647
This is the interface for a simple mod/ref and alias analysis over globals.
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.
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:264
int getConsecutiveDirection() const
Get the consecutive direction.
ConstantInt * getConstIntStepValue() const
static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, bool HasFunNoNaNAttr, 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.
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
const Value * getTrueValue() const
A cache of @llvm.assume calls within a function.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:720
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
F(f)
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:659
MaxMin_match< FCmpInst, LHS, RHS, ufmax_pred_ty > m_UnordFMax(const LHS &L, const RHS &R)
Match an &#39;unordered&#39; floating point maximum function.
static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, InstDesc &Prev, bool HasFunNoNaNAttr)
Returns a struct describing if the instruction &#39;I&#39; can be a recurrence variable of type &#39;Kind&#39;...
op_iterator op_begin()
Definition: User.h:229
static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction *> &Insts, unsigned MaxNumUses)
Returns true if instruction I has multiple uses in Insts.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
This is the interface for a SCEV-based alias analysis.
static FastMathFlags getFast()
Definition: Operator.h:190
This class represents the LLVM &#39;select&#39; instruction.
Type * getPointerElementType() const
Definition: Type.h:375
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:161
static Instruction * lookThroughAnd(PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction *> &Visited, SmallPtrSetImpl< Instruction *> &CI)
Determines if Phi may have been type-promoted.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:196
static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction *> &Set)
Returns true if all uses of the instruction I is within the Set.
static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev)
Returns a struct describing if the instruction if the instruction is a Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) or max(X, Y).
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...
MaxMin_match< FCmpInst, LHS, RHS, ufmin_pred_ty > m_UnordFMin(const LHS &L, const RHS &R)
Match an &#39;unordered&#39; floating point minimum function.
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
BlockT * getHeader() const
Definition: LoopInfo.h:102
ConstantInt * getValue() const
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:200
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
This node represents a polynomial recurrence on the trip count of the specified loop.
This instruction compares its operands according to the predicate given to the constructor.
MaxMin_match< FCmpInst, LHS, RHS, ofmin_pred_ty > m_OrdFMin(const LHS &L, const RHS &R)
Match an &#39;ordered&#39; floating point minimum function.
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
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...
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:208
This POD struct holds information about a potential recurrence operation.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:95
bool isFloatTy() const
Return true if this is &#39;float&#39;, a 32-bit IEEE fp type.
Definition: Type.h:146
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...
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty > m_UMax(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:175
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
Value * getIncomingValueForBlock(const BasicBlock *BB) const
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
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.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:433
op_iterator op_end()
Definition: User.h:231
bool isFast() const
Determine whether all fast-math-flags are set.
bool isHalfTy() const
Return true if this is &#39;half&#39;, a 16-bit IEEE fp type.
Definition: Type.h:143
bool isBinaryOp() const
Definition: Instruction.h:130
op_range operands()
Definition: User.h:237
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
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.
const Value * getCondition() const
static InstDesc isConditionalRdxPattern(RecurrenceKind Kind, Instruction *I)
Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:639
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
static unsigned getRecurrenceBinOp(RecurrenceKind Kind)
Returns the opcode of binary operation corresponding to the RecurrenceKind.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static bool isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, DenseMap< Instruction *, Instruction *> &SinkAfter, DominatorTree *DT)
Returns true if Phi is a first-order recurrence.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:62
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:239
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:112
MinMaxRecurrenceKind getMinMaxKind()
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
Type * getType() const
Return the LLVM type of this SCEV expression.
A struct for saving information about induction variables.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Module.h This file contains the declarations for the Module class.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:63
static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is a floating point kind.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:179
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
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:631
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:694
unsigned getNumIncomingValues() const
Return the number of incoming edges.
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:714
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
bool isCommutative() const
Return true if the instruction is commutative:
Definition: Instruction.h:488
static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit, Type *RecurrenceType, SmallPtrSetImpl< Instruction *> &Casts)
Collect cast instructions that can be ignored in the vectorizer&#39;s cost model, given a reduction exit ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static Constant * getRecurrenceIdentity(RecurrenceKind K, Type *Tp)
Returns identity corresponding to the RecurrenceKind.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
Class for arbitrary precision integers.
Definition: APInt.h:69
iterator_range< user_iterator > users()
Definition: Value.h:399
const Value * getFalseValue() const
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:601
uint64_t getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:469
use_iterator use_begin()
Definition: Value.h:338
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:549
This class represents an analyzed expression in the program.
static bool isIntegerRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is an integer kind.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getValueAsString() const
Return the attribute&#39;s value as a string.
Definition: Attributes.cpp:223
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:467
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
uint32_t Size
Definition: Profile.cpp:46
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
MaxMin_match< FCmpInst, LHS, RHS, ofmax_pred_ty > m_OrdFMax(const LHS &L, const RHS &R)
Match an &#39;ordered&#39; floating point maximum function.
LLVM Value Representation.
Definition: Value.h:72
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool hasAllowReassoc() const
Determine whether the allow-reassociation flag is set.
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:250
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
Definition: Function.h:333
const SCEV * getUnknown(Value *V)
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:159
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:98
This pass exposes codegen information to IR-level passes.
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:156
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool isDoubleTy() const
Return true if this is &#39;double&#39;, a 64-bit IEEE fp type.
Definition: Type.h:149
bool use_empty() const
Definition: Value.h:322
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:478
RecurrenceKind
This enum represents the kinds of recurrences that we support.
Definition: IVDescriptors.h:65
const BasicBlock * getParent() const
Definition: Instruction.h:66
This class represents a constant integer value.
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:1251