[PATCH, PR 45934 2/5] Dynamic type change detection
Richard Guenther
rguenther@suse.de
Fri Jan 14 09:51:00 GMT 2011
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.
More information about the Gcc-patches
mailing list