New badness metric for inliner

New badness metric for inliner

[Jan Hubicka]

Hi,
this patch implements new badness metric for inliner.  It is now based on
relative speedup, but not of calee, but of the caller + callee combo.  This
nicely encompasses the edge frequency and other parameters simplifying the
actual badness code. I re-added code considering growth after inlining into
all callees, but this time without any attempt to keep the value up to
date across inlining that has shown to be expensive to do.

The patch also adds two new inline hints: INLINE_HINT_declared_inline and
INLINE_HINT_cross_module. INLINE_HINT_declared_inline decreases badness of the
call so explicitely declared functions are more likely inlined.
INLINE_HINT_cross_module increase badness since programs are usually organized
in a way that cross module inlining is less important than inter-module
inlining still.

While the patch ended up quite simple, it is result of much experimentation and
bugfixing ;)
I have bootstrapped/regtested the patch on x86_64-linux and tested on SPEC2000,
SPEC2006, c++ benchmark suite and Mozilla.  The patch is generally quite
considerable win. Most nice speedup are seen on the C++ benchmark suite where
it leads to nice code size savings and speedups. (i.e. tramp3d is now 30%
smaller and faster than before) http://gcc.opensuse.org/c++bench-frescobaldi/

There are few benchmarks that are not on historically best scores over my
experiments - botan (that regress relative to 4.7), fatigue and c-ray. I will
address these incrementally.  I will also do incrementally tunning with profile
feedback.

Honza

	* ipa-inline.c (compute_uninlined_call_time,
	compute_inlined_call_time): New functions.
	(RELATIVE_TIME_BENEFIT_RANGE): New macro.
	(relative_time_benefit): Rewrite.
	(edge_badness): Rewrite path with guessed profile and estimated profile.
	* ipa-inline.h (INLINE_HINT_declared_inline, INLINE_HINT_cross_module):
	New hints.
	(struct inline_summary): Add GROWTH filed.
	* ipa-inline-analysis.c (dump_inline_hints): Update.
	(reset_inline_summary): Update.
	(dump_inline_summary): Update.
	(will_be_nonconstant_predicate): Cleanup to use gimple_store_p and
	gimple_assign_load_p predicates.
	(estimate_node_size_and_time): Drop INLINE_HINT_declared_inline hint.
	(simple_edge_hints): New function.
	(do_estimate_edge_time): Return time of invocation of callee rather
	than the time scaled by edge frequency; update hints code.
	(do_estimate_edge_hints): Update.
	(do_estimate_growth): Cleanup.
Index: ipa-inline.c
===================================================================
--- ipa-inline.c	(revision 193157)
+++ ipa-inline.c	(working copy)
@@ -456,6 +456,42 @@ want_early_inline_function_p (struct cgr
   return want_inline;
 }
 
+/* Compute time of the edge->caller + edge->callee execution when inlining
+   does not happen.  */
+
+inline int
+compute_uninlined_call_time (struct inline_summary *callee_info,
+			     struct cgraph_edge *edge)
+{
+  int 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;
+  return uninlined_call_time + caller_time;
+}
+
+/* Same as compute_uinlined_call_time but compute time when inlining
+   does happen.  */
+
+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);
+  /* Possible one roundoff error, but watch for overflows.  */
+  gcc_checking_assert (time >= INT_MIN / 2);
+  if (time < 0)
+    time = 0;
+  return time;
+}
+
 /* Return true if we are interested in inlining small function.
    When REPORT is true, report reason to dump file.  */
 
@@ -724,31 +760,41 @@ want_inline_function_to_all_callers_p (s
    return true;
 }
 
+#define RELATIVE_TIME_BENEFIT_RANGE (INT_MAX / 64)
 
 /* Return relative time improvement for inlining EDGE in range
-   1...2^9.  */
+   1...RELATIVE_TIME_BENEFIT_RANGE  */
 
 static inline int
 relative_time_benefit (struct inline_summary *callee_info,
 		       struct cgraph_edge *edge,
-		       int time_growth)
+		       int edge_time)
 {
   int relbenefit;
-  gcov_type uninlined_call_time;
+  int uninlined_call_time = compute_uninlined_call_time (callee_info, edge);
+  int 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
+		     ? edge->caller->global.inlined_to->symbol.decl
+		     : edge->caller->symbol.decl))
+    return 1;
+
+  /* Watch overflows.  */
+  gcc_checking_assert (uninlined_call_time >= 0);
+  gcc_checking_assert (inlined_call_time >= 0);
+  gcc_checking_assert (uninlined_call_time >= inlined_call_time);
 
-  uninlined_call_time =
-    ((gcov_type)
-     (callee_info->time
-      + inline_edge_summary (edge)->call_stmt_time) * edge->frequency
-     + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
   /* Compute relative time benefit, i.e. how much the call becomes faster.
      ??? perhaps computing how much the caller+calle together become faster
      would lead to more realistic results.  */
   if (!uninlined_call_time)
     uninlined_call_time = 1;
   relbenefit =
-    (uninlined_call_time - time_growth) * 256 / (uninlined_call_time);
-  relbenefit = MIN (relbenefit, 512);
+    RDIV (((gcov_type)uninlined_call_time - inlined_call_time) * RELATIVE_TIME_BENEFIT_RANGE,
+	  uninlined_call_time);
+  relbenefit = MIN (relbenefit, RELATIVE_TIME_BENEFIT_RANGE);
+  gcc_checking_assert (relbenefit >= 0);
   relbenefit = MAX (relbenefit, 1);
   return relbenefit;
 }
@@ -764,7 +810,7 @@ static int
 edge_badness (struct cgraph_edge *edge, bool dump)
 {
   gcov_type badness;
-  int growth, time_growth;
+  int growth, edge_time;
   struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee,
 							      NULL);
   struct inline_summary *callee_info = inline_summary (callee);
@@ -774,17 +820,20 @@ edge_badness (struct cgraph_edge *edge, 
     return INT_MIN;
 
   growth = estimate_edge_growth (edge);
-  time_growth = estimate_edge_time (edge);
+  edge_time = estimate_edge_time (edge);
   hints = estimate_edge_hints (edge);
+  gcc_checking_assert (edge_time >= 0);
+  gcc_checking_assert (edge_time <= callee_info->time);
+  gcc_checking_assert (growth <= callee_info->size);
 
   if (dump)
     {
       fprintf (dump_file, "    Badness calculation for %s -> %s\n",
 	       xstrdup (cgraph_node_name (edge->caller)),
 	       xstrdup (cgraph_node_name (callee)));
-      fprintf (dump_file, "      size growth %i, time growth %i ",
+      fprintf (dump_file, "      size growth %i, time %i ",
 	       growth,
-	       time_growth);
+	       edge_time);
       dump_inline_hints (dump_file, hints);
       fprintf (dump_file, "\n");
     }
@@ -802,7 +851,7 @@ edge_badness (struct cgraph_edge *edge, 
 
 	        relative_edge_count * relative_time_benefit
      goodness = -------------------------------------------
-		edge_growth
+		growth_f_caller
      badness = -goodness  
 
     The fraction is upside down, because on edge counts and time beneits
@@ -810,11 +859,11 @@ edge_badness (struct cgraph_edge *edge, 
 
   else if (max_count)
     {
-      int relbenefit = relative_time_benefit (callee_info, edge, time_growth);
+      int relbenefit = relative_time_benefit (callee_info, edge, edge_time);
       badness =
 	((int)
-	 ((double) edge->count * INT_MIN / 2 / max_count / 512) *
-	 relative_time_benefit (callee_info, edge, time_growth)) / growth;
+	 ((double) edge->count * INT_MIN / 2 / max_count / RELATIVE_TIME_BENEFIT_RANGE) *
+	 relbenefit) / growth;
       
       /* Be sure that insanity of the profile won't lead to increasing counts
 	 in the scalling and thus to overflow in the computation above.  */
@@ -826,73 +875,53 @@ edge_badness (struct cgraph_edge *edge, 
 		   " * Relative benefit %f\n",
 		   (int) badness, (double) badness / INT_MIN,
 		   (double) edge->count / max_count,
-		   relbenefit * 100 / 256.0);
+		   relbenefit * 100.0 / RELATIVE_TIME_BENEFIT_RANGE);
 	}
     }
 
   /* When function local profile is available. Compute badness as:
-
      
-               growth_of_callee
-     badness = -------------------------------------- + growth_for-all
-	       relative_time_benefit * edge_frequency
+                 relative_time_benefit
+     goodness =  ---------------------------------
+	         growth_of_caller * overall_growth
 
+     badness = - goodness
+
+     compensated by the inline hints.
   */
   else if (flag_guess_branch_prob)
     {
-      int div = edge->frequency * (1<<10) / CGRAPH_FREQ_MAX;
-
-      div = MAX (div, 1);
-      gcc_checking_assert (edge->frequency <= CGRAPH_FREQ_MAX);
-      div *= relative_time_benefit (callee_info, edge, time_growth);
-
-      /* frequency is normalized in range 1...2^10.
-         relbenefit in range 1...2^9
-	 DIV should be in range 1....2^19.  */
-      gcc_checking_assert (div >= 1 && div <= (1<<19));
-
-      /* Result must be integer in range 0...INT_MAX.
-	 Set the base of fixed point calculation so we don't lose much of
-	 precision for small bandesses (those are interesting) yet we don't
-	 overflow for growths that are still in interesting range.
-
-	 Fixed point arithmetic with point at 6th bit. */
-      badness = ((gcov_type)growth) * (1<<(19+6));
-      badness = (badness + div / 2) / div;
-
-      /* Overall growth of inlining all calls of function matters: we want to
-	 inline so offline copy of function is no longer needed.
-
-	 Additionally functions that can be fully inlined without much of
-	 effort are better inline candidates than functions that can be fully
-	 inlined only after noticeable overall unit growths. The latter
-	 are better in a sense compressing of code size by factoring out common
-	 code into separate function shared by multiple code paths.
-
-	 We might mix the valud into the fraction by taking into account
-	 relative growth of the unit, but for now just add the number
-	 into resulting fraction.  */
-      if (badness > INT_MAX / 8)
-	{
-	  badness = INT_MAX / 8;
-	  if (dump)
-	    fprintf (dump_file, "Badness overflow\n");
-	}
-      if (hints & (INLINE_HINT_indirect_call
-		   | INLINE_HINT_loop_iterations
-		   | INLINE_HINT_loop_stride))
-	badness /= 8;
+      badness = (relative_time_benefit (callee_info, edge, edge_time)
+		 * (INT_MIN / 16 / RELATIVE_TIME_BENEFIT_RANGE));
+      badness /= (growth * MAX (1, callee_info->growth));
+      gcc_checking_assert (badness <=0 && badness >= INT_MIN / 16);
+      if ((hints & (INLINE_HINT_indirect_call
+		    | INLINE_HINT_loop_iterations
+		    | INLINE_HINT_loop_stride))
+	  || callee_info->growth <= 0)
+	badness *= 8;
       if (hints & (INLINE_HINT_same_scc))
-	badness *= 4;
-      if (hints & (INLINE_HINT_in_scc))
-	badness *= 2;
+	badness /= 16;
+      else if (hints & (INLINE_HINT_in_scc))
+	badness /= 8;
+      else if (hints & (INLINE_HINT_cross_module))
+	badness /= 2;
+      gcc_checking_assert (badness <= 0 && badness >= INT_MIN / 2);
+      if ((hints & INLINE_HINT_declared_inline) && badness >= INT_MIN / 32)
+	badness *= 16;
       if (dump)
 	{
 	  fprintf (dump_file,
 		   "      %i: guessed profile. frequency %f,"
-		   " benefit %f%%, divisor %i\n",
+		   " benefit %f%%, time w/o inlining %i, time w inlining %i"
+		   " overall growth %i (current) %i (original)\n",
 		   (int) badness, (double)edge->frequency / CGRAPH_FREQ_BASE,
-		   relative_time_benefit (callee_info, edge, time_growth) * 100 / 256.0, div);
+		   relative_time_benefit (callee_info, edge, edge_time) * 100.0
+		   / RELATIVE_TIME_BENEFIT_RANGE, 
+		   compute_uninlined_call_time (callee_info, edge),
+		   (int)compute_inlined_call_time (edge, edge_time),
+		   estimate_growth (callee),
+		   callee_info->growth);
 	}
     }
   /* When function local profile is not available or it does not give
@@ -1371,6 +1400,7 @@ inline_small_functions (void)
 
 	    if (!DECL_EXTERNAL (node->symbol.decl))
 	      initial_size += info->size;
+	    info->growth = estimate_growth (node);
 	    if (dfs && dfs->next_cycle)
 	      {
 		struct cgraph_node *n2;
Index: ipa-inline.h
===================================================================
--- ipa-inline.h	(revision 193155)
+++ ipa-inline.h	(working copy)
@@ -49,7 +49,9 @@ enum inline_hints_vals {
   INLINE_HINT_loop_iterations = 2,
   INLINE_HINT_loop_stride = 4,
   INLINE_HINT_same_scc = 8,
-  INLINE_HINT_in_scc = 16
+  INLINE_HINT_in_scc = 16,
+  INLINE_HINT_declared_inline = 32,
+  INLINE_HINT_cross_module = 64
 };
 typedef int inline_hints;
 
@@ -129,6 +131,12 @@ struct GTY(()) inline_summary
   /* Predicate on when some loop in the function becomes to have known
      stride.   */
   struct predicate * GTY((skip)) loop_stride;
+  /* Estimated growth for inlining all copies of the function before start
+     of small functions inlining.
+     This value will get out of date as the callers are duplicated, but
+     using up-to-date value in the badness metric mean a lot of extra
+     expenses.  */
+  int growth;
   /* Number of SCC on the beggining of inlining process.  */
   int scc_no;
 };
Index: ipa-inline-analysis.c
===================================================================
--- ipa-inline-analysis.c	(revision 193155)
+++ ipa-inline-analysis.c	(working copy)
@@ -649,6 +649,16 @@ dump_inline_hints (FILE *f, inline_hints
       hints &= ~INLINE_HINT_in_scc;
       fprintf (f, " in_scc");
     }
+  if (hints & INLINE_HINT_cross_module)
+    {
+      hints &= ~INLINE_HINT_cross_module;
+      fprintf (f, " cross_module");
+    }
+  if (hints & INLINE_HINT_declared_inline)
+    {
+      hints &= ~INLINE_HINT_declared_inline;
+      fprintf (f, " declared_inline");
+    }
   gcc_assert (!hints);
 }
 
@@ -983,6 +993,7 @@ reset_inline_summary (struct cgraph_node
   info->stack_frame_offset = 0;
   info->size = 0;
   info->time = 0;
+  info->growth = 0;
   info->scc_no = 0;
   if (info->loop_iterations)
     {
@@ -1375,6 +1386,9 @@ dump_inline_summary (FILE * f, struct cg
 	       (int) s->estimated_self_stack_size);
       fprintf (f, "  global stack:    %i\n",
 	       (int) s->estimated_stack_size);
+      if (s->growth)
+        fprintf (f, "  estimated growth:%i\n",
+	         (int) s->growth);
       if (s->scc_no)
         fprintf (f, "  In SCC:          %i\n",
 	         (int) s->scc_no);
@@ -1977,10 +1991,11 @@ will_be_nonconstant_predicate (struct ip
     return p;
 
   /* Stores will stay anyway.  */
-  if (gimple_vdef (stmt))
+  if (gimple_store_p (stmt))
     return p;
 
-  is_load = gimple_vuse (stmt) != NULL;
+  is_load = gimple_assign_load_p (stmt);
+
   /* Loads can be optimized when the value is known.  */
   if (is_load)
     {
@@ -2857,6 +2872,8 @@ estimate_node_size_and_time (struct cgra
     hints |=INLINE_HINT_loop_stride;
   if (info->scc_no)
     hints |= INLINE_HINT_in_scc;
+  if (DECL_DECLARED_INLINE_P (node->symbol.decl))
+    hints |= INLINE_HINT_declared_inline;
 
   estimate_calls_size_and_time (node, &size, &time, &hints, possible_truths,
 				known_vals, known_binfos, known_aggs);
@@ -2865,7 +2882,6 @@ estimate_node_size_and_time (struct cgra
   time = RDIV (time, INLINE_TIME_SCALE);
   size = RDIV (size, INLINE_SIZE_SCALE);
 
-
   if (dump_file
       && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "\n   size:%i time:%i\n", (int)size, (int)time);
@@ -3315,6 +3331,26 @@ inline_update_overall_summary (struct cg
   info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
 }
 
+/* Return hints derrived from EDGE.   */
+int
+simple_edge_hints (struct cgraph_edge *edge)
+{
+  int hints = 0;
+  struct cgraph_node *to = (edge->caller->global.inlined_to
+			    ? edge->caller->global.inlined_to
+			    : edge->caller);
+  if (inline_summary (to)->scc_no
+      && inline_summary (to)->scc_no == inline_summary (edge->callee)->scc_no
+      && !cgraph_edge_recursive_p (edge))
+    hints |= INLINE_HINT_same_scc;
+
+  if (to->symbol.lto_file_data && edge->callee->symbol.lto_file_data
+      && to->symbol.lto_file_data != edge->callee->symbol.lto_file_data)
+    hints |= INLINE_HINT_cross_module;
+
+  return hints;
+}
+
 /* Estimate the time cost for the caller when inlining EDGE.
    Only to be called via estimate_edge_time, that handles the
    caching mechanism.
@@ -3328,7 +3364,6 @@ do_estimate_edge_time (struct cgraph_edg
   int time;
   int size;
   inline_hints hints;
-  gcov_type ret;
   struct cgraph_node *callee;
   clause_t clause;
   VEC (tree, heap) *known_vals;
@@ -3347,33 +3382,26 @@ do_estimate_edge_time (struct cgraph_edg
   VEC_free (tree, heap, known_vals);
   VEC_free (tree, heap, known_binfos);
   VEC_free (ipa_agg_jump_function_p, heap, known_aggs);
-
-  ret = RDIV ((gcov_type)time * edge->frequency,
-	      CGRAPH_FREQ_BASE);
+  gcc_checking_assert (size >= 0);
+  gcc_checking_assert (time >= 0);
 
   /* When caching, update the cache entry.  */
   if (edge_growth_cache)
     {
-      struct cgraph_node *to = (edge->caller->global.inlined_to
-			        ? edge->caller->global.inlined_to
-				: edge->caller);
       if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache)
 	  <= edge->uid)
 	VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
 			       cgraph_edge_max_uid);
       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid).time
-	= ret + (ret >= 0);
+	= time + (time >= 0);
 
       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid).size
 	= size + (size >= 0);
-      if (inline_summary (to)->scc_no
-	  && inline_summary (to)->scc_no == inline_summary (callee)->scc_no
-	  && !cgraph_edge_recursive_p (edge))
-	hints |= INLINE_HINT_same_scc;
+      hints |= simple_edge_hints (edge);
       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid).hints
 	= hints + 1;
     }
-  return ret;
+  return time;
 }
 
 
@@ -3430,9 +3458,6 @@ do_estimate_edge_hints (struct cgraph_ed
   VEC (tree, heap) *known_vals;
   VEC (tree, heap) *known_binfos;
   VEC (ipa_agg_jump_function_p, heap) *known_aggs;
-  struct cgraph_node *to = (edge->caller->global.inlined_to
-		            ? edge->caller->global.inlined_to
-			    : edge->caller);
 
   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 
@@ -3458,10 +3483,7 @@ do_estimate_edge_hints (struct cgraph_ed
   VEC_free (tree, heap, known_vals);
   VEC_free (tree, heap, known_binfos);
   VEC_free (ipa_agg_jump_function_p, heap, known_aggs);
-  if (inline_summary (to)->scc_no
-      && inline_summary (to)->scc_no == inline_summary (callee)->scc_no
-      && !cgraph_edge_recursive_p (edge))
-    hints |= INLINE_HINT_same_scc;
+  hints |= simple_edge_hints (edge);
   return hints;
 }
 
@@ -3549,10 +3571,11 @@ do_estimate_growth (struct cgraph_node *
      return zero or negative growths. */
   if (d.self_recursive)
     d.growth = d.growth < info->size ? info->size : d.growth;
+  else if (DECL_EXTERNAL (node->symbol.decl))
+    ;
   else
     {
-      if (!DECL_EXTERNAL (node->symbol.decl)
-	  && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
+      if (cgraph_will_be_removed_from_program_if_no_direct_calls (node))
 	d.growth -= info->size;
       /* COMDAT functions are very often not shared across multiple units
 	 since they come from various template instantiations.

Re: New badness metric for inliner

[David Miller]

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
 }
 ^
0x10bcf1b relative_time_benefit
        ../../gcc/gcc/ipa-inline.c:784
0x10bd583 edge_badness
        ../../gcc/gcc/ipa-inline.c:894
0x10bdcdf update_edge_key
        ../../gcc/gcc/ipa-inline.c:962
0x10be68b update_callee_keys
        ../../gcc/gcc/ipa-inline.c:1141
0x10c00f7 inline_small_functions
        ../../gcc/gcc/ipa-inline.c:1594
0x10c0aa7 ipa_inline
        ../../gcc/gcc/ipa-inline.c:1769
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

Re: New badness metric for inliner

[Jan Hubicka]

> 
> 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

I am sorry for that.  I added couple of sanity checks for overflow and it seems it triggers.
Is line 784 for you "gcc_checking_assert (uninlined_call_time >= 0);"?

Honza

Re: New badness metric for inliner

[David Miller]

From: Jan Hubicka <hubicka@ucw.cz>
Date: Mon, 5 Nov 2012 23:19:16 +0100

> Is line 784 for you "gcc_checking_assert (uninlined_call_time >= 0);"?

Yes.

Re: New badness metric for inliner

[Jan Hubicka]

> 
> 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.
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);

Re: New badness metric for inliner

[David Miller]

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.

Re: New badness metric for inliner

[David Miller]

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.

Re: New badness metric for inliner

[David Miller]

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) 

Re: New badness metric for inliner

[David Miller]

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.

Re: New badness metric for inliner

[David Miller]

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.

Re: New badness metric for inliner

[Jan Hubicka]

> 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

Re: New badness metric for inliner

[David Miller]

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.

Re: New badness metric for inliner

[Jan Hubicka]

> 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.

Right and that is why they need to be capped after every addition.
(while writting the code it did not have the INLINE_TIME_SCALE
factor yet and I concluded I do not need to do capping because 
there are at most 32 additions).

I noticed there is one extra place with this problem, so I fixed it, too.

The attached patch fixes the testcase, so I comitted it as obvious.  Hope it
will fix the bootstrap for you. I did not hit this because my bootstrap did not
have graphite enabled due to lack of proper support libraries.

Comitted as obvious.

	* ipa-inline-analysis.c (estimate_function_body_sizes,
	inline_update_overall_summary): Cap time calculations.
Index: ipa-inline-analysis.c
===================================================================
--- ipa-inline-analysis.c	(revision 193246)
+++ ipa-inline-analysis.c	(working copy)
@@ -2442,6 +2442,8 @@ estimate_function_body_sizes (struct cgr
 		{
 		  time += this_time;
 		  size += this_size;
+		  if (time > MAX_TIME * INLINE_TIME_SCALE)
+		    time = MAX_TIME * INLINE_TIME_SCALE;
 		}
 
 	      /* We account everything but the calls.  Calls have their own
@@ -3323,7 +3325,11 @@ inline_update_overall_summary (struct cg
   info->size = 0;
   info->time = 0;
   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
-    info->size += e->size, info->time += e->time;
+    {
+      info->size += e->size, info->time += e->time;
+      if (info->time > MAX_TIME * INLINE_TIME_SCALE)
+        info->time = MAX_TIME * INLINE_TIME_SCALE;
+    }
   estimate_calls_size_and_time (node, &info->size, &info->time, NULL,
 				~(clause_t)(1 << predicate_false_condition),
 				NULL, NULL, NULL);

Re: New badness metric for inliner

[David Miller]

From: Jan Hubicka <hubicka@ucw.cz>
Date: Tue, 6 Nov 2012 22:11:44 +0100

> The attached patch fixes the testcase, so I comitted it as obvious.  Hope it
> will fix the bootstrap for you. I did not hit this because my bootstrap did not
> have graphite enabled due to lack of proper support libraries.
> 
> Comitted as obvious.
> 
> 	* ipa-inline-analysis.c (estimate_function_body_sizes,
> 	inline_update_overall_summary): Cap time calculations.

Bootstrap is working again for me, thanks Jan!