Implement z-parsing

[mablinov]

Hi all,

This patch is a basic implementation for z-parsing. It provides the expected additive behaviour, and expects correct canonical z-extension order.

I've also classified the riscv-opc.c table entries, and also made a change in how multiple ISA membership is interpreted. Consider the following:

/* Bitmanip instruction subset */
{"andn",      0, {"B", "ZBB", "ZBP", 0},   "d,s,t",  MATCH_ANDN, MASK_ANDN, match_opcode, 0 },
{"orn",       0, {"B", "ZBB", "ZBP", 0},   "d,s,t",  MATCH_ORN, MASK_ORN, match_opcode, 0 },
{"xnor",      0, {"B", "ZBB", "ZBP", 0},   "d,s,t",  MATCH_XNOR, MASK_XNOR, match_opcode, 0 },

Normally, the {"B", "ZBB", "ZBP", 0} entry corresponding to andn means "this instruction may only be used if -march contains "B", "ZBB", and "ZBP".

Logically I cannot think of a situation that an instruction is comprised by multiple ISA subsets - an instruction is always a member of only one subset. However, an instruction may be present in multiple ISA subsets (like we have), so I have changed the semantics of this field in the corresponding riscv_multi_subset_supports checking function to be OR rather than AND.

The rest is parsing code. I've tried to generalize the notion of parsing subset names with prefixes, and didn't bother adding an option to use the old parsing scheme.

I must confess I am sort-of using this branch as an opportunity to test the new "s, sx, z, x" prefix order parsing code, but this goes rather hand-in-hand with bitmanip, since bitmanip really puts this type of parsing to the test. So I think it is justified.

I haven't really given much thought towards the merging of architectures - that has been left as-is since my very first patch to the binutils mailing list.

I've assembled some programs in the terminal, and the behaviour seems to be correct. I'll add testcases as bugs crop up. There will also be a corresponding riscv-gcc/riscv-bitmanip patch very soon.

[jim-wilson]

This is complicated because recent changes to the ISA spec have created incompatibilities in how to specify the architecture (s before or after x?) and what exactly the architecture string means (is fence.i included in i or not?, in g or not?). There is unfortunately no agreement yet on how to deal with this problem.

This is also complicated because Max has posted a similar patch upsream. Should I be reviewing the upstream patch or this one? If we end up with different versions of the same patch here and upstream, that will complicate future merging/rebasing with upstream.

[jim-wilson]

Do you prefer Max or Maxim? I thought I had seen Max somewhere but maybe I'm confused.

[cliffordwolf]

This is also complicated because Max has posted a similar patch upsream.

In that case this PR should probably be two patches: The one for upstream, and then a 2nd one ontop of that for the bitmanip stuff. This will simplify rebasing our branch when the upstream patch gets accepted.

[cliffordwolf]

I cannot think of a situation that an instruction is comprised by multiple ISA subsets

Compressed instructions are such a case: https://github.com/riscv/riscv-binutils-gdb/blob/db8566af4bb2a9cac3c103c81bea257d74a142f6/opcodes/riscv-opc.c#L858-L865

Maybe we should interpret something like "C+D" as the AND of two ISA extensions, and then interpret the list is an OR? This way we could use CNF to express arbitrary relationships between instructions and ISA extensions.

[mablinov]

This is complicated because recent changes to the ISA spec have created incompatibilities in how to specify the architecture (s before or after x?) and what exactly the architecture string means (is fence.i included in i or not?, in g or not?). There is unfortunately no agreement yet on how to deal with this problem.

I appreciate this problem, and I have participated in some of those discussions.

I would really like to get the bitmanip toolchain to a state where one could use it relatively easily and fully-featured, so being able to select subsets through -march for custom processors that support only those subsets, or for benchmarking, etc.

I think, since we have made this branch we can afford some liberty with regards to backwards compatibility. This is after all an experimental branch, and as you commented in my last patch we will go through the full review process later anyway.

So for now, perhaps we can just focus on exposing the bitmanip functionality, and worry about the parsing order issue in parallel. Once that gets sorted out, we can fix up our branch here.

This is also complicated because Max has posted a similar patch upsream. Should I be reviewing the upstream patch or this one? If we end up with different versions of the same patch here and upstream, that will complicate future merging/rebasing with upstream. Do you prefer Max or Maxim? I thought I had seen Max somewhere but maybe I'm confused.

I prefer Maxim. I think, you are probably referring to the same person: You reviewed one of my patches some time ago, that was on the binutils mailing list. Patch for z-prefix parsing: https://www.sourceware.org/ml/binutils/2019-08/msg00000.html (but please ignore the above now, it is out of date.) Patch for dynamic parsing order: https://www.sourceware.org/ml/binutils/2019-08/msg00010.html (my current pull request is very similar, but without the -misa-spec flag.)

And after that, I posted an updated version of the above which implements the alternate parsing order, through the -misa-spec (or -misa-ver, I forget) flag. But it is very rudimentary. It is in the linked repo on the multi-spec-opt branch. https://github.com/mablinov/riscv-binutils-gdb/tree/multi-spec-opt

Just to note, I also have a GCC pull request that mirrors this pull request's functionality: https://github.com/riscv/riscv-gcc/pull/166

We had a discussion with regards to adding an -misa-flag here: https://groups.google.com/a/groups.riscv.org/forum/#!topic/sw-dev/aZhMG7NIVTk but frankly, I left that discussion with more questions than answers. I haven't worked on that branch since.

Maybe we should interpret something like "C+D" as the AND of two ISA extensions, and then interpret the list is an OR? This way we could use CNF to express arbitrary relationships between instructions and ISA extensions.

Damn, I didn't see those... That seems like the most straightforward solution.

[mablinov]

This is also complicated because Max has posted a similar patch upsream.

In that case this PR should probably be two patches: The one for upstream, and then a 2nd one ontop of that for the bitmanip stuff. This will simplify rebasing our branch when the upstream patch gets accepted.

The problem is that I suspect the -march and -misa-spec stuff will take time to resolve. How do we parse -misa-spec? YYYYMMDD? Or some "ratified" string, or a version number "x.y"... And then that selects the default versions for each arch subset? (i2p0 vs i2p1, etc).

You can see all the details here: https://groups.google.com/a/groups.riscv.org/forum/#!topic/sw-dev/aZhMG7NIVTk

I think here we should focus on "-march=rv32izbb..._zbt", and have the assembler do the right thing when it sees the right string (enable the right subset of instructions for usage).

[cliffordwolf]

Maybe we should interpret something like "C+D" as the AND of two ISA extensions [..]

Damn, I didn't see those... That seems like the most straightforward solution.

After sleeping a night over it I'm now thinking that either it should be a list of lists such as {{"A", "B"}, {"A", "C"}} (for (A&B)|(A&C)), or just an easy-to-parse string such as "A+B,A+C". But combining the two (parsing for AND, list for OR) might just leave us with the combined downsides of both solutions.

@jim-wilson what do you think?

[mablinov]

Maybe we should interpret something like "C+D" as the AND of two ISA extensions [..]

Damn, I didn't see those... That seems like the most straightforward solution.

After sleeping a night over it I'm now thinking that either it should be a list of lists such as {{"A", "B"}, {"A", "C"}} (for (A&B)|(A&C)), or just an easy-to-parse string such as "A+B,A+C". But combining the two (parsing for AND, list for OR) might just leave us with the combined downsides of both solutions.

@jim-wilson what do you think?

@cliffordwolf I was thinking, maybe just add some enums, like (please ignore the enum naming scheme, calling them "_P" was a bad idea after I wrote the below...)

enum asm_class_predicate {
  ASM_COMPRESSED_P, // "A"
  ASM_BASE_P, // "I"
  ...
  ASM_COMPRESSED_P, // "C"
  ASM_FLOAT_COMPRESSED_P, // "F" and "C"
  ASM_DOUBLE_COMPRESSED_P, // "D" and "C"
  ...
  ASM_BITMANIP_BASE_P, // "B" or "ZBP"
};

and then in the riscv_multi_subset_supports func, we can do instead of

static bfd_boolean                                                                              
riscv_multi_subset_supports (const char *features[])                                            
{                                                                                               
  unsigned i = 0;                                                                               
  bfd_boolean supported = FALSE;                                                                

  for (;features[i]; ++i)                                                                       
    supported = supported || riscv_subset_supports (features[i]);                               

  return supported;                                                                             
}

have a big switch statement, and do it programmatically

static bfd_boolean                                                                              
riscv_multi_subset_supports (enum asm_class_predicate pred)                                            
{                                                                                               
  switch (pred)
  {
    case ASM_BASE_P:
      return riscv_subset_supports ("i");
    case ASM_FLOAT_COMPRESSED_P:
      return riscv_subset_supports ("c") && riscv_subset_supports ("f");
    ...
    case ASM_BITMANIP_BASE_P:
      return riscv_subset_supports ("b") || riscv_subset_supports ("zbb");
    ...
}

This gives us the most flexibility, and I doubt the number of cases we're going to have is going to exceed 40.

[kito-cheng]

Just another idea for that, use a predicate function instead of string, so that we don't need string parser, string parser might get complicated once version is added.

For example:

...
 {"c.fsw",     32, FC_p , "CD,Ck(Cs)",  MATCH_C_FSW, MASK_C_FSW, match_opcode, INSN_DREF|INSN_4_BYTE }, 
...

bfd_bool FC_P()
{
  return riscv_subset_supports ("c") && riscv_subset_supports ("f");
}

[cliffordwolf]

Just another idea for that, use a predicate function instead of string

I personally like that option a lot. No idea what's the "most GNU" option though. I'll rely on @jim-wilson to make that determination.

[mablinov]

Just another idea for that, use a predicate function instead of string

I personally like that option a lot. No idea what's the "most GNU" option though. I'll rely on @jim-wilson to make that determination.

I would suggest not putting function pointers into the table, as it would mean that the riscv-opc.c opcode table definition is no longer strictly independent of the rest of the assembler/bfd code (atleast, to my understanding.)

Such a separation may be of value in the future, if once wants to re-use the table for perhaps some other library or tool.

With the switch statement, there is admittedly a functionally unnecessary additional level of indirection, but we get to preserve the separation of the opcode table from the parsing and assembly logic.

[kito-cheng]

oh, I got your point, using call back function to decoupling that, and in this version I also put the xlen check inside the predicate function.

...
 {"c.fsw",     FC_p , "CD,Ck(Cs)",  MATCH_C_FSW, MASK_C_FSW, match_opcode, INSN_DREF|INSN_4_BYTE }, 
...

bfd_bool FC_P(subset_support_func_ptr subset_support_func, int xlen)
{
  return  subset_support_func("c") &&  subset_support_func ("f") && (xlen == 32);
}

[kito-cheng]

Such a separation may be of value in the future, if once wants to re-use the table for perhaps some other library or tool.

This also another point I din't consider, let me think.

[mablinov]

Hi everyone,

Here is my proposed implementation. I chose to avoid function pointers for now - if it is a performance problem, or gets really ugly, we can always amend it later. For reference, here is a little sed script to quickly change the subset field:

s/\{\"I\"\,\ 0\}/INSN_CLASS_I/
s/\{\"C\"\,\ 0\}/INSN_CLASS_C/
s/\{\"A\"\,\ 0\}/INSN_CLASS_A/
s/\{\"M\"\,\ 0\}/INSN_CLASS_M/
s/\{\"F\"\,\ 0\}/INSN_CLASS_F/
s/\{\"D\"\,\ 0\}/INSN_CLASS_D/
s/\{\"D\"\,\ \"C\"\,\ 0\}/INSN_CLASS_D_C/
s/\{\"F\"\,\ \"C\"\,\ 0\}/INSN_CLASS_F_C/
s/\{\"Q\"\,\ 0\}/INSN_CLASS_Q/

s/\{\"B\"\,\ 0\}/INSN_CLASS_B/
s/\{\"B\"\,\ \"ZBB\"\,\ 0\}/INSN_CLASS_B_ZBB/
s/\{\"B\"\,\ \"ZBC\"\,\ 0\}/INSN_CLASS_B_ZBC/
s/\{\"B\"\,\ \"ZBE\"\,\ 0\}/INSN_CLASS_B_ZBE/
s/\{\"B\"\,\ \"ZBM\"\,\ 0\}/INSN_CLASS_B_ZBM/
s/\{\"B\"\,\ \"ZBP\"\,\ 0\}/INSN_CLASS_B_ZBP/
s/\{\"B\"\,\ \"ZBR\"\,\ 0\}/INSN_CLASS_B_ZBR/
s/\{\"B\"\,\ \"ZBS\"\,\ 0\}/INSN_CLASS_B_ZBS/
s/\{\"B\"\,\ \"ZBT\"\,\ 0\}/INSN_CLASS_B_ZBT/
s/\{\"B\"\,\ \"ZBB\"\,\ \"ZBP\"\,\ 0\}/INSN_CLASS_B_ZBB_ZBP/

To invoke: $ cd binutils-gdb/gas $ sed -E -f ~/notes/script.sed opcodes/riscv-opc.c > opcodes/riscv-opc2.c

Note that this should be done against the table in the first commit, db8566a.

[kito-cheng]

Hi @mablinov : I don't think your way is ugly, it's just another alternative to implement, but the concept is similar, so I think it's fine to continue with your original proposal :)

BTW, the original multiple extension/subset support was done by me, but it wasn't consider future extension :P so I am really appreciate you improve that.

[mablinov]

@jim-wilson @cliffordwolf @kito-cheng Hi everyone, what do you think of changes? Can it be merged into riscv-bitmanip?

[mablinov]

@kito-cheng Thanks for reviewing Kito. I've incorporated the NULL sentinel changes, and also extended the merging code to cover the other prefix classes also.

[cliffordwolf]

Considering that most of this patch adds the general infrastructure for z-parsing, not something specific to bitmanip, and it changes the entire opcode table in riscv-opc.c in doing so, I think the best way forward for this would be to merge those infrastructure changes to binutils upstream first, and then just add the bitmanip specific bits into this branch.

What do you think @jim-wilson @kito-cheng ?

[jim-wilson]

Some parts of the patch are controversial, and I have far more things to do than time to do them. I was hoping that Kito would make progress on his -misa-spec proposal, coordinating with the LLVM folks, as that gives us a way forward. Meanwhile, splitting the patch up would make it a easier for me. Only some of the stuff is ISA spec version dependent. The other stuff is easier to deal with.

[kito-cheng]

For -misa-spec, I've talked with LLVM guys including @asb last week, but I think it would be better get his response publicly on mailing list, I'll ping him today.

[kito-cheng]

For riscv-opc.c, this changed can be upstream first, it didn't rely on -misa-spec or B-extension

[mablinov]

Ok, I will upstream the riscv-opc.c table changes first.

[mablinov]

if anyone would like to have a look, the patch is here: https://www.sourceware.org/ml/binutils/2019-08/msg00234.html

[cliffordwolf]

jfyi, I have now rebased the riscv-bitmanip branch to binutils upstream, and added INSN_CLASS_B to restore the original functionality before rebase. I'm ready to merge a PR that adds support for more fine-grain Zb ISA extension handling.