From: <me...@ho...> - 2005-12-06 17:08:44
Attachments:
test-arg-ordering.patch
bug-233.patch
|
On Monday 28 November 2005 19:56, Alexey Dejneka wrote: > Hello, > > G=E1bor Melis <me...@ho...> writes: > > Thanks for annotating http://paste.lisp.org/display/13919. Could > > you shed some light on why is that so? Chrishtophe was of the > > opinion that it was wrong and I alternate between blaming the > > substitute-single-use-lvar and constraint propagation. > > Changing SSUL will not help, because you can model the bug without > SSUL: > > (defun foo (x y) > (if (typep (multiple-value-prog1 x (setq x y)) 'double-float) > (+ x 1d0) > (+ x 2))) > > The interesting part of IR1 looks like this: > > IR1 block 2 start c17 > start stack: > 17> entry NIL > 18> 19: SB-INT:DOUBLE-FLOAT-P {GLOBAL-FUNCTION} > 20> 21: X > 22> 23: Y > 24> set X v23 > 25> 26: known combination v19 v21 > 27> if v26 c28 c29 > end stack: > successors c28 c29 > > This is interpreted by IR2 as > > 20> x->v21 > 22> y->v23 > 24> v23->x > 25> if (double-float-p (v21)) go c28 else go c29 > > i.e. the check uses the old value of X, which seems to be right to > me. > > Constraint propagation (as is said in the comment in the beginning of > the file) considers LVARs to be transparent, which is not right; e.g. > in the example above it thinks that at c28 not only v21, but also X > is of type DOUBLE-FLOAT. The solution I thought about was to > introduce a new kind of constraint: (EQL lambda-var lvar), and check > them before adding a constraint on a lambda-var. But it requires to > change the algorithm. E.g. "test constraints" generators are > determined on the simple prepass; the change seems to require to > perform a whole propagation of equalities before starting to look at > type constraints. I did not try to implement it, so I cannot say how > hard is it. I tried but it didn't look very promising, so I settled for a less elegant/generalizable but much easier solution that's attached as bug-233.patch based on my sketchy understanding of IR1 representation. It fixes 6 occurrences of the bug in the ansi tests with no visible regressions except for a slight performance hit on cl-bench. As to why that happens I have a few ideas: =2D the ok-lvar-lambda-var test may be too stringent now: it says no to lvars with USE and DEST in different blocks which may or may not be a problem since AFAICT USE is always in the same block as DEST except when the lvar is used by branches of a conditional, but that case was excluded by the old code as well (it tested for single use lvars). Let me know if/how I'm wrong about this. Preferably with an example. =2D the buggy constraint propagator happened to get the constraints right even in some of the situations where the the referenced variable was set before the test was made. Well, maybe. > > Also in add-test-constraints I'm baffled by the apparent asymmetry > > in the handling of EQ/EQL's args. For instance, if arg1 is constant > > and arg2 is not then no constraints are added. > > Commutative functions have a transformation, putting constant > arguments second :-) Aha. Actually this transformation is not always done. The attached test-arg-ordering.patch makes that statement more true. Unfortunately, it slows things down a bit because (defun xxx (x) (if (eq :something x) y 0)) is now compiled to: ; 0AFC01F5: 3B1D8C01FC0A CMP EBX, [#xAFC018C] ; :SOMETHING ; no-arg-pars= ing entry point ; 1FB: 7515 JNE L1 ; 1FD: 8B158C01FC0A MOV EDX, [#xAFC018C] ; :SOMETHING ; 203: L0: 8B4DF8 MOV ECX, [EBP-8] ; 206: 8B45FC MOV EAX, [EBP-4] ; 209: 83C102 ADD ECX, 2 ; 20C: 8BE5 MOV ESP, EBP ; 20E: 8BE8 MOV EBP, EAX ; 210: FFE1 JMP ECX ; 212: L1: BA0B000005 MOV EDX, 83886091 ; 217: EBEA JMP L0 while it was MOV EDX, EBX before for the second :SOMETHING. When the constant is the second argument cvs sbcl already does this pessimization. If one could tell whether a register already holds the desired constant value the the compiler could be more clever about it. Please review and comment, G=E1bor |
From: Alexey D. <ade...@ma...> - 2005-12-07 08:03:12
|
Hello, Gábor Melis <me...@ho...> writes: > I tried but it didn't look very promising, so I settled for a less > elegant/generalizable but much easier solution that's attached as > bug-233.patch based on my sketchy understanding of IR1 representation. > It fixes 6 occurrences of the bug in the ansi tests with no visible > regressions except for a slight performance hit on cl-bench. > > As to why that happens I have a few ideas: > > - the ok-lvar-lambda-var test may be too stringent now: it says no to > lvars with USE and DEST in different blocks which may or may not be > a problem since AFAICT USE is always in the same block as DEST except > when the lvar is used by branches of a conditional, (USE (if (ok) GEN (error))) (USE GEN (if ...)) (USE (let ((l ...)) (declare (dynamic-extent/special l)) ... GEN)) > - the buggy constraint propagator happened to get the constraints > right even in some of the situations where the the referenced variable > was set before the test was made. Well, maybe. An example? >> Commutative functions have a transformation, putting constant >> arguments second :-) > > Aha. Actually this transformation is not always done. The attached > test-arg-ordering.patch makes that statement more true. Unfortunately, > it slows things down a bit because > > (defun xxx (x) > (if (eq :something x) > y ^ x? > 0)) Yes. Replacing expressions with explicit constants in constraint propagation and in DERIVE-NODE-TYPE is a controversial optimization. > -#!-sb-fluid (declaim (inline ok-lvar-lambda-var)) > +;;; If LVAR has a single USE that is a REF to a LAMBDA-VAR and > +;;; LAMBDA-VAR is not set between LVAR's USE and DEST then return > +;;; OK-REF-LAMBDA-VAR of the USE, otherwise NIL. + FIXME: We also return NIL when USE and DEST are in different blocks, + even when there are no SETs between them. > (defun ok-lvar-lambda-var (lvar) -- Regards, Alexey Dejneka "Alas, the spheres of truth are less transparent than those of illusion." -- L.E.J. Brouwer |
From: <me...@ho...> - 2005-12-07 17:44:19
Attachments:
bug-233-2.patch
|
On Wednesday 07 December 2005 09:03, Alexey Dejneka wrote: > Gábor Melis <me...@ho...> writes: > > - the buggy constraint propagator happened to get the constraints > > right even in some of the situations where the the referenced > > variable was set before the test was made. Well, maybe. > > An example? Maybe something like: (defun xxx (x y) ;;(declare (fixnum y)) (when (typep (multiple-value-prog1 x (setq x y)) 'fixnum) (1+ x))) where Y is always a fixnum but it is not declared to be. > > (defun xxx (x) > > (if (eq :something x) > > y > ^ x? Yes, it should have been X. > > 0)) > > Yes. Replacing expressions with explicit constants in > constraint propagation and in DERIVE-NODE-TYPE is a controversial > optimization. How do you think it should be handled? Finding references to the same=20 constant and turning then into register movs if possible sounds good to=20 me, because it would speed up non-constraint-propagation-optimized=20 code, too. But I have no idea if it is feasible. > + FIXME: We also return NIL when USE and DEST are in different > blocks, + even when there are no SETs between them. I tried to get the performance back by making ok-lvar-lambda-var more=20 clever, but it resisted my attempts. Attached is an interpretation of=20 what you described: a new constraint type (EQL lambda-var lvar) is=20 added and propagated before the test constraints are added. Propagation=20 is done by the same mechanism that is used to propagate the test=20 constraints. * find-block-type-constraints sets up (EQL lambda-var lvar) constraints=20 with the help of maybe-add-eql-constraint-for-lvar * ok-lvar-lambda-var checks that there is an appropriate (EQL lambda-var=20 lvar) constraint core size: +30k cl-bench: no observable difference Cheers, G=E1bor PS: for what it's worth the way is paved to add (< lambda-var lvar) |
From: Alexey D. <ade...@ma...> - 2005-12-07 19:13:34
|
Gábor Melis <me...@ho...> writes: > Attached is an interpretation of > what you described: a new constraint type (EQL lambda-var lvar) is > added and propagated before the test constraints are added. Propagation > is done by the same mechanism that is used to propagate the test > constraints. > > * find-block-type-constraints sets up (EQL lambda-var lvar) constraints > with the help of maybe-add-eql-constraint-for-lvar > > * ok-lvar-lambda-var checks that there is an appropriate (EQL lambda-var > lvar) constraint A quick first observation: in order to completely fix 233b you need to s/ref/cast/ in CONSTRAINT-PROPAGATE-IN-BLOCK->TYPECASE, and update REF clause in ADD-TEST-CONSTRAINTS. I'll look harder at the patch later. -- Regards, Alexey Dejneka "Alas, the spheres of truth are less transparent than those of illusion." -- L.E.J. Brouwer |
From: <me...@ho...> - 2005-12-08 13:55:01
Attachments:
bug-233-3.patch
|
On Wednesday 07 December 2005 20:13, Alexey Dejneka wrote: > A quick first observation: in order to completely fix 233b you need > to s/ref/cast/ in CONSTRAINT-PROPAGATE-IN-BLOCK->TYPECASE, and update > REF clause in ADD-TEST-CONSTRAINTS. > > I'll look harder at the patch later. I included what you pasted at http://paste.lisp.org/display/14421#2 ,=20 enabled (eql lambda-var lvar) constraint generation for CASTs in=20 MAYBE-ADD-EQL-CONSTRAINT-FOR-LVAR and updated the REF clause so that=20 (if (m-v-prog1 x (setq x t) ..) works too. A few tests for the fixed=20 cases are now also included. core size: +70k on x86 cl-bench: see attached report (bignums win, defmethod loses) Cheers, G=E1bor |
From: Alexey D. <ade...@ma...> - 2005-12-08 18:31:00
|
Hello, Gábor Melis <me...@ho...> writes: > I included what you pasted at http://paste.lisp.org/display/14421#2 , > enabled (eql lambda-var lvar) constraint generation for CASTs in > MAYBE-ADD-EQL-CONSTRAINT-FOR-LVAR and updated the REF clause so that > (if (m-v-prog1 x (setq x t) ..) works too. A few tests for the fixed > cases are now also included. Self-rebuilding has shown a regression: SB!BIGNUM::BIGNUM-TRUNCATE is now compiled with a note. (defun use-result-constraints (block) (declare (type cblock block)) (constraint-propagate-in-block block (block-in block) :ref-preprocessor (lambda (node cons) + (maybe-add-eql-constraint-for-lvar node cons) (let* ((var (ref-leaf node)) (con (lambda-var-constraints var))) (constrain-ref-type node con cons))))) The second regression is in code (+ x x), which is compiled to x -> lv1 x -> lv2 cast lv1 'number -> lv3 cast lv2 'number -> lv4 + lv3 lv4 -> lv5 Generation of constraints at REF reduced the second CAST; new code does not. I think that CONSTRAINT-PROPAGATE-IN-BLOCK for CASTs does not work efficiently with cross-block LVARs: they are not present in GEN even on the second pass! -- Regards, Alexey Dejneka "Alas, the spheres of truth are less transparent than those of illusion." -- L.E.J. Brouwer |
From: <me...@ho...> - 2005-12-08 15:31:30
Attachments:
report
|
forgot to attach the the report |