Missed function specialization + partial devirtualization

v8:
 1. Rebase to master with Martin's static function (r280043) comments merge.
    Boostrap/testsuite/SPEC2017 tested pass on Power8-LE.
 2. TODO:
    2.1. C++ devirt for multiple speculative call targets.
    2.2. ipa-icf ipa_merge_profiles refine with COMDAT inline testcase.

This patch aims to fix PR69678 caused by PGO indirect call profiling
performance issues.
The bug that profiling data is never working was fixed by Martin's pull
back of topN patches, performance got GEOMEAN ~1% improvement(+24% for
511.povray_r specifically).
Still, currently the default profile only generates SINGLE indirect target
that called more than 75%.  This patch leverages MULTIPLE indirect
targets use in LTO-WPA and LTO-LTRANS stage, as a result, function
specialization, profiling, partial devirtualization, inlining and
cloning could be done successfully based on it.
Performance can get improved from 0.70 sec to 0.38 sec on simple tests.
Details are:
  1.  PGO with topn is enabled by default now, but only one indirect
  target edge will be generated in ipa-profile pass, so add variables to enable
  multiple speculative edges through passes, speculative_id will record the
  direct edge index bind to the indirect edge, indirect_call_targets length
  records how many direct edges owned by the indirect edge, postpone gimple_ic
  to ipa-profile like default as inline pass will decide whether it is benefit
  to transform indirect call.
  2.  Use speculative_id to track and search the reference node matched
  with the direct edge's callee for multiple targets.  Actually, it is the
  caller's responsibility to handle the direct edges mapped to same indirect
  edge.  speculative_call_info will return one of the direct edge specified,
  this will leverage current IPA edge process framework mostly.
  3.  Enable LTO WPA/LTRANS stage multiple indirect call targets analysis for
  profile full support in ipa passes and cgraph_edge functions.  speculative_id
  can be set by make_speculative id when multiple targets are binded to
  one indirect edge, and cloned if new edge is cloned.  speculative_id
  is streamed out and stream int by lto like lto_stmt_uid.
  4.  Create and duplicate all speculative direct edge's call summary
  in ipa-fnsummary.c with auto_vec.
  5.  Add 1 in module testcase and 2 cross module testcases.
  6.  Bootstrap and regression test passed on Power8-LE.  No function
  and performance regression for SPEC2017.

gcc/ChangeLog

	2020-01-14  Xiong Hu Luo  <luoxhu@linux.ibm.com>

	PR ipa/69678
	* cgraph.c (symbol_table::create_edge): Init speculative_id and
	target_prob.
	(cgraph_edge::make_speculative): Add param for setting speculative_id
	and target_prob.
	(cgraph_edge::speculative_call_info): Update comments and find reference
	by speculative_id for multiple indirect targets.
	(cgraph_edge::resolve_speculation): Decrease the speculations
	for indirect edge, drop it's speculative if not direct target
	left. Update comments.
	(cgraph_edge::redirect_call_stmt_to_callee): Likewise.
	(cgraph_node::dump): Print num_speculative_call_targets.
	(cgraph_node::verify_node): Don't report error if speculative
	edge not include statement.
	(cgraph_edge::num_speculative_call_targets_p): New function.
	* cgraph.h (int common_target_id): Remove.
	(int common_target_probability): Remove.
	(num_speculative_call_targets): New variable.
	(make_speculative): Add param for setting speculative_id.
	(cgraph_edge::num_speculative_call_targets_p): New declare.
	(target_prob): New variable.
	(speculative_id): New variable.
	* ipa-fnsummary.c (analyze_function_body): Create and duplicate
	  call summaries for multiple speculative call targets.
	* cgraphclones.c (cgraph_node::create_clone): Clone speculative_id.
	* ipa-profile.c (struct speculative_call_target): New struct.
	(class speculative_call_summary): New class.
	(class speculative_call_summaries): New class.
	(call_sums): New variable.
	(ipa_profile_generate_summary): Generate indirect multiple targets summaries.
	(ipa_profile_write_edge_summary): New function.
	(ipa_profile_write_summary): Stream out indirect multiple targets summaries.
	(ipa_profile_dump_all_summaries): New function.
	(ipa_profile_read_edge_summary): New function.
	(ipa_profile_read_summary_section): New function.
	(ipa_profile_read_summary): Stream in indirect multiple targets summaries.
	(ipa_profile): Generate num_speculative_call_targets from
	profile summaries.
	* ipa-ref.h (speculative_id): New variable.
	* ipa-utils.c (ipa_merge_profiles): Update with target_prob.
	* lto-cgraph.c (lto_output_edge): Remove indirect common_target_id and
	common_target_probability.   Stream out speculative_id and
	num_speculative_call_targets.
	(input_edge): Likewise.
	* predict.c (dump_prediction): Remove edges count assert to be
	precise.
	* symtab.c (symtab_node::create_reference): Init speculative_id.
	(symtab_node::clone_references): Clone speculative_id.
	(symtab_node::clone_referring): Clone speculative_id.
	(symtab_node::clone_reference): Clone speculative_id.
	(symtab_node::clear_stmts_in_references): Clear speculative_id.
	* tree-inline.c (copy_bb): Duplicate all the speculative edges
	if indirect call contains multiple speculative targets.
	* value-prof.h  (check_ic_target): Remove.
	* value-prof.c  (gimple_value_profile_transformations):
	Use void function gimple_ic_transform.
	* value-prof.c  (gimple_ic_transform): Handle topn case.
	Fix comment typos.  Change it to a void function.

gcc/testsuite/ChangeLog

	2020-01-14  Xiong Hu Luo  <luoxhu@linux.ibm.com>

	PR ipa/69678
	* gcc.dg/tree-prof/indir-call-prof-topn.c: New testcase.
	* gcc.dg/tree-prof/crossmodule-indir-call-topn-1.c: New testcase.
	* gcc.dg/tree-prof/crossmodule-indir-call-topn-1a.c: New testcase.
	* gcc.dg/tree-prof/crossmodule-indir-call-topn-2.c: New testcase.
	* lib/scandump.exp: Dump executable file name.
	* lib/scanwpaipa.exp: New scan-pgo-wap-ipa-dump.

1 files changed, 101 insertions, 16 deletions

diff --git a/gcc/cgraph.c b/gcc/cgraph.c
index fe3f067..95b523d 100644
--- a/gcc/cgraph.c
+++ b/gcc/cgraph.c
@@ -858,6 +858,8 @@ symbol_table::create_edge (cgraph_node *caller, cgraph_node *callee,
   edge->prev_callee = NULL;
   edge->next_callee = NULL;
   edge->lto_stmt_uid = 0;
+  edge->target_prob = 0;
+  edge->speculative_id = 0;
 
   edge->count = count;
   edge->call_stmt = call_stmt;
@@ -1044,10 +1046,16 @@ cgraph_edge::remove (cgraph_edge *edge)
    the reference representing the if conditional and attaches
    them all to the original indirect call statement.  
 
+   speculative_id is used to link direct calls with their corresponding
+   IPA_REF_ADDR references when representing speculative calls.
+
+   target_prob is the probability of the speculative call.
+
    Return direct edge created.  */
 
 cgraph_edge *
-cgraph_edge::make_speculative (cgraph_node *n2, profile_count direct_count)
+cgraph_edge::make_speculative (cgraph_node *n2, profile_count direct_count,
+			       unsigned int speculative_id, int target_prob)
 {
   cgraph_node *n = caller;
   ipa_ref *ref = NULL;
@@ -1065,24 +1073,53 @@ cgraph_edge::make_speculative (cgraph_node *n2, profile_count direct_count)
   else
     e2->can_throw_external = can_throw_external;
   e2->lto_stmt_uid = lto_stmt_uid;
+  e2->speculative_id = speculative_id;
+  e2->target_prob = target_prob;
   e2->in_polymorphic_cdtor = in_polymorphic_cdtor;
   count -= e2->count;
   symtab->call_edge_duplication_hooks (this, e2);
   ref = n->create_reference (n2, IPA_REF_ADDR, call_stmt);
   ref->lto_stmt_uid = lto_stmt_uid;
+  ref->speculative_id = speculative_id;
   ref->speculative = speculative;
   n2->mark_address_taken ();
   return e2;
 }
 
-/* Speculative call consist of three components:
-   1) an indirect edge representing the original call
-   2) an direct edge representing the new call
-   3) ADDR_EXPR reference representing the speculative check.
-   All three components are attached to single statement (the indirect
-   call) and if one of them exists, all of them must exist.
+/* Speculative calls represent a transformation of indirect calls
+   which may be later inserted into gimple in the following form:
+
+   if (call_dest == target1)
+   target1 ();
+   else if (call_dest == target2)
+   target2 ();
+   else
+   call_dest ();
+
+   This is a win in the case when target1 and target2 are common values for
+   call_dest as determined by ipa-devirt or indirect call profiling.
+   In particular this may enable inlining and other optimizations.
+
+   Speculative call consists of the following main components:
+
+   1) One or more "speculative" direct call (num_speculative_call_targets is
+   speculative direct call count belongs to the speculative indirect call)
+   2) One or more IPA_REF_ADDR references (representing the fact that code above
+   takes address of target1 and target2)
+   3) The fallback "speculative" indirect call
 
-   Given speculative call edge, return all three components.
+   Direct calls and corresponding references are linked by
+   speculative_id.
+
+   speculative_call_info returns triple
+   (direct_call, indirect call, IPA_REF_ADDR reference)
+   when called on one edge participating in the speculative call:
+
+   1) If called on direct call, its corresponding IPA_REF_ADDR and related
+   indirect call are returned.
+
+   2) If called on indirect call, it will return one of direct edges and its
+   matching IPA_REF_ADDR.
  */
 
 void
@@ -1122,7 +1159,7 @@ cgraph_edge::speculative_call_info (cgraph_edge *&direct,
 
   reference = NULL;
   for (i = 0; e->caller->iterate_reference (i, ref); i++)
-    if (ref->speculative
+    if (ref->speculative && ref->speculative_id == e->speculative_id
 	&& ((ref->stmt && ref->stmt == e->call_stmt)
 	    || (!ref->stmt && ref->lto_stmt_uid == e->lto_stmt_uid)))
       {
@@ -1138,9 +1175,18 @@ cgraph_edge::speculative_call_info (cgraph_edge *&direct,
 
 /* Speculative call EDGE turned out to be direct call to CALLEE_DECL.  Remove
    the speculative call sequence and return edge representing the call, the
-   original EDGE can be removed and deallocated.  It is up to caller to
-   redirect the call as appropriate.  Return the edge that now represents the
-   call.  */
+   original EDGE can be removed and deallocated.  Return the edge that now
+   represents the call.
+
+   For "speculative" indirect call that contains multiple "speculative"
+   targets (i.e. edge->indirect_info->num_speculative_call_targets > 1),
+   decrease the count and only remove current direct edge.
+
+   If no speculative direct call left to the speculative indirect call, remove
+   the speculative of both the indirect call and corresponding direct edge.
+
+   It is up to caller to iteratively resolve each "speculative" direct call and
+   redirect the call as appropriate.  */
 
 cgraph_edge *
 cgraph_edge::resolve_speculation (cgraph_edge *edge, tree callee_decl)
@@ -1184,7 +1230,16 @@ cgraph_edge::resolve_speculation (cgraph_edge *edge, tree callee_decl)
          in the functions inlined through it.  */
     }
   edge->count += e2->count;
-  edge->speculative = false;
+  if (edge->num_speculative_call_targets_p ())
+    {
+      /* The indirect edge has multiple speculative targets, don't remove
+	 speculative until all related direct edges are resolved.  */
+      edge->indirect_info->num_speculative_call_targets--;
+      if (!edge->indirect_info->num_speculative_call_targets)
+	edge->speculative = false;
+    }
+  else
+    edge->speculative = false;
   e2->speculative = false;
   ref->remove_reference ();
   if (e2->indirect_unknown_callee || e2->inline_failed)
@@ -1244,7 +1299,17 @@ cgraph_edge::make_direct (cgraph_edge *edge, cgraph_node *callee)
 
 /* If necessary, change the function declaration in the call statement
    associated with E so that it corresponds to the edge callee.  Speculations
-   can be resolved in the process and EDGE can be removed and deallocated.  */
+   can be resolved in the process and EDGE can be removed and deallocated.
+
+   The edge could be one of speculative direct call generated from speculative
+   indirect call.  In this circumstance, decrease the speculative targets
+   count (i.e. num_speculative_call_targets) and redirect call stmt to the
+   corresponding i-th target.  If no speculative direct call left to the
+   speculative indirect call, remove "speculative" of the indirect call and
+   also redirect stmt to it's final direct target.
+
+   It is up to caller to iteratively transform each "speculative"
+   direct call as appropriate.  */
 
 gimple *
 cgraph_edge::redirect_call_stmt_to_callee (cgraph_edge *e)
@@ -1290,7 +1355,17 @@ cgraph_edge::redirect_call_stmt_to_callee (cgraph_edge *e)
 	  e->caller->set_call_stmt_including_clones (e->call_stmt, new_stmt,
 						     false);
 	  e->count = gimple_bb (e->call_stmt)->count;
-	  e2->speculative = false;
+	  if (e2->num_speculative_call_targets_p ())
+	    {
+	      /* The indirect edge has multiple speculative targets, don't
+		 remove speculative until all related direct edges are
+		 redirected.  */
+	      e2->indirect_info->num_speculative_call_targets--;
+	      if (!e2->indirect_info->num_speculative_call_targets)
+		e2->speculative = false;
+	    }
+	  else
+	    e2->speculative = false;
 	  e2->count = gimple_bb (e2->call_stmt)->count;
 	  ref->speculative = false;
 	  ref->stmt = NULL;
@@ -2103,6 +2178,8 @@ cgraph_node::dump (FILE *f)
 	  if (edge->indirect_info->vptr_changed)
 	    fprintf (f, " (vptr maybe changed)");
 	}
+      fprintf (f, " Num speculative call targets: %i",
+	       edge->indirect_info->num_speculative_call_targets);
       fprintf (f, "\n");
       if (edge->indirect_info->polymorphic)
 	edge->indirect_info->context.dump (f);
@@ -3393,7 +3470,7 @@ cgraph_node::verify_node (void)
 
       for (e = callees; e; e = e->next_callee)
 	{
-	  if (!e->aux)
+	  if (!e->aux && !e->speculative)
 	    {
 	      error ("edge %s->%s has no corresponding call_stmt",
 		     identifier_to_locale (e->caller->name ()),
@@ -3732,6 +3809,14 @@ cgraph_edge::possibly_call_in_translation_unit_p (void)
   return node->get_availability () >= AVAIL_INTERPOSABLE;
 }
 
+/* Return num_speculative_targets of this edge.  */
+
+int
+cgraph_edge::num_speculative_call_targets_p (void)
+{
+  return indirect_info ? indirect_info->num_speculative_call_targets : 0;
+}
+
 /* A stashed copy of "symtab" for use by selftest::symbol_table_test.
    This needs to be a global so that it can be a GC root, and thus
    prevent the stashed copy from being garbage-collected if the GC runs