So if you are currently involved with ISA-level decisions about inclusion of any pext/pdep-like instructions:

Please consider including SAG/inverse-SAG with bit-reversal of the goats.

No matter which of the two implementation methods you are using: All you need to do is not mask the goat bits.

It looks like the patent expires at the end of 2028. The earliest I could see a RVI extension ratified at this point is 2027, so it's definitely worth evaluating.

Also, the new diagrams are cool.

I've only watched the last hour this far, but I quite liked your take on null-terminated strings.
C really has to be understood with its history in mind.

YouTube video by Ventana Micro Ventana’s Second Gen RISC V Processor for Data Center and Other High Performance | Greg Favor

www.youtube.com/watch?v=OPgj...

Their V2 slides say, that they have a macro-op cache equivalent in size to a regular 32 KiB icache.
It can store variable length entries of up to 48 macro ops, which can be fuses from non-sequential instruction runs by collapsing taken branches.

TIL about Trace Cache: www.realworldtech.com/forum/?threa... (thread on Apples Trace Cache)

Ventanas Veyron V2/V3 seem to also use something like a trace cache.

YouTube video by Rami Sheikh CBP2025 - Opening Remarks - Rami Sheikh

Ohh, the talk recordings are on YouTube: www.youtube.com/watch?v=1lwz...

The sixth Championship of Branch Prediction (CBP2025) happened a week ago: ericrotenberg.wordpress.ncsu.edu/cbp2025-work...

edu-sag/param.v at main · clairexen/edu-sag Educational 8-Bit Sheep-And-Goats (SAG) Verilog Reference IP - clairexen/edu-sag

I wrote a reference implementation for a SAG without bit reflection: github.com/clairexen/ed..., and I wrote a parametric SAG core for any bit width: github.com/clairexen/ed...

>>> lut=np.array([ord('a'),0,ord('e'),0,ord('i'),0,0,ord('o'),0,0,ord('u'),0,0,0,0,0], dtype=np.uint8)
>>> inp=np.frombuffer(b"test128aeiou72761xjs",dtype=np.uint8)
>>> lut[(inp&31)>>1]==inp

4x 16-bit: 120 u^2 63% utilized, 5GHz met (49 slack)

2x 32-bit: 120 u^2 65% utilized, 5GHz met (52 slack)

1x 64-bit: 153 u^2 64% utilized, 5GHz met (14 slack)

So subsetting on SEW really doesn't make much sense compared to a .vx subset.

I got OpenROAD working and tested the bfly part of your implementation (so without decode) in a SIMD setup.

asap7, targeting 5GHz, 75% placement density and 50% utilization:

SiFive X280 RVV benchmarks: camel-cdr.github.io/rvv-bench-re...

Civil was so nice run my RVV benchmark on the SiFive X280 cores on the Tenstorrent Blackhole.

I just had this problem on RISC-V where I didn't clobber the vector registers and some autovectorized surrounding code broke on a newer kenel version.

TIL you can't do forward compatible syscalls with inline assembly because the kernel can decide to clobber architectural state that was added after you wrote the code.

If you use svc with inline assembly, you have to explicitly clobber SVE registers.
Good luck doing this back in 2015 when you wrote

I suppose, the instruction encoding space has to be considered as well.

Ah, I understand my mistake now.
My mental model had the element order between the stages as fixed, which is why I didn't see the equivalence of the graphs.

Guess I'll step up: github.com/camel-cdr/bf...

And, yes, I wasn't the first person to write an optimizing brainfuck interpreter in the c preprocessing, that honor goes to kotha.

Also, I think there should be a compress_right_flip and compress_right instruction, because most cases would want the mask and it's basically free to add in hardware.

I (not a hardware person) would expect a regular ibfly to have 2+4+8 parallel wires, while this approach has 10+10+10. (both +4 for every layer, if you include the control signals)

For 8-bit this is quite tame, but for 64-bit this may be a significant factor.

Ah, I think I understand this better now.

The unshuffle approach is quite neat, but
isn't it a lot worse in terms of wire crossings/area/delay for a single cycle implementation?

I thought a butterfly network can't do SAG in one pass: programming.sirrida.de/bit_perm.htm...

> […] sheep-and-goats operation generally cannot be performed on a butterfly network; […] a variant thereof can which gathers the […] bits on one end in order, but also the remaining ones mirrored […]

I think something like vrgather128ei4.vx would be useful.
It would do a 16-byte shuffle in all 128-bit lanes controlled by the nibbles in the GPR.
This could use the same shuffle hardware as vrgather, but scales better with LMUL/large vlen and saves a vector register allocation.

So like xperm4? That would require new, presumably expensive, bit shuffle hardware.

With vbmatflip+vrgather+vbmatflip you could shuffle bits in bytes and using vrgather+vbmatflip+vrgather+vbmatflip+vrgather gives you bits in 16b/32b/64b/... permute (the limit depends on VLEN).

On that topic. I think a 16-bit bit permute would be extremly cheap to implement.
You just chain the bfly and ibfly networks and need 2x 4x8-bit = 64 control bits, which fit in a GPR.

Something like vb16perm.vx vrd, vs, rs.

I don't see any chances getting that through RVI though, to impl specific

Looking forward to it.

SAG would be nice, if it's cheap with the pext/pdep hardware, but I'm not sure I follow the "not mask the unselected bits".

Wouldn't you run the bfly and ibfly in parallel and combine the results, which would require a new shifter.
Or implement compress-flip, which needs a partial bit reverse.

Sidenote: My pseudocode for the LEB128 decoder using RVV pext/pdep instructions isn't completely correct.

I'll revisit it properly, with spike/qemu implementation, once I finish my project.

Lastly, do you know any other bitmanip instructions that were considered and may be useful for RVV?

This also goes to everybody else reading; I'd love to hear interesting SIMD instruction suggestions.

This would mean implementations of that subset would only have to decode one mask to control signals; it might even be possible to do the prefix sum on the viota.m hardware.

Is implementing bmatflip via chaining the bfly and ibfly network uses in the pdep/pext implementation reasonable?