URL
https://opencores.org/ocsvn/scarts/scarts/trunk
Subversion Repositories scarts
[/] [scarts/] [trunk/] [toolchain/] [scarts-binutils/] [binutils-2.19.1/] [cgen/] [decode.scm] - Rev 6
Compare with Previous | Blame | View Log
; 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. ; Decoder data structures and accessors. ; 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". ; A simple data structure of 4 elements: ; 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. ; A simple data structure of 3 elements: ; 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. ; The key is computed so as to make comparisons possible with assv. " "" "" "" "" ""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. "-"; A set of instructions that need expressions to distinguish. ; 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 ; its predicate is chosen. ; Accessors. ; Decoded table entry data structure. ; A simple data structure of 3 elements: ; index: index in the parent table ; entry type indicator: 'insn or 'table or 'expr ; value: the insn or subtable or exprtable ; Accessors. ; Return #t if BITNUM is a good bit to use for decoding. ; MASKS is a list of opcode masks. ; MASK-LENS is a list of lengths of each value in 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 ; be from 0 to 15. ; 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. ; If no distinguishing bit fits in the window, return an empty vector. ; Compute the 1- and 0-population vectors " population count mask="" len=""\n"; ignore this bit if it's not set in the mask ; 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 ; another. Assign these bits a high value (greater than num-insns). ; ; The next most useful bits are those with counts in either p0 ; 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 ; to bits for which p0 or p1 is equal to num_insns. These are bits ; which are always 1 or always 0 in the ISA and are useless for ; decoding purposes. ; ; 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). ; Return a copy of VECTOR, with all entries with given INDICES set ; to VALUE. ; Return a list of indices whose counts in the given vector exceed the given ; threshold. ; 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: count-threshold is zero!\n"; No new matches? "-population-top-few: No bits left to pick from!\n"; Way too many matches? ; prefer old-picks ; About right number of matches? ; 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' ; holds (note that this is independent of LSB0?). ; 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, ; decode-bitsize, and more bytes need to be fetched. ; ; We assume INSN-LIST matches all opcode bits before STARTBIT (if any). ; FIXME: Revisit, as a more optimal decoder is sometimes achieved by doing ; a cluster of opcode bits that appear later in the insn, and then coming ; 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 ; that an opcode bit is skipped over because it doesn't contribute much ; 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 ; until we've processed all bits up to startbit + decode-bitsize. ;; (undecoded (if lsb0? ;; (-range2 startbit (+ startbit decode-bitsize)) ;; (-range2 (- startbit decode-bitsize) startbit))) ; (append already-used undecoded)) "Best decode bits (prev="" start="" decode="")""=>""("")\n"; ??? We assume mask lengths are repeatedly used for insns longer ; 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 ; part), then elements 48 49 50 51 of INSN-VEC are cons'd with INSN. ; 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. ; INDEX-LIST is a list of pairs: list of bitnums, table entry number, ; 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. ; The result is a dtable-entry element (or "slot"). ; ??? 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. ; Need to build `subtable' separately because we ; may be appending to -decode-subtables recursively. ""; Given vector of insn slots, generate the guts of the decode table, recorded ; 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' ; holds (note that this is independent of LSB0?). ; For example, it is initially zero. If DECODE-BITSIZE is 16 and after ; scanning the first fetched piece of the instruction, more decoding is ; 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. "Processing decoder for bits"" "", startbit "", decode-bitsize "", index-list "" ...\n"; Entry point. ; Return a table that efficiently decodes INSN-LIST. ; BITNUMS is the set of bits to initially key off of. ; DECODE-BITSIZE is the number of bits of the instruction that `insn' holds. ; 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 ; that recorded the necessary bits (insn, ifield-list, remaining ; ifield-assertions).