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/types.cpp | 22 ++++++++-------------- 1 file changed, 8 insertions(+), 14 deletions(-) (limited to 'src/types.cpp') diff --git a/src/types.cpp b/src/types.cpp index b9f2b375f..220d1a6ab 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -226,7 +226,6 @@ struct TypeProc { TYPE_KIND(Map, struct { \ Type *key; \ Type *value; \ - Type *entry_type; \ Type *internal_type; \ Type *lookup_result_type; \ }) \ @@ -685,9 +684,8 @@ gb_global Type *t_allocator_error = nullptr; gb_global Type *t_source_code_location = nullptr; gb_global Type *t_source_code_location_ptr = nullptr; -gb_global Type *t_map_hash = nullptr; -gb_global Type *t_map_header = nullptr; -gb_global Type *t_map_header_table = nullptr; +gb_global Type *t_map_info = nullptr; +gb_global Type *t_map_cell_info = nullptr; gb_global Type *t_equal_proc = nullptr; @@ -3330,8 +3328,6 @@ Selection lookup_field_with_selection(Type *type_, String field_name, bool is_ty } } } else if (type->kind == Type_DynamicArray) { - // IMPORTANT TODO(bill): Should these members be available to should I only allow them with - // `Raw_Dynamic_Array` type? GB_ASSERT(t_allocator != nullptr); String allocator_str = str_lit("allocator"); gb_local_persist Entity *entity__allocator = alloc_entity_field(nullptr, make_token_ident(allocator_str), t_allocator, false, 3); @@ -3342,15 +3338,12 @@ Selection lookup_field_with_selection(Type *type_, String field_name, bool is_ty return sel; } } else if (type->kind == Type_Map) { - // IMPORTANT TODO(bill): Should these members be available to should I only allow them with - // `Raw_Map` type? GB_ASSERT(t_allocator != nullptr); String allocator_str = str_lit("allocator"); - gb_local_persist Entity *entity__allocator = alloc_entity_field(nullptr, make_token_ident(allocator_str), t_allocator, false, 3); + gb_local_persist Entity *entity__allocator = alloc_entity_field(nullptr, make_token_ident(allocator_str), t_allocator, false, 2); if (field_name == allocator_str) { - selection_add_index(&sel, 1); - selection_add_index(&sel, 3); + selection_add_index(&sel, 2); sel.entity = entity__allocator; return sel; } @@ -3795,11 +3788,12 @@ i64 type_size_of_internal(Type *t, TypePath *path) { case Type_Map: /* struct { - hashes: []int, // 2 words - entries: [dynamic]Entry_Type, // 5 words + data: uintptr, // 1 word + size: uintptr, // 1 word + allocator: runtime.Allocator, // 2 words } */ - return (2 + (3 + 2))*build_context.word_size; + return (1 + 1 + 2)*build_context.word_size; case Type_Tuple: { i64 count, align, size; -- cgit v1.2.3 From 810a1eee41cc8e047759c8934af70d6e68113082 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 8 Nov 2022 11:13:46 +0000 Subject: Remove the need for `type->Map.internal_type` and replace with the definition of `runtime.Raw_Map` --- src/check_expr.cpp | 1 - src/check_type.cpp | 24 ++---------------------- src/checker.cpp | 11 +++++++---- src/llvm_backend_debug.cpp | 3 ++- src/llvm_backend_general.cpp | 20 ++------------------ src/llvm_backend_utility.cpp | 17 +++++++---------- src/types.cpp | 2 +- 7 files changed, 21 insertions(+), 57 deletions(-) (limited to 'src/types.cpp') diff --git a/src/check_expr.cpp b/src/check_expr.cpp index 043b98173..c2753e979 100644 --- a/src/check_expr.cpp +++ b/src/check_expr.cpp @@ -1364,7 +1364,6 @@ bool is_polymorphic_type_assignable(CheckerContext *c, Type *poly, Type *source, bool key = is_polymorphic_type_assignable(c, poly->Map.key, source->Map.key, true, modify_type); bool value = is_polymorphic_type_assignable(c, poly->Map.value, source->Map.value, true, modify_type); if (key || value) { - poly->Map.internal_type = nullptr; poly->Map.lookup_result_type = nullptr; init_map_internal_types(poly); return true; diff --git a/src/check_type.cpp b/src/check_type.cpp index 39344fb2c..5d7f8d7b5 100644 --- a/src/check_type.cpp +++ b/src/check_type.cpp @@ -2198,34 +2198,14 @@ void map_cell_size_and_len(Type *type, i64 *size_, i64 *len_) { void init_map_internal_types(Type *type) { GB_ASSERT(type->kind == Type_Map); GB_ASSERT(t_allocator != nullptr); - if (type->Map.internal_type != nullptr) return; + if (type->Map.lookup_result_type != nullptr) return; Type *key = type->Map.key; Type *value = type->Map.value; GB_ASSERT(key != nullptr); GB_ASSERT(value != nullptr); - Type *generated_struct_type = alloc_type_struct(); - - /* - struct { - data: uintptr, - size: uintptr, - allocator: runtime.Allocator, - } - */ - Scope *s = create_scope(nullptr, builtin_pkg->scope); - - auto fields = slice_make(permanent_allocator(), 3); - fields[0] = alloc_entity_field(s, make_token_ident(str_lit("data")), t_uintptr, false, 0, EntityState_Resolved); - fields[1] = alloc_entity_field(s, make_token_ident(str_lit("size")), t_uintptr, false, 1, EntityState_Resolved); - fields[2] = alloc_entity_field(s, make_token_ident(str_lit("allocator")), t_allocator, false, 2, EntityState_Resolved); - - generated_struct_type->Struct.fields = fields; - type_set_offsets(generated_struct_type); - - type->Map.internal_type = generated_struct_type; - type->Map.lookup_result_type = make_optional_ok_type(value); + type->Map.lookup_result_type = make_optional_ok_type(value); } void add_map_key_type_dependencies(CheckerContext *ctx, Type *key) { diff --git a/src/checker.cpp b/src/checker.cpp index d5d2c6026..fa3ef245b 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -1933,7 +1933,8 @@ void add_type_info_type_internal(CheckerContext *c, Type *t) { init_map_internal_types(bt); add_type_info_type_internal(c, bt->Map.key); add_type_info_type_internal(c, bt->Map.value); - add_type_info_type_internal(c, bt->Map.internal_type); + add_type_info_type_internal(c, t_uintptr); // hash value + add_type_info_type_internal(c, t_allocator); break; case Type_Tuple: @@ -2155,7 +2156,8 @@ void add_min_dep_type_info(Checker *c, Type *t) { init_map_internal_types(bt); add_min_dep_type_info(c, bt->Map.key); add_min_dep_type_info(c, bt->Map.value); - add_min_dep_type_info(c, bt->Map.internal_type); + add_min_dep_type_info(c, t_uintptr); // hash value + add_min_dep_type_info(c, t_allocator); break; case Type_Tuple: @@ -2845,9 +2847,10 @@ void init_core_map_type(Checker *c) { if (t_map_info != nullptr) { return; } - t_map_info = find_core_type(c, str_lit("Map_Info")); - t_map_cell_info = find_core_type(c, str_lit("Map_Cell_Info")); init_mem_allocator(c); + t_map_info = find_core_type(c, str_lit("Map_Info")); + t_map_cell_info = find_core_type(c, str_lit("Map_Cell_Info")); + t_raw_map = find_core_type(c, str_lit("Raw_Map")); } void init_preload(Checker *c) { diff --git a/src/llvm_backend_debug.cpp b/src/llvm_backend_debug.cpp index 8a98b7f39..e69424929 100644 --- a/src/llvm_backend_debug.cpp +++ b/src/llvm_backend_debug.cpp @@ -671,7 +671,8 @@ void lb_debug_complete_types(lbModule *m) { break; case Type_Map: - bt = bt->Map.internal_type; + GB_ASSERT(t_raw_map != nullptr); + bt = base_type(t_raw_map); /*fallthrough*/ case Type_Struct: if (file == nullptr) { diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp index 69b1fce20..ffc7a1496 100644 --- a/src/llvm_backend_general.cpp +++ b/src/llvm_backend_general.cpp @@ -1931,24 +1931,8 @@ LLVMTypeRef lb_type_internal(lbModule *m, Type *type) { case Type_Map: init_map_internal_types(type); - { - Type *internal_type = type->Map.internal_type; - GB_ASSERT(internal_type->kind == Type_Struct); - - m->internal_type_level -= 1; - defer (m->internal_type_level += 1); - - unsigned field_count = cast(unsigned)(internal_type->Struct.fields.count); - GB_ASSERT(field_count == 3); - - LLVMTypeRef fields[3] = { - lb_type(m, t_uintptr), // data - lb_type(m, t_uintptr), // len - lb_type(m, t_allocator), // allocator - }; - - return LLVMStructTypeInContext(ctx, fields, field_count, false); - } + GB_ASSERT(t_raw_map != nullptr); + return lb_type_internal(m, t_raw_map); case Type_Struct: { diff --git a/src/llvm_backend_utility.cpp b/src/llvm_backend_utility.cpp index cbe690155..f4d17c7a2 100644 --- a/src/llvm_backend_utility.cpp +++ b/src/llvm_backend_utility.cpp @@ -990,15 +990,13 @@ lbValue lb_emit_struct_ep(lbProcedure *p, lbValue s, i32 index) { } } else if (is_type_map(t)) { init_map_internal_types(t); - Type *itp = alloc_type_pointer(t->Map.internal_type); + Type *itp = alloc_type_pointer(t_raw_map); s = lb_emit_transmute(p, s, itp); - Type *gst = t->Map.internal_type; - GB_ASSERT(gst->kind == Type_Struct); switch (index) { - case 0: result_type = get_struct_field_type(gst, 0); break; - case 1: result_type = get_struct_field_type(gst, 1); break; - case 2: result_type = get_struct_field_type(gst, 2); break; + case 0: result_type = get_struct_field_type(t_raw_map, 0); break; + case 1: result_type = get_struct_field_type(t_raw_map, 1); break; + case 2: result_type = get_struct_field_type(t_raw_map, 2); break; } } else if (is_type_array(t)) { return lb_emit_array_epi(p, s, index); @@ -1131,11 +1129,10 @@ lbValue lb_emit_struct_ev(lbProcedure *p, lbValue s, i32 index) { case Type_Map: { init_map_internal_types(t); - Type *gst = t->Map.internal_type; switch (index) { - case 0: result_type = get_struct_field_type(gst, 0); break; - case 1: result_type = get_struct_field_type(gst, 1); break; - case 2: result_type = get_struct_field_type(gst, 2); break; + case 0: result_type = get_struct_field_type(t_raw_map, 0); break; + case 1: result_type = get_struct_field_type(t_raw_map, 1); break; + case 2: result_type = get_struct_field_type(t_raw_map, 2); break; } } break; diff --git a/src/types.cpp b/src/types.cpp index 220d1a6ab..9b2fd30d4 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -226,7 +226,6 @@ struct TypeProc { TYPE_KIND(Map, struct { \ Type *key; \ Type *value; \ - Type *internal_type; \ Type *lookup_result_type; \ }) \ TYPE_KIND(Struct, TypeStruct) \ @@ -686,6 +685,7 @@ gb_global Type *t_source_code_location_ptr = nullptr; gb_global Type *t_map_info = nullptr; gb_global Type *t_map_cell_info = nullptr; +gb_global Type *t_raw_map = nullptr; gb_global Type *t_equal_proc = nullptr; -- cgit v1.2.3 From d77269dee2abe3104df0c36bdffe157a079bec7c Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 8 Nov 2022 11:42:42 +0000 Subject: Disallow zero sized map keys --- src/types.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/types.cpp') diff --git a/src/types.cpp b/src/types.cpp index 9b2fd30d4..c92d8a78f 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -1921,7 +1921,7 @@ bool is_type_valid_for_keys(Type *t) { if (is_type_untyped(t)) { return false; } - return is_type_comparable(t); + return type_size_of(t) > 0 && is_type_comparable(t); } bool is_type_valid_bit_set_elem(Type *t) { -- 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/types.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 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/types.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/types.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 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/types.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