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?
Thanks,
Richard.
2016-03-23 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.
(MAXSPEC): New define.
(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,1353 ----
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. */
+
+ #define MAXSPEC (PARAM_VALUE (PARAM_MAX_SPECULATIVE_DEVIRT_MAYDEFS))
+
/* 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;
--- 1394,1408 ----
&size, &max_size, &reverse);
if (size != max_size || max_size == -1)
{
! tci->speculative++;
! return tci->speculative > MAXSPEC ? true : false;
}
if (op && TREE_CODE (op) == MEM_REF)
{
if (!tree_fits_shwi_p (TREE_OPERAND (op, 1)))
{
! tci->speculative++;
! return tci->speculative > MAXSPEC ? true : false;
}
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);
}
--- 1412,1419 ----
;
else
{
! tci->speculative++;
! return tci->speculative > MAXSPEC ? true : false;
}
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))
--- 1448,1455 ----
fprintf (dump_file, " Function call may change dynamic type:");
print_gimple_stmt (dump_file, stmt, 0, 0);
}
! tci->speculative++;
! return tci->speculative > MAXSPEC ? true : false;
}
/* 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);
--- 1471,1477 ----
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);
*************** check_stmt_for_type_change (ao_ref *ao A
*** 1471,1476 ****
--- 1481,1489 ----
return false;
}
+ #undef MAXSPEC
+
+
/* THIS is polymorphic call context obtained from get_polymorphic_context.
OTR_OBJECT is pointer to the instance returned by OBJ_TYPE_REF_OBJECT.
INSTANCE is pointer to the outer instance as returned by
*************** 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,
--- 1659,1665 ----
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
