From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 8330 invoked by alias); 24 Oct 2009 00:03:56 -0000 Received: (qmail 8303 invoked by uid 22791); 24 Oct 2009 00:03:53 -0000 X-SWARE-Spam-Status: No, hits=-0.4 required=5.0 tests=AWL,BAYES_00,DNS_FROM_RFC_BOGUSMX X-Spam-Check-By: sourceware.org Received: from sebabeach.org (HELO sebabeach.org) (64.165.110.50) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 24 Oct 2009 00:03:48 +0000 Received: by sebabeach.org (Postfix, from userid 500) id F0DA36E3D5; Fri, 23 Oct 2009 17:03:46 -0700 (PDT) From: Doug Evans To: cgen@sourceware.org Subject: [commit] Avoid emitting unnecessary opcode bits test Message-Id: <20091024000346.F0DA36E3D5@sebabeach.org> Date: Sat, 24 Oct 2009 00:03:00 -0000 X-IsSubscribed: yes Mailing-List: contact cgen-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: cgen-owner@sourceware.org X-SW-Source: 2009-q4/txt/msg00020.txt.bz2 Hi. This is a patch I've wanted to do for awhile. It removes redundant test of whether all opcode bits have been checked in the simulator decoders. 2009-10-23 Doug Evans * decode.scm: Tweak various comments. (/opcode-slots): Add FIXME. (/build-decode-table-guts): Add assert. * utils-sim.scm (/gen-set-itype-and-extract): New function. (/gen-bracketed-set-itype-and-extract): New function. (/gen-decode-default-entry): Rewrite. (/table-guts-to-mask, /all-opcode-bits-used?): New functions. (/gen-decode-insn-entry): New arg table-guts-thus-far, all callers updated. Don't unnecessarily emit check for whether all opcode bits have been examined. (/gen-decode-expr-set-itype): Delete. (/gen-decode-expr-entry): Update. (/gen-decode-table-entry): New arg table-guts-thus-far, all callers updated. Keep track of decoder tables used thus far. (/gen-decoder-switch): Ditto. * utils.scm (word-bit-value): New function. Index: decode.scm =================================================================== RCS file: /cvs/src/src/cgen/decode.scm,v retrieving revision 1.14 diff -u -p -r1.14 decode.scm --- decode.scm 8 Sep 2009 06:51:44 -0000 1.14 +++ decode.scm 23 Oct 2009 23:50:01 -0000 @@ -37,12 +37,12 @@ ; [The choice of "table-guts" is historical, a better name will come to mind ; eventually.] -; Decoded tables data structure, termed "table guts". +; Decoded tables data structure, termed "dtable-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 +; (note that this is independent of LSB0?) +; bitsize: size of value in C local variable `insn' ; entries: list of insns that match the decoding thus far, ; each entry in the list is a `dtable-entry' record @@ -470,7 +470,7 @@ ; part), then the result is (#b110000 #b110001 #b110010 #b110011). (define (/opcode-slots insn bitnums lsb0?) - (let ((opcode (insn-value insn)) + (let ((opcode (insn-value insn)) ;; FIXME: unused, overridden below (insn-len (insn-base-mask-length insn)) (decode-len (length bitnums))) (let* ((opcode (/get-subopcode-value (insn-value insn) insn-len decode-len bitnums 0 lsb0?)) @@ -688,13 +688,11 @@ ) ) -; 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. +; Given a vector of insn slots INSN-VEC, generate the guts of the decode table, +; recorded as a "dtable-guts" data structure. ; ; BITNUMS is the list of bit numbers used to build the slot table. +; I.e., (= (vector-length insn-vec) (ash 1 (length bitnums))). ; 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 @@ -706,6 +704,10 @@ ; pointers to other tables. ; LSB0? is non-#f if bit number 0 is the least significant bit. ; INVALID-INSN is an object representing invalid insns. +; +; 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. (define (/build-decode-table-guts insn-vec bitnums startbit decode-bitsize index-list lsb0? invalid-insn) (logit 2 "Processing decoder for bits" @@ -714,6 +716,7 @@ ", decode-bitsize " decode-bitsize ", index-list " index-list " ...\n") + (assert (= (vector-length insn-vec) (ash 1 (length bitnums)))) (dtable-guts-make bitnums startbit decode-bitsize @@ -727,6 +730,8 @@ ; Entry point. ; Return a table that efficiently decodes INSN-LIST. +; The table is a "dtable-guts" data structure, see dtable-guts-make. +; ; 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. Index: utils-sim.scm =================================================================== RCS file: /cvs/src/src/cgen/utils-sim.scm,v retrieving revision 1.19 diff -u -p -r1.19 utils-sim.scm --- utils-sim.scm 17 Sep 2009 16:49:12 -0000 1.19 +++ utils-sim.scm 23 Oct 2009 23:50:02 -0000 @@ -508,7 +508,8 @@ ; gen-decoder [our entry point] ; decode-build-table ; /gen-decoder-switch -; /gen-decoder-switch +; /gen-decode-table-entry +; /gen-decoder-switch ; ; decode-build-table is called to construct a tree of "table-guts" elements ; (??? Need better name obviously), @@ -587,27 +588,80 @@ ")")) ) -; Convert decoder table into C code. +; Return code to set `itype' and branch to the extraction phase. -; Return code for the default entry of each switch table -; -(define (/gen-decode-default-entry indent invalid-insn fn?) +(define (/gen-set-itype-and-extract insn-enum fmt-name fn?) (string-append "itype = " - (gen-cpu-insn-enum (current-cpu) invalid-insn) - ";" + insn-enum + "; " (if (with-scache?) (if fn? - " @prefix@_extract_sfmt_empty (this, current_cpu, pc, base_insn, entire_insn); goto done;\n" - " goto extract_sfmt_empty;\n") - " goto done;\n") - ) + (string-append "@prefix@_extract_" fmt-name + " (this, current_cpu, pc, base_insn, entire_insn);" + " goto done;") + (string-append "goto extract_" fmt-name ";")) + "goto done;")) ) -; Return code for one insn entry. +;; Return code to set `itype' and branch to the extraction phase, +;; bracketed in { } and indented by INDENT. + +(define (/gen-bracketed-set-itype-and-extract indent insn-enum fmt-name fn?) + (string-append + indent "{ " + (/gen-set-itype-and-extract insn-enum fmt-name fn?) + " }\n") +) + +; Return code for the default entry of each switch table + +(define (/gen-decode-default-entry invalid-insn fn?) + (/gen-set-itype-and-extract (gen-cpu-insn-enum (current-cpu) invalid-insn) + "sfmt_empty" + fn?) +) + +;; Subroutine of /all-opcode-bits-used? to simplify it. +;; Given TABLE-GUTS-THUS-FAR return the mask of base its that have been +;; examined. +;; TABLE-GUTS-THUS-FAR is a list of dtable-guts objects. +;; PERF: Don't compute this for each insn, but that has to wait on the +;; base-insn-bitsize cleanup (m32r). + +(define (/table-guts-to-mask table-guts-thus-far base-bitsize lsb0?) + ;;(logit 2 "/table-guts-to-mask " (map dtable-guts-bitnums table-guts-thus-far) "\n") + (let guts-loop ((mask 0) (guts-list table-guts-thus-far)) + (if (null? guts-list) + mask + (let bits-loop ((mask mask) (bits (dtable-guts-bitnums (car guts-list)))) + (if (null? bits) + (guts-loop mask (cdr guts-list)) + (bits-loop (+ mask (word-bit-value (car bits) base-bitsize lsb0?)) + (cdr bits)))))) +) + +;; Subroutine of /gen-decode-insn-entry to simplify it. +;; Return a boolean indicating if all opcode bits of INSN have been +;; examined given TABLE-GUTS-THUS-FAR. +;; FIXME: Examine entire insn's opcode bits. + +(define (/all-opcode-bits-used? insn table-guts-thus-far lsb0?) + (let* ((base-mask (insn-base-mask insn)) + ;; FIXME: This can go away when base-insn-bitsize is fixed (m32r). + (base-bitsize (min (insn-base-mask-length insn) (state-base-insn-bitsize))) + (table-guts-base-mask (/table-guts-to-mask table-guts-thus-far + base-bitsize + lsb0?))) + (= (cg-logand base-mask table-guts-base-mask) base-mask)) +) + +; Return code for one insn entry, ENTRY. ; REST is the remaining entries. +; TABLE-GUTS-THUS-FAR is the list of dtable-guts objects that led to this insn. -(define (/gen-decode-insn-entry entry rest indent invalid-insn fn?) +(define (/gen-decode-insn-entry entry rest table-guts-thus-far + indent lsb0? invalid-insn fn?) (assert (eq? 'insn (dtable-entry-type entry))) (logit 3 "Generating decode insn entry for " (obj:name (dtable-entry-value entry)) " ...\n") @@ -633,30 +687,46 @@ " : /* fall through */\n")) (else - (string-append indent " case " - (number->string (dtable-entry-index entry)) " :\n" - ; Compensate for base-insn-size > current-insn-size by adjusting entire_insn. - ; Activate this logic only for sid simulators; they are consistent in - ; interpreting base-insn-bitsize this way. - (if (and (equal? APPLICATION 'SID-SIMULATOR) - (> (state-base-insn-bitsize) (insn-length insn))) - (string-append - indent " entire_insn = entire_insn >> " - (number->string (- (state-base-insn-bitsize) (insn-length insn))) - ";\n") - "") - ; Generate code to check that all of the opcode bits for this insn match - indent " if ((" - (if (adata-integral-insn? CURRENT-ARCH) "entire_insn" "base_insn") - " & 0x" (number->hex (insn-base-mask insn)) ") == 0x" (number->hex (insn-value insn)) ")\n" - indent " { itype = " (gen-cpu-insn-enum (current-cpu) insn) ";" - (if (with-scache?) - (if fn? - (string-append " @prefix@_extract_" fmt-name " (this, current_cpu, pc, base_insn, entire_insn); goto done;") - (string-append " goto extract_" fmt-name ";")) - " goto done;") - " }\n" - indent " " (/gen-decode-default-entry indent invalid-insn fn?))))) + (let ((consistent-base-insn? (and (equal? APPLICATION 'SID-SIMULATOR) + (> (state-base-insn-bitsize) + (insn-length insn))))) + (string-append indent " case " + (number->string (dtable-entry-index entry)) " :" + ;; Compensate for base-insn-size > current-insn-size by + ;; adjusting entire_insn. + ;; Activate this logic only for sid simulators; they are + ;; consistent in interpreting base-insn-bitsize this way. + (if consistent-base-insn? + (string-append + "\n" + indent " entire_insn = entire_insn >> " + (number->string (- (state-base-insn-bitsize) (insn-length insn))) + ";\n") + "") + ;; If necessary, generate code to check that all of the + ;; opcode bits for this insn match. + (if (/all-opcode-bits-used? insn table-guts-thus-far lsb0?) + (string-append + (if consistent-base-insn? + (string-append indent " ") + " ") + (/gen-set-itype-and-extract (gen-cpu-insn-enum (current-cpu) insn) + fmt-name fn?) + "\n") + (string-append + (if consistent-base-insn? + "" + "\n") + indent " if ((" + (if (adata-integral-insn? CURRENT-ARCH) "entire_insn" "base_insn") + " & 0x" (number->hex (insn-base-mask insn)) + ") == 0x" (number->hex (insn-value insn)) ")\n" + (/gen-bracketed-set-itype-and-extract (string-append indent " ") + (gen-cpu-insn-enum (current-cpu) insn) + fmt-name fn?) + indent " " + (/gen-decode-default-entry invalid-insn fn?) + "\n"))))))) ) ; Subroutine of /decode-expr-ifield-tracking. @@ -744,24 +814,6 @@ *UNSPECIFIED* ) -; Subroutine of /gen-decode-expr-entry. -; Return code to set `itype' and branch to the extraction phase. - -(define (/gen-decode-expr-set-itype indent insn-enum fmt-name fn?) - (string-append - indent - "{ itype = " - insn-enum - "; " - (if (with-scache?) - (if fn? - (string-append "@prefix@_extract_" fmt-name " (this, current_cpu, pc, base_insn, entire_insn); goto done;") - (string-append "goto extract_" fmt-name ";")) - "goto done;") - " }\n" - ) -) - ; Generate code to decode the expression table in ENTRY. ; INVALID-INSN is the object of the pseudo insn to handle invalid ones. @@ -789,7 +841,7 @@ code (append! code (list - (/gen-decode-expr-set-itype + (/gen-bracketed-set-itype-and-extract indent (gen-cpu-insn-enum (current-cpu) invalid-insn) "sfmt_empty" @@ -815,33 +867,33 @@ ; Need this in a list for a later append!. (string-list - (/gen-decode-expr-set-itype + (/gen-bracketed-set-itype-and-extract indent (gen-cpu-insn-enum (current-cpu) insn) (gen-sym (insn-sfmt insn)) fn?)) ; We don't use up all ifield values, so emit a test. - (let ((iflds (map current-ifld-lookup ifld-names))) - (string-list - indent "{\n" - (gen-define-ifields iflds + (let ((iflds (map current-ifld-lookup ifld-names))) + (string-list + indent "{\n" + (gen-define-ifields iflds + (insn-length insn) + (string-append indent " ") + #f) + (gen-extract-ifields iflds (insn-length insn) (string-append indent " ") #f) - (gen-extract-ifields iflds - (insn-length insn) - (string-append indent " ") - #f) - indent " if (" - (rtl-c 'BI expr nil #:ifield-var? #t) - ")\n" - (/gen-decode-expr-set-itype - (string-append indent " ") - (gen-cpu-insn-enum (current-cpu) insn) - (gen-sym (insn-sfmt insn)) - fn?) - indent "}\n"))))) + indent " if (" + (rtl-c 'BI expr nil #:ifield-var? #t) + ")\n" + (/gen-bracketed-set-itype-and-extract + (string-append indent " ") + (gen-cpu-insn-enum (current-cpu) insn) + (gen-sym (insn-sfmt insn)) + fn?) + indent "}\n"))))) (loop (cdr expr-list) (append! code next-code))))))) @@ -850,10 +902,12 @@ ; Generate code to decode TABLE. ; REST is the remaining entries. -; SWITCH-NUM, STARTBIT, DECODE-BITSIZE, INDENT, LSB0?, INVALID-INSN are same -; as for /gen-decoder-switch. +; SWITCH-NUM, STARTBIT, DECODE-BITSIZE, TABLE-GUTS-THUS-FAR, +; INDENT, LSB0?, INVALID-INSN are the same as for /gen-decoder-switch. -(define (/gen-decode-table-entry table rest switch-num startbit decode-bitsize indent lsb0? invalid-insn fn?) +(define (/gen-decode-table-entry table rest switch-num startbit decode-bitsize + table-guts-thus-far + indent lsb0? invalid-insn fn?) (assert (eq? 'table (dtable-entry-type table))) (logit 3 "Generating decode table entry for case " (dtable-entry-index table) " ...\n") @@ -876,6 +930,7 @@ startbit decode-bitsize (subdtable-table (dtable-entry-value table)) + table-guts-thus-far (string-append indent " ") lsb0? invalid-insn @@ -945,6 +1000,9 @@ ; 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. +; TABLE-GUTS-THUS-FAR is a list of the table-guts that got us here, +; excluding TABLE-GUTS. It is used to decide whether insns have been +; fully decoded (i.e. all opcode bits have been examined). ; LSB0? is non-#f if bit number 0 is the least significant bit. ; INVALID-INSN is the object of the pseudo insn to handle invalid ones. @@ -955,63 +1013,72 @@ ; else {} ; may well be less stressful on the compiler to optimize than small switch() stmts. -(define (/gen-decoder-switch switch-num startbit decode-bitsize table-guts +(define (/gen-decoder-switch switch-num startbit decode-bitsize + table-guts table-guts-thus-far indent lsb0? invalid-insn fn?) - ; For entries that are a single insn, we're done, otherwise recurse. - (string-list - indent "{\n" - ; Are we at the next word? - (if (not (= startbit (dtable-guts-startbit table-guts))) - (begin - (set! startbit (dtable-guts-startbit table-guts)) - (set! decode-bitsize (dtable-guts-bitsize table-guts)) - ; FIXME: Bits may get fetched again during extraction. - (string-append indent " unsigned int val;\n" - indent " /* Must fetch more bits. */\n" - indent " insn = " - (gen-ifetch "pc" startbit decode-bitsize) - ";\n" - indent " val = ")) - (string-append indent " unsigned int val = ")) - (/gen-decode-bits (dtable-guts-bitnums table-guts) - (dtable-guts-startbit table-guts) - (dtable-guts-bitsize table-guts) - "insn" "entire_insn" lsb0?) - ";\n" - indent " switch (val)\n" - indent " {\n" - - ; The code is more readable, and icache use is improved, if we collapse - ; common code into one case and use "fall throughs" for all but the last of - ; a set of common cases. - ; FIXME: We currently rely on /gen-decode-foo-entry to recognize the fall - ; through. We should take care of it ourselves. - - (let loop ((entries (/decode-sort-entries (dtable-guts-entries table-guts))) - (result nil)) - (if (null? entries) - (reverse! result) - (loop - (cdr entries) - (cons (case (dtable-entry-type (car entries)) - ((insn) - (/gen-decode-insn-entry (car entries) (cdr entries) indent invalid-insn fn?)) - ((expr) - (/gen-decode-expr-entry (car entries) indent invalid-insn fn?)) - ((table) - (/gen-decode-table-entry (car entries) (cdr entries) - switch-num startbit decode-bitsize - indent lsb0? invalid-insn fn?)) - ) - result)))) - - ; ??? Can delete if all cases are present. - indent " default : " - (/gen-decode-default-entry indent invalid-insn fn?) - indent " }\n" - indent "}\n" - ) + (let ((new-table-guts-thus-far (append table-guts-thus-far (list table-guts)))) + + (string-list + indent "{\n" + ;; Are we at the next word? + (if (not (= startbit (dtable-guts-startbit table-guts))) + (begin + (set! startbit (dtable-guts-startbit table-guts)) + (set! decode-bitsize (dtable-guts-bitsize table-guts)) + ;; FIXME: Bits may get fetched again during extraction. + (string-append indent " unsigned int val;\n" + indent " /* Must fetch more bits. */\n" + indent " insn = " + (gen-ifetch "pc" startbit decode-bitsize) + ";\n" + indent " val = ")) + (string-append indent " unsigned int val = ")) + (/gen-decode-bits (dtable-guts-bitnums table-guts) + (dtable-guts-startbit table-guts) + (dtable-guts-bitsize table-guts) + "insn" "entire_insn" lsb0?) + ";\n" + indent " switch (val)\n" + indent " {\n" + + ;; The code is more readable, and icache use is improved, if we collapse + ;; common code into one case and use "fall throughs" for all but the last + ;; of a set of common cases. + ;; FIXME: We currently rely on /gen-decode-foo-entry to recognize the fall + ;; through. We should take care of it ourselves. + + (let loop ((entries (/decode-sort-entries (dtable-guts-entries table-guts))) + (result nil)) + + (if (null? entries) + + (reverse! result) + + (loop + (cdr entries) + ;; For entries that are a single insn, we're done, otherwise recurse. + (cons (case (dtable-entry-type (car entries)) + ((insn) + (/gen-decode-insn-entry (car entries) (cdr entries) + new-table-guts-thus-far + indent lsb0? invalid-insn fn?)) + ((expr) + (/gen-decode-expr-entry (car entries) indent invalid-insn fn?)) + ((table) + (/gen-decode-table-entry (car entries) (cdr entries) + switch-num startbit decode-bitsize + new-table-guts-thus-far + indent lsb0? invalid-insn fn?)) + ) + result)))) + + ;; ??? Can delete if all cases are present. + indent " default : " + (/gen-decode-default-entry invalid-insn fn?) "\n" + indent " }\n" + indent "}\n" + )) ) ; Decoder generation entry point. @@ -1038,7 +1105,7 @@ ; Now print it out. - (/gen-decoder-switch "0" 0 decode-bitsize table-guts indent lsb0? - invalid-insn fn?) - ) + (/gen-decoder-switch "0" 0 decode-bitsize + table-guts nil + indent lsb0? invalid-insn fn?)) ) Index: utils.scm =================================================================== RCS file: /cvs/src/src/cgen/utils.scm,v retrieving revision 1.32 diff -u -p -r1.32 utils.scm --- utils.scm 23 Sep 2009 22:30:19 -0000 1.32 +++ utils.scm 23 Oct 2009 23:50:02 -0000 @@ -837,6 +837,15 @@ (remainder (logslr value (- size (+ start length))) (integer-expt 2 length)))) ) +; Return numeric value of bit N in a word of size WORD-BITSIZE. + +(define (word-bit-value bitnum word-bitsize lsb0?) + (assert (< bitnum word-bitsize)) + (if lsb0? + (ash 1 bitnum) + (ash 1 (- word-bitsize bitnum 1))) +) + ; Return a bit mask of size SIZE beginning at the LSB. (define (mask size)