Steel Bank Common Lisp

Strength-reduced TYPEP forms don't always flow types through conditional forms

Reported by Paul Khuong on 2013-09-23
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Low
Unassigned

Bug Description

The flow-sensitive constraint propagation pass only handles a restricted set of predicates: typep, eq, eql, <, >, and predicates in *backend-predicate-types*. This has always caused issues when for TYPEP forms that are macroexpanded (structure types are an obvious example). Recently, support has been added on x86oids to convert (MOD X) typechecks into a single comparison, instead of comparing with < and >. Such comparison forms are opaque to constraint propagation, and some code might suffer (testing for WORD goes through a primitive that's known to *b-p-t*).

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.

Paul Khuong (pvk) wrote :

I've thought about annotating LVARs with information about what the nodes that use them compute. While that may be a good idea to allow further type propagation and type-directed simplification of inlined functions, it won't work for type tests.

Type tests are often of the form (or ... ...) or (and ... ...); these get compiled to conditionals, and, if we want to have decent code, we need if/if conversion to trigger. Unfortunately, as soon as that happens, the LVAR that receives the value for the initial OR/AND form disappears.

The approach in https://github.com/pkhuong/sbcl/tree/mnesic-type-tests still works: the body for each branch is annotated with special functions that track type information and detect code that is dead because of type mismatches.

However, I'm starting to think that a simpler solution will do most of the job: wrap TYPEP expanded forms with a function that is a fancy identity, (typep-info [typep-boolean] [variable] [type]). After a single round of constraint propagation, all the REF nodes have been annotated with types, and TYPEP-INFO can hopefully be converted into a constant, and otherwise simply bypassed. It's probably possible to devise code such that this simpler choice will cause worse code than the branch above, but it's also probably good enough, and definitely on the Pareto frontier for simplicity:propagation quality.

Paul Khuong (pvk) wrote :

This branch https://github.com/pkhuong/sbcl/tree/pluggable-constraints adds two new classes of optimizers to hook into constraint propagation, and uses them to implement the simpler proposal above. Unless there's something wrong, I'll commit after the freeze.

Paul Khuong (pvk) on 2013-11-04
Changed in sbcl:
status: In Progress → Fix Committed
assignee: Paul Khuong (pvk) → nobody
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers