/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp

Bug Summary

File:	lib/Transforms/Scalar/IndVarSimplify.cpp
Warning:	line 2272, column 47 Called C++ object pointer is null

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 IndVarSimplify.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn374877/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.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++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn374877=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-10-15-233810-7101-1 -x c++ /build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp

/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp

→

1//===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This transformation analyzes and transforms the induction variables (and
10// computations derived from them) into simpler forms suitable for subsequent
11// analysis and transformation.
12//
13// If the trip count of a loop is computable, this pass also makes the following
14// changes:
15//   1. The exit condition for the loop is canonicalized to compare the
16//      induction value against the exit value.  This turns loops like:
17//        'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'
18//   2. Any use outside of the loop of an expression derived from the indvar
19//      is changed to compute the derived value outside of the loop, eliminating
20//      the dependence on the exit value of the induction variable.  If the only
21//      purpose of the loop is to compute the exit value of some derived
22//      expression, this transformation will make the loop dead.
23//
24//===----------------------------------------------------------------------===//

26#include "llvm/Transforms/Scalar/IndVarSimplify.h"
27#include "llvm/ADT/APFloat.h"
28#include "llvm/ADT/APInt.h"
29#include "llvm/ADT/ArrayRef.h"
30#include "llvm/ADT/DenseMap.h"
31#include "llvm/ADT/None.h"
32#include "llvm/ADT/Optional.h"
33#include "llvm/ADT/STLExtras.h"
34#include "llvm/ADT/SmallSet.h"
35#include "llvm/ADT/SmallPtrSet.h"
36#include "llvm/ADT/SmallVector.h"
37#include "llvm/ADT/Statistic.h"
38#include "llvm/ADT/iterator_range.h"
39#include "llvm/Analysis/LoopInfo.h"
40#include "llvm/Analysis/LoopPass.h"
41#include "llvm/Analysis/ScalarEvolution.h"
42#include "llvm/Analysis/ScalarEvolutionExpander.h"
43#include "llvm/Analysis/ScalarEvolutionExpressions.h"
44#include "llvm/Analysis/TargetLibraryInfo.h"
45#include "llvm/Analysis/TargetTransformInfo.h"
46#include "llvm/Analysis/ValueTracking.h"
47#include "llvm/Transforms/Utils/Local.h"
48#include "llvm/IR/BasicBlock.h"
49#include "llvm/IR/Constant.h"
50#include "llvm/IR/ConstantRange.h"
51#include "llvm/IR/Constants.h"
52#include "llvm/IR/DataLayout.h"
53#include "llvm/IR/DerivedTypes.h"
54#include "llvm/IR/Dominators.h"
55#include "llvm/IR/Function.h"
56#include "llvm/IR/IRBuilder.h"
57#include "llvm/IR/InstrTypes.h"
58#include "llvm/IR/Instruction.h"
59#include "llvm/IR/Instructions.h"
60#include "llvm/IR/IntrinsicInst.h"
61#include "llvm/IR/Intrinsics.h"
62#include "llvm/IR/Module.h"
63#include "llvm/IR/Operator.h"
64#include "llvm/IR/PassManager.h"
65#include "llvm/IR/PatternMatch.h"
66#include "llvm/IR/Type.h"
67#include "llvm/IR/Use.h"
68#include "llvm/IR/User.h"
69#include "llvm/IR/Value.h"
70#include "llvm/IR/ValueHandle.h"
71#include "llvm/Pass.h"
72#include "llvm/Support/Casting.h"
73#include "llvm/Support/CommandLine.h"
74#include "llvm/Support/Compiler.h"
75#include "llvm/Support/Debug.h"
76#include "llvm/Support/ErrorHandling.h"
77#include "llvm/Support/MathExtras.h"
78#include "llvm/Support/raw_ostream.h"
79#include "llvm/Transforms/Scalar.h"
80#include "llvm/Transforms/Scalar/LoopPassManager.h"
81#include "llvm/Transforms/Utils/BasicBlockUtils.h"
82#include "llvm/Transforms/Utils/LoopUtils.h"
83#include "llvm/Transforms/Utils/SimplifyIndVar.h"
84#include <cassert>
85#include <cstdint>
86#include <utility>

88using namespace llvm;

90#define DEBUG_TYPE"indvars" "indvars"

92STATISTIC(NumWidened     , "Number of indvars widened")static llvm::Statistic NumWidened = {"indvars", "NumWidened",
 "Number of indvars widened"};
93STATISTIC(NumReplaced    , "Number of exit values replaced")static llvm::Statistic NumReplaced = {"indvars", "NumReplaced"
, "Number of exit values replaced"};
94STATISTIC(NumLFTR        , "Number of loop exit tests replaced")static llvm::Statistic NumLFTR = {"indvars", "NumLFTR", "Number of loop exit tests replaced"
};
95STATISTIC(NumElimExt     , "Number of IV sign/zero extends eliminated")static llvm::Statistic NumElimExt = {"indvars", "NumElimExt",
 "Number of IV sign/zero extends eliminated"};
96STATISTIC(NumElimIV      , "Number of congruent IVs eliminated")static llvm::Statistic NumElimIV = {"indvars", "NumElimIV", "Number of congruent IVs eliminated"
};

98// Trip count verification can be enabled by default under NDEBUG if we
99// implement a strong expression equivalence checker in SCEV. Until then, we
100// use the verify-indvars flag, which may assert in some cases.
101static cl::opt<bool> VerifyIndvars(
"verify-indvars", cl::Hidden,
cl::desc("Verify the ScalarEvolution result after running indvars"));

105enum ReplaceExitVal { NeverRepl, OnlyCheapRepl, NoHardUse, AlwaysRepl };

107static cl::opt<ReplaceExitVal> ReplaceExitValue(
  "replexitval", cl::Hidden, cl::init(OnlyCheapRepl),
  cl::desc("Choose the strategy to replace exit value in IndVarSimplify"),
  cl::values(clEnumValN(NeverRepl, "never", "never replace exit value")llvm::cl::OptionEnumValue { "never", int(NeverRepl), "never replace exit value"
 },
             clEnumValN(OnlyCheapRepl, "cheap",llvm::cl::OptionEnumValue { "cheap", int(OnlyCheapRepl), "only replace exit value when the cost is cheap"
 }
                        "only replace exit value when the cost is cheap")llvm::cl::OptionEnumValue { "cheap", int(OnlyCheapRepl), "only replace exit value when the cost is cheap"
 },
             clEnumValN(NoHardUse, "noharduse",llvm::cl::OptionEnumValue { "noharduse", int(NoHardUse), "only replace exit values when loop def likely dead"
 }
                        "only replace exit values when loop def likely dead")llvm::cl::OptionEnumValue { "noharduse", int(NoHardUse), "only replace exit values when loop def likely dead"
 },
             clEnumValN(AlwaysRepl, "always",llvm::cl::OptionEnumValue { "always", int(AlwaysRepl), "always replace exit value whenever possible"
 }
                        "always replace exit value whenever possible")llvm::cl::OptionEnumValue { "always", int(AlwaysRepl), "always replace exit value whenever possible"
 }));

118static cl::opt<bool> UsePostIncrementRanges(
"indvars-post-increment-ranges", cl::Hidden,
cl::desc("Use post increment control-dependent ranges in IndVarSimplify"),
cl::init(true));

123static cl::opt<bool>
124DisableLFTR("disable-lftr", cl::Hidden, cl::init(false),
          cl::desc("Disable Linear Function Test Replace optimization"));

127static cl::opt<bool>
128LoopPredication("indvars-predicate-loops", cl::Hidden, cl::init(false),
              cl::desc("Predicate conditions in read only loops"));


132namespace {

134struct RewritePhi;

136class IndVarSimplify {
LoopInfo *LI;
ScalarEvolution *SE;
DominatorTree *DT;
const DataLayout &DL;
TargetLibraryInfo *TLI;
const TargetTransformInfo *TTI;

SmallVector<WeakTrackingVH, 16> DeadInsts;

bool isValidRewrite(Value *FromVal, Value *ToVal);

bool handleFloatingPointIV(Loop *L, PHINode *PH);
bool rewriteNonIntegerIVs(Loop *L);

bool simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
bool optimizeLoopExits(Loop *L, SCEVExpander &Rewriter);

bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
bool rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
bool rewriteFirstIterationLoopExitValues(Loop *L);
bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) const;

bool linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,
                               const SCEV *ExitCount,
                               PHINode *IndVar, SCEVExpander &Rewriter);

bool sinkUnusedInvariants(Loop *L);

165public:
IndVarSimplify(LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
               const DataLayout &DL, TargetLibraryInfo *TLI,
               TargetTransformInfo *TTI)
    : LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI) {}

bool run(Loop *L);
172};

174} // end anonymous namespace

176/// Return true if the SCEV expansion generated by the rewriter can replace the
177/// original value. SCEV guarantees that it produces the same value, but the way
178/// it is produced may be illegal IR.  Ideally, this function will only be
179/// called for verification.
180bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) {
// If an SCEV expression subsumed multiple pointers, its expansion could
// reassociate the GEP changing the base pointer. This is illegal because the
// final address produced by a GEP chain must be inbounds relative to its
// underlying object. Otherwise basic alias analysis, among other things,
// could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
// producing an expression involving multiple pointers. Until then, we must
// bail out here.
//
// Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject
// because it understands lcssa phis while SCEV does not.
Value *FromPtr = FromVal;
Value *ToPtr = ToVal;
if (auto *GEP = dyn_cast<GEPOperator>(FromVal)) {
  FromPtr = GEP->getPointerOperand();
}
if (auto *GEP = dyn_cast<GEPOperator>(ToVal)) {
  ToPtr = GEP->getPointerOperand();
}
if (FromPtr != FromVal || ToPtr != ToVal) {
  // Quickly check the common case
  if (FromPtr == ToPtr)
    return true;

  // SCEV may have rewritten an expression that produces the GEP's pointer
  // operand. That's ok as long as the pointer operand has the same base
  // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the
  // base of a recurrence. This handles the case in which SCEV expansion
  // converts a pointer type recurrence into a nonrecurrent pointer base
  // indexed by an integer recurrence.

  // If the GEP base pointer is a vector of pointers, abort.
  if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy())
    return false;

  const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
  const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
  if (FromBase == ToBase)
    return true;

  LLVM_DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " << *FromBasedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: GEP rewrite bail out "
 << *FromBase << " != " << *ToBase <<
 "\n"; } } while (false)
                    << " != " << *ToBase << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: GEP rewrite bail out "
 << *FromBase << " != " << *ToBase <<
 "\n"; } } while (false);

  return false;
}
return true;
226}

228/// Determine the insertion point for this user. By default, insert immediately
229/// before the user. SCEVExpander or LICM will hoist loop invariants out of the
230/// loop. For PHI nodes, there may be multiple uses, so compute the nearest
231/// common dominator for the incoming blocks. A nullptr can be returned if no
232/// viable location is found: it may happen if User is a PHI and Def only comes
233/// to this PHI from unreachable blocks.
234static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
                                        DominatorTree *DT, LoopInfo *LI) {
PHINode *PHI = dyn_cast<PHINode>(User);
if (!PHI)
  return User;

Instruction *InsertPt = nullptr;
for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
  if (PHI->getIncomingValue(i) != Def)
    continue;

  BasicBlock *InsertBB = PHI->getIncomingBlock(i);

  if (!DT->isReachableFromEntry(InsertBB))
    continue;

  if (!InsertPt) {
    InsertPt = InsertBB->getTerminator();
    continue;
  }
  InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
  InsertPt = InsertBB->getTerminator();
}

// If we have skipped all inputs, it means that Def only comes to Phi from
// unreachable blocks.
if (!InsertPt)
  return nullptr;

auto *DefI = dyn_cast<Instruction>(Def);
if (!DefI)
  return InsertPt;

assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses")((DT->dominates(DefI, InsertPt) && "def does not dominate all uses"
) ? static_cast<void> (0) : __assert_fail ("DT->dominates(DefI, InsertPt) && \"def does not dominate all uses\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 267, __PRETTY_FUNCTION__));

auto *L = LI->getLoopFor(DefI->getParent());
assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())))((!L || L->contains(LI->getLoopFor(InsertPt->getParent
()))) ? static_cast<void> (0) : __assert_fail ("!L || L->contains(LI->getLoopFor(InsertPt->getParent()))"
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 270, __PRETTY_FUNCTION__));

for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
  if (LI->getLoopFor(DTN->getBlock()) == L)
    return DTN->getBlock()->getTerminator();

llvm_unreachable("DefI dominates InsertPt!")::llvm::llvm_unreachable_internal("DefI dominates InsertPt!",
 "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 276);
277}

279//===----------------------------------------------------------------------===//
280// rewriteNonIntegerIVs and helpers. Prefer integer IVs.
281//===----------------------------------------------------------------------===//

283/// Convert APF to an integer, if possible.
284static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) {
bool isExact = false;
// See if we can convert this to an int64_t
uint64_t UIntVal;
if (APF.convertToInteger(makeMutableArrayRef(UIntVal), 64, true,
                         APFloat::rmTowardZero, &isExact) != APFloat::opOK ||
    !isExact)
  return false;
IntVal = UIntVal;
return true;
294}

296/// If the loop has floating induction variable then insert corresponding
297/// integer induction variable if possible.
298/// For example,
299/// for(double i = 0; i < 10000; ++i)
300///   bar(i)
301/// is converted into
302/// for(int i = 0; i < 10000; ++i)
303///   bar((double)i);
304bool IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {
unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
unsigned BackEdge     = IncomingEdge^1;

// Check incoming value.
auto *InitValueVal = dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge));

int64_t InitValue;
if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue))
  return false;

// Check IV increment. Reject this PN if increment operation is not
// an add or increment value can not be represented by an integer.
auto *Incr = dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge));
if (Incr == nullptr || Incr->getOpcode() != Instruction::FAdd) return false;

// If this is not an add of the PHI with a constantfp, or if the constant fp
// is not an integer, bail out.
ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1));
int64_t IncValue;
if (IncValueVal == nullptr || Incr->getOperand(0) != PN ||
    !ConvertToSInt(IncValueVal->getValueAPF(), IncValue))
  return false;

// Check Incr uses. One user is PN and the other user is an exit condition
// used by the conditional terminator.
Value::user_iterator IncrUse = Incr->user_begin();
Instruction *U1 = cast<Instruction>(*IncrUse++);
if (IncrUse == Incr->user_end()) return false;
Instruction *U2 = cast<Instruction>(*IncrUse++);
if (IncrUse != Incr->user_end()) return false;

// Find exit condition, which is an fcmp.  If it doesn't exist, or if it isn't
// only used by a branch, we can't transform it.
FCmpInst *Compare = dyn_cast<FCmpInst>(U1);
if (!Compare)
  Compare = dyn_cast<FCmpInst>(U2);
if (!Compare || !Compare->hasOneUse() ||
    !isa<BranchInst>(Compare->user_back()))
  return false;

BranchInst *TheBr = cast<BranchInst>(Compare->user_back());

// We need to verify that the branch actually controls the iteration count
// of the loop.  If not, the new IV can overflow and no one will notice.
// The branch block must be in the loop and one of the successors must be out
// of the loop.
assert(TheBr->isConditional() && "Can't use fcmp if not conditional")((TheBr->isConditional() && "Can't use fcmp if not conditional"
) ? static_cast<void> (0) : __assert_fail ("TheBr->isConditional() && \"Can't use fcmp if not conditional\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 351, __PRETTY_FUNCTION__));
if (!L->contains(TheBr->getParent()) ||
    (L->contains(TheBr->getSuccessor(0)) &&
     L->contains(TheBr->getSuccessor(1))))
  return false;

// If it isn't a comparison with an integer-as-fp (the exit value), we can't
// transform it.
ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1));
int64_t ExitValue;
if (ExitValueVal == nullptr ||
    !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue))
  return false;

// Find new predicate for integer comparison.
CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE;
switch (Compare->getPredicate()) {
default: return false;  // Unknown comparison.
case CmpInst::FCMP_OEQ:
case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break;
case CmpInst::FCMP_ONE:
case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break;
case CmpInst::FCMP_OGT:
case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break;
case CmpInst::FCMP_OGE:
case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break;
case CmpInst::FCMP_OLT:
case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break;
case CmpInst::FCMP_OLE:
case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break;
}

// We convert the floating point induction variable to a signed i32 value if
// we can.  This is only safe if the comparison will not overflow in a way
// that won't be trapped by the integer equivalent operations.  Check for this
// now.
// TODO: We could use i64 if it is native and the range requires it.

// The start/stride/exit values must all fit in signed i32.
if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue))
  return false;

// If not actually striding (add x, 0.0), avoid touching the code.
if (IncValue == 0)
  return false;

// Positive and negative strides have different safety conditions.
if (IncValue > 0) {
  // If we have a positive stride, we require the init to be less than the
  // exit value.
  if (InitValue >= ExitValue)
    return false;

  uint32_t Range = uint32_t(ExitValue-InitValue);
  // Check for infinite loop, either:
  // while (i <= Exit) or until (i > Exit)
  if (NewPred == CmpInst::ICMP_SLE || NewPred == CmpInst::ICMP_SGT) {
    if (++Range == 0) return false;  // Range overflows.
  }

  unsigned Leftover = Range % uint32_t(IncValue);

  // If this is an equality comparison, we require that the strided value
  // exactly land on the exit value, otherwise the IV condition will wrap
  // around and do things the fp IV wouldn't.
  if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
      Leftover != 0)
    return false;

  // If the stride would wrap around the i32 before exiting, we can't
  // transform the IV.
  if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue)
    return false;
} else {
  // If we have a negative stride, we require the init to be greater than the
  // exit value.
  if (InitValue <= ExitValue)
    return false;

  uint32_t Range = uint32_t(InitValue-ExitValue);
  // Check for infinite loop, either:
  // while (i >= Exit) or until (i < Exit)
  if (NewPred == CmpInst::ICMP_SGE || NewPred == CmpInst::ICMP_SLT) {
    if (++Range == 0) return false;  // Range overflows.
  }

  unsigned Leftover = Range % uint32_t(-IncValue);

  // If this is an equality comparison, we require that the strided value
  // exactly land on the exit value, otherwise the IV condition will wrap
  // around and do things the fp IV wouldn't.
  if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
      Leftover != 0)
    return false;

  // If the stride would wrap around the i32 before exiting, we can't
  // transform the IV.
  if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue)
    return false;
}

IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext());

// Insert new integer induction variable.
PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN);
NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue),
                    PN->getIncomingBlock(IncomingEdge));

Value *NewAdd =
  BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue),
                            Incr->getName()+".int", Incr);
NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge));

ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd,
                                    ConstantInt::get(Int32Ty, ExitValue),
                                    Compare->getName());

// In the following deletions, PN may become dead and may be deleted.
// Use a WeakTrackingVH to observe whether this happens.
WeakTrackingVH WeakPH = PN;

// Delete the old floating point exit comparison.  The branch starts using the
// new comparison.
NewCompare->takeName(Compare);
Compare->replaceAllUsesWith(NewCompare);
RecursivelyDeleteTriviallyDeadInstructions(Compare, TLI);

// Delete the old floating point increment.
Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
RecursivelyDeleteTriviallyDeadInstructions(Incr, TLI);

// If the FP induction variable still has uses, this is because something else
// in the loop uses its value.  In order to canonicalize the induction
// variable, we chose to eliminate the IV and rewrite it in terms of an
// int->fp cast.
//
// We give preference to sitofp over uitofp because it is faster on most
// platforms.
if (WeakPH) {
  Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv",
                               &*PN->getParent()->getFirstInsertionPt());
  PN->replaceAllUsesWith(Conv);
  RecursivelyDeleteTriviallyDeadInstructions(PN, TLI);
}
return true;
496}

498bool IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {
// First step.  Check to see if there are any floating-point recurrences.
// If there are, change them into integer recurrences, permitting analysis by
// the SCEV routines.
BasicBlock *Header = L->getHeader();

SmallVector<WeakTrackingVH, 8> PHIs;
for (PHINode &PN : Header->phis())
  PHIs.push_back(&PN);

bool Changed = false;
for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
  if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i]))
    Changed |= handleFloatingPointIV(L, PN);

// If the loop previously had floating-point IV, ScalarEvolution
// may not have been able to compute a trip count. Now that we've done some
// re-writing, the trip count may be computable.
if (Changed)
  SE->forgetLoop(L);
return Changed;
519}

521namespace {

523// Collect information about PHI nodes which can be transformed in
524// rewriteLoopExitValues.
525struct RewritePhi {
PHINode *PN;

// Ith incoming value.
unsigned Ith;

// Exit value after expansion.
Value *Val;

// High Cost when expansion.
bool HighCost;

RewritePhi(PHINode *P, unsigned I, Value *V, bool H)
    : PN(P), Ith(I), Val(V), HighCost(H) {}
539};

541} // end anonymous namespace

543//===----------------------------------------------------------------------===//
544// rewriteLoopExitValues - Optimize IV users outside the loop.
545// As a side effect, reduces the amount of IV processing within the loop.
546//===----------------------------------------------------------------------===//

548bool IndVarSimplify::hasHardUserWithinLoop(const Loop *L, const Instruction *I) const {
SmallPtrSet<const Instruction *, 8> Visited;
SmallVector<const Instruction *, 8> WorkList;
Visited.insert(I);
WorkList.push_back(I);
while (!WorkList.empty()) {
  const Instruction *Curr = WorkList.pop_back_val();
  // This use is outside the loop, nothing to do.
  if (!L->contains(Curr))
    continue;
  // Do we assume it is a "hard" use which will not be eliminated easily?
  if (Curr->mayHaveSideEffects())
    return true;
  // Otherwise, add all its users to worklist.
  for (auto U : Curr->users()) {
    auto *UI = cast<Instruction>(U);
    if (Visited.insert(UI).second)
      WorkList.push_back(UI);
  }
}
return false;
569}

571/// Check to see if this loop has a computable loop-invariant execution count.
572/// If so, this means that we can compute the final value of any expressions
573/// that are recurrent in the loop, and substitute the exit values from the loop
574/// into any instructions outside of the loop that use the final values of the
575/// current expressions.
576///
577/// This is mostly redundant with the regular IndVarSimplify activities that
578/// happen later, except that it's more powerful in some cases, because it's
579/// able to brute-force evaluate arbitrary instructions as long as they have
580/// constant operands at the beginning of the loop.
581bool IndVarSimplify::rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
// Check a pre-condition.
assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&((L->isRecursivelyLCSSAForm(*DT, *LI) && "Indvars did not preserve LCSSA!"
) ? static_cast<void> (0) : __assert_fail ("L->isRecursivelyLCSSAForm(*DT, *LI) && \"Indvars did not preserve LCSSA!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 584, __PRETTY_FUNCTION__))
       "Indvars did not preserve LCSSA!")((L->isRecursivelyLCSSAForm(*DT, *LI) && "Indvars did not preserve LCSSA!"
) ? static_cast<void> (0) : __assert_fail ("L->isRecursivelyLCSSAForm(*DT, *LI) && \"Indvars did not preserve LCSSA!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 584, __PRETTY_FUNCTION__));

SmallVector<BasicBlock*, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);

SmallVector<RewritePhi, 8> RewritePhiSet;
// Find all values that are computed inside the loop, but used outside of it.
// Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
// the exit blocks of the loop to find them.
for (BasicBlock *ExitBB : ExitBlocks) {
  // If there are no PHI nodes in this exit block, then no values defined
  // inside the loop are used on this path, skip it.
  PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
  if (!PN) continue;

  unsigned NumPreds = PN->getNumIncomingValues();

  // Iterate over all of the PHI nodes.
  BasicBlock::iterator BBI = ExitBB->begin();
  while ((PN = dyn_cast<PHINode>(BBI++))) {
    if (PN->use_empty())
      continue; // dead use, don't replace it

    if (!SE->isSCEVable(PN->getType()))
      continue;

    // It's necessary to tell ScalarEvolution about this explicitly so that
    // it can walk the def-use list and forget all SCEVs, as it may not be
    // watching the PHI itself. Once the new exit value is in place, there
    // may not be a def-use connection between the loop and every instruction
    // which got a SCEVAddRecExpr for that loop.
    SE->forgetValue(PN);

    // Iterate over all of the values in all the PHI nodes.
    for (unsigned i = 0; i != NumPreds; ++i) {
      // If the value being merged in is not integer or is not defined
      // in the loop, skip it.
      Value *InVal = PN->getIncomingValue(i);
      if (!isa<Instruction>(InVal))
        continue;

      // If this pred is for a subloop, not L itself, skip it.
      if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
        continue; // The Block is in a subloop, skip it.

      // Check that InVal is defined in the loop.
      Instruction *Inst = cast<Instruction>(InVal);
      if (!L->contains(Inst))
        continue;

      // Okay, this instruction has a user outside of the current loop
      // and varies predictably *inside* the loop.  Evaluate the value it
      // contains when the loop exits, if possible.  We prefer to start with
      // expressions which are true for all exits (so as to maximize
      // expression reuse by the SCEVExpander), but resort to per-exit
      // evaluation if that fails.  
      const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
      if (isa<SCEVCouldNotCompute>(ExitValue) ||
          !SE->isLoopInvariant(ExitValue, L) ||
          !isSafeToExpand(ExitValue, *SE)) {
        // TODO: This should probably be sunk into SCEV in some way; maybe a
        // getSCEVForExit(SCEV*, L, ExitingBB)?  It can be generalized for
        // most SCEV expressions and other recurrence types (e.g. shift
        // recurrences).  Is there existing code we can reuse?
        const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i));
        if (isa<SCEVCouldNotCompute>(ExitCount))
          continue;
        if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Inst)))
          if (AddRec->getLoop() == L)
            ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
        if (isa<SCEVCouldNotCompute>(ExitValue) ||
            !SE->isLoopInvariant(ExitValue, L) ||
            !isSafeToExpand(ExitValue, *SE))
          continue;
      }
      
      // Computing the value outside of the loop brings no benefit if it is
      // definitely used inside the loop in a way which can not be optimized
      // away.  Avoid doing so unless we know we have a value which computes
      // the ExitValue already.  TODO: This should be merged into SCEV
      // expander to leverage its knowledge of existing expressions.
      if (ReplaceExitValue != AlwaysRepl &&
          !isa<SCEVConstant>(ExitValue) && !isa<SCEVUnknown>(ExitValue) &&
          hasHardUserWithinLoop(L, Inst))
        continue;

      bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, Inst);
      Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);

      LLVM_DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitValdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: RLEV: AfterLoopVal = "
 << *ExitVal << '\n' << "  LoopVal = " <<
 *Inst << "\n"; } } while (false)
                        << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: RLEV: AfterLoopVal = "
 << *ExitVal << '\n' << "  LoopVal = " <<
 *Inst << "\n"; } } while (false)
                        << "  LoopVal = " << *Inst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: RLEV: AfterLoopVal = "
 << *ExitVal << '\n' << "  LoopVal = " <<
 *Inst << "\n"; } } while (false);

      if (!isValidRewrite(Inst, ExitVal)) {
        DeadInsts.push_back(ExitVal);
        continue;
      }

682#ifndef NDEBUG
      // If we reuse an instruction from a loop which is neither L nor one of
      // its containing loops, we end up breaking LCSSA form for this loop by
      // creating a new use of its instruction.
      if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
        if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
          if (EVL != L)
            assert(EVL->contains(L) && "LCSSA breach detected!")((EVL->contains(L) && "LCSSA breach detected!") ? static_cast
<void> (0) : __assert_fail ("EVL->contains(L) && \"LCSSA breach detected!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 689, __PRETTY_FUNCTION__));
690#endif

      // Collect all the candidate PHINodes to be rewritten.
      RewritePhiSet.emplace_back(PN, i, ExitVal, HighCost);
    }
  }
}

bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);

bool Changed = false;
// Transformation.
for (const RewritePhi &Phi : RewritePhiSet) {
  PHINode *PN = Phi.PN;
  Value *ExitVal = Phi.Val;

  // Only do the rewrite when the ExitValue can be expanded cheaply.
  // If LoopCanBeDel is true, rewrite exit value aggressively.
  if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
    DeadInsts.push_back(ExitVal);
    continue;
  }

  Changed = true;
  ++NumReplaced;
  Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
  PN->setIncomingValue(Phi.Ith, ExitVal);

  // If this instruction is dead now, delete it. Don't do it now to avoid
  // invalidating iterators.
  if (isInstructionTriviallyDead(Inst, TLI))
    DeadInsts.push_back(Inst);

  // Replace PN with ExitVal if that is legal and does not break LCSSA.
  if (PN->getNumIncomingValues() == 1 &&
      LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
    PN->replaceAllUsesWith(ExitVal);
    PN->eraseFromParent();
  }
}

// The insertion point instruction may have been deleted; clear it out
// so that the rewriter doesn't trip over it later.
Rewriter.clearInsertPoint();
return Changed;
735}

737//===---------------------------------------------------------------------===//
738// rewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know
739// they will exit at the first iteration.
740//===---------------------------------------------------------------------===//

742/// Check to see if this loop has loop invariant conditions which lead to loop
743/// exits. If so, we know that if the exit path is taken, it is at the first
744/// loop iteration. This lets us predict exit values of PHI nodes that live in
745/// loop header.
746bool IndVarSimplify::rewriteFirstIterationLoopExitValues(Loop *L) {
// Verify the input to the pass is already in LCSSA form.
assert(L->isLCSSAForm(*DT))((L->isLCSSAForm(*DT)) ? static_cast<void> (0) : __assert_fail
 ("L->isLCSSAForm(*DT)", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 748, __PRETTY_FUNCTION__));

SmallVector<BasicBlock *, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);

bool MadeAnyChanges = false;
for (auto *ExitBB : ExitBlocks) {
  // If there are no more PHI nodes in this exit block, then no more
  // values defined inside the loop are used on this path.
  for (PHINode &PN : ExitBB->phis()) {
    for (unsigned IncomingValIdx = 0, E = PN.getNumIncomingValues();
         IncomingValIdx != E; ++IncomingValIdx) {
      auto *IncomingBB = PN.getIncomingBlock(IncomingValIdx);

      // Can we prove that the exit must run on the first iteration if it
      // runs at all?  (i.e. early exits are fine for our purposes, but
      // traces which lead to this exit being taken on the 2nd iteration
      // aren't.)  Note that this is about whether the exit branch is
      // executed, not about whether it is taken.
      if (!L->getLoopLatch() ||
          !DT->dominates(IncomingBB, L->getLoopLatch()))
        continue;

      // Get condition that leads to the exit path.
      auto *TermInst = IncomingBB->getTerminator();

      Value *Cond = nullptr;
      if (auto *BI = dyn_cast<BranchInst>(TermInst)) {
        // Must be a conditional branch, otherwise the block
        // should not be in the loop.
        Cond = BI->getCondition();
      } else if (auto *SI = dyn_cast<SwitchInst>(TermInst))
        Cond = SI->getCondition();
      else
        continue;

      if (!L->isLoopInvariant(Cond))
        continue;

      auto *ExitVal = dyn_cast<PHINode>(PN.getIncomingValue(IncomingValIdx));

      // Only deal with PHIs in the loop header.
      if (!ExitVal || ExitVal->getParent() != L->getHeader())
        continue;

      // If ExitVal is a PHI on the loop header, then we know its
      // value along this exit because the exit can only be taken
      // on the first iteration.
      auto *LoopPreheader = L->getLoopPreheader();
      assert(LoopPreheader && "Invalid loop")((LoopPreheader && "Invalid loop") ? static_cast<void
> (0) : __assert_fail ("LoopPreheader && \"Invalid loop\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 797, __PRETTY_FUNCTION__));
      int PreheaderIdx = ExitVal->getBasicBlockIndex(LoopPreheader);
      if (PreheaderIdx != -1) {
        assert(ExitVal->getParent() == L->getHeader() &&((ExitVal->getParent() == L->getHeader() && "ExitVal must be in loop header"
) ? static_cast<void> (0) : __assert_fail ("ExitVal->getParent() == L->getHeader() && \"ExitVal must be in loop header\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 801, __PRETTY_FUNCTION__))
               "ExitVal must be in loop header")((ExitVal->getParent() == L->getHeader() && "ExitVal must be in loop header"
) ? static_cast<void> (0) : __assert_fail ("ExitVal->getParent() == L->getHeader() && \"ExitVal must be in loop header\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 801, __PRETTY_FUNCTION__));
        MadeAnyChanges = true;
        PN.setIncomingValue(IncomingValIdx,
                            ExitVal->getIncomingValue(PreheaderIdx));
      }
    }
  }
}
return MadeAnyChanges;
810}

812/// Check whether it is possible to delete the loop after rewriting exit
813/// value. If it is possible, ignore ReplaceExitValue and do rewriting
814/// aggressively.
815bool IndVarSimplify::canLoopBeDeleted(
  Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
BasicBlock *Preheader = L->getLoopPreheader();
// If there is no preheader, the loop will not be deleted.
if (!Preheader)
  return false;

// In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
// We obviate multiple ExitingBlocks case for simplicity.
// TODO: If we see testcase with multiple ExitingBlocks can be deleted
// after exit value rewriting, we can enhance the logic here.
SmallVector<BasicBlock *, 4> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks);
SmallVector<BasicBlock *, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);
if (ExitBlocks.size() != 1 || ExitingBlocks.size() != 1)
  return false;

BasicBlock *ExitBlock = ExitBlocks[0];
BasicBlock::iterator BI = ExitBlock->begin();
while (PHINode *P = dyn_cast<PHINode>(BI)) {
  Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);

  // If the Incoming value of P is found in RewritePhiSet, we know it
  // could be rewritten to use a loop invariant value in transformation
  // phase later. Skip it in the loop invariant check below.
  bool found = false;
  for (const RewritePhi &Phi : RewritePhiSet) {
    unsigned i = Phi.Ith;
    if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
      found = true;
      break;
    }
  }

  Instruction *I;
  if (!found && (I = dyn_cast<Instruction>(Incoming)))
    if (!L->hasLoopInvariantOperands(I))
      return false;

  ++BI;
}

for (auto *BB : L->blocks())
  if (llvm::any_of(*BB, [](Instruction &I) {
        return I.mayHaveSideEffects();
      }))
    return false;

return true;
865}

867//===----------------------------------------------------------------------===//
868//  IV Widening - Extend the width of an IV to cover its widest uses.
869//===----------------------------------------------------------------------===//

871namespace {

873// Collect information about induction variables that are used by sign/zero
874// extend operations. This information is recorded by CollectExtend and provides
875// the input to WidenIV.
876struct WideIVInfo {
PHINode *NarrowIV = nullptr;

// Widest integer type created [sz]ext
Type *WidestNativeType = nullptr;

// Was a sext user seen before a zext?
bool IsSigned = false;
884};

886} // end anonymous namespace

888/// Update information about the induction variable that is extended by this
889/// sign or zero extend operation. This is used to determine the final width of
890/// the IV before actually widening it.
891static void visitIVCast(CastInst *Cast, WideIVInfo &WI, ScalarEvolution *SE,
                      const TargetTransformInfo *TTI) {
bool IsSigned = Cast->getOpcode() == Instruction::SExt;
if (!IsSigned && Cast->getOpcode() != Instruction::ZExt)
  return;

Type *Ty = Cast->getType();
uint64_t Width = SE->getTypeSizeInBits(Ty);
if (!Cast->getModule()->getDataLayout().isLegalInteger(Width))
  return;

// Check that `Cast` actually extends the induction variable (we rely on this
// later).  This takes care of cases where `Cast` is extending a truncation of
// the narrow induction variable, and thus can end up being narrower than the
// "narrow" induction variable.
uint64_t NarrowIVWidth = SE->getTypeSizeInBits(WI.NarrowIV->getType());
if (NarrowIVWidth >= Width)
  return;

// Cast is either an sext or zext up to this point.
// We should not widen an indvar if arithmetics on the wider indvar are more
// expensive than those on the narrower indvar. We check only the cost of ADD
// because at least an ADD is required to increment the induction variable. We
// could compute more comprehensively the cost of all instructions on the
// induction variable when necessary.
if (TTI &&
    TTI->getArithmeticInstrCost(Instruction::Add, Ty) >
        TTI->getArithmeticInstrCost(Instruction::Add,
                                    Cast->getOperand(0)->getType())) {
  return;
}

if (!WI.WidestNativeType) {
  WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
  WI.IsSigned = IsSigned;
  return;
}

// We extend the IV to satisfy the sign of its first user, arbitrarily.
if (WI.IsSigned != IsSigned)
  return;

if (Width > SE->getTypeSizeInBits(WI.WidestNativeType))
  WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
935}

937namespace {

939/// Record a link in the Narrow IV def-use chain along with the WideIV that
940/// computes the same value as the Narrow IV def.  This avoids caching Use*
941/// pointers.
942struct NarrowIVDefUse {
Instruction *NarrowDef = nullptr;
Instruction *NarrowUse = nullptr;
Instruction *WideDef = nullptr;

// True if the narrow def is never negative.  Tracking this information lets
// us use a sign extension instead of a zero extension or vice versa, when
// profitable and legal.
bool NeverNegative = false;

NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,
               bool NeverNegative)
    : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
      NeverNegative(NeverNegative) {}
956};

958/// The goal of this transform is to remove sign and zero extends without
959/// creating any new induction variables. To do this, it creates a new phi of
960/// the wider type and redirects all users, either removing extends or inserting
961/// truncs whenever we stop propagating the type.
962class WidenIV {
// Parameters
PHINode *OrigPhi;
Type *WideType;

// Context
LoopInfo        *LI;
Loop            *L;
ScalarEvolution *SE;
DominatorTree   *DT;

// Does the module have any calls to the llvm.experimental.guard intrinsic
// at all? If not we can avoid scanning instructions looking for guards.
bool HasGuards;

// Result
PHINode *WidePhi = nullptr;
Instruction *WideInc = nullptr;
const SCEV *WideIncExpr = nullptr;
SmallVectorImpl<WeakTrackingVH> &DeadInsts;

SmallPtrSet<Instruction *,16> Widened;
SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;

enum ExtendKind { ZeroExtended, SignExtended, Unknown };

// A map tracking the kind of extension used to widen each narrow IV
// and narrow IV user.
// Key: pointer to a narrow IV or IV user.
// Value: the kind of extension used to widen this Instruction.
DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;

using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;

// A map with control-dependent ranges for post increment IV uses. The key is
// a pair of IV def and a use of this def denoting the context. The value is
// a ConstantRange representing possible values of the def at the given
// context.
DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;

Optional<ConstantRange> getPostIncRangeInfo(Value *Def,
                                            Instruction *UseI) {
  DefUserPair Key(Def, UseI);
  auto It = PostIncRangeInfos.find(Key);
  return It == PostIncRangeInfos.end()
             ? Optional<ConstantRange>(None)
             : Optional<ConstantRange>(It->second);
}

void calculatePostIncRanges(PHINode *OrigPhi);
void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);

void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
  DefUserPair Key(Def, UseI);
  auto It = PostIncRangeInfos.find(Key);
  if (It == PostIncRangeInfos.end())
    PostIncRangeInfos.insert({Key, R});
  else
    It->second = R.intersectWith(It->second);
}

1023public:
WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
        DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
        bool HasGuards)
    : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
      L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),
      HasGuards(HasGuards), DeadInsts(DI) {
  assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV")((L->getHeader() == OrigPhi->getParent() && "Phi must be an IV"
) ? static_cast<void> (0) : __assert_fail ("L->getHeader() == OrigPhi->getParent() && \"Phi must be an IV\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1030, __PRETTY_FUNCTION__));
  ExtendKindMap[OrigPhi] = WI.IsSigned ? SignExtended : ZeroExtended;
}

PHINode *createWideIV(SCEVExpander &Rewriter);

1036protected:
Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,
                        Instruction *Use);

Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);
Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
                                   const SCEVAddRecExpr *WideAR);
Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);

ExtendKind getExtendKind(Instruction *I);

using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;

WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);

WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);

const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
                            unsigned OpCode) const;

Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter);

bool widenLoopCompare(NarrowIVDefUse DU);
bool widenWithVariantLoadUse(NarrowIVDefUse DU);
void widenWithVariantLoadUseCodegen(NarrowIVDefUse DU);

void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
1063};

1065} // end anonymous namespace

1067Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,
                               bool IsSigned, Instruction *Use) {
// Set the debug location and conservative insertion point.
IRBuilder<> Builder(Use);
// Hoist the insertion point into loop preheaders as far as possible.
for (const Loop *L = LI->getLoopFor(Use->getParent());
     L && L->getLoopPreheader() && L->isLoopInvariant(NarrowOper);
     L = L->getParentLoop())
  Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());

return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
                  Builder.CreateZExt(NarrowOper, WideType);
1079}

1081/// Instantiate a wide operation to replace a narrow operation. This only needs
1082/// to handle operations that can evaluation to SCEVAddRec. It can safely return
1083/// 0 for any operation we decide not to clone.
1084Instruction *WidenIV::cloneIVUser(NarrowIVDefUse DU,
                                const SCEVAddRecExpr *WideAR) {
unsigned Opcode = DU.NarrowUse->getOpcode();
switch (Opcode) {
default:
  return nullptr;
case Instruction::Add:
case Instruction::Mul:
case Instruction::UDiv:
case Instruction::Sub:
  return cloneArithmeticIVUser(DU, WideAR);

case Instruction::And:
case Instruction::Or:
case Instruction::Xor:
case Instruction::Shl:
case Instruction::LShr:
case Instruction::AShr:
  return cloneBitwiseIVUser(DU);
}
1104}

1106Instruction *WidenIV::cloneBitwiseIVUser(NarrowIVDefUse DU) {
Instruction *NarrowUse = DU.NarrowUse;
Instruction *NarrowDef = DU.NarrowDef;
Instruction *WideDef = DU.WideDef;

LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "Cloning bitwise IVUser: " <<
 *NarrowUse << "\n"; } } while (false);

// Replace NarrowDef operands with WideDef. Otherwise, we don't know anything
// about the narrow operand yet so must insert a [sz]ext. It is probably loop
// invariant and will be folded or hoisted. If it actually comes from a
// widened IV, it should be removed during a future call to widenIVUse.
bool IsSigned = getExtendKind(NarrowDef) == SignExtended;
Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
                 ? WideDef
                 : createExtendInst(NarrowUse->getOperand(0), WideType,
                                    IsSigned, NarrowUse);
Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
                 ? WideDef
                 : createExtendInst(NarrowUse->getOperand(1), WideType,
                                    IsSigned, NarrowUse);

auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
                                      NarrowBO->getName());
IRBuilder<> Builder(NarrowUse);
Builder.Insert(WideBO);
WideBO->copyIRFlags(NarrowBO);
return WideBO;
1134}

1136Instruction *WidenIV::cloneArithmeticIVUser(NarrowIVDefUse DU,
                                          const SCEVAddRecExpr *WideAR) {
Instruction *NarrowUse = DU.NarrowUse;
Instruction *NarrowDef = DU.NarrowDef;
Instruction *WideDef = DU.WideDef;

LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "Cloning arithmetic IVUser: " <<
 *NarrowUse << "\n"; } } while (false);

unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;

// We're trying to find X such that
//
//  Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X
//
// We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),
// and check using SCEV if any of them are correct.

// Returns true if extending NonIVNarrowDef according to `SignExt` is a
// correct solution to X.
auto GuessNonIVOperand = [&](bool SignExt) {
  const SCEV *WideLHS;
  const SCEV *WideRHS;

  auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {
    if (SignExt)
      return SE->getSignExtendExpr(S, Ty);
    return SE->getZeroExtendExpr(S, Ty);
  };

  if (IVOpIdx == 0) {
    WideLHS = SE->getSCEV(WideDef);
    const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));
    WideRHS = GetExtend(NarrowRHS, WideType);
  } else {
    const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));
    WideLHS = GetExtend(NarrowLHS, WideType);
    WideRHS = SE->getSCEV(WideDef);
  }

  // WideUse is "WideDef `op.wide` X" as described in the comment.
  const SCEV *WideUse = nullptr;

  switch (NarrowUse->getOpcode()) {
  default:
    llvm_unreachable("No other possibility!")::llvm::llvm_unreachable_internal("No other possibility!", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1180);

  case Instruction::Add:
    WideUse = SE->getAddExpr(WideLHS, WideRHS);
    break;

  case Instruction::Mul:
    WideUse = SE->getMulExpr(WideLHS, WideRHS);
    break;

  case Instruction::UDiv:
    WideUse = SE->getUDivExpr(WideLHS, WideRHS);
    break;

  case Instruction::Sub:
    WideUse = SE->getMinusSCEV(WideLHS, WideRHS);
    break;
  }

  return WideUse == WideAR;
};

bool SignExtend = getExtendKind(NarrowDef) == SignExtended;
if (!GuessNonIVOperand(SignExtend)) {
  SignExtend = !SignExtend;
  if (!GuessNonIVOperand(SignExtend))
    return nullptr;
}

Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
                 ? WideDef
                 : createExtendInst(NarrowUse->getOperand(0), WideType,
                                    SignExtend, NarrowUse);
Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
                 ? WideDef
                 : createExtendInst(NarrowUse->getOperand(1), WideType,
                                    SignExtend, NarrowUse);

auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
                                      NarrowBO->getName());

IRBuilder<> Builder(NarrowUse);
Builder.Insert(WideBO);
WideBO->copyIRFlags(NarrowBO);
return WideBO;
1226}

1228WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {
auto It = ExtendKindMap.find(I);
assert(It != ExtendKindMap.end() && "Instruction not yet extended!")((It != ExtendKindMap.end() && "Instruction not yet extended!"
) ? static_cast<void> (0) : __assert_fail ("It != ExtendKindMap.end() && \"Instruction not yet extended!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1230, __PRETTY_FUNCTION__));
return It->second;
1232}

1234const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
                                   unsigned OpCode) const {
if (OpCode == Instruction::Add)
  return SE->getAddExpr(LHS, RHS);
if (OpCode == Instruction::Sub)
  return SE->getMinusSCEV(LHS, RHS);
if (OpCode == Instruction::Mul)
  return SE->getMulExpr(LHS, RHS);

llvm_unreachable("Unsupported opcode.")::llvm::llvm_unreachable_internal("Unsupported opcode.", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1243);
1244}

1246/// No-wrap operations can transfer sign extension of their result to their
1247/// operands. Generate the SCEV value for the widened operation without
1248/// actually modifying the IR yet. If the expression after extending the
1249/// operands is an AddRec for this loop, return the AddRec and the kind of
1250/// extension used.
1251WidenIV::WidenedRecTy WidenIV::getExtendedOperandRecurrence(NarrowIVDefUse DU) {
// Handle the common case of add<nsw/nuw>
const unsigned OpCode = DU.NarrowUse->getOpcode();
// Only Add/Sub/Mul instructions supported yet.
if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
    OpCode != Instruction::Mul)
  return {nullptr, Unknown};

// One operand (NarrowDef) has already been extended to WideDef. Now determine
// if extending the other will lead to a recurrence.
const unsigned ExtendOperIdx =
    DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU")((DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef
 && "bad DU") ? static_cast<void> (0) : __assert_fail
 ("DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && \"bad DU\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1263, __PRETTY_FUNCTION__));

const SCEV *ExtendOperExpr = nullptr;
const OverflowingBinaryOperator *OBO =
  cast<OverflowingBinaryOperator>(DU.NarrowUse);
ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
  ExtendOperExpr = SE->getSignExtendExpr(
    SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
else if(ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
  ExtendOperExpr = SE->getZeroExtendExpr(
    SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
else
  return {nullptr, Unknown};

// When creating this SCEV expr, don't apply the current operations NSW or NUW
// flags. This instruction may be guarded by control flow that the no-wrap
// behavior depends on. Non-control-equivalent instructions can be mapped to
// the same SCEV expression, and it would be incorrect to transfer NSW/NUW
// semantics to those operations.
const SCEV *lhs = SE->getSCEV(DU.WideDef);
const SCEV *rhs = ExtendOperExpr;

// Let's swap operands to the initial order for the case of non-commutative
// operations, like SUB. See PR21014.
if (ExtendOperIdx == 0)
  std::swap(lhs, rhs);
const SCEVAddRecExpr *AddRec =
    dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));

if (!AddRec || AddRec->getLoop() != L)
  return {nullptr, Unknown};

return {AddRec, ExtKind};
1297}

1299/// Is this instruction potentially interesting for further simplification after
1300/// widening it's type? In other words, can the extend be safely hoisted out of
1301/// the loop with SCEV reducing the value to a recurrence on the same loop. If
1302/// so, return the extended recurrence and the kind of extension used. Otherwise
1303/// return {nullptr, Unknown}.
1304WidenIV::WidenedRecTy WidenIV::getWideRecurrence(NarrowIVDefUse DU) {
if (!SE->isSCEVable(DU.NarrowUse->getType()))
  return {nullptr, Unknown};

const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);
if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=
    SE->getTypeSizeInBits(WideType)) {
  // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
  // index. So don't follow this use.
  return {nullptr, Unknown};
}

const SCEV *WideExpr;
ExtendKind ExtKind;
if (DU.NeverNegative) {
  WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
  if (isa<SCEVAddRecExpr>(WideExpr))
    ExtKind = SignExtended;
  else {
    WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
    ExtKind = ZeroExtended;
  }
} else if (getExtendKind(DU.NarrowDef) == SignExtended) {
  WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
  ExtKind = SignExtended;
} else {
  WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
  ExtKind = ZeroExtended;
}
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
if (!AddRec || AddRec->getLoop() != L)
  return {nullptr, Unknown};
return {AddRec, ExtKind};
1337}

1339/// This IV user cannot be widened. Replace this use of the original narrow IV
1340/// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
1341static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI) {
auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
if (!InsertPt)
  return;
LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Truncate IV " <<
 *DU.WideDef << " for user " << *DU.NarrowUse <<
 "\n"; } } while (false)
                  << *DU.NarrowUse << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Truncate IV " <<
 *DU.WideDef << " for user " << *DU.NarrowUse <<
 "\n"; } } while (false);
IRBuilder<> Builder(InsertPt);
Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1350}

1352/// If the narrow use is a compare instruction, then widen the compare
1353//  (and possibly the other operand).  The extend operation is hoisted into the
1354// loop preheader as far as possible.
1355bool WidenIV::widenLoopCompare(NarrowIVDefUse DU) {
ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);
if (!Cmp)
  return false;

// We can legally widen the comparison in the following two cases:
//
//  - The signedness of the IV extension and comparison match
//
//  - The narrow IV is always positive (and thus its sign extension is equal
//    to its zero extension).  For instance, let's say we're zero extending
//    %narrow for the following use
//
//      icmp slt i32 %narrow, %val   ... (A)
//
//    and %narrow is always positive.  Then
//
//      (A) == icmp slt i32 sext(%narrow), sext(%val)
//          == icmp slt i32 zext(%narrow), sext(%val)
bool IsSigned = getExtendKind(DU.NarrowDef) == SignExtended;
if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
  return false;

Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
unsigned IVWidth = SE->getTypeSizeInBits(WideType);
assert(CastWidth <= IVWidth && "Unexpected width while widening compare.")((CastWidth <= IVWidth && "Unexpected width while widening compare."
) ? static_cast<void> (0) : __assert_fail ("CastWidth <= IVWidth && \"Unexpected width while widening compare.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1381, __PRETTY_FUNCTION__));

// Widen the compare instruction.
auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
if (!InsertPt)
  return false;
IRBuilder<> Builder(InsertPt);
DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);

// Widen the other operand of the compare, if necessary.
if (CastWidth < IVWidth) {
  Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
  DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
}
return true;
1396}

1398/// If the narrow use is an instruction whose two operands are the defining
1399/// instruction of DU and a load instruction, then we have the following:
1400/// if the load is hoisted outside the loop, then we do not reach this function
1401/// as scalar evolution analysis works fine in widenIVUse with variables
1402/// hoisted outside the loop and efficient code is subsequently generated by
1403/// not emitting truncate instructions. But when the load is not hoisted
1404/// (whether due to limitation in alias analysis or due to a true legality),
1405/// then scalar evolution can not proceed with loop variant values and
1406/// inefficient code is generated. This function handles the non-hoisted load
1407/// special case by making the optimization generate the same type of code for
1408/// hoisted and non-hoisted load (widen use and eliminate sign extend
1409/// instruction). This special case is important especially when the induction
1410/// variables are affecting addressing mode in code generation.
1411bool WidenIV::widenWithVariantLoadUse(NarrowIVDefUse DU) {
Instruction *NarrowUse = DU.NarrowUse;
Instruction *NarrowDef = DU.NarrowDef;
Instruction *WideDef = DU.WideDef;

// Handle the common case of add<nsw/nuw>
const unsigned OpCode = NarrowUse->getOpcode();
// Only Add/Sub/Mul instructions are supported.
if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
    OpCode != Instruction::Mul)
  return false;

// The operand that is not defined by NarrowDef of DU. Let's call it the
// other operand.
unsigned ExtendOperIdx = DU.NarrowUse->getOperand(0) == NarrowDef ? 1 : 0;
assert(DU.NarrowUse->getOperand(1 - ExtendOperIdx) == DU.NarrowDef &&((DU.NarrowUse->getOperand(1 - ExtendOperIdx) == DU.NarrowDef
 && "bad DU") ? static_cast<void> (0) : __assert_fail
 ("DU.NarrowUse->getOperand(1 - ExtendOperIdx) == DU.NarrowDef && \"bad DU\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1427, __PRETTY_FUNCTION__))
       "bad DU")((DU.NarrowUse->getOperand(1 - ExtendOperIdx) == DU.NarrowDef
 && "bad DU") ? static_cast<void> (0) : __assert_fail
 ("DU.NarrowUse->getOperand(1 - ExtendOperIdx) == DU.NarrowDef && \"bad DU\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1427, __PRETTY_FUNCTION__));

const SCEV *ExtendOperExpr = nullptr;
const OverflowingBinaryOperator *OBO =
  cast<OverflowingBinaryOperator>(NarrowUse);
ExtendKind ExtKind = getExtendKind(NarrowDef);
if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
  ExtendOperExpr = SE->getSignExtendExpr(
    SE->getSCEV(NarrowUse->getOperand(ExtendOperIdx)), WideType);
else if (ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
  ExtendOperExpr = SE->getZeroExtendExpr(
    SE->getSCEV(NarrowUse->getOperand(ExtendOperIdx)), WideType);
else
  return false;

// We are interested in the other operand being a load instruction.
// But, we should look into relaxing this restriction later on.
auto *I = dyn_cast<Instruction>(NarrowUse->getOperand(ExtendOperIdx));
if (I && I->getOpcode() != Instruction::Load)
  return false;

// Verifying that Defining operand is an AddRec
const SCEV *Op1 = SE->getSCEV(WideDef);
const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Op1);
if (!AddRecOp1 || AddRecOp1->getLoop() != L)
  return false;
// Verifying that other operand is an Extend.
if (ExtKind == SignExtended) {
  if (!isa<SCEVSignExtendExpr>(ExtendOperExpr))
    return false;
} else {
  if (!isa<SCEVZeroExtendExpr>(ExtendOperExpr))
    return false;
}

if (ExtKind == SignExtended) {
  for (Use &U : NarrowUse->uses()) {
    SExtInst *User = dyn_cast<SExtInst>(U.getUser());
    if (!User || User->getType() != WideType)
      return false;
  }
} else { // ExtKind == ZeroExtended
  for (Use &U : NarrowUse->uses()) {
    ZExtInst *User = dyn_cast<ZExtInst>(U.getUser());
    if (!User || User->getType() != WideType)
      return false;
  }
}

return true;
1477}

1479/// Special Case for widening with variant Loads (see
1480/// WidenIV::widenWithVariantLoadUse). This is the code generation part.
1481void WidenIV::widenWithVariantLoadUseCodegen(NarrowIVDefUse DU) {
Instruction *NarrowUse = DU.NarrowUse;
Instruction *NarrowDef = DU.NarrowDef;
Instruction *WideDef = DU.WideDef;

ExtendKind ExtKind = getExtendKind(NarrowDef);

LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "Cloning arithmetic IVUser: " <<
 *NarrowUse << "\n"; } } while (false);

// Generating a widening use instruction.
Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
                 ? WideDef
                 : createExtendInst(NarrowUse->getOperand(0), WideType,
                                    ExtKind, NarrowUse);
Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
                 ? WideDef
                 : createExtendInst(NarrowUse->getOperand(1), WideType,
                                    ExtKind, NarrowUse);

auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
                                      NarrowBO->getName());
IRBuilder<> Builder(NarrowUse);
Builder.Insert(WideBO);
WideBO->copyIRFlags(NarrowBO);

if (ExtKind == SignExtended)
  ExtendKindMap[NarrowUse] = SignExtended;
else
  ExtendKindMap[NarrowUse] = ZeroExtended;

// Update the Use.
if (ExtKind == SignExtended) {
  for (Use &U : NarrowUse->uses()) {
    SExtInst *User = dyn_cast<SExtInst>(U.getUser());
    if (User && User->getType() == WideType) {
      LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: eliminating " <<
 *User << " replaced by " << *WideBO << "\n"
; } } while (false)
                        << *WideBO << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: eliminating " <<
 *User << " replaced by " << *WideBO << "\n"
; } } while (false);
      ++NumElimExt;
      User->replaceAllUsesWith(WideBO);
      DeadInsts.emplace_back(User);
    }
  }
} else { // ExtKind == ZeroExtended
  for (Use &U : NarrowUse->uses()) {
    ZExtInst *User = dyn_cast<ZExtInst>(U.getUser());
    if (User && User->getType() == WideType) {
      LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: eliminating " <<
 *User << " replaced by " << *WideBO << "\n"
; } } while (false)
                        << *WideBO << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: eliminating " <<
 *User << " replaced by " << *WideBO << "\n"
; } } while (false);
      ++NumElimExt;
      User->replaceAllUsesWith(WideBO);
      DeadInsts.emplace_back(User);
    }
  }
}
1536}

1538/// Determine whether an individual user of the narrow IV can be widened. If so,
1539/// return the wide clone of the user.
1540Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
assert(ExtendKindMap.count(DU.NarrowDef) &&((ExtendKindMap.count(DU.NarrowDef) && "Should already know the kind of extension used to widen NarrowDef"
) ? static_cast<void> (0) : __assert_fail ("ExtendKindMap.count(DU.NarrowDef) && \"Should already know the kind of extension used to widen NarrowDef\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1542, __PRETTY_FUNCTION__))
       "Should already know the kind of extension used to widen NarrowDef")((ExtendKindMap.count(DU.NarrowDef) && "Should already know the kind of extension used to widen NarrowDef"
) ? static_cast<void> (0) : __assert_fail ("ExtendKindMap.count(DU.NarrowDef) && \"Should already know the kind of extension used to widen NarrowDef\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1542, __PRETTY_FUNCTION__));

// Stop traversing the def-use chain at inner-loop phis or post-loop phis.
if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
  if (LI->getLoopFor(UsePhi->getParent()) != L) {
    // For LCSSA phis, sink the truncate outside the loop.
    // After SimplifyCFG most loop exit targets have a single predecessor.
    // Otherwise fall back to a truncate within the loop.
    if (UsePhi->getNumOperands() != 1)
      truncateIVUse(DU, DT, LI);
    else {
      // Widening the PHI requires us to insert a trunc.  The logical place
      // for this trunc is in the same BB as the PHI.  This is not possible if
      // the BB is terminated by a catchswitch.
      if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
        return nullptr;

      PHINode *WidePhi =
        PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
                        UsePhi);
      WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
      IRBuilder<> Builder(&*WidePhi->getParent()->getFirstInsertionPt());
      Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
      UsePhi->replaceAllUsesWith(Trunc);
      DeadInsts.emplace_back(UsePhi);
      LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Widen lcssa phi " <<
 *UsePhi << " to " << *WidePhi << "\n"; } }
 while (false)
                        << *WidePhi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Widen lcssa phi " <<
 *UsePhi << " to " << *WidePhi << "\n"; } }
 while (false);
    }
    return nullptr;
  }
}

// This narrow use can be widened by a sext if it's non-negative or its narrow
// def was widended by a sext. Same for zext.
auto canWidenBySExt = [&]() {
  return DU.NeverNegative || getExtendKind(DU.NarrowDef) == SignExtended;
};
auto canWidenByZExt = [&]() {
  return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ZeroExtended;
};

// Our raison d'etre! Eliminate sign and zero extension.
if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
    (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
  Value *NewDef = DU.WideDef;
  if (DU.NarrowUse->getType() != WideType) {
    unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
    unsigned IVWidth = SE->getTypeSizeInBits(WideType);
    if (CastWidth < IVWidth) {
      // The cast isn't as wide as the IV, so insert a Trunc.
      IRBuilder<> Builder(DU.NarrowUse);
      NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
    }
    else {
      // A wider extend was hidden behind a narrower one. This may induce
      // another round of IV widening in which the intermediate IV becomes
      // dead. It should be very rare.
      LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: New IV " << *WidePhi
 << " not wide enough to subsume " << *DU.NarrowUse
 << "\n"; } } while (false)
                        << " not wide enough to subsume " << *DU.NarrowUsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: New IV " << *WidePhi
 << " not wide enough to subsume " << *DU.NarrowUse
 << "\n"; } } while (false)
                        << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: New IV " << *WidePhi
 << " not wide enough to subsume " << *DU.NarrowUse
 << "\n"; } } while (false);
      DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
      NewDef = DU.NarrowUse;
    }
  }
  if (NewDef != DU.NarrowUse) {
    LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: eliminating " <<
 *DU.NarrowUse << " replaced by " << *DU.WideDef <<
 "\n"; } } while (false)
                      << " replaced by " << *DU.WideDef << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: eliminating " <<
 *DU.NarrowUse << " replaced by " << *DU.WideDef <<
 "\n"; } } while (false);
    ++NumElimExt;
    DU.NarrowUse->replaceAllUsesWith(NewDef);
    DeadInsts.emplace_back(DU.NarrowUse);
  }
  // Now that the extend is gone, we want to expose it's uses for potential
  // further simplification. We don't need to directly inform SimplifyIVUsers
  // of the new users, because their parent IV will be processed later as a
  // new loop phi. If we preserved IVUsers analysis, we would also want to
  // push the uses of WideDef here.

  // No further widening is needed. The deceased [sz]ext had done it for us.
  return nullptr;
}

// Does this user itself evaluate to a recurrence after widening?
WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
if (!WideAddRec.first)
  WideAddRec = getWideRecurrence(DU);

assert((WideAddRec.first == nullptr) == (WideAddRec.second == Unknown))(((WideAddRec.first == nullptr) == (WideAddRec.second == Unknown
)) ? static_cast<void> (0) : __assert_fail ("(WideAddRec.first == nullptr) == (WideAddRec.second == Unknown)"
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1628, __PRETTY_FUNCTION__));
if (!WideAddRec.first) {
  // If use is a loop condition, try to promote the condition instead of
  // truncating the IV first.
  if (widenLoopCompare(DU))
    return nullptr;

  // We are here about to generate a truncate instruction that may hurt
  // performance because the scalar evolution expression computed earlier
  // in WideAddRec.first does not indicate a polynomial induction expression.
  // In that case, look at the operands of the use instruction to determine
  // if we can still widen the use instead of truncating its operand.
  if (widenWithVariantLoadUse(DU)) {
    widenWithVariantLoadUseCodegen(DU);
    return nullptr;
  }

  // This user does not evaluate to a recurrence after widening, so don't
  // follow it. Instead insert a Trunc to kill off the original use,
  // eventually isolating the original narrow IV so it can be removed.
  truncateIVUse(DU, DT, LI);
  return nullptr;
}
// Assume block terminators cannot evaluate to a recurrence. We can't to
// insert a Trunc after a terminator if there happens to be a critical edge.
assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() &&((DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator
() && "SCEV is not expected to evaluate a block terminator"
) ? static_cast<void> (0) : __assert_fail ("DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() && \"SCEV is not expected to evaluate a block terminator\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1654, __PRETTY_FUNCTION__))
       "SCEV is not expected to evaluate a block terminator")((DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator
() && "SCEV is not expected to evaluate a block terminator"
) ? static_cast<void> (0) : __assert_fail ("DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() && \"SCEV is not expected to evaluate a block terminator\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1654, __PRETTY_FUNCTION__));

// Reuse the IV increment that SCEVExpander created as long as it dominates
// NarrowUse.
Instruction *WideUse = nullptr;
if (WideAddRec.first == WideIncExpr &&
    Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
  WideUse = WideInc;
else {
  WideUse = cloneIVUser(DU, WideAddRec.first);
  if (!WideUse)
    return nullptr;
}
// Evaluation of WideAddRec ensured that the narrow expression could be
// extended outside the loop without overflow. This suggests that the wide use
// evaluates to the same expression as the extended narrow use, but doesn't
// absolutely guarantee it. Hence the following failsafe check. In rare cases
// where it fails, we simply throw away the newly created wide use.
if (WideAddRec.first != SE->getSCEV(WideUse)) {
  LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "Wide use expression mismatch: "
 << *WideUse << ": " << *SE->getSCEV(WideUse
) << " != " << *WideAddRec.first << "\n"; }
 } while (false)
                    << *SE->getSCEV(WideUse) << " != " << *WideAddRec.firstdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "Wide use expression mismatch: "
 << *WideUse << ": " << *SE->getSCEV(WideUse
) << " != " << *WideAddRec.first << "\n"; }
 } while (false)
                    << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "Wide use expression mismatch: "
 << *WideUse << ": " << *SE->getSCEV(WideUse
) << " != " << *WideAddRec.first << "\n"; }
 } while (false);
  DeadInsts.emplace_back(WideUse);
  return nullptr;
}

// if we reached this point then we are going to replace
// DU.NarrowUse with WideUse. Reattach DbgValue then.
replaceAllDbgUsesWith(*DU.NarrowUse, *WideUse, *WideUse, *DT);

ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
// Returning WideUse pushes it on the worklist.
return WideUse;
1687}

1689/// Add eligible users of NarrowDef to NarrowIVUsers.
1690void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
bool NonNegativeDef =
    SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
                         SE->getConstant(NarrowSCEV->getType(), 0));
for (User *U : NarrowDef->users()) {
  Instruction *NarrowUser = cast<Instruction>(U);

  // Handle data flow merges and bizarre phi cycles.
  if (!Widened.insert(NarrowUser).second)
    continue;

  bool NonNegativeUse = false;
  if (!NonNegativeDef) {
    // We might have a control-dependent range information for this context.
    if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
      NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
  }

  NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
                             NonNegativeDef || NonNegativeUse);
}
1712}

1714/// Process a single induction variable. First use the SCEVExpander to create a
1715/// wide induction variable that evaluates to the same recurrence as the
1716/// original narrow IV. Then use a worklist to forward traverse the narrow IV's
1717/// def-use chain. After widenIVUse has processed all interesting IV users, the
1718/// narrow IV will be isolated for removal by DeleteDeadPHIs.
1719///
1720/// It would be simpler to delete uses as they are processed, but we must avoid
1721/// invalidating SCEV expressions.
1722PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
// Is this phi an induction variable?
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
if (!AddRec)
  return nullptr;

// Widen the induction variable expression.
const SCEV *WideIVExpr = getExtendKind(OrigPhi) == SignExtended
                             ? SE->getSignExtendExpr(AddRec, WideType)
                             : SE->getZeroExtendExpr(AddRec, WideType);

assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&((SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType
 && "Expect the new IV expression to preserve its type"
) ? static_cast<void> (0) : __assert_fail ("SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType && \"Expect the new IV expression to preserve its type\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1734, __PRETTY_FUNCTION__))
       "Expect the new IV expression to preserve its type")((SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType
 && "Expect the new IV expression to preserve its type"
) ? static_cast<void> (0) : __assert_fail ("SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType && \"Expect the new IV expression to preserve its type\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1734, __PRETTY_FUNCTION__));

// Can the IV be extended outside the loop without overflow?
AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
if (!AddRec || AddRec->getLoop() != L)
  return nullptr;

// An AddRec must have loop-invariant operands. Since this AddRec is
// materialized by a loop header phi, the expression cannot have any post-loop
// operands, so they must dominate the loop header.
assert(((SE->properlyDominates(AddRec->getStart(), L->getHeader
()) && SE->properlyDominates(AddRec->getStepRecurrence
(*SE), L->getHeader()) && "Loop header phi recurrence inputs do not dominate the loop"
) ? static_cast<void> (0) : __assert_fail ("SE->properlyDominates(AddRec->getStart(), L->getHeader()) && SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) && \"Loop header phi recurrence inputs do not dominate the loop\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1747, __PRETTY_FUNCTION__))
    SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&((SE->properlyDominates(AddRec->getStart(), L->getHeader
()) && SE->properlyDominates(AddRec->getStepRecurrence
(*SE), L->getHeader()) && "Loop header phi recurrence inputs do not dominate the loop"
) ? static_cast<void> (0) : __assert_fail ("SE->properlyDominates(AddRec->getStart(), L->getHeader()) && SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) && \"Loop header phi recurrence inputs do not dominate the loop\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1747, __PRETTY_FUNCTION__))
    SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&((SE->properlyDominates(AddRec->getStart(), L->getHeader
()) && SE->properlyDominates(AddRec->getStepRecurrence
(*SE), L->getHeader()) && "Loop header phi recurrence inputs do not dominate the loop"
) ? static_cast<void> (0) : __assert_fail ("SE->properlyDominates(AddRec->getStart(), L->getHeader()) && SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) && \"Loop header phi recurrence inputs do not dominate the loop\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1747, __PRETTY_FUNCTION__))
    "Loop header phi recurrence inputs do not dominate the loop")((SE->properlyDominates(AddRec->getStart(), L->getHeader
()) && SE->properlyDominates(AddRec->getStepRecurrence
(*SE), L->getHeader()) && "Loop header phi recurrence inputs do not dominate the loop"
) ? static_cast<void> (0) : __assert_fail ("SE->properlyDominates(AddRec->getStart(), L->getHeader()) && SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) && \"Loop header phi recurrence inputs do not dominate the loop\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1747, __PRETTY_FUNCTION__));

// Iterate over IV uses (including transitive ones) looking for IV increments
// of the form 'add nsw %iv, <const>'. For each increment and each use of
// the increment calculate control-dependent range information basing on
// dominating conditions inside of the loop (e.g. a range check inside of the
// loop). Calculated ranges are stored in PostIncRangeInfos map.
//
// Control-dependent range information is later used to prove that a narrow
// definition is not negative (see pushNarrowIVUsers). It's difficult to do
// this on demand because when pushNarrowIVUsers needs this information some
// of the dominating conditions might be already widened.
if (UsePostIncrementRanges)
  calculatePostIncRanges(OrigPhi);

// The rewriter provides a value for the desired IV expression. This may
// either find an existing phi or materialize a new one. Either way, we
// expect a well-formed cyclic phi-with-increments. i.e. any operand not part
// of the phi-SCC dominates the loop entry.
Instruction *InsertPt = &L->getHeader()->front();
WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt));

// Remembering the WideIV increment generated by SCEVExpander allows
// widenIVUse to reuse it when widening the narrow IV's increment. We don't
// employ a general reuse mechanism because the call above is the only call to
// SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
if (BasicBlock *LatchBlock = L->getLoopLatch()) {
  WideInc =
    cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
  WideIncExpr = SE->getSCEV(WideInc);
  // Propagate the debug location associated with the original loop increment
  // to the new (widened) increment.
  auto *OrigInc =
    cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
  WideInc->setDebugLoc(OrigInc->getDebugLoc());
}

LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "Wide IV: " << *WidePhi <<
 "\n"; } } while (false);
++NumWidened;

// Traverse the def-use chain using a worklist starting at the original IV.
assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" )((Widened.empty() && NarrowIVUsers.empty() &&
 "expect initial state") ? static_cast<void> (0) : __assert_fail
 ("Widened.empty() && NarrowIVUsers.empty() && \"expect initial state\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 1788, __PRETTY_FUNCTION__));

Widened.insert(OrigPhi);
pushNarrowIVUsers(OrigPhi, WidePhi);

while (!NarrowIVUsers.empty()) {
  NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();

  // Process a def-use edge. This may replace the use, so don't hold a
  // use_iterator across it.
  Instruction *WideUse = widenIVUse(DU, Rewriter);

  // Follow all def-use edges from the previous narrow use.
  if (WideUse)
    pushNarrowIVUsers(DU.NarrowUse, WideUse);

  // widenIVUse may have removed the def-use edge.
  if (DU.NarrowDef->use_empty())
    DeadInsts.emplace_back(DU.NarrowDef);
}

// Attach any debug information to the new PHI.
replaceAllDbgUsesWith(*OrigPhi, *WidePhi, *WidePhi, *DT);

return WidePhi;
1813}

1815/// Calculates control-dependent range for the given def at the given context
1816/// by looking at dominating conditions inside of the loop
1817void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
                                  Instruction *NarrowUser) {
using namespace llvm::PatternMatch;

Value *NarrowDefLHS;
const APInt *NarrowDefRHS;
if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),
                               m_APInt(NarrowDefRHS))) ||
    !NarrowDefRHS->isNonNegative())
  return;

auto UpdateRangeFromCondition = [&] (Value *Condition,
                                     bool TrueDest) {
  CmpInst::Predicate Pred;
  Value *CmpRHS;
  if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),
                               m_Value(CmpRHS))))
    return;

  CmpInst::Predicate P =
          TrueDest ? Pred : CmpInst::getInversePredicate(Pred);

  auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));
  auto CmpConstrainedLHSRange =
          ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);
  auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
      *NarrowDefRHS, OverflowingBinaryOperator::NoSignedWrap);

  updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
};

auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
  if (!HasGuards)
    return;

  for (Instruction &I : make_range(Ctx->getIterator().getReverse(),
                                   Ctx->getParent()->rend())) {
    Value *C = nullptr;
    if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))
      UpdateRangeFromCondition(C, /*TrueDest=*/true);
  }
};

UpdateRangeFromGuards(NarrowUser);

BasicBlock *NarrowUserBB = NarrowUser->getParent();
// If NarrowUserBB is statically unreachable asking dominator queries may
// yield surprising results. (e.g. the block may not have a dom tree node)
if (!DT->isReachableFromEntry(NarrowUserBB))
  return;

for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
     L->contains(DTB->getBlock());
     DTB = DTB->getIDom()) {
  auto *BB = DTB->getBlock();
  auto *TI = BB->getTerminator();
  UpdateRangeFromGuards(TI);

  auto *BI = dyn_cast<BranchInst>(TI);
  if (!BI || !BI->isConditional())
    continue;

  auto *TrueSuccessor = BI->getSuccessor(0);
  auto *FalseSuccessor = BI->getSuccessor(1);

  auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {
    return BBE.isSingleEdge() &&
           DT->dominates(BBE, NarrowUser->getParent());
  };

  if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))
    UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);

  if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))
    UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
}
1893}

1895/// Calculates PostIncRangeInfos map for the given IV
1896void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
SmallPtrSet<Instruction *, 16> Visited;
SmallVector<Instruction *, 6> Worklist;
Worklist.push_back(OrigPhi);
Visited.insert(OrigPhi);

while (!Worklist.empty()) {
  Instruction *NarrowDef = Worklist.pop_back_val();

  for (Use &U : NarrowDef->uses()) {
    auto *NarrowUser = cast<Instruction>(U.getUser());

    // Don't go looking outside the current loop.
    auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
    if (!NarrowUserLoop || !L->contains(NarrowUserLoop))
      continue;

    if (!Visited.insert(NarrowUser).second)
      continue;

    Worklist.push_back(NarrowUser);

    calculatePostIncRange(NarrowDef, NarrowUser);
  }
}
1921}

1923//===----------------------------------------------------------------------===//
1924//  Live IV Reduction - Minimize IVs live across the loop.
1925//===----------------------------------------------------------------------===//

1927//===----------------------------------------------------------------------===//
1928//  Simplification of IV users based on SCEV evaluation.
1929//===----------------------------------------------------------------------===//

1931namespace {

1933class IndVarSimplifyVisitor : public IVVisitor {
ScalarEvolution *SE;
const TargetTransformInfo *TTI;
PHINode *IVPhi;

1938public:
WideIVInfo WI;

IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV,
                      const TargetTransformInfo *TTI,
                      const DominatorTree *DTree)
  : SE(SCEV), TTI(TTI), IVPhi(IV) {
  DT = DTree;
  WI.NarrowIV = IVPhi;
}

// Implement the interface used by simplifyUsersOfIV.
void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); }
1951};

1953} // end anonymous namespace

1955/// Iteratively perform simplification on a worklist of IV users. Each
1956/// successive simplification may push more users which may themselves be
1957/// candidates for simplification.
1958///
1959/// Sign/Zero extend elimination is interleaved with IV simplification.
1960bool IndVarSimplify::simplifyAndExtend(Loop *L,
                                     SCEVExpander &Rewriter,
                                     LoopInfo *LI) {
SmallVector<WideIVInfo, 8> WideIVs;

auto *GuardDecl = L->getBlocks()[0]->getModule()->getFunction(
        Intrinsic::getName(Intrinsic::experimental_guard));
bool HasGuards = GuardDecl && !GuardDecl->use_empty();

SmallVector<PHINode*, 8> LoopPhis;
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
  LoopPhis.push_back(cast<PHINode>(I));
}
// Each round of simplification iterates through the SimplifyIVUsers worklist
// for all current phis, then determines whether any IVs can be
// widened. Widening adds new phis to LoopPhis, inducing another round of
// simplification on the wide IVs.
bool Changed = false;
while (!LoopPhis.empty()) {
  // Evaluate as many IV expressions as possible before widening any IVs. This
  // forces SCEV to set no-wrap flags before evaluating sign/zero
  // extension. The first time SCEV attempts to normalize sign/zero extension,
  // the result becomes final. So for the most predictable results, we delay
  // evaluation of sign/zero extend evaluation until needed, and avoid running
  // other SCEV based analysis prior to simplifyAndExtend.
  do {
    PHINode *CurrIV = LoopPhis.pop_back_val();

    // Information about sign/zero extensions of CurrIV.
    IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT);

    Changed |=
        simplifyUsersOfIV(CurrIV, SE, DT, LI, DeadInsts, Rewriter, &Visitor);

    if (Visitor.WI.WidestNativeType) {
      WideIVs.push_back(Visitor.WI);
    }
  } while(!LoopPhis.empty());

  for (; !WideIVs.empty(); WideIVs.pop_back()) {
    WidenIV Widener(WideIVs.back(), LI, SE, DT, DeadInsts, HasGuards);
    if (PHINode *WidePhi = Widener.createWideIV(Rewriter)) {
      Changed = true;
      LoopPhis.push_back(WidePhi);
    }
  }
}
return Changed;
2008}

2010//===----------------------------------------------------------------------===//
2011//  linearFunctionTestReplace and its kin. Rewrite the loop exit condition.
2012//===----------------------------------------------------------------------===//

2014/// Given an Value which is hoped to be part of an add recurance in the given
2015/// loop, return the associated Phi node if so.  Otherwise, return null.  Note
2016/// that this is less general than SCEVs AddRec checking.  
2017static PHINode *getLoopPhiForCounter(Value *IncV, Loop *L) {
Instruction *IncI = dyn_cast<Instruction>(IncV);
if (!IncI)
  return nullptr;

switch (IncI->getOpcode()) {
case Instruction::Add:
case Instruction::Sub:
  break;
case Instruction::GetElementPtr:
  // An IV counter must preserve its type.
  if (IncI->getNumOperands() == 2)
    break;
  LLVM_FALLTHROUGH[[gnu::fallthrough]];
default:
  return nullptr;
}

PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0));
if (Phi && Phi->getParent() == L->getHeader()) {
  if (L->isLoopInvariant(IncI->getOperand(1)))
    return Phi;
  return nullptr;
}
if (IncI->getOpcode() == Instruction::GetElementPtr)
  return nullptr;

// Allow add/sub to be commuted.
Phi = dyn_cast<PHINode>(IncI->getOperand(1));
if (Phi && Phi->getParent() == L->getHeader()) {
  if (L->isLoopInvariant(IncI->getOperand(0)))
    return Phi;
}
return nullptr;
2051}

2053/// Whether the current loop exit test is based on this value.  Currently this
2054/// is limited to a direct use in the loop condition.
2055static bool isLoopExitTestBasedOn(Value *V, BasicBlock *ExitingBB) {
BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());
ICmpInst *ICmp = dyn_cast<ICmpInst>(BI->getCondition());
// TODO: Allow non-icmp loop test.
if (!ICmp)
  return false;

// TODO: Allow indirect use.
return ICmp->getOperand(0) == V || ICmp->getOperand(1) == V;
2064}

2066/// linearFunctionTestReplace policy. Return true unless we can show that the
2067/// current exit test is already sufficiently canonical.
2068static bool needsLFTR(Loop *L, BasicBlock *ExitingBB) {
assert(L->getLoopLatch() && "Must be in simplified form")((L->getLoopLatch() && "Must be in simplified form"
) ? static_cast<void> (0) : __assert_fail ("L->getLoopLatch() && \"Must be in simplified form\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2069, __PRETTY_FUNCTION__));

// Avoid converting a constant or loop invariant test back to a runtime
// test.  This is critical for when SCEV's cached ExitCount is less precise
// than the current IR (such as after we've proven a particular exit is
// actually dead and thus the BE count never reaches our ExitCount.)
BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());
if (L->isLoopInvariant(BI->getCondition()))
  return false;

// Do LFTR to simplify the exit condition to an ICMP.
ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition());
if (!Cond)
  return true;

// Do LFTR to simplify the exit ICMP to EQ/NE
ICmpInst::Predicate Pred = Cond->getPredicate();
if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
  return true;

// Look for a loop invariant RHS
Value *LHS = Cond->getOperand(0);
Value *RHS = Cond->getOperand(1);
if (!L->isLoopInvariant(RHS)) {
  if (!L->isLoopInvariant(LHS))
    return true;
  std::swap(LHS, RHS);
}
// Look for a simple IV counter LHS
PHINode *Phi = dyn_cast<PHINode>(LHS);
if (!Phi)
  Phi = getLoopPhiForCounter(LHS, L);

if (!Phi)
  return true;

// Do LFTR if PHI node is defined in the loop, but is *not* a counter.
int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());
if (Idx < 0)
  return true;

// Do LFTR if the exit condition's IV is *not* a simple counter.
Value *IncV = Phi->getIncomingValue(Idx);
return Phi != getLoopPhiForCounter(IncV, L);
2113}

2115/// Return true if undefined behavior would provable be executed on the path to
2116/// OnPathTo if Root produced a posion result.  Note that this doesn't say
2117/// anything about whether OnPathTo is actually executed or whether Root is
2118/// actually poison.  This can be used to assess whether a new use of Root can
2119/// be added at a location which is control equivalent with OnPathTo (such as
2120/// immediately before it) without introducing UB which didn't previously
2121/// exist.  Note that a false result conveys no information.  
2122static bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root,
                                        Instruction *OnPathTo, 
                                        DominatorTree *DT) {
// Basic approach is to assume Root is poison, propagate poison forward
// through all users we can easily track, and then check whether any of those
// users are provable UB and must execute before out exiting block might
// exit.

// The set of all recursive users we've visited (which are assumed to all be
// poison because of said visit)
SmallSet<const Value *, 16> KnownPoison;
SmallVector<const Instruction*, 16> Worklist;
Worklist.push_back(Root);
while (!Worklist.empty()) {
  const Instruction *I = Worklist.pop_back_val();

  // If we know this must trigger UB on a path leading our target.
  if (mustTriggerUB(I, KnownPoison) && DT->dominates(I, OnPathTo))
    return true;
  
  // If we can't analyze propagation through this instruction, just skip it
  // and transitive users.  Safe as false is a conservative result.
  if (!propagatesFullPoison(I) && I != Root)
    continue;

  if (KnownPoison.insert(I).second)
    for (const User *User : I->users())
      Worklist.push_back(cast<Instruction>(User));
}

// Might be non-UB, or might have a path we couldn't prove must execute on
// way to exiting bb. 
return false;
2155}

2157/// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils
2158/// down to checking that all operands are constant and listing instructions
2159/// that may hide undef.
2160static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl<Value*> &Visited,
                             unsigned Depth) {
if (isa<Constant>(V))
  return !isa<UndefValue>(V);

if (Depth >= 6)
  return false;

// Conservatively handle non-constant non-instructions. For example, Arguments
// may be undef.
Instruction *I = dyn_cast<Instruction>(V);
if (!I)
  return false;

// Load and return values may be undef.
if(I->mayReadFromMemory() || isa<CallInst>(I) || isa<InvokeInst>(I))
  return false;

// Optimistically handle other instructions.
for (Value *Op : I->operands()) {
  if (!Visited.insert(Op).second)
    continue;
  if (!hasConcreteDefImpl(Op, Visited, Depth+1))
    return false;
}
return true;
2186}

2188/// Return true if the given value is concrete. We must prove that undef can
2189/// never reach it.
2190///
2191/// TODO: If we decide that this is a good approach to checking for undef, we
2192/// may factor it into a common location.
2193static bool hasConcreteDef(Value *V) {
SmallPtrSet<Value*, 8> Visited;
Visited.insert(V);
return hasConcreteDefImpl(V, Visited, 0);
2197}

2199/// Return true if this IV has any uses other than the (soon to be rewritten)
2200/// loop exit test.
2201static bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) {
int LatchIdx = Phi->getBasicBlockIndex(LatchBlock);
Value *IncV = Phi->getIncomingValue(LatchIdx);

for (User *U : Phi->users())
  if (U != Cond && U != IncV) return false;

for (User *U : IncV->users())
  if (U != Cond && U != Phi) return false;
return true;
2211}

2213/// Return true if the given phi is a "counter" in L.  A counter is an
2214/// add recurance (of integer or pointer type) with an arbitrary start, and a
2215/// step of 1.  Note that L must have exactly one latch.
2216static bool isLoopCounter(PHINode* Phi, Loop *L,
                        ScalarEvolution *SE) {
assert(Phi->getParent() == L->getHeader())((Phi->getParent() == L->getHeader()) ? static_cast<
void> (0) : __assert_fail ("Phi->getParent() == L->getHeader()"
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2218, __PRETTY_FUNCTION__));
27
←
Assuming the condition is true→
28
←
'?' condition is true→
assert(L->getLoopLatch())((L->getLoopLatch()) ? static_cast<void> (0) : __assert_fail
 ("L->getLoopLatch()", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2219, __PRETTY_FUNCTION__));
29
←
Assuming the condition is true→
30
←
'?' condition is true→

if (!SE->isSCEVable(Phi->getType()))
31
←
Assuming the condition is false→
32
←
Taking false branch→
  return false;

const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi));
33
←
Assuming the object is a 'SCEVAddRecExpr'→
if (!AR33.1
'AR' is non-null, which participates in a condition later
1
'AR' is non-null, which participates in a condition later
1
'AR' is non-null, which participates in a condition later
 || AR->getLoop() != L || !AR->isAffine())
34
←
Assuming the condition is false→
35
←
Calling 'SCEVAddRecExpr::isAffine'→
38
←
Returning from 'SCEVAddRecExpr::isAffine'→
39
←
Taking false branch→
  return false;

const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE));
40
←
Assuming the object is a 'SCEVConstant'→
if (!Step40.1
'Step' is non-null, which participates in a condition later
1
'Step' is non-null, which participates in a condition later
1
'Step' is non-null, which participates in a condition later
 || !Step->isOne())
41
←
Assuming the condition is false→
42
←
Taking false branch→
  return false;

int LatchIdx = Phi->getBasicBlockIndex(L->getLoopLatch());
Value *IncV = Phi->getIncomingValue(LatchIdx);
return (getLoopPhiForCounter(IncV, L) == Phi);
43
←
Assuming the condition is true→
44
←
Returning the value 1, which participates in a condition later→
2235}

2237/// Search the loop header for a loop counter (anadd rec w/step of one)
2238/// suitable for use by LFTR.  If multiple counters are available, select the
2239/// "best" one based profitable heuristics.
2240///
2241/// BECount may be an i8* pointer type. The pointer difference is already
2242/// valid count without scaling the address stride, so it remains a pointer
2243/// expression as far as SCEV is concerned.
2244static PHINode *FindLoopCounter(Loop *L, BasicBlock *ExitingBB,
                              const SCEV *BECount,
                              ScalarEvolution *SE, DominatorTree *DT) {
uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType());

Value *Cond = cast<BranchInst>(ExitingBB->getTerminator())->getCondition();
21
←
The object is a 'BranchInst'→

// Loop over all of the PHI nodes, looking for a simple counter.
PHINode *BestPhi = nullptr;
const SCEV *BestInit = nullptr;
BasicBlock *LatchBlock = L->getLoopLatch();
assert(LatchBlock && "Must be in simplified form")((LatchBlock && "Must be in simplified form") ? static_cast
<void> (0) : __assert_fail ("LatchBlock && \"Must be in simplified form\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2255, __PRETTY_FUNCTION__));
22
←
Assuming 'LatchBlock' is non-null→
23
←
'?' condition is true→
const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();

for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
24
←
Assuming 'I' is a 'PHINode'→
25
←
Loop condition is true.  Entering loop body→
  PHINode *Phi = cast<PHINode>(I);
  if (!isLoopCounter(Phi, L, SE))
26
←
Calling 'isLoopCounter'→
45
←
Returning from 'isLoopCounter'→
46
←
Taking false branch→
    continue;

  // Avoid comparing an integer IV against a pointer Limit.
  if (BECount->getType()->isPointerTy() && !Phi->getType()->isPointerTy())
47
←
Calling 'Type::isPointerTy'→
50
←
Returning from 'Type::isPointerTy'→
    continue;

  const auto *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi));
51
←
Assuming the object is not a 'SCEVAddRecExpr'→
52
←
'AR' initialized to a null pointer value→
  
  // AR may be a pointer type, while BECount is an integer type.
  // AR may be wider than BECount. With eq/ne tests overflow is immaterial.
  // AR may not be a narrower type, or we may never exit.
  uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType());
53
←
Called C++ object pointer is null
  if (PhiWidth < BCWidth || !DL.isLegalInteger(PhiWidth))
    continue;

  // Avoid reusing a potentially undef value to compute other values that may
  // have originally had a concrete definition.
  if (!hasConcreteDef(Phi)) {
    // We explicitly allow unknown phis as long as they are already used by
    // the loop exit test.  This is legal since performing LFTR could not
    // increase the number of undef users. 
    Value *IncPhi = Phi->getIncomingValueForBlock(LatchBlock);
    if (!isLoopExitTestBasedOn(Phi, ExitingBB) &&
        !isLoopExitTestBasedOn(IncPhi, ExitingBB))
      continue;
  }

  // Avoid introducing undefined behavior due to poison which didn't exist in
  // the original program.  (Annoyingly, the rules for poison and undef
  // propagation are distinct, so this does NOT cover the undef case above.)
  // We have to ensure that we don't introduce UB by introducing a use on an
  // iteration where said IV produces poison.  Our strategy here differs for
  // pointers and integer IVs.  For integers, we strip and reinfer as needed,
  // see code in linearFunctionTestReplace.  For pointers, we restrict
  // transforms as there is no good way to reinfer inbounds once lost.
  if (!Phi->getType()->isIntegerTy() &&
      !mustExecuteUBIfPoisonOnPathTo(Phi, ExitingBB->getTerminator(), DT))
    continue;
  
  const SCEV *Init = AR->getStart();

  if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) {
    // Don't force a live loop counter if another IV can be used.
    if (AlmostDeadIV(Phi, LatchBlock, Cond))
      continue;

    // Prefer to count-from-zero. This is a more "canonical" counter form. It
    // also prefers integer to pointer IVs.
    if (BestInit->isZero() != Init->isZero()) {
      if (BestInit->isZero())
        continue;
    }
    // If two IVs both count from zero or both count from nonzero then the
    // narrower is likely a dead phi that has been widened. Use the wider phi
    // to allow the other to be eliminated.
    else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType()))
      continue;
  }
  BestPhi = Phi;
  BestInit = Init;
}
return BestPhi;
2323}

2325/// Insert an IR expression which computes the value held by the IV IndVar
2326/// (which must be an loop counter w/unit stride) after the backedge of loop L
2327/// is taken ExitCount times.
2328static Value *genLoopLimit(PHINode *IndVar, BasicBlock *ExitingBB,
                         const SCEV *ExitCount, bool UsePostInc, Loop *L,
                         SCEVExpander &Rewriter, ScalarEvolution *SE) {
assert(isLoopCounter(IndVar, L, SE))((isLoopCounter(IndVar, L, SE)) ? static_cast<void> (0)
 : __assert_fail ("isLoopCounter(IndVar, L, SE)", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2331, __PRETTY_FUNCTION__));
const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));
const SCEV *IVInit = AR->getStart();

// IVInit may be a pointer while ExitCount is an integer when FindLoopCounter
// finds a valid pointer IV. Sign extend ExitCount in order to materialize a
// GEP. Avoid running SCEVExpander on a new pointer value, instead reusing
// the existing GEPs whenever possible.
if (IndVar->getType()->isPointerTy() &&
    !ExitCount->getType()->isPointerTy()) {
  // IVOffset will be the new GEP offset that is interpreted by GEP as a
  // signed value. ExitCount on the other hand represents the loop trip count,
  // which is an unsigned value. FindLoopCounter only allows induction
  // variables that have a positive unit stride of one. This means we don't
  // have to handle the case of negative offsets (yet) and just need to zero
  // extend ExitCount.
  Type *OfsTy = SE->getEffectiveSCEVType(IVInit->getType());
  const SCEV *IVOffset = SE->getTruncateOrZeroExtend(ExitCount, OfsTy);
  if (UsePostInc)
    IVOffset = SE->getAddExpr(IVOffset, SE->getOne(OfsTy));

  // Expand the code for the iteration count.
  assert(SE->isLoopInvariant(IVOffset, L) &&((SE->isLoopInvariant(IVOffset, L) && "Computed iteration count is not loop invariant!"
) ? static_cast<void> (0) : __assert_fail ("SE->isLoopInvariant(IVOffset, L) && \"Computed iteration count is not loop invariant!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2354, __PRETTY_FUNCTION__))
         "Computed iteration count is not loop invariant!")((SE->isLoopInvariant(IVOffset, L) && "Computed iteration count is not loop invariant!"
) ? static_cast<void> (0) : __assert_fail ("SE->isLoopInvariant(IVOffset, L) && \"Computed iteration count is not loop invariant!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2354, __PRETTY_FUNCTION__));

  // We could handle pointer IVs other than i8*, but we need to compensate for
  // gep index scaling.
  assert(SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext()),((SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext
()), cast<PointerType>(IndVar->getType()) ->getElementType
())->isOne() && "unit stride pointer IV must be i8*"
) ? static_cast<void> (0) : __assert_fail ("SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext()), cast<PointerType>(IndVar->getType()) ->getElementType())->isOne() && \"unit stride pointer IV must be i8*\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2361, __PRETTY_FUNCTION__))
                           cast<PointerType>(IndVar->getType())((SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext
()), cast<PointerType>(IndVar->getType()) ->getElementType
())->isOne() && "unit stride pointer IV must be i8*"
) ? static_cast<void> (0) : __assert_fail ("SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext()), cast<PointerType>(IndVar->getType()) ->getElementType())->isOne() && \"unit stride pointer IV must be i8*\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2361, __PRETTY_FUNCTION__))
                               ->getElementType())->isOne() &&((SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext
()), cast<PointerType>(IndVar->getType()) ->getElementType
())->isOne() && "unit stride pointer IV must be i8*"
) ? static_cast<void> (0) : __assert_fail ("SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext()), cast<PointerType>(IndVar->getType()) ->getElementType())->isOne() && \"unit stride pointer IV must be i8*\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2361, __PRETTY_FUNCTION__))
         "unit stride pointer IV must be i8*")((SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext
()), cast<PointerType>(IndVar->getType()) ->getElementType
())->isOne() && "unit stride pointer IV must be i8*"
) ? static_cast<void> (0) : __assert_fail ("SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext()), cast<PointerType>(IndVar->getType()) ->getElementType())->isOne() && \"unit stride pointer IV must be i8*\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2361, __PRETTY_FUNCTION__));

  const SCEV *IVLimit = SE->getAddExpr(IVInit, IVOffset);
  BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());
  return Rewriter.expandCodeFor(IVLimit, IndVar->getType(), BI);
} else {
  // In any other case, convert both IVInit and ExitCount to integers before
  // comparing. This may result in SCEV expansion of pointers, but in practice
  // SCEV will fold the pointer arithmetic away as such:
  // BECount = (IVEnd - IVInit - 1) => IVLimit = IVInit (postinc).
  //
  // Valid Cases: (1) both integers is most common; (2) both may be pointers
  // for simple memset-style loops.
  //
  // IVInit integer and ExitCount pointer would only occur if a canonical IV
  // were generated on top of case #2, which is not expected.

  assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride")((AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride"
) ? static_cast<void> (0) : __assert_fail ("AR->getStepRecurrence(*SE)->isOne() && \"only handles unit stride\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2378, __PRETTY_FUNCTION__));
  // For unit stride, IVCount = Start + ExitCount with 2's complement
  // overflow.

  // For integer IVs, truncate the IV before computing IVInit + BECount,
  // unless we know apriori that the limit must be a constant when evaluated
  // in the bitwidth of the IV.  We prefer (potentially) keeping a truncate
  // of the IV in the loop over a (potentially) expensive expansion of the
  // widened exit count add(zext(add)) expression.
  if (SE->getTypeSizeInBits(IVInit->getType())
      > SE->getTypeSizeInBits(ExitCount->getType())) {
    if (isa<SCEVConstant>(IVInit) && isa<SCEVConstant>(ExitCount))
      ExitCount = SE->getZeroExtendExpr(ExitCount, IVInit->getType());
    else
      IVInit = SE->getTruncateExpr(IVInit, ExitCount->getType());
  }

  const SCEV *IVLimit = SE->getAddExpr(IVInit, ExitCount);

  if (UsePostInc)
    IVLimit = SE->getAddExpr(IVLimit, SE->getOne(IVLimit->getType()));

  // Expand the code for the iteration count.
  assert(SE->isLoopInvariant(IVLimit, L) &&((SE->isLoopInvariant(IVLimit, L) && "Computed iteration count is not loop invariant!"
) ? static_cast<void> (0) : __assert_fail ("SE->isLoopInvariant(IVLimit, L) && \"Computed iteration count is not loop invariant!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2402, __PRETTY_FUNCTION__))
         "Computed iteration count is not loop invariant!")((SE->isLoopInvariant(IVLimit, L) && "Computed iteration count is not loop invariant!"
) ? static_cast<void> (0) : __assert_fail ("SE->isLoopInvariant(IVLimit, L) && \"Computed iteration count is not loop invariant!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2402, __PRETTY_FUNCTION__));
  // Ensure that we generate the same type as IndVar, or a smaller integer
  // type. In the presence of null pointer values, we have an integer type
  // SCEV expression (IVInit) for a pointer type IV value (IndVar).
  Type *LimitTy = ExitCount->getType()->isPointerTy() ?
    IndVar->getType() : ExitCount->getType();
  BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());
  return Rewriter.expandCodeFor(IVLimit, LimitTy, BI);
}
2411}

2413/// This method rewrites the exit condition of the loop to be a canonical !=
2414/// comparison against the incremented loop induction variable.  This pass is
2415/// able to rewrite the exit tests of any loop where the SCEV analysis can
2416/// determine a loop-invariant trip count of the loop, which is actually a much
2417/// broader range than just linear tests.
2418bool IndVarSimplify::
2419linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,
                        const SCEV *ExitCount,
                        PHINode *IndVar, SCEVExpander &Rewriter) {
assert(L->getLoopLatch() && "Loop no longer in simplified form?")((L->getLoopLatch() && "Loop no longer in simplified form?"
) ? static_cast<void> (0) : __assert_fail ("L->getLoopLatch() && \"Loop no longer in simplified form?\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2422, __PRETTY_FUNCTION__));
assert(isLoopCounter(IndVar, L, SE))((isLoopCounter(IndVar, L, SE)) ? static_cast<void> (0)
 : __assert_fail ("isLoopCounter(IndVar, L, SE)", "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2423, __PRETTY_FUNCTION__));
Instruction * const IncVar =
  cast<Instruction>(IndVar->getIncomingValueForBlock(L->getLoopLatch()));

// Initialize CmpIndVar to the preincremented IV.
Value *CmpIndVar = IndVar;
bool UsePostInc = false;

// If the exiting block is the same as the backedge block, we prefer to
// compare against the post-incremented value, otherwise we must compare
// against the preincremented value.
if (ExitingBB == L->getLoopLatch()) {
  // For pointer IVs, we chose to not strip inbounds which requires us not
  // to add a potentially UB introducing use.  We need to either a) show
  // the loop test we're modifying is already in post-inc form, or b) show
  // that adding a use must not introduce UB.
  bool SafeToPostInc =
      IndVar->getType()->isIntegerTy() ||
      isLoopExitTestBasedOn(IncVar, ExitingBB) ||
      mustExecuteUBIfPoisonOnPathTo(IncVar, ExitingBB->getTerminator(), DT);
  if (SafeToPostInc) {
    UsePostInc = true;
    CmpIndVar = IncVar;
  }
}

// It may be necessary to drop nowrap flags on the incrementing instruction
// if either LFTR moves from a pre-inc check to a post-inc check (in which
// case the increment might have previously been poison on the last iteration
// only) or if LFTR switches to a different IV that was previously dynamically
// dead (and as such may be arbitrarily poison). We remove any nowrap flags
// that SCEV didn't infer for the post-inc addrec (even if we use a pre-inc
// check), because the pre-inc addrec flags may be adopted from the original
// instruction, while SCEV has to explicitly prove the post-inc nowrap flags.
// TODO: This handling is inaccurate for one case: If we switch to a
// dynamically dead IV that wraps on the first loop iteration only, which is
// not covered by the post-inc addrec. (If the new IV was not dynamically
// dead, it could not be poison on the first iteration in the first place.)
if (auto *BO = dyn_cast<BinaryOperator>(IncVar)) {
  const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IncVar));
  if (BO->hasNoUnsignedWrap())
    BO->setHasNoUnsignedWrap(AR->hasNoUnsignedWrap());
  if (BO->hasNoSignedWrap())
    BO->setHasNoSignedWrap(AR->hasNoSignedWrap());
}

Value *ExitCnt = genLoopLimit(
    IndVar, ExitingBB, ExitCount, UsePostInc, L, Rewriter, SE);
assert(ExitCnt->getType()->isPointerTy() ==((ExitCnt->getType()->isPointerTy() == IndVar->getType
()->isPointerTy() && "genLoopLimit missed a cast")
 ? static_cast<void> (0) : __assert_fail ("ExitCnt->getType()->isPointerTy() == IndVar->getType()->isPointerTy() && \"genLoopLimit missed a cast\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2473, __PRETTY_FUNCTION__))
           IndVar->getType()->isPointerTy() &&((ExitCnt->getType()->isPointerTy() == IndVar->getType
()->isPointerTy() && "genLoopLimit missed a cast")
 ? static_cast<void> (0) : __assert_fail ("ExitCnt->getType()->isPointerTy() == IndVar->getType()->isPointerTy() && \"genLoopLimit missed a cast\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2473, __PRETTY_FUNCTION__))
       "genLoopLimit missed a cast")((ExitCnt->getType()->isPointerTy() == IndVar->getType
()->isPointerTy() && "genLoopLimit missed a cast")
 ? static_cast<void> (0) : __assert_fail ("ExitCnt->getType()->isPointerTy() == IndVar->getType()->isPointerTy() && \"genLoopLimit missed a cast\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2473, __PRETTY_FUNCTION__));

// Insert a new icmp_ne or icmp_eq instruction before the branch.
BranchInst *BI = cast<BranchInst>(ExitingBB->getTerminator());
ICmpInst::Predicate P;
if (L->contains(BI->getSuccessor(0)))
  P = ICmpInst::ICMP_NE;
else
  P = ICmpInst::ICMP_EQ;

IRBuilder<> Builder(BI);

// The new loop exit condition should reuse the debug location of the
// original loop exit condition.
if (auto *Cond = dyn_cast<Instruction>(BI->getCondition()))
  Builder.SetCurrentDebugLocation(Cond->getDebugLoc());

// For integer IVs, if we evaluated the limit in the narrower bitwidth to
// avoid the expensive expansion of the limit expression in the wider type,
// emit a truncate to narrow the IV to the ExitCount type.  This is safe
// since we know (from the exit count bitwidth), that we can't self-wrap in
// the narrower type.
unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->getType());
unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->getType());
if (CmpIndVarSize > ExitCntSize) {
  assert(!CmpIndVar->getType()->isPointerTy() &&((!CmpIndVar->getType()->isPointerTy() && !ExitCnt
->getType()->isPointerTy()) ? static_cast<void> (
0) : __assert_fail ("!CmpIndVar->getType()->isPointerTy() && !ExitCnt->getType()->isPointerTy()"
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2499, __PRETTY_FUNCTION__))
         !ExitCnt->getType()->isPointerTy())((!CmpIndVar->getType()->isPointerTy() && !ExitCnt
->getType()->isPointerTy()) ? static_cast<void> (
0) : __assert_fail ("!CmpIndVar->getType()->isPointerTy() && !ExitCnt->getType()->isPointerTy()"
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2499, __PRETTY_FUNCTION__));

  // Before resorting to actually inserting the truncate, use the same
  // reasoning as from SimplifyIndvar::eliminateTrunc to see if we can extend
  // the other side of the comparison instead.  We still evaluate the limit
  // in the narrower bitwidth, we just prefer a zext/sext outside the loop to
  // a truncate within in.  
  bool Extended = false;
  const SCEV *IV = SE->getSCEV(CmpIndVar);
  const SCEV *TruncatedIV = SE->getTruncateExpr(SE->getSCEV(CmpIndVar),
                                                ExitCnt->getType());
  const SCEV *ZExtTrunc =
    SE->getZeroExtendExpr(TruncatedIV, CmpIndVar->getType());
  
  if (ZExtTrunc == IV) {
    Extended = true;
    ExitCnt = Builder.CreateZExt(ExitCnt, IndVar->getType(),
                                 "wide.trip.count");
  } else {
    const SCEV *SExtTrunc =
      SE->getSignExtendExpr(TruncatedIV, CmpIndVar->getType());
    if (SExtTrunc == IV) {
      Extended = true;
      ExitCnt = Builder.CreateSExt(ExitCnt, IndVar->getType(),
                                   "wide.trip.count");
    }
  }

  if (Extended) {
    bool Discard;
    L->makeLoopInvariant(ExitCnt, Discard);
  } else 
    CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(),
                                    "lftr.wideiv");
}
LLVM_DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
 << "      LHS:" << *CmpIndVar << '\n' <<
 "       op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "=="
) << "\n" << "      RHS:\t" << *ExitCnt <<
 "\n" << "ExitCount:\t" << *ExitCount << "\n"
 << "  was: " << *BI->getCondition() << "\n"
; } } while (false)
                  << "      LHS:" << *CmpIndVar << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
 << "      LHS:" << *CmpIndVar << '\n' <<
 "       op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "=="
) << "\n" << "      RHS:\t" << *ExitCnt <<
 "\n" << "ExitCount:\t" << *ExitCount << "\n"
 << "  was: " << *BI->getCondition() << "\n"
; } } while (false)
                  << "       op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "==")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
 << "      LHS:" << *CmpIndVar << '\n' <<
 "       op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "=="
) << "\n" << "      RHS:\t" << *ExitCnt <<
 "\n" << "ExitCount:\t" << *ExitCount << "\n"
 << "  was: " << *BI->getCondition() << "\n"
; } } while (false)
                  << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
 << "      LHS:" << *CmpIndVar << '\n' <<
 "       op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "=="
) << "\n" << "      RHS:\t" << *ExitCnt <<
 "\n" << "ExitCount:\t" << *ExitCount << "\n"
 << "  was: " << *BI->getCondition() << "\n"
; } } while (false)
                  << "      RHS:\t" << *ExitCnt << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
 << "      LHS:" << *CmpIndVar << '\n' <<
 "       op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "=="
) << "\n" << "      RHS:\t" << *ExitCnt <<
 "\n" << "ExitCount:\t" << *ExitCount << "\n"
 << "  was: " << *BI->getCondition() << "\n"
; } } while (false)
                  << "ExitCount:\t" << *ExitCount << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
 << "      LHS:" << *CmpIndVar << '\n' <<
 "       op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "=="
) << "\n" << "      RHS:\t" << *ExitCnt <<
 "\n" << "ExitCount:\t" << *ExitCount << "\n"
 << "  was: " << *BI->getCondition() << "\n"
; } } while (false)
                  << "  was: " << *BI->getCondition() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("indvars")) { dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
 << "      LHS:" << *CmpIndVar << '\n' <<
 "       op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "=="
) << "\n" << "      RHS:\t" << *ExitCnt <<
 "\n" << "ExitCount:\t" << *ExitCount << "\n"
 << "  was: " << *BI->getCondition() << "\n"
; } } while (false);

Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond");
Value *OrigCond = BI->getCondition();
// It's tempting to use replaceAllUsesWith here to fully replace the old
// comparison, but that's not immediately safe, since users of the old
// comparison may not be dominated by the new comparison. Instead, just
// update the branch to use the new comparison; in the common case this
// will make old comparison dead.
BI->setCondition(Cond);
DeadInsts.push_back(OrigCond);

++NumLFTR;
return true;
2554}

2556//===----------------------------------------------------------------------===//
2557//  sinkUnusedInvariants. A late subpass to cleanup loop preheaders.
2558//===----------------------------------------------------------------------===//

2560/// If there's a single exit block, sink any loop-invariant values that
2561/// were defined in the preheader but not used inside the loop into the
2562/// exit block to reduce register pressure in the loop.
2563bool IndVarSimplify::sinkUnusedInvariants(Loop *L) {
BasicBlock *ExitBlock = L->getExitBlock();
if (!ExitBlock) return false;

BasicBlock *Preheader = L->getLoopPreheader();
if (!Preheader) return false;

bool MadeAnyChanges = false;
BasicBlock::iterator InsertPt = ExitBlock->getFirstInsertionPt();
BasicBlock::iterator I(Preheader->getTerminator());
while (I != Preheader->begin()) {
  --I;
  // New instructions were inserted at the end of the preheader.
  if (isa<PHINode>(I))
    break;

  // Don't move instructions which might have side effects, since the side
  // effects need to complete before instructions inside the loop.  Also don't
  // move instructions which might read memory, since the loop may modify
  // memory. Note that it's okay if the instruction might have undefined
  // behavior: LoopSimplify guarantees that the preheader dominates the exit
  // block.
  if (I->mayHaveSideEffects() || I->mayReadFromMemory())
    continue;

  // Skip debug info intrinsics.
  if (isa<DbgInfoIntrinsic>(I))
    continue;

  // Skip eh pad instructions.
  if (I->isEHPad())
    continue;

  // Don't sink alloca: we never want to sink static alloca's out of the
  // entry block, and correctly sinking dynamic alloca's requires
  // checks for stacksave/stackrestore intrinsics.
  // FIXME: Refactor this check somehow?
  if (isa<AllocaInst>(I))
    continue;

  // Determine if there is a use in or before the loop (direct or
  // otherwise).
  bool UsedInLoop = false;
  for (Use &U : I->uses()) {
    Instruction *User = cast<Instruction>(U.getUser());
    BasicBlock *UseBB = User->getParent();
    if (PHINode *P = dyn_cast<PHINode>(User)) {
      unsigned i =
        PHINode::getIncomingValueNumForOperand(U.getOperandNo());
      UseBB = P->getIncomingBlock(i);
    }
    if (UseBB == Preheader || L->contains(UseBB)) {
      UsedInLoop = true;
      break;
    }
  }

  // If there is, the def must remain in the preheader.
  if (UsedInLoop)
    continue;

  // Otherwise, sink it to the exit block.
  Instruction *ToMove = &*I;
  bool Done = false;

  if (I != Preheader->begin()) {
    // Skip debug info intrinsics.
    do {
      --I;
    } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin());

    if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin())
      Done = true;
  } else {
    Done = true;
  }

  MadeAnyChanges = true;
  ToMove->moveBefore(*ExitBlock, InsertPt);
  if (Done) break;
  InsertPt = ToMove->getIterator();
}

return MadeAnyChanges;
2647}

2649bool IndVarSimplify::optimizeLoopExits(Loop *L, SCEVExpander &Rewriter) {
SmallVector<BasicBlock*, 16> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks);

// Form an expression for the maximum exit count possible for this loop. We
// merge the max and exact information to approximate a version of
// getConstantMaxBackedgeTakenCount which isn't restricted to just constants.
// TODO: factor this out as a version of getConstantMaxBackedgeTakenCount which
// isn't guaranteed to return a constant.
SmallVector<const SCEV*, 4> ExitCounts;
const SCEV *MaxConstEC = SE->getConstantMaxBackedgeTakenCount(L);
if (!isa<SCEVCouldNotCompute>(MaxConstEC))
  ExitCounts.push_back(MaxConstEC);
for (BasicBlock *ExitingBB : ExitingBlocks) {
  const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
  if (!isa<SCEVCouldNotCompute>(ExitCount)) {
    assert(DT->dominates(ExitingBB, L->getLoopLatch()) &&((DT->dominates(ExitingBB, L->getLoopLatch()) &&
 "We should only have known counts for exiting blocks that " "dominate latch!"
) ? static_cast<void> (0) : __assert_fail ("DT->dominates(ExitingBB, L->getLoopLatch()) && \"We should only have known counts for exiting blocks that \" \"dominate latch!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2667, __PRETTY_FUNCTION__))
           "We should only have known counts for exiting blocks that "((DT->dominates(ExitingBB, L->getLoopLatch()) &&
 "We should only have known counts for exiting blocks that " "dominate latch!"
) ? static_cast<void> (0) : __assert_fail ("DT->dominates(ExitingBB, L->getLoopLatch()) && \"We should only have known counts for exiting blocks that \" \"dominate latch!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2667, __PRETTY_FUNCTION__))
           "dominate latch!")((DT->dominates(ExitingBB, L->getLoopLatch()) &&
 "We should only have known counts for exiting blocks that " "dominate latch!"
) ? static_cast<void> (0) : __assert_fail ("DT->dominates(ExitingBB, L->getLoopLatch()) && \"We should only have known counts for exiting blocks that \" \"dominate latch!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2667, __PRETTY_FUNCTION__));
    ExitCounts.push_back(ExitCount);
  }
}
if (ExitCounts.empty())
  return false;
const SCEV *MaxExitCount = SE->getUMinFromMismatchedTypes(ExitCounts);

bool Changed = false;
for (BasicBlock *ExitingBB : ExitingBlocks) {
  // If our exitting block exits multiple loops, we can only rewrite the
  // innermost one.  Otherwise, we're changing how many times the innermost
  // loop runs before it exits. 
  if (LI->getLoopFor(ExitingBB) != L)
    continue;

  // Can't rewrite non-branch yet.
  BranchInst *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
  if (!BI)
    continue;

  // If already constant, nothing to do.
  if (isa<Constant>(BI->getCondition()))
    continue;
  
  const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
  if (isa<SCEVCouldNotCompute>(ExitCount))
    continue;

  // If we know we'd exit on the first iteration, rewrite the exit to
  // reflect this.  This does not imply the loop must exit through this
  // exit; there may be an earlier one taken on the first iteration.
  // TODO: Given we know the backedge can't be taken, we should go ahead
  // and break it.  Or at least, kill all the header phis and simplify.
  if (ExitCount->isZero()) {
    bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
    auto *OldCond = BI->getCondition();
    auto *NewCond = ExitIfTrue ? ConstantInt::getTrue(OldCond->getType()) :
      ConstantInt::getFalse(OldCond->getType());
    BI->setCondition(NewCond);
    if (OldCond->use_empty())
      DeadInsts.push_back(OldCond);
    Changed = true;
    continue;
  }

  // If we end up with a pointer exit count, bail.  Note that we can end up
  // with a pointer exit count for one exiting block, and not for another in
  // the same loop.
  if (!ExitCount->getType()->isIntegerTy() ||
      !MaxExitCount->getType()->isIntegerTy())
    continue;
  
  Type *WiderType =
    SE->getWiderType(MaxExitCount->getType(), ExitCount->getType());
  ExitCount = SE->getNoopOrZeroExtend(ExitCount, WiderType);
  MaxExitCount = SE->getNoopOrZeroExtend(MaxExitCount, WiderType);
  assert(MaxExitCount->getType() == ExitCount->getType())((MaxExitCount->getType() == ExitCount->getType()) ? static_cast
<void> (0) : __assert_fail ("MaxExitCount->getType() == ExitCount->getType()"
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2724, __PRETTY_FUNCTION__));
  
  // Can we prove that some other exit must be taken strictly before this
  // one?
  if (SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_ULT,
                                   MaxExitCount, ExitCount)) {
    bool ExitIfTrue = !L->contains(*succ_begin(ExitingBB));
    auto *OldCond = BI->getCondition();
    auto *NewCond = ExitIfTrue ? ConstantInt::getFalse(OldCond->getType()) :
      ConstantInt::getTrue(OldCond->getType());
    BI->setCondition(NewCond);
    if (OldCond->use_empty())
      DeadInsts.push_back(OldCond);
    Changed = true;
    continue;
  }

  // TODO: If we can prove that the exiting iteration is equal to the exit
  // count for this exit and that no previous exit oppurtunities exist within
  // the loop, then we can discharge all other exits.  (May fall out of
  // previous TODO.)
}

// Finally, see if we can rewrite our exit conditions into a loop invariant
// form.  If we have a read-only loop, and we can tell that we must exit down
// a path which does not need any of the values computed within the loop, we
// can rewrite the loop to exit on the first iteration.  Note that this
// doesn't either a) tell us the loop exits on the first iteration (unless
// *all* exits are predicateable) or b) tell us *which* exit might be taken.
// This transformation looks a lot like a restricted form of dead loop
// elimination, but restricted to read-only loops and without neccesssarily
// needing to kill the loop entirely. 
if (!LoopPredication)
  return Changed;

if (!SE->hasLoopInvariantBackedgeTakenCount(L))
  return Changed;

// Note: ExactBTC is the exact backedge taken count *iff* the loop exits
// through *explicit* control flow.  We have to eliminate the possibility of
// implicit exits (see below) before we know it's truly exact.
const SCEV *ExactBTC = SE->getBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(ExactBTC) ||
    !SE->isLoopInvariant(ExactBTC, L) ||
    !isSafeToExpand(ExactBTC, *SE))
  return Changed;

auto Filter = [&](BasicBlock *ExitingBB) {
  // If our exiting block exits multiple loops, we can only rewrite the
  // innermost one.  Otherwise, we're changing how many times the innermost
  // loop runs before it exits. 
  if (LI->getLoopFor(ExitingBB) != L)
    return true;

  // Can't rewrite non-branch yet.
  BranchInst *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
  if (!BI)
    return true;

  // If already constant, nothing to do.
  if (isa<Constant>(BI->getCondition()))
    return true;

  // If the exit block has phis, we need to be able to compute the values
  // within the loop which contains them.  This assumes trivially lcssa phis
  // have already been removed; TODO: generalize
  BasicBlock *ExitBlock =
  BI->getSuccessor(L->contains(BI->getSuccessor(0)) ? 1 : 0);
  if (!ExitBlock->phis().empty())
    return true;

  const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
  assert(!isa<SCEVCouldNotCompute>(ExactBTC) && "implied by having exact trip count")((!isa<SCEVCouldNotCompute>(ExactBTC) && "implied by having exact trip count"
) ? static_cast<void> (0) : __assert_fail ("!isa<SCEVCouldNotCompute>(ExactBTC) && \"implied by having exact trip count\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2796, __PRETTY_FUNCTION__));
  if (!SE->isLoopInvariant(ExitCount, L) ||
      !isSafeToExpand(ExitCount, *SE))
    return true;

  return false;
};
auto Erased = std::remove_if(ExitingBlocks.begin(), ExitingBlocks.end(),
                             Filter);
ExitingBlocks.erase(Erased, ExitingBlocks.end());

if (ExitingBlocks.empty())
  return Changed;

// We rely on not being able to reach an exiting block on a later iteration
// than it's statically compute exit count.  The implementaton of
// getExitCount currently has this invariant, but assert it here so that
// breakage is obvious if this ever changes..
assert(llvm::all_of(ExitingBlocks, [&](BasicBlock *ExitingBB) {((llvm::all_of(ExitingBlocks, [&](BasicBlock *ExitingBB) {
 return DT->dominates(ExitingBB, L->getLoopLatch()); })
) ? static_cast<void> (0) : __assert_fail ("llvm::all_of(ExitingBlocks, [&](BasicBlock *ExitingBB) { return DT->dominates(ExitingBB, L->getLoopLatch()); })"
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2816, __PRETTY_FUNCTION__))
      return DT->dominates(ExitingBB, L->getLoopLatch());((llvm::all_of(ExitingBlocks, [&](BasicBlock *ExitingBB) {
 return DT->dominates(ExitingBB, L->getLoopLatch()); })
) ? static_cast<void> (0) : __assert_fail ("llvm::all_of(ExitingBlocks, [&](BasicBlock *ExitingBB) { return DT->dominates(ExitingBB, L->getLoopLatch()); })"
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2816, __PRETTY_FUNCTION__))
    }))((llvm::all_of(ExitingBlocks, [&](BasicBlock *ExitingBB) {
 return DT->dominates(ExitingBB, L->getLoopLatch()); })
) ? static_cast<void> (0) : __assert_fail ("llvm::all_of(ExitingBlocks, [&](BasicBlock *ExitingBB) { return DT->dominates(ExitingBB, L->getLoopLatch()); })"
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2816, __PRETTY_FUNCTION__));

// At this point, ExitingBlocks consists of only those blocks which are
// predicatable.  Given that, we know we have at least one exit we can
// predicate if the loop is doesn't have side effects and doesn't have any
// implicit exits (because then our exact BTC isn't actually exact).
// @Reviewers - As structured, this is O(I^2) for loop nests.  Any
// suggestions on how to improve this?  I can obviously bail out for outer
// loops, but that seems less than ideal.  MemorySSA can find memory writes,
// is that enough for *all* side effects?
for (BasicBlock *BB : L->blocks())
  for (auto &I : *BB)
    // TODO:isGuaranteedToTransfer
    if (I.mayHaveSideEffects() || I.mayThrow())
      return Changed;

// Finally, do the actual predication for all predicatable blocks.  A couple
// of notes here:
// 1) We don't bother to constant fold dominated exits with identical exit
//    counts; that's simply a form of CSE/equality propagation and we leave
//    it for dedicated passes.
// 2) We insert the comparison at the branch.  Hoisting introduces additional
//    legality constraints and we leave that to dedicated logic.  We want to
//    predicate even if we can't insert a loop invariant expression as
//    peeling or unrolling will likely reduce the cost of the otherwise loop
//    varying check.
Rewriter.setInsertPoint(L->getLoopPreheader()->getTerminator());
IRBuilder<> B(L->getLoopPreheader()->getTerminator());
Value *ExactBTCV = nullptr; //lazy generated if needed
for (BasicBlock *ExitingBB : ExitingBlocks) {
  const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);

  auto *BI = cast<BranchInst>(ExitingBB->getTerminator());
  Value *NewCond;
  if (ExitCount == ExactBTC) {
    NewCond = L->contains(BI->getSuccessor(0)) ?
      B.getFalse() : B.getTrue();
  } else {
    Value *ECV = Rewriter.expandCodeFor(ExitCount);
    if (!ExactBTCV)
      ExactBTCV = Rewriter.expandCodeFor(ExactBTC);
    Value *RHS = ExactBTCV;
    if (ECV->getType() != RHS->getType()) {
      Type *WiderTy = SE->getWiderType(ECV->getType(), RHS->getType());
      ECV = B.CreateZExt(ECV, WiderTy);
      RHS = B.CreateZExt(RHS, WiderTy);
    }
    auto Pred = L->contains(BI->getSuccessor(0)) ?
      ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;
    NewCond = B.CreateICmp(Pred, ECV, RHS);
  }
  Value *OldCond = BI->getCondition();
  BI->setCondition(NewCond);
  if (OldCond->use_empty())
    DeadInsts.push_back(OldCond);
  Changed = true;
}

return Changed;
2875}

2877//===----------------------------------------------------------------------===//
2878//  IndVarSimplify driver. Manage several subpasses of IV simplification.
2879//===----------------------------------------------------------------------===//

2881bool IndVarSimplify::run(Loop *L) {
// We need (and expect!) the incoming loop to be in LCSSA.
assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&((L->isRecursivelyLCSSAForm(*DT, *LI) && "LCSSA required to run indvars!"
) ? static_cast<void> (0) : __assert_fail ("L->isRecursivelyLCSSAForm(*DT, *LI) && \"LCSSA required to run indvars!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2884, __PRETTY_FUNCTION__))
2
←
Assuming the condition is true→
3
←
'?' condition is true→
       "LCSSA required to run indvars!")((L->isRecursivelyLCSSAForm(*DT, *LI) && "LCSSA required to run indvars!"
) ? static_cast<void> (0) : __assert_fail ("L->isRecursivelyLCSSAForm(*DT, *LI) && \"LCSSA required to run indvars!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 2884, __PRETTY_FUNCTION__));
bool Changed = false;

// If LoopSimplify form is not available, stay out of trouble. Some notes:
//  - LSR currently only supports LoopSimplify-form loops. Indvars'
//    canonicalization can be a pessimization without LSR to "clean up"
//    afterwards.
//  - We depend on having a preheader; in particular,
//    Loop::getCanonicalInductionVariable only supports loops with preheaders,
//    and we're in trouble if we can't find the induction variable even when
//    we've manually inserted one.
//  - LFTR relies on having a single backedge.
if (!L->isLoopSimplifyForm())
4
←
Assuming the condition is false→
5
←
Taking false branch→
  return false;

// If there are any floating-point recurrences, attempt to
// transform them to use integer recurrences.
Changed |= rewriteNonIntegerIVs(L);

2903#ifndef NDEBUG
// Used below for a consistency check only
const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
2906#endif

// Create a rewriter object which we'll use to transform the code with.
SCEVExpander Rewriter(*SE, DL, "indvars");
2910#ifndef NDEBUG
Rewriter.setDebugType(DEBUG_TYPE"indvars");
2912#endif

// Eliminate redundant IV users.
//
// Simplification works best when run before other consumers of SCEV. We
// attempt to avoid evaluating SCEVs for sign/zero extend operations until
// other expressions involving loop IVs have been evaluated. This helps SCEV
// set no-wrap flags before normalizing sign/zero extension.
Rewriter.disableCanonicalMode();
Changed |= simplifyAndExtend(L, Rewriter, LI);

// Check to see if we can compute the final value of any expressions
// that are recurrent in the loop, and substitute the exit values from the
// loop into any instructions outside of the loop that use the final values
// of the current expressions.
if (ReplaceExitValue != NeverRepl)
6
←
Assuming the condition is false→
7
←
Taking false branch→
  Changed |= rewriteLoopExitValues(L, Rewriter);

// Eliminate redundant IV cycles.
NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);

Changed |= optimizeLoopExits(L, Rewriter);

// If we have a trip count expression, rewrite the loop's exit condition
// using it.  
if (!DisableLFTR) {
8
←
Assuming the condition is true→
9
←
Taking true branch→
  SmallVector<BasicBlock*, 16> ExitingBlocks;
  L->getExitingBlocks(ExitingBlocks);
  for (BasicBlock *ExitingBB : ExitingBlocks) {
10
←
Assuming '__begin2' is not equal to '__end2'→
    // Can't rewrite non-branch yet.
    if (!isa<BranchInst>(ExitingBB->getTerminator()))
11
←
Assuming the object is a 'BranchInst'→
12
←
Taking false branch→
      continue;

    // If our exitting block exits multiple loops, we can only rewrite the
    // innermost one.  Otherwise, we're changing how many times the innermost
    // loop runs before it exits. 
    if (LI->getLoopFor(ExitingBB) != L)
13
←
Assuming the condition is false→
14
←
Taking false branch→
      continue;
    
    if (!needsLFTR(L, ExitingBB))
15
←
Taking false branch→
      continue;

    const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
    if (isa<SCEVCouldNotCompute>(ExitCount))
16
←
Assuming 'ExitCount' is not a 'SCEVCouldNotCompute'→
17
←
Taking false branch→
      continue;

    // This was handled above, but as we form SCEVs, we can sometimes refine
    // existing ones; this allows exit counts to be folded to zero which
    // weren't when optimizeLoopExits saw them.  Arguably, we should iterate
    // until stable to handle cases like this better.
    if (ExitCount->isZero())
18
←
Assuming the condition is false→
19
←
Taking false branch→
      continue;
    
    PHINode *IndVar = FindLoopCounter(L, ExitingBB, ExitCount, SE, DT);
20
←
Calling 'FindLoopCounter'→
    if (!IndVar)
      continue;
    
    // Avoid high cost expansions.  Note: This heuristic is questionable in
    // that our definition of "high cost" is not exactly principled.  
    if (Rewriter.isHighCostExpansion(ExitCount, L))
      continue;

    // Check preconditions for proper SCEVExpander operation. SCEV does not
    // express SCEVExpander's dependencies, such as LoopSimplify. Instead
    // any pass that uses the SCEVExpander must do it. This does not work
    // well for loop passes because SCEVExpander makes assumptions about
    // all loops, while LoopPassManager only forces the current loop to be
    // simplified. 
    //
    // FIXME: SCEV expansion has no way to bail out, so the caller must
    // explicitly check any assumptions made by SCEV. Brittle.
    const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(ExitCount);
    if (!AR || AR->getLoop()->getLoopPreheader())
      Changed |= linearFunctionTestReplace(L, ExitingBB,
                                           ExitCount, IndVar,
                                           Rewriter);
  }
}
// Clear the rewriter cache, because values that are in the rewriter's cache
// can be deleted in the loop below, causing the AssertingVH in the cache to
// trigger.
Rewriter.clear();

// Now that we're done iterating through lists, clean up any instructions
// which are now dead.
while (!DeadInsts.empty())
  if (Instruction *Inst =
          dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()))
    Changed |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI);

// The Rewriter may not be used from this point on.

// Loop-invariant instructions in the preheader that aren't used in the
// loop may be sunk below the loop to reduce register pressure.
Changed |= sinkUnusedInvariants(L);

// rewriteFirstIterationLoopExitValues does not rely on the computation of
// trip count and therefore can further simplify exit values in addition to
// rewriteLoopExitValues.
Changed |= rewriteFirstIterationLoopExitValues(L);

// Clean up dead instructions.
Changed |= DeleteDeadPHIs(L->getHeader(), TLI);

// Check a post-condition.
assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&((L->isRecursivelyLCSSAForm(*DT, *LI) && "Indvars did not preserve LCSSA!"
) ? static_cast<void> (0) : __assert_fail ("L->isRecursivelyLCSSAForm(*DT, *LI) && \"Indvars did not preserve LCSSA!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 3018, __PRETTY_FUNCTION__))
       "Indvars did not preserve LCSSA!")((L->isRecursivelyLCSSAForm(*DT, *LI) && "Indvars did not preserve LCSSA!"
) ? static_cast<void> (0) : __assert_fail ("L->isRecursivelyLCSSAForm(*DT, *LI) && \"Indvars did not preserve LCSSA!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 3018, __PRETTY_FUNCTION__));

// Verify that LFTR, and any other change have not interfered with SCEV's
// ability to compute trip count.
3022#ifndef NDEBUG
if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
  SE->forgetLoop(L);
  const SCEV *NewBECount = SE->getBackedgeTakenCount(L);
  if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) <
      SE->getTypeSizeInBits(NewBECount->getType()))
    NewBECount = SE->getTruncateOrNoop(NewBECount,
                                       BackedgeTakenCount->getType());
  else
    BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount,
                                               NewBECount->getType());
  assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV")((BackedgeTakenCount == NewBECount && "indvars must preserve SCEV"
) ? static_cast<void> (0) : __assert_fail ("BackedgeTakenCount == NewBECount && \"indvars must preserve SCEV\""
, "/build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/Scalar/IndVarSimplify.cpp"
, 3033, __PRETTY_FUNCTION__));
}
3035#endif

return Changed;
3038}

3040PreservedAnalyses IndVarSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
                                        LoopStandardAnalysisResults &AR,
                                        LPMUpdater &) {
Function *F = L.getHeader()->getParent();
const DataLayout &DL = F->getParent()->getDataLayout();

IndVarSimplify IVS(&AR.LI, &AR.SE, &AR.DT, DL, &AR.TLI, &AR.TTI);
if (!IVS.run(&L))
1
Calling 'IndVarSimplify::run'→
  return PreservedAnalyses::all();

auto PA = getLoopPassPreservedAnalyses();
PA.preserveSet<CFGAnalyses>();
return PA;
3053}

3055namespace {

3057struct IndVarSimplifyLegacyPass : public LoopPass {
static char ID; // Pass identification, replacement for typeid

IndVarSimplifyLegacyPass() : LoopPass(ID) {
  initializeIndVarSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
}

bool runOnLoop(Loop *L, LPPassManager &LPM) override {
  if (skipLoop(L))
    return false;

  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
  auto *TLI = TLIP ? &TLIP->getTLI(*L->getHeader()->getParent()) : nullptr;
  auto *TTIP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
  auto *TTI = TTIP ? &TTIP->getTTI(*L->getHeader()->getParent()) : nullptr;
  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();

  IndVarSimplify IVS(LI, SE, DT, DL, TLI, TTI);
  return IVS.run(L);
}

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.setPreservesCFG();
  getLoopAnalysisUsage(AU);
}
3085};

3087} // end anonymous namespace

3089char IndVarSimplifyLegacyPass::ID = 0;

3091INITIALIZE_PASS_BEGIN(IndVarSimplifyLegacyPass, "indvars",static void *initializeIndVarSimplifyLegacyPassPassOnce(PassRegistry
 &Registry) {
                    "Induction Variable Simplification", false, false)static void *initializeIndVarSimplifyLegacyPassPassOnce(PassRegistry
 &Registry) {
3093INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
3094INITIALIZE_PASS_END(IndVarSimplifyLegacyPass, "indvars",PassInfo *PI = new PassInfo( "Induction Variable Simplification"
, "indvars", &IndVarSimplifyLegacyPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<IndVarSimplifyLegacyPass>), false, false
); Registry.registerPass(*PI, true); return PI; } static llvm
::once_flag InitializeIndVarSimplifyLegacyPassPassFlag; void llvm
::initializeIndVarSimplifyLegacyPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeIndVarSimplifyLegacyPassPassFlag
, initializeIndVarSimplifyLegacyPassPassOnce, std::ref(Registry
)); }
                  "Induction Variable Simplification", false, false)PassInfo *PI = new PassInfo( "Induction Variable Simplification"
, "indvars", &IndVarSimplifyLegacyPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<IndVarSimplifyLegacyPass>), false, false
); Registry.registerPass(*PI, true); return PI; } static llvm
::once_flag InitializeIndVarSimplifyLegacyPassPassFlag; void llvm
::initializeIndVarSimplifyLegacyPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeIndVarSimplifyLegacyPassPassFlag
, initializeIndVarSimplifyLegacyPassPassOnce, std::ref(Registry
)); }

3097Pass *llvm::createIndVarSimplifyPass() {
return new IndVarSimplifyLegacyPass();
3099}

←

/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Analysis/ScalarEvolutionExpressions.h

→

1//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the classes used to represent and build scalar expressions.
10//
11//===----------------------------------------------------------------------===//

13#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
14#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/FoldingSet.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/iterator_range.h"
21#include "llvm/Analysis/ScalarEvolution.h"
22#include "llvm/IR/Constants.h"
23#include "llvm/IR/Value.h"
24#include "llvm/IR/ValueHandle.h"
25#include "llvm/Support/Casting.h"
26#include "llvm/Support/ErrorHandling.h"
27#include <cassert>
28#include <cstddef>

30namespace llvm {

32class APInt;
33class Constant;
34class ConstantRange;
35class Loop;
36class Type;

enum SCEVTypes {
  // These should be ordered in terms of increasing complexity to make the
  // folders simpler.
  scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
  scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUMinExpr, scSMinExpr,
  scUnknown, scCouldNotCompute
};

/// This class represents a constant integer value.
class SCEVConstant : public SCEV {
  friend class ScalarEvolution;

  ConstantInt *V;

  SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
    SCEV(ID, scConstant, 1), V(v) {}

public:
  ConstantInt *getValue() const { return V; }
  const APInt &getAPInt() const { return getValue()->getValue(); }

  Type *getType() const { return V->getType(); }

  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scConstant;
  }
};

static unsigned short computeExpressionSize(ArrayRef<const SCEV *> Args) {
  APInt Size(16, 1);
  for (auto *Arg : Args)
    Size = Size.uadd_sat(APInt(16, Arg->getExpressionSize()));
  return (unsigned short)Size.getZExtValue();
}

/// This is the base class for unary cast operator classes.
class SCEVCastExpr : public SCEV {
protected:
  const SCEV *Op;
  Type *Ty;

  SCEVCastExpr(const FoldingSetNodeIDRef ID,
               unsigned SCEVTy, const SCEV *op, Type *ty);

public:
  const SCEV *getOperand() const { return Op; }
  Type *getType() const { return Ty; }

  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scTruncate ||
           S->getSCEVType() == scZeroExtend ||
           S->getSCEVType() == scSignExtend;
  }
};

/// This class represents a truncation of an integer value to a
/// smaller integer value.
class SCEVTruncateExpr : public SCEVCastExpr {
  friend class ScalarEvolution;

  SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
                   const SCEV *op, Type *ty);

public:
  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scTruncate;
  }
};

/// This class represents a zero extension of a small integer value
/// to a larger integer value.
class SCEVZeroExtendExpr : public SCEVCastExpr {
  friend class ScalarEvolution;

  SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
                     const SCEV *op, Type *ty);

public:
  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scZeroExtend;
  }
};

/// This class represents a sign extension of a small integer value
/// to a larger integer value.
class SCEVSignExtendExpr : public SCEVCastExpr {
  friend class ScalarEvolution;

  SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
                     const SCEV *op, Type *ty);

public:
  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scSignExtend;
  }
};

/// This node is a base class providing common functionality for
/// n'ary operators.
class SCEVNAryExpr : public SCEV {
protected:
  // Since SCEVs are immutable, ScalarEvolution allocates operand
  // arrays with its SCEVAllocator, so this class just needs a simple
  // pointer rather than a more elaborate vector-like data structure.
  // This also avoids the need for a non-trivial destructor.
  const SCEV *const *Operands;
  size_t NumOperands;

  SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T,
               const SCEV *const *O, size_t N)
      : SCEV(ID, T, computeExpressionSize(makeArrayRef(O, N))), Operands(O),
        NumOperands(N) {}

public:
  size_t getNumOperands() const { return NumOperands; }

  const SCEV *getOperand(unsigned i) const {
    assert(i < NumOperands && "Operand index out of range!")((i < NumOperands && "Operand index out of range!"
) ? static_cast<void> (0) : __assert_fail ("i < NumOperands && \"Operand index out of range!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Analysis/ScalarEvolutionExpressions.h"
, 160, __PRETTY_FUNCTION__));
    return Operands[i];
  }

  using op_iterator = const SCEV *const *;
  using op_range = iterator_range<op_iterator>;

  op_iterator op_begin() const { return Operands; }
  op_iterator op_end() const { return Operands + NumOperands; }
  op_range operands() const {
    return make_range(op_begin(), op_end());
  }

  Type *getType() const { return getOperand(0)->getType(); }

  NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const {
    return (NoWrapFlags)(SubclassData & Mask);
  }

  bool hasNoUnsignedWrap() const {
    return getNoWrapFlags(FlagNUW) != FlagAnyWrap;
  }

  bool hasNoSignedWrap() const {
    return getNoWrapFlags(FlagNSW) != FlagAnyWrap;
  }

  bool hasNoSelfWrap() const {
    return getNoWrapFlags(FlagNW) != FlagAnyWrap;
  }

  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
           S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
           S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr ||
           S->getSCEVType() == scAddRecExpr;
  }
};

/// This node is the base class for n'ary commutative operators.
class SCEVCommutativeExpr : public SCEVNAryExpr {
protected:
  SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
                      enum SCEVTypes T, const SCEV *const *O, size_t N)
    : SCEVNAryExpr(ID, T, O, N) {}

public:
  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
           S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
           S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr;
  }

  /// Set flags for a non-recurrence without clearing previously set flags.
  void setNoWrapFlags(NoWrapFlags Flags) {
    SubclassData |= Flags;
  }
};

/// This node represents an addition of some number of SCEVs.
class SCEVAddExpr : public SCEVCommutativeExpr {
  friend class ScalarEvolution;

  SCEVAddExpr(const FoldingSetNodeIDRef ID,
              const SCEV *const *O, size_t N)
    : SCEVCommutativeExpr(ID, scAddExpr, O, N) {}

public:
  Type *getType() const {
    // Use the type of the last operand, which is likely to be a pointer
    // type, if there is one. This doesn't usually matter, but it can help
    // reduce casts when the expressions are expanded.
    return getOperand(getNumOperands() - 1)->getType();
  }

  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scAddExpr;
  }
};

/// This node represents multiplication of some number of SCEVs.
class SCEVMulExpr : public SCEVCommutativeExpr {
  friend class ScalarEvolution;

  SCEVMulExpr(const FoldingSetNodeIDRef ID,
              const SCEV *const *O, size_t N)
    : SCEVCommutativeExpr(ID, scMulExpr, O, N) {}

public:
  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scMulExpr;
  }
};

/// This class represents a binary unsigned division operation.
class SCEVUDivExpr : public SCEV {
  friend class ScalarEvolution;

  const SCEV *LHS;
  const SCEV *RHS;

  SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
      : SCEV(ID, scUDivExpr, computeExpressionSize({lhs, rhs})), LHS(lhs),
        RHS(rhs) {}

public:
  const SCEV *getLHS() const { return LHS; }
  const SCEV *getRHS() const { return RHS; }

  Type *getType() const {
    // In most cases the types of LHS and RHS will be the same, but in some
    // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
    // depend on the type for correctness, but handling types carefully can
    // avoid extra casts in the SCEVExpander. The LHS is more likely to be
    // a pointer type than the RHS, so use the RHS' type here.
    return getRHS()->getType();
  }

  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scUDivExpr;
  }
};

/// This node represents a polynomial recurrence on the trip count
/// of the specified loop.  This is the primary focus of the
/// ScalarEvolution framework; all the other SCEV subclasses are
/// mostly just supporting infrastructure to allow SCEVAddRecExpr
/// expressions to be created and analyzed.
///
/// All operands of an AddRec are required to be loop invariant.
///
class SCEVAddRecExpr : public SCEVNAryExpr {
  friend class ScalarEvolution;

  const Loop *L;

  SCEVAddRecExpr(const FoldingSetNodeIDRef ID,
                 const SCEV *const *O, size_t N, const Loop *l)
    : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}

public:
  const SCEV *getStart() const { return Operands[0]; }
  const Loop *getLoop() const { return L; }

  /// Constructs and returns the recurrence indicating how much this
  /// expression steps by.  If this is a polynomial of degree N, it
  /// returns a chrec of degree N-1.  We cannot determine whether
  /// the step recurrence has self-wraparound.
  const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
    if (isAffine()) return getOperand(1);
    return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
                                                         op_end()),
                            getLoop(), FlagAnyWrap);
  }

  /// Return true if this represents an expression A + B*x where A
  /// and B are loop invariant values.
  bool isAffine() const {
    // We know that the start value is invariant.  This expression is thus
    // affine iff the step is also invariant.
    return getNumOperands() == 2;
36
←
Assuming the condition is true→
37
←
Returning the value 1, which participates in a condition later→
  }

  /// Return true if this represents an expression A + B*x + C*x^2
  /// where A, B and C are loop invariant values.  This corresponds
  /// to an addrec of the form {L,+,M,+,N}
  bool isQuadratic() const {
    return getNumOperands() == 3;
  }

  /// Set flags for a recurrence without clearing any previously set flags.
  /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
  /// to make it easier to propagate flags.
  void setNoWrapFlags(NoWrapFlags Flags) {
    if (Flags & (FlagNUW | FlagNSW))
      Flags = ScalarEvolution::setFlags(Flags, FlagNW);
    SubclassData |= Flags;
  }

  /// Return the value of this chain of recurrences at the specified
  /// iteration number.
  const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;

  /// Return the number of iterations of this loop that produce
  /// values in the specified constant range.  Another way of
  /// looking at this is that it returns the first iteration number
  /// where the value is not in the condition, thus computing the
  /// exit count.  If the iteration count can't be computed, an
  /// instance of SCEVCouldNotCompute is returned.
  const SCEV *getNumIterationsInRange(const ConstantRange &Range,
                                      ScalarEvolution &SE) const;

  /// Return an expression representing the value of this expression
  /// one iteration of the loop ahead.
  const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const;

  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scAddRecExpr;
  }
};

/// This node is the base class min/max selections.
class SCEVMinMaxExpr : public SCEVCommutativeExpr {
  friend class ScalarEvolution;

  static bool isMinMaxType(enum SCEVTypes T) {
    return T == scSMaxExpr || T == scUMaxExpr || T == scSMinExpr ||
           T == scUMinExpr;
  }

protected:
  /// Note: Constructing subclasses via this constructor is allowed
  SCEVMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T,
                 const SCEV *const *O, size_t N)
      : SCEVCommutativeExpr(ID, T, O, N) {
    assert(isMinMaxType(T))((isMinMaxType(T)) ? static_cast<void> (0) : __assert_fail
 ("isMinMaxType(T)", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Analysis/ScalarEvolutionExpressions.h"
, 381, __PRETTY_FUNCTION__));
    // Min and max never overflow
    setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
  }

public:
  static bool classof(const SCEV *S) {
    return isMinMaxType(static_cast<SCEVTypes>(S->getSCEVType()));
  }

  static enum SCEVTypes negate(enum SCEVTypes T) {
    switch (T) {
    case scSMaxExpr:
      return scSMinExpr;
    case scSMinExpr:
      return scSMaxExpr;
    case scUMaxExpr:
      return scUMinExpr;
    case scUMinExpr:
      return scUMaxExpr;
    default:
      llvm_unreachable("Not a min or max SCEV type!")::llvm::llvm_unreachable_internal("Not a min or max SCEV type!"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Analysis/ScalarEvolutionExpressions.h"
, 402);
    }
  }
};

/// This class represents a signed maximum selection.
class SCEVSMaxExpr : public SCEVMinMaxExpr {
  friend class ScalarEvolution;

  SCEVSMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
      : SCEVMinMaxExpr(ID, scSMaxExpr, O, N) {}

public:
  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scSMaxExpr;
  }
};

/// This class represents an unsigned maximum selection.
class SCEVUMaxExpr : public SCEVMinMaxExpr {
  friend class ScalarEvolution;

  SCEVUMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
      : SCEVMinMaxExpr(ID, scUMaxExpr, O, N) {}

public:
  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scUMaxExpr;
  }
};

/// This class represents a signed minimum selection.
class SCEVSMinExpr : public SCEVMinMaxExpr {
  friend class ScalarEvolution;

  SCEVSMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
      : SCEVMinMaxExpr(ID, scSMinExpr, O, N) {}

public:
  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scSMinExpr;
  }
};

/// This class represents an unsigned minimum selection.
class SCEVUMinExpr : public SCEVMinMaxExpr {
  friend class ScalarEvolution;

  SCEVUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
      : SCEVMinMaxExpr(ID, scUMinExpr, O, N) {}

public:
  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scUMinExpr;
  }
};

/// This means that we are dealing with an entirely unknown SCEV
/// value, and only represent it as its LLVM Value.  This is the
/// "bottom" value for the analysis.
class SCEVUnknown final : public SCEV, private CallbackVH {
  friend class ScalarEvolution;

  /// The parent ScalarEvolution value. This is used to update the
  /// parent's maps when the value associated with a SCEVUnknown is
  /// deleted or RAUW'd.
  ScalarEvolution *SE;

  /// The next pointer in the linked list of all SCEVUnknown
  /// instances owned by a ScalarEvolution.
  SCEVUnknown *Next;

  SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
              ScalarEvolution *se, SCEVUnknown *next) :
    SCEV(ID, scUnknown, 1), CallbackVH(V), SE(se), Next(next) {}

  // Implement CallbackVH.
  void deleted() override;
  void allUsesReplacedWith(Value *New) override;

public:
  Value *getValue() const { return getValPtr(); }

  /// @{
  /// Test whether this is a special constant representing a type
  /// size, alignment, or field offset in a target-independent
  /// manner, and hasn't happened to have been folded with other
  /// operations into something unrecognizable. This is mainly only
  /// useful for pretty-printing and other situations where it isn't
  /// absolutely required for these to succeed.
  bool isSizeOf(Type *&AllocTy) const;
  bool isAlignOf(Type *&AllocTy) const;
  bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
  /// @}

  Type *getType() const { return getValPtr()->getType(); }

  /// Methods for support type inquiry through isa, cast, and dyn_cast:
  static bool classof(const SCEV *S) {
    return S->getSCEVType() == scUnknown;
  }
};

/// This class defines a simple visitor class that may be used for
/// various SCEV analysis purposes.
template<typename SC, typename RetVal=void>
struct SCEVVisitor {
  RetVal visit(const SCEV *S) {
    switch (S->getSCEVType()) {
    case scConstant:
      return ((SC*)this)->visitConstant((const SCEVConstant*)S);
    case scTruncate:
      return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
    case scZeroExtend:
      return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
    case scSignExtend:
      return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
    case scAddExpr:
      return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
    case scMulExpr:
      return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
    case scUDivExpr:
      return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
    case scAddRecExpr:
      return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
    case scSMaxExpr:
      return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
    case scUMaxExpr:
      return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
    case scSMinExpr:
      return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
    case scUMinExpr:
      return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
    case scUnknown:
      return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
    case scCouldNotCompute:
      return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
    default:
      llvm_unreachable("Unknown SCEV type!")::llvm::llvm_unreachable_internal("Unknown SCEV type!", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Analysis/ScalarEvolutionExpressions.h"
, 544);
    }
  }

  RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
    llvm_unreachable("Invalid use of SCEVCouldNotCompute!")::llvm::llvm_unreachable_internal("Invalid use of SCEVCouldNotCompute!"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Analysis/ScalarEvolutionExpressions.h"
, 549);
  }
};

/// Visit all nodes in the expression tree using worklist traversal.
///
/// Visitor implements:
///   // return true to follow this node.
///   bool follow(const SCEV *S);
///   // return true to terminate the search.
///   bool isDone();
template<typename SV>
class SCEVTraversal {
  SV &Visitor;
  SmallVector<const SCEV *, 8> Worklist;
  SmallPtrSet<const SCEV *, 8> Visited;

  void push(const SCEV *S) {
    if (Visited.insert(S).second && Visitor.follow(S))
      Worklist.push_back(S);
  }

public:
  SCEVTraversal(SV& V): Visitor(V) {}

  void visitAll(const SCEV *Root) {
    push(Root);
    while (!Worklist.empty() && !Visitor.isDone()) {
      const SCEV *S = Worklist.pop_back_val();

      switch (S->getSCEVType()) {
      case scConstant:
      case scUnknown:
        break;
      case scTruncate:
      case scZeroExtend:
      case scSignExtend:
        push(cast<SCEVCastExpr>(S)->getOperand());
        break;
      case scAddExpr:
      case scMulExpr:
      case scSMaxExpr:
      case scUMaxExpr:
      case scSMinExpr:
      case scUMinExpr:
      case scAddRecExpr:
        for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
          push(Op);
        break;
      case scUDivExpr: {
        const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
        push(UDiv->getLHS());
        push(UDiv->getRHS());
        break;
      }
      case scCouldNotCompute:
        llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!")::llvm::llvm_unreachable_internal("Attempt to use a SCEVCouldNotCompute object!"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Analysis/ScalarEvolutionExpressions.h"
, 605);
      default:
        llvm_unreachable("Unknown SCEV kind!")::llvm::llvm_unreachable_internal("Unknown SCEV kind!", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Analysis/ScalarEvolutionExpressions.h"
, 607);
      }
    }
  }
};

/// Use SCEVTraversal to visit all nodes in the given expression tree.
template<typename SV>
void visitAll(const SCEV *Root, SV& Visitor) {
  SCEVTraversal<SV> T(Visitor);
  T.visitAll(Root);
}

/// Return true if any node in \p Root satisfies the predicate \p Pred.
template <typename PredTy>
bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
  struct FindClosure {
    bool Found = false;
    PredTy Pred;

    FindClosure(PredTy Pred) : Pred(Pred) {}

    bool follow(const SCEV *S) {
      if (!Pred(S))
        return true;

      Found = true;
      return false;
    }

    bool isDone() const { return Found; }
  };

  FindClosure FC(Pred);
  visitAll(Root, FC);
  return FC.Found;
}

/// This visitor recursively visits a SCEV expression and re-writes it.
/// The result from each visit is cached, so it will return the same
/// SCEV for the same input.
template<typename SC>
class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
protected:
  ScalarEvolution &SE;
  // Memoize the result of each visit so that we only compute once for
  // the same input SCEV. This is to avoid redundant computations when
  // a SCEV is referenced by multiple SCEVs. Without memoization, this
  // visit algorithm would have exponential time complexity in the worst
  // case, causing the compiler to hang on certain tests.
  DenseMap<const SCEV *, const SCEV *> RewriteResults;

public:
  SCEVRewriteVisitor(ScalarEvolution &SE) : SE(SE) {}

  const SCEV *visit(const SCEV *S) {
    auto It = RewriteResults.find(S);
    if (It != RewriteResults.end())
      return It->second;
    auto* Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
    auto Result = RewriteResults.try_emplace(S, Visited);
    assert(Result.second && "Should insert a new entry")((Result.second && "Should insert a new entry") ? static_cast
<void> (0) : __assert_fail ("Result.second && \"Should insert a new entry\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Analysis/ScalarEvolutionExpressions.h"
, 668, __PRETTY_FUNCTION__));
    return Result.first->second;
  }

  const SCEV *visitConstant(const SCEVConstant *Constant) {
    return Constant;
  }

  const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
    const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
    return Operand == Expr->getOperand()
               ? Expr
               : SE.getTruncateExpr(Operand, Expr->getType());
  }

  const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
    const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
    return Operand == Expr->getOperand()
               ? Expr
               : SE.getZeroExtendExpr(Operand, Expr->getType());
  }

  const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
    const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
    return Operand == Expr->getOperand()
               ? Expr
               : SE.getSignExtendExpr(Operand, Expr->getType());
  }

  const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
    SmallVector<const SCEV *, 2> Operands;
    bool Changed = false;
    for (auto *Op : Expr->operands()) {
      Operands.push_back(((SC*)this)->visit(Op));
      Changed |= Op != Operands.back();
    }
    return !Changed ? Expr : SE.getAddExpr(Operands);
  }

  const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
    SmallVector<const SCEV *, 2> Operands;
    bool Changed = false;
    for (auto *Op : Expr->operands()) {
      Operands.push_back(((SC*)this)->visit(Op));
      Changed |= Op != Operands.back();
    }
    return !Changed ? Expr : SE.getMulExpr(Operands);
  }

  const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
    auto *LHS = ((SC *)this)->visit(Expr->getLHS());
    auto *RHS = ((SC *)this)->visit(Expr->getRHS());
    bool Changed = LHS != Expr->getLHS() || RHS != Expr->getRHS();
    return !Changed ? Expr : SE.getUDivExpr(LHS, RHS);
  }

  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
    SmallVector<const SCEV *, 2> Operands;
    bool Changed = false;
    for (auto *Op : Expr->operands()) {
      Operands.push_back(((SC*)this)->visit(Op));
      Changed |= Op != Operands.back();
    }
    return !Changed ? Expr
                    : SE.getAddRecExpr(Operands, Expr->getLoop(),
                                       Expr->getNoWrapFlags());
  }

  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
    SmallVector<const SCEV *, 2> Operands;
    bool Changed = false;
    for (auto *Op : Expr->operands()) {
      Operands.push_back(((SC *)this)->visit(Op));
      Changed |= Op != Operands.back();
    }
    return !Changed ? Expr : SE.getSMaxExpr(Operands);
  }

  const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
    SmallVector<const SCEV *, 2> Operands;
    bool Changed = false;
    for (auto *Op : Expr->operands()) {
      Operands.push_back(((SC*)this)->visit(Op));
      Changed |= Op != Operands.back();
    }
    return !Changed ? Expr : SE.getUMaxExpr(Operands);
  }

  const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) {
    SmallVector<const SCEV *, 2> Operands;
    bool Changed = false;
    for (auto *Op : Expr->operands()) {
      Operands.push_back(((SC *)this)->visit(Op));
      Changed |= Op != Operands.back();
    }
    return !Changed ? Expr : SE.getSMinExpr(Operands);
  }

  const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
    SmallVector<const SCEV *, 2> Operands;
    bool Changed = false;
    for (auto *Op : Expr->operands()) {
      Operands.push_back(((SC *)this)->visit(Op));
      Changed |= Op != Operands.back();
    }
    return !Changed ? Expr : SE.getUMinExpr(Operands);
  }

  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
    return Expr;
  }

  const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
    return Expr;
  }
};

using ValueToValueMap = DenseMap<const Value *, Value *>;

/// The SCEVParameterRewriter takes a scalar evolution expression and updates
/// the SCEVUnknown components following the Map (Value -> Value).
class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
public:
  static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
                             ValueToValueMap &Map,
                             bool InterpretConsts = false) {
    SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts);
    return Rewriter.visit(Scev);
  }

  SCEVParameterRewriter(ScalarEvolution &SE, ValueToValueMap &M, bool C)
    : SCEVRewriteVisitor(SE), Map(M), InterpretConsts(C) {}

  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
    Value *V = Expr->getValue();
    if (Map.count(V)) {
      Value *NV = Map[V];
      if (InterpretConsts && isa<ConstantInt>(NV))
        return SE.getConstant(cast<ConstantInt>(NV));
      return SE.getUnknown(NV);
    }
    return Expr;
  }

private:
  ValueToValueMap &Map;
  bool InterpretConsts;
};

using LoopToScevMapT = DenseMap<const Loop *, const SCEV *>;

/// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
/// the Map (Loop -> SCEV) to all AddRecExprs.
class SCEVLoopAddRecRewriter
    : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
public:
  SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
      : SCEVRewriteVisitor(SE), Map(M) {}

  static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
                             ScalarEvolution &SE) {
    SCEVLoopAddRecRewriter Rewriter(SE, Map);
    return Rewriter.visit(Scev);
  }

  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
    SmallVector<const SCEV *, 2> Operands;
    for (const SCEV *Op : Expr->operands())
      Operands.push_back(visit(Op));

    const Loop *L = Expr->getLoop();
    const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());

    if (0 == Map.count(L))
      return Res;

    const SCEVAddRecExpr *Rec = cast<SCEVAddRecExpr>(Res);
    return Rec->evaluateAtIteration(Map[L], SE);
  }

private:
  LoopToScevMapT &Map;
};

852} // end namespace llvm

854#endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

←

/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Type.h

1//===- llvm/Type.h - Classes for handling data types ------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains the declaration of the Type class.  For more "Type"
10// stuff, look in DerivedTypes.h.
11//
12//===----------------------------------------------------------------------===//

14#ifndef LLVM_IR_TYPE_H
15#define LLVM_IR_TYPE_H

17#include "llvm/ADT/APFloat.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/Support/CBindingWrapping.h"
21#include "llvm/Support/Casting.h"
22#include "llvm/Support/Compiler.h"
23#include "llvm/Support/ErrorHandling.h"
24#include "llvm/Support/TypeSize.h"
25#include <cassert>
26#include <cstdint>
27#include <iterator>

29namespace llvm {

31template<class GraphType> struct GraphTraits;
32class IntegerType;
33class LLVMContext;
34class PointerType;
35class raw_ostream;
36class StringRef;

38/// The instances of the Type class are immutable: once they are created,
39/// they are never changed.  Also note that only one instance of a particular
40/// type is ever created.  Thus seeing if two types are equal is a matter of
41/// doing a trivial pointer comparison. To enforce that no two equal instances
42/// are created, Type instances can only be created via static factory methods
43/// in class Type and in derived classes.  Once allocated, Types are never
44/// free'd.
45///
46class Type {
47public:
//===--------------------------------------------------------------------===//
/// Definitions of all of the base types for the Type system.  Based on this
/// value, you can cast to a class defined in DerivedTypes.h.
/// Note: If you add an element to this, you need to add an element to the
/// Type::getPrimitiveType function, or else things will break!
/// Also update LLVMTypeKind and LLVMGetTypeKind () in the C binding.
///
enum TypeID {
  // PrimitiveTypes - make sure LastPrimitiveTyID stays up to date.
  VoidTyID = 0,    ///<  0: type with no size
  HalfTyID,        ///<  1: 16-bit floating point type
  FloatTyID,       ///<  2: 32-bit floating point type
  DoubleTyID,      ///<  3: 64-bit floating point type
  X86_FP80TyID,    ///<  4: 80-bit floating point type (X87)
  FP128TyID,       ///<  5: 128-bit floating point type (112-bit mantissa)
  PPC_FP128TyID,   ///<  6: 128-bit floating point type (two 64-bits, PowerPC)
  LabelTyID,       ///<  7: Labels
  MetadataTyID,    ///<  8: Metadata
  X86_MMXTyID,     ///<  9: MMX vectors (64 bits, X86 specific)
  TokenTyID,       ///< 10: Tokens

  // Derived types... see DerivedTypes.h file.
  // Make sure FirstDerivedTyID stays up to date!
  IntegerTyID,     ///< 11: Arbitrary bit width integers
  FunctionTyID,    ///< 12: Functions
  StructTyID,      ///< 13: Structures
  ArrayTyID,       ///< 14: Arrays
  PointerTyID,     ///< 15: Pointers
  VectorTyID       ///< 16: SIMD 'packed' format, or other vector type
};

79private:
/// This refers to the LLVMContext in which this type was uniqued.
LLVMContext &Context;

TypeID   ID : 8;            // The current base type of this type.
unsigned SubclassData : 24; // Space for subclasses to store data.
                            // Note that this should be synchronized with
                            // MAX_INT_BITS value in IntegerType class.

88protected:
friend class LLVMContextImpl;

explicit Type(LLVMContext &C, TypeID tid)
  : Context(C), ID(tid), SubclassData(0) {}
~Type() = default;

unsigned getSubclassData() const { return SubclassData; }

void setSubclassData(unsigned val) {
  SubclassData = val;
  // Ensure we don't have any accidental truncation.
  assert(getSubclassData() == val && "Subclass data too large for field")((getSubclassData() == val && "Subclass data too large for field"
) ? static_cast<void> (0) : __assert_fail ("getSubclassData() == val && \"Subclass data too large for field\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Type.h"
, 100, __PRETTY_FUNCTION__));
}

/// Keeps track of how many Type*'s there are in the ContainedTys list.
unsigned NumContainedTys = 0;

/// A pointer to the array of Types contained by this Type. For example, this
/// includes the arguments of a function type, the elements of a structure,
/// the pointee of a pointer, the element type of an array, etc. This pointer
/// may be 0 for types that don't contain other types (Integer, Double,
/// Float).
Type * const *ContainedTys = nullptr;

static bool isSequentialType(TypeID TyID) {
  return TyID == ArrayTyID || TyID == VectorTyID;
}

117public:
/// Print the current type.
/// Omit the type details if \p NoDetails == true.
/// E.g., let %st = type { i32, i16 }
/// When \p NoDetails is true, we only print %st.
/// Put differently, \p NoDetails prints the type as if
/// inlined with the operands when printing an instruction.
void print(raw_ostream &O, bool IsForDebug = false,
           bool NoDetails = false) const;

void dump() const;

/// Return the LLVMContext in which this type was uniqued.
LLVMContext &getContext() const { return Context; }

//===--------------------------------------------------------------------===//
// Accessors for working with types.
//

/// Return the type id for the type. This will return one of the TypeID enum
/// elements defined above.
TypeID getTypeID() const { return ID; }

/// Return true if this is 'void'.
bool isVoidTy() const { return getTypeID() == VoidTyID; }

/// Return true if this is 'half', a 16-bit IEEE fp type.
bool isHalfTy() const { return getTypeID() == HalfTyID; }

/// Return true if this is 'float', a 32-bit IEEE fp type.
bool isFloatTy() const { return getTypeID() == FloatTyID; }

/// Return true if this is 'double', a 64-bit IEEE fp type.
bool isDoubleTy() const { return getTypeID() == DoubleTyID; }

/// Return true if this is x86 long double.
bool isX86_FP80Ty() const { return getTypeID() == X86_FP80TyID; }

/// Return true if this is 'fp128'.
bool isFP128Ty() const { return getTypeID() == FP128TyID; }

/// Return true if this is powerpc long double.
bool isPPC_FP128Ty() const { return getTypeID() == PPC_FP128TyID; }

/// Return true if this is one of the six floating-point types
bool isFloatingPointTy() const {
  return getTypeID() == HalfTyID || getTypeID() == FloatTyID ||
         getTypeID() == DoubleTyID ||
         getTypeID() == X86_FP80TyID || getTypeID() == FP128TyID ||
         getTypeID() == PPC_FP128TyID;
}

const fltSemantics &getFltSemantics() const {
  switch (getTypeID()) {
  case HalfTyID: return APFloat::IEEEhalf();
  case FloatTyID: return APFloat::IEEEsingle();
  case DoubleTyID: return APFloat::IEEEdouble();
  case X86_FP80TyID: return APFloat::x87DoubleExtended();
  case FP128TyID: return APFloat::IEEEquad();
  case PPC_FP128TyID: return APFloat::PPCDoubleDouble();
  default: llvm_unreachable("Invalid floating type")::llvm::llvm_unreachable_internal("Invalid floating type", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Type.h"
, 177);
  }
}

/// Return true if this is X86 MMX.
bool isX86_MMXTy() const { return getTypeID() == X86_MMXTyID; }

/// Return true if this is a FP type or a vector of FP.
bool isFPOrFPVectorTy() const { return getScalarType()->isFloatingPointTy(); }

/// Return true if this is 'label'.
bool isLabelTy() const { return getTypeID() == LabelTyID; }

/// Return true if this is 'metadata'.
bool isMetadataTy() const { return getTypeID() == MetadataTyID; }

/// Return true if this is 'token'.
bool isTokenTy() const { return getTypeID() == TokenTyID; }

/// True if this is an instance of IntegerType.
bool isIntegerTy() const { return getTypeID() == IntegerTyID; }

/// Return true if this is an IntegerType of the given width.
bool isIntegerTy(unsigned Bitwidth) const;

/// Return true if this is an integer type or a vector of integer types.
bool isIntOrIntVectorTy() const { return getScalarType()->isIntegerTy(); }

/// Return true if this is an integer type or a vector of integer types of
/// the given width.
bool isIntOrIntVectorTy(unsigned BitWidth) const {
  return getScalarType()->isIntegerTy(BitWidth);
}

/// Return true if this is an integer type or a pointer type.
bool isIntOrPtrTy() const { return isIntegerTy() || isPointerTy(); }

/// True if this is an instance of FunctionType.
bool isFunctionTy() const { return getTypeID() == FunctionTyID; }

/// True if this is an instance of StructType.
bool isStructTy() const { return getTypeID() == StructTyID; }

/// True if this is an instance of ArrayType.
bool isArrayTy() const { return getTypeID() == ArrayTyID; }

/// True if this is an instance of PointerType.
bool isPointerTy() const { return getTypeID() == PointerTyID; }
48
←
Assuming the condition is false→
49
←
Returning zero, which participates in a condition later→

/// Return true if this is a pointer type or a vector of pointer types.
bool isPtrOrPtrVectorTy() const { return getScalarType()->isPointerTy(); }

/// True if this is an instance of VectorType.
bool isVectorTy() const { return getTypeID() == VectorTyID; }

/// Return true if this type could be converted with a lossless BitCast to
/// type 'Ty'. For example, i8* to i32*. BitCasts are valid for types of the
/// same size only where no re-interpretation of the bits is done.
/// Determine if this type could be losslessly bitcast to Ty
bool canLosslesslyBitCastTo(Type *Ty) const;

/// Return true if this type is empty, that is, it has no elements or all of
/// its elements are empty.
bool isEmptyTy() const;

/// Return true if the type is "first class", meaning it is a valid type for a
/// Value.
bool isFirstClassType() const {
  return getTypeID() != FunctionTyID && getTypeID() != VoidTyID;
}

/// Return true if the type is a valid type for a register in codegen. This
/// includes all first-class types except struct and array types.
bool isSingleValueType() const {
  return isFloatingPointTy() || isX86_MMXTy() || isIntegerTy() ||
         isPointerTy() || isVectorTy();
}

/// Return true if the type is an aggregate type. This means it is valid as
/// the first operand of an insertvalue or extractvalue instruction. This
/// includes struct and array types, but does not include vector types.
bool isAggregateType() const {
  return getTypeID() == StructTyID || getTypeID() == ArrayTyID;
}

/// Return true if it makes sense to take the size of this type. To get the
/// actual size for a particular target, it is reasonable to use the
/// DataLayout subsystem to do this.
bool isSized(SmallPtrSetImpl<Type*> *Visited = nullptr) const {
  // If it's a primitive, it is always sized.
  if (getTypeID() == IntegerTyID || isFloatingPointTy() ||
      getTypeID() == PointerTyID ||
      getTypeID() == X86_MMXTyID)
    return true;
  // If it is not something that can have a size (e.g. a function or label),
  // it doesn't have a size.
  if (getTypeID() != StructTyID && getTypeID() != ArrayTyID &&
      getTypeID() != VectorTyID)
    return false;
  // Otherwise we have to try harder to decide.
  return isSizedDerivedType(Visited);
}

/// Return the basic size of this type if it is a primitive type. These are
/// fixed by LLVM and are not target-dependent.
/// This will return zero if the type does not have a size or is not a
/// primitive type.
///
/// If this is a scalable vector type, the scalable property will be set and
/// the runtime size will be a positive integer multiple of the base size.
///
/// Note that this may not reflect the size of memory allocated for an
/// instance of the type or the number of bytes that are written when an
/// instance of the type is stored to memory. The DataLayout class provides
/// additional query functions to provide this information.
///
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY__attribute__((__pure__));

/// If this is a vector type, return the getPrimitiveSizeInBits value for the
/// element type. Otherwise return the getPrimitiveSizeInBits value for this
/// type.
unsigned getScalarSizeInBits() const LLVM_READONLY__attribute__((__pure__));

/// Return the width of the mantissa of this type. This is only valid on
/// floating-point types. If the FP type does not have a stable mantissa (e.g.
/// ppc long double), this method returns -1.
int getFPMantissaWidth() const;

/// If this is a vector type, return the element type, otherwise return
/// 'this'.
Type *getScalarType() const {
  if (isVectorTy())
    return getVectorElementType();
  return const_cast<Type*>(this);
}

//===--------------------------------------------------------------------===//
// Type Iteration support.
//
using subtype_iterator = Type * const *;

subtype_iterator subtype_begin() const { return ContainedTys; }
subtype_iterator subtype_end() const { return &ContainedTys[NumContainedTys];}
ArrayRef<Type*> subtypes() const {
  return makeArrayRef(subtype_begin(), subtype_end());
}

using subtype_reverse_iterator = std::reverse_iterator<subtype_iterator>;

subtype_reverse_iterator subtype_rbegin() const {
  return subtype_reverse_iterator(subtype_end());
}
subtype_reverse_iterator subtype_rend() const {
  return subtype_reverse_iterator(subtype_begin());
}

/// This method is used to implement the type iterator (defined at the end of
/// the file). For derived types, this returns the types 'contained' in the
/// derived type.
Type *getContainedType(unsigned i) const {
  assert(i < NumContainedTys && "Index out of range!")((i < NumContainedTys && "Index out of range!") ? static_cast
<void> (0) : __assert_fail ("i < NumContainedTys && \"Index out of range!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Type.h"
, 337, __PRETTY_FUNCTION__));
  return ContainedTys[i];
}

/// Return the number of types in the derived type.
unsigned getNumContainedTypes() const { return NumContainedTys; }

//===--------------------------------------------------------------------===//
// Helper methods corresponding to subclass methods.  This forces a cast to
// the specified subclass and calls its accessor.  "getVectorNumElements" (for
// example) is shorthand for cast<VectorType>(Ty)->getNumElements().  This is
// only intended to cover the core methods that are frequently used, helper
// methods should not be added here.

inline unsigned getIntegerBitWidth() const;

inline Type *getFunctionParamType(unsigned i) const;
inline unsigned getFunctionNumParams() const;
inline bool isFunctionVarArg() const;

inline StringRef getStructName() const;
inline unsigned getStructNumElements() const;
inline Type *getStructElementType(unsigned N) const;

inline Type *getSequentialElementType() const {
  assert(isSequentialType(getTypeID()) && "Not a sequential type!")((isSequentialType(getTypeID()) && "Not a sequential type!"
) ? static_cast<void> (0) : __assert_fail ("isSequentialType(getTypeID()) && \"Not a sequential type!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Type.h"
, 362, __PRETTY_FUNCTION__));
  return ContainedTys[0];
}

inline uint64_t getArrayNumElements() const;

Type *getArrayElementType() const {
  assert(getTypeID() == ArrayTyID)((getTypeID() == ArrayTyID) ? static_cast<void> (0) : __assert_fail
 ("getTypeID() == ArrayTyID", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Type.h"
, 369, __PRETTY_FUNCTION__));
  return ContainedTys[0];
}

inline bool getVectorIsScalable() const;
inline unsigned getVectorNumElements() const;
Type *getVectorElementType() const {
  assert(getTypeID() == VectorTyID)((getTypeID() == VectorTyID) ? static_cast<void> (0) : __assert_fail
 ("getTypeID() == VectorTyID", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Type.h"
, 376, __PRETTY_FUNCTION__));
  return ContainedTys[0];
}

Type *getPointerElementType() const {
  assert(getTypeID() == PointerTyID)((getTypeID() == PointerTyID) ? static_cast<void> (0) :
 __assert_fail ("getTypeID() == PointerTyID", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Type.h"
, 381, __PRETTY_FUNCTION__));
  return ContainedTys[0];
}

/// Given scalar/vector integer type, returns a type with elements twice as
/// wide as in the original type. For vectors, preserves element count.
inline Type *getExtendedType() const;

/// Get the address space of this pointer or pointer vector type.
inline unsigned getPointerAddressSpace() const;

//===--------------------------------------------------------------------===//
// Static members exported by the Type class itself.  Useful for getting
// instances of Type.
//

/// Return a type based on an identifier.
static Type *getPrimitiveType(LLVMContext &C, TypeID IDNumber);

//===--------------------------------------------------------------------===//
// These are the builtin types that are always available.
//
static Type *getVoidTy(LLVMContext &C);
static Type *getLabelTy(LLVMContext &C);
static Type *getHalfTy(LLVMContext &C);
static Type *getFloatTy(LLVMContext &C);
static Type *getDoubleTy(LLVMContext &C);
static Type *getMetadataTy(LLVMContext &C);
static Type *getX86_FP80Ty(LLVMContext &C);
static Type *getFP128Ty(LLVMContext &C);
static Type *getPPC_FP128Ty(LLVMContext &C);
static Type *getX86_MMXTy(LLVMContext &C);
static Type *getTokenTy(LLVMContext &C);
static IntegerType *getIntNTy(LLVMContext &C, unsigned N);
static IntegerType *getInt1Ty(LLVMContext &C);
static IntegerType *getInt8Ty(LLVMContext &C);
static IntegerType *getInt16Ty(LLVMContext &C);
static IntegerType *getInt32Ty(LLVMContext &C);
static IntegerType *getInt64Ty(LLVMContext &C);
static IntegerType *getInt128Ty(LLVMContext &C);
template <typename ScalarTy> static Type *getScalarTy(LLVMContext &C) {
  int noOfBits = sizeof(ScalarTy) * CHAR_BIT8;
  if (std::is_integral<ScalarTy>::value) {
    return (Type*) Type::getIntNTy(C, noOfBits);
  } else if (std::is_floating_point<ScalarTy>::value) {
    switch (noOfBits) {
    case 32:
      return Type::getFloatTy(C);
    case 64:
      return Type::getDoubleTy(C);
    }
  }
  llvm_unreachable("Unsupported type in Type::getScalarTy")::llvm::llvm_unreachable_internal("Unsupported type in Type::getScalarTy"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Type.h"
, 433);
}

//===--------------------------------------------------------------------===//
// Convenience methods for getting pointer types with one of the above builtin
// types as pointee.
//
static PointerType *getHalfPtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getFloatPtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getDoublePtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getX86_FP80PtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getFP128PtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getPPC_FP128PtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getX86_MMXPtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getIntNPtrTy(LLVMContext &C, unsigned N, unsigned AS = 0);
static PointerType *getInt1PtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getInt8PtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getInt16PtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getInt32PtrTy(LLVMContext &C, unsigned AS = 0);
static PointerType *getInt64PtrTy(LLVMContext &C, unsigned AS = 0);

/// Return a pointer to the current type. This is equivalent to
/// PointerType::get(Foo, AddrSpace).
PointerType *getPointerTo(unsigned AddrSpace = 0) const;

458private:
/// Derived types like structures and arrays are sized iff all of the members
/// of the type are sized as well. Since asking for their size is relatively
/// uncommon, move this operation out-of-line.
bool isSizedDerivedType(SmallPtrSetImpl<Type*> *Visited = nullptr) const;
463};

465// Printing of types.
466inline raw_ostream &operator<<(raw_ostream &OS, const Type &T) {
T.print(OS);
return OS;
469}

471// allow isa<PointerType>(x) to work without DerivedTypes.h included.
472template <> struct isa_impl<PointerType, Type> {
static inline bool doit(const Type &Ty) {
  return Ty.getTypeID() == Type::PointerTyID;
}
476};

478// Create wrappers for C Binding types (see CBindingWrapping.h).
479DEFINE_ISA_CONVERSION_FUNCTIONS(Type, LLVMTypeRef)inline Type *unwrap(LLVMTypeRef P) { return reinterpret_cast<
Type*>(P); } inline LLVMTypeRef wrap(const Type *P) { return
 reinterpret_cast<LLVMTypeRef>(const_cast<Type*>(
P)); } template<typename T> inline T *unwrap(LLVMTypeRef
 P) { return cast<T>(unwrap(P)); }

481/* Specialized opaque type conversions.
*/
483inline Type **unwrap(LLVMTypeRef* Tys) {
return reinterpret_cast<Type**>(Tys);
485}

487inline LLVMTypeRef *wrap(Type **Tys) {
return reinterpret_cast<LLVMTypeRef*>(const_cast<Type**>(Tys));
489}

491} // end namespace llvm

493#endif // LLVM_IR_TYPE_H