bytecodealliance / bytecodealliance/wasmtime

[proposal] fast path for general integer division for x64

Open
#2,439 8 comments 0 reactions 0 assignees View on GitHub
cranelift cranelift:area:x64 cranelift:goal:optimize-speed
Dominant language
Rust
Stars
18.6k
Forks
1.8k
Avg merge
1d 18h
Merged PRs (30d)
126

Description

#### Feature

Latency and RCP for division depends on register sizes for most of x64 architectures. So Clang do one interesting trick which may speedup 64-bit division if high parts of operands equal to zero. Pseudocode:
```cpp
idiv(a: i64, b: i64) -> i64 {
if ((a | b) >> 32) return a / b; // full 64-bit division
return i32(a) / i32(b) as i64; // 32-bit division
}
```

godbolt: https://godbolt.org/z/Tqqzs1

Is it make sense apply same optimization for cranelift only for x64 architecture?

#### Benefit

it may speedup div / rem over 2x for arguments without high parts with small constant overhead according to this table:
comparision

But it is worth excluding **Zen1,2,3** architecture due to it uses a more modern scheme for division which doesn't dependent on register's width. Also it doesn't need for ARM.

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.