cgen/insn.scm

   1 ; Instruction definitions.
   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 ; Class to hold an insn.
   7
   8 (define <insn>
   9   (class-make '<insn>
  10               '(<source-ident>)
  11               '(
  12                 ; Used to explicitly specify mnemonic, now it's computed from
  13                 ; syntax string.  ??? Might be useful as an override someday.
  14                 ;mnemonic
  15
  16                 ; Instruction syntax string.
  17                 syntax
  18
  19                 ; The insn fields as specified in the .cpu file.
  20                 ; Also contains values for constant fields.
  21                 iflds
  22                 (/insn-value . #f) ; Lazily computed cache
  23                 (/insn-base-value . #f) ; Lazily computed cache
  24
  25                 ; RTL source of assertions of ifield values or #f if none.
  26                 ; This is used, for example, by the decoder to help
  27                 ; distinguish what would otherwise be an ambiguity in the
  28                 ; specification.  It is also used by decode-split support.
  29                 ; ??? It could also be used the the assembler/disassembler
  30                 ; some day.
  31                 (ifield-assertion . #f)
  32
  33                 ; The <fmt-desc> of the insn.
  34                 ; This is used to help calculate the ifmt,sfmt members.
  35                 (fmt-desc . #f)
  36
  37                 ; The <iformat> of the insn.
  38                 (ifmt . #f)
  39
  40                 ; The <sformat> of the insn.
  41                 (sfmt . #f)
  42
  43                 ; Temp slot for use by applications.
  44                 (tmp . #f)
  45
  46                 ; Instruction semantics.
  47                 ; This is the rtl in source form, as provided in the
  48                 ; description file, or #f if there is none.
  49                 ;
  50                 ; There are a few issues (ick, I hate that word) to consider
  51                 ; here:
  52                 ; - some apps don't need the trap checks (e.g. SIGSEGV)
  53                 ; - some apps treat the pieces in different ways
  54                 ; - the simulator tries to merge common fragments among insns
  55                 ;   to reduce code size in a pbb simulator
  56                 ;
  57                 ; Some insns don't have any semantics at all, they are defined
  58                 ; in another insn [akin to anonymous patterns in gcc].  wip.
  59                 ;
  60                 ; ??? GCC-like apps will need a new field to allow specifying
  61                 ; the semantics if a different value is needed.  wip.
  62                 ; ??? May wish to put this and the compiled forms in a
  63                 ; separate class.
  64                 ; ??? Contents of trap expressions is wip.  It will probably
  65                 ; be a sequence with an #:errchk modifier or some such.
  66                 semantics
  67
  68                 ; The processed form of the semantics.
  69                 ; This remains #f for virtual insns (FIXME: keep?).
  70                 (canonical-semantics . #f)
  71
  72                 ; The processed form of the semantics.
  73                 ; This remains #f for virtual insns (FIXME: keep?).
  74                 (compiled-semantics . #f)
  75
  76                 ; The mapping of the semantics onto the host.
  77                 ; FIXME: Not sure what its value will be.
  78                 ; Another thing that will be needed is [in some cases] a more
  79                 ; simplified version of the RTL for use by apps like compilers.
  80                 ; Perhaps that's what this will become.
  81                 ;host-semantics
  82
  83                 ; The function unit usage of the instruction.
  84                 timing
  85                 )
  86               nil)
  87 )
  88
  89 (method-make-make! <insn>
  90                    '(location name comment attrs syntax iflds ifield-assertion
  91                      semantics timing)
  92 )
  93
  94 ; Accessor fns
  95
  96 (define-getters <insn> insn
  97   (syntax iflds ifield-assertion fmt-desc ifmt sfmt tmp
  98           semantics canonical-semantics compiled-semantics timing)
  99 )
 100
 101 (define-setters <insn> insn
 102   (fmt-desc ifmt sfmt tmp ifield-assertion
 103    canonical-semantics compiled-semantics)
 104 )
 105
 106 ; Return a boolean indicating if X is an <insn>.
 107
 108 (define (insn? x) (class-instance? <insn> x))
 109
 110 ; Return a list of the machs that support INSN.
 111
 112 (define (insn-machs insn)
 113   nil ; ??? wip
 114 )
 115
 116 ; Return the length of INSN in bits.
 117
 118 (define (insn-length insn)
 119   (ifmt-length (insn-ifmt insn))
 120 )
 121
 122 ; Return the length of INSN in bytes.
 123
 124 (define (insn-length-bytes insn)
 125   (bits->bytes (insn-length insn))
 126 )
 127
 128 ; Return instruction mnemonic.
 129 ; This is computed from the syntax string.
 130 ; The mnemonic, as we define it, is everything up to, but not including, the
 131 ; first space or '$'.
 132 ; FIXME: Rename to syntax-mnemonic, and take a syntax string argument.
 133 ; FIXME: Doesn't handle \$ to indicate a $ is actually in the mnemonic.
 134
 135 (define (insn-mnemonic insn)
 136   (letrec ((mnem-len (lambda (str len)
 137                        (cond ((= (string-length str) 0) len)
 138                              ((char=? #\space (string-ref str 0)) len)
 139                              ((char=? #\$ (string-ref str 0)) len)
 140                              (else (mnem-len (string-drop1 str) (+ len 1)))))))
 141     (string-take (mnem-len (insn-syntax insn) 0) (insn-syntax insn)))
 142 )
 143
 144 ; Return enum cgen_insn_types value for INSN.
 145
 146 (define (insn-enum insn)
 147   (string-upcase (string-append "@ARCH@_INSN_" (gen-sym insn)))
 148 )
 149
 150 ; Return enum for insn named INSN-NAME.
 151 ; This is needed for the `invalid' insn, there is no object for it.
 152 ; [Though obviously having such an object seems like a good idea.]
 153
 154 (define (gen-insn-enum insn-name)
 155   (string-upcase (string-append "@ARCH@_INSN_" (gen-c-symbol insn-name)))
 156 )
 157 \f
 158 ; Insns with derived operands (see define-derived-operand).
 159 ; ??? These are [currently] recorded separately to minimize impact on existing
 160 ; code while the design is worked out.
 161 ;
 162 ; The class is called <multi-insn> because the insn has multiple variants,
 163 ; one for each combination of "anyof" alternatives.
 164 ; Internally we create one <insn> per alternative.  The theory is that this
 165 ; will remain an internal implementation issue.  When appropriate applications
 166 ; will collapse the number of insns in a way that is appropriate for them.
 167 ;
 168 ; ??? Another way to do this is with insn templates.  One problem the current
 169 ; way has is that it requires each operand's assembler syntax to be self
 170 ; contained (one way to fix this is to use "fake" operands like before).
 171 ; Insn templates needn't have this problem.  On the other hand insn templates
 172 ; [seem to] require more description file entries.
 173 ;
 174 ; ??? This doesn't use all of the members of <insn>.
 175 ; The <multi-insn> class is wip, but should eventually reorganize <insn>.
 176 ; This reorganization might also take into account real, virtual, etc. insns.
 177
 178 (define <multi-insn>
 179   (class-make '<multi-insn>
 180               '(<insn>)
 181               '(
 182                 ; An <insn> is created for each combination of "anyof"
 183                 ; alternatives.  They are recorded with other insns, but a
 184                 ; list of them is recorded here as well.
 185                 ; This is #f if the sub-insns haven't been instantiated yet.
 186                 (sub-insns . #f)
 187                 )
 188               nil)
 189 )
 190
 191 (method-make-make! <multi-insn>
 192                    '(location name comment attrs syntax iflds ifield-assertion
 193                      semantics timing)
 194 )
 195
 196 (define-getters <multi-insn> multi-insn (sub-insns))
 197
 198 ; Return a boolean indicating if X is a <multi-insn>.
 199
 200 (define (multi-insn? x) (class-instance? <multi-insn> x))
 201
 202 ; Subroutine of /sub-insn-make! to create the ifield list.
 203 ; Return encoding of {insn} with each element of {anyof-operands} replaced
 204 ; with {new-values}.
 205 ; {value-names} is a list of names of {anyof-operands}.
 206
 207 (define (/sub-insn-ifields insn anyof-operands value-names new-values)
 208   ; Delete ifields of {anyof-operands} and add those for {new-values}.
 209   (let ((iflds
 210          (append!
 211           ; Delete ifields in {anyof-operands}.
 212           (find (lambda (f)
 213                   (not (and (ifld-anyof-operand? f)
 214                             (memq (obj:name (ifld-get-value f))
 215                                   value-names))))
 216                 (insn-iflds insn))
 217           ; Add ifields for {new-values}.
 218           (map derived-encoding new-values)))
 219
 220         ; Return the last ifield of OWNER in IFLD-LIST.
 221         ; OWNER is the object that owns the <ifield> we want.
 222         ; For ifields, the owner is the ifield itself.
 223         ; For operands, the owner is the operand.
 224         ; For derived operands, the owner is the "anyof" parent.
 225         ; IFLD-LIST is an unsorted list of <ifield> elements.
 226         (find-preceder
 227          (lambda (ifld-list owner)
 228            (cond ((ifield? owner)
 229                   owner)
 230                  ((anyof-operand? owner)
 231                   ; This is the interesting case.  The instantiated choice of
 232                   ; {owner} is in {ifld-list}.  We have to find it.
 233                   (let* ((name (obj:name owner))
 234                          (result
 235                           (find-first (lambda (f)
 236                                         (and (derived-ifield? f)
 237                                              (anyof-instance? (derived-ifield-owner f))
 238                                              (eq? name (obj:name (anyof-instance-parent (derived-ifield-owner f))))))
 239                                       ifld-list)))
 240                     (assert result)
 241                     result))
 242                  ((operand? owner) ; derived operands are handled here too
 243                   (let ((result (op-ifield owner)))
 244                     (assert result)
 245                     result))
 246                  (else
 247                   (error "`owner' not <ifield>, <operand>, or <derived-operand>")))))
 248         )
 249
 250     ; Resolve any `follows' specs.
 251     ; Bad worst case performance but ifield lists aren't usually that long.
 252     ; FIXME: Doesn't handle A following B following C.
 253     (map (lambda (f)
 254            (let ((follows (ifld-follows f)))
 255              (if follows
 256                  (let ((preceder (find-preceder iflds follows)))
 257                    (ifld-new-word-offset f (ifld-next-word preceder)))
 258                  f)))
 259          iflds))
 260 )
 261
 262
 263 ; Subroutine of multi-insn-instantiate! to instantiate one insn.
 264 ; INSN is the parent insn.
 265 ; ANYOF-OPERANDS is a list of the <anyof-operand>'s of INSN.
 266 ; NEW-VALUES is a list of the value to use for each corresponding element in
 267 ; ANYOF-OPERANDS.  Each element is a <derived-operand>.
 268
 269 (define (/sub-insn-make! insn anyof-operands new-values)
 270   (assert (= (length anyof-operands) (length new-values)))
 271   (assert (all-true? (map anyof-operand? anyof-operands)))
 272   (assert (all-true? (map derived-operand? new-values)))
 273   (logit 3 "Instantiating "
 274          (obj:name insn)
 275          ":"
 276          (string-map (lambda (op newval)
 277                        (string/symbol-append " "
 278                                              (obj:name op)
 279                                              "="
 280                                              (obj:name newval)))
 281                      anyof-operands new-values)
 282          " ...\n")
 283
 284   (let* ((value-names (map obj:name anyof-operands))
 285          (ifields (/sub-insn-ifields insn anyof-operands value-names new-values))
 286          (known-values (ifld-known-values ifields)))
 287
 288     ; Don't create insn if ifield assertions fail.
 289     (if (all-true? (map (lambda (op)
 290                           (anyof-satisfies-assertions? op known-values))
 291                         new-values))
 292
 293         (let ((sub-insn
 294                (make <insn>
 295                      (obj-location insn)
 296                      (apply symbol-append
 297                             (cons (obj:name insn)
 298                                   (map (lambda (anyof)
 299                                          (symbol-append '- (obj:name anyof)))
 300                                        new-values)))
 301                      (obj:comment insn)
 302                      (obj-atlist insn)
 303                      (/anyof-merge-syntax (insn-syntax insn)
 304                                           value-names new-values insn)
 305                      ifields
 306                      (insn-ifield-assertion insn) ; FIXME
 307                      (anyof-merge-semantics (insn-semantics insn)
 308                                             value-names new-values)
 309                      (insn-timing insn)
 310                      )))
 311           (logit 3 "   instantiated.\n")
 312           (current-insn-add! sub-insn)
 313
 314           ;; FIXME: Hack to remove differences in generated code when we
 315           ;; switched to recording insns in hash tables.
 316           ;; See similar comment in arch-analyze-insns!.
 317           ;; Make the ordinals count backwards.
 318           ;; Subtract 2 because mach.scm:-get-next-ordinal! adds 1.
 319           (arch-set-next-ordinal! CURRENT-ARCH
 320                                   (- (arch-next-ordinal CURRENT-ARCH) 2))
 321           )
 322
 323         (begin
 324           logit 3 "    failed ifield assertions.\n")))
 325
 326   *UNSPECIFIED*
 327 )
 328
 329 ; Instantiate all sub-insns of MULTI-INSN.
 330 ; ??? Might be better to return the list of insns, rather than add them to
 331 ; the global list, and leave it to the caller to add them.
 332
 333 (define (multi-insn-instantiate! multi-insn)
 334   ; We shouldn't get called more than once.
 335   (assert (not (multi-insn-sub-insns multi-insn)))
 336
 337   (let ((iflds (insn-iflds multi-insn)))
 338
 339     ; What we want to create here is the set of all "anyof" alternatives.
 340     ; From that we create one <insn> per alternative.
 341
 342     (let* ((anyof-iflds (find ifld-anyof-operand? iflds))
 343            (anyof-operands (map ifld-get-value anyof-iflds)))
 344
 345       (assert (all-true? (map anyof-operand? anyof-operands)))
 346       (logit 4 "  anyof: " (map obj:name anyof-operands) "\n")
 347       (logit 4 "    choices: "
 348              (map (lambda (l) (map obj:name l))
 349                   (map anyof-choices anyof-operands))
 350              "\n")
 351
 352       ; Iterate over all combinations.
 353       ; TODO is a list with one element for each <anyof-operand>.
 354       ; Each element is in turn a list of all choices (<derived-operands>'s)
 355       ; for the <anyof-operand>.  Note that some of these values may be
 356       ; derived from nested <anyof-operand>'s.
 357       ; ??? anyof-all-choices should cache the results. [Still useful?]
 358       ; ??? Need to cache results of assertion processing in addition or
 359       ; instead of anyof-all-choices. [Still useful?]
 360
 361       (let* ((todo (map anyof-all-choices anyof-operands))
 362              (lengths (map length todo))
 363              (total (apply * lengths)))
 364
 365         (logit 2 "Instantiating " total " multi-insns for "
 366                (obj:name multi-insn) " ...\n")
 367
 368         ; ??? One might prefer a `do' loop here, but every time I see one I
 369         ; have to spend too long remembering its syntax.
 370         (let loop ((i 0))
 371           (if (< i total)
 372               (let* ((indices (split-value lengths i))
 373                      (anyof-instances (map list-ref todo indices)))
 374                 (logit 4 "Derived: " (map obj:name anyof-instances) "\n")
 375                 (/sub-insn-make! multi-insn anyof-operands anyof-instances)
 376                 (loop (+ i 1))))))))
 377
 378   *UNSPECIFIED*
 379 )
 380 \f
 381 ; Parse an instruction description.
 382 ; This is the main routine for building an insn object from a
 383 ; description in the .cpu file.
 384 ; All arguments are in raw (non-evaluated) form.
 385 ; The result is the parsed object or #f if insn isn't for selected mach(s).
 386
 387 (define (/insn-parse context name comment attrs syntax fmt ifield-assertion
 388                      semantics timing)
 389   (logit 2 "Processing insn " name " ...\n")
 390
 391   ;; Pick out name first to augment the error context.
 392   (let* ((name (parse-name context name))
 393          (context (context-append-name context name))
 394          (atlist-obj (atlist-parse context attrs "cgen_insn"))
 395          (isa-name-list (atlist-attr-value atlist-obj 'ISA #f)))
 396
 397     ;; Verify all specified ISAs are valid.
 398     (if (not (all-true? (map current-isa-lookup isa-name-list)))
 399         (parse-error context "unknown isa in isa list" isa-name-list))
 400
 401     (if (keep-atlist? atlist-obj #f)
 402
 403         (let ((ifield-assertion (if (and ifield-assertion
 404                                          (not (null? ifield-assertion)))
 405                                     (rtx-canonicalize context
 406                                                       'DFLT ;; BI?
 407                                                       isa-name-list nil
 408                                                       ifield-assertion)
 409                                     #f))
 410               (semantics (if (not (null? semantics))
 411                              semantics
 412                              #f))
 413               (format (/parse-insn-format
 414                        (context-append context " format")
 415                        (and (not (atlist-has-attr? atlist-obj 'VIRTUAL))
 416                             (reader-verify-iformat? CURRENT-READER))
 417                        isa-name-list
 418                        fmt))
 419               (comment (parse-comment context comment))
 420               ; If there are no semantics, mark this as an alias.
 421               ; ??? Not sure this makes sense for multi-insns.
 422               (atlist-obj (if semantics
 423                               atlist-obj
 424                               (atlist-cons (bool-attr-make 'ALIAS #t)
 425                                            atlist-obj)))
 426               (syntax (parse-syntax context syntax))
 427               (timing (parse-insn-timing context timing))
 428               )
 429
 430           (if (anyof-operand-format? format)
 431
 432               (make <multi-insn>
 433                 (context-location context)
 434                 name comment atlist-obj
 435                 syntax
 436                 format
 437                 ifield-assertion
 438                 semantics
 439                 timing)
 440
 441               (make <insn>
 442                 (context-location context)
 443                 name comment atlist-obj
 444                 syntax
 445                 format
 446                 ifield-assertion
 447                 semantics
 448                 timing)))
 449
 450         (begin
 451           (logit 2 "Ignoring " name ".\n")
 452           #f)))
 453 )
 454
 455 ; Read an instruction description.
 456 ; This is the main routine for analyzing instructions in the .cpu file.
 457 ; This is also used to create virtual insns by apps like simulators.
 458 ; CONTEXT is a <context> object for error messages.
 459 ; ARG-LIST is an associative list of field name and field value.
 460 ; /insn-parse is invoked to create the <insn> object.
 461
 462 (define (insn-read context . arg-list)
 463   (let (
 464         (name nil)
 465         (comment "")
 466         (attrs nil)
 467         (syntax nil)
 468         (fmt nil)
 469         (ifield-assertion nil)
 470         (semantics nil)
 471         (timing nil)
 472         )
 473
 474     ; Loop over each element in ARG-LIST, recording what's found.
 475     (let loop ((arg-list arg-list))
 476       (if (null? arg-list)
 477           nil
 478           (let ((arg (car arg-list))
 479                 (elm-name (caar arg-list)))
 480             (case elm-name
 481               ((name) (set! name (cadr arg)))
 482               ((comment) (set! comment (cadr arg)))
 483               ((attrs) (set! attrs (cdr arg)))
 484               ((syntax) (set! syntax (cadr arg)))
 485               ((format) (set! fmt (cadr arg)))
 486               ((ifield-assertion) (set! ifield-assertion (cadr arg)))
 487               ((semantics) (set! semantics (cadr arg)))
 488               ((timing) (set! timing (cdr arg)))
 489               (else (parse-error context "invalid insn arg" arg)))
 490             (loop (cdr arg-list)))))
 491
 492     ; Now that we've identified the elements, build the object.
 493     (/insn-parse context name comment attrs syntax fmt ifield-assertion
 494                  semantics timing))
 495 )
 496
 497 ; Define an instruction object, name/value pair list version.
 498
 499 (define define-insn
 500   (lambda arg-list
 501     (let ((i (apply insn-read (cons (make-current-context "define-insn")
 502                                     arg-list))))
 503       (if i
 504           (current-insn-add! i))
 505       i))
 506 )
 507
 508 ; Define an instruction object, all arguments specified.
 509
 510 (define (define-full-insn name comment attrs syntax fmt ifield-assertion
 511           semantics timing)
 512   (let ((i (/insn-parse (make-current-context "define-full-insn")
 513                         name comment attrs
 514                         syntax fmt ifield-assertion
 515                         semantics timing)))
 516     (if i
 517         (current-insn-add! i))
 518     i)
 519 )
 520 \f
 521 ; Parsing support.
 522
 523 ; Parse an insn syntax field.
 524 ; SYNTAX is either a string or a list of strings, each element of which may
 525 ; in turn be a list of strings.
 526 ; ??? Not sure this extra flexibility is worth it yet.
 527
 528 (define (parse-syntax context syntax)
 529   (cond ((list? syntax)
 530          (string-map (lambda (elm) (parse-syntax context elm)) syntax))
 531         ((or (string? syntax) (symbol? syntax))
 532          syntax)
 533         (else (parse-error context "improper syntax" syntax)))
 534 )
 535
 536 ; Subroutine of /parse-insn-format to parse a symbol ifield spec.
 537
 538 (define (/parse-insn-format-symbol context isa-name-list sym)
 539   (let ((op (current-op-lookup sym isa-name-list)))
 540     (if op
 541         (cond ((derived-operand? op)
 542                ; There is a one-to-one relationship b/w derived operands and
 543                ; the associated derived ifield.
 544                (let ((ifld (op-ifield op)))
 545                  (assert (derived-ifield? ifld))
 546                  ifld))
 547               ((anyof-operand? op)
 548                (ifld-new-value f-anyof op))
 549               (else
 550                (let ((ifld (op-ifield op)))
 551                  (ifld-new-value ifld op))))
 552         ; An insn-enum?
 553         (let ((e (ienum-lookup-val sym)))
 554           (if e
 555               (ifld-new-value (ienum:fld (cdr e)) (car e))
 556               (parse-error context "bad format element, expecting symbol to be operand or insn enum" sym)))))
 557 )
 558
 559 ; Subroutine of /parse-insn-format to parse an (ifield-name value) ifield spec.
 560 ;
 561 ; The last element is the ifield's value.  It must be an integer.
 562 ; ??? Whether it can be negative is still unspecified.
 563 ; ??? While there might be a case where allowing floating point values is
 564 ; desirable, supporting them would require precise conversion routines.
 565 ; They should be rare enough that we instead punt.
 566 ;
 567 ; ??? May wish to support something like "(% startbit bitsize value)".
 568 ;
 569 ; ??? Error messages need improvement, but that's generally true of cgen.
 570
 571 (define (/parse-insn-format-ifield-spec context ifld ifld-spec)
 572   (if (!= (length ifld-spec) 2)
 573       (parse-error context "bad ifield format, should be (ifield-name value)" ifld-spec))
 574
 575   (let ((value (cadr ifld-spec)))
 576     ; ??? This use to allow (ifield-name operand-name).  That's how
 577     ; `operand-name' elements are handled, but there's no current need
 578     ; to handle (ifield-name operand-name).
 579     (cond ((integer? value)
 580            (ifld-new-value ifld value))
 581           ((symbol? value)
 582            (let ((e (enum-lookup-val value)))
 583              (if (not e)
 584                  (parse-error context "symbolic ifield value not an enum" ifld-spec))
 585              (ifld-new-value ifld (car e))))
 586           (else
 587            (parse-error context "ifield value not an integer or enum" ifld-spec))))
 588 )
 589
 590 ; Subroutine of /parse-insn-format to parse an
 591 ; (ifield-name value) ifield spec.
 592 ; ??? There is room for growth in the specification syntax here.
 593 ; Possibilities are (ifield-name|operand-name [options] [value]).
 594
 595 (define (/parse-insn-format-list context isa-name-list spec)
 596   (let ((ifld (current-ifld-lookup (car spec) isa-name-list)))
 597     (if ifld
 598         (/parse-insn-format-ifield-spec context ifld spec)
 599         (parse-error context "unknown ifield" spec)))
 600 )
 601
 602 ; Subroutine of /parse-insn-format to simplify it.
 603 ; Parse the provided iformat spec and return the list of ifields.
 604 ; ISA-NAME-lIST is the ISA attribute of the containing insn.
 605
 606 (define (/parse-insn-iformat-iflds context isa-name-list fld-list)
 607   (if (null? fld-list)
 608       nil ; field list unspecified
 609       (case (car fld-list)
 610         ((+) (map (lambda (fld)
 611                     (let ((f (if (string? fld)
 612                                  (string->symbol fld)
 613                                  fld)))
 614                       (cond ((symbol? f)
 615                              (/parse-insn-format-symbol context isa-name-list f))
 616                             ((and (list? f)
 617                                   ; ??? This use to allow <ifield> objects
 618                                   ; in the `car' position.  Checked for below.
 619                                   (symbol? (car f)))
 620                              (/parse-insn-format-list context isa-name-list f))
 621                             (else
 622                              (if (and (list? f)
 623                                       (ifield? (car f)))
 624                                  (parse-error context "FIXME: <ifield> object in format spec" f))
 625                              (parse-error context "bad format element, neither symbol nor ifield spec" f)))))
 626                   (cdr fld-list)))
 627         ((=) (begin
 628                (if (or (!= (length fld-list) 2)
 629                        (not (symbol? (cadr fld-list))))
 630                    (parse-error context
 631                                 "bad `=' format spec, should be `(= insn-name)'"
 632                                 fld-list))
 633                (let ((insn (current-insn-lookup (cadr fld-list) isa-name-list)))
 634                  (if (not insn)
 635                      (parse-error context "unknown insn" (cadr fld-list)))
 636                  (insn-iflds insn))))
 637         (else
 638          (parse-error context "format must begin with `+' or `='" fld-list))
 639         ))
 640 )
 641
 642 ; Given an insn format field from a .cpu file, replace it with a list of
 643 ; ifield objects with the values assigned.
 644 ; ISA-NAME-LIST is the ISA attribute of the containing insn.
 645 ; If VERIFY? is non-#f, perform various checks on the format.
 646 ;
 647 ; An insn format field is a list of ifields that make up the instruction.
 648 ; All bits must be specified, including reserved bits
 649 ; [at present little checking is made of this, but the rule still holds].
 650 ;
 651 ; A normal entry begins with `+' and then consist of the following:
 652 ; - operand name
 653 ; - (ifield-name [options] value)
 654 ; - (operand-name [options] [value])
 655 ; - insn ifield enum
 656 ;
 657 ; Example: (+ OP1_ADD (f-res2 0) dr src1 (f-src2 1) (f-res1 #xea))
 658 ;
 659 ; where OP1_ADD is an enum, dr and src1 are operands, and f-src2 and f-res1
 660 ; are ifield's.  The `+' allows for future extension.
 661 ;
 662 ; The other form of entry begins with `=' and is followed by an instruction
 663 ; name that has the same format.  The specified instruction must already be
 664 ; defined.  Instructions with this form typically also include an
 665 ; `ifield-assertion' spec to keep them separate.
 666 ;
 667 ; An empty field list is ok.  This means it's unspecified.
 668 ; VIRTUAL insns have this.
 669 ;
 670 ; This is one of the more important routines to be efficient.
 671 ; It's called for each instruction, and is one of the more expensive routines
 672 ; in insn parsing.
 673
 674 (define (/parse-insn-format context verify? isa-name-list ifld-list)
 675   (let* ((parsed-ifld-list
 676           (/parse-insn-iformat-iflds context isa-name-list ifld-list)))
 677
 678     ;; NOTE: We could sort the fields here, but it introduces differences
 679     ;; in the generated opcodes files.  Later it might be a good thing to do
 680     ;; but keeping the output consistent is important right now.
 681     ;;   (sorted-ifld-list (sort-ifield-list parsed-ifld-list
 682     ;;                                       (not (current-arch-insn-lsb0?))))
 683     ;; The rest of the code assumes the list isn't sorted.
 684     ;; Is there a benefit to removing this assumption?  Note that
 685     ;; multi-ifields can be discontiguous, so the sorting isn't perfect.
 686
 687     (if verify?
 688
 689         ;; Just pick the first ISA, the base len for each should be the same.
 690         ;; If not this is caught by compute-insn-base-mask-length.
 691         (let* ((isa (current-isa-lookup (car isa-name-list)))
 692                (base-len (isa-base-insn-bitsize isa))
 693                (pretty-print-iflds (lambda (iflds)
 694                                      (if (null? iflds)
 695                                          " none provided"
 696                                          (string-map (lambda (f)
 697                                                        (string-append " "
 698                                                                       (ifld-pretty-print f)))
 699                                                      iflds)))))
 700
 701           ;; Perform some error checking.
 702           ;; Look for overlapping ifields and missing bits.
 703           ;; With derived ifields this is really hard, so only do the base insn
 704           ;; for now.  Do the simple test for now, it doesn't catch everything,
 705           ;; but it should catch a lot.
 706           ;; ??? One thing we don't catch yet is overlapping bits.
 707
 708           (let* ((base-iflds (find (lambda (f)
 709                                      (not (ifld-beyond-base? f)))
 710                                    (ifields-simple-ifields parsed-ifld-list)))
 711                  (base-iflds-length (apply + (map ifld-length base-iflds))))
 712
 713             ;; FIXME: We don't use parse-error here because some existing ports
 714             ;; have problems, and I don't have time to fix them right now.
 715             (cond ((< base-iflds-length base-len)
 716                    (parse-warning context
 717                                   (string-append
 718                                    "insufficient number of bits specified in base insn\n"
 719                                    "ifields:"
 720                                    (pretty-print-iflds parsed-ifld-list)
 721                                    "\nprovided spec")
 722                                   ifld-list))
 723                   ((> base-iflds-length base-len)
 724                    (parse-warning context
 725                                   (string-append
 726                                    "too many or duplicated bits specified in base insn\n"
 727                                    "ifields:"
 728                                    (pretty-print-iflds parsed-ifld-list)
 729                                    "\nprovided spec")
 730                                   ifld-list)))
 731
 732             ;; Detect duplicate ifields.
 733             (if (!= (length base-iflds)
 734                     (length (obj-list-nub base-iflds)))
 735                 (parse-error-continuable context
 736                                          "duplicate ifields present"
 737                                          ifld-list))
 738             )
 739           ))
 740
 741     parsed-ifld-list)
 742 )
 743
 744 ; Return a boolean indicating if IFLD-LIST contains anyof operands.
 745
 746 (define (anyof-operand-format? ifld-list)
 747   (any-true? (map (lambda (f)
 748                     (or (ifld-anyof? f)
 749                         (derived-ifield? f)))
 750                   ifld-list))
 751 )
 752 \f
 753 ; Insn utilities.
 754 ; ??? multi-insn support wip, may require changes here.
 755
 756 ; Return a boolean indicating if INSN is an alias insn.
 757
 758 (define (insn-alias? insn)
 759   (obj-has-attr? insn 'ALIAS)
 760 )
 761
 762 ; Return a list of instructions that are not aliases in INSN-LIST.
 763
 764 (define (non-alias-insns insn-list)
 765   (find (lambda (insn)
 766           (not (insn-alias? insn)))
 767         insn-list)
 768 )
 769
 770 ; Return a boolean indicating if INSN is a "real" INSN
 771 ; (not ALIAS and not VIRTUAL and not a <multi-insn>).
 772
 773 (define (insn-real? insn)
 774   (let ((atlist (obj-atlist insn)))
 775     (and (not (atlist-has-attr? atlist 'ALIAS))
 776          (not (atlist-has-attr? atlist 'VIRTUAL))
 777          (not (multi-insn? insn))))
 778 )
 779
 780 ; Return a list of real instructions in INSN-LIST.
 781
 782 (define (real-insns insn-list)
 783   (find insn-real? insn-list)
 784 )
 785
 786 ; Return a boolean indicating if INSN is a virtual insn.
 787
 788 (define (insn-virtual? insn)
 789   (obj-has-attr? insn 'VIRTUAL)
 790 )
 791
 792 ; Return a list of virtual instructions in INSN-LIST.
 793
 794 (define (virtual-insns insn-list)
 795   (find insn-virtual? insn-list)
 796 )
 797
 798 ; Return a list of non-alias/non-pbb insns in INSN-LIST.
 799
 800 (define (non-alias-pbb-insns insn-list)
 801   (find (lambda (insn)
 802           (let ((atlist (obj-atlist insn)))
 803             (and (not (atlist-has-attr? atlist 'ALIAS))
 804                  (not (atlist-has-attr? atlist 'PBB)))))
 805         insn-list)
 806 )
 807
 808 ; Return a list of multi-insns in INSN-LIST.
 809
 810 (define (multi-insns insn-list)
 811   (find multi-insn? insn-list)
 812 )
 813
 814 ; And the opposite:
 815
 816 (define (non-multi-insns insn-list)
 817   (find (lambda (insn) (not (multi-insn? insn))) insn-list)
 818 )
 819
 820 ; Filter out instructions whose ifield patterns are strict supersets of
 821 ; another, keeping the less general cousin.  Used to resolve ambiguity
 822 ; when there are no more bits to consider.
 823
 824 (define (filter-non-specialized-ambiguous-insns insn-list)
 825   (logit 3 "Filtering " (length insn-list) " instructions for non specializations.\n")
 826   (find (lambda (insn)
 827           (let* ((i-mask (insn-base-mask insn))
 828                  (i-mask-len (insn-base-mask-length insn))
 829                  (i-value (insn-value insn))
 830                  (subset-insn (find-first
 831                                (lambda (insn2) ; insn2: possible submatch (more mask bits)
 832                                     (let ((i2-mask (insn-base-mask insn2))
 833                                           (i2-mask-len (insn-base-mask-length insn2))
 834                                           (i2-value (insn-value insn2)))
 835                                       (and (not (eq? insn insn2))
 836                                            (= i-mask-len i2-mask-len)
 837                                            (mask-superset? i-mask i-value i2-mask i2-value))))
 838                                   insn-list))
 839                  (keep? (not subset-insn)))
 840             (if (not keep?)
 841                 (logit 2
 842                        "Instruction " (obj:name insn) " specialization-filtered by "
 843                        (obj:name subset-insn) "\n"))
 844             keep?))
 845         insn-list)
 846 )
 847
 848 ; Filter out instructions whose ifield patterns are identical.
 849
 850 (define (filter-identical-ambiguous-insns insn-list)
 851   (logit 3 "Filtering " (length insn-list) " instructions for identical variants.\n")
 852   (let loop ((l insn-list) (result nil))
 853     (cond ((null? l) (reverse! result))
 854           ((find-identical-insn (car l) (cdr l)) (loop (cdr l) result))
 855           (else (loop (cdr l) (cons (car l) result)))
 856           )
 857     )
 858 )
 859
 860 (define (find-identical-insn insn insn-list)
 861   (let ((i-mask (insn-base-mask insn))
 862         (i-mask-len (insn-base-mask-length insn))
 863         (i-value (insn-value insn)))
 864     (find-first
 865      (lambda (insn2)
 866        (let ((i2-mask (insn-base-mask insn2))
 867              (i2-mask-len (insn-base-mask-length insn2))
 868              (i2-value (insn-value insn2)))
 869          (and (= i-mask-len i2-mask-len)
 870               (= i-mask i2-mask)
 871               (= i-value i2-value))))
 872        insn-list))
 873 )
 874
 875 ; Helper function for above: does (m1,v1) match a STRICT superset of (m2,v2) ?
 876 ;
 877 ; eg> mask-superset? #b1100 #b1000 #b1110 #b1010 -> #t
 878 ; eg> mask-superset? #b1100 #b1000 #b1010 #b1010 -> #f
 879 ; eg> mask-superset? #b1100 #b1000 #b1110 #b1100 -> #f
 880 ; eg> mask-superset? #b1100 #b1000 #b1100 #b1000 -> #f
 881
 882 (define (mask-superset? m1 v1 m2 v2)
 883   (let ((result
 884          (and (= (cg-logand m1 m2) m1)
 885               (= (cg-logand m1 v1) (cg-logand m1 v2))
 886               (not (and (= m1 m2) (= v1 v2))))))
 887     (if result (logit 4
 888                       "(" (number->string m1 16) "," (number->string v1 16) ")"
 889                       " contains "
 890                       "(" (number->string m2 16) "," (number->string v2 16) ")"
 891                       "\n"))
 892     result)
 893 )
 894
 895 ;; Return a boolean indicating if INSN is a cti [control transfer insn]
 896 ;; according the its attributes.
 897 ;;
 898 ;; N.B. This only looks at the insn's atlist, which only contains what was
 899 ;; specified in the .cpu file.  .cpu files are not required to manually mark
 900 ;; CTI insns.  Basically this exists as an escape hatch in case semantic-attrs
 901 ;; gets it wrong.
 902
 903 (define (insn-cti-attr? insn)
 904   (atlist-cti? (obj-atlist insn))
 905 )
 906
 907 ;; Return a boolean indicating if INSN is a cti [control transfer insn].
 908 ;; This includes SKIP-CTI insns even though they don't terminate a basic block.
 909 ;; ??? SKIP-CTI insns are wip, waiting for more examples of how they're used.
 910 ;;
 911 ;; N.B. This requires the <sformat> of INSN.
 912
 913 (define (insn-cti? insn)
 914   (or (insn-cti-attr? insn)
 915       (sfmt-cti? (insn-sfmt insn)))
 916 )
 917
 918 ; Return a boolean indicating if INSN can be executed in parallel.
 919 ; Such insns are required to have enum attribute PARALLEL != NO.
 920 ; This is worded specifically to allow the PARALLEL attribute to have more
 921 ; than just NO/YES values (should a target want to do so).
 922 ; This specification may not be sufficient, but the intent is explicit.
 923
 924 (define (insn-parallel? insn)
 925   (let ((atval (obj-attr-value insn 'PARALLEL)))
 926     (and atval (not (eq? atval 'NO))))
 927 )
 928
 929 ; Return a list of the insns that support parallel execution in INSN-LIST.
 930
 931 (define (parallel-insns insn-list)
 932   (find insn-parallel? insn-list)
 933 )
 934 \f
 935 ; Instruction field utilities.
 936
 937 ; Return a boolean indicating if INSN has ifield named F-NAME.
 938
 939 (define (insn-has-ifield? insn f-name)
 940   (->bool (object-assq f-name (insn-iflds insn)))
 941 )
 942 \f
 943 ; Insn opcode value utilities.
 944
 945 ; Given INSN, return the length in bits of the base mask (insn-base-mask).
 946
 947 (define (insn-base-mask-length insn)
 948   (ifmt-mask-length (insn-ifmt insn))
 949 )
 950
 951 ; Given INSN, return the bitmask of constant values (the opcode field)
 952 ; in the base part.
 953
 954 (define (insn-base-mask insn)
 955   (ifmt-mask (insn-ifmt insn))
 956 )
 957
 958 ; Given INSN, return the sum of the constant values in the insn
 959 ; (i.e. the opcode field).
 960 ;
 961 ; See also (compute-insn-base-mask).
 962 ;
 963 ; FIXME: For non-fixed-length ISAs, using this doesn't feel right.
 964
 965 (define (insn-value insn)
 966   (if (elm-get insn '/insn-value)
 967       (elm-get insn '/insn-value)
 968       (let* ((base-len (insn-base-mask-length insn))
 969              (value (apply +
 970                            (map (lambda (fld) (ifld-value fld base-len (ifld-get-value fld)))
 971                                 (find ifld-constant?
 972                                       (ifields-base-ifields (insn-iflds insn))))
 973                            )))
 974         (elm-set! insn '/insn-value value)
 975         value))
 976 )
 977
 978 ;; Return the base value of INSN.
 979
 980 (define (insn-base-value insn)
 981   (if (elm-get insn '/insn-base-value)
 982       (elm-get insn '/insn-base-value)
 983       (let* ((base-len (insn-base-mask-length insn))
 984              (constant-base-iflds
 985               (find (lambda (f)
 986                       (and (ifld-constant? f)
 987                            (not (ifld-beyond-base? f))))
 988                     (ifields-base-ifields (insn-iflds insn))))
 989              (base-value (apply +
 990                                 (map (lambda (f)
 991                                        (ifld-value f base-len (ifld-get-value f)))
 992                                      constant-base-iflds))))
 993         (elm-set! insn '/insn-base-value base-value)
 994         base-value))
 995 )
 996 \f
 997 ; Insn operand utilities.
 998
 999 ; Lookup operand SEM-NAME in INSN.
1000
1001 (define (insn-lookup-op insn sem-name)
1002   (or (op:lookup-sem-name (sfmt-in-ops (insn-sfmt insn)) sem-name)
1003       (op:lookup-sem-name (sfmt-out-ops (insn-sfmt insn)) sem-name))
1004 )
1005 \f
1006 ; Insn syntax utilities.
1007
1008 ; Create a list of syntax strings broken up into a list of characters and
1009 ; operand objects.
1010
1011 (define (syntax-break-out syntax isa-name-list)
1012   (let ((result nil))
1013     ; ??? The style of the following could be more Scheme-like.  Later.
1014     (let loop ()
1015       (if (> (string-length syntax) 0)
1016           (begin
1017             (cond
1018              ; Handle escaped syntax metacharacters.
1019              ((char=? #\\ (string-ref syntax 0))
1020               (begin
1021                 (if (= (string-length syntax) 1)
1022                     (parse-error context "syntax-break-out: missing char after '\\' in " syntax))
1023                 (set! result (cons (substring syntax 1 2) result))
1024                 (set! syntax (string-drop 2 syntax))))
1025                 ; Handle operand reference.
1026              ((char=? #\$ (string-ref syntax 0))
1027               ; Extract the symbol from the string, get the operand.
1028               ; FIXME: Will crash if $ is last char in string.
1029               (if (char=? #\{ (string-ref syntax 1))
1030                   (let ((n (string-index syntax #\})))
1031                     (set! result (cons (current-op-lookup
1032                                         (string->symbol
1033                                          (substring syntax 2 n))
1034                                         isa-name-list)
1035                                        result))
1036                     (set! syntax (string-drop (+ 1 n) syntax)))
1037                   (let ((n (id-len (string-drop1 syntax))))
1038                     (set! result (cons (current-op-lookup
1039                                         (string->symbol
1040                                          (substring syntax 1 (+ 1 n)))
1041                                         isa-name-list)
1042                                        result))
1043                     (set! syntax (string-drop (+ 1 n) syntax)))))
1044              ; Handle everything else.
1045              (else (set! result (cons (substring syntax 0 1) result))
1046                    (set! syntax (string-drop1 syntax))))
1047             (loop))))
1048     (reverse result))
1049 )
1050
1051 ; Given a list of syntax elements (e.g. the result of syntax-break-out),
1052 ; create a syntax string.
1053
1054 (define (syntax-make elements)
1055   (apply string-append
1056          (map (lambda (e)
1057                 (cond ((char? e)
1058                        (string "\\" e))
1059                       ((string? e)
1060                        e)
1061                       (else
1062                        (assert (operand? e))
1063                        (string-append "${" (obj:str-name e) "}"))))
1064               elements))
1065 )
1066 \f
1067 ; Called before a .cpu file is read in.
1068
1069 (define (insn-init!)
1070   (reader-add-command! 'define-insn
1071                        "\
1072 Define an instruction, name/value pair list version.
1073 "
1074                        nil 'arg-list define-insn)
1075   (reader-add-command! 'define-full-insn
1076                        "\
1077 Define an instruction, all arguments specified.
1078 "
1079                        nil '(name comment attrs syntax fmt ifield-assertion semantics timing)
1080                        define-full-insn)
1081
1082   *UNSPECIFIED*
1083 )
1084
1085 ; Called before a .cpu file is read in to install any builtins.
1086
1087 (define (insn-builtin!)
1088   ; Standard insn attributes.
1089   ; ??? Some of these can be combined into one.
1090
1091   (define-attr '(for insn) '(type boolean) '(name UNCOND-CTI) '(comment "unconditional cti"))
1092
1093   (define-attr '(for insn) '(type boolean) '(name COND-CTI) '(comment "conditional cti"))
1094
1095   ; SKIP-CTI: one or more immediately following instructions are conditionally
1096   ; executed (or skipped)
1097   (define-attr '(for insn) '(type boolean) '(name SKIP-CTI) '(comment "skip cti"))
1098
1099   ; DELAY-SLOT: insn has one or more delay slots (wip)
1100   (define-attr '(for insn) '(type boolean) '(name DELAY-SLOT) '(comment "insn has a delay slot"))
1101
1102   ; RELAXABLE: Insn has one or more identical but larger variants.
1103   ; The assembler tries this one first and then the relaxation phase
1104   ; switches to the larger ones as necessary.
1105   ; All insns of identical behaviour have a RELAX_FOO attribute that groups
1106   ; them together.
1107   ; FIXME: This is a case where we need one attribute with several values.
1108   ; Presently each RELAX_FOO will use up a bit.
1109   (define-attr '(for insn) '(type boolean) '(name RELAXABLE)
1110     '(comment "insn is relaxable"))
1111
1112   ; RELAXED: Large relaxable variant.  Avoided by assembler in first pass.
1113   (define-attr '(for insn) '(type boolean) '(name RELAXED)
1114     '(comment "relaxed form of insn"))
1115
1116   ; NO-DIS: For macro insns, do not use during disassembly.
1117   (define-attr '(for insn) '(type boolean) '(name NO-DIS) '(comment "don't use for disassembly"))
1118
1119   ; PBB: Virtual insn used for PBB support.
1120   (define-attr '(for insn) '(type boolean) '(name PBB) '(comment "virtual insn used for PBB support"))
1121
1122   ; DECODE-SPLIT: insn resulted from decode-split processing
1123   (define-attr '(for insn) '(type boolean) '(name DECODE-SPLIT) '(comment "insn split from another insn for decoding purposes") '(attrs META))
1124
1125   ; Also (defined elsewhere):
1126   ; VIRTUAL: Helper insn used by the simulator.
1127
1128   *UNSPECIFIED*
1129 )
1130
1131 ; Called after the .cpu file has been read in.
1132
1133 (define (insn-finish!)
1134   *UNSPECIFIED*
1135 )