From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20868 invoked by alias); 3 Jan 2002 18:47:00 -0000 Mailing-List: contact cgen-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: cgen-owner@sources.redhat.com Received: (qmail 20819 invoked from network); 3 Jan 2002 18:47:00 -0000 Message-ID: <3C34A720.9050209@redhat.com> Date: Thu, 03 Jan 2002 10:47:00 -0000 From: Dave Brolley User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.2) Gecko/20010726 Netscape6/6.1 X-Accept-Language: en-us MIME-Version: 1.0 To: sid@sources.redhat.com, cgen@sources.redhat.com Subject: Re: [patch][rfa]: Decoding (not-so) ambiguous insns in sid/sim References: <3C3391D7.6050301@redhat.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-SW-Source: 2002-q1/txt/msg00005.txt.bz2 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 > > * 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. >