[Chicken-hackers] specialization

[Felix]

Hello!


This message is intended to describe the recent work in the
"specialization" branch of the chicken-core git repository which has
now been merged into "master". I'll try to explain the changes in a
bit more detailed manner, as it might be helpful for taking maximum
advantage of any enhancements, and understanding the shortcomings. And
of course I can't let a opportunity for bragging simply pass along
unused...

"specialization" means using the type-information obtained by the part
of the compiler that performs an intraprocedural flow-analysis
(enabled using "-scrutinize") and rewrite calls to core-library
procedures that match a given set of argument types. There are quite a
number of optimizations that can be done that way, starting from
eliminating simple predicate calls up to using more efficient internal
routines that omit argument checking. Specifically, arithmetic
operations that are known to take floating-point arguments can be
rewritten to use floating-point-specific operators. 

Note that specialization will not result in any significant
performance improvements compared to unsafe code. In unsafe mode, many
library calls are rewritten to unsafe internal operations anyway, so
specialization has most effect in safe mode. This is usually the way
code is compiled and also applies to compiled extensions.

Performance improvements are highly dependent on the compiled code, of
course. The FFT benchmark by Brad Lucier contained in the core
test-suite runs about twice as fast (-O3 -d0), but may not be
representative, as it is very tight floating-point intensive code. The
few measurements I did show significant improvements sometimes, and
sometimes no improvement at all (but at least it doesn't get
slower...)

Specialization is enabled with "-specialize" and implies
"-scrutinize". Optimization-levels 3 and higher will enable
specialization as well.

Additionally to the rewriting done by the compiler, the flow analysis
pass has been improved quite a bit. Flow-sensitive handling of
conditionals and (sometimes) assignments has been added, as well as
special handling of variable arguments to procedures of known type and
use of predicates on variable arguments.

The latter is what "Typed Racket" calls "occurrence typing" (or so
I believe):

  (if (string? x)
      (string-append x ".")  ; "x" is known to be a string here, use 
##sys#string-append
      ...)                 ; "x" is something else

"Enforcement" of argument types means that a variable passed to a
known procedure indicates what type it must have, if the function
returns (only valid if the procedure checks its argument types):

  (let ((a (car x))      ; "car" returns? then "x" must be a pair
        (b (cdr x)))     ; golly! "x" is a pair, use unsafe inline operation 
for this one
    ...)

Handling of library procedures that do not return are handled inside
conditionals:

  (define (foo2 x)
    (if (string? x) ; if this conditional returns, "x" must be a number 
        (error "foo") 
        (+ x 3)) 
    (string-append x "abc"))   ; will trigger a warning, "x" assumed to be 
number

Note that assignments generally reduce the amount of type-information
that can be inferred. Also, flow-analysis is still local, and not
carried through to procedure calls or -returns. Well, not quite,
because a procedure call where the procedure is not externally visible
(or "local" mode is enabled) and where the call is textually following
the definition, can assume the called procedure has the type that was
previously calculated by the flow-analysis:

  (define (foo x) (string-append x " my foot."))

  ... (foo ...) ...        ; "foo" known to take and return a string.

(Very) simple alias analysis for "let"-bound variables is done.

Conditionals where the test is known to return a non-boolean will drop
their "else" branch (as requested by Joerg Wittenberger).

The results of the type-analysis can be somewhat improved, under the
assumption that variables are "strictly" typed, which means that they
do not change their type by assignment. The compiler option
"-strict-types" will enable this mode but violating these assumptions
will result in undefined behaviour. This also applies when core
library procedures are redefined. Optimization levels 2 and higher
assume standard and extended bindings are not globally modified, so
this is not new, but specialization will quickly result in incorrect
rewriting of the source program in such cases.

Global definitions can have type declarations, like this:

  (: foo (string -> number))
  (define (foo str) ...)

Implicit type-declarations are done for unexported toplevel bindings
or when using "-block" or "-local" (the latter being implied by
optimization levels 3 and higher). You can view these with "-debug I".
Usually the declaration should precede the definition. With
"-strict-types" the compiler will assume the formal parameters of the
associated definition will have the types indicated.

Type-information can be written to a file ("-emit-type-file") and
installed. The compiler will automatically load files with the
".types" extension from the repository for extensions imported with
"require-extension" or "use". This feature has not been tested much,
but opens up the possibility for extending the available type
information for extensions.

Not all scrutinizer messages are critical, but sometimes one wants as
much information as possible, for example, when the test of a
conditional is always true (like in the expansion of "and-let*").  For
this the meaning of the "-verbose" compiler option has been
changed. It used to show progress information about compiler passes,
but since this is normally not very interesting, "-verbose" only
enables non-critical messages that still might be of interest. To see
what the compiler is doing use "-debug p".

Toplevel FFI bindings ("(define foo (foreign-lambda ...))", etc.)
generate an implicit type-declaration, as full type-information is
available here. Again, this only works with "-local" or "-block" or
when the toplevel binding is hidden.

There is now a "the" (similar to the "the" found in Common Lisp),
which can be used to declare an expression's type inline. There
also is an "assume" that does local variable type declarations:

  (assume ((x pair) (y number)) ...)

  ~>

  (let ((x (the pair x)) (y (the number y))) ...)

Caveats:

Violating type-declarations will result in undefined behaviour.

Modifying an object with "object-become!" will have interesting but
unpleasant implications, should code be specialized for the object
having a particular type.

Assignments make flow-analysis more complicated and less precise.

The types implicitly declared for FFI forms do not play well with
user-defined foreign types that have custom argument/result conversion
functions which means non-critical warnings may be generated.

So far most eggs seem to work fine with specialization enabled. The
one egg that does not work is "stalin", but the code redefines various
standard procedures, which is likely to be the reason for the failure.

Do not expect everything to be just magically more efficient.  Even
though many checks can be removed (particularly procedure checks), I
have not done a thorough performance analysis.

Because it might be of interest to the performance-addicted, I also
say something about the specification of rewrite rules, which is done
in the file types.db.  It is possible to do this in user code, like
this:

  (: next (* -> *)
     ((number) (add1 #(1)))
     ((pair) (cdr #(1)))
     ...)

The format of these rules is quite obscure and the templates given for
the rewrite are an abnormous s-expression rendering of the internal
node tree, and of course completely undocumented. These rules also get
exported in ".types" files. Desperate users interested in this should
consult the source code or contact me for more information. Otherwise
don't use it.

For local use on the other hand, there is a cleaner form of specifying
rewrite rules, say:

  (define-specialization (foo (x fixnum) (y float))
    (frob-fix-and-flo x y))

"foo" must have a declared type (this is currently not checked) and
all calls of "foo" where the argument types are known to be of type
"fixnum" + "float" will be replaced by code that executes
"(frob-fix-and-flo ...)", but only if enough type information is
available. Note that these user-defined specializations are _not_
exported into ".types" files.

An elegant weapon. For a more civilized age.

All the rewrite-rules for the core-libraries are stored in types.db.
Suggestions for more rewrite rules for the core procedures are always
welcome. It would probably also be worthwhile to refactor the
libraries a bit to give more opportunities for rewriting.

One additional change that was necessary is parameter-assignment:
Invoking a parameter procedure with an arguments returns the new value
(and not an undefined value). This was done to keep the
type-declarations consistent (built-in parameter procedures must be
declared to have a return value of the same type in the zero- and
one-argument case).

To build the system you MUST make a "boot-chicken" first -
specialization is used for the core libraries and the compiler (the
bootstrapping chicken will be built without specialization).

See the "Types" manual chapter for documentation on the new
type-related things.


cheers,
felix