Make `Map_Info` store pointers to cell info rather than inline

11 files changed, 86 insertions, 61 deletions

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<lbAddr> objc_classes;
 	StringMap<lbAddr> objc_selectors;
 
-	PtrMap<Type *, lbAddr> map_info_map;
+	PtrMap<Type *, lbAddr> map_cell_info_map; // address of runtime.Map_Info
+	PtrMap<Type *, lbAddr> 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;