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

