Strength-reduced TYPEP forms don't always flow types through conditional forms
The flow-sensitive constraint propagation pass only handles a restricted set of predicates: typep, eq, eql, <, >, and predicates in *backend-
I see two complementary fixes:
1. Add a new class of optimizers for functions used as predicates. The optimizers could return a set of constraints to add to variables when the function returns true or false. This would likely be useful for code that uses predicates (e.g. MEMBER) instead of equivalent TYPEP forms.
2. Some type expand into complex tests, and the previous approach would likely not suffice; it would also entail adding a lot of code in the compiler to recover information that is always available to TYPEP forms. Ideally, complex type test forms would be tagged with the type they test for. That way, constraint propagation could directly get to that tag and adjoin TYPEP constraints.
Moreover, such a tag would enable IR1 optimisation to eliminate redundant type tests when the result of the TYPEP form is known, but not the path through the test form.
The problem is, code generation also likes to treat predicate combinations specially, and if/if conversion is important to get decent code out of typical branchy lisp source. Simply wrapping the generated form in a special combination makes everything more complicated. So far, the most promising approach seems to be to annotate the consequent and alternative branches:
(typep x foo) => (let ((value x)) (cond ([test form] [annotate value with type foo] t) (t [annotate value with type (not foo)] nil)))
Dummy combinations seem to work (if/if conversion will duplicate the correct branch and eliminate redundant test for equality with NIL). Constraint propagation only has to adjoin the constraints corresponding to the annotations as it walks basic blocks. Moreover, when an annotation detects that derived types conflict and that the branch it guards is dead, it can rewrite itself into another form, and IF optimisation can then unconditionally jump to the other branch; the predicate form will be flushed as much as possible.
However, the annotation also makes it difficult to tell whether the type-tested value is only used in the type test, which may allow further transforms to trigger. Less hacky annotations, perhaps encoded directly in the CFG, may be a better idea.
Another, simpler approach would be to try and delay the total conversion of TYPEP forms until after constraint propagation: either all of the source transform logic, or just wrapping the TYPEP form in an annotation, and dropping the wrapper after constraint. Of course, it may only seem simpler because I haven't implemented it yet; the annotations grew more complicated as I converged to workingness.
|Changed in sbcl:|
|status:||In Progress → Fix Committed|
|assignee:||Paul Khuong (pvk) → nobody|
|Changed in sbcl:|
|status:||Fix Committed → Fix Released|