[PATCH][RFC] Remove quadratic loop with component_uses_parent_alias_set
Richard Biener
rguenther@suse.de
Thu Sep 26 13:54:00 GMT 2013
On Thu, 26 Sep 2013, Richard Biener wrote:
> 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.
Like the following.
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
Richard.
2013-09-26 Richard Biener <rguenther@suse.de>
* alias.h (component_uses_parent_alias_set): Rename to ...
(component_uses_parent_alias_set_from): ... this.
* alias.c (component_uses_parent_alias_set): Rename to ...
(component_uses_parent_alias_set_from): ... this and return
the desired parent.
(reference_alias_ptr_type_1): Use the result from
component_uses_parent_alias_set_from instead of stripping
components one at a time.
* emit-rtl.c (set_mem_attributes_minus_bitpos): Adjust.
Index: gcc/alias.c
===================================================================
--- gcc/alias.c (revision 202941)
+++ gcc/alias.c (working copy)
@@ -500,51 +500,58 @@ objects_must_conflict_p (tree t1, tree t
return alias_sets_must_conflict_p (set1, set2);
}
-/* Return true if all nested component references handled by
- get_inner_reference in T are such that we should use the alias set
- provided by the object at the heart of T.
-
- This is true for non-addressable components (which don't have their
- own alias set), as well as components of objects in alias set zero.
- This later point is a special case wherein we wish to override the
- alias set used by the component, but we don't have per-FIELD_DECL
- assignable alias sets. */
+/* 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. */
-bool
-component_uses_parent_alias_set (const_tree t)
+tree
+component_uses_parent_alias_set_from (const_tree t)
{
- while (1)
- {
- /* If we're at the end, it vacuously uses its own alias set. */
- if (!handled_component_p (t))
- return false;
+ const_tree found = NULL_TREE;
+ while (handled_component_p (t))
+ {
switch (TREE_CODE (t))
{
case COMPONENT_REF:
if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
- return true;
+ found = t;
break;
case ARRAY_REF:
case ARRAY_RANGE_REF:
if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
- return true;
+ found = t;
break;
case REALPART_EXPR:
case IMAGPART_EXPR:
break;
- default:
+ case BIT_FIELD_REF:
+ case VIEW_CONVERT_EXPR:
/* Bitfields and casts are never addressable. */
- return true;
+ found = t;
+ break;
+
+ default:
+ gcc_unreachable ();
}
+ if (get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) == 0)
+ found = t;
+
t = TREE_OPERAND (t, 0);
- if (get_alias_set (TREE_TYPE (t)) == 0)
- return true;
}
+
+ if (found)
+ return TREE_OPERAND (found, 0);
+
+ return NULL_TREE;
}
@@ -645,14 +652,11 @@ reference_alias_ptr_type_1 (tree *t)
(TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner, 1))))))
return TREE_TYPE (TREE_OPERAND (inner, 1));
- /* Otherwise, pick up the outermost object that we could have a pointer
- to, processing conversions as above. */
- /* ??? Ick, this is worse than quadratic! */
- while (component_uses_parent_alias_set (*t))
- {
- *t = TREE_OPERAND (*t, 0);
- STRIP_NOPS (*t);
- }
+ /* Otherwise, pick up the outermost object that we could have
+ a pointer to. */
+ tree tem = component_uses_parent_alias_set_from (*t);
+ if (tem)
+ *t = tem;
return NULL_TREE;
}
Index: gcc/alias.h
===================================================================
--- gcc/alias.h (revision 202941)
+++ gcc/alias.h (working copy)
@@ -33,7 +33,7 @@ extern alias_set_type get_alias_set (tre
extern alias_set_type get_deref_alias_set (tree);
extern alias_set_type get_varargs_alias_set (void);
extern alias_set_type get_frame_alias_set (void);
-extern bool component_uses_parent_alias_set (const_tree);
+extern tree component_uses_parent_alias_set_from (const_tree);
extern bool alias_set_subset_of (alias_set_type, alias_set_type);
extern void record_alias_subset (alias_set_type, alias_set_type);
extern void record_component_aliases (tree);
Index: gcc/emit-rtl.c
===================================================================
--- gcc/emit-rtl.c (revision 202941)
+++ gcc/emit-rtl.c (working copy)
@@ -1704,7 +1704,7 @@ set_mem_attributes_minus_bitpos (rtx ref
/* If this expression uses it's parent's alias set, mark it such
that we won't change it. */
- if (component_uses_parent_alias_set (t))
+ if (component_uses_parent_alias_set_from (t) != NULL_TREE)
MEM_KEEP_ALIAS_SET_P (ref) = 1;
/* If this is a decl, set the attributes of the MEM from it. */
More information about the Gcc-patches
mailing list