PR bootstrap/50709 (bootstrap miscompare)

PR bootstrap/50709 (bootstrap miscompare)

[Jan Hubicka]

Hi,
the ENABLE_CHECKING code verifying consistency of inliner cache has effect on changing
order of querries to the fibheap that consequentely makes entries with same key come
in different orders.

Fixed by enabling the checking aways.  I also added extra check that the keys are conservatively
correct.

Bootstrapped/regtested x86_64-linux.


Index: ChangeLog
===================================================================
--- ChangeLog	(revision 180190)
+++ ChangeLog	(working copy)
@@ -1,3 +1,9 @@
+2011-10-19  Jan Hubicka  <jh@suse.cz>
+
+	PR bootstrap/50709
+	* ipa-inline.c (inline_small_functions): Fix checking code to not make
+	effect on fibheap stability.
+
 2011-10-19  Roland Stigge  <stigge@antcom.de>
 
 	PR translation/48638
Index: ipa-inline.c
===================================================================
--- ipa-inline.c	(revision 180190)
+++ ipa-inline.c	(working copy)
@@ -1384,6 +1384,7 @@ inline_small_functions (void)
       struct cgraph_node *where, *callee;
       int badness = fibheap_min_key (heap);
       int current_badness;
+      int cached_badness = -1;
       int growth;
 
       edge = (struct cgraph_edge *) fibheap_extract_min (heap);
@@ -1392,16 +1393,20 @@ inline_small_functions (void)
       if (!edge->inline_failed)
 	continue;
 
-      /* Be sure that caches are maintained consistent.  */
 #ifdef ENABLE_CHECKING
+      /* Be sure that caches are maintained conservatively consistent.
+	 This means that cached badness is allways smaller or equal
+	 to the real badness.  */
+      cached_badness = edge_badness (edge, false);
+#endif
       reset_edge_growth_cache (edge);
       reset_node_growth_cache (edge->callee);
-#endif
 
       /* When updating the edge costs, we only decrease badness in the keys.
 	 Increases of badness are handled lazilly; when we see key with out
 	 of date value on it, we re-insert it now.  */
       current_badness = edge_badness (edge, false);
+      gcc_assert (cached_badness == -1 || cached_badness <= current_badness);
       gcc_assert (current_badness >= badness);
       if (current_badness != badness)
 	{

Re: PR bootstrap/50709 (bootstrap miscompare)

[Jan Hubicka]

> @@ -1392,16 +1393,20 @@ inline_small_functions (void)
>        if (!edge->inline_failed)
>  	continue;
>  
> -      /* Be sure that caches are maintained consistent.  */
>  #ifdef ENABLE_CHECKING
> +      /* Be sure that caches are maintained conservatively consistent.
> +	 This means that cached badness is allways smaller or equal
> +	 to the real badness.  */
> +      cached_badness = edge_badness (edge, false);
> +#endif
>        reset_edge_growth_cache (edge);
>        reset_node_growth_cache (edge->callee);
> -#endif
>  
>        /* When updating the edge costs, we only decrease badness in the keys.
>  	 Increases of badness are handled lazilly; when we see key with out
>  	 of date value on it, we re-insert it now.  */
>        current_badness = edge_badness (edge, false);
> +      gcc_assert (cached_badness == -1 || cached_badness <= current_badness);

This new check actually cathes a bug that is in tree since introduction of new
ipa-inline-analysis code.  The inliner assume that when it produce a new inline
copy, the overall growth estimates for all callees can only degrade.  This is
not quite true: when a new knowledge is propagated, the callees might actually
become cheaper and reduce the growth.

This patch takes the easy but expensive way to plug the problem by forcing
updating of all keys in the queue.  It increases LTO compile time of Mozilla to
10 minutes, so I will need to develop better sollution. (the trick saving
recomputation was originally introduced to reduce copmile time particularly on
this testcase) Just I should not keep tree ICEing on many C++ sources until I
am done.

Bootstrapped/regtested x86_64-linux, comitted.

Honza

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 180247)
+++ ChangeLog	(working copy)
@@ -1,5 +1,10 @@
 2011-10-19  Jan Hubicka  <jh@suse.cz>
 
+	* ipa-inline.c (inline_small_functions): Always update all calles after
+	inlining.
+
+2011-10-19  Jan Hubicka  <jh@suse.cz>
+
 	PR bootstrap/50709
 	* ipa-inline.c (inline_small_functions): Fix checking code to not make
 	effect on fibheap stability.
Index: ipa-inline.c
===================================================================
--- ipa-inline.c	(revision 180247)
+++ ipa-inline.c	(working copy)
@@ -1515,8 +1515,13 @@ inline_small_functions (void)
 
 	  /* We inlined last offline copy to the body.  This might lead
 	     to callees of function having fewer call sites and thus they
-	     may need updating.  */
-	  if (callee->global.inlined_to)
+	     may need updating. 
+
+	     FIXME: the callee size could also shrink because more information
+	     is propagated from caller.  We don't track when this happen and
+	     thus we need to recompute everything all the time.  Once this is
+	     solved, "|| 1" should go away.  */
+	  if (callee->global.inlined_to || 1)
 	    update_all_callee_keys (heap, callee, updated_nodes);
 	  else
 	    update_callee_keys (heap, edge->callee, updated_nodes);

Re: PR bootstrap/50709 (bootstrap miscompare)

[H.J. Lu]

On Thu, Oct 20, 2011 at 5:23 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> @@ -1392,16 +1393,20 @@ inline_small_functions (void)
>>        if (!edge->inline_failed)
>>       continue;
>>
>> -      /* Be sure that caches are maintained consistent.  */
>>  #ifdef ENABLE_CHECKING
>> +      /* Be sure that caches are maintained conservatively consistent.
>> +      This means that cached badness is allways smaller or equal
>> +      to the real badness.  */
>> +      cached_badness = edge_badness (edge, false);
>> +#endif
>>        reset_edge_growth_cache (edge);
>>        reset_node_growth_cache (edge->callee);
>> -#endif
>>
>>        /* When updating the edge costs, we only decrease badness in the keys.
>>        Increases of badness are handled lazilly; when we see key with out
>>        of date value on it, we re-insert it now.  */
>>        current_badness = edge_badness (edge, false);
>> +      gcc_assert (cached_badness == -1 || cached_badness <= current_badness);
>
> This new check actually cathes a bug that is in tree since introduction of new
> ipa-inline-analysis code.  The inliner assume that when it produce a new inline
> copy, the overall growth estimates for all callees can only degrade.  This is
> not quite true: when a new knowledge is propagated, the callees might actually
> become cheaper and reduce the growth.
>
> This patch takes the easy but expensive way to plug the problem by forcing
> updating of all keys in the queue.  It increases LTO compile time of Mozilla to
> 10 minutes, so I will need to develop better sollution. (the trick saving
> recomputation was originally introduced to reduce copmile time particularly on
> this testcase) Just I should not keep tree ICEing on many C++ sources until I
> am done.
>
> Bootstrapped/regtested x86_64-linux, comitted.
>
> Honza
>
> Index: ChangeLog
> ===================================================================
> --- ChangeLog   (revision 180247)
> +++ ChangeLog   (working copy)
> @@ -1,5 +1,10 @@
>  2011-10-19  Jan Hubicka  <jh@suse.cz>
>
> +       * ipa-inline.c (inline_small_functions): Always update all calles after
> +       inlining.
> +
> +2011-10-19  Jan Hubicka  <jh@suse.cz>
> +
>        PR bootstrap/50709
>        * ipa-inline.c (inline_small_functions): Fix checking code to not make
>        effect on fibheap stability.

Those changes may have caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50868

-- 
H.J.