Help understanding gcc alias analysis

[Raoul Gough]

Richard Guenther wrote:
> On Sat, Jan 10, 2009 at 12:55 PM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>   
>> On Sat, Jan 10, 2009 at 12:19 PM, Raoul Gough <RaoulGough@clara.co.uk> wrote:
>>     
[snip]
>>> Here we pass into bar a pointer to int and double at the same storage
>>> location. So now, if the compiler goes ahead and reorders the read and write
>>> in function bar, the assertion would fail. Note that this code does *not*
>>> write one type into a union and read another. It writes an int, reads an int
>>> and then writes a double. All that's happening is that the storage is being
>>> *reused* for a different type. However, this re-use takes place within
>>> function bar, which doesn't necessarily know about the union (especially if
>>> it's in a different compilation unit).
>>>
>>> So, my question is, does the salias analysis indicate that the compiler
>>> thinks it can reorder the operations in function bar?
>>>       
>> There is a defect report about this and I'm sure numerous bugreports
>> in bugzilla.
>> The conclusion is that the above invokes undefined behavior because the
>> accesses are not done through a union type, so the static memory typing rules
>> of C apply.
>>     
>
> http://www.open-std.org/JTC1/SC22/WG14/www/docs/dr_236.htm
>
>   
Interesting. It looks like the committee discussion was going to make 
the union example invalid, but the one using plain pointers (and malloc) 
was still up for discussion. Then the final decision was that both of 
their examples invoked undefined behaviour. Unfortunately, that renders 
invalid a common idiom for free-list memory (de)allocators, by which I 
mean re-using the client storage space for the free-list "next" pointer 
in the deallocator.

I guess the situation is more complicated in C++, which has explicit 
destructors. Consider the following example, which is getting closer to 
the problem that originally got me interested in this subject:

void** global_free_list = 0;

inline void operator delete(void* p2) throw()
{
    // Save "next" pointer in re-used client storage. TODO - check for NULL
    *static_cast<void **>(p2) = global_free_list;
    global_free_list = static_cast<void **>(p2);
}

double foo(double* p1)
{
    double result = *p1;
    delete p1;
    return result;
}

Now, after inlining, this example looks very similar to my original one, 
except we have pointers of type double* and void** sharing the same 
storage space instead of int* and double*. Note - we can easily ensure 
that the corresponding operator new() always allocates storage suitably 
sized and aligned for a void*.

Using g++ -O3 -fdump-tree-salias -c alias2.cpp -o /dev/null (again, 
using g++ 4.3.2) shows the following:


Alias information for double foo(double*)

[...]

Symbol memory tags

SMT.6, UID D.1675, 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)
SMT.7, UID D.1676, void *, is addressable, is global, score: 640004, 
direct reads: 0, direct writes: 0, indirect reads: 0, indirect writes: 
1, call clobbered (stored in global, is global var)

Flow-sensitive alias information for double foo(double*)

SSA_NAME pointers

p1_1(D), name memory tag: NMT.8, is dereferenced, its value escapes, 
points-to vars: { SMT.6 }

p2.0_5, name memory tag: NMT.9, is dereferenced, points-to vars: { SMT.7 }

global_free_list.1_6, name memory tag: NMT.9, is dereferenced, its value 
escapes, points-to vars: { SMT.7 }

p2.0_7, name memory tag: NMT.9, is dereferenced, its value escapes, 
points-to vars: { SMT.7 }

[...]

double foo(double*) (p1)
{
  void * * p2.0;
  void * * global_free_list.1;
  double result;

<bb 2>:
  result_2 = *p1_1(D);
  p2.0_5 = (void * *) p1_1(D);
  global_free_list.1_6 = global_free_list;
  *p2.0_5 = global_free_list.1_6;
  p2.0_7 = (void * *) p1_1(D);
  global_free_list = p2.0_7;
  return result_2;

}

Of course, the type-based alias analysis says that double* and void** 
cannot refer to the same storage. I'm not so sure about the 
flow-sensitive alias information, since in principle the compiler can 
tell that p1 and p2 are identical. I've included the complete .salias 
file below. Would someone be able to say whether g++ thinks it can 
re-order the accesses via p1_1(D) and p2.0_5 in this example?

By the way, I'm pretty sure g++ 3.4.3 used to allow the re-ordering.

-- 
Thanks,
Raoul Gough.


$ g++ -v

Using built-in specs.

Target: i686-pc-linux-gnu

Configured with: ../../gcc-4.3.2/configure --prefix /local/build/install

--with-gmp=/local/build/install --with-mpfr=/local/build/install

Thread model: posix

gcc version 4.3.2 (GCC) 


salias output from
$ g++ -g -Wall -O3 -fdump-tree-salias -c alias2.cpp -o /dev/null



;; Function double foo(double*) (_Z3fooPd)

Points-to analysis

Constraints:

ANYTHING = &ANYTHING
READONLY = &ANYTHING
INTEGER = &ANYTHING
p1 = &ANYTHING
p2.0_5 = p1
global_free_list = &ANYTHING
global_free_list.1_6 = global_free_list
*p2.0_5 = global_free_list.1_6
p2.0_7 = p1
global_free_list = p2.0_7

Collapsing static cycles and doing variable substitution
Building predecessor graph
Detecting pointer and location equivalences
Rewriting constraints and unifying variables
Uniting pointer but not location equivalent variables
Finding indirect cycles
Solving graph

Points-to sets

NULL = { }
ANYTHING = { ANYTHING }
READONLY = { ANYTHING }
INTEGER = { ANYTHING }
p1 = { ANYTHING }
p2.0_5 = same as p1
global_free_list.1_6 = same as p1
global_free_list = same as p1
p2.0_7 = same as p1

Memory partitioning NOT NEEDED for foo

Memory reference statistics for double foo(double*)

Number of memory statements:     4
Number of call sites:            0
Number of pure/const call sites: 0
Number of asm sites:             0
Estimated number of loads:       2 (1/stmt)
Actual number of loads:          2 (1/stmt)
Estimated number of stores:      2 (1/stmt)
Actual number of stores:         2 (1/stmt)
Partitioning thresholds:         MAX = 1000   AVG = 3 (NO NEED TO PARTITION)
Number of partitioned symbols:   0
Number of unpartitioned symbols: 5

Alias information for double foo(double*)


Memory partitions


0 memory partitions holding 0 symbols

Flow-insensitive alias information for double foo(double*)

Aliased symbols

SMT.6, UID D.1675, 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)
SMT.7, UID D.1676, void *, is addressable, is global, score: 640004, 
direct reads: 0, direct writes: 0, indirect reads: 0, indirect writes: 
1, call clobbered (stored in global, is global var)
NMT.8, UID D.1677, 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: { SMT.6 }
NMT.9, UID D.1678, 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: { SMT.7 }
global_free_list, UID D.1655, void * *, is global, score: 960024, direct 
reads: 1, direct writes: 1, indirect reads: 0, indirect writes: 0, call 
clobbered (is global var)

Dereferenced pointers

p1, UID D.1661, double *, symbol memory tag: SMT.6, default def: p1_1(D)
p2.0, UID D.1669, void * *, symbol memory tag: SMT.7
global_free_list.1, UID D.1670, void * *, symbol memory tag: SMT.7

Symbol memory tags

SMT.6, UID D.1675, 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)
SMT.7, UID D.1676, void *, is addressable, is global, score: 640004, 
direct reads: 0, direct writes: 0, indirect reads: 0, indirect writes: 
1, call clobbered (stored in global, is global var)


Flow-sensitive alias information for double foo(double*)

SSA_NAME pointers

p1_1(D), name memory tag: NMT.8, is dereferenced, its value escapes, 
points-to vars: { SMT.6 }

p2.0_5, name memory tag: NMT.9, is dereferenced, points-to vars: { SMT.7 }

global_free_list.1_6, name memory tag: NMT.9, is dereferenced, its value 
escapes, points-to vars: { SMT.7 }

p2.0_7, name memory tag: NMT.9, is dereferenced, its value escapes, 
points-to vars: { SMT.7 }


Name memory tags

NMT.8, UID D.1677, 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: { SMT.6 }
NMT.9, UID D.1678, 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: { SMT.7 }



Pointed-to sets for pointers in double foo(double*)

p1_1(D), name memory tag: NMT.8, is dereferenced, its value escapes, 
points-to vars: { SMT.6 }

p2.0_5, name memory tag: NMT.9, is dereferenced, points-to vars: { SMT.7 }

global_free_list.1_6, name memory tag: NMT.9, is dereferenced, its value 
escapes, points-to vars: { SMT.7 }

p2.0_7, name memory tag: NMT.9, is dereferenced, its value escapes, 
points-to vars: { SMT.7 }




Symbols to be put in SSA form

{ global_free_list SMT.6 SMT.7 NMT.8 NMT.9 }


Incremental SSA update started at block: 0

Number of blocks in CFG: 3
Number of blocks to update: 2 ( 67%)



double foo(double*) (p1)
{
  void * * p2.0;
  void * * global_free_list.1;
  double result;

<bb 2>:
  result_2 = *p1_1(D);
  p2.0_5 = (void * *) p1_1(D);
  global_free_list.1_6 = global_free_list;
  *p2.0_5 = global_free_list.1_6;
  p2.0_7 = (void * *) p1_1(D);
  global_free_list = p2.0_7;
  return result_2;

}