2016-03-30 Michael Matz <matz@suse.de>

	Richard Biener  <rguenther@suse.de>

	PR ipa/12392
	* ipa-polymorphic-call.c (struct type_change_info): Change
	speculative to an unsigned allowing to limit the work we do.
	(csftc_abort_walking_p): New inline function..
	(check_stmt_for_type_change): Limit the number of may-defs
	skipped for speculative devirtualization to
	max-speculative-devirt-maydefs.
	* params.def (max-speculative-devirt-maydefs): New param.
	* doc/invoke.texi (--param max-speculative-devirt-maydefs): Document.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@234546 138bc75d-0d04-0410-961f-82ee72b054a4

4 files changed, 52 insertions, 13 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 40fddc4007e..f09c0a02638 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,16 @@
+2016-03-30  Michael Matz  <matz@suse.de>
+	Richard Biener  <rguenther@suse.de>
+
+	PR ipa/12392
+	* ipa-polymorphic-call.c (struct type_change_info): Change
+	speculative to an unsigned allowing to limit the work we do.
+	(csftc_abort_walking_p): New inline function..
+	(check_stmt_for_type_change): Limit the number of may-defs
+	skipped for speculative devirtualization to
+	max-speculative-devirt-maydefs.
+	* params.def (max-speculative-devirt-maydefs): New param.
+	* doc/invoke.texi (--param max-speculative-devirt-maydefs): Document.
+
 2016-03-30  Mike Stump  <mrs@gcc.gnu.org>
 
 	PR target/63890
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index ed1ad6214b2..e9763d44d8d 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -9601,6 +9601,11 @@ Enable emission of special debug stores within HSA kernels which are
 then read and reported by libgomp plugin.  Generation of these stores
 is disabled by default, use @option{--param hsa-gen-debug-stores=1} to
 enable it.
+
+@item max-speculative-devirt-maydefs
+The maximum number of may-defs we analyze when looking for a must-def
+specifying the dynamic type of an object that invokes a virtual call
+we may be able to devirtualize speculatively.
 @end table
 @end table
 
diff --git a/gcc/ipa-polymorphic-call.c b/gcc/ipa-polymorphic-call.c
index 842ca13cd06..0ebbd4ae66d 100644
--- a/gcc/ipa-polymorphic-call.c
+++ b/gcc/ipa-polymorphic-call.c
@@ -38,6 +38,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-dfa.h"
 #include "gimple-pretty-print.h"
 #include "tree-into-ssa.h"
+#include "params.h"
 
 /* Return true when TYPE contains an polymorphic type and thus is interesting
    for devirtualization machinery.  */
@@ -1094,14 +1095,15 @@ struct type_change_info
   tree known_current_type;
   HOST_WIDE_INT known_current_offset;
 
+  /* Set to nonzero if we possibly missed some dynamic type changes and we
+     should consider the set to be speculative.  */
+  unsigned speculative;
+
   /* Set to true if dynamic type change has been detected.  */
   bool type_maybe_changed;
   /* Set to true if multiple types have been encountered.  known_current_type
      must be disregarded in that case.  */
   bool multiple_types_encountered;
-  /* Set to true if we possibly missed some dynamic type changes and we should
-     consider the set to be speculative.  */
-  bool speculative;
   bool seen_unanalyzed_store;
 };
 
@@ -1338,6 +1340,19 @@ record_known_type (struct type_change_info *tci, tree type, HOST_WIDE_INT offset
   tci->type_maybe_changed = true;
 }
 
+
+/* The maximum number of may-defs we visit when looking for a must-def
+   that changes the dynamic type in check_stmt_for_type_change.  Tuned
+   after the PR12392 testcase which unlimited spends 40% time within
+   these alias walks and 8% with the following limit.  */
+
+static inline bool
+csftc_abort_walking_p (unsigned speculative)
+{
+  unsigned max = PARAM_VALUE (PARAM_MAX_SPECULATIVE_DEVIRT_MAYDEFS);
+  return speculative > max ? true : false;
+}
+
 /* Callback of walk_aliased_vdefs and a helper function for
    detect_type_change to check whether a particular statement may modify
    the virtual table pointer, and if possible also determine the new type of
@@ -1384,15 +1399,15 @@ check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
 					  &size, &max_size, &reverse);
 	    if (size != max_size || max_size == -1)
 	      {
-                tci->speculative = true;
-	        return false;
+                tci->speculative++;
+	        return csftc_abort_walking_p (tci->speculative);
 	      }
 	    if (op && TREE_CODE (op) == MEM_REF)
 	      {
 		if (!tree_fits_shwi_p (TREE_OPERAND (op, 1)))
 		  {
-                    tci->speculative = true;
-		    return false;
+                    tci->speculative++;
+		    return csftc_abort_walking_p (tci->speculative);
 		  }
 		offset += tree_to_shwi (TREE_OPERAND (op, 1))
 			  * BITS_PER_UNIT;
@@ -1402,8 +1417,8 @@ check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
 	      ;
 	    else
 	      {
-                tci->speculative = true;
-	        return false;
+                tci->speculative++;
+	        return csftc_abort_walking_p (tci->speculative);
 	      }
 	    op = walk_ssa_copies (op);
 	  }
@@ -1438,8 +1453,8 @@ check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
           fprintf (dump_file, "  Function call may change dynamic type:");
 	  print_gimple_stmt (dump_file, stmt, 0, 0);
 	}
-     tci->speculative = true;
-     return false;
+     tci->speculative++;
+     return csftc_abort_walking_p (tci->speculative);
    }
   /* Check for inlined virtual table store.  */
   else if (noncall_stmt_may_be_vtbl_ptr_store (stmt))
@@ -1461,7 +1476,7 @@ check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
 	  if (dump_file)
 	    fprintf (dump_file, "  Unanalyzed store may change type.\n");
 	  tci->seen_unanalyzed_store = true;
-	  tci->speculative = true;
+	  tci->speculative++;
 	}
       else
         record_known_type (tci, type, offset);
@@ -1646,7 +1661,7 @@ ipa_polymorphic_call_context::get_dynamic_type (tree instance,
   tci.otr_type = otr_type;
   tci.type_maybe_changed = false;
   tci.multiple_types_encountered = false;
-  tci.speculative = false;
+  tci.speculative = 0;
   tci.seen_unanalyzed_store = false;
 
   walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
diff --git a/gcc/params.def b/gcc/params.def
index 9362c1588de..dbff305b7f4 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -1203,6 +1203,12 @@ DEFPARAM (PARAM_HSA_GEN_DEBUG_STORES,
 	  "hsa-gen-debug-stores",
 	  "Level of hsa debug stores verbosity",
 	  0, 0, 1)
+
+DEFPARAM (PARAM_MAX_SPECULATIVE_DEVIRT_MAYDEFS,
+	  "max-speculative-devirt-maydefs",
+	  "Maximum number of may-defs visited when devirtualizing "
+	  "speculatively", 50, 0, 0)
+
 /*
 
 Local variables: