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, 729 insertions, 0 deletions

diff --git a/gcc/ipa-pure-const.c b/gcc/ipa-pure-const.c
new file mode 100644
index 00000000000..1402607aa8b
--- /dev/null
+++ b/gcc/ipa-pure-const.c
@@ -0,0 +1,729 @@
+/* Callgraph based analysis of static variables.
+   Copyright (C) 2004, 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.  */
+
+/* This file mark functions as being either const (TREE_READONLY) or
+   pure (DECL_IS_PURE).
+
+   This must be run after inlining decisions have been made since
+   otherwise, the local sets will not contain information that is
+   consistent with post inlined state.  The global sets are not prone
+   to this problem since they are by definition transitive.  */
+
+/* The code in this module is called by the ipa pass manager. It
+   should be one of the later passes since it's information is used by
+   the rest of the compilation. */
+
+#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 "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"
+
+static struct pointer_set_t *visited_nodes;
+
+/* Lattice values for const and pure functions.  Everything starts out
+   being const, then may drop to pure and then neither depending on
+   what is found.  */
+enum pure_const_state_e
+{
+  IPA_CONST,
+  IPA_PURE,
+  IPA_NEITHER
+};
+
+/* Holder inserted into the ipa_dfs_info aux field to hold the
+   const_state.  */
+struct funct_state_d 
+{
+  enum pure_const_state_e pure_const_state;
+  bool state_set_in_source;
+};
+
+typedef struct funct_state_d * funct_state;
+
+/* Return the function state from NODE.  */ 
+
+static inline funct_state
+get_function_state (struct cgraph_node *node)
+{
+  struct ipa_dfs_info * info = node->aux;
+  return info->aux;
+}
+
+/* Check to see if the use (or definition when CHECHING_WRITE is true) 
+   variable T is legal in a function that is either pure or const.  */
+
+static inline void 
+check_decl (funct_state local, 
+	    tree t, bool checking_write)
+{
+  /* If the variable has the "used" attribute, treat it as if it had a
+     been touched by the devil.  */
+  if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
+    {
+      local->pure_const_state = IPA_NEITHER;
+      return;
+    }
+
+  /* Do not want to do anything with volatile except mark any
+     function that uses one to be not const or pure.  */
+  if (TREE_THIS_VOLATILE (t)) 
+    { 
+      local->pure_const_state = IPA_NEITHER;
+      return;
+    }
+
+  /* Do not care about a local automatic that is not static.  */
+  if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
+    return;
+
+  /* Since we have dealt with the locals and params cases above, if we
+     are CHECKING_WRITE, this cannot be a pure or constant
+     function.  */
+  if (checking_write) 
+    local->pure_const_state = IPA_NEITHER;
+
+  if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
+    {
+      /* If the front end set the variable to be READONLY and
+	 constant, we can allow this variable in pure or const
+	 functions but the scope is too large for our analysis to set
+	 these bits ourselves.  */
+      
+      if (TREE_READONLY (t)
+	  && DECL_INITIAL (t)
+	  && is_gimple_min_invariant (DECL_INITIAL (t)))
+	; /* Read of a constant, do not change the function state.  */
+      else 
+	{
+	  /* Just a regular read.  */
+	  if (local->pure_const_state == IPA_CONST)
+	    local->pure_const_state = IPA_PURE;
+	}
+    }
+  
+  /* Compilation level statics can be read if they are readonly
+     variables.  */
+  if (TREE_READONLY (t))
+    return;
+
+  /* Just a regular read.  */
+  if (local->pure_const_state == IPA_CONST)
+    local->pure_const_state = IPA_PURE;
+}
+
+/* If T is a VAR_DECL check to see if it is an allowed reference.  */
+
+static void
+check_operand (funct_state local, 
+	       tree t, bool checking_write)
+{
+  if (!t) return;
+
+  if (TREE_CODE (t) == VAR_DECL)
+    check_decl (local, t, checking_write); 
+}
+
+/* Examine tree T for references.  */
+
+static void
+check_tree (funct_state local, tree t, bool checking_write)
+{
+  if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
+    return;
+
+  while (TREE_CODE (t) == REALPART_EXPR 
+	 || TREE_CODE (t) == IMAGPART_EXPR
+	 || handled_component_p (t))
+    {
+      if (TREE_CODE (t) == ARRAY_REF)
+	check_operand (local, TREE_OPERAND (t, 1), false);
+      t = TREE_OPERAND (t, 0);
+    }
+
+  /* The bottom of an indirect reference can only be read, not
+     written.  */
+  if (INDIRECT_REF_P (t))
+    {
+      check_tree (local, TREE_OPERAND (t, 0), false);
+      
+      /* Any indirect reference that occurs on the lhs
+	 disqualifies the function from being pure or const. Any
+	 indirect reference that occurs on the rhs disqualifies
+	 the function from being const.  */
+      if (checking_write) 
+	local->pure_const_state = IPA_NEITHER;
+      else 
+	if (local->pure_const_state == IPA_CONST)
+	  local->pure_const_state = IPA_PURE;
+    }
+
+  if (SSA_VAR_P (t))
+    check_operand (local, t, checking_write);
+}
+
+/* Scan tree T to see if there are any addresses taken in within T.  */
+
+static void 
+look_for_address_of (funct_state local, tree t)
+{
+  if (TREE_CODE (t) == ADDR_EXPR)
+    {
+      tree x = get_base_var (t);
+      if (TREE_CODE (x) == VAR_DECL) 
+	{
+	  check_decl (local, x, false);
+	  
+	  /* Taking the address of something appears to be reasonable
+	     in PURE code.  Not allowed in const.  */
+	  if (local->pure_const_state == IPA_CONST)
+	    local->pure_const_state = IPA_PURE;
+	}
+    }
+}
+
+/* Check to see if T is a read or address of operation on a var we are
+   interested in analyzing.  LOCAL is passed in to get access to its
+   bit vectors.  */
+
+static void
+check_rhs_var (funct_state local, tree t)
+{
+  look_for_address_of (local, t);
+
+  /* Memcmp and strlen can both trap and they are declared pure.  */
+  if (tree_could_trap_p (t)
+      && local->pure_const_state == IPA_CONST)
+    local->pure_const_state = IPA_PURE;
+
+  check_tree(local, t, false);
+}
+
+/* Check to see if T is an assignment to a var we are interested in
+   analyzing.  LOCAL is passed in to get access to its bit vectors. */
+
+static void
+check_lhs_var (funct_state local, tree t)
+{
+  /* Memcmp and strlen can both trap and they are declared pure.
+     Which seems to imply that we can apply the same rule here.  */
+  if (tree_could_trap_p (t)
+      && local->pure_const_state == IPA_CONST)
+    local->pure_const_state = IPA_PURE;
+    
+  check_tree(local, t, true);
+}
+
+/* This is a scaled down version of get_asm_expr_operands from
+   tree_ssa_operands.c.  The version there runs much later and assumes
+   that aliasing information is already available. Here we are just
+   trying to find if the set of inputs and outputs contain references
+   or address of operations to local static variables.  STMT is the
+   actual asm statement.  */
+
+static void
+get_asm_expr_operands (funct_state local, tree stmt)
+{
+  int noutputs = list_length (ASM_OUTPUTS (stmt));
+  const char **oconstraints
+    = (const char **) alloca ((noutputs) * sizeof (const char *));
+  int i;
+  tree link;
+  const char *constraint;
+  bool allows_mem, allows_reg, is_inout;
+  
+  for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link))
+    {
+      oconstraints[i] = constraint
+	= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
+      parse_output_constraint (&constraint, i, 0, 0,
+			       &allows_mem, &allows_reg, &is_inout);
+      
+      check_lhs_var (local, TREE_VALUE (link));
+    }
+
+  for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
+    {
+      constraint
+	= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
+      parse_input_constraint (&constraint, 0, 0, noutputs, 0,
+			      oconstraints, &allows_mem, &allows_reg);
+      
+      check_rhs_var (local, TREE_VALUE (link));
+    }
+  
+  for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
+    if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1) 
+      /* Abandon all hope, ye who enter here. */
+      local->pure_const_state = IPA_NEITHER;
+
+  if (ASM_VOLATILE_P (stmt))
+    local->pure_const_state = IPA_NEITHER;
+}
+
+/* Check the parameters of a function call to CALL_EXPR to see if
+   there are any references in the parameters that are not allowed for
+   pure or const functions.  Also check to see if this is either an
+   indirect call, a call outside the compilation unit, or has special
+   attributes that may also effect the purity.  The CALL_EXPR node for
+   the entire call expression.  */
+
+static void
+check_call (funct_state local, tree call_expr) 
+{
+  int flags = call_expr_flags(call_expr);
+  tree operand_list = TREE_OPERAND (call_expr, 1);
+  tree operand;
+  tree callee_t = get_callee_fndecl (call_expr);
+  struct cgraph_node* callee;
+  enum availability avail = AVAIL_NOT_AVAILABLE;
+
+  for (operand = operand_list;
+       operand != NULL_TREE;
+       operand = TREE_CHAIN (operand))
+    {
+      tree argument = TREE_VALUE (operand);
+      check_rhs_var (local, argument);
+    }
+  
+  /* The const and pure flags are set by a variety of places in the
+     compiler (including here).  If someone has already set the flags
+     for the callee, (such as for some of the builtins) we will use
+     them, otherwise we will compute our own information. 
+  
+     Const and pure functions have less clobber effects than other
+     functions so we process these first.  Otherwise if it is a call
+     outside the compilation unit or an indirect call we punt.  This
+     leaves local calls which will be processed by following the call
+     graph.  */  
+  if (callee_t)
+    {
+      callee = cgraph_node(callee_t);
+      avail = cgraph_function_body_availability (callee);
+
+      /* When bad things happen to bad functions, they cannot be const
+	 or pure.  */
+      if (setjmp_call_p (callee_t))
+	local->pure_const_state = IPA_NEITHER;
+
+      if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL)
+	switch (DECL_FUNCTION_CODE (callee_t))
+	  {
+	  case BUILT_IN_LONGJMP:
+	  case BUILT_IN_NONLOCAL_GOTO:
+	    local->pure_const_state = IPA_NEITHER;
+	    break;
+	  default:
+	    break;
+	  }
+    }
+
+  /* The callee is either unknown (indirect call) or there is just no
+     scannable code for it (external call) .  We look to see if there
+     are any bits available for the callee (such as by declaration or
+     because it is builtin) and process solely on the basis of those
+     bits. */
+  if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
+    {
+      if (flags & ECF_PURE) 
+	{
+	  if (local->pure_const_state == IPA_CONST)
+	    local->pure_const_state = IPA_PURE;
+	}
+      else 
+	local->pure_const_state = IPA_NEITHER;
+    }
+  else
+    {
+      /* We have the code and we will scan it for the effects. */
+      if (flags & ECF_PURE) 
+	{
+	  if (local->pure_const_state == IPA_CONST)
+	    local->pure_const_state = IPA_PURE;
+	}
+    }
+}
+
+/* TP is the part of the tree currently under the microscope.
+   WALK_SUBTREES is part of the walk_tree api but is unused here.
+   DATA is cgraph_node of the function being walked.  */
+
+/* FIXME: When this is converted to run over SSA form, this code
+   should be converted to use the operand scanner.  */
+
+static tree
+scan_function (tree *tp, 
+		      int *walk_subtrees, 
+		      void *data)
+{
+  struct cgraph_node *fn = data;
+  tree t = *tp;
+  funct_state local = get_function_state (fn);
+
+  switch (TREE_CODE (t))  
+    {
+    case VAR_DECL:
+      if (DECL_INITIAL (t))
+	walk_tree (&DECL_INITIAL (t), scan_function, fn, visited_nodes);
+      *walk_subtrees = 0;
+      break;
+
+    case MODIFY_EXPR:
+      {
+	/* First look on the lhs and see what variable is stored to */
+	tree lhs = TREE_OPERAND (t, 0);
+	tree rhs = TREE_OPERAND (t, 1);
+	check_lhs_var (local, lhs);
+
+	/* For the purposes of figuring out what the cast affects */
+
+	/* Next check the operands on the rhs to see if they are ok. */
+	switch (TREE_CODE_CLASS (TREE_CODE (rhs))) 
+	  {
+	  case tcc_binary:	    
+ 	    {
+ 	      tree op0 = TREE_OPERAND (rhs, 0);
+ 	      tree op1 = TREE_OPERAND (rhs, 1);
+ 	      check_rhs_var (local, op0);
+ 	      check_rhs_var (local, op1);
+	    }
+	    break;
+	  case tcc_unary:
+ 	    {
+ 	      tree op0 = TREE_OPERAND (rhs, 0);
+ 	      check_rhs_var (local, op0);
+ 	    }
+
+	    break;
+	  case tcc_reference:
+	    check_rhs_var (local, rhs);
+	    break;
+	  case tcc_declaration:
+	    check_rhs_var (local, rhs);
+	    break;
+	  case tcc_expression:
+	    switch (TREE_CODE (rhs)) 
+	      {
+	      case ADDR_EXPR:
+		check_rhs_var (local, rhs);
+		break;
+	      case CALL_EXPR: 
+		check_call (local, rhs);
+		break;
+	      default:
+		break;
+	      }
+	    break;
+	  default:
+	    break;
+	  }
+	*walk_subtrees = 0;
+      }
+      break;
+
+    case ADDR_EXPR:
+      /* This case is here to find addresses on rhs of constructors in
+	 decl_initial of static variables. */
+      check_rhs_var (local, t);
+      *walk_subtrees = 0;
+      break;
+
+    case LABEL_EXPR:
+      if (DECL_NONLOCAL (TREE_OPERAND (t, 0)))
+	/* Target of long jump. */
+	local->pure_const_state = IPA_NEITHER;
+      break;
+
+    case CALL_EXPR: 
+      check_call (local, t);
+      *walk_subtrees = 0;
+      break;
+      
+    case ASM_EXPR:
+      get_asm_expr_operands (local, t);
+      *walk_subtrees = 0;
+      break;
+      
+    default:
+      break;
+    }
+  return NULL;
+}
+
+/* This is the main routine for finding the reference patterns for
+   global variables within a function FN.  */
+
+static void
+analyze_function (struct cgraph_node *fn)
+{
+  funct_state l = xcalloc (1, sizeof (struct funct_state_d));
+  tree decl = fn->decl;
+  struct ipa_dfs_info * w_info = fn->aux;
+
+  w_info->aux = l;
+
+  l->pure_const_state = IPA_CONST;
+  l->state_set_in_source = false;
+
+  /* If this is a volatile function, do not touch this unless it has
+     been marked as const or pure by the front end.  */
+  if (TREE_THIS_VOLATILE (decl))
+    {
+      l->pure_const_state = IPA_NEITHER;
+      return;
+    }
+
+  if (TREE_READONLY (decl))
+    {
+      l->pure_const_state = IPA_CONST;
+      l->state_set_in_source = true;
+    }
+  if (DECL_IS_PURE (decl))
+    {
+      l->pure_const_state = IPA_PURE;
+      l->state_set_in_source = true;
+    }
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "\n local analysis of %s with initial value = %d\n ", 
+	       cgraph_node_name (fn),
+	       l->pure_const_state);
+    }
+  
+  if (!l->state_set_in_source)
+    {
+      struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
+      basic_block this_block;
+      
+      FOR_EACH_BB_FN (this_block, this_cfun)
+	{
+	  block_stmt_iterator bsi;
+	  for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
+	    {
+	      walk_tree (bsi_stmt_ptr (bsi), scan_function, 
+			 fn, visited_nodes);
+	      if (l->pure_const_state == IPA_NEITHER) 
+		return;
+	    }
+	}
+
+      if (l->pure_const_state != IPA_NEITHER)
+	{
+	  tree old_decl = current_function_decl;
+	  /* Const functions cannot have back edges (an
+	     indication of possible infinite loop side
+	     effect.  */
+	    
+	  current_function_decl = fn->decl;
+
+	  /* The C++ front end, has a tendency to some times jerk away
+	     a function after it has created it.  This should have
+	     been fixed.  */
+	  gcc_assert (DECL_STRUCT_FUNCTION (fn->decl));
+	  
+	  push_cfun (DECL_STRUCT_FUNCTION (fn->decl));
+	  
+	  if (mark_dfs_back_edges ())
+	    l->pure_const_state = IPA_NEITHER;
+	  
+	  current_function_decl = old_decl;
+	  pop_cfun ();
+	}
+    }
+}
+
+
+/* Produce the global information by preforming a transitive closure
+   on the local information that was produced by ipa_analyze_function
+   and ipa_analyze_variable.  */
+
+static void
+static_execute (void)
+{
+  struct cgraph_node *node;
+  struct cgraph_node *w;
+  struct cgraph_node **order =
+    xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
+  int order_pos = order_pos = ipa_utils_reduced_inorder (order, true, false);
+  int i;
+  struct ipa_dfs_info * w_info;
+
+  if (!memory_identifier_string)
+    memory_identifier_string = build_string(7, "memory");
+
+  /* There are some shared nodes, in particular the initializers on
+     static declarations.  We do not need to scan them more than once
+     since all we would be interested in are the addressof
+     operations.  */
+  visited_nodes = pointer_set_create ();
+
+  /* Process all of the functions. 
+
+     We do not want to process any of the clones so we check that this
+     is a master clone.  However, we do NOT process any
+     AVAIL_OVERWRITABLE functions (these are never clones) we cannot
+     guarantee that what we learn about the one we see will be true
+     for the one that overriders it.
+  */
+  for (node = cgraph_nodes; node; node = node->next)
+    if (node->analyzed && cgraph_is_master_clone (node))
+      analyze_function (node);
+
+  pointer_set_destroy (visited_nodes);
+  visited_nodes = NULL;
+  if (dump_file)
+    {
+      dump_cgraph (dump_file);
+      ipa_utils_print_order(dump_file, "reduced", order, order_pos);
+    }
+
+  /* Propagate the local information thru the call graph to produce
+     the global information.  All the nodes within a cycle will have
+     the same info so we collapse cycles first.  Then we can do the
+     propagation in one pass from the leaves to the roots.  */
+  for (i = 0; i < order_pos; i++ )
+    {
+      enum pure_const_state_e pure_const_state = IPA_CONST;
+      node = order[i];
+
+      /* Find the worst state for any node in the cycle.  */
+      w = node;
+      while (w)
+	{
+	  funct_state w_l = get_function_state (w);
+	  if (pure_const_state < w_l->pure_const_state)
+	    pure_const_state = w_l->pure_const_state;
+
+	  if (pure_const_state == IPA_NEITHER) 
+	    break;
+
+	  if (!w_l->state_set_in_source)
+	    {
+	      struct cgraph_edge *e;
+	      for (e = w->callees; e; e = e->next_callee) 
+		{
+		  struct cgraph_node *y = e->callee;
+		  /* Only look at the master nodes and skip external nodes.  */
+		  y = cgraph_master_clone (y);
+		  if (y)
+		    {
+		      funct_state y_l = get_function_state (y);
+		      if (pure_const_state < y_l->pure_const_state)
+			pure_const_state = y_l->pure_const_state;
+		      if (pure_const_state == IPA_NEITHER) 
+			break;
+		    }
+		}
+	    }
+	  w_info = w->aux;
+	  w = w_info->next_cycle;
+	}
+
+      /* Copy back the region's pure_const_state which is shared by
+	 all nodes in the region.  */
+      w = node;
+      while (w)
+	{
+	  funct_state w_l = get_function_state (w);
+
+	  /* All nodes within a cycle share the same info.  */
+	  if (!w_l->state_set_in_source)
+	    {
+	      w_l->pure_const_state = pure_const_state;
+	      switch (pure_const_state)
+		{
+		case IPA_CONST:
+		  TREE_READONLY (w->decl) = 1;
+		  if (dump_file)
+		    fprintf (dump_file, "Function found to be const: %s\n",  
+			     lang_hooks.decl_printable_name(w->decl, 2)); 
+		  break;
+		  
+		case IPA_PURE:
+		  DECL_IS_PURE (w->decl) = 1;
+		  if (dump_file)
+		    fprintf (dump_file, "Function found to be pure: %s\n",  
+			     lang_hooks.decl_printable_name(w->decl, 2)); 
+		  break;
+		  
+		default:
+		  break;
+		}
+	    }
+	  w_info = w->aux;
+	  w = w_info->next_cycle;
+	}
+    }
+
+  /* Cleanup. */
+  for (node = cgraph_nodes; node; node = node->next)
+    /* Get rid of the aux information.  */
+    if (node->aux)
+      {
+	free (node->aux);
+	node->aux = NULL;
+      }
+
+  free (order);
+}
+
+static bool
+gate_pure_const (void)
+{
+  return (flag_unit_at_a_time != 0 && flag_ipa_pure_const 
+	  /* Don't bother doing anything if the program has errors.  */
+	  && !(errorcount || sorrycount));
+}
+
+struct tree_opt_pass pass_ipa_pure_const =
+{
+  "ipa-pure-const",		        /* name */
+  gate_pure_const,			/* gate */
+  static_execute,			/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_IPA_PURE_CONST,		        /* tv_id */
+  0,	                                /* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  0,                                    /* todo_flags_finish */
+  0					/* letter */
+};
+
+