commit 2f64b278e3a8a4bf480cd2c8d2d021eeb7f45d64
parent a68660f16ce9b6ec0f00e71b01fc11ba298f3fe8
Author: Thomas Vigouroux <thomas.vigouroux@univ-grenoble-alpes.fr>
Date: Thu, 6 Jun 2024 16:19:55 +0200
perf: constant folding
Diffstat:
3 files changed, 76 insertions(+), 20 deletions(-)
diff --git a/src/chunk.zig b/src/chunk.zig
@@ -2,18 +2,31 @@ const std = @import("std");
const value = @import("value.zig");
pub const Op = union(enum) {
+ // Finish execution of current function
@"return",
+
+ // ..[a] -> ..
pop,
+ // .. -> ..[c]
@"constant": usize,
+
+ // ..[v].. -> ..[v]..[v]
@"local": usize,
+
+ // ..[scope...][top] -> ..[top]
popscope: usize,
+ // ..[a] -> ..[-a]
negate,
+
+ // ..[r][l] -> ..[l op r]
add,
substract,
multiply,
pow,
+
+ // ..[r][l] -> ..[l/r][l%r]
div
};
diff --git a/src/compile.zig b/src/compile.zig
@@ -3,6 +3,9 @@ const v = @import("value.zig");
const c = @import("chunk.zig");
const complog = std.log.scoped(.compile);
+
+const Storage = union(enum) { local: usize, value: *v.Value };
+
pub const Compiler = struct {
const Self = @This();
@@ -10,8 +13,8 @@ pub const Compiler = struct {
val: *v.Value,
chunk: c.Chunk,
- // Variable management
- sym_map: std.StringHashMap(usize),
+ // Variable management (+ constant folding)
+ sym_map: std.StringHashMap(Storage),
scope_depth: usize,
pub fn init(all: std.mem.Allocator, val: *v.Value) !Self {
@@ -19,7 +22,7 @@ pub const Compiler = struct {
.all = all,
.val = val.ref(),
.chunk = c.Chunk.init(all),
- .sym_map = std.StringHashMap(usize).init(all),
+ .sym_map = std.StringHashMap(Storage).init(all),
.scope_depth = 0,
};
}
@@ -30,15 +33,45 @@ pub const Compiler = struct {
self.sym_map.deinit();
}
+ fn isConstant(self: *Self, val: *v.Value) ?*v.Value {
+ if (val.isA(.number) or val.isA(.nil)) {
+ return val;
+ }
+
+ switch (val.val) {
+ .symbol => |sym| {
+ if (self.sym_map.get(sym)) |store| {
+ switch (store) {
+ .value => |cval| return cval,
+ else => {}
+ }
+ }
+ },
+ else => {},
+ }
+ return null;
+ }
+
fn compileInner(self: *Self, val: *v.Value) !void {
switch (val.val) {
- .number, .nil => {
+ .number, .nil, .true, .false => {
const cst = try self.chunk.addConstant(val.ref());
try self.chunk.write(.{ .constant = cst });
},
.symbol => |sym| {
- if (self.sym_map.get(sym)) |index| {
- try self.chunk.write(.{ .local = index });
+ if (self.sym_map.get(sym)) |store| {
+ switch (store) {
+ .local => |index| {
+ try self.chunk.write(.{ .local = index });
+ },
+
+ // This variant takes care of constant folding
+ // actual constant folding is done when generating the symbol
+ .value => |cst| {
+ const cval = try self.chunk.addConstant(cst.ref());
+ try self.chunk.write(.{ .constant = cval });
+ }
+ }
} else {
return error.UndefinedVariable;
}
@@ -99,19 +132,36 @@ pub const Compiler = struct {
return error.InvalidArgType;
}
- try self.compileInner(sval);
- complog.debug("{s} is at depth {}", .{ sym.val.symbol, self.scope_depth });
- try self.sym_map.put(sym.val.symbol, self.scope_depth);
- self.scope_depth += 1;
+ // Perform constant folding !!
+ const storage: Storage = if (self.isConstant(sval)) |cval|
+ .{ .value = cval }
+ else blk: {
+ try self.compileInner(sval);
+ complog.debug("{s} is at depth {}", .{ sym.val.symbol, self.scope_depth });
+ const loc = .{ .local = self.scope_depth };
+ self.scope_depth += 1;
+ break :blk loc;
+ };
+
+ try self.sym_map.put(sym.val.symbol, storage);
}
try self.compileInner(lst[2]);
// Now, remove the bindings of the variables
- try self.chunk.write(.{ .popscope = blist.len / 2});
+ var to_pop: usize = 0;
for (0..blist.len / 2) |idx| {
- _ = self.sym_map.remove(blist[2 * idx].val.symbol);
- self.scope_depth -= 1;
+ const got = self.sym_map.fetchRemove(blist[2*idx].val.symbol).?;
+ switch (got.value) {
+ .local => {
+ to_pop += 1;
+ self.scope_depth -= 1;
+ },
+ .value => {},
+ }
+ }
+ if (to_pop != 0) {
+ try self.chunk.write(.{.popscope = to_pop});
}
},
}
diff --git a/src/vm.zig b/src/vm.zig
@@ -53,13 +53,11 @@ pub const VM = struct {
}
switch (instr) {
- // .. -> ..[c]
.constant => |vindex| {
const val = self.cchunk.values.items[vindex];
try self.push(val.ref());
},
- // ..[v].. -> ..[v]..[v]
.@"local" => |vindex| {
const val = self.stack.items[vindex];
try self.push(val.ref());
@@ -72,7 +70,6 @@ pub const VM = struct {
.pop => (try self.pop()).unref(),
- // ..[scope...][top] -> ..[top]
.popscope => |amount| {
const topval = try self.pop();
@@ -83,7 +80,6 @@ pub const VM = struct {
try self.push(topval);
},
- // ..[a] -> ..[-a]
.negate => {
var val = try self.pop();
defer val.unref();
@@ -99,8 +95,6 @@ pub const VM = struct {
try self.push(new);
},
- // Pops 2 pushes 2
- // ..[r][l] -> ..[l/r][l%r]
.div => {
var left = try self.pop();
defer left.unref();
@@ -117,7 +111,6 @@ pub const VM = struct {
try self.push(try v.Value.newInt(self.all, rem));
},
- // ..[r][l] -> ..[l op r]
inline .add, .multiply, .substract, .pow => |_, tag| {
var left = try self.pop();
defer left.unref();
