Range Analysis: Compute range of `Binary` with `>>` operator
This patch computes the range of a `Binary` with `>>`
(shift-right) operator when the `lhs` is a non-negative integer.
Bug: 348701956
Test: tint_unittests
Change-Id: I42d0e4ff542a6feb7b6e1f929c6fffa8338b2bed
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/245776
Commit-Queue: Jiawei Shao <jiawei.shao@intel.com>
Reviewed-by: James Price <jrprice@google.com>
diff --git a/src/tint/lang/core/ir/analysis/integer_range_analysis.cc b/src/tint/lang/core/ir/analysis/integer_range_analysis.cc
index e6fa91f..c316b63 100644
--- a/src/tint/lang/core/ir/analysis/integer_range_analysis.cc
+++ b/src/tint/lang/core/ir/analysis/integer_range_analysis.cc
@@ -284,6 +284,9 @@
case BinaryOp::kShiftLeft:
return ComputeAndCacheIntegerRangeForBinaryShiftLeft(binary, range_lhs, range_rhs);
+ case BinaryOp::kShiftRight:
+ return ComputeAndCacheIntegerRangeForBinaryShiftRight(binary, range_lhs, range_rhs);
+
default:
return nullptr;
}
@@ -1095,6 +1098,45 @@
}
}
+ const IntegerRangeInfo* ComputeAndCacheIntegerRangeForBinaryShiftRight(
+ const Binary* binary,
+ 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 nullptr;
+ }
+
+ 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 nullptr;
+ }
+
+ // [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;
+
+ auto result =
+ integer_binary_range_info_map_.Add(binary, IntegerRangeInfo(min_bound, max_bound));
+ return &result.value;
+ } 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;
+ auto result =
+ integer_binary_range_info_map_.Add(binary, IntegerRangeInfo(min_bound, max_bound));
+ return &result.value;
+ }
+ }
+
Hashmap<const FunctionParam*, Vector<IntegerRangeInfo, 3>, 4>
integer_function_param_range_info_map_;
Hashmap<const Var*, IntegerRangeInfo, 8> integer_var_range_info_map_;
diff --git a/src/tint/lang/core/ir/analysis/integer_range_analysis_test.cc b/src/tint/lang/core/ir/analysis/integer_range_analysis_test.cc
index 8bb0701..404ebe6 100644
--- a/src/tint/lang/core/ir/analysis/integer_range_analysis_test.cc
+++ b/src/tint/lang/core/ir/analysis/integer_range_analysis_test.cc
@@ -13774,5 +13774,801 @@
ASSERT_EQ(nullptr, info);
}
+TEST_F(IR_IntegerRangeAnalysisTest, ShiftRight_Success_U32_NonZero) {
+ Var* idx = nullptr;
+ Binary* shiftRight = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ auto* loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 4
+ idx = b.Var("idx", 4_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // idx < 9
+ auto* binary = b.LessThan<bool>(b.Load(idx), 9_u);
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+
+ Var* idy = nullptr;
+ auto* loop2 = b.Loop();
+ b.Append(loop2->Initializer(), [&] {
+ // idy = 1
+ idy = b.Var("idy", 1_u);
+ b.NextIteration(loop2);
+ });
+ b.Append(loop2->Body(), [&] {
+ // idy < 3
+ auto* binary_inner = b.LessThan<bool>(b.Load(idy), 3_u);
+ auto* ifelse_inner = b.If(binary_inner);
+ b.Append(ifelse_inner->True(), [&] { b.ExitIf(ifelse_inner); });
+ b.Append(ifelse_inner->False(), [&] { b.ExitLoop(loop2); });
+ auto* loadx = b.Load(idx);
+ auto* loady = b.Load(idy);
+ // shiftRight = idx >> idy
+ shiftRight = b.ShiftRight<u32>(loadx, loady);
+ b.Continue(loop2);
+ });
+ b.Append(loop2->Continuing(), [&] {
+ // idy++
+ b.Store(idy, b.Add<u32>(b.Load(idy), 1_u));
+ b.NextIteration(loop2);
+ });
+
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx++
+ b.Store(idx, b.Add<u32>(b.Load(idx), 1_u));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func():void {
+ $B1: {
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, u32, read_write> = var 4u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lt %3, 9u
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ loop [i: $B7, b: $B8, c: $B9] { # loop_2
+ $B7: { # initializer
+ %idy:ptr<function, u32, read_write> = var 1u
+ next_iteration # -> $B8
+ }
+ $B8: { # body
+ %6:u32 = load %idy
+ %7:bool = lt %6, 3u
+ if %7 [t: $B10, f: $B11] { # if_2
+ $B10: { # true
+ exit_if # if_2
+ }
+ $B11: { # false
+ exit_loop # loop_2
+ }
+ }
+ %8:u32 = load %idx
+ %9:u32 = load %idy
+ %10:u32 = shr %8, %9
+ continue # -> $B9
+ }
+ $B9: { # continuing
+ %11:u32 = load %idy
+ %12:u32 = add %11, 1u
+ store %idy, %12
+ next_iteration # -> $B8
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %13:u32 = load %idx
+ %14:u32 = add %13, 1u
+ store %idx, %14
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(&mod);
+
+ // Range of `shiftRight` (`idx >> idy`)
+ // idx: [4u, 8u], idy: [1u, 2u]
+ // shiftRight: [4u >> 2u, 8u >> 1u] = [1u, 4u]
+ auto* info = analysis.GetInfo(shiftRight);
+ ASSERT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(info->range));
+ const auto& range = std::get<IntegerRangeInfo::UnsignedIntegerRange>(info->range);
+ EXPECT_EQ(1u, range.min_bound);
+ EXPECT_EQ(4u, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, ShiftRight_Success_I32_NonZero) {
+ Var* idx = nullptr;
+ Binary* shiftRight = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ auto* loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 4
+ idx = b.Var("idx", 4_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // idx < 9
+ auto* binary = b.LessThan<bool>(b.Load(idx), 9_i);
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+
+ Var* idy = nullptr;
+ auto* loop2 = b.Loop();
+ b.Append(loop2->Initializer(), [&] {
+ // idy = 1
+ idy = b.Var("idy", 1_u);
+ b.NextIteration(loop2);
+ });
+ b.Append(loop2->Body(), [&] {
+ // idy < 3
+ auto* binary_inner = b.LessThan<bool>(b.Load(idy), 3_u);
+ auto* ifelse_inner = b.If(binary_inner);
+ b.Append(ifelse_inner->True(), [&] { b.ExitIf(ifelse_inner); });
+ b.Append(ifelse_inner->False(), [&] { b.ExitLoop(loop2); });
+ auto* loadx = b.Load(idx);
+ auto* loady = b.Load(idy);
+ // shiftRight = idx >> idy
+ shiftRight = b.ShiftRight<i32>(loadx, loady);
+ b.Continue(loop2);
+ });
+ b.Append(loop2->Continuing(), [&] {
+ // idy++
+ b.Store(idy, b.Add<u32>(b.Load(idy), 1_u));
+ b.NextIteration(loop2);
+ });
+
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx++
+ b.Store(idx, b.Add<i32>(b.Load(idx), 1_i));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func():void {
+ $B1: {
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, i32, read_write> = var 4i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = lt %3, 9i
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ loop [i: $B7, b: $B8, c: $B9] { # loop_2
+ $B7: { # initializer
+ %idy:ptr<function, u32, read_write> = var 1u
+ next_iteration # -> $B8
+ }
+ $B8: { # body
+ %6:u32 = load %idy
+ %7:bool = lt %6, 3u
+ if %7 [t: $B10, f: $B11] { # if_2
+ $B10: { # true
+ exit_if # if_2
+ }
+ $B11: { # false
+ exit_loop # loop_2
+ }
+ }
+ %8:i32 = load %idx
+ %9:u32 = load %idy
+ %10:i32 = shr %8, %9
+ continue # -> $B9
+ }
+ $B9: { # continuing
+ %11:u32 = load %idy
+ %12:u32 = add %11, 1u
+ store %idy, %12
+ next_iteration # -> $B8
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %13:i32 = load %idx
+ %14:i32 = add %13, 1i
+ store %idx, %14
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(&mod);
+
+ // Range of `shiftRight` (`idx >> idy`)
+ // idx: [4, 8], idy: [1u, 2u]
+ // shiftRight: [4 >> 2u, 8 >> 1u] = [1, 4]
+ auto* info = analysis.GetInfo(shiftRight);
+ ASSERT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(info->range));
+ const auto& range = std::get<IntegerRangeInfo::SignedIntegerRange>(info->range);
+ EXPECT_EQ(1, range.min_bound);
+ EXPECT_EQ(4, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, ShiftRight_Success_U32_Zero) {
+ Var* idx = nullptr;
+ Binary* shiftRight = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ auto* loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 4
+ idx = b.Var("idx", 4_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // idx < 9
+ auto* binary = b.LessThan<bool>(b.Load(idx), 9_u);
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+
+ Var* idy = nullptr;
+ auto* loop2 = b.Loop();
+ b.Append(loop2->Initializer(), [&] {
+ // idy = 1
+ idy = b.Var("idy", 1_u);
+ b.NextIteration(loop2);
+ });
+ b.Append(loop2->Body(), [&] {
+ // idy < 5
+ auto* binary_inner = b.LessThan<bool>(b.Load(idy), 5_u);
+ auto* ifelse_inner = b.If(binary_inner);
+ b.Append(ifelse_inner->True(), [&] { b.ExitIf(ifelse_inner); });
+ b.Append(ifelse_inner->False(), [&] { b.ExitLoop(loop2); });
+ auto* loadx = b.Load(idx);
+ auto* loady = b.Load(idy);
+ // shiftRight = idx >> idy
+ shiftRight = b.ShiftRight<u32>(loadx, loady);
+ b.Continue(loop2);
+ });
+ b.Append(loop2->Continuing(), [&] {
+ // idy++
+ b.Store(idy, b.Add<u32>(b.Load(idy), 1_u));
+ b.NextIteration(loop2);
+ });
+
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx++
+ b.Store(idx, b.Add<u32>(b.Load(idx), 1_u));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func():void {
+ $B1: {
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, u32, read_write> = var 4u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lt %3, 9u
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ loop [i: $B7, b: $B8, c: $B9] { # loop_2
+ $B7: { # initializer
+ %idy:ptr<function, u32, read_write> = var 1u
+ next_iteration # -> $B8
+ }
+ $B8: { # body
+ %6:u32 = load %idy
+ %7:bool = lt %6, 5u
+ if %7 [t: $B10, f: $B11] { # if_2
+ $B10: { # true
+ exit_if # if_2
+ }
+ $B11: { # false
+ exit_loop # loop_2
+ }
+ }
+ %8:u32 = load %idx
+ %9:u32 = load %idy
+ %10:u32 = shr %8, %9
+ continue # -> $B9
+ }
+ $B9: { # continuing
+ %11:u32 = load %idy
+ %12:u32 = add %11, 1u
+ store %idy, %12
+ next_iteration # -> $B8
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %13:u32 = load %idx
+ %14:u32 = add %13, 1u
+ store %idx, %14
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(&mod);
+
+ // Range of `shiftRight` (`idx >> idy`)
+ // idx: [4u, 8u], idy: [1u, 4u]
+ // shiftRight: [4u >> 4u, 8u >> 1u] = [0u, 4u]
+ auto* info = analysis.GetInfo(shiftRight);
+ ASSERT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(info->range));
+ const auto& range = std::get<IntegerRangeInfo::UnsignedIntegerRange>(info->range);
+ EXPECT_EQ(0u, range.min_bound);
+ EXPECT_EQ(4u, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, ShiftRight_Success_I32_Zero) {
+ Var* idx = nullptr;
+ Binary* shiftRight = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ auto* loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 4
+ idx = b.Var("idx", 4_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // idx < 9
+ auto* binary = b.LessThan<bool>(b.Load(idx), 9_i);
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+
+ Var* idy = nullptr;
+ auto* loop2 = b.Loop();
+ b.Append(loop2->Initializer(), [&] {
+ // idy = 4
+ idy = b.Var("idy", 4_u);
+ b.NextIteration(loop2);
+ });
+ b.Append(loop2->Body(), [&] {
+ // idy < 6
+ auto* binary_inner = b.LessThan<bool>(b.Load(idy), 6_u);
+ auto* ifelse_inner = b.If(binary_inner);
+ b.Append(ifelse_inner->True(), [&] { b.ExitIf(ifelse_inner); });
+ b.Append(ifelse_inner->False(), [&] { b.ExitLoop(loop2); });
+ auto* loadx = b.Load(idx);
+ auto* loady = b.Load(idy);
+ // shiftRight = idx >> idy
+ shiftRight = b.ShiftRight<i32>(loadx, loady);
+ b.Continue(loop2);
+ });
+ b.Append(loop2->Continuing(), [&] {
+ // idy++
+ b.Store(idy, b.Add<u32>(b.Load(idy), 1_u));
+ b.NextIteration(loop2);
+ });
+
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx++
+ b.Store(idx, b.Add<i32>(b.Load(idx), 1_i));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func():void {
+ $B1: {
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, i32, read_write> = var 4i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = lt %3, 9i
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ loop [i: $B7, b: $B8, c: $B9] { # loop_2
+ $B7: { # initializer
+ %idy:ptr<function, u32, read_write> = var 4u
+ next_iteration # -> $B8
+ }
+ $B8: { # body
+ %6:u32 = load %idy
+ %7:bool = lt %6, 6u
+ if %7 [t: $B10, f: $B11] { # if_2
+ $B10: { # true
+ exit_if # if_2
+ }
+ $B11: { # false
+ exit_loop # loop_2
+ }
+ }
+ %8:i32 = load %idx
+ %9:u32 = load %idy
+ %10:i32 = shr %8, %9
+ continue # -> $B9
+ }
+ $B9: { # continuing
+ %11:u32 = load %idy
+ %12:u32 = add %11, 1u
+ store %idy, %12
+ next_iteration # -> $B8
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %13:i32 = load %idx
+ %14:i32 = add %13, 1i
+ store %idx, %14
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(&mod);
+
+ // Range of `shiftRight` (`idx >> idy`)
+ // idx: [4, 8], idy: [4u, 5u]
+ // shiftRight: [4 >> 5u, 8 >> 4u] = [0, 0]
+ auto* info = analysis.GetInfo(shiftRight);
+ ASSERT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(info->range));
+ const auto& range = std::get<IntegerRangeInfo::SignedIntegerRange>(info->range);
+ EXPECT_EQ(0, range.min_bound);
+ EXPECT_EQ(0, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, ShiftRight_Failure_I32_Negative) {
+ Var* idx = nullptr;
+ Binary* shiftRight = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ auto* loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = -4
+ idx = b.Var("idx", -4_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // idx < 9
+ auto* binary = b.LessThan<bool>(b.Load(idx), 9_i);
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+
+ Var* idy = nullptr;
+ auto* loop2 = b.Loop();
+ b.Append(loop2->Initializer(), [&] {
+ // idy = 4
+ idy = b.Var("idy", 4_u);
+ b.NextIteration(loop2);
+ });
+ b.Append(loop2->Body(), [&] {
+ // idy < 6
+ auto* binary_inner = b.LessThan<bool>(b.Load(idy), 6_u);
+ auto* ifelse_inner = b.If(binary_inner);
+ b.Append(ifelse_inner->True(), [&] { b.ExitIf(ifelse_inner); });
+ b.Append(ifelse_inner->False(), [&] { b.ExitLoop(loop2); });
+ auto* loadx = b.Load(idx);
+ auto* loady = b.Load(idy);
+ // shiftRight = idx >> idy
+ shiftRight = b.ShiftRight<i32>(loadx, loady);
+ b.Continue(loop2);
+ });
+ b.Append(loop2->Continuing(), [&] {
+ // idy++
+ b.Store(idy, b.Add<u32>(b.Load(idy), 1_u));
+ b.NextIteration(loop2);
+ });
+
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx++
+ b.Store(idx, b.Add<i32>(b.Load(idx), 1_i));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func():void {
+ $B1: {
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, i32, read_write> = var -4i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = lt %3, 9i
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ loop [i: $B7, b: $B8, c: $B9] { # loop_2
+ $B7: { # initializer
+ %idy:ptr<function, u32, read_write> = var 4u
+ next_iteration # -> $B8
+ }
+ $B8: { # body
+ %6:u32 = load %idy
+ %7:bool = lt %6, 6u
+ if %7 [t: $B10, f: $B11] { # if_2
+ $B10: { # true
+ exit_if # if_2
+ }
+ $B11: { # false
+ exit_loop # loop_2
+ }
+ }
+ %8:i32 = load %idx
+ %9:u32 = load %idy
+ %10:i32 = shr %8, %9
+ continue # -> $B9
+ }
+ $B9: { # continuing
+ %11:u32 = load %idy
+ %12:u32 = add %11, 1u
+ store %idy, %12
+ next_iteration # -> $B8
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %13:i32 = load %idx
+ %14:i32 = add %13, 1i
+ store %idx, %14
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(&mod);
+
+ // Range of `shiftRight` (`idx >> idy`)
+ // idx: [-4, 8], idy: [4u, 5u]
+ auto* info = analysis.GetInfo(shiftRight);
+ ASSERT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, ShiftRight_Failure_U32_NoLessThan32) {
+ Var* idx = nullptr;
+ Binary* shiftRight = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ auto* loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 4
+ idx = b.Var("idx", 4_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // idx < 33
+ auto* binary = b.LessThan<bool>(b.Load(idx), 33_u);
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+
+ auto* loadx = b.Load(idx);
+
+ // shiftRight = u32::HighestValue >> idx
+ shiftRight = b.ShiftRight<u32>(u32::Highest(), loadx);
+
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx++
+ b.Store(idx, b.Add<u32>(b.Load(idx), 1_u));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func():void {
+ $B1: {
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, u32, read_write> = var 4u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lt %3, 33u
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ %5:u32 = load %idx
+ %6:u32 = shr 4294967295u, %5
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %7:u32 = load %idx
+ %8:u32 = add %7, 1u
+ store %idx, %8
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(&mod);
+
+ // Range of `shiftRight` (`u32::kHighestValue >> idx`)
+ // idx: [4u, 32u]
+ auto* info = analysis.GetInfo(shiftRight);
+ ASSERT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, ShiftRight_Failure_I32_NoLessThan32) {
+ Var* idx = nullptr;
+ Binary* shiftRight = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ auto* loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 4
+ idx = b.Var("idx", 4_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // idx < 33
+ auto* binary = b.LessThan<bool>(b.Load(idx), 33_u);
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+
+ auto* loadx = b.Load(idx);
+
+ // shiftRight = i32::Highest() >> idx
+ shiftRight = b.ShiftRight<i32>(i32::Highest(), loadx);
+
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx++
+ b.Store(idx, b.Add<u32>(b.Load(idx), 1_u));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func():void {
+ $B1: {
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, u32, read_write> = var 4u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lt %3, 33u
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ %5:u32 = load %idx
+ %6:i32 = shr 2147483647i, %5
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %7:u32 = load %idx
+ %8:u32 = add %7, 1u
+ store %idx, %8
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(&mod);
+
+ // Range of `shiftRight` (`i32::kHighestValue >> idx`)
+ // idx: [4, 32]
+ auto* info = analysis.GetInfo(shiftRight);
+ ASSERT_EQ(nullptr, info);
+}
+
} // namespace
} // namespace tint::core::ir::analysis
