[PGO] Indirect call promotion of `musttail` dispatch in a threaded interpreter inlines too much

I've been benchmarking an interpreter written in Rust that uses guaranteed tail calls and noticed that using PGO substantially reduced performance instead of improving it. The handler is picked by a `switch` on the opcode, which the compiler lowers to one jump table, and each handler is a few instructions long.

With `-fprofile-use` the result is much worse than without a profile:

| build (clang 23.1.1, `-O2`, x86-64) | time | code in handlers |
|---|---|---|
| no profile | 476 ms | 4.7 KB, largest handler 94 B |
| `-fprofile-use` | 874 ms | 316 KB, largest handler 13.7 KB |
| `-fprofile-use -mllvm -disable-icp` | 478 ms | 4.7 KB, largest handler 94 B |

The profile shows every dispatch site with a handful of hot targets, so indirect call promotion promotes them. From there things compound: the promoted target is a `musttail` callee, so it gets inlined; its own dispatch site is hot too, so it is promoted and inlined as well; and because the callee was selected by a `switch` on the opcode, the promotion guards fold back into a `switch`, so every inlined body drags a private copy of the whole jump table along with it. This stops only when the inliner runs out of budget, at which point each handler contains dozens of other handlers and dozens of jump tables.

The cost is the obvious one: the hot code no longer fits in the instruction cache, and the extra branches predict worse than the single indirect jump did. The original indirect jump is the point of the design, it lets the indirect branch predictor key on the current instruction. Replacing it only pays off when one successor dominates, which is not the case for interpreted code, where the most frequent successor is typically well under half of the transitions.

In a RISC-V interpreter written in Rust (~450 handlers, Rust `become` tail calls): with PGO, a 52-byte `add` handler became 27 KB and the benchmark got 25% slower, while `-C llvm-args=-disable-icp` turned PGO into a 5% win.

## Reproduction

I used LLM to produce this representative C example of my Rust application:

threaded.c

```c
// Threaded interpreter: every handler ends in a guaranteed tail call through a table of handlers,
// indexed by the opcode of the next instruction, the way interpreters with a decoded instruction
// stream dispatch. Build and run:
//
// clang -O2 threaded.c -o plain && ./plain
// clang -O2 -fprofile-generate threaded.c -o gen && ./gen && \
// llvm-profdata merge -o pgo.profdata default_*.profraw
// clang -O2 -fprofile-use=pgo.profdata threaded.c -o pgo && ./pgo
// clang -O2 -fprofile-use=pgo.profdata -mllvm -disable-icp threaded.c -o pgo-noicp && ./pgo-noicp
#include
#include
#include

typedef struct {
uint8_t op;
uint8_t rd;
uint8_t rs1;
uint8_t rs2;
int32_t imm;
} Insn;

typedef uint64_t (*Handler)(const Insn *pc, uint64_t *regs);
// Decoded instruction streams select the handler with a `switch` on the opcode (an enum
// discriminant), which the compiler lowers to a jump table on its own
static inline __attribute__((always_inline)) Handler dispatch(uint8_t op);

#define NEXT() __attribute__((musttail)) return dispatch(pc[1].op)(pc + 1, regs)
#define HANDLER(name) static uint64_t name(const Insn *pc, uint64_t *regs)

// Several variants of each operation, like an ISA has (register/immediate/word forms and so on),
// so that the table is not tiny
#define VARIANTS(X) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7)
#define ADD(k) HANDLER(op_add##k) { regs[pc->rd] = regs[pc->rs1] + regs[pc->rs2] + k; NEXT(); }
#define SUB(k) HANDLER(op_sub##k) { regs[pc->rd] = regs[pc->rs1] - regs[pc->rs2] - k; NEXT(); }
#define XOR(k) HANDLER(op_xor##k) { regs[pc->rd] = regs[pc->rs1] ^ regs[pc->rs2] ^ k; NEXT(); }
#define AND(k) HANDLER(op_and##k) { regs[pc->rd] = regs[pc->rs1] & (regs[pc->rs2] | k); NEXT(); }
#define ROR(k) HANDLER(op_ror##k) { \
uint64_t v = regs[pc->rs1]; \
unsigned s = ((unsigned)pc->imm + k) & 63; \
regs[pc->rd] = (v >> s) | (v << ((64 - s) & 63)); \
NEXT(); \
}
#define MUL(k) HANDLER(op_mul##k) { regs[pc->rd] = regs[pc->rs1] * (regs[pc->rs2] | k); NEXT(); }
VARIANTS(ADD) VARIANTS(SUB) VARIANTS(XOR) VARIANTS(AND) VARIANTS(ROR) VARIANTS(MUL)
// Memory operands with a bounds check and an error exit, like real load/store handlers
#define MEMORY_SIZE 65536
static uint8_t memory[MEMORY_SIZE];
#define LOAD(k) HANDLER(op_load##k) { \
uint64_t address = regs[pc->rs1] + (uint64_t)(int64_t)pc->imm + k; \
if (address > MEMORY_SIZE - 8) return 0xE000 + address; \
uint64_t value; \
__builtin_memcpy(&value, memory + address, 8); \
regs[pc->rd] = value; \
NEXT(); \
}
#define STORE(k) HANDLER(op_store##k) { \
uint64_t address = regs[pc->rs1] + (uint64_t)(int64_t)pc->imm + k; \
if (address > MEMORY_SIZE - 8) return 0xF000 + address; \
__builtin_memcpy(memory + address, ®s[pc->rs2], 8); \
NEXT(); \
}
VARIANTS(LOAD) VARIANTS(STORE)
HANDLER(op_addi) { regs[pc->rd] = regs[pc->rs1] + (uint64_t)(int64_t)pc->imm; NEXT(); }
HANDLER(op_bnez) {
if (regs[pc->rs1] != 0) {
pc += pc->imm;
__attribute__((musttail)) return dispatch(pc->op)(pc, regs);
}
NEXT();
}
HANDLER(op_halt) { return regs[1]; }

enum { NUM_ARITH = 8 * 8, ADDI = NUM_ARITH, BNEZ, HALT };

#define CASES(k) \
case 8 * k + 0: return op_add##k; \
case 8 * k + 1: return op_sub##k; \
case 8 * k + 2: return op_xor##k; \
case 8 * k + 3: return op_and##k; \
case 8 * k + 4: return op_ror##k; \
case 8 * k + 5: return op_mul##k; \
case 8 * k + 6: return op_load##k; \
case 8 * k + 7: return op_store##k;
static inline __attribute__((always_inline)) Handler dispatch(uint8_t op) {
switch (op) {
VARIANTS(CASES)
case ADDI: return op_addi;
case BNEZ: return op_bnez;
default: return op_halt;
}
}

// After each instruction the next one is its favourite successor with probability
// `FAVOURITE_PERCENT`, like the recurring idioms in compiler output, and an arbitrary one otherwise
#ifndef FAVOURITE_PERCENT
#define FAVOURITE_PERCENT 40
#endif
#define BODY 4096
static Insn program[BODY + 3];

static void build_program(void) {
uint8_t favourite[NUM_ARITH];
uint32_t state = 12345;
for (int i = 0; i < NUM_ARITH; i++) {
state = state * 1664525u + 1013904223u;
favourite[i] = (uint8_t)((state >> 24) % NUM_ARITH);
}
uint8_t op = 0;
for (int i = 0; i < BODY; i++) {
state = state * 1664525u + 1013904223u;
if ((state >> 24) % 100 < FAVOURITE_PERCENT) {
op = favourite[op];
} else {
op = (uint8_t)((state >> 16) % NUM_ARITH);
}
program[i].op = op;
program[i].rd = 1 + (uint8_t)((state >> 8) % 7);
program[i].rs1 = 1 + (uint8_t)((state >> 12) % 7);
if (op % 8 >= 6) {
program[i].rs1 = 9;
}
program[i].rs2 = 1 + (uint8_t)((state >> 4) % 7);
program[i].imm = 1 + (int32_t)((state >> 2) % 63);
}
program[BODY] = (Insn){ADDI, 8, 8, 0, -1};
program[BODY + 1] = (Insn){BNEZ, 0, 8, 0, -(BODY + 1)};
program[BODY + 2] = (Insn){HALT, 0, 0, 0, 0};
}

int main(int argc, char **argv) {
(void)argv;
build_program();
uint64_t regs[32] = {0};
for (int i = 1; i < 8; i++) regs[i] = 0x9e3779b97f4a7c15ull * (uint64_t)(i + argc);
regs[8] = 20000;
regs[9] = 1024;
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
uint64_t result = dispatch(program[0].op)(program, regs);
clock_gettime(CLOCK_MONOTONIC, &end);
double ms = (double)(end.tv_sec - start.tv_sec) * 1e3 + (double)(end.tv_nsec - start.tv_nsec) / 1e6;
printf("result %016llx, %.1f ms\n", (unsigned long long)result, ms);
return 0;
}
```

`threaded.c` is a 66-handler interpreter over a decoded instruction stream running a program where the next instruction is a fixed favorite successor 40% of the time and arbitrary otherwise.

```sh
clang -O2 threaded.c -o plain && ./plain
clang -O2 -fprofile-generate threaded.c -o gen && ./gen && \
llvm-profdata merge -o pgo.profdata default_*.profraw
clang -O2 -fprofile-use=pgo.profdata threaded.c -o pgo && ./pgo
clang -O2 -fprofile-use=pgo.profdata -mllvm -disable-icp threaded.c -o pgo-noicp && ./pgo-noicp
```

The dispatch looks like this:

```c
typedef uint64_t (*Handler)(const Insn *pc, uint64_t *regs);

static inline __attribute__((always_inline)) Handler dispatch(uint8_t op) {
switch (op) { case 0: return op_add0; /* ... */ default: return op_halt; }
}

#define NEXT() __attribute__((musttail)) return dispatch(pc[1].op)(pc + 1, regs)

static uint64_t op_add0(const Insn *pc, uint64_t *regs) {
regs[pc->rd] = regs[pc->rs1] + regs[pc->rs2];
NEXT();
}
```

Selecting the handler from an array (`TABLE[pc[1].op]`) instead of a `switch` does not reproduce the problem: the promotion guard stays a pointer compare, the chains stay short and PGO is a win. It is the `switch` (an enum discriminant in most front ends, and the natural way to write this) that lets the guards fold into a duplicated jump table.

## What the promoted handler looks like

Without a profile, `op_add0` is sixteen instructions ending in one `jmp *(%rcx,%rax,8)`.

With a profile, the largest handler (`op_xor7`, 13.7 KB) contains 617 indirect jumps. After its own work it switches on the next opcode through a private jump table into inlined handler bodies, each of which does the same again:

```asm
op_xor7:
movzbl 0x2(%rdi),%eax
mov (%rsi,%rax,8),%rax
movzbl 0x3(%rdi),%ecx
xor (%rsi,%rcx,8),%rax
xor $0x7,%rax
movzbl 0x1(%rdi),%ecx
mov %rax,(%rsi,%rcx,8)
movzbl 0x8(%rdi),%eax ; next opcode
cmp $0x41,%rax
ja .Lhalt
lea .Ltable_1(%rip),%rcx ; private copy of the dispatch table
movslq (%rcx,%rax,4),%rax
add %rcx,%rax
jmp *%rax
movzbl 0xa(%rdi),%eax ; op_mul body, inlined
movzbl 0xb(%rdi),%ecx
mov (%rsi,%rcx,8),%rcx
imul (%rsi,%rax,8),%rcx
movzbl 0x9(%rdi),%eax
mov %rcx,(%rsi,%rax,8)
movzbl 0x10(%rdi),%eax ; the opcode after that
cmp $0x41,%rax
ja .Lhalt_2
lea .Ltable_2(%rip),%rcx ; another copy of the table
movslq (%rcx,%rax,4),%rax
add %rcx,%rax
jmp *%rax
... ; and so on, 617 times
```

## Possible fixes (LLM-generated, take with a grain of salt)

Any of these would leave ICP alone for ordinary indirect calls:

1. Do not inline a promoted `musttail` callee whose body ends in the same kind of promotable site. The inlining is what compounds; a `musttail` call asks for a jump, not for a copy.
2. In the ICP cost model, treat a guard that folds into a compare on a value that already feeds a jump table in the same function as unrolling that jump table rather than as devirtualization, and skip it.
3. Cap the code growth ICP-driven inlining may add to one function, as the inliner does for ordinary inlining.

Workaround: `-mllvm -disable-icp` on the profile-use build.

The issue was originally discovered using `rustc 1.100.0-nightly (e7769602a 2026-08-24)`.