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
@@ -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. */
@@ -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);
@@ -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;
}
@@ -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;
@@ -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
@@ -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;
@@ -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.
@@ -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.
@@ -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;
@@ -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
@@ -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 *)
{
@@ -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
@@ -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 *);
@@ -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 */);
new file mode 100644
@@ -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"} } */
@@ -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")
@@ -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);
@@ -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)
{
@@ -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.
@@ -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
@@ -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);
}
@@ -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