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

[Richard Biener <rguenther at suse dot de>]

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