[PR,45934,2/5] Dynamic type change detection

This is a re-submission of the patch originally posted here:
http://gcc.gnu.org/ml/gcc-patches/2010-12/msg00091.html

The main differences are:

1. No special provisons for builtin functions.  There is a new big
   comment explaining why we ignore all calls when searching for
   statements changing the dynamic type.

2. Aggregate stores to COMPONENT_REFs are also considered as changing
   dynamic the type.

3. The new use of DECL_CONTEXT is briefly documented in tree.h.

4. check_stmt_for_type_change is now ready to be called even after it
   has returned true and checks that if we derive any known new
   dynamic type, it is always the same one.

5. I have renamed the functions a slightly.  There is now a function
   called detect_type_change which should be directly used for
   declarations and their component_refs and dereferenced pointers and
   their component_refs.  Dereferenced pointers are not supplied
   directly from the analyzed IL but are created by
   detect_type_change_ssa which is to be used to detect any dynamic
   type changed of objects pointed to by an SSA_NAME (as it currently
   is, all callers check a PARAM_DECL DEFAULT_DEF
   SSA_NAMEs). detect_type_change_ssa uses detect_type_change
   internally.

   So when we construct a PASS_THROUGH jump function without any
   binary operation (pass through functions with an operation are
   never combined with a known_type ones), we use
   detect_type_change_ssa.

   On the other hand, when we either want to construct an ANCESTOR
   jump function (and therefore are looking at an address of a
   component of a dereferenced pointer) or TYPE_KNOWN jump function
   (looking either at an address of a decl or its component), we use
   directly detect_type_change.  On both occasions we already need to
   invoke get_ref_base_and extent and so we supply this information to
   detect_type_change which uses it to initialize its ao_ref structure
   on its own.  

   I was considering using ao_ref_init_from_ptr_and_size but I would
   then need to adjust ref_alias_set and base_alias_set because I
   really want to utilize TBAA (and therefore either compute the sets
   or set the ref field too) and considered that to be even uglier
   than setting up the whole thing myself.

   The size is set to the size of a pointer.  We really only care
   about components representing ancestors (get_binfo_at_offset is
   smart enough to recognize them and not use encapsulating
   object-type for non-artificial components) which have at least one
   VMT pointer right at the beginning if they have any virtual methods
   at all and cannot be part of arrays or larger structures without a
   VMT at the beginning.  This also prevents us from wrongly deriving
   a type from an object constructed inside another one with placement
   new (there is a new testcase in the next patch for this).

   All of this is for objects passed by reference, there is no
   provision (or intention) to track stuff passed by value.

I hope I answered all comments raised in the previous thread.

As before, the code that does both detection of dynamic type changes
and tries to extract the new dynamic type in some cases is the
following:

----------------------------------------------------------------------

/* Structure to be passed in between detect_type_change and
   check_stmt_for_type_change.  */

struct type_change_info
{
  /* The declaration or SSA_NAME pointer of the base that we are checking for
     type change.  */
  tree object;
  /* If we actually can tell the type that the object has changed to, it is
     stored in this field.  Otherwise it remains NULL_TREE.  */
  tree known_current_type;
  /* Set to true if dynamic type change has been detected.  */
  bool type_maybe_changed;
  /* Set to true if multiple types have been encountered.  known_current_type
     must be disregarded in that case.  */
  bool multiple_types_encountered;
};

/* Return true if STMT can modify a virtual method table pointer.

   This function makes special assumptions about both constructors and
   destructors which are all the functions that are allowed to alter the VMT
   pointers.  It assumes that destructors begin with assignment into all VMT
   pointers and that constructors essentially look in the following way:

   1) The very first thing they do is that they call constructors of ancestor
   sub-objects that have them.

   2) Then VMT pointers of this and all its ancestors is set to new values
   corresponding to the type corresponding to the constructor.

   3) Only afterwards, other stuff such as constructor of member sub-objects
   and the code written by the user is run.  Only this may include calling
   virtual functions, directly or indirectly.

   There is no way to call a constructor of an ancestor sub-object in any
   other way.

   This means that we do not have to care whether constructors get the correct
   type information because they will always change it (in fact, if we define
   the type to be given by the VMT pointer, it is undefined).

   The most important fact to derive from the above is that if, for some
   statement in the section 3, we try to detect whether the dynamic type has
   changed, we can safely ignore all calls as we examine the function body
   backwards until we reach statements in section 2 because these calls cannot
   be ancestor constructors or destructors (if the input is not bogus) and so
   do not change the dynamic type.  We then must detect that statements in
   section 2 change the dynamic type and can try to derive the new type.  That
   is enough and we can stop, we will never see the calls into constructors of
   sub-objects in this code.  Therefore we can safely ignore all call
   statements that we traverse.
  */

static bool
stmt_may_be_vtbl_ptr_store (gimple stmt)
{
  if (is_gimple_call (stmt))
    return false;
  else if (is_gimple_assign (stmt))
    {
      tree lhs = gimple_assign_lhs (stmt);

      if (TREE_CODE (lhs) == COMPONENT_REF
	  && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
	  && !AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
	    return false;
      /* In the future we might want to use get_base_ref_and_offset to find
	 if there is a field corresponding to the offset and if so, proceed
	 almost like if it was a component ref.  */
    }
  return true;
}

/* If STMT can be proved to be an assignment to the virtual method table
   pointer of ANALYZED_OBJ and the type associated witht the new table
   identified, return the type.  Otherwise return NULL_TREE.  */

static tree
extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj)
{
  tree lhs, t, obj;

  if (!is_gimple_assign (stmt))
    return NULL_TREE;

  lhs = gimple_assign_lhs (stmt);

  if (TREE_CODE (lhs) != COMPONENT_REF)
    return NULL_TREE;
   obj = lhs;

   if (!DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
     return NULL_TREE;

   do
     {
       obj = TREE_OPERAND (obj, 0);
     }
   while (TREE_CODE (obj) == COMPONENT_REF);
   if (TREE_CODE (obj) == MEM_REF)
     obj = TREE_OPERAND (obj, 0);
   if (TREE_CODE (obj) == ADDR_EXPR)
     obj = TREE_OPERAND (obj, 0);
   if (obj != analyzed_obj)
     return NULL_TREE;

   t = gimple_assign_rhs1 (stmt);
   if (TREE_CODE (t) != ADDR_EXPR)
     return NULL_TREE;
   t = get_base_address (TREE_OPERAND (t, 0));
   if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t))
     return NULL_TREE;

   return DECL_CONTEXT (t);
}

/* Callbeck of walk_aliased_vdefs and a helper function for
   detect_type_change to check whether a particular statement may modify
   the virtual table pointer, and if possible also determine the new type of
   the (sub-)object.  It stores its result into DATA, which points to a
   type_change_info structure.  */

static bool
check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
{
  gimple stmt = SSA_NAME_DEF_STMT (vdef);
  struct type_change_info *tci = (struct type_change_info *) data;

  if (stmt_may_be_vtbl_ptr_store (stmt))
    {
      tree type;
      type = extr_type_from_vtbl_ptr_store (stmt, tci->object);
      if (tci->type_maybe_changed
	  && type != tci->known_current_type)
	tci->multiple_types_encountered = true;
      tci->known_current_type = type;
      tci->type_maybe_changed = true;
      return true;
    }
  else
    return false;
}

/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
   looking for assignments to its virtual table pointer.  If it is, return true
   and fill in the jump function JFUNC with relevant type information or set it
   to unknown.  ARG is the object itself (not a pointer to it, unless
   dereferenced).  BASE is the base of the memory access as returned by
   get_ref_base_and_extent, as is the offset.  */

static bool
detect_type_change (tree arg, tree base, gimple call,
		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
{
  struct type_change_info tci;
  tree type;
  ao_ref ao;

  gcc_checking_assert (DECL_P (arg)
		       || TREE_CODE (arg) == MEM_REF
		       || handled_component_p (arg));
  /* Const calls cannot call virtual methods through VMT and so type changes do
     not matter.  */
  if (!gimple_vuse (call))
    return false;

  ao.ref = arg;
  ao.base = base;
  ao.offset = offset;
  ao.size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ptr_type_node)) * BITS_PER_UNIT;
  ao.max_size = ao.size;
  ao.ref_alias_set = -1;
  ao.base_alias_set = -1;

  type = TREE_TYPE (arg);
  while (handled_component_p (arg))
    arg = TREE_OPERAND (arg, 0);
  if (TREE_CODE (arg) == MEM_REF)
    arg = TREE_OPERAND (arg, 0);
  if (TREE_CODE (arg) == ADDR_EXPR)
    arg = TREE_OPERAND (arg, 0);
  tci.object = arg;
  tci.known_current_type = NULL_TREE;
  tci.type_maybe_changed = false;
  tci.multiple_types_encountered = false;

  walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
		      &tci, NULL);
  if (!tci.type_maybe_changed)
    return false;

 if (!tci.known_current_type || tci.multiple_types_encountered)
   jfunc->type = IPA_JF_UNKNOWN;
 else
   {
     tree new_binfo = get_binfo_at_offset (TYPE_BINFO (tci.known_current_type),
					   offset, type);
     if (new_binfo)
	{
	  jfunc->type = IPA_JF_KNOWN_TYPE;
	  jfunc->value.base_binfo = new_binfo;
	}
     else
       jfunc->type = IPA_JF_UNKNOWN;
   }

  return true;
}

/* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
   SSA name (its dereference will become the base and the offset is assumed to
   be zero).  */

static bool
detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
{
  gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
  if (!POINTER_TYPE_P (TREE_TYPE (arg))
      || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
    return false;

  arg = build_simple_mem_ref (arg);

  return detect_type_change (arg, arg, call, jfunc, 0);
}

----------------------------------------------------------------------

The patch implementing just the detection of changes with all the
callers is below, the rest is in the next patch.

I have bootstrapped and tested this patch separately (i.e. with the
previous ones but not the subsequent ones) on x86-64-linux and it has
also passed make check-c++ on i686.

Thanks for any comments,

Martin


2010-11-09  Martin Jambor  <mjambor@suse.cz>

	PR tree-optimization/45934
	PR tree-optimization/46302
	* ipa-prop.c (type_change_info): New type.
	(stmt_may_be_vtbl_ptr_store): New function.
	(check_stmt_for_type_change): Likewise.
	(detect_type_change): Likewise.
	(detect_type_change_ssa): Likewise.
	(compute_complex_assign_jump_func): Check for dynamic type change.
	(compute_complex_ancestor_jump_func): Likewise.
	(compute_known_type_jump_func): Likewise.
	(compute_scalar_jump_functions): Likewise.
	(ipa_analyze_virtual_call_uses): Likewise.
	(ipa_analyze_node): Push and pop cfun, set current_function_decl.

	* testsuite/g++.dg/ipa/devirt-c-1.C: New test.
	* testsuite/g++.dg/ipa/devirt-c-2.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-c-3.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-c-4.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-c-5.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-c-6.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-c-7.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-d-1.C: Likewise.
	* testsuite/g++.dg/torture/pr45934.C: Likewise.

On Wed, 15 Dec 2010, Martin Jambor wrote:

> This is a re-submission of the patch originally posted here:
> http://gcc.gnu.org/ml/gcc-patches/2010-12/msg00091.html
> 
> The main differences are:
> 
> 1. No special provisons for builtin functions.  There is a new big
>    comment explaining why we ignore all calls when searching for
>    statements changing the dynamic type.
> 
> 2. Aggregate stores to COMPONENT_REFs are also considered as changing
>    dynamic the type.
> 
> 3. The new use of DECL_CONTEXT is briefly documented in tree.h.
> 
> 4. check_stmt_for_type_change is now ready to be called even after it
>    has returned true and checks that if we derive any known new
>    dynamic type, it is always the same one.
> 
> 5. I have renamed the functions a slightly.  There is now a function
>    called detect_type_change which should be directly used for
>    declarations and their component_refs and dereferenced pointers and
>    their component_refs.  Dereferenced pointers are not supplied
>    directly from the analyzed IL but are created by
>    detect_type_change_ssa which is to be used to detect any dynamic
>    type changed of objects pointed to by an SSA_NAME (as it currently
>    is, all callers check a PARAM_DECL DEFAULT_DEF
>    SSA_NAMEs). detect_type_change_ssa uses detect_type_change
>    internally.
> 
>    So when we construct a PASS_THROUGH jump function without any
>    binary operation (pass through functions with an operation are
>    never combined with a known_type ones), we use
>    detect_type_change_ssa.
> 
>    On the other hand, when we either want to construct an ANCESTOR
>    jump function (and therefore are looking at an address of a
>    component of a dereferenced pointer) or TYPE_KNOWN jump function
>    (looking either at an address of a decl or its component), we use
>    directly detect_type_change.  On both occasions we already need to
>    invoke get_ref_base_and extent and so we supply this information to
>    detect_type_change which uses it to initialize its ao_ref structure
>    on its own.  
> 
>    I was considering using ao_ref_init_from_ptr_and_size but I would
>    then need to adjust ref_alias_set and base_alias_set because I
>    really want to utilize TBAA (and therefore either compute the sets
>    or set the ref field too) and considered that to be even uglier
>    than setting up the whole thing myself.
> 
>    The size is set to the size of a pointer.  We really only care
>    about components representing ancestors (get_binfo_at_offset is
>    smart enough to recognize them and not use encapsulating
>    object-type for non-artificial components) which have at least one
>    VMT pointer right at the beginning if they have any virtual methods
>    at all and cannot be part of arrays or larger structures without a
>    VMT at the beginning.  This also prevents us from wrongly deriving
>    a type from an object constructed inside another one with placement
>    new (there is a new testcase in the next patch for this).
> 
>    All of this is for objects passed by reference, there is no
>    provision (or intention) to track stuff passed by value.
> 
> I hope I answered all comments raised in the previous thread.
> 
> As before, the code that does both detection of dynamic type changes
> and tries to extract the new dynamic type in some cases is the
> following:

I'm commenting in the plain text below, not in the patch.

> ----------------------------------------------------------------------
> 
> /* Structure to be passed in between detect_type_change and
>    check_stmt_for_type_change.  */
> 
> struct type_change_info
> {
>   /* The declaration or SSA_NAME pointer of the base that we are checking for
>      type change.  */
>   tree object;
>   /* If we actually can tell the type that the object has changed to, it is
>      stored in this field.  Otherwise it remains NULL_TREE.  */
>   tree known_current_type;
>   /* Set to true if dynamic type change has been detected.  */
>   bool type_maybe_changed;
>   /* Set to true if multiple types have been encountered.  known_current_type
>      must be disregarded in that case.  */
>   bool multiple_types_encountered;
> };
> 
> /* Return true if STMT can modify a virtual method table pointer.
> 
>    This function makes special assumptions about both constructors and
>    destructors which are all the functions that are allowed to alter the VMT
>    pointers.  It assumes that destructors begin with assignment into all VMT
>    pointers and that constructors essentially look in the following way:
> 
>    1) The very first thing they do is that they call constructors of ancestor
>    sub-objects that have them.
> 
>    2) Then VMT pointers of this and all its ancestors is set to new values
>    corresponding to the type corresponding to the constructor.
> 
>    3) Only afterwards, other stuff such as constructor of member sub-objects
>    and the code written by the user is run.  Only this may include calling
>    virtual functions, directly or indirectly.
> 
>    There is no way to call a constructor of an ancestor sub-object in any
>    other way.
> 
>    This means that we do not have to care whether constructors get the correct
>    type information because they will always change it (in fact, if we define
>    the type to be given by the VMT pointer, it is undefined).
> 
>    The most important fact to derive from the above is that if, for some
>    statement in the section 3, we try to detect whether the dynamic type has
>    changed, we can safely ignore all calls as we examine the function body
>    backwards until we reach statements in section 2 because these calls cannot
>    be ancestor constructors or destructors (if the input is not bogus) and so
>    do not change the dynamic type.  We then must detect that statements in
>    section 2 change the dynamic type and can try to derive the new type.  That
>    is enough and we can stop, we will never see the calls into constructors of
>    sub-objects in this code.  Therefore we can safely ignore all call
>    statements that we traverse.
>   */
>
> static bool
> stmt_may_be_vtbl_ptr_store (gimple stmt)
> {
>   if (is_gimple_call (stmt))
>     return false;
>   else if (is_gimple_assign (stmt))
>     {
>       tree lhs = gimple_assign_lhs (stmt);
> 
>       if (TREE_CODE (lhs) == COMPONENT_REF
> 	  && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
> 	  && !AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
> 	    return false;
>       /* In the future we might want to use get_base_ref_and_offset to find
> 	 if there is a field corresponding to the offset and if so, proceed
> 	 almost like if it was a component ref.  */
>     }
>   return true;
> }

Hm.  Does this address

extern "C" void abort (void);
extern "C" void *malloc(__SIZE_TYPE__);
inline void* operator new(__SIZE_TYPE__, void* __p) throw() { return __p;
}
int x;
class A {
public:
   virtual ~A() { }
};
class B : public A {
public:
   virtual ~B() { if (x == 1) abort (); x = 1; }
};
void __attribute__((noinline,noclone)) foo (void *p)
{
 B *b = reinterpret_cast<B *>(p);
 b->~B();
 new (p) A;
}
int main()
{
 void *p = __builtin_malloc (sizeof (B));
 new (p) B;
 foo(p);
 reinterpret_cast<A *>(p)->~A();
 return 0;
}

where we have a call (foo) that changes the dynamic type of *p?

Or is this a non-issue with the current patch because we only
ever devirtualize calls when we eventually see a statically
allocated object?  Can you still add the above testcase please?
Can you add a comment to the above function that ignoring
calls is not possible if we start to devirtualize for
allocated objects?  Or rather, mention that we only deal
with statically allocated objects?

You said you could make a failing testcase out of the
array testcase sketch - I can't see if that is included in
the set of testcases you add.  Is it?

> /* If STMT can be proved to be an assignment to the virtual method table
>    pointer of ANALYZED_OBJ and the type associated witht the new table
>    identified, return the type.  Otherwise return NULL_TREE.  */
> 
> static tree
> extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj)
> {
>   tree lhs, t, obj;
> 
>   if (!is_gimple_assign (stmt))
>     return NULL_TREE;
> 
>   lhs = gimple_assign_lhs (stmt);
> 
>   if (TREE_CODE (lhs) != COMPONENT_REF)
>     return NULL_TREE;
>    obj = lhs;
> 
>    if (!DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
>      return NULL_TREE;
> 
>    do
>      {
>        obj = TREE_OPERAND (obj, 0);
>      }
>    while (TREE_CODE (obj) == COMPONENT_REF);
>    if (TREE_CODE (obj) == MEM_REF)
>      obj = TREE_OPERAND (obj, 0);
>    if (TREE_CODE (obj) == ADDR_EXPR)
>      obj = TREE_OPERAND (obj, 0);
>    if (obj != analyzed_obj)
>      return NULL_TREE;
> 
>    t = gimple_assign_rhs1 (stmt);
>    if (TREE_CODE (t) != ADDR_EXPR)
>      return NULL_TREE;
>    t = get_base_address (TREE_OPERAND (t, 0));
>    if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t))
>      return NULL_TREE;
> 
>    return DECL_CONTEXT (t);
> }
> 
> /* Callbeck of walk_aliased_vdefs and a helper function for
>    detect_type_change to check whether a particular statement may modify
>    the virtual table pointer, and if possible also determine the new type of
>    the (sub-)object.  It stores its result into DATA, which points to a
>    type_change_info structure.  */
> 
> static bool
> check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
> {
>   gimple stmt = SSA_NAME_DEF_STMT (vdef);
>   struct type_change_info *tci = (struct type_change_info *) data;
> 
>   if (stmt_may_be_vtbl_ptr_store (stmt))
>     {
>       tree type;
>       type = extr_type_from_vtbl_ptr_store (stmt, tci->object);
>       if (tci->type_maybe_changed
> 	  && type != tci->known_current_type)
> 	tci->multiple_types_encountered = true;
>       tci->known_current_type = type;
>       tci->type_maybe_changed = true;
>       return true;
>     }
>   else
>     return false;
> }
> 
> /* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
>    looking for assignments to its virtual table pointer.  If it is, return true
>    and fill in the jump function JFUNC with relevant type information or set it
>    to unknown.  ARG is the object itself (not a pointer to it, unless
>    dereferenced).  BASE is the base of the memory access as returned by
>    get_ref_base_and_extent, as is the offset.  */
> 
> static bool
> detect_type_change (tree arg, tree base, gimple call,
> 		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
> {
>   struct type_change_info tci;
>   tree type;
>   ao_ref ao;
> 
>   gcc_checking_assert (DECL_P (arg)
> 		       || TREE_CODE (arg) == MEM_REF
> 		       || handled_component_p (arg));
>   /* Const calls cannot call virtual methods through VMT and so type changes do
>      not matter.  */

But as there won't be calls we are interested in in the callee why do
we end up here at all?  Well, I guess this can be cleaned up in
a followup.

>   if (!gimple_vuse (call))
>     return false;
> 
>   ao.ref = arg;
>   ao.base = base;
>   ao.offset = offset;
>   ao.size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ptr_type_node)) * BITS_PER_UNIT;

POINTER_SIZE

>   ao.max_size = ao.size;
>   ao.ref_alias_set = -1;
>   ao.base_alias_set = -1;
> 
>   type = TREE_TYPE (arg);
>   while (handled_component_p (arg))
>     arg = TREE_OPERAND (arg, 0);
>   if (TREE_CODE (arg) == MEM_REF)
>     arg = TREE_OPERAND (arg, 0);
>   if (TREE_CODE (arg) == ADDR_EXPR)
>     arg = TREE_OPERAND (arg, 0);
>   tci.object = arg;
>   tci.known_current_type = NULL_TREE;
>   tci.type_maybe_changed = false;
>   tci.multiple_types_encountered = false;
> 
>   walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
> 		      &tci, NULL);
>   if (!tci.type_maybe_changed)
>     return false;
> 
>  if (!tci.known_current_type || tci.multiple_types_encountered)
>    jfunc->type = IPA_JF_UNKNOWN;
>  else
>    {
>      tree new_binfo = get_binfo_at_offset (TYPE_BINFO (tci.known_current_type),
> 					   offset, type);
>      if (new_binfo)
> 	{
> 	  jfunc->type = IPA_JF_KNOWN_TYPE;
> 	  jfunc->value.base_binfo = new_binfo;
> 	}
>      else
>        jfunc->type = IPA_JF_UNKNOWN;
>    }
> 
>   return true;
> }
> 
> /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
>    SSA name (its dereference will become the base and the offset is assumed to
>    be zero).  */
> 
> static bool
> detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
> {
>   gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
>   if (!POINTER_TYPE_P (TREE_TYPE (arg))
>       || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
>     return false;
> 
>   arg = build_simple_mem_ref (arg);

This still yields to wrong TBAA disambiguations.  I suggest you
pass a flag to detect_type_change and drop back to basic tbaa:

  ao.base_alias_set = get_alias_set (ptr_type_node);
  ao.ref_alias_set = get_alias_set (ptr_type_node);

(you could do the ref_alias_set initialization unconditionally
and the base_alias_set one if the call is from detect_type_change_ssa
in which case you should leave ao.ref as NULL_TREE.  Basically
do a ao_ref_init_from_ptr_and_size but provide some TBAA
information).  Or you can simply do

  arg = build2 (MEM_REF, ptr_type_node, arg,
	        build_int_cst (ptr_type_node, 0));

which will magically do the same things.

I think I have reviewed patch 3/5 with the above as well as far
as I can see.

Iff we indeed only deal with statically allocated objects patch 2/5
is ok with the minor adjustments I requested and the TBAA issue
fixed for detect_type_change_ssa.

Thanks,
Richard.

>   return detect_type_change (arg, arg, call, jfunc, 0);
> }
> 
> ----------------------------------------------------------------------
> 
> The patch implementing just the detection of changes with all the
> callers is below, the rest is in the next patch.
> 
> I have bootstrapped and tested this patch separately (i.e. with the
> previous ones but not the subsequent ones) on x86-64-linux and it has
> also passed make check-c++ on i686.
> 
> Thanks for any comments,
> 
> Martin
> 
> 
> 2010-11-09  Martin Jambor  <mjambor@suse.cz>
> 
> 	PR tree-optimization/45934
> 	PR tree-optimization/46302
> 	* ipa-prop.c (type_change_info): New type.
> 	(stmt_may_be_vtbl_ptr_store): New function.
> 	(check_stmt_for_type_change): Likewise.
> 	(detect_type_change): Likewise.
> 	(detect_type_change_ssa): Likewise.
> 	(compute_complex_assign_jump_func): Check for dynamic type change.
> 	(compute_complex_ancestor_jump_func): Likewise.
> 	(compute_known_type_jump_func): Likewise.
> 	(compute_scalar_jump_functions): Likewise.
> 	(ipa_analyze_virtual_call_uses): Likewise.
> 	(ipa_analyze_node): Push and pop cfun, set current_function_decl.
> 
> 	* testsuite/g++.dg/ipa/devirt-c-1.C: New test.
> 	* testsuite/g++.dg/ipa/devirt-c-2.C: Likewise.
> 	* testsuite/g++.dg/ipa/devirt-c-3.C: Likewise.
> 	* testsuite/g++.dg/ipa/devirt-c-4.C: Likewise.
> 	* testsuite/g++.dg/ipa/devirt-c-5.C: Likewise.
> 	* testsuite/g++.dg/ipa/devirt-c-6.C: Likewise.
> 	* testsuite/g++.dg/ipa/devirt-c-7.C: Likewise.
> 	* testsuite/g++.dg/ipa/devirt-d-1.C: Likewise.
> 	* testsuite/g++.dg/torture/pr45934.C: Likewise.
> 
> 
> Index: icln/gcc/ipa-prop.c
> ===================================================================
> --- icln.orig/gcc/ipa-prop.c
> +++ icln/gcc/ipa-prop.c
> @@ -350,6 +350,151 @@ ipa_print_all_jump_functions (FILE *f)
>      }
>  }
>  
> +/* Structure to be passed in between detect_type_change and
> +   check_stmt_for_type_change.  */
> +
> +struct type_change_info
> +{
> +  /* Set to true if dynamic type change has been detected.  */
> +  bool type_maybe_changed;
> +};
> +
> +/* Return true if STMT can modify a virtual method table pointer.
> +
> +   This function makes special assumptions about both constructors and
> +   destructors which are all the functions that are allowed to alter the VMT
> +   pointers.  It assumes that destructors begin with assignment into all VMT
> +   pointers and that constructors essentially look in the following way:
> +
> +   1) The very first thing they do is that they call constructors of ancestor
> +   sub-objects that have them.
> +
> +   2) Then VMT pointers of this and all its ancestors is set to new values
> +   corresponding to the type corresponding to the constructor.
> +
> +   3) Only afterwards, other stuff such as constructor of member sub-objects
> +   and the code written by the user is run.  Only this may include calling
> +   virtual functions, directly or indirectly.
> +
> +   There is no way to call a constructor of an ancestor sub-object in any
> +   other way.
> +
> +   This means that we do not have to care whether constructors get the correct
> +   type information because they will always change it (in fact, if we define
> +   the type to be given by the VMT pointer, it is undefined).
> +
> +   The most important fact to derive from the above is that if, for some
> +   statement in the section 3, we try to detect whether the dynamic type has
> +   changed, we can safely ignore all calls as we examine the function body
> +   backwards until we reach statements in section 2 because these calls cannot
> +   be ancestor constructors or destructors (if the input is not bogus) and so
> +   do not change the dynamic type.  We then must detect that statements in
> +   section 2 change the dynamic type and can try to derive the new type.  That
> +   is enough and we can stop, we will never see the calls into constructors of
> +   sub-objects in this code.  Therefore we can safely ignore all call
> +   statements that we traverse.
> +  */
> +
> +static bool
> +stmt_may_be_vtbl_ptr_store (gimple stmt)
> +{
> +  if (is_gimple_call (stmt))
> +    return false;
> +  else if (is_gimple_assign (stmt))
> +    {
> +      tree lhs = gimple_assign_lhs (stmt);
> +
> +      if (TREE_CODE (lhs) == COMPONENT_REF
> +	  && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
> +	  && !AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
> +	    return false;
> +      /* In the future we might want to use get_base_ref_and_offset to find
> +	 if there is a field corresponding to the offset and if so, proceed
> +	 almost like if it was a component ref.  */
> +    }
> +  return true;
> +}
> +
> +/* Callbeck of walk_aliased_vdefs and a helper function for
> +   detect_type_change to check whether a particular statement may modify
> +   the virtual table pointer, and if possible also determine the new type of
> +   the (sub-)object.  It stores its result into DATA, which points to a
> +   type_change_info structure.  */
> +
> +static bool
> +check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
> +{
> +  gimple stmt = SSA_NAME_DEF_STMT (vdef);
> +  struct type_change_info *tci = (struct type_change_info *) data;
> +
> +  if (stmt_may_be_vtbl_ptr_store (stmt))
> +    {
> +      tci->type_maybe_changed = true;
> +      return true;
> +    }
> +  else
> +    return false;
> +}
> +
> +/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
> +   looking for assignments to its virtual table pointer.  If it is, return true
> +   and fill in the jump function JFUNC with relevant type information or set it
> +   to unknown.  ARG is the object itself (not a pointer to it, unless
> +   dereferenced).  BASE is the base of the memory access as returned by
> +   get_ref_base_and_extent, as is the offset.  */
> +
> +static bool
> +detect_type_change (tree arg, tree base, gimple call,
> +		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
> +{
> +  struct type_change_info tci;
> +  ao_ref ao;
> +
> +  gcc_checking_assert (DECL_P (arg)
> +		       || TREE_CODE (arg) == MEM_REF
> +		       || handled_component_p (arg));
> +  /* Const calls cannot call virtual methods through VMT and so type changes do
> +     not matter.  */
> +  if (!gimple_vuse (call))
> +    return false;
> +
> +  tci.type_maybe_changed = false;
> +
> +  ao.ref = arg;
> +  ao.base = base;
> +  ao.offset = offset;
> +  ao.size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ptr_type_node)) * BITS_PER_UNIT;
> +  ao.max_size = ao.size;
> +  ao.ref_alias_set = -1;
> +  ao.base_alias_set = -1;
> +
> +  walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
> +		      &tci, NULL);
> +  if (!tci.type_maybe_changed)
> +    return false;
> +
> +  jfunc->type = IPA_JF_UNKNOWN;
> +  return true;
> +}
> +
> +/* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
> +   SSA name (its dereference will become the base and the offset is assumed to
> +   be zero).  */
> +
> +static bool
> +detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
> +{
> +  gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
> +  if (!POINTER_TYPE_P (TREE_TYPE (arg))
> +      || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
> +    return false;
> +
> +  arg = build_simple_mem_ref (arg);
> +
> +  return detect_type_change (arg, arg, call, jfunc, 0);
> +}
> +
> +
>  /* Given that an actual argument is an SSA_NAME (given in NAME) and is a result
>     of an assignment statement STMT, try to find out whether NAME can be
>     described by a (possibly polynomial) pass-through jump-function or an
> @@ -359,10 +504,10 @@ ipa_print_all_jump_functions (FILE *f)
>  static void
>  compute_complex_assign_jump_func (struct ipa_node_params *info,
>  				  struct ipa_jump_func *jfunc,
> -				  gimple stmt, tree name)
> +				  gimple call, gimple stmt, tree name)
>  {
>    HOST_WIDE_INT offset, size, max_size;
> -  tree op1, op2, base, type;
> +  tree op1, op2, base, ssa;
>    int index;
>  
>    op1 = gimple_assign_rhs1 (stmt);
> @@ -388,7 +533,8 @@ compute_complex_assign_jump_func (struct
>  	  jfunc->value.pass_through.operation = gimple_assign_rhs_code (stmt);
>  	  jfunc->value.pass_through.operand = op2;
>  	}
> -      else if (gimple_assign_unary_nop_p (stmt))
> +      else if (gimple_assign_unary_nop_p (stmt)
> +	       && !detect_type_change_ssa (op1, call, jfunc))
>  	{
>  	  jfunc->type = IPA_JF_PASS_THROUGH;
>  	  jfunc->value.pass_through.formal_id = index;
> @@ -399,10 +545,8 @@ compute_complex_assign_jump_func (struct
>  
>    if (TREE_CODE (op1) != ADDR_EXPR)
>      return;
> -
>    op1 = TREE_OPERAND (op1, 0);
> -  type = TREE_TYPE (op1);
> -  if (TREE_CODE (type) != RECORD_TYPE)
> +  if (TREE_CODE (TREE_TYPE (op1)) != RECORD_TYPE)
>      return;
>    base = get_ref_base_and_extent (op1, &offset, &size, &max_size);
>    if (TREE_CODE (base) != MEM_REF
> @@ -411,20 +555,21 @@ compute_complex_assign_jump_func (struct
>        || max_size != size)
>      return;
>    offset += mem_ref_offset (base).low * BITS_PER_UNIT;
> -  base = TREE_OPERAND (base, 0);
> -  if (TREE_CODE (base) != SSA_NAME
> -      || !SSA_NAME_IS_DEFAULT_DEF (base)
> +  ssa = TREE_OPERAND (base, 0);
> +  if (TREE_CODE (ssa) != SSA_NAME
> +      || !SSA_NAME_IS_DEFAULT_DEF (ssa)
>        || offset < 0)
>      return;
>  
>    /* Dynamic types are changed only in constructors and destructors and  */
> -  index = ipa_get_param_decl_index (info, SSA_NAME_VAR (base));
> -  if (index >= 0)
> +  index = ipa_get_param_decl_index (info, SSA_NAME_VAR (ssa));
> +  if (index >= 0
> +      && !detect_type_change (op1, base, call, jfunc, offset))
>      {
>        jfunc->type = IPA_JF_ANCESTOR;
>        jfunc->value.ancestor.formal_id = index;
>        jfunc->value.ancestor.offset = offset;
> -      jfunc->value.ancestor.type = type;
> +      jfunc->value.ancestor.type = TREE_TYPE (op1);
>      }
>  }
>  
> @@ -453,12 +598,12 @@ compute_complex_assign_jump_func (struct
>  static void
>  compute_complex_ancestor_jump_func (struct ipa_node_params *info,
>  				    struct ipa_jump_func *jfunc,
> -				    gimple phi)
> +				    gimple call, gimple phi)
>  {
>    HOST_WIDE_INT offset, size, max_size;
>    gimple assign, cond;
>    basic_block phi_bb, assign_bb, cond_bb;
> -  tree tmp, parm, expr;
> +  tree tmp, parm, expr, obj;
>    int index, i;
>  
>    if (gimple_phi_num_args (phi) != 2)
> @@ -486,6 +631,7 @@ compute_complex_ancestor_jump_func (stru
>    if (TREE_CODE (expr) != ADDR_EXPR)
>      return;
>    expr = TREE_OPERAND (expr, 0);
> +  obj = expr;
>    expr = get_ref_base_and_extent (expr, &offset, &size, &max_size);
>  
>    if (TREE_CODE (expr) != MEM_REF
> @@ -513,7 +659,6 @@ compute_complex_ancestor_jump_func (stru
>        || !integer_zerop (gimple_cond_rhs (cond)))
>      return;
>  
> -
>    phi_bb = gimple_bb (phi);
>    for (i = 0; i < 2; i++)
>      {
> @@ -522,10 +667,13 @@ compute_complex_ancestor_jump_func (stru
>  	return;
>      }
>  
> -  jfunc->type = IPA_JF_ANCESTOR;
> -  jfunc->value.ancestor.formal_id = index;
> -  jfunc->value.ancestor.offset = offset;
> -  jfunc->value.ancestor.type = TREE_TYPE (TREE_TYPE (tmp));
> +  if (!detect_type_change (obj, expr, call, jfunc, offset))
> +    {
> +      jfunc->type = IPA_JF_ANCESTOR;
> +      jfunc->value.ancestor.formal_id = index;
> +      jfunc->value.ancestor.offset = offset;
> +      jfunc->value.ancestor.type = TREE_TYPE (obj);;
> +    }
>  }
>  
>  /* Given OP whch is passed as an actual argument to a called function,
> @@ -533,7 +681,8 @@ compute_complex_ancestor_jump_func (stru
>     and if so, create one and store it to JFUNC.  */
>  
>  static void
> -compute_known_type_jump_func (tree op, struct ipa_jump_func *jfunc)
> +compute_known_type_jump_func (tree op, struct ipa_jump_func *jfunc,
> +			      gimple call)
>  {
>    HOST_WIDE_INT offset, size, max_size;
>    tree base, binfo;
> @@ -551,6 +700,9 @@ compute_known_type_jump_func (tree op, s
>        || is_global_var (base))
>      return;
>  
> +  if (detect_type_change (op, base, call, jfunc, offset))
> +    return;
> +
>    binfo = TYPE_BINFO (TREE_TYPE (base));
>    if (!binfo)
>      return;
> @@ -592,7 +744,8 @@ compute_scalar_jump_functions (struct ip
>  	    {
>  	      int index = ipa_get_param_decl_index (info, SSA_NAME_VAR (arg));
>  
> -	      if (index >= 0)
> +	      if (index >= 0
> +		  && !detect_type_change_ssa (arg, call, &functions[num]))
>  		{
>  		  functions[num].type = IPA_JF_PASS_THROUGH;
>  		  functions[num].value.pass_through.formal_id = index;
> @@ -604,14 +757,14 @@ compute_scalar_jump_functions (struct ip
>  	      gimple stmt = SSA_NAME_DEF_STMT (arg);
>  	      if (is_gimple_assign (stmt))
>  		compute_complex_assign_jump_func (info, &functions[num],
> -						  stmt, arg);
> +						  call, stmt, arg);
>  	      else if (gimple_code (stmt) == GIMPLE_PHI)
>  		compute_complex_ancestor_jump_func (info, &functions[num],
> -						    stmt);
> +						    call, stmt);
>  	    }
>  	}
>        else
> -	compute_known_type_jump_func (arg, &functions[num]);
> +	compute_known_type_jump_func (arg, &functions[num], call);
>      }
>  }
>  
> @@ -1218,6 +1371,7 @@ ipa_analyze_virtual_call_uses (struct cg
>  			       struct ipa_node_params *info, gimple call,
>  			       tree target)
>  {
> +  struct ipa_jump_func jfunc;
>    tree obj = OBJ_TYPE_REF_OBJECT (target);
>    tree var;
>    int index;
> @@ -1241,7 +1395,8 @@ ipa_analyze_virtual_call_uses (struct cg
>    var = SSA_NAME_VAR (obj);
>    index = ipa_get_param_decl_index (info, var);
>  
> -  if (index >= 0)
> +  if (index >= 0
> +      && !detect_type_change_ssa (obj, call, &jfunc))
>      ipa_note_param_call (node, index, call, true);
>  }
>  
> @@ -1364,6 +1519,8 @@ ipa_analyze_node (struct cgraph_node *no
>    struct param_analysis_info *parms_info;
>    int i, param_count;
>  
> +  push_cfun (DECL_STRUCT_FUNCTION (node->decl));
> +  current_function_decl = node->decl;
>    ipa_initialize_node_params (node);
>  
>    param_count = ipa_get_param_count (info);
> @@ -1376,6 +1533,9 @@ ipa_analyze_node (struct cgraph_node *no
>    for (i = 0; i < param_count; i++)
>      if (parms_info[i].visited_statements)
>        BITMAP_FREE (parms_info[i].visited_statements);
> +
> +  current_function_decl = NULL;
> +  pop_cfun ();
>  }
>  
>  
> Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
> @@ -0,0 +1,71 @@
> +/* Verify that ipa-cp correctly detects the dynamic type of an object
> +   under construction when doing devirtualization.  */
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
> +
> +extern "C" void abort (void);
> +
> +class A
> +{
> +public:
> +  int data;
> +  A();
> +  virtual int foo (int i);
> +};
> +
> +class B : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +class C : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +int C::foo (int i)
> +{
> +  return i + 3;
> +}
> +
> +static int middleman (class A *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +A::A ()
> +{
> +  if (middleman (this, get_input ()) != 2)
> +    abort ();
> +}
> +
> +static void bah ()
> +{
> +  class B b;
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = 0; i < 10; i++)
> +    bah ();
> +  return 0;
> +}
> Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
> @@ -0,0 +1,79 @@
> +/* Verify that ipa-cp correctly detects the dynamic type of an object
> +   under construction when doing devirtualization.  */
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
> +
> +extern "C" void abort (void);
> +
> +class Distraction
> +{
> +public:
> +  float f;
> +  double d;
> +  Distraction ()
> +  {
> +    f = 8.3;
> +    d = 10.2;
> +  }
> +  virtual float bar (float z);
> +};
> +
> +class A
> +{
> +public:
> +  int data;
> +  A();
> +  virtual int foo (int i);
> +};
> +
> +class B : public Distraction, public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +float Distraction::bar (float z)
> +{
> +  f += z;
> +  return f/2;
> +}
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +static int middleman (class A *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +A::A()
> +{
> +  if (middleman (this, get_input ()) != 2)
> +    abort ();
> +}
> +
> +static void bah ()
> +{
> +  class B b;
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = 0; i < 10; i++)
> +    bah ();
> +  return 0;
> +}
> Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-3.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-3.C
> @@ -0,0 +1,80 @@
> +/* Verify that ipa-cp correctly detects the dynamic type of an object
> +   under construction when doing devirtualization.  */
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fno-inline"  } */
> +
> +extern "C" void abort (void);
> +
> +class Distraction
> +{
> +public:
> +  float f;
> +  double d;
> +  Distraction ()
> +  {
> +    f = 8.3;
> +    d = 10.2;
> +  }
> +  virtual float bar (float z);
> +};
> +
> +class A
> +{
> +public:
> +  int data;
> +  A();
> +  virtual int foo (int i);
> +};
> +
> +class B : public Distraction, public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +float Distraction::bar (float z)
> +{
> +  f += z;
> +  return f/2;
> +}
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +static int __attribute__ ((noinline))
> +middleman (class A *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +inline __attribute__ ((always_inline)) A::A()
> +{
> +  if (middleman (this, get_input ()) != 2)
> +    abort ();
> +}
> +
> +static void bah ()
> +{
> +  class B b;
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = 0; i < 10; i++)
> +    bah ();
> +  return 0;
> +}
> Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-4.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-4.C
> @@ -0,0 +1,110 @@
> +/* Verify that ipa-cp correctly detects the dynamic type of an object
> +   under construction when doing devirtualization.  */
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fno-inline"  } */
> +
> +extern "C" void abort (void);
> +
> +class Distraction
> +{
> +public:
> +  float f;
> +  double d;
> +  Distraction ()
> +  {
> +    f = 8.3;
> +    d = 10.2;
> +  }
> +  virtual float bar (float z);
> +};
> +
> +class A
> +{
> +public:
> +  int data;
> +  A();
> +  virtual int foo (int i);
> +};
> +
> +class B : public Distraction, public A
> +{
> +public:
> +  B();
> +  virtual int foo (int i);
> +};
> +
> +class C : public B
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +
> +float Distraction::bar (float z)
> +{
> +  f += z;
> +  return f/2;
> +}
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +int C::foo (int i)
> +{
> +  return i + 3;
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +static int __attribute__ ((noinline))
> +middleman (class A *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +static void __attribute__ ((noinline))
> +sth2 (A *a)
> +{
> +  if (a->foo (get_input ()) != 3)
> +    abort ();
> +}
> +
> +inline void __attribute__ ((always_inline)) sth1 (B *b)
> +{
> +  sth2 (b);
> +}
> +
> +inline __attribute__ ((always_inline)) A::A()
> +{
> +  if (middleman (this, get_input ()) != 2)
> +    abort ();
> +}
> +
> +B::B() : Distraction(), A()
> +{
> +  sth1 (this);
> +}
> +
> +static void bah ()
> +{
> +  class C c;
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = 0; i < 10; i++)
> +    bah ();
> +  return 0;
> +}
> Index: icln/gcc/testsuite/g++.dg/ipa/devirt-d-1.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/ipa/devirt-d-1.C
> @@ -0,0 +1,71 @@
> +/* Verify that ipa-cp correctly detects the dynamic type of an object
> +   under destruction when doing devirtualization.  */
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
> +
> +extern "C" void abort (void);
> +
> +class A
> +{
> +public:
> +  int data;
> +  ~A();
> +  virtual int foo (int i);
> +};
> +
> +class B : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +class C : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +int C::foo (int i)
> +{
> +  return i + 3;
> +}
> +
> +static int middleman (class A *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +A::~A ()
> +{
> +  if (middleman (this, get_input ()) != 2)
> +    abort ();
> +}
> +
> +static void bah ()
> +{
> +  class B b;
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = 0; i < 10; i++)
> +    bah ();
> +  return 0;
> +}
> Index: icln/gcc/testsuite/g++.dg/torture/pr45934.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/torture/pr45934.C
> @@ -0,0 +1,23 @@
> +/* { dg-do run } */
> +
> +extern "C" void abort ();
> +
> +struct B *b;
> +
> +struct B
> +{
> +  virtual void f () { }
> +  ~B() { b->f(); }
> +};
> +
> +struct D : public B
> +{
> +  virtual void f () { abort (); }
> +};
> +
> +int main ()
> +{
> +  D d;
> +  b = &d;
> +  return 0;
> +}
> Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-5.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-5.C
> @@ -0,0 +1,79 @@
> +/* Verify that ipa-cp correctly detects the dynamic type of an object
> +   under construction when doing devirtualization.  */
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
> +
> +extern "C" void abort (void);
> +
> +class B;
> +
> +class A
> +{
> +public:
> +  int data;
> +  A();
> +  A(B *b);
> +  virtual int foo (int i);
> +};
> +
> +class B : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +class C : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +int C::foo (int i)
> +{
> +  return i + 3;
> +}
> +
> +static int middleman (class A *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +A::A ()
> +{
> +}
> +
> +A::A (B *b)
> +{
> +  if (middleman (b, get_input ()) != 3)
> +    abort ();
> +}
> +
> +static void bah ()
> +{
> +  B b;
> +  A a(&b);
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = 0; i < 10; i++)
> +    bah ();
> +  return 0;
> +}
> Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-6.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-6.C
> @@ -0,0 +1,72 @@
> +/* Verify that ipa-cp correctly detects the dynamic type of an object
> +   under construction when doing devirtualization.  */
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fno-inline"  } */
> +
> +extern "C" void abort (void);
> +
> +class A
> +{
> +public:
> +  int data;
> +  A();
> +  virtual int foo (int i);
> +};
> +
> +class B : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +class C : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +int C::foo (int i)
> +{
> +  return i + 3;
> +}
> +
> +static inline int __attribute__ ((always_inline))
> +middleman (class A *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +__attribute__ ((noinline)) A::A ()
> +{
> +  if (middleman (this, get_input ()) != 2)
> +    abort ();
> +}
> +
> +static void bah ()
> +{
> +  class B b;
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = 0; i < 10; i++)
> +    bah ();
> +  return 0;
> +}
> Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-7.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-7.C
> @@ -0,0 +1,101 @@
> +/* Verify that ipa-cp can use TBAA to fingure out that the virtual call to
> +   D::foo is not affected by dynamic type change in constructor A::A(D*).  */
> +
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp"  } */
> +
> +extern "C" void abort (void);
> +
> +class D;
> +
> +class A
> +{
> +public:
> +  int data;
> +  A();
> +  A(D *d);
> +  virtual int foo (int i);
> +};
> +
> +class B : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +class C : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +class D
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +int C::foo (int i)
> +{
> +  return i + 3;
> +}
> +
> +int D::foo (int i)
> +{
> +  return i + 4;
> +}
> +
> +static int middleman (class A *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +static int middleman (class D *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +A::A ()
> +{
> +}
> +
> +A::A (D *d)
> +{
> +  if (middleman (d, get_input ()) != 5)
> +    abort ();
> +  if (middleman (this, get_input ()) != 2)
> +    abort ();
> +}
> +
> +static void bah ()
> +{
> +  D d;
> +  A a(&d);
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = 0; i < 10; i++)
> +    bah ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*D::foo"  "cp"  } } */
> +/* { dg-final { cleanup-ipa-dump "cp" } } */
> 
>

Hi,

On Thu, Jan 13, 2011 at 12:56:24PM +0100, Richard Guenther wrote:
> On Wed, 15 Dec 2010, Martin Jambor wrote:
> 
> 
> I'm commenting in the plain text below, not in the patch.
> 
> > ----------------------------------------------------------------------
> > 
> > /* Structure to be passed in between detect_type_change and
> >    check_stmt_for_type_change.  */
> > 
> > struct type_change_info
> > {
> >   /* The declaration or SSA_NAME pointer of the base that we are checking for
> >      type change.  */
> >   tree object;
> >   /* If we actually can tell the type that the object has changed to, it is
> >      stored in this field.  Otherwise it remains NULL_TREE.  */
> >   tree known_current_type;
> >   /* Set to true if dynamic type change has been detected.  */
> >   bool type_maybe_changed;
> >   /* Set to true if multiple types have been encountered.  known_current_type
> >      must be disregarded in that case.  */
> >   bool multiple_types_encountered;
> > };
> > 
> > /* Return true if STMT can modify a virtual method table pointer.
> > 
> >    This function makes special assumptions about both constructors and
> >    destructors which are all the functions that are allowed to alter the VMT
> >    pointers.  It assumes that destructors begin with assignment into all VMT
> >    pointers and that constructors essentially look in the following way:
> > 
> >    1) The very first thing they do is that they call constructors of ancestor
> >    sub-objects that have them.
> > 
> >    2) Then VMT pointers of this and all its ancestors is set to new values
> >    corresponding to the type corresponding to the constructor.
> > 
> >    3) Only afterwards, other stuff such as constructor of member sub-objects
> >    and the code written by the user is run.  Only this may include calling
> >    virtual functions, directly or indirectly.
> > 
> >    There is no way to call a constructor of an ancestor sub-object in any
> >    other way.
> > 
> >    This means that we do not have to care whether constructors get the correct
> >    type information because they will always change it (in fact, if we define
> >    the type to be given by the VMT pointer, it is undefined).
> > 
> >    The most important fact to derive from the above is that if, for some
> >    statement in the section 3, we try to detect whether the dynamic type has
> >    changed, we can safely ignore all calls as we examine the function body
> >    backwards until we reach statements in section 2 because these calls cannot
> >    be ancestor constructors or destructors (if the input is not bogus) and so
> >    do not change the dynamic type.  We then must detect that statements in
> >    section 2 change the dynamic type and can try to derive the new type.  That
> >    is enough and we can stop, we will never see the calls into constructors of
> >    sub-objects in this code.  Therefore we can safely ignore all call
> >    statements that we traverse.
> >   */
> >
> > static bool
> > stmt_may_be_vtbl_ptr_store (gimple stmt)
> > {
> >   if (is_gimple_call (stmt))
> >     return false;
> >   else if (is_gimple_assign (stmt))
> >     {
> >       tree lhs = gimple_assign_lhs (stmt);
> > 
> >       if (TREE_CODE (lhs) == COMPONENT_REF
> > 	  && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
> > 	  && !AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
> > 	    return false;
> >       /* In the future we might want to use get_base_ref_and_offset to find
> > 	 if there is a field corresponding to the offset and if so, proceed
> > 	 almost like if it was a component ref.  */
> >     }
> >   return true;
> > }
> 
> Hm.  Does this address
> 
> extern "C" void abort (void);
> extern "C" void *malloc(__SIZE_TYPE__);
> inline void* operator new(__SIZE_TYPE__, void* __p) throw() { return __p;
> }
> int x;
> class A {
> public:
>    virtual ~A() { }
> };
> class B : public A {
> public:
>    virtual ~B() { if (x == 1) abort (); x = 1; }
> };
> void __attribute__((noinline,noclone)) foo (void *p)
> {
>  B *b = reinterpret_cast<B *>(p);
>  b->~B();
>  new (p) A;
> }
> int main()
> {
>  void *p = __builtin_malloc (sizeof (B));
>  new (p) B;
>  foo(p);
>  reinterpret_cast<A *>(p)->~A();
>  return 0;
> }
> 
> where we have a call (foo) that changes the dynamic type of *p?
> 
> Or is this a non-issue with the current patch because we only
> ever devirtualize calls when we eventually see a statically
> allocated object?  Can you still add the above testcase please?
> Can you add a comment to the above function that ignoring
> calls is not possible if we start to devirtualize for
> allocated objects?  Or rather, mention that we only deal
> with statically allocated objects?

Exactly.  I've added the above as another testcase and added a comment
saying that we only care for automatically allocated objects at this
point.

> 
> You said you could make a failing testcase out of the
> array testcase sketch - I can't see if that is included in
> the set of testcases you add.  Is it?

It is the last one in the third patch in the series.

> 
> > /* If STMT can be proved to be an assignment to the virtual method table
> >    pointer of ANALYZED_OBJ and the type associated witht the new table
> >    identified, return the type.  Otherwise return NULL_TREE.  */
> > 
> > static tree
> > extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj)
> > {
> >   tree lhs, t, obj;
> > 
> >   if (!is_gimple_assign (stmt))
> >     return NULL_TREE;
> > 
> >   lhs = gimple_assign_lhs (stmt);
> > 
> >   if (TREE_CODE (lhs) != COMPONENT_REF)
> >     return NULL_TREE;
> >    obj = lhs;
> > 
> >    if (!DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
> >      return NULL_TREE;
> > 
> >    do
> >      {
> >        obj = TREE_OPERAND (obj, 0);
> >      }
> >    while (TREE_CODE (obj) == COMPONENT_REF);
> >    if (TREE_CODE (obj) == MEM_REF)
> >      obj = TREE_OPERAND (obj, 0);
> >    if (TREE_CODE (obj) == ADDR_EXPR)
> >      obj = TREE_OPERAND (obj, 0);
> >    if (obj != analyzed_obj)
> >      return NULL_TREE;
> > 
> >    t = gimple_assign_rhs1 (stmt);
> >    if (TREE_CODE (t) != ADDR_EXPR)
> >      return NULL_TREE;
> >    t = get_base_address (TREE_OPERAND (t, 0));
> >    if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t))
> >      return NULL_TREE;
> > 
> >    return DECL_CONTEXT (t);
> > }
> > 
> > /* Callbeck of walk_aliased_vdefs and a helper function for
> >    detect_type_change to check whether a particular statement may modify
> >    the virtual table pointer, and if possible also determine the new type of
> >    the (sub-)object.  It stores its result into DATA, which points to a
> >    type_change_info structure.  */
> > 
> > static bool
> > check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
> > {
> >   gimple stmt = SSA_NAME_DEF_STMT (vdef);
> >   struct type_change_info *tci = (struct type_change_info *) data;
> > 
> >   if (stmt_may_be_vtbl_ptr_store (stmt))
> >     {
> >       tree type;
> >       type = extr_type_from_vtbl_ptr_store (stmt, tci->object);
> >       if (tci->type_maybe_changed
> > 	  && type != tci->known_current_type)
> > 	tci->multiple_types_encountered = true;
> >       tci->known_current_type = type;
> >       tci->type_maybe_changed = true;
> >       return true;
> >     }
> >   else
> >     return false;
> > }
> > 
> > /* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
> >    looking for assignments to its virtual table pointer.  If it is, return true
> >    and fill in the jump function JFUNC with relevant type information or set it
> >    to unknown.  ARG is the object itself (not a pointer to it, unless
> >    dereferenced).  BASE is the base of the memory access as returned by
> >    get_ref_base_and_extent, as is the offset.  */
> > 
> > static bool
> > detect_type_change (tree arg, tree base, gimple call,
> > 		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
> > {
> >   struct type_change_info tci;
> >   tree type;
> >   ao_ref ao;
> > 
> >   gcc_checking_assert (DECL_P (arg)
> > 		       || TREE_CODE (arg) == MEM_REF
> > 		       || handled_component_p (arg));
> >   /* Const calls cannot call virtual methods through VMT and so type changes do
> >      not matter.  */
> 
> But as there won't be calls we are interested in in the callee why do
> we end up here at all?  Well, I guess this can be cleaned up in
> a followup.

The call here represents the point at which we need to figure out
whether the type has changed, not the calls we skip when walking.  We
take the virtual SSA name from it.  If we can, that is.  The comment
just states that if we cannot, it does not matter since the function
does not use memory including any VMTs.

> 
> >   if (!gimple_vuse (call))
> >     return false;
> > 
> >   ao.ref = arg;
> >   ao.base = base;
> >   ao.offset = offset;
> >   ao.size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ptr_type_node)) * BITS_PER_UNIT;
> 
> POINTER_SIZE

OK

> 
> >   ao.max_size = ao.size;
> >   ao.ref_alias_set = -1;
> >   ao.base_alias_set = -1;
> > 
> >   type = TREE_TYPE (arg);
> >   while (handled_component_p (arg))
> >     arg = TREE_OPERAND (arg, 0);
> >   if (TREE_CODE (arg) == MEM_REF)
> >     arg = TREE_OPERAND (arg, 0);
> >   if (TREE_CODE (arg) == ADDR_EXPR)
> >     arg = TREE_OPERAND (arg, 0);
> >   tci.object = arg;
> >   tci.known_current_type = NULL_TREE;
> >   tci.type_maybe_changed = false;
> >   tci.multiple_types_encountered = false;
> > 
> >   walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
> > 		      &tci, NULL);
> >   if (!tci.type_maybe_changed)
> >     return false;
> > 
> >  if (!tci.known_current_type || tci.multiple_types_encountered)
> >    jfunc->type = IPA_JF_UNKNOWN;
> >  else
> >    {
> >      tree new_binfo = get_binfo_at_offset (TYPE_BINFO (tci.known_current_type),
> > 					   offset, type);
> >      if (new_binfo)
> > 	{
> > 	  jfunc->type = IPA_JF_KNOWN_TYPE;
> > 	  jfunc->value.base_binfo = new_binfo;
> > 	}
> >      else
> >        jfunc->type = IPA_JF_UNKNOWN;
> >    }
> > 
> >   return true;
> > }
> > 
> > /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
> >    SSA name (its dereference will become the base and the offset is assumed to
> >    be zero).  */
> > 
> > static bool
> > detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
> > {
> >   gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
> >   if (!POINTER_TYPE_P (TREE_TYPE (arg))
> >       || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
> >     return false;
> > 
> >   arg = build_simple_mem_ref (arg);
> 
> This still yields to wrong TBAA disambiguations.  I suggest you
> pass a flag to detect_type_change and drop back to basic tbaa:
> 
>   ao.base_alias_set = get_alias_set (ptr_type_node);
>   ao.ref_alias_set = get_alias_set (ptr_type_node);
> 
> (you could do the ref_alias_set initialization unconditionally
> and the base_alias_set one if the call is from detect_type_change_ssa
> in which case you should leave ao.ref as NULL_TREE.  Basically
> do a ao_ref_init_from_ptr_and_size but provide some TBAA
> information).  Or you can simply do
> 
>   arg = build2 (MEM_REF, ptr_type_node, arg,
> 	        build_int_cst (ptr_type_node, 0));

I did the above and the testcase devirt-c-7.C below started to fail.
Maybe I ask too much from the TBAA.  My idea was that objects with
virtual methods should only be accessed with their or their ancestors'
types and so decided to rely on the provided pointer type.

Nevertheless, at the moment I decided to simply remove the testcase
and keep it aside until I have a better idea of how much this matters
in practice.  Maybe I'll revisit this in the future.

> 
> which will magically do the same things.
> 
> I think I have reviewed patch 3/5 with the above as well as far
> as I can see.

Yes.

> 
> Iff we indeed only deal with statically allocated objects patch 2/5
> is ok with the minor adjustments I requested and the TBAA issue
> fixed for detect_type_change_ssa.

And the 3/5?

I am now in the process of doing the final touches and re-testing this
and the two subsequent patches and would like to commit it (them?)
tomorrow.

Thanks a lot,

Martin


> 
> Thanks,
> Richard.
> 
> >   return detect_type_change (arg, arg, call, jfunc, 0);
> > }
> > 
> > ----------------------------------------------------------------------
> > 
> > The patch implementing just the detection of changes with all the
> > callers is below, the rest is in the next patch.
> > 
> > I have bootstrapped and tested this patch separately (i.e. with the
> > previous ones but not the subsequent ones) on x86-64-linux and it has
> > also passed make check-c++ on i686.
> > 
> > Thanks for any comments,
> > 
> > Martin
> > 
> > 
> > 2010-11-09  Martin Jambor  <mjambor@suse.cz>
> > 
> > 	PR tree-optimization/45934
> > 	PR tree-optimization/46302
> > 	* ipa-prop.c (type_change_info): New type.
> > 	(stmt_may_be_vtbl_ptr_store): New function.
> > 	(check_stmt_for_type_change): Likewise.
> > 	(detect_type_change): Likewise.
> > 	(detect_type_change_ssa): Likewise.
> > 	(compute_complex_assign_jump_func): Check for dynamic type change.
> > 	(compute_complex_ancestor_jump_func): Likewise.
> > 	(compute_known_type_jump_func): Likewise.
> > 	(compute_scalar_jump_functions): Likewise.
> > 	(ipa_analyze_virtual_call_uses): Likewise.
> > 	(ipa_analyze_node): Push and pop cfun, set current_function_decl.
> > 
> > 	* testsuite/g++.dg/ipa/devirt-c-1.C: New test.
> > 	* testsuite/g++.dg/ipa/devirt-c-2.C: Likewise.
> > 	* testsuite/g++.dg/ipa/devirt-c-3.C: Likewise.
> > 	* testsuite/g++.dg/ipa/devirt-c-4.C: Likewise.
> > 	* testsuite/g++.dg/ipa/devirt-c-5.C: Likewise.
> > 	* testsuite/g++.dg/ipa/devirt-c-6.C: Likewise.
> > 	* testsuite/g++.dg/ipa/devirt-c-7.C: Likewise.
> > 	* testsuite/g++.dg/ipa/devirt-d-1.C: Likewise.
> > 	* testsuite/g++.dg/torture/pr45934.C: Likewise.
> > 
> > 
> > Index: icln/gcc/ipa-prop.c
> > ===================================================================
> > --- icln.orig/gcc/ipa-prop.c
> > +++ icln/gcc/ipa-prop.c
> > @@ -350,6 +350,151 @@ ipa_print_all_jump_functions (FILE *f)
> >      }
> >  }
> >  
> > +/* Structure to be passed in between detect_type_change and
> > +   check_stmt_for_type_change.  */
> > +
> > +struct type_change_info
> > +{
> > +  /* Set to true if dynamic type change has been detected.  */
> > +  bool type_maybe_changed;
> > +};
> > +
> > +/* Return true if STMT can modify a virtual method table pointer.
> > +
> > +   This function makes special assumptions about both constructors and
> > +   destructors which are all the functions that are allowed to alter the VMT
> > +   pointers.  It assumes that destructors begin with assignment into all VMT
> > +   pointers and that constructors essentially look in the following way:
> > +
> > +   1) The very first thing they do is that they call constructors of ancestor
> > +   sub-objects that have them.
> > +
> > +   2) Then VMT pointers of this and all its ancestors is set to new values
> > +   corresponding to the type corresponding to the constructor.
> > +
> > +   3) Only afterwards, other stuff such as constructor of member sub-objects
> > +   and the code written by the user is run.  Only this may include calling
> > +   virtual functions, directly or indirectly.
> > +
> > +   There is no way to call a constructor of an ancestor sub-object in any
> > +   other way.
> > +
> > +   This means that we do not have to care whether constructors get the correct
> > +   type information because they will always change it (in fact, if we define
> > +   the type to be given by the VMT pointer, it is undefined).
> > +
> > +   The most important fact to derive from the above is that if, for some
> > +   statement in the section 3, we try to detect whether the dynamic type has
> > +   changed, we can safely ignore all calls as we examine the function body
> > +   backwards until we reach statements in section 2 because these calls cannot
> > +   be ancestor constructors or destructors (if the input is not bogus) and so
> > +   do not change the dynamic type.  We then must detect that statements in
> > +   section 2 change the dynamic type and can try to derive the new type.  That
> > +   is enough and we can stop, we will never see the calls into constructors of
> > +   sub-objects in this code.  Therefore we can safely ignore all call
> > +   statements that we traverse.
> > +  */
> > +
> > +static bool
> > +stmt_may_be_vtbl_ptr_store (gimple stmt)
> > +{
> > +  if (is_gimple_call (stmt))
> > +    return false;
> > +  else if (is_gimple_assign (stmt))
> > +    {
> > +      tree lhs = gimple_assign_lhs (stmt);
> > +
> > +      if (TREE_CODE (lhs) == COMPONENT_REF
> > +	  && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
> > +	  && !AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
> > +	    return false;
> > +      /* In the future we might want to use get_base_ref_and_offset to find
> > +	 if there is a field corresponding to the offset and if so, proceed
> > +	 almost like if it was a component ref.  */
> > +    }
> > +  return true;
> > +}
> > +
> > +/* Callbeck of walk_aliased_vdefs and a helper function for
> > +   detect_type_change to check whether a particular statement may modify
> > +   the virtual table pointer, and if possible also determine the new type of
> > +   the (sub-)object.  It stores its result into DATA, which points to a
> > +   type_change_info structure.  */
> > +
> > +static bool
> > +check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
> > +{
> > +  gimple stmt = SSA_NAME_DEF_STMT (vdef);
> > +  struct type_change_info *tci = (struct type_change_info *) data;
> > +
> > +  if (stmt_may_be_vtbl_ptr_store (stmt))
> > +    {
> > +      tci->type_maybe_changed = true;
> > +      return true;
> > +    }
> > +  else
> > +    return false;
> > +}
> > +
> > +/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
> > +   looking for assignments to its virtual table pointer.  If it is, return true
> > +   and fill in the jump function JFUNC with relevant type information or set it
> > +   to unknown.  ARG is the object itself (not a pointer to it, unless
> > +   dereferenced).  BASE is the base of the memory access as returned by
> > +   get_ref_base_and_extent, as is the offset.  */
> > +
> > +static bool
> > +detect_type_change (tree arg, tree base, gimple call,
> > +		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
> > +{
> > +  struct type_change_info tci;
> > +  ao_ref ao;
> > +
> > +  gcc_checking_assert (DECL_P (arg)
> > +		       || TREE_CODE (arg) == MEM_REF
> > +		       || handled_component_p (arg));
> > +  /* Const calls cannot call virtual methods through VMT and so type changes do
> > +     not matter.  */
> > +  if (!gimple_vuse (call))
> > +    return false;
> > +
> > +  tci.type_maybe_changed = false;
> > +
> > +  ao.ref = arg;
> > +  ao.base = base;
> > +  ao.offset = offset;
> > +  ao.size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ptr_type_node)) * BITS_PER_UNIT;
> > +  ao.max_size = ao.size;
> > +  ao.ref_alias_set = -1;
> > +  ao.base_alias_set = -1;
> > +
> > +  walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
> > +		      &tci, NULL);
> > +  if (!tci.type_maybe_changed)
> > +    return false;
> > +
> > +  jfunc->type = IPA_JF_UNKNOWN;
> > +  return true;
> > +}
> > +
> > +/* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
> > +   SSA name (its dereference will become the base and the offset is assumed to
> > +   be zero).  */
> > +
> > +static bool
> > +detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
> > +{
> > +  gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
> > +  if (!POINTER_TYPE_P (TREE_TYPE (arg))
> > +      || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
> > +    return false;
> > +
> > +  arg = build_simple_mem_ref (arg);
> > +
> > +  return detect_type_change (arg, arg, call, jfunc, 0);
> > +}
> > +
> > +
> >  /* Given that an actual argument is an SSA_NAME (given in NAME) and is a result
> >     of an assignment statement STMT, try to find out whether NAME can be
> >     described by a (possibly polynomial) pass-through jump-function or an
> > @@ -359,10 +504,10 @@ ipa_print_all_jump_functions (FILE *f)
> >  static void
> >  compute_complex_assign_jump_func (struct ipa_node_params *info,
> >  				  struct ipa_jump_func *jfunc,
> > -				  gimple stmt, tree name)
> > +				  gimple call, gimple stmt, tree name)
> >  {
> >    HOST_WIDE_INT offset, size, max_size;
> > -  tree op1, op2, base, type;
> > +  tree op1, op2, base, ssa;
> >    int index;
> >  
> >    op1 = gimple_assign_rhs1 (stmt);
> > @@ -388,7 +533,8 @@ compute_complex_assign_jump_func (struct
> >  	  jfunc->value.pass_through.operation = gimple_assign_rhs_code (stmt);
> >  	  jfunc->value.pass_through.operand = op2;
> >  	}
> > -      else if (gimple_assign_unary_nop_p (stmt))
> > +      else if (gimple_assign_unary_nop_p (stmt)
> > +	       && !detect_type_change_ssa (op1, call, jfunc))
> >  	{
> >  	  jfunc->type = IPA_JF_PASS_THROUGH;
> >  	  jfunc->value.pass_through.formal_id = index;
> > @@ -399,10 +545,8 @@ compute_complex_assign_jump_func (struct
> >  
> >    if (TREE_CODE (op1) != ADDR_EXPR)
> >      return;
> > -
> >    op1 = TREE_OPERAND (op1, 0);
> > -  type = TREE_TYPE (op1);
> > -  if (TREE_CODE (type) != RECORD_TYPE)
> > +  if (TREE_CODE (TREE_TYPE (op1)) != RECORD_TYPE)
> >      return;
> >    base = get_ref_base_and_extent (op1, &offset, &size, &max_size);
> >    if (TREE_CODE (base) != MEM_REF
> > @@ -411,20 +555,21 @@ compute_complex_assign_jump_func (struct
> >        || max_size != size)
> >      return;
> >    offset += mem_ref_offset (base).low * BITS_PER_UNIT;
> > -  base = TREE_OPERAND (base, 0);
> > -  if (TREE_CODE (base) != SSA_NAME
> > -      || !SSA_NAME_IS_DEFAULT_DEF (base)
> > +  ssa = TREE_OPERAND (base, 0);
> > +  if (TREE_CODE (ssa) != SSA_NAME
> > +      || !SSA_NAME_IS_DEFAULT_DEF (ssa)
> >        || offset < 0)
> >      return;
> >  
> >    /* Dynamic types are changed only in constructors and destructors and  */
> > -  index = ipa_get_param_decl_index (info, SSA_NAME_VAR (base));
> > -  if (index >= 0)
> > +  index = ipa_get_param_decl_index (info, SSA_NAME_VAR (ssa));
> > +  if (index >= 0
> > +      && !detect_type_change (op1, base, call, jfunc, offset))
> >      {
> >        jfunc->type = IPA_JF_ANCESTOR;
> >        jfunc->value.ancestor.formal_id = index;
> >        jfunc->value.ancestor.offset = offset;
> > -      jfunc->value.ancestor.type = type;
> > +      jfunc->value.ancestor.type = TREE_TYPE (op1);
> >      }
> >  }
> >  
> > @@ -453,12 +598,12 @@ compute_complex_assign_jump_func (struct
> >  static void
> >  compute_complex_ancestor_jump_func (struct ipa_node_params *info,
> >  				    struct ipa_jump_func *jfunc,
> > -				    gimple phi)
> > +				    gimple call, gimple phi)
> >  {
> >    HOST_WIDE_INT offset, size, max_size;
> >    gimple assign, cond;
> >    basic_block phi_bb, assign_bb, cond_bb;
> > -  tree tmp, parm, expr;
> > +  tree tmp, parm, expr, obj;
> >    int index, i;
> >  
> >    if (gimple_phi_num_args (phi) != 2)
> > @@ -486,6 +631,7 @@ compute_complex_ancestor_jump_func (stru
> >    if (TREE_CODE (expr) != ADDR_EXPR)
> >      return;
> >    expr = TREE_OPERAND (expr, 0);
> > +  obj = expr;
> >    expr = get_ref_base_and_extent (expr, &offset, &size, &max_size);
> >  
> >    if (TREE_CODE (expr) != MEM_REF
> > @@ -513,7 +659,6 @@ compute_complex_ancestor_jump_func (stru
> >        || !integer_zerop (gimple_cond_rhs (cond)))
> >      return;
> >  
> > -
> >    phi_bb = gimple_bb (phi);
> >    for (i = 0; i < 2; i++)
> >      {
> > @@ -522,10 +667,13 @@ compute_complex_ancestor_jump_func (stru
> >  	return;
> >      }
> >  
> > -  jfunc->type = IPA_JF_ANCESTOR;
> > -  jfunc->value.ancestor.formal_id = index;
> > -  jfunc->value.ancestor.offset = offset;
> > -  jfunc->value.ancestor.type = TREE_TYPE (TREE_TYPE (tmp));
> > +  if (!detect_type_change (obj, expr, call, jfunc, offset))
> > +    {
> > +      jfunc->type = IPA_JF_ANCESTOR;
> > +      jfunc->value.ancestor.formal_id = index;
> > +      jfunc->value.ancestor.offset = offset;
> > +      jfunc->value.ancestor.type = TREE_TYPE (obj);;
> > +    }
> >  }
> >  
> >  /* Given OP whch is passed as an actual argument to a called function,
> > @@ -533,7 +681,8 @@ compute_complex_ancestor_jump_func (stru
> >     and if so, create one and store it to JFUNC.  */
> >  
> >  static void
> > -compute_known_type_jump_func (tree op, struct ipa_jump_func *jfunc)
> > +compute_known_type_jump_func (tree op, struct ipa_jump_func *jfunc,
> > +			      gimple call)
> >  {
> >    HOST_WIDE_INT offset, size, max_size;
> >    tree base, binfo;
> > @@ -551,6 +700,9 @@ compute_known_type_jump_func (tree op, s
> >        || is_global_var (base))
> >      return;
> >  
> > +  if (detect_type_change (op, base, call, jfunc, offset))
> > +    return;
> > +
> >    binfo = TYPE_BINFO (TREE_TYPE (base));
> >    if (!binfo)
> >      return;
> > @@ -592,7 +744,8 @@ compute_scalar_jump_functions (struct ip
> >  	    {
> >  	      int index = ipa_get_param_decl_index (info, SSA_NAME_VAR (arg));
> >  
> > -	      if (index >= 0)
> > +	      if (index >= 0
> > +		  && !detect_type_change_ssa (arg, call, &functions[num]))
> >  		{
> >  		  functions[num].type = IPA_JF_PASS_THROUGH;
> >  		  functions[num].value.pass_through.formal_id = index;
> > @@ -604,14 +757,14 @@ compute_scalar_jump_functions (struct ip
> >  	      gimple stmt = SSA_NAME_DEF_STMT (arg);
> >  	      if (is_gimple_assign (stmt))
> >  		compute_complex_assign_jump_func (info, &functions[num],
> > -						  stmt, arg);
> > +						  call, stmt, arg);
> >  	      else if (gimple_code (stmt) == GIMPLE_PHI)
> >  		compute_complex_ancestor_jump_func (info, &functions[num],
> > -						    stmt);
> > +						    call, stmt);
> >  	    }
> >  	}
> >        else
> > -	compute_known_type_jump_func (arg, &functions[num]);
> > +	compute_known_type_jump_func (arg, &functions[num], call);
> >      }
> >  }
> >  
> > @@ -1218,6 +1371,7 @@ ipa_analyze_virtual_call_uses (struct cg
> >  			       struct ipa_node_params *info, gimple call,
> >  			       tree target)
> >  {
> > +  struct ipa_jump_func jfunc;
> >    tree obj = OBJ_TYPE_REF_OBJECT (target);
> >    tree var;
> >    int index;
> > @@ -1241,7 +1395,8 @@ ipa_analyze_virtual_call_uses (struct cg
> >    var = SSA_NAME_VAR (obj);
> >    index = ipa_get_param_decl_index (info, var);
> >  
> > -  if (index >= 0)
> > +  if (index >= 0
> > +      && !detect_type_change_ssa (obj, call, &jfunc))
> >      ipa_note_param_call (node, index, call, true);
> >  }
> >  
> > @@ -1364,6 +1519,8 @@ ipa_analyze_node (struct cgraph_node *no
> >    struct param_analysis_info *parms_info;
> >    int i, param_count;
> >  
> > +  push_cfun (DECL_STRUCT_FUNCTION (node->decl));
> > +  current_function_decl = node->decl;
> >    ipa_initialize_node_params (node);
> >  
> >    param_count = ipa_get_param_count (info);
> > @@ -1376,6 +1533,9 @@ ipa_analyze_node (struct cgraph_node *no
> >    for (i = 0; i < param_count; i++)
> >      if (parms_info[i].visited_statements)
> >        BITMAP_FREE (parms_info[i].visited_statements);
> > +
> > +  current_function_decl = NULL;
> > +  pop_cfun ();
> >  }
> >  
> >  
> > Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
> > ===================================================================
> > --- /dev/null
> > +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
> > @@ -0,0 +1,71 @@
> > +/* Verify that ipa-cp correctly detects the dynamic type of an object
> > +   under construction when doing devirtualization.  */
> > +/* { dg-do run } */
> > +/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
> > +
> > +extern "C" void abort (void);
> > +
> > +class A
> > +{
> > +public:
> > +  int data;
> > +  A();
> > +  virtual int foo (int i);
> > +};
> > +
> > +class B : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +class C : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +int A::foo (int i)
> > +{
> > +  return i + 1;
> > +}
> > +
> > +int B::foo (int i)
> > +{
> > +  return i + 2;
> > +}
> > +
> > +int C::foo (int i)
> > +{
> > +  return i + 3;
> > +}
> > +
> > +static int middleman (class A *obj, int i)
> > +{
> > +  return obj->foo (i);
> > +}
> > +
> > +int __attribute__ ((noinline,noclone)) get_input(void)
> > +{
> > +  return 1;
> > +}
> > +
> > +A::A ()
> > +{
> > +  if (middleman (this, get_input ()) != 2)
> > +    abort ();
> > +}
> > +
> > +static void bah ()
> > +{
> > +  class B b;
> > +}
> > +
> > +int main (int argc, char *argv[])
> > +{
> > +  int i;
> > +
> > +  for (i = 0; i < 10; i++)
> > +    bah ();
> > +  return 0;
> > +}
> > Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
> > ===================================================================
> > --- /dev/null
> > +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
> > @@ -0,0 +1,79 @@
> > +/* Verify that ipa-cp correctly detects the dynamic type of an object
> > +   under construction when doing devirtualization.  */
> > +/* { dg-do run } */
> > +/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
> > +
> > +extern "C" void abort (void);
> > +
> > +class Distraction
> > +{
> > +public:
> > +  float f;
> > +  double d;
> > +  Distraction ()
> > +  {
> > +    f = 8.3;
> > +    d = 10.2;
> > +  }
> > +  virtual float bar (float z);
> > +};
> > +
> > +class A
> > +{
> > +public:
> > +  int data;
> > +  A();
> > +  virtual int foo (int i);
> > +};
> > +
> > +class B : public Distraction, public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +float Distraction::bar (float z)
> > +{
> > +  f += z;
> > +  return f/2;
> > +}
> > +
> > +int A::foo (int i)
> > +{
> > +  return i + 1;
> > +}
> > +
> > +int B::foo (int i)
> > +{
> > +  return i + 2;
> > +}
> > +
> > +int __attribute__ ((noinline,noclone)) get_input(void)
> > +{
> > +  return 1;
> > +}
> > +
> > +static int middleman (class A *obj, int i)
> > +{
> > +  return obj->foo (i);
> > +}
> > +
> > +A::A()
> > +{
> > +  if (middleman (this, get_input ()) != 2)
> > +    abort ();
> > +}
> > +
> > +static void bah ()
> > +{
> > +  class B b;
> > +}
> > +
> > +int main (int argc, char *argv[])
> > +{
> > +  int i;
> > +
> > +  for (i = 0; i < 10; i++)
> > +    bah ();
> > +  return 0;
> > +}
> > Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-3.C
> > ===================================================================
> > --- /dev/null
> > +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-3.C
> > @@ -0,0 +1,80 @@
> > +/* Verify that ipa-cp correctly detects the dynamic type of an object
> > +   under construction when doing devirtualization.  */
> > +/* { dg-do run } */
> > +/* { dg-options "-O3 -fno-inline"  } */
> > +
> > +extern "C" void abort (void);
> > +
> > +class Distraction
> > +{
> > +public:
> > +  float f;
> > +  double d;
> > +  Distraction ()
> > +  {
> > +    f = 8.3;
> > +    d = 10.2;
> > +  }
> > +  virtual float bar (float z);
> > +};
> > +
> > +class A
> > +{
> > +public:
> > +  int data;
> > +  A();
> > +  virtual int foo (int i);
> > +};
> > +
> > +class B : public Distraction, public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +float Distraction::bar (float z)
> > +{
> > +  f += z;
> > +  return f/2;
> > +}
> > +
> > +int A::foo (int i)
> > +{
> > +  return i + 1;
> > +}
> > +
> > +int B::foo (int i)
> > +{
> > +  return i + 2;
> > +}
> > +
> > +int __attribute__ ((noinline,noclone)) get_input(void)
> > +{
> > +  return 1;
> > +}
> > +
> > +static int __attribute__ ((noinline))
> > +middleman (class A *obj, int i)
> > +{
> > +  return obj->foo (i);
> > +}
> > +
> > +inline __attribute__ ((always_inline)) A::A()
> > +{
> > +  if (middleman (this, get_input ()) != 2)
> > +    abort ();
> > +}
> > +
> > +static void bah ()
> > +{
> > +  class B b;
> > +}
> > +
> > +int main (int argc, char *argv[])
> > +{
> > +  int i;
> > +
> > +  for (i = 0; i < 10; i++)
> > +    bah ();
> > +  return 0;
> > +}
> > Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-4.C
> > ===================================================================
> > --- /dev/null
> > +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-4.C
> > @@ -0,0 +1,110 @@
> > +/* Verify that ipa-cp correctly detects the dynamic type of an object
> > +   under construction when doing devirtualization.  */
> > +/* { dg-do run } */
> > +/* { dg-options "-O3 -fno-inline"  } */
> > +
> > +extern "C" void abort (void);
> > +
> > +class Distraction
> > +{
> > +public:
> > +  float f;
> > +  double d;
> > +  Distraction ()
> > +  {
> > +    f = 8.3;
> > +    d = 10.2;
> > +  }
> > +  virtual float bar (float z);
> > +};
> > +
> > +class A
> > +{
> > +public:
> > +  int data;
> > +  A();
> > +  virtual int foo (int i);
> > +};
> > +
> > +class B : public Distraction, public A
> > +{
> > +public:
> > +  B();
> > +  virtual int foo (int i);
> > +};
> > +
> > +class C : public B
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +
> > +float Distraction::bar (float z)
> > +{
> > +  f += z;
> > +  return f/2;
> > +}
> > +
> > +int A::foo (int i)
> > +{
> > +  return i + 1;
> > +}
> > +
> > +int B::foo (int i)
> > +{
> > +  return i + 2;
> > +}
> > +
> > +int C::foo (int i)
> > +{
> > +  return i + 3;
> > +}
> > +
> > +int __attribute__ ((noinline,noclone)) get_input(void)
> > +{
> > +  return 1;
> > +}
> > +
> > +static int __attribute__ ((noinline))
> > +middleman (class A *obj, int i)
> > +{
> > +  return obj->foo (i);
> > +}
> > +
> > +static void __attribute__ ((noinline))
> > +sth2 (A *a)
> > +{
> > +  if (a->foo (get_input ()) != 3)
> > +    abort ();
> > +}
> > +
> > +inline void __attribute__ ((always_inline)) sth1 (B *b)
> > +{
> > +  sth2 (b);
> > +}
> > +
> > +inline __attribute__ ((always_inline)) A::A()
> > +{
> > +  if (middleman (this, get_input ()) != 2)
> > +    abort ();
> > +}
> > +
> > +B::B() : Distraction(), A()
> > +{
> > +  sth1 (this);
> > +}
> > +
> > +static void bah ()
> > +{
> > +  class C c;
> > +}
> > +
> > +int main (int argc, char *argv[])
> > +{
> > +  int i;
> > +
> > +  for (i = 0; i < 10; i++)
> > +    bah ();
> > +  return 0;
> > +}
> > Index: icln/gcc/testsuite/g++.dg/ipa/devirt-d-1.C
> > ===================================================================
> > --- /dev/null
> > +++ icln/gcc/testsuite/g++.dg/ipa/devirt-d-1.C
> > @@ -0,0 +1,71 @@
> > +/* Verify that ipa-cp correctly detects the dynamic type of an object
> > +   under destruction when doing devirtualization.  */
> > +/* { dg-do run } */
> > +/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
> > +
> > +extern "C" void abort (void);
> > +
> > +class A
> > +{
> > +public:
> > +  int data;
> > +  ~A();
> > +  virtual int foo (int i);
> > +};
> > +
> > +class B : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +class C : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +int A::foo (int i)
> > +{
> > +  return i + 1;
> > +}
> > +
> > +int B::foo (int i)
> > +{
> > +  return i + 2;
> > +}
> > +
> > +int C::foo (int i)
> > +{
> > +  return i + 3;
> > +}
> > +
> > +static int middleman (class A *obj, int i)
> > +{
> > +  return obj->foo (i);
> > +}
> > +
> > +int __attribute__ ((noinline,noclone)) get_input(void)
> > +{
> > +  return 1;
> > +}
> > +
> > +A::~A ()
> > +{
> > +  if (middleman (this, get_input ()) != 2)
> > +    abort ();
> > +}
> > +
> > +static void bah ()
> > +{
> > +  class B b;
> > +}
> > +
> > +int main (int argc, char *argv[])
> > +{
> > +  int i;
> > +
> > +  for (i = 0; i < 10; i++)
> > +    bah ();
> > +  return 0;
> > +}
> > Index: icln/gcc/testsuite/g++.dg/torture/pr45934.C
> > ===================================================================
> > --- /dev/null
> > +++ icln/gcc/testsuite/g++.dg/torture/pr45934.C
> > @@ -0,0 +1,23 @@
> > +/* { dg-do run } */
> > +
> > +extern "C" void abort ();
> > +
> > +struct B *b;
> > +
> > +struct B
> > +{
> > +  virtual void f () { }
> > +  ~B() { b->f(); }
> > +};
> > +
> > +struct D : public B
> > +{
> > +  virtual void f () { abort (); }
> > +};
> > +
> > +int main ()
> > +{
> > +  D d;
> > +  b = &d;
> > +  return 0;
> > +}
> > Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-5.C
> > ===================================================================
> > --- /dev/null
> > +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-5.C
> > @@ -0,0 +1,79 @@
> > +/* Verify that ipa-cp correctly detects the dynamic type of an object
> > +   under construction when doing devirtualization.  */
> > +/* { dg-do run } */
> > +/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
> > +
> > +extern "C" void abort (void);
> > +
> > +class B;
> > +
> > +class A
> > +{
> > +public:
> > +  int data;
> > +  A();
> > +  A(B *b);
> > +  virtual int foo (int i);
> > +};
> > +
> > +class B : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +class C : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +int A::foo (int i)
> > +{
> > +  return i + 1;
> > +}
> > +
> > +int B::foo (int i)
> > +{
> > +  return i + 2;
> > +}
> > +
> > +int C::foo (int i)
> > +{
> > +  return i + 3;
> > +}
> > +
> > +static int middleman (class A *obj, int i)
> > +{
> > +  return obj->foo (i);
> > +}
> > +
> > +int __attribute__ ((noinline,noclone)) get_input(void)
> > +{
> > +  return 1;
> > +}
> > +
> > +A::A ()
> > +{
> > +}
> > +
> > +A::A (B *b)
> > +{
> > +  if (middleman (b, get_input ()) != 3)
> > +    abort ();
> > +}
> > +
> > +static void bah ()
> > +{
> > +  B b;
> > +  A a(&b);
> > +}
> > +
> > +int main (int argc, char *argv[])
> > +{
> > +  int i;
> > +
> > +  for (i = 0; i < 10; i++)
> > +    bah ();
> > +  return 0;
> > +}
> > Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-6.C
> > ===================================================================
> > --- /dev/null
> > +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-6.C
> > @@ -0,0 +1,72 @@
> > +/* Verify that ipa-cp correctly detects the dynamic type of an object
> > +   under construction when doing devirtualization.  */
> > +/* { dg-do run } */
> > +/* { dg-options "-O3 -fno-inline"  } */
> > +
> > +extern "C" void abort (void);
> > +
> > +class A
> > +{
> > +public:
> > +  int data;
> > +  A();
> > +  virtual int foo (int i);
> > +};
> > +
> > +class B : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +class C : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +int A::foo (int i)
> > +{
> > +  return i + 1;
> > +}
> > +
> > +int B::foo (int i)
> > +{
> > +  return i + 2;
> > +}
> > +
> > +int C::foo (int i)
> > +{
> > +  return i + 3;
> > +}
> > +
> > +static inline int __attribute__ ((always_inline))
> > +middleman (class A *obj, int i)
> > +{
> > +  return obj->foo (i);
> > +}
> > +
> > +int __attribute__ ((noinline,noclone)) get_input(void)
> > +{
> > +  return 1;
> > +}
> > +
> > +__attribute__ ((noinline)) A::A ()
> > +{
> > +  if (middleman (this, get_input ()) != 2)
> > +    abort ();
> > +}
> > +
> > +static void bah ()
> > +{
> > +  class B b;
> > +}
> > +
> > +int main (int argc, char *argv[])
> > +{
> > +  int i;
> > +
> > +  for (i = 0; i < 10; i++)
> > +    bah ();
> > +  return 0;
> > +}
> > Index: icln/gcc/testsuite/g++.dg/ipa/devirt-c-7.C
> > ===================================================================
> > --- /dev/null
> > +++ icln/gcc/testsuite/g++.dg/ipa/devirt-c-7.C
> > @@ -0,0 +1,101 @@
> > +/* Verify that ipa-cp can use TBAA to fingure out that the virtual call to
> > +   D::foo is not affected by dynamic type change in constructor A::A(D*).  */
> > +
> > +/* { dg-do run } */
> > +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp"  } */
> > +
> > +extern "C" void abort (void);
> > +
> > +class D;
> > +
> > +class A
> > +{
> > +public:
> > +  int data;
> > +  A();
> > +  A(D *d);
> > +  virtual int foo (int i);
> > +};
> > +
> > +class B : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +class C : public A
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +class D
> > +{
> > +public:
> > +  virtual int foo (int i);
> > +};
> > +
> > +int A::foo (int i)
> > +{
> > +  return i + 1;
> > +}
> > +
> > +int B::foo (int i)
> > +{
> > +  return i + 2;
> > +}
> > +
> > +int C::foo (int i)
> > +{
> > +  return i + 3;
> > +}
> > +
> > +int D::foo (int i)
> > +{
> > +  return i + 4;
> > +}
> > +
> > +static int middleman (class A *obj, int i)
> > +{
> > +  return obj->foo (i);
> > +}
> > +
> > +static int middleman (class D *obj, int i)
> > +{
> > +  return obj->foo (i);
> > +}
> > +
> > +int __attribute__ ((noinline,noclone)) get_input(void)
> > +{
> > +  return 1;
> > +}
> > +
> > +A::A ()
> > +{
> > +}
> > +
> > +A::A (D *d)
> > +{
> > +  if (middleman (d, get_input ()) != 5)
> > +    abort ();
> > +  if (middleman (this, get_input ()) != 2)
> > +    abort ();
> > +}
> > +
> > +static void bah ()
> > +{
> > +  D d;
> > +  A a(&d);
> > +}
> > +
> > +int main (int argc, char *argv[])
> > +{
> > +  int i;
> > +
> > +  for (i = 0; i < 10; i++)
> > +    bah ();
> > +  return 0;
> > +}
> > +
> > +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*D::foo"  "cp"  } } */
> > +/* { dg-final { cleanup-ipa-dump "cp" } } */
> > 
> > 
> 
> -- 
> Richard Guenther <rguenther@suse.de>
> Novell / SUSE Labs
> SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex

On Thu, 13 Jan 2011, Martin Jambor wrote:

> Hi,
> 
> On Thu, Jan 13, 2011 at 12:56:24PM +0100, Richard Guenther wrote:
> > On Wed, 15 Dec 2010, Martin Jambor wrote:
> > 
> > 
> > I'm commenting in the plain text below, not in the patch.
> > 
> > > ----------------------------------------------------------------------
> > > 
> > > /* Structure to be passed in between detect_type_change and
> > >    check_stmt_for_type_change.  */
> > > 
> > > struct type_change_info
> > > {
> > >   /* The declaration or SSA_NAME pointer of the base that we are checking for
> > >      type change.  */
> > >   tree object;
> > >   /* If we actually can tell the type that the object has changed to, it is
> > >      stored in this field.  Otherwise it remains NULL_TREE.  */
> > >   tree known_current_type;
> > >   /* Set to true if dynamic type change has been detected.  */
> > >   bool type_maybe_changed;
> > >   /* Set to true if multiple types have been encountered.  known_current_type
> > >      must be disregarded in that case.  */
> > >   bool multiple_types_encountered;
> > > };
> > > 
> > > /* Return true if STMT can modify a virtual method table pointer.
> > > 
> > >    This function makes special assumptions about both constructors and
> > >    destructors which are all the functions that are allowed to alter the VMT
> > >    pointers.  It assumes that destructors begin with assignment into all VMT
> > >    pointers and that constructors essentially look in the following way:
> > > 
> > >    1) The very first thing they do is that they call constructors of ancestor
> > >    sub-objects that have them.
> > > 
> > >    2) Then VMT pointers of this and all its ancestors is set to new values
> > >    corresponding to the type corresponding to the constructor.
> > > 
> > >    3) Only afterwards, other stuff such as constructor of member sub-objects
> > >    and the code written by the user is run.  Only this may include calling
> > >    virtual functions, directly or indirectly.
> > > 
> > >    There is no way to call a constructor of an ancestor sub-object in any
> > >    other way.
> > > 
> > >    This means that we do not have to care whether constructors get the correct
> > >    type information because they will always change it (in fact, if we define
> > >    the type to be given by the VMT pointer, it is undefined).
> > > 
> > >    The most important fact to derive from the above is that if, for some
> > >    statement in the section 3, we try to detect whether the dynamic type has
> > >    changed, we can safely ignore all calls as we examine the function body
> > >    backwards until we reach statements in section 2 because these calls cannot
> > >    be ancestor constructors or destructors (if the input is not bogus) and so
> > >    do not change the dynamic type.  We then must detect that statements in
> > >    section 2 change the dynamic type and can try to derive the new type.  That
> > >    is enough and we can stop, we will never see the calls into constructors of
> > >    sub-objects in this code.  Therefore we can safely ignore all call
> > >    statements that we traverse.
> > >   */
> > >
> > > static bool
> > > stmt_may_be_vtbl_ptr_store (gimple stmt)
> > > {
> > >   if (is_gimple_call (stmt))
> > >     return false;
> > >   else if (is_gimple_assign (stmt))
> > >     {
> > >       tree lhs = gimple_assign_lhs (stmt);
> > > 
> > >       if (TREE_CODE (lhs) == COMPONENT_REF
> > > 	  && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
> > > 	  && !AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
> > > 	    return false;
> > >       /* In the future we might want to use get_base_ref_and_offset to find
> > > 	 if there is a field corresponding to the offset and if so, proceed
> > > 	 almost like if it was a component ref.  */
> > >     }
> > >   return true;
> > > }
> > 
> > Hm.  Does this address
> > 
> > extern "C" void abort (void);
> > extern "C" void *malloc(__SIZE_TYPE__);
> > inline void* operator new(__SIZE_TYPE__, void* __p) throw() { return __p;
> > }
> > int x;
> > class A {
> > public:
> >    virtual ~A() { }
> > };
> > class B : public A {
> > public:
> >    virtual ~B() { if (x == 1) abort (); x = 1; }
> > };
> > void __attribute__((noinline,noclone)) foo (void *p)
> > {
> >  B *b = reinterpret_cast<B *>(p);
> >  b->~B();
> >  new (p) A;
> > }
> > int main()
> > {
> >  void *p = __builtin_malloc (sizeof (B));
> >  new (p) B;
> >  foo(p);
> >  reinterpret_cast<A *>(p)->~A();
> >  return 0;
> > }
> > 
> > where we have a call (foo) that changes the dynamic type of *p?
> > 
> > Or is this a non-issue with the current patch because we only
> > ever devirtualize calls when we eventually see a statically
> > allocated object?  Can you still add the above testcase please?
> > Can you add a comment to the above function that ignoring
> > calls is not possible if we start to devirtualize for
> > allocated objects?  Or rather, mention that we only deal
> > with statically allocated objects?
> 
> Exactly.  I've added the above as another testcase and added a comment
> saying that we only care for automatically allocated objects at this
> point.
> 
> > 
> > You said you could make a failing testcase out of the
> > array testcase sketch - I can't see if that is included in
> > the set of testcases you add.  Is it?
> 
> It is the last one in the third patch in the series.
> 
> > 
> > > /* If STMT can be proved to be an assignment to the virtual method table
> > >    pointer of ANALYZED_OBJ and the type associated witht the new table
> > >    identified, return the type.  Otherwise return NULL_TREE.  */
> > > 
> > > static tree
> > > extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj)
> > > {
> > >   tree lhs, t, obj;
> > > 
> > >   if (!is_gimple_assign (stmt))
> > >     return NULL_TREE;
> > > 
> > >   lhs = gimple_assign_lhs (stmt);
> > > 
> > >   if (TREE_CODE (lhs) != COMPONENT_REF)
> > >     return NULL_TREE;
> > >    obj = lhs;
> > > 
> > >    if (!DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
> > >      return NULL_TREE;
> > > 
> > >    do
> > >      {
> > >        obj = TREE_OPERAND (obj, 0);
> > >      }
> > >    while (TREE_CODE (obj) == COMPONENT_REF);
> > >    if (TREE_CODE (obj) == MEM_REF)
> > >      obj = TREE_OPERAND (obj, 0);
> > >    if (TREE_CODE (obj) == ADDR_EXPR)
> > >      obj = TREE_OPERAND (obj, 0);
> > >    if (obj != analyzed_obj)
> > >      return NULL_TREE;
> > > 
> > >    t = gimple_assign_rhs1 (stmt);
> > >    if (TREE_CODE (t) != ADDR_EXPR)
> > >      return NULL_TREE;
> > >    t = get_base_address (TREE_OPERAND (t, 0));
> > >    if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t))
> > >      return NULL_TREE;
> > > 
> > >    return DECL_CONTEXT (t);
> > > }
> > > 
> > > /* Callbeck of walk_aliased_vdefs and a helper function for
> > >    detect_type_change to check whether a particular statement may modify
> > >    the virtual table pointer, and if possible also determine the new type of
> > >    the (sub-)object.  It stores its result into DATA, which points to a
> > >    type_change_info structure.  */
> > > 
> > > static bool
> > > check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
> > > {
> > >   gimple stmt = SSA_NAME_DEF_STMT (vdef);
> > >   struct type_change_info *tci = (struct type_change_info *) data;
> > > 
> > >   if (stmt_may_be_vtbl_ptr_store (stmt))
> > >     {
> > >       tree type;
> > >       type = extr_type_from_vtbl_ptr_store (stmt, tci->object);
> > >       if (tci->type_maybe_changed
> > > 	  && type != tci->known_current_type)
> > > 	tci->multiple_types_encountered = true;
> > >       tci->known_current_type = type;
> > >       tci->type_maybe_changed = true;
> > >       return true;
> > >     }
> > >   else
> > >     return false;
> > > }
> > > 
> > > /* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
> > >    looking for assignments to its virtual table pointer.  If it is, return true
> > >    and fill in the jump function JFUNC with relevant type information or set it
> > >    to unknown.  ARG is the object itself (not a pointer to it, unless
> > >    dereferenced).  BASE is the base of the memory access as returned by
> > >    get_ref_base_and_extent, as is the offset.  */
> > > 
> > > static bool
> > > detect_type_change (tree arg, tree base, gimple call,
> > > 		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
> > > {
> > >   struct type_change_info tci;
> > >   tree type;
> > >   ao_ref ao;
> > > 
> > >   gcc_checking_assert (DECL_P (arg)
> > > 		       || TREE_CODE (arg) == MEM_REF
> > > 		       || handled_component_p (arg));
> > >   /* Const calls cannot call virtual methods through VMT and so type changes do
> > >      not matter.  */
> > 
> > But as there won't be calls we are interested in in the callee why do
> > we end up here at all?  Well, I guess this can be cleaned up in
> > a followup.
> 
> The call here represents the point at which we need to figure out
> whether the type has changed, not the calls we skip when walking.  We
> take the virtual SSA name from it.  If we can, that is.  The comment
> just states that if we cannot, it does not matter since the function
> does not use memory including any VMTs.
> 
> > 
> > >   if (!gimple_vuse (call))
> > >     return false;
> > > 
> > >   ao.ref = arg;
> > >   ao.base = base;
> > >   ao.offset = offset;
> > >   ao.size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ptr_type_node)) * BITS_PER_UNIT;
> > 
> > POINTER_SIZE
> 
> OK
> 
> > 
> > >   ao.max_size = ao.size;
> > >   ao.ref_alias_set = -1;
> > >   ao.base_alias_set = -1;
> > > 
> > >   type = TREE_TYPE (arg);
> > >   while (handled_component_p (arg))
> > >     arg = TREE_OPERAND (arg, 0);
> > >   if (TREE_CODE (arg) == MEM_REF)
> > >     arg = TREE_OPERAND (arg, 0);
> > >   if (TREE_CODE (arg) == ADDR_EXPR)
> > >     arg = TREE_OPERAND (arg, 0);
> > >   tci.object = arg;
> > >   tci.known_current_type = NULL_TREE;
> > >   tci.type_maybe_changed = false;
> > >   tci.multiple_types_encountered = false;
> > > 
> > >   walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
> > > 		      &tci, NULL);
> > >   if (!tci.type_maybe_changed)
> > >     return false;
> > > 
> > >  if (!tci.known_current_type || tci.multiple_types_encountered)
> > >    jfunc->type = IPA_JF_UNKNOWN;
> > >  else
> > >    {
> > >      tree new_binfo = get_binfo_at_offset (TYPE_BINFO (tci.known_current_type),
> > > 					   offset, type);
> > >      if (new_binfo)
> > > 	{
> > > 	  jfunc->type = IPA_JF_KNOWN_TYPE;
> > > 	  jfunc->value.base_binfo = new_binfo;
> > > 	}
> > >      else
> > >        jfunc->type = IPA_JF_UNKNOWN;
> > >    }
> > > 
> > >   return true;
> > > }
> > > 
> > > /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
> > >    SSA name (its dereference will become the base and the offset is assumed to
> > >    be zero).  */
> > > 
> > > static bool
> > > detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
> > > {
> > >   gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
> > >   if (!POINTER_TYPE_P (TREE_TYPE (arg))
> > >       || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
> > >     return false;
> > > 
> > >   arg = build_simple_mem_ref (arg);
> > 
> > This still yields to wrong TBAA disambiguations.  I suggest you
> > pass a flag to detect_type_change and drop back to basic tbaa:
> > 
> >   ao.base_alias_set = get_alias_set (ptr_type_node);
> >   ao.ref_alias_set = get_alias_set (ptr_type_node);
> > 
> > (you could do the ref_alias_set initialization unconditionally
> > and the base_alias_set one if the call is from detect_type_change_ssa
> > in which case you should leave ao.ref as NULL_TREE.  Basically
> > do a ao_ref_init_from_ptr_and_size but provide some TBAA
> > information).  Or you can simply do
> > 
> >   arg = build2 (MEM_REF, ptr_type_node, arg,
> > 	        build_int_cst (ptr_type_node, 0));
> 
> I did the above and the testcase devirt-c-7.C below started to fail.
> Maybe I ask too much from the TBAA.  My idea was that objects with
> virtual methods should only be accessed with their or their ancestors'
> types and so decided to rely on the provided pointer type.
> 
> Nevertheless, at the moment I decided to simply remove the testcase
> and keep it aside until I have a better idea of how much this matters
> in practice.  Maybe I'll revisit this in the future.
> 
> > 
> > which will magically do the same things.
> > 
> > I think I have reviewed patch 3/5 with the above as well as far
> > as I can see.
> 
> Yes.
> 
> > 
> > Iff we indeed only deal with statically allocated objects patch 2/5
> > is ok with the minor adjustments I requested and the TBAA issue
> > fixed for detect_type_change_ssa.
> 
> And the 3/5?

Yes, including 3/5.

> I am now in the process of doing the final touches and re-testing this
> and the two subsequent patches and would like to commit it (them?)
> tomorrow.

Thanks,
Richard.