Patchwork New badness metric for inliner

login
register
mail settings
Submitter Jan Hubicka
Date Nov. 6, 2012, 6:21 p.m.
Message ID <20121106182146.GA13455@kam.mff.cuni.cz>
Download mbox | patch
Permalink /patch/197531/
State New
Headers show

Comments

Jan Hubicka - Nov. 6, 2012, 6:21 p.m.
> 
> This broke the bootstrap on sparc:
> 
> /home/davem/src/GIT/GCC/build-sparc32-linux/./prev-gcc/g++ -B/home/davem/src/GIT/GCC/build-sparc32\
> -linux/./prev-gcc/ -B/usr/local/sparc-unknown-linux-gnu/bin/ -nostdinc++ -B/home/davem/src/GIT/GCC\
> /build-sparc32-linux/prev-sparc-unknown-linux-gnu/libstdc++-v3/src/.libs -B/home/davem/src/GIT/GCC\
> /build-sparc32-linux/prev-sparc-unknown-linux-gnu/libstdc++-v3/libsupc++/.libs -I/home/davem/src/G\
> IT/GCC/build-sparc32-linux/prev-sparc-unknown-linux-gnu/libstdc++-v3/include/sparc-unknown-linux-g\
> nu -I/home/davem/src/GIT/GCC/build-sparc32-linux/prev-sparc-unknown-linux-gnu/libstdc++-v3/include\
>  -I/home/davem/src/GIT/GCC/gcc/libstdc++-v3/libsupc++ -L/home/davem/src/GIT/GCC/build-sparc32-linu\
> x/prev-sparc-unknown-linux-gnu/libstdc++-v3/src/.libs -L/home/davem/src/GIT/GCC/build-sparc32-linu\
> x/prev-sparc-unknown-linux-gnu/libstdc++-v3/libsupc++/.libs -c   -g -O2 -gtoggle -DIN_GCC   -fno-e\
> xceptions -fno-rtti -fasynchronous-unwind-tables -W -Wall -Wno-narrowing -Wwrite-strings -Wcast-qu\
> al -Wmissing-format-attribute -pedantic -Wno-long-long -Wno-variadic-macros -Wno-overlength-string\
> s -Werror -fno-common  -DHAVE_CONFIG_H -I. -I. -I../../gcc/gcc -I../../gcc/gcc/. -I../../gcc/gcc/.\
> ./include -I../../gcc/gcc/../libcpp/include  -I../../gcc/gcc/../libdecnumber -I../../gcc/gcc/../li\
> bdecnumber/dpd -I../libdecnumber -I../../gcc/gcc/../libbacktrace -DCLOOG_INT_GMP    ../../gcc/gcc/\
> graphite-interchange.c -o graphite-interchange.o
> ../../gcc/gcc/graphite-interchange.c:645:1: internal compiler error: in relative_time_benefit, at \
> ipa-inline.c:784
The problem here is really that MAX_TIME * MAX_FREQ do not fit into 32bit integer. Fixed thus.

	* ipa-inline.c (compute_uninlined_call_time): Return gcov_type.
	(compute_inlined_call_time): Watch overflows.
	(relative_time_benefit): Compute in gcov_type.
David Miller - Nov. 6, 2012, 6:26 p.m.
From: Jan Hubicka <hubicka@ucw.cz>
Date: Tue, 6 Nov 2012 19:21:46 +0100

> The problem here is really that MAX_TIME * MAX_FREQ do not fit into 32bit integer. Fixed thus.
> 
> 	* ipa-inline.c (compute_uninlined_call_time): Return gcov_type.
> 	(compute_inlined_call_time): Watch overflows.
> 	(relative_time_benefit): Compute in gcov_type.

Thanks Jan, I'll test this right now.
David Miller - Nov. 6, 2012, 6:54 p.m.
From: David Miller <davem@davemloft.net>
Date: Tue, 06 Nov 2012 13:26:53 -0500 (EST)

> From: Jan Hubicka <hubicka@ucw.cz>
> Date: Tue, 6 Nov 2012 19:21:46 +0100
> 
>> The problem here is really that MAX_TIME * MAX_FREQ do not fit into 32bit integer. Fixed thus.
>> 
>> 	* ipa-inline.c (compute_uninlined_call_time): Return gcov_type.
>> 	(compute_inlined_call_time): Watch overflows.
>> 	(relative_time_benefit): Compute in gcov_type.
> 
> Thanks Jan, I'll test this right now.

Bootstrap still fails with this change installed:

../../gcc/gcc/graphite-interchange.c:645:1: internal compiler error: in relative_time_benefit, at \
ipa-inline.c:785
 }
 ^
0x108289f relative_time_benefit
        ../../gcc/gcc/ipa-inline.c:785
0x1082fcb edge_badness
        ../../gcc/gcc/ipa-inline.c:895
0x108372f update_edge_key
        ../../gcc/gcc/ipa-inline.c:963
0x10840db update_callee_keys
        ../../gcc/gcc/ipa-inline.c:1142
0x1085b47 inline_small_functions
        ../../gcc/gcc/ipa-inline.c:1595
0x10864f7 ipa_inline
        ../../gcc/gcc/ipa-inline.c:1770
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.
make[3]: *** [graphite-interchange.o] Error 1
make[3]: *** Waiting for unfinished jobs....
make[2]: *** [all-stage2-gcc] Error 2
make[1]: *** [stage2-bubble] Error 2
make: *** [all] Error 2

And as Toon pointed out, even x86-64 is seeing this problem, so something
other than the size of the datum holding the value is at work here.
David Miller - Nov. 6, 2012, 7:16 p.m.
From: David Miller <davem@davemloft.net>
Date: Tue, 06 Nov 2012 13:54:01 -0500 (EST)

> From: David Miller <davem@davemloft.net>
> Date: Tue, 06 Nov 2012 13:26:53 -0500 (EST)
> 
>> From: Jan Hubicka <hubicka@ucw.cz>
>> Date: Tue, 6 Nov 2012 19:21:46 +0100
>> 
>>> The problem here is really that MAX_TIME * MAX_FREQ do not fit into 32bit integer. Fixed thus.
>>> 
>>> 	* ipa-inline.c (compute_uninlined_call_time): Return gcov_type.
>>> 	(compute_inlined_call_time): Watch overflows.
>>> 	(relative_time_benefit): Compute in gcov_type.
>> 
>> Thanks Jan, I'll test this right now.
> 
> Bootstrap still fails with this change installed:
> 
> ../../gcc/gcc/graphite-interchange.c:645:1: internal compiler error: in relative_time_benefit, at \
> ipa-inline.c:785
>  }

The problem appears to be that inline_summary (edge->caller)->time
is negative.

#1  0x010828a0 in relative_time_benefit (callee_info=0xf76fcb10, edge=0xf598a980, edge_time=3861) \
at ../../gcc/gcc/ipa-inline.c:785
(gdb) p callee_info->time
$1200 = 3864
(gdb) p edge->frequency
$1201 = 263
(gdb) p (callee_info->time * edge->frequency)
$1202 = 1016232
(gdb) p edge->caller->global.inlined_to
$1203 = (cgraph_node *) 0x0
(gdb) p edge->caller
$1204 = (cgraph_node *) 0xf589ed10
(gdb) p p inline_summary (edge->caller)->time
No symbol "p" in current context.
(gdb) p inline_summary (edge->caller)->time
$1205 = -1044761
(gdb)
David Miller - Nov. 6, 2012, 7:28 p.m.
From: David Miller <davem@davemloft.net>
Date: Tue, 06 Nov 2012 14:16:32 -0500 (EST)

> (gdb) p inline_summary (edge->caller)->time
> $1205 = -1044761

This negative value is computed by inline_update_overall_summary().

I added some debugging to dump the entry->time values processed when
info->time goes negative:

davem@patience:~/src/GIT/GCC/build-sparc32-linux/prev-gcc$ ./cc1plus -quiet -g -O2 -o x.s graphite-interchange.i
e[19]: time[0]
e[19]: time[3996]
e[19]: time[4000]
e[19]: time[1960]
e[19]: time[7840]
e[19]: time[980]
e[19]: time[4900]
e[19]: time[382]
e[19]: time[382]
e[19]: time[2292]
e[19]: time[10073452]
e[19]: time[6644]
e[19]: time[10865]
e[19]: time[726004281]
e[19]: time[10865]
e[19]: time[726004281]
e[19]: time[10865]
e[19]: time[726004281]
e[19]: time[3916]

My initial impression is that we'll need to use gcov_t all over the
place, which is unfortunate because that's going to make the inliner
more expensive on 32-bit builds.

Or perhaps we can get away with only using gcov_t for info->time, I'll
give that a try.
David Miller - Nov. 6, 2012, 7:45 p.m.
From: David Miller <davem@davemloft.net>
Date: Tue, 06 Nov 2012 14:28:19 -0500 (EST)

> Or perhaps we can get away with only using gcov_t for info->time, I'll
> give that a try.

That gets thing further, but if the edge times add up to such large
values it seems we have lots of other potential problems.

With info->times converted to gcov_type, the next assertion I hit is:

    gcc_assert (cached_badness == current_badness);

in inline_small_functions().

Both badness values are negative.

(gdb) p cached_badness
$1 = -91472
(gdb) p current_badness
$2 = -11434

This is starting to look like a very deep rabbit hole, and I'm really
surprised that you hit none of these problems.  Especially since even
x86-64 is getting fortran testsuite failure regressions due to these
changes.
Jan Hubicka - Nov. 6, 2012, 9:01 p.m.
> From: David Miller <davem@davemloft.net>
> Date: Tue, 06 Nov 2012 13:54:01 -0500 (EST)
> 
> > From: David Miller <davem@davemloft.net>
> > Date: Tue, 06 Nov 2012 13:26:53 -0500 (EST)
> > 
> >> From: Jan Hubicka <hubicka@ucw.cz>
> >> Date: Tue, 6 Nov 2012 19:21:46 +0100
> >> 
> >>> The problem here is really that MAX_TIME * MAX_FREQ do not fit into 32bit integer. Fixed thus.
> >>> 
> >>> 	* ipa-inline.c (compute_uninlined_call_time): Return gcov_type.
> >>> 	(compute_inlined_call_time): Watch overflows.
> >>> 	(relative_time_benefit): Compute in gcov_type.
> >> 
> >> Thanks Jan, I'll test this right now.
> > 
> > Bootstrap still fails with this change installed:
> > 
> > ../../gcc/gcc/graphite-interchange.c:645:1: internal compiler error: in relative_time_benefit, at \
> > ipa-inline.c:785
> >  }
> 
> The problem appears to be that inline_summary (edge->caller)->time
> is negative.
> 
> #1  0x010828a0 in relative_time_benefit (callee_info=0xf76fcb10, edge=0xf598a980, edge_time=3861) \
> at ../../gcc/gcc/ipa-inline.c:785
> (gdb) p callee_info->time
> $1200 = 3864
> (gdb) p edge->frequency
> $1201 = 263
> (gdb) p (callee_info->time * edge->frequency)
> $1202 = 1016232
> (gdb) p edge->caller->global.inlined_to
> $1203 = (cgraph_node *) 0x0
> (gdb) p edge->caller
> $1204 = (cgraph_node *) 0xf589ed10
> (gdb) p p inline_summary (edge->caller)->time
> No symbol "p" in current context.
> (gdb) p inline_summary (edge->caller)->time
> $1205 = -1044761

Hmm, this is obvoiusly wrong.  All the caller time computation should be capped
to MAX_TIME that should be safe from overflows.  I will dig into it tonight or
tomorrow. Sorry for the trouble.

Honza
David Miller - Nov. 6, 2012, 9:06 p.m.
From: Jan Hubicka <hubicka@ucw.cz>
Date: Tue, 6 Nov 2012 22:01:27 +0100

> Hmm, this is obvoiusly wrong.  All the caller time computation should be capped
> to MAX_TIME that should be safe from overflows.

They are not capped to MAX_TIME.

They are capped to MAX_TIME * INLINE_TIME_SCALE which is
1000000000.

Patch

Index: ipa-inline.c
===================================================================
--- ipa-inline.c	(revision 193246)
+++ ipa-inline.c	(working copy)
@@ -459,16 +459,16 @@  want_early_inline_function_p (struct cgr
 /* Compute time of the edge->caller + edge->callee execution when inlining
    does not happen.  */
 
-inline int
+inline gcov_type
 compute_uninlined_call_time (struct inline_summary *callee_info,
 			     struct cgraph_edge *edge)
 {
-  int uninlined_call_time =
+  gcov_type uninlined_call_time =
     RDIV ((gcov_type)callee_info->time * MAX (edge->frequency, 1),
 	  CGRAPH_FREQ_BASE);
-  int caller_time = inline_summary (edge->caller->global.inlined_to
-				    ? edge->caller->global.inlined_to
-				    : edge->caller)->time;
+  gcov_type caller_time = inline_summary (edge->caller->global.inlined_to
+				          ? edge->caller->global.inlined_to
+				          : edge->caller)->time;
   return uninlined_call_time + caller_time;
 }
 
@@ -479,12 +479,13 @@  inline gcov_type
 compute_inlined_call_time (struct cgraph_edge *edge,
 			   int edge_time)
 {
-  int caller_time = inline_summary (edge->caller->global.inlined_to
-				    ? edge->caller->global.inlined_to
-				    : edge->caller)->time;
-  int time = caller_time + RDIV ((edge_time - inline_edge_summary (edge)->call_stmt_time)
-			         * MAX (edge->frequency, 1),
-				 CGRAPH_FREQ_BASE);
+  gcov_type caller_time = inline_summary (edge->caller->global.inlined_to
+					  ? edge->caller->global.inlined_to
+					  : edge->caller)->time;
+  gcov_type time = (caller_time
+		    + RDIV (((gcov_type) edge_time
+			     - inline_edge_summary (edge)->call_stmt_time)
+		    * MAX (edge->frequency, 1), CGRAPH_FREQ_BASE));
   /* Possible one roundoff error, but watch for overflows.  */
   gcc_checking_assert (time >= INT_MIN / 2);
   if (time < 0)
@@ -770,9 +771,9 @@  relative_time_benefit (struct inline_sum
 		       struct cgraph_edge *edge,
 		       int edge_time)
 {
-  int relbenefit;
-  int uninlined_call_time = compute_uninlined_call_time (callee_info, edge);
-  int inlined_call_time = compute_inlined_call_time (edge, edge_time);
+  gcov_type relbenefit;
+  gcov_type uninlined_call_time = compute_uninlined_call_time (callee_info, edge);
+  gcov_type inlined_call_time = compute_inlined_call_time (edge, edge_time);
 
   /* Inlining into extern inline function is not a win.  */
   if (DECL_EXTERNAL (edge->caller->global.inlined_to
@@ -918,7 +919,7 @@  edge_badness (struct cgraph_edge *edge, 
 		   (int) badness, (double)edge->frequency / CGRAPH_FREQ_BASE,
 		   relative_time_benefit (callee_info, edge, edge_time) * 100.0
 		   / RELATIVE_TIME_BENEFIT_RANGE, 
-		   compute_uninlined_call_time (callee_info, edge),
+		   (int)compute_uninlined_call_time (callee_info, edge),
 		   (int)compute_inlined_call_time (edge, edge_time),
 		   estimate_growth (callee),
 		   callee_info->growth);