summaryrefslogtreecommitdiff
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
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]>
-rw-r--r--build/llvm.zig95
-rw-r--r--llvm/bench.sh57
-rw-r--r--llvm/pass.cpp469
-rw-r--r--src/cli/cc.zig116
-rw-r--r--src/cli/main.zig2
-rw-r--r--src/instr/bench.zig70
-rw-r--r--src/instr/rt.zig227
-rw-r--r--src/instr/test.zig464
-rw-r--r--src/instr/types.zig215
-rw-r--r--targets/instr_bfs.c39
-rw-r--r--targets/instr_big.c11
-rw-r--r--targets/instr_fib.c12
-rw-r--r--targets/instr_list.c46
-rw-r--r--targets/instr_own.c27
-rw-r--r--targets/instr_sort.c44
15 files changed, 1893 insertions, 1 deletions
diff --git a/build/llvm.zig b/build/llvm.zig
index d3c7eb3..a3e93cc 100644
--- a/build/llvm.zig
+++ b/build/llvm.zig
@@ -1,5 +1,98 @@
+//! Compiler instrumentation: the pass plugin (C++, built with the system
+//! clang++ against the LLVM that will load it), the runtime instrumented
+//! programs link, and tests on targets compiled through `ztrace cc`.
+const std = @import("std");
const Ctx = @import("../build.zig").Ctx;
pub fn add(ctx: Ctx) void {
- _ = ctx;
+ const b = ctx.b;
+
+ // The runtime runs inside the target at every event: optimized whatever
+ // mode the rest is built in.
+ const fast = b.createModule(.{ .root_source_file = b.path("src/trace/root.zig"), .target = ctx.target, .optimize = .ReleaseFast, .pic = true });
+ const rt = b.addLibrary(.{ .name = "ztrace-rt", .root_module = b.createModule(.{
+ .root_source_file = b.path("src/instr/rt.zig"),
+ .target = ctx.target,
+ .optimize = .ReleaseFast,
+ .pic = true,
+ .imports = &.{.{ .name = "ztrace", .module = fast }},
+ }) });
+ b.installArtifact(rt);
+
+ const cxx = b.addSystemCommand(&.{ "sh", "-c", "exec clang++ -shared -fPIC -O2 -fno-rtti $(llvm-config --cxxflags) \"$0\" -o \"$1\"" });
+ cxx.addFileArg(b.path("llvm/pass.cpp"));
+ const plugin = cxx.addOutputFileArg("ztrace-pass.so");
+ b.getInstallStep().dependOn(&b.addInstallLibFile(plugin, "ztrace-pass.so").step);
+
+ // For whoever draws values: the parser of type descriptions.
+ const types = b.addModule("ztrace-types", .{ .root_source_file = b.path("src/instr/types.zig"), .target = ctx.target, .optimize = ctx.optimize });
+
+ // The tests read recordings of the targets, each compiled by `ztrace cc`
+ // and run by `ztrace run`.
+ const options = b.addOptions();
+ // A recording by name: its source, how clang optimizes it (-O2 is the
+ // optimizer going over what the pass put in), what `ztrace cc` is told.
+ const Target = struct { []const u8, []const u8, []const u8, []const []const u8 };
+ for ([_]Target{
+ .{ "fib", "fib", "-O0", &.{} },
+ .{ "sort", "sort", "-O0", &.{} },
+ .{ "sort_O2", "sort", "-O2", &.{} },
+ .{ "sort_only", "sort", "-O0", &.{ "--only", "bub*" } },
+ .{ "sort_mem", "sort", "-O0", &.{ "--only", "instr_sort.c", "--mem", "insertion" } },
+ .{ "list", "list", "-O0", &.{} },
+ .{ "bfs", "bfs", "-O0", &.{} },
+ .{ "own", "own", "-O0", &.{} },
+ .{ "big", "big", "-O0", &.{} },
+ }) |target| {
+ const name, const source, const opt, const selection = target;
+ const cc = b.addRunArtifact(ctx.exe);
+ cc.addArg("cc");
+ cc.addArgs(selection);
+ cc.addArg("--plugin");
+ cc.addFileArg(plugin);
+ cc.addArg("--rt");
+ cc.addArtifactArg(rt);
+ cc.addArgs(&.{ "--", "clang", opt });
+ cc.addFileArg(b.path(b.fmt("targets/instr_{s}.c", .{source})));
+ cc.addArg("-o");
+ const program = cc.addOutputFileArg(b.fmt("instr_{s}", .{name}));
+ options.addOptionPath(b.fmt("{s}_program", .{name}), program);
+
+ const run = b.addRunArtifact(ctx.exe);
+ run.addArgs(&.{ "run", "-o" });
+ options.addOptionPath(name, run.addOutputFileArg(b.fmt("{s}.ztrace", .{name})));
+ run.addArg("--");
+ run.addFileArg(program);
+ run.expectStdErrMatch("(0 dropped)");
+ }
+
+ const step = ctx.areaTest("test-llvm", "Compiler instrumentation: the pass, the runtime, ztrace cc");
+ const tests = b.addTest(.{ .root_module = b.createModule(.{
+ .root_source_file = b.path("src/instr/test.zig"),
+ .target = ctx.target,
+ .optimize = ctx.optimize,
+ .imports = &.{
+ .{ .name = "ztrace", .module = ctx.ztrace },
+ .{ .name = "types", .module = types },
+ .{ .name = "recordings", .module = options.createModule() },
+ },
+ }) });
+ step.dependOn(&b.addRunArtifact(tests).step);
+ step.dependOn(&b.addRunArtifact(b.addTest(.{ .root_module = types })).step);
+
+ // zig build bench-llvm -Doptimize=ReleaseFast: what each kind of
+ // instrumentation costs each target (llvm/bench.sh).
+ const bench = b.addSystemCommand(&.{"sh"});
+ bench.addFileArg(b.path("llvm/bench.sh"));
+ bench.addArtifactArg(ctx.exe);
+ bench.addArtifactArg(b.addExecutable(.{ .name = "bench", .root_module = b.createModule(.{
+ .root_source_file = b.path("src/instr/bench.zig"),
+ .target = ctx.target,
+ .optimize = .ReleaseFast,
+ .imports = &.{.{ .name = "ztrace", .module = fast }},
+ }) }));
+ bench.addFileArg(plugin);
+ bench.addArtifactArg(rt);
+ bench.addDirectoryArg(b.path("targets"));
+ b.step("bench-llvm", "Measure the cost of compiler instrumentation").dependOn(&bench.step);
}
diff --git a/llvm/bench.sh b/llvm/bench.sh
new file mode 100644
index 0000000..00edc88
--- /dev/null
+++ b/llvm/bench.sh
@@ -0,0 +1,57 @@
+#!/bin/sh
+# What compiler instrumentation costs: zig build bench-llvm -Doptimize=ReleaseFast.
+# Arguments: ztrace, the bench tool (src/instr/bench.zig), the plugin, the
+# runtime, the targets directory.
+set -eu
+ztrace=$1 bench=$2 plugin=$3 rt=$4 targets=$5
+tmp=$(mktemp -d)
+trap 'rm -rf "$tmp"' EXIT
+
+# target : argument when traced : argument when not : how many times more
+# work the second is. With no tracer a target runs too briefly to time at
+# the first.
+workloads="fib:24:35:199.006 sort:2000:400000:200 list:5000:1000000:200 bfs:3000:600000:200"
+selections="lines stores loads calls vars lines,calls,vars lines,calls,vars,stores edges cmps cyg"
+
+# The best of three runs: milliseconds, then whatever else the tool printed.
+best() {
+ for _ in 1 2 3; do "$bench" "$@"; done | sort -n | head -1
+}
+
+cat <<'EOF2'
+Per selection of `ztrace cc --instr`:
+ events emitted at the traced workload
+ idle time against the uninstrumented program, with no tracer
+ ring the same into a ring drained and thrown away
+ ns nanoseconds an event, into that ring
+ B/event bytes of recording an event (`ztrace run`, a moment a line)
+ B/line bytes of recording a source line executed
+ rec/s events a second into the recording
+EOF2
+for opt in -O0 -O2; do
+ for w in $workloads; do
+ IFS=: read -r name arg long scale <<EOF2
+$w
+EOF2
+ clang $opt "$targets/instr_$name.c" -o "$tmp/plain"
+ start=$(best --untraced "$tmp/plain" 0 | cut -d' ' -f1)
+ alone=$(best --untraced "$tmp/plain" "$long" | awk -v start="$start" '{ print $1 - start }')
+ printf '\n%s %s: uninstrumented, %.1f ms at %s; traced at %s\n' "$name" "$opt" "$alone" "$long" "$arg"
+ printf ' %-24s %9s %7s %9s %6s %8s %7s %9s\n' selection events idle ring ns B/event B/line rec/s
+ for s in $selections; do
+ "$ztrace" cc --instr "$s" --plugin "$plugin" --rt "$rt" -- clang $opt "$targets/instr_$name.c" -o "$tmp/instr"
+ idle=$(best --untraced "$tmp/instr" "$long" | cut -d' ' -f1)
+ traced=$(best "$tmp/instr" "$arg")
+ # The lines the workload executes, whatever is selected: counted once.
+ [ "$s" = lines ] && lines=$(echo "$traced" | sed 's/.* line=\([0-9]*\).*/\1/')
+ recorded=$("$ztrace" run -o "$tmp/r.ztrace" -- "$tmp/instr" "$arg" 2>&1 | sed 's/.* \([0-9]*\) bytes.* \([0-9]*\) events\/s.*/\1 \2/')
+ echo "$traced $recorded" | awk -v s="$s" -v start="$start" -v alone="$alone" -v scale="$scale" -v idle="$idle" -v lines="$lines" \
+ '{ printf " %-24s %9d %6.1fx %8.1fx %6.1f %8.1f %7.1f %9d\n", s, $2, (idle - start) / alone, ($1 - start) * scale / alone, ($1 - start - alone / scale) * 1e6 / $2, $(NF - 1) / $2, $(NF - 1) / lines, $NF }'
+ done
+ done
+done
+
+"$ztrace" cc --plugin "$plugin" --rt "$rt" -- clang -O0 "$targets/instr_sort.c" -o "$tmp/sort"
+echo
+echo "sort 2000 -O0, held at each line by the stop mask and resumed at once:"
+best --step "$tmp/sort" 2000 | awk '{ ms = $1; sub(/.* line=/, ""); printf " %d stops in %.0f ms: %.0f a second\n", $1, ms, $1 / ms * 1000 }'
diff --git a/llvm/pass.cpp b/llvm/pass.cpp
new file mode 100644
index 0000000..2872a98
--- /dev/null
+++ b/llvm/pass.cpp
@@ -0,0 +1,469 @@
+// ztrace-pass.so: an LLVM pass plugin that instruments a program for
+// animation. Each inserted call hands the runtime (src/instr/rt.zig) what a
+// viewer needs, so nothing parses DWARF at view time:
+//
+// lines __zt_line(file, line, column) before each new source line of a block
+// stores __zt_store(addr, size) after each store, memset, memcpy
+// loads __zt_load(addr, size) after each load; neither for the
+// compiler's own temporaries
+// calls __zt_enter(name, type, sp, site) at function entry
+// __zt_exit(name, value, size) before each return
+// vars __zt_var(addr, size, name, type, arg) per named local, after __zt_enter;
+// a record in section ztrace_vars per global
+//
+// file, name and type are texts: pointers to records in section ztrace_strs
+// (id, length, text), one per text in the program, the linker folding the
+// copies of other translation units. The runtime numbers them from 1 and
+// emits each as a `string` before the first event: an id is a byte or two
+// in a recording. Type descriptions follow the grammar in
+// src/instr/types.zig; the description of a named type has its id fixed
+// here, a hash of the name, so a viewer finds it from the name.
+//
+// clang -g -fpass-plugin=ztrace-pass.so -Xclang -load -Xclang ztrace-pass.so \
+// -mllvm -ztrace-instr=lines,calls,vars,stores \
+// -mllvm -ztrace-only='sqlite3Btree*,*/pager.c' -mllvm -ztrace-mem='*Insert*'
+// opt -load-pass-plugin=ztrace-pass.so -passes=ztrace
+//
+// It runs before optimization by default: every local still has an address
+// and a debug record that says so, every source store exists, lines come in
+// source order; the optimizer then keeps what the calls made observable.
+// -ztrace-late runs it after: the stores, loads and lines of the code that
+// really runs, and only the variables the optimizer left in memory.
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/BinaryFormat/Dwarf.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/DebugProgramInstruction.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Passes/PassBuilder.h"
+#include "llvm/Plugins/PassPlugin.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/GlobPattern.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
+
+using namespace llvm;
+
+static cl::opt<std::string> Instr("ztrace-instr", cl::init("lines,calls,vars,stores"),
+ cl::desc("What to instrument: lines,stores,loads,calls,vars"));
+static cl::opt<std::string> Only("ztrace-only",
+ cl::desc("Globs: instrument only the functions and globals whose name, "
+ "source path or source file name matches one"));
+static cl::opt<std::string> MemOnly("ztrace-mem", cl::desc("Globs: of those, the functions whose stores and loads are instrumented"));
+static cl::opt<bool> Late("ztrace-late", cl::desc("Instrument after optimization"));
+
+namespace {
+
+uint64_t hash(StringRef S) {
+ uint64_t H = 0xcbf29ce484222325;
+ for (unsigned char C : S)
+ H = (H ^ C) * 0x100000001b3;
+ return H;
+}
+
+struct Instrumenter {
+ Module &M;
+ LLVMContext &Ctx = M.getContext();
+ const DataLayout &DL = M.getDataLayout();
+ Type *Void = Type::getVoidTy(Ctx), *Ptr = PointerType::getUnqual(Ctx);
+ IntegerType *I32 = Type::getInt32Ty(Ctx), *I64 = Type::getInt64Ty(Ctx);
+ bool Lines = false, Stores = false, Loads = false, Calls = false, Vars = false;
+ std::vector<GlobPattern> Where, Memory;
+ std::vector<GlobalValue *> Used;
+ DenseSet<const DIType *> Defined;
+ DenseMap<const DIFile *, Constant *> Files;
+
+ FunctionCallee callee(const char *Name, std::initializer_list<Type *> Params) {
+ return M.getOrInsertFunction(Name, FunctionType::get(Void, Params, false));
+ }
+ ConstantInt *i64(uint64_t V) { return ConstantInt::get(I64, V); }
+
+ Instrumenter(Module &M) : M(M) {
+ SmallVector<StringRef> Words;
+ StringRef(Instr).split(Words, ',', -1, false);
+ for (StringRef W : Words) {
+ bool *Flag = StringSwitch<bool *>(W).Case("lines", &Lines).Case("stores", &Stores).Case("loads", &Loads).Case("calls", &Calls).Case("vars", &Vars).Default(nullptr);
+ if (!Flag)
+ reportFatalUsageError(Twine("-ztrace-instr: '") + W + "' is none of lines,stores,loads,calls,vars");
+ *Flag = true;
+ }
+ for (auto [Text, Globs] : {std::pair(StringRef(Only), &Where), std::pair(StringRef(MemOnly), &Memory)}) {
+ Words.clear();
+ Text.split(Words, ',', -1, false);
+ for (StringRef W : Words) {
+ auto G = GlobPattern::create(W);
+ if (!G)
+ reportFatalUsageError(Twine("ztrace: glob '") + W + "': " + toString(G.takeError()));
+ Globs->push_back(*G);
+ }
+ }
+ }
+
+ // Names.
+
+ // The record the runtime turns into a `string` event: id, length, text,
+ // padded to 8 bytes. One per name in the program: the linker folds the
+ // rest. Id 0 is the runtime's to number.
+ Constant *record(const Twine &Name, uint64_t Id, StringRef Text) {
+ if (GlobalVariable *G = M.getNamedGlobal(Name.str()))
+ return G;
+ std::string Bytes(16 + alignTo(Text.size(), 8), '\0');
+ uint64_t Len = Text.size();
+ memcpy(&Bytes[0], &Id, 8);
+ memcpy(&Bytes[8], &Len, 8);
+ memcpy(&Bytes[16], Text.data(), Len);
+ Constant *Init = ConstantDataArray::getString(Ctx, Bytes, false);
+ auto *G = new GlobalVariable(M, Init->getType(), false, GlobalValue::LinkOnceODRLinkage, Init, Name);
+ G->setSection("ztrace_strs");
+ G->setAlignment(Align(8));
+ G->setVisibility(GlobalValue::HiddenVisibility);
+ G->setComdat(M.getOrInsertComdat(G->getName()));
+ Used.push_back(G);
+ return G;
+ }
+ Constant *str(StringRef Text) { return record("__zt_s_" + utohexstr(hash(Text)), 0, Text); }
+
+ static std::string path(const DIFile *F) {
+ SmallString<256> P(F->getFilename());
+ if (!sys::path::is_absolute(P)) {
+ P = F->getDirectory();
+ sys::path::append(P, F->getFilename());
+ }
+ sys::path::remove_dots(P, true);
+ return std::string(P);
+ }
+
+ // C++: the namespaces and classes a name sits in.
+ static std::string qualified(const DIScope *S, StringRef Name) {
+ std::string Out(Name);
+ for (; S && (isa<DINamespace>(S) || isa<DICompositeType>(S)); S = S->getScope())
+ Out = (S->getName().empty() ? "(anonymous)" : S->getName().str()) + "::" + Out;
+ return Out;
+ }
+
+ // No list selects everything; a list, what has a name (as written, or as
+ // linked) or a source file (its path, or its last part) matching one glob.
+ static bool selected(std::vector<GlobPattern> &Globs, StringRef Name, StringRef Linked, const DIFile *File) {
+ std::string Path = File ? path(File) : "";
+ for (GlobPattern &G : Globs)
+ if (G.match(Name) || G.match(Linked) || G.match(Path) || G.match(sys::path::filename(Path)))
+ return true;
+ return Globs.empty();
+ }
+
+ // Type descriptions: the grammar of src/instr/types.zig.
+
+ static std::string opaque(const DIType *T) { return "x" + utostr(T->getSizeInBits()); }
+
+ static char letter(const DIType *T) {
+ while (auto *D = dyn_cast_or_null<DIDerivedType>(T))
+ T = D->getBaseType();
+ if (auto *C = dyn_cast_or_null<DICompositeType>(T))
+ T = C->getBaseType(); // an enum's integer
+ auto *B = dyn_cast_or_null<DIBasicType>(T);
+ switch (B ? B->getEncoding() : 0) {
+ case dwarf::DW_ATE_boolean:
+ return 'b';
+ case dwarf::DW_ATE_float:
+ return 'f';
+ case dwarf::DW_ATE_signed:
+ return 'i';
+ case dwarf::DW_ATE_unsigned:
+ return 'u';
+ case dwarf::DW_ATE_signed_char:
+ return B->getName() == "char" ? 'c' : 'i';
+ case dwarf::DW_ATE_unsigned_char:
+ return B->getName() == "char" ? 'c' : 'u';
+ case dwarf::DW_ATE_UTF:
+ case dwarf::DW_ATE_ASCII:
+ return 'c';
+ default:
+ return 'x';
+ }
+ }
+
+ // A named type is written as its name. Its description is a text of its
+ // own, under an id no numbered text has (the top bit) that follows from
+ // the name: `defId` in types.zig. It is marked defined before its body is
+ // described, so a struct that points to itself ends.
+ std::string named(const DIType *T, std::string Name, bool HasBody, function_ref<std::string()> Body) {
+ if (HasBody && Defined.insert(T).second) {
+ uint64_t Id = hash("=" + Name) | 1ull << 63;
+ record("__zt_d_" + utohexstr(Id), Id, Body());
+ }
+ return "`" + Name + "`";
+ }
+
+ std::string record(const DICompositeType *C) {
+ if (C->getTag() == dwarf::DW_TAG_enumeration_type) {
+ std::string Out = "enum(" + (C->getBaseType() ? type(C->getBaseType()) : "u" + utostr(C->getSizeInBits())) + "){";
+ for (DINode *E : C->getElements())
+ if (auto *V = dyn_cast<DIEnumerator>(E))
+ Out += V->getName().str() + "=" + toString(V->getValue(), 10, !V->isUnsigned()) + ";";
+ return Out + "}";
+ }
+ std::string Out = (C->getTag() == dwarf::DW_TAG_union_type ? "union(" : "struct(") + utostr(C->getSizeInBits() / 8) + "){";
+ for (DINode *E : C->getElements()) {
+ auto *F = dyn_cast<DIDerivedType>(E);
+ if (!F || F->isStaticMember() || (F->getTag() != dwarf::DW_TAG_member && F->getTag() != dwarf::DW_TAG_inheritance))
+ continue;
+ for (char Ch : F->getName())
+ Out += isAlnum(Ch) || Ch == '$' ? Ch : '_';
+ uint64_t At = F->getOffsetInBits();
+ Out += "@" + utostr(At / 8);
+ if (F->isBitField())
+ Out += "." + utostr(At % 8) + ":" + letter(F->getBaseType()) + utostr(F->getSizeInBits());
+ else
+ Out += ":" + type(F->getBaseType());
+ Out += ";";
+ }
+ return Out + "}";
+ }
+
+ std::string type(const DIType *T) {
+ if (!T)
+ return "void";
+ if (auto *B = dyn_cast<DIBasicType>(T))
+ return letter(B) + utostr(B->getSizeInBits());
+ if (auto *S = dyn_cast<DISubroutineType>(T)) {
+ DITypeArray Types = S->getTypeArray();
+ std::string Out = "fn(";
+ for (unsigned I = 1; I < Types.size(); ++I)
+ Out += (I > 1 ? "," : "") + (Types[I] ? type(Types[I]) : "...");
+ return Out + ")" + type(Types.size() ? Types[0] : nullptr);
+ }
+ if (auto *D = dyn_cast<DIDerivedType>(T)) {
+ switch (D->getTag()) {
+ case dwarf::DW_TAG_pointer_type:
+ case dwarf::DW_TAG_reference_type:
+ case dwarf::DW_TAG_rvalue_reference_type:
+ return "*" + type(D->getBaseType());
+ case dwarf::DW_TAG_typedef:
+ return named(D, qualified(D->getScope(), D->getName()), true, [&] { return type(D->getBaseType()); });
+ case dwarf::DW_TAG_ptr_to_member_type:
+ return opaque(D);
+ default: // const, volatile, restrict, atomic
+ return type(D->getBaseType());
+ }
+ }
+ if (auto *C = dyn_cast<DICompositeType>(T)) {
+ unsigned Tag = C->getTag();
+ if (Tag == dwarf::DW_TAG_array_type && !C->isVector()) {
+ std::string Out;
+ for (DINode *E : C->getElements())
+ if (auto *R = dyn_cast<DISubrange>(E)) {
+ // A flexible or variable-length array has no constant count: 0.
+ auto *N = dyn_cast_if_present<ConstantInt *>(R->getCount());
+ Out += "[" + utostr(N && N->getSExtValue() > 0 ? N->getZExtValue() : 0) + "]";
+ }
+ return Out + type(C->getBaseType());
+ }
+ bool Struct = Tag == dwarf::DW_TAG_structure_type || Tag == dwarf::DW_TAG_class_type;
+ if (Struct || Tag == dwarf::DW_TAG_union_type || Tag == dwarf::DW_TAG_enumeration_type) {
+ if (C->getName().empty())
+ return record(C);
+ // shortcut: two different types with one name (file-local structs in
+ // two C files) share a definition; add the declaring file to the name
+ // when a target has them.
+ return named(C, (Struct ? "struct " : Tag == dwarf::DW_TAG_union_type ? "union " : "enum ") + qualified(C->getScope(), C->getName()),
+ !C->isForwardDecl(), [&] { return record(C); });
+ }
+ }
+ return opaque(T);
+ }
+
+ // Code.
+
+ void instrument(Function &F) {
+ DISubprogram *SP = F.getSubprogram();
+ BasicBlock &Entry = F.getEntryBlock();
+ std::string FName = qualified(SP->getScope(), SP->getName());
+ bool Mem = selected(Memory, FName, F.getName(), SP->getFile());
+
+ // The named locals that live in memory: the first debug record that
+ // gives a static alloca or a by-value argument as a variable's address.
+ // That is #dbg_declare at -O0, and #dbg_assign from -O1 on, where clang
+ // turns the one into the other before any plugin runs.
+ struct Local {
+ Value *Addr;
+ uint64_t Size;
+ DILocalVariable *Var;
+ };
+ std::vector<Local> Locals;
+ SmallPtrSet<Value *, 8> Named;
+ for (BasicBlock &BB : F)
+ for (Instruction &I : BB)
+ for (DbgVariableRecord &R : filterDbgVars(I.getDbgRecordRange())) {
+ if (!R.isDbgDeclare() && !R.isDbgAssign())
+ continue;
+ Value *V = R.getAddress();
+ if (!V || !Named.insert(V).second || !Vars || (R.isDbgAssign() ? R.getAddressExpression() : R.getExpression())->getNumElements())
+ continue;
+ if (auto *A = dyn_cast<AllocaInst>(V); A && A->isStaticAlloca()) {
+ if (auto Size = A->getAllocationSize(DL))
+ Locals.push_back({A, Size->getFixedValue(), R.getVariable()});
+ } else if (auto *Arg = dyn_cast<Argument>(V); Arg && Arg->hasByValAttr()) {
+ Locals.push_back({Arg, DL.getTypeAllocSize(Arg->getParamByValType()).getFixedValue(), R.getVariable()});
+ }
+ }
+ // Declared for the whole call, so two of them must not share a stack
+ // slot: without its lifetime markers a slot is never reused.
+ for (Local &L : Locals)
+ for (User *U : make_early_inc_range(L.Addr->users()))
+ if (auto *Life = dyn_cast<LifetimeIntrinsic>(U))
+ Life->eraseFromParent();
+
+ // What was there before anything is inserted.
+ std::vector<Instruction *> Body;
+ for (BasicBlock &BB : F)
+ for (Instruction &I : BB)
+ Body.push_back(&I);
+
+ IRBuilder<> B(&Entry, Entry.getFirstNonPHIOrDbgOrAlloca());
+ B.SetCurrentDebugLocation(DILocation::get(Ctx, SP->getScopeLine(), 0, SP));
+ Constant *Name = Calls ? str(FName) : nullptr;
+ if (Calls) {
+ Value *Sp = B.CreateIntrinsic(Intrinsic::addressofreturnaddress, {Ptr}, {});
+ Value *Site = B.CreateIntrinsic(Intrinsic::returnaddress, {Ptr}, {ConstantInt::get(I32, 0)});
+ B.CreateCall(callee("__zt_enter", {Ptr, Ptr, Ptr, Ptr}), {Name, str(type(SP->getType())), Sp, Site});
+ }
+ for (Local &L : Locals)
+ B.CreateCall(callee("__zt_var", {Ptr, I64, Ptr, Ptr, I32}),
+ {L.Addr, i64(L.Size), str(L.Var->getName()), str(type(L.Var->getType())), ConstantInt::get(I32, L.Var->getArg())});
+
+ const BasicBlock *Block = nullptr;
+ const DIFile *File = nullptr;
+ unsigned Line = 0;
+ for (Instruction *I : Body) {
+ // Nothing may come between a musttail call and its return: the call
+ // is where this function ends.
+ CallInst *Tail = I->getParent()->getTerminatingMustTailCall();
+ if (Tail && I != Tail && Tail->comesBefore(I))
+ continue;
+ B.SetInsertPoint(I);
+
+ // A line event where a block reaches a line it was not on. A block
+ // always says where it is: a loop comes back to the same line. Jumps
+ // do no work of their own (the closing brace of a loop body).
+ if (I->getParent() != Block) {
+ Block = I->getParent();
+ Line = 0;
+ }
+ const DebugLoc &Loc = I->getDebugLoc();
+ if (Lines && Loc && Loc.getLine() && !isa<PHINode>(I) && !isa<AllocaInst>(I) && !I->isEHPad() && !I->isLifetimeStartOrEnd() && !isa<UncondBrInst>(I) &&
+ (Loc.getLine() != Line || Loc->getFile() != File)) {
+ Line = Loc.getLine();
+ File = Loc->getFile();
+ auto [At, New] = Files.try_emplace(File);
+ if (New)
+ At->second = str(path(File));
+ B.CreateCall(callee("__zt_line", {Ptr, I32, I32}), {At->second, ConstantInt::get(I32, Line), ConstantInt::get(I32, Loc.getCol())});
+ }
+
+ if (Calls && (isa<ReturnInst>(I) || I == Tail)) {
+ Value *V = I == Tail ? nullptr : cast<ReturnInst>(I)->getReturnValue();
+ Type *T = V ? V->getType() : Void;
+ unsigned Bits = T->isPointerTy() ? 64 : T->isIntegerTy() || T->isFloatTy() || T->isDoubleTy() ? T->getPrimitiveSizeInBits().getFixedValue() : 0;
+ if (Bits == 0 || Bits > 64)
+ V = i64(0), Bits = 0; // void, or an aggregate: no value
+ else if (T->isPointerTy())
+ V = B.CreatePtrToInt(V, I64);
+ else
+ V = B.CreateZExt(B.CreateBitCast(V, IntegerType::get(Ctx, Bits)), I64);
+ B.CreateCall(callee("__zt_exit", {Ptr, I64, I32}), {Name, V, ConstantInt::get(I32, (Bits + 7) / 8)});
+ }
+
+ Value *Addr = nullptr, *Size = nullptr;
+ const char *Hook = "__zt_store";
+ if (auto *S = dyn_cast<StoreInst>(I); S && Stores)
+ Addr = S->getPointerOperand(), Size = i64(DL.getTypeStoreSize(S->getValueOperand()->getType()));
+ else if (auto *A = dyn_cast<AtomicRMWInst>(I); A && Stores)
+ Addr = A->getPointerOperand(), Size = i64(DL.getTypeStoreSize(A->getValOperand()->getType()));
+ else if (auto *X = dyn_cast<AtomicCmpXchgInst>(I); X && Stores)
+ Addr = X->getPointerOperand(), Size = i64(DL.getTypeStoreSize(X->getNewValOperand()->getType()));
+ else if (auto *Set = dyn_cast<MemIntrinsic>(I); Set && Stores)
+ Addr = Set->getRawDest(), Size = Set->getLength();
+ else if (auto *L = dyn_cast<LoadInst>(I); L && Loads)
+ Addr = L->getPointerOperand(), Size = i64(DL.getTypeStoreSize(L->getType())), Hook = "__zt_load";
+ // Not the stack slots the compiler made for itself (a return value on
+ // its way out, a temporary): nothing names them, so nothing draws them.
+ Value *Object = Addr ? getUnderlyingObject(Addr) : nullptr;
+ if (Addr && Mem && (!isa<AllocaInst>(Object) || Named.count(Object))) {
+ // After it: the runtime reads the bytes the store left.
+ B.SetInsertPoint(I->getNextNode());
+ B.SetCurrentDebugLocation(Loc);
+ B.CreateCall(callee(Hook, {Ptr, I64}), {Addr, B.CreateZExtOrTrunc(Size, I64)});
+ }
+ }
+ }
+
+ bool run() {
+ std::vector<Function *> Functions;
+ for (Function &F : M) {
+ DISubprogram *SP = F.getSubprogram();
+ if (!F.isDeclaration() && SP && !F.hasAvailableExternallyLinkage() && !F.hasFnAttribute(Attribute::Naked) &&
+ !F.hasFnAttribute(Attribute::DisableSanitizerInstrumentation) &&
+ selected(Where, qualified(SP->getScope(), SP->getName()), F.getName(), SP->getFile()))
+ Functions.push_back(&F);
+ }
+ // The globals with debug info: {address, size, name, type} each, for the
+ // runtime to declare and snapshot at startup.
+ std::vector<Constant *> Globals;
+ if (Vars)
+ for (GlobalVariable &G : M.globals()) {
+ SmallVector<DIGlobalVariableExpression *, 1> Info;
+ G.getDebugInfo(Info);
+ if (G.isDeclaration() || G.hasAvailableExternallyLinkage() || G.isThreadLocal() || Info.empty())
+ continue;
+ DIGlobalVariable *V = Info[0]->getVariable();
+ std::string Name = qualified(V->getScope(), V->getName());
+ if (selected(Where, Name, G.getName(), V->getFile()))
+ Globals.push_back(ConstantStruct::getAnon({&G, i64(DL.getTypeAllocSize(G.getValueType())), str(Name), str(type(V->getType()))}));
+ }
+ for (Function *F : Functions)
+ instrument(*F);
+ for (Constant *Init : Globals) {
+ auto *G = new GlobalVariable(M, Init->getType(), true, GlobalValue::PrivateLinkage, Init, "__zt_v");
+ G->setSection("ztrace_vars");
+ G->setAlignment(Align(8));
+ Used.push_back(G);
+ }
+ // Used: nothing refers to these records but the section's bounds.
+ appendToUsed(M, Used);
+ return !Used.empty() || !Functions.empty();
+ }
+};
+
+struct ZtracePass : PassInfoMixin<ZtracePass> {
+ PreservedAnalyses run(Module &M, ModuleAnalysisManager &) {
+ return Instrumenter(M).run() ? PreservedAnalyses::none() : PreservedAnalyses::all();
+ }
+ // Also for the optnone functions of -O0.
+ static bool isRequired() { return true; }
+};
+
+} // namespace
+
+extern "C" LLVM_ATTRIBUTE_WEAK PassPluginLibraryInfo llvmGetPassPluginInfo() {
+ return {LLVM_PLUGIN_API_VERSION, "ztrace", "0.1", [](PassBuilder &PB) {
+ PB.registerPipelineStartEPCallback([](ModulePassManager &MPM, OptimizationLevel) {
+ if (!Late)
+ MPM.addPass(ZtracePass());
+ });
+ PB.registerOptimizerLastEPCallback([](ModulePassManager &MPM, OptimizationLevel, ThinOrFullLTOPhase) {
+ if (Late)
+ MPM.addPass(ZtracePass());
+ });
+ PB.registerPipelineParsingCallback([](StringRef Name, ModulePassManager &MPM, ArrayRef<PassBuilder::PipelineElement>) {
+ if (Name != "ztrace")
+ return false;
+ MPM.addPass(ZtracePass());
+ return true;
+ });
+ }};
+}
diff --git a/src/cli/cc.zig b/src/cli/cc.zig
new file mode 100644
index 0000000..1d08b51
--- /dev/null
+++ b/src/cli/cc.zig
@@ -0,0 +1,116 @@
+//! ztrace cc: a compiler command with the instrumentation added, so a
+//! program compiled from source records itself under `ztrace run`.
+const std = @import("std");
+const util = @import("util.zig");
+const fail = util.fail;
+
+pub const usage =
+ \\usage: ztrace cc [--instr LIST] [--only GLOBS] [--mem GLOBS] [--late] [--plugin SO] [--rt A] -- CLANG ARGS
+ \\
+ \\Runs CLANG (clang, clang++) with ARGS and -g, the pass plugin and its
+ \\options, and when the command links, the runtime:
+ \\
+ \\ ztrace cc -- clang sort.c -o sort && ztrace run -- ./sort
+ \\
+ \\ --instr LIST comma separated, default lines,calls,vars,stores
+ \\ lines `line` at each source line reached
+ \\ stores `mem_write`, with the bytes, after each store to a
+ \\ variable or through a pointer; a memset or
+ \\ memcpy is one, of its first 64 KiB at most
+ \\ loads `mem_read` after each load
+ \\ calls `call` at function entry, `ret` with the value at exit
+ \\ vars `variable` for each named local and global:
+ \\ address, size, name, type description
+ \\ from stock clang, no plugin and no names:
+ \\ edges `edge` (-fsanitize-coverage=trace-pc-guard)
+ \\ cmps `cmp`, and `edge`: clang compares only along with edges
+ \\ (-fsanitize-coverage=trace-pc-guard,trace-cmp)
+ \\ cyg `call`, `ret` (-finstrument-functions)
+ \\ --only GLOBS comma separated; the plugin instruments only the functions
+ \\ and globals whose name, source path or source file name
+ \\ matches one: 'sort*,*/vdbe.c'
+ \\ --mem GLOBS of those, the functions whose stores and loads are recorded
+ \\ (default: all of them). Stores are most of a recording:
+ \\ in a large program, name where memory matters.
+ \\ --late instrument after optimization: the stores and lines of the
+ \\ code that runs, not of the source
+ \\ --plugin SO the pass (default: ../lib/ztrace-pass.so from this program)
+ \\ --rt A the runtime (default: ../lib/libztrace-rt.a)
+ \\
+;
+
+pub fn run(init: std.process.Init, args: []const [:0]const u8) !void {
+ const arena = init.arena.allocator();
+ var instr: []const u8 = "lines,calls,vars,stores";
+ var only: ?[]const u8 = null;
+ var mem: ?[]const u8 = null;
+ var late = false;
+ var plugin: ?[]const u8 = null;
+ var rt: ?[]const u8 = null;
+ var i: usize = 0;
+ while (i < args.len) : (i += 1) {
+ const arg = args[i];
+ if (std.mem.eql(u8, arg, "--")) {
+ i += 1;
+ break;
+ } else if (std.mem.eql(u8, arg, "--late")) {
+ late = true;
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--instr")) {
+ i += 1;
+ instr = args[i];
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--only")) {
+ i += 1;
+ only = args[i];
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--mem")) {
+ i += 1;
+ mem = args[i];
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--plugin")) {
+ i += 1;
+ plugin = args[i];
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--rt")) {
+ i += 1;
+ rt = args[i];
+ } else fail(usage, .{});
+ }
+ if (i >= args.len) fail(usage, .{});
+ const lib = try std.fs.path.join(arena, &.{ try std.process.executableDirPathAlloc(init.io, arena), "..", "lib" });
+
+ var argv: std.ArrayList([]const u8) = .empty;
+ for (args[i..]) |arg| try argv.append(arena, arg);
+ // What a command that only links does not use is no warning.
+ try argv.appendSlice(arena, &.{ "--start-no-unused-arguments", "-g" });
+ // The plugin's own words, which it checks; the rest are clang's flags.
+ var pass: std.ArrayList(u8) = .empty;
+ var words = std.mem.tokenizeScalar(u8, instr, ',');
+ while (words.next()) |word| {
+ if (std.mem.eql(u8, word, "edges")) {
+ try argv.append(arena, "-fsanitize-coverage=trace-pc-guard");
+ } else if (std.mem.eql(u8, word, "cmps")) {
+ try argv.append(arena, "-fsanitize-coverage=trace-pc-guard,trace-cmp");
+ } else if (std.mem.eql(u8, word, "cyg")) {
+ try argv.append(arena, "-finstrument-functions");
+ } else try pass.print(arena, "{s}{s}", .{ if (pass.items.len > 0) "," else "", word });
+ }
+ if (pass.items.len > 0) {
+ const so = plugin orelse try std.fs.path.join(arena, &.{ lib, "ztrace-pass.so" });
+ // -load as well: the plugin's options must exist when -mllvm is read,
+ // which is before -fpass-plugin loads it.
+ try argv.appendSlice(arena, &.{ try std.fmt.allocPrint(arena, "-fpass-plugin={s}", .{so}), "-Xclang", "-load", "-Xclang", so });
+ try argv.appendSlice(arena, &.{ "-mllvm", try std.fmt.allocPrint(arena, "-ztrace-instr={s}", .{pass.items}) });
+ if (only) |globs| try argv.appendSlice(arena, &.{ "-mllvm", try std.fmt.allocPrint(arena, "-ztrace-only={s}", .{globs}) });
+ if (mem) |globs| try argv.appendSlice(arena, &.{ "-mllvm", try std.fmt.allocPrint(arena, "-ztrace-mem={s}", .{globs}) });
+ if (late) try argv.appendSlice(arena, &.{ "-mllvm", "-ztrace-late" });
+ }
+ try argv.append(arena, "--end-no-unused-arguments");
+ // The command links unless it says where to stop. The whole archive: with
+ // -fsanitize-coverage clang links weak callbacks of its own first, and
+ // only a runtime already in the link replaces them. -x none: after an
+ // -x c the archive would be read as source.
+ const links = for (args[i..]) |arg| {
+ if (std.mem.eql(u8, arg, "-c") or std.mem.eql(u8, arg, "-S") or std.mem.eql(u8, arg, "-E") or std.mem.eql(u8, arg, "-fsyntax-only")) break false;
+ } else true;
+ if (links) try argv.appendSlice(arena, &.{ "-x", "none", "-Wl,--whole-archive", rt orelse try std.fs.path.join(arena, &.{ lib, "libztrace-rt.a" }), "-Wl,--no-whole-archive" });
+
+ const err = std.process.replace(init.io, .{ .argv = argv.items });
+ fail("{s}: {t}\n", .{ argv.items[0], err });
+}
diff --git a/src/cli/main.zig b/src/cli/main.zig
index 72b894a..1ac019f 100644
--- a/src/cli/main.zig
+++ b/src/cli/main.zig
@@ -9,6 +9,7 @@ const commands = .{
.run = @import("run.zig"),
.dump = @import("dump.zig"),
.show = @import("show.zig"),
+ .cc = @import("cc.zig"),
};
const usage =
@@ -19,6 +20,7 @@ const usage =
\\ run record a program that carries a ring producer (agent, instrumentation)
\\ dump print a recording's events
\\ show print a recording's summary, or the program's state at a moment
+ \\ cc compile a program with instrumentation that records it
\\
\\`ztrace COMMAND --help` for each.
\\
diff --git a/src/instr/bench.zig b/src/instr/bench.zig
new file mode 100644
index 0000000..38ad1a3
--- /dev/null
+++ b/src/instr/bench.zig
@@ -0,0 +1,70 @@
+//! What instrumentation costs, measured on a target: runs PROGRAM and prints
+//! one line, its wall time in milliseconds and the events it emitted by kind.
+//!
+//! bench PROGRAM ARGS with a ring, drained and counted, nothing recorded
+//! bench --untraced PROGRAM ARGS with no ring: the calls return at once
+//! bench --step PROGRAM ARGS held at each `line` by the ring's stop mask, resumed at once
+//!
+//! llvm/bench.sh makes the tables from it.
+const std = @import("std");
+const linux = std.os.linux;
+const zt = @import("ztrace");
+
+var counts: [64]u64 = @splat(0);
+
+pub fn main(init: std.process.Init) !void {
+ const arena = init.arena.allocator();
+ const args = try init.minimal.args.toSlice(arena);
+ const mode: enum { ring, untraced, step } = if (args.len > 1 and std.mem.eql(u8, args[1], "--untraced")) .untraced else if (args.len > 1 and std.mem.eql(u8, args[1], "--step")) .step else .ring;
+ const rest = args[@as(usize, 1) + @intFromBool(mode != .ring) ..];
+ if (rest.len == 0) return error.Usage;
+ const argv = try arena.allocSentinel(?[*:0]const u8, rest.len, null);
+ for (argv, rest) |*dst, s| dst.* = s.ptr;
+ const env = init.minimal.environ.block.slice;
+
+ const start = zt.event.now();
+ if (mode == .untraced) {
+ const pid = linux.fork();
+ if (pid == 0) {
+ _ = linux.execve(argv[0].?, argv.ptr, env.ptr);
+ linux.exit_group(127);
+ }
+ var status: u32 = 0;
+ _ = linux.waitpid(@intCast(pid), @ptrCast(&status), 0);
+ } else {
+ var session = try zt.host.Session.spawn(arena, argv[0].?, argv.ptr, env, .{ .stop_mask = if (mode == .step) zt.Kind.line.bit() else 0 });
+ defer session.close();
+ const ring = &session.ring;
+ // Step mode answers each stop at once. Otherwise the consumer drains
+ // what there is and sleeps a moment, never on the ring's futex: so
+ // the producer pays neither a wake nor for a cache line the consumer
+ // keeps taking, and the time is the cost of producing.
+ 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 = 0;
+ } else if (mode == .step) std.atomic.spinLoopHint() else _ = linux.nanosleep(&.{ .sec = 0, .nsec = 200_000 }, null);
+ continue;
+ };
+ const kind = rec.ev.kind;
+ counts[@intFromEnum(kind)] += 1;
+ ring.advance(rec);
+ if (mode == .step and kind == .line) ring.resumeAll();
+ }
+ }
+ const ms = @as(f64, @floatFromInt(zt.event.now() - start)) / 1e6;
+
+ var buf: [1024]u8 = undefined;
+ var out = std.Io.File.stdout().writer(init.io, &buf);
+ const w = &out.interface;
+ var total: u64 = 0;
+ for (counts) |n| total += n;
+ try w.print("{d:.2} {d}", .{ ms, total });
+ for (counts, 0..) |n, kind| {
+ if (n > 0) try w.print(" {t}={d}", .{ @as(zt.Kind, @enumFromInt(kind)), n });
+ }
+ try w.print("\n", .{});
+ try w.flush();
+}
diff --git a/src/instr/rt.zig b/src/instr/rt.zig
new file mode 100644
index 0000000..3719409
--- /dev/null
+++ b/src/instr/rt.zig
@@ -0,0 +1,227 @@
+//! libztrace-rt.a: what compiler-instrumented code calls, linked into the
+//! target; every call becomes an event in the ring the tracer handed over,
+//! or returns at once when there is none. Two faces:
+//!
+//! Our pass (llvm/pass.cpp):
+//! __zt_line(file, line, column) line a0=file a1=line a2=column
+//! __zt_store(addr, size) mem_write a0=addr a1=len, the bytes (see `wrote`)
+//! __zt_load(addr, size) mem_read a0=addr a1=len
+//! __zt_enter(name, type, sp, site) call a0=function name a1=call site a2=sp a3=function type
+//! __zt_exit(name, value, size) ret a0=function name a1=value, aux=bytes of value (0: none)
+//! __zt_var(addr, size, name, type, arg) variable a0=addr a1=size a2=name a3=type, aux=N for the Nth parameter
+//! file, name and type arrive as pointers to text records and leave as
+//! string ids. The records, and the program's globals, sit in two sections
+//! the pass filled: before the first event the runtime numbers the texts
+//! and emits each as a `string` (from thread 0: no thread), and each global
+//! as a `variable` with one `mem_write` of what it holds, from the thread
+//! that got there first, which is inside no call yet. A local is declared,
+//! never dumped: what it holds arrives with the stores.
+//!
+//! No pc in `line`, `mem_write` and `mem_read`, though event.zig has a
+//! place for one: the source line is the place, and seven bytes would be a
+//! third of each of them in a recording.
+//!
+//! Stock clang, no plugin:
+//! -fsanitize-coverage=trace-pc-guard edge a0=pc
+//! -fsanitize-coverage=trace-cmp cmp aux=operand bytes a0=pc a1=lhs a2=rhs
+//! -finstrument-functions call a0=function address a1=call site a2=frame
+//! ret a0=function address
+//!
+//! Raw syscalls only, no allocation: a store may be anywhere.
+// shortcut: one program, one runtime: the texts of a shared library loaded later are never numbered; walk its sections on dlopen when a target needs it.
+const std = @import("std");
+const linux = std.os.linux;
+const zt = @import("ztrace");
+
+/// 0 untried, 1 starting, 2 tracing, 3 not traced.
+var state: std.atomic.Value(u8) = .init(0);
+var ring: *zt.Ring = undefined;
+
+fn start(tid: u32) bool {
+ @branchHint(.cold);
+ while (true) switch (state.load(.acquire)) {
+ 2 => return true,
+ 3 => return false,
+ // Another thread is emitting the names: nothing may get ahead of them.
+ 1 => _ = linux.sched_yield(),
+ else => if (state.cmpxchgStrong(0, 1, .acquire, .monotonic) == null) {
+ const found = zt.client.get();
+ if (found) |r| {
+ ring = r;
+ names();
+ globals(tid);
+ }
+ state.store(if (found != null) 2 else 3, .release);
+ },
+ };
+}
+
+fn put(tid: u32, kind: zt.Kind, aux: u16, a: [6]u64, payload: []const u8) void {
+ ring.emit(.{ .ts = zt.event.now(), .tid = tid, .kind = kind, .aux = aux, .a = a }, payload);
+}
+
+const Thread = struct {
+ /// A gettid a thread, not an event: the syscall would be half the cost
+ /// of an event.
+ // shortcut: a forked child keeps its parent's tid; reset it in a fork hook once a target forks.
+ tid: u32 = 0,
+ inside: bool = false,
+};
+threadlocal var thread: Thread = .{};
+
+/// The calling thread, for one event; `inside` is the caller's to clear.
+/// Null when nobody listens, or when the thread is already in here: what the
+/// runtime calls (memcpy and strlen, in a libc compiled with the pass) must
+/// not trace itself.
+fn enter() ?*Thread {
+ const s = state.load(.monotonic);
+ if (s == 3) return null;
+ const t = &thread;
+ if (t.inside) return null;
+ t.inside = true;
+ if (t.tid == 0) t.tid = @intCast(linux.gettid());
+ if (s == 2 or start(t.tid)) return t;
+ t.inside = false;
+ return null;
+}
+
+/// An event with no text in it: a text's id is read after `enter`, which
+/// may be what numbers it.
+fn emit(kind: zt.Kind, aux: u16, a: [6]u64, payload: []const u8) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, kind, aux, a, payload);
+}
+
+/// The `mem_write`s of one write (a store, a memset, a memcpy, a global's
+/// first contents), in pieces that fit the smallest ring. a1 is how much was
+/// written from a0 on, so the first piece says the whole length; a payload
+/// shorter than a1 is all that is recorded of it. A write is recorded up to
+/// `most`: a megabyte cleared is not a megabyte in the recording.
+const most = 64 << 10;
+
+fn wrote(tid: u32, addr: usize, len: usize) void {
+ var at: usize = 0;
+ while (at < @min(len, most)) : (at += 2048) {
+ const bytes: [*]const u8 = @ptrFromInt(addr + at);
+ put(tid, .mem_write, 0, .{ addr + at, len - at, 0, 0, 0, 0 }, bytes[0..@min(len - at, 2048)]);
+ }
+}
+
+/// The bounds the linker gives a section named like a C identifier; both 0
+/// when no object has the section.
+fn section(comptime name: []const u8) [2]usize {
+ return .{
+ @intFromPtr(@extern(?*const u8, .{ .name = "__start_" ++ name, .linkage = .weak })),
+ @intFromPtr(@extern(?*const u8, .{ .name = "__stop_" ++ name, .linkage = .weak })),
+ };
+}
+
+/// A text of the program, in section ztrace_strs: this, then the text,
+/// padded to 8 bytes.
+const Text = extern struct {
+ /// The string id. The pass leaves 0, to be numbered here from 1: ids
+ /// small enough to cost a recording a byte or two each. It fixes only
+ /// the ids nothing but a viewer looks up (`types.defId`).
+ id: u64,
+ len: u64,
+};
+
+fn names() void {
+ var at, const end = section("ztrace_strs");
+ var next: u64 = 0;
+ while (at < end) {
+ const text: *Text = @ptrFromInt(at);
+ if (text.id == 0) {
+ next += 1;
+ text.id = next;
+ }
+ const bytes: [*]const u8 = @ptrFromInt(at + @sizeOf(Text));
+ // A text the ring cannot hold is cut: better than none of it.
+ put(0, .string, 0, .{ text.id, 0, 0, 0, 0, 0 }, bytes[0..@min(text.len, ring.hdr.capacity / 2)]);
+ at += @sizeOf(Text) + std.mem.alignForward(usize, text.len, 8);
+ }
+}
+
+/// ztrace_vars: (address, size, name, type)*.
+fn globals(tid: u32) void {
+ var at, const end = section("ztrace_vars");
+ while (at < end) : (at += 32) {
+ const g: *const extern struct { addr: u64, size: u64, name: *const Text, type: *const Text } = @ptrFromInt(at);
+ put(tid, .variable, 0, .{ g.addr, g.size, g.name.id, g.type.id, 0, 0 }, "");
+ wrote(tid, g.addr, g.size);
+ }
+}
+
+// The pass.
+
+export fn __zt_line(file: *const Text, line: u32, column: u32) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, .line, 0, .{ file.id, line, column, 0, 0, 0 }, "");
+}
+
+export fn __zt_store(addr: usize, size: u64) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ wrote(t.tid, addr, size);
+}
+
+export fn __zt_load(addr: usize, size: u64) void {
+ emit(.mem_read, 0, .{ addr, size, 0, 0, 0, 0 }, "");
+}
+
+export fn __zt_enter(name: *const Text, type_text: *const Text, sp: usize, site: usize) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, .call, 0, .{ name.id, site, sp, type_text.id, 0, 0 }, "");
+}
+
+export fn __zt_exit(name: *const Text, value: u64, size: u32) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, .ret, @intCast(size), .{ name.id, value, 0, 0, 0, 0 }, "");
+}
+
+export fn __zt_var(addr: usize, size: u64, name: *const Text, type_text: *const Text, arg: u32) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, .variable, @truncate(arg), .{ addr, size, name.id, type_text.id, 0, 0 }, "");
+}
+
+// Stock clang.
+
+export fn __sanitizer_cov_trace_pc_guard_init(_: *u32, _: *u32) void {}
+
+export fn __sanitizer_cov_trace_pc_guard(_: *u32) void {
+ emit(.edge, 0, .{ @returnAddress(), 0, 0, 0, 0, 0 }, "");
+}
+
+comptime {
+ for (.{ u8, u16, u32, u64 }) |T| {
+ const f = struct {
+ fn cmp(lhs: T, rhs: T) callconv(.c) void {
+ emit(.cmp, @sizeOf(T), .{ @returnAddress(), lhs, rhs, 0, 0, 0 }, "");
+ }
+ }.cmp;
+ for (.{ "", "const_" }) |c| @export(&f, .{ .name = std.fmt.comptimePrint("__sanitizer_cov_trace_{s}cmp{d}", .{ c, @sizeOf(T) }) });
+ }
+}
+
+/// `cases` is (count, bits, values...). One event a switch, not one a case:
+/// rhs is the case taken, or the first when it is the default.
+export fn __sanitizer_cov_trace_switch(value: u64, cases: [*]const u64) void {
+ var rhs = cases[2];
+ for (cases[2..][0..cases[0]]) |c| {
+ if (c == value) rhs = c;
+ }
+ emit(.cmp, @intCast(cases[1] / 8), .{ @returnAddress(), value, rhs, 0, 0, 0 }, "");
+}
+
+export fn __cyg_profile_func_enter(function: usize, site: usize) void {
+ emit(.call, 0, .{ function, site, @frameAddress(), 0, 0, 0 }, "");
+}
+
+export fn __cyg_profile_func_exit(function: usize, _: usize) void {
+ emit(.ret, 0, .{ function, 0, 0, 0, 0, 0 }, "");
+}
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));
+}
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);
+}
diff --git a/targets/instr_bfs.c b/targets/instr_bfs.c
new file mode 100644
index 0000000..a7b176e
--- /dev/null
+++ b/targets/instr_bfs.c
@@ -0,0 +1,39 @@
+// Breadth-first search from vertex 0 of a seven-vertex graph, one vertex
+// out of reach, argv[1] times (by default once). Exits with the number of
+// vertices reached.
+#include <stdlib.h>
+
+#define N 7
+static const int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}};
+static int adjacent[N][N];
+static int distance[N];
+static int order[N];
+
+static int bfs(int from) {
+ int queue[N], head = 0, tail = 0;
+ for (int v = 0; v < N; v++) distance[v] = -1;
+ distance[from] = 0;
+ queue[tail++] = from;
+ while (head < tail) {
+ int v = queue[head];
+ order[head++] = v;
+ for (int w = 0; w < N; w++) {
+ if (adjacent[v][w] && distance[w] < 0) {
+ distance[w] = distance[v] + 1;
+ queue[tail++] = w;
+ }
+ }
+ }
+ return tail;
+}
+
+int main(int argc, char **argv) {
+ int rounds = argc > 1 ? atoi(argv[1]) : 1;
+ int reached = 0;
+ for (unsigned i = 0; i < sizeof edges / sizeof *edges; i++) {
+ adjacent[edges[i][0]][edges[i][1]] = 1;
+ adjacent[edges[i][1]][edges[i][0]] = 1;
+ }
+ while (rounds-- > 0) reached = bfs(0);
+ return reached;
+}
diff --git a/targets/instr_big.c b/targets/instr_big.c
new file mode 100644
index 0000000..ce89947
--- /dev/null
+++ b/targets/instr_big.c
@@ -0,0 +1,11 @@
+// A megabyte set, then copied: a recording keeps the first 64 KiB of each
+// write. Exits with the last byte copied.
+#include <string.h>
+
+static char from[1 << 20], to[1 << 20];
+
+int main(void) {
+ memset(from, 7, sizeof from);
+ memcpy(to, from, sizeof to);
+ return to[sizeof to - 1];
+}
diff --git a/targets/instr_fib.c b/targets/instr_fib.c
new file mode 100644
index 0000000..9da9306
--- /dev/null
+++ b/targets/instr_fib.c
@@ -0,0 +1,12 @@
+// fib(n) the slow way: a call tree to draw. Exits with fib(argv[1]), by
+// default fib(6).
+#include <stdlib.h>
+
+static unsigned fib(unsigned n) {
+ if (n < 2) return n;
+ return fib(n - 1) + fib(n - 2);
+}
+
+int main(int argc, char **argv) {
+ return (int)fib(argc > 1 ? (unsigned)atoi(argv[1]) : 6);
+}
diff --git a/targets/instr_list.c b/targets/instr_list.c
new file mode 100644
index 0000000..aaa6c8a
--- /dev/null
+++ b/targets/instr_list.c
@@ -0,0 +1,46 @@
+// A linked list of five squares, built at its head and then reversed in
+// place, argv[1] times (by default once). The last list is left standing.
+// Exits with the sum of its values.
+#include <stdlib.h>
+
+struct node {
+ int value;
+ struct node *next;
+};
+
+static struct node *list;
+
+static struct node *push(struct node *head, int value) {
+ struct node *n = malloc(sizeof *n);
+ n->value = value;
+ n->next = head;
+ return n;
+}
+
+static struct node *reverse(struct node *head) {
+ struct node *prev = NULL;
+ while (head) {
+ struct node *next = head->next;
+ head->next = prev;
+ prev = head;
+ head = next;
+ }
+ return prev;
+}
+
+int main(int argc, char **argv) {
+ int rounds = argc > 1 ? atoi(argv[1]) : 1;
+ int sum = 0;
+ while (rounds-- > 0) {
+ while (list) {
+ struct node *next = list->next;
+ free(list);
+ list = next;
+ }
+ for (int i = 1; i <= 5; i++) list = push(list, i * i);
+ list = reverse(list);
+ sum = 0;
+ for (struct node *n = list; n; n = n->next) sum += n->value;
+ }
+ return sum;
+}
diff --git a/targets/instr_own.c b/targets/instr_own.c
new file mode 100644
index 0000000..5c30141
--- /dev/null
+++ b/targets/instr_own.c
@@ -0,0 +1,27 @@
+// A program with its own memcpy and strlen, as one linked with a libc
+// compiled by the pass has: the runtime calls them too, and must not trace
+// itself. Exits with the length of the string it copied.
+#include <stddef.h>
+
+void *memcpy(void *to, const void *from, size_t n) {
+ char *d = to;
+ const char *s = from;
+ for (size_t i = 0; i < n; i++) d[i] = s[i];
+ return to;
+}
+
+size_t strlen(const char *s) {
+ size_t n = 0;
+ while (s[n]) n++;
+ return n;
+}
+
+// Through pointers: the compiler would do a known memcpy inline.
+void *(*volatile copy)(void *, const void *, size_t) = memcpy;
+size_t (*volatile length)(const char *) = strlen;
+
+int main(void) {
+ char to[8], from[8] = "abcdefg";
+ copy(to, from, sizeof from);
+ return (int)length(to);
+}
diff --git a/targets/instr_sort.c b/targets/instr_sort.c
new file mode 100644
index 0000000..411b348
--- /dev/null
+++ b/targets/instr_sort.c
@@ -0,0 +1,44 @@
+// Bubble sort and insertion sort of the same eight numbers, argv[1] times
+// (by default once). Exits with the smallest plus the largest.
+#include <stdlib.h>
+#include <string.h>
+
+#define N 8
+// Not const, not static: -O2 must sort at run time, not when compiling.
+int unsorted[N] = {5, 2, 9, 1, 7, 3, 8, 4};
+
+static void bubble(int *a, int n) {
+ for (int i = 0; i < n - 1; i++) {
+ for (int j = 0; j < n - 1 - i; j++) {
+ if (a[j] > a[j + 1]) {
+ int t = a[j];
+ a[j] = a[j + 1];
+ a[j + 1] = t;
+ }
+ }
+ }
+}
+
+static void insertion(int *a, int n) {
+ for (int i = 1; i < n; i++) {
+ int key = a[i];
+ int j = i - 1;
+ while (j >= 0 && a[j] > key) {
+ a[j + 1] = a[j];
+ j--;
+ }
+ a[j + 1] = key;
+ }
+}
+
+int main(int argc, char **argv) {
+ int rounds = argc > 1 ? atoi(argv[1]) : 1;
+ int bubbled[N], inserted[N];
+ while (rounds-- > 0) {
+ memcpy(bubbled, unsorted, sizeof unsorted);
+ memcpy(inserted, unsorted, sizeof unsorted);
+ bubble(bubbled, N);
+ insertion(inserted, N);
+ }
+ return bubbled[0] + inserted[N - 1];
+}