summaryrefslogtreecommitdiff
path: root/src/instr/test.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/test.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/test.zig')
-rw-r--r--src/instr/test.zig464
1 files changed, 464 insertions, 0 deletions
diff --git a/src/instr/test.zig b/src/instr/test.zig
new file mode 100644
index 0000000..3b67c62
--- /dev/null
+++ b/src/instr/test.zig
@@ -0,0 +1,464 @@
+//! The pass and the runtime on real programs: each test reads the recording
+//! of a target the build compiled with `ztrace cc` and ran under `ztrace
+//! run` (their paths come from build/llvm.zig), as a viewer would: names
+//! and types from the recording alone.
+const std = @import("std");
+const linux = std.os.linux;
+const zt = @import("ztrace");
+const types = @import("types");
+const recordings = @import("recordings");
+
+const gpa = std.testing.allocator;
+const io = std.testing.io;
+const expect = std.testing.expect;
+const expectEqual = std.testing.expectEqual;
+const expectEqualSlices = std.testing.expectEqualSlices;
+const expectEqualStrings = std.testing.expectEqualStrings;
+
+const Item = struct { moment: u64, ev: zt.Event, payload: []const u8 };
+
+/// A recording, its events in order with the moment each is in, and the id
+/// the runtime gave each text.
+const Recording = struct {
+ arena: std.heap.ArenaAllocator,
+ trace: zt.Trace,
+ items: []Item,
+ ids: std.StringHashMapUnmanaged(u64) = .empty,
+
+ fn open(path: []const u8) !Recording {
+ var r: Recording = .{ .arena = .init(gpa), .trace = try zt.Trace.open(gpa, io, path), .items = &.{} };
+ errdefer r.close();
+ const arena = r.arena.allocator();
+ var items: std.ArrayList(Item) = .empty;
+ for (0..r.trace.len) |m| {
+ var events = try (try r.trace.moment(m)).events(arena);
+ while (events.next()) |item| {
+ try items.append(arena, .{ .moment = m, .ev = item.ev, .payload = item.payload });
+ if (item.ev.kind == .string) try r.ids.put(arena, item.payload, item.ev.a[0]);
+ }
+ }
+ r.items = items.items;
+ return r;
+ }
+
+ /// The id of a text; 0, which nothing has, for one the program lacks.
+ fn id(r: *const Recording, text: []const u8) u64 {
+ return r.ids.get(text) orelse 0;
+ }
+
+ fn close(r: *Recording) void {
+ r.trace.close();
+ r.arena.deinit();
+ }
+
+ fn last(r: *const Recording) !zt.store.Moment {
+ return r.trace.moment(r.trace.len - 1);
+ }
+
+ fn string(r: *Recording, of: u64) ![]const u8 {
+ const buf = try r.arena.allocator().alloc(u8, 4096);
+ return (try (try r.last()).string(of, buf)) orelse error.NoSuchString;
+ }
+
+ /// The first `variable` event of that name and type.
+ fn variable(r: *Recording, name: []const u8, type_text: []const u8) !zt.Event {
+ for (r.items) |item| {
+ if (item.ev.kind == .variable and item.ev.a[2] == r.id(name) and item.ev.a[3] == r.id(type_text)) return item.ev;
+ }
+ return error.NoSuchVariable;
+ }
+
+ fn count(r: *const Recording, kind: zt.Kind, a0: u64) usize {
+ var n: usize = 0;
+ for (r.items) |item| n += @intFromBool(item.ev.kind == kind and item.ev.a[0] == a0);
+ return n;
+ }
+
+ /// `T` from the memory recorded as of a moment; every byte must be known.
+ fn read(moment: zt.store.Moment, comptime T: type, addr: u64) !T {
+ var out: T = undefined;
+ var known: [@sizeOf(T)]bool = undefined;
+ try moment.read(addr, std.mem.asBytes(&out), &known);
+ try expect(std.mem.allEqual(bool, &known, true));
+ return out;
+ }
+};
+
+/// The calls of fib(n) from `at` on must be the tree of the source: each
+/// declares its parameter and stores n in it (the recorder keeps the bytes
+/// of a store only where they changed memory: the value is read there),
+/// calls fib(n-1) then fib(n-2), and returns their sum from the frame it
+/// entered. Returns the sum.
+fn fibTree(r: *const Recording, at: *usize, calls: *usize, n: u32) !u32 {
+ const items = r.items;
+ const fib = r.id("fib");
+ while (!((items[at.*].ev.kind == .call or items[at.*].ev.kind == .ret) and items[at.*].ev.a[0] == fib)) at.* += 1;
+ const call, const param, const store = .{ items[at.*].ev, items[at.* + 1].ev, items[at.* + 2] };
+ at.* += 3;
+ calls.* += 1;
+ try expectEqual(zt.Kind.call, call.kind);
+ try expectEqual(r.id("fn(u32)u32"), call.a[3]);
+ try expectEqual(zt.Kind.variable, param.kind);
+ try expectEqual(@as(u16, 1), param.aux);
+ try expectEqual(r.id("n"), param.a[2]);
+ try expectEqual(zt.Kind.mem_write, store.ev.kind);
+ try expectEqual(param.a[0], store.ev.a[0]);
+ try expectEqual(n, try Recording.read(try r.trace.moment(store.moment), u32, param.a[0]));
+
+ const result = if (n < 2) n else try fibTree(r, at, calls, n - 1) + try fibTree(r, at, calls, n - 2);
+ while (items[at.*].ev.kind != .ret) at.* += 1;
+ const ret = items[at.*].ev;
+ at.* += 1;
+ try expectEqual(fib, ret.a[0]);
+ try expectEqual(@as(u64, result), ret.a[1]);
+ try expectEqual(@as(u16, 4), ret.aux);
+ return result;
+}
+
+test "fib: the call tree, arguments and results" {
+ var r = try Recording.open(recordings.fib);
+ defer r.close();
+ var at: usize = 0;
+ var calls: usize = 0;
+ try expectEqual(@as(u32, 8), try fibTree(&r, &at, &calls, 6));
+ try expectEqual(@as(usize, 25), calls);
+ try expectEqual(@as(usize, 25), r.count(.call, r.id("fib")));
+ try expectEqual(@as(usize, 25), r.count(.ret, r.id("fib")));
+ try expectEqualStrings("fib", try r.string(r.id("fib")));
+ // Numbered from 1: a name costs a recording a byte or two each time.
+ try expect(r.id("fib") != 0 and r.id("fib") <= r.ids.count());
+
+ // The recorder's stack at the first fib(1): main, then fib six deep.
+ var seen: usize = 0;
+ const deepest = for (r.items) |item| {
+ if (item.ev.kind == .call and item.ev.a[0] == r.id("fib")) seen += 1;
+ if (seen == 6) break item;
+ } else unreachable;
+ const stack = try (try r.trace.moment(deepest.moment)).stack(gpa, deepest.ev.tid);
+ defer gpa.free(stack);
+ try expectEqual(@as(usize, 7), stack.len);
+ try expectEqual(r.id("main"), stack[0].function);
+ for (stack[1..], stack[0 .. stack.len - 1]) |frame, outer| {
+ try expectEqual(r.id("fib"), frame.function);
+ try expect(frame.sp < outer.sp);
+ }
+}
+
+test "sort: both arrays end sorted, and the lines run as often as the source says" {
+ try sortChecks(recordings.sort);
+}
+
+test "sort -O2: the optimizer keeps what the pass put in before it" {
+ try sortChecks(recordings.sort_O2);
+}
+
+fn sortChecks(recording: []const u8) !void {
+ var r = try Recording.open(recording);
+ defer r.close();
+ const unsorted = [8]i32{ 5, 2, 9, 1, 7, 3, 8, 4 };
+ const sorted = [8]i32{ 1, 2, 3, 4, 5, 7, 8, 9 };
+ for ([_][]const u8{ "bubbled", "inserted" }) |name| {
+ const v = try r.variable(name, "[8]i32");
+ try expectEqual(@as(u64, 32), v.a[1]);
+ try expectEqual(sorted, try Recording.read(try r.last(), [8]i32, v.a[0]));
+ }
+ // The constant they are copied from is a global: known from the start.
+ const source = try r.variable("unsorted", "[8]i32");
+ try expectEqual(unsorted, try Recording.read(try r.trace.moment(0), [8]i32, source.a[0]));
+
+ // Inside bubble the recorder knows its locals, and the array as it then was.
+ const in_bubble = for (r.items) |item| {
+ if (item.ev.kind == .line and item.ev.tid != 0 and (try (try r.trace.moment(item.moment)).stack(r.arena.allocator(), item.ev.tid)).len == 2) break item;
+ } else unreachable;
+ const then = try r.trace.moment(in_bubble.moment);
+ try expectEqual(unsorted, try Recording.read(then, [8]i32, (try r.variable("bubbled", "[8]i32")).a[0]));
+ var depth_of_a: u32 = 0;
+ for (try then.variables(r.arena.allocator())) |v| {
+ if (v.name == r.id("a")) depth_of_a = v.depth;
+ }
+ try expectEqual(@as(u32, 2), depth_of_a);
+ // After main returned only the global is left.
+ const left = try (try r.last()).variables(r.arena.allocator());
+ try expectEqual(@as(usize, 1), left.len);
+ try expectEqual(r.id("unsorted"), left[0].name);
+
+ // Every line event is a line of the one source file, which the recording names.
+ var file: u64 = 0;
+ var hits: [64]u32 = @splat(0);
+ for (r.items) |item| {
+ if (item.ev.kind != .line) continue;
+ if (file == 0) file = item.ev.a[0];
+ try expectEqual(file, item.ev.a[0]);
+ hits[item.ev.a[1]] += 1;
+ }
+ const path = try r.string(file);
+ try expect(std.mem.endsWith(u8, path, "targets/instr_sort.c"));
+ const text = try std.Io.Dir.cwd().readFileAlloc(io, path, r.arena.allocator(), .limited(1 << 20));
+ // The array has 13 inversions: bubble sort swaps that often, insertion
+ // sort shifts that often. Bubble sort compares 8*7/2 times.
+ const expected = [_]struct { []const u8, u32 }{
+ .{ "if (a[j] > a[j + 1]) {", 28 },
+ .{ "a[j + 1] = t;", 13 },
+ .{ "a[j + 1] = a[j];", 13 },
+ .{ "int key = a[i];", 7 },
+ .{ "bubble(bubbled, N);", 1 },
+ };
+ var found: usize = 0;
+ var lines = std.mem.splitScalar(u8, text, '\n');
+ var number: usize = 1;
+ while (lines.next()) |line| : (number += 1) {
+ const code = std.mem.trim(u8, line, " ");
+ // No event on a line with no code.
+ if (code.len == 0 or std.mem.startsWith(u8, code, "//") or std.mem.startsWith(u8, code, "#")) try expectEqual(@as(u32, 0), hits[number]);
+ for (expected) |e| {
+ if (!std.mem.eql(u8, code, e[0])) continue;
+ try expectEqual(e[1], hits[number]);
+ found += 1;
+ }
+ }
+ try expectEqual(expected.len, found);
+}
+
+/// The values of a list from `head` on, following `next` through the memory
+/// recorded as of `moment`, by the offsets of the node's description.
+fn listValues(moment: zt.store.Moment, node: types.Type, head: u64, out: []i32) ![]i32 {
+ var at = head;
+ var n: usize = 0;
+ while (at != 0) : (n += 1) {
+ out[n] = try Recording.read(moment, i32, at + node.field("value").?.offset);
+ at = try Recording.read(moment, u64, at + node.field("next").?.offset);
+ }
+ return out[0..n];
+}
+
+test "list: the recorded stores are the list, at every push and at the end" {
+ var r = try Recording.open(recordings.list);
+ defer r.close();
+ const arena = r.arena.allocator();
+
+ // From the variable to the shape of a node, through the type descriptions.
+ const list = try r.variable("list", "*`struct node`");
+ const pointer = try types.parse(arena, try r.string(list.a[3]));
+ const node = try types.parse(arena, try r.string(types.defId(pointer.pointer.named)));
+ try expectEqual(@as(?u64, 16), node.size());
+ try expectEqualStrings("struct node", node.field("next").?.type.pointer.named);
+
+ // Each push returns a list one longer: its squares, newest first.
+ var buf: [8]i32 = undefined;
+ var pushes: usize = 0;
+ for (r.items) |item| {
+ if (item.ev.kind != .ret or item.ev.a[0] != r.id("push")) continue;
+ pushes += 1;
+ const values = try listValues(try r.trace.moment(item.moment), node, item.ev.a[1], &buf);
+ try expectEqual(pushes, values.len);
+ for (values, 0..) |v, i| try expectEqual(@as(i32, @intCast((pushes - i) * (pushes - i))), v);
+ }
+ try expectEqual(@as(usize, 5), pushes);
+
+ // Reversed in place, and left in the global.
+ const end = try r.last();
+ const head = try Recording.read(end, u64, list.a[0]);
+ try expectEqualSlices(i32, &.{ 1, 4, 9, 16, 25 }, try listValues(end, node, head, &buf));
+ const globals = try end.variables(arena);
+ try expectEqual(@as(usize, 1), globals.len);
+ try expectEqual(@as(u32, 0), globals[0].depth);
+}
+
+test "bfs: distances and visiting order, the graph known from the start" {
+ var r = try Recording.open(recordings.bfs);
+ defer r.close();
+ const end = try r.last();
+
+ const distance = try r.variable("distance", "[7]i32");
+ try expectEqual([7]i32{ 0, 1, 1, 2, 3, 4, -1 }, try Recording.read(end, [7]i32, distance.a[0]));
+ const order = try r.variable("order", "[7]i32");
+ try expectEqual([7]i32{ 0, 1, 2, 3, 4, 5, 0 }, try Recording.read(end, [7]i32, order.a[0]));
+
+ // The edge list is constant: in the first moment already. The matrix
+ // main builds from it is symmetric and has each edge twice.
+ const edges = try Recording.read(try r.trace.moment(0), [6][2]i32, (try r.variable("edges", "[6][2]i32")).a[0]);
+ const adjacent = try Recording.read(end, [7][7]i32, (try r.variable("adjacent", "[7][7]i32")).a[0]);
+ var ones: usize = 0;
+ for (adjacent) |row| {
+ for (row) |cell| ones += @intCast(cell);
+ }
+ try expectEqual(2 * edges.len, ones);
+ for (edges) |e| try expectEqual(@as(i32, 1), adjacent[@intCast(e[1])][@intCast(e[0])]);
+
+ // bfs returns how many it reached; its queue lived only during the call.
+ const queue = try r.variable("queue", "[7]i32");
+ for (r.items) |item| {
+ if (item.ev.kind != .ret or item.ev.a[0] != r.id("bfs")) continue;
+ try expectEqual(@as(u64, 6), item.ev.a[1]);
+ try expectEqual([6]i32{ 0, 1, 2, 3, 4, 5 }, try Recording.read(try r.trace.moment(item.moment), [6]i32, queue.a[0]));
+ }
+ try expectEqual(@as(usize, 1), r.count(.ret, r.id("bfs")));
+ for (try end.variables(r.arena.allocator())) |v| try expect(v.name != r.id("queue"));
+}
+
+test "only: nothing outside the selection, by function name" {
+ var r = try Recording.open(recordings.sort_only);
+ defer r.close();
+ // Of three functions and a global, bubble alone: its call, its five locals.
+ var calls: usize = 0;
+ var variables: usize = 0;
+ var writes: usize = 0;
+ for (r.items) |item| switch (item.ev.kind) {
+ .call => {
+ try expectEqual(r.id("bubble"), item.ev.a[0]);
+ calls += 1;
+ },
+ .variable => variables += 1,
+ .mem_write => writes += 1,
+ .line => try expect(item.ev.a[1] >= 11 and item.ev.a[1] <= 21),
+ else => {},
+ };
+ try expectEqual(@as(usize, 1), calls);
+ try expectEqual(@as(usize, 5), variables);
+ try expect(writes > 13);
+ try expect(r.ids.get("bubble") != null and r.ids.get("insertion") == null and r.ids.get("unsorted") == null);
+}
+
+test "mem: lines and calls in the whole file, stores in one function" {
+ var r = try Recording.open(recordings.sort_mem);
+ defer r.close();
+ var full = try Recording.open(recordings.sort);
+ defer full.close();
+ // The file's name selects all of it: every line and call of the full recording.
+ for ([_]zt.Kind{ .line, .call, .ret, .variable }) |kind| {
+ var here: usize = 0;
+ var there: usize = 0;
+ for (r.items) |item| here += @intFromBool(item.ev.kind == kind);
+ for (full.items) |item| there += @intFromBool(item.ev.kind == kind);
+ try expectEqual(there, here);
+ }
+ // Stores only while insertion runs; the one before is the global's contents.
+ var inside = false;
+ var writes: usize = 0;
+ for (r.items) |item| switch (item.ev.kind) {
+ .call, .ret => inside = item.ev.kind == .call and item.ev.a[0] == r.id("insertion"),
+ .mem_write => {
+ try expect(inside or item.ev.a[0] == (try r.variable("unsorted", "[8]i32")).a[0]);
+ writes += @intFromBool(inside);
+ },
+ else => {},
+ };
+ try expect(writes > 13);
+}
+
+test "big: a megabyte written is 64 KiB recorded" {
+ var r = try Recording.open(recordings.big);
+ defer r.close();
+ const end = try r.last();
+ for ([_][]const u8{ "from", "to" }) |name| {
+ const v = try r.variable(name, "[1048576]c8");
+ var bytes: [(64 << 10) + 1]u8 = undefined;
+ var known: [bytes.len]bool = undefined;
+ try end.read(v.a[0], &bytes, &known);
+ try expect(std.mem.allEqual(u8, bytes[0 .. 64 << 10], 7));
+ try expect(std.mem.allEqual(bool, known[0 .. 64 << 10], true));
+ try expect(!known[64 << 10]);
+ }
+ // Four megabytes of globals and writes: four times 64 KiB, and the keyframe.
+ try expect((try std.Io.Dir.cwd().statFile(io, recordings.big, .{})).size < 1 << 20);
+
+ // As the runtime emits them, before the recorder: pieces, each saying how
+ // much was written from its address on.
+ const arena = r.arena.allocator();
+ const path = try arena.dupeSentinel(u8, recordings.big_program, 0);
+ var session = try zt.host.Session.spawn(arena, path, &.{ path, null }, &.{}, .{});
+ defer session.close();
+ const Pieces = struct {
+ name: u64 = 0,
+ from: u64 = 0,
+ bytes: u64 = 0,
+ first: u64 = 0,
+ last: u64 = 0,
+
+ fn emit(ctx: *anyopaque, ev: *const zt.Event, payload: []const u8) anyerror!void {
+ const p: *@This() = @ptrCast(@alignCast(ctx));
+ if (ev.kind == .string and std.mem.eql(u8, payload, "from")) p.name = ev.a[0];
+ if (ev.kind == .variable and ev.a[2] == p.name) p.from = ev.a[0];
+ // The memset, not the global's first contents.
+ if (ev.kind != .mem_write or ev.a[0] -% p.from >= 1 << 20 or payload[0] != 7) return;
+ try expect(payload.len <= 2048 and ev.a[1] >= payload.len);
+ if (p.bytes == 0) p.first = ev.a[1];
+ p.bytes += payload.len;
+ p.last = ev.a[1];
+ }
+ };
+ var pieces: Pieces = .{};
+ while (try session.pump(.{ .ctx = &pieces, .emitFn = Pieces.emit }, std.time.ns_per_ms)) {}
+ try expectEqual(@as(u64, 64 << 10), pieces.bytes);
+ try expectEqual(@as(u64, 1 << 20), pieces.first);
+ try expectEqual(@as(u64, (1 << 20) - (64 << 10) + 2048), pieces.last);
+}
+
+test "own: a program's own memcpy is traced when the program calls it, not when the runtime does" {
+ var r = try Recording.open(recordings.own);
+ defer r.close();
+ // Every mem_write the runtime emits it copies with this memcpy.
+ try expect(r.count(.mem_write, (try r.variable("to", "[8]c8")).a[0]) > 0);
+ try expectEqual(@as(usize, 1), r.count(.call, r.id("memcpy")));
+ try expectEqual(@as(usize, 1), r.count(.call, r.id("strlen")));
+ for (r.items) |item| {
+ if (item.ev.kind == .ret and item.ev.a[0] == r.id("strlen")) try expectEqual(@as(u64, 7), item.ev.a[1]);
+ }
+ try expectEqualStrings("abcdefg", std.mem.sliceTo(&try Recording.read(try r.last(), [8]u8, (try r.variable("to", "[8]c8")).a[0]), 0));
+}
+
+test "step: the ring holds the target at every line, its memory there to read" {
+ var r = try Recording.open(recordings.sort);
+ defer r.close();
+ const arena = r.arena.allocator();
+ var lines: usize = 0;
+ for (r.items) |item| lines += @intFromBool(item.ev.kind == .line);
+
+ const path = try arena.dupeSentinel(u8, recordings.sort_program, 0);
+ var session = try zt.host.Session.spawn(arena, path, &.{ path, null }, &.{}, .{ .stop_mask = zt.Kind.line.bit() });
+ defer session.close();
+ const ring = &session.ring;
+
+ // The array as the events so far say it is, against the target's own.
+ var name: u64 = 0;
+ var addr: u64 = 0;
+ var told: [32]u8 = @splat(0);
+ var compared: usize = 0;
+ var stops: usize = 0;
+ while (true) {
+ const rec = ring.peek() orelse {
+ if (session.exit_code != null) break;
+ var status: u32 = 0;
+ if (linux.waitpid(session.pid, @ptrCast(&status), linux.W.NOHANG) != 0) session.exit_code = linux.W.EXITSTATUS(status) else ring.wait(std.time.ns_per_ms);
+ continue;
+ };
+ const ev = rec.ev.*;
+ if (ev.kind == .string and std.mem.eql(u8, rec.payload, "bubbled")) name = ev.a[0];
+ if (ev.kind == .variable and ev.a[2] == name) addr = ev.a[0];
+ if (ev.kind == .mem_write and ev.a[0] >= addr and ev.a[0] + ev.a[1] <= addr + told.len) {
+ @memcpy(told[ev.a[0] - addr ..][0..rec.payload.len], rec.payload);
+ // From the first copy into it on; before, it is whatever the stack held.
+ compared += @intFromBool(compared == 0 and rec.payload.len == told.len);
+ }
+ ring.advance(rec);
+ if (ev.kind != .line) continue;
+
+ // Held: it emits nothing more until resumed.
+ while (ring.hdr.stopped.load(.acquire) == 0) std.atomic.spinLoopHint();
+ try expect(ring.peek() == null);
+ var live: [32]u8 = undefined;
+ const local = [_]std.posix.iovec{.{ .base = &live, .len = live.len }};
+ const remote = [_]std.posix.iovec_const{.{ .base = @ptrFromInt(addr), .len = live.len }};
+ try expectEqual(live.len, linux.process_vm_readv(session.pid, &local, &remote, 0));
+ if (compared > 0) {
+ try expectEqualSlices(u8, &told, &live);
+ compared += 1;
+ }
+ stops += 1;
+ ring.resumeAll();
+ }
+ try expectEqual(lines, stops);
+ try expect(compared > lines - 16);
+ try expectEqual(@as(?u8, 10), session.exit_code);
+ try expectEqualSlices(i32, &.{ 1, 2, 3, 4, 5, 7, 8, 9 }, &std.mem.bytesToValue([8]i32, &told));
+}