This is the mail archive of the
cgen@sources.redhat.com
mailing list for the CGEN project.
Re: [patch][rfa]: Decoding (not-so) ambiguous insns in sid/sim
- From: Dave Brolley <brolley at redhat dot com>
- To: sid at sources dot redhat dot com, cgen at sources dot redhat dot com
- Date: Thu, 03 Jan 2002 13:46:56 -0500
- Subject: Re: [patch][rfa]: Decoding (not-so) ambiguous insns in sid/sim
- References: <3C3391D7.6050301@redhat.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.
>