+ /* tmp2 == op2-1 inherited from previous block. */
+ stmt1 = gimple_build_assign_with_ops (BIT_AND_EXPR, result, op1, tmp2);
+ gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
+ bb2end = stmt1;
+
+ stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
+ op1, op2);
+ gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
+ bb3end = stmt1;
+
+ /* 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;
+ e34 = split_block (bb3, bb3end);
+ bb4 = e34->dest;
+ bb4->count = all;
+
+ 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;
+
+ return result;
+}
+
+/* Do transform 2) on INSN if applicable. */
+static bool
+gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
+{
+ histogram_value histogram;
+ enum tree_code code;
+ gcov_type count, wrong_values, all;
+ tree lhs_type, result, value;
+ gcov_type prob;
+ gimple stmt;
+
+ stmt = gsi_stmt (*si);
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return false;
+
+ lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
+ if (!INTEGRAL_TYPE_P (lhs_type))
+ return false;
+
+ code = gimple_assign_rhs_code (stmt);
+
+ if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
+ return false;
+
+ histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
+ if (!histogram)
+ return false;
+
+ value = histogram->hvalue.value;
+ 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 (gimple_assign_rhs2 (stmt), value) != 1
+ || count < wrong_values
+ || optimize_bb_for_size_p (gimple_bb (stmt)))
+ return false;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Mod power of 2 transformation on insn ");
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+ }
+
+ /* Compute probability of taking the optimal path. */
+ all = count + wrong_values;
+
+ if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
+ return false;
+
+ if (all > 0)
+ prob = (count * REG_BR_PROB_BASE + all / 2) / all;
+ else
+ prob = 0;
+
+ result = gimple_mod_pow2 (stmt, prob, count, all);
+
+ gimple_assign_set_rhs_from_tree (si, result);
+
+ return true;
+}
+
+/* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
+ NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
+ supported and this is built into this interface. The probabilities of taking
+ the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
+ COUNT2/ALL respectively within roundoff error). This generates the
+ result into a temp and returns the temp; it does not replace or alter
+ the original STMT. */
+/* FIXME: Generalize the interface to handle NCOUNTS > 1. */
+
+static tree
+gimple_mod_subtract (gimple stmt, int prob1, int prob2, int ncounts,
+ gcov_type count1, gcov_type count2, gcov_type all)
+{
+ gimple stmt1, stmt2, stmt3;
+ tree tmp1;
+ gimple bb1end, bb2end = NULL, bb3end;
+ basic_block bb, bb2, bb3, bb4;
+ tree optype, op1, op2;
+ edge e12, e23 = 0, e24, e34, e14;
+ gimple_stmt_iterator gsi;
+ tree result;
+
+ gcc_assert (is_gimple_assign (stmt)
+ && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
+
+ optype = TREE_TYPE (gimple_assign_lhs (stmt));
+ op1 = gimple_assign_rhs1 (stmt);
+ op2 = gimple_assign_rhs2 (stmt);
+
+ bb = gimple_bb (stmt);
+ gsi = gsi_for_stmt (stmt);
+
+ result = create_tmp_var (optype, "PROF");
+ tmp1 = create_tmp_var (optype, "PROF");
+ stmt1 = gimple_build_assign (result, op1);
+ stmt2 = gimple_build_assign (tmp1, op2);
+ stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
+ gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
+ gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
+ gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
+ bb1end = stmt3;
+
+ if (ncounts) /* Assumed to be 0 or 1 */
+ {
+ stmt1 = gimple_build_assign_with_ops (MINUS_EXPR, result, result, tmp1);
+ stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
+ gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
+ gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
+ bb2end = stmt2;
+ }
+
+ /* Fallback case. */
+ stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
+ result, tmp1);
+ gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
+ bb3end = stmt1;
+
+ /* Fix CFG. */
+ /* Edge e23 connects bb2 to bb3, etc. */
+ /* However block 3 is optional; if it is not there, references
+ to 3 really refer to block 2. */
+ e12 = split_block (bb, bb1end);
+ bb2 = e12->dest;
+ bb2->count = all - count1;
+
+ if (ncounts) /* Assumed to be 0 or 1. */
+ {
+ e23 = split_block (bb2, bb2end);
+ bb3 = e23->dest;
+ bb3->count = all - count1 - count2;
+ }
+
+ e34 = split_block (ncounts ? bb3 : bb2, bb3end);
+ bb4 = e34->dest;
+ bb4->count = all;
+
+ e12->flags &= ~EDGE_FALLTHRU;
+ e12->flags |= EDGE_FALSE_VALUE;
+ e12->probability = REG_BR_PROB_BASE - prob1;
+ e12->count = all - count1;
+
+ e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
+ e14->probability = prob1;
+ e14->count = count1;
+
+ if (ncounts) /* Assumed to be 0 or 1. */
+ {
+ e23->flags &= ~EDGE_FALLTHRU;
+ e23->flags |= EDGE_FALSE_VALUE;
+ e23->count = all - count1 - count2;
+ e23->probability = REG_BR_PROB_BASE - prob2;
+
+ e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
+ e24->probability = prob2;
+ e24->count = count2;
+ }
+
+ e34->probability = REG_BR_PROB_BASE;
+ e34->count = all - count1 - count2;
+
+ return result;
+}
+
+
+/* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
+
+static bool
+gimple_mod_subtract_transform (gimple_stmt_iterator *si)
+{
+ histogram_value histogram;
+ enum tree_code code;
+ gcov_type count, wrong_values, all;
+ tree lhs_type, result, value;
+ gcov_type prob1, prob2;
+ unsigned int i, steps;
+ gcov_type count1, count2;
+ gimple stmt;
+
+ stmt = gsi_stmt (*si);
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return false;
+
+ lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
+ if (!INTEGRAL_TYPE_P (lhs_type))
+ return false;
+
+ code = gimple_assign_rhs_code (stmt);
+
+ if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
+ return false;
+
+ histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
+ if (!histogram)
+ return false;
+
+ value = histogram->hvalue.value;
+ all = 0;
+ wrong_values = 0;
+ for (i = 0; i < histogram->hdata.intvl.steps; i++)
+ all += histogram->hvalue.counters[i];
+
+ 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", &count1, &all, gimple_bb (stmt)->count))
+ {
+ gimple_remove_histogram_value (cfun, stmt, histogram);
+ return false;
+ }
+
+ if (flag_profile_correction && count1 + count2 > all)
+ all = count1 + count2;
+
+ gcc_assert (count1 + count2 <= all);
+
+ /* We require that we use just subtractions in at least 50% of all
+ evaluations. */
+ count = 0;
+ for (i = 0; i < histogram->hdata.intvl.steps; i++)
+ {
+ count += histogram->hvalue.counters[i];
+ if (count * 2 >= all)
+ break;
+ }
+ if (i == steps
+ || optimize_bb_for_size_p (gimple_bb (stmt)))
+ return false;
+
+ gimple_remove_histogram_value (cfun, stmt, histogram);
+ if (dump_file)
+ {
+ fprintf (dump_file, "Mod subtract transformation on insn ");
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+ }
+
+ /* Compute probability of taking the optimal path(s). */
+ if (all > 0)
+ {
+ prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
+ prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
+ }
+ else
+ {
+ prob1 = prob2 = 0;
+ }
+
+ /* In practice, "steps" is always 2. This interface reflects this,
+ and will need to be changed if "steps" can change. */
+ result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all);
+
+ gimple_assign_set_rhs_from_tree (si, result);
+
+ return true;
+}
+
+static struct cgraph_node** pid_map = NULL;
+
+/* Initialize map of pids (pid -> cgraph node) */
+
+static void
+init_pid_map (void)
+{
+ struct cgraph_node *n;
+
+ if (pid_map != NULL)
+ return;
+
+ pid_map
+ = (struct cgraph_node**) xmalloc (sizeof (struct cgraph_node*) * cgraph_max_pid);
+
+ for (n = cgraph_nodes; n; n = n->next)
+ {
+ if (n->pid != -1)
+ pid_map [n->pid] = n;
+ }
+}
+
+/* Return cgraph node for function with pid */
+
+static inline struct cgraph_node*
+find_func_by_pid (int pid)
+{
+ init_pid_map ();
+
+ return pid_map [pid];
+}
+
+/* Do transformation
+
+ if (actual_callee_address == address_of_most_common_function/method)
+ do direct call
+ else
+ old call
+ */
+
+static gimple
+gimple_ic (gimple stmt, gimple call, struct cgraph_node *direct_call,
+ int prob, gcov_type count, gcov_type all)
+{
+ gimple stmt1, stmt2, stmt3;
+ tree tmp1, tmpv, tmp;
+ gimple bb1end, bb2end, bb3end;
+ basic_block bb, bb2, bb3, bb4;
+ tree optype = build_pointer_type (void_type_node);
+ edge e12, e13, e23, e24, e34;
+ gimple_stmt_iterator gsi;
+ int region;
+
+ bb = gimple_bb (stmt);
+ gsi = gsi_for_stmt (stmt);