/build/source/llvm/lib/Analysis/IVDescriptors.cpp

Bug Summary

File:	build/source/llvm/lib/Analysis/IVDescriptors.cpp
Warning:	line 1191, column 8 Called C++ object pointer is null
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name IVDescriptors.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Analysis -I /build/source/llvm/lib/Analysis -I include -I /build/source/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-17/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1683717183 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-05-10-133810-16478-1 -x c++ /build/source/llvm/lib/Analysis/IVDescriptors.cpp
1//===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file "describes" induction and recurrence variables.
10//
11//===----------------------------------------------------------------------===//

13#include "llvm/Analysis/IVDescriptors.h"
14#include "llvm/Analysis/DemandedBits.h"
15#include "llvm/Analysis/LoopInfo.h"
16#include "llvm/Analysis/ScalarEvolution.h"
17#include "llvm/Analysis/ScalarEvolutionExpressions.h"
18#include "llvm/Analysis/ValueTracking.h"
19#include "llvm/IR/Dominators.h"
20#include "llvm/IR/Instructions.h"
21#include "llvm/IR/Module.h"
22#include "llvm/IR/PatternMatch.h"
23#include "llvm/IR/ValueHandle.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/KnownBits.h"

27#include <set>

29using namespace llvm;
30using namespace llvm::PatternMatch;

32#define DEBUG_TYPE"iv-descriptors" "iv-descriptors"

34bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
                                      SmallPtrSetImpl<Instruction *> &Set) {
for (const Use &Use : I->operands())
  if (!Set.count(dyn_cast<Instruction>(Use)))
    return false;
return true;
40}

42bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) {
switch (Kind) {
default:
  break;
case RecurKind::Add:
case RecurKind::Mul:
case RecurKind::Or:
case RecurKind::And:
case RecurKind::Xor:
case RecurKind::SMax:
case RecurKind::SMin:
case RecurKind::UMax:
case RecurKind::UMin:
case RecurKind::SelectICmp:
case RecurKind::SelectFCmp:
  return true;
}
return false;
60}

62bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) {
return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind);
64}

66/// Determines if Phi may have been type-promoted. If Phi has a single user
67/// that ANDs the Phi with a type mask, return the user. RT is updated to
68/// account for the narrower bit width represented by the mask, and the AND
69/// instruction is added to CI.
70static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
                                 SmallPtrSetImpl<Instruction *> &Visited,
                                 SmallPtrSetImpl<Instruction *> &CI) {
if (!Phi->hasOneUse())
  return Phi;

const APInt *M = nullptr;
Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());

// Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
// with a new integer type of the corresponding bit width.
if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) {
  int32_t Bits = (*M + 1).exactLogBase2();
  if (Bits > 0) {
    RT = IntegerType::get(Phi->getContext(), Bits);
    Visited.insert(Phi);
    CI.insert(J);
    return J;
  }
}
return Phi;
91}

93/// Compute the minimal bit width needed to represent a reduction whose exit
94/// instruction is given by Exit.
95static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
                                                   DemandedBits *DB,
                                                   AssumptionCache *AC,
                                                   DominatorTree *DT) {
bool IsSigned = false;
const DataLayout &DL = Exit->getModule()->getDataLayout();
uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());

if (DB) {
  // Use the demanded bits analysis to determine the bits that are live out
  // of the exit instruction, rounding up to the nearest power of two. If the
  // use of demanded bits results in a smaller bit width, we know the value
  // must be positive (i.e., IsSigned = false), because if this were not the
  // case, the sign bit would have been demanded.
  auto Mask = DB->getDemandedBits(Exit);
  MaxBitWidth = Mask.getBitWidth() - Mask.countl_zero();
}

if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
  // If demanded bits wasn't able to limit the bit width, we can try to use
  // value tracking instead. This can be the case, for example, if the value
  // may be negative.
  auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT);
  auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
  MaxBitWidth = NumTypeBits - NumSignBits;
  KnownBits Bits = computeKnownBits(Exit, DL);
  if (!Bits.isNonNegative()) {
    // If the value is not known to be non-negative, we set IsSigned to true,
    // meaning that we will use sext instructions instead of zext
    // instructions to restore the original type.
    IsSigned = true;
    // Make sure at at least one sign bit is included in the result, so it
    // will get properly sign-extended.
    ++MaxBitWidth;
  }
}
MaxBitWidth = llvm::bit_ceil(MaxBitWidth);

return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
                      IsSigned);
135}

137/// Collect cast instructions that can be ignored in the vectorizer's cost
138/// model, given a reduction exit value and the minimal type in which the
139// reduction can be represented. Also search casts to the recurrence type
140// to find the minimum width used by the recurrence.
141static void collectCastInstrs(Loop *TheLoop, Instruction *Exit,
                            Type *RecurrenceType,
                            SmallPtrSetImpl<Instruction *> &Casts,
                            unsigned &MinWidthCastToRecurTy) {

SmallVector<Instruction *, 8> Worklist;
SmallPtrSet<Instruction *, 8> Visited;
Worklist.push_back(Exit);
MinWidthCastToRecurTy = -1U;

while (!Worklist.empty()) {
  Instruction *Val = Worklist.pop_back_val();
  Visited.insert(Val);
  if (auto *Cast = dyn_cast<CastInst>(Val)) {
    if (Cast->getSrcTy() == RecurrenceType) {
      // If the source type of a cast instruction is equal to the recurrence
      // type, it will be eliminated, and should be ignored in the vectorizer
      // cost model.
      Casts.insert(Cast);
      continue;
    }
    if (Cast->getDestTy() == RecurrenceType) {
      // The minimum width used by the recurrence is found by checking for
      // casts on its operands. The minimum width is used by the vectorizer
      // when finding the widest type for in-loop reductions without any
      // loads/stores.
      MinWidthCastToRecurTy = std::min<unsigned>(
          MinWidthCastToRecurTy, Cast->getSrcTy()->getScalarSizeInBits());
      continue;
    }
  }
  // Add all operands to the work list if they are loop-varying values that
  // we haven't yet visited.
  for (Value *O : cast<User>(Val)->operands())
    if (auto *I = dyn_cast<Instruction>(O))
      if (TheLoop->contains(I) && !Visited.count(I))
        Worklist.push_back(I);
}
179}

181// Check if a given Phi node can be recognized as an ordered reduction for
182// vectorizing floating point operations without unsafe math.
183static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst,
                                Instruction *Exit, PHINode *Phi) {
// Currently only FAdd and FMulAdd are supported.
if (Kind != RecurKind::FAdd && Kind != RecurKind::FMulAdd)
  return false;

if (Kind == RecurKind::FAdd && Exit->getOpcode() != Instruction::FAdd)
  return false;

if (Kind == RecurKind::FMulAdd &&
    !RecurrenceDescriptor::isFMulAddIntrinsic(Exit))
  return false;

// Ensure the exit instruction has only one user other than the reduction PHI
if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(3))
  return false;

// The only pattern accepted is the one in which the reduction PHI
// is used as one of the operands of the exit instruction
auto *Op0 = Exit->getOperand(0);
auto *Op1 = Exit->getOperand(1);
if (Kind == RecurKind::FAdd && Op0 != Phi && Op1 != Phi)
  return false;
if (Kind == RecurKind::FMulAdd && Exit->getOperand(2) != Phi)
  return false;

LLVM_DEBUG(dbgs() << "LV: Found an ordered reduction: Phi: " << *Phido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: Found an ordered reduction: Phi: "
 << *Phi << ", ExitInst: " << *Exit <<
 "\n"; } } while (false)
                  << ", ExitInst: " << *Exit << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: Found an ordered reduction: Phi: "
 << *Phi << ", ExitInst: " << *Exit <<
 "\n"; } } while (false);

return true;
213}

215bool RecurrenceDescriptor::AddReductionVar(
  PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF,
  RecurrenceDescriptor &RedDes, DemandedBits *DB, AssumptionCache *AC,
  DominatorTree *DT, ScalarEvolution *SE) {
if (Phi->getNumIncomingValues() != 2)
  return false;

// Reduction variables are only found in the loop header block.
if (Phi->getParent() != TheLoop->getHeader())
  return false;

// Obtain the reduction start value from the value that comes from the loop
// preheader.
Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());

// ExitInstruction is the single value which is used outside the loop.
// We only allow for a single reduction value to be used outside the loop.
// This includes users of the reduction, variables (which form a cycle
// which ends in the phi node).
Instruction *ExitInstruction = nullptr;

// Variable to keep last visited store instruction. By the end of the
// algorithm this variable will be either empty or having intermediate
// reduction value stored in invariant address.
StoreInst *IntermediateStore = nullptr;

// Indicates that we found a reduction operation in our scan.
bool FoundReduxOp = false;

// We start with the PHI node and scan for all of the users of this
// instruction. All users must be instructions that can be used as reduction
// variables (such as ADD). We must have a single out-of-block user. The cycle
// must include the original PHI.
bool FoundStartPHI = false;

// To recognize min/max patterns formed by a icmp select sequence, we store
// the number of instruction we saw from the recognized min/max pattern,
//  to make sure we only see exactly the two instructions.
unsigned NumCmpSelectPatternInst = 0;
InstDesc ReduxDesc(false, nullptr);

// Data used for determining if the recurrence has been type-promoted.
Type *RecurrenceType = Phi->getType();
SmallPtrSet<Instruction *, 4> CastInsts;
unsigned MinWidthCastToRecurrenceType;
Instruction *Start = Phi;
bool IsSigned = false;

SmallPtrSet<Instruction *, 8> VisitedInsts;
SmallVector<Instruction *, 8> Worklist;

// Return early if the recurrence kind does not match the type of Phi. If the
// recurrence kind is arithmetic, we attempt to look through AND operations
// resulting from the type promotion performed by InstCombine.  Vector
// operations are not limited to the legal integer widths, so we may be able
// to evaluate the reduction in the narrower width.
if (RecurrenceType->isFloatingPointTy()) {
  if (!isFloatingPointRecurrenceKind(Kind))
    return false;
} else if (RecurrenceType->isIntegerTy()) {
  if (!isIntegerRecurrenceKind(Kind))
    return false;
  if (!isMinMaxRecurrenceKind(Kind))
    Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
} else {
  // Pointer min/max may exist, but it is not supported as a reduction op.
  return false;
}

Worklist.push_back(Start);
VisitedInsts.insert(Start);

// Start with all flags set because we will intersect this with the reduction
// flags from all the reduction operations.
FastMathFlags FMF = FastMathFlags::getFast();

// The first instruction in the use-def chain of the Phi node that requires
// exact floating point operations.
Instruction *ExactFPMathInst = nullptr;

// A value in the reduction can be used:
//  - By the reduction:
//      - Reduction operation:
//        - One use of reduction value (safe).
//        - Multiple use of reduction value (not safe).
//      - PHI:
//        - All uses of the PHI must be the reduction (safe).
//        - Otherwise, not safe.
//  - By instructions outside of the loop (safe).
//      * One value may have several outside users, but all outside
//        uses must be of the same value.
//  - By store instructions with a loop invariant address (safe with
//    the following restrictions):
//      * If there are several stores, all must have the same address.
//      * Final value should be stored in that loop invariant address.
//  - By an instruction that is not part of the reduction (not safe).
//    This is either:
//      * An instruction type other than PHI or the reduction operation.
//      * A PHI in the header other than the initial PHI.
while (!Worklist.empty()) {
  Instruction *Cur = Worklist.pop_back_val();

  // Store instructions are allowed iff it is the store of the reduction
  // value to the same loop invariant memory location.
  if (auto *SI = dyn_cast<StoreInst>(Cur)) {
    if (!SE) {
      LLVM_DEBUG(dbgs() << "Store instructions are not processed without "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Store instructions are not processed without "
 << "Scalar Evolution Analysis\n"; } } while (false)
                        << "Scalar Evolution Analysis\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Store instructions are not processed without "
 << "Scalar Evolution Analysis\n"; } } while (false);
      return false;
    }

    const SCEV *PtrScev = SE->getSCEV(SI->getPointerOperand());
    // Check it is the same address as previous stores
    if (IntermediateStore) {
      const SCEV *OtherScev =
          SE->getSCEV(IntermediateStore->getPointerOperand());

      if (OtherScev != PtrScev) {
        LLVM_DEBUG(dbgs() << "Storing reduction value to different addresses "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses "
 << "inside the loop: " << *SI->getPointerOperand
() << " and " << *IntermediateStore->getPointerOperand
() << '\n'; } } while (false)
                          << "inside the loop: " << *SI->getPointerOperand()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses "
 << "inside the loop: " << *SI->getPointerOperand
() << " and " << *IntermediateStore->getPointerOperand
() << '\n'; } } while (false)
                          << " and "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses "
 << "inside the loop: " << *SI->getPointerOperand
() << " and " << *IntermediateStore->getPointerOperand
() << '\n'; } } while (false)
                          << *IntermediateStore->getPointerOperand() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to different addresses "
 << "inside the loop: " << *SI->getPointerOperand
() << " and " << *IntermediateStore->getPointerOperand
() << '\n'; } } while (false);
        return false;
      }
    }

    // Check the pointer is loop invariant
    if (!SE->isLoopInvariant(PtrScev, TheLoop)) {
      LLVM_DEBUG(dbgs() << "Storing reduction value to non-uniform address "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to non-uniform address "
 << "inside the loop: " << *SI->getPointerOperand
() << '\n'; } } while (false)
                        << "inside the loop: " << *SI->getPointerOperand()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to non-uniform address "
 << "inside the loop: " << *SI->getPointerOperand
() << '\n'; } } while (false)
                        << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Storing reduction value to non-uniform address "
 << "inside the loop: " << *SI->getPointerOperand
() << '\n'; } } while (false);
      return false;
    }

    // IntermediateStore is always the last store in the loop.
    IntermediateStore = SI;
    continue;
  }

  // No Users.
  // If the instruction has no users then this is a broken chain and can't be
  // a reduction variable.
  if (Cur->use_empty())
    return false;

  bool IsAPhi = isa<PHINode>(Cur);

  // A header PHI use other than the original PHI.
  if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
    return false;

  // Reductions of instructions such as Div, and Sub is only possible if the
  // LHS is the reduction variable.
  if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
      !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&
      !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
    return false;

  // Any reduction instruction must be of one of the allowed kinds. We ignore
  // the starting value (the Phi or an AND instruction if the Phi has been
  // type-promoted).
  if (Cur != Start) {
    ReduxDesc =
        isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF);
    ExactFPMathInst = ExactFPMathInst == nullptr
                          ? ReduxDesc.getExactFPMathInst()
                          : ExactFPMathInst;
    if (!ReduxDesc.isRecurrence())
      return false;
    // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
    if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi) {
      FastMathFlags CurFMF = ReduxDesc.getPatternInst()->getFastMathFlags();
      if (auto *Sel = dyn_cast<SelectInst>(ReduxDesc.getPatternInst())) {
        // Accept FMF on either fcmp or select of a min/max idiom.
        // TODO: This is a hack to work-around the fact that FMF may not be
        //       assigned/propagated correctly. If that problem is fixed or we
        //       standardize on fmin/fmax via intrinsics, this can be removed.
        if (auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))
          CurFMF |= FCmp->getFastMathFlags();
      }
      FMF &= CurFMF;
    }
    // Update this reduction kind if we matched a new instruction.
    // TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind'
    //       state accurate while processing the worklist?
    if (ReduxDesc.getRecKind() != RecurKind::None)
      Kind = ReduxDesc.getRecKind();
  }

  bool IsASelect = isa<SelectInst>(Cur);

  // A conditional reduction operation must only have 2 or less uses in
  // VisitedInsts.
  if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) &&
      hasMultipleUsesOf(Cur, VisitedInsts, 2))
    return false;

  // A reduction operation must only have one use of the reduction value.
  if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) &&
      !isSelectCmpRecurrenceKind(Kind) &&
      hasMultipleUsesOf(Cur, VisitedInsts, 1))
    return false;

  // All inputs to a PHI node must be a reduction value.
  if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
    return false;

  if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectICmp) &&
      (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
    ++NumCmpSelectPatternInst;
  if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectFCmp) &&
      (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
    ++NumCmpSelectPatternInst;

  // Check  whether we found a reduction operator.
  FoundReduxOp |= !IsAPhi && Cur != Start;

  // Process users of current instruction. Push non-PHI nodes after PHI nodes
  // onto the stack. This way we are going to have seen all inputs to PHI
  // nodes once we get to them.
  SmallVector<Instruction *, 8> NonPHIs;
  SmallVector<Instruction *, 8> PHIs;
  for (User *U : Cur->users()) {
    Instruction *UI = cast<Instruction>(U);

    // If the user is a call to llvm.fmuladd then the instruction can only be
    // the final operand.
    if (isFMulAddIntrinsic(UI))
      if (Cur == UI->getOperand(0) || Cur == UI->getOperand(1))
        return false;

    // Check if we found the exit user.
    BasicBlock *Parent = UI->getParent();
    if (!TheLoop->contains(Parent)) {
      // If we already know this instruction is used externally, move on to
      // the next user.
      if (ExitInstruction == Cur)
        continue;

      // Exit if you find multiple values used outside or if the header phi
      // node is being used. In this case the user uses the value of the
      // previous iteration, in which case we would loose "VF-1" iterations of
      // the reduction operation if we vectorize.
      if (ExitInstruction != nullptr || Cur == Phi)
        return false;

      // The instruction used by an outside user must be the last instruction
      // before we feed back to the reduction phi. Otherwise, we loose VF-1
      // operations on the value.
      if (!is_contained(Phi->operands(), Cur))
        return false;

      ExitInstruction = Cur;
      continue;
    }

    // Process instructions only once (termination). Each reduction cycle
    // value must only be used once, except by phi nodes and min/max
    // reductions which are represented as a cmp followed by a select.
    InstDesc IgnoredVal(false, nullptr);
    if (VisitedInsts.insert(UI).second) {
      if (isa<PHINode>(UI)) {
        PHIs.push_back(UI);
      } else {
        StoreInst *SI = dyn_cast<StoreInst>(UI);
        if (SI && SI->getPointerOperand() == Cur) {
          // Reduction variable chain can only be stored somewhere but it
          // can't be used as an address.
          return false;
        }
        NonPHIs.push_back(UI);
      }
    } else if (!isa<PHINode>(UI) &&
               ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
                 !isa<SelectInst>(UI)) ||
                (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
                 !isSelectCmpPattern(TheLoop, Phi, UI, IgnoredVal)
                      .isRecurrence() &&
                 !isMinMaxPattern(UI, Kind, IgnoredVal).isRecurrence())))
      return false;

    // Remember that we completed the cycle.
    if (UI == Phi)
      FoundStartPHI = true;
  }
  Worklist.append(PHIs.begin(), PHIs.end());
  Worklist.append(NonPHIs.begin(), NonPHIs.end());
}

// This means we have seen one but not the other instruction of the
// pattern or more than just a select and cmp. Zero implies that we saw a
// llvm.min/max intrinsic, which is always OK.
if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2 &&
    NumCmpSelectPatternInst != 0)
  return false;

if (isSelectCmpRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1)
  return false;

if (IntermediateStore) {
  // Check that stored value goes to the phi node again. This way we make sure
  // that the value stored in IntermediateStore is indeed the final reduction
  // value.
  if (!is_contained(Phi->operands(), IntermediateStore->getValueOperand())) {
    LLVM_DEBUG(dbgs() << "Not a final reduction value stored: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Not a final reduction value stored: "
 << *IntermediateStore << '\n'; } } while (false)
                      << *IntermediateStore << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Not a final reduction value stored: "
 << *IntermediateStore << '\n'; } } while (false);
    return false;
  }

  // If there is an exit instruction it's value should be stored in
  // IntermediateStore
  if (ExitInstruction &&
      IntermediateStore->getValueOperand() != ExitInstruction) {
    LLVM_DEBUG(dbgs() << "Last store Instruction of reduction value does not "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Last store Instruction of reduction value does not "
 "store last calculated value of the reduction: " << *IntermediateStore
 << '\n'; } } while (false)
                         "store last calculated value of the reduction: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Last store Instruction of reduction value does not "
 "store last calculated value of the reduction: " << *IntermediateStore
 << '\n'; } } while (false)
                      << *IntermediateStore << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Last store Instruction of reduction value does not "
 "store last calculated value of the reduction: " << *IntermediateStore
 << '\n'; } } while (false);
    return false;
  }

  // If all uses are inside the loop (intermediate stores), then the
  // reduction value after the loop will be the one used in the last store.
  if (!ExitInstruction)
    ExitInstruction = cast<Instruction>(IntermediateStore->getValueOperand());
}

if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
  return false;

const bool IsOrdered =
    checkOrderedReduction(Kind, ExactFPMathInst, ExitInstruction, Phi);

if (Start != Phi) {
  // If the starting value is not the same as the phi node, we speculatively
  // looked through an 'and' instruction when evaluating a potential
  // arithmetic reduction to determine if it may have been type-promoted.
  //
  // We now compute the minimal bit width that is required to represent the
  // reduction. If this is the same width that was indicated by the 'and', we
  // can represent the reduction in the smaller type. The 'and' instruction
  // will be eliminated since it will essentially be a cast instruction that
  // can be ignore in the cost model. If we compute a different type than we
  // did when evaluating the 'and', the 'and' will not be eliminated, and we
  // will end up with different kinds of operations in the recurrence
  // expression (e.g., IntegerAND, IntegerADD). We give up if this is
  // the case.
  //
  // The vectorizer relies on InstCombine to perform the actual
  // type-shrinking. It does this by inserting instructions to truncate the
  // exit value of the reduction to the width indicated by RecurrenceType and
  // then extend this value back to the original width. If IsSigned is false,
  // a 'zext' instruction will be generated; otherwise, a 'sext' will be
  // used.
  //
  // TODO: We should not rely on InstCombine to rewrite the reduction in the
  //       smaller type. We should just generate a correctly typed expression
  //       to begin with.
  Type *ComputedType;
  std::tie(ComputedType, IsSigned) =
      computeRecurrenceType(ExitInstruction, DB, AC, DT);
  if (ComputedType != RecurrenceType)
    return false;
}

// Collect cast instructions and the minimum width used by the recurrence.
// If the starting value is not the same as the phi node and the computed
// recurrence type is equal to the recurrence type, the recurrence expression
// will be represented in a narrower or wider type. If there are any cast
// instructions that will be unnecessary, collect them in CastsFromRecurTy.
// Note that the 'and' instruction was already included in this list.
//
// TODO: A better way to represent this may be to tag in some way all the
//       instructions that are a part of the reduction. The vectorizer cost
//       model could then apply the recurrence type to these instructions,
//       without needing a white list of instructions to ignore.
//       This may also be useful for the inloop reductions, if it can be
//       kept simple enough.
collectCastInstrs(TheLoop, ExitInstruction, RecurrenceType, CastInsts,
                  MinWidthCastToRecurrenceType);

// We found a reduction var if we have reached the original phi node and we
// only have a single instruction with out-of-loop users.

// The ExitInstruction(Instruction which is allowed to have out-of-loop users)
// is saved as part of the RecurrenceDescriptor.

// Save the description of this reduction variable.
RecurrenceDescriptor RD(RdxStart, ExitInstruction, IntermediateStore, Kind,
                        FMF, ExactFPMathInst, RecurrenceType, IsSigned,
                        IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
RedDes = RD;

return true;
607}

609// We are looking for loops that do something like this:
610//   int r = 0;
611//   for (int i = 0; i < n; i++) {
612//     if (src[i] > 3)
613//       r = 3;
614//   }
615// where the reduction value (r) only has two states, in this example 0 or 3.
616// The generated LLVM IR for this type of loop will be like this:
617//   for.body:
618//     %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ]
619//     ...
620//     %cmp = icmp sgt i32 %5, 3
621//     %spec.select = select i1 %cmp, i32 3, i32 %r
622//     ...
623// In general we can support vectorization of loops where 'r' flips between
624// any two non-constants, provided they are loop invariant. The only thing
625// we actually care about at the end of the loop is whether or not any lane
626// in the selected vector is different from the start value. The final
627// across-vector reduction after the loop simply involves choosing the start
628// value if nothing changed (0 in the example above) or the other selected
629// value (3 in the example above).
630RecurrenceDescriptor::InstDesc
631RecurrenceDescriptor::isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
                                       Instruction *I, InstDesc &Prev) {
// We must handle the select(cmp(),x,y) as a single instruction. Advance to
// the select.
CmpInst::Predicate Pred;
if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
  if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
    return InstDesc(Select, Prev.getRecKind());
}

// Only match select with single use cmp condition.
if (!match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
                       m_Value())))
  return InstDesc(false, I);

SelectInst *SI = cast<SelectInst>(I);
Value *NonPhi = nullptr;

if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue()))
  NonPhi = SI->getFalseValue();
else if (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue()))
  NonPhi = SI->getTrueValue();
else
  return InstDesc(false, I);

// We are looking for selects of the form:
//   select(cmp(), phi, loop_invariant) or
//   select(cmp(), loop_invariant, phi)
if (!Loop->isLoopInvariant(NonPhi))
  return InstDesc(false, I);

return InstDesc(I, isa<ICmpInst>(I->getOperand(0)) ? RecurKind::SelectICmp
                                                   : RecurKind::SelectFCmp);
664}

666RecurrenceDescriptor::InstDesc
667RecurrenceDescriptor::isMinMaxPattern(Instruction *I, RecurKind Kind,
                                    const InstDesc &Prev) {
assert((isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) &&(static_cast <bool> ((isa<CmpInst>(I) || isa<SelectInst
>(I) || isa<CallInst>(I)) && "Expected a cmp or select or call instruction"
) ? void (0) : __assert_fail ("(isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) && \"Expected a cmp or select or call instruction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 670, __extension__ __PRETTY_FUNCTION__
))
       "Expected a cmp or select or call instruction")(static_cast <bool> ((isa<CmpInst>(I) || isa<SelectInst
>(I) || isa<CallInst>(I)) && "Expected a cmp or select or call instruction"
) ? void (0) : __assert_fail ("(isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) && \"Expected a cmp or select or call instruction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 670, __extension__ __PRETTY_FUNCTION__
));
if (!isMinMaxRecurrenceKind(Kind))
  return InstDesc(false, I);

// We must handle the select(cmp()) as a single instruction. Advance to the
// select.
CmpInst::Predicate Pred;
if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
  if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
    return InstDesc(Select, Prev.getRecKind());
}

// Only match select with single use cmp condition, or a min/max intrinsic.
if (!isa<IntrinsicInst>(I) &&
    !match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
                       m_Value())))
  return InstDesc(false, I);

// Look for a min/max pattern.
if (match(I, m_UMin(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::UMin, I);
if (match(I, m_UMax(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::UMax, I);
if (match(I, m_SMax(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::SMax, I);
if (match(I, m_SMin(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::SMin, I);
if (match(I, m_OrdFMin(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::FMin, I);
if (match(I, m_OrdFMax(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::FMax, I);
if (match(I, m_UnordFMin(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::FMin, I);
if (match(I, m_UnordFMax(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::FMax, I);
if (match(I, m_Intrinsic<Intrinsic::minnum>(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::FMin, I);
if (match(I, m_Intrinsic<Intrinsic::maxnum>(m_Value(), m_Value())))
  return InstDesc(Kind == RecurKind::FMax, I);

return InstDesc(false, I);
711}

713/// Returns true if the select instruction has users in the compare-and-add
714/// reduction pattern below. The select instruction argument is the last one
715/// in the sequence.
716///
717/// %sum.1 = phi ...
718/// ...
719/// %cmp = fcmp pred %0, %CFP
720/// %add = fadd %0, %sum.1
721/// %sum.2 = select %cmp, %add, %sum.1
722RecurrenceDescriptor::InstDesc
723RecurrenceDescriptor::isConditionalRdxPattern(RecurKind Kind, Instruction *I) {
SelectInst *SI = dyn_cast<SelectInst>(I);
if (!SI)
  return InstDesc(false, I);

CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());
// Only handle single use cases for now.
if (!CI || !CI->hasOneUse())
  return InstDesc(false, I);

Value *TrueVal = SI->getTrueValue();
Value *FalseVal = SI->getFalseValue();
// Handle only when either of operands of select instruction is a PHI
// node for now.
if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) ||
    (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal)))
  return InstDesc(false, I);

Instruction *I1 =
    isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal)
                           : dyn_cast<Instruction>(TrueVal);
if (!I1 || !I1->isBinaryOp())
  return InstDesc(false, I);

Value *Op1, *Op2;
if (!(((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) ||
        m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) &&
       I1->isFast()) ||
      (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast())) ||
      ((m_Add(m_Value(Op1), m_Value(Op2)).match(I1) ||
        m_Sub(m_Value(Op1), m_Value(Op2)).match(I1))) ||
      (m_Mul(m_Value(Op1), m_Value(Op2)).match(I1))))
  return InstDesc(false, I);

Instruction *IPhi = isa<PHINode>(*Op1) ? dyn_cast<Instruction>(Op1)
                                       : dyn_cast<Instruction>(Op2);
if (!IPhi || IPhi != FalseVal)
  return InstDesc(false, I);

return InstDesc(true, SI);
763}

765RecurrenceDescriptor::InstDesc
766RecurrenceDescriptor::isRecurrenceInstr(Loop *L, PHINode *OrigPhi,
                                      Instruction *I, RecurKind Kind,
                                      InstDesc &Prev, FastMathFlags FuncFMF) {
assert(Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind)(static_cast <bool> (Prev.getRecKind() == RecurKind::None
 || Prev.getRecKind() == Kind) ? void (0) : __assert_fail ("Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind"
, "llvm/lib/Analysis/IVDescriptors.cpp", 769, __extension__ __PRETTY_FUNCTION__
));
switch (I->getOpcode()) {
default:
  return InstDesc(false, I);
case Instruction::PHI:
  return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst());
case Instruction::Sub:
case Instruction::Add:
  return InstDesc(Kind == RecurKind::Add, I);
case Instruction::Mul:
  return InstDesc(Kind == RecurKind::Mul, I);
case Instruction::And:
  return InstDesc(Kind == RecurKind::And, I);
case Instruction::Or:
  return InstDesc(Kind == RecurKind::Or, I);
case Instruction::Xor:
  return InstDesc(Kind == RecurKind::Xor, I);
case Instruction::FDiv:
case Instruction::FMul:
  return InstDesc(Kind == RecurKind::FMul, I,
                  I->hasAllowReassoc() ? nullptr : I);
case Instruction::FSub:
case Instruction::FAdd:
  return InstDesc(Kind == RecurKind::FAdd, I,
                  I->hasAllowReassoc() ? nullptr : I);
case Instruction::Select:
  if (Kind == RecurKind::FAdd || Kind == RecurKind::FMul ||
      Kind == RecurKind::Add || Kind == RecurKind::Mul)
    return isConditionalRdxPattern(Kind, I);
  [[fallthrough]];
case Instruction::FCmp:
case Instruction::ICmp:
case Instruction::Call:
  if (isSelectCmpRecurrenceKind(Kind))
    return isSelectCmpPattern(L, OrigPhi, I, Prev);
  if (isIntMinMaxRecurrenceKind(Kind) ||
      (((FuncFMF.noNaNs() && FuncFMF.noSignedZeros()) ||
        (isa<FPMathOperator>(I) && I->hasNoNaNs() &&
         I->hasNoSignedZeros())) &&
       isFPMinMaxRecurrenceKind(Kind)))
    return isMinMaxPattern(I, Kind, Prev);
  else if (isFMulAddIntrinsic(I))
    return InstDesc(Kind == RecurKind::FMulAdd, I,
                    I->hasAllowReassoc() ? nullptr : I);
  return InstDesc(false, I);
}
815}

817bool RecurrenceDescriptor::hasMultipleUsesOf(
  Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
  unsigned MaxNumUses) {
unsigned NumUses = 0;
for (const Use &U : I->operands()) {
  if (Insts.count(dyn_cast<Instruction>(U)))
    ++NumUses;
  if (NumUses > MaxNumUses)
    return true;
}

return false;
829}

831bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
                                        RecurrenceDescriptor &RedDes,
                                        DemandedBits *DB, AssumptionCache *AC,
                                        DominatorTree *DT,
                                        ScalarEvolution *SE) {
BasicBlock *Header = TheLoop->getHeader();
Function &F = *Header->getParent();
FastMathFlags FMF;
FMF.setNoNaNs(
    F.getFnAttribute("no-nans-fp-math").getValueAsBool());
FMF.setNoSignedZeros(
    F.getFnAttribute("no-signed-zeros-fp-math").getValueAsBool());

if (AddReductionVar(Phi, RecurKind::Add, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an ADD reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::Mul, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a MUL reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::Or, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an OR reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::And, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an AND reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::Xor, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a XOR reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::SMax, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a SMAX reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::SMin, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a SMIN reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::UMax, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a UMAX reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::UMin, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a UMIN reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::SelectICmp, TheLoop, FMF, RedDes, DB, AC,
                    DT, SE)) {
  LLVM_DEBUG(dbgs() << "Found an integer conditional select reduction PHI."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an integer conditional select reduction PHI."
 << *Phi << "\n"; } } while (false)
                    << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an integer conditional select reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an FMult reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an FAdd reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::FMax, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a float MAX reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::FMin, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a float MIN reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RecurKind::SelectFCmp, TheLoop, FMF, RedDes, DB, AC,
                    DT, SE)) {
  LLVM_DEBUG(dbgs() << "Found a float conditional select reduction PHI."do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a float conditional select reduction PHI."
 << " PHI." << *Phi << "\n"; } } while (false
)
                    << " PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found a float conditional select reduction PHI."
 << " PHI." << *Phi << "\n"; } } while (false
);
  return true;
}
if (AddReductionVar(Phi, RecurKind::FMulAdd, TheLoop, FMF, RedDes, DB, AC, DT,
                    SE)) {
  LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "Found an FMulAdd reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
// Not a reduction of known type.
return false;
928}

930bool RecurrenceDescriptor::isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop,
                                                DominatorTree *DT) {

// Ensure the phi node is in the loop header and has two incoming values.
if (Phi->getParent() != TheLoop->getHeader() ||
    Phi->getNumIncomingValues() != 2)
  return false;

// Ensure the loop has a preheader and a single latch block. The loop
// vectorizer will need the latch to set up the next iteration of the loop.
auto *Preheader = TheLoop->getLoopPreheader();
auto *Latch = TheLoop->getLoopLatch();
if (!Preheader || !Latch)
  return false;

// Ensure the phi node's incoming blocks are the loop preheader and latch.
if (Phi->getBasicBlockIndex(Preheader) < 0 ||
    Phi->getBasicBlockIndex(Latch) < 0)
  return false;

// Get the previous value. The previous value comes from the latch edge while
// the initial value comes from the preheader edge.
auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));

// If Previous is a phi in the header, go through incoming values from the
// latch until we find a non-phi value. Use this as the new Previous, all uses
// in the header will be dominated by the original phi, but need to be moved
// after the non-phi previous value.
SmallPtrSet<PHINode *, 4> SeenPhis;
while (auto *PrevPhi = dyn_cast_or_null<PHINode>(Previous)) {
  if (PrevPhi->getParent() != Phi->getParent())
    return false;
  if (!SeenPhis.insert(PrevPhi).second)
    return false;
  Previous = dyn_cast<Instruction>(PrevPhi->getIncomingValueForBlock(Latch));
}

if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous))
  return false;

// Ensure every user of the phi node (recursively) is dominated by the
// previous value. The dominance requirement ensures the loop vectorizer will
// not need to vectorize the initial value prior to the first iteration of the
// loop.
// TODO: Consider extending this sinking to handle memory instructions.

SmallPtrSet<Value *, 8> Seen;
BasicBlock *PhiBB = Phi->getParent();
SmallVector<Instruction *, 8> WorkList;
auto TryToPushSinkCandidate = [&](Instruction *SinkCandidate) {
  // Cyclic dependence.
  if (Previous == SinkCandidate)
    return false;

  if (!Seen.insert(SinkCandidate).second)
    return true;
  if (DT->dominates(Previous,
                    SinkCandidate)) // We already are good w/o sinking.
    return true;

  if (SinkCandidate->getParent() != PhiBB ||
      SinkCandidate->mayHaveSideEffects() ||
      SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())
    return false;

  // If we reach a PHI node that is not dominated by Previous, we reached a
  // header PHI. No need for sinking.
  if (isa<PHINode>(SinkCandidate))
    return true;

  // Sink User tentatively and check its users
  WorkList.push_back(SinkCandidate);
  return true;
};

WorkList.push_back(Phi);
// Try to recursively sink instructions and their users after Previous.
while (!WorkList.empty()) {
  Instruction *Current = WorkList.pop_back_val();
  for (User *User : Current->users()) {
    if (!TryToPushSinkCandidate(cast<Instruction>(User)))
      return false;
  }
}

return true;
1016}

1018/// This function returns the identity element (or neutral element) for
1019/// the operation K.
1020Value *RecurrenceDescriptor::getRecurrenceIdentity(RecurKind K, Type *Tp,
                                                 FastMathFlags FMF) const {
switch (K) {
case RecurKind::Xor:
case RecurKind::Add:
case RecurKind::Or:
  // Adding, Xoring, Oring zero to a number does not change it.
  return ConstantInt::get(Tp, 0);
case RecurKind::Mul:
  // Multiplying a number by 1 does not change it.
  return ConstantInt::get(Tp, 1);
case RecurKind::And:
  // AND-ing a number with an all-1 value does not change it.
  return ConstantInt::get(Tp, -1, true);
case RecurKind::FMul:
  // Multiplying a number by 1 does not change it.
  return ConstantFP::get(Tp, 1.0L);
case RecurKind::FMulAdd:
case RecurKind::FAdd:
  // Adding zero to a number does not change it.
  // FIXME: Ideally we should not need to check FMF for FAdd and should always
  // use -0.0. However, this will currently result in mixed vectors of 0.0/-0.0.
  // Instead, we should ensure that 1) the FMF from FAdd are propagated to the PHI
  // nodes where possible, and 2) PHIs with the nsz flag + -0.0 use 0.0. This would
  // mean we can then remove the check for noSignedZeros() below (see D98963).
  if (FMF.noSignedZeros())
    return ConstantFP::get(Tp, 0.0L);
  return ConstantFP::get(Tp, -0.0L);
case RecurKind::UMin:
  return ConstantInt::get(Tp, -1, true);
case RecurKind::UMax:
  return ConstantInt::get(Tp, 0);
case RecurKind::SMin:
  return ConstantInt::get(Tp,
                          APInt::getSignedMaxValue(Tp->getIntegerBitWidth()));
case RecurKind::SMax:
  return ConstantInt::get(Tp,
                          APInt::getSignedMinValue(Tp->getIntegerBitWidth()));
case RecurKind::FMin:
  assert((FMF.noNaNs() && FMF.noSignedZeros()) &&(static_cast <bool> ((FMF.noNaNs() && FMF.noSignedZeros
()) && "nnan, nsz is expected to be set for FP min reduction."
) ? void (0) : __assert_fail ("(FMF.noNaNs() && FMF.noSignedZeros()) && \"nnan, nsz is expected to be set for FP min reduction.\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1060, __extension__ __PRETTY_FUNCTION__
))
         "nnan, nsz is expected to be set for FP min reduction.")(static_cast <bool> ((FMF.noNaNs() && FMF.noSignedZeros
()) && "nnan, nsz is expected to be set for FP min reduction."
) ? void (0) : __assert_fail ("(FMF.noNaNs() && FMF.noSignedZeros()) && \"nnan, nsz is expected to be set for FP min reduction.\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1060, __extension__ __PRETTY_FUNCTION__
));
  return ConstantFP::getInfinity(Tp, false /*Negative*/);
case RecurKind::FMax:
  assert((FMF.noNaNs() && FMF.noSignedZeros()) &&(static_cast <bool> ((FMF.noNaNs() && FMF.noSignedZeros
()) && "nnan, nsz is expected to be set for FP max reduction."
) ? void (0) : __assert_fail ("(FMF.noNaNs() && FMF.noSignedZeros()) && \"nnan, nsz is expected to be set for FP max reduction.\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1064, __extension__ __PRETTY_FUNCTION__
))
         "nnan, nsz is expected to be set for FP max reduction.")(static_cast <bool> ((FMF.noNaNs() && FMF.noSignedZeros
()) && "nnan, nsz is expected to be set for FP max reduction."
) ? void (0) : __assert_fail ("(FMF.noNaNs() && FMF.noSignedZeros()) && \"nnan, nsz is expected to be set for FP max reduction.\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1064, __extension__ __PRETTY_FUNCTION__
));
  return ConstantFP::getInfinity(Tp, true /*Negative*/);
case RecurKind::SelectICmp:
case RecurKind::SelectFCmp:
  return getRecurrenceStartValue();
  break;
default:
  llvm_unreachable("Unknown recurrence kind")::llvm::llvm_unreachable_internal("Unknown recurrence kind", "llvm/lib/Analysis/IVDescriptors.cpp"
, 1071);
}
1073}

1075unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
switch (Kind) {
case RecurKind::Add:
  return Instruction::Add;
case RecurKind::Mul:
  return Instruction::Mul;
case RecurKind::Or:
  return Instruction::Or;
case RecurKind::And:
  return Instruction::And;
case RecurKind::Xor:
  return Instruction::Xor;
case RecurKind::FMul:
  return Instruction::FMul;
case RecurKind::FMulAdd:
case RecurKind::FAdd:
  return Instruction::FAdd;
case RecurKind::SMax:
case RecurKind::SMin:
case RecurKind::UMax:
case RecurKind::UMin:
case RecurKind::SelectICmp:
  return Instruction::ICmp;
case RecurKind::FMax:
case RecurKind::FMin:
case RecurKind::SelectFCmp:
  return Instruction::FCmp;
default:
  llvm_unreachable("Unknown recurrence operation")::llvm::llvm_unreachable_internal("Unknown recurrence operation"
, "llvm/lib/Analysis/IVDescriptors.cpp", 1103);
}
1105}

1107SmallVector<Instruction *, 4>
1108RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const {
SmallVector<Instruction *, 4> ReductionOperations;
unsigned RedOp = getOpcode(Kind);

// Search down from the Phi to the LoopExitInstr, looking for instructions
// with a single user of the correct type for the reduction.

// Note that we check that the type of the operand is correct for each item in
// the chain, including the last (the loop exit value). This can come up from
// sub, which would otherwise be treated as an add reduction. MinMax also need
// to check for a pair of icmp/select, for which we use getNextInstruction and
// isCorrectOpcode functions to step the right number of instruction, and
// check the icmp/select pair.
// FIXME: We also do not attempt to look through Select's yet, which might
// be part of the reduction chain, or attempt to looks through And's to find a
// smaller bitwidth. Subs are also currently not allowed (which are usually
// treated as part of a add reduction) as they are expected to generally be
// more expensive than out-of-loop reductions, and need to be costed more
// carefully.
unsigned ExpectedUses = 1;
if (RedOp0.1
'RedOp' is equal to ICmp
 == Instruction::ICmp || RedOp == Instruction::FCmp)
  ExpectedUses = 2;

auto getNextInstruction = [&](Instruction *Cur) -> Instruction * {
  for (auto *User : Cur->users()) {
    Instruction *UI = cast<Instruction>(User);
    if (isa<PHINode>(UI))
      continue;
    if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
      // We are expecting a icmp/select pair, which we go to the next select
      // instruction if we can. We already know that Cur has 2 uses.
      if (isa<SelectInst>(UI))
        return UI;
      continue;
    }
    return UI;
  }
  return nullptr;
};
auto isCorrectOpcode = [&](Instruction *Cur) {
  if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {
    Value *LHS, *RHS;
    return SelectPatternResult::isMinOrMax(
        matchSelectPattern(Cur, LHS, RHS).Flavor);
  }
  // Recognize a call to the llvm.fmuladd intrinsic.
  if (isFMulAddIntrinsic(Cur))
    return true;

  return Cur->getOpcode() == RedOp;
};

// Attempt to look through Phis which are part of the reduction chain
unsigned ExtraPhiUses = 0;
Instruction *RdxInstr = LoopExitInstr;
if (auto ExitPhi1.1
'ExitPhi' is non-null
 = dyn_cast<PHINode>(LoopExitInstr)) {
1
Assuming field 'LoopExitInstr' is a 'CastReturnType'→
2
←
Taking true branch→
  if (ExitPhi->getNumIncomingValues() != 2)
3
←
Assuming the condition is false→
4
←
Taking false branch→
    return {};

  Instruction *Inc0 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(0));
5
←
Assuming the object is not a 'CastReturnType'→
  Instruction *Inc1 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(1));

  Instruction *Chain = nullptr;
  if (Inc0 == Phi)
6
←
Assuming 'Inc0' is equal to 'Phi'→
7
←
Taking true branch→
    Chain = Inc1;
  else if (Inc1 == Phi)
    Chain = Inc0;
  else
    return {};

  RdxInstr = Chain;
  ExtraPhiUses = 1;
}

// The loop exit instruction we check first (as a quick test) but add last. We
// check the opcode is correct (and dont allow them to be Subs) and that they
// have expected to have the expected number of uses. They will have one use
// from the phi and one from a LCSSA value, no matter the type.
if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->hasNUses(2))
8
←
Assuming the condition is false→
9
←
Taking false branch→
  return {};

// Check that the Phi has one (or two for min/max) uses, plus an extra use
// for conditional reductions.
if (!Phi->hasNUses(ExpectedUses + ExtraPhiUses))
10
←
Called C++ object pointer is null
  return {};

Instruction *Cur = getNextInstruction(Phi);

// Each other instruction in the chain should have the expected number of uses
// and be the correct opcode.
while (Cur != RdxInstr) {
  if (!Cur || !isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses))
    return {};

  ReductionOperations.push_back(Cur);
  Cur = getNextInstruction(Cur);
}

ReductionOperations.push_back(Cur);
return ReductionOperations;
1208}

1210InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
                                       const SCEV *Step, BinaryOperator *BOp,
                                       Type *ElementType,
                                       SmallVectorImpl<Instruction *> *Casts)
  : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp),
    ElementType(ElementType) {
assert(IK != IK_NoInduction && "Not an induction")(static_cast <bool> (IK != IK_NoInduction && "Not an induction"
) ? void (0) : __assert_fail ("IK != IK_NoInduction && \"Not an induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1216, __extension__ __PRETTY_FUNCTION__
));

// Start value type should match the induction kind and the value
// itself should not be null.
assert(StartValue && "StartValue is null")(static_cast <bool> (StartValue && "StartValue is null"
) ? void (0) : __assert_fail ("StartValue && \"StartValue is null\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1220, __extension__ __PRETTY_FUNCTION__
));
assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&(static_cast <bool> ((IK != IK_PtrInduction || StartValue
->getType()->isPointerTy()) && "StartValue is not a pointer for pointer induction"
) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && \"StartValue is not a pointer for pointer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1222, __extension__ __PRETTY_FUNCTION__
))
       "StartValue is not a pointer for pointer induction")(static_cast <bool> ((IK != IK_PtrInduction || StartValue
->getType()->isPointerTy()) && "StartValue is not a pointer for pointer induction"
) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && \"StartValue is not a pointer for pointer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1222, __extension__ __PRETTY_FUNCTION__
));
assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&(static_cast <bool> ((IK != IK_IntInduction || StartValue
->getType()->isIntegerTy()) && "StartValue is not an integer for integer induction"
) ? void (0) : __assert_fail ("(IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && \"StartValue is not an integer for integer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1224, __extension__ __PRETTY_FUNCTION__
))
       "StartValue is not an integer for integer induction")(static_cast <bool> ((IK != IK_IntInduction || StartValue
->getType()->isIntegerTy()) && "StartValue is not an integer for integer induction"
) ? void (0) : __assert_fail ("(IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && \"StartValue is not an integer for integer induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1224, __extension__ __PRETTY_FUNCTION__
));

// Check the Step Value. It should be non-zero integer value.
assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&(static_cast <bool> ((!getConstIntStepValue() || !getConstIntStepValue
()->isZero()) && "Step value is zero") ? void (0) :
 __assert_fail ("(!getConstIntStepValue() || !getConstIntStepValue()->isZero()) && \"Step value is zero\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1228, __extension__ __PRETTY_FUNCTION__
))
       "Step value is zero")(static_cast <bool> ((!getConstIntStepValue() || !getConstIntStepValue
()->isZero()) && "Step value is zero") ? void (0) :
 __assert_fail ("(!getConstIntStepValue() || !getConstIntStepValue()->isZero()) && \"Step value is zero\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1228, __extension__ __PRETTY_FUNCTION__
));

assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&(static_cast <bool> ((IK == IK_FpInduction || Step->
getType()->isIntegerTy()) && "StepValue is not an integer"
) ? void (0) : __assert_fail ("(IK == IK_FpInduction || Step->getType()->isIntegerTy()) && \"StepValue is not an integer\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1231, __extension__ __PRETTY_FUNCTION__
))
       "StepValue is not an integer")(static_cast <bool> ((IK == IK_FpInduction || Step->
getType()->isIntegerTy()) && "StepValue is not an integer"
) ? void (0) : __assert_fail ("(IK == IK_FpInduction || Step->getType()->isIntegerTy()) && \"StepValue is not an integer\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1231, __extension__ __PRETTY_FUNCTION__
));

assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&(static_cast <bool> ((IK != IK_FpInduction || Step->
getType()->isFloatingPointTy()) && "StepValue is not FP for FpInduction"
) ? void (0) : __assert_fail ("(IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) && \"StepValue is not FP for FpInduction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1234, __extension__ __PRETTY_FUNCTION__
))
       "StepValue is not FP for FpInduction")(static_cast <bool> ((IK != IK_FpInduction || Step->
getType()->isFloatingPointTy()) && "StepValue is not FP for FpInduction"
) ? void (0) : __assert_fail ("(IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) && \"StepValue is not FP for FpInduction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1234, __extension__ __PRETTY_FUNCTION__
));
assert((IK != IK_FpInduction ||(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
 && (InductionBinOp->getOpcode() == Instruction::FAdd
 || InductionBinOp->getOpcode() == Instruction::FSub))) &&
 "Binary opcode should be specified for FP induction") ? void
 (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__
))
        (InductionBinOp &&(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
 && (InductionBinOp->getOpcode() == Instruction::FAdd
 || InductionBinOp->getOpcode() == Instruction::FSub))) &&
 "Binary opcode should be specified for FP induction") ? void
 (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__
))
         (InductionBinOp->getOpcode() == Instruction::FAdd ||(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
 && (InductionBinOp->getOpcode() == Instruction::FAdd
 || InductionBinOp->getOpcode() == Instruction::FSub))) &&
 "Binary opcode should be specified for FP induction") ? void
 (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__
))
          InductionBinOp->getOpcode() == Instruction::FSub))) &&(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
 && (InductionBinOp->getOpcode() == Instruction::FAdd
 || InductionBinOp->getOpcode() == Instruction::FSub))) &&
 "Binary opcode should be specified for FP induction") ? void
 (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__
))
       "Binary opcode should be specified for FP induction")(static_cast <bool> ((IK != IK_FpInduction || (InductionBinOp
 && (InductionBinOp->getOpcode() == Instruction::FAdd
 || InductionBinOp->getOpcode() == Instruction::FSub))) &&
 "Binary opcode should be specified for FP induction") ? void
 (0) : __assert_fail ("(IK != IK_FpInduction || (InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub))) && \"Binary opcode should be specified for FP induction\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1239, __extension__ __PRETTY_FUNCTION__
));

if (IK == IK_PtrInduction)
  assert(ElementType && "Pointer induction must have element type")(static_cast <bool> (ElementType && "Pointer induction must have element type"
) ? void (0) : __assert_fail ("ElementType && \"Pointer induction must have element type\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1242, __extension__ __PRETTY_FUNCTION__
));
else
  assert(!ElementType && "Non-pointer induction cannot have element type")(static_cast <bool> (!ElementType && "Non-pointer induction cannot have element type"
) ? void (0) : __assert_fail ("!ElementType && \"Non-pointer induction cannot have element type\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1244, __extension__ __PRETTY_FUNCTION__
));

if (Casts) {
  for (auto &Inst : *Casts) {
    RedundantCasts.push_back(Inst);
  }
}
1251}

1253ConstantInt *InductionDescriptor::getConstIntStepValue() const {
if (isa<SCEVConstant>(Step))
  return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
return nullptr;
1257}

1259bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
                                         ScalarEvolution *SE,
                                         InductionDescriptor &D) {

// Here we only handle FP induction variables.
assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type")(static_cast <bool> (Phi->getType()->isFloatingPointTy
() && "Unexpected Phi type") ? void (0) : __assert_fail
 ("Phi->getType()->isFloatingPointTy() && \"Unexpected Phi type\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1264, __extension__ __PRETTY_FUNCTION__
));

if (TheLoop->getHeader() != Phi->getParent())
  return false;

// The loop may have multiple entrances or multiple exits; we can analyze
// this phi if it has a unique entry value and a unique backedge value.
if (Phi->getNumIncomingValues() != 2)
  return false;
Value *BEValue = nullptr, *StartValue = nullptr;
if (TheLoop->contains(Phi->getIncomingBlock(0))) {
  BEValue = Phi->getIncomingValue(0);
  StartValue = Phi->getIncomingValue(1);
} else {
  assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&(static_cast <bool> (TheLoop->contains(Phi->getIncomingBlock
(1)) && "Unexpected Phi node in the loop") ? void (0)
 : __assert_fail ("TheLoop->contains(Phi->getIncomingBlock(1)) && \"Unexpected Phi node in the loop\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1279, __extension__ __PRETTY_FUNCTION__
))
         "Unexpected Phi node in the loop")(static_cast <bool> (TheLoop->contains(Phi->getIncomingBlock
(1)) && "Unexpected Phi node in the loop") ? void (0)
 : __assert_fail ("TheLoop->contains(Phi->getIncomingBlock(1)) && \"Unexpected Phi node in the loop\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1279, __extension__ __PRETTY_FUNCTION__
));
  BEValue = Phi->getIncomingValue(1);
  StartValue = Phi->getIncomingValue(0);
}

BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
if (!BOp)
  return false;

Value *Addend = nullptr;
if (BOp->getOpcode() == Instruction::FAdd) {
  if (BOp->getOperand(0) == Phi)
    Addend = BOp->getOperand(1);
  else if (BOp->getOperand(1) == Phi)
    Addend = BOp->getOperand(0);
} else if (BOp->getOpcode() == Instruction::FSub)
  if (BOp->getOperand(0) == Phi)
    Addend = BOp->getOperand(1);

if (!Addend)
  return false;

// The addend should be loop invariant
if (auto *I = dyn_cast<Instruction>(Addend))
  if (TheLoop->contains(I))
    return false;

// FP Step has unknown SCEV
const SCEV *Step = SE->getUnknown(Addend);
D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp);
return true;
1310}

1312/// This function is called when we suspect that the update-chain of a phi node
1313/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
1314/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
1315/// predicate P under which the SCEV expression for the phi can be the
1316/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
1317/// cast instructions that are involved in the update-chain of this induction.
1318/// A caller that adds the required runtime predicate can be free to drop these
1319/// cast instructions, and compute the phi using \p AR (instead of some scev
1320/// expression with casts).
1321///
1322/// For example, without a predicate the scev expression can take the following
1323/// form:
1324///      (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
1325///
1326/// It corresponds to the following IR sequence:
1327/// %for.body:
1328///   %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
1329///   %casted_phi = "ExtTrunc i64 %x"
1330///   %add = add i64 %casted_phi, %step
1331///
1332/// where %x is given in \p PN,
1333/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
1334/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
1335/// several forms, for example, such as:
1336///   ExtTrunc1:    %casted_phi = and  %x, 2^n-1
1337/// or:
1338///   ExtTrunc2:    %t = shl %x, m
1339///                 %casted_phi = ashr %t, m
1340///
1341/// If we are able to find such sequence, we return the instructions
1342/// we found, namely %casted_phi and the instructions on its use-def chain up
1343/// to the phi (not including the phi).
1344static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
                                  const SCEVUnknown *PhiScev,
                                  const SCEVAddRecExpr *AR,
                                  SmallVectorImpl<Instruction *> &CastInsts) {

assert(CastInsts.empty() && "CastInsts is expected to be empty.")(static_cast <bool> (CastInsts.empty() && "CastInsts is expected to be empty."
) ? void (0) : __assert_fail ("CastInsts.empty() && \"CastInsts is expected to be empty.\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1349, __extension__ __PRETTY_FUNCTION__
));
auto *PN = cast<PHINode>(PhiScev->getValue());
assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression")(static_cast <bool> (PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression"
) ? void (0) : __assert_fail ("PSE.getSCEV(PN) == AR && \"Unexpected phi node SCEV expression\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1351, __extension__ __PRETTY_FUNCTION__
));
const Loop *L = AR->getLoop();

// Find any cast instructions that participate in the def-use chain of
// PhiScev in the loop.
// FORNOW/TODO: We currently expect the def-use chain to include only
// two-operand instructions, where one of the operands is an invariant.
// createAddRecFromPHIWithCasts() currently does not support anything more
// involved than that, so we keep the search simple. This can be
// extended/generalized as needed.

auto getDef = [&](const Value *Val) -> Value * {
  const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val);
  if (!BinOp)
    return nullptr;
  Value *Op0 = BinOp->getOperand(0);
  Value *Op1 = BinOp->getOperand(1);
  Value *Def = nullptr;
  if (L->isLoopInvariant(Op0))
    Def = Op1;
  else if (L->isLoopInvariant(Op1))
    Def = Op0;
  return Def;
};

// Look for the instruction that defines the induction via the
// loop backedge.
BasicBlock *Latch = L->getLoopLatch();
if (!Latch)
  return false;
Value *Val = PN->getIncomingValueForBlock(Latch);
if (!Val)
  return false;

// Follow the def-use chain until the induction phi is reached.
// If on the way we encounter a Value that has the same SCEV Expr as the
// phi node, we can consider the instructions we visit from that point
// as part of the cast-sequence that can be ignored.
bool InCastSequence = false;
auto *Inst = dyn_cast<Instruction>(Val);
while (Val != PN) {
  // If we encountered a phi node other than PN, or if we left the loop,
  // we bail out.
  if (!Inst || !L->contains(Inst)) {
    return false;
  }
  auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val));
  if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR))
    InCastSequence = true;
  if (InCastSequence) {
    // Only the last instruction in the cast sequence is expected to have
    // uses outside the induction def-use chain.
    if (!CastInsts.empty())
      if (!Inst->hasOneUse())
        return false;
    CastInsts.push_back(Inst);
  }
  Val = getDef(Val);
  if (!Val)
    return false;
  Inst = dyn_cast<Instruction>(Val);
}

return InCastSequence;
1415}

1417bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
                                       PredicatedScalarEvolution &PSE,
                                       InductionDescriptor &D, bool Assume) {
Type *PhiTy = Phi->getType();

// Handle integer and pointer inductions variables.
// Now we handle also FP induction but not trying to make a
// recurrent expression from the PHI node in-place.

if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&
    !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
  return false;

if (PhiTy->isFloatingPointTy())
  return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D);

const SCEV *PhiScev = PSE.getSCEV(Phi);
const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);

// We need this expression to be an AddRecExpr.
if (Assume && !AR)
  AR = PSE.getAsAddRec(Phi);

if (!AR) {
  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: PHI is not a poly recurrence.\n"
; } } while (false);
  return false;
}

// Record any Cast instructions that participate in the induction update
const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev);
// If we started from an UnknownSCEV, and managed to build an addRecurrence
// only after enabling Assume with PSCEV, this means we may have encountered
// cast instructions that required adding a runtime check in order to
// guarantee the correctness of the AddRecurrence respresentation of the
// induction.
if (PhiScev != AR && SymbolicPhi) {
  SmallVector<Instruction *, 2> Casts;
  if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts))
    return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts);
}

return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
1459}

1461bool InductionDescriptor::isInductionPHI(
  PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
  InductionDescriptor &D, const SCEV *Expr,
  SmallVectorImpl<Instruction *> *CastsToIgnore) {
Type *PhiTy = Phi->getType();
// We only handle integer and pointer inductions variables.
if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
  return false;

// Check that the PHI is consecutive.
const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);

if (!AR) {
  LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: PHI is not a poly recurrence.\n"
; } } while (false);
  return false;
}

if (AR->getLoop() != TheLoop) {
  // FIXME: We should treat this as a uniform. Unfortunately, we
  // don't currently know how to handled uniform PHIs.
  LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n"
; } } while (false)
      dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iv-descriptors")) { dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n"
; } } while (false);
  return false;
}

// This function assumes that InductionPhi is called only on Phi nodes
// present inside loop headers. Check for the same, and throw an assert if
// the current Phi is not present inside the loop header.
assert(Phi->getParent() == AR->getLoop()->getHeader()(static_cast <bool> (Phi->getParent() == AR->getLoop
()->getHeader() && "Invalid Phi node, not present in loop header"
) ? void (0) : __assert_fail ("Phi->getParent() == AR->getLoop()->getHeader() && \"Invalid Phi node, not present in loop header\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1491, __extension__ __PRETTY_FUNCTION__
))
  && "Invalid Phi node, not present in loop header")(static_cast <bool> (Phi->getParent() == AR->getLoop
()->getHeader() && "Invalid Phi node, not present in loop header"
) ? void (0) : __assert_fail ("Phi->getParent() == AR->getLoop()->getHeader() && \"Invalid Phi node, not present in loop header\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1491, __extension__ __PRETTY_FUNCTION__
));

Value *StartValue =
    Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());

BasicBlock *Latch = AR->getLoop()->getLoopLatch();
if (!Latch)
  return false;

const SCEV *Step = AR->getStepRecurrence(*SE);
// Calculate the pointer stride and check if it is consecutive.
// The stride may be a constant or a loop invariant integer value.
const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
  return false;

if (PhiTy->isIntegerTy()) {
  BinaryOperator *BOp =
      dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
  D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
                          /* ElementType */ nullptr, CastsToIgnore);
  return true;
}

assert(PhiTy->isPointerTy() && "The PHI must be a pointer")(static_cast <bool> (PhiTy->isPointerTy() &&
 "The PHI must be a pointer") ? void (0) : __assert_fail ("PhiTy->isPointerTy() && \"The PHI must be a pointer\""
, "llvm/lib/Analysis/IVDescriptors.cpp", 1515, __extension__ __PRETTY_FUNCTION__
));
PointerType *PtrTy = cast<PointerType>(PhiTy);

// Always use i8 element type for opaque pointer inductions.
// This allows induction variables w/non-constant steps.
if (PtrTy->isOpaque()) {
  D = InductionDescriptor(StartValue, IK_PtrInduction, Step,
                          /* BinOp */ nullptr,
                          Type::getInt8Ty(PtrTy->getContext()));
  return true;
}

// Pointer induction should be a constant.
// TODO: This could be generalized, but should probably just
// be dropped instead once the migration to opaque ptrs is
// complete.
if (!ConstStep)
  return false;

Type *ElementType = PtrTy->getNonOpaquePointerElementType();
if (!ElementType->isSized())
  return false;

ConstantInt *CV = ConstStep->getValue();
const DataLayout &DL = Phi->getModule()->getDataLayout();
TypeSize TySize = DL.getTypeAllocSize(ElementType);
// TODO: We could potentially support this for scalable vectors if we can
// prove at compile time that the constant step is always a multiple of
// the scalable type.
if (TySize.isZero() || TySize.isScalable())
  return false;

int64_t Size = static_cast<int64_t>(TySize.getFixedValue());
int64_t CVSize = CV->getSExtValue();
if (CVSize % Size)
  return false;
auto *StepValue =
    SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue,
                        /* BinOp */ nullptr, ElementType);
return true;
1556}