QEmu ARC port - decoder implementation feedback

QEmu ARC port - decoder implementation feedback

[Cupertino Miranda]

Hi Richard,

Last few weeks I have been working on cleaning up ARC port for further
reviewing.

In the context of the decoder, if I recall well, your observation was
that a linear search was not Ok.
Your suggestion was not to reinvent the wheel and generate decodetree to
create the decoder.

We started to do that and in the process we realize that the approach
would bring us yet another encoding language description to maintain.
Also that decodetree alone would not allow us to properly disassembly
code, still requiring to keep the initial structure.

Taking in consideration that we do all the other toolchain tools for ARC
and that the decoder structure is already upstreamed in binutils we
would definitely prefer to keep that structure and optimize the
surroundings for proper decoding speeds.

So far, we did the following:
   - converted opcodes.def to macros instead of table entries.
   - created a script that reads those entries and outputs macros that
directly translate to a switch/case decision tree (example below), just
like the ones produced by decodetree. The difference is that the switch
will return the enum entry for the proper decoder structure instead of
calling a translation function.
   - the script can either be contributed in C or python language as it
is based on a simple recursive algorithm.

As you have been the one giving attention to our target, I seek for your
early feedback and to make sure that the solution is still inline with
your expectations.

Looking forward for your feedback.

Regards,
Cupertino

PS: Would it be asking too much if we could have a call, just to
get to meet each other. Unfortunately, no one now is able to do it any
other way. I miss the traveling and conferences.

Example1 (first few lines of the file):

   MATCH_PATTERN(0xf8000000) /* 11111000000000000000000000000000 */
    MATCH_VALUE(0x0) /* 0 */
     MATCH_PATTERN(0x10000) /* 10000000000000000 */
      MATCH_VALUE(0x0) /* 0 */
RETURN_MATCH(OPCODE_ARCv2HS_b_0x00000000_0xF8010000_BRANCH_OP_SIMM21_A16_5)
/* 00000ssssssssss0SSSSSSSSSSNQQQQQ */
      END_MATCH_VALUE(0x0) /* 0 */
      MATCH_VALUE(0x10000) /* 10000000000000000 */
RETURN_MATCH(OPCODE_ARCv2HS_b_0x00010000_0xF8010000_BRANCH_OP_SIMM25_A16_5)
/* 00000ssssssssss1SSSSSSSSSSNRtttt */
      END_MATCH_VALUE(0x10000) /* 10000000000000000 */
     END_MATCH_PATTERN(0x10000) /* 10000000000000000 */
    END_MATCH_VALUE(0x0) /* 0 */
    MATCH_VALUE(0x8000000) /* 1000000000000000000000000000 */
     MATCH_PATTERN(0x10000) /* 10000000000000000 */
      MATCH_VALUE(0x0) /* 0 */
       MATCH_PATTERN(0x20000) /* 100000000000000000 */
        MATCH_VALUE(0x0) /* 0 */
RETURN_MATCH(OPCODE_ARCv2HS_bl_0x08000000_0xF8030000_BRANCH_OP_SIMM21_A32_5)
/* 00001sssssssss00SSSSSSSSSSNQQQQQ */
        END_MATCH_VALUE(0x0) /* 0 */
        MATCH_VALUE(0x20000) /* 100000000000000000 */
RETURN_MATCH(OPCODE_ARCv2HS_bl_0x08020000_0xF8030000_BRANCH_OP_SIMM25_A32_5)
/* 00001sssssssss10SSSSSSSSSSNRtttt */
        END_MATCH_VALUE(0x20000) /* 100000000000000000 */
       END_MATCH_PATTERN(0x20000) /* 100000000000000000 */
      END_MATCH_VALUE(0x0) /* 0 */
      MATCH_VALUE(0x10000) /* 10000000000000000 */
       MATCH_PATTERN(0x17) /* 10111 */
        MATCH_VALUE(0x0) /* 0 */
MULTI_MATCH(OPCODE_ARCv2HS_breq_0x08010000_0xF8010017_BRCC_OP_RB_RC_SIMM9_A16_8)
/* 00001bbbsssssss1SBBBCCCCCCN0Y000 */
MULTI_MATCH(OPCODE_ARCv2HS_breq_0x08010F80_0xF8010FF7_BRCC_OP_RB_LIMM_SIMM9_A16_8)
/* 00001bbbsssssss1SBBB11111000Y000 */
MULTI_MATCH(OPCODE_ARCv2HS_breq_0x0E017000_0xFF017037_BRCC_OP_LIMM_RC_SIMM9_A16_8)
/* 00001110sssssss1S111CCCCCC00Y000 */
MULTI_MATCH(OPCODE_ARCv2HS_breq_0x0E017F80_0xFF017FF7_BRCC_OP_LIMM_LIMMdup_SIMM9_A16_8)
/* 00001110sssssss1S11111111000Y000 */
        END_MATCH_VALUE(0x0) /* 0 */

_______________________________________________
linux-snps-arc mailing list
linux-snps-arc@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-snps-arc

QEmu ARC port - decoder implementation feedback

[Cupertino Miranda]

Hi Richard,

Last few weeks I have been working on cleaning up ARC port for further
reviewing.

In the context of the decoder, if I recall well, your observation was
that a linear search was not Ok.
Your suggestion was not to reinvent the wheel and generate decodetree to
create the decoder.

We started to do that and in the process we realize that the approach
would bring us yet another encoding language description to maintain.
Also that decodetree alone would not allow us to properly disassembly
code, still requiring to keep the initial structure.

Taking in consideration that we do all the other toolchain tools for ARC
and that the decoder structure is already upstreamed in binutils we
would definitely prefer to keep that structure and optimize the
surroundings for proper decoding speeds.

So far, we did the following:
   - converted opcodes.def to macros instead of table entries.
   - created a script that reads those entries and outputs macros that
directly translate to a switch/case decision tree (example below), just
like the ones produced by decodetree. The difference is that the switch
will return the enum entry for the proper decoder structure instead of
calling a translation function.
   - the script can either be contributed in C or python language as it
is based on a simple recursive algorithm.

As you have been the one giving attention to our target, I seek for your
early feedback and to make sure that the solution is still inline with
your expectations.

Looking forward for your feedback.

Regards,
Cupertino

PS: Would it be asking too much if we could have a call, just to
get to meet each other. Unfortunately, no one now is able to do it any
other way. I miss the traveling and conferences.

Example1 (first few lines of the file):

   MATCH_PATTERN(0xf8000000) /* 11111000000000000000000000000000 */
    MATCH_VALUE(0x0) /* 0 */
     MATCH_PATTERN(0x10000) /* 10000000000000000 */
      MATCH_VALUE(0x0) /* 0 */
RETURN_MATCH(OPCODE_ARCv2HS_b_0x00000000_0xF8010000_BRANCH_OP_SIMM21_A16_5)
/* 00000ssssssssss0SSSSSSSSSSNQQQQQ */
      END_MATCH_VALUE(0x0) /* 0 */
      MATCH_VALUE(0x10000) /* 10000000000000000 */
RETURN_MATCH(OPCODE_ARCv2HS_b_0x00010000_0xF8010000_BRANCH_OP_SIMM25_A16_5)
/* 00000ssssssssss1SSSSSSSSSSNRtttt */
      END_MATCH_VALUE(0x10000) /* 10000000000000000 */
     END_MATCH_PATTERN(0x10000) /* 10000000000000000 */
    END_MATCH_VALUE(0x0) /* 0 */
    MATCH_VALUE(0x8000000) /* 1000000000000000000000000000 */
     MATCH_PATTERN(0x10000) /* 10000000000000000 */
      MATCH_VALUE(0x0) /* 0 */
       MATCH_PATTERN(0x20000) /* 100000000000000000 */
        MATCH_VALUE(0x0) /* 0 */
RETURN_MATCH(OPCODE_ARCv2HS_bl_0x08000000_0xF8030000_BRANCH_OP_SIMM21_A32_5)
/* 00001sssssssss00SSSSSSSSSSNQQQQQ */
        END_MATCH_VALUE(0x0) /* 0 */
        MATCH_VALUE(0x20000) /* 100000000000000000 */
RETURN_MATCH(OPCODE_ARCv2HS_bl_0x08020000_0xF8030000_BRANCH_OP_SIMM25_A32_5)
/* 00001sssssssss10SSSSSSSSSSNRtttt */
        END_MATCH_VALUE(0x20000) /* 100000000000000000 */
       END_MATCH_PATTERN(0x20000) /* 100000000000000000 */
      END_MATCH_VALUE(0x0) /* 0 */
      MATCH_VALUE(0x10000) /* 10000000000000000 */
       MATCH_PATTERN(0x17) /* 10111 */
        MATCH_VALUE(0x0) /* 0 */
MULTI_MATCH(OPCODE_ARCv2HS_breq_0x08010000_0xF8010017_BRCC_OP_RB_RC_SIMM9_A16_8)
/* 00001bbbsssssss1SBBBCCCCCCN0Y000 */
MULTI_MATCH(OPCODE_ARCv2HS_breq_0x08010F80_0xF8010FF7_BRCC_OP_RB_LIMM_SIMM9_A16_8)
/* 00001bbbsssssss1SBBB11111000Y000 */
MULTI_MATCH(OPCODE_ARCv2HS_breq_0x0E017000_0xFF017037_BRCC_OP_LIMM_RC_SIMM9_A16_8)
/* 00001110sssssss1S111CCCCCC00Y000 */
MULTI_MATCH(OPCODE_ARCv2HS_breq_0x0E017F80_0xFF017FF7_BRCC_OP_LIMM_LIMMdup_SIMM9_A16_8)
/* 00001110sssssss1S11111111000Y000 */
        END_MATCH_VALUE(0x0) /* 0 */

Re: QEmu ARC port - decoder implementation feedback

[Richard Henderson]

On 6/9/21 2:58 AM, Cupertino Miranda wrote:
> We started to do that and in the process we realize that the approach
> would bring us yet another encoding language description to maintain.

Why would you be maintaining another description?  Your approach below with the 
simple recursive algorithm appears to be no different.

> Also that decodetree alone would not allow us to properly disassembly
> code, still requiring to keep the initial structure.

Why is that?

The current uses of decodetree are quite complex, so I sincerely doubt that it 
cannot do the job.  You've asked no questions, nor have you described any 
problems you have encountered.

That said, decodetree was merely a suggestion based on what appeared to me to 
be a trivial automated textual rewrite of your current data set.  If you want 
to use something else that performs equally well, fine.

> So far, we did the following:
>     - converted opcodes.def to macros instead of table entries.

Sure.

>     - created a script that reads those entries and outputs macros that
> directly translate to a switch/case decision tree (example below), just
> like the ones produced by decodetree. The difference is that the switch
> will return the enum entry for the proper decoder structure instead of
> calling a translation function.

An enum result is fine, sure.

The example is not especially enlightening because you don't show the macro 
definitions, or the expansion.  Have you a link to a git repo that you can share?

>     - the script can either be contributed in C or python language as it
> is based on a simple recursive algorithm.

Either is fine.  We currently use both as build-time generators.


r~

_______________________________________________
linux-snps-arc mailing list
linux-snps-arc@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-snps-arc

Re: QEmu ARC port - decoder implementation feedback

[Richard Henderson]

On 6/9/21 2:58 AM, Cupertino Miranda wrote:
> We started to do that and in the process we realize that the approach
> would bring us yet another encoding language description to maintain.

Why would you be maintaining another description?  Your approach below with the 
simple recursive algorithm appears to be no different.

> Also that decodetree alone would not allow us to properly disassembly
> code, still requiring to keep the initial structure.

Why is that?

The current uses of decodetree are quite complex, so I sincerely doubt that it 
cannot do the job.  You've asked no questions, nor have you described any 
problems you have encountered.

That said, decodetree was merely a suggestion based on what appeared to me to 
be a trivial automated textual rewrite of your current data set.  If you want 
to use something else that performs equally well, fine.

> So far, we did the following:
>     - converted opcodes.def to macros instead of table entries.

Sure.

>     - created a script that reads those entries and outputs macros that
> directly translate to a switch/case decision tree (example below), just
> like the ones produced by decodetree. The difference is that the switch
> will return the enum entry for the proper decoder structure instead of
> calling a translation function.

An enum result is fine, sure.

The example is not especially enlightening because you don't show the macro 
definitions, or the expansion.  Have you a link to a git repo that you can share?

>     - the script can either be contributed in C or python language as it
> is based on a simple recursive algorithm.

Either is fine.  We currently use both as build-time generators.


r~

Re: QEmu ARC port - decoder implementation feedback

[Cupertino Miranda]

Hi Richard

> Why would you be maintaining another description?  Your approach below 
> with the simple recursive algorithm appears to be no different.

We initially considered to drop our tables completely replacing it by 
decodetree.

>
>> Also that decodetree alone would not allow us to properly disassembly
>> code, still requiring to keep the initial structure.
>
> Why is that?

By disassembly I am referring to the pretty-print of the instructions 
when using "-d in_asm". Our tables contain information for printing as 
they are the ones used by bintutils assembler.

>
> The current uses of decodetree are quite complex, so I sincerely doubt 
> that it cannot do the job.  You've asked no questions, nor have you 
> described any problems you have encountered.

There where no problems from the perspective of understanding what it 
did or how to use it.
It was just that auto generating of the decodetree seemed more then a 
simple task but a rather elaborated one, since we needed to identify 
common operand style instructions, group similar instruction conflicting 
encodings, etc. And when comparing to the ease of automating the 
creation of the decoding trees, seemed much more complex.

>
> The example is not especially enlightening because you don't show the 
> macro definitions, or the expansion.  Have you a link to a git repo 
> that you can share?
I do have. Please allow me a few days to properly clean it. Considering, 
I wanted to get your opinion before of a greater commitment to the 
solution, it is still in a prototype stage.

Cupertino

_______________________________________________
linux-snps-arc mailing list
linux-snps-arc@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-snps-arc

Re: QEmu ARC port - decoder implementation feedback

[Cupertino Miranda]

Hi Richard

> Why would you be maintaining another description?  Your approach below 
> with the simple recursive algorithm appears to be no different.

We initially considered to drop our tables completely replacing it by 
decodetree.

>
>> Also that decodetree alone would not allow us to properly disassembly
>> code, still requiring to keep the initial structure.
>
> Why is that?

By disassembly I am referring to the pretty-print of the instructions 
when using "-d in_asm". Our tables contain information for printing as 
they are the ones used by bintutils assembler.

>
> The current uses of decodetree are quite complex, so I sincerely doubt 
> that it cannot do the job.  You've asked no questions, nor have you 
> described any problems you have encountered.

There where no problems from the perspective of understanding what it 
did or how to use it.
It was just that auto generating of the decodetree seemed more then a 
simple task but a rather elaborated one, since we needed to identify 
common operand style instructions, group similar instruction conflicting 
encodings, etc. And when comparing to the ease of automating the 
creation of the decoding trees, seemed much more complex.

>
> The example is not especially enlightening because you don't show the 
> macro definitions, or the expansion.  Have you a link to a git repo 
> that you can share?
I do have. Please allow me a few days to properly clean it. Considering, 
I wanted to get your opinion before of a greater commitment to the 
solution, it is still in a prototype stage.

Cupertino