Re: [PATCH] Limit alias walking by speculative devirt

[Richard Biener <rguenther at suse dot de>]

On Wed, 23 Mar 2016, Richard Biener wrote:

> 
> This reduces the compile-time for the testcase from PR12392 from
> ~50s to ~35s, dropping the alias-stmt walking time from 40% to around 8%.
> 
> Currently (even when -fno-devirtualize-speculatively - heh) when
> looking for a must-def that specifies the dynamic type of an object
> we invoke a virtual call on we skip may-defs speculatively until
> we run into the function start which of course may be quite some
> work to do and which is of course not acceptable.
> 
> The following limits the number of may-defs we skip.
> 
> It does not limit the number of stmts we skip as non-aliasing, thus we can
> still run into large overhead cases but that would require to assign an
> overall budget to the current function which isn't that trivial
> because this is a helper which is called from multiple places in GCC.
> Ideally the devirt machinery would record interesting must-defs in
> a body walk and thus when looking for it it could find candidates
> with a hashtable lookup and would only need to check whether there
> is no intermediate may-def.  But as said, with the "tool" nature
> of the devirt thing this is hard (but maybe speculative devirt
> is really only done at IPA time and not from PRE?).
> 
> Bootstrap and regtest running on x86_64-unknown-linux-gnu.
> 
> Honza, is this ok?  Can you check effects on devirt numbers for
> the testcases you have monitored that?

Honza had some comments and checked effects on libreoffice and approved
off-list.

Bootstrapped / tested on x86_64-unknown-linux-gnu, applied.

Richard.

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.

Index: gcc/params.def
===================================================================
*** gcc/params.def	(revision 234415)
--- gcc/params.def	(working copy)
*************** DEFPARAM (PARAM_HSA_GEN_DEBUG_STORES,
*** 1203,1208 ****
--- 1203,1214 ----
  	  "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:
Index: gcc/ipa-polymorphic-call.c
===================================================================
*** gcc/ipa-polymorphic-call.c	(revision 234415)
--- gcc/ipa-polymorphic-call.c	(working copy)
*************** along with GCC; see the file COPYING3.
*** 38,43 ****
--- 38,44 ----
  #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.  */
*************** struct type_change_info
*** 1094,1107 ****
    tree known_current_type;
    HOST_WIDE_INT known_current_offset;
  
    /* 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;
  };
  
--- 1095,1109 ----
    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;
    bool seen_unanalyzed_store;
  };
  
*************** record_known_type (struct type_change_in
*** 1338,1343 ****
--- 1340,1358 ----
    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
*************** check_stmt_for_type_change (ao_ref *ao A
*** 1384,1398 ****
  					  &size, &max_size, &reverse);
  	    if (size != max_size || max_size == -1)
  	      {
!                 tci->speculative = true;
! 	        return false;
  	      }
  	    if (op && TREE_CODE (op) == MEM_REF)
  	      {
  		if (!tree_fits_shwi_p (TREE_OPERAND (op, 1)))
  		  {
!                     tci->speculative = true;
! 		    return false;
  		  }
  		offset += tree_to_shwi (TREE_OPERAND (op, 1))
  			  * BITS_PER_UNIT;
--- 1399,1413 ----
  					  &size, &max_size, &reverse);
  	    if (size != max_size || max_size == -1)
  	      {
!                 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++;
! 		    return csftc_abort_walking_p (tci->speculative);
  		  }
  		offset += tree_to_shwi (TREE_OPERAND (op, 1))
  			  * BITS_PER_UNIT;
*************** check_stmt_for_type_change (ao_ref *ao A
*** 1402,1409 ****
  	      ;
  	    else
  	      {
!                 tci->speculative = true;
! 	        return false;
  	      }
  	    op = walk_ssa_copies (op);
  	  }
--- 1417,1424 ----
  	      ;
  	    else
  	      {
!                 tci->speculative++;
! 	        return csftc_abort_walking_p (tci->speculative);
  	      }
  	    op = walk_ssa_copies (op);
  	  }
*************** check_stmt_for_type_change (ao_ref *ao A
*** 1438,1445 ****
            fprintf (dump_file, "  Function call may change dynamic type:");
  	  print_gimple_stmt (dump_file, stmt, 0, 0);
  	}
!      tci->speculative = true;
!      return false;
     }
    /* Check for inlined virtual table store.  */
    else if (noncall_stmt_may_be_vtbl_ptr_store (stmt))
--- 1453,1460 ----
            fprintf (dump_file, "  Function call may change dynamic type:");
  	  print_gimple_stmt (dump_file, stmt, 0, 0);
  	}
!      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))
*************** check_stmt_for_type_change (ao_ref *ao A
*** 1461,1467 ****
  	  if (dump_file)
  	    fprintf (dump_file, "  Unanalyzed store may change type.\n");
  	  tci->seen_unanalyzed_store = true;
! 	  tci->speculative = true;
  	}
        else
          record_known_type (tci, type, offset);
--- 1476,1482 ----
  	  if (dump_file)
  	    fprintf (dump_file, "  Unanalyzed store may change type.\n");
  	  tci->seen_unanalyzed_store = true;
! 	  tci->speculative++;
  	}
        else
          record_known_type (tci, type, offset);
*************** ipa_polymorphic_call_context::get_dynami
*** 1646,1652 ****
    tci.otr_type = otr_type;
    tci.type_maybe_changed = false;
    tci.multiple_types_encountered = false;
!   tci.speculative = false;
    tci.seen_unanalyzed_store = false;
  
    walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
--- 1661,1667 ----
    tci.otr_type = otr_type;
    tci.type_maybe_changed = false;
    tci.multiple_types_encountered = false;
!   tci.speculative = 0;
    tci.seen_unanalyzed_store = false;
  
    walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
Index: gcc/doc/invoke.texi
===================================================================
*** gcc/doc/invoke.texi	(revision 234415)
--- gcc/doc/invoke.texi	(working copy)
*************** Enable emission of special debug stores
*** 9593,9598 ****
--- 9593,9603 ----
  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