| 1 |
;;; |
| 2 |
;;; Register set |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2024 Shiro Kawai <[email protected]> |
| 5 |
;;; |
| 6 |
;;; Redistribution and use in source and binary forms, with or without |
| 7 |
;;; modification, are permitted provided that the following conditions |
| 8 |
;;; are met: |
| 9 |
;;; |
| 10 |
;;; 1. Redistributions of source code must retain the above copyright |
| 11 |
;;; notice, this list of conditions and the following disclaimer. |
| 12 |
;;; |
| 13 |
;;; 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
;;; notice, this list of conditions and the following disclaimer in the |
| 15 |
;;; documentation and/or other materials provided with the distribution. |
| 16 |
;;; |
| 17 |
;;; 3. Neither the name of the authors nor the names of its contributors |
| 18 |
;;; may be used to endorse or promote products derived from this |
| 19 |
;;; software without specific prior written permission. |
| 20 |
;;; |
| 21 |
;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
;;; |
| 33 |
|
| 34 |
;; A common infrastructure to treat register set as a bitmap. |
| 35 |
;; Each processor implementation should provide a vector of |
| 36 |
;; register names (regvec). |
| 37 |
|
| 38 |
;; Technically, we could implement this on top of srfi-209 (enums); however, |
| 39 |
;; this module is used from Gauche internals and we don't want to depend |
| 40 |
;; on another srfi. |
| 41 |
|
| 42 |
(define-module lang.asm.regset |
| 43 |
(use util.match) |
| 44 |
(use gauche.bitvector) |
| 45 |
(export <regset> make-regset regset regset-copy |
| 46 |
regset->list list->regset |
| 47 |
regset-union regset-union! |
| 48 |
regset-difference regset-difference! |
| 49 |
regset-intersection regset-intersection!) |
| 50 |
) |
| 51 |
(select-module lang.asm.regset) |
| 52 |
|
| 53 |
|
| 54 |
(define-class <regset> (<sequence>) |
| 55 |
(;; all slots are private |
| 56 |
(%regvec :init-keyword :regvec) |
| 57 |
(%bits :init-keyword :bits))) |
| 58 |
|
| 59 |
(define-method write-object ((regset <regset>) port) |
| 60 |
(format port "#<regset ~:w>" (regset->list regset))) |
| 61 |
|
| 62 |
;;; Constructors |
| 63 |
|
| 64 |
(define (make-regset regvec :optional (regs '())) |
| 65 |
(assume-type regvec <vector>) |
| 66 |
(let1 rs (make <regset> |
| 67 |
:regvec regvec |
| 68 |
:bits (make-bitvector (vector-length regvec) 0)) |
| 69 |
(if (null? regs) |
| 70 |
rs |
| 71 |
(apply regset-adjoin! rs regs)))) |
| 72 |
|
| 73 |
(define (regset regvec . regs) (make-regset regvec regs)) |
| 74 |
|
| 75 |
(define (regset-copy regset) |
| 76 |
(make <regset> |
| 77 |
:regvec (~ regset'%regvec) |
| 78 |
:bits (bitvector-copy (~ regset'%bits)))) |
| 79 |
|
| 80 |
;;; Internal utilities |
| 81 |
|
| 82 |
(define (%regname->pos regvec reg) |
| 83 |
;; NB: We roll our own to avoid depending on scheme.vector |
| 84 |
(let1 len (vector-length regvec) |
| 85 |
(let loop ([i 0]) |
| 86 |
(cond [(= i len) (error "No such register:" reg)] |
| 87 |
[(eq? (vector-ref regvec i) reg) i] |
| 88 |
[else (loop (+ i 1))])))) |
| 89 |
|
| 90 |
(define (%pos->regname regvec pos) |
| 91 |
(vector-ref regvec pos)) |
| 92 |
|
| 93 |
;;; Converters |
| 94 |
|
| 95 |
(define (regset->list regset) |
| 96 |
(assume-type regset <regset>) |
| 97 |
(bitvector-value-map-index->list |
| 98 |
(cute %pos->regname (~ regset'%regvec)) |
| 99 |
(~ regset'%bits) |
| 100 |
#t)) |
| 101 |
|
| 102 |
(define (list->regset regvec lis) |
| 103 |
(make-regset regvec lis)) |
| 104 |
|
| 105 |
;;; Set ops |
| 106 |
|
| 107 |
(define (regset-adjoin! regset . regs) |
| 108 |
(define regvec (~ regset'%regvec)) |
| 109 |
(let loop ([regs regs] [bv (~ regset'%bits)]) |
| 110 |
(match regs |
| 111 |
[(reg . regs) (loop regs (bitvector-set! bv (%regname->pos regvec reg) 1))] |
| 112 |
[_ (set! (~ regset'%bits) bv) regset]))) |
| 113 |
|
| 114 |
(define (regset-adjoin regset . regs) |
| 115 |
(apply regset-adjoin! (regset-copy regset) regs)) |
| 116 |
|
| 117 |
(define (regset-union! regset1 . regsets) |
| 118 |
(let1 bits (apply bitvector-ior! (~ regset1'%bits) |
| 119 |
(map (cut ~ <> '%bits) regsets)) |
| 120 |
(set! (~ regset1'%bits) bits) |
| 121 |
regset1)) |
| 122 |
|
| 123 |
(define (regset-union regset1 . regsets) |
| 124 |
(apply regset-union! (regset-copy regset) regset1 regsets)) |
| 125 |
|
| 126 |
(define (regset-intersection! regset1 . regsets) |
| 127 |
(let1 bits (apply bitvector-and! (~ regset1'%bits) |
| 128 |
(map (cut ~ <> '%bits) regsets)) |
| 129 |
(set! (~ regset1'%bits) bits) |
| 130 |
regset1)) |
| 131 |
|
| 132 |
(define (regset-intersection regset1 . regsets) |
| 133 |
(apply regset-intersection! (regset-copy regset) regset1 regsets)) |
| 134 |
|
| 135 |
(define (regset-difference! regset1 . regsets) |
| 136 |
(let1 bits (fold (^[rs r] (bitvector-andc2! r (~ rs'%bits))) |
| 137 |
(~ regset1'%bits) |
| 138 |
regsets) |
| 139 |
(set! (~ regset1'%bits) bits) |
| 140 |
regset1)) |
| 141 |
|
| 142 |
(define (regset-difference regset1 regsets) |
| 143 |
(apply regset-difference (regset-copy regset) regsets)) |