Simple memcpy/memset/bzero profiling
Jan Hubicka
jh@suse.cz
Sat Nov 4 19:57:00 GMT 2006
Hi,
this patch adds basic profiling bits for memcpy/memset/bzero. Because the
neccesary infrastructure stuff wasn't reviewed yet, I broke up just the easy
part of profiling if the common size of block isn't constant.
If it is, the code is transfromed from:
memcpy (a,b,var);
into
if (var==4)
memcpy(a,b,4);
else
memcpy(a,b,var);
Where the first case works significantly faster when expanded inline.
The only problematic bit here is when to apply this transformation - at the
moment I do that only when it expands to move_by_pieces.
THis is quite suboptimal, since it also match for instance on Mesa, where block
of size 3*320 is being copied and expanding for this particular size brings
about 5% speedup, but only with new memcpy implementation not merged yet too.
In this restricted form on SPEC2000 the transformation match for vortex,
wupwise and lucas. Vortex is sped up by about 1% on K8, other two testcases
seems to be down in the noise. The transformation was done basically because
it is easy once one do have infrastructure for stringop profiling and I am
merging it first just because it don't need the other changes.
Bootstrapped/regtested x86_64-linux. I will commit it tomorrow if there are no
complains.
Honza
* value-prof.c (tree_stringops_transform): New.
(tree_value_profile_transformations): Require count to be non-zero;
call stringop transform; reset stmt BSI after BB changed.
(tree_divmod_fixed_value, tree_mod_pow2): Don't emit unnecesary label.
(interesting_stringop_to_profile_p, tree_stringop_fixed_value): New.
(tree_stringops_values_to_profile): New.
(tree_values_to_profile): Call tree_stringops_values_to_profile.
* tree.h (build_string_literal): Tidy prototype.
(validate_arglist, builtin_memset_read_str, get_pointer_alignment):
Declare.
* builtins.c (validate_arglist, builtin_memset_read_str,
get_pointer_alignment): Export.
Index: value-prof.c
===================================================================
*** value-prof.c (revision 118432)
--- value-prof.c (working copy)
*************** static tree tree_mod_subtract (tree, tre
*** 79,84 ****
--- 79,85 ----
static bool tree_divmod_fixed_value_transform (tree);
static bool tree_mod_pow2_value_transform (tree);
static bool tree_mod_subtract_transform (tree);
+ static bool tree_stringops_transform (block_stmt_iterator *);
/* The overall number of invocations of the counter should match execution count
of basic block. Report it as error rather than internal error as it might
*************** tree_value_profile_transformations (void
*** 110,116 ****
FOR_EACH_BB (bb)
{
/* Ignore cold areas -- we are enlarging the code. */
! if (!maybe_hot_bb_p (bb))
continue;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
--- 111,117 ----
FOR_EACH_BB (bb)
{
/* Ignore cold areas -- we are enlarging the code. */
! if (!bb->count || !maybe_hot_bb_p (bb))
continue;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
*************** tree_value_profile_transformations (void
*** 137,144 ****
if (flag_value_profile_transformations
&& (tree_mod_subtract_transform (stmt)
|| tree_divmod_fixed_value_transform (stmt)
! || tree_mod_pow2_value_transform (stmt)))
{
changed = true;
/* Original statement may no longer be in the same block. */
if (bb != bb_for_stmt (stmt))
--- 138,147 ----
if (flag_value_profile_transformations
&& (tree_mod_subtract_transform (stmt)
|| tree_divmod_fixed_value_transform (stmt)
! || tree_mod_pow2_value_transform (stmt)
! || tree_stringops_transform (&bsi)))
{
+ stmt = bsi_stmt (bsi);
changed = true;
/* Original statement may no longer be in the same block. */
if (bb != bb_for_stmt (stmt))
*************** tree_divmod_fixed_value (tree stmt, tree
*** 180,187 ****
tree tmp1, tmp2, tmpv;
tree label_decl1 = create_artificial_label ();
tree label_decl2 = create_artificial_label ();
! tree label_decl3 = create_artificial_label ();
! tree label1, label2, label3;
tree bb1end, bb2end, bb3end;
basic_block bb, bb2, bb3, bb4;
tree optype = TREE_TYPE (operation);
--- 183,189 ----
tree tmp1, tmp2, tmpv;
tree label_decl1 = create_artificial_label ();
tree label_decl2 = create_artificial_label ();
! tree label1, label2;
tree bb1end, bb2end, bb3end;
basic_block bb, bb2, bb3, bb4;
tree optype = TREE_TYPE (operation);
*************** tree_divmod_fixed_value (tree stmt, tree
*** 219,227 ****
bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
bb3end = stmt1;
- label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
- bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
-
/* Fix CFG. */
/* Edge e23 connects bb2 to bb3, etc. */
e12 = split_block (bb, bb1end);
--- 221,226 ----
*************** tree_mod_pow2 (tree stmt, tree operation
*** 343,350 ****
tree tmp2, tmp3;
tree label_decl1 = create_artificial_label ();
tree label_decl2 = create_artificial_label ();
! tree label_decl3 = create_artificial_label ();
! tree label1, label2, label3;
tree bb1end, bb2end, bb3end;
basic_block bb, bb2, bb3, bb4;
tree optype = TREE_TYPE (operation);
--- 342,348 ----
tree tmp2, tmp3;
tree label_decl1 = create_artificial_label ();
tree label_decl2 = create_artificial_label ();
! tree label1, label2;
tree bb1end, bb2end, bb3end;
basic_block bb, bb2, bb3, bb4;
tree optype = TREE_TYPE (operation);
*************** tree_mod_pow2 (tree stmt, tree operation
*** 386,394 ****
bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
bb3end = stmt1;
- label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
- bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
-
/* Fix CFG. */
/* Edge e23 connects bb2 to bb3, etc. */
e12 = split_block (bb, bb1end);
--- 384,389 ----
*************** tree_mod_subtract_transform (tree stmt)
*** 690,695 ****
--- 685,919 ----
return true;
}
+ /* Return true if the stringop FNDECL with ARGLIST shall be profiled. */
+ static bool
+ interesting_stringop_to_profile_p (tree fndecl, tree arglist)
+ {
+ enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
+
+ if (fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_MEMCPY
+ && fcode != BUILT_IN_BZERO)
+ return false;
+
+ switch (fcode)
+ {
+ case BUILT_IN_MEMCPY:
+ case BUILT_IN_MEMPCPY:
+ return validate_arglist (arglist,
+ POINTER_TYPE, POINTER_TYPE, INTEGER_TYPE,
+ VOID_TYPE);
+ case BUILT_IN_MEMSET:
+ return validate_arglist (arglist,
+ POINTER_TYPE, INTEGER_TYPE, INTEGER_TYPE,
+ VOID_TYPE);
+ case BUILT_IN_BZERO:
+ return validate_arglist (arglist, POINTER_TYPE, INTEGER_TYPE,
+ VOID_TYPE);
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ /* Convert stringop (..., size)
+ into
+ if (size == VALUE)
+ stringop (...., VALUE);
+ else
+ stringop (...., size);
+ assuming constant propagation of VALUE will happen later.
+ */
+ static void
+ tree_stringop_fixed_value (tree stmt, tree value, int prob, gcov_type count,
+ gcov_type all)
+ {
+ tree stmt1, stmt2, stmt3;
+ tree tmp1, tmpv;
+ tree label_decl1 = create_artificial_label ();
+ tree label_decl2 = create_artificial_label ();
+ tree label1, label2;
+ tree bb1end, bb2end;
+ basic_block bb, bb2, bb3, bb4;
+ edge e12, e13, e23, e24, e34;
+ block_stmt_iterator bsi;
+ tree call = get_call_expr_in (stmt);
+ tree arglist = TREE_OPERAND (call, 1);
+ tree blck_size = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist)));
+ tree optype = TREE_TYPE (blck_size);
+ int region;
+
+ bb = bb_for_stmt (stmt);
+ bsi = bsi_for_stmt (stmt);
+
+ if (bsi_end_p (bsi))
+ {
+ edge_iterator ei;
+ for (ei = ei_start (bb->succs); (e34 = ei_safe_edge (ei)); )
+ if (!e34->flags & EDGE_ABNORMAL)
+ break;
+ }
+ else
+ {
+ e34 = split_block (bb, stmt);
+ bsi = bsi_for_stmt (stmt);
+ }
+ bb4 = e34->dest;
+
+ tmpv = create_tmp_var (optype, "PROF");
+ tmp1 = create_tmp_var (optype, "PROF");
+ stmt1 = build2 (MODIFY_EXPR, optype, tmpv, fold_convert (optype, value));
+ stmt2 = build2 (MODIFY_EXPR, optype, tmp1, blck_size);
+ stmt3 = build3 (COND_EXPR, void_type_node,
+ build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
+ build1 (GOTO_EXPR, void_type_node, label_decl2),
+ build1 (GOTO_EXPR, void_type_node, label_decl1));
+ bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+ bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
+ bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
+ bb1end = stmt3;
+
+ label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
+ stmt1 = unshare_expr (stmt);
+ call = get_call_expr_in (stmt1);
+ arglist = TREE_OPERAND (call, 1);
+ TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist))) = value;
+ bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
+ bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+ region = lookup_stmt_eh_region (stmt);
+ if (region >= 0)
+ add_stmt_to_eh_region (stmt1, region);
+ bb2end = stmt1;
+ label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
+ bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
+
+ /* Fix CFG. */
+ /* Edge e23 connects bb2 to bb3, etc. */
+ e12 = split_block (bb, bb1end);
+ bb2 = e12->dest;
+ bb2->count = count;
+ e23 = split_block (bb2, bb2end);
+ bb3 = e23->dest;
+ bb3->count = all - count;
+
+ e12->flags &= ~EDGE_FALLTHRU;
+ e12->flags |= EDGE_FALSE_VALUE;
+ e12->probability = prob;
+ e12->count = count;
+
+ e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
+ e13->probability = REG_BR_PROB_BASE - prob;
+ e13->count = all - count;
+
+ remove_edge (e23);
+
+ e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
+ e24->probability = REG_BR_PROB_BASE;
+ e24->count = count;
+
+ e34->probability = REG_BR_PROB_BASE;
+ e34->count = all - count;
+ }
+
+ /* Find values inside STMT for that we want to measure histograms for
+ division/modulo optimization. */
+ static bool
+ tree_stringops_transform (block_stmt_iterator *bsi)
+ {
+ tree stmt = bsi_stmt (*bsi);
+ tree call = get_call_expr_in (stmt);
+ tree fndecl;
+ tree arglist;
+ tree blck_size;
+ enum built_in_function fcode;
+ stmt_ann_t ann = get_stmt_ann (stmt);
+ histogram_value histogram;
+ gcov_type count, all, val;
+ tree value;
+ tree dest, src;
+ unsigned int dest_align, src_align;
+ int prob;
+ tree tree_val;
+
+ if (!call)
+ return false;
+ fndecl = get_callee_fndecl (call);
+ if (!fndecl)
+ return false;
+ fcode = DECL_FUNCTION_CODE (fndecl);
+ arglist = TREE_OPERAND (call, 1);
+ if (!interesting_stringop_to_profile_p (fndecl, arglist))
+ return false;
+
+ if (fcode == BUILT_IN_BZERO)
+ blck_size = TREE_VALUE (TREE_CHAIN (arglist));
+ else
+ blck_size = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist)));
+ if (TREE_CODE (blck_size) == INTEGER_CST)
+ return false;
+
+ if (!ann->histograms)
+ return false;
+
+ all = bb_for_stmt (stmt)->count;
+ if (!all)
+ return false;
+ for (histogram = ann->histograms; histogram;
+ histogram = histogram->hvalue.next)
+ if (histogram->type == HIST_TYPE_SINGLE_VALUE)
+ break;
+ if (!histogram)
+ return false;
+ value = histogram->hvalue.value;
+ val = histogram->hvalue.counters[0];
+ count = histogram->hvalue.counters[1];
+ all = histogram->hvalue.counters[2];
+ /* We require that count is at least half of all; this means
+ that for the transformation to fire the value must be constant
+ at least 80% of time. */
+ if ((6 * count / 5) < all)
+ return false;
+ if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
+ return false;
+ prob = (count * REG_BR_PROB_BASE + all / 2) / all;
+ dest = TREE_VALUE (arglist);
+ dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
+ switch (fcode)
+ {
+ case BUILT_IN_MEMCPY:
+ case BUILT_IN_MEMPCPY:
+ src = TREE_VALUE (TREE_CHAIN (arglist));
+ src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
+ if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
+ return false;
+ break;
+ case BUILT_IN_MEMSET:
+ if (!can_store_by_pieces (val, builtin_memset_read_str,
+ TREE_VALUE (TREE_CHAIN (arglist)),
+ dest_align))
+ return false;
+ break;
+ case BUILT_IN_BZERO:
+ if (!can_store_by_pieces (val, builtin_memset_read_str,
+ integer_zero_node,
+ dest_align))
+ return false;
+ break;
+ default:
+ gcc_unreachable ();
+ }
+ tree_val = build_int_cst_wide (get_gcov_type (),
+ (unsigned HOST_WIDE_INT) val,
+ val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
+ if (dump_file)
+ {
+ fprintf (dump_file, "Single value %i stringop transformation on ",
+ (int)val);
+ print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ }
+ tree_stringop_fixed_value (stmt, tree_val, prob, count, all);
+
+ return true;
+ }
+
struct value_prof_hooks {
/* Find list of values for which we want to measure histograms. */
void (*find_values_to_profile) (histogram_values *);
*************** tree_divmod_values_to_profile (tree stmt
*** 769,774 ****
--- 993,1037 ----
}
}
+ /* Find values inside STMT for that we want to measure histograms for
+ division/modulo optimization. */
+ static void
+ tree_stringops_values_to_profile (tree stmt, histogram_values *values)
+ {
+ tree call = get_call_expr_in (stmt);
+ tree fndecl;
+ tree arglist;
+ tree blck_size;
+ enum built_in_function fcode;
+ histogram_value hist;
+
+ if (!call)
+ return;
+ fndecl = get_callee_fndecl (call);
+ if (!fndecl)
+ return;
+ fcode = DECL_FUNCTION_CODE (fndecl);
+ arglist = TREE_OPERAND (call, 1);
+
+ if (!interesting_stringop_to_profile_p (fndecl, arglist))
+ return;
+
+ if (fcode == BUILT_IN_BZERO)
+ blck_size = TREE_VALUE (TREE_CHAIN (arglist));
+ else
+ blck_size = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist)));
+
+ if (TREE_CODE (blck_size) != INTEGER_CST)
+ {
+ VEC_reserve (histogram_value, heap, *values, 3);
+ hist = ggc_alloc (sizeof (*hist));
+ hist->hvalue.value = blck_size;
+ hist->hvalue.stmt = stmt;
+ hist->type = HIST_TYPE_SINGLE_VALUE;
+ VEC_quick_push (histogram_value, *values, hist);
+ }
+ }
+
/* Find values inside STMT for that we want to measure histograms and adds
them to list VALUES. */
*************** static void
*** 776,782 ****
tree_values_to_profile (tree stmt, histogram_values *values)
{
if (flag_value_profile_transformations)
! tree_divmod_values_to_profile (stmt, values);
}
static void
--- 1039,1048 ----
tree_values_to_profile (tree stmt, histogram_values *values)
{
if (flag_value_profile_transformations)
! {
! tree_divmod_values_to_profile (stmt, values);
! tree_stringops_values_to_profile (stmt, values);
! }
}
static void
Index: tree.h
===================================================================
*** tree.h (revision 118432)
--- tree.h (working copy)
*************** extern tree strip_float_extensions (tree
*** 4301,4307 ****
extern tree c_strlen (tree, int);
extern tree std_gimplify_va_arg_expr (tree, tree, tree *, tree *);
extern tree build_va_arg_indirect_ref (tree);
! tree build_string_literal (int, const char *);
/* In convert.c */
extern tree strip_float_extensions (tree);
--- 4301,4310 ----
extern tree c_strlen (tree, int);
extern tree std_gimplify_va_arg_expr (tree, tree, tree *, tree *);
extern tree build_va_arg_indirect_ref (tree);
! extern tree build_string_literal (int, const char *);
! extern int validate_arglist (tree, ...);
! extern rtx builtin_memset_read_str (void *, HOST_WIDE_INT, enum machine_mode);
! extern int get_pointer_alignment (tree, unsigned int);
/* In convert.c */
extern tree strip_float_extensions (tree);
Index: builtins.c
===================================================================
*** builtins.c (revision 118432)
--- builtins.c (working copy)
*************** tree built_in_decls[(int) END_BUILTINS];
*** 71,77 ****
required to implement the function call in all cases). */
tree implicit_built_in_decls[(int) END_BUILTINS];
- static int get_pointer_alignment (tree, unsigned int);
static const char *c_getstr (tree);
static rtx c_readstr (const char *, enum machine_mode);
static int target_char_cast (tree, char *);
--- 71,76 ----
*************** static rtx expand_builtin_strcpy (tree,
*** 117,123 ****
static rtx expand_builtin_stpcpy (tree, rtx, enum machine_mode);
static rtx builtin_strncpy_read_str (void *, HOST_WIDE_INT, enum machine_mode);
static rtx expand_builtin_strncpy (tree, rtx, enum machine_mode);
- static rtx builtin_memset_read_str (void *, HOST_WIDE_INT, enum machine_mode);
static rtx builtin_memset_gen_str (void *, HOST_WIDE_INT, enum machine_mode);
static rtx expand_builtin_memset (tree, rtx, enum machine_mode, tree);
static rtx expand_builtin_bzero (tree);
--- 116,121 ----
*************** static tree fold_builtin_classify_type (
*** 140,146 ****
static tree fold_builtin_strlen (tree);
static tree fold_builtin_inf (tree, int);
static tree fold_builtin_nan (tree, tree, int);
- static int validate_arglist (tree, ...);
static bool integer_valued_real_p (tree);
static tree fold_trunc_transparent_mathfn (tree, tree);
static bool readonly_data_expr (tree);
--- 138,143 ----
*************** static bool called_as_built_in (tree nod
*** 231,237 ****
Otherwise, look at the expression to see if we can do better, i.e., if the
expression is actually pointing at an object whose alignment is tighter. */
! static int
get_pointer_alignment (tree exp, unsigned int max_align)
{
unsigned int align, inner;
--- 228,234 ----
Otherwise, look at the expression to see if we can do better, i.e., if the
expression is actually pointing at an object whose alignment is tighter. */
! int
get_pointer_alignment (tree exp, unsigned int max_align)
{
unsigned int align, inner;
*************** expand_builtin_strncpy (tree exp, rtx ta
*** 3400,3406 ****
bytes from constant string DATA + OFFSET and return it as target
constant. */
! static rtx
builtin_memset_read_str (void *data, HOST_WIDE_INT offset ATTRIBUTE_UNUSED,
enum machine_mode mode)
{
--- 3397,3403 ----
bytes from constant string DATA + OFFSET and return it as target
constant. */
! rtx
builtin_memset_read_str (void *data, HOST_WIDE_INT offset ATTRIBUTE_UNUSED,
enum machine_mode mode)
{
*************** build_function_call_expr (tree fn, tree
*** 9483,9489 ****
of tree_codes. If the last specifier is a 0, that represents an
ellipses, otherwise the last specifier must be a VOID_TYPE. */
! static int
validate_arglist (tree arglist, ...)
{
enum tree_code code;
--- 9480,9486 ----
of tree_codes. If the last specifier is a 0, that represents an
ellipses, otherwise the last specifier must be a VOID_TYPE. */
! int
validate_arglist (tree arglist, ...)
{
enum tree_code code;
Index: testsuite/gcc.dg/tree-prof/stringop-1.c
===================================================================
*** testsuite/gcc.dg/tree-prof/stringop-1.c (revision 0)
--- testsuite/gcc.dg/tree-prof/stringop-1.c (revision 0)
***************
*** 0 ****
--- 1,20 ----
+ /* { dg-options "-O2 -fdump-tree-optimized -fdump-tree-tree_profile" } */
+ int a[1000];
+ int b[1000];
+ int size=1;
+ int max=10000;
+ main()
+ {
+ int i;
+ for (i=0;i<max; i++)
+ {
+ __builtin_memcpy (a, b, size * sizeof (a[0]));
+ asm("");
+ }
+ return 0;
+ }
+ /* { dg-final-use { scan-tree-dump "Single value 4 stringop" "tree_profile"} } */
+ /* Really this ought to simplify into assignment, but we are not there yet. */
+ /* { dg-final-use { scan-tree-dump "memcpy.*4\\)" "optimized"} } */
+ /* { dg-final-use { cleanup-tree-dump "optimized" } } */
+ /* { dg-final-use { cleanup-tree-dump "tree_profile" } } */
Index: testsuite/gcc.dg/tree-prof/stringop-2.c
===================================================================
*** testsuite/gcc.dg/tree-prof/stringop-2.c (revision 0)
--- testsuite/gcc.dg/tree-prof/stringop-2.c (revision 0)
***************
*** 0 ****
--- 1,20 ----
+ /* { dg-options "-O2 -fdump-tree-optimized -fdump-tree-tree_profile" } */
+ int a[1000];
+ int b[1000];
+ int size=1;
+ int max=10000;
+ main()
+ {
+ int i;
+ for (i=0;i<max; i++)
+ {
+ __builtin_memset (a, 10, size * sizeof (a[0]));
+ asm("");
+ }
+ return 0;
+ }
+ /* { dg-final-use { scan-tree-dump "Single value 4 stringop" "tree_profile"} } */
+ /* Really this ought to simplify into assignment, but we are not there yet. */
+ /* { dg-final-use { scan-tree-dump "memset.*4\\)" "optimized"} } */
+ /* { dg-final-use { cleanup-tree-dump "optimized" } } */
+ /* { dg-final-use { cleanup-tree-dump "tree_profile" } } */
More information about the Gcc-patches
mailing list