OSDN Git Service

Use datarootdir for locales.
[pf3gnuchains/pf3gnuchains4x.git] / cgen / iformat.scm
1 ; Instruction formats.
2 ; Copyright (C) 2000, 2009, 2010 Red Hat, Inc.
3 ; This file is part of CGEN.
4 ; See file COPYING.CGEN for details.
5
6 ; Instruction formats are computed after the .cpu file has been read in.
7 ; ??? May also wish to allow programmer to specify formats, but not sure this
8 ; will complicate things more than it simplifies them, so it's defered.
9 ;
10 ; Two kinds of formats are defined here: iformat and sformat.
11 ; (pronounced "I-format" and "S-format")
12 ;
13 ; Iformats are the instruction format as specified by the instructions' fields,
14 ; and are the machine computed version of the generally known notion of an
15 ; "instruction format".  No semantic information is attributed to iformats.
16 ;
17 ; Sformats are the same as iformats except that semantics are used to
18 ; distinguish them.  For example, if an operand is refered to in one mode by
19 ; one instruction and in a different mode by another instruction, then these
20 ; two insns would have different sformats but the same iformat.  Sformats
21 ; are used in simulator extraction code to collapse the number of cases that
22 ; must be handled.  They can also be used to collapse the number of cases
23 ; in the modeling code.
24 ;
25 ; The "base length" is the length of the insn that is initially fetched for
26 ; decoding purposes.
27 ; Formats are fixed in length.  For variable instruction length architectures
28 ; there are separate formats for each insn's possible length.
29
30 (define <iformat>
31   (class-make '<iformat>
32               '(<ident>)
33                 ; From <ident>:
34                 ; - NAME is derived from number, but we might have user
35                 ;   specified formats someday [though I wouldn't add them
36                 ;   without a clear need].
37                 ; - COMMENT is the assembler syntax of an example insn that
38                 ;   uses the format.
39               '(
40                 ; Index into the iformat table.
41                 number
42
43                 ; Sort key, used to determine insns with identical formats.
44                 key
45
46                 ; List of <ifield> objects.
47                 ifields
48
49                 ; min (insn-length, base-insn-size)
50                 mask-length
51
52                 ; total length of insns with this format
53                 length
54
55                 ; mask of base part
56                 mask
57
58                 ; An example insn that uses the format.
59                 eg-insn
60                 )
61               nil)
62 )
63
64 ; Accessor fns.
65
66 (define-getters <iformat> ifmt
67   (number key ifields mask-length length mask eg-insn)
68 )
69
70 ; Return enum cgen_fmt_type value for FMT.
71 ; ??? Not currently used.
72
73 (define (ifmt-enum fmt)
74   (string-append "@CPU@_" (string-upcase (gen-sym fmt)))
75 )
76 \f
77 ; Given FLD-LIST, compute the length of the insn in bits.
78 ; This is done by adding up all the field sizes.
79 ; All bits must be represent exactly once.
80
81 (define (compute-insn-length fld-list)
82   (apply + (map ifld-length (ifields-base-ifields fld-list)))
83 )
84
85 ; Given FLD-LIST, compute the base length in bits.
86 ;
87 ; For variable length instruction sets, or with cpus with multiple
88 ; instruction sets, compute the base appropriate for this set of
89 ; ifields.  Check that ifields are not shared among isas with
90 ; inconsistent base insn lengths.
91 ;
92 ; ??? The algorithm here is a bit odd.  [Though there is value in verifying
93 ; ifields are from consistent ISAs.]
94
95 (define (compute-insn-base-mask-length fld-list)
96   (let* ((isa-base-bitsizes
97           (remove-duplicates
98            (map isa-base-insn-bitsize
99                 (map current-isa-lookup
100                      (collect (lambda (ifld) 
101                                 (atlist-attr-value (obj-atlist ifld) 'ISA #f))
102                               fld-list))))))
103     (if (= 1 (length isa-base-bitsizes))
104         (min (car isa-base-bitsizes) (compute-insn-length fld-list))
105         (error "ifields have inconsistent isa/base-insn-size values:" isa-base-bitsizes)))
106 )
107
108 ; Given FLD-LIST, compute the bitmask of constant values in the base part
109 ; of the insn (i.e. the opcode field).
110 ;
111 ; FIXME: Need to add support for constant fields appearing outside the base
112 ; insn.  One way would be to record with each insn the value for each constant
113 ; field.  That would allow code to straightforwardly fetch it.  Another would
114 ; be to only record constant values appearing outside the base insn.
115 ;
116 ; See also (insn-value).
117 ;
118 (define (compute-insn-base-mask fld-list)
119   (let* ((mask-len (compute-insn-base-mask-length fld-list))
120          (lsb0? (ifld-lsb0? (car fld-list)))
121          (mask-bitrange (make <bitrange>
122                               0 ; word-offset
123                               (if lsb0? (- mask-len 1) 0) ; start
124                               mask-len ; length
125                               mask-len ; word-length
126                               lsb0?)))
127     (apply +
128            (map (lambda (fld) (ifld-mask fld mask-len mask-bitrange))
129                 ; Find the fields that have constant values.
130                 (find ifld-constant? (ifields-base-ifields fld-list)))))
131 )
132 \f
133 ; Return the <iformat> search key for a sorted field list.
134 ; This determines how iformats differ from each other.
135 ; It also speeds up searching as the search key can be anything
136 ; (though at present searching isn't as fast as it could be).
137 ; INSN is passed so that we can include its sanytize attribute, if present,
138 ; so sanytized sources work (needed formats don't disappear).
139
140 (define (/ifmt-search-key insn sorted-ifld-list)
141   (string-map (lambda (ifld)
142                 (string-append " ("
143                                (or (->string (obj-attr-value insn 'sanitize))
144                                    "-nosan-")
145                                " "
146                                (obj:str-name ifld)
147                                " "
148                                (ifld-ilk ifld)
149                                ")"))
150               sorted-ifld-list)
151 )
152
153 ; Create an <iformat> object for INSN.
154 ; INDEX is the ordinal to assign to the result or -1 if unknown.
155 ; SEARCH-KEY is the search key used to determine the iformat's uniqueness.
156 ; IFLDS is a sorted list of INSN's ifields.
157
158 (define (ifmt-build insn index search-key iflds)
159   (make <iformat>
160     (symbol-append 'ifmt- (obj:name insn))
161     (string-append "e.g. " (insn-syntax insn))
162     atlist-empty
163     index
164     search-key
165     iflds
166     (compute-insn-base-mask-length iflds)
167     (compute-insn-length iflds)
168     (compute-insn-base-mask iflds)
169     insn)
170 )
171 \f
172 ; Sformats.
173
174 (define <sformat>
175   (class-make '<sformat>
176               '(<ident>)
177               ; From <ident>:
178               ; - NAME is derived from number.
179               ; - COMMENT is the assembler syntax of an example insn that
180               ;   uses the format.
181               '(
182                 ; Index into the sformat table.
183                 number
184
185                 ; Sort key, used to determine insns with identical formats.
186                 key
187
188                 ; Non-#f if insns with this format are cti insns.
189                 cti?
190
191                 ; IN-OPS is a list of input operands.
192                 ; OUT-OPS is a list of output operands.
193                 ; These are used to distinguish the format from others,
194                 ; so that the extract and read operations can be based on the
195                 ; sformat.
196                 ; The extract fns use this data to record the necessary
197                 ; information for profiling [which isn't necessarily a property
198                 ; of the field list].  We could have one extraction function
199                 ; per instruction, but there's a *lot* of duplicated code, and
200                 ; the semantic operands rarely contribute to extra formats.
201                 ; The parallel execution support uses this data to record the
202                 ; input (or output) values based on the instruction format,
203                 ; again cutting down on duplicated code.
204                 in-ops
205                 out-ops
206
207                 ; Length of all insns with this format.
208                 ; Since insns with different iformats can have the same sformat
209                 ; we need to ensure ifield extraction works among the various
210                 ; iformats.  We do this by ensuring all insns with the same
211                 ; sformat have the same length.
212                 length
213
214                 ; Cached list of all ifields used.
215                 ; This can be derived from IN-OPS/OUT-OPS but is computed once
216                 ; and cached here for speed.
217                 iflds
218
219                 ; An example insn that uses the format.
220                 ; This is used for debugging purposes, but also to help get
221                 ; sanytization (spelled wrong on purpose) right.
222                 eg-insn
223
224                 ; <sformat-argbuf> entry
225                 ; FIXME: Temporary location, to be moved elsewhere
226                 (sbuf . #f)
227                 )
228               nil)
229 )
230
231 ; Accessor fns.
232
233 (define-getters <sformat> sfmt
234   (number key cti? in-ops out-ops length iflds eg-insn sbuf)
235 )
236
237 (define-setters <sformat> sfmt (sbuf))
238
239 (method-make-make! <sformat>
240                    '(name comment attrs
241                      number key cti? in-ops out-ops length iflds eg-insn)
242 )
243 \f
244 ; Return the <sformat> search key for a sorted field list and semantic
245 ; operands.
246 ; This determines how sformats differ from each other.
247 ; It also speeds up searching as the search key can be anything
248 ; (though at present searching isn't as fast as it could be).
249 ;
250 ; INSN is passed so that we can include its sanytize attribute, if present,
251 ; so sanytized sources work (needed formats don't disappear).
252 ; SORTED-USED-IFLDS is a sorted list of ifields used by SEM-{IN,OUT}-OPS.
253 ; Note that it is not the complete set of ifields used by INSN.
254 ;
255 ; We assume INSN's <iformat> has been recorded.
256 ;
257 ; Note: It's important to minimize the number of created sformats.  It keeps
258 ; the generated code smaller (and sometimes faster - more usable common
259 ; fragments in pbb simulators).  Don't cause spurious differences.
260
261 (define (/sfmt-search-key insn cti? sorted-used-iflds sem-in-ops sem-out-ops)
262   (assert (insn-ifmt insn))
263
264   (let ((op-key (lambda (op)
265                   (string-append " ("
266                                  (or (->string (obj-attr-value insn 'sanitize))
267                                      "-nosan-")
268                                  " "
269                                  (obj:str-name op)
270                                  ; ??? Including memory operands currently
271                                  ; isn't necessary and it can account for some
272                                  ; spurious differences.  On the other hand
273                                  ; leaving it out doesn't seem like the right
274                                  ; thing to do.
275                                  (if (memory? (op:type op))
276                                      ""
277                                      (string-append " "
278                                                     (obj:str-name (op:mode op))))
279                                  ; CGEN_OPERAND_INSTANCE_COND_REF is stored
280                                  ; with the operand in the operand instance
281                                  ; table thus formats must be distinguished
282                                  ; by this.
283                                  (if (op:cond? op) " cond" "")
284                                  ")")))
285         )
286     (list
287      ;; Use the iformat key so that each sformat maps to only one iformat.
288      (if (= (length sorted-used-iflds) 0)
289          "no-used-ifields"
290          (ifmt-key (insn-ifmt insn)))
291      cti?
292      (string-map op-key
293                  sem-in-ops)
294      (string-map op-key
295                  sem-out-ops)
296      ))
297 )
298
299 ; Create an <sformat> object for INSN.
300 ; INDEX is the ordinal to assign to the result or -1 if unknown.
301 ; SEARCH-KEY is the search key used to determine the sformat's uniqueness.
302 ; {IN,OUT}-OPS are lists of INSN's input/output operands.
303 ; SORTED-USED-IFLDS is a sorted list of ifields used by {IN,OUT}-OPS.
304 ; Note that it is not the complete set of ifields used by INSN.
305 ;
306 ; We assume INSN's <iformat> has already been recorded.
307
308 (define (sfmt-build insn index search-key cti? in-ops out-ops sorted-used-iflds)
309   (make <sformat>
310     (symbol-append 'sfmt- (obj:name insn))
311     (string-append "e.g. " (insn-syntax insn))
312     atlist-empty
313     index
314     search-key
315     cti?
316     in-ops
317     out-ops
318     (insn-length insn)
319     sorted-used-iflds
320     insn)
321 )
322
323 ; Sort IFLDS by dependencies and then by starting bit number.
324
325 (define (/sfmt-order-iflds iflds)
326   (let ((up? 
327          ; ??? Something like this is preferable.
328          ;(not (ifld-lsb0? (car ifld-list)))
329          (not (current-arch-insn-lsb0?))))
330     (let loop ((independent nil) (dependent nil) (iflds iflds))
331       (cond ((null? iflds)
332              (append (sort-ifield-list independent up?)
333                      (sort-ifield-list dependent up?)))
334             ; FIXME: quick hack.
335             ((multi-ifield? (car iflds))
336              (loop independent (cons (car iflds) dependent) (cdr iflds)))
337             (else
338              (loop (cons (car iflds) independent) dependent (cdr iflds))))))
339 )
340
341 ; Return a sorted list of ifields used by IN-OPS, OUT-OPS.
342 ; The ifields are sorted by dependencies and then by start bit.
343 ; The important points are to help distinguish sformat's by the ifields used
344 ; and to put ifields that others depend on first.
345
346 (define (/sfmt-used-iflds in-ops out-ops)
347   (let ((in-iflds (map op-iflds-used in-ops))
348         (out-iflds (map op-iflds-used out-ops)))
349     (let ((all-iflds (nub (append (apply append in-iflds)
350                                   (apply append out-iflds))
351                           obj:name)))
352       (/sfmt-order-iflds all-iflds)))
353 )
354 \f
355 ; The format descriptor is used to sort formats.
356 ; This is a utility class internal to this file.
357 ; There is one instance per insn.
358
359 (define <fmt-desc>
360   (class-make '<fmt-desc>
361               nil
362               '(
363                 ; #t if insn is a cti insn
364                 cti?
365
366                 ; sorted list of insn's ifields
367                 iflds
368
369                 ; computed set of input/output operands
370                 in-ops out-ops
371
372                 ; set of ifields used by IN-OPS,OUT-OPS.
373                 used-iflds
374
375                 ; computed set of attributes
376                 attrs
377                 )
378               nil)
379 )
380
381 ; Accessors.
382
383 (define-getters <fmt-desc> -fmt-desc
384   (cti? iflds in-ops out-ops used-iflds attrs)
385 )
386
387 ; Compute an iformat descriptor used to build an <iformat> object for INSN.
388 ;
389 ; If COMPUTE-SFORMAT? is #t compute the semantic format
390 ; (same as instruction format except that operands are used to
391 ; distinguish insns).
392 ; Attributes derivable from the semantics are also computed.
393 ; This is all done at the same time to minimize the number of times the
394 ; semantic code is traversed.
395 ; The semantics of INSN must already be canonicalized and stored in
396 ; canonical-semantics.
397 ;
398 ; The result is (descriptor compiled-semantics attrs).
399 ; `descriptor' and `compiled-semantics' are #f for insns with an empty
400 ; field list.  This happens for virtual insns.
401 ; `attrs' is an <attr-list> object of attributes derived from the semantics.
402 ;
403 ; ??? We never traverse the semantics of virtual insns.
404
405 (define (ifmt-analyze insn compute-sformat?)
406   ; First sort by starting bit number the list of fields in INSN.
407   (let ((sorted-ifields
408          (sort-ifield-list (insn-iflds insn)
409                            ; ??? Something like this is preferable, but
410                            ; if the first insn is a virtual insn there are
411                            ; no fields.
412                            ;(not (ifld-lsb0? (car (insn-iflds insn))))
413                            (not (current-arch-insn-lsb0?))
414                            )))
415
416     (if (null? sorted-ifields)
417
418         ; Field list is unspecified.
419         (list #f #f atlist-empty)
420
421         (let* ((sem (insn-canonical-semantics insn))
422                ; Compute list of input and output operands if asked for.
423                (sem-ops (if compute-sformat?
424                             (semantic-compile #f ; FIXME: context
425                                               insn sem)
426                             (csem-make #f #f #f
427                                        (if sem
428                                            (semantic-attrs #f ; FIXME: context
429                                                            insn sem)
430                                            atlist-empty)))))
431
432           (let ((compiled-sem (csem-code sem-ops))
433                 (in-ops (csem-inputs sem-ops))
434                 (out-ops (csem-outputs sem-ops))
435                 (attrs (csem-attrs sem-ops))
436                 (cti? (or (atlist-cti? (csem-attrs sem-ops))
437                           (insn-cti-attr? insn))))
438
439             (list (make <fmt-desc>
440                     cti? sorted-ifields in-ops out-ops
441                     (if (and in-ops out-ops)
442                         (/sfmt-used-iflds in-ops out-ops)
443                         #f)
444                     attrs)
445                   compiled-sem
446                   attrs)))))
447 )
448
449 ; Subroutine of ifmt-compute!, to simplify it.
450 ; Lookup INSN's iformat in IFMT-LIST and if not found add it.
451 ; FMT-DESC is INSN's <fmt-desc> object.
452 ; IFMT-LIST is append!'d to and the found iformat is stored in INSN.
453
454 (define (/ifmt-lookup-ifmt! insn fmt-desc ifmt-list)
455   (let* ((search-key (/ifmt-search-key insn (-fmt-desc-iflds fmt-desc)))
456          (ifmt (find-first (lambda (elm)
457                              (equal? (ifmt-key elm) search-key))
458                            ifmt-list)))
459
460     (if ifmt
461
462         ; Format was found, use it.
463         (begin
464           (logit 3 "Using iformat " (number->string (ifmt-number ifmt)) ".\n")
465           (insn-set-ifmt! insn ifmt)
466           )
467
468         ; Format wasn't found, create new entry.
469         (let* ((ifmt-index (length ifmt-list))
470                (ifmt (ifmt-build insn ifmt-index search-key
471                                  (ifields-base-ifields (-fmt-desc-iflds fmt-desc)))))
472           (logit 3 "Creating iformat " (number->string ifmt-index) ".\n")
473           (insn-set-ifmt! insn ifmt)
474           (append! ifmt-list (list ifmt))
475           )
476         ))
477
478   *UNSPECIFIED*
479 )
480
481 ; Subroutine of ifmt-compute!, to simplify it.
482 ; Lookup INSN's sformat in SFMT-LIST and if not found add it.
483 ; FMT-DESC is INSN's <fmt-desc> object.
484 ; SFMT-LIST is append!'d to and the found sformat is stored in INSN.
485 ;
486 ; We assume INSN's <iformat> has already been recorded.
487
488 (define (/ifmt-lookup-sfmt! insn fmt-desc sfmt-list)
489   (assert (insn-ifmt insn))
490
491   (let* ((search-key (/sfmt-search-key insn (-fmt-desc-cti? fmt-desc)
492                                        (-fmt-desc-used-iflds fmt-desc)
493                                        (-fmt-desc-in-ops fmt-desc)
494                                        (-fmt-desc-out-ops fmt-desc)))
495          (sfmt (find-first (lambda (elm)
496                              (equal? (sfmt-key elm) search-key))
497                            sfmt-list)))
498
499     (if sfmt
500
501         ; Format was found, use it.
502         (begin
503           (logit 3 "Using sformat " (number->string (sfmt-number sfmt)) ".\n")
504           (insn-set-sfmt! insn sfmt)
505           )
506
507         ; Format wasn't found, create new entry.
508         (let* ((sfmt-index (length sfmt-list))
509                (sfmt (sfmt-build insn sfmt-index search-key
510                                  (-fmt-desc-cti? fmt-desc)
511                                  (-fmt-desc-in-ops fmt-desc)
512                                  (-fmt-desc-out-ops fmt-desc)
513                                  (ifields-base-ifields (-fmt-desc-used-iflds fmt-desc)))))
514           (logit 3 "Creating sformat " (number->string sfmt-index) ".\n")
515           (insn-set-sfmt! insn sfmt)
516           (append! sfmt-list (list sfmt))
517           )
518         ))
519
520   *UNSPECIFIED*
521 )
522 \f
523 ; Main entry point.
524
525 ; Given a list of insns, compute the set of instruction formats, semantic
526 ; formats, semantic attributes, and compiled semantics for each insn.
527 ;
528 ; The computed <iformat> object is stored in the `ifmt' field of each insn.
529 ;
530 ; Attributes derived from the semantic code are added to the insn's attributes,
531 ; but they don't override any prespecified values.
532 ;
533 ; If COMPUTE-SFORMAT? is #t, the computed <sformat> object is stored in the
534 ; `sfmt' field of each insn, and the processed semantic code is stored in the
535 ; `compiled-semantics' field of each insn.
536 ;
537 ; The `fmt-desc' field of each insn is used to store an <fmt-desc> object
538 ; which contains the search keys, sorted field list, input-operands, and
539 ; output-operands, and is not used outside this procedure.
540 ;
541 ; The result is a list of two lists: the set of computed iformats, and the
542 ; set of computed sformats.
543 ;
544 ; *** This is the most expensive calculation in CGEN.   ***
545 ; *** (mainly because of the detailed semantic parsing) ***
546
547 (define (ifmt-compute! insn-list compute-sformat?)
548   (logit 2 "Computing instruction formats and analyzing semantics ...\n")
549
550   ; First analyze each insn, storing the result in fmt-desc.
551   ; If asked to, convert the semantic code to a compiled form to simplify more
552   ; intelligent processing of it later.
553
554   (for-each (lambda (insn)
555               (logit 2 "Scanning operands of " (obj:name insn) ": "
556                      (insn-syntax insn) " ...\n")
557               (let ((sem-ops (ifmt-analyze insn compute-sformat?)))
558                 (insn-set-fmt-desc! insn (car sem-ops))
559                 (if (and compute-sformat? (cadr sem-ops))
560                     (let ((compiled-sem (cadr sem-ops)))
561                       (insn-set-compiled-semantics! insn compiled-sem)))
562                 (obj-set-atlist! insn
563                                  (atlist-append (obj-atlist insn)
564                                                 (caddr sem-ops)))
565                 ))
566             insn-list)
567
568   ; Now for each insn, look up the ifield list in the format table (and if not
569   ; found add it), and set the ifmt/sfmt elements of the insn.
570
571   (let* ((empty-ifmt (make <iformat>
572                           'ifmt-empty
573                           "empty iformat for unspecified field list"
574                           atlist-empty ; attrs
575                           -1 ; number
576                           #f ; key
577                           nil ; fields
578                           0 ; mask-length
579                           0 ; length
580                           0 ; mask
581                           #f)) ; eg-insn
582          (empty-sfmt (make <sformat>
583                           'sfmt-empty
584                           "empty sformat for unspecified field list"
585                           atlist-empty ; attrs
586                           -1 ; number
587                           #f ; key
588                           #f ; cti?
589                           nil ; sem-in-ops
590                           nil ; sem-out-ops
591                           0 ; length
592                           nil ; used iflds
593                           #f)) ; eg-insn
594          (ifmt-list (list empty-ifmt))
595          (sfmt-list (list empty-sfmt))
596          )
597
598     (for-each (lambda (insn)
599                 (logit 2 "Processing format for " (obj:name insn) ": "
600                        (insn-syntax insn) " ...\n")
601
602                 (let ((fmt-desc (insn-fmt-desc insn)))
603
604                   (if fmt-desc
605
606                       (begin
607                         ; Must compute <iformat> before <sformat>, the latter
608                         ; needs the former.
609                         (/ifmt-lookup-ifmt! insn fmt-desc ifmt-list)
610                         (if compute-sformat?
611                             (/ifmt-lookup-sfmt! insn fmt-desc sfmt-list)))
612
613                       ; No field list present, use empty format.
614                       (begin
615                         (insn-set-ifmt! insn empty-ifmt)
616                         (if compute-sformat?
617                             (insn-set-sfmt! insn empty-sfmt))))))
618
619               (non-multi-insns insn-list))
620
621     ; Done.  Return the computed iformat and sformat lists.
622     (list ifmt-list sfmt-list)
623     )
624 )