[PR,45934,4/6] Dynamic type change detection

This is the crux of the matter.  I'll try to explain what and why I do
in order to detect sub-object type changes during their construction
first, below it there is the detection code as it looks like with the
next patch applied and then there is of course the patch at the end.

I have split the detection code into two patches, this one just
detects that there is a type change in force and the subsequent one
also tries to derive the new type.  I did this in order to better
structure the discussion about both and I also intend to commit the
separately, easing potential bisecting (I hope there will be no reason
for that of course).  If it was absolutely necessary, we could
postpone the next patch for stage1 but I hope to commit a variant of
it soon.

Because operations like placement new, memcpy and other byte-per-byte
operations with objects that have virtual methods are deemed to
produce code with undefined behavior and there are no unions of
non-POD types, dynamic type change has a special meaning for
devirtualization and only refers to what actual virtual method table a
VMT pointer of an object points to.  On the other hand the type in the
sense of what you get from TREE_TYPE of the base of any given access
to it is still the same and it is its static type.  An important
property of such objects is that their dynamic types (as given by the
current VMT) can only be altered in constructors and destructors.

This patch makes special assumptions about both constructors and
destructors which are all the functions that are allowed to alter the
dynamic types.  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 the
   components (including 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 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 (or any component for that matter but type is interesting
only for ancestors).

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 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,
possibly except builtins which we consider as changing the type in an
unknown way and which previous optimization passes might have
introduced.

Constructors of ancestors may be early inlined but that does not
change the above division.  Function splitting may lead to inlining of
only a portion of a constructor but it can only inline the beginning
of the constructor, not some part in the middle and so the division
again holds.  Moreover, the inlined portion will essentially be
divided into three such sections too (perhaps some of the latter ones
in another function which means that the type we pass to it either
does not matter or is known) and therefore the same arguments will
also hold for the associated sub-object.

Exceptions can change this flow and lead to invocations of destructors
of the completely constructed sub-objects in places where the method
based on examining all possible previous statements might fail.
However, because destructors begin with assignment to all VMT
pointers, the type information passed to them is never used anyway.
Apart from the destructors, user code cannot handle exceptions that
escape an ancestor constructor in any of the constructors of the
descendants and so we will never encounter calls to other functions in
these areas.

Therefore we do the following.  Whenever we are about to construct a
jump function that carries type information (known_type, ancestor or
pass_through) or note that a virtual call is based on the type of a
parameter, we invoke a function to check whether the dynamic type has
changed and see whether we can deduce the new type.  This function
traverses VDEFs from the call site and examines individual statements
and their potential or known effect on the VMT pointers in question.

When we do this, we employ the TBAA disambiguation using the static
type of the (sub-)object for reasons stated above when defining what
we mean by dynamic type change.  I believe we can even use types
derived from pointers because of what conversions are allowed by the
C++ standard.

When examining the statements, we default to assume VMT pointers are
changed in unpredictable ways.  There are, however, two exceptions.
The first are calls to non-builtins which we consider harmless for the
reasons above.  The second one are assignments to COMPONENT_REFs where
we check whether the FIELD_DECL has the virtual flag set or not.  If
it is not set, we assume this is not a store to the VMT pointer.  In
the future, we might want to add more such cases (like ignoring
ARRAY_REFs too, for example) but so far I am happy with the two.

If the assignment is a COMPONENT_REF to a field with the virtual flag
set and the base is the same decl or SSA name as the object we are
examining, we try to deduce the new type from the right hand side.

Tho 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_anc 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;
};

/* Return true if STMT can modify a virtual method table pointer.  The function
   assumes it will never be called on constructor or destructor calls (since
   the search for dynamic type change will always end before reaching the
   former and lifetime of the object is over anyway after the latter.  */

static bool
stmt_may_be_vtbl_ptr_store (gimple stmt)
{
  if (is_gimple_call (stmt))
    {
      tree fndecl = gimple_call_fndecl (stmt);
      if (!fndecl || !DECL_BUILT_IN (fndecl))
	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)))
	    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_anc 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;
      tci->known_current_type = extr_type_from_vtbl_ptr_store (stmt,
							       tci->object);
      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.  If
   ANC_OFFSET is non-zero, look for binfo of its ancestor of that type at that
   offset.  ARG is supposed to be a dereferenced pointer or a declaration or a
   series of component_refs of either.  */

static bool
detect_type_change_anc (tree arg, gimple call, struct ipa_jump_func *jfunc,
			HOST_WIDE_INT anc_offset)
{
  struct type_change_info tci;
  tree obj;
  ao_ref ar;

  /* Const calls cannot call virtual methods through VMT and so type changes do
     not matter.  */
  if (!gimple_vuse (call))
    return false;

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

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

  if (!tci.known_current_type)
    jfunc->type = IPA_JF_UNKNOWN;
  else if (anc_offset != 0)
    {
      tree new_binfo = get_binfo_at_offset (TYPE_BINFO (tci.known_current_type),
					    anc_offset, TREE_TYPE (arg));

      if (new_binfo)
	{
	  jfunc->type = IPA_JF_KNOWN_TYPE;
	  jfunc->value.base_binfo = new_binfo;
	}
      else
	jfunc->type = IPA_JF_UNKNOWN;
    }
  else
    {
      /* If an offset of a searched-for sub-object actually happens to be zero,
	 we do not have to worry about non-artificialness.  Either there are no
	 virtual methods anyway or there is a VMT pointer at offset zero and so
	 artificial sub-objects start at higher offsets.  */
      jfunc->type = IPA_JF_KNOWN_TYPE;
      jfunc->value.base_binfo = TYPE_BINFO (tci.known_current_type);
    }

  return true;
}

/* Like detect_type_change_anc but ARG is supposed to be a non-dereferenced
   pointer SSA name.  */

static bool
detect_type_change (tree arg, gimple call, struct ipa_jump_func *jfunc)
{
  if (!POINTER_TYPE_P (TREE_TYPE (arg))
      || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
    return false;
  gcc_checking_assert (TREE_CODE (arg) != ADDR_EXPR);
  arg = build_simple_mem_ref (arg);
  /* Building a MEM_REF just for the sake of ao_ref_init is probably
  wasteful here, I'll be happy to discuss alternatives.  */

  return detect_type_change_anc (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-29  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_1): Likewise.
	(detect_type_change): 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.

	* 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-d-1.C: Likewise.
	* testsuite/g++.dg/torture/pr45934.C: Likewise.

On Wed, 1 Dec 2010, Martin Jambor wrote:

> This is the crux of the matter.  I'll try to explain what and why I do
> in order to detect sub-object type changes during their construction
> first, below it there is the detection code as it looks like with the
> next patch applied and then there is of course the patch at the end.
> 
> I have split the detection code into two patches, this one just
> detects that there is a type change in force and the subsequent one
> also tries to derive the new type.  I did this in order to better
> structure the discussion about both and I also intend to commit the
> separately, easing potential bisecting (I hope there will be no reason
> for that of course).  If it was absolutely necessary, we could
> postpone the next patch for stage1 but I hope to commit a variant of
> it soon.
> 
> Because operations like placement new, memcpy and other byte-per-byte
> operations with objects that have virtual methods are deemed to
> produce code with undefined behavior and there are no unions of
> non-POD types, dynamic type change has a special meaning for
> devirtualization and only refers to what actual virtual method table a
> VMT pointer of an object points to.  On the other hand the type in the
> sense of what you get from TREE_TYPE of the base of any given access
> to it is still the same and it is its static type.  An important
> property of such objects is that their dynamic types (as given by the
> current VMT) can only be altered in constructors and destructors.
> 
> This patch makes special assumptions about both constructors and
> destructors which are all the functions that are allowed to alter the
> dynamic types.  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 the
>    components (including 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 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 (or any component for that matter but type is interesting
> only for ancestors).
> 
> 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 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,
> possibly except builtins which we consider as changing the type in an
> unknown way and which previous optimization passes might have
> introduced.
> 
> Constructors of ancestors may be early inlined but that does not
> change the above division.  Function splitting may lead to inlining of
> only a portion of a constructor but it can only inline the beginning
> of the constructor, not some part in the middle and so the division
> again holds.  Moreover, the inlined portion will essentially be
> divided into three such sections too (perhaps some of the latter ones
> in another function which means that the type we pass to it either
> does not matter or is known) and therefore the same arguments will
> also hold for the associated sub-object.
> 
> Exceptions can change this flow and lead to invocations of destructors
> of the completely constructed sub-objects in places where the method
> based on examining all possible previous statements might fail.
> However, because destructors begin with assignment to all VMT
> pointers, the type information passed to them is never used anyway.
> Apart from the destructors, user code cannot handle exceptions that
> escape an ancestor constructor in any of the constructors of the
> descendants and so we will never encounter calls to other functions in
> these areas.
> 
> Therefore we do the following.  Whenever we are about to construct a
> jump function that carries type information (known_type, ancestor or
> pass_through) or note that a virtual call is based on the type of a
> parameter, we invoke a function to check whether the dynamic type has
> changed and see whether we can deduce the new type.  This function
> traverses VDEFs from the call site and examines individual statements
> and their potential or known effect on the VMT pointers in question.
> 
> When we do this, we employ the TBAA disambiguation using the static
> type of the (sub-)object for reasons stated above when defining what
> we mean by dynamic type change.  I believe we can even use types
> derived from pointers because of what conversions are allowed by the
> C++ standard.
> 
> When examining the statements, we default to assume VMT pointers are
> changed in unpredictable ways.  There are, however, two exceptions.
> The first are calls to non-builtins which we consider harmless for the
> reasons above.  The second one are assignments to COMPONENT_REFs where
> we check whether the FIELD_DECL has the virtual flag set or not.  If
> it is not set, we assume this is not a store to the VMT pointer.  In
> the future, we might want to add more such cases (like ignoring
> ARRAY_REFs too, for example) but so far I am happy with the two.
> 
> If the assignment is a COMPONENT_REF to a field with the virtual flag
> set and the base is the same decl or SSA name as the object we are
> examining, we try to deduce the new type from the right hand side.
> 
> Tho 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_anc 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;
> };
> 
> /* Return true if STMT can modify a virtual method table pointer.  The function
>    assumes it will never be called on constructor or destructor calls (since
>    the search for dynamic type change will always end before reaching the
>    former and lifetime of the object is over anyway after the latter.  */
> 
> static bool
> stmt_may_be_vtbl_ptr_store (gimple stmt)
> {
>   if (is_gimple_call (stmt))
>     {
>       tree fndecl = gimple_call_fndecl (stmt);
>       if (!fndecl || !DECL_BUILT_IN (fndecl))
> 	return false;

I'm not totally convinced by your arguments above (mainly the
partial inlining and EH ones).  But let those aside, why are
all builtins possibly changing the vtable (but not indirect
calls to builtins (huh)).  I know I made the memcpy argument,
but if it is valid then any call can make a memcpy call and
so all calls would be possibly changing the vtable pointer.

Thus, please remove the code and instead do

  if (is_gimple_call (stmt))
    return false;

and add a big comment as to why, possibly just cut&pasted from
your mail.

>     }
>   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)))
> 	    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;

Otherwise I guess I'm happy with this as initial implementation.

I could now argue that any aggregate store could also copy
a vtable pointer though, like when we'd detect that we are
doing copy construction and copying every field, including
the vtable pointer we could optimize it that way.

As I know we don't do that at the moment I'm fine if you add
a FIXME comment with respect to that.  Or, alternatively,
only return false if !AGGREGATE_TYPE_P (TREE_TYPE (lhs))
which would me make feel 120% comfortable.

> }
> 
> /* 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);

while goes to the next line

>    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;
> 

excess vertical space

>    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);

Can you document the special semantics of a vtables DECL_CONTEXT
in tree.h please?

> }
> 
> /* Callbeck of walk_aliased_vdefs and a helper function for
>    detect_type_change_anc 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;
>       tci->known_current_type = extr_type_from_vtbl_ptr_store (stmt,
> 							       tci->object);

Now we get to the EH concern.  Please change that to

        tree type;
        tci->type_maybe_changed = true;
        type = extr_type_from_vtbl_ptr_store (stmt, tci->object);
        if (tci->known_current_type
            && type != tci->known_current_type)
          tci->known_current_type = (tree) (intptr_t) -1;

if you ever come along a PHI node while walking and detect two different
vtable pointer stores before reaching a common dominator punt.  You
say this won't happen, but I say be safe, not sorry.

You of course need to handle the -1 value in the consumers as
also unknown (or add another flag, whatever you prefer).

>       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.  If
>    ANC_OFFSET is non-zero, look for binfo of its ancestor of that type at that
>    offset.  ARG is supposed to be a dereferenced pointer or a declaration or a
>    series of component_refs of either.  */
> 
> static bool
> detect_type_change_anc (tree arg, gimple call, struct ipa_jump_func *jfunc,
> 			HOST_WIDE_INT anc_offset)
> {
>   struct type_change_info tci;
>   tree obj;
>   ao_ref ar;

So this function is for pass-by-value of objects while the one below
is for pass-by-reference?  Or is arg always a pointer but it is 
dereferenced in the callee here as opposed to the other function?

>   /* Const calls cannot call virtual methods through VMT and so type changes do
>      not matter.  */
>   if (!gimple_vuse (call))
>     return false;
> 
>   obj = arg;
>   while (handled_component_p (obj))
>     obj = TREE_OPERAND (obj, 0);
>   if (TREE_CODE (obj) == MEM_REF)
>     obj = TREE_OPERAND (obj, 0);
>   if (TREE_CODE (obj) == ADDR_EXPR)
>     obj = TREE_OPERAND (obj, 0);

As of the question above I'm not sure but this doesn't seem to handle
an array of objects correctly (we lose information as to what sub-object
we refer to).  That is, I could do

  A a[2];
  ~a[1];
  foo (&a[0]);

and you'd wrongly infer for example the vtable for a pure-virtual
base (thus, I get the usual problem of pure-virtual call runtime
error when refering to a destructed object)?

At least you seem to assume that from the base of the address/object
you can only refer to a single object?

>   tci.object = obj;
>   tci.known_current_type = NULL_TREE;
>   tci.type_maybe_changed = false;
> 
>   ao_ref_init (&ar, arg);
>   walk_aliased_vdefs (&ar, gimple_vuse (call), check_stmt_for_type_change,
> 		      &tci, NULL);
>   if (!tci.type_maybe_changed)
>     return false;
> 
>   if (!tci.known_current_type)
>     jfunc->type = IPA_JF_UNKNOWN;
>   else if (anc_offset != 0)
>     {
>       tree new_binfo = get_binfo_at_offset (TYPE_BINFO (tci.known_current_type),
> 					    anc_offset, TREE_TYPE (arg));
> 
>       if (new_binfo)
> 	{
> 	  jfunc->type = IPA_JF_KNOWN_TYPE;
> 	  jfunc->value.base_binfo = new_binfo;
> 	}
>       else
> 	jfunc->type = IPA_JF_UNKNOWN;
>     }
>   else
>     {
>       /* If an offset of a searched-for sub-object actually happens to be zero,
> 	 we do not have to worry about non-artificialness.  Either there are no
> 	 virtual methods anyway or there is a VMT pointer at offset zero and so
> 	 artificial sub-objects start at higher offsets.  */
>       jfunc->type = IPA_JF_KNOWN_TYPE;
>       jfunc->value.base_binfo = TYPE_BINFO (tci.known_current_type);
>     }
> 
>   return true;
> }
> 
> /* Like detect_type_change_anc but ARG is supposed to be a non-dereferenced
>    pointer SSA name.  */
> 
> static bool
> detect_type_change (tree arg, gimple call, struct ipa_jump_func *jfunc)
> {
>   if (!POINTER_TYPE_P (TREE_TYPE (arg))
>       || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
>     return false;
>   gcc_checking_assert (TREE_CODE (arg) != ADDR_EXPR);

Hm.  I suppose the interfacing to this and the above function can
be improved to not need to build a mem-ref here - esp. as you seem
to handle &a explicitly in the caller.

More comments below at the callers (eventually)

>   arg = build_simple_mem_ref (arg);
>   /* Building a MEM_REF just for the sake of ao_ref_init is probably
>   wasteful here, I'll be happy to discuss alternatives.  */
> 
>   return detect_type_change_anc (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-29  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_1): Likewise.
> 	(detect_type_change): 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.
> 
> 	* 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-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,111 @@ ipa_print_all_jump_functions (FILE *f)
>      }
>  }
>  
> +/* Structure to be passed in between detect_type_change_anc 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.  The function
> +   assumes it will never be called on constructor or destructor calls (since
> +   the search for dynamic type change will always end before reaching the
> +   former and lifetime of the object is over anyway after the latter.  */
> +
> +static bool
> +stmt_may_be_vtbl_ptr_store (gimple stmt)
> +{
> +  if (is_gimple_call (stmt))
> +    {
> +      tree fndecl = gimple_call_fndecl (stmt);
> +      if (!fndecl || !DECL_BUILT_IN (fndecl))
> +	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)))
> +	    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_anc 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.  If
> +   ANC_OFFSET is non-zero, look for binfo of its ancestor of that type at that
> +   offset.  ARG is supposed to be a dereferenced pointer or a declaration or a
> +   series of component_refs of either.  */
> +
> +static bool
> +detect_type_change_anc (tree arg, gimple call, struct ipa_jump_func *jfunc,
> +			HOST_WIDE_INT anc_offset ATTRIBUTE_UNUSED)
> +{
> +  struct type_change_info tci;
> +  ao_ref ar;
> +
> +  /* 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_init (&ar, arg);
> +  walk_aliased_vdefs (&ar, 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_anc but ARG is supposed to be a non-dereferenced
> +   pointer SSA name.  */
> +
> +static bool
> +detect_type_change (tree arg, gimple call, struct ipa_jump_func *jfunc)
> +{
> +  if (!POINTER_TYPE_P (TREE_TYPE (arg))
> +      || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
> +    return false;
> +  gcc_checking_assert (TREE_CODE (arg) != ADDR_EXPR);
> +  arg = build_simple_mem_ref (arg);
> +
> +  return detect_type_change_anc (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 +464,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;
>    int index;
>  
>    op1 = gimple_assign_rhs1 (stmt);
> @@ -388,7 +493,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 (op1, call, jfunc))

Why's it only necessary to check for type changes when the statement
is a (pointer) conversion?

>  	{
>  	  jfunc->type = IPA_JF_PASS_THROUGH;
>  	  jfunc->value.pass_through.formal_id = index;
> @@ -399,10 +505,8 @@ compute_complex_assign_jump_func (struct
>  
>    if (TREE_CODE (op1) != ADDR_EXPR)
>      return;
> -

Like pass the ADDR_EXPR (it seems that pass-by-value isn't handled)
down to a single detect_type_change function.  You'd then use
ao_ref_init_from_ptr_and_size which is more correct anyway
(just pass NULL_TREE to the size, or if you know that the object
starts at the given address and the vtable pointer is at offset
zero pass TYPE_SIZE_UNIT (ptr_type_node)).

>    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
> @@ -419,12 +523,13 @@ compute_complex_assign_jump_func (struct
>  
>    /* Dynamic types are changed only in constructors and destructors and  */
>    index = ipa_get_param_decl_index (info, SSA_NAME_VAR (base));
> -  if (index >= 0)
> +  if (index >= 0
> +      && !detect_type_change_anc (op1, 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 +558,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 +591,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 +619,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 +627,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_anc (obj, call, jfunc, offset))

works here as well.

> +    {
> +      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 +641,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 +660,9 @@ compute_known_type_jump_func (tree op, s
>        || is_global_var (base))
>      return;
>  
> +  if (detect_type_change_anc (op, call, jfunc, offset))
> +    return;

and here.

Thanks,
Richard.

>    binfo = TYPE_BINFO (TREE_TYPE (base));
>    if (!binfo)
>      return;
> @@ -592,7 +704,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 (arg, call, &functions[num]))
>  		{
>  		  functions[num].type = IPA_JF_PASS_THROUGH;
>  		  functions[num].value.pass_through.formal_id = index;
> @@ -604,14 +717,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 +1331,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 +1355,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 (obj, call, &jfunc))
>      ipa_note_param_call (node, index, call, true);
>  }
>  
> 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;
> +}
> 
>

On Thu, 2 Dec 2010, Richard Guenther wrote:

> On Wed, 1 Dec 2010, Martin Jambor wrote:
> 
> > This is the crux of the matter.  I'll try to explain what and why I do
> > in order to detect sub-object type changes during their construction
> > first, below it there is the detection code as it looks like with the
> > next patch applied and then there is of course the patch at the end.
> > 
> > I have split the detection code into two patches, this one just
> > detects that there is a type change in force and the subsequent one
> > also tries to derive the new type.  I did this in order to better
> > structure the discussion about both and I also intend to commit the
> > separately, easing potential bisecting (I hope there will be no reason
> > for that of course).  If it was absolutely necessary, we could
> > postpone the next patch for stage1 but I hope to commit a variant of
> > it soon.
> > 
> > Because operations like placement new, memcpy and other byte-per-byte
> > operations with objects that have virtual methods are deemed to
> > produce code with undefined behavior and there are no unions of
> > non-POD types, dynamic type change has a special meaning for
> > devirtualization and only refers to what actual virtual method table a
> > VMT pointer of an object points to.  On the other hand the type in the
> > sense of what you get from TREE_TYPE of the base of any given access
> > to it is still the same and it is its static type.  An important
> > property of such objects is that their dynamic types (as given by the
> > current VMT) can only be altered in constructors and destructors.
> > 
> > This patch makes special assumptions about both constructors and
> > destructors which are all the functions that are allowed to alter the
> > dynamic types.  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 the
> >    components (including 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 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 (or any component for that matter but type is interesting
> > only for ancestors).
> > 
> > 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).

You can still reach wrong conclusions for the dynamic type of *p
in the following testcase:

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;
}

if you ignore the call to foo() then you see a vtable pointer store
to make *p a B, but in reality at the time of the virtual call to
the destructor it is an A.

Similar, if you add a char data[256]; member to A then a

 {
   B x;
   new (&x.data) A;
   reinterpret_cast<A *>(&x.data)->~A;
 }

might possibly mis-lead you as to the type of B at destruction time
(this example is more similar to the array issue I raised).

Richard.

On 12/01/2010 03:16 PM, Martin Jambor wrote:
> and there are no unions of non-POD types

This is actually no longer true in C++0x.

> dynamic types.  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 the
>     components (including 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.

Slight clarification: this happens after calling constructors for base 
sub-objects and before calling constructors for member sub-objects.

The rest of the writeup all sounds correct.

Jason

Hi,

On Thu, Dec 02, 2010 at 06:25:28PM -0500, Jason Merrill wrote:
> On 12/01/2010 03:16 PM, Martin Jambor wrote:
> >and there are no unions of non-POD types
> 
> This is actually no longer true in C++0x.

OK... but from what I have googled I understand that types with
virtual functions are still explicitely not allowed to be fields of
a union, right?

> 
> >dynamic types.  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 the
> >    components (including 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.
> 
> Slight clarification: this happens after calling constructors for
> base sub-objects and before calling constructors for member
> sub-objects.

OK, I really only care about the sub-objects representing ancestors
(virtual or otherwise) as type of the user-defined member sub-objects
is not derived from the type of whatever other object they are
embedded in.  In any event, passing the correct type to any
constructor is not necessary.

> 
> The rest of the writeup all sounds correct.
> 

Great, thanks a lot,

Martin

On Fri, Dec 3, 2010 at 7:45 AM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> On Thu, Dec 02, 2010 at 06:25:28PM -0500, Jason Merrill wrote:
>> On 12/01/2010 03:16 PM, Martin Jambor wrote:
>> >and there are no unions of non-POD types
>>
>> This is actually no longer true in C++0x.
>
> OK... but from what I have googled I understand that types with
> virtual functions are still explicitely not allowed to be fields of
> a union, right?

I cannot see that restriction from the current draft.

     http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2010/n3225.pdf

-- Gaby

On 12/03/2010 08:45 AM, Martin Jambor wrote:
> On Thu, Dec 02, 2010 at 06:25:28PM -0500, Jason Merrill wrote:
>> On 12/01/2010 03:16 PM, Martin Jambor wrote:
>>> and there are no unions of non-POD types
>>
>> This is actually no longer true in C++0x.
>
> OK... but from what I have googled I understand that types with
> virtual functions are still explicitly not allowed to be fields of
> a union, right?

They are allowed now. 9.5/4 of N3126:

[ Example: Consider an object u of a union type U having non-static data
members m of type M and n of type N. If M has a non-trivial destructor 
and N has a non-trivial constructor (for instance, if they declare or 
inherit virtual functions), the active member of u can be safely 
switched from m to n using the destructor and placement new operator as 
follows:
   u.m.~M();
   new (&u.n) N;
-- end example ]

I wouldn't worry about this for now, though.  I'll add it to the pile of 
union language issues.

Jason

On Fri, 3 Dec 2010, Jason Merrill wrote:

> On 12/03/2010 08:45 AM, Martin Jambor wrote:
> > On Thu, Dec 02, 2010 at 06:25:28PM -0500, Jason Merrill wrote:
> > > On 12/01/2010 03:16 PM, Martin Jambor wrote:
> > > > and there are no unions of non-POD types
> > > 
> > > This is actually no longer true in C++0x.
> > 
> > OK... but from what I have googled I understand that types with
> > virtual functions are still explicitly not allowed to be fields of
> > a union, right?
> 
> They are allowed now. 9.5/4 of N3126:
> 
> [ Example: Consider an object u of a union type U having non-static data
> members m of type M and n of type N. If M has a non-trivial destructor and N
> has a non-trivial constructor (for instance, if they declare or inherit
> virtual functions), the active member of u can be safely switched from m to n
> using the destructor and placement new operator as follows:
>   u.m.~M();
>   new (&u.n) N;
> -- end example ]
> 
> I wouldn't worry about this for now, though.  I'll add it to the pile of union
> language issues.

You have to handle similar situations with allocated storage and
arrays of chars anyway, so I don't think unions should
complicate anything.

Richard.

On Fri, Dec 3, 2010 at 10:07 AM, Jason Merrill <jason@redhat.com> wrote:
> On 12/03/2010 08:45 AM, Martin Jambor wrote:
>>
>> On Thu, Dec 02, 2010 at 06:25:28PM -0500, Jason Merrill wrote:
>>>
>>> On 12/01/2010 03:16 PM, Martin Jambor wrote:
>>>>
>>>> and there are no unions of non-POD types
>>>
>>> This is actually no longer true in C++0x.
>>
>> OK... but from what I have googled I understand that types with
>> virtual functions are still explicitly not allowed to be fields of
>> a union, right?
>
> They are allowed now. 9.5/4 of N3126:
>
> [ Example: Consider an object u of a union type U having non-static data
> members m of type M and n of type N. If M has a non-trivial destructor and N
> has a non-trivial constructor (for instance, if they declare or inherit
> virtual functions), the active member of u can be safely switched from m to
> n using the destructor and placement new operator as follows:
>  u.m.~M();
>  new (&u.n) N;
> -- end example ]
>
> I wouldn't worry about this for now, though.  I'll add it to the pile of
> union language issues.

Are you anticipating banning them?
I would not think they pose any problem -- copy and assignment
has to be user provided anyway, and assignment to a non-POD
data can be done only to the active member (since it is a
member function call)

-- Gaby

On 12/03/2010 11:21 AM, Gabriel Dos Reis wrote:
> On Fri, Dec 3, 2010 at 10:07 AM, Jason Merrill<jason@redhat.com>  wrote:
>> On 12/03/2010 08:45 AM, Martin Jambor wrote:
>>> OK... but from what I have googled I understand that types with
>>> virtual functions are still explicitly not allowed to be fields of
>>> a union, right?
>>
>> They are allowed now. 9.5/4 of N3126:
>>[...]
>> I wouldn't worry about this for now, though.  I'll add it to the pile of
>> union language issues.
>
> Are you anticipating banning them?

No, just need to add this to the list of cases to be considered when 
fixing the C/C++ union aliasing rules.

Jason

Hi,

On Thu, Dec 02, 2010 at 05:17:25PM +0100, Richard Guenther wrote:
> On Thu, 2 Dec 2010, Richard Guenther wrote:
> 
> > On Wed, 1 Dec 2010, Martin Jambor wrote:
> > 
> > > 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).
> 
> You can still reach wrong conclusions for the dynamic type of *p
> in the following testcase:
> 
> 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;
> }
> 
> if you ignore the call to foo() then you see a vtable pointer store
> to make *p a B, but in reality at the time of the virtual call to
> the destructor it is an A.

This exactly the reason why I only devirtualize when I now that the
object has been automatically allocated (well, after the second patch
removes devirtualization according to global variables).

If we split main from the above testcase into three functions, one of
the jump function would look wrong but would not be used because it
will be combined with an UNKNOWN jump function coming from the caller
so it would not matter.

> 
> Similar, if you add a char data[256]; member to A then a
> 
>  {
>    B x;
>    new (&x.data) A;
>    reinterpret_cast<A *>(&x.data)->~A;
>  }
> 
> might possibly mis-lead you as to the type of B at destruction time
> (this example is more similar to the array issue I raised).
> 

With a bit of tweaking I was able to make a failing testcase out of
this.  More on this when I reply to the other email.

Thanks,

Martin