#include "llvm/IR/ConstantRange.h"
#include "llvm/ADT/APInt.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>

Functions
static ConstantRange	makeExactMulNUWRegion (const APInt &V)
	Exact mul nuw region for single element RHS.

static ConstantRange	makeExactMulNSWRegion (const APInt &V)
	Exact mul nsw region for single element RHS.

static ConstantRange	getPreferredRange (const ConstantRange &CR1, const ConstantRange &CR2, ConstantRange::PreferredRangeType Type)

static APInt	estimateBitMaskedAndLowerBound (const ConstantRange &LHS, const ConstantRange &RHS)
	Estimate the 'bit-masked AND' operation's lower bound.

static ConstantRange	computeShlNUW (const ConstantRange &LHS, const ConstantRange &RHS)

static ConstantRange	computeShlNSWWithNNegLHS (const APInt &LHSMin, const APInt &LHSMax, unsigned RHSMin, unsigned RHSMax)

static ConstantRange	computeShlNSWWithNegLHS (const APInt &LHSMin, const APInt &LHSMax, unsigned RHSMin, unsigned RHSMax)

static ConstantRange	computeShlNSW (const ConstantRange &LHS, const ConstantRange &RHS)

static ConstantRange	getUnsignedCountTrailingZerosRange (const APInt &Lower, const APInt &Upper)

static ConstantRange	getUnsignedPopCountRange (const APInt &Lower, const APInt &Upper)

Function Documentation

◆ computeShlNSW()

static ConstantRange computeShlNSW	(	const ConstantRange &	LHS,
		const ConstantRange &	RHS
	)

static

Definition at line 1748 of file ConstantRange.cpp.

References llvm::BitWidth, computeShlNSWWithNegLHS(), computeShlNSWWithNNegLHS(), llvm::APInt::getAllOnes(), llvm::APInt::getZero(), llvm::APInt::isNegative(), llvm::APInt::isNonNegative(), LHS, RHS, llvm::ConstantRange::Signed, and llvm::ConstantRange::unionWith().

Referenced by llvm::ConstantRange::shlWithNoWrap().

◆ computeShlNSWWithNegLHS()

static ConstantRange computeShlNSWWithNegLHS	(	const APInt &	LHSMin,
		const APInt &	LHSMax,
		unsigned	RHSMin,
		unsigned	RHSMax
	)

static

Definition at line 1729 of file ConstantRange.cpp.

References llvm::BitWidth, llvm::APInt::countLeadingOnes(), llvm::APInt::getBitWidth(), llvm::ConstantRange::getNonEmpty(), llvm::APInt::getSignMask(), llvm::APInt::shl(), and llvm::APInt::sshl_ov().

Referenced by computeShlNSW().

◆ computeShlNSWWithNNegLHS()

static ConstantRange computeShlNSWWithNNegLHS	(	const APInt &	LHSMin,
		const APInt &	LHSMax,
		unsigned	RHSMin,
		unsigned	RHSMax
	)

static

Definition at line 1708 of file ConstantRange.cpp.

References llvm::BitWidth, llvm::APInt::countLeadingZeros(), llvm::APInt::getBitsSet(), llvm::APInt::getBitWidth(), llvm::ConstantRange::getNonEmpty(), llvm::APInt::sshl_ov(), and llvm::APIntOps::umax().

Referenced by computeShlNSW().

◆ computeShlNUW()

static ConstantRange computeShlNUW	(	const ConstantRange &	LHS,
		const ConstantRange &	RHS
	)

static

Definition at line 1685 of file ConstantRange.cpp.

References llvm::BitWidth, llvm::APInt::countLeadingZeros(), llvm::APInt::getHighBitsSet(), llvm::ConstantRange::getNonEmpty(), LHS, RHS, llvm::APIntOps::umax(), and llvm::APInt::ushl_ov().

Referenced by llvm::ConstantRange::shlWithNoWrap().

◆ estimateBitMaskedAndLowerBound()

static APInt estimateBitMaskedAndLowerBound	(	const ConstantRange &	LHS,
		const ConstantRange &	RHS
	)

static

Estimate the 'bit-masked AND' operation's lower bound.

E.g., given two ranges as follows (single quotes are separators and have no meaning here),

LHS = [10'00101'1, ; LLo 10'10000'0] ; LHi RHS = [10'11111'0, ; RLo 10'11111'1] ; RHi

we know that the higher 2 bits of the result is always 10; and we also notice that RHS[1:6] are always 1, so the result[1:6] cannot be less than LHS[1:6] (i.e., 00101). Thus, the lower bound is 10'00101'0.

The algorithm is as follows,

we first calculate a mask to find the higher common bits by Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo)); Mask = clear all non-leading-ones bits in Mask; in the example, the Mask is set to 11'00000'0;
calculate a new mask by setting all common leading bits to 1 in RHS, and keeping the longest leading ones (i.e., 11'11111'0 in the example);
return (LLo & new mask) as the lower bound;
repeat the step 2 and 3 with LHS and RHS swapped, and update the lower bound with the larger one.

Definition at line 1547 of file ConstantRange.cpp.

References llvm::BitWidth, llvm::APInt::getZero(), LHS, RHS, and llvm::APIntOps::umax().

Referenced by llvm::ConstantRange::binaryAnd(), and llvm::ConstantRange::binaryOr().