test-swiss-name-dictionary-csa.cc 16.6 KB
Newer Older
1 2 3 4
// Copyright 2021 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.

5
#include "src/codegen/code-stub-assembler.h"
6
#include "src/codegen/cpu-features.h"
7 8 9 10
#include "src/objects/objects-inl.h"
#include "src/objects/swiss-name-dictionary-inl.h"
#include "test/cctest/compiler/code-assembler-tester.h"
#include "test/cctest/compiler/function-tester.h"
11
#include "test/cctest/test-swiss-name-dictionary-infra.h"
12
#include "test/cctest/test-swiss-name-dictionary-shared-tests.h"
13 14 15 16 17

namespace v8 {
namespace internal {
namespace test_swiss_hash_table {

18 19 20 21 22 23 24 25 26 27 28 29
// The non-SIMD SwissNameDictionary implementation requires 64 bit integer
// operations, which CSA/Torque don't offer on 32 bit platforms. Therefore, we
// cannot run the CSA version of the tests on 32 bit platforms. The only
// exception is IA32, where we can use SSE and don't need 64 bit integers.
// TODO(v8:11330) The Torque SIMD implementation is not specific to SSE (like
// the C++ one), but works on other platforms. It should be possible to create a
// workaround where on 32 bit, non-IA32 platforms we use the "portable", non-SSE
// implementation on the C++ side (which uses a group size of 8) and create a
// special version of the SIMD Torque implementation that works for group size 8
// instead of 16.
#if V8_TARGET_ARCH_64_BIT || V8_TARGET_ARCH_IA32

30 31 32 33 34 35
// Executes tests by executing CSA/Torque versions of dictionary operations.
// See RuntimeTestRunner for description of public functions.
class CSATestRunner {
 public:
  CSATestRunner(Isolate* isolate, int initial_capacity, KeyCache& keys);

36 37 38 39 40 41 42 43 44 45 46 47 48
  // TODO(v8:11330): Remove once CSA implementation has a fallback for
  // non-SSSE3/AVX configurations.
  static bool IsEnabled() {
#if V8_TARGET_ARCH_X64 || V8_TARGET_ARCH_IA32
    CpuFeatures::SupportedFeatures();
    return CpuFeatures::IsSupported(CpuFeature::AVX) ||
           CpuFeatures::IsSupported(CpuFeature::SSSE3);
#else
    // Other 64-bit architectures always support the required operations.
    return true;
#endif
  }

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
  void Add(Handle<Name> key, Handle<Object> value, PropertyDetails details);
  InternalIndex FindEntry(Handle<Name> key);
  void Put(InternalIndex entry, Handle<Object> new_value,
           PropertyDetails new_details);
  void Delete(InternalIndex entry);
  void RehashInplace();
  void Shrink();

  Handle<FixedArray> GetData(InternalIndex entry);
  void CheckCounts(base::Optional<int> capacity, base::Optional<int> elements,
                   base::Optional<int> deleted);
  void CheckEnumerationOrder(const std::vector<std::string>& expected_keys);
  void CheckCopy();
  void VerifyHeap();

  void PrintTable();

  Handle<SwissNameDictionary> table;

 private:
69 70 71 72
  using Label = compiler::CodeAssemblerLabel;
  template <class T>
  using TVariable = compiler::TypedCodeAssemblerVariable<T>;

73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
  void CheckAgainstReference();

  void Allocate(Handle<Smi> capacity);

  Isolate* isolate_;

  // Used to mirror all operations using C++ versions of all operations,
  // yielding a reference to compare against.
  Handle<SwissNameDictionary> reference_;

  // CSA functions execute the corresponding dictionary operation.
  compiler::FunctionTester find_entry_ft_;
  compiler::FunctionTester get_data_ft_;
  compiler::FunctionTester put_ft_;
  compiler::FunctionTester delete_ft_;
  compiler::FunctionTester add_ft_;
  compiler::FunctionTester allocate_ft_;
90 91
  compiler::FunctionTester get_counts_ft_;
  compiler::FunctionTester copy_ft_;
92 93 94 95 96 97 98 99

  // Used to create the FunctionTesters above.
  static Handle<Code> create_get_data(Isolate* isolate);
  static Handle<Code> create_find_entry(Isolate* isolate);
  static Handle<Code> create_put(Isolate* isolate);
  static Handle<Code> create_delete(Isolate* isolate);
  static Handle<Code> create_add(Isolate* isolate);
  static Handle<Code> create_allocate(Isolate* isolate);
100 101
  static Handle<Code> create_get_counts(Isolate* isolate);
  static Handle<Code> create_copy(Isolate* isolate);
102 103 104 105 106 107 108 109

  // Number of parameters of each of the tester functions above.
  static constexpr int kFindEntryParams = 2;  // (table, key)
  static constexpr int kGetDataParams = 2;    // (table, entry)
  static constexpr int kPutParams = 4;        // (table, entry, value,  details)
  static constexpr int kDeleteParams = 2;     // (table, entry)
  static constexpr int kAddParams = 4;        // (table, key, value, details)
  static constexpr int kAllocateParams = 1;   // (capacity)
110 111
  static constexpr int kGetCountsParams = 1;  // (table)
  static constexpr int kCopyParams = 1;       // (table)
112 113 114 115 116 117 118 119 120 121 122 123
};

CSATestRunner::CSATestRunner(Isolate* isolate, int initial_capacity,
                             KeyCache& keys)
    : isolate_{isolate},
      reference_{isolate_->factory()->NewSwissNameDictionaryWithCapacity(
          initial_capacity, AllocationType::kYoung)},
      find_entry_ft_(create_find_entry(isolate), kFindEntryParams),
      get_data_ft_(create_get_data(isolate), kGetDataParams),
      put_ft_{create_put(isolate), kPutParams},
      delete_ft_{create_delete(isolate), kDeleteParams},
      add_ft_{create_add(isolate), kAddParams},
124 125 126 127
      allocate_ft_{create_allocate(isolate), kAllocateParams},
      get_counts_ft_{create_get_counts(isolate), kGetCountsParams},
      copy_ft_{create_copy(isolate), kCopyParams} {
  Allocate(handle(Smi::FromInt(initial_capacity), isolate));
128 129 130 131
}

void CSATestRunner::Add(Handle<Name> key, Handle<Object> value,
                        PropertyDetails details) {
132
  ReadOnlyRoots roots(isolate_);
133 134 135 136
  reference_ =
      SwissNameDictionary::Add(isolate_, reference_, key, value, details);

  Handle<Smi> details_smi = handle(details.AsSmi(), isolate_);
137 138 139 140 141 142 143 144 145 146 147 148 149
  Handle<Oddball> success =
      add_ft_.CallChecked<Oddball>(table, key, value, details_smi);

  if (*success == roots.false_value()) {
    // |add_ft_| does not resize and indicates the need to do so by returning
    // false.
    int capacity = table->Capacity();
    int used_capacity = table->UsedCapacity();
    CHECK_GT(used_capacity + 1,
             SwissNameDictionary::MaxUsableCapacity(capacity));

    table = SwissNameDictionary::Add(isolate_, table, key, value, details);
  }
150 151 152 153 154

  CheckAgainstReference();
}

void CSATestRunner::Allocate(Handle<Smi> capacity) {
155 156 157 158 159 160 161 162
  // We must handle |capacity| == 0 specially, because
  // AllocateSwissNameDictionary (just like AllocateNameDictionary) always
  // returns a non-zero sized table.
  if (capacity->value() == 0) {
    table = ReadOnlyRoots(isolate_).empty_swiss_property_dictionary_handle();
  } else {
    table = allocate_ft_.CallChecked<SwissNameDictionary>(capacity);
  }
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185

  CheckAgainstReference();
}

InternalIndex CSATestRunner::FindEntry(Handle<Name> key) {
  Handle<Smi> index = find_entry_ft_.CallChecked<Smi>(table, key);
  if (index->value() == SwissNameDictionary::kNotFoundSentinel) {
    return InternalIndex::NotFound();
  } else {
    return InternalIndex(index->value());
  }
}

Handle<FixedArray> CSATestRunner::GetData(InternalIndex entry) {
  DCHECK(entry.is_found());

  return get_data_ft_.CallChecked<FixedArray>(
      table, handle(Smi::FromInt(entry.as_int()), isolate_));
}

void CSATestRunner::CheckCounts(base::Optional<int> capacity,
                                base::Optional<int> elements,
                                base::Optional<int> deleted) {
186 187 188 189 190 191 192 193 194 195 196 197 198 199
  Handle<FixedArray> counts = get_counts_ft_.CallChecked<FixedArray>(table);

  if (capacity.has_value()) {
    CHECK_EQ(Smi::FromInt(capacity.value()), counts->get(0));
  }

  if (elements.has_value()) {
    CHECK_EQ(Smi::FromInt(elements.value()), counts->get(1));
  }

  if (deleted.has_value()) {
    CHECK_EQ(Smi::FromInt(deleted.value()), counts->get(2));
  }

200 201 202 203 204
  CheckAgainstReference();
}

void CSATestRunner::CheckEnumerationOrder(
    const std::vector<std::string>& expected_keys) {
205 206 207 208
  // Not implemented in CSA. Making this a no-op (rather than forbidding
  // executing CSA tests with this operation) because CheckEnumerationOrder is
  // also used by some tests whose main goal is not to test the enumeration
  // order.
209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
}

void CSATestRunner::Put(InternalIndex entry, Handle<Object> new_value,
                        PropertyDetails new_details) {
  DCHECK(entry.is_found());
  reference_->ValueAtPut(entry, *new_value);
  reference_->DetailsAtPut(entry, new_details);

  Handle<Smi> entry_smi = handle(Smi::FromInt(entry.as_int()), isolate_);
  Handle<Smi> details_smi = handle(new_details.AsSmi(), isolate_);

  put_ft_.Call(table, entry_smi, new_value, details_smi);

  CheckAgainstReference();
}

void CSATestRunner::Delete(InternalIndex entry) {
  DCHECK(entry.is_found());
  reference_ = SwissNameDictionary::DeleteEntry(isolate_, reference_, entry);

  Handle<Smi> entry_smi = handle(Smi::FromInt(entry.as_int()), isolate_);
  table = delete_ft_.CallChecked<SwissNameDictionary>(table, entry_smi);
231

232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247
  CheckAgainstReference();
}

void CSATestRunner::RehashInplace() {
  // There's no CSA version of this. Use IsRuntimeTest to ensure that we only
  // run a test using this if it's a runtime test.
  UNREACHABLE();
}

void CSATestRunner::Shrink() {
  // There's no CSA version of this. Use IsRuntimeTest to ensure that we only
  // run a test using this if it's a runtime test.
  UNREACHABLE();
}

void CSATestRunner::CheckCopy() {
248 249 250
  Handle<SwissNameDictionary> copy =
      copy_ft_.CallChecked<SwissNameDictionary>(table);
  CHECK(table->EqualsForTesting(*copy));
251 252 253 254 255 256 257 258 259 260 261 262 263 264 265
}

void CSATestRunner::VerifyHeap() {
#if VERIFY_HEAP
  table->SwissNameDictionaryVerify(isolate_, true);
#endif
}

void CSATestRunner::PrintTable() {
#ifdef OBJECT_PRINT
  table->SwissNameDictionaryPrint(std::cout);
#endif
}

Handle<Code> CSATestRunner::create_find_entry(Isolate* isolate) {
266 267 268
  // TODO(v8:11330): Remove once CSA implementation has a fallback for
  // non-SSSE3/AVX configurations.
  if (!IsEnabled()) {
269 270
    return FromCodeT(isolate->builtins()->code_handle(Builtin::kIllegal),
                     isolate);
271
  }
272
  static_assert(kFindEntryParams == 2);  // (table, key)
273 274 275 276 277 278
  compiler::CodeAssemblerTester asm_tester(isolate, kFindEntryParams + 1);
  CodeStubAssembler m(asm_tester.state());
  {
    TNode<SwissNameDictionary> table = m.Parameter<SwissNameDictionary>(1);
    TNode<Name> key = m.Parameter<Name>(2);

279 280 281 282 283 284 285
    Label done(&m);
    TVariable<IntPtrT> entry_var(
        m.IntPtrConstant(SwissNameDictionary::kNotFoundSentinel), &m);

    // |entry_var| defaults to |kNotFoundSentinel| meaning that  one label
    // suffices.
    m.SwissNameDictionaryFindEntry(table, key, &done, &entry_var, &done);
286

287 288
    m.Bind(&done);
    m.Return(m.SmiFromIntPtr(entry_var.value()));
289 290 291 292 293 294
  }

  return asm_tester.GenerateCodeCloseAndEscape();
}

Handle<Code> CSATestRunner::create_get_data(Isolate* isolate) {
295
  static_assert(kGetDataParams == 2);  // (table, entry)
296 297 298 299
  compiler::CodeAssemblerTester asm_tester(isolate, kGetDataParams + 1);
  CodeStubAssembler m(asm_tester.state());
  {
    TNode<SwissNameDictionary> table = m.Parameter<SwissNameDictionary>(1);
300
    TNode<IntPtrT> entry = m.SmiToIntPtr(m.Parameter<Smi>(2));
301 302 303

    TNode<FixedArray> data = m.AllocateZeroedFixedArray(m.IntPtrConstant(3));

304 305 306
    TNode<Object> key = m.LoadSwissNameDictionaryKey(table, entry);
    TNode<Object> value = m.LoadValueByKeyIndex(table, entry);
    TNode<Smi> details = m.SmiFromUint32(m.LoadDetailsByKeyIndex(table, entry));
307 308 309 310 311 312 313 314 315 316 317

    m.StoreFixedArrayElement(data, 0, key);
    m.StoreFixedArrayElement(data, 1, value);
    m.StoreFixedArrayElement(data, 2, details);

    m.Return(data);
  }
  return asm_tester.GenerateCodeCloseAndEscape();
}

Handle<Code> CSATestRunner::create_put(Isolate* isolate) {
318
  static_assert(kPutParams == 4);  // (table, entry, value, details)
319 320 321 322 323 324 325 326
  compiler::CodeAssemblerTester asm_tester(isolate, kPutParams + 1);
  CodeStubAssembler m(asm_tester.state());
  {
    TNode<SwissNameDictionary> table = m.Parameter<SwissNameDictionary>(1);
    TNode<Smi> entry = m.Parameter<Smi>(2);
    TNode<Object> value = m.Parameter<Object>(3);
    TNode<Smi> details = m.Parameter<Smi>(4);

327 328 329 330 331 332
    TNode<IntPtrT> entry_intptr = m.SmiToIntPtr(entry);

    m.StoreValueByKeyIndex(table, entry_intptr, value,
                           WriteBarrierMode::UPDATE_WRITE_BARRIER);
    m.StoreDetailsByKeyIndex(table, entry_intptr, details);

333 334 335 336 337 338
    m.Return(m.UndefinedConstant());
  }
  return asm_tester.GenerateCodeCloseAndEscape();
}

Handle<Code> CSATestRunner::create_delete(Isolate* isolate) {
339 340 341
  // TODO(v8:11330): Remove once CSA implementation has a fallback for
  // non-SSSE3/AVX configurations.
  if (!IsEnabled()) {
342 343
    return FromCodeT(isolate->builtins()->code_handle(Builtin::kIllegal),
                     isolate);
344
  }
345
  static_assert(kDeleteParams == 2);  // (table, entry)
346 347 348 349
  compiler::CodeAssemblerTester asm_tester(isolate, kDeleteParams + 1);
  CodeStubAssembler m(asm_tester.state());
  {
    TNode<SwissNameDictionary> table = m.Parameter<SwissNameDictionary>(1);
350 351 352 353
    TNode<IntPtrT> entry = m.SmiToIntPtr(m.Parameter<Smi>(2));

    TVariable<SwissNameDictionary> shrunk_table_var(table, &m);
    Label done(&m);
354

355 356
    m.SwissNameDictionaryDelete(table, entry, &done, &shrunk_table_var);
    m.Goto(&done);
357

358 359
    m.Bind(&done);
    m.Return(shrunk_table_var.value());
360 361 362 363 364
  }
  return asm_tester.GenerateCodeCloseAndEscape();
}

Handle<Code> CSATestRunner::create_add(Isolate* isolate) {
365 366 367
  // TODO(v8:11330): Remove once CSA implementation has a fallback for
  // non-SSSE3/AVX configurations.
  if (!IsEnabled()) {
368 369
    return FromCodeT(isolate->builtins()->code_handle(Builtin::kIllegal),
                     isolate);
370
  }
371
  static_assert(kAddParams == 4);  // (table, key, value, details)
372 373 374 375 376 377 378 379
  compiler::CodeAssemblerTester asm_tester(isolate, kAddParams + 1);
  CodeStubAssembler m(asm_tester.state());
  {
    TNode<SwissNameDictionary> table = m.Parameter<SwissNameDictionary>(1);
    TNode<Name> key = m.Parameter<Name>(2);
    TNode<Object> value = m.Parameter<Object>(3);
    TNode<Smi> details = m.Parameter<Smi>(4);

380 381 382 383
    Label needs_resize(&m);

    TNode<Int32T> d32 = m.SmiToInt32(details);
    TNode<Uint8T> d = m.UncheckedCast<Uint8T>(d32);
384

385 386 387 388 389
    m.SwissNameDictionaryAdd(table, key, value, d, &needs_resize);
    m.Return(m.TrueConstant());

    m.Bind(&needs_resize);
    m.Return(m.FalseConstant());
390 391 392 393 394
  }
  return asm_tester.GenerateCodeCloseAndEscape();
}

Handle<Code> CSATestRunner::create_allocate(Isolate* isolate) {
395
  static_assert(kAllocateParams == 1);  // (capacity)
396 397 398
  compiler::CodeAssemblerTester asm_tester(isolate, kAllocateParams + 1);
  CodeStubAssembler m(asm_tester.state());
  {
399
    TNode<IntPtrT> capacity = m.SmiToIntPtr(m.Parameter<Smi>(1));
400

401 402
    TNode<SwissNameDictionary> table =
        m.AllocateSwissNameDictionaryWithCapacity(capacity);
403 404 405 406 407 408

    m.Return(table);
  }
  return asm_tester.GenerateCodeCloseAndEscape();
}

409
Handle<Code> CSATestRunner::create_get_counts(Isolate* isolate) {
410
  static_assert(kGetCountsParams == 1);  // (table)
411 412 413 414 415 416 417 418 419 420 421 422 423 424 425
  compiler::CodeAssemblerTester asm_tester(isolate, kGetCountsParams + 1);
  CodeStubAssembler m(asm_tester.state());
  {
    TNode<SwissNameDictionary> table = m.Parameter<SwissNameDictionary>(1);

    TNode<IntPtrT> capacity =
        m.ChangeInt32ToIntPtr(m.LoadSwissNameDictionaryCapacity(table));
    TNode<IntPtrT> elements =
        m.LoadSwissNameDictionaryNumberOfElements(table, capacity);
    TNode<IntPtrT> deleted =
        m.LoadSwissNameDictionaryNumberOfDeletedElements(table, capacity);

    TNode<FixedArray> results = m.AllocateZeroedFixedArray(m.IntPtrConstant(3));

    auto check_and_add = [&](TNode<IntPtrT> value, int array_index) {
426 427
      CSA_DCHECK(&m, m.UintPtrGreaterThanOrEqual(value, m.IntPtrConstant(0)));
      CSA_DCHECK(&m, m.UintPtrLessThanOrEqual(
428 429 430 431 432 433 434 435 436 437 438 439 440 441 442
                         value, m.IntPtrConstant(Smi::kMaxValue)));
      TNode<Smi> smi = m.SmiFromIntPtr(value);
      m.StoreFixedArrayElement(results, array_index, smi);
    };

    check_and_add(capacity, 0);
    check_and_add(elements, 1);
    check_and_add(deleted, 2);

    m.Return(results);
  }
  return asm_tester.GenerateCodeCloseAndEscape();
}

Handle<Code> CSATestRunner::create_copy(Isolate* isolate) {
443
  static_assert(kCopyParams == 1);  // (table)
444 445 446 447 448 449 450 451 452 453
  compiler::CodeAssemblerTester asm_tester(isolate, kCopyParams + 1);
  CodeStubAssembler m(asm_tester.state());
  {
    TNode<SwissNameDictionary> table = m.Parameter<SwissNameDictionary>(1);

    m.Return(m.CopySwissNameDictionary(table));
  }
  return asm_tester.GenerateCodeCloseAndEscape();
}

454 455 456 457
void CSATestRunner::CheckAgainstReference() {
  CHECK(table->EqualsForTesting(*reference_));
}

458 459 460 461 462 463 464
// Executes the tests defined in test-swiss-name-dictionary-shared-tests.h as if
// they were defined in this file, using the CSATestRunner. See comments in
// test-swiss-name-dictionary-shared-tests.h and in
// swiss-name-dictionary-infra.h for details.
const char kCSATestFileName[] = __FILE__;
SharedSwissTableTests<CSATestRunner, kCSATestFileName> execute_shared_tests_csa;

465 466
#endif

467 468 469
}  // namespace test_swiss_hash_table
}  // namespace internal
}  // namespace v8