Fix updating of call_stmt_site_hash

Hi,
this patch fixes ICE causes by call stmt site hash going out of sync.  For
speculative edges it is assumed to contain a direct call so if we are
removing it hashtable needs to be updated.  I realize that the code is ugly
but I will leave cleanup for next stage1.

Bootstrapped/regtested x86_64-linux. This patch makes it possible to build
Firefox again.

	PR lto/93318	
	* cgraph.c (cgraph_edge::resolve_speculation,
	cgraph_edge::redirect_call_stmt_to_callee): Fix update of
	call_stmt_site_hash.

On January 21, 2020 4:37:31 PM GMT+01:00, Jan Hubicka <hubicka@ucw.cz> wrote:
>Hi,
>this patch fixes ICE causes by call stmt site hash going out of sync. 
>For
>speculative edges it is assumed to contain a direct call so if we are
>removing it hashtable needs to be updated.  I realize that the code is
>ugly
>but I will leave cleanup for next stage1.
>
>Bootstrapped/regtested x86_64-linux. This patch makes it possible to
>build
>Firefox again.

It even looks quadratic? Can't you simply lookup the stmt? 

>	PR lto/93318	
>	* cgraph.c (cgraph_edge::resolve_speculation,
>	cgraph_edge::redirect_call_stmt_to_callee): Fix update of
>	call_stmt_site_hash.
>diff --git a/gcc/cgraph.c b/gcc/cgraph.c
>index 187f6ed30ba..f7ebcc917d1 100644
>--- a/gcc/cgraph.c
>+++ b/gcc/cgraph.c
>@@ -1248,7 +1248,22 @@ cgraph_edge::resolve_speculation (cgraph_edge
>*edge, tree callee_decl)
>   else
>     e2->callee->remove_symbol_and_inline_clones ();
>   if (edge->caller->call_site_hash)
>-    cgraph_update_edge_in_call_site_hash (edge);
>+    {
>+      /* We always maintain direct edge in the call site hash, if one
>+	 exists.  */
>+      if (!edge->num_speculative_call_targets_p ())
>+	cgraph_update_edge_in_call_site_hash (edge);
>+      else
>+	{
>+	  cgraph_edge *e;
>+	  for (e = edge->caller->callees;
>+	       e->call_stmt != edge->call_stmt
>+	       || e->lto_stmt_uid != edge->lto_stmt_uid;
>+	       e = e->next_callee)
>+	    ;
>+	  cgraph_update_edge_in_call_site_hash (e);
>+	}
>+    }
>   return edge;
> }
> 
>@@ -1414,7 +1429,20 @@ cgraph_edge::redirect_call_stmt_to_callee
>(cgraph_edge *e)
> 	  /* Indirect edges are not both in the call site hash.
> 	     get it updated.  */
> 	  if (e->caller->call_site_hash)
>-	    cgraph_update_edge_in_call_site_hash (e2);
>+	    {
>+	      if (!e2->num_speculative_call_targets_p ())
>+		cgraph_update_edge_in_call_site_hash (e2);
>+	      else
>+		{
>+		  cgraph_edge *e;
>+		  for (e = e2->caller->callees;
>+		       e->call_stmt != e2->call_stmt
>+		       || e->lto_stmt_uid != e2->lto_stmt_uid;
>+		       e = e->next_callee)
>+		    ;
>+		  cgraph_update_edge_in_call_site_hash (e);
>+		}
>+	    }
> 	  pop_cfun ();
> 	  /* Continue redirecting E to proper target.  */
> 	}

> On January 21, 2020 4:37:31 PM GMT+01:00, Jan Hubicka <hubicka@ucw.cz> wrote:
> >Hi,
> >this patch fixes ICE causes by call stmt site hash going out of sync. 
> >For
> >speculative edges it is assumed to contain a direct call so if we are
> >removing it hashtable needs to be updated.  I realize that the code is
> >ugly
> >but I will leave cleanup for next stage1.
> >
> >Bootstrapped/regtested x86_64-linux. This patch makes it possible to
> >build
> >Firefox again.
> 
> It even looks quadratic? Can't you simply lookup the stmt? 

I am not sure what you mean by looking up the stmt.  To go from stmt to
call edge you either walk the callees chain or use call_site_hash that
populates itself when you have more than 100 callees.  The situation
this code solves is that with speculative calls have multiple direct
edges, one indirect and multiple refs associated with the speculated
call stmt. Now one of direct edges gets removed and at this moment one
needs to look up different one to re-populate the hash.

I meant to fix the ICE first, but indeed resolve_speuclations and
redirect_stmt_to_callee is O(num_callees+num_refs) in worst case here
which needs to be fixed (though the case is quite rare in practice).
One can keep direct edges in a block in the lists (with verifier help),
but still looking up referneces is bit hard since they are in vector and
that is re-numbered on inserts and deletes.  I plan to fix this
incrementally (we want also refs hash and verifier for the caches, plus
this all is memory use critical)

Honza

On Tue, Jan 21, 2020 at 8:09 PM Jan Hubicka <hubicka@ucw.cz> wrote:
>
> > On January 21, 2020 4:37:31 PM GMT+01:00, Jan Hubicka <hubicka@ucw.cz> wrote:
> > >Hi,
> > >this patch fixes ICE causes by call stmt site hash going out of sync.
> > >For
> > >speculative edges it is assumed to contain a direct call so if we are
> > >removing it hashtable needs to be updated.  I realize that the code is
> > >ugly
> > >but I will leave cleanup for next stage1.
> > >
> > >Bootstrapped/regtested x86_64-linux. This patch makes it possible to
> > >build
> > >Firefox again.
> >
> > It even looks quadratic? Can't you simply lookup the stmt?
>
> I am not sure what you mean by looking up the stmt.  To go from stmt to
> call edge you either walk the callees chain or use call_site_hash that
> populates itself when you have more than 100 callees.  The situation
> this code solves is that with speculative calls have multiple direct
> edges, one indirect and multiple refs associated with the speculated
> call stmt. Now one of direct edges gets removed and at this moment one
> needs to look up different one to re-populate the hash.

I see.  I thought that maybe we have the hash record stmt -> { set of edges }
but if we have only stmt -> single-edge then indeed that's bad.

> I meant to fix the ICE first, but indeed resolve_speuclations and
> redirect_stmt_to_callee is O(num_callees+num_refs) in worst case here
> which needs to be fixed (though the case is quite rare in practice).

At least isolating this "detail" into a function might be nice...

> One can keep direct edges in a block in the lists (with verifier help),
> but still looking up referneces is bit hard since they are in vector and
> that is re-numbered on inserts and deletes.  I plan to fix this
> incrementally (we want also refs hash and verifier for the caches, plus
> this all is memory use critical)

Thanks,
Richard.

>
> Honza