2 ; Copyright (C) 2000, 2005, 2006, 2007, 2009, 2010 Red Hat, Inc.
3 ; This file is part of CGEN.
4 ; See file COPYING.CGEN for details.
6 ; These utilities are neither object nor cgen centric.
7 ; They're generic, non application-specific utilities.
8 ; There are a few exceptions, keep them to a minimum.
11 ; - the prefix "gen-" comes from cgen's convention that procs that return C
12 ; code, and only those procs, are prefixed with "gen-"
16 ; Hobbit support code; for when not using hobbit.
17 ; FIXME: eliminate this stuff ASAP.
19 (defmacro /fastcall-make (proc) proc)
21 (defmacro fastcall4 (proc arg1 arg2 arg3 arg4)
22 (list proc arg1 arg2 arg3 arg4)
25 (defmacro fastcall5 (proc arg1 arg2 arg3 arg4 arg5)
26 (list proc arg1 arg2 arg3 arg4 arg5)
29 (defmacro fastcall6 (proc arg1 arg2 arg3 arg4 arg5 arg6)
30 (list proc arg1 arg2 arg3 arg4 arg5 arg6)
33 (defmacro fastcall7 (proc arg1 arg2 arg3 arg4 arg5 arg6 arg7)
34 (list proc arg1 arg2 arg3 arg4 arg5 arg6 arg7)
37 ; Value doesn't matter too much here, just ensure it's portable.
38 (define *UNSPECIFIED* (if #f 1))
40 (define assert-fail-msg "assertion failure:")
42 (defmacro assert (expr)
44 (error assert-fail-msg ',expr))
47 (define verbose-level 0)
49 (define (verbose-inc!)
50 (set! verbose-level (+ verbose-level 1))
53 (define (verbose? level) (>= verbose-level level))
55 ; Print to stderr, takes an arbitrary number of objects, possibly nested.
56 ; ??? Audit callers, can we maybe just use "display" here (except that
57 ; we still might want some control over the output).
61 (for-each (lambda (str)
64 ;; ??? Incorrect for improper lists, later.
67 (for-each (lambda (s) (message s " ")) str)
69 (message "(" (car str) " . " (cdr str) ")"))
70 (display str (current-error-port))))
74 ; Print a message if the verbosity level calls for it.
75 ; This is a macro as a bit of cpu may be spent computing args,
76 ; and we only want to spend it if the result will be printed.
78 (defmacro logit (level . args)
79 `(if (>= verbose-level ,level) (message ,@args))
82 ; Return a string of N spaces.
84 (define (spaces n) (make-string n #\space))
86 ; Write N spaces to PORT, or the current output port if elided.
88 (define (write-spaces n . port)
89 (let ((port (if (null? port) (current-output-port) (car port))))
90 (write (spaces n) port))
93 ; Concatenate all the arguments and make a string. Symbols are
94 ; converted to strings.
95 (define (string/symbol-append . sequences)
96 (define (sequence->string o) (if (symbol? o) (symbol->string o) o))
97 (apply string-append (map sequence->string sequences)))
101 (define (string-map fn . args) (apply string-append (apply map (cons fn args))))
103 ; Collect a flat list of returned sublists from the lambda fn applied over args.
105 (define (collect fn . args) (apply append (apply map (cons fn args))))
107 ; Map over value entries in an alist.
108 ; 'twould be nice if this were a primitive.
110 (define (amap fn args)
111 (map fn (map cdr args))
114 ; Like map but accept a proper or improper list.
115 ; An improper list is (a b c . d).
116 ; FN must be a proc of one argument.
118 (define (map1-improper fn l)
120 (let loop ((last #f) (l l))
126 (set-cdr! last (cons (fn (car l)) nil))
127 (loop (cdr last) (cdr l)))
129 (set! result (cons (fn (car l)) nil))
130 (loop result (cdr l)))))
134 (set-cdr! last (fn l))
139 ; Turn string or symbol STR into a proper C symbol.
140 ; The result is a string.
141 ; We assume STR has no leading digits.
142 ; All invalid characters are turned into '_'.
143 ; FIXME: Turn trailing "?" into "_p".
145 (define (gen-c-symbol str)
146 (if (not (or (string? str) (symbol? str)))
147 (error "gen-c-symbol: not symbol or string:" str))
148 (map-over-string (lambda (c) (if (id-char? c) c #\_))
152 ; Turn string or symbol STR into a proper file name, which is
153 ; defined to be the same as gen-c-symbol except use -'s instead of _'s.
154 ; The result is a string.
156 (define (gen-file-name str)
157 (if (not (or (string? str) (symbol? str)))
158 (error "gen-file-name: not symbol or string:" str))
159 (map-over-string (lambda (c) (if (id-char? c) c #\-))
163 ; Turn STR into lowercase.
165 (define (string-downcase str)
166 (map-over-string (lambda (c) (char-downcase c)) str)
169 ; Turn STR into uppercase.
171 (define (string-upcase str)
172 (map-over-string (lambda (c) (char-upcase c)) str)
175 ; Turn SYM into lowercase.
177 (define (symbol-downcase sym)
178 (string->symbol (string-downcase (symbol->string sym)))
181 ; Turn SYM into uppercase.
183 (define (symbol-upcase sym)
184 (string->symbol (string-upcase (symbol->string sym)))
189 (define (symbol<? a b)
190 (string<? (symbol->string a) (symbol->string b))
193 ; Drop N chars from string S.
194 ; If N is negative, drop chars from the end.
195 ; It is ok to drop more characters than are in the string, the result is "".
197 (define (string-drop n s)
198 (cond ((>= n (string-length s)) "")
199 ((< n 0) (substring s 0 (+ (string-length s) n)))
200 (else (substring s n (string-length s))))
203 ; Drop the leading char from string S (assumed to have at least 1 char).
205 (define (string-drop1 s)
209 ; Return the leading N chars from string STR.
210 ; This has APL semantics:
211 ; N > length: FILLER chars are appended
212 ; N < 0: take from the end of the string and prepend FILLER if necessary
214 (define (string-take-with-filler n str filler)
215 (let ((len (string-length str)))
218 (string-append (if (> n len)
219 (make-string (- n len) filler)
221 (substring str (max 0 (- len n)) len)))
222 (string-append (substring str 0 (min len n))
224 (make-string (- n len) filler)
228 (define (string-take n str)
229 (string-take-with-filler n str #\space)
232 ; Return the leading char from string S (assumed to have at least 1 char).
234 (define (string-take1 s)
238 ; Return the index of char C in string S or #f if not found.
240 (define (string-index s c)
242 (cond ((= i (string-length s)) #f)
243 ((char=? c (string-ref s i)) i)
244 (else (loop (1+ i)))))
247 ; Cut string S into a list of strings using delimiter DELIM (a character).
249 (define (string-cut s delim)
252 (length (string-length s))
254 (cond ((= end length)
256 (reverse! (cons (substring s start end) result))
258 ((char=? (string-ref s end) delim)
259 (loop (1+ end) (1+ end) length (cons (substring s start end) result)))
260 (else (loop start (1+ end) length result))))
263 ; Convert a list of elements to a string, inserting DELIM (a string)
265 ; L can also be a string or a number.
267 (define (stringize l delim)
268 (cond ((string? l) l)
269 ((number? l) (number->string l))
270 ((symbol? l) (symbol->string l))
273 (string-length delim)
274 (string-map (lambda (elm)
276 (stringize elm delim)))
278 (else (error "stringize: can't handle:" l)))
281 ; Same as string-append, but accepts symbols too.
282 ; PERF: This implementation may be unacceptably slow. Revisit.
284 (define stringsym-append
294 ; Same as symbol-append, but accepts strings too.
296 (define symbolstr-append
298 (string->symbol (apply stringsym-append args)))
301 ; Given a symbol or a string, return the string form.
309 ; Given a symbol or a string, return the symbol form.
319 ;; Given some state that has a setter function (SETTER NEW-VALUE) and
320 ;; a getter function (GETTER), call THUNK with the state set to VALUE,
321 ;; and restore the original value when THUNK returns. Ensure that the
322 ;; original value is restored whether THUNK returns normally, throws
323 ;; an exception, or invokes a continuation that leaves the call's
326 (define (setter-getter-fluid-let setter getter value thunk)
327 (let ((swap (lambda ()
328 (let ((temp (getter)))
330 (set! value temp)))))
331 (dynamic-wind swap thunk swap)))
334 ;; Call THUNK with the current input and output ports set to PORT, and
335 ;; then restore the current ports to their original values.
337 ;; This ensures the current ports get restored whether THUNK exits
338 ;; normally, throws an exception, or leaves the call's dynamic scope
339 ;; by applying a continuation.
341 (define (with-input-and-output-to port thunk)
342 (setter-getter-fluid-let
343 set-current-input-port current-input-port port
345 (setter-getter-fluid-let
346 set-current-output-port current-output-port port
350 ; Extension to the current-output-port.
351 ; Only valid inside string-write.
353 (define /current-print-state #f)
355 ; Create a print-state object.
356 ; This is written in portable Scheme so we don't use COS objects, etc.
358 (define (make-print-state)
359 (vector 'print-state 0)
362 ; print-state accessors.
364 (define (pstate-indent pstate) (vector-ref pstate 1))
365 (define (pstate-set-indent! pstate indent) (vector-set! pstate 1 indent))
367 ; Special print commands (embedded in args).
369 (define (pstate-cmd? x) (and (vector? x) (eq? (vector-ref x 0) 'pstate)))
371 ;(define /endl (vector 'pstate '/endl)) ; ??? needed?
372 (define /indent (vector 'pstate '/indent))
373 (define (/indent-set n) (vector 'pstate '/indent-set n))
374 (define (/indent-add n) (vector 'pstate '/indent-add n))
376 ; Process a pstate command.
378 (define (pstate-cmd-do pstate cmd)
379 (assert (pstate-cmd? cmd))
380 (case (vector-ref cmd 1)
384 (let ((indent (pstate-indent pstate)))
385 (string-append (make-string (quotient indent 8) #\tab)
386 (make-string (remainder indent 8) #\space))))
388 (pstate-set-indent! pstate (vector-ref cmd 2))
391 (pstate-set-indent! pstate (+ (pstate-indent pstate)
395 (error "unknown pstate command" (vector-ref cmd 1))))
398 ; Write STRINGS to current-output-port.
399 ; STRINGS is a list of things to write. Supported types are strings, symbols,
400 ; lists, procedures. Lists are printed by applying string-write recursively.
401 ; Procedures are thunks that return the string to write.
403 ; The result is the empty string. This is for debugging where this
404 ; procedure is modified to return its args, rather than write them out.
408 (let ((pstate (make-print-state)))
409 (set! /current-print-state pstate)
410 (for-each (lambda (elm) (/string-write pstate elm))
412 (set! /current-print-state #f)
416 ; Subroutine of string-write and string-write-map.
418 (define (/string-write pstate expr)
419 (cond ((string? expr) (display expr)) ; not write, we want raw text
420 ((symbol? expr) (display expr))
421 ((procedure? expr) (/string-write pstate (expr)))
422 ((pstate-cmd? expr) (display (pstate-cmd-do pstate expr)))
423 ((list? expr) (for-each (lambda (x) (/string-write pstate x)) expr))
424 (else (error "string-write: bad arg:" expr)))
428 ; Combination of string-map and string-write.
430 (define (string-write-map proc arglist)
431 (let ((pstate /current-print-state))
432 (for-each (lambda (arg) (/string-write pstate (proc arg)))
437 ; Build up an argument for string-write.
439 (define string-list list)
440 (define string-list-map map)
442 ; Subroutine of string-list->string. Does same thing /string-write does.
444 (define (/string-list-flatten pstate strlist)
445 (cond ((string? strlist) strlist)
446 ((symbol? strlist) strlist)
447 ((procedure? strlist) (/string-list-flatten pstate (strlist)))
448 ((pstate-cmd? strlist) (pstate-cmd-do pstate strlist))
449 ((list? strlist) (apply string-append
451 (/string-list-flatten pstate str))
453 (else (error "string-list->string: bad arg:" strlist)))
456 ; Flatten out a string list.
458 (define (string-list->string strlist)
459 (/string-list-flatten (make-print-state) strlist)
462 ; Prefix CHARS, a string of characters, with backslash in STR.
463 ; STR is either a string or list of strings (to any depth).
464 ; ??? Quick-n-dirty implementation.
466 (define (backslash chars str)
468 ; quick check for any work to do
469 (if (any-true? (map (lambda (c)
470 (string-index str c))
471 (string->list chars)))
472 (let loop ((result "") (str str))
473 (if (= (string-length str) 0)
475 (loop (string-append result
476 (if (string-index chars (string-ref str 0))
480 (substring str 1 (string-length str)))))
485 (cons (backslash chars (car str))
486 (backslash chars (cdr str)))))
489 ; Return a boolean indicating if S is bound to a value.
490 ;(define old-symbol-bound? symbol-bound?)
491 ;(define (symbol-bound? s) (old-symbol-bound? #f s))
493 ; Return a boolean indicating if S is a symbol and is bound to a value.
495 (define (bound-symbol? s)
497 (or (symbol-bound? #f s)
498 ;(module-bound? cgen-module s)
504 (define (identity x) x)
506 ; Test whether X is a `form' (non-empty list).
507 ; ??? Is `form' the right word to use here?
508 ; One can argue we should also test for a valid car. If so, it's the
509 ; name that's wrong not the code (because the code is what I want).
511 (define (form? x) (and (not (null? x)) (list? x)))
513 ; Return the number of arguments to ARG-SPEC, a valid argument list
515 ; The result is a pair: number of fixed arguments, varargs indicator (#f/#t).
517 (define (num-args arg-spec)
518 (if (symbol? arg-spec)
520 (let loop ((count 0) (arg-spec arg-spec))
521 (cond ((null? arg-spec) (cons count #f))
522 ((null? (cdr arg-spec)) (cons (+ count 1) #f))
523 ((pair? (cdr arg-spec)) (loop (+ count 1) (cdr arg-spec)))
524 (else (cons (+ count 1) #t)))))
527 ; Return a boolean indicating if N args is ok to pass to a proc with
528 ; an argument specification of ARG-SPEC (a valid argument list of `lambda').
530 (define (num-args-ok? n arg-spec)
531 (let ((processed-spec (num-args arg-spec)))
533 ; Ensure enough fixed arguments.
534 (>= n (car processed-spec))
535 ; If more args than fixed args, ensure varargs.
536 (or (= n (car processed-spec))
537 (cdr processed-spec))))
540 ; Take N elements from list L.
541 ; If N is negative, take elements from the end.
542 ; If N is larger than the length, the extra elements are NIL.
544 ; FIXME: list-tail has args reversed (we should conform)
546 (define (list-take n l)
547 (let ((len (length l)))
549 (list-tail l (+ len n))
550 (let loop ((result nil) (l l) (i 0))
553 (loop (cons (car l) result) (cdr l) (+ i 1))))))
556 ; Drop N elements from list L.
557 ; FIXME: list-tail has args reversed (we should conform)
559 (define (list-drop n l)
560 (let loop ((n n) (l l))
562 (loop (- n 1) (cdr l))
566 ; Drop N elements from the end of L.
567 ; FIXME: list-tail has args reversed (we should conform)
569 (define (list-tail-drop n l)
570 (reverse! (list-drop n (reverse l)))
575 (define (foldl kons accum lis)
576 (if (null? lis) accum
577 (foldl kons (kons accum (car lis)) (cdr lis))))
581 (define (foldr kons knil lis)
583 (kons (car lis) (foldr kons knil (cdr lis)))))
585 ;; filter list on predicate
587 (define (filter p ls)
588 (foldr (lambda (x a) (if (p x) (cons x a) a))
591 ; APL's +\ operation on a vector of numbers.
593 (define (plus-scan l)
594 (letrec ((-plus-scan (lambda (l result)
598 (cons (if (null? result)
600 (+ (car l) (car result)))
602 (reverse! (-plus-scan l nil)))
605 ; Remove duplicate elements from sorted list L.
606 ; Currently supported elements are symbols (a b c) and lists ((a) (b) (c)).
607 ; NOTE: Uses equal? for comparisons.
609 (define (remove-duplicates l)
610 (let loop ((l l) (result nil))
611 (cond ((null? l) (reverse! result))
612 ((null? result) (loop (cdr l) (cons (car l) result)))
613 ((equal? (car l) (car result)) (loop (cdr l) result))
614 (else (loop (cdr l) (cons (car l) result)))
619 ; Return a boolean indicating if each element of list satisfies its
620 ; corresponding predicates. The length of L must be equal to the length
623 (define (list-elements-ok? l preds)
625 (= (length l) (length preds))
626 (all-true? (map (lambda (pred elm) (pred elm)) preds l)))
629 ; Remove duplicates from unsorted list L.
630 ; KEY-GENERATOR is a lambda that takes a list element as input and returns
631 ; an equal? key to use to determine duplicates.
632 ; The first instance in a set of duplicates is always used.
633 ; This is not intended to be applied to large lists with an expected large
634 ; result (where sorting the list first would be faster), though one could
635 ; add such support later.
637 ; ??? Rename to follow memq/memv/member naming convention.
639 (define (nub l key-generator)
640 (let loop ((l l) (keys (map key-generator l)) (result nil))
642 (reverse! (map cdr result))
643 (if (assv (car keys) result)
644 (loop (cdr l) (cdr keys) result)
645 (loop (cdr l) (cdr keys) (acons (car keys) (car l)
649 ; Return a boolean indicating if list L1 is a subset of L2.
652 (define (subset? l1 l2)
656 (if (memq (car l1) l2)
661 ; Return intersection of two lists.
663 (define (intersection a b)
664 (foldl (lambda (l e) (if (memq e a) (cons e l) l)) '() b))
666 ; Return #t if the intersection of A and B is non-null.
668 (define (non-null-intersection? a b)
678 ; Return union of two lists.
681 (foldl (lambda (l e) (if (memq e l) l (cons e l))) a b))
683 ; Return a count of the number of elements of list L1 that are in list L2.
686 (define (count-common l1 l2)
687 (let loop ((result 0) (l1 l1))
690 (if (memq (car l1) l2)
691 (loop (+ result 1) (cdr l1))
692 (loop result (cdr l1)))))
695 ; Remove duplicate elements from sorted alist L.
696 ; L must be sorted by name.
698 (define (alist-nub l)
699 (let loop ((l l) (result nil))
700 (cond ((null? l) (reverse! result))
701 ((null? result) (loop (cdr l) (cons (car l) result)))
702 ((eq? (caar l) (caar result)) (loop (cdr l) result))
703 (else (loop (cdr l) (cons (car l) result)))
708 ; Return a copy of alist L.
710 (define (alist-copy l)
711 ; (map cons (map car l) (map cdr l)) ; simple way
712 ; presumably more efficient way (less cons cells created)
714 (cons (car elm) (cdr elm)))
718 ; Return the order in which to select elements of L sorted by SORT-FN.
719 ; The result is origin 0.
721 (define (sort-grade l sort-fn)
722 (let ((sorted (sort (map cons (iota (length l)) l)
723 (lambda (a b) (sort-fn (cdr a) (cdr b))))))
727 ; Return ALIST sorted on the name in ascending order.
729 (define (alist-sort alist)
732 (string<? (symbol->string (car a))
733 (symbol->string (car b)))))
736 ; Return a boolean indicating if C is a leading id char.
737 ; '@' is treated as an id-char as it's used to delimit something that
740 (define (leading-id-char? c)
741 (or (char-alphabetic? c)
746 ; Return a boolean indicating if C is an id char.
747 ; '@' is treated as an id-char as it's used to delimit something that
751 (or (leading-id-char? c)
755 ; Return the length of the identifier that begins S.
756 ; Identifiers are any of letter, digit, _, @.
757 ; The first character must not be a digit.
758 ; ??? The convention is to use "-" between cgen symbols, not "_".
759 ; Try to handle "-" here as well.
762 (if (leading-id-char? (string-ref s 0))
763 (let ((len (string-length s)))
766 (id-char? (string-ref s n)))
772 ; Return number of characters in STRING until DELIMITER.
773 ; Returns #f if DELIMITER not present.
774 ; FIXME: Doesn't yet support \-prefixed delimiter (doesn't terminate scan).
776 (define (chars-until-delimiter string delimiter)
777 (let loop ((str string) (result 0))
778 (cond ((= (string-length str) 0)
780 ((char=? (string-ref str 0) delimiter)
782 (else (loop (string-drop1 str) (1+ result)))))
785 ; Apply FN to each char of STR.
787 (define (map-over-string fn str)
788 (do ((tmp (string-copy (if (symbol? str) (symbol->string str) str)))
789 (i (- (string-length str) 1) (- i 1)))
791 (string-set! tmp i (fn (string-ref tmp i)))
796 ; It must be distinguishable from a list of numbers.
798 (define (minmax min max) (cons min max))
800 ; Move VALUE of LENGTH bits to position START in a word of SIZE bits.
801 ; LSB0? is non-#f if bit numbering goes LSB->MSB.
802 ; Otherwise it goes MSB->LSB.
803 ; START-LSB? is non-#f if START denotes the least significant bit.
804 ; Otherwise START denotes the most significant bit.
805 ; N is assumed to fit in the field.
807 (define (word-value start length size lsb0? start-lsb? value)
811 (logsll value (+ (- start length) 1)))
813 (logsll value (- size start 1))
814 (logsll value (- size (+ start length)))))
817 ; Return a bit mask of LENGTH bits in a word of SIZE bits starting at START.
818 ; LSB0? is non-#f if bit numbering goes LSB->MSB.
819 ; Otherwise it goes MSB->LSB.
820 ; START-LSB? is non-#f if START denotes the least significant bit.
821 ; Otherwise START denotes the most significant bit.
823 (define (word-mask start length size lsb0? start-lsb?)
826 (logsll (mask length) start)
827 (logsll (mask length) (+ (- start length) 1)))
829 (logsll (mask length) (- size start 1))
830 (logsll (mask length) (- size (+ start length)))))
833 ; Extract LENGTH bits at bit number START in a word of SIZE bits from VALUE.
834 ; LSB0? is non-#f if bit numbering goes LSB->MSB.
835 ; Otherwise it goes MSB->LSB.
836 ; START-LSB? is non-#f if START denotes the least significant bit.
837 ; Otherwise START denotes the most significant bit.
839 ; ??? bit-extract takes a big-number argument but still uses logand
840 ; which doesn't so we don't use it
842 (define (word-extract start length size lsb0? start-lsb? value)
845 (remainder (logslr value start) (integer-expt 2 length))
846 (remainder (logslr value (+ (- start length) 1)) (integer-expt 2 length)))
848 (remainder (logslr value (- size start 1)) (integer-expt 2 length))
849 (remainder (logslr value (- size (+ start length))) (integer-expt 2 length))))
852 ; Return numeric value of bit N in a word of size WORD-BITSIZE.
854 (define (word-bit-value bitnum word-bitsize lsb0?)
855 (assert (< bitnum word-bitsize))
858 (ash 1 (- word-bitsize bitnum 1)))
861 ; Return a bit mask of size SIZE beginning at the LSB.
864 (- (logsll 1 size) 1)
867 ; Split VAL into pieces of bit size LENGTHS.
868 ; e.g. (split-bits '(8 2) 997) -> (229 3)
869 ; There are as many elements in the result as there are in LENGTHS.
870 ; Note that this can result in a loss of information.
872 (define (split-bits lengths val)
874 (lambda (lengths val result)
877 (split1 (cdr lengths)
878 (quotient val (integer-expt 2 (car lengths)))
879 (cons (remainder val (integer-expt 2 (car lengths)))
881 (reverse! (split1 lengths val nil)))
884 ; Generalized version of split-bits.
885 ; e.g. (split-value '(10 10 10) 1234) -> (4 3 2 1) ; ??? -> (1 2 3 4) ?
886 ; (split-value '(10 10) 1234) -> (4 3)
887 ; There are as many elements in the result as there are in BASES.
888 ; Note that this can result in a loss of information.
890 (define (split-value bases val)
892 (lambda (bases val result)
896 (quotient val (car bases))
897 (cons (remainder val (car bases))
899 (reverse! (split1 bases val nil)))
902 ; Convert bits to bytes.
904 (define (bits->bytes bits) (quotient (+ 7 bits) 8))
906 ; Convert bytes to bits.
908 (define (bytes->bits bytes) (* bytes 8))
910 ; Return a list of integers.
912 ; (.iota count) ; start=0, incr=1
913 ; (.iota count start) ; incr=1
914 ; (.iota count start incr)
916 (define (iota count . start-incr)
917 (if (> (length start-incr) 2)
918 (error "iota: wrong number of arguments:" start-incr))
920 (error "iota: count must be non-negative:" n))
921 (let ((start (if (pair? start-incr) (car start-incr) 0))
922 (incr (if (= (length start-incr) 2) (cadr start-incr) 1)))
923 (let loop ((i start) (count count) (result '()))
926 (loop (+ i incr) (- count 1) (cons i result)))))
929 ; Return a list of the first N powers of 2.
931 (define (powers-of-2 n)
933 (else (cons (integer-expt 2 (1- n)) (powers-of-2 (1- n))))
935 ; Another way: (map (lambda (n) (ash 1 n)) (iota n))
938 ; I'm tired of writing (not (= foo bar)).
940 (define (!= a b) (not (= a b)))
942 ; Return #t if BIT-NUM (which is starting from LSB), is set in the binary
943 ; representation of non-negative integer N.
945 (define (bit-set? n bit-num)
946 ; ??? Quick hack to work around missing bignum support.
947 ;(= 1 (cg-logand (logslr n bit-num) 1))
948 (if (>= n #x20000000)
950 (logbit? (- bit-num 16) (logslr n 16))
951 (logbit? bit-num (remainder n 65536)))
955 ; Return #t if each element of bools is #t. Since Scheme considers any
956 ; non-#f value as #t we do too.
957 ; (all-true? '()) is #t since that is the identity element.
959 (define (all-true? bools)
960 (cond ((null? bools) #t)
961 ((car bools) (all-true? (cdr bools)))
965 ; Return #t if any element of BOOLS is #t.
966 ; If BOOLS is empty, return #f.
968 (define (any-true? bools)
969 (cond ((null? bools) #f)
971 (else (any-true? (cdr bools))))
974 ; Return count of true values.
976 (define (count-true flags)
977 (let loop ((result 0) (flags flags))
980 (loop (+ result (if (car flags) 1 0))
984 ; Return count of all ones in BITS.
986 (define (count-bits bits)
987 (let loop ((result 0) (bits bits))
990 (loop (+ result (remainder bits 2)) (quotient bits 2))))
993 ; Convert bits in N #f/#t.
994 ; LENGTH is the length of N in bits.
996 (define (bits->bools n length)
997 (do ((result (make-list length #f))
999 ((= i length) (reverse! result))
1000 (list-set! result i (if (bit-set? n i) #t #f))
1004 ; Print a C integer.
1006 (define (gen-integer val)
1007 (cond ((and (<= #x-80000000 val) (> #x80000000 val))
1008 (number->string val))
1009 ((and (<= #x80000000 val) (>= #xffffffff val))
1010 ; ??? GCC complains if not affixed with "U" but that's not k&r.
1011 ;(string-append (number->string val) "U"))
1012 (string-append "0x" (number->string val 16)))
1013 (else (error "Number too large for gen-integer:" val)))
1016 ; Return higher/lower part of double word integer.
1018 (define (high-part val)
1021 (define (low-part val)
1022 (remainder val #x100000000)
1025 ; Logical operations.
1027 (define (logslr val shift) (ash val (- shift)))
1028 (define logsll ash) ; (logsll val shift) (ash val shift))
1030 ; logand, logior, logxor defined by guile so we don't need to
1031 ; (define (logand a b) ...)
1032 ; (define (logxor a b) ...)
1033 ; (define (logior a b) ...)
1035 ; On the other hand they didn't support bignums, so the cgen-binary
1036 ; defines cg-log* that does. These are just a quick hack that only
1037 ; handle what currently needs handling.
1039 (define (cg-logand a b)
1040 (if (or (>= a #x20000000)
1042 (+ (logsll (logand (logslr a 16) (logslr b 16)) 16)
1043 (logand (remainder a 65536) (remainder b 65536)))
1047 (define (cg-logxor a b)
1048 (if (or (>= a #x20000000)
1050 (+ (logsll (logxor (logslr a 16) (logslr b 16)) 16)
1051 (logxor (remainder a 65536) (remainder b 65536)))
1055 ; Return list of bit values for the 1's in X.
1057 (define (bit-vals x)
1058 (let loop ((result nil) (mask 65536))
1059 (cond ((= mask 0) result)
1060 ((> (logand x mask) 0) (loop (cons mask result) (logslr mask 1)))
1061 (else (loop result (logslr mask 1)))))
1064 ; Return bit representation of N in LEN bits.
1065 ; e.g. (bit-rep 6 3) -> (1 1 0)
1067 (define (bit-rep n len)
1068 (cond ((= len 0) nil)
1069 ((> (logand n (logsll 1 (- len 1))) 0)
1070 (cons 1 (bit-rep n (- len 1))))
1071 (else (cons 0 (bit-rep n (- len 1))))))
1073 ; Return list of all bit values from 0 to N.
1074 ; e.g. (bit-patterns 3) -> ((0 0 0) (0 0 1) (0 1 0) ... (1 1 1))
1076 (define (bit-patterns len)
1077 (map (lambda (x) (bit-rep x len)) (iota (logsll 1 len)))
1080 ; Compute the list of all indices from bits missing in MASK.
1081 ; e.g. (missing-bit-indices #xff00 #xffff) -> (0 1 2 3 ... 255)
1083 (define (missing-bit-indices mask full-mask)
1084 (let* ((bitvals (bit-vals (logxor mask full-mask)))
1085 (selectors (bit-patterns (length bitvals)))
1086 (map-star (lambda (sel) (map * sel bitvals)))
1087 (compute-indices (lambda (sel) (apply + (map-star sel)))))
1088 (map compute-indices selectors))
1091 ; Return #t if n is a non-negative integer.
1093 (define (non-negative-integer? n)
1098 ; Convert a list of numbers to a string, separated by SEP.
1099 ; The result is prefixed by SEP too.
1101 (define (numbers->string nums sep)
1102 (string-map (lambda (elm) (string-append sep (number->string elm))) nums)
1105 ; Convert a number to a hex string.
1107 (define (number->hex num)
1108 (number->string num 16)
1111 ; Convert a number to a hex C constant,
1112 ; taking care to handle large numbers.
1113 ; If NUM won't fit in a portable int (32-bits), cast it to BIG-NUM-TYPE.
1115 (define (gen-c-hex-constant num big-num-type)
1116 (cond ((< num (- (ash 1 31)))
1117 ;; Skip outputting -ve numbers in hex for now.
1118 (string-append "((" big-num-type ") " (number->string num) "LL)"))
1119 ((> num (- (ash 1 32) 1))
1120 (string-append "((" big-num-type ") 0x" (number->string num 16) "LL)"))
1122 (string-append "0x" (number->string num 16))))
1125 ; Given a list of numbers NUMS, generate text to pass them as arguments to a
1126 ; C function. We assume they're not the first argument and thus have a
1129 (define (gen-int-args nums)
1130 (numbers->string nums ", ")
1133 ; Given a C expression or a list of C expressions, return a comma separated
1135 ; In the case of more than 0 elements the leading ", " is present so that
1136 ; there is no edge case in the case of 0 elements when the caller is appending
1137 ; the result to an initial set of arguments (the number of commas equals the
1138 ; number of elements). The caller is responsible for dropping the leading
1139 ; ", " if necessary. Note that `string-drop' can handle the case where more
1140 ; characters are dropped than are present.
1142 (define (gen-c-args exprs)
1143 (cond ((null? exprs) "")
1144 ((pair? exprs) (string-map (lambda (elm) (string-append ", " elm))
1146 ((equal? exprs "") "")
1147 (else (string-append ", " exprs)))
1150 ; Return a list of N macro argument names.
1152 (define (macro-args n)
1153 (map (lambda (i) (string-append "a" (number->string i)))
1157 ; Return C code for N macro argument names.
1158 ; (gen-macro-args 4) -> ", a1, a2, a3, a4"
1160 (define (gen-macro-args n)
1161 (gen-c-args (macro-args n))
1164 ; Return a string to reference an array.
1165 ; INDICES is either a (possibly empty) list of indices or a single index.
1166 ; The values can either be numbers or strings (/symbols).
1168 (define (gen-array-ref indices)
1169 (let ((gen-index (lambda (idx)
1171 (cond ((number? idx) (number->string idx))
1174 (cond ((null? indices) "")
1175 ((pair? indices) ; list of indices?
1176 (string-map gen-index indices))
1177 (else (gen-index indices))))
1180 ; Return list element N or #f if list L is too short.
1182 (define (list-maybe-ref l n)
1183 (if (> (length l) n)
1188 ; Return list of index numbers of elements in list L that satisfy PRED.
1189 ; I is added to each index, it's usually 0.
1191 (define (find-index i pred l)
1192 (define (find1 i pred l result)
1193 (cond ((null? l) result)
1194 ((pred (car l)) (find1 (+ 1 i) pred (cdr l) (cons i result)))
1195 (else (find1 (+ 1 i) pred (cdr l) result))))
1196 (reverse! (find1 i pred l nil))
1199 ; Return index number of first element in list L that satisfy PRED.
1200 ; Returns #f if not present.
1201 ; I is added to the result, it's usually 0.
1203 (define (find-first-index i pred l)
1204 (cond ((null? l) #f)
1206 (else (find-first-index (+ 1 i) pred (cdr l))))
1209 ; Return list of elements of L that satisfy PRED.
1211 (define (find pred l)
1212 (define (find1 pred l result)
1213 (cond ((null? l) result)
1214 ((pred (car l)) (find1 pred (cdr l) (cons (car l) result)))
1215 (else (find1 pred (cdr l) result))))
1216 (reverse! (find1 pred l nil))
1219 ; Return first element of L that satisfies PRED or #f if there is none.
1221 (define (find-first pred l)
1222 (cond ((null? l) #f)
1223 ((pred (car l)) (car l))
1224 (else (find-first pred (cdr l))))
1227 ; Return list of FN applied to elements of L that satisfy PRED.
1229 (define (find-apply fn pred l)
1230 (cond ((null? l) nil)
1231 ((pred (car l)) (cons (fn (car l)) (find-apply fn pred (cdr l))))
1232 (else (find-apply fn pred (cdr l))))
1235 ; Given a list L, look up element ELM and return its index.
1236 ; If not found, return #f.
1237 ; I is added to the result.
1238 ; (Yes, in one sense I is present to simplify the implementation. Sue me.)
1240 (define (eqv-lookup-index elm l i)
1241 (cond ((null? l) #f)
1242 ((eqv? elm (car l)) i)
1243 (else (eqv-lookup-index elm (cdr l) (1+ i))))
1246 ; Given an associative list L, look up entry for symbol S and return its index.
1247 ; If not found, return #f.
1248 ; Eg: (lookup 'element2 '((element1 1) (element2 2)))
1249 ; I is added to the result.
1250 ; (Yes, in one sense I is present to simplify the implementation. Sue me.)
1251 ; NOTE: Uses eq? for comparisons.
1253 (define (assq-lookup-index s l i)
1254 (cond ((null? l) #f)
1255 ((eqv? s (caar l)) i)
1256 (else (assq-lookup-index s (cdr l) (1+ i))))
1259 ; Return the index of element ELM in list L or #f if not found.
1260 ; If found, I is added to the result.
1261 ; (Yes, in one sense I is present to simplify the implementation. Sue me.)
1262 ; NOTE: Uses equal? for comparisons.
1264 (define (element-lookup-index elm l i)
1265 (cond ((null? l) #f)
1266 ((equal? elm (car l)) i)
1267 (else (element-lookup-index elm (cdr l) (1+ i))))
1270 ; Return #t if ELM is in ELM-LIST.
1271 ; NOTE: Uses equal? for comparisons (via `member').
1273 (define (element? elm elm-list)
1274 (->bool (member elm elm-list))
1277 ; Return the set of all possible combinations of elements in list L
1278 ; according to the following rules:
1279 ; - each element of L is either an atom (non-list) or a list
1280 ; - each list element is (recursively) interpreted as a set of choices
1281 ; - the result is a list of all possible combinations of elements
1283 ; Example: (list-expand '(a b (1 2 (3 4)) c (5 6)))
1284 ; --> ((a b 1 c d 5)
1293 (define (list-expand l)
1297 ; If OBJ has a dump method call it, otherwise return OBJ untouched.
1300 (if (method-present? obj 'dump)
1305 ; Copyright messages.
1307 ; Pair of header,trailer parts of copyright.
1309 (define copyright-fsf
1311 THIS FILE IS MACHINE GENERATED WITH CGEN.
1313 Copyright 1996-2010 Free Software Foundation, Inc.
1316 This file is free software; you can redistribute it and/or modify
1317 it under the terms of the GNU General Public License as published by
1318 the Free Software Foundation; either version 3, or (at your option)
1321 It is distributed in the hope that it will be useful, but WITHOUT
1322 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1323 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
1324 License for more details.
1326 You should have received a copy of the GNU General Public License along
1327 with this program; if not, write to the Free Software Foundation, Inc.,
1328 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.
1332 ; Pair of header,trailer parts of copyright.
1334 (define copyright-red-hat
1336 THIS FILE IS MACHINE GENERATED WITH CGEN.
1338 Copyright (C) 2000-2010 Red Hat, Inc.
1343 ; Set this to one of copyright-fsf, copyright-red-hat.
1345 (define CURRENT-COPYRIGHT copyright-fsf)
1349 (define package-gnu-binutils-gdb "\
1350 This file is part of the GNU Binutils and/or GDB, the GNU debugger.
1353 (define package-gnu-simulators "\
1354 This file is part of the GNU simulators.
1357 (define package-red-hat-simulators "\
1358 This file is part of the Red Hat simulators.
1361 (define package-cgen "\
1362 This file is part of CGEN.
1365 ; Return COPYRIGHT, with FILE-DESC as the first line
1366 ; and PACKAGE as the name of the package which the file belongs in.
1367 ; COPYRIGHT is a pair of (header . trailer).
1369 (define (gen-c-copyright file-desc copyright package)
1370 (string-append "/* " file-desc "\n\n"
1379 ; Delete FILE, handling the case where it doesn't exist.
1381 (define (delete-file-noerr file)
1382 ; This could also use file-exists?, but it's nice to have a few examples
1383 ; of how to use `catch' lying around.
1384 (catch 'system-error (lambda () (delete-file file))
1388 ; Create FILE, point current-output-port to it, and call WRITE-FN.
1389 ; FILE is always overwritten.
1390 ; GEN-FN either writes output to stdout or returns the text to write,
1391 ; the last thing we do is write the text returned by WRITE-FN to FILE.
1393 (define (file-write file write-fn)
1394 (delete-file-noerr file)
1395 (let ((left-over-text (with-output-to-file file write-fn)))
1396 (let ((port (open-file file "a")))
1397 (display left-over-text port)
1402 ; Return the size in bytes of FILE.
1404 (define (file-size file)
1405 (let ((stat (%stat file)))
1407 (vector-ref (%stat file) 7)
1413 ; Return the current time.
1414 ; The result is a black box understood only by time-elapsed.
1416 (define (time-current) (gettimeofday))
1418 ; Return the elapsed time in milliseconds since START.
1420 (define (time-elapsed start)
1421 (let ((now (gettimeofday)))
1422 (+ (* (- (car now) (car start)) 1000)
1423 (quotient (- (cdr now) (cdr start)) 1000)))
1426 ; Run PROC and return the number of milliseconds it took to execute it N times.
1428 (define (time-proc n proc)
1429 (let ((now (time-current)))
1430 (do ((i 0 (+ i 1))) ((= i n) (time-elapsed now))
1436 ; Record of arguments passed to debug-repl, so they can be accessed in
1439 (define debug-env #f)
1441 ; Return list of recorded variables for debugging.
1443 (define (debug-var-names) (map car debug-env))
1445 ; Return value of recorded var NAME.
1447 (define (debug-var name) (assq-ref debug-env name))
1449 ; A handle on /dev/tty, so we can be sure we're talking with the user.
1450 ; We open this the first time we actually need it.
1452 (define debug-tty #f)
1454 ; Return the port we should use for interacting with the user,
1455 ; opening it if necessary.
1457 (define (debug-tty-port)
1459 (set! debug-tty (open-file "/dev/tty" "r+")))
1462 ; Enter a repl loop for debugging purposes.
1463 ; Use (quit) to exit cgen completely.
1464 ; Use (debug-quit) or (quit 0) to exit the debugging session and
1465 ; resume argument processing.
1467 ; ENV-ALIST can be anything, but it is intended to be an alist of values
1468 ; the caller will want to be able to access in the repl loop.
1469 ; It is stored in global `debug-env'.
1471 (define (debug-repl env-alist)
1472 (with-input-and-output-to
1475 (set! debug-env env-alist)
1477 (let ((rc (top-repl)))
1479 (quit 1)) ; indicate error to `make'
1480 (if (not (equal? rc '(0)))
1484 ; Utility for debug-repl.
1486 (define (debug-quit)
1487 ; Keep around for later debugging.
1488 ;(set! debug-env #f)
1493 ; Macro to simplify calling debug-repl.
1494 ; Usage: (debug-repl-env var-name1 var-name2 ...)
1496 ; This is for debugging cgen itself, and is inserted into code at the point
1497 ; where one wants to start a repl.
1499 (defmacro debug-repl-env var-names
1500 (let ((env (map (lambda (var-name)
1501 (list 'cons (list 'quote var-name) var-name))
1503 (list 'debug-repl (cons 'list env)))