[PATCH][RFC] Remove quadratic loop with component_uses_parent_alias_set

[Richard Biener <rguenther at suse dot de>]

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"

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'?
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).

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 only other use besides from get_alias_set is to set
MEM_KEEP_ALIAS_SET_P - 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).  And for the following call

            store_constructor_field (to_rtx, bitsize, bitpos, mode,
                                     value, cleared,
                                     get_alias_set (TREE_TYPE (field)));

pass MEM_ALIAS_SET instead of get_alias_set (TREE_TYPE (field)) for
DECL_NONADDRESSABLE_P (field), similar for the array handling in
the other use.

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?

Anyway, the patch nearly preserves behavior for the emit-rtl.c use.

Comments?

Thanks,
Richard.

Index: gcc/alias.c
===================================================================
--- gcc/alias.c	(revision 202865)
+++ gcc/alias.c	(working copy)
@@ -510,41 +510,49 @@ objects_must_conflict_p (tree t1, tree t
    alias set used by the component, but we don't have per-FIELD_DECL
    assignable alias sets.  */
 
-bool
+tree
 component_uses_parent_alias_set (const_tree t)
 {
-  while (1)
+  const_tree non_addressable = NULL_TREE;
+  while (handled_component_p (t))
     {
-      /* If we're at the end, it vacuously uses its own alias set.  */
-      if (!handled_component_p (t))
-	return false;
-
       switch (TREE_CODE (t))
 	{
 	case COMPONENT_REF:
 	  if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
-	    return true;
+	    non_addressable = t;
 	  break;
 
 	case ARRAY_REF:
 	case ARRAY_RANGE_REF:
 	  if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
-	    return true;
+	    non_addressable = 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;
+	  non_addressable = t;
+	  break;
+
+	default:
+	  gcc_unreachable ();
 	}
 
-      t = TREE_OPERAND (t, 0);
       if (get_alias_set (TREE_TYPE (t)) == 0)
-	return true;
+	non_addressable = t;
+
+      t = TREE_OPERAND (t, 0);
     }
+ 
+  if (non_addressable)
+    return TREE_OPERAND (non_addressable, 0);
+
+  return NULL_TREE;
 }
 
 
@@ -645,14 +653,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 (*t);
+  if (tem)
+    *t = tem;
 
   return NULL_TREE;
 }
Index: gcc/alias.h
===================================================================
--- gcc/alias.h	(revision 202865)
+++ 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 (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);