diff options
Diffstat (limited to 'src/Module.zig')
| -rw-r--r-- | src/Module.zig | 828 |
1 files changed, 606 insertions, 222 deletions
diff --git a/src/Module.zig b/src/Module.zig index 716ea7c9e5..b51ceda1a9 100644 --- a/src/Module.zig +++ b/src/Module.zig @@ -144,10 +144,26 @@ global_error_set: GlobalErrorSet = .{}, /// Maximum amount of distinct error values, set by --error-limit error_limit: ErrorInt, -/// Incrementing integer used to compare against the corresponding Decl -/// field to determine whether a Decl's status applies to an ongoing update, or a -/// previous analysis. -generation: u32 = 0, +/// Value is the number of PO or outdated Decls which this Depender depends on. +potentially_outdated: std.AutoArrayHashMapUnmanaged(InternPool.Depender, u32) = .{}, +/// Value is the number of PO or outdated Decls which this Depender depends on. +/// Once this value drops to 0, the Depender is a candidate for re-analysis. +outdated: std.AutoArrayHashMapUnmanaged(InternPool.Depender, u32) = .{}, +/// This contains all `Depender`s in `outdated` whose PO dependency count is 0. +/// Such `Depender`s are ready for immediate re-analysis. +/// See `findOutdatedToAnalyze` for details. +outdated_ready: std.AutoArrayHashMapUnmanaged(InternPool.Depender, void) = .{}, +/// This contains a set of Decls which may not be in `outdated`, but are the +/// root Decls of files which have updated source and thus must be re-analyzed. +/// If such a Decl is only in this set, the struct type index may be preserved +/// (only the namespace might change). If such a Decl is also `outdated`, the +/// struct type index must be recreated. +outdated_file_root: std.AutoArrayHashMapUnmanaged(Decl.Index, void) = .{}, +/// This contains a list of Dependers whose analysis or codegen failed, but the +/// failure was something like running out of disk space, and trying again may +/// succeed. On the next update, we will flush this list, marking all members of +/// it as outdated. +retryable_failures: std.ArrayListUnmanaged(InternPool.Depender) = .{}, stage1_flags: packed struct { have_winmain: bool = false, @@ -364,21 +380,14 @@ pub const Decl = struct { alignment: Alignment, /// Populated when `has_tv`. @"addrspace": std.builtin.AddressSpace, - /// The direct parent namespace of the Decl. - /// Reference to externally owned memory. - /// In the case of the Decl corresponding to a file, this is - /// the namespace of the struct, since there is no parent. + /// The direct parent namespace of the Decl. In the case of the Decl + /// corresponding to a file, this is the namespace of the struct, since + /// there is no parent. src_namespace: Namespace.Index, - /// The scope which lexically contains this decl. A decl must depend - /// on its lexical parent, in order to ensure that this pointer is valid. - /// This scope is allocated out of the arena of the parent decl. + /// The scope which lexically contains this decl. src_scope: CaptureScope.Index, - /// An integer that can be checked against the corresponding incrementing - /// generation field of Module. This is used to determine whether `complete` status - /// represents pre- or post- re-analysis. - generation: u32, /// The AST node index of this declaration. /// Must be recomputed when the corresponding source file is modified. src_node: Ast.Node.Index, @@ -404,31 +413,20 @@ pub const Decl = struct { /// The file corresponding to this Decl had a parse error or ZIR error. /// There will be a corresponding ErrorMsg in Module.failed_files. file_failure, - /// This Decl might be OK but it depends on another one which did not successfully complete - /// semantic analysis. + /// This Decl might be OK but it depends on another one which did not + /// successfully complete semantic analysis. dependency_failure, /// Semantic analysis failure. /// There will be a corresponding ErrorMsg in Module.failed_decls. sema_failure, /// There will be a corresponding ErrorMsg in Module.failed_decls. - /// This indicates the failure was something like running out of disk space, - /// and attempting semantic analysis again may succeed. - sema_failure_retryable, - /// There will be a corresponding ErrorMsg in Module.failed_decls. - liveness_failure, - /// There will be a corresponding ErrorMsg in Module.failed_decls. codegen_failure, - /// There will be a corresponding ErrorMsg in Module.failed_decls. - /// This indicates the failure was something like running out of disk space, - /// and attempting codegen again may succeed. - codegen_failure_retryable, - /// Everything is done. During an update, this Decl may be out of date, depending - /// on its dependencies. The `generation` field can be used to determine if this - /// completion status occurred before or after a given update. + /// Sematic analysis and constant value codegen of this Decl has + /// succeeded. However, the Decl may be outdated due to an in-progress + /// update. Note that for a function, this does not mean codegen of the + /// function body succeded: that state is indicated by the function's + /// `analysis` field. complete, - /// A Module update is in progress, and this Decl has been flagged as being known - /// to require re-analysis. - outdated, }, /// Whether `typed_value`, `align`, `linksection` and `addrspace` are populated. has_tv: bool, @@ -680,14 +678,6 @@ pub const Decl = struct { return mod.namespacePtr(decl.src_namespace).file_scope; } - pub fn removeDependant(decl: *Decl, other: Decl.Index) void { - assert(decl.dependants.swapRemove(other)); - } - - pub fn removeDependency(decl: *Decl, other: Decl.Index) void { - assert(decl.dependencies.swapRemove(other)); - } - pub fn getExternDecl(decl: Decl, mod: *Module) OptionalIndex { assert(decl.has_tv); return switch (mod.intern_pool.indexToKey(decl.val.toIntern())) { @@ -734,8 +724,7 @@ pub const Namespace = struct { file_scope: *File, /// Will be a struct, enum, union, or opaque. ty: Type, - /// Direct children of the namespace. Used during an update to detect - /// which decls have been added/removed from source. + /// Direct children of the namespace. /// Declaration order is preserved via entry order. /// These are only declarations named directly by the AST; anonymous /// declarations are not stored here. @@ -838,14 +827,6 @@ pub const File = struct { /// undefined until `zir_loaded == true`. path_digest: Cache.BinDigest = undefined, - /// Used by change detection algorithm, after astgen, contains the - /// set of decls that existed in the previous ZIR but not in the new one. - deleted_decls: ArrayListUnmanaged(Decl.Index) = .{}, - /// Used by change detection algorithm, after astgen, contains the - /// set of decls that existed both in the previous ZIR and in the new one, - /// but their source code has been modified. - outdated_decls: ArrayListUnmanaged(Decl.Index) = .{}, - /// The most recent successful ZIR for this file, with no errors. /// This is only populated when a previously successful ZIR /// newly introduces compile errors during an update. When ZIR is @@ -898,8 +879,6 @@ pub const File = struct { gpa.free(file.sub_file_path); file.unload(gpa); } - file.deleted_decls.deinit(gpa); - file.outdated_decls.deinit(gpa); file.references.deinit(gpa); if (file.root_decl.unwrap()) |root_decl| { mod.destroyDecl(root_decl); @@ -2498,6 +2477,12 @@ pub fn deinit(zcu: *Zcu) void { zcu.global_error_set.deinit(gpa); + zcu.potentially_outdated.deinit(gpa); + zcu.outdated.deinit(gpa); + zcu.outdated_ready.deinit(gpa); + zcu.outdated_file_root.deinit(gpa); + zcu.retryable_failures.deinit(gpa); + zcu.test_functions.deinit(gpa); for (zcu.global_assembly.values()) |s| { @@ -2856,27 +2841,20 @@ pub fn astGenFile(mod: *Module, file: *File) !void { } if (file.prev_zir) |prev_zir| { - // Iterate over all Namespace objects contained within this File, looking at the - // previous and new ZIR together and update the references to point - // to the new one. For example, Decl name, Decl zir_decl_index, and Namespace - // decl_table keys need to get updated to point to the new memory, even if the - // underlying source code is unchanged. - // We do not need to hold any locks at this time because all the Decl and Namespace - // objects being touched are specific to this File, and the only other concurrent - // tasks are touching other File objects. try updateZirRefs(mod, file, prev_zir.*); - // At this point, `file.outdated_decls` and `file.deleted_decls` are populated, - // and semantic analysis will deal with them properly. // No need to keep previous ZIR. prev_zir.deinit(gpa); gpa.destroy(prev_zir); file.prev_zir = null; - } else if (file.root_decl.unwrap()) |root_decl| { - // This is an update, but it is the first time the File has succeeded - // ZIR. We must mark it outdated since we have already tried to - // semantically analyze it. - try file.outdated_decls.resize(gpa, 1); - file.outdated_decls.items[0] = root_decl; + } + + if (file.root_decl.unwrap()) |root_decl| { + // The root of this file must be re-analyzed, since the file has changed. + comp.mutex.lock(); + defer comp.mutex.unlock(); + + log.debug("outdated root Decl: {}", .{root_decl}); + try mod.outdated_file_root.put(gpa, root_decl, {}); } } @@ -2950,25 +2928,347 @@ fn loadZirCacheBody(gpa: Allocator, header: Zir.Header, cache_file: std.fs.File) return zir; } +/// This is called from the AstGen thread pool, so must acquire +/// the Compilation mutex when acting on shared state. fn updateZirRefs(zcu: *Module, file: *File, old_zir: Zir) !void { const gpa = zcu.gpa; + const new_zir = file.zir; var inst_map: std.AutoHashMapUnmanaged(Zir.Inst.Index, Zir.Inst.Index) = .{}; defer inst_map.deinit(gpa); - try mapOldZirToNew(gpa, old_zir, file.zir, &inst_map); + try mapOldZirToNew(gpa, old_zir, new_zir, &inst_map); + + const old_tag = old_zir.instructions.items(.tag); + const old_data = old_zir.instructions.items(.data); // TODO: this should be done after all AstGen workers complete, to avoid // iterating over this full set for every updated file. - for (zcu.intern_pool.tracked_insts.keys()) |*ti| { + for (zcu.intern_pool.tracked_insts.keys(), 0..) |*ti, idx_raw| { + const ti_idx: InternPool.TrackedInst.Index = @enumFromInt(idx_raw); if (!std.mem.eql(u8, &ti.path_digest, &file.path_digest)) continue; + const old_inst = ti.inst; ti.inst = inst_map.get(ti.inst) orelse { - // TODO: invalidate this `TrackedInst` via the dependency mechanism + // Tracking failed for this instruction. Invalidate associated `src_hash` deps. + zcu.comp.mutex.lock(); + defer zcu.comp.mutex.unlock(); + log.debug("tracking failed for %{d}", .{old_inst}); + try zcu.markDependeeOutdated(.{ .src_hash = ti_idx }); continue; }; + + if (old_zir.getAssociatedSrcHash(old_inst)) |old_hash| hash_changed: { + if (new_zir.getAssociatedSrcHash(ti.inst)) |new_hash| { + if (std.zig.srcHashEql(old_hash, new_hash)) { + break :hash_changed; + } + log.debug("hash for (%{d} -> %{d}) changed: {} -> {}", .{ + old_inst, + ti.inst, + std.fmt.fmtSliceHexLower(&old_hash), + std.fmt.fmtSliceHexLower(&new_hash), + }); + } + // The source hash associated with this instruction changed - invalidate relevant dependencies. + zcu.comp.mutex.lock(); + defer zcu.comp.mutex.unlock(); + try zcu.markDependeeOutdated(.{ .src_hash = ti_idx }); + } + + // If this is a `struct_decl` etc, we must invalidate any outdated namespace dependencies. + const has_namespace = switch (old_tag[@intFromEnum(old_inst)]) { + .extended => switch (old_data[@intFromEnum(old_inst)].extended.opcode) { + .struct_decl, .union_decl, .opaque_decl, .enum_decl => true, + else => false, + }, + else => false, + }; + if (!has_namespace) continue; + + var old_names: std.AutoArrayHashMapUnmanaged(InternPool.NullTerminatedString, void) = .{}; + defer old_names.deinit(zcu.gpa); + { + var it = old_zir.declIterator(old_inst); + while (it.next()) |decl_inst| { + const decl_name = old_zir.getDeclaration(decl_inst)[0].name; + switch (decl_name) { + .@"comptime", .@"usingnamespace", .unnamed_test, .decltest => continue, + _ => if (decl_name.isNamedTest(old_zir)) continue, + } + const name_zir = decl_name.toString(old_zir).?; + const name_ip = try zcu.intern_pool.getOrPutString( + zcu.gpa, + old_zir.nullTerminatedString(name_zir), + ); + try old_names.put(zcu.gpa, name_ip, {}); + } + } + var any_change = false; + { + var it = new_zir.declIterator(ti.inst); + while (it.next()) |decl_inst| { + const decl_name = old_zir.getDeclaration(decl_inst)[0].name; + switch (decl_name) { + .@"comptime", .@"usingnamespace", .unnamed_test, .decltest => continue, + _ => if (decl_name.isNamedTest(old_zir)) continue, + } + const name_zir = decl_name.toString(old_zir).?; + const name_ip = try zcu.intern_pool.getOrPutString( + zcu.gpa, + old_zir.nullTerminatedString(name_zir), + ); + if (!old_names.swapRemove(name_ip)) continue; + // Name added + any_change = true; + zcu.comp.mutex.lock(); + defer zcu.comp.mutex.unlock(); + try zcu.markDependeeOutdated(.{ .namespace_name = .{ + .namespace = ti_idx, + .name = name_ip, + } }); + } + } + // The only elements remaining in `old_names` now are any names which were removed. + for (old_names.keys()) |name_ip| { + any_change = true; + zcu.comp.mutex.lock(); + defer zcu.comp.mutex.unlock(); + try zcu.markDependeeOutdated(.{ .namespace_name = .{ + .namespace = ti_idx, + .name = name_ip, + } }); + } + + if (any_change) { + zcu.comp.mutex.lock(); + defer zcu.comp.mutex.unlock(); + try zcu.markDependeeOutdated(.{ .namespace = ti_idx }); + } } } +pub fn markDependeeOutdated(zcu: *Zcu, dependee: InternPool.Dependee) !void { + log.debug("outdated dependee: {}", .{dependee}); + var it = zcu.intern_pool.dependencyIterator(dependee); + while (it.next()) |depender| { + if (zcu.outdated.contains(depender)) { + // We do not need to increment the PO dep count, as if the outdated + // dependee is a Decl, we had already marked this as PO. + continue; + } + const opt_po_entry = zcu.potentially_outdated.fetchSwapRemove(depender); + try zcu.outdated.putNoClobber( + zcu.gpa, + depender, + // We do not need to increment this count for the same reason as above. + if (opt_po_entry) |e| e.value else 0, + ); + log.debug("outdated: {}", .{depender}); + if (opt_po_entry != null) { + // This is a new entry with no PO dependencies. + try zcu.outdated_ready.put(zcu.gpa, depender, {}); + } + // If this is a Decl and was not previously PO, we must recursively + // mark dependencies on its tyval as PO. + if (opt_po_entry == null) switch (depender.unwrap()) { + .decl => |decl_index| try zcu.markDeclDependenciesPotentiallyOutdated(decl_index), + .func => {}, + }; + } +} + +fn markPoDependeeUpToDate(zcu: *Zcu, dependee: InternPool.Dependee) !void { + var it = zcu.intern_pool.dependencyIterator(dependee); + while (it.next()) |depender| { + if (zcu.outdated.getPtr(depender)) |po_dep_count| { + // This depender is already outdated, but it now has one + // less PO dependency! + po_dep_count.* -= 1; + if (po_dep_count.* == 0) { + try zcu.outdated_ready.put(zcu.gpa, depender, {}); + } + continue; + } + // This depender is definitely at least PO, because this Decl was just analyzed + // due to being outdated. + const ptr = zcu.potentially_outdated.getPtr(depender).?; + if (ptr.* > 1) { + ptr.* -= 1; + continue; + } + + // This dependency is no longer PO, i.e. is known to be up-to-date. + assert(zcu.potentially_outdated.swapRemove(depender)); + // If this is a Decl, we must recursively mark dependencies on its tyval + // as no longer PO. + switch (depender.unwrap()) { + .decl => |decl_index| try zcu.markPoDependeeUpToDate(.{ .decl_val = decl_index }), + .func => {}, + } + } +} + +/// Given a Decl which is newly outdated or PO, mark all dependers which depend +/// on its tyval as PO. +fn markDeclDependenciesPotentiallyOutdated(zcu: *Zcu, decl_index: Decl.Index) !void { + var it = zcu.intern_pool.dependencyIterator(.{ .decl_val = decl_index }); + while (it.next()) |po| { + if (zcu.outdated.getPtr(po)) |po_dep_count| { + // This dependency is already outdated, but it now has one more PO + // dependency. + if (po_dep_count.* == 0) { + _ = zcu.outdated_ready.swapRemove(po); + } + po_dep_count.* += 1; + continue; + } + if (zcu.potentially_outdated.getPtr(po)) |n| { + // There is now one more PO dependency. + n.* += 1; + continue; + } + try zcu.potentially_outdated.putNoClobber(zcu.gpa, po, 1); + // If this ia a Decl, we must recursively mark dependencies + // on its tyval as PO. + switch (po.unwrap()) { + .decl => |po_decl| try zcu.markDeclDependenciesPotentiallyOutdated(po_decl), + .func => {}, + } + } + // TODO: repeat the above for `decl_ty` dependencies when they are introduced +} + +pub fn findOutdatedToAnalyze(zcu: *Zcu) Allocator.Error!?InternPool.Depender { + if (!zcu.comp.debug_incremental) return null; + + if (zcu.outdated.count() == 0 and zcu.potentially_outdated.count() == 0) { + log.debug("findOutdatedToAnalyze: no outdated depender", .{}); + return null; + } + + // Our goal is to find an outdated Depender which itself has no outdated or + // PO dependencies. Most of the time, such a Depender will exist - we track + // them in the `outdated_ready` set for efficiency. However, this is not + // necessarily the case, since the Decl dependency graph may contain loops + // via mutually recursive definitions: + // pub const A = struct { b: *B }; + // pub const B = struct { b: *A }; + // In this case, we must defer to more complex logic below. + + if (zcu.outdated_ready.count() > 0) { + log.debug("findOutdatedToAnalyze: trivial '{s} {d}'", .{ + @tagName(zcu.outdated_ready.keys()[0].unwrap()), + switch (zcu.outdated_ready.keys()[0].unwrap()) { + inline else => |x| @intFromEnum(x), + }, + }); + return zcu.outdated_ready.keys()[0]; + } + + // Next, we will see if there is any outdated file root which was not in + // `outdated`. This set will be small (number of files changed in this + // update), so it's alright for us to just iterate here. + for (zcu.outdated_file_root.keys()) |file_decl| { + const decl_depender = InternPool.Depender.wrap(.{ .decl = file_decl }); + if (zcu.outdated.contains(decl_depender)) { + // Since we didn't hit this in the first loop, this Decl must have + // pending dependencies, so is ineligible. + continue; + } + if (zcu.potentially_outdated.contains(decl_depender)) { + // This Decl's struct may or may not need to be recreated depending + // on whether it is outdated. If we analyzed it now, we would have + // to assume it was outdated and recreate it! + continue; + } + log.debug("findOutdatedToAnalyze: outdated file root decl '{d}'", .{file_decl}); + return decl_depender; + } + + // There is no single Depender which is ready for re-analysis. Instead, we + // must assume that some Decl with PO dependencies is outdated - e.g. in the + // above example we arbitrarily pick one of A or B. We should select a Decl, + // since a Decl is definitely responsible for the loop in the dependency + // graph (since you can't depend on a runtime function analysis!). + + // The choice of this Decl could have a big impact on how much total + // analysis we perform, since if analysis concludes its tyval is unchanged, + // then other PO Dependers may be resolved as up-to-date. To hopefully avoid + // doing too much work, let's find a Decl which the most things depend on - + // the idea is that this will resolve a lot of loops (but this is only a + // heuristic). + + log.debug("findOutdatedToAnalyze: no trivial ready, using heuristic; {d} outdated, {d} PO", .{ + zcu.outdated.count(), + zcu.potentially_outdated.count(), + }); + + var chosen_decl_idx: ?Decl.Index = null; + var chosen_decl_dependers: u32 = undefined; + + for (zcu.outdated.keys()) |depender| { + const decl_index = switch (depender.unwrap()) { + .decl => |d| d, + .func => continue, + }; + + var n: u32 = 0; + var it = zcu.intern_pool.dependencyIterator(.{ .decl_val = decl_index }); + while (it.next()) |_| n += 1; + + if (chosen_decl_idx == null or n > chosen_decl_dependers) { + chosen_decl_idx = decl_index; + chosen_decl_dependers = n; + } + } + + for (zcu.potentially_outdated.keys()) |depender| { + const decl_index = switch (depender.unwrap()) { + .decl => |d| d, + .func => continue, + }; + + var n: u32 = 0; + var it = zcu.intern_pool.dependencyIterator(.{ .decl_val = decl_index }); + while (it.next()) |_| n += 1; + + if (chosen_decl_idx == null or n > chosen_decl_dependers) { + chosen_decl_idx = decl_index; + chosen_decl_dependers = n; + } + } + + log.debug("findOutdatedToAnalyze: heuristic returned Decl {d} ({d} dependers)", .{ + chosen_decl_idx.?, + chosen_decl_dependers, + }); + + return InternPool.Depender.wrap(.{ .decl = chosen_decl_idx.? }); +} + +/// During an incremental update, before semantic analysis, call this to flush all values from +/// `retryable_failures` and mark them as outdated so they get re-analyzed. +pub fn flushRetryableFailures(zcu: *Zcu) !void { + const gpa = zcu.gpa; + for (zcu.retryable_failures.items) |depender| { + if (zcu.outdated.contains(depender)) continue; + if (zcu.potentially_outdated.fetchSwapRemove(depender)) |kv| { + // This Depender was already PO, but we now consider it outdated. + // Any transitive dependencies are already marked PO. + try zcu.outdated.put(gpa, depender, kv.value); + continue; + } + // This Depender was not marked PO, but is now outdated. Mark it as + // such, then recursively mark transitive dependencies as PO. + try zcu.outdated.put(gpa, depender, 0); + switch (depender.unwrap()) { + .decl => |decl| try zcu.markDeclDependenciesPotentiallyOutdated(decl), + .func => {}, + } + } + zcu.retryable_failures.clearRetainingCapacity(); +} + pub fn mapOldZirToNew( gpa: Allocator, old_zir: Zir, @@ -3096,7 +3396,7 @@ pub fn mapOldZirToNew( } } -/// This ensures that the Decl will have a Type and Value populated. +/// This ensures that the Decl will have an up-to-date Type and Value populated. /// However the resolution status of the Type may not be fully resolved. /// For example an inferred error set is not resolved until after `analyzeFnBody`. /// is called. @@ -3106,40 +3406,57 @@ pub fn ensureDeclAnalyzed(mod: *Module, decl_index: Decl.Index) SemaError!void { const decl = mod.declPtr(decl_index); - const subsequent_analysis = switch (decl.analysis) { + // Determine whether or not this Decl is outdated, i.e. requires re-analysis + // even if `complete`. If a Decl is PO, we pessismistically assume that it + // *does* require re-analysis, to ensure that the Decl is definitely + // up-to-date when this function returns. + + // If analysis occurs in a poor order, this could result in over-analysis. + // We do our best to avoid this by the other dependency logic in this file + // which tries to limit re-analysis to Decls whose previously listed + // dependencies are all up-to-date. + + const decl_as_depender = InternPool.Depender.wrap(.{ .decl = decl_index }); + const was_outdated = mod.outdated.swapRemove(decl_as_depender) or + mod.potentially_outdated.swapRemove(decl_as_depender); + + if (was_outdated) { + _ = mod.outdated_ready.swapRemove(decl_as_depender); + } + + switch (decl.analysis) { .in_progress => unreachable, - .file_failure, + .file_failure => return error.AnalysisFail, + .sema_failure, - .sema_failure_retryable, - .liveness_failure, - .codegen_failure, .dependency_failure, - .codegen_failure_retryable, - => return error.AnalysisFail, - - .complete => return, + .codegen_failure, + => if (!was_outdated) return error.AnalysisFail, - .outdated => blk: { - if (build_options.only_c) unreachable; - // The exports this Decl performs will be re-discovered, so we remove them here - // prior to re-analysis. - try mod.deleteDeclExports(decl_index); + .complete => if (!was_outdated) return, - break :blk true; - }, + .unreferenced => {}, + } - .unreferenced => false, - }; + if (was_outdated) { + // The exports this Decl performs will be re-discovered, so we remove them here + // prior to re-analysis. + if (build_options.only_c) unreachable; + try mod.deleteDeclExports(decl_index); + } var decl_prog_node = mod.sema_prog_node.start("", 0); decl_prog_node.activate(); defer decl_prog_node.end(); - const type_changed = blk: { + const sema_result: SemaDeclResult = blk: { if (decl.zir_decl_index == .none and !mod.declIsRoot(decl_index)) { // Anonymous decl. We don't semantically analyze these. - break :blk false; // tv unchanged + break :blk .{ + .invalidate_decl_val = false, + .invalidate_decl_ref = false, + }; } break :blk mod.semaDecl(decl_index) catch |err| switch (err) { @@ -3155,8 +3472,9 @@ pub fn ensureDeclAnalyzed(mod: *Module, decl_index: Decl.Index) SemaError!void { error.NeededSourceLocation => unreachable, error.GenericPoison => unreachable, else => |e| { - decl.analysis = .sema_failure_retryable; + decl.analysis = .sema_failure; try mod.failed_decls.ensureUnusedCapacity(mod.gpa, 1); + try mod.retryable_failures.append(mod.gpa, InternPool.Depender.wrap(.{ .decl = decl_index })); mod.failed_decls.putAssumeCapacityNoClobber(decl_index, try ErrorMsg.create( mod.gpa, decl.srcLoc(mod), @@ -3168,9 +3486,18 @@ pub fn ensureDeclAnalyzed(mod: *Module, decl_index: Decl.Index) SemaError!void { }; }; - if (subsequent_analysis) { - _ = type_changed; - @panic("TODO re-implement incremental compilation"); + // TODO: we do not yet have separate dependencies for decl values vs types. + if (was_outdated) { + if (sema_result.invalidate_decl_val or sema_result.invalidate_decl_ref) { + // This dependency was marked as PO, meaning dependees were waiting + // on its analysis result, and it has turned out to be outdated. + // Update dependees accordingly. + try mod.markDependeeOutdated(.{ .decl_val = decl_index }); + } else { + // This dependency was previously PO, but turned out to be up-to-date. + // We do not need to queue successive analysis. + try mod.markPoDependeeUpToDate(.{ .decl_val = decl_index }); + } } } @@ -3186,119 +3513,129 @@ pub fn ensureFuncBodyAnalyzed(zcu: *Zcu, func_index: InternPool.Index) SemaError switch (decl.analysis) { .unreferenced => unreachable, .in_progress => unreachable, - .outdated => unreachable, + + .codegen_failure => unreachable, // functions do not perform constant value generation .file_failure, .sema_failure, - .liveness_failure, - .codegen_failure, .dependency_failure, - .sema_failure_retryable, => return error.AnalysisFail, - .complete, .codegen_failure_retryable => { - switch (func.analysis(ip).state) { - .sema_failure, .dependency_failure => return error.AnalysisFail, - .none, .queued => {}, - .in_progress => unreachable, - .inline_only => unreachable, // don't queue work for this - .success => return, - } + .complete => {}, + } - const gpa = zcu.gpa; + const func_as_depender = InternPool.Depender.wrap(.{ .func = func_index }); + const was_outdated = zcu.outdated.swapRemove(func_as_depender) or + zcu.potentially_outdated.swapRemove(func_as_depender); - var tmp_arena = std.heap.ArenaAllocator.init(gpa); - defer tmp_arena.deinit(); - const sema_arena = tmp_arena.allocator(); + if (was_outdated) { + _ = zcu.outdated_ready.swapRemove(func_as_depender); + } - var air = zcu.analyzeFnBody(func_index, sema_arena) catch |err| switch (err) { - error.AnalysisFail => { - if (func.analysis(ip).state == .in_progress) { - // If this decl caused the compile error, the analysis field would - // be changed to indicate it was this Decl's fault. Because this - // did not happen, we infer here that it was a dependency failure. - func.analysis(ip).state = .dependency_failure; - } - return error.AnalysisFail; - }, - error.OutOfMemory => return error.OutOfMemory, - }; - defer air.deinit(gpa); + switch (func.analysis(ip).state) { + .success, + .sema_failure, + .dependency_failure, + .codegen_failure, + => if (!was_outdated) return error.AnalysisFail, + .none, .queued => {}, + .in_progress => unreachable, + .inline_only => unreachable, // don't queue work for this + } - const comp = zcu.comp; + const gpa = zcu.gpa; - const dump_air = builtin.mode == .Debug and comp.verbose_air; - const dump_llvm_ir = builtin.mode == .Debug and (comp.verbose_llvm_ir != null or comp.verbose_llvm_bc != null); + var tmp_arena = std.heap.ArenaAllocator.init(gpa); + defer tmp_arena.deinit(); + const sema_arena = tmp_arena.allocator(); - if (comp.bin_file == null and zcu.llvm_object == null and !dump_air and !dump_llvm_ir) { - return; + var air = zcu.analyzeFnBody(func_index, sema_arena) catch |err| switch (err) { + error.AnalysisFail => { + if (func.analysis(ip).state == .in_progress) { + // If this decl caused the compile error, the analysis field would + // be changed to indicate it was this Decl's fault. Because this + // did not happen, we infer here that it was a dependency failure. + func.analysis(ip).state = .dependency_failure; } + return error.AnalysisFail; + }, + error.OutOfMemory => return error.OutOfMemory, + }; + defer air.deinit(gpa); - var liveness = try Liveness.analyze(gpa, air, ip); - defer liveness.deinit(gpa); + const comp = zcu.comp; - if (dump_air) { - const fqn = try decl.getFullyQualifiedName(zcu); - std.debug.print("# Begin Function AIR: {}:\n", .{fqn.fmt(ip)}); - @import("print_air.zig").dump(zcu, air, liveness); - std.debug.print("# End Function AIR: {}\n\n", .{fqn.fmt(ip)}); - } + const dump_air = builtin.mode == .Debug and comp.verbose_air; + const dump_llvm_ir = builtin.mode == .Debug and (comp.verbose_llvm_ir != null or comp.verbose_llvm_bc != null); - if (std.debug.runtime_safety) { - var verify = Liveness.Verify{ - .gpa = gpa, - .air = air, - .liveness = liveness, - .intern_pool = ip, - }; - defer verify.deinit(); - - verify.verify() catch |err| switch (err) { - error.OutOfMemory => return error.OutOfMemory, - else => { - try zcu.failed_decls.ensureUnusedCapacity(gpa, 1); - zcu.failed_decls.putAssumeCapacityNoClobber( - decl_index, - try Module.ErrorMsg.create( - gpa, - decl.srcLoc(zcu), - "invalid liveness: {s}", - .{@errorName(err)}, - ), - ); - decl.analysis = .liveness_failure; - return error.AnalysisFail; - }, - }; - } + if (comp.bin_file == null and zcu.llvm_object == null and !dump_air and !dump_llvm_ir) { + return; + } - if (comp.bin_file) |lf| { - lf.updateFunc(zcu, func_index, air, liveness) catch |err| switch (err) { - error.OutOfMemory => return error.OutOfMemory, - error.AnalysisFail => { - decl.analysis = .codegen_failure; - }, - else => { - try zcu.failed_decls.ensureUnusedCapacity(gpa, 1); - zcu.failed_decls.putAssumeCapacityNoClobber(decl_index, try Module.ErrorMsg.create( - gpa, - decl.srcLoc(zcu), - "unable to codegen: {s}", - .{@errorName(err)}, - )); - decl.analysis = .codegen_failure_retryable; - }, - }; - } else if (zcu.llvm_object) |llvm_object| { - if (build_options.only_c) unreachable; - llvm_object.updateFunc(zcu, func_index, air, liveness) catch |err| switch (err) { - error.OutOfMemory => return error.OutOfMemory, - error.AnalysisFail => { - decl.analysis = .codegen_failure; - }, - }; - } - }, + var liveness = try Liveness.analyze(gpa, air, ip); + defer liveness.deinit(gpa); + + if (dump_air) { + const fqn = try decl.getFullyQualifiedName(zcu); + std.debug.print("# Begin Function AIR: {}:\n", .{fqn.fmt(ip)}); + @import("print_air.zig").dump(zcu, air, liveness); + std.debug.print("# End Function AIR: {}\n\n", .{fqn.fmt(ip)}); + } + + if (std.debug.runtime_safety) { + var verify = Liveness.Verify{ + .gpa = gpa, + .air = air, + .liveness = liveness, + .intern_pool = ip, + }; + defer verify.deinit(); + + verify.verify() catch |err| switch (err) { + error.OutOfMemory => return error.OutOfMemory, + else => { + try zcu.failed_decls.ensureUnusedCapacity(gpa, 1); + zcu.failed_decls.putAssumeCapacityNoClobber( + decl_index, + try Module.ErrorMsg.create( + gpa, + decl.srcLoc(zcu), + "invalid liveness: {s}", + .{@errorName(err)}, + ), + ); + func.analysis(ip).state = .codegen_failure; + return; + }, + }; + } + + if (comp.bin_file) |lf| { + lf.updateFunc(zcu, func_index, air, liveness) catch |err| switch (err) { + error.OutOfMemory => return error.OutOfMemory, + error.AnalysisFail => { + func.analysis(ip).state = .codegen_failure; + }, + else => { + try zcu.failed_decls.ensureUnusedCapacity(gpa, 1); + zcu.failed_decls.putAssumeCapacityNoClobber(decl_index, try Module.ErrorMsg.create( + gpa, + decl.srcLoc(zcu), + "unable to codegen: {s}", + .{@errorName(err)}, + )); + func.analysis(ip).state = .codegen_failure; + try zcu.retryable_failures.append(zcu.gpa, InternPool.Depender.wrap(.{ .func = func_index })); + }, + }; + } else if (zcu.llvm_object) |llvm_object| { + if (build_options.only_c) unreachable; + llvm_object.updateFunc(zcu, func_index, air, liveness) catch |err| switch (err) { + error.OutOfMemory => return error.OutOfMemory, + error.AnalysisFail => { + func.analysis(ip).state = .codegen_failure; + }, + }; } } @@ -3318,18 +3655,14 @@ pub fn ensureFuncBodyAnalysisQueued(mod: *Module, func_index: InternPool.Index) switch (decl.analysis) { .unreferenced => unreachable, .in_progress => unreachable, - .outdated => unreachable, .file_failure, .sema_failure, - .liveness_failure, .codegen_failure, .dependency_failure, - .sema_failure_retryable, - .codegen_failure_retryable, - // The function analysis failed, but we've already emitted an error for - // that. The callee doesn't need the function to be analyzed right now, - // so its analysis can safely continue. + // Analysis of the function Decl itself failed, but we've already + // emitted an error for that. The callee doesn't need the function to be + // analyzed right now, so its analysis can safely continue. => return, .complete => {}, @@ -3337,14 +3670,21 @@ pub fn ensureFuncBodyAnalysisQueued(mod: *Module, func_index: InternPool.Index) assert(decl.has_tv); + const func_as_depender = InternPool.Depender.wrap(.{ .func = func_index }); + const is_outdated = mod.outdated.contains(func_as_depender) or + mod.potentially_outdated.contains(func_as_depender); + switch (func.analysis(ip).state) { .none => {}, .queued => return, // As above, we don't need to forward errors here. - .sema_failure, .dependency_failure => return, + .sema_failure, + .dependency_failure, + .codegen_failure, + .success, + => if (!is_outdated) return, .in_progress => return, .inline_only => unreachable, // don't queue work for this - .success => return, } // Decl itself is safely analyzed, and body analysis is not yet queued @@ -3404,7 +3744,6 @@ pub fn semaFile(mod: *Module, file: *File) SemaError!void { new_decl.@"linksection" = .none; new_decl.alive = true; // This Decl corresponds to a File and is therefore always alive. new_decl.analysis = .in_progress; - new_decl.generation = mod.generation; if (file.status != .success_zir) { new_decl.analysis = .file_failure; @@ -3483,12 +3822,19 @@ pub fn semaFile(mod: *Module, file: *File) SemaError!void { }, .incremental => {}, } + + // Since this is our first time analyzing this file, there can be no dependencies on + // its root Decl. Thus, we do not need to invalidate any dependencies. } -/// Returns `true` if the Decl type changed. -/// Returns `true` if this is the first time analyzing the Decl. -/// Returns `false` otherwise. -fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { +const SemaDeclResult = packed struct { + /// Whether the value of a `decl_val` of this Decl changed. + invalidate_decl_val: bool, + /// Whether the type of a `decl_ref` of this Decl changed. + invalidate_decl_ref: bool, +}; + +fn semaDecl(mod: *Module, decl_index: Decl.Index) !SemaDeclResult { const tracy = trace(@src()); defer tracy.end(); @@ -3499,6 +3845,15 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { return error.AnalysisFail; } + if (mod.declIsRoot(decl_index)) { + // This comes from an `analyze_decl` job on an incremental update where + // this file changed. + @panic("TODO: update root Decl of modified file"); + } else if (decl.owns_tv) { + // We are re-analyzing an owner Decl (for a function or a namespace type). + @panic("TODO: update owner Decl"); + } + const gpa = mod.gpa; const zir = decl.getFileScope(mod).zir; @@ -3535,6 +3890,8 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { break :blk .none; }; + mod.intern_pool.removeDependenciesForDepender(gpa, InternPool.Depender.wrap(.{ .decl = decl_index })); + decl.analysis = .in_progress; var analysis_arena = std.heap.ArenaAllocator.init(gpa); @@ -3564,7 +3921,12 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { }; defer sema.deinit(); - assert(!mod.declIsRoot(decl_index)); + // Every Decl (other than file root Decls, which do not have a ZIR index) has a dependency on its own source. + try sema.declareDependency(.{ .src_hash = try ip.trackZir( + sema.gpa, + decl.getFileScope(mod), + decl.zir_decl_index.unwrap().?, + ) }); var block_scope: Sema.Block = .{ .parent = null, @@ -3620,9 +3982,12 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { decl.has_tv = true; decl.owns_tv = false; decl.analysis = .complete; - decl.generation = mod.generation; - return true; + // TODO: usingnamespace cannot currently participate in incremental compilation + return .{ + .invalidate_decl_val = true, + .invalidate_decl_ref = true, + }; } switch (ip.indexToKey(decl_tv.val.toIntern())) { @@ -3647,7 +4012,6 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { decl.has_tv = true; decl.owns_tv = owns_tv; decl.analysis = .complete; - decl.generation = mod.generation; const is_inline = decl.ty.fnCallingConvention(mod) == .Inline; if (decl.is_exported) { @@ -3658,15 +4022,16 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { // The scope needs to have the decl in it. try sema.analyzeExport(&block_scope, export_src, .{ .name = decl.name }, decl_index); } - return type_changed or is_inline != prev_is_inline; + // TODO: align, linksection, addrspace? + const changed = type_changed or is_inline != prev_is_inline; + return .{ + .invalidate_decl_val = changed, + .invalidate_decl_ref = changed, + }; } }, else => {}, } - var type_changed = true; - if (decl.has_tv) { - type_changed = !decl.ty.eql(decl_tv.ty, mod); - } decl.owns_tv = false; var queue_linker_work = false; @@ -3694,6 +4059,14 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { }, } + const old_has_tv = decl.has_tv; + // The following values are ignored if `!old_has_tv` + const old_ty = decl.ty; + const old_val = decl.val; + const old_align = decl.alignment; + const old_linksection = decl.@"linksection"; + const old_addrspace = decl.@"addrspace"; + decl.ty = decl_tv.ty; decl.val = Value.fromInterned((try decl_tv.val.intern(decl_tv.ty, mod))); decl.alignment = blk: { @@ -3735,7 +4108,17 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { }; decl.has_tv = true; decl.analysis = .complete; - decl.generation = mod.generation; + + const result: SemaDeclResult = if (old_has_tv) .{ + .invalidate_decl_val = !decl.ty.eql(old_ty, mod) or !decl.val.eql(old_val, decl.ty, mod), + .invalidate_decl_ref = !decl.ty.eql(old_ty, mod) or + decl.alignment != old_align or + decl.@"linksection" != old_linksection or + decl.@"addrspace" != old_addrspace, + } else .{ + .invalidate_decl_val = true, + .invalidate_decl_ref = true, + }; const has_runtime_bits = is_extern or (queue_linker_work and try sema.typeHasRuntimeBits(decl.ty)); @@ -3748,7 +4131,7 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { try mod.comp.work_queue.writeItem(.{ .codegen_decl = decl_index }); - if (type_changed and mod.emit_h != null) { + if (result.invalidate_decl_ref and mod.emit_h != null) { try mod.comp.work_queue.writeItem(.{ .emit_h_decl = decl_index }); } } @@ -3759,7 +4142,7 @@ fn semaDecl(mod: *Module, decl_index: Decl.Index) !bool { try sema.analyzeExport(&block_scope, export_src, .{ .name = decl.name }, decl_index); } - return type_changed; + return result; } pub const ImportFileResult = struct { @@ -4362,6 +4745,8 @@ pub fn analyzeFnBody(mod: *Module, func_index: InternPool.Index, arena: Allocato const decl_index = func.owner_decl; const decl = mod.declPtr(decl_index); + mod.intern_pool.removeDependenciesForDepender(gpa, InternPool.Depender.wrap(.{ .func = func_index })); + var comptime_mutable_decls = std.ArrayList(Decl.Index).init(gpa); defer comptime_mutable_decls.deinit(); @@ -4633,7 +5018,6 @@ pub fn allocateNewDecl( .analysis = .unreferenced, .zir_decl_index = .none, .src_scope = src_scope, - .generation = 0, .is_pub = false, .is_exported = false, .alive = false, @@ -4711,7 +5095,6 @@ pub fn initNewAnonDecl( new_decl.@"linksection" = .none; new_decl.has_tv = true; new_decl.analysis = .complete; - new_decl.generation = mod.generation; } pub fn errNoteNonLazy( @@ -5373,7 +5756,8 @@ pub fn linkerUpdateDecl(zcu: *Zcu, decl_index: Decl.Index) !void { "unable to codegen: {s}", .{@errorName(err)}, )); - decl.analysis = .codegen_failure_retryable; + decl.analysis = .codegen_failure; + try zcu.retryable_failures.append(zcu.gpa, InternPool.Depender.wrap(.{ .decl = decl_index })); }, }; } else if (zcu.llvm_object) |llvm_object| { |