diff mbox

PR ipa/59831 (ipa-cp devirt issues)

Message ID 20140131062254.GA28026@kam.mff.cuni.cz
State New
Headers show

Commit Message

Jan Hubicka Jan. 31, 2014, 6:22 a.m. UTC 
Hi,
PR ipa/59831 has testcase with one virtual call that shows really interesting
sequence of events.  First we speculatively identify the target of call. Next
ipa-cp correctly works out the target and decides to clone.  While creating a
clone it however no longer identifies the direct edge.  It is because in
meantime it worked out the exact value of the pointer (&globalvar) and thrown
away the binfo information we used previously.  ipa-cp tries to look up the
binfo again, but it uses gimple_extract_devirt_binfo_from_cst that is not as
good at doing the same work as ipa-devirt is.  For bogus reason (empty base
class) it gives up.  Consequently we create the clone and propagate value, then
we hit recursive inlining and it tries to save the function body. While doing
so, it calls fold on the (now substituted) function body and it works out the
virtual call target.  This leads to ICE since it tries to resolve the call and
remove the speculation before the body is fully copied.

This patch sanitizes behaviour of ipa-cp. I decided to remove
gimple_extract_devirt_binfo_from_cst since ipa-devirt already has all logic in
it, it was just not available to ipa-cp (it was on my TODO for a while). 

To however prevent consistently the deivrutalization, we I added code to use
aggregate value info.  It is quite easy to do: when we know the virtual table
pointer, we can lookup the BINFO same was as extr_type_from_vtbl_ptr_store
already does - by checking DECL_CONTEXT of the vtable. I borrowed the logic and
hardened it a bit by extra sanity checking in vtable_pointer_value_to_binfo.

Since I asked about it, I discovered bug in that logic: in the case of multiple
inheritance, we may end up having one vtable nested in another and vtable
initialization like &vtable+120, instead of default 16.  In this case we
definitely can not conclude that the dynamic type is the object is the CONTEXT
of vtable, since the it is the dynamic type of the object with some non-zero
offset.

I added code to vtable_pointer_value_to_binfo to lookup the proper binfo of
base with vtable at given offset, but sadly I can't hook it easily to 
extr_type_from_vtbl_ptr_store, so I made it to give up in that case for now.

Bootstrapped/regtested x86_64-linux, tested on firefox LTO where it adds
10 new devirtualizations (out of 1200). Will commit it tomorrow if there are
no complains.  There is one devirtualization fewer on javascript that is
due to extra checking I added to the instance type lookup.

Honza

	PR ipa/59831
	* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): Remove.
	* ipa-devirt.c (get_poymorphic_call_info_for_decl): Break out from ...
	(get_polymorphic_call_info): ... here.
	(get_polymorphic_call_info_from_invariant): New function based on
	gimple_extract_devirt_binfo_from_cst.
	(try_make_edge_direct_virtual_call): Update to use ipa-devirt.
	(ipa_get_indirect_edge_target_1): Likewise.
	(get_polymorphic_call_info_from_invariant): New function.
	(vtable_pointer_value_to_binfo): New function.
	* ipa-utils.h (get_polymorphic_call_info_from_invariant): Declare.
	(vtable_pointer_value_to_binfo): Declare.
	* ipa-prop.c (extr_type_from_vtbl_ptr_store): Use it.
	(try_make_edge_direct_virtual_call): Use aggregate propagation;
	rewrite handling of constants.
	* ipa-cp.c (ipa_get_indirect_edge_target_1): Likewise.

	* testsuite/g++.dg/ipa/devirt-21.C: New testcase.
	* testsuite/g++.dg/ipa/devirt-20.C: Fix template.

Comments

Jakub Jelinek Jan. 31, 2014, 6:44 a.m. UTC | #1 
On Fri, Jan 31, 2014 at 07:22:55AM +0100, Jan Hubicka wrote:
> --- ipa-devirt.c	(revision 207287)
> +++ ipa-devirt.c	(working copy)
> @@ -972,6 +972,120 @@ contains_type_p (tree outer_type, HOST_W
>    return get_class_context (&context, otr_type);
>  }
>  
> +/* Proudce polymorphic call context for call method of instance
> +   that is located within BASE (that is assumed to be a decl) at OFFSET. */
> +
> +static void
> +get_poymorphic_call_info_for_decl (ipa_polymorphic_call_context *context,
> +				   tree base, HOST_WIDE_INT offset)

Missing l in polymorphic.

	Jakub
Markus Trippelsdorf Jan. 31, 2014, 2:58 p.m. UTC | #2 
On 2014.01.31 at 07:22 +0100, Jan Hubicka wrote:
> +tree
> +vtable_pointer_value_to_binfo (tree t)
> +{
> +  /* We expect &MEM[(void *)&virtual_table + 16B].
> +     We obtain object's BINFO from the context of the virtual table. 
> +     This one contains pointer to virtual table represented via
> +     POINTER_PLUS_EXPR.  Verify that this pointer match to what
> +     we propagated through.
> +
> +     In the case of virtual inheritance, the virtual tables may
> +     be nested, i.e. the offset may be different from 16 and we may
> +     need to dive into the type representation.  */
> +  if (t && TREE_CODE (t) == ADDR_EXPR
> +      && TREE_CODE (TREE_OPERAND (t, 0)) == MEM_REF
> +      && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == ADDR_EXPR
> +      && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST
> +      && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0))
> +	  == VAR_DECL)
> +      && DECL_VIRTUAL_P (TREE_OPERAND (TREE_OPERAND
> +					 (TREE_OPERAND (t, 0), 0), 0)))
> +    {
> +      tree vtable = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0);
> +      tree offset = TREE_OPERAND (TREE_OPERAND (t, 0), 1);
> +      tree binfo = TYPE_BINFO (DECL_CONTEXT (vtable));
> +
> +      binfo = subbinfo_with_vtable_at_offset (binfo, offset, vtable);
> +      gcc_assert (binfo);
> +      return binfo;
> +    }
> +  return NULL;
> +}

I've tested your patch a little bit and hit the gcc_assert above:

markus@x4 tmp % cat test.ii
class A {
public:
  unsigned length;
};
class B {};
class MultiTermDocs : public virtual B {
protected:
  A readerTermDocs;
  A subReaders;
  virtual B *m_fn1(int *);
  virtual ~MultiTermDocs();
};
class C : MultiTermDocs {
  B *m_fn1(int *);
};
MultiTermDocs::~MultiTermDocs() {
  if (&readerTermDocs) {
    B *a;
    for (unsigned i = 0; i < subReaders.length; i++)
      (a != 0);
  }
}

B *C::m_fn1(int *) { return 0; }

markus@x4 tmp % g++ -O2 test.ii
test.ii: In destructor ‘virtual C::~C()’:
test.ii:24:32: internal compiler error: in vtable_pointer_value_to_binfo, at ipa-devirt.c:1082
 B *C::m_fn1(int *) { return 0; }
                                ^
0x9ca774 vtable_pointer_value_to_binfo(tree_node*)
        ../../gcc/gcc/ipa-devirt.c:1082
0x9e22b9 extr_type_from_vtbl_ptr_store
        ../../gcc/gcc/ipa-prop.c:606
0x9e22b9 check_stmt_for_type_change
        ../../gcc/gcc/ipa-prop.c:648
0xc18343 walk_aliased_vdefs_1
        ../../gcc/gcc/tree-ssa-alias.c:2472
0xc1846d walk_aliased_vdefs(ao_ref*, tree_node*, bool (*)(ao_ref*, tree_node*, void*), void*, bitmap_head**)
        ../../gcc/gcc/tree-ssa-alias.c:2491
0x9e1cba detect_type_change
        ../../gcc/gcc/ipa-prop.c:702
0x9e8b63 compute_complex_assign_jump_func
        ../../gcc/gcc/ipa-prop.c:1089
0x9e8b63 ipa_compute_jump_functions_for_edge
        ../../gcc/gcc/ipa-prop.c:1635
0x9eb882 ipa_compute_jump_functions
        ../../gcc/gcc/ipa-prop.c:1675
0x9eb882 ipa_analyze_node(cgraph_node*)
        ../../gcc/gcc/ipa-prop.c:2212
0x103ea7f ipcp_generate_summary
        ../../gcc/gcc/ipa-cp.c:3709
0xaa4906 execute_ipa_summary_passes(ipa_opt_pass_d*)
        ../../gcc/gcc/passes.c:2027
0x833dbb ipa_passes
        ../../gcc/gcc/cgraphunit.c:2070
0x833dbb compile()
        ../../gcc/gcc/cgraphunit.c:2174
0x834304 finalize_compilation_unit()
        ../../gcc/gcc/cgraphunit.c:2329
0x62efce cp_write_global_declarations()
        ../../gcc/gcc/cp/decl2.c:4447
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
Jan Hubicka Jan. 31, 2014, 6:10 p.m. UTC | #3 
> I've tested your patch a little bit and hit the gcc_assert above:
> 
> markus@x4 tmp % cat test.ii
> class A {
> public:
>   unsigned length;
> };
> class B {};
> class MultiTermDocs : public virtual B {
> protected:
>   A readerTermDocs;
>   A subReaders;
>   virtual B *m_fn1(int *);
>   virtual ~MultiTermDocs();
> };
> class C : MultiTermDocs {
>   B *m_fn1(int *);
> };
> MultiTermDocs::~MultiTermDocs() {
>   if (&readerTermDocs) {
>     B *a;
>     for (unsigned i = 0; i < subReaders.length; i++)
>       (a != 0);
>   }
> }
> 
> B *C::m_fn1(int *) { return 0; }

Thanks!  It is the case where we see a construction vtable store.  There is no
BINFO for that, so we need to give up trying to analyze the type.
We will need to improve our representation to handle this eventually, but
that is definitely not stage3 material.

I actualy wondered about this and tried to construct a testcase that did not
trigger for some reason and concluded that I probably don't care when it does
not fire for firefox.  Your testing (and reduced testcaes) are very useful.

I will drop the abort and add your testcase before comitting the patch.
I wonder if we can reproduce this as wrong code bug for gcc-4.8.  Basically
virtual calls in the destructors of the virtual base should get devirtualized
the wrong way.

Honza
> 
> markus@x4 tmp % g++ -O2 test.ii
> test.ii: In destructor ‘virtual C::~C()’:
> test.ii:24:32: internal compiler error: in vtable_pointer_value_to_binfo, at ipa-devirt.c:1082
>  B *C::m_fn1(int *) { return 0; }
>                                 ^
> 0x9ca774 vtable_pointer_value_to_binfo(tree_node*)
>         ../../gcc/gcc/ipa-devirt.c:1082
> 0x9e22b9 extr_type_from_vtbl_ptr_store
>         ../../gcc/gcc/ipa-prop.c:606
> 0x9e22b9 check_stmt_for_type_change
>         ../../gcc/gcc/ipa-prop.c:648
> 0xc18343 walk_aliased_vdefs_1
>         ../../gcc/gcc/tree-ssa-alias.c:2472
> 0xc1846d walk_aliased_vdefs(ao_ref*, tree_node*, bool (*)(ao_ref*, tree_node*, void*), void*, bitmap_head**)
>         ../../gcc/gcc/tree-ssa-alias.c:2491
> 0x9e1cba detect_type_change
>         ../../gcc/gcc/ipa-prop.c:702
> 0x9e8b63 compute_complex_assign_jump_func
>         ../../gcc/gcc/ipa-prop.c:1089
> 0x9e8b63 ipa_compute_jump_functions_for_edge
>         ../../gcc/gcc/ipa-prop.c:1635
> 0x9eb882 ipa_compute_jump_functions
>         ../../gcc/gcc/ipa-prop.c:1675
> 0x9eb882 ipa_analyze_node(cgraph_node*)
>         ../../gcc/gcc/ipa-prop.c:2212
> 0x103ea7f ipcp_generate_summary
>         ../../gcc/gcc/ipa-cp.c:3709
> 0xaa4906 execute_ipa_summary_passes(ipa_opt_pass_d*)
>         ../../gcc/gcc/passes.c:2027
> 0x833dbb ipa_passes
>         ../../gcc/gcc/cgraphunit.c:2070
> 0x833dbb compile()
>         ../../gcc/gcc/cgraphunit.c:2174
> 0x834304 finalize_compilation_unit()
>         ../../gcc/gcc/cgraphunit.c:2329
> 0x62efce cp_write_global_declarations()
>         ../../gcc/gcc/cp/decl2.c:4447
> Please submit a full bug report,
> with preprocessed source if appropriate.
> Please include the complete backtrace with any bug report.
> 
> 
> -- 
> Markus
Jan Hubicka Jan. 31, 2014, 8:48 p.m. UTC | #4 
Hi,
this is variant of testcase that produces wrong code on Mainline.

$ ./xgcc -B ./ -O3 ~/t.C -S -fno-partial-inlining -fno-early-inlining -fdump-ipa-all ; g++ t.s; ./a.out
Aborted

The bug is that we determine wrong type on call of ~MultiTermDocs within ~C (it
is determined as C, while it really should be C in construction).
Quite amusingly gcc-4.8 also determine the wrong type but does devirtualize correctly.  Martin,
any idea why?


#include <stdlib.h>
class A {                                                                                                                                                                                       
public:                                                                                                                                                                                         
  unsigned length;                                                                                                                                                                              
};                                                                                                                                                                                              
class B {};                                                                                                                                                                                     
class MultiTermDocs : public virtual B {                                                                                                                                                        
protected:                                                                                                                                                                                      
  A readerTermDocs;                                                                                                                                                                             
  A subReaders;                                                                                                                                                                                 
  virtual B *m_fn1(int *) {}                                                                                                                                                                     
  inline virtual ~MultiTermDocs();                                                                                                                                                                     
  void wrap(void)
  {
  m_fn1(NULL);
  }
};                                                                                                                                                                                              
class C : MultiTermDocs {                                                                                                                                                                       
  B *m_fn1(int *);                                                                                                                                                                              
};                                                                                                                                                                                              
MultiTermDocs::~MultiTermDocs() {                                                                                                                                                               
  wrap ();
  if (&readerTermDocs) {                                                                                                                                                                        
    B *a;                                                                                                                                                                                       
    for (unsigned i = 0; i < subReaders.length; i++)                                                                                                                                            
      (a != 0);                                                                                                                                                                                 
  }                                                                                                                                                                                             
}                                                                                                                                                                                               
                                                                                                                                                                                                
B *C::m_fn1(int *) { abort (); }                                                                                                                                                                
                                                                                                                                                                                                
main()
{
  class C c;
}
Jan Hubicka Jan. 31, 2014, 10:04 p.m. UTC | #5 
Hi,
here is even better testcase (in a sense that my patch does not solve the wrong code issue)

Compile with ./xgcc -B ./ -O3 ~/t.C -S -fno-partial-inlining -fno-early-inlining -fdump-ipa-all -fdump-tree-all -fipa-cp -fno-ipa-sra

Here the sequence is bit different.  Here we have contstruction table store done within destructor that
sets it accoridng to the second parameter. We hover still produce PASSTHROUGH function for it and
we end up propagating the wrong type.

Honza


#include <stdlib.h>
class A {                                                                                                                                                                                       
public:                                                                                                                                                                                         
  unsigned length;                                                                                                                                                                              
};                                                                                                                                                                                              
class B {};                                                                                                                                                                                     
class MultiTermDocs : public virtual B {                                                                                                                                                        
protected:                                                                                                                                                                                      
  A readerTermDocs;                                                                                                                                                                             
  A subReaders;                                                                                                                                                                                 
  virtual B *m_fn1(int *) {}                                                                                                                                                                     
  virtual inline  ~MultiTermDocs();                                                                                                                                                                     
  void wrap(void)
  {
  m_fn1(NULL);
  }
};                                                                                                                                                                                              
class C : MultiTermDocs {                                                                                                                                                                       
  B *m_fn1(int *);                                                                                                                                                                              
};                                                                                                                                                                                              
MultiTermDocs::~MultiTermDocs() {                                                                                                                                                               
  wrap ();
  if (&readerTermDocs) {                                                                                                                                                                        
    B *a;                                                                                                                                                                                       
    for (unsigned i = 0; i < subReaders.length; i++)                                                                                                                                            
      (a != 0);                                                                                                                                                                                 
  }                                                                                                                                                                                             
}                                                                                                                                                                                               
                                                                                                                                                                                                
B *C::m_fn1(int *) { abort (); }                                                                                                                                                                
                                                                                                                                                                                                
main()
{
  class C c;
}
Martin Jambor Feb. 4, 2014, 11:17 p.m. UTC | #6 
Hi,

On Fri, Jan 31, 2014 at 07:22:55AM +0100, Jan Hubicka wrote:

...

> 	PR ipa/59831
> 	* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): Remove.
> 	* ipa-devirt.c (get_poymorphic_call_info_for_decl): Break out from ...
> 	(get_polymorphic_call_info): ... here.
> 	(get_polymorphic_call_info_from_invariant): New function based on
> 	gimple_extract_devirt_binfo_from_cst.
> 	(try_make_edge_direct_virtual_call): Update to use ipa-devirt.
> 	(ipa_get_indirect_edge_target_1): Likewise.
> 	(get_polymorphic_call_info_from_invariant): New function.
> 	(vtable_pointer_value_to_binfo): New function.
> 	* ipa-utils.h (get_polymorphic_call_info_from_invariant): Declare.
> 	(vtable_pointer_value_to_binfo): Declare.
> 	* ipa-prop.c (extr_type_from_vtbl_ptr_store): Use it.
> 	(try_make_edge_direct_virtual_call): Use aggregate propagation;
> 	rewrite handling of constants.
> 	* ipa-cp.c (ipa_get_indirect_edge_target_1): Likewise.
> 
> 	* testsuite/g++.dg/ipa/devirt-21.C: New testcase.
> 	* testsuite/g++.dg/ipa/devirt-20.C: Fix template.

...


> Index: ipa-cp.c
> ===================================================================
> --- ipa-cp.c	(revision 207287)
> +++ ipa-cp.c	(working copy)
> @@ -117,6 +117,7 @@ along with GCC; see the file COPYING3.
>  #include "params.h"
>  #include "ipa-inline.h"
>  #include "ipa-utils.h"
> +#include "print-tree.h"
>  
>  struct ipcp_value;
>  
> @@ -1479,9 +1480,9 @@ ipa_get_indirect_edge_target_1 (struct c
>    HOST_WIDE_INT token, anc_offset;
>    tree otr_type;
>    tree t;
> -  tree target;
> +  tree target = NULL;
>  
> -  if (param_index == -1
> +  if (!flag_devirtualize || param_index == -1
>        || known_vals.length () <= (unsigned int) param_index)
>      return NULL_TREE;
>  
> @@ -1532,25 +1533,76 @@ ipa_get_indirect_edge_target_1 (struct c
>    anc_offset = ie->indirect_info->offset;
>    otr_type = ie->indirect_info->otr_type;
>  
> -  t = known_vals[param_index];
> +  t = NULL;
> +
> +  /* Do we know BINFO?  */
>    if (!t && known_binfos.length () > (unsigned int) param_index)
>      t = known_binfos[param_index];
> -  if (!t)
> -    return NULL_TREE;
> +  /* FIXME: ipcp_discover_new_direct_edges makes no difference between
> +     constants and binfos.  This is because ipa-cp currently assumes that known
> +     value is always better than binfo.  Hopefully this will be fixed when
> +     ipa-cp is turned to propagate polymorphic call contextes.  */
> +  if (known_vals[param_index] && TREE_CODE (known_vals[param_index]) == TREE_BINFO)
> +    t = known_vals[param_index];
>  
> -  if (TREE_CODE (t) != TREE_BINFO)
> +  /* Try to work out BINFO from virtual table pointer value in replacements.  */
> +  if (!t && agg_reps && !ie->indirect_info->by_ref)

At this point you know that !ie->indirect_info->polymorphic is set and
thus ie->indirect_info->by_ref is always false because it really has
no meaning (it is only meaningful when agg_contents is set which is
mutually exclusive with the polymorphic flag).

>      {
> -      tree binfo;
> -      binfo = gimple_extract_devirt_binfo_from_cst
> -		 (t, ie->indirect_info->otr_type);
> -      if (!binfo)
> +      while (agg_reps)
> +	{
> +	  if (agg_reps->index == param_index
> +	      && agg_reps->offset == ie->indirect_info->offset
> +	      && agg_reps->by_ref)
> +	    {
> +	      debug_tree (t);
> +	      t = agg_reps->value;
> +	      t = vtable_pointer_value_to_binfo (t);
> +	      break;
> +	    }
> +	  agg_reps = agg_reps->next;
> +	}
> +    }
> +
> +  /* Try to work out BINFO from virtual table pointer value in known
> +     known aggregate values.  */
> +  if (!t && known_aggs.length () > (unsigned int) param_index
> +      && !ie->indirect_info->by_ref)

The same here.

Thanks,

Martin
Jan Hubicka Feb. 4, 2014, 11:47 p.m. UTC | #7 
> > -  if (TREE_CODE (t) != TREE_BINFO)
> > +  /* Try to work out BINFO from virtual table pointer value in replacements.  */
> > +  if (!t && agg_reps && !ie->indirect_info->by_ref)
> 
> At this point you know that !ie->indirect_info->polymorphic is set and
> thus ie->indirect_info->by_ref is always false because it really has
> no meaning (it is only meaningful when agg_contents is set which is
> mutually exclusive with the polymorphic flag).

I was worried here about case where in future we may want to represent call of
virtual methods from pointers passed by reference (i.e. in some other object).
We don't do that at the moment, but for that would really need better jump
functions.

If you preffer, I can remove that check.

Honza
> 
> >      {
> > -      tree binfo;
> > -      binfo = gimple_extract_devirt_binfo_from_cst
> > -		 (t, ie->indirect_info->otr_type);
> > -      if (!binfo)
> > +      while (agg_reps)
> > +	{
> > +	  if (agg_reps->index == param_index
> > +	      && agg_reps->offset == ie->indirect_info->offset
> > +	      && agg_reps->by_ref)
> > +	    {
> > +	      debug_tree (t);
> > +	      t = agg_reps->value;
> > +	      t = vtable_pointer_value_to_binfo (t);
> > +	      break;
> > +	    }
> > +	  agg_reps = agg_reps->next;
> > +	}
> > +    }
> > +
> > +  /* Try to work out BINFO from virtual table pointer value in known
> > +     known aggregate values.  */
> > +  if (!t && known_aggs.length () > (unsigned int) param_index
> > +      && !ie->indirect_info->by_ref)
> 
> The same here.
> 
> Thanks,
> 
> Martin
Martin Jambor Feb. 5, 2014, 10:26 a.m. UTC | #8 
Hi,

On Wed, Feb 05, 2014 at 12:47:30AM +0100, Jan Hubicka wrote:
> > > -  if (TREE_CODE (t) != TREE_BINFO)
> > > +  /* Try to work out BINFO from virtual table pointer value in replacements.  */
> > > +  if (!t && agg_reps && !ie->indirect_info->by_ref)
> > 
> > At this point you know that !ie->indirect_info->polymorphic is set and
> > thus ie->indirect_info->by_ref is always false because it really has
> > no meaning (it is only meaningful when agg_contents is set which is
> > mutually exclusive with the polymorphic flag).
> 
> I was worried here about case where in future we may want to represent call of
> virtual methods from pointers passed by reference (i.e. in some other object).
> We don't do that at the moment, but for that would really need better jump
> functions.
> 
> If you preffer, I can remove that check.
> 

I think it would be better, yes.  IIRC, We want to re-organize
indirect_info anyway (I vaguely remember we want to split the
overloaded offset field into two but forgot the exact reason why but I
have it written somewhere), I suppose we'll be turning it into a union
(or class hierarchy?) and this would make it slightly awkward.  If we
ever support the pointer-by-reference scenario, quite a few more
places will need to be adjusted anyway.

Thanks,

Martin
Jan Hubicka Feb. 5, 2014, 3:27 p.m. UTC | #9 
> > 
> 
> I think it would be better, yes.  IIRC, We want to re-organize
> indirect_info anyway (I vaguely remember we want to split the
> overloaded offset field into two but forgot the exact reason why but I
> have it written somewhere), I suppose we'll be turning it into a union
> (or class hierarchy?) and this would make it slightly awkward.  If we
> ever support the pointer-by-reference scenario, quite a few more
> places will need to be adjusted anyway.

OK, I will remove the check. I wanted to split polymorphic call context
and its propagation from aggregate analysis.  For example

struct A
{
  struct B b;
  struct C c;
}

when you call method of A.c.foo() its context is not
{outer_type=a,offset=offsetof(c)}, since A is not polymorphic type at all. We
should instead use {outer_type=c,offset=0,not_derived_type}.  In
ipa-devirt there is function get_class_context that gets you from first to
second.

So as briefly discussed last july, I think ipa-prop can simply do two
propagations in parallel where the type one is done via functionality that
willbe exported from ipa-devirt, since the logic should be shared with
a local devirt pass.

There are also cases where the parameter is KNOWN_TYPE but also PASS_THROUGH at
the same type (as tings passed by invisible refernece, or when the function is
constructor and it initialized dynamic type of THIS pointer).

Those are cases where current code is losing information because one is not
supperset of the other.  We want to use KNOWN_TYPE information for devirtualization,
but we do not want to forget about PASS_THROUGH for normal constant propagation in
case constructor is only called on &decl.

Honza
> 
> Thanks,
> 
> Martin
diff mbox

Patch

Index: gimple-fold.c
===================================================================
--- gimple-fold.c	(revision 207287)
+++ gimple-fold.c	(working copy)
@@ -1071,74 +1071,6 @@  gimple_fold_builtin (gimple stmt)
 }
 
 
-/* Return a binfo to be used for devirtualization of calls based on an object
-   represented by a declaration (i.e. a global or automatically allocated one)
-   or NULL if it cannot be found or is not safe.  CST is expected to be an
-   ADDR_EXPR of such object or the function will return NULL.  Currently it is
-   safe to use such binfo only if it has no base binfo (i.e. no ancestors)
-   EXPECTED_TYPE is type of the class virtual belongs to.  */
-
-tree
-gimple_extract_devirt_binfo_from_cst (tree cst, tree expected_type)
-{
-  HOST_WIDE_INT offset, size, max_size;
-  tree base, type, binfo;
-  bool last_artificial = false;
-
-  if (!flag_devirtualize
-      || TREE_CODE (cst) != ADDR_EXPR
-      || TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) != RECORD_TYPE)
-    return NULL_TREE;
-
-  cst = TREE_OPERAND (cst, 0);
-  base = get_ref_base_and_extent (cst, &offset, &size, &max_size);
-  type = TREE_TYPE (base);
-  if (!DECL_P (base)
-      || max_size == -1
-      || max_size != size
-      || TREE_CODE (type) != RECORD_TYPE)
-    return NULL_TREE;
-
-  /* Find the sub-object the constant actually refers to and mark whether it is
-     an artificial one (as opposed to a user-defined one).  */
-  while (true)
-    {
-      HOST_WIDE_INT pos, size;
-      tree fld;
-
-      if (types_same_for_odr (type, expected_type))
-	break;
-      if (offset < 0)
-	return NULL_TREE;
-
-      for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
-	{
-	  if (TREE_CODE (fld) != FIELD_DECL)
-	    continue;
-
-	  pos = int_bit_position (fld);
-	  size = tree_to_uhwi (DECL_SIZE (fld));
-	  if (pos <= offset && (pos + size) > offset)
-	    break;
-	}
-      if (!fld || TREE_CODE (TREE_TYPE (fld)) != RECORD_TYPE)
-	return NULL_TREE;
-
-      last_artificial = DECL_ARTIFICIAL (fld);
-      type = TREE_TYPE (fld);
-      offset -= pos;
-    }
-  /* Artificial sub-objects are ancestors, we do not want to use them for
-     devirtualization, at least not here.  */
-  if (last_artificial)
-    return NULL_TREE;
-  binfo = TYPE_BINFO (type);
-  if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
-    return NULL_TREE;
-  else
-    return binfo;
-}
-
 /* Attempt to fold a call statement referenced by the statement iterator GSI.
    The statement may be replaced by another statement, e.g., if the call
    simplifies to a constant value. Return true if any changes were made.
Index: gimple-fold.h
===================================================================
--- gimple-fold.h	(revision 207287)
+++ gimple-fold.h	(working copy)
@@ -26,7 +26,6 @@  extern tree canonicalize_constructor_val
 extern tree get_symbol_constant_value (tree);
 extern void gimplify_and_update_call_from_tree (gimple_stmt_iterator *, tree);
 extern tree gimple_fold_builtin (gimple);
-extern tree gimple_extract_devirt_binfo_from_cst (tree, tree);
 extern bool fold_stmt (gimple_stmt_iterator *);
 extern bool fold_stmt_inplace (gimple_stmt_iterator *);
 extern tree maybe_fold_and_comparisons (enum tree_code, tree, tree, 
Index: ipa-utils.h
===================================================================
--- ipa-utils.h	(revision 207287)
+++ ipa-utils.h	(working copy)
@@ -87,6 +87,9 @@  tree method_class_type (tree);
 tree get_polymorphic_call_info (tree, tree, tree *,
 				HOST_WIDE_INT *,
 				ipa_polymorphic_call_context *);
+bool get_polymorphic_call_info_from_invariant (ipa_polymorphic_call_context *,
+					       tree, tree, HOST_WIDE_INT);
+tree vtable_pointer_value_to_binfo (tree t);
 
 /* Return vector containing possible targets of polymorphic call E.
    If FINALP is non-NULL, store true if the list is complette. 
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c	(revision 207287)
+++ ipa-devirt.c	(working copy)
@@ -972,6 +972,120 @@  contains_type_p (tree outer_type, HOST_W
   return get_class_context (&context, otr_type);
 }
 
+/* Proudce polymorphic call context for call method of instance
+   that is located within BASE (that is assumed to be a decl) at OFFSET. */
+
+static void
+get_poymorphic_call_info_for_decl (ipa_polymorphic_call_context *context,
+				   tree base, HOST_WIDE_INT offset)
+{
+  gcc_assert (DECL_P (base));
+
+  context->outer_type = TREE_TYPE (base);
+  context->offset = offset;
+  /* Make very conservative assumption that all objects
+     may be in construction. 
+     TODO: ipa-prop already contains code to tell better. 
+     merge it later.  */
+  context->maybe_in_construction = true;
+  context->maybe_derived_type = false;
+}
+
+/* CST is an invariant (address of decl), try to get meaningful
+   polymorphic call context for polymorphic call of method 
+   if instance of OTR_TYPE that is located at OFFSET of this invariant.
+   Return FALSE if nothing meaningful can be found.  */
+
+bool
+get_polymorphic_call_info_from_invariant (ipa_polymorphic_call_context *context,
+				          tree cst,
+				          tree otr_type,
+				          HOST_WIDE_INT offset)
+{
+  HOST_WIDE_INT offset2, size, max_size;
+  tree base;
+
+  if (TREE_CODE (cst) != ADDR_EXPR)
+    return NULL_TREE;
+
+  cst = TREE_OPERAND (cst, 0);
+  base = get_ref_base_and_extent (cst, &offset2, &size, &max_size);
+  if (!DECL_P (base)
+      || max_size == -1
+      || max_size != size)
+    return NULL_TREE;
+
+  /* Only type inconsistent programs can have otr_type that is
+     not part of outer type.  */
+  if (!contains_type_p (TREE_TYPE (base),
+			offset, otr_type))
+    return NULL_TREE;
+
+  get_poymorphic_call_info_for_decl (context,
+				     base, offset);
+  return true;
+}
+
+/* Lookup base of BINFO that has virtual table VTABLE with OFFSET.  */
+
+static tree
+subbinfo_with_vtable_at_offset (tree binfo, tree offset, tree vtable)
+{
+  tree v = BINFO_VTABLE (binfo);
+  int i;
+  tree base_binfo;
+
+  gcc_assert (!v || TREE_CODE (v) == POINTER_PLUS_EXPR);
+  
+  if (v && tree_int_cst_equal (TREE_OPERAND (v, 1), offset)
+      && TREE_OPERAND (TREE_OPERAND (v, 0), 0) == vtable)
+    return binfo;
+  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
+    if (polymorphic_type_binfo_p (base_binfo))
+      {
+	base_binfo = subbinfo_with_vtable_at_offset (base_binfo, offset, vtable);
+	if (base_binfo)
+	  return base_binfo;
+      }
+  return NULL;
+}
+
+/* T is known constant value of virtual table pointer.  Return BINFO of the
+   instance type.  */
+
+tree
+vtable_pointer_value_to_binfo (tree t)
+{
+  /* We expect &MEM[(void *)&virtual_table + 16B].
+     We obtain object's BINFO from the context of the virtual table. 
+     This one contains pointer to virtual table represented via
+     POINTER_PLUS_EXPR.  Verify that this pointer match to what
+     we propagated through.
+
+     In the case of virtual inheritance, the virtual tables may
+     be nested, i.e. the offset may be different from 16 and we may
+     need to dive into the type representation.  */
+  if (t && TREE_CODE (t) == ADDR_EXPR
+      && TREE_CODE (TREE_OPERAND (t, 0)) == MEM_REF
+      && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == ADDR_EXPR
+      && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST
+      && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0))
+	  == VAR_DECL)
+      && DECL_VIRTUAL_P (TREE_OPERAND (TREE_OPERAND
+					 (TREE_OPERAND (t, 0), 0), 0)))
+    {
+      tree vtable = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0);
+      tree offset = TREE_OPERAND (TREE_OPERAND (t, 0), 1);
+      tree binfo = TYPE_BINFO (DECL_CONTEXT (vtable));
+
+      binfo = subbinfo_with_vtable_at_offset (binfo, offset, vtable);
+      gcc_assert (binfo);
+      return binfo;
+    }
+  return NULL;
+}
+
+
 /* Given REF call in FNDECL, determine class of the polymorphic
    call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT.
    Return pointer to object described by the context  */
@@ -1030,21 +1144,13 @@  get_polymorphic_call_info (tree fndecl,
 		 is known.  */
 	      else if (DECL_P (base))
 		{
-		  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (base)));
-
 		  /* Only type inconsistent programs can have otr_type that is
 		     not part of outer type.  */
 		  if (!contains_type_p (TREE_TYPE (base),
 					context->offset + offset2, *otr_type))
 		    return base_pointer;
-		  context->outer_type = TREE_TYPE (base);
-		  context->offset += offset2;
-		  /* Make very conservative assumption that all objects
-		     may be in construction. 
-		     TODO: ipa-prop already contains code to tell better. 
-		     merge it later.  */
-		  context->maybe_in_construction = true;
-		  context->maybe_derived_type = false;
+		  get_poymorphic_call_info_for_decl (context, base,
+						     context->offset + offset2);
 		  return NULL;
 		}
 	      else
Index: ipa-prop.c
===================================================================
--- ipa-prop.c	(revision 207287)
+++ ipa-prop.c	(working copy)
@@ -592,6 +592,7 @@  extr_type_from_vtbl_ptr_store (gimple st
 {
   HOST_WIDE_INT offset, size, max_size;
   tree lhs, rhs, base;
+  tree binfo;
 
   if (!gimple_assign_single_p (stmt))
     return NULL_TREE;
@@ -602,10 +603,12 @@  extr_type_from_vtbl_ptr_store (gimple st
       || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
       || TREE_CODE (rhs) != ADDR_EXPR)
     return NULL_TREE;
-  rhs = get_base_address (TREE_OPERAND (rhs, 0));
-  if (!rhs
-      || TREE_CODE (rhs) != VAR_DECL
-      || !DECL_VIRTUAL_P (rhs))
+  binfo = vtable_pointer_value_to_binfo (rhs);
+
+  /* FIXME: We may end up looking up an binfo that is not
+     a base type, since the instance is part of a bigger one.
+     We should handle this in future by working out proper offset.  */
+  if (!binfo || TYPE_BINFO (BINFO_TYPE (binfo)) != binfo)
     return NULL_TREE;
 
   base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
@@ -624,7 +627,7 @@  extr_type_from_vtbl_ptr_store (gimple st
   else if (tci->object != base)
     return NULL_TREE;
 
-  return DECL_CONTEXT (rhs);
+  return BINFO_TYPE (binfo);
 }
 
 /* Callback of walk_aliased_vdefs and a helper function for
@@ -2670,28 +2673,58 @@  try_make_edge_direct_virtual_call (struc
 				   struct ipa_jump_func *jfunc,
 				   struct ipa_node_params *new_root_info)
 {
-  tree binfo, target;
+  tree binfo = NULL, target;
+
+  if (!flag_devirtualize)
+    return NULL;
 
-  binfo = ipa_value_from_jfunc (new_root_info, jfunc);
+  /* First try to work out binfo from the knowledge of virtual
+     table pointer.  This is always safe.  */
+  if (!ie->indirect_info->by_ref)
+    {
+      tree t = ipa_find_agg_cst_for_param (&jfunc->agg,
+					   ie->indirect_info->offset,
+					   true);
+      binfo = vtable_pointer_value_to_binfo (t);
+    }
 
+  /* See if we propagated value or binfo.  */
+  if (!binfo)
+    binfo = ipa_value_from_jfunc (new_root_info, jfunc);
   if (!binfo)
     return NULL;
 
   if (TREE_CODE (binfo) != TREE_BINFO)
     {
-      binfo = gimple_extract_devirt_binfo_from_cst
-		 (binfo, ie->indirect_info->otr_type);
-      if (!binfo)
-        return NULL;
+      ipa_polymorphic_call_context context;
+      vec <cgraph_node *>targets;
+      bool final;
+
+      if (!get_polymorphic_call_info_from_invariant
+	     (&context, binfo, ie->indirect_info->otr_type,
+	      ie->indirect_info->offset))
+	return NULL;
+      targets = possible_polymorphic_call_targets
+		 (ie->indirect_info->otr_type,
+		  ie->indirect_info->otr_token,
+		  context, &final);
+      if (!final || targets.length () > 1)
+	return NULL;
+      if (targets.length () == 1)
+	target = targets[0]->decl;
+      else
+        target = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
     }
-
-  binfo = get_binfo_at_offset (binfo, ie->indirect_info->offset,
-			       ie->indirect_info->otr_type);
-  if (binfo)
-    target = gimple_get_virt_method_for_binfo (ie->indirect_info->otr_token,
-					       binfo);
   else
-    return NULL;
+    {
+      binfo = get_binfo_at_offset (binfo, ie->indirect_info->offset,
+				   ie->indirect_info->otr_type);
+      if (binfo)
+	target = gimple_get_virt_method_for_binfo (ie->indirect_info->otr_token,
+						   binfo);
+      else
+	return NULL;
+    }
 
   if (target)
     {
Index: ipa-cp.c
===================================================================
--- ipa-cp.c	(revision 207287)
+++ ipa-cp.c	(working copy)
@@ -117,6 +117,7 @@  along with GCC; see the file COPYING3.
 #include "params.h"
 #include "ipa-inline.h"
 #include "ipa-utils.h"
+#include "print-tree.h"
 
 struct ipcp_value;
 
@@ -1479,9 +1480,9 @@  ipa_get_indirect_edge_target_1 (struct c
   HOST_WIDE_INT token, anc_offset;
   tree otr_type;
   tree t;
-  tree target;
+  tree target = NULL;
 
-  if (param_index == -1
+  if (!flag_devirtualize || param_index == -1
       || known_vals.length () <= (unsigned int) param_index)
     return NULL_TREE;
 
@@ -1532,25 +1533,76 @@  ipa_get_indirect_edge_target_1 (struct c
   anc_offset = ie->indirect_info->offset;
   otr_type = ie->indirect_info->otr_type;
 
-  t = known_vals[param_index];
+  t = NULL;
+
+  /* Do we know BINFO?  */
   if (!t && known_binfos.length () > (unsigned int) param_index)
     t = known_binfos[param_index];
-  if (!t)
-    return NULL_TREE;
+  /* FIXME: ipcp_discover_new_direct_edges makes no difference between
+     constants and binfos.  This is because ipa-cp currently assumes that known
+     value is always better than binfo.  Hopefully this will be fixed when
+     ipa-cp is turned to propagate polymorphic call contextes.  */
+  if (known_vals[param_index] && TREE_CODE (known_vals[param_index]) == TREE_BINFO)
+    t = known_vals[param_index];
 
-  if (TREE_CODE (t) != TREE_BINFO)
+  /* Try to work out BINFO from virtual table pointer value in replacements.  */
+  if (!t && agg_reps && !ie->indirect_info->by_ref)
     {
-      tree binfo;
-      binfo = gimple_extract_devirt_binfo_from_cst
-		 (t, ie->indirect_info->otr_type);
-      if (!binfo)
+      while (agg_reps)
+	{
+	  if (agg_reps->index == param_index
+	      && agg_reps->offset == ie->indirect_info->offset
+	      && agg_reps->by_ref)
+	    {
+	      debug_tree (t);
+	      t = agg_reps->value;
+	      t = vtable_pointer_value_to_binfo (t);
+	      break;
+	    }
+	  agg_reps = agg_reps->next;
+	}
+    }
+
+  /* Try to work out BINFO from virtual table pointer value in known
+     known aggregate values.  */
+  if (!t && known_aggs.length () > (unsigned int) param_index
+      && !ie->indirect_info->by_ref)
+    {
+       struct ipa_agg_jump_function *agg;
+       agg = known_aggs[param_index];
+       t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
+				       true);
+       if (t)
+	 t = vtable_pointer_value_to_binfo (t);
+    }
+
+  /* Try to work out value of the pointer.  This comes last since not all
+     values leads to devirtualization.  */
+  if (!t)
+    {
+      ipa_polymorphic_call_context context;
+      vec <cgraph_node *>targets;
+      bool final;
+
+      t = known_vals[param_index];
+      if (!t)
+	return NULL_TREE;
+
+      if (!get_polymorphic_call_info_from_invariant
+	     (&context, t, ie->indirect_info->otr_type,
+	      anc_offset))
 	return NULL_TREE;
-      binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
-      if (!binfo)
+      targets = possible_polymorphic_call_targets
+		 (ie->indirect_info->otr_type,
+		  ie->indirect_info->otr_token,
+		  context, &final);
+      if (!final || targets.length () > 1)
 	return NULL_TREE;
-      target = gimple_get_virt_method_for_binfo (token, binfo);
+      if (targets.length () == 1)
+	return targets[0]->decl;
+      return builtin_decl_implicit (BUILT_IN_UNREACHABLE);
     }
-  else
+  if (t)
     {
       tree binfo;