This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[Patch] Factor self-referential size trees into functions


Hi,

as explained during last year's summit, types with self-referential size exist 
in Ada and can have an arbitrary complexity.  For these types, an object has 
a size that depends on its contents, i.e. on one or more fields present in 
the object.  Technically this means that the TYPE_SIZE is an expression that 
contains one or more PLACEHOLDER_EXPRs and the DECL_SIZE for a particular 
object is obtained by substituting the value of fields in the object for the 
PLACEHOLDER_EXPRs in the expression.  See SUBSTITUTE_PLACEHOLDER_IN_EXPR.

The complexity can quickly grow with multiple levels of self-referentialness.
In this case, the TYPE_SIZE can be a huge expression with dozens of nodes that 
cannot be folded before substitution and may even need to be used directly 
when pointers to these types come into play; it gets copied over and over, 
then gimplified and expanded multiple times, leading to long compilation 
times and bloated code.

The approach proposed in the attached patch (and used for about 3 years in 
AdaCore's compiler) is to factor out these self-referential size trees into 
functions and replace them with call expressions; these expressions are cheap 
to manipulate and copy, and the size functions can be integrated back by the 
inliner if it deems this profitable, otherwise they are emitted or discarded.

The main points of the patch are:

 1. discovery/construction of functions in stor-layout.c:self_referential_size 
invoked through variable_size when PLACEHOLDER_EXPRs are detected, with the 
help of tree.c:find_substitute_in_expr.

 2. more aggressive propagation of TREE_READONLY in expressions.  Expressions 
cannot be factored out if they contain SAVE_EXPRs so superfluous SAVE_EXPRs 
must be eliminated as much as possible by tracking the TREE_READONLYness.

 3. re-integration of size functions into expressions.  This is necessary in a 
few cases to compute properties of types at compile time and is implemented 
as a limited form of inlining on trees.

This should only affect the Ada compiler (although I presume 2. can marginally 
help the other compilers) and dramatically help for code with multiple levels 
of discriminated types (for our favorite example at -O0: code size divided by 
2 and compilation time by 4).

Tested on i586-suse-linux and x86_64-suse-linux, OK for mainline?


2009-06-29  Eric Botcazou  <ebotcazou@adacore.com>

	* cgraphunit.c (cgraph_finalize_compilation_unit): Call
	finalize_size_functions before further processing.
	* stor-layout.c: Include cgraph.h, tree-inline.h and tree-dump.h.
	(variable_size): Call self_referential_size on size expressions
	that contain a PLACEHOLDER_EXPR.
	(size_functions): New static variable.
	(copy_self_referential_tree_r): New static function.
	(self_referential_size): Likewise.
	(finalize_size_functions): New global function.
	* tree.c: Include tree-inline.h.
	(process_call_operands): Propagate TREE_READONLY from the operands.
	(push_without_duplicate): New static function.
	(find_substitute_in_expr): New global function.
	(substitute_in_expr) <tcc_declaration>: Return the replacement object
	on equality.
	<tcc_expression>: Likewise.
	<tcc_vl_exp>: If the replacement object is a constant, try to inline
	the call in the expression.
	(PROCESS_ARG): Do not clear TREE_READONLY if CONSTANT_CLASS_P.
	(build3_stat): Propagate TREE_READONLY for COND_EXPR.
	* tree.h (finalize_size_functions): Declare.
	(find_substitute_in_expr): Likewise.
	(FIND_SUBSTITUTE_IN_EXPR): New macro.
	(substitute_placeholder_in_expr): Update comment.
	* tree-inline.c (remap_decl): Do not unshare trees if do_not_unshare
	is true.
	(remap_gimple_op_r): Likewise.
	(copy_tree_body): New static function.
	(maybe_inline_call_in_expr): New global function.
	* tree-inline.h (struct copy_body_data): Add do_not_unshare field.
	(maybe_inline_call_in_expr): Declare.
	* Makefile.in (tree.o): Depend on TREE_INLINE_H.
	(stor-layout.o): Depend on CGRAPH_H, TREE_INLINE_H, TREE_DUMP_H and
	GIMPLE_H.
ada/
	* gcc-interface/decl.c: Include tree-inline.h.
	(annotate_value) <CALL_EXPR>: Try to inline the call in the expression.
	* gcc-interface/utils.c (max_size) <CALL_EXPR>: Likewise.
	* gcc-interface/utils2.c: Include tree-inline.h.
	(known_alignment) <CALL_EXPR>: Likewise.


-- 
Eric Botcazou
Index: tree.c
===================================================================
--- tree.c	(revision 149023)
+++ tree.c	(working copy)
@@ -45,6 +45,7 @@ along with GCC; see the file COPYING3.
 #include "output.h"
 #include "target.h"
 #include "langhooks.h"
+#include "tree-inline.h"
 #include "tree-iterator.h"
 #include "basic-block.h"
 #include "tree-flow.h"
@@ -2489,28 +2490,29 @@ static void
 process_call_operands (tree t)
 {
   bool side_effects = TREE_SIDE_EFFECTS (t);
+  bool read_only = false;
   int i;
 
-  if (!side_effects)
+  /* Calls have side-effects, except those to const or pure functions.  */
+  i = call_expr_flags (t);
+  if ((i & ECF_LOOPING_CONST_OR_PURE) || !(i & (ECF_CONST | ECF_PURE)))
+    side_effects = true;
+  /* Propagate TREE_READONLY of arguments for const functions.  */
+  if (i & ECF_CONST)
+    read_only = true;
+
+  if (!side_effects || read_only)
     for (i = 1; i < TREE_OPERAND_LENGTH (t); i++)
       {
 	tree op = TREE_OPERAND (t, i);
 	if (op && TREE_SIDE_EFFECTS (op))
-	  {
-	    side_effects = true;
-	    break;
-	  }
+	  side_effects = true;
+	if (op && !TREE_READONLY (op) && !CONSTANT_CLASS_P (op))
+	  read_only = false;
       }
 
-  if (!side_effects)
-    {
-      /* Calls have side-effects, except those to const or pure functions.  */
-      i = call_expr_flags (t);
-      if ((i & ECF_LOOPING_CONST_OR_PURE) || !(i & (ECF_CONST | ECF_PURE)))
-	side_effects = true;
-    }
-
   TREE_SIDE_EFFECTS (t) = side_effects;
+  TREE_READONLY (t) = read_only;
 }
 
 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
@@ -2688,11 +2690,102 @@ type_contains_placeholder_p (tree type)
   return result;
 }
 
+/* Push tree EXP onto vector QUEUE if it is not already present.  */
+
+static void
+push_without_duplicate (tree exp, VEC (tree, heap) **queue)
+{
+  unsigned int i;
+  tree iter;
+
+  for (i = 0; VEC_iterate (tree, *queue, i, iter); i++)
+    if (simple_cst_equal (iter, exp) == 1)
+      break;
+
+  if (!iter)
+    VEC_safe_push (tree, heap, *queue, exp);
+}
+
+/* Given a tree EXP, find all occurences of references to fields
+   in a PLACEHOLDER_EXPR and place them in vector SUBSTS without
+   duplicates.  Also record VAR_DECLs and CONST_DECLs.  Note that
+   we assume here that EXP contains only arithmetic expressions
+   or CALL_EXPRs with PLACEHOLDER_EXPRs occurring only in their
+   argument list.  */
+
+void
+find_substitute_in_expr (tree exp, VEC (tree, heap) **substs)
+{
+  enum tree_code code = TREE_CODE (exp);
+  tree inner;
+  int i;
+
+  /* We handle TREE_LIST and COMPONENT_REF separately.  */
+  if (code == TREE_LIST)
+    {
+      FIND_SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), substs);
+      FIND_SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), substs);
+    }
+  else if (code == COMPONENT_REF)
+    {
+      for (inner = TREE_OPERAND (exp, 0);
+	   REFERENCE_CLASS_P (inner);
+	   inner = TREE_OPERAND (inner, 0))
+	;
+
+      if (TREE_CODE (inner) == PLACEHOLDER_EXPR)
+	push_without_duplicate (exp, substs);
+      else
+	FIND_SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), substs);
+   }
+  else
+    switch (TREE_CODE_CLASS (code))
+      {
+      case tcc_constant:
+	break;
+
+      case tcc_declaration:
+	/* Variables allocated to static storage can stay.  */
+        if (!TREE_STATIC (exp))
+	  push_without_duplicate (exp, substs);
+	break;
+
+      case tcc_expression:
+	/* This is the pattern built in ada/make_aligning_type.  */
+	if (code == ADDR_EXPR
+	    && TREE_CODE (TREE_OPERAND (exp, 0)) == PLACEHOLDER_EXPR)
+	  {
+	    push_without_duplicate (exp, substs);
+	    break;
+	  }
+
+        /* Fall through...  */
+
+      case tcc_exceptional:
+      case tcc_unary:
+      case tcc_binary:
+      case tcc_comparison:
+      case tcc_reference:
+	for (i = 0; i < TREE_CODE_LENGTH (code); i++)
+	  FIND_SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, i), substs);
+	break;
+
+      case tcc_vl_exp:
+	for (i = 1; i < TREE_OPERAND_LENGTH (exp); i++)
+	  FIND_SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, i), substs);
+	break;
+
+      default:
+	gcc_unreachable ();
+      }
+}
+
 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
    return a tree with all occurrences of references to F in a
-   PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
-   contains only arithmetic expressions or a CALL_EXPR with a
-   PLACEHOLDER_EXPR occurring only in its arglist.  */
+   PLACEHOLDER_EXPR replaced by R.  Also handle VAR_DECLs and
+   CONST_DECLs.  Note that we assume here that EXP contains only
+   arithmetic expressions or CALL_EXPRs with PLACEHOLDER_EXPRs
+   occurring only in their argument list.  */
 
 tree
 substitute_in_expr (tree exp, tree f, tree r)
@@ -2743,14 +2836,24 @@ substitute_in_expr (tree exp, tree f, tr
     switch (TREE_CODE_CLASS (code))
       {
       case tcc_constant:
-      case tcc_declaration:
 	return exp;
 
+      case tcc_declaration:
+	if (exp == f)
+	  return r;
+	else
+	  return exp;
+
+      case tcc_expression:
+	if (exp == f)
+	  return r;
+
+        /* Fall through...  */
+
       case tcc_exceptional:
       case tcc_unary:
       case tcc_binary:
       case tcc_comparison:
-      case tcc_expression:
       case tcc_reference:
 	switch (TREE_CODE_LENGTH (code))
 	  {
@@ -2813,6 +2916,17 @@ substitute_in_expr (tree exp, tree f, tr
 
 	  new_tree = NULL_TREE;
 
+	  /* If we are trying to replace F with a constant, inline back
+	     functions which do nothing else than computing a value from
+	     the arguments they are passed.  This makes it possible to
+	     fold partially or entirely the replacement expression.  */
+	  if (CONSTANT_CLASS_P (r) && code == CALL_EXPR)
+	    {
+	      tree t = maybe_inline_call_in_expr (exp);
+	      if (t)
+		return SUBSTITUTE_IN_EXPR (t, f, r);
+	    }
+
 	  for (i = 1; i < TREE_OPERAND_LENGTH (exp); i++)
 	    {
 	      tree op = TREE_OPERAND (exp, i);
@@ -3356,18 +3470,19 @@ build1_stat (enum tree_code code, tree t
   return t;
 }
 
-#define PROCESS_ARG(N)			\
-  do {					\
-    TREE_OPERAND (t, N) = arg##N;	\
-    if (arg##N &&!TYPE_P (arg##N))	\
-      {					\
-        if (TREE_SIDE_EFFECTS (arg##N))	\
-	  side_effects = 1;		\
-        if (!TREE_READONLY (arg##N))	\
-	  read_only = 0;		\
-        if (!TREE_CONSTANT (arg##N))	\
-	  constant = 0;			\
-      }					\
+#define PROCESS_ARG(N)				\
+  do {						\
+    TREE_OPERAND (t, N) = arg##N;		\
+    if (arg##N &&!TYPE_P (arg##N))		\
+      {						\
+        if (TREE_SIDE_EFFECTS (arg##N))		\
+	  side_effects = 1;			\
+        if (!TREE_READONLY (arg##N)		\
+	    && !CONSTANT_CLASS_P (arg##N))	\
+	  read_only = 0;			\
+        if (!TREE_CONSTANT (arg##N))		\
+	  constant = 0;				\
+      }						\
   } while (0)
 
 tree
@@ -3434,6 +3549,8 @@ build3_stat (enum tree_code code, tree t
   t = make_node_stat (code PASS_MEM_STAT);
   TREE_TYPE (t) = tt;
 
+  read_only = 1;
+
   /* As a special exception, if COND_EXPR has NULL branches, we
      assume that it is a gimple statement and always consider
      it to have side effects.  */
@@ -3449,6 +3566,9 @@ build3_stat (enum tree_code code, tree t
   PROCESS_ARG(1);
   PROCESS_ARG(2);
 
+  if (code == COND_EXPR)
+    TREE_READONLY (t) = read_only;
+
   TREE_SIDE_EFFECTS (t) = side_effects;
   TREE_THIS_VOLATILE (t)
     = (TREE_CODE_CLASS (code) == tcc_reference
Index: tree.h
===================================================================
--- tree.h	(revision 149023)
+++ tree.h	(working copy)
@@ -4242,6 +4242,7 @@ extern tree round_down (tree, int);
 extern tree get_pending_sizes (void);
 extern void put_pending_size (tree);
 extern void put_pending_sizes (tree);
+extern void finalize_size_functions (void);
 
 /* Type for sizes of data-type.  */
 
@@ -4387,10 +4388,30 @@ extern bool contains_placeholder_p (cons
 
 extern bool type_contains_placeholder_p (tree);
 
+/* Given a tree EXP, find all occurences of references to fields
+   in a PLACEHOLDER_EXPR and place them in vector SUBSTS without
+   duplicates.  Also record VAR_DECLs and CONST_DECLs.  Note that
+   we assume here that EXP contains only arithmetic expressions
+   or CALL_EXPRs with PLACEHOLDER_EXPRs occurring only in their
+   argument list.  */
+
+extern void find_substitute_in_expr (tree, VEC (tree, heap) **);
+
+/* This macro calls the above function but short-circuits the common
+   case of a constant to save time and also checks for NULL.  */
+
+#define FIND_SUBSTITUTE_IN_EXPR(EXP, V)	\
+do {					\
+  if((EXP) && !TREE_CONSTANT (EXP))	\
+    find_substitute_in_expr (EXP, V);	\
+} while (0)
+
 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
    return a tree with all occurrences of references to F in a
-   PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
-   contains only arithmetic expressions.  */
+   PLACEHOLDER_EXPR replaced by R.  Also handle VAR_DECLs and
+   CONST_DECLs.  Note that we assume here that EXP contains only
+   arithmetic expressions or CALL_EXPRs with PLACEHOLDER_EXPRs
+   occurring only in their argument list.  */
 
 extern tree substitute_in_expr (tree, tree, tree);
 
Index: cgraphunit.c
===================================================================
--- cgraphunit.c	(revision 149023)
+++ cgraphunit.c	(working copy)
@@ -1012,6 +1012,7 @@ cgraph_finalize_compilation_unit (void)
   if (errorcount || sorrycount)
     return;
 
+  finalize_size_functions ();
   finish_aliases_1 ();
 
   if (!quiet_flag)
Index: ada/gcc-interface/utils.c
===================================================================
--- ada/gcc-interface/utils.c	(revision 149023)
+++ ada/gcc-interface/utils.c	(working copy)
@@ -2333,10 +2333,15 @@ max_size (tree exp, bool max_p)
     case tcc_vl_exp:
       if (code == CALL_EXPR)
 	{
-	  tree *argarray;
-	  int i, n = call_expr_nargs (exp);
-	  gcc_assert (n > 0);
+	  tree t, *argarray;
+	  int n, i;
+
+	  t = maybe_inline_call_in_expr (exp);
+	  if (t)
+	    return max_size (t, max_p);
 
+	  n = call_expr_nargs (exp);
+	  gcc_assert (n > 0);
 	  argarray = (tree *) alloca (n * sizeof (tree));
 	  for (i = 0; i < n; i++)
 	    argarray[i] = max_size (CALL_EXPR_ARG (exp, i), max_p);
Index: ada/gcc-interface/decl.c
===================================================================
--- ada/gcc-interface/decl.c	(revision 149023)
+++ ada/gcc-interface/decl.c	(working copy)
@@ -33,6 +33,7 @@
 #include "ggc.h"
 #include "target.h"
 #include "expr.h"
+#include "tree-inline.h"
 
 #include "ada.h"
 #include "types.h"
@@ -7190,6 +7191,15 @@ annotate_value (tree gnu_size)
     case EQ_EXPR:		tcode = Eq_Expr; break;
     case NE_EXPR:		tcode = Ne_Expr; break;
 
+    case CALL_EXPR:
+      {
+	tree t = maybe_inline_call_in_expr (gnu_size);
+	if (t)
+	  return annotate_value (t);
+      }
+
+      /* Fall through... */
+
     default:
       return No_Uint;
     }
Index: ada/gcc-interface/utils2.c
===================================================================
--- ada/gcc-interface/utils2.c	(revision 149023)
+++ ada/gcc-interface/utils2.c	(working copy)
@@ -31,6 +31,7 @@
 #include "ggc.h"
 #include "flags.h"
 #include "output.h"
+#include "tree-inline.h"
 
 #include "ada.h"
 #include "types.h"
@@ -215,6 +216,15 @@ known_alignment (tree exp)
       this_alignment = expr_align (TREE_OPERAND (exp, 0));
       break;
 
+    case CALL_EXPR:
+      {
+	tree t = maybe_inline_call_in_expr (exp);
+	if (t)
+	  return known_alignment (t);
+      }
+
+      /* Fall through... */
+
     default:
       /* For other pointer expressions, we assume that the pointed-to object
 	 is at least as aligned as the pointed-to type.  Beware that we can
Index: stor-layout.c
===================================================================
--- stor-layout.c	(revision 149023)
+++ stor-layout.c	(working copy)
@@ -37,6 +37,10 @@ along with GCC; see the file COPYING3.
 #include "langhooks.h"
 #include "regs.h"
 #include "params.h"
+#include "cgraph.h"
+#include "tree-inline.h"
+#include "tree-dump.h"
+#include "gimple.h"
 
 /* Data type for the expressions representing sizes of data types.
    It is the first integer type laid out.  */
@@ -53,6 +57,7 @@ unsigned int initial_max_fld_align = TAR
    called only by a front end.  */
 static int reference_types_internal = 0;
 
+static tree self_referential_size (tree);
 static void finalize_record_size (record_layout_info);
 static void finalize_type_size (tree);
 static void place_union_field (record_layout_info, tree);
@@ -117,13 +122,19 @@ variable_size (tree size)
 {
   tree save;
 
+  /* Obviously.  */
+  if (TREE_CONSTANT (size))
+    return size;
+
+  /* If the size is self-referential, we can't make a SAVE_EXPR (see
+     save_expr for the rationale).  But we can do something else.  */
+  if (CONTAINS_PLACEHOLDER_P (size))
+    return self_referential_size (size);
+
   /* If the language-processor is to take responsibility for variable-sized
      items (e.g., languages which have elaboration procedures like Ada),
-     just return SIZE unchanged.  Likewise for self-referential sizes and
-     constant sizes.  */
-  if (TREE_CONSTANT (size)
-      || lang_hooks.decls.global_bindings_p () < 0
-      || CONTAINS_PLACEHOLDER_P (size))
+     just return SIZE unchanged.  */
+  if (lang_hooks.decls.global_bindings_p () < 0)
     return size;
 
   size = save_expr (size);
@@ -157,6 +168,206 @@ variable_size (tree size)
 
   return size;
 }
+
+/* An array of functions used for self-referential size computation.  */
+static GTY(()) VEC (tree, gc) *size_functions;
+
+/* Similar to copy_tree_r but do not copy component references involving
+   PLACEHOLDER_EXPRs.  These nodes are spotted in find_substitute_in_expr
+   and substituted in substitute_in_expr.  */
+
+static tree
+copy_self_referential_tree_r (tree *tp, int *walk_subtrees, void *data)
+{
+  enum tree_code code = TREE_CODE (*tp);
+
+  /* Stop at types, decls, constants like copy_tree_r.  */
+  if (TREE_CODE_CLASS (code) == tcc_type
+      || TREE_CODE_CLASS (code) == tcc_declaration
+      || TREE_CODE_CLASS (code) == tcc_constant)
+    {
+      *walk_subtrees = 0;
+      return NULL_TREE;
+    }
+
+  /* This is the pattern built in ada/make_aligning_type.  */
+  else if (code == ADDR_EXPR
+	   && TREE_CODE (TREE_OPERAND (*tp, 0)) == PLACEHOLDER_EXPR)
+    {
+      *walk_subtrees = 0;
+      return NULL_TREE;
+    }
+
+  /* Default case: the component reference.  */
+  else if (code == COMPONENT_REF)
+    {
+      tree inner;
+      for (inner = TREE_OPERAND (*tp, 0);
+	   REFERENCE_CLASS_P (inner);
+	   inner = TREE_OPERAND (inner, 0))
+	;
+
+      if (TREE_CODE (inner) == PLACEHOLDER_EXPR)
+	{
+	  *walk_subtrees = 0;
+	  return NULL_TREE;
+	}
+    }
+
+  /* We're not supposed to have them in self-referential size trees
+     because we wouldn't properly control when they are evaluated.
+     However, not creating superfluous SAVE_EXPRs requires accurate
+     tracking of readonly-ness all the way down to here, which we
+     cannot always guarantee in practice.  So punt in this case.  */
+  else if (code == SAVE_EXPR)
+    return error_mark_node;
+
+  return copy_tree_r (tp, walk_subtrees, data);
+}
+
+/* Given a SIZE expression that is self-referential, return an equivalent
+   expression to serve as the actual size expression for a type.  */
+
+static tree
+self_referential_size (tree size)
+{
+  static unsigned HOST_WIDE_INT fnno = 0;
+  VEC (tree, heap) *self_refs = NULL;
+  tree param_type_list = NULL, param_decl_list = NULL, arg_list = NULL;
+  tree t, ref, return_type, fntype, fnname, fndecl;
+  unsigned int i;
+  char buf[128];
+
+  /* Do not factor out simple operations.  */
+  t = skip_simple_arithmetic (size);
+  if (TREE_CODE (t) == CALL_EXPR)
+    return size;
+
+  /* Collect the list of self-references in the expression.  */
+  find_substitute_in_expr (size, &self_refs);
+  gcc_assert (VEC_length (tree, self_refs) > 0);
+
+  /* Obtain a private copy of the expression.  */
+  t = size;
+  if (walk_tree (&t, copy_self_referential_tree_r, NULL, NULL))
+    return size;
+  size = t;
+
+  /* Build the parameter and argument lists in parallel; also
+     substitute the former for the latter in the expression.  */
+  for (i = 0; VEC_iterate (tree, self_refs, i, ref); i++)
+    {
+      tree subst, param_name, param_type, param_decl;
+
+      if (DECL_P (ref))
+	{
+	  /* We shouldn't have true variables here.  */
+	  gcc_assert (TREE_READONLY (ref));
+	  subst = ref;
+	}
+      /* This is the pattern built in ada/make_aligning_type.  */
+      else if (TREE_CODE (ref) == ADDR_EXPR)
+        subst = ref;
+      /* Default case: the component reference.  */
+      else
+	subst = TREE_OPERAND (ref, 1);
+
+      sprintf (buf, "p%d", i);
+      param_name = get_identifier (buf);
+      param_type = TREE_TYPE (ref);
+      param_decl
+	= build_decl (input_location, PARM_DECL, param_name, param_type);
+      if (targetm.calls.promote_prototypes (NULL_TREE)
+	  && INTEGRAL_TYPE_P (param_type)
+	  && TYPE_PRECISION (param_type) < TYPE_PRECISION (integer_type_node))
+	DECL_ARG_TYPE (param_decl) = integer_type_node;
+      else
+	DECL_ARG_TYPE (param_decl) = param_type;
+      DECL_ARTIFICIAL (param_decl) = 1;
+      TREE_READONLY (param_decl) = 1;
+
+      size = substitute_in_expr (size, subst, param_decl);
+
+      param_type_list = tree_cons (NULL_TREE, param_type, param_type_list);
+      param_decl_list = chainon (param_decl, param_decl_list);
+      arg_list = tree_cons (NULL_TREE, ref, arg_list);
+    }
+
+  VEC_free (tree, heap, self_refs);
+
+  /* Append 'void' to indicate that the number of parameters is fixed.  */
+  param_type_list = tree_cons (NULL_TREE, void_type_node, param_type_list);
+
+  /* The 3 lists have been created in reverse order.  */
+  param_type_list = nreverse (param_type_list);
+  param_decl_list = nreverse (param_decl_list);
+  arg_list = nreverse (arg_list);
+
+  /* Build the function type.  */
+  return_type = TREE_TYPE (size);
+  fntype = build_function_type (return_type, param_type_list);
+
+  /* Build the function declaration.  */
+  sprintf (buf, "SZ"HOST_WIDE_INT_PRINT_UNSIGNED, fnno++);
+  fnname = get_file_function_name (buf);
+  fndecl = build_decl (input_location, FUNCTION_DECL, fnname, fntype);
+  for (t = param_decl_list; t; t = TREE_CHAIN (t))
+    DECL_CONTEXT (t) = fndecl;
+  DECL_ARGUMENTS (fndecl) = param_decl_list;
+  DECL_RESULT (fndecl)
+    = build_decl (input_location, RESULT_DECL, 0, return_type);
+  DECL_CONTEXT (DECL_RESULT (fndecl)) = fndecl;
+
+  /* The function has been created by the compiler and we don't
+     want to emit debug info for it.  */
+  DECL_ARTIFICIAL (fndecl) = 1;
+  DECL_IGNORED_P (fndecl) = 1;
+
+  /* It is supposed to be "const" and never throw.  */
+  TREE_READONLY (fndecl) = 1;
+  TREE_NOTHROW (fndecl) = 1;
+
+  /* We want it to be inlined when this is deemed profitable, as
+     well as discarded if every call has been integrated.  */
+  DECL_DECLARED_INLINE_P (fndecl) = 1;
+
+  /* It is made up of a unique return statement.  */
+  DECL_INITIAL (fndecl) = make_node (BLOCK);
+  BLOCK_SUPERCONTEXT (DECL_INITIAL (fndecl)) = fndecl;
+  t = build2 (MODIFY_EXPR, return_type, DECL_RESULT (fndecl), size);
+  DECL_SAVED_TREE (fndecl) = build1 (RETURN_EXPR, void_type_node, t);
+  TREE_STATIC (fndecl) = 1;
+
+  /* Put it onto the list of size functions.  */
+  VEC_safe_push (tree, gc, size_functions, fndecl);
+
+  /* Replace the original expression with a call to the size function.  */
+  return build_function_call_expr (fndecl, arg_list);
+}
+
+/* Take, queue and compile all the size functions.  It is essential that
+   the size functions be gimplified at the very end of the compilation
+   in order to guarantee transparent handling of self-referential sizes.
+   Otherwise the GENERIC inliner would not be able to inline them back
+   at each of their call sites, thus creating artificial non-constant
+   size expressions which would trigger nasty problems later on.  */
+
+void
+finalize_size_functions (void)
+{
+  unsigned int i;
+  tree fndecl;
+
+  for (i = 0; VEC_iterate(tree, size_functions, i, fndecl); i++)
+    {
+      dump_function (TDI_original, fndecl);
+      gimplify_function_tree (fndecl);
+      dump_function (TDI_generic, fndecl);
+      cgraph_finalize_function (fndecl, false);
+    }
+
+  VEC_free (tree, gc, size_functions);
+}
 
 #ifndef MAX_FIXED_MODE_SIZE
 #define MAX_FIXED_MODE_SIZE GET_MODE_BITSIZE (DImode)
Index: tree-inline.c
===================================================================
--- tree-inline.c	(revision 149023)
+++ tree-inline.c	(working copy)
@@ -287,7 +287,10 @@ remap_decl (tree decl, copy_body_data *i
       return t;
     }
 
-  return unshare_expr (*n);
+  if (id->do_not_unshare)
+    return *n;
+  else
+    return unshare_expr (*n);
 }
 
 static tree
@@ -768,7 +771,10 @@ remap_gimple_op_r (tree *tp, int *walk_s
 		 fold_indirect_ref does other useful transformations,
 		 try that first, though.  */
 	      type = TREE_TYPE (TREE_TYPE (*n));
-	      new_tree = unshare_expr (*n);
+	      if (id->do_not_unshare)
+		new_tree = *n;
+	      else
+		new_tree = unshare_expr (*n);
 	      old = *tp;
 	      *tp = gimple_fold_indirect_ref (new_tree);
 	      if (!*tp)
@@ -1993,6 +1999,21 @@ copy_cfg_body (copy_body_data * id, gcov
   return new_fndecl;
 }
 
+/* Make a copy of the body of FN so that it can be inserted inline in
+   another function.  */
+
+static tree
+copy_tree_body (copy_body_data *id)
+{
+  tree body;
+  tree fndecl = id->src_fn;
+
+  body = DECL_SAVED_TREE (fndecl);
+  walk_tree (&body, copy_tree_body_r, id, NULL);
+
+  return body;
+}
+
 static tree
 copy_body (copy_body_data *id, gcov_type count, int frequency,
 	   basic_block entry_block_map, basic_block exit_block_map)
@@ -4605,6 +4626,60 @@ tree_function_versioning (tree old_decl,
   return;
 }
 
+ /* EXP is CALL_EXPR present in a GENERIC expression tree.  Try
+    to integrate it and return the inlined body on success.  */
+ 
+ tree
+ maybe_inline_call_in_expr (tree exp)
+ {
+   tree fn = get_callee_fndecl (exp);
+ 
+   /* We can only try to inline "const" functions.  */
+   if (fn && TREE_READONLY (fn) && DECL_SAVED_TREE (fn))
+     {
+       struct pointer_map_t *decl_map = pointer_map_create ();
+       call_expr_arg_iterator iter;
+       copy_body_data id;
+       tree param, arg, t;
+ 
+       /* Remap the parameters.  */
+       for (param = DECL_ARGUMENTS (fn), arg = first_call_expr_arg (exp, &iter);
+ 	   param;
+ 	   param = TREE_CHAIN (param), arg = next_call_expr_arg (&iter))
+ 	*pointer_map_insert (decl_map, param) = arg;
+ 
+       memset (&id, 0, sizeof (id));
+       id.src_fn = fn;
+       id.dst_fn = current_function_decl;
+       id.src_cfun = DECL_STRUCT_FUNCTION (fn);
+       id.decl_map = decl_map;
+ 
+       id.copy_decl = copy_decl_no_change;
+       id.transform_call_graph_edges = CB_CGE_DUPLICATE;
+       id.transform_new_cfg = false;
+       id.transform_return_to_modify = true;
+       id.transform_lang_insert_block = false;
+ 
+       /* Make sure not to unshare trees behind the front-end's back
+ 	 since front-end specific mechanisms may rely on sharing.  */
+       id.regimplify = false;
+       id.do_not_unshare = true;
+ 
+       /* We're not inside any EH region.  */
+       id.eh_region = -1;
+ 
+       t = copy_tree_body (&id);
+       pointer_map_destroy (decl_map);
+ 
+       /* We can only return something suitable for use
+ 	 in a GENERIC expression tree.  */
+       if (TREE_CODE (t) == MODIFY_EXPR)
+ 	return TREE_OPERAND (t, 1);
+     }
+
+   return NULL_TREE;
+}
+
 /* Duplicate a type, fields and all.  */
 
 tree
Index: tree-inline.h
===================================================================
--- tree-inline.h	(revision 149023)
+++ tree-inline.h	(working copy)
@@ -102,6 +102,9 @@ typedef struct copy_body_data
   /* True if this statement will need to be regimplified.  */
   bool regimplify;
 
+  /* True if trees should not be unshared.  */
+  bool do_not_unshare;
+
   /* > 0 if we are remapping a type currently.  */
   int remapping_type_depth;
 
@@ -157,6 +160,7 @@ extern tree copy_tree_body_r (tree *, in
 extern void insert_decl_map (copy_body_data *, tree, tree);
 
 unsigned int optimize_inline_calls (tree);
+tree maybe_inline_call_in_expr (tree);
 bool tree_inlinable_function_p (tree);
 tree copy_tree_r (tree *, int *, void *);
 tree copy_decl_no_change (tree decl, copy_body_data *id);
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 149023)
+++ Makefile.in	(working copy)
@@ -2126,8 +2126,8 @@ langhooks.o : langhooks.c $(CONFIG_H) $(
 tree.o : tree.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
    all-tree.def $(FLAGS_H) $(FUNCTION_H) $(PARAMS_H) \
    $(TOPLEV_H) $(GGC_H) $(HASHTAB_H) $(TARGET_H) output.h $(TM_P_H) langhooks.h \
-   $(REAL_H) gt-tree.h tree-iterator.h $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
-   $(OBSTACK_H) pointer-set.h fixed-value.h
+   $(REAL_H) gt-tree.h $(TREE_INLINE_H) tree-iterator.h $(BASIC_BLOCK_H) \
+   $(TREE_FLOW_H) $(OBSTACK_H) pointer-set.h fixed-value.h
 tree-dump.o: tree-dump.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TREE_H) langhooks.h $(TOPLEV_H) $(SPLAY_TREE_H) $(TREE_DUMP_H) \
    tree-iterator.h $(TREE_PASS_H) $(DIAGNOSTIC_H) $(REAL_H) fixed-value.h
@@ -2143,7 +2143,7 @@ print-tree.o : print-tree.c $(CONFIG_H)
 stor-layout.o : stor-layout.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TREE_H) $(PARAMS_H) $(FLAGS_H) $(FUNCTION_H) $(EXPR_H) output.h $(RTL_H) \
    $(GGC_H) $(TM_P_H) $(TARGET_H) langhooks.h $(REGS_H) gt-stor-layout.h \
-   $(TOPLEV_H)
+   $(TOPLEV_H) $(CGRAPH_H) $(TREE_INLINE_H) $(TREE_DUMP_H) $(GIMPLE_H)
 tree-ssa-structalias.o: tree-ssa-structalias.c \
    $(SYSTEM_H) $(CONFIG_H) coretypes.h $(TM_H) $(GGC_H) $(OBSTACK_H) $(BITMAP_H) \
    $(FLAGS_H) $(RTL_H) $(TM_P_H) hard-reg-set.h $(BASIC_BLOCK_H) output.h \

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]