diff options
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | Variables.zig | 109 | ||||
| -rw-r--r-- | synth.zig | 172 |
3 files changed, 244 insertions, 42 deletions
@@ -1,5 +1,5 @@ .POSIX: -.PHONY: all clean install uninstall +.PHONY: all clean check install uninstall CXXFLAGS += -g -std=c++23 -Wextra -Werror LDLIBS += -lcommon -ldyninstAPI -linstructionAPI -lparseAPI # dyninst @@ -34,6 +34,9 @@ trace-call: trace-call.o helpers.o %: %.c e9compile $< +check: synth.zig + zig test $< + install: $(BIN:%=$(BIN_PREFIX)%) $(DATA:%=$(DATA_DIR)/%) $(BIN_PREFIX)%: % diff --git a/Variables.zig b/Variables.zig index 99f7061..9732afa 100644 --- a/Variables.zig +++ b/Variables.zig @@ -20,27 +20,29 @@ const Allocator = std.mem.Allocator; const Writer = std.io.Writer; const assert = std.debug.assert; const bytesAsSlice = std.mem.bytesAsSlice; +const comptimePrint = std.fmt.comptimePrint; const cwd = std.fs.cwd; const divCeil = std.math.divCeil; -const fields = std.meta.fields; +const eql = std.meta.eql; +const expect = std.testing.expect; +const maxInt = std.math.maxInt; +const minInt = std.math.minInt; const std = @import("std"); +const tags = std.meta.tags; pub const RegisterEnum = enum(u4) { rax, rbx, rcx, rdx, rsi, rdi, rsp, rbp, r8, r9, r10, r11, r12, r13, r14, r15, - - pub fn format(tag: RegisterEnum, writer: *Writer) Writer.Error!void { - try writer.print("{s}", .{ @tagName(tag) }); - } }; -const Register = i64; -const Registers = [fields(RegisterEnum).len]Register; +pub const Register = i64; +const Registers = [tags(RegisterEnum).len]Register; pub const signed_integers = .{ i64, i32, i16, i8 }; const alignment = @alignOf(Register); -comptime { - for (signed_integers) |Int| - assert(alignment >= @alignOf(Int)); + +test alignment { + inline for (signed_integers) |Int| + try expect(alignment >= @alignOf(Int)); } fn alignedSize(T: type, count: usize) !usize { @@ -85,9 +87,9 @@ pub fn init(allocator: Allocator, stack_size: usize, assert(try file.getEndPos() == file_size); assert(try file.read(buffer) == file_size); var offset: usize = 0; - inline for (registers) |reg| { + inline for (registers) |register| { const slice = bytesAsSlice(Register, bytes[offset..]); - slice[index] = reg; + slice[index] = register; offset += try alignedSize(Register, count); } inline for (signed_integers) |Int| { @@ -106,9 +108,82 @@ pub fn deinit(variables: Variables, allocator: Allocator) void { allocator.free(variables.bytes); } -pub fn register(variables: Variables, name: RegisterEnum) ![]const Register { - const aligned_size = try alignedSize(Register, variables.samples); - const offset = aligned_size * @intFromEnum(name); - const slice = bytesAsSlice(Register, variables.bytes[offset..]); - return @alignCast(slice[0..variables.samples]); +const ConstantEnum = enum(i64) { + max1 = maxInt(i1), + min2 = minInt(i2), + max2 = maxInt(i2), + min3 = minInt(i3), + max3 = maxInt(i3), + min4 = minInt(i4), + max4 = maxInt(i4), + min5 = minInt(i5), + max5 = maxInt(i5), + min6 = minInt(i6), + max6 = maxInt(i6), + min7 = minInt(i7), + max7 = maxInt(i7), + min8 = minInt(i8), + max8 = maxInt(i8), + min9 = minInt(i9), + min16 = minInt(i16), + max16 = maxInt(i16), + min17 = minInt(i17), + min32 = minInt(i32), + max32 = maxInt(i32), + min33 = minInt(i33), + min64 = minInt(i64), + max64 = maxInt(i64), +}; + +pub const Query = union(enum) { + constant: ConstantEnum, + register: RegisterEnum, + stack: usize, + + pub fn all(allocator: Allocator) Allocator.Error![]Query { + const constants = tags(ConstantEnum); + const registers = tags(RegisterEnum); + const n = constants.len + registers.len; + const queries = try allocator.alloc(Query, n); + for (queries[0..constants.len], constants) |*dest, src| + dest.* = .{ .constant = src }; + for (queries[constants.len..][0..registers.len], + registers) |*dest, src| + dest.* = .{ .register = src }; + return queries; + } + + pub fn skip(q: Query, r: Query, s: Query) bool { + return eql(q, r) or eql(r, s) or eql(s, q) + or q == .constant and r == .constant and s == .constant + or q != .constant and r != .constant and s != .constant; + } + + pub fn format(query: Query, writer: *Writer) Writer.Error!void { + switch (query) { + inline .constant, .register => |tag| + try writer.print("{s}", .{ @tagName(tag) }), + .stack => unreachable, + } + } +}; + +pub fn get(variables: Variables, query: Query, + tmp: []Register) ![]const Register { + switch (query) { + .constant => |constant| switch (constant) { + inline else => |tag| { + for (tmp) |*register| + register.* = @intFromEnum(tag); + return tmp; + }, + }, + .register => |tag| { + const aligned_size = try alignedSize(Register, variables.samples); + const offset = aligned_size * @intFromEnum(tag); + const slice = bytesAsSlice(Register, variables.bytes[offset..]); + return @alignCast(slice[0..variables.samples]); + }, + .stack => unreachable, + } } @@ -16,6 +16,7 @@ // You should have received a copy of the GNU Affero General Public License // along with taosc. If not, see <https://www.gnu.org/licenses/>. +const Allocator = std.mem.Allocator; const ArenaAllocator = std.heap.ArenaAllocator; const CompareOperator = std.math.CompareOperator; const Writer = std.io.Writer; @@ -23,37 +24,107 @@ const argsAlloc = std.process.argsAlloc; const argsFree = std.process.argsFree; const assert = std.debug.assert; const compare = std.math.compare; -const enums = std.enums; +const divTrunc = std.math.divTrunc; const exit = std.process.exit; const page_allocator = std.heap.page_allocator; const parseUnsigned = std.fmt.parseUnsigned; const print = std.debug.print; +const rem = std.math.rem; +const shl = std.math.shl; +const shr = std.math.shr; const std = @import("std"); const stdout = std.fs.File.stdout; +const tags = std.meta.tags; +const Register = Variables.Register; const RegisterEnum = Variables.RegisterEnum; const Variables = @import("Variables.zig"); const signed_integers = Variables.signed_integers; -const Variable = RegisterEnum; -const Expression = Variable; +comptime { + _ = Variables; // for test discovery +} + +const UnaryOperator = enum { + @"+", + @"-", + @"~", + + fn apply(op: UnaryOperator, val: Register) Register { + return switch (op) { + .@"+" => val, + .@"-" => -%val, + .@"~" => ~val, + }; + } +}; + +const Unary = struct { + op: UnaryOperator, + val: Variables.Query, + + pub fn format(un: Unary, writer: *Writer) Writer.Error!void { + try writer.print("{s}{f}", .{ @tagName(un.op), un.val }); + } +}; + +const ArithmeticOperator = enum { + @"+", @"-", @"*", @"/", @"%", + @"&", @"|", @"^", @"<<", @">>", + + fn apply(op: ArithmeticOperator, lhs: Register, rhs: Register) !Register { + return switch (op) { + .@"+" => lhs +% rhs, + .@"-" => lhs -% rhs, + .@"*" => lhs *% rhs, + .@"/" => try divTrunc(Register, lhs, rhs), + .@"%" => try rem(Register, lhs, rhs), + .@"&" => lhs & rhs, + .@"|" => lhs | rhs, + .@"^" => lhs ^ rhs, + .@"<<" => shl(Register, lhs, rhs), + .@">>" => shr(Register, lhs, rhs), + }; + } +}; + +const Arithmetic = struct { + lhs: Unary, + op: ArithmeticOperator, + rhs: Unary, + + pub fn format(arith: Arithmetic, writer: *Writer) Writer.Error!void { + try writer.print("{f} {s} {f}", .{ + arith.lhs, + @tagName(arith.op), + arith.rhs, + }); + } +}; + const Comparison = struct { - lhs: Expression, + lhs: Unary, op: CompareOperator, - rhs: Expression, + rhs: Arithmetic, - fn check(cmp: Comparison, bot: Variables, top: Variables) !bool { - for (try bot.register(cmp.lhs), try bot.register(cmp.rhs)) |lhs, rhs| - if (compare(lhs, cmp.op, rhs)) + fn check(cmp: Comparison, vars: Variables, expected: bool, + tmp: Temporaries) !bool { + for (try vars.get(cmp.lhs.val, tmp[0]), + try vars.get(cmp.rhs.lhs.val, tmp[1]), + try vars.get(cmp.rhs.rhs.val, tmp[2])) |v0, v1, v2| { + const arith = cmp.rhs.op.apply(cmp.rhs.lhs.op.apply(v1), + cmp.rhs.lhs.op.apply(v2)) catch return false; - for (try top.register(cmp.lhs), try top.register(cmp.rhs)) |lhs, rhs| - if (!compare(lhs, cmp.op, rhs)) + const actual = compare(cmp.lhs.op.apply(v0), cmp.op, arith); + if (if (expected) !actual else actual) return false; + } return true; } pub fn format(cmp: Comparison, writer: *Writer) Writer.Error!void { - try writer.print("{s} {f} {f}", .{ + try writer.print("{f} {s} {f}", .{ + cmp.lhs, switch (cmp.op) { .lt => "<", .lte => "<=", @@ -62,12 +133,74 @@ const Comparison = struct { .gt => ">", .neq => "!=", }, - cmp.lhs, cmp.rhs, }); } }; +const Temporaries = [3][]Register; + +fn process(writer: *Writer, bot: Variables, top: Variables, + v0: Variables.Query, v1: Variables.Query, v2: Variables.Query, + o0: UnaryOperator, o1: UnaryOperator, o2: UnaryOperator, + arith: ArithmeticOperator, cmp: CompareOperator, + bot_tmp: Temporaries, top_tmp: Temporaries) !void { + const predicate = Comparison{ + .lhs = .{ .op = o0, .val = v0 }, + .op = cmp, + .rhs = .{ + .lhs = .{ .op = o1, .val = v1 }, + .op = arith, + .rhs = .{ .op = o2, .val = v2 }, + }, + }; + if (try predicate.check(bot, false, bot_tmp)) + return; + if (try predicate.check(top, true, top_tmp)) + return; + try writer.print("{f}\n", .{ predicate }); +} + +fn mineOperator(writer: *Writer, bot: Variables, top: Variables, + v0: Variables.Query, v1: Variables.Query, v2: Variables.Query, + bot_tmp: Temporaries, top_tmp: Temporaries) !void { + for (tags(UnaryOperator)) |o0| + for (tags(UnaryOperator)) |o1| + for (tags(UnaryOperator)) |o2| + for (tags(ArithmeticOperator)) |arith| + for (tags(CompareOperator)) |cmp| + try process(writer, bot, top, v0, v1, v2, o0, o1, o2, + arith, cmp, bot_tmp, top_tmp); +} + +fn alloc_tmp(allocator: Allocator, len: usize) Allocator.Error!Temporaries { + var tmp = [_][]Register{ &.{} } ** 3; + errdefer free_tmp(allocator, tmp); + for (&tmp) |*variable| + variable.* = try allocator.alloc(Register, len); + return tmp; +} + +fn free_tmp(allocator: Allocator, tmp: Temporaries) void { + for (tmp) |variable| + allocator.free(variable); +} + +fn mine(allocator: Allocator, writer: *Writer, + bot: Variables, top: Variables) !void { + const bot_tmp = try alloc_tmp(allocator, bot.samples); + defer free_tmp(allocator, bot_tmp); + const top_tmp = try alloc_tmp(allocator, top.samples); + defer free_tmp(allocator, top_tmp); + + const variables = try Variables.Query.all(allocator); + defer allocator.free(variables); + for (variables) |v0| for (variables) |v1| for (variables) |v2| + if (!v0.skip(v1, v2)) + try mineOperator(writer, bot, top, v0, v1, v2, bot_tmp, top_tmp); + try writer.flush(); +} + pub fn main() !void { var buffer: [80]u8 = undefined; var writer = stdout().writer(&buffer); @@ -84,20 +217,11 @@ pub fn main() !void { exit(1); } const stack_size = try parseUnsigned(usize, args[1], 0); - inline for (signed_integers) |Int| - assert(stack_size % @sizeOf(Int) == 0); + inline for (signed_integers) |SignedInt| + assert(stack_size % @sizeOf(SignedInt) == 0); const bot = try Variables.init(allocator, stack_size, args[2]); defer bot.deinit(allocator); const top = try Variables.init(allocator, stack_size, args[3]); defer top.deinit(allocator); - - for (enums.values(RegisterEnum)) |lhs| - for (enums.values(RegisterEnum)) |rhs| - if (@intFromEnum(lhs) < @intFromEnum(rhs)) - for (enums.values(CompareOperator)) |op| { - const cmp = Comparison{ .lhs = lhs, .op = op, .rhs = rhs }; - if (try cmp.check(bot, top)) - try writer.interface.print("{f}\n", .{ cmp }); - }; - try writer.interface.flush(); + try mine(allocator, &writer.interface, bot, top); } |