Re: [patch][rfa]: Decoding (not-so) ambiguous insns in sid/sim

[Dave Brolley <brolley at redhat dot com>]

Approved by fche and committed with the following changes:

o Added more comments to explain the heuristic function which 
prioritizes bit selection
o Removed the function "filter-harmlessly-ambiguous-insns"

Dave

Dave Brolley wrote:

> 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
>
>
>------------------------------------------------------------------------
>
>2002-01-02  Dave Brolley  <brolley@redhat.com>
>
>	* decode.scm (-distinguishing-bit-population): Compute num-insns, the
>	number of insns in the list.  Update the population count function to
>	identify and prioritize 3 catgories of useful bits.
>	(-population-top-few): Don't consider bits with a population count of
>	zero.
>	(-build-decode-table-entry): Don't call
>	filter-harmlessly-ambiguous-insns.  Filter out non-specialized and
>	identical insns at the next tree level.
>	* insn.scm (filter-harmlessly-ambiguous-insns): Note in a comment that
>	this function is no longer used.
>	(filter-non-specialized-ambiguous-insns): New function.
>	(filter-identical-ambiguous-insns): New function.
>	(find-identical-insn): New function.
>