Speculative call support in the callgraph

Hi,
this patch adds support for speculative calls into callgraph.  The idea is that
any IPA optimization that believes it knows likely target of an indirect call
(currently I use it for cross-module indirect call profiling, but I expect
Martin J. can easily add support for ipa-cp and I hope to add speculative
devirtualization in foreseeable future since it should make difference for
Firefox). Speculative call replaces indirect call

    call_target ()

by:

    if (call_target == expected_fn)
      expected_fn ();
    else
      call_target ();

We already know how to produce these by gimple_ic, however the idea is to not
modify the body immediately (IPA passes can not do that), but do that only when
we are applying ipa transformations.

Every speculative call is represented by three components attached
to the same call statement (the original indirect call):
 1) a direct call (to expected_fn)
 2) an indirect call (to call_target)
 3) a IPA_REF_ADDR refrence to expected_fn.

Each of those can be found by having "speculative" flag set.

This representation allows IPA passes to be smart about speculative calls.
1) the direct calls can be inlined or redirected to cprop clones just as any
   ordinary calls.  The reference still links to the original call target making
   it possible to later expand the test.
2) When indirect call target is found by ipa propagation, the call can be turned back
   to a direct call. Either by using the exisitng speculative direct call (if
   speculation was right) and keeping optimizations already attached to it
   or by turning the indirect call into new target if speculation was wrong.
   (this is done by resolve_speuclative_call)
3) at the end of IPA optimization we may get rid of speuclative calls that
   don't seem to buy anything.  I think that on most modern cores the
   speculative sequence is actually worse than the indirect call when
   the expected_fn call stays uninlined or unpropagated.
   (not implemented yet)
4) inliner can adjust its metric knowing that inlining speuclative call
   is costier (disabling 3) (also not implemented yet).

This patch implements the infrastructure only. I will send the corss-module
indirect call profiling code in followup patch.

I hoped this all to go quite smoothly into exisitng WHOPR infrastructure that
juding from the size of patch is not true.  I had to deal with some issues:

1) I am not linking the three components of calls explicitely together. Instead
   I rely on statement pointers in both edges&refs to allow later lookup of
   the components (by cgraph_speculative_call_info).

   ipa-reference call statements are however not streamed by LTO, so I had to
   implement the streaming. (hitting some surprises handled by preparation
   patches)
2) IPA-refs are not really maintained through versioning and inlining that is
   needed now for speculative expansion to work.  Currently we update only 
   callgraph edges and we rebuild ipa-refs (and wrongly so not updating
   clones that is harmless since they are used only for unreachable function
   removal).

   I solved this partly by updating speculative calls only (since I can use
   the existing callgraph edge path).
   tree-inline got fat&ugly, I need to push higher the plans to clean it up.
3) cgraph_edge statement hash expect only one call per statement.  I fixed
   this by always recording the direct speculative call only.
4) ipa-prop and ipa-cp was not expecting the function to turn indirect call
   to direct call to return different edge that is passed to it (that happens
   when speculation was right).  It also accesses indirect_call_info in
   edges that are already direct.
   I fixed these and added code to explicitely free the indirect call info
   when they are turned to direct edges. Until now it stayed dormant
   in memory.
5) Indirect call expansion breaks basic blocks. Currently it happens during 
   call redirection performed by inliner.  It needs to be moved later in
   tree-inline after the body is fully duplicated or we ICE on trying to fixup
   not yet finished loop structure in split_bb.
6) ipa-inline was not ready for callgraph edges to be removed as result
   of inlining.  This was longer time on my TODO, so I fixed it by adding
   the missing edge removal hook.

Bootstrapped/regtested x86_64-linux, will commit it later today. Comments welcome.

Honza
	* cgraphbuild.c (cgraph_rebuild_references): Rebuild only non-speculative
	refs.
	* cgraph.c (cgraph_update_edge_in_call_site_hash): New function.
	(cgraph_add_edge_to_call_site_hash): Deal with speculative calls.
	(cgraph_set_call_stmt): Likewise.
	(cgraph_create_edge_1): Fix release checking compilatoin;
	clear lto_stmt_uid.
	(cgraph_free_edge): Free indirect info.
	(cgraph_turn_edge_to_speculative): New function.
	(cgraph_speculative_call_info): New function.
	(cgraph_make_edge_direct): Return direct edge; handle speculation.
	(cgraph_redirect_edge_call_stmt_to_callee): Expand speculative
	edges.
	(dump_cgraph_node): Dump speculation.
	(verify_edge_count_and_frequency): Accept speculative edges.
	(verify_edge_corresponds_to_fndecl): Handle partitioned cgraph.
	(verify_cgraph_node): Handle speculation.
	* cgraph.h (cgraph_edge): Add SPECULATIVE flag.
	(cgraph_set_call_stmt): Update prototype.
	(cgraph_make_edge_direct): Update prototype.
	(cgraph_speculative_call_info): Declare.
	* ipa-cp.c (ipcp_discover_new_direct_edges): Be ready for edge
	to change; update call of ipa_find_references.
	* ipa-ref.c (ipa_record_reference): Fix return value; clear
	lto_stmt_uid and speculative flags.
	(ipa_dump_references): Dump speculation.
	(ipa_clone_references): Clone speculative flag.
	(ipa_clone_referring): Likewise.
	(ipa_clone_ref): New function.
	(ipa_find_reference): Look into lto_stmt_uids
	(ipa_clear_stmts_in_references): Do not clear speculative calls.
	* ipa-ref.h (ipa_ref): Add lto_stmt_uid and speculative flags.
	(ipa_find_reference): Update declaration.
	(ipa_clone_ref): Declare.
	* lto-cgraph.c (lto_output_edge): Make lto_stmt_uids start from 0;
	stream speculative flag.
	(lto_output_ref): Stream statements uids and speculation.
	(input_ref): Likewise.
	(input_edge): Stream speuclation.
	* cgraphclones.c (cgraph_clone_edge): Clone speculation.
	(cgraph_set_call_stmt_including_clones): Handle speculation.
	* ipa-inline.c (heap_edge_removal_hook): New function.
	(inline_small_functions): Register it.
	* lto-streamer-in.c (fixup_call_stmt_edges_1): Bounds checking;
	also initialize refs.
	* ipa-prop.c (ipa_make_edge_direct_to_target): Be ready for
	edge to change.
	(try_make_edge_direct_simple_call): Likewise.
	(try_make_edge_direct_simple_call): Likewise.
	(update_indirect_edges_after_inlining): Likewise.
	(remove_described_reference): Look proper lto_stmt_uid.
	(propagate_controlled_uses): Likewise.
	(propagate_controlled_uses): Liekwise.
	* tree-inline.c (copy_bb): Copy speculative edges.
	(redirect_all_calls): New function.
	(copy_cfg_body): Do redirection after loop info
	is updated.
	(delete_unreachable_blocks_update_callgraph): Updadte
	speculation.
	* value-prof.c (gimple_ic): Export.
	* value-prof.h (gimple_ic): Declare.

Speculative call support in the callgraph

Commit Message

Comments

Patch