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
14#include "llvm/Analysis/AliasAnalysis.h"
15#include "llvm/Analysis/BasicAliasAnalysis.h"
16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/Analysis/GlobalsModRef.h"
18#include "llvm/Analysis/ScalarEvolution.h"
19#include "llvm/Analysis/ScalarEvolutionExpander.h"
20#include "llvm/Analysis/ScalarEvolutionExpressions.h"
21#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
22#include "llvm/IR/Dominators.h"
23#include "llvm/IR/Instructions.h"
24#include "llvm/IR/Module.h"
25#include "llvm/IR/PatternMatch.h"
26#include "llvm/IR/ValueHandle.h"
27#include "llvm/Pass.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Transforms/Utils/LoopUtils.h"
30
31using namespace llvm;
32using namespace llvm::PatternMatch;
33
34#define DEBUG_TYPE "loop-utils"
35
36bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
37                                        SmallPtrSetImpl<Instruction *> &Set) {
38  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
39    if (!Set.count(dyn_cast<Instruction>(*Use)))
40      return false;
41  return true;
42}
43
44bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
45  switch (Kind) {
46  default:
47    break;
48  case RK_IntegerAdd:
49  case RK_IntegerMult:
50  case RK_IntegerOr:
51  case RK_IntegerAnd:
52  case RK_IntegerXor:
53  case RK_IntegerMinMax:
54    return true;
55  }
56  return false;
57}
58
59bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
60  return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
61}
62
63bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
64  switch (Kind) {
65  default:
66    break;
67  case RK_IntegerAdd:
68  case RK_IntegerMult:
69  case RK_FloatAdd:
70  case RK_FloatMult:
71    return true;
72  }
73  return false;
74}
75
76Instruction *
77RecurrenceDescriptor::lookThroughAnd(PHINode *Phi, Type *&RT,
78                                     SmallPtrSetImpl<Instruction *> &Visited,
79                                     SmallPtrSetImpl<Instruction *> &CI) {
80  if (!Phi->hasOneUse())
81    return Phi;
82
83  const APInt *M = nullptr;
84  Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
85
86  // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
87  // with a new integer type of the corresponding bit width.
88  if (match(J, m_CombineOr(m_And(m_Instruction(I), m_APInt(M)),
89                           m_And(m_APInt(M), m_Instruction(I))))) {
90    int32_t Bits = (*M + 1).exactLogBase2();
91    if (Bits > 0) {
92      RT = IntegerType::get(Phi->getContext(), Bits);
93      Visited.insert(Phi);
94      CI.insert(J);
95      return J;
96    }
97  }
98  return Phi;
99}
100
101bool RecurrenceDescriptor::getSourceExtensionKind(
102    Instruction *Start, Instruction *Exit, Type *RT, bool &IsSigned,
103    SmallPtrSetImpl<Instruction *> &Visited,
104    SmallPtrSetImpl<Instruction *> &CI) {
105
106  SmallVector<Instruction *, 8> Worklist;
107  bool FoundOneOperand = false;
108  unsigned DstSize = RT->getPrimitiveSizeInBits();
109  Worklist.push_back(Exit);
110
111  // Traverse the instructions in the reduction expression, beginning with the
112  // exit value.
113  while (!Worklist.empty()) {
114    Instruction *I = Worklist.pop_back_val();
115    for (Use &U : I->operands()) {
116
117      // Terminate the traversal if the operand is not an instruction, or we
118      // reach the starting value.
119      Instruction *J = dyn_cast<Instruction>(U.get());
120      if (!J || J == Start)
121        continue;
122
123      // Otherwise, investigate the operation if it is also in the expression.
124      if (Visited.count(J)) {
125        Worklist.push_back(J);
126        continue;
127      }
128
129      // If the operand is not in Visited, it is not a reduction operation, but
130      // it does feed into one. Make sure it is either a single-use sign- or
131      // zero-extend instruction.
132      CastInst *Cast = dyn_cast<CastInst>(J);
133      bool IsSExtInst = isa<SExtInst>(J);
134      if (!Cast || !Cast->hasOneUse() || !(isa<ZExtInst>(J) || IsSExtInst))
135        return false;
136
137      // Ensure the source type of the extend is no larger than the reduction
138      // type. It is not necessary for the types to be identical.
139      unsigned SrcSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
140      if (SrcSize > DstSize)
141        return false;
142
143      // Furthermore, ensure that all such extends are of the same kind.
144      if (FoundOneOperand) {
145        if (IsSigned != IsSExtInst)
146          return false;
147      } else {
148        FoundOneOperand = true;
149        IsSigned = IsSExtInst;
150      }
151
152      // Lastly, if the source type of the extend matches the reduction type,
153      // add the extend to CI so that we can avoid accounting for it in the
154      // cost model.
155      if (SrcSize == DstSize)
156        CI.insert(Cast);
157    }
158  }
159  return true;
160}
161
162bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
163                                           Loop *TheLoop, bool HasFunNoNaNAttr,
164                                           RecurrenceDescriptor &RedDes) {
165  if (Phi->getNumIncomingValues() != 2)
166    return false;
167
168  // Reduction variables are only found in the loop header block.
169  if (Phi->getParent() != TheLoop->getHeader())
170    return false;
171
172  // Obtain the reduction start value from the value that comes from the loop
173  // preheader.
174  Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
175
176  // ExitInstruction is the single value which is used outside the loop.
177  // We only allow for a single reduction value to be used outside the loop.
178  // This includes users of the reduction, variables (which form a cycle
179  // which ends in the phi node).
180  Instruction *ExitInstruction = nullptr;
181  // Indicates that we found a reduction operation in our scan.
182  bool FoundReduxOp = false;
183
184  // We start with the PHI node and scan for all of the users of this
185  // instruction. All users must be instructions that can be used as reduction
186  // variables (such as ADD). We must have a single out-of-block user. The cycle
187  // must include the original PHI.
188  bool FoundStartPHI = false;
189
190  // To recognize min/max patterns formed by a icmp select sequence, we store
191  // the number of instruction we saw from the recognized min/max pattern,
192  //  to make sure we only see exactly the two instructions.
193  unsigned NumCmpSelectPatternInst = 0;
194  InstDesc ReduxDesc(false, nullptr);
195
196  // Data used for determining if the recurrence has been type-promoted.
197  Type *RecurrenceType = Phi->getType();
198  SmallPtrSet<Instruction *, 4> CastInsts;
199  Instruction *Start = Phi;
200  bool IsSigned = false;
201
202  SmallPtrSet<Instruction *, 8> VisitedInsts;
203  SmallVector<Instruction *, 8> Worklist;
204
205  // Return early if the recurrence kind does not match the type of Phi. If the
206  // recurrence kind is arithmetic, we attempt to look through AND operations
207  // resulting from the type promotion performed by InstCombine.  Vector
208  // operations are not limited to the legal integer widths, so we may be able
209  // to evaluate the reduction in the narrower width.
210  if (RecurrenceType->isFloatingPointTy()) {
211    if (!isFloatingPointRecurrenceKind(Kind))
212      return false;
213  } else {
214    if (!isIntegerRecurrenceKind(Kind))
215      return false;
216    if (isArithmeticRecurrenceKind(Kind))
217      Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
218  }
219
220  Worklist.push_back(Start);
221  VisitedInsts.insert(Start);
222
223  // A value in the reduction can be used:
224  //  - By the reduction:
225  //      - Reduction operation:
226  //        - One use of reduction value (safe).
227  //        - Multiple use of reduction value (not safe).
228  //      - PHI:
229  //        - All uses of the PHI must be the reduction (safe).
230  //        - Otherwise, not safe.
231  //  - By one instruction outside of the loop (safe).
232  //  - By further instructions outside of the loop (not safe).
233  //  - By an instruction that is not part of the reduction (not safe).
234  //    This is either:
235  //      * An instruction type other than PHI or the reduction operation.
236  //      * A PHI in the header other than the initial PHI.
237  while (!Worklist.empty()) {
238    Instruction *Cur = Worklist.back();
239    Worklist.pop_back();
240
241    // No Users.
242    // If the instruction has no users then this is a broken chain and can't be
243    // a reduction variable.
244    if (Cur->use_empty())
245      return false;
246
247    bool IsAPhi = isa<PHINode>(Cur);
248
249    // A header PHI use other than the original PHI.
250    if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
251      return false;
252
253    // Reductions of instructions such as Div, and Sub is only possible if the
254    // LHS is the reduction variable.
255    if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
256        !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
257        !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
258      return false;
259
260    // Any reduction instruction must be of one of the allowed kinds. We ignore
261    // the starting value (the Phi or an AND instruction if the Phi has been
262    // type-promoted).
263    if (Cur != Start) {
264      ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
265      if (!ReduxDesc.isRecurrence())
266        return false;
267    }
268
269    // A reduction operation must only have one use of the reduction value.
270    if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
271        hasMultipleUsesOf(Cur, VisitedInsts))
272      return false;
273
274    // All inputs to a PHI node must be a reduction value.
275    if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
276      return false;
277
278    if (Kind == RK_IntegerMinMax &&
279        (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
280      ++NumCmpSelectPatternInst;
281    if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
282      ++NumCmpSelectPatternInst;
283
284    // Check  whether we found a reduction operator.
285    FoundReduxOp |= !IsAPhi && Cur != Start;
286
287    // Process users of current instruction. Push non-PHI nodes after PHI nodes
288    // onto the stack. This way we are going to have seen all inputs to PHI
289    // nodes once we get to them.
290    SmallVector<Instruction *, 8> NonPHIs;
291    SmallVector<Instruction *, 8> PHIs;
292    for (User *U : Cur->users()) {
293      Instruction *UI = cast<Instruction>(U);
294
295      // Check if we found the exit user.
296      BasicBlock *Parent = UI->getParent();
297      if (!TheLoop->contains(Parent)) {
298        // Exit if you find multiple outside users or if the header phi node is
299        // being used. In this case the user uses the value of the previous
300        // iteration, in which case we would loose "VF-1" iterations of the
301        // reduction operation if we vectorize.
302        if (ExitInstruction != nullptr || Cur == Phi)
303          return false;
304
305        // The instruction used by an outside user must be the last instruction
306        // before we feed back to the reduction phi. Otherwise, we loose VF-1
307        // operations on the value.
308        if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end())
309          return false;
310
311        ExitInstruction = Cur;
312        continue;
313      }
314
315      // Process instructions only once (termination). Each reduction cycle
316      // value must only be used once, except by phi nodes and min/max
317      // reductions which are represented as a cmp followed by a select.
318      InstDesc IgnoredVal(false, nullptr);
319      if (VisitedInsts.insert(UI).second) {
320        if (isa<PHINode>(UI))
321          PHIs.push_back(UI);
322        else
323          NonPHIs.push_back(UI);
324      } else if (!isa<PHINode>(UI) &&
325                 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
326                   !isa<SelectInst>(UI)) ||
327                  !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
328        return false;
329
330      // Remember that we completed the cycle.
331      if (UI == Phi)
332        FoundStartPHI = true;
333    }
334    Worklist.append(PHIs.begin(), PHIs.end());
335    Worklist.append(NonPHIs.begin(), NonPHIs.end());
336  }
337
338  // This means we have seen one but not the other instruction of the
339  // pattern or more than just a select and cmp.
340  if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
341      NumCmpSelectPatternInst != 2)
342    return false;
343
344  if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
345    return false;
346
347  // If we think Phi may have been type-promoted, we also need to ensure that
348  // all source operands of the reduction are either SExtInsts or ZEstInsts. If
349  // so, we will be able to evaluate the reduction in the narrower bit width.
350  if (Start != Phi)
351    if (!getSourceExtensionKind(Start, ExitInstruction, RecurrenceType,
352                                IsSigned, VisitedInsts, CastInsts))
353      return false;
354
355  // We found a reduction var if we have reached the original phi node and we
356  // only have a single instruction with out-of-loop users.
357
358  // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
359  // is saved as part of the RecurrenceDescriptor.
360
361  // Save the description of this reduction variable.
362  RecurrenceDescriptor RD(
363      RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
364      ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
365  RedDes = RD;
366
367  return true;
368}
369
370/// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
371/// pattern corresponding to a min(X, Y) or max(X, Y).
372RecurrenceDescriptor::InstDesc
373RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
374
375  assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
376         "Expect a select instruction");
377  Instruction *Cmp = nullptr;
378  SelectInst *Select = nullptr;
379
380  // We must handle the select(cmp()) as a single instruction. Advance to the
381  // select.
382  if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
383    if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
384      return InstDesc(false, I);
385    return InstDesc(Select, Prev.getMinMaxKind());
386  }
387
388  // Only handle single use cases for now.
389  if (!(Select = dyn_cast<SelectInst>(I)))
390    return InstDesc(false, I);
391  if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
392      !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
393    return InstDesc(false, I);
394  if (!Cmp->hasOneUse())
395    return InstDesc(false, I);
396
397  Value *CmpLeft;
398  Value *CmpRight;
399
400  // Look for a min/max pattern.
401  if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
402    return InstDesc(Select, MRK_UIntMin);
403  else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
404    return InstDesc(Select, MRK_UIntMax);
405  else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
406    return InstDesc(Select, MRK_SIntMax);
407  else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
408    return InstDesc(Select, MRK_SIntMin);
409  else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
410    return InstDesc(Select, MRK_FloatMin);
411  else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
412    return InstDesc(Select, MRK_FloatMax);
413  else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
414    return InstDesc(Select, MRK_FloatMin);
415  else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
416    return InstDesc(Select, MRK_FloatMax);
417
418  return InstDesc(false, I);
419}
420
421RecurrenceDescriptor::InstDesc
422RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
423                                        InstDesc &Prev, bool HasFunNoNaNAttr) {
424  bool FP = I->getType()->isFloatingPointTy();
425  Instruction *UAI = Prev.getUnsafeAlgebraInst();
426  if (!UAI && FP && !I->hasUnsafeAlgebra())
427    UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
428
429  switch (I->getOpcode()) {
430  default:
431    return InstDesc(false, I);
432  case Instruction::PHI:
433    return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
434  case Instruction::Sub:
435  case Instruction::Add:
436    return InstDesc(Kind == RK_IntegerAdd, I);
437  case Instruction::Mul:
438    return InstDesc(Kind == RK_IntegerMult, I);
439  case Instruction::And:
440    return InstDesc(Kind == RK_IntegerAnd, I);
441  case Instruction::Or:
442    return InstDesc(Kind == RK_IntegerOr, I);
443  case Instruction::Xor:
444    return InstDesc(Kind == RK_IntegerXor, I);
445  case Instruction::FMul:
446    return InstDesc(Kind == RK_FloatMult, I, UAI);
447  case Instruction::FSub:
448  case Instruction::FAdd:
449    return InstDesc(Kind == RK_FloatAdd, I, UAI);
450  case Instruction::FCmp:
451  case Instruction::ICmp:
452  case Instruction::Select:
453    if (Kind != RK_IntegerMinMax &&
454        (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
455      return InstDesc(false, I);
456    return isMinMaxSelectCmpPattern(I, Prev);
457  }
458}
459
460bool RecurrenceDescriptor::hasMultipleUsesOf(
461    Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
462  unsigned NumUses = 0;
463  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
464       ++Use) {
465    if (Insts.count(dyn_cast<Instruction>(*Use)))
466      ++NumUses;
467    if (NumUses > 1)
468      return true;
469  }
470
471  return false;
472}
473bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
474                                          RecurrenceDescriptor &RedDes) {
475
476  BasicBlock *Header = TheLoop->getHeader();
477  Function &F = *Header->getParent();
478  bool HasFunNoNaNAttr =
479      F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
480
481  if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
482    DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
483    return true;
484  }
485  if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
486    DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
487    return true;
488  }
489  if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
490    DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
491    return true;
492  }
493  if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
494    DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
495    return true;
496  }
497  if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
498    DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
499    return true;
500  }
501  if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
502                      RedDes)) {
503    DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
504    return true;
505  }
506  if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
507    DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
508    return true;
509  }
510  if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
511    DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
512    return true;
513  }
514  if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
515    DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
516    return true;
517  }
518  // Not a reduction of known type.
519  return false;
520}
521
522bool RecurrenceDescriptor::isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
523                                                  DominatorTree *DT) {
524
525  // Ensure the phi node is in the loop header and has two incoming values.
526  if (Phi->getParent() != TheLoop->getHeader() ||
527      Phi->getNumIncomingValues() != 2)
528    return false;
529
530  // Ensure the loop has a preheader and a single latch block. The loop
531  // vectorizer will need the latch to set up the next iteration of the loop.
532  auto *Preheader = TheLoop->getLoopPreheader();
533  auto *Latch = TheLoop->getLoopLatch();
534  if (!Preheader || !Latch)
535    return false;
536
537  // Ensure the phi node's incoming blocks are the loop preheader and latch.
538  if (Phi->getBasicBlockIndex(Preheader) < 0 ||
539      Phi->getBasicBlockIndex(Latch) < 0)
540    return false;
541
542  // Get the previous value. The previous value comes from the latch edge while
543  // the initial value comes form the preheader edge.
544  auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
545  if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous))
546    return false;
547
548  // Ensure every user of the phi node is dominated by the previous value. The
549  // dominance requirement ensures the loop vectorizer will not need to
550  // vectorize the initial value prior to the first iteration of the loop.
551  for (User *U : Phi->users())
552    if (auto *I = dyn_cast<Instruction>(U))
553      if (!DT->dominates(Previous, I))
554        return false;
555
556  return true;
557}
558
559/// This function returns the identity element (or neutral element) for
560/// the operation K.
561Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
562                                                      Type *Tp) {
563  switch (K) {
564  case RK_IntegerXor:
565  case RK_IntegerAdd:
566  case RK_IntegerOr:
567    // Adding, Xoring, Oring zero to a number does not change it.
568    return ConstantInt::get(Tp, 0);
569  case RK_IntegerMult:
570    // Multiplying a number by 1 does not change it.
571    return ConstantInt::get(Tp, 1);
572  case RK_IntegerAnd:
573    // AND-ing a number with an all-1 value does not change it.
574    return ConstantInt::get(Tp, -1, true);
575  case RK_FloatMult:
576    // Multiplying a number by 1 does not change it.
577    return ConstantFP::get(Tp, 1.0L);
578  case RK_FloatAdd:
579    // Adding zero to a number does not change it.
580    return ConstantFP::get(Tp, 0.0L);
581  default:
582    llvm_unreachable("Unknown recurrence kind");
583  }
584}
585
586/// This function translates the recurrence kind to an LLVM binary operator.
587unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
588  switch (Kind) {
589  case RK_IntegerAdd:
590    return Instruction::Add;
591  case RK_IntegerMult:
592    return Instruction::Mul;
593  case RK_IntegerOr:
594    return Instruction::Or;
595  case RK_IntegerAnd:
596    return Instruction::And;
597  case RK_IntegerXor:
598    return Instruction::Xor;
599  case RK_FloatMult:
600    return Instruction::FMul;
601  case RK_FloatAdd:
602    return Instruction::FAdd;
603  case RK_IntegerMinMax:
604    return Instruction::ICmp;
605  case RK_FloatMinMax:
606    return Instruction::FCmp;
607  default:
608    llvm_unreachable("Unknown recurrence operation");
609  }
610}
611
612Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
613                                            MinMaxRecurrenceKind RK,
614                                            Value *Left, Value *Right) {
615  CmpInst::Predicate P = CmpInst::ICMP_NE;
616  switch (RK) {
617  default:
618    llvm_unreachable("Unknown min/max recurrence kind");
619  case MRK_UIntMin:
620    P = CmpInst::ICMP_ULT;
621    break;
622  case MRK_UIntMax:
623    P = CmpInst::ICMP_UGT;
624    break;
625  case MRK_SIntMin:
626    P = CmpInst::ICMP_SLT;
627    break;
628  case MRK_SIntMax:
629    P = CmpInst::ICMP_SGT;
630    break;
631  case MRK_FloatMin:
632    P = CmpInst::FCMP_OLT;
633    break;
634  case MRK_FloatMax:
635    P = CmpInst::FCMP_OGT;
636    break;
637  }
638
639  // We only match FP sequences with unsafe algebra, so we can unconditionally
640  // set it on any generated instructions.
641  IRBuilder<>::FastMathFlagGuard FMFG(Builder);
642  FastMathFlags FMF;
643  FMF.setUnsafeAlgebra();
644  Builder.setFastMathFlags(FMF);
645
646  Value *Cmp;
647  if (RK == MRK_FloatMin || RK == MRK_FloatMax)
648    Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
649  else
650    Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
651
652  Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
653  return Select;
654}
655
656InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
657                                         const SCEV *Step)
658  : StartValue(Start), IK(K), Step(Step) {
659  assert(IK != IK_NoInduction && "Not an induction");
660
661  // Start value type should match the induction kind and the value
662  // itself should not be null.
663  assert(StartValue && "StartValue is null");
664  assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
665         "StartValue is not a pointer for pointer induction");
666  assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
667         "StartValue is not an integer for integer induction");
668
669  // Check the Step Value. It should be non-zero integer value.
670  assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
671         "Step value is zero");
672
673  assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
674         "Step value should be constant for pointer induction");
675  assert(Step->getType()->isIntegerTy() && "StepValue is not an integer");
676}
677
678int InductionDescriptor::getConsecutiveDirection() const {
679  ConstantInt *ConstStep = getConstIntStepValue();
680  if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
681    return ConstStep->getSExtValue();
682  return 0;
683}
684
685ConstantInt *InductionDescriptor::getConstIntStepValue() const {
686  if (isa<SCEVConstant>(Step))
687    return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
688  return nullptr;
689}
690
691Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index,
692                                      ScalarEvolution *SE,
693                                      const DataLayout& DL) const {
694
695  SCEVExpander Exp(*SE, DL, "induction");
696  switch (IK) {
697  case IK_IntInduction: {
698    assert(Index->getType() == StartValue->getType() &&
699           "Index type does not match StartValue type");
700
701    // FIXME: Theoretically, we can call getAddExpr() of ScalarEvolution
702    // and calculate (Start + Index * Step) for all cases, without
703    // special handling for "isOne" and "isMinusOne".
704    // But in the real life the result code getting worse. We mix SCEV
705    // expressions and ADD/SUB operations and receive redundant
706    // intermediate values being calculated in different ways and
707    // Instcombine is unable to reduce them all.
708
709    if (getConstIntStepValue() &&
710        getConstIntStepValue()->isMinusOne())
711      return B.CreateSub(StartValue, Index);
712    if (getConstIntStepValue() &&
713        getConstIntStepValue()->isOne())
714      return B.CreateAdd(StartValue, Index);
715    const SCEV *S = SE->getAddExpr(SE->getSCEV(StartValue),
716                                   SE->getMulExpr(Step, SE->getSCEV(Index)));
717    return Exp.expandCodeFor(S, StartValue->getType(), &*B.GetInsertPoint());
718  }
719  case IK_PtrInduction: {
720    assert(Index->getType() == Step->getType() &&
721           "Index type does not match StepValue type");
722    assert(isa<SCEVConstant>(Step) &&
723           "Expected constant step for pointer induction");
724    const SCEV *S = SE->getMulExpr(SE->getSCEV(Index), Step);
725    Index = Exp.expandCodeFor(S, Index->getType(), &*B.GetInsertPoint());
726    return B.CreateGEP(nullptr, StartValue, Index);
727  }
728  case IK_NoInduction:
729    return nullptr;
730  }
731  llvm_unreachable("invalid enum");
732}
733
734bool InductionDescriptor::isInductionPHI(PHINode *Phi,
735                                         PredicatedScalarEvolution &PSE,
736                                         InductionDescriptor &D,
737                                         bool Assume) {
738  Type *PhiTy = Phi->getType();
739  // We only handle integer and pointer inductions variables.
740  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
741    return false;
742
743  const SCEV *PhiScev = PSE.getSCEV(Phi);
744  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
745
746  // We need this expression to be an AddRecExpr.
747  if (Assume && !AR)
748    AR = PSE.getAsAddRec(Phi);
749
750  if (!AR) {
751    DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
752    return false;
753  }
754
755  return isInductionPHI(Phi, PSE.getSE(), D, AR);
756}
757
758bool InductionDescriptor::isInductionPHI(PHINode *Phi,
759                                         ScalarEvolution *SE,
760                                         InductionDescriptor &D,
761                                         const SCEV *Expr) {
762  Type *PhiTy = Phi->getType();
763  // We only handle integer and pointer inductions variables.
764  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
765    return false;
766
767  // Check that the PHI is consecutive.
768  const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
769  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
770
771  if (!AR) {
772    DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
773    return false;
774  }
775
776  assert(AR->getLoop()->getHeader() == Phi->getParent() &&
777         "PHI is an AddRec for a different loop?!");
778  Value *StartValue =
779    Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
780  const SCEV *Step = AR->getStepRecurrence(*SE);
781  // Calculate the pointer stride and check if it is consecutive.
782  // The stride may be a constant or a loop invariant integer value.
783  const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
784  if (!ConstStep && !SE->isLoopInvariant(Step, AR->getLoop()))
785    return false;
786
787  if (PhiTy->isIntegerTy()) {
788    D = InductionDescriptor(StartValue, IK_IntInduction, Step);
789    return true;
790  }
791
792  assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
793  // Pointer induction should be a constant.
794  if (!ConstStep)
795    return false;
796
797  ConstantInt *CV = ConstStep->getValue();
798  Type *PointerElementType = PhiTy->getPointerElementType();
799  // The pointer stride cannot be determined if the pointer element type is not
800  // sized.
801  if (!PointerElementType->isSized())
802    return false;
803
804  const DataLayout &DL = Phi->getModule()->getDataLayout();
805  int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
806  if (!Size)
807    return false;
808
809  int64_t CVSize = CV->getSExtValue();
810  if (CVSize % Size)
811    return false;
812  auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size,
813                                    true /* signed */);
814  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
815  return true;
816}
817
818/// \brief Returns the instructions that use values defined in the loop.
819SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
820  SmallVector<Instruction *, 8> UsedOutside;
821
822  for (auto *Block : L->getBlocks())
823    // FIXME: I believe that this could use copy_if if the Inst reference could
824    // be adapted into a pointer.
825    for (auto &Inst : *Block) {
826      auto Users = Inst.users();
827      if (std::any_of(Users.begin(), Users.end(), [&](User *U) {
828            auto *Use = cast<Instruction>(U);
829            return !L->contains(Use->getParent());
830          }))
831        UsedOutside.push_back(&Inst);
832    }
833
834  return UsedOutside;
835}
836
837void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
838  // By definition, all loop passes need the LoopInfo analysis and the
839  // Dominator tree it depends on. Because they all participate in the loop
840  // pass manager, they must also preserve these.
841  AU.addRequired<DominatorTreeWrapperPass>();
842  AU.addPreserved<DominatorTreeWrapperPass>();
843  AU.addRequired<LoopInfoWrapperPass>();
844  AU.addPreserved<LoopInfoWrapperPass>();
845
846  // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
847  // here because users shouldn't directly get them from this header.
848  extern char &LoopSimplifyID;
849  extern char &LCSSAID;
850  AU.addRequiredID(LoopSimplifyID);
851  AU.addPreservedID(LoopSimplifyID);
852  AU.addRequiredID(LCSSAID);
853  AU.addPreservedID(LCSSAID);
854
855  // Loop passes are designed to run inside of a loop pass manager which means
856  // that any function analyses they require must be required by the first loop
857  // pass in the manager (so that it is computed before the loop pass manager
858  // runs) and preserved by all loop pasess in the manager. To make this
859  // reasonably robust, the set needed for most loop passes is maintained here.
860  // If your loop pass requires an analysis not listed here, you will need to
861  // carefully audit the loop pass manager nesting structure that results.
862  AU.addRequired<AAResultsWrapperPass>();
863  AU.addPreserved<AAResultsWrapperPass>();
864  AU.addPreserved<BasicAAWrapperPass>();
865  AU.addPreserved<GlobalsAAWrapperPass>();
866  AU.addPreserved<SCEVAAWrapperPass>();
867  AU.addRequired<ScalarEvolutionWrapperPass>();
868  AU.addPreserved<ScalarEvolutionWrapperPass>();
869}
870
871/// Manually defined generic "LoopPass" dependency initialization. This is used
872/// to initialize the exact set of passes from above in \c
873/// getLoopAnalysisUsage. It can be used within a loop pass's initialization
874/// with:
875///
876///   INITIALIZE_PASS_DEPENDENCY(LoopPass)
877///
878/// As-if "LoopPass" were a pass.
879void llvm::initializeLoopPassPass(PassRegistry &Registry) {
880  INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
881  INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
882  INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
883  INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
884  INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
885  INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
886  INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
887  INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
888  INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
889}
890
891/// \brief Find string metadata for loop
892///
893/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
894/// operand or null otherwise.  If the string metadata is not found return
895/// Optional's not-a-value.
896Optional<const MDOperand *> llvm::findStringMetadataForLoop(Loop *TheLoop,
897                                                            StringRef Name) {
898  MDNode *LoopID = TheLoop->getLoopID();
899  // Return none if LoopID is false.
900  if (!LoopID)
901    return None;
902
903  // First operand should refer to the loop id itself.
904  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
905  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
906
907  // Iterate over LoopID operands and look for MDString Metadata
908  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
909    MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
910    if (!MD)
911      continue;
912    MDString *S = dyn_cast<MDString>(MD->getOperand(0));
913    if (!S)
914      continue;
915    // Return true if MDString holds expected MetaData.
916    if (Name.equals(S->getString()))
917      switch (MD->getNumOperands()) {
918      case 1:
919        return nullptr;
920      case 2:
921        return &MD->getOperand(1);
922      default:
923        llvm_unreachable("loop metadata has 0 or 1 operand");
924      }
925  }
926  return None;
927}
928
929/// Returns true if the instruction in a loop is guaranteed to execute at least
930/// once.
931bool llvm::isGuaranteedToExecute(const Instruction &Inst,
932                                 const DominatorTree *DT, const Loop *CurLoop,
933                                 const LoopSafetyInfo *SafetyInfo) {
934  // We have to check to make sure that the instruction dominates all
935  // of the exit blocks.  If it doesn't, then there is a path out of the loop
936  // which does not execute this instruction, so we can't hoist it.
937
938  // If the instruction is in the header block for the loop (which is very
939  // common), it is always guaranteed to dominate the exit blocks.  Since this
940  // is a common case, and can save some work, check it now.
941  if (Inst.getParent() == CurLoop->getHeader())
942    // If there's a throw in the header block, we can't guarantee we'll reach
943    // Inst.
944    return !SafetyInfo->HeaderMayThrow;
945
946  // Somewhere in this loop there is an instruction which may throw and make us
947  // exit the loop.
948  if (SafetyInfo->MayThrow)
949    return false;
950
951  // Get the exit blocks for the current loop.
952  SmallVector<BasicBlock *, 8> ExitBlocks;
953  CurLoop->getExitBlocks(ExitBlocks);
954
955  // Verify that the block dominates each of the exit blocks of the loop.
956  for (BasicBlock *ExitBlock : ExitBlocks)
957    if (!DT->dominates(Inst.getParent(), ExitBlock))
958      return false;
959
960  // As a degenerate case, if the loop is statically infinite then we haven't
961  // proven anything since there are no exit blocks.
962  if (ExitBlocks.empty())
963    return false;
964
965  // FIXME: In general, we have to prove that the loop isn't an infinite loop.
966  // See http::llvm.org/PR24078 .  (The "ExitBlocks.empty()" check above is
967  // just a special case of this.)
968  return true;
969}
970