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