PR ipa/59775 (get_binfo_at_offset not handling virtual inheritance well)

PR ipa/59775 (get_binfo_at_offset not handling virtual inheritance well)

[Jan Hubicka]

Hi,
this patch fixes ICE in ipa-devirt that is caused by get_binfo_at_offset
reporting NULL for a valid query.  This is because how virtual inheritance
is represented.

Here we have chain A<-B<-C where A is a virtual base.  We look for A within
C that is there at offset 64.  On this query get_binfo_at_offset walks
fields of C and it finds A, it matches it and it looks for BINFO. The
catch is that BINFO represents only direct bases and A is not direct base.
Conseuqentely it returns NULL. In the past this only prevented us from
devirtualizing here, now we ICE, since ipa-devirt depends on fact that
it can resolve all possible queries. get_binfo_at_offset needs to make a hop
through B.

This patch is kind of minimal change needed to get get_binfo_at_offset to
look into B: when base is not found, it finds a base that contains A
and dives into it.

I plan to rewrite the function for next stage1: the walk of fields is already
done by ipa-devirt separately, so it really should do only BINFO walk.  For
that we however need to retire other uses of get_binfo_at_offset that are still
used by ipa-devirt.  That is on the TODO list to switch it to be basically a
propagation engine for ipa-devirt's polymorphic_call_context structures.
(basically I want to have one local pass doing non-trivial propagation and
one IPA pass propagation across function boundaries, both sharing
polymorphic_call_context structure and a lattice operations)

Bootstrapped/regtested x86_64-linux, OK with the testcase?

struct A
{
  virtual void foo () = 0;
  void bar () { foo (); }
  bool a;
};
struct B : public virtual A
{
  virtual void foo ();
};
struct C : public B
{
  C ();
};
void
baz ()
{
  C c;
  c.bar ();
}
	PR ipa/59775
	* tree.c (get_binfo_at_offset): Look harder for virtual bases.
Index: tree.c
===================================================================
--- tree.c	(revision 206617)
+++ tree.c	(working copy)
@@ -11995,16 +11995,35 @@ get_binfo_at_offset (tree binfo, HOST_WI
 	 represented in the binfo for the derived class.  */
       else if (offset != 0)
 	{
-	  tree base_binfo, found_binfo = NULL_TREE;
-	  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
-	    if (types_same_for_odr (TREE_TYPE (base_binfo), TREE_TYPE (fld)))
-	      {
-		found_binfo = base_binfo;
-		break;
-	      }
-	  if (!found_binfo)
-	    return NULL_TREE;
-	  binfo = found_binfo;
+	  tree base_binfo, binfo2 = binfo;
+
+	  /* Find BINFO corresponding to FLD.  This is bit harder
+	     by a fact that in virtual inheritance we may need to walk down
+	     the non-virtual inheritance chain.  */
+	  while (true)
+	    {
+	      tree containing_binfo = NULL, found_binfo = NULL;
+	      for (i = 0; BINFO_BASE_ITERATE (binfo2, i, base_binfo); i++)
+		if (types_same_for_odr (TREE_TYPE (base_binfo), TREE_TYPE (fld)))
+		  {
+		    found_binfo = base_binfo;
+		    break;
+		  }
+		else
+		  if (BINFO_OFFSET (base_binfo) - BINFO_OFFSET (binfo) < pos
+		      && (!containing_binfo
+			  || (BINFO_OFFSET (containing_binfo)
+			      < BINFO_OFFSET (base_binfo))))
+		    containing_binfo = base_binfo;
+	      if (found_binfo)
+		{
+		  binfo = found_binfo;
+		  break;
+		}
+	      if (!containing_binfo)
+		return NULL_TREE;
+	      binfo2 = containing_binfo;
+	    }
 	}
 
       type = TREE_TYPE (fld);

Re: PR ipa/59775 (get_binfo_at_offset not handling virtual inheritance well)

[Jan Hubicka]

> Hi,
> this patch fixes ICE in ipa-devirt that is caused by get_binfo_at_offset
> reporting NULL for a valid query.  This is because how virtual inheritance
> is represented.
> 
> Here we have chain A<-B<-C where A is a virtual base.  We look for A within
> C that is there at offset 64.  On this query get_binfo_at_offset walks
> fields of C and it finds A, it matches it and it looks for BINFO. The
> catch is that BINFO represents only direct bases and A is not direct base.
> Conseuqentely it returns NULL. In the past this only prevented us from
> devirtualizing here, now we ICE, since ipa-devirt depends on fact that
> it can resolve all possible queries. get_binfo_at_offset needs to make a hop
> through B.
> 
> This patch is kind of minimal change needed to get get_binfo_at_offset to
> look into B: when base is not found, it finds a base that contains A
> and dives into it.
> 
> I plan to rewrite the function for next stage1: the walk of fields is already
> done by ipa-devirt separately, so it really should do only BINFO walk.  For
> that we however need to retire other uses of get_binfo_at_offset that are still
> used by ipa-devirt.  That is on the TODO list to switch it to be basically a

	  ^^^ ipa-cp, that is the only place still ging through
	gimple_extract_devirt_binfo_from_cst that works in a way so
	get_binfo_at_offset needs to dive into fields.

> propagation engine for ipa-devirt's polymorphic_call_context structures.
> (basically I want to have one local pass doing non-trivial propagation and
> one IPA pass propagation across function boundaries, both sharing
> polymorphic_call_context structure and a lattice operations)

Re: PR ipa/59775 (get_binfo_at_offset not handling virtual inheritance well)

[Richard Biener]

On Wed, 15 Jan 2014, Jan Hubicka wrote:

> Hi,
> this patch fixes ICE in ipa-devirt that is caused by get_binfo_at_offset
> reporting NULL for a valid query.  This is because how virtual inheritance
> is represented.
> 
> Here we have chain A<-B<-C where A is a virtual base.  We look for A within
> C that is there at offset 64.  On this query get_binfo_at_offset walks
> fields of C and it finds A, it matches it and it looks for BINFO. The
> catch is that BINFO represents only direct bases and A is not direct base.
> Conseuqentely it returns NULL. In the past this only prevented us from
> devirtualizing here, now we ICE, since ipa-devirt depends on fact that
> it can resolve all possible queries. 

Ugh - not sure that I like that.  Are we sure we preserve enough
info with LTO?

> get_binfo_at_offset needs to make a hop
> through B.
> 
> This patch is kind of minimal change needed to get get_binfo_at_offset to
> look into B: when base is not found, it finds a base that contains A
> and dives into it.
> 
> I plan to rewrite the function for next stage1: the walk of fields is already
> done by ipa-devirt separately, so it really should do only BINFO walk.  For
> that we however need to retire other uses of get_binfo_at_offset that are still
> used by ipa-devirt.  That is on the TODO list to switch it to be basically a
> propagation engine for ipa-devirt's polymorphic_call_context structures.
> (basically I want to have one local pass doing non-trivial propagation and
> one IPA pass propagation across function boundaries, both sharing
> polymorphic_call_context structure and a lattice operations)

Does that get rid of the seemingly costly linear walks?  Or should
we think of a data-structure that is more suited for these kind of
lookups in the long run?

> Bootstrapped/regtested x86_64-linux, OK with the testcase?

Ok.

Thanks,
Richard.

> struct A
> {
>   virtual void foo () = 0;
>   void bar () { foo (); }
>   bool a;
> };
> struct B : public virtual A
> {
>   virtual void foo ();
> };
> struct C : public B
> {
>   C ();
> };
> void
> baz ()
> {
>   C c;
>   c.bar ();
> }
> 	PR ipa/59775
> 	* tree.c (get_binfo_at_offset): Look harder for virtual bases.
> Index: tree.c
> ===================================================================
> --- tree.c	(revision 206617)
> +++ tree.c	(working copy)
> @@ -11995,16 +11995,35 @@ get_binfo_at_offset (tree binfo, HOST_WI
>  	 represented in the binfo for the derived class.  */
>        else if (offset != 0)
>  	{
> -	  tree base_binfo, found_binfo = NULL_TREE;
> -	  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
> -	    if (types_same_for_odr (TREE_TYPE (base_binfo), TREE_TYPE (fld)))
> -	      {
> -		found_binfo = base_binfo;
> -		break;
> -	      }
> -	  if (!found_binfo)
> -	    return NULL_TREE;
> -	  binfo = found_binfo;
> +	  tree base_binfo, binfo2 = binfo;
> +
> +	  /* Find BINFO corresponding to FLD.  This is bit harder
> +	     by a fact that in virtual inheritance we may need to walk down
> +	     the non-virtual inheritance chain.  */
> +	  while (true)
> +	    {
> +	      tree containing_binfo = NULL, found_binfo = NULL;
> +	      for (i = 0; BINFO_BASE_ITERATE (binfo2, i, base_binfo); i++)
> +		if (types_same_for_odr (TREE_TYPE (base_binfo), TREE_TYPE (fld)))
> +		  {
> +		    found_binfo = base_binfo;
> +		    break;
> +		  }
> +		else
> +		  if (BINFO_OFFSET (base_binfo) - BINFO_OFFSET (binfo) < pos
> +		      && (!containing_binfo
> +			  || (BINFO_OFFSET (containing_binfo)
> +			      < BINFO_OFFSET (base_binfo))))
> +		    containing_binfo = base_binfo;
> +	      if (found_binfo)
> +		{
> +		  binfo = found_binfo;
> +		  break;
> +		}
> +	      if (!containing_binfo)
> +		return NULL_TREE;
> +	      binfo2 = containing_binfo;
> +	    }
>  	}
>  
>        type = TREE_TYPE (fld);
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer

Re: PR ipa/59775 (get_binfo_at_offset not handling virtual inheritance well)

[Jan Hubicka]

> On Wed, 15 Jan 2014, Jan Hubicka wrote:
> 
> > Hi,
> > this patch fixes ICE in ipa-devirt that is caused by get_binfo_at_offset
> > reporting NULL for a valid query.  This is because how virtual inheritance
> > is represented.
> > 
> > Here we have chain A<-B<-C where A is a virtual base.  We look for A within
> > C that is there at offset 64.  On this query get_binfo_at_offset walks
> > fields of C and it finds A, it matches it and it looks for BINFO. The
> > catch is that BINFO represents only direct bases and A is not direct base.
> > Conseuqentely it returns NULL. In the past this only prevented us from
> > devirtualizing here, now we ICE, since ipa-devirt depends on fact that
> > it can resolve all possible queries. 
> 
> Ugh - not sure that I like that.  Are we sure we preserve enough
> info with LTO?

Yes, we have have all information here. We only need precise ODR info for
polymorphic types that is given by vtable mangling and save way to look
into vtables.  We also have several sanity checks to verify that this
works as expected (that also triggered on this bug).

There is other PR that is ICE on invalid C++ programs with LTO. My plan is
to add a diagnostic comparing sizes of vtables and warn user about ODR violation
+ relax the sanity checks when violation was reported.

I will do that later this week.
> 
> > get_binfo_at_offset needs to make a hop
> > through B.
> > 
> > This patch is kind of minimal change needed to get get_binfo_at_offset to
> > look into B: when base is not found, it finds a base that contains A
> > and dives into it.
> > 
> > I plan to rewrite the function for next stage1: the walk of fields is already
> > done by ipa-devirt separately, so it really should do only BINFO walk.  For
> > that we however need to retire other uses of get_binfo_at_offset that are still
> > used by ipa-devirt.  That is on the TODO list to switch it to be basically a
> > propagation engine for ipa-devirt's polymorphic_call_context structures.
> > (basically I want to have one local pass doing non-trivial propagation and
> > one IPA pass propagation across function boundaries, both sharing
> > polymorphic_call_context structure and a lattice operations)
> 
> Does that get rid of the seemingly costly linear walks?  Or should
> we think of a data-structure that is more suited for these kind of
> lookups in the long run?

It will avoid the double walk (looking up filed + looking up binfo) and the
binfo walk is definitely cheaper than fields walk.

I did quite some profiling on firefox and webkit with the query cache disabled
and the only important hot spot seems to be gimple_get_virt_method_for_binfo
that looks up into virtual tables via generic folding code that is insanely
slow. 

If that becomes a problem, we definitely either speed up the folder or can have
alternative representation of vtables as simple vectors of method pointers to
make this O(1).

As for the type walking, it is simple recursive walk down to the specified location.
Since BINFOs can be assumed to be ordered by offsets, we can implement binary search
for classes with very many direct bases.

I am unsure what to do for classes with very deep inehritance tree, but we will run
out of stack bounds on them anyway since a lot of code walking them uses recursion
(including the C++ parser)
> 
> > Bootstrapped/regtested x86_64-linux, OK with the testcase?
> 
> Ok.
Thanks,
Honza