Use a slice for InstMap instead of std.HashMap

The `sema.inst_map` datastructure is very often accessed. All
instructions that reference the result of other instructions does a
lookup into this field. Because of this, a significant amount of time,
is spent in `std.HashMap.get`.

This commit replaces the `HashMap` with a simpler data structure that
uses the zir indexes to index into a slice for the result. See the data
structure doc comment for more info.

2 files changed, 125 insertions, 23 deletions

diff --git a/src/Module.zig b/src/Module.zig
index bb03616dff..b7930615c8 100644
--- a/src/Module.zig
+++ b/src/Module.zig
@@ -5582,7 +5582,7 @@ pub fn analyzeFnBody(mod: *Module, func: *Fn, arena: Allocator) SemaError!Air {
     const runtime_params_len = @intCast(u32, fn_ty_info.param_types.len);
     try inner_block.instructions.ensureTotalCapacityPrecise(gpa, runtime_params_len);
     try sema.air_instructions.ensureUnusedCapacity(gpa, fn_info.total_params_len * 2); // * 2 for the `addType`
-    try sema.inst_map.ensureUnusedCapacity(gpa, fn_info.total_params_len);
+    try sema.inst_map.ensureSpaceForInstructions(gpa, fn_info.param_body);
 
     var runtime_param_index: usize = 0;
     var total_param_index: usize = 0;
diff --git a/src/Sema.zig b/src/Sema.zig
index c06afb9c51..b8b8f3738a 100644
--- a/src/Sema.zig
+++ b/src/Sema.zig
@@ -117,7 +117,103 @@ const build_options = @import("build_options");
 pub const default_branch_quota = 1000;
 pub const default_reference_trace_len = 2;
 
-pub const InstMap = std.AutoHashMapUnmanaged(Zir.Inst.Index, Air.Inst.Ref);
+/// Stores the mapping from `Zir.Inst.Index -> Air.Inst.Ref`, which is used by sema to resolve
+/// instructions during analysis.
+/// Instead of a hash table approach, InstMap is simply a slice that is indexed into using the
+/// zir instruction index and a start offset. An index is not pressent in the map if the value
+/// at the index is `Air.Inst.Ref.none`.
+/// `ensureSpaceForInstructions` can be called to force InstMap to have a mapped range that
+/// includes all instructions in a slice. After calling this function, `putAssumeCapacity*` can
+/// be called safely for any of the instructions passed in.
+pub const InstMap = struct {
+    items: []Air.Inst.Ref = &[_]Air.Inst.Ref{},
+    start: Zir.Inst.Index = 0,
+
+    pub fn deinit(map: InstMap, allocator: mem.Allocator) void {
+        allocator.free(map.items);
+    }
+
+    pub fn get(map: InstMap, key: Zir.Inst.Index) ?Air.Inst.Ref {
+        if (!map.contains(key)) return null;
+        return map.items[key - map.start];
+    }
+
+    pub fn putAssumeCapacity(
+        map: *InstMap,
+        key: Zir.Inst.Index,
+        ref: Air.Inst.Ref,
+    ) void {
+        map.items[key - map.start] = ref;
+    }
+
+    pub fn putAssumeCapacityNoClobber(
+        map: *InstMap,
+        key: Zir.Inst.Index,
+        ref: Air.Inst.Ref,
+    ) void {
+        assert(!map.contains(key));
+        map.putAssumeCapacity(key, ref);
+    }
+
+    pub const GetOrPutResult = struct {
+        value_ptr: *Air.Inst.Ref,
+        found_existing: bool,
+    };
+
+    pub fn getOrPutAssumeCapacity(
+        map: *InstMap,
+        key: Zir.Inst.Index,
+    ) GetOrPutResult {
+        const index = key - map.start;
+        return GetOrPutResult{
+            .value_ptr = &map.items[index],
+            .found_existing = map.items[index] != .none,
+        };
+    }
+
+    pub fn remove(map: InstMap, key: Zir.Inst.Index) bool {
+        if (!map.contains(key)) return false;
+        map.items[key - map.start] = .none;
+        return true;
+    }
+
+    pub fn contains(map: InstMap, key: Zir.Inst.Index) bool {
+        return map.items[key - map.start] != .none;
+    }
+
+    pub fn ensureSpaceForInstructions(
+        map: *InstMap,
+        allocator: mem.Allocator,
+        insts: []const Zir.Inst.Index,
+    ) !void {
+        const min_max = mem.minMax(Zir.Inst.Index, insts);
+        const start = min_max.min;
+        const end = min_max.max;
+        if (map.start <= start and end < map.items.len + map.start)
+            return;
+
+        const old_start = if (map.items.len == 0) start else map.start;
+        var better_capacity = map.items.len;
+        var better_start = old_start;
+        while (true) {
+            const extra_capacity = better_capacity / 2 + 16;
+            better_capacity += extra_capacity;
+            better_start -|= @intCast(Zir.Inst.Index, extra_capacity / 2);
+            if (better_start <= start and end < better_capacity + better_start)
+                break;
+        }
+
+        const start_diff = old_start - better_start;
+        const new_items = try allocator.alloc(Air.Inst.Ref, better_capacity);
+        mem.set(Air.Inst.Ref, new_items[0..start_diff], .none);
+        mem.copy(Air.Inst.Ref, new_items[start_diff..], map.items);
+        mem.set(Air.Inst.Ref, new_items[start_diff + map.items.len ..], .none);
+
+        allocator.free(map.items);
+        map.items = new_items;
+        map.start = @intCast(Zir.Inst.Index, better_start);
+    }
+};
 
 /// This is the context needed to semantically analyze ZIR instructions and
 /// produce AIR instructions.
@@ -753,6 +849,8 @@ fn analyzeBodyInner(
 ) CompileError!Zir.Inst.Index {
     // No tracy calls here, to avoid interfering with the tail call mechanism.
 
+    try sema.inst_map.ensureSpaceForInstructions(sema.gpa, body);
+
     const parent_capture_scope = block.wip_capture_scope;
 
     var wip_captures = WipCaptureScope{
@@ -1443,7 +1541,7 @@ fn analyzeBodyInner(
                         labeled_block.destroy(gpa);
                         assert(sema.post_hoc_blocks.remove(new_block_inst));
                     }
-                    try map.put(gpa, inst, block_result);
+                    map.putAssumeCapacity(inst, block_result);
                     i += 1;
                     continue;
                 }
@@ -1622,7 +1720,7 @@ fn analyzeBodyInner(
                 const extra = sema.code.extraData(Zir.Inst.DeferErrCode, inst_data.payload_index).data;
                 const defer_body = sema.code.extra[extra.index..][0..extra.len];
                 const err_code = try sema.resolveInst(inst_data.err_code);
-                try sema.inst_map.put(sema.gpa, extra.remapped_err_code, err_code);
+                sema.inst_map.putAssumeCapacity(extra.remapped_err_code, err_code);
                 const break_inst = sema.analyzeBodyInner(block, defer_body) catch |err| switch (err) {
                     error.ComptimeBreak => sema.comptime_break_inst,
                     else => |e| return e,
@@ -1633,7 +1731,7 @@ fn analyzeBodyInner(
         };
         if (sema.typeOf(air_inst).isNoReturn())
             break always_noreturn;
-        try map.put(sema.gpa, inst, air_inst);
+        map.putAssumeCapacity(inst, air_inst);
         i += 1;
     } else unreachable;
 
@@ -5980,7 +6078,7 @@ fn zirCall(
         }
 
         const param_ty_inst = try sema.addType(param_ty);
-        try sema.inst_map.put(sema.gpa, inst, param_ty_inst);
+        sema.inst_map.putAssumeCapacity(inst, param_ty_inst);
 
         const resolved = try sema.resolveBody(block, args_body[arg_start..arg_end], inst);
         const resolved_ty = sema.typeOf(resolved);
@@ -6368,6 +6466,8 @@ fn analyzeCall(
         // which means its parameter type expressions must be resolved in order and used
         // to successively coerce the arguments.
         const fn_info = sema.code.getFnInfo(module_fn.zir_body_inst);
+        try sema.inst_map.ensureSpaceForInstructions(sema.gpa, fn_info.param_body);
+
         var arg_i: usize = 0;
         for (fn_info.param_body) |inst| {
             sema.analyzeInlineCallArg(
@@ -6662,7 +6762,7 @@ fn analyzeInlineCallArg(
             const casted_arg = try sema.coerce(arg_block, param_ty, uncasted_arg, arg_src);
 
             if (is_comptime_call) {
-                try sema.inst_map.putNoClobber(sema.gpa, inst, casted_arg);
+                sema.inst_map.putAssumeCapacityNoClobber(inst, casted_arg);
                 const arg_val = sema.resolveConstMaybeUndefVal(arg_block, arg_src, casted_arg, "argument to function being called at comptime must be comptime-known") catch |err| {
                     if (err == error.AnalysisFail and param_block.comptime_reason != null) try param_block.comptime_reason.?.explain(sema, sema.err);
                     return err;
@@ -6686,13 +6786,13 @@ fn analyzeInlineCallArg(
                     .val = arg_val,
                 };
             } else if (zir_tags[inst] == .param_comptime or try sema.typeRequiresComptime(param_ty)) {
-                try sema.inst_map.putNoClobber(sema.gpa, inst, casted_arg);
+                sema.inst_map.putAssumeCapacityNoClobber(inst, casted_arg);
             } else if (try sema.resolveMaybeUndefVal(casted_arg)) |val| {
                 // We have a comptime value but we need a runtime value to preserve inlining semantics,
                 const wrapped = try sema.addConstant(param_ty, try Value.Tag.runtime_value.create(sema.arena, val));
-                try sema.inst_map.putNoClobber(sema.gpa, inst, wrapped);
+                sema.inst_map.putAssumeCapacityNoClobber(inst, wrapped);
             } else {
-                try sema.inst_map.putNoClobber(sema.gpa, inst, casted_arg);
+                sema.inst_map.putAssumeCapacityNoClobber(inst, casted_arg);
             }
 
             arg_i.* += 1;
@@ -6704,7 +6804,7 @@ fn analyzeInlineCallArg(
             const param_ty = sema.typeOf(uncasted_arg);
 
             if (is_comptime_call) {
-                try sema.inst_map.putNoClobber(sema.gpa, inst, uncasted_arg);
+                sema.inst_map.putAssumeCapacityNoClobber(inst, uncasted_arg);
                 const arg_val = sema.resolveConstMaybeUndefVal(arg_block, arg_src, uncasted_arg, "argument to function being called at comptime must be comptime-known") catch |err| {
                     if (err == error.AnalysisFail and param_block.comptime_reason != null) try param_block.comptime_reason.?.explain(sema, sema.err);
                     return err;
@@ -6728,13 +6828,13 @@ fn analyzeInlineCallArg(
                     .val = arg_val,
                 };
             } else if (zir_tags[inst] == .param_anytype_comptime or try sema.typeRequiresComptime(param_ty)) {
-                try sema.inst_map.putNoClobber(sema.gpa, inst, uncasted_arg);
+                sema.inst_map.putAssumeCapacityNoClobber(inst, uncasted_arg);
             } else if (try sema.resolveMaybeUndefVal(uncasted_arg)) |val| {
                 // We have a comptime value but we need a runtime value to preserve inlining semantics,
                 const wrapped = try sema.addConstant(param_ty, try Value.Tag.runtime_value.create(sema.arena, val));
-                try sema.inst_map.putNoClobber(sema.gpa, inst, wrapped);
+                sema.inst_map.putAssumeCapacityNoClobber(inst, wrapped);
             } else {
-                try sema.inst_map.putNoClobber(sema.gpa, inst, uncasted_arg);
+                sema.inst_map.putAssumeCapacityNoClobber(inst, uncasted_arg);
             }
 
             arg_i.* += 1;
@@ -7008,7 +7108,8 @@ fn instantiateGenericCall(
             child_block.params.deinit(gpa);
         }
 
-        try child_sema.inst_map.ensureUnusedCapacity(gpa, @intCast(u32, uncasted_args.len));
+        try child_sema.inst_map.ensureSpaceForInstructions(gpa, fn_info.param_body);
+
         var arg_i: usize = 0;
         for (fn_info.param_body) |inst| {
             var is_comptime = false;
@@ -8111,6 +8212,7 @@ fn resolveGenericBody(
             block.params.deinit(sema.gpa);
             block.params = prev_params;
         }
+
         const uncasted = sema.resolveBody(block, body, func_inst) catch |err| break :err err;
         const result = sema.coerce(block, dest_ty, uncasted, src) catch |err| break :err err;
         const val = sema.resolveConstValue(block, src, result, reason) catch |err| break :err err;
@@ -8660,7 +8762,7 @@ fn zirParam(
                     .is_comptime = comptime_syntax,
                     .name = param_name,
                 });
-                try sema.inst_map.putNoClobber(sema.gpa, inst, .generic_poison);
+                sema.inst_map.putAssumeCapacityNoClobber(inst, .generic_poison);
                 return;
             },
             else => |e| return e,
@@ -8676,7 +8778,7 @@ fn zirParam(
                 .is_comptime = comptime_syntax,
                 .name = param_name,
             });
-            try sema.inst_map.putNoClobber(sema.gpa, inst, .generic_poison);
+            sema.inst_map.putAssumeCapacityNoClobber(inst, .generic_poison);
             return;
         },
         else => |e| return e,
@@ -8700,7 +8802,7 @@ fn zirParam(
             // non-anytype parameter that ended up being a one-possible-type.
             // We don't want the parameter to be part of the instantiated function type.
             const result = try sema.addConstant(param_ty, opv);
-            try sema.inst_map.put(sema.gpa, inst, result);
+            sema.inst_map.putAssumeCapacity(inst, result);
             return;
         }
     }
@@ -8715,7 +8817,7 @@ fn zirParam(
         // If this is a comptime parameter we can add a constant generic_poison
         // since this is also a generic parameter.
         const result = try sema.addConstant(param_ty, Value.initTag(.generic_poison));
-        try sema.inst_map.putNoClobber(sema.gpa, inst, result);
+        sema.inst_map.putAssumeCapacityNoClobber(inst, result);
     } else {
         // Otherwise we need a dummy runtime instruction.
         const result_index = @intCast(Air.Inst.Index, sema.air_instructions.len);
@@ -8724,7 +8826,7 @@ fn zirParam(
             .data = .{ .ty = param_ty },
         });
         const result = Air.indexToRef(result_index);
-        try sema.inst_map.putNoClobber(sema.gpa, inst, result);
+        sema.inst_map.putAssumeCapacityNoClobber(inst, result);
     }
 }
 
@@ -8763,7 +8865,7 @@ fn zirParamAnytype(
         .is_comptime = comptime_syntax,
         .name = param_name,
     });
-    try sema.inst_map.put(sema.gpa, inst, .generic_poison);
+    sema.inst_map.putAssumeCapacity(inst, .generic_poison);
 }
 
 fn zirAs(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Air.Inst.Ref {
@@ -11220,7 +11322,7 @@ fn maybeErrorUnwrap(sema: *Sema, block: *Block, body: []const Zir.Inst.Index, op
         };
         if (sema.typeOf(air_inst).isNoReturn())
             return true;
-        try sema.inst_map.put(sema.gpa, inst, air_inst);
+        sema.inst_map.putAssumeCapacity(inst, air_inst);
     }
     unreachable;
 }
@@ -16348,7 +16450,7 @@ fn zirTryPtr(sema: *Sema, parent_block: *Block, inst: Zir.Inst.Index) CompileErr
 // break from an inline loop. In such case we must convert it to
 // a runtime break.
 fn addRuntimeBreak(sema: *Sema, child_block: *Block, break_data: BreakData) !void {
-    const gop = try sema.inst_map.getOrPut(sema.gpa, break_data.block_inst);
+    const gop = sema.inst_map.getOrPutAssumeCapacity(break_data.block_inst);
     const labeled_block = if (!gop.found_existing) blk: {
         try sema.post_hoc_blocks.ensureUnusedCapacity(sema.gpa, 1);