Range Analysis: Check loop continuing block
This patch is the second part to implement the computation of the
range on the loop control variables. In this patch we implement the
function `GetBinaryToUpdateLoopControlVariableInContinuingBlock()`
to get the binary to update the loop control variable in the loop
continuing block if the loop continuing block meets the requirements
of current range analysis algorithm (a straightforward for-loop):
- Only one load and one store instruction on the loop control
variable got in the loop initializer.
- Only accept plus one or minus one to the loop control variable.
Bug: chromium:348701956
Test: tint_unittests
Change-Id: I20ec096ab14d6d7bc098e92bcd731d0195d963e6
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/222074
Reviewed-by: James Price <jrprice@google.com>
Commit-Queue: Jiawei Shao <jiawei.shao@intel.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 56213f1..1e7384d 100644
--- a/src/tint/lang/core/ir/analysis/integer_range_analysis.cc
+++ b/src/tint/lang/core/ir/analysis/integer_range_analysis.cc
@@ -30,15 +30,36 @@
#include <limits>
#include "src/tint/lang/core/constant/scalar.h"
+#include "src/tint/lang/core/ir/binary.h"
#include "src/tint/lang/core/ir/function.h"
+#include "src/tint/lang/core/ir/load.h"
#include "src/tint/lang/core/ir/loop.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;
+}
+} // namespace
+
IntegerRangeInfo::IntegerRangeInfo(int64_t min_bound, int64_t max_bound) {
TINT_ASSERT(min_bound <= max_bound);
range = SignedIntegerRange{min_bound, max_bound};
@@ -100,6 +121,8 @@
}
const Var* GetLoopControlVariableFromConstantInitializer(const Loop* loop) {
+ TINT_ASSERT(loop);
+
auto* init_block = loop->Initializer();
if (!init_block) {
return nullptr;
@@ -141,6 +164,97 @@
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(0)) {
+ 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(0);
+ 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(0);
+ if (store_into_loop_control_variable->From() != dst) {
+ return nullptr;
+ }
+ if (store_into_loop_control_variable->To() != loop_control_variable->Result(0)) {
+ 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;
+ }
+
private:
Function* function_;
Hashmap<const FunctionParam*, Vector<IntegerRangeInfo, 3>, 4>
@@ -160,4 +274,11 @@
return impl_->GetLoopControlVariableFromConstantInitializer(loop);
}
+const Binary* IntegerRangeAnalysis::GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(
+ const Loop* loop,
+ const Var* loop_control_variable) {
+ return impl_->GetBinaryToUpdateLoopControlVariableInContinuingBlock(loop,
+ loop_control_variable);
+}
+
} // namespace tint::core::ir::analysis
diff --git a/src/tint/lang/core/ir/analysis/integer_range_analysis.h b/src/tint/lang/core/ir/analysis/integer_range_analysis.h
index 010c5c8..00576c5 100644
--- a/src/tint/lang/core/ir/analysis/integer_range_analysis.h
+++ b/src/tint/lang/core/ir/analysis/integer_range_analysis.h
@@ -32,6 +32,7 @@
#include <variant>
namespace tint::core::ir {
+class Binary;
class Function;
class FunctionParam;
class Loop;
@@ -92,6 +93,23 @@
/// requirements, return nullptr otherwise.
const Var* GetLoopControlVariableFromConstantInitializerForTest(const Loop* loop);
+ /// Note: This function is only for tests.
+ /// Returns the pointer of the binary operation that updates the loop control variable in the
+ /// continuing block of the given loop if the loop meets the below requirements.
+ /// - There are only 4 instructions in the loop initializer block.
+ /// - 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`.
+ /// @param loop the Loop variable to investigate
+ /// @returns the pointer of the binary operation that updates the loop control variable in the
+ /// continuing block of the given loop if the loop meets all the requirements, return nullptr
+ /// otherwise.
+ const Binary* GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(
+ const Loop* loop,
+ const Var* loop_control_variable);
+
private:
IntegerRangeAnalysis(const IntegerRangeAnalysis&) = delete;
IntegerRangeAnalysis(IntegerRangeAnalysis&&) = delete;
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 96e9690..9601f60 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
@@ -585,5 +585,982 @@
EXPECT_EQ(nullptr, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
}
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Success_AddOne_sint) {
+ 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 = b.Var("idx", 0_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ binary = b.Add<i32>(b.Load(idx), 1_i);
+ b.Store(idx, binary);
+ 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 0i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:i32 = load %idx
+ %4:i32 = add %3, 1i
+ store %idx, %4
+ 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.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Success_AddOne_uint) {
+ 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 = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ binary = b.Add<u32>(b.Load(idx), 1_u);
+ b.Store(idx, binary);
+ 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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ %4:u32 = add %3, 1u
+ store %idx, %4
+ 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.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Success_OneAddLoopControlVariable_sint) {
+ 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 = b.Var("idx", 0_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ binary = b.Add<i32>(1_i, b.Load(idx));
+ b.Store(idx, binary);
+ 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 0i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:i32 = load %idx
+ %4:i32 = add 1i, %3
+ store %idx, %4
+ 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.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Success_OneAddLoopControlVariable_uint) {
+ 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 = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ binary = b.Add<u32>(1_u, b.Load(idx));
+ b.Store(idx, binary);
+ 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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ %4:u32 = add 1u, %3
+ store %idx, %4
+ 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.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Success_MinusOne_sint) {
+ 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 = b.Var("idx", 0_i);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ binary = b.Subtract<i32>(b.Load(idx), 1_i);
+ b.Store(idx, binary);
+ 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 0i
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:i32 = load %idx
+ %4:i32 = sub %3, 1i
+ store %idx, %4
+ 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.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Success_MinusOne_uint) {
+ 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 = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ binary = b.Subtract<u32>(b.Load(idx), 1_u);
+ b.Store(idx, binary);
+ 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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ %4:u32 = sub %3, 1u
+ store %idx, %4
+ 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.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_TooFewInstructions) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ b.Store(idx, b.Load(idx));
+ 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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ store %idx, %3
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_TooManyInstructions) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ auto* addx = b.Add<u32>(b.Load(idx), 1_u);
+ auto* minusx = b.Subtract<u32>(addx, 1_u);
+ b.Store(idx, minusx);
+ 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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ %4:u32 = add %3, 1u
+ %5:u32 = sub %4, 1u
+ store %idx, %5
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_FirstInstructionIsNotLoad) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ Var* idy = b.Var("idy", 1_u);
+ b.Store(idx, b.Load(idy));
+ 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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %idy:ptr<function, u32, read_write> = var 1u
+ %4:u32 = load %idy
+ store %idx, %4
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_NoLoadFromLoopControlVariable) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Var* idy = nullptr;
+ auto* end = b.FunctionParam("end", ty.u32());
+ auto* func = b.Function("func", ty.void_());
+ func->AppendParam(end);
+ b.Append(func->Block(), [&] {
+ idy = b.Var("idy", end);
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ // idx = idy + 1
+ b.Store(idx, b.Add<u32>(b.Load(idy), 1_u));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func(%end:u32):void {
+ $B1: {
+ %idy:ptr<function, u32, read_write> = var %end
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, u32, read_write> = var 0u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %5:u32 = load %idy
+ %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(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_SecondInstructionNotABinaryOp) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ // idx = bitcast<u32>(idx);
+ b.Store(idx, b.Bitcast<u32>(b.Load(idx)));
+ 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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ %4:u32 = bitcast %3
+ store %idx, %4
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_AddTwo) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ // idx += 2u;
+ b.Store(idx, b.Add<u32>(b.Load(idx), 2_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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ %4:u32 = add %3, 2u
+ store %idx, %4
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_MinusTwo) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ // idx -= 2u
+ b.Store(idx, b.Subtract<u32>(b.Load(idx), 2_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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ %4:u32 = sub %3, 2u
+ store %idx, %4
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_OneMinusLoopControlVariable) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ // idx = 1u - idx
+ b.Store(idx, b.Subtract<u32>(1_u, b.Load(idx)));
+ 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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ %4:u32 = sub 1u, %3
+ store %idx, %4
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_AddNonConstantValue) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* end = b.FunctionParam("end", ty.u32());
+ auto* func = b.Function("func", ty.void_());
+ func->AppendParam(end);
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ // idx += end
+ b.Store(idx, b.Add<u32>(b.Load(idx), end));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func(%end:u32):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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %4:u32 = load %idx
+ %5:u32 = add %4, %end
+ store %idx, %5
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_MinusNonConstantValue) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* end = b.FunctionParam("end", ty.u32());
+ auto* func = b.Function("func", ty.void_());
+ func->AppendParam(end);
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ // idx -= end
+ b.Store(idx, b.Subtract<u32>(b.Load(idx), end));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func(%end:u32):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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %4:u32 = load %idx
+ %5:u32 = sub %4, %end
+ store %idx, %5
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_NeitherAddNorMinus) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ auto* func = b.Function("func", ty.void_());
+ b.Append(func->Block(), [&] {
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ // idx << 1ui;
+ b.Store(idx, b.ShiftLeft<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
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %3:u32 = load %idx
+ %4:u32 = shl %3, 1u
+ store %idx, %4
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_NoStoreFromLoopControlVariable) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Var* idy = nullptr;
+ auto* end = b.FunctionParam("end", ty.u32());
+ auto* func = b.Function("func", ty.void_());
+ func->AppendParam(end);
+ b.Append(func->Block(), [&] {
+ idy = b.Var("idy", end);
+ auto* loady = b.Load(idy);
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ b.Add<u32>(b.Load(idx), 1_u);
+ // idx = idy
+ b.Store(idx, loady);
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func(%end:u32):void {
+ $B1: {
+ %idy:ptr<function, u32, read_write> = var %end
+ %4:u32 = load %idy
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, u32, read_write> = var 0u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %6:u32 = load %idx
+ %7:u32 = add %6, 1u
+ store %idx, %4
+ next_iteration # -> $B3
+ }
+ }
+ ret
+ }
+}
+)";
+ EXPECT_EQ(src, str());
+ EXPECT_EQ(Validate(mod), Success);
+
+ IntegerRangeAnalysis analysis(func);
+ EXPECT_EQ(idx, analysis.GetLoopControlVariableFromConstantInitializerForTest(loop));
+ EXPECT_EQ(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
+TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopContinuing_Failure_NoStoreToLoopControlVariable) {
+ Var* idx = nullptr;
+ Loop* loop = nullptr;
+ Var* idy = nullptr;
+ auto* end = b.FunctionParam("end", ty.u32());
+ auto* func = b.Function("func", ty.void_());
+ func->AppendParam(end);
+ b.Append(func->Block(), [&] {
+ idy = b.Var("idy", end);
+ loop = b.Loop();
+ b.Append(loop->Initializer(), [&] {
+ idx = b.Var("idx", 0_u);
+ b.NextIteration(loop);
+ });
+ b.Append(loop->Body(), [&] { b.ExitLoop(loop); });
+ b.Append(loop->Continuing(), [&] {
+ // idy = idx + 1
+ b.Store(idy, b.Add<u32>(b.Load(idx), 1_u));
+ b.NextIteration(loop);
+ });
+ b.Return(func);
+ });
+
+ auto* src = R"(
+%func = func(%end:u32):void {
+ $B1: {
+ %idy:ptr<function, u32, read_write> = var %end
+ loop [i: $B2, b: $B3, c: $B4] { # loop_1
+ $B2: { # initializer
+ %idx:ptr<function, u32, read_write> = var 0u
+ next_iteration # -> $B3
+ }
+ $B3: { # body
+ exit_loop # loop_1
+ }
+ $B4: { # continuing
+ %5:u32 = load %idx
+ %6:u32 = add %5, 1u
+ store %idy, %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(nullptr,
+ analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
+}
+
} // namespace
} // namespace tint::core::ir::analysis
