Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

## Re: [Sbcl-devel] Constraint propagation problem.

 Re: [Sbcl-devel] Constraint propagation problem. From: Douglas Katzman - 2014-07-23 15:16:09 Attachments: Message as HTML ```Thanks. Your change works for me. I'd also like to fix this problem that equivalent formulations of (NOT hairy-array) aren't TYPE=. (TYPE= (SPECIFIER-TYPE '(NOT (AND ARRAY (NOT SIMPLE-ARRAY)))) (SPECIFIER-TYPE '(OR (NOT ARRAY) SIMPLE-ARRAY))) => NIL and NIL, should be T and T. What do you think of this patch which achieves that? Nothing breaks, and the above test passes. --- a/src/code/late-type.lisp +++ b/src/code/late-type.lisp @@ -2424,7 +2424,17 @@ used for a COMPLEX component.~:@>" ;; FIXME (and hint to PFD): we're vulnerable here to attacks of the ;; form "are (AND ARRAY (NOT (ARRAY T))) and (OR (ARRAY BIT) (ARRAY ;; NIL) (ARRAY CHAR) ...) equivalent?" -- CSR, 2003-12-10 - (make-negation-type :type type)) + (if (and (eq (array-type-dimensions type) '*) + (eq (array-type-complexp type) 't) + (eq (array-type-element-type type) *wild-type*)) + ;; not hairy-array = either simple array or (not array) + ;; This is deliberately asymmetric - trying to say that + ;; NOT simple-array is hairy-array|(not array) leads to infinite recursion. + (type-union (make-array-type '* :complexp nil + :element-type *wild-type*) + (make-negation-type + :type (make-array-type '* :element-type *wild-type*))) + (make-negation-type :type type))) ```

### Thread view

 [Sbcl-devel] Constraint propagation problem. From: Douglas Katzman - 2014-07-22 15:10:24 Attachments: Message as HTML ```I'm trying to fix an inefficiency of WITH-ARRAY-DATA. It does not know that if (NOT (ARRAY-HEADER-P)), then its object under test is simple or not an array. Since it doesn't begin with a check that the object is an array at all, it might need to check that, but in many cases there was already an assertion that the object is a vector. A reduced example would be: * (disassemble '(lambda (x) (declare (bit-vector x)) (if (array-header-p x) 'hairy (simpfn (the simple-bit-vector x))))) Before calling SIMPFN is a test of SIMPLE-BIT-VECTOR-P, though the type should be derived as both SIMPLE-ARRAY and BIT-VECTOR. ... ; 6A: 807EF1D5 CMP BYTE PTR [RSI-15], -43 ; 6E: 751B JNE L2 ; 70: 488BD6 MOV RDX, RSI ; 73: 488B055EFFFFFF MOV RAX, [RIP-162] ; # ... ; 8B: L2: 0F0B0A BREAK 10 ; error trap ; 8E: 04 BYTE #X04 ; 8F: 62 BYTE #X62 ; OBJECT-NOT-SIMPLE-BIT-VECTOR-ERROR ; 90: FE1B03 BYTE #XFE, #X1B, #X03 ; RSI Part of the issue is the inability to reason about ARRAY-HEADER-P. I've fixed that adequately. * (deftype array-header () '(or (and simple-array (not vector)) (and array (not simple-array)))) * (specifier-type '(and bit-vector (not array-header))) => # Without my changes the answer would have been: # Next I'm trying to emulate how TYPEP confers knowledge of the object's type, with something like this: * (setf (gethash 'sb-kernel:array-header-p sb-c::*backend-predicate-types*) (specifier-type 'array-header)) * (disassemble '(lambda (s) (if (bit-vector-p s) (if (sb-c::%typep-wrapper (sb-kernel:array-header-p s) s 'array-header) 'hairy (simpfn (the simple-bit-vector s)))))) and I'm still getting the type-check as shown in the above disassembly. But it should have propagated (type-intersection (specifier-type 'bit-vector) (specifier-type '(not array-header))) => # What's going wrong? ```
 Re: [Sbcl-devel] Constraint propagation problem. From: Paul Khuong - 2014-07-23 04:18:29 Attachments: constraint.diff ```Douglas Katzman wrote: > I'm trying to fix an inefficiency of WITH-ARRAY-DATA. It does not know > that if (NOT (ARRAY-HEADER-P)), then its object under test is simple or > not an array. > Since it doesn't begin with a check that the object is an array at all, > it might need to check that, but in many cases there was already an > assertion that the object is a vector. A reduced example would be: > > * (disassemble > '(lambda (x) > (declare (bit-vector x)) > (if (array-header-p x) 'hairy (simpfn (the simple-bit-vector x))))) There are multiple issues at play here. The root problem is that constraint propagation is extra weak on *combining* constraints (in short, we work on an uninterpreted powerset of constraints that appear in the input IR1), especially for negated type info. That's likely a deliberate choice in order to guarantee obvious termination as and to keep compile times reasonable. The downside is that constraint propagation will sometimes fail to derive obvious stuff like your example above. That's part of the reason I introduced constraint-propagate-if optimizers in ce6c2726bfb08211d6d281fdf070490110bdc374. We can now write (defoptimizer (array-header-p constraint-propagate-if) ((var) node constraints) (values nil nil nil `((typep ,(ok-lvar-lambda-var var constraints) ,(specifier-type '(simple-array * 1)))))) Combined with the patch below (which augments constraints for the alternative arm even when the consequent doesn't yield any useful info), I get CL-USER> (disassemble '(lambda (x) (declare (bit-vector x)) (if (sb-c::array-header-p x) 'hairy (simpfn (the simple-bit-vector x))))) ; disassembly for (LAMBDA (X)) ; Size: 53 bytes ; 07B6FF2C: 8D46F1 LEA EAX, [RSI-15] ; no-arg-parsing entry point ; 2F: A80F TEST AL, 15 ; 31: 7513 JNE L0 ; 33: 807EF1E5 CMP BYTE PTR [RSI-15], -27 ; 37: 720D JB L0 ; 39: 488B1570FFFFFF MOV RDX, [RIP-144] ; 'HAIRY ; 40: 488BE5 MOV RSP, RBP ; 43: F8 CLC ; 44: 5D POP RBP ; 45: C3 RET ; 46: L0: 488BD6 MOV RDX, RSI ; 49: 488B0568FFFFFF MOV RAX, [RIP-152] ; # ; 50: B902000000 MOV ECX, 2 ; 55: FF7508 PUSH QWORD PTR [RBP+8] ; 58: FF6009 JMP QWORD PTR [RAX+9] ; 5B: 0F0B0A BREAK 10 ; error trap ; 5E: 02 BYTE #X02 ; 5F: 19 BYTE #X19 ; INVALID-ARG-COUNT-ERROR ; 60: 9A BYTE #X9A ; RCX I'll commit the fix to constraint.lisp soon after the freeze. Paul ```
 Re: [Sbcl-devel] Constraint propagation problem. From: Douglas Katzman - 2014-07-23 15:16:09 Attachments: Message as HTML ```Thanks. Your change works for me. I'd also like to fix this problem that equivalent formulations of (NOT hairy-array) aren't TYPE=. (TYPE= (SPECIFIER-TYPE '(NOT (AND ARRAY (NOT SIMPLE-ARRAY)))) (SPECIFIER-TYPE '(OR (NOT ARRAY) SIMPLE-ARRAY))) => NIL and NIL, should be T and T. What do you think of this patch which achieves that? Nothing breaks, and the above test passes. --- a/src/code/late-type.lisp +++ b/src/code/late-type.lisp @@ -2424,7 +2424,17 @@ used for a COMPLEX component.~:@>" ;; FIXME (and hint to PFD): we're vulnerable here to attacks of the ;; form "are (AND ARRAY (NOT (ARRAY T))) and (OR (ARRAY BIT) (ARRAY ;; NIL) (ARRAY CHAR) ...) equivalent?" -- CSR, 2003-12-10 - (make-negation-type :type type)) + (if (and (eq (array-type-dimensions type) '*) + (eq (array-type-complexp type) 't) + (eq (array-type-element-type type) *wild-type*)) + ;; not hairy-array = either simple array or (not array) + ;; This is deliberately asymmetric - trying to say that + ;; NOT simple-array is hairy-array|(not array) leads to infinite recursion. + (type-union (make-array-type '* :complexp nil + :element-type *wild-type*) + (make-negation-type + :type (make-array-type '* :element-type *wild-type*))) + (make-negation-type :type type))) ```