Two new optimizer types for flow-sensitive type propagation
authorPaul Khuong <pvk@pvk.ca>
Thu, 24 Oct 2013 02:34:37 +0000 (22:34 -0400)
committerPaul Khuong <pvk@pvk.ca>
Mon, 4 Nov 2013 17:32:11 +0000 (12:32 -0500)
commitce6c2726bfb08211d6d281fdf070490110bdc374
treee96f27972069f6fd4bd7ab43914ed01e67f9028c
parent2023abc03e7a8ab27efd814b936f87b75b704102
Two new optimizer types for flow-sensitive type propagation

CONSTRAINT-PROPAGATE optimizers can add new information about the
state of the world after/if the function has returned.  Function
type declarations/propagation suffice for simple patterns (e.g.
return types, or unconditional type requirements on arguments),
but this optimizer is more general.

Such optimizers receive two arguments, the combination node and the
current set of constraints, and return a sequence of constraints.
Constraints are lists of three or four values:
 1. a constraint kind (either TYPEP, <, >, or EQL);
 2, 3. two arguments, either LVARs, LAMBDA-VARs or a CTYPE;
 4. optionally, whether the meaning of the constraint must be
    flipped.
This mimics the (defstruct (constraint ...)) in constraint.lisp.
If any of the argument is NIL, the constraint is skipped; otherwise,
it is added to current set of constraints.  Optimizers have access
to that set, and can thus map LVARs to LAMBDA-VARs thanks to
OK-LVAR-LAMBDA-VAR.

CONSTRAINT-PROPAGATE-IF optimizers can instead hook into the
interpretation of functions as predicate, when their result feeds
into an IF node.  They also receive the node and the current set
of constraints as arguments, and return four values.  The first two
values are an LVAR and a CTYPE: if they are non-NIL, that LVAR is
of that CTYPE iff the combination returns true.  The two remaining
values are sequences of constraints (see previous paragraph) for
the consequent (if-true) and alternative (if-false) branches,
respectively.  These are useful for more complex tests, but also
to represent partial information, e.g., if an EQUAL test fails,
the two values are not EQL either.
src/compiler/constraint.lisp
src/compiler/knownfun.lisp