diff options
Diffstat (limited to 'gcc-4.4.0/gcc/mcf.c')
| -rw-r--r-- | gcc-4.4.0/gcc/mcf.c | 205 |
1 files changed, 147 insertions, 58 deletions
diff --git a/gcc-4.4.0/gcc/mcf.c b/gcc-4.4.0/gcc/mcf.c index 0f3a59741..510840298 100644 --- a/gcc-4.4.0/gcc/mcf.c +++ b/gcc-4.4.0/gcc/mcf.c @@ -53,6 +53,8 @@ along with GCC; see the file COPYING3. If not see #include "tree.h" #include "gcov-io.h" #include "tree-flow.h" +#include "params.h" +#include "toplev.h" #include "profile.h" @@ -66,11 +68,12 @@ along with GCC; see the file COPYING3. If not see #define REVERSE_PENALTY 5 #define EDGE_COST 1 #define COST(k, w) ((k) / mcf_ln ((w) + 2)) -#define S_COST(k, w, i) ((k) * (((w) + 1000 * (i)))) +#define S_COST(m, k, w, i) ((m) * ((k) * (((w) + 1000 * (i))))) /* Limit the number of iterations for cancel_negative_cycles() to ensure reasonable compile time. */ -#define MAX_ITER(n, e) 10 + (1000000 / ((n) * (e))) +#define MAX_ITER(n, e) (PARAM_VALUE (PARAM_MIN_MCF_CANCEL_ITERS) + \ + (1000000 / ((n) * (e)))) typedef enum { @@ -82,12 +85,13 @@ typedef enum typedef enum { - INVALID_EDGE, + INVALID_EDGE = 0, VERTEX_SPLIT_EDGE, /* Edge to represent vertex with w(e) = w(v). */ REDIRECT_EDGE, /* Edge after vertex transformation. */ REVERSE_EDGE, SOURCE_CONNECT_EDGE, /* Single edge connecting to single source. */ SINK_CONNECT_EDGE, /* Single edge connecting to single sink. */ + SINK_SOURCE_EDGE, /* Single edge connecting sink to source. */ BALANCE_EDGE, /* Edge connecting with source/sink: cp(e) = 0. */ REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge. */ REVERSE_NORMALIZED_EDGE /* Normalized edge for a reverse edge. */ @@ -266,6 +270,10 @@ dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge) fputs (" @SINK_CONNECT_EDGE", file); break; + case SINK_SOURCE_EDGE: + fputs (" @SINK_SOURCE_EDGE", file); + break; + case REVERSE_EDGE: fputs (" @REVERSE_EDGE", file); break; @@ -522,7 +530,7 @@ create_fixup_graph (fixup_graph_type *fixup_graph) double k_neg = 0; /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */ gcov_type *diff_out_in = NULL; - gcov_type supply_value = 1, demand_value = 0; + gcov_type supply_value = 0, demand_value = 0; gcov_type fcost = 0; int new_entry_index = 0, new_exit_index = 0; int i = 0, j = 0; @@ -569,7 +577,7 @@ create_fixup_graph (fixup_graph_type *fixup_graph) /* Compute constants b, k_pos, k_neg used in the cost function calculation. b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */ - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) + FOR_ALL_BB (bb) total_vertex_weight += bb->count; sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / n_basic_blocks); @@ -583,47 +591,64 @@ create_fixup_graph (fixup_graph_type *fixup_graph) if (dump_file) fprintf (dump_file, "\nVertex transformation:\n"); - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) - { - predict_type predict = UNKNOWN; - /* v'->v'': index1->(index1+1). */ - i = 2 * bb->index; - if (flag_sample_profile) - { - if (same_line_with_preds (bb->preds)) - { - fcost = (gcov_type) S_COST (k_pos / CORRECT_PENALTY, - bb->count, compute_bb_num_ir (bb)); - predict = UNKNOWN; - } - else - { - fcost = (gcov_type) S_COST (k_pos, - bb->count, compute_bb_num_ir (bb)); - predict = CORRECT; - } - } - else - fcost = (gcov_type) COST (k_pos, bb->count); - add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count, - fcost, CAP_INFINITY, predict); - fixup_graph->num_vertices++; - - FOR_EACH_EDGE (e, ei, bb->succs) + FOR_ALL_BB (bb) { - /* Edges with ignore attribute set should be treated like they don't - exist. */ - if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) - continue; - j = 2 * e->dest->index; + predict_type predict = UNKNOWN; + /* v'->v'': index1->(index1+1). */ + i = 2 * bb->index; if (flag_sample_profile) - fcost = EDGE_COST; + { + if (bb->confidence == LOW_CONFIDENCE) + { + fcost = 0; + predict = UNKNOWN; + } + else + { + int mult = 1; + if (bb->confidence == HIGH_CONFIDENCE) + { + mult = + PARAM_VALUE (PARAM_SAMPLEFDO_MCF_HIGH_CONFIDENCE_COST_MULT); + } + + if (same_line_with_preds (bb->preds)) + { + fcost = + (gcov_type) S_COST (mult, k_pos / CORRECT_PENALTY, + bb->count, compute_bb_num_ir (bb)); + predict = UNKNOWN; + } + else + { + fcost = + (gcov_type) S_COST (mult, k_pos, + bb->count, compute_bb_num_ir (bb)); + predict = CORRECT; + } + } + } else - fcost = (gcov_type) COST (k_pos, e->count); - add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost, - CAP_INFINITY, UNKNOWN); + fcost = (gcov_type) COST (k_pos, bb->count); + add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count, + fcost, CAP_INFINITY, predict); + fixup_graph->num_vertices++; + + FOR_EACH_EDGE (e, ei, bb->succs) + { + /* Edges with ignore attribute set should be treated like they don't + exist. */ + if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) + continue; + j = 2 * e->dest->index; + if (flag_sample_profile) + fcost = EDGE_COST; + else + fcost = (gcov_type) COST (k_pos, e->count); + add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost, + CAP_INFINITY, UNKNOWN); + } } - } /* After vertex transformation. */ gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform); @@ -678,23 +703,35 @@ create_fixup_graph (fixup_graph_type *fixup_graph) new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices; fixup_graph->num_vertices++; - /* Set supply_value to 1 to avoid zero count function ENTRY. */ - add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE, - 1 /* supply_value */, 0, 1 /* supply_value */, UNKNOWN); + /* Set capacity to 0 initially, it will be updated after + supply_value is computed. */ + add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, + SOURCE_CONNECT_EDGE, 0 /* supply_value */, 0, + 0 /* supply_value */, UNKNOWN); /* Create new exit with EXIT_BLOCK as single pred. */ new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices; fixup_graph->num_vertices++; + /* Set capacity to 0 initially, it will be updated after + demand_value is computed. */ add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index, SINK_CONNECT_EDGE, 0 /* demand_value */, 0, 0 /* demand_value */, UNKNOWN); + /* Create a back edge from the new_exit to the new_entry. + Initially, its capacity will be set to 0 so that it does not + affect max flow, but later its capacity will be changed to + infinity to cancel negative cycles. */ + add_fixup_edge (fixup_graph, new_exit_index, new_entry_index, + SINK_SOURCE_EDGE, 0, 0, 0, UNKNOWN); + /* Connect vertices with unbalanced D(v) to source/sink. */ if (dump_file) fprintf (dump_file, "\nD(v) balance:\n"); - /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4. - diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2. */ - for (i = 4; i < new_entry_index; i += 2) + /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start + with i = 4. diff_out_in[v''] should be 0, but may not be due to + rounding error. So here we consider all vertices. */ + for (i = 4; i < new_entry_index; i += 1) { if (diff_out_in[i] > 0) { @@ -905,8 +942,6 @@ cancel_negative_cycle (fixup_graph_type *fixup_graph, for (i = 0; i < fnum_edges; i++) { pfedge = fedge_list + i; - if (pfedge->src == new_entry_index) - continue; if (pfedge->is_rflow_valid && pfedge->rflow && d[pfedge->src] != CAP_INFINITY && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost)) @@ -928,8 +963,6 @@ cancel_negative_cycle (fixup_graph_type *fixup_graph, for (i = 0; i < fnum_edges; i++) { pfedge = fedge_list + i; - if (pfedge->src == new_entry_index) - continue; if (pfedge->is_rflow_valid && pfedge->rflow && d[pfedge->src] != CAP_INFINITY && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost)) @@ -1155,20 +1188,20 @@ find_max_flow (fixup_graph_type *fixup_graph, int source, int sink) { pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u); r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]); + + pfedge->rflow -= increment; + r_pfedge->rflow += increment; + if (pfedge->type) { /* forward edge. */ pfedge->flow += increment; - pfedge->rflow -= increment; - r_pfedge->rflow += increment; } else { /* backward edge. */ gcc_assert (r_pfedge->type); - r_pfedge->rflow += increment; r_pfedge->flow -= increment; - pfedge->rflow -= increment; } } @@ -1387,6 +1420,52 @@ adjust_cfg_counts (fixup_graph_type *fixup_graph) } +/* Called before negative_cycle_cancellation, to form a cycle between + * new_exit to new_entry in FIXUP_GRAPH with capacity MAX_FLOW. We + * don't want the flow in the BALANCE_EDGE to be modified, so we set + * the residural flow of those edges to 0 */ + +static void +modify_sink_source_capacity (fixup_graph_type *fixup_graph, gcov_type max_flow) +{ + fixup_edge_p edge, r_edge; + int i; + int entry = ENTRY_BLOCK; + int exit = 2 * EXIT_BLOCK + 1; + int new_entry = fixup_graph->new_entry_index; + int new_exit = fixup_graph->new_exit_index; + + edge = find_fixup_edge (fixup_graph, new_entry, entry); + edge->max_capacity = CAP_INFINITY; + edge->rflow = CAP_INFINITY; + + edge = find_fixup_edge (fixup_graph, exit, new_exit); + edge->max_capacity = CAP_INFINITY; + edge->rflow = CAP_INFINITY; + + edge = find_fixup_edge (fixup_graph, new_exit, new_entry); + edge->max_capacity = CAP_INFINITY; + edge->flow = max_flow; + edge->rflow = CAP_INFINITY - max_flow; + + r_edge = find_fixup_edge (fixup_graph, new_entry, new_exit); + r_edge->rflow = max_flow; + + /* Find all the backwards residual edges corresponding to + BALANCE_EDGEs and set their residual flow to 0 to enforce a + minimum flow constraint on these edges. */ + for (i = 4; i < new_entry; i += 1) + { + edge = find_fixup_edge (fixup_graph, i, new_entry); + if (edge) + edge->rflow = 0; + edge = find_fixup_edge (fixup_graph, new_exit, i); + if (edge) + edge->rflow = 0; + } +} + + /* Implements the negative cycle canceling algorithm to compute a minimum cost flow. Algorithm: @@ -1415,13 +1494,18 @@ find_minimum_cost_flow (fixup_graph_type *fixup_graph) int fnum_vertices; int new_exit_index; int new_entry_index; + gcov_type max_flow; gcc_assert (fixup_graph); fnum_vertices = fixup_graph->num_vertices; new_exit_index = fixup_graph->new_exit_index; new_entry_index = fixup_graph->new_entry_index; - find_max_flow (fixup_graph, new_entry_index, new_exit_index); + max_flow = find_max_flow (fixup_graph, new_entry_index, new_exit_index); + + /* Adjust the fixup graph to translate things into a minimum cost + circulation problem. */ + modify_sink_source_capacity (fixup_graph, max_flow); /* Initialize the structures for find_negative_cycle(). */ pred = (int *) xcalloc (fnum_vertices, sizeof (int)); @@ -1437,7 +1521,12 @@ find_minimum_cost_flow (fixup_graph_type *fixup_graph) iteration++; if (iteration > MAX_ITER (fixup_graph->num_vertices, fixup_graph->num_edges)) - break; + { + inform (DECL_SOURCE_LOCATION (current_function_decl), + "Exiting profile correction early to avoid excessive " + "compile time"); + break; + } } if (dump_file) |