bytecodealliance / bytecodealliance/wasmtime

__multi3 optimization

Open
#4,077 19 comments 0 reactions 0 assignees View on GitHub
cranelift enhancement
Dominant language
Rust
Stars
18.6k
Forks
1.8k
Avg merge
1d 18h
Merged PRs (30d)
126

Description

#### Feature

Implement an optimization pass that would eliminate the `__multi3` function from WASM binary during JIT by replacing it with ISA specific (mainly for `x86_64` and `arm64`) sequences, and then inline such sequences into callsites that would allow further optimizations

#### Benefit

A lot of code dealing with cryptography would benefit form faster full width `u64` multiplications where such `__multi3` arises

#### Implementation

If someone would give a few hints about where to start I'd try to implement it by myself

#### Alternatives

Not that I'm aware of. Patching into calling come native library function is a huge overhead for modern CPUs (4 cycles for `x86_64` for e.g. `mulx` or `mul`), and while it would be faster most likely, it's still far from optimal case on a hot path

As an example a simple multiply-add-carry function like `a*b + c + carry -> (high, low)` that accumulates into `u128` without overflows compiles down to the listing below, and it can be a good test subject (transformed from `wasm` into `wat`, may be not the best readable)

```
(module
(type (;0;) (func (param i32 i64 i64 i64 i64)))
(func $mac (type 0) (param i32 i64 i64 i64 i64)
(local i32)
global.get $__stack_pointer
i32.const 16
i32.sub
local.tee 5
global.set $__stack_pointer
local.get 5
local.get 2
i64.const 0
local.get 1
i64.const 0
call $__multi3
local.get 0
local.get 5
i64.load
local.tee 2
local.get 3
i64.add
local.tee 3
local.get 4
i64.add
local.tee 4
i64.store
local.get 0
local.get 5
i32.const 8
i32.add
i64.load
local.get 3
local.get 2
i64.lt_u
i64.extend_i32_u
i64.add
local.get 4
local.get 3
i64.lt_u
i64.extend_i32_u
i64.add
i64.store offset=8
local.get 5
i32.const 16
i32.add
global.set $__stack_pointer
)
(func $__multi3 (type 0) (param i32 i64 i64 i64 i64)
(local i64 i64 i64 i64 i64 i64)
local.get 0
local.get 3
i64.const 4294967295
i64.and
local.tee 5
local.get 1
i64.const 4294967295
i64.and
local.tee 6
i64.mul
local.tee 7
local.get 5
local.get 1
i64.const 32
i64.shr_u
local.tee 8
i64.mul
local.tee 9
local.get 3
i64.const 32
i64.shr_u
local.tee 10
local.get 6
i64.mul
i64.add
local.tee 5
i64.const 32
i64.shl
i64.add
local.tee 6
i64.store
local.get 0
local.get 10
local.get 8
i64.mul
local.get 5
local.get 9
i64.lt_u
i64.extend_i32_u
i64.const 32
i64.shl
local.get 5
i64.const 32
i64.shr_u
i64.or
i64.add
local.get 6
local.get 7
i64.lt_u
i64.extend_i32_u
i64.add
local.get 4
local.get 1
i64.mul
local.get 3
local.get 2
i64.mul
i64.add
i64.add
i64.store offset=8
)
(table (;0;) 1 1 funcref)
(memory (;0;) 16)
(global $__stack_pointer (mut i32) i32.const 1048576)
(global (;1;) i32 i32.const 1048576)
(global (;2;) i32 i32.const 1048576)
(export "memory" (memory 0))
(export "mac" (func $mac))
(export "__data_end" (global 1))
(export "__heap_base" (global 2))
)
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.