Re: Strenghten assumption about dynamic type changes (placement new)

Re: Strenghten assumption about dynamic type changes (placement new)

[Dominique Dhumieres]

> I'm fixing that with the following (will commit as obvious).

Marek,

With your patch g++.dg/ipa/imm-devirt-2.C sitll fails in 32 bit mode
because the mangling is C::_ZThn16_N1C3fooEi. This is fixed by something
such as 

--- ../_clean/gcc/testsuite/g++.dg/ipa/imm-devirt-2.C	2014-07-05 23:22:52.000000000 +0200
+++ gcc/testsuite/g++.dg/ipa/imm-devirt-2.C	2014-07-06 18:03:59.000000000 +0200
@@ -92,5 +92,5 @@ int main (int argc, char *argv[])
 }
 
 /* We fold into thunk of C. Eventually we should inline the thunk.  */
-/* { dg-final { scan-tree-dump "C::_ZThn24_N1C3fooEi (" "einline"  } } */
+/* { dg-final { scan-tree-dump "C::_ZThn\(16|24\)_N1C3fooEi \\(" "einline"  } } */
 /* { dg-final { cleanup-tree-dump "einline" } } */

Dominique

Re: Strenghten assumption about dynamic type changes (placement new)

[Jason Merrill]

On 07/23/2014 07:29 AM, Richard Biener wrote:
> On Wed, Jul 23, 2014 at 12:44 PM, Jason Merrill <jason@redhat.com> wrote:
>> On 07/22/2014 02:34 PM, Richard Biener wrote:
>>>
>>> As discussed during the Cauldron keeping some builtin doesn't help because
>>>
>>> you are not forced to access the newly created object via the pointer
>>> returned
>>> by the placement new.  That is,
>>>
>>>     template <T>
>>>    struct Storage {
>>>        char x[sizeof(T)];
>>>       Storage() { new (x) T; }
>>>       T& get() { return reinterpret_cast <T&> (x); }
>>> };
>>>
>>> is valid
>>
>> Yes.
>>
>>> (and used in this way in Boost - with a type different from 'char'
>>> to force bigger alignment).
>>
>> But I don't think that should be valid, unless the type contains a char
>> array at offset 0, as {std,boost}::aligned_storage; the C++ standard needs
>> improvement in this area.
>
> Why especially at offset 0?  I'm constructing in the place of 'x', not
> 'this'.

Right, and I'm talking about the type of 'x', not the type of *this.

> Do you say that
>
> template <class T>
> struct Storage {
>    T& get(i) { return new (x + sizeof (T) * i) T; }
>    Storage (int n_) n (n_) {}
>    int n;
>    char x[sizeof (T)];
> };
>
> and doing
>
>    Storage *s = new (malloc (sizeof (int)  * 4)) Storage (4);
>    s->get (2);
>
> isn't valid?

That's fine.

>> Looks like the small buffer optimization in boost::spirit::hold_any would
>> need to be tweaked, as it uses a void* to store anything the same size or
>> smaller, but that's the only dodgy case I see.
>
> I've seen other odd cases in GCC bugreports ultimately coming from
> Boost & friends (mpl or whatnot).  Very likely older Boost versions
> of course.
>
> Btw, any reason why the standard treats 'char' and 'unsigned char'
> special but not 'signed char'?

I think we'd prefer to only treat unsigned char specially, but plain 
char is also allowed for historical reasons.

> That said, as a matter of QOI I think only special-casing character
> types would be a bad thing (see your hold_any example).

Well, there's a tradeoff between expressiveness and optimization.  But 
perhaps you have a better sense of that than I.

Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On Thu, Jul 24, 2014 at 12:46 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>
>> Aggregate copies and memcpy transferring the dynamic type for example.  Being able to tbaa union accesses for another.  And yes, placement new.
>
> I see that if we previously dropped all union accesses to 0, the current scheme
> is nice improvement.  But it seem to me it may be in use only when one of
> accesses is through union.
>
> How the memcpy case works? I always tought that memcpy does reads&writes in set 0
> that makes it to introduce the necessary conflicts.

Yes, that's possible now (with MEM_REF), previously it was not
and the memory model "fixed" it.

> Similarly can't we make set 0 clobber of the memory retyped by placement new?

We don't have a way to do that, but yes, we could.  But as said, for PODs
you don't even need placement new.  You can just store with a new type.

Richard.

> If the clobber is hidden in external function call, we still have it as a side
> effect of the call. It would have to survive all the way down to RTL...
>
> Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> 
> Aggregate copies and memcpy transferring the dynamic type for example.  Being able to tbaa union accesses for another.  And yes, placement new.

I see that if we previously dropped all union accesses to 0, the current scheme
is nice improvement.  But it seem to me it may be in use only when one of
accesses is through union.

How the memcpy case works? I always tought that memcpy does reads&writes in set 0
that makes it to introduce the necessary conflicts.

Similarly can't we make set 0 clobber of the memory retyped by placement new?
If the clobber is hidden in external function call, we still have it as a side
effect of the call. It would have to survive all the way down to RTL...

Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On Thu, Jul 24, 2014 at 11:53 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Jul 24, 2014 at 11:23 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>> >  *shortptr = exp
>>> >  <longer dependency chain with shortptr>
>>> >  var = *shortptr
>>> >  *intptr = exp
>>> >  <longer dependency chain with intptr>
>>> >  var = *intptr
>>>
>>> Yes (that is, you can't hoist the *intptr = exp store above the var = *shortptr
>>> load with TBAA only).  You can probably still hoist the <longer dependency
>>> chain with intptr>, it's not clear from your example.
>>
>> Well, this is placement new version of this, where of course the movement is not desirable.
>> Obvioulsy the chains can not overlap:
>> #include <new>
>> #include <stdio.h>
>> struct A {short a; short b; A(){a=1;}};
>> struct B {int a; B(){a=2;}};
>>
>> struct A a;
>> struct A *pa = &a;
>> struct B *pb = reinterpret_cast<struct B *>(&a);
>> int
>> main()
>> {
>>   int sum;
>>   struct A *ppa = pa;
>>   struct B *ppb = pb;
>>   if (!pa || !pb)
>>     return 1;
>>   ppa->~A();
>>   new (ppa) A();
>>   asm ("#asm1":"=m"(ppa->a):"m"(ppa->a));
>>   sum = ppa->a*11;
>>   new (ppb) B();
>>
>>   asm ("#asm2":"=m"(ppb->a):"m"(ppb->a));
>>   sum += ppb->a*11;
>>   printf ("%i\n",sum);
>>   return 0;
>> }
>>
>> Of course it makes us i.e. in
>> t(short *a, short *b, int *c)
>> {
>>   int i;
>>   for (i=0;i<1000000;i++)
>>     c[i]=a[i]+b[i];
>> }
>>
>> generate the fallback case when vectorizing where c is overlapping with a or b, while clang doesn't.
>
> Yep.  I bet clang gets it wrong with placement new (but then for
> PODs simply writing to a storage location ends lifetime of the old
> object in there and starts lifetime of a new object, so placement new
> is not needed to make an overlap valid as far as I read the standard(s)).
>
> So I don't think omitting the runtime alias check is valid for the above
> case.

Btw, we don't create a runtime test here.  The argument is as simple
as overlap may only happen during iteration 0, otherwise you have
an invalid read via short of sth stored via int.

Thus if you are in loops you are usually fine to use TBAA.

Richard.

> Richard.
>
>> Honza
>>>
>>> That said, being able to optimize union accesses with TBAA at all
>>> is still nice (esp. for GCC).  Now, the C frontend still forces alias-set zero
>>> for this case because of the RTL alias oracle disfunctionality which doesn't
>>> treat a must-alias as an alias if it can TBAA disambiguate.
>>>
>>> Richard.
>>>
>>> > Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On Thu, Jul 24, 2014 at 11:23 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >  *shortptr = exp
>> >  <longer dependency chain with shortptr>
>> >  var = *shortptr
>> >  *intptr = exp
>> >  <longer dependency chain with intptr>
>> >  var = *intptr
>>
>> Yes (that is, you can't hoist the *intptr = exp store above the var = *shortptr
>> load with TBAA only).  You can probably still hoist the <longer dependency
>> chain with intptr>, it's not clear from your example.
>
> Well, this is placement new version of this, where of course the movement is not desirable.
> Obvioulsy the chains can not overlap:
> #include <new>
> #include <stdio.h>
> struct A {short a; short b; A(){a=1;}};
> struct B {int a; B(){a=2;}};
>
> struct A a;
> struct A *pa = &a;
> struct B *pb = reinterpret_cast<struct B *>(&a);
> int
> main()
> {
>   int sum;
>   struct A *ppa = pa;
>   struct B *ppb = pb;
>   if (!pa || !pb)
>     return 1;
>   ppa->~A();
>   new (ppa) A();
>   asm ("#asm1":"=m"(ppa->a):"m"(ppa->a));
>   sum = ppa->a*11;
>   new (ppb) B();
>
>   asm ("#asm2":"=m"(ppb->a):"m"(ppb->a));
>   sum += ppb->a*11;
>   printf ("%i\n",sum);
>   return 0;
> }
>
> Of course it makes us i.e. in
> t(short *a, short *b, int *c)
> {
>   int i;
>   for (i=0;i<1000000;i++)
>     c[i]=a[i]+b[i];
> }
>
> generate the fallback case when vectorizing where c is overlapping with a or b, while clang doesn't.

Yep.  I bet clang gets it wrong with placement new (but then for
PODs simply writing to a storage location ends lifetime of the old
object in there and starts lifetime of a new object, so placement new
is not needed to make an overlap valid as far as I read the standard(s)).

So I don't think omitting the runtime alias check is valid for the above
case.

Richard.

> Honza
>>
>> That said, being able to optimize union accesses with TBAA at all
>> is still nice (esp. for GCC).  Now, the C frontend still forces alias-set zero
>> for this case because of the RTL alias oracle disfunctionality which doesn't
>> treat a must-alias as an alias if it can TBAA disambiguate.
>>
>> Richard.
>>
>> > Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> >  *shortptr = exp
> >  <longer dependency chain with shortptr>
> >  var = *shortptr
> >  *intptr = exp
> >  <longer dependency chain with intptr>
> >  var = *intptr
> 
> Yes (that is, you can't hoist the *intptr = exp store above the var = *shortptr
> load with TBAA only).  You can probably still hoist the <longer dependency
> chain with intptr>, it's not clear from your example.

Well, this is placement new version of this, where of course the movement is not desirable.
Obvioulsy the chains can not overlap:
#include <new>
#include <stdio.h>
struct A {short a; short b; A(){a=1;}};
struct B {int a; B(){a=2;}};

struct A a;
struct A *pa = &a;
struct B *pb = reinterpret_cast<struct B *>(&a);
int
main()
{
  int sum;
  struct A *ppa = pa;
  struct B *ppb = pb;
  if (!pa || !pb)
    return 1;
  ppa->~A();
  new (ppa) A();
  asm ("#asm1":"=m"(ppa->a):"m"(ppa->a));
  sum = ppa->a*11;
  new (ppb) B();
  
  asm ("#asm2":"=m"(ppb->a):"m"(ppb->a));
  sum += ppb->a*11;
  printf ("%i\n",sum);
  return 0;
}

Of course it makes us i.e. in 
t(short *a, short *b, int *c)
{
  int i;
  for (i=0;i<1000000;i++)
    c[i]=a[i]+b[i];
}

generate the fallback case when vectorizing where c is overlapping with a or b, while clang doesn't.

Honza
> 
> That said, being able to optimize union accesses with TBAA at all
> is still nice (esp. for GCC).  Now, the C frontend still forces alias-set zero
> for this case because of the RTL alias oracle disfunctionality which doesn't
> treat a must-alias as an alias if it can TBAA disambiguate.
> 
> Richard.
> 
> > Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On Wed, Jul 23, 2014 at 6:29 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> On July 23, 2014 4:42:22 PM CEST, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >> On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >> >> I don't see why
>> >> >>
>> >> >> long x[1024];
>> >> >>
>> >> >> Q *q = new (x) Q;
>> >> >> q->~Q ();
>> >> >> new (x) T;
>> >> >>
>> >> >> would be invalid.  I also don't see why
>> >> >>
>> >> >> Q q;
>> >> >> q.~Q ();
>> >> >> new (&q) T;
>> >> >>
>> >> >> would be.  Object lifetime is precisely specified and I don't see
>> >where it is
>> >> >> tied to (static) storage lifetime.
>> >> >
>> >> > This is precisely the testcase I posted on beggining of this
>> >thread.
>> >> >
>> >> > I do not see how the testcases can work with aliasing rules in the
>> >case Q's and T's
>> >> > memory is known to not alias.
>> >>
>> >> It works because of the well-defined memory model (with regarding to
>> >> TBAA) in the middle-end.  Every store changes the dynamic type of
>> >> a memory location which means that you can only use TBAA for
>> >> true-dependence checks (not anti-dependence or write-dependence
>> >> checks).
>> >
>> >I see, I did not notice this change - it seems like quite a big hammer
>> >though,
>> >limiting scheduling (and loop opts) quite noticeably for all languages.
>> >Are
>> >there any other motivations for this besides placement new?
>>
>> Aggregate copies and memcpy transferring the dynamic type for example.  Being able to tbaa union accesses for another.  And yes, placement new.
>>
>> It's not so much an optimization preventing thing as you still can move loads up and stores down with the help of tbaa.
>
> well, but you lose extra parallelism like
>
>  *shortptr = exp
>  <longer dependency chain with shortptr>
>  var = *shortptr
>  *intptr = exp
>  <longer dependency chain with intptr>
>  var = *intptr

Yes (that is, you can't hoist the *intptr = exp store above the var = *shortptr
load with TBAA only).  You can probably still hoist the <longer dependency
chain with intptr>, it's not clear from your example.

That said, being able to optimize union accesses with TBAA at all
is still nice (esp. for GCC).  Now, the C frontend still forces alias-set zero
for this case because of the RTL alias oracle disfunctionality which doesn't
treat a must-alias as an alias if it can TBAA disambiguate.

Richard.

> Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> On July 23, 2014 4:42:22 PM CEST, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> >> I don't see why
> >> >>
> >> >> long x[1024];
> >> >>
> >> >> Q *q = new (x) Q;
> >> >> q->~Q ();
> >> >> new (x) T;
> >> >>
> >> >> would be invalid.  I also don't see why
> >> >>
> >> >> Q q;
> >> >> q.~Q ();
> >> >> new (&q) T;
> >> >>
> >> >> would be.  Object lifetime is precisely specified and I don't see
> >where it is
> >> >> tied to (static) storage lifetime.
> >> >
> >> > This is precisely the testcase I posted on beggining of this
> >thread.
> >> >
> >> > I do not see how the testcases can work with aliasing rules in the
> >case Q's and T's
> >> > memory is known to not alias.
> >> 
> >> It works because of the well-defined memory model (with regarding to
> >> TBAA) in the middle-end.  Every store changes the dynamic type of
> >> a memory location which means that you can only use TBAA for
> >> true-dependence checks (not anti-dependence or write-dependence
> >> checks).
> >
> >I see, I did not notice this change - it seems like quite a big hammer
> >though,
> >limiting scheduling (and loop opts) quite noticeably for all languages.
> >Are
> >there any other motivations for this besides placement new?
> 
> Aggregate copies and memcpy transferring the dynamic type for example.  Being able to tbaa union accesses for another.  And yes, placement new.
> 
> It's not so much an optimization preventing thing as you still can move loads up and stores down with the help of tbaa.

well, but you lose extra parallelism like

 *shortptr = exp
 <longer dependency chain with shortptr>
 var = *shortptr
 *intptr = exp
 <longer dependency chain with intptr>
 var = *intptr

Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On July 23, 2014 4:42:22 PM CEST, Jan Hubicka <hubicka@ucw.cz> wrote:
>> On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >> I don't see why
>> >>
>> >> long x[1024];
>> >>
>> >> Q *q = new (x) Q;
>> >> q->~Q ();
>> >> new (x) T;
>> >>
>> >> would be invalid.  I also don't see why
>> >>
>> >> Q q;
>> >> q.~Q ();
>> >> new (&q) T;
>> >>
>> >> would be.  Object lifetime is precisely specified and I don't see
>where it is
>> >> tied to (static) storage lifetime.
>> >
>> > This is precisely the testcase I posted on beggining of this
>thread.
>> >
>> > I do not see how the testcases can work with aliasing rules in the
>case Q's and T's
>> > memory is known to not alias.
>> 
>> It works because of the well-defined memory model (with regarding to
>> TBAA) in the middle-end.  Every store changes the dynamic type of
>> a memory location which means that you can only use TBAA for
>> true-dependence checks (not anti-dependence or write-dependence
>> checks).
>
>I see, I did not notice this change - it seems like quite a big hammer
>though,
>limiting scheduling (and loop opts) quite noticeably for all languages.
>Are
>there any other motivations for this besides placement new?

Aggregate copies and memcpy transferring the dynamic type for example.  Being able to tbaa union accesses for another.  And yes, placement new.

It's not so much an optimization preventing thing as you still can move loads up and stores down with the help of tbaa.

>> That has been the way we operate since GCC 4.3 (if I remember
>> correctly).  That's also the reason we don't have to special-case
>> unions in any tricky way (yeah, we still do - because of that
>> type-punning special case and RTL alias analysis not dealing with
>it).
>> 
>> > Either we need to define what is and is not supported or go for
>speculative devirt more often.
>> 
>> The GCC middle-end (which also has to deal with cross-language
>> cases!) has this specified very clearly.
>
>Yep, the cross language support is bit more limited when you speak of
>polymorphic types. But indeed with the aliasing "hack" above I can
>imagine one can destroy one object and build new one on a given
>location.
>
>I will push things towards speculative types to allow implementing
>super-safe
>devirt and we could have flag strenghtening assumptions declaring that
>placement
>new is not used to change polymorphic type to other polymorphic type
>and we can
>see hw important it is in practice.

Yeah.

Thanks,
Richard.

>Honza
>> 
>> Richard.
>> 
>> > Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> I don't see why
> >>
> >> long x[1024];
> >>
> >> Q *q = new (x) Q;
> >> q->~Q ();
> >> new (x) T;
> >>
> >> would be invalid.  I also don't see why
> >>
> >> Q q;
> >> q.~Q ();
> >> new (&q) T;
> >>
> >> would be.  Object lifetime is precisely specified and I don't see where it is
> >> tied to (static) storage lifetime.
> >
> > This is precisely the testcase I posted on beggining of this thread.
> >
> > I do not see how the testcases can work with aliasing rules in the case Q's and T's
> > memory is known to not alias.
> 
> It works because of the well-defined memory model (with regarding to
> TBAA) in the middle-end.  Every store changes the dynamic type of
> a memory location which means that you can only use TBAA for
> true-dependence checks (not anti-dependence or write-dependence
> checks).

I see, I did not notice this change - it seems like quite a big hammer though,
limiting scheduling (and loop opts) quite noticeably for all languages. Are
there any other motivations for this besides placement new?
> 
> That has been the way we operate since GCC 4.3 (if I remember
> correctly).  That's also the reason we don't have to special-case
> unions in any tricky way (yeah, we still do - because of that
> type-punning special case and RTL alias analysis not dealing with it).
> 
> > Either we need to define what is and is not supported or go for speculative devirt more often.
> 
> The GCC middle-end (which also has to deal with cross-language
> cases!) has this specified very clearly.

Yep, the cross language support is bit more limited when you speak of
polymorphic types. But indeed with the aliasing "hack" above I can
imagine one can destroy one object and build new one on a given location.

I will push things towards speculative types to allow implementing super-safe
devirt and we could have flag strenghtening assumptions declaring that placement
new is not used to change polymorphic type to other polymorphic type and we can
see hw important it is in practice.

Honza
> 
> Richard.
> 
> > Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On Wed, Jul 23, 2014 at 12:44 PM, Jason Merrill <jason@redhat.com> wrote:
> On 07/22/2014 02:34 PM, Richard Biener wrote:
>>
>> As discussed during the Cauldron keeping some builtin doesn't help because
>>
>> you are not forced to access the newly created object via the pointer
>> returned
>> by the placement new.  That is,
>>
>>    template <T>
>>   struct Storage {
>>       char x[sizeof(T)];
>>      Storage() { new (x) T; }
>>      T& get() { return reinterpret_cast <T&> (x); }
>> };
>>
>> is valid
>
>
> Yes.
>
>
>> (and used in this way in Boost - with a type different from 'char'
>> to force bigger alignment).
>
>
> But I don't think that should be valid, unless the type contains a char
> array at offset 0, as {std,boost}::aligned_storage; the C++ standard needs
> improvement in this area.

Why especially at offset 0?  I'm constructing in the place of 'x', not
'this'.  Do you say that

template <class T>
struct Storage {
  T& get(i) { return new (x + sizeof (T) * i) T; }
  Storage (int n_) n (n_) {}
  int n;
  char x[sizeof (T)];
};

and doing

  Storage *s = new (malloc (sizeof (int)  * 4)) Storage (4);
  s->get (2);

isn't valid?

> Looks like the small buffer optimization in boost::spirit::hold_any would
> need to be tweaked, as it uses a void* to store anything the same size or
> smaller, but that's the only dodgy case I see.

I've seen other odd cases in GCC bugreports ultimately coming from
Boost & friends (mpl or whatnot).  Very likely older Boost versions
of course.

Btw, any reason why the standard treats 'char' and 'unsigned char'
special but not 'signed char'?

That said, as a matter of QOI I think only special-casing character
types would be a bad thing (see your hold_any example).

Richard.

> Jason
>

Re: Strenghten assumption about dynamic type changes (placement new)

[Jason Merrill]

On 07/22/2014 02:34 PM, Richard Biener wrote:
> As discussed during the Cauldron keeping some builtin doesn't help because
> you are not forced to access the newly created object via the pointer returned
> by the placement new.  That is,
>
>    template <T>
>   struct Storage {
>       char x[sizeof(T)];
>      Storage() { new (x) T; }
>      T& get() { return reinterpret_cast <T&> (x); }
> };
>
> is valid

Yes.

> (and used in this way in Boost - with a type different from 'char'
> to force bigger alignment).

But I don't think that should be valid, unless the type contains a char 
array at offset 0, as {std,boost}::aligned_storage; the C++ standard 
needs improvement in this area.

Looks like the small buffer optimization in boost::spirit::hold_any 
would need to be tweaked, as it uses a void* to store anything the same 
size or smaller, but that's the only dodgy case I see.

Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> I don't see why
>>
>> long x[1024];
>>
>> Q *q = new (x) Q;
>> q->~Q ();
>> new (x) T;
>>
>> would be invalid.  I also don't see why
>>
>> Q q;
>> q.~Q ();
>> new (&q) T;
>>
>> would be.  Object lifetime is precisely specified and I don't see where it is
>> tied to (static) storage lifetime.
>
> This is precisely the testcase I posted on beggining of this thread.
>
> I do not see how the testcases can work with aliasing rules in the case Q's and T's
> memory is known to not alias.

It works because of the well-defined memory model (with regarding to
TBAA) in the middle-end.  Every store changes the dynamic type of
a memory location which means that you can only use TBAA for
true-dependence checks (not anti-dependence or write-dependence
checks).

That has been the way we operate since GCC 4.3 (if I remember
correctly).  That's also the reason we don't have to special-case
unions in any tricky way (yeah, we still do - because of that
type-punning special case and RTL alias analysis not dealing with it).

> Either we need to define what is and is not supported or go for speculative devirt more often.

The GCC middle-end (which also has to deal with cross-language
cases!) has this specified very clearly.

Richard.

> Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> I don't see why
> 
> long x[1024];
> 
> Q *q = new (x) Q;
> q->~Q ();
> new (x) T;
> 
> would be invalid.  I also don't see why
> 
> Q q;
> q.~Q ();
> new (&q) T;
> 
> would be.  Object lifetime is precisely specified and I don't see where it is
> tied to (static) storage lifetime.

This is precisely the testcase I posted on beggining of this thread.

I do not see how the testcases can work with aliasing rules in the case Q's and T's
memory is known to not alias.

Either we need to define what is and is not supported or go for speculative devirt more often.

Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On Tue, Jul 22, 2014 at 3:54 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>
>> As discussen during the Cauldron keeping some builtin doesn't help because
>> you are not forced to access the newly created object via the pointer returned
>> by the placement new.  That is,
>>
>>   template <T>
>>  struct Storage {
>>      char x[sizeof(T)];
>>     Storage() { new (x) T; }
>>     T& get() { return reinterpret_cast <T&> (x); }
>> };
>
> This indeed looks like sensible use of placement new...
>>
>> is valid (and used in this way in Boost - with a type different from 'char'
>> to force bigger alignment).
>
> This testcase with char replaced to long or other POD type is still fine for my analysis.
> I would like to assume that once a polymorphic type is built at a given location, it can
> not be changed to other, that is:
>
>   template <T>
>  struct Storage {
>      Q x;
>     Storage() { new (x) T; }
>     T& get() { return reinterpret_cast <T&> (x); }
> };
>
> Where both T and Q are polymorphic types. I think essentially aliasing rules
> disallows this (for Q and T being different types at least, not sure if one
> inherits other) because Q gets constructed and thus accessed. But it is sliperly
> indeed, as whole concept of placement new.
>
> I believe easiest way to go forward is to extend polymorphic_call_context to
> also hold speculative information about outer type.  In the cases I can detect
> a dynamic type but can not prove it did not changed, I still can use the
> speculative path.  This is not perfect, but will improve code quality.
>
> I am still hoping we can get sensible rules for placement new :)

I don't see why

long x[1024];

Q *q = new (x) Q;
q->~Q ();
new (x) T;

would be invalid.  I also don't see why

Q q;
q.~Q ();
new (&q) T;

would be.  Object lifetime is precisely specified and I don't see where it is
tied to (static) storage lifetime.

Richard.

> Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> 
> As discussen during the Cauldron keeping some builtin doesn't help because
> you are not forced to access the newly created object via the pointer returned
> by the placement new.  That is,
> 
>   template <T>
>  struct Storage {
>      char x[sizeof(T)];
>     Storage() { new (x) T; }
>     T& get() { return reinterpret_cast <T&> (x); }
> };

This indeed looks like sensible use of placement new...
> 
> is valid (and used in this way in Boost - with a type different from 'char'
> to force bigger alignment).

This testcase with char replaced to long or other POD type is still fine for my analysis.
I would like to assume that once a polymorphic type is built at a given location, it can
not be changed to other, that is:

  template <T>
 struct Storage {
     Q x;
    Storage() { new (x) T; }
    T& get() { return reinterpret_cast <T&> (x); }
};

Where both T and Q are polymorphic types. I think essentially aliasing rules
disallows this (for Q and T being different types at least, not sure if one
inherits other) because Q gets constructed and thus accessed. But it is sliperly
indeed, as whole concept of placement new.

I believe easiest way to go forward is to extend polymorphic_call_context to
also hold speculative information about outer type.  In the cases I can detect
a dynamic type but can not prove it did not changed, I still can use the
speculative path.  This is not perfect, but will improve code quality.

I am still hoping we can get sensible rules for placement new :)

Honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On Sat, Jul 19, 2014 at 5:44 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> On 07/18/2014 11:03 AM, Jan Hubicka wrote:
>> >I really only care about types containing virtual table pointers to not change,
>> >so non-PODs are out of game.  Current propagation is built around assumption that
>> >once polymorphic type is constructed on a given location it won't change to
>> >completely different type, only possibly repetitively construct & destruct.
>> >This is based on our earlier conversation where the outcome was that changing
>> >non-POD variable by placement new to different type is not defined.
>>
>> For a variable, yes.  If I have a char array buffer (possibly
>> wrapped in a class, e.g. std::aligned_storage), it is OK to
>> construct one non-POD object, destroy it, then construct one of a
>> different type in the same space, just like if we have two automatic
>> variables in different blocks that happen to occupy the same
>> location on the stack.  Again, this really needs to be specified
>> better in the standard.
>
> To support this safely I really think we will need to mark placement new
> in the gimple code via builtin for a short while.
>
> As discussed today. I may make a difference in between objects allocated in
> char buffers and objects allocated via normal new and propagate only across
> the second ones, but that seems a bit slipperly, too.
>>
>> >Anything weaker will probably need some cooperation from the frontend - I
>> >suppose best tie we have is the fact that you can't use 'a' to call foo after
>> >changing object. If placement news was marked for some time by a builtin, we
>> >could effectively thread the re-allocated objects as a new memory locations.
>>
>> My concern about treating them as different memory locations is
>> danger of code reordering causing the lifetimes of the old and new
>> objects to overlap.
>
> I still do not see how this can work with aliasing rules - if the two objects
> allocated do not overlap, we will freely overlap the old and new objects.
> But adding extra builtin that will (for some time) keep the two pointer distinct
> should not make it any worse.

As discussen during the Cauldron keeping some builtin doesn't help because
you are not forced to access the newly created object via the pointer returned
by the placement new.  That is,

  template <T>
 struct Storage {
     char x[sizeof(T)];
    Storage() { new (x) T; }
    T& get() { return reinterpret_cast <T&> (x); }
};

is valid (and used in this way in Boost - with a type different from 'char'
to force bigger alignment).

Richard.

> Honza
>>
>> >Where I find current wording of DR1116?
>>
>> http://open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1116
>>
>> Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> On 07/18/2014 11:03 AM, Jan Hubicka wrote:
> >I really only care about types containing virtual table pointers to not change,
> >so non-PODs are out of game.  Current propagation is built around assumption that
> >once polymorphic type is constructed on a given location it won't change to
> >completely different type, only possibly repetitively construct & destruct.
> >This is based on our earlier conversation where the outcome was that changing
> >non-POD variable by placement new to different type is not defined.
> 
> For a variable, yes.  If I have a char array buffer (possibly
> wrapped in a class, e.g. std::aligned_storage), it is OK to
> construct one non-POD object, destroy it, then construct one of a
> different type in the same space, just like if we have two automatic
> variables in different blocks that happen to occupy the same
> location on the stack.  Again, this really needs to be specified
> better in the standard.

To support this safely I really think we will need to mark placement new
in the gimple code via builtin for a short while.

As discussed today. I may make a difference in between objects allocated in
char buffers and objects allocated via normal new and propagate only across
the second ones, but that seems a bit slipperly, too.
> 
> >Anything weaker will probably need some cooperation from the frontend - I
> >suppose best tie we have is the fact that you can't use 'a' to call foo after
> >changing object. If placement news was marked for some time by a builtin, we
> >could effectively thread the re-allocated objects as a new memory locations.
> 
> My concern about treating them as different memory locations is
> danger of code reordering causing the lifetimes of the old and new
> objects to overlap.

I still do not see how this can work with aliasing rules - if the two objects
allocated do not overlap, we will freely overlap the old and new objects.
But adding extra builtin that will (for some time) keep the two pointer distinct
should not make it any worse.  

Honza
> 
> >Where I find current wording of DR1116?
> 
> http://open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1116
> 
> Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Jason Merrill]

On 07/18/2014 11:03 AM, Jan Hubicka wrote:
> I really only care about types containing virtual table pointers to not change,
> so non-PODs are out of game.  Current propagation is built around assumption that
> once polymorphic type is constructed on a given location it won't change to
> completely different type, only possibly repetitively construct & destruct.
> This is based on our earlier conversation where the outcome was that changing
> non-POD variable by placement new to different type is not defined.

For a variable, yes.  If I have a char array buffer (possibly wrapped in 
a class, e.g. std::aligned_storage), it is OK to construct one non-POD 
object, destroy it, then construct one of a different type in the same 
space, just like if we have two automatic variables in different blocks 
that happen to occupy the same location on the stack.  Again, this 
really needs to be specified better in the standard.

> Anything weaker will probably need some cooperation from the frontend - I
> suppose best tie we have is the fact that you can't use 'a' to call foo after
> changing object. If placement news was marked for some time by a builtin, we
> could effectively thread the re-allocated objects as a new memory locations.

My concern about treating them as different memory locations is danger 
of code reordering causing the lifetimes of the old and new objects to 
overlap.

> Where I find current wording of DR1116?

http://open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1116

Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> On 07/08/2014 02:50 PM, Jan Hubicka wrote:
> >I am looking into tracking dynamic types now. Obviously I need to set very
> >exact rules about when these may change.
> 
> Let me first say that this area is somewhat in flux in the standard;
> if we have a model of what we want the rules to be for GCC, there's
> a good chance of getting them into the standard.  There are several
> unresolved DRs in this area already (1027, 1116, 1776).
> 
> >I think b variants are invalid
> 
> Yes, by 3.8/7; we can't use 'a' to call foo after we've changed the
> object there to a C.
> 
> >currently we also assume t1 to be invalid, but
> >t2 to be valid.
> 
> I think the compiler ought to be able to treat both as undefined,
> because 'a' is either defined (t1) or allocated (t2) as a B, and B
> does not contain an array of char, so changing the dynamic type of
> that memory before the end of its storage duration ought to be
> undefined.
> 
> But the standard doesn't currently say that, though it's along the
> lines of my proposed drafting for 1116 (which needs reworking).
> 
> And I suppose that my notion of 'allocated type' can really only
> apply when using the library allocation functions in 18.6.1.1 and
> 18.6.1.2, not the inline placement new.

Thanks! I guess we will have chance to chat about this on the Cauldron?  

As you probably know, for middle-end analysis it would be good if types was as
sticky as possible. The sucess of type based devirtualization is largely based
on the fact that it is hard to track a value of memory location by alias
analysis (as calls to external functions are generally believed to change it)
but it is easier to track type of a memory location, because the ways it can
change are limited to construcition/destruction and placement news.

I really only care about types containing virtual table pointers to not change,
so non-PODs are out of game.  Current propagation is built around assumption that
once polymorphic type is constructed on a given location it won't change to
completely different type, only possibly repatively construct & destruct.
This is based on our arlier conversation where the outcome was that chaning
non-POD variable by placement new to different type is not defined.

Anything weakter will probably need some cooperation from the frontend - I
suppose best tie we have is the fact that you can't use 'a' to call foo after
changing object. If placement news was marked for some time by a builtin, we
could effectively thread the re-allocated objects as a new memory locations..

So perhaps we can go with my dynamic type patch enforcing the strong
interpretation (no changes beyond construction/destruction once polymorphic
type lands on a given location) and document it (do we have convenient place in
the user documentation).  If it turns out to be impractical, we can always
carefuly relax it?

Where I find current wording of DR1116?

Honza
> 
> Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Jason Merrill]

On 07/08/2014 02:50 PM, Jan Hubicka wrote:
> I am looking into tracking dynamic types now. Obviously I need to set very
> exact rules about when these may change.

Let me first say that this area is somewhat in flux in the standard; if 
we have a model of what we want the rules to be for GCC, there's a good 
chance of getting them into the standard.  There are several unresolved 
DRs in this area already (1027, 1116, 1776).

> I think b variants are invalid

Yes, by 3.8/7; we can't use 'a' to call foo after we've changed the 
object there to a C.

> currently we also assume t1 to be invalid, but
> t2 to be valid.

I think the compiler ought to be able to treat both as undefined, 
because 'a' is either defined (t1) or allocated (t2) as a B, and B does 
not contain an array of char, so changing the dynamic type of that 
memory before the end of its storage duration ought to be undefined.

But the standard doesn't currently say that, though it's along the lines 
of my proposed drafting for 1116 (which needs reworking).

And I suppose that my notion of 'allocated type' can really only apply 
when using the library allocation functions in 18.6.1.1 and 18.6.1.2, 
not the inline placement new.

Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> > On 07/02/2014 01:18 PM, Jan Hubicka wrote:
> > >We propagate types from places we know instances are created across pointers
> > >passed to functions.  Once non-POD type is created at a given memory location,
> > >one can not change its type by placement_new into something else.
> > 
> > Hmm.  If the memory location is untyped (i.e. from malloc) or a
> > character array, or a union, you can indeed destroy an object of one
> > type and create an object of a different type in that location.
> > 
> > >Jason, this assumes that one can not destroy the type and re-construct same
> > >type at the same spot.
> > 
> > That is an invalid assumption; you can destroy one object and
> > construct a new one in the same location.  Doing it within a method
> > would be unusual, but I don't think there's a rule against it.
> > 
> Jason,
> I am looking into tracking dynamic types now. Obviously I need to set very
> exact rules about when these may change. Can you take a few minutes and tell me
> what of these sequences are valid?
> 
> I think b variants are invalid, currently we also assume t1 to be invalid, but
> t2 to be valid.
> With placement news, I wonder if we can arrange them to do before return:
> ptr = __builtin_placement_new (ptr)
> this builtin would be folded away after IPA wwhen we no longer need to track
> types same way as builtin_constant. That way I won't get two different dynamic
> types mixed at one pointer location, since these will look as two pointers
> until after inlining.  But given that C++ makes placement new to be written by
> hand, perhaps this is not possible?

It would be useful to know rules in these testcases. I am attaching WIP patch for
detecting dynamic type of heap allocated objects.  It basically takes Martin's detect_type_change
code from ipa-prop and adds discovery of constructor calls.  I however need to know if I need
to plan extra safe when propagating these types.
> 
> #include <stdio.h>
> inline void* operator new(__SIZE_TYPE__, void* __p) throw() { return __p;}
> 
> struct A
> {
>   virtual void foo() {printf ("A\n");}
> };
> struct B: A
> {
>   virtual void foo() {printf ("B\n");}
> };
> struct C: A
> {
>   virtual void foo() {printf ("C\n");}
> };
> 
> struct A *
> type(struct B *a)
> {
>   struct C *b;
>   ((struct B *)a)->~B();
>   b = new (a) C;
>   return b;
> }
> struct A *
> type_back(struct A *a)
> {
>   struct B *b;
>   ((struct C *)a)->~C();
>   b = new (a) B;
>   return b;
> }
> 
> void
> t1()
> {
>   struct B a;
>   struct A *b;
>   a.foo();
>   b=type(&a);
>   b->foo();
>   b=type_back (b);
>   a.foo();
> }
> void
> t1b()
> {
>   struct B a;
>   a.foo();
>   type(&a);
>   ((struct A *)&a)->foo();
>   type_back (&a);
>   ((struct A *)&a)->foo();
> }
> void
> t2()
> {
>   struct B *a = new (B);
>   struct A *b;
>   a->foo();
>   b=type(a);
>   b->foo();
> }
> void
> t2b()
> {
>   struct B *a = new (B);
>   struct A *b;
>   a->foo();
>   type(a);
>   ((struct A *)a)->foo();
> }
> main()
> {
>   t1();
>   t1b();
>   t2();
>   t2b();
> }

Index: gimple-fold.c
===================================================================
--- gimple-fold.c	(revision 212546)
+++ gimple-fold.c	(working copy)
@@ -372,7 +372,7 @@
 	    tree val = OBJ_TYPE_REF_EXPR (rhs);
 	    if (is_gimple_min_invariant (val))
 	      return val;
-	    else if (flag_devirtualize && virtual_method_call_p (val))
+	    else if (flag_devirtualize && virtual_method_call_p (rhs))
 	      {
 		bool final;
 		vec <cgraph_node *>targets
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c	(revision 212546)
+++ ipa-devirt.c	(working copy)
@@ -2092,6 +2113,26 @@
   return true;
 }
 
+/* See if OP is SSA name initialized as a copy or by single assignment.
+   If so, walk the SSA graph up.  */
+
+static tree
+walk_ssa_copies (tree op)
+{
+  STRIP_NOPS (op);
+  while (TREE_CODE (op) == SSA_NAME
+	 && !SSA_NAME_IS_DEFAULT_DEF (op)
+	 && SSA_NAME_DEF_STMT (op)
+	 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
+    {
+      if (gimple_assign_load_p (SSA_NAME_DEF_STMT (op)))
+	return op;
+      op = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op));
+      STRIP_NOPS (op);
+    }
+  return op;
+}
+
 /* Given REF call in FNDECL, determine class of the polymorphic
    call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT.
    CALL is optional argument giving the actual statement (usually call) where
@@ -2120,16 +2161,9 @@
   /* Walk SSA for outer object.  */
   do 
     {
-      if (TREE_CODE (base_pointer) == SSA_NAME
-	  && !SSA_NAME_IS_DEFAULT_DEF (base_pointer)
-	  && SSA_NAME_DEF_STMT (base_pointer)
-	  && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer)))
+      base_pointer = walk_ssa_copies (base_pointer);
+      if (TREE_CODE (base_pointer) == ADDR_EXPR)
 	{
-	  base_pointer = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (base_pointer));
-	  STRIP_NOPS (base_pointer);
-	}
-      else if (TREE_CODE (base_pointer) == ADDR_EXPR)
-	{
 	  HOST_WIDE_INT size, max_size;
 	  HOST_WIDE_INT offset2;
 	  tree base = get_ref_base_and_extent (TREE_OPERAND (base_pointer, 0),
@@ -2174,7 +2208,7 @@
 						     context->outer_type,
 						     call,
 						     current_function_decl);
-		  return NULL;
+		  return base_pointer;
 		}
 	      else
 		break;
@@ -2264,6 +2298,402 @@
   return base_pointer;
 }
 
+/* Structure to be passed in between detect_type_change and
+   check_stmt_for_type_change.  */
+
+struct type_change_info
+{
+  /* Offset into the object where there is the virtual method pointer we are
+     looking for.  */
+  HOST_WIDE_INT offset;
+  /* The declaration or SSA_NAME pointer of the base that we are checking for
+     type change.  */
+  tree instance;
+  /* The reference to virtual table pointer used.  */
+  tree vtbl_ptr_ref;
+  tree otr_type;
+  /* If we actually can tell the type that the object has changed to, it is
+     stored in this field.  Otherwise it remains NULL_TREE.  */
+  tree known_current_type;
+  HOST_WIDE_INT known_current_offset;
+
+  /* Set to true if dynamic type change has been detected.  */
+  bool type_maybe_changed;
+  /* Set to true if multiple types have been encountered.  known_current_type
+     must be disregarded in that case.  */
+  bool multiple_types_encountered;
+};
+
+/* Return true if STMT can modify a virtual method table pointer.
+
+   This function makes special assumptions about both constructors and
+   destructors which are all the functions that are allowed to alter the VMT
+   pointers.  It assumes that destructors begin with assignment into all VMT
+   pointers and that constructors essentially look in the following way:
+
+   1) The very first thing they do is that they call constructors of ancestor
+   sub-objects that have them.
+
+   2) Then VMT pointers of this and all its ancestors is set to new values
+   corresponding to the type corresponding to the constructor.
+
+   3) Only afterwards, other stuff such as constructor of member sub-objects
+   and the code written by the user is run.  Only this may include calling
+   virtual functions, directly or indirectly.
+
+   There is no way to call a constructor of an ancestor sub-object in any
+   other way.
+
+   This means that we do not have to care whether constructors get the correct
+   type information because they will always change it (in fact, if we define
+   the type to be given by the VMT pointer, it is undefined).
+
+   The most important fact to derive from the above is that if, for some
+   statement in the section 3, we try to detect whether the dynamic type has
+   changed, we can safely ignore all calls as we examine the function body
+   backwards until we reach statements in section 2 because these calls cannot
+   be ancestor constructors or destructors (if the input is not bogus) and so
+   do not change the dynamic type (this holds true only for automatically
+   allocated objects but at the moment we devirtualize only these).  We then
+   must detect that statements in section 2 change the dynamic type and can try
+   to derive the new type.  That is enough and we can stop, we will never see
+   the calls into constructors of sub-objects in this code.  Therefore we can
+   safely ignore all call statements that we traverse.
+  */
+
+static bool
+stmt_may_be_vtbl_ptr_store (gimple stmt)
+{
+  if (is_gimple_call (stmt))
+    return false;
+  else if (is_gimple_assign (stmt))
+    {
+      tree lhs = gimple_assign_lhs (stmt);
+
+      if (gimple_clobber_p (stmt))
+	return false;
+      if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
+	{
+	  if (flag_strict_aliasing
+	      && !POINTER_TYPE_P (TREE_TYPE (lhs)))
+	    return false;
+
+	  if (TREE_CODE (lhs) == COMPONENT_REF
+	      && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
+	    return false;
+	  /* In the future we might want to use get_base_ref_and_offset to find
+	     if there is a field corresponding to the offset and if so, proceed
+	     almost like if it was a component ref.  */
+	}
+    }
+  return true;
+}
+
+/* If STMT can be proved to be an assignment to the virtual method table
+   pointer of ANALYZED_OBJ and the type associated with the new table
+   identified, return the type.  Otherwise return NULL_TREE.  */
+
+static tree
+extr_type_from_vtbl_ptr_store (gimple stmt, struct type_change_info *tci,
+			       HOST_WIDE_INT *type_offset)
+{
+  HOST_WIDE_INT offset, size, max_size;
+  tree lhs, rhs, base, binfo;
+
+  if (!gimple_assign_single_p (stmt))
+    return NULL_TREE;
+
+  lhs = gimple_assign_lhs (stmt);
+  rhs = gimple_assign_rhs1 (stmt);
+  if (TREE_CODE (lhs) != COMPONENT_REF
+      || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
+    return NULL_TREE;
+
+  if (operand_equal_p (lhs, tci->vtbl_ptr_ref, 0))
+    ;
+  else
+    {
+      base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
+      if (offset != tci->offset
+	  || size != POINTER_SIZE
+	  || max_size != POINTER_SIZE)
+	return NULL_TREE;
+      if (TREE_CODE (base) == MEM_REF)
+	{
+	  if (!operand_equal_p (tci->instance, TREE_OPERAND (base, 0), 0)
+	      || !integer_zerop (TREE_OPERAND (base, 1)))
+	    return NULL_TREE;
+	}
+      else if (!operand_equal_p (tci->instance, base, 0)
+	       || tci->offset)
+	return NULL_TREE;
+    }
+
+  binfo = vtable_pointer_value_to_binfo (rhs);
+
+  if (!binfo)
+    return NULL;
+  *type_offset = tree_to_shwi (BINFO_OFFSET (binfo)) * BITS_PER_UNIT;
+  if (TYPE_BINFO (BINFO_TYPE (binfo)) == binfo)
+    return BINFO_TYPE (binfo);
+
+  /* TODO: Figure out the type containing BINFO.  */
+  debug_tree (binfo);
+  return NULL;
+}
+
+/* Record dynamic type change of TCI to TYPE.  */
+
+void
+record_known_type (struct type_change_info *tci, tree type, HOST_WIDE_INT offset)
+{
+  if (dump_file)
+    {
+      if (type)
+	{
+          fprintf (dump_file, "  Recording type: ");
+	  print_generic_expr (dump_file, type, TDF_SLIM);
+          fprintf (dump_file, " at offset %i\n", (int)offset);
+	}
+     else
+       fprintf (dump_file, "  Recording unknown type\n");
+    }
+  if (tci->type_maybe_changed
+      && (type != tci->known_current_type
+	  || offset != tci->known_current_offset))
+    tci->multiple_types_encountered = true;
+  tci->known_current_type = type;
+  tci->known_current_offset = offset;
+  tci->type_maybe_changed = true;
+}
+
+/* Callback of walk_aliased_vdefs and a helper function for
+   detect_type_change to check whether a particular statement may modify
+   the virtual table pointer, and if possible also determine the new type of
+   the (sub-)object.  It stores its result into DATA, which points to a
+   type_change_info structure.  */
+
+static bool
+check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
+{
+  gimple stmt = SSA_NAME_DEF_STMT (vdef);
+  struct type_change_info *tci = (struct type_change_info *) data;
+  tree fn;
+
+  /* If we already gave up, just terminate the rest of walk.  */
+  if (tci->multiple_types_encountered)
+    return true;
+
+  /* Check for a constructor call.  */
+  if (is_gimple_call (stmt)
+      && (fn = gimple_call_fndecl (stmt)) != NULL_TREE
+      && DECL_CXX_CONSTRUCTOR_P (fn)
+      && TREE_CODE (TREE_TYPE (fn)) == METHOD_TYPE
+      && gimple_call_num_args (stmt))
+    {
+      tree op = walk_ssa_copies (gimple_call_arg (stmt, 0));
+      tree type = method_class_type (TREE_TYPE (fn));
+      HOST_WIDE_INT offset, size, max_size;
+
+      if (dump_file)
+	{
+	  fprintf (dump_file, "  Checking constructor call: ");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	}
+
+      if (TREE_CODE (op) == ADDR_EXPR)
+	{
+	  op = get_ref_base_and_extent (TREE_OPERAND (op, 0),
+					&offset, &size, &max_size);
+	  if (op && TREE_CODE (op) == MEM_REF)
+	    {
+	      if (!tree_fits_shwi_p (TREE_OPERAND (op, 1)))
+	        return false;
+	      offset += tree_to_shwi (TREE_OPERAND (op, 1))
+		        * BITS_PER_UNIT;
+	      op = TREE_OPERAND (op, 0);
+	    }
+	  else
+	    return false;
+	  op = walk_ssa_copies (op);
+	}
+      if (operand_equal_p (op, tci->instance, 0)
+	  && TYPE_SIZE (type)
+	  && TREE_CODE (TYPE_SIZE (type)) == INTEGER_CST
+	  && tree_fits_shwi_p (TYPE_SIZE (type))
+	  && tree_to_shwi (TYPE_SIZE (type)) + offset > tci->offset)
+	{
+	  record_known_type (tci, type, tci->offset - offset);
+	  return true;
+	}
+    }
+
+  /* Check for inlined virtual table store.  */
+  if (stmt_may_be_vtbl_ptr_store (stmt))
+    {
+      tree type;
+      HOST_WIDE_INT offset = 0;
+      if (dump_file)
+	{
+	  fprintf (dump_file, "  Checking vtbl store: ");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	}
+
+      type = extr_type_from_vtbl_ptr_store (stmt, tci, &offset);
+      gcc_assert (!type || TYPE_MAIN_VARIANT (type) == type);
+      record_known_type (tci, type, offset);
+      return true;
+    }
+  else
+    return false;
+}
+
+/* CONTEXT is polymorphic call context obtained from get_polymorphic_context.
+   INSTANCE is pointer to the instance as returned by get_polymorphic_context.
+   If the type of instance is not fully determined (either OUTER_TYPE is unknown
+   or MAYBE_IN_CONSTRUCTION/INCLUDE_DERIVED_TYPES is set), try to walk memory
+   writes and find the actual construction of the instance.
+
+   We do not include this analysis in the context analysis itself, because
+   it needs memory SSA to be fully built and the walk may be expensive.
+   So it is not suitable for use withing fold_stmt and similar uses.  */
+
+bool
+get_dynamic_type (tree instance,
+		  ipa_polymorphic_call_context *context,
+		  tree otr_type,
+		  gimple call)
+{
+  struct type_change_info tci;
+  ao_ref ao;
+  bool function_entry_reached = false;
+  tree instance_ref = NULL;
+  gimple stmt = call;
+
+  if (!context->maybe_in_construction && !context->maybe_derived_type)
+    return false;
+
+  /* We need to obtain refernce to virtual table pointer.  It is better
+     to look it up in the code rather than build our own.  This require bit
+     of pattern matching, but we end up verifying that what we found is
+     correct.  */
+  if (gimple_code (call) == GIMPLE_CALL)
+    {
+      tree ref = gimple_call_fn (call);
+      HOST_WIDE_INT offset2, size, max_size;
+
+      if (TREE_CODE (ref) == OBJ_TYPE_REF)
+	{
+	  ref = OBJ_TYPE_REF_EXPR (ref);
+	  ref = walk_ssa_copies (ref);
+
+	  /* Check if definition looks like vtable lookup.  */
+	  if (TREE_CODE (ref) == SSA_NAME
+	      && !SSA_NAME_IS_DEFAULT_DEF (ref)
+	      && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref))
+	      && TREE_CODE (gimple_assign_rhs1
+			     (SSA_NAME_DEF_STMT (ref))) == MEM_REF)
+	    {
+	      ref = get_base_address
+		     (TREE_OPERAND (gimple_assign_rhs1
+				     (SSA_NAME_DEF_STMT (ref)), 0));
+	      ref = walk_ssa_copies (ref);
+	      /* Find base address of the lookup and see if it looks like
+		 vptr load.  */
+	      if (TREE_CODE (ref) == SSA_NAME
+		  && !SSA_NAME_IS_DEFAULT_DEF (ref)
+		  && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref)))
+		{
+		  tree ref_exp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (ref));
+		  tree base_ref = get_ref_base_and_extent (ref_exp, &offset2, &size, &max_size);
+
+		  /* Finally verify that what we found is based on INSTANCE.  */
+		  if (base_ref
+		      && TREE_CODE (base_ref) == MEM_REF
+		      && TREE_OPERAND (base_ref, 0) == instance)
+		    {
+		      stmt = SSA_NAME_DEF_STMT (ref);
+		      instance_ref = ref_exp;
+		    }
+		}
+	    }
+	}
+    }
+ 
+
+  /* If we failed to look up the refernece in code, build our own.  */
+  if (!instance_ref)
+    {
+      /* If the statement in question does not use memory, we can't tell
+	 anything.  */
+      if (!gimple_vuse (stmt))
+	return false;
+      instance_ref = build2 (MEM_REF,
+			     TREE_TYPE (BINFO_VTABLE (TYPE_BINFO (otr_type))),
+			     instance,
+			     build_int_cst (ptr_type_node,
+					    context->offset / BITS_PER_UNIT));
+    }
+
+
+  ao_ref_init (&ao, instance_ref);
+  /*ao.base = instance_ref;
+  ao.offset = context->offset;*/
+  ao.size = POINTER_SIZE;
+  ao.max_size = ao.size;
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "Determining dynamic type for call: ");
+      print_gimple_stmt (dump_file, call, 0, 0);
+      fprintf (dump_file, "  Starting walk at: ");
+      print_gimple_stmt (dump_file, stmt, 0, 0);
+      fprintf (dump_file, "  Instance pointer: ");
+      print_generic_expr (dump_file, instance, TDF_SLIM);
+      fprintf (dump_file, " offset: %i (bits)", (int)context->offset);
+      fprintf (dump_file, " vtbl reference: ");
+      print_generic_expr (dump_file, instance_ref, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+
+  tci.offset = context->offset;
+  tci.instance = instance;
+  tci.vtbl_ptr_ref = instance_ref;
+  gcc_assert (TREE_CODE (instance) != MEM_REF);
+  tci.known_current_type = NULL_TREE;
+  tci.known_current_offset = 0;
+  tci.otr_type = otr_type;
+  tci.type_maybe_changed = false;
+  tci.multiple_types_encountered = false;
+
+  walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
+		      &tci, NULL, &function_entry_reached);
+  if (!tci.type_maybe_changed)
+    {
+      if (context->maybe_in_construction)
+        context->maybe_in_construction = false;
+      if (dump_file)
+	fprintf (dump_file, "  No dynamic type change found.\n");
+      return true;
+    }
+
+  if (tci.known_current_type
+      && !function_entry_reached
+      && !tci.multiple_types_encountered)
+    {
+      context->outer_type = tci.known_current_type;
+      context->offset = tci.known_current_offset;
+      context->maybe_in_construction = false;
+      context->maybe_derived_type = false;
+      if (dump_file)
+	fprintf (dump_file, "  Determined dynamic type.\n");
+    }
+  else if (dump_file)
+    fprintf (dump_file, "  Found multiple types.\n");
+
+  return true;
+}
+
 /* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET.
    Lookup their respecitve virtual methods for OTR_TOKEN and OTR_TYPE
    and insert them to NODES.
Index: ipa-prop.c
===================================================================
--- ipa-prop.c	(revision 212546)
+++ ipa-prop.c	(working copy)
@@ -2134,7 +2134,36 @@
   struct ipa_node_params *info = fbi->info;
   HOST_WIDE_INT offset;
   bool by_ref;
+  struct cgraph_edge *cs = cgraph_edge (cgraph_get_node (current_function_decl), call);
 
+  if (cs->indirect_info->polymorphic)
+    {
+      tree otr_type;
+      HOST_WIDE_INT otr_token;
+      ipa_polymorphic_call_context context;
+      tree instance;
+      tree target = gimple_call_fn (call);
+
+      instance = get_polymorphic_call_info (current_function_decl,
+					    target,
+					    &otr_type, &otr_token,
+					    &context, call);
+
+      if (get_dynamic_type (instance, &context, otr_type, call))
+	{
+	  gcc_assert (TREE_CODE (otr_type) == RECORD_TYPE);
+	  cs->indirect_info->polymorphic = true;
+	  cs->indirect_info->param_index = -1;
+	  cs->indirect_info->otr_token = otr_token;
+	  cs->indirect_info->otr_type = otr_type;
+	  cs->indirect_info->outer_type = context.outer_type;
+	  cs->indirect_info->offset = context.offset;
+	  cs->indirect_info->maybe_in_construction
+	     = context.maybe_in_construction;
+	  cs->indirect_info->maybe_derived_type = context.maybe_derived_type;
+	}
+    }
+
   if (SSA_NAME_IS_DEFAULT_DEF (target))
     {
       tree var = SSA_NAME_VAR (target);
Index: ipa-utils.h
===================================================================
--- ipa-utils.h	(revision 212546)
+++ ipa-utils.h	(working copy)
@@ -89,6 +89,7 @@
 				HOST_WIDE_INT *,
 				ipa_polymorphic_call_context *,
 				gimple call = NULL);
+bool get_dynamic_type (tree, ipa_polymorphic_call_context *, tree, gimple);
 bool get_polymorphic_call_info_from_invariant (ipa_polymorphic_call_context *,
 					       tree, tree, HOST_WIDE_INT);
 bool decl_maybe_in_construction_p (tree, tree, gimple, tree);
Index: tree-ssa-pre.c
===================================================================
--- tree-ssa-pre.c	(revision 212546)
+++ tree-ssa-pre.c	(working copy)
@@ -63,6 +63,7 @@
 #include "domwalk.h"
 #include "ipa-prop.h"
 #include "tree-ssa-propagate.h"
+#include "ipa-utils.h"
 
 /* TODO:
 
@@ -4359,12 +4360,34 @@
 	{
 	  tree fn = gimple_call_fn (stmt);
 	  if (fn
-	      && TREE_CODE (fn) == OBJ_TYPE_REF
-	      && TREE_CODE (OBJ_TYPE_REF_EXPR (fn)) == SSA_NAME)
+	      && flag_devirtualize
+	      && virtual_method_call_p (fn))
 	    {
-	      fn = ipa_intraprocedural_devirtualization (stmt);
-	      if (fn && dbg_cnt (devirt))
+	      tree otr_type;
+	      HOST_WIDE_INT otr_token;
+	      ipa_polymorphic_call_context context;
+	      tree instance;
+	      bool final;
+
+	      instance = get_polymorphic_call_info (current_function_decl,
+						    fn,
+						    &otr_type, &otr_token, &context, stmt);
+
+	      get_dynamic_type (instance, &context, otr_type, stmt);
+
+	      vec <cgraph_node *>targets
+		= possible_polymorphic_call_targets (obj_type_ref_class (fn),
+						     tree_to_uhwi
+						       (OBJ_TYPE_REF_TOKEN (fn)),
+						     context,
+						     &final);
+	      if (final && targets.length () <= 1 && dbg_cnt (devirt))
 		{
+		  tree fn;
+		  if (targets.length () == 1)
+		    fn = targets[0]->decl;
+		  else
+		    fn = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
 		  if (dump_enabled_p ())
 		    {
 		      location_t loc = gimple_location_safe (stmt);
@@ -4376,6 +4399,8 @@
 		  gimple_call_set_fndecl (stmt, fn);
 		  gimple_set_modified (stmt, true);
 		}
+	      else
+	        gcc_assert (!ipa_intraprocedural_devirtualization (stmt));
 	    }
 	}
 

Re: Strenghten assumption about dynamic type changes (placement new)

[Richard Biener]

On Thu, Jul 3, 2014 at 4:20 AM, Jason Merrill <jason@redhat.com> wrote:
> On 07/02/2014 06:30 PM, Jan Hubicka wrote:
>>
>> But this is one of things that was not quite clear to me.  I know that
>> polymorphic type A
>> was created at a give memory location.  THis means that accesses to that
>> location in one
>> alias class has been made.
>> Now I destroy A and turn it into B, construct B and make memory accesses
>> in different
>> alias set.  I see this has chance to work if one is base of another, but
>> if B is completely
>> different type, I think strick aliasin should just make those accesses to
>> not alias and in turn
>> make whole thing undefined?
>
>
> Right, if they're unrelated types the accesses don't alias (3.10p10).
>
> On the subject of aliasing, there's a proposal to add explicit alias sets to
> C++:
>
>  http://open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf
>
> Any thoughts?

Well, but deleting the object at *p and constructing a new one with
different alias set there doesn't make it valid for GCC to move loads/stores
across that destruction/construction point, no?  With placement new / delete
they will basically be a no-op and be "invisible" in the IL - so what avoids
GCC, for example from insn scheduling, to mess things up here?  (the
GCC middle-end memory model does - but as far as I understand Honza
want's to play tricks to get around that, no?)

Richard.

> Jason
>

Re: Strenghten assumption about dynamic type changes (placement new)

[Bin.Cheng]

On Tue, Jul 8, 2014 at 2:50 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> On 07/02/2014 01:18 PM, Jan Hubicka wrote:
>> >We propagate types from places we know instances are created across pointers
>> >passed to functions.  Once non-POD type is created at a given memory location,
>> >one can not change its type by placement_new into something else.
>>
>> Hmm.  If the memory location is untyped (i.e. from malloc) or a
>> character array, or a union, you can indeed destroy an object of one
>> type and create an object of a different type in that location.
>>
>> >Jason, this assumes that one can not destroy the type and re-construct same
>> >type at the same spot.
>>
>> That is an invalid assumption; you can destroy one object and
>> construct a new one in the same location.  Doing it within a method
>> would be unusual, but I don't think there's a rule against it.
>>
> Jason,
> I am looking into tracking dynamic types now. Obviously I need to set very
> exact rules about when these may change. Can you take a few minutes and tell me
> what of these sequences are valid?
>
> I think b variants are invalid, currently we also assume t1 to be invalid, but
> t2 to be valid.
> With placement news, I wonder if we can arrange them to do before return:
> ptr = __builtin_placement_new (ptr)
> this builtin would be folded away after IPA wwhen we no longer need to track
> types same way as builtin_constant. That way I won't get two different dynamic
> types mixed at one pointer location, since these will look as two pointers
> until after inlining.  But given that C++ makes placement new to be written by
> hand, perhaps this is not possible?
>
> #include <stdio.h>
> inline void* operator new(__SIZE_TYPE__, void* __p) throw() { return __p;}
>
> struct A
> {
>   virtual void foo() {printf ("A\n");}
> };
> struct B: A
> {
>   virtual void foo() {printf ("B\n");}
> };
> struct C: A
> {
>   virtual void foo() {printf ("C\n");}
> };
>
> struct A *
> type(struct B *a)
> {
>   struct C *b;
>   ((struct B *)a)->~B();
>   b = new (a) C;
>   return b;
> }
> struct A *
> type_back(struct A *a)
> {
>   struct B *b;
>   ((struct C *)a)->~C();
>   b = new (a) B;
>   return b;
> }
>
> void
> t1()
> {
>   struct B a;
>   struct A *b;
>   a.foo();
>   b=type(&a);
>   b->foo();
>   b=type_back (b);
>   a.foo();
> }
> void
> t1b()
> {
>   struct B a;
>   a.foo();
>   type(&a);
>   ((struct A *)&a)->foo();
>   type_back (&a);
>   ((struct A *)&a)->foo();
> }
> void
> t2()
> {
>   struct B *a = new (B);
>   struct A *b;
>   a->foo();
>   b=type(a);
>   b->foo();
> }
> void
> t2b()
> {
>   struct B *a = new (B);
>   struct A *b;
>   a->foo();
>   type(a);
>   ((struct A *)a)->foo();
> }
> main()
> {
>   t1();
>   t1b();
>   t2();
>   t2b();
> }

Hi,

Below test also fails on arm-none-linux-gnueabi(hf):
NA->FAIL: g++.dg/ipa/imm-devirt-2.C  -std=gnu++11  scan-tree-dump einline "C
NA->FAIL: g++.dg/ipa/imm-devirt-2.C  -std=gnu++1y  scan-tree-dump einline "C
NA->FAIL: g++.dg/ipa/imm-devirt-2.C  -std=gnu++98  scan-tree-dump einline "C

Reported at https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61748

Thanks,
bin

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> On 07/02/2014 01:18 PM, Jan Hubicka wrote:
> >We propagate types from places we know instances are created across pointers
> >passed to functions.  Once non-POD type is created at a given memory location,
> >one can not change its type by placement_new into something else.
> 
> Hmm.  If the memory location is untyped (i.e. from malloc) or a
> character array, or a union, you can indeed destroy an object of one
> type and create an object of a different type in that location.
> 
> >Jason, this assumes that one can not destroy the type and re-construct same
> >type at the same spot.
> 
> That is an invalid assumption; you can destroy one object and
> construct a new one in the same location.  Doing it within a method
> would be unusual, but I don't think there's a rule against it.
> 
Jason,
I am looking into tracking dynamic types now. Obviously I need to set very
exact rules about when these may change. Can you take a few minutes and tell me
what of these sequences are valid?

I think b variants are invalid, currently we also assume t1 to be invalid, but
t2 to be valid.
With placement news, I wonder if we can arrange them to do before return:
ptr = __builtin_placement_new (ptr)
this builtin would be folded away after IPA wwhen we no longer need to track
types same way as builtin_constant. That way I won't get two different dynamic
types mixed at one pointer location, since these will look as two pointers
until after inlining.  But given that C++ makes placement new to be written by
hand, perhaps this is not possible?

#include <stdio.h>
inline void* operator new(__SIZE_TYPE__, void* __p) throw() { return __p;}

struct A
{
  virtual void foo() {printf ("A\n");}
};
struct B: A
{
  virtual void foo() {printf ("B\n");}
};
struct C: A
{
  virtual void foo() {printf ("C\n");}
};

struct A *
type(struct B *a)
{
  struct C *b;
  ((struct B *)a)->~B();
  b = new (a) C;
  return b;
}
struct A *
type_back(struct A *a)
{
  struct B *b;
  ((struct C *)a)->~C();
  b = new (a) B;
  return b;
}

void
t1()
{
  struct B a;
  struct A *b;
  a.foo();
  b=type(&a);
  b->foo();
  b=type_back (b);
  a.foo();
}
void
t1b()
{
  struct B a;
  a.foo();
  type(&a);
  ((struct A *)&a)->foo();
  type_back (&a);
  ((struct A *)&a)->foo();
}
void
t2()
{
  struct B *a = new (B);
  struct A *b;
  a->foo();
  b=type(a);
  b->foo();
}
void
t2b()
{
  struct B *a = new (B);
  struct A *b;
  a->foo();
  type(a);
  ((struct A *)a)->foo();
}
main()
{
  t1();
  t1b();
  t2();
  t2b();
}

Re: Strenghten assumption about dynamic type changes (placement new)

[Andreas Schwab]

Jan Hubicka <hubicka@ucw.cz> writes:

> Index: testsuite/g++.dg/ipa/imm-devirt-2.C
> ===================================================================
> --- testsuite/g++.dg/ipa/imm-devirt-2.C	(revision 212278)
> +++ testsuite/g++.dg/ipa/imm-devirt-2.C	(working copy)
> @@ -1,7 +1,7 @@
>  /* Verify that virtual calls are folded even early inlining puts them into one
>     function with the definition.  */
>  /* { dg-do run } */
> -/* { dg-options "-O2 -fdump-tree-fre1-details"  } */
> +/* { dg-options "-O2 -fdump-tree-einline"  } */
>  
>  extern "C" void abort (void);
>  
> @@ -91,5 +91,6 @@ int main (int argc, char *argv[])
>    return 0;
>  }
>  
> -/* { dg-final { scan-tree-dump "converting indirect call to function" "fre1"  } } */
> -/* { dg-final { cleanup-tree-dump "fre1" } } */
> +/* We fold into thunk of C. Eventually we should inline the thunk.  */
> +/* { dg-final { scan-tree-dump "C::_ZThn24_N1C3fooEi (" "einline"  } } */

FAIL: g++.dg/ipa/imm-devirt-2.C  -std=gnu++11  scan-tree-dump einline "C::_ZThn24_N1C3fooEi \\("

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Strenghten assumption about dynamic type changes (placement new)

[Andreas Schwab]

Jan Hubicka <hubicka@ucw.cz> writes:

> 	* cgraph.c (cgraph_create_indirect_edge): Update call of
> 	get_polymorphic_call_info.
> 	* ipa-utils.h (get_polymorphic_call_info): Add parameter CALL.
> 	(possible_polymorphic_call_targets): Add parameter call.
> 	(decl_maybe_in_construction_p): New predicate.
> 	(get_polymorphic_call_info): Add parameter call;
> 	use decl_maybe_in_construction_p.
> 	* gimple-fold.c (fold_gimple_assign): Update use of
> 	possible_polymorphic_call_targets.
> 	(gimple_fold_call): Likewise.
> 	* ipa-prop.c: Inlcude calls.h
> 	(ipa_binfo_from_known_type_jfunc): Check that known type is record.
> 	(param_type_may_change_p): New predicate.
> 	(detect_type_change_from_memory_writes): Break out from ...
> 	(detect_type_change): ... this one; use 
> 	param_type_may_change_p.
> 	(detect_type_change_ssa): Use param_type_may_change_p.
> 	(compute_known_type_jump_func): Use decl_maybe_in_construction_p.

This breaks g++.dg/ipa/pr61085.C on ia64.

(gdb) bt
#0  0xa000000000040721 in __kernel_syscall_via_break ()
#1  0x20000000004331d0 in *__GI_raise (sig=<optimized out>)
    at ../nptl/sysdeps/unix/sysv/linux/raise.c:67
#2  0x2000000000435ab0 in *__GI_abort () at abort.c:92
#3  0x40000000000009e0 in C::m_virt (this=0x4000000000000760 <main()+96>)
    at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:26
#4  0x4000000000000760 in m_foo (this=0x600ffffffffeee40)
    at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:20
#5  ~B (__vtt_parm=<optimized out>, this=0x600ffffffffeee40, 
    __in_chrg=<optimized out>)
    at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:14
#6  ~C (this=0x600ffffffffeee40, __in_chrg=<optimized out>, 
    __vtt_parm=<optimized out>)
    at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:24
#7  main ()
    at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:32

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Strenghten assumption about dynamic type changes (placement new)

[Marek Polacek]

On Fri, Jul 04, 2014 at 11:39:52PM +0200, Jan Hubicka wrote:
> Bootstrapped/regtested x86_64-linux, will commit it after bit more
> testing.
...
> 	* g++.dg/ipa/imm-devirt-1.C: Update testcase.
> 	* g++.dg/ipa/imm-devirt-2.C: Update testcase.

These testcases fail:

ERROR: g++.dg/ipa/imm-devirt-1.C  -std=gnu++98: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced
ERROR: g++.dg/ipa/imm-devirt-1.C  -std=gnu++11: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced
ERROR: g++.dg/ipa/imm-devirt-1.C  -std=gnu++1y: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced
ERROR: g++.dg/ipa/imm-devirt-2.C  -std=gnu++98: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced
ERROR: g++.dg/ipa/imm-devirt-2.C  -std=gnu++11: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced
ERROR: g++.dg/ipa/imm-devirt-2.C  -std=gnu++1y: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced

I'm fixing that with the following (will commit as obvious).

2014-07-06  Marek Polacek  <polacek@redhat.com>

	* g++.dg/ipa/imm-devirt-1.C: Fix regexp in dg-final.
	* g++.dg/ipa/imm-devirt-2.C: Likewise.

diff --git gcc/testsuite/g++.dg/ipa/imm-devirt-1.C gcc/testsuite/g++.dg/ipa/imm-devirt-1.C
index 115277f..85f1a8f 100644
--- gcc/testsuite/g++.dg/ipa/imm-devirt-1.C
+++ gcc/testsuite/g++.dg/ipa/imm-devirt-1.C
@@ -62,6 +62,6 @@ int main (int argc, char *argv[])
    a direct call.  */
 /* { dg-final { scan-tree-dump "Inlining int middleman_1" "einline"  } } */
 /* { dg-final { scan-tree-dump "Inlining int middleman_2" "einline"  } } */
-/* { dg-final { scan-tree-dump "B::foo (" "einline"  } } */
+/* { dg-final { scan-tree-dump "B::foo \\(" "einline"  } } */
 /* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 2 "einline"  } } */
 /* { dg-final { cleanup-tree-dump "einline" } } */
diff --git gcc/testsuite/g++.dg/ipa/imm-devirt-2.C gcc/testsuite/g++.dg/ipa/imm-devirt-2.C
index 58af089..db85487 100644
--- gcc/testsuite/g++.dg/ipa/imm-devirt-2.C
+++ gcc/testsuite/g++.dg/ipa/imm-devirt-2.C
@@ -92,5 +92,5 @@ int main (int argc, char *argv[])
 }
 
 /* We fold into thunk of C. Eventually we should inline the thunk.  */
-/* { dg-final { scan-tree-dump "C::_ZThn24_N1C3fooEi (" "einline"  } } */
+/* { dg-final { scan-tree-dump "C::_ZThn24_N1C3fooEi \\(" "einline"  } } */
 /* { dg-final { cleanup-tree-dump "einline" } } */

	Marek

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> On 07/02/2014 01:18 PM, Jan Hubicka wrote:
> >We propagate types from places we know instances are created across pointers
> >passed to functions.  Once non-POD type is created at a given memory location,
> >one can not change its type by placement_new into something else.
> 
> Hmm.  If the memory location is untyped (i.e. from malloc) or a
> character array, or a union, you can indeed destroy an object of one
> type and create an object of a different type in that location.
> 
> >Jason, this assumes that one can not destroy the type and re-construct same
> >type at the same spot.
> 
> That is an invalid assumption; you can destroy one object and
> construct a new one in the same location.  Doing it within a method
> would be unusual, but I don't think there's a rule against it.
Hi,
this is updated patch that does the legwork needed to prove we are not
re-constructing an object in the same location as we created previous one.
Currenlty we track only objects places in declarations, but I would really
like to understand how precisely the rules of the game differs when the
object lives in dynamically allocated memory - i.e. I work out the dynamic
type by spotting either virtual table store or constructor call.

Bootstrapped/regtested x86_64-linux, will commit it after bit more
testing.

	* cgraph.c (cgraph_create_indirect_edge): Update call of
	get_polymorphic_call_info.
	* ipa-utils.h (get_polymorphic_call_info): Add parameter CALL.
	(possible_polymorphic_call_targets): Add parameter call.
	(decl_maybe_in_construction_p): New predicate.
	(get_polymorphic_call_info): Add parameter call;
	use decl_maybe_in_construction_p.
	* gimple-fold.c (fold_gimple_assign): Update use of
	possible_polymorphic_call_targets.
	(gimple_fold_call): Likewise.
	* ipa-prop.c: Inlcude calls.h
	(ipa_binfo_from_known_type_jfunc): Check that known type is record.
	(param_type_may_change_p): New predicate.
	(detect_type_change_from_memory_writes): Break out from ...
	(detect_type_change): ... this one; use 
	param_type_may_change_p.
	(detect_type_change_ssa): Use param_type_may_change_p.
	(compute_known_type_jump_func): Use decl_maybe_in_construction_p.

	* g++.dg/ipa/devirt-26.C: Update testcase.
	* g++.dg/ipa/imm-devirt-1.C: Update testcase.
	* g++.dg/ipa/imm-devirt-2.C: Update testcase.
Index: cgraph.c
===================================================================
--- cgraph.c	(revision 212278)
+++ cgraph.c	(working copy)
@@ -967,7 +967,7 @@ cgraph_create_indirect_edge (struct cgra
       get_polymorphic_call_info (caller->decl,
 				 target,
 				 &otr_type, &otr_token,
-				 &context);
+				 &context, call_stmt);
 
       /* Only record types can have virtual calls.  */
       gcc_assert (TREE_CODE (otr_type) == RECORD_TYPE);
Index: testsuite/g++.dg/ipa/devirt-26.C
===================================================================
--- testsuite/g++.dg/ipa/devirt-26.C	(revision 212278)
+++ testsuite/g++.dg/ipa/devirt-26.C	(working copy)
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O3 -fdump-ipa-devirt-details"  } */
+/* { dg-options "-O3 -fdump-tree-ccp1"  } */
 struct A
  {
    int a;
@@ -23,7 +23,6 @@ int test(void)
   return d->foo()+b->foo();
 }
 /* The call to b->foo() is perfectly devirtualizable because C can not be in construction
-   when &c was used, but we can not analyze that so far.  Test that we at least speculate
-   that type is in the construction.  */
-/* { dg-final { scan-ipa-dump "speculatively devirtualizing" "devirt"  } } */
-/* { dg-final { cleanup-ipa-dump "devirt" } } */
+   when &c was used.  */
+/* { dg-final { scan-tree-dump-not "OBJ_TYPE_REF" "ccp1"  } } */
+/* { dg-final { cleanup-tree-dump "ccp1" } } */
Index: testsuite/g++.dg/ipa/imm-devirt-1.C
===================================================================
--- testsuite/g++.dg/ipa/imm-devirt-1.C	(revision 212278)
+++ testsuite/g++.dg/ipa/imm-devirt-1.C	(working copy)
@@ -1,7 +1,7 @@
 /* Verify that virtual calls are folded even early inlining puts them into one
    function with the definition.  */
 /* { dg-do run } */
-/* { dg-options "-O2 -fdump-tree-fre1-details"  } */
+/* { dg-options "-O2 -fdump-tree-einline"  } */
 
 extern "C" void abort (void);
 
@@ -58,5 +58,10 @@ int main (int argc, char *argv[])
   return 0;
 }
 
-/* { dg-final { scan-tree-dump "converting indirect call to function virtual int B::foo" "fre1"  } } */
-/* { dg-final { cleanup-tree-dump "fre1" } } */
+/* middleman_2 gets early inlined and the virtual call should get turned to
+   a direct call.  */
+/* { dg-final { scan-tree-dump "Inlining int middleman_1" "einline"  } } */
+/* { dg-final { scan-tree-dump "Inlining int middleman_2" "einline"  } } */
+/* { dg-final { scan-tree-dump "B::foo (" "einline"  } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 2 "einline"  } } */
+/* { dg-final { cleanup-tree-dump "einline" } } */
Index: testsuite/g++.dg/ipa/imm-devirt-2.C
===================================================================
--- testsuite/g++.dg/ipa/imm-devirt-2.C	(revision 212278)
+++ testsuite/g++.dg/ipa/imm-devirt-2.C	(working copy)
@@ -1,7 +1,7 @@
 /* Verify that virtual calls are folded even early inlining puts them into one
    function with the definition.  */
 /* { dg-do run } */
-/* { dg-options "-O2 -fdump-tree-fre1-details"  } */
+/* { dg-options "-O2 -fdump-tree-einline"  } */
 
 extern "C" void abort (void);
 
@@ -91,5 +91,6 @@ int main (int argc, char *argv[])
   return 0;
 }
 
-/* { dg-final { scan-tree-dump "converting indirect call to function" "fre1"  } } */
-/* { dg-final { cleanup-tree-dump "fre1" } } */
+/* We fold into thunk of C. Eventually we should inline the thunk.  */
+/* { dg-final { scan-tree-dump "C::_ZThn24_N1C3fooEi (" "einline"  } } */
+/* { dg-final { cleanup-tree-dump "einline" } } */
Index: ipa-utils.h
===================================================================
--- ipa-utils.h	(revision 212278)
+++ ipa-utils.h	(working copy)
@@ -87,9 +87,11 @@ bool possible_polymorphic_call_target_p
 tree method_class_type (const_tree);
 tree get_polymorphic_call_info (tree, tree, tree *,
 				HOST_WIDE_INT *,
-				ipa_polymorphic_call_context *);
+				ipa_polymorphic_call_context *,
+				gimple call = NULL);
 bool get_polymorphic_call_info_from_invariant (ipa_polymorphic_call_context *,
 					       tree, tree, HOST_WIDE_INT);
+bool decl_maybe_in_construction_p (tree, tree, gimple, tree);
 tree vtable_pointer_value_to_binfo (const_tree);
 bool vtable_pointer_value_to_vtable (const_tree, tree *, unsigned HOST_WIDE_INT *);
 bool contains_polymorphic_type_p (const_tree);
@@ -125,7 +127,8 @@ possible_polymorphic_call_targets (struc
 /* Same as above but taking OBJ_TYPE_REF as an parameter.  */
 
 inline vec <cgraph_node *>
-possible_polymorphic_call_targets (tree call,
+possible_polymorphic_call_targets (tree ref,
+				   gimple call,
 				   bool *final = NULL,
 				   void **cache_token = NULL)
 {
@@ -134,11 +137,11 @@ possible_polymorphic_call_targets (tree
   ipa_polymorphic_call_context context;
 
   get_polymorphic_call_info (current_function_decl,
-			     call,
-			     &otr_type, &otr_token, &context);
-  return possible_polymorphic_call_targets (obj_type_ref_class (call),
+			     ref,
+			     &otr_type, &otr_token, &context, call);
+  return possible_polymorphic_call_targets (obj_type_ref_class (ref),
 					    tree_to_uhwi
-					      (OBJ_TYPE_REF_TOKEN (call)),
+					      (OBJ_TYPE_REF_TOKEN (ref)),
 					    context,
 					    final, cache_token);
 }
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c	(revision 212278)
+++ ipa-devirt.c	(working copy)
@@ -1438,6 +1438,99 @@ vtable_pointer_value_to_binfo (const_tre
 					 offset, vtable);
 }
 
+/* We know that the instance is stored in variable or parameter
+   (not dynamically allocated) and we want to disprove the fact
+   that it may be in construction at invocation of CALL.
+
+   For the variable to be in construction we actually need to
+   be in constructor of corresponding global variable or
+   the inline stack of CALL must contain the constructor.
+   Check this condition.  This check works safely only before
+   IPA passes, because inline stacks may become out of date
+   later.  */
+
+bool
+decl_maybe_in_construction_p (tree base, tree outer_type,
+			      gimple call, tree function)
+{
+  outer_type = TYPE_MAIN_VARIANT (outer_type);
+  gcc_assert (DECL_P (base));
+
+  /* After inlining the code unification optimizations may invalidate
+     inline stacks.  Also we need to give up on global variables after
+     IPA, because addresses of these may have been propagated to their
+     constructors.  */
+  if (DECL_STRUCT_FUNCTION (function)->after_inlining)
+    return true;
+
+  /* Pure functions can not do any changes on the dynamic type;
+     that require writting to memory.  */
+  if (!auto_var_in_fn_p (base, function)
+      && flags_from_decl_or_type (function) & (ECF_PURE | ECF_CONST))
+    return false;
+
+  for (tree block = gimple_block (call); block && TREE_CODE (block) == BLOCK;
+       block = BLOCK_SUPERCONTEXT (block))
+    if (BLOCK_ABSTRACT_ORIGIN (block)
+	&& TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block)) == FUNCTION_DECL)
+      {
+	tree fn = BLOCK_ABSTRACT_ORIGIN (block);
+
+	if (TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
+	    || (!DECL_CXX_CONSTRUCTOR_P (fn)
+		|| !DECL_CXX_DESTRUCTOR_P (fn)))
+	  {
+	    /* Watch for clones where we constant propagated the first
+	       argument (pointer to the instance).  */
+	    fn = DECL_ABSTRACT_ORIGIN (fn);
+	    if (!fn
+		|| !is_global_var (base)
+	        || TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
+		|| (!DECL_CXX_CONSTRUCTOR_P (fn)
+		    || !DECL_CXX_DESTRUCTOR_P (fn)))
+	      continue;
+	  }
+	if (flags_from_decl_or_type (fn) & (ECF_PURE | ECF_CONST))
+	  continue;
+
+	/* FIXME: this can go away once we have ODR types equivalency on
+	   LTO level.  */
+	if (in_lto_p && !polymorphic_type_binfo_p (TYPE_BINFO (outer_type)))
+	  return true;
+	tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (fn)));
+	if (types_same_for_odr (type, outer_type))
+	  return true;
+      }
+
+  if (TREE_CODE (base) == VAR_DECL
+      && is_global_var (base))
+    {
+      if (TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
+	  || (!DECL_CXX_CONSTRUCTOR_P (function)
+	      || !DECL_CXX_DESTRUCTOR_P (function)))
+	{
+	  if (!DECL_ABSTRACT_ORIGIN (function))
+	    return false;
+	  /* Watch for clones where we constant propagated the first
+	     argument (pointer to the instance).  */
+	  function = DECL_ABSTRACT_ORIGIN (function);
+	  if (!function
+	      || TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
+	      || (!DECL_CXX_CONSTRUCTOR_P (function)
+		  || !DECL_CXX_DESTRUCTOR_P (function)))
+	    return false;
+	}
+      /* FIXME: this can go away once we have ODR types equivalency on
+	 LTO level.  */
+      if (in_lto_p && !polymorphic_type_binfo_p (TYPE_BINFO (outer_type)))
+	return true;
+      tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (function)));
+      if (types_same_for_odr (type, outer_type))
+	return true;
+    }
+  return false;
+}
+
 /* Proudce polymorphic call context for call method of instance
    that is located within BASE (that is assumed to be a decl) at OFFSET. */
 
@@ -1490,6 +1583,8 @@ get_polymorphic_call_info_from_invariant
 
 /* Given REF call in FNDECL, determine class of the polymorphic
    call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT.
+   CALL is optional argument giving the actual statement (usually call) where
+   the context is used.
    Return pointer to object described by the context  */
 
 tree
@@ -1497,7 +1592,8 @@ get_polymorphic_call_info (tree fndecl,
 			   tree ref,
 			   tree *otr_type,
 			   HOST_WIDE_INT *otr_token,
-			   ipa_polymorphic_call_context *context)
+			   ipa_polymorphic_call_context *context,
+			   gimple call)
 {
   tree base_pointer;
   *otr_type = obj_type_ref_class (ref);
@@ -1561,6 +1657,12 @@ get_polymorphic_call_info (tree fndecl,
 		    }
 		  get_polymorphic_call_info_for_decl (context, base,
 						      context->offset + offset2);
+		  if (context->maybe_in_construction && call)
+		    context->maybe_in_construction
+		     = decl_maybe_in_construction_p (base,
+						     context->outer_type,
+						     call,
+						     current_function_decl);
 		  return NULL;
 		}
 	      else
Index: gimple-fold.c
===================================================================
--- gimple-fold.c	(revision 212278)
+++ gimple-fold.c	(working copy)
@@ -376,7 +376,7 @@ fold_gimple_assign (gimple_stmt_iterator
 	      {
 		bool final;
 		vec <cgraph_node *>targets
-		  = possible_polymorphic_call_targets (val, &final);
+		  = possible_polymorphic_call_targets (val, stmt, &final);
 		if (final && targets.length () <= 1 && dbg_cnt (devirt))
 		  {
 		    tree fndecl;
@@ -1125,7 +1125,7 @@ gimple_fold_call (gimple_stmt_iterator *
 	{
 	  bool final;
 	  vec <cgraph_node *>targets
-	    = possible_polymorphic_call_targets (callee, &final);
+	    = possible_polymorphic_call_targets (callee, stmt, &final);
 	  if (final && targets.length () <= 1 && dbg_cnt (devirt))
 	    {
 	      tree lhs = gimple_call_lhs (stmt);
Index: ipa-prop.c
===================================================================
--- ipa-prop.c	(revision 212278)
+++ ipa-prop.c	(working copy)
@@ -62,6 +62,7 @@ along with GCC; see the file COPYING3.
 #include "dbgcnt.h"
 #include "domwalk.h"
 #include "builtins.h"
+#include "calls.h"
 
 /* Intermediate information that we get from alias analysis about a particular
    parameter in a particular basic_block.  When a parameter or the memory it
@@ -552,7 +553,11 @@ ipa_set_ancestor_jf (struct ipa_jump_fun
 tree
 ipa_binfo_from_known_type_jfunc (struct ipa_jump_func *jfunc)
 {
+  if (!RECORD_OR_UNION_TYPE_P (jfunc->value.known_type.base_type))
+    return NULL_TREE;
+
   tree base_binfo = TYPE_BINFO (jfunc->value.known_type.base_type);
+
   if (!base_binfo)
     return NULL_TREE;
   return get_binfo_at_offset (base_binfo,
@@ -731,18 +736,84 @@ check_stmt_for_type_change (ao_ref *ao A
     return false;
 }
 
+/* See if ARG is PARAM_DECl describing instance passed by pointer
+   or reference in FUNCTION.  Return false if the dynamic type may change
+   in between beggining of the function until CALL is invoked.
+
+   Generally functions are not allowed to change type of such instances,
+   but they call destructors.  We assume that methods can not destroy the THIS
+   pointer.  Also as a special cases, constructor and destructors may change
+   type of the THIS pointer.  */
 
+static bool
+param_type_may_change_p (tree function, tree arg, gimple call)
+{
+  /* Pure functions can not do any changes on the dynamic type;
+     that require writting to memory.  */
+  if (flags_from_decl_or_type (function) & (ECF_PURE | ECF_CONST))
+    return false;
+  /* We need to check if we are within inlined consturctor
+     or destructor (ideally we would have way to check that the
+     inline cdtor is actually working on ARG, but we don't have
+     easy tie on this, so punt on all non-pure cdtors.
+     We may also record the types of cdtors and once we know type
+     of the instance match them.
+
+     Also code unification optimizations may merge calls from
+     different blocks making return values unreliable.  So
+     do nothing during late optimization.  */
+  if (DECL_STRUCT_FUNCTION (function)->after_inlining)
+    return true;
+  if (TREE_CODE (arg) == SSA_NAME
+      && SSA_NAME_IS_DEFAULT_DEF (arg)
+      && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL)
+    {
+      /* Normal (non-THIS) argument.  */
+      if ((SSA_NAME_VAR (arg) != DECL_ARGUMENTS (function)
+	   || TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE)
+	  /* THIS pointer of an method - here we we want to watch constructors
+	     and destructors as those definitely may change the dynamic
+	     type.  */
+	  || (TREE_CODE (TREE_TYPE (function)) == METHOD_TYPE
+	      && !DECL_CXX_CONSTRUCTOR_P (function)
+	      && !DECL_CXX_DESTRUCTOR_P (function)
+	      && (SSA_NAME_VAR (arg) == DECL_ARGUMENTS (function))))
+	{
+	  /* Walk the inline stack and watch out for ctors/dtors.  */
+	  for (tree block = gimple_block (call); block && TREE_CODE (block) == BLOCK;
+	       block = BLOCK_SUPERCONTEXT (block))
+	    if (BLOCK_ABSTRACT_ORIGIN (block)
+	        && TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block)) == FUNCTION_DECL)
+	      {
+		tree fn = BLOCK_ABSTRACT_ORIGIN (block);
+
+		if (flags_from_decl_or_type (fn) & (ECF_PURE | ECF_CONST))
+		  continue;
+		if (TREE_CODE (TREE_TYPE (fn)) == METHOD_TYPE
+		    && (DECL_CXX_CONSTRUCTOR_P (fn)
+		        || DECL_CXX_DESTRUCTOR_P (fn)))
+		  return true;
+	      }
+	  return false;
+	}
+    }
+  return true;
+}
 
 /* Detect whether the dynamic type of ARG of COMP_TYPE has changed (before
    callsite CALL) by looking for assignments to its virtual table pointer.  If
    it is, return true and fill in the jump function JFUNC with relevant type
    information or set it to unknown.  ARG is the object itself (not a pointer
    to it, unless dereferenced).  BASE is the base of the memory access as
-   returned by get_ref_base_and_extent, as is the offset.  */
+   returned by get_ref_base_and_extent, as is the offset. 
+
+   This is helper function for detect_type_change and detect_type_change_ssa
+   that does the heavy work which is usually unnecesary.  */
 
 static bool
-detect_type_change (tree arg, tree base, tree comp_type, gimple call,
-		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
+detect_type_change_from_memory_writes (tree arg, tree base, tree comp_type,
+				       gimple call, struct ipa_jump_func *jfunc,
+				       HOST_WIDE_INT offset)
 {
   struct type_change_info tci;
   ao_ref ao;
@@ -753,25 +824,6 @@ detect_type_change (tree arg, tree base,
 
   comp_type = TYPE_MAIN_VARIANT (comp_type);
 
-  if (!flag_devirtualize)
-    return false;
-
-  /* C++ methods are not allowed to change THIS pointer unless they
-     are constructors or destructors.  */
-  if (TREE_CODE	(base) == MEM_REF
-      && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
-      && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (base, 0))
-      && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (base, 0))) == PARM_DECL
-      && TREE_CODE (TREE_TYPE (current_function_decl)) == METHOD_TYPE
-      && !DECL_CXX_CONSTRUCTOR_P (current_function_decl)
-      && !DECL_CXX_DESTRUCTOR_P (current_function_decl)
-      && (SSA_NAME_VAR (TREE_OPERAND (base, 0))
-	  == DECL_ARGUMENTS (current_function_decl)))
-    {
-      gcc_assert (comp_type);
-      return false;
-    }
-
   /* Const calls cannot call virtual methods through VMT and so type changes do
      not matter.  */
   if (!flag_devirtualize || !gimple_vuse (call)
@@ -809,6 +861,28 @@ detect_type_change (tree arg, tree base,
   return true;
 }
 
+/* Detect whether the dynamic type of ARG of COMP_TYPE may have changed.
+   If it is, return true and fill in the jump function JFUNC with relevant type
+   information or set it to unknown.  ARG is the object itself (not a pointer
+   to it, unless dereferenced).  BASE is the base of the memory access as
+   returned by get_ref_base_and_extent, as is the offset.  */
+
+static bool
+detect_type_change (tree arg, tree base, tree comp_type, gimple call,
+		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
+{
+  if (!flag_devirtualize)
+    return false;
+
+  if (TREE_CODE	(base) == MEM_REF
+      && !param_type_may_change_p (current_function_decl,
+				   TREE_OPERAND (base, 0),
+				   call))
+    return false;
+  return detect_type_change_from_memory_writes (arg, base, comp_type,
+						call, jfunc, offset);
+}
+
 /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
    SSA name (its dereference will become the base and the offset is assumed to
    be zero).  */
@@ -822,10 +896,14 @@ detect_type_change_ssa (tree arg, tree c
       || !POINTER_TYPE_P (TREE_TYPE (arg)))
     return false;
 
+  if (!param_type_may_change_p (current_function_decl, arg, call))
+    return false;
+
   arg = build2 (MEM_REF, ptr_type_node, arg,
 		build_int_cst (ptr_type_node, 0));
 
-  return detect_type_change (arg, arg, comp_type, call, jfunc, 0);
+  return detect_type_change_from_memory_writes (arg, arg, comp_type,
+						call, jfunc, 0);
 }
 
 /* Callback of walk_aliased_vdefs.  Flags that it has been invoked to the
@@ -1433,11 +1511,15 @@ compute_known_type_jump_func (tree op, s
   if (!DECL_P (base)
       || max_size == -1
       || max_size != size
-      || !contains_polymorphic_type_p (TREE_TYPE (base))
-      || is_global_var (base))
+      || !contains_polymorphic_type_p (TREE_TYPE (base)))
     return;
 
-  if (detect_type_change (op, base, expected_type, call, jfunc, offset))
+  if (decl_maybe_in_construction_p (base, TREE_TYPE (base),
+				    call, current_function_decl)
+      /* Even if the var seems to be in construction by inline call stack,
+	 we may work out the actual type by walking memory writes.  */
+      && (!is_global_var (base)
+	  && detect_type_change (op, base, expected_type, call, jfunc, offset)))
     return;
 
   ipa_set_jf_known_type (jfunc, offset, TREE_TYPE (base),

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> On 07/02/2014 06:30 PM, Jan Hubicka wrote:
> >But this is one of things that was not quite clear to me.  I know that polymorphic type A
> >was created at a give memory location.  THis means that accesses to that location in one
> >alias class has been made.
> >Now I destroy A and turn it into B, construct B and make memory accesses in different
> >alias set.  I see this has chance to work if one is base of another, but if B is completely
> >different type, I think strick aliasin should just make those accesses to not alias and in turn
> >make whole thing undefined?
> 
> Right, if they're unrelated types the accesses don't alias (3.10p10).
> 
> On the subject of aliasing, there's a proposal to add explicit alias
> sets to C++:
> 
>  http://open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf
> 
> Any thoughts?

Thanks! I will take a look.
I would like to decide what to do with this approach. I can see
 1) I can start explicitly tracking if type came from a declaration or was detected dynamically
    (by seeing a vtable write or constructor call).  Currently we don't do the second, but I would
    like to understand if these make difference
 2) The code in question first detect that a type in a given variable is fully constructed and 
    then starts tracking it across function calls.  If needed I can check if my unwind stack contains
    some additional constructors/destructors that may possibly be currently destructing the type
    if it is valid to call destructor and construct same type there again.
    
    If one can there destruct the type and build completely different type, we need updates elsewhere
    in devirt machinery, too.

Thanks!
Honza
> 
> Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Jason Merrill]

On 07/02/2014 06:30 PM, Jan Hubicka wrote:
> But this is one of things that was not quite clear to me.  I know that polymorphic type A
> was created at a give memory location.  THis means that accesses to that location in one
> alias class has been made.
> Now I destroy A and turn it into B, construct B and make memory accesses in different
> alias set.  I see this has chance to work if one is base of another, but if B is completely
> different type, I think strick aliasin should just make those accesses to not alias and in turn
> make whole thing undefined?

Right, if they're unrelated types the accesses don't alias (3.10p10).

On the subject of aliasing, there's a proposal to add explicit alias 
sets to C++:

  http://open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf

Any thoughts?

Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> > On 07/02/2014 01:18 PM, Jan Hubicka wrote:
> > >We propagate types from places we know instances are created across pointers
> > >passed to functions.  Once non-POD type is created at a given memory location,
> > >one can not change its type by placement_new into something else.
> > 
> > Hmm.  If the memory location is untyped (i.e. from malloc) or a
> > character array, or a union, you can indeed destroy an object of one
> > type and create an object of a different type in that location.
> > 
> > >Jason, this assumes that one can not destroy the type and re-construct same
> > >type at the same spot.
> > 
> > That is an invalid assumption; you can destroy one object and
> > construct a new one in the same location.  Doing it within a method
> > would be unusual, but I don't think there's a rule against it.
> 
> The types get currently are one comming from declarations of variables
> and parameters passed by reference.
> Can I really destroy it/allocate new type/destroy new type/allocate back the original
> type (or terminate the program) so the destruction at the end of the lifetimate of the
> variable apsses?
> 
> I suppose we should keep track if memory location is comming from declaration or 
> it is dynamically typed (i.e. type seen from calling constructor)? Currently we don't
> deal with dynamic types, but I have patches for that.

But this is one of things that was not quite clear to me.  I know that polymorphic type A
was created at a give memory location.  THis means that accesses to that location in one
alias class has been made.
Now I destroy A and turn it into B, construct B and make memory accesses in different
alias set.  I see this has chance to work if one is base of another, but if B is completely
different type, I think strick aliasin should just make those accesses to not alias and in turn
make whole thing undefined?

honza

Re: Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

> On 07/02/2014 01:18 PM, Jan Hubicka wrote:
> >We propagate types from places we know instances are created across pointers
> >passed to functions.  Once non-POD type is created at a given memory location,
> >one can not change its type by placement_new into something else.
> 
> Hmm.  If the memory location is untyped (i.e. from malloc) or a
> character array, or a union, you can indeed destroy an object of one
> type and create an object of a different type in that location.
> 
> >Jason, this assumes that one can not destroy the type and re-construct same
> >type at the same spot.
> 
> That is an invalid assumption; you can destroy one object and
> construct a new one in the same location.  Doing it within a method
> would be unusual, but I don't think there's a rule against it.

The types get currently are one comming from declarations of variables
and parameters passed by reference.
Can I really destroy it/allocate new type/destroy new type/allocate back the original
type (or terminate the program) so the destruction at the end of the lifetimate of the
variable apsses?

I suppose we should keep track if memory location is comming from declaration or 
it is dynamically typed (i.e. type seen from calling constructor)? Currently we don't
deal with dynamic types, but I have patches for that.

Honza
> 
> Jason

Re: Strenghten assumption about dynamic type changes (placement new)

[Jason Merrill]

On 07/02/2014 01:18 PM, Jan Hubicka wrote:
> We propagate types from places we know instances are created across pointers
> passed to functions.  Once non-POD type is created at a given memory location,
> one can not change its type by placement_new into something else.

Hmm.  If the memory location is untyped (i.e. from malloc) or a 
character array, or a union, you can indeed destroy an object of one 
type and create an object of a different type in that location.

> Jason, this assumes that one can not destroy the type and re-construct same
> type at the same spot.

That is an invalid assumption; you can destroy one object and construct 
a new one in the same location.  Doing it within a method would be 
unusual, but I don't think there's a rule against it.

Jason

Strenghten assumption about dynamic type changes (placement new)

[Jan Hubicka]

Hi,
this patch strengthens detect_type_change and makes it cheaper based on the following observation.

We propagate types from places we know instances are created across pointers
passed to functions.  Once non-POD type is created at a given memory location,
one can not change its type by placement_new into something else.
This makes it easier to check if types may be altered from function start to
a given call site (information needed to produce jump function) by checking
whether function in question is a constructor or destructor and the parameter
is THIS pointer.  In other cases we can not retype anymore.

Jason, this assumes that one can not destroy the type and re-construct same
type at the same spot.  Is this valid for THIS pointer of normal methods and is
this valid in general?  If so, we will need to walk inline stack of the call
statement and watch for inlined constructor, as we may be within the
destructing/reconstructing sequence. This is not hard to do and I want to do it
anyway to disprove the fact htat local variable may be in
construction/destruction - that can be true only for calls that are within the
inlined constructor/destructor.

Bootstrapped/regtested x86_64-linux, will commit it if the above question is resolved.

Honza

	* ipa-prop.c (param_type_may_change_p): New function.
	(detect_type_change_from_memory_writes): Break out from ....
	(detect_type_change): ... here; use param_type_may_change_p.
	(detect_type_change_ssa): Use param_type_may_change_p.

Index: ipa-prop.c
===================================================================
--- ipa-prop.c	(revision 212234)
+++ ipa-prop.c	(working copy)
@@ -731,18 +731,45 @@ check_stmt_for_type_change (ao_ref *ao A
     return false;
 }
 
+/* See if ARG is PARAM_DECl describing instance passed by pointer
+   or reference in FUNCTION.  Return false if the dynamic type may not change.
 
+   Generally functions are not allowed to change type of such instances,
+   only excetions are C++ constructors and destructors.  */
+
+static bool
+param_type_may_change_p (tree function, tree arg)
+{
+  if (TREE_CODE (arg) == SSA_NAME
+      && SSA_NAME_IS_DEFAULT_DEF (arg)
+      && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL)
+    {
+      if (TREE_CODE (TREE_TYPE (function)) == METHOD_TYPE
+	  && !DECL_CXX_CONSTRUCTOR_P (function)
+	  && !DECL_CXX_DESTRUCTOR_P (function)
+	  && (SSA_NAME_VAR (arg) == DECL_ARGUMENTS (function)))
+	return false;
+
+      if (SSA_NAME_VAR (arg) != DECL_ARGUMENTS (function))
+	return false;
+    }
+  return true;
+}
 
 /* Detect whether the dynamic type of ARG of COMP_TYPE has changed (before
    callsite CALL) by looking for assignments to its virtual table pointer.  If
    it is, return true and fill in the jump function JFUNC with relevant type
    information or set it to unknown.  ARG is the object itself (not a pointer
    to it, unless dereferenced).  BASE is the base of the memory access as
-   returned by get_ref_base_and_extent, as is the offset.  */
+   returned by get_ref_base_and_extent, as is the offset. 
+
+   This is helper function for detect_type_change and detect_type_change_ssa
+   that does the heavy work which is usually unnecesary.  */
 
 static bool
-detect_type_change (tree arg, tree base, tree comp_type, gimple call,
-		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
+detect_type_change_from_memory_writes (tree arg, tree base, tree comp_type,
+				       gimple call, struct ipa_jump_func *jfunc,
+				       HOST_WIDE_INT offset)
 {
   struct type_change_info tci;
   ao_ref ao;
@@ -753,25 +780,6 @@ detect_type_change (tree arg, tree base,
 
   comp_type = TYPE_MAIN_VARIANT (comp_type);
 
-  if (!flag_devirtualize)
-    return false;
-
-  /* C++ methods are not allowed to change THIS pointer unless they
-     are constructors or destructors.  */
-  if (TREE_CODE	(base) == MEM_REF
-      && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
-      && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (base, 0))
-      && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (base, 0))) == PARM_DECL
-      && TREE_CODE (TREE_TYPE (current_function_decl)) == METHOD_TYPE
-      && !DECL_CXX_CONSTRUCTOR_P (current_function_decl)
-      && !DECL_CXX_DESTRUCTOR_P (current_function_decl)
-      && (SSA_NAME_VAR (TREE_OPERAND (base, 0))
-	  == DECL_ARGUMENTS (current_function_decl)))
-    {
-      gcc_assert (comp_type);
-      return false;
-    }
-
   /* Const calls cannot call virtual methods through VMT and so type changes do
      not matter.  */
   if (!flag_devirtualize || !gimple_vuse (call)
@@ -809,6 +817,27 @@ detect_type_change (tree arg, tree base,
   return true;
 }
 
+/* Detect whether the dynamic type of ARG of COMP_TYPE may have changed.
+   If it is, return true and fill in the jump function JFUNC with relevant type
+   information or set it to unknown.  ARG is the object itself (not a pointer
+   to it, unless dereferenced).  BASE is the base of the memory access as
+   returned by get_ref_base_and_extent, as is the offset.  */
+
+static bool
+detect_type_change (tree arg, tree base, tree comp_type, gimple call,
+		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
+{
+  if (!flag_devirtualize)
+    return false;
+
+  if (TREE_CODE	(base) == MEM_REF
+      && !param_type_may_change_p (current_function_decl,
+				   TREE_OPERAND (base, 0)))
+    return false;
+  return detect_type_change_from_memory_writes (arg, base, comp_type,
+						call, jfunc, offset);
+}
+
 /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
    SSA name (its dereference will become the base and the offset is assumed to
    be zero).  */
@@ -822,10 +851,14 @@ detect_type_change_ssa (tree arg, tree c
       || !POINTER_TYPE_P (TREE_TYPE (arg)))
     return false;
 
+  if (!param_type_may_change_p (current_function_decl, arg))
+    return false;
+
   arg = build2 (MEM_REF, ptr_type_node, arg,
 		build_int_cst (ptr_type_node, 0));
 
-  return detect_type_change (arg, arg, comp_type, call, jfunc, 0);
+  return detect_type_change_from_memory_writes (arg, arg, comp_type,
+						call, jfunc, 0);
 }
 
 /* Callback of walk_aliased_vdefs.  Flags that it has been invoked to the