tree inlining and alloca

tree inlining and alloca

[Jan Hubicka]

Hi,
I've just noticed that my callgraph inlinig patch causes SPEC2000 GCC to
require 2GB of memory instead of 256MB it required previously.  The reason is
that function that does use alloca got inlined so the alloca blocks are not
garbagecollected as the programmer intended and we allocate O(n^4) instead of
O(n^2) memory!

The comment in tree-inline mentiones that we used to refuse to inline functions
that do call alloca and i think we still should for this very reason.

Bootstrap/regtesting on mainline in progress.  OK if it passes?
What about 3.2 branch?

Honza

Sat Nov 16 19:20:16 CET 2002  Jan Hubicka  <jh@suse.cz>
	* calls.c (find_alloca): New static function.
	(call_alloca_p): New global function.
	* tree.h (call_alloca_p): New.
	* tree-inline.c (inlinable_function_p):  Do not inline when
	function calls alloca.
Index: calls.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/calls.c,v
retrieving revision 1.242
diff -c -3 -p -r1.242 calls.c
*** calls.c	11 Nov 2002 03:13:17 -0000	1.242
--- calls.c	16 Nov 2002 18:19:10 -0000
*************** static rtx emit_library_call_value_1 		P
*** 219,224 ****
--- 219,225 ----
  							 enum machine_mode,
  							 int, va_list));
  static int special_function_p			PARAMS ((tree, int));
+ static tree find_alloca				PARAMS ((tree *, int *, void *));
  static int flags_from_decl_or_type 		PARAMS ((tree));
  static rtx try_to_integrate			PARAMS ((tree, tree, rtx,
  							 int, tree, rtx));
*************** setjmp_call_p (fndecl)
*** 799,804 ****
--- 800,831 ----
       tree fndecl;
  {
    return special_function_p (fndecl, 0) & ECF_RETURNS_TWICE;
+ }
+ 
+ /* if *TP is possibly call to alloca, return nonzero.  */
+ static tree
+ find_alloca (tp, walk_subtrees, data)
+      tree *tp;
+      int *walk_subtrees ATTRIBUTE_UNUSED;
+      void *data ATTRIBUTE_UNUSED;
+ {
+   tree exp = *tp;
+   if (TREE_CODE (exp) == CALL_EXPR
+       && TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR
+       && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (exp, 0), 0))
+ 	  == FUNCTION_DECL)
+       && (special_function_p (TREE_OPERAND (TREE_OPERAND (exp, 0), 0),
+ 			      0) & ECF_MAY_BE_ALLOCA))
+     return exp;
+   return NULL;
+ }
+ 
+ /* Return true when exp contains alloca call.  */
+ bool
+ call_alloca_p (exp)
+      tree exp;
+ {
+   return walk_tree (&exp, find_alloca, NULL, NULL);
  }
  
  /* Detect flags (function attributes) from the function decl or type node.  */
Index: tree-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.c,v
retrieving revision 1.35
diff -c -3 -p -r1.35 tree-inline.c
*** tree-inline.c	14 Nov 2002 21:58:35 -0000	1.35
--- tree-inline.c	16 Nov 2002 18:19:14 -0000
*************** inlinable_function_p (fn, id)
*** 897,902 ****
--- 897,908 ----
    else if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn)
  	   && currfn_insns > MAX_INLINE_INSNS_SINGLE)
      ;
+   /* Refuse to inline alloca call unless user explicitly forced so as this may
+      change program's memory overhead drastically when the function using alloca
+      is called in loop.  In GCC present in SPEC2000 inlining into schedule_block
+      cause it to require 2GB of ram instead of 256MB.  */
+   else if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)) == NULL
+ 	   && call_alloca_p (DECL_SAVED_TREE (fn)))
    /* All is well.  We can inline this function.  Traditionally, GCC
       has refused to inline functions using alloca, or functions whose
       values are returned in a PARALLEL, and a few other such obscure
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.361
diff -c -3 -p -r1.361 tree.h
*** tree.h	14 Nov 2002 21:58:35 -0000	1.361
--- tree.h	16 Nov 2002 18:19:16 -0000
*************** extern rtx emit_line_note		PARAMS ((cons
*** 3018,3023 ****
--- 3018,3024 ----
  /* In calls.c */
  
  extern int setjmp_call_p		PARAMS ((tree));
+ extern bool call_alloca_p		PARAMS ((tree));
  
  /* In attribs.c.  */
  

Re: tree inlining and alloca

[Geoff Keating]

Jan Hubicka <jh@suse.cz> writes:

> Hi,
> I've just noticed that my callgraph inlinig patch causes SPEC2000 GCC to
> require 2GB of memory instead of 256MB it required previously.  The reason is
> that function that does use alloca got inlined so the alloca blocks are not
> garbagecollected as the programmer intended and we allocate O(n^4) instead of
> O(n^2) memory!
> 
> The comment in tree-inline mentiones that we used to refuse to inline functions
> that do call alloca and i think we still should for this very reason.
> 
> Bootstrap/regtesting on mainline in progress.  OK if it passes?
> What about 3.2 branch?

OK for mainline.  I think 3.2 branch is closed.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: tree inlining and alloca

[Gerald Pfeifer]

On Sat, 16 Nov 2002, Geoff Keating wrote:
>> I've just noticed that my callgraph inlinig patch causes SPEC2000 GCC
>> to require 2GB of memory instead of 256MB it required previously.  The
>> reason is that function that does use alloca got inlined so the alloca
>> blocks are not garbagecollected as the programmer intended and we
>> allocate O(n^4) instead of O(n^2) memory!
>> [...]
>> Bootstrap/regtesting on mainline in progress.  OK if it passes?
>> What about 3.2 branch?
> OK for mainline.  I think 3.2 branch is closed.

No longer. ;-)

Is Jan's patch fine for 3.2.2?

Gerald
-- 
Gerald "Jerry" pfeifer@dbai.tuwien.ac.at http://www.dbai.tuwien.ac.at/~pfeifer/

Re: tree inlining and alloca

[Geoff Keating]

> Date: Fri, 22 Nov 2002 21:30:37 +0100 (CET)
> From: Gerald Pfeifer <pfeifer@dbai.tuwien.ac.at>
> Cc: Jan Hubicka <jh@suse.cz>, "" <gcc-patches@gcc.gnu.org>
> X-OriginalArrivalTime: 22 Nov 2002 20:30:18.0078 (UTC) FILETIME=[F8A60FE0:01C29265]
> 
> On Sat, 16 Nov 2002, Geoff Keating wrote:
> >> I've just noticed that my callgraph inlinig patch causes SPEC2000 GCC
> >> to require 2GB of memory instead of 256MB it required previously.  The
> >> reason is that function that does use alloca got inlined so the alloca
> >> blocks are not garbagecollected as the programmer intended and we
> >> allocate O(n^4) instead of O(n^2) memory!
> >> [...]
> >> Bootstrap/regtesting on mainline in progress.  OK if it passes?
> >> What about 3.2 branch?
> > OK for mainline.  I think 3.2 branch is closed.
> 
> No longer. ;-)
> 
> Is Jan's patch fine for 3.2.2?

Yes.  It's a regression and the patch is in mainline.

-- 
- Geoffrey Keating <geoffk@geoffk.org>