Hi,
this patch tries to make gimple_extract_devirt_binfo_from_cst little bit more
sane and make it match bit more cases. Currently we seem to be able to
devirtualize only if the type in question has no basetypes (not even some not
having virtual methods at all) and it is the initial type implementing the
given virtual method (i.e. we even refuse any derivation not giving new
implementation of the virtual method in question). This is bit silly.
What the current implemntation does
===================================
gimple_extract_devirt_binfo_from_cst looks for address expression that object
used for virtual method comes from. It sees something like
&var + 10;
It looks at the type of VAR and tries to look for a field at offset 10. If it
suceeds it verify that the field is not artificial (i.e. it is not base of some
outer type present in var) and that its BINFO has no derived types (it basically
has to be the original type defining the virtual method and the type can not
be derived at all).
After this happen the caller proceeds by calling get_binfo_at_offset and by
lookup of virtual call from vtable found.
Why it does so
==============
I was always confused on why gimple_extract_devirt_binfo_from_cst apparently
duplicates logic of get_binfo_at_offset and why it has the limitations.
Disussing this with Martin, it is about dynamic type changes. My understanding
is that
1) we want the type to not have base because we may have inlined the
constructor.
During construction the vtables are filled by base's vtable and thus we can
not simply devirtualize based on the final virtual table without proving
that
constructor was not (partially) inlined.
This is ensured by the exisitng code refusing artifical types and
by the check for number of bases being 0.
2) apparently the code is supposed to refuse non-0 offset
because ipa-prop is tracking possibly dynamic type changes only for
beggining of the objects.
What is wrong with 1
====================
I think 1) is unnecesarily restrictive.
a) when tyhe bases of type found define no virtual methods (or do not
define virtual method in question) then partially constructed types
are not harmful.
b) when the type found has a base type that defines given method, but do
not overwrite it, we are safe too.
Less conservative solution for 1
================================
I think 1) can be also ignored in gimple_extract_devirt_binfo_from_cst pushing
the need to check for effects of partial construction into users. I think I can
track constructors inlined into given function, but I am not doing it right now.
Intead I do two lookups - I find the method by the mechanizm above and I compare
it with the first definition of the method. If they are same, I devirtualize.
What seems worng with 2
=======================
For 2) i actually found no code checking it. All I can notice that current
implementation will always fail to find anything in ipa-prop when
indirect_info->offset is non-0. This is because the conditions implementing 1)
prevents gimple_extract_devirt_binfo_from_cst to return anything than the final
type and it will never match on any derived type (making the whole thing bit
pointless, since devirtualization is mostly about derived types I think).
Solution for 2
==============
It does not seem to break the testcases, but if check_stmt_for_type_change
really
can not detect changes outside the main object, then I think all the code above
is wrong anyway and it needs to test for zero the combined offset (i.e. offset
given by get_ref_base_and_extent on the constant as well as offset of the
basetype given by indirect_info->offset). This can be done easily and will
disable any transformations on derived types, but I suppose I can extend it
incrementally.
I am also confused why ipa-prop needs to track dynamic changes, while
gimple-fold is happy without doing so. I do not know if one can do
something like having automatic variable of class A and use placement new
to change it to class B. I tried to change devirt-6.C testcase to do so
but did not suceed in producing anything that would seem to have sane
construction and destruction order. The local variable is destructed
at the end of sope block, so I would at least need to placement new it to
something class B, do somethjing and then placement new it back so the
destructor can be called. I would hope this is invalid. Is there any
sane summary of restriction of placement new use?
If such changing of dyanmic type is possible, we will need to track in
gimple-fold the changes, too.
My secret plan is to track these cases and devirtualize speculatively - the
dynamic type changes are rare and often they can be detected by the local
constant propagation on memory locations and optimized out anyway (at least
for the inlined constructors).
Why I can not use get_binfo_at_offset
=====================================
Finally I decided to replace the lookup of base binfo by call to
get_binfo_at_offset. This is not possible. For example my base
variable can be:
struct {class A a; class B b} var;
and offset 10 may point to class B. Here I get an ICE since TYPE_BINFO
of the structure is NULL (it is not class).
So we need to
A) walk type fields until we find an field we look for (containing the
base defining virtual method in question)
B) walk binfos of that field to find correct one.
A) is now done by new field walking in gimple_extract_devirt_binfo_from_cst
and then it dispatch to get_binfo_at_offset that implements B.
What is wrong with get_binfo_at_offset
======================================
>From observation above I think get_binfo_at_offset code is wrong. It has
code that attempts to walk non-artifical fields (i.e. non-base types).
It bails out on NULL BINFO that is likely to happen. In fact
get_binfo_at_offset
probably should use it through the loop in gimple_extract_devirt_binfo_from_cst
but I decided to leave this for incremental step.
Of course we can also handle array and union containers. unions are bit
harder since we will need to collect all binfos and update callers to be ready
to receive multitude of them.
The proposed patch bootstraps®tests x86_64-linux and ppc64-linux.
If it seems to make sense I will proceed with
1) mentioned get_binfo_at_offset reorg
2) using speculative call trick to handle cases where virtual method
was overwritten
3) trakcing of partial inlining of constructors to avoid need in speculation
in most cases (I hope)
4) I wonder if we can track functions that return pointers/values of objects
exactly of given type (i.e. no derivations). This seems to be implementable
and also may allow to add user attribute returns_no_derived_types.
The devirtualization machinery then can use the type knowledge as if it
was the type of container var
5) Is the dynamic type upon return from constructor always known to be of
constructor's type? We may want to introduce assert_type_expr use like:
obj_ptr = assert_type_expr<class A> obj_ptr;
that can be dropped by FE for us to drive those more interesting cases, like
partial construction. Like for bulitin_expect we can drop this one after
IPA passes.
Honza
* ipa-cp.c (ipa_get_indirect_edge_target_1): Update use
of gimple_extract_devirt_binfo_from_cst.
* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): Rework.
(gimple_fold_call): Update use of gimple_extract_devirt_binfo_from_cst.
* ipa-prop.c (try_make_edge_direct_virtual_call): Likewise.
* gimple.h (gimple_extract_devirt_binfo_from_cst): Update.
Index: ipa-cp.c
===================================================================
--- ipa-cp.c (revision 201814)
+++ ipa-cp.c (working copy)
@@ -1541,14 +1541,24 @@ ipa_get_indirect_edge_target_1 (struct c
if (TREE_CODE (t) != TREE_BINFO)
{
tree binfo;
+ tree target, base_target;
binfo = gimple_extract_devirt_binfo_from_cst
- (t, ie->indirect_info->otr_type);
+ (t, ie->indirect_info->otr_type,
+ ie->indirect_info->offset);
if (!binfo)
return NULL_TREE;
- binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
- if (!binfo)
+ target = gimple_get_virt_method_for_binfo (token, binfo);
+ if (!target)
+ return NULL_TREE;
+ /* Constructors may be partially inlined. We do not track
+ if type is in construction and during that time the
+ virtual table may correspond to virtual table of the
+ base type. */
+ base_target = gimple_get_virt_method_for_binfo
+ (token, TYPE_BINFO (ie->indirect_info->otr_type));
+ if (base_target != target)
return NULL_TREE;
- return gimple_get_virt_method_for_binfo (token, binfo);
+ return target;
}
else
{
Index: gimple-fold.c
===================================================================
--- gimple-fold.c (revision 201814)
+++ gimple-fold.c (working copy)
@@ -1006,16 +1006,20 @@ gimple_fold_builtin (gimple stmt)
/* Return a binfo to be used for devirtualization of calls based on an object
represented by a declaration (i.e. a global or automatically allocated one)
or NULL if it cannot be found or is not safe. CST is expected to be an
- ADDR_EXPR of such object or the function will return NULL. Currently it is
- safe to use such binfo only if it has no base binfo (i.e. no ancestors)
- EXPECTED_TYPE is type of the class virtual belongs to. */
+ ADDR_EXPR of such object or the function will return NULL.
+
+ It is up to the caller to check for absence of dynamic type changes.
+ Because constructors may be partially inlined and the virtual tables
+ during construction may be overwritten by virtual tables by base types,
+ it is also up to caller to verify that either all base types have
+ the same virtual method or that this does not happen. */
tree
-gimple_extract_devirt_binfo_from_cst (tree cst, tree expected_type)
+gimple_extract_devirt_binfo_from_cst (tree cst, tree expected_type,
+ HOST_WIDE_INT otr_offset)
{
- HOST_WIDE_INT offset, size, max_size;
- tree base, type, binfo;
- bool last_artificial = false;
+ HOST_WIDE_INT offset, size, max_size, base_offset;
+ tree base, type, last_nonartifical;
if (!flag_devirtualize
|| TREE_CODE (cst) != ADDR_EXPR
@@ -1024,15 +1028,19 @@ gimple_extract_devirt_binfo_from_cst (tr
cst = TREE_OPERAND (cst, 0);
base = get_ref_base_and_extent (cst, &offset, &size, &max_size);
+ base_offset = offset;
type = TREE_TYPE (base);
+ last_nonartifical = type;
if (!DECL_P (base)
|| max_size == -1
|| max_size != size
|| TREE_CODE (type) != RECORD_TYPE)
return NULL_TREE;
- /* Find the sub-object the constant actually refers to and mark whether it is
- an artificial one (as opposed to a user-defined one). */
+ /* Find the sub-object the constant actually refers to.
+ We are interested in the innermost non-artifical one, since that
+ actually represent the basetype of the field.
+ Rest of walking is done by get_binfo_at_offset. */
while (true)
{
HOST_WIDE_INT pos, size;
@@ -1056,19 +1064,19 @@ gimple_extract_devirt_binfo_from_cst (tr
if (!fld || TREE_CODE (TREE_TYPE (fld)) != RECORD_TYPE)
return NULL_TREE;
- last_artificial = DECL_ARTIFICIAL (fld);
type = TREE_TYPE (fld);
+ if (!DECL_ARTIFICIAL (fld))
+ {
+ last_nonartifical = type;
+ base_offset = offset;
+ }
offset -= pos;
}
- /* Artificial sub-objects are ancestors, we do not want to use them for
- devirtualization, at least not here. */
- if (last_artificial)
- return NULL_TREE;
- binfo = TYPE_BINFO (type);
- if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
+
+ if (!TYPE_BINFO (last_nonartifical))
return NULL_TREE;
- else
- return binfo;
+ return get_binfo_at_offset (TYPE_BINFO (last_nonartifical),
+ base_offset + otr_offset, expected_type);
}
/* Attempt to fold a call statement referenced by the statement iterator GSI.
@@ -1108,14 +1116,20 @@ gimple_fold_call (gimple_stmt_iterator *
else
{
tree obj = OBJ_TYPE_REF_OBJECT (callee);
+ tree class_type = obj_type_ref_class (callee);
tree binfo = gimple_extract_devirt_binfo_from_cst
- (obj, obj_type_ref_class (callee));
+ (obj, class_type, 0);
if (binfo)
{
HOST_WIDE_INT token
= TREE_INT_CST_LOW (OBJ_TYPE_REF_TOKEN (callee));
tree fndecl = gimple_get_virt_method_for_binfo (token, binfo);
- if (fndecl)
+ tree base_fndecl = gimple_get_virt_method_for_binfo (token,
TYPE_BINFO (class_type));
+ /* Constructors may be partially inlined. We do not track
+ if type is in construction and during that time the
+ virtual table may correspond to virtual table of the
+ base type. */
+ if (fndecl && base_fndecl == fndecl)
{
gimple_call_set_fndecl (stmt, fndecl);
changed = true;
Index: ipa-prop.c
===================================================================
--- ipa-prop.c (revision 201814)
+++ ipa-prop.c (working copy)
@@ -2444,7 +2444,7 @@ try_make_edge_direct_virtual_call (struc
struct ipa_jump_func *jfunc,
struct ipa_node_params *new_root_info)
{
- tree binfo, target;
+ tree binfo, target, base_target = NULL;
binfo = ipa_value_from_jfunc (new_root_info, jfunc);
@@ -2454,19 +2454,31 @@ try_make_edge_direct_virtual_call (struc
if (TREE_CODE (binfo) != TREE_BINFO)
{
binfo = gimple_extract_devirt_binfo_from_cst
- (binfo, ie->indirect_info->otr_type);
+ (binfo, ie->indirect_info->otr_type,
+ ie->indirect_info->offset);
if (!binfo)
return NULL;
+ /* Constructors may be partially inlined. We do not track
+ if type is in construction and during that time the
+ virtual table may correspond to virtual table of the
+ base type. */
+ base_target = gimple_get_virt_method_for_binfo
(ie->indirect_info->otr_token,
+ TYPE_BINFO
(ie->indirect_info->otr_type));
+ if (!base_target)
+ return NULL;
}
-
- binfo = get_binfo_at_offset (binfo, ie->indirect_info->offset,
- ie->indirect_info->otr_type);
+ else
+ binfo = get_binfo_at_offset (binfo, ie->indirect_info->offset,
+ ie->indirect_info->otr_type);
if (binfo)
target = gimple_get_virt_method_for_binfo (ie->indirect_info->otr_token,
binfo);
else
return NULL;
+ if (base_target && target != base_target)
+ return NULL;
+
if (target)
return ipa_make_edge_direct_to_target (ie, target);
else
Index: gimple.h
===================================================================
--- gimple.h (revision 201814)
+++ gimple.h (working copy)
@@ -854,7 +854,7 @@ unsigned get_gimple_rhs_num_ops (enum tr
gimple gimple_alloc_stat (enum gimple_code, unsigned MEM_STAT_DECL);
const char *gimple_decl_printable_name (tree, int);
tree gimple_get_virt_method_for_binfo (HOST_WIDE_INT, tree);
-tree gimple_extract_devirt_binfo_from_cst (tree, tree);
+tree gimple_extract_devirt_binfo_from_cst (tree, tree, HOST_WIDE_INT);
/* Returns true iff T is a scalar register variable. */
extern bool is_gimple_reg (tree);
