bytecodealliance / bytecodealliance/wasmtime

Optimize bitreverse using rotate instructions

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

Description

The bitreverse seqences in [lib/codegen/meta-python/base/legalize.py](https://github.com/CraneStation/cranelift/blob/master/lib/codegen/meta-python/base/legalize.py) all end with two shifts and a bitwise or that effectively swap the low half of the value and the high half:
https://github.com/CraneStation/cranelift/blob/master/lib/codegen/meta-python/base/legalize.py#L445
https://github.com/CraneStation/cranelift/blob/master/lib/codegen/meta-python/base/legalize.py#L475
and others for the other types

It would be better to replace these trailing sequences with `rotl_imm`.

That change is the first step, however the catch is that `rotl_imm` isn't implemented in isel yet so we'll need to implement that too. See [the encodings for shifts and non-imm rotates](https://github.com/CraneStation/cranelift/blob/master/lib/codegen/meta-python/isa/x86/encodings.py#L218) as well as [the encodings for imm shifts](https://github.com/CraneStation/cranelift/blob/master/lib/codegen/meta-python/isa/x86/encodings.py#L234) for some examples.

Of course, in the future Cranelift is expected to have a pattern-matching optimization which would automatically optimize shift+bor sequences into rotates, however it doesn't have one right now, and even when it does, it would make the code simpler to just use rotate, and it's more efficient to just use the instruction we want than to emit sequences of instructions that we know will end up getting replaced.

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.