Merge pull request #2063 from odin-lang/map-header-changes

Map header changes

7 files changed, 94 insertions, 112 deletions

diff --git a/src/checker.cpp b/src/checker.cpp
index cdc0630bf..e30dea6e1 100644
--- a/src/checker.cpp
+++ b/src/checker.cpp
@@ -2831,23 +2831,12 @@ void init_core_source_code_location(Checker *c) {
 }
 
 void init_core_map_type(Checker *c) {
-	if (t_map_hash == nullptr) {
-		Entity *e = find_core_entity(c, str_lit("Map_Hash"));
-		if (e->state == EntityState_Unresolved) {
-			check_entity_decl(&c->builtin_ctx, e, nullptr, nullptr);
-		}
-		t_map_hash = e->type;
-		GB_ASSERT(t_map_hash != nullptr);
-	}
-
-	if (t_map_header == nullptr) {
-		Entity *e = find_core_entity(c, str_lit("Map_Header"));
-		if (e->state == EntityState_Unresolved) {
-			check_entity_decl(&c->builtin_ctx, e, nullptr, nullptr);
-		}
-		t_map_header = e->type;
-		GB_ASSERT(t_map_header != nullptr);
+	if (t_map_hash != nullptr) {
+		return;
 	}
+	t_map_hash = find_core_type(c, str_lit("Map_Hash"));
+	t_map_header = find_core_type(c, str_lit("Map_Header"));
+	t_map_header_table = find_core_type(c, str_lit("Map_Header_Table"));
 }
 
 void init_preload(Checker *c) {
diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp
index 9594e9d86..8bee5c9e5 100644
--- a/src/llvm_backend.cpp
+++ b/src/llvm_backend.cpp
@@ -500,20 +500,18 @@ lbValue lb_generate_anonymous_proc_lit(lbModule *m, String const &prefix_name, A
 	return value;
 }
 
-lbAddr lb_gen_map_header_internal(lbProcedure *p, lbValue map_val_ptr, Type *map_type) {
+lbValue lb_gen_map_header_table_internal(lbProcedure *p, Type *map_type) {
+	lbModule *m = p->module;
+
 	map_type = base_type(map_type);
 	GB_ASSERT(map_type->kind == Type_Map);
 
-	lbAddr h = lb_add_local_generated(p, t_map_header, true); // all the values will be initialzed later
-
-	Type *key_type = map_type->Map.key;
-	Type *val_type = map_type->Map.value;
-	gb_unused(val_type);
+	lbAddr *found = map_get(&m->map_header_table_map, map_type);
+	if (found) {
+		return lb_addr_load(p, *found);
+	}
 
 	GB_ASSERT(map_type->Map.entry_type->kind == Type_Struct);
-	map_type->Map.entry_type->cached_size = -1;
-	map_type->Map.entry_type->Struct.are_offsets_set = false;
-
 	i64 entry_size   = type_size_of  (map_type->Map.entry_type);
 	i64 entry_align  = type_align_of (map_type->Map.entry_type);
 
@@ -524,52 +522,34 @@ lbAddr lb_gen_map_header_internal(lbProcedure *p, lbValue map_val_ptr, Type *map
 	i64 value_size   = type_size_of  (map_type->Map.value);
 
 
-	Type *map_header_base = base_type(t_map_header);
-	GB_ASSERT(map_header_base->Struct.fields.count == 8);
-	Type *raw_map_ptr_type = map_header_base->Struct.fields[0]->type;
-	LLVMValueRef const_values[8] = {};
-	const_values[0] = LLVMConstNull(lb_type(p->module, raw_map_ptr_type));
-	const_values[1] = lb_get_equal_proc_for_type(p->module, key_type)    .value;
-	const_values[2] = lb_const_int(p->module, t_int,        entry_size)  .value;
-	const_values[3] = lb_const_int(p->module, t_int,        entry_align) .value;
-	const_values[4] = lb_const_int(p->module, t_uintptr,    key_offset)  .value;
-	const_values[5] = lb_const_int(p->module, t_int,        key_size)    .value;
-	const_values[6] = lb_const_int(p->module, t_uintptr,    value_offset).value;
-	const_values[7] = lb_const_int(p->module, t_int,        value_size)  .value;
-
-	LLVMValueRef const_value = llvm_const_named_struct(p->module, t_map_header, const_values, gb_count_of(const_values));
-	LLVMBuildStore(p->builder, const_value, h.addr.value);
-
-	// NOTE(bill): Removes unnecessary allocation if split gep
-	lbValue gep0 = lb_emit_struct_ep(p, h.addr, 0);
-	lbValue m = lb_emit_conv(p, map_val_ptr, type_deref(gep0.type));
-	lb_emit_store(p, gep0, m);
-	return h;
-}
+	Type *key_type = map_type->Map.key;
+	Type *val_type = map_type->Map.value;
+	gb_unused(val_type);
 
+	Type *st = base_type(t_map_header_table);
+	GB_ASSERT(st->Struct.fields.count == 7);
 
-lbValue lb_gen_map_header(lbProcedure *p, lbValue map_val_ptr, Type *map_type) {
-	GB_ASSERT_MSG(is_type_pointer(map_val_ptr.type), "%s", type_to_string(map_val_ptr.type));
-	GB_ASSERT(is_type_map(map_type));
+	LLVMValueRef const_values[7] = {};
+	const_values[0] = lb_get_equal_proc_for_type(m, key_type)    .value;
+	const_values[1] = lb_const_int(m, t_int,        entry_size)  .value;
+	const_values[2] = lb_const_int(m, t_int,        entry_align) .value;
+	const_values[3] = lb_const_int(m, t_uintptr,    key_offset)  .value;
+	const_values[4] = lb_const_int(m, t_int,        key_size)    .value;
+	const_values[5] = lb_const_int(m, t_uintptr,    value_offset).value;
+	const_values[6] = lb_const_int(m, t_int,        value_size)  .value;
 
+	LLVMValueRef llvm_res = llvm_const_named_struct(m, t_map_header_table, const_values, gb_count_of(const_values));
+	lbValue res = {llvm_res, t_map_header_table};
 
-	// TODO(bill): this is a temporary fix since this caching is not working other platforms
-	bool allow_caching = build_context.metrics.os == TargetOs_windows || is_arch_wasm();
+	lbAddr addr = lb_add_global_generated(m, t_map_header_table, res, nullptr);
+	LLVMValueRef global_data = addr.addr.value;
 
-	lbAddr h = {};
-	if (!allow_caching) {
-		h = lb_gen_map_header_internal(p, map_val_ptr, map_type);
-	} else {
-		lbAddr *found = map_get(&p->map_header_cache, map_val_ptr.value);
-		if (found != nullptr) {
-			h = *found;
-		} else {
-			h = lb_gen_map_header_internal(p, map_val_ptr, map_type);
-			map_set(&p->map_header_cache, map_val_ptr.value, h);
-		}
-	}
+	LLVMSetLinkage(global_data, LLVMPrivateLinkage);
+	LLVMSetUnnamedAddress(global_data, LLVMGlobalUnnamedAddr);
+	LLVMSetGlobalConstant(global_data, true);
 
-	return lb_addr_load(p, h);
+	map_set(&m->map_header_table_map, map_type, addr);
+	return lb_addr_load(p, addr);
 }
 
 lbValue lb_const_hash(lbModule *m, lbValue key, Type *key_type) {
@@ -638,12 +618,26 @@ lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue
 	return hashed_key;
 }
 
-void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbAddr addr, Type *map_type,
-                                         lbValue map_key, lbValue map_value, Ast *node) {
+lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key) {
+	Type *map_type = base_type(type_deref(map_ptr.type));
+
+	lbValue key_ptr = {};
+	auto args = array_make<lbValue>(permanent_allocator(), 4);
+	args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
+	args[1] = lb_gen_map_header_table_internal(p, map_type);
+	args[2] = lb_gen_map_key_hash(p, key, map_type->Map.key, &key_ptr);
+	args[3] = key_ptr;
+
+	lbValue ptr = lb_emit_runtime_call(p, "__dynamic_map_get", args);
+
+	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) {
 	map_type = base_type(map_type);
 	GB_ASSERT(map_type->kind == Type_Map);
 
-	lbValue h = lb_gen_map_header(p, addr.addr, map_type);
 	lbValue key_ptr = {};
 	lbValue key_hash = lb_gen_map_key_hash(p, map_key, map_type->Map.key, &key_ptr);
 	lbValue v = lb_emit_conv(p, map_value, map_type->Map.value);
@@ -651,15 +645,32 @@ void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbAddr addr, Type *map_
 	lbAddr value_addr = lb_add_local_generated(p, v.type, false);
 	lb_addr_store(p, value_addr, v);
 
-	auto args = array_make<lbValue>(permanent_allocator(), 5);
-	args[0] = h;
-	args[1] = key_hash;
-	args[2] = key_ptr;
-	args[3] = lb_emit_conv(p, value_addr.addr, t_rawptr);
-	args[4] = lb_emit_source_code_location(p, node);
+	auto args = array_make<lbValue>(permanent_allocator(), 6);
+	args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
+	args[1] = lb_gen_map_header_table_internal(p, map_type);
+	args[2] = key_hash;
+	args[3] = key_ptr;
+	args[4] = lb_emit_conv(p, value_addr.addr, t_rawptr);
+	args[5] = lb_emit_source_code_location(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) {
+	GB_ASSERT(!build_context.no_dynamic_literals);
+
+	String proc_name = {};
+	if (p->entity) {
+		proc_name = p->entity->token.string;
+	}
+
+	auto args = array_make<lbValue>(permanent_allocator(), 4);
+	args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
+	args[1] = lb_gen_map_header_table_internal(p, type_deref(map_ptr.type));
+	args[2] = lb_const_int(p->module, t_int, capacity);
+	args[3] = lb_emit_source_code_location(p, proc_name, pos);
+	lb_emit_runtime_call(p, "__dynamic_map_reserve", args);
+}
+
 
 struct lbGlobalVariable {
 	lbValue var;
diff --git a/src/llvm_backend.hpp b/src/llvm_backend.hpp
index d622f3661..e69d3a6ed 100644
--- a/src/llvm_backend.hpp
+++ b/src/llvm_backend.hpp
@@ -159,6 +159,8 @@ struct lbModule {
 
 	StringMap<lbAddr> objc_classes;
 	StringMap<lbAddr> objc_selectors;
+
+	PtrMap<Type *, lbAddr> map_header_table_map;
 };
 
 struct lbGenerator {
@@ -308,7 +310,6 @@ struct lbProcedure {
 
 	PtrMap<Ast *, lbValue> selector_values;
 	PtrMap<Ast *, lbAddr>  selector_addr;
-	PtrMap<LLVMValueRef, lbAddr> map_header_cache;
 };
 
 
@@ -444,9 +445,11 @@ String lb_get_const_string(lbModule *m, lbValue value);
 
 lbValue lb_generate_local_array(lbProcedure *p, Type *elem_type, i64 count, bool zero_init=true);
 lbValue lb_generate_global_array(lbModule *m, Type *elem_type, i64 count, String prefix, i64 id);
-lbValue lb_gen_map_header(lbProcedure *p, lbValue map_val_ptr, Type *map_type);
 lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue *key_ptr_);
-void    lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbAddr addr, Type *map_type, lbValue map_key, lbValue map_value, Ast *node);
+
+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_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);
 lbValue lb_find_value_from_entity(lbModule *m, Entity *e);
diff --git a/src/llvm_backend_expr.cpp b/src/llvm_backend_expr.cpp
index 3ab73a27b..e8138d0a2 100644
--- a/src/llvm_backend_expr.cpp
+++ b/src/llvm_backend_expr.cpp
@@ -3670,16 +3670,14 @@ lbAddr lb_build_addr_index_expr(lbProcedure *p, Ast *expr) {
 
 	if (is_type_map(t)) {
 		lbAddr map_addr = lb_build_addr(p, ie->expr);
-		lbValue map_val = lb_addr_load(p, map_addr);
-		if (deref) {
-			map_val = lb_emit_load(p, map_val);
-		}
-
 		lbValue key = lb_build_expr(p, ie->index);
 		key = lb_emit_conv(p, key, t->Map.key);
 
 		Type *result_type = type_of_expr(expr);
-		lbValue map_ptr = lb_address_from_load_or_generate_local(p, map_val);
+		lbValue map_ptr = lb_addr_get_ptr(p, map_addr);
+		if (is_type_pointer(type_deref(map_ptr.type))) {
+			map_ptr = lb_emit_load(p, map_ptr);
+		}
 		return lb_addr_map(map_ptr, key, t, result_type);
 	}
 
@@ -4130,20 +4128,16 @@ lbAddr lb_build_addr_compound_lit(lbProcedure *p, Ast *expr) {
 			break;
 		}
 		GB_ASSERT(!build_context.no_dynamic_literals);
-		{
-			auto args = array_make<lbValue>(permanent_allocator(), 3);
-			args[0] = lb_gen_map_header(p, v.addr, type);
-			args[1] = lb_const_int(p->module, t_int, 2*cl->elems.count);
-			args[2] = lb_emit_source_code_location(p, proc_name, pos);
-			lb_emit_runtime_call(p, "__dynamic_map_reserve", args);
-		}
+
+		lb_dynamic_map_reserve(p, v.addr, 2*cl->elems.count, pos);
+
 		for_array(field_index, cl->elems) {
 			Ast *elem = cl->elems[field_index];
 			ast_node(fv, FieldValue, elem);
 
 			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, type, key, value, elem);
+			lb_insert_dynamic_map_key_and_value(p, v.addr, type, key, value, elem);
 		}
 		break;
 	}
diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp
index 55b09cbfc..ba1c501ad 100644
--- a/src/llvm_backend_general.cpp
+++ b/src/llvm_backend_general.cpp
@@ -74,6 +74,9 @@ void lb_init_module(lbModule *m, Checker *c) {
 
 	string_map_init(&m->objc_classes, a);
 	string_map_init(&m->objc_selectors, a);
+
+	map_init(&m->map_header_table_map, a, 0);
+
 }
 
 bool lb_init_generator(lbGenerator *gen, Checker *c) {
@@ -383,21 +386,6 @@ Type *lb_addr_type(lbAddr const &addr) {
 	return type_deref(addr.addr.type);
 }
 
-lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key) {
-	Type *map_type = base_type(type_deref(map_ptr.type));
-	lbValue h = lb_gen_map_header(p, map_ptr, map_type);
-
-	lbValue key_ptr = {};
-	auto args = array_make<lbValue>(permanent_allocator(), 3);
-	args[0] = h;
-	args[1] = lb_gen_map_key_hash(p, key, map_type->Map.key, &key_ptr);
-	args[2] = key_ptr;
-
-	lbValue ptr = lb_emit_runtime_call(p, "__dynamic_map_get", args);
-
-	return lb_emit_conv(p, ptr, alloc_type_pointer(map_type->Map.value));
-}
-
 lbValue lb_addr_get_ptr(lbProcedure *p, lbAddr const &addr) {
 	if (addr.addr.value == nullptr) {
 		GB_PANIC("Illegal addr -> nullptr");
@@ -715,7 +703,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.map.type, addr.map.key, value, p->curr_stmt);
+		lb_insert_dynamic_map_key_and_value(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_proc.cpp b/src/llvm_backend_proc.cpp
index 17ed9c2a6..56ffe3fe9 100644
--- a/src/llvm_backend_proc.cpp
+++ b/src/llvm_backend_proc.cpp
@@ -123,7 +123,6 @@ lbProcedure *lb_create_procedure(lbModule *m, Entity *entity, bool ignore_body)
 	p->scope_stack.allocator   = a;
 	map_init(&p->selector_values,  a, 0);
 	map_init(&p->selector_addr,    a, 0);
-	map_init(&p->map_header_cache, a, 0);
 
 	if (p->is_foreign) {
 		lb_add_foreign_library_path(p->module, entity->Procedure.foreign_library);
@@ -380,9 +379,6 @@ lbProcedure *lb_create_dummy_procedure(lbModule *m, String link_name, Type *type
 		lb_add_proc_attribute_at_index(p, offset+parameter_index, "nonnull");
 		lb_add_proc_attribute_at_index(p, offset+parameter_index, "nocapture");
 	}
-
-	map_init(&p->map_header_cache, heap_allocator(), 0);
-
 	return p;
 }
 
@@ -889,7 +885,7 @@ lbValue lb_emit_call(lbProcedure *p, lbValue value, Array<lbValue> const &args,
 		GB_ASSERT(param_count-1 <= args.count);
 		param_count -= 1;
 	} else {
-		GB_ASSERT_MSG(param_count == args.count, "%td == %td", param_count, args.count);
+		GB_ASSERT_MSG(param_count == args.count, "%td == %td (%s)", param_count, args.count, LLVMPrintValueToString(value.value));
 	}
 
 	lbValue result = {};
diff --git a/src/types.cpp b/src/types.cpp
index 5ebc8689f..321f42aa0 100644
--- a/src/types.cpp
+++ b/src/types.cpp
@@ -688,6 +688,7 @@ 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_equal_proc  = nullptr;