This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Help understanding gcc alias analysis
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;
}