Revert "Range Analysis: Get loop exit condition from body block"
This reverts commit 1411699ba4cdf29eca037c4320543ab8189bad28.
Reason for revert: Crashing on the cmake-linux-clang-dbg-x64-ubsan bot
[ RUN ] IR_IntegerRangeAnalysisTest.AnalyzeLoopBody_Failure_Index_LessThan_Min_I32
/b/s/w/ir/cache/uncached/dawn/src/tint/lang/core/number.h:176:46: runtime error: negation of -2147483648 cannot be represented in type 'type' (aka 'int'); cast to an unsigned type to negate this value to itself
Original change's description:
> Range Analysis: Get loop exit condition from body block
>
> This patch is the third part to implement the computation of the
> range on the loop control variables. In this patch we implement the
> function `GetBinaryToCompareLoopControlVariableInLoopBody()` to get
> the condition to exit the loop in the loop body block if the loop
> meets the below requirements (a straightforward for-loop):
> - The loop control variable is only used as the parameter of the
> load instruction.
> - The first instruction is to load the loop control variable into a
> temporary variable.
> - The second instruction is to compare the temporary variable with
> a constant value and save the result to a boolean variable.
> - The second instruction cannot be a comparison that will never be
> true (out of range of 32-bit integer).
> - The third instruction is an `ifelse` expression that uses the
> boolean variable got in the second instruction as the condition.
> - The true block of the above `ifelse` expression doesn't contain
> `exit_loop`.
> - The false block of the above `ifelse` expression only contains
> `exit_loop`.
>
> Bug: chromium:348701956
> Test: tint_unittests
> Change-Id: Ie99911791eb6530e6d081ac9b54c2ec74e1be64c
> Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/233294
> Commit-Queue: Jiawei Shao <jiawei.shao@intel.com>
> Reviewed-by: James Price <jrprice@google.com>
TBR=jiawei.shao@intel.com,dneto@google.com,jrprice@google.com,dawn-scoped@luci-project-accounts.iam.gserviceaccount.com
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: chromium:348701956
Change-Id: Idf151f39c2b25d66d0ce40dd31300735f3aabf76
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/234094
Reviewed-by: James Price <jrprice@google.com>
Commit-Queue: James Price <jrprice@google.com>
Reviewed-by: dan sinclair <dsinclair@chromium.org>
Auto-Submit: dan sinclair <dsinclair@chromium.org>
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 7ea8370..1e7384d 100644
--- a/src/tint/lang/core/ir/analysis/integer_range_analysis.cc
+++ b/src/tint/lang/core/ir/analysis/integer_range_analysis.cc
@@ -31,10 +31,7 @@
#include "src/tint/lang/core/constant/scalar.h"
#include "src/tint/lang/core/ir/binary.h"
-#include "src/tint/lang/core/ir/exit_if.h"
-#include "src/tint/lang/core/ir/exit_loop.h"
#include "src/tint/lang/core/ir/function.h"
-#include "src/tint/lang/core/ir/if.h"
#include "src/tint/lang/core/ir/load.h"
#include "src/tint/lang/core/ir/loop.h"
#include "src/tint/lang/core/ir/multi_in_block.h"
@@ -61,13 +58,6 @@
}
return false;
}
-
-bool IsConstantInteger(const Value* v) {
- if (auto* cv = v->As<Constant>()) {
- return cv->Type()->IsIntegerScalar();
- }
- return false;
-}
} // namespace
IntegerRangeInfo::IntegerRangeInfo(int64_t min_bound, int64_t max_bound) {
@@ -265,162 +255,6 @@
return add_or_sub_from_loop_control_variable;
}
- // Currently we only support the loop continuing of a simple for-loop which meets all the below
- // requirements:
- // - The loop control variable is only used as the parameter of the load instruction.
- // - The first instruction is to load the loop control variable into a temporary variable.
- // - The second instruction is to compare the temporary variable with a constant value and save
- // the result to a boolean variable.
- // - The second instruction cannot be a comparison that will never return true.
- // - The third instruction is an `ifelse` expression that uses the boolean variable got in the
- // second instruction as the condition.
- // - The true block of the above `ifelse` expression doesn't contain `exit_loop`.
- // - The false block of the above `ifelse` expression only contains `exit_loop`.
- const Binary* GetBinaryToCompareLoopControlVariableInLoopBody(
- const Loop* loop,
- const Var* loop_control_variable) {
- TINT_ASSERT(loop);
- TINT_ASSERT(loop_control_variable);
-
- auto* body_block = loop->Body();
-
- // Reject any non-load instructions unless it is a store in the continuing block
- const auto& uses = loop_control_variable->Result(0)->UsagesUnsorted();
- for (auto& use : uses) {
- if (use->instruction->Is<Load>()) {
- continue;
- }
- if (use->instruction->Is<Store>() && use->instruction->Block() == loop->Continuing()) {
- continue;
- }
- return nullptr;
- }
-
- // 1st instruction:
- // %src = load %loop_control_variable
- const auto* load_from_loop_control_variable = body_block->Instructions()->As<Load>();
- if (!load_from_loop_control_variable) {
- return nullptr;
- }
- if (load_from_loop_control_variable->From() != loop_control_variable->Result(0)) {
- return nullptr;
- }
-
- // 2nd instruction:
- // %condition:bool = lt(gt, lte, gte) %src, constant_value
- // or %condition:bool = lt(gt, lte, gte) constant_value, %src
- const auto* exit_condition_on_loop_control_variable =
- load_from_loop_control_variable->next->As<Binary>();
- if (!exit_condition_on_loop_control_variable) {
- return nullptr;
- }
- BinaryOp op = exit_condition_on_loop_control_variable->Op();
- auto* lhs = exit_condition_on_loop_control_variable->LHS();
- auto* rhs = exit_condition_on_loop_control_variable->RHS();
- switch (op) {
- case BinaryOp::kLessThan:
- case BinaryOp::kGreaterThan:
- case BinaryOp::kLessThanEqual:
- case BinaryOp::kGreaterThanEqual: {
- if (IsConstantInteger(rhs) && lhs == load_from_loop_control_variable->Result(0)) {
- break;
- }
- if (IsConstantInteger(lhs) && rhs == load_from_loop_control_variable->Result(0)) {
- break;
- }
- return nullptr;
- }
- default:
- return nullptr;
- }
-
- // Early-return when the comparison will never return true.
- if (op == BinaryOp::kLessThan) {
- if (IsConstantInteger(lhs)) {
- // std::numeric_limits<uint32_t>::max() < idx
- if (lhs->As<Constant>()->Value()->Type()->IsUnsignedIntegerScalar() &&
- lhs->As<Constant>()->Value()->ValueAs<uint32_t>() ==
- std::numeric_limits<uint32_t>::max()) {
- return nullptr;
- }
- // std::numeric_limits<int32_t>::max() < idx
- if (lhs->As<Constant>()->Value()->Type()->IsSignedIntegerScalar() &&
- lhs->As<Constant>()->Value()->ValueAs<int32_t>() ==
- std::numeric_limits<int32_t>::max()) {
- return nullptr;
- }
- } else {
- TINT_ASSERT(IsConstantInteger(rhs));
- // idx < 0u
- if (rhs->As<Constant>()->Value()->Type()->IsUnsignedIntegerScalar() &&
- rhs->As<Constant>()->Value()->ValueAs<uint32_t>() ==
- std::numeric_limits<uint32_t>::min()) {
- return nullptr;
- }
- // idx < std::numeric_limits<int32_t>::min()
- if (rhs->As<Constant>()->Value()->Type()->IsSignedIntegerScalar() &&
- rhs->As<Constant>()->Value()->ValueAs<int32_t>() ==
- std::numeric_limits<int32_t>::min()) {
- return nullptr;
- }
- }
- } else if (op == BinaryOp::kGreaterThan) {
- if (IsConstantInteger(lhs)) {
- // std::numeric_limits<uint32_t>::min() > idx
- if (lhs->As<Constant>()->Value()->Type()->IsUnsignedIntegerScalar() &&
- lhs->As<Constant>()->Value()->ValueAs<uint32_t>() ==
- std::numeric_limits<uint32_t>::min()) {
- return nullptr;
- }
- // std::numeric_limits<int32_t>::min() > idx
- if (lhs->As<Constant>()->Value()->Type()->IsSignedIntegerScalar() &&
- lhs->As<Constant>()->Value()->ValueAs<int32_t>() ==
- std::numeric_limits<int32_t>::min()) {
- return nullptr;
- }
- } else {
- TINT_ASSERT(IsConstantInteger(rhs));
- // idx > std::numeric_limits<uint32_t>::max()
- if (rhs->As<Constant>()->Value()->Type()->IsUnsignedIntegerScalar() &&
- rhs->As<Constant>()->Value()->ValueAs<uint32_t>() ==
- std::numeric_limits<uint32_t>::max()) {
- return nullptr;
- }
- // idx > std::numeric_limits<int32_t>::max()
- if (rhs->As<Constant>()->Value()->Type()->IsSignedIntegerScalar() &&
- rhs->As<Constant>()->Value()->ValueAs<int32_t>() ==
- std::numeric_limits<int32_t>::max()) {
- return nullptr;
- }
- }
- }
-
- // 3rd instruction:
- // if %condition [t: $true, f: $false] {
- // $true: {
- // // Maybe some other instructions
- // exit_if
- // }
- // $false: { exit_loop }
- // }
- const auto* if_on_exit_condition = exit_condition_on_loop_control_variable->next->As<If>();
- if (!if_on_exit_condition) {
- return nullptr;
- }
- if (if_on_exit_condition->Condition() !=
- exit_condition_on_loop_control_variable->Result(0)) {
- return nullptr;
- }
- if (!if_on_exit_condition->True()->Terminator()->As<ExitIf>()) {
- return nullptr;
- }
- if (!if_on_exit_condition->False()->Front()->As<ExitLoop>()) {
- return nullptr;
- }
-
- return exit_condition_on_loop_control_variable;
- }
-
private:
Function* function_;
Hashmap<const FunctionParam*, Vector<IntegerRangeInfo, 3>, 4>
@@ -447,10 +281,4 @@
loop_control_variable);
}
-const Binary* IntegerRangeAnalysis::GetBinaryToCompareLoopControlVariableInLoopBodyForTest(
- const Loop* loop,
- const Var* loop_control_variable) {
- return impl_->GetBinaryToCompareLoopControlVariableInLoopBody(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 d00e262..00576c5 100644
--- a/src/tint/lang/core/ir/analysis/integer_range_analysis.h
+++ b/src/tint/lang/core/ir/analysis/integer_range_analysis.h
@@ -102,8 +102,7 @@
/// - 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.
- /// @param loop_control_variable the loop control variable to investigate.
+ /// @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.
@@ -111,27 +110,6 @@
const Loop* loop,
const Var* loop_control_variable);
- /// Note: This function is only for tests
- /// Returns the pointer of the binary operation that compares the loop control variable with its
- /// limitations in the body block of the loop if the loop meets the below requirements:
- /// - The loop control variable is only used as the parameter of the load instruction.
- /// - The first instruction is to load the loop control variable into a temporary variable.
- /// - The second instruction is to compare the temporary variable with a constant value and save
- /// the result to a boolean variable.
- /// - The second instruction cannot be a comparison that will never return true.
- /// - The third instruction is an `ifelse` expression that uses the boolean variable got in the
- /// second instruction as the condition.
- // - The true block of the above `ifelse` expression doesn't contain `exit_loop`.
- // - The false block of the above `ifelse` expression only contains `exit_loop`.
- /// @param loop the Loop variable to investigate.
- /// @param loop_control_variable the loop control variable to investigate.
- /// @returns the pointer of the binary operation that compares the loop control variable with
- /// its limitations in the body block of the loop if the loop meets the below requirements,
- /// return nullptr otherwise.
- const Binary* GetBinaryToCompareLoopControlVariableInLoopBodyForTest(
- 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 97b7aa2..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
@@ -1562,2297 +1562,5 @@
analysis.GetBinaryToUpdateLoopControlVariableInContinuingBlockForTest(loop, idx));
}
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_index_LessThan_Constant) {
- 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(), [&] {
- // idx < 10
- binary = b.LessThan<bool>(b.Load(idx), 10_i);
- 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.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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = lt %3, 10i
- 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_Constant_LessThan_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 = b.Var("idx", 20_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // 10 < idx
- binary = b.LessThan<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(), [&] {
- 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 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_index_LessThan_Constant_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 = b.Var("idx", 0_u);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // idx < 10u
- binary = b.LessThan<bool>(b.Load(idx), 10_u);
- 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.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 = lt %3, 10u
- 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_Constant_LessThan_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 = 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(), [&] {
- 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 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_index_LessThanEqual_constant) {
- 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(), [&] {
- // idx <= 10
- binary = b.LessThanEqual<bool>(b.Load(idx), 10_i);
- 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.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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = lte %3, 10i
- 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_constant_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 = b.Var("idx", 20_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // 10 <= idx
- binary = b.LessThanEqual<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(), [&] {
- 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 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_index_GreaterThan_constant) {
- 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(), [&] {
- binary = b.GreaterThan<bool>(b.Load(idx), 10_i);
- 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 = gt %3, 10i
- 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_constant_GreaterThan_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 = b.Var("idx", 0_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(), [&] {
- 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 0i
- 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 = 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_index_GreaterThanEqual_Constant) {
- 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", 20_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // idx >= 10
- binary = b.GreaterThanEqual<bool>(b.Load(idx), 10_i);
- 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 = gte %3, 10i
- 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_Constant_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 = b.Var("idx", 0_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(), [&] {
- 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 0i
- 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 = 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_InstructionsOtherThanLoadOnIndex) {
- Var* idx = nullptr;
- Loop* loop = nullptr;
- Binary* binary = nullptr;
- auto* end = b.FunctionParam("end", ty.i32());
- 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", 20_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- 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.Store(idx, end);
- 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(%end:i32):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
- %4:i32 = load %idx
- %5:bool = gte 10i, %4
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- store %idx, %end
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = sub %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_FirstInstructionIsNotLoad) {
- 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(), [&] {
- // Initialize idy to 1
- Var* idy = b.Var("idy", 1_i);
- binary = b.LessThan<bool>(b.Load(idy), 10_i);
- 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.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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %idy:ptr<function, i32, read_write> = var 1i
- %4:i32 = load %idy
- %5:bool = lt %4, 10i
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = add %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_NoLoadFromLoopControlVariable) {
- Var* idx = nullptr;
- Loop* loop = nullptr;
- Binary* binary = nullptr;
- auto* func = b.Function("func", ty.void_());
- b.Append(func->Block(), [&] {
- Var* idy = b.Var("idy", 1_i);
- loop = b.Loop();
- b.Append(loop->Initializer(), [&] {
- idx = b.Var("idx", 0_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // idy < 10
- binary = b.LessThan<bool>(b.Load(idy), 10_i);
- 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.Add<i32>(b.Load(idx), 1_i));
- b.NextIteration(loop);
- });
- b.Return(func);
- });
-
- auto* src = R"(
-%func = func():void {
- $B1: {
- %idy:ptr<function, i32, read_write> = var 1i
- loop [i: $B2, b: $B3, c: $B4] { # loop_1
- $B2: { # initializer
- %idx:ptr<function, i32, read_write> = var 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %4:i32 = load %idy
- %5:bool = lt %4, 10i
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = add %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_StoreLoopControlVariableInInnerBlock) {
- Var* idx = nullptr;
- Loop* loop = nullptr;
- Binary* binary = nullptr;
- auto* func = b.Function("func", ty.void_());
- b.Append(func->Block(), [&] {
- Var* idy = b.Var("idy", 1_i);
- loop = b.Loop();
- b.Append(loop->Initializer(), [&] {
- idx = b.Var("idx", 0_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- binary = b.LessThan<bool>(b.Load(idx), 10_i);
- auto* ifelse = b.If(binary);
- b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
- b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
- auto* ifelse_y = b.If(b.LessThan<bool>(b.Load(idy), 10_i));
- b.Append(ifelse_y->True(), [&] {
- b.Store(idx, 2_i);
- b.ExitIf(ifelse_y);
- });
- b.Continue(loop);
- });
- b.Append(loop->Continuing(), [&] {
- b.Store(idx, b.Add<i32>(b.Load(idx), 1_i));
- b.NextIteration(loop);
- });
- b.Return(func);
- });
-
- auto* src = R"(
-%func = func():void {
- $B1: {
- %idy:ptr<function, i32, read_write> = var 1i
- loop [i: $B2, b: $B3, c: $B4] { # loop_1
- $B2: { # initializer
- %idx:ptr<function, i32, read_write> = var 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %4:i32 = load %idx
- %5:bool = lt %4, 10i
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- %6:i32 = load %idy
- %7:bool = lt %6, 10i
- if %7 [t: $B7] { # if_2
- $B7: { # true
- store %idx, 2i
- exit_if # if_2
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %8:i32 = load %idx
- %9:i32 = add %8, 1i
- store %idx, %9
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_SecondInstructionNotABinaryOp) {
- 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(), [&] {
- // bitcastX = bitcast<i32>(idx)
- auto* bitcastX = b.Bitcast<i32>(b.Load(idx));
- binary = b.LessThan<bool>(bitcastX, 10_i);
- 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.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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:i32 = bitcast %3
- %5:bool = lt %4, 10i
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = add %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_BinaryOpIsNotComparisonOp) {
- 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(), [&] {
- // shl = idx << 1
- auto* shl = b.ShiftLeft<i32>(b.Load(idx), 1_u);
- binary = b.LessThan<bool>(10_i, shl);
- 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.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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:i32 = shl %3, 1u
- %5:bool = lt 10i, %4
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = add %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_IndexCompareWithNonConst) {
- Var* idx = nullptr;
- Loop* loop = nullptr;
- Binary* binary = nullptr;
- auto* end = b.FunctionParam("end", ty.i32());
- 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_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // idx < end
- binary = b.LessThan<bool>(b.Load(idx), end);
- 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.Add<i32>(b.Load(idx), 1_i));
- b.NextIteration(loop);
- });
- b.Return(func);
- });
-
- auto* src = R"(
-%func = func(%end:i32):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
- %4:i32 = load %idx
- %5:bool = lt %4, %end
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = add %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_NonConstCompareWithIndex) {
- Var* idx = nullptr;
- Loop* loop = nullptr;
- Binary* binary = nullptr;
- auto* end = b.FunctionParam("end", ty.i32());
- 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", 20_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // end > idx
- binary = b.GreaterThan<bool>(end, 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(%end:i32):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
- %4:i32 = load %idx
- %5:bool = gt %end, %4
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = sub %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_NonIndexCompareWithConst) {
- Var* idx = nullptr;
- Loop* loop = nullptr;
- Binary* binary = nullptr;
- auto* end = b.FunctionParam("end", ty.i32());
- 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_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- b.Load(idx);
- // end < 10
- binary = b.LessThan<bool>(end, 10_i);
- 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.Add<i32>(b.Load(idx), 1_i));
- b.NextIteration(loop);
- });
- b.Return(func);
- });
-
- auto* src = R"(
-%func = func(%end:i32):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
- %4:i32 = load %idx
- %5:bool = lt %end, 10i
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = add %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_ConstCompareWithNonIndex) {
- Var* idx = nullptr;
- Loop* loop = nullptr;
- Binary* binary = nullptr;
- auto* end = b.FunctionParam("end", ty.i32());
- 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", 20_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- b.Load(idx);
- // 10 > end
- binary = b.GreaterThan<bool>(10_i, end);
- 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(%end:i32):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
- %4:i32 = load %idx
- %5:bool = gt 10i, %end
- if %5 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = sub %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_Index_LessThan_Zero_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 = b.Var("idx", 0_u);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // idx < 0u
- binary = b.LessThan<bool>(b.Load(idx), 0_u);
- 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.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 = lt %3, 0u
- 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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_Zero_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 = b.Var("idx", 0_u);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // 0u > idx
- binary = b.GreaterThan<bool>(0_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.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 0u, %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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_Index_GreaterThan_Max_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 = b.Var("idx", 0_u);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // idx > 4294967295u (maximum uint32_t value)
- binary = b.GreaterThan<bool>(b.Load(idx), 4294967295_u);
- 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.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 %3, 4294967295u
- 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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_Max_u32_LessThan_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 = b.Var("idx", 0_u);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // 4294967295u (maximum uint32_t value) < idx
- binary = b.LessThan<bool>(4294967295_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.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 = lt 4294967295u, %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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_Index_LessThan_Min_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 = b.Var("idx", 0_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // idx < -2147483648 (minimum int32_t value)
- binary = b.LessThan<bool>(b.Load(idx), -2147483648_i);
- 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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = lt %3, -2147483648i
- 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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_Min_I32_GreaterThan_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 = b.Var("idx", 0_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // -2147483648 (minimum int32_t value) > idx
- binary = b.GreaterThan<bool>(-2147483648_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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = gt -2147483648i, %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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_Index_GreaterThan_Max_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 = b.Var("idx", 0_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // idx > 2147483647 (maximum int32_t value)
- binary = b.GreaterThan<bool>(b.Load(idx), 2147483647_i);
- 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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = gt %3, 2147483647i
- 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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_Max_I32_LessThan_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 = b.Var("idx", 0_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- // 2147483647i (maximum int32_t value) < idx
- binary = b.LessThan<bool>(2147483647_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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = lt 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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_NotIfElseAfterCompareInstruction) {
- 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(), [&] {
- binary = b.LessThan<bool>(b.Load(idx), 10_i);
- // Now idx can be 10 before the if-statement
- b.Add<i32>(b.Load(idx), 1_i);
- 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.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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = lt %3, 10i
- %5:i32 = load %idx
- %6:i32 = add %5, 1i
- if %4 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %7:i32 = load %idx
- %8:i32 = add %7, 1i
- store %idx, %8
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_NotUseLastComparisonAsIfCondition) {
- Var* idx = nullptr;
- Loop* loop = nullptr;
- Binary* binary = nullptr;
- auto* param = b.FunctionParam("param", ty.i32());
- auto* func = b.Function("func", ty.void_());
- func->AppendParam(param);
- b.Append(func->Block(), [&] {
- Binary* binaryOnParam = b.LessThan<bool>(param, 30_i);
- loop = b.Loop();
- b.Append(loop->Initializer(), [&] {
- idx = b.Var("idx", 0_i);
- b.NextIteration(loop);
- });
- b.Append(loop->Body(), [&] {
- binary = b.LessThan<bool>(b.Load(idx), 10_i);
- auto* ifelse = b.If(binaryOnParam);
- 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.Add<i32>(b.Load(idx), 1_i));
- b.NextIteration(loop);
- });
- b.Return(func);
- });
-
- auto* src = R"(
-%func = func(%param:i32):void {
- $B1: {
- %3:bool = lt %param, 30i
- loop [i: $B2, b: $B3, c: $B4] { # loop_1
- $B2: { # initializer
- %idx:ptr<function, i32, read_write> = var 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %5:i32 = load %idx
- %6:bool = lt %5, 10i
- if %3 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %7:i32 = load %idx
- %8:i32 = add %7, 1i
- store %idx, %8
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Success_MultipleInstructionsInTrueBlock) {
- 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(), [&] {
- binary = b.LessThan<bool>(b.Load(idx), 10_i);
- auto* ifelse = b.If(binary);
- b.Append(ifelse->True(), [&] {
- // Now idx < 10
- b.Add<i32>(b.Load(idx), 30_i);
- b.ExitIf(ifelse);
- });
- b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
- b.Continue(loop);
- });
- b.Append(loop->Continuing(), [&] {
- 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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = lt %3, 10i
- if %4 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- %5:i32 = load %idx
- %6:i32 = add %5, 30i
- exit_if # if_1
- }
- $B6: { # false
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %7:i32 = load %idx
- %8:i32 = add %7, 1i
- store %idx, %8
- 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));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_ExitLoopInTrueBlock) {
- 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(), [&] {
- binary = b.LessThan<bool>(b.Load(idx), 10_i);
- auto* ifelse = b.If(binary);
- b.Append(ifelse->True(), [&] { b.ExitLoop(loop); });
- b.Append(ifelse->False(), [&] { b.ExitLoop(loop); });
- b.Continue(loop);
- });
- b.Append(loop->Continuing(), [&] {
- 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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = lt %3, 10i
- if %4 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_loop # loop_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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_TooManyInstructionsInFalseBlock) {
- 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(), [&] {
- binary = b.LessThan<bool>(b.Load(idx), 10_i);
- auto* ifelse = b.If(binary);
- b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
- b.Append(ifelse->False(), [&] {
- // Now idx can be 10
- b.Load(idx);
- b.ExitLoop(loop);
- });
- b.Continue(loop);
- });
- b.Append(loop->Continuing(), [&] {
- 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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = lt %3, 10i
- if %4 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- %5:i32 = load %idx
- exit_loop # loop_1
- }
- }
- continue # -> $B4
- }
- $B4: { # continuing
- %6:i32 = load %idx
- %7:i32 = add %6, 1i
- store %idx, %7
- 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.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
-TEST_F(IR_IntegerRangeAnalysisTest, AnalyzeLoopBody_Failure_NoExitLoopInFalseBlock) {
- 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(), [&] {
- binary = b.LessThan<bool>(b.Load(idx), 10_i);
- auto* ifelse = b.If(binary);
- b.Append(ifelse->True(), [&] { b.ExitIf(ifelse); });
- b.Append(ifelse->False(), [&] { b.ExitIf(ifelse); });
- b.Continue(loop);
- });
- b.Append(loop->Continuing(), [&] {
- 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 0i
- next_iteration # -> $B3
- }
- $B3: { # body
- %3:i32 = load %idx
- %4:bool = lt %3, 10i
- if %4 [t: $B5, f: $B6] { # if_1
- $B5: { # true
- exit_if # if_1
- }
- $B6: { # false
- exit_if # if_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(nullptr, analysis.GetBinaryToCompareLoopControlVariableInLoopBodyForTest(loop, idx));
-}
-
} // namespace
} // namespace tint::core::ir::analysis
diff --git a/src/tint/lang/core/ir/value.h b/src/tint/lang/core/ir/value.h
index 54879fa..c2475b6 100644
--- a/src/tint/lang/core/ir/value.h
+++ b/src/tint/lang/core/ir/value.h
@@ -104,7 +104,7 @@
/// @returns the set of usages of this value. An instruction may appear multiple times if it
/// uses the value for multiple different operands.
- const Hashset<Usage, 4>& UsagesUnsorted() const { return uses_; }
+ const Hashset<Usage, 4>& UsagesUnsorted() { return uses_; }
/// @returns a sorted list of usages of this value. The usages are in the order of
/// <instruction, operand index> where the instructions are ordered earliest instruction to
