[PATCH][RFC] Remove quadratic loop with component_uses_parent_alias_set

[Eric Botcazou]

> 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.

> 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. 

> Or is it for correctness reasons in case there is a ref-all
> indirect ref at the base?  For the former I believe it doesn't
> work because it only checks the non-outermost type).

This code predates ref-all.  

> So, the following patch removes the quadraticness by returning
> the parent of the innermost non-addressable (or alias-set zero)
> reference component instead of just a flag.  That changes behavior
> for the alias-set zero case but still doesn't match the overall
> function comment.

The change is fine, but let's rename the function and reword the comment (and 
agree on the terminology, I think it's better to use outermost here as already 
used in get_alias_set/reference_alias_ptr_type_1):

/* Return the outermost parent of component present in the chain of component
   references handled by get_inner_reference in T with the following property:
     - the component is non-addressable, or
     - the parent has alias set zero,
   or NULL_TREE if no such parent exists.  In the former cases, the alias set
   of this parent is the alias set that must be used for T itself.  */

tree
component_uses_parent_alias_set_from (const_tree t)

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)

> 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.

> Btw, checks like
> 
>      if (!MEM_KEEP_ALIAS_SET_P (to_rtx) && MEM_ALIAS_SET (to_rtx) != 0)
>         set_mem_alias_set (to_rtx, alias_set);
> 
> seem to miss MEM_ALIAS_SET (to_rtx) being ALIAS_SET_MEMORY_BARRIER?
> Or alias_set being zero / ALIAS_SET_MEMORY_BARRIER?

This code predates ALIAS_SET_MEMORY_BARRIER.

-- 
Eric Botcazou