Re: Help understanding gcc alias analysis

[Richard Guenther <richard dot guenther at gmail dot com>]

On Mon, Jan 12, 2009 at 10:50 PM, Raoul Gough <RaoulGough@yahoo.co.uk> wrote:
> Richard Guenther wrote:
>>
>> On Mon, Jan 12, 2009 at 12:03 AM, Raoul Gough <RaoulGough@yahoo.co.uk>
>> wrote:
>>
>>>
>>> Richard Guenther wrote:
>>>
>
> [snip]
>>>>
>>>> This is also invalid.  You have to use placement new to change the
>>>> dynamic
>>>> type of memory.
>>>>
>>>>
>>>>
>>>
>>> Yes, I guess that makes sense. I've modified the example like this:
>>>
>>> #include <new>
>>>
>>> void** global_free_list = 0;
>>>
>>> inline void operator delete(void* p2) throw()
>>> {
>>>  // Save "next" pointer in re-used client storage
>>>  new (p2) (void *) (global_free_list);
>>>  global_free_list = static_cast<void **>(p2);
>>> }
>>>
>>> double foo(double* p1)
>>> {
>>>  double result = *p1;
>>>  delete p1;
>>>  return result;
>>> }
>>>
>>>
>>>
>
> [snip]
>>>
>>> So how is this example looking now? Does the alias analysis mean that g++
>>> will never reorder the read and write via p1 and p2?
>>>
>>
>> Yes, as that would now be an invalid thing to do.  Note that for C
>> there is no way to do "placement new", but the memory model of C
>> only has static typing, not the notion of a dynamic type.  Which is
>> why some people (including me) say you cannot do a C conforming
>> implementation of malloc that ever re-uses memory.
>>
>>
>
> I don't really see which part of the alias analysis shows that g++ won't
> reorder the accesses via the double* and the void**. Is it because the
> intersection of the "may aliases" lists is non-empty?

If you dump with -vops included you will see that we have conflict
SSA edges between the stores:

<bb 2>:
  # VUSE <global_free_list_10(D), SMT.12_11(D)>
  result_2 = *p1_1(D);
  D.2277_4 = p1_1(D);
  D.2278_5 = D.2277_4;
  if (D.2278_5 != 0B)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  D.2279_6 = (void * *) D.2278_5;
  # VUSE <global_free_list_10(D)>
  global_free_list.1_7 = global_free_list;
  # global_free_list_12 = VDEF <global_free_list_10(D)>
  # SMT.12_13 = VDEF <SMT.12_11(D)>
  *D.2279_6 = global_free_list.1_7;

<bb 4>:
  # global_free_list_9 = PHI <global_free_list_10(D)(2), global_free_list_12(3)>
  p2.2_8 = (void * *) p1_1(D);
  # global_free_list_14 = VDEF <global_free_list_9>
  global_free_list = p2.2_8;
  return result_2;

You can see that the stores/loads via *p1 or D.2279 (the void** pointer)
include VUSEs/VDEFs for both SMT.12 and global_free_list.  And this
is exactly because

SMT.12, UID D.2291, void, is addressable, is global, score: 24, direct
reads: 1, direct writes: 1, indirect reads: 0, indirect writes: 0,
call clobbered (stored in global, is global var, is incoming pointer),
may aliases: { global_free_list }

SMT.12 includes global_free_list in its aliases list.

Note that the may aliases list is only used for building this virtual
operands SSA web, it isn't suitable to be used in another way.

Richard.


> ----8<--------  start
> Symbol memory tags
>
> SMT.7, UID D.1868, void *, is addressable, is global, score: 556356, direct
> reads: 0, direct writes: 0, indirect reads: 0, indirect writes: 1, call
> clobbered (stored in global, is global var), may aliases: { global_free_list
> }
> SMT.8, UID D.1869, double, is addressable, is global, score: 320002, direct
> reads: 0, direct writes: 0, indirect reads: 1, indirect writes: 0, call
> clobbered (is global var, is incoming pointer), may aliases: {
> global_free_list }
> [...]
> Name memory tags
>
> NMT.9, UID D.1870, double, is addressable, is global, score: 8, direct
> reads: 1, direct writes: 0, indirect reads: 0, indirect writes: 0, call
> clobbered (is global var, is incoming pointer), may aliases: {
> global_free_list SMT.8 }
> NMT.10, UID D.1871, void *, is addressable, is global, score: 16, direct
> reads: 0, direct writes: 1, indirect reads: 0, indirect writes: 0, call
> clobbered (stored in global, is global var), may aliases: { global_free_list
> SMT.7 }
> ----8<--------  end
>
>
> By the way, if I change the example very slightly, so it uses char* for p1,
> the aliasing information is somewhat different. In particular, it includes
> the void* in the may-aliases list for the char.
>
> double bar(char* p1)
> {
>   double result = *p1;
>   delete p1;
>   return result;
>
> }
>
> Alias information for double bar(char*)
>
> [...]
>
> Symbol memory tags
>
> SMT.22, UID D.1898, void *, is addressable, is global, score: 876358, direct
> reads: 0, direct writes: 0, indirect reads: 1, indirect writes: 1, call
> clobbered (stored in global, is global var, is incoming pointer), may
> aliases: { global_free_list }
> SMT.23, UID D.1899, char, is addressable, is global, score: 320002, direct
> reads: 0, direct writes: 0, indirect reads: 1, indirect writes: 0, call
> clobbered (is global var, is incoming pointer), may aliases: {
> global_free_list SMT.22 }
>
> [...]
>
> Name memory tags
>
> NMT.24, UID D.1900, char, is addressable, is global, score: 8, direct reads:
> 1, direct writes: 0, indirect reads: 0, indirect writes: 0, call clobbered
> (is global var, is incoming pointer), may aliases: { global_free_list SMT.22
> SMT.23 }
> NMT.25, UID D.1901, void *, is addressable, is global, score: 16, direct
> reads: 0, direct writes: 1, indirect reads: 0, indirect writes: 0, call
> clobbered (stored in global, is global var), may aliases: { global_free_list
> SMT.22 }
>
>
> So I guess I'm just trying to understand how the alias data structures are
> used. In the one case (with a char*) it's pretty easy I guess, but I don't
> really understand how it represents the potential aliasing in the void**
> versus double* example.
>
> --
> Thanks,
> Raoul Gough.
>
>
>