[wasm] Add loop assignment analysis.

test/unittests/wasm/loop-assignment-analysis-unittest.cc

+// Copyright 2016 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "test/unittests/test-utils.h"
+
+#include "src/v8.h"
+
+#include "test/cctest/wasm/test-signatures.h"
+
+#include "src/bit-vector.h"
+#include "src/objects.h"
+
+#include "src/wasm/ast-decoder.h"
+#include "src/wasm/wasm-macro-gen.h"
+#include "src/wasm/wasm-module.h"
+
+#define WASM_SET_ZERO(i) WASM_SET_LOCAL(i, WASM_ZERO)
+
+namespace v8 {
+namespace internal {
+namespace wasm {
+
+class WasmLoopAssignmentAnalyzerTest : public TestWithZone {
+ public:
+  WasmLoopAssignmentAnalyzerTest() : TestWithZone(), sigs() {
+    init_env(&env, sigs.v_v());
+  }
+
+  TestSignatures sigs;
+  FunctionEnv env;
+
+  static void init_env(FunctionEnv* env, FunctionSig* sig) {
+    env->module = nullptr;
+    env->sig = sig;
+    env->local_int32_count = 0;
+    env->local_int64_count = 0;
+    env->local_float32_count = 0;
+    env->local_float64_count = 0;
+    env->SumLocals();
+  }
+
+  BitVector* Analyze(const byte* start, const byte* end) {
+    return AnalyzeLoopAssignmentForTesting(zone(), &env, start, end);
+  }
+};
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, Empty0) {
+  byte code[] = { 0 };
+  BitVector* assigned = Analyze(code, code);
+  CHECK_NULL(assigned);
+}
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, Empty1) {
+  byte code[] = {kExprLoop, 0};
+  for (int i = 0; i < 5; i++) {
+    BitVector* assigned = Analyze(code, code + arraysize(code));
+    for (int j = 0; j < assigned->length(); j++) {
+      CHECK_EQ(false, assigned->Contains(j));
+    }
+    env.AddLocals(kAstI32, 1);
+  }
+}
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, One) {
+  env.AddLocals(kAstI32, 5);
+  for (int i = 0; i < 5; i++) {
+    byte code[] = {WASM_LOOP(1, WASM_SET_ZERO(i))};
+    BitVector* assigned = Analyze(code, code + arraysize(code));
+    for (int j = 0; j < assigned->length(); j++) {
+      CHECK_EQ(j == i, assigned->Contains(j));
+    }
+  }
+}
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, OneBeyond) {
+  env.AddLocals(kAstI32, 5);
+  for (int i = 0; i < 5; i++) {
+    byte code[] = {WASM_LOOP(1, WASM_SET_ZERO(i)), WASM_SET_ZERO(1)};
+    BitVector* assigned = Analyze(code, code + arraysize(code));
+    for (int j = 0; j < assigned->length(); j++) {
+      CHECK_EQ(j == i, assigned->Contains(j));
+    }
+  }
+}
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, Two) {
+  env.AddLocals(kAstI32, 5);
+  for (int i = 0; i < 5; i++) {
+    for (int j = 0; j < 5; j++) {
+      byte code[] = {WASM_LOOP(2, WASM_SET_ZERO(i), WASM_SET_ZERO(j))};
+      BitVector* assigned = Analyze(code, code + arraysize(code));
+      for (int k = 0; k < assigned->length(); k++) {
+        bool expected = k == i || k == j;
+        CHECK_EQ(expected, assigned->Contains(k));
+      }
+    }
+  }
+}
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, NestedIf) {
+  env.AddLocals(kAstI32, 5);
+  for (int i = 0; i < 5; i++) {
+    byte code[] = {WASM_LOOP(
+        1, WASM_IF_ELSE(WASM_SET_ZERO(0), WASM_SET_ZERO(i), WASM_SET_ZERO(1)))};
+    BitVector* assigned = Analyze(code, code + arraysize(code));
+    for (int j = 0; j < assigned->length(); j++) {
+      bool expected = i == j || j == 0 || j == 1;
+      CHECK_EQ(expected, assigned->Contains(j));
+    }
+  }
+}
+
+
+static byte LEBByte(uint32_t val, byte which) {
+  byte b = (val >> (which * 7)) & 0x7F;
+  if (val >> ((which + 1) * 7)) b |= 0x80;
+  return b;
+}
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, BigLocal) {
+  env.AddLocals(kAstI32, 65000);
+  for (int i = 13; i < 65000; i = static_cast<int>(i * 1.5)) {
+    byte code[] = {kExprLoop,
+                   1,
+                   kExprSetLocal,
+                   LEBByte(i, 0),
+                   LEBByte(i, 1),
+                   LEBByte(i, 2),
+                   11,
+                   12,
+                   13};
+
+    BitVector* assigned = Analyze(code, code + arraysize(code));
+    for (int j = 0; j < assigned->length(); j++) {
+      bool expected = i == j;
+      CHECK_EQ(expected, assigned->Contains(j));
+    }
+  }
+}
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, Break) {
+  env.AddLocals(kAstI32, 3);
+  byte code[] = {
+      WASM_LOOP(1, WASM_IF(WASM_GET_LOCAL(0), WASM_BRV(1, WASM_SET_ZERO(1)))),
+      WASM_SET_ZERO(0)};
+
+  BitVector* assigned = Analyze(code, code + arraysize(code));
+  for (int j = 0; j < assigned->length(); j++) {
+    bool expected = j == 1;
+    CHECK_EQ(expected, assigned->Contains(j));
+  }
+}
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, Loop1) {
+  env.AddLocals(kAstI32, 5);
+  byte code[] = {
+      WASM_LOOP(1, WASM_IF(WASM_GET_LOCAL(0),
+                           WASM_BRV(0, WASM_SET_LOCAL(
+                                           3, WASM_I32_SUB(WASM_GET_LOCAL(0),
+                                                           WASM_I8(1)))))),
+      WASM_GET_LOCAL(0)};
+
+  BitVector* assigned = Analyze(code, code + arraysize(code));
+  for (int j = 0; j < assigned->length(); j++) {
+    bool expected = j == 3;
+    CHECK_EQ(expected, assigned->Contains(j));
+  }
+}
+
+
+TEST_F(WasmLoopAssignmentAnalyzerTest, Loop2) {
+  env.AddLocals(kAstI32, 3);
+  const byte kIter = 0;
+  env.AddLocals(kAstF32, 3);
+  const byte kSum = 3;
+
+  byte code[] = {WASM_BLOCK(
+      3,
+      WASM_WHILE(
+          WASM_GET_LOCAL(kIter),
+          WASM_BLOCK(2, WASM_SET_LOCAL(
+                            kSum, WASM_F32_ADD(
+                                      WASM_GET_LOCAL(kSum),
+                                      WASM_LOAD_MEM(MachineType::Float32(),
+                                                    WASM_GET_LOCAL(kIter)))),
+                     WASM_SET_LOCAL(kIter, WASM_I32_SUB(WASM_GET_LOCAL(kIter),
+                                                        WASM_I8(4))))),
+      WASM_STORE_MEM(MachineType::Float32(), WASM_ZERO, WASM_GET_LOCAL(kSum)),
+      WASM_GET_LOCAL(kIter))};
+
+  BitVector* assigned = Analyze(code + 2, code + arraysize(code));
+  for (int j = 0; j < assigned->length(); j++) {
+    bool expected = j == kIter || j == kSum;
+    CHECK_EQ(expected, assigned->Contains(j));
+  }
+}
+
+
+}  // namespace wasm
+}  // namespace internal
+}  // namespace v8