4 ms·

The trick takes advantage of 32-bit registers automatically being zero-extended to 64. It actually uses 8GB of allocated address space because WASM's address mo

The trick takes advantage of 32-bit registers automatically being zero-extended to 64. It actually uses 8GB of allocated address space because WASM's address mode takes both a "pointer" and a 32-bit offset, making the effective index 33 bits. On x86-64, there are address modes that can add those and the base address in a single instruction. When that trick can't be used, I think the most efficient method would be to clamp the top of the address so that the max would land on a single guard page. On x86-64 and ARM that would be done with a `cmp`and a conditional move. RISC-V (RVA22 profile and up) has a `max` instruction. That would be typically one additional cycle. The new proposal is for using a 64-bit pointer and a 64-bit offset, which would create a 65-bit effective index. So neither method above could be used. I think each address calculation would first have to add and check for overflow, then do the bounds-check, and then add the base address to the linear memory.

deleted 2y ago
[deleted]
Retr0id 2y ago
A saturating add instruction could help do the same trick without checking for overflows first, although they seem fairly uncommon outside of SIMD instruction sets (aarch64 has UQADD for example)
BeeOnRope 2y ago
> When that trick can't be used, I think the most efficient method would be to clamp the top of the address so that the max would land on a single guard page. If you are already doing a cmp + cmov, wouldn't you be better off just doing a cmp + jmp (to OOB handler)? The cmp + jmp can fuse, so it's probably strictly better in an execution cost sense, plus it doesn't add to the critical data-dependent chain of the load address, which would otherwise add a couple of cycles to the address data chain. Of course, it does require you have these landing pads for the jmp.
- lossolo 2y ago
  CMP + JMP have a branch, which can be mispredicted and then you may pay 5-10x more than for cmp + cmov.
  - BeeOnRope 2y ago
    They won't be mispredicted nor take predictor resources since the default prediction is "not taken" and these branches are never taken (except perhaps once immediately before an OOB crash if that occurs). So they are free in that sense.
Joker_vD 2y ago
> RISC-V (RVA22 profile and up) has a `max` instruction. You know, it's kind of insane that things like this are nigh impossible to learn from the RISC-V official site. Googling on the site itself doesn't yield anything; you have to go to the "Technical > Specifications" page which has PDFs on the basic ISA from 2019, but not on the newer frozen/ratified extensions, and a link to the "RISC-V Technical Specifications" page on their Attlassian subdomain, where you can find a link to a Google doc "RISC-V profiles" and there you will learn that, indeed Zbb extension is mandatory for RVA22U64 profile (and that, apparently, there is no RVA22U32 profile). And of course, you have to know that Zbb extension is the one that has max/min/minu/maxu instructions in it; grepping for "min" or "max" won't find you anything. Because why bother listing all the mnemonics of the mandatorily supported function in a document about the sets of instructions with mandatory support? If someone's reading a RISC-V document, they obviously have already read all the other RISC-V docs that predate it, that's the target audience, after all.
- camel-cdr 2y ago
  There is ongoing work in addressing this. For one, all of the specs are getting merged into a unified isa-manual, you can get the latest version from github: https://github.com/riscv/riscv-isa-manual/releases https://github.com/riscv/riscv-isa-manual/releases The other project is the riscv-unified-db: https://github.com/riscv-software-src/riscv-unified-db https://github.com/riscv-software-src/riscv-unified-db The goal is that this database will hold all specification information in a machine readable format. That allows you to e.g. generate a manual for RVA22 including the ISA specifications: https://riscv-software-src.github.io/riscv-unified-db/pdfs/RVA22.pdf https://riscv-software-src.github.io/riscv-unified-db/pdfs/R... Or a website were you can search for instructions, and get all of the relevant information about it: https://riscv-software-src.github.io/riscv-unified-db/example_cfg/html/generic_rv64/insts/max.html https://riscv-software-src.github.io/riscv-unified-db/exampl... The above two links are still WIP, so there are still a lot of things missing.

deleted 2y ago

[deleted]

Retr0id 2y ago

A saturating add instruction could help do the same trick without checking for overflows first, although they seem fairly uncommon outside of SIMD instruction sets (aarch64 has UQADD for example)

BeeOnRope 2y ago

> When that trick can't be used, I think the most efficient method would be to clamp the top of the address so that the max would land on a single guard page. If you are already doing a cmp + cmov, wouldn't you be better off just doing a cmp + jmp (to OOB handler)? The cmp + jmp can fuse, so it's probably strictly better in an execution cost sense, plus it doesn't add to the critical data-dependent chain of the load address, which would otherwise add a couple of cycles to the address data chain. Of course, it does require you have these landing pads for the jmp.

lossolo 2y ago
CMP + JMP have a branch, which can be mispredicted and then you may pay 5-10x more than for cmp + cmov.
- BeeOnRope 2y ago
  They won't be mispredicted nor take predictor resources since the default prediction is "not taken" and these branches are never taken (except perhaps once immediately before an OOB crash if that occurs). So they are free in that sense.

Joker_vD 2y ago

> RISC-V (RVA22 profile and up) has a `max` instruction. You know, it's kind of insane that things like this are nigh impossible to learn from the RISC-V official site. Googling on the site itself doesn't yield anything; you have to go to the "Technical > Specifications" page which has PDFs on the basic ISA from 2019, but not on the newer frozen/ratified extensions, and a link to the "RISC-V Technical Specifications" page on their Attlassian subdomain, where you can find a link to a Google doc "RISC-V profiles" and there you will learn that, indeed Zbb extension is mandatory for RVA22U64 profile (and that, apparently, there is no RVA22U32 profile). And of course, you have to know that Zbb extension is the one that has max/min/minu/maxu instructions in it; grepping for "min" or "max" won't find you anything. Because why bother listing all the mnemonics of the mandatorily supported function in a document about the sets of instructions with mandatory support? If someone's reading a RISC-V document, they obviously have already read all the other RISC-V docs that predate it, that's the target audience, after all.

camel-cdr 2y ago
There is ongoing work in addressing this. For one, all of the specs are getting merged into a unified isa-manual, you can get the latest version from github: https://github.com/riscv/riscv-isa-manual/releases https://github.com/riscv/riscv-isa-manual/releases The other project is the riscv-unified-db: https://github.com/riscv-software-src/riscv-unified-db https://github.com/riscv-software-src/riscv-unified-db The goal is that this database will hold all specification information in a machine readable format. That allows you to e.g. generate a manual for RVA22 including the ISA specifications: https://riscv-software-src.github.io/riscv-unified-db/pdfs/RVA22.pdf https://riscv-software-src.github.io/riscv-unified-db/pdfs/R... Or a website were you can search for instructions, and get all of the relevant information about it: https://riscv-software-src.github.io/riscv-unified-db/example_cfg/html/generic_rv64/insts/max.html https://riscv-software-src.github.io/riscv-unified-db/exampl... The above two links are still WIP, so there are still a lot of things missing.