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 <m...@suse.de> Richard Biener <rguent...@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