[4/4] Devirtualization based on global objects

Hi,

this is the patch that actually speeds up astar (together with the
previous one).  It implements devirtualization based on global
objects.  In the past we have refrained from doing this because in
general it is difficult to say whether the object is currently being
constructed and so it might have a dynamic type of one of its
ancestors.  However, if the object's class does not have any ancestors
that obviously cannot happen.

Devirtualizing in such conditions is enough to change a virtual call
to regwayobj::isaddtobound in 473.astar to a direct one which can and
should be inlined.  That seemed a good justification to implement this
and so the patch below does so and brings about 3.1% speedup for that
benchmark with LTO.

I acknowledge that instead of discarding all classes with ancestors it
would be better to check that the called virtual method has the same
implementation in all ancestors instead.  That is perhaps something
for later.

It took me surprisingly long to realize that this technique can be
used for folding virtual calls based on local automatically allocated
objexts too and so can be used to un-XFAIL g++.dg/opt/devirt1.c that
regressed in 4.6.

Bootstrapped and tested on x86_64-linux.  OK for trunk?

Thanks,

Martin


2011-04-15  Martin Jambor  <mjambor@suse.cz>

	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Devirtualize
	also according to actual contants.
	* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): New function.
	(gimple_fold_obj_type_ref_call): New function.
	(gimple_fold_call): Call gimple_fold_obj_type_ref_call on
	OBJ_TYPE_REFs.
	* gimple.h (gimple_extract_devirt_binfo_from_cst): Declare.

	* testsuite/g++.dg/opt/devirt1.C: Bump to -O2, remove XFAIL.
	* testsuite/g++.dg/opt/devirt2.C: New test.
	* testsuite/g++.dg/ipa/devirt-g-1.C: Likewise.

On Fri, 15 Apr 2011, Martin Jambor wrote:

> Hi,
> 
> this is the patch that actually speeds up astar (together with the
> previous one).  It implements devirtualization based on global
> objects.  In the past we have refrained from doing this because in
> general it is difficult to say whether the object is currently being
> constructed and so it might have a dynamic type of one of its
> ancestors.  However, if the object's class does not have any ancestors
> that obviously cannot happen.
> 
> Devirtualizing in such conditions is enough to change a virtual call
> to regwayobj::isaddtobound in 473.astar to a direct one which can and
> should be inlined.  That seemed a good justification to implement this
> and so the patch below does so and brings about 3.1% speedup for that
> benchmark with LTO.
> 
> I acknowledge that instead of discarding all classes with ancestors it
> would be better to check that the called virtual method has the same
> implementation in all ancestors instead.  That is perhaps something
> for later.
> 
> It took me surprisingly long to realize that this technique can be
> used for folding virtual calls based on local automatically allocated
> objexts too and so can be used to un-XFAIL g++.dg/opt/devirt1.c that
> regressed in 4.6.
> 
> Bootstrapped and tested on x86_64-linux.  OK for trunk?
> 
> Thanks,
> 
> Martin
> 
> 
> 2011-04-15  Martin Jambor  <mjambor@suse.cz>
> 
> 	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Devirtualize
> 	also according to actual contants.
> 	* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): New function.
> 	(gimple_fold_obj_type_ref_call): New function.
> 	(gimple_fold_call): Call gimple_fold_obj_type_ref_call on
> 	OBJ_TYPE_REFs.
> 	* gimple.h (gimple_extract_devirt_binfo_from_cst): Declare.
> 
> 	* testsuite/g++.dg/opt/devirt1.C: Bump to -O2, remove XFAIL.
> 	* testsuite/g++.dg/opt/devirt2.C: New test.
> 	* testsuite/g++.dg/ipa/devirt-g-1.C: Likewise.
> 
> 
> Index: src/gcc/ipa-cp.c
> ===================================================================
> --- src.orig/gcc/ipa-cp.c
> +++ src/gcc/ipa-cp.c
> @@ -1245,51 +1245,71 @@ ipcp_process_devirtualization_opportunit
>  
>    for (ie = node->indirect_calls; ie; ie = next_ie)
>      {
> -      int param_index, types_count, j;
> +      int param_index;
>        HOST_WIDE_INT token, anc_offset;
>        tree target, delta, otr_type;
> +      struct ipcp_lattice *lat;
>  
>        next_ie = ie->next_callee;
>        if (!ie->indirect_info->polymorphic)
>  	continue;
>        param_index = ie->indirect_info->param_index;
> -      if (param_index == -1
> -	  || ipa_param_cannot_devirtualize_p (info, param_index)
> -	  || ipa_param_types_vec_empty (info, param_index))
> +      if (param_index == -1)
>  	continue;
>  
> +      lat = ipcp_get_lattice (info, param_index);
>        token = ie->indirect_info->otr_token;
>        anc_offset = ie->indirect_info->anc_offset;
>        otr_type = ie->indirect_info->otr_type;
>        target = NULL_TREE;
> -      types_count = VEC_length (tree, info->params[param_index].types);
> -      for (j = 0; j < types_count; j++)
> +      if (lat->type == IPA_CONST_VALUE)
>  	{
> -	  tree binfo = VEC_index (tree, info->params[param_index].types, j);
> -	  tree d, t;
> -
> +	  tree binfo = gimple_extract_devirt_binfo_from_cst (lat->constant);
> +	  if (!binfo)
> +	    continue;
>  	  binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
>  	  if (!binfo)
> -	    {
> -	      target = NULL_TREE;
> -	      break;
> -	    }
> +	    continue;
> +	  target = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta,
> +						     false);
> +	}
> +      else
> +	{
> +	  int  types_count, j;
>  
> -	  t = gimple_get_virt_mehtod_for_binfo (token, binfo, &d, true);
> -	  if (!t)
> -	    {
> -	      target = NULL_TREE;
> -	      break;
> -	    }
> -	  else if (!target)
> -	    {
> -	      target = t;
> -	      delta = d;
> -	    }
> -	  else if (target != t || !tree_int_cst_equal (delta, d))
> +	  if (ipa_param_cannot_devirtualize_p (info, param_index)
> +	      || ipa_param_types_vec_empty (info, param_index))
> +	    continue;
> +
> +	  types_count = VEC_length (tree, info->params[param_index].types);
> +	  for (j = 0; j < types_count; j++)
>  	    {
> -	      target = NULL_TREE;
> -	      break;
> +	      tree binfo = VEC_index (tree, info->params[param_index].types, j);
> +	      tree d, t;
> +
> +	      binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
> +	      if (!binfo)
> +		{
> +		  target = NULL_TREE;
> +		  break;
> +		}
> +
> +	      t = gimple_get_virt_mehtod_for_binfo (token, binfo, &d, true);
> +	      if (!t)
> +		{
> +		  target = NULL_TREE;
> +		  break;
> +		}
> +	      else if (!target)
> +		{
> +		  target = t;
> +		  delta = d;
> +		}
> +	      else if (target != t || !tree_int_cst_equal (delta, d))
> +		{
> +		  target = NULL_TREE;
> +		  break;
> +		}
>  	    }
>  	}
>  
> Index: src/gcc/gimple-fold.c
> ===================================================================
> --- src.orig/gcc/gimple-fold.c
> +++ src/gcc/gimple-fold.c
> @@ -1438,6 +1438,95 @@ gimple_adjust_this_by_delta (gimple_stmt
>    gimple_call_set_arg (call_stmt, 0, tmp);
>  }
>  
> +/* 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).  */
> +
> +tree
> +gimple_extract_devirt_binfo_from_cst (tree cst)
> +{
> +  HOST_WIDE_INT offset, size, max_size;
> +  tree base, type, expected_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);
> +  expected_type = TREE_TYPE (cst);
> +  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;
> +
> +  while (true)
> +    {
> +      HOST_WIDE_INT pos, size;
> +      tree fld;
> +
> +      if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (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_low_cst (DECL_SIZE (fld), 1);
> +	  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;
> +    }

Please add come comments on what this loop does.  It looks like
it searches for the FIELD_DECL that corresponds to the incoming
constant address (but it doesn't have to exactly point to its
beginning?).  Note that you miss to handle the case where the
declaration is view-converted to a different type and you
instead use the declared type.  Which ISTR was correct as
placement new on decls is kind of invalid.

> +  if (last_artificial)
> +    return NULL_TREE;
> +  binfo = TYPE_BINFO (type);
> +  if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
> +    return NULL_TREE;
> +  else
> +    return binfo;
> +}
> +
> +/* Fold a call statement to OBJ_TYPE_REF to a direct call if possible.  Return
> +   true iff the statement was changed.  GSI determines the statement.  */
> +
> +static bool
> +gimple_fold_obj_type_ref_call (gimple_stmt_iterator *gsi)
> +{
> +  gimple stmt = gsi_stmt (*gsi);
> +  tree ref = gimple_call_fn (stmt);
> +  tree binfo, fndecl, delta;
> +  HOST_WIDE_INT token;
> +
> +  binfo = gimple_extract_devirt_binfo_from_cst (OBJ_TYPE_REF_OBJECT (ref));
> +  if (!binfo)
> +    return false;
> +
> +  token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);

Either use TREE_INT_CST_LOW or first check with host_integerp.

Ok with that change.

Thanks,
Richard.

> +  fndecl = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta, false);
> +  if (!fndecl)
> +    return false;
> +  gcc_assert (integer_zerop (delta));
> +  gimple_call_set_fndecl (stmt, fndecl);
> +  return true;
> +}
> +
> +
>  /* 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.
> @@ -1463,6 +1552,13 @@ gimple_fold_call (gimple_stmt_iterator *
>  	  return true;
>  	}
>      }
> +  else
> +    {
> +      callee = gimple_call_fn (stmt);
> +      if (TREE_CODE (callee) == OBJ_TYPE_REF)
> +	return gimple_fold_obj_type_ref_call (gsi);
> +    }
> +
>    return false;
>  }
>  
> Index: src/gcc/gimple.h
> ===================================================================
> --- src.orig/gcc/gimple.h
> +++ src/gcc/gimple.h
> @@ -894,6 +894,7 @@ const char *gimple_decl_printable_name (
>  bool gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace);
>  tree gimple_get_virt_mehtod_for_binfo (HOST_WIDE_INT, tree, tree *, bool);
>  void gimple_adjust_this_by_delta (gimple_stmt_iterator *, tree);
> +tree gimple_extract_devirt_binfo_from_cst (tree);
>  /* Returns true iff T is a valid GIMPLE statement.  */
>  extern bool is_gimple_stmt (tree);
>  
> Index: src/gcc/testsuite/g++.dg/opt/devirt2.C
> ===================================================================
> --- /dev/null
> +++ src/gcc/testsuite/g++.dg/opt/devirt2.C
> @@ -0,0 +1,11 @@
> +// { dg-do compile }
> +// { dg-options "-O2" }
> +// { dg-final { scan-assembler-times "xyzzy" 2 } }
> +
> +struct S { S(); virtual void xyzzy(); };
> +struct R { int a; S s; R(); };
> +S s;
> +R r;
> +inline void foo(S *p) { p->xyzzy(); }
> +void bar() {foo(&s);}
> +void bah() {foo(&r.s);}
> Index: src/gcc/testsuite/g++.dg/ipa/devirt-g-1.C
> ===================================================================
> --- /dev/null
> +++ src/gcc/testsuite/g++.dg/ipa/devirt-g-1.C
> @@ -0,0 +1,24 @@
> +// { dg-do compile }
> +// { dg-options "-O2 -fdump-ipa-cp -fdump-tree-optimized" }
> +
> +struct S { S(); virtual void xyzzy(); void otherstuff(); };
> +struct R { int a; S s; R(); };
> +S s;
> +R r;
> +
> +void S::xyzzy ()
> +{
> +  otherstuff ();
> +  otherstuff ();
> +}
> +
> +static void __attribute__ ((noinline)) foo(S *p) { p->xyzzy(); }
> +void bar() {foo(&s); }
> +
> +static void __attribute__ ((noinline)) foh(S *p) { p->xyzzy(); }
> +void bah() {foh(&r.s); }
> +
> +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*S::xyzzy" "cp"  } } */
> +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
> +/* { dg-final { cleanup-ipa-dump "cp" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: src/gcc/testsuite/g++.dg/opt/devirt1.C
> ===================================================================
> --- src.orig/gcc/testsuite/g++.dg/opt/devirt1.C
> +++ src/gcc/testsuite/g++.dg/opt/devirt1.C
> @@ -1,6 +1,6 @@
>  // { dg-do compile }
> -// { dg-options "-O" }
> -// { dg-final { scan-assembler "xyzzy" { xfail *-*-* } } }
> +// { dg-options "-O2" }
> +// { dg-final { scan-assembler "xyzzy" } }
>  
>  struct S { S(); virtual void xyzzy(); };
>  inline void foo(S *s) { s->xyzzy(); }
> 
>

Hi,

On Fri, Apr 15, 2011 at 05:38:50PM +0200, Richard Guenther wrote:
> On Fri, 15 Apr 2011, Martin Jambor wrote:
> 
> > Hi,
> > 
> > this is the patch that actually speeds up astar (together with the
> > previous one).  It implements devirtualization based on global
> > objects.  In the past we have refrained from doing this because in
> > general it is difficult to say whether the object is currently being
> > constructed and so it might have a dynamic type of one of its
> > ancestors.  However, if the object's class does not have any ancestors
> > that obviously cannot happen.
> > 
> > Devirtualizing in such conditions is enough to change a virtual call
> > to regwayobj::isaddtobound in 473.astar to a direct one which can and
> > should be inlined.  That seemed a good justification to implement this
> > and so the patch below does so and brings about 3.1% speedup for that
> > benchmark with LTO.
> > 
> > I acknowledge that instead of discarding all classes with ancestors it
> > would be better to check that the called virtual method has the same
> > implementation in all ancestors instead.  That is perhaps something
> > for later.
> > 
> > It took me surprisingly long to realize that this technique can be
> > used for folding virtual calls based on local automatically allocated
> > objexts too and so can be used to un-XFAIL g++.dg/opt/devirt1.c that
> > regressed in 4.6.
> > 
> > Bootstrapped and tested on x86_64-linux.  OK for trunk?
> > 
> > Thanks,
> > 
> > Martin
> > 
> > 
> > 2011-04-15  Martin Jambor  <mjambor@suse.cz>
> > 
> > 	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Devirtualize
> > 	also according to actual contants.
> > 	* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): New function.
> > 	(gimple_fold_obj_type_ref_call): New function.
> > 	(gimple_fold_call): Call gimple_fold_obj_type_ref_call on
> > 	OBJ_TYPE_REFs.
> > 	* gimple.h (gimple_extract_devirt_binfo_from_cst): Declare.
> > 
> > 	* testsuite/g++.dg/opt/devirt1.C: Bump to -O2, remove XFAIL.
> > 	* testsuite/g++.dg/opt/devirt2.C: New test.
> > 	* testsuite/g++.dg/ipa/devirt-g-1.C: Likewise.
> > 
> > 

...

> > Index: src/gcc/gimple-fold.c
> > ===================================================================
> > --- src.orig/gcc/gimple-fold.c
> > +++ src/gcc/gimple-fold.c
> > @@ -1438,6 +1438,95 @@ gimple_adjust_this_by_delta (gimple_stmt
> >    gimple_call_set_arg (call_stmt, 0, tmp);
> >  }
> >  
> > +/* 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).  */
> > +
> > +tree
> > +gimple_extract_devirt_binfo_from_cst (tree cst)
> > +{
> > +  HOST_WIDE_INT offset, size, max_size;
> > +  tree base, type, expected_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);
> > +  expected_type = TREE_TYPE (cst);
> > +  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;
> > +
> > +  while (true)
> > +    {
> > +      HOST_WIDE_INT pos, size;
> > +      tree fld;
> > +
> > +      if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (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_low_cst (DECL_SIZE (fld), 1);
> > +	  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;
> > +    }
> 
> Please add come comments on what this loop does.  It looks like
> it searches for the FIELD_DECL that corresponds to the incoming
> constant address (but it doesn't have to exactly point to its
> beginning?). 

Yes, an object can be within another.  Like S within R in the added
testcase g++/opt/devirt2.C.  Then it checks it is not a representative
of an ancestor but a user-defined object by looking at DECL_ARTIFICIAL.

> Note that you miss to handle the case where the
> declaration is view-converted to a different type and you
> instead use the declared type.  Which ISTR was correct as
> placement new on decls is kind of invalid.

Yes, I know I'm assuming that.

> 
> > +  if (last_artificial)
> > +    return NULL_TREE;
> > +  binfo = TYPE_BINFO (type);
> > +  if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
> > +    return NULL_TREE;
> > +  else
> > +    return binfo;
> > +}
> > +
> > +/* Fold a call statement to OBJ_TYPE_REF to a direct call if possible.  Return
> > +   true iff the statement was changed.  GSI determines the statement.  */
> > +
> > +static bool
> > +gimple_fold_obj_type_ref_call (gimple_stmt_iterator *gsi)
> > +{
> > +  gimple stmt = gsi_stmt (*gsi);
> > +  tree ref = gimple_call_fn (stmt);
> > +  tree binfo, fndecl, delta;
> > +  HOST_WIDE_INT token;
> > +
> > +  binfo = gimple_extract_devirt_binfo_from_cst (OBJ_TYPE_REF_OBJECT (ref));
> > +  if (!binfo)
> > +    return false;
> > +
> > +  token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
> 
> Either use TREE_INT_CST_LOW or first check with host_integerp.
> 
> Ok with that change.
> 

OK.

Unfortunately I have conflicted with your patch folding OBJ_TYPE_REFs
and since you did not introduce a special function for OBJ_TYPE_REFs,
I kept the functionality within gimple_fold_call too.

So this is what I am testing and what I intend to commit if all goes
well.

Thanks a lot,

Martin


2011-04-18  Martin Jambor  <mjambor@suse.cz>

	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Devirtualize
	also according to actual contants.
	* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): New function.
	(gimple_fold_call): Use it.
	* gimple.h (gimple_extract_devirt_binfo_from_cst): Declare.

	* testsuite/g++.dg/opt/devirt1.C: Bump to -O2, remove XFAIL.
	* testsuite/g++.dg/opt/devirt2.C: New test.
	* testsuite/g++.dg/ipa/devirt-g-1.C: Likewise.

Index: src/gcc/ipa-cp.c
===================================================================
*** src.orig/gcc/ipa-cp.c
--- src/gcc/ipa-cp.c
*************** ipcp_process_devirtualization_opportunit
*** 1246,1296 ****
  
    for (ie = node->indirect_calls; ie; ie = next_ie)
      {
!       int param_index, types_count, j;
        HOST_WIDE_INT token, anc_offset;
        tree target, delta, otr_type;
  
        next_ie = ie->next_callee;
        if (!ie->indirect_info->polymorphic)
  	continue;
        param_index = ie->indirect_info->param_index;
!       if (param_index == -1
! 	  || ipa_param_cannot_devirtualize_p (info, param_index)
! 	  || ipa_param_types_vec_empty (info, param_index))
  	continue;
  
        token = ie->indirect_info->otr_token;
        anc_offset = ie->indirect_info->anc_offset;
        otr_type = ie->indirect_info->otr_type;
        target = NULL_TREE;
!       types_count = VEC_length (tree, info->params[param_index].types);
!       for (j = 0; j < types_count; j++)
  	{
! 	  tree binfo = VEC_index (tree, info->params[param_index].types, j);
! 	  tree d, t;
! 
  	  binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
  	  if (!binfo)
! 	    {
! 	      target = NULL_TREE;
! 	      break;
! 	    }
  
! 	  t = gimple_get_virt_mehtod_for_binfo (token, binfo, &d, true);
! 	  if (!t)
! 	    {
! 	      target = NULL_TREE;
! 	      break;
! 	    }
! 	  else if (!target)
! 	    {
! 	      target = t;
! 	      delta = d;
! 	    }
! 	  else if (target != t || !tree_int_cst_equal (delta, d))
  	    {
! 	      target = NULL_TREE;
! 	      break;
  	    }
  	}
  
--- 1246,1316 ----
  
    for (ie = node->indirect_calls; ie; ie = next_ie)
      {
!       int param_index;
        HOST_WIDE_INT token, anc_offset;
        tree target, delta, otr_type;
+       struct ipcp_lattice *lat;
  
        next_ie = ie->next_callee;
        if (!ie->indirect_info->polymorphic)
  	continue;
        param_index = ie->indirect_info->param_index;
!       if (param_index == -1)
  	continue;
  
+       lat = ipcp_get_lattice (info, param_index);
        token = ie->indirect_info->otr_token;
        anc_offset = ie->indirect_info->anc_offset;
        otr_type = ie->indirect_info->otr_type;
        target = NULL_TREE;
!       if (lat->type == IPA_CONST_VALUE)
  	{
! 	  tree binfo = gimple_extract_devirt_binfo_from_cst (lat->constant);
! 	  if (!binfo)
! 	    continue;
  	  binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
  	  if (!binfo)
! 	    continue;
! 	  target = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta,
! 						     false);
! 	}
!       else
! 	{
! 	  int  types_count, j;
  
! 	  if (ipa_param_cannot_devirtualize_p (info, param_index)
! 	      || ipa_param_types_vec_empty (info, param_index))
! 	    continue;
! 
! 	  types_count = VEC_length (tree, info->params[param_index].types);
! 	  for (j = 0; j < types_count; j++)
  	    {
! 	      tree binfo = VEC_index (tree, info->params[param_index].types, j);
! 	      tree d, t;
! 
! 	      binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
! 	      if (!binfo)
! 		{
! 		  target = NULL_TREE;
! 		  break;
! 		}
! 
! 	      t = gimple_get_virt_mehtod_for_binfo (token, binfo, &d, true);
! 	      if (!t)
! 		{
! 		  target = NULL_TREE;
! 		  break;
! 		}
! 	      else if (!target)
! 		{
! 		  target = t;
! 		  delta = d;
! 		}
! 	      else if (target != t || !tree_int_cst_equal (delta, d))
! 		{
! 		  target = NULL_TREE;
! 		  break;
! 		}
  	    }
  	}
  
Index: src/gcc/gimple-fold.c
===================================================================
*** src.orig/gcc/gimple-fold.c
--- src/gcc/gimple-fold.c
*************** gimple_adjust_this_by_delta (gimple_stmt
*** 1441,1446 ****
--- 1441,1514 ----
    gimple_call_set_arg (call_stmt, 0, tmp);
  }
  
+ /* 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).  */
+ 
+ tree
+ gimple_extract_devirt_binfo_from_cst (tree cst)
+ {
+   HOST_WIDE_INT offset, size, max_size;
+   tree base, type, expected_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);
+   expected_type = TREE_TYPE (cst);
+   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 (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (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_low_cst (DECL_SIZE (fld), 1);
+ 	  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;
+     }
+   /* Artifical 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.
*************** gimple_fold_call (gimple_stmt_iterator *
*** 1469,1478 ****
  
    /* Check for virtual calls that became direct calls.  */
    callee = gimple_call_fn (stmt);
!   if (TREE_CODE (callee) == OBJ_TYPE_REF
!       && gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee)) != NULL_TREE)
      {
!       gimple_call_set_fn (stmt, OBJ_TYPE_REF_EXPR (callee));
        return true;
      }
  
--- 1537,1563 ----
  
    /* Check for virtual calls that became direct calls.  */
    callee = gimple_call_fn (stmt);
!   if (TREE_CODE (callee) == OBJ_TYPE_REF)
      {
!       tree binfo, fndecl, delta, obj;
!       HOST_WIDE_INT token;
! 
!       if (gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee)) != NULL_TREE)
! 	{
! 	  gimple_call_set_fn (stmt, OBJ_TYPE_REF_EXPR (callee));
! 	  return true;
! 	}
! 
!       obj = OBJ_TYPE_REF_OBJECT (callee);
!       binfo = gimple_extract_devirt_binfo_from_cst (obj);
!       if (!binfo)
! 	return false;
!       token = TREE_INT_CST_LOW (OBJ_TYPE_REF_TOKEN (callee));
!       fndecl = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta, false);
!       if (!fndecl)
! 	return false;
!       gcc_assert (integer_zerop (delta));
!       gimple_call_set_fndecl (stmt, fndecl);
        return true;
      }
  
Index: src/gcc/gimple.h
===================================================================
*** src.orig/gcc/gimple.h
--- src/gcc/gimple.h
*************** const char *gimple_decl_printable_name (
*** 898,903 ****
--- 898,904 ----
  bool gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace);
  tree gimple_get_virt_mehtod_for_binfo (HOST_WIDE_INT, tree, tree *, bool);
  void gimple_adjust_this_by_delta (gimple_stmt_iterator *, tree);
+ tree gimple_extract_devirt_binfo_from_cst (tree);
  /* Returns true iff T is a valid GIMPLE statement.  */
  extern bool is_gimple_stmt (tree);
  
Index: src/gcc/testsuite/g++.dg/opt/devirt2.C
===================================================================
*** /dev/null
--- src/gcc/testsuite/g++.dg/opt/devirt2.C
***************
*** 0 ****
--- 1,11 ----
+ // { dg-do compile }
+ // { dg-options "-O2" }
+ // { dg-final { scan-assembler-times "xyzzy" 2 } }
+ 
+ struct S { S(); virtual void xyzzy(); };
+ struct R { int a; S s; R(); };
+ S s;
+ R r;
+ inline void foo(S *p) { p->xyzzy(); }
+ void bar() {foo(&s);}
+ void bah() {foo(&r.s);}
Index: src/gcc/testsuite/g++.dg/ipa/devirt-g-1.C
===================================================================
*** /dev/null
--- src/gcc/testsuite/g++.dg/ipa/devirt-g-1.C
***************
*** 0 ****
--- 1,24 ----
+ // { dg-do compile }
+ // { dg-options "-O2 -fdump-ipa-cp -fdump-tree-optimized" }
+ 
+ struct S { S(); virtual void xyzzy(); void otherstuff(); };
+ struct R { int a; S s; R(); };
+ S s;
+ R r;
+ 
+ void S::xyzzy ()
+ {
+   otherstuff ();
+   otherstuff ();
+ }
+ 
+ static void __attribute__ ((noinline)) foo(S *p) { p->xyzzy(); }
+ void bar() {foo(&s); }
+ 
+ static void __attribute__ ((noinline)) foh(S *p) { p->xyzzy(); }
+ void bah() {foh(&r.s); }
+ 
+ /* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*S::xyzzy" "cp"  } } */
+ /* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+ /* { dg-final { cleanup-ipa-dump "cp" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: src/gcc/testsuite/g++.dg/opt/devirt1.C
===================================================================
*** src.orig/gcc/testsuite/g++.dg/opt/devirt1.C
--- src/gcc/testsuite/g++.dg/opt/devirt1.C
***************
*** 1,6 ****
  // { dg-do compile }
! // { dg-options "-O" }
! // { dg-final { scan-assembler "xyzzy" { xfail *-*-* } } }
  
  struct S { S(); virtual void xyzzy(); };
  inline void foo(S *s) { s->xyzzy(); }
--- 1,6 ----
  // { dg-do compile }
! // { dg-options "-O2" }
! // { dg-final { scan-assembler "xyzzy" } }
  
  struct S { S(); virtual void xyzzy(); };
  inline void foo(S *s) { s->xyzzy(); }