LLVM  8.0.0svn
LoopUtils.cpp
Go to the documentation of this file.
1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines common loop utility functions.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/ScopeExit.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/LoopPass.h"
29 #include "llvm/IR/DomTreeUpdater.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/Module.h"
33 #include "llvm/IR/PatternMatch.h"
34 #include "llvm/IR/ValueHandle.h"
35 #include "llvm/Pass.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/KnownBits.h"
39 
40 using namespace llvm;
41 using namespace llvm::PatternMatch;
42 
43 #define DEBUG_TYPE "loop-utils"
44 
47  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
48  if (!Set.count(dyn_cast<Instruction>(*Use)))
49  return false;
50  return true;
51 }
52 
54  switch (Kind) {
55  default:
56  break;
57  case RK_IntegerAdd:
58  case RK_IntegerMult:
59  case RK_IntegerOr:
60  case RK_IntegerAnd:
61  case RK_IntegerXor:
62  case RK_IntegerMinMax:
63  return true;
64  }
65  return false;
66 }
67 
69  return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
70 }
71 
73  switch (Kind) {
74  default:
75  break;
76  case RK_IntegerAdd:
77  case RK_IntegerMult:
78  case RK_FloatAdd:
79  case RK_FloatMult:
80  return true;
81  }
82  return false;
83 }
84 
85 /// Determines if Phi may have been type-promoted. If Phi has a single user
86 /// that ANDs the Phi with a type mask, return the user. RT is updated to
87 /// account for the narrower bit width represented by the mask, and the AND
88 /// instruction is added to CI.
92  if (!Phi->hasOneUse())
93  return Phi;
94 
95  const APInt *M = nullptr;
96  Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
97 
98  // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
99  // with a new integer type of the corresponding bit width.
100  if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
101  int32_t Bits = (*M + 1).exactLogBase2();
102  if (Bits > 0) {
103  RT = IntegerType::get(Phi->getContext(), Bits);
104  Visited.insert(Phi);
105  CI.insert(J);
106  return J;
107  }
108  }
109  return Phi;
110 }
111 
112 /// Compute the minimal bit width needed to represent a reduction whose exit
113 /// instruction is given by Exit.
114 static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
115  DemandedBits *DB,
116  AssumptionCache *AC,
117  DominatorTree *DT) {
118  bool IsSigned = false;
119  const DataLayout &DL = Exit->getModule()->getDataLayout();
120  uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());
121 
122  if (DB) {
123  // Use the demanded bits analysis to determine the bits that are live out
124  // of the exit instruction, rounding up to the nearest power of two. If the
125  // use of demanded bits results in a smaller bit width, we know the value
126  // must be positive (i.e., IsSigned = false), because if this were not the
127  // case, the sign bit would have been demanded.
128  auto Mask = DB->getDemandedBits(Exit);
129  MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros();
130  }
131 
132  if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
133  // If demanded bits wasn't able to limit the bit width, we can try to use
134  // value tracking instead. This can be the case, for example, if the value
135  // may be negative.
136  auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
137  auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
138  MaxBitWidth = NumTypeBits - NumSignBits;
139  KnownBits Bits = computeKnownBits(Exit, DL);
140  if (!Bits.isNonNegative()) {
141  // If the value is not known to be non-negative, we set IsSigned to true,
142  // meaning that we will use sext instructions instead of zext
143  // instructions to restore the original type.
144  IsSigned = true;
145  if (!Bits.isNegative())
146  // If the value is not known to be negative, we don't known what the
147  // upper bit is, and therefore, we don't know what kind of extend we
148  // will need. In this case, just increase the bit width by one bit and
149  // use sext.
150  ++MaxBitWidth;
151  }
152  }
153  if (!isPowerOf2_64(MaxBitWidth))
154  MaxBitWidth = NextPowerOf2(MaxBitWidth);
155 
156  return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
157  IsSigned);
158 }
159 
160 /// Collect cast instructions that can be ignored in the vectorizer's cost
161 /// model, given a reduction exit value and the minimal type in which the
162 /// reduction can be represented.
163 static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
164  Type *RecurrenceType,
166 
169  Worklist.push_back(Exit);
170 
171  while (!Worklist.empty()) {
172  Instruction *Val = Worklist.pop_back_val();
173  Visited.insert(Val);
174  if (auto *Cast = dyn_cast<CastInst>(Val))
175  if (Cast->getSrcTy() == RecurrenceType) {
176  // If the source type of a cast instruction is equal to the recurrence
177  // type, it will be eliminated, and should be ignored in the vectorizer
178  // cost model.
179  Casts.insert(Cast);
180  continue;
181  }
182 
183  // Add all operands to the work list if they are loop-varying values that
184  // we haven't yet visited.
185  for (Value *O : cast<User>(Val)->operands())
186  if (auto *I = dyn_cast<Instruction>(O))
187  if (TheLoop->contains(I) && !Visited.count(I))
188  Worklist.push_back(I);
189  }
190 }
191 
193  Loop *TheLoop, bool HasFunNoNaNAttr,
194  RecurrenceDescriptor &RedDes,
195  DemandedBits *DB,
196  AssumptionCache *AC,
197  DominatorTree *DT) {
198  if (Phi->getNumIncomingValues() != 2)
199  return false;
200 
201  // Reduction variables are only found in the loop header block.
202  if (Phi->getParent() != TheLoop->getHeader())
203  return false;
204 
205  // Obtain the reduction start value from the value that comes from the loop
206  // preheader.
207  Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
208 
209  // ExitInstruction is the single value which is used outside the loop.
210  // We only allow for a single reduction value to be used outside the loop.
211  // This includes users of the reduction, variables (which form a cycle
212  // which ends in the phi node).
213  Instruction *ExitInstruction = nullptr;
214  // Indicates that we found a reduction operation in our scan.
215  bool FoundReduxOp = false;
216 
217  // We start with the PHI node and scan for all of the users of this
218  // instruction. All users must be instructions that can be used as reduction
219  // variables (such as ADD). We must have a single out-of-block user. The cycle
220  // must include the original PHI.
221  bool FoundStartPHI = false;
222 
223  // To recognize min/max patterns formed by a icmp select sequence, we store
224  // the number of instruction we saw from the recognized min/max pattern,
225  // to make sure we only see exactly the two instructions.
226  unsigned NumCmpSelectPatternInst = 0;
227  InstDesc ReduxDesc(false, nullptr);
228 
229  // Data used for determining if the recurrence has been type-promoted.
230  Type *RecurrenceType = Phi->getType();
232  Instruction *Start = Phi;
233  bool IsSigned = false;
234 
235  SmallPtrSet<Instruction *, 8> VisitedInsts;
237 
238  // Return early if the recurrence kind does not match the type of Phi. If the
239  // recurrence kind is arithmetic, we attempt to look through AND operations
240  // resulting from the type promotion performed by InstCombine. Vector
241  // operations are not limited to the legal integer widths, so we may be able
242  // to evaluate the reduction in the narrower width.
243  if (RecurrenceType->isFloatingPointTy()) {
244  if (!isFloatingPointRecurrenceKind(Kind))
245  return false;
246  } else {
247  if (!isIntegerRecurrenceKind(Kind))
248  return false;
249  if (isArithmeticRecurrenceKind(Kind))
250  Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
251  }
252 
253  Worklist.push_back(Start);
254  VisitedInsts.insert(Start);
255 
256  // A value in the reduction can be used:
257  // - By the reduction:
258  // - Reduction operation:
259  // - One use of reduction value (safe).
260  // - Multiple use of reduction value (not safe).
261  // - PHI:
262  // - All uses of the PHI must be the reduction (safe).
263  // - Otherwise, not safe.
264  // - By instructions outside of the loop (safe).
265  // * One value may have several outside users, but all outside
266  // uses must be of the same value.
267  // - By an instruction that is not part of the reduction (not safe).
268  // This is either:
269  // * An instruction type other than PHI or the reduction operation.
270  // * A PHI in the header other than the initial PHI.
271  while (!Worklist.empty()) {
272  Instruction *Cur = Worklist.back();
273  Worklist.pop_back();
274 
275  // No Users.
276  // If the instruction has no users then this is a broken chain and can't be
277  // a reduction variable.
278  if (Cur->use_empty())
279  return false;
280 
281  bool IsAPhi = isa<PHINode>(Cur);
282 
283  // A header PHI use other than the original PHI.
284  if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
285  return false;
286 
287  // Reductions of instructions such as Div, and Sub is only possible if the
288  // LHS is the reduction variable.
289  if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
290  !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
291  !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
292  return false;
293 
294  // Any reduction instruction must be of one of the allowed kinds. We ignore
295  // the starting value (the Phi or an AND instruction if the Phi has been
296  // type-promoted).
297  if (Cur != Start) {
298  ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
299  if (!ReduxDesc.isRecurrence())
300  return false;
301  }
302 
303  // A reduction operation must only have one use of the reduction value.
304  if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
305  hasMultipleUsesOf(Cur, VisitedInsts))
306  return false;
307 
308  // All inputs to a PHI node must be a reduction value.
309  if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
310  return false;
311 
312  if (Kind == RK_IntegerMinMax &&
313  (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
314  ++NumCmpSelectPatternInst;
315  if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
316  ++NumCmpSelectPatternInst;
317 
318  // Check whether we found a reduction operator.
319  FoundReduxOp |= !IsAPhi && Cur != Start;
320 
321  // Process users of current instruction. Push non-PHI nodes after PHI nodes
322  // onto the stack. This way we are going to have seen all inputs to PHI
323  // nodes once we get to them.
326  for (User *U : Cur->users()) {
327  Instruction *UI = cast<Instruction>(U);
328 
329  // Check if we found the exit user.
330  BasicBlock *Parent = UI->getParent();
331  if (!TheLoop->contains(Parent)) {
332  // If we already know this instruction is used externally, move on to
333  // the next user.
334  if (ExitInstruction == Cur)
335  continue;
336 
337  // Exit if you find multiple values used outside or if the header phi
338  // node is being used. In this case the user uses the value of the
339  // previous iteration, in which case we would loose "VF-1" iterations of
340  // the reduction operation if we vectorize.
341  if (ExitInstruction != nullptr || Cur == Phi)
342  return false;
343 
344  // The instruction used by an outside user must be the last instruction
345  // before we feed back to the reduction phi. Otherwise, we loose VF-1
346  // operations on the value.
347  if (!is_contained(Phi->operands(), Cur))
348  return false;
349 
350  ExitInstruction = Cur;
351  continue;
352  }
353 
354  // Process instructions only once (termination). Each reduction cycle
355  // value must only be used once, except by phi nodes and min/max
356  // reductions which are represented as a cmp followed by a select.
357  InstDesc IgnoredVal(false, nullptr);
358  if (VisitedInsts.insert(UI).second) {
359  if (isa<PHINode>(UI))
360  PHIs.push_back(UI);
361  else
362  NonPHIs.push_back(UI);
363  } else if (!isa<PHINode>(UI) &&
364  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
365  !isa<SelectInst>(UI)) ||
366  !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
367  return false;
368 
369  // Remember that we completed the cycle.
370  if (UI == Phi)
371  FoundStartPHI = true;
372  }
373  Worklist.append(PHIs.begin(), PHIs.end());
374  Worklist.append(NonPHIs.begin(), NonPHIs.end());
375  }
376 
377  // This means we have seen one but not the other instruction of the
378  // pattern or more than just a select and cmp.
379  if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
380  NumCmpSelectPatternInst != 2)
381  return false;
382 
383  if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
384  return false;
385 
386  if (Start != Phi) {
387  // If the starting value is not the same as the phi node, we speculatively
388  // looked through an 'and' instruction when evaluating a potential
389  // arithmetic reduction to determine if it may have been type-promoted.
390  //
391  // We now compute the minimal bit width that is required to represent the
392  // reduction. If this is the same width that was indicated by the 'and', we
393  // can represent the reduction in the smaller type. The 'and' instruction
394  // will be eliminated since it will essentially be a cast instruction that
395  // can be ignore in the cost model. If we compute a different type than we
396  // did when evaluating the 'and', the 'and' will not be eliminated, and we
397  // will end up with different kinds of operations in the recurrence
398  // expression (e.g., RK_IntegerAND, RK_IntegerADD). We give up if this is
399  // the case.
400  //
401  // The vectorizer relies on InstCombine to perform the actual
402  // type-shrinking. It does this by inserting instructions to truncate the
403  // exit value of the reduction to the width indicated by RecurrenceType and
404  // then extend this value back to the original width. If IsSigned is false,
405  // a 'zext' instruction will be generated; otherwise, a 'sext' will be
406  // used.
407  //
408  // TODO: We should not rely on InstCombine to rewrite the reduction in the
409  // smaller type. We should just generate a correctly typed expression
410  // to begin with.
411  Type *ComputedType;
412  std::tie(ComputedType, IsSigned) =
413  computeRecurrenceType(ExitInstruction, DB, AC, DT);
414  if (ComputedType != RecurrenceType)
415  return false;
416 
417  // The recurrence expression will be represented in a narrower type. If
418  // there are any cast instructions that will be unnecessary, collect them
419  // in CastInsts. Note that the 'and' instruction was already included in
420  // this list.
421  //
422  // TODO: A better way to represent this may be to tag in some way all the
423  // instructions that are a part of the reduction. The vectorizer cost
424  // model could then apply the recurrence type to these instructions,
425  // without needing a white list of instructions to ignore.
426  collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
427  }
428 
429  // We found a reduction var if we have reached the original phi node and we
430  // only have a single instruction with out-of-loop users.
431 
432  // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
433  // is saved as part of the RecurrenceDescriptor.
434 
435  // Save the description of this reduction variable.
437  RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
438  ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
439  RedDes = RD;
440 
441  return true;
442 }
443 
444 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
445 /// pattern corresponding to a min(X, Y) or max(X, Y).
448 
449  assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
450  "Expect a select instruction");
451  Instruction *Cmp = nullptr;
452  SelectInst *Select = nullptr;
453 
454  // We must handle the select(cmp()) as a single instruction. Advance to the
455  // select.
456  if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
457  if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
458  return InstDesc(false, I);
459  return InstDesc(Select, Prev.getMinMaxKind());
460  }
461 
462  // Only handle single use cases for now.
463  if (!(Select = dyn_cast<SelectInst>(I)))
464  return InstDesc(false, I);
465  if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
466  !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
467  return InstDesc(false, I);
468  if (!Cmp->hasOneUse())
469  return InstDesc(false, I);
470 
471  Value *CmpLeft;
472  Value *CmpRight;
473 
474  // Look for a min/max pattern.
475  if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
476  return InstDesc(Select, MRK_UIntMin);
477  else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
478  return InstDesc(Select, MRK_UIntMax);
479  else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
480  return InstDesc(Select, MRK_SIntMax);
481  else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
482  return InstDesc(Select, MRK_SIntMin);
483  else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
484  return InstDesc(Select, MRK_FloatMin);
485  else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
486  return InstDesc(Select, MRK_FloatMax);
487  else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
488  return InstDesc(Select, MRK_FloatMin);
489  else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
490  return InstDesc(Select, MRK_FloatMax);
491 
492  return InstDesc(false, I);
493 }
494 
497  InstDesc &Prev, bool HasFunNoNaNAttr) {
498  bool FP = I->getType()->isFloatingPointTy();
499  Instruction *UAI = Prev.getUnsafeAlgebraInst();
500  if (!UAI && FP && !I->isFast())
501  UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
502 
503  switch (I->getOpcode()) {
504  default:
505  return InstDesc(false, I);
506  case Instruction::PHI:
507  return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
508  case Instruction::Sub:
509  case Instruction::Add:
510  return InstDesc(Kind == RK_IntegerAdd, I);
511  case Instruction::Mul:
512  return InstDesc(Kind == RK_IntegerMult, I);
513  case Instruction::And:
514  return InstDesc(Kind == RK_IntegerAnd, I);
515  case Instruction::Or:
516  return InstDesc(Kind == RK_IntegerOr, I);
517  case Instruction::Xor:
518  return InstDesc(Kind == RK_IntegerXor, I);
519  case Instruction::FMul:
520  return InstDesc(Kind == RK_FloatMult, I, UAI);
521  case Instruction::FSub:
522  case Instruction::FAdd:
523  return InstDesc(Kind == RK_FloatAdd, I, UAI);
524  case Instruction::FCmp:
525  case Instruction::ICmp:
526  case Instruction::Select:
527  if (Kind != RK_IntegerMinMax &&
528  (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
529  return InstDesc(false, I);
530  return isMinMaxSelectCmpPattern(I, Prev);
531  }
532 }
533 
536  unsigned NumUses = 0;
537  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
538  ++Use) {
539  if (Insts.count(dyn_cast<Instruction>(*Use)))
540  ++NumUses;
541  if (NumUses > 1)
542  return true;
543  }
544 
545  return false;
546 }
548  RecurrenceDescriptor &RedDes,
549  DemandedBits *DB, AssumptionCache *AC,
550  DominatorTree *DT) {
551 
552  BasicBlock *Header = TheLoop->getHeader();
553  Function &F = *Header->getParent();
554  bool HasFunNoNaNAttr =
555  F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
556 
557  if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
558  AC, DT)) {
559  LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
560  return true;
561  }
562  if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
563  AC, DT)) {
564  LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
565  return true;
566  }
567  if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB,
568  AC, DT)) {
569  LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
570  return true;
571  }
572  if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
573  AC, DT)) {
574  LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
575  return true;
576  }
577  if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
578  AC, DT)) {
579  LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
580  return true;
581  }
582  if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes,
583  DB, AC, DT)) {
584  LLVM_DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
585  return true;
586  }
587  if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
588  AC, DT)) {
589  LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
590  return true;
591  }
592  if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
593  AC, DT)) {
594  LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
595  return true;
596  }
597  if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
598  AC, DT)) {
599  LLVM_DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi
600  << "\n");
601  return true;
602  }
603  // Not a reduction of known type.
604  return false;
605 }
606 
608  PHINode *Phi, Loop *TheLoop,
610 
611  // Ensure the phi node is in the loop header and has two incoming values.
612  if (Phi->getParent() != TheLoop->getHeader() ||
613  Phi->getNumIncomingValues() != 2)
614  return false;
615 
616  // Ensure the loop has a preheader and a single latch block. The loop
617  // vectorizer will need the latch to set up the next iteration of the loop.
618  auto *Preheader = TheLoop->getLoopPreheader();
619  auto *Latch = TheLoop->getLoopLatch();
620  if (!Preheader || !Latch)
621  return false;
622 
623  // Ensure the phi node's incoming blocks are the loop preheader and latch.
624  if (Phi->getBasicBlockIndex(Preheader) < 0 ||
625  Phi->getBasicBlockIndex(Latch) < 0)
626  return false;
627 
628  // Get the previous value. The previous value comes from the latch edge while
629  // the initial value comes form the preheader edge.
630  auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
631  if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
632  SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
633  return false;
634 
635  // Ensure every user of the phi node is dominated by the previous value.
636  // The dominance requirement ensures the loop vectorizer will not need to
637  // vectorize the initial value prior to the first iteration of the loop.
638  // TODO: Consider extending this sinking to handle other kinds of instructions
639  // and expressions, beyond sinking a single cast past Previous.
640  if (Phi->hasOneUse()) {
641  auto *I = Phi->user_back();
642  if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() &&
643  DT->dominates(Previous, I->user_back())) {
644  if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
645  SinkAfter[I] = Previous;
646  return true;
647  }
648  }
649 
650  for (User *U : Phi->users())
651  if (auto *I = dyn_cast<Instruction>(U)) {
652  if (!DT->dominates(Previous, I))
653  return false;
654  }
655 
656  return true;
657 }
658 
659 /// This function returns the identity element (or neutral element) for
660 /// the operation K.
662  Type *Tp) {
663  switch (K) {
664  case RK_IntegerXor:
665  case RK_IntegerAdd:
666  case RK_IntegerOr:
667  // Adding, Xoring, Oring zero to a number does not change it.
668  return ConstantInt::get(Tp, 0);
669  case RK_IntegerMult:
670  // Multiplying a number by 1 does not change it.
671  return ConstantInt::get(Tp, 1);
672  case RK_IntegerAnd:
673  // AND-ing a number with an all-1 value does not change it.
674  return ConstantInt::get(Tp, -1, true);
675  case RK_FloatMult:
676  // Multiplying a number by 1 does not change it.
677  return ConstantFP::get(Tp, 1.0L);
678  case RK_FloatAdd:
679  // Adding zero to a number does not change it.
680  return ConstantFP::get(Tp, 0.0L);
681  default:
682  llvm_unreachable("Unknown recurrence kind");
683  }
684 }
685 
686 /// This function translates the recurrence kind to an LLVM binary operator.
688  switch (Kind) {
689  case RK_IntegerAdd:
690  return Instruction::Add;
691  case RK_IntegerMult:
692  return Instruction::Mul;
693  case RK_IntegerOr:
694  return Instruction::Or;
695  case RK_IntegerAnd:
696  return Instruction::And;
697  case RK_IntegerXor:
698  return Instruction::Xor;
699  case RK_FloatMult:
700  return Instruction::FMul;
701  case RK_FloatAdd:
702  return Instruction::FAdd;
703  case RK_IntegerMinMax:
704  return Instruction::ICmp;
705  case RK_FloatMinMax:
706  return Instruction::FCmp;
707  default:
708  llvm_unreachable("Unknown recurrence operation");
709  }
710 }
711 
714  Value *Left, Value *Right) {
716  switch (RK) {
717  default:
718  llvm_unreachable("Unknown min/max recurrence kind");
719  case MRK_UIntMin:
720  P = CmpInst::ICMP_ULT;
721  break;
722  case MRK_UIntMax:
723  P = CmpInst::ICMP_UGT;
724  break;
725  case MRK_SIntMin:
726  P = CmpInst::ICMP_SLT;
727  break;
728  case MRK_SIntMax:
729  P = CmpInst::ICMP_SGT;
730  break;
731  case MRK_FloatMin:
732  P = CmpInst::FCMP_OLT;
733  break;
734  case MRK_FloatMax:
735  P = CmpInst::FCMP_OGT;
736  break;
737  }
738 
739  // We only match FP sequences that are 'fast', so we can unconditionally
740  // set it on any generated instructions.
741  IRBuilder<>::FastMathFlagGuard FMFG(Builder);
742  FastMathFlags FMF;
743  FMF.setFast();
744  Builder.setFastMathFlags(FMF);
745 
746  Value *Cmp;
747  if (RK == MRK_FloatMin || RK == MRK_FloatMax)
748  Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
749  else
750  Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
751 
752  Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
753  return Select;
754 }
755 
756 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
757  const SCEV *Step, BinaryOperator *BOp,
759  : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
760  assert(IK != IK_NoInduction && "Not an induction");
761 
762  // Start value type should match the induction kind and the value
763  // itself should not be null.
764  assert(StartValue && "StartValue is null");
765  assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
766  "StartValue is not a pointer for pointer induction");
767  assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
768  "StartValue is not an integer for integer induction");
769 
770  // Check the Step Value. It should be non-zero integer value.
771  assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
772  "Step value is zero");
773 
774  assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
775  "Step value should be constant for pointer induction");
776  assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&
777  "StepValue is not an integer");
778 
779  assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
780  "StepValue is not FP for FpInduction");
781  assert((IK != IK_FpInduction || (InductionBinOp &&
782  (InductionBinOp->getOpcode() == Instruction::FAdd ||
783  InductionBinOp->getOpcode() == Instruction::FSub))) &&
784  "Binary opcode should be specified for FP induction");
785 
786  if (Casts) {
787  for (auto &Inst : *Casts) {
788  RedundantCasts.push_back(Inst);
789  }
790  }
791 }
792 
794  ConstantInt *ConstStep = getConstIntStepValue();
795  if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
796  return ConstStep->getSExtValue();
797  return 0;
798 }
799 
801  if (isa<SCEVConstant>(Step))
802  return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
803  return nullptr;
804 }
805 
807  ScalarEvolution *SE,
808  const DataLayout& DL) const {
809 
810  SCEVExpander Exp(*SE, DL, "induction");
811  assert(Index->getType() == Step->getType() &&
812  "Index type does not match StepValue type");
813  switch (IK) {
814  case IK_IntInduction: {
815  assert(Index->getType() == StartValue->getType() &&
816  "Index type does not match StartValue type");
817 
818  // FIXME: Theoretically, we can call getAddExpr() of ScalarEvolution
819  // and calculate (Start + Index * Step) for all cases, without
820  // special handling for "isOne" and "isMinusOne".
821  // But in the real life the result code getting worse. We mix SCEV
822  // expressions and ADD/SUB operations and receive redundant
823  // intermediate values being calculated in different ways and
824  // Instcombine is unable to reduce them all.
825 
826  if (getConstIntStepValue() &&
827  getConstIntStepValue()->isMinusOne())
828  return B.CreateSub(StartValue, Index);
829  if (getConstIntStepValue() &&
830  getConstIntStepValue()->isOne())
831  return B.CreateAdd(StartValue, Index);
832  const SCEV *S = SE->getAddExpr(SE->getSCEV(StartValue),
833  SE->getMulExpr(Step, SE->getSCEV(Index)));
834  return Exp.expandCodeFor(S, StartValue->getType(), &*B.GetInsertPoint());
835  }
836  case IK_PtrInduction: {
837  assert(isa<SCEVConstant>(Step) &&
838  "Expected constant step for pointer induction");
839  const SCEV *S = SE->getMulExpr(SE->getSCEV(Index), Step);
840  Index = Exp.expandCodeFor(S, Index->getType(), &*B.GetInsertPoint());
841  return B.CreateGEP(nullptr, StartValue, Index);
842  }
843  case IK_FpInduction: {
844  assert(Step->getType()->isFloatingPointTy() && "Expected FP Step value");
845  assert(InductionBinOp &&
846  (InductionBinOp->getOpcode() == Instruction::FAdd ||
847  InductionBinOp->getOpcode() == Instruction::FSub) &&
848  "Original bin op should be defined for FP induction");
849 
850  Value *StepValue = cast<SCEVUnknown>(Step)->getValue();
851 
852  // Floating point operations had to be 'fast' to enable the induction.
853  FastMathFlags Flags;
854  Flags.setFast();
855 
856  Value *MulExp = B.CreateFMul(StepValue, Index);
857  if (isa<Instruction>(MulExp))
858  // We have to check, the MulExp may be a constant.
859  cast<Instruction>(MulExp)->setFastMathFlags(Flags);
860 
861  Value *BOp = B.CreateBinOp(InductionBinOp->getOpcode() , StartValue,
862  MulExp, "induction");
863  if (isa<Instruction>(BOp))
864  cast<Instruction>(BOp)->setFastMathFlags(Flags);
865 
866  return BOp;
867  }
868  case IK_NoInduction:
869  return nullptr;
870  }
871  llvm_unreachable("invalid enum");
872 }
873 
875  ScalarEvolution *SE,
877 
878  // Here we only handle FP induction variables.
879  assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
880 
881  if (TheLoop->getHeader() != Phi->getParent())
882  return false;
883 
884  // The loop may have multiple entrances or multiple exits; we can analyze
885  // this phi if it has a unique entry value and a unique backedge value.
886  if (Phi->getNumIncomingValues() != 2)
887  return false;
888  Value *BEValue = nullptr, *StartValue = nullptr;
889  if (TheLoop->contains(Phi->getIncomingBlock(0))) {
890  BEValue = Phi->getIncomingValue(0);
891  StartValue = Phi->getIncomingValue(1);
892  } else {
893  assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
894  "Unexpected Phi node in the loop");
895  BEValue = Phi->getIncomingValue(1);
896  StartValue = Phi->getIncomingValue(0);
897  }
898 
899  BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
900  if (!BOp)
901  return false;
902 
903  Value *Addend = nullptr;
904  if (BOp->getOpcode() == Instruction::FAdd) {
905  if (BOp->getOperand(0) == Phi)
906  Addend = BOp->getOperand(1);
907  else if (BOp->getOperand(1) == Phi)
908  Addend = BOp->getOperand(0);
909  } else if (BOp->getOpcode() == Instruction::FSub)
910  if (BOp->getOperand(0) == Phi)
911  Addend = BOp->getOperand(1);
912 
913  if (!Addend)
914  return false;
915 
916  // The addend should be loop invariant
917  if (auto *I = dyn_cast<Instruction>(Addend))
918  if (TheLoop->contains(I))
919  return false;
920 
921  // FP Step has unknown SCEV
922  const SCEV *Step = SE->getUnknown(Addend);
923  D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
924  return true;
925 }
926 
927 /// This function is called when we suspect that the update-chain of a phi node
928 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
929 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
930 /// predicate P under which the SCEV expression for the phi can be the
931 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
932 /// cast instructions that are involved in the update-chain of this induction.
933 /// A caller that adds the required runtime predicate can be free to drop these
934 /// cast instructions, and compute the phi using \p AR (instead of some scev
935 /// expression with casts).
936 ///
937 /// For example, without a predicate the scev expression can take the following
938 /// form:
939 /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
940 ///
941 /// It corresponds to the following IR sequence:
942 /// %for.body:
943 /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
944 /// %casted_phi = "ExtTrunc i64 %x"
945 /// %add = add i64 %casted_phi, %step
946 ///
947 /// where %x is given in \p PN,
948 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
949 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
950 /// several forms, for example, such as:
951 /// ExtTrunc1: %casted_phi = and %x, 2^n-1
952 /// or:
953 /// ExtTrunc2: %t = shl %x, m
954 /// %casted_phi = ashr %t, m
955 ///
956 /// If we are able to find such sequence, we return the instructions
957 /// we found, namely %casted_phi and the instructions on its use-def chain up
958 /// to the phi (not including the phi).
960  const SCEVUnknown *PhiScev,
961  const SCEVAddRecExpr *AR,
962  SmallVectorImpl<Instruction *> &CastInsts) {
963 
964  assert(CastInsts.empty() && "CastInsts is expected to be empty.");
965  auto *PN = cast<PHINode>(PhiScev->getValue());
966  assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");
967  const Loop *L = AR->getLoop();
968 
969  // Find any cast instructions that participate in the def-use chain of
970  // PhiScev in the loop.
971  // FORNOW/TODO: We currently expect the def-use chain to include only
972  // two-operand instructions, where one of the operands is an invariant.
973  // createAddRecFromPHIWithCasts() currently does not support anything more
974  // involved than that, so we keep the search simple. This can be
975  // extended/generalized as needed.
976 
977  auto getDef = [&](const Value *Val) -> Value * {
978  const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
979  if (!BinOp)
980  return nullptr;
981  Value *Op0 = BinOp->getOperand(0);
982  Value *Op1 = BinOp->getOperand(1);
983  Value *Def = nullptr;
984  if (L->isLoopInvariant(Op0))
985  Def = Op1;
986  else if (L->isLoopInvariant(Op1))
987  Def = Op0;
988  return Def;
989  };
990 
991  // Look for the instruction that defines the induction via the
992  // loop backedge.
993  BasicBlock *Latch = L->getLoopLatch();
994  if (!Latch)
995  return false;
996  Value *Val = PN->getIncomingValueForBlock(Latch);
997  if (!Val)
998  return false;
999 
1000  // Follow the def-use chain until the induction phi is reached.
1001  // If on the way we encounter a Value that has the same SCEV Expr as the
1002  // phi node, we can consider the instructions we visit from that point
1003  // as part of the cast-sequence that can be ignored.
1004  bool InCastSequence = false;
1005  auto *Inst = dyn_cast<Instruction>(Val);
1006  while (Val != PN) {
1007  // If we encountered a phi node other than PN, or if we left the loop,
1008  // we bail out.
1009  if (!Inst || !L->contains(Inst)) {
1010  return false;
1011  }
1012  auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
1013  if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
1014  InCastSequence = true;
1015  if (InCastSequence) {
1016  // Only the last instruction in the cast sequence is expected to have
1017  // uses outside the induction def-use chain.
1018  if (!CastInsts.empty())
1019  if (!Inst->hasOneUse())
1020  return false;
1021  CastInsts.push_back(Inst);
1022  }
1023  Val = getDef(Val);
1024  if (!Val)
1025  return false;
1026  Inst = dyn_cast<Instruction>(Val);
1027  }
1028 
1029  return InCastSequence;
1030 }
1031 
1035  bool Assume) {
1036  Type *PhiTy = Phi->getType();
1037 
1038  // Handle integer and pointer inductions variables.
1039  // Now we handle also FP induction but not trying to make a
1040  // recurrent expression from the PHI node in-place.
1041 
1042  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() &&
1043  !PhiTy->isFloatTy() && !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
1044  return false;
1045 
1046  if (PhiTy->isFloatingPointTy())
1047  return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);
1048 
1049  const SCEV *PhiScev = PSE.getSCEV(Phi);
1050  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1051 
1052  // We need this expression to be an AddRecExpr.
1053  if (Assume && !AR)
1054  AR = PSE.getAsAddRec(Phi);
1055 
1056  if (!AR) {
1057  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1058  return false;
1059  }
1060 
1061  // Record any Cast instructions that participate in the induction update
1062  const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
1063  // If we started from an UnknownSCEV, and managed to build an addRecurrence
1064  // only after enabling Assume with PSCEV, this means we may have encountered
1065  // cast instructions that required adding a runtime check in order to
1066  // guarantee the correctness of the AddRecurence respresentation of the
1067  // induction.
1068  if (PhiScev != AR && SymbolicPhi) {
1070  if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
1071  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
1072  }
1073 
1074  return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1075 }
1076 
1078  PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
1079  InductionDescriptor &D, const SCEV *Expr,
1080  SmallVectorImpl<Instruction *> *CastsToIgnore) {
1081  Type *PhiTy = Phi->getType();
1082  // We only handle integer and pointer inductions variables.
1083  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
1084  return false;
1085 
1086  // Check that the PHI is consecutive.
1087  const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
1088  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
1089 
1090  if (!AR) {
1091  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
1092  return false;
1093  }
1094 
1095  if (AR->getLoop() != TheLoop) {
1096  // FIXME: We should treat this as a uniform. Unfortunately, we
1097  // don't currently know how to handled uniform PHIs.
1098  LLVM_DEBUG(
1099  dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
1100  return false;
1101  }
1102 
1103  Value *StartValue =
1105  const SCEV *Step = AR->getStepRecurrence(*SE);
1106  // Calculate the pointer stride and check if it is consecutive.
1107  // The stride may be a constant or a loop invariant integer value.
1108  const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
1109  if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
1110  return false;
1111 
1112  if (PhiTy->isIntegerTy()) {
1113  D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/ nullptr,
1114  CastsToIgnore);
1115  return true;
1116  }
1117 
1118  assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
1119  // Pointer induction should be a constant.
1120  if (!ConstStep)
1121  return false;
1122 
1123  ConstantInt *CV = ConstStep->getValue();
1124  Type *PointerElementType = PhiTy->getPointerElementType();
1125  // The pointer stride cannot be determined if the pointer element type is not
1126  // sized.
1127  if (!PointerElementType->isSized())
1128  return false;
1129 
1130  const DataLayout &DL = Phi->getModule()->getDataLayout();
1131  int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
1132  if (!Size)
1133  return false;
1134 
1135  int64_t CVSize = CV->getSExtValue();
1136  if (CVSize % Size)
1137  return false;
1138  auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size,
1139  true /* signed */);
1140  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
1141  return true;
1142 }
1143 
1145  bool PreserveLCSSA) {
1146  bool Changed = false;
1147 
1148  // We re-use a vector for the in-loop predecesosrs.
1149  SmallVector<BasicBlock *, 4> InLoopPredecessors;
1150 
1151  auto RewriteExit = [&](BasicBlock *BB) {
1152  assert(InLoopPredecessors.empty() &&
1153  "Must start with an empty predecessors list!");
1154  auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });
1155 
1156  // See if there are any non-loop predecessors of this exit block and
1157  // keep track of the in-loop predecessors.
1158  bool IsDedicatedExit = true;
1159  for (auto *PredBB : predecessors(BB))
1160  if (L->contains(PredBB)) {
1161  if (isa<IndirectBrInst>(PredBB->getTerminator()))
1162  // We cannot rewrite exiting edges from an indirectbr.
1163  return false;
1164 
1165  InLoopPredecessors.push_back(PredBB);
1166  } else {
1167  IsDedicatedExit = false;
1168  }
1169 
1170  assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
1171 
1172  // Nothing to do if this is already a dedicated exit.
1173  if (IsDedicatedExit)
1174  return false;
1175 
1176  auto *NewExitBB = SplitBlockPredecessors(
1177  BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA);
1178 
1179  if (!NewExitBB)
1180  LLVM_DEBUG(
1181  dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
1182  << *L << "\n");
1183  else
1184  LLVM_DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
1185  << NewExitBB->getName() << "\n");
1186  return true;
1187  };
1188 
1189  // Walk the exit blocks directly rather than building up a data structure for
1190  // them, but only visit each one once.
1192  for (auto *BB : L->blocks())
1193  for (auto *SuccBB : successors(BB)) {
1194  // We're looking for exit blocks so skip in-loop successors.
1195  if (L->contains(SuccBB))
1196  continue;
1197 
1198  // Visit each exit block exactly once.
1199  if (!Visited.insert(SuccBB).second)
1200  continue;
1201 
1202  Changed |= RewriteExit(SuccBB);
1203  }
1204 
1205  return Changed;
1206 }
1207 
1208 /// Returns the instructions that use values defined in the loop.
1210  SmallVector<Instruction *, 8> UsedOutside;
1211 
1212  for (auto *Block : L->getBlocks())
1213  // FIXME: I believe that this could use copy_if if the Inst reference could
1214  // be adapted into a pointer.
1215  for (auto &Inst : *Block) {
1216  auto Users = Inst.users();
1217  if (any_of(Users, [&](User *U) {
1218  auto *Use = cast<Instruction>(U);
1219  return !L->contains(Use->getParent());
1220  }))
1221  UsedOutside.push_back(&Inst);
1222  }
1223 
1224  return UsedOutside;
1225 }
1226 
1228  // By definition, all loop passes need the LoopInfo analysis and the
1229  // Dominator tree it depends on. Because they all participate in the loop
1230  // pass manager, they must also preserve these.
1235 
1236  // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
1237  // here because users shouldn't directly get them from this header.
1238  extern char &LoopSimplifyID;
1239  extern char &LCSSAID;
1240  AU.addRequiredID(LoopSimplifyID);
1241  AU.addPreservedID(LoopSimplifyID);
1242  AU.addRequiredID(LCSSAID);
1243  AU.addPreservedID(LCSSAID);
1244  // This is used in the LPPassManager to perform LCSSA verification on passes
1245  // which preserve lcssa form
1248 
1249  // Loop passes are designed to run inside of a loop pass manager which means
1250  // that any function analyses they require must be required by the first loop
1251  // pass in the manager (so that it is computed before the loop pass manager
1252  // runs) and preserved by all loop pasess in the manager. To make this
1253  // reasonably robust, the set needed for most loop passes is maintained here.
1254  // If your loop pass requires an analysis not listed here, you will need to
1255  // carefully audit the loop pass manager nesting structure that results.
1263 }
1264 
1265 /// Manually defined generic "LoopPass" dependency initialization. This is used
1266 /// to initialize the exact set of passes from above in \c
1267 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
1268 /// with:
1269 ///
1270 /// INITIALIZE_PASS_DEPENDENCY(LoopPass)
1271 ///
1272 /// As-if "LoopPass" were a pass.
1276  INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1277  INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
1283 }
1284 
1285 /// Find string metadata for loop
1286 ///
1287 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1288 /// operand or null otherwise. If the string metadata is not found return
1289 /// Optional's not-a-value.
1291  StringRef Name) {
1292  MDNode *LoopID = TheLoop->getLoopID();
1293  // Return none if LoopID is false.
1294  if (!LoopID)
1295  return None;
1296 
1297  // First operand should refer to the loop id itself.
1298  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1299  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1300 
1301  // Iterate over LoopID operands and look for MDString Metadata
1302  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1303  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1304  if (!MD)
1305  continue;
1306  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1307  if (!S)
1308  continue;
1309  // Return true if MDString holds expected MetaData.
1310  if (Name.equals(S->getString()))
1311  switch (MD->getNumOperands()) {
1312  case 1:
1313  return nullptr;
1314  case 2:
1315  return &MD->getOperand(1);
1316  default:
1317  llvm_unreachable("loop metadata has 0 or 1 operand");
1318  }
1319  }
1320  return None;
1321 }
1322 
1323 /// Does a BFS from a given node to all of its children inside a given loop.
1324 /// The returned vector of nodes includes the starting point.
1328  auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
1329  // Only include subregions in the top level loop.
1330  BasicBlock *BB = DTN->getBlock();
1331  if (CurLoop->contains(BB))
1332  Worklist.push_back(DTN);
1333  };
1334 
1335  AddRegionToWorklist(N);
1336 
1337  for (size_t I = 0; I < Worklist.size(); I++)
1338  for (DomTreeNode *Child : Worklist[I]->getChildren())
1339  AddRegionToWorklist(Child);
1340 
1341  return Worklist;
1342 }
1343 
1344 void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
1345  ScalarEvolution *SE = nullptr,
1346  LoopInfo *LI = nullptr) {
1347  assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
1348  auto *Preheader = L->getLoopPreheader();
1349  assert(Preheader && "Preheader should exist!");
1350 
1351  // Now that we know the removal is safe, remove the loop by changing the
1352  // branch from the preheader to go to the single exit block.
1353  //
1354  // Because we're deleting a large chunk of code at once, the sequence in which
1355  // we remove things is very important to avoid invalidation issues.
1356 
1357  // Tell ScalarEvolution that the loop is deleted. Do this before
1358  // deleting the loop so that ScalarEvolution can look at the loop
1359  // to determine what it needs to clean up.
1360  if (SE)
1361  SE->forgetLoop(L);
1362 
1363  auto *ExitBlock = L->getUniqueExitBlock();
1364  assert(ExitBlock && "Should have a unique exit block!");
1365  assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
1366 
1367  auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
1368  assert(OldBr && "Preheader must end with a branch");
1369  assert(OldBr->isUnconditional() && "Preheader must have a single successor");
1370  // Connect the preheader to the exit block. Keep the old edge to the header
1371  // around to perform the dominator tree update in two separate steps
1372  // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
1373  // preheader -> header.
1374  //
1375  //
1376  // 0. Preheader 1. Preheader 2. Preheader
1377  // | | | |
1378  // V | V |
1379  // Header <--\ | Header <--\ | Header <--\
1380  // | | | | | | | | | | |
1381  // | V | | | V | | | V |
1382  // | Body --/ | | Body --/ | | Body --/
1383  // V V V V V
1384  // Exit Exit Exit
1385  //
1386  // By doing this is two separate steps we can perform the dominator tree
1387  // update without using the batch update API.
1388  //
1389  // Even when the loop is never executed, we cannot remove the edge from the
1390  // source block to the exit block. Consider the case where the unexecuted loop
1391  // branches back to an outer loop. If we deleted the loop and removed the edge
1392  // coming to this inner loop, this will break the outer loop structure (by
1393  // deleting the backedge of the outer loop). If the outer loop is indeed a
1394  // non-loop, it will be deleted in a future iteration of loop deletion pass.
1395  IRBuilder<> Builder(OldBr);
1396  Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
1397  // Remove the old branch. The conditional branch becomes a new terminator.
1398  OldBr->eraseFromParent();
1399 
1400  // Rewrite phis in the exit block to get their inputs from the Preheader
1401  // instead of the exiting block.
1402  for (PHINode &P : ExitBlock->phis()) {
1403  // Set the zero'th element of Phi to be from the preheader and remove all
1404  // other incoming values. Given the loop has dedicated exits, all other
1405  // incoming values must be from the exiting blocks.
1406  int PredIndex = 0;
1407  P.setIncomingBlock(PredIndex, Preheader);
1408  // Removes all incoming values from all other exiting blocks (including
1409  // duplicate values from an exiting block).
1410  // Nuke all entries except the zero'th entry which is the preheader entry.
1411  // NOTE! We need to remove Incoming Values in the reverse order as done
1412  // below, to keep the indices valid for deletion (removeIncomingValues
1413  // updates getNumIncomingValues and shifts all values down into the operand
1414  // being deleted).
1415  for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i)
1416  P.removeIncomingValue(e - i, false);
1417 
1418  assert((P.getNumIncomingValues() == 1 &&
1419  P.getIncomingBlock(PredIndex) == Preheader) &&
1420  "Should have exactly one value and that's from the preheader!");
1421  }
1422 
1423  // Disconnect the loop body by branching directly to its exit.
1424  Builder.SetInsertPoint(Preheader->getTerminator());
1425  Builder.CreateBr(ExitBlock);
1426  // Remove the old branch.
1427  Preheader->getTerminator()->eraseFromParent();
1428 
1430  if (DT) {
1431  // Update the dominator tree by informing it about the new edge from the
1432  // preheader to the exit.
1433  DTU.insertEdge(Preheader, ExitBlock);
1434  // Inform the dominator tree about the removed edge.
1435  DTU.deleteEdge(Preheader, L->getHeader());
1436  }
1437 
1438  // Given LCSSA form is satisfied, we should not have users of instructions
1439  // within the dead loop outside of the loop. However, LCSSA doesn't take
1440  // unreachable uses into account. We handle them here.
1441  // We could do it after drop all references (in this case all users in the
1442  // loop will be already eliminated and we have less work to do but according
1443  // to API doc of User::dropAllReferences only valid operation after dropping
1444  // references, is deletion. So let's substitute all usages of
1445  // instruction from the loop with undef value of corresponding type first.
1446  for (auto *Block : L->blocks())
1447  for (Instruction &I : *Block) {
1448  auto *Undef = UndefValue::get(I.getType());
1449  for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
1450  Use &U = *UI;
1451  ++UI;
1452  if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
1453  if (L->contains(Usr->getParent()))
1454  continue;
1455  // If we have a DT then we can check that uses outside a loop only in
1456  // unreachable block.
1457  if (DT)
1458  assert(!DT->isReachableFromEntry(U) &&
1459  "Unexpected user in reachable block");
1460  U.set(Undef);
1461  }
1462  }
1463 
1464  // Remove the block from the reference counting scheme, so that we can
1465  // delete it freely later.
1466  for (auto *Block : L->blocks())
1467  Block->dropAllReferences();
1468 
1469  if (LI) {
1470  // Erase the instructions and the blocks without having to worry
1471  // about ordering because we already dropped the references.
1472  // NOTE: This iteration is safe because erasing the block does not remove
1473  // its entry from the loop's block list. We do that in the next section.
1474  for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
1475  LpI != LpE; ++LpI)
1476  (*LpI)->eraseFromParent();
1477 
1478  // Finally, the blocks from loopinfo. This has to happen late because
1479  // otherwise our loop iterators won't work.
1480 
1482  blocks.insert(L->block_begin(), L->block_end());
1483  for (BasicBlock *BB : blocks)
1484  LI->removeBlock(BB);
1485 
1486  // The last step is to update LoopInfo now that we've eliminated this loop.
1487  LI->erase(L);
1488  }
1489 }
1490 
1492  // Only support loops with a unique exiting block, and a latch.
1493  if (!L->getExitingBlock())
1494  return None;
1495 
1496  // Get the branch weights for the loop's backedge.
1497  BranchInst *LatchBR =
1499  if (!LatchBR || LatchBR->getNumSuccessors() != 2)
1500  return None;
1501 
1502  assert((LatchBR->getSuccessor(0) == L->getHeader() ||
1503  LatchBR->getSuccessor(1) == L->getHeader()) &&
1504  "At least one edge out of the latch must go to the header");
1505 
1506  // To estimate the number of times the loop body was executed, we want to
1507  // know the number of times the backedge was taken, vs. the number of times
1508  // we exited the loop.
1509  uint64_t TrueVal, FalseVal;
1510  if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
1511  return None;
1512 
1513  if (!TrueVal || !FalseVal)
1514  return 0;
1515 
1516  // Divide the count of the backedge by the count of the edge exiting the loop,
1517  // rounding to nearest.
1518  if (LatchBR->getSuccessor(0) == L->getHeader())
1519  return (TrueVal + (FalseVal / 2)) / FalseVal;
1520  else
1521  return (FalseVal + (TrueVal / 2)) / TrueVal;
1522 }
1523 
1525  ScalarEvolution &SE) {
1526  Loop *OuterL = InnerLoop->getParentLoop();
1527  if (!OuterL)
1528  return true;
1529 
1530  // Get the backedge taken count for the inner loop
1531  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1532  const SCEV *InnerLoopBECountSC = SE.getExitCount(InnerLoop, InnerLoopLatch);
1533  if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
1534  !InnerLoopBECountSC->getType()->isIntegerTy())
1535  return false;
1536 
1537  // Get whether count is invariant to the outer loop
1539  SE.getLoopDisposition(InnerLoopBECountSC, OuterL);
1541  return false;
1542 
1543  return true;
1544 }
1545 
1546 /// Adds a 'fast' flag to floating point operations.
1548  if (isa<FPMathOperator>(V)) {
1549  FastMathFlags Flags;
1550  Flags.setFast();
1551  cast<Instruction>(V)->setFastMathFlags(Flags);
1552  }
1553  return V;
1554 }
1555 
1556 // Helper to generate an ordered reduction.
1557 Value *
1559  unsigned Op,
1561  ArrayRef<Value *> RedOps) {
1562  unsigned VF = Src->getType()->getVectorNumElements();
1563 
1564  // Extract and apply reduction ops in ascending order:
1565  // e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
1566  Value *Result = Acc;
1567  for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
1568  Value *Ext =
1569  Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));
1570 
1571  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1572  Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
1573  "bin.rdx");
1574  } else {
1575  assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
1576  "Invalid min/max");
1577  Result = RecurrenceDescriptor::createMinMaxOp(Builder, MinMaxKind, Result,
1578  Ext);
1579  }
1580 
1581  if (!RedOps.empty())
1582  propagateIRFlags(Result, RedOps);
1583  }
1584 
1585  return Result;
1586 }
1587 
1588 // Helper to generate a log2 shuffle reduction.
1589 Value *
1592  ArrayRef<Value *> RedOps) {
1593  unsigned VF = Src->getType()->getVectorNumElements();
1594  // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
1595  // and vector ops, reducing the set of values being computed by half each
1596  // round.
1597  assert(isPowerOf2_32(VF) &&
1598  "Reduction emission only supported for pow2 vectors!");
1599  Value *TmpVec = Src;
1600  SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
1601  for (unsigned i = VF; i != 1; i >>= 1) {
1602  // Move the upper half of the vector to the lower half.
1603  for (unsigned j = 0; j != i / 2; ++j)
1604  ShuffleMask[j] = Builder.getInt32(i / 2 + j);
1605 
1606  // Fill the rest of the mask with undef.
1607  std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
1608  UndefValue::get(Builder.getInt32Ty()));
1609 
1610  Value *Shuf = Builder.CreateShuffleVector(
1611  TmpVec, UndefValue::get(TmpVec->getType()),
1612  ConstantVector::get(ShuffleMask), "rdx.shuf");
1613 
1614  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1615  // Floating point operations had to be 'fast' to enable the reduction.
1616  TmpVec = addFastMathFlag(Builder.CreateBinOp((Instruction::BinaryOps)Op,
1617  TmpVec, Shuf, "bin.rdx"));
1618  } else {
1619  assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&
1620  "Invalid min/max");
1621  TmpVec = RecurrenceDescriptor::createMinMaxOp(Builder, MinMaxKind, TmpVec,
1622  Shuf);
1623  }
1624  if (!RedOps.empty())
1625  propagateIRFlags(TmpVec, RedOps);
1626  }
1627  // The result is in the first element of the vector.
1628  return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
1629 }
1630 
1631 /// Create a simple vector reduction specified by an opcode and some
1632 /// flags (if generating min/max reductions).
1634  IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
1636  ArrayRef<Value *> RedOps) {
1637  assert(isa<VectorType>(Src->getType()) && "Type must be a vector");
1638 
1639  Value *ScalarUdf = UndefValue::get(Src->getType()->getVectorElementType());
1640  std::function<Value*()> BuildFunc;
1641  using RD = RecurrenceDescriptor;
1642  RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
1643  // TODO: Support creating ordered reductions.
1644  FastMathFlags FMFFast;
1645  FMFFast.setFast();
1646 
1647  switch (Opcode) {
1648  case Instruction::Add:
1649  BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
1650  break;
1651  case Instruction::Mul:
1652  BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
1653  break;
1654  case Instruction::And:
1655  BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
1656  break;
1657  case Instruction::Or:
1658  BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
1659  break;
1660  case Instruction::Xor:
1661  BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
1662  break;
1663  case Instruction::FAdd:
1664  BuildFunc = [&]() {
1665  auto Rdx = Builder.CreateFAddReduce(ScalarUdf, Src);
1666  cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
1667  return Rdx;
1668  };
1669  break;
1670  case Instruction::FMul:
1671  BuildFunc = [&]() {
1672  auto Rdx = Builder.CreateFMulReduce(ScalarUdf, Src);
1673  cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
1674  return Rdx;
1675  };
1676  break;
1677  case Instruction::ICmp:
1678  if (Flags.IsMaxOp) {
1679  MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
1680  BuildFunc = [&]() {
1681  return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
1682  };
1683  } else {
1684  MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
1685  BuildFunc = [&]() {
1686  return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
1687  };
1688  }
1689  break;
1690  case Instruction::FCmp:
1691  if (Flags.IsMaxOp) {
1692  MinMaxKind = RD::MRK_FloatMax;
1693  BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
1694  } else {
1695  MinMaxKind = RD::MRK_FloatMin;
1696  BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
1697  }
1698  break;
1699  default:
1700  llvm_unreachable("Unhandled opcode");
1701  break;
1702  }
1703  if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
1704  return BuildFunc();
1705  return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
1706 }
1707 
1708 /// Create a vector reduction using a given recurrence descriptor.
1710  const TargetTransformInfo *TTI,
1711  RecurrenceDescriptor &Desc, Value *Src,
1712  bool NoNaN) {
1713  // TODO: Support in-order reductions based on the recurrence descriptor.
1714  using RD = RecurrenceDescriptor;
1715  RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
1717  Flags.NoNaN = NoNaN;
1718  switch (RecKind) {
1719  case RD::RK_FloatAdd:
1720  return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
1721  case RD::RK_FloatMult:
1722  return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
1723  case RD::RK_IntegerAdd:
1724  return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
1725  case RD::RK_IntegerMult:
1726  return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
1727  case RD::RK_IntegerAnd:
1728  return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
1729  case RD::RK_IntegerOr:
1730  return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
1731  case RD::RK_IntegerXor:
1732  return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
1733  case RD::RK_IntegerMinMax: {
1734  RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
1735  Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_UIntMax);
1736  Flags.IsSigned = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_SIntMin);
1737  return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
1738  }
1739  case RD::RK_FloatMinMax: {
1740  Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
1741  return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
1742  }
1743  default:
1744  llvm_unreachable("Unhandled RecKind");
1745  }
1746 }
1747 
1749  auto *VecOp = dyn_cast<Instruction>(I);
1750  if (!VecOp)
1751  return;
1752  auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
1753  : dyn_cast<Instruction>(OpValue);
1754  if (!Intersection)
1755  return;
1756  const unsigned Opcode = Intersection->getOpcode();
1757  VecOp->copyIRFlags(Intersection);
1758  for (auto *V : VL) {
1759  auto *Instr = dyn_cast<Instruction>(V);
1760  if (!Instr)
1761  continue;
1762  if (OpValue == nullptr || Opcode == Instr->getOpcode())
1763  VecOp->andIRFlags(V);
1764  }
1765 }
Legacy wrapper pass to provide the GlobalsAAResult object.
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
Type * getVectorElementType() const
Definition: Type.h:371
const NoneType None
Definition: None.h:24
static bool isArithmeticRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is an arithmetic kind.
Definition: LoopUtils.cpp:72
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:172
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:72
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1846
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:225
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1246
static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D)
Returns true if Phi is a floating point induction in the loop L.
Definition: LoopUtils.cpp:874
void setFast(bool B=true)
Definition: Operator.h:231
InductionDescriptor()=default
Default constructor - creates an invalid induction.
const SCEV * getConstant(ConstantInt *V)
static Instruction * lookThroughAnd(PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction *> &Visited, SmallPtrSetImpl< Instruction *> &CI)
Determines if Phi may have been type-promoted.
Definition: LoopUtils.cpp:89
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:555
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.
Definition: LoopUtils.cpp:1077
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.
Definition: LoopUtils.cpp:793
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:86
ConstantInt * getConstIntStepValue() const
Definition: LoopUtils.cpp:800
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:176
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.
Definition: LoopUtils.cpp:192
The main scalar evolution driver.
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:45
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:174
unsigned less than
Definition: InstrTypes.h:910
A cache of @llvm.assume calls within a function.
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:891
Value * createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, unsigned Opcode, Value *Src, TargetTransformInfo::ReductionFlags Flags=TargetTransformInfo::ReductionFlags(), ArrayRef< Value *> RedOps=None)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1633
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:714
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
BasicBlock * getSuccessor(unsigned i) const
MinMaxRecurrenceKind getMinMaxRecurrenceKind()
Definition: LoopUtils.h:200
Metadata node.
Definition: Metadata.h:862
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
Value * getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=None)
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:1590
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.
iv Induction Variable Users
Definition: IVUsers.cpp:52
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;...
Definition: LoopUtils.cpp:496
op_iterator op_begin()
Definition: User.h:230
static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction *> &Insts)
Returns true if instruction I has multiple uses in Insts.
Definition: LoopUtils.cpp:534
IntegerType * getInt32Ty()
Fetch the type representing a 32-bit integer.
Definition: IRBuilder.h:347
The SCEV is loop-invariant.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
This is the interface for a SCEV-based alias analysis.
void initializeLoopPassPass(PassRegistry &)
Manually defined generic "LoopPass" dependency initialization.
Definition: LoopUtils.cpp:1273
This class represents the LLVM &#39;select&#39; instruction.
Type * getPointerElementType() const
Definition: Type.h:376
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
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
unsigned getNumSuccessors() const
CallInst * CreateFAddReduce(Value *Acc, Value *Src)
Create a vector fadd reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:321
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:731
static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction *> &Set)
Returns true if all uses of the instruction I is within the Set.
Definition: LoopUtils.cpp:45
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).
Definition: LoopUtils.cpp:447
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:962
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 ...
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:1209
BlockT * getHeader() const
Definition: LoopInfo.h:100
CallInst * CreateFPMinReduce(Value *Src, bool NoNaN=false)
Create a vector float min reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:389
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI)
This function deletes dead loops.
Definition: LoopUtils.cpp:1344
Value * getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind=RecurrenceDescriptor::MRK_Invalid, ArrayRef< Value *> RedOps=None)
Generates an ordered vector reduction using extracts to reduce the value.
Definition: LoopUtils.cpp:1558
ConstantInt * getValue() const
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:201
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
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.
void andIRFlags(const Value *V)
Logical &#39;and&#39; of any supported wrapping, exact, and fast-math flags of V and this instruction...
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.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
AnalysisUsage & addPreservedID(const void *ID)
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:979
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:209
This POD struct holds information about a potential recurrence operation.
Definition: LoopUtils.h:102
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:142
Value * getOperand(unsigned i) const
Definition: User.h:170
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
use_iterator_impl< Use > use_iterator
Definition: Value.h:332
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 ...
Definition: LoopUtils.cpp:163
CallInst * CreateXorReduce(Value *Src)
Create a vector int XOR reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:361
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:96
StringRef getString() const
Definition: Metadata.cpp:464
static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE, const SCEVUnknown *PhiScev, const SCEVAddRecExpr *AR, SmallVectorImpl< Instruction *> &CastInsts)
This function is called when we suspect that the update-chain of a phi node (whose symbolic SCEV expr...
Definition: LoopUtils.cpp:959
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1854
bool isFloatTy() const
Return true if this is &#39;float&#39;, a 32-bit IEEE fp type.
Definition: Type.h:147
#define P(N)
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Value * CreateFMul(Value *L, Value *R, const Twine &Name="", MDNode *FPMD=nullptr)
Definition: IRBuilder.h:1195
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:177
void set(Value *Val)
Definition: Value.h:671
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:429
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Flags describing the kind of vector reduction.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.h:1901
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.
char & LCSSAID
Definition: LCSSA.cpp:424
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:371
const SCEV * getAddExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
Represent the analysis usage information of a pass.
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:434
op_iterator op_end()
Definition: User.h:232
bool isFast() const
Determine whether all fast-math-flags are set.
bool any_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1025
bool isHalfTy() const
Return true if this is &#39;half&#39;, a 16-bit IEEE fp type.
Definition: Type.h:144
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:885
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
op_range operands()
Definition: User.h:238
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
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:382
Optional< unsigned > getLoopEstimatedTripCount(Loop *L)
Get a loop&#39;s estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:1491
static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Returns true if Phi is a reduction in TheLoop.
Definition: LoopUtils.cpp:547
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:1921
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1392
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:640
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:145
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
size_t size() const
Definition: SmallVector.h:53
bool IsMaxOp
If the op a min/max kind, true if it&#39;s a max operation.
RecurrenceKind getRecurrenceKind()
Definition: LoopUtils.h:198
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Optional< const MDOperand * > findStringMetadataForLoop(Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopUtils.cpp:1290
static unsigned getRecurrenceBinOp(RecurrenceKind Kind)
Returns the opcode of binary operation corresponding to the RecurrenceKind.
Definition: LoopUtils.cpp:687
const SCEV * getMulExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
void deleteEdge(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge deletion.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void propagateIRFlags(Value *I, ArrayRef< Value *> VL, Value *OpValue=nullptr)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
Definition: LoopUtils.cpp:1748
static bool isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, DenseMap< Instruction *, Instruction *> &SinkAfter, DominatorTree *DT)
Returns true if Phi is a first-order recurrence.
Definition: LoopUtils.cpp:607
signed greater than
Definition: InstrTypes.h:912
char & LoopSimplifyID
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: LoopUtils.h:64
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1374
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:889
Value * transform(IRBuilder<> &B, Value *Index, ScalarEvolution *SE, const DataLayout &DL) const
Compute the transformed value of Index at offset StartValue using step StepValue. ...
Definition: LoopUtils.cpp:806
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:240
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
void insertEdge(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge insertion.
bool hasInvariantIterationCount(Loop *L, ScalarEvolution &SE)
Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop...
Definition: LoopUtils.cpp:1524
MinMaxRecurrenceKind getMinMaxKind()
Definition: LoopUtils.h:118
CallInst * CreateAddReduce(Value *Src)
Create a vector int add reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:341
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
Legacy wrapper pass to provide the SCEVAAResult object.
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
Type * getType() const
Return the LLVM type of this SCEV expression.
A struct for saving information about induction variables.
Definition: LoopUtils.h:254
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return the number of times the sign bit of the register is replicated into the other bits...
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
CallInst * CreateIntMaxReduce(Value *Src, bool IsSigned=false)
Create a vector integer max reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:366
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:299
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:244
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:64
static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is a floating point kind.
Definition: LoopUtils.cpp:68
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
signed less than
Definition: InstrTypes.h:914
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:307
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:180
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:1948
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
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:113
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
CallInst * CreateFMulReduce(Value *Acc, Value *Src)
Create a vector fmul reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:331
unsigned getNumIncomingValues() const
Return the number of incoming edges.
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
bool isCommutative() const
Return true if the instruction is commutative:
Definition: Instruction.h:457
Value * createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, RecurrenceDescriptor &Desc, Value *Src, bool NoNaN=false)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
Definition: LoopUtils.cpp:1709
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
static Constant * getRecurrenceIdentity(RecurrenceKind K, Type *Tp)
Returns identity corresponding to the RecurrenceKind.
Definition: LoopUtils.cpp:661
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
Class for arbitrary precision integers.
Definition: APInt.h:70
iterator_range< user_iterator > users()
Definition: Value.h:400
static Value * createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:712
This class uses information about analyze scalars to rewrite expressions in canonical form...
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:169
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:394
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:560
uint64_t getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:428
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
use_iterator use_begin()
Definition: Value.h:339
CallInst * CreateAndReduce(Value *Src)
Create a vector int AND reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:351
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:546
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:214
static MachineInstr * getDef(unsigned Reg, const MachineRegisterInfo *MRI)
CallInst * CreateOrReduce(Value *Src)
Create a vector int OR reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:356
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
CallInst * CreateIntMinReduce(Value *Src, bool IsSigned=false)
Create a vector integer min reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:372
This class represents an analyzed expression in the program.
static bool isIntegerRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is an integer kind.
Definition: LoopUtils.cpp:53
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
StringRef getValueAsString() const
Return the attribute&#39;s value as a string.
Definition: Attributes.cpp:195
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:149
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:108
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:1227
CallInst * CreateMulReduce(Value *Src)
Create a vector int mul reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:346
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:323
block_iterator block_end() const
Definition: LoopInfo.h:155
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:141
SmallVector< DomTreeNode *, 16 > collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop)
Does a BFS from a given node to all of its children inside a given loop.
Definition: LoopUtils.cpp:1326
const unsigned Kind
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:376
static std::pair< Type *, bool > computeRecurrenceType(Instruction *Exit, DemandedBits *DB, AssumptionCache *AC, DominatorTree *DT)
Compute the minimal bit width needed to represent a reduction whose exit instruction is given by Exit...
Definition: LoopUtils.cpp:114
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:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:149
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool useReductionIntrinsic(unsigned Opcode, Type *Ty, ReductionFlags Flags) const
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
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:81
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition: IRBuilder.h:220
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:122
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
Definition: Function.h:317
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:1144
const SCEV * getUnknown(Value *V)
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:413
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:160
unsigned greater than
Definition: InstrTypes.h:908
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
A single uniqued string.
Definition: Metadata.h:602
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
const SCEV * getExitCount(const Loop *L, BasicBlock *ExitingBlock)
Get the expression for the number of loop iterations for which this loop is guaranteed not to exit vi...
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:254
This pass exposes codegen information to IR-level passes.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
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:157
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
CallInst * CreateFPMaxReduce(Value *Src, bool NoNaN=false)
Create a vector float max reduction intrinsic of the source vector.
Definition: IRBuilder.cpp:378
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
#define LLVM_DEBUG(X)
Definition: Debug.h:119
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
Definition: Metadata.cpp:1315
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
bool isDoubleTy() const
Return true if this is &#39;double&#39;, a 64-bit IEEE fp type.
Definition: Type.h:150
static Value * addFastMathFlag(Value *V)
Adds a &#39;fast&#39; flag to floating point operations.
Definition: LoopUtils.cpp:1547
block_iterator block_begin() const
Definition: LoopInfo.h:154
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:50
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)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool NoNaN
If op is an fp min/max, whether NaNs may be present.
bool use_empty() const
Definition: Value.h:323
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1056
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:476
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144
RecurrenceKind
This enum represents the kinds of recurrences that we support.
Definition: LoopUtils.h:67
const BasicBlock * getParent() const
Definition: Instruction.h:67
This class represents a constant integer value.
Legacy wrapper pass to provide the BasicAAResult object.
bool IsSigned
Whether the operation is a signed int reduction.
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:1077