Merge pull request #9310 from ziglang/stage1-better-hashing

Speed up stage 1 by improving hash functions

1 files changed, 164 insertions, 4 deletions

diff --git a/src/stage1/ir.cpp b/src/stage1/ir.cpp
index 22a4bdf92f..ab8aac9a91 100644
--- a/src/stage1/ir.cpp
+++ b/src/stage1/ir.cpp
@@ -272,6 +272,10 @@ static bool value_cmp_numeric_val_all(ZigValue *left, Cmp predicate, ZigValue *r
 static void memoize_field_init_val(CodeGen *codegen, ZigType *container_type, TypeStructField *field);
 static void value_to_bigfloat(BigFloat *out, ZigValue *val);
 
+static Error ir_resolve_lazy_recurse(AstNode *source_node, ZigValue *val);
+static Error ir_resolve_lazy_recurse_array(AstNode *source_node, ZigValue *val, size_t len);
+
+
 static void ir_assert_impl(bool ok, IrInstGen *source_instruction, char const *file, unsigned int line) {
     if (ok) return;
     src_assert_impl(ok, source_instruction->source_node, file, line);
@@ -554,7 +558,10 @@ static ZigValue *const_ptr_pointee_unchecked_no_isf(CodeGen *g, ZigValue *const_
         case ConstPtrSpecialBaseStruct: {
             ZigValue *struct_val = const_val->data.x_ptr.data.base_struct.struct_val;
             expand_undef_struct(g, struct_val);
-            result = struct_val->data.x_struct.fields[const_val->data.x_ptr.data.base_struct.field_index];
+            size_t field_index = const_val->data.x_ptr.data.base_struct.field_index;
+            assert(struct_val->type->id == ZigTypeIdStruct);
+            assert(!struct_val->type->data.structure.fields[field_index]->is_comptime);
+            result = struct_val->data.x_struct.fields[field_index];
             break;
         }
         case ConstPtrSpecialBaseErrorUnionCode:
@@ -7018,6 +7025,17 @@ static IrInstGen *ir_analyze_struct_literal_to_struct(IrAnalyze *ira, Scope *sco
                 buf_sprintf("field '%s' declared here", buf_ptr(src_field->name)));
             return ira->codegen->invalid_inst_gen;
         }
+        if (dst_field->is_comptime) {
+            ErrorMsg *msg = ir_add_error_node(ira, source_node, buf_sprintf("field '%s' in struct '%s' is comptime, it cannot be assigned",
+                    buf_ptr(src_field->name), buf_ptr(&wanted_type->name)));
+            if (wanted_type->data.structure.decl_node) {
+                add_error_note(ira->codegen, msg, wanted_type->data.structure.decl_node,
+                    buf_sprintf("struct '%s' declared here", buf_ptr(&wanted_type->name)));
+            }
+            add_error_note(ira->codegen, msg, src_field->decl_node,
+                buf_sprintf("field '%s' declared here", buf_ptr(src_field->name)));
+            return ira->codegen->invalid_inst_gen;
+        }
 
         src_assert(src_field->decl_node != nullptr, source_node);
         AstNode *existing_assign_node = field_assign_nodes[dst_field->src_index];
@@ -7062,6 +7080,7 @@ static IrInstGen *ir_analyze_struct_literal_to_struct(IrAnalyze *ira, Scope *sco
 
         // look for a default field value
         TypeStructField *field = wanted_type->data.structure.fields[i];
+        assert(!field->is_comptime); // field_assign_nodes[i] should be null for comptime fields
         memoize_field_init_val(ira->codegen, wanted_type, field);
         if (field->init_val == nullptr) {
             ir_add_error_node(ira, source_node,
@@ -7097,6 +7116,9 @@ static IrInstGen *ir_analyze_struct_literal_to_struct(IrAnalyze *ira, Scope *sco
 
     for (size_t i = 0; i < actual_field_count; i += 1) {
         TypeStructField *field = wanted_type->data.structure.fields[i];
+        if (field->is_comptime)
+            continue;
+
         IrInstGen *field_ptr = ir_analyze_struct_field_ptr(ira, scope, source_node, field, result_loc_inst, wanted_type, true);
         if (type_is_invalid(field_ptr->value->type))
             return ira->codegen->invalid_inst_gen;
@@ -12750,6 +12772,29 @@ static IrInstGen *ir_analyze_fn_call(IrAnalyze *ira, Scope *scope, AstNode *sour
         bool cacheable = fn_eval_cacheable(exec_scope, return_type);
         ZigValue *result = nullptr;
         if (cacheable) {
+            // We are about to put ZigValues into a hash map. The hash of a lazy value and a
+            // fully resolved value must equal, and so we must resolve the lazy values here.
+            // The hash function asserts that none of the values are lazy.
+            {
+                Scope *scope = exec_scope;
+                while (scope) {
+                    if (scope->id == ScopeIdVarDecl) {
+                        ScopeVarDecl *var_scope = (ScopeVarDecl *)scope;
+                        if ((err = ir_resolve_lazy_recurse(
+                            var_scope->var->decl_node,
+                            var_scope->var->const_value)))
+                        {
+                            return ira->codegen->invalid_inst_gen;
+                        }
+                    } else if (scope->id == ScopeIdFnDef) {
+                        break;
+                    } else {
+                        zig_unreachable();
+                    }
+                    scope = scope->parent;
+                }
+            }
+
             auto entry = ira->codegen->memoized_fn_eval_table.maybe_get(exec_scope);
             if (entry)
                 result = entry->value;
@@ -12935,6 +12980,18 @@ static IrInstGen *ir_analyze_fn_call(IrAnalyze *ira, Scope *scope, AstNode *sour
             break;
         }
 
+        // We are about to put ZigValues into a hash map. The hash of a lazy value and a
+        // fully resolved value must equal, and so we must resolve the lazy values here.
+        // The hash function asserts that none of the values are lazy.
+        for (size_t i = 0; i < generic_id->param_count; i += 1) {
+            ZigValue *generic_param = &generic_id->params[i];
+            if (generic_param->special != ConstValSpecialRuntime) {
+                if ((err = ir_resolve_lazy_recurse(source_node, generic_param))) {
+                    return ira->codegen->invalid_inst_gen;
+                }
+            }
+        }
+
         auto existing_entry = ira->codegen->generic_table.put_unique(generic_id, impl_fn);
         if (existing_entry) {
             // throw away all our work and use the existing function
@@ -14873,6 +14930,8 @@ static IrInstGen *ir_analyze_struct_field_ptr(IrAnalyze *ira, Scope *scope, AstN
                 struct_val->data.x_struct.fields = alloc_const_vals_ptrs(ira->codegen, struct_type->data.structure.src_field_count);
                 struct_val->special = ConstValSpecialStatic;
                 for (size_t i = 0; i < struct_type->data.structure.src_field_count; i += 1) {
+                    if (struct_type->data.structure.fields[i]->is_comptime)
+                        continue;
                     ZigValue *field_val = struct_val->data.x_struct.fields[i];
                     field_val->special = ConstValSpecialUndef;
                     field_val->type = resolve_struct_field_type(ira->codegen,
@@ -18247,7 +18306,9 @@ static ZigValue *get_const_field(IrAnalyze *ira, AstNode *source_node, ZigValue
 {
     Error err;
     ensure_field_index(struct_value->type, name, field_index);
-    ZigValue *val = struct_value->data.x_struct.fields[field_index];
+    TypeStructField *field = struct_value->type->data.structure.fields[field_index];
+    ZigValue *val = field->is_comptime ? field->init_val :
+        struct_value->data.x_struct.fields[field_index];
     if ((err = ir_resolve_const_val(ira->codegen, ira->new_irb.exec, source_node, val, UndefBad)))
         return nullptr;
     return val;
@@ -22422,7 +22483,7 @@ static void buf_write_value_bytes(CodeGen *codegen, uint8_t *buf, ZigValue *val)
                     size_t src_field_count = val->type->data.structure.src_field_count;
                     for (size_t field_i = 0; field_i < src_field_count; field_i += 1) {
                         TypeStructField *struct_field = val->type->data.structure.fields[field_i];
-                        if (struct_field->gen_index == SIZE_MAX)
+                        if (struct_field->gen_index == SIZE_MAX || struct_field->is_comptime)
                             continue;
                         ZigValue *field_val = val->data.x_struct.fields[field_i];
                         size_t offset = struct_field->offset;
@@ -22451,6 +22512,10 @@ static void buf_write_value_bytes(CodeGen *codegen, uint8_t *buf, ZigValue *val)
                         size_t used_bits = 0;
                         while (src_i < src_field_count) {
                             TypeStructField *field = val->type->data.structure.fields[src_i];
+                            if (field->is_comptime) {
+                                src_i += 1;
+                                continue;
+                            }
                             assert(field->gen_index != SIZE_MAX);
                             if (field->gen_index != gen_i)
                                 break;
@@ -22599,9 +22664,11 @@ static Error buf_read_value_bytes(IrAnalyze *ira, CodeGen *codegen, AstNode *sou
                     size_t src_field_count = val->type->data.structure.src_field_count;
                     val->data.x_struct.fields = alloc_const_vals_ptrs(codegen, src_field_count);
                     for (size_t field_i = 0; field_i < src_field_count; field_i += 1) {
+                        TypeStructField *struct_field = val->type->data.structure.fields[field_i];
+                        if (struct_field->is_comptime)
+                            continue;
                         ZigValue *field_val = val->data.x_struct.fields[field_i];
                         field_val->special = ConstValSpecialStatic;
-                        TypeStructField *struct_field = val->type->data.structure.fields[field_i];
                         field_val->type = struct_field->type_entry;
                         if (struct_field->gen_index == SIZE_MAX)
                             continue;
@@ -22634,6 +22701,10 @@ static Error buf_read_value_bytes(IrAnalyze *ira, CodeGen *codegen, AstNode *sou
                         uint64_t bit_offset = 0;
                         while (src_i < src_field_count) {
                             TypeStructField *field = val->type->data.structure.fields[src_i];
+                            if (field->is_comptime) {
+                                src_i += 1;
+                                continue;
+                            }
                             src_assert(field->gen_index != SIZE_MAX, source_node);
                             if (field->gen_index != gen_i)
                                 break;
@@ -25515,6 +25586,95 @@ static Error ir_resolve_lazy_raw(AstNode *source_node, ZigValue *val) {
     zig_unreachable();
 }
 
+static Error ir_resolve_lazy_recurse_array(AstNode *source_node, ZigValue *val, size_t len) {
+    Error err;
+    switch (val->data.x_array.special) {
+        case ConstArraySpecialUndef:
+        case ConstArraySpecialBuf:
+            return ErrorNone;
+        case ConstArraySpecialNone:
+            break;
+    }
+    ZigValue *elems = val->data.x_array.data.s_none.elements;
+
+    for (size_t i = 0; i < len; i += 1) {
+        if ((err = ir_resolve_lazy_recurse(source_node, &elems[i])))
+            return err;
+    }
+
+    return ErrorNone;
+}
+
+static Error ir_resolve_lazy_recurse(AstNode *source_node, ZigValue *val) {
+    Error err;
+    if ((err = ir_resolve_lazy_raw(source_node, val))) 
+        return err;
+    assert(val->special != ConstValSpecialRuntime);
+    assert(val->special != ConstValSpecialLazy);
+    if (val->special != ConstValSpecialStatic)
+        return ErrorNone;
+    switch (val->type->id) {
+        case ZigTypeIdOpaque:
+        case ZigTypeIdEnum:
+        case ZigTypeIdMetaType:
+        case ZigTypeIdBool:
+        case ZigTypeIdVoid:
+        case ZigTypeIdComptimeFloat:
+        case ZigTypeIdInt:
+        case ZigTypeIdComptimeInt:
+        case ZigTypeIdEnumLiteral:
+        case ZigTypeIdErrorSet:
+        case ZigTypeIdUndefined:
+        case ZigTypeIdNull:
+        case ZigTypeIdPointer:
+        case ZigTypeIdFn:
+        case ZigTypeIdAnyFrame:
+        case ZigTypeIdBoundFn:
+        case ZigTypeIdInvalid:
+        case ZigTypeIdUnreachable:
+        case ZigTypeIdFloat:
+            return ErrorNone;
+        case ZigTypeIdFnFrame:
+            zig_panic("TODO: ir_resolve_lazy_recurse ZigTypeIdFnFrame");
+        case ZigTypeIdUnion: {
+            ConstUnionValue *union_val = &val->data.x_union;
+            return ir_resolve_lazy_recurse(source_node, union_val->payload);
+        }
+        case ZigTypeIdVector:
+            return ir_resolve_lazy_recurse_array(source_node, val, val->type->data.vector.len);
+        case ZigTypeIdArray:
+            return ir_resolve_lazy_recurse_array(source_node, val, val->type->data.array.len);
+        case ZigTypeIdStruct:
+            for (size_t i = 0; i < val->type->data.structure.src_field_count; i += 1) {
+                ZigValue *field = val->data.x_struct.fields[i];
+                if (val->type->data.structure.fields[i]->is_comptime) {
+                    // comptime struct fields do not need to be resolved because
+                    // they are not part of the value.
+                    continue;
+                }
+                if ((err = ir_resolve_lazy_recurse(source_node, field)))
+                    return err;
+            }
+            return ErrorNone;
+        case ZigTypeIdOptional:
+            if (get_src_ptr_type(val->type) != nullptr)
+                return ErrorNone;
+            if (val->data.x_optional == nullptr)
+                return ErrorNone;
+
+            return ir_resolve_lazy_recurse(source_node, val->data.x_optional);
+        case ZigTypeIdErrorUnion: {
+            bool is_err = val->data.x_err_union.error_set->data.x_err_set != nullptr;
+            if (is_err) {
+                return ir_resolve_lazy_recurse(source_node, val->data.x_err_union.error_set);
+            } else {
+                return ir_resolve_lazy_recurse(source_node, val->data.x_err_union.payload);
+            }
+        }
+    }
+    zig_unreachable();
+}
+
 Error ir_resolve_lazy(CodeGen *codegen, AstNode *source_node, ZigValue *val) {
     Error err;
     if ((err = ir_resolve_lazy_raw(source_node, val))) {