generated decoder code question

generated decoder code question

[Chuan-Hua Chang]

In the utils-sim.scm file, the "-gen-decode-insn-entry" function has
the following lines:

		     ; Generate code to check that all of the opcode bits for this insn match
		     indent "    if (("
		     (if (adata-integral-insn? CURRENT-ARCH) "entire_insn" "base_insn")
		     " & 0x" (number->hex (insn-base-mask insn)) ") == 0x"
(number->hex (insn-value insn)) ")\n"
		     indent "      { itype = " (gen-cpu-insn-enum (current-cpu) insn) ";"
		     (if (with-scache?)
			 (if fn?
			     (string-append " @prefix@_extract_" fmt-name " (this,
current_cpu, pc, base_insn, entire_insn); goto done;")
			     (string-append " goto extract_" fmt-name ";"))
			 " goto done;")
		     " }\n"
		     indent "    " (-gen-decode-default-entry indent invalid-insn fn?)))))
)

It generates an IF-statement to check the opcode again inside the case
statement before doing the real extraction. This seems really
redundant and make the decoder inefficient.

I am wondering why this is needed here. Could someone help to explain
the reasoning?

When looking at the M32R decode function, the IF-statement is absent
from the decoder code.  This lets me wonder that if there is a way to
remove this redundant IF-statement check in the CGEN flow.

Thanks.

Re: generated decoder code question

[Frank Ch. Eigler]

Hi -

> In the utils-sim.scm file, the "-gen-decode-insn-entry" function has
> the following lines:
> 		     ; Generate code to check that all of the opcode bits 
> 		     for this insn match
> [...]
> It generates an IF-statement to check the opcode again inside the case
> statement before doing the real extraction. This seems really
> redundant 


I believe that this check is done because the switch statement by
itself is not necessarily sufficient.  The switch may simply
disambiguate the instructions (so no two candidate instructions fall
into the same switch case), but that could leave some additional
decodeable bits.  Those bits would need to be tested to tell apart the
remaining candidate instruction from illegal opcodes.

> and make the decoder inefficient.

Do you have a sense of how frequently such a test is completely
redundant, and how much additional time this test takes?

- FChE

Re: generated decoder code question

[Dave Brolley]

Frank Ch. Eigler wrote:

>Hi -
>
>  
>
>>In the utils-sim.scm file, the "-gen-decode-insn-entry" function has
>>the following lines:
>>		     ; Generate code to check that all of the opcode bits 
>>		     for this insn match
>>[...]
>>It generates an IF-statement to check the opcode again inside the case
>>statement before doing the real extraction. This seems really
>>redundant 
>>    
>>
>
>
>I believe that this check is done because the switch statement by
>itself is not necessarily sufficient.  The switch may simply
>disambiguate the instructions (so no two candidate instructions fall
>into the same switch case), but that could leave some additional
>decodeable bits.  Those bits would need to be tested to tell apart the
>remaining candidate instruction from illegal opcodes.
>  
>
This is correct. The switch only disambiguates the valid insns. 
Sometimes when a case has been reduced to only one insn, there are still 
some opcodes bits which have not been tested. In this case only, the 
additional test is generated.

>  
>
>>and make the decoder inefficient.
>>    
>>
>
>Do you have a sense of how frequently such a test is completely
>redundant, and how much additional time this test takes?
>  
>
Please point out any cases where the test is not needed and I will see 
if I can eliminate it in those cases.

Thanks,
Dave

Re: generated decoder code question

[Chuan-Hua Chang]

>
> Please point out any cases where the test is not needed and I will see
> if I can eliminate it in those cases.
>

Using sid/component/cgen-cpu/mt/mt-decode.cxx as an example:

---------------------------------------------------------------------------------------------
void
mt_scache::decode (mt_cpu* current_cpu, PCADDR pc, mt_insn_word
base_insn, mt_insn_word entire_insn)
{
  /* Result of decoder.  */
  MT_INSN_TYPE itype;

  {
    mt_insn_word insn = base_insn;

    {
      unsigned int val = (((insn >> 24) & (255 << 0)));
      switch (val)
      {
      case 0 :
        if ((entire_insn & 0xff000fff) == 0x0)
          { itype = MT_INSN_ADD; mt_extract_sfmt_add (this,
current_cpu, pc, base_insn, entire_insn); goto done; }
        itype = MT_INSN_X_INVALID; mt_extract_sfmt_empty (this,
current_cpu, pc, base_insn, entire_insn); goto done;
      case 1 :
        if ((entire_insn & 0xff000000) == 0x1000000)
          { itype = MT_INSN_ADDI; mt_extract_sfmt_addi (this,
current_cpu, pc, base_insn, entire_insn); goto done; }
        itype = MT_INSN_X_INVALID; mt_extract_sfmt_empty (this,
current_cpu, pc, base_insn, entire_insn); goto done;
      case 2 :
        if ((entire_insn & 0xff000fff) == 0x2000000)
          { itype = MT_INSN_ADDU; mt_extract_sfmt_addu (this,
current_cpu, pc, base_insn, entire_insn); goto done; }
        itype = MT_INSN_X_INVALID; mt_extract_sfmt_empty (this,
current_cpu, pc, base_insn, entire_insn); goto done;
      case 3 :
        if ((entire_insn & 0xff000000) == 0x3000000)
          { itype = MT_INSN_ADDUI; mt_extract_sfmt_addui (this,
current_cpu, pc, base_insn, entire_insn); goto done; }
        itype = MT_INSN_X_INVALID; mt_extract_sfmt_empty (this,
current_cpu, pc, base_insn, entire_insn); goto done;
      case 4 :
        if ((entire_insn & 0xff000fff) == 0x4000000)
          { itype = MT_INSN_SUB; mt_extract_sfmt_add (this,
current_cpu, pc, base_insn, entire_insn); goto done; }
        itype = MT_INSN_X_INVALID; mt_extract_sfmt_empty (this,
current_cpu, pc, base_insn, entire_insn); goto done;
      case 5 :
        if ((entire_insn & 0xff000000) == 0x5000000)
          { itype = MT_INSN_SUBI; mt_extract_sfmt_addi (this,
current_cpu, pc, base_insn, entire_insn); goto done; }
        itype = MT_INSN_X_INVALID; mt_extract_sfmt_empty (this,
current_cpu, pc, base_insn, entire_insn); goto done;
---------------------------------------------------------------------------------------------------

The top level switch/case statement tests the upper 8 bits of the
instruction ((>> 24) & 255). For case 0, it is true that additional
lower 12 bits are being tested (& 0xff000fff). However, for case 1, no
additional bits are being tested (& 0xff000000), this is where the
redundancy comes in. I would expect CGEN to detect this case and not
generate unnecessary IF checking here. (e.g similar to M32R code in
the CGEN release.)


>>
>> When looking at the M32R decode function, the IF-statement is absent
>> from the decoder code.  This lets me wonder that if there is a way to
>> remove this redundant IF-statement check in the CGEN flow.
>>
>This is likely a case where all of the decodable bits have already been
>tested in reaching that particular case.
>

May I ask that if the released M32R code is generated by the current
CGEN utils-sim.scm file or generated by another version or hand-edited
to remove the IF checking statement mentioned in my question? I am
asking this since from the the "-gen-decode-insn-entry" function I do
not see any conditional construct to control the generation of the IF
checking code. It seems that the IF checking code is always generated.
I have also re-generated the M32R simulator to confirm my guess, and
the newly-generated M32R decode function DOES have the IF checking
statement now. Am I missing something?

>
>Do you have a sense of how frequently such a test is completely
>redundant, and how much additional time this test takes?
>

For high locality code, the decode function may not be invoked that
frequently, but for low locality code, the decode function will be
invoked a lot more often. it seems that this kind of redundancy should
be made as few as possible.

Thanks for your help.

Re: generated decoder code question

[Dave Brolley]

Chuan-Hua Chang wrote:

>
> When looking at the M32R decode function, the IF-statement is absent
> from the decoder code.  This lets me wonder that if there is a way to
> remove this redundant IF-statement check in the CGEN flow.
>
This is likely a case where all of the decodable bits have already been 
tested in reaching that particular case.

Dave