Mercurial > hg > CbC > CbC_gcc

comparison gcc/mcf.c @ 55:77e2b8dfacca gcc-4.4.5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update it from 4.4.3 to 4.5.0
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Fri, 12 Feb 2010 23:39:51 +0900
parents a06113de4d67
children 04ced10e8804
comparison
equal deleted inserted replaced
52:c156f1bd5cd9 55:77e2b8dfacca
1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth 1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth
2 basic block and edge frequency counts. 2 basic block and edge frequency counts.
3 Copyright (C) 2008 3 Copyright (C) 2008, 2009
4 Free Software Foundation, Inc. 4 Free Software Foundation, Inc.
5 Contributed by Paul Yuan (yingbo.com@gmail.com) and 5 Contributed by Paul Yuan (yingbo.com@gmail.com) and
6 Vinodha Ramasamy (vinodha@google.com). 6 Vinodha Ramasamy (vinodha@google.com).
7 7
8 This file is part of GCC. 8 This file is part of GCC.
386 386
387 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and 387 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
388 MAX_CAPACITY to the edge_list in the fixup graph. */ 388 MAX_CAPACITY to the edge_list in the fixup graph. */
389 389
390 static void 390 static void
391 add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest, int type, 391 add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
392 gcov_type weight, gcov_type cost, gcov_type max_capacity) 392 edge_type type, gcov_type weight, gcov_type cost,
393 gcov_type max_capacity)
393 { 394 {
394 fixup_edge_p curr_edge = add_edge(fixup_graph, src, dest, cost); 395 fixup_edge_p curr_edge = add_edge(fixup_graph, src, dest, cost);
395 curr_edge->type = type; 396 curr_edge->type = type;
396 curr_edge->weight = weight; 397 curr_edge->weight = weight;
397 curr_edge->max_capacity = max_capacity; 398 curr_edge->max_capacity = max_capacity;
1016 Algorithm: 1017 Algorithm:
1017 1. Initialize flow to 0 1018 1. Initialize flow to 0
1018 2. Find an augmenting path form source to sink. 1019 2. Find an augmenting path form source to sink.
1019 3. Send flow equal to the path's residual capacity along the edges of this path. 1020 3. Send flow equal to the path's residual capacity along the edges of this path.
1020 4. Repeat steps 2 and 3 until no new augmenting path is found. 1021 4. Repeat steps 2 and 3 until no new augmenting path is found.
1021 1022
1022 Parameters: 1023 Parameters:
1023 SOURCE: index of source vertex (input) 1024 SOURCE: index of source vertex (input)
1024 SINK: index of sink vertex (input) 1025 SINK: index of sink vertex (input)
1025 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be 1026 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1026 set to have a valid maximal flow by this routine. (input) 1027 set to have a valid maximal flow by this routine. (input)
1236 e->probability = REG_BR_PROB_BASE * e->count / bb->count; 1237 e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1237 if (dump_file) 1238 if (dump_file)
1238 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\t(%.1f%%)\n", 1239 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\t(%.1f%%)\n",
1239 e->count, e->probability * 100.0 / REG_BR_PROB_BASE); 1240 e->count, e->probability * 100.0 / REG_BR_PROB_BASE);
1240 } 1241 }
1241 } 1242 }
1242 1243
1243 ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs); 1244 ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs);
1244 EXIT_BLOCK_PTR->count = sum_edge_counts (EXIT_BLOCK_PTR->preds); 1245 EXIT_BLOCK_PTR->count = sum_edge_counts (EXIT_BLOCK_PTR->preds);
1245 1246
1246 /* Compute edge probabilities. */ 1247 /* Compute edge probabilities. */
1247 FOR_ALL_BB (bb) 1248 FOR_ALL_BB (bb)
1248 { 1249 {