stage2: comptime function with the same args is memoized

 * Introduce `memoized_calls` to `Module` which stores all the comptime
   function calls that are cached. It is keyed on the `*Fn` and the
   comptime arguments, but it does not yet properly detect comptime function
   pointers and avoid memoizing in this case. So it will have false
   positives for when a comptime function call mutates data through a
   pointer parameter.
 * Sema: Add a new helper function: `resolveConstMaybeUndefVal`
 * Value: add `enumToInt` method and use it in `zirEnumToInt`. It is
   also used by the hashing function.
 * Value: fix representation of optionals to match error unions.
   Previously it would not handle nested optionals correctly. Now it
   matches the memory layout of error unions and supports nested
   optionals properly. This required changes in all the backends for
   generating optional constants.
 * TypedValue gains `eql` and `hash` methods.
 * Value: Implement hashing for floats, optionals, and enums.
   Additionally, the zig type tag is added to the hash, where it was not
   previously, so that values of differing types will get different
   hashes.

1 files changed, 73 insertions, 4 deletions

diff --git a/src/Module.zig b/src/Module.zig
index 29c091abd3..4ed39c9954 100644
--- a/src/Module.zig
+++ b/src/Module.zig
@@ -66,6 +66,10 @@ import_table: std.StringArrayHashMapUnmanaged(*Scope.File) = .{},
 /// to the same function.
 monomorphed_funcs: MonomorphedFuncsSet = .{},
 
+/// The set of all comptime function calls that have been cached so that future calls
+/// with the same parameters will get the same return value.
+memoized_calls: MemoizedCallSet = .{},
+
 /// We optimize memory usage for a compilation with no compile errors by storing the
 /// error messages and mapping outside of `Decl`.
 /// The ErrorMsg memory is owned by the decl, using Module's general purpose allocator.
@@ -157,6 +161,60 @@ const MonomorphedFuncsContext = struct {
     }
 };
 
+pub const MemoizedCallSet = std.HashMapUnmanaged(
+    MemoizedCall.Key,
+    MemoizedCall.Result,
+    MemoizedCall,
+    std.hash_map.default_max_load_percentage,
+);
+
+pub const MemoizedCall = struct {
+    pub const Key = struct {
+        func: *Fn,
+        args: []TypedValue,
+    };
+
+    pub const Result = struct {
+        val: Value,
+        arena: std.heap.ArenaAllocator.State,
+    };
+
+    pub fn eql(ctx: @This(), a: Key, b: Key) bool {
+        _ = ctx;
+
+        if (a.func != b.func) return false;
+
+        assert(a.args.len == b.args.len);
+        for (a.args) |a_arg, arg_i| {
+            const b_arg = b.args[arg_i];
+            if (!a_arg.eql(b_arg)) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    /// Must match `Sema.GenericCallAdapter.hash`.
+    pub fn hash(ctx: @This(), key: Key) u64 {
+        _ = ctx;
+
+        var hasher = std.hash.Wyhash.init(0);
+
+        // The generic function Decl is guaranteed to be the first dependency
+        // of each of its instantiations.
+        std.hash.autoHash(&hasher, @ptrToInt(key.func));
+
+        // This logic must be kept in sync with the logic in `analyzeCall` that
+        // computes the hash.
+        for (key.args) |arg| {
+            arg.hash(&hasher);
+        }
+
+        return hasher.final();
+    }
+};
+
 /// A `Module` has zero or one of these depending on whether `-femit-h` is enabled.
 pub const GlobalEmitH = struct {
     /// Where to put the output.
@@ -2255,15 +2313,26 @@ pub fn deinit(mod: *Module) void {
     }
     mod.export_owners.deinit(gpa);
 
-    var it = mod.global_error_set.keyIterator();
-    while (it.next()) |key| {
-        gpa.free(key.*);
+    {
+        var it = mod.global_error_set.keyIterator();
+        while (it.next()) |key| {
+            gpa.free(key.*);
+        }
+        mod.global_error_set.deinit(gpa);
     }
-    mod.global_error_set.deinit(gpa);
 
     mod.error_name_list.deinit(gpa);
     mod.test_functions.deinit(gpa);
     mod.monomorphed_funcs.deinit(gpa);
+
+    {
+        var it = mod.memoized_calls.iterator();
+        while (it.next()) |entry| {
+            gpa.free(entry.key_ptr.args);
+            entry.value_ptr.arena.promote(gpa).deinit();
+        }
+        mod.memoized_calls.deinit(gpa);
+    }
 }
 
 fn freeExportList(gpa: *Allocator, export_list: []*Export) void {