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]

[C++ PATCH] Serious time and code quality regression with inlining on trees


Hi!

The testcase below takes half a minute to compile, eats ~50MB of RAM and
results in 86KB of code for foo function (non-tree based inlining would give
far below 1KB). A slightly bigger testcase this was simplified into eats
.5GB of RAM, runs a long time and results in several megabytes of code
(although gcc-2.95.2 generates for it code hundreds times smaller). The
result is that mozilla does not seem to build with CVS gcc.
Basically, if there is a loop in the inlining graph, especially if it is not
function a inlines b and b inlines a, then the cut-off point for not
inlining comes too late, because during optimize_function of say foo we may be
attempting to inline a function which has already inlined foo in its saved
tree.
This patch solves this by not inlining a function if it successfully inlined
the function being currently expanded.
Bootstrapped, no regressions.
Ok to commit or should I take a different approach (like if
inlinable_function_p detects a loop, go and mark all functions on the loop
which have not yet been optimized by optimize_function that they cannot
inline function currently being optimized)?

2001-02-21  Jakub Jelinek  <jakub@redhat.com>

	* cp-tree.h (struct lang_decl_inlined_fns): New.
	(struct lang_decls): Add inlined_fns.
	(DECL_INLINED_FNS): New macro.
	* optimize.c (struct inline_data): Add inlined_fns.
	(declare_return_variable): Use VARRAY_ACTIVE_SIZE macro.
	(inlinable_function_p): Likewise, fix typo in comment,
	function is not inlinable if it already inlined function currently
	being optimized.
	(expand_call_inline): Add fn to inlined_fns if neccessary.
	(optimize_function): Initialize inlined_fns.
	Save inlined_fns into DECL_INLINED_FNS after expanding inlines.
	* decl.c (mark_inlined_fns): New function.
	(lang_mark_tree): Call it.

	* g++.old-deja/g++.other/inline20.C: New test.

--- gcc/cp/optimize.c.jj	Mon Feb 19 12:30:36 2001
+++ gcc/cp/optimize.c	Wed Feb 21 17:16:02 2001
@@ -28,6 +28,7 @@ Software Foundation, 59 Temple Place - S
 #include "input.h"
 #include "integrate.h"
 #include "varray.h"
+#include "ggc.h"
 
 /* To Do:
 
@@ -62,6 +63,8 @@ typedef struct inline_data
   int in_target_cleanup_p;
   /* A stack of the TARGET_EXPRs that we are currently processing.  */
   varray_type target_exprs;
+  /* A list of the functions current function has inlined.  */
+  varray_type inlined_fns;
 } inline_data;
 
 /* Prototypes.  */
@@ -520,7 +523,7 @@ declare_return_variable (id, use_stmt)
      references to the RESULT into references to the target.  */
   if (aggregate_return_p)
     {
-      my_friendly_assert (id->target_exprs->elements_used != 0,
+      my_friendly_assert (VARRAY_ACTIVE_SIZE (id->target_exprs) != 0,
 			  20000430);
       var = TREE_OPERAND (VARRAY_TOP_TREE (id->target_exprs), 0);
       my_friendly_assert 
@@ -605,14 +608,23 @@ inlinable_function_p (fn, id)
     inlinable = 0;
 
   /* Don't do recursive inlining, either.  We don't record this in
-     DECL_UNLINABLE; we may be able to inline this function later.  */
+     DECL_UNINLINABLE; we may be able to inline this function later.  */
   if (inlinable)
     {
       size_t i;
 
-      for (i = 0; i < id->fns->elements_used; ++i)
+      for (i = 0; i < VARRAY_ACTIVE_SIZE (id->fns); ++i)
 	if (VARRAY_TREE (id->fns, i) == fn)
-	  inlinable = 0;
+	  return 0;
+
+      if (inlinable && DECL_LANG_SPECIFIC (fn) && DECL_INLINED_FNS (fn))
+	{
+	  struct lang_decl_inlined_fns *ifn = DECL_INLINED_FNS (fn);
+
+	  for (i = 0; i < ifn->num_fns; ++i)
+	    if (ifn->fns [i] == VARRAY_TREE (id->fns, 0))
+	      return 0;
+	}
     }
 
   /* Return the result.  */
@@ -728,6 +740,19 @@ expand_call_inline (tp, walk_subtrees, d
      recursing into it.  */
   VARRAY_PUSH_TREE (id->fns, fn);
 
+  /* Record the function we are about to inline if optimize_function
+     has not been called on it yet and we don't have it in the list.  */
+  if (DECL_LANG_SPECIFIC (fn) && !DECL_INLINED_FNS (fn))
+    {
+      int i;
+
+      for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
+	if (VARRAY_TREE (id->inlined_fns, i) == fn)
+	  break;
+      if (i < 0)
+	VARRAY_PUSH_TREE (id->inlined_fns, fn);
+    }
+
   /* Return statements in the function body will be replaced by jumps
      to the RET_LABEL.  */
   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
@@ -874,6 +899,9 @@ optimize_function (fn)
       /* Create the stack of TARGET_EXPRs.  */
       VARRAY_TREE_INIT (id.target_exprs, 32, "target_exprs");
 
+      /* Create the list of functions this call will inline.  */
+      VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
+
       /* Replace all calls to inline functions with the bodies of those
 	 functions.  */
       expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
@@ -881,6 +909,19 @@ optimize_function (fn)
       /* Clean up.  */
       VARRAY_FREE (id.fns);
       VARRAY_FREE (id.target_exprs);
+      if (DECL_LANG_SPECIFIC (fn))
+	{
+	  struct lang_decl_inlined_fns *ifn;
+
+	  ifn = ggc_alloc (sizeof (struct lang_decl_inlined_fns)
+			   + (VARRAY_ACTIVE_SIZE (id.inlined_fns) - 1)
+			     * sizeof (tree));
+	  ifn->num_fns = VARRAY_ACTIVE_SIZE (id.inlined_fns);
+	  memcpy (&ifn->fns[0], &VARRAY_TREE (id.inlined_fns, 0),
+		  ifn->num_fns * sizeof (tree));
+	  DECL_INLINED_FNS (fn) = ifn;
+	}
+      VARRAY_FREE (id.inlined_fns);
     }
 
   /* Undo the call to ggc_push_context above.  */
--- gcc/cp/cp-tree.h.jj	Mon Feb 19 12:30:36 2001
+++ gcc/cp/cp-tree.h	Wed Feb 21 16:08:31 2001
@@ -1855,6 +1855,12 @@ struct lang_decl_flags
 
 struct unparsed_text;
 
+struct lang_decl_inlined_fns
+{
+  size_t num_fns;
+  tree fns[1];
+};
+
 struct lang_decl
 {
   struct lang_decl_flags decl_flags;
@@ -1868,6 +1874,9 @@ struct lang_decl
   /* In a FUNCTION_DECL, this is DECL_CLONED_FUNCTION.  */
   tree cloned_function;
 
+  /* In a FUNCTION_DECL, this is a list of trees inlined into its body.  */
+  struct lang_decl_inlined_fns *inlined_fns;
+
   union
   {
     tree sorted_fields;
@@ -1977,6 +1986,10 @@ struct lang_decl
    cloned.  */
 #define DECL_CLONED_FUNCTION(NODE) \
   (DECL_LANG_SPECIFIC (NODE)->cloned_function)
+
+/* List of FUNCION_DECLs inlined into this function's body.  */
+#define DECL_INLINED_FNS(NODE) \
+  (DECL_LANG_SPECIFIC (NODE)->inlined_fns)
 
 /* Non-zero if the VTT parm has been added to NODE.  */
 #define DECL_HAS_VTT_PARM_P(NODE) \
--- gcc/cp/decl.c.jj	Mon Feb 19 12:30:36 2001
+++ gcc/cp/decl.c	Wed Feb 21 16:18:30 2001
@@ -14329,6 +14329,19 @@ pop_cp_function_context (f)
   f->language = 0;
 }
 
+/* Mark I for GC.  */
+
+static void
+mark_inlined_fns (i)
+     struct lang_decl_inlined_fns *i;
+{
+  int n;
+
+  for (n = i->num_fns - 1; n >= 0; n--)
+    ggc_mark_tree (i->fns [n]);
+  ggc_set_mark (i);
+}
+
 /* Mark P for GC.  */
 
 static void
@@ -14415,6 +14428,8 @@ lang_mark_tree (t)
 	      ggc_mark_tree (ld->befriending_classes);
 	      ggc_mark_tree (ld->context);
 	      ggc_mark_tree (ld->cloned_function);
+	      if (ld->inlined_fns)
+		mark_inlined_fns (ld->inlined_fns);
 	      if (TREE_CODE (t) == TYPE_DECL)
 		ggc_mark_tree (ld->u.sorted_fields);
 	      else if (TREE_CODE (t) == FUNCTION_DECL
--- gcc/testsuite/g++.old-deja/g++.other/inline20.C.jj	Wed Feb 21 14:08:24 2001
+++ gcc/testsuite/g++.old-deja/g++.other/inline20.C	Wed Feb 21 13:20:09 2001
@@ -0,0 +1,58 @@
+// Build don't link:
+
+struct A {
+  int a, b, c, d;
+};
+
+inline void foo (int, A &);
+
+struct D {
+};
+
+struct E: public D {
+  void f (A &y)
+  {
+    foo (1, y);
+  }
+};
+
+struct F: public D {
+  void f (A &y)
+  {
+    foo (2, y);
+  }
+};
+
+E *d;
+F *e;
+
+inline int baz (int y)
+{
+  A a;
+  if (y) {
+    d->f (a);
+  } else {
+    e->f (a);
+  }
+  return 0;
+}
+
+inline void foo (int y, A &z)
+{
+  z.a = baz (y);
+  z.b = baz (y);
+  z.c = baz (y);
+  z.d = baz (y);
+}
+
+struct G {
+  E a;
+  F b;
+  void bar (A &);
+};
+
+void G::bar(A &y)
+{
+  a.f(y);
+  b.f(y);
+}

	Jakub


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