emulator: Simplify hosted instruction profiling

ec6635ad229c13bbb737ba0b4a63b9283de1fd73601e9cd2563855034db79df1
Share the interpreter dispatch loop and pair JIT range recording with
budget charging. Index function entries by code page and walk sorted
symbols when writing per-PC counts.

Change-Id: Id778ba6c857ceb2481842f83819005fa4031897b
Alexis Sellier committed ago 1 parent d9ccfba8
emulator.c +31 -34
204 204
            *value |= (u64)memory[address + j] << (j * 8);
205 205
    }
206 206
    return true;
207 207
}
208 208
209 -
static void cpu_execute(struct cpu *, enum display, bool headless);
209 +
static bool cpu_execute(struct cpu *, enum display, bool headless);
210 210
static void emit_fault_diagnostics(struct cpu *, u32 pc);
211 211
212 212
/* Emulator runtime options, populated from CLI flags. */
213 213
struct emulator_options {
214 214
    bool        stack_guard;
1520 1520
    io->reservation =
1521 1521
        cpu->reserved ? jit_reservation(cpu->reservation, cpu->reservation_size)
1522 1522
                      : 0;
1523 1523
}
1524 1524
1525 -
static void cpu_execute(struct cpu *cpu, enum display display, bool headless) {
1525 +
/* Execute one instruction. Return false if there is no instruction to dispatch.
1526 +
 */
1527 +
static bool cpu_execute(struct cpu *cpu, enum display display, bool headless) {
1526 1528
    if (cpu_out_of_bounds(cpu)) {
1527 1529
        cpu->running = false;
1528 1530
        emit_fault_diagnostics(cpu, cpu->pc);
1529 1531
        if (headless) {
1530 1532
            fprintf(stderr, "program is out of bounds\n");
1531 -
            return;
1533 +
            return false;
1532 1534
        }
1533 1535
        bail("program is out of bounds");
1534 1536
    }
1535 1537
1536 1538
    u32     executed_pc = cpu->pc;
2235 2237
    }
2236 2238
2237 2239
    /* Track last executed PC for trace mode. */
2238 2240
    if (headless && g_opts.trace_print_instructions)
2239 2241
        last_executed_pc = executed_pc;
2242 +
    return true;
2240 2243
}
2241 2244
2242 2245
/* Render the instructions column. */
2243 2246
static void ui_render_instructions(
2244 2247
    struct cpu *cpu, int col, int width, int height
2482 2485
        host_report_outcome(g_opts.outcome_fd, &outcome);
2483 2486
    }
2484 2487
    return status;
2485 2488
}
2486 2489
2487 -
/* Run the interpreter and batch the PC of each dispatched instruction. */
2488 -
static void run_profiled_interpreter(
2490 +
/* Number of words available to the JIT and interpreter for trace ranges. */
2491 +
enum { PROFILE_BUFFER_COUNT = 16384 };
2492 +
2493 +
/* Run the interpreter and batch the PC of each dispatched instruction when
2494 +
 * profiling is enabled. Return the updated instruction count. */
2495 +
static u64 run_interpreter(
2489 2496
    struct cpu     *cpu,
2490 2497
    enum display    display,
2491 2498
    u64             max_steps,
2492 -
    u64            *steps,
2499 +
    u64             steps,
2493 2500
    struct profile *profile,
2494 -
    u32            *ranges,
2495 -
    size_t          capacity
2501 +
    u32            *ranges
2496 2502
) {
2497 2503
    size_t count = 0;
2498 -
    while (cpu->running && *steps < max_steps) {
2499 -
        u32 pc = cpu->pc;
2500 -
        if (!cpu_out_of_bounds(cpu)) {
2504 +
    /* ---- Interpreter-only loop ---- */
2505 +
    while (cpu->running && steps < max_steps) {
2506 +
        u32  pc         = cpu->pc;
2507 +
        bool dispatched = cpu_execute(cpu, display, true);
2508 +
        if (profile) {
2509 +
            if (!dispatched)
2510 +
                break;
2501 2511
            if (pc > PROFILE_PC_MASK)
2502 2512
                ranges[count++] = PROFILE_PC_ESCAPE;
2503 2513
            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;
2514 +
            if (count >= PROFILE_BUFFER_COUNT - 1) {
2515 +
                profile_record(profile, ranges, ranges + count);
2516 +
                count = 0;
2517 +
            }
2510 2518
        }
2519 +
        steps++;
2511 2520
    }
2512 2521
    if (count)
2513 2522
        profile_record(profile, ranges, ranges + count);
2523 +
    return steps;
2514 2524
}
2515 2525
2516 2526
int main(int argc, char *argv[]) {
2517 2527
    struct cpu        cpu;
2518 2528
    enum display      display = DISPLAY_DEC;
2556 2566
2557 2567
    if (headless) {
2558 2568
        u64             max_steps = g_opts.headless_max_steps;
2559 2569
        u64             steps     = 0;
2560 2570
        struct profile *profile   = NULL;
2561 -
        enum { PROFILE_BUFFER_COUNT = 16384 };
2562 -
        static u32 ranges[PROFILE_BUFFER_COUNT];
2571 +
        static u32      ranges[PROFILE_BUFFER_COUNT];
2563 2572
        if (g_opts.profile_prefix || g_opts.profile_trace ||
2564 2573
            g_opts.profile_function)
2565 2574
            profile = profile_open(
2566 2575
                cli.program_path,
2567 2576
                memory,
2657 2666
                    break;
2658 2667
                }
2659 2668
            }
2660 2669
            jit_destroy(&jit);
2661 2670
        }
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 +
        if (interpret)
2672 +
            steps = run_interpreter(
2673 +
                &cpu, display, max_steps, steps, profile, ranges
2671 2674
            );
2672 -
        } else if (interpret) {
2673 -
            /* ---- Interpreter-only loop ---- */
2674 -
            while (cpu.running && steps++ < max_steps) {
2675 -
                cpu_execute(&cpu, display, true);
2676 -
            }
2677 -
        }
2678 2675
2679 2676
        if (!profile_close(
2680 2677
                profile,
2681 2678
                cpu.running ? cpu.pc : 0,
2682 2679
                cpu.running || (!cpu.regs[RA] && !cpu.faulted && !cpu.ebreak)
jit.c +10 -8
443 443
    emit_u8(e, modrm(1, X_RCX, HIO));
444 444
    emit_u8(e, IO_PROFILE_NEXT);
445 445
}
446 446
447 447
/* Charge the instructions on this path and set the budget flags. */
448 -
static void emit_charge(struct emitter *e, u32 insns) {
448 +
static void emit_budget_charge(struct emitter *e, u32 insns) {
449 449
    if (insns == 0)
450 450
        return;
451 451
    bool small = insns <= INT8_MAX;
452 452
    emit_u8(e, 0x49);
453 453
    emit_u8(e, small ? 0x83 : 0x81);
456 456
        emit_u8(e, (u8)insns);
457 457
    else
458 458
        emit_u32(e, insns);
459 459
}
460 460
461 +
/* Record instructions before charging them, so the budget sets the flags. */
462 +
static void emit_charge(struct emitter *e, u32 insns) {
463 +
    emit_profile(e, insns);
464 +
    emit_budget_charge(e, insns);
465 +
}
466 +
461 467
/* mov eax, reason; jmp exit_stub.  While spilled, the register
462 468
 * file is already current and the host registers may be stale. */
463 469
static void emit_exit(struct emitter *e, u32 exit_reason) {
464 470
    emit_u8(e, 0xB8);
465 471
    emit_u32(e, exit_reason); /* mov eax, reason */
468 474
469 475
/* Store next-PC to *r14 and leave the cache with `reason`. */
470 476
static void emit_block_exit(
471 477
    struct emitter *e, enum jit_exit reason, u32 next_pc
472 478
) {
473 -
    emit_profile(e, e->insns);
474 479
    emit_charge(e, e->insns);
475 480
    emit_store_pc_imm(e, next_pc);
476 481
    emit_exit(e, (u32)reason);
477 482
}
478 483
504 509
/* Charge the block and jump to `target` with all held registers loaded. */
505 510
static void emit_chain_exit(struct emitter *e, u32 target) {
506 511
    bool spilled = e->spilled;
507 512
    if (spilled)
508 513
        emit_reload(e);
509 -
    emit_profile(e, e->insns);
510 514
    emit_charge(e, e->insns);
511 515
    emit_link(e, target);
512 516
    e->spilled = spilled;
513 517
}
514 518
545 549
    emit_u8(e, 0x86);
546 550
    emit_u32(e, 0);
547 551
548 552
    emit_u8(e, 0x68); /* push guest link */
549 553
    emit_u32(e, next);
550 -
    emit_profile(e, e->insns);
551 554
    emit_charge(e, e->insns);
552 555
    u32 call = e->pos;
553 556
    emit_u8(e, 0xE8);
554 557
    emit_u32(e, 0);
555 558
579 582
 */
580 583
static void emit_indirect_jump(struct emitter *e) {
581 584
    if (e->spilled)
582 585
        emit_reload(e);
583 586
587 +
    /* Record before using rcx for the cache index. */
584 588
    emit_profile(e, e->insns);
585 589
586 590
    /* mov ecx, eax; and ecx, mask << 2; shl ecx, 2 -- byte offset of the
587 591
     * entry, ((pc >> 2) & mask) * sizeof(struct jit_jump_entry). */
588 592
    emit_u8(e, 0x89);
601 605
    emit_u8(e, sib(0, X_RCX, HIO));
602 606
    emit_u32(e, IO_JUMP_CACHE);
603 607
604 608
    u32 jne_pos = emit_jnz_placeholder(e);
605 609
606 -
    emit_charge(e, e->insns);
610 +
    emit_budget_charge(e, e->insns);
607 611
608 612
    /* jmp [r14 + rcx + IO_JUMP_CACHE + offsetof(code)] */
609 613
    emit_u8(e, 0x41);
610 614
    emit_u8(e, 0xFF);
611 615
    emit_u8(e, modrm(2, 4, 4));
612 616
    emit_u8(e, sib(0, X_RCX, HIO));
613 617
    emit_u32(e, IO_JUMP_CACHE + offsetof(struct jit_jump_entry, code));
614 618
615 619
    /* Miss: save the target PC for C. */
616 620
    patch_jcc(e, jne_pos, e->pos);
617 -
    emit_charge(e, e->insns);
621 +
    emit_budget_charge(e, e->insns);
618 622
    emit_u8(e, 0x41);
619 623
    emit_u8(e, 0x89);
620 624
    emit_u8(e, modrm(0, X_RAX, HIO));
621 625
    emit_exit(e, JIT_EXIT_BRANCH);
622 626
}
1973 1977
        bad[i] = emit_jne_placeholder(e);
1974 1978
    }
1975 1979
    u32 ok = emit_jmp_placeholder(e);
1976 1980
    for (u32 i = 0; i < 3; i++)
1977 1981
        patch_jcc(e, bad[i], e->pos);
1978 -
    emit_profile(e, 1);
1979 1982
    emit_charge(e, 1);
1980 1983
    emit_store_pc_imm(e, pc);
1981 1984
    emit_exit(e, JIT_EXIT_FAULT);
1982 1985
    patch_jmp(e, ok, e->pos);
1983 1986
}
2056 2059
    emit_u8(e, modrm(1, X_RAX, X_RSP));
2057 2060
    emit_u8(e, sib(0, X_RSP, X_RSP));
2058 2061
    emit_u8(e, 8);
2059 2062
    u32 mismatch = emit_jnz_placeholder(e);
2060 2063
    /* The budget was positive at entry, so this subtraction clears OF. */
2061 -
    emit_profile(e, e->insns);
2062 2064
    emit_charge(e, e->insns);
2063 2065
    emit_native_ret(e);
2064 2066
    patch_jcc(e, mismatch, e->pos);
2065 2067
2066 2068
    /* test rax, rax */
profile.c +50 -29
18 18
struct symbol {
19 19
    u32   offset;
20 20
    char *name;
21 21
};
22 22
23 +
/* A page indexes 64 instructions. Its entry bits recognize jump targets,
24 +
 * and first gives the start of the page's names in the sorted symbol table. */
25 +
struct symbol_page {
26 +
    u64 entries;
27 +
    u32 first;
28 +
};
29 +
23 30
/* One unique call stack, stored with its parent stack. Index zero is empty. */
24 31
struct stack_node {
25 32
    u32 parent;
26 33
    u32 pc;
27 34
    u64 self;
51 58
    bool                    track_calls;
52 59
    u32                     function_pc;
53 60
    u64                     invocations;
54 61
    struct symbol          *symbols;
55 62
    size_t                  symbol_count;
56 -
    /* Index of the containing symbol plus one, or zero for an unknown PC. */
57 -
    u32 *symbol_index;
63 +
    struct symbol_page     *symbol_pages;
58 64
    /* Range updates give per-PC counts with two additions per recorded range.
59 65
     */
60 66
    u64               *pc_delta;
61 67
    struct stack_node *nodes;
62 68
    size_t             node_count;
141 147
    free(data);
142 148
    if (!p->symbol_count)
143 149
        return;
144 150
    qsort(p->symbols, p->symbol_count, sizeof(*p->symbols), compare_symbols);
145 151
146 -
    size_t words    = p->bytes / INSTR_SIZE;
147 -
    p->symbol_index = calloc(words, sizeof(*p->symbol_index));
148 -
    if (!p->symbol_index)
152 +
    u32 page_bytes  = 64 * INSTR_SIZE;
153 +
    u32 pages       = (p->bytes + page_bytes - 1) / page_bytes;
154 +
    p->symbol_pages = calloc(pages + 1, sizeof(*p->symbol_pages));
155 +
    if (!p->symbol_pages)
149 156
        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;
157 +
    u32 symbol = 0;
158 +
    for (u32 i = 0; i < pages; i++) {
159 +
        struct symbol_page *page = &p->symbol_pages[i];
160 +
        page->first              = symbol;
161 +
        u32 end                  = (i + 1) * page_bytes;
162 +
        while (symbol < p->symbol_count && p->symbols[symbol].offset < end) {
163 +
            u32 index      = p->symbols[symbol++].offset / INSTR_SIZE;
164 +
            page->entries |= 1ull << (index % 64);
165 +
        }
156 166
    }
167 +
    p->symbol_pages[pages].first = symbol;
157 168
}
158 169
159 -
static const struct symbol *symbol_at(const struct profile *p, u32 pc) {
160 -
    if (!p->symbol_index || pc - p->base >= p->bytes)
170 +
/* Return the index page if offset identifies a function entry. */
171 +
static const struct symbol_page *entry_page(
172 +
    const struct profile *p, u32 offset
173 +
) {
174 +
    if (!p->symbol_pages || offset >= p->bytes || offset % INSTR_SIZE)
161 175
        return NULL;
162 -
    u32 index = p->symbol_index[(pc - p->base) / INSTR_SIZE];
163 -
    return index ? &p->symbols[index - 1] : NULL;
176 +
    u32                       index = offset / INSTR_SIZE;
177 +
    const struct symbol_page *page  = &p->symbol_pages[index / 64];
178 +
    return (page->entries & (1ull << (index % 64))) ? page : NULL;
164 179
}
165 180
166 181
/* Render a field that is also safe as a folded-stack frame. */
167 182
static void field(FILE *file, const char *str) {
168 183
    size_t n = strcspn(str, ";\t\r\n");
173 188
    for (; *str; str++)
174 189
        fputc(strchr(";\t\r\n", *str) ? '_' : (unsigned char)*str, file);
175 190
}
176 191
177 192
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);
193 +
    u32                       offset = pc - p->base;
194 +
    const struct symbol_page *page   = entry_page(p, offset);
195 +
    if (page) {
196 +
        /* Search backward so an exact match uses the last alias. */
197 +
        u32 symbol = page[1].first - 1;
198 +
        while (p->symbols[symbol].offset != offset)
199 +
            symbol--;
200 +
        field(file, p->symbols[symbol].name);
181 201
        return;
182 202
    }
183 203
    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);
204 +
    if (offset < p->bytes) {
205 +
        const struct debug_entry *loc = debug_map_lookup(p->debug, offset);
187 206
        if (loc) {
188 207
            fputc('@', file);
189 208
            field(file, loc->file);
190 209
            fprintf(file, ":%u", loc->offset);
191 210
        }
310 329
    if (is_link(rd)) {
311 330
        enter(p, target, prev + INSTR_SIZE, false);
312 331
        return;
313 332
    }
314 333
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)
334 +
    const struct frame *frame = &p->frames[p->depth - 1];
335 +
    if (rd == ZERO && frame->pc != target && entry_page(p, target - p->base))
319 336
        enter(p, target, frame->link, true);
320 337
}
321 338
322 339
struct profile *profile_open(
323 340
    const char             *program,
452 469
            fprintf(p->folded, " %llu\n", (unsigned long long)p->nodes[i].self);
453 470
        }
454 471
        free(path);
455 472
456 473
        fputs("pc\tinstructions\tfunction\tsource\tbyte_offset\n", p->pcs);
457 -
        u64 count = 0;
474 +
        u64                  count       = 0;
475 +
        size_t               next_symbol = 0;
476 +
        const struct symbol *sym         = NULL;
458 477
        for (u32 i = 0; i < p->bytes / INSTR_SIZE; i++) {
459 478
            count += p->pc_delta[i];
460 479
            if (!count)
461 480
                continue;
462 -
            u32                       offset = i * INSTR_SIZE;
463 -
            const struct symbol      *sym    = symbol_at(p, p->base + offset);
481 +
            u32 offset = i * INSTR_SIZE;
482 +
            while (next_symbol < p->symbol_count &&
483 +
                   p->symbols[next_symbol].offset <= offset)
484 +
                sym = &p->symbols[next_symbol++];
464 485
            const struct debug_entry *loc = debug_map_lookup(p->debug, offset);
465 486
            if (sym && loc && loc->pc < sym->offset)
466 487
                loc = NULL;
467 488
            fprintf(
468 489
                p->pcs,
493 514
    }
494 515
    bool ok = !p->failed;
495 516
    for (size_t i = 0; i < p->symbol_count; i++)
496 517
        free(p->symbols[i].name);
497 518
    free(p->symbols);
498 -
    free(p->symbol_index);
519 +
    free(p->symbol_pages);
499 520
    free(p->pc_delta);
500 521
    free(p->nodes);
501 522
    free(p->node_hash);
502 523
    free(p->frames);
503 524
    free(p);