From c96e0afbf1060dc719356b8c82601c45ad688110 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 7 Nov 2022 23:02:21 +0000 Subject: Begin work on implementing the new `map` internals --- src/check_type.cpp | 49 ++++++++----------------------------------------- 1 file changed, 8 insertions(+), 41 deletions(-) (limited to 'src/check_type.cpp') diff --git a/src/check_type.cpp b/src/check_type.cpp index 2ffe04342..ea1c90a66 100644 --- a/src/check_type.cpp +++ b/src/check_type.cpp @@ -2176,40 +2176,9 @@ Type *make_optional_ok_type(Type *value, bool typed) { return t; } -void init_map_entry_type(Type *type) { - GB_ASSERT(type->kind == Type_Map); - if (type->Map.entry_type != nullptr) return; - - // NOTE(bill): The preload types may have not been set yet - GB_ASSERT(t_map_hash != nullptr); - - /* - struct { - hash: uintptr, - next: int, - key: Key, - value: Value, - } - */ - Scope *s = create_scope(nullptr, builtin_pkg->scope); - - auto fields = slice_make(permanent_allocator(), 4); - fields[0] = alloc_entity_field(s, make_token_ident(str_lit("hash")), t_uintptr, false, 0, EntityState_Resolved); - fields[1] = alloc_entity_field(s, make_token_ident(str_lit("next")), t_int, false, 1, EntityState_Resolved); - fields[2] = alloc_entity_field(s, make_token_ident(str_lit("key")), type->Map.key, false, 2, EntityState_Resolved); - fields[3] = alloc_entity_field(s, make_token_ident(str_lit("value")), type->Map.value, false, 3, EntityState_Resolved); - - Type *entry_type = alloc_type_struct(); - entry_type->Struct.fields = fields; - entry_type->Struct.tags = gb_alloc_array(permanent_allocator(), String, fields.count); - - type_set_offsets(entry_type); - type->Map.entry_type = entry_type; -} - void init_map_internal_types(Type *type) { GB_ASSERT(type->kind == Type_Map); - init_map_entry_type(type); + GB_ASSERT(t_allocator != nullptr); if (type->Map.internal_type != nullptr) return; Type *key = type->Map.key; @@ -2221,19 +2190,17 @@ void init_map_internal_types(Type *type) { /* struct { - hashes: []int; - entries: [dynamic]EntryType; + data: uintptr, + size: uintptr, + allocator: runtime.Allocator, } */ Scope *s = create_scope(nullptr, builtin_pkg->scope); - Type *hashes_type = alloc_type_slice(t_int); - Type *entries_type = alloc_type_dynamic_array(type->Map.entry_type); - - - auto fields = slice_make(permanent_allocator(), 2); - fields[0] = alloc_entity_field(s, make_token_ident(str_lit("hashes")), hashes_type, false, 0, EntityState_Resolved); - fields[1] = alloc_entity_field(s, make_token_ident(str_lit("entries")), entries_type, false, 1, EntityState_Resolved); + auto fields = slice_make(permanent_allocator(), 3); + fields[0] = alloc_entity_field(s, make_token_ident(str_lit("data")), t_uintptr, false, 0, EntityState_Resolved); + fields[1] = alloc_entity_field(s, make_token_ident(str_lit("size")), t_uintptr, false, 1, EntityState_Resolved); + fields[2] = alloc_entity_field(s, make_token_ident(str_lit("allocator")), t_allocator, false, 2, EntityState_Resolved); generated_struct_type->Struct.fields = fields; type_set_offsets(generated_struct_type); -- cgit v1.2.3 From da774e3fd22848bdedf5aadb9d897c0c4e9d9b7a Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 8 Nov 2022 00:38:31 +0000 Subject: General modifications --- core/fmt/fmt.odin | 3 +- core/runtime/dynamic_map_internal.odin | 48 ++++++++------- src/check_type.cpp | 19 ++++++ src/llvm_backend.cpp | 19 +----- src/llvm_backend.hpp | 2 - src/llvm_backend_stmt.cpp | 107 +++++++++++++++++++++++++++++---- src/llvm_backend_utility.cpp | 44 +++++++------- 7 files changed, 165 insertions(+), 77 deletions(-) (limited to 'src/check_type.cpp') diff --git a/core/fmt/fmt.odin b/core/fmt/fmt.odin index b4118a95b..384f43aa5 100644 --- a/core/fmt/fmt.odin +++ b/core/fmt/fmt.odin @@ -2075,9 +2075,10 @@ fmt_value :: proc(fi: ^Info, v: any, verb: rune) { map_cap := uintptr(runtime.map_cap(m^)) ks, vs, hs, _, _ := runtime.map_kvh_data_dynamic(m^, info.map_info) j := 0 + fmt_arg(fi, map_cap, 'v') for bucket_index in 0.. 0 { diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index 5e1c67e1c..f173f095a 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -88,7 +88,7 @@ MAP_CACHE_LINE_SIZE :: 1 << MAP_CACHE_LINE_LOG2 // In the optimal case, len(Map_Cell(T){}.data) = 1 so the cell array can be treated // as a regular array of T, which is the case for hashes. Map_Cell :: struct($T: typeid) #align MAP_CACHE_LINE_SIZE { - data: [MAP_CACHE_LINE_SIZE / size_of(T) when size_of(T) < MAP_CACHE_LINE_SIZE else 1]T, + data: [MAP_CACHE_LINE_SIZE / size_of(T) when 0 < size_of(T) && size_of(T) < MAP_CACHE_LINE_SIZE else 1]T, } // So we can operate on a cell data structure at runtime without any type @@ -107,36 +107,38 @@ Map_Cell_Info :: struct { map_cell_index_dynamic :: #force_inline proc "contextless" (base: uintptr, info: ^Map_Cell_Info, index: uintptr) -> uintptr { // Micro-optimize the case when the number of elements per cell is one or two // to save on expensive integer division. + + cell_index, data_index: uintptr switch elements_per_cell := info.elements_per_cell; elements_per_cell { case 1: return base + (index * info.size_of_cell) case 2: - cell_index := index >> 1 - data_index := index & 1 + cell_index = index >> 1 + data_index = index & 1 return base + (cell_index * info.size_of_cell) + (data_index * info.size_of_type) case 4: - cell_index := index >> 2 - data_index := index & 3 + cell_index = index >> 2 + data_index = index & 3 return base + (cell_index * info.size_of_cell) + (data_index * info.size_of_type) case 8: - cell_index := index >> 3 - data_index := index & 7 + cell_index = index >> 3 + data_index = index & 7 return base + (cell_index * info.size_of_cell) + (data_index * info.size_of_type) case 16: - cell_index := index >> 4 - data_index := index & 15 + cell_index = index >> 4 + data_index = index & 15 return base + (cell_index * info.size_of_cell) + (data_index * info.size_of_type) case 32: - cell_index := index >> 5 - data_index := index & 31 + cell_index = index >> 5 + data_index = index & 31 return base + (cell_index * info.size_of_cell) + (data_index * info.size_of_type) case 64: - cell_index := index >> 6 - data_index := index & 63 + cell_index = index >> 6 + data_index = index & 63 return base + (cell_index * info.size_of_cell) + (data_index * info.size_of_type) case: - cell_index := index / elements_per_cell - data_index := index % elements_per_cell + cell_index = index / elements_per_cell + data_index = index % elements_per_cell return base + (cell_index * info.size_of_cell) + (data_index * info.size_of_type) } } @@ -309,7 +311,7 @@ map_alloc_dynamic :: proc(info: ^Map_Info, log2_capacity: uintptr, allocator := return {}, .Out_Of_Memory } - capacity := uintptr(1) << log2_capacity + capacity := uintptr(1) << max(log2_capacity, MAP_MIN_LOG2_CAPACITY) @static INFO_HS := Map_Cell_Info { size_of(Map_Hash), @@ -552,6 +554,9 @@ map_reserve_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, ne allocator = context.allocator } + new_capacity := new_capacity + new_capacity = max(new_capacity, uintptr(1)< rawptr { +__dynamic_map_get :: proc "contextless" (m: rawptr, #no_alias info: ^Map_Info, key: rawptr) -> (ptr: rawptr) { rm := (^Raw_Map)(m)^ - index, ok := map_lookup_dynamic(rm, info, uintptr(key)) - if !ok { - return nil + if index, ok := map_lookup_dynamic(rm, info, uintptr(key)); ok { + vs := map_kvh_data_values_dynamic(rm, info) + ptr = rawptr(map_cell_index_dynamic(vs, &info.vs, index)) } - vs := map_kvh_data_values_dynamic(rm, info) - return rawptr(map_cell_index_dynamic(vs, &info.vs, index)) + return } __dynamic_map_set :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, key, value: rawptr, loc := #caller_location) -> rawptr { diff --git a/src/check_type.cpp b/src/check_type.cpp index ea1c90a66..39344fb2c 100644 --- a/src/check_type.cpp +++ b/src/check_type.cpp @@ -2176,6 +2176,25 @@ Type *make_optional_ok_type(Type *value, bool typed) { return t; } + +// IMPORTANT NOTE(bill): This must match the definition in dynamic_map_internal.odin +enum : i64 { + MAP_CACHE_LINE_LOG2 = 6, + MAP_CACHE_LINE_SIZE = 1 << MAP_CACHE_LINE_LOG2 +}; +GB_STATIC_ASSERT(MAP_CACHE_LINE_SIZE >= 64); +void map_cell_size_and_len(Type *type, i64 *size_, i64 *len_) { + i64 elem_sz = type_size_of(type); + + i64 len = 1; + if (0 < elem_sz && elem_sz < MAP_CACHE_LINE_SIZE) { + len = MAP_CACHE_LINE_SIZE / elem_sz; + } + i64 size = align_formula(elem_sz * len, MAP_CACHE_LINE_SIZE); + if (size_) *size_ = size; + if (len_) *len_ = len; +} + void init_map_internal_types(Type *type) { GB_ASSERT(type->kind == Type_Map); GB_ASSERT(t_allocator != nullptr); diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 7c1e53b7f..fa9727106 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -500,27 +500,10 @@ lbValue lb_generate_anonymous_proc_lit(lbModule *m, String const &prefix_name, A return value; } -// IMPORTANT NOTE(bill): This must match the definition in dynamic_map_internal.odin -enum : i64 { - MAP_CACHE_LINE_LOG2 = 6, - MAP_CACHE_LINE_SIZE = 1 << MAP_CACHE_LINE_LOG2 -}; -GB_STATIC_ASSERT(MAP_CACHE_LINE_SIZE >= 64); -void lb_map_cell_size_and_len(Type *type, i64 *size_, i64 *len_) { - i64 elem_sz = type_size_of(type); - - i64 len = 1; - if (0 < elem_sz && elem_sz < MAP_CACHE_LINE_SIZE) { - len = MAP_CACHE_LINE_SIZE / elem_sz; - } - i64 size = align_formula(elem_sz * len, MAP_CACHE_LINE_SIZE); - if (size_) *size_ = size; - if (len_) *len_ = len; -} LLVMValueRef lb_gen_map_cell_info(lbModule *m, Type *type) { i64 size = 0, len = 0; - lb_map_cell_size_and_len(type, &size, &len); + map_cell_size_and_len(type, &size, &len); LLVMValueRef const_values[4] = {}; const_values[0] = lb_const_int(m, t_uintptr, type_size_of(type)).value; diff --git a/src/llvm_backend.hpp b/src/llvm_backend.hpp index f4d4cce21..2b9014d94 100644 --- a/src/llvm_backend.hpp +++ b/src/llvm_backend.hpp @@ -422,8 +422,6 @@ lbValue lb_dynamic_array_elem(lbProcedure *p, lbValue da); lbValue lb_dynamic_array_len(lbProcedure *p, lbValue da); lbValue lb_dynamic_array_cap(lbProcedure *p, lbValue da); lbValue lb_dynamic_array_allocator(lbProcedure *p, lbValue da); -lbValue lb_map_entries(lbProcedure *p, lbValue value); -lbValue lb_map_entries_ptr(lbProcedure *p, lbValue value); lbValue lb_map_len(lbProcedure *p, lbValue value); lbValue lb_map_cap(lbProcedure *p, lbValue value); lbValue lb_soa_struct_len(lbProcedure *p, lbValue value); diff --git a/src/llvm_backend_stmt.cpp b/src/llvm_backend_stmt.cpp index bd622d411..55b0c4d90 100644 --- a/src/llvm_backend_stmt.cpp +++ b/src/llvm_backend_stmt.cpp @@ -354,16 +354,6 @@ void lb_build_range_indexed(lbProcedure *p, lbValue expr, Type *val_type, lbValu } break; } - case Type_Map: { - lbValue entries = lb_map_entries_ptr(p, expr); - lbValue elem = lb_emit_struct_ep(p, entries, 0); - elem = lb_emit_load(p, elem); - lbValue entry = lb_emit_ptr_offset(p, elem, idx); - idx = lb_emit_load(p, lb_emit_struct_ep(p, entry, 2)); - val = lb_emit_load(p, lb_emit_struct_ep(p, entry, 3)); - - break; - } case Type_Struct: { GB_ASSERT(is_type_soa_struct(expr_type)); break; @@ -380,6 +370,99 @@ void lb_build_range_indexed(lbProcedure *p, lbValue expr, Type *val_type, lbValu if (done_) *done_ = done; } +lbValue lb_map_cell_index_static(lbProcedure *p, Type *type, lbValue cells_ptr, lbValue index) { + i64 size, N; + i64 sz = type_size_of(type); + map_cell_size_and_len(type, &size, &N); + + index = lb_emit_conv(p, index, t_uint); + + if (size == N*sz) { + lbValue elems_ptr = lb_emit_conv(p, cells_ptr, alloc_type_pointer(type)); + return lb_emit_ptr_offset(p, elems_ptr, index); + } + + // TOOD(bill): N power of two optimization to use >> and & + + lbValue N_const = lb_const_int(p->module, index.type, N); + lbValue cell_index = lb_emit_arith(p, Token_Quo, index, N_const, index.type); + lbValue data_index = lb_emit_arith(p, Token_Mod, index, N_const, index.type); + lbValue cell = lb_emit_ptr_offset(p, cells_ptr, cell_index); + lbValue elems_ptr = lb_emit_conv(p, cell, alloc_type_pointer(type)); + return lb_emit_ptr_offset(p, elems_ptr, data_index); +} + +void lb_map_kvh_data_static(lbProcedure *p, lbValue map_value, lbValue *ks_, lbValue *vs_, lbValue *hs_) { + lbValue capacity = lb_map_cap(p, map_value); + lbValue ks = lb_map_data_uintptr(p, map_value); + lbValue vs = {}; + lbValue hs = {}; + if (ks_) *ks_ = ks; + if (vs_) *vs_ = vs; + if (hs_) *hs_ = hs; +} + +void lb_build_range_map(lbProcedure *p, lbValue expr, Type *val_type, + lbValue *val_, lbValue *key_, lbBlock **loop_, lbBlock **done_) { + lbModule *m = p->module; + + Type *type = base_type(type_deref(expr.type)); + GB_ASSERT(type->kind == Type_Map); + + lbValue idx = {}; + lbBlock *loop = nullptr; + lbBlock *done = nullptr; + lbBlock *body = nullptr; + lbBlock *hash_check = nullptr; + + + lbAddr index = lb_add_local_generated(p, t_int, false); + lb_addr_store(p, index, lb_const_int(m, t_int, cast(u64)-1)); + + loop = lb_create_block(p, "for.index.loop"); + lb_emit_jump(p, loop); + lb_start_block(p, loop); + + lbValue incr = lb_emit_arith(p, Token_Add, lb_addr_load(p, index), lb_const_int(m, t_int, 1), t_int); + lb_addr_store(p, index, incr); + + hash_check = lb_create_block(p, "for.index.hash_check"); + body = lb_create_block(p, "for.index.body"); + done = lb_create_block(p, "for.index.done"); + + lbValue map_value = lb_emit_load(p, expr); + lbValue capacity = lb_map_cap(p, map_value); + lbValue cond = lb_emit_comp(p, Token_Lt, incr, capacity); + lb_emit_if(p, cond, hash_check, done); + lb_start_block(p, hash_check); + + idx = lb_addr_load(p, index); + + lbValue ks = lb_map_data_uintptr(p, map_value); + lbValue vs = lb_map_cell_index_static(p, type->Map.key, ks, capacity); + lbValue hs = lb_map_cell_index_static(p, type->Map.value, vs, capacity); + + lbValue hash = lb_emit_load(p, lb_emit_ptr_offset(p, hs, idx)); + + lbValue hash_cond = lb_emit_comp(p, Token_CmpEq, hash, lb_const_int(m, t_uintptr, 0)); + lb_emit_if(p, hash_cond, body, loop); + lb_start_block(p, body); + + // lbValue entries = lb_map_entries_ptr(p, expr); + // lbValue elem = lb_emit_struct_ep(p, entries, 0); + // elem = lb_emit_load(p, elem); + // lbValue entry = lb_emit_ptr_offset(p, elem, idx); + lbValue key = lb_const_nil(m, type->Map.key); + lbValue val = lb_const_nil(m, type->Map.value); + + + if (val_) *val_ = val; + if (key_) *key_ = key; + if (loop_) *loop_ = loop; + if (done_) *done_ = done; +} + + void lb_build_range_string(lbProcedure *p, lbValue expr, Type *val_type, lbValue *val_, lbValue *idx_, lbBlock **loop_, lbBlock **done_) { @@ -749,9 +832,7 @@ void lb_build_range_stmt(lbProcedure *p, AstRangeStmt *rs, Scope *scope) { if (is_type_pointer(type_deref(map.type))) { map = lb_emit_load(p, map); } - lbValue entries_ptr = lb_map_entries_ptr(p, map); - lbValue count_ptr = lb_emit_struct_ep(p, entries_ptr, 1); - lb_build_range_indexed(p, map, val1_type, count_ptr, &val, &key, &loop, &done); + lb_build_range_map(p, map, val1_type, &val, &key, &loop, &done); break; } case Type_Array: { diff --git a/src/llvm_backend_utility.cpp b/src/llvm_backend_utility.cpp index a54171b51..dce74126e 100644 --- a/src/llvm_backend_utility.cpp +++ b/src/llvm_backend_utility.cpp @@ -998,6 +998,7 @@ lbValue lb_emit_struct_ep(lbProcedure *p, lbValue s, i32 index) { switch (index) { case 0: result_type = get_struct_field_type(gst, 0); break; case 1: result_type = get_struct_field_type(gst, 1); break; + case 2: result_type = get_struct_field_type(gst, 2); break; } } else if (is_type_array(t)) { return lb_emit_array_epi(p, s, index); @@ -1134,6 +1135,7 @@ lbValue lb_emit_struct_ev(lbProcedure *p, lbValue s, i32 index) { switch (index) { case 0: result_type = get_struct_field_type(gst, 0); break; case 1: result_type = get_struct_field_type(gst, 1); break; + case 2: result_type = get_struct_field_type(gst, 2); break; } } break; @@ -1439,34 +1441,34 @@ lbValue lb_dynamic_array_allocator(lbProcedure *p, lbValue da) { return lb_emit_struct_ev(p, da, 3); } -lbValue lb_map_entries(lbProcedure *p, lbValue value) { - Type *t = base_type(value.type); - GB_ASSERT_MSG(t->kind == Type_Map, "%s", type_to_string(t)); - init_map_internal_types(t); - i32 index = 1; - lbValue entries = lb_emit_struct_ev(p, value, index); - return entries; +lbValue lb_map_len(lbProcedure *p, lbValue value) { + GB_ASSERT(is_type_map(value.type)); + lbValue len = lb_emit_struct_ev(p, value, 1); + return lb_emit_conv(p, len, t_int); } -lbValue lb_map_entries_ptr(lbProcedure *p, lbValue value) { - Type *t = base_type(type_deref(value.type)); - GB_ASSERT_MSG(t->kind == Type_Map, "%s", type_to_string(t)); - init_map_internal_types(t); - i32 index = 1; - lbValue entries = lb_emit_struct_ep(p, value, index); - return entries; -} +lbValue lb_map_cap(lbProcedure *p, lbValue value) { + GB_ASSERT(is_type_map(value.type)); + lbValue zero = lb_const_int(p->module, t_uintptr, 0); + lbValue one = lb_const_int(p->module, t_uintptr, 1); -lbValue lb_map_len(lbProcedure *p, lbValue value) { - lbValue entries = lb_map_entries(p, value); - return lb_dynamic_array_len(p, entries); + lbValue mask = lb_const_int(p->module, t_uintptr, MAP_CACHE_LINE_SIZE-1); + + lbValue data = lb_emit_struct_ev(p, value, 0); + lbValue log2_cap = lb_emit_arith(p, Token_And, data, mask, t_uintptr); + lbValue cap = lb_emit_arith(p, Token_Shl, one, log2_cap, t_uintptr); + lbValue cmp = lb_emit_comp(p, Token_CmpEq, data, zero); + return lb_emit_conv(p, lb_emit_select(p, cmp, zero, cap), t_int); } -lbValue lb_map_cap(lbProcedure *p, lbValue value) { - lbValue entries = lb_map_entries(p, value); - return lb_dynamic_array_cap(p, entries); +lbValue lb_map_data_uintptr(lbProcedure *p, lbValue value) { + GB_ASSERT(is_type_map(value.type)); + lbValue data = lb_emit_struct_ev(p, value, 0); + lbValue mask = lb_const_int(p->module, t_uintptr, MAP_CACHE_LINE_SIZE-1); + return lb_emit_arith(p, Token_And, data, mask, t_uintptr); } + lbValue lb_soa_struct_len(lbProcedure *p, lbValue value) { Type *t = base_type(value.type); bool is_ptr = false; -- cgit v1.2.3 From 810a1eee41cc8e047759c8934af70d6e68113082 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 8 Nov 2022 11:13:46 +0000 Subject: Remove the need for `type->Map.internal_type` and replace with the definition of `runtime.Raw_Map` --- src/check_expr.cpp | 1 - src/check_type.cpp | 24 ++---------------------- src/checker.cpp | 11 +++++++---- src/llvm_backend_debug.cpp | 3 ++- src/llvm_backend_general.cpp | 20 ++------------------ src/llvm_backend_utility.cpp | 17 +++++++---------- src/types.cpp | 2 +- 7 files changed, 21 insertions(+), 57 deletions(-) (limited to 'src/check_type.cpp') diff --git a/src/check_expr.cpp b/src/check_expr.cpp index 043b98173..c2753e979 100644 --- a/src/check_expr.cpp +++ b/src/check_expr.cpp @@ -1364,7 +1364,6 @@ bool is_polymorphic_type_assignable(CheckerContext *c, Type *poly, Type *source, bool key = is_polymorphic_type_assignable(c, poly->Map.key, source->Map.key, true, modify_type); bool value = is_polymorphic_type_assignable(c, poly->Map.value, source->Map.value, true, modify_type); if (key || value) { - poly->Map.internal_type = nullptr; poly->Map.lookup_result_type = nullptr; init_map_internal_types(poly); return true; diff --git a/src/check_type.cpp b/src/check_type.cpp index 39344fb2c..5d7f8d7b5 100644 --- a/src/check_type.cpp +++ b/src/check_type.cpp @@ -2198,34 +2198,14 @@ void map_cell_size_and_len(Type *type, i64 *size_, i64 *len_) { void init_map_internal_types(Type *type) { GB_ASSERT(type->kind == Type_Map); GB_ASSERT(t_allocator != nullptr); - if (type->Map.internal_type != nullptr) return; + if (type->Map.lookup_result_type != nullptr) return; Type *key = type->Map.key; Type *value = type->Map.value; GB_ASSERT(key != nullptr); GB_ASSERT(value != nullptr); - Type *generated_struct_type = alloc_type_struct(); - - /* - struct { - data: uintptr, - size: uintptr, - allocator: runtime.Allocator, - } - */ - Scope *s = create_scope(nullptr, builtin_pkg->scope); - - auto fields = slice_make(permanent_allocator(), 3); - fields[0] = alloc_entity_field(s, make_token_ident(str_lit("data")), t_uintptr, false, 0, EntityState_Resolved); - fields[1] = alloc_entity_field(s, make_token_ident(str_lit("size")), t_uintptr, false, 1, EntityState_Resolved); - fields[2] = alloc_entity_field(s, make_token_ident(str_lit("allocator")), t_allocator, false, 2, EntityState_Resolved); - - generated_struct_type->Struct.fields = fields; - type_set_offsets(generated_struct_type); - - type->Map.internal_type = generated_struct_type; - type->Map.lookup_result_type = make_optional_ok_type(value); + type->Map.lookup_result_type = make_optional_ok_type(value); } void add_map_key_type_dependencies(CheckerContext *ctx, Type *key) { diff --git a/src/checker.cpp b/src/checker.cpp index d5d2c6026..fa3ef245b 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -1933,7 +1933,8 @@ void add_type_info_type_internal(CheckerContext *c, Type *t) { init_map_internal_types(bt); add_type_info_type_internal(c, bt->Map.key); add_type_info_type_internal(c, bt->Map.value); - add_type_info_type_internal(c, bt->Map.internal_type); + add_type_info_type_internal(c, t_uintptr); // hash value + add_type_info_type_internal(c, t_allocator); break; case Type_Tuple: @@ -2155,7 +2156,8 @@ void add_min_dep_type_info(Checker *c, Type *t) { init_map_internal_types(bt); add_min_dep_type_info(c, bt->Map.key); add_min_dep_type_info(c, bt->Map.value); - add_min_dep_type_info(c, bt->Map.internal_type); + add_min_dep_type_info(c, t_uintptr); // hash value + add_min_dep_type_info(c, t_allocator); break; case Type_Tuple: @@ -2845,9 +2847,10 @@ void init_core_map_type(Checker *c) { if (t_map_info != nullptr) { return; } - t_map_info = find_core_type(c, str_lit("Map_Info")); - t_map_cell_info = find_core_type(c, str_lit("Map_Cell_Info")); init_mem_allocator(c); + t_map_info = find_core_type(c, str_lit("Map_Info")); + t_map_cell_info = find_core_type(c, str_lit("Map_Cell_Info")); + t_raw_map = find_core_type(c, str_lit("Raw_Map")); } void init_preload(Checker *c) { diff --git a/src/llvm_backend_debug.cpp b/src/llvm_backend_debug.cpp index 8a98b7f39..e69424929 100644 --- a/src/llvm_backend_debug.cpp +++ b/src/llvm_backend_debug.cpp @@ -671,7 +671,8 @@ void lb_debug_complete_types(lbModule *m) { break; case Type_Map: - bt = bt->Map.internal_type; + GB_ASSERT(t_raw_map != nullptr); + bt = base_type(t_raw_map); /*fallthrough*/ case Type_Struct: if (file == nullptr) { diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp index 69b1fce20..ffc7a1496 100644 --- a/src/llvm_backend_general.cpp +++ b/src/llvm_backend_general.cpp @@ -1931,24 +1931,8 @@ LLVMTypeRef lb_type_internal(lbModule *m, Type *type) { case Type_Map: init_map_internal_types(type); - { - Type *internal_type = type->Map.internal_type; - GB_ASSERT(internal_type->kind == Type_Struct); - - m->internal_type_level -= 1; - defer (m->internal_type_level += 1); - - unsigned field_count = cast(unsigned)(internal_type->Struct.fields.count); - GB_ASSERT(field_count == 3); - - LLVMTypeRef fields[3] = { - lb_type(m, t_uintptr), // data - lb_type(m, t_uintptr), // len - lb_type(m, t_allocator), // allocator - }; - - return LLVMStructTypeInContext(ctx, fields, field_count, false); - } + GB_ASSERT(t_raw_map != nullptr); + return lb_type_internal(m, t_raw_map); case Type_Struct: { diff --git a/src/llvm_backend_utility.cpp b/src/llvm_backend_utility.cpp index cbe690155..f4d17c7a2 100644 --- a/src/llvm_backend_utility.cpp +++ b/src/llvm_backend_utility.cpp @@ -990,15 +990,13 @@ lbValue lb_emit_struct_ep(lbProcedure *p, lbValue s, i32 index) { } } else if (is_type_map(t)) { init_map_internal_types(t); - Type *itp = alloc_type_pointer(t->Map.internal_type); + Type *itp = alloc_type_pointer(t_raw_map); s = lb_emit_transmute(p, s, itp); - Type *gst = t->Map.internal_type; - GB_ASSERT(gst->kind == Type_Struct); switch (index) { - case 0: result_type = get_struct_field_type(gst, 0); break; - case 1: result_type = get_struct_field_type(gst, 1); break; - case 2: result_type = get_struct_field_type(gst, 2); break; + case 0: result_type = get_struct_field_type(t_raw_map, 0); break; + case 1: result_type = get_struct_field_type(t_raw_map, 1); break; + case 2: result_type = get_struct_field_type(t_raw_map, 2); break; } } else if (is_type_array(t)) { return lb_emit_array_epi(p, s, index); @@ -1131,11 +1129,10 @@ lbValue lb_emit_struct_ev(lbProcedure *p, lbValue s, i32 index) { case Type_Map: { init_map_internal_types(t); - Type *gst = t->Map.internal_type; switch (index) { - case 0: result_type = get_struct_field_type(gst, 0); break; - case 1: result_type = get_struct_field_type(gst, 1); break; - case 2: result_type = get_struct_field_type(gst, 2); break; + case 0: result_type = get_struct_field_type(t_raw_map, 0); break; + case 1: result_type = get_struct_field_type(t_raw_map, 1); break; + case 2: result_type = get_struct_field_type(t_raw_map, 2); break; } } break; diff --git a/src/types.cpp b/src/types.cpp index 220d1a6ab..9b2fd30d4 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -226,7 +226,6 @@ struct TypeProc { TYPE_KIND(Map, struct { \ Type *key; \ Type *value; \ - Type *internal_type; \ Type *lookup_result_type; \ }) \ TYPE_KIND(Struct, TypeStruct) \ @@ -686,6 +685,7 @@ gb_global Type *t_source_code_location_ptr = nullptr; gb_global Type *t_map_info = nullptr; gb_global Type *t_map_cell_info = nullptr; +gb_global Type *t_raw_map = nullptr; gb_global Type *t_equal_proc = nullptr; -- cgit v1.2.3 From 3edb3d8d8c16a24371bb401fe0d69ec93e667b27 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Sun, 13 Nov 2022 23:24:08 +0000 Subject: Simplify the handling of the hashing calls for `map`s --- core/runtime/dynamic_map_internal.odin | 98 +++++++++------------------------- src/check_type.cpp | 20 +++---- src/llvm_backend.cpp | 14 +---- 3 files changed, 31 insertions(+), 101 deletions(-) (limited to 'src/check_type.cpp') diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index e943a3e24..ac09c3e2b 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -732,92 +732,42 @@ __dynamic_map_reserve :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Ma +// NOTE: the default hashing algorithm derives from fnv64a, with some minor modifications to work for `map` type: +// +// * Convert a `0` result to `1` +// * "empty entry" +// * Prevent the top bit from being set +// * "deleted entry" +// +// Both of these modification are necessary for the implementation of the `map` INITIAL_HASH_SEED :: 0xcbf29ce484222325 HASH_MASK :: 1 << (8*size_of(uintptr) - 1) -1 -_fnv64a :: proc "contextless" (data: []byte, seed: u64 = INITIAL_HASH_SEED) -> u64 { - h: u64 = seed - for b in data { - h = (h ~ u64(b)) * 0x100000001b3 - } - h &= HASH_MASK - return h | u64(h == 0) -} - -default_hash :: #force_inline proc "contextless" (data: []byte) -> uintptr { - return uintptr(_fnv64a(data)) -} -default_hash_string :: #force_inline proc "contextless" (s: string) -> uintptr { - return default_hash(transmute([]byte)(s)) -} -default_hash_ptr :: #force_inline proc "contextless" (data: rawptr, size: int) -> uintptr { - s := Raw_Slice{data, size} - return default_hash(transmute([]byte)(s)) -} - -@(private) -_default_hasher_const :: #force_inline proc "contextless" (data: rawptr, seed: uintptr, $N: uint) -> uintptr where N <= 16 { - h := u64(seed) + 0xcbf29ce484222325 - p := uintptr(data) - #unroll for _ in 0.. uintptr { - h := u64(seed) + 0xcbf29ce484222325 - p := uintptr(data) +default_hasher :: #force_inline proc "contextless" (data: rawptr, seed: uintptr, N: int) -> uintptr { + h := u64(seed) + INITIAL_HASH_SEED + p := ([^]byte)(data) for _ in 0.. uintptr { return #force_inline _default_hasher_const(data, seed, 1) } -default_hasher2 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 2) } -default_hasher3 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 3) } -default_hasher4 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 4) } -default_hasher5 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 5) } -default_hasher6 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 6) } -default_hasher7 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 7) } -default_hasher8 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 8) } -default_hasher9 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 9) } -default_hasher10 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 10) } -default_hasher11 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 11) } -default_hasher12 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 12) } -default_hasher13 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 13) } -default_hasher14 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 14) } -default_hasher15 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 15) } -default_hasher16 :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { return #force_inline _default_hasher_const(data, seed, 16) } + return uintptr(h) | uintptr(uintptr(h) == 0) +} default_hasher_string :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { - h := u64(seed) + 0xcbf29ce484222325 - str := (^[]byte)(data)^ - for b in str { - h = (h ~ u64(b)) * 0x100000001b3 - } - h &= HASH_MASK - return uintptr(h) | uintptr(h == 0) + str := (^[]byte)(data) + return default_hasher(raw_data(str^), seed, len(str)) } default_hasher_cstring :: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr { - h := u64(seed) + 0xcbf29ce484222325 - ptr := (^uintptr)(data)^ - for (^byte)(ptr)^ != 0 { - b := (^byte)(ptr)^ - h = (h ~ u64(b)) * 0x100000001b3 - ptr += 1 + h := u64(seed) + INITIAL_HASH_SEED + if ptr := (^[^]byte)(data)^; ptr != nil { + for ptr[0] != 0 { + h = (h ~ u64(ptr[0])) * 0x100000001b3 + ptr = ptr[1:] + } } h &= HASH_MASK - return uintptr(h) | uintptr(h == 0) + return uintptr(h) | uintptr(uintptr(h) == 0) } diff --git a/src/check_type.cpp b/src/check_type.cpp index 5d7f8d7b5..4d94fce6c 100644 --- a/src/check_type.cpp +++ b/src/check_type.cpp @@ -2221,35 +2221,27 @@ void add_map_key_type_dependencies(CheckerContext *ctx, Type *key) { } if (is_type_simple_compare(key)) { - i64 sz = type_size_of(key); - if (1 <= sz && sz <= 16) { - char buf[20] = {}; - gb_snprintf(buf, 20, "default_hasher%d", cast(i32)sz); - add_package_dependency(ctx, "runtime", buf); - return; - } else { - add_package_dependency(ctx, "runtime", "default_hasher_n"); - return; - } + add_package_dependency(ctx, "runtime", "default_hasher"); + return; } if (key->kind == Type_Struct) { - add_package_dependency(ctx, "runtime", "default_hasher_n"); + add_package_dependency(ctx, "runtime", "default_hasher"); for_array(i, key->Struct.fields) { Entity *field = key->Struct.fields[i]; add_map_key_type_dependencies(ctx, field->type); } } else if (key->kind == Type_Union) { - add_package_dependency(ctx, "runtime", "default_hasher_n"); + add_package_dependency(ctx, "runtime", "default_hasher"); for_array(i, key->Union.variants) { Type *v = key->Union.variants[i]; add_map_key_type_dependencies(ctx, v); } } else if (key->kind == Type_EnumeratedArray) { - add_package_dependency(ctx, "runtime", "default_hasher_n"); + add_package_dependency(ctx, "runtime", "default_hasher"); add_map_key_type_dependencies(ctx, key->EnumeratedArray.elem); } else if (key->kind == Type_Array) { - add_package_dependency(ctx, "runtime", "default_hasher_n"); + add_package_dependency(ctx, "runtime", "default_hasher"); add_map_key_type_dependencies(ctx, key->Array.elem); } } diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 5b9db7f2b..2ee292880 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -282,23 +282,11 @@ lbValue lb_equal_proc_for_type(lbModule *m, Type *type) { lbValue lb_simple_compare_hash(lbProcedure *p, Type *type, lbValue data, lbValue seed) { GB_ASSERT_MSG(is_type_simple_compare(type), "%s", type_to_string(type)); - i64 sz = type_size_of(type); - - if (1 <= sz && sz <= 16) { - char name[32] = {}; - gb_snprintf(name, 32, "default_hasher%d", cast(i32)sz); - - auto args = array_make(permanent_allocator(), 2); - args[0] = data; - args[1] = seed; - return lb_emit_runtime_call(p, name, args); - } - auto args = array_make(permanent_allocator(), 3); args[0] = data; args[1] = seed; args[2] = lb_const_int(p->module, t_int, type_size_of(type)); - return lb_emit_runtime_call(p, "default_hasher_n", args); + return lb_emit_runtime_call(p, "default_hasher", args); } void lb_add_callsite_force_inline(lbProcedure *p, lbValue ret_value) { -- cgit v1.2.3