emulator: Add deterministic instruction profiles

d9ccfba8227a3ce91c5065a241c2f94a33a99ca243ee17c9a07051200c1477ac
Record the exact ranges executed by the hosted JIT and interpreter.
Use Radiance source and function maps to report instruction counts
by PC, folded call stacks, and costs for individual invocations.
Keep profiling instrumentation out of ordinary translated code.

Change-Id: Id8c8a86497cd56d40469a39bce6e87a203f82f97
Alexis Sellier committed ago 1 parent a503d772
Makefile +3 -3
16 16
                 -march=native -flto
17 17
BLAKE3_CFLAGS := $(shell pkg-config --cflags libblake3)
18 18
BLAKE3_LIBS   := $(shell pkg-config --libs libblake3)
19 19
LDFLAGS       := -fuse-ld=lld -Wl,-z,stack-size=33554432
20 20
EMULATOR_SRCS := emulator.c abi_host.c abi_linux.c image_native.c image_rad0.c \
21 -
                 image_raw.c host_posix.c jit.c riscv/debug.c io.c riscv.c \
21 +
                 image_raw.c host_posix.c jit.c profile.c debug_map.c riscv/debug.c io.c riscv.c \
22 22
                 vector.c machine.c machine_cpu.c machine_csr.c machine_devices.c machine_fdt.c
23 23
24 24
default: bin/emulator
25 25
26 -
bin/emulator: $(EMULATOR_SRCS) jit.h bitmanip.h vector.h muldiv.h color.h types.h io.h host.h hosted.h riscv.h riscv/debug.h machine.h machine_internal.h
26 +
bin/emulator: $(EMULATOR_SRCS) profile.h debug_map.h jit.h bitmanip.h vector.h muldiv.h color.h types.h io.h host.h hosted.h riscv.h riscv/debug.h machine.h machine_internal.h
27 27
	@echo "cc    emulator => $@"
28 28
	@mkdir -p bin
29 29
	@$(CC) $(CPPFLAGS) $(CFLAGS) $(BLAKE3_CFLAGS) $(LDFLAGS) $(EMULATOR_SRCS) $(BLAKE3_LIBS) -o $@
30 30
31 31
install: bin/emulator
58 58
	@ASAN_OPTIONS=detect_leaks=0 timeout 30 bin/vector-machine-test
59 59
60 60
.PHONY: test-vector
61 61
62 62
# Compare hosted vector translation with architectural interpreter state.
63 -
bin/jit-vector-test: test/jit_vector.c jit.c jit.h vector.c vector.h riscv.c riscv.h riscv/debug.c riscv/debug.h bitmanip.h color.h types.h
63 +
bin/jit-vector-test: test/jit_vector.c jit.c jit.h profile.h vector.c vector.h riscv.c riscv.h riscv/debug.c riscv/debug.h bitmanip.h color.h types.h
64 64
	@mkdir -p bin
65 65
	@$(CC) $(CPPFLAGS) -std=c99 -O2 -g -Wall -Wextra -fsanitize=address,undefined test/jit_vector.c jit.c vector.c riscv.c riscv/debug.c -o $@
66 66
67 67
test-jit: bin/jit-vector-test test-jit-calls
68 68
	@ASAN_OPTIONS=detect_leaks=0 timeout 60 $<
debug_map.c added +164 -0
1 +
#include <stdio.h>
2 +
#include <stdlib.h>
3 +
#include <string.h>
4 +
5 +
#include "debug_map.h"
6 +
#include "hosted.h"
7 +
#include "io.h"
8 +
9 +
u8 *debug_read_sidecar(const char *program, const char *suffix, size_t *size) {
10 +
    size_t length = strlen(program) + strlen(suffix) + 1;
11 +
    char  *path   = malloc(length);
12 +
    if (!path)
13 +
        bail("cannot allocate sidecar path");
14 +
    snprintf(path, length, "%s%s", program, suffix);
15 +
    FILE *file = fopen(path, "rb");
16 +
    free(path);
17 +
    if (!file)
18 +
        return NULL;
19 +
    long length_on_disk = -1;
20 +
    if (fseek(file, 0, SEEK_END) == 0)
21 +
        length_on_disk = ftell(file);
22 +
    u8 *data = NULL;
23 +
    if (length_on_disk >= 0 && fseek(file, 0, SEEK_SET) == 0) {
24 +
        *size = (size_t)length_on_disk;
25 +
        data  = malloc(*size ? *size : 1);
26 +
        if (!data)
27 +
            bail("cannot allocate sidecar");
28 +
        if (fread(data, 1, *size, file) != *size) {
29 +
            free(data);
30 +
            data = NULL;
31 +
        }
32 +
    }
33 +
    fclose(file);
34 +
    return data;
35 +
}
36 +
37 +
static bool load_paths(struct debug_map *map, size_t size, u32 code_bytes) {
38 +
    const u8 *data = map->data;
39 +
    if (size < 4)
40 +
        return false;
41 +
    u32    count = decode_u32_le(data);
42 +
    size_t pos   = 4;
43 +
    if (count > (size - pos) / 4)
44 +
        return false;
45 +
    /* Validate lengths and locations before allocating paths. */
46 +
    for (u32 i = 0; i < count; i++) {
47 +
        if (size - pos < 4)
48 +
            return false;
49 +
        u32 len  = decode_u32_le(data + pos);
50 +
        pos     += 4;
51 +
        if (!len || len > size - pos || memchr(data + pos, 0, len))
52 +
            return false;
53 +
        pos += len;
54 +
    }
55 +
    if ((size - pos) % 12)
56 +
        return false;
57 +
    for (size_t i = pos; i < size; i += 12) {
58 +
        u32 pc = decode_u32_le(data + i);
59 +
        if (pc > code_bytes || pc % INSTR_SIZE ||
60 +
            decode_u32_le(data + i + 8) >= count)
61 +
            return false;
62 +
    }
63 +
64 +
    map->path_count = count;
65 +
    map->count      = (size - pos) / 12;
66 +
    map->paths      = calloc(count, sizeof(*map->paths));
67 +
    map->entries    = calloc(map->count, sizeof(*map->entries));
68 +
    if ((count && !map->paths) || (map->count && !map->entries))
69 +
        bail("cannot allocate source map");
70 +
    pos = 4;
71 +
    for (u32 i = 0; i < count; i++) {
72 +
        u32 len        = decode_u32_le(data + pos);
73 +
        pos           += 4;
74 +
        map->paths[i]  = malloc((size_t)len + 1);
75 +
        if (!map->paths[i])
76 +
            bail("cannot allocate source path");
77 +
        memcpy(map->paths[i], data + pos, len);
78 +
        map->paths[i][len]  = 0;
79 +
        pos                += len;
80 +
    }
81 +
    for (size_t i = 0; i < map->count; i++, pos += 12) {
82 +
        map->entries[i] =
83 +
            (struct debug_entry){ decode_u32_le(data + pos),
84 +
                                  decode_u32_le(data + pos + 4),
85 +
                                  map->paths[decode_u32_le(data + pos + 8)] };
86 +
    }
87 +
    return true;
88 +
}
89 +
90 +
static bool load_legacy(struct debug_map *map, size_t size, u32 code_bytes) {
91 +
    size_t count = 0;
92 +
    for (size_t pos = 0; pos < size; count++) {
93 +
        if (size - pos < 10)
94 +
            return false;
95 +
        u32 pc = decode_u32_le(map->data + pos);
96 +
        if (pc > code_bytes || pc % INSTR_SIZE)
97 +
            return false;
98 +
        const u8 *path = map->data + pos + 8;
99 +
        const u8 *end  = memchr(path, 0, size - pos - 8);
100 +
        if (!end || end == path)
101 +
            return false;
102 +
        pos = (size_t)(end - map->data) + 1;
103 +
    }
104 +
    map->entries = calloc(count, sizeof(*map->entries));
105 +
    if (count && !map->entries)
106 +
        bail("cannot allocate source map");
107 +
    map->count = count;
108 +
    size_t pos = 0;
109 +
    for (size_t i = 0; i < count; i++) {
110 +
        const char *path = (const char *)map->data + pos + 8;
111 +
        map->entries[i] =
112 +
            (struct debug_entry){ decode_u32_le(map->data + pos),
113 +
                                  decode_u32_le(map->data + pos + 4),
114 +
                                  path };
115 +
        pos += 9 + strlen(path);
116 +
    }
117 +
    return true;
118 +
}
119 +
120 +
static int compare_pc(const void *a, const void *b) {
121 +
    u32 left  = ((const struct debug_entry *)a)->pc;
122 +
    u32 right = ((const struct debug_entry *)b)->pc;
123 +
    return (left > right) - (left < right);
124 +
}
125 +
126 +
bool debug_map_load(
127 +
    struct debug_map *map, const char *program, u32 code_bytes
128 +
) {
129 +
    size_t size = 0;
130 +
    map->data   = debug_read_sidecar(program, ".debug", &size);
131 +
    if (!map->data)
132 +
        return true;
133 +
    if (!load_paths(map, size, code_bytes) &&
134 +
        !load_legacy(map, size, code_bytes)) {
135 +
        debug_map_free(map);
136 +
        return false;
137 +
    }
138 +
    if (map->count > 1)
139 +
        qsort(map->entries, map->count, sizeof(*map->entries), compare_pc);
140 +
    return true;
141 +
}
142 +
143 +
const struct debug_entry *debug_map_lookup(
144 +
    const struct debug_map *map, u32 pc
145 +
) {
146 +
    size_t start = 0, end = map->count;
147 +
    while (start < end) {
148 +
        size_t middle = start + (end - start) / 2;
149 +
        if (map->entries[middle].pc <= pc)
150 +
            start = middle + 1;
151 +
        else
152 +
            end = middle;
153 +
    }
154 +
    return start ? &map->entries[start - 1] : NULL;
155 +
}
156 +
157 +
void debug_map_free(struct debug_map *map) {
158 +
    for (size_t i = 0; i < map->path_count; i++)
159 +
        free(map->paths[i]);
160 +
    free(map->paths);
161 +
    free(map->entries);
162 +
    free(map->data);
163 +
    *map = (struct debug_map){ 0 };
164 +
}
debug_map.h added +36 -0
1 +
#ifndef DEBUG_MAP_H
2 +
#define DEBUG_MAP_H
3 +
4 +
#include <stddef.h>
5 +
6 +
#include "types.h"
7 +
8 +
/* Native PC mapped to one source location. */
9 +
struct debug_entry {
10 +
    u32         pc;     /* Byte offset from the first instruction. */
11 +
    u32         offset; /* Byte offset from the start of the source file. */
12 +
    const char *file;   /* Source path. */
13 +
};
14 +
15 +
/* Storage for a native source map. */
16 +
struct debug_map {
17 +
    struct debug_entry *entries;    /* Entries in PC order. */
18 +
    size_t              count;      /* Number of entries. */
19 +
    char              **paths;      /* Owned paths from the path table. */
20 +
    size_t              path_count; /* Number of owned paths. */
21 +
    u8                 *data;       /* Sidecar bytes, including legacy paths. */
22 +
};
23 +
24 +
/* Read a whole sidecar. Return NULL for an absent or unreadable file. */
25 +
u8 *debug_read_sidecar(const char *program, const char *suffix, size_t *size);
26 +
27 +
/* Load <program>.debug if present. Return false for an invalid map. */
28 +
bool debug_map_load(struct debug_map *map, const char *program, u32 code_bytes);
29 +
30 +
/* Return the source entry at or before the given code offset, or NULL. */
31 +
const struct debug_entry *debug_map_lookup(const struct debug_map *map, u32 pc);
32 +
33 +
/* Free all memory held by the map. */
34 +
void debug_map_free(struct debug_map *map);
35 +
36 +
#endif
emulator.c +161 -125
13 13
14 14
#include <blake3.h>
15 15
16 16
#include "bitmanip.h"
17 17
#include "color.h"
18 +
#include "debug_map.h"
18 19
#include "host.h"
19 20
#include "hosted.h"
20 21
#include "io.h"
21 22
#include "jit.h"
22 23
#include "machine.h"
23 24
#include "muldiv.h"
25 +
#include "profile.h"
24 26
#include "riscv.h"
25 27
#include "riscv/debug.h"
26 28
#include "types.h"
27 29
28 30
#ifndef PATH_MAX
42 44
) {
43 45
    fprintf(stderr, "%s:%d: assertion `%s` failed\n", file, line, condition);
44 46
    abort();
45 47
}
46 48
49 +
#if DATA_MEMORY_START > PROFILE_PC_MASK || JIT_MAX_BLOCK_INSNS > 256
50 +
#error "hosted JIT ranges must fit in a profile word"
51 +
#endif
52 +
47 53
/* Default physical memory size (128MB). */
48 54
#define DEFAULT_MEMORY_SIZE      (128 * 1024 * 1024)
49 55
/* Default data memory size. */
50 56
#define DEFAULT_DATA_MEMORY_SIZE (DEFAULT_MEMORY_SIZE - DATA_MEMORY_START)
51 57
/* Default stack size (256KB), allocated at the end of memory. */
77 83
};
78 84
79 85
/* Display mode for immediates and values. */
80 86
enum display { DISPLAY_HEX, DISPLAY_DEC };
81 87
82 -
/* Debug info entry mapping PC to source location. */
83 -
struct debug_entry {
84 -
    u32  pc;
85 -
    u32  offset;
86 -
    char file[PATH_MAX];
87 -
};
88 -
89 -
/* Debug info table. */
90 -
struct debug_info {
91 -
    struct debug_entry *entries;
92 -
    size_t              count;
93 -
    size_t              capacity;
94 -
};
95 -
96 -
/* Global debug info. */
97 -
static struct debug_info g_debug = { 0 };
88 +
static struct debug_map g_debug;
98 89
99 90
/* Snapshot of CPU and memory state for reversing execution. */
100 91
struct snapshot {
101 92
    struct cpu cpu;                 /* Copy of CPU state. */
102 93
    u8         memory[MEMORY_SIZE]; /* Copy of memory. */
218 209
static void cpu_execute(struct cpu *, enum display, bool headless);
219 210
static void emit_fault_diagnostics(struct cpu *, u32 pc);
220 211
221 212
/* Emulator runtime options, populated from CLI flags. */
222 213
struct emulator_options {
223 -
    bool stack_guard;
224 -
    u32  stack_size;
225 -
    bool debug_enabled;
226 -
    bool trace_headless;
227 -
    bool trace_enabled;
228 -
    bool trace_print_instructions;
229 -
    u32  trace_depth;
230 -
    u64  headless_max_steps;
231 -
    u32  memory_size;
232 -
    u32  data_memory_size;
233 -
    bool watch_enabled;
234 -
    u32  watch_addr;
235 -
    u32  watch_size;
236 -
    u32  watch_arm_pc;
237 -
    bool watch_zero_only;
238 -
    u32  watch_skip;
239 -
    bool watch_backtrace;
240 -
    u32  watch_backtrace_depth;
241 -
    bool validate_memory;
242 -
    bool count_instructions;
243 -
    bool jit_disabled;
244 -
    bool machine_mode;
245 -
    int  outcome_fd; /* Internal: descriptor for the outcome record, or -1. */
214 +
    bool        stack_guard;
215 +
    u32         stack_size;
216 +
    bool        debug_enabled;
217 +
    bool        trace_headless;
218 +
    bool        trace_enabled;
219 +
    bool        trace_print_instructions;
220 +
    u32         trace_depth;
221 +
    u64         headless_max_steps;
222 +
    u32         memory_size;
223 +
    u32         data_memory_size;
224 +
    bool        watch_enabled;
225 +
    u32         watch_addr;
226 +
    u32         watch_size;
227 +
    u32         watch_arm_pc;
228 +
    bool        watch_zero_only;
229 +
    u32         watch_skip;
230 +
    bool        watch_backtrace;
231 +
    u32         watch_backtrace_depth;
232 +
    bool        validate_memory;
233 +
    bool        count_instructions;
234 +
    bool        jit_disabled;
235 +
    const char *profile_prefix;   /* Prefix of folded stack and PC reports. */
236 +
    const char *profile_trace;    /* Ordered binary range stream. */
237 +
    const char *profile_function; /* Exact function name for call counts. */
238 +
    bool        machine_mode;
239 +
    int outcome_fd; /* Internal: descriptor for the outcome record, or -1. */
246 240
};
247 241
248 242
/* Global emulator options. */
249 243
static struct emulator_options g_opts = {
250 244
    .stack_guard              = true,
515 509
        " [-max-steps=n] [-memory-size=KB] [-data-size=KB]"
516 510
        " [-watch=addr] [-watch-size=bytes] [-watch-arm-pc=addr]"
517 511
        " [-watch-zero-only] [-watch-skip=n]"
518 512
        " [-watch-backtrace] [-watch-bt-depth=n]"
519 513
        " [-count-instructions] [-no-jit]"
514 +
        " [-profile=prefix] [-profile-trace=file] [-profile-function=name]"
520 515
        " [-irq=1..31] [-irq-at=tick]"
521 -
        " <file.bin> [program args...]\n",
516 +
        " <file.bin> [program args...]\n"
517 +
        "  -profile=prefix         Write prefix.folded and prefix.pcs.tsv.\n"
518 +
        "  -profile-trace=file     Write ordered instruction ranges.\n"
519 +
        "  -profile-function=name Write per-call counts to prefix.calls.tsv or "
520 +
        "stderr.\n",
522 521
        prog
523 522
    );
524 523
    return 1;
525 524
}
526 525
850 849
        if (strcmp(arg, "-count-instructions") == 0) {
851 850
            g_opts.count_instructions = true;
852 851
            argi++;
853 852
            continue;
854 853
        }
854 +
        if (strncmp(arg, "-profile=", 9) == 0 && arg[9]) {
855 +
            g_opts.profile_prefix = arg + 9;
856 +
            argi++;
857 +
            continue;
858 +
        }
859 +
        if (strncmp(arg, "-profile-trace=", 15) == 0 && arg[15]) {
860 +
            g_opts.profile_trace = arg + 15;
861 +
            argi++;
862 +
            continue;
863 +
        }
864 +
        if (strncmp(arg, "-profile-function=", 18) == 0 && arg[18]) {
865 +
            g_opts.profile_function = arg + 18;
866 +
            argi++;
867 +
            continue;
868 +
        }
855 869
        if (strncmp(arg, "-outcome-fd=", 12) == 0) {
856 870
            u32 fd;
857 871
            if (!parse_u32(arg + 12, "outcome descriptor", 10, &fd) ||
858 872
                fd > INT_MAX)
859 873
                return false;
887 901
            "hosted watchpoints and source debugger are unavailable in machine "
888 902
            "mode; use -trace\n"
889 903
        );
890 904
        return false;
891 905
    }
906 +
    if ((g_opts.profile_prefix || g_opts.profile_trace ||
907 +
         g_opts.profile_function) &&
908 +
        (!headless || g_opts.machine_mode)) {
909 +
        fprintf(stderr, "instruction profiling requires hosted -run mode\n");
910 +
        return false;
911 +
    }
892 912
    if (g_opts.watch_enabled && g_opts.watch_size == 0)
893 913
        g_opts.watch_size = 4;
894 914
    if (!validate_memory_layout())
895 915
        return false;
896 916
1361 1381
    }
1362 1382
    cpu->regs[A0] = env_addr;
1363 1383
    cpu->regs[A1] = env_addr;
1364 1384
}
1365 1385
1366 -
/* Load debug information from the .debug file. */
1367 -
static void debug_load(const char *program_path) {
1368 -
    char debugpath[PATH_MAX];
1369 -
    snprintf(debugpath, sizeof(debugpath), "%s.debug", program_path);
1370 -
1371 -
    FILE *file = fopen(debugpath, "rb");
1372 -
    if (!file)
1373 -
        return; /* Debug file is optional. */
1374 -
1375 -
    g_debug.capacity = 64;
1376 -
    g_debug.entries  = malloc(sizeof(struct debug_entry) * g_debug.capacity);
1377 -
    g_debug.count    = 0;
1378 -
1379 -
    if (!g_debug.entries) {
1380 -
        fclose(file);
1381 -
        return;
1382 -
    }
1383 -
    while (!feof(file)) {
1384 -
        struct debug_entry entry;
1385 -
1386 -
        if (fread(&entry.pc, sizeof(u32), 1, file) != 1)
1387 -
            break;
1388 -
        if (fread(&entry.offset, sizeof(u32), 1, file) != 1)
1389 -
            break;
1390 -
1391 -
        /* Read null-terminated file path. */
1392 -
        size_t i = 0;
1393 -
        int    c;
1394 -
        while (i < PATH_MAX - 1 && (c = fgetc(file)) != EOF && c != '\0') {
1395 -
            entry.file[i++] = (char)c;
1396 -
        }
1397 -
        entry.file[i] = '\0';
1398 -
1399 -
        if (c == EOF && i == 0)
1400 -
            break;
1401 -
1402 -
        /* Grow array if needed. */
1403 -
        if (g_debug.count >= g_debug.capacity) {
1404 -
            g_debug.capacity *= 2;
1405 -
            g_debug.entries   = realloc(
1406 -
                g_debug.entries, sizeof(struct debug_entry) * g_debug.capacity
1407 -
            );
1408 -
            if (!g_debug.entries) {
1409 -
                fclose(file);
1410 -
                return;
1411 -
            }
1412 -
        }
1413 -
        g_debug.entries[g_debug.count++] = entry;
1414 -
    }
1415 -
    fclose(file);
1416 -
}
1417 -
1418 -
/* Look up source location for a given PC. */
1419 -
static struct debug_entry *debug_lookup(u32 pc) {
1420 -
    struct debug_entry *best = NULL;
1421 -
1422 -
    for (size_t i = 0; i < g_debug.count; i++) {
1423 -
        if (g_debug.entries[i].pc == pc) {
1424 -
            return &g_debug.entries[i];
1425 -
        }
1426 -
        /* Track the closest entry at or before this PC. */
1427 -
        if (g_debug.entries[i].pc <= pc) {
1428 -
            best = &g_debug.entries[i];
1429 -
        }
1430 -
    }
1431 -
    return best;
1432 -
}
1433 -
1434 1386
/* Compute the line number from a file path and byte offset. */
1435 1387
static int line_from_offset(const char *filepath, u32 offset) {
1436 1388
    FILE *file = fopen(filepath, "r");
1437 1389
    if (!file)
1438 1390
        return 0;
1452 1404
1453 1405
/* Load the program image into memory. */
1454 1406
static void program_init(struct cpu *cpu, const char *filepath) {
1455 1407
    program_bytes = 0;
1456 1408
    data_bytes    = 0;
1457 -
    if (g_opts.debug_enabled)
1458 -
        debug_load(filepath);
1459 1409
1460 1410
    FILE *file = fopen(filepath, "rb");
1461 1411
    if (!file)
1462 1412
        bail("failed to open file '%s'", filepath);
1463 1413
    if (fseek(file, 0, SEEK_END) != 0) {
2137 2087
        if (funct12 == 0) {
2138 2088
            ecall_dispatch(cpu, executed_pc);
2139 2089
        } else if (funct12 == 1) {
2140 2090
            /* Look up source location for this EBREAK.  PC in the debug
2141 2091
             * file is relative to program start, so subtract base. */
2142 -
            u32                 relative_pc = executed_pc - program_base;
2143 -
            struct debug_entry *entry       = debug_lookup(relative_pc);
2092 +
            u32                       relative_pc = executed_pc - program_base;
2093 +
            const struct debug_entry *entry =
2094 +
                debug_map_lookup(&g_debug, relative_pc);
2144 2095
2145 2096
            printf("\n%sRuntime error (EBREAK)%s", COLOR_BOLD_RED, COLOR_RESET);
2146 2097
            if (entry) {
2147 2098
                u32 line = line_from_offset(entry->file, entry->offset);
2148 2099
                printf(
2531 2482
        host_report_outcome(g_opts.outcome_fd, &outcome);
2532 2483
    }
2533 2484
    return status;
2534 2485
}
2535 2486
2487 +
/* Run the interpreter and batch the PC of each dispatched instruction. */
2488 +
static void run_profiled_interpreter(
2489 +
    struct cpu     *cpu,
2490 +
    enum display    display,
2491 +
    u64             max_steps,
2492 +
    u64            *steps,
2493 +
    struct profile *profile,
2494 +
    u32            *ranges,
2495 +
    size_t          capacity
2496 +
) {
2497 +
    size_t count = 0;
2498 +
    while (cpu->running && *steps < max_steps) {
2499 +
        u32 pc = cpu->pc;
2500 +
        if (!cpu_out_of_bounds(cpu)) {
2501 +
            if (pc > PROFILE_PC_MASK)
2502 +
                ranges[count++] = PROFILE_PC_ESCAPE;
2503 +
            ranges[count++] = pc;
2504 +
            (*steps)++;
2505 +
        }
2506 +
        cpu_execute(cpu, display, true);
2507 +
        if (count >= capacity - 1) {
2508 +
            profile_record(profile, ranges, ranges + count);
2509 +
            count = 0;
2510 +
        }
2511 +
    }
2512 +
    if (count)
2513 +
        profile_record(profile, ranges, ranges + count);
2514 +
}
2515 +
2536 2516
int main(int argc, char *argv[]) {
2537 2517
    struct cpu        cpu;
2538 2518
    enum display      display = DISPLAY_DEC;
2539 2519
    struct cli_config cli     = { 0 };
2540 2520
2564 2544
            timed_out ? HOST_OUTCOME_STEPS : HOST_OUTCOME_EXITED,
2565 2545
            timed_out ? 0 : status,
2566 2546
            status
2567 2547
        );
2568 2548
    }
2549 +
    if ((g_opts.debug_enabled || g_opts.profile_prefix) &&
2550 +
        !debug_map_load(&g_debug, cli.program_path, program_bytes))
2551 +
        fprintf(stderr, "invalid source map '%s.debug'\n", cli.program_path);
2552 +
2569 2553
    int    prog_argc = argc - cli.arg_index;
2570 2554
    char **prog_argv = &argv[cli.arg_index];
2571 2555
    prepare_env(&cpu, prog_argc, prog_argv);
2572 2556
2573 2557
    if (headless) {
2574 -
        u64 max_steps = g_opts.headless_max_steps;
2575 -
        u64 steps     = 0;
2558 +
        u64             max_steps = g_opts.headless_max_steps;
2559 +
        u64             steps     = 0;
2560 +
        struct profile *profile   = NULL;
2561 +
        enum { PROFILE_BUFFER_COUNT = 16384 };
2562 +
        static u32 ranges[PROFILE_BUFFER_COUNT];
2563 +
        if (g_opts.profile_prefix || g_opts.profile_trace ||
2564 +
            g_opts.profile_function)
2565 +
            profile = profile_open(
2566 +
                cli.program_path,
2567 +
                memory,
2568 +
                program_base,
2569 +
                program_bytes,
2570 +
                &g_debug,
2571 +
                g_opts.profile_prefix,
2572 +
                g_opts.profile_trace,
2573 +
                g_opts.profile_function
2574 +
            );
2576 2575
2577 2576
        /* Try to initialise the JIT for headless mode.  Falls back to the
2578 2577
         * interpreter automatically when JIT is disabled, unavailable,
2579 2578
         * or when the code cache fills up. */
2580 2579
        static struct jit_state jit;
2583 2582
        if (!g_opts.jit_disabled && !g_opts.trace_enabled &&
2584 2583
            !g_opts.trace_print_instructions && !g_opts.watch_enabled) {
2585 2584
            use_jit = jit_init(&jit);
2586 2585
        }
2587 2586
2587 +
        bool interpret = !use_jit;
2588 2588
        if (use_jit) {
2589 2589
            jit.io.vector      = &cpu.vector;
2590 2590
            jit.io.memory_size = guest_sizes().memory;
2591 +
            if (profile)
2592 +
                jit.io.profile_next = ranges;
2591 2593
            /* ---- JIT execution loop ---- */
2592 2594
            u8 *patch = NULL; /* Direct jump to link to the next block. */
2593 2595
2594 2596
            while (cpu.running && steps < max_steps) {
2595 -
                struct jit_block *block = jit_get_block(
2596 -
                    &jit, cpu.pc, memory, program_base, program_bytes
2597 -
                );
2597 +
                u64               left = max_steps - steps;
2598 +
                struct jit_block *block =
2599 +
                    profile && left < JIT_MAX_BLOCK_INSNS
2600 +
                        ? NULL
2601 +
                        : jit_get_block(
2602 +
                              &jit, cpu.pc, memory, program_base, program_bytes
2603 +
                          );
2598 2604
                if (!block) {
2599 -
                    /* Cache full or compilation error -- fall back to
2600 -
                     * interpreter for remainder. */
2605 +
                    /* Interpret after a full cache or near the profile's
2606 +
                     * step limit, where a whole block might run past it. */
2601 2607
                    reservation_from_jit(&cpu, &jit.io);
2602 -
                    while (cpu.running && steps++ < max_steps) {
2603 -
                        cpu_execute(&cpu, display, true);
2604 -
                    }
2608 +
                    interpret = true;
2605 2609
                    break;
2606 2610
                }
2607 2611
                if (patch)
2608 2612
                    jit_patch_chain(patch, block);
2609 2613
                jit_cache_jump(&jit, block);
2610 2614
2611 2615
                /* Generated code charges each block's instructions against
2612 2616
                 * the budget, so `steps` advances by what it consumed. */
2613 -
                u64 left   = max_steps - steps;
2614 -
                i64 budget = left > INT64_MAX ? INT64_MAX : (i64)left;
2617 +
                u64 limit = left;
2618 +
                if (profile)
2619 +
                    limit -= JIT_MAX_BLOCK_INSNS - 1;
2620 +
                i64 budget = limit > INT64_MAX ? INT64_MAX : (i64)limit;
2621 +
                /* Each range contains at least one instruction. Leave space
2622 +
                 * for the final block, which can exceed the entry budget. */
2623 +
                if (profile &&
2624 +
                    budget > PROFILE_BUFFER_COUNT - JIT_MAX_BLOCK_INSNS)
2625 +
                    budget = PROFILE_BUFFER_COUNT - JIT_MAX_BLOCK_INSNS;
2615 2626
                int exit_reason =
2616 2627
                    jit_run(&jit, block, cpu.regs, memory, budget);
2617 2628
                steps  += (u64)budget - (u64)jit.io.budget;
2618 2629
                cpu.pc  = jit.io.pc;
2619 2630
                patch   = NULL;
2620 2631
2632 +
                if (profile && jit.io.profile_next != ranges) {
2633 +
                    profile_record(profile, ranges, jit.io.profile_next);
2634 +
                    jit.io.profile_next = ranges;
2635 +
                }
2636 +
2621 2637
                switch (exit_reason) {
2622 2638
                case JIT_EXIT_BRANCH:
2623 2639
                    break;
2624 2640
2625 2641
                case JIT_EXIT_CHAIN:
2640 2656
                    reservation_to_jit(&cpu, &jit.io);
2641 2657
                    break;
2642 2658
                }
2643 2659
            }
2644 2660
            jit_destroy(&jit);
2645 -
        } else {
2661 +
        }
2662 +
        if (interpret && profile) {
2663 +
            run_profiled_interpreter(
2664 +
                &cpu,
2665 +
                display,
2666 +
                max_steps,
2667 +
                &steps,
2668 +
                profile,
2669 +
                ranges,
2670 +
                PROFILE_BUFFER_COUNT
2671 +
            );
2672 +
        } else if (interpret) {
2646 2673
            /* ---- Interpreter-only loop ---- */
2647 2674
            while (cpu.running && steps++ < max_steps) {
2648 2675
                cpu_execute(&cpu, display, true);
2649 2676
            }
2650 2677
        }
2651 2678
2679 +
        if (!profile_close(
2680 +
                profile,
2681 +
                cpu.running ? cpu.pc : 0,
2682 +
                cpu.running || (!cpu.regs[RA] && !cpu.faulted && !cpu.ebreak)
2683 +
            )) {
2684 +
            fprintf(stderr, "cannot write instruction profile\n");
2685 +
            return finish(HOST_OUTCOME_FAULT, 0, 1);
2686 +
        }
2687 +
        debug_map_free(&g_debug);
2652 2688
        if (cpu.running) {
2653 2689
            fprintf(
2654 2690
                stderr,
2655 2691
                "program did not terminate within %zu steps\n",
2656 2692
                (size_t)max_steps
jit.c +54 -5
34 34
#include <string.h>
35 35
#include <sys/mman.h>
36 36
37 37
#include "bitmanip.h"
38 38
#include "jit.h"
39 +
#include "profile.h"
39 40
#include "riscv.h"
40 41
#include "types.h"
41 42
#include "vector.h"
42 43
43 44
/* ---------- x86-64 code emitter helpers --------------------------------- */
400 401
    emit_u8(e, 0xC7);
401 402
    emit_u8(e, modrm(0, 0, HIO));
402 403
    emit_u32(e, pc);
403 404
}
404 405
406 +
#define IO_PROFILE_NEXT ((u8)offsetof(struct jit_io, profile_next))
407 +
408 +
/* Record the executed prefix of the block. A block can follow several
409 +
 * guest jumps, so its prefix can span several disjoint PC ranges. */
410 +
static void emit_profile(struct emitter *e, u32 insns) {
411 +
    if (!e->jit->io.profile_next || !insns)
412 +
        return;
413 +
414 +
    /* mov rcx, [r14 + IO_PROFILE_NEXT] */
415 +
    emit_u8(e, 0x49);
416 +
    emit_u8(e, 0x8B);
417 +
    emit_u8(e, modrm(1, X_RCX, HIO));
418 +
    emit_u8(e, IO_PROFILE_NEXT);
419 +
    u8 offset = 0;
420 +
    for (u32 i = 0; insns; i++) {
421 +
        u32 pc    = e->run_start[i];
422 +
        u32 count = insns;
423 +
        if (i + 1 < e->runs) {
424 +
            u32 length = (e->run_end[i] - pc) / INSTR_SIZE;
425 +
            if (length < count)
426 +
                count = length;
427 +
        }
428 +
        /* mov dword [rcx + offset], packed range */
429 +
        emit_u8(e, 0xC7);
430 +
        emit_u8(e, modrm(1, 0, X_RCX));
431 +
        emit_u8(e, offset);
432 +
        emit_u32(e, ((count - 1) << PROFILE_PC_BITS) | pc);
433 +
        insns  -= count;
434 +
        offset += sizeof(u32);
435 +
    }
436 +
    /* add rcx, offset; mov [r14 + IO_PROFILE_NEXT], rcx */
437 +
    emit_u8(e, 0x48);
438 +
    emit_u8(e, 0x83);
439 +
    emit_u8(e, modrm(3, 0, X_RCX));
440 +
    emit_u8(e, offset);
441 +
    emit_u8(e, 0x49);
442 +
    emit_u8(e, 0x89);
443 +
    emit_u8(e, modrm(1, X_RCX, HIO));
444 +
    emit_u8(e, IO_PROFILE_NEXT);
445 +
}
446 +
405 447
/* Charge the instructions on this path and set the budget flags. */
406 448
static void emit_charge(struct emitter *e, u32 insns) {
407 449
    if (insns == 0)
408 450
        return;
409 451
    bool small = insns <= INT8_MAX;
426 468
427 469
/* Store next-PC to *r14 and leave the cache with `reason`. */
428 470
static void emit_block_exit(
429 471
    struct emitter *e, enum jit_exit reason, u32 next_pc
430 472
) {
473 +
    emit_profile(e, e->insns);
431 474
    emit_charge(e, e->insns);
432 475
    emit_store_pc_imm(e, next_pc);
433 476
    emit_exit(e, (u32)reason);
434 477
}
435 478
461 504
/* Charge the block and jump to `target` with all held registers loaded. */
462 505
static void emit_chain_exit(struct emitter *e, u32 target) {
463 506
    bool spilled = e->spilled;
464 507
    if (spilled)
465 508
        emit_reload(e);
509 +
    emit_profile(e, e->insns);
466 510
    emit_charge(e, e->insns);
467 511
    emit_link(e, target);
468 512
    e->spilled = spilled;
469 513
}
470 514
501 545
    emit_u8(e, 0x86);
502 546
    emit_u32(e, 0);
503 547
504 548
    emit_u8(e, 0x68); /* push guest link */
505 549
    emit_u32(e, next);
550 +
    emit_profile(e, e->insns);
506 551
    emit_charge(e, e->insns);
507 552
    u32 call = e->pos;
508 553
    emit_u8(e, 0xE8);
509 554
    emit_u32(e, 0);
510 555
534 579
 */
535 580
static void emit_indirect_jump(struct emitter *e) {
536 581
    if (e->spilled)
537 582
        emit_reload(e);
538 583
584 +
    emit_profile(e, e->insns);
585 +
539 586
    /* mov ecx, eax; and ecx, mask << 2; shl ecx, 2 -- byte offset of the
540 587
     * entry, ((pc >> 2) & mask) * sizeof(struct jit_jump_entry). */
541 588
    emit_u8(e, 0x89);
542 589
    emit_u8(e, modrm(3, X_RAX, X_RCX));
543 590
    emit_u8(e, 0x81);
1926 1973
        bad[i] = emit_jne_placeholder(e);
1927 1974
    }
1928 1975
    u32 ok = emit_jmp_placeholder(e);
1929 1976
    for (u32 i = 0; i < 3; i++)
1930 1977
        patch_jcc(e, bad[i], e->pos);
1978 +
    emit_profile(e, 1);
1931 1979
    emit_charge(e, 1);
1932 1980
    emit_store_pc_imm(e, pc);
1933 1981
    emit_exit(e, JIT_EXIT_FAULT);
1934 1982
    patch_jmp(e, ok, e->pos);
1935 1983
}
2008 2056
    emit_u8(e, modrm(1, X_RAX, X_RSP));
2009 2057
    emit_u8(e, sib(0, X_RSP, X_RSP));
2010 2058
    emit_u8(e, 8);
2011 2059
    u32 mismatch = emit_jnz_placeholder(e);
2012 2060
    /* The budget was positive at entry, so this subtraction clears OF. */
2061 +
    emit_profile(e, e->insns);
2013 2062
    emit_charge(e, e->insns);
2014 2063
    emit_native_ret(e);
2015 2064
    patch_jcc(e, mismatch, e->pos);
2016 2065
2017 2066
    /* test rax, rax */
2795 2844
    struct emitter *em, u32 guest_pc, u8 *mem, u32 prog_base, u32 prog_bytes
2796 2845
) {
2797 2846
    /* if (budget <= 0) goto .exhausted */
2798 2847
    u32 jle_pos = emit_jle_placeholder(em);
2799 2848
2800 -
    if (em->guard)
2801 -
        emit_vector_guard(em, guest_pc);
2802 -
2803 2849
    u32 pc           = guest_pc;
2804 2850
    u32 insn_count   = 0;
2805 2851
    em->run_start[0] = guest_pc;
2806 2852
    em->runs         = 1;
2807 -
    u32 prog_end_pc  = prog_base + prog_bytes;
2853 +
    if (em->guard)
2854 +
        emit_vector_guard(em, guest_pc);
2855 +
2856 +
    u32 prog_end_pc = prog_base + prog_bytes;
2808 2857
2809 2858
    while (insn_count < JIT_MAX_BLOCK_INSNS) {
2810 2859
        if (pc < prog_base || pc >= prog_end_pc) {
2811 2860
            emit_block_exit(em, JIT_EXIT_FAULT, pc);
2812 2861
            break;
2842 2891
2843 2892
    /* The side exits and the budget exit start with held registers. */
2844 2893
    emit_side_exits(em);
2845 2894
    em->spilled = false;
2846 2895
2847 -
    /* .exhausted: out of budget, leave before running anything. */
2896 +
    /* .exhausted: leave before executing any guest instructions. */
2848 2897
    patch_jcc(em, jle_pos, em->pos);
2849 2898
    emit_store_pc_imm(em, guest_pc);
2850 2899
    emit_exit(em, JIT_EXIT_BRANCH);
2851 2900
}
2852 2901
jit.h +3 -2
81 81
    u64                  memory_size; /* Accessible hosted memory bytes. */
82 82
    /* LR reservation: the address in the low word and the access width in
83 83
     * the high word, or zero when none is held. */
84 84
    u64 reservation;
85 85
    /* Bounds of the host stack frames for translated calls. */
86 -
    u64 stack_base;
87 -
    u64 stack_floor;
86 +
    u64  stack_base;
87 +
    u64  stack_floor;
88 +
    u32 *profile_next; /* Next free range, or NULL. */
88 89
};
89 90
90 91
/* Reservation value of an LR of `size` bytes at `address`. */
91 92
static inline u64 jit_reservation(u32 address, u32 size) {
92 93
    return (u64)size << 32 | address;
profile.c added +505 -0
1 +
/* Deterministic hosted instruction profiles. */
2 +
#define _POSIX_C_SOURCE 200809L
3 +
4 +
#include <fcntl.h>
5 +
#include <stdio.h>
6 +
#include <stdlib.h>
7 +
#include <string.h>
8 +
#include <unistd.h>
9 +
10 +
#include <blake3.h>
11 +
12 +
#include "debug_map.h"
13 +
#include "hosted.h"
14 +
#include "io.h"
15 +
#include "profile.h"
16 +
17 +
/* A name and its byte offset from the start of the image's code. */
18 +
struct symbol {
19 +
    u32   offset;
20 +
    char *name;
21 +
};
22 +
23 +
/* One unique call stack, stored with its parent stack. Index zero is empty. */
24 +
struct stack_node {
25 +
    u32 parent;
26 +
    u32 pc;
27 +
    u64 self;
28 +
};
29 +
30 +
/* One active invocation. */
31 +
struct frame {
32 +
    u32  node;
33 +
    u32  pc;
34 +
    u32  link; /* Guest return address. Tail calls share their caller's link. */
35 +
    u64  start;
36 +
    u64  self;
37 +
    u64  invocation; /* Sequence number for a selected function, or zero. */
38 +
    bool tail;       /* The frame below shares this frame's return. */
39 +
};
40 +
41 +
struct profile {
42 +
    const u8               *memory;
43 +
    u32                     base;
44 +
    u32                     bytes;
45 +
    const struct debug_map *debug;
46 +
    FILE                   *trace;
47 +
    FILE                   *folded;
48 +
    FILE                   *pcs;
49 +
    FILE                   *calls;
50 +
    bool                    failed;
51 +
    bool                    track_calls;
52 +
    u32                     function_pc;
53 +
    u64                     invocations;
54 +
    struct symbol          *symbols;
55 +
    size_t                  symbol_count;
56 +
    /* Index of the containing symbol plus one, or zero for an unknown PC. */
57 +
    u32 *symbol_index;
58 +
    /* Range updates give per-PC counts with two additions per recorded range.
59 +
     */
60 +
    u64               *pc_delta;
61 +
    struct stack_node *nodes;
62 +
    size_t             node_count;
63 +
    size_t             node_capacity;
64 +
    u32               *node_hash;
65 +
    size_t             hash_capacity;
66 +
    struct frame      *frames;
67 +
    size_t             depth;
68 +
    size_t             frame_capacity;
69 +
    u64                total;
70 +
    u32                last_pc;
71 +
};
72 +
73 +
static void *resize(void *data, size_t count, size_t size) {
74 +
    void *result = realloc(data, count * size);
75 +
    if (!result)
76 +
        bail("cannot allocate instruction profile");
77 +
    return result;
78 +
}
79 +
80 +
static FILE *open_output(const char *prefix, const char *suffix) {
81 +
    size_t size = strlen(prefix) + strlen(suffix) + 1;
82 +
    char  *path = resize(NULL, size, 1);
83 +
    snprintf(path, size, "%s%s", prefix, suffix);
84 +
    int   fd   = open(path, O_WRONLY | O_CREAT | O_EXCL | O_CLOEXEC, 0666);
85 +
    FILE *file = fd < 0 ? NULL : fdopen(fd, "wb");
86 +
    if (!file)
87 +
        bail("cannot create profile output '%s'", path);
88 +
    free(path);
89 +
    return file;
90 +
}
91 +
92 +
static int compare_symbols(const void *a, const void *b) {
93 +
    const struct symbol *left = a, *right = b;
94 +
    if (left->offset != right->offset)
95 +
        return left->offset < right->offset ? -1 : 1;
96 +
    return strcmp(left->name, right->name);
97 +
}
98 +
99 +
static void load_symbols(struct profile *p, const char *program) {
100 +
    size_t size = 0;
101 +
    u8    *data = debug_read_sidecar(program, ".symbols", &size);
102 +
    if (!data)
103 +
        return;
104 +
105 +
    /* Magic and text digest, then (byte offset, name length) and name bytes. */
106 +
    if (size < 40 || memcmp(data, "RADSYM01", 8))
107 +
        bail("invalid symbol map for '%s'", program);
108 +
    blake3_hasher hasher;
109 +
    u8            digest[BLAKE3_OUT_LEN];
110 +
    blake3_hasher_init(&hasher);
111 +
    blake3_hasher_update(&hasher, p->memory + p->base, p->bytes);
112 +
    blake3_hasher_finalize(&hasher, digest, sizeof(digest));
113 +
    if (memcmp(digest, data + 8, sizeof(digest))) {
114 +
        fprintf(stderr, "symbol map does not match '%s'\n", program);
115 +
        free(data);
116 +
        return;
117 +
    }
118 +
    size_t capacity = 0;
119 +
    for (size_t pos = 40; pos < size;) {
120 +
        if (size - pos < 8)
121 +
            bail("truncated symbol map for '%s'", program);
122 +
        u32 offset  = decode_u32_le(data + pos);
123 +
        u32 len     = decode_u32_le(data + pos + 4);
124 +
        pos        += 8;
125 +
        if (offset > p->bytes || offset % INSTR_SIZE || !len ||
126 +
            len > size - pos || memchr(data + pos, 0, len))
127 +
            bail("invalid symbol in map for '%s'", program);
128 +
        /* A label at the end of the text has no instructions. */
129 +
        if (offset != p->bytes) {
130 +
            if (p->symbol_count == capacity) {
131 +
                capacity   = capacity ? 2 * capacity : 64;
132 +
                p->symbols = resize(p->symbols, capacity, sizeof(*p->symbols));
133 +
            }
134 +
            char *name = resize(NULL, (size_t)len + 1, 1);
135 +
            memcpy(name, data + pos, len);
136 +
            name[len]                     = 0;
137 +
            p->symbols[p->symbol_count++] = (struct symbol){ offset, name };
138 +
        }
139 +
        pos += len;
140 +
    }
141 +
    free(data);
142 +
    if (!p->symbol_count)
143 +
        return;
144 +
    qsort(p->symbols, p->symbol_count, sizeof(*p->symbols), compare_symbols);
145 +
146 +
    size_t words    = p->bytes / INSTR_SIZE;
147 +
    p->symbol_index = calloc(words, sizeof(*p->symbol_index));
148 +
    if (!p->symbol_index)
149 +
        bail("cannot allocate profile symbol index");
150 +
    size_t symbol = 0;
151 +
    for (size_t i = 0; i < words; i++) {
152 +
        while (symbol < p->symbol_count &&
153 +
               p->symbols[symbol].offset == i * INSTR_SIZE)
154 +
            symbol++;
155 +
        p->symbol_index[i] = (u32)symbol;
156 +
    }
157 +
}
158 +
159 +
static const struct symbol *symbol_at(const struct profile *p, u32 pc) {
160 +
    if (!p->symbol_index || pc - p->base >= p->bytes)
161 +
        return NULL;
162 +
    u32 index = p->symbol_index[(pc - p->base) / INSTR_SIZE];
163 +
    return index ? &p->symbols[index - 1] : NULL;
164 +
}
165 +
166 +
/* Render a field that is also safe as a folded-stack frame. */
167 +
static void field(FILE *file, const char *str) {
168 +
    size_t n = strcspn(str, ";\t\r\n");
169 +
    if (!str[n]) {
170 +
        fputs(str, file);
171 +
        return;
172 +
    }
173 +
    for (; *str; str++)
174 +
        fputc(strchr(";\t\r\n", *str) ? '_' : (unsigned char)*str, file);
175 +
}
176 +
177 +
static void frame_name(FILE *file, const struct profile *p, u32 pc) {
178 +
    const struct symbol *sym = symbol_at(p, pc);
179 +
    if (sym && sym->offset == pc - p->base) {
180 +
        field(file, sym->name);
181 +
        return;
182 +
    }
183 +
    fprintf(file, "0x%x", pc);
184 +
    if (pc - p->base < p->bytes) {
185 +
        const struct debug_entry *loc =
186 +
            debug_map_lookup(p->debug, pc - p->base);
187 +
        if (loc) {
188 +
            fputc('@', file);
189 +
            field(file, loc->file);
190 +
            fprintf(file, ":%u", loc->offset);
191 +
        }
192 +
    }
193 +
}
194 +
195 +
static size_t node_slot(const struct profile *p, u32 parent, u32 pc) {
196 +
    u64 key      = ((u64)parent << 32) | pc;
197 +
    key         ^= key >> 33;
198 +
    key         *= 0xff51afd7ed558ccduLL;
199 +
    key         ^= key >> 33;
200 +
    size_t slot  = (size_t)key & (p->hash_capacity - 1);
201 +
    while (p->node_hash[slot]) {
202 +
        const struct stack_node *node = &p->nodes[p->node_hash[slot]];
203 +
        if (node->parent == parent && node->pc == pc)
204 +
            break;
205 +
        slot = (slot + 1) & (p->hash_capacity - 1);
206 +
    }
207 +
    return slot;
208 +
}
209 +
210 +
static u32 stack_node(struct profile *p, u32 parent, u32 pc) {
211 +
    if (p->node_count * 2 >= p->hash_capacity) {
212 +
        free(p->node_hash);
213 +
        p->hash_capacity = p->hash_capacity ? p->hash_capacity * 2 : 128;
214 +
        p->node_hash     = calloc(p->hash_capacity, sizeof(*p->node_hash));
215 +
        if (!p->node_hash)
216 +
            bail("cannot allocate profile stack index");
217 +
        for (u32 i = 1; i < p->node_count; i++)
218 +
            p->node_hash[node_slot(p, p->nodes[i].parent, p->nodes[i].pc)] = i;
219 +
    }
220 +
    size_t slot = node_slot(p, parent, pc);
221 +
    if (p->node_hash[slot])
222 +
        return p->node_hash[slot];
223 +
    if (p->node_count >= p->node_capacity) {
224 +
        p->node_capacity = p->node_capacity ? p->node_capacity * 2 : 64;
225 +
        p->nodes = resize(p->nodes, p->node_capacity, sizeof(*p->nodes));
226 +
    }
227 +
    u32 index          = (u32)p->node_count++;
228 +
    p->nodes[index]    = (struct stack_node){ .parent = parent, .pc = pc };
229 +
    p->node_hash[slot] = index;
230 +
    return index;
231 +
}
232 +
233 +
static void enter(struct profile *p, u32 pc, u32 link, bool tail) {
234 +
    if (p->depth == p->frame_capacity) {
235 +
        p->frame_capacity = p->frame_capacity ? p->frame_capacity * 2 : 32;
236 +
        p->frames = resize(p->frames, p->frame_capacity, sizeof(*p->frames));
237 +
    }
238 +
    u32           parent = p->depth ? p->frames[p->depth - 1].node : 0;
239 +
    struct frame *frame  = &p->frames[p->depth++];
240 +
    *frame               = (struct frame){
241 +
        .node  = p->folded ? stack_node(p, parent, pc) : 0,
242 +
        .pc    = pc,
243 +
        .link  = link,
244 +
        .start = p->total,
245 +
        .tail  = tail,
246 +
    };
247 +
    if (p->track_calls && pc == p->function_pc)
248 +
        frame->invocation = ++p->invocations;
249 +
}
250 +
251 +
static void leave(struct profile *p, bool returned) {
252 +
    const struct frame *f = &p->frames[--p->depth];
253 +
    if (f->invocation)
254 +
        fprintf(
255 +
            p->calls,
256 +
            "%llu\t%llu\t%llu\t%s\n",
257 +
            (unsigned long long)f->invocation,
258 +
            (unsigned long long)f->self,
259 +
            (unsigned long long)(p->total - f->start),
260 +
            returned ? "returned" : "stopped"
261 +
        );
262 +
}
263 +
264 +
static bool is_link(u32 reg) {
265 +
    return reg == RA || reg == T0;
266 +
}
267 +
268 +
/* Complete the invocation whose link is the actual return target.
269 +
 * A transfer to an outer frame stops any intervening active calls. */
270 +
static bool return_to(struct profile *p, u32 target) {
271 +
    for (size_t i = p->depth; i; i--) {
272 +
        if (p->frames[i - 1].link != target)
273 +
            continue;
274 +
        while (p->depth > i)
275 +
            leave(p, false);
276 +
        bool tail;
277 +
        do {
278 +
            tail = p->frames[p->depth - 1].tail;
279 +
            leave(p, true);
280 +
        } while (tail);
281 +
        return true;
282 +
    }
283 +
    return false;
284 +
}
285 +
286 +
static bool is_return(instr_t ins) {
287 +
    return ins.r.opcode == OP_JALR && is_link(ins.i.rs1) &&
288 +
           (!is_link(ins.i.rd) || ins.i.rd != ins.i.rs1);
289 +
}
290 +
291 +
/* Apply the transfer at the end of the previous range with its actual target.
292 +
 */
293 +
static void transfer(struct profile *p, u32 target) {
294 +
    if (!p->depth) {
295 +
        enter(p, target, 0, false);
296 +
        return;
297 +
    }
298 +
    u32 prev = p->last_pc;
299 +
    if (prev - p->base >= p->bytes)
300 +
        return;
301 +
    instr_t ins = { .raw = decode_u32_le(p->memory + prev) };
302 +
    if (ins.r.opcode != OP_JAL && ins.r.opcode != OP_JALR)
303 +
        return;
304 +
    u32 rd = ins.r.rd;
305 +
    if (is_return(ins) && return_to(p, target) && !is_link(rd)) {
306 +
        if (!p->depth)
307 +
            enter(p, target, 0, false);
308 +
        return;
309 +
    }
310 +
    if (is_link(rd)) {
311 +
        enter(p, target, prev + INSTR_SIZE, false);
312 +
        return;
313 +
    }
314 +
315 +
    const struct symbol *sym   = symbol_at(p, target);
316 +
    struct frame        *frame = p->depth ? &p->frames[p->depth - 1] : NULL;
317 +
    if (rd == ZERO && sym && sym->offset == target - p->base && frame &&
318 +
        frame->pc != target)
319 +
        enter(p, target, frame->link, true);
320 +
}
321 +
322 +
struct profile *profile_open(
323 +
    const char             *program,
324 +
    const u8               *memory,
325 +
    u32                     base,
326 +
    u32                     bytes,
327 +
    const struct debug_map *debug,
328 +
    const char             *prefix,
329 +
    const char             *trace,
330 +
    const char             *function
331 +
) {
332 +
    struct profile *p = calloc(1, sizeof(*p));
333 +
    if (!p)
334 +
        bail("cannot allocate instruction profile");
335 +
    p->memory     = memory;
336 +
    p->base       = base;
337 +
    p->bytes      = bytes;
338 +
    p->debug      = debug;
339 +
    p->node_count = 1; /* Reserve the empty stack. */
340 +
    if (prefix || function)
341 +
        load_symbols(p, program);
342 +
    if (function) {
343 +
        for (size_t i = 0; i < p->symbol_count; i++) {
344 +
            if (!strcmp(function, p->symbols[i].name)) {
345 +
                p->track_calls = true;
346 +
                p->function_pc = base + p->symbols[i].offset;
347 +
                break;
348 +
            }
349 +
        }
350 +
        if (!p->track_calls)
351 +
            bail(
352 +
                "profile function '%s' is absent from '%s.symbols'",
353 +
                function,
354 +
                program
355 +
            );
356 +
        if (prefix) {
357 +
            p->calls = open_output(prefix, ".calls.tsv");
358 +
        } else {
359 +
            int fd = fcntl(STDERR_FILENO, F_DUPFD_CLOEXEC, 3);
360 +
            if (fd < 0 || !(p->calls = fdopen(fd, "w")))
361 +
                bail("cannot open the call report stream");
362 +
        }
363 +
        fputs("call\tself\tinclusive\tstatus\n", p->calls);
364 +
    }
365 +
    if (prefix) {
366 +
        p->folded = open_output(prefix, ".folded");
367 +
        p->pcs    = open_output(prefix, ".pcs.tsv");
368 +
        p->pc_delta =
369 +
            calloc((size_t)bytes / INSTR_SIZE + 1, sizeof(*p->pc_delta));
370 +
        if (!p->pc_delta)
371 +
            bail("cannot allocate profile PC counters");
372 +
    }
373 +
    if (trace) {
374 +
        p->trace = open_output(trace, "");
375 +
        /* RVTRACE1, code base and size, then packed range words.
376 +
         * All integer fields are little-endian. */
377 +
        u8 header[16] = "RVTRACE1";
378 +
        encode_le(header + 8, base, 4);
379 +
        encode_le(header + 12, bytes, 4);
380 +
        p->failed |=
381 +
            fwrite(header, 1, sizeof(header), p->trace) != sizeof(header);
382 +
    }
383 +
    return p;
384 +
}
385 +
386 +
void profile_record(struct profile *p, const u32 *ranges, const u32 *end) {
387 +
    if (p->trace && !p->failed) {
388 +
        const u16 little_endian = 1;
389 +
        if (*(const u8 *)&little_endian) {
390 +
            size_t n   = (size_t)(end - ranges);
391 +
            p->failed |= fwrite(ranges, sizeof(*ranges), n, p->trace) != n;
392 +
        } else {
393 +
            for (const u32 *r = ranges; r < end; r++) {
394 +
                u8 bytes[4];
395 +
                encode_le(bytes, *r, sizeof(bytes));
396 +
                p->failed |=
397 +
                    fwrite(bytes, 1, sizeof(bytes), p->trace) != sizeof(bytes);
398 +
            }
399 +
        }
400 +
    }
401 +
    if (!p->folded && !p->calls)
402 +
        return;
403 +
    for (const u32 *r = ranges; r < end;) {
404 +
        u32 word  = *r++;
405 +
        u32 count = (word >> PROFILE_PC_BITS) + 1;
406 +
        u32 pc    = word & PROFILE_PC_MASK;
407 +
        if (word == PROFILE_PC_ESCAPE) {
408 +
            pc    = *r++;
409 +
            count = 1;
410 +
        }
411 +
        u32 offset = pc - p->base;
412 +
        if (p->pc_delta && offset < p->bytes) {
413 +
            u32 index = offset / INSTR_SIZE;
414 +
            u32 words = p->bytes / INSTR_SIZE - index;
415 +
            p->pc_delta[index]++;
416 +
            p->pc_delta[index + (count < words ? count : words)]--;
417 +
        }
418 +
        transfer(p, pc);
419 +
        struct frame *f = &p->frames[p->depth - 1];
420 +
        if (p->folded)
421 +
            p->nodes[f->node].self += count;
422 +
        f->self    += count;
423 +
        p->total   += count;
424 +
        p->last_pc  = pc + (count - 1) * INSTR_SIZE;
425 +
    }
426 +
}
427 +
428 +
bool profile_close(struct profile *p, u32 next_pc, bool continued) {
429 +
    if (!p)
430 +
        return true;
431 +
    if (continued && p->depth && p->last_pc - p->base < p->bytes) {
432 +
        instr_t ins = { .raw = decode_u32_le(p->memory + p->last_pc) };
433 +
        if (is_return(ins))
434 +
            return_to(p, next_pc);
435 +
    }
436 +
    while (p->depth)
437 +
        leave(p, false);
438 +
439 +
    if (p->folded) {
440 +
        u32 *path = resize(NULL, p->node_count, sizeof(*path));
441 +
        for (u32 i = 1; i < p->node_count; i++) {
442 +
            if (!p->nodes[i].self)
443 +
                continue;
444 +
            size_t depth = 0;
445 +
            for (u32 node = i; node; node = p->nodes[node].parent)
446 +
                path[depth++] = p->nodes[node].pc;
447 +
            while (depth) {
448 +
                frame_name(p->folded, p, path[--depth]);
449 +
                if (depth)
450 +
                    fputc(';', p->folded);
451 +
            }
452 +
            fprintf(p->folded, " %llu\n", (unsigned long long)p->nodes[i].self);
453 +
        }
454 +
        free(path);
455 +
456 +
        fputs("pc\tinstructions\tfunction\tsource\tbyte_offset\n", p->pcs);
457 +
        u64 count = 0;
458 +
        for (u32 i = 0; i < p->bytes / INSTR_SIZE; i++) {
459 +
            count += p->pc_delta[i];
460 +
            if (!count)
461 +
                continue;
462 +
            u32                       offset = i * INSTR_SIZE;
463 +
            const struct symbol      *sym    = symbol_at(p, p->base + offset);
464 +
            const struct debug_entry *loc = debug_map_lookup(p->debug, offset);
465 +
            if (sym && loc && loc->pc < sym->offset)
466 +
                loc = NULL;
467 +
            fprintf(
468 +
                p->pcs,
469 +
                "0x%x\t%llu\t",
470 +
                p->base + offset,
471 +
                (unsigned long long)count
472 +
            );
473 +
            if (sym)
474 +
                field(p->pcs, sym->name);
475 +
            if (loc) {
476 +
                fputc('\t', p->pcs);
477 +
                field(p->pcs, loc->file);
478 +
                fprintf(p->pcs, "\t%u", loc->offset);
479 +
            } else {
480 +
                fputs("\t\t", p->pcs);
481 +
            }
482 +
            fputc('\n', p->pcs);
483 +
        }
484 +
    }
485 +
486 +
    FILE *outputs[] = { p->folded, p->pcs, p->trace, p->calls };
487 +
    for (size_t i = 0; i < sizeof(outputs) / sizeof(*outputs); i++) {
488 +
        FILE *file = outputs[i];
489 +
        if (file) {
490 +
            p->failed |= ferror(file) != 0;
491 +
            p->failed |= fclose(file) != 0;
492 +
        }
493 +
    }
494 +
    bool ok = !p->failed;
495 +
    for (size_t i = 0; i < p->symbol_count; i++)
496 +
        free(p->symbols[i].name);
497 +
    free(p->symbols);
498 +
    free(p->symbol_index);
499 +
    free(p->pc_delta);
500 +
    free(p->nodes);
501 +
    free(p->node_hash);
502 +
    free(p->frames);
503 +
    free(p);
504 +
    return ok;
505 +
}
profile.h added +41 -0
1 +
#ifndef PROFILE_H
2 +
#define PROFILE_H
3 +
4 +
#include "types.h"
5 +
6 +
struct debug_map;
7 +
8 +
/* A range word stores the absolute PC in its low 24 bits and the
9 +
 * instruction count minus one in its high byte. Hosted text ends below
10 +
 * 16 MiB. The interpreter uses an escape followed by a full PC for a
11 +
 * single instruction outside this range. */
12 +
#define PROFILE_PC_BITS   24
13 +
#define PROFILE_PC_MASK   ((1u << PROFILE_PC_BITS) - 1)
14 +
#define PROFILE_PC_ESCAPE U32_MAX
15 +
16 +
/* State of one hosted execution profile. */
17 +
struct profile;
18 +
19 +
/* Start an instruction profile. Write folded stacks and PC counts if prefix
20 +
 * is set. Write ordered PC ranges if trace is set. Report each invocation
21 +
 * of function if set. The image and debug map stay valid until close. */
22 +
struct profile *profile_open(
23 +
    const char             *program,
24 +
    const u8               *memory,
25 +
    u32                     base,
26 +
    u32                     bytes,
27 +
    const struct debug_map *debug,
28 +
    const char             *prefix,
29 +
    const char             *trace,
30 +
    const char             *function
31 +
);
32 +
33 +
/* Read ranges in execution order. Keep the last range's transfer pending
34 +
 * until the next PC is known. */
35 +
void profile_record(struct profile *profile, const u32 *ranges, const u32 *end);
36 +
37 +
/* Write reports and free the profile. If the final instruction had a known
38 +
 * continuation, next_pc is its target, including zero for a hosted return. */
39 +
bool profile_close(struct profile *profile, u32 next_pc, bool continued);
40 +
41 +
#endif
test/jit_vector.c +14 -5
2 2
#include <assert.h>
3 3
#include <stdio.h>
4 4
#include <stdlib.h>
5 5
6 6
#include "jit.h"
7 +
#include "profile.h"
7 8
#include "vector.h"
8 9
9 10
/* Test code lies outside the accessible data region. */
10 11
#define DATA 4096
11 12
#define CODE 8192
85 86
    x[12] = y[12] = 0xa5;
86 87
    memcpy(actual + CODE, code, count * 4);
87 88
    u32 ret = 0x00008067;
88 89
    memcpy(actual + CODE + count * 4, &ret, 4);
89 90
    assert(jit_init(&jit));
90 -
    jit.io.vector      = &a;
91 -
    jit.io.memory_size = DATA;
92 -
    u32  pc            = CODE;
93 -
    i64  budget        = 100000;
94 -
    bool failed        = false;
91 +
    u32 ranges[JIT_MAX_BLOCK_INSNS + 2];
92 +
    jit.io.profile_next = ranges;
93 +
    jit.io.vector       = &a;
94 +
    jit.io.memory_size  = DATA;
95 +
    u32  pc             = CODE;
96 +
    i64  budget         = 100000;
97 +
    bool failed         = false;
95 98
    for (u32 i = 0; i < count + 2; i++) {
96 99
        struct jit_block *block =
97 100
            jit_get_block(&jit, pc, actual, CODE, (count + 1) * 4);
98 101
        assert(block);
99 102
        int reason = jit_run(&jit, block, x, actual, budget);
124 127
    }
125 128
    if (!ref_failed)
126 129
        used++;
127 130
    assert(failed == ref_failed);
128 131
    assert(budget == 100000 - used);
132 +
    u32 traced = 0;
133 +
    for (const u32 *range = ranges; range < jit.io.profile_next; range++) {
134 +
        assert((*range & PROFILE_PC_MASK) == CODE + traced * 4);
135 +
        traced += (*range >> PROFILE_PC_BITS) + 1;
136 +
    }
137 +
    assert(traced == used);
129 138
    assert(memcmp(&a, &b, sizeof(a)) == 0);
130 139
    assert(memcmp(x, y, sizeof(x)) == 0);
131 140
    assert(memcmp(actual, expected, DATA) == 0);
132 141
    if ((count == 8 || (count == 7 && base == 128)) &&
133 142
        (type & ~0xc0u) == 0x11 && vl == 4 && start == 0)