***SPAM*** 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

Currently regtesting / bootstrapping for sh-elf and i686-pc-linux-gnu

2004-02-18  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.

	* alias.c (non_addressed_function_scope_var_p): New function.
	(nonoverlapping_memrefs_p): Use it.
	* rtlanal.c (may_trap_p): Check MEM_EXPR for evidence of a static
	variable access.

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	18 Feb 2004 18:00:46 -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 (exprx != expry
+       && (non_addressed_function_scope_var (exprx) !=
+ 	  non_addressed_function_scope_var (expry))
+       /* (mem:BLK (const_int 0 [0x0]) [0 A8]) is used as a wildcard,
+          when scan_loop detects that there is a non-pure function call -
+          which might cause recursion.  */
+       && XEXP (x, 0) != const0_rtx
+       && XEXP (y, 0) != const0_rtx)
+ 
+     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	18 Feb 2004 18:00:47 -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: 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	18 Feb 2004 18:00:48 -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	18 Feb 2004 18:00:48 -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]