Fix PR 33870

[Diego Novillo]

Richard Guenther wrote:

> taking the address of result.x.pDirty causes the SFT to be marked as
> in substructure and the problem re-surfaces.

Yes.  Thanks for the test case.  The original patch did not take into 
account that the nesting level of the memory reference is also important.

There are two problems here:

1- Given an arbitrary memory expression M dereferencing a pointer P into 
a nested structure, the offset computed for M is the offset starting at 
P.  However, the offsets computed for the original SFTs are offsets from 
the top of the pointed-to memory object O.  So, when we recognize this 
situation, we must adjust the offsets.  This was the situation 
recognized and fixed by the original patch.

The bug was in the detection of whether P is "pointing to the middle of 
an object".  This is where the nesting level comes in to play.  Suppose 
that M was the expression p_3->b[3] and the original pointed-to object 
was v.x.y:

		struct {
			...
			struct {
				...
				struct {
					...
					int b[4];
				} y;
			} x;
		} v;

		p_3 = &v.x.y;

If alias analysis created SFTs for this structure, the array 'b' will 
have 4 SFTs associated with it.  Say SFT.12, SFT.13, SFT.14 and SFT.15. 
  However, only SFT.12 will be added to the alias set of p_3's name tag.

So, when we see the expression 'p_3->b[3]', we compute an offset of 96, 
but we need SFT.14 which will probably have an offset much higher than 
that.  So, we adjust 96 by the offset of SFT.12 and get to SFT.14.

In the original patch, we recognized this situation by asking whether 
the SFT.12 was inside a nested structure.  However, it may happen that 
the pointer was actually pointing to the base of the original object 
'v'.  In which case, we would have the expression 'p_3->x.y.b[3]', which 
also takes us to SFT.12.

But in this case, the offset we computed from 'p_3->x.y.b[3]' is 
*already* the right offset, so adding the offset of SFT.12 to it gives 
us the wrong offset.  So, what this patch does is determine the nesting 
level of each SFT and the nesting level of the memory expression.  We 
only need to adjust the offset of an SFT if the nesting level of the 
memory expression is lower than the nesting level of the SFT that we are 
analyzing.


2- The second problem we have with this scheme is that we rely on the 
presence of key SFTs to adjust offsets when we detect references to 
nested aggregates.  This is something we cannot easily undo because 
inside the operand scanner we cannot really start doing use-def chain 
chasing to determine the original pointed-to objects.  This work has 
already been done by alias analysis, so duplicating this in the operand 
scanner would be wasteful.

This means that this scheme cannot tolerate these key SFTs to be 
partitioned away.  If they are partitioned, then inside the operand 
scanner is essentially impossible to determine where in the structure is 
an arbitrary memory expression referring to.  This is shown in the new 
test gcc.dg/tree-ssa/alias-16.c.

One way to deal with this would be to use the pointed-to set for the 
base pointer instead of the alias set of the name tag.  This has the 
problem that we'd miss the compile-time benefits of partitioning, as we 
would be traversing the original sets instead of the partitioned 
(smaller) alias sets.  Also, we may want to get rid of the duplicate 
pointed-to/alias sets in the future (not sure if they're both worth 
keeping).

The other way of dealing with this is to recognize which SFTs are 
important to not partition and make sure they are never partitioned. 
During alias analysis, if a nested SFT is added to the alias set of a 
pointer, then it is marked as unpartitionable.  The partitioner, in 
turn, gives these SFTs a very high score and makes sure that they are 
never added to a partition.  The effects of this are/should be 
negligible as it only involves a single SFT and nested structures.

The new test alias-16.c tests for these edge cases.

Tested on x86_64 and ppc64.  Committed to trunk.


Diego.
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 20071113-33870-nesting-level.diff.txt
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20071113/45d69dce/attachment.txt>