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] Fix PR 1687 (C tree inliner related compile time 3.xregression)


Hi,

This fixes exponential behavior in tree-inline.c by walking tree nodes
only once.  I would have prefered to find out why we build such a
horrible tree for this test case, but:
- That does not seem to hurt anything other than the tree-inliner
- It is much harder to fix fold-const and convert, and this patch
  is sufficient improvement, I think :-)

Here's the test case I'll put in c-torture/compile if this
patch is approved.

/*
   This blows up in tree-inline.  Replace '|' with '+', '-', '&' and
   probably one or two other operators and you'll see the same thing.
*/

int in0 ; int in1 ; int in2 ; int in3 ;
int in4 ; int in5 ; int in6 ; int in7 ;
int in8 ; int in9 ; int in10; int in11;
int in12; int in13; int in14; int in15;
unsigned long output;

void mux(void)
{
  output =
      (in0   ?  0x00000001 : 0) | (in1   ?  0x00000002 : 0) |
      (in2   ?  0x00000004 : 0) | (in3   ?  0x00000008 : 0) |
      (in4   ?  0x00000010 : 0) | (in5   ?  0x00000020 : 0) |
      (in6   ?  0x00000040 : 0) | (in7   ?  0x00000080 : 0) |
      (in8   ?  0x00000100 : 0) | (in9   ?  0x00000200 : 0) |
      (in10  ?  0x00000400 : 0) | (in11  ?  0x00000800 : 0) |
      (in12  ?  0x00001000 : 0) | (in13  ?  0x00002000 : 0) |
      (in14  ?  0x00004000 : 0) | (in15  ?  0x00008000 : 0) ;
}

The patch slashes the compile time for this snippet.  Timings for
"cc1 -quiet -O -finline-functions", checking disabled:

Without patch today's CVS:
real    0m12.749s
user    0m12.680s
sys    0m0.040s

With patch:
real    0m0.090s
user    0m0.090s
sys    0m0.000s

Yes, it was _that_ bad!

Booted (with checking) and regtested on i586-pc-linux-gnu with no new
failures.  OK for mainline?

Mark, I don't have a 3.3 tree around anymore, so if this is OK for 3.3,
can you apply it please?


Greetz
Steven


2003-05-02  Steven Bosscher  <steven@gcc.gnu.org>

	* tree-inline.c (find_alloca_call): Use
	walk_tree_without_duplicates, instead of walk_tree.
	(find_builtin_longjmp_call): Ditto.
	* c-objc-common.c (c_cannot_inline_fn): Ditto.

Index: tree-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.c,v
retrieving revision 1.57
diff -c -3 -p -r1.57 tree-inline.c
*** tree-inline.c	1 May 2003 16:13:29 -0000	1.57
--- tree-inline.c	2 May 2003 09:23:48 -0000
*************** find_alloca_call (exp)
*** 902,908 ****
  {
    int line = input_line;
    const char *file = input_filename;
!   tree ret = walk_tree (&exp, find_alloca_call_1, NULL, NULL);
    input_line = line;
    input_filename = file;
    return ret;
--- 902,908 ----
  {
    int line = input_line;
    const char *file = input_filename;
!   tree ret = walk_tree_without_duplicates (&exp, find_alloca_call_1, NULL);
    input_line = line;
    input_filename = file;
    return ret;
*************** find_builtin_longjmp_call (exp)
*** 933,939 ****
  {
    int line = input_line;
    const char *file = input_filename;
!   tree ret = walk_tree (&exp, find_builtin_longjmp_call_1, NULL, NULL);
    input_line = line;
    input_filename = file;
    return ret;
--- 933,940 ----
  {
    int line = input_line;
    const char *file = input_filename;
!   tree ret = walk_tree_without_duplicates
! 		(&exp, find_builtin_longjmp_call_1, NULL);
    input_line = line;
    input_filename = file;
    return ret;
Index: c-objc-common.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-objc-common.c,v
retrieving revision 1.24
diff -c -3 -p -r1.24 c-objc-common.c
*** c-objc-common.c	10 Apr 2003 08:07:10 -0000	1.24
--- c-objc-common.c	2 May 2003 09:24:35 -0000
*************** c_cannot_inline_tree_fn (fnp)
*** 216,222 ****
  	return 0;
      }
      
!   if (walk_tree (&DECL_SAVED_TREE (fn), inline_forbidden_p, fn, NULL))
      goto cannot_inline;
  
    return 0;
--- 216,223 ----
  	return 0;
      }
      
!   if (walk_tree_without_duplicates
! 	(&DECL_SAVED_TREE (fn), inline_forbidden_p, fn))
      goto cannot_inline;
  
    return 0;


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