[turboshaft] Use absl containers instead of std::unordered*

DadaIsCrazy · V8 LUCI CQ · commit fa7521ef3eb6 · 2023-11-08T13:59:46.000Z
Bug: v8:12783 Change-Id: Ifdb5ae48d6f236ad7ace474c38c1822ebb7930f3 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/4681718 Commit-Queue: Darius Mercadier <dmercadier@chromium.org> Reviewed-by: Victor Gomes <victorgomes@chromium.org> Reviewed-by: Toon Verwaest <verwaest@chromium.org> Cr-Commit-Position: refs/heads/main@{#90814}
diff --git a/BUILD.bazel b/BUILD.bazel
@@ -3968,6 +3968,8 @@ v8_library(
     deps = [
         ":v8_libbase",
         "//external:base_trace_event_common",
+        "//external:absl_flat_hash_map",
+        "//external:absl_flat_hash_set",
     ],
 )
 
diff --git a/BUILD.gn b/BUILD.gn
@@ -1446,6 +1446,8 @@ config("toolchain") {
     if (v8_enable_slow_dchecks) {
       defines += [ "ENABLE_SLOW_DCHECKS" ]
     }
+  } else {
+    defines += [ "NDEBUG" ]
   }
 
   if (v8_enable_verify_csa) {
@@ -4629,6 +4631,7 @@ v8_header_set("v8_internal_headers") {
     ":cppgc_headers",
     ":generate_bytecode_builtins_list",
     ":run_torque",
+    ":v8_abseil",
     ":v8_heap_base_headers",
     ":v8_libbase",
   ]
diff --git a/DEPS b/DEPS
@@ -338,6 +338,8 @@ include_rules = [
   # the Chromium guidelines (though note that some requirements in V8 may be
   # different to Chromium's):
   # https://chromium.googlesource.com/chromium/src/+/main/styleguide/c++/c++11.md
+  '+absl/container/flat_hash_map.h',
+  '+absl/container/flat_hash_set.h',
   '+absl/types/optional.h',
   '+absl/types/variant.h',
   '+absl/status',
diff --git a/WORKSPACE b/WORKSPACE
@@ -44,6 +44,16 @@ bind(
     actual = "@com_google_absl//absl/types:optional"
 )
 
+bind(
+    name = "absl_flat_hash_map",
+    actual = "@com_google_absl//absl/container:flat_hash_map"
+)
+
+bind(
+    name = "absl_flat_hash_set",
+    actual = "@com_google_absl//absl/container:flat_hash_set"
+)
+
 new_local_repository(
     name = "com_googlesource_chromium_icu",
     build_file = "bazel/BUILD.icu",
diff --git a/src/compiler/turboshaft/index.h b/src/compiler/turboshaft/index.h
@@ -141,6 +141,11 @@ class OpIndex {
   uint32_t offset_;
 
   static constexpr uint32_t kTurbofanNodeIdFlag = 1;
+
+  template <typename H>
+  friend H AbslHashValue(H h, const OpIndex& idx) {
+    return H::combine(std::move(h), idx.offset_);
+  }
 };
 
 std::ostream& operator<<(std::ostream& os, OpIndex idx);
@@ -165,6 +170,11 @@ class OptionalOpIndex : protected OpIndex {
     return OpIndex(*this);
   }
   constexpr OpIndex value_or_invalid() const { return OpIndex(*this); }
+
+  template <typename H>
+  friend H AbslHashValue(H h, const OptionalOpIndex& idx) {
+    return H::combine(std::move(h), idx.offset_);
+  }
 };
 
 V8_INLINE std::ostream& operator<<(std::ostream& os, OptionalOpIndex idx) {
diff --git a/src/compiler/turboshaft/late-escape-analysis-reducer.h b/src/compiler/turboshaft/late-escape-analysis-reducer.h
@@ -36,7 +36,7 @@ class LateEscapeAnalysisAnalyzer {
   Zone* phase_zone_;
 
   // {alloc_uses_} records all the uses of each AllocateOp.
-  ZoneUnorderedMap<OpIndex, ZoneVector<OpIndex>> alloc_uses_;
+  ZoneAbslFlatHashMap<OpIndex, ZoneVector<OpIndex>> alloc_uses_;
   // {allocs_} is filled with all of the AllocateOp of the graph, and then
   // iterated upon to determine which allocations can be removed and which
   // cannot.
diff --git a/src/compiler/turboshaft/late-load-elimination-reducer.h b/src/compiler/turboshaft/late-load-elimination-reducer.h
@@ -179,6 +179,12 @@ struct MemoryAddress {
            offset == other.offset &&
            element_size_log2 == other.element_size_log2 && size == other.size;
   }
+
+  template <typename H>
+  friend H AbslHashValue(H h, const MemoryAddress& mem) {
+    return H::combine(std::move(h), mem.base, mem.index, mem.offset,
+                      mem.element_size_log2, mem.size);
+  }
 };
 
 inline size_t hash_value(MemoryAddress const& mem) {
@@ -530,16 +536,14 @@ class MemoryContentTable
   SparseOpIndexSnapshotTable<MapMaskAndOr>& object_maps_;
   FixedOpIndexSidetable<OpIndex>& replacements_;
 
-  // TODO(dmercadier): consider using a faster datastructure than
-  // ZoneUnorderedMap for {all_keys_}, {base_keys_} and {offset_keys_}.
-
   // A map containing all of the keys, for fast lookup of a specific
   // MemoryAddress.
-  ZoneUnorderedMap<MemoryAddress, Key> all_keys_;
+  ZoneAbslFlatHashMap<MemoryAddress, Key> all_keys_;
   // Map from base OpIndex to keys associated with this base.
-  ZoneUnorderedMap<OpIndex, BaseData> base_keys_;
+  ZoneAbslFlatHashMap<OpIndex, BaseData> base_keys_;
   // Map from offsets to keys associated with this offset.
-  ZoneUnorderedMap<int, DoublyThreadedList<Key, OffsetListTraits>> offset_keys_;
+  ZoneAbslFlatHashMap<int, DoublyThreadedList<Key, OffsetListTraits>>
+      offset_keys_;
 
   // List of all of the keys that have a valid index.
   DoublyThreadedList<Key, OffsetListTraits> index_keys_;
diff --git a/src/compiler/turboshaft/memory-optimization-reducer.h b/src/compiler/turboshaft/memory-optimization-reducer.h
@@ -11,6 +11,7 @@
 #include "src/compiler/turboshaft/assembler.h"
 #include "src/compiler/turboshaft/phase.h"
 #include "src/compiler/turboshaft/utils.h"
+#include "src/zone/zone-containers.h"
 
 namespace v8::internal::compiler::turboshaft {
 
@@ -55,10 +56,10 @@ struct MemoryAnalyzer {
   };
   FixedBlockSidetable<base::Optional<BlockState>> block_states{
       input_graph.block_count(), phase_zone};
-  ZoneUnorderedMap<const AllocateOp*, const AllocateOp*> folded_into{
+  ZoneAbslFlatHashMap<const AllocateOp*, const AllocateOp*> folded_into{
       phase_zone};
-  ZoneUnorderedSet<OpIndex> skipped_write_barriers{phase_zone};
-  ZoneUnorderedMap<const AllocateOp*, uint32_t> reserved_size{phase_zone};
+  ZoneAbslFlatHashSet<OpIndex> skipped_write_barriers{phase_zone};
+  ZoneAbslFlatHashMap<const AllocateOp*, uint32_t> reserved_size{phase_zone};
   BlockIndex current_block = BlockIndex(0);
   BlockState state;
 
diff --git a/src/compiler/turboshaft/operations.h b/src/compiler/turboshaft/operations.h
@@ -2912,7 +2912,13 @@ struct AllocateOp : FixedArityOperationT<1, AllocateOp> {
   void Validate(const Graph& graph) const {
   }
   void PrintOptions(std::ostream& os) const;
+
   auto options() const { return std::tuple{type}; }
+
+  // template <typename H>
+  // friend H AbslHashValue(H h, const AllocateOp& op) {
+  //   return H::combine(std::move(h), op.size(), op.type);
+  // }
 };
 
 struct DecodeExternalPointerOp
diff --git a/src/compiler/turboshaft/optimization-phase.h b/src/compiler/turboshaft/optimization-phase.h
@@ -8,7 +8,6 @@
 #include <algorithm>
 #include <cstddef>
 #include <cstdint>
-#include <unordered_map>
 #include <utility>
 
 #include "src/base/iterator.h"
@@ -23,6 +22,7 @@
 #include "src/compiler/turboshaft/phase.h"
 #include "src/compiler/turboshaft/reducer-traits.h"
 #include "src/compiler/turboshaft/snapshot-table.h"
+#include "src/zone/zone-containers.h"
 
 namespace v8::internal::compiler::turboshaft {
 
diff --git a/src/compiler/turboshaft/pretenuring-propagation-reducer.h b/src/compiler/turboshaft/pretenuring-propagation-reducer.h
@@ -9,6 +9,9 @@
 #include "src/compiler/turboshaft/phase.h"
 #include "src/compiler/turboshaft/reducer-traits.h"
 #include "src/compiler/turboshaft/utils.h"
+#include "src/zone/zone-allocator.h"
+#include "src/zone/zone-containers.h"
+#include "src/zone/zone.h"
 
 namespace v8::internal::compiler::turboshaft {
 
@@ -196,13 +199,13 @@ class PretenuringPropagationAnalyzer {
   // `store_graph_` contains mapping from OpIndex to vector<OpIndex>. If for an
   // entry `a` it contains a vector `v`, it means that `a` has edges to all of
   // the values in `v`.
-  ZoneUnorderedMap<OpIndex, ZoneVector<OpIndex>*> store_graph_;
+  ZoneAbslFlatHashMap<OpIndex, ZoneVector<OpIndex>*> store_graph_;
 
   // AllocateOp have an AllocationType field, which is set to kOld once they've
   // been visited, thus ensuring that recursion ends. However, PhiOp don't have
   // such a field. Thus, once we've visited a Phi, we store it in {old_phis_} to
   // prevent revisiting it.
-  ZoneUnorderedSet<OpIndex> old_phis_;
+  ZoneAbslFlatHashSet<OpIndex> old_phis_;
 
   // Used in the final phase to do DFS in the graph from each old store. It
   // could be a local variable, but we instead use an instance variable to reuse
diff --git a/src/compiler/turboshaft/recreate-schedule.cc b/src/compiler/turboshaft/recreate-schedule.cc
@@ -61,8 +61,8 @@ struct ScheduleBuilder {
   compiler::SimplifiedOperatorBuilder simplified{graph_zone};
   compiler::BasicBlock* current_block = schedule->start();
   const Block* current_input_block = nullptr;
-  ZoneUnorderedMap<int, Node*> parameters{phase_zone};
-  ZoneUnorderedMap<int, Node*> osr_values{phase_zone};
+  ZoneAbslFlatHashMap<int, Node*> parameters{phase_zone};
+  ZoneAbslFlatHashMap<int, Node*> osr_values{phase_zone};
   std::vector<BasicBlock*> blocks = {};
   std::vector<Node*> nodes{input_graph.op_id_count()};
   std::vector<std::pair<Node*, OpIndex>> loop_phis = {};
diff --git a/src/compiler/turboshaft/snapshot-table-opindex.h b/src/compiler/turboshaft/snapshot-table-opindex.h
@@ -10,7 +10,7 @@
 
 namespace v8::internal::compiler::turboshaft {
 // A Wrapper around a SnapshotTable, which takes care of mapping OpIndex to Key.
-// It uses a ZoneUnorderedMap to store this mapping, and is thus more
+// It uses a ZoneAbslFlatHashMap to store this mapping, and is thus more
 // appropriate for cases where not many OpIndex have a corresponding key.
 template <class Value, class KeyData = NoKeyData>
 class SparseOpIndexSnapshotTable : public SnapshotTable<Value, KeyData> {
@@ -66,7 +66,7 @@ class SparseOpIndexSnapshotTable : public SnapshotTable<Value, KeyData> {
     indices_to_keys_.insert({idx, key});
     return key;
   }
-  ZoneUnorderedMap<OpIndex, Key> indices_to_keys_;
+  ZoneAbslFlatHashMap<OpIndex, Key> indices_to_keys_;
 };
 
 }  // namespace v8::internal::compiler::turboshaft
diff --git a/src/compiler/turboshaft/store-store-elimination-reducer.h b/src/compiler/turboshaft/store-store-elimination-reducer.h
@@ -253,7 +253,7 @@ class MaybeRedundantStoresTable
 
   const Graph& graph_;
   GrowingBlockSidetable<base::Optional<Snapshot>> block_to_snapshot_mapping_;
-  ZoneUnorderedMap<std::pair<OpIndex, int32_t>, Key> key_mapping_;
+  ZoneAbslFlatHashMap<std::pair<OpIndex, int32_t>, Key> key_mapping_;
   // In `active_keys_`, we track the keys of all stores that arge gc-observable
   // or unobservable. Keys that are mapped to the default value (observable) are
   // removed from the `active_keys_`.
diff --git a/src/zone/zone-containers.h b/src/zone/zone-containers.h
@@ -17,6 +17,8 @@
 #include <unordered_map>
 #include <unordered_set>
 
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/flat_hash_set.h"
 #include "src/base/functional.h"
 #include "src/base/intrusive-set.h"
 #include "src/base/small-map.h"
@@ -783,6 +785,41 @@ class SmallZoneMap
             ZoneMapInit<ZoneMap<K, V, Compare>>(zone)) {}
 };
 
+// A wrapper subclass for absl::flat_hash_map to make it easy to construct one
+// that uses a zone allocator. If you want to use a user-defined type as key
+// (K), you'll need to define a AbslHashValue function for it (see
+// https://abseil.io/docs/cpp/guides/hash).
+template <typename K, typename V,
+          typename Hash = typename absl::flat_hash_map<K, V>::hasher,
+          typename KeyEqual =
+              typename absl::flat_hash_map<K, V, Hash>::key_equal>
+class ZoneAbslFlatHashMap
+    : public absl::flat_hash_map<K, V, Hash, KeyEqual,
+                                 ZoneAllocator<std::pair<const K, V>>> {
+ public:
+  // Constructs an empty map.
+  explicit ZoneAbslFlatHashMap(Zone* zone, size_t bucket_count = 100)
+      : absl::flat_hash_map<K, V, Hash, KeyEqual,
+                            ZoneAllocator<std::pair<const K, V>>>(
+            bucket_count, Hash(), KeyEqual(),
+            ZoneAllocator<std::pair<const K, V>>(zone)) {}
+};
+
+// A wrapper subclass for absl::flat_hash_set to make it easy to construct one
+// that uses a zone allocator. If you want to use a user-defined type as key
+// (K), you'll need to define a AbslHashValue function for it (see
+// https://abseil.io/docs/cpp/guides/hash).
+template <typename K, typename Hash = typename absl::flat_hash_set<K>::hasher,
+          typename KeyEqual = typename absl::flat_hash_set<K, Hash>::key_equal>
+class ZoneAbslFlatHashSet
+    : public absl::flat_hash_set<K, Hash, KeyEqual, ZoneAllocator<K>> {
+ public:
+  // Constructs an empty map.
+  explicit ZoneAbslFlatHashSet(Zone* zone, size_t bucket_count = 100)
+      : absl::flat_hash_set<K, Hash, KeyEqual, ZoneAllocator<K>>(
+            bucket_count, Hash(), KeyEqual(), ZoneAllocator<K>(zone)) {}
+};
+
 // Typedefs to shorten commonly used vectors.
 using IntVector = ZoneVector<int>;
 
diff --git a/test/BUILD.gn b/test/BUILD.gn
@@ -176,6 +176,7 @@ v8_header_set("common_test_headers") {
   configs = []
 
   public_deps = [
+    "../:v8_abseil",
     "../:v8_internal_headers",
     "../:v8_libbase",
   ]
diff --git a/tools/gcmole/BUILD.gn b/tools/gcmole/BUILD.gn
@@ -31,6 +31,7 @@ if (v8_gcmole) {
       "../../test/cctest/",
       "../../test/common/",
       "../../testing/gtest/include/gtest/gtest_prod.h",
+      "../../third_party/abseil-cpp/",
       "../../third_party/glibc/",
       "../../third_party/googletest/src/googletest/include/gtest/gtest_prod.h",
       "../../third_party/icu/source/common/",

Original file line number	Diff line number	Diff line change
`@@ -3968,6 +3968,8 @@ v8_library(`
`3968`	`3968`	`deps = [`
`3969`	`3969`	`":v8_libbase",`
`3970`	`3970`	`"//external:base_trace_event_common",`
	`3971`	`+ "//external:absl_flat_hash_map",`
	`3972`	`+ "//external:absl_flat_hash_set",`
`3971`	`3973`	`],`
`3972`	`3974`	`)`
`3973`	`3975`
Original file line number	Diff line number	Diff line change
`@@ -1446,6 +1446,8 @@ config("toolchain") {`
`1446`	`1446`	`if (v8_enable_slow_dchecks) {`
`1447`	`1447`	`defines += [ "ENABLE_SLOW_DCHECKS" ]`
`1448`	`1448`	`}`
	`1449`	`+ } else {`
	`1450`	`+ defines += [ "NDEBUG" ]`
`1449`	`1451`	`}`
`1450`	`1452`
`1451`	`1453`	`if (v8_enable_verify_csa) {`
`@@ -4629,6 +4631,7 @@ v8_header_set("v8_internal_headers") {`
`4629`	`4631`	`":cppgc_headers",`
`4630`	`4632`	`":generate_bytecode_builtins_list",`
`4631`	`4633`	`":run_torque",`
	`4634`	`+ ":v8_abseil",`
`4632`	`4635`	`":v8_heap_base_headers",`
`4633`	`4636`	`":v8_libbase",`
`4634`	`4637`	`]`