From: Nikodemus S. <nik...@ra...> - 2007-09-15 13:05:19
|
The attached patches implement DX support for CONS, and for nested calls. The first patch takes care of (LET ((X (CONS 1 2))) (DECLARE (DYNAMIC-EXTENT X)) ...) and the second handles (LET ((X (LIST (LIST 1 2) (LIST 3 4)))) (DECLARE (DYNAMIC-EXTENT X)) ...) I'm pretty confident they are correct, but a review would be much appreciated. Cheers, -- Nikodemus |
From: Christophe R. <cs...@ca...> - 2007-09-15 17:32:07
|
"Nikodemus Siivola" <nik...@ra...> writes: > + ;; If the function result is DX, so are its arguments... This > + ;; assumes that all our DX functions do not store their arguments > + ;; anywhere -- just use, and maybe return. I'm not entirely sure about this, from the point of view of the future (I'm trying to think of a CL function which allocates, and for which this isn't true; such may not exist...). Anyway, there's also a class of functions where some arguments are DX even if the result isn't: the various mappers and similar. How hard do you think it would be to handle the following cases? (mapcar (lambda (x) ...) ...) (flet ((foo ...)) ;; no DX declaration (mapcar #'foo ...)) ; the only use of #'FOO Cheers, Christophe |
From: Nikodemus S. <nik...@ra...> - 2007-09-15 18:15:25
Attachments:
0003-multiply-used-DX-LVARS.patch
|
On 9/15/07, Christophe Rhodes <cs...@ca...> wrote: > "Nikodemus Siivola" <nik...@ra...> writes: > > > + ;; If the function result is DX, so are its arguments... This > > + ;; assumes that all our DX functions do not store their arguments > > + ;; anywhere -- just use, and maybe return. > > I'm not entirely sure about this, from the point of view of the future > (I'm trying to think of a CL function which allocates, and for which > this isn't true; such may not exist...). It needs a KLUDGE marker at least, I think... But given that our current scheme requires an explicit DEFOPTIMIZER for each DX supporting function, I don't think it's too bad. > Anyway, there's also a class of functions where some arguments are DX > even if the result isn't: the various mappers and similar. How hard > do you think it would be to handle the following cases? > > (mapcar (lambda (x) ...) ...) > > (flet ((foo ...)) > ;; no DX declaration > (mapcar #'foo ...)) ; the only use of #'FOO Not very hard, I think. Attached a third patch of the series (depends on the two first ones), which adds support for DX LVARs with multiple uses: (defun foo () (declare (optimize speed)) (let ((dx (if (quux) (list 1 2 3) (list 3 2 1)))) (declare (dynamic-extent dx)) ...)) Cheers, -- Nikodemus |
From: Alexey D. <ade...@to...> - 2007-09-15 19:34:28
|
Hello, "Nikodemus Siivola" <nik...@ra...> writes: > The attached patches implement DX support for CONS, > and for nested calls. You have almost convinced me that prolongation of life-time of dynamic-extent variables is safe in the current SBCL, but then I've remembered about EQL-substitution of variables by the constraint propagation... So: (defun-with-dx nested-dx-lists (s) (let ((l 0)) (print (multiple-value-call #'list :before (let ((x 1) ; keep L2 as a variable till constraint propagation (l2 (list 1 2 3)) ; here it is allocated--and remains in the middle of MV-block ) (setq x 4) (setq l l2) (when (< x 4) (print l2))) :after)) (loop repeat 100 do (let ((l1 (list (list l 2) 1))) (funcall (if t ; keep L3 till L and L2 are substituted into L1 (lambda (l3) (declare (dynamic-extent l3)) (check l3) ; some DX-safe function s) #'identity) l1))))) Compilation by 1.0.8.46 with your second patch causes failed AVER in stack analisys. -- Regards, Alexey Dejneka "Alas, the spheres of truth are less transparent than those of illusion." -- L.E.J. Brouwer |
From: James Y K. <fo...@fu...> - 2007-09-15 23:13:46
|
On Sep 15, 2007, at 9:05 AM, Nikodemus Siivola wrote: > The attached patches implement DX support for CONS, > and for nested calls. I'd really like is to be able to be confident that DX declarations I insert are actually *correct*. With type declarations, sbcl will check them when compiling with sufficient safety, so you can be fairly confident that things won't blow up when then running in high speed/low safety. DX ought to be the same. Without that, there is no way to be sure you aren't going to crash in totally mysterious and impossible to debug ways when running with low safety. Basically in safe mode, for every DX declaration that the compiler can't already tell is obviously correct, I'd like it to insert an unwind-protect with some teardown code to mark the supposed-to-be-DX- allocated objects in some way such that any further use will fail in a clear manner. James |
From: Alexey D. <ade...@to...> - 2007-09-16 17:27:49
|
Alexey Dejneka <ade...@to...> writes: > "Nikodemus Siivola" <nik...@ra...> writes: > >> The attached patches implement DX support for CONS, >> and for nested calls. > > You have almost convinced me that prolongation of life-time of > dynamic-extent variables is safe in the current SBCL, but then I've > remembered about EQL-substitution of variables by the constraint > propagation... So: [example skip] Having tought some more, I see that the bug already exists: just replace L1 with L in the last line :-(. -- Regards, Alexey Dejneka "Alas, the spheres of truth are less transparent than those of illusion." -- L.E.J. Brouwer |
From: <wil...@ai...> - 2007-09-20 12:23:30
|
On Sat, Sep 15, 2007 at 07:13:30PM -0400, James Y Knight wrote: > > On Sep 15, 2007, at 9:05 AM, Nikodemus Siivola wrote: > > > The attached patches implement DX support for CONS, > > and for nested calls. > > I'd really like is to be able to be confident that DX declarations I > insert are actually *correct*. With type declarations, sbcl will > check them when compiling with sufficient safety, so you can be > fairly confident that things won't blow up when then running in high > speed/low safety. DX ought to be the same. Without that, there is no > way to be sure you aren't going to crash in totally mysterious and > impossible to debug ways when running with low safety. > > Basically in safe mode, for every DX declaration that the compiler > can't already tell is obviously correct, I'd like it to insert an > unwind-protect with some teardown code to mark the supposed-to-be-DX- > allocated objects in some way such that any further use will fail in > a clear manner. Is it technically possible to achieve what you want? If I understand correctly, the DX-allocated objects will still be in a region of memory which is reserved for the stack. You can mark them with #xDEADBEEF-like-pattern as the stack is popped at return time, sure. But that won't stop them from being overwritten by arbitrary binary data pushed at future subroutine calls, and any number of such future subroutine calls can intervene between DX allocation of a data structure and misuse of the DX allocation by code outside dynamic extent. (I think it would be possible to make a slow safe+debugging mode where declared-DX data are allocated on the heap, and also invalidated by the UNWIND-PROTECT form: a sort of CL analogue of some kinds of heap-oops detectors for C and C++. But I don't think that's what you were proposing.) To me, DX declarations seem so inherently dangerous that users can't reasonably expect much protection from them other than suppressing them in safe code. (And if ANSI didn't make it so inconvenient for users to implement policy-dependent macroexpansions, I'd question even whether we should be suppressing them in safe code.) For any given compiler which can prove that any given DX declaration is safe, the DX declaration is nearly redundant: the compiler is already nearly advanced enough to do the DX optimization without the declaration. -- William Harold Newman <wil...@ai...> PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C Ubi saeva indignatio ulterius cor lacerare nequit. -- Jonathan Swift's epitaph |
From: James Y K. <fo...@fu...> - 2007-09-20 14:56:47
|
On Sep 20, 2007, at 8:26 AM, William Harold Newman wrote: > (I think it would be possible to make a slow safe+debugging mode where > declared-DX data are allocated on the heap, and also invalidated by > the UNWIND-PROTECT form: a sort of CL analogue of some kinds of > heap-oops detectors for C and C++. But I don't think that's what you > were proposing.) That's exactly what I as proposing. SBCL already allocates on the heap in safe mode. I'd like it to additionally do the invalidation step. > To me, DX declarations seem so inherently dangerous that users can't > reasonably expect much protection from them other than suppressing > them in safe code. (And if ANSI didn't make it so inconvenient for > users to implement policy-dependent macroexpansions, I'd question even > whether we should be suppressing them in safe code.) They're dangerous, if you get them wrong. Right now it's essentially impossible to verify that you didn't get them wrong. Doing dx checking in safe mode makes it feasible to ensure with high probability that you don't get them wrong. I consider this similar to type declarations; SBCL helps out a lot there by verifying every single type declaration in safe code, unless it can prove they're correct already. > For any given > compiler which can prove that any given DX declaration is safe, the DX > declaration is nearly redundant: the compiler is already nearly > advanced enough to do the DX optimization without the declaration. I'm be perfectly happy to have the compiler become more advanced in its detection of when DX can be used. But that's really a separate issue. James |
From: Nikodemus S. <nik...@ra...> - 2007-09-27 08:55:18
|
On 9/20/07, James Y Knight <fo...@fu...> wrote: > > (I think it would be possible to make a slow safe+debugging mode where > > declared-DX data are allocated on the heap, and also invalidated by > > the UNWIND-PROTECT form: a sort of CL analogue of some kinds of > > heap-oops detectors for C and C++. But I don't think that's what you > > were proposing.) > > That's exactly what I as proposing. SBCL already allocates on the > heap in safe mode. I'd like it to additionally do the invalidation step. Make that "monstrously slow", unless we teach the backend(s) to emit code for a software read/write barrier: I may be missing something obvious here, but I don't see how to trap out-of-scope reads/writes to supposedly DX allocated objects without mprotect() tricks. > I'm be perfectly happy to have the compiler become more advanced in > its detection of when DX can be used. But that's really a separate > issue. That would probably be easier, for some cases at least. I'm thinking of code like (defun foo (...) ... (let ((x (list ...))) ...X used only in standard CL functions that don't keep refs to arguments...) ...)) Cheers, -- Nikodemus |
From: Nikodemus S. <nik...@ra...> - 2007-09-26 14:08:49
|
On 9/16/07, Alexey Dejneka <ade...@to...> wrote: > Having tought some more, I see that the bug already exists: just > replace L1 with L in the last line :-(. Does this mean that the patches are sane, after all? Or that 1 is good, but 2-3 are suspect as they compound existing bugs? Cheers, -- Nikodemus |
From: Alexey D. <ade...@to...> - 2007-09-26 14:59:33
|
Hello, "Nikodemus Siivola" <nik...@ra...> writes: > On 9/16/07, Alexey Dejneka <ade...@to...> wrote: > >> Having tought some more, I see that the bug already exists: just >> replace L1 with L in the last line :-(. > > Does this mean that the patches are sane, after all? I think they are worth to be committed: 1. They do not seem to create new bugs. 2. The old bug seem to require quite contrived code to be exposed. 3. In case of problems compiler reports on its bug; there are no random low-level crashes. -- Regards, Alexey Dejneka "Alas, the spheres of truth are less transparent than those of illusion." -- L.E.J. Brouwer |
From: Alexey D. <ade...@to...> - 2007-09-26 19:44:36
|
"Nikodemus Siivola" <nik...@ra...> writes: > +(defun handle-nested-dynamic-extent-lvars (arg) > + (let ((use (lvar-uses arg))) > + ;; Stack analysis wants DX value generators to end their > + ;; blocks. Uses of mupltiple used LVARs already end their blocks, > + ;; so we just need to process used-once LVARs. > + (when (node-p use) > + (node-ends-block use)) > + ;; If the function result is DX, so are its arguments... This > + ;; assumes that all our DX functions do not store their arguments > + ;; anywhere -- just use, and maybe return. > + (if (basic-combination-p use) Well, it should not be that straightforward. The right conditions are: * it is a COMBINATION - not m-v-call! * it is of kind :KNOWN * processed arguments are known to be included to the result and not stored elsewhere. The following program seems to be correct to me (except for usage of PRINT): (defvar *h* (make-hash-table)) (locally (declare (optimize (speed 3) (safety 0))) (defun foo (x) (let ((l (setf (gethash x *h*) (list x x x)))) (declare (dynamic-extent l)) (print l) (print (length l)) nil))) -- Regards, Alexey Dejneka "Alas, the spheres of truth are less transparent than those of illusion." -- L.E.J. Brouwer |
From: Nikodemus S. <nik...@ra...> - 2007-09-27 10:26:14
|
On 9/26/07, Alexey Dejneka <ade...@to...> wrote: > Well, it should not be that straightforward. The right conditions are: > > * it is a COMBINATION - not m-v-call! > * it is of kind :KNOWN > * processed arguments are known to be included to the result > and not stored elsewhere. Right, like in RECHECK-DYNAMIC-EXTENT-LVARS. > The following program seems to be correct to me (except for usage of PRINT): > > (defvar *h* (make-hash-table)) > > (locally (declare (optimize (speed 3) (safety 0))) > (defun foo (x) > (let ((l (setf (gethash x *h*) (list x x x)))) > (declare (dynamic-extent l)) > (print l) > (print (length l)) > nil))) Urk. Fixed coming up. Cheers, -- Nikodemus |
From: Nikodemus S. <nik...@ra...> - 2007-09-27 15:46:59
|
On 9/27/07, Nikodemus Siivola <nik...@ra...> wrote: > > The following program seems to be correct to me (except for usage of PRINT): > > > > (defvar *h* (make-hash-table)) > > > > (locally (declare (optimize (speed 3) (safety 0))) > > (defun foo (x) > > (let ((l (setf (gethash x *h*) (list x x x)))) > > (declare (dynamic-extent l)) > > (print l) > > (print (length l)) > > nil))) > > Urk. Fixed coming up. Fixed in 1.0.10.8: the "is this a good USE for a DX-lvar" factored out from RECHECK-DYNAMIC-EXTENT-LVARS, and used also in HANDLE-NESTED- DYNAMIC-EXTENT-LVARS to check the uses. Cheers, -- Nikodemus |
From: Christophe R. <cs...@ca...> - 2007-09-27 17:53:21
|
Alexey Dejneka <ade...@to...> writes: > The following program seems to be correct to me (except for usage of PRINT): > > (defvar *h* (make-hash-table)) > > (locally (declare (optimize (speed 3) (safety 0))) > (defun foo (x) > (let ((l (setf (gethash x *h*) (list x x x)))) > (declare (dynamic-extent l)) > (print l) > (print (length l)) > nil))) Is it? I would have expected that this was a bad dynamic-extent declaration, as the value bound to L is not inaccessible after the form executes. What am I missing? (I'm also not sure why the usage of PRINT is bad) Best, Christophe |
From: Alexey D. <ade...@to...> - 2007-09-27 18:56:53
|
Hello, Christophe Rhodes <cs...@ca...> writes: > Alexey Dejneka <ade...@to...> writes: > >> The following program seems to be correct to me (except for usage of PRINT): >> >> (defvar *h* (make-hash-table)) >> >> (locally (declare (optimize (speed 3) (safety 0))) >> (defun foo (x) >> (let ((l (setf (gethash x *h*) (list x x x)))) >> (declare (dynamic-extent l)) >> (print l) >> (print (length l)) >> nil))) > > Is it? I would have expected that this was a bad dynamic-extent > declaration, as the value bound to L is not inaccessible after the > form executes. Ok. I considered bound DYNAMIC-EXTENT to mean "the body does not create new references", but now I've reread CLHS and it seems to agree with you for top-level objects. But let's correct the example slightly: (locally (declare (optimize (speed 3) (safety 0))) (defun foo (x) (let ((l (list (setf (gethash x *h*) (list x x x))))) (declare (dynamic-extent l)) (print l) (print (length l)) nil))) Now the saved list is otherwise accessible part of L, so CLHS does not even require the body to refrain from saving (CAR L), does it? :-/ > (I'm also not sure why the usage > of PRINT is bad) What does prevent PRINT from saving its argument? (E.g. when some PRINT-OBJECT is implemented via CLIM:PRESENT.) -- Regards, Alexey Dejneka "Alas, the spheres of truth are less transparent than those of illusion." -- L.E.J. Brouwer |
From: Christophe R. <cs...@ca...> - 2007-09-27 19:14:36
|
Alexey Dejneka <ade...@to...> writes: > Ok. I considered bound DYNAMIC-EXTENT to mean "the body does not > create new references", but now I've reread CLHS and it seems to agree > with you for top-level objects. But let's correct the example slightly: > > (locally (declare (optimize (speed 3) (safety 0))) > (defun foo (x) > (let ((l (list (setf (gethash x *h*) (list x x x))))) > (declare (dynamic-extent l)) > (print l) > (print (length l)) > nil))) > > Now the saved list is otherwise accessible part of L, so CLHS does not > even require the body to refrain from saving (CAR L), does it? :-/ Right, I think I agree with you that this is a legal DX declaration and that this would cause problems for Nikodemus' (old version of) his patch (and also that the body can do what it likes with (CAR L)). >> (I'm also not sure why the usage >> of PRINT is bad) > > What does prevent PRINT from saving its argument? (E.g. when some > PRINT-OBJECT is implemented via CLIM:PRESENT.) Oh, yes, of course. Best, Christophe |