LLVM  10.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  // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
304  if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi)
305  FMF &= ReduxDesc.getPatternInst()->getFastMathFlags();
306  }
307 
308  bool IsASelect = isa<SelectInst>(Cur);
309 
310  // A conditional reduction operation must only have 2 or less uses in
311  // VisitedInsts.
312  if (IsASelect && (Kind == RK_FloatAdd || Kind == RK_FloatMult) &&
313  hasMultipleUsesOf(Cur, VisitedInsts, 2))
314  return false;
315 
316  // A reduction operation must only have one use of the reduction value.
317  if (!IsAPhi && !IsASelect && Kind != RK_IntegerMinMax &&
318  Kind != RK_FloatMinMax && hasMultipleUsesOf(Cur, VisitedInsts, 1))
319  return false;
320 
321  // All inputs to a PHI node must be a reduction value.
322  if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
323  return false;
324 
325  if (Kind == RK_IntegerMinMax &&
326  (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
327  ++NumCmpSelectPatternInst;
328  if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
329  ++NumCmpSelectPatternInst;
330 
331  // Check whether we found a reduction operator.
332  FoundReduxOp |= !IsAPhi && Cur != Start;
333 
334  // Process users of current instruction. Push non-PHI nodes after PHI nodes
335  // onto the stack. This way we are going to have seen all inputs to PHI
336  // nodes once we get to them.
339  for (User *U : Cur->users()) {
340  Instruction *UI = cast<Instruction>(U);
341 
342  // Check if we found the exit user.
343  BasicBlock *Parent = UI->getParent();
344  if (!TheLoop->contains(Parent)) {
345  // If we already know this instruction is used externally, move on to
346  // the next user.
347  if (ExitInstruction == Cur)
348  continue;
349 
350  // Exit if you find multiple values used outside or if the header phi
351  // node is being used. In this case the user uses the value of the
352  // previous iteration, in which case we would loose "VF-1" iterations of
353  // the reduction operation if we vectorize.
354  if (ExitInstruction != nullptr || Cur == Phi)
355  return false;
356 
357  // The instruction used by an outside user must be the last instruction
358  // before we feed back to the reduction phi. Otherwise, we loose VF-1
359  // operations on the value.
360  if (!is_contained(Phi->operands(), Cur))
361  return false;
362 
363  ExitInstruction = Cur;
364  continue;
365  }
366 
367  // Process instructions only once (termination). Each reduction cycle
368  // value must only be used once, except by phi nodes and min/max
369  // reductions which are represented as a cmp followed by a select.
370  InstDesc IgnoredVal(false, nullptr);
371  if (VisitedInsts.insert(UI).second) {
372  if (isa<PHINode>(UI))
373  PHIs.push_back(UI);
374  else
375  NonPHIs.push_back(UI);
376  } else if (!isa<PHINode>(UI) &&
377  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
378  !isa<SelectInst>(UI)) ||
379  (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
380  !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())))
381  return false;
382 
383  // Remember that we completed the cycle.
384  if (UI == Phi)
385  FoundStartPHI = true;
386  }
387  Worklist.append(PHIs.begin(), PHIs.end());
388  Worklist.append(NonPHIs.begin(), NonPHIs.end());
389  }
390 
391  // This means we have seen one but not the other instruction of the
392  // pattern or more than just a select and cmp.
393  if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
394  NumCmpSelectPatternInst != 2)
395  return false;
396 
397  if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
398  return false;
399 
400  if (Start != Phi) {
401  // If the starting value is not the same as the phi node, we speculatively
402  // looked through an 'and' instruction when evaluating a potential
403  // arithmetic reduction to determine if it may have been type-promoted.
404  //
405  // We now compute the minimal bit width that is required to represent the
406  // reduction. If this is the same width that was indicated by the 'and', we
407  // can represent the reduction in the smaller type. The 'and' instruction
408  // will be eliminated since it will essentially be a cast instruction that
409  // can be ignore in the cost model. If we compute a different type than we
410  // did when evaluating the 'and', the 'and' will not be eliminated, and we
411  // will end up with different kinds of operations in the recurrence
412  // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is
413  // the case.
414  //
415  // The vectorizer relies on InstCombine to perform the actual
416  // type-shrinking. It does this by inserting instructions to truncate the
417  // exit value of the reduction to the width indicated by RecurrenceType and
418  // then extend this value back to the original width. If IsSigned is false,
419  // a 'zext' instruction will be generated; otherwise, a 'sext' will be
420  // used.
421  //
422  // TODO: We should not rely on InstCombine to rewrite the reduction in the
423  // smaller type. We should just generate a correctly typed expression
424  // to begin with.
425  Type *ComputedType;
426  std::tie(ComputedType, IsSigned) =
427  computeRecurrenceType(ExitInstruction, DB, AC, DT);
428  if (ComputedType != RecurrenceType)
429  return false;
430 
431  // The recurrence expression will be represented in a narrower type. If
432  // there are any cast instructions that will be unnecessary, collect them
433  // in CastInsts. Note that the 'and' instruction was already included in
434  // this list.
435  //
436  // TODO: A better way to represent this may be to tag in some way all the
437  // instructions that are a part of the reduction. The vectorizer cost
438  // model could then apply the recurrence type to these instructions,
439  // without needing a white list of instructions to ignore.
440  collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
441  }
442 
443  // We found a reduction var if we have reached the original phi node and we
444  // only have a single instruction with out-of-loop users.
445 
446  // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
447  // is saved as part of the RecurrenceDescriptor.
448 
449  // Save the description of this reduction variable.
451  RdxStart, ExitInstruction, Kind, FMF, ReduxDesc.getMinMaxKind(),
452  ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
453  RedDes = RD;
454 
455  return true;
456 }
457 
458 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
459 /// pattern corresponding to a min(X, Y) or max(X, Y).
462 
463  assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
464  "Expect a select instruction");
465  Instruction *Cmp = nullptr;
466  SelectInst *Select = nullptr;
467 
468  // We must handle the select(cmp()) as a single instruction. Advance to the
469  // select.
470  if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
471  if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
472  return InstDesc(false, I);
473  return InstDesc(Select, Prev.getMinMaxKind());
474  }
475 
476  // Only handle single use cases for now.
477  if (!(Select = dyn_cast<SelectInst>(I)))
478  return InstDesc(false, I);
479  if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
480  !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
481  return InstDesc(false, I);
482  if (!Cmp->hasOneUse())
483  return InstDesc(false, I);
484 
485  Value *CmpLeft;
486  Value *CmpRight;
487 
488  // Look for a min/max pattern.
489  if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
490  return InstDesc(Select, MRK_UIntMin);
491  else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
492  return InstDesc(Select, MRK_UIntMax);
493  else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
494  return InstDesc(Select, MRK_SIntMax);
495  else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
496  return InstDesc(Select, MRK_SIntMin);
497  else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
498  return InstDesc(Select, MRK_FloatMin);
499  else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
500  return InstDesc(Select, MRK_FloatMax);
501  else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
502  return InstDesc(Select, MRK_FloatMin);
503  else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
504  return InstDesc(Select, MRK_FloatMax);
505 
506  return InstDesc(false, I);
507 }
508 
509 /// Returns true if the select instruction has users in the compare-and-add
510 /// reduction pattern below. The select instruction argument is the last one
511 /// in the sequence.
512 ///
513 /// %sum.1 = phi ...
514 /// ...
515 /// %cmp = fcmp pred %0, %CFP
516 /// %add = fadd %0, %sum.1
517 /// %sum.2 = select %cmp, %add, %sum.1
522  if (!SI)
523  return InstDesc(false, I);
524 
525  CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
526  // Only handle single use cases for now.
527  if (!CI || !CI->hasOneUse())
528  return InstDesc(false, I);
529 
530  Value *TrueVal = SI->getTrueValue();
531  Value *FalseVal = SI->getFalseValue();
532  // Handle only when either of operands of select instruction is a PHI
533  // node for now.
534  if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
535  (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
536  return InstDesc(false, I);
537 
538  Instruction *I1 =
539  isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
540  : dyn_cast<Instruction>(TrueVal);
541  if (!I1 || !I1->isBinaryOp())
542  return InstDesc(false, I);
543 
544  Value *Op1, *Op2;
545  if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) ||
546  m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) &&
547  I1->isFast())
548  return InstDesc(Kind == RK_FloatAdd, SI);
549 
550  if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
551  return InstDesc(Kind == RK_FloatMult, SI);
552 
553  return InstDesc(false, I);
554 }
555 
558  InstDesc &Prev, bool HasFunNoNaNAttr) {
559  Instruction *UAI = Prev.getUnsafeAlgebraInst();
560  if (!UAI && isa<FPMathOperator>(I) && !I->hasAllowReassoc())
561  UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
562 
563  switch (I->getOpcode()) {
564  default:
565  return InstDesc(false, I);
566  case Instruction::PHI:
567  return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
568  case Instruction::Sub:
569  case Instruction::Add:
570  return InstDesc(Kind == RK_IntegerAdd, I);
571  case Instruction::Mul:
572  return InstDesc(Kind == RK_IntegerMult, I);
573  case Instruction::And:
574  return InstDesc(Kind == RK_IntegerAnd, I);
575  case Instruction::Or:
576  return InstDesc(Kind == RK_IntegerOr, I);
577  case Instruction::Xor:
578  return InstDesc(Kind == RK_IntegerXor, I);
579  case Instruction::FMul:
580  return InstDesc(Kind == RK_FloatMult, I, UAI);
581  case Instruction::FSub:
582  case Instruction::FAdd:
583  return InstDesc(Kind == RK_FloatAdd, I, UAI);
584  case Instruction::Select:
585  if (Kind == RK_FloatAdd || Kind == RK_FloatMult)
586  return isConditionalRdxPattern(Kind, I);
588  case Instruction::FCmp:
589  case Instruction::ICmp:
590  if (Kind != RK_IntegerMinMax &&
591  (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
592  return InstDesc(false, I);
593  return isMinMaxSelectCmpPattern(I, Prev);
594  }
595 }
596 
599  unsigned MaxNumUses) {
600  unsigned NumUses = 0;
601  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
602  ++Use) {
603  if (Insts.count(dyn_cast<Instruction>(*Use)))
604  ++NumUses;
605  if (NumUses > MaxNumUses)
606  return true;
607  }
608 
609  return false;
610 }
612  RecurrenceDescriptor &RedDes,
613  DemandedBits *DB, AssumptionCache *AC,
614  DominatorTree *DT) {
615 
616  BasicBlock *Header = TheLoop->getHeader();
617  Function &F = *Header->getParent();
618  bool HasFunNoNaNAttr =
619  F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
620 
621  if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
622  AC, DT)) {
623  LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
624  return true;
625  }
626  if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
627  AC, DT)) {
628  LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
629  return true;
630  }
631  if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB,
632  AC, DT)) {
633  LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
634  return true;
635  }
636  if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
637  AC, DT)) {
638  LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
639  return true;
640  }
641  if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
642  AC, DT)) {
643  LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
644  return true;
645  }
646  if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes,
647  DB, AC, DT)) {
648  LLVM_DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
649  return true;
650  }
651  if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
652  AC, DT)) {
653  LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
654  return true;
655  }
656  if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
657  AC, DT)) {
658  LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
659  return true;
660  }
661  if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
662  AC, DT)) {
663  LLVM_DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi
664  << "\n");
665  return true;
666  }
667  // Not a reduction of known type.
668  return false;
669 }
670 
672  PHINode *Phi, Loop *TheLoop,
674 
675  // Ensure the phi node is in the loop header and has two incoming values.
676  if (Phi->getParent() != TheLoop->getHeader() ||
677  Phi->getNumIncomingValues() != 2)
678  return false;
679 
680  // Ensure the loop has a preheader and a single latch block. The loop
681  // vectorizer will need the latch to set up the next iteration of the loop.
682  auto *Preheader = TheLoop->getLoopPreheader();
683  auto *Latch = TheLoop->getLoopLatch();
684  if (!Preheader || !Latch)
685  return false;
686 
687  // Ensure the phi node's incoming blocks are the loop preheader and latch.
688  if (Phi->getBasicBlockIndex(Preheader) < 0 ||
689  Phi->getBasicBlockIndex(Latch) < 0)
690  return false;
691 
692  // Get the previous value. The previous value comes from the latch edge while
693  // the initial value comes form the preheader edge.
694  auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
695  if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
696  SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
697  return false;
698 
699  // Ensure every user of the phi node is dominated by the previous value.
700  // The dominance requirement ensures the loop vectorizer will not need to
701  // vectorize the initial value prior to the first iteration of the loop.
702  // TODO: Consider extending this sinking to handle other kinds of instructions
703  // and expressions, beyond sinking a single cast past Previous.
704  if (Phi->hasOneUse()) {
705  auto *I = Phi->user_back();
706  if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() &&
707  DT->dominates(Previous, I->user_back())) {
708  if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
709  SinkAfter[I] = Previous;
710  return true;
711  }
712  }
713 
714  for (User *U : Phi->users())
715  if (auto *I = dyn_cast<Instruction>(U)) {
716  if (!DT->dominates(Previous, I))
717  return false;
718  }
719 
720  return true;
721 }
722 
723 /// This function returns the identity element (or neutral element) for
724 /// the operation K.
726  Type *Tp) {
727  switch (K) {
728  case RK_IntegerXor:
729  case RK_IntegerAdd:
730  case RK_IntegerOr:
731  // Adding, Xoring, Oring zero to a number does not change it.
732  return ConstantInt::get(Tp, 0);
733  case RK_IntegerMult:
734  // Multiplying a number by 1 does not change it.
735  return ConstantInt::get(Tp, 1);
736  case RK_IntegerAnd:
737  // AND-ing a number with an all-1 value does not change it.
738  return ConstantInt::get(Tp, -1, true);
739  case RK_FloatMult:
740  // Multiplying a number by 1 does not change it.
741  return ConstantFP::get(Tp, 1.0L);
742  case RK_FloatAdd:
743  // Adding zero to a number does not change it.
744  return ConstantFP::get(Tp, 0.0L);
745  default:
746  llvm_unreachable("Unknown recurrence kind");
747  }
748 }
749 
750 /// This function translates the recurrence kind to an LLVM binary operator.
752  switch (Kind) {
753  case RK_IntegerAdd:
754  return Instruction::Add;
755  case RK_IntegerMult:
756  return Instruction::Mul;
757  case RK_IntegerOr:
758  return Instruction::Or;
759  case RK_IntegerAnd:
760  return Instruction::And;
761  case RK_IntegerXor:
762  return Instruction::Xor;
763  case RK_FloatMult:
764  return Instruction::FMul;
765  case RK_FloatAdd:
766  return Instruction::FAdd;
767  case RK_IntegerMinMax:
768  return Instruction::ICmp;
769  case RK_FloatMinMax:
770  return Instruction::FCmp;
771  default:
772  llvm_unreachable("Unknown recurrence operation");
773  }
774 }
775 
776 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
777  const SCEV *Step, BinaryOperator *BOp,
779  : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
780  assert(IK != IK_NoInduction && "Not an induction");
781 
782  // Start value type should match the induction kind and the value
783  // itself should not be null.
784  assert(StartValue && "StartValue is null");
785  assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
786  "StartValue is not a pointer for pointer induction");
787  assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
788  "StartValue is not an integer for integer induction");
789 
790  // Check the Step Value. It should be non-zero integer value.
791  assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
792  "Step value is zero");
793 
794  assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
795  "Step value should be constant for pointer induction");
796  assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
797  "StepValue is not an integer");
798 
799  assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
800  "StepValue is not FP for FpInduction");
801  assert((IK != IK_FpInduction ||
802  (InductionBinOp &&
803  (InductionBinOp->getOpcode() == Instruction::FAdd ||
804  InductionBinOp->getOpcode() == Instruction::FSub))) &&
805  "Binary opcode should be specified for FP induction");
806 
807  if (Casts) {
808  for (auto &Inst : *Casts) {
809  RedundantCasts.push_back(Inst);
810  }
811  }
812 }
813 
815  ConstantInt *ConstStep = getConstIntStepValue();
816  if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
817  return ConstStep->getSExtValue();
818  return 0;
819 }
820 
822  if (isa<SCEVConstant>(Step))
823  return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
824  return nullptr;
825 }
826 
828  ScalarEvolution *SE,
830 
831  // Here we only handle FP induction variables.
832  assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
833 
834  if (TheLoop->getHeader() != Phi->getParent())
835  return false;
836 
837  // The loop may have multiple entrances or multiple exits; we can analyze
838  // this phi if it has a unique entry value and a unique backedge value.
839  if (Phi->getNumIncomingValues() != 2)
840  return false;
841  Value *BEValue = nullptr, *StartValue = nullptr;
842  if (TheLoop->contains(Phi->getIncomingBlock(0))) {
843  BEValue = Phi->getIncomingValue(0);
844  StartValue = Phi->getIncomingValue(1);
845  } else {
846  assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
847  "Unexpected Phi node in the loop");
848  BEValue = Phi->getIncomingValue(1);
849  StartValue = Phi->getIncomingValue(0);
850  }
851 
852  BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
853  if (!BOp)
854  return false;
855 
856  Value *Addend = nullptr;
857  if (BOp->getOpcode() == Instruction::FAdd) {
858  if (BOp->getOperand(0) == Phi)
859  Addend = BOp->getOperand(1);
860  else if (BOp->getOperand(1) == Phi)
861  Addend = BOp->getOperand(0);
862  } else if (BOp->getOpcode() == Instruction::FSub)
863  if (BOp->getOperand(0) == Phi)
864  Addend = BOp->getOperand(1);
865 
866  if (!Addend)
867  return false;
868 
869  // The addend should be loop invariant
870  if (auto *I = dyn_cast<Instruction>(Addend))
871  if (TheLoop->contains(I))
872  return false;
873 
874  // FP Step has unknown SCEV
875  const SCEV *Step = SE->getUnknown(Addend);
876  D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
877  return true;
878 }
879 
880 /// This function is called when we suspect that the update-chain of a phi node
881 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
882 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
883 /// predicate P under which the SCEV expression for the phi can be the
884 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
885 /// cast instructions that are involved in the update-chain of this induction.
886 /// A caller that adds the required runtime predicate can be free to drop these
887 /// cast instructions, and compute the phi using \p AR (instead of some scev
888 /// expression with casts).
889 ///
890 /// For example, without a predicate the scev expression can take the following
891 /// form:
892 /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
893 ///
894 /// It corresponds to the following IR sequence:
895 /// %for.body:
896 /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
897 /// %casted_phi = "ExtTrunc i64 %x"
898 /// %add = add i64 %casted_phi, %step
899 ///
900 /// where %x is given in \p PN,
901 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
902 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
903 /// several forms, for example, such as:
904 /// ExtTrunc1: %casted_phi = and %x, 2^n-1
905 /// or:
906 /// ExtTrunc2: %t = shl %x, m
907 /// %casted_phi = ashr %t, m
908 ///
909 /// If we are able to find such sequence, we return the instructions
910 /// we found, namely %casted_phi and the instructions on its use-def chain up
911 /// to the phi (not including the phi).
913  const SCEVUnknown *PhiScev,
914  const SCEVAddRecExpr *AR,
915  SmallVectorImpl<Instruction *> &CastInsts) {
916 
917  assert(CastInsts.empty() && "CastInsts is expected to be empty.");
918  auto *PN = cast<PHINode>(PhiScev->getValue());
919  assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
920  const Loop *L = AR->getLoop();
921 
922  // Find any cast instructions that participate in the def-use chain of
923  // PhiScev in the loop.
924  // FORNOW/TODO: We currently expect the def-use chain to include only
925  // two-operand instructions, where one of the operands is an invariant.
926  // createAddRecFromPHIWithCasts() currently does not support anything more
927  // involved than that, so we keep the search simple. This can be
928  // extended/generalized as needed.
929 
930  auto getDef = [&](const Value *Val) -> Value * {
931  const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
932  if (!BinOp)
933  return nullptr;
934  Value *Op0 = BinOp->getOperand(0);
935  Value *Op1 = BinOp->getOperand(1);
936  Value *Def = nullptr;
937  if (L->isLoopInvariant(Op0))
938  Def = Op1;
939  else if (L->isLoopInvariant(Op1))
940  Def = Op0;
941  return Def;
942  };
943 
944  // Look for the instruction that defines the induction via the
945  // loop backedge.
946  BasicBlock *Latch = L->getLoopLatch();
947  if (!Latch)
948  return false;
949  Value *Val = PN->getIncomingValueForBlock(Latch);
950  if (!Val)
951  return false;
952 
953  // Follow the def-use chain until the induction phi is reached.
954  // If on the way we encounter a Value that has the same SCEV Expr as the
955  // phi node, we can consider the instructions we visit from that point
956  // as part of the cast-sequence that can be ignored.
957  bool InCastSequence = false;
958  auto *Inst = dyn_cast<Instruction>(Val);
959  while (Val != PN) {
960  // If we encountered a phi node other than PN, or if we left the loop,
961  // we bail out.
962  if (!Inst || !L->contains(Inst)) {
963  return false;
964  }
965  auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
966  if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
967  InCastSequence = true;
968  if (InCastSequence) {
969  // Only the last instruction in the cast sequence is expected to have
970  // uses outside the induction def-use chain.
971  if (!CastInsts.empty())
972  if (!Inst->hasOneUse())
973  return false;
974  CastInsts.push_back(Inst);
975  }
976  Val = getDef(Val);
977  if (!Val)
978  return false;
979  Inst = dyn_cast<Instruction>(Val);
980  }
981 
982  return InCastSequence;
983 }
984 
987  InductionDescriptor &D, bool Assume) {
988  Type *PhiTy = Phi->getType();
989 
990  // Handle integer and pointer inductions variables.
991  // Now we handle also FP induction but not trying to make a
992  // recurrent expression from the PHI node in-place.
993 
994  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
995  !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
996  return false;
997 
998  if (PhiTy->isFloatingPointTy())
999  return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
1000 
1001  const SCEV *PhiScev = PSE.getSCEV(Phi);
1002  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1003 
1004  // We need this expression to be an AddRecExpr.
1005  if (Assume && !AR)
1006  AR = PSE.getAsAddRec(Phi);
1007 
1008  if (!AR) {
1009  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1010  return false;
1011  }
1012 
1013  // Record any Cast instructions that participate in the induction update
1014  const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1015  // If we started from an UnknownSCEV, and managed to build an addRecurrence
1016  // only after enabling Assume with PSCEV, this means we may have encountered
1017  // cast instructions that required adding a runtime check in order to
1018  // guarantee the correctness of the AddRecurrence respresentation of the
1019  // induction.
1020  if (PhiScev != AR && SymbolicPhi) {
1022  if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1023  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1024  }
1025 
1026  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1027 }
1028 
1030  PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1031  InductionDescriptor &D, const SCEV *Expr,
1032  SmallVectorImpl<Instruction *> *CastsToIgnore) {
1033  Type *PhiTy = Phi->getType();
1034  // We only handle integer and pointer inductions variables.
1035  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1036  return false;
1037 
1038  // Check that the PHI is consecutive.
1039  const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1040  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1041 
1042  if (!AR) {
1043  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1044  return false;
1045  }
1046 
1047  if (AR->getLoop() != TheLoop) {
1048  // FIXME: We should treat this as a uniform. Unfortunately, we
1049  // don't currently know how to handled uniform PHIs.
1050  LLVM_DEBUG(
1051  dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1052  return false;
1053  }
1054 
1055  Value *StartValue =
1057 
1058  BasicBlock *Latch = AR->getLoop()->getLoopLatch();
1059  if (!Latch)
1060  return false;
1061  BinaryOperator *BOp =
1063 
1064  const SCEV *Step = AR->getStepRecurrence(*SE);
1065  // Calculate the pointer stride and check if it is consecutive.
1066  // The stride may be a constant or a loop invariant integer value.
1067  const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1068  if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1069  return false;
1070 
1071  if (PhiTy->isIntegerTy()) {
1072  D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
1073  CastsToIgnore);
1074  return true;
1075  }
1076 
1077  assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1078  // Pointer induction should be a constant.
1079  if (!ConstStep)
1080  return false;
1081 
1082  ConstantInt *CV = ConstStep->getValue();
1083  Type *PointerElementType = PhiTy->getPointerElementType();
1084  // The pointer stride cannot be determined if the pointer element type is not
1085  // sized.
1086  if (!PointerElementType->isSized())
1087  return false;
1088 
1089  const DataLayout &DL = Phi->getModule()->getDataLayout();
1090  int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1091  if (!Size)
1092  return false;
1093 
1094  int64_t CVSize = CV->getSExtValue();
1095  if (CVSize % Size)
1096  return false;
1097  auto *StepValue =
1098  SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
1099  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp);
1100  return true;
1101 }
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:111
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:209
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:765
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:265
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:160
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:743
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:777
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.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:624
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:381
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:162
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
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
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:105
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:246
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:147
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:194
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:46
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:224
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.
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:486
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:470
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:144
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:672
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:244
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
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:184
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:653
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:716
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:832
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
bool isCommutative() const
Return true if the instruction is commutative:
Definition: Instruction.h:498
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:420
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
use_iterator use_begin()
Definition: Value.h:359
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:220
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
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:145
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:396
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:74
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:273
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:433
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:150
bool use_empty() const
Definition: Value.h:343
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:558
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:1224