Re: [PATCH, devirtualization] Detect the new type in type change detection
On Tue, Nov 1, 2011 at 10:02 PM, Martin Jambor mjam...@suse.cz wrote:
Hi,
On Tue, Nov 01, 2011 at 10:37:10AM +0100, Richard Guenther wrote:
On Mon, Oct 31, 2011 at 5:58 PM, Martin Jambor mjam...@suse.cz wrote:
On Fri, Oct 28, 2011 at 11:21:23AM +0200, Richard Guenther wrote:
On Thu, Oct 27, 2011 at 9:54 PM, Martin Jambor mjam...@suse.cz wrote:
Hi,
On Thu, Oct 27, 2011 at 11:06:02AM +0200, Richard Guenther wrote:
On Thu, Oct 27, 2011 at 1:22 AM, Martin Jambor mjam...@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 mjam...@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)
OK.
+ 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).
I guess I might have been overly conservative here, ARRAY_REFs are
fine. get_base_address only digs into MEM_REFs if they are based on
an ADDR_EXPR while I do so always. But I can check that either both
obj and analyzed_obj are a MEM_REF of the same SSA_NAME or they are
the same thing (i.e. the same decl)... which even feels a bit cleaner,
so I did that.
Well, as you are looking for a must-change-type pattern I think you cannot
simply ignore offsets. Consider
T a[10];
new (T') (a[9]);
a[8]-foo();
Re: [PATCH, devirtualization] Detect the new type in type change detection
On Mon, Oct 31, 2011 at 5:58 PM, Martin Jambor mjam...@suse.cz wrote:
On Fri, Oct 28, 2011 at 11:21:23AM +0200, Richard Guenther wrote:
On Thu, Oct 27, 2011 at 9:54 PM, Martin Jambor mjam...@suse.cz wrote:
Hi,
On Thu, Oct 27, 2011 at 11:06:02AM +0200, Richard Guenther wrote:
On Thu, Oct 27, 2011 at 1:22 AM, Martin Jambor mjam...@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 mjam...@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)
OK.
+ 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).
I guess I might have been overly conservative here, ARRAY_REFs are
fine. get_base_address only digs into MEM_REFs if they are based on
an ADDR_EXPR while I do so always. But I can check that either both
obj and analyzed_obj are a MEM_REF of the same SSA_NAME or they are
the same thing (i.e. the same decl)... which even feels a bit cleaner,
so I did that.
Well, as you are looking for a must-change-type pattern I think you cannot
simply ignore offsets. Consider
T a[10];
new (T') (a[9]);
a[8]-foo();
where the must-type-change on a[9] is _not_ changing the type of a[8]!
Similar cases might happen with
class Compound { T a; T b; };
no?
Please think about the difference must vs. may-type-change for these
cases. I'm not convinced that the must-type-change code is
Re: [PATCH, devirtualization] Detect the new type in type change detection
Hi,
On Tue, Nov 01, 2011 at 10:37:10AM +0100, Richard Guenther wrote:
On Mon, Oct 31, 2011 at 5:58 PM, Martin Jambor mjam...@suse.cz wrote:
On Fri, Oct 28, 2011 at 11:21:23AM +0200, Richard Guenther wrote:
On Thu, Oct 27, 2011 at 9:54 PM, Martin Jambor mjam...@suse.cz wrote:
Hi,
On Thu, Oct 27, 2011 at 11:06:02AM +0200, Richard Guenther wrote:
On Thu, Oct 27, 2011 at 1:22 AM, Martin Jambor mjam...@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 mjam...@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)
OK.
+ 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).
I guess I might have been overly conservative here, ARRAY_REFs are
fine. get_base_address only digs into MEM_REFs if they are based on
an ADDR_EXPR while I do so always. But I can check that either both
obj and analyzed_obj are a MEM_REF of the same SSA_NAME or they are
the same thing (i.e. the same decl)... which even feels a bit cleaner,
so I did that.
Well, as you are looking for a must-change-type pattern I think you cannot
simply ignore offsets. Consider
T a[10];
new (T') (a[9]);
a[8]-foo();
where the must-type-change on a[9] is _not_ changing the type of a[8]!
Re: [PATCH, devirtualization] Detect the new type in type change detection
On Thu, Oct 27, 2011 at 1:22 AM, Martin Jambor mjam...@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 mjam...@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)
+
Re: [PATCH, devirtualization] Detect the new type in type change detection
Hi,
On Thu, Oct 27, 2011 at 11:06:02AM +0200, Richard Guenther wrote:
On Thu, Oct 27, 2011 at 1:22 AM, Martin Jambor mjam...@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 mjam...@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)
OK.
+ 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).
I guess I might have been overly conservative here, ARRAY_REFs are
fine. get_base_address only digs into MEM_REFs if they are based on
an ADDR_EXPR while I do so always. But I can check that either both
obj and analyzed_obj are a MEM_REF of the same SSA_NAME or they are
the same thing (i.e. the same decl)... which even feels a bit cleaner,
so I did that.
+ 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
Re: [PATCH, devirtualization] Detect the new type in type change detection
On 27/10/2011, at 12:22 PM, Martin Jambor 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). Martin, Thank you for pushing this patch forward. This patch fixes one of the inlining/devirtualization tests I posted in another thread. It also removes one of the roadblocks for several of the other tests to pass. -- Maxim Kuvyrkov CodeSourcery / Mentor Graphics
[PATCH, devirtualization] Detect the new type in type change detection
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 mjam...@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))
+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);
+}
+
/* 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
