* ipa-cp.c: New file. Contains IPCP specific functionality.

	* ipa-prop.h: New file. Contains structures/definitions that can be
	used by several interprocedural data flow optimizations (and also IPCP).
	* ipa-prop.c: New file.


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

1 files changed, 676 insertions, 0 deletions

diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
new file mode 100644
index 00000000000..cdbf94be8ab
--- /dev/null
+++ b/gcc/ipa-prop.c
@@ -0,0 +1,676 @@
+/* Interprocedural analyses.
+   Copyright (C) 2005 Free Software Foundation, Inc.
+
+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 "tree.h"
+#include "langhooks.h"
+#include "ggc.h"
+#include "target.h"
+#include "cgraph.h"
+#include "ipa-prop.h"
+#include "tree-flow.h"
+#include "tree-pass.h"
+#include "flags.h"
+#include "timevar.h"
+
+/* This file contains interfaces that can be used for various IPA 
+   optimizations:
+
+   - ipa_methodlist interface - It is used to create and handle a temporary 
+   worklist used in  the propagation stage of IPCP. (can be used for more 
+   IPA optimizations).  
+
+   - ipa_callsite interface - for each callsite this interface creates and 
+   handles ipa_edge structure associated with it.
+
+   - ipa_method interface - for each method this interface creates and 
+   handles ipa_node structure associated with it.  */
+
+/* ipa_methodlist interface.  */
+
+/* Create a new worklist node.  */
+static inline ipa_methodlist_p
+ipa_create_methodlist_node (void)
+{
+  return (ipa_methodlist_p) xcalloc (1, sizeof (struct ipa_methodlist));
+}
+
+/* Return true if worklist WL is empty.  */
+bool
+ipa_methodlist_not_empty (ipa_methodlist_p wl)
+{
+  return (wl != NULL);
+}
+
+/* Return the method in worklist element WL.  */
+static inline struct cgraph_node *
+ipa_methodlist_method (ipa_methodlist_p wl)
+{
+  return wl->method_p;
+}
+
+/* Make worklist element WL point to method MT in the callgraph.  */
+static inline void
+ipa_methodlist_method_set (ipa_methodlist_p wl, struct cgraph_node *mt)
+{
+  wl->method_p = mt;
+}
+
+/* Return the next element in the worklist following worklist 
+   element WL.  */
+static inline ipa_methodlist_p
+ipa_methodlist_next_method (ipa_methodlist_p wl)
+{
+  return wl->next_method;
+}
+
+/* Set worklist element WL1 to point to worklist element WL2.  */
+static inline void
+ipa_methodlist_next_method_set (ipa_methodlist_p wl1, ipa_methodlist_p wl2)
+{
+  wl1->next_method = wl2;
+}
+
+/* Initialize worklist to contain all methods.  */
+ipa_methodlist_p
+ipa_methodlist_init (void)
+{
+  struct cgraph_node *node;
+  ipa_methodlist_p wl;
+
+  wl = NULL;
+  for (node = cgraph_nodes; node; node = node->next)
+    ipa_add_method (&wl, node);
+
+  return wl;
+}
+
+/* Add method MT to the worklist. Set worklist element WL  
+   to point to MT.  */
+void
+ipa_add_method (ipa_methodlist_p * wl, struct cgraph_node *mt)
+{
+  ipa_methodlist_p temp;
+
+  temp = ipa_create_methodlist_node ();
+  ipa_methodlist_method_set (temp, mt);
+  ipa_methodlist_next_method_set (temp, *wl);
+  *wl = temp;
+}
+
+/* Remove a method from the worklist. WL points to the first 
+   element in the list, which is removed.  */
+struct cgraph_node *
+ipa_remove_method (ipa_methodlist_p * wl)
+{
+  ipa_methodlist_p first;
+  struct cgraph_node *return_method;
+
+  first = *wl;
+  *wl = ipa_methodlist_next_method (*wl);
+  return_method = ipa_methodlist_method (first);
+  free (first);
+  return return_method;
+}
+
+/* ipa_method interface.  */
+
+/* Return number of formals of method MT.  */
+int
+ipa_method_formal_count (struct cgraph_node *mt)
+{
+  return IPA_NODE_REF (mt)->ipa_arg_num;
+}
+
+/* Set number of formals of method MT to I.  */
+void
+ipa_method_formal_count_set (struct cgraph_node *mt, int i)
+{
+  IPA_NODE_REF (mt)->ipa_arg_num = i;
+}
+
+/* Return whether I-th formal of MT is modified in MT.  */
+static inline bool
+ipa_method_is_modified (struct cgraph_node *mt, int i)
+{
+  return IPA_NODE_REF (mt)->ipa_mod[i];
+}
+
+/* Return the tree of I-th formal of MT.  */
+tree
+ipa_method_get_tree (struct cgraph_node *mt, int i)
+{
+  return IPA_NODE_REF (mt)->ipa_param_tree[i];
+}
+
+/* Create tree map structure for MT.  */
+static inline void
+ipa_method_tree_map_create (struct cgraph_node *mt)
+{
+  IPA_NODE_REF (mt)->ipa_param_tree =
+    xcalloc (ipa_method_formal_count (mt), sizeof (tree));
+}
+
+/* Create modify structure for MT.  */
+static inline void
+ipa_method_modify_create (struct cgraph_node *mt)
+{
+  ((struct ipa_node *) mt->aux)->ipa_mod =
+    xcalloc (ipa_method_formal_count (mt), sizeof (bool));
+}
+
+/* Set modify of I-th formal of MT to VAL.  */
+static inline void
+ipa_method_modify_set (struct cgraph_node *mt, int i, bool val)
+{
+  IPA_NODE_REF (mt)->ipa_mod[i] = val;
+}
+
+/* Return index of the formal whose tree is PTREE in method MT.  */
+static int
+ipa_method_tree_map (struct cgraph_node *mt, tree ptree)
+{
+  int i, count;
+
+  count = ipa_method_formal_count (mt);
+  for (i = 0; i < count; i++)
+    if (IPA_NODE_REF (mt)->ipa_param_tree[i] == ptree)
+      return i;
+
+  return -1;
+}
+
+/* Insert the formal trees to the ipa_param_tree array in method MT.  */
+void
+ipa_method_compute_tree_map (struct cgraph_node *mt)
+{
+  tree fndecl;
+  tree fnargs;
+  tree parm;
+  int param_num;
+
+  ipa_method_tree_map_create (mt);
+  fndecl = mt->decl;
+  fnargs = DECL_ARGUMENTS (fndecl);
+  param_num = 0;
+  for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
+    {
+      IPA_NODE_REF (mt)->ipa_param_tree[param_num] = parm;
+      param_num++;
+    }
+}
+
+/* Count number of formals in MT. Insert the result to the 
+   ipa_node.  */
+void
+ipa_method_formal_compute_count (struct cgraph_node *mt)
+{
+  tree fndecl;
+  tree fnargs;
+  tree parm;
+  int param_num;
+
+  fndecl = mt->decl;
+  fnargs = DECL_ARGUMENTS (fndecl);
+  param_num = 0;
+  for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
+    param_num++;
+  ipa_method_formal_count_set (mt, param_num);
+}
+
+/* Check STMT to detect whether a formal is modified within MT,
+   the appropriate entry is updated in the ipa_mod array of ipa_node
+   (associated with MT).  */
+static void
+ipa_method_modify_stmt (struct cgraph_node *mt, tree stmt)
+{
+  int i, j;
+
+  switch (TREE_CODE (stmt))
+    {
+    case MODIFY_EXPR:
+      if (TREE_CODE (TREE_OPERAND (stmt, 0)) == PARM_DECL)
+	{
+	  i = ipa_method_tree_map (mt, TREE_OPERAND (stmt, 0));
+	  if (i >= 0)
+            ipa_method_modify_set (mt, i, true);
+	}
+      break;
+    case ASM_EXPR:
+      /* Asm code could modify any of the parameters.  */
+      for (j = 0; j < ipa_method_formal_count (mt); j++)
+	ipa_method_modify_set (mt, j, true);
+      break;
+    default:
+      break;
+    }
+}
+
+/* Initialize ipa_mod array of MT.  */
+static void
+ipa_method_modify_init (struct cgraph_node *mt)
+{
+  int i, count;
+
+  ipa_method_modify_create (mt);
+  count = ipa_method_formal_count (mt);
+  for (i = 0; i < count; i++)
+    ipa_method_modify_set (mt, i, false);
+}
+
+/* The modify computation driver for MT. Compute which formal arguments 
+   of method MT are locally modified.  Formals may be modified in MT 
+   if their address is taken, or if
+   they appear on the left hand side of an assignment.  */
+void
+ipa_method_compute_modify (struct cgraph_node *mt)
+{
+  tree decl;
+  tree body;
+  int j, count;
+  basic_block bb;
+  struct function *func;
+  block_stmt_iterator bsi;
+  tree stmt, parm_tree;
+
+  ipa_method_modify_init (mt);
+  decl = mt->decl;
+  count = ipa_method_formal_count (mt);
+  /* ??? Handle pending sizes case. Set all parameters 
+     of the method to be modified.  */
+  if (DECL_UNINLINABLE (decl))
+    {
+      for (j = 0; j < count; j++)
+	ipa_method_modify_set (mt, j, true);
+      return;
+    }
+  /* Formals whose address is taken are considered modified.  */
+  for (j = 0; j < count; j++)
+    {
+      parm_tree = ipa_method_get_tree (mt, j);
+      if (TREE_ADDRESSABLE (parm_tree))
+	ipa_method_modify_set (mt, j, true);
+    }
+  body = DECL_SAVED_TREE (decl);
+  if (body != NULL)
+    {
+      func = DECL_STRUCT_FUNCTION (decl);
+      FOR_EACH_BB_FN (bb, func)
+      {
+	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+	  {
+	    stmt = bsi_stmt (bsi);
+	    ipa_method_modify_stmt (mt, stmt);
+	  }
+      }
+    }
+}
+
+
+/* ipa_callsite interface.  */
+
+/* Return number of arguments in callsite CS.  */
+int
+ipa_callsite_param_count (struct cgraph_edge *cs)
+{
+  return IPA_EDGE_REF (cs)->ipa_param_num;
+}
+
+/* Set number of arguments in callsite CS to I.  */
+void
+ipa_callsite_param_count_set (struct cgraph_edge *cs, int i)
+{
+  IPA_EDGE_REF (cs)->ipa_param_num = i;
+}
+
+/* Return the jump function (ipa_jump_func struct) for argument I of 
+   callsite CS.  */
+struct ipa_jump_func *
+ipa_callsite_param (struct cgraph_edge *cs, int i)
+{
+  return &(IPA_EDGE_REF (cs)->ipa_param_map[i]);
+}
+
+/* return the callee (cgraph_node) of callsite CS.  */
+struct cgraph_node *
+ipa_callsite_callee (struct cgraph_edge *cs)
+{
+  return cs->callee;
+}
+
+/* Set field 'type' of jump function (ipa_jump_func struct) of argument I 
+   in callsite CS.  */
+static inline void
+ipa_callsite_param_set_type (struct cgraph_edge *cs, int i,
+			     enum jump_func_type type1)
+{
+  IPA_EDGE_REF (cs)->ipa_param_map[i].type = type1;
+}
+
+/* Set FORMAL as 'info_type' field of jump function (ipa_jump_func struct)
+   of argument I of callsite CS.  */
+static inline void
+ipa_callsite_param_set_info_type_formal (struct cgraph_edge *cs, int i,
+					 unsigned int formal)
+{
+  ipa_callsite_param (cs, i)->info_type.formal_id = formal;
+}
+
+/* Set int-valued INFO_TYPE1 as 'info_type' field of 
+   jump function (ipa_jump_func struct) of argument I of callsite CS.  */
+static inline void
+ipa_callsite_param_set_info_type (struct cgraph_edge *cs, int i, tree info_type1)
+{
+  ipa_callsite_param (cs, i)->info_type.value = info_type1;
+}
+
+/* Allocate space for callsite CS.  */
+static inline void
+ipa_callsite_param_map_create (struct cgraph_edge *cs)
+{
+  IPA_EDGE_REF (cs)->ipa_param_map =
+    xcalloc (ipa_callsite_param_count (cs), sizeof (struct ipa_jump_func));
+}
+
+/* Return the call expr tree related to callsite CS.  */
+static inline tree
+ipa_callsite_tree (struct cgraph_edge *cs)
+{
+  return cs->call_stmt;
+}
+
+/* Return the caller (cgraph_node) of CS.  */
+static inline struct cgraph_node *
+ipa_callsite_caller (struct cgraph_edge *cs)
+{
+  return cs->caller;
+}
+
+/* Count number of arguments callsite CS has and store it in 
+   ipa_edge structure corresponding to this callsite.  */
+void
+ipa_callsite_compute_count (struct cgraph_edge *cs)
+{
+  tree call_tree;
+  tree arg;
+  int arg_num;
+
+  call_tree = get_call_expr_in (ipa_callsite_tree (cs));
+  gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
+  arg = TREE_OPERAND (call_tree, 1);
+  arg_num = 0;
+  for (; arg != NULL_TREE; arg = TREE_CHAIN (arg))
+    arg_num++;
+  ipa_callsite_param_count_set (cs, arg_num);
+}
+
+/* Compute jump function for all arguments of callsite CS 
+   and insert the information in the ipa_param_map array 
+   in the ipa_edge corresponding to this callsite. (Explanation 
+   on jump functions is in ipa-prop.h).  */
+void
+ipa_callsite_compute_param (struct cgraph_edge *cs)
+{
+  tree call_tree;
+  tree arg, cst_decl, arg_type, formal_type;
+  int arg_num;
+  int i;
+  struct cgraph_node *mt;
+
+  if (ipa_callsite_param_count (cs) == 0)
+    return;
+  ipa_callsite_param_map_create (cs);
+  call_tree = get_call_expr_in (ipa_callsite_tree (cs));
+  gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
+  arg = TREE_OPERAND (call_tree, 1);
+  arg_num = 0;
+
+  for (; arg != NULL_TREE; arg = TREE_CHAIN (arg))
+    {
+      /* If the formal parameter was passed as argument, we store 
+         FORMAL_IPATYPE and its index in the caller as the jump function 
+         of this argument.  */
+      if (TREE_CODE (TREE_VALUE (arg)) == PARM_DECL)
+	{
+	  mt = ipa_callsite_caller (cs);
+	  i = ipa_method_tree_map (mt, TREE_VALUE (arg));
+	  if (i < 0 || ipa_method_is_modified (mt, i))
+	    ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
+	  else
+	    {
+		arg_type = TREE_TYPE (TREE_VALUE (arg));
+	  	formal_type = TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num));
+	  	if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type)
+		    && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type)
+		    && attribute_list_equal (TYPE_ATTRIBUTES (arg_type),
+					     TYPE_ATTRIBUTES (formal_type)))
+		  {
+		    ipa_callsite_param_set_type (cs, arg_num, FORMAL_IPATYPE);
+		    ipa_callsite_param_set_info_type_formal (cs, arg_num, i);
+		  }
+	 	else
+		  ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
+	    }
+	}
+      /* If a constant value was passed as argument, 
+         we store CONST_IPATYPE and its value as the jump function 
+         of this argument.  */
+      else if (TREE_CODE (TREE_VALUE (arg)) == INTEGER_CST
+	       || TREE_CODE (TREE_VALUE (arg)) == REAL_CST)
+	{
+	  arg_type = TREE_TYPE (TREE_VALUE (arg));
+	  formal_type = TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num));
+	  if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type)
+	      && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type)
+	      && attribute_list_equal (TYPE_ATTRIBUTES (arg_type),
+				       TYPE_ATTRIBUTES (formal_type)))
+	    {
+	      ipa_callsite_param_set_type (cs, arg_num, CONST_IPATYPE);
+	      ipa_callsite_param_set_info_type (cs, arg_num, TREE_VALUE (arg));
+	    }
+	  else
+	    ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
+	}
+      /* This is for the case of Fortran. If the address of a const_decl 
+         was passed as argument then we store 
+         CONST_IPATYPE_REF/CONST_IPATYPE_REF and the costant 
+         value as the jump function corresponding to this argument.  */
+      else if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR
+	       && TREE_CODE (TREE_OPERAND (TREE_VALUE (arg), 0)) ==
+	       CONST_DECL)
+	{
+	  cst_decl = TREE_OPERAND (TREE_VALUE (arg), 0);
+	  arg_type = TREE_TYPE (DECL_INITIAL (cst_decl));
+	  formal_type =
+	    TREE_TYPE (TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num)));
+	  if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST
+	      || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST)
+	    {
+	      if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type)
+		  && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type)
+		  && attribute_list_equal (TYPE_ATTRIBUTES (arg_type),
+					   TYPE_ATTRIBUTES (formal_type)))
+
+		{
+		  ipa_callsite_param_set_type (cs, arg_num,
+					       CONST_IPATYPE_REF);
+		  ipa_callsite_param_set_info_type (cs, arg_num, DECL_INITIAL (cst_decl));
+
+		}
+	      else
+		ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
+	    }
+	}
+      else
+	ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
+      arg_num++;
+    }
+}
+
+/* Return type of jump function JF.  */
+enum jump_func_type
+get_type (struct ipa_jump_func *jf)
+{
+  return jf->type;
+}
+
+/* Return info type of jump function JF.  */
+union parameter_info *
+ipa_jf_get_info_type (struct ipa_jump_func *jf)
+{
+  return &(jf->info_type);
+}
+
+/* Allocate and initialize ipa_node structure.  
+   cgraph_node NODE points to the new allocated ipa_node.  */
+void
+ipa_node_create (struct cgraph_node *node)
+{
+  node->aux = xcalloc (1, sizeof (struct ipa_node));
+}
+
+/* Allocate and initialize ipa_node structure for all
+   nodes in callgraph.  */
+void
+ipa_nodes_create (void)
+{
+  struct cgraph_node *node;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    ipa_node_create (node);
+}
+
+/* Allocate and initialize ipa_edge structure.  */
+void
+ipa_edges_create (void)
+{
+  struct cgraph_node *node;
+  struct cgraph_edge *cs;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    for (cs = node->callees; cs; cs = cs->next_callee)
+      cs->aux = xcalloc (1, sizeof (struct ipa_edge));
+}
+
+/* Free ipa_node structure.  */
+void
+ipa_nodes_free (void)
+{
+  struct cgraph_node *node;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      free (node->aux);
+      node->aux = NULL;
+    }
+}
+
+/* Free ipa_edge structure.  */
+void
+ipa_edges_free (void)
+{
+  struct cgraph_node *node;
+  struct cgraph_edge *cs;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    for (cs = node->callees; cs; cs = cs->next_callee)
+      {
+	free (cs->aux);
+	cs->aux = NULL;
+      }
+}
+
+/* Free ipa data structures of ipa_node and ipa_edge.  */
+void
+ipa_free (void)
+{
+  struct cgraph_node *node;
+  struct cgraph_edge *cs;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      if (node->aux == NULL)
+	continue;
+      if (IPA_NODE_REF (node)->ipcp_cval)
+	free (IPA_NODE_REF (node)->ipcp_cval);
+      if (IPA_NODE_REF (node)->ipa_param_tree)
+	free (IPA_NODE_REF (node)->ipa_param_tree);
+      if (IPA_NODE_REF (node)->ipa_mod)
+	free (IPA_NODE_REF (node)->ipa_mod);
+      for (cs = node->callees; cs; cs = cs->next_callee)
+	{
+	  if (cs->aux)
+	    if (IPA_EDGE_REF (cs)->ipa_param_map)
+	      free (IPA_EDGE_REF (cs)->ipa_param_map);
+	}
+    }
+}
+
+/* Print ipa_tree_map data structures of all methods in the 
+   callgraph to F.  */
+void
+ipa_method_tree_print (FILE * f)
+{
+  int i, count;
+  tree temp;
+  struct cgraph_node *node;
+
+  fprintf (f, "\nPARAM TREE MAP PRINT\n");
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      fprintf (f, "method  %s Trees :: \n", cgraph_node_name (node));
+      count = ipa_method_formal_count (node);
+      for (i = 0; i < count; i++)
+	{
+	  temp = ipa_method_get_tree (node, i);
+	  if (TREE_CODE (temp) == PARM_DECL)
+	    fprintf (f, "  param [%d] : %s\n", i,
+		     (*lang_hooks.decl_printable_name) (temp, 2));
+	}
+
+    }
+}
+
+/* Print ipa_modify data structures of all methods in the 
+   callgraph to F.  */
+void
+ipa_method_modify_print (FILE * f)
+{
+  int i, count;
+  bool temp;
+  struct cgraph_node *node;
+
+  fprintf (f, "\nMODIFY PRINT\n");
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      fprintf (f, "method  %s :: \n", cgraph_node_name (node));
+      count = ipa_method_formal_count (node);
+      for (i = 0; i < count; i++)
+	{
+	  temp = ipa_method_is_modified (node, i);
+	  if (temp)
+	    fprintf (f, " param [%d] true \n", i);
+	  else
+	    fprintf (f, " param [%d] false \n", i);
+	}
+    }
+}