/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp

Bug Summary

File:	lib/Transforms/Utils/LoopUtils.cpp
Warning:	line 1679, column 1 Potential memory leak

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoopUtils.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -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 -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/Transforms/Utils -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp

/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp

→

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//===----------------------------------------------------------------------===//

14#include "llvm/Transforms/Utils/LoopUtils.h"
15#include "llvm/ADT/ScopeExit.h"
16#include "llvm/Analysis/AliasAnalysis.h"
17#include "llvm/Analysis/BasicAliasAnalysis.h"
18#include "llvm/Analysis/GlobalsModRef.h"
19#include "llvm/Analysis/InstructionSimplify.h"
20#include "llvm/Analysis/LoopInfo.h"
21#include "llvm/Analysis/LoopPass.h"
22#include "llvm/Analysis/MustExecute.h"
23#include "llvm/Analysis/ScalarEvolution.h"
24#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
25#include "llvm/Analysis/ScalarEvolutionExpander.h"
26#include "llvm/Analysis/ScalarEvolutionExpressions.h"
27#include "llvm/Analysis/TargetTransformInfo.h"
28#include "llvm/Analysis/ValueTracking.h"
29#include "llvm/IR/Dominators.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/Module.h"
32#include "llvm/IR/PatternMatch.h"
33#include "llvm/IR/ValueHandle.h"
34#include "llvm/Pass.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/KnownBits.h"
37#include "llvm/Transforms/Utils/BasicBlockUtils.h"

39using namespace llvm;
40using namespace llvm::PatternMatch;

42#define DEBUG_TYPE"loop-utils" "loop-utils"

44bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
                                      SmallPtrSetImpl<Instruction *> &Set) {
for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
  if (!Set.count(dyn_cast<Instruction>(*Use)))
    return false;
return true;
50}

52bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
switch (Kind) {
default:
  break;
case RK_IntegerAdd:
case RK_IntegerMult:
case RK_IntegerOr:
case RK_IntegerAnd:
case RK_IntegerXor:
case RK_IntegerMinMax:
  return true;
}
return false;
65}

67bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
69}

71bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
switch (Kind) {
default:
  break;
case RK_IntegerAdd:
case RK_IntegerMult:
case RK_FloatAdd:
case RK_FloatMult:
  return true;
}
return false;
82}

84/// Determines if Phi may have been type-promoted. If Phi has a single user
85/// that ANDs the Phi with a type mask, return the user. RT is updated to
86/// account for the narrower bit width represented by the mask, and the AND
87/// instruction is added to CI.
88static 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;
109}

111/// Compute the minimal bit width needed to represent a reduction whose exit
112/// instruction is given by Exit.
113static 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.countLeadingZeros();
}

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;
    if (!Bits.isNegative())
      // If the value is not known to be negative, we don't known what the
      // upper bit is, and therefore, we don't know what kind of extend we
      // will need. In this case, just increase the bit width by one bit and
      // use sext.
      ++MaxBitWidth;
  }
}
if (!isPowerOf2_64(MaxBitWidth))
  MaxBitWidth = NextPowerOf2(MaxBitWidth);

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

159/// Collect cast instructions that can be ignored in the vectorizer's cost
160/// model, given a reduction exit value and the minimal type in which the
161/// reduction can be represented.
162static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit,
                               Type *RecurrenceType,
                               SmallPtrSetImpl<Instruction *> &Casts) {

SmallVector<Instruction *, 8> Worklist;
SmallPtrSet<Instruction *, 8> Visited;
Worklist.push_back(Exit);

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;
    }

  // 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);
}
189}

191bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
                                         Loop *TheLoop, bool HasFunNoNaNAttr,
                                         RecurrenceDescriptor &RedDes,
                                         DemandedBits *DB,
                                         AssumptionCache *AC,
                                         DominatorTree *DT) {
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;
// 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;
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 (!isIntegerRecurrenceKind(Kind))
    return false;
  if (isArithmeticRecurrenceKind(Kind))
    Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
}

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

// 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 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.back();
  Worklist.pop_back();

  // 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(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
    if (!ReduxDesc.isRecurrence())
      return false;
  }

  // A reduction operation must only have one use of the reduction value.
  if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
      hasMultipleUsesOf(Cur, VisitedInsts))
    return false;

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

  if (Kind == RK_IntegerMinMax &&
      (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
    ++NumCmpSelectPatternInst;
  if (Kind == RK_FloatMinMax && (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);

    // 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
        NonPHIs.push_back(UI);
    } else if (!isa<PHINode>(UI) &&
               ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
                 !isa<SelectInst>(UI)) ||
                !isMinMaxSelectCmpPattern(UI, 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.
if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
    NumCmpSelectPatternInst != 2)
  return false;

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

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., RK_IntegerAND, RK_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;

  // The recurrence expression will be represented in a narrower type. If
  // there are any cast instructions that will be unnecessary, collect them
  // in CastInsts. 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.
  collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts);
}

// 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, Kind, ReduxDesc.getMinMaxKind(),
    ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
RedDes = RD;

return true;
441}

443/// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
444/// pattern corresponding to a min(X, Y) or max(X, Y).
445RecurrenceDescriptor::InstDesc
446RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {

assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&(static_cast <bool> ((isa<ICmpInst>(I) || isa<
FCmpInst>(I) || isa<SelectInst>(I)) && "Expect a select instruction"
) ? void (0) : __assert_fail ("(isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) && \"Expect a select instruction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 449, __extension__ __PRETTY_FUNCTION__))
       "Expect a select instruction")(static_cast <bool> ((isa<ICmpInst>(I) || isa<
FCmpInst>(I) || isa<SelectInst>(I)) && "Expect a select instruction"
) ? void (0) : __assert_fail ("(isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) && \"Expect a select instruction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 449, __extension__ __PRETTY_FUNCTION__));
Instruction *Cmp = nullptr;
SelectInst *Select = nullptr;

// We must handle the select(cmp()) as a single instruction. Advance to the
// select.
if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
  if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
    return InstDesc(false, I);
  return InstDesc(Select, Prev.getMinMaxKind());
}

// Only handle single use cases for now.
if (!(Select = dyn_cast<SelectInst>(I)))
  return InstDesc(false, I);
if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
    !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
  return InstDesc(false, I);
if (!Cmp->hasOneUse())
  return InstDesc(false, I);

Value *CmpLeft;
Value *CmpRight;

// Look for a min/max pattern.
if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
  return InstDesc(Select, MRK_UIntMin);
else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
  return InstDesc(Select, MRK_UIntMax);
else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
  return InstDesc(Select, MRK_SIntMax);
else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
  return InstDesc(Select, MRK_SIntMin);
else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
  return InstDesc(Select, MRK_FloatMin);
else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
  return InstDesc(Select, MRK_FloatMax);
else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
  return InstDesc(Select, MRK_FloatMin);
else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
  return InstDesc(Select, MRK_FloatMax);

return InstDesc(false, I);
492}

494RecurrenceDescriptor::InstDesc
495RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
                                      InstDesc &Prev, bool HasFunNoNaNAttr) {
bool FP = I->getType()->isFloatingPointTy();
Instruction *UAI = Prev.getUnsafeAlgebraInst();
if (!UAI && FP && !I->isFast())
  UAI = I; // Found an unsafe (unvectorizable) algebra instruction.

switch (I->getOpcode()) {
default:
  return InstDesc(false, I);
case Instruction::PHI:
  return InstDesc(I, Prev.getMinMaxKind(), Prev.getUnsafeAlgebraInst());
case Instruction::Sub:
case Instruction::Add:
  return InstDesc(Kind == RK_IntegerAdd, I);
case Instruction::Mul:
  return InstDesc(Kind == RK_IntegerMult, I);
case Instruction::And:
  return InstDesc(Kind == RK_IntegerAnd, I);
case Instruction::Or:
  return InstDesc(Kind == RK_IntegerOr, I);
case Instruction::Xor:
  return InstDesc(Kind == RK_IntegerXor, I);
case Instruction::FMul:
  return InstDesc(Kind == RK_FloatMult, I, UAI);
case Instruction::FSub:
case Instruction::FAdd:
  return InstDesc(Kind == RK_FloatAdd, I, UAI);
case Instruction::FCmp:
case Instruction::ICmp:
case Instruction::Select:
  if (Kind != RK_IntegerMinMax &&
      (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
    return InstDesc(false, I);
  return isMinMaxSelectCmpPattern(I, Prev);
}
531}

533bool RecurrenceDescriptor::hasMultipleUsesOf(
  Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
unsigned NumUses = 0;
for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
     ++Use) {
  if (Insts.count(dyn_cast<Instruction>(*Use)))
    ++NumUses;
  if (NumUses > 1)
    return true;
}

return false;
545}
546bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
                                        RecurrenceDescriptor &RedDes,
                                        DemandedBits *DB, AssumptionCache *AC,
                                        DominatorTree *DT) {

BasicBlock *Header = TheLoop->getHeader();
Function &F = *Header->getParent();
bool HasFunNoNaNAttr =
    F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";

if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
                    AC, DT)) {
  DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "Found an ADD reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
                    AC, DT)) {
  DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "Found a MUL reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes, DB,
                    AC, DT)) {
  DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "Found an OR reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
                    AC, DT)) {
  DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "Found an AND reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes, DB,
                    AC, DT)) {
  DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "Found a XOR reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, RedDes,
                    DB, AC, DT)) {
  DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "Found a MINMAX reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes, DB,
                    AC, DT)) {
  DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "Found an FMult reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes, DB,
                    AC, DT)) {
  DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "Found an FAdd reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
                    AC, DT)) {
  DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "Found an float MINMAX reduction PHI."
 << *Phi << "\n"; } } while (false);
  return true;
}
// Not a reduction of known type.
return false;
603}

605bool RecurrenceDescriptor::isFirstOrderRecurrence(
  PHINode *Phi, Loop *TheLoop,
  DenseMap<Instruction *, Instruction *> &SinkAfter, 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 form the preheader edge.
auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
    SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
  return false;

// Ensure every user of the phi node 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 other kinds of instructions
// and expressions, beyond sinking a single cast past Previous.
if (Phi->hasOneUse()) {
  auto *I = Phi->user_back();
  if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() &&
      DT->dominates(Previous, I->user_back())) {
    if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking.
      SinkAfter[I] = Previous;
    return true;
  }
}

for (User *U : Phi->users())
  if (auto *I = dyn_cast<Instruction>(U)) {
    if (!DT->dominates(Previous, I))
      return false;
  }

return true;
655}

657/// This function returns the identity element (or neutral element) for
658/// the operation K.
659Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
                                                    Type *Tp) {
switch (K) {
case RK_IntegerXor:
case RK_IntegerAdd:
case RK_IntegerOr:
  // Adding, Xoring, Oring zero to a number does not change it.
  return ConstantInt::get(Tp, 0);
case RK_IntegerMult:
  // Multiplying a number by 1 does not change it.
  return ConstantInt::get(Tp, 1);
case RK_IntegerAnd:
  // AND-ing a number with an all-1 value does not change it.
  return ConstantInt::get(Tp, -1, true);
case RK_FloatMult:
  // Multiplying a number by 1 does not change it.
  return ConstantFP::get(Tp, 1.0L);
case RK_FloatAdd:
  // Adding zero to a number does not change it.
  return ConstantFP::get(Tp, 0.0L);
default:
  llvm_unreachable("Unknown recurrence kind")::llvm::llvm_unreachable_internal("Unknown recurrence kind", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 680);
}
682}

684/// This function translates the recurrence kind to an LLVM binary operator.
685unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) {
switch (Kind) {
case RK_IntegerAdd:
  return Instruction::Add;
case RK_IntegerMult:
  return Instruction::Mul;
case RK_IntegerOr:
  return Instruction::Or;
case RK_IntegerAnd:
  return Instruction::And;
case RK_IntegerXor:
  return Instruction::Xor;
case RK_FloatMult:
  return Instruction::FMul;
case RK_FloatAdd:
  return Instruction::FAdd;
case RK_IntegerMinMax:
  return Instruction::ICmp;
case RK_FloatMinMax:
  return Instruction::FCmp;
default:
  llvm_unreachable("Unknown recurrence operation")::llvm::llvm_unreachable_internal("Unknown recurrence operation"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 706);
}
708}

710Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
                                          MinMaxRecurrenceKind RK,
                                          Value *Left, Value *Right) {
CmpInst::Predicate P = CmpInst::ICMP_NE;
switch (RK) {
default:
  llvm_unreachable("Unknown min/max recurrence kind")::llvm::llvm_unreachable_internal("Unknown min/max recurrence kind"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 716);
case MRK_UIntMin:
  P = CmpInst::ICMP_ULT;
  break;
case MRK_UIntMax:
  P = CmpInst::ICMP_UGT;
  break;
case MRK_SIntMin:
  P = CmpInst::ICMP_SLT;
  break;
case MRK_SIntMax:
  P = CmpInst::ICMP_SGT;
  break;
case MRK_FloatMin:
  P = CmpInst::FCMP_OLT;
  break;
case MRK_FloatMax:
  P = CmpInst::FCMP_OGT;
  break;
}

// We only match FP sequences that are 'fast', so we can unconditionally
// set it on any generated instructions.
IRBuilder<>::FastMathFlagGuard FMFG(Builder);
FastMathFlags FMF;
FMF.setFast();
Builder.setFastMathFlags(FMF);

Value *Cmp;
if (RK == MRK_FloatMin || RK == MRK_FloatMax)
  Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
else
  Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");

Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
return Select;
752}

754InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
                                       const SCEV *Step, BinaryOperator *BOp,
                                       SmallVectorImpl<Instruction *> *Casts)
: StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {
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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 758, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 762, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 764, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 764, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 766, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 766, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 770, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 770, __extension__ __PRETTY_FUNCTION__));

assert((IK != IK_PtrInduction || getConstIntStepValue()) &&(static_cast <bool> ((IK != IK_PtrInduction || getConstIntStepValue
()) && "Step value should be constant for pointer induction"
) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || getConstIntStepValue()) && \"Step value should be constant for pointer induction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 773, __extension__ __PRETTY_FUNCTION__))
       "Step value should be constant for pointer induction")(static_cast <bool> ((IK != IK_PtrInduction || getConstIntStepValue
()) && "Step value should be constant for pointer induction"
) ? void (0) : __assert_fail ("(IK != IK_PtrInduction || getConstIntStepValue()) && \"Step value should be constant for pointer induction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 773, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 775, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 775, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 778, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 778, __extension__ __PRETTY_FUNCTION__));
assert((IK != IK_FpInduction || (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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 782, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 782, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 782, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 782, __extension__ __PRETTY_FUNCTION__));

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

791int InductionDescriptor::getConsecutiveDirection() const {
ConstantInt *ConstStep = getConstIntStepValue();
if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
  return ConstStep->getSExtValue();
return 0;
796}

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

804Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index,
                                    ScalarEvolution *SE,
                                    const DataLayout& DL) const {

SCEVExpander Exp(*SE, DL, "induction");
assert(Index->getType() == Step->getType() &&(static_cast <bool> (Index->getType() == Step->getType
() && "Index type does not match StepValue type") ? void
 (0) : __assert_fail ("Index->getType() == Step->getType() && \"Index type does not match StepValue type\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 810, __extension__ __PRETTY_FUNCTION__))
       "Index type does not match StepValue type")(static_cast <bool> (Index->getType() == Step->getType
() && "Index type does not match StepValue type") ? void
 (0) : __assert_fail ("Index->getType() == Step->getType() && \"Index type does not match StepValue type\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 810, __extension__ __PRETTY_FUNCTION__));
switch (IK) {
case IK_IntInduction: {
  assert(Index->getType() == StartValue->getType() &&(static_cast <bool> (Index->getType() == StartValue->
getType() && "Index type does not match StartValue type"
) ? void (0) : __assert_fail ("Index->getType() == StartValue->getType() && \"Index type does not match StartValue type\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 814, __extension__ __PRETTY_FUNCTION__))
         "Index type does not match StartValue type")(static_cast <bool> (Index->getType() == StartValue->
getType() && "Index type does not match StartValue type"
) ? void (0) : __assert_fail ("Index->getType() == StartValue->getType() && \"Index type does not match StartValue type\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 814, __extension__ __PRETTY_FUNCTION__));

  // FIXME: Theoretically, we can call getAddExpr() of ScalarEvolution
  // and calculate (Start + Index * Step) for all cases, without
  // special handling for "isOne" and "isMinusOne".
  // But in the real life the result code getting worse. We mix SCEV
  // expressions and ADD/SUB operations and receive redundant
  // intermediate values being calculated in different ways and
  // Instcombine is unable to reduce them all.

  if (getConstIntStepValue() &&
      getConstIntStepValue()->isMinusOne())
    return B.CreateSub(StartValue, Index);
  if (getConstIntStepValue() &&
      getConstIntStepValue()->isOne())
    return B.CreateAdd(StartValue, Index);
  const SCEV *S = SE->getAddExpr(SE->getSCEV(StartValue),
                                 SE->getMulExpr(Step, SE->getSCEV(Index)));
  return Exp.expandCodeFor(S, StartValue->getType(), &*B.GetInsertPoint());
}
case IK_PtrInduction: {
  assert(isa<SCEVConstant>(Step) &&(static_cast <bool> (isa<SCEVConstant>(Step) &&
 "Expected constant step for pointer induction") ? void (0) :
 __assert_fail ("isa<SCEVConstant>(Step) && \"Expected constant step for pointer induction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 836, __extension__ __PRETTY_FUNCTION__))
         "Expected constant step for pointer induction")(static_cast <bool> (isa<SCEVConstant>(Step) &&
 "Expected constant step for pointer induction") ? void (0) :
 __assert_fail ("isa<SCEVConstant>(Step) && \"Expected constant step for pointer induction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 836, __extension__ __PRETTY_FUNCTION__));
  const SCEV *S = SE->getMulExpr(SE->getSCEV(Index), Step);
  Index = Exp.expandCodeFor(S, Index->getType(), &*B.GetInsertPoint());
  return B.CreateGEP(nullptr, StartValue, Index);
}
case IK_FpInduction: {
  assert(Step->getType()->isFloatingPointTy() && "Expected FP Step value")(static_cast <bool> (Step->getType()->isFloatingPointTy
() && "Expected FP Step value") ? void (0) : __assert_fail
 ("Step->getType()->isFloatingPointTy() && \"Expected FP Step value\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 842, __extension__ __PRETTY_FUNCTION__));
  assert(InductionBinOp &&(static_cast <bool> (InductionBinOp && (InductionBinOp
->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode
() == Instruction::FSub) && "Original bin op should be defined for FP induction"
) ? void (0) : __assert_fail ("InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub) && \"Original bin op should be defined for FP induction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 846, __extension__ __PRETTY_FUNCTION__))
         (InductionBinOp->getOpcode() == Instruction::FAdd ||(static_cast <bool> (InductionBinOp && (InductionBinOp
->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode
() == Instruction::FSub) && "Original bin op should be defined for FP induction"
) ? void (0) : __assert_fail ("InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub) && \"Original bin op should be defined for FP induction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 846, __extension__ __PRETTY_FUNCTION__))
          InductionBinOp->getOpcode() == Instruction::FSub) &&(static_cast <bool> (InductionBinOp && (InductionBinOp
->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode
() == Instruction::FSub) && "Original bin op should be defined for FP induction"
) ? void (0) : __assert_fail ("InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub) && \"Original bin op should be defined for FP induction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 846, __extension__ __PRETTY_FUNCTION__))
         "Original bin op should be defined for FP induction")(static_cast <bool> (InductionBinOp && (InductionBinOp
->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode
() == Instruction::FSub) && "Original bin op should be defined for FP induction"
) ? void (0) : __assert_fail ("InductionBinOp && (InductionBinOp->getOpcode() == Instruction::FAdd || InductionBinOp->getOpcode() == Instruction::FSub) && \"Original bin op should be defined for FP induction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 846, __extension__ __PRETTY_FUNCTION__));

  Value *StepValue = cast<SCEVUnknown>(Step)->getValue();

  // Floating point operations had to be 'fast' to enable the induction.
  FastMathFlags Flags;
  Flags.setFast();

  Value *MulExp = B.CreateFMul(StepValue, Index);
  if (isa<Instruction>(MulExp))
    // We have to check, the MulExp may be a constant.
    cast<Instruction>(MulExp)->setFastMathFlags(Flags);

  Value *BOp = B.CreateBinOp(InductionBinOp->getOpcode() , StartValue,
                             MulExp, "induction");
  if (isa<Instruction>(BOp))
    cast<Instruction>(BOp)->setFastMathFlags(Flags);

  return BOp;
}
case IK_NoInduction:
  return nullptr;
}
llvm_unreachable("invalid enum")::llvm::llvm_unreachable_internal("invalid enum", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 869);
870}

872bool 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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 877, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 892, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 892, __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;
923}

925/// This function is called when we suspect that the update-chain of a phi node
926/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
927/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
928/// predicate P under which the SCEV expression for the phi can be the
929/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
930/// cast instructions that are involved in the update-chain of this induction.
931/// A caller that adds the required runtime predicate can be free to drop these
932/// cast instructions, and compute the phi using \p AR (instead of some scev
933/// expression with casts).
934///
935/// For example, without a predicate the scev expression can take the following
936/// form:
937///      (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
938///
939/// It corresponds to the following IR sequence:
940/// %for.body:
941///   %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
942///   %casted_phi = "ExtTrunc i64 %x"
943///   %add = add i64 %casted_phi, %step
944///
945/// where %x is given in \p PN,
946/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
947/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
948/// several forms, for example, such as:
949///   ExtTrunc1:    %casted_phi = and  %x, 2^n-1
950/// or:
951///   ExtTrunc2:    %t = shl %x, m
952///                 %casted_phi = ashr %t, m
953///
954/// If we are able to find such sequence, we return the instructions
955/// we found, namely %casted_phi and the instructions on its use-def chain up
956/// to the phi (not including the phi).
957static 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.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 962, __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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 964, __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;
1028}

1030bool 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) {
  DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { 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 AddRecurence 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);
1073}

1075bool 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) {
  DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { 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.
  DEBUG(dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n"
; } } while (false);
  return false;
}

Value *StartValue =
  Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
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()) {
  D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/ 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\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1115, __extension__ __PRETTY_FUNCTION__));
// Pointer induction should be a constant.
if (!ConstStep)
  return false;

ConstantInt *CV = ConstStep->getValue();
Type *PointerElementType = PhiTy->getPointerElementType();
// The pointer stride cannot be determined if the pointer element type is not
// sized.
if (!PointerElementType->isSized())
  return false;

const DataLayout &DL = Phi->getModule()->getDataLayout();
int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType));
if (!Size)
  return false;

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);
return true;
1139}

1141bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
                                 bool PreserveLCSSA) {
bool Changed = false;

// We re-use a vector for the in-loop predecesosrs.
SmallVector<BasicBlock *, 4> InLoopPredecessors;

auto RewriteExit = [&](BasicBlock *BB) {
  assert(InLoopPredecessors.empty() &&(static_cast <bool> (InLoopPredecessors.empty() &&
 "Must start with an empty predecessors list!") ? void (0) : __assert_fail
 ("InLoopPredecessors.empty() && \"Must start with an empty predecessors list!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1150, __extension__ __PRETTY_FUNCTION__))
         "Must start with an empty predecessors list!")(static_cast <bool> (InLoopPredecessors.empty() &&
 "Must start with an empty predecessors list!") ? void (0) : __assert_fail
 ("InLoopPredecessors.empty() && \"Must start with an empty predecessors list!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1150, __extension__ __PRETTY_FUNCTION__));
  auto Cleanup = make_scope_exit([&] { InLoopPredecessors.clear(); });

  // See if there are any non-loop predecessors of this exit block and
  // keep track of the in-loop predecessors.
  bool IsDedicatedExit = true;
  for (auto *PredBB : predecessors(BB))
    if (L->contains(PredBB)) {
      if (isa<IndirectBrInst>(PredBB->getTerminator()))
        // We cannot rewrite exiting edges from an indirectbr.
        return false;

      InLoopPredecessors.push_back(PredBB);
    } else {
      IsDedicatedExit = false;
    }

  assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!")(static_cast <bool> (!InLoopPredecessors.empty() &&
 "Must have *some* loop predecessor!") ? void (0) : __assert_fail
 ("!InLoopPredecessors.empty() && \"Must have *some* loop predecessor!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1167, __extension__ __PRETTY_FUNCTION__));

  // Nothing to do if this is already a dedicated exit.
  if (IsDedicatedExit)
    return false;

  auto *NewExitBB = SplitBlockPredecessors(
      BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA);

  if (!NewExitBB)
    DEBUG(dbgs() << "WARNING: Can't create a dedicated exit block for loop: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
 << *L << "\n"; } } while (false)
                 << *L << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
 << *L << "\n"; } } while (false);
  else
    DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "LoopSimplify: Creating dedicated exit block "
 << NewExitBB->getName() << "\n"; } } while (false
)
                 << NewExitBB->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-utils")) { dbgs() << "LoopSimplify: Creating dedicated exit block "
 << NewExitBB->getName() << "\n"; } } while (false
);
  return true;
};

// Walk the exit blocks directly rather than building up a data structure for
// them, but only visit each one once.
SmallPtrSet<BasicBlock *, 4> Visited;
for (auto *BB : L->blocks())
  for (auto *SuccBB : successors(BB)) {
    // We're looking for exit blocks so skip in-loop successors.
    if (L->contains(SuccBB))
      continue;

    // Visit each exit block exactly once.
    if (!Visited.insert(SuccBB).second)
      continue;

    Changed |= RewriteExit(SuccBB);
  }

return Changed;
1202}

1204/// \brief Returns the instructions that use values defined in the loop.
1205SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
SmallVector<Instruction *, 8> UsedOutside;

for (auto *Block : L->getBlocks())
  // FIXME: I believe that this could use copy_if if the Inst reference could
  // be adapted into a pointer.
  for (auto &Inst : *Block) {
    auto Users = Inst.users();
    if (any_of(Users, [&](User *U) {
          auto *Use = cast<Instruction>(U);
          return !L->contains(Use->getParent());
        }))
      UsedOutside.push_back(&Inst);
  }

return UsedOutside;
1221}

1223void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
// By definition, all loop passes need the LoopInfo analysis and the
// Dominator tree it depends on. Because they all participate in the loop
// pass manager, they must also preserve these.
AU.addRequired<DominatorTreeWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();
AU.addRequired<LoopInfoWrapperPass>();
AU.addPreserved<LoopInfoWrapperPass>();

// We must also preserve LoopSimplify and LCSSA. We locally access their IDs
// here because users shouldn't directly get them from this header.
extern char &LoopSimplifyID;
extern char &LCSSAID;
AU.addRequiredID(LoopSimplifyID);
AU.addPreservedID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addPreservedID(LCSSAID);
// This is used in the LPPassManager to perform LCSSA verification on passes
// which preserve lcssa form
AU.addRequired<LCSSAVerificationPass>();
AU.addPreserved<LCSSAVerificationPass>();

// Loop passes are designed to run inside of a loop pass manager which means
// that any function analyses they require must be required by the first loop
// pass in the manager (so that it is computed before the loop pass manager
// runs) and preserved by all loop pasess in the manager. To make this
// reasonably robust, the set needed for most loop passes is maintained here.
// If your loop pass requires an analysis not listed here, you will need to
// carefully audit the loop pass manager nesting structure that results.
AU.addRequired<AAResultsWrapperPass>();
AU.addPreserved<AAResultsWrapperPass>();
AU.addPreserved<BasicAAWrapperPass>();
AU.addPreserved<GlobalsAAWrapperPass>();
AU.addPreserved<SCEVAAWrapperPass>();
AU.addRequired<ScalarEvolutionWrapperPass>();
AU.addPreserved<ScalarEvolutionWrapperPass>();
1259}

1261/// Manually defined generic "LoopPass" dependency initialization. This is used
1262/// to initialize the exact set of passes from above in \c
1263/// getLoopAnalysisUsage. It can be used within a loop pass's initialization
1264/// with:
1265///
1266///   INITIALIZE_PASS_DEPENDENCY(LoopPass)
1267///
1268/// As-if "LoopPass" were a pass.
1269void llvm::initializeLoopPassPass(PassRegistry &Registry) {
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)initializeLoopSimplifyPass(Registry);
INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)initializeLCSSAWrapperPassPass(Registry);
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)initializeBasicAAWrapperPassPass(Registry);
INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)initializeSCEVAAWrapperPassPass(Registry);
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);
1279}

1281/// \brief Find string metadata for loop
1282///
1283/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1284/// operand or null otherwise.  If the string metadata is not found return
1285/// Optional's not-a-value.
1286Optional<const MDOperand *> llvm::findStringMetadataForLoop(Loop *TheLoop,
                                                          StringRef Name) {
MDNode *LoopID = TheLoop->getLoopID();
// Return none if LoopID is false.
if (!LoopID)
  return None;

// First operand should refer to the loop id itself.
assert(LoopID->getNumOperands() > 0 && "requires at least one operand")(static_cast <bool> (LoopID->getNumOperands() > 0
 && "requires at least one operand") ? void (0) : __assert_fail
 ("LoopID->getNumOperands() > 0 && \"requires at least one operand\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1294, __extension__ __PRETTY_FUNCTION__));
assert(LoopID->getOperand(0) == LoopID && "invalid loop id")(static_cast <bool> (LoopID->getOperand(0) == LoopID
 && "invalid loop id") ? void (0) : __assert_fail ("LoopID->getOperand(0) == LoopID && \"invalid loop id\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1295, __extension__ __PRETTY_FUNCTION__));

// Iterate over LoopID operands and look for MDString Metadata
for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
  if (!MD)
    continue;
  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
  if (!S)
    continue;
  // Return true if MDString holds expected MetaData.
  if (Name.equals(S->getString()))
    switch (MD->getNumOperands()) {
    case 1:
      return nullptr;
    case 2:
      return &MD->getOperand(1);
    default:
      llvm_unreachable("loop metadata has 0 or 1 operand")::llvm::llvm_unreachable_internal("loop metadata has 0 or 1 operand"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1313);
    }
}
return None;
1317}

1319/// Does a BFS from a given node to all of its children inside a given loop.
1320/// The returned vector of nodes includes the starting point.
1321SmallVector<DomTreeNode *, 16>
1322llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
SmallVector<DomTreeNode *, 16> Worklist;
auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
  // Only include subregions in the top level loop.
  BasicBlock *BB = DTN->getBlock();
  if (CurLoop->contains(BB))
    Worklist.push_back(DTN);
};

AddRegionToWorklist(N);

for (size_t I = 0; I < Worklist.size(); I++)
  for (DomTreeNode *Child : Worklist[I]->getChildren())
    AddRegionToWorklist(Child);

return Worklist;
1338}

1340void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
                        ScalarEvolution *SE = nullptr,
                        LoopInfo *LI = nullptr) {
assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!")(static_cast <bool> ((!DT || L->isLCSSAForm(*DT)) &&
 "Expected LCSSA!") ? void (0) : __assert_fail ("(!DT || L->isLCSSAForm(*DT)) && \"Expected LCSSA!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1343, __extension__ __PRETTY_FUNCTION__));
auto *Preheader = L->getLoopPreheader();
assert(Preheader && "Preheader should exist!")(static_cast <bool> (Preheader && "Preheader should exist!"
) ? void (0) : __assert_fail ("Preheader && \"Preheader should exist!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1345, __extension__ __PRETTY_FUNCTION__));

// Now that we know the removal is safe, remove the loop by changing the
// branch from the preheader to go to the single exit block.
//
// Because we're deleting a large chunk of code at once, the sequence in which
// we remove things is very important to avoid invalidation issues.

// Tell ScalarEvolution that the loop is deleted. Do this before
// deleting the loop so that ScalarEvolution can look at the loop
// to determine what it needs to clean up.
if (SE)
  SE->forgetLoop(L);

auto *ExitBlock = L->getUniqueExitBlock();
assert(ExitBlock && "Should have a unique exit block!")(static_cast <bool> (ExitBlock && "Should have a unique exit block!"
) ? void (0) : __assert_fail ("ExitBlock && \"Should have a unique exit block!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1360, __extension__ __PRETTY_FUNCTION__));
assert(L->hasDedicatedExits() && "Loop should have dedicated exits!")(static_cast <bool> (L->hasDedicatedExits() &&
 "Loop should have dedicated exits!") ? void (0) : __assert_fail
 ("L->hasDedicatedExits() && \"Loop should have dedicated exits!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1361, __extension__ __PRETTY_FUNCTION__));

auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
assert(OldBr && "Preheader must end with a branch")(static_cast <bool> (OldBr && "Preheader must end with a branch"
) ? void (0) : __assert_fail ("OldBr && \"Preheader must end with a branch\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1364, __extension__ __PRETTY_FUNCTION__));
assert(OldBr->isUnconditional() && "Preheader must have a single successor")(static_cast <bool> (OldBr->isUnconditional() &&
 "Preheader must have a single successor") ? void (0) : __assert_fail
 ("OldBr->isUnconditional() && \"Preheader must have a single successor\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1365, __extension__ __PRETTY_FUNCTION__));
// Connect the preheader to the exit block. Keep the old edge to the header
// around to perform the dominator tree update in two separate steps
// -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
// preheader -> header.
//
//
// 0.  Preheader          1.  Preheader           2.  Preheader
//        |                    |   |                   |
//        V                    |   V                   |
//      Header <--\            | Header <--\           | Header <--\
//       |  |     |            |  |  |     |           |  |  |     |
//       |  V     |            |  |  V     |           |  |  V     |
//       | Body --/            |  | Body --/           |  | Body --/
//       V                     V  V                    V  V
//      Exit                   Exit                    Exit
//
// By doing this is two separate steps we can perform the dominator tree
// update without using the batch update API.
//
// Even when the loop is never executed, we cannot remove the edge from the
// source block to the exit block. Consider the case where the unexecuted loop
// branches back to an outer loop. If we deleted the loop and removed the edge
// coming to this inner loop, this will break the outer loop structure (by
// deleting the backedge of the outer loop). If the outer loop is indeed a
// non-loop, it will be deleted in a future iteration of loop deletion pass.
IRBuilder<> Builder(OldBr);
Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
// Remove the old branch. The conditional branch becomes a new terminator.
OldBr->eraseFromParent();

// Rewrite phis in the exit block to get their inputs from the Preheader
// instead of the exiting block.
for (PHINode &P : ExitBlock->phis()) {
  // Set the zero'th element of Phi to be from the preheader and remove all
  // other incoming values. Given the loop has dedicated exits, all other
  // incoming values must be from the exiting blocks.
  int PredIndex = 0;
  P.setIncomingBlock(PredIndex, Preheader);
  // Removes all incoming values from all other exiting blocks (including
  // duplicate values from an exiting block).
  // Nuke all entries except the zero'th entry which is the preheader entry.
  // NOTE! We need to remove Incoming Values in the reverse order as done
  // below, to keep the indices valid for deletion (removeIncomingValues
  // updates getNumIncomingValues and shifts all values down into the operand
  // being deleted).
  for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i)
    P.removeIncomingValue(e - i, false);

  assert((P.getNumIncomingValues() == 1 &&(static_cast <bool> ((P.getNumIncomingValues() == 1 &&
 P.getIncomingBlock(PredIndex) == Preheader) && "Should have exactly one value and that's from the preheader!"
) ? void (0) : __assert_fail ("(P.getNumIncomingValues() == 1 && P.getIncomingBlock(PredIndex) == Preheader) && \"Should have exactly one value and that's from the preheader!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1416, __extension__ __PRETTY_FUNCTION__))
          P.getIncomingBlock(PredIndex) == Preheader) &&(static_cast <bool> ((P.getNumIncomingValues() == 1 &&
 P.getIncomingBlock(PredIndex) == Preheader) && "Should have exactly one value and that's from the preheader!"
) ? void (0) : __assert_fail ("(P.getNumIncomingValues() == 1 && P.getIncomingBlock(PredIndex) == Preheader) && \"Should have exactly one value and that's from the preheader!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1416, __extension__ __PRETTY_FUNCTION__))
         "Should have exactly one value and that's from the preheader!")(static_cast <bool> ((P.getNumIncomingValues() == 1 &&
 P.getIncomingBlock(PredIndex) == Preheader) && "Should have exactly one value and that's from the preheader!"
) ? void (0) : __assert_fail ("(P.getNumIncomingValues() == 1 && P.getIncomingBlock(PredIndex) == Preheader) && \"Should have exactly one value and that's from the preheader!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1416, __extension__ __PRETTY_FUNCTION__));
}

// Disconnect the loop body by branching directly to its exit.
Builder.SetInsertPoint(Preheader->getTerminator());
Builder.CreateBr(ExitBlock);
// Remove the old branch.
Preheader->getTerminator()->eraseFromParent();

if (DT) {
  // Update the dominator tree by informing it about the new edge from the
  // preheader to the exit.
  DT->insertEdge(Preheader, ExitBlock);
  // Inform the dominator tree about the removed edge.
  DT->deleteEdge(Preheader, L->getHeader());
}

// Given LCSSA form is satisfied, we should not have users of instructions
// within the dead loop outside of the loop. However, LCSSA doesn't take
// unreachable uses into account. We handle them here.
// We could do it after drop all references (in this case all users in the
// loop will be already eliminated and we have less work to do but according
// to API doc of User::dropAllReferences only valid operation after dropping
// references, is deletion. So let's substitute all usages of
// instruction from the loop with undef value of corresponding type first.
for (auto *Block : L->blocks())
  for (Instruction &I : *Block) {
    auto *Undef = UndefValue::get(I.getType());
    for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
      Use &U = *UI;
      ++UI;
      if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
        if (L->contains(Usr->getParent()))
          continue;
      // If we have a DT then we can check that uses outside a loop only in
      // unreachable block.
      if (DT)
        assert(!DT->isReachableFromEntry(U) &&(static_cast <bool> (!DT->isReachableFromEntry(U) &&
 "Unexpected user in reachable block") ? void (0) : __assert_fail
 ("!DT->isReachableFromEntry(U) && \"Unexpected user in reachable block\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1454, __extension__ __PRETTY_FUNCTION__))
               "Unexpected user in reachable block")(static_cast <bool> (!DT->isReachableFromEntry(U) &&
 "Unexpected user in reachable block") ? void (0) : __assert_fail
 ("!DT->isReachableFromEntry(U) && \"Unexpected user in reachable block\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1454, __extension__ __PRETTY_FUNCTION__));
      U.set(Undef);
    }
  }

// Remove the block from the reference counting scheme, so that we can
// delete it freely later.
for (auto *Block : L->blocks())
  Block->dropAllReferences();

if (LI) {
  // Erase the instructions and the blocks without having to worry
  // about ordering because we already dropped the references.
  // NOTE: This iteration is safe because erasing the block does not remove
  // its entry from the loop's block list.  We do that in the next section.
  for (Loop::block_iterator LpI = L->block_begin(), LpE = L->block_end();
       LpI != LpE; ++LpI)
    (*LpI)->eraseFromParent();

  // Finally, the blocks from loopinfo.  This has to happen late because
  // otherwise our loop iterators won't work.

  SmallPtrSet<BasicBlock *, 8> blocks;
  blocks.insert(L->block_begin(), L->block_end());
  for (BasicBlock *BB : blocks)
    LI->removeBlock(BB);

  // The last step is to update LoopInfo now that we've eliminated this loop.
  LI->erase(L);
}
1484}

1486Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
// Only support loops with a unique exiting block, and a latch.
if (!L->getExitingBlock())
  return None;

// Get the branch weights for the loop's backedge.
BranchInst *LatchBR =
    dyn_cast<BranchInst>(L->getLoopLatch()->getTerminator());
if (!LatchBR || LatchBR->getNumSuccessors() != 2)
  return None;

assert((LatchBR->getSuccessor(0) == L->getHeader() ||(static_cast <bool> ((LatchBR->getSuccessor(0) == L->
getHeader() || LatchBR->getSuccessor(1) == L->getHeader
()) && "At least one edge out of the latch must go to the header"
) ? void (0) : __assert_fail ("(LatchBR->getSuccessor(0) == L->getHeader() || LatchBR->getSuccessor(1) == L->getHeader()) && \"At least one edge out of the latch must go to the header\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1499, __extension__ __PRETTY_FUNCTION__))
        LatchBR->getSuccessor(1) == L->getHeader()) &&(static_cast <bool> ((LatchBR->getSuccessor(0) == L->
getHeader() || LatchBR->getSuccessor(1) == L->getHeader
()) && "At least one edge out of the latch must go to the header"
) ? void (0) : __assert_fail ("(LatchBR->getSuccessor(0) == L->getHeader() || LatchBR->getSuccessor(1) == L->getHeader()) && \"At least one edge out of the latch must go to the header\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1499, __extension__ __PRETTY_FUNCTION__))
       "At least one edge out of the latch must go to the header")(static_cast <bool> ((LatchBR->getSuccessor(0) == L->
getHeader() || LatchBR->getSuccessor(1) == L->getHeader
()) && "At least one edge out of the latch must go to the header"
) ? void (0) : __assert_fail ("(LatchBR->getSuccessor(0) == L->getHeader() || LatchBR->getSuccessor(1) == L->getHeader()) && \"At least one edge out of the latch must go to the header\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1499, __extension__ __PRETTY_FUNCTION__));

// To estimate the number of times the loop body was executed, we want to
// know the number of times the backedge was taken, vs. the number of times
// we exited the loop.
uint64_t TrueVal, FalseVal;
if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
  return None;

if (!TrueVal || !FalseVal)
  return 0;

// Divide the count of the backedge by the count of the edge exiting the loop,
// rounding to nearest.
if (LatchBR->getSuccessor(0) == L->getHeader())
  return (TrueVal + (FalseVal / 2)) / FalseVal;
else
  return (FalseVal + (TrueVal / 2)) / TrueVal;
1517}

1519/// \brief Adds a 'fast' flag to floating point operations.
1520static Value *addFastMathFlag(Value *V) {
if (isa<FPMathOperator>(V)) {
  FastMathFlags Flags;
  Flags.setFast();
  cast<Instruction>(V)->setFastMathFlags(Flags);
}
return V;
1527}

1529// Helper to generate an ordered reduction.
1530Value *
1531llvm::getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src,
                        unsigned Op,
                        RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
                        ArrayRef<Value *> RedOps) {
unsigned VF = Src->getType()->getVectorNumElements();

// Extract and apply reduction ops in ascending order:
// e.g. ((((Acc + Scl[0]) + Scl[1]) + Scl[2]) + ) ... + Scl[VF-1]
Value *Result = Acc;
for (unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
  Value *Ext =
      Builder.CreateExtractElement(Src, Builder.getInt32(ExtractIdx));

  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
    Result = Builder.CreateBinOp((Instruction::BinaryOps)Op, Result, Ext,
                                 "bin.rdx");
  } else {
    assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&(static_cast <bool> (MinMaxKind != RecurrenceDescriptor
::MRK_Invalid && "Invalid min/max") ? void (0) : __assert_fail
 ("MinMaxKind != RecurrenceDescriptor::MRK_Invalid && \"Invalid min/max\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1549, __extension__ __PRETTY_FUNCTION__))
           "Invalid min/max")(static_cast <bool> (MinMaxKind != RecurrenceDescriptor
::MRK_Invalid && "Invalid min/max") ? void (0) : __assert_fail
 ("MinMaxKind != RecurrenceDescriptor::MRK_Invalid && \"Invalid min/max\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1549, __extension__ __PRETTY_FUNCTION__));
    Result = RecurrenceDescriptor::createMinMaxOp(Builder, MinMaxKind, Result,
                                                  Ext);
  }

  if (!RedOps.empty())
    propagateIRFlags(Result, RedOps);
}

return Result;
1559}

1561// Helper to generate a log2 shuffle reduction.
1562Value *
1563llvm::getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
                        RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind,
                        ArrayRef<Value *> RedOps) {
unsigned VF = Src->getType()->getVectorNumElements();
// VF is a power of 2 so we can emit the reduction using log2(VF) shuffles
// and vector ops, reducing the set of values being computed by half each
// round.
assert(isPowerOf2_32(VF) &&(static_cast <bool> (isPowerOf2_32(VF) && "Reduction emission only supported for pow2 vectors!"
) ? void (0) : __assert_fail ("isPowerOf2_32(VF) && \"Reduction emission only supported for pow2 vectors!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1571, __extension__ __PRETTY_FUNCTION__))
       "Reduction emission only supported for pow2 vectors!")(static_cast <bool> (isPowerOf2_32(VF) && "Reduction emission only supported for pow2 vectors!"
) ? void (0) : __assert_fail ("isPowerOf2_32(VF) && \"Reduction emission only supported for pow2 vectors!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1571, __extension__ __PRETTY_FUNCTION__));
Value *TmpVec = Src;
SmallVector<Constant *, 32> ShuffleMask(VF, nullptr);
for (unsigned i = VF; i != 1; i >>= 1) {
  // Move the upper half of the vector to the lower half.
  for (unsigned j = 0; j != i / 2; ++j)
    ShuffleMask[j] = Builder.getInt32(i / 2 + j);

  // Fill the rest of the mask with undef.
  std::fill(&ShuffleMask[i / 2], ShuffleMask.end(),
            UndefValue::get(Builder.getInt32Ty()));

  Value *Shuf = Builder.CreateShuffleVector(
      TmpVec, UndefValue::get(TmpVec->getType()),
      ConstantVector::get(ShuffleMask), "rdx.shuf");

  if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
    // Floating point operations had to be 'fast' to enable the reduction.
    TmpVec = addFastMathFlag(Builder.CreateBinOp((Instruction::BinaryOps)Op,
                                                 TmpVec, Shuf, "bin.rdx"));
  } else {
    assert(MinMaxKind != RecurrenceDescriptor::MRK_Invalid &&(static_cast <bool> (MinMaxKind != RecurrenceDescriptor
::MRK_Invalid && "Invalid min/max") ? void (0) : __assert_fail
 ("MinMaxKind != RecurrenceDescriptor::MRK_Invalid && \"Invalid min/max\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1593, __extension__ __PRETTY_FUNCTION__))
           "Invalid min/max")(static_cast <bool> (MinMaxKind != RecurrenceDescriptor
::MRK_Invalid && "Invalid min/max") ? void (0) : __assert_fail
 ("MinMaxKind != RecurrenceDescriptor::MRK_Invalid && \"Invalid min/max\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1593, __extension__ __PRETTY_FUNCTION__));
    TmpVec = RecurrenceDescriptor::createMinMaxOp(Builder, MinMaxKind, TmpVec,
                                                  Shuf);
  }
  if (!RedOps.empty())
    propagateIRFlags(TmpVec, RedOps);
}
// The result is in the first element of the vector.
return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
1602}

1604/// Create a simple vector reduction specified by an opcode and some
1605/// flags (if generating min/max reductions).
1606Value *llvm::createSimpleTargetReduction(
  IRBuilder<> &Builder, const TargetTransformInfo *TTI, unsigned Opcode,
  Value *Src, TargetTransformInfo::ReductionFlags Flags,
  ArrayRef<Value *> RedOps) {
assert(isa<VectorType>(Src->getType()) && "Type must be a vector")(static_cast <bool> (isa<VectorType>(Src->getType
()) && "Type must be a vector") ? void (0) : __assert_fail
 ("isa<VectorType>(Src->getType()) && \"Type must be a vector\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1610, __extension__ __PRETTY_FUNCTION__));

Value *ScalarUdf = UndefValue::get(Src->getType()->getVectorElementType());
std::function<Value*()> BuildFunc;
using RD = RecurrenceDescriptor;
RD::MinMaxRecurrenceKind MinMaxKind = RD::MRK_Invalid;
// TODO: Support creating ordered reductions.
FastMathFlags FMFFast;
FMFFast.setFast();

switch (Opcode) {
3
←
Control jumps to 'case FAdd:'  at line 1636→
case Instruction::Add:
  BuildFunc = [&]() { return Builder.CreateAddReduce(Src); };
  break;
case Instruction::Mul:
  BuildFunc = [&]() { return Builder.CreateMulReduce(Src); };
  break;
case Instruction::And:
  BuildFunc = [&]() { return Builder.CreateAndReduce(Src); };
  break;
case Instruction::Or:
  BuildFunc = [&]() { return Builder.CreateOrReduce(Src); };
  break;
case Instruction::Xor:
  BuildFunc = [&]() { return Builder.CreateXorReduce(Src); };
  break;
case Instruction::FAdd:
  BuildFunc = [&]() {
4
←
Calling 'function::operator='→
13
←
Returned allocated memory→
    auto Rdx = Builder.CreateFAddReduce(ScalarUdf, Src);
    cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
    return Rdx;
  };
  break;
14
←
 Execution continues on line 1676→
case Instruction::FMul:
  BuildFunc = [&]() {
    auto Rdx = Builder.CreateFMulReduce(ScalarUdf, Src);
    cast<CallInst>(Rdx)->setFastMathFlags(FMFFast);
    return Rdx;
  };
  break;
case Instruction::ICmp:
  if (Flags.IsMaxOp) {
    MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMax : RD::MRK_UIntMax;
    BuildFunc = [&]() {
      return Builder.CreateIntMaxReduce(Src, Flags.IsSigned);
    };
  } else {
    MinMaxKind = Flags.IsSigned ? RD::MRK_SIntMin : RD::MRK_UIntMin;
    BuildFunc = [&]() {
      return Builder.CreateIntMinReduce(Src, Flags.IsSigned);
    };
  }
  break;
case Instruction::FCmp:
  if (Flags.IsMaxOp) {
    MinMaxKind = RD::MRK_FloatMax;
    BuildFunc = [&]() { return Builder.CreateFPMaxReduce(Src, Flags.NoNaN); };
  } else {
    MinMaxKind = RD::MRK_FloatMin;
    BuildFunc = [&]() { return Builder.CreateFPMinReduce(Src, Flags.NoNaN); };
  }
  break;
default:
  llvm_unreachable("Unhandled opcode")::llvm::llvm_unreachable_internal("Unhandled opcode", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1673);
  break;
}
if (TTI->useReductionIntrinsic(Opcode, Src->getType(), Flags))
15
←
Assuming the condition is false→
16
←
Taking false branch→
  return BuildFunc();
return getShuffleReduction(Builder, Src, Opcode, MinMaxKind, RedOps);
1679}
17
←
Potential memory leak

1681/// Create a vector reduction using a given recurrence descriptor.
1682Value *llvm::createTargetReduction(IRBuilder<> &B,
                                 const TargetTransformInfo *TTI,
                                 RecurrenceDescriptor &Desc, Value *Src,
                                 bool NoNaN) {
// TODO: Support in-order reductions based on the recurrence descriptor.
using RD = RecurrenceDescriptor;
RD::RecurrenceKind RecKind = Desc.getRecurrenceKind();
TargetTransformInfo::ReductionFlags Flags;
Flags.NoNaN = NoNaN;
switch (RecKind) {
1
Control jumps to 'case RK_FloatAdd:'  at line 1692→
case RD::RK_FloatAdd:
  return createSimpleTargetReduction(B, TTI, Instruction::FAdd, Src, Flags);
2
←
Calling 'createSimpleTargetReduction'→
case RD::RK_FloatMult:
  return createSimpleTargetReduction(B, TTI, Instruction::FMul, Src, Flags);
case RD::RK_IntegerAdd:
  return createSimpleTargetReduction(B, TTI, Instruction::Add, Src, Flags);
case RD::RK_IntegerMult:
  return createSimpleTargetReduction(B, TTI, Instruction::Mul, Src, Flags);
case RD::RK_IntegerAnd:
  return createSimpleTargetReduction(B, TTI, Instruction::And, Src, Flags);
case RD::RK_IntegerOr:
  return createSimpleTargetReduction(B, TTI, Instruction::Or, Src, Flags);
case RD::RK_IntegerXor:
  return createSimpleTargetReduction(B, TTI, Instruction::Xor, Src, Flags);
case RD::RK_IntegerMinMax: {
  RD::MinMaxRecurrenceKind MMKind = Desc.getMinMaxRecurrenceKind();
  Flags.IsMaxOp = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_UIntMax);
  Flags.IsSigned = (MMKind == RD::MRK_SIntMax || MMKind == RD::MRK_SIntMin);
  return createSimpleTargetReduction(B, TTI, Instruction::ICmp, Src, Flags);
}
case RD::RK_FloatMinMax: {
  Flags.IsMaxOp = Desc.getMinMaxRecurrenceKind() == RD::MRK_FloatMax;
  return createSimpleTargetReduction(B, TTI, Instruction::FCmp, Src, Flags);
}
default:
  llvm_unreachable("Unhandled RecKind")::llvm::llvm_unreachable_internal("Unhandled RecKind", "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUtils.cpp"
, 1717);
}
1719}

1721void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue) {
auto *VecOp = dyn_cast<Instruction>(I);
if (!VecOp)
  return;
auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
                                          : dyn_cast<Instruction>(OpValue);
if (!Intersection)
  return;
const unsigned Opcode = Intersection->getOpcode();
VecOp->copyIRFlags(Intersection);
for (auto *V : VL) {
  auto *Instr = dyn_cast<Instruction>(V);
  if (!Instr)
    continue;
  if (OpValue == nullptr || Opcode == Instr->getOpcode())
    VecOp->andIRFlags(V);
}
1738}

←

/usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/bits/std_function.h

1// Implementation of std::function -*- C++ -*-

3// Copyright (C) 2004-2017 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.

20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.

25/** @file include/bits/function.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{functional}
*/

30#ifndef _GLIBCXX_STD_FUNCTION_H1
31#define _GLIBCXX_STD_FUNCTION_H1 1

33#pragma GCC system_header

35#if __cplusplus201103L < 201103L
36# include <bits/c++0x_warning.h>
37#else

39#if __cpp_rtti199711
40# include <typeinfo>
41#endif
42#include <bits/stl_function.h>
43#include <bits/invoke.h>
44#include <bits/refwrap.h>
45#include <bits/functexcept.h>

47namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
48{
49_GLIBCXX_BEGIN_NAMESPACE_VERSION

/**
 * Derives from @c unary_function or @c binary_function, or perhaps
 * nothing, depending on the number of arguments provided. The
 * primary template is the basis case, which derives nothing.
 */
template<typename _Res, typename... _ArgTypes>
  struct _Maybe_unary_or_binary_function { };

/// Derives from @c unary_function, as appropriate.
template<typename _Res, typename _T1>
  struct _Maybe_unary_or_binary_function<_Res, _T1>
  : std::unary_function<_T1, _Res> { };

/// Derives from @c binary_function, as appropriate.
template<typename _Res, typename _T1, typename _T2>
  struct _Maybe_unary_or_binary_function<_Res, _T1, _T2>
  : std::binary_function<_T1, _T2, _Res> { };


/**
 *  @brief Exception class thrown when class template function's
 *  operator() is called with an empty target.
 *  @ingroup exceptions
 */
class bad_function_call : public std::exception
{
public:
  virtual ~bad_function_call() noexcept;

  const char* what() const noexcept;
};

/**
 *  Trait identifying "location-invariant" types, meaning that the
 *  address of the object (or any of its members) will not escape.
 *  Trivially copyable types are location-invariant and users can
 *  specialize this trait for other types.
 */
template<typename _Tp>
  struct __is_location_invariant
  : is_trivially_copyable<_Tp>::type
  { };

class _Undefined_class;

union _Nocopy_types
{
  void*       _M_object;
  const void* _M_const_object;
  void (*_M_function_pointer)();
  void (_Undefined_class::*_M_member_pointer)();
};

union [[gnu::may_alias]] _Any_data
{
  void*       _M_access()       { return &_M_pod_data[0]; }
  const void* _M_access() const { return &_M_pod_data[0]; }

  template<typename _Tp>
    _Tp&
    _M_access()
    { return *static_cast<_Tp*>(_M_access()); }

  template<typename _Tp>
    const _Tp&
    _M_access() const
    { return *static_cast<const _Tp*>(_M_access()); }

  _Nocopy_types _M_unused;
  char _M_pod_data[sizeof(_Nocopy_types)];
};

enum _Manager_operation
{
  __get_type_info,
  __get_functor_ptr,
  __clone_functor,
  __destroy_functor
};

// Simple type wrapper that helps avoid annoying const problems
// when casting between void pointers and pointers-to-pointers.
template<typename _Tp>
  struct _Simple_type_wrapper
  {
    _Simple_type_wrapper(_Tp __value) : __value(__value) { }

    _Tp __value;
  };

template<typename _Tp>
  struct __is_location_invariant<_Simple_type_wrapper<_Tp> >
  : __is_location_invariant<_Tp>
  { };

template<typename _Signature>
  class function;

/// Base class of all polymorphic function object wrappers.
class _Function_base
{
public:
  static const std::size_t _M_max_size = sizeof(_Nocopy_types);
  static const std::size_t _M_max_align = __alignof__(_Nocopy_types);

  template<typename _Functor>
    class _Base_manager
    {
    protected:
static const bool __stored_locally =
(__is_location_invariant<_Functor>::value
&& sizeof(_Functor) <= _M_max_size
&& __alignof__(_Functor) <= _M_max_align
&& (_M_max_align % __alignof__(_Functor) == 0));

typedef integral_constant<bool, __stored_locally> _Local_storage;

// Retrieve a pointer to the function object
static _Functor*
_M_get_pointer(const _Any_data& __source)
{
 const _Functor* __ptr =
   __stored_locally? std::__addressof(__source._M_access<_Functor>())
   /* have stored a pointer */ : __source._M_access<_Functor*>();
 return const_cast<_Functor*>(__ptr);
}

// Clone a location-invariant function object that fits within
// an _Any_data structure.
static void
_M_clone(_Any_data& __dest, const _Any_data& __source, true_type)
{
 ::new (__dest._M_access()) _Functor(__source._M_access<_Functor>());
}

// Clone a function object that is not location-invariant or
// that cannot fit into an _Any_data structure.
static void
_M_clone(_Any_data& __dest, const _Any_data& __source, false_type)
{
 __dest._M_access<_Functor*>() =
   new _Functor(*__source._M_access<_Functor*>());
}

// Destroying a location-invariant object may still require
// destruction.
static void
_M_destroy(_Any_data& __victim, true_type)
{
 __victim._M_access<_Functor>().~_Functor();
}

// Destroying an object located on the heap.
static void
_M_destroy(_Any_data& __victim, false_type)
{
 delete __victim._M_access<_Functor*>();
}

    public:
static bool
_M_manager(_Any_data& __dest, const _Any_data& __source,
   _Manager_operation __op)
{
 switch (__op)
   {
217#if __cpp_rtti199711
   case __get_type_info:
     __dest._M_access<const type_info*>() = &typeid(_Functor);
     break;
221#endif
   case __get_functor_ptr:
     __dest._M_access<_Functor*>() = _M_get_pointer(__source);
     break;

   case __clone_functor:
     _M_clone(__dest, __source, _Local_storage());
     break;

   case __destroy_functor:
     _M_destroy(__dest, _Local_storage());
     break;
   }
 return false;
}

static void
_M_init_functor(_Any_data& __functor, _Functor&& __f)
{ _M_init_functor(__functor, std::move(__f), _Local_storage()); }
8
←
Calling '_Base_manager::_M_init_functor'→
10
←
Returned allocated memory→

template<typename _Signature>
 static bool
 _M_not_empty_function(const function<_Signature>& __f)
 { return static_cast<bool>(__f); }

template<typename _Tp>
 static bool
 _M_not_empty_function(_Tp* __fp)
 { return __fp != nullptr; }

template<typename _Class, typename _Tp>
 static bool
 _M_not_empty_function(_Tp _Class::* __mp)
 { return __mp != nullptr; }

template<typename _Tp>
 static bool
 _M_not_empty_function(const _Tp&)
 { return true; }

    private:
static void
_M_init_functor(_Any_data& __functor, _Functor&& __f, true_type)
{ ::new (__functor._M_access()) _Functor(std::move(__f)); }

static void
_M_init_functor(_Any_data& __functor, _Functor&& __f, false_type)
{ __functor._M_access<_Functor*>() = new _Functor(std::move(__f)); }
9
←
Memory is allocated→
    };

  _Function_base() : _M_manager(nullptr) { }

  ~_Function_base()
  {
    if (_M_manager)
_M_manager(_M_functor, _M_functor, __destroy_functor);
  }

  bool _M_empty() const { return !_M_manager; }

  typedef bool (*_Manager_type)(_Any_data&, const _Any_data&,
		  _Manager_operation);

  _Any_data     _M_functor;
  _Manager_type _M_manager;
};

template<typename _Signature, typename _Functor>
  class _Function_handler;

template<typename _Res, typename _Functor, typename... _ArgTypes>
  class _Function_handler<_Res(_ArgTypes...), _Functor>
  : public _Function_base::_Base_manager<_Functor>
  {
    typedef _Function_base::_Base_manager<_Functor> _Base;

  public:
    static _Res
    _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
    {
return (*_Base::_M_get_pointer(__functor))(
   std::forward<_ArgTypes>(__args)...);
    }
  };

template<typename _Functor, typename... _ArgTypes>
  class _Function_handler<void(_ArgTypes...), _Functor>
  : public _Function_base::_Base_manager<_Functor>
  {
    typedef _Function_base::_Base_manager<_Functor> _Base;

   public:
    static void
    _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
    {
(*_Base::_M_get_pointer(__functor))(
   std::forward<_ArgTypes>(__args)...);
    }
  };

template<typename _Class, typename _Member, typename _Res,
  typename... _ArgTypes>
  class _Function_handler<_Res(_ArgTypes...), _Member _Class::*>
  : public _Function_handler<void(_ArgTypes...), _Member _Class::*>
  {
    typedef _Function_handler<void(_ArgTypes...), _Member _Class::*>
_Base;

   public:
    static _Res
    _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
    {
return std::__invoke(_Base::_M_get_pointer(__functor)->__value,
	     std::forward<_ArgTypes>(__args)...);
    }
  };

template<typename _Class, typename _Member, typename... _ArgTypes>
  class _Function_handler<void(_ArgTypes...), _Member _Class::*>
  : public _Function_base::_Base_manager<
 _Simple_type_wrapper< _Member _Class::* > >
  {
    typedef _Member _Class::* _Functor;
    typedef _Simple_type_wrapper<_Functor> _Wrapper;
    typedef _Function_base::_Base_manager<_Wrapper> _Base;

  public:
    static bool
    _M_manager(_Any_data& __dest, const _Any_data& __source,
 _Manager_operation __op)
    {
switch (__op)
 {
354#if __cpp_rtti199711
 case __get_type_info:
   __dest._M_access<const type_info*>() = &typeid(_Functor);
   break;
358#endif
 case __get_functor_ptr:
   __dest._M_access<_Functor*>() =
     &_Base::_M_get_pointer(__source)->__value;
   break;

 default:
   _Base::_M_manager(__dest, __source, __op);
 }
return false;
    }

    static void
    _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
    {
std::__invoke(_Base::_M_get_pointer(__functor)->__value,
      std::forward<_ArgTypes>(__args)...);
    }
  };

template<typename _From, typename _To>
  using __check_func_return_type
    = __or_<is_void<_To>, is_same<_From, _To>, is_convertible<_From, _To>>;

/**
 *  @brief Primary class template for std::function.
 *  @ingroup functors
 *
 *  Polymorphic function wrapper.
 */
template<typename _Res, typename... _ArgTypes>
  class function<_Res(_ArgTypes...)>
  : public _Maybe_unary_or_binary_function<_Res, _ArgTypes...>,
    private _Function_base
  {
    template<typename _Func,
      typename _Res2 = typename result_of<_Func&(_ArgTypes...)>::type>
struct _Callable : __check_func_return_type<_Res2, _Res> { };

    // Used so the return type convertibility checks aren't done when
    // performing overload resolution for copy construction/assignment.
    template<typename _Tp>
struct _Callable<function, _Tp> : false_type { };

    template<typename _Cond, typename _Tp>
using _Requires = typename enable_if<_Cond::value, _Tp>::type;

  public:
    typedef _Res result_type;

    // [3.7.2.1] construct/copy/destroy

    /**
     *  @brief Default construct creates an empty function call wrapper.
     *  @post @c !(bool)*this
     */
    function() noexcept
    : _Function_base() { }

    /**
     *  @brief Creates an empty function call wrapper.
     *  @post @c !(bool)*this
     */
    function(nullptr_t) noexcept
    : _Function_base() { }

    /**
     *  @brief %Function copy constructor.
     *  @param __x A %function object with identical call signature.
     *  @post @c bool(*this) == bool(__x)
     *
     *  The newly-created %function contains a copy of the target of @a
     *  __x (if it has one).
     */
    function(const function& __x);

    /**
     *  @brief %Function move constructor.
     *  @param __x A %function object rvalue with identical call signature.
     *
     *  The newly-created %function contains the target of @a __x
     *  (if it has one).
     */
    function(function&& __x) noexcept : _Function_base()
    {
__x.swap(*this);
    }

    /**
     *  @brief Builds a %function that targets a copy of the incoming
     *  function object.
     *  @param __f A %function object that is callable with parameters of
     *  type @c T1, @c T2, ..., @c TN and returns a value convertible
     *  to @c Res.
     *
     *  The newly-created %function object will target a copy of
     *  @a __f. If @a __f is @c reference_wrapper<F>, then this function
     *  object will contain a reference to the function object @c
     *  __f.get(). If @a __f is a NULL function pointer or NULL
     *  pointer-to-member, the newly-created object will be empty.
     *
     *  If @a __f is a non-NULL function pointer or an object of type @c
     *  reference_wrapper<F>, this function will not throw.
     */
    template<typename _Functor,
      typename = _Requires<__not_<is_same<_Functor, function>>, void>,
      typename = _Requires<_Callable<_Functor>, void>>
function(_Functor);

    /**
     *  @brief %Function assignment operator.
     *  @param __x A %function with identical call signature.
     *  @post @c (bool)*this == (bool)x
     *  @returns @c *this
     *
     *  The target of @a __x is copied to @c *this. If @a __x has no
     *  target, then @c *this will be empty.
     *
     *  If @a __x targets a function pointer or a reference to a function
     *  object, then this operation will not throw an %exception.
     */
    function&
    operator=(const function& __x)
    {
function(__x).swap(*this);
return *this;
    }

    /**
     *  @brief %Function move-assignment operator.
     *  @param __x A %function rvalue with identical call signature.
     *  @returns @c *this
     *
     *  The target of @a __x is moved to @c *this. If @a __x has no
     *  target, then @c *this will be empty.
     *
     *  If @a __x targets a function pointer or a reference to a function
     *  object, then this operation will not throw an %exception.
     */
    function&
    operator=(function&& __x) noexcept
    {
function(std::move(__x)).swap(*this);
return *this;
    }

    /**
     *  @brief %Function assignment to zero.
     *  @post @c !(bool)*this
     *  @returns @c *this
     *
     *  The target of @c *this is deallocated, leaving it empty.
     */
    function&
    operator=(nullptr_t) noexcept
    {
if (_M_manager)
 {
   _M_manager(_M_functor, _M_functor, __destroy_functor);
   _M_manager = nullptr;
   _M_invoker = nullptr;
 }
return *this;
    }

    /**
     *  @brief %Function assignment to a new target.
     *  @param __f A %function object that is callable with parameters of
     *  type @c T1, @c T2, ..., @c TN and returns a value convertible
     *  to @c Res.
     *  @return @c *this
     *
     *  This  %function object wrapper will target a copy of @a
     *  __f. If @a __f is @c reference_wrapper<F>, then this function
     *  object will contain a reference to the function object @c
     *  __f.get(). If @a __f is a NULL function pointer or NULL
     *  pointer-to-member, @c this object will be empty.
     *
     *  If @a __f is a non-NULL function pointer or an object of type @c
     *  reference_wrapper<F>, this function will not throw.
     */
    template<typename _Functor>
_Requires<_Callable<typename decay<_Functor>::type>, function&>
operator=(_Functor&& __f)
{
 function(std::forward<_Functor>(__f)).swap(*this);
5
←
Calling constructor for 'function'→
12
←
Returning from constructor for 'function'→
 return *this;
}

    /// @overload
    template<typename _Functor>
function&
operator=(reference_wrapper<_Functor> __f) noexcept
{
 function(__f).swap(*this);
 return *this;
}

    // [3.7.2.2] function modifiers

    /**
     *  @brief Swap the targets of two %function objects.
     *  @param __x A %function with identical call signature.
     *
     *  Swap the targets of @c this function object and @a __f. This
     *  function will not throw an %exception.
     */
    void swap(function& __x) noexcept
    {
std::swap(_M_functor, __x._M_functor);
std::swap(_M_manager, __x._M_manager);
std::swap(_M_invoker, __x._M_invoker);
    }

    // [3.7.2.3] function capacity

    /**
     *  @brief Determine if the %function wrapper has a target.
     *
     *  @return @c true when this %function object contains a target,
     *  or @c false when it is empty.
     *
     *  This function will not throw an %exception.
     */
    explicit operator bool() const noexcept
    { return !_M_empty(); }

    // [3.7.2.4] function invocation

    /**
     *  @brief Invokes the function targeted by @c *this.
     *  @returns the result of the target.
     *  @throws bad_function_call when @c !(bool)*this
     *
     *  The function call operator invokes the target function object
     *  stored by @c this.
     */
    _Res operator()(_ArgTypes... __args) const;

597#if __cpp_rtti199711
    // [3.7.2.5] function target access
    /**
     *  @brief Determine the type of the target of this function object
     *  wrapper.
     *
     *  @returns the type identifier of the target function object, or
     *  @c typeid(void) if @c !(bool)*this.
     *
     *  This function will not throw an %exception.
     */
    const type_info& target_type() const noexcept;

    /**
     *  @brief Access the stored target function object.
     *
     *  @return Returns a pointer to the stored target function object,
     *  if @c typeid(_Functor).equals(target_type()); otherwise, a NULL
     *  pointer.
     *
     * This function does not throw exceptions.
     *
     * @{
     */
    template<typename _Functor>       _Functor* target() noexcept;

    template<typename _Functor> const _Functor* target() const noexcept;
    // @}
625#endif

  private:
    using _Invoker_type = _Res (*)(const _Any_data&, _ArgTypes&&...);
    _Invoker_type _M_invoker;
};

632#if __cpp_deduction_guides >= 201606
template<typename>
  struct __function_guide_helper
  { };

template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
  struct __function_guide_helper<
    _Res (_Tp::*) (_Args...) noexcept(_Nx)
  >
  { using type = _Res(_Args...); };

template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
  struct __function_guide_helper<
    _Res (_Tp::*) (_Args...) & noexcept(_Nx)
  >
  { using type = _Res(_Args...); };

template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
  struct __function_guide_helper<
    _Res (_Tp::*) (_Args...) const noexcept(_Nx)
  >
  { using type = _Res(_Args...); };

template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
  struct __function_guide_helper<
    _Res (_Tp::*) (_Args...) const & noexcept(_Nx)
  >
  { using type = _Res(_Args...); };

template<typename _Res, typename... _ArgTypes>
  function(_Res(*)(_ArgTypes...)) -> function<_Res(_ArgTypes...)>;

template<typename _Functor, typename _Signature = typename
  __function_guide_helper<decltype(&_Functor::operator())>::type>
  function(_Functor) -> function<_Signature>;
667#endif

// Out-of-line member definitions.
template<typename _Res, typename... _ArgTypes>
  function<_Res(_ArgTypes...)>::
  function(const function& __x)
  : _Function_base()
  {
    if (static_cast<bool>(__x))
{
 __x._M_manager(_M_functor, __x._M_functor, __clone_functor);
 _M_invoker = __x._M_invoker;
 _M_manager = __x._M_manager;
}
  }

template<typename _Res, typename... _ArgTypes>
  template<typename _Functor, typename, typename>
    function<_Res(_ArgTypes...)>::
    function(_Functor __f)
    : _Function_base()
    {
typedef _Function_handler<_Res(_ArgTypes...), _Functor> _My_handler;

if (_My_handler::_M_not_empty_function(__f))
6
←
Taking true branch→
 {
   _My_handler::_M_init_functor(_M_functor, std::move(__f));
7
←
Calling '_Base_manager::_M_init_functor'→
11
←
Returned allocated memory→
   _M_invoker = &_My_handler::_M_invoke;
   _M_manager = &_My_handler::_M_manager;
 }
    }

template<typename _Res, typename... _ArgTypes>
  _Res
  function<_Res(_ArgTypes...)>::
  operator()(_ArgTypes... __args) const
  {
    if (_M_empty())
__throw_bad_function_call();
    return _M_invoker(_M_functor, std::forward<_ArgTypes>(__args)...);
  }

709#if __cpp_rtti199711
template<typename _Res, typename... _ArgTypes>
  const type_info&
  function<_Res(_ArgTypes...)>::
  target_type() const noexcept
  {
    if (_M_manager)
{
 _Any_data __typeinfo_result;
 _M_manager(__typeinfo_result, _M_functor, __get_type_info);
 return *__typeinfo_result._M_access<const type_info*>();
}
    else
return typeid(void);
  }

template<typename _Res, typename... _ArgTypes>
  template<typename _Functor>
    _Functor*
    function<_Res(_ArgTypes...)>::
    target() noexcept
    {
const function* __const_this = this;
const _Functor* __func = __const_this->template target<_Functor>();
return const_cast<_Functor*>(__func);
    }

template<typename _Res, typename... _ArgTypes>
  template<typename _Functor>
    const _Functor*
    function<_Res(_ArgTypes...)>::
    target() const noexcept
    {
if (typeid(_Functor) == target_type() && _M_manager)
 {
   _Any_data __ptr;
   _M_manager(__ptr, _M_functor, __get_functor_ptr);
   return __ptr._M_access<const _Functor*>();
 }
else
 return nullptr;
    }
751#endif

// [20.7.15.2.6] null pointer comparisons

/**
 *  @brief Compares a polymorphic function object wrapper against 0
 *  (the NULL pointer).
 *  @returns @c true if the wrapper has no target, @c false otherwise
 *
 *  This function will not throw an %exception.
 */
template<typename _Res, typename... _Args>
  inline bool
  operator==(const function<_Res(_Args...)>& __f, nullptr_t) noexcept
  { return !static_cast<bool>(__f); }

/// @overload
template<typename _Res, typename... _Args>
  inline bool
  operator==(nullptr_t, const function<_Res(_Args...)>& __f) noexcept
  { return !static_cast<bool>(__f); }

/**
 *  @brief Compares a polymorphic function object wrapper against 0
 *  (the NULL pointer).
 *  @returns @c false if the wrapper has no target, @c true otherwise
 *
 *  This function will not throw an %exception.
 */
template<typename _Res, typename... _Args>
  inline bool
  operator!=(const function<_Res(_Args...)>& __f, nullptr_t) noexcept
  { return static_cast<bool>(__f); }

/// @overload
template<typename _Res, typename... _Args>
  inline bool
  operator!=(nullptr_t, const function<_Res(_Args...)>& __f) noexcept
  { return static_cast<bool>(__f); }


// [20.7.15.2.7] specialized algorithms

/**
 *  @brief Swap the targets of two polymorphic function object wrappers.
 *
 *  This function will not throw an %exception.
 */
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2062. Effect contradictions w/o no-throw guarantee of std::function swaps
template<typename _Res, typename... _Args>
  inline void
  swap(function<_Res(_Args...)>& __x, function<_Res(_Args...)>& __y) noexcept
  { __x.swap(__y); }

806_GLIBCXX_END_NAMESPACE_VERSION
807} // namespace std

809#endif // C++11

811#endif // _GLIBCXX_STD_FUNCTION_H