blob: 290547ac6ff2a2a619b054f66fdbbae6c768b564 [file] [edit]
// Copyright 2024 The Dawn & Tint Authors
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include "src/tint/lang/core/ir/analysis/integer_range_analysis.h"
#include <algorithm>
#include <limits>
#include "src/tint/lang/core/constant/scalar.h"
#include "src/tint/lang/core/ir/access.h"
#include "src/tint/lang/core/ir/binary.h"
#include "src/tint/lang/core/ir/convert.h"
#include "src/tint/lang/core/ir/core_builtin_call.h"
#include "src/tint/lang/core/ir/exit_if.h"
#include "src/tint/lang/core/ir/exit_loop.h"
#include "src/tint/lang/core/ir/function.h"
#include "src/tint/lang/core/ir/if.h"
#include "src/tint/lang/core/ir/let.h"
#include "src/tint/lang/core/ir/load.h"
#include "src/tint/lang/core/ir/loop.h"
#include "src/tint/lang/core/ir/module.h"
#include "src/tint/lang/core/ir/multi_in_block.h"
#include "src/tint/lang/core/ir/next_iteration.h"
#include "src/tint/lang/core/ir/store.h"
#include "src/tint/lang/core/ir/traverse.h"
#include "src/tint/lang/core/ir/var.h"
#include "src/tint/lang/core/type/i32.h"
#include "src/tint/lang/core/type/pointer.h"
#include "src/tint/lang/core/type/u32.h"
#include "src/tint/utils/rtti/switch.h"
namespace tint::core::ir::analysis {
namespace {
/// Returns true if v is the integer constant 1.
bool IsOne(const Value* v) {
if (auto* cv = v->As<Constant>()) {
return Switch(
cv->Type(),
[&](const core::type::I32*) { return cv->Value()->ValueAs<int32_t>() == 1; },
[&](const core::type::U32*) { return cv->Value()->ValueAs<uint32_t>() == 1; },
[&](const Default) -> bool { return false; });
}
return false;
}
bool IsConstantInteger(const Value* v) {
if (auto* cv = v->As<Constant>()) {
return cv->Type()->IsIntegerScalar();
}
return false;
}
int64_t GetValueFromConstant(const Constant* value) {
// Return an int64_t is enough as the type of `value` can only be either i32 or u32.
[[maybe_unused]] bool is_i32_or_u32 = value->Type()->IsAnyOf<type::I32, type::U32>();
TINT_ASSERT(is_i32_or_u32);
return value->Value()->ValueAs<int64_t>();
}
struct CompareOpAndConstRHS {
BinaryOp op;
int64_t const_rhs = 0;
const Binary* binary = nullptr;
};
IntegerRangeInfo ToIntegerRangeInfo(const Constant* constant,
int64_t min_value,
int64_t max_value) {
if (constant->Type()->IsSignedIntegerScalar()) {
return IntegerRangeInfo(min_value, max_value);
} else {
return IntegerRangeInfo(static_cast<uint64_t>(min_value), static_cast<uint64_t>(max_value));
}
}
IntegerRangeInfo GetFullRangeWithSameIntegerRangeInfoType(const IntegerRangeInfo& range) {
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(range.range)) {
return IntegerRangeInfo(static_cast<int64_t>(i32::kLowestValue),
static_cast<int64_t>(i32::kHighestValue));
} else {
return IntegerRangeInfo(static_cast<uint64_t>(u32::kLowestValue),
static_cast<uint64_t>(u32::kHighestValue));
}
}
} // namespace
IntegerRangeInfo::IntegerRangeInfo(int64_t min_bound, int64_t max_bound) {
TINT_ASSERT(min_bound <= max_bound);
range = SignedIntegerRange{min_bound, max_bound};
}
IntegerRangeInfo::IntegerRangeInfo(uint64_t min_bound, uint64_t max_bound) {
TINT_ASSERT(min_bound <= max_bound);
range = UnsignedIntegerRange{min_bound, max_bound};
}
bool IntegerRangeInfo::IsValid() const {
return !std::holds_alternative<std::monostate>(range);
}
struct IntegerRangeAnalysisImpl {
explicit IntegerRangeAnalysisImpl(Module* ir_module) {
for (Function* func : ir_module->functions) {
// Analyze all the function parameters.
AnalyzeFunctionParameters(func);
// Analyze all of the loops in the function.
Traverse(func->Block(), [&](Loop* l) { AnalyzeLoop(l); });
}
}
IntegerRangeInfo GetInfo(const FunctionParam* param, uint32_t index) {
const auto& range_info = integer_function_param_range_info_map_.Get(param);
if (!range_info) {
return {};
}
TINT_ASSERT(range_info.value->Length() > index);
return (*range_info)[index];
}
IntegerRangeInfo GetInfo(const Var* var) { return integer_var_range_info_map_.GetOr(var, {}); }
IntegerRangeInfo GetInfo(const Load* load) {
const InstructionResult* instruction = load->From()->As<InstructionResult>();
if (!instruction) {
return {};
}
const Var* load_from_var = instruction->Instruction()->As<Var>();
if (!load_from_var) {
return {};
}
return GetInfo(load_from_var);
}
IntegerRangeInfo GetInfo(const Access* access) {
const Value* obj = access->Object();
// Currently we only support the access to `local_invocation_id` or `local_invocation_index`
// as a function parameter.
const FunctionParam* function_param = obj->As<FunctionParam>();
if (!function_param) {
return {};
}
if (access->Indices().Length() > 1) {
return {};
}
if (!access->Indices()[0]->As<Constant>()) {
return {};
}
uint32_t index =
static_cast<uint32_t>(GetValueFromConstant(access->Indices()[0]->As<Constant>()));
return GetInfo(function_param, index);
}
IntegerRangeInfo GetInfo(const Let* let) { return GetInfo(let->Value()); }
IntegerRangeInfo GetInfo(const Constant* constant) {
if (!IsConstantInteger(constant)) {
return {};
}
return integer_constant_range_info_map_.GetOrAdd(constant, [&]() {
int64_t const_value = GetValueFromConstant(constant);
return ToIntegerRangeInfo(constant, const_value, const_value);
});
}
IntegerRangeInfo GetInfo(const Convert* convert) {
return integer_convert_range_info_map_.GetOrAdd(convert, [&]() -> IntegerRangeInfo {
auto* result_type = convert->Result()->Type();
if (!result_type->IsIntegerScalar()) {
return {};
}
const auto* operand = convert->Operand(Convert::kValueOperandOffset);
IntegerRangeInfo operand_range_info = GetInfo(operand);
if (!operand_range_info.IsValid()) {
return {};
}
TINT_ASSERT(operand->Type()->IsIntegerScalar());
TINT_ASSERT(operand->Type() != result_type);
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(
operand_range_info.range)) {
// result = convert<u32>(operand), operand cannot be negative.
TINT_ASSERT(result_type->As<type::U32>());
const auto& range =
std::get<IntegerRangeInfo::SignedIntegerRange>(operand_range_info.range);
if (range.min_bound < 0) {
return {};
}
return IntegerRangeInfo(static_cast<uint64_t>(range.min_bound),
static_cast<uint64_t>(range.max_bound));
} else {
// result = convert<i32>(operand), operand cannot be greater than
// `i32::kHighestValue`.
TINT_ASSERT(result_type->As<type::I32>());
const auto& range =
std::get<IntegerRangeInfo::UnsignedIntegerRange>(operand_range_info.range);
if (range.max_bound > i32::kHighestValue) {
return {};
}
return IntegerRangeInfo(static_cast<int64_t>(range.min_bound),
static_cast<int64_t>(range.max_bound));
}
});
}
IntegerRangeInfo GetInfo(const Value* value) {
return Switch(
value, [&](const Constant* constant) { return GetInfo(constant); },
[&](const FunctionParam* param) {
if (!param->Type()->IsIntegerScalar()) {
return IntegerRangeInfo();
}
return GetInfo(param, 0);
},
[&](const InstructionResult* r) {
// TODO(348701956): Support more instruction types
return Switch(
r->Instruction(), [&](const Var* var) { return GetInfo(var); },
[&](const Load* load) { return GetInfo(load); },
[&](const Access* access) { return GetInfo(access); },
[&](const Let* let) { return GetInfo(let); },
[&](const Binary* binary) { return GetInfo(binary); },
[&](const Convert* convert) { return GetInfo(convert); },
[&](const CoreBuiltinCall* call) { return GetInfo(call); },
[](Default) { return IntegerRangeInfo(); });
},
[](Default) { return IntegerRangeInfo(); });
}
IntegerRangeInfo GetInfo(const Binary* binary) {
return integer_binary_range_info_map_.GetOrAdd(binary, [&]() -> IntegerRangeInfo {
IntegerRangeInfo range_rhs = GetInfo(binary->RHS());
if (!range_rhs.IsValid()) {
return {};
}
// We may compute the range of a `modulo` binary when the LHS doesn't have a valid
// range.
if (binary->Op() == BinaryOp::kModulo) {
return ComputeIntegerRangeForBinaryModulo(binary->LHS(), range_rhs);
}
IntegerRangeInfo range_lhs = GetInfo(binary->LHS());
if (!range_lhs.IsValid()) {
return {};
}
// TODO(348701956): Support more binary operators
switch (binary->Op()) {
case BinaryOp::kAdd:
return ComputeIntegerRangeForBinaryAdd(range_lhs, range_rhs);
case BinaryOp::kSubtract:
return ComputeIntegerRangeForBinarySubtract(range_lhs, range_rhs);
case BinaryOp::kMultiply:
return ComputeIntegerRangeForBinaryMultiply(range_lhs, range_rhs);
case BinaryOp::kDivide:
return ComputeIntegerRangeForBinaryDivide(range_lhs, range_rhs);
case BinaryOp::kShiftLeft:
return ComputeIntegerRangeForBinaryShiftLeft(range_lhs, range_rhs);
case BinaryOp::kShiftRight:
return ComputeIntegerRangeForBinaryShiftRight(range_lhs, range_rhs);
default:
return {};
}
});
}
IntegerRangeInfo GetInfo(const CoreBuiltinCall* call) {
return integer_core_builtin_call_range_info_map_.GetOrAdd(call, [&]() -> IntegerRangeInfo {
// Currently we only support the integer builtin calls that return an integer value.
if (!call->Result()->Type()->IsIntegerScalar()) {
return {};
}
// TODO(348701956): Support more builtin functions
switch (call->Func()) {
case core::BuiltinFn::kMin: {
return ComputeIntegerRangeForBuiltinMin(call);
}
case core::BuiltinFn::kMax: {
return ComputeIntegerRangeForBuiltinMax(call);
}
default:
return {};
}
});
}
/// Analyze a loop to compute the range of the loop control variable if possible.
void AnalyzeLoop(const Loop* loop) {
const Var* index = GetLoopControlVariableFromConstantInitializer(loop);
if (!index) {
return;
}
const Binary* update = GetBinaryToUpdateLoopControlVariableInContinuingBlock(loop, index);
if (!update) {
return;
}
CompareOpAndConstRHS compare_info =
GetCompareInfoOfLoopControlVariableInLoopBody(loop, index);
if (!compare_info.binary) {
return;
}
TINT_ASSERT(index->Initializer());
TINT_ASSERT(index->Initializer()->As<Constant>());
// for (var i = const_init; ...)
const Constant* constant_initializer = index->Initializer()->As<Constant>();
int64_t const_init = GetValueFromConstant(constant_initializer);
// for (...; i++) or for(...; i--)
bool index_is_increasing = update->Op() == BinaryOp::kAdd;
switch (compare_info.op) {
case BinaryOp::kLessThanEqual: {
// for (var index = const_init; index <= const_rhs; index++)
// Only `const_init <= const_rhs` is valid. The range of `index` is:
// [const_init, const_rhs]
// Note that in `GetBinaryToCompareLoopControlVariableInLoopBody()` we disallow
// `const_rhs` to be the maximum value of `i32` or `u32`, so:
// - `index + 1` won't be overflow as `const_init` cannot be greater than
// `const_rhs`.
// - `index <= const_rhs` can correctly exit when `const_init + 1` is the maximum
// value of `i32` or `u32`.
if (index_is_increasing && const_init <= compare_info.const_rhs) {
IntegerRangeInfo range_info = ToIntegerRangeInfo(
constant_initializer, const_init, compare_info.const_rhs);
integer_var_range_info_map_.Add(index, range_info);
}
break;
}
case BinaryOp::kGreaterThanEqual: {
// for (var index = const_init; index >= const_rhs; index--)
// Only `const_init >= const_rhs` is valid. The range of `index` is:
// [const_rhs, const_init]
// Note that in `GetBinaryToCompareLoopControlVariableInLoopBody()` we disallow
// `const_rhs` to be the minimum value of `i32` or `u32`, so:
// - `index - 1` won't be underflow as `const_init` cannot be less than `const_rhs`.
// - `index >= const_rhs` can correctly exit when `const_init - 1` is the minimum
// value of `i32` or `u32`.
if (!index_is_increasing && const_init >= compare_info.const_rhs) {
IntegerRangeInfo range_info = ToIntegerRangeInfo(
constant_initializer, compare_info.const_rhs, const_init);
integer_var_range_info_map_.Add(index, range_info);
}
break;
}
default:
break;
}
}
const Var* GetLoopControlVariableFromConstantInitializer(const Loop* loop) {
TINT_ASSERT(loop);
auto* init_block = loop->Initializer();
if (!init_block) {
return nullptr;
}
// Currently we only support the loop initializer of a simple for-loop, which only has two
// instructions
// - The first instruction is to initialize the loop control variable
// with a constant integer (signed or unsigned) value.
// - The second instruction is `next_iteration`
// e.g. for (var i = 0; ...)
if (init_block->Length() != 2u) {
return nullptr;
}
auto* var = init_block->Front()->As<Var>();
if (!var) {
return nullptr;
}
if (!init_block->Back()->As<NextIteration>()) {
return nullptr;
}
const auto* pointer = var->Result()->Type()->As<core::type::Pointer>();
if (!pointer->StoreType()->IsIntegerScalar()) {
return nullptr;
}
const auto* initializer = var->Initializer();
if (!initializer) {
return nullptr;
}
if (!initializer->As<Constant>()) {
return nullptr;
}
return var;
}
// Currently we only support the loop continuing of a simple for-loop, which only has 4
// instructions
/// - The first instruction is to load the loop control variable into a temporary variable.
/// - The second instruction is to add one or minus one to the temporary variable.
/// - The third instruction is to store the value of the temporary variable into the loop
/// control variable.
/// - The fourth instruction is `next_iteration`.
const Binary* GetBinaryToUpdateLoopControlVariableInContinuingBlock(
const Loop* loop,
const Var* loop_control_variable) {
TINT_ASSERT(loop);
TINT_ASSERT(loop_control_variable);
auto* continuing_block = loop->Continuing();
if (!continuing_block) {
return nullptr;
}
if (continuing_block->Length() != 4u) {
return nullptr;
}
// 1st instruction:
// %src = load %loop_control_variable
const auto* load_from_loop_control_variable = continuing_block->Instructions()->As<Load>();
if (!load_from_loop_control_variable) {
return nullptr;
}
if (load_from_loop_control_variable->From() != loop_control_variable->Result()) {
return nullptr;
}
// 2nd instruction:
// %dst = add %src, 1
// or %dst = add 1, %src
// or %dst = sub %src, 1
const auto* add_or_sub_from_loop_control_variable =
load_from_loop_control_variable->next->As<Binary>();
if (!add_or_sub_from_loop_control_variable) {
return nullptr;
}
const auto* src = load_from_loop_control_variable->Result();
const auto* lhs = add_or_sub_from_loop_control_variable->LHS();
const auto* rhs = add_or_sub_from_loop_control_variable->RHS();
switch (add_or_sub_from_loop_control_variable->Op()) {
case BinaryOp::kAdd: {
// %dst = add %src, 1
if (lhs == src && IsOne(rhs)) {
break;
}
// %dst = add 1, %src
if (rhs == src && IsOne(lhs)) {
break;
}
return nullptr;
}
case BinaryOp::kSubtract: {
// %dst = sub %src, 1
if (lhs == src && IsOne(rhs)) {
break;
}
return nullptr;
}
default:
return nullptr;
}
// 3rd instruction:
// store %loop_control_variable, %dst
const auto* store_into_loop_control_variable =
add_or_sub_from_loop_control_variable->next->As<Store>();
if (!store_into_loop_control_variable) {
return nullptr;
}
const auto* dst = add_or_sub_from_loop_control_variable->Result();
if (store_into_loop_control_variable->From() != dst) {
return nullptr;
}
if (store_into_loop_control_variable->To() != loop_control_variable->Result()) {
return nullptr;
}
// 4th instruction:
// next_iteration
if (!store_into_loop_control_variable->next->As<NextIteration>()) {
return nullptr;
}
return add_or_sub_from_loop_control_variable;
}
// Currently we only support the loop continuing of a simple for-loop which meets all the below
// requirements:
// - The loop control variable is only used as the parameter of the load instruction.
// - The first instruction is to load the loop control variable into a temporary variable.
// - The second instruction is a `compare` binary to compare the temporary variable with a
// constant value and save the result to a boolean variable.
// - The second instruction cannot be a comparison that will never return true.
// - The third instruction is an `ifelse` expression that uses the boolean variable got in the
// second instruction as the condition.
// - The true block of the above `ifelse` expression doesn't contain `exit_loop`.
// - The false block of the above `ifelse` expression only contains `exit_loop`.
// A valid `compare` binary instruction (the second instruction) can be in one of the below
// formats:
// 1. variable >= constant variable <= constant
// 2. variable > constant variable < constant
// 3. constant >= variable constant <= variable
// 4. constant > variable constant < variable
// This function analyzes the `compare` binary and returns both `variable` and `constant` in the
// equivalent format of format 1 and a pointer to the `compare` binary in a
// `CompareOpAndConstRHS`struct when the input `loop` meets all the above requirements.
// `CompareOpAndConstRHS.binary` will be set to nullptr otherwise.
CompareOpAndConstRHS GetCompareInfoOfLoopControlVariableInLoopBody(
const Loop* loop,
const Var* loop_control_variable) {
TINT_ASSERT(loop);
TINT_ASSERT(loop_control_variable);
auto* body_block = loop->Body();
CompareOpAndConstRHS compare_info = {};
// Reject any non-load instructions unless it is a store in the continuing block
const auto& uses = loop_control_variable->Result(0)->UsagesUnsorted();
for (auto& use : uses) {
if (use->instruction->Is<Load>()) {
continue;
}
if (use->instruction->Is<Store>() && use->instruction->Block() == loop->Continuing()) {
continue;
}
return compare_info;
}
// 1st instruction:
// %src = load %loop_control_variable
const auto* load_from_loop_control_variable = body_block->Instructions()->As<Load>();
if (!load_from_loop_control_variable) {
return compare_info;
}
if (load_from_loop_control_variable->From() != loop_control_variable->Result(0)) {
return compare_info;
}
// 2nd instruction:
// %condition:bool = lt(gt, lte, gte) %src, constant_value
// or %condition:bool = lt(gt, lte, gte) constant_value, %src
const auto* exit_condition_on_loop_control_variable =
load_from_loop_control_variable->next->As<Binary>();
if (!exit_condition_on_loop_control_variable) {
return compare_info;
}
BinaryOp op = exit_condition_on_loop_control_variable->Op();
auto* lhs = exit_condition_on_loop_control_variable->LHS();
auto* rhs = exit_condition_on_loop_control_variable->RHS();
switch (op) {
case BinaryOp::kLessThan:
case BinaryOp::kGreaterThan:
case BinaryOp::kLessThanEqual:
case BinaryOp::kGreaterThanEqual: {
if (IsConstantInteger(rhs) && lhs == load_from_loop_control_variable->Result(0)) {
break;
}
if (IsConstantInteger(lhs) && rhs == load_from_loop_control_variable->Result(0)) {
break;
}
return compare_info;
}
default:
return compare_info;
}
const bool is_signed = lhs->Type()->IsSignedIntegerScalar();
auto const_i32 = [](const Value* val) {
return val->As<Constant>()->Value()->ValueAs<int32_t>();
};
auto const_u32 = [](const Value* val) {
return val->As<Constant>()->Value()->ValueAs<uint32_t>();
};
// Check and extract necessary information from `binary`.
// Note that we should early return when the comparison will never return true.
// e.g. for (...; i < 0u; ...) // The loop body will never be executed.
// We should also early return when the comparison will always return true, which means the
// loop exit condition takes no effect and the loop control variable can actually take all
// the numbers.
// e.g. for (i = 100u; i >= 0u; i--) // `i` can be any u32 value instead of [0u, 100u]
if (IsConstantInteger(rhs)) {
// Handle `binary` in the format of `variable op const_rhs`
int64_t const_rhs = GetValueFromConstant(rhs->As<Constant>());
switch (op) {
case BinaryOp::kLessThan: {
// variable < std::numeric_limits<uint32_t>::min()
if (!is_signed && const_u32(rhs) == u32::kLowestValue) {
return compare_info;
}
// variable < std::numeric_limits<int32_t>::min()
if (is_signed && const_i32(rhs) == i32::kLowestValue) {
return compare_info;
}
// variable < constant => variable <= constant - 1
// `const_rhs - 1` will always be safe after the above checks.
compare_info.op = BinaryOp::kLessThanEqual;
compare_info.const_rhs = const_rhs - 1;
break;
}
case BinaryOp::kGreaterThan: {
// variable > std::numeric_limits<uint32_t>::max()
if (!is_signed && const_u32(rhs) == u32::kHighestValue) {
return compare_info;
}
// variable > std::numeric_limits<int32_t>::max()
if (is_signed && const_i32(rhs) == i32::kHighestValue) {
return compare_info;
}
// variable > constant => variable >= constant + 1
// `const_rhs` will always be safe after the above checks.
compare_info.op = BinaryOp::kGreaterThanEqual;
compare_info.const_rhs = const_rhs + 1;
break;
}
case BinaryOp::kLessThanEqual: {
// variable <= std::numeric_limits<uint32_t>::max()
if (!is_signed && const_u32(rhs) == u32::kHighestValue) {
return compare_info;
}
// variable <= std::numeric_limits<int32_t>::max()
if (is_signed && const_i32(rhs) == i32::kHighestValue) {
return compare_info;
}
compare_info.op = op;
compare_info.const_rhs = const_rhs;
break;
}
case BinaryOp::kGreaterThanEqual: {
// variable >= std::numeric_limits<uint32_t>::min()
if (!is_signed && const_u32(rhs) == u32::kLowestValue) {
return compare_info;
}
// variable >= std::numeric_limits<int32_t>::min()
if (is_signed && const_i32(rhs) == i32::kLowestValue) {
return compare_info;
}
compare_info.op = op;
compare_info.const_rhs = const_rhs;
break;
}
default:
TINT_UNREACHABLE();
}
} else {
// Handle `binary` in the format of `const_lhs op variable`
TINT_ASSERT(IsConstantInteger(lhs));
int64_t const_lhs = GetValueFromConstant(lhs->As<Constant>());
switch (op) {
case BinaryOp::kLessThan: {
// std::numeric_limits<uint32_t>::max() < variable
if (!is_signed && const_u32(lhs) == u32::kHighestValue) {
return compare_info;
}
// std::numeric_limits<int32_t>::max() < variable
if (is_signed && const_i32(lhs) == i32::kHighestValue) {
return compare_info;
}
// constant < variable => variable > constant => variable >= constant + 1
// `const_lhs + 1` will always be safe after the above checks.
compare_info.op = BinaryOp::kGreaterThanEqual;
compare_info.const_rhs = const_lhs + 1;
break;
}
case BinaryOp::kGreaterThan: {
// std::numeric_limits<uint32_t>::min() > variable
if (!is_signed && const_u32(lhs) == u32::kLowestValue) {
return compare_info;
}
// std::numeric_limits<int32_t>::min() > variable
if (is_signed && const_i32(lhs) == i32::kLowestValue) {
return compare_info;
}
// constant > variable => variable < constant => variable <= constant - 1
// `const_lhs - 1` will always be safe after the above checks.
compare_info.op = BinaryOp::kLessThanEqual;
compare_info.const_rhs = const_lhs - 1;
break;
}
case BinaryOp::kLessThanEqual: {
// std::numeric_limits<uint32_t>::min() <= variable
if (!is_signed && const_u32(lhs) == u32::kLowestValue) {
return compare_info;
}
// std::numeric_limits<int32_t>::min() <= variable
if (is_signed && const_i32(lhs) == i32::kLowestValue) {
return compare_info;
}
// constant <= variable => variable >= constant
compare_info.op = BinaryOp::kGreaterThanEqual;
compare_info.const_rhs = const_lhs;
break;
}
case BinaryOp::kGreaterThanEqual: {
// std::numeric_limits<uint32_t>::max() >= variable
if (!is_signed && const_u32(lhs) == u32::kHighestValue) {
return compare_info;
}
// std::numeric_limits<int32_t>::max() >= variable
if (is_signed && const_i32(lhs) == i32::kHighestValue) {
return compare_info;
}
// constant >= variable => variable <= constant
compare_info.op = BinaryOp::kLessThanEqual;
compare_info.const_rhs = const_lhs;
break;
}
default:
TINT_UNREACHABLE();
}
}
// 3rd instruction:
// if %condition [t: $true, f: $false] {
// $true: {
// // Maybe some other instructions
// exit_if
// }
// $false: { exit_loop }
// }
const auto* if_on_exit_condition = exit_condition_on_loop_control_variable->next->As<If>();
if (!if_on_exit_condition) {
return compare_info;
}
if (if_on_exit_condition->Condition() !=
exit_condition_on_loop_control_variable->Result(0)) {
return compare_info;
}
if (!if_on_exit_condition->True()->Terminator()->As<ExitIf>()) {
return compare_info;
}
const auto* front_inst = if_on_exit_condition->False()->Front();
if (!front_inst || !front_inst->As<ExitLoop>()) {
return compare_info;
}
// Set `compare_info.binary` after the loop passes all the above checks.
compare_info.binary = exit_condition_on_loop_control_variable;
return compare_info;
}
private:
void AnalyzeFunctionParameters(const Function* func) {
for (const auto* param : func->Params()) {
if (!param->Type()->IsIntegerScalarOrVector()) {
return;
}
// Currently we only support the query of ranges of `local_invocation_id` or
// `local_invocation_index`.
if (!param->Builtin()) {
return;
}
switch (*param->Builtin()) {
case BuiltinValue::kLocalInvocationIndex: {
// We shouldn't be trying to use range analysis on a module that has
// non-constant workgroup sizes, since we will always have replaced pipeline
// overrides with constant values early in the pipeline.
TINT_ASSERT(func->WorkgroupSizeAsConst().has_value());
std::array<uint32_t, 3> workgroup_size = func->WorkgroupSizeAsConst().value();
uint64_t max_bound =
workgroup_size[0] * workgroup_size[1] * workgroup_size[2] - 1u;
constexpr uint64_t kMinBound = 0;
integer_function_param_range_info_map_.Add(
param,
Vector<IntegerRangeInfo, 3>({IntegerRangeInfo(kMinBound, max_bound)}));
break;
}
case BuiltinValue::kLocalInvocationId: {
TINT_ASSERT(func->WorkgroupSizeAsConst().has_value());
std::array<uint32_t, 3> workgroup_size = func->WorkgroupSizeAsConst().value();
constexpr uint64_t kMinBound = 0;
Vector<IntegerRangeInfo, 3> integerRanges;
for (uint32_t size_x_y_z : workgroup_size) {
integerRanges.Push({kMinBound, size_x_y_z - 1u});
}
integer_function_param_range_info_map_.Add(param, integerRanges);
}
break;
default:
break;
}
}
}
IntegerRangeInfo ComputeIntegerRangeForBinaryAdd(const IntegerRangeInfo& lhs,
const IntegerRangeInfo& rhs) {
// Add two 32-bit signed integer values saved in int64_t. Return {} when either overflow or
// underflow happens.
auto SafeAddI32 = [](int64_t a, int64_t b) -> std::optional<int64_t> {
TINT_ASSERT(a >= i32::kLowestValue && a <= i32::kHighestValue);
TINT_ASSERT(b >= i32::kLowestValue && b <= i32::kHighestValue);
int64_t sum = a + b;
if (sum > i32::kHighestValue || sum < i32::kLowestValue) {
return {};
}
return sum;
};
// No-overflow add between two 32-bit unsigned integer values saved in uint64_t. Return {}
// when overflow happens.
auto SafeAddU32 = [](uint64_t a, uint64_t b) -> std::optional<uint64_t> {
TINT_ASSERT(a <= u32::kHighestValue);
TINT_ASSERT(b <= u32::kHighestValue);
uint64_t sum = a + b;
if (sum > u32::kHighestValue) {
return {};
}
return sum;
};
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(lhs.range)) {
auto lhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(lhs.range);
auto rhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(rhs.range);
// [min1, max1] + [min2, max2] => [min1 + min2, max1 + max2]
std::optional<int64_t> min_bound = SafeAddI32(lhs_i32.min_bound, rhs_i32.min_bound);
std::optional<int64_t> max_bound = SafeAddI32(lhs_i32.max_bound, rhs_i32.max_bound);
if (!min_bound.has_value() || !max_bound.has_value()) {
return {};
}
return IntegerRangeInfo(*min_bound, *max_bound);
} else {
auto lhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(lhs.range);
auto rhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(rhs.range);
// [min1, max1] + [min2, max2] => [min1 + min2, max1 + max2]
std::optional<uint64_t> min_bound = SafeAddU32(lhs_u32.min_bound, rhs_u32.min_bound);
std::optional<uint64_t> max_bound = SafeAddU32(lhs_u32.max_bound, rhs_u32.max_bound);
if (!min_bound || !max_bound) {
return {};
}
return IntegerRangeInfo(*min_bound, *max_bound);
}
}
IntegerRangeInfo ComputeIntegerRangeForBinarySubtract(const IntegerRangeInfo& lhs,
const IntegerRangeInfo& rhs) {
// Subtract two 32-bit signed integer values saved in int64_t. Return {} when either
// overflow or underflow happens.
auto SafeSubtractI32 = [](int64_t a, int64_t b) -> std::optional<int64_t> {
TINT_ASSERT(a >= i32::kLowestValue && a <= i32::kHighestValue);
TINT_ASSERT(b >= i32::kLowestValue && b <= i32::kHighestValue);
int64_t diff = a - b;
if (diff > i32::kHighestValue || diff < i32::kLowestValue) {
return {};
}
return diff;
};
// No-underflow Subtract between two 32-bit unsigned integer values saved in uint64_t.
// Return {} when underflow happens.
auto SafeSubtractU32 = [](uint64_t a, uint64_t b) -> std::optional<uint64_t> {
TINT_ASSERT(a <= u32::kHighestValue);
TINT_ASSERT(b <= u32::kHighestValue);
if (a < b) {
return {};
}
return a - b;
};
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(lhs.range)) {
auto lhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(lhs.range);
auto rhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(rhs.range);
// [min1, max1] - [min2, max2] => [min1 - max2, max1 - min2]
std::optional<int64_t> min_bound =
SafeSubtractI32(lhs_i32.min_bound, rhs_i32.max_bound);
std::optional<int64_t> max_bound =
SafeSubtractI32(lhs_i32.max_bound, rhs_i32.min_bound);
if (!min_bound.has_value() || !max_bound.has_value()) {
return {};
}
return IntegerRangeInfo(*min_bound, *max_bound);
} else {
auto lhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(lhs.range);
auto rhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(rhs.range);
// [min1, max1] - [min2, max2] => [min1 - max2, max1 - min2]
std::optional<uint64_t> min_bound =
SafeSubtractU32(lhs_u32.min_bound, rhs_u32.max_bound);
std::optional<uint64_t> max_bound =
SafeSubtractU32(lhs_u32.max_bound, rhs_u32.min_bound);
if (!min_bound || !max_bound) {
return {};
}
return IntegerRangeInfo(*min_bound, *max_bound);
}
}
IntegerRangeInfo ComputeIntegerRangeForBinaryMultiply(const IntegerRangeInfo& lhs,
const IntegerRangeInfo& rhs) {
// Multiply two 32-bit non-negative signed integer values saved in int64_t. Return {} when
// overflow happens.
auto SafeMultiplyNonNegativeI32 = [](int64_t a, int64_t b) -> std::optional<int64_t> {
TINT_ASSERT(a >= 0 && a <= i32::kHighestValue);
TINT_ASSERT(b >= 0 && b <= i32::kHighestValue);
int64_t multiply = a * b;
if (multiply > i32::kHighestValue) {
return {};
}
return multiply;
};
// No-underflow multiply two 32-bit unsigned integer values saved in uint64_t.
// Return {} when underflow happens.
auto SafeMultiplyU32 = [](uint64_t a, uint64_t b) -> std::optional<uint64_t> {
TINT_ASSERT(a <= u32::kHighestValue);
TINT_ASSERT(b <= u32::kHighestValue);
uint64_t multiply = a * b;
if (multiply > u32::kHighestValue) {
return {};
}
return multiply;
};
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(lhs.range)) {
auto lhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(lhs.range);
auto rhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(rhs.range);
// Currently we only handle multiplication with non-negative values, which means
// 0 <= min_bound <= max_bound
if (lhs_i32.min_bound < 0 || rhs_i32.min_bound < 0) {
return {};
}
// min1 >= 0, min2 >= 0
// [min1, max1] * [min2, max2] => [min1 * min2, max1 * max2]
std::optional<int64_t> min_bound =
SafeMultiplyNonNegativeI32(lhs_i32.min_bound, rhs_i32.min_bound);
std::optional<int64_t> max_bound =
SafeMultiplyNonNegativeI32(lhs_i32.max_bound, rhs_i32.max_bound);
if (!min_bound.has_value() || !max_bound.has_value()) {
return {};
}
return IntegerRangeInfo(*min_bound, *max_bound);
} else {
auto lhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(lhs.range);
auto rhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(rhs.range);
// [min1, max1] * [min2, max2] => [min1 * min2, max1 * max2]
std::optional<uint64_t> min_bound =
SafeMultiplyU32(lhs_u32.min_bound, rhs_u32.min_bound);
std::optional<uint64_t> max_bound =
SafeMultiplyU32(lhs_u32.max_bound, rhs_u32.max_bound);
if (!min_bound || !max_bound) {
return {};
}
return IntegerRangeInfo(*min_bound, *max_bound);
}
}
IntegerRangeInfo ComputeIntegerRangeForBinaryDivide(const IntegerRangeInfo& lhs,
const IntegerRangeInfo& rhs) {
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(lhs.range)) {
auto lhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(lhs.range);
auto rhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(rhs.range);
// Currently we require `lhs` must be non-negative, and `rhs` must be positive.
// 0 <= lhs.min_bound <= lhs.max_bound
if (lhs_i32.min_bound < 0) {
return {};
}
// 0 < rhs.min_bound <= rhs.max_bound
if (rhs_i32.min_bound <= 0) {
return {};
}
// min1 >= 0, min2 > 0
// [min1, max1] / [min2, max2] => [min1 / max2, max1 / min2]
int64_t min_bound = lhs_i32.min_bound / rhs_i32.max_bound;
int64_t max_bound = lhs_i32.max_bound / rhs_i32.min_bound;
return IntegerRangeInfo(min_bound, max_bound);
} else {
auto lhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(lhs.range);
auto rhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(rhs.range);
// `rhs` must be positive.
if (rhs_u32.min_bound == 0) {
return {};
}
// [min1, max1] / [min2, max2] => [min1 / max2, max1 / min2]
uint64_t min_bound = lhs_u32.min_bound / rhs_u32.max_bound;
uint64_t max_bound = lhs_u32.max_bound / rhs_u32.min_bound;
return IntegerRangeInfo(min_bound, max_bound);
}
}
IntegerRangeInfo ComputeIntegerRangeForBinaryShiftLeft(const IntegerRangeInfo& lhs,
const IntegerRangeInfo& rhs) {
auto rhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(rhs.range);
// rhs_u32 must be less than the bit width of i32 and u32 (32):
// rhs_u32.min_bound <= rhs_u32.max_bound < 32
if (rhs_u32.max_bound >= 32) {
return {};
}
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(lhs.range)) {
auto lhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(lhs.range);
// Currently we require `lhs` must be non-negative.
// 0 <= lhs.min_bound <= lhs.max_bound
if (lhs_i32.min_bound < 0) {
return {};
}
// [min1, max1] << [min2, max2] => [min1 << min2, max1 << max2]
// `max_bound` (as a uint64_t) won't be overflow because `rhs_u32.max_bound` < 32.
uint64_t max_bound = static_cast<uint64_t>(lhs_i32.max_bound) << rhs_u32.max_bound;
// Overflow an `i32` is not allowed, which means:
// min_bound <= max_bound <= i32::kHighestValue
if (max_bound > static_cast<uint64_t>(i32::kHighestValue)) {
return {};
}
int64_t min_bound = lhs_i32.min_bound << rhs_u32.min_bound;
return IntegerRangeInfo(min_bound, static_cast<int64_t>(max_bound));
} else {
auto lhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(lhs.range);
// `max_bound` (as a uint64_t) won't be overflow because `rhs_u32.max_bound` < 32.
uint64_t max_bound = lhs_u32.max_bound << rhs_u32.max_bound;
// Overflow a `u32` is not allowed, which means:
// min_bound <= max_bound <= u32::kHighestValue
if (max_bound > u32::kHighestValue) {
return {};
}
uint64_t min_bound = lhs_u32.min_bound << rhs_u32.min_bound;
return IntegerRangeInfo(min_bound, max_bound);
}
}
IntegerRangeInfo ComputeIntegerRangeForBinaryShiftRight(const IntegerRangeInfo& lhs,
const IntegerRangeInfo& rhs) {
auto rhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(rhs.range);
// rhs_u32 must be less than the bit width of i32 and u32 (32):
// rhs_u32.min_bound <= rhs_u32.max_bound < 32
if (rhs_u32.max_bound >= 32) {
return {};
}
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(lhs.range)) {
auto lhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(lhs.range);
// Currently we require `lhs` must be non-negative.
// 0 <= lhs.min_bound <= lhs.max_bound
if (lhs_i32.min_bound < 0) {
return {};
}
// [min1, max1] >> [min2, max2] => [min1 >> max2, max1 >> min2]
int64_t min_bound = lhs_i32.min_bound >> rhs_u32.max_bound;
int64_t max_bound = lhs_i32.max_bound >> rhs_u32.min_bound;
return IntegerRangeInfo(min_bound, max_bound);
} else {
auto lhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(lhs.range);
uint64_t min_bound = lhs_u32.min_bound >> rhs_u32.max_bound;
uint64_t max_bound = lhs_u32.max_bound >> rhs_u32.min_bound;
return IntegerRangeInfo(min_bound, max_bound);
}
}
IntegerRangeInfo ComputeIntegerRangeForBinaryModulo(const Value* lhs,
const IntegerRangeInfo& rhs_range) {
TINT_ASSERT(rhs_range.IsValid());
if (!lhs->Type()->IsIntegerScalar()) {
return {};
}
IntegerRangeInfo lhs_range = GetInfo(lhs);
if (!lhs_range.IsValid()) {
lhs_range = GetFullRangeWithSameIntegerRangeInfoType(rhs_range);
}
// Suppose the range of `lhs` is [a, b], `a` and `b` are 64-bit signed positive integers
// and no greater than u32::kHighestValue.
// .
// `rhs` is a 64-bit signed constant positive integer.
// Let ra = a % rhs (0 <= ra <= rhs - 1), rb = b % rhs (0 <= rb <= rhs - 1)
// qa = a / rhs, qb = b / rhs
// Then a = qa * rhs + ra, b = qb * rhs + rb
//
// All the below arithmetic operations are done in the range of 64-bit signed integers so
// there won't be any overflow or underflow issues.
//
// I. We can ignore the case of qa > qb.
// Proof:
// Let qa = qb + d (d >= 1), then
// a = (qb + d) * rhs + ra
// = (qb * rhs + d * rhs) + ra
// = (qb * rhs + rb) - rb + (d * rhs + ra)
// = b - rb + (d * rhs) + ra
// >= b - rb + rhs + (ra) // d >= 1
// >= b + (rhs - rb) // ra >= 0
// > b (impossible) // rhs > rb
//
// II. When qa < qb, the range of `lhs % rhs` is [0, rhs- 1].
// Proof:
// Let qb = qa + d (d >= 1), then
// b = (qa + d) * rhs + rb
// = (qa * rhs + d * rhs) + rb
// = qa * rhs + (ra - ra) + d * rhs + rb
// = (qa * rhs + ra) + rb - ra + d * rhs
// = a + rb - ra + d * rhs
// >= a + (rb) - ra + rhs // d >= 1
//
// (1) rb >= 0
// => b >= a - ra + rhs
// => b >= (a) + (rhs - ra) > a // rhs > ra
// => b >= (qa * rhs + ra) + (rhs - ra) > a
// => b >= (qa + 1) * rhs > a
// So there must exist a k = ((qa + 1) * rhs) in (a, b] that satisfies `k % rhs == 0`
//
// (2) k = (qa + 1) * rhs > a
// k > a, a >= 0 => k - 1 >= 0
// Then b >= k
// > k - 1 = (qa + 1) * rhs - 1
// = qa * rhs + (rhs - 1) // rhs - 1 >= ra
// >= qa * rhs + ra = a
// So there must exist a (k - 1) = ((qa + 1) * rhs - 1) in [a, b) that satisfies
// `(k - 1) % rhs == 0`.
//
// Based on (1) and (2), we can conclude the range of `lhs % rhs` is [0, rhs - 1].
//
// III. When qa == qb, the range of `lhs % rhs` is `[ra, rb]`.
// Proof:
// let q = qa = qb,
// then a = q * rhs + ra, b = q * rhs + rb
// a = q * rhs + ra <= q * rhs + rb = b
// => ra <= rb
// Arbitrarily choose x in range [a, b], let rx = x % rhs, qx = x / rhs
// x = qx * rhs + rx (0 <= rx < rhs)
// a <= x <= b
// => (q * rhs + ra) <= (qx * rhs + rx) <= (q * rhs + rb)
//
// (1) q * rhs + ra <= qx * rhs + rx
// ra <= qx * rhs + rx - q * rhs // ra >= 0
// 0 <= ra <= qx * rhs + rx - q * rhs
// 0 <= qx * rhs + rx - q * rhs
// q * rhs - qx * rhs <= rx < rhs
// q * rhs - qx * rhs < rhs // rhs > 0
// q - qx < 1
// qx > q - 1
//
// (2) qx * rhs + rx <= q * rhs + rb
// qx * rhs + rx - q * rhs <= rb < rhs
// qx * rhs + rx - q * rhs < rhs
// rx < rhs + q * rhs - qx * rhs // rx >= 0
// 0 <= rx < rhs + q * rhs - qx * rhs
// 0 < rhs + q * rhs - qx * rhs // rhs > 0
// 0 < 1 + q - qx
// qx < q + 1
//
// Based on (1) and (2), qx == q
// Then (q * rhs + ra) <= (q * rhs + rx) <= (q * rhs + rb)
// => ra <= rx <= rb
// The range of `lhs % rhs` is [ra, rb].
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(rhs_range.range)) {
// Currently we require `lhs` must be non-negative.
auto lhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(lhs_range.range);
if (lhs_i32.min_bound < 0) {
return {};
}
// Currently we only accept `rhs` as a constant positive integer.
auto rhs_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(rhs_range.range);
if (rhs_i32.min_bound != rhs_i32.max_bound) {
return {};
}
int64_t rhs_const = rhs_i32.min_bound;
if (rhs_const <= 0) {
return {};
}
// Let:
// lhs_max = q_max * rhs_const + r_max; // 0 <= r_max < rhs_const
// lhs_min = q_min * rhs_const + r_min; // 0 <= r_min < rhs_const
if (lhs_i32.min_bound / rhs_const == lhs_i32.max_bound / rhs_const) {
// if q_min == q_max (matches case III):
// The range of `lhs % rhs` is [r_min, r_max].
int64_t min_bound = lhs_i32.min_bound % rhs_const;
int64_t max_bound = lhs_i32.max_bound % rhs_const;
TINT_ASSERT(min_bound <= max_bound);
return IntegerRangeInfo(min_bound, max_bound);
} else {
// Otherwise (q_min < q_max, matches case II):
// The range of `lhs % rhs` is [0, rhs - 1] (the whole remainder range).
return IntegerRangeInfo(0, rhs_const - 1);
}
} else {
// Currently we only accept `rhs` as a constant positive integer.
auto rhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(rhs_range.range);
if (rhs_u32.min_bound != rhs_u32.max_bound) {
return {};
}
uint64_t rhs_const = rhs_u32.min_bound;
if (rhs_const == 0) {
return {};
}
// `lhs` must not be negative so we don't need to do the check on it.
// Let:
// lhs_max = q_max * rhs_const + r_max; // 0 <= r_max < rhs_const
// lhs_min = q_min * rhs_const + r_min; // 0 <= r_min < rhs_const
auto lhs_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(lhs_range.range);
if (lhs_u32.min_bound / rhs_const == lhs_u32.max_bound / rhs_const) {
// if q_min == q_max (matches case III):
// The range of `lhs % rhs` is [r_min, r_max].
uint64_t min_bound = lhs_u32.min_bound % rhs_const;
uint64_t max_bound = lhs_u32.max_bound % rhs_const;
TINT_ASSERT(min_bound <= max_bound);
return IntegerRangeInfo(min_bound, max_bound);
} else {
// Otherwise (q_min < q_max, matches case II):
// The range of `lhs % rhs` is [0, rhs - 1] (the whole remainder range).
return IntegerRangeInfo(0, rhs_const - 1);
}
}
}
IntegerRangeInfo ComputeIntegerRangeForBuiltinMin(const CoreBuiltinCall* call) {
TINT_ASSERT(call->Operands().Length() == 2u);
TINT_ASSERT(call->Operand(0)->Type()->IsIntegerScalar());
TINT_ASSERT(call->Operand(1)->Type()->IsIntegerScalar());
IntegerRangeInfo range1 = GetInfo(call->Operand(0));
IntegerRangeInfo range2 = GetInfo(call->Operand(1));
if (!range1.IsValid() && !range2.IsValid()) {
return {};
}
if (!range1.IsValid()) {
range1 = GetFullRangeWithSameIntegerRangeInfoType(range2);
}
if (!range2.IsValid()) {
range2 = GetFullRangeWithSameIntegerRangeInfoType(range1);
}
// range1: [min1, max1] range2: [min2, max2]
// The minimum value of (min(range1, range2)) is min(min1, min2) and
// The maximum value of (min(range1, range2)) is min(max1, max2).
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(range1.range)) {
TINT_ASSERT(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(range2.range));
auto range1_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(range1.range);
auto range2_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(range2.range);
// When the range is all i32 or u32, we will treat it as an invalid range.
int64_t min_bound = std::min(range1_i32.min_bound, range2_i32.min_bound);
int64_t max_bound = std::min(range1_i32.max_bound, range2_i32.max_bound);
if (min_bound == i32::kLowestValue && max_bound == i32::kHighestValue) {
return {};
}
return IntegerRangeInfo(min_bound, max_bound);
} else {
TINT_ASSERT(
std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(range2.range));
auto range1_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(range1.range);
auto range2_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(range2.range);
// When the range is all i32 or u32, we will treat it as an invalid range.
uint64_t min_bound = std::min(range1_u32.min_bound, range2_u32.min_bound);
uint64_t max_bound = std::min(range1_u32.max_bound, range2_u32.max_bound);
if (min_bound == u32::kLowestValue && max_bound == u32::kHighestValue) {
return {};
}
return IntegerRangeInfo(min_bound, max_bound);
}
}
IntegerRangeInfo ComputeIntegerRangeForBuiltinMax(const CoreBuiltinCall* call) {
TINT_ASSERT(call->Operands().Length() == 2u);
TINT_ASSERT(call->Operand(0)->Type()->IsIntegerScalar());
TINT_ASSERT(call->Operand(1)->Type()->IsIntegerScalar());
IntegerRangeInfo range1 = GetInfo(call->Operand(0));
IntegerRangeInfo range2 = GetInfo(call->Operand(1));
if (!range1.IsValid() && !range2.IsValid()) {
return {};
}
if (!range1.IsValid()) {
range1 = GetFullRangeWithSameIntegerRangeInfoType(range2);
}
if (!range2.IsValid()) {
range2 = GetFullRangeWithSameIntegerRangeInfoType(range1);
}
// range1: [min1, max1] range2: [min2, max2]
// The minimum value of (max(range1, range2)) is max(min1, min2) and
// The maximum value of (max(range1, range2)) is max(max1, max2).
if (std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(range1.range)) {
TINT_ASSERT(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(range2.range));
auto range1_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(range1.range);
auto range2_i32 = std::get<IntegerRangeInfo::SignedIntegerRange>(range2.range);
// When the range is all i32 or u32, we will treat it as an invalid range.
int64_t min_bound = std::max(range1_i32.min_bound, range2_i32.min_bound);
int64_t max_bound = std::max(range1_i32.max_bound, range2_i32.max_bound);
if (min_bound == i32::kLowestValue && max_bound == i32::kHighestValue) {
return {};
}
return IntegerRangeInfo(min_bound, max_bound);
} else {
TINT_ASSERT(
std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(range2.range));
auto range1_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(range1.range);
auto range2_u32 = std::get<IntegerRangeInfo::UnsignedIntegerRange>(range2.range);
// When the range is all i32 or u32, we will treat it as an invalid range.
uint64_t min_bound = std::max(range1_u32.min_bound, range2_u32.min_bound);
uint64_t max_bound = std::max(range1_u32.max_bound, range2_u32.max_bound);
if (min_bound == u32::kLowestValue && max_bound == u32::kHighestValue) {
return {};
}
return IntegerRangeInfo(min_bound, max_bound);
}
}
Hashmap<const FunctionParam*, Vector<IntegerRangeInfo, 3>, 4>
integer_function_param_range_info_map_;
Hashmap<const Var*, IntegerRangeInfo, 8> integer_var_range_info_map_;
Hashmap<const Constant*, IntegerRangeInfo, 8> integer_constant_range_info_map_;
Hashmap<const Binary*, IntegerRangeInfo, 8> integer_binary_range_info_map_;
Hashmap<const Convert*, IntegerRangeInfo, 8> integer_convert_range_info_map_;
Hashmap<const CoreBuiltinCall*, IntegerRangeInfo, 8> integer_core_builtin_call_range_info_map_;
};
IntegerRangeAnalysis::IntegerRangeAnalysis(Module* ir_module)
: impl_(new IntegerRangeAnalysisImpl(ir_module)) {}
IntegerRangeAnalysis::~IntegerRangeAnalysis() = default;
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const FunctionParam* param, uint32_t index) {
return impl_->GetInfo(param, index);
}
const Var* IntegerRangeAnalysis::GetLoopControlVariableFromConstantInitializerForTest(
const Loop* loop) {
return impl_->GetLoopControlVariableFromConstantInitializer(loop);
}
const Binary* IntegerRangeAnalysis::GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(
const Loop* loop,
const Var* loop_control_variable) {
return impl_->GetBinaryToUpdateLoopControlVariableInContinuingBlock(loop,
loop_control_variable);
}
const Binary* IntegerRangeAnalysis::GetBinaryToCompareLoopControlVariableInLoopBodyForTest(
const Loop* loop,
const Var* loop_control_variable) {
return impl_->GetCompareInfoOfLoopControlVariableInLoopBody(loop, loop_control_variable).binary;
}
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const Var* var) {
return impl_->GetInfo(var);
}
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const Load* load) {
return impl_->GetInfo(load);
}
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const Access* access) {
return impl_->GetInfo(access);
}
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const Constant* constant) {
return impl_->GetInfo(constant);
}
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const Value* value) {
return impl_->GetInfo(value);
}
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const Binary* binary) {
return impl_->GetInfo(binary);
}
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const Let* let) {
return impl_->GetInfo(let);
}
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const Convert* convert) {
return impl_->GetInfo(convert);
}
IntegerRangeInfo IntegerRangeAnalysis::GetInfo(const CoreBuiltinCall* call) {
return impl_->GetInfo(call);
}
} // namespace tint::core::ir::analysis