#include "timevar.h"
#include "tree-pass.h"
#include "toplev.h"
+#include "pointer-set.h"
static struct value_prof_hooks *value_prof_hooks;
-/* This is the vector of histograms. Created in find_values_to_profile.
- During profile generation, freed by instrument_values.
- During profile use, freed by value_profile_transformations. */
-
-static histogram_values static_values = NULL;
-
/* In this file value profile based optimizations are placed. Currently the
following optimizations are implemented (for more detailed descriptions
see comments at value_profile_transformations):
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 *);
+
+/* Allocate histogram value. */
+
+static histogram_value
+gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
+ enum hist_type type, tree stmt, tree value)
+{
+ histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
+ hist->hvalue.value = value;
+ hist->hvalue.stmt = stmt;
+ hist->type = type;
+ return hist;
+}
+
+/* Hash value for histogram. */
+
+static hashval_t
+histogram_hash (const void *x)
+{
+ return htab_hash_pointer (((histogram_value)x)->hvalue.stmt);
+}
+
+/* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
+
+static int
+histogram_eq (const void *x, const void *y)
+{
+ return ((histogram_value) x)->hvalue.stmt == (tree)y;
+}
+
+/* Set histogram for STMT. */
+
+static void
+set_histogram_value (struct function *fun, tree stmt, histogram_value hist)
+{
+ void **loc;
+ if (!hist && !VALUE_HISTOGRAMS (fun))
+ return;
+ if (!VALUE_HISTOGRAMS (fun))
+ VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
+ histogram_eq, NULL);
+ loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
+ htab_hash_pointer (stmt),
+ hist ? INSERT : NO_INSERT);
+ if (!hist)
+ {
+ if (loc)
+ htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
+ return;
+ }
+ *loc = hist;
+}
+
+/* Get histogram list for STMT. */
+
+histogram_value
+gimple_histogram_value (struct function *fun, tree stmt)
+{
+ if (!VALUE_HISTOGRAMS (fun))
+ return NULL;
+ return htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
+ htab_hash_pointer (stmt));
+}
+
+/* Add histogram for STMT. */
+
+void
+gimple_add_histogram_value (struct function *fun, tree stmt, histogram_value hist)
+{
+ hist->hvalue.next = gimple_histogram_value (fun, stmt);
+ set_histogram_value (fun, stmt, hist);
+}
+
+/* Remove histogram HIST from STMT's histogram list. */
+
+void
+gimple_remove_histogram_value (struct function *fun, tree stmt, histogram_value hist)
+{
+ histogram_value hist2 = gimple_histogram_value (fun, stmt);
+ if (hist == hist2)
+ {
+ set_histogram_value (fun, stmt, hist->hvalue.next);
+ }
+ else
+ {
+ while (hist2->hvalue.next != hist)
+ hist2 = hist2->hvalue.next;
+ hist2->hvalue.next = hist->hvalue.next;
+ }
+ free (hist->hvalue.counters);
+#ifdef ENABLE_CHECKING
+ memset (hist, 0xab, sizeof (*hist));
+#endif
+ free (hist);
+}
+
+/* Lookup histogram of type TYPE in the STMT. */
+
+histogram_value
+gimple_histogram_value_of_type (struct function *fun, tree stmt, enum hist_type type)
+{
+ histogram_value hist;
+ for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
+ if (hist->type == type)
+ return hist;
+ return NULL;
+}
+
+/* Dump information about HIST to DUMP_FILE. */
+
+static void
+dump_histogram_value (FILE *dump_file, histogram_value hist)
+{
+ switch (hist->type)
+ {
+ case HIST_TYPE_INTERVAL:
+ fprintf (dump_file, "Interval counter range %d -- %d",
+ hist->hdata.intvl.int_start,
+ (hist->hdata.intvl.int_start
+ + hist->hdata.intvl.steps - 1));
+ if (hist->hvalue.counters)
+ {
+ unsigned int i;
+ fprintf(dump_file, " [");
+ for (i = 0; i < hist->hdata.intvl.steps; i++)
+ fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC,
+ hist->hdata.intvl.int_start + i,
+ (HOST_WIDEST_INT) hist->hvalue.counters[i]);
+ fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[i]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+
+ case HIST_TYPE_POW2:
+ fprintf (dump_file, "Pow2 counter ");
+ if (hist->hvalue.counters)
+ {
+ fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC
+ " nonpow2:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[0],
+ (HOST_WIDEST_INT) hist->hvalue.counters[1]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+
+ case HIST_TYPE_SINGLE_VALUE:
+ fprintf (dump_file, "Single value ");
+ if (hist->hvalue.counters)
+ {
+ fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
+ " match:"HOST_WIDEST_INT_PRINT_DEC
+ " wrong:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[0],
+ (HOST_WIDEST_INT) hist->hvalue.counters[1],
+ (HOST_WIDEST_INT) hist->hvalue.counters[2]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+
+ case HIST_TYPE_CONST_DELTA:
+ fprintf (dump_file, "Constant delta ");
+ if (hist->hvalue.counters)
+ {
+ fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
+ " match:"HOST_WIDEST_INT_PRINT_DEC
+ " wrong:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[0],
+ (HOST_WIDEST_INT) hist->hvalue.counters[1],
+ (HOST_WIDEST_INT) hist->hvalue.counters[2]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+ }
+}
+
+/* Dump all histograms attached to STMT to DUMP_FILE. */
+
+void
+dump_histograms_for_stmt (struct function *fun, FILE *dump_file, tree stmt)
+{
+ histogram_value hist;
+ for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
+ dump_histogram_value (dump_file, hist);
+}
+
+/* Remove all histograms associated with STMT. */
+
+void
+gimple_remove_stmt_histograms (struct function *fun, tree stmt)
+{
+ histogram_value val;
+ while ((val = gimple_histogram_value (fun, stmt)) != NULL)
+ gimple_remove_histogram_value (fun, stmt, val);
+}
+
+/* Duplicate all histograms associates with OSTMT to STMT. */
+
+void
+gimple_duplicate_stmt_histograms (struct function *fun, tree stmt,
+ struct function *ofun, tree ostmt)
+{
+ histogram_value val;
+ for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
+ {
+ histogram_value new = gimple_alloc_histogram_value (fun, val->type, NULL, NULL);
+ memcpy (new, val, sizeof (*val));
+ new->hvalue.stmt = stmt;
+ new->hvalue.counters = xmalloc (sizeof (*new->hvalue.counters) * new->n_counters);
+ memcpy (new->hvalue.counters, val->hvalue.counters, sizeof (*new->hvalue.counters) * new->n_counters);
+ gimple_add_histogram_value (fun, stmt, new);
+ }
+}
+
+static bool error_found = false;
+
+/* Helper function for verify_histograms. For each histogram reachable via htab
+ walk verify that it was reached via statement walk. */
+
+static int
+visit_hist (void **slot, void *data)
+{
+ struct pointer_set_t *visited = (struct pointer_set_t *) data;
+ histogram_value hist = *(histogram_value *) slot;
+ if (!pointer_set_contains (visited, hist))
+ {
+ error ("Dead histogram");
+ dump_histogram_value (stderr, hist);
+ debug_generic_stmt (hist->hvalue.stmt);
+ error_found = true;
+ }
+ return 0;
+}
+
+/* Verify sanity of the histograms. */
+
+void
+verify_histograms (void)
+{
+ basic_block bb;
+ block_stmt_iterator bsi;
+ histogram_value hist;
+ struct pointer_set_t *visited_hists;
+
+ error_found = false;
+ visited_hists = pointer_set_create ();
+ FOR_EACH_BB (bb)
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+
+ for (hist = gimple_histogram_value (cfun, stmt); hist; hist = hist->hvalue.next)
+ {
+ if (hist->hvalue.stmt != stmt)
+ {
+ error ("Histogram value statement does not correspond to statement"
+ " it is associated with");
+ debug_generic_stmt (stmt);
+ dump_histogram_value (stderr, hist);
+ error_found = true;
+ }
+ pointer_set_insert (visited_hists, hist);
+ }
+ }
+ if (VALUE_HISTOGRAMS (cfun))
+ htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists);
+ pointer_set_destroy (visited_hists);
+ if (error_found)
+ internal_error ("verify_histograms failed");
+}
+
+/* Helper function for verify_histograms. For each histogram reachable via htab
+ walk verify that it was reached via statement walk. */
+
+static int
+free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+ histogram_value hist = *(histogram_value *) slot;
+ free (hist->hvalue.counters);
+#ifdef ENABLE_CHECKING
+ memset (hist, 0xab, sizeof (*hist));
+#endif
+ free (hist);
+ return 0;
+}
+
+void
+free_histograms (void)
+{
+ if (VALUE_HISTOGRAMS (cfun))
+ {
+ htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);
+ htab_delete (VALUE_HISTOGRAMS (cfun));
+ VALUE_HISTOGRAMS (cfun) = NULL;
+ }
+}
/* 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
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))
{
tree stmt = bsi_stmt (bsi);
- stmt_ann_t ann = get_stmt_ann (stmt);
- histogram_value th = ann->histograms;
+ histogram_value th = gimple_histogram_value (cfun, stmt);
if (!th)
continue;
if (dump_file)
{
- fprintf (dump_file, "Trying transformations on insn ");
+ fprintf (dump_file, "Trying transformations on stmt ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ dump_histograms_for_stmt (cfun, dump_file, stmt);
}
/* Transformations: */
if (flag_value_profile_transformations
&& (tree_mod_subtract_transform (stmt)
|| tree_divmod_fixed_value_transform (stmt)
- || tree_mod_pow2_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))
bsi = bsi_for_stmt (stmt);
}
}
-
- /* Free extra storage from compute_value_histograms. */
- while (th)
- {
- free (th->hvalue.counters);
- th = th->hvalue.next;
- }
- ann->histograms = 0;
}
}
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 label1, label2;
tree bb1end, bb2end, bb3end;
basic_block bb, bb2, bb3, bb4;
tree optype = TREE_TYPE (operation);
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, op2);
+ stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, tmpv,
+ fold_convert (optype, value));
+ stmt2 = build2 (GIMPLE_MODIFY_STMT, optype, tmp1, op2);
stmt3 = build3 (COND_EXPR, void_type_node,
build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
build1 (GOTO_EXPR, void_type_node, label_decl2),
tmp2 = create_tmp_var (optype, "PROF");
label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
- stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
+ stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, tmp2,
build2 (TREE_CODE (operation), optype, op1, tmpv));
bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
bb2end = stmt1;
label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
- stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
+ stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, tmp2,
build2 (TREE_CODE (operation), optype, op1, op2));
bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
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);
static bool
tree_divmod_fixed_value_transform (tree stmt)
{
- stmt_ann_t ann = get_stmt_ann (stmt);
histogram_value histogram;
enum tree_code code;
gcov_type val, count, all;
modify = stmt;
if (TREE_CODE (stmt) == RETURN_EXPR
&& TREE_OPERAND (stmt, 0)
- && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
modify = TREE_OPERAND (stmt, 0);
- if (TREE_CODE (modify) != MODIFY_EXPR)
+ if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
return false;
- op = TREE_OPERAND (modify, 1);
+ op = GIMPLE_STMT_OPERAND (modify, 1);
if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
return false;
code = TREE_CODE (op);
op1 = TREE_OPERAND (op, 0);
op2 = TREE_OPERAND (op, 1);
- if (!ann->histograms)
- return false;
-
- for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
- if (histogram->type == HIST_TYPE_SINGLE_VALUE)
- break;
+ histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
if (!histogram)
return false;
val = histogram->hvalue.counters[0];
count = histogram->hvalue.counters[1];
all = histogram->hvalue.counters[2];
+ gimple_remove_histogram_value (cfun, stmt, histogram);
/* 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 50% of time (and 75% gives the guarantee of usage). */
- if (simple_cst_equal (op2, value) != 1 || 2 * count < all)
+ if (simple_cst_equal (op2, value) != 1 || 2 * count < all
+ || !maybe_hot_bb_p (bb_for_stmt (stmt)))
return false;
if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
print_generic_stmt (dump_file, stmt, TDF_SLIM);
}
- TREE_OPERAND (modify, 1) = result;
+ GIMPLE_STMT_OPERAND (modify, 1) = result;
return true;
}
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 label1, label2;
tree bb1end, bb2end, bb3end;
basic_block bb, bb2, bb3, bb4;
tree optype = TREE_TYPE (operation);
tmp2 = create_tmp_var (optype, "PROF");
tmp3 = create_tmp_var (optype, "PROF");
- stmt2 = build2 (MODIFY_EXPR, optype, tmp2,
+ stmt2 = build2 (GIMPLE_MODIFY_STMT, optype, tmp2,
build2 (PLUS_EXPR, optype, op2, build_int_cst (optype, -1)));
- stmt3 = build2 (MODIFY_EXPR, optype, tmp3,
+ stmt3 = build2 (GIMPLE_MODIFY_STMT, optype, tmp3,
build2 (BIT_AND_EXPR, optype, tmp2, op2));
stmt4 = build3 (COND_EXPR, void_type_node,
build2 (NE_EXPR, boolean_type_node,
/* tmp2 == op2-1 inherited from previous block */
label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
- stmt1 = build2 (MODIFY_EXPR, optype, result,
+ stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result,
build2 (BIT_AND_EXPR, optype, op1, tmp2));
bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
bb2end = stmt1;
label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
- stmt1 = build2 (MODIFY_EXPR, optype, result,
+ stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result,
build2 (TREE_CODE (operation), optype, op1, op2));
bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
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);
static bool
tree_mod_pow2_value_transform (tree stmt)
{
- stmt_ann_t ann = get_stmt_ann (stmt);
histogram_value histogram;
enum tree_code code;
gcov_type count, wrong_values, all;
modify = stmt;
if (TREE_CODE (stmt) == RETURN_EXPR
&& TREE_OPERAND (stmt, 0)
- && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
modify = TREE_OPERAND (stmt, 0);
- if (TREE_CODE (modify) != MODIFY_EXPR)
+ if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
return false;
- op = TREE_OPERAND (modify, 1);
+ op = GIMPLE_STMT_OPERAND (modify, 1);
if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
return false;
code = TREE_CODE (op);
op1 = TREE_OPERAND (op, 0);
op2 = TREE_OPERAND (op, 1);
- if (!ann->histograms)
- return false;
-
- for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
- if (histogram->type == HIST_TYPE_POW2)
- break;
+ histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
if (!histogram)
return false;
wrong_values = histogram->hvalue.counters[0];
count = histogram->hvalue.counters[1];
+ gimple_remove_histogram_value (cfun, stmt, histogram);
+
/* We require that we hit a power of 2 at least half of all evaluations. */
- if (simple_cst_equal (op2, value) != 1 || count < wrong_values)
+ if (simple_cst_equal (op2, value) != 1 || count < wrong_values
+ || !maybe_hot_bb_p (bb_for_stmt (stmt)))
return false;
if (dump_file)
/* Compute probability of taking the optimal path. */
all = count + wrong_values;
+
if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
return false;
result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
- TREE_OPERAND (modify, 1) = result;
+ GIMPLE_STMT_OPERAND (modify, 1) = result;
return true;
}
bsi = bsi_for_stmt (stmt);
tmp1 = create_tmp_var (optype, "PROF");
- stmt1 = build2 (MODIFY_EXPR, optype, result, op1);
- stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
+ stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result, op1);
+ stmt2 = build2 (GIMPLE_MODIFY_STMT, optype, tmp1, op2);
stmt3 = build3 (COND_EXPR, void_type_node,
build2 (LT_EXPR, boolean_type_node, result, tmp1),
build1 (GOTO_EXPR, void_type_node, label_decl3),
if (ncounts) /* Assumed to be 0 or 1 */
{
label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
- stmt1 = build2 (MODIFY_EXPR, optype, result,
+ stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result,
build2 (MINUS_EXPR, optype, result, tmp1));
stmt2 = build3 (COND_EXPR, void_type_node,
build2 (LT_EXPR, boolean_type_node, result, tmp1),
/* Fallback case. */
label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
- stmt1 = build2 (MODIFY_EXPR, optype, result,
+ stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result,
build2 (TREE_CODE (operation), optype, result, tmp1));
bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
static bool
tree_mod_subtract_transform (tree stmt)
{
- stmt_ann_t ann = get_stmt_ann (stmt);
histogram_value histogram;
enum tree_code code;
gcov_type count, wrong_values, all;
tree modify, op, op1, op2, result, value;
int prob1, prob2;
- unsigned int i;
+ unsigned int i, steps;
+ gcov_type count1, count2;
modify = stmt;
if (TREE_CODE (stmt) == RETURN_EXPR
&& TREE_OPERAND (stmt, 0)
- && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
modify = TREE_OPERAND (stmt, 0);
- if (TREE_CODE (modify) != MODIFY_EXPR)
+ if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
return false;
- op = TREE_OPERAND (modify, 1);
+ op = GIMPLE_STMT_OPERAND (modify, 1);
if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
return false;
code = TREE_CODE (op);
op1 = TREE_OPERAND (op, 0);
op2 = TREE_OPERAND (op, 1);
- if (!ann->histograms)
- return false;
-
- for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
- if (histogram->type == HIST_TYPE_INTERVAL)
- break;
+ histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
if (!histogram)
return false;
wrong_values += histogram->hvalue.counters[i];
wrong_values += histogram->hvalue.counters[i+1];
+ steps = histogram->hdata.intvl.steps;
all += wrong_values;
+ count1 = histogram->hvalue.counters[0];
+ count2 = histogram->hvalue.counters[1];
/* Compute probability of taking the optimal path. */
if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
- return false;
+ {
+ gimple_remove_histogram_value (cfun, stmt, histogram);
+ return false;
+ }
/* We require that we use just subtractions in at least 50% of all
evaluations. */
if (count * 2 >= all)
break;
}
- if (i == histogram->hdata.intvl.steps)
+ if (i == steps
+ || !maybe_hot_bb_p (bb_for_stmt (stmt)))
return false;
+ gimple_remove_histogram_value (cfun, stmt, histogram);
if (dump_file)
{
fprintf (dump_file, "Mod subtract transformation on insn ");
}
/* Compute probability of taking the optimal path(s). */
- prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all;
- prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all;
+ prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
+ prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
/* In practice, "steps" is always 2. This interface reflects this,
and will need to be changed if "steps" can change. */
result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
- histogram->hvalue.counters[0],
- histogram->hvalue.counters[1], all);
+ count1, count2, all);
+
+ GIMPLE_STMT_OPERAND (modify, 1) = result;
+
+ 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 (GIMPLE_MODIFY_STMT, optype, tmpv,
+ fold_convert (optype, value));
+ stmt2 = build2 (GIMPLE_MODIFY_STMT, 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;
- TREE_OPERAND (modify, 1) = result;
+ 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;
+ 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;
+
+ histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
+ if (!histogram)
+ return false;
+ value = histogram->hvalue.value;
+ val = histogram->hvalue.counters[0];
+ count = histogram->hvalue.counters[1];
+ all = histogram->hvalue.counters[2];
+ gimple_remove_histogram_value (cfun, stmt, histogram);
+ /* 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 || !maybe_hot_bb_p (bb_for_stmt (stmt)))
+ 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;
}
assign = stmt;
if (!assign
- || TREE_CODE (assign) != MODIFY_EXPR)
+ || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
return;
- lhs = TREE_OPERAND (assign, 0);
+ lhs = GIMPLE_STMT_OPERAND (assign, 0);
type = TREE_TYPE (lhs);
if (!INTEGRAL_TYPE_P (type))
return;
- rhs = TREE_OPERAND (assign, 1);
+ rhs = GIMPLE_STMT_OPERAND (assign, 1);
switch (TREE_CODE (rhs))
{
case TRUNC_DIV_EXPR:
VEC_reserve (histogram_value, heap, *values, 3);
if (is_gimple_reg (divisor))
- {
- /* Check for the case where the divisor is the same value most
- of the time. */
- hist = ggc_alloc (sizeof (*hist));
- hist->hvalue.value = divisor;
- hist->hvalue.stmt = stmt;
- hist->type = HIST_TYPE_SINGLE_VALUE;
- VEC_quick_push (histogram_value, *values, hist);
- }
+ /* Check for the case where the divisor is the same value most
+ of the time. */
+ VEC_quick_push (histogram_value, *values,
+ gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
+ stmt, divisor));
/* For mod, check whether it is not often a noop (or replaceable by
a few subtractions). */
if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
&& TYPE_UNSIGNED (type))
{
+ tree val;
/* Check for a special case where the divisor is power of 2. */
- hist = ggc_alloc (sizeof (*hist));
- hist->hvalue.value = divisor;
- hist->hvalue.stmt = stmt;
- hist->type = HIST_TYPE_POW2;
- VEC_quick_push (histogram_value, *values, hist);
+ VEC_quick_push (histogram_value, *values,
+ gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
+ stmt, divisor));
- hist = ggc_alloc (sizeof (*hist));
- hist->hvalue.stmt = stmt;
- hist->hvalue.value
- = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
- hist->type = HIST_TYPE_INTERVAL;
+ val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
+ hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
+ stmt, val);
hist->hdata.intvl.int_start = 0;
hist->hdata.intvl.steps = 2;
VEC_quick_push (histogram_value, *values, hist);
}
}
+/* Find values inside STMT for that we want to measure histograms for
+ string operations. */
+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;
+
+ 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_safe_push (histogram_value, heap, *values,
+ gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
+ stmt, blck_size));
+}
+
/* Find values inside STMT for that we want to measure histograms and adds
them to list VALUES. */
tree_values_to_profile (tree stmt, histogram_values *values)
{
if (flag_value_profile_transformations)
- tree_divmod_values_to_profile (stmt, values);
+ {
+ tree_divmod_values_to_profile (stmt, values);
+ tree_stringops_values_to_profile (stmt, values);
+ }
}
static void
basic_block bb;
block_stmt_iterator bsi;
unsigned i;
- histogram_value hist;
+ histogram_value hist = NULL;
*values = NULL;
FOR_EACH_BB (bb)
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
tree_values_to_profile (bsi_stmt (bsi), values);
- static_values = *values;
for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
{
switch (hist->type)
{
case HIST_TYPE_INTERVAL:
- if (dump_file)
- {
- fprintf (dump_file, "Interval counter for tree ");
- print_generic_expr (dump_file, hist->hvalue.stmt,
- TDF_SLIM);
- fprintf (dump_file, ", range %d -- %d.\n",
- hist->hdata.intvl.int_start,
- (hist->hdata.intvl.int_start
- + hist->hdata.intvl.steps - 1));
- }
hist->n_counters = hist->hdata.intvl.steps + 2;
break;
case HIST_TYPE_POW2:
- if (dump_file)
- {
- fprintf (dump_file, "Pow2 counter for tree ");
- print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
- fprintf (dump_file, ".\n");
- }
hist->n_counters = 2;
break;
case HIST_TYPE_SINGLE_VALUE:
- if (dump_file)
- {
- fprintf (dump_file, "Single value counter for tree ");
- print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
- fprintf (dump_file, ".\n");
- }
hist->n_counters = 3;
break;
case HIST_TYPE_CONST_DELTA:
- if (dump_file)
- {
- fprintf (dump_file, "Constant delta counter for tree ");
- print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
- fprintf (dump_file, ".\n");
- }
hist->n_counters = 4;
break;
default:
gcc_unreachable ();
}
+ if (dump_file)
+ {
+ fprintf (dump_file, "Stmt ");
+ print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
+ dump_histogram_value (dump_file, hist);
+ }
}
}
void
tree_register_value_prof_hooks (void)
{
+ gcc_assert (current_ir_type () == IR_GIMPLE);
value_prof_hooks = &tree_value_prof_hooks;
- gcc_assert (ir_type ());
}
\f
/* IR-independent entry points. */
bool
value_profile_transformations (void)
{
- bool retval = (value_prof_hooks->value_profile_transformations) ();
- VEC_free (histogram_value, heap, static_values);
- return retval;
+ return (value_prof_hooks->value_profile_transformations) ();
}
\f