tiny.profiling.ir

1const std = @import("std");23pub const normalization_version = "tiny.profiling.ir-origin/v1";4pub const maximum_line_bytes: u32 = 16 * 1024;5pub const maximum_lines: u32 = 1_000_000;6pub const maximum_functions: u32 = 100_000;7pub const maximum_findings: u16 = 64;8pub const maximum_origins: u16 = 64;9pub const maximum_symbol_bytes: u16 = 240;1011pub const Limits = struct {12    line_bytes: u32 = maximum_line_bytes,13    lines: u32 = maximum_lines,14    functions: u32 = maximum_functions,15    findings: u16 = maximum_findings,16    origins: u16 = maximum_origins,1718    fn assertValid(self: Limits) void {19        std.debug.assert(self.line_bytes > 0);20        std.debug.assert(self.line_bytes <= maximum_line_bytes);21        std.debug.assert(self.lines > 0);22        std.debug.assert(self.lines <= maximum_lines);23        std.debug.assert(self.functions > 0);24        std.debug.assert(self.functions <= maximum_functions);25        std.debug.assert(self.findings > 0);26        std.debug.assert(self.findings <= maximum_findings);27        std.debug.assert(self.origins > 0);28        std.debug.assert(self.origins <= maximum_origins);29    }30};3132pub const Kind = enum {33    memcpy,34    stack,35    specialization,36};3738pub const Symbol = struct {39    bytes: [maximum_symbol_bytes]u8 = undefined,40    len: u16,4142    fn init(value: []const u8) !Symbol {43        if (value.len == 0) return error.EmptyIrSymbol;44        if (value.len > maximum_symbol_bytes) return error.IrSymbolTooLong;45        var result = Symbol{ .len = @intCast(value.len) };46        @memcpy(result.bytes[0..value.len], value);47        return result;48    }4950    pub fn slice(self: *const Symbol) []const u8 {51        return self.bytes[0..self.len];52    }53};5455pub const Finding = struct {56    kind: Kind,57    function: Symbol,58    bytes: u64 = 0,59    occurrences: u32 = 1,60    ir_lines: u32 = 0,61};6263pub const Audit = struct {64    line_count: u32 = 0,65    function_count: u32 = 0,66    findings: [maximum_findings]Finding = undefined,67    finding_count: u16 = 0,6869    pub fn items(self: *const Audit) []const Finding {70        return self.findings[0..self.finding_count];71    }72};7374const Current = struct {75    name: Symbol,76    origin: ?Symbol,77    line_count: u32,78};7980const Origin = struct {81    name: Symbol,82    occurrences: u32,83    line_count: u32,84};8586const Parser = struct {87    limits: Limits,88    audit: Audit = .{},89    current: ?Current = null,90    origins: [maximum_origins]Origin = undefined,91    origin_count: u16 = 0,9293    fn ingest(self: *Parser, raw_line: []const u8) !void {94        if (raw_line.len > self.limits.line_bytes) return error.IrLineTooLong;95        if (self.audit.line_count == self.limits.lines) {96            return error.IrLineLimitExceeded;97        }98        self.audit.line_count += 1;99        const line = std.mem.trim(u8, raw_line, " \t\r");100        if (std.mem.startsWith(u8, line, "define ")) {101            if (self.current != null) return error.NestedIrFunction;102            try self.beginFunction(try functionName(line));103            return;104        }105        if (self.current) |*current| {106            current.line_count += 1;107            if (try constantMemcpyBytes(line)) |byte_count| {108                try self.addFinding(.{109                    .kind = .memcpy,110                    .function = current.name,111                    .bytes = byte_count,112                });113            }114            if (try fixedAllocaBytes(line)) |byte_count| {115                try self.addFinding(.{116                    .kind = .stack,117                    .function = current.name,118                    .bytes = byte_count,119                });120            }121            if (std.mem.eql(u8, line, "}")) try self.finishFunction();122        }123    }124125    fn beginFunction(self: *Parser, name: []const u8) !void {126        if (self.audit.function_count == self.limits.functions) {127            return error.IrFunctionLimitExceeded;128        }129        self.audit.function_count += 1;130        const normalized = normalizeOrigin(name);131        self.current = .{132            .name = try Symbol.init(name),133            .origin = if (normalized.changed)134                try Symbol.init(normalized.name)135            else136                null,137            .line_count = 1,138        };139    }140141    fn finishFunction(self: *Parser) !void {142        const current = self.current orelse return error.MissingIrFunction;143        self.current = null;144        const origin = current.origin orelse return;145        for (self.origins[0..self.origin_count]) |*entry| {146            if (std.mem.eql(u8, entry.name.slice(), origin.slice())) {147                entry.occurrences += 1;148                entry.line_count += current.line_count;149                return;150            }151        }152        if (self.origin_count == self.limits.origins) {153            return error.IrOriginLimitExceeded;154        }155        self.origins[self.origin_count] = .{156            .name = origin,157            .occurrences = 1,158            .line_count = current.line_count,159        };160        self.origin_count += 1;161    }162163    fn finish(self: *Parser) !Audit {164        if (self.current != null) return error.UnterminatedIrFunction;165        for (self.origins[0..self.origin_count]) |origin| {166            if (origin.occurrences < 2) continue;167            try self.addFinding(.{168                .kind = .specialization,169                .function = origin.name,170                .occurrences = origin.occurrences,171                .ir_lines = origin.line_count,172            });173        }174        return self.audit;175    }176177    fn addFinding(self: *Parser, finding: Finding) !void {178        if (self.audit.finding_count == self.limits.findings) {179            return error.IrFindingLimitExceeded;180        }181        self.audit.findings[self.audit.finding_count] = finding;182        self.audit.finding_count += 1;183    }184};185186pub fn parse(reader: *std.Io.Reader, limits: Limits) !Audit {187    limits.assertValid();188    var parser = Parser{ .limits = limits };189    while (true) {190        const line = try reader.takeDelimiter('\n');191        try parser.ingest(line orelse break);192    }193    return parser.finish();194}195196const Normalized = struct {197    name: []const u8,198    changed: bool,199};200201fn normalizeOrigin(name: []const u8) Normalized {202    const marker = "__anon_";203    const marker_index = std.mem.lastIndexOf(u8, name, marker) orelse204        return .{ .name = name, .changed = false };205    const suffix = name[marker_index + marker.len ..];206    if (suffix.len == 0) return .{ .name = name, .changed = false };207    for (suffix) |byte| {208        if (!std.ascii.isDigit(byte)) {209            return .{ .name = name, .changed = false };210        }211    }212    if (marker_index == 0) return .{ .name = name, .changed = false };213    return .{ .name = name[0..marker_index], .changed = true };214}215216fn functionName(line: []const u8) ![]const u8 {217    const at = std.mem.indexOfScalar(u8, line, '@') orelse218        return error.InvalidIrFunction;219    const name_start = at + 1;220    if (name_start == line.len) return error.InvalidIrFunction;221    if (line[name_start] != '"') {222        const end = std.mem.indexOfScalarPos(u8, line, name_start, '(') orelse223            return error.InvalidIrFunction;224        return line[name_start..end];225    }226    var index = name_start + 1;227    var escaped = false;228    while (index < line.len) : (index += 1) {229        const byte = line[index];230        if (escaped) {231            escaped = false;232        } else if (byte == '\\') {233            escaped = true;234        } else if (byte == '"') {235            return line[name_start + 1 .. index];236        }237    }238    return error.InvalidIrFunction;239}240241fn constantMemcpyBytes(line: []const u8) !?u64 {242    const name = "@llvm.memcpy";243    const call = std.mem.indexOf(u8, line, name) orelse return null;244    const open = std.mem.indexOfScalarPos(u8, line, call + name.len, '(') orelse245        return error.InvalidIrMemcpy;246    const length = argumentAt(line[open + 1 ..], 2) orelse247        return error.InvalidIrMemcpy;248    return parseIntegerConstant(length) orelse error.InvalidIrMemcpy;249}250251fn argumentAt(arguments: []const u8, requested: u8) ?[]const u8 {252    var current: u8 = 0;253    var start: usize = 0;254    var depth: u16 = 0;255    var quoted = false;256    var escaped = false;257    for (arguments, 0..) |byte, index| {258        if (escaped) {259            escaped = false;260            continue;261        }262        if (byte == '\\' and quoted) {263            escaped = true;264            continue;265        }266        if (byte == '"') {267            quoted = !quoted;268            continue;269        }270        if (quoted) continue;271        switch (byte) {272            '(', '[', '{', '<' => depth += 1,273            ']', '}', '>' => if (depth > 0) {274                depth -= 1;275            },276            ')' => if (depth == 0) {277                return if (current == requested) arguments[start..index] else null;278            } else {279                depth -= 1;280            },281            ',' => if (depth == 0) {282                if (current == requested) return arguments[start..index];283                current += 1;284                start = index + 1;285            },286            else => {},287        }288    }289    return if (current == requested) arguments[start..] else null;290}291292fn fixedAllocaBytes(line: []const u8) !?u64 {293    const marker = "alloca ";294    const index = std.mem.indexOf(u8, line, marker) orelse return null;295    const value = std.mem.trimStart(u8, line[index + marker.len ..], " \t");296    if (value.len == 0) return error.InvalidIrAlloca;297    if (value[0] == '[') return try arrayTypeBytes(value);298    const scalar_bytes = integerTypeBytes(value) orelse return null;299    const comma = std.mem.indexOfScalar(u8, value, ',') orelse300        return scalar_bytes;301    const count = parseIntegerConstant(value[comma + 1 ..]) orelse302        return scalar_bytes;303    return std.math.mul(u64, scalar_bytes, count) catch304        return error.IrSizeOverflow;305}306307fn arrayTypeBytes(value: []const u8) !?u64 {308    const close = std.mem.indexOfScalar(u8, value, ']') orelse309        return error.InvalidIrAlloca;310    const body = value[1..close];311    const separator = std.mem.indexOf(u8, body, " x ") orelse312        return error.InvalidIrAlloca;313    const count = std.fmt.parseInt(314        u64,315        std.mem.trim(u8, body[0..separator], " \t"),316        10,317    ) catch return error.InvalidIrAlloca;318    const scalar_bytes = integerTypeBytes(body[separator + 3 ..]) orelse319        return null;320    return std.math.mul(u64, count, scalar_bytes) catch321        return error.IrSizeOverflow;322}323324fn integerTypeBytes(value: []const u8) ?u64 {325    const trimmed = std.mem.trimStart(u8, value, " \t");326    if (trimmed.len < 2 or trimmed[0] != 'i') return null;327    var end: usize = 1;328    while (end < trimmed.len and std.ascii.isDigit(trimmed[end])) : (end += 1) {}329    if (end == 1) return null;330    const bits = std.fmt.parseInt(u64, trimmed[1..end], 10) catch return null;331    if (bits == 0 or bits % 8 != 0) return null;332    return bits / 8;333}334335fn parseIntegerConstant(value: []const u8) ?u64 {336    const trimmed = std.mem.trimStart(u8, value, " \t");337    if (trimmed.len < 3 or trimmed[0] != 'i') return null;338    var index: usize = 1;339    while (index < trimmed.len and std.ascii.isDigit(trimmed[index])) : (index += 1) {}340    if (index == 1 or index == trimmed.len or trimmed[index] != ' ') return null;341    index += 1;342    const start = index;343    while (index < trimmed.len and std.ascii.isDigit(trimmed[index])) : (index += 1) {}344    if (index == start) return null;345    return std.fmt.parseInt(u64, trimmed[start..index], 10) catch null;346}347348const copy_fixture =349    "define void @copy_fixture(ptr %target, ptr %source) {\n" ++350    "entry:\n" ++351    "  call void @llvm.memcpy.p0.p0.i64(" ++352    "ptr %target, ptr %source, i64 4100, i1 false)\n" ++353    "  ret void\n" ++354    "}\n";355356const stack_fixture =357    "define void @stack_fixture() {\n" ++358    "entry:\n" ++359    "  %buffer = alloca [10240 x i8], align 16\n" ++360    "  ret void\n" ++361    "}\n";362363const specialization_fixture =364    "define i32 @fixture.generic__anon_101(i32 %value) {\n" ++365    "  ret i32 %value\n" ++366    "}\n" ++367    "define i32 @fixture.generic__anon_202(i32 %value) {\n" ++368    "  ret i32 %value\n" ++369    "}\n";370371test "IR audit fixed copy fixture finds a 4 KiB by-value copy" {372    var reader = std.Io.Reader.fixed(copy_fixture);373    const audit = try parse(&reader, .{});374    try std.testing.expectEqual(@as(usize, 1), audit.items().len);375    const finding = audit.items()[0];376    try std.testing.expectEqual(Kind.memcpy, finding.kind);377    try std.testing.expectEqual(@as(u64, 4100), finding.bytes);378    try std.testing.expectEqualStrings("copy_fixture", finding.function.slice());379}380381test "IR audit fixed stack fixture finds a large stack candidate" {382    var reader = std.Io.Reader.fixed(stack_fixture);383    const audit = try parse(&reader, .{});384    try std.testing.expectEqual(@as(usize, 1), audit.items().len);385    const finding = audit.items()[0];386    try std.testing.expectEqual(Kind.stack, finding.kind);387    try std.testing.expectEqual(@as(u64, 10240), finding.bytes);388    try std.testing.expectEqualStrings("stack_fixture", finding.function.slice());389}390391test "IR audit fixed specialization fixture groups duplicate bodies" {392    var reader = std.Io.Reader.fixed(specialization_fixture);393    const audit = try parse(&reader, .{});394    try std.testing.expectEqual(@as(usize, 1), audit.items().len);395    const finding = audit.items()[0];396    try std.testing.expectEqual(Kind.specialization, finding.kind);397    try std.testing.expectEqual(@as(u32, 2), finding.occurrences);398    try std.testing.expectEqual(@as(u32, 6), finding.ir_lines);399    try std.testing.expectEqualStrings("fixture.generic", finding.function.slice());400    try std.testing.expectEqualStrings(401        "tiny.profiling.ir-origin/v1",402        normalization_version,403    );404}405406test "IR audit rejects input beyond caller bounds" {407    var line_reader = std.Io.Reader.fixed("12345\n");408    try std.testing.expectError(409        error.IrLineTooLong,410        parse(&line_reader, .{ .line_bytes = 4 }),411    );412413    var function_reader = std.Io.Reader.fixed(414        "define void @one() {\n}\ndefine void @two() {\n}\n",415    );416    try std.testing.expectError(417        error.IrFunctionLimitExceeded,418        parse(&function_reader, .{ .functions = 1 }),419    );420421    var finding_reader = std.Io.Reader.fixed(422        "define void @copies(ptr %a, ptr %b) {\n" ++423            "call void @llvm.memcpy.p0.p0.i64(ptr %a, ptr %b, i64 1, i1 false)\n" ++424            "call void @llvm.memcpy.p0.p0.i64(ptr %a, ptr %b, i64 2, i1 false)\n" ++425            "}\n",426    );427    try std.testing.expectError(428        error.IrFindingLimitExceeded,429        parse(&finding_reader, .{ .findings = 1 }),430    );431432    var origin_reader = std.Io.Reader.fixed(433        "define void @one__anon_1() {\n}\n" ++434            "define void @two__anon_2() {\n}\n",435    );436    try std.testing.expectError(437        error.IrOriginLimitExceeded,438        parse(&origin_reader, .{ .origins = 1 }),439    );440}

1pub const ir = @import("ir.zig");