search

golang / go

The Go programming language
https://go.dev
BSD 3-Clause "New" or "Revised" License
124.13k stars 17.69k forks source link

cmd/asm: Allow data references to labels in assembly (support for jump tables) #10870

Open eloff opened 9 years ago

eloff commented 9 years ago

I've noticed a couple comments in Go assembly routines "TODO replace this with a jump table in the future" and when I tried implementing an assembly routine with a jump table I realized why it hasn't been tried yet. The assembler does not support using labels in data, so there's no easy way to construct the jump table. My incomplete understanding of x64 architecture is that jumps are signed 32 bit offsets from the instruction pointer, which seems like it would make it difficult to implement. Maybe there's also a way to do a jump to a 64bit virtual address, I don't know.

Anyway if it's not too difficult, this would be a nice to have.

ianlancetaylor commented 9 years ago

The usual way to implement jump tables on amd64 is something like

tableStart: .word label-tableStart

and then the code that uses the table loads the word into a register, adds tableStart, and jumps to the register.

minux commented 9 years ago

A related compiler request: #5496.

quasilyte commented 6 years ago

In hand-written asm you can do jump tables, though slighly less efficient than you may want (requires 1 more instruction for dispatch).

In short:

  1. Use TEXT blocks instead of labels.
  2. Put every function (label) address into table using $sym<>(SB) syntax.
  3. The rest is the same: compute index, fetch address, use JMP to execute it. This can be done in 2 instruction on x86: load index into register, for example, CX, then do JMP [CX*8+table] (if it's 32-bit platform, you need to scaling of 4). For Go asm, you need to use explicit register base instead of table reference as a displacement. This means you load $table<>(SB) into register, for example AX and then do JMP (AX)(CX*8).

(full read, compete example included: go-asm-dispatch-tables)

But please, measure result performance carefully. Branch tables are not always worth it. And the results will depend on the host machine for sure.

Good luck.

quasilyte commented 6 years ago

If this solution is acceptable, this issue should probably be closed. Or do we really want "real" labels as data support in cmd/asm or in x86 backend specifically?

martisch commented 6 years ago

Thanks for the write up!

Would "real" labels as data support needed for #5496?

randall77 commented 6 years ago

@martisch : Probably not. The compiler "assembles" its own instructions, so the assembler proper would need no changes. We might need some common support in the obj library.

It would be weird for the compiler to generate code that the assembler can't, though.