RFA: alias analysis for non-addressed variables vs. INDIRECT_REF

[Joern Rennecke <joern dot rennecke at superh dot com>]

As discussed before, we are currently missing opportunities to
hoist out accesses of non-addressed variables.  I have now
modified my patch so that a special node unspecified_indirect_ref_node
is used in MEM_EXPRs to mark memory accesses that are generated
from an otherwise unspecified INDIRECT_REF.

Consider this test case:

int
f(int s, int *a)
{
  static int i;
  for (i = 0; i < 800; i++)
    s += a[i];
  return s;
}

For the inner loop, this is the code that I get for sh-elf at -O2 -m4
with mainline from 2004-02-17 without my patch:

.L5:
        mov.l   @r7,r1
        mov     r1,r0
        shll2   r0
        mov.l   @(r0,r5),r2
        add     #1,r1
        cmp/gt  r6,r1
        mov.l   r1,@r7
        bf/s    .L5
        add     r2,r3

And this with the patch; the loads and stores if the loop induction
variable 'i' (@r7) have been hoisted out, and the a[i] giv has been
strength reduced from @(r0,r5) to @r5+.

.L5:
        mov.l   @r5+,r1
        add     #1,r2
        cmp/gt  r3,r2
        bf/s    .L5
        add     r1,r0

Bootstrapped / regtested on i686-pc-linux-gnu native.
Currently regtesting for i686-pc-linux-gnu X sh-elf.

2004-02-19  Stephen Clarke <stevec@superh.com>
	    J"orn Rennecke <joern.rennecke@superh.com>

	* tree.h (enum tree_index): Add TI_UNSPEC_IND_REF.
	(unspecified_indirect_ref_node): Define.
	* tree.c (build_common_tree_nodes): Initialize
	unspecified_indirect_ref_node.
	* emit-rtl.c (set_mem_attributes_minus_bitpos): When finding
	a vanilla INDIRECT_REF, record unspecified_indirect_ref_node.
	* print-rtl.c (print_mem_expr): Handle unspecified_indirect_ref_node.

	* alias.c (non_addressed_function_scope_var_p): New function.
	(nonoverlapping_memrefs_p): Use it.

Index: alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/alias.c,v
retrieving revision 1.214
diff -p -r1.214 alias.c
*** alias.c	3 Feb 2004 23:53:48 -0000	1.214
--- alias.c	19 Feb 2004 18:09:31 -0000
*************** static int aliases_everything_p (rtx);
*** 111,116 ****
--- 111,117 ----
  static bool nonoverlapping_component_refs_p (tree, tree);
  static tree decl_for_component_ref (tree);
  static rtx adjust_offset_for_component_ref (tree, rtx);
+ static tree non_addressed_function_scope_var (tree);
  static int nonoverlapping_memrefs_p (rtx, rtx);
  static int write_dependence_p (rtx, rtx, int, int);
  
*************** adjust_offset_for_component_ref (tree x,
*** 1943,1948 ****
--- 1944,1973 ----
    return GEN_INT (ioffset);
  }
  
+ /* Iff EXPRX is a non-addressed variable in function scope, or a component
+    of one, return that variable.  */
+ static tree
+ non_addressed_function_scope_var (tree exprx)
+ {
+   if (exprx)
+     {
+       while (TREE_CODE (exprx) == COMPONENT_REF)
+ 	{
+ 	  exprx = TREE_OPERAND (exprx, 0);
+ 	  /* component_ref_for_mem_expr will just put NULL_RTX into argument
+ 	     0 of a COMPONENT_REF if it doesn't have a declaration.  */
+ 	  if (! exprx)
+ 	    return 0;
+ 	}
+       if (TREE_CODE (exprx) == VAR_DECL
+ 	  && TREE_STATIC (exprx)
+ 	  && ! TREE_ADDRESSABLE (exprx)
+ 	  && decl_function_context (exprx) != 0)
+ 	return exprx;
+     }
+   return 0;
+ }
+ 
  /* Return nonzero if we can determine the exprs corresponding to memrefs
     X and Y and they do not overlap.  */
  
*************** nonoverlapping_memrefs_p (rtx x, rtx y)
*** 1958,1963 ****
--- 1983,1999 ----
    /* Unless both have exprs, we can't tell anything.  */
    if (exprx == 0 || expry == 0)
      return 0;
+ 
+   /* If one is a (part of) a variable that doesn't have its address taken,
+      and the other is not (part of) the same variable, they can't alias.
+      In particular, this test covers the case where one expression is
+      such a variable, and the other is an unspecified indirect_ref as
+      we commonly generate for C language family array accesses.  */
+   if (exprx != expry
+       && (non_addressed_function_scope_var (exprx) !=
+ 	  non_addressed_function_scope_var (expry)))
+ 
+     return 1;
  
    /* If both are field references, we may be able to determine something.  */
    if (TREE_CODE (exprx) == COMPONENT_REF
Index: emit-rtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/emit-rtl.c,v
retrieving revision 1.380
diff -p -r1.380 emit-rtl.c
*** emit-rtl.c	14 Feb 2004 18:45:41 -0000	1.380
--- emit-rtl.c	19 Feb 2004 18:09:31 -0000
*************** set_mem_attributes_minus_bitpos (rtx ref
*** 1651,1656 ****
--- 1651,1664 ----
  	  expr = t;
  	  offset = NULL;
  	}
+       /* If it is any other kind of indirect reference, just note the
+ 	 fact that it is - i.e. it can't alias a variable which never
+ 	 has its address taken.  */
+       else if (TREE_CODE (t) == INDIRECT_REF)
+ 	{
+ 	  expr = unspecified_indirect_ref_node;
+ 	  offset = NULL;
+ 	}
      }
  
    /* If we modified OFFSET based on T, then subtract the outstanding
Index: print-rtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/print-rtl.c,v
retrieving revision 1.106
diff -p -r1.106 print-rtl.c
*** print-rtl.c	7 Feb 2004 14:14:51 -0000	1.106
--- print-rtl.c	19 Feb 2004 18:09:31 -0000
*************** print_mem_expr (FILE *outfile, tree expr
*** 79,85 ****
    else if (TREE_CODE (expr) == INDIRECT_REF)
      {
        fputs (" (*", outfile);
!       print_mem_expr (outfile, TREE_OPERAND (expr, 0));
        fputs (")", outfile);
      }
    else if (DECL_NAME (expr))
--- 79,91 ----
    else if (TREE_CODE (expr) == INDIRECT_REF)
      {
        fputs (" (*", outfile);
!       /* We can't do a pointer-comparison to unspecified_indirect_ref_node
! 	 here because genflags doesn't have the global_trees array, but
! 	 links with print-rtl.o .  */
!       if (TREE_OPERAND (expr, 0) == NULL_TREE)
! 	fputs (" <anonymous>", outfile);
!       else
! 	print_mem_expr (outfile, TREE_OPERAND (expr, 0));
        fputs (")", outfile);
      }
    else if (DECL_NAME (expr))
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.347
diff -p -r1.347 tree.c
*** tree.c	11 Feb 2004 01:55:28 -0000	1.347
--- tree.c	19 Feb 2004 18:09:32 -0000
*************** build_common_tree_nodes (int signed_char
*** 4859,4864 ****
--- 4859,4867 ----
    error_mark_node = make_node (ERROR_MARK);
    TREE_TYPE (error_mark_node) = error_mark_node;
  
+   unspecified_indirect_ref_node = make_node (INDIRECT_REF);
+   TREE_TYPE (unspecified_indirect_ref_node) = error_mark_node;
+ 
    initialize_sizetypes ();
  
    /* Define both `signed char' and `unsigned char'.  */
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.468
diff -p -r1.468 tree.h
*** tree.h	17 Feb 2004 21:33:34 -0000	1.468
--- tree.h	19 Feb 2004 18:09:34 -0000
*************** union tree_node GTY ((ptr_alias (union l
*** 1793,1798 ****
--- 1793,1799 ----
  enum tree_index
  {
    TI_ERROR_MARK,
+   TI_UNSPEC_IND_REF,
    TI_INTQI_TYPE,
    TI_INTHI_TYPE,
    TI_INTSI_TYPE,
*************** enum tree_index
*** 1883,1888 ****
--- 1884,1890 ----
  extern GTY(()) tree global_trees[TI_MAX];
  
  #define error_mark_node			global_trees[TI_ERROR_MARK]
+ #define unspecified_indirect_ref_node	global_trees[TI_UNSPEC_IND_REF]
  
  #define intQI_type_node			global_trees[TI_INTQI_TYPE]
  #define intHI_type_node			global_trees[TI_INTHI_TYPE]