Hi,

You may recall a patch which I submitted (and committed, after approval) 
which allowed the decoder for the opcodes-based disassembler to to 
distinguish between insns when the set of decodable bits of one insn is 
a superset of the decodable bits of another.

http://sources.redhat.com/ml/binutils/2001-11/msg00406.html

This situation occurs when one insn is a specialization of another. This 
patch adds the same capability to the decoders used by the cgen-based 
simulators in the sim and sid source trees. While the disassembler 
solution was as simple as sorting a list of insns, the simulators use a 
switch statement which is generated by a tree constructed by a cgen 
application to decode the insns. This patch modifes the cgen application 
which generates the tree.

The patch can be divided into several pieces:

1) The current tree generator calls a function, 
filter-harmlessly-ambiguous-insns, on each tree node before creating 
further sub-trees from the insns remaining in the node. This function 
removes any insn whose decodable bits are a strict superset of another 
insn in the list. It turns out that these insns are not so "harmlessly 
ambiguous" for all ISAs. For example, an architecture may define memory 
access using a base register, but may also define that the base register 
be incremented if a particular register (stack pointer) is used. That 
particular instance (specialization) of the insn would have the same 
decodable bits as the more general insn and would also require a 
particular bit pattern for the field representing the base register. The 
current tree generator removes the specialized insns completely by 
calling "filter-harmlessly-ambiguous-insns". This patch removes that 
call (decode.scm:516) and adds additional code to handle the apparently 
ambiguous insns (decode.scm:574, decode.scm:595). This additional code 
filters identical insns and chooses a specialized insn over its more 
general cousin in the same tree node (The same preference used in the 
previous opcodes patch). The more general insn will still be decodable, 
since it will appear in other tree nodes which do not contain the 
specialized insn.

2) Supporting code for the above is in the new functions in insn.scm 
which perform the filtering. Note that 
"filter-harmlessly-ambiguous-insns" is no longer used, but I did not 
remove it (yet). I will remove it, if no one thinks it could possibly be 
useful.

These changes alone result in a tree generator that works, however, not 
filtering the previously-believed-to-be-harmlessly-ambiguous insns 
exposes a problem in the tree generator which is that, for these insns 
it goes on to attempt to use every single insn bit in an effort to 
distinguish the insns before reaching the point where it applies the 
additional logic that I added. For a 32 bit ISA, this results in 2^n 
tree nodes generated (where n is the number of non-decodable bits), 
which is clearly unacceptable, not to mention that the additional tree 
nodes are all identical and resolve nothing! For one particular port, 
the tree generation, which previously took a few minutes now took over 
12 hours.

The root of the problem is that the heuristic which chooses bits to use 
will eventually choose bits which have no effect on the decoding of the 
insn.  There is a heuristic function which computes a value representing 
the usefulness of each bit to the decoding process. It does correctly 
rate these bits as the least useful, but the fact remains that they will 
eventually be chosen anyway, as the other usful bits are exhausted. It 
turns out that the heuristic function assigns these bits a value of 
zero. Unfortunately, the existing heuristic function also assigns the 
value zero to the bits representing the specialized insn fields that 
were interested in. Two changes were necessary:

1) The change to decode.scm:317 ignores bits which are assigned the 
heuristic value of zero.
2) The heuristic function was changed to prioritize bits into 3 categories:
    a) bits which are true decodable bits
    b) bits which are used in specialization of an insn
    c) useless bits

The previous heuristic counted the number of times in the ISA that a bit 
was required to be zero (p0) and the number of times it was required to 
be one (p1). The function then computed the geometric mean (sqrt (p0 * 
p1)). You can see that the more often a bit is constant in an insn, the 
higher this value will be. You can also see that if a bit is never 
constant in an insn (useless for decoding), the result will be zero. For 
a bit which is in a specialized field of an insn, however, one of p0 or 
p1 will be zero, resulting in an overal heurstic value of zero. We need 
to modify the function so that these bits receive a value greater than 
zero, but less that the value assigned to a truly decodable bit. The new 
function (decode.scm:241) works as follows:

    if (p0 + p1 == 0) // useless for decoding
        result = 0;
    else if (p0 * p1 == 0) // specialization bit: heuristic range: 0 <= 
h < num_insns
        result = num_insns - (p0 + p1);
    else // decodable bit -- heuristic range: num_insns < h
        result = num_insns + (sqrt (p0 * p1));

So the heuristic now chooses decodable bits first, followed by 
specialization bits and ignores the useless bits. Note also that a bit 
which is always 1 or always 0 is also useless for decoding and will be 
assigned a value of zero (since p0 or p1 will be equal to num_insns). 
This brought the build time for the port which had ballooned to 12 hours 
back down to its normal few minutes.

The result of this patch should be:

o No effect for ports with no specialized insns. The new heuristic will 
result in the same prioritization of bits as before.
o Slightly larger decoder tree for ports with specialized insns. One 
extra tree level for each node containing a specialized insn. I know of 
only one such port. For that port, the specializations are meaningless 
since the the semantics of the specialized insn are the as those of the 
general insn. This is why the previous filtering implementation was not 
a problem. I have tested this port with no regressions.
o The port I'm developing now works as expected  :-)

I know this is a complex patch, so please feel free to ask questions. 
I'm seeking approval to commit this.

Dave