ipa-cp.c: New file.

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

From-SVN: r102624

1 files changed, 1143 insertions, 0 deletions

diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
new file mode 100644
index 0000000..f7dad3f
--- /dev/null
+++ b/gcc/ipa-cp.c
@@ -0,0 +1,1143 @@
+/* Interprocedural constant propagation
+   Copyright (C) 2005 Free Software Foundation, Inc.
+   Contributed by Razya Ladelsky <RAZYA@il.ibm.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.  */
+
+/* Interprocedural constant propagation.
+   The aim of interprocedural constant propagation (IPCP) is to find which 
+   function's argument has the same constant value in each invocation throughout 
+   the whole program. For example, for an application consisting of two files, 
+   foo1.c, foo2.c:
+
+   foo1.c contains :
+   
+   int f (int x)
+   {
+     g (x);
+   }
+   void main (void)
+   {
+     f (3);
+     h (3);
+   }
+   
+   foo2.c contains :
+   
+   int h (int y)
+   {
+     g (y);
+   }
+   int g (int y)
+   {
+     printf ("value is %d",y);
+   }
+   
+   The IPCP algorithm will find that g's formal argument y
+   is always called with the value 3.
+   
+   The algorithm used is based on "Interprocedural Constant Propagation",
+   by Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, 
+   pg 152-161
+   
+   The optimization is divided into three stages:
+
+   First stage - intraprocedural analysis
+   =======================================
+   This phase computes jump_function and modify information.
+   
+   A jump function for a callsite represents the values passed as actual 
+   arguments
+   of the callsite. There are three types of values :
+   Formal - the caller's formal parameter is passed as an actual argument.
+   Constant - a constant is passed as a an actual argument.
+   Unknown - neither of the above.
+   
+   In order to compute the jump functions, we need the modify information for 
+   the formal parameters of methods.
+   
+   The jump function info, ipa_jump_func, is defined in ipa_edge
+   structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
+   The modify info, ipa_modify, is defined in ipa_node structure
+   (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
+   
+   -ipcp_init_stage() is the first stage driver.
+
+   Second stage - interprocedural analysis
+   ========================================
+   This phase does the interprocedural constant propagation.
+   It computes for all formal parameters in the program
+   their cval value that may be:
+   TOP - unknown.
+   BOTTOM - non constant.
+   CONSTANT_TYPE - constant value.
+   
+   Cval of formal f will have a constant value if all callsites to this
+   function have the same constant value passed to f.
+   
+   The cval info, ipcp_formal, is defined in ipa_node structure
+   (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
+
+   -ipcp_iterate_stage() is the second stage driver.
+
+   Third phase - transformation of methods code
+   ============================================
+   Propagates the constant-valued formals into the function.
+   For each method mt, whose parameters are consts, we create a clone/version.
+
+   We use two ways to annotate the versioned function with the constant 
+   formal information:
+   1. We insert an assignment statement 'parameter = const' at the beginning
+   of the cloned method.
+   2. For read-only formals whose address is not taken, we replace all uses 
+   of the formal with the constant (we provide versioning with an 
+   ipa_replace_map struct representing the trees we want to replace).
+
+   We also need to modify some callsites to call to the cloned methods instead
+   of the original ones. For a callsite passing an argument found to be a
+   constant by IPCP, there are two different cases to handle:
+   1. A constant is passed as an argument.
+   2. A parameter (of the caller) passed as an argument (pass through argument).
+
+   In the first case, the callsite in the original caller should be redirected
+   to call the cloned callee.
+   In the second case, both the caller and the callee have clones
+   and the callsite of the cloned caller would be redirected to call to
+   the cloned callee.
+
+   The callgraph is updated accordingly.
+
+   This update is done in two stages:
+   First all cloned methods are created during a traversal of the callgraph,
+   during which all callsites are redirected to call the cloned method.
+   Then the callsites are traversed and updated as described above.
+
+   -ipcp_insert_stage() is the third phase driver.
+   
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.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"
+#include "diagnostic.h"
+
+/* Get orig node field of ipa_node associated with method MT.  */
+static inline struct cgraph_node *
+ipcp_method_orig_node (struct cgraph_node *mt)
+{
+  return IPA_NODE_REF (mt)->ipcp_orig_node;
+}
+
+/* Return true if NODE is a cloned/versioned method.  */
+static inline bool
+ipcp_method_is_cloned (struct cgraph_node *node)
+{
+  return (ipcp_method_orig_node (node) != NULL);
+}
+
+/* Set ORIG_NODE in ipa_node associated with method NODE.  */
+static inline void
+ipcp_method_set_orig_node (struct cgraph_node *node,
+			   struct cgraph_node *orig_node)
+{
+  IPA_NODE_REF (node)->ipcp_orig_node = orig_node;
+}
+
+/* Create ipa_node and its data strutures for NEW_NODE.
+   Set ORIG_NODE as the orig_node field in ipa_node.  */
+static void
+ipcp_cloned_create (struct cgraph_node *orig_node,
+		    struct cgraph_node *new_node)
+{
+  ipa_node_create (new_node);
+  ipcp_method_set_orig_node (new_node, orig_node);
+  ipa_method_formal_compute_count (new_node);
+  ipa_method_compute_tree_map (new_node);
+}
+
+/* Return cval_type field of CVAL.  */
+static inline enum cvalue_type
+ipcp_cval_get_cvalue_type (struct ipcp_formal *cval)
+{
+  return cval->cval_type;
+}
+
+/* Return scale for MT.  */
+static inline gcov_type
+ipcp_method_get_scale (struct cgraph_node *mt)
+{
+  return IPA_NODE_REF (mt)->count_scale;
+}
+
+/* Set COUNT as scale for MT.  */
+static inline void
+ipcp_method_set_scale (struct cgraph_node *node, gcov_type count)
+{
+  IPA_NODE_REF (node)->count_scale = count;
+}
+
+/* Set TYPE as cval_type field of CVAL.  */
+static inline void
+ipcp_cval_set_cvalue_type (struct ipcp_formal *cval, enum cvalue_type type)
+{
+  cval->cval_type = type;
+}
+
+/* Return cvalue field of CVAL.  */
+static inline union parameter_info *
+ipcp_cval_get_cvalue (struct ipcp_formal *cval)
+{
+  return &(cval->cvalue);
+}
+
+/* Set VALUE as cvalue field  CVAL.  */
+static inline void
+ipcp_cval_set_cvalue (struct ipcp_formal *cval, union parameter_info *value,
+		      enum cvalue_type type)
+{
+  if (type == CONST_VALUE || type == CONST_VALUE_REF)
+    cval->cvalue.value =  value->value;
+}
+
+/* Return whether TYPE is a constant type.  */
+static bool
+ipcp_type_is_const (enum cvalue_type type)
+{
+  if (type == CONST_VALUE || type == CONST_VALUE_REF)
+    return true;
+  else
+    return false;
+}
+
+/* Return true if CONST_VAL1 and CONST_VAL2 are equal.  */
+static inline bool
+ipcp_cval_equal_cvalues (union parameter_info *const_val1,
+			 union parameter_info *const_val2,
+			 enum cvalue_type type1, enum cvalue_type type2)
+{
+  gcc_assert (ipcp_type_is_const (type1) && ipcp_type_is_const (type2));
+  if (type1 != type2)
+    return false;
+
+  if (operand_equal_p (const_val1->value, const_val2->value, 0))
+    return true;
+
+  return false;
+}
+
+/* Compute Meet arithmetics:
+   Meet (BOTTOM, x) = BOTTOM
+   Meet (TOP,x) = x
+   Meet (const_a,const_b) = BOTTOM,  if const_a != const_b.  
+   MEET (const_a,const_b) = const_a, if const_a == const_b.*/
+static void
+ipcp_cval_meet (struct ipcp_formal *cval, struct ipcp_formal *cval1,
+		struct ipcp_formal *cval2)
+{
+  if (ipcp_cval_get_cvalue_type (cval1) == BOTTOM
+      || ipcp_cval_get_cvalue_type (cval2) == BOTTOM)
+    {
+      ipcp_cval_set_cvalue_type (cval, BOTTOM);
+      return;
+    }
+  if (ipcp_cval_get_cvalue_type (cval1) == TOP)
+    {
+      ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval2));
+      ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval2),
+			    ipcp_cval_get_cvalue_type (cval2));
+      return;
+    }
+  if (ipcp_cval_get_cvalue_type (cval2) == TOP)
+    {
+      ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1));
+      ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1),
+			    ipcp_cval_get_cvalue_type (cval1));
+      return;
+    }
+  if (!ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1),
+				ipcp_cval_get_cvalue (cval2),
+				ipcp_cval_get_cvalue_type (cval1),
+				ipcp_cval_get_cvalue_type (cval2)))
+    {
+      ipcp_cval_set_cvalue_type (cval, BOTTOM);
+      return;
+    }
+  ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1));
+  ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1),
+			ipcp_cval_get_cvalue_type (cval1));
+}
+
+/* Return cval structure for the formal at index INFO_TYPE in MT.  */
+static inline struct ipcp_formal *
+ipcp_method_cval (struct cgraph_node *mt, int info_type)
+{
+  return &(IPA_NODE_REF (mt)->ipcp_cval[info_type]);
+}
+
+/* Given the jump function (TYPE, INFO_TYPE), compute a new value of CVAL.  
+   If TYPE is FORMAL_IPA_TYPE, the cval of the corresponding formal is 
+   drawn from MT.  */
+static void
+ipcp_cval_compute (struct ipcp_formal *cval, struct cgraph_node *mt,
+		   enum jump_func_type type, union parameter_info *info_type)
+{
+  if (type == UNKNOWN_IPATYPE)
+    ipcp_cval_set_cvalue_type (cval, BOTTOM);
+  else if (type == CONST_IPATYPE)
+    {
+      ipcp_cval_set_cvalue_type (cval, CONST_VALUE);
+      ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE);
+    }
+  else if (type == CONST_IPATYPE_REF)
+    {
+      ipcp_cval_set_cvalue_type (cval, CONST_VALUE_REF);
+      ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE_REF);
+    }
+  else if (type == FORMAL_IPATYPE)
+    {
+      enum cvalue_type type =
+	ipcp_cval_get_cvalue_type (ipcp_method_cval
+				   (mt, info_type->formal_id));
+      ipcp_cval_set_cvalue_type (cval, type);
+      ipcp_cval_set_cvalue (cval,
+			    ipcp_cval_get_cvalue (ipcp_method_cval
+						  (mt, info_type->formal_id)),
+			    type);
+    }
+}
+
+/* True when CVAL1 and CVAL2 values are not the same.  */
+static bool
+ipcp_cval_changed (struct ipcp_formal *cval1, struct ipcp_formal *cval2)
+{
+  if (ipcp_cval_get_cvalue_type (cval1) == ipcp_cval_get_cvalue_type (cval2))
+    {
+      if (ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE &&
+	  ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE_REF)	 
+	return false;
+      if (ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1),
+				   ipcp_cval_get_cvalue (cval2),
+				   ipcp_cval_get_cvalue_type (cval1),
+				   ipcp_cval_get_cvalue_type (cval2)))
+	return false;
+    }
+  return true;
+}
+
+/* Create cval structure for method MT.  */
+static inline void
+ipcp_formal_create (struct cgraph_node *mt)
+{
+  IPA_NODE_REF (mt)->ipcp_cval =
+    xcalloc (ipa_method_formal_count (mt), sizeof (struct ipcp_formal));
+}
+
+/* Set cval structure of I-th formal of MT to CVAL.  */
+static inline void
+ipcp_method_cval_set (struct cgraph_node *mt, int i, struct ipcp_formal *cval)
+{
+  IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval->cval_type;
+  ipcp_cval_set_cvalue (ipcp_method_cval (mt, i),
+			ipcp_cval_get_cvalue (cval), cval->cval_type);
+}
+
+/* Set type of cval structure of formal I of MT to CVAL_TYPE1.  */
+static inline void
+ipcp_method_cval_set_cvalue_type (struct cgraph_node *mt, int i,
+				  enum cvalue_type cval_type1)
+{
+  IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval_type1;
+}
+
+/* Print ipcp_cval data structures to F.  */
+static void
+ipcp_method_cval_print (FILE * f)
+{
+  struct cgraph_node *node;
+  int i, count;
+  tree cvalue;
+ 
+  fprintf (f, "\nCVAL PRINT\n");
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      fprintf (f, "Printing cvals %s:\n", cgraph_node_name (node));
+      count = ipa_method_formal_count (node);
+      for (i = 0; i < count; i++)
+	{
+	  if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i))
+	      == CONST_VALUE
+	      || ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) ==
+	      CONST_VALUE_REF)
+	    {
+	      fprintf (f, " param [%d]: ", i);
+	      fprintf (f, "type is CONST ");
+	      cvalue =
+		ipcp_cval_get_cvalue (ipcp_method_cval (node, i))->
+		  value;
+              print_generic_expr (f, cvalue, 0);
+              fprintf (f, "\n");
+	    }
+	  else if (ipcp_method_cval (node, i)->cval_type == TOP)
+	    fprintf (f, "param [%d]: type is TOP  \n", i);
+	  else
+	    fprintf (f, "param [%d]: type is BOTTOM  \n", i);
+	}
+    }
+}
+
+/* Initialize ipcp_cval array of MT with TOP values.
+   All cvals for a method's formal parameters are initialized to BOTTOM
+   The currently supported types are integer types, real types and
+   Fortran constants (i.e. references to constants defined as
+   const_decls). All other types are not analyzed and therefore are
+   assigned with BOTTOM.  */
+static void
+ipcp_method_cval_init (struct cgraph_node *mt)
+{
+  int i;
+  tree parm_tree;
+
+  ipcp_formal_create (mt);
+  for (i = 0; i < ipa_method_formal_count (mt); i++)
+    {
+      parm_tree = ipa_method_get_tree (mt, i);
+      if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree)) 
+	  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree)) 
+	  || POINTER_TYPE_P (TREE_TYPE (parm_tree)))
+	ipcp_method_cval_set_cvalue_type (mt, i, TOP);
+      else
+	ipcp_method_cval_set_cvalue_type (mt, i, BOTTOM);
+    }
+}
+
+/* Create a new assignment statment and make
+   it the first statemant in the function FN
+   tree.
+   PARM1 is the lhs of the assignment and
+   VAL is the rhs. */
+static void
+constant_val_insert (tree fn, tree parm1, tree val)
+{
+  struct function *func;
+  tree init_stmt;
+  edge e_step;
+  edge_iterator ei;
+
+  init_stmt = build2 (MODIFY_EXPR, void_type_node, parm1, val);
+  func = DECL_STRUCT_FUNCTION (fn);
+  cfun = func;
+  current_function_decl = fn;
+  if (ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs)
+    FOR_EACH_EDGE (e_step, ei, ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs)
+      bsi_insert_on_edge_immediate (e_step, init_stmt);
+}
+
+/* build INTEGER_CST tree with type TREE_TYPE and 
+   value according to CVALUE. Return the tree.   */
+static tree
+build_const_val (union parameter_info *cvalue, enum cvalue_type type,
+		 tree tree_type)
+{
+  tree const_val = NULL;
+
+  gcc_assert (ipcp_type_is_const (type));
+  const_val = fold_convert (tree_type, cvalue->value);
+  return const_val;
+}
+
+/* Build the tree representing the constant and call 
+   constant_val_insert().  */
+static void
+ipcp_propagate_const (struct cgraph_node *mt, int param,
+		      union parameter_info *cvalue ,enum cvalue_type type)
+{
+  tree fndecl;
+  tree const_val;
+  tree parm_tree;
+
+  if (dump_file)
+    fprintf (dump_file, "propagating const to %s\n", cgraph_node_name (mt));
+  fndecl = mt->decl;
+  parm_tree = ipa_method_get_tree (mt, param);
+  const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
+  constant_val_insert (fndecl, parm_tree, const_val);
+}
+
+/* Compute the proper scale for NODE.  It is the ratio between 
+   the number of direct calls (represented on the incoming 
+   cgraph_edges) and sum of all invocations of NODE (represented 
+   as count in cgraph_node). */
+static void
+ipcp_method_compute_scale (struct cgraph_node *node)
+{
+  gcov_type sum;
+  struct cgraph_edge *cs;
+
+  sum = 0;
+  /* Compute sum of all counts of callers. */
+  for (cs = node->callers; cs != NULL; cs = cs->next_caller)
+    sum += cs->count;
+  if (node->count == 0)
+    ipcp_method_set_scale (node, 0);
+  else
+    ipcp_method_set_scale (node, sum * REG_BR_PROB_BASE / node->count);
+}
+
+/* Initialization and computation of IPCP data structures. 
+   It is an intraprocedural
+   analysis of methods, which gathers information to be propagated
+   later on.  */
+static void
+ipcp_init_stage (void)
+{
+  struct cgraph_node *node;
+  struct cgraph_edge *cs;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      ipa_method_formal_compute_count (node);
+      ipa_method_compute_tree_map (node);
+      ipcp_method_cval_init (node);
+      ipa_method_compute_modify (node);
+      ipcp_method_compute_scale (node);
+    }
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      /* building jump functions  */
+      for (cs = node->callees; cs; cs = cs->next_callee)
+	{
+	  ipa_callsite_compute_count (cs);
+	  if (ipa_callsite_param_count (cs)
+	      != ipa_method_formal_count (cs->callee))
+	    {
+	      /* Handle cases of functions with 
+	         a variable number of parameters.  */
+	      ipa_callsite_param_count_set (cs, 0);
+	      ipa_method_formal_count_set (cs->callee, 0);
+	    }
+	  else
+	    ipa_callsite_compute_param (cs);
+	}
+    }
+}
+
+/* Return true if there are some formal parameters whose value is TOP.
+   Change their values to BOTTOM, since they weren't determined.  */
+static bool
+ipcp_after_propagate (void)
+{
+  int i, count;
+  struct cgraph_node *node;
+  bool prop_again;
+
+  prop_again = false;
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      count = ipa_method_formal_count (node);
+      for (i = 0; i < count; i++)
+	if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == TOP)
+	  {
+	    prop_again = true;
+	    ipcp_method_cval_set_cvalue_type (node, i, BOTTOM);
+	  }
+    }
+  return prop_again;
+}
+
+/* Interprocedural analysis. The algorithm propagates constants from
+   the caller's parameters to the callee's arguments.  */
+static void
+ipcp_propagate_stage (void)
+{
+  int i;
+  struct ipcp_formal cval1 = { 0, {0} }, cval = { 0,{0} };
+  struct ipcp_formal *cval2;
+  struct cgraph_node *mt, *callee;
+  struct cgraph_edge *cs;
+  struct ipa_jump_func *jump_func;
+  enum jump_func_type type;
+  union parameter_info *info_type;
+  ipa_methodlist_p wl;
+  int count;
+
+  /* Initialize worklist to contain all methods.  */
+  wl = ipa_methodlist_init ();
+  while (ipa_methodlist_not_empty (wl))
+    {
+      mt = ipa_remove_method (&wl);
+      for (cs = mt->callees; cs; cs = cs->next_callee)
+	{
+	  callee = ipa_callsite_callee (cs);
+	  count = ipa_callsite_param_count (cs);
+	  for (i = 0; i < count; i++)
+	    {
+	      jump_func = ipa_callsite_param (cs, i);
+	      type = get_type (jump_func);
+	      info_type = ipa_jf_get_info_type (jump_func);
+	      ipcp_cval_compute (&cval1, mt, type, info_type);
+	      cval2 = ipcp_method_cval (callee, i);
+	      ipcp_cval_meet (&cval, &cval1, cval2);
+	      if (ipcp_cval_changed (&cval, cval2))
+		{
+		  ipcp_method_cval_set (callee, i, &cval);
+		  ipa_add_method (&wl, callee);
+		}
+	    }
+	}
+    }
+}
+
+/* Call the constant propagation algorithm and re-call it if necessary
+   (if there are undetermined values left).  */
+static void
+ipcp_iterate_stage (void)
+{
+  ipcp_propagate_stage ();
+  if (ipcp_after_propagate ())
+    /* Some cvals have changed from TOP to BOTTOM.  
+       This change should be propagated.  */
+    ipcp_propagate_stage ();
+}
+
+/* Check conditions to forbid constant insertion to MT.  */
+static bool
+ipcp_method_dont_insert_const (struct cgraph_node *mt)
+{
+  /* ??? Handle pending sizes case.  */
+  if (DECL_UNINLINABLE (mt->decl))
+    return true;
+  return false;
+}
+
+/* Print ipa_jump_func data structures to F.  */
+static void
+ipcp_callsite_param_print (FILE * f)
+{
+  struct cgraph_node *node;
+  int i, count;
+  struct cgraph_edge *cs;
+  struct ipa_jump_func *jump_func;
+  enum jump_func_type type;
+  tree info_type;
+ 
+  fprintf (f, "\nCALLSITE PARAM PRINT\n");
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      for (cs = node->callees; cs; cs = cs->next_callee)
+	{
+	  fprintf (f, "callsite  %s ", cgraph_node_name (node));
+	  fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee));
+	  count = ipa_callsite_param_count (cs);
+	  for (i = 0; i < count; i++)
+	    {
+	      jump_func = ipa_callsite_param (cs, i);
+	      type = get_type (jump_func);
+
+	      fprintf (f, " param %d: ", i);
+	      if (type == UNKNOWN_IPATYPE)
+		fprintf (f, "UNKNOWN\n");
+	      else if (type == CONST_IPATYPE || type == CONST_IPATYPE_REF)
+		{
+		  info_type =
+		    ipa_jf_get_info_type (jump_func)->value;
+                  fprintf (f, "CONST : ");
+                  print_generic_expr (f, info_type, 0);
+                  fprintf (f, "\n");
+		}
+	      else if (type == FORMAL_IPATYPE)
+		{
+		  fprintf (f, "FORMAL : ");
+		  fprintf (f, "%d\n",
+			   ipa_jf_get_info_type (jump_func)->formal_id);
+		}
+	    }
+	}
+    }
+}
+
+/* Print count scale data structures.  */
+static void
+ipcp_method_scale_print (FILE * f)
+{
+  struct cgraph_node *node;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
+      fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
+	       "  \n", (HOST_WIDE_INT) ipcp_method_get_scale (node));
+    }
+}
+
+/* Print counts of all cgraph nodes.  */
+static void
+ipcp_profile_mt_count_print (FILE * f)
+{
+  struct cgraph_node *node;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      fprintf (f, "method %s: ", cgraph_node_name (node));
+      fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
+	       "  \n", (HOST_WIDE_INT) node->count);
+    }
+}
+
+/* Print counts of all cgraph edgess.  */
+static void
+ipcp_profile_cs_count_print (FILE * f)
+{
+  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)
+	{
+	  fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
+		   cgraph_node_name (cs->callee));
+	  fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
+		   (HOST_WIDE_INT) cs->count);
+	}
+    }
+}
+
+/* Print all counts and probabilities of cfg edges of all methods.  */
+static void
+ipcp_profile_edge_print (FILE * f)
+{
+  struct cgraph_node *node;
+  basic_block bb;
+  edge_iterator ei;
+  edge e;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      fprintf (f, "method %s: \n", cgraph_node_name (node));
+      if (DECL_SAVED_TREE (node->decl))
+	{
+	  bb =
+	    ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
+	  fprintf (f, "ENTRY: ");
+	  fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
+		   " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
+
+	  if (bb->succs)
+	    FOR_EACH_EDGE (e, ei, bb->succs)
+	    {
+	      if (e->dest ==
+		  EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
+					       (node->decl)))
+		fprintf (f, "edge ENTRY -> EXIT,  Count");
+	      else
+		fprintf (f, "edge ENTRY -> %d,  Count", e->dest->index);
+	      fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
+		       " Prob %d\n", (HOST_WIDE_INT) e->count,
+		       e->probability);
+	    }
+	  FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
+	  {
+	    fprintf (f, "bb[%d]: ", bb->index);
+	    fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
+		     " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
+	    FOR_EACH_EDGE (e, ei, bb->succs)
+	    {
+	      if (e->dest ==
+		  EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
+					       (node->decl)))
+		fprintf (f, "edge %d -> EXIT,  Count", e->src->index);
+	      else
+		fprintf (f, "edge %d -> %d,  Count", e->src->index,
+			 e->dest->index);
+	      fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n",
+		       (HOST_WIDE_INT) e->count, e->probability);
+	    }
+	  }
+	}
+    }
+}
+
+/* Print counts and frequencies for all basic blocks of all methods.  */
+static void
+ipcp_profile_bb_print (FILE * f)
+{
+  basic_block bb;
+  struct cgraph_node *node;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      fprintf (f, "method %s: \n", cgraph_node_name (node));
+      if (DECL_SAVED_TREE (node->decl))
+	{
+	  bb =
+	    ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
+	  fprintf (f, "ENTRY: Count");
+	  fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
+		   " Frquency  %d\n", (HOST_WIDE_INT) bb->count,
+		   bb->frequency);
+
+	  FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
+	  {
+	    fprintf (f, "bb[%d]: Count", bb->index);
+	    fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
+		     " Frequency %d\n", (HOST_WIDE_INT) bb->count,
+		     bb->frequency);
+	  }
+	  bb =
+	    EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
+	  fprintf (f, "EXIT: Count");
+	  fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
+		   " Frequency %d\n", (HOST_WIDE_INT) bb->count,
+		   bb->frequency);
+
+	}
+    }
+}
+
+/* Print all IPCP data structures to F.  */
+static void
+ipcp_structures_print (FILE * f)
+{
+  ipcp_method_cval_print (f);
+  ipcp_method_scale_print (f);
+  ipa_method_tree_print (f);
+  ipa_method_modify_print (f);
+  ipcp_callsite_param_print (f);
+}
+
+/* Print profile info for all methods.  */
+static void
+ipcp_profile_print (FILE * f)
+{
+  fprintf (f, "\nNODE COUNTS :\n");
+  ipcp_profile_mt_count_print (f);
+  fprintf (f, "\nCS COUNTS stage:\n");
+  ipcp_profile_cs_count_print (f);
+  fprintf (f, "\nBB COUNTS and FREQUENCIES :\n");
+  ipcp_profile_bb_print (f);
+  fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
+  ipcp_profile_edge_print (f);
+}
+
+/* Build and initialize ipa_replace_map struct
+   according to TYPE. This struct is read by versioning, which
+   operates according to the flags sent.  PARM_TREE is the 
+   formal's tree found to be constant.  CVALUE represents the constant.  */
+static struct ipa_replace_map *
+ipcp_replace_map_create (enum cvalue_type type, tree parm_tree,
+			 union parameter_info *cvalue)
+{
+  struct ipa_replace_map *replace_map;
+  tree const_val;
+
+  replace_map = xcalloc (1, sizeof (struct ipa_replace_map));
+  gcc_assert (ipcp_type_is_const (type));
+  if (type == CONST_VALUE_REF )
+    {
+      const_val =
+	build_const_val (cvalue, type, TREE_TYPE (TREE_TYPE (parm_tree)));
+      replace_map->old_tree = parm_tree;
+      replace_map->new_tree = const_val;
+      replace_map->replace_p = true;
+      replace_map->ref_p = true;
+    }
+  else if (TREE_READONLY (parm_tree) && !TREE_ADDRESSABLE (parm_tree))
+    {
+      const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
+      replace_map->old_tree = parm_tree;
+      replace_map->new_tree = const_val;
+      replace_map->replace_p = true;
+      replace_map->ref_p = false;
+    }
+  else
+    {
+      replace_map->old_tree = NULL;
+      replace_map->new_tree = NULL;
+      replace_map->replace_p = false;
+      replace_map->ref_p = false;
+    }
+
+  return replace_map;
+}
+
+/* Return true if this callsite should be redirected to
+   the orig callee (instead of the cloned one).  */
+static bool
+ipcp_redirect (struct cgraph_edge *cs)
+{
+  struct cgraph_node *caller, *callee, *orig_callee;
+  int i, count;
+  struct ipa_jump_func *jump_func;
+  enum jump_func_type type;
+  enum cvalue_type cval_type;
+
+  caller = cs->caller;
+  callee = cs->callee;
+  orig_callee = ipcp_method_orig_node (callee);
+  count = ipa_method_formal_count (orig_callee);
+  for (i = 0; i < count; i++)
+    {
+      cval_type =
+	ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee, i));
+      if (ipcp_type_is_const (cval_type))
+	{
+	  jump_func = ipa_callsite_param (cs, i);
+	  type = get_type (jump_func);
+	  if (type != CONST_IPATYPE 
+	      && type != CONST_IPATYPE_REF)
+	    return true;
+	}
+    }
+
+  return false;
+}
+
+/* Fix the callsites and the callgraph after function cloning was done.  */
+static void
+ipcp_update_callgraph (void)
+{
+  struct cgraph_node *node, *orig_callee;
+  struct cgraph_edge *cs;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      /* want to fix only original nodes  */
+      if (ipcp_method_is_cloned (node))
+	continue;
+      for (cs = node->callees; cs; cs = cs->next_callee)
+	if (ipcp_method_is_cloned (cs->callee))
+	  {
+	    /* Callee is a cloned node  */
+	    orig_callee = ipcp_method_orig_node (cs->callee);
+	    if (ipcp_redirect (cs))
+	      {
+		cgraph_redirect_edge_callee (cs, orig_callee);
+		TREE_OPERAND (TREE_OPERAND
+			      (get_call_expr_in (cs->call_stmt), 0), 0) =
+		  orig_callee->decl;
+	      }
+	  }
+    }
+}
+
+/* Update all cfg basic blocks in NODE according to SCALE.  */
+static void
+ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale)
+{
+  basic_block bb;
+
+  FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
+    bb->count = bb->count * scale / REG_BR_PROB_BASE;
+}
+
+/* Update all cfg edges in NODE according to SCALE.  */
+static void
+ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale)
+{
+  basic_block bb;
+  edge_iterator ei;
+  edge e;
+
+  FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
+    FOR_EACH_EDGE (e, ei, bb->succs)
+    e->count = e->count * scale / REG_BR_PROB_BASE;
+}
+
+/* Update profiling info for versioned methods and the
+   methods they were versioned from.  */
+static void
+ipcp_update_profiling (void)
+{
+  struct cgraph_node *node, *orig_node;
+  gcov_type scale, scale_complement;
+  struct cgraph_edge *cs;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      if (ipcp_method_is_cloned (node))
+	{
+	  orig_node = ipcp_method_orig_node (node);
+	  scale = ipcp_method_get_scale (orig_node);
+	  node->count = orig_node->count * scale / REG_BR_PROB_BASE;
+	  scale_complement = REG_BR_PROB_BASE - scale;
+	  orig_node->count =
+	    orig_node->count * scale_complement / REG_BR_PROB_BASE;
+	  for (cs = node->callees; cs; cs = cs->next_callee)
+	    cs->count = cs->count * scale / REG_BR_PROB_BASE;
+	  for (cs = orig_node->callees; cs; cs = cs->next_callee)
+	    cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
+	  ipcp_update_bb_counts (node, scale);
+	  ipcp_update_bb_counts (orig_node, scale_complement);
+	  ipcp_update_edges_counts (node, scale);
+	  ipcp_update_edges_counts (orig_node, scale_complement);
+	}
+    }
+}
+
+/* Propagate the constant parameters found by ipcp_iterate_stage()
+   to the function's code.  */
+static void
+ipcp_insert_stage (void)
+{
+  struct cgraph_node *node, *node1 = NULL;
+  int i, const_param;
+  union parameter_info *cvalue;
+  varray_type redirect_callers, replace_trees;
+  struct cgraph_edge *cs;
+  int node_callers, count;
+  tree parm_tree;
+  enum cvalue_type type;
+  struct ipa_replace_map *replace_param;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      /* Propagation of the constant is forbidden in 
+         certain conditions.  */
+      if (ipcp_method_dont_insert_const (node))
+	continue;
+      const_param = 0;
+      count = ipa_method_formal_count (node);
+      for (i = 0; i < count; i++)
+	{
+	  type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
+	  if (ipcp_type_is_const (type))
+	    const_param++;
+	}
+      if (const_param == 0)
+	continue;
+      VARRAY_GENERIC_PTR_INIT (replace_trees, const_param, "replace_trees");
+      for (i = 0; i < count; i++)
+	{
+	  type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
+	  if (ipcp_type_is_const (type))
+	    {
+	      cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
+	      parm_tree = ipa_method_get_tree (node, i);
+	      replace_param =
+		ipcp_replace_map_create (type, parm_tree, cvalue);
+	      VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param);
+	    }
+	}
+      /* Compute how many callers node has.  */
+      node_callers = 0;
+      for (cs = node->callers; cs != NULL; cs = cs->next_caller)
+	node_callers++;
+      VARRAY_GENERIC_PTR_INIT (redirect_callers, node_callers,
+			       "redirect_callers");
+      for (cs = node->callers; cs != NULL; cs = cs->next_caller)
+	VARRAY_PUSH_GENERIC_PTR (redirect_callers, cs);
+      /* Redirecting all the callers of the node to the
+         new versioned node.  */
+      node1 =
+	cgraph_function_versioning (node, redirect_callers, replace_trees);
+      VARRAY_CLEAR (redirect_callers);
+      VARRAY_CLEAR (replace_trees);
+      if (node1 == NULL)
+	continue;
+      if (dump_file)
+	fprintf (dump_file, "versioned function %s\n",
+		 cgraph_node_name (node));
+      ipcp_cloned_create (node, node1);
+      for (i = 0; i < count; i++)
+	{
+	  type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
+	  if (ipcp_type_is_const (type))
+	    {
+	      cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
+	      parm_tree = ipa_method_get_tree (node, i);
+	      if (type != CONST_VALUE_REF 
+		  && !TREE_READONLY (parm_tree))
+		ipcp_propagate_const (node1, i, cvalue, type);
+	    }
+	}
+    }
+  ipcp_update_callgraph ();
+  ipcp_update_profiling ();
+}
+
+/* The IPCP driver.  */
+void
+ipcp_driver (void)
+{
+  if (dump_file)
+    fprintf (dump_file, "\nIPA constant propagation start:\n");
+  ipa_nodes_create ();
+  ipa_edges_create ();
+  /* 1. Call the init stage to initialize 
+     the ipa_node and ipa_edge structures.  */
+  ipcp_init_stage ();
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nIPA structures before propagation:\n");
+      ipcp_structures_print (dump_file);
+    }
+  /* 2. Do the interprocedural propagation.  */
+  ipcp_iterate_stage ();
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nIPA structures after propagation:\n");
+      ipcp_structures_print (dump_file);
+      fprintf (dump_file, "\nProfiling info before insert stage:\n");
+      ipcp_profile_print (dump_file);
+    }
+  /* 3. Insert the constants found to the functions.  */
+  ipcp_insert_stage ();
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nProfiling info after insert stage:\n");
+      ipcp_profile_print (dump_file);
+    }
+  /* Free all IPCP structures.  */
+  ipa_free ();
+  ipa_nodes_free ();
+  ipa_edges_free ();
+  if (dump_file)
+    fprintf (dump_file, "\nIPA constant propagation end\n");
+  cgraph_remove_unreachable_nodes (true, NULL);
+}
+
+/* Gate for IPCP optimization.  */
+static bool
+cgraph_gate_cp (void)
+{
+  return flag_ipa_cp;
+}
+
+struct tree_opt_pass pass_ipa_cp = {
+  "cp",				/* name */
+  cgraph_gate_cp,		/* gate */
+  ipcp_driver,			/* execute */
+  NULL,				/* sub */
+  NULL,				/* next */
+  0,				/* static_pass_number */
+  TV_IPA_CONSTANT_PROP,		/* tv_id */
+  0,				/* properties_required */
+  PROP_trees,			/* properties_provided */
+  0,				/* properties_destroyed */
+  0,				/* todo_flags_start */
+  TODO_dump_cgraph | TODO_dump_func,	/* todo_flags_finish */
+  0				/* letter */
+};