/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/ADT/APInt.h

Bug Summary

File:	build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/ADT/APInt.h
Warning:	line 153, column 39 Assigned value is garbage or undefined

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name LazyValueInfo.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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -resource-dir /usr/lib/llvm-15/lib/clang/15.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Analysis -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Analysis -I include -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-15/lib/clang/15.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-04-20-140412-16051-1 -x c++ /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Analysis/LazyValueInfo.cpp

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Analysis/LazyValueInfo.cpp

→

1//===- LazyValueInfo.cpp - Value constraint analysis ------------*- 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 interface for lazy computation of value constraint
10// information.
11//
12//===----------------------------------------------------------------------===//

14#include "llvm/Analysis/LazyValueInfo.h"
15#include "llvm/ADT/DenseSet.h"
16#include "llvm/ADT/Optional.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/Analysis/AssumptionCache.h"
19#include "llvm/Analysis/ConstantFolding.h"
20#include "llvm/Analysis/InstructionSimplify.h"
21#include "llvm/Analysis/TargetLibraryInfo.h"
22#include "llvm/Analysis/ValueLattice.h"
23#include "llvm/Analysis/ValueTracking.h"
24#include "llvm/IR/AssemblyAnnotationWriter.h"
25#include "llvm/IR/CFG.h"
26#include "llvm/IR/ConstantRange.h"
27#include "llvm/IR/Constants.h"
28#include "llvm/IR/DataLayout.h"
29#include "llvm/IR/Dominators.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/IntrinsicInst.h"
32#include "llvm/IR/Intrinsics.h"
33#include "llvm/IR/LLVMContext.h"
34#include "llvm/IR/PatternMatch.h"
35#include "llvm/IR/ValueHandle.h"
36#include "llvm/InitializePasses.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/FormattedStream.h"
39#include "llvm/Support/KnownBits.h"
40#include "llvm/Support/raw_ostream.h"
41using namespace llvm;
42using namespace PatternMatch;

44#define DEBUG_TYPE"lazy-value-info" "lazy-value-info"

46// This is the number of worklist items we will process to try to discover an
47// answer for a given value.
48static const unsigned MaxProcessedPerValue = 500;

50char LazyValueInfoWrapperPass::ID = 0;
51LazyValueInfoWrapperPass::LazyValueInfoWrapperPass() : FunctionPass(ID) {
initializeLazyValueInfoWrapperPassPass(*PassRegistry::getPassRegistry());
53}
54INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",static void *initializeLazyValueInfoWrapperPassPassOnce(PassRegistry
 &Registry) {
              "Lazy Value Information Analysis", false, true)static void *initializeLazyValueInfoWrapperPassPassOnce(PassRegistry
 &Registry) {
56INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);
57INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
58INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",PassInfo *PI = new PassInfo( "Lazy Value Information Analysis"
, "lazy-value-info", &LazyValueInfoWrapperPass::ID, PassInfo
::NormalCtor_t(callDefaultCtor<LazyValueInfoWrapperPass>
), false, true); Registry.registerPass(*PI, true); return PI;
 } static llvm::once_flag InitializeLazyValueInfoWrapperPassPassFlag
; void llvm::initializeLazyValueInfoWrapperPassPass(PassRegistry
 &Registry) { llvm::call_once(InitializeLazyValueInfoWrapperPassPassFlag
, initializeLazyValueInfoWrapperPassPassOnce, std::ref(Registry
)); }
              "Lazy Value Information Analysis", false, true)PassInfo *PI = new PassInfo( "Lazy Value Information Analysis"
, "lazy-value-info", &LazyValueInfoWrapperPass::ID, PassInfo
::NormalCtor_t(callDefaultCtor<LazyValueInfoWrapperPass>
), false, true); Registry.registerPass(*PI, true); return PI;
 } static llvm::once_flag InitializeLazyValueInfoWrapperPassPassFlag
; void llvm::initializeLazyValueInfoWrapperPassPass(PassRegistry
 &Registry) { llvm::call_once(InitializeLazyValueInfoWrapperPassPassFlag
, initializeLazyValueInfoWrapperPassPassOnce, std::ref(Registry
)); }

61namespace llvm {
FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
63}

65AnalysisKey LazyValueAnalysis::Key;

67/// Returns true if this lattice value represents at most one possible value.
68/// This is as precise as any lattice value can get while still representing
69/// reachable code.
70static bool hasSingleValue(const ValueLatticeElement &Val) {
if (Val.isConstantRange() &&
    Val.getConstantRange().isSingleElement())
  // Integer constants are single element ranges
  return true;
if (Val.isConstant())
  // Non integer constants
  return true;
return false;
79}

81/// Combine two sets of facts about the same value into a single set of
82/// facts.  Note that this method is not suitable for merging facts along
83/// different paths in a CFG; that's what the mergeIn function is for.  This
84/// is for merging facts gathered about the same value at the same location
85/// through two independent means.
86/// Notes:
87/// * This method does not promise to return the most precise possible lattice
88///   value implied by A and B.  It is allowed to return any lattice element
89///   which is at least as strong as *either* A or B (unless our facts
90///   conflict, see below).
91/// * Due to unreachable code, the intersection of two lattice values could be
92///   contradictory.  If this happens, we return some valid lattice value so as
93///   not confuse the rest of LVI.  Ideally, we'd always return Undefined, but
94///   we do not make this guarantee.  TODO: This would be a useful enhancement.
95static ValueLatticeElement intersect(const ValueLatticeElement &A,
                                   const ValueLatticeElement &B) {
// Undefined is the strongest state.  It means the value is known to be along
// an unreachable path.
if (A.isUnknown())
  return A;
if (B.isUnknown())
  return B;

// If we gave up for one, but got a useable fact from the other, use it.
if (A.isOverdefined())
  return B;
if (B.isOverdefined())
  return A;

// Can't get any more precise than constants.
if (hasSingleValue(A))
  return A;
if (hasSingleValue(B))
  return B;

// Could be either constant range or not constant here.
if (!A.isConstantRange() || !B.isConstantRange()) {
  // TODO: Arbitrary choice, could be improved
  return A;
}

// Intersect two constant ranges
ConstantRange Range =
    A.getConstantRange().intersectWith(B.getConstantRange());
// Note: An empty range is implicitly converted to unknown or undef depending
// on MayIncludeUndef internally.
return ValueLatticeElement::getRange(
    std::move(Range), /*MayIncludeUndef=*/A.isConstantRangeIncludingUndef() ||
                          B.isConstantRangeIncludingUndef());
130}

132//===----------------------------------------------------------------------===//
133//                          LazyValueInfoCache Decl
134//===----------------------------------------------------------------------===//

136namespace {
/// A callback value handle updates the cache when values are erased.
class LazyValueInfoCache;
struct LVIValueHandle final : public CallbackVH {
  LazyValueInfoCache *Parent;

  LVIValueHandle(Value *V, LazyValueInfoCache *P = nullptr)
    : CallbackVH(V), Parent(P) { }

  void deleted() override;
  void allUsesReplacedWith(Value *V) override {
    deleted();
  }
};
150} // end anonymous namespace

152namespace {
using NonNullPointerSet = SmallDenseSet<AssertingVH<Value>, 2>;

/// This is the cache kept by LazyValueInfo which
/// maintains information about queries across the clients' queries.
class LazyValueInfoCache {
  /// This is all of the cached information for one basic block. It contains
  /// the per-value lattice elements, as well as a separate set for
  /// overdefined values to reduce memory usage. Additionally pointers
  /// dereferenced in the block are cached for nullability queries.
  struct BlockCacheEntry {
    SmallDenseMap<AssertingVH<Value>, ValueLatticeElement, 4> LatticeElements;
    SmallDenseSet<AssertingVH<Value>, 4> OverDefined;
    // None indicates that the nonnull pointers for this basic block
    // block have not been computed yet.
    Optional<NonNullPointerSet> NonNullPointers;
  };

  /// Cached information per basic block.
  DenseMap<PoisoningVH<BasicBlock>, std::unique_ptr<BlockCacheEntry>>
      BlockCache;
  /// Set of value handles used to erase values from the cache on deletion.
  DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles;

  const BlockCacheEntry *getBlockEntry(BasicBlock *BB) const {
    auto It = BlockCache.find_as(BB);
    if (It == BlockCache.end())
      return nullptr;
    return It->second.get();
  }

  BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) {
    auto It = BlockCache.find_as(BB);
    if (It == BlockCache.end())
      It = BlockCache.insert({ BB, std::make_unique<BlockCacheEntry>() })
                     .first;

    return It->second.get();
  }

  void addValueHandle(Value *Val) {
    auto HandleIt = ValueHandles.find_as(Val);
    if (HandleIt == ValueHandles.end())
      ValueHandles.insert({ Val, this });
  }

public:
  void insertResult(Value *Val, BasicBlock *BB,
                    const ValueLatticeElement &Result) {
    BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);

    // Insert over-defined values into their own cache to reduce memory
    // overhead.
    if (Result.isOverdefined())
      Entry->OverDefined.insert(Val);
    else
      Entry->LatticeElements.insert({ Val, Result });

    addValueHandle(Val);
  }

  Optional<ValueLatticeElement> getCachedValueInfo(Value *V,
                                                   BasicBlock *BB) const {
    const BlockCacheEntry *Entry = getBlockEntry(BB);
    if (!Entry)
      return None;

    if (Entry->OverDefined.count(V))
      return ValueLatticeElement::getOverdefined();

    auto LatticeIt = Entry->LatticeElements.find_as(V);
    if (LatticeIt == Entry->LatticeElements.end())
      return None;

    return LatticeIt->second;
  }

  bool isNonNullAtEndOfBlock(
      Value *V, BasicBlock *BB,
      function_ref<NonNullPointerSet(BasicBlock *)> InitFn) {
    BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
    if (!Entry->NonNullPointers) {
      Entry->NonNullPointers = InitFn(BB);
      for (Value *V : *Entry->NonNullPointers)
        addValueHandle(V);
    }

    return Entry->NonNullPointers->count(V);
  }

  /// clear - Empty the cache.
  void clear() {
    BlockCache.clear();
    ValueHandles.clear();
  }

  /// Inform the cache that a given value has been deleted.
  void eraseValue(Value *V);

  /// This is part of the update interface to inform the cache
  /// that a block has been deleted.
  void eraseBlock(BasicBlock *BB);

  /// Updates the cache to remove any influence an overdefined value in
  /// OldSucc might have (unless also overdefined in NewSucc).  This just
  /// flushes elements from the cache and does not add any.
  void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
};
260}

262void LazyValueInfoCache::eraseValue(Value *V) {
for (auto &Pair : BlockCache) {
  Pair.second->LatticeElements.erase(V);
  Pair.second->OverDefined.erase(V);
  if (Pair.second->NonNullPointers)
    Pair.second->NonNullPointers->erase(V);
}

auto HandleIt = ValueHandles.find_as(V);
if (HandleIt != ValueHandles.end())
  ValueHandles.erase(HandleIt);
273}

275void LVIValueHandle::deleted() {
// This erasure deallocates *this, so it MUST happen after we're done
// using any and all members of *this.
Parent->eraseValue(*this);
279}

281void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
BlockCache.erase(BB);
283}

285void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
                                      BasicBlock *NewSucc) {
// When an edge in the graph has been threaded, values that we could not
// determine a value for before (i.e. were marked overdefined) may be
// possible to solve now. We do NOT try to proactively update these values.
// Instead, we clear their entries from the cache, and allow lazy updating to
// recompute them when needed.

// The updating process is fairly simple: we need to drop cached info
// for all values that were marked overdefined in OldSucc, and for those same
// values in any successor of OldSucc (except NewSucc) in which they were
// also marked overdefined.
std::vector<BasicBlock*> worklist;
worklist.push_back(OldSucc);

const BlockCacheEntry *Entry = getBlockEntry(OldSucc);
if (!Entry || Entry->OverDefined.empty())
  return; // Nothing to process here.
SmallVector<Value *, 4> ValsToClear(Entry->OverDefined.begin(),
                                    Entry->OverDefined.end());

// Use a worklist to perform a depth-first search of OldSucc's successors.
// NOTE: We do not need a visited list since any blocks we have already
// visited will have had their overdefined markers cleared already, and we
// thus won't loop to their successors.
while (!worklist.empty()) {
  BasicBlock *ToUpdate = worklist.back();
  worklist.pop_back();

  // Skip blocks only accessible through NewSucc.
  if (ToUpdate == NewSucc) continue;

  // If a value was marked overdefined in OldSucc, and is here too...
  auto OI = BlockCache.find_as(ToUpdate);
  if (OI == BlockCache.end() || OI->second->OverDefined.empty())
    continue;
  auto &ValueSet = OI->second->OverDefined;

  bool changed = false;
  for (Value *V : ValsToClear) {
    if (!ValueSet.erase(V))
      continue;

    // If we removed anything, then we potentially need to update
    // blocks successors too.
    changed = true;
  }

  if (!changed) continue;

  llvm::append_range(worklist, successors(ToUpdate));
}
337}


340namespace {
341/// An assembly annotator class to print LazyValueCache information in
342/// comments.
343class LazyValueInfoImpl;
344class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
LazyValueInfoImpl *LVIImpl;
// While analyzing which blocks we can solve values for, we need the dominator
// information.
DominatorTree &DT;

350public:
LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
    : LVIImpl(L), DT(DTree) {}

void emitBasicBlockStartAnnot(const BasicBlock *BB,
                              formatted_raw_ostream &OS) override;

void emitInstructionAnnot(const Instruction *I,
                          formatted_raw_ostream &OS) override;
359};
360}
361namespace {
362// The actual implementation of the lazy analysis and update.  Note that the
363// inheritance from LazyValueInfoCache is intended to be temporary while
364// splitting the code and then transitioning to a has-a relationship.
365class LazyValueInfoImpl {

/// Cached results from previous queries
LazyValueInfoCache TheCache;

/// This stack holds the state of the value solver during a query.
/// It basically emulates the callstack of the naive
/// recursive value lookup process.
SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;

/// Keeps track of which block-value pairs are in BlockValueStack.
DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;

/// Push BV onto BlockValueStack unless it's already in there.
/// Returns true on success.
bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
  if (!BlockValueSet.insert(BV).second)
    return false;  // It's already in the stack.

  LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "PUSH: " << *BV.
second << " in " << BV.first->getName() <<
 "\n"; } } while (false)
                    << BV.first->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "PUSH: " << *BV.
second << " in " << BV.first->getName() <<
 "\n"; } } while (false);
  BlockValueStack.push_back(BV);
  return true;
}

AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
const DataLayout &DL; ///< A mandatory DataLayout

/// Declaration of the llvm.experimental.guard() intrinsic,
/// if it exists in the module.
Function *GuardDecl;

Optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB,
                                            Instruction *CxtI);
Optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F,
                              BasicBlock *T, Instruction *CxtI = nullptr);

// These methods process one work item and may add more. A false value
// returned means that the work item was not completely processed and must
// be revisited after going through the new items.
bool solveBlockValue(Value *Val, BasicBlock *BB);
Optional<ValueLatticeElement> solveBlockValueImpl(Value *Val, BasicBlock *BB);
Optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val,
                                                      BasicBlock *BB);
Optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN,
                                                     BasicBlock *BB);
Optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S,
                                                    BasicBlock *BB);
Optional<ConstantRange> getRangeFor(Value *V, Instruction *CxtI,
                                    BasicBlock *BB);
Optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
    Instruction *I, BasicBlock *BB,
    std::function<ConstantRange(const ConstantRange &,
                                const ConstantRange &)> OpFn);
Optional<ValueLatticeElement> solveBlockValueBinaryOp(BinaryOperator *BBI,
                                                      BasicBlock *BB);
Optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI,
                                                  BasicBlock *BB);
Optional<ValueLatticeElement> solveBlockValueOverflowIntrinsic(
    WithOverflowInst *WO, BasicBlock *BB);
Optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II,
                                                       BasicBlock *BB);
Optional<ValueLatticeElement> solveBlockValueExtractValue(
    ExtractValueInst *EVI, BasicBlock *BB);
bool isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB);
void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
                                                   ValueLatticeElement &BBLV,
                                                   Instruction *BBI);

void solve();

436public:
/// This is the query interface to determine the lattice value for the
/// specified Value* at the context instruction (if specified) or at the
/// start of the block.
ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
                                    Instruction *CxtI = nullptr);

/// This is the query interface to determine the lattice value for the
/// specified Value* at the specified instruction using only information
/// from assumes/guards and range metadata. Unlike getValueInBlock(), no
/// recursive query is performed.
ValueLatticeElement getValueAt(Value *V, Instruction *CxtI);

/// This is the query interface to determine the lattice
/// value for the specified Value* that is true on the specified edge.
ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB,
                                   BasicBlock *ToBB,
                                   Instruction *CxtI = nullptr);

/// Complete flush all previously computed values
void clear() {
  TheCache.clear();
}

/// Printing the LazyValueInfo Analysis.
void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
  LazyValueInfoAnnotatedWriter Writer(this, DTree);
  F.print(OS, &Writer);
}

/// This is part of the update interface to inform the cache
/// that a block has been deleted.
void eraseBlock(BasicBlock *BB) {
  TheCache.eraseBlock(BB);
}

/// This is the update interface to inform the cache that an edge from
/// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);

LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
                  Function *GuardDecl)
    : AC(AC), DL(DL), GuardDecl(GuardDecl) {}
479};
480} // end anonymous namespace


483void LazyValueInfoImpl::solve() {
SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
    BlockValueStack.begin(), BlockValueStack.end());

unsigned processedCount = 0;
while (!BlockValueStack.empty()) {
  processedCount++;
  // Abort if we have to process too many values to get a result for this one.
  // Because of the design of the overdefined cache currently being per-block
  // to avoid naming-related issues (IE it wants to try to give different
  // results for the same name in different blocks), overdefined results don't
  // get cached globally, which in turn means we will often try to rediscover
  // the same overdefined result again and again.  Once something like
  // PredicateInfo is used in LVI or CVP, we should be able to make the
  // overdefined cache global, and remove this throttle.
  if (processedCount > MaxProcessedPerValue) {
    LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "Giving up on stack because we are getting too deep\n"
; } } while (false)
        dbgs() << "Giving up on stack because we are getting too deep\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "Giving up on stack because we are getting too deep\n"
; } } while (false);
    // Fill in the original values
    while (!StartingStack.empty()) {
      std::pair<BasicBlock *, Value *> &e = StartingStack.back();
      TheCache.insertResult(e.second, e.first,
                            ValueLatticeElement::getOverdefined());
      StartingStack.pop_back();
    }
    BlockValueSet.clear();
    BlockValueStack.clear();
    return;
  }
  std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
  assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!")(static_cast <bool> (BlockValueSet.count(e) && "Stack value should be in BlockValueSet!"
) ? void (0) : __assert_fail ("BlockValueSet.count(e) && \"Stack value should be in BlockValueSet!\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 513, __extension__ __PRETTY_FUNCTION__
));

  if (solveBlockValue(e.second, e.first)) {
    // The work item was completely processed.
    assert(BlockValueStack.back() == e && "Nothing should have been pushed!")(static_cast <bool> (BlockValueStack.back() == e &&
 "Nothing should have been pushed!") ? void (0) : __assert_fail
 ("BlockValueStack.back() == e && \"Nothing should have been pushed!\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 517, __extension__ __PRETTY_FUNCTION__
));
518#ifndef NDEBUG
    Optional<ValueLatticeElement> BBLV =
        TheCache.getCachedValueInfo(e.second, e.first);
    assert(BBLV && "Result should be in cache!")(static_cast <bool> (BBLV && "Result should be in cache!"
) ? void (0) : __assert_fail ("BBLV && \"Result should be in cache!\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 521, __extension__ __PRETTY_FUNCTION__
));
    LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "POP " << *e.second
 << " in " << e.first->getName() << " = "
 << *BBLV << "\n"; } } while (false)
        dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "POP " << *e.second
 << " in " << e.first->getName() << " = "
 << *BBLV << "\n"; } } while (false)
               << *BBLV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "POP " << *e.second
 << " in " << e.first->getName() << " = "
 << *BBLV << "\n"; } } while (false);
525#endif

    BlockValueStack.pop_back();
    BlockValueSet.erase(e);
  } else {
    // More work needs to be done before revisiting.
    assert(BlockValueStack.back() != e && "Stack should have been pushed!")(static_cast <bool> (BlockValueStack.back() != e &&
 "Stack should have been pushed!") ? void (0) : __assert_fail
 ("BlockValueStack.back() != e && \"Stack should have been pushed!\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 531, __extension__ __PRETTY_FUNCTION__
));
  }
}
534}

536Optional<ValueLatticeElement> LazyValueInfoImpl::getBlockValue(
  Value *Val, BasicBlock *BB, Instruction *CxtI) {
// If already a constant, there is nothing to compute.
if (Constant *VC = dyn_cast<Constant>(Val))
  return ValueLatticeElement::get(VC);

if (Optional<ValueLatticeElement> OptLatticeVal =
        TheCache.getCachedValueInfo(Val, BB)) {
  intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);
  return OptLatticeVal;
}

// We have hit a cycle, assume overdefined.
if (!pushBlockValue({ BB, Val }))
  return ValueLatticeElement::getOverdefined();

// Yet to be resolved.
return None;
554}

556static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
switch (BBI->getOpcode()) {
default: break;
case Instruction::Load:
case Instruction::Call:
case Instruction::Invoke:
  if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
    if (isa<IntegerType>(BBI->getType())) {
      return ValueLatticeElement::getRange(
          getConstantRangeFromMetadata(*Ranges));
    }
  break;
};
// Nothing known - will be intersected with other facts
return ValueLatticeElement::getOverdefined();
571}

573bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
assert(!isa<Constant>(Val) && "Value should not be constant")(static_cast <bool> (!isa<Constant>(Val) &&
 "Value should not be constant") ? void (0) : __assert_fail (
"!isa<Constant>(Val) && \"Value should not be constant\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 574, __extension__ __PRETTY_FUNCTION__
));
assert(!TheCache.getCachedValueInfo(Val, BB) &&(static_cast <bool> (!TheCache.getCachedValueInfo(Val, BB
) && "Value should not be in cache") ? void (0) : __assert_fail
 ("!TheCache.getCachedValueInfo(Val, BB) && \"Value should not be in cache\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 576, __extension__ __PRETTY_FUNCTION__
))
       "Value should not be in cache")(static_cast <bool> (!TheCache.getCachedValueInfo(Val, BB
) && "Value should not be in cache") ? void (0) : __assert_fail
 ("!TheCache.getCachedValueInfo(Val, BB) && \"Value should not be in cache\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 576, __extension__ __PRETTY_FUNCTION__
));

// Hold off inserting this value into the Cache in case we have to return
// false and come back later.
Optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB);
if (!Res)
  // Work pushed, will revisit
  return false;

TheCache.insertResult(Val, BB, *Res);
return true;
587}

589Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueImpl(
  Value *Val, BasicBlock *BB) {
Instruction *BBI = dyn_cast<Instruction>(Val);
if (!BBI || BBI->getParent() != BB)
  return solveBlockValueNonLocal(Val, BB);

if (PHINode *PN = dyn_cast<PHINode>(BBI))
  return solveBlockValuePHINode(PN, BB);

if (auto *SI = dyn_cast<SelectInst>(BBI))
  return solveBlockValueSelect(SI, BB);

// If this value is a nonnull pointer, record it's range and bailout.  Note
// that for all other pointer typed values, we terminate the search at the
// definition.  We could easily extend this to look through geps, bitcasts,
// and the like to prove non-nullness, but it's not clear that's worth it
// compile time wise.  The context-insensitive value walk done inside
// isKnownNonZero gets most of the profitable cases at much less expense.
// This does mean that we have a sensitivity to where the defining
// instruction is placed, even if it could legally be hoisted much higher.
// That is unfortunate.
PointerType *PT = dyn_cast<PointerType>(BBI->getType());
if (PT && isKnownNonZero(BBI, DL))
  return ValueLatticeElement::getNot(ConstantPointerNull::get(PT));

if (BBI->getType()->isIntegerTy()) {
  if (auto *CI = dyn_cast<CastInst>(BBI))
    return solveBlockValueCast(CI, BB);

  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
    return solveBlockValueBinaryOp(BO, BB);

  if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
    return solveBlockValueExtractValue(EVI, BB);

  if (auto *II = dyn_cast<IntrinsicInst>(BBI))
    return solveBlockValueIntrinsic(II, BB);
}

LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - unknown inst def found.\n"; }
 } while (false)
                  << "' - unknown inst def found.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - unknown inst def found.\n"; }
 } while (false);
return getFromRangeMetadata(BBI);
631}

633static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) {
// TODO: Use NullPointerIsDefined instead.
if (Ptr->getType()->getPointerAddressSpace() == 0)
  PtrSet.insert(getUnderlyingObject(Ptr));
637}

639static void AddNonNullPointersByInstruction(
  Instruction *I, NonNullPointerSet &PtrSet) {
if (LoadInst *L = dyn_cast<LoadInst>(I)) {
  AddNonNullPointer(L->getPointerOperand(), PtrSet);
} else if (StoreInst *S = dyn_cast<StoreInst>(I)) {
  AddNonNullPointer(S->getPointerOperand(), PtrSet);
} else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
  if (MI->isVolatile()) return;

  // FIXME: check whether it has a valuerange that excludes zero?
  ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
  if (!Len || Len->isZero()) return;

  AddNonNullPointer(MI->getRawDest(), PtrSet);
  if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
    AddNonNullPointer(MTI->getRawSource(), PtrSet);
}
656}

658bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) {
if (NullPointerIsDefined(BB->getParent(),
                         Val->getType()->getPointerAddressSpace()))
  return false;

Val = Val->stripInBoundsOffsets();
return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) {
  NonNullPointerSet NonNullPointers;
  for (Instruction &I : *BB)
    AddNonNullPointersByInstruction(&I, NonNullPointers);
  return NonNullPointers;
});
670}

672Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal(
  Value *Val, BasicBlock *BB) {
ValueLatticeElement Result;  // Start Undefined.

// If this is the entry block, we must be asking about an argument.  The
// value is overdefined.
if (BB->isEntryBlock()) {
  assert(isa<Argument>(Val) && "Unknown live-in to the entry block")(static_cast <bool> (isa<Argument>(Val) &&
 "Unknown live-in to the entry block") ? void (0) : __assert_fail
 ("isa<Argument>(Val) && \"Unknown live-in to the entry block\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 679, __extension__ __PRETTY_FUNCTION__
));
  return ValueLatticeElement::getOverdefined();
}

// Loop over all of our predecessors, merging what we know from them into
// result.  If we encounter an unexplored predecessor, we eagerly explore it
// in a depth first manner.  In practice, this has the effect of discovering
// paths we can't analyze eagerly without spending compile times analyzing
// other paths.  This heuristic benefits from the fact that predecessors are
// frequently arranged such that dominating ones come first and we quickly
// find a path to function entry.  TODO: We should consider explicitly
// canonicalizing to make this true rather than relying on this happy
// accident.
for (BasicBlock *Pred : predecessors(BB)) {
  Optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB);
  if (!EdgeResult)
    // Explore that input, then return here
    return None;

  Result.mergeIn(*EdgeResult);

  // If we hit overdefined, exit early.  The BlockVals entry is already set
  // to overdefined.
  if (Result.isOverdefined()) {
    LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined because of pred (non local).\n"
; } } while (false)
                      << "' - overdefined because of pred (non local).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined because of pred (non local).\n"
; } } while (false);
    return Result;
  }
}

// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined())(static_cast <bool> (!Result.isOverdefined()) ? void (0
) : __assert_fail ("!Result.isOverdefined()", "llvm/lib/Analysis/LazyValueInfo.cpp"
, 710, __extension__ __PRETTY_FUNCTION__));
return Result;
712}

714Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValuePHINode(
  PHINode *PN, BasicBlock *BB) {
ValueLatticeElement Result;  // Start Undefined.

// Loop over all of our predecessors, merging what we know from them into
// result.  See the comment about the chosen traversal order in
// solveBlockValueNonLocal; the same reasoning applies here.
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
  BasicBlock *PhiBB = PN->getIncomingBlock(i);
  Value *PhiVal = PN->getIncomingValue(i);
  // Note that we can provide PN as the context value to getEdgeValue, even
  // though the results will be cached, because PN is the value being used as
  // the cache key in the caller.
  Optional<ValueLatticeElement> EdgeResult =
      getEdgeValue(PhiVal, PhiBB, BB, PN);
  if (!EdgeResult)
    // Explore that input, then return here
    return None;

  Result.mergeIn(*EdgeResult);

  // If we hit overdefined, exit early.  The BlockVals entry is already set
  // to overdefined.
  if (Result.isOverdefined()) {
    LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined because of pred (local).\n"
; } } while (false)
                      << "' - overdefined because of pred (local).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined because of pred (local).\n"
; } } while (false);

    return Result;
  }
}

// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined() && "Possible PHI in entry block?")(static_cast <bool> (!Result.isOverdefined() &&
 "Possible PHI in entry block?") ? void (0) : __assert_fail (
"!Result.isOverdefined() && \"Possible PHI in entry block?\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 746, __extension__ __PRETTY_FUNCTION__
));
return Result;
748}

750static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
                                               bool isTrueDest = true);

753// If we can determine a constraint on the value given conditions assumed by
754// the program, intersect those constraints with BBLV
755void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
      Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
if (!BBI)
  return;

BasicBlock *BB = BBI->getParent();
for (auto &AssumeVH : AC->assumptionsFor(Val)) {
  if (!AssumeVH)
    continue;

  // Only check assumes in the block of the context instruction. Other
  // assumes will have already been taken into account when the value was
  // propagated from predecessor blocks.
  auto *I = cast<CallInst>(AssumeVH);
  if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))
    continue;

  BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
}

// If guards are not used in the module, don't spend time looking for them
if (GuardDecl && !GuardDecl->use_empty() &&
    BBI->getIterator() != BB->begin()) {
  for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()),
                                   BB->rend())) {
    Value *Cond = nullptr;
    if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
      BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
  }
}

if (BBLV.isOverdefined()) {
  // Check whether we're checking at the terminator, and the pointer has
  // been dereferenced in this block.
  PointerType *PTy = dyn_cast<PointerType>(Val->getType());
  if (PTy && BB->getTerminator() == BBI &&
      isNonNullAtEndOfBlock(Val, BB))
    BBLV = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
}
795}

797static ConstantRange getConstantRangeOrFull(const ValueLatticeElement &Val,
                                          Type *Ty, const DataLayout &DL) {
if (Val.isConstantRange())
  return Val.getConstantRange();
return ConstantRange::getFull(DL.getTypeSizeInBits(Ty));
802}

804Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect(
  SelectInst *SI, BasicBlock *BB) {
// Recurse on our inputs if needed
Optional<ValueLatticeElement> OptTrueVal =
    getBlockValue(SI->getTrueValue(), BB, SI);
if (!OptTrueVal)
  return None;
ValueLatticeElement &TrueVal = *OptTrueVal;

Optional<ValueLatticeElement> OptFalseVal =
    getBlockValue(SI->getFalseValue(), BB, SI);
if (!OptFalseVal)
  return None;
ValueLatticeElement &FalseVal = *OptFalseVal;

if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) {
  const ConstantRange &TrueCR =
      getConstantRangeOrFull(TrueVal, SI->getType(), DL);
  const ConstantRange &FalseCR =
      getConstantRangeOrFull(FalseVal, SI->getType(), DL);
  Value *LHS = nullptr;
  Value *RHS = nullptr;
  SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
  // Is this a min specifically of our two inputs?  (Avoid the risk of
  // ValueTracking getting smarter looking back past our immediate inputs.)
  if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
      ((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) ||
       (RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) {
    ConstantRange ResultCR = [&]() {
      switch (SPR.Flavor) {
      default:
        llvm_unreachable("unexpected minmax type!")::llvm::llvm_unreachable_internal("unexpected minmax type!", "llvm/lib/Analysis/LazyValueInfo.cpp"
, 835);
      case SPF_SMIN:                   /// Signed minimum
        return TrueCR.smin(FalseCR);
      case SPF_UMIN:                   /// Unsigned minimum
        return TrueCR.umin(FalseCR);
      case SPF_SMAX:                   /// Signed maximum
        return TrueCR.smax(FalseCR);
      case SPF_UMAX:                   /// Unsigned maximum
        return TrueCR.umax(FalseCR);
      };
    }();
    return ValueLatticeElement::getRange(
        ResultCR, TrueVal.isConstantRangeIncludingUndef() ||
                      FalseVal.isConstantRangeIncludingUndef());
  }

  if (SPR.Flavor == SPF_ABS) {
    if (LHS == SI->getTrueValue())
      return ValueLatticeElement::getRange(
          TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef());
    if (LHS == SI->getFalseValue())
      return ValueLatticeElement::getRange(
          FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef());
  }

  if (SPR.Flavor == SPF_NABS) {
    ConstantRange Zero(APInt::getZero(TrueCR.getBitWidth()));
    if (LHS == SI->getTrueValue())
      return ValueLatticeElement::getRange(
          Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef());
    if (LHS == SI->getFalseValue())
      return ValueLatticeElement::getRange(
          Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef());
  }
}

// Can we constrain the facts about the true and false values by using the
// condition itself?  This shows up with idioms like e.g. select(a > 5, a, 5).
// TODO: We could potentially refine an overdefined true value above.
Value *Cond = SI->getCondition();
TrueVal = intersect(TrueVal,
                    getValueFromCondition(SI->getTrueValue(), Cond, true));
FalseVal = intersect(FalseVal,
                     getValueFromCondition(SI->getFalseValue(), Cond, false));

ValueLatticeElement Result = TrueVal;
Result.mergeIn(FalseVal);
return Result;
883}

885Optional<ConstantRange> LazyValueInfoImpl::getRangeFor(Value *V,
                                                     Instruction *CxtI,
                                                     BasicBlock *BB) {
Optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI);
if (!OptVal)
  return None;
return getConstantRangeOrFull(*OptVal, V->getType(), DL);
892}

894Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueCast(
  CastInst *CI, BasicBlock *BB) {
// Without knowing how wide the input is, we can't analyze it in any useful
// way.
if (!CI->getOperand(0)->getType()->isSized())
  return ValueLatticeElement::getOverdefined();

// Filter out casts we don't know how to reason about before attempting to
// recurse on our operand.  This can cut a long search short if we know we're
// not going to be able to get any useful information anways.
switch (CI->getOpcode()) {
case Instruction::Trunc:
case Instruction::SExt:
case Instruction::ZExt:
case Instruction::BitCast:
  break;
default:
  // Unhandled instructions are overdefined.
  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined (unknown cast).\n"
; } } while (false)
                    << "' - overdefined (unknown cast).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined (unknown cast).\n"
; } } while (false);
  return ValueLatticeElement::getOverdefined();
}

// Figure out the range of the LHS.  If that fails, we still apply the
// transfer rule on the full set since we may be able to locally infer
// interesting facts.
Optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB);
if (!LHSRes.hasValue())
  // More work to do before applying this transfer rule.
  return None;
const ConstantRange &LHSRange = LHSRes.getValue();

const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();

// NOTE: We're currently limited by the set of operations that ConstantRange
// can evaluate symbolically.  Enhancing that set will allows us to analyze
// more definitions.
return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
                                                     ResultBitWidth));
933}

935Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
  Instruction *I, BasicBlock *BB,
  std::function<ConstantRange(const ConstantRange &,
                              const ConstantRange &)> OpFn) {
// Figure out the ranges of the operands.  If that fails, use a
// conservative range, but apply the transfer rule anyways.  This
// lets us pick up facts from expressions like "and i32 (call i32
// @foo()), 32"
Optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB);
Optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB);
if (!LHSRes.hasValue() || !RHSRes.hasValue())
  // More work to do before applying this transfer rule.
  return None;

const ConstantRange &LHSRange = LHSRes.getValue();
const ConstantRange &RHSRange = RHSRes.getValue();
return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange));
952}

954Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOp(
  BinaryOperator *BO, BasicBlock *BB) {
assert(BO->getOperand(0)->getType()->isSized() &&(static_cast <bool> (BO->getOperand(0)->getType()
->isSized() && "all operands to binary operators are sized"
) ? void (0) : __assert_fail ("BO->getOperand(0)->getType()->isSized() && \"all operands to binary operators are sized\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 957, __extension__ __PRETTY_FUNCTION__
))
       "all operands to binary operators are sized")(static_cast <bool> (BO->getOperand(0)->getType()
->isSized() && "all operands to binary operators are sized"
) ? void (0) : __assert_fail ("BO->getOperand(0)->getType()->isSized() && \"all operands to binary operators are sized\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 957, __extension__ __PRETTY_FUNCTION__
));
if (BO->getOpcode() == Instruction::Xor) {
  // Xor is the only operation not supported by ConstantRange::binaryOp().
  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined (unknown binary operator).\n"
; } } while (false)
                    << "' - overdefined (unknown binary operator).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined (unknown binary operator).\n"
; } } while (false);
  return ValueLatticeElement::getOverdefined();
}

if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
  unsigned NoWrapKind = 0;
  if (OBO->hasNoUnsignedWrap())
    NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap;
  if (OBO->hasNoSignedWrap())
    NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap;

  return solveBlockValueBinaryOpImpl(
      BO, BB,
      [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) {
        return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind);
      });
}

return solveBlockValueBinaryOpImpl(
    BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
      return CR1.binaryOp(BO->getOpcode(), CR2);
    });
983}

985Optional<ValueLatticeElement>
986LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,
                                                  BasicBlock *BB) {
return solveBlockValueBinaryOpImpl(
    WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
      return CR1.binaryOp(WO->getBinaryOp(), CR2);
    });
992}

994Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueIntrinsic(
  IntrinsicInst *II, BasicBlock *BB) {
if (!ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
  LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - unknown intrinsic.\n"; } } while
 (false)
                    << "' - unknown intrinsic.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - unknown intrinsic.\n"; } } while
 (false);
  return getFromRangeMetadata(II);
}

SmallVector<ConstantRange, 2> OpRanges;
for (Value *Op : II->args()) {
  Optional<ConstantRange> Range = getRangeFor(Op, II, BB);
  if (!Range)
    return None;
  OpRanges.push_back(*Range);
}

return ValueLatticeElement::getRange(
    ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges));
1012}

1014Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueExtractValue(
  ExtractValueInst *EVI, BasicBlock *BB) {
if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
  if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
    return solveBlockValueOverflowIntrinsic(WO, BB);

// Handle extractvalue of insertvalue to allow further simplification
// based on replaced with.overflow intrinsics.
if (Value *V = SimplifyExtractValueInst(
        EVI->getAggregateOperand(), EVI->getIndices(),
        EVI->getModule()->getDataLayout()))
  return getBlockValue(V, BB, EVI);

LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined (unknown extractvalue).\n"
; } } while (false)
                  << "' - overdefined (unknown extractvalue).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << " compute BB '" <<
 BB->getName() << "' - overdefined (unknown extractvalue).\n"
; } } while (false);
return ValueLatticeElement::getOverdefined();
1030}

1032static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val,
                           ICmpInst::Predicate Pred) {
if (LHS == Val)
  return true;

// Handle range checking idiom produced by InstCombine. We will subtract the
// offset from the allowed range for RHS in this case.
const APInt *C;
if (match(LHS, m_Add(m_Specific(Val), m_APInt(C)))) {
  Offset = *C;
  return true;
}

// Handle the symmetric case. This appears in saturation patterns like
// (x == 16) ? 16 : (x + 1).
if (match(Val, m_Add(m_Specific(LHS), m_APInt(C)))) {
  Offset = -*C;
  return true;
}

// If (x | y) < C, then (x < C) && (y < C).
if (match(LHS, m_c_Or(m_Specific(Val), m_Value())) &&
    (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE))
  return true;

// If (x & y) > C, then (x > C) && (y > C).
if (match(LHS, m_c_And(m_Specific(Val), m_Value())) &&
    (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE))
  return true;

return false;
1063}

1065/// Get value range for a "(Val + Offset) Pred RHS" condition.
1066static ValueLatticeElement getValueFromSimpleICmpCondition(
  CmpInst::Predicate Pred, Value *RHS, const APInt &Offset) {
ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
                       /*isFullSet=*/true);
if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
  RHSRange = ConstantRange(CI->getValue());
else if (Instruction *I = dyn_cast<Instruction>(RHS))
  if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
    RHSRange = getConstantRangeFromMetadata(*Ranges);

ConstantRange TrueValues =
    ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
return ValueLatticeElement::getRange(TrueValues.subtract(Offset));
1079}

1081static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
                                                   bool isTrueDest) {
Value *LHS = ICI->getOperand(0);
Value *RHS = ICI->getOperand(1);

// Get the predicate that must hold along the considered edge.
CmpInst::Predicate EdgePred =
    isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();

if (isa<Constant>(RHS)) {
  if (ICI->isEquality() && LHS == Val) {
    if (EdgePred == ICmpInst::ICMP_EQ)
      return ValueLatticeElement::get(cast<Constant>(RHS));
    else if (!isa<UndefValue>(RHS))
      return ValueLatticeElement::getNot(cast<Constant>(RHS));
  }
}

Type *Ty = Val->getType();
if (!Ty->isIntegerTy())
  return ValueLatticeElement::getOverdefined();

unsigned BitWidth = Ty->getScalarSizeInBits();
APInt Offset(BitWidth, 0);
if (matchICmpOperand(Offset, LHS, Val, EdgePred))
  return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset);

CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(EdgePred);
if (matchICmpOperand(Offset, RHS, Val, SwappedPred))
  return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset);

const APInt *Mask, *C;
if (match(LHS, m_And(m_Specific(Val), m_APInt(Mask))) &&
    match(RHS, m_APInt(C))) {
  // If (Val & Mask) == C then all the masked bits are known and we can
  // compute a value range based on that.
  if (EdgePred == ICmpInst::ICMP_EQ) {
    KnownBits Known;
    Known.Zero = ~*C & *Mask;
    Known.One = *C & *Mask;
    return ValueLatticeElement::getRange(
        ConstantRange::fromKnownBits(Known, /*IsSigned*/ false));
  }
  // If (Val & Mask) != 0 then the value must be larger than the lowest set
  // bit of Mask.
  if (EdgePred == ICmpInst::ICMP_NE && !Mask->isZero() && C->isZero()) {
    return ValueLatticeElement::getRange(ConstantRange::getNonEmpty(
        APInt::getOneBitSet(BitWidth, Mask->countTrailingZeros()),
        APInt::getZero(BitWidth)));
  }
}

// If (X urem Modulus) >= C, then X >= C.
// If trunc X >= C, then X >= C.
// TODO: An upper bound could be computed as well.
if (match(LHS, m_CombineOr(m_URem(m_Specific(Val), m_Value()),
                           m_Trunc(m_Specific(Val)))) &&
    match(RHS, m_APInt(C))) {
  // Use the icmp region so we don't have to deal with different predicates.
  ConstantRange CR = ConstantRange::makeExactICmpRegion(EdgePred, *C);
  if (!CR.isEmptySet())
    return ValueLatticeElement::getRange(ConstantRange::getNonEmpty(
        CR.getUnsignedMin().zextOrSelf(BitWidth), APInt(BitWidth, 0)));
}

return ValueLatticeElement::getOverdefined();
1147}

1149// Handle conditions of the form
1150// extractvalue(op.with.overflow(%x, C), 1).
1151static ValueLatticeElement getValueFromOverflowCondition(
  Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
// TODO: This only works with a constant RHS for now. We could also compute
// the range of the RHS, but this doesn't fit into the current structure of
// the edge value calculation.
const APInt *C;
if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C)))
  return ValueLatticeElement::getOverdefined();

// Calculate the possible values of %x for which no overflow occurs.
ConstantRange NWR = ConstantRange::makeExactNoWrapRegion(
    WO->getBinaryOp(), *C, WO->getNoWrapKind());

// If overflow is false, %x is constrained to NWR. If overflow is true, %x is
// constrained to it's inverse (all values that might cause overflow).
if (IsTrueDest)
  NWR = NWR.inverse();
return ValueLatticeElement::getRange(NWR);
1169}

1171static Optional<ValueLatticeElement>
1172getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
                        bool isRevisit,
                        SmallDenseMap<Value *, ValueLatticeElement> &Visited,
                        SmallVectorImpl<Value *> &Worklist) {
if (!isRevisit) {
  if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
    return getValueFromICmpCondition(Val, ICI, isTrueDest);

  if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
    if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
      if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
        return getValueFromOverflowCondition(Val, WO, isTrueDest);
}

Value *L, *R;
bool IsAnd;
if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R))))
  IsAnd = true;
else if (match(Cond, m_LogicalOr(m_Value(L), m_Value(R))))
  IsAnd = false;
else
  return ValueLatticeElement::getOverdefined();

auto LV = Visited.find(L);
auto RV = Visited.find(R);

// if (L && R) -> intersect L and R
// if (!(L || R)) -> intersect L and R
// if (L || R) -> union L and R
// if (!(L && R)) -> union L and R
if ((isTrueDest ^ IsAnd) && (LV != Visited.end())) {
  ValueLatticeElement V = LV->second;
  if (V.isOverdefined())
    return V;
  if (RV != Visited.end()) {
    V.mergeIn(RV->second);
    return V;
  }
}

if (LV == Visited.end() || RV == Visited.end()) {
  assert(!isRevisit)(static_cast <bool> (!isRevisit) ? void (0) : __assert_fail
 ("!isRevisit", "llvm/lib/Analysis/LazyValueInfo.cpp", 1213, __extension__
 __PRETTY_FUNCTION__));
  if (LV == Visited.end())
    Worklist.push_back(L);
  if (RV == Visited.end())
    Worklist.push_back(R);
  return None;
}

return intersect(LV->second, RV->second);
1222}

1224ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
                                        bool isTrueDest) {
assert(Cond && "precondition")(static_cast <bool> (Cond && "precondition") ? void
 (0) : __assert_fail ("Cond && \"precondition\"", "llvm/lib/Analysis/LazyValueInfo.cpp"
, 1226, __extension__ __PRETTY_FUNCTION__));
SmallDenseMap<Value*, ValueLatticeElement> Visited;
SmallVector<Value *> Worklist;

Worklist.push_back(Cond);
do {
  Value *CurrentCond = Worklist.back();
  // Insert an Overdefined placeholder into the set to prevent
  // infinite recursion if there exists IRs that use not
  // dominated by its def as in this example:
  //   "%tmp3 = or i1 undef, %tmp4"
  //   "%tmp4 = or i1 undef, %tmp3"
  auto Iter =
      Visited.try_emplace(CurrentCond, ValueLatticeElement::getOverdefined());
  bool isRevisit = !Iter.second;
  Optional<ValueLatticeElement> Result = getValueFromConditionImpl(
      Val, CurrentCond, isTrueDest, isRevisit, Visited, Worklist);
  if (Result) {
    Visited[CurrentCond] = *Result;
    Worklist.pop_back();
  }
} while (!Worklist.empty());

auto Result = Visited.find(Cond);
assert(Result != Visited.end())(static_cast <bool> (Result != Visited.end()) ? void (0
) : __assert_fail ("Result != Visited.end()", "llvm/lib/Analysis/LazyValueInfo.cpp"
, 1250, __extension__ __PRETTY_FUNCTION__));
return Result->second;
1252}

1254// Return true if Usr has Op as an operand, otherwise false.
1255static bool usesOperand(User *Usr, Value *Op) {
return is_contained(Usr->operands(), Op);
1257}

1259// Return true if the instruction type of Val is supported by
1260// constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.
1261// Call this before calling constantFoldUser() to find out if it's even worth
1262// attempting to call it.
1263static bool isOperationFoldable(User *Usr) {
return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);
1265}

1267// Check if Usr can be simplified to an integer constant when the value of one
1268// of its operands Op is an integer constant OpConstVal. If so, return it as an
1269// lattice value range with a single element or otherwise return an overdefined
1270// lattice value.
1271static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
                                          const APInt &OpConstVal,
                                          const DataLayout &DL) {
assert(isOperationFoldable(Usr) && "Precondition")(static_cast <bool> (isOperationFoldable(Usr) &&
 "Precondition") ? void (0) : __assert_fail ("isOperationFoldable(Usr) && \"Precondition\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1274, __extension__ __PRETTY_FUNCTION__
));
Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
// Check if Usr can be simplified to a constant.
if (auto *CI = dyn_cast<CastInst>(Usr)) {
  assert(CI->getOperand(0) == Op && "Operand 0 isn't Op")(static_cast <bool> (CI->getOperand(0) == Op &&
 "Operand 0 isn't Op") ? void (0) : __assert_fail ("CI->getOperand(0) == Op && \"Operand 0 isn't Op\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1278, __extension__ __PRETTY_FUNCTION__
));
  if (auto *C = dyn_cast_or_null<ConstantInt>(
          SimplifyCastInst(CI->getOpcode(), OpConst,
                           CI->getDestTy(), DL))) {
    return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
  }
} else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
  bool Op0Match = BO->getOperand(0) == Op;
  bool Op1Match = BO->getOperand(1) == Op;
  assert((Op0Match || Op1Match) &&(static_cast <bool> ((Op0Match || Op1Match) && "Operand 0 nor Operand 1 isn't a match"
) ? void (0) : __assert_fail ("(Op0Match || Op1Match) && \"Operand 0 nor Operand 1 isn't a match\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1288, __extension__ __PRETTY_FUNCTION__
))
         "Operand 0 nor Operand 1 isn't a match")(static_cast <bool> ((Op0Match || Op1Match) && "Operand 0 nor Operand 1 isn't a match"
) ? void (0) : __assert_fail ("(Op0Match || Op1Match) && \"Operand 0 nor Operand 1 isn't a match\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1288, __extension__ __PRETTY_FUNCTION__
));
  Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
  Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
  if (auto *C = dyn_cast_or_null<ConstantInt>(
          SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
    return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
  }
} else if (isa<FreezeInst>(Usr)) {
  assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op")(static_cast <bool> (cast<FreezeInst>(Usr)->getOperand
(0) == Op && "Operand 0 isn't Op") ? void (0) : __assert_fail
 ("cast<FreezeInst>(Usr)->getOperand(0) == Op && \"Operand 0 isn't Op\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1296, __extension__ __PRETTY_FUNCTION__
));
  return ValueLatticeElement::getRange(ConstantRange(OpConstVal));
}
return ValueLatticeElement::getOverdefined();
1300}

1302/// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1303/// Val is not constrained on the edge.  Result is unspecified if return value
1304/// is false.
1305static Optional<ValueLatticeElement> getEdgeValueLocal(Value *Val,
                                                     BasicBlock *BBFrom,
                                                     BasicBlock *BBTo) {
// TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
// know that v != 0.
if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
  // If this is a conditional branch and only one successor goes to BBTo, then
  // we may be able to infer something from the condition.
  if (BI->isConditional() &&
      BI->getSuccessor(0) != BI->getSuccessor(1)) {
    bool isTrueDest = BI->getSuccessor(0) == BBTo;
    assert(BI->getSuccessor(!isTrueDest) == BBTo &&(static_cast <bool> (BI->getSuccessor(!isTrueDest) ==
 BBTo && "BBTo isn't a successor of BBFrom") ? void (
0) : __assert_fail ("BI->getSuccessor(!isTrueDest) == BBTo && \"BBTo isn't a successor of BBFrom\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1317, __extension__ __PRETTY_FUNCTION__
))
           "BBTo isn't a successor of BBFrom")(static_cast <bool> (BI->getSuccessor(!isTrueDest) ==
 BBTo && "BBTo isn't a successor of BBFrom") ? void (
0) : __assert_fail ("BI->getSuccessor(!isTrueDest) == BBTo && \"BBTo isn't a successor of BBFrom\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1317, __extension__ __PRETTY_FUNCTION__
));
    Value *Condition = BI->getCondition();

    // If V is the condition of the branch itself, then we know exactly what
    // it is.
    if (Condition == Val)
      return ValueLatticeElement::get(ConstantInt::get(
                            Type::getInt1Ty(Val->getContext()), isTrueDest));

    // If the condition of the branch is an equality comparison, we may be
    // able to infer the value.
    ValueLatticeElement Result = getValueFromCondition(Val, Condition,
                                                       isTrueDest);
    if (!Result.isOverdefined())
      return Result;

    if (User *Usr = dyn_cast<User>(Val)) {
      assert(Result.isOverdefined() && "Result isn't overdefined")(static_cast <bool> (Result.isOverdefined() && "Result isn't overdefined"
) ? void (0) : __assert_fail ("Result.isOverdefined() && \"Result isn't overdefined\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1334, __extension__ __PRETTY_FUNCTION__
));
      // Check with isOperationFoldable() first to avoid linearly iterating
      // over the operands unnecessarily which can be expensive for
      // instructions with many operands.
      if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
        const DataLayout &DL = BBTo->getModule()->getDataLayout();
        if (usesOperand(Usr, Condition)) {
          // If Val has Condition as an operand and Val can be folded into a
          // constant with either Condition == true or Condition == false,
          // propagate the constant.
          // eg.
          //   ; %Val is true on the edge to %then.
          //   %Val = and i1 %Condition, true.
          //   br %Condition, label %then, label %else
          APInt ConditionVal(1, isTrueDest ? 1 : 0);
          Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
        } else {
          // If one of Val's operand has an inferred value, we may be able to
          // infer the value of Val.
          // eg.
          //    ; %Val is 94 on the edge to %then.
          //    %Val = add i8 %Op, 1
          //    %Condition = icmp eq i8 %Op, 93
          //    br i1 %Condition, label %then, label %else
          for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
            Value *Op = Usr->getOperand(i);
            ValueLatticeElement OpLatticeVal =
                getValueFromCondition(Op, Condition, isTrueDest);
            if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
              Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
              break;
            }
          }
        }
      }
    }
    if (!Result.isOverdefined())
      return Result;
  }
}

// If the edge was formed by a switch on the value, then we may know exactly
// what it is.
if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
  Value *Condition = SI->getCondition();
  if (!isa<IntegerType>(Val->getType()))
    return None;
  bool ValUsesConditionAndMayBeFoldable = false;
  if (Condition != Val) {
    // Check if Val has Condition as an operand.
    if (User *Usr = dyn_cast<User>(Val))
      ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
          usesOperand(Usr, Condition);
    if (!ValUsesConditionAndMayBeFoldable)
      return None;
  }
  assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&(static_cast <bool> ((Condition == Val || ValUsesConditionAndMayBeFoldable
) && "Condition != Val nor Val doesn't use Condition"
) ? void (0) : __assert_fail ("(Condition == Val || ValUsesConditionAndMayBeFoldable) && \"Condition != Val nor Val doesn't use Condition\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1391, __extension__ __PRETTY_FUNCTION__
))
         "Condition != Val nor Val doesn't use Condition")(static_cast <bool> ((Condition == Val || ValUsesConditionAndMayBeFoldable
) && "Condition != Val nor Val doesn't use Condition"
) ? void (0) : __assert_fail ("(Condition == Val || ValUsesConditionAndMayBeFoldable) && \"Condition != Val nor Val doesn't use Condition\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1391, __extension__ __PRETTY_FUNCTION__
));

  bool DefaultCase = SI->getDefaultDest() == BBTo;
  unsigned BitWidth = Val->getType()->getIntegerBitWidth();
  ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);

  for (auto Case : SI->cases()) {
    APInt CaseValue = Case.getCaseValue()->getValue();
    ConstantRange EdgeVal(CaseValue);
    if (ValUsesConditionAndMayBeFoldable) {
      User *Usr = cast<User>(Val);
      const DataLayout &DL = BBTo->getModule()->getDataLayout();
      ValueLatticeElement EdgeLatticeVal =
          constantFoldUser(Usr, Condition, CaseValue, DL);
      if (EdgeLatticeVal.isOverdefined())
        return None;
      EdgeVal = EdgeLatticeVal.getConstantRange();
    }
    if (DefaultCase) {
      // It is possible that the default destination is the destination of
      // some cases. We cannot perform difference for those cases.
      // We know Condition != CaseValue in BBTo.  In some cases we can use
      // this to infer Val == f(Condition) is != f(CaseValue).  For now, we
      // only do this when f is identity (i.e. Val == Condition), but we
      // should be able to do this for any injective f.
      if (Case.getCaseSuccessor() != BBTo && Condition == Val)
        EdgesVals = EdgesVals.difference(EdgeVal);
    } else if (Case.getCaseSuccessor() == BBTo)
      EdgesVals = EdgesVals.unionWith(EdgeVal);
  }
  return ValueLatticeElement::getRange(std::move(EdgesVals));
}
return None;
1424}

1426/// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1427/// the basic block if the edge does not constrain Val.
1428Optional<ValueLatticeElement> LazyValueInfoImpl::getEdgeValue(
  Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, Instruction *CxtI) {
// If already a constant, there is nothing to compute.
if (Constant *VC = dyn_cast<Constant>(Val))
  return ValueLatticeElement::get(VC);

ValueLatticeElement LocalResult = getEdgeValueLocal(Val, BBFrom, BBTo)
    .getValueOr(ValueLatticeElement::getOverdefined());
if (hasSingleValue(LocalResult))
  // Can't get any more precise here
  return LocalResult;

Optional<ValueLatticeElement> OptInBlock =
    getBlockValue(Val, BBFrom, BBFrom->getTerminator());
if (!OptInBlock)
  return None;
ValueLatticeElement &InBlock = *OptInBlock;

// We can use the context instruction (generically the ultimate instruction
// the calling pass is trying to simplify) here, even though the result of
// this function is generally cached when called from the solve* functions
// (and that cached result might be used with queries using a different
// context instruction), because when this function is called from the solve*
// functions, the context instruction is not provided. When called from
// LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
// but then the result is not cached.
intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);

return intersect(LocalResult, InBlock);
1457}

1459ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
                                                     Instruction *CxtI) {
LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "LVI Getting block end value "
 << *V << " at '" << BB->getName() <<
 "'\n"; } } while (false)
                  << BB->getName() << "'\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "LVI Getting block end value "
 << *V << " at '" << BB->getName() <<
 "'\n"; } } while (false);

assert(BlockValueStack.empty() && BlockValueSet.empty())(static_cast <bool> (BlockValueStack.empty() &&
 BlockValueSet.empty()) ? void (0) : __assert_fail ("BlockValueStack.empty() && BlockValueSet.empty()"
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1464, __extension__ __PRETTY_FUNCTION__
));
Optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI);
if (!OptResult) {
  solve();
  OptResult = getBlockValue(V, BB, CxtI);
  assert(OptResult && "Value not available after solving")(static_cast <bool> (OptResult && "Value not available after solving"
) ? void (0) : __assert_fail ("OptResult && \"Value not available after solving\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1469, __extension__ __PRETTY_FUNCTION__
));
}

ValueLatticeElement Result = *OptResult;
LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "  Result = " <<
 Result << "\n"; } } while (false);
return Result;
1475}

1477ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "LVI Getting value " <<
 *V << " at '" << CxtI->getName() << "'\n"
; } } while (false)
                  << "'\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "LVI Getting value " <<
 *V << " at '" << CxtI->getName() << "'\n"
; } } while (false);

if (auto *C = dyn_cast<Constant>(V))
  return ValueLatticeElement::get(C);

ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
if (auto *I = dyn_cast<Instruction>(V))
  Result = getFromRangeMetadata(I);
intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);

LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "  Result = " <<
 Result << "\n"; } } while (false);
return Result;
1491}

1493ValueLatticeElement LazyValueInfoImpl::
1494getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
             Instruction *CxtI) {
LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "LVI Getting edge value "
 << *V << " from '" << FromBB->getName()
 << "' to '" << ToBB->getName() << "'\n"
; } } while (false)
                  << FromBB->getName() << "' to '" << ToBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "LVI Getting edge value "
 << *V << " from '" << FromBB->getName()
 << "' to '" << ToBB->getName() << "'\n"
; } } while (false)
                  << "'\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "LVI Getting edge value "
 << *V << " from '" << FromBB->getName()
 << "' to '" << ToBB->getName() << "'\n"
; } } while (false);

Optional<ValueLatticeElement> Result = getEdgeValue(V, FromBB, ToBB, CxtI);
if (!Result) {
  solve();
  Result = getEdgeValue(V, FromBB, ToBB, CxtI);
  assert(Result && "More work to do after problem solved?")(static_cast <bool> (Result && "More work to do after problem solved?"
) ? void (0) : __assert_fail ("Result && \"More work to do after problem solved?\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1504, __extension__ __PRETTY_FUNCTION__
));
}

LLVM_DEBUG(dbgs() << "  Result = " << *Result << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("lazy-value-info")) { dbgs() << "  Result = " <<
 *Result << "\n"; } } while (false);
return *Result;
1509}

1511void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
                                 BasicBlock *NewSucc) {
TheCache.threadEdgeImpl(OldSucc, NewSucc);
1514}

1516//===----------------------------------------------------------------------===//
1517//                            LazyValueInfo Impl
1518//===----------------------------------------------------------------------===//

1520/// This lazily constructs the LazyValueInfoImpl.
1521static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
                                const Module *M) {
if (!PImpl) {
  assert(M && "getCache() called with a null Module")(static_cast <bool> (M && "getCache() called with a null Module"
) ? void (0) : __assert_fail ("M && \"getCache() called with a null Module\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1524, __extension__ __PRETTY_FUNCTION__
));
  const DataLayout &DL = M->getDataLayout();
  Function *GuardDecl = M->getFunction(
      Intrinsic::getName(Intrinsic::experimental_guard));
  PImpl = new LazyValueInfoImpl(AC, DL, GuardDecl);
}
return *static_cast<LazyValueInfoImpl*>(PImpl);
1531}

1533bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);

if (Info.PImpl)
  getImpl(Info.PImpl, Info.AC, F.getParent()).clear();

// Fully lazy.
return false;
1542}

1544void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<AssumptionCacheTracker>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
1548}

1550LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }

1552LazyValueInfo::~LazyValueInfo() { releaseMemory(); }

1554void LazyValueInfo::releaseMemory() {
// If the cache was allocated, free it.
if (PImpl) {
  delete &getImpl(PImpl, AC, nullptr);
  PImpl = nullptr;
}
1560}

1562bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
                             FunctionAnalysisManager::Invalidator &Inv) {
// We need to invalidate if we have either failed to preserve this analyses
// result directly or if any of its dependencies have been invalidated.
auto PAC = PA.getChecker<LazyValueAnalysis>();
if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()))
  return true;

return false;
1571}

1573void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }

1575LazyValueInfo LazyValueAnalysis::run(Function &F,
                                   FunctionAnalysisManager &FAM) {
auto &AC = FAM.getResult<AssumptionAnalysis>(F);
auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);

return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI);
1581}

1583/// Returns true if we can statically tell that this value will never be a
1584/// "useful" constant.  In practice, this means we've got something like an
1585/// alloca or a malloc call for which a comparison against a constant can
1586/// only be guarding dead code.  Note that we are potentially giving up some
1587/// precision in dead code (a constant result) in favour of avoiding a
1588/// expensive search for a easily answered common query.
1589static bool isKnownNonConstant(Value *V) {
V = V->stripPointerCasts();
// The return val of alloc cannot be a Constant.
if (isa<AllocaInst>(V))
  return true;
return false;
1595}

1597Constant *LazyValueInfo::getConstant(Value *V, Instruction *CxtI) {
// Bail out early if V is known not to be a Constant.
if (isKnownNonConstant(V))
  return nullptr;

BasicBlock *BB = CxtI->getParent();
ValueLatticeElement Result =
    getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI);

if (Result.isConstant())
  return Result.getConstant();
if (Result.isConstantRange()) {
  const ConstantRange &CR = Result.getConstantRange();
  if (const APInt *SingleVal = CR.getSingleElement())
    return ConstantInt::get(V->getContext(), *SingleVal);
}
return nullptr;
1614}

1616ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI,
                                            bool UndefAllowed) {
assert(V->getType()->isIntegerTy())(static_cast <bool> (V->getType()->isIntegerTy())
 ? void (0) : __assert_fail ("V->getType()->isIntegerTy()"
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1618, __extension__ __PRETTY_FUNCTION__
));
unsigned Width = V->getType()->getIntegerBitWidth();
BasicBlock *BB = CxtI->getParent();
ValueLatticeElement Result =
    getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI);
if (Result.isUnknown())
  return ConstantRange::getEmpty(Width);
if (Result.isConstantRange(UndefAllowed))
  return Result.getConstantRange(UndefAllowed);
// We represent ConstantInt constants as constant ranges but other kinds
// of integer constants, i.e. ConstantExpr will be tagged as constants
assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&(static_cast <bool> (!(Result.isConstant() && isa
<ConstantInt>(Result.getConstant())) && "ConstantInt value must be represented as constantrange"
) ? void (0) : __assert_fail ("!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) && \"ConstantInt value must be represented as constantrange\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1630, __extension__ __PRETTY_FUNCTION__
))
       "ConstantInt value must be represented as constantrange")(static_cast <bool> (!(Result.isConstant() && isa
<ConstantInt>(Result.getConstant())) && "ConstantInt value must be represented as constantrange"
) ? void (0) : __assert_fail ("!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) && \"ConstantInt value must be represented as constantrange\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1630, __extension__ __PRETTY_FUNCTION__
));
return ConstantRange::getFull(Width);
1632}

1634/// Determine whether the specified value is known to be a
1635/// constant on the specified edge. Return null if not.
1636Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
                                         BasicBlock *ToBB,
                                         Instruction *CxtI) {
Module *M = FromBB->getModule();
ValueLatticeElement Result =
    getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);

if (Result.isConstant())
  return Result.getConstant();
if (Result.isConstantRange()) {
  const ConstantRange &CR = Result.getConstantRange();
  if (const APInt *SingleVal = CR.getSingleElement())
    return ConstantInt::get(V->getContext(), *SingleVal);
}
return nullptr;
1651}

1653ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
                                                  BasicBlock *FromBB,
                                                  BasicBlock *ToBB,
                                                  Instruction *CxtI) {
unsigned Width = V->getType()->getIntegerBitWidth();
Module *M = FromBB->getModule();
ValueLatticeElement Result =
    getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);

if (Result.isUnknown())
1
Assuming the condition is false→
2
←
Taking false branch→
  return ConstantRange::getEmpty(Width);
if (Result.isConstantRange())
3
←
Taking true branch→
  return Result.getConstantRange();
4
←
Calling implicit copy constructor for 'ConstantRange'→
5
←
Calling copy constructor for 'APInt'→
// We represent ConstantInt constants as constant ranges but other kinds
// of integer constants, i.e. ConstantExpr will be tagged as constants
assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&(static_cast <bool> (!(Result.isConstant() && isa
<ConstantInt>(Result.getConstant())) && "ConstantInt value must be represented as constantrange"
) ? void (0) : __assert_fail ("!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) && \"ConstantInt value must be represented as constantrange\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1669, __extension__ __PRETTY_FUNCTION__
))
       "ConstantInt value must be represented as constantrange")(static_cast <bool> (!(Result.isConstant() && isa
<ConstantInt>(Result.getConstant())) && "ConstantInt value must be represented as constantrange"
) ? void (0) : __assert_fail ("!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) && \"ConstantInt value must be represented as constantrange\""
, "llvm/lib/Analysis/LazyValueInfo.cpp", 1669, __extension__ __PRETTY_FUNCTION__
));
return ConstantRange::getFull(Width);
1671}

1673static LazyValueInfo::Tristate
1674getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
                 const DataLayout &DL, TargetLibraryInfo *TLI) {
// If we know the value is a constant, evaluate the conditional.
Constant *Res = nullptr;
if (Val.isConstant()) {
  Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
  if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
    return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
  return LazyValueInfo::Unknown;
}

if (Val.isConstantRange()) {
  ConstantInt *CI = dyn_cast<ConstantInt>(C);
  if (!CI) return LazyValueInfo::Unknown;

  const ConstantRange &CR = Val.getConstantRange();
  if (Pred == ICmpInst::ICMP_EQ) {
    if (!CR.contains(CI->getValue()))
      return LazyValueInfo::False;

    if (CR.isSingleElement())
      return LazyValueInfo::True;
  } else if (Pred == ICmpInst::ICMP_NE) {
    if (!CR.contains(CI->getValue()))
      return LazyValueInfo::True;

    if (CR.isSingleElement())
      return LazyValueInfo::False;
  } else {
    // Handle more complex predicates.
    ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
        (ICmpInst::Predicate)Pred, CI->getValue());
    if (TrueValues.contains(CR))
      return LazyValueInfo::True;
    if (TrueValues.inverse().contains(CR))
      return LazyValueInfo::False;
  }
  return LazyValueInfo::Unknown;
}

if (Val.isNotConstant()) {
  // If this is an equality comparison, we can try to fold it knowing that
  // "V != C1".
  if (Pred == ICmpInst::ICMP_EQ) {
    // !C1 == C -> false iff C1 == C.
    Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
                                          Val.getNotConstant(), C, DL,
                                          TLI);
    if (Res->isNullValue())
      return LazyValueInfo::False;
  } else if (Pred == ICmpInst::ICMP_NE) {
    // !C1 != C -> true iff C1 == C.
    Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
                                          Val.getNotConstant(), C, DL,
                                          TLI);
    if (Res->isNullValue())
      return LazyValueInfo::True;
  }
  return LazyValueInfo::Unknown;
}

return LazyValueInfo::Unknown;
1736}

1738/// Determine whether the specified value comparison with a constant is known to
1739/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1740LazyValueInfo::Tristate
1741LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
                                BasicBlock *FromBB, BasicBlock *ToBB,
                                Instruction *CxtI) {
Module *M = FromBB->getModule();
ValueLatticeElement Result =
    getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);

return getPredicateResult(Pred, C, Result, M->getDataLayout(), TLI);
1749}

1751LazyValueInfo::Tristate
1752LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
                            Instruction *CxtI, bool UseBlockValue) {
// Is or is not NonNull are common predicates being queried. If
// isKnownNonZero can tell us the result of the predicate, we can
// return it quickly. But this is only a fastpath, and falling
// through would still be correct.
Module *M = CxtI->getModule();
const DataLayout &DL = M->getDataLayout();
if (V->getType()->isPointerTy() && C->isNullValue() &&
    isKnownNonZero(V->stripPointerCastsSameRepresentation(), DL)) {
  if (Pred == ICmpInst::ICMP_EQ)
    return LazyValueInfo::False;
  else if (Pred == ICmpInst::ICMP_NE)
    return LazyValueInfo::True;
}

ValueLatticeElement Result = UseBlockValue
    ? getImpl(PImpl, AC, M).getValueInBlock(V, CxtI->getParent(), CxtI)
    : getImpl(PImpl, AC, M).getValueAt(V, CxtI);
Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
if (Ret != Unknown)
  return Ret;

// Note: The following bit of code is somewhat distinct from the rest of LVI;
// LVI as a whole tries to compute a lattice value which is conservatively
// correct at a given location.  In this case, we have a predicate which we
// weren't able to prove about the merged result, and we're pushing that
// predicate back along each incoming edge to see if we can prove it
// separately for each input.  As a motivating example, consider:
// bb1:
//   %v1 = ... ; constantrange<1, 5>
//   br label %merge
// bb2:
//   %v2 = ... ; constantrange<10, 20>
//   br label %merge
// merge:
//   %phi = phi [%v1, %v2] ; constantrange<1,20>
//   %pred = icmp eq i32 %phi, 8
// We can't tell from the lattice value for '%phi' that '%pred' is false
// along each path, but by checking the predicate over each input separately,
// we can.
// We limit the search to one step backwards from the current BB and value.
// We could consider extending this to search further backwards through the
// CFG and/or value graph, but there are non-obvious compile time vs quality
// tradeoffs.
BasicBlock *BB = CxtI->getParent();

// Function entry or an unreachable block.  Bail to avoid confusing
// analysis below.
pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
if (PI == PE)
  return Unknown;

// If V is a PHI node in the same block as the context, we need to ask
// questions about the predicate as applied to the incoming value along
// each edge. This is useful for eliminating cases where the predicate is
// known along all incoming edges.
if (auto *PHI = dyn_cast<PHINode>(V))
  if (PHI->getParent() == BB) {
    Tristate Baseline = Unknown;
    for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
      Value *Incoming = PHI->getIncomingValue(i);
      BasicBlock *PredBB = PHI->getIncomingBlock(i);
      // Note that PredBB may be BB itself.
      Tristate Result =
          getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, CxtI);

      // Keep going as long as we've seen a consistent known result for
      // all inputs.
      Baseline = (i == 0) ? Result /* First iteration */
                          : (Baseline == Result ? Baseline
                                                : Unknown); /* All others */
      if (Baseline == Unknown)
        break;
    }
    if (Baseline != Unknown)
      return Baseline;
  }

// For a comparison where the V is outside this block, it's possible
// that we've branched on it before. Look to see if the value is known
// on all incoming edges.
if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB) {
  // For predecessor edge, determine if the comparison is true or false
  // on that edge. If they're all true or all false, we can conclude
  // the value of the comparison in this block.
  Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
  if (Baseline != Unknown) {
    // Check that all remaining incoming values match the first one.
    while (++PI != PE) {
      Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
      if (Ret != Baseline)
        break;
    }
    // If we terminated early, then one of the values didn't match.
    if (PI == PE) {
      return Baseline;
    }
  }
}

return Unknown;
1854}

1856LazyValueInfo::Tristate LazyValueInfo::getPredicateAt(unsigned P, Value *LHS,
                                                    Value *RHS,
                                                    Instruction *CxtI,
                                                    bool UseBlockValue) {
CmpInst::Predicate Pred = (CmpInst::Predicate)P;

if (auto *C = dyn_cast<Constant>(RHS))
  return getPredicateAt(P, LHS, C, CxtI, UseBlockValue);
if (auto *C = dyn_cast<Constant>(LHS))
  return getPredicateAt(CmpInst::getSwappedPredicate(Pred), RHS, C, CxtI,
                        UseBlockValue);

// Got two non-Constant values. While we could handle them somewhat,
// by getting their constant ranges, and applying ConstantRange::icmp(),
// so far it did not appear to be profitable.
return LazyValueInfo::Unknown;
1872}

1874void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
                             BasicBlock *NewSucc) {
if (PImpl) {
  getImpl(PImpl, AC, PredBB->getModule())
      .threadEdge(PredBB, OldSucc, NewSucc);
}
1880}

1882void LazyValueInfo::eraseBlock(BasicBlock *BB) {
if (PImpl) {
  getImpl(PImpl, AC, BB->getModule()).eraseBlock(BB);
}
1886}

1888void LazyValueInfo::clear(const Module *M) {
if (PImpl) {
  getImpl(PImpl, AC, M).clear();
}
1892}

1894void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
if (PImpl) {
  getImpl(PImpl, AC, F.getParent()).printLVI(F, DTree, OS);
}
1898}

1900// Print the LVI for the function arguments at the start of each basic block.
1901void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
  const BasicBlock *BB, formatted_raw_ostream &OS) {
// Find if there are latticevalues defined for arguments of the function.
auto *F = BB->getParent();
for (auto &Arg : F->args()) {
  ValueLatticeElement Result = LVIImpl->getValueInBlock(
      const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
  if (Result.isUnknown())
    continue;
  OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
}
1912}

1914// This function prints the LVI analysis for the instruction I at the beginning
1915// of various basic blocks. It relies on calculated values that are stored in
1916// the LazyValueInfoCache, and in the absence of cached values, recalculate the
1917// LazyValueInfo for `I`, and print that info.
1918void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
  const Instruction *I, formatted_raw_ostream &OS) {

auto *ParentBB = I->getParent();
SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
// We can generate (solve) LVI values only for blocks that are dominated by
// the I's parent. However, to avoid generating LVI for all dominating blocks,
// that contain redundant/uninteresting information, we print LVI for
// blocks that may use this LVI information (such as immediate successor
// blocks, and blocks that contain uses of `I`).
auto printResult = [&](const BasicBlock *BB) {
  if (!BlocksContainingLVI.insert(BB).second)
    return;
  ValueLatticeElement Result = LVIImpl->getValueInBlock(
      const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
    OS << "; LatticeVal for: '" << *I << "' in BB: '";
    BB->printAsOperand(OS, false);
    OS << "' is: " << Result << "\n";
};

printResult(ParentBB);
// Print the LVI analysis results for the immediate successor blocks, that
// are dominated by `ParentBB`.
for (auto *BBSucc : successors(ParentBB))
  if (DT.dominates(ParentBB, BBSucc))
    printResult(BBSucc);

// Print LVI in blocks where `I` is used.
for (auto *U : I->users())
  if (auto *UseI = dyn_cast<Instruction>(U))
    if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
      printResult(UseI->getParent());

1951}

1953namespace {
1954// Printer class for LazyValueInfo results.
1955class LazyValueInfoPrinter : public FunctionPass {
1956public:
static char ID; // Pass identification, replacement for typeid
LazyValueInfoPrinter() : FunctionPass(ID) {
  initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
}

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.setPreservesAll();
  AU.addRequired<LazyValueInfoWrapperPass>();
  AU.addRequired<DominatorTreeWrapperPass>();
}

// Get the mandatory dominator tree analysis and pass this in to the
// LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
bool runOnFunction(Function &F) override {
  dbgs() << "LVI for function '" << F.getName() << "':\n";
  auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
  auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  LVI.printLVI(F, DTree, dbgs());
  return false;
}
1977};
1978}

1980char LazyValueInfoPrinter::ID = 0;
1981INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",static void *initializeLazyValueInfoPrinterPassOnce(PassRegistry
 &Registry) {
              "Lazy Value Info Printer Pass", false, false)static void *initializeLazyValueInfoPrinterPassOnce(PassRegistry
 &Registry) {
1983INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)initializeLazyValueInfoWrapperPassPass(Registry);
1984INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",PassInfo *PI = new PassInfo( "Lazy Value Info Printer Pass", "print-lazy-value-info"
, &LazyValueInfoPrinter::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LazyValueInfoPrinter>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoPrinterPassFlag
; void llvm::initializeLazyValueInfoPrinterPass(PassRegistry &
Registry) { llvm::call_once(InitializeLazyValueInfoPrinterPassFlag
, initializeLazyValueInfoPrinterPassOnce, std::ref(Registry))
; }
              "Lazy Value Info Printer Pass", false, false)PassInfo *PI = new PassInfo( "Lazy Value Info Printer Pass", "print-lazy-value-info"
, &LazyValueInfoPrinter::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LazyValueInfoPrinter>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoPrinterPassFlag
; void llvm::initializeLazyValueInfoPrinterPass(PassRegistry &
Registry) { llvm::call_once(InitializeLazyValueInfoPrinterPassFlag
, initializeLazyValueInfoPrinterPassOnce, std::ref(Registry))
; }

←

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/IR/ConstantRange.h

→

1	//===- ConstantRange.h - Represent a range ----------------------- 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	// Represent a range of possible values that may occur when the program is run
10	// for an integral value. This keeps track of a lower and upper bound for the
11	// constant, which MAY wrap around the end of the numeric range. To do this, it
12	// keeps track of a [lower, upper) bound, which specifies an interval just like
13	// STL iterators. When used with boolean values, the following are important
14	// ranges: :
15	//
16	// [F, F) = {} = Empty set
17	// [T, F) = {T}
18	// [F, T) = {F}
19	// [T, T) = {F, T} = Full set
20	//
21	// The other integral ranges use min/max values for special range values. For
22	// example, for 8-bit types, it uses:
23	// [0, 0) = {} = Empty set
24	// [255, 255) = {0..255} = Full Set
25	//
26	// Note that ConstantRange can be used to represent either signed or
27	// unsigned ranges.
28	//
29	//===----------------------------------------------------------------------===//
30
31	#ifndef LLVM_IR_CONSTANTRANGE_H
32	#define LLVM_IR_CONSTANTRANGE_H
33
34	#include "llvm/ADT/APInt.h"
35	#include "llvm/IR/InstrTypes.h"
36	#include "llvm/IR/Instruction.h"
37	#include "llvm/Support/Compiler.h"
38	#include <cstdint>
39
40	namespace llvm {
41
42	class MDNode;
43	class raw_ostream;
44	struct KnownBits;
45
46	/// This class represents a range of values.
47	class LLVM_NODISCARD[[clang::warn_unused_result]] ConstantRange {
48	APInt Lower, Upper;
49
50	/// Create empty constant range with same bitwidth.
51	ConstantRange getEmpty() const {
52	return ConstantRange(getBitWidth(), false);
53	}
54
55	/// Create full constant range with same bitwidth.
56	ConstantRange getFull() const {
57	return ConstantRange(getBitWidth(), true);
58	}
59
60	public:
61	/// Initialize a full or empty set for the specified bit width.
62	explicit ConstantRange(uint32_t BitWidth, bool isFullSet);
63
64	/// Initialize a range to hold the single specified value.
65	ConstantRange(APInt Value);
66
67	/// Initialize a range of values explicitly. This will assert out if
68	/// Lower==Upper and Lower != Min or Max value for its type. It will also
69	/// assert out if the two APInt's are not the same bit width.
70	ConstantRange(APInt Lower, APInt Upper);
71
72	/// Create empty constant range with the given bit width.
73	static ConstantRange getEmpty(uint32_t BitWidth) {
74	return ConstantRange(BitWidth, false);
75	}
76
77	/// Create full constant range with the given bit width.
78	static ConstantRange getFull(uint32_t BitWidth) {
79	return ConstantRange(BitWidth, true);
80	}
81
82	/// Create non-empty constant range with the given bounds. If Lower and
83	/// Upper are the same, a full range is returned.
84	static ConstantRange getNonEmpty(APInt Lower, APInt Upper) {
85	if (Lower == Upper)
86	return getFull(Lower.getBitWidth());
87	return ConstantRange(std::move(Lower), std::move(Upper));
88	}
89
90	/// Initialize a range based on a known bits constraint. The IsSigned flag
91	/// indicates whether the constant range should not wrap in the signed or
92	/// unsigned domain.
93	static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned);
94
95	/// Produce the smallest range such that all values that may satisfy the given
96	/// predicate with any value contained within Other is contained in the
97	/// returned range. Formally, this returns a superset of
98	/// 'union over all y in Other . { x : icmp op x y is true }'. If the exact
99	/// answer is not representable as a ConstantRange, the return value will be a
100	/// proper superset of the above.
101	///
102	/// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4)
103	static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred,
104	const ConstantRange &Other);
105
106	/// Produce the largest range such that all values in the returned range
107	/// satisfy the given predicate with all values contained within Other.
108	/// Formally, this returns a subset of
109	/// 'intersection over all y in Other . { x : icmp op x y is true }'. If the
110	/// exact answer is not representable as a ConstantRange, the return value
111	/// will be a proper subset of the above.
112	///
113	/// Example: Pred = ult and Other = i8 [2, 5) returns [0, 2)
114	static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
115	const ConstantRange &Other);
116
117	/// Produce the exact range such that all values in the returned range satisfy
118	/// the given predicate with any value contained within Other. Formally, this
119	/// returns the exact answer when the superset of 'union over all y in Other
120	/// is exactly same as the subset of intersection over all y in Other.
121	/// { x : icmp op x y is true}'.
122	///
123	/// Example: Pred = ult and Other = i8 3 returns [0, 3)
124	static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred,
125	const APInt &Other);
126
127	/// Does the predicate \p Pred hold between ranges this and \p Other?
128	/// NOTE: false does not mean that inverse predicate holds!
129	bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const;
130
131	/// Return true iff CR1 ult CR2 is equivalent to CR1 slt CR2.
132	/// Does not depend on strictness/direction of the predicate.
133	static bool
134	areInsensitiveToSignednessOfICmpPredicate(const ConstantRange &CR1,
135	const ConstantRange &CR2);
136
137	/// Return true iff CR1 ult CR2 is equivalent to CR1 sge CR2.
138	/// Does not depend on strictness/direction of the predicate.
139	static bool
140	areInsensitiveToSignednessOfInvertedICmpPredicate(const ConstantRange &CR1,
141	const ConstantRange &CR2);
142
143	/// If the comparison between constant ranges this and Other
144	/// is insensitive to the signedness of the comparison predicate,
145	/// return a predicate equivalent to \p Pred, with flipped signedness
146	/// (i.e. unsigned instead of signed or vice versa), and maybe inverted,
147	/// otherwise returns CmpInst::Predicate::BAD_ICMP_PREDICATE.
148	static CmpInst::Predicate
149	getEquivalentPredWithFlippedSignedness(CmpInst::Predicate Pred,
150	const ConstantRange &CR1,
151	const ConstantRange &CR2);
152
153	/// Produce the largest range containing all X such that "X BinOp Y" is
154	/// guaranteed not to wrap (overflow) for all Y in Other. However, there may
155	/// be some Y in Other for which additional X not contained in the result
156	/// also do not overflow.
157	///
158	/// NoWrapKind must be one of OBO::NoUnsignedWrap or OBO::NoSignedWrap.
159	///
160	/// Examples:
161	/// typedef OverflowingBinaryOperator OBO;
162	/// #define MGNR makeGuaranteedNoWrapRegion
163	/// MGNR(Add, [i8 1, 2), OBO::NoSignedWrap) == [-128, 127)
164	/// MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap) == [0, -1)
165	/// MGNR(Add, [i8 0, 1), OBO::NoUnsignedWrap) == Full Set
166	/// MGNR(Add, [i8 -1, 6), OBO::NoSignedWrap) == [INT_MIN+1, INT_MAX-4)
167	/// MGNR(Sub, [i8 1, 2), OBO::NoSignedWrap) == [-127, 128)
168	/// MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap) == [1, 0)
169	static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
170	const ConstantRange &Other,
171	unsigned NoWrapKind);
172
173	/// Produce the range that contains X if and only if "X BinOp Other" does
174	/// not wrap.
175	static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp,
176	const APInt &Other,
177	unsigned NoWrapKind);
178
179	/// Returns true if ConstantRange calculations are supported for intrinsic
180	/// with \p IntrinsicID.
181	static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID);
182
183	/// Compute range of intrinsic result for the given operand ranges.
184	static ConstantRange intrinsic(Intrinsic::ID IntrinsicID,
185	ArrayRef<ConstantRange> Ops);
186
187	/// Set up \p Pred and \p RHS such that
188	/// ConstantRange::makeExactICmpRegion(Pred, RHS) == *this. Return true if
189	/// successful.
190	bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const;
191
192	/// Set up \p Pred, \p RHS and \p Offset such that (V + Offset) Pred RHS
193	/// is true iff V is in the range. Prefers using Offset == 0 if possible.
194	void
195	getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS, APInt &Offset) const;
196
197	/// Return the lower value for this range.
198	const APInt &getLower() const { return Lower; }
199
200	/// Return the upper value for this range.
201	const APInt &getUpper() const { return Upper; }
202
203	/// Get the bit width of this ConstantRange.
204	uint32_t getBitWidth() const { return Lower.getBitWidth(); }
205
206	/// Return true if this set contains all of the elements possible
207	/// for this data-type.
208	bool isFullSet() const;
209
210	/// Return true if this set contains no members.
211	bool isEmptySet() const;
212
213	/// Return true if this set wraps around the unsigned domain. Special cases:
214	/// * Empty set: Not wrapped.
215	/// * Full set: Not wrapped.
216	/// * [X, 0) == [X, Max]: Not wrapped.
217	bool isWrappedSet() const;
218
219	/// Return true if the exclusive upper bound wraps around the unsigned
220	/// domain. Special cases:
221	/// * Empty set: Not wrapped.
222	/// * Full set: Not wrapped.
223	/// * [X, 0): Wrapped.
224	bool isUpperWrapped() const;
225
226	/// Return true if this set wraps around the signed domain. Special cases:
227	/// * Empty set: Not wrapped.
228	/// * Full set: Not wrapped.
229	/// * [X, SignedMin) == [X, SignedMax]: Not wrapped.
230	bool isSignWrappedSet() const;
231
232	/// Return true if the (exclusive) upper bound wraps around the signed
233	/// domain. Special cases:
234	/// * Empty set: Not wrapped.
235	/// * Full set: Not wrapped.
236	/// * [X, SignedMin): Wrapped.
237	bool isUpperSignWrapped() const;
238
239	/// Return true if the specified value is in the set.
240	bool contains(const APInt &Val) const;
241
242	/// Return true if the other range is a subset of this one.
243	bool contains(const ConstantRange &CR) const;
244
245	/// If this set contains a single element, return it, otherwise return null.
246	const APInt *getSingleElement() const {
247	if (Upper == Lower + 1)
248	return &Lower;
249	return nullptr;
250	}
251
252	/// If this set contains all but a single element, return it, otherwise return
253	/// null.
254	const APInt *getSingleMissingElement() const {
255	if (Lower == Upper + 1)
256	return &Upper;
257	return nullptr;
258	}
259
260	/// Return true if this set contains exactly one member.
261	bool isSingleElement() const { return getSingleElement() != nullptr; }
262
263	/// Compare set size of this range with the range CR.
264	bool isSizeStrictlySmallerThan(const ConstantRange &CR) const;
265
266	/// Compare set size of this range with Value.
267	bool isSizeLargerThan(uint64_t MaxSize) const;
268
269	/// Return true if all values in this range are negative.
270	bool isAllNegative() const;
271
272	/// Return true if all values in this range are non-negative.
273	bool isAllNonNegative() const;
274
275	/// Return the largest unsigned value contained in the ConstantRange.
276	APInt getUnsignedMax() const;
277
278	/// Return the smallest unsigned value contained in the ConstantRange.
279	APInt getUnsignedMin() const;
280
281	/// Return the largest signed value contained in the ConstantRange.
282	APInt getSignedMax() const;
283
284	/// Return the smallest signed value contained in the ConstantRange.
285	APInt getSignedMin() const;
286
287	/// Return true if this range is equal to another range.
288	bool operator==(const ConstantRange &CR) const {
289	return Lower == CR.Lower && Upper == CR.Upper;
290	}
291	bool operator!=(const ConstantRange &CR) const {
292	return !operator==(CR);
293	}
294
295	/// Compute the maximal number of active bits needed to represent every value
296	/// in this range.
297	unsigned getActiveBits() const;
298
299	/// Compute the maximal number of bits needed to represent every value
300	/// in this signed range.
301	unsigned getMinSignedBits() const;
302
303	/// Subtract the specified constant from the endpoints of this constant range.
304	ConstantRange subtract(const APInt &CI) const;
305
306	/// Subtract the specified range from this range (aka relative complement of
307	/// the sets).
308	ConstantRange difference(const ConstantRange &CR) const;
309
310	/// If represented precisely, the result of some range operations may consist
311	/// of multiple disjoint ranges. As only a single range may be returned, any
312	/// range covering these disjoint ranges constitutes a valid result, but some
313	/// may be more useful than others depending on context. The preferred range
314	/// type specifies whether a range that is non-wrapping in the unsigned or
315	/// signed domain, or has the smallest size, is preferred. If a signedness is
316	/// preferred but all ranges are non-wrapping or all wrapping, then the
317	/// smallest set size is preferred. If there are multiple smallest sets, any
318	/// one of them may be returned.
319	enum PreferredRangeType { Smallest, Unsigned, Signed };
320
321	/// Return the range that results from the intersection of this range with
322	/// another range. If the intersection is disjoint, such that two results
323	/// are possible, the preferred range is determined by the PreferredRangeType.
324	ConstantRange intersectWith(const ConstantRange &CR,
325	PreferredRangeType Type = Smallest) const;
326
327	/// Return the range that results from the union of this range
328	/// with another range. The resultant range is guaranteed to include the
329	/// elements of both sets, but may contain more. For example, [3, 9) union
330	/// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included
331	/// in either set before.
332	ConstantRange unionWith(const ConstantRange &CR,
333	PreferredRangeType Type = Smallest) const;
334
335	/// Intersect the two ranges and return the result if it can be represented
336	/// exactly, otherwise return None.
337	Optional<ConstantRange> exactIntersectWith(const ConstantRange &CR) const;
338
339	/// Union the two ranges and return the result if it can be represented
340	/// exactly, otherwise return None.
341	Optional<ConstantRange> exactUnionWith(const ConstantRange &CR) const;
342
343	/// Return a new range representing the possible values resulting
344	/// from an application of the specified cast operator to this range. \p
345	/// BitWidth is the target bitwidth of the cast. For casts which don't
346	/// change bitwidth, it must be the same as the source bitwidth. For casts
347	/// which do change bitwidth, the bitwidth must be consistent with the
348	/// requested cast and source bitwidth.
349	ConstantRange castOp(Instruction::CastOps CastOp,
350	uint32_t BitWidth) const;
351
352	/// Return a new range in the specified integer type, which must
353	/// be strictly larger than the current type. The returned range will
354	/// correspond to the possible range of values if the source range had been
355	/// zero extended to BitWidth.
356	ConstantRange zeroExtend(uint32_t BitWidth) const;
357
358	/// Return a new range in the specified integer type, which must
359	/// be strictly larger than the current type. The returned range will
360	/// correspond to the possible range of values if the source range had been
361	/// sign extended to BitWidth.
362	ConstantRange signExtend(uint32_t BitWidth) const;
363
364	/// Return a new range in the specified integer type, which must be
365	/// strictly smaller than the current type. The returned range will
366	/// correspond to the possible range of values if the source range had been
367	/// truncated to the specified type.
368	ConstantRange truncate(uint32_t BitWidth) const;
369
370	/// Make this range have the bit width given by \p BitWidth. The
371	/// value is zero extended, truncated, or left alone to make it that width.
372	ConstantRange zextOrTrunc(uint32_t BitWidth) const;
373
374	/// Make this range have the bit width given by \p BitWidth. The
375	/// value is sign extended, truncated, or left alone to make it that width.
376	ConstantRange sextOrTrunc(uint32_t BitWidth) const;
377
378	/// Return a new range representing the possible values resulting
379	/// from an application of the specified binary operator to an left hand side
380	/// of this range and a right hand side of \p Other.
381	ConstantRange binaryOp(Instruction::BinaryOps BinOp,
382	const ConstantRange &Other) const;
383
384	/// Return a new range representing the possible values resulting
385	/// from an application of the specified overflowing binary operator to a
386	/// left hand side of this range and a right hand side of \p Other given
387	/// the provided knowledge about lack of wrapping \p NoWrapKind.
388	ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp,
389	const ConstantRange &Other,
390	unsigned NoWrapKind) const;
391
392	/// Return a new range representing the possible values resulting
393	/// from an addition of a value in this range and a value in \p Other.
394	ConstantRange add(const ConstantRange &Other) const;
395
396	/// Return a new range representing the possible values resulting
397	/// from an addition with wrap type \p NoWrapKind of a value in this
398	/// range and a value in \p Other.
399	/// If the result range is disjoint, the preferred range is determined by the
400	/// \p PreferredRangeType.
401	ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
402	PreferredRangeType RangeType = Smallest) const;
403
404	/// Return a new range representing the possible values resulting
405	/// from a subtraction of a value in this range and a value in \p Other.
406	ConstantRange sub(const ConstantRange &Other) const;
407
408	/// Return a new range representing the possible values resulting
409	/// from an subtraction with wrap type \p NoWrapKind of a value in this
410	/// range and a value in \p Other.
411	/// If the result range is disjoint, the preferred range is determined by the
412	/// \p PreferredRangeType.
413	ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
414	PreferredRangeType RangeType = Smallest) const;
415
416	/// Return a new range representing the possible values resulting
417	/// from a multiplication of a value in this range and a value in \p Other,
418	/// treating both this and \p Other as unsigned ranges.
419	ConstantRange multiply(const ConstantRange &Other) const;
420
421	/// Return range of possible values for a signed multiplication of this and
422	/// \p Other. However, if overflow is possible always return a full range
423	/// rather than trying to determine a more precise result.
424	ConstantRange smul_fast(const ConstantRange &Other) const;
425
426	/// Return a new range representing the possible values resulting
427	/// from a signed maximum of a value in this range and a value in \p Other.
428	ConstantRange smax(const ConstantRange &Other) const;
429
430	/// Return a new range representing the possible values resulting
431	/// from an unsigned maximum of a value in this range and a value in \p Other.
432	ConstantRange umax(const ConstantRange &Other) const;
433
434	/// Return a new range representing the possible values resulting
435	/// from a signed minimum of a value in this range and a value in \p Other.
436	ConstantRange smin(const ConstantRange &Other) const;
437
438	/// Return a new range representing the possible values resulting
439	/// from an unsigned minimum of a value in this range and a value in \p Other.
440	ConstantRange umin(const ConstantRange &Other) const;
441
442	/// Return a new range representing the possible values resulting
443	/// from an unsigned division of a value in this range and a value in
444	/// \p Other.
445	ConstantRange udiv(const ConstantRange &Other) const;
446
447	/// Return a new range representing the possible values resulting
448	/// from a signed division of a value in this range and a value in
449	/// \p Other. Division by zero and division of SignedMin by -1 are considered
450	/// undefined behavior, in line with IR, and do not contribute towards the
451	/// result.
452	ConstantRange sdiv(const ConstantRange &Other) const;
453
454	/// Return a new range representing the possible values resulting
455	/// from an unsigned remainder operation of a value in this range and a
456	/// value in \p Other.
457	ConstantRange urem(const ConstantRange &Other) const;
458
459	/// Return a new range representing the possible values resulting
460	/// from a signed remainder operation of a value in this range and a
461	/// value in \p Other.
462	ConstantRange srem(const ConstantRange &Other) const;
463
464	/// Return a new range representing the possible values resulting from
465	/// a binary-xor of a value in this range by an all-one value,
466	/// aka bitwise complement operation.
467	ConstantRange binaryNot() const;
468
469	/// Return a new range representing the possible values resulting
470	/// from a binary-and of a value in this range by a value in \p Other.
471	ConstantRange binaryAnd(const ConstantRange &Other) const;
472
473	/// Return a new range representing the possible values resulting
474	/// from a binary-or of a value in this range by a value in \p Other.
475	ConstantRange binaryOr(const ConstantRange &Other) const;
476
477	/// Return a new range representing the possible values resulting
478	/// from a binary-xor of a value in this range by a value in \p Other.
479	ConstantRange binaryXor(const ConstantRange &Other) const;
480
481	/// Return a new range representing the possible values resulting
482	/// from a left shift of a value in this range by a value in \p Other.
483	/// TODO: This isn't fully implemented yet.
484	ConstantRange shl(const ConstantRange &Other) const;
485
486	/// Return a new range representing the possible values resulting from a
487	/// logical right shift of a value in this range and a value in \p Other.
488	ConstantRange lshr(const ConstantRange &Other) const;
489
490	/// Return a new range representing the possible values resulting from a
491	/// arithmetic right shift of a value in this range and a value in \p Other.
492	ConstantRange ashr(const ConstantRange &Other) const;
493
494	/// Perform an unsigned saturating addition of two constant ranges.
495	ConstantRange uadd_sat(const ConstantRange &Other) const;
496
497	/// Perform a signed saturating addition of two constant ranges.
498	ConstantRange sadd_sat(const ConstantRange &Other) const;
499
500	/// Perform an unsigned saturating subtraction of two constant ranges.
501	ConstantRange usub_sat(const ConstantRange &Other) const;
502
503	/// Perform a signed saturating subtraction of two constant ranges.
504	ConstantRange ssub_sat(const ConstantRange &Other) const;
505
506	/// Perform an unsigned saturating multiplication of two constant ranges.
507	ConstantRange umul_sat(const ConstantRange &Other) const;
508
509	/// Perform a signed saturating multiplication of two constant ranges.
510	ConstantRange smul_sat(const ConstantRange &Other) const;
511
512	/// Perform an unsigned saturating left shift of this constant range by a
513	/// value in \p Other.
514	ConstantRange ushl_sat(const ConstantRange &Other) const;
515
516	/// Perform a signed saturating left shift of this constant range by a
517	/// value in \p Other.
518	ConstantRange sshl_sat(const ConstantRange &Other) const;
519
520	/// Return a new range that is the logical not of the current set.
521	ConstantRange inverse() const;
522
523	/// Calculate absolute value range. If the original range contains signed
524	/// min, then the resulting range will contain signed min if and only if
525	/// \p IntMinIsPoison is false.
526	ConstantRange abs(bool IntMinIsPoison = false) const;
527
528	/// Represents whether an operation on the given constant range is known to
529	/// always or never overflow.
530	enum class OverflowResult {
531	/// Always overflows in the direction of signed/unsigned min value.
532	AlwaysOverflowsLow,
533	/// Always overflows in the direction of signed/unsigned max value.
534	AlwaysOverflowsHigh,
535	/// May or may not overflow.
536	MayOverflow,
537	/// Never overflows.
538	NeverOverflows,
539	};
540
541	/// Return whether unsigned add of the two ranges always/never overflows.
542	OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const;
543
544	/// Return whether signed add of the two ranges always/never overflows.
545	OverflowResult signedAddMayOverflow(const ConstantRange &Other) const;
546
547	/// Return whether unsigned sub of the two ranges always/never overflows.
548	OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const;
549
550	/// Return whether signed sub of the two ranges always/never overflows.
551	OverflowResult signedSubMayOverflow(const ConstantRange &Other) const;
552
553	/// Return whether unsigned mul of the two ranges always/never overflows.
554	OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const;
555
556	/// Print out the bounds to a stream.
557	void print(raw_ostream &OS) const;
558
559	/// Allow printing from a debugger easily.
560	void dump() const;
561	};
562
563	inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) {
564	CR.print(OS);
565	return OS;
566	}
567
568	/// Parse out a conservative ConstantRange from !range metadata.
569	///
570	/// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20).
571	ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD);
572
573	} // end namespace llvm
574
575	#endif // LLVM_IR_CONSTANTRANGE_H

←

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/ADT/APInt.h

1//===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- 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/// \file
10/// This file implements a class to represent arbitrary precision
11/// integral constant values and operations on them.
12///
13//===----------------------------------------------------------------------===//

15#ifndef LLVM_ADT_APINT_H
16#define LLVM_ADT_APINT_H

18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/MathExtras.h"
20#include <cassert>
21#include <climits>
22#include <cstring>
23#include <utility>

25namespace llvm {
26class FoldingSetNodeID;
27class StringRef;
28class hash_code;
29class raw_ostream;

31template <typename T> class SmallVectorImpl;
32template <typename T> class ArrayRef;
33template <typename T> class Optional;
34template <typename T, typename Enable> struct DenseMapInfo;

36class APInt;

38inline APInt operator-(APInt);

40//===----------------------------------------------------------------------===//
41//                              APInt Class
42//===----------------------------------------------------------------------===//

44/// Class for arbitrary precision integers.
45///
46/// APInt is a functional replacement for common case unsigned integer type like
47/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
48/// integer sizes and large integer value types such as 3-bits, 15-bits, or more
49/// than 64-bits of precision. APInt provides a variety of arithmetic operators
50/// and methods to manipulate integer values of any bit-width. It supports both
51/// the typical integer arithmetic and comparison operations as well as bitwise
52/// manipulation.
53///
54/// The class has several invariants worth noting:
55///   * All bit, byte, and word positions are zero-based.
56///   * Once the bit width is set, it doesn't change except by the Truncate,
57///     SignExtend, or ZeroExtend operations.
58///   * All binary operators must be on APInt instances of the same bit width.
59///     Attempting to use these operators on instances with different bit
60///     widths will yield an assertion.
61///   * The value is stored canonically as an unsigned value. For operations
62///     where it makes a difference, there are both signed and unsigned variants
63///     of the operation. For example, sdiv and udiv. However, because the bit
64///     widths must be the same, operations such as Mul and Add produce the same
65///     results regardless of whether the values are interpreted as signed or
66///     not.
67///   * In general, the class tries to follow the style of computation that LLVM
68///     uses in its IR. This simplifies its use for LLVM.
69///   * APInt supports zero-bit-width values, but operations that require bits
70///     are not defined on it (e.g. you cannot ask for the sign of a zero-bit
71///     integer).  This means that operations like zero extension and logical
72///     shifts are defined, but sign extension and ashr is not.  Zero bit values
73///     compare and hash equal to themselves, and countLeadingZeros returns 0.
74///
75class LLVM_NODISCARD[[clang::warn_unused_result]] APInt {
76public:
typedef uint64_t WordType;

/// This enum is used to hold the constants we needed for APInt.
enum : unsigned {
  /// Byte size of a word.
  APINT_WORD_SIZE = sizeof(WordType),
  /// Bits in a word.
  APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8
};

enum class Rounding {
  DOWN,
  TOWARD_ZERO,
  UP,
};

static constexpr WordType WORDTYPE_MAX = ~WordType(0);

/// \name Constructors
/// @{

/// Create a new APInt of numBits width, initialized as val.
///
/// If isSigned is true then val is treated as if it were a signed value
/// (i.e. as an int64_t) and the appropriate sign extension to the bit width
/// will be done. Otherwise, no sign extension occurs (high order bits beyond
/// the range of val are zero filled).
///
/// \param numBits the bit width of the constructed APInt
/// \param val the initial value of the APInt
/// \param isSigned how to treat signedness of val
APInt(unsigned numBits, uint64_t val, bool isSigned = false)
    : BitWidth(numBits) {
  if (isSingleWord()) {
    U.VAL = val;
    clearUnusedBits();
  } else {
    initSlowCase(val, isSigned);
  }
}

/// Construct an APInt of numBits width, initialized as bigVal[].
///
/// Note that bigVal.size() can be smaller or larger than the corresponding
/// bit width but any extraneous bits will be dropped.
///
/// \param numBits the bit width of the constructed APInt
/// \param bigVal a sequence of words to form the initial value of the APInt
APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);

/// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
/// deprecated because this constructor is prone to ambiguity with the
/// APInt(unsigned, uint64_t, bool) constructor.
///
/// If this overload is ever deleted, care should be taken to prevent calls
/// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
/// constructor.
APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);

/// Construct an APInt from a string representation.
///
/// This constructor interprets the string \p str in the given radix. The
/// interpretation stops when the first character that is not suitable for the
/// radix is encountered, or the end of the string. Acceptable radix values
/// are 2, 8, 10, 16, and 36. It is an error for the value implied by the
/// string to require more bits than numBits.
///
/// \param numBits the bit width of the constructed APInt
/// \param str the string to be interpreted
/// \param radix the radix to use for the conversion
APInt(unsigned numBits, StringRef str, uint8_t radix);

/// Default constructor that creates an APInt with a 1-bit zero value.
explicit APInt() : BitWidth(1) { U.VAL = 0; }

/// Copy Constructor.
APInt(const APInt &that) : BitWidth(that.BitWidth) {
6
←
Assigned value is garbage or undefined
  if (isSingleWord())
    U.VAL = that.U.VAL;
  else
    initSlowCase(that);
}

/// Move Constructor.
APInt(APInt &&that) : BitWidth(that.BitWidth) {
  memcpy(&U, &that.U, sizeof(U));
  that.BitWidth = 0;
}

/// Destructor.
~APInt() {
  if (needsCleanup())
    delete[] U.pVal;
}

/// @}
/// \name Value Generators
/// @{

/// Get the '0' value for the specified bit-width.
static APInt getZero(unsigned numBits) { return APInt(numBits, 0); }

/// NOTE: This is soft-deprecated.  Please use `getZero()` instead.
static APInt getNullValue(unsigned numBits) { return getZero(numBits); }

/// Return an APInt zero bits wide.
static APInt getZeroWidth() { return getZero(0); }

/// Gets maximum unsigned value of APInt for specific bit width.
static APInt getMaxValue(unsigned numBits) { return getAllOnes(numBits); }

/// Gets maximum signed value of APInt for a specific bit width.
static APInt getSignedMaxValue(unsigned numBits) {
  APInt API = getAllOnes(numBits);
  API.clearBit(numBits - 1);
  return API;
}

/// Gets minimum unsigned value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); }

/// Gets minimum signed value of APInt for a specific bit width.
static APInt getSignedMinValue(unsigned numBits) {
  APInt API(numBits, 0);
  API.setBit(numBits - 1);
  return API;
}

/// Get the SignMask for a specific bit width.
///
/// This is just a wrapper function of getSignedMinValue(), and it helps code
/// readability when we want to get a SignMask.
static APInt getSignMask(unsigned BitWidth) {
  return getSignedMinValue(BitWidth);
}

/// Return an APInt of a specified width with all bits set.
static APInt getAllOnes(unsigned numBits) {
  return APInt(numBits, WORDTYPE_MAX, true);
}

/// NOTE: This is soft-deprecated.  Please use `getAllOnes()` instead.
static APInt getAllOnesValue(unsigned numBits) { return getAllOnes(numBits); }

/// Return an APInt with exactly one bit set in the result.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo) {
  APInt Res(numBits, 0);
  Res.setBit(BitNo);
  return Res;
}

/// Get a value with a block of bits set.
///
/// Constructs an APInt value that has a contiguous range of bits set. The
/// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
/// bits will be zero. For example, with parameters(32, 0, 16) you would get
/// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than
/// \p hiBit.
///
/// \param numBits the intended bit width of the result
/// \param loBit the index of the lowest bit set.
/// \param hiBit the index of the highest bit set.
///
/// \returns An APInt value with the requested bits set.
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
  APInt Res(numBits, 0);
  Res.setBits(loBit, hiBit);
  return Res;
}

/// Wrap version of getBitsSet.
/// If \p hiBit is bigger than \p loBit, this is same with getBitsSet.
/// If \p hiBit is not bigger than \p loBit, the set bits "wrap". For example,
/// with parameters (32, 28, 4), you would get 0xF000000F.
/// If \p hiBit is equal to \p loBit, you would get a result with all bits
/// set.
static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit,
                                unsigned hiBit) {
  APInt Res(numBits, 0);
  Res.setBitsWithWrap(loBit, hiBit);
  return Res;
}

/// Constructs an APInt value that has a contiguous range of bits set. The
/// bits from loBit (inclusive) to numBits (exclusive) will be set. All other
/// bits will be zero. For example, with parameters(32, 12) you would get
/// 0xFFFFF000.
///
/// \param numBits the intended bit width of the result
/// \param loBit the index of the lowest bit to set.
///
/// \returns An APInt value with the requested bits set.
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) {
  APInt Res(numBits, 0);
  Res.setBitsFrom(loBit);
  return Res;
}

/// Constructs an APInt value that has the top hiBitsSet bits set.
///
/// \param numBits the bitwidth of the result
/// \param hiBitsSet the number of high-order bits set in the result.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) {
  APInt Res(numBits, 0);
  Res.setHighBits(hiBitsSet);
  return Res;
}

/// Constructs an APInt value that has the bottom loBitsSet bits set.
///
/// \param numBits the bitwidth of the result
/// \param loBitsSet the number of low-order bits set in the result.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) {
  APInt Res(numBits, 0);
  Res.setLowBits(loBitsSet);
  return Res;
}

/// Return a value containing V broadcasted over NewLen bits.
static APInt getSplat(unsigned NewLen, const APInt &V);

/// @}
/// \name Value Tests
/// @{

/// Determine if this APInt just has one word to store value.
///
/// \returns true if the number of bits <= 64, false otherwise.
bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; }

/// Determine sign of this APInt.
///
/// This tests the high bit of this APInt to determine if it is set.
///
/// \returns true if this APInt is negative, false otherwise
bool isNegative() const { return (*this)[BitWidth - 1]; }

/// Determine if this APInt Value is non-negative (>= 0)
///
/// This tests the high bit of the APInt to determine if it is unset.
bool isNonNegative() const { return !isNegative(); }

/// Determine if sign bit of this APInt is set.
///
/// This tests the high bit of this APInt to determine if it is set.
///
/// \returns true if this APInt has its sign bit set, false otherwise.
bool isSignBitSet() const { return (*this)[BitWidth - 1]; }

/// Determine if sign bit of this APInt is clear.
///
/// This tests the high bit of this APInt to determine if it is clear.
///
/// \returns true if this APInt has its sign bit clear, false otherwise.
bool isSignBitClear() const { return !isSignBitSet(); }

/// Determine if this APInt Value is positive.
///
/// This tests if the value of this APInt is positive (> 0). Note
/// that 0 is not a positive value.
///
/// \returns true if this APInt is positive.
bool isStrictlyPositive() const { return isNonNegative() && !isZero(); }

/// Determine if this APInt Value is non-positive (<= 0).
///
/// \returns true if this APInt is non-positive.
bool isNonPositive() const { return !isStrictlyPositive(); }

/// Determine if all bits are set.  This is true for zero-width values.
bool isAllOnes() const {
  if (BitWidth == 0)
    return true;
  if (isSingleWord())
    return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth);
  return countTrailingOnesSlowCase() == BitWidth;
}

/// NOTE: This is soft-deprecated.  Please use `isAllOnes()` instead.
bool isAllOnesValue() const { return isAllOnes(); }

/// Determine if this value is zero, i.e. all bits are clear.
bool isZero() const {
  if (isSingleWord())
    return U.VAL == 0;
  return countLeadingZerosSlowCase() == BitWidth;
}

/// NOTE: This is soft-deprecated.  Please use `isZero()` instead.
bool isNullValue() const { return isZero(); }

/// Determine if this is a value of 1.
///
/// This checks to see if the value of this APInt is one.
bool isOne() const {
  if (isSingleWord())
    return U.VAL == 1;
  return countLeadingZerosSlowCase() == BitWidth - 1;
}

/// NOTE: This is soft-deprecated.  Please use `isOne()` instead.
bool isOneValue() const { return isOne(); }

/// Determine if this is the largest unsigned value.
///
/// This checks to see if the value of this APInt is the maximum unsigned
/// value for the APInt's bit width.
bool isMaxValue() const { return isAllOnes(); }

/// Determine if this is the largest signed value.
///
/// This checks to see if the value of this APInt is the maximum signed
/// value for the APInt's bit width.
bool isMaxSignedValue() const {
  if (isSingleWord()) {
    assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 392, __extension__ __PRETTY_FUNCTION__
));
    return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1);
  }
  return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1;
}

/// Determine if this is the smallest unsigned value.
///
/// This checks to see if the value of this APInt is the minimum unsigned
/// value for the APInt's bit width.
bool isMinValue() const { return isZero(); }

/// Determine if this is the smallest signed value.
///
/// This checks to see if the value of this APInt is the minimum signed
/// value for the APInt's bit width.
bool isMinSignedValue() const {
  if (isSingleWord()) {
    assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 410, __extension__ __PRETTY_FUNCTION__
));
    return U.VAL == (WordType(1) << (BitWidth - 1));
  }
  return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1;
}

/// Check if this APInt has an N-bits unsigned integer value.
bool isIntN(unsigned N) const { return getActiveBits() <= N; }

/// Check if this APInt has an N-bits signed integer value.
bool isSignedIntN(unsigned N) const { return getSignificantBits() <= N; }

/// Check if this APInt's value is a power of two greater than zero.
///
/// \returns true if the argument APInt value is a power of two > 0.
bool isPowerOf2() const {
  if (isSingleWord()) {
    assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 427, __extension__ __PRETTY_FUNCTION__
));
    return isPowerOf2_64(U.VAL);
  }
  return countPopulationSlowCase() == 1;
}

/// Check if this APInt's negated value is a power of two greater than zero.
bool isNegatedPowerOf2() const {
  assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 435, __extension__ __PRETTY_FUNCTION__
));
  if (isNonNegative())
    return false;
  // NegatedPowerOf2 - shifted mask in the top bits.
  unsigned LO = countLeadingOnes();
  unsigned TZ = countTrailingZeros();
  return (LO + TZ) == BitWidth;
}

/// Check if the APInt's value is returned by getSignMask.
///
/// \returns true if this is the value returned by getSignMask.
bool isSignMask() const { return isMinSignedValue(); }

/// Convert APInt to a boolean value.
///
/// This converts the APInt to a boolean value as a test against zero.
bool getBoolValue() const { return !isZero(); }

/// If this value is smaller than the specified limit, return it, otherwise
/// return the limit value.  This causes the value to saturate to the limit.
uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX(18446744073709551615UL)) const {
  return ugt(Limit) ? Limit : getZExtValue();
}

/// Check if the APInt consists of a repeated bit pattern.
///
/// e.g. 0x01010101 satisfies isSplat(8).
/// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
/// width without remainder.
bool isSplat(unsigned SplatSizeInBits) const;

/// \returns true if this APInt value is a sequence of \param numBits ones
/// starting at the least significant bit with the remainder zero.
bool isMask(unsigned numBits) const {
  assert(numBits != 0 && "numBits must be non-zero")(static_cast <bool> (numBits != 0 && "numBits must be non-zero"
) ? void (0) : __assert_fail ("numBits != 0 && \"numBits must be non-zero\""
, "llvm/include/llvm/ADT/APInt.h", 470, __extension__ __PRETTY_FUNCTION__
));
  assert(numBits <= BitWidth && "numBits out of range")(static_cast <bool> (numBits <= BitWidth && "numBits out of range"
) ? void (0) : __assert_fail ("numBits <= BitWidth && \"numBits out of range\""
, "llvm/include/llvm/ADT/APInt.h", 471, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord())
    return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits));
  unsigned Ones = countTrailingOnesSlowCase();
  return (numBits == Ones) &&
         ((Ones + countLeadingZerosSlowCase()) == BitWidth);
}

/// \returns true if this APInt is a non-empty sequence of ones starting at
/// the least significant bit with the remainder zero.
/// Ex. isMask(0x0000FFFFU) == true.
bool isMask() const {
  if (isSingleWord())
    return isMask_64(U.VAL);
  unsigned Ones = countTrailingOnesSlowCase();
  return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth);
}

/// Return true if this APInt value contains a non-empty sequence of ones with
/// the remainder zero.
bool isShiftedMask() const {
  if (isSingleWord())
    return isShiftedMask_64(U.VAL);
  unsigned Ones = countPopulationSlowCase();
  unsigned LeadZ = countLeadingZerosSlowCase();
  return (Ones + LeadZ + countTrailingZeros()) == BitWidth;
}

/// Return true if this APInt value contains a non-empty sequence of ones with
/// the remainder zero. If true, \p MaskIdx will specify the index of the
/// lowest set bit and \p MaskLen is updated to specify the length of the
/// mask, else neither are updated.
bool isShiftedMask(unsigned &MaskIdx, unsigned &MaskLen) const {
  if (isSingleWord())
    return isShiftedMask_64(U.VAL, MaskIdx, MaskLen);
  unsigned Ones = countPopulationSlowCase();
  unsigned LeadZ = countLeadingZerosSlowCase();
  unsigned TrailZ = countTrailingZerosSlowCase();
  if ((Ones + LeadZ + TrailZ) != BitWidth)
    return false;
  MaskLen = Ones;
  MaskIdx = TrailZ;
  return true;
}

/// Compute an APInt containing numBits highbits from this APInt.
///
/// Get an APInt with the same BitWidth as this APInt, just zero mask the low
/// bits and right shift to the least significant bit.
///
/// \returns the high "numBits" bits of this APInt.
APInt getHiBits(unsigned numBits) const;

/// Compute an APInt containing numBits lowbits from this APInt.
///
/// Get an APInt with the same BitWidth as this APInt, just zero mask the high
/// bits.
///
/// \returns the low "numBits" bits of this APInt.
APInt getLoBits(unsigned numBits) const;

/// Determine if two APInts have the same value, after zero-extending
/// one of them (if needed!) to ensure that the bit-widths match.
static bool isSameValue(const APInt &I1, const APInt &I2) {
  if (I1.getBitWidth() == I2.getBitWidth())
    return I1 == I2;

  if (I1.getBitWidth() > I2.getBitWidth())
    return I1 == I2.zext(I1.getBitWidth());

  return I1.zext(I2.getBitWidth()) == I2;
}

/// Overload to compute a hash_code for an APInt value.
friend hash_code hash_value(const APInt &Arg);

/// This function returns a pointer to the internal storage of the APInt.
/// This is useful for writing out the APInt in binary form without any
/// conversions.
const uint64_t *getRawData() const {
  if (isSingleWord())
    return &U.VAL;
  return &U.pVal[0];
}

/// @}
/// \name Unary Operators
/// @{

/// Postfix increment operator.  Increment *this by 1.
///
/// \returns a new APInt value representing the original value of *this.
APInt operator++(int) {
  APInt API(*this);
  ++(*this);
  return API;
}

/// Prefix increment operator.
///
/// \returns *this incremented by one
APInt &operator++();

/// Postfix decrement operator. Decrement *this by 1.
///
/// \returns a new APInt value representing the original value of *this.
APInt operator--(int) {
  APInt API(*this);
  --(*this);
  return API;
}

/// Prefix decrement operator.
///
/// \returns *this decremented by one.
APInt &operator--();

/// Logical negation operation on this APInt returns true if zero, like normal
/// integers.
bool operator!() const { return isZero(); }

/// @}
/// \name Assignment Operators
/// @{

/// Copy assignment operator.
///
/// \returns *this after assignment of RHS.
APInt &operator=(const APInt &RHS) {
  // The common case (both source or dest being inline) doesn't require
  // allocation or deallocation.
  if (isSingleWord() && RHS.isSingleWord()) {
    U.VAL = RHS.U.VAL;
    BitWidth = RHS.BitWidth;
    return *this;
  }

  assignSlowCase(RHS);
  return *this;
}

/// Move assignment operator.
APInt &operator=(APInt &&that) {
614#ifdef EXPENSIVE_CHECKS
  // Some std::shuffle implementations still do self-assignment.
  if (this == &that)
    return *this;
618#endif
  assert(this != &that && "Self-move not supported")(static_cast <bool> (this != &that && "Self-move not supported"
) ? void (0) : __assert_fail ("this != &that && \"Self-move not supported\""
, "llvm/include/llvm/ADT/APInt.h", 619, __extension__ __PRETTY_FUNCTION__
));
  if (!isSingleWord())
    delete[] U.pVal;

  // Use memcpy so that type based alias analysis sees both VAL and pVal
  // as modified.
  memcpy(&U, &that.U, sizeof(U));

  BitWidth = that.BitWidth;
  that.BitWidth = 0;
  return *this;
}

/// Assignment operator.
///
/// The RHS value is assigned to *this. If the significant bits in RHS exceed
/// the bit width, the excess bits are truncated. If the bit width is larger
/// than 64, the value is zero filled in the unspecified high order bits.
///
/// \returns *this after assignment of RHS value.
APInt &operator=(uint64_t RHS) {
  if (isSingleWord()) {
    U.VAL = RHS;
    return clearUnusedBits();
  }
  U.pVal[0] = RHS;
  memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
  return *this;
}

/// Bitwise AND assignment operator.
///
/// Performs a bitwise AND operation on this APInt and RHS. The result is
/// assigned to *this.
///
/// \returns *this after ANDing with RHS.
APInt &operator&=(const APInt &RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 656, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord())
    U.VAL &= RHS.U.VAL;
  else
    andAssignSlowCase(RHS);
  return *this;
}

/// Bitwise AND assignment operator.
///
/// Performs a bitwise AND operation on this APInt and RHS. RHS is
/// logically zero-extended or truncated to match the bit-width of
/// the LHS.
APInt &operator&=(uint64_t RHS) {
  if (isSingleWord()) {
    U.VAL &= RHS;
    return *this;
  }
  U.pVal[0] &= RHS;
  memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
  return *this;
}

/// Bitwise OR assignment operator.
///
/// Performs a bitwise OR operation on this APInt and RHS. The result is
/// assigned *this;
///
/// \returns *this after ORing with RHS.
APInt &operator|=(const APInt &RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 686, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord())
    U.VAL |= RHS.U.VAL;
  else
    orAssignSlowCase(RHS);
  return *this;
}

/// Bitwise OR assignment operator.
///
/// Performs a bitwise OR operation on this APInt and RHS. RHS is
/// logically zero-extended or truncated to match the bit-width of
/// the LHS.
APInt &operator|=(uint64_t RHS) {
  if (isSingleWord()) {
    U.VAL |= RHS;
    return clearUnusedBits();
  }
  U.pVal[0] |= RHS;
  return *this;
}

/// Bitwise XOR assignment operator.
///
/// Performs a bitwise XOR operation on this APInt and RHS. The result is
/// assigned to *this.
///
/// \returns *this after XORing with RHS.
APInt &operator^=(const APInt &RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 715, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord())
    U.VAL ^= RHS.U.VAL;
  else
    xorAssignSlowCase(RHS);
  return *this;
}

/// Bitwise XOR assignment operator.
///
/// Performs a bitwise XOR operation on this APInt and RHS. RHS is
/// logically zero-extended or truncated to match the bit-width of
/// the LHS.
APInt &operator^=(uint64_t RHS) {
  if (isSingleWord()) {
    U.VAL ^= RHS;
    return clearUnusedBits();
  }
  U.pVal[0] ^= RHS;
  return *this;
}

/// Multiplication assignment operator.
///
/// Multiplies this APInt by RHS and assigns the result to *this.
///
/// \returns *this
APInt &operator*=(const APInt &RHS);
APInt &operator*=(uint64_t RHS);

/// Addition assignment operator.
///
/// Adds RHS to *this and assigns the result to *this.
///
/// \returns *this
APInt &operator+=(const APInt &RHS);
APInt &operator+=(uint64_t RHS);

/// Subtraction assignment operator.
///
/// Subtracts RHS from *this and assigns the result to *this.
///
/// \returns *this
APInt &operator-=(const APInt &RHS);
APInt &operator-=(uint64_t RHS);

/// Left-shift assignment function.
///
/// Shifts *this left by shiftAmt and assigns the result to *this.
///
/// \returns *this after shifting left by ShiftAmt
APInt &operator<<=(unsigned ShiftAmt) {
  assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast <bool> (ShiftAmt <= BitWidth &&
 "Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "llvm/include/llvm/ADT/APInt.h", 767, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord()) {
    if (ShiftAmt == BitWidth)
      U.VAL = 0;
    else
      U.VAL <<= ShiftAmt;
    return clearUnusedBits();
  }
  shlSlowCase(ShiftAmt);
  return *this;
}

/// Left-shift assignment function.
///
/// Shifts *this left by shiftAmt and assigns the result to *this.
///
/// \returns *this after shifting left by ShiftAmt
APInt &operator<<=(const APInt &ShiftAmt);

/// @}
/// \name Binary Operators
/// @{

/// Multiplication operator.
///
/// Multiplies this APInt by RHS and returns the result.
APInt operator*(const APInt &RHS) const;

/// Left logical shift operator.
///
/// Shifts this APInt left by \p Bits and returns the result.
APInt operator<<(unsigned Bits) const { return shl(Bits); }

/// Left logical shift operator.
///
/// Shifts this APInt left by \p Bits and returns the result.
APInt operator<<(const APInt &Bits) const { return shl(Bits); }

/// Arithmetic right-shift function.
///
/// Arithmetic right-shift this APInt by shiftAmt.
APInt ashr(unsigned ShiftAmt) const {
  APInt R(*this);
  R.ashrInPlace(ShiftAmt);
  return R;
}

/// Arithmetic right-shift this APInt by ShiftAmt in place.
void ashrInPlace(unsigned ShiftAmt) {
  assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast <bool> (ShiftAmt <= BitWidth &&
 "Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "llvm/include/llvm/ADT/APInt.h", 816, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord()) {
    int64_t SExtVAL = SignExtend64(U.VAL, BitWidth);
    if (ShiftAmt == BitWidth)
      U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit.
    else
      U.VAL = SExtVAL >> ShiftAmt;
    clearUnusedBits();
    return;
  }
  ashrSlowCase(ShiftAmt);
}

/// Logical right-shift function.
///
/// Logical right-shift this APInt by shiftAmt.
APInt lshr(unsigned shiftAmt) const {
  APInt R(*this);
  R.lshrInPlace(shiftAmt);
  return R;
}

/// Logical right-shift this APInt by ShiftAmt in place.
void lshrInPlace(unsigned ShiftAmt) {
  assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast <bool> (ShiftAmt <= BitWidth &&
 "Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "llvm/include/llvm/ADT/APInt.h", 840, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord()) {
    if (ShiftAmt == BitWidth)
      U.VAL = 0;
    else
      U.VAL >>= ShiftAmt;
    return;
  }
  lshrSlowCase(ShiftAmt);
}

/// Left-shift function.
///
/// Left-shift this APInt by shiftAmt.
APInt shl(unsigned shiftAmt) const {
  APInt R(*this);
  R <<= shiftAmt;
  return R;
}

/// Rotate left by rotateAmt.
APInt rotl(unsigned rotateAmt) const;

/// Rotate right by rotateAmt.
APInt rotr(unsigned rotateAmt) const;

/// Arithmetic right-shift function.
///
/// Arithmetic right-shift this APInt by shiftAmt.
APInt ashr(const APInt &ShiftAmt) const {
  APInt R(*this);
  R.ashrInPlace(ShiftAmt);
  return R;
}

/// Arithmetic right-shift this APInt by shiftAmt in place.
void ashrInPlace(const APInt &shiftAmt);

/// Logical right-shift function.
///
/// Logical right-shift this APInt by shiftAmt.
APInt lshr(const APInt &ShiftAmt) const {
  APInt R(*this);
  R.lshrInPlace(ShiftAmt);
  return R;
}

/// Logical right-shift this APInt by ShiftAmt in place.
void lshrInPlace(const APInt &ShiftAmt);

/// Left-shift function.
///
/// Left-shift this APInt by shiftAmt.
APInt shl(const APInt &ShiftAmt) const {
  APInt R(*this);
  R <<= ShiftAmt;
  return R;
}

/// Rotate left by rotateAmt.
APInt rotl(const APInt &rotateAmt) const;

/// Rotate right by rotateAmt.
APInt rotr(const APInt &rotateAmt) const;

/// Concatenate the bits from "NewLSB" onto the bottom of *this.  This is
/// equivalent to:
///   (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth)
APInt concat(const APInt &NewLSB) const {
  /// If the result will be small, then both the merged values are small.
  unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth();
  if (NewWidth <= APINT_BITS_PER_WORD)
    return APInt(NewWidth, (U.VAL << NewLSB.getBitWidth()) | NewLSB.U.VAL);
  return concatSlowCase(NewLSB);
}

/// Unsigned division operation.
///
/// Perform an unsigned divide operation on this APInt by RHS. Both this and
/// RHS are treated as unsigned quantities for purposes of this division.
///
/// \returns a new APInt value containing the division result, rounded towards
/// zero.
APInt udiv(const APInt &RHS) const;
APInt udiv(uint64_t RHS) const;

/// Signed division function for APInt.
///
/// Signed divide this APInt by APInt RHS.
///
/// The result is rounded towards zero.
APInt sdiv(const APInt &RHS) const;
APInt sdiv(int64_t RHS) const;

/// Unsigned remainder operation.
///
/// Perform an unsigned remainder operation on this APInt with RHS being the
/// divisor. Both this and RHS are treated as unsigned quantities for purposes
/// of this operation. Note that this is a true remainder operation and not a
/// modulo operation because the sign follows the sign of the dividend which
/// is *this.
///
/// \returns a new APInt value containing the remainder result
APInt urem(const APInt &RHS) const;
uint64_t urem(uint64_t RHS) const;

/// Function for signed remainder operation.
///
/// Signed remainder operation on APInt.
APInt srem(const APInt &RHS) const;
int64_t srem(int64_t RHS) const;

/// Dual division/remainder interface.
///
/// Sometimes it is convenient to divide two APInt values and obtain both the
/// quotient and remainder. This function does both operations in the same
/// computation making it a little more efficient. The pair of input arguments
/// may overlap with the pair of output arguments. It is safe to call
/// udivrem(X, Y, X, Y), for example.
static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
                    APInt &Remainder);
static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
                    uint64_t &Remainder);

static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
                    APInt &Remainder);
static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient,
                    int64_t &Remainder);

// Operations that return overflow indicators.
APInt sadd_ov(const APInt &RHS, bool &Overflow) const;
APInt uadd_ov(const APInt &RHS, bool &Overflow) const;
APInt ssub_ov(const APInt &RHS, bool &Overflow) const;
APInt usub_ov(const APInt &RHS, bool &Overflow) const;
APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
APInt smul_ov(const APInt &RHS, bool &Overflow) const;
APInt umul_ov(const APInt &RHS, bool &Overflow) const;
APInt sshl_ov(const APInt &Amt, bool &Overflow) const;
APInt ushl_ov(const APInt &Amt, bool &Overflow) const;

// Operations that saturate
APInt sadd_sat(const APInt &RHS) const;
APInt uadd_sat(const APInt &RHS) const;
APInt ssub_sat(const APInt &RHS) const;
APInt usub_sat(const APInt &RHS) const;
APInt smul_sat(const APInt &RHS) const;
APInt umul_sat(const APInt &RHS) const;
APInt sshl_sat(const APInt &RHS) const;
APInt ushl_sat(const APInt &RHS) const;

/// Array-indexing support.
///
/// \returns the bit value at bitPosition
bool operator[](unsigned bitPosition) const {
  assert(bitPosition < getBitWidth() && "Bit position out of bounds!")(static_cast <bool> (bitPosition < getBitWidth() &&
 "Bit position out of bounds!") ? void (0) : __assert_fail ("bitPosition < getBitWidth() && \"Bit position out of bounds!\""
, "llvm/include/llvm/ADT/APInt.h", 994, __extension__ __PRETTY_FUNCTION__
));
  return (maskBit(bitPosition) & getWord(bitPosition)) != 0;
}

/// @}
/// \name Comparison Operators
/// @{

/// Equality operator.
///
/// Compares this APInt with RHS for the validity of the equality
/// relationship.
bool operator==(const APInt &RHS) const {
  assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Comparison requires equal bit widths") ? void (0) : __assert_fail
 ("BitWidth == RHS.BitWidth && \"Comparison requires equal bit widths\""
, "llvm/include/llvm/ADT/APInt.h", 1007, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord())
    return U.VAL == RHS.U.VAL;
  return equalSlowCase(RHS);
}

/// Equality operator.
///
/// Compares this APInt with a uint64_t for the validity of the equality
/// relationship.
///
/// \returns true if *this == Val
bool operator==(uint64_t Val) const {
  return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val;
}

/// Equality comparison.
///
/// Compares this APInt with RHS for the validity of the equality
/// relationship.
///
/// \returns true if *this == Val
bool eq(const APInt &RHS) const { return (*this) == RHS; }

/// Inequality operator.
///
/// Compares this APInt with RHS for the validity of the inequality
/// relationship.
///
/// \returns true if *this != Val
bool operator!=(const APInt &RHS) const { return !((*this) == RHS); }

/// Inequality operator.
///
/// Compares this APInt with a uint64_t for the validity of the inequality
/// relationship.
///
/// \returns true if *this != Val
bool operator!=(uint64_t Val) const { return !((*this) == Val); }

/// Inequality comparison
///
/// Compares this APInt with RHS for the validity of the inequality
/// relationship.
///
/// \returns true if *this != Val
bool ne(const APInt &RHS) const { return !((*this) == RHS); }

/// Unsigned less than comparison
///
/// Regards both *this and RHS as unsigned quantities and compares them for
/// the validity of the less-than relationship.
///
/// \returns true if *this < RHS when both are considered unsigned.
bool ult(const APInt &RHS) const { return compare(RHS) < 0; }

/// Unsigned less than comparison
///
/// Regards both *this as an unsigned quantity and compares it with RHS for
/// the validity of the less-than relationship.
///
/// \returns true if *this < RHS when considered unsigned.
bool ult(uint64_t RHS) const {
  // Only need to check active bits if not a single word.
  return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
}

/// Signed less than comparison
///
/// Regards both *this and RHS as signed quantities and compares them for
/// validity of the less-than relationship.
///
/// \returns true if *this < RHS when both are considered signed.
bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; }

/// Signed less than comparison
///
/// Regards both *this as a signed quantity and compares it with RHS for
/// the validity of the less-than relationship.
///
/// \returns true if *this < RHS when considered signed.
bool slt(int64_t RHS) const {
  return (!isSingleWord() && getSignificantBits() > 64)
             ? isNegative()
             : getSExtValue() < RHS;
}

/// Unsigned less or equal comparison
///
/// Regards both *this and RHS as unsigned quantities and compares them for
/// validity of the less-or-equal relationship.
///
/// \returns true if *this <= RHS when both are considered unsigned.
bool ule(const APInt &RHS) const { return compare(RHS) <= 0; }

/// Unsigned less or equal comparison
///
/// Regards both *this as an unsigned quantity and compares it with RHS for
/// the validity of the less-or-equal relationship.
///
/// \returns true if *this <= RHS when considered unsigned.
bool ule(uint64_t RHS) const { return !ugt(RHS); }

/// Signed less or equal comparison
///
/// Regards both *this and RHS as signed quantities and compares them for
/// validity of the less-or-equal relationship.
///
/// \returns true if *this <= RHS when both are considered signed.
bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; }

/// Signed less or equal comparison
///
/// Regards both *this as a signed quantity and compares it with RHS for the
/// validity of the less-or-equal relationship.
///
/// \returns true if *this <= RHS when considered signed.
bool sle(uint64_t RHS) const { return !sgt(RHS); }

/// Unsigned greater than comparison
///
/// Regards both *this and RHS as unsigned quantities and compares them for
/// the validity of the greater-than relationship.
///
/// \returns true if *this > RHS when both are considered unsigned.
bool ugt(const APInt &RHS) const { return !ule(RHS); }

/// Unsigned greater than comparison
///
/// Regards both *this as an unsigned quantity and compares it with RHS for
/// the validity of the greater-than relationship.
///
/// \returns true if *this > RHS when considered unsigned.
bool ugt(uint64_t RHS) const {
  // Only need to check active bits if not a single word.
  return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
}

/// Signed greater than comparison
///
/// Regards both *this and RHS as signed quantities and compares them for the
/// validity of the greater-than relationship.
///
/// \returns true if *this > RHS when both are considered signed.
bool sgt(const APInt &RHS) const { return !sle(RHS); }

/// Signed greater than comparison
///
/// Regards both *this as a signed quantity and compares it with RHS for
/// the validity of the greater-than relationship.
///
/// \returns true if *this > RHS when considered signed.
bool sgt(int64_t RHS) const {
  return (!isSingleWord() && getSignificantBits() > 64)
             ? !isNegative()
             : getSExtValue() > RHS;
}

/// Unsigned greater or equal comparison
///
/// Regards both *this and RHS as unsigned quantities and compares them for
/// validity of the greater-or-equal relationship.
///
/// \returns true if *this >= RHS when both are considered unsigned.
bool uge(const APInt &RHS) const { return !ult(RHS); }

/// Unsigned greater or equal comparison
///
/// Regards both *this as an unsigned quantity and compares it with RHS for
/// the validity of the greater-or-equal relationship.
///
/// \returns true if *this >= RHS when considered unsigned.
bool uge(uint64_t RHS) const { return !ult(RHS); }

/// Signed greater or equal comparison
///
/// Regards both *this and RHS as signed quantities and compares them for
/// validity of the greater-or-equal relationship.
///
/// \returns true if *this >= RHS when both are considered signed.
bool sge(const APInt &RHS) const { return !slt(RHS); }

/// Signed greater or equal comparison
///
/// Regards both *this as a signed quantity and compares it with RHS for
/// the validity of the greater-or-equal relationship.
///
/// \returns true if *this >= RHS when considered signed.
bool sge(int64_t RHS) const { return !slt(RHS); }

/// This operation tests if there are any pairs of corresponding bits
/// between this APInt and RHS that are both set.
bool intersects(const APInt &RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 1200, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord())
    return (U.VAL & RHS.U.VAL) != 0;
  return intersectsSlowCase(RHS);
}

/// This operation checks that all bits set in this APInt are also set in RHS.
bool isSubsetOf(const APInt &RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 1208, __extension__ __PRETTY_FUNCTION__
));
  if (isSingleWord())
    return (U.VAL & ~RHS.U.VAL) == 0;
  return isSubsetOfSlowCase(RHS);
}

/// @}
/// \name Resizing Operators
/// @{

/// Truncate to new width.
///
/// Truncate the APInt to a specified width. It is an error to specify a width
/// that is greater than or equal to the current width.
APInt trunc(unsigned width) const;

/// Truncate to new width with unsigned saturation.
///
/// If the APInt, treated as unsigned integer, can be losslessly truncated to
/// the new bitwidth, then return truncated APInt. Else, return max value.
APInt truncUSat(unsigned width) const;

/// Truncate to new width with signed saturation.
///
/// If this APInt, treated as signed integer, can be losslessly truncated to
/// the new bitwidth, then return truncated APInt. Else, return either
/// signed min value if the APInt was negative, or signed max value.
APInt truncSSat(unsigned width) const;

/// Sign extend to a new width.
///
/// This operation sign extends the APInt to a new width. If the high order
/// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
/// It is an error to specify a width that is less than or equal to the
/// current width.
APInt sext(unsigned width) const;

/// Zero extend to a new width.
///
/// This operation zero extends the APInt to a new width. The high order bits
/// are filled with 0 bits.  It is an error to specify a width that is less
/// than or equal to the current width.
APInt zext(unsigned width) const;

/// Sign extend or truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is sign
/// extended, truncated, or left alone to make it that width.
APInt sextOrTrunc(unsigned width) const;

/// Zero extend or truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is zero
/// extended, truncated, or left alone to make it that width.
APInt zextOrTrunc(unsigned width) const;

/// Truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is
/// truncated or left alone to make it that width.
APInt truncOrSelf(unsigned width) const;

/// Sign extend or truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is sign
/// extended, or left alone to make it that width.
APInt sextOrSelf(unsigned width) const;

/// Zero extend or truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is zero
/// extended, or left alone to make it that width.
APInt zextOrSelf(unsigned width) const;

/// @}
/// \name Bit Manipulation Operators
/// @{

/// Set every bit to 1.
void setAllBits() {
  if (isSingleWord())
    U.VAL = WORDTYPE_MAX;
  else
    // Set all the bits in all the words.
    memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE);
  // Clear the unused ones
  clearUnusedBits();
}

/// Set the given bit to 1 whose position is given as "bitPosition".
void setBit(unsigned BitPosition) {
  assert(BitPosition < BitWidth && "BitPosition out of range")(static_cast <bool> (BitPosition < BitWidth &&
 "BitPosition out of range") ? void (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1299, __extension__ __PRETTY_FUNCTION__
));
  WordType Mask = maskBit(BitPosition);
  if (isSingleWord())
    U.VAL |= Mask;
  else
    U.pVal[whichWord(BitPosition)] |= Mask;
}

/// Set the sign bit to 1.
void setSignBit() { setBit(BitWidth - 1); }

/// Set a given bit to a given value.
void setBitVal(unsigned BitPosition, bool BitValue) {
  if (BitValue)
    setBit(BitPosition);
  else
    clearBit(BitPosition);
}

/// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
/// This function handles "wrap" case when \p loBit >= \p hiBit, and calls
/// setBits when \p loBit < \p hiBit.
/// For \p loBit == \p hiBit wrap case, set every bit to 1.
void setBitsWithWrap(unsigned loBit, unsigned hiBit) {
  assert(hiBit <= BitWidth && "hiBit out of range")(static_cast <bool> (hiBit <= BitWidth && "hiBit out of range"
) ? void (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1323, __extension__ __PRETTY_FUNCTION__
));
  assert(loBit <= BitWidth && "loBit out of range")(static_cast <bool> (loBit <= BitWidth && "loBit out of range"
) ? void (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1324, __extension__ __PRETTY_FUNCTION__
));
  if (loBit < hiBit) {
    setBits(loBit, hiBit);
    return;
  }
  setLowBits(hiBit);
  setHighBits(BitWidth - loBit);
}

/// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
/// This function handles case when \p loBit <= \p hiBit.
void setBits(unsigned loBit, unsigned hiBit) {
  assert(hiBit <= BitWidth && "hiBit out of range")(static_cast <bool> (hiBit <= BitWidth && "hiBit out of range"
) ? void (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1336, __extension__ __PRETTY_FUNCTION__
));
  assert(loBit <= BitWidth && "loBit out of range")(static_cast <bool> (loBit <= BitWidth && "loBit out of range"
) ? void (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1337, __extension__ __PRETTY_FUNCTION__
));
  assert(loBit <= hiBit && "loBit greater than hiBit")(static_cast <bool> (loBit <= hiBit && "loBit greater than hiBit"
) ? void (0) : __assert_fail ("loBit <= hiBit && \"loBit greater than hiBit\""
, "llvm/include/llvm/ADT/APInt.h", 1338, __extension__ __PRETTY_FUNCTION__
));
  if (loBit == hiBit)
    return;
  if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
    uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
    mask <<= loBit;
    if (isSingleWord())
      U.VAL |= mask;
    else
      U.pVal[0] |= mask;
  } else {
    setBitsSlowCase(loBit, hiBit);
  }
}

/// Set the top bits starting from loBit.
void setBitsFrom(unsigned loBit) { return setBits(loBit, BitWidth); }

/// Set the bottom loBits bits.
void setLowBits(unsigned loBits) { return setBits(0, loBits); }

/// Set the top hiBits bits.
void setHighBits(unsigned hiBits) {
  return setBits(BitWidth - hiBits, BitWidth);
}

/// Set every bit to 0.
void clearAllBits() {
  if (isSingleWord())
    U.VAL = 0;
  else
    memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
}

/// Set a given bit to 0.
///
/// Set the given bit to 0 whose position is given as "bitPosition".
void clearBit(unsigned BitPosition) {
  assert(BitPosition < BitWidth && "BitPosition out of range")(static_cast <bool> (BitPosition < BitWidth &&
 "BitPosition out of range") ? void (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1376, __extension__ __PRETTY_FUNCTION__
));
  WordType Mask = ~maskBit(BitPosition);
  if (isSingleWord())
    U.VAL &= Mask;
  else
    U.pVal[whichWord(BitPosition)] &= Mask;
}

/// Set bottom loBits bits to 0.
void clearLowBits(unsigned loBits) {
  assert(loBits <= BitWidth && "More bits than bitwidth")(static_cast <bool> (loBits <= BitWidth && "More bits than bitwidth"
) ? void (0) : __assert_fail ("loBits <= BitWidth && \"More bits than bitwidth\""
, "llvm/include/llvm/ADT/APInt.h", 1386, __extension__ __PRETTY_FUNCTION__
));
  APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits);
  *this &= Keep;
}

/// Set the sign bit to 0.
void clearSignBit() { clearBit(BitWidth - 1); }

/// Toggle every bit to its opposite value.
void flipAllBits() {
  if (isSingleWord()) {
    U.VAL ^= WORDTYPE_MAX;
    clearUnusedBits();
  } else {
    flipAllBitsSlowCase();
  }
}

/// Toggles a given bit to its opposite value.
///
/// Toggle a given bit to its opposite value whose position is given
/// as "bitPosition".
void flipBit(unsigned bitPosition);

/// Negate this APInt in place.
void negate() {
  flipAllBits();
  ++(*this);
}

/// Insert the bits from a smaller APInt starting at bitPosition.
void insertBits(const APInt &SubBits, unsigned bitPosition);
void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits);

/// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
APInt extractBits(unsigned numBits, unsigned bitPosition) const;
uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const;

/// @}
/// \name Value Characterization Functions
/// @{

/// Return the number of bits in the APInt.
unsigned getBitWidth() const { return BitWidth; }

/// Get the number of words.
///
/// Here one word's bitwidth equals to that of uint64_t.
///
/// \returns the number of words to hold the integer value of this APInt.
unsigned getNumWords() const { return getNumWords(BitWidth); }

/// Get the number of words.
///
/// *NOTE* Here one word's bitwidth equals to that of uint64_t.
///
/// \returns the number of words to hold the integer value with a given bit
/// width.
static unsigned getNumWords(unsigned BitWidth) {
  return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
}

/// Compute the number of active bits in the value
///
/// This function returns the number of active bits which is defined as the
/// bit width minus the number of leading zeros. This is used in several
/// computations to see how "wide" the value is.
unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }

/// Compute the number of active words in the value of this APInt.
///
/// This is used in conjunction with getActiveData to extract the raw value of
/// the APInt.
unsigned getActiveWords() const {
  unsigned numActiveBits = getActiveBits();
  return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
}

/// Get the minimum bit size for this signed APInt
///
/// Computes the minimum bit width for this APInt while considering it to be a
/// signed (and probably negative) value. If the value is not negative, this
/// function returns the same value as getActiveBits()+1. Otherwise, it
/// returns the smallest bit width that will retain the negative value. For
/// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
/// for -1, this function will always return 1.
unsigned getSignificantBits() const {
  return BitWidth - getNumSignBits() + 1;
}

/// NOTE: This is soft-deprecated.  Please use `getSignificantBits()` instead.
unsigned getMinSignedBits() const { return getSignificantBits(); }

/// Get zero extended value
///
/// This method attempts to return the value of this APInt as a zero extended
/// uint64_t. The bitwidth must be <= 64 or the value must fit within a
/// uint64_t. Otherwise an assertion will result.
uint64_t getZExtValue() const {
  if (isSingleWord())
    return U.VAL;
  assert(getActiveBits() <= 64 && "Too many bits for uint64_t")(static_cast <bool> (getActiveBits() <= 64 &&
 "Too many bits for uint64_t") ? void (0) : __assert_fail ("getActiveBits() <= 64 && \"Too many bits for uint64_t\""
, "llvm/include/llvm/ADT/APInt.h", 1487, __extension__ __PRETTY_FUNCTION__
));
  return U.pVal[0];
}

/// Get sign extended value
///
/// This method attempts to return the value of this APInt as a sign extended
/// int64_t. The bit width must be <= 64 or the value must fit within an
/// int64_t. Otherwise an assertion will result.
int64_t getSExtValue() const {
  if (isSingleWord())
    return SignExtend64(U.VAL, BitWidth);
  assert(getSignificantBits() <= 64 && "Too many bits for int64_t")(static_cast <bool> (getSignificantBits() <= 64 &&
 "Too many bits for int64_t") ? void (0) : __assert_fail ("getSignificantBits() <= 64 && \"Too many bits for int64_t\""
, "llvm/include/llvm/ADT/APInt.h", 1499, __extension__ __PRETTY_FUNCTION__
));
  return int64_t(U.pVal[0]);
}

/// Get bits required for string value.
///
/// This method determines how many bits are required to hold the APInt
/// equivalent of the string given by \p str.
static unsigned getBitsNeeded(StringRef str, uint8_t radix);

/// Get the bits that are sufficient to represent the string value. This may
/// over estimate the amount of bits required, but it does not require
/// parsing the value in the string.
static unsigned getSufficientBitsNeeded(StringRef Str, uint8_t Radix);

/// The APInt version of the countLeadingZeros functions in
///   MathExtras.h.
///
/// It counts the number of zeros from the most significant bit to the first
/// one bit.
///
/// \returns BitWidth if the value is zero, otherwise returns the number of
///   zeros from the most significant bit to the first one bits.
unsigned countLeadingZeros() const {
  if (isSingleWord()) {
    unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
    return llvm::countLeadingZeros(U.VAL) - unusedBits;
  }
  return countLeadingZerosSlowCase();
}

/// Count the number of leading one bits.
///
/// This function is an APInt version of the countLeadingOnes
/// functions in MathExtras.h. It counts the number of ones from the most
/// significant bit to the first zero bit.
///
/// \returns 0 if the high order bit is not set, otherwise returns the number
/// of 1 bits from the most significant to the least
unsigned countLeadingOnes() const {
  if (isSingleWord()) {
    if (LLVM_UNLIKELY(BitWidth == 0)__builtin_expect((bool)(BitWidth == 0), false))
      return 0;
    return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
  }
  return countLeadingOnesSlowCase();
}

/// Computes the number of leading bits of this APInt that are equal to its
/// sign bit.
unsigned getNumSignBits() const {
  return isNegative() ? countLeadingOnes() : countLeadingZeros();
}

/// Count the number of trailing zero bits.
///
/// This function is an APInt version of the countTrailingZeros
/// functions in MathExtras.h. It counts the number of zeros from the least
/// significant bit to the first set bit.
///
/// \returns BitWidth if the value is zero, otherwise returns the number of
/// zeros from the least significant bit to the first one bit.
unsigned countTrailingZeros() const {
  if (isSingleWord()) {
    unsigned TrailingZeros = llvm::countTrailingZeros(U.VAL);
    return (TrailingZeros > BitWidth ? BitWidth : TrailingZeros);
  }
  return countTrailingZerosSlowCase();
}

/// Count the number of trailing one bits.
///
/// This function is an APInt version of the countTrailingOnes
/// functions in MathExtras.h. It counts the number of ones from the least
/// significant bit to the first zero bit.
///
/// \returns BitWidth if the value is all ones, otherwise returns the number
/// of ones from the least significant bit to the first zero bit.
unsigned countTrailingOnes() const {
  if (isSingleWord())
    return llvm::countTrailingOnes(U.VAL);
  return countTrailingOnesSlowCase();
}

/// Count the number of bits set.
///
/// This function is an APInt version of the countPopulation functions
/// in MathExtras.h. It counts the number of 1 bits in the APInt value.
///
/// \returns 0 if the value is zero, otherwise returns the number of set bits.
unsigned countPopulation() const {
  if (isSingleWord())
    return llvm::countPopulation(U.VAL);
  return countPopulationSlowCase();
}

/// @}
/// \name Conversion Functions
/// @{
void print(raw_ostream &OS, bool isSigned) const;

/// Converts an APInt to a string and append it to Str.  Str is commonly a
/// SmallString.
void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
              bool formatAsCLiteral = false) const;

/// Considers the APInt to be unsigned and converts it into a string in the
/// radix given. The radix can be 2, 8, 10 16, or 36.
void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
  toString(Str, Radix, false, false);
}

/// Considers the APInt to be signed and converts it into a string in the
/// radix given. The radix can be 2, 8, 10, 16, or 36.
void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
  toString(Str, Radix, true, false);
}

/// \returns a byte-swapped representation of this APInt Value.
APInt byteSwap() const;

/// \returns the value with the bit representation reversed of this APInt
/// Value.
APInt reverseBits() const;

/// Converts this APInt to a double value.
double roundToDouble(bool isSigned) const;

/// Converts this unsigned APInt to a double value.
double roundToDouble() const { return roundToDouble(false); }

/// Converts this signed APInt to a double value.
double signedRoundToDouble() const { return roundToDouble(true); }

/// Converts APInt bits to a double
///
/// The conversion does not do a translation from integer to double, it just
/// re-interprets the bits as a double. Note that it is valid to do this on
/// any bit width. Exactly 64 bits will be translated.
double bitsToDouble() const { return BitsToDouble(getWord(0)); }

/// Converts APInt bits to a float
///
/// The conversion does not do a translation from integer to float, it just
/// re-interprets the bits as a float. Note that it is valid to do this on
/// any bit width. Exactly 32 bits will be translated.
float bitsToFloat() const {
  return BitsToFloat(static_cast<uint32_t>(getWord(0)));
}

/// Converts a double to APInt bits.
///
/// The conversion does not do a translation from double to integer, it just
/// re-interprets the bits of the double.
static APInt doubleToBits(double V) {
  return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V));
}

/// Converts a float to APInt bits.
///
/// The conversion does not do a translation from float to integer, it just
/// re-interprets the bits of the float.
static APInt floatToBits(float V) {
  return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V));
}

/// @}
/// \name Mathematics Operations
/// @{

/// \returns the floor log base 2 of this APInt.
unsigned logBase2() const { return getActiveBits() - 1; }

/// \returns the ceil log base 2 of this APInt.
unsigned ceilLogBase2() const {
  APInt temp(*this);
  --temp;
  return temp.getActiveBits();
}

/// \returns the nearest log base 2 of this APInt. Ties round up.
///
/// NOTE: When we have a BitWidth of 1, we define:
///
///   log2(0) = UINT32_MAX
///   log2(1) = 0
///
/// to get around any mathematical concerns resulting from
/// referencing 2 in a space where 2 does no exist.
unsigned nearestLogBase2() const;

/// \returns the log base 2 of this APInt if its an exact power of two, -1
/// otherwise
int32_t exactLogBase2() const {
  if (!isPowerOf2())
    return -1;
  return logBase2();
}

/// Compute the square root.
APInt sqrt() const;

/// Get the absolute value.  If *this is < 0 then return -(*this), otherwise
/// *this.  Note that the "most negative" signed number (e.g. -128 for 8 bit
/// wide APInt) is unchanged due to how negation works.
APInt abs() const {
  if (isNegative())
    return -(*this);
  return *this;
}

/// \returns the multiplicative inverse for a given modulo.
APInt multiplicativeInverse(const APInt &modulo) const;

/// @}
/// \name Building-block Operations for APInt and APFloat
/// @{

// These building block operations operate on a representation of arbitrary
// precision, two's-complement, bignum integer values. They should be
// sufficient to implement APInt and APFloat bignum requirements. Inputs are
// generally a pointer to the base of an array of integer parts, representing
// an unsigned bignum, and a count of how many parts there are.

/// Sets the least significant part of a bignum to the input value, and zeroes
/// out higher parts.
static void tcSet(WordType *, WordType, unsigned);

/// Assign one bignum to another.
static void tcAssign(WordType *, const WordType *, unsigned);

/// Returns true if a bignum is zero, false otherwise.
static bool tcIsZero(const WordType *, unsigned);

/// Extract the given bit of a bignum; returns 0 or 1.  Zero-based.
static int tcExtractBit(const WordType *, unsigned bit);

/// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
/// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
/// significant bit of DST.  All high bits above srcBITS in DST are
/// zero-filled.
static void tcExtract(WordType *, unsigned dstCount, const WordType *,
                      unsigned srcBits, unsigned srcLSB);

/// Set the given bit of a bignum.  Zero-based.
static void tcSetBit(WordType *, unsigned bit);

/// Clear the given bit of a bignum.  Zero-based.
static void tcClearBit(WordType *, unsigned bit);

/// Returns the bit number of the least or most significant set bit of a
/// number.  If the input number has no bits set -1U is returned.
static unsigned tcLSB(const WordType *, unsigned n);
static unsigned tcMSB(const WordType *parts, unsigned n);

/// Negate a bignum in-place.
static void tcNegate(WordType *, unsigned);

/// DST += RHS + CARRY where CARRY is zero or one.  Returns the carry flag.
static WordType tcAdd(WordType *, const WordType *, WordType carry, unsigned);
/// DST += RHS.  Returns the carry flag.
static WordType tcAddPart(WordType *, WordType, unsigned);

/// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
static WordType tcSubtract(WordType *, const WordType *, WordType carry,
                           unsigned);
/// DST -= RHS.  Returns the carry flag.
static WordType tcSubtractPart(WordType *, WordType, unsigned);

/// DST += SRC * MULTIPLIER + PART   if add is true
/// DST  = SRC * MULTIPLIER + PART   if add is false
///
/// Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC they must
/// start at the same point, i.e. DST == SRC.
///
/// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
/// Otherwise DST is filled with the least significant DSTPARTS parts of the
/// result, and if all of the omitted higher parts were zero return zero,
/// otherwise overflow occurred and return one.
static int tcMultiplyPart(WordType *dst, const WordType *src,
                          WordType multiplier, WordType carry,
                          unsigned srcParts, unsigned dstParts, bool add);

/// DST = LHS * RHS, where DST has the same width as the operands and is
/// filled with the least significant parts of the result.  Returns one if
/// overflow occurred, otherwise zero.  DST must be disjoint from both
/// operands.
static int tcMultiply(WordType *, const WordType *, const WordType *,
                      unsigned);

/// DST = LHS * RHS, where DST has width the sum of the widths of the
/// operands. No overflow occurs. DST must be disjoint from both operands.
static void tcFullMultiply(WordType *, const WordType *, const WordType *,
                           unsigned, unsigned);

/// If RHS is zero LHS and REMAINDER are left unchanged, return one.
/// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
/// REMAINDER to the remainder, return zero.  i.e.
///
///  OLD_LHS = RHS * LHS + REMAINDER
///
/// SCRATCH is a bignum of the same size as the operands and result for use by
/// the routine; its contents need not be initialized and are destroyed.  LHS,
/// REMAINDER and SCRATCH must be distinct.
static int tcDivide(WordType *lhs, const WordType *rhs, WordType *remainder,
                    WordType *scratch, unsigned parts);

/// Shift a bignum left Count bits. Shifted in bits are zero. There are no
/// restrictions on Count.
static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);

/// Shift a bignum right Count bits.  Shifted in bits are zero.  There are no
/// restrictions on Count.
static void tcShiftRight(WordType *, unsigned Words, unsigned Count);

/// Comparison (unsigned) of two bignums.
static int tcCompare(const WordType *, const WordType *, unsigned);

/// Increment a bignum in-place.  Return the carry flag.
static WordType tcIncrement(WordType *dst, unsigned parts) {
  return tcAddPart(dst, 1, parts);
}

/// Decrement a bignum in-place.  Return the borrow flag.
static WordType tcDecrement(WordType *dst, unsigned parts) {
  return tcSubtractPart(dst, 1, parts);
}

/// Used to insert APInt objects, or objects that contain APInt objects, into
///  FoldingSets.
void Profile(FoldingSetNodeID &id) const;

/// debug method
void dump() const;

/// Returns whether this instance allocated memory.
bool needsCleanup() const { return !isSingleWord(); }

1837private:
/// This union is used to store the integer value. When the
/// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
union {
  uint64_t VAL;   ///< Used to store the <= 64 bits integer value.
  uint64_t *pVal; ///< Used to store the >64 bits integer value.
} U;

unsigned BitWidth; ///< The number of bits in this APInt.

friend struct DenseMapInfo<APInt, void>;
friend class APSInt;

/// This constructor is used only internally for speed of construction of
/// temporaries. It is unsafe since it takes ownership of the pointer, so it
/// is not public.
APInt(uint64_t *val, unsigned bits) : BitWidth(bits) { U.pVal = val; }

/// Determine which word a bit is in.
///
/// \returns the word position for the specified bit position.
static unsigned whichWord(unsigned bitPosition) {
  return bitPosition / APINT_BITS_PER_WORD;
}

/// Determine which bit in a word the specified bit position is in.
static unsigned whichBit(unsigned bitPosition) {
  return bitPosition % APINT_BITS_PER_WORD;
}

/// Get a single bit mask.
///
/// \returns a uint64_t with only bit at "whichBit(bitPosition)" set
/// This method generates and returns a uint64_t (word) mask for a single
/// bit at a specific bit position. This is used to mask the bit in the
/// corresponding word.
static uint64_t maskBit(unsigned bitPosition) {
  return 1ULL << whichBit(bitPosition);
}

/// Clear unused high order bits
///
/// This method is used internally to clear the top "N" bits in the high order
/// word that are not used by the APInt. This is needed after the most
/// significant word is assigned a value to ensure that those bits are
/// zero'd out.
APInt &clearUnusedBits() {
  // Compute how many bits are used in the final word.
  unsigned WordBits = ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1;

  // Mask out the high bits.
  uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits);
  if (LLVM_UNLIKELY(BitWidth == 0)__builtin_expect((bool)(BitWidth == 0), false))
    mask = 0;

  if (isSingleWord())
    U.VAL &= mask;
  else
    U.pVal[getNumWords() - 1] &= mask;
  return *this;
}

/// Get the word corresponding to a bit position
/// \returns the corresponding word for the specified bit position.
uint64_t getWord(unsigned bitPosition) const {
  return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)];
}

/// Utility method to change the bit width of this APInt to new bit width,
/// allocating and/or deallocating as necessary. There is no guarantee on the
/// value of any bits upon return. Caller should populate the bits after.
void reallocate(unsigned NewBitWidth);

/// Convert a char array into an APInt
///
/// \param radix 2, 8, 10, 16, or 36
/// Converts a string into a number.  The string must be non-empty
/// and well-formed as a number of the given base. The bit-width
/// must be sufficient to hold the result.
///
/// This is used by the constructors that take string arguments.
///
/// StringRef::getAsInteger is superficially similar but (1) does
/// not assume that the string is well-formed and (2) grows the
/// result to hold the input.
void fromString(unsigned numBits, StringRef str, uint8_t radix);

/// An internal division function for dividing APInts.
///
/// This is used by the toString method to divide by the radix. It simply
/// provides a more convenient form of divide for internal use since KnuthDiv
/// has specific constraints on its inputs. If those constraints are not met
/// then it provides a simpler form of divide.
static void divide(const WordType *LHS, unsigned lhsWords,
                   const WordType *RHS, unsigned rhsWords, WordType *Quotient,
                   WordType *Remainder);

/// out-of-line slow case for inline constructor
void initSlowCase(uint64_t val, bool isSigned);

/// shared code between two array constructors
void initFromArray(ArrayRef<uint64_t> array);

/// out-of-line slow case for inline copy constructor
void initSlowCase(const APInt &that);

/// out-of-line slow case for shl
void shlSlowCase(unsigned ShiftAmt);

/// out-of-line slow case for lshr.
void lshrSlowCase(unsigned ShiftAmt);

/// out-of-line slow case for ashr.
void ashrSlowCase(unsigned ShiftAmt);

/// out-of-line slow case for operator=
void assignSlowCase(const APInt &RHS);

/// out-of-line slow case for operator==
bool equalSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countLeadingZeros
unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countLeadingOnes.
unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countTrailingZeros.
unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countTrailingOnes
unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countPopulation
unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for intersects.
bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for isSubsetOf.
bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for setBits.
void setBitsSlowCase(unsigned loBit, unsigned hiBit);

/// out-of-line slow case for flipAllBits.
void flipAllBitsSlowCase();

/// out-of-line slow case for concat.
APInt concatSlowCase(const APInt &NewLSB) const;

/// out-of-line slow case for operator&=.
void andAssignSlowCase(const APInt &RHS);

/// out-of-line slow case for operator|=.
void orAssignSlowCase(const APInt &RHS);

/// out-of-line slow case for operator^=.
void xorAssignSlowCase(const APInt &RHS);

/// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal
/// to, or greater than RHS.
int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

/// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
/// to, or greater than RHS.
int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

/// @}
2006};

2008inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }

2010inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }

2012/// Unary bitwise complement operator.
2013///
2014/// \returns an APInt that is the bitwise complement of \p v.
2015inline APInt operator~(APInt v) {
v.flipAllBits();
return v;
2018}

2020inline APInt operator&(APInt a, const APInt &b) {
a &= b;
return a;
2023}

2025inline APInt operator&(const APInt &a, APInt &&b) {
b &= a;
return std::move(b);
2028}

2030inline APInt operator&(APInt a, uint64_t RHS) {
a &= RHS;
return a;
2033}

2035inline APInt operator&(uint64_t LHS, APInt b) {
b &= LHS;
return b;
2038}

2040inline APInt operator|(APInt a, const APInt &b) {
a |= b;
return a;
2043}

2045inline APInt operator|(const APInt &a, APInt &&b) {
b |= a;
return std::move(b);
2048}

2050inline APInt operator|(APInt a, uint64_t RHS) {
a |= RHS;
return a;
2053}

2055inline APInt operator|(uint64_t LHS, APInt b) {
b |= LHS;
return b;
2058}

2060inline APInt operator^(APInt a, const APInt &b) {
a ^= b;
return a;
2063}

2065inline APInt operator^(const APInt &a, APInt &&b) {
b ^= a;
return std::move(b);
2068}

2070inline APInt operator^(APInt a, uint64_t RHS) {
a ^= RHS;
return a;
2073}

2075inline APInt operator^(uint64_t LHS, APInt b) {
b ^= LHS;
return b;
2078}

2080inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
I.print(OS, true);
return OS;
2083}

2085inline APInt operator-(APInt v) {
v.negate();
return v;
2088}

2090inline APInt operator+(APInt a, const APInt &b) {
a += b;
return a;
2093}

2095inline APInt operator+(const APInt &a, APInt &&b) {
b += a;
return std::move(b);
2098}

2100inline APInt operator+(APInt a, uint64_t RHS) {
a += RHS;
return a;
2103}

2105inline APInt operator+(uint64_t LHS, APInt b) {
b += LHS;
return b;
2108}

2110inline APInt operator-(APInt a, const APInt &b) {
a -= b;
return a;
2113}

2115inline APInt operator-(const APInt &a, APInt &&b) {
b.negate();
b += a;
return std::move(b);
2119}

2121inline APInt operator-(APInt a, uint64_t RHS) {
a -= RHS;
return a;
2124}

2126inline APInt operator-(uint64_t LHS, APInt b) {
b.negate();
b += LHS;
return b;
2130}

2132inline APInt operator*(APInt a, uint64_t RHS) {
a *= RHS;
return a;
2135}

2137inline APInt operator*(uint64_t LHS, APInt b) {
b *= LHS;
return b;
2140}

2142namespace APIntOps {

2144/// Determine the smaller of two APInts considered to be signed.
2145inline const APInt &smin(const APInt &A, const APInt &B) {
return A.slt(B) ? A : B;
2147}

2149/// Determine the larger of two APInts considered to be signed.
2150inline const APInt &smax(const APInt &A, const APInt &B) {
return A.sgt(B) ? A : B;
2152}

2154/// Determine the smaller of two APInts considered to be unsigned.
2155inline const APInt &umin(const APInt &A, const APInt &B) {
return A.ult(B) ? A : B;
2157}

2159/// Determine the larger of two APInts considered to be unsigned.
2160inline const APInt &umax(const APInt &A, const APInt &B) {
return A.ugt(B) ? A : B;
2162}

2164/// Compute GCD of two unsigned APInt values.
2165///
2166/// This function returns the greatest common divisor of the two APInt values
2167/// using Stein's algorithm.
2168///
2169/// \returns the greatest common divisor of A and B.
2170APInt GreatestCommonDivisor(APInt A, APInt B);

2172/// Converts the given APInt to a double value.
2173///
2174/// Treats the APInt as an unsigned value for conversion purposes.
2175inline double RoundAPIntToDouble(const APInt &APIVal) {
return APIVal.roundToDouble();
2177}

2179/// Converts the given APInt to a double value.
2180///
2181/// Treats the APInt as a signed value for conversion purposes.
2182inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
return APIVal.signedRoundToDouble();
2184}

2186/// Converts the given APInt to a float value.
2187inline float RoundAPIntToFloat(const APInt &APIVal) {
return float(RoundAPIntToDouble(APIVal));
2189}

2191/// Converts the given APInt to a float value.
2192///
2193/// Treats the APInt as a signed value for conversion purposes.
2194inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
return float(APIVal.signedRoundToDouble());
2196}

2198/// Converts the given double value into a APInt.
2199///
2200/// This function convert a double value to an APInt value.
2201APInt RoundDoubleToAPInt(double Double, unsigned width);

2203/// Converts a float value into a APInt.
2204///
2205/// Converts a float value into an APInt value.
2206inline APInt RoundFloatToAPInt(float Float, unsigned width) {
return RoundDoubleToAPInt(double(Float), width);
2208}

2210/// Return A unsign-divided by B, rounded by the given rounding mode.
2211APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);

2213/// Return A sign-divided by B, rounded by the given rounding mode.
2214APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);

2216/// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2217/// (e.g. 32 for i32).
2218/// This function finds the smallest number n, such that
2219/// (a) n >= 0 and q(n) = 0, or
2220/// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2221///     integers, belong to two different intervals [Rk, Rk+R),
2222///     where R = 2^BW, and k is an integer.
2223/// The idea here is to find when q(n) "overflows" 2^BW, while at the
2224/// same time "allowing" subtraction. In unsigned modulo arithmetic a
2225/// subtraction (treated as addition of negated numbers) would always
2226/// count as an overflow, but here we want to allow values to decrease
2227/// and increase as long as they are within the same interval.
2228/// Specifically, adding of two negative numbers should not cause an
2229/// overflow (as long as the magnitude does not exceed the bit width).
2230/// On the other hand, given a positive number, adding a negative
2231/// number to it can give a negative result, which would cause the
2232/// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2233/// treated as a special case of an overflow.
2234///
2235/// This function returns None if after finding k that minimizes the
2236/// positive solution to q(n) = kR, both solutions are contained between
2237/// two consecutive integers.
2238///
2239/// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2240/// in arithmetic modulo 2^BW, and treating the values as signed) by the
2241/// virtue of *signed* overflow. This function will *not* find such an n,
2242/// however it may find a value of n satisfying the inequalities due to
2243/// an *unsigned* overflow (if the values are treated as unsigned).
2244/// To find a solution for a signed overflow, treat it as a problem of
2245/// finding an unsigned overflow with a range with of BW-1.
2246///
2247/// The returned value may have a different bit width from the input
2248/// coefficients.
2249Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
                                         unsigned RangeWidth);

2252/// Compare two values, and if they are different, return the position of the
2253/// most significant bit that is different in the values.
2254Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A,
                                                const APInt &B);

2257/// Splat/Merge neighboring bits to widen/narrow the bitmask represented
2258/// by \param A to \param NewBitWidth bits.
2259///
2260/// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011
2261/// e.g. ScaleBitMask(0b00011011, 4) -> 0b0111
2262/// A.getBitwidth() or NewBitWidth must be a whole multiples of the other.
2263///
2264/// TODO: Do we need a mode where all bits must be set when merging down?
2265APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth);
2266} // namespace APIntOps

2268// See friend declaration above. This additional declaration is required in
2269// order to compile LLVM with IBM xlC compiler.
2270hash_code hash_value(const APInt &Arg);

2272/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
2273/// with the integer held in IntVal.
2274void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes);

2276/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
2277/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
2278void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes);

2280/// Provide DenseMapInfo for APInt.
2281template <> struct DenseMapInfo<APInt, void> {
static inline APInt getEmptyKey() {
  APInt V(nullptr, 0);
  V.U.VAL = 0;
  return V;
}

static inline APInt getTombstoneKey() {
  APInt V(nullptr, 0);
  V.U.VAL = 1;
  return V;
}

static unsigned getHashValue(const APInt &Key);

static bool isEqual(const APInt &LHS, const APInt &RHS) {
  return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS;
}
2299};

2301} // namespace llvm

2303#endif