Subject: [PATCH] [PR 89330] Remove non-useful speculations from new_edges

Hi,

the following patch prevents the call speculation machinery from
deallocating call graph edges from under the indirect inlining machinery
and it also fixes a potential issue in speculation which could in some
cases undo an earlier inlining decision, something that the inliner is
not built to expect.

That latter change requires disabling speculation on a testcase through
adding -fno-profile-values, otherwise a devirtualziation happens before
it is dump-scanned for.

Bootstrapped and tested on an x86_64-linux, OK for trunk?

Thanks,

Martin


2019-07-25  Martin Jambor  <mjambor@suse.cz>

	PR ipa/89330
	* ipa-inline-transform.c (check_speculations_1): New function.
	(push_all_edges_in_set_to_vec): Likewise.
	(check_speculations): Use check_speculations_1, new parameter
	new_edges.
	(inline_call): Pass new_edges to check_speculations.
	* ipa-inline.c (add_new_edges_to_heap): Assert edge_callee is not
	NULL.
	(speculation_useful_p): Early return true if edge is inlined, remove
	later checks for inline_failed.

	testsuite/
	* g++.dg/lto/pr89330_[01].C: New test.
	* g++.dg/tree-prof/devirt.C: Added -fno-profile-values to dg-options.
---
 gcc/ipa-inline-transform.c              | 42 +++++++++++++++++++--
 gcc/ipa-inline.c                        | 12 ++++--
 gcc/testsuite/g++.dg/lto/pr89330_0.C    | 50 +++++++++++++++++++++++++
 gcc/testsuite/g++.dg/lto/pr89330_1.C    | 36 ++++++++++++++++++
 gcc/testsuite/g++.dg/tree-prof/devirt.C |  2 +-
 5 files changed, 133 insertions(+), 9 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/lto/pr89330_0.C
 create mode 100644 gcc/testsuite/g++.dg/lto/pr89330_1.C

> Hi,
> 
> the following patch prevents the call speculation machinery from
> deallocating call graph edges from under the indirect inlining machinery
> and it also fixes a potential issue in speculation which could in some
> cases undo an earlier inlining decision, something that the inliner is
> not built to expect.
> 
> That latter change requires disabling speculation on a testcase through
> adding -fno-profile-values, otherwise a devirtualziation happens before
> it is dump-scanned for.
> 
> Bootstrapped and tested on an x86_64-linux, OK for trunk?

OK,
thanks!
Honza
> 
> Thanks,
> 
> Martin
> 
> 
> 2019-07-25  Martin Jambor  <mjambor@suse.cz>
> 
> 	PR ipa/89330
> 	* ipa-inline-transform.c (check_speculations_1): New function.
> 	(push_all_edges_in_set_to_vec): Likewise.
> 	(check_speculations): Use check_speculations_1, new parameter
> 	new_edges.
> 	(inline_call): Pass new_edges to check_speculations.
> 	* ipa-inline.c (add_new_edges_to_heap): Assert edge_callee is not
> 	NULL.
> 	(speculation_useful_p): Early return true if edge is inlined, remove
> 	later checks for inline_failed.
> 
> 	testsuite/
> 	* g++.dg/lto/pr89330_[01].C: New test.
> 	* g++.dg/tree-prof/devirt.C: Added -fno-profile-values to dg-options.
> ---
>  gcc/ipa-inline-transform.c              | 42 +++++++++++++++++++--
>  gcc/ipa-inline.c                        | 12 ++++--
>  gcc/testsuite/g++.dg/lto/pr89330_0.C    | 50 +++++++++++++++++++++++++
>  gcc/testsuite/g++.dg/lto/pr89330_1.C    | 36 ++++++++++++++++++
>  gcc/testsuite/g++.dg/tree-prof/devirt.C |  2 +-
>  5 files changed, 133 insertions(+), 9 deletions(-)
>  create mode 100644 gcc/testsuite/g++.dg/lto/pr89330_0.C
>  create mode 100644 gcc/testsuite/g++.dg/lto/pr89330_1.C
> 
> diff --git a/gcc/ipa-inline-transform.c b/gcc/ipa-inline-transform.c
> index 4a3a193bc9c..897c563f19a 100644
> --- a/gcc/ipa-inline-transform.c
> +++ b/gcc/ipa-inline-transform.c
> @@ -237,10 +237,13 @@ clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
>      }
>  }
>  
> -/* Check all speculations in N and resolve them if they seems useless. */
> +/* Check all speculations in N and if any seem useless, resolve them.  When a
> +   first edge is resolved, pop all edges from NEW_EDGES and insert them to
> +   EDGE_SET.  Then remove each resolved edge from EDGE_SET, if it is there.  */
>  
>  static bool
> -check_speculations (cgraph_node *n)
> +check_speculations_1 (cgraph_node *n, vec<cgraph_edge *> *new_edges,
> +		      hash_set <cgraph_edge *> *edge_set)
>  {
>    bool speculation_removed = false;
>    cgraph_edge *next;
> @@ -250,15 +253,46 @@ check_speculations (cgraph_node *n)
>        next = e->next_callee;
>        if (e->speculative && !speculation_useful_p (e, true))
>  	{
> +	  while (new_edges && !new_edges->is_empty ())
> +	    edge_set->add (new_edges->pop ());
> +	  edge_set->remove (e);
> +
>  	  e->resolve_speculation (NULL);
>  	  speculation_removed = true;
>  	}
>        else if (!e->inline_failed)
> -	speculation_removed |= check_speculations (e->callee);
> +	speculation_removed |= check_speculations_1 (e->callee, new_edges,
> +						     edge_set);
>      }
>    return speculation_removed;
>  }
>  
> +/* Push E to NEW_EDGES.  Called from hash_set traverse method, which
> +   unfortunately means this function has to have external linkage, otherwise
> +   the code will not compile with gcc 4.8.  */
> +
> +bool
> +push_all_edges_in_set_to_vec (cgraph_edge * const &e,
> +			      vec<cgraph_edge *> *new_edges)
> +{
> +  new_edges->safe_push (e);
> +  return true;
> +}
> +
> +/* Check all speculations in N and if any seem useless, resolve them and remove
> +   them from NEW_EDGES.  */
> +
> +static bool
> +check_speculations (cgraph_node *n, vec<cgraph_edge *> *new_edges)
> +{
> +  hash_set <cgraph_edge *> edge_set;
> +  bool res = check_speculations_1 (n, new_edges, &edge_set);
> +  if (!edge_set.is_empty ())
> +    edge_set.traverse <vec<cgraph_edge *> *,
> +		       push_all_edges_in_set_to_vec> (new_edges);
> +  return res;
> +}
> +
>  /* Mark all call graph edges coming out of NODE and all nodes that have been
>     inlined to it as in_polymorphic_cdtor.  */
>  
> @@ -450,7 +484,7 @@ inline_call (struct cgraph_edge *e, bool update_original,
>      mark_all_inlined_calls_cdtor (e->callee);
>    if (opt_for_fn (e->caller->decl, optimize))
>      new_edges_found = ipa_propagate_indirect_call_infos (curr, new_edges);
> -  check_speculations (e->callee);
> +  check_speculations (e->callee, new_edges);
>    if (update_overall_summary)
>      ipa_update_overall_fn_summary (to);
>    else
> diff --git a/gcc/ipa-inline.c b/gcc/ipa-inline.c
> index 5862d00008d..0f1699a182f 100644
> --- a/gcc/ipa-inline.c
> +++ b/gcc/ipa-inline.c
> @@ -1626,6 +1626,7 @@ add_new_edges_to_heap (edge_heap_t *heap, vec<cgraph_edge *> new_edges)
>        struct cgraph_edge *edge = new_edges.pop ();
>  
>        gcc_assert (!edge->aux);
> +      gcc_assert (edge->callee);
>        if (edge->inline_failed
>  	  && can_inline_edge_p (edge, true)
>  	  && want_inline_small_function_p (edge, true)
> @@ -1653,6 +1654,10 @@ heap_edge_removal_hook (struct cgraph_edge *e, void *data)
>  bool
>  speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining)
>  {
> +  /* If we have already decided to inline the edge, it seems useful.  */
> +  if (!e->inline_failed)
> +    return true;
> +
>    enum availability avail;
>    struct cgraph_node *target = e->callee->ultimate_alias_target (&avail,
>  								 e->caller);
> @@ -1687,12 +1692,11 @@ speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining)
>       to an ipa-cp clone (that are seen by having local flag set),
>       it is probably pointless to inline it unless hardware is missing
>       indirect call predictor.  */
> -  if (!anticipate_inlining && e->inline_failed && !target->local.local)
> +  if (!anticipate_inlining && !target->local.local)
>      return false;
>    /* For overwritable targets there is not much to do.  */
> -  if (e->inline_failed
> -      && (!can_inline_edge_p (e, false)
> -	  || !can_inline_edge_by_limits_p (e, false, true)))
> +  if (!can_inline_edge_p (e, false)
> +      || !can_inline_edge_by_limits_p (e, false, true))
>      return false;
>    /* OK, speculation seems interesting.  */
>    return true;
> diff --git a/gcc/testsuite/g++.dg/lto/pr89330_0.C b/gcc/testsuite/g++.dg/lto/pr89330_0.C
> new file mode 100644
> index 00000000000..10082f83412
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/lto/pr89330_0.C
> @@ -0,0 +1,50 @@
> +// { dg-lto-do link }
> +// { dg-lto-options { { -O3 -g -flto -shared -Wno-odr } } }
> +
> +namespace Inkscape {
> +class Anchored {};
> +namespace XML {
> +enum NodeType {};
> +class Node :Anchored {
> +public:
> +  virtual NodeType type() ;
> +  virtual char name() ;
> +  virtual int code() ;
> +  virtual unsigned position() ;
> +  virtual unsigned childCount() ;
> +  virtual char content() ;
> +  virtual char *attribute() const ;
> +  virtual int attributeList() ;
> +  virtual bool matchAttributeName() ;
> +  virtual void setPosition() ;
> +  virtual void setContent() ;
> +  virtual void setAttribute() ;
> +  virtual int document() ;
> +  virtual int document() const ;
> +  virtual Node *root() ;
> +  virtual Node *root() const ;
> +  virtual Node *parent() ;
> +  virtual Node *next() const ;
> +  virtual Node *firstChild() const ;
> +
> +};
> +} } struct rdf_license_t {
> +  };
> +;
> +class RDFImpl {
> +;
> +  rdf_license_t *getLicense();
> +};
> +static bool rdf_match_license(Inkscape::XML::Node const *repr) {
> +  for (Inkscape::XML::Node *current = repr->firstChild(); current;
> +       current->next()->attribute());
> +  return 0;
> +}
> +rdf_license_t *RDFImpl::getLicense() {
> +  Inkscape::XML::Node *repr ;
> +  for (rdf_license_t *license ; license;
> +       license) {
> +    rdf_match_license(repr);
> +  }
> +  return 0;
> +}
> diff --git a/gcc/testsuite/g++.dg/lto/pr89330_1.C b/gcc/testsuite/g++.dg/lto/pr89330_1.C
> new file mode 100644
> index 00000000000..5b999eee8d7
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/lto/pr89330_1.C
> @@ -0,0 +1,36 @@
> +typedef char gchar;
> +namespace Inkscape {
> +class Anchored {
> +int _anchor;
> +};
> +namespace XML {
> +enum NodeType {};
> +class Node :Anchored {
> +virtual NodeType type() ;
> +  virtual char const *name() const ;
> +  virtual int code() ;
> +  virtual unsigned position() ;
> +  virtual unsigned childCount() ;
> +  virtual char content() ;
> +  virtual char attribute() ;
> +  virtual int attributeList() ;
> +  virtual bool matchAttributeName() ;
> +  virtual void setPosition() ;
> +  virtual void setContent() ;
> +  virtual int document() ;
> +  virtual int document() const ;
> +  virtual Node *root() ;
> +  virtual Node *root() const ;
> +  virtual Node *parent() ;
> +  virtual Node *parent() const ;
> +  virtual Node *next() ;
> +  virtual Node const *next() const ;
> +
> +};
> +class SimpleNode : virtual Node {
> +char const *name() const;
> +  Node *next() const { return _next; }
> +  SimpleNode *_next;
> +};
> +gchar const *SimpleNode::name() const { return 0; }
> +} } 
> diff --git a/gcc/testsuite/g++.dg/tree-prof/devirt.C b/gcc/testsuite/g++.dg/tree-prof/devirt.C
> index d8fb2d9ef46..1121f487157 100644
> --- a/gcc/testsuite/g++.dg/tree-prof/devirt.C
> +++ b/gcc/testsuite/g++.dg/tree-prof/devirt.C
> @@ -1,5 +1,5 @@
>  /* PR ipa/88561 */
> -/* { dg-options "-O3 -fdump-tree-tracer-details -fdump-tree-dom3-details" } */
> +/* { dg-options "-O3 -fdump-tree-tracer-details -fdump-tree-dom3-details -fno-profile-values" } */
>  
>  struct nsISupports
>  {
> -- 
> 2.22.0
>

Hi Martin,

> the following patch prevents the call speculation machinery from
> deallocating call graph edges from under the indirect inlining machinery
> and it also fixes a potential issue in speculation which could in some
> cases undo an earlier inlining decision, something that the inliner is
> not built to expect.
>
> That latter change requires disabling speculation on a testcase through
> adding -fno-profile-values, otherwise a devirtualziation happens before
> it is dump-scanned for.
>
> Bootstrapped and tested on an x86_64-linux, OK for trunk?
[...]
> 2019-07-25  Martin Jambor  <mjambor@suse.cz>
>
> 	PR ipa/89330
> 	* ipa-inline-transform.c (check_speculations_1): New function.
> 	(push_all_edges_in_set_to_vec): Likewise.
> 	(check_speculations): Use check_speculations_1, new parameter
> 	new_edges.
> 	(inline_call): Pass new_edges to check_speculations.
> 	* ipa-inline.c (add_new_edges_to_heap): Assert edge_callee is not
> 	NULL.
> 	(speculation_useful_p): Early return true if edge is inlined, remove
> 	later checks for inline_failed.
>
> 	testsuite/
> 	* g++.dg/lto/pr89330_[01].C: New test.

the new test FAILs on Solaris:

+FAIL: g++.dg/lto/pr89330 cp_lto_pr89330_0.o-cp_lto_pr89330_1.o link,  -O3 -g -flto -shared -Wno-odr 

Text relocation remains                         referenced
    against symbol                  offset      in file
Inkscape::XML::Node::root()         0x9c        cp_lto_pr89330_1.o
virtual thunk to Inkscape::XML::SimpleNode::name() const 0x6c           cp_lto_pr89330_1.o
Inkscape::XML::Node::parent()       0xa4        cp_lto_pr89330_1.o
Inkscape::XML::Node::document() const 0x98              cp_lto_pr89330_1.o
Inkscape::XML::Node::next()         0xac        cp_lto_pr89330_1.o
[...]
Inkscape::XML::Node::code()         0x70        cp_lto_pr89330_1.o
Inkscape::XML::SimpleNode::name() const 0xc             cp_lto_pr89330_1.o
Inkscape::XML::Node::document()     0x94        cp_lto_pr89330_1.o
ld: fatal: relocations remain against allocatable but non-writable sections
collect2: error: ld returned 1 exit status

This happens because ld defaults to -z text here and can easily be
avoided by compiling the code as PIC.

This is what the following patch does.  Tested on i386-pc-solaris2.11,
sparc-sun-solaris2.11, and x86_64-pc-linux-gnu, installed on mainline.

	Rainer