Subversion Repositories scarts

; Application independent decoder support.

; Copyright (C) 2000, 2004, 2009 Red Hat, Inc.

; This file is part of CGEN.

;

; This file provides utilities for building instruction set decoders.

; At present its rather limited, and is geared towards the simulator

; where the goal is hyper-efficiency [not that there isn't room for much

; improvement, but rather that that's what the current focus is].

;

; The CPU description file provides the first pass's bit mask with the

; `decode-assist' spec.  This gives the decoder a head start on how to

; efficiently decode the instruction set.  The rest of the decoder is

; determined algorithmically.

; ??? Need to say more here.

;

; The main entry point is decode-build-table.

;

; Main procedure call tree:

; decode-build-table

;     -build-slots

;     -build-decode-table-guts

;         -build-decode-table-entry

;             -build-slots

;             -build-decode-table-guts

;

; -build-slots/-build-decode-table-guts are recursively called to construct a

; tree of "table-guts" elements, and then the application recurses on the

; result.  For example see sim-decode.scm.

;

; FIXME: Don't create more than 3 shifts (i.e. no more than 3 groups).

; FIXME: Exits when insns are unambiguously determined, even if there are more

; opcode bits to examine.

; The set of instruction is internally recorded as a tree of two data

; structures: "table-guts" and "table-entry".

; [The choice of "table-guts" is historical, a better name will come to mind

; eventually.]

; Decoded tables data structure, termed "table guts".

; bitnums:  list of bits that have been used thus far to decode the insn

; startbit: bit offset in instruction of value in C local variable `insn'

; bitsize:  size of value in C local variable `insn', the number

;           of bits of the instruction read thus far

; entries:  list of insns that match the decoding thus far,

;           each entry in the list is a `dtable-entry' record

; Accessors.

; A decoded subtable.

; key: name to distinguish this subtable from others, used for lookup

; table: a table-guts element

; name: name of C variable containing the table

; The implementation uses a list so the lookup can use assv.

; Accessors.

; List of decode subtables.

; Add SUBTABLE-GUTS to the subtables list if not already present.

; Result is the subtable entry already present, or new entry.

" "" "" "" "" ""bad dtable entry type:"; An instruction and predicate for final matching.

; Accessors.

; Return a pseudo-cost of processing exprentry X.

; Sort an exprtable, optimum choices first.

; Basically an optimum choice is a cheaper choice.

; Return the name of the expr table for INSN-EXPRS,

; which is a list of exprtable-entry elements.

; Typically the expressions are ifield-assertion specs.

; INSN-EXPRS is a sorted list of exprtable-entry elements.

; The list is considered sorted in the sense that the first insn to satisfy

; Accessors.

; Decoded table entry data structure.

; A simple data structure of 3 elements:

; index: index in the parent table

; value: the insn or subtable or exprtable

; Accessors.

; MASKS is a list of opcode masks.

; BITNUM is the number of the bit to test.  It's value depends on LSB0?.

; It can be no larger than the smallest element in MASKS.

; E.g. If MASK-LENS consists of 16 and 32 and LSB0? is #f, BITNUM must

; FIXME: This isn't quite right.  What if LSB0? = #t?  Need decode-bitsize.

; LSB0? is non-#f if bit number 0 is the least significant bit.

;

; FIXME: This is just a first cut, but the governing intent is to not require

; targets to specify decode tables, hints, or algorithms.

; Certainly as it becomes useful they can supply such information.

; The point is to avoid having to as much as possible.

;

; FIXME: Bit numbers shouldn't be considered in isolation.

; It would be better to compute use counts of all of them and then see

; if there's a cluster of high use counts.

; If half or more insns use the bit, it's a good one.

; FIXME: An empirical guess at best.

; Compute population counts for each bit.  Return it as a vector indexed by bit

; number.  Rather than computing raw popularity, attempt to compute

; "disinguishing value" or inverse-entropy for each bit.  The idea is that the

; larger the number for any particular bit slot, the more instructions it can

; be used to distinguish.  Raw mask popularity is not enough -- popular masks

; may include useless "reserved" fields whose values don't change, and thus are

; useless in distinguishing.

;

; NOTE: mask-lens are not necessarily all the same value.

; E.g. for the m32r it can consist of both 16 and 32.

; But all masks must exist in the window specified by STARTBIT,DECODE-BITSIZE,

; and all bits in the result must live in that window.

; Compute the 1- and 0-population vectors

; Compute an aggregate "distinguishing value" for each bit.

"/"" "; The most useful bits for decoding are those with counts in both

; p0 and p1. These are the bits which distinguish one insn from

;

; or p1.  These bits represent specializations of other insns.

; Assign these bits a value between 0 and (num-insns - 1). Note that

; p0 + p1 is guaranteed to be <= num-insns. The value 0 is assigned

; which are always 1 or always 0 in the ISA and are useless for

;

; Bits with no count in either p0 or p1 are useless for decoding

; and should never be considered. Assigning these bits a value of

; 0 ensures this.

; Return a list (0 ... LIMIT-1).

; Return a list (BASE ... BASE+SIZE-1).

; to VALUE.

; Return a list of indices whose counts in the given vector exceed the given

; Sort them in decreasing order of popularity.

; Return the top few most popular indices in the population vector,

; ignoring any that are already used (marked by #f).  Don't exceed

; `size' unless the clustering is just too good to pass up.

"-population-top-few"" desired="" picks=("") pop=("")"" threshold="" new-picks=("")\n"; No point picking bits with population count of zero.  This leads to

; the generation of layers of subtables which resolve nothing.  Generating

; these tables can slow the build by several orders of magnitude.

"-population-top-few: No bits left to pick from!\n"; Way too many matches?

; prefer old-picks

; Not enough?  Lower the threshold a bit and try to add some more.

; Notice magic clustering decay parameter

;  vvvv

; Given list of insns, return list of bit numbers of constant bits in opcode

; that they all share (or mostly share), up to MAX elements.

; ALREADY-USED is a list of bitnums we can't use.

; STARTBIT is the bit offset of the instruction value that C variable `insn'

; DECODE-BITSIZE is the number of bits of the insn that `insn' holds.

; LSB0? is non-#f if bit number 0 is the least significant bit.

;

; Nil is returned if there are none, meaning that there is an ambiguity in

; the specification up to the current word as defined by startbit,

;

; We assume INSN-LIST matches all opcode bits before STARTBIT (if any).

; FIXME: Revisit, as a more optimal decoder is sometimes achieved by doing

; back to earlier ones.

; All insns are assumed to start at the same address so we handle insns of

; varying lengths - we only analyze the common bits in all of them.

; Note that if we get called again to compute further opcode bits, we

; start looking at STARTBIT again (rather than keeping track of how far in

; the insn word we've progressed).  We could do this as an optimization, but

; we also have to handle the case where the initial set of decode bits misses

; some and thus we have to go back and look at them.  It may also turn out

; information to the decoding process (see -usable-decode-bit?).  As the

; possible insn list gets wittled down, the bit will become significant.  Thus

; the optimization is left for later.

; Also, see preceding FIXME: We can't proceed past startbit + decode-bitsize

;; (undecoded (if lsb0?

;;              (-range2 startbit (+ startbit decode-bitsize))

;;              (-range2 (- startbit decode-bitsize) startbit)))

; (append already-used undecoded))

; than the base insn size.

; FIXME: for now (gets sparc port going)

; Return list of decode table entry numbers for INSN's opcode bits BITNUMS.

; This is the indices into the decode table that match the instruction.

; LSB0? is non-#f if bit number 0 is the least significant bit.

;

; Example: If BITNUMS is (0 1 2 3 4 5), and the constant (i.e. opcode) part of

; the those bits of INSN is #b1100xx (where 'x' indicates a non-constant

; part), then the result is (#b110000 #b110001 #b110010 #b110011).

;(display (list val insn-len decode-len bl)) (newline)

; Oh My God.  This isn't tail recursive.

"insn ="" insn-value="" insn-base-mask="" insn-len="" decode-len="" opcode="" opcode-mask="" indices=""\n"; Subroutine of -build-slots.

; Fill slot in INSN-VEC that INSN goes into.

; BITNUMS is the list of opcode bits.

; LSB0? is non-#f if bit number 0 is the least significant bit.

;

; Example: If BITNUMS is (0 1 2 3 4 5) and the constant (i.e. opcode) part of

; the first six bits of INSN is #b1100xx (where 'x' indicates a non-constant

; Each "slot" is a list of matching instructions.

;(display (string-append "fill-slot!: " (obj:str-name insn) " ")) (display bitnums) (newline)

;(display (list "Filling slot(s)" slot-nums "...")) (newline)

; Given a list of constant bitnums (ones that are predominantly, though perhaps

; not always, in the opcode), record each insn in INSN-LIST in the proper slot.

; LSB0? is non-#f if bit number 0 is the least significant bit.

; The result is a vector of insn lists.  Each slot is a list of insns

; that go in that slot.

; Loop over each element, filling RESULT.

; Compute the name of a decode table, prefixed with PREFIX.

; in reverse order of traversal (since they're built with cons).

; INDEX-LIST may be empty.

"table""_"; CDR of each element is the table index.

; Generate one decode table entry for INSN-VEC at INDEX.

; INSN-VEC is a vector of slots where each slot is a list of instructions that

; map to that slot (opcode value).  If a slot is nil, no insn has that opcode

; value so the decoder marks it as being invalid.

; STARTBIT is the bit offset of the instruction value that C variable `insn'

; holds (note that this is independent of LSB0?).

; DECODE-BITSIZE is the number of bits of the insn that `insn' holds.

; INDEX-LIST is a list of pairs: list of bitnums, table entry number.

; LSB0? is non-#f if bit number 0 is the least significant bit.

; INVALID-INSN is an <insn> object to use for invalid insns.

; ??? For debugging.

"Processing decode entry "" in ""decode_"", ""invalid""subtable"" ...\n"; If no insns map to this value, mark it as invalid.

; If only one insn maps to this value, that's it for this insn.

; FIXME: Incomplete: need to check further opcode bits.

; Otherwise more than one insn maps to this value and we need to look at

; further opcode bits.

"Building subtable at index "", decode-bitsize = "", indices used thus far:"" ""\n"; If bitnums is nil, either there is an ambiguity or we need to read

; more of the instruction in order to distinguish insns in SLOT.

; We might be able to resolve the ambiguity by reading more bits.

; We know from the < test that there are, indeed, more bits to

; be read.

; FIXME: It's technically possible that the next

; startbit+decode-bitsize chunk has no usable bits and we have to

; iterate, but rather unlikely.

; The calculation of the new startbit, decode-bitsize will

; undoubtedly need refinement.

;nil ; FIXME: what to put here?

; If bitnums is still nil there is an ambiguity.

; Try filtering out insns which are more general cases of

; other insns in the slot.  The filtered insns will appear

; in other slots as appropriate.

; Only 1 insn left in the slot, so take it.

; There is still more than one insn in 'slot',

; so there is still an ambiguity.

; If all insns are marked as DECODE-SPLIT, don't warn.

"WARNING: Decoder ambiguity detected: "; drop leading comma

", ""\n"; Things aren't entirely hopeless.  We've warned about

; the ambiguity.  Now, if there are any identical insns,

; filter them out.  If only one remains, then use it.

; Only 1 insn left in the slot, so take it.

; Otherwise, see if any ifield-assertion

; specs are present.

; FIXME: For now we assume that if they all have an

; ifield-assertion spec, then there is no ambiguity (it's left

; to the programmer to get it right).  This can be made more

; clever later.

; FIXME: May need to back up startbit if we've tried to read

; more of the instruction.  We currently require that

; all bits get used before advancing startbit, so this

; shouldn't be necessary.  Verify.

; Save arguments for debugging purposes.

"Unable to resolve ambiguity (maybe need some ifield-assertion specs?)"; FIXME: Punt on even simple cleverness for now.

; There is no ambiguity so generate the subtable.

; may be appending to -decode-subtables recursively.

; as a list of 3 elements: bitnums, decode-bitsize, and list of entries.

; Bitnums is recorded with the guts so that tables whose contents are

; identical but are accessed by different bitnums are treated as separate in

; -decode-subtables.  Not sure this will ever happen, but play it safe.

;

; BITNUMS is the list of bit numbers used to build the slot table.

; STARTBIT is the bit offset of the instruction value that C variable `insn'

; For example, it is initially zero.  If DECODE-BITSIZE is 16 and after

; needed, another piece will be fetched and STARTBIT will then be 16.

; DECODE-BITSIZE is the number of bits of the insn that `insn' holds.

; INDEX-LIST is a list of pairs: list of bitnums, table entry number.

; Decode tables consist of entries of two types: actual insns and

; pointers to other tables.

; LSB0? is non-#f if bit number 0 is the least significant bit.

; INVALID-INSN is an <insn> object representing invalid insns.

; Return a table that efficiently decodes INSN-LIST.

; BITNUMS is the set of bits to initially key off of.

; LSB0? is non-#f if bit number 0 is the least significant bit.

; INVALID-INSN is an <insn> object representing the `invalid' insn (for

; instructions values that don't decode to any entry in INSN-LIST).

; Initialize the list of subtables computed.

; ??? Another way to handle simple forms of ifield-assertions (like those

; created by insn specialization) is to record a copy of the insn for each

; possible value of the ifield and modify its ifield list with the ifield's

; value.  This would then let the decoder table builder handle it normally.

; I wouldn't create N insns, but would rather create an intermediary record

; ifield-assertions).