Re: [PATCH][RFC] Remove quadratic loop with component_uses_parent_alias_set

[Richard Biener <rguenther at suse dot de>]

On Thu, 26 Sep 2013, Eric Botcazou wrote:

> > Eric, the current way component_uses_parent_alias_set is called from
> > get_alias_set causes the reference tree chain to be walked O(n^2)
> > in case there is any DECL_NONADDRESSABLE_P or TYPE_NONALIASED_COMPONENT
> > reference in the tree chain.  Also the comment above
> > component_uses_parent_alias_set doesn't seem to match behavior
> > in get_alias_set.  get_alias_set ends up using exactly the type of
> > the parent
> > of the DECL_NONADDRESSABLE_P / TYPE_NONALIASED_COMPONENT reference
> > instead of "the alias set provided by the object at the heart of T"
> 
> That's what "the object at the heart of T" means I think: given the loop in 
> get_alias_set (or reference_alias_ptr_type_1 now), we end up retrieving the 
> parent of the outermost non-addressable component in the component chain 
> (outermost in the type layout sense), which is what is wanted: when you go 
> down the component chain from the base object to find the alias set, you need 
> to stop at the first non-addressable component.  That's what is achieved in 
> the RTL expander by means of MEM_KEEP_ALIAS_SET_P: you expand first the base 
> object, then set MEM_KEEP_ALIAS_SET_P for the first non-addressable component, 
> so that the alias set isn't touched any more after that.
> 
> But I agree that the head comment and the interface of c_u_p_a_s are awkward, 
> to say the least, and the quadratic aspect isn't very nice either.

Ok.

> > I also fail to see why component_uses_parent_alias_set invokes
> > get_alias_set (is that to make 'a.c' in struct { char c; } a;
> > use the alias set of 'a' instead of the alias set of 'char'?
> 
> Yes, I think it's intended to stop the walk as soon as you have a type with 
> alias set 0: if 'a' has alias set 0, then 'a.c' will have it. 

That wasn't the question - I was asking if we have a struct type
with non-zero alias set, like struct { char c; int i } a; then
if we have an access like a.c does the code want to use the
alias set of 'a' (non-zero) for the access for optimization purposes?
It seems not, given your comment below...

[...]

> However, I think the handling of the "parent has alias set zero" is wrong in 
> your patch, you should test
> 
>   if (get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) == 0)

but I fail to see how this can happen in practice?  It can happen
for ref-all bases but that case is handled separately.

But ok, I'll leave the code as-is functionality wise, we should change
semantics as followup if at all.

> > The only other use besides from get_alias_set is to set
> > MEM_KEEP_ALIAS_SET_P -
> 
> It means that the alias set already on the MEM may not be changed afterwards, 
> even if you look into its sub-components later.
> 
> > whatever that is exactly for, I can
> > see a single non-obvious use in store_constructor_field
> > (didn't bother to lookup how callers specify the alias_set argument).
> > In
> > 
> >             if (MEM_P (to_rtx) && !MEM_KEEP_ALIAS_SET_P (to_rtx)
> >                 && DECL_NONADDRESSABLE_P (field))
> >               {
> >                 to_rtx = copy_rtx (to_rtx);
> >                 MEM_KEEP_ALIAS_SET_P (to_rtx) = 1;
> >               }
> > 
> > we can just drop the MEM_KEEP_ALIAS_SET_P check (well, in case
> > MEM_KEEP_ALIAS_SET_P is dropped).
> 
> Do you mean dropped in set_mem_attributes_minus_bitpos?  No, I don't think we 
> can do that.

Yeah, I thought of dropping it completely - we know the effective
alias-set of the load/store stmt we are expanding via get_alias_set
of the expression.  I don't see why we need to invent new alias sets
in any place down the road when creating sub-accesses (either from
storing constructor components or from storing bitfield pieces).

Thanks for the comments, I'll prepare a patch to only remove the
quadraticness without changing anything else.

Richard.