;;; Type analysis on CPS ;;; Copyright (C) 2014, 2015, 2018 Free Software Foundation, Inc. ;;; ;;; This library is free software: you can redistribute it and/or modify ;;; it under the terms of the GNU Lesser General Public License as ;;; published by the Free Software Foundation, either version 3 of the ;;; License, or (at your option) any later version. ;;; ;;; This library is distributed in the hope that it will be useful, but ;;; WITHOUT ANY WARRANTY; without even the implied warranty of ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU ;;; Lesser General Public License for more details. ;;; ;;; You should have received a copy of the GNU Lesser General Public ;;; License along with this program. If not, see ;;; . ;;; Commentary: ;;; ;;; Type analysis computes the possible types and ranges that values may ;;; have at all program positions. This analysis can help to prove that ;;; a primcall has no side-effects, if its arguments have the ;;; appropriate type and range. It can also enable constant folding of ;;; type predicates and, in the future, enable the compiler to choose ;;; untagged, unboxed representations for numbers. ;;; ;;; For the purposes of this analysis, a "type" is an aspect of a value ;;; that will not change. Guile's CPS intermediate language does not ;;; carry manifest type information that asserts properties about given ;;; values; instead, we recover this information via flow analysis, ;;; garnering properties from type predicates, constant literals, ;;; primcall results, and primcalls that assert that their arguments are ;;; of particular types. ;;; ;;; A range denotes a subset of the set of values in a type, bounded by ;;; a minimum and a maximum. The precise meaning of a range depends on ;;; the type. For real numbers, the range indicates an inclusive lower ;;; and upper bound on the integer value of a type. For vectors, the ;;; range indicates the length of the vector. The range is the union of ;;; the signed and unsigned 64-bit ranges. Additionally, the minimum ;;; bound of a range may be -inf.0, and the maximum bound may be +inf.0. ;;; For some types, like pairs, the concept of "range" makes no sense. ;;; In these cases we consider the range to be -inf.0 to +inf.0. ;;; ;;; Types are represented as a bitfield. Fewer bits means a more precise ;;; type. Although normally only values that have a single type will ;;; have an associated range, this is not enforced. The range applies ;;; to all types in the bitfield. When control flow meets, the types and ;;; ranges meet with the union operator. ;;; ;;; It is not practical to precisely compute value ranges in all cases. ;;; For example, in the following case: ;;; ;;; (let lp ((n 0)) (when (foo) (lp (1+ n)))) ;;; ;;; The first time that range analysis visits the program, N is ;;; determined to be the exact integer 0. The second time, it is an ;;; exact integer in the range [0, 1]; the third, [0, 2]; and so on. ;;; This analysis will terminate, but only after the positive half of ;;; the 64-bit range has been fully explored and we decide that the ;;; range of N is [0, +inf.0]. At the same time, we want to do range ;;; analysis and type analysis at the same time, as there are ;;; interactions between them, notably in the case of `sqrt' which ;;; returns a complex number if its argument cannot be proven to be ;;; non-negative. So what we do instead is to precisely propagate types ;;; and ranges when propagating forward, but after the first backwards ;;; branch is seen, we cause backward branches that would expand the ;;; range of a value to saturate that range towards positive or negative ;;; infinity (as appropriate). ;;; ;;; A naive approach to type analysis would build up a table that has ;;; entries for all variables at all program points, but this has ;;; N-squared complexity and quickly grows unmanageable. Instead, we ;;; use _intmaps_ from (language cps intmap) to share state between ;;; connected program points. ;;; ;;; Code: (define-module (language cps types) #:use-module (ice-9 match) #:use-module (language cps) #:use-module (language cps utils) #:use-module (language cps intmap) #:use-module (language cps intset) #:use-module (rnrs bytevectors) #:use-module (srfi srfi-11) #:use-module ((system syntax internal) #:select (syntax?)) #:export (;; Specific types. &exact-integer &flonum &complex &fraction &char &unspecified &unbound &false &true &nil &null &symbol &keyword &procedure &pointer &fluid &pair &vector &box &struct &string &bytevector &bitvector &array &syntax ;; Union types. &number &real ;; Untagged types. &f64 &u64 &s64 infer-types lookup-pre-type lookup-post-type primcall-types-check?)) (define-syntax define-flags (lambda (x) (syntax-case x () ((_ all shift name ...) (let ((count (length #'(name ...)))) (with-syntax (((n ...) (iota count)) (count count)) #'(begin (define-syntax name (identifier-syntax (ash 1 n))) ... (define-syntax all (identifier-syntax (1- (ash 1 count)))) (define-syntax shift (identifier-syntax count))))))))) ;; More precise types have fewer bits. (define-flags &all-types &type-bits &exact-integer &flonum &complex &fraction &char &unspecified &unbound &false &true &nil &null &symbol &keyword &procedure &pointer &fluid &pair &vector &box &struct &string &bytevector &bitvector &array &syntax &f64 &u64 &s64) (define-syntax &no-type (identifier-syntax 0)) (define-syntax &number (identifier-syntax (logior &exact-integer &flonum &complex &fraction))) (define-syntax &real (identifier-syntax (logior &exact-integer &flonum &fraction))) ;; Versions of min and max that do not coerce exact numbers to become ;; inexact. (define min (case-lambda ((a b) (if (< a b) a b)) ((a b c) (min (min a b) c)) ((a b c d) (min (min a b) c d)))) (define max (case-lambda ((a b) (if (> a b) a b)) ((a b c) (max (max a b) c)) ((a b c d) (max (max a b) c d))))