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/llvm_backend.cpp | 110 +++++++++++++++++++++++++++++---------------------- 1 file changed, 63 insertions(+), 47 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 1d2c00700..40b861d40 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -298,7 +298,7 @@ lbValue lb_simple_compare_hash(lbProcedure *p, Type *type, lbValue data, lbValue lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { type = core_type(type); - GB_ASSERT(is_type_valid_for_keys(type)); + GB_ASSERT_MSG(is_type_valid_for_keys(type), "%s", type_to_string(type)); Type *pt = alloc_type_pointer(type); @@ -500,51 +500,67 @@ lbValue lb_generate_anonymous_proc_lit(lbModule *m, String const &prefix_name, A return value; } -lbValue lb_gen_map_header_table_internal(lbProcedure *p, Type *map_type) { +// 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); + + LLVMValueRef const_values[4] = {}; + const_values[0] = lb_const_int(m, t_uintptr, type_size_of(type)).value; + const_values[1] = lb_const_int(m, t_uintptr, type_align_of(type)).value; + const_values[2] = lb_const_int(m, t_uintptr, size).value; + const_values[3] = lb_const_int(m, t_uintptr, len).value; + return llvm_const_named_struct(m, t_map_cell_info, const_values, gb_count_of(const_values)); + +} +lbValue lb_gen_map_info_ptr(lbProcedure *p, Type *map_type) { lbModule *m = p->module; map_type = base_type(map_type); GB_ASSERT(map_type->kind == Type_Map); - lbAddr *found = map_get(&m->map_header_table_map, map_type); + lbAddr *found = map_get(&m->map_info_map, map_type); if (found) { - return lb_addr_load(p, *found); + return lb_addr_get_ptr(p, *found); } - GB_ASSERT(map_type->Map.entry_type->kind == Type_Struct); - i64 entry_size = type_size_of (map_type->Map.entry_type); - i64 entry_align = type_align_of (map_type->Map.entry_type); - - i64 key_offset = type_offset_of(map_type->Map.entry_type, 2); - i64 key_size = type_size_of (map_type->Map.key); + GB_ASSERT(t_map_info != nullptr); + GB_ASSERT(t_map_cell_info != nullptr); - i64 value_offset = type_offset_of(map_type->Map.entry_type, 3); - i64 value_size = type_size_of (map_type->Map.value); + LLVMValueRef key_cell_info = lb_gen_map_cell_info(m, map_type->Map.key); + LLVMValueRef value_cell_info = lb_gen_map_cell_info(m, map_type->Map.value); - Type *key_type = map_type->Map.key; - Type *val_type = map_type->Map.value; - gb_unused(val_type); + LLVMValueRef const_values[4] = {}; + const_values[0] = key_cell_info; + const_values[1] = value_cell_info; + const_values[2] = lb_get_hasher_proc_for_type(m, map_type->Map.key).value; + const_values[3] = lb_get_equal_proc_for_type(m, map_type->Map.key).value; - Type *st = base_type(t_map_header_table); - GB_ASSERT(st->Struct.fields.count == 7); + LLVMValueRef llvm_res = llvm_const_named_struct(m, t_map_info, const_values, gb_count_of(const_values)); + lbValue res = {llvm_res, t_map_info}; - LLVMValueRef const_values[7] = {}; - const_values[0] = lb_get_equal_proc_for_type(m, key_type) .value; - const_values[1] = lb_const_int(m, t_int, entry_size) .value; - const_values[2] = lb_const_int(m, t_int, entry_align) .value; - const_values[3] = lb_const_int(m, t_uintptr, key_offset) .value; - const_values[4] = lb_const_int(m, t_int, key_size) .value; - const_values[5] = lb_const_int(m, t_uintptr, value_offset).value; - const_values[6] = lb_const_int(m, t_int, value_size) .value; - - LLVMValueRef llvm_res = llvm_const_named_struct(m, t_map_header_table, const_values, gb_count_of(const_values)); - lbValue res = {llvm_res, t_map_header_table}; - - lbAddr addr = lb_add_global_generated(m, t_map_header_table, res, nullptr); + lbAddr addr = lb_add_global_generated(m, t_map_info, res, nullptr); lb_make_global_private_const(addr); - map_set(&m->map_header_table_map, map_type, addr); - return lb_addr_load(p, addr); + map_set(&m->map_info_map, map_type, addr); + return lb_addr_get_ptr(p, addr); } lbValue lb_const_hash(lbModule *m, lbValue key, Type *key_type) { @@ -616,12 +632,13 @@ lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key) { Type *map_type = base_type(type_deref(map_ptr.type)); - lbValue key_ptr = {}; - auto args = array_make(permanent_allocator(), 4); + lbValue key_ptr = lb_address_from_load_or_generate_local(p, key); + key_ptr = lb_emit_conv(p, key_ptr, t_rawptr); + + auto args = array_make(permanent_allocator(), 3); args[0] = lb_emit_conv(p, map_ptr, t_rawptr); - args[1] = lb_gen_map_header_table_internal(p, map_type); - args[2] = lb_gen_map_key_hash(p, key, map_type->Map.key, &key_ptr); - args[3] = key_ptr; + args[1] = lb_gen_map_info_ptr(p, map_type); + args[2] = key_ptr; lbValue ptr = lb_emit_runtime_call(p, "__dynamic_map_get", args); @@ -633,20 +650,19 @@ void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, map_type = base_type(map_type); GB_ASSERT(map_type->kind == Type_Map); - lbValue key_ptr = {}; - lbValue key_hash = lb_gen_map_key_hash(p, map_key, map_type->Map.key, &key_ptr); + lbValue key_ptr = lb_address_from_load_or_generate_local(p, map_key); + key_ptr = lb_emit_conv(p, key_ptr, t_rawptr); lbValue v = lb_emit_conv(p, map_value, map_type->Map.value); lbAddr value_addr = lb_add_local_generated(p, v.type, false); lb_addr_store(p, value_addr, v); - auto args = array_make(permanent_allocator(), 6); + auto args = array_make(permanent_allocator(), 5); args[0] = lb_emit_conv(p, map_ptr, t_rawptr); - args[1] = lb_gen_map_header_table_internal(p, map_type); - args[2] = key_hash; - args[3] = key_ptr; - args[4] = lb_emit_conv(p, value_addr.addr, t_rawptr); - args[5] = lb_emit_source_code_location_as_global(p, node); + args[1] = lb_gen_map_info_ptr(p, map_type); + args[2] = key_ptr; + args[3] = lb_emit_conv(p, value_addr.addr, t_rawptr); + args[4] = lb_emit_source_code_location_as_global(p, node); lb_emit_runtime_call(p, "__dynamic_map_set", args); } @@ -660,8 +676,8 @@ void lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const auto args = array_make(permanent_allocator(), 4); args[0] = lb_emit_conv(p, map_ptr, t_rawptr); - args[1] = lb_gen_map_header_table_internal(p, type_deref(map_ptr.type)); - args[2] = lb_const_int(p->module, t_int, capacity); + args[1] = lb_gen_map_info_ptr(p, type_deref(map_ptr.type)); + args[2] = lb_const_int(p->module, t_uint, capacity); args[3] = lb_emit_source_code_location_as_global(p, proc_name, pos); lb_emit_runtime_call(p, "__dynamic_map_reserve", args); } -- cgit v1.2.3 From bce62b98d4608d627b3a98b4d969fc7a7e5fd9c7 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Mon, 7 Nov 2022 23:32:59 +0000 Subject: Basic fmt printing for `map` --- core/fmt/fmt.odin | 44 +++++++++++----------------------- core/runtime/core.odin | 8 +++---- core/runtime/dynamic_map_internal.odin | 13 +++++----- src/llvm_backend.cpp | 14 +++++------ src/llvm_backend.hpp | 1 + src/llvm_backend_type.cpp | 8 ++----- 6 files changed, 32 insertions(+), 56 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/core/fmt/fmt.odin b/core/fmt/fmt.odin index ce79aab9f..dbccab67b 100644 --- a/core/fmt/fmt.odin +++ b/core/fmt/fmt.odin @@ -2069,45 +2069,29 @@ fmt_value :: proc(fi: ^Info, v: any, verb: rune) { m := (^mem.Raw_Map)(v.data) if m != nil { - if info.generated_struct == nil { + if info.map_info == nil { return } - /* - entries := &m.entries - gs := runtime.type_info_base(info.generated_struct).variant.(runtime.Type_Info_Struct) - ed := runtime.type_info_base(gs.types[1]).variant.(runtime.Type_Info_Dynamic_Array) - entry_type := ed.elem.variant.(runtime.Type_Info_Struct) - entry_size := ed.elem_size - /* - NOTE: The layout of a `map` is as follows: - - map[Key]Value - - ## Internal Layout - struct { - hashes: []int, - entries: [dynamic]struct{ - hash: uintptr, - next: int, - key: Key, - value: Value, - }, + map_cap := uintptr(runtime.map_cap(m^)) + ks, vs, hs, _, _ := runtime.map_kvh_data_dynamic(m^, info.map_info) + j := 0 + for bucket_index in 0.. 0 { io.write_string(fi.writer, ", ", &fi.n) } - data := uintptr(entries.data) + uintptr(i*entry_size) + if j > 0 { + io.write_string(fi.writer, ", ", &fi.n) + } + j += 1 - key := data + entry_type.offsets[2] // key: Key - fmt_arg(&Info{writer = fi.writer}, any{rawptr(key), info.key.id}, 'v') + key := ks + bucket_index*uintptr(info.key.size) + value := vs + bucket_index*uintptr(info.value.size) + fmt_arg(&Info{writer = fi.writer}, any{rawptr(key), info.key.id}, 'v') io.write_string(fi.writer, "=", &fi.n) - - value := data + entry_type.offsets[3] // value: Value fmt_arg(fi, any{rawptr(value), info.value.id}, 'v') } - */ } case runtime.Type_Info_Struct: diff --git a/core/runtime/core.odin b/core/runtime/core.odin index ce3aa239b..69e5128a9 100644 --- a/core/runtime/core.odin +++ b/core/runtime/core.odin @@ -143,11 +143,9 @@ Type_Info_Enum :: struct { values: []Type_Info_Enum_Value, } Type_Info_Map :: struct { - key: ^Type_Info, - value: ^Type_Info, - generated_struct: ^Type_Info, - key_equal: Equal_Proc, - key_hasher: Hasher_Proc, + key: ^Type_Info, + value: ^Type_Info, + map_info: ^Map_Info, } Type_Info_Bit_Set :: struct { elem: ^Type_Info, diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index 3fd86f38e..5e1c67e1c 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -242,8 +242,8 @@ map_probe_distance :: #force_inline proc "contextless" (m: Raw_Map, hash: Map_Ha Map_Info :: struct { ks: Map_Cell_Info, // 32-bytes on 64-bit, 16-bytes on 32-bit vs: Map_Cell_Info, // 32-bytes on 64-bit, 16-bytes on 32-bit - hash: proc "contextless" (key: rawptr, seed: Map_Hash) -> Map_Hash, // 8-bytes on 64-bit, 4-bytes on 32-bit - cmp: proc "contextless" (lhs, rhs: rawptr) -> bool, // 8-bytes on 64-bit, 4-bytes on 32-bit + key_hasher: proc "contextless" (key: rawptr, seed: Map_Hash) -> Map_Hash, // 8-bytes on 64-bit, 4-bytes on 32-bit + key_equal: proc "contextless" (lhs, rhs: rawptr) -> bool, // 8-bytes on 64-bit, 4-bytes on 32-bit } @@ -669,7 +669,7 @@ map_lookup_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, if map_len(m) == 0 { return 0, false } - h := info.hash(rawptr(k), 0) + h := info.key_hasher(rawptr(k), 0) p := map_desired_position(m, h) d := uintptr(0) c := (uintptr(1) << map_log2_cap(m)) - 1 @@ -681,7 +681,7 @@ map_lookup_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, return 0, false } else if d > map_probe_distance(m, element_hash, p) { return 0, false - } else if element_hash == h && info.cmp(rawptr(k), rawptr(map_cell_index_dynamic(ks, info_ks, p))) { + } else if element_hash == h && info.key_equal(rawptr(k), rawptr(map_cell_index_dynamic(ks, info_ks, p))) { return p, true } p = (p + 1) & c @@ -698,7 +698,7 @@ map_insert_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, k, if map_len(m^) + 1 >= map_resize_threshold(m^) { map_grow_dynamic(m, info) or_return } - hashed := info.hash(rawptr(k), 0) + hashed := info.key_hasher(rawptr(k), 0) value = map_insert_hash_dynamic(m^, info, hashed, k, v) m.len += 1 return @@ -710,7 +710,7 @@ map_add_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, k, v: if map_len(m^) + 1 >= map_resize_threshold(m^) { map_grow_dynamic(m, info) or_return } - map_add_hash_dynamic(m^, info, info.hash(rawptr(k), 0), k, v) + map_add_hash_dynamic(m^, info, info.key_hasher(rawptr(k), 0), k, v) m.len += 1 return nil } @@ -735,7 +735,6 @@ map_clear_dynamic :: #force_inline proc "contextless" (#no_alias m: ^Raw_Map, #n } -// TODO(bill): Change signature to not be a `rawptr` __dynamic_map_get :: proc "contextless" (m: rawptr, #no_alias info: ^Map_Info, key: rawptr) -> rawptr { rm := (^Raw_Map)(m)^ index, ok := map_lookup_dynamic(rm, info, uintptr(key)) diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 40b861d40..7c1e53b7f 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -530,15 +530,13 @@ LLVMValueRef lb_gen_map_cell_info(lbModule *m, Type *type) { return llvm_const_named_struct(m, t_map_cell_info, const_values, gb_count_of(const_values)); } -lbValue lb_gen_map_info_ptr(lbProcedure *p, Type *map_type) { - lbModule *m = p->module; - +lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type) { map_type = base_type(map_type); GB_ASSERT(map_type->kind == Type_Map); lbAddr *found = map_get(&m->map_info_map, map_type); if (found) { - return lb_addr_get_ptr(p, *found); + return found->addr; } GB_ASSERT(t_map_info != nullptr); @@ -560,7 +558,7 @@ lbValue lb_gen_map_info_ptr(lbProcedure *p, Type *map_type) { lb_make_global_private_const(addr); map_set(&m->map_info_map, map_type, addr); - return lb_addr_get_ptr(p, addr); + return addr.addr; } lbValue lb_const_hash(lbModule *m, lbValue key, Type *key_type) { @@ -637,7 +635,7 @@ lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, auto args = array_make(permanent_allocator(), 3); args[0] = lb_emit_conv(p, map_ptr, t_rawptr); - args[1] = lb_gen_map_info_ptr(p, map_type); + args[1] = lb_gen_map_info_ptr(p->module, map_type); args[2] = key_ptr; lbValue ptr = lb_emit_runtime_call(p, "__dynamic_map_get", args); @@ -659,7 +657,7 @@ void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, auto args = array_make(permanent_allocator(), 5); args[0] = lb_emit_conv(p, map_ptr, t_rawptr); - args[1] = lb_gen_map_info_ptr(p, map_type); + args[1] = lb_gen_map_info_ptr(p->module, map_type); args[2] = key_ptr; args[3] = lb_emit_conv(p, value_addr.addr, t_rawptr); args[4] = lb_emit_source_code_location_as_global(p, node); @@ -676,7 +674,7 @@ void lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const auto args = array_make(permanent_allocator(), 4); args[0] = lb_emit_conv(p, map_ptr, t_rawptr); - args[1] = lb_gen_map_info_ptr(p, type_deref(map_ptr.type)); + args[1] = lb_gen_map_info_ptr(p->module, type_deref(map_ptr.type)); args[2] = lb_const_int(p->module, t_uint, capacity); args[3] = lb_emit_source_code_location_as_global(p, proc_name, pos); lb_emit_runtime_call(p, "__dynamic_map_reserve", args); diff --git a/src/llvm_backend.hpp b/src/llvm_backend.hpp index b797f28f9..f4d4cce21 100644 --- a/src/llvm_backend.hpp +++ b/src/llvm_backend.hpp @@ -447,6 +447,7 @@ String lb_get_const_string(lbModule *m, lbValue value); lbValue lb_generate_local_array(lbProcedure *p, Type *elem_type, i64 count, bool zero_init=true); lbValue lb_generate_global_array(lbModule *m, Type *elem_type, i64 count, String prefix, i64 id); lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue *key_ptr_); +lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type); lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key); void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, Type *map_type, lbValue const &map_key, lbValue const &map_value, Ast *node); diff --git a/src/llvm_backend_type.cpp b/src/llvm_backend_type.cpp index 4abf674c5..26f89f985 100644 --- a/src/llvm_backend_type.cpp +++ b/src/llvm_backend_type.cpp @@ -788,15 +788,11 @@ void lb_setup_type_info_data(lbProcedure *p) { // NOTE(bill): Setup type_info da case Type_Map: { tag = lb_const_ptr_cast(m, variant_ptr, t_type_info_map_ptr); init_map_internal_types(t); - - lbValue gst = lb_type_info(m, t->Map.internal_type); - LLVMValueRef vals[5] = { + LLVMValueRef vals[3] = { lb_type_info(m, t->Map.key).value, lb_type_info(m, t->Map.value).value, - gst.value, - lb_get_equal_proc_for_type(m, t->Map.key).value, - lb_get_hasher_proc_for_type(m, t->Map.key).value + lb_gen_map_info_ptr(p->module, t).value }; lbValue res = {}; -- 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/llvm_backend.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 ed58374964889db91b38fe95db409111819790ca Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 8 Nov 2022 12:18:36 +0000 Subject: Make `Map_Info` store pointers to cell info rather than inline --- core/fmt/fmt.odin | 4 +- core/runtime/core_builtin.odin | 7 ++- core/runtime/dynamic_map_internal.odin | 85 +++++++++++++--------------------- src/check_builtin.cpp | 23 +++++++++ src/checker.cpp | 3 ++ src/checker_builtin_procs.hpp | 2 + src/llvm_backend.cpp | 14 +++++- src/llvm_backend.hpp | 3 +- src/llvm_backend_general.cpp | 1 + src/llvm_backend_proc.cpp | 3 ++ src/types.cpp | 2 + 11 files changed, 86 insertions(+), 61 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/core/fmt/fmt.odin b/core/fmt/fmt.odin index 76a1ee20f..9dd38eb29 100644 --- a/core/fmt/fmt.odin +++ b/core/fmt/fmt.odin @@ -2085,8 +2085,8 @@ fmt_value :: proc(fi: ^Info, v: any, verb: rune) { } j += 1 - key := runtime.map_cell_index_dynamic(ks, &info.map_info.ks, bucket_index) - value := runtime.map_cell_index_dynamic(vs, &info.map_info.vs, bucket_index) + key := runtime.map_cell_index_dynamic(ks, info.map_info.ks, bucket_index) + value := runtime.map_cell_index_dynamic(vs, info.map_info.vs, bucket_index) fmt_arg(&Info{writer = fi.writer}, any{rawptr(key), info.key.id}, 'v') io.write_string(fi.writer, "=", &fi.n) diff --git a/core/runtime/core_builtin.odin b/core/runtime/core_builtin.odin index 80a9f2944..5093fbbd7 100644 --- a/core/runtime/core_builtin.odin +++ b/core/runtime/core_builtin.odin @@ -272,13 +272,13 @@ clear_map :: proc "contextless" (m: ^$T/map[$K]$V) { if m == nil { return } - map_clear_dynamic((^Raw_Map)(m), map_info(K, V)) + map_clear_dynamic((^Raw_Map)(m), map_info(T)) } @builtin reserve_map :: proc(m: ^$T/map[$K]$V, capacity: int, loc := #caller_location) { if m != nil { - __dynamic_map_reserve((^Raw_Map)(m), map_info(K, V), uint(capacity), loc) + __dynamic_map_reserve((^Raw_Map)(m), map_info(T), uint(capacity), loc) } } @@ -306,8 +306,7 @@ shrink_map :: proc(m: ^$T/map[$K]$V, new_cap := -1, loc := #caller_location) -> delete_key :: proc(m: ^$T/map[$K]$V, key: K) -> (deleted_key: K, deleted_value: V) { if m != nil { key := key - info := map_info(K, V) - _ = map_erase_dynamic((^Raw_Map)(m), info, uintptr(&key)) + _ = map_erase_dynamic((^Raw_Map)(m), map_info(T), uintptr(&key)) // TODO(bill) old key and value } return diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index 6f6a17f11..79e1a4f30 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -184,13 +184,15 @@ map_hash_is_empty :: #force_inline proc "contextless" (hash: Map_Hash) -> bool { return hash == 0 } -map_hash_is_deleted :: #force_inline proc "contextless" (hash: Map_Hash) -> bool { +map_hash_is_deleted :: #force_no_inline proc "contextless" (hash: Map_Hash) -> bool { // The MSB indicates a tombstone - return (hash >> ((size_of(Map_Hash) * 8) - 1)) != 0 + N :: size_of(Map_Hash)*8 - 1 + return hash >> N != 0 } map_hash_is_valid :: #force_inline proc "contextless" (hash: Map_Hash) -> bool { // The MSB indicates a tombstone - return (hash != 0) & ((hash >> ((size_of(Map_Hash) * 8) - 1)) == 0) + N :: size_of(Map_Hash)*8 - 1 + return (hash != 0) & (hash >> N == 0) } @@ -212,42 +214,19 @@ map_probe_distance :: #force_inline proc "contextless" (m: Raw_Map, hash: Map_Ha // about the map to make working with it possible. This info structure stores // that. // -// The Odin compiler should generate this for __get_map_header. -// -// 80-bytes on 64-bit -// 40-bytes on 32-bit +// 32-bytes on 64-bit +// 16-bytes on 32-bit Map_Info :: struct { - ks: Map_Cell_Info, // 32-bytes on 64-bit, 16-bytes on 32-bit - vs: Map_Cell_Info, // 32-bytes on 64-bit, 16-bytes on 32-bit + ks: ^Map_Cell_Info, // 8-bytes on 64-bit, 4-bytes on 32-bit + vs: ^Map_Cell_Info, // 8-bytes on 64-bit, 4-bytes on 32-bit key_hasher: proc "contextless" (key: rawptr, seed: Map_Hash) -> Map_Hash, // 8-bytes on 64-bit, 4-bytes on 32-bit key_equal: proc "contextless" (lhs, rhs: rawptr) -> bool, // 8-bytes on 64-bit, 4-bytes on 32-bit } // The Map_Info structure is basically a pseudo-table of information for a given K and V pair. -map_info :: #force_inline proc "contextless" ($K: typeid, $V: typeid) -> ^Map_Info where intrinsics.type_is_comparable(K) { - @static INFO := Map_Info { - Map_Cell_Info { - size_of(K), - align_of(K), - size_of(Map_Cell(K)), - len(Map_Cell(K){}.data), - }, - Map_Cell_Info { - size_of(V), - align_of(V), - size_of(Map_Cell(V)), - len(Map_Cell(V){}.data), - }, - proc "contextless" (ptr: rawptr, seed: uintptr) -> Map_Hash { - return intrinsics.type_hasher_proc(K)(ptr, seed) - } , - proc "contextless" (a, b: rawptr) -> bool { - return intrinsics.type_equal_proc(K)(a, b) - }, - } - return &INFO -} +// map_info :: proc "contextless" ($T: typeid/map[$K]$V) -> ^Map_Info {...} +map_info :: intrinsics.type_map_info map_kvh_data_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info) -> (ks: uintptr, vs: uintptr, hs: [^]Map_Hash, sk: uintptr, sv: uintptr) { @static INFO_HS := Map_Cell_Info { @@ -259,12 +238,12 @@ map_kvh_data_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Inf capacity := uintptr(1) << map_log2_cap(m) ks = map_data(m) - vs = map_cell_index_dynamic(ks, &info.ks, capacity) // Skip past ks to get start of vs - hs_ := map_cell_index_dynamic(vs, &info.vs, capacity) // Skip past vs to get start of hs + vs = map_cell_index_dynamic(ks, info.ks, capacity) // Skip past ks to get start of vs + hs_ := map_cell_index_dynamic(vs, info.vs, capacity) // Skip past vs to get start of hs sk = map_cell_index_dynamic(hs_, &INFO_HS, capacity) // Skip past hs to get start of sk // Need to skip past two elements in the scratch key space to get to the start // of the scratch value space, of which there's only two elements as well. - sv = map_cell_index_dynamic_const(sk, &info.ks, 2) + sv = map_cell_index_dynamic_const(sk, info.ks, 2) hs = ([^]Map_Hash)(hs_) return @@ -272,7 +251,7 @@ map_kvh_data_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Inf map_kvh_data_values_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info) -> (vs: uintptr) { capacity := uintptr(1) << map_log2_cap(m) - return map_cell_index_dynamic(map_data(m), &info.ks, capacity) // Skip past ks to get start of vs + return map_cell_index_dynamic(map_data(m), info.ks, capacity) // Skip past ks to get start of vs } @@ -303,11 +282,11 @@ map_alloc_dynamic :: proc(info: ^Map_Info, log2_capacity: uintptr, allocator := } size := uintptr(0) - size = round(map_cell_index_dynamic(size, &info.ks, capacity)) - size = round(map_cell_index_dynamic(size, &info.vs, capacity)) + size = round(map_cell_index_dynamic(size, info.ks, capacity)) + size = round(map_cell_index_dynamic(size, info.vs, capacity)) size = round(map_cell_index_dynamic(size, &INFO_HS, capacity)) - size = round(map_cell_index_dynamic(size, &info.ks, 2)) // Two additional ks for scratch storage - size = round(map_cell_index_dynamic(size, &info.vs, 2)) // Two additional vs for scratch storage + size = round(map_cell_index_dynamic(size, info.ks, 2)) // Two additional ks for scratch storage + size = round(map_cell_index_dynamic(size, info.vs, 2)) // Two additional vs for scratch storage data := mem_alloc(int(size), MAP_CACHE_LINE_SIZE, allocator) or_return data_ptr := uintptr(raw_data(data)) @@ -334,8 +313,8 @@ map_alloc_dynamic :: proc(info: ^Map_Info, log2_capacity: uintptr, allocator := // This procedure returns the address of the just inserted value. @(optimization_mode="speed") map_insert_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, ik: uintptr, iv: uintptr) -> (result: uintptr) { - info_ks := &info.ks - info_vs := &info.vs + info_ks := info.ks + info_vs := info.vs p := map_desired_position(m, h) d := uintptr(0) @@ -416,8 +395,8 @@ map_insert_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Ha @(optimization_mode="speed") map_add_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, ik: uintptr, iv: uintptr) { - info_ks := &info.ks - info_vs := &info.vs + info_ks := info.ks + info_vs := info.vs capacity := uintptr(1) << map_log2_cap(m) p := map_desired_position(m, h) @@ -515,8 +494,8 @@ map_grow_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info) -> Al ks, vs, hs, _, _ := map_kvh_data_dynamic(m^, info) // Cache these loads to avoid hitting them in the for loop. - info_ks := &info.ks - info_vs := &info.vs + info_ks := info.ks + info_vs := info.vs n := map_len(m^) for i := uintptr(0); i < old_capacity; i += 1 { @@ -576,8 +555,8 @@ map_reserve_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, ne ks, vs, hs, _, _ := map_kvh_data_dynamic(m^, info) // Cache these loads to avoid hitting them in the for loop. - info_ks := &info.ks - info_vs := &info.vs + info_ks := info.ks + info_vs := info.vs n := map_len(m^) for i := uintptr(0); i < capacity; i += 1 { @@ -629,8 +608,8 @@ map_shrink_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info) -> ks, vs, hs, _, _ := map_kvh_data_dynamic(m^, info) - info_ks := &info.ks - info_vs := &info.vs + info_ks := info.ks + info_vs := info.vs n := map_len(m^) for i := uintptr(0); i < capacity; i += 1 { @@ -678,7 +657,7 @@ map_lookup_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, d := uintptr(0) c := (uintptr(1) << map_log2_cap(m)) - 1 ks, _, hs, _, _ := map_kvh_data_dynamic(m, info) - info_ks := &info.ks + info_ks := info.ks for { element_hash := hs[p] if map_hash_is_empty(element_hash) { @@ -702,7 +681,7 @@ map_exists_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, d := uintptr(0) c := (uintptr(1) << map_log2_cap(m)) - 1 ks, _, hs, _, _ := map_kvh_data_dynamic(m, info) - info_ks := &info.ks + info_ks := info.ks for { element_hash := hs[p] if map_hash_is_empty(element_hash) { @@ -766,7 +745,7 @@ __dynamic_map_get :: proc "contextless" (m: rawptr, #no_alias info: ^Map_Info, k rm := (^Raw_Map)(m)^ 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)) + ptr = rawptr(map_cell_index_dynamic(vs, info.vs, index)) } return } diff --git a/src/check_builtin.cpp b/src/check_builtin.cpp index b8bf1bcc7..457100d6e 100644 --- a/src/check_builtin.cpp +++ b/src/check_builtin.cpp @@ -5363,6 +5363,29 @@ bool check_builtin_procedure(CheckerContext *c, Operand *operand, Ast *call, i32 break; } + case BuiltinProc_type_map_info: + { + Operand op = {}; + Type *bt = check_type(c, ce->args[0]); + Type *type = base_type(bt); + if (type == nullptr || type == t_invalid) { + error(ce->args[0], "Expected a type for '%.*s'", LIT(builtin_name)); + return false; + } + if (!is_type_map(type)) { + gbString t = type_to_string(type); + error(ce->args[0], "Expected a map type for '%.*s', got %s", LIT(builtin_name), t); + gb_string_free(t); + return false; + } + + add_map_key_type_dependencies(c, type); + + operand->mode = Addressing_Value; + operand->type = t_map_info_ptr; + break; + } + case BuiltinProc_constant_utf16_cstring: { String value = {}; diff --git a/src/checker.cpp b/src/checker.cpp index fa3ef245b..5b9e83bda 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -2851,6 +2851,9 @@ void init_core_map_type(Checker *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")); + + t_map_info_ptr = alloc_type_pointer(t_map_info); + t_map_cell_info_ptr = alloc_type_pointer(t_map_cell_info); } void init_preload(Checker *c) { diff --git a/src/checker_builtin_procs.hpp b/src/checker_builtin_procs.hpp index c59ae7867..72639e071 100644 --- a/src/checker_builtin_procs.hpp +++ b/src/checker_builtin_procs.hpp @@ -277,6 +277,7 @@ BuiltinProc__type_simple_boolean_end, BuiltinProc_type_equal_proc, BuiltinProc_type_hasher_proc, + BuiltinProc_type_map_info, BuiltinProc__type_end, @@ -572,6 +573,7 @@ gb_global BuiltinProc builtin_procs[BuiltinProc_COUNT] = { {STR_LIT("type_equal_proc"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, {STR_LIT("type_hasher_proc"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, + {STR_LIT("type_map_info"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, {STR_LIT(""), 0, false, Expr_Stmt, BuiltinProcPkg_intrinsics}, diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index fa9727106..960ef84f6 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -502,6 +502,11 @@ lbValue lb_generate_anonymous_proc_lit(lbModule *m, String const &prefix_name, A LLVMValueRef lb_gen_map_cell_info(lbModule *m, Type *type) { + lbAddr *found = map_get(&m->map_cell_info_map, type); + if (found) { + return found->addr.value; + } + i64 size = 0, len = 0; map_cell_size_and_len(type, &size, &len); @@ -510,8 +515,15 @@ LLVMValueRef lb_gen_map_cell_info(lbModule *m, Type *type) { const_values[1] = lb_const_int(m, t_uintptr, type_align_of(type)).value; const_values[2] = lb_const_int(m, t_uintptr, size).value; const_values[3] = lb_const_int(m, t_uintptr, len).value; - return llvm_const_named_struct(m, t_map_cell_info, const_values, gb_count_of(const_values)); + LLVMValueRef llvm_res = llvm_const_named_struct(m, t_map_cell_info, const_values, gb_count_of(const_values)); + lbValue res = {llvm_res, t_map_cell_info}; + + lbAddr addr = lb_add_global_generated(m, t_map_cell_info, res, nullptr); + lb_make_global_private_const(addr); + + map_set(&m->map_cell_info_map, type, addr); + return addr.addr.value; } lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type) { map_type = base_type(map_type); diff --git a/src/llvm_backend.hpp b/src/llvm_backend.hpp index 2b9014d94..065bf4943 100644 --- a/src/llvm_backend.hpp +++ b/src/llvm_backend.hpp @@ -160,7 +160,8 @@ struct lbModule { StringMap objc_classes; StringMap objc_selectors; - PtrMap map_info_map; + PtrMap map_cell_info_map; // address of runtime.Map_Info + PtrMap map_info_map; // address of runtime.Map_Cell_Info }; struct lbGenerator { diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp index ffc7a1496..b7654614e 100644 --- a/src/llvm_backend_general.cpp +++ b/src/llvm_backend_general.cpp @@ -76,6 +76,7 @@ void lb_init_module(lbModule *m, Checker *c) { string_map_init(&m->objc_selectors, a); map_init(&m->map_info_map, a, 0); + map_init(&m->map_cell_info_map, a, 0); } diff --git a/src/llvm_backend_proc.cpp b/src/llvm_backend_proc.cpp index a9de7b231..3881790e0 100644 --- a/src/llvm_backend_proc.cpp +++ b/src/llvm_backend_proc.cpp @@ -2324,6 +2324,9 @@ lbValue lb_build_builtin_proc(lbProcedure *p, Ast *expr, TypeAndValue const &tv, case BuiltinProc_type_hasher_proc: return lb_get_hasher_proc_for_type(p->module, ce->args[0]->tav.type); + case BuiltinProc_type_map_info: + return lb_gen_map_info_ptr(p->module, ce->args[0]->tav.type); + case BuiltinProc_fixed_point_mul: case BuiltinProc_fixed_point_div: case BuiltinProc_fixed_point_mul_sat: diff --git a/src/types.cpp b/src/types.cpp index c92d8a78f..ca15531dd 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -685,6 +685,8 @@ 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_map_info_ptr = nullptr; +gb_global Type *t_map_cell_info_ptr = nullptr; gb_global Type *t_raw_map = nullptr; -- cgit v1.2.3 From a74093784cea3637b445657541cb7fff2f374f50 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 8 Nov 2022 12:24:00 +0000 Subject: Add `intrinsics.map_cell_info` and `intrinsics.map_info` --- core/intrinsics/intrinsics.odin | 3 +++ core/runtime/dynamic_map_internal.odin | 23 ++++++++--------------- src/check_builtin.cpp | 14 ++++++++++++++ src/checker_builtin_procs.hpp | 8 +++++--- src/llvm_backend.cpp | 10 +++++----- src/llvm_backend.hpp | 1 + src/llvm_backend_proc.cpp | 4 ++++ 7 files changed, 40 insertions(+), 23 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/core/intrinsics/intrinsics.odin b/core/intrinsics/intrinsics.odin index 69f77cea2..38542d2fc 100644 --- a/core/intrinsics/intrinsics.odin +++ b/core/intrinsics/intrinsics.odin @@ -188,6 +188,9 @@ type_field_index_of :: proc($T: typeid, $name: string) -> uintptr --- type_equal_proc :: proc($T: typeid) -> (equal: proc "contextless" (rawptr, rawptr) -> bool) where type_is_comparable(T) --- type_hasher_proc :: proc($T: typeid) -> (hasher: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr) where type_is_comparable(T) --- +type_map_info :: proc($T: typeid/map[$K]$V) -> ^runtime.Map_Info --- +type_map_cell_info :: proc($T: typeid) -> ^runtime.Map_Cell_Info --- + type_convert_variants_to_pointers :: proc($T: typeid) -> typeid where type_is_union(T) --- constant_utf16_cstring :: proc($literal: string) -> [^]u16 --- diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index 79e1a4f30..983bfde35 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -103,6 +103,9 @@ Map_Cell_Info :: struct { elements_per_cell: uintptr, // 8-bytes on 64-bit, 4-bytes on 32-bits } +// map_cell_info :: proc "contextless" ($T: typeid) -> ^Map_Cell_Info {...} +map_cell_info :: intrinsics.type_map_cell_info + // Same as the above procedure but at runtime with the cell Map_Cell_Info value. map_cell_index_dynamic :: #force_inline proc "contextless" (base: uintptr, info: ^Map_Cell_Info, index: uintptr) -> uintptr { // Micro-optimize the common cases to save on integer division. @@ -229,18 +232,13 @@ Map_Info :: struct { map_info :: intrinsics.type_map_info map_kvh_data_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info) -> (ks: uintptr, vs: uintptr, hs: [^]Map_Hash, sk: uintptr, sv: uintptr) { - @static INFO_HS := Map_Cell_Info { - size_of(Map_Hash), - align_of(Map_Hash), - size_of(Map_Cell(Map_Hash)), - len(Map_Cell(Map_Hash){}.data), - } + INFO_HS := intrinsics.type_map_cell_info(Map_Hash) capacity := uintptr(1) << map_log2_cap(m) ks = map_data(m) vs = map_cell_index_dynamic(ks, info.ks, capacity) // Skip past ks to get start of vs hs_ := map_cell_index_dynamic(vs, info.vs, capacity) // Skip past vs to get start of hs - sk = map_cell_index_dynamic(hs_, &INFO_HS, capacity) // Skip past hs to get start of sk + sk = map_cell_index_dynamic(hs_, INFO_HS, capacity) // Skip past hs to get start of sk // Need to skip past two elements in the scratch key space to get to the start // of the scratch value space, of which there's only two elements as well. sv = map_cell_index_dynamic_const(sk, info.ks, 2) @@ -270,21 +268,16 @@ map_alloc_dynamic :: proc(info: ^Map_Info, log2_capacity: uintptr, allocator := capacity := uintptr(1) << max(log2_capacity, MAP_MIN_LOG2_CAPACITY) - @static INFO_HS := Map_Cell_Info { - size_of(Map_Hash), - align_of(Map_Hash), - size_of(Map_Cell(Map_Hash)), - len(Map_Cell(Map_Hash){}.data), - } - round :: #force_inline proc "contextless" (value: uintptr) -> uintptr { return (value + MAP_CACHE_LINE_SIZE - 1) &~ uintptr(MAP_CACHE_LINE_SIZE - 1) } + INFO_HS := intrinsics.type_map_cell_info(Map_Hash) + size := uintptr(0) size = round(map_cell_index_dynamic(size, info.ks, capacity)) size = round(map_cell_index_dynamic(size, info.vs, capacity)) - size = round(map_cell_index_dynamic(size, &INFO_HS, capacity)) + size = round(map_cell_index_dynamic(size, INFO_HS, capacity)) size = round(map_cell_index_dynamic(size, info.ks, 2)) // Two additional ks for scratch storage size = round(map_cell_index_dynamic(size, info.vs, 2)) // Two additional vs for scratch storage diff --git a/src/check_builtin.cpp b/src/check_builtin.cpp index 457100d6e..890f7a39b 100644 --- a/src/check_builtin.cpp +++ b/src/check_builtin.cpp @@ -5385,6 +5385,20 @@ bool check_builtin_procedure(CheckerContext *c, Operand *operand, Ast *call, i32 operand->type = t_map_info_ptr; break; } + case BuiltinProc_type_map_cell_info: + { + Operand op = {}; + Type *bt = check_type(c, ce->args[0]); + Type *type = base_type(bt); + if (type == nullptr || type == t_invalid) { + error(ce->args[0], "Expected a type for '%.*s'", LIT(builtin_name)); + return false; + } + + operand->mode = Addressing_Value; + operand->type = t_map_cell_info_ptr; + break; + } case BuiltinProc_constant_utf16_cstring: { diff --git a/src/checker_builtin_procs.hpp b/src/checker_builtin_procs.hpp index 72639e071..e03e94ab4 100644 --- a/src/checker_builtin_procs.hpp +++ b/src/checker_builtin_procs.hpp @@ -278,6 +278,7 @@ BuiltinProc__type_simple_boolean_end, BuiltinProc_type_equal_proc, BuiltinProc_type_hasher_proc, BuiltinProc_type_map_info, + BuiltinProc_type_map_cell_info, BuiltinProc__type_end, @@ -571,9 +572,10 @@ gb_global BuiltinProc builtin_procs[BuiltinProc_COUNT] = { {STR_LIT("type_field_index_of"), 2, false, Expr_Expr, BuiltinProcPkg_intrinsics}, - {STR_LIT("type_equal_proc"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, - {STR_LIT("type_hasher_proc"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, - {STR_LIT("type_map_info"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, + {STR_LIT("type_equal_proc"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, + {STR_LIT("type_hasher_proc"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, + {STR_LIT("type_map_info"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, + {STR_LIT("type_map_cell_info"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics}, {STR_LIT(""), 0, false, Expr_Stmt, BuiltinProcPkg_intrinsics}, diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 960ef84f6..bce1fa1d1 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -501,10 +501,10 @@ lbValue lb_generate_anonymous_proc_lit(lbModule *m, String const &prefix_name, A } -LLVMValueRef lb_gen_map_cell_info(lbModule *m, Type *type) { +lbValue lb_gen_map_cell_info_ptr(lbModule *m, Type *type) { lbAddr *found = map_get(&m->map_cell_info_map, type); if (found) { - return found->addr.value; + return found->addr; } i64 size = 0, len = 0; @@ -523,7 +523,7 @@ LLVMValueRef lb_gen_map_cell_info(lbModule *m, Type *type) { map_set(&m->map_cell_info_map, type, addr); - return addr.addr.value; + return addr.addr; } lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type) { map_type = base_type(map_type); @@ -537,8 +537,8 @@ lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type) { GB_ASSERT(t_map_info != nullptr); GB_ASSERT(t_map_cell_info != nullptr); - LLVMValueRef key_cell_info = lb_gen_map_cell_info(m, map_type->Map.key); - LLVMValueRef value_cell_info = lb_gen_map_cell_info(m, map_type->Map.value); + LLVMValueRef key_cell_info = lb_gen_map_cell_info_ptr(m, map_type->Map.key).value; + LLVMValueRef value_cell_info = lb_gen_map_cell_info_ptr(m, map_type->Map.value).value; LLVMValueRef const_values[4] = {}; const_values[0] = key_cell_info; diff --git a/src/llvm_backend.hpp b/src/llvm_backend.hpp index 065bf4943..6c7c2e392 100644 --- a/src/llvm_backend.hpp +++ b/src/llvm_backend.hpp @@ -446,6 +446,7 @@ String lb_get_const_string(lbModule *m, lbValue value); lbValue lb_generate_local_array(lbProcedure *p, Type *elem_type, i64 count, bool zero_init=true); lbValue lb_generate_global_array(lbModule *m, Type *elem_type, i64 count, String prefix, i64 id); lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue *key_ptr_); +lbValue lb_gen_map_cell_info_ptr(lbModule *m, Type *type); lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type); lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key); diff --git a/src/llvm_backend_proc.cpp b/src/llvm_backend_proc.cpp index 3881790e0..6d7d7eecb 100644 --- a/src/llvm_backend_proc.cpp +++ b/src/llvm_backend_proc.cpp @@ -2327,6 +2327,10 @@ lbValue lb_build_builtin_proc(lbProcedure *p, Ast *expr, TypeAndValue const &tv, case BuiltinProc_type_map_info: return lb_gen_map_info_ptr(p->module, ce->args[0]->tav.type); + case BuiltinProc_type_map_cell_info: + return lb_gen_map_cell_info_ptr(p->module, ce->args[0]->tav.type); + + case BuiltinProc_fixed_point_mul: case BuiltinProc_fixed_point_div: case BuiltinProc_fixed_point_mul_sat: -- cgit v1.2.3 From 046dd5503211c617a88d7de7d089dd5b74e63500 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 8 Nov 2022 13:02:32 +0000 Subject: Change `__dynamic_map_get` signature --- core/runtime/dynamic_map_internal.odin | 173 +++++++++++++++++---------------- src/checker.cpp | 1 + src/llvm_backend.cpp | 19 ++-- src/llvm_backend_expr.cpp | 4 +- src/llvm_backend_general.cpp | 4 +- src/llvm_backend_utility.cpp | 23 ++--- src/types.cpp | 3 +- 7 files changed, 113 insertions(+), 114 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index 4218912c9..7e453b4b8 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -217,6 +217,9 @@ map_probe_distance :: #force_inline proc "contextless" (m: Raw_Map, hash: Map_Ha // about the map to make working with it possible. This info structure stores // that. // +// `Map_Info` and `Map_Cell_Info` are read only data structures and cannot be +// modified after creation +// // 32-bytes on 64-bit // 16-bytes on 32-bit Map_Info :: struct { @@ -255,7 +258,7 @@ map_kvh_data_values_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^ // The only procedure which needs access to the context is the one which allocates the map. -map_alloc_dynamic :: proc(info: ^Map_Info, log2_capacity: uintptr, allocator := context.allocator) -> (result: Raw_Map, err: Allocator_Error) { +map_alloc_dynamic :: proc "odin" (info: ^Map_Info, log2_capacity: uintptr, allocator := context.allocator, loc := #caller_location) -> (result: Raw_Map, err: Allocator_Error) { if log2_capacity == 0 { // Empty map, but set the allocator. return { 0, 0, allocator }, nil @@ -268,8 +271,9 @@ map_alloc_dynamic :: proc(info: ^Map_Info, log2_capacity: uintptr, allocator := capacity := uintptr(1) << max(log2_capacity, MAP_MIN_LOG2_CAPACITY) + CACHE_MASK :: MAP_CACHE_LINE_SIZE - 1 round :: #force_inline proc "contextless" (value: uintptr) -> uintptr { - return (value + MAP_CACHE_LINE_SIZE - 1) &~ uintptr(MAP_CACHE_LINE_SIZE - 1) + return (value + CACHE_MASK) &~ CACHE_MASK } INFO_HS := intrinsics.type_map_cell_info(Map_Hash) @@ -281,19 +285,20 @@ map_alloc_dynamic :: proc(info: ^Map_Info, log2_capacity: uintptr, allocator := size = round(map_cell_index_dynamic(size, info.ks, 2)) // Two additional ks for scratch storage size = round(map_cell_index_dynamic(size, info.vs, 2)) // Two additional vs for scratch storage - data := mem_alloc(int(size), MAP_CACHE_LINE_SIZE, allocator) or_return + data := mem_alloc_non_zeroed(int(size), MAP_CACHE_LINE_SIZE, allocator, loc) or_return data_ptr := uintptr(raw_data(data)) - assert(data_ptr & 63 == 0) + if intrinsics.expect(data_ptr & CACHE_MASK != 0, false) { + panic("allocation not aligned to a cache line", loc) + } else { + result = { + // Tagged pointer representation for capacity. + data_ptr | log2_capacity, + 0, + allocator, + } - result = { - // Tagged pointer representation for capacity. - data_ptr | log2_capacity, - 0, - allocator, + map_clear_dynamic(&result, info) } - - map_clear_dynamic(&result, info) - return } @@ -305,10 +310,7 @@ map_alloc_dynamic :: proc(info: ^Map_Info, log2_capacity: uintptr, allocator := // // This procedure returns the address of the just inserted value. @(optimization_mode="speed") -map_insert_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, ik: uintptr, iv: uintptr) -> (result: uintptr) { - info_ks := info.ks - info_vs := info.vs - +map_insert_hash_dynamic :: proc "odin" (m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, ik: uintptr, iv: uintptr) -> (result: uintptr) { p := map_desired_position(m, h) d := uintptr(0) c := (uintptr(1) << map_log2_cap(m)) - 1 // Saturating arithmetic mask @@ -316,8 +318,8 @@ map_insert_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Ha ks, vs, hs, sk, sv := map_kvh_data_dynamic(m, info) // Avoid redundant loads of these values - size_of_k := info_ks.size_of_type - size_of_v := info_vs.size_of_type + size_of_k := info.ks.size_of_type + size_of_v := info.vs.size_of_type // Use sk and sv scratch storage space for dynamic k and v storage here. // @@ -325,23 +327,23 @@ map_insert_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Ha // k = ik // v = iv // h = h - k := map_cell_index_dynamic_const(sk, info_ks, 0) - v := map_cell_index_dynamic_const(sv, info_vs, 0) + k := map_cell_index_dynamic_const(sk, info.ks, 0) + v := map_cell_index_dynamic_const(sv, info.vs, 0) intrinsics.mem_copy_non_overlapping(rawptr(k), rawptr(ik), size_of_k) intrinsics.mem_copy_non_overlapping(rawptr(v), rawptr(iv), size_of_v) h := h // Temporary k and v dynamic storage for swap below - tk := map_cell_index_dynamic_const(sk, info_ks, 1) - tv := map_cell_index_dynamic_const(sv, info_vs, 1) + tk := map_cell_index_dynamic_const(sk, info.ks, 1) + tv := map_cell_index_dynamic_const(sv, info.vs, 1) for { hp := &hs[p] element_hash := hp^ if map_hash_is_empty(element_hash) { - k_dst := map_cell_index_dynamic(ks, info_ks, p) - v_dst := map_cell_index_dynamic(vs, info_vs, p) + k_dst := map_cell_index_dynamic(ks, info.ks, p) + v_dst := map_cell_index_dynamic(vs, info.vs, p) intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k), size_of_k) intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v), size_of_v) hp^ = h @@ -350,8 +352,8 @@ map_insert_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Ha if pd := map_probe_distance(m, element_hash, p); pd < d { if map_hash_is_deleted(element_hash) { - k_dst := map_cell_index_dynamic(ks, info_ks, p) - v_dst := map_cell_index_dynamic(vs, info_vs, p) + k_dst := map_cell_index_dynamic(ks, info.ks, p) + v_dst := map_cell_index_dynamic(vs, info.vs, p) intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k), size_of_k) intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v), size_of_v) hp^ = h @@ -359,11 +361,11 @@ map_insert_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Ha } if result == 0 { - result = map_cell_index_dynamic(vs, info_vs, p) + result = map_cell_index_dynamic(vs, info.vs, p) } - kp := map_cell_index_dynamic(ks, info_vs, p) - vp := map_cell_index_dynamic(vs, info_ks, p) + kp := map_cell_index_dynamic(ks, info.vs, p) + vp := map_cell_index_dynamic(vs, info.ks, p) // Simulate the following at runtime with dynamic storage // @@ -387,10 +389,7 @@ map_insert_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Ha } @(optimization_mode="speed") -map_add_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, ik: uintptr, iv: uintptr) { - info_ks := info.ks - info_vs := info.vs - +map_add_hash_dynamic :: proc "odin" (m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, ik: uintptr, iv: uintptr) { capacity := uintptr(1) << map_log2_cap(m) p := map_desired_position(m, h) d := uintptr(0) @@ -399,8 +398,8 @@ map_add_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, ks, vs, hs, sk, sv := map_kvh_data_dynamic(m, info) // Avoid redundant loads of these values - size_of_k := info_ks.size_of_type - size_of_v := info_vs.size_of_type + size_of_k := info.ks.size_of_type + size_of_v := info.vs.size_of_type // Use sk and sv scratch storage space for dynamic k and v storage here. // @@ -408,23 +407,23 @@ map_add_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, // k = ik // v = iv // h = h - k := map_cell_index_dynamic_const(sk, info_ks, 0) - v := map_cell_index_dynamic_const(sv, info_vs, 0) + k := map_cell_index_dynamic_const(sk, info.ks, 0) + v := map_cell_index_dynamic_const(sv, info.vs, 0) intrinsics.mem_copy_non_overlapping(rawptr(k), rawptr(ik), size_of_k) intrinsics.mem_copy_non_overlapping(rawptr(v), rawptr(iv), size_of_v) h := h // Temporary k and v dynamic storage for swap below - tk := map_cell_index_dynamic_const(sk, info_ks, 1) - tv := map_cell_index_dynamic_const(sv, info_vs, 1) + tk := map_cell_index_dynamic_const(sk, info.ks, 1) + tv := map_cell_index_dynamic_const(sv, info.vs, 1) for { hp := &hs[p] element_hash := hp^ if map_hash_is_empty(element_hash) { - k_dst := map_cell_index_dynamic(ks, info_ks, p) - v_dst := map_cell_index_dynamic(vs, info_vs, p) + k_dst := map_cell_index_dynamic(ks, info.ks, p) + v_dst := map_cell_index_dynamic(vs, info.vs, p) intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k), size_of_k) intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v), size_of_v) hp^ = h @@ -433,16 +432,16 @@ map_add_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, if pd := map_probe_distance(m, element_hash, p); pd < d { if map_hash_is_deleted(element_hash) { - k_dst := map_cell_index_dynamic(ks, info_ks, p) - v_dst := map_cell_index_dynamic(vs, info_vs, p) + k_dst := map_cell_index_dynamic(ks, info.ks, p) + v_dst := map_cell_index_dynamic(vs, info.vs, p) intrinsics.mem_copy_non_overlapping(rawptr(k_dst), rawptr(k), size_of_k) intrinsics.mem_copy_non_overlapping(rawptr(v_dst), rawptr(v), size_of_v) hp^ = h return } - kp := map_cell_index_dynamic(ks, info_vs, p) - vp := map_cell_index_dynamic(vs, info_ks, p) + kp := map_cell_index_dynamic(ks, info.vs, p) + vp := map_cell_index_dynamic(vs, info.ks, p) // Simulate the following at runtime with dynamic storage // @@ -466,7 +465,7 @@ map_add_hash_dynamic :: proc(m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, } @(optimization_mode="size") -map_grow_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info) -> Allocator_Error { +map_grow_dynamic :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, loc := #caller_location) -> Allocator_Error { allocator := m.allocator if allocator.procedure == nil { allocator = context.allocator @@ -475,23 +474,20 @@ map_grow_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info) -> Al log2_capacity := map_log2_cap(m^) if m.data == 0 { - n := map_alloc_dynamic(info, MAP_MIN_LOG2_CAPACITY, allocator) or_return + n := map_alloc_dynamic(info, MAP_MIN_LOG2_CAPACITY, allocator, loc) or_return m.data = n.data return nil } - resized := map_alloc_dynamic(info, log2_capacity + 1, allocator) or_return + resized := map_alloc_dynamic(info, log2_capacity + 1, allocator, loc) or_return old_capacity := uintptr(1) << log2_capacity ks, vs, hs, _, _ := map_kvh_data_dynamic(m^, info) // Cache these loads to avoid hitting them in the for loop. - info_ks := info.ks - info_vs := info.vs - n := map_len(m^) - for i := uintptr(0); i < old_capacity; i += 1 { + for i in 0.. Al if map_hash_is_deleted(hash) { continue } - k := map_cell_index_dynamic(ks, info_ks, i) - v := map_cell_index_dynamic(vs, info_vs, i) + k := map_cell_index_dynamic(ks, info.ks, i) + v := map_cell_index_dynamic(vs, info.vs, i) map_insert_hash_dynamic(resized, info, hash, k, v) // Only need to do this comparison on each actually added pair, so do not // fold it into the for loop comparator as a micro-optimization. @@ -510,7 +506,7 @@ map_grow_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info) -> Al } } - mem_free(rawptr(ks), allocator) + mem_free(rawptr(ks), allocator, loc) m.data = resized.data // Should copy the capacity too @@ -519,7 +515,7 @@ map_grow_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info) -> Al @(optimization_mode="size") -map_reserve_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, new_capacity: uintptr) -> Allocator_Error { +map_reserve_dynamic :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, new_capacity: uintptr) -> Allocator_Error { allocator := m.allocator if allocator.procedure == nil { allocator = context.allocator @@ -544,15 +540,11 @@ map_reserve_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, ne resized := map_alloc_dynamic(info, log2_new_capacity, allocator) or_return - ks, vs, hs, _, _ := map_kvh_data_dynamic(m^, info) // Cache these loads to avoid hitting them in the for loop. - info_ks := info.ks - info_vs := info.vs - n := map_len(m^) - for i := uintptr(0); i < capacity; i += 1 { + for i in 0.. Allocator_Error { +map_shrink_dynamic :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info) -> Allocator_Error { allocator := m.allocator if allocator.procedure == nil { // TODO(bill): is this correct behaviour? @@ -601,11 +593,8 @@ map_shrink_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info) -> ks, vs, hs, _, _ := map_kvh_data_dynamic(m^, info) - info_ks := info.ks - info_vs := info.vs - n := map_len(m^) - for i := uintptr(0); i < capacity; i += 1 { + for i in 0.. continue } - k := map_cell_index_dynamic(ks, info_ks, i) - v := map_cell_index_dynamic(vs, info_vs, i) + k := map_cell_index_dynamic(ks, info.ks, i) + v := map_cell_index_dynamic(vs, info.vs, i) map_insert_hash_dynamic(shrinked, info, hash, k, v) @@ -636,7 +625,7 @@ map_shrink_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info) -> // Single procedure for static and dynamic paths. @(require_results) -map_free :: proc(m: Raw_Map, loc := #caller_location) -> Allocator_Error { +map_free :: proc "odin" (m: Raw_Map, loc := #caller_location) -> Allocator_Error { return mem_free(rawptr(map_data(m)), m.allocator, loc) } @@ -650,14 +639,13 @@ map_lookup_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, d := uintptr(0) c := (uintptr(1) << map_log2_cap(m)) - 1 ks, _, hs, _, _ := map_kvh_data_dynamic(m, info) - info_ks := info.ks for { element_hash := hs[p] if map_hash_is_empty(element_hash) { return 0, false } else if d > map_probe_distance(m, element_hash, p) { return 0, false - } else if element_hash == h && info.key_equal(rawptr(k), rawptr(map_cell_index_dynamic(ks, info_ks, p))) { + } else if element_hash == h && info.key_equal(rawptr(k), rawptr(map_cell_index_dynamic(ks, info.ks, p))) { return p, true } p = (p + 1) & c @@ -674,14 +662,13 @@ map_exists_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, d := uintptr(0) c := (uintptr(1) << map_log2_cap(m)) - 1 ks, _, hs, _, _ := map_kvh_data_dynamic(m, info) - info_ks := info.ks for { element_hash := hs[p] if map_hash_is_empty(element_hash) { return false } else if d > map_probe_distance(m, element_hash, p) { return false - } else if element_hash == h && info.key_equal(rawptr(k), rawptr(map_cell_index_dynamic(ks, info_ks, p))) { + } else if element_hash == h && info.key_equal(rawptr(k), rawptr(map_cell_index_dynamic(ks, info.ks, p))) { return true } p = (p + 1) & c @@ -693,9 +680,9 @@ map_exists_dynamic :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, @(optimization_mode="speed") -map_insert_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, k, v: uintptr) -> (value: uintptr, err: Allocator_Error) { +map_insert_dynamic :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, k, v: uintptr, loc := #caller_location) -> (value: uintptr, err: Allocator_Error) { if map_len(m^) + 1 >= map_resize_threshold(m^) { - map_grow_dynamic(m, info) or_return + map_grow_dynamic(m, info, loc) or_return } hashed := info.key_hasher(rawptr(k), 0) value = map_insert_hash_dynamic(m^, info, hashed, k, v) @@ -705,9 +692,9 @@ map_insert_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, k, // Same as map_insert_dynamic but does not return address to the inserted element. @(optimization_mode="speed") -map_add_dynamic :: proc(#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, k, v: uintptr) -> Allocator_Error { +map_add_dynamic :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, k, v: uintptr, loc := #caller_location) -> Allocator_Error { if map_len(m^) + 1 >= map_resize_threshold(m^) { - map_grow_dynamic(m, info) or_return + map_grow_dynamic(m, info, loc) or_return } map_add_hash_dynamic(m^, info, info.key_hasher(rawptr(k), 0), k, v) m.len += 1 @@ -734,13 +721,28 @@ map_clear_dynamic :: #force_inline proc "contextless" (#no_alias m: ^Raw_Map, #n } -__dynamic_map_get :: proc "contextless" (m: rawptr, #no_alias info: ^Map_Info, key: rawptr) -> (ptr: rawptr) { - rm := (^Raw_Map)(m)^ - 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)) +__dynamic_map_get :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, key: rawptr) -> (ptr: rawptr) { + if m.len == 0 { + return nil + } + + h := info.key_hasher(key, 0) + p := map_desired_position(m, h) + d := uintptr(0) + c := (uintptr(1) << map_log2_cap(m)) - 1 + ks, vs, hs, _, _ := map_kvh_data_dynamic(m, info) + for { + element_hash := hs[p] + if map_hash_is_empty(element_hash) { + return nil + } else if d > map_probe_distance(m, element_hash, p) { + return nil + } else if element_hash == h && info.key_equal(key, rawptr(map_cell_index_dynamic(ks, info.ks, p))) { + return rawptr(map_cell_index_dynamic(vs, info.vs, p)) + } + p = (p + 1) & c + d += 1 } - return } __dynamic_map_set :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, key, value: rawptr, loc := #caller_location) -> rawptr { @@ -748,6 +750,7 @@ __dynamic_map_set :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_In return rawptr(value) if err == nil else nil } +@(private) __dynamic_map_reserve :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, new_capacity: uint, loc := #caller_location) { map_reserve_dynamic(m, info, uintptr(new_capacity)) } diff --git a/src/checker.cpp b/src/checker.cpp index 5b9e83bda..75a6da6fa 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -2854,6 +2854,7 @@ void init_core_map_type(Checker *c) { t_map_info_ptr = alloc_type_pointer(t_map_info); t_map_cell_info_ptr = alloc_type_pointer(t_map_cell_info); + t_raw_map_ptr = alloc_type_pointer(t_raw_map); } void init_preload(Checker *c) { diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index bce1fa1d1..629daf1c9 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -622,14 +622,15 @@ lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue return hashed_key; } -lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key) { - Type *map_type = base_type(type_deref(map_ptr.type)); +lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map, lbValue const &key) { + Type *map_type = base_type(map.type); + GB_ASSERT(map_type->kind == Type_Map); lbValue key_ptr = lb_address_from_load_or_generate_local(p, key); key_ptr = lb_emit_conv(p, key_ptr, t_rawptr); auto args = array_make(permanent_allocator(), 3); - args[0] = lb_emit_conv(p, map_ptr, t_rawptr); + args[0] = lb_emit_transmute(p, map, t_raw_map); args[1] = lb_gen_map_info_ptr(p->module, map_type); args[2] = key_ptr; @@ -644,17 +645,15 @@ void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, GB_ASSERT(map_type->kind == Type_Map); lbValue key_ptr = lb_address_from_load_or_generate_local(p, map_key); - key_ptr = lb_emit_conv(p, key_ptr, t_rawptr); - lbValue v = lb_emit_conv(p, map_value, map_type->Map.value); - lbAddr value_addr = lb_add_local_generated(p, v.type, false); - lb_addr_store(p, value_addr, v); + lbValue v = lb_emit_conv(p, map_value, map_type->Map.value); + lbValue value_ptr = lb_address_from_load_or_generate_local(p, v); auto args = array_make(permanent_allocator(), 5); - args[0] = lb_emit_conv(p, map_ptr, t_rawptr); + args[0] = lb_emit_conv(p, map_ptr, t_raw_map_ptr); args[1] = lb_gen_map_info_ptr(p->module, map_type); - args[2] = key_ptr; - args[3] = lb_emit_conv(p, value_addr.addr, t_rawptr); + args[2] = lb_emit_conv(p, key_ptr, t_rawptr); + args[3] = lb_emit_conv(p, value_ptr, t_rawptr); args[4] = lb_emit_source_code_location_as_global(p, node); lb_emit_runtime_call(p, "__dynamic_map_set", args); } diff --git a/src/llvm_backend_expr.cpp b/src/llvm_backend_expr.cpp index 05a9fdfbf..7e9aa3a78 100644 --- a/src/llvm_backend_expr.cpp +++ b/src/llvm_backend_expr.cpp @@ -1423,9 +1423,9 @@ lbValue lb_build_binary_expr(lbProcedure *p, Ast *expr) { switch (rt->kind) { case Type_Map: { - lbValue map_ptr = lb_address_from_load_or_generate_local(p, right); + lbValue map = right; lbValue key = left; - lbValue ptr = lb_internal_dynamic_map_get_ptr(p, map_ptr, key); + lbValue ptr = lb_internal_dynamic_map_get_ptr(p, map, key); if (be->op.kind == Token_in) { return lb_emit_conv(p, lb_emit_comp_against_nil(p, Token_NotEq, ptr), t_bool); } else { diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp index b7654614e..e1a926255 100644 --- a/src/llvm_backend_general.cpp +++ b/src/llvm_backend_general.cpp @@ -417,7 +417,7 @@ lbValue lb_addr_get_ptr(lbProcedure *p, lbAddr const &addr) { switch (addr.kind) { case lbAddr_Map: - return lb_internal_dynamic_map_get_ptr(p, addr.addr, addr.map.key); + return lb_internal_dynamic_map_get_ptr(p, lb_emit_load(p, addr.addr), addr.map.key); case lbAddr_RelativePointer: { Type *rel_ptr = base_type(lb_addr_type(addr)); @@ -1074,7 +1074,7 @@ lbValue lb_addr_load(lbProcedure *p, lbAddr const &addr) { GB_ASSERT(map_type->kind == Type_Map); lbAddr v = lb_add_local_generated(p, map_type->Map.lookup_result_type, true); - lbValue ptr = lb_internal_dynamic_map_get_ptr(p, addr.addr, addr.map.key); + lbValue ptr = lb_internal_dynamic_map_get_ptr(p, lb_emit_load(p, addr.addr), addr.map.key); lbValue ok = lb_emit_conv(p, lb_emit_comp_against_nil(p, Token_NotEq, ptr), t_bool); lb_emit_store(p, lb_emit_struct_ep(p, v.addr, 1), ok); diff --git a/src/llvm_backend_utility.cpp b/src/llvm_backend_utility.cpp index f4d17c7a2..a3493f864 100644 --- a/src/llvm_backend_utility.cpp +++ b/src/llvm_backend_utility.cpp @@ -203,26 +203,19 @@ lbValue lb_emit_transmute(lbProcedure *p, lbValue value, Type *t) { if (is_type_uintptr(src) && is_type_internally_pointer_like(dst)) { res.value = LLVMBuildIntToPtr(p->builder, value.value, lb_type(m, t), ""); return res; - } - if (is_type_internally_pointer_like(src) && is_type_uintptr(dst)) { + } else if (is_type_internally_pointer_like(src) && is_type_uintptr(dst)) { res.value = LLVMBuildPtrToInt(p->builder, value.value, lb_type(m, t), ""); return res; - } - - if (is_type_integer(src) && is_type_internally_pointer_like(dst)) { + } else if (is_type_integer(src) && is_type_internally_pointer_like(dst)) { res.value = LLVMBuildIntToPtr(p->builder, value.value, lb_type(m, t), ""); return res; } else if (is_type_internally_pointer_like(src) && is_type_integer(dst)) { res.value = LLVMBuildPtrToInt(p->builder, value.value, lb_type(m, t), ""); return res; - } - - if (is_type_internally_pointer_like(src) && is_type_internally_pointer_like(dst)) { + } else if (is_type_internally_pointer_like(src) && is_type_internally_pointer_like(dst)) { res.value = LLVMBuildPointerCast(p->builder, value.value, lb_type(p->module, t), ""); return res; - } - - if (is_type_simd_vector(src) && is_type_simd_vector(dst)) { + } else if (is_type_simd_vector(src) && is_type_simd_vector(dst)) { res.value = LLVMBuildBitCast(p->builder, value.value, lb_type(p->module, t), ""); return res; } else if (is_type_array_like(src) && is_type_simd_vector(dst)) { @@ -239,9 +232,11 @@ lbValue lb_emit_transmute(lbProcedure *p, lbValue value, Type *t) { ap = lb_emit_conv(p, ap, alloc_type_pointer(value.type)); lb_emit_store(p, ap, value); return lb_addr_load(p, addr); - } - - if (lb_is_type_aggregate(src) || lb_is_type_aggregate(dst)) { + } else if (is_type_map(src) && are_types_identical(t_raw_map, t)) { + res.value = value.value; + res.type = t; + return res; + } else if (lb_is_type_aggregate(src) || lb_is_type_aggregate(dst)) { lbValue s = lb_address_from_load_or_generate_local(p, value); lbValue d = lb_emit_transmute(p, s, alloc_type_pointer(t)); return lb_emit_load(p, d); diff --git a/src/types.cpp b/src/types.cpp index ca15531dd..ab82e87b8 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -685,9 +685,10 @@ 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_map_info_ptr = nullptr; gb_global Type *t_map_cell_info_ptr = nullptr; -gb_global Type *t_raw_map = nullptr; +gb_global Type *t_raw_map_ptr = nullptr; gb_global Type *t_equal_proc = nullptr; -- cgit v1.2.3 From a71daee545f5425aae971c0e00d7064fe53d64c7 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 8 Nov 2022 14:58:05 +0000 Subject: Allow for `-use-static-map-calls` which generates a get procedure per `map`; add `runtime.map_get` --- core/runtime/dynamic_map_internal.odin | 104 ++++++++++++++++++-- src/build_settings.cpp | 2 + src/check_expr.cpp | 15 ++- src/checker.cpp | 4 + src/llvm_backend.cpp | 172 ++++++++++++++++++++++++++++++--- src/llvm_backend.hpp | 1 + src/llvm_backend_general.cpp | 1 + src/llvm_backend_stmt.cpp | 26 +++-- src/llvm_backend_utility.cpp | 4 +- src/main.cpp | 6 ++ src/types.cpp | 1 + 11 files changed, 302 insertions(+), 34 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index 7e453b4b8..b9b10dd40 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -137,6 +137,47 @@ map_cell_index_dynamic_const :: proc "contextless" (base: uintptr, #no_alias inf return base + (cell_index * size_of_cell) + (data_index * size_of_type) } +// We always round the capacity to a power of two so this becomes [16]Foo, which +// works out to [4]Cell(Foo). +// +// The following compile-time procedure indexes such a [N]Cell(T) structure as +// if it were a flat array accounting for the internal padding introduced by the +// Cell structure. +map_cell_index_static :: #force_inline proc "contextless" (cells: [^]Map_Cell($T), index: uintptr) -> ^T #no_bounds_check { + N :: size_of(Map_Cell(T){}.data) / size_of(T) when size_of(T) > 0 else 1 + + #assert(N <= MAP_CACHE_LINE_SIZE) + + // No padding case, can treat as a regular array of []T. + when size_of(Map_Cell(T)) == size_of([N]T) { + return &([^]T)(cells)[index] + } + + // Likely case, N is a power of two because T is a power of two. + when (N & (N - 1)) == 0 { + // Compute the integer log 2 of N, this is the shift amount to index the + // correct cell. Odin's intrinsics.count_leading_zeros does not produce a + // constant, hence this approach. We only need to check up to N = 64. + SHIFT :: 1 when N < 2 else + 2 when N < 4 else + 3 when N < 8 else + 4 when N < 16 else + 5 when N < 32 else 6 + #assert(SHIFT <= MAP_CACHE_LINE_LOG2) + // Unique case, no need to index data here since only one element. + when N == 1 { + return &cells[index >> SHIFT].data[0] + } else { + return &cells[index >> SHIFT].data[index & (N - 1)] + } + } + + // Least likely (and worst case), we pay for a division operation but we + // assume the compiler does not actually generate a division. N will be in the + // range [1, CACHE_LINE_SIZE) and not a power of two. + return &cells[index / N].data[index % N] +} + // len() for map map_len :: #force_inline proc "contextless" (m: Raw_Map) -> int { return m.len @@ -721,27 +762,72 @@ map_clear_dynamic :: #force_inline proc "contextless" (#no_alias m: ^Raw_Map, #n } +map_kvh_data_static :: #force_inline proc "contextless" (m: $T/map[$K]$V) -> ([^]Map_Cell(K), [^]Map_Cell(V), [^]Map_Hash) { + H :: Map_Hash + capacity := uintptr(cap(m)) + ks := ([^]Map_Cell(K))(map_data(transmute(Raw_Map)m)) + vs := ([^]Map_Cell(V))(map_cell_index_static(ks, capacity)) + hs := ([^]Map_Cell(H))(map_cell_index_static(vs, capacity)) + return ks, vs, ([^]Map_Hash)(hs) +} + + +map_get :: proc "contextless" (m: $T/map[$K]$V, key: K) -> (stored_key: K, stored_value: V, ok: bool) { + rm := transmute(Raw_Map)m + if rm.len == 0 { + return + } + info := intrinsics.type_map_info(T) + key := key + + h := info.key_hasher(&key, 0) + pos := map_desired_position(rm, h) + distance := uintptr(0) + mask := (uintptr(1) << map_log2_cap(rm)) - 1 + ks, vs, hs := map_kvh_data_static(m) + for { + element_hash := hs[pos] + if map_hash_is_empty(element_hash) { + return + } else if distance > map_probe_distance(rm, element_hash, pos) { + return + } else if element_hash == h { + element_key := map_cell_index_static(ks, pos) + if info.key_equal(&key, rawptr(element_key)) { + element_value := map_cell_index_static(vs, pos) + stored_key = (^K)(element_key)^ + stored_value = (^V)(element_value)^ + ok = true + return + } + + } + pos = (pos + 1) & mask + distance += 1 + } +} + __dynamic_map_get :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, key: rawptr) -> (ptr: rawptr) { if m.len == 0 { return nil } h := info.key_hasher(key, 0) - p := map_desired_position(m, h) - d := uintptr(0) - c := (uintptr(1) << map_log2_cap(m)) - 1 + pos := map_desired_position(m, h) + distance := uintptr(0) + mask := (uintptr(1) << map_log2_cap(m)) - 1 ks, vs, hs, _, _ := map_kvh_data_dynamic(m, info) for { - element_hash := hs[p] + element_hash := hs[pos] if map_hash_is_empty(element_hash) { return nil - } else if d > map_probe_distance(m, element_hash, p) { + } else if distance > map_probe_distance(m, element_hash, pos) { return nil - } else if element_hash == h && info.key_equal(key, rawptr(map_cell_index_dynamic(ks, info.ks, p))) { - return rawptr(map_cell_index_dynamic(vs, info.vs, p)) + } else if element_hash == h && info.key_equal(key, rawptr(map_cell_index_dynamic(ks, info.ks, pos))) { + return rawptr(map_cell_index_dynamic(vs, info.vs, pos)) } - p = (p + 1) & c - d += 1 + pos = (pos + 1) & mask + distance += 1 } } diff --git a/src/build_settings.cpp b/src/build_settings.cpp index 8067d1d01..1cd2899c4 100644 --- a/src/build_settings.cpp +++ b/src/build_settings.cpp @@ -307,6 +307,8 @@ struct BuildContext { bool disallow_rtti; + bool use_static_map_calls; + RelocMode reloc_mode; bool disable_red_zone; diff --git a/src/check_expr.cpp b/src/check_expr.cpp index c2753e979..045b22ca2 100644 --- a/src/check_expr.cpp +++ b/src/check_expr.cpp @@ -3244,7 +3244,12 @@ void check_binary_expr(CheckerContext *c, Operand *x, Ast *node, Type *type_hint check_assignment(c, x, yt->Map.key, str_lit("map 'not_in'")); } - add_package_dependency(c, "runtime", "__dynamic_map_get"); + if (build_context.use_static_map_calls) { + add_package_dependency(c, "runtime", "map_desired_position"); + add_package_dependency(c, "runtime", "map_probe_distance"); + } else { + add_package_dependency(c, "runtime", "__dynamic_map_get"); + } } else if (is_type_bit_set(rhs_type)) { Type *yt = base_type(rhs_type); @@ -8992,8 +8997,14 @@ ExprKind check_index_expr(CheckerContext *c, Operand *o, Ast *node, Type *type_h o->type = t->Map.value; o->expr = node; - add_package_dependency(c, "runtime", "__dynamic_map_get"); + add_package_dependency(c, "runtime", "__dynamic_map_set"); + if (build_context.use_static_map_calls) { + add_package_dependency(c, "runtime", "map_desired_position"); + add_package_dependency(c, "runtime", "map_probe_distance"); + } else { + add_package_dependency(c, "runtime", "__dynamic_map_get"); + } return Expr_Expr; } diff --git a/src/checker.cpp b/src/checker.cpp index 75a6da6fa..d48b37b26 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -926,6 +926,10 @@ void init_universal(void) { Type *hasher_args[2] = {t_rawptr, t_uintptr}; t_hasher_proc = alloc_type_proc_from_types(hasher_args, 2, t_uintptr, false, ProcCC_Contextless); + + Type *map_get_args[2] = {/*map*/t_rawptr, /*key*/t_rawptr}; + t_map_get_proc = alloc_type_proc_from_types(map_get_args, 2, t_rawptr, false, ProcCC_Contextless); + } // Constants diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 629daf1c9..2b95c5b2f 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -157,8 +157,8 @@ lbValue lb_get_equal_proc_for_type(lbModule *m, Type *type) { static u32 proc_index = 0; - char buf[16] = {}; - isize n = gb_snprintf(buf, 16, "__$equal%u", ++proc_index); + char buf[32] = {}; + isize n = gb_snprintf(buf, 32, "__$equal%u", ++proc_index); char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1); String proc_name = make_string_c(str); @@ -280,8 +280,8 @@ lbValue lb_simple_compare_hash(lbProcedure *p, Type *type, lbValue data, lbValue i64 sz = type_size_of(type); if (1 <= sz && sz <= 16) { - char name[20] = {}; - gb_snprintf(name, 20, "default_hasher%d", cast(i32)sz); + char name[32] = {}; + gb_snprintf(name, 32, "default_hasher%d", cast(i32)sz); auto args = array_make(permanent_allocator(), 2); args[0] = data; @@ -310,8 +310,8 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { static u32 proc_index = 0; - char buf[16] = {}; - isize n = gb_snprintf(buf, 16, "__$hasher%u", ++proc_index); + char buf[32] = {}; + isize n = gb_snprintf(buf, 32, "__$hasher%u", ++proc_index); char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1); String proc_name = make_string_c(str); @@ -454,6 +454,141 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { } +lbValue lb_get_map_get_proc_for_type(lbModule *m, Type *type) { + GB_ASSERT(build_context.use_static_map_calls); + type = base_type(type); + GB_ASSERT(type->kind == Type_Map); + + + lbProcedure **found = map_get(&m->map_get_procs, type); + if (found) { + GB_ASSERT(*found != nullptr); + return {(*found)->value, (*found)->type}; + } + static u32 proc_index = 0; + + char buf[32] = {}; + isize n = gb_snprintf(buf, 32, "__$map_get%u", ++proc_index); + char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1); + String proc_name = make_string_c(str); + + lbProcedure *p = lb_create_dummy_procedure(m, proc_name, t_map_get_proc); + map_set(&m->map_get_procs, type, p); + lb_begin_procedure_body(p); + defer (lb_end_procedure_body(p)); + + LLVMValueRef x = LLVMGetParam(p->value, 0); + LLVMValueRef y = LLVMGetParam(p->value, 1); + lbValue map_ptr = {x, t_rawptr}; + lbValue key_ptr = {y, t_rawptr}; + + LLVMAttributeRef nonnull_attr = lb_create_enum_attribute(m->ctx, "nonnull"); + LLVMAttributeRef noalias_attr = lb_create_enum_attribute(m->ctx, "noalias"); + LLVMAddAttributeAtIndex(p->value, 1+0, nonnull_attr); + LLVMAddAttributeAtIndex(p->value, 1+0, noalias_attr); + LLVMAddAttributeAtIndex(p->value, 1+1, nonnull_attr); + LLVMAddAttributeAtIndex(p->value, 1+1, noalias_attr); + + map_ptr = lb_emit_conv(p, map_ptr, t_raw_map_ptr); + lbValue map = lb_emit_load(p, map_ptr); + + key_ptr = lb_emit_conv(p, key_ptr, alloc_type_pointer(type->Map.key)); + lbValue key = lb_emit_load(p, key_ptr); + + lbValue h = lb_gen_map_key_hash(p, key, type->Map.key, nullptr); + lbAddr pos = lb_add_local_generated(p, t_uintptr, false); + lbAddr distance = lb_add_local_generated(p, t_uintptr, true); + lbValue capacity = lb_map_cap(p, map); + lbValue mask = lb_emit_conv(p, lb_emit_arith(p, Token_Sub, capacity, lb_const_int(m, t_int, 1), t_int), t_uintptr); + + { + auto args = array_make(heap_allocator(), 2); + args[0] = map; + args[1] = h; + lb_addr_store(p, pos, lb_emit_runtime_call(p, "map_desired_position", args)); + } + lbValue zero_uintptr = lb_const_int(m, t_uintptr, 0); + lbValue one_uintptr = lb_const_int(m, t_uintptr, 1); + + lbValue ks = lb_map_data_uintptr(p, map); + 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); + + ks = lb_emit_conv(p, ks, alloc_type_pointer(type->Map.key)); + vs = lb_emit_conv(p, vs, alloc_type_pointer(type->Map.value)); + hs = lb_emit_conv(p, hs, alloc_type_pointer(t_uintptr)); + + // lbValue res = + // LLVMBuildRet(p->builder, res.value); + + lbBlock *loop = lb_create_block(p, "loop"); + lbBlock *probe_block = lb_create_block(p, "probe"); + lbBlock *increment_block = lb_create_block(p, "increment"); + lbBlock *hash_compare_block = lb_create_block(p, "hash_compare"); + lbBlock *key_compare_block = lb_create_block(p, "key_compare"); + lbBlock *value_block = lb_create_block(p, "value"); + lbBlock *nil_block = lb_create_block(p, "nil"); + + lb_emit_jump(p, loop); + lb_start_block(p, loop); + + lbValue element_hash = lb_emit_load(p, lb_emit_ptr_offset(p, hs, lb_addr_load(p, pos))); + { + // if element_hash == 0 { return nil } + lb_emit_if(p, lb_emit_comp(p, Token_CmpEq, element_hash, zero_uintptr), nil_block, probe_block); + } + + lb_start_block(p, probe_block); + { + auto args = array_make(heap_allocator(), 3); + args[0] = map; + args[1] = element_hash; + args[2] = lb_addr_load(p, pos); + lbValue probe_distance = lb_emit_runtime_call(p, "map_probe_distance", args); + lbValue cond = lb_emit_comp(p, Token_Gt, lb_addr_load(p, distance), probe_distance); + lb_emit_if(p, cond, nil_block, hash_compare_block); + } + + lb_start_block(p, hash_compare_block); + { + lb_emit_if(p, lb_emit_comp(p, Token_CmpEq, element_hash, h), key_compare_block, increment_block); + } + + lb_start_block(p, key_compare_block); + { + lbValue element_key = lb_map_cell_index_static(p, type->Map.key, ks, lb_addr_load(p, pos)); + element_key = lb_emit_conv(p, element_key, ks.type); + lbValue cond = lb_emit_comp(p, Token_CmpEq, lb_emit_load(p, element_key), key); + lb_emit_if(p, cond, value_block, increment_block); + } + + lb_start_block(p, value_block); + { + lbValue element_value = lb_map_cell_index_static(p, type->Map.value, vs, lb_addr_load(p, pos)); + element_value = lb_emit_conv(p, element_value, t_rawptr); + LLVMBuildRet(p->builder, element_value.value); + } + + lb_start_block(p, increment_block); + { + lbValue pp = lb_addr_load(p, pos); + pp = lb_emit_arith(p, Token_Add, pp, one_uintptr, t_uintptr); + pp = lb_emit_arith(p, Token_And, pp, mask, t_uintptr); + lb_addr_store(p, pos, pp); + lb_emit_increment(p, distance.addr); + } + lb_emit_jump(p, loop); + + lb_start_block(p, nil_block); + { + lbValue res = lb_const_nil(m, t_rawptr); + LLVMBuildRet(p->builder, res.value); + } + + + return {p->value, p->type}; +} + lbValue lb_generate_anonymous_proc_lit(lbModule *m, String const &prefix_name, Ast *expr, lbProcedure *parent) { lbProcedure **found = map_get(&m->gen->anonymous_proc_lits, expr); if (found) { @@ -626,16 +761,27 @@ lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map, lbVa Type *map_type = base_type(map.type); GB_ASSERT(map_type->kind == Type_Map); + lbValue ptr = {}; + lbValue key_ptr = lb_address_from_load_or_generate_local(p, key); key_ptr = lb_emit_conv(p, key_ptr, t_rawptr); - auto args = array_make(permanent_allocator(), 3); - args[0] = lb_emit_transmute(p, map, t_raw_map); - args[1] = lb_gen_map_info_ptr(p->module, map_type); - args[2] = key_ptr; + if (build_context.use_static_map_calls) { + lbValue map_get_proc = lb_get_map_get_proc_for_type(p->module, map_type); - lbValue ptr = lb_emit_runtime_call(p, "__dynamic_map_get", args); + auto args = array_make(permanent_allocator(), 2); + args[0] = lb_address_from_load_or_generate_local(p, map); + args[1] = key_ptr; + ptr = lb_emit_call(p, map_get_proc, args); + } else { + auto args = array_make(permanent_allocator(), 3); + args[0] = lb_emit_transmute(p, map, t_raw_map); + args[1] = lb_gen_map_info_ptr(p->module, map_type); + args[2] = key_ptr; + + ptr = lb_emit_runtime_call(p, "__dynamic_map_get", args); + } return lb_emit_conv(p, ptr, alloc_type_pointer(map_type->Map.value)); } @@ -1206,6 +1352,10 @@ WORKER_TASK_PROC(lb_llvm_function_pass_worker_proc) { lbProcedure *p = m->hasher_procs.entries[i].value; lb_run_function_pass_manager(default_function_pass_manager, p); } + for_array(i, m->map_get_procs.entries) { + lbProcedure *p = m->map_get_procs.entries[i].value; + lb_run_function_pass_manager(default_function_pass_manager, p); + } return 0; } diff --git a/src/llvm_backend.hpp b/src/llvm_backend.hpp index 6c7c2e392..f9fe6cff0 100644 --- a/src/llvm_backend.hpp +++ b/src/llvm_backend.hpp @@ -144,6 +144,7 @@ struct lbModule { PtrMap equal_procs; PtrMap hasher_procs; + PtrMap map_get_procs; u32 nested_type_name_guid; diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp index e1a926255..859542fb5 100644 --- a/src/llvm_backend_general.cpp +++ b/src/llvm_backend_general.cpp @@ -67,6 +67,7 @@ void lb_init_module(lbModule *m, Checker *c) { map_init(&m->function_type_map, a); map_init(&m->equal_procs, a); map_init(&m->hasher_procs, a); + map_init(&m->map_get_procs, a); array_init(&m->procedures_to_generate, a, 0, 1024); array_init(&m->missing_procedures_to_check, a, 0, 16); map_init(&m->debug_values, a); diff --git a/src/llvm_backend_stmt.cpp b/src/llvm_backend_stmt.cpp index 3e4846f02..6b83068ce 100644 --- a/src/llvm_backend_stmt.cpp +++ b/src/llvm_backend_stmt.cpp @@ -371,24 +371,30 @@ void lb_build_range_indexed(lbProcedure *p, lbValue expr, Type *val_type, lbValu } 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); + i64 size, len; + i64 elem_sz = type_size_of(type); + map_cell_size_and_len(type, &size, &len); - index = lb_emit_conv(p, index, t_uint); + index = lb_emit_conv(p, index, t_uintptr); - if (size == N*sz) { + if (size == len*elem_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)); + lbValue size_const = lb_const_int(p->module, t_uintptr, size); + lbValue len_const = lb_const_int(p->module, t_uintptr, len); + lbValue cell_index = lb_emit_arith(p, Token_Quo, index, len_const, t_uintptr); + lbValue data_index = lb_emit_arith(p, Token_Mod, index, len_const, t_uintptr); + + lbValue elems_ptr = lb_emit_conv(p, cells_ptr, t_uintptr); + lbValue cell_offset = lb_emit_arith(p, Token_Mul, size_const, cell_index, t_uintptr); + elems_ptr = lb_emit_arith(p, Token_Add, elems_ptr, cell_offset, t_uintptr); + + elems_ptr = lb_emit_conv(p, elems_ptr, alloc_type_pointer(type)); + return lb_emit_ptr_offset(p, elems_ptr, data_index); } diff --git a/src/llvm_backend_utility.cpp b/src/llvm_backend_utility.cpp index a3493f864..6d69021ce 100644 --- a/src/llvm_backend_utility.cpp +++ b/src/llvm_backend_utility.cpp @@ -1440,7 +1440,7 @@ lbValue lb_map_len(lbProcedure *p, lbValue value) { } lbValue lb_map_cap(lbProcedure *p, lbValue value) { - GB_ASSERT(is_type_map(value.type)); + GB_ASSERT_MSG(is_type_map(value.type) || are_types_identical(value.type, t_raw_map), "%s", type_to_string(value.type)); lbValue zero = lb_const_int(p->module, t_uintptr, 0); lbValue one = lb_const_int(p->module, t_uintptr, 1); @@ -1454,7 +1454,7 @@ lbValue lb_map_cap(lbProcedure *p, lbValue value) { } lbValue lb_map_data_uintptr(lbProcedure *p, lbValue value) { - GB_ASSERT(is_type_map(value.type)); + GB_ASSERT(is_type_map(value.type) || are_types_identical(value.type, t_raw_map)); lbValue data = lb_emit_struct_ev(p, value, 0); u64 mask_value = 0; if (build_context.word_size == 4) { diff --git a/src/main.cpp b/src/main.cpp index b75137613..3b0a599db 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -638,6 +638,7 @@ enum BuildFlagKind { BuildFlag_StrictStyleInitOnly, BuildFlag_ForeignErrorProcedures, BuildFlag_DisallowRTTI, + BuildFlag_UseStaticMapCalls, BuildFlag_Compact, BuildFlag_GlobalDefinitions, @@ -814,6 +815,8 @@ bool parse_build_flags(Array args) { add_flag(&build_flags, BuildFlag_DisallowRTTI, str_lit("disallow-rtti"), BuildFlagParam_None, Command__does_check); + add_flag(&build_flags, BuildFlag_UseStaticMapCalls, str_lit("use-static-map-calls"), BuildFlagParam_None, Command__does_check); + add_flag(&build_flags, BuildFlag_Compact, str_lit("compact"), BuildFlagParam_None, Command_query); add_flag(&build_flags, BuildFlag_GlobalDefinitions, str_lit("global-definitions"), BuildFlagParam_None, Command_query); @@ -1414,6 +1417,9 @@ bool parse_build_flags(Array args) { case BuildFlag_DisallowRTTI: build_context.disallow_rtti = true; break; + case BuildFlag_UseStaticMapCalls: + build_context.use_static_map_calls = true; + break; case BuildFlag_DefaultToNilAllocator: build_context.ODIN_DEFAULT_TO_NIL_ALLOCATOR = true; break; diff --git a/src/types.cpp b/src/types.cpp index ab82e87b8..74b192010 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -693,6 +693,7 @@ gb_global Type *t_raw_map_ptr = nullptr; gb_global Type *t_equal_proc = nullptr; gb_global Type *t_hasher_proc = nullptr; +gb_global Type *t_map_get_proc = nullptr; gb_global Type *t_objc_object = nullptr; gb_global Type *t_objc_selector = nullptr; -- cgit v1.2.3 From 1bcec3f7696243664d8bfefa24b4262d4f412755 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Wed, 9 Nov 2022 22:21:36 +0000 Subject: Change map internal calls to use a pointer --- src/llvm_backend.cpp | 8 ++++---- src/llvm_backend_expr.cpp | 4 ++-- src/llvm_backend_general.cpp | 4 ++-- 3 files changed, 8 insertions(+), 8 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 2b95c5b2f..e12a4c016 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -757,8 +757,8 @@ lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue return hashed_key; } -lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map, lbValue const &key) { - Type *map_type = base_type(map.type); +lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key) { + Type *map_type = base_type(type_deref(map_ptr.type)); GB_ASSERT(map_type->kind == Type_Map); lbValue ptr = {}; @@ -770,13 +770,13 @@ lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map, lbVa lbValue map_get_proc = lb_get_map_get_proc_for_type(p->module, map_type); auto args = array_make(permanent_allocator(), 2); - args[0] = lb_address_from_load_or_generate_local(p, map); + args[0] = map_ptr; args[1] = key_ptr; ptr = lb_emit_call(p, map_get_proc, args); } else { auto args = array_make(permanent_allocator(), 3); - args[0] = lb_emit_transmute(p, map, t_raw_map); + args[0] = lb_emit_transmute(p, lb_emit_load(p, map_ptr), t_raw_map); args[1] = lb_gen_map_info_ptr(p->module, map_type); args[2] = key_ptr; diff --git a/src/llvm_backend_expr.cpp b/src/llvm_backend_expr.cpp index 7e9aa3a78..05a9fdfbf 100644 --- a/src/llvm_backend_expr.cpp +++ b/src/llvm_backend_expr.cpp @@ -1423,9 +1423,9 @@ lbValue lb_build_binary_expr(lbProcedure *p, Ast *expr) { switch (rt->kind) { case Type_Map: { - lbValue map = right; + lbValue map_ptr = lb_address_from_load_or_generate_local(p, right); lbValue key = left; - lbValue ptr = lb_internal_dynamic_map_get_ptr(p, map, key); + lbValue ptr = lb_internal_dynamic_map_get_ptr(p, map_ptr, key); if (be->op.kind == Token_in) { return lb_emit_conv(p, lb_emit_comp_against_nil(p, Token_NotEq, ptr), t_bool); } else { diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp index 859542fb5..a0e4d80ba 100644 --- a/src/llvm_backend_general.cpp +++ b/src/llvm_backend_general.cpp @@ -418,7 +418,7 @@ lbValue lb_addr_get_ptr(lbProcedure *p, lbAddr const &addr) { switch (addr.kind) { case lbAddr_Map: - return lb_internal_dynamic_map_get_ptr(p, lb_emit_load(p, addr.addr), addr.map.key); + return lb_internal_dynamic_map_get_ptr(p, addr.addr, addr.map.key); case lbAddr_RelativePointer: { Type *rel_ptr = base_type(lb_addr_type(addr)); @@ -1075,7 +1075,7 @@ lbValue lb_addr_load(lbProcedure *p, lbAddr const &addr) { GB_ASSERT(map_type->kind == Type_Map); lbAddr v = lb_add_local_generated(p, map_type->Map.lookup_result_type, true); - lbValue ptr = lb_internal_dynamic_map_get_ptr(p, lb_emit_load(p, addr.addr), addr.map.key); + lbValue ptr = lb_internal_dynamic_map_get_ptr(p, addr.addr, addr.map.key); lbValue ok = lb_emit_conv(p, lb_emit_comp_against_nil(p, Token_NotEq, ptr), t_bool); lb_emit_store(p, lb_emit_struct_ep(p, v.addr, 1), ok); -- cgit v1.2.3 From 8852d090b61fab27f97787b37b7cbd5b63a52083 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Thu, 10 Nov 2022 12:46:53 +0000 Subject: Correct static map get; make get take a pointer to simplify compiler internals --- core/runtime/dynamic_map_internal.odin | 21 ++++++------ src/llvm_backend.cpp | 58 +++++++++++++++++++--------------- src/llvm_backend.hpp | 4 +-- src/llvm_backend_expr.cpp | 2 +- src/llvm_backend_proc.cpp | 4 +-- src/llvm_backend_type.cpp | 4 +-- src/llvm_backend_utility.cpp | 2 +- 7 files changed, 50 insertions(+), 45 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index f57dce885..aedd3f260 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -107,7 +107,7 @@ Map_Cell_Info :: struct { map_cell_info :: intrinsics.type_map_cell_info // Same as the above procedure but at runtime with the cell Map_Cell_Info value. -map_cell_index_dynamic :: #force_inline proc "contextless" (base: uintptr, info: ^Map_Cell_Info, index: uintptr) -> uintptr { +map_cell_index_dynamic :: #force_inline proc "contextless" (base: uintptr, #no_alias info: ^Map_Cell_Info, index: uintptr) -> uintptr { // Micro-optimize the common cases to save on integer division. elements_per_cell := uintptr(info.elements_per_cell) size_of_cell := uintptr(info.size_of_cell) @@ -355,13 +355,13 @@ map_alloc_dynamic :: proc "odin" (info: ^Map_Info, log2_capacity: uintptr, alloc // there is no type information. // // This procedure returns the address of the just inserted value. -map_insert_hash_dynamic :: proc "odin" (m: ^Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, ik: uintptr, iv: uintptr) -> (result: uintptr) { +map_insert_hash_dynamic :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, ik: uintptr, iv: uintptr) -> (result: uintptr) { + h := h pos := map_desired_position(m^, h) distance := uintptr(0) mask := (uintptr(1) << map_log2_cap(m^)) - 1 ks, vs, hs, sk, sv := map_kvh_data_dynamic(m^, info) - _, _ = sk, sv // Avoid redundant loads of these values size_of_k := info.ks.size_of_type @@ -376,7 +376,6 @@ map_insert_hash_dynamic :: proc "odin" (m: ^Raw_Map, #no_alias info: ^Map_Info, tk := map_cell_index_dynamic(sk, info.ks, 1) tv := map_cell_index_dynamic(sv, info.vs, 1) - h := h for { hp := &hs[pos] @@ -660,19 +659,19 @@ map_get :: proc "contextless" (m: $T/map[$K]$V, key: K) -> (stored_key: K, store } } -__dynamic_map_get_with_hash :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, key: rawptr) -> (ptr: rawptr) { +__dynamic_map_get_with_hash :: proc "contextless" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, key: rawptr) -> (ptr: rawptr) { if m.len == 0 { return nil } - pos := map_desired_position(m, h) + pos := map_desired_position(m^, h) distance := uintptr(0) - mask := (uintptr(1) << map_log2_cap(m)) - 1 - ks, vs, hs, _, _ := map_kvh_data_dynamic(m, info) + mask := (uintptr(1) << map_log2_cap(m^)) - 1 + ks, vs, hs, _, _ := map_kvh_data_dynamic(m^, info) for { element_hash := hs[pos] if map_hash_is_empty(element_hash) { return nil - } else if distance > map_probe_distance(m, element_hash, pos) { + } else if distance > map_probe_distance(m^, element_hash, pos) { return nil } else if element_hash == h && info.key_equal(key, rawptr(map_cell_index_dynamic(ks, info.ks, pos))) { return rawptr(map_cell_index_dynamic(vs, info.vs, pos)) @@ -682,7 +681,7 @@ __dynamic_map_get_with_hash :: proc "contextless" (m: Raw_Map, #no_alias info: ^ } } -__dynamic_map_get :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, key: rawptr) -> (ptr: rawptr) { +__dynamic_map_get :: proc "contextless" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, key: rawptr) -> (ptr: rawptr) { if m.len == 0 { return nil } @@ -693,7 +692,7 @@ __dynamic_map_get :: proc "contextless" (m: Raw_Map, #no_alias info: ^Map_Info, __dynamic_map_set :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, key, value: rawptr, loc := #caller_location) -> rawptr { hash := info.key_hasher(key, 0) - if found := __dynamic_map_get_with_hash(m^, info, hash, key); found != nil { + if found := __dynamic_map_get_with_hash(m, info, hash, key); found != nil { intrinsics.mem_copy_non_overlapping(found, value, info.vs.size_of_type) return found } diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index e12a4c016..c313bc825 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -140,7 +140,7 @@ lbContextData *lb_push_context_onto_stack(lbProcedure *p, lbAddr ctx) { } -lbValue lb_get_equal_proc_for_type(lbModule *m, Type *type) { +lbValue lb_equal_proc_for_type(lbModule *m, Type *type) { type = base_type(type); GB_ASSERT(is_type_comparable(type)); @@ -296,7 +296,7 @@ lbValue lb_simple_compare_hash(lbProcedure *p, Type *type, lbValue data, lbValue return lb_emit_runtime_call(p, "default_hasher_n", args); } -lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { +lbValue lb_hasher_proc_for_type(lbModule *m, Type *type) { type = core_type(type); GB_ASSERT_MSG(is_type_valid_for_keys(type), "%s", type_to_string(type)); @@ -343,7 +343,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { GB_ASSERT(type->Struct.offsets != nullptr); i64 offset = type->Struct.offsets[i]; Entity *field = type->Struct.fields[i]; - lbValue field_hasher = lb_get_hasher_proc_for_type(m, field->type); + lbValue field_hasher = lb_hasher_proc_for_type(m, field->type); lbValue ptr = lb_emit_ptr_offset(p, data, lb_const_int(m, t_uintptr, offset)); args[0] = ptr; @@ -356,7 +356,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { if (is_type_union_maybe_pointer(type)) { Type *v = type->Union.variants[0]; - lbValue variant_hasher = lb_get_hasher_proc_for_type(m, v); + lbValue variant_hasher = lb_hasher_proc_for_type(m, v); args[0] = data; args[1] = seed; @@ -379,7 +379,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { Type *v = type->Union.variants[i]; lbValue case_tag = lb_const_union_tag(p->module, type, v); - lbValue variant_hasher = lb_get_hasher_proc_for_type(m, v); + lbValue variant_hasher = lb_hasher_proc_for_type(m, v); args[0] = data; args[1] = seed; @@ -397,7 +397,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { lb_addr_store(p, pres, seed); auto args = array_make(permanent_allocator(), 2); - lbValue elem_hasher = lb_get_hasher_proc_for_type(m, type->Array.elem); + lbValue elem_hasher = lb_hasher_proc_for_type(m, type->Array.elem); auto loop_data = lb_loop_start(p, cast(isize)type->Array.count, t_i32); @@ -418,7 +418,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { lb_addr_store(p, res, seed); auto args = array_make(permanent_allocator(), 2); - lbValue elem_hasher = lb_get_hasher_proc_for_type(m, type->EnumeratedArray.elem); + lbValue elem_hasher = lb_hasher_proc_for_type(m, type->EnumeratedArray.elem); auto loop_data = lb_loop_start(p, cast(isize)type->EnumeratedArray.count, t_i32); @@ -454,7 +454,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) { } -lbValue lb_get_map_get_proc_for_type(lbModule *m, Type *type) { +lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) { GB_ASSERT(build_context.use_static_map_calls); type = base_type(type); GB_ASSERT(type->kind == Type_Map); @@ -468,7 +468,7 @@ lbValue lb_get_map_get_proc_for_type(lbModule *m, Type *type) { static u32 proc_index = 0; char buf[32] = {}; - isize n = gb_snprintf(buf, 32, "__$map_get%u", ++proc_index); + isize n = gb_snprintf(buf, 32, "__$map_get_%u", ++proc_index); char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1); String proc_name = make_string_c(str); @@ -489,9 +489,23 @@ lbValue lb_get_map_get_proc_for_type(lbModule *m, Type *type) { LLVMAddAttributeAtIndex(p->value, 1+1, nonnull_attr); LLVMAddAttributeAtIndex(p->value, 1+1, noalias_attr); + lbBlock *loop_block = lb_create_block(p, "loop"); + lbBlock *hash_block = lb_create_block(p, "hash"); + lbBlock *probe_block = lb_create_block(p, "probe"); + lbBlock *increment_block = lb_create_block(p, "increment"); + lbBlock *hash_compare_block = lb_create_block(p, "hash_compare"); + lbBlock *key_compare_block = lb_create_block(p, "key_compare"); + lbBlock *value_block = lb_create_block(p, "value"); + lbBlock *nil_block = lb_create_block(p, "nil"); + map_ptr = lb_emit_conv(p, map_ptr, t_raw_map_ptr); lbValue map = lb_emit_load(p, map_ptr); + lbValue length = lb_map_len(p, map); + + lb_emit_if(p, lb_emit_comp(p, Token_CmpEq, length, lb_const_nil(m, t_int)), nil_block, hash_block); + lb_start_block(p, hash_block); + key_ptr = lb_emit_conv(p, key_ptr, alloc_type_pointer(type->Map.key)); lbValue key = lb_emit_load(p, key_ptr); @@ -521,16 +535,8 @@ lbValue lb_get_map_get_proc_for_type(lbModule *m, Type *type) { // lbValue res = // LLVMBuildRet(p->builder, res.value); - lbBlock *loop = lb_create_block(p, "loop"); - lbBlock *probe_block = lb_create_block(p, "probe"); - lbBlock *increment_block = lb_create_block(p, "increment"); - lbBlock *hash_compare_block = lb_create_block(p, "hash_compare"); - lbBlock *key_compare_block = lb_create_block(p, "key_compare"); - lbBlock *value_block = lb_create_block(p, "value"); - lbBlock *nil_block = lb_create_block(p, "nil"); - - lb_emit_jump(p, loop); - lb_start_block(p, loop); + lb_emit_jump(p, loop_block); + lb_start_block(p, loop_block); lbValue element_hash = lb_emit_load(p, lb_emit_ptr_offset(p, hs, lb_addr_load(p, pos))); { @@ -577,7 +583,7 @@ lbValue lb_get_map_get_proc_for_type(lbModule *m, Type *type) { lb_addr_store(p, pos, pp); lb_emit_increment(p, distance.addr); } - lb_emit_jump(p, loop); + lb_emit_jump(p, loop_block); lb_start_block(p, nil_block); { @@ -678,8 +684,8 @@ lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type) { LLVMValueRef const_values[4] = {}; const_values[0] = key_cell_info; const_values[1] = value_cell_info; - const_values[2] = lb_get_hasher_proc_for_type(m, map_type->Map.key).value; - const_values[3] = lb_get_equal_proc_for_type(m, map_type->Map.key).value; + const_values[2] = lb_hasher_proc_for_type(m, map_type->Map.key).value; + const_values[3] = lb_equal_proc_for_type(m, map_type->Map.key).value; LLVMValueRef llvm_res = llvm_const_named_struct(m, t_map_info, const_values, gb_count_of(const_values)); lbValue res = {llvm_res, t_map_info}; @@ -746,7 +752,7 @@ lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue lbValue hashed_key = lb_const_hash(p->module, key, key_type); if (hashed_key.value == nullptr) { - lbValue hasher = lb_get_hasher_proc_for_type(p->module, key_type); + lbValue hasher = lb_hasher_proc_for_type(p->module, key_type); auto args = array_make(permanent_allocator(), 2); args[0] = key_ptr; @@ -767,16 +773,16 @@ lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, key_ptr = lb_emit_conv(p, key_ptr, t_rawptr); if (build_context.use_static_map_calls) { - lbValue map_get_proc = lb_get_map_get_proc_for_type(p->module, map_type); + lbValue map_get_proc = lb_map_get_proc_for_type(p->module, map_type); auto args = array_make(permanent_allocator(), 2); - args[0] = map_ptr; + args[0] = lb_emit_conv(p, map_ptr, t_rawptr); args[1] = key_ptr; ptr = lb_emit_call(p, map_get_proc, args); } else { auto args = array_make(permanent_allocator(), 3); - args[0] = lb_emit_transmute(p, lb_emit_load(p, map_ptr), t_raw_map); + args[0] = lb_emit_transmute(p, map_ptr, t_raw_map_ptr); args[1] = lb_gen_map_info_ptr(p->module, map_type); args[2] = key_ptr; diff --git a/src/llvm_backend.hpp b/src/llvm_backend.hpp index f9fe6cff0..c4333e949 100644 --- a/src/llvm_backend.hpp +++ b/src/llvm_backend.hpp @@ -463,8 +463,8 @@ lbValue lb_emit_source_code_location_const(lbProcedure *p, String const &procedu lbValue lb_handle_param_value(lbProcedure *p, Type *parameter_type, ParameterValue const ¶m_value, TokenPos const &pos); -lbValue lb_get_equal_proc_for_type(lbModule *m, Type *type); -lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type); +lbValue lb_equal_proc_for_type(lbModule *m, Type *type); +lbValue lb_hasher_proc_for_type(lbModule *m, Type *type); lbValue lb_emit_conv(lbProcedure *p, lbValue value, Type *t); LLVMMetadataRef lb_debug_type(lbModule *m, Type *type); diff --git a/src/llvm_backend_expr.cpp b/src/llvm_backend_expr.cpp index 05a9fdfbf..aee87242c 100644 --- a/src/llvm_backend_expr.cpp +++ b/src/llvm_backend_expr.cpp @@ -2215,7 +2215,7 @@ lbValue lb_compare_records(lbProcedure *p, TokenKind op_kind, lbValue left, lbVa args[2] = lb_const_int(p->module, t_int, type_size_of(type)); res = lb_emit_runtime_call(p, "memory_equal", args); } else { - lbValue value = lb_get_equal_proc_for_type(p->module, type); + lbValue value = lb_equal_proc_for_type(p->module, type); auto args = array_make(permanent_allocator(), 2); args[0] = lb_emit_conv(p, left_ptr, t_rawptr); args[1] = lb_emit_conv(p, right_ptr, t_rawptr); diff --git a/src/llvm_backend_proc.cpp b/src/llvm_backend_proc.cpp index 6d7d7eecb..4b0323855 100644 --- a/src/llvm_backend_proc.cpp +++ b/src/llvm_backend_proc.cpp @@ -2319,10 +2319,10 @@ lbValue lb_build_builtin_proc(lbProcedure *p, Ast *expr, TypeAndValue const &tv, case BuiltinProc_type_equal_proc: - return lb_get_equal_proc_for_type(p->module, ce->args[0]->tav.type); + return lb_equal_proc_for_type(p->module, ce->args[0]->tav.type); case BuiltinProc_type_hasher_proc: - return lb_get_hasher_proc_for_type(p->module, ce->args[0]->tav.type); + return lb_hasher_proc_for_type(p->module, ce->args[0]->tav.type); case BuiltinProc_type_map_info: return lb_gen_map_info_ptr(p->module, ce->args[0]->tav.type); diff --git a/src/llvm_backend_type.cpp b/src/llvm_backend_type.cpp index 26f89f985..307d9304b 100644 --- a/src/llvm_backend_type.cpp +++ b/src/llvm_backend_type.cpp @@ -666,7 +666,7 @@ void lb_setup_type_info_data(lbProcedure *p) { // NOTE(bill): Setup type_info da } if (is_type_comparable(t) && !is_type_simple_compare(t)) { - vals[3] = lb_get_equal_proc_for_type(m, t).value; + vals[3] = lb_equal_proc_for_type(m, t).value; } vals[4] = lb_const_bool(m, t_bool, t->Union.custom_align != 0).value; @@ -702,7 +702,7 @@ void lb_setup_type_info_data(lbProcedure *p) { // NOTE(bill): Setup type_info da vals[6] = is_raw_union.value; vals[7] = is_custom_align.value; if (is_type_comparable(t) && !is_type_simple_compare(t)) { - vals[8] = lb_get_equal_proc_for_type(m, t).value; + vals[8] = lb_equal_proc_for_type(m, t).value; } diff --git a/src/llvm_backend_utility.cpp b/src/llvm_backend_utility.cpp index 6d69021ce..30c531d71 100644 --- a/src/llvm_backend_utility.cpp +++ b/src/llvm_backend_utility.cpp @@ -1434,7 +1434,7 @@ lbValue lb_dynamic_array_allocator(lbProcedure *p, lbValue da) { } lbValue lb_map_len(lbProcedure *p, lbValue value) { - GB_ASSERT(is_type_map(value.type)); + GB_ASSERT_MSG(is_type_map(value.type) || are_types_identical(value.type, t_raw_map), "%s", type_to_string(value.type)); lbValue len = lb_emit_struct_ev(p, value, 1); return lb_emit_conv(p, len, t_int); } -- cgit v1.2.3 From 033525fe13762237a17ba1f08c59a346ff3cf326 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 11 Nov 2022 11:10:26 +0000 Subject: Force inline of hasher proc where possible --- src/llvm_backend.cpp | 39 +++++++++++++++++++++++++++++++-------- 1 file changed, 31 insertions(+), 8 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index c313bc825..79db03f85 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -166,6 +166,9 @@ lbValue lb_equal_proc_for_type(lbModule *m, Type *type) { map_set(&m->equal_procs, type, p); lb_begin_procedure_body(p); + lb_add_attribute_to_proc(m, p->value, "readonly"); + lb_add_attribute_to_proc(m, p->value, "nounwind"); + LLVMValueRef x = LLVMGetParam(p->value, 0); LLVMValueRef y = LLVMGetParam(p->value, 1); x = LLVMBuildPointerCast(p->builder, x, ptr_type, ""); @@ -173,6 +176,8 @@ lbValue lb_equal_proc_for_type(lbModule *m, Type *type) { lbValue lhs = {x, pt}; lbValue rhs = {y, pt}; + lb_add_proc_attribute_at_index(p, 1+0, "nonnull"); + lb_add_proc_attribute_at_index(p, 1+1, "nonnull"); lbBlock *block_same_ptr = lb_create_block(p, "same_ptr"); lbBlock *block_diff_ptr = lb_create_block(p, "diff_ptr"); @@ -296,6 +301,10 @@ lbValue lb_simple_compare_hash(lbProcedure *p, Type *type, lbValue data, lbValue return lb_emit_runtime_call(p, "default_hasher_n", args); } +void lb_add_callsite_force_inline(lbProcedure *p, lbValue ret_value) { + LLVMAddCallSiteAttribute(ret_value.value, LLVMAttributeIndex_FunctionIndex, lb_create_enum_attribute(p->module->ctx, "alwaysinline")); +} + lbValue lb_hasher_proc_for_type(lbModule *m, Type *type) { type = core_type(type); GB_ASSERT_MSG(is_type_valid_for_keys(type), "%s", type_to_string(type)); @@ -320,16 +329,20 @@ lbValue lb_hasher_proc_for_type(lbModule *m, Type *type) { lb_begin_procedure_body(p); defer (lb_end_procedure_body(p)); + lb_add_attribute_to_proc(m, p->value, "readonly"); + lb_add_attribute_to_proc(m, p->value, "nounwind"); + LLVMValueRef x = LLVMGetParam(p->value, 0); LLVMValueRef y = LLVMGetParam(p->value, 1); lbValue data = {x, t_rawptr}; lbValue seed = {y, t_uintptr}; - LLVMAttributeRef nonnull_attr = lb_create_enum_attribute(m->ctx, "nonnull"); - LLVMAddAttributeAtIndex(p->value, 1+0, nonnull_attr); + lb_add_proc_attribute_at_index(p, 1+0, "nonnull"); + lb_add_proc_attribute_at_index(p, 1+0, "readonly"); if (is_type_simple_compare(type)) { lbValue res = lb_simple_compare_hash(p, type, data, seed); + lb_add_callsite_force_inline(p, res); LLVMBuildRet(p->builder, res.value); return {p->value, p->type}; } @@ -361,6 +374,7 @@ lbValue lb_hasher_proc_for_type(lbModule *m, Type *type) { args[0] = data; args[1] = seed; lbValue res = lb_emit_call(p, variant_hasher, args); + lb_add_callsite_force_inline(p, res); LLVMBuildRet(p->builder, res.value); } @@ -439,12 +453,14 @@ lbValue lb_hasher_proc_for_type(lbModule *m, Type *type) { args[0] = data; args[1] = seed; lbValue res = lb_emit_runtime_call(p, "default_hasher_cstring", args); + lb_add_callsite_force_inline(p, res); LLVMBuildRet(p->builder, res.value); } else if (is_type_string(type)) { auto args = array_make(permanent_allocator(), 2); args[0] = data; args[1] = seed; lbValue res = lb_emit_runtime_call(p, "default_hasher_string", args); + lb_add_callsite_force_inline(p, res); LLVMBuildRet(p->builder, res.value); } else { GB_PANIC("Unhandled type for hasher: %s", type_to_string(type)); @@ -477,17 +493,21 @@ lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) { lb_begin_procedure_body(p); defer (lb_end_procedure_body(p)); + lb_add_attribute_to_proc(m, p->value, "readonly"); + lb_add_attribute_to_proc(m, p->value, "nounwind"); + LLVMValueRef x = LLVMGetParam(p->value, 0); LLVMValueRef y = LLVMGetParam(p->value, 1); lbValue map_ptr = {x, t_rawptr}; lbValue key_ptr = {y, t_rawptr}; - LLVMAttributeRef nonnull_attr = lb_create_enum_attribute(m->ctx, "nonnull"); - LLVMAttributeRef noalias_attr = lb_create_enum_attribute(m->ctx, "noalias"); - LLVMAddAttributeAtIndex(p->value, 1+0, nonnull_attr); - LLVMAddAttributeAtIndex(p->value, 1+0, noalias_attr); - LLVMAddAttributeAtIndex(p->value, 1+1, nonnull_attr); - LLVMAddAttributeAtIndex(p->value, 1+1, noalias_attr); + lb_add_proc_attribute_at_index(p, 1+0, "nonnull"); + lb_add_proc_attribute_at_index(p, 1+0, "noalias"); + lb_add_proc_attribute_at_index(p, 1+0, "readonly"); + + lb_add_proc_attribute_at_index(p, 1+1, "nonnull"); + lb_add_proc_attribute_at_index(p, 1+1, "noalias"); + lb_add_proc_attribute_at_index(p, 1+1, "readonly"); lbBlock *loop_block = lb_create_block(p, "loop"); lbBlock *hash_block = lb_create_block(p, "hash"); @@ -848,6 +868,8 @@ lbProcedure *lb_create_startup_type_info(lbModule *m) { p->is_startup = true; LLVMSetLinkage(p->value, LLVMInternalLinkage); + lb_add_attribute_to_proc(m, p->value, "nounwind"); + lb_begin_procedure_body(p); lb_setup_type_info_data(p); @@ -872,6 +894,7 @@ lbProcedure *lb_create_objc_names(lbModule *main_module) { } Type *proc_type = alloc_type_proc(nullptr, nullptr, 0, nullptr, 0, false, ProcCC_CDecl); lbProcedure *p = lb_create_dummy_procedure(main_module, str_lit("__$init_objc_names"), proc_type); + lb_add_attribute_to_proc(p->module, p->value, "nounwind"); p->is_startup = true; return p; } -- cgit v1.2.3 From 0d37da54b4937a19bf581dc001271eb16ac86daf Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 11 Nov 2022 11:41:28 +0000 Subject: Add minor optimization for `lb_map_cell_index_static` --- src/llvm_backend.cpp | 3 --- src/llvm_backend_stmt.cpp | 14 +++++++++++--- 2 files changed, 11 insertions(+), 6 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 79db03f85..ee3d36896 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -552,9 +552,6 @@ lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) { vs = lb_emit_conv(p, vs, alloc_type_pointer(type->Map.value)); hs = lb_emit_conv(p, hs, alloc_type_pointer(t_uintptr)); - // lbValue res = - // LLVMBuildRet(p->builder, res.value); - lb_emit_jump(p, loop_block); lb_start_block(p, loop_block); diff --git a/src/llvm_backend_stmt.cpp b/src/llvm_backend_stmt.cpp index ec7a162cb..c8f244181 100644 --- a/src/llvm_backend_stmt.cpp +++ b/src/llvm_backend_stmt.cpp @@ -382,12 +382,20 @@ lbValue lb_map_cell_index_static(lbProcedure *p, Type *type, lbValue cells_ptr, return lb_emit_ptr_offset(p, elems_ptr, index); } - // TOOD(bill): N power of two optimization to use >> and & + lbValue cell_index = {}; + lbValue data_index = {}; lbValue size_const = lb_const_int(p->module, t_uintptr, size); lbValue len_const = lb_const_int(p->module, t_uintptr, len); - lbValue cell_index = lb_emit_arith(p, Token_Quo, index, len_const, t_uintptr); - lbValue data_index = lb_emit_arith(p, Token_Mod, index, len_const, t_uintptr); + + if (is_power_of_two(len)) { + u64 log2_len = floor_log2(cast(u64)len); + cell_index = log2_len == 0 ? index : lb_emit_arith(p, Token_Shr, index, lb_const_int(p->module, t_uintptr, log2_len), t_uintptr); + data_index = lb_emit_arith(p, Token_And, index, lb_const_int(p->module, t_uintptr, len-1), t_uintptr); + } else { + cell_index = lb_emit_arith(p, Token_Quo, index, len_const, t_uintptr); + data_index = lb_emit_arith(p, Token_Mod, index, len_const, t_uintptr); + } lbValue elems_ptr = lb_emit_conv(p, cells_ptr, t_uintptr); lbValue cell_offset = lb_emit_arith(p, Token_Mul, size_const, cell_index, t_uintptr); -- cgit v1.2.3 From a0bd31646bd5ab0fa4b8e3e8766d59f70c5f0d4c Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 11 Nov 2022 13:02:23 +0000 Subject: Make `map` get internal calls take the hash value rather than compute it internally --- core/runtime/dynamic_map_internal.odin | 21 +++++++++------------ src/checker.cpp | 4 ++-- src/llvm_backend.cpp | 26 ++++++++++++++------------ 3 files changed, 25 insertions(+), 26 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index 007df4365..65f883c7c 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -665,7 +665,8 @@ map_get :: proc "contextless" (m: $T/map[$K]$V, key: K) -> (stored_key: K, store } } -__dynamic_map_get_with_hash :: proc "contextless" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, key: rawptr) -> (ptr: rawptr) { +// IMPORTANT: USED WITHIN THE COMPILER +__dynamic_map_get :: proc "contextless" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, h: Map_Hash, key: rawptr) -> (ptr: rawptr) { if m.len == 0 { return nil } @@ -687,28 +688,24 @@ __dynamic_map_get_with_hash :: proc "contextless" (#no_alias m: ^Raw_Map, #no_al } } -// IMPORTANT: USED WITHIN THE COMPILER -__dynamic_map_get :: proc "contextless" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, key: rawptr) -> (ptr: rawptr) { - if m.len == 0 { - return nil +__dynamic_map_check_grow :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, loc := #caller_location) -> Allocator_Error { + if m.len + 1 >= map_resize_threshold(m^) { + return map_grow_dynamic(m, info, loc) } - h := info.key_hasher(key, 0) - return __dynamic_map_get_with_hash(m, info, h, key) + return nil } // IMPORTANT: USED WITHIN THE COMPILER __dynamic_map_set :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, key, value: rawptr, loc := #caller_location) -> rawptr { hash := info.key_hasher(key, 0) - if found := __dynamic_map_get_with_hash(m, info, hash, key); found != nil { + if found := __dynamic_map_get(m, info, hash, key); found != nil { intrinsics.mem_copy_non_overlapping(found, value, info.vs.size_of_type) return found } - if m.len + 1 >= map_resize_threshold(m^) { - if err := map_grow_dynamic(m, info, loc); err != nil { - return nil - } + if __dynamic_map_check_grow(m, info, loc) != nil { + return nil } result := map_insert_hash_dynamic(m, info, hash, uintptr(key), uintptr(value)) diff --git a/src/checker.cpp b/src/checker.cpp index d48b37b26..0c23f2627 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -927,8 +927,8 @@ void init_universal(void) { Type *hasher_args[2] = {t_rawptr, t_uintptr}; t_hasher_proc = alloc_type_proc_from_types(hasher_args, 2, t_uintptr, false, ProcCC_Contextless); - Type *map_get_args[2] = {/*map*/t_rawptr, /*key*/t_rawptr}; - t_map_get_proc = alloc_type_proc_from_types(map_get_args, 2, t_rawptr, false, ProcCC_Contextless); + Type *map_get_args[3] = {/*map*/t_rawptr, /*hash*/t_uintptr, /*key*/t_rawptr}; + t_map_get_proc = alloc_type_proc_from_types(map_get_args, 3, t_rawptr, false, ProcCC_Contextless); } diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index ee3d36896..f0a123e5e 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -498,16 +498,18 @@ lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) { LLVMValueRef x = LLVMGetParam(p->value, 0); LLVMValueRef y = LLVMGetParam(p->value, 1); + LLVMValueRef z = LLVMGetParam(p->value, 2); lbValue map_ptr = {x, t_rawptr}; - lbValue key_ptr = {y, t_rawptr}; + lbValue h = {y, t_uintptr}; + lbValue key_ptr = {z, t_rawptr}; lb_add_proc_attribute_at_index(p, 1+0, "nonnull"); lb_add_proc_attribute_at_index(p, 1+0, "noalias"); lb_add_proc_attribute_at_index(p, 1+0, "readonly"); - lb_add_proc_attribute_at_index(p, 1+1, "nonnull"); - lb_add_proc_attribute_at_index(p, 1+1, "noalias"); - lb_add_proc_attribute_at_index(p, 1+1, "readonly"); + lb_add_proc_attribute_at_index(p, 1+2, "nonnull"); + lb_add_proc_attribute_at_index(p, 1+2, "noalias"); + lb_add_proc_attribute_at_index(p, 1+2, "readonly"); lbBlock *loop_block = lb_create_block(p, "loop"); lbBlock *hash_block = lb_create_block(p, "hash"); @@ -529,7 +531,6 @@ lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) { key_ptr = lb_emit_conv(p, key_ptr, alloc_type_pointer(type->Map.key)); lbValue key = lb_emit_load(p, key_ptr); - lbValue h = lb_gen_map_key_hash(p, key, type->Map.key, nullptr); lbAddr pos = lb_add_local_generated(p, t_uintptr, false); lbAddr distance = lb_add_local_generated(p, t_uintptr, true); lbValue capacity = lb_map_cap(p, map); @@ -785,23 +786,24 @@ lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, GB_ASSERT(map_type->kind == Type_Map); lbValue ptr = {}; - - lbValue key_ptr = lb_address_from_load_or_generate_local(p, key); - key_ptr = lb_emit_conv(p, key_ptr, t_rawptr); + lbValue key_ptr = {}; + lbValue hash = lb_gen_map_key_hash(p, key, map_type->Map.key, &key_ptr); if (build_context.use_static_map_calls) { lbValue map_get_proc = lb_map_get_proc_for_type(p->module, map_type); - auto args = array_make(permanent_allocator(), 2); + auto args = array_make(permanent_allocator(), 3); args[0] = lb_emit_conv(p, map_ptr, t_rawptr); - args[1] = key_ptr; + args[1] = hash; + args[2] = key_ptr; ptr = lb_emit_call(p, map_get_proc, args); } else { - auto args = array_make(permanent_allocator(), 3); + auto args = array_make(permanent_allocator(), 4); args[0] = lb_emit_transmute(p, map_ptr, t_raw_map_ptr); args[1] = lb_gen_map_info_ptr(p->module, map_type); - args[2] = key_ptr; + args[2] = hash; + args[3] = key_ptr; ptr = lb_emit_runtime_call(p, "__dynamic_map_get", args); } -- cgit v1.2.3 From d2701d8b13bce7ac684c215e5ec4bd1dd65f670a Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 11 Nov 2022 13:04:38 +0000 Subject: Make `__dynamic_map_set` take the `hash` rather than compute it internally --- src/llvm_backend.cpp | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index f0a123e5e..5306ed35e 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -815,17 +815,19 @@ void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, map_type = base_type(map_type); GB_ASSERT(map_type->kind == Type_Map); - lbValue key_ptr = lb_address_from_load_or_generate_local(p, map_key); + lbValue key_ptr = {}; + lbValue hash = lb_gen_map_key_hash(p, map_key, map_type->Map.key, &key_ptr); lbValue v = lb_emit_conv(p, map_value, map_type->Map.value); lbValue value_ptr = lb_address_from_load_or_generate_local(p, v); - auto args = array_make(permanent_allocator(), 5); + auto args = array_make(permanent_allocator(), 6); args[0] = lb_emit_conv(p, map_ptr, t_raw_map_ptr); args[1] = lb_gen_map_info_ptr(p->module, map_type); - args[2] = lb_emit_conv(p, key_ptr, t_rawptr); - args[3] = lb_emit_conv(p, value_ptr, t_rawptr); - args[4] = lb_emit_source_code_location_as_global(p, node); + args[2] = hash; + args[3] = lb_emit_conv(p, key_ptr, t_rawptr); + args[4] = lb_emit_conv(p, value_ptr, t_rawptr); + args[5] = lb_emit_source_code_location_as_global(p, node); lb_emit_runtime_call(p, "__dynamic_map_set", args); } -- cgit v1.2.3 From 16fc96101049ef884401ab6182ea860390abd6a9 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 11 Nov 2022 14:45:22 +0000 Subject: Begin work on map static set --- core/runtime/dynamic_map_internal.odin | 4 +- src/check_expr.cpp | 52 +++++++---- src/checker.cpp | 9 +- src/llvm_backend.cpp | 162 ++++++++++++++++++++++++++++++--- src/llvm_backend.hpp | 3 +- src/llvm_backend_const.cpp | 17 +++- src/llvm_backend_expr.cpp | 2 +- src/llvm_backend_general.cpp | 3 +- src/llvm_backend_utility.cpp | 7 ++ src/types.cpp | 1 + 10 files changed, 218 insertions(+), 42 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/core/runtime/dynamic_map_internal.odin b/core/runtime/dynamic_map_internal.odin index 65f883c7c..9721340f6 100644 --- a/core/runtime/dynamic_map_internal.odin +++ b/core/runtime/dynamic_map_internal.odin @@ -696,9 +696,7 @@ __dynamic_map_check_grow :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: } // IMPORTANT: USED WITHIN THE COMPILER -__dynamic_map_set :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, key, value: rawptr, loc := #caller_location) -> rawptr { - hash := info.key_hasher(key, 0) - +__dynamic_map_set :: proc "odin" (#no_alias m: ^Raw_Map, #no_alias info: ^Map_Info, hash: Map_Hash, key, value: rawptr, loc := #caller_location) -> rawptr { if found := __dynamic_map_get(m, info, hash, key); found != nil { intrinsics.mem_copy_non_overlapping(found, value, info.vs.size_of_type) return found diff --git a/src/check_expr.cpp b/src/check_expr.cpp index 045b22ca2..c58aac609 100644 --- a/src/check_expr.cpp +++ b/src/check_expr.cpp @@ -285,6 +285,37 @@ void error_operand_no_value(Operand *o) { } } +void add_map_get_dependencies(CheckerContext *c) { + if (build_context.use_static_map_calls) { + add_package_dependency(c, "runtime", "map_desired_position"); + add_package_dependency(c, "runtime", "map_probe_distance"); + } else { + add_package_dependency(c, "runtime", "__dynamic_map_get"); + } +} + +void add_map_set_dependencies(CheckerContext *c) { + init_core_source_code_location(c->checker); + + if (t_map_set_proc == nullptr) { + Type *map_set_args[5] = {/*map*/t_rawptr, /*hash*/t_uintptr, /*key*/t_rawptr, /*value*/t_rawptr, /*#caller_location*/t_source_code_location}; + t_map_set_proc = alloc_type_proc_from_types(map_set_args, gb_count_of(map_set_args), t_rawptr, false, ProcCC_Odin); + } + + if (build_context.use_static_map_calls) { + add_package_dependency(c, "runtime", "__dynamic_map_check_grow"); + add_package_dependency(c, "runtime", "map_insert_hash_dynamic"); + } else { + add_package_dependency(c, "runtime", "__dynamic_map_set"); + } +} + +void add_map_reserve_dependencies(CheckerContext *c) { + init_core_source_code_location(c->checker); + add_package_dependency(c, "runtime", "__dynamic_map_reserve"); +} + + void check_scope_decls(CheckerContext *c, Slice const &nodes, isize reserve_size) { Scope *s = c->scope; @@ -3244,12 +3275,7 @@ void check_binary_expr(CheckerContext *c, Operand *x, Ast *node, Type *type_hint check_assignment(c, x, yt->Map.key, str_lit("map 'not_in'")); } - if (build_context.use_static_map_calls) { - add_package_dependency(c, "runtime", "map_desired_position"); - add_package_dependency(c, "runtime", "map_probe_distance"); - } else { - add_package_dependency(c, "runtime", "__dynamic_map_get"); - } + add_map_get_dependencies(c); } else if (is_type_bit_set(rhs_type)) { Type *yt = base_type(rhs_type); @@ -8560,8 +8586,8 @@ ExprKind check_compound_literal(CheckerContext *c, Operand *o, Ast *node, Type * if (build_context.no_dynamic_literals && cl->elems.count) { error(node, "Compound literals of dynamic types have been disabled"); } else { - add_package_dependency(c, "runtime", "__dynamic_map_reserve"); - add_package_dependency(c, "runtime", "__dynamic_map_set"); + add_map_reserve_dependencies(c); + add_map_set_dependencies(c); } break; } @@ -8997,14 +9023,8 @@ ExprKind check_index_expr(CheckerContext *c, Operand *o, Ast *node, Type *type_h o->type = t->Map.value; o->expr = node; - - add_package_dependency(c, "runtime", "__dynamic_map_set"); - if (build_context.use_static_map_calls) { - add_package_dependency(c, "runtime", "map_desired_position"); - add_package_dependency(c, "runtime", "map_probe_distance"); - } else { - add_package_dependency(c, "runtime", "__dynamic_map_get"); - } + add_map_get_dependencies(c); + add_map_set_dependencies(c); return Expr_Expr; } diff --git a/src/checker.cpp b/src/checker.cpp index 0c23f2627..4d1ef4614 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -922,14 +922,13 @@ void init_universal(void) { { Type *equal_args[2] = {t_rawptr, t_rawptr}; - t_equal_proc = alloc_type_proc_from_types(equal_args, 2, t_bool, false, ProcCC_Contextless); + t_equal_proc = alloc_type_proc_from_types(equal_args, gb_count_of(equal_args), t_bool, false, ProcCC_Contextless); Type *hasher_args[2] = {t_rawptr, t_uintptr}; - t_hasher_proc = alloc_type_proc_from_types(hasher_args, 2, t_uintptr, false, ProcCC_Contextless); + t_hasher_proc = alloc_type_proc_from_types(hasher_args, gb_count_of(hasher_args), t_uintptr, false, ProcCC_Contextless); Type *map_get_args[3] = {/*map*/t_rawptr, /*hash*/t_uintptr, /*key*/t_rawptr}; - t_map_get_proc = alloc_type_proc_from_types(map_get_args, 3, t_rawptr, false, ProcCC_Contextless); - + t_map_get_proc = alloc_type_proc_from_types(map_get_args, gb_count_of(map_get_args), t_rawptr, false, ProcCC_Contextless); } // Constants @@ -2844,7 +2843,7 @@ void init_core_source_code_location(Checker *c) { return; } t_source_code_location = find_core_type(c, str_lit("Source_Code_Location")); - t_source_code_location_ptr = alloc_type_pointer(t_allocator); + t_source_code_location_ptr = alloc_type_pointer(t_source_code_location); } void init_core_map_type(Checker *c) { diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 5306ed35e..4c34a56e9 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -484,7 +484,7 @@ lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) { static u32 proc_index = 0; char buf[32] = {}; - isize n = gb_snprintf(buf, 32, "__$map_get_%u", ++proc_index); + isize n = gb_snprintf(buf, 32, "__$map_get-%u", ++proc_index); char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1); String proc_name = make_string_c(str); @@ -613,6 +613,129 @@ lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) { return {p->value, p->type}; } +void lb_debug_print(lbProcedure *p, String const &str) { + auto args = array_make(heap_allocator(), 1); + args[0] = lb_const_string(p->module, str); + lb_emit_runtime_call(p, "print_string", args); +} + +lbValue lb_map_set_proc_for_type(lbModule *m, Type *type) { + GB_ASSERT(build_context.use_static_map_calls); + type = base_type(type); + GB_ASSERT(type->kind == Type_Map); + + + lbProcedure **found = map_get(&m->map_set_procs, type); + if (found) { + GB_ASSERT(*found != nullptr); + return {(*found)->value, (*found)->type}; + } + static u32 proc_index = 0; + + char buf[32] = {}; + isize n = gb_snprintf(buf, 32, "__$map_set-%u", ++proc_index); + char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1); + String proc_name = make_string_c(str); + + lbProcedure *p = lb_create_dummy_procedure(m, proc_name, t_map_set_proc); + map_set(&m->map_set_procs, type, p); + lb_begin_procedure_body(p); + defer (lb_end_procedure_body(p)); + + lb_add_attribute_to_proc(m, p->value, "nounwind"); + lb_add_attribute_to_proc(m, p->value, "noinline"); + + lbValue map_ptr = {LLVMGetParam(p->value, 0), t_rawptr}; + lbValue hash = {LLVMGetParam(p->value, 1), t_uintptr}; + lbValue key_ptr = {LLVMGetParam(p->value, 2), t_rawptr}; + lbValue value_ptr = {LLVMGetParam(p->value, 3), t_rawptr}; + lbValue location_ptr = {LLVMGetParam(p->value, 4), t_source_code_location_ptr}; + + map_ptr = lb_emit_conv(p, map_ptr, alloc_type_pointer(type)); + key_ptr = lb_emit_conv(p, key_ptr, alloc_type_pointer(type->Map.key)); + + lb_add_proc_attribute_at_index(p, 1+0, "nonnull"); + lb_add_proc_attribute_at_index(p, 1+0, "noalias"); + + lb_add_proc_attribute_at_index(p, 1+2, "nonnull"); + if (!are_types_identical(type->Map.key, type->Map.value)) { + lb_add_proc_attribute_at_index(p, 1+2, "noalias"); + } + lb_add_proc_attribute_at_index(p, 1+2, "readonly"); + + lb_add_proc_attribute_at_index(p, 1+3, "nonnull"); + if (!are_types_identical(type->Map.key, type->Map.value)) { + lb_add_proc_attribute_at_index(p, 1+3, "noalias"); + } + lb_add_proc_attribute_at_index(p, 1+3, "readonly"); + + lb_add_proc_attribute_at_index(p, 1+4, "nonnull"); + lb_add_proc_attribute_at_index(p, 1+4, "noalias"); + lb_add_proc_attribute_at_index(p, 1+4, "readonly"); + + //// + lbValue found_ptr = {}; + { + lbValue map_get_proc = lb_map_get_proc_for_type(m, type); + + auto args = array_make(permanent_allocator(), 3); + args[0] = lb_emit_conv(p, map_ptr, t_rawptr); + args[1] = hash; + args[2] = key_ptr; + + found_ptr = lb_emit_call(p, map_get_proc, args); + } + + + lbBlock *found_block = lb_create_block(p, "found"); + lbBlock *check_grow_block = lb_create_block(p, "check-grow"); + lbBlock *grow_fail_block = lb_create_block(p, "grow-fail"); + lbBlock *insert_block = lb_create_block(p, "insert"); + + lb_emit_if(p, lb_emit_comp_against_nil(p, Token_NotEq, found_ptr), found_block, check_grow_block); + lb_start_block(p, found_block); + { + lb_mem_copy_non_overlapping(p, found_ptr, value_ptr, lb_const_int(m, t_int, type_size_of(type->Map.value))); + LLVMBuildRet(p->builder, lb_emit_conv(p, found_ptr, t_rawptr).value); + } + lb_start_block(p, check_grow_block); + + + lbValue map_info = lb_gen_map_info_ptr(p->module, type); + + { + auto args = array_make(permanent_allocator(), 3); + args[0] = lb_emit_conv(p, map_ptr, t_rawptr); + args[1] = map_info; + args[2] = lb_emit_load(p, location_ptr); + lbValue grow_err = lb_emit_runtime_call(p, "__dynamic_map_check_grow", args); + + lb_emit_if(p, lb_emit_comp_against_nil(p, Token_NotEq, grow_err), grow_fail_block, insert_block); + + lb_start_block(p, grow_fail_block); + LLVMBuildRet(p->builder, LLVMConstNull(lb_type(m, t_rawptr))); + } + + lb_start_block(p, insert_block); + { + auto args = array_make(permanent_allocator(), 5); + args[0] = lb_emit_conv(p, map_ptr, t_rawptr); + args[1] = map_info; + args[2] = hash; + args[3] = lb_emit_conv(p, key_ptr, t_uintptr); + args[4] = lb_emit_conv(p, value_ptr, t_uintptr); + + lbValue result = lb_emit_runtime_call(p, "map_insert_hash_dynamic", args); + + lb_emit_increment(p, lb_map_len_ptr(p, map_ptr)); + + LLVMBuildRet(p->builder, lb_emit_conv(p, result, t_rawptr).value); + } + + return {p->value, p->type}; +} + + lbValue lb_generate_anonymous_proc_lit(lbModule *m, String const &prefix_name, Ast *expr, lbProcedure *parent) { lbProcedure **found = map_get(&m->gen->anonymous_proc_lits, expr); if (found) { @@ -810,8 +933,8 @@ lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, return lb_emit_conv(p, ptr, alloc_type_pointer(map_type->Map.value)); } -void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, Type *map_type, - lbValue const &map_key, lbValue const &map_value, Ast *node) { +void lb_internal_dynamic_map_set(lbProcedure *p, lbValue const &map_ptr, Type *map_type, + lbValue const &map_key, lbValue const &map_value, Ast *node) { map_type = base_type(map_type); GB_ASSERT(map_type->kind == Type_Map); @@ -821,14 +944,27 @@ void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, lbValue v = lb_emit_conv(p, map_value, map_type->Map.value); lbValue value_ptr = lb_address_from_load_or_generate_local(p, v); - auto args = array_make(permanent_allocator(), 6); - args[0] = lb_emit_conv(p, map_ptr, t_raw_map_ptr); - args[1] = lb_gen_map_info_ptr(p->module, map_type); - args[2] = hash; - args[3] = lb_emit_conv(p, key_ptr, t_rawptr); - args[4] = lb_emit_conv(p, value_ptr, t_rawptr); - args[5] = lb_emit_source_code_location_as_global(p, node); - lb_emit_runtime_call(p, "__dynamic_map_set", args); + if (build_context.use_static_map_calls) { + lbValue map_set_proc = lb_map_set_proc_for_type(p->module, map_type); + + auto args = array_make(permanent_allocator(), 5); + args[0] = lb_emit_conv(p, map_ptr, t_rawptr); + args[1] = hash; + args[2] = lb_emit_conv(p, key_ptr, t_rawptr); + args[3] = lb_emit_conv(p, value_ptr, t_rawptr); + args[4] = lb_emit_source_code_location_as_global(p, node); + + lb_emit_call(p, map_set_proc, args); + } else { + auto args = array_make(permanent_allocator(), 6); + args[0] = lb_emit_conv(p, map_ptr, t_raw_map_ptr); + args[1] = lb_gen_map_info_ptr(p->module, map_type); + args[2] = hash; + args[3] = lb_emit_conv(p, key_ptr, t_rawptr); + args[4] = lb_emit_conv(p, value_ptr, t_rawptr); + args[5] = lb_emit_source_code_location_as_global(p, node); + lb_emit_runtime_call(p, "__dynamic_map_set", args); + } } void lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const capacity, TokenPos const &pos) { @@ -1386,6 +1522,10 @@ WORKER_TASK_PROC(lb_llvm_function_pass_worker_proc) { lbProcedure *p = m->map_get_procs.entries[i].value; lb_run_function_pass_manager(default_function_pass_manager, p); } + for_array(i, m->map_set_procs.entries) { + lbProcedure *p = m->map_set_procs.entries[i].value; + lb_run_function_pass_manager(default_function_pass_manager, p); + } return 0; } diff --git a/src/llvm_backend.hpp b/src/llvm_backend.hpp index c4333e949..9074de42a 100644 --- a/src/llvm_backend.hpp +++ b/src/llvm_backend.hpp @@ -145,6 +145,7 @@ struct lbModule { PtrMap equal_procs; PtrMap hasher_procs; PtrMap map_get_procs; + PtrMap map_set_procs; u32 nested_type_name_guid; @@ -451,7 +452,7 @@ lbValue lb_gen_map_cell_info_ptr(lbModule *m, Type *type); lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type); lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key); -void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, Type *map_type, lbValue const &map_key, lbValue const &map_value, Ast *node); +void lb_internal_dynamic_map_set(lbProcedure *p, lbValue const &map_ptr, Type *map_type, lbValue const &map_key, lbValue const &map_value, Ast *node); void lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const capacity, TokenPos const &pos); lbValue lb_find_procedure_value_from_entity(lbModule *m, Entity *e); diff --git a/src/llvm_backend_const.cpp b/src/llvm_backend_const.cpp index a8b66a0ea..dff5298c5 100644 --- a/src/llvm_backend_const.cpp +++ b/src/llvm_backend_const.cpp @@ -283,19 +283,28 @@ lbValue lb_emit_source_code_location_const(lbProcedure *p, Ast *node) { return lb_emit_source_code_location_const(p, proc_name, pos); } -lbValue lb_emit_source_code_location_as_global(lbProcedure *p, String const &procedure, TokenPos const &pos) { + +lbValue lb_emit_source_code_location_as_global_ptr(lbProcedure *p, String const &procedure, TokenPos const &pos) { lbValue loc = lb_emit_source_code_location_const(p, procedure, pos); lbAddr addr = lb_add_global_generated(p->module, loc.type, loc, nullptr); lb_make_global_private_const(addr); - return lb_addr_load(p, addr); + return addr.addr; } -lbValue lb_emit_source_code_location_as_global(lbProcedure *p, Ast *node) { +lbValue lb_emit_source_code_location_as_global_ptr(lbProcedure *p, Ast *node) { lbValue loc = lb_emit_source_code_location_const(p, node); lbAddr addr = lb_add_global_generated(p->module, loc.type, loc, nullptr); lb_make_global_private_const(addr); - return lb_addr_load(p, addr); + return addr.addr; +} + +lbValue lb_emit_source_code_location_as_global(lbProcedure *p, String const &procedure, TokenPos const &pos) { + return lb_emit_load(p, lb_emit_source_code_location_as_global_ptr(p, procedure, pos)); +} + +lbValue lb_emit_source_code_location_as_global(lbProcedure *p, Ast *node) { + return lb_emit_load(p, lb_emit_source_code_location_as_global_ptr(p, node)); } diff --git a/src/llvm_backend_expr.cpp b/src/llvm_backend_expr.cpp index aee87242c..e58c84c9c 100644 --- a/src/llvm_backend_expr.cpp +++ b/src/llvm_backend_expr.cpp @@ -4139,7 +4139,7 @@ lbAddr lb_build_addr_compound_lit(lbProcedure *p, Ast *expr) { lbValue key = lb_build_expr(p, fv->field); lbValue value = lb_build_expr(p, fv->value); - lb_insert_dynamic_map_key_and_value(p, v.addr, type, key, value, elem); + lb_internal_dynamic_map_set(p, v.addr, type, key, value, elem); } break; } diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp index a0e4d80ba..f36dc1842 100644 --- a/src/llvm_backend_general.cpp +++ b/src/llvm_backend_general.cpp @@ -68,6 +68,7 @@ void lb_init_module(lbModule *m, Checker *c) { map_init(&m->equal_procs, a); map_init(&m->hasher_procs, a); map_init(&m->map_get_procs, a); + map_init(&m->map_set_procs, a); array_init(&m->procedures_to_generate, a, 0, 1024); array_init(&m->missing_procedures_to_check, a, 0, 16); map_init(&m->debug_values, a); @@ -727,7 +728,7 @@ void lb_addr_store(lbProcedure *p, lbAddr addr, lbValue value) { return; } else if (addr.kind == lbAddr_Map) { - lb_insert_dynamic_map_key_and_value(p, addr.addr, addr.map.type, addr.map.key, value, p->curr_stmt); + lb_internal_dynamic_map_set(p, addr.addr, addr.map.type, addr.map.key, value, p->curr_stmt); return; } else if (addr.kind == lbAddr_Context) { lbAddr old_addr = lb_find_or_generate_context_ptr(p); diff --git a/src/llvm_backend_utility.cpp b/src/llvm_backend_utility.cpp index 30c531d71..101b9dbfb 100644 --- a/src/llvm_backend_utility.cpp +++ b/src/llvm_backend_utility.cpp @@ -1438,6 +1438,13 @@ lbValue lb_map_len(lbProcedure *p, lbValue value) { lbValue len = lb_emit_struct_ev(p, value, 1); return lb_emit_conv(p, len, t_int); } +lbValue lb_map_len_ptr(lbProcedure *p, lbValue map_ptr) { + Type *type = map_ptr.type; + GB_ASSERT(is_type_pointer(type)); + type = type_deref(type); + GB_ASSERT_MSG(is_type_map(type) || are_types_identical(type, t_raw_map), "%s", type_to_string(type)); + return lb_emit_struct_ep(p, map_ptr, 1); +} lbValue lb_map_cap(lbProcedure *p, lbValue value) { GB_ASSERT_MSG(is_type_map(value.type) || are_types_identical(value.type, t_raw_map), "%s", type_to_string(value.type)); diff --git a/src/types.cpp b/src/types.cpp index 74b192010..47007491d 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -694,6 +694,7 @@ gb_global Type *t_raw_map_ptr = nullptr; gb_global Type *t_equal_proc = nullptr; gb_global Type *t_hasher_proc = nullptr; gb_global Type *t_map_get_proc = nullptr; +gb_global Type *t_map_set_proc = nullptr; gb_global Type *t_objc_object = nullptr; gb_global Type *t_objc_selector = nullptr; -- cgit v1.2.3 From f9576c2f5bc6e1354a9e736b32bdfb193593173b Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 11 Nov 2022 15:28:20 +0000 Subject: Add internal linkage to static map calls --- src/llvm_backend.cpp | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/llvm_backend.cpp') diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 4c34a56e9..4d2f95bdf 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -493,6 +493,7 @@ lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) { lb_begin_procedure_body(p); defer (lb_end_procedure_body(p)); + LLVMSetLinkage(p->value, LLVMInternalLinkage); lb_add_attribute_to_proc(m, p->value, "readonly"); lb_add_attribute_to_proc(m, p->value, "nounwind"); @@ -642,8 +643,8 @@ lbValue lb_map_set_proc_for_type(lbModule *m, Type *type) { lb_begin_procedure_body(p); defer (lb_end_procedure_body(p)); + LLVMSetLinkage(p->value, LLVMInternalLinkage); lb_add_attribute_to_proc(m, p->value, "nounwind"); - lb_add_attribute_to_proc(m, p->value, "noinline"); lbValue map_ptr = {LLVMGetParam(p->value, 0), t_rawptr}; lbValue hash = {LLVMGetParam(p->value, 1), t_uintptr}; -- cgit v1.2.3 From 22840ddf9769c47f8ac0f68b5b12f75200229bd9 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 11 Nov 2022 15:35:05 +0000 Subject: Add `noinline` LLVM attribute to static map procedures --- src/llvm_backend.cpp | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'src/llvm_backend.cpp') diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 4d2f95bdf..5b9db7f2b 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -496,6 +496,9 @@ lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) { LLVMSetLinkage(p->value, LLVMInternalLinkage); lb_add_attribute_to_proc(m, p->value, "readonly"); lb_add_attribute_to_proc(m, p->value, "nounwind"); + if (build_context.ODIN_DEBUG) { + lb_add_attribute_to_proc(m, p->value, "noinline"); + } LLVMValueRef x = LLVMGetParam(p->value, 0); LLVMValueRef y = LLVMGetParam(p->value, 1); @@ -645,6 +648,9 @@ lbValue lb_map_set_proc_for_type(lbModule *m, Type *type) { LLVMSetLinkage(p->value, LLVMInternalLinkage); lb_add_attribute_to_proc(m, p->value, "nounwind"); + if (build_context.ODIN_DEBUG) { + lb_add_attribute_to_proc(m, p->value, "noinline"); + } lbValue map_ptr = {LLVMGetParam(p->value, 0), t_rawptr}; lbValue hash = {LLVMGetParam(p->value, 1), t_uintptr}; -- 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/llvm_backend.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 From d2019e3e4d4b45c34bdc0ef7cf7d630ee61a02fb Mon Sep 17 00:00:00 2001 From: gingerBill Date: Sun, 13 Nov 2022 23:50:45 +0000 Subject: Enforce pointer cast --- src/llvm_backend.cpp | 4 ++-- src/llvm_backend_expr.cpp | 3 ++- src/llvm_backend_proc.cpp | 1 + 3 files changed, 5 insertions(+), 3 deletions(-) (limited to 'src/llvm_backend.cpp') diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 2ee292880..594224e6a 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -962,7 +962,7 @@ void lb_internal_dynamic_map_set(lbProcedure *p, lbValue const &map_ptr, Type *m } } -void lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const capacity, TokenPos const &pos) { +lbValue lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const capacity, TokenPos const &pos) { GB_ASSERT(!build_context.no_dynamic_literals); String proc_name = {}; @@ -975,7 +975,7 @@ void lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const args[1] = lb_gen_map_info_ptr(p->module, type_deref(map_ptr.type)); args[2] = lb_const_int(p->module, t_uint, capacity); args[3] = lb_emit_source_code_location_as_global(p, proc_name, pos); - lb_emit_runtime_call(p, "__dynamic_map_reserve", args); + return lb_emit_runtime_call(p, "__dynamic_map_reserve", args); } diff --git a/src/llvm_backend_expr.cpp b/src/llvm_backend_expr.cpp index e58c84c9c..034682855 100644 --- a/src/llvm_backend_expr.cpp +++ b/src/llvm_backend_expr.cpp @@ -4131,7 +4131,8 @@ lbAddr lb_build_addr_compound_lit(lbProcedure *p, Ast *expr) { } GB_ASSERT(!build_context.no_dynamic_literals); - lb_dynamic_map_reserve(p, v.addr, 2*cl->elems.count, pos); + lbValue err = lb_dynamic_map_reserve(p, v.addr, 2*cl->elems.count, pos); + gb_unused(err); for_array(field_index, cl->elems) { Ast *elem = cl->elems[field_index]; diff --git a/src/llvm_backend_proc.cpp b/src/llvm_backend_proc.cpp index 2e508a939..510479440 100644 --- a/src/llvm_backend_proc.cpp +++ b/src/llvm_backend_proc.cpp @@ -599,6 +599,7 @@ void lb_begin_procedure_body(lbProcedure *p) { p->entity->decl_info != nullptr && p->entity->decl_info->defer_use_count == 0) { lbValue val = lb_emit_struct_ep(p, p->return_ptr.addr, cast(i32)i); + val = lb_emit_conv(p, val, alloc_type_pointer(e->type)); lb_add_entity(p->module, e, val); lb_add_debug_local_variable(p, val.value, e->type, e->token); -- cgit v1.2.3