summaryrefslogtreecommitdiff
path: root/src/instr/types.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-10 11:32:21 -0300
committerGabriel Schneider <[email protected]>2026-11-10 12:08:27 -0300
commitb426a8a99bcad81ecbb41d1f2a2e83738c29d8e1 (patch)
tree06e303f1f33ce53cfc2d8a2043e24f032877f9ad /src/instr/types.zig
parent7f363779cb99b0820cce69c433bcfab87bb3d709 (diff)
downloadcomputeranim-b426a8a99bcad81ecbb41d1f2a2e83738c29d8e1.tar.gz
computeranim-b426a8a99bcad81ecbb41d1f2a2e83738c29d8e1.zip
llvm: a pass that instruments for animation, its runtime, ztrace cc
llvm/pass.cpp is an LLVM pass plugin: lines, stores, loads, calls and variables, each call into the runtime carrying names and type descriptions, selected by globs (-ztrace-only, -ztrace-mem), before the optimizer by default. src/instr/rt.zig is the runtime (libztrace-rt.a), which also answers clang's own coverage and -finstrument-functions hooks; src/instr/types.zig the grammar of the type descriptions and its parser. ztrace cc adds all of it to a compiler command. test-llvm compiles fib, two sorts, a linked list and a BFS through ztrace cc and asserts on their recordings; bench-llvm measures what each selection costs. Co-Authored-By: Claude Fable 5.2 <[email protected]>
Diffstat (limited to 'src/instr/types.zig')
-rw-r--r--src/instr/types.zig215
1 files changed, 215 insertions, 0 deletions
diff --git a/src/instr/types.zig b/src/instr/types.zig
new file mode 100644
index 0000000..1f6615a
--- /dev/null
+++ b/src/instr/types.zig
@@ -0,0 +1,215 @@
+//! The type descriptions the pass (llvm/pass.cpp) attaches to variables and
+//! functions: what a viewer needs to draw a value from its bytes, with no
+//! DWARF. A `variable` event's a3 and a `call` event's a3 are the string ids
+//! of one:
+//!
+//! type := 'void'
+//! | KIND BITS i32 u64 f64, c8 a character, b8 a boolean, x128 opaque bits
+//! | '*' type a pointer or a reference: 8 bytes
+//! | '[' COUNT ']' type an array; [3][4]i32 is three rows of four
+//! | 'fn(' (type (',' type)*)? ')' type a function: its parameters ('...' when variadic), its result
+//! | ('struct' | 'union') '(' BYTES '){' field* '}'
+//! | 'enum(' type '){' (NAME '=' VALUE ';')* '}'
+//! | '`' NAME '`' a named type, described elsewhere
+//! field := NAME '@' BYTE ('.' BIT)? ':' type ';'
+//!
+//! A field sits at a byte offset. A bit-field adds the bit it starts at
+//! within that byte, counted from the least significant, and is as wide as
+//! its type: `[email protected]:u1`. An anonymous member or a C++ base has an empty
+//! NAME. A flexible or variable-length array has COUNT 0.
+//!
+//! A named type is `struct NAME`, `union NAME`, `enum NAME`, or a typedef's
+//! bare name (in C++ qualified: `struct v8::internal::Isolate`). What it is
+//! is one more string, with the id `defId(NAME)`: of all the pass's string
+//! ids (small numbers, given when the program starts) the only ones that
+//! follow from a text. A type the program only declares has none. So a
+//! struct is described once however many variables have it, and one that
+//! points to itself ends:
+//!
+//! struct node { int value; struct node *next; } *head;
+//! size_t n;
+//!
+//! type of head *`struct node`
+//! defId("struct node") struct(16){value@0:i32;next@8:*`struct node`;}
+//! type of n `size_t`
+//! defId("size_t") u64
+const std = @import("std");
+
+pub const Type = union(enum) {
+ void,
+ scalar: Scalar,
+ pointer: *const Type,
+ array: struct { len: u64, elem: *const Type },
+ function: struct { params: []const Type, variadic: bool, result: *const Type },
+ record: struct { kind: enum { @"struct", @"union" }, size: u64, fields: []const Field },
+ @"enum": struct { base: *const Type, items: []const Item },
+ /// Look its description up at `defId`.
+ named: []const u8,
+
+ /// Bytes a value takes. Null for void, a function, and a named type:
+ /// resolve the name first.
+ pub fn size(t: Type) ?u64 {
+ return switch (t) {
+ .void, .function, .named => null,
+ .scalar => |s| (s.bits + 7) / 8,
+ .pointer => 8,
+ .array => |a| a.len * (a.elem.size() orelse return null),
+ .record => |r| r.size,
+ .@"enum" => |e| e.base.size(),
+ };
+ }
+
+ /// The field of a struct or union by name.
+ pub fn field(t: Type, name: []const u8) ?Field {
+ if (t != .record) return null;
+ for (t.record.fields) |f| {
+ if (std.mem.eql(u8, f.name, name)) return f;
+ }
+ return null;
+ }
+};
+
+pub const Scalar = struct {
+ kind: enum(u8) { int = 'i', uint = 'u', float = 'f', char = 'c', bool = 'b', @"opaque" = 'x' },
+ bits: u16,
+};
+
+pub const Field = struct { name: []const u8, offset: u64, bit: u3 = 0, type: Type };
+pub const Item = struct { name: []const u8, value: i128 };
+
+/// The string id of the description of the named type `name`: FNV-1a of
+/// "=" and the name, with the top bit, which no numbered id has.
+pub fn defId(name: []const u8) u64 {
+ var h = std.hash.Fnv1a_64.init();
+ h.update("=");
+ h.update(name);
+ return h.final() | 1 << 63;
+}
+
+pub const Error = error{ BadType, OutOfMemory };
+
+/// A description as a tree, allocated in `arena`; its names point into `text`.
+pub fn parse(arena: std.mem.Allocator, text: []const u8) Error!Type {
+ var p: Parser = .{ .arena = arena, .text = text };
+ const t = try p.type();
+ return if (p.at == text.len) t else error.BadType;
+}
+
+const Parser = struct {
+ arena: std.mem.Allocator,
+ text: []const u8,
+ at: usize = 0,
+
+ fn eat(p: *Parser, word: []const u8) bool {
+ if (!std.mem.startsWith(u8, p.text[p.at..], word)) return false;
+ p.at += word.len;
+ return true;
+ }
+
+ /// The text up to `end`, which is consumed.
+ fn until(p: *Parser, end: u8) ![]const u8 {
+ const len = std.mem.indexOfScalar(u8, p.text[p.at..], end) orelse return error.BadType;
+ defer p.at += len + 1;
+ return p.text[p.at..][0..len];
+ }
+
+ fn number(p: *Parser, comptime T: type, end: u8) !T {
+ return std.fmt.parseInt(T, try p.until(end), 10) catch error.BadType;
+ }
+
+ fn box(p: *Parser, t: Type) !*const Type {
+ const out = try p.arena.create(Type);
+ out.* = t;
+ return out;
+ }
+
+ fn @"type"(p: *Parser) Error!Type {
+ if (p.eat("void")) return .void;
+ if (p.eat("*")) return .{ .pointer = try p.box(try p.type()) };
+ if (p.eat("`")) return .{ .named = try p.until('`') };
+ if (p.eat("[")) {
+ const len = try p.number(u64, ']');
+ return .{ .array = .{ .len = len, .elem = try p.box(try p.type()) } };
+ }
+ if (p.eat("fn(")) {
+ var params: std.ArrayList(Type) = .empty;
+ var variadic = false;
+ while (!p.eat(")")) {
+ if (p.eat("...")) variadic = true else try params.append(p.arena, try p.type());
+ _ = p.eat(",");
+ }
+ return .{ .function = .{ .params = params.items, .variadic = variadic, .result = try p.box(try p.type()) } };
+ }
+ if (p.eat("enum(")) {
+ const base = try p.box(try p.type());
+ if (!p.eat("){")) return error.BadType;
+ var items: std.ArrayList(Item) = .empty;
+ while (!p.eat("}")) try items.append(p.arena, .{ .name = try p.until('='), .value = try p.number(i128, ';') });
+ return .{ .@"enum" = .{ .base = base, .items = items.items } };
+ }
+ const is_union = p.eat("union(");
+ if (is_union or p.eat("struct(")) {
+ const bytes = try p.number(u64, ')');
+ if (!p.eat("{")) return error.BadType;
+ var fields: std.ArrayList(Field) = .empty;
+ while (!p.eat("}")) {
+ var f: Field = .{ .name = try p.until('@'), .offset = 0, .type = .void };
+ var place = std.mem.splitScalar(u8, try p.until(':'), '.');
+ f.offset = std.fmt.parseInt(u64, place.first(), 10) catch return error.BadType;
+ if (place.next()) |bit| f.bit = std.fmt.parseInt(u3, bit, 10) catch return error.BadType;
+ f.type = try p.type();
+ if (!p.eat(";")) return error.BadType;
+ try fields.append(p.arena, f);
+ }
+ return .{ .record = .{ .kind = if (is_union) .@"union" else .@"struct", .size = bytes, .fields = fields.items } };
+ }
+ if (p.at < p.text.len and std.mem.indexOfScalar(u8, "iufcbx", p.text[p.at]) != null) {
+ const start = p.at + 1;
+ p.at = start;
+ while (p.at < p.text.len and std.ascii.isDigit(p.text[p.at])) p.at += 1;
+ return .{ .scalar = .{ .kind = @enumFromInt(p.text[start - 1]), .bits = std.fmt.parseInt(u16, p.text[start..p.at], 10) catch return error.BadType } };
+ }
+ return error.BadType;
+ }
+};
+
+test "descriptions parse to what the pass meant" {
+ var arena_state: std.heap.ArenaAllocator = .init(std.testing.allocator);
+ defer arena_state.deinit();
+ const arena = arena_state.allocator();
+
+ const node = try parse(arena, "struct(16){value@0:i32;next@8:*`struct node`;}");
+ try std.testing.expectEqual(@as(?u64, 16), node.size());
+ try std.testing.expectEqual(Scalar{ .kind = .int, .bits = 32 }, node.field("value").?.type.scalar);
+ const next = node.field("next").?;
+ try std.testing.expectEqual(@as(u64, 8), next.offset);
+ try std.testing.expectEqualStrings("struct node", next.type.pointer.named);
+ try std.testing.expect(node.field("prev") == null);
+
+ // Bit-fields, an anonymous union member, an array of arrays.
+ const bits = try parse(arena, "struct(24){[email protected]:u3;[email protected]:i5;@8:union(8){d@0:f64;p@0:*void;};m@16:[2][3]c8;}");
+ try std.testing.expectEqual(@as(u3, 3), bits.field("b").?.bit);
+ try std.testing.expectEqual(Scalar{ .kind = .int, .bits = 5 }, bits.field("b").?.type.scalar);
+ try std.testing.expectEqual(@as(usize, 2), bits.field("").?.type.record.fields.len);
+ try std.testing.expectEqual(@as(?u64, 6), bits.field("m").?.type.size());
+ try std.testing.expectEqual(@as(u64, 3), bits.field("m").?.type.array.elem.array.len);
+
+ const f = (try parse(arena, "fn(*`struct node`,i32,...)*c8")).function;
+ try std.testing.expectEqual(@as(usize, 2), f.params.len);
+ try std.testing.expect(f.variadic);
+ try std.testing.expectEqual(Scalar{ .kind = .char, .bits = 8 }, f.result.pointer.scalar);
+ try std.testing.expectEqual(Type.void, (try parse(arena, "fn()void")).function.result.*);
+
+ const e = (try parse(arena, "enum(i32){LOW=-1;HIGH=5;}")).@"enum";
+ try std.testing.expectEqualStrings("HIGH", e.items[1].name);
+ try std.testing.expectEqual(@as(i128, -1), e.items[0].value);
+ // A name may hold anything but a backquote.
+ try std.testing.expectEqualStrings("struct std::pair<int, char *>", (try parse(arena, "[4]`struct std::pair<int, char *>`")).array.elem.named);
+
+ for ([_][]const u8{ "", "i", "i32x", "struct(8){a@0:i32}", "[x]i32", "*", "`open", "fn(i32" }) |bad| try std.testing.expectError(error.BadType, parse(arena, bad));
+
+ // FNV-1a of "=", worked out by hand. That the pass agrees is the list
+ // test of src/instr/test.zig, on a real program.
+ try std.testing.expectEqual(@as(u64, 0xaf63b04c8601a1c8), defId(""));
+ try std.testing.expectEqual(@as(u64, 1), defId("size_t") >> 63);
+}