* [PATCH] Implement devirtualize by typeid optimization pass
@ 2024-06-24 10:28 user202729
0 siblings, 0 replies; only message in thread
From: user202729 @ 2024-06-24 10:28 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1117 bytes --]
This patch tries to address the issue in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115413 .
It does so by adding another pass devirtualize-typeid which does the same thing as the value range propagation pass, except
* in the true branch of a conditional of the form `typeid (a) == typeid (b)`, it is assumed that the vptr are equal.
* the constant folding is only performed for member function calls.
This must be done into a separate pass because it is desirable that accesses to the pointer's value (which is possible with the pmf extension of gcc) print out the correct pointer value.
Reviews are appreciated, in particular with respect to the following points:
* Currently only expressions written exactly `typeid (a) == typeid (b)` will be detected, and not expressions such as `auto &tmp = typeid (a); if (tmp == typeid (b)) ...`
* The second argument of `TYPEID_WITH_PTR_TAG` is put in, even though evaluating it might trigger a segmentation fault when the pointer is NULL, only to be thrown away in the expansion pass. We must make sure that it never get evaluated in the final code.
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: a.patch --]
[-- Type: text/x-patch; name=a.patch, Size: 31999 bytes --]
From dcfdcc86cb6ce9e9ec390f031c9ab1563506cdee Mon Sep 17 00:00:00 2001
From: user202729 <user202729@protonmail.com>
Date: Mon, 24 Jun 2024 17:15:58 +0800
Subject: [PATCH] Implement devirtualize by typeid optimization pass
PR c++/115413
gcc/cp/ChangeLog:
* class.cc (build_vtbl_ref): Split off the function into two sections, one to get the vtbl and one to get the element.
(build_vtbl_element_from_vtbl_ref): Splitted off from the above.
* cp-tree.h (build_vtbl_ref): Modify declaration accordingly.
(build_vtbl_element_from_vtbl_ref): Likewise.
* rtti.cc (get_tinfo_decl_dynamic): Now also return the vptr of the type.
(tag_typeid_with_vptr): New function.
(build_typeid): Modify to tag result with vptr.
(get_vtable_ptr): New function.
(get_typeid): Modify to tag result with vptr.
(tinfo_base_init): Part moved to get_vtable_ptr.
* typeck.cc (build_x_binary_op): Detect comparison of typeid.
gcc/ChangeLog:
* gimple-range-cache.cc (ranger_cache::ranger_cache): Add flag for devirtualize-typeid pass.
* gimple-range-cache.h (class ranger_cache): Likewise.
* gimple-range-gori.cc (gori_map::gori_map): Likewise.
(gori_compute::gori_compute): Likewise.
* gimple-range-gori.h (class gori_map): Likewise.
(class gori_compute): Likewise.
* gimple-range.cc (gimple_ranger::gimple_ranger): Likewise.
(enable_ranger): Likewise.
* gimple-range.h (enable_ranger): Likewise.
* internal-fn.cc (expand_TYPEID_WITH_VPTR_TAG): New function.
(expand_VPTR_EQUIV): New function.
* internal-fn.def (TYPEID_WITH_VPTR_TAG): New internal function for devirtualize-typeid pass.
(VPTR_EQUIV): Likewise.
* internal-fn.h (expand_TYPEID_WITH_VPTR_TAG): New function declaration.
(expand_VPTR_EQUIV): New function declaration.
* passes.def (pass_devirtualize_by_typeid): New pass.
* timevar.def (TV_TREE_DEVIRT_TYPEID): Likewise.
* tree-pass.h (make_pass_devirtualize_by_typeid): Likewise.
* tree-vrp.cc (execute_ranger_vrp): Add flag for devirtualize-typeid pass.
(make_pass_devirtualize_by_typeid): New function to create the devirtualize-typeid pass info.
* value-pointer-equiv.h (class pointer_equiv_analyzer): Add flag for devirtualize-typeid pass.
* value-pointer-equiv.cc (pointer_equiv_analyzer::pointer_equiv_analyzer): Likewise.
(pointer_equiv_analyzer::visit_edge): Specially handle vptr equivalence.
* value-query.cc (range_query::create_gori): Add flag for devirtualize-typeid pass.
* value-query.h (range_query::create_gori): Modify declaration accordingly.
gcc/testsuite/ChangeLog:
* g++.dg/tree-ssa/devirt-typeid.C: New test.
---
gcc/cp/class.cc | 30 +++++--
gcc/cp/cp-tree.h | 2 +
gcc/cp/rtti.cc | 87 +++++++++++++++----
gcc/cp/typeck.cc | 36 ++++++++
gcc/gimple-range-cache.cc | 6 +-
gcc/gimple-range-cache.h | 3 +-
gcc/gimple-range-gori.cc | 10 ++-
gcc/gimple-range-gori.h | 6 +-
gcc/gimple-range.cc | 9 +-
gcc/gimple-range.h | 5 +-
gcc/internal-fn.cc | 22 +++++
gcc/internal-fn.def | 4 +
gcc/internal-fn.h | 2 +
gcc/passes.def | 1 +
gcc/testsuite/g++.dg/tree-ssa/devirt-typeid.C | 56 ++++++++++++
gcc/timevar.def | 1 +
gcc/tree-pass.h | 1 +
gcc/tree-vrp.cc | 37 ++++++--
gcc/value-pointer-equiv.cc | 26 +++++-
gcc/value-pointer-equiv.h | 3 +-
gcc/value-query.cc | 8 +-
gcc/value-query.h | 3 +-
22 files changed, 307 insertions(+), 51 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/tree-ssa/devirt-typeid.C
diff --git a/gcc/cp/class.cc b/gcc/cp/class.cc
index 0ce361eb88e..007d357207e 100644
--- a/gcc/cp/class.cc
+++ b/gcc/cp/class.cc
@@ -727,14 +727,14 @@ build_vfield_ref (tree datum, tree type)
}
/* Given an object INSTANCE, return an expression which yields the
- vtable element corresponding to INDEX. There are many special
- cases for INSTANCE which we take care of here, mainly to avoid
- creating extra tree nodes when we don't have to. */
+ vtable. There are many special cases for INSTANCE which we take care of
+ here, mainly to avoid creating extra tree nodes when we don't have to.
+ If a TYPE is given, use build_vtbl_ref instead.
+ If a BINFO is given, use BINFO_VTABLE instead. */
tree
-build_vtbl_ref (tree instance, tree idx)
+build_vtbl_ref (tree instance)
{
- tree aref;
tree vtbl = NULL_TREE;
/* Try to figure out what a reference refers to, and
@@ -756,12 +756,30 @@ build_vtbl_ref (tree instance, tree idx)
if (!vtbl)
vtbl = build_vfield_ref (instance, basetype);
- aref = build_array_ref (input_location, vtbl, idx);
+ return vtbl;
+}
+
+/* Given a vtable (often result of build_vtbl_ref (instance)), return the
+ element corresponding to IDX. */
+
+tree
+build_vtbl_element_from_vtbl_ref (tree vtbl, tree idx)
+{
+ tree aref = build_array_ref (input_location, vtbl, idx);
TREE_CONSTANT (aref) |= TREE_CONSTANT (vtbl) && TREE_CONSTANT (idx);
return aref;
}
+/* Given an object INSTANCE, return an expression which yields the
+ vtable element corresponding to IDX. */
+
+tree
+build_vtbl_ref (tree instance, tree idx)
+{
+ return build_vtbl_element_from_vtbl_ref (build_vtbl_ref (instance), idx);
+}
+
/* Given a stable object pointer INSTANCE_PTR, return an expression which
yields a function pointer corresponding to vtable element INDEX. */
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 1ac31d073d1..fc6cf716881 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -6867,6 +6867,8 @@ extern tree convert_to_base (tree, tree, bool, bool,
tsubst_flags_t);
extern tree convert_to_base_statically (tree, tree);
extern bool is_empty_base_ref (tree);
+extern tree build_vtbl_ref (tree);
+extern tree build_vtbl_element_from_vtbl_ref (tree, tree);
extern tree build_vtbl_ref (tree, tree);
extern tree build_vfn_ref (tree, tree);
extern tree get_vtable_decl (tree, int);
diff --git a/gcc/cp/rtti.cc b/gcc/cp/rtti.cc
index ed69606f4dd..72c0c4abaab 100644
--- a/gcc/cp/rtti.cc
+++ b/gcc/cp/rtti.cc
@@ -29,6 +29,7 @@ along with GCC; see the file COPYING3. If not see
#include "intl.h"
#include "stor-layout.h"
#include "c-family/c-pragma.h"
+#include "gimplify.h"
#include "gcc-rich-location.h"
/* C++ returns type information to the user in struct type_info
@@ -256,14 +257,18 @@ get_void_tinfo_ptr (tree type)
/* Return an lvalue expression whose type is "const std::type_info"
and whose value indicates the type of the expression EXP. If EXP
is a reference to a polymorphic class, return the dynamic type;
- otherwise return the static type of the expression. */
+ otherwise return the static type of the expression.
+ If vptr is not NULL, set vptr to be the virtual pointer table. */
static tree
-get_tinfo_decl_dynamic (tree exp, tsubst_flags_t complain)
+get_tinfo_decl_dynamic (tree exp, tsubst_flags_t complain, tree *vptr)
{
tree type;
tree t;
+ if (vptr)
+ *vptr = error_mark_node;
+
if (error_operand_p (exp))
return error_mark_node;
@@ -292,12 +297,27 @@ get_tinfo_decl_dynamic (tree exp, tsubst_flags_t complain)
/* The RTTI information is at index -1. */
index = build_int_cst (NULL_TREE,
-1 * TARGET_VTABLE_DATA_ENTRY_DISTANCE);
- t = build_vtbl_ref (exp, index);
+ if (vptr)
+ {
+ *vptr = save_expr (build_vtbl_ref (exp));
+ t = build_vtbl_element_from_vtbl_ref (*vptr, index);
+ }
+ else
+ t = build_vtbl_ref (exp, index);
t = convert (type_info_ptr_type (), t);
}
else
- /* Otherwise return the type_info for the static type of the expr. */
- t = get_tinfo_ptr (type);
+ {
+ /* Otherwise return the type_info for the static type of the expr. */
+ t = get_tinfo_ptr (type);
+ if (vptr)
+ {
+ if (TYPE_POLYMORPHIC_P (type))
+ *vptr = unshare_expr (BINFO_VTABLE (TYPE_BINFO (type))); // TODO why need unshare_expr actually?
+ else
+ *vptr = null_pointer_node;
+ }
+ }
return cp_build_fold_indirect_ref (t);
}
@@ -342,6 +362,21 @@ typeid_ok_p (void)
return true;
}
+/* Given exp of type "const std::type_info &",
+ return an expression of the form TYPEID_WITH_VPTR_TAG (exp, vptr)
+ which is equivalent to exp for all purpose except for the
+ devirtualize typeid phase which uses the additional vptr information. */
+
+tree
+tag_typeid_with_vptr (tree exp, tree vptr)
+{
+ return build_call_expr_internal_loc (UNKNOWN_LOCATION,
+ IFN_TYPEID_WITH_VPTR_TAG,
+ cp_build_reference_type (TREE_TYPE (exp), /*rval*/false),
+ 2, build_address (exp), vptr);
+ // TODO what's wrong with build_address function being low-level?
+}
+
/* Return an expression for "typeid(EXP)". The expression returned is
an lvalue of type "const std::type_info". */
@@ -369,7 +404,8 @@ build_typeid (tree exp, tsubst_flags_t complain)
exp = cp_build_fold_indirect_ref (exp);
}
- exp = get_tinfo_decl_dynamic (exp, complain);
+ tree vptr;
+ exp = get_tinfo_decl_dynamic (exp, complain, &vptr);
if (exp == error_mark_node)
return error_mark_node;
@@ -383,6 +419,10 @@ build_typeid (tree exp, tsubst_flags_t complain)
else
mark_type_use (initial_expr);
+ exp = tag_typeid_with_vptr (exp, vptr);
+ // TODO this is dangerous because subsequent passes need to make sure the
+ // second argument (vptr) is not evaluated when the pointer is null
+
return exp;
}
@@ -499,6 +539,27 @@ get_tinfo_decl_direct (tree type, tree name, int pseudo_ix)
return d;
}
+/* Return the pointer to the vtable for a type.
+ The pointer points to the middle of the vtable, just after the pointer to
+ the typeinfo object.
+ To build the expression for the vtable pointer from an instance of a
+ polymorphic type, use build_vtbl_ref. */
+
+tree
+get_vtable_ptr (tree type)
+{
+ tree vtable_ptr = get_vtable_decl (type, /*complete=*/1);
+ vtable_ptr = cp_build_addr_expr (vtable_ptr, tf_warning_or_error);
+
+ /* We need to point into the middle of the vtable. */
+ vtable_ptr = fold_build_pointer_plus
+ (vtable_ptr,
+ size_binop (MULT_EXPR,
+ size_int (2 * TARGET_VTABLE_DATA_ENTRY_DISTANCE),
+ TYPE_SIZE_UNIT (vtable_entry_type)));
+ return vtable_ptr;
+}
+
/* Return the type_info object for TYPE. */
tree
@@ -537,7 +598,8 @@ get_typeid (tree type, tsubst_flags_t complain)
if (!type)
return error_mark_node;
- return cp_build_fold_indirect_ref (get_tinfo_ptr (type));
+ return tag_typeid_with_vptr
+ (cp_build_fold_indirect_ref (get_tinfo_ptr (type)), get_vtable_ptr (type));
}
/* Check whether TEST is null before returning RESULT. If TEST is used in
@@ -980,16 +1042,7 @@ tinfo_base_init (tinfo_s *ti, tree target)
CLASSTYPE_INTERFACE_ONLY (real_type) = 1;
}
- vtable_ptr = get_vtable_decl (real_type, /*complete=*/1);
- vtable_ptr = cp_build_addr_expr (vtable_ptr, tf_warning_or_error);
-
- /* We need to point into the middle of the vtable. */
- vtable_ptr = fold_build_pointer_plus
- (vtable_ptr,
- size_binop (MULT_EXPR,
- size_int (2 * TARGET_VTABLE_DATA_ENTRY_DISTANCE),
- TYPE_SIZE_UNIT (vtable_entry_type)));
-
+ vtable_ptr = get_vtable_ptr (real_type);
ti->vtable = vtable_ptr;
}
diff --git a/gcc/cp/typeck.cc b/gcc/cp/typeck.cc
index 5970ac3d398..e5c40237b2b 100644
--- a/gcc/cp/typeck.cc
+++ b/gcc/cp/typeck.cc
@@ -4713,6 +4713,42 @@ build_x_binary_op (const op_location_t &loc, enum tree_code code, tree arg1,
enum tree_code arg2_code, tree lookups,
tree *overload_p, tsubst_flags_t complain)
{
+ if (TREE_CODE (arg1) == CALL_EXPR
+ && CALL_EXPR_IFN (arg1) == IFN_TYPEID_WITH_VPTR_TAG
+ && TREE_CODE (arg2) == CALL_EXPR
+ && CALL_EXPR_IFN (arg2) == IFN_TYPEID_WITH_VPTR_TAG)
+ {
+ if (code == EQ_EXPR)
+ {
+ /* When "typeid(a) == typeid(b)" is seen, build_typeid generated
+ arg1 = TYPEID_WITH_VPTR_TAG (&a.vptr[-1], a.vptr)
+ arg2 = TYPEID_WITH_VPTR_TAG (&b.vptr[-1], b.vptr)
+ we want to generate
+ a.vptr[-1] == b.vptr[-1] && VPTR_EQUIV (a.vptr, b.vptr). */
+ return
+ build_x_binary_op (UNKNOWN_LOCATION, TRUTH_ANDIF_EXPR,
+ build_x_binary_op (loc, EQ_EXPR,
+ cp_build_fold_indirect_ref (CALL_EXPR_ARG (arg1, 0)), arg1_code,
+ cp_build_fold_indirect_ref (CALL_EXPR_ARG (arg2, 0)), arg2_code,
+ lookups, overload_p, complain),
+ ERROR_MARK,
+ build_call_expr_internal_loc (UNKNOWN_LOCATION, IFN_VPTR_EQUIV,
+ boolean_type_node,
+ 2, CALL_EXPR_ARG (arg1, 1), CALL_EXPR_ARG (arg2, 1)),
+ ERROR_MARK,
+ lookups, overload_p, complain);
+ }
+ if (code == NE_EXPR)
+ {
+ /* Similar to above but handle the case "typeid(a) != typeid(b)". */
+ return
+ build_x_unary_op (UNKNOWN_LOCATION, TRUTH_NOT_EXPR,
+ build_x_binary_op (loc, EQ_EXPR, arg1, arg1_code,
+ arg2, arg2_code,
+ lookups, overload_p, complain),
+ lookups, complain);
+ }
+ }
tree orig_arg1;
tree orig_arg2;
tree expr;
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index a511a2c3a4c..d4dd10a7687 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -949,7 +949,8 @@ update_list::pop ()
// --------------------------------------------------------------------------
-ranger_cache::ranger_cache (int not_executable_flag, bool use_imm_uses)
+ranger_cache::ranger_cache (int not_executable_flag, bool use_imm_uses,
+ bool do_devirtualize_typeid)
{
m_workback.create (0);
m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
@@ -959,7 +960,8 @@ ranger_cache::ranger_cache (int not_executable_flag, bool use_imm_uses)
// If DOM info is available, spawn an oracle as well.
create_relation_oracle ();
create_infer_oracle (use_imm_uses);
- create_gori (not_executable_flag, param_vrp_switch_limit);
+ create_gori (not_executable_flag, param_vrp_switch_limit,
+ do_devirtualize_typeid);
unsigned x, lim = last_basic_block_for_fn (cfun);
// Calculate outgoing range info upfront. This will fully populate the
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index c7499f928a9..311ac78d435 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -98,7 +98,8 @@ protected:
class ranger_cache : public range_query
{
public:
- ranger_cache (int not_executable_flag, bool use_imm_uses);
+ ranger_cache (int not_executable_flag, bool use_imm_uses,
+ bool do_devirtualize_typeid);
~ranger_cache ();
bool range_of_expr (vrange &r, tree name, gimple *stmt) final override;
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index d489aef312c..e3bbb2270bc 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -27,7 +27,9 @@ along with GCC; see the file COPYING3. If not see
#include "gimple.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
+#include "gimple-iterator.h"
#include "gimple-range.h"
+#include "tree-cfg.h"
// Return TRUE if GS is a logical && or || expression.
@@ -356,7 +358,8 @@ range_def_chain::dump (FILE *f, basic_block bb, const char *prefix)
// Initialize a gori-map structure.
-gori_map::gori_map ()
+gori_map::gori_map (bool do_devirtualize_typeid)
+ : m_do_devirtualize_typeid (do_devirtualize_typeid)
{
m_outgoing.create (0);
m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
@@ -558,8 +561,9 @@ debug (gori_map &g)
// Construct a gori_compute object.
gori_compute::gori_compute (gori_map &map, int not_executable_flag,
- int sw_max_edges)
- : gimple_outgoing_range (sw_max_edges), m_map (map), tracer ("GORI ")
+ int sw_max_edges, bool do_devirtualize_typeid)
+ : gimple_outgoing_range (sw_max_edges), m_map (map),
+ tracer ("GORI "), m_do_devirtualize_typeid (do_devirtualize_typeid)
{
m_not_executable_flag = not_executable_flag;
// Create a boolean_type true and false range.
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index 11019e38471..4080ec34653 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -93,7 +93,7 @@ range_def_chain::depend2 (tree name) const
class gori_map : public range_def_chain
{
public:
- gori_map ();
+ gori_map (bool do_devirtualize_typeid);
~gori_map ();
bool is_export_p (tree name, basic_block bb = NULL);
@@ -108,6 +108,7 @@ private:
vec<bitmap> m_outgoing; // BB: Outgoing ranges calculable on edges
vec<bitmap> m_incoming; // BB: Incoming ranges which can affect exports.
bitmap m_maybe_variant; // Names which might have outgoing ranges.
+ bool m_do_devirtualize_typeid;
void maybe_add_gori (tree name, basic_block bb);
void calculate_gori (basic_block bb);
};
@@ -165,7 +166,7 @@ class gori_compute : public gimple_outgoing_range
{
public:
gori_compute (gori_map &map, int not_executable_flag = 0,
- int max_sw_edges = 0);
+ int max_sw_edges = 0, bool do_devirtualize_typeid = false);
virtual ~gori_compute ();
bool edge_range_p (vrange &r, edge e, tree name, range_query &q);
bool has_edge_range_p (tree name, basic_block bb = NULL);
@@ -206,6 +207,7 @@ private:
range_tracer tracer;
int m_not_executable_flag;
+ bool m_do_devirtualize_typeid;
};
// These APIs are used to query GORI if there are ranges generated on an edge.
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index be22bb4aa18..fcff29971fa 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -37,9 +37,9 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-fold.h"
#include "gimple-walk.h"
-gimple_ranger::gimple_ranger (bool use_imm_uses) :
+gimple_ranger::gimple_ranger (bool use_imm_uses, bool do_devirtualize_typeid) :
non_executable_edge_flag (cfun),
- m_cache (non_executable_edge_flag, use_imm_uses),
+ m_cache (non_executable_edge_flag, use_imm_uses, do_devirtualize_typeid),
tracer (""),
current_bb (NULL)
{
@@ -697,14 +697,15 @@ gimple_ranger::debug ()
resources. */
gimple_ranger *
-enable_ranger (struct function *fun, bool use_imm_uses)
+enable_ranger (struct function *fun, bool use_imm_uses,
+ bool do_devirtualize_typeid)
{
gimple_ranger *r;
bitmap_obstack_initialize (NULL);
gcc_checking_assert (!fun->x_range_query);
- r = new gimple_ranger (use_imm_uses);
+ r = new gimple_ranger (use_imm_uses, do_devirtualize_typeid);
fun->x_range_query = r;
return r;
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 180090bed15..a33b63d4864 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -47,7 +47,7 @@ along with GCC; see the file COPYING3. If not see
class gimple_ranger : public range_query
{
public:
- gimple_ranger (bool use_imm_uses = true);
+ gimple_ranger (bool use_imm_uses = true, bool do_devirtualize_typeid = false);
~gimple_ranger ();
virtual bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override;
virtual bool range_of_expr (vrange &r, tree name, gimple * = NULL) override;
@@ -79,7 +79,8 @@ protected:
resources. If USE_IMM_USES is true, pre-calculate side effects like
non-null uses as required using the immediate use chains. */
extern gimple_ranger *enable_ranger (struct function *m,
- bool use_imm_uses = true);
+ bool use_imm_uses = true,
+ bool do_devirtualize_typeid = false);
extern void disable_ranger (struct function *);
class assume_query : public range_query
diff --git a/gcc/internal-fn.cc b/gcc/internal-fn.cc
index 4948b48bde8..5eb46b70ec7 100644
--- a/gcc/internal-fn.cc
+++ b/gcc/internal-fn.cc
@@ -5076,6 +5076,28 @@ expand_SPACESHIP (internal_fn, gcall *stmt)
emit_move_insn (target, ops[0].value);
}
+void
+expand_TYPEID_WITH_VPTR_TAG (internal_fn, gcall *stmt)
+{
+ /* TYPEID_WITH_VPTR_TAG (typeinfo, vptr) = typeinfo.
+ Do not evaluate the second operand, because the instance might be null.
+ It might have been a better idea to kill all occurrences of this tree node
+ in GIMPLE pass instead. */
+ tree lhs = gimple_call_lhs (stmt);
+ rtx target = expand_expr (lhs, NULL_RTX, VOIDmode, EXPAND_WRITE);
+ rtx val = expand_normal (gimple_call_arg (stmt, 0));
+ emit_move_insn (target, val);
+}
+
+void
+expand_VPTR_EQUIV (internal_fn, gcall *stmt)
+{
+ /* VPTR_EQUIV (a, b) = true. */
+ tree lhs = gimple_call_lhs (stmt);
+ rtx target = expand_expr (lhs, NULL_RTX, VOIDmode, EXPAND_WRITE);
+ emit_move_insn (target, const_true_rtx);
+}
+
void
expand_ASSUME (internal_fn, gcall *)
{
diff --git a/gcc/internal-fn.def b/gcc/internal-fn.def
index a8c83437ada..622f6afad08 100644
--- a/gcc/internal-fn.def
+++ b/gcc/internal-fn.def
@@ -593,6 +593,10 @@ DEF_INTERNAL_FN (DIVMODBITINT, ECF_LEAF, ". O . O . R . R . ")
DEF_INTERNAL_FN (FLOATTOBITINT, ECF_LEAF | ECF_NOTHROW, ". O . . ")
DEF_INTERNAL_FN (BITINTTOFLOAT, ECF_PURE | ECF_LEAF, ". R . ")
+/* For the devirtualize-by-typeid optimization pass. */
+DEF_INTERNAL_FN (TYPEID_WITH_VPTR_TAG, ECF_CONST, NULL)
+DEF_INTERNAL_FN (VPTR_EQUIV, ECF_CONST, NULL)
+
#undef DEF_INTERNAL_WIDENING_OPTAB_FN
#undef DEF_INTERNAL_SIGNED_COND_FN
#undef DEF_INTERNAL_COND_FN
diff --git a/gcc/internal-fn.h b/gcc/internal-fn.h
index 2785a5a95a2..6825b40f25e 100644
--- a/gcc/internal-fn.h
+++ b/gcc/internal-fn.h
@@ -255,6 +255,8 @@ extern void expand_internal_call (internal_fn, gcall *);
extern void expand_PHI (internal_fn, gcall *);
extern void expand_SHUFFLEVECTOR (internal_fn, gcall *);
extern void expand_SPACESHIP (internal_fn, gcall *);
+extern void expand_TYPEID_WITH_VPTR_TAG (internal_fn, gcall *);
+extern void expand_VPTR_EQUIV (internal_fn, gcall *);
extern void expand_TRAP (internal_fn, gcall *);
extern void expand_ASSUME (internal_fn, gcall *);
extern void expand_MASK_CALL (internal_fn, gcall *);
diff --git a/gcc/passes.def b/gcc/passes.def
index 1cbbd413097..27b6276ab70 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -93,6 +93,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_phiprop);
NEXT_PASS (pass_fre, true /* may_iterate */);
NEXT_PASS (pass_early_vrp);
+ NEXT_PASS (pass_devirtualize_by_typeid);
NEXT_PASS (pass_merge_phi);
NEXT_PASS (pass_dse);
NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */);
diff --git a/gcc/testsuite/g++.dg/tree-ssa/devirt-typeid.C b/gcc/testsuite/g++.dg/tree-ssa/devirt-typeid.C
new file mode 100644
index 00000000000..1e1a3a5b563
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/devirt-typeid.C
@@ -0,0 +1,56 @@
+// PR c++/115413
+/* typeid equality should allow for devirtualization of function call */
+/* { dg-do-compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+#include <typeinfo>
+
+struct A
+{
+ virtual void f();
+};
+
+void
+test1 (A &a)
+{
+ if (typeid (a) != typeid (A))
+ __builtin_unreachable();
+ a.f ();
+}
+
+void
+test2 (A &a)
+{
+ if (typeid (a) == typeid (A))
+ a.f ();
+ else
+ __builtin_unreachable();
+}
+
+void
+test3 (A &a)
+{
+ A b;
+ if (typeid (a) == typeid (b))
+ a.f ();
+ else
+ __builtin_unreachable();
+}
+
+void
+test4 (A *a)
+{
+ A b;
+ if (typeid (*a) == typeid (b)) // may throw bad_typeid if !a
+ a->f ();
+ else
+ __builtin_unreachable();
+}
+
+void
+test5 (A &a)
+{
+ a.f (); // this call cannot be devirtualized
+}
+
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 1 "optimized"} } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 8e2168e0817..e31524727fa 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -160,6 +160,7 @@ DEFTIMEVAR (TV_TREE_TAIL_MERGE , "tree tail merge")
DEFTIMEVAR (TV_TREE_VRP , "tree VRP")
DEFTIMEVAR (TV_TREE_VRP_THREADER , "tree VRP threader")
DEFTIMEVAR (TV_TREE_EARLY_VRP , "tree Early VRP")
+DEFTIMEVAR (TV_TREE_DEVIRT_TYPEID , "tree devirtualize by typeid")
DEFTIMEVAR (TV_TREE_FAST_VRP , "tree Fast VRP")
DEFTIMEVAR (TV_TREE_COPY_PROP , "tree copy propagation")
DEFTIMEVAR (TV_FIND_REFERENCED_VARS , "tree find ref. vars")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 29267589eeb..9fb403c32bc 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -471,6 +471,7 @@ extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_early_vrp (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_devirtualize_by_typeid (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_fast_vrp (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_assumptions (gcc::context *ctxt);
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 1c7b451d8fb..abd5b1d93ab 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -1000,13 +1000,14 @@ class rvrp_folder : public substitute_and_fold_engine
{
public:
- rvrp_folder (gimple_ranger *r, bool all)
+ rvrp_folder (gimple_ranger *r, bool all, bool do_devirtualize_typeid)
: substitute_and_fold_engine (),
m_unreachable (*r, all),
- m_simplifier (r, r->non_executable_edge_flag)
+ m_simplifier (r, r->non_executable_edge_flag),
+ m_do_devirtualize_typeid (do_devirtualize_typeid)
{
m_ranger = r;
- m_pta = new pointer_equiv_analyzer (m_ranger);
+ m_pta = new pointer_equiv_analyzer (m_ranger, m_do_devirtualize_typeid);
m_last_bb_stmt = NULL;
}
@@ -1089,6 +1090,7 @@ private:
simplify_using_ranges m_simplifier;
pointer_equiv_analyzer *m_pta;
gimple *m_last_bb_stmt;
+ bool m_do_devirtualize_typeid;
};
/* Main entry point for a VRP pass using just ranger. This can be called
@@ -1096,7 +1098,7 @@ private:
unsigned int
execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p,
- bool final_p)
+ bool final_p, bool do_devirtualize_typeid)
{
loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
@@ -1104,8 +1106,8 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p,
calculate_dominance_info (CDI_DOMINATORS);
set_all_edges_as_executable (fun);
- gimple_ranger *ranger = enable_ranger (fun, false);
- rvrp_folder folder (ranger, final_p);
+ gimple_ranger *ranger = enable_ranger (fun, false, do_devirtualize_typeid);
+ rvrp_folder folder (ranger, final_p, do_devirtualize_typeid);
phi_analysis_initialize (ranger->const_query ());
folder.substitute_and_fold ();
// Remove tagged builtin-unreachable and maybe update globals.
@@ -1313,6 +1315,19 @@ const pass_data pass_data_early_vrp =
( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
};
+const pass_data pass_data_devirtualize_by_typeid =
+{
+ GIMPLE_PASS, /* type */
+ "devirt_typeid", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_DEVIRT_TYPEID, /* tv_id */
+ PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
+};
+
const pass_data pass_data_fast_vrp =
{
GIMPLE_PASS, /* type */
@@ -1349,8 +1364,8 @@ public:
// Check for fast vrp.
if (&data == &pass_data_fast_vrp)
return execute_fast_vrp (fun);
-
- return execute_ranger_vrp (fun, warn_array_bounds_p, final_p);
+ return execute_ranger_vrp (fun, warn_array_bounds_p, final_p,
+ &data == &pass_data_devirtualize_by_typeid);
}
private:
@@ -1435,6 +1450,12 @@ make_pass_early_vrp (gcc::context *ctxt)
return new pass_vrp (ctxt, pass_data_early_vrp, false);
}
+gimple_opt_pass *
+make_pass_devirtualize_by_typeid (gcc::context *ctxt)
+{
+ return new pass_vrp (ctxt, pass_data_devirtualize_by_typeid, false);
+}
+
gimple_opt_pass *
make_pass_fast_vrp (gcc::context *ctxt)
{
diff --git a/gcc/value-pointer-equiv.cc b/gcc/value-pointer-equiv.cc
index bfc940ec991..0c63cf2e669 100644
--- a/gcc/value-pointer-equiv.cc
+++ b/gcc/value-pointer-equiv.cc
@@ -121,11 +121,13 @@ ssa_equiv_stack::get_replacement (tree name)
return m_replacements[v];
}
-pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r)
+pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r,
+ bool do_devirtualize_typeid)
{
m_ranger = r;
m_global_points.safe_grow_cleared (num_ssa_names + 1);
m_cond_points = new ssa_equiv_stack;
+ m_do_devirtualize_typeid = do_devirtualize_typeid;
}
pointer_equiv_analyzer::~pointer_equiv_analyzer ()
@@ -302,6 +304,28 @@ pointer_equiv_analyzer::visit_stmt (gimple *stmt)
void
pointer_equiv_analyzer::visit_edge (edge e)
{
+ if (m_do_devirtualize_typeid)
+ {
+ gcall *stmt;
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb (e->src); !gsi_end_p (gsi); gsi_next (&gsi))
+ // if the statement of the form IFN_VPTR_EQUIV (a, b) then
+ // deduce that a is equal to b
+ if ((stmt = safe_dyn_cast<gcall *> (gsi_stmt (gsi)))
+ && gimple_call_internal_p (stmt)
+ && gimple_call_internal_fn (stmt) == IFN_VPTR_EQUIV)
+ {
+ tree op1 = gimple_call_arg (stmt, 0);
+ tree op2 = gimple_call_arg (stmt, 1);
+ if (TREE_CODE (op2) == SSA_NAME)
+ std::swap (op1, op2);
+ if (TREE_CODE (op1) == SSA_NAME && TREE_CODE (op2) == ADDR_EXPR)
+ {
+ set_cond_equiv (op1, op2);
+ }
+ }
+ }
+
gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (e->src));
tree lhs;
// Recognize: x_13 [==,!=] &foo.
diff --git a/gcc/value-pointer-equiv.h b/gcc/value-pointer-equiv.h
index 8a04bbb6742..feec1c6835a 100644
--- a/gcc/value-pointer-equiv.h
+++ b/gcc/value-pointer-equiv.h
@@ -33,7 +33,7 @@ along with GCC; see the file COPYING3. If not see
class pointer_equiv_analyzer
{
public:
- pointer_equiv_analyzer (gimple_ranger *r);
+ pointer_equiv_analyzer (gimple_ranger *r, bool do_devirtualize_typeid);
~pointer_equiv_analyzer ();
void enter (basic_block);
void leave (basic_block);
@@ -51,6 +51,7 @@ private:
auto_vec<tree> m_global_points;
// Conditional pointer equivalency.
class ssa_equiv_stack *m_cond_points;
+ bool m_do_devirtualize_typeid;
};
inline bool
diff --git a/gcc/value-query.cc b/gcc/value-query.cc
index 556a0f39b09..acec91d666a 100644
--- a/gcc/value-query.cc
+++ b/gcc/value-query.cc
@@ -185,13 +185,15 @@ infer_range_oracle default_infer_oracle;
gimple_outgoing_range default_gori;
void
-range_query::create_gori (int not_executable_flag, int sw_max_edges)
+range_query::create_gori (int not_executable_flag, int sw_max_edges,
+ bool do_devirtualize_typeid)
{
gcc_checking_assert (m_gori == &default_gori);
gcc_checking_assert (m_map == NULL);
- m_map = new gori_map ();
+ m_map = new gori_map (do_devirtualize_typeid);
gcc_checking_assert (m_map);
- m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
+ m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges,
+ do_devirtualize_typeid);
gcc_checking_assert (m_gori);
}
diff --git a/gcc/value-query.h b/gcc/value-query.h
index 2572a03095d..f41d457b4c7 100644
--- a/gcc/value-query.h
+++ b/gcc/value-query.h
@@ -85,7 +85,8 @@ public:
inline class gimple_outgoing_range &gori () const { return *m_gori; }
inline class gori_map *gori_ssa () const { return m_map; }
- void create_gori (int not_executable_flag = 0, int sw_max_edges = INT_MAX);
+ void create_gori (int not_executable_flag = 0, int sw_max_edges = INT_MAX,
+ bool do_devirtualize_typeid = false);
void destroy_gori ();
virtual void dump (FILE *);
--
2.34.1
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2024-06-24 10:28 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-06-24 10:28 [PATCH] Implement devirtualize by typeid optimization pass user202729
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).