Makefile.in: Added rules for ipa-pure-const.c...

2005-07-16  Danny Berlin <dberlin@dberlin.org>
	    Kenneth Zadeck <zadeck@naturalbridge.com>

	* Makefile.in: Added rules for ipa-pure-const.c, ipa-reference.c,
	ipa-reference.h, ipa-utils.c, ipa-utils.h, ipa-type-escape.c,
	ipa-type-escape.h, tree-promote-statics.c
	* ipa-pure-const.c, ipa-reference.c, ipa-reference.h, ipa-utils.c,
	ipa-utils.h, ipa-type-escape.c, ipa-type-escape.h,
	tree-promote-statics.c: new files.
	* alias.c: (nonlocal_mentioned_p_1, nonlocal_mentioned_p,
	nonlocal_referenced_p_1, nonlocal_referenced_p, nonlocal_set_p_1,
	int nonlocal_set_p, mark_constant_function): Deleted.
	(rest_of_handle_cfg): Removed call to mark_constant_function.
        (nonoverlapping_component_refs_p): Added calls to support
	type based aliasing.
        * tree-ssa-alias.c (may_alias_p,
	compute_flow_insensitive_aliasing): Ditto.
	* calls.c (flags_from_decl_or_type): Removed reference to
	cgraph_rtl_info.
	(flags_from_decl_or_type): Support ECF_POINTER_NO_CAPTURE attribute.
	* c-common.c (handle_pointer_no_capture_attribute): New function
	and added pointer_no_capture attribute.
      	* c-typeck.c (convert_arguments): Make builtins tolerant of having
	too many arguments.  This is necessary for Spec 2000.
	* cgraph.h (const_function, pure_function): Removed.
	* common.opt: Added "fipa-pure-const", "fipa-reference",
	"fipa-type-escape", and "ftree-promote-static".
	* opts.c: Ditto.
	* passes.c: Added ipa and tree-promote-statics passes.
	* timevar.def: Added TV_IPA_PURE_CONST, TV_IPA_REFERENCE,
	TV_IPA_TYPE_ESCAPE, and TV_PROMOTE_STATICS.
	* tree.h: Support ECF_POINTER_NO_CAPTURE attribute.
	* tree-dfa.c (referenced_var_lookup_if_exists): New function.
	* tree-flow.h: Added exposed sra calls and addition of
	reference_vars_info field for FUNCTION_DECLS.
	* tree-pass.h: Added passes.
	* tree-sra.c: (sra_init_cache): New function.
	(sra_insert_before, sra_insert_after) Made public.
	(type_can_be_decomposed_p): Renamed from type_can_be_decomposed_p
	and made public.
	* tree-ssa-alias.c (dump_alias_stats): Added stats for type based
	aliasing. (may_alias_p): Added code to use type escape analysis to
	improve alias sets.
	* tree-ssa-operands.c (add_call_clobber_ops): Added parameter and
	code to prune clobbers of static variables based on information
	produced in ipa-reference pass.  Changed call clobbering so that
	statics are not marked as clobbered if the call does not clobber
	them.


2005-07-16  Danny Berlin <dberlin@dberlin.org>
	    Kenneth Zadeck <zadeck@naturalbridge.com>

	* gcc.dg/tree-ssa/ssa-dce-2.c: Changed dg-options to run at -O2
	since pure const detection cannot run at -O1 in c compiler.
	* gcc.dg/tree-ssa/20030714-1.c Changed scanning patterns because we
	can now optimize this case properly.
	* gcc.dg/tree-ssa/sra-2.c: Changed to -O3 and removed xfail
	because we now pass.
	* gcc.dg/vect/vect-92.c: Removed out of bounds array access.

Co-Authored-By: Kenneth Zadeck <zadeck@naturalbridge.com>

From-SVN: r102098

1 files changed, 87 insertions, 388 deletions

diff --git a/gcc/alias.c b/gcc/alias.c
index 9bc11d7..cdbb94d 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -45,6 +45,58 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "cgraph.h"
 #include "varray.h"
 #include "tree-pass.h"
+#include "ipa-type-escape.h"
+
+/* The aliasing API provided here solves related but different problems:
+
+   Say there exists (in c) 
+
+   struct X {
+     struct Y y1;
+     struct Z z2;
+   } x1, *px1,  *px2;
+
+   struct Y y2, *py;
+   struct Z z2, *pz;
+
+
+   py = &px1.y1;
+   px2 = &x1;
+
+   Consider the four questions:
+
+   Can a store to x1 interfere with px2->y1?
+   Can a store to x1 interfere with px2->z2?
+   (*px2).z2
+   Can a store to x1 change the value pointed to by with py?
+   Can a store to x1 change the value pointed to by with pz?
+
+   The answer to these questions can be yes, yes, yes, and maybe.
+
+   The first two questions can be answered with a simple examination
+   of the type system.  If structure X contains a field of type Y then
+   a store thru a pointer to an X can overwrite any field that is
+   contained (recursively) in an X (unless we know that px1 != px2).
+
+   The last two of the questions can be solved in the same way as the
+   first two questions but this is too conservative.  The observation
+   is that in some cases analysis we can know if which (if any) fields
+   are addressed and if those addresses are used in bad ways.  This
+   analysis may be language specific.  In C, arbitrary operations may
+   be applied to pointers.  However, there is some indication that
+   this may be too conservative for some C++ types.
+
+   The pass ipa-type-escape does this analysis for the types whose
+   instances do not escape across the compilation boundary.  
+
+   Historically in GCC, these two problems were combined and a single
+   data structure was used to represent the solution to these
+   problems.  We now have two similar but different data structures,
+   The data structure to solve the last two question is similar to the
+   first, but does not contain have the fields in it whose address are
+   never taken.  For types that do escape the compilation unit, the
+   data structures will have identical information.
+*/
 
 /* The alias sets assigned to MEMs assist the back-end in determining
    which MEMs can alias which other MEMs.  In general, two MEMs in
@@ -116,12 +168,6 @@ static rtx adjust_offset_for_component_ref (tree, rtx);
 static int nonoverlapping_memrefs_p (rtx, rtx);
 static int write_dependence_p (rtx, rtx, int);
 
-static int nonlocal_mentioned_p_1 (rtx *, void *);
-static int nonlocal_mentioned_p (rtx);
-static int nonlocal_referenced_p_1 (rtx *, void *);
-static int nonlocal_referenced_p (rtx);
-static int nonlocal_set_p_1 (rtx *, void *);
-static int nonlocal_set_p (rtx);
 static void memory_modified_1 (rtx, rtx, void *);
 static void record_alias_subset (HOST_WIDE_INT, HOST_WIDE_INT);
 
@@ -1924,9 +1970,8 @@ nonoverlapping_component_refs_p (tree x, tree y)
 	  x = TREE_OPERAND (x, 0);
 	}
       while (x && TREE_CODE (x) == COMPONENT_REF);
-
       /* Never found a common type.  */
-      return false;
+      return true;
 
     found:
       /* If we're left with accessing different fields of a structure,
@@ -2006,22 +2051,34 @@ nonoverlapping_memrefs_p (rtx x, rtx y)
   /* Unless both have exprs, we can't tell anything.  */
   if (exprx == 0 || expry == 0)
     return 0;
-
+  
   /* If both are field references, we may be able to determine something.  */
   if (TREE_CODE (exprx) == COMPONENT_REF
       && TREE_CODE (expry) == COMPONENT_REF
       && nonoverlapping_component_refs_p (exprx, expry))
     return 1;
 
+  
   /* If the field reference test failed, look at the DECLs involved.  */
   moffsetx = MEM_OFFSET (x);
   if (TREE_CODE (exprx) == COMPONENT_REF)
     {
-      tree t = decl_for_component_ref (exprx);
-      if (! t)
-	return 0;
-      moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
-      exprx = t;
+      if (TREE_CODE (expry) == VAR_DECL
+	  && POINTER_TYPE_P (TREE_TYPE (expry)))
+	{
+	 tree field = TREE_OPERAND (exprx, 1);
+	 tree fieldcontext = DECL_FIELD_CONTEXT (field);
+	 if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
+						       TREE_TYPE (field)))
+	   return 1;	 
+	}
+      {
+	tree t = decl_for_component_ref (exprx);
+	if (! t)
+	  return 0;
+	moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
+	exprx = t;
+      }
     }
   else if (INDIRECT_REF_P (exprx))
     {
@@ -2034,11 +2091,22 @@ nonoverlapping_memrefs_p (rtx x, rtx y)
   moffsety = MEM_OFFSET (y);
   if (TREE_CODE (expry) == COMPONENT_REF)
     {
-      tree t = decl_for_component_ref (expry);
-      if (! t)
-	return 0;
-      moffsety = adjust_offset_for_component_ref (expry, moffsety);
-      expry = t;
+      if (TREE_CODE (exprx) == VAR_DECL
+	  && POINTER_TYPE_P (TREE_TYPE (exprx)))
+	{
+	 tree field = TREE_OPERAND (expry, 1);
+	 tree fieldcontext = DECL_FIELD_CONTEXT (field);
+	 if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
+						       TREE_TYPE (field)))
+	   return 1;	 
+	}
+      {
+	tree t = decl_for_component_ref (expry);
+	if (! t)
+	  return 0;
+	moffsety = adjust_offset_for_component_ref (expry, moffsety);
+	expry = t;
+      }
     }
   else if (INDIRECT_REF_P (expry))
     {
@@ -2326,353 +2394,6 @@ output_dependence (rtx mem, rtx x)
   return write_dependence_p (mem, x, /*writep=*/1);
 }
 
-/* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions
-   something which is not local to the function and is not constant.  */
-
-static int
-nonlocal_mentioned_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
-{
-  rtx x = *loc;
-  rtx base;
-  int regno;
-
-  if (! x)
-    return 0;
-
-  switch (GET_CODE (x))
-    {
-    case SUBREG:
-      if (REG_P (SUBREG_REG (x)))
-	{
-	  /* Global registers are not local.  */
-	  if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
-	      && global_regs[subreg_regno (x)])
-	    return 1;
-	  return 0;
-	}
-      break;
-
-    case REG:
-      regno = REGNO (x);
-      /* Global registers are not local.  */
-      if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
-	return 1;
-      return 0;
-
-    case SCRATCH:
-    case PC:
-    case CC0:
-    case CONST_INT:
-    case CONST_DOUBLE:
-    case CONST_VECTOR:
-    case CONST:
-    case LABEL_REF:
-      return 0;
-
-    case SYMBOL_REF:
-      /* Constants in the function's constants pool are constant.  */
-      if (CONSTANT_POOL_ADDRESS_P (x))
-	return 0;
-      return 1;
-
-    case CALL:
-      /* Non-constant calls and recursion are not local.  */
-      return 1;
-
-    case MEM:
-      /* Be overly conservative and consider any volatile memory
-	 reference as not local.  */
-      if (MEM_VOLATILE_P (x))
-	return 1;
-      base = find_base_term (XEXP (x, 0));
-      if (base)
-	{
-	  /* A Pmode ADDRESS could be a reference via the structure value
-	     address or static chain.  Such memory references are nonlocal.
-
-	     Thus, we have to examine the contents of the ADDRESS to find
-	     out if this is a local reference or not.  */
-	  if (GET_CODE (base) == ADDRESS
-	      && GET_MODE (base) == Pmode
-	      && (XEXP (base, 0) == stack_pointer_rtx
-		  || XEXP (base, 0) == arg_pointer_rtx
-#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
-		  || XEXP (base, 0) == hard_frame_pointer_rtx
-#endif
-		  || XEXP (base, 0) == frame_pointer_rtx))
-	    return 0;
-	  /* Constants in the function's constant pool are constant.  */
-	  if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base))
-	    return 0;
-	}
-      return 1;
-
-    case UNSPEC_VOLATILE:
-    case ASM_INPUT:
-      return 1;
-
-    case ASM_OPERANDS:
-      if (MEM_VOLATILE_P (x))
-	return 1;
-
-    /* Fall through.  */
-
-    default:
-      break;
-    }
-
-  return 0;
-}
-
-/* Returns nonzero if X might mention something which is not
-   local to the function and is not constant.  */
-
-static int
-nonlocal_mentioned_p (rtx x)
-{
-  if (INSN_P (x))
-    {
-      if (CALL_P (x))
-	{
-	  if (! CONST_OR_PURE_CALL_P (x))
-	    return 1;
-	  x = CALL_INSN_FUNCTION_USAGE (x);
-	  if (x == 0)
-	    return 0;
-	}
-      else
-	x = PATTERN (x);
-    }
-
-  return for_each_rtx (&x, nonlocal_mentioned_p_1, NULL);
-}
-
-/* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references
-   something which is not local to the function and is not constant.  */
-
-static int
-nonlocal_referenced_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
-{
-  rtx x = *loc;
-
-  if (! x)
-    return 0;
-
-  switch (GET_CODE (x))
-    {
-    case MEM:
-    case REG:
-    case SYMBOL_REF:
-    case SUBREG:
-      return nonlocal_mentioned_p (x);
-
-    case CALL:
-      /* Non-constant calls and recursion are not local.  */
-      return 1;
-
-    case SET:
-      if (nonlocal_mentioned_p (SET_SRC (x)))
-	return 1;
-
-      if (MEM_P (SET_DEST (x)))
-	return nonlocal_mentioned_p (XEXP (SET_DEST (x), 0));
-
-      /* If the destination is anything other than a CC0, PC,
-	 MEM, REG, or a SUBREG of a REG that occupies all of
-	 the REG, then X references nonlocal memory if it is
-	 mentioned in the destination.  */
-      if (GET_CODE (SET_DEST (x)) != CC0
-	  && GET_CODE (SET_DEST (x)) != PC
-	  && !REG_P (SET_DEST (x))
-	  && ! (GET_CODE (SET_DEST (x)) == SUBREG
-		&& REG_P (SUBREG_REG (SET_DEST (x)))
-		&& (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x))))
-		      + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
-		    == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x)))
-			 + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD))))
-	return nonlocal_mentioned_p (SET_DEST (x));
-      return 0;
-
-    case CLOBBER:
-      if (MEM_P (XEXP (x, 0)))
-	return nonlocal_mentioned_p (XEXP (XEXP (x, 0), 0));
-      return 0;
-
-    case USE:
-      return nonlocal_mentioned_p (XEXP (x, 0));
-
-    case ASM_INPUT:
-    case UNSPEC_VOLATILE:
-      return 1;
-
-    case ASM_OPERANDS:
-      if (MEM_VOLATILE_P (x))
-	return 1;
-
-    /* Fall through.  */
-
-    default:
-      break;
-    }
-
-  return 0;
-}
-
-/* Returns nonzero if X might reference something which is not
-   local to the function and is not constant.  */
-
-static int
-nonlocal_referenced_p (rtx x)
-{
-  if (INSN_P (x))
-    {
-      if (CALL_P (x))
-	{
-	  if (! CONST_OR_PURE_CALL_P (x))
-	    return 1;
-	  x = CALL_INSN_FUNCTION_USAGE (x);
-	  if (x == 0)
-	    return 0;
-	}
-      else
-	x = PATTERN (x);
-    }
-
-  return for_each_rtx (&x, nonlocal_referenced_p_1, NULL);
-}
-
-/* A subroutine of nonlocal_set_p, returns 1 if *LOC sets
-   something which is not local to the function and is not constant.  */
-
-static int
-nonlocal_set_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
-{
-  rtx x = *loc;
-
-  if (! x)
-    return 0;
-
-  switch (GET_CODE (x))
-    {
-    case CALL:
-      /* Non-constant calls and recursion are not local.  */
-      return 1;
-
-    case PRE_INC:
-    case PRE_DEC:
-    case POST_INC:
-    case POST_DEC:
-    case PRE_MODIFY:
-    case POST_MODIFY:
-      return nonlocal_mentioned_p (XEXP (x, 0));
-
-    case SET:
-      if (nonlocal_mentioned_p (SET_DEST (x)))
-	return 1;
-      return nonlocal_set_p (SET_SRC (x));
-
-    case CLOBBER:
-      return nonlocal_mentioned_p (XEXP (x, 0));
-
-    case USE:
-      return 0;
-
-    case ASM_INPUT:
-    case UNSPEC_VOLATILE:
-      return 1;
-
-    case ASM_OPERANDS:
-      if (MEM_VOLATILE_P (x))
-	return 1;
-
-    /* Fall through.  */
-
-    default:
-      break;
-    }
-
-  return 0;
-}
-
-/* Returns nonzero if X might set something which is not
-   local to the function and is not constant.  */
-
-static int
-nonlocal_set_p (rtx x)
-{
-  if (INSN_P (x))
-    {
-      if (CALL_P (x))
-	{
-	  if (! CONST_OR_PURE_CALL_P (x))
-	    return 1;
-	  x = CALL_INSN_FUNCTION_USAGE (x);
-	  if (x == 0)
-	    return 0;
-	}
-      else
-	x = PATTERN (x);
-    }
-
-  return for_each_rtx (&x, nonlocal_set_p_1, NULL);
-}
-
-/* Mark the function if it is pure or constant.  */
-
-void
-mark_constant_function (void)
-{
-  rtx insn;
-  int nonlocal_memory_referenced;
-
-  if (TREE_READONLY (current_function_decl)
-      || DECL_IS_PURE (current_function_decl)
-      || TREE_THIS_VOLATILE (current_function_decl)
-      || current_function_has_nonlocal_goto
-      || !targetm.binds_local_p (current_function_decl))
-    return;
-
-  /* A loop might not return which counts as a side effect.  */
-  if (mark_dfs_back_edges ())
-    return;
-
-  nonlocal_memory_referenced = 0;
-
-  init_alias_analysis ();
-
-  /* Determine if this is a constant or pure function.  */
-
-  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
-    {
-      if (! INSN_P (insn))
-	continue;
-
-      if (nonlocal_set_p (insn) || global_reg_mentioned_p (insn)
-	  || volatile_refs_p (PATTERN (insn)))
-	break;
-
-      if (! nonlocal_memory_referenced)
-	nonlocal_memory_referenced = nonlocal_referenced_p (insn);
-    }
-
-  end_alias_analysis ();
-
-  /* Mark the function.  */
-
-  if (insn)
-    ;
-  else if (nonlocal_memory_referenced)
-    {
-      cgraph_rtl_info (current_function_decl)->pure_function = 1;
-      DECL_IS_PURE (current_function_decl) = 1;
-    }
-  else
-    {
-      cgraph_rtl_info (current_function_decl)->const_function = 1;
-      TREE_READONLY (current_function_decl) = 1;
-    }
-}
-
 
 void
 init_alias_once (void)
@@ -2979,28 +2700,6 @@ rest_of_handle_cfg (void)
   if (optimize)
     cleanup_cfg (CLEANUP_EXPENSIVE
                  | (flag_thread_jumps ? CLEANUP_THREADING : 0));
-
-  /* It may make more sense to mark constant functions after dead code is
-     eliminated by life_analysis, but we need to do it early, as -fprofile-arcs
-     may insert code making function non-constant, but we still must consider
-     it as constant, otherwise -fbranch-probabilities will not read data back.
-
-     life_analysis rarely eliminates modification of external memory.
-
-     FIXME: now with tree based profiling we are in the trap described above
-     again.  It seems to be easiest to disable the optimization for time
-     being before the problem is either solved by moving the transformation
-     to the IPA level (we need the CFG for this) or the very early optimization
-     passes are made to ignore the const/pure flags so code does not change.  */
-  if (optimize
-      && (!flag_tree_based_profiling
-          || (!profile_arc_flag && !flag_branch_probabilities)))
-    {
-      /* Alias analysis depends on this information and mark_constant_function
-       depends on alias analysis.  */
-      reg_scan (get_insns (), max_reg_num ());
-      mark_constant_function ();
-    }
 }
 
 struct tree_opt_pass pass_cfg =