-
Notifications
You must be signed in to change notification settings - Fork 5
Provisional deftransform
Recently I've added facilities to Cleavir enabling Clasp to do float arithmetic unboxed, e.g. (sin (exp (the double-float a))) does not cons a boxed double for the result of exp. This is a general facility but I'm still developing it. A brief introduction to how it works follows:
First, I've expanded on the cleavir-attributes facility. Attributes are information about functions themselves (as opposed to their calls, as the CL type system expresses). Before my changes, the attributes were just a set of flags, but now there is an attributes class with more information.
Attributes are like types in that they can be conjoined and disjoined and have a sub-attributes-p. They are unlike types in that there is no standard facility for a programmer to define them; thus the client system has full discretion over what information to provide to Cleavir, and so Cleavir can "believe" attributes without testing them. Relatedly, attributes can generally not be tested like types, though they may sometimes be possible to infer. They are included in environment information, so the client has to affirmatively provide an attributes object for a given function name in a given environment. (If no attributes are defined, no special optimizations are made possible.)
Attributes flow through IR like types. Before my changes, they were attached directly to literal calls, which had the odd result that (sin x) would have attributes while (funcall #'sin x) would not. This has now been fixed, so the forms can both be optimized with the same information.
Currently the attributes object has only two components: A set of flags, and a list of transform keys (explained below). The flags so far contain information on the dynamic-extent treatment of the function's arguments, and whether calls to the function can be flushed if unused (e.g. there are no side effects needing preservation).
- Clients should be able to add more things as attributes
- Parameter-specific attributes
- Type derivation information (e.g. something that can determine that adding two floats gets you another float)
- Improve flow merger (e.g.
(if test #'+ #'-)could still be inferred as returning a float if given two floats)
Transforms are probably the most important part of the changes. A "transform" is an IR-editor provided by the client, specific to calls to a given function, and which can use inferred information about arguments etc. They can be thought of as more powerful compiler macros.
An example of a transform would be one on eql that reduces to eq when possible. This can be done when at least one of the arguments to eql has been inferred to have an eq-comparable type, such as if one is a symbol. The transform function would examine the IR to check whether either parameter must be eq-comparable (i.e. that its inferred type is a subtype of the generally-client-defined type of eq-comparable objects). If it is, it would rewrite the call to eql into a call to eq, or more directly into a use of the cleavir-primop:eq primop. If it's not, and the transform is impossible, the transform function simply does nothing.
Transforms are attached to attributes through an indirect key mechanism[^mlf]. The client writes a transform particular to some function and attaches it to that function's attributes in the environment. Cleavir will then call the transform function during its meta evaluation phase. The transform function determines whether it is applicable, and returns false if it is not; otherwise it edits the IR and returns true to let Cleavir know the call is gone.
Because the transform can do arbitrary things based on IR information, it is more flexible than compiler macros or inlining. For example, for the form (expt x n), a transformer that knows n is a constant could generate addition-chain multiplication code specific to that constant, on demand.
Transforms can also insert type information. Clasp has a transform on sin (and other functions) that marks it as returning a double if its argument is a double. More complex custom derivations can be done, e.g. inferring the type of (+ a b) based on the integer bounds of the types of a and b. This information is not expressible through standard types alone.
- Editing the IR directly is fraught and probably shouldn't be encouraged for clients. A cleaner mechanism is for the transformer to provide IR for a new function (possibly compiled on the spot) to be called in place of the unoptimized function; the new function can then be inlined. This helps centralize IR manipulation code in Cleavir's inliner while still allowing clients to insert arbitrary code.
- Type derivation should be done through a more specific, non-destructive mechanism as mentioned above under Attributes.
This is what allows Clasp to manipulate floats as unboxed entities. Currently, representation selection is part of Clasp rather than Cleavir, but I would like to move it ot Cleavir once I figure out a good way to do it while keeping different client concerns in mind.
When Clasp lowers code from BIR to BMIR, it adds a slot to most IR data indicating its "rtype". An "rtype", or "representation type", is an indication of how the datum should actually be represented at runtime. An rtype is either the symbol :multiple-values, meaning a general multiple value structure with any number of values, or a list of value rtypes. A value rtype is either :object, meaning a boxed object, or :single-float or :double-float, meaning unboxed singles and doubles respectively.
Primops are recorded in Clasp as having inputs and outputs of given rtypes. For example, there is an sf-ftruncate primop that implements cl:ftruncate for single floats. It has two parameters, both of which are expected to have value rtype :single-float, and its output rtype is (:single-float :single-float), meaning it outputs exactly two single floats.
Clasp determines what rtype a given datum should have by seeing what rtypes that datum's definitions expect to output, and what rtype its uses expect to input. For example, given (lambda (x) (declare (double-float x)) (sin x)), Clasp reduces the sin call to a use of the df-sin primop, which inputs and outputs a :double-float; however x, being the parameter to a function, will in general be boxed and so have rtype :object. Clasp prefers unboxed data to boxed data, and so gives the datum the rtype (:double-float). Then it inserts a "cast" instruction before the sine operation. This cast performs the unboxing required.
Because BMIR depends more on the properties of the target architecture and the client's runtime, it's difficult to make it really client-agnostic. For example an implementation may have different kinds of data it can manipulate unboxed, or it may be unable to unbox closed-over variables in general. I haven't yet worked out the best way to generalize this functionality.
- Port to Cleavir
- Cast placement can be non-optimal, e.g. inserting them into loops instead of outside them. A code motion pass should probably run after cast insertion.
- Allow unboxed parameters and return values when possible for local functions
- Flatten
multiple-value-callforms where the number of values of all parameters is known
[^mlf]: Originally the transform functions themselves were stored in the attributes object, but this means attributes objects were not externalizable, which posed a problem when a client might want to externalize an AST made as an inline function definition.