Patchwork [RFC] Remove quadratic loop with component_uses_parent_alias_set

login
register
mail settings
Submitter Richard Guenther
Date Sept. 26, 2013, 12:42 p.m.
Message ID <alpine.LNX.2.00.1309261442050.29411@zhemvz.fhfr.qr>
Download mbox | patch
Permalink /patch/278188/
State New
Headers show

Comments

Richard Guenther - Sept. 26, 2013, 12:42 p.m.
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.
Eric Botcazou - Sept. 27, 2013, 8:48 a.m.
> 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.

FWIW it looks fine to me.

Patch

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