SIMD-0174

TL;DR

This proposal introduces wide multiplication, signed division and explicit sign extension to SBPF.

Summary

This proposal introduces wide multiplication, signed division and explicit sign extension to SBPF.

Motivation

All major hardware ISAs support 64 x 64 = 128 bit multiplication; BPF does not. This hurts performance of big integer arithmetics. Similarly, signed division and signed remainder / modulo instructions must be emulated in software as well. Another issue related to arithmetics is that some 32 bit instructions perform sign extension of their results (output, **not** input, there is a difference) implicitly. This is first of all useless because source languages do not read the 32 MSBs of a 32 bit result stored in a 64 bit register. And second, it requires interpreters and compilers to perform extra work to add sign extension at the end of these instructions. Instead we should go the same route as the underlying hardware ISAs and require sign extension to be made explicit in a dedicated instruction. Furthermore, the instruction `sub dst, imm` is redundant as it can also be encoded as `add dst, -imm`. If we were to swap the operands meaning of minuend and subtrahend, then the instruction would become useful and would even render `neg dst` redundant. Negation would then be encoded as `reg = 0 - reg`. This would also make it clear how sign extension rules work for negation.

Key Changes

• the MUL instruction (opcodes 0x24, 0x2C, 0x27 and 0x2F)
• the DIV instruction (opcodes 0x34, 0x3C, 0x37 and 0x3F)
• the MOD instruction (opcodes 0x94, 0x9C, 0x97 and 0x9F)
• the NEG instruction (opcodes 0x84 and 0x87)
• the UHMUL64 instruction (opcode 0x36 and 0x3E)
• the UDIV32 instruction (opcode 0x46 and 0x4E)
• the UDIV64 instruction (opcode 0x56 and 0x5E)
• the UREM32 instruction (opcode 0x66 and 0x6E)
• the UREM64 instruction (opcode 0x76 and 0x7E)
• the LMUL32 instruction (opcode 0x86 and 0x8E)
• the LMUL64 instruction (opcode 0x96 and 0x9E)
• the SHMUL64 instruction (opcode 0xB6 and 0xBE)
• the SDIV32 instruction (opcode 0xC6 and 0xCE)
• the SDIV64 instruction (opcode 0xD6 and 0xDE)
• the SREM32 instruction (opcode 0xE6 and 0xEE)
• the SREM64 instruction (opcode 0xF6 and 0xFE)
• the UHMUL64 instruction (opcode 0x36 and 0x3E) produces the 64 MSBs of
• the UDIV32 instruction (opcode 0x46 and 0x4E) produces the quotient of
• the UDIV64 instruction (opcode 0x56 and 0x5E) produces the quotient of
• the UREM32 instruction (opcode 0x66 and 0x6E) produces the remainder of

Impact

The toolchain will emit machine-code according to the selected SBPF version. Big integer arithmetics and signed divisions will become cheaper CU wise.

Security Considerations

None.