[patch][rfa] Ordering insns in hash chain for cgen disassemblers

[patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Dave Brolley]

[-- Attachment #1: Type: text/plain, Size: 1650 bytes --]

Hi,

Currently insns are added to the chains of the hash table in the
disassembler in the order in which they appear in the .cpu file. Thus,
resolution of insns which are a special case of another must be
managed by carefully defining then in the correct order. The insns are
also parsed in the order in which they appear and this is important in
cases where an operand in the assembler input might be successfully
parsed as more than on ecgen operand (e.g. register names are
successfully parsed as immediates). There is an impass, however, when
the order in which insns need to be parsed is not the same as the
order in which decoding must be attempted.

I have run into such a case where an operand of an insn may be a
register name or an immediate. One particular register is forbidden,
however, and when the bits representing that register appear in the
field of the insn, it signifies that the operand is really an
immediate value which follows the insn. Thus the operand must be
parsed as a register name first, but decoding must attempt it as an
immediate first.

The problem may be solved by automating the order in which the insns
are placed into the hash chains in the disassembler. By ordering insns
iby the number of decoding bits in decreasing order, we can assure
that an insn which is a special case of another wil be attempted
first, regardless of the order in which they appear in the .cpu file.
This is the same ordering which would have been required manually up
until now, so no existing ports should be affected.

I have tested the attached patch on m32r (sid), fr30 and two internal
ports. Requesting approval to commit.

Dave

[-- Attachment #2: dis-sort.patch.txt --]
[-- Type: text/plain, Size: 3768 bytes --]

Index: opcodes/cgen-dis.c
===================================================================
RCS file: /cvs/src/src/opcodes/cgen-dis.c,v
retrieving revision 1.5
diff -c -p -r1.5 cgen-dis.c
*** opcodes/cgen-dis.c	2001/09/19 17:40:28	1.5
--- opcodes/cgen-dis.c	2001/11/12 20:10:55
***************
*** 30,36 ****
  static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
  static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
  static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
!      
  /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
  
     COUNT is the number of elements in INSNS.
--- 30,87 ----
  static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
  static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
  static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
! 
! /* Return the number of decodable bits in this insn.  */
! static int
! count_decodable_bits (insn)
!   const CGEN_INSN *insn;
! {
!   unsigned mask = CGEN_INSN_BASE_MASK (insn);
!   int bits = 0;
!   int m;
!   for (m = 1; m != 0; m <<= 1)
!     {
!       if (mask & m)
! 	++bits;
!     }
!   return bits;
! }
! 
! /* Add an instruction to the hash chain.  */     
! static void
! add_insn_to_hash_chain (hentbuf, insn, htable, hash)
!      CGEN_INSN_LIST *hentbuf;
!      const CGEN_INSN *insn;
!      CGEN_INSN_LIST **htable;
!      unsigned int hash;
! {
!   CGEN_INSN_LIST *current_buf;
!   CGEN_INSN_LIST *previous_buf;
!   int insn_decodable_bits;
! 
!   /* Add insns sorted by the number of decodable bits, in decreasing order.
!      This ensures that any insn which is a special case of another will be
!      checked first.  */
!   insn_decodable_bits = count_decodable_bits (insn);
!   previous_buf = NULL;
!   for (current_buf = htable[hash]; current_buf != NULL;
!        current_buf = current_buf->next)
!     {
!       int current_decodable_bits = count_decodable_bits (current_buf->insn);
!       if (insn_decodable_bits >= current_decodable_bits)
! 	break;
!       previous_buf = current_buf;
!     }
! 
!   /* Now insert the new insn.  */
!   hentbuf->insn = insn;
!   hentbuf->next = current_buf;
!   if (previous_buf == NULL)
!     htable[hash] = hentbuf;
!   else
!     previous_buf->next = hentbuf;
! }
! 
  /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
  
     COUNT is the number of elements in INSNS.
*************** hash_insn_array (cd, insns, count, entsi
*** 74,82 ****
  		    CGEN_INSN_MASK_BITSIZE (insn),
  		    big_p);
        hash = (* cd->dis_hash) (buf, value);
!       hentbuf->next = htable[hash];
!       hentbuf->insn = insn;
!       htable[hash] = hentbuf;
      }
  
    return hentbuf;
--- 125,131 ----
  		    CGEN_INSN_MASK_BITSIZE (insn),
  		    big_p);
        hash = (* cd->dis_hash) (buf, value);
!       add_insn_to_hash_chain (hentbuf, insn, htable, hash);
      }
  
    return hentbuf;
*************** hash_insn_list (cd, insns, htable, hentb
*** 114,122 ****
  		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
  		   big_p);
        hash = (* cd->dis_hash) (buf, value);
!       hentbuf->next = htable [hash];
!       hentbuf->insn = ilist->insn;
!       htable [hash] = hentbuf;
      }
  
    return hentbuf;
--- 163,169 ----
  		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
  		   big_p);
        hash = (* cd->dis_hash) (buf, value);
!       add_insn_to_hash_chain (hentbuf, ilist->insn, htable, hash);
      }
  
    return hentbuf;

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers -- committed.

[Dave Brolley]

Approved by fche and committed. Let me know if there are any problems.

Dave

Dave Brolley wrote:

>Hi,
>
>Currently insns are added to the chains of the hash table in the
>disassembler in the order in which they appear in the .cpu file. Thus,
>resolution of insns which are a special case of another must be
>managed by carefully defining then in the correct order. The insns are
>also parsed in the order in which they appear and this is important in
>cases where an operand in the assembler input might be successfully
>parsed as more than on ecgen operand (e.g. register names are
>successfully parsed as immediates). There is an impass, however, when
>the order in which insns need to be parsed is not the same as the
>order in which decoding must be attempted.
>
>I have run into such a case where an operand of an insn may be a
>register name or an immediate. One particular register is forbidden,
>however, and when the bits representing that register appear in the
>field of the insn, it signifies that the operand is really an
>immediate value which follows the insn. Thus the operand must be
>parsed as a register name first, but decoding must attempt it as an
>immediate first.
>
>The problem may be solved by automating the order in which the insns
>are placed into the hash chains in the disassembler. By ordering insns
>iby the number of decoding bits in decreasing order, we can assure
>that an insn which is a special case of another wil be attempted
>first, regardless of the order in which they appear in the .cpu file.
>This is the same ordering which would have been required manually up
>until now, so no existing ports should be affected.
>
>I have tested the attached patch on m32r (sid), fr30 and two internal
>ports. Requesting approval to commit.
>
>Dave
>
>
>------------------------------------------------------------------------
>
>Index: opcodes/cgen-dis.c
>===================================================================
>RCS file: /cvs/src/src/opcodes/cgen-dis.c,v
>retrieving revision 1.5
>diff -c -p -r1.5 cgen-dis.c
>*** opcodes/cgen-dis.c	2001/09/19 17:40:28	1.5
>--- opcodes/cgen-dis.c	2001/11/12 20:10:55
>***************
>*** 30,36 ****
>  static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
>  static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
>  static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
>!      
>  /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
>  
>     COUNT is the number of elements in INSNS.
>--- 30,87 ----
>  static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
>  static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
>  static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
>! 
>! /* Return the number of decodable bits in this insn.  */
>! static int
>! count_decodable_bits (insn)
>!   const CGEN_INSN *insn;
>! {
>!   unsigned mask = CGEN_INSN_BASE_MASK (insn);
>!   int bits = 0;
>!   int m;
>!   for (m = 1; m != 0; m <<= 1)
>!     {
>!       if (mask & m)
>! 	++bits;
>!     }
>!   return bits;
>! }
>! 
>! /* Add an instruction to the hash chain.  */     
>! static void
>! add_insn_to_hash_chain (hentbuf, insn, htable, hash)
>!      CGEN_INSN_LIST *hentbuf;
>!      const CGEN_INSN *insn;
>!      CGEN_INSN_LIST **htable;
>!      unsigned int hash;
>! {
>!   CGEN_INSN_LIST *current_buf;
>!   CGEN_INSN_LIST *previous_buf;
>!   int insn_decodable_bits;
>! 
>!   /* Add insns sorted by the number of decodable bits, in decreasing order.
>!      This ensures that any insn which is a special case of another will be
>!      checked first.  */
>!   insn_decodable_bits = count_decodable_bits (insn);
>!   previous_buf = NULL;
>!   for (current_buf = htable[hash]; current_buf != NULL;
>!        current_buf = current_buf->next)
>!     {
>!       int current_decodable_bits = count_decodable_bits (current_buf->insn);
>!       if (insn_decodable_bits >= current_decodable_bits)
>! 	break;
>!       previous_buf = current_buf;
>!     }
>! 
>!   /* Now insert the new insn.  */
>!   hentbuf->insn = insn;
>!   hentbuf->next = current_buf;
>!   if (previous_buf == NULL)
>!     htable[hash] = hentbuf;
>!   else
>!     previous_buf->next = hentbuf;
>! }
>! 
>  /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
>  
>     COUNT is the number of elements in INSNS.
>*************** hash_insn_array (cd, insns, count, entsi
>*** 74,82 ****
>  		    CGEN_INSN_MASK_BITSIZE (insn),
>  		    big_p);
>        hash = (* cd->dis_hash) (buf, value);
>!       hentbuf->next = htable[hash];
>!       hentbuf->insn = insn;
>!       htable[hash] = hentbuf;
>      }
>  
>    return hentbuf;
>--- 125,131 ----
>  		    CGEN_INSN_MASK_BITSIZE (insn),
>  		    big_p);
>        hash = (* cd->dis_hash) (buf, value);
>!       add_insn_to_hash_chain (hentbuf, insn, htable, hash);
>      }
>  
>    return hentbuf;
>*************** hash_insn_list (cd, insns, htable, hentb
>*** 114,122 ****
>  		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
>  		   big_p);
>        hash = (* cd->dis_hash) (buf, value);
>!       hentbuf->next = htable [hash];
>!       hentbuf->insn = ilist->insn;
>!       htable [hash] = hentbuf;
>      }
>  
>    return hentbuf;
>--- 163,169 ----
>  		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
>  		   big_p);
>        hash = (* cd->dis_hash) (buf, value);
>!       add_insn_to_hash_chain (hentbuf, ilist->insn, htable, hash);
>      }
>  
>    return hentbuf;
>
> dis-sort.patch.txt
>
> Content-Type:
>
> text/plain
> Content-Encoding:
>
> 7bit
>
>

[patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Doug Evans]

Dave Brolley writes:
 > Currently insns are added to the chains of the hash table in the
 > disassembler in the order in which they appear in the .cpu file. Thus,
 > resolution of insns which are a special case of another must be
 > managed by carefully defining then in the correct order. The insns are
 > also parsed in the order in which they appear and this is important in
 > cases where an operand in the assembler input might be successfully
 > parsed as more than on ecgen operand (e.g. register names are
 > successfully parsed as immediates). There is an impass, however, when
 > the order in which insns need to be parsed is not the same as the
 > order in which decoding must be attempted.
 > 
 > I have run into such a case where an operand of an insn may be a
 > register name or an immediate. One particular register is forbidden,
 > however, and when the bits representing that register appear in the
 > field of the insn, it signifies that the operand is really an
 > immediate value which follows the insn. Thus the operand must be
 > parsed as a register name first, but decoding must attempt it as an
 > immediate first.
 > 
 > The problem may be solved by automating the order in which the insns
 > are placed into the hash chains in the disassembler. By ordering insns
 > iby the number of decoding bits in decreasing order, we can assure
 > that an insn which is a special case of another wil be attempted
 > first, regardless of the order in which they appear in the .cpu file.
 > This is the same ordering which would have been required manually up
 > until now, so no existing ports should be affected.

Setting aside the state of the implementation of ifield assertions
(since I don't remember what it is), why wouldn't an ifield assertion
work here?

I'm not saying I disapprove of the patch in principle, just curious
whether you tried that and the results of it.

Studying your patch though, I have some questions.
Are you assuming both insns are on the same hash chain?
[If not, never mind of course.]
If so, is that guaranteed?

Is basing the sort strictly on the number of decodable bit sufficient?

Also, style nit: I hate the absence of a blank line between the comment
introducing the function and the function definition.
Another style note while I'm on it.  Boy do I hate the proliferation
of "pretty aligned code".

int                         a;
some_long_type_definition_t b;

(or see the static fn decls at the top of cgen-dis.c)

puhleeze. :-(

 > Index: opcodes/cgen-dis.c
 > ===================================================================
 > RCS file: /cvs/src/src/opcodes/cgen-dis.c,v
 > retrieving revision 1.5
 > diff -c -p -r1.5 cgen-dis.c
 > *** opcodes/cgen-dis.c	2001/09/19 17:40:28	1.5
 > --- opcodes/cgen-dis.c	2001/11/12 20:10:55
 > ***************
 > *** 30,36 ****
 >   static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
 >   static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
 >   static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
 > !      
 >   /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
 >   
 >      COUNT is the number of elements in INSNS.
 > --- 30,87 ----
 >   static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
 >   static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
 >   static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
 > ! 
 > ! /* Return the number of decodable bits in this insn.  */
 > ! static int
 > ! count_decodable_bits (insn)
 > !   const CGEN_INSN *insn;
 > ! {
 > !   unsigned mask = CGEN_INSN_BASE_MASK (insn);
 > !   int bits = 0;
 > !   int m;
 > !   for (m = 1; m != 0; m <<= 1)
 > !     {
 > !       if (mask & m)
 > ! 	++bits;
 > !     }
 > !   return bits;
 > ! }
 > ! 
 > ! /* Add an instruction to the hash chain.  */     
 > ! static void
 > ! add_insn_to_hash_chain (hentbuf, insn, htable, hash)
 > !      CGEN_INSN_LIST *hentbuf;
 > !      const CGEN_INSN *insn;
 > !      CGEN_INSN_LIST **htable;
 > !      unsigned int hash;
 > ! {
 > !   CGEN_INSN_LIST *current_buf;
 > !   CGEN_INSN_LIST *previous_buf;
 > !   int insn_decodable_bits;
 > ! 
 > !   /* Add insns sorted by the number of decodable bits, in decreasing order.
 > !      This ensures that any insn which is a special case of another will be
 > !      checked first.  */
 > !   insn_decodable_bits = count_decodable_bits (insn);
 > !   previous_buf = NULL;
 > !   for (current_buf = htable[hash]; current_buf != NULL;
 > !        current_buf = current_buf->next)
 > !     {
 > !       int current_decodable_bits = count_decodable_bits (current_buf->insn);
 > !       if (insn_decodable_bits >= current_decodable_bits)
 > ! 	break;
 > !       previous_buf = current_buf;
 > !     }
 > ! 
 > !   /* Now insert the new insn.  */
 > !   hentbuf->insn = insn;
 > !   hentbuf->next = current_buf;
 > !   if (previous_buf == NULL)
 > !     htable[hash] = hentbuf;
 > !   else
 > !     previous_buf->next = hentbuf;
 > ! }
 > ! 
 >   /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
 >   
 >      COUNT is the number of elements in INSNS.
 > *************** hash_insn_array (cd, insns, count, entsi
 > *** 74,82 ****
 >   		    CGEN_INSN_MASK_BITSIZE (insn),
 >   		    big_p);
 >         hash = (* cd->dis_hash) (buf, value);
 > !       hentbuf->next = htable[hash];
 > !       hentbuf->insn = insn;
 > !       htable[hash] = hentbuf;
 >       }
 >   
 >     return hentbuf;
 > --- 125,131 ----
 >   		    CGEN_INSN_MASK_BITSIZE (insn),
 >   		    big_p);
 >         hash = (* cd->dis_hash) (buf, value);
 > !       add_insn_to_hash_chain (hentbuf, insn, htable, hash);
 >       }
 >   
 >     return hentbuf;
 > *************** hash_insn_list (cd, insns, htable, hentb
 > *** 114,122 ****
 >   		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
 >   		   big_p);
 >         hash = (* cd->dis_hash) (buf, value);
 > !       hentbuf->next = htable [hash];
 > !       hentbuf->insn = ilist->insn;
 > !       htable [hash] = hentbuf;
 >       }
 >   
 >     return hentbuf;
 > --- 163,169 ----
 >   		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
 >   		   big_p);
 >         hash = (* cd->dis_hash) (buf, value);
 > !       add_insn_to_hash_chain (hentbuf, ilist->insn, htable, hash);
 >       }
 >   
 >     return hentbuf;

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Dave Brolley]

Doug Evans wrote:

>
>Setting aside the state of the implementation of ifield assertions
>(since I don't remember what it is), why wouldn't an ifield assertion
>work here?
>
Yes, I specified them fully and found that they are ignored  :-(

>I'm not saying I disapprove of the patch in principle, just curious
>whether you tried that and the results of it.
>
>Studying your patch though, I have some questions.
>Are you assuming both insns are on the same hash chain?
>[If not, never mind of course.]
>If so, is that guaranteed?
>
Nope it's not guaranteed. If two such insns end up on different hash 
chains, then even better. The ambiguity would be removed at a higher 
level. The solution presented by my patch removes dependence on any 
particular hash function by allowing the insns to be resolved even if 
they do end up on the same hash chain.

>Is basing the sort strictly on the number of decodable bit sufficient?
>
I think that basing the sort on the number of decodable bits is 
sufficient becase the decodable bits of the more general insn will be a 
proper subset of the decodable bits if the other. Thus the number of 
decodable bits will be less than that of the less general insn. Sorting 
based on the number of decodable bits will therefore guarantee the 
relative ordering  between the conflicting insns.

>Also, style nit: I hate the absence of a blank line between the comment
>introducing the function and the function definition.
>
Feel free to add one if you like.

>Another style note while I'm on it.  Boy do I hate the proliferation
>of "pretty aligned code".
>
>int                         a;
>some_long_type_definition_t b;
>
I assume you're referring to previous code I may have written? I didn't 
do this in this patch, although I personally do like this style.

>(or see the static fn decls at the top of cgen-dis.c)
>
That was there already.

>puhleeze. :-(
>
Thank you  :-)

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Doug Evans]

Dave Brolley writes:
 > Doug Evans wrote:
 > >Setting aside the state of the implementation of ifield assertions
 > >(since I don't remember what it is), why wouldn't an ifield assertion
 > >work here?
 > >
 > Yes, I specified them fully and found that they are ignored  :-(

Then a todo item (I saw a mention of this in the docs).  Wanna do it?
That's a more preferable patch than the current one (I think!).

I'm not going to argue for it's removal but fwiw it slightly bothers me.
I worry it's just going to cause headaches.
[While not being the only cause of the worry, question: how will this
sort play with ifield assertion support when it's added, and the
user's expectation that things are picked based on order in the file.
Maybe you could choose to not sort insns with ifield assertions, I guess.
But then things would be getting a bit convoluted.]

 > >(or see the static fn decls at the top of cgen-dis.c)
 > >
 > That was there already.

No claim was made that you had written it (though I can see that
one might infer that), and yes I realize it was there already.

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Dave Brolley]

Doug Evans wrote:

>Dave Brolley writes:
> > Doug Evans wrote:
> > >Setting aside the state of the implementation of ifield assertions
> > >(since I don't remember what it is), why wouldn't an ifield assertion
> > >work here?
> > >
> > Yes, I specified them fully and found that they are ignored  :-(
>
>Then a todo item (I saw a mention of this in the docs).  Wanna do it?
>That's a more preferable patch than the current one (I think!).
>
Yes, I agree. As usual, however, my shedule is tight.

>I'm not going to argue for it's removal but fwiw it slightly bothers me.
>I worry it's just going to cause headaches.
>[While not being the only cause of the worry, question: how will this
>sort play with ifield assertion support when it's added, and the
>user's expectation that things are picked based on order in the file.
>Maybe you could choose to not sort insns with ifield assertions, I guess.
>But then things would be getting a bit convoluted.]
>
For any existing port which does not already specify the insns in this 
order, the less general insn will never be found. I only needed to add 
this because the order I needed for parsing was not the order I needed 
for decoding. I don't think that there will be any problems.

Glad to see that you're still active and interested in CGEN!

Dave

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Frank Ch. Eigler]

dje wrote:

: [...]
: I'm not going to argue for it's removal but fwiw it slightly bothers me.
: I worry it's just going to cause headaches.

Yeah, I worried too, for a little while.


: [While not being the only cause of the worry, question: how will this
: sort play with ifield assertion support when it's added, 

What value do you see for the ifield-assertion mechanism (the "(andif
(eq FOO 0) ...)"  clauses in derived-operands, right?), beyond what
the encoding fields ("+ (f-FOO 0) ...") can/should provide?  As it is,
RTL-rich code appears legal in too many contexts.


: and the user's expectation that things are picked based on order in
: the file.  [...]

IMO, such expectations are just desperate measures to try to get
around some cgen limitations.  As those limitations start to disappear
(and brolley is going to work on one of the most annoying: insn
encoding special cases), these measures will no longer be needed.

(Thanks for still keeping an eye on cgen!)


- FChE

[patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Dave Brolley]

Hi,

Currently insns are added to the chains of the hash table in the
disassembler in the order in which they appear in the .cpu file. Thus,
resolution of insns which are a special case of another must be
managed by carefully defining then in the correct order. The insns are
also parsed in the order in which they appear and this is important in
cases where an operand in the assembler input might be successfully
parsed as more than on ecgen operand (e.g. register names are
successfully parsed as immediates). There is an impass, however, when
the order in which insns need to be parsed is not the same as the
order in which decoding must be attempted.

I have run into such a case where an operand of an insn may be a
register name or an immediate. One particular register is forbidden,
however, and when the bits representing that register appear in the
field of the insn, it signifies that the operand is really an
immediate value which follows the insn. Thus the operand must be
parsed as a register name first, but decoding must attempt it as an
immediate first.

The problem may be solved by automating the order in which the insns
are placed into the hash chains in the disassembler. By ordering insns
iby the number of decoding bits in decreasing order, we can assure
that an insn which is a special case of another wil be attempted
first, regardless of the order in which they appear in the .cpu file.
This is the same ordering which would have been required manually up
until now, so no existing ports should be affected.

I have tested the attached patch on m32r (sid), fr30 and two internal
ports. Requesting approval to commit.

Dave

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers -- committed.

[Dave Brolley]

Approved by fche and committed. Let me know if there are any problems.

Dave

Dave Brolley wrote:

>Hi,
>
>Currently insns are added to the chains of the hash table in the
>disassembler in the order in which they appear in the .cpu file. Thus,
>resolution of insns which are a special case of another must be
>managed by carefully defining then in the correct order. The insns are
>also parsed in the order in which they appear and this is important in
>cases where an operand in the assembler input might be successfully
>parsed as more than on ecgen operand (e.g. register names are
>successfully parsed as immediates). There is an impass, however, when
>the order in which insns need to be parsed is not the same as the
>order in which decoding must be attempted.
>
>I have run into such a case where an operand of an insn may be a
>register name or an immediate. One particular register is forbidden,
>however, and when the bits representing that register appear in the
>field of the insn, it signifies that the operand is really an
>immediate value which follows the insn. Thus the operand must be
>parsed as a register name first, but decoding must attempt it as an
>immediate first.
>
>The problem may be solved by automating the order in which the insns
>are placed into the hash chains in the disassembler. By ordering insns
>iby the number of decoding bits in decreasing order, we can assure
>that an insn which is a special case of another wil be attempted
>first, regardless of the order in which they appear in the .cpu file.
>This is the same ordering which would have been required manually up
>until now, so no existing ports should be affected.
>
>I have tested the attached patch on m32r (sid), fr30 and two internal
>ports. Requesting approval to commit.
>
>Dave
>
>
>------------------------------------------------------------------------
>
>Index: opcodes/cgen-dis.c
>===================================================================
>RCS file: /cvs/src/src/opcodes/cgen-dis.c,v
>retrieving revision 1.5
>diff -c -p -r1.5 cgen-dis.c
>*** opcodes/cgen-dis.c	2001/09/19 17:40:28	1.5
>--- opcodes/cgen-dis.c	2001/11/12 20:10:55
>***************
>*** 30,36 ****
>  static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
>  static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
>  static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
>!      
>  /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
>  
>     COUNT is the number of elements in INSNS.
>--- 30,87 ----
>  static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
>  static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
>  static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
>! 
>! /* Return the number of decodable bits in this insn.  */
>! static int
>! count_decodable_bits (insn)
>!   const CGEN_INSN *insn;
>! {
>!   unsigned mask = CGEN_INSN_BASE_MASK (insn);
>!   int bits = 0;
>!   int m;
>!   for (m = 1; m != 0; m <<= 1)
>!     {
>!       if (mask & m)
>! 	++bits;
>!     }
>!   return bits;
>! }
>! 
>! /* Add an instruction to the hash chain.  */     
>! static void
>! add_insn_to_hash_chain (hentbuf, insn, htable, hash)
>!      CGEN_INSN_LIST *hentbuf;
>!      const CGEN_INSN *insn;
>!      CGEN_INSN_LIST **htable;
>!      unsigned int hash;
>! {
>!   CGEN_INSN_LIST *current_buf;
>!   CGEN_INSN_LIST *previous_buf;
>!   int insn_decodable_bits;
>! 
>!   /* Add insns sorted by the number of decodable bits, in decreasing order.
>!      This ensures that any insn which is a special case of another will be
>!      checked first.  */
>!   insn_decodable_bits = count_decodable_bits (insn);
>!   previous_buf = NULL;
>!   for (current_buf = htable[hash]; current_buf != NULL;
>!        current_buf = current_buf->next)
>!     {
>!       int current_decodable_bits = count_decodable_bits (current_buf->insn);
>!       if (insn_decodable_bits >= current_decodable_bits)
>! 	break;
>!       previous_buf = current_buf;
>!     }
>! 
>!   /* Now insert the new insn.  */
>!   hentbuf->insn = insn;
>!   hentbuf->next = current_buf;
>!   if (previous_buf == NULL)
>!     htable[hash] = hentbuf;
>!   else
>!     previous_buf->next = hentbuf;
>! }
>! 
>  /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
>  
>     COUNT is the number of elements in INSNS.
>*************** hash_insn_array (cd, insns, count, entsi
>*** 74,82 ****
>  		    CGEN_INSN_MASK_BITSIZE (insn),
>  		    big_p);
>        hash = (* cd->dis_hash) (buf, value);
>!       hentbuf->next = htable[hash];
>!       hentbuf->insn = insn;
>!       htable[hash] = hentbuf;
>      }
>  
>    return hentbuf;
>--- 125,131 ----
>  		    CGEN_INSN_MASK_BITSIZE (insn),
>  		    big_p);
>        hash = (* cd->dis_hash) (buf, value);
>!       add_insn_to_hash_chain (hentbuf, insn, htable, hash);
>      }
>  
>    return hentbuf;
>*************** hash_insn_list (cd, insns, htable, hentb
>*** 114,122 ****
>  		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
>  		   big_p);
>        hash = (* cd->dis_hash) (buf, value);
>!       hentbuf->next = htable [hash];
>!       hentbuf->insn = ilist->insn;
>!       htable [hash] = hentbuf;
>      }
>  
>    return hentbuf;
>--- 163,169 ----
>  		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
>  		   big_p);
>        hash = (* cd->dis_hash) (buf, value);
>!       add_insn_to_hash_chain (hentbuf, ilist->insn, htable, hash);
>      }
>  
>    return hentbuf;
>
> dis-sort.patch.txt
>
> Content-Type:
>
> text/plain
> Content-Encoding:
>
> 7bit
>
>

[patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Doug Evans]

Dave Brolley writes:
 > Currently insns are added to the chains of the hash table in the
 > disassembler in the order in which they appear in the .cpu file. Thus,
 > resolution of insns which are a special case of another must be
 > managed by carefully defining then in the correct order. The insns are
 > also parsed in the order in which they appear and this is important in
 > cases where an operand in the assembler input might be successfully
 > parsed as more than on ecgen operand (e.g. register names are
 > successfully parsed as immediates). There is an impass, however, when
 > the order in which insns need to be parsed is not the same as the
 > order in which decoding must be attempted.
 > 
 > I have run into such a case where an operand of an insn may be a
 > register name or an immediate. One particular register is forbidden,
 > however, and when the bits representing that register appear in the
 > field of the insn, it signifies that the operand is really an
 > immediate value which follows the insn. Thus the operand must be
 > parsed as a register name first, but decoding must attempt it as an
 > immediate first.
 > 
 > The problem may be solved by automating the order in which the insns
 > are placed into the hash chains in the disassembler. By ordering insns
 > iby the number of decoding bits in decreasing order, we can assure
 > that an insn which is a special case of another wil be attempted
 > first, regardless of the order in which they appear in the .cpu file.
 > This is the same ordering which would have been required manually up
 > until now, so no existing ports should be affected.

Setting aside the state of the implementation of ifield assertions
(since I don't remember what it is), why wouldn't an ifield assertion
work here?

I'm not saying I disapprove of the patch in principle, just curious
whether you tried that and the results of it.

Studying your patch though, I have some questions.
Are you assuming both insns are on the same hash chain?
[If not, never mind of course.]
If so, is that guaranteed?

Is basing the sort strictly on the number of decodable bit sufficient?

Also, style nit: I hate the absence of a blank line between the comment
introducing the function and the function definition.
Another style note while I'm on it.  Boy do I hate the proliferation
of "pretty aligned code".

int                         a;
some_long_type_definition_t b;

(or see the static fn decls at the top of cgen-dis.c)

puhleeze. :-(

 > Index: opcodes/cgen-dis.c
 > ===================================================================
 > RCS file: /cvs/src/src/opcodes/cgen-dis.c,v
 > retrieving revision 1.5
 > diff -c -p -r1.5 cgen-dis.c
 > *** opcodes/cgen-dis.c	2001/09/19 17:40:28	1.5
 > --- opcodes/cgen-dis.c	2001/11/12 20:10:55
 > ***************
 > *** 30,36 ****
 >   static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
 >   static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
 >   static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
 > !      
 >   /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
 >   
 >      COUNT is the number of elements in INSNS.
 > --- 30,87 ----
 >   static CGEN_INSN_LIST *  hash_insn_array      PARAMS ((CGEN_CPU_DESC, const CGEN_INSN *, int, int, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
 >   static CGEN_INSN_LIST *  hash_insn_list       PARAMS ((CGEN_CPU_DESC, const CGEN_INSN_LIST *, CGEN_INSN_LIST **, CGEN_INSN_LIST *));
 >   static void              build_dis_hash_table PARAMS ((CGEN_CPU_DESC));
 > ! 
 > ! /* Return the number of decodable bits in this insn.  */
 > ! static int
 > ! count_decodable_bits (insn)
 > !   const CGEN_INSN *insn;
 > ! {
 > !   unsigned mask = CGEN_INSN_BASE_MASK (insn);
 > !   int bits = 0;
 > !   int m;
 > !   for (m = 1; m != 0; m <<= 1)
 > !     {
 > !       if (mask & m)
 > ! 	++bits;
 > !     }
 > !   return bits;
 > ! }
 > ! 
 > ! /* Add an instruction to the hash chain.  */     
 > ! static void
 > ! add_insn_to_hash_chain (hentbuf, insn, htable, hash)
 > !      CGEN_INSN_LIST *hentbuf;
 > !      const CGEN_INSN *insn;
 > !      CGEN_INSN_LIST **htable;
 > !      unsigned int hash;
 > ! {
 > !   CGEN_INSN_LIST *current_buf;
 > !   CGEN_INSN_LIST *previous_buf;
 > !   int insn_decodable_bits;
 > ! 
 > !   /* Add insns sorted by the number of decodable bits, in decreasing order.
 > !      This ensures that any insn which is a special case of another will be
 > !      checked first.  */
 > !   insn_decodable_bits = count_decodable_bits (insn);
 > !   previous_buf = NULL;
 > !   for (current_buf = htable[hash]; current_buf != NULL;
 > !        current_buf = current_buf->next)
 > !     {
 > !       int current_decodable_bits = count_decodable_bits (current_buf->insn);
 > !       if (insn_decodable_bits >= current_decodable_bits)
 > ! 	break;
 > !       previous_buf = current_buf;
 > !     }
 > ! 
 > !   /* Now insert the new insn.  */
 > !   hentbuf->insn = insn;
 > !   hentbuf->next = current_buf;
 > !   if (previous_buf == NULL)
 > !     htable[hash] = hentbuf;
 > !   else
 > !     previous_buf->next = hentbuf;
 > ! }
 > ! 
 >   /* Subroutine of build_dis_hash_table to add INSNS to the hash table.
 >   
 >      COUNT is the number of elements in INSNS.
 > *************** hash_insn_array (cd, insns, count, entsi
 > *** 74,82 ****
 >   		    CGEN_INSN_MASK_BITSIZE (insn),
 >   		    big_p);
 >         hash = (* cd->dis_hash) (buf, value);
 > !       hentbuf->next = htable[hash];
 > !       hentbuf->insn = insn;
 > !       htable[hash] = hentbuf;
 >       }
 >   
 >     return hentbuf;
 > --- 125,131 ----
 >   		    CGEN_INSN_MASK_BITSIZE (insn),
 >   		    big_p);
 >         hash = (* cd->dis_hash) (buf, value);
 > !       add_insn_to_hash_chain (hentbuf, insn, htable, hash);
 >       }
 >   
 >     return hentbuf;
 > *************** hash_insn_list (cd, insns, htable, hentb
 > *** 114,122 ****
 >   		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
 >   		   big_p);
 >         hash = (* cd->dis_hash) (buf, value);
 > !       hentbuf->next = htable [hash];
 > !       hentbuf->insn = ilist->insn;
 > !       htable [hash] = hentbuf;
 >       }
 >   
 >     return hentbuf;
 > --- 163,169 ----
 >   		   CGEN_INSN_MASK_BITSIZE (ilist->insn),
 >   		   big_p);
 >         hash = (* cd->dis_hash) (buf, value);
 > !       add_insn_to_hash_chain (hentbuf, ilist->insn, htable, hash);
 >       }
 >   
 >     return hentbuf;

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Dave Brolley]

Doug Evans wrote:

>
>Setting aside the state of the implementation of ifield assertions
>(since I don't remember what it is), why wouldn't an ifield assertion
>work here?
>
Yes, I specified them fully and found that they are ignored  :-(

>I'm not saying I disapprove of the patch in principle, just curious
>whether you tried that and the results of it.
>
>Studying your patch though, I have some questions.
>Are you assuming both insns are on the same hash chain?
>[If not, never mind of course.]
>If so, is that guaranteed?
>
Nope it's not guaranteed. If two such insns end up on different hash 
chains, then even better. The ambiguity would be removed at a higher 
level. The solution presented by my patch removes dependence on any 
particular hash function by allowing the insns to be resolved even if 
they do end up on the same hash chain.

>Is basing the sort strictly on the number of decodable bit sufficient?
>
I think that basing the sort on the number of decodable bits is 
sufficient becase the decodable bits of the more general insn will be a 
proper subset of the decodable bits if the other. Thus the number of 
decodable bits will be less than that of the less general insn. Sorting 
based on the number of decodable bits will therefore guarantee the 
relative ordering  between the conflicting insns.

>Also, style nit: I hate the absence of a blank line between the comment
>introducing the function and the function definition.
>
Feel free to add one if you like.

>Another style note while I'm on it.  Boy do I hate the proliferation
>of "pretty aligned code".
>
>int                         a;
>some_long_type_definition_t b;
>
I assume you're referring to previous code I may have written? I didn't 
do this in this patch, although I personally do like this style.

>(or see the static fn decls at the top of cgen-dis.c)
>
That was there already.

>puhleeze. :-(
>
Thank you  :-)

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Doug Evans]

Dave Brolley writes:
 > Doug Evans wrote:
 > >Setting aside the state of the implementation of ifield assertions
 > >(since I don't remember what it is), why wouldn't an ifield assertion
 > >work here?
 > >
 > Yes, I specified them fully and found that they are ignored  :-(

Then a todo item (I saw a mention of this in the docs).  Wanna do it?
That's a more preferable patch than the current one (I think!).

I'm not going to argue for it's removal but fwiw it slightly bothers me.
I worry it's just going to cause headaches.
[While not being the only cause of the worry, question: how will this
sort play with ifield assertion support when it's added, and the
user's expectation that things are picked based on order in the file.
Maybe you could choose to not sort insns with ifield assertions, I guess.
But then things would be getting a bit convoluted.]

 > >(or see the static fn decls at the top of cgen-dis.c)
 > >
 > That was there already.

No claim was made that you had written it (though I can see that
one might infer that), and yes I realize it was there already.

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Dave Brolley]

Doug Evans wrote:

>Dave Brolley writes:
> > Doug Evans wrote:
> > >Setting aside the state of the implementation of ifield assertions
> > >(since I don't remember what it is), why wouldn't an ifield assertion
> > >work here?
> > >
> > Yes, I specified them fully and found that they are ignored  :-(
>
>Then a todo item (I saw a mention of this in the docs).  Wanna do it?
>That's a more preferable patch than the current one (I think!).
>
Yes, I agree. As usual, however, my shedule is tight.

>I'm not going to argue for it's removal but fwiw it slightly bothers me.
>I worry it's just going to cause headaches.
>[While not being the only cause of the worry, question: how will this
>sort play with ifield assertion support when it's added, and the
>user's expectation that things are picked based on order in the file.
>Maybe you could choose to not sort insns with ifield assertions, I guess.
>But then things would be getting a bit convoluted.]
>
For any existing port which does not already specify the insns in this 
order, the less general insn will never be found. I only needed to add 
this because the order I needed for parsing was not the order I needed 
for decoding. I don't think that there will be any problems.

Glad to see that you're still active and interested in CGEN!

Dave

Re: [patch][rfa] Ordering insns in hash chain for cgen disassemblers

[Frank Ch. Eigler]

dje wrote:

: [...]
: I'm not going to argue for it's removal but fwiw it slightly bothers me.
: I worry it's just going to cause headaches.

Yeah, I worried too, for a little while.


: [While not being the only cause of the worry, question: how will this
: sort play with ifield assertion support when it's added, 

What value do you see for the ifield-assertion mechanism (the "(andif
(eq FOO 0) ...)"  clauses in derived-operands, right?), beyond what
the encoding fields ("+ (f-FOO 0) ...") can/should provide?  As it is,
RTL-rich code appears legal in too many contexts.


: and the user's expectation that things are picked based on order in
: the file.  [...]

IMO, such expectations are just desperate measures to try to get
around some cgen limitations.  As those limitations start to disappear
(and brolley is going to work on one of the most annoying: insn
encoding special cases), these measures will no longer be needed.

(Thanks for still keeping an eye on cgen!)


- FChE