Help understanding gcc alias analysis

[Raoul Gough]

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;

}