From b426a8a99bcad81ecbb41d1f2a2e83738c29d8e1 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Tue, 10 Nov 2026 11:32:21 -0300 Subject: 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 --- src/instr/types.zig | 215 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 215 insertions(+) create mode 100644 src/instr/types.zig (limited to 'src/instr/types.zig') 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: `ready@4.3: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){a@0.0:u3;b@0.3: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", (try parse(arena, "[4]`struct std::pair`")).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); +} -- cgit v1.3