Type inheritance graph analysis & speculative devirtualization, part 4/7 (the verifier)

[Jan Hubicka]

Hi,
this is the last patch of the series.

This patch adds sanity check that all devirtualizations are among ones
predicted by possible_polymorphic_call_targets.  This sanity check was
very useful to chase out numberous problems in this area.

The patch check the type based devirtualization to go in the directions
predicted, but it also reality checks agains folding based devirt.  In my
tree I use gcc_assert.  I turned it into dump only, since i think it
is matter of time until someone construct type inconsistent testcase that
uses virtual table of completely incompatible class to resolve the call.

I was thinking about making this a warning, but I am not sure how useful
it would be (except for my sanity check) and whether we would not run into
problems with fase positives on specialized code pretty much as we do with
all the backend warnings.

So for now i am just dumping and will keep it an assert in my local tree.

I am still not enabling the check in full strength - we build type inheritance
graph based on defined methods in the unit.  We however ignore types that has
only external methods and thus it is possible that new external calls will be
discovered.  This is solved by an incremental patch.

Bootstrapped/regtested x86_64-linux, will commit it shortly.

Honza

	* ipa-cp.c (ipa_get_indirect_edge_target_1): Add sanity check
	for ipa-devirt.
	* ipa-utils.h (possible_polymorphic_call_target_p): New function.
	* ipa-devirt.c (possible_polymorphic_call_target_p): Be tolerant
	of external calls
	* gimple-fold.c: Include ipa-utils.h and gimple-pretty-print.h
	(gimple_fold_call): Dump inconsistent devirtualizations; add
	sanity check for type based devirtualizations.
	* ipa-prop.c: Include ipa-utils.h
	(ipa_intraprocedural_devirtualization): Add sanity check.
	(try_make_edge_direct_virtual_call): Likewise.

Index: ipa-cp.c
===================================================================
--- ipa-cp.c	(revision 202812)
+++ ipa-cp.c	(working copy)
@@ -1484,6 +1484,7 @@ ipa_get_indirect_edge_target_1 (struct c
   HOST_WIDE_INT token, anc_offset;
   tree otr_type;
   tree t;
+  tree target;
 
   if (param_index == -1
       || known_vals.length () <= (unsigned int) param_index)
@@ -1552,7 +1553,7 @@ ipa_get_indirect_edge_target_1 (struct c
       binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
       if (!binfo)
 	return NULL_TREE;
-      return gimple_get_virt_method_for_binfo (token, binfo);
+      target = gimple_get_virt_method_for_binfo (token, binfo);
     }
   else
     {
@@ -1561,8 +1562,15 @@ ipa_get_indirect_edge_target_1 (struct c
       binfo = get_binfo_at_offset (t, anc_offset, otr_type);
       if (!binfo)
 	return NULL_TREE;
-      return gimple_get_virt_method_for_binfo (token, binfo);
+      target = gimple_get_virt_method_for_binfo (token, binfo);
     }
+#ifdef ENABLE_CHECKING
+  if (target)
+    gcc_assert (possible_polymorphic_call_target_p
+		 (ie, cgraph_get_node (target)));
+#endif
+
+  return target;
 }
 
 
Index: ipa-utils.h
===================================================================
--- ipa-utils.h	(revision 202812)
+++ ipa-utils.h	(working copy)
@@ -108,6 +108,19 @@ possible_polymorphic_call_target_p (stru
   return possible_polymorphic_call_target_p (e->indirect_info->otr_type,
 					     e->indirect_info->otr_token, n);
 }
+
+/* Return true if N can be possibly target of a polymorphic call of
+   OBJ_TYPE_REF expression CALL.  */
+
+inline bool
+possible_polymorphic_call_target_p (tree call,
+				    struct cgraph_node *n)
+{
+  return possible_polymorphic_call_target_p (obj_type_ref_class (call),
+					     tree_low_cst
+						(OBJ_TYPE_REF_TOKEN (call), 1),
+					     n);
+}
 #endif  /* GCC_IPA_UTILS_H  */
 
 
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c	(revision 202812)
+++ ipa-devirt.c	(working copy)
@@ -905,13 +905,19 @@ possible_polymorphic_call_target_p (tree
 {
   vec <cgraph_node *> targets;
   unsigned int i;
+  bool final;
 
   if (!odr_hash.is_created ())
     return true;
-  targets = possible_polymorphic_call_targets (otr_type, otr_token);
+  targets = possible_polymorphic_call_targets (otr_type, otr_token, &final);
   for (i = 0; i < targets.length (); i++)
     if (n == targets[i])
       return true;
+
+  /* At a moment we allow middle end to dig out new external declarations
+     as a targets of polymorphic calls.  */
+  if (!final && !n->symbol.definition)
+    return true;
   return false;
 }
 
Index: gimple-fold.c
===================================================================
--- gimple-fold.c	(revision 202812)
+++ gimple-fold.c	(working copy)
@@ -30,6 +30,8 @@ along with GCC; see the file COPYING3.
 #include "tree-ssa-propagate.h"
 #include "target.h"
 #include "gimple-fold.h"
+#include "ipa-utils.h"
+#include "gimple-pretty-print.h"
 
 /* Return true when DECL can be referenced from current unit.
    FROM_DECL (if non-null) specify constructor of variable DECL was taken from.
@@ -1116,6 +1118,19 @@ gimple_fold_call (gimple_stmt_iterator *
     {
       if (gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee)) != NULL_TREE)
 	{
+          if (dump_file && virtual_method_call_p (callee)
+	      && !possible_polymorphic_call_target_p
+		    (callee, cgraph_get_node (gimple_call_addr_fndecl
+                                                 (OBJ_TYPE_REF_EXPR (callee)))))
+	    {
+	      fprintf (dump_file,
+		       "Type inheritnace inconsistent devirtualization of ");
+	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	      fprintf (dump_file, " to ");
+	      print_generic_expr (dump_file, callee, TDF_SLIM);
+	      fprintf (dump_file, "\n");
+	    }
+
 	  gimple_call_set_fn (stmt, OBJ_TYPE_REF_EXPR (callee));
 	  changed = true;
 	}
@@ -1131,6 +1146,11 @@ gimple_fold_call (gimple_stmt_iterator *
 	      tree fndecl = gimple_get_virt_method_for_binfo (token, binfo);
 	      if (fndecl)
 		{
+#ifdef ENABLE_CHECKING
+		  gcc_assert (possible_polymorphic_call_target_p
+				 (callee, cgraph_get_node (fndecl)));
+
+#endif
 		  gimple_call_set_fndecl (stmt, fndecl);
 		  changed = true;
 		}
Index: ipa-prop.c
===================================================================
--- ipa-prop.c	(revision 202812)
+++ ipa-prop.c	(working copy)
@@ -38,6 +38,7 @@ along with GCC; see the file COPYING3.
 #include "data-streamer.h"
 #include "tree-streamer.h"
 #include "params.h"
+#include "ipa-utils.h"
 
 /* Intermediate information about a parameter that is only useful during the
    run of ipa_analyze_node and is not kept afterwards.  */
@@ -2196,6 +2197,11 @@ ipa_intraprocedural_devirtualization (gi
   token = OBJ_TYPE_REF_TOKEN (otr);
   fndecl = gimple_get_virt_method_for_binfo (tree_low_cst (token, 1),
 					     binfo);
+#ifdef ENABLE_CHECKING
+  if (fndecl)
+    gcc_assert (possible_polymorphic_call_target_p
+		  (otr, cgraph_get_node (fndecl)));
+#endif
   return fndecl;
 }
 
@@ -2651,7 +2657,13 @@ try_make_edge_direct_virtual_call (struc
     return NULL;
 
   if (target)
-    return ipa_make_edge_direct_to_target (ie, target);
+    {
+#ifdef ENABLE_CHECKING
+      gcc_assert (possible_polymorphic_call_target_p
+	 (ie, cgraph_get_node (target)));
+#endif
+      return ipa_make_edge_direct_to_target (ie, target);
+    }
   else
     return NULL;
 }