I've been investigating a code-reordering question to do with g++ strict
alias analysis, and I suspect there is a deficiency in the way
type-based alias analysis works. I realise that's unlikely to be the
case, so I'll try to present a concise demonstration which uses (I
think) well-defined C code. The original problem (now long worked
around) was in a much larger C++ codebase and did result in a harmful
reordering of code (although, that was with g++ 3.4.3). Output below is
from 4.3.2
Take these two example functions:
extern int foo(int* p1, char* p2)
{
int result = *p1;
*p2 = 4;
return result;
}
extern int bar(int* p1, double* p2)
{
int result = *p1;
*p2 = 4;
return result;
}
Both of these read via one pointer, assign via another and return the
first value. Obviously, if the two pointers alias the same storage and
the compiler reorders the read and the write, the wrong value will
result. In the first case, it's obvious that p2 may alias p1, since it
has type char*. Indeed, -fdump-tree-salias from g++ 4.3.2, shows the
following:
Alias information for int foo(int*, char*)
[...]
Symbol memory tags
SMT.4, UID D.1674, int, is addressable, is global, score: 960006, direct
reads: 0, direct writes: 0, indirect reads: 1, indirect writes: 1, call
clobbered (is global var, is incoming pointer), may aliases: { SMT.5 }
SMT.5, UID D.1675, char, is addressable, is global, score: 960006,
direct reads: 0, direct writes: 0, indirect reads: 1, indirect writes:
1, call clobbered (is global var, is incoming pointer), may aliases: {
SMT.4 }
[...]
I guess this means the compiler knows that the int* and char* "may
alias" the same storage. Now for the second function, type based alias
analysis tells us that p1 and p2 cannot alias each other, because an int
and a double can't simultaneously occupy the same storage. So
-fdump-tree-salias shows the following:
Alias information for int bar(int*, double*)
[...]
Symbol memory tags
SMT.18, UID D.1688, int, 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.19, UID D.1689, double, is addressable, is global, score: 640004,
direct reads: 0, direct writes: 0, indirect reads: 0, indirect writes:
1, call clobbered (is global var, is incoming pointer)
[...]
This doesn't show any "may aliases" lists, so I assume this means the
compiler thinks it can reorder accesses via the pointers. I've included
the full salias output below, in case I'm missing something. So here's a
problematic example (which was first pointed out to me by James Kanze on
comp.std.c++):
union A
{
int i_;
double d_;
};
void bar_bad()
{
A a;
a.i_ = 3;
assert(bar(&a.i_, &a.d_) == 3);
}
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?
--
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)
$ g++ -o /dev/null -g -O3 -fdump-tree-salias -c alias.cpp
;; Function int foo(int*, char*) (_Z3fooPiPc)
Points-to analysis
Constraints:
ANYTHING = &ANYTHING
READONLY = &ANYTHING
INTEGER = &ANYTHING
p1 = &ANYTHING
p2 = &ANYTHING
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 = same as p1
Memory partitioning NOT NEEDED for foo
Memory reference statistics for int foo(int*, char*)
Number of memory statements: 2
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: 3
Alias information for int foo(int*, char*)
Memory partitions
0 memory partitions holding 0 symbols
Flow-insensitive alias information for int foo(int*, char*)
Aliased symbols
SMT.4, UID D.1674, int, is addressable, is global, score: 960006, direct
reads: 0, direct writes: 0, indirect reads: 1, indirect writes: 1, call
clobbered (is global var, is incoming pointer), may aliases: { SMT.5 }
SMT.5, UID D.1675, char, is addressable, is global, score: 960006,
direct reads: 0, direct writes: 0, indirect reads: 1, indirect writes:
1, call clobbered (is global var, is incoming pointer), may aliases: {
SMT.4 }
NMT.6, UID D.1676, int, is addressable, is global, score: 24, direct
reads: 1, direct writes: 1, indirect reads: 0, indirect writes: 0, call
clobbered (is global var, is incoming pointer), may aliases: { SMT.4 SMT.5 }
Dereferenced pointers
p1, UID D.1655, int *, symbol memory tag: SMT.4, default def: p1_1(D)
p2, UID D.1656, char *, symbol memory tag: SMT.5, default def: p2_3(D)
Symbol memory tags
SMT.4, UID D.1674, int, is addressable, is global, score: 960006, direct
reads: 0, direct writes: 0, indirect reads: 1, indirect writes: 1, call
clobbered (is global var, is incoming pointer), may aliases: { SMT.5 }
SMT.5, UID D.1675, char, is addressable, is global, score: 960006,
direct reads: 0, direct writes: 0, indirect reads: 1, indirect writes:
1, call clobbered (is global var, is incoming pointer), may aliases: {
SMT.4 }
Flow-sensitive alias information for int foo(int*, char*)
SSA_NAME pointers
p1_1(D), name memory tag: NMT.6, is dereferenced, its value escapes,
points-to vars: { SMT.4 SMT.5 }
p2_3(D), name memory tag: NMT.6, is dereferenced, its value escapes,
points-to vars: { SMT.4 SMT.5 }
Name memory tags
NMT.6, UID D.1676, int, is addressable, is global, score: 24, direct
reads: 1, direct writes: 1, indirect reads: 0, indirect writes: 0, call
clobbered (is global var, is incoming pointer), may aliases: { SMT.4 SMT.5 }
Pointed-to sets for pointers in int foo(int*, char*)
p1_1(D), name memory tag: NMT.6, is dereferenced, its value escapes,
points-to vars: { SMT.4 SMT.5 }
p2_3(D), name memory tag: NMT.6, is dereferenced, its value escapes,
points-to vars: { SMT.4 SMT.5 }
Symbols to be put in SSA form
{ SMT.4 SMT.5 NMT.6 }
Incremental SSA update started at block: 0
Number of blocks in CFG: 3
Number of blocks to update: 2 ( 67%)
int foo(int*, char*) (p1, p2)
{
int result;
<bb 2>:
result_2 = *p1_1(D);
*p2_3(D) = 4;
return result_2;
}
;; Function int bar(int*, double*) (_Z3barPiPd)
Points-to analysis
Constraints:
ANYTHING = &ANYTHING
READONLY = &ANYTHING
INTEGER = &ANYTHING
p1 = &ANYTHING
p2 = &ANYTHING
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 = same as p1
Memory partitioning NOT NEEDED for bar
Memory reference statistics for int bar(int*, double*)
Number of memory statements: 2
Number of call sites: 0
Number of pure/const call sites: 0
Number of asm sites: 0
Estimated number of loads: 1 (1/stmt)
Actual number of loads: 1 (1/stmt)
Estimated number of stores: 1 (1/stmt)
Actual number of stores: 1 (1/stmt)
Partitioning thresholds: MAX = 1000 AVG = 3 (NO NEED TO PARTITION)
Number of partitioned symbols: 0
Number of unpartitioned symbols: 4
Alias information for int bar(int*, double*)
Memory partitions
0 memory partitions holding 0 symbols
Flow-insensitive alias information for int bar(int*, double*)
Aliased symbols
SMT.18, UID D.1688, int, 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.19, UID D.1689, double, is addressable, is global, score: 640004,
direct reads: 0, direct writes: 0, indirect reads: 0, indirect writes:
1, call clobbered (is global var, is incoming pointer)
NMT.20, UID D.1690, int, 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.18 }
NMT.21, UID D.1691, double, is addressable, is global, score: 16, direct
reads: 0, direct writes: 1, indirect reads: 0, indirect writes: 0, call
clobbered (is global var, is incoming pointer), may aliases: { SMT.19 }
Dereferenced pointers
p1, UID D.1661, int *, symbol memory tag: SMT.18, default def: p1_1(D)
p2, UID D.1662, double *, symbol memory tag: SMT.19, default def: p2_3(D)
Symbol memory tags
SMT.18, UID D.1688, int, 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.19, UID D.1689, double, is addressable, is global, score: 640004,
direct reads: 0, direct writes: 0, indirect reads: 0, indirect writes:
1, call clobbered (is global var, is incoming pointer)
Flow-sensitive alias information for int bar(int*, double*)
SSA_NAME pointers
p1_1(D), name memory tag: NMT.20, is dereferenced, its value escapes,
points-to vars: { SMT.18 }
p2_3(D), name memory tag: NMT.21, is dereferenced, its value escapes,
points-to vars: { SMT.19 }
Name memory tags
NMT.20, UID D.1690, int, 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.18 }
NMT.21, UID D.1691, double, is addressable, is global, score: 16, direct
reads: 0, direct writes: 1, indirect reads: 0, indirect writes: 0, call
clobbered (is global var, is incoming pointer), may aliases: { SMT.19 }
Pointed-to sets for pointers in int bar(int*, double*)
p1_1(D), name memory tag: NMT.20, is dereferenced, its value escapes,
points-to vars: { SMT.18 }
p2_3(D), name memory tag: NMT.21, is dereferenced, its value escapes,
points-to vars: { SMT.19 }
Symbols to be put in SSA form
{ SMT.18 SMT.19 NMT.20 NMT.21 }
Incremental SSA update started at block: 0
Number of blocks in CFG: 3
Number of blocks to update: 2 ( 67%)
int bar(int*, double*) (p1, p2)
{
int result;
<bb 2>:
result_2 = *p1_1(D);
*p2_3(D) = 4.0e+0;
return result_2;
}