7 ms·

> The variable length instructions (currently 16 bit or 32 bit but 48 bit on the horizon) complicate instruction fetch and decode and in particular this is a pr

> The variable length instructions (currently 16 bit or 32 bit but 48 bit on the horizon) complicate instruction fetch and decode and in particular this is a problem for high performance RISC-V implementations. I want to see variable length instructions, but a requirement for instruction alignment. Ie. every aligned 64 bit word of RAM contain one of these: [64 bit instruction] [32 bit instruction][32 bit instruction] [16 bit instruction][16 bit instruction][32 bit instruction] [32 bit instruction][16 bit instruction][16 bit instruction] [16 bit instruction][16 bit instruction][16 bit instruction][16 bit instruction] That should make decode far simpler, but put a little more pressure on compilers (instructions will frequently need to be reordered to align - but a review of compiler generated code is that that frequently isn't an issue)

camel-cdr 3y ago
This is basically what qualcomm proposes, 32 bit instructions and 64 bit aligned 64 bit instructions. I don't think we have real data on it, but I suspect that the negative impact of this would effect 16/32/48/64 way more than just 32/64.
- londons_explore 3y ago
  I would like to also have aligned 16 bit instructions. And maybe even aligned 8 bit instructions for very common things like "decrement register 0" or "test if register 0 is greater than or equal to zero". "Jump back by 10 instructions", etc. Those instructions get widely used in tight loops, so might as well be smaller.
  - adgjlsfhk1 3y ago
    8 bit instructions are a really bad idea. you only get a tiny number of them and they significantly increase decode complexity (and massively reduce the number of larger instructions available)
gchadwick 3y ago
As the other reply states that is effectively the Qualcomm proposal though note the 16-bit instructions likely gobble up a large amount of your 32-bit instruction space. You have to have something to identify an instruction as 16-bit which takes up 32-bit encoding space. The larger you make that identification (in terms of bits) the less encoding space it takes up but then the fewer spare bits you have to actually encoding your 16-bit instruction. RISC-V uses the bottom two bits for this purpose, one value (11) indicates a 32-bit instruction, the others are used for 16-bit instructions. So you're dedicating 75% of your 32-bit encoding space to 16-bit instructions.
- londons_explore 3y ago
  By requiring alignment, you can halve or more the size of the identifier. Since if you have a 16 bit instruction, you know that it must be followed by another 16 bit instruction. Therefore, that 2nd instruction doesn't need the identifying bits. Or, more precisely, within a 32 bit slot, the 2^32 instructions possible need to be divided - and one way to do that is 2^31+2^30 possible 32 bit instructions, and 2^15 * 2^15 16 bit instructions. Now, the 16 bit instructions are only taking 25%, not 75% of the instruction space.
  - Joker_vD 3y ago
    But now you have two kinds of 16-bit instructions, the ones for the leading position and the ones for the trailing position, and the latter ones have slightly more available functionality, right? Personally, at this point I'd think the decoder must already be complicated enough (it has either to maintain "leading/trailing/full" state between the cycles, or to decode 8/16-byte long batches at once) that you could simply give up and go for an encoding with completely irregular lengths à la x86 without much additional cost.
    - namibj 3y ago
      No, the idea was to say "prefix 0"=>31bit, "prefix 10"=>30bit, "prefix 11"=>2*15bit. If you need you can split the two bits to have the two 15 bit chunks aligned identically.
jstanley 3y ago
> instructions will frequently need to be reordered to align Can't you pad it with nops up to the alignment boundary? Even if there's not an explicit nop instruction in 16-bit and 32-bit variants (I don't know) there's surely something you can find that will have no side effects.
- londons_explore 3y ago
  Yes, of course - but in general you want to avoid padding with nops because it makes the code larger (which, as well as costing more RAM, also uses more power and time to read the code from RAM, and fits less code into the instruction cache, which makes the power and time cost of reading code from RAM even bigger). If you can make a compiler fill those NOP slots with useful instructions, then all the better. It adds complexity for humans writing assembly code by hand, but that is a tiny minority of code now.
- KMag 3y ago
  For one, I don't see why you would ever pad a 16-bit instruction with a 16-bit noop instead of just using the 32-bit equivalent instruction. That way, you can skip decoding the no-op.
  - StillBored 3y ago
    Because you have a long odd numbered chain of 16-bit ops. Ex: 15 16-bit ops, leaves you with a 16bit NOP in order to realign for the following 32-bit op.
    - Joker_vD 3y ago
      Use 14 16-bit ops instead, and use a regular 32-bit op as the 15th instruction (which is already correctly aligned since 14 is an even number).
    - KMag 3y ago
      To be more clear: if a 16-bit instruction is 32-bit aligned, then you might want a 16-bit noop so that the instruction following the noop is also 32-bit aligned. But, in that case, you could just use a 32-bit aligned 32-bit instruction at the same location. No padding, one instruction saved, and the following instruction is still 32-bit aligned. If the 16-bit instruction isn't 32-bit aligned, then the following instruction will be 32-bit aligned with no padding. So, equivalently: "I don't know why you'd ever want to add padding after a 16-bit instruction in order to force the next instruction to not be 32-bit aligned." Is there such a use case (other than the obvious use case of checking behavior/performance of the sub-optimal case, or writing a noop-slide for an exploit payload)?
_a_a_a_ 3y ago
Others have pointed out adding bits to identify instruction types eats into your instruction length, so let's go stupid big time: what if you had the instructions as described here, without any instruction length being part of the instruction, but have that stored separately? (3 bits would be plenty per word) You might put it 1. as a contiguous bit string somewhere, or you might 2. put it at the bottom of the cache line that holds the instructions (the cache line being 512 bits I assume). Okay, for 1. you'd have to do two fetches to get stuff into the I-cache (but not if it's part of the same cache line, option 2.) and of course you're going to reduce instruction density because you're using up cache, but there's nothing you can do about that, but at least it would allow n-bit instructions to be genuinely n-bits long which is a big advantage. That this hasn't been done before to my knowledge is proof that it's a rotten idea, but can the experts here please explain why – thanks
- londons_explore 3y ago
  > you'd have to do two fetches I think this is the big downside. You're effectively taking information which will always be needed at the same time, and storing it in two different places. There is never a need for one piece of information without the other, so why not store it together.
  - _a_a_a_ 3y ago
    > There is never a need for one piece of information without the other, so why not store it together. Why not? as I said, so you can have full-length instructions! And you can store it together in the same fetchable unit - the cache line (my option 2)
    - KingLancelot 3y ago
      Why not treat it like Unicode does and just have two marker instructions before and after the compressed ones? Start compressed instructions <size> Compressed instructions End compressed instructions <size>
      - 3y ago
Symmetry 3y ago
Once you're moving to alignment within a larger fixed width block you don't even need to stick to byte boundaries. I've got a toy ISA I've played around with that breaks 64 bit chunks into a 62 bit instruction, a 40 and a 21 bit instruction, or 3 21 bit instructions.
- leosarev 3y ago
  I think Itanium did something like that
  - Symmetry 3y ago
    Yup, 128 bit bundles with 3 instructions each, and ways to indicate that different bundles could execute in parallel.
pklausler 3y ago
The CDC 6600 (1963) had 60-bit words and both 15-bit and 30-bit instructions, with the restriction that 30-bit instructions couldn't straddle a word boundary. The COMPASS assembler would sometimes have to insert a 15-bit no-op instruction to "force upper". Careful optimizing programmers and compilers would try to minimize "forcing upper" to avoid wasting precious space in the 7-word instruction "stack". So it's been done, and is not a big deal.
- chx 3y ago
  was it called assembler though? I was looking and https://web.archive.org/web/20120910064824/http://www.bitsavers.org/pdf/cdc/3x00/24bit/60184200_compassTrng_May67.pdf https://web.archive.org/web/20120910064824/http://www.bitsav... does not say so but http://www.bitsavers.org/pdf/cdc/cyber/cyber_70/60225100_Extended_Core_Storage_System_Ref_Feb68.pdf http://www.bitsavers.org/pdf/cdc/cyber/cyber_70/60225100_Ext... does refer to "COMPASS assembly language". Interesitng.
mshockwave 3y ago
Motorola 68k has this kind of aligned variable length instructions (in their case it’s always aligned on 16 bit boundaries). It’s not super difficult to support this in compilers though

camel-cdr 3y ago

This is basically what qualcomm proposes, 32 bit instructions and 64 bit aligned 64 bit instructions. I don't think we have real data on it, but I suspect that the negative impact of this would effect 16/32/48/64 way more than just 32/64.

londons_explore 3y ago
I would like to also have aligned 16 bit instructions. And maybe even aligned 8 bit instructions for very common things like "decrement register 0" or "test if register 0 is greater than or equal to zero". "Jump back by 10 instructions", etc. Those instructions get widely used in tight loops, so might as well be smaller.
- adgjlsfhk1 3y ago
  8 bit instructions are a really bad idea. you only get a tiny number of them and they significantly increase decode complexity (and massively reduce the number of larger instructions available)

gchadwick 3y ago

As the other reply states that is effectively the Qualcomm proposal though note the 16-bit instructions likely gobble up a large amount of your 32-bit instruction space. You have to have something to identify an instruction as 16-bit which takes up 32-bit encoding space. The larger you make that identification (in terms of bits) the less encoding space it takes up but then the fewer spare bits you have to actually encoding your 16-bit instruction. RISC-V uses the bottom two bits for this purpose, one value (11) indicates a 32-bit instruction, the others are used for 16-bit instructions. So you're dedicating 75% of your 32-bit encoding space to 16-bit instructions.

londons_explore 3y ago
By requiring alignment, you can halve or more the size of the identifier. Since if you have a 16 bit instruction, you know that it must be followed by another 16 bit instruction. Therefore, that 2nd instruction doesn't need the identifying bits. Or, more precisely, within a 32 bit slot, the 2^32 instructions possible need to be divided - and one way to do that is 2^31+2^30 possible 32 bit instructions, and 2^15 * 2^15 16 bit instructions. Now, the 16 bit instructions are only taking 25%, not 75% of the instruction space.
- Joker_vD 3y ago
  But now you have two kinds of 16-bit instructions, the ones for the leading position and the ones for the trailing position, and the latter ones have slightly more available functionality, right? Personally, at this point I'd think the decoder must already be complicated enough (it has either to maintain "leading/trailing/full" state between the cycles, or to decode 8/16-byte long batches at once) that you could simply give up and go for an encoding with completely irregular lengths à la x86 without much additional cost.
  - namibj 3y ago
    No, the idea was to say "prefix 0"=>31bit, "prefix 10"=>30bit, "prefix 11"=>2*15bit. If you need you can split the two bits to have the two 15 bit chunks aligned identically.

jstanley 3y ago

> instructions will frequently need to be reordered to align Can't you pad it with nops up to the alignment boundary? Even if there's not an explicit nop instruction in 16-bit and 32-bit variants (I don't know) there's surely something you can find that will have no side effects.

londons_explore 3y ago
Yes, of course - but in general you want to avoid padding with nops because it makes the code larger (which, as well as costing more RAM, also uses more power and time to read the code from RAM, and fits less code into the instruction cache, which makes the power and time cost of reading code from RAM even bigger). If you can make a compiler fill those NOP slots with useful instructions, then all the better. It adds complexity for humans writing assembly code by hand, but that is a tiny minority of code now.
KMag 3y ago
For one, I don't see why you would ever pad a 16-bit instruction with a 16-bit noop instead of just using the 32-bit equivalent instruction. That way, you can skip decoding the no-op.
- StillBored 3y ago
  Because you have a long odd numbered chain of 16-bit ops. Ex: 15 16-bit ops, leaves you with a 16bit NOP in order to realign for the following 32-bit op.
  - Joker_vD 3y ago
    Use 14 16-bit ops instead, and use a regular 32-bit op as the 15th instruction (which is already correctly aligned since 14 is an even number).
  - KMag 3y ago
    To be more clear: if a 16-bit instruction is 32-bit aligned, then you might want a 16-bit noop so that the instruction following the noop is also 32-bit aligned. But, in that case, you could just use a 32-bit aligned 32-bit instruction at the same location. No padding, one instruction saved, and the following instruction is still 32-bit aligned. If the 16-bit instruction isn't 32-bit aligned, then the following instruction will be 32-bit aligned with no padding. So, equivalently: "I don't know why you'd ever want to add padding after a 16-bit instruction in order to force the next instruction to not be 32-bit aligned." Is there such a use case (other than the obvious use case of checking behavior/performance of the sub-optimal case, or writing a noop-slide for an exploit payload)?

_a_a_a_ 3y ago

Others have pointed out adding bits to identify instruction types eats into your instruction length, so let's go stupid big time: what if you had the instructions as described here, without any instruction length being part of the instruction, but have that stored separately? (3 bits would be plenty per word) You might put it 1. as a contiguous bit string somewhere, or you might 2. put it at the bottom of the cache line that holds the instructions (the cache line being 512 bits I assume). Okay, for 1. you'd have to do two fetches to get stuff into the I-cache (but not if it's part of the same cache line, option 2.) and of course you're going to reduce instruction density because you're using up cache, but there's nothing you can do about that, but at least it would allow n-bit instructions to be genuinely n-bits long which is a big advantage. That this hasn't been done before to my knowledge is proof that it's a rotten idea, but can the experts here please explain why – thanks

londons_explore 3y ago
> you'd have to do two fetches I think this is the big downside. You're effectively taking information which will always be needed at the same time, and storing it in two different places. There is never a need for one piece of information without the other, so why not store it together.
- _a_a_a_ 3y ago
  > There is never a need for one piece of information without the other, so why not store it together. Why not? as I said, so you can have full-length instructions! And you can store it together in the same fetchable unit - the cache line (my option 2)
  - KingLancelot 3y ago
    Why not treat it like Unicode does and just have two marker instructions before and after the compressed ones? Start compressed instructions <size> Compressed instructions End compressed instructions <size>
    - 3y ago

Symmetry 3y ago

Once you're moving to alignment within a larger fixed width block you don't even need to stick to byte boundaries. I've got a toy ISA I've played around with that breaks 64 bit chunks into a 62 bit instruction, a 40 and a 21 bit instruction, or 3 21 bit instructions.

leosarev 3y ago
I think Itanium did something like that
- Symmetry 3y ago
  Yup, 128 bit bundles with 3 instructions each, and ways to indicate that different bundles could execute in parallel.

pklausler 3y ago

The CDC 6600 (1963) had 60-bit words and both 15-bit and 30-bit instructions, with the restriction that 30-bit instructions couldn't straddle a word boundary. The COMPASS assembler would sometimes have to insert a 15-bit no-op instruction to "force upper". Careful optimizing programmers and compilers would try to minimize "forcing upper" to avoid wasting precious space in the 7-word instruction "stack". So it's been done, and is not a big deal.

chx 3y ago
was it called assembler though? I was looking and https://web.archive.org/web/20120910064824/http://www.bitsavers.org/pdf/cdc/3x00/24bit/60184200_compassTrng_May67.pdf https://web.archive.org/web/20120910064824/http://www.bitsav... does not say so but http://www.bitsavers.org/pdf/cdc/cyber/cyber_70/60225100_Extended_Core_Storage_System_Ref_Feb68.pdf http://www.bitsavers.org/pdf/cdc/cyber/cyber_70/60225100_Ext... does refer to "COMPASS assembly language". Interesitng.

mshockwave 3y ago

Motorola 68k has this kind of aligned variable length instructions (in their case it’s always aligned on 16 bit boundaries). It’s not super difficult to support this in compilers though