Re: ivopts vs. garbage collection
On Mon, 11 Jan 2016 13:51:25 -0700 Tom Tromey wrote: > > "Michael" == Michael Matz writes: > > Michael> Well, that's a hack. A solution is to design something that > Michael> works generally for garbage collected languages with such > Michael> requirements instead of arbitrarily limiting transformations > Michael> here and there. It could be something like the notion of > Michael> derived pointers, where the base pointer needs to stay alive > Michael> as long as the derived pointers are. > > This was done once in GCC, for the Modula 3 compiler. > There was a paper about it, but I can't find it any more. > > The basic idea was to emit a description of the stack frame that their > GC could read. They had a moving GC that could use this information > to rewrite the frame when moving objects. This one perhaps? https://www.cs.purdue.edu/homes/hosking/papers/ismm06.pdf Julian
Re: ivopts vs. garbage collection
> "Michael" == Michael Matz writes: Michael> Well, that's a hack. A solution is to design something that Michael> works generally for garbage collected languages with such Michael> requirements instead of arbitrarily limiting transformations Michael> here and there. It could be something like the notion of Michael> derived pointers, where the base pointer needs to stay alive as Michael> long as the derived pointers are. This was done once in GCC, for the Modula 3 compiler. There was a paper about it, but I can't find it any more. The basic idea was to emit a description of the stack frame that their GC could read. They had a moving GC that could use this information to rewrite the frame when moving objects. Tom
Re: ivopts vs. garbage collection
On January 11, 2016 8:35:25 PM GMT+01:00, Michael Matz wrote: >Hi, > >On Mon, 11 Jan 2016, Ian Lance Taylor wrote: > >> > Well, that's a hack. A solution is to design something that works >> > generally for garbage collected languages with such requirements >> > instead of arbitrarily limiting transformations here and there. It > >> > could be something like the notion of derived pointers, where the >base >> > pointer needs to stay alive as long as the derived pointers are. >All >> > potential GC points where a derived pointer is alive also needs to >> > have the base pointer be alive (they could explicitely add uses of >the >> > base pointers, or alternatively anthing computing liveness needs to > >> > deal with this). For normal transformation that don't deal with >> > explicit liveness sets (i.e. most of our SSA transforms) it's >enough >> > if the instruction creating the derived pointer from the base can't >be >> > looked through, i.e. is an optimization barrier. >> >> What do you suggest we do for GCC 6? > >Realistically? The hack of course. > >> Your suggestion of every derived pointer keeping the base pointer >alive >> sounds too strong to me; it certainly sounds too strong for Go. For >Go >> it should be sufficient to ensure that every derived pointer points >> within the bounds of the object. > >Okay, that's a certain type of GC. Others might need exact offset-zero > >base pointers. > >> It's also not obvious to me that making a pointer transformation into >> an optimization barrier would be a win overall. > >It will almost always be a pessimization (the additional live value >needs >at least a place on the stack). > >> For something like >> ivopts it seems better to simply not introduce the pointer >> transformation--to apply ivopts only to non-pointers when GC matters > >Of course that deals only with ivopts. In practice that might be >enough, >even for a long time, but it's not really a full solution, there are >other >transformations on pointers (e.g. the vectorizer fiddling with >alignment), >some of them creating out of object pointers (e.g. chopping off the >lowest >few bits). > >Another problem is to define "when GC matters". With LTO you can't >rely >on anything from the frontend, so it needs to be encoded in the IL, or >at >the very least in a per-function item, with corresponding avoidance of >inlining of GC into non-GC aware functions. Here you can extend the hack to apply said flag to the final link if it is in at least one LTO object. As we do for some already. And yes, avoiding IVOPTs on pointer values is certainly the easiest fix. Richard. >> (I'm still puzzled by the fact that Java has apparently not >encountered >> this problem in all these years.) > >Probably it just so happened that the base pointer for some derived >pointer was lying around in some memory location. It's not very likely > >that the only reference is in a register, it can happen only shortly >after >allocating the new block, but before it's actually stored into some >other >structure (or freed, i.e. when it's only temporary, but then the base >pointer would be live as well), perhaps this pattern doesn't happen >very >often in java code. Obviously it does in Go. Perhaps we can limit the > >ivopts hack also to pointers that are problematic. Only if the base >pointer comes from a new allocation (is not loaded from memory) and >isn't >stored into memory before use do we need to avoid manipulating it too >much. > > >Ciao, >Michael.
Re: ivopts vs. garbage collection
Hi, On Mon, 11 Jan 2016, Ian Lance Taylor wrote: > > Well, that's a hack. A solution is to design something that works > > generally for garbage collected languages with such requirements > > instead of arbitrarily limiting transformations here and there. It > > could be something like the notion of derived pointers, where the base > > pointer needs to stay alive as long as the derived pointers are. All > > potential GC points where a derived pointer is alive also needs to > > have the base pointer be alive (they could explicitely add uses of the > > base pointers, or alternatively anthing computing liveness needs to > > deal with this). For normal transformation that don't deal with > > explicit liveness sets (i.e. most of our SSA transforms) it's enough > > if the instruction creating the derived pointer from the base can't be > > looked through, i.e. is an optimization barrier. > > What do you suggest we do for GCC 6? Realistically? The hack of course. > Your suggestion of every derived pointer keeping the base pointer alive > sounds too strong to me; it certainly sounds too strong for Go. For Go > it should be sufficient to ensure that every derived pointer points > within the bounds of the object. Okay, that's a certain type of GC. Others might need exact offset-zero base pointers. > It's also not obvious to me that making a pointer transformation into > an optimization barrier would be a win overall. It will almost always be a pessimization (the additional live value needs at least a place on the stack). > For something like > ivopts it seems better to simply not introduce the pointer > transformation--to apply ivopts only to non-pointers when GC matters Of course that deals only with ivopts. In practice that might be enough, even for a long time, but it's not really a full solution, there are other transformations on pointers (e.g. the vectorizer fiddling with alignment), some of them creating out of object pointers (e.g. chopping off the lowest few bits). Another problem is to define "when GC matters". With LTO you can't rely on anything from the frontend, so it needs to be encoded in the IL, or at the very least in a per-function item, with corresponding avoidance of inlining of GC into non-GC aware functions. > (I'm still puzzled by the fact that Java has apparently not encountered > this problem in all these years.) Probably it just so happened that the base pointer for some derived pointer was lying around in some memory location. It's not very likely that the only reference is in a register, it can happen only shortly after allocating the new block, but before it's actually stored into some other structure (or freed, i.e. when it's only temporary, but then the base pointer would be live as well), perhaps this pattern doesn't happen very often in java code. Obviously it does in Go. Perhaps we can limit the ivopts hack also to pointers that are problematic. Only if the base pointer comes from a new allocation (is not loaded from memory) and isn't stored into memory before use do we need to avoid manipulating it too much. Ciao, Michael.
Re: ivopts vs. garbage collection
On Mon, Jan 11, 2016 at 10:00 AM, Michael Matz wrote: > > On Fri, 8 Jan 2016, Richard Biener wrote: > >> > The only solution here is for ivopts to keep a pointer to the array, >> > not a pointer to some location near, but outside of the array. >> >> Yes, the solution is to make IVOPTs not do this (eventually controlled >> by a parameter because clearly it thinks doing this is beneficial >> cost-wise). > > Well, that's a hack. A solution is to design something that works > generally for garbage collected languages with such requirements instead > of arbitrarily limiting transformations here and there. It could be > something like the notion of derived pointers, where the base pointer > needs to stay alive as long as the derived pointers are. All potential GC > points where a derived pointer is alive also needs to have the base > pointer be alive (they could explicitely add uses of the base pointers, or > alternatively anthing computing liveness needs to deal with this). For > normal transformation that don't deal with explicit liveness sets (i.e. > most of our SSA transforms) it's enough if the instruction creating the > derived pointer from the base can't be looked through, i.e. is an > optimization barrier. What do you suggest we do for GCC 6? Your suggestion of every derived pointer keeping the base pointer alive sounds too strong to me; it certainly sounds too strong for Go. For Go it should be sufficient to ensure that every derived pointer points within the bounds of the object. Only when a derived pointer points outside of the object (including just after the end of the object) is it necessary to explicitly keep a base pointer alive. It's also not obvious to me that making a pointer transformation into an optimization barrier would be a win overall. For something like ivopts it seems better to simply not introduce the pointer transformation--to apply ivopts only to non-pointers when GC matters (GC matters not only for Go and Java, but also for any C/C++ program using something like the Boehm collector). (I'm still puzzled by the fact that Java has apparently not encountered this problem in all these years.) Ian
Re: ivopts vs. garbage collection
Hi, On Fri, 8 Jan 2016, Richard Biener wrote: > > The only solution here is for ivopts to keep a pointer to the array, > > not a pointer to some location near, but outside of the array. > > Yes, the solution is to make IVOPTs not do this (eventually controlled > by a parameter because clearly it thinks doing this is beneficial > cost-wise). Well, that's a hack. A solution is to design something that works generally for garbage collected languages with such requirements instead of arbitrarily limiting transformations here and there. It could be something like the notion of derived pointers, where the base pointer needs to stay alive as long as the derived pointers are. All potential GC points where a derived pointer is alive also needs to have the base pointer be alive (they could explicitely add uses of the base pointers, or alternatively anthing computing liveness needs to deal with this). For normal transformation that don't deal with explicit liveness sets (i.e. most of our SSA transforms) it's enough if the instruction creating the derived pointer from the base can't be looked through, i.e. is an optimization barrier. Ciao, Michael.
Re: ivopts vs. garbage collection
On Wed, Jan 6, 2016 at 4:26 PM, Jeff Law wrote: > On 01/06/2016 08:17 AM, Ian Lance Taylor wrote: >> >> The bug report https://golang.org/issue/13662 describes a case in >> which ivopts appears to be breaking garbage collection for the Go >> compiler. There is an array allocated in memory, and there is a loop >> over that array. The ivopts optimization is taking the only pointer >> to the array and subtracting 8 from it before entering the loop. >> There are function calls in between this subtraction and the actual >> use of the array. During those function calls, a garbage collection >> occurs. Since the only pointer to the array no longer points to the >> actual memory being used, the array is unexpectedly freed. >> >> That all seems clear enough, although I'm not sure how best to fix it. >> What I'm wondering in particular is whether Java does anything to >> avoid this kind of problem. I don't see anything obvious. Thanks for >> any pointers. > > The only solution here is for ivopts to keep a pointer to the array, not a > pointer to some location near, but outside of the array. Yes, the solution is to make IVOPTs not do this (eventually controlled by a parameter because clearly it thinks doing this is beneficial cost-wise). Note that a similar issue may occur with a pointer one after the last element (which is valid in C). Not sure if your GC handles this case well. Richard. > Java doesn't do anything special to the best of my knowledge, it just relies > on the fact that this kind of situation is very rare. > > This is related, but not the same as the issue we have with Ada's virtual > origins for array accesses where the front-end would set up a similar > situation, which resulted in a "pointer" that points outside the object. > When we actually dereference the pointer, it's done so with a base+index > access which brings the effective address back into the object. That kind > of scheme wrecks havoc with segmented targets where the segment selection > may be from the base register rather than the full effective address. > > jeff >
Re: ivopts vs. garbage collection
On 01/06/2016 08:17 AM, Ian Lance Taylor wrote: The bug report https://golang.org/issue/13662 describes a case in which ivopts appears to be breaking garbage collection for the Go compiler. There is an array allocated in memory, and there is a loop over that array. The ivopts optimization is taking the only pointer to the array and subtracting 8 from it before entering the loop. There are function calls in between this subtraction and the actual use of the array. During those function calls, a garbage collection occurs. Since the only pointer to the array no longer points to the actual memory being used, the array is unexpectedly freed. That all seems clear enough, although I'm not sure how best to fix it. What I'm wondering in particular is whether Java does anything to avoid this kind of problem. I don't see anything obvious. Thanks for any pointers. The only solution here is for ivopts to keep a pointer to the array, not a pointer to some location near, but outside of the array. Java doesn't do anything special to the best of my knowledge, it just relies on the fact that this kind of situation is very rare. This is related, but not the same as the issue we have with Ada's virtual origins for array accesses where the front-end would set up a similar situation, which resulted in a "pointer" that points outside the object. When we actually dereference the pointer, it's done so with a base+index access which brings the effective address back into the object. That kind of scheme wrecks havoc with segmented targets where the segment selection may be from the base register rather than the full effective address. jeff
ivopts vs. garbage collection
The bug report https://golang.org/issue/13662 describes a case in which ivopts appears to be breaking garbage collection for the Go compiler. There is an array allocated in memory, and there is a loop over that array. The ivopts optimization is taking the only pointer to the array and subtracting 8 from it before entering the loop. There are function calls in between this subtraction and the actual use of the array. During those function calls, a garbage collection occurs. Since the only pointer to the array no longer points to the actual memory being used, the array is unexpectedly freed. That all seems clear enough, although I'm not sure how best to fix it. What I'm wondering in particular is whether Java does anything to avoid this kind of problem. I don't see anything obvious. Thanks for any pointers. Ian
