Bitfield Extract/Create instructions

[moonheart08]

This would add two new instructions to cranelift, bextr and bmak. They provide a easy to optimize, and easy to generate mechanism for bitfield manipulation.

bextr

a = bextr target, size, offset

bextr will extract a n bit large field at the provided offset, and return it in a, shifted so that the LSB of the field is also the LSB of a.
a's type is inferred from target

Visual example

offset = 4
size = 4
typeof target = i8

xxxx **** 
\__/----V
0000 xxxx

bmak

a = bmak target, size, offset

bmak will fill a n bit large field at the provided offset with 1s, the rest with 0. The generated field will then be applied to target using a bitwise AND, and the result will be returned in a.
a's type is inferred from target
bmak is designed so that you can simply use a bitwise or to combine the fields.

Visual Example

offset = 2
size = 4
typeof target = i8

xx0101xx
  \__/
  /  \
00010100

[sunfishcode]

Thanks for the idea!

One thing we'll need to investigate here is how these instructions relate to hardware instructions on popular platforms. How does this bextr compare to x86's bextr, or PEXT, ARM's SBFX/UBFX, or RISC-V's proposed bext? And, how does this bmak compare to ARM's BFI, x86's PDEP, or RISC-V's proposed bdep? If it's exactly the same as one or more hardware instructions (possibly ignoring effects on flags registers), that's actually a strong argument for including it. And even if it's different, it'll be important for us to understand how it'll be lowered to hardware instructions.

[moonheart08]

Sorry i'm so late. I described bmak incorrectly. It's suppost a close match to the RISC-V bmak, and both instructions are modeled after the bmak and bextr instructions presented by the MC88100.
The MC88100's bextr and bmak closely match RISC-V's proposed bext and bdep.

I will update the main text soon.

[cfallin]

We discussed this during old-issue triage today and agreed that it is probably better to have users implement this behavior with shifts/masks and then pattern-match that during isel if a particular target ISA has a nice instruction for it. This fits better with the general trend of making CLIF a simple core IR, especially as not every ISA has such instructions -- this would have to be re-expanded in backends otherwise, and only after the point that that expansion could be optimized. I'll close this issue but thank you for the discussion!

[moonheart08]

We discussed this during old-issue triage today and agreed that it is probably better to have users implement this behavior with shifts/masks and then pattern-match that during isel if a particular target ISA has a nice instruction for it. This fits better with the general trend of making CLIF a simple core IR, especially as not every ISA has such instructions -- this would have to be re-expanded in backends otherwise, and only after the point that that expansion could be optimized. I'll close this issue but thank you for the discussion!

7 years later with a stronger understanding of compilers and architectures, and I agree this is probably the right approach. Yet another issue I didn't remember creating resolved today!

[Rafferty97]

Hi, I'm writing a compiler that does a lot of bit manipulation, and using cranelift for the backend.

I've noticed that quite a few instances where two instructions could be compressed into a single UBFM or SBFM instruction.

I'd be willing to open a PR that adds the appropriate ISLE rules, if it's likely to be merged?

[cfallin]

@Rafferty97 yes, PRs that improve instruction selection are always welcome!

[Rafferty97]

@Rafferty97 yes, PRs that improve instruction selection are always welcome!

Awesome, thanks for the quick response! I'll work on it now and put up a PR when I can. Should I file a GitHub issue too or is a detailed PR sufficient?

[cfallin]

A PR is fine, with a reasonable description and ideally a test showing the new lowering -- no need to file a specific issue beforehand.