Commit [ce6c27] Maximize Restore History

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
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

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.

Paul Khuong Paul Khuong 2013-10-24

changed src/compiler/constraint.lisp
changed src/compiler/knownfun.lisp
src/compiler/constraint.lisp Diff Switch to side-by-side view
src/compiler/knownfun.lisp Diff Switch to side-by-side view