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.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@102098 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 228 insertions, 0 deletions

diff --git a/gcc/ipa-utils.c b/gcc/ipa-utils.c
new file mode 100644
index 00000000000..b758031adbe
--- /dev/null
+++ b/gcc/ipa-utils.c
@@ -0,0 +1,228 @@
+/* Utilities for ipa analysis.
+   Copyright (C) 2005 Free Software Foundation, Inc.
+   Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "tree-flow.h"
+#include "tree-inline.h"
+#include "tree-pass.h"
+#include "langhooks.h"
+#include "pointer-set.h"
+#include "ggc.h"
+#include "ipa-utils.h"
+#include "ipa-reference.h"
+#include "c-common.h"
+#include "tree-gimple.h"
+#include "cgraph.h"
+#include "output.h"
+#include "flags.h"
+#include "timevar.h"
+#include "diagnostic.h"
+#include "langhooks.h"
+
+/* Debugging function for postorder and inorder code. NOTE is a string
+   that is printed before the nodes are printed.  ORDER is an array of
+   cgraph_nodes that has COUNT useful nodes in it.  */
+
+void 
+ipa_utils_print_order (FILE* out, 
+		       const char * note, 
+		       struct cgraph_node** order, 
+		       int count) 
+{
+  int i;
+  fprintf (out, "\n\n ordered call graph: %s\n", note);
+  
+  for (i = count - 1; i >= 0; i--)
+    dump_cgraph_node(dump_file, order[i]);
+  fprintf (out, "\n");
+  fflush(out);
+}
+
+
+struct searchc_env {
+  struct cgraph_node **stack;
+  int stack_size;
+  struct cgraph_node **result;
+  int order_pos;
+  splay_tree nodes_marked_new;
+  bool reduce;
+  int count;
+};
+
+/* This is an implementation of Tarjan's strongly connected region
+   finder as reprinted in Aho Hopcraft and Ullman's The Design and
+   Analysis of Computer Programs (1975) pages 192-193.  This version
+   has been customized for cgraph_nodes.  The env parameter is because
+   it is recursive and there are no nested functions here.  This
+   function should only be called from itself or
+   cgraph_reduced_inorder.  ENV is a stack env and would be
+   unnecessary if C had nested functions.  V is the node to start
+   searching from.  */
+
+static void
+searchc (struct searchc_env* env, struct cgraph_node *v) 
+{
+  struct cgraph_edge *edge;
+  struct ipa_dfs_info *v_info = v->aux;
+  
+  /* mark node as old */
+  v_info->new = false;
+  splay_tree_remove (env->nodes_marked_new, v->uid);
+  
+  v_info->dfn_number = env->count;
+  v_info->low_link = env->count;
+  env->count++;
+  env->stack[(env->stack_size)++] = v;
+  v_info->on_stack = true;
+  
+  for (edge = v->callees; edge; edge = edge->next_callee)
+    {
+      struct ipa_dfs_info * w_info;
+      struct cgraph_node *w = edge->callee;
+      /* Bypass the clones and only look at the master node.  Skip
+	 external and other bogus nodes.  */
+      w = cgraph_master_clone (w);
+      if (w && w->aux) 
+	{
+	  w_info = w->aux;
+	  if (w_info->new) 
+	    {
+	      searchc (env, w);
+	      v_info->low_link =
+		(v_info->low_link < w_info->low_link) ?
+		v_info->low_link : w_info->low_link;
+	    } 
+	  else 
+	    if ((w_info->dfn_number < v_info->dfn_number) 
+		&& (w_info->on_stack)) 
+	      v_info->low_link =
+		(w_info->dfn_number < v_info->low_link) ?
+		w_info->dfn_number : v_info->low_link;
+	}
+    }
+
+
+  if (v_info->low_link == v_info->dfn_number) 
+    {
+      struct cgraph_node *last = NULL;
+      struct cgraph_node *x;
+      struct ipa_dfs_info *x_info;
+      do {
+	x = env->stack[--(env->stack_size)];
+	x_info = x->aux;
+	x_info->on_stack = false;
+	
+	if (env->reduce) 
+	  {
+	    x_info->next_cycle = last;
+	    last = x;
+	  } 
+	else 
+	  env->result[env->order_pos++] = x;
+      } 
+      while (v != x);
+      if (env->reduce) 
+	env->result[env->order_pos++] = v;
+    }
+}
+
+/* Topsort the call graph by caller relation.  Put the result in ORDER.
+
+   The REDUCE flag is true if you want the cycles reduced to single
+   nodes.  Only consider nodes that have the output bit set. */
+
+int
+ipa_utils_reduced_inorder (struct cgraph_node **order, 
+			   bool reduce, bool allow_overwritable)
+{
+  struct cgraph_node *node;
+  struct searchc_env env;
+  splay_tree_node result;
+  env.stack = xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
+  env.stack_size = 0;
+  env.result = order;
+  env.order_pos = 0;
+  env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
+  env.count = 1;
+  env.reduce = reduce;
+  
+  for (node = cgraph_nodes; node; node = node->next) 
+    if ((node->analyzed)
+	&& (cgraph_is_master_clone (node) 
+	 || (allow_overwritable 
+	     && (cgraph_function_body_availability (node) == 
+		 AVAIL_OVERWRITABLE))))
+      {
+	/* Reuse the info if it is already there.  */
+	struct ipa_dfs_info *info = node->aux;
+	if (!info)
+	  info = xcalloc (1, sizeof (struct ipa_dfs_info));
+	info->new = true;
+	info->on_stack = false;
+	info->next_cycle = NULL;
+	node->aux = info;
+	
+	splay_tree_insert (env.nodes_marked_new,
+			   (splay_tree_key)node->uid, 
+			   (splay_tree_value)node);
+      } 
+    else 
+      node->aux = NULL;
+  result = splay_tree_min (env.nodes_marked_new);
+  while (result)
+    {
+      node = (struct cgraph_node *)result->value;
+      searchc (&env, node);
+      result = splay_tree_min (env.nodes_marked_new);
+    }
+  splay_tree_delete (env.nodes_marked_new);
+  free (env.stack);
+
+  return env.order_pos;
+}
+
+
+/* Given a memory reference T, will return the variable at the bottom
+   of the access.  Unlike get_base_address, this will recurse thru
+   INDIRECT_REFS.  */
+
+tree
+get_base_var (tree t)
+{
+  if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
+    return t;
+
+  while (!SSA_VAR_P (t) 
+	 && (!CONSTANT_CLASS_P (t))
+	 && TREE_CODE (t) != LABEL_DECL
+	 && TREE_CODE (t) != FUNCTION_DECL
+	 && TREE_CODE (t) != CONST_DECL)
+    {
+      t = TREE_OPERAND (t, 0);
+    }
+  return t;
+} 
+