[PATCH, devirtualization] Detect the new type in type change detection

[Richard Guenther]

On Thu, Oct 27, 2011 at 1:22 AM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> I've been asked by Maxim Kuvyrkov to revive the following patch which
> has not made it to 4.6.  Currently, when type based devirtualization
> detects a potential type change, it simply gives up on gathering any
> information on the object in question.  This patch adds an attempt to
> actually detect the new type after the change.
>
> Maxim claimed this (and another patch I'll post tomorrow) noticeably
> improved performance of some real code.  I can only offer a rather
> artificial example in the attachment.  When the constructors are
> inlined but the function multiply_matrices is not, this patch makes
> the produced executable run for only 7 seconds instead of about 20 on
> my 4 year old i686 desktop (with -Ofast).
>
> Anyway, the patch passes bootstrap and testsuite on x86_64-linux.
> What do you think, is it a good idea for trunk now?
>
> Thanks,
>
> Martin
>
>
> 2011-10-21  Martin Jambor  <mjambor@suse.cz>
>
>        * ipa-prop.c (type_change_info): New fields object, known_current_type
>        and multiple_types_encountered.
>        (extr_type_from_vtbl_ptr_store): New function.
>        (check_stmt_for_type_change): Use it, set multiple_types_encountered if
>        the result is different from the previous one.
>        (detect_type_change): Renamed to detect_type_change_1. New parameter
>        comp_type.  Set up new fields in tci, build known type jump
>        functions if the new type can be identified.
>        (detect_type_change): New function.
>        * tree.h (DECL_CONTEXT): Comment new use.
>
>        * testsuite/g++.dg/ipa/devirt-c-1.C: Add dump scans.
>        * testsuite/g++.dg/ipa/devirt-c-2.C: Likewise.
>        * testsuite/g++.dg/ipa/devirt-c-7.C: New test.
>
>
> Index: src/gcc/ipa-prop.c
> ===================================================================
> --- src.orig/gcc/ipa-prop.c
> +++ src/gcc/ipa-prop.c
> @@ -271,8 +271,17 @@ ipa_print_all_jump_functions (FILE *f)
>
>  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.
> @@ -338,6 +347,49 @@ stmt_may_be_vtbl_ptr_store (gimple stmt)
>   return true;
>  }
>
> +/* If STMT can be proved to be an assignment to the virtual method table
> +   pointer of ANALYZED_OBJ and the type associated with 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))

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

You do not allow other components than component-refs (thus, for
example an ARRAY_REF - that is for a reason?).  Please add
a comment why.  Otherwise this whole sequence would look like
it should be replaceable by get_base_address (obj).

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

Do we actually ever store sth else than the plain address of a
virtual table (thus, &decl)?  If so, what difference makes the offset
into the virtual table we get in this way?  I ask, because ...

> +  if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t))
> +    return NULL_TREE;
> +
> +  return DECL_CONTEXT (t);

... DECL_CONTEXT (t) is of course independent of any offset.

Thus I think you should drop the call to get_base_address () and
instead just look at TREE_OPERAND (t, 0).

> +}
> +
>  /* Callback 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
> @@ -352,6 +404,12 @@ check_stmt_for_type_change (ao_ref *ao A
>
>   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;
>     }
> @@ -359,19 +417,19 @@ check_stmt_for_type_change (ao_ref *ao A
>     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.  */
> +
> +
> +/* Like detect_type_change but with extra argument COMP_TYPE which will become
> +   the component type part of new JFUNC of dynamic type change is detected and
> +   the new base type is identified.  */
>
>  static bool
> -detect_type_change (tree arg, tree base, gimple call,
> -                   struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
> +detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call,
> +                     struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
>  {
>   struct type_change_info tci;
>   ao_ref ao;
> +  tree t;
>
>   gcc_checking_assert (DECL_P (arg)
>                       || TREE_CODE (arg) == MEM_REF
> @@ -381,8 +439,6 @@ detect_type_change (tree arg, tree base,
>   if (!flag_devirtualize || !gimple_vuse (call))
>     return false;
>
> -  tci.type_maybe_changed = false;
> -
>   ao.ref = arg;
>   ao.base = base;
>   ao.offset = offset;
> @@ -391,15 +447,51 @@ detect_type_change (tree arg, tree base,
>   ao.ref_alias_set = -1;
>   ao.base_alias_set = -1;
>
> +  t = arg;
> +  while (handled_component_p (t))
> +    t = TREE_OPERAND (t, 0);

Here you are using handled_component_p, thus allow ARRAY_REFs ...
but you are not trying to distinguish a[1] from a[2] anywhere, so this
looks bogus and instead should look like the case above (with a comment
as to why looking at ARRAY_REFs would be bogus).

Thanks,
Richard.

> +  if (TREE_CODE (t) == MEM_REF)
> +    t = TREE_OPERAND (t, 0);
> +  if (TREE_CODE (t) == ADDR_EXPR)
> +    t = TREE_OPERAND (t, 0);
> +  tci.object = t;
> +  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;
>
> -  jfunc->type = IPA_JF_UNKNOWN;
> +  if (!tci.known_current_type
> +      || tci.multiple_types_encountered
> +      || offset != 0)
> +    jfunc->type = IPA_JF_UNKNOWN;
> +  else
> +    {
> +      jfunc->type = IPA_JF_KNOWN_TYPE;
> +      jfunc->value.known_type.base_type = tci.known_current_type;
> +      jfunc->value.known_type.component_type = comp_type;
> +    }
> +
>   return true;
>  }
>
> +/* 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)
> +{
> +  return detect_type_change_1 (arg, base, TREE_TYPE (arg), call, jfunc, offset);
> +}
> +
>  /* 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).  */
> @@ -407,16 +499,19 @@ detect_type_change (tree arg, tree base,
>  static bool
>  detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
>  {
> +  tree comp_type;
> +
>   gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
>   if (!flag_devirtualize
>       || !POINTER_TYPE_P (TREE_TYPE (arg))
>       || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
>     return false;
>
> +  comp_type = TREE_TYPE (TREE_TYPE (arg));
>   arg = build2 (MEM_REF, ptr_type_node, arg,
> -                build_int_cst (ptr_type_node, 0));
> +               build_int_cst (ptr_type_node, 0));
>
> -  return detect_type_change (arg, arg, call, jfunc, 0);
> +  return detect_type_change_1 (arg, arg, comp_type, call, jfunc, 0);
>  }
>
>  /* Callback of walk_aliased_vdefs.  Flags that it has been invoked to the
> Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
> ===================================================================
> --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
> +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
> @@ -1,7 +1,7 @@
>  /* 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"  } */
> +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized"  } */
>
>  extern "C" void abort (void);
>
> @@ -69,3 +69,8 @@ int main (int argc, char *argv[])
>     bah ();
>   return 0;
>  }
> +
> +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo"  "cp"  } } */
> +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
> +/* { dg-final { cleanup-ipa-dump "cp" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
> ===================================================================
> --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
> +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
> @@ -1,7 +1,7 @@
>  /* 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"  } */
> +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized"  } */
>
>  extern "C" void abort (void);
>
> @@ -77,3 +77,8 @@ int main (int argc, char *argv[])
>     bah ();
>   return 0;
>  }
> +
> +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo"  "cp"  } } */
> +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
> +/* { dg-final { cleanup-ipa-dump "cp" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: src/gcc/tree.h
> ===================================================================
> --- src.orig/gcc/tree.h
> +++ src/gcc/tree.h
> @@ -2678,7 +2678,9 @@ struct function;
>     nodes, this points to either the FUNCTION_DECL for the containing
>     function, the RECORD_TYPE or UNION_TYPE for the containing type, or
>     NULL_TREE or a TRANSLATION_UNIT_DECL if the given decl has "file
> -    scope".  */
> +    scope".  In particular, for VAR_DECLs which are virtual table pointers
> +    (they have DECL_VIRTUAL set), we use DECL_CONTEXT to determine the type
> +    they belong to.  */
>  #define DECL_CONTEXT(NODE) (DECL_MINIMAL_CHECK (NODE)->decl_minimal.context)
>  #define DECL_FIELD_CONTEXT(NODE) \
>   (FIELD_DECL_CHECK (NODE)->decl_minimal.context)
> Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C
> ===================================================================
> --- /dev/null
> +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C
> @@ -0,0 +1,87 @@
> +/* Verify that ipa-cp will not get confused by placement new constructing an
> +   object within another one when looking for dynamic type change .  */
> +/* { dg-do run } */
> +/* { dg-options "-O3 -Wno-attributes"  } */
> +
> +extern "C" void abort (void);
> +namespace std {
> +  typedef __SIZE_TYPE__ size_t;
> +}
> +inline void* __attribute__ ((always_inline))
> +operator new(std::size_t, void* __p) throw()
> +{
> +  return __p;
> +}
> +
> +class A
> +{
> +public:
> +  char data[256];
> +  A();
> +  virtual int foo (int i);
> +};
> +
> +class B : public A
> +{
> +public:
> +  virtual int foo (int i);
> +};
> +
> +class C
> +{
> +public:
> +  C();
> +  virtual double foo (double i);
> +};
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +double C::foo (double i)
> +{
> +  return i + 3.5;
> +}
> +
> +static int __attribute__ ((noinline)) middleman (class A *obj, int i)
> +{
> +  return obj->foo (i);
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +__attribute__ ((always_inline)) C::C ()
> +{
> +}
> +
> +A::A ()
> +{
> +}
> +
> +static  __attribute__ ((noinline)) void bah ()
> +{
> +  class B b;
> +
> +  C *c = new ((void *) &b.data) C;
> +
> +  if (middleman (&b, get_input ()) != 3)
> +    abort ();
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  int i;
> +
> +  for (i = 0; i < 10; i++)
> +    bah ();
> +  return 0;
> +}
>