Re: Preserve pointer types in ivopts
On 03/16/2012 09:49 PM, Richard Henderson wrote: > On 03/16/12 05:36, Bernd Schmidt wrote: >> The machine is "special". Pointer addition is a different operation than >> integer addition. It'll also need a new ptr_plus rtx code which takes a >> Pmode and an SImode operand. Pmode is larger than SImode but fits in a >> single register; intptr_t (which is what we'd need to use if we freely >> cast between pointers and integers is DImode - that requires two regs >> and can't be used for memory addressing. > > Surely the least amount of work is to not use sizetype/intptr_t, but a > custom type that has the same bit-width as a pointer? See some of the later mails in this thread for more details - the pointer add instruction isn't commutative. There is no true Pmode add, only a Pmode lea; in fact there is no normal arithmetic in Pmode at all. So you can't afford to lose information about which operand is the pointer. Making Pmode integer types would mean lying to the compiler very heavily about what operations are available, and it becomes way too hackish very quickly. Bernd
Re: Preserve pointer types in ivopts
On 03/16/12 05:36, Bernd Schmidt wrote: > The machine is "special". Pointer addition is a different operation than > integer addition. It'll also need a new ptr_plus rtx code which takes a > Pmode and an SImode operand. Pmode is larger than SImode but fits in a > single register; intptr_t (which is what we'd need to use if we freely > cast between pointers and integers is DImode - that requires two regs > and can't be used for memory addressing. Surely the least amount of work is to not use sizetype/intptr_t, but a custom type that has the same bit-width as a pointer? r~
Re: Preserve pointer types in ivopts
On Fri, Mar 16, 2012 at 4:49 PM, Zdenek Dvorak wrote:
> Hello,
>
>> On 03/16/2012 02:46 PM, Richard Guenther wrote:
>> > In the end what we want is a POINTER_PLUS_EXPR variant
>> > that does not make alias-analysis assume the result still points
>> > to within the objects the pointer pointed to before the
>> > increment/decrement.
>>
>> Hold on, is alias analysis really affected by this? Sure, we create
>> temporary pointers that point outside their base object, but we don't
>> dereference them. Anything value that ends up in a MEM_REF can only
>> point into that object again.
>
> it can be affected; by standard pointer arithmetics rules, you cannot
> create a pointer that would be outside of an object (unless you convert
> it from an integer). Thus, alias analysis may deduce that if we have
> something like
>
> int a[100];
> int *p = a + 10;
> int *q = p - i;
> *(q + 5) = 1;
> a[1] = 2;
>
> then q points inside a, and consequently q + 5 >= a + 5, hence the
> assignments do not alias. Ivopts may however produce this (in an equivalent
> form with casts to unsigned) even if i > 10.
See also the various invalid PRs that essentially do
foo (int *q)
{
int i;
int *p = &i;
long x = q - p;
*(p + x) = 1;
}
thus, cleverly encode address-space differences relative to an unrelated
object (seen in Boost, for cross-shmem pointers for example). C obviously
does not allow the "q - p" operation, and points-to analysis thinks that
p + x points to i and thus we remove the unused store to the local variable.
Another alias assumption is in offset-based analysis which assumes you
cannot have a pointer to before the object, so *(T *)(p + 1) may not
alias a global of type 'T' (because by seeing p + 1 and the access of type
T we conclude that the object pointed to is at least of size sizeof (T) + 1).
Richard.
> Zdenek
Re: Preserve pointer types in ivopts
Hello, > On 03/16/2012 02:46 PM, Richard Guenther wrote: > > In the end what we want is a POINTER_PLUS_EXPR variant > > that does not make alias-analysis assume the result still points > > to within the objects the pointer pointed to before the increment/decrement. > > Hold on, is alias analysis really affected by this? Sure, we create > temporary pointers that point outside their base object, but we don't > dereference them. Anything value that ends up in a MEM_REF can only > point into that object again. it can be affected; by standard pointer arithmetics rules, you cannot create a pointer that would be outside of an object (unless you convert it from an integer). Thus, alias analysis may deduce that if we have something like int a[100]; int *p = a + 10; int *q = p - i; *(q + 5) = 1; a[1] = 2; then q points inside a, and consequently q + 5 >= a + 5, hence the assignments do not alias. Ivopts may however produce this (in an equivalent form with casts to unsigned) even if i > 10. Zdenek
Re: Preserve pointer types in ivopts
On 03/16/2012 02:46 PM, Richard Guenther wrote: > In the end what we want is a POINTER_PLUS_EXPR variant > that does not make alias-analysis assume the result still points > to within the objects the pointer pointed to before the increment/decrement. Hold on, is alias analysis really affected by this? Sure, we create temporary pointers that point outside their base object, but we don't dereference them. Anything value that ends up in a MEM_REF can only point into that object again. I would have thought that it's mainly in fold-const where a POINTER_PLUSV would be handled differently from POINTER_PLUS (e.g. in pointer comparisons). Bernd
Re: Preserve pointer types in ivopts
On 03/16/2012 02:46 PM, Richard Guenther wrote: > We do have three pointer offsetting operations at the moment, > POINTER_PLUS_EXPR, &MEM_REF and &TARGET_MEM_REF. > All of which expect C pointer semantics (if they can see the base > pointer, which is why I suggested to create a TARGET_MEM_REF > with a NULL pointer TMR_BASE and shove the base pointer to > TMR_INDEX2 (which incidentially needs to be an integer type ...). Oh; looks like misunderstood your suggestion about TARGET_MEM_REF. Maybe I'll just have to bite the bullet and make a new tree code. > Btw, how do you handle pointer differences? The frontend already > lowers them to (intptr_t)ptr1 - (intptr_t)ptr2. More new stuff: targetm.pointer_mode_real_precision. Also, modifications in tree-ssa-loop-niter to use the new baseptr capability in tree-affine and subtract just the offsets in sizetype if possible. Bernd
Re: Preserve pointer types in ivopts
On Fri, Mar 16, 2012 at 2:37 PM, Bernd Schmidt wrote: > On 03/16/2012 02:33 PM, Zdenek Dvorak wrote: > Yes, that could work. ?Though it might end up being incredibly ugly ;) In the code? Should really only change a few lines in the patch I would have thought. I'll get back to you when I have a new version - thanks for the tip. >>> >>> No, in the GIMPLE IL. >>> >>> Richard. >> >> And I can just imagine how happy would other optimizations be about such a >> change. >> Are we speaking about something that you would like to get into mainline? >> All of this looks like a lot of hacks to deal with a rather weird target. > > The final piece - using &TARGET_MEM_REF rather than POINTER_PLUS_EXPR to > avoid overflow issues - is clearly a bit of a hack. But otherwise, > keeping around the proper types rather than casting everything to > unsigned int is IMO much less ugly and hackish than what we have now. > Certainly the gimple IL is much less cluttered after the patch than before. Btw, at one point I thought we might use Pmode integer types as base "pointer" types for [TARGET_]MEM_REF. But of course your target shows that this might not be a good idea. We do have three pointer offsetting operations at the moment, POINTER_PLUS_EXPR, &MEM_REF and &TARGET_MEM_REF. All of which expect C pointer semantics (if they can see the base pointer, which is why I suggested to create a TARGET_MEM_REF with a NULL pointer TMR_BASE and shove the base pointer to TMR_INDEX2 (which incidentially needs to be an integer type ...). In the end what we want is a POINTER_PLUS_EXPR variant that does not make alias-analysis assume the result still points to within the objects the pointer pointed to before the increment/decrement. Btw, how do you handle pointer differences? The frontend already lowers them to (intptr_t)ptr1 - (intptr_t)ptr2. Richard. > Bernd
Re: Preserve pointer types in ivopts
On 03/16/2012 02:33 PM, Zdenek Dvorak wrote: Yes, that could work. ?Though it might end up being incredibly ugly ;) >>> >>> In the code? Should really only change a few lines in the patch I would >>> have thought. I'll get back to you when I have a new version - thanks >>> for the tip. >> >> No, in the GIMPLE IL. >> >> Richard. > > And I can just imagine how happy would other optimizations be about such a > change. > Are we speaking about something that you would like to get into mainline? > All of this looks like a lot of hacks to deal with a rather weird target. The final piece - using &TARGET_MEM_REF rather than POINTER_PLUS_EXPR to avoid overflow issues - is clearly a bit of a hack. But otherwise, keeping around the proper types rather than casting everything to unsigned int is IMO much less ugly and hackish than what we have now. Certainly the gimple IL is much less cluttered after the patch than before. Bernd
Re: Preserve pointer types in ivopts
> >> Yes, that could work. ?Though it might end up being incredibly ugly ;) > > > > In the code? Should really only change a few lines in the patch I would > > have thought. I'll get back to you when I have a new version - thanks > > for the tip. > > No, in the GIMPLE IL. > > Richard. And I can just imagine how happy would other optimizations be about such a change. Are we speaking about something that you would like to get into mainline? All of this looks like a lot of hacks to deal with a rather weird target. Zdenek
Re: Preserve pointer types in ivopts
On Fri, Mar 16, 2012 at 2:18 PM, Bernd Schmidt wrote: > On 03/16/2012 02:15 PM, Richard Guenther wrote: >> Hmm, ok. So to have your lea represented on RTL you cannot use >> a fancy pattern using add because it would not be an add. Hmm. >> If it merely does not affect upper bits then >> >> (set (reg:SI ptr) (add (reg:SI ptr) (reg:SI off)) >> >> might work (if Pmode aka DImode is word_mode of course - otherwise >> the upper bits would be lost ...). > > It's not. > > Really, this isn't a problem right now. I already have a patch which > makes a ptr_plus RTX code and handles it everywhere. Fair enough. >> Maybe simply dispatching through a two-mode optab for expanding >> POINTER_PLUS_EXPRs would suit you? > > padd_optab, yes. > >> Yes, that could work. Though it might end up being incredibly ugly ;) > > In the code? Should really only change a few lines in the patch I would > have thought. I'll get back to you when I have a new version - thanks > for the tip. No, in the GIMPLE IL. Richard. > > Bernd
Re: Preserve pointer types in ivopts
On 03/16/2012 02:15 PM, Richard Guenther wrote: > Hmm, ok. So to have your lea represented on RTL you cannot use > a fancy pattern using add because it would not be an add. Hmm. > If it merely does not affect upper bits then > > (set (reg:SI ptr) (add (reg:SI ptr) (reg:SI off)) > > might work (if Pmode aka DImode is word_mode of course - otherwise > the upper bits would be lost ...). It's not. Really, this isn't a problem right now. I already have a patch which makes a ptr_plus RTX code and handles it everywhere. > Maybe simply dispatching through a two-mode optab for expanding > POINTER_PLUS_EXPRs would suit you? padd_optab, yes. > Yes, that could work. Though it might end up being incredibly ugly ;) In the code? Should really only change a few lines in the patch I would have thought. I'll get back to you when I have a new version - thanks for the tip. Bernd
Re: Preserve pointer types in ivopts
On Fri, Mar 16, 2012 at 2:05 PM, Bernd Schmidt wrote: > On 03/16/2012 01:55 PM, Richard Guenther wrote: >> On Fri, Mar 16, 2012 at 1:36 PM, Bernd Schmidt >> wrote: >>> >>> The machine is "special". Pointer addition is a different operation than >>> integer addition. It'll also need a new ptr_plus rtx code which takes a >>> Pmode and an SImode operand. Pmode is larger than SImode but fits in a >>> single register; intptr_t (which is what we'd need to use if we freely >>> cast between pointers and integers is DImode - that requires two regs >>> and can't be used for memory addressing. >> >> Hm, I see. On RTL would you get away with using REG_POINTER and >> paradoxical subregs for the offset operand? Sth like (add (reg:DI >> ptr) (subreg:DI (reg:SI off)))? > > No, because (reg:DI ptr) is the wrong representation. Pointers only take > a single reg, and besides such subreg games would be extremely nasty. > There's also the problem that this really isn't an arithmetic plus, > since the top bits of the pointer are unaffected. Hence it doesn't > commute: lea is a different operation than add. There is no other > arithmetic that operates on Pmode, so it is impossible to use that mode > for integer types. Well, not impossible - I have existence proof in the > form of the port I inherited - but you have to lie pretty heavily to the > compiler to even just make it limp along. Hmm, ok. So to have your lea represented on RTL you cannot use a fancy pattern using add because it would not be an add. Hmm. If it merely does not affect upper bits then (set (reg:SI ptr) (add (reg:SI ptr) (reg:SI off)) might work (if Pmode aka DImode is word_mode of course - otherwise the upper bits would be lost ...). Or of course an UNSPEC generated during address legitimization. Do we even have sth like address legitimization for pointer arithmetic? I suppose we should, when expanding POINTER_PLUS_EXPRs. Maybe simply dispatching through a two-mode optab for expanding POINTER_PLUS_EXPRs would suit you? >> Basically your issue on trees is that pointer information is lost and (wide) >> integer operations appear? > > That's the main issue, yes. > >> Note that IVOPTs at the moment does not try to generate lea-style >> pointer arithmetic while it could use &TARGET_MEM_REF for this. >> We still assume that those addresses are within the object of >> operand zero (but if you use a literal zero as that operand and put >> the base somewhere else you might use that as a vehicle for >> telling GCC the arithmetic is not within C language scope). > > Oh, ok. So IIUC maybe I can simply adjust the patch to still create > POINTER_PLUS_EXPR in memory addresses, but use &TARGET_MEM_REF for the > arithmetic in initializing the ivs? Yes, that could work. Though it might end up being incredibly ugly ;) Richard. > > Bernd
Re: Preserve pointer types in ivopts
On 03/16/2012 01:55 PM, Richard Guenther wrote: > On Fri, Mar 16, 2012 at 1:36 PM, Bernd Schmidt > wrote: >> >> The machine is "special". Pointer addition is a different operation than >> integer addition. It'll also need a new ptr_plus rtx code which takes a >> Pmode and an SImode operand. Pmode is larger than SImode but fits in a >> single register; intptr_t (which is what we'd need to use if we freely >> cast between pointers and integers is DImode - that requires two regs >> and can't be used for memory addressing. > > Hm, I see. On RTL would you get away with using REG_POINTER and > paradoxical subregs for the offset operand? Sth like (add (reg:DI > ptr) (subreg:DI (reg:SI off)))? No, because (reg:DI ptr) is the wrong representation. Pointers only take a single reg, and besides such subreg games would be extremely nasty. There's also the problem that this really isn't an arithmetic plus, since the top bits of the pointer are unaffected. Hence it doesn't commute: lea is a different operation than add. There is no other arithmetic that operates on Pmode, so it is impossible to use that mode for integer types. Well, not impossible - I have existence proof in the form of the port I inherited - but you have to lie pretty heavily to the compiler to even just make it limp along. > Basically your issue on trees is that pointer information is lost and (wide) > integer operations appear? That's the main issue, yes. > Note that IVOPTs at the moment does not try to generate lea-style > pointer arithmetic while it could use &TARGET_MEM_REF for this. > We still assume that those addresses are within the object of > operand zero (but if you use a literal zero as that operand and put > the base somewhere else you might use that as a vehicle for > telling GCC the arithmetic is not within C language scope). Oh, ok. So IIUC maybe I can simply adjust the patch to still create POINTER_PLUS_EXPR in memory addresses, but use &TARGET_MEM_REF for the arithmetic in initializing the ivs? Bernd
Re: Preserve pointer types in ivopts
On Fri, Mar 16, 2012 at 1:36 PM, Bernd Schmidt wrote: > On 03/16/2012 11:08 AM, Richard Guenther wrote: >> >> Your patch as-is is not safe at the moment. But why is casting a pointer >> to an integer prohibitly expensive? That fact should be an implementation >> detail of GIMPLE. Or is it the issue that IVOPTs chooses an integer >> type that does not necessarily match the mode we'll use on RTL? >> (thus, ptr_mode vs. Pmode issues, and/or sizeof (sizetype) != sizeof (void *) >> issues?) > > The machine is "special". Pointer addition is a different operation than > integer addition. It'll also need a new ptr_plus rtx code which takes a > Pmode and an SImode operand. Pmode is larger than SImode but fits in a > single register; intptr_t (which is what we'd need to use if we freely > cast between pointers and integers is DImode - that requires two regs > and can't be used for memory addressing. Hm, I see. On RTL would you get away with using REG_POINTER and paradoxical subregs for the offset operand? Sth like (add (reg:DI ptr) (subreg:DI (reg:SI off)))? Or even use a plain sign/zero_extend which is what expansion would generate at the moment I think. I suppose the HW either sign- or zero-extends that offset operand anyway. Basically your issue on trees is that pointer information is lost and (wide) integer operations appear? Note that IVOPTs at the moment does not try to generate lea-style pointer arithmetic while it could use &TARGET_MEM_REF for this. We still assume that those addresses are within the object of operand zero (but if you use a literal zero as that operand and put the base somewhere else you might use that as a vehicle for telling GCC the arithmetic is not within C language scope). Richard.
Re: Preserve pointer types in ivopts
On 03/16/2012 11:08 AM, Richard Guenther wrote: > > Your patch as-is is not safe at the moment. But why is casting a pointer > to an integer prohibitly expensive? That fact should be an implementation > detail of GIMPLE. Or is it the issue that IVOPTs chooses an integer > type that does not necessarily match the mode we'll use on RTL? > (thus, ptr_mode vs. Pmode issues, and/or sizeof (sizetype) != sizeof (void *) > issues?) The machine is "special". Pointer addition is a different operation than integer addition. It'll also need a new ptr_plus rtx code which takes a Pmode and an SImode operand. Pmode is larger than SImode but fits in a single register; intptr_t (which is what we'd need to use if we freely cast between pointers and integers is DImode - that requires two regs and can't be used for memory addressing. Bernd
Re: Preserve pointer types in ivopts
On Fri, Mar 16, 2012 at 1:13 AM, Andrew Pinski wrote: > On Thu, Mar 15, 2012 at 5:09 PM, Bernd Schmidt > wrote: >> On 03/16/2012 12:44 AM, Jakub Jelinek wrote: >>> For pointer arithmetics in the IL we assume the C >>> requirements, pointer arithmetics can be performed only within the same >>> object, so for >>> int a[10]; >>> both of the following are invalid, even in the IL: >>> int *p = a - 1; >>> int *q = a + 11; >> >> Ok, so what's the solution? Add a second POINTER_PLUS_EXPR code with >> defined overflow behaviour, or add a flag to it? > > We should have one for PLUS_EXPR also. There was some movement on > that on a branch that Richard Guenther did but I don't know if he is > going to work on it further. I have been noticing more and more the > need for this feature while working on my tree combiner branch, that I > might try to see if Richard's branch can be revisited. The branch was a too big task at one time, so presently I'm trying to get rid of the speciality of "sizetypes" first and then plan to revisit the branch. To recap - on the branch we have an explicit notion on whether a operation can overflow or not (where "not overflowing" is equivalent to "undefined behavior if overflow happens"). Operations are marked either way by choosing different tree codes. See http://gcc.gnu.org/wiki/NoUndefinedOverflow Unfortunately updating the branch stopped before tuplification (heh ...). So I guess it will need to be re-done from start. And yes, it's a massive effort. But in theory you can do the massaging incrementally - so, in your case add only POINTER_PLUSNV_EXPR and make sure to drop that to POINTER_PLUS_EXPR whenever you are no longer sure that the operation follows the C language constraints of pointer arithmetic (and change all folders that assume that semantic to work only on POINTER_PLUSNV_EXPRs). Or do it the other way around (which of course will be less conservatively correct - something I'm no longer 100% sure about). Your patch as-is is not safe at the moment. But why is casting a pointer to an integer prohibitly expensive? That fact should be an implementation detail of GIMPLE. Or is it the issue that IVOPTs chooses an integer type that does not necessarily match the mode we'll use on RTL? (thus, ptr_mode vs. Pmode issues, and/or sizeof (sizetype) != sizeof (void *) issues?) Richard.
Re: Preserve pointer types in ivopts
On Thu, Mar 15, 2012 at 5:09 PM, Bernd Schmidt wrote: > On 03/16/2012 12:44 AM, Jakub Jelinek wrote: >> For pointer arithmetics in the IL we assume the C >> requirements, pointer arithmetics can be performed only within the same >> object, so for >> int a[10]; >> both of the following are invalid, even in the IL: >> int *p = a - 1; >> int *q = a + 11; > > Ok, so what's the solution? Add a second POINTER_PLUS_EXPR code with > defined overflow behaviour, or add a flag to it? We should have one for PLUS_EXPR also. There was some movement on that on a branch that Richard Guenther did but I don't know if he is going to work on it further. I have been noticing more and more the need for this feature while working on my tree combiner branch, that I might try to see if Richard's branch can be revisited. Thanks, Andrew Pinski
Re: Preserve pointer types in ivopts
On 03/16/2012 12:44 AM, Jakub Jelinek wrote: > For pointer arithmetics in the IL we assume the C > requirements, pointer arithmetics can be performed only within the same > object, so for > int a[10]; > both of the following are invalid, even in the IL: > int *p = a - 1; > int *q = a + 11; Ok, so what's the solution? Add a second POINTER_PLUS_EXPR code with defined overflow behaviour, or add a flag to it? Bernd
Re: Preserve pointer types in ivopts
Hi,
> > Well, what are our rules for whether overflow on POINTER_PLUS_EXPR is
> > defined or not? A quick search through the headers and docs doesn't turn
> > up anything. Would there be a downside to defining it as wrapping?
> >
> > Can you show an example where a POINTER_PLUS_EXPR produced by ivopts
> > would overflow?
>
> Don't have a testcase right now, I've just seen IVOPTS many times in the
> past initialize an IV with start of array minus some constant, end of array
> plus some constant or similar (which is fine if the IV is unsigned integer
> of the size of a pointer, but certainly wouldn't be fine if the IV had
> pointer type). For pointer arithmetics in the IL we assume the C
> requirements, pointer arithmetics can be performed only within the same
> object, so for
> int a[10];
> both of the following are invalid, even in the IL:
> int *p = a - 1;
> int *q = a + 11;
for example, something like this:
int a[1000];
void foo(int n)
{
int i, *p = a;
for (i = 8; i < n; i++)
*p++ = 10;
}
ivopts may decide to change this to:
int a[1000];
void foo(int n)
{
int i, *p = a - 8;
for (i = 8; i < n; i++)
p[i] = 10;
}
which may require one less adition, depending on the available addressing modes.
Of course, as written above this has undefined behavior; hence, the casts to
unsigned integer,
Zdenek
Re: Preserve pointer types in ivopts
On Fri, Mar 16, 2012 at 12:20:44AM +0100, Bernd Schmidt wrote: > On 03/16/2012 12:16 AM, Jakub Jelinek wrote: > > On Fri, Mar 16, 2012 at 12:03:08AM +0100, Bernd Schmidt wrote: > >> On 03/15/2012 11:12 PM, Zdenek Dvorak wrote: > >> > >>> the reason unsigned integer types are prefered is that possible overflows > >>> during the computation have defined semantics. With pointer types, the > >>> intermediate steps of the computations could have undefined behavior, > >>> possibly > >>> confusing further optimizations. Is the patch with this regard? > >> > >> It's trying to use sizetype for pointer offset computations. As far as I > >> can tell that's supposed to be an unsigned type, so it should be OK. I > >> think the final POINTER_PLUS_EXPRs we make can't overflow in valid > >> programs. > > > > In the IL before ivopts it shouldn't for valid programs, but what ivopts > > makes out of it often would, that is why it uses unsigned integers instead. > > Well, what are our rules for whether overflow on POINTER_PLUS_EXPR is > defined or not? A quick search through the headers and docs doesn't turn > up anything. Would there be a downside to defining it as wrapping? > > Can you show an example where a POINTER_PLUS_EXPR produced by ivopts > would overflow? Don't have a testcase right now, I've just seen IVOPTS many times in the past initialize an IV with start of array minus some constant, end of array plus some constant or similar (which is fine if the IV is unsigned integer of the size of a pointer, but certainly wouldn't be fine if the IV had pointer type). For pointer arithmetics in the IL we assume the C requirements, pointer arithmetics can be performed only within the same object, so for int a[10]; both of the following are invalid, even in the IL: int *p = a - 1; int *q = a + 11; Jakub
Re: Preserve pointer types in ivopts
On 03/16/2012 12:16 AM, Jakub Jelinek wrote: > On Fri, Mar 16, 2012 at 12:03:08AM +0100, Bernd Schmidt wrote: >> On 03/15/2012 11:12 PM, Zdenek Dvorak wrote: >> >>> the reason unsigned integer types are prefered is that possible overflows >>> during the computation have defined semantics. With pointer types, the >>> intermediate steps of the computations could have undefined behavior, >>> possibly >>> confusing further optimizations. Is the patch with this regard? >> >> It's trying to use sizetype for pointer offset computations. As far as I >> can tell that's supposed to be an unsigned type, so it should be OK. I >> think the final POINTER_PLUS_EXPRs we make can't overflow in valid programs. > > In the IL before ivopts it shouldn't for valid programs, but what ivopts > makes out of it often would, that is why it uses unsigned integers instead. Well, what are our rules for whether overflow on POINTER_PLUS_EXPR is defined or not? A quick search through the headers and docs doesn't turn up anything. Would there be a downside to defining it as wrapping? Can you show an example where a POINTER_PLUS_EXPR produced by ivopts would overflow? Bernd
Re: Preserve pointer types in ivopts
On Fri, Mar 16, 2012 at 12:03:08AM +0100, Bernd Schmidt wrote: > On 03/15/2012 11:12 PM, Zdenek Dvorak wrote: > > > the reason unsigned integer types are prefered is that possible overflows > > during the computation have defined semantics. With pointer types, the > > intermediate steps of the computations could have undefined behavior, > > possibly > > confusing further optimizations. Is the patch with this regard? > > It's trying to use sizetype for pointer offset computations. As far as I > can tell that's supposed to be an unsigned type, so it should be OK. I > think the final POINTER_PLUS_EXPRs we make can't overflow in valid programs. In the IL before ivopts it shouldn't for valid programs, but what ivopts makes out of it often would, that is why it uses unsigned integers instead. Jakub
Re: Preserve pointer types in ivopts
On 03/15/2012 11:12 PM, Zdenek Dvorak wrote: > the reason unsigned integer types are prefered is that possible overflows > during the computation have defined semantics. With pointer types, the > intermediate steps of the computations could have undefined behavior, possibly > confusing further optimizations. Is the patch with this regard? It's trying to use sizetype for pointer offset computations. As far as I can tell that's supposed to be an unsigned type, so it should be OK. I think the final POINTER_PLUS_EXPRs we make can't overflow in valid programs. Bernd
Re: Preserve pointer types in ivopts
Hi, > Currently, tree-ssa-loop-ivopts assumes that pointers and integers can > be used interchangeably. It prefers to compute everything in unsigned > integer types rather than pointer types. > On a new target that I'm working on, this assumption is problematic; > casting a pointer to an integer and doing arithmetic on the integer > would be much too expensive to be useful. I came up with the patch > below, which makes ivopts try harder to preserve pointer types. > tree-affine is changed to keep track of base pointers, and do arithmetic > (in particular subtraction) properly if base pointers are involved. > > Bootstrapped and regression tested with all languages on i686-linux. I > get FAILs in: > > * gcc.dg/guality/pr43051-1.c > A somewhat contrived testcase; gdb now produces "optimized out" > messages which I think is acceptable? In any case I remain to be > convinced that this testcase demonstrates any real problem. > * gcc.dg/tree-ssa/reassoc-19.c scan-tree-dump-times reassoc2 " \+ " 0 > This seems to fail because we do POINTER_PLUS (ptr, NEG offset)) > rather than (char *)((int)ptr - offset). As far as I can tell this > is also not a real problem, but I don't know how to adjust the > testcase. > > Comments? Ok? the reason unsigned integer types are prefered is that possible overflows during the computation have defined semantics. With pointer types, the intermediate steps of the computations could have undefined behavior, possibly confusing further optimizations. Is the patch with this regard? Zdenek
Preserve pointer types in ivopts
Currently, tree-ssa-loop-ivopts assumes that pointers and integers can
be used interchangeably. It prefers to compute everything in unsigned
integer types rather than pointer types.
On a new target that I'm working on, this assumption is problematic;
casting a pointer to an integer and doing arithmetic on the integer
would be much too expensive to be useful. I came up with the patch
below, which makes ivopts try harder to preserve pointer types.
tree-affine is changed to keep track of base pointers, and do arithmetic
(in particular subtraction) properly if base pointers are involved.
Bootstrapped and regression tested with all languages on i686-linux. I
get FAILs in:
* gcc.dg/guality/pr43051-1.c
A somewhat contrived testcase; gdb now produces "optimized out"
messages which I think is acceptable? In any case I remain to be
convinced that this testcase demonstrates any real problem.
* gcc.dg/tree-ssa/reassoc-19.c scan-tree-dump-times reassoc2 " \+ " 0
This seems to fail because we do POINTER_PLUS (ptr, NEG offset))
rather than (char *)((int)ptr - offset). As far as I can tell this
is also not a real problem, but I don't know how to adjust the
testcase.
Comments? Ok?
Bernd
* tree-affine.c (aff_combination_zero): Initialize baseptr.
(aff_combination_add): Handle baseptrs. Abort if both are set.
(aff_combination_diff): New function.
(tree_to_aff_combination_1): Renamed from tree_to_aff_combination.
Remove code to handle pointers; changed to call itself recursively.
(tree_to_aff_combination): New function. Handle the pointer cases
formerly found in the function of the same name, and use
tree_to_aff_combination_1 to compute the offsets.
(aff_combination_to_tree): Build a POINTER_PLUS_EXPR around the
offset if the baseptr is nonnull.
* tree-affine.h (struct affine_tree_combination): New member baseptr.
(aff_combination_diff): Declare.
* tree-predcom.c (determine_offset, valid_initialier_p): Use
aff_combination_diff and return false if it fails.
* tree-ssa-loop-ivopts.c (determine_base_object): If an non-pointer
is cast to a pointer, return the cast.
(add_candidate_1): Use sizetype for steps of a pointer-type iv.
(add_old_iv_candidates): Only add a zero-base pointer candidate if
the precision of pointers and sizetype is equal.
(get_computation_aff): Don't convert steps to pointer types.
Ensure pointers are not scaled. Use aff_combination_diff for
subtraction.
(ptr_difference_cost, difference_cost): Use aff_combination_diff and
return infinite_cost if it fails.
(get_loop_invariant_expr_id): Likewise, returning -1 on failure.
(get_computation_cost_at): Fail if bad pointer expressions would be
generated.
(rewrite_use_nonlinear_expr): Use POINTER_PLUS_EXPR if necessary.
* tree-ssa-address.c (addr_to_parts): Look for a baseptr in the
aff_tree.
* tree-ssa-loop-im.c (mem_refs_may_alias_p): Use aff_combination_diff.
testsuite/
* gcc.dg/tree-ssa/loop-4.c: Scan only for real MEMs, not addresses of
them.
Index: gcc/tree-ssa-loop-im.c
===
--- gcc/tree-ssa-loop-im.c (revision 184938)
+++ gcc/tree-ssa-loop-im.c (working copy)
@@ -1772,8 +1772,8 @@ mem_refs_may_alias_p (tree mem1, tree me
get_inner_reference_aff (mem2, &off2, &size2);
aff_combination_expand (&off1, ttae_cache);
aff_combination_expand (&off2, ttae_cache);
- aff_combination_scale (&off1, double_int_minus_one);
- aff_combination_add (&off2, &off1);
+ if (!aff_combination_diff (&off2, &off1))
+return true;
if (aff_comb_cannot_overlap_p (&off2, size1, size2))
return false;
Index: gcc/testsuite/gcc.dg/tree-ssa/loop-4.c
===
--- gcc/testsuite/gcc.dg/tree-ssa/loop-4.c (revision 184938)
+++ gcc/testsuite/gcc.dg/tree-ssa/loop-4.c (working copy)
@@ -37,7 +37,7 @@ void xxx(void)
/* { dg-final { scan-tree-dump-times " \\* \[^\\n\\r\]*=" 0 "optimized" } } */
/* { dg-final { scan-tree-dump-times "\[^\\n\\r\]*= \\* " 0 "optimized" } } */
-/* { dg-final { scan-tree-dump-times "MEM" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\[^&\]MEM" 1 "optimized" } } */
/* And the original induction variable should be eliminated. */
Index: gcc/tree-ssa-loop-ivopts.c
===
--- gcc/tree-ssa-loop-ivopts.c (revision 184938)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -879,15 +879,21 @@ static tree
determine_base_object (tree expr)
{
enum tree_code code = TREE_CODE (expr);
+ tree type = TREE_TYPE (expr);
tree base, obj;
/* If this is a pointer casted to any type, we need to determine
the base object for the pointer; so handle conversi
