performance regression in clang-19 when using computed goto

[mikulas-patocka]

Hi

I noticed that the Ajla programming language ( https://www.ajla-lang.cz/ ) runs slower when being compiled by clang-19 compared to clang-18 or gcc-14. I looked at the assembler, and it turns out that the bytecode interpreter (the file "ipret.c") is not compiled as efficiently as it could be. In particular, clang-19 joins all the "goto *next_label" statements in a function into just one "jmp *" instruction. That reduces code size, but it also makes branch prediction inefficient, because the CPU cannot learn that a single instruction jumps to multiple targets.

I created this example that shows the issue:
http://www.jikos.cz/~mikulas/testcases/clang/computed-goto.c
(use: clang-19 -O2 computed-goto.c && time ./a.out)

The results (in seconds) are here:
http://www.jikos.cz/~mikulas/testcases/clang/computed-goto.txt

We can see that the worst slowdown happens on Sandy Bridge. Zen 4 shows no slowdown, so it seems that it has smart indirect branch predictor that can predict multiple jump targets from a single instruction.

[nikic]

This is caused by #78582, we get separate indirect gotos with -mllvm -tail-dup-pred-size=30. cc @dianqk Possibly we should not apply the limitation to INDIRECTBR, which is more profitable to tail-duplicate than other instructions.

[mikulas-patocka]

-mllvm -tail-dup-pred-size=30 helps the testcase, but not Ajla. If you compile Ajla with clang-19 -O2 -mllvm -tail-dup-pred-size=30 and do
$ objdump -d ipret.o | grep 'jmp \*'
it shows that there is just one indirect jump in the whole file.

[nikic]

What about -mllvm -tail-dup-pred-size=1000? The value needs to be about as large as the number of instructions / indirect jumps.

[mikulas-patocka]

Yes - there are 2284 instructions in the Ajla interpreter. So, I set tail-dup-pred-size=3000 and I get the same output as with clang-18 - 2466 indirect jumps in ipret.o.

[pinskia]

Note GCC (RTL) has a specific pass which duplicates the computed gotos (as GCC merges all computed goto into one BB for performance reasons) which was added in GCC 4.0 and then improved for GCC 7.1.0 (to also unduplicate some related instructions). This pass happens late in the pipeline after register allocation. This is just explaining GCC's solution to the problem and nothing more.

[dianqk]

This is caused by #78582, we get separate indirect gotos with -mllvm -tail-dup-pred-size=30. cc @dianqk Possibly we should not apply the limitation to INDIRECTBR, which is more profitable to tail-duplicate than other instructions.

It looks like makes sense. Thanks!
I will check it later.