Range Analysis: Compute the range of loop control variable - Part III
This patch implements the range analysis on the loop control variable
of a simple for-loop when the for-loop matches the below pattern:
```
// The range of i is [const_rhs, const_value]
for (var i = const_value; const_rhs <= i; i--)
// The range of i is [const_value, const_rhs]
for (var i = const_value; const_rhs >= i; i++)
// The range of i is [const_rhs + 1, const_value]
for (var i = const_value; const_rhs < i; i--)
// The range of i is [const_value, const_rhs - 1]
for (var i = const_value; const_rhs > i; i++)
```
Bug: 348701956
Test: tint_unittests
Change-Id: Id95c7d4ae62333731a6641e0261d60077d321592
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/238234
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 19841ac..a0d4a0c 100644
--- a/src/tint/lang/core/ir/analysis/integer_range_analysis.cc
+++ b/src/tint/lang/core/ir/analysis/integer_range_analysis.cc
@@ -86,40 +86,67 @@
// 2. variable > constant variable < constant
// 3. constant >= variable constant <= variable
// 4. constant > variable constant < variable
-// Currently this function only accepts format 1, 2.
-// TODO(348701956): turns the `compare` in format 3, 4 into format 1 and always fetch the
-// equivalent information in format 1. e.g.
-// - "constant >= variable" => result.op = "<=", result.constRHS = variable
-// - "constant > variable" => result.op = "<=", result.constRHS = constant - 1
+// This function analyzes the input `compare` and outputs both `variable` and `constant` in the
+// equivalent format of format 1.
CompareOpAndConstRHS GetCompareOpAndConstRHS(const Binary* compare) {
CompareOpAndConstRHS result;
- // TODO(348701956): Support more situations
- TINT_ASSERT(IsConstantInteger(compare->RHS()));
- int64_t const_rhs = GetValueFromConstant(compare->RHS()->As<Constant>());
+ if (IsConstantInteger(compare->RHS())) {
+ int64_t const_rhs = GetValueFromConstant(compare->RHS()->As<Constant>());
- switch (compare->Op()) {
- case BinaryOp::kLessThan:
- // variable < constant => variable <= constant - 1
- // `const_rhs - 1` will always be safe after the checks in
- // `GetBinaryToCompareLoopControlVariableInLoopBody()`.
- result.op = BinaryOp::kLessThanEqual;
- result.const_rhs = const_rhs - 1;
- break;
- case BinaryOp::kGreaterThan:
- // variable > constant => variable >= constant + 1
- // `const_rhs` will always be safe after the checks in
- // `GetBinaryToCompareLoopControlVariableInLoopBody()`.
- result.op = BinaryOp::kGreaterThanEqual;
- result.const_rhs = const_rhs + 1;
- break;
- case BinaryOp::kLessThanEqual:
- case BinaryOp::kGreaterThanEqual:
- result.op = compare->Op();
- result.const_rhs = const_rhs;
- break;
- default:
- TINT_UNREACHABLE();
+ switch (compare->Op()) {
+ case BinaryOp::kLessThan:
+ // variable < constant => variable <= constant - 1
+ // `const_rhs - 1` will always be safe after the checks in
+ // `GetBinaryToCompareLoopControlVariableInLoopBody()`.
+ result.op = BinaryOp::kLessThanEqual;
+ result.const_rhs = const_rhs - 1;
+ break;
+ case BinaryOp::kGreaterThan:
+ // variable > constant => variable >= constant + 1
+ // `const_rhs` will always be safe after the checks in
+ // `GetBinaryToCompareLoopControlVariableInLoopBody()`.
+ result.op = BinaryOp::kGreaterThanEqual;
+ result.const_rhs = const_rhs + 1;
+ break;
+ case BinaryOp::kLessThanEqual:
+ case BinaryOp::kGreaterThanEqual:
+ result.op = compare->Op();
+ result.const_rhs = const_rhs;
+ break;
+ default:
+ TINT_UNREACHABLE();
+ }
+ } else {
+ TINT_ASSERT(IsConstantInteger(compare->LHS()));
+ int64_t const_lhs = GetValueFromConstant(compare->LHS()->As<Constant>());
+
+ switch (compare->Op()) {
+ case BinaryOp::kLessThan:
+ // constant < variable => variable > constant => variable >= constant + 1
+ // `const_lhs + 1` will always be safe after the checks in
+ // `GetBinaryToCompareLoopControlVariableInLoopBody()`.
+ result.op = BinaryOp::kGreaterThanEqual;
+ result.const_rhs = const_lhs + 1;
+ break;
+ case BinaryOp::kGreaterThan:
+ // constant > variable => variable < constant => variable <= constant - 1
+ // `const_lhs - 1` will always be safe after the checks in
+ // `GetBinaryToCompareLoopControlVariableInLoopBody()`.
+ result.op = BinaryOp::kLessThanEqual;
+ result.const_rhs = const_lhs - 1;
+ break;
+ case BinaryOp::kLessThanEqual:
+ result.op = BinaryOp::kGreaterThanEqual;
+ result.const_rhs = const_lhs;
+ break;
+ case BinaryOp::kGreaterThanEqual:
+ result.op = BinaryOp::kLessThanEqual;
+ result.const_rhs = const_lhs;
+ break;
+ default:
+ TINT_UNREACHABLE();
+ }
}
return result;
@@ -218,13 +245,6 @@
// for (...; i++) or for(...; i--)
bool index_is_increasing = update->Op() == BinaryOp::kAdd;
- // Currently we only support `binary` in "index op constant" format.
- // TODO(348701956): Support other cases in `GetCompareOpAndConstRHS()`. For example,
- // - turn "constant op index" into "index reverse-op constant"
- if (!IsConstantInteger(compare->RHS())) {
- return;
- }
-
auto to_integer_range_info = [&](int64_t min_value, int64_t max_value) {
if (index->Initializer()->As<Constant>()->Type()->IsSignedIntegerScalar()) {
return IntegerRangeInfo(min_value, max_value);
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 6ecd887..8807932 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
@@ -1638,7 +1638,7 @@
EXPECT_EQ(9, range.max_bound);
}
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_Constant_LessThan_index) {
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_Constant_LessThan_index_i32) {
Var* idx = nullptr;
Loop* loop = nullptr;
Binary* binary = nullptr;
@@ -1646,6 +1646,7 @@
b.Append(func->Block(), [&] {
loop = b.Loop();
b.Append(loop->Initializer(), [&] {
+ // idx = 20
idx = b.Var("idx", 20_i);
b.NextIteration(loop);
});
@@ -1702,6 +1703,14 @@
IntegerRangeAnalysis analysis(func);
EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::SignedIntegerRange>(info->range);
+ EXPECT_EQ(11, range.min_bound);
+ EXPECT_EQ(20, range.max_bound);
}
TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_index_LessThan_Constant_u32) {
@@ -1788,6 +1797,7 @@
b.Append(func->Block(), [&] {
loop = b.Loop();
b.Append(loop->Initializer(), [&] {
+ // idx = 20u
idx = b.Var("idx", 20_u);
b.NextIteration(loop);
});
@@ -1844,6 +1854,14 @@
IntegerRangeAnalysis analysis(func);
EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::UnsignedIntegerRange>(info->range);
+ EXPECT_EQ(11u, range.min_bound);
+ EXPECT_EQ(20u, range.max_bound);
}
TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_index_LessThanEqual_constant_i32) {
@@ -1996,7 +2014,7 @@
EXPECT_EQ(10u, range.max_bound);
}
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_constant_LessThanEqual_index) {
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_constant_LessThanEqual_index_i32) {
Var* idx = nullptr;
Loop* loop = nullptr;
Binary* binary = nullptr;
@@ -2004,6 +2022,7 @@
b.Append(func->Block(), [&] {
loop = b.Loop();
b.Append(loop->Initializer(), [&] {
+ // idx = 20
idx = b.Var("idx", 20_i);
b.NextIteration(loop);
});
@@ -2060,6 +2079,89 @@
IntegerRangeAnalysis analysis(func);
EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::SignedIntegerRange>(info->range);
+ EXPECT_EQ(10, range.min_bound);
+ EXPECT_EQ(20, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_constant_LessThanEqual_index_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 10 <= idx
+ binary = b.LessThanEqual<bool>(10_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ b.Store(idx, b.Subtract<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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lte 10u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::UnsignedIntegerRange>(info->range);
+ EXPECT_EQ(10u, range.min_bound);
+ EXPECT_EQ(20u, range.max_bound);
}
TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_index_GreaterThan_constant_i32) {
@@ -2214,7 +2316,7 @@
EXPECT_EQ(20u, range.max_bound);
}
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_constant_GreaterThan_index) {
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_constant_GreaterThan_index_i32) {
Var* idx = nullptr;
Loop* loop = nullptr;
Binary* binary = nullptr;
@@ -2222,6 +2324,7 @@
b.Append(func->Block(), [&] {
loop = b.Loop();
b.Append(loop->Initializer(), [&] {
+ // idx = 0
idx = b.Var("idx", 0_i);
b.NextIteration(loop);
});
@@ -2234,6 +2337,7 @@
b.Continue(loop);
});
b.Append(loop->Continuing(), [&] {
+ // idx++
b.Store(idx, b.Add<i32>(b.Load(idx), 1_i));
b.NextIteration(loop);
});
@@ -2278,6 +2382,90 @@
IntegerRangeAnalysis analysis(func);
EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_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(9, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_constant_GreaterThan_index_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 0u
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 10u > idx
+ binary = b.GreaterThan<bool>(10_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 0u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = gt 10u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = add %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_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(9u, range.max_bound);
}
TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_index_GreaterThanEqual_Constant_i32) {
@@ -2432,7 +2620,7 @@
EXPECT_EQ(20u, range.max_bound);
}
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_Constant_GreaterThanEqual_index) {
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_Constant_GreaterThanEqual_index_i32) {
Var* idx = nullptr;
Loop* loop = nullptr;
Binary* binary = nullptr;
@@ -2440,6 +2628,7 @@
b.Append(func->Block(), [&] {
loop = b.Loop();
b.Append(loop->Initializer(), [&] {
+ // idx = 0
idx = b.Var("idx", 0_i);
b.NextIteration(loop);
});
@@ -2452,6 +2641,7 @@
b.Continue(loop);
});
b.Append(loop->Continuing(), [&] {
+ // idx++
b.Store(idx, b.Add<i32>(b.Load(idx), 1_i));
b.NextIteration(loop);
});
@@ -2496,6 +2686,90 @@
IntegerRangeAnalysis analysis(func);
EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_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(10, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_Constant_GreaterThanEqual_index_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 0u
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 10u >= idx
+ binary = b.GreaterThanEqual<bool>(10_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 0u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = gte 10u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = add %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_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(10u, range.max_bound);
}
TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_InstructionsOtherThanLoadOnIndex) {
@@ -6401,5 +6675,1751 @@
EXPECT_EQ(nullptr, info);
}
+// const_lhs <= index
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_LessThanEqual_init_equals_lhs_i32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 20 <= idx
+ binary = b.LessThanEqual<bool>(20_i, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ b.Store(idx, b.Subtract<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 20i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = lte 20i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = sub %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::SignedIntegerRange>(info->range);
+ EXPECT_EQ(20, range.min_bound);
+ EXPECT_EQ(20, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_LessThanEqual_init_equals_lhs_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 20 <= idx
+ binary = b.LessThanEqual<bool>(20_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ b.Store(idx, b.Subtract<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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lte 20u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::UnsignedIntegerRange>(info->range);
+ EXPECT_EQ(20u, range.min_bound);
+ EXPECT_EQ(20u, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_LessThanEqual_init_LessThan_lhs_i32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 30 <= idx
+ binary = b.LessThanEqual<bool>(30_i, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = lte 30i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = sub %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_LessThanEqual_init_LessThan_lhs_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20u
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 30u <= idx
+ binary = b.LessThanEqual<bool>(30_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lte 30u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest,
+ AnalyzeLoopBody_Failure_constant_LessThanEqual_index_increasing) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20u
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 10u <= idx
+ binary = b.LessThanEqual<bool>(10_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lte 10u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = add %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoop_Success_min_u32_add_1_LessThanEqual_index) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 1u (minimum uint32_t value + 1)
+ idx = b.Var("idx", u32(u32::kLowestValue + 1u));
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 1u >= idx
+ binary = b.LessThanEqual<bool>(u32(u32::kLowestValue + 1u), b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 1u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lte 1u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::UnsignedIntegerRange>(info->range);
+ EXPECT_EQ(u32::kLowestValue + 1u, range.min_bound);
+ EXPECT_EQ(u32::kLowestValue + 1u, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoop_Success_min_i32_add_1_LessThanEqual_index) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = -2147483647 (minimum int32_t value + 1)
+ idx = b.Var("idx", i32(i32::kLowestValue + 1));
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // -2147483647 >= idx
+ binary = b.LessThanEqual<bool>(i32(i32::kLowestValue + 1), b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 -2147483647i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = lte -2147483647i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = sub %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::SignedIntegerRange>(info->range);
+ EXPECT_EQ(i32::kLowestValue + 1, range.min_bound);
+ EXPECT_EQ(i32::kLowestValue + 1, range.max_bound);
+}
+
+// const_lhs >= index
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_GreaterThanEqual_init_equals_lhs_i32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 20 >= idx
+ binary = b.GreaterThanEqual<bool>(20_i, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 20i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = gte 20i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = add %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::SignedIntegerRange>(info->range);
+ EXPECT_EQ(20, range.min_bound);
+ EXPECT_EQ(20, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_GreaterThanEqual_init_equals_lhs_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 20 >= idx
+ binary = b.GreaterThanEqual<bool>(20_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = gte 20u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = add %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::UnsignedIntegerRange>(info->range);
+ EXPECT_EQ(20u, range.min_bound);
+ EXPECT_EQ(20u, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest,
+ AnalyzeLoopBody_Failure_GreaterThanEqual_init_GreaterThan_lhs_i32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 10 >= idx
+ binary = b.GreaterThanEqual<bool>(10_i, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = gte 10i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = sub %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest,
+ AnalyzeLoopBody_Failure_GreaterThanEqual_init_GreaterThan_lhs_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20u
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 10u >= idx
+ binary = b.GreaterThanEqual<bool>(10_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = gte 10u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest,
+ AnalyzeLoopBody_Failure_constant_GreaterThanEqual_index_decreasing) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20u
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 30u >= idx
+ binary = b.GreaterThanEqual<bool>(30_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = gte 30u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoop_Success_max_u32_minus_1_GreaterThanEqual_index) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 4294967294u (maximum uint32_t value - 1)
+ idx = b.Var("idx", u32(u32::kHighestValue - 1u));
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 4294967294u >= idx
+ binary = b.GreaterThanEqual<bool>(u32(u32::kHighestValue - 1u), b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 4294967294u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = gte 4294967294u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = add %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::UnsignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::UnsignedIntegerRange>(info->range);
+ EXPECT_EQ(u32::kHighestValue - 1u, range.min_bound);
+ EXPECT_EQ(u32::kHighestValue - 1u, range.max_bound);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoop_Success_max_i32_minus_1_GreaterThanEqual_index) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 2147483646 (maximum int32_t value - 1)
+ idx = b.Var("idx", i32(i32::kHighestValue - 1));
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 2147483646 >= idx
+ binary = b.GreaterThanEqual<bool>(i32(i32::kHighestValue - 1), b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 2147483646i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = gte 2147483646i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = add %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_NE(nullptr, info);
+ ASSERT_TRUE(std::holds_alternative<IntegerRangeInfo::SignedIntegerRange>(info->range));
+
+ const auto& range = std::get<IntegerRangeInfo::SignedIntegerRange>(info->range);
+ EXPECT_EQ(i32::kHighestValue - 1, range.min_bound);
+ EXPECT_EQ(i32::kHighestValue - 1, range.max_bound);
+}
+
+// const_lhs < index
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_LessThan_init_equals_lhs_i32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 20 < idx
+ binary = b.LessThan<bool>(20_i, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = lt 20i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = sub %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_LessThan_init_equals_lhs_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 20 < idx
+ binary = b.LessThan<bool>(20_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lt 20u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_LessThan_init_LessThan_lhs_i32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 30 < idx
+ binary = b.LessThan<bool>(30_i, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = lt 30i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = sub %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_LessThan_init_LessThan_lhs_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20u
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 30u < idx
+ binary = b.LessThan<bool>(30_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lt 30u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_constant_LessThan_index_increasing) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20u
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 10u < idx
+ binary = b.LessThan<bool>(10_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = lt 10u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = add %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+// lhs > index
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_GreaterThan_init_equals_lhs_i32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 20 > idx
+ binary = b.GreaterThan<bool>(20_i, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 20i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = gt 20i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = add %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_GreaterThan_init_equals_lhs_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 20 > idx
+ binary = b.GreaterThan<bool>(20_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ 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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = gt 20u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = add %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_GreaterThan_init_GreaterThan_lhs_i32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20
+ idx = b.Var("idx", 20_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 10 > idx
+ binary = b.GreaterThan<bool>(10_i, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:i32 = load %idx
+ %4:bool = gt 10i, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:i32 = load %idx
+ %6:i32 = sub %5, 1i
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_GreaterThan_init_GreaterThan_lhs_u32) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20u
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 10u > idx
+ binary = b.GreaterThan<bool>(10_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = gt 10u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_constant_GreaterThan_index_decreasing) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Binary* binary = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ // idx = 20u
+ idx = b.Var("idx", 20_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] {
+ // 30u > idx
+ binary = b.GreaterThan<bool>(30_u, b.Load(idx));
+ auto* ifelse = b.If(binary);
+ b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
+ b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
+ b.Continue(loop);
+ });
+ b.Append(loop->Continuing(), [&] {
+ // idx--
+ b.Store(idx, b.Subtract<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 20u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ %3:u32 = load %idx
+ %4:bool = gt 30u, %3
+ if %4 [t: $B5, f: $B6] { # if_1
+ $B5: { # true
+ exit_if # if_1
+ }
+ $B6: { # false
+ exit_loop # loop_1
+ }
+ }
+ continue # -> $B4
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = sub %5, 1u
+ store %idx, %6
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(binary, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
+
+ const IntegerRangeInfo* info = analysis.GetInfo(idx);
+ EXPECT_EQ(nullptr, info);
+}
+
} // namespace
} // namespace tint::core::ir::analysis
