PR tree-optimization/43833
[official-gcc/alias-decl.git] / gcc / mcf.c
blobaf993fba05778b77e11a0fd86714086c2e63d377
1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth
2 basic block and edge frequency counts.
3 Copyright (C) 2008, 2009
4 Free Software Foundation, Inc.
5 Contributed by Paul Yuan (yingbo.com@gmail.com) and
6 Vinodha Ramasamy (vinodha@google.com).
8 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* References:
24 [1] "Feedback-directed Optimizations in GCC with Estimated Edge Profiles
25 from Hardware Event Sampling", Vinodha Ramasamy, Paul Yuan, Dehao Chen,
26 and Robert Hundt; GCC Summit 2008.
27 [2] "Complementing Missing and Inaccurate Profiling Using a Minimum Cost
28 Circulation Algorithm", Roy Levin, Ilan Newman and Gadi Haber;
29 HiPEAC '08.
31 Algorithm to smooth basic block and edge counts:
32 1. create_fixup_graph: Create fixup graph by translating function CFG into
33 a graph that satisfies MCF algorithm requirements.
34 2. find_max_flow: Find maximal flow.
35 3. compute_residual_flow: Form residual network.
36 4. Repeat:
37 cancel_negative_cycle: While G contains a negative cost cycle C, reverse
38 the flow on the found cycle by the minimum residual capacity in that
39 cycle.
40 5. Form the minimal cost flow
41 f(u,v) = rf(v, u).
42 6. adjust_cfg_counts: Update initial edge weights with corrected weights.
43 delta(u.v) = f(u,v) -f(v,u).
44 w*(u,v) = w(u,v) + delta(u,v). */
46 #include "config.h"
47 #include "system.h"
48 #include "coretypes.h"
49 #include "tm.h"
50 #include "basic-block.h"
51 #include "output.h"
52 #include "langhooks.h"
53 #include "tree.h"
54 #include "gcov-io.h"
56 #include "profile.h"
58 /* CAP_INFINITY: Constant to represent infinite capacity. */
59 #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT)
61 /* COST FUNCTION. */
62 #define K_POS(b) ((b))
63 #define K_NEG(b) (50 * (b))
64 #define COST(k, w) ((k) / mcf_ln ((w) + 2))
65 /* Limit the number of iterations for cancel_negative_cycles() to ensure
66 reasonable compile time. */
67 #define MAX_ITER(n, e) 10 + (1000000 / ((n) * (e)))
68 typedef enum
70 INVALID_EDGE,
71 VERTEX_SPLIT_EDGE, /* Edge to represent vertex with w(e) = w(v). */
72 REDIRECT_EDGE, /* Edge after vertex transformation. */
73 REVERSE_EDGE,
74 SOURCE_CONNECT_EDGE, /* Single edge connecting to single source. */
75 SINK_CONNECT_EDGE, /* Single edge connecting to single sink. */
76 BALANCE_EDGE, /* Edge connecting with source/sink: cp(e) = 0. */
77 REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge. */
78 REVERSE_NORMALIZED_EDGE /* Normalized edge for a reverse edge. */
79 } edge_type;
81 /* Structure to represent an edge in the fixup graph. */
82 typedef struct fixup_edge_d
84 int src;
85 int dest;
86 /* Flag denoting type of edge and attributes for the flow field. */
87 edge_type type;
88 bool is_rflow_valid;
89 /* Index to the normalization vertex added for this edge. */
90 int norm_vertex_index;
91 /* Flow for this edge. */
92 gcov_type flow;
93 /* Residual flow for this edge - used during negative cycle canceling. */
94 gcov_type rflow;
95 gcov_type weight;
96 gcov_type cost;
97 gcov_type max_capacity;
98 } fixup_edge_type;
100 typedef fixup_edge_type *fixup_edge_p;
102 DEF_VEC_P (fixup_edge_p);
103 DEF_VEC_ALLOC_P (fixup_edge_p, heap);
105 /* Structure to represent a vertex in the fixup graph. */
106 typedef struct fixup_vertex_d
108 VEC (fixup_edge_p, heap) *succ_edges;
109 } fixup_vertex_type;
111 typedef fixup_vertex_type *fixup_vertex_p;
113 /* Fixup graph used in the MCF algorithm. */
114 typedef struct fixup_graph_d
116 /* Current number of vertices for the graph. */
117 int num_vertices;
118 /* Current number of edges for the graph. */
119 int num_edges;
120 /* Index of new entry vertex. */
121 int new_entry_index;
122 /* Index of new exit vertex. */
123 int new_exit_index;
124 /* Fixup vertex list. Adjacency list for fixup graph. */
125 fixup_vertex_p vertex_list;
126 /* Fixup edge list. */
127 fixup_edge_p edge_list;
128 } fixup_graph_type;
130 typedef struct queue_d
132 int *queue;
133 int head;
134 int tail;
135 int size;
136 } queue_type;
138 /* Structure used in the maximal flow routines to find augmenting path. */
139 typedef struct augmenting_path_d
141 /* Queue used to hold vertex indices. */
142 queue_type queue_list;
143 /* Vector to hold chain of pred vertex indices in augmenting path. */
144 int *bb_pred;
145 /* Vector that indicates if basic block i has been visited. */
146 int *is_visited;
147 } augmenting_path_type;
150 /* Function definitions. */
152 /* Dump routines to aid debugging. */
154 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */
156 static void
157 print_basic_block (FILE *file, fixup_graph_type *fixup_graph, int n)
159 if (n == ENTRY_BLOCK)
160 fputs ("ENTRY", file);
161 else if (n == ENTRY_BLOCK + 1)
162 fputs ("ENTRY''", file);
163 else if (n == 2 * EXIT_BLOCK)
164 fputs ("EXIT", file);
165 else if (n == 2 * EXIT_BLOCK + 1)
166 fputs ("EXIT''", file);
167 else if (n == fixup_graph->new_exit_index)
168 fputs ("NEW_EXIT", file);
169 else if (n == fixup_graph->new_entry_index)
170 fputs ("NEW_ENTRY", file);
171 else
173 fprintf (file, "%d", n / 2);
174 if (n % 2)
175 fputs ("''", file);
176 else
177 fputs ("'", file);
182 /* Print edge S->D for given fixup_graph with n' and n'' format.
183 PARAMETERS:
184 S is the index of the source vertex of the edge (input) and
185 D is the index of the destination vertex of the edge (input) for the given
186 fixup_graph (input). */
188 static void
189 print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d)
191 print_basic_block (file, fixup_graph, s);
192 fputs ("->", file);
193 print_basic_block (file, fixup_graph, d);
197 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
198 file. */
199 static void
200 dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge)
202 if (!fedge)
204 fputs ("NULL fixup graph edge.\n", file);
205 return;
208 print_edge (file, fixup_graph, fedge->src, fedge->dest);
209 fputs (": ", file);
211 if (fedge->type)
213 fprintf (file, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC "/",
214 fedge->flow);
215 if (fedge->max_capacity == CAP_INFINITY)
216 fputs ("+oo,", file);
217 else
218 fprintf (file, "" HOST_WIDEST_INT_PRINT_DEC ",", fedge->max_capacity);
221 if (fedge->is_rflow_valid)
223 if (fedge->rflow == CAP_INFINITY)
224 fputs (" rflow=+oo.", file);
225 else
226 fprintf (file, " rflow=" HOST_WIDEST_INT_PRINT_DEC ",", fedge->rflow);
229 fprintf (file, " cost=" HOST_WIDEST_INT_PRINT_DEC ".", fedge->cost);
231 fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest);
233 if (fedge->type)
235 switch (fedge->type)
237 case VERTEX_SPLIT_EDGE:
238 fputs (" @VERTEX_SPLIT_EDGE", file);
239 break;
241 case REDIRECT_EDGE:
242 fputs (" @REDIRECT_EDGE", file);
243 break;
245 case SOURCE_CONNECT_EDGE:
246 fputs (" @SOURCE_CONNECT_EDGE", file);
247 break;
249 case SINK_CONNECT_EDGE:
250 fputs (" @SINK_CONNECT_EDGE", file);
251 break;
253 case REVERSE_EDGE:
254 fputs (" @REVERSE_EDGE", file);
255 break;
257 case BALANCE_EDGE:
258 fputs (" @BALANCE_EDGE", file);
259 break;
261 case REDIRECT_NORMALIZED_EDGE:
262 case REVERSE_NORMALIZED_EDGE:
263 fputs (" @NORMALIZED_EDGE", file);
264 break;
266 default:
267 fputs (" @INVALID_EDGE", file);
268 break;
271 fputs ("\n", file);
275 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
276 file. The input string MSG is printed out as a heading. */
278 static void
279 dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg)
281 int i, j;
282 int fnum_vertices, fnum_edges;
284 fixup_vertex_p fvertex_list, pfvertex;
285 fixup_edge_p pfedge;
287 gcc_assert (fixup_graph);
288 fvertex_list = fixup_graph->vertex_list;
289 fnum_vertices = fixup_graph->num_vertices;
290 fnum_edges = fixup_graph->num_edges;
292 fprintf (file, "\nDump fixup graph for %s(): %s.\n",
293 lang_hooks.decl_printable_name (current_function_decl, 2), msg);
294 fprintf (file,
295 "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
296 fnum_vertices, fnum_edges, fixup_graph->new_exit_index);
298 for (i = 0; i < fnum_vertices; i++)
300 pfvertex = fvertex_list + i;
301 fprintf (file, "vertex_list[%d]: %d succ fixup edges.\n",
302 i, VEC_length (fixup_edge_p, pfvertex->succ_edges));
304 for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge);
305 j++)
307 /* Distinguish forward edges and backward edges in the residual flow
308 network. */
309 if (pfedge->type)
310 fputs ("(f) ", file);
311 else if (pfedge->is_rflow_valid)
312 fputs ("(b) ", file);
313 dump_fixup_edge (file, fixup_graph, pfedge);
317 fputs ("\n", file);
321 /* Utility routines. */
322 /* ln() implementation: approximate calculation. Returns ln of X. */
324 static double
325 mcf_ln (double x)
327 #define E 2.71828
328 int l = 1;
329 double m = E;
331 gcc_assert (x >= 0);
333 while (m < x)
335 m *= E;
336 l++;
339 return l;
343 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
344 implementation) by John Carmack. Returns sqrt of X. */
346 static double
347 mcf_sqrt (double x)
349 #define MAGIC_CONST1 0x1fbcf800
350 #define MAGIC_CONST2 0x5f3759df
351 union {
352 int intPart;
353 float floatPart;
354 } convertor, convertor2;
356 gcc_assert (x >= 0);
358 convertor.floatPart = x;
359 convertor2.floatPart = x;
360 convertor.intPart = MAGIC_CONST1 + (convertor.intPart >> 1);
361 convertor2.intPart = MAGIC_CONST2 - (convertor2.intPart >> 1);
363 return 0.5f * (convertor.floatPart + (x * convertor2.floatPart));
367 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
368 (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
369 added set to COST. */
371 static fixup_edge_p
372 add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost)
374 fixup_vertex_p curr_vertex = fixup_graph->vertex_list + src;
375 fixup_edge_p curr_edge = fixup_graph->edge_list + fixup_graph->num_edges;
376 curr_edge->src = src;
377 curr_edge->dest = dest;
378 curr_edge->cost = cost;
379 fixup_graph->num_edges++;
380 if (dump_file)
381 dump_fixup_edge (dump_file, fixup_graph, curr_edge);
382 VEC_safe_push (fixup_edge_p, heap, curr_vertex->succ_edges, curr_edge);
383 return curr_edge;
387 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
388 MAX_CAPACITY to the edge_list in the fixup graph. */
390 static void
391 add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
392 edge_type type, gcov_type weight, gcov_type cost,
393 gcov_type max_capacity)
395 fixup_edge_p curr_edge = add_edge(fixup_graph, src, dest, cost);
396 curr_edge->type = type;
397 curr_edge->weight = weight;
398 curr_edge->max_capacity = max_capacity;
402 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
403 to the fixup graph. */
405 static void
406 add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
407 gcov_type rflow, gcov_type cost)
409 fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost);
410 curr_edge->rflow = rflow;
411 curr_edge->is_rflow_valid = true;
412 /* This edge is not a valid edge - merely used to hold residual flow. */
413 curr_edge->type = INVALID_EDGE;
417 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
418 exist in the FIXUP_GRAPH. */
420 static fixup_edge_p
421 find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest)
423 int j;
424 fixup_edge_p pfedge;
425 fixup_vertex_p pfvertex;
427 gcc_assert (src < fixup_graph->num_vertices);
429 pfvertex = fixup_graph->vertex_list + src;
431 for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge);
432 j++)
433 if (pfedge->dest == dest)
434 return pfedge;
436 return NULL;
440 /* Cleanup routine to free structures in FIXUP_GRAPH. */
442 static void
443 delete_fixup_graph (fixup_graph_type *fixup_graph)
445 int i;
446 int fnum_vertices = fixup_graph->num_vertices;
447 fixup_vertex_p pfvertex = fixup_graph->vertex_list;
449 for (i = 0; i < fnum_vertices; i++, pfvertex++)
450 VEC_free (fixup_edge_p, heap, pfvertex->succ_edges);
452 free (fixup_graph->vertex_list);
453 free (fixup_graph->edge_list);
457 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
459 static void
460 create_fixup_graph (fixup_graph_type *fixup_graph)
462 double sqrt_avg_vertex_weight = 0;
463 double total_vertex_weight = 0;
464 double k_pos = 0;
465 double k_neg = 0;
466 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */
467 gcov_type *diff_out_in = NULL;
468 gcov_type supply_value = 1, demand_value = 0;
469 gcov_type fcost = 0;
470 int new_entry_index = 0, new_exit_index = 0;
471 int i = 0, j = 0;
472 int new_index = 0;
473 basic_block bb;
474 edge e;
475 edge_iterator ei;
476 fixup_edge_p pfedge, r_pfedge;
477 fixup_edge_p fedge_list;
478 int fnum_edges;
480 /* Each basic_block will be split into 2 during vertex transformation. */
481 int fnum_vertices_after_transform = 2 * n_basic_blocks;
482 int fnum_edges_after_transform = n_edges + n_basic_blocks;
484 /* Count the new SOURCE and EXIT vertices to be added. */
485 int fmax_num_vertices =
486 fnum_vertices_after_transform + n_edges + n_basic_blocks + 2;
488 /* In create_fixup_graph: Each basic block and edge can be split into 3
489 edges. Number of balance edges = n_basic_blocks. So after
490 create_fixup_graph:
491 max_edges = 4 * n_basic_blocks + 3 * n_edges
492 Accounting for residual flow edges
493 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
494 = 8 * n_basic_blocks + 6 * n_edges
495 < 8 * n_basic_blocks + 8 * n_edges. */
496 int fmax_num_edges = 8 * (n_basic_blocks + n_edges);
498 /* Initial num of vertices in the fixup graph. */
499 fixup_graph->num_vertices = n_basic_blocks;
501 /* Fixup graph vertex list. */
502 fixup_graph->vertex_list =
503 (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type));
505 /* Fixup graph edge list. */
506 fixup_graph->edge_list =
507 (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type));
509 diff_out_in =
510 (gcov_type *) xcalloc (1 + fnum_vertices_after_transform,
511 sizeof (gcov_type));
513 /* Compute constants b, k_pos, k_neg used in the cost function calculation.
514 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */
515 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
516 total_vertex_weight += bb->count;
518 sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / n_basic_blocks);
520 k_pos = K_POS (sqrt_avg_vertex_weight);
521 k_neg = K_NEG (sqrt_avg_vertex_weight);
523 /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
524 connected by an edge e from v' to v''. w(e) = w(v). */
526 if (dump_file)
527 fprintf (dump_file, "\nVertex transformation:\n");
529 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
531 /* v'->v'': index1->(index1+1). */
532 i = 2 * bb->index;
533 fcost = (gcov_type) COST (k_pos, bb->count);
534 add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count,
535 fcost, CAP_INFINITY);
536 fixup_graph->num_vertices++;
538 FOR_EACH_EDGE (e, ei, bb->succs)
540 /* Edges with ignore attribute set should be treated like they don't
541 exist. */
542 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
543 continue;
544 j = 2 * e->dest->index;
545 fcost = (gcov_type) COST (k_pos, e->count);
546 add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost,
547 CAP_INFINITY);
551 /* After vertex transformation. */
552 gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform);
553 /* Redirect edges are not added for edges with ignore attribute. */
554 gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform);
556 fnum_edges_after_transform = fixup_graph->num_edges;
558 /* 2. Initialize D(v). */
559 for (i = 0; i < fnum_edges_after_transform; i++)
561 pfedge = fixup_graph->edge_list + i;
562 diff_out_in[pfedge->src] += pfedge->weight;
563 diff_out_in[pfedge->dest] -= pfedge->weight;
566 /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */
567 for (i = 0; i <= 3; i++)
568 diff_out_in[i] = 0;
570 /* 3. Add reverse edges: needed to decrease counts during smoothing. */
571 if (dump_file)
572 fprintf (dump_file, "\nReverse edges:\n");
573 for (i = 0; i < fnum_edges_after_transform; i++)
575 pfedge = fixup_graph->edge_list + i;
576 if ((pfedge->src == 0) || (pfedge->src == 2))
577 continue;
578 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
579 if (!r_pfedge && pfedge->weight)
581 /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
582 capacity is 0. */
583 fcost = (gcov_type) COST (k_neg, pfedge->weight);
584 add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src,
585 REVERSE_EDGE, 0, fcost, pfedge->weight);
589 /* 4. Create single source and sink. Connect new source vertex s' to function
590 entry block. Connect sink vertex t' to function exit. */
591 if (dump_file)
592 fprintf (dump_file, "\ns'->S, T->t':\n");
594 new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices;
595 fixup_graph->num_vertices++;
596 /* Set supply_value to 1 to avoid zero count function ENTRY. */
597 add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE,
598 1 /* supply_value */, 0, 1 /* supply_value */);
600 /* Create new exit with EXIT_BLOCK as single pred. */
601 new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices;
602 fixup_graph->num_vertices++;
603 add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index,
604 SINK_CONNECT_EDGE,
605 0 /* demand_value */, 0, 0 /* demand_value */);
607 /* Connect vertices with unbalanced D(v) to source/sink. */
608 if (dump_file)
609 fprintf (dump_file, "\nD(v) balance:\n");
610 /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
611 diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2. */
612 for (i = 4; i < new_entry_index; i += 2)
614 if (diff_out_in[i] > 0)
616 add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0,
617 diff_out_in[i]);
618 demand_value += diff_out_in[i];
620 else if (diff_out_in[i] < 0)
622 add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0,
623 -diff_out_in[i]);
624 supply_value -= diff_out_in[i];
628 /* Set supply = demand. */
629 if (dump_file)
631 fprintf (dump_file, "\nAdjust supply and demand:\n");
632 fprintf (dump_file, "supply_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
633 supply_value);
634 fprintf (dump_file, "demand_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
635 demand_value);
638 if (demand_value > supply_value)
640 pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK);
641 pfedge->max_capacity += (demand_value - supply_value);
643 else
645 pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index);
646 pfedge->max_capacity += (supply_value - demand_value);
649 /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
650 created by the vertex transformation step from self-edges in the original
651 CFG and by the reverse edges added earlier. */
652 if (dump_file)
653 fprintf (dump_file, "\nNormalize edges:\n");
655 fnum_edges = fixup_graph->num_edges;
656 fedge_list = fixup_graph->edge_list;
658 for (i = 0; i < fnum_edges; i++)
660 pfedge = fedge_list + i;
661 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
662 if (((pfedge->type == VERTEX_SPLIT_EDGE)
663 || (pfedge->type == REDIRECT_EDGE)) && r_pfedge)
665 new_index = fixup_graph->num_vertices;
666 fixup_graph->num_vertices++;
668 if (dump_file)
670 fprintf (dump_file, "\nAnti-parallel edge:\n");
671 dump_fixup_edge (dump_file, fixup_graph, pfedge);
672 dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
673 fprintf (dump_file, "New vertex is %d.\n", new_index);
674 fprintf (dump_file, "------------------\n");
677 pfedge->cost /= 2;
678 pfedge->norm_vertex_index = new_index;
679 if (dump_file)
681 fprintf (dump_file, "After normalization:\n");
682 dump_fixup_edge (dump_file, fixup_graph, pfedge);
685 /* Add a new fixup edge: new_index->src. */
686 add_fixup_edge (fixup_graph, new_index, pfedge->src,
687 REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost,
688 r_pfedge->max_capacity);
689 gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices);
691 /* Edge: r_pfedge->src -> r_pfedge->dest
692 ==> r_pfedge->src -> new_index. */
693 r_pfedge->dest = new_index;
694 r_pfedge->type = REVERSE_NORMALIZED_EDGE;
695 r_pfedge->cost = pfedge->cost;
696 r_pfedge->max_capacity = pfedge->max_capacity;
697 if (dump_file)
698 dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
702 if (dump_file)
703 dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()");
705 /* Cleanup. */
706 free (diff_out_in);
710 /* Allocates space for the structures in AUGMENTING_PATH. The space needed is
711 proportional to the number of nodes in the graph, which is given by
712 GRAPH_SIZE. */
714 static void
715 init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size)
717 augmenting_path->queue_list.queue = (int *)
718 xcalloc (graph_size + 2, sizeof (int));
719 augmenting_path->queue_list.size = graph_size + 2;
720 augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int));
721 augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int));
724 /* Free the structures in AUGMENTING_PATH. */
725 static void
726 free_augmenting_path (augmenting_path_type *augmenting_path)
728 free (augmenting_path->queue_list.queue);
729 free (augmenting_path->bb_pred);
730 free (augmenting_path->is_visited);
734 /* Queue routines. Assumes queue will never overflow. */
736 static void
737 init_queue (queue_type *queue_list)
739 gcc_assert (queue_list);
740 queue_list->head = 0;
741 queue_list->tail = 0;
744 /* Return true if QUEUE_LIST is empty. */
745 static bool
746 is_empty (queue_type *queue_list)
748 return (queue_list->head == queue_list->tail);
751 /* Insert element X into QUEUE_LIST. */
752 static void
753 enqueue (queue_type *queue_list, int x)
755 gcc_assert (queue_list->tail < queue_list->size);
756 queue_list->queue[queue_list->tail] = x;
757 (queue_list->tail)++;
760 /* Return the first element in QUEUE_LIST. */
761 static int
762 dequeue (queue_type *queue_list)
764 int x;
765 gcc_assert (queue_list->head >= 0);
766 x = queue_list->queue[queue_list->head];
767 (queue_list->head)++;
768 return x;
772 /* Finds a negative cycle in the residual network using
773 the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
774 minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
775 considered.
777 Parameters:
778 FIXUP_GRAPH - Residual graph (input/output)
779 The following are allocated/freed by the caller:
780 PI - Vector to hold predecessors in path (pi = pred index)
781 D - D[I] holds minimum cost of path from i to sink
782 CYCLE - Vector to hold the minimum cost cycle
784 Return:
785 true if a negative cycle was found, false otherwise. */
787 static bool
788 cancel_negative_cycle (fixup_graph_type *fixup_graph,
789 int *pi, gcov_type *d, int *cycle)
791 int i, j, k;
792 int fnum_vertices, fnum_edges;
793 fixup_edge_p fedge_list, pfedge, r_pfedge;
794 bool found_cycle = false;
795 int cycle_start = 0, cycle_end = 0;
796 gcov_type sum_cost = 0, cycle_flow = 0;
797 int new_entry_index;
798 bool propagated = false;
800 gcc_assert (fixup_graph);
801 fnum_vertices = fixup_graph->num_vertices;
802 fnum_edges = fixup_graph->num_edges;
803 fedge_list = fixup_graph->edge_list;
804 new_entry_index = fixup_graph->new_entry_index;
806 /* Initialize. */
807 /* Skip ENTRY. */
808 for (i = 1; i < fnum_vertices; i++)
810 d[i] = CAP_INFINITY;
811 pi[i] = -1;
812 cycle[i] = -1;
814 d[ENTRY_BLOCK] = 0;
816 /* Relax. */
817 for (k = 1; k < fnum_vertices; k++)
819 propagated = false;
820 for (i = 0; i < fnum_edges; i++)
822 pfedge = fedge_list + i;
823 if (pfedge->src == new_entry_index)
824 continue;
825 if (pfedge->is_rflow_valid && pfedge->rflow
826 && d[pfedge->src] != CAP_INFINITY
827 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
829 d[pfedge->dest] = d[pfedge->src] + pfedge->cost;
830 pi[pfedge->dest] = pfedge->src;
831 propagated = true;
834 if (!propagated)
835 break;
838 if (!propagated)
839 /* No negative cycles exist. */
840 return 0;
842 /* Detect. */
843 for (i = 0; i < fnum_edges; i++)
845 pfedge = fedge_list + i;
846 if (pfedge->src == new_entry_index)
847 continue;
848 if (pfedge->is_rflow_valid && pfedge->rflow
849 && d[pfedge->src] != CAP_INFINITY
850 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
852 found_cycle = true;
853 break;
857 if (!found_cycle)
858 return 0;
860 /* Augment the cycle with the cycle's minimum residual capacity. */
861 found_cycle = false;
862 cycle[0] = pfedge->dest;
863 j = pfedge->dest;
865 for (i = 1; i < fnum_vertices; i++)
867 j = pi[j];
868 cycle[i] = j;
869 for (k = 0; k < i; k++)
871 if (cycle[k] == j)
873 /* cycle[k] -> ... -> cycle[i]. */
874 cycle_start = k;
875 cycle_end = i;
876 found_cycle = true;
877 break;
880 if (found_cycle)
881 break;
884 gcc_assert (cycle[cycle_start] == cycle[cycle_end]);
885 if (dump_file)
886 fprintf (dump_file, "\nNegative cycle length is %d:\n",
887 cycle_end - cycle_start);
889 sum_cost = 0;
890 cycle_flow = CAP_INFINITY;
891 for (k = cycle_start; k < cycle_end; k++)
893 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
894 cycle_flow = MIN (cycle_flow, pfedge->rflow);
895 sum_cost += pfedge->cost;
896 if (dump_file)
897 fprintf (dump_file, "%d ", cycle[k]);
900 if (dump_file)
902 fprintf (dump_file, "%d", cycle[k]);
903 fprintf (dump_file,
904 ": (" HOST_WIDEST_INT_PRINT_DEC ", " HOST_WIDEST_INT_PRINT_DEC
905 ")\n", sum_cost, cycle_flow);
906 fprintf (dump_file,
907 "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC "\n",
908 cycle_flow);
911 for (k = cycle_start; k < cycle_end; k++)
913 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
914 r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]);
915 pfedge->rflow -= cycle_flow;
916 if (pfedge->type)
917 pfedge->flow += cycle_flow;
918 r_pfedge->rflow += cycle_flow;
919 if (r_pfedge->type)
920 r_pfedge->flow -= cycle_flow;
923 return true;
927 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
928 the edges. ENTRY and EXIT vertices should not be considered. */
930 static void
931 compute_residual_flow (fixup_graph_type *fixup_graph)
933 int i;
934 int fnum_edges;
935 fixup_edge_p fedge_list, pfedge;
937 gcc_assert (fixup_graph);
939 if (dump_file)
940 fputs ("\ncompute_residual_flow():\n", dump_file);
942 fnum_edges = fixup_graph->num_edges;
943 fedge_list = fixup_graph->edge_list;
945 for (i = 0; i < fnum_edges; i++)
947 pfedge = fedge_list + i;
948 pfedge->rflow = pfedge->max_capacity - pfedge->flow;
949 pfedge->is_rflow_valid = true;
950 add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow,
951 -pfedge->cost);
956 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
957 SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
958 this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
959 to reflect the path found.
960 Returns: 0 if no augmenting path is found, 1 otherwise. */
962 static int
963 find_augmenting_path (fixup_graph_type *fixup_graph,
964 augmenting_path_type *augmenting_path, int source,
965 int sink)
967 int u = 0;
968 int i;
969 fixup_vertex_p fvertex_list, pfvertex;
970 fixup_edge_p pfedge;
971 int *bb_pred, *is_visited;
972 queue_type *queue_list;
974 gcc_assert (augmenting_path);
975 bb_pred = augmenting_path->bb_pred;
976 gcc_assert (bb_pred);
977 is_visited = augmenting_path->is_visited;
978 gcc_assert (is_visited);
979 queue_list = &(augmenting_path->queue_list);
981 gcc_assert (fixup_graph);
983 fvertex_list = fixup_graph->vertex_list;
985 for (u = 0; u < fixup_graph->num_vertices; u++)
986 is_visited[u] = 0;
988 init_queue (queue_list);
989 enqueue (queue_list, source);
990 bb_pred[source] = -1;
992 while (!is_empty (queue_list))
994 u = dequeue (queue_list);
995 is_visited[u] = 1;
996 pfvertex = fvertex_list + u;
997 for (i = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, i, pfedge);
998 i++)
1000 int dest = pfedge->dest;
1001 if ((pfedge->rflow > 0) && (is_visited[dest] == 0))
1003 enqueue (queue_list, dest);
1004 bb_pred[dest] = u;
1005 is_visited[dest] = 1;
1006 if (dest == sink)
1007 return 1;
1012 return 0;
1016 /* Routine to find the maximal flow:
1017 Algorithm:
1018 1. Initialize flow to 0
1019 2. Find an augmenting path form source to sink.
1020 3. Send flow equal to the path's residual capacity along the edges of this path.
1021 4. Repeat steps 2 and 3 until no new augmenting path is found.
1023 Parameters:
1024 SOURCE: index of source vertex (input)
1025 SINK: index of sink vertex (input)
1026 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1027 set to have a valid maximal flow by this routine. (input)
1028 Return: Maximum flow possible. */
1030 static gcov_type
1031 find_max_flow (fixup_graph_type *fixup_graph, int source, int sink)
1033 int fnum_edges;
1034 augmenting_path_type augmenting_path;
1035 int *bb_pred;
1036 gcov_type max_flow = 0;
1037 int i, u;
1038 fixup_edge_p fedge_list, pfedge, r_pfedge;
1040 gcc_assert (fixup_graph);
1042 fnum_edges = fixup_graph->num_edges;
1043 fedge_list = fixup_graph->edge_list;
1045 /* Initialize flow to 0. */
1046 for (i = 0; i < fnum_edges; i++)
1048 pfedge = fedge_list + i;
1049 pfedge->flow = 0;
1052 compute_residual_flow (fixup_graph);
1054 init_augmenting_path (&augmenting_path, fixup_graph->num_vertices);
1056 bb_pred = augmenting_path.bb_pred;
1057 while (find_augmenting_path (fixup_graph, &augmenting_path, source, sink))
1059 /* Determine the amount by which we can increment the flow. */
1060 gcov_type increment = CAP_INFINITY;
1061 for (u = sink; u != source; u = bb_pred[u])
1063 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1064 increment = MIN (increment, pfedge->rflow);
1066 max_flow += increment;
1068 /* Now increment the flow. EXIT vertex index is 1. */
1069 for (u = sink; u != source; u = bb_pred[u])
1071 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1072 r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]);
1073 if (pfedge->type)
1075 /* forward edge. */
1076 pfedge->flow += increment;
1077 pfedge->rflow -= increment;
1078 r_pfedge->rflow += increment;
1080 else
1082 /* backward edge. */
1083 gcc_assert (r_pfedge->type);
1084 r_pfedge->rflow += increment;
1085 r_pfedge->flow -= increment;
1086 pfedge->rflow -= increment;
1090 if (dump_file)
1092 fprintf (dump_file, "\nDump augmenting path:\n");
1093 for (u = sink; u != source; u = bb_pred[u])
1095 print_basic_block (dump_file, fixup_graph, u);
1096 fprintf (dump_file, "<-");
1098 fprintf (dump_file,
1099 "ENTRY (path_capacity=" HOST_WIDEST_INT_PRINT_DEC ")\n",
1100 increment);
1101 fprintf (dump_file,
1102 "Network flow is " HOST_WIDEST_INT_PRINT_DEC ".\n",
1103 max_flow);
1107 free_augmenting_path (&augmenting_path);
1108 if (dump_file)
1109 dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()");
1110 return max_flow;
1114 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1115 after applying the find_minimum_cost_flow() routine. */
1117 static void
1118 adjust_cfg_counts (fixup_graph_type *fixup_graph)
1120 basic_block bb;
1121 edge e;
1122 edge_iterator ei;
1123 int i, j;
1124 fixup_edge_p pfedge, pfedge_n;
1126 gcc_assert (fixup_graph);
1128 if (dump_file)
1129 fprintf (dump_file, "\nadjust_cfg_counts():\n");
1131 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1133 i = 2 * bb->index;
1135 /* Fixup BB. */
1136 if (dump_file)
1137 fprintf (dump_file,
1138 "BB%d: " HOST_WIDEST_INT_PRINT_DEC "", bb->index, bb->count);
1140 pfedge = find_fixup_edge (fixup_graph, i, i + 1);
1141 if (pfedge->flow)
1143 bb->count += pfedge->flow;
1144 if (dump_file)
1146 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1147 pfedge->flow);
1148 print_edge (dump_file, fixup_graph, i, i + 1);
1149 fprintf (dump_file, ")");
1153 pfedge_n =
1154 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1155 /* Deduct flow from normalized reverse edge. */
1156 if (pfedge->norm_vertex_index && pfedge_n->flow)
1158 bb->count -= pfedge_n->flow;
1159 if (dump_file)
1161 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
1162 pfedge_n->flow);
1163 print_edge (dump_file, fixup_graph, i + 1,
1164 pfedge->norm_vertex_index);
1165 fprintf (dump_file, ")");
1168 if (dump_file)
1169 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\n", bb->count);
1171 /* Fixup edge. */
1172 FOR_EACH_EDGE (e, ei, bb->succs)
1174 /* Treat edges with ignore attribute set as if they don't exist. */
1175 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1176 continue;
1178 j = 2 * e->dest->index;
1179 if (dump_file)
1180 fprintf (dump_file, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC "",
1181 bb->index, e->dest->index, e->count);
1183 pfedge = find_fixup_edge (fixup_graph, i + 1, j);
1185 if (bb->index != e->dest->index)
1187 /* Non-self edge. */
1188 if (pfedge->flow)
1190 e->count += pfedge->flow;
1191 if (dump_file)
1193 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1194 pfedge->flow);
1195 print_edge (dump_file, fixup_graph, i + 1, j);
1196 fprintf (dump_file, ")");
1200 pfedge_n =
1201 find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index);
1202 /* Deduct flow from normalized reverse edge. */
1203 if (pfedge->norm_vertex_index && pfedge_n->flow)
1205 e->count -= pfedge_n->flow;
1206 if (dump_file)
1208 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
1209 pfedge_n->flow);
1210 print_edge (dump_file, fixup_graph, j,
1211 pfedge->norm_vertex_index);
1212 fprintf (dump_file, ")");
1216 else
1218 /* Handle self edges. Self edge is split with a normalization
1219 vertex. Here i=j. */
1220 pfedge = find_fixup_edge (fixup_graph, j, i + 1);
1221 pfedge_n =
1222 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1223 e->count += pfedge_n->flow;
1224 bb->count += pfedge_n->flow;
1225 if (dump_file)
1227 fprintf (dump_file, "(self edge)");
1228 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1229 pfedge_n->flow);
1230 print_edge (dump_file, fixup_graph, i + 1,
1231 pfedge->norm_vertex_index);
1232 fprintf (dump_file, ")");
1236 if (bb->count)
1237 e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1238 if (dump_file)
1239 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\t(%.1f%%)\n",
1240 e->count, e->probability * 100.0 / REG_BR_PROB_BASE);
1244 ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs);
1245 EXIT_BLOCK_PTR->count = sum_edge_counts (EXIT_BLOCK_PTR->preds);
1247 /* Compute edge probabilities. */
1248 FOR_ALL_BB (bb)
1250 if (bb->count)
1252 FOR_EACH_EDGE (e, ei, bb->succs)
1253 e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1255 else
1257 int total = 0;
1258 FOR_EACH_EDGE (e, ei, bb->succs)
1259 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1260 total++;
1261 if (total)
1263 FOR_EACH_EDGE (e, ei, bb->succs)
1265 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1266 e->probability = REG_BR_PROB_BASE / total;
1267 else
1268 e->probability = 0;
1271 else
1273 total += EDGE_COUNT (bb->succs);
1274 FOR_EACH_EDGE (e, ei, bb->succs)
1275 e->probability = REG_BR_PROB_BASE / total;
1280 if (dump_file)
1282 fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n",
1283 lang_hooks.decl_printable_name (current_function_decl, 2));
1284 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
1286 if ((bb->count != sum_edge_counts (bb->preds))
1287 || (bb->count != sum_edge_counts (bb->succs)))
1289 fprintf (dump_file,
1290 "BB%d(" HOST_WIDEST_INT_PRINT_DEC ") **INVALID**: ",
1291 bb->index, bb->count);
1292 fprintf (stderr,
1293 "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC
1294 ") **INVALID**: \n", bb->index, bb->count);
1295 fprintf (dump_file, "in_edges=" HOST_WIDEST_INT_PRINT_DEC " ",
1296 sum_edge_counts (bb->preds));
1297 fprintf (dump_file, "out_edges=" HOST_WIDEST_INT_PRINT_DEC "\n",
1298 sum_edge_counts (bb->succs));
1305 /* Implements the negative cycle canceling algorithm to compute a minimum cost
1306 flow.
1307 Algorithm:
1308 1. Find maximal flow.
1309 2. Form residual network
1310 3. Repeat:
1311 While G contains a negative cost cycle C, reverse the flow on the found cycle
1312 by the minimum residual capacity in that cycle.
1313 4. Form the minimal cost flow
1314 f(u,v) = rf(v, u)
1315 Input:
1316 FIXUP_GRAPH - Initial fixup graph.
1317 The flow field is modified to represent the minimum cost flow. */
1319 static void
1320 find_minimum_cost_flow (fixup_graph_type *fixup_graph)
1322 /* Holds the index of predecessor in path. */
1323 int *pred;
1324 /* Used to hold the minimum cost cycle. */
1325 int *cycle;
1326 /* Used to record the number of iterations of cancel_negative_cycle. */
1327 int iteration;
1328 /* Vector d[i] holds the minimum cost of path from i to sink. */
1329 gcov_type *d;
1330 int fnum_vertices;
1331 int new_exit_index;
1332 int new_entry_index;
1334 gcc_assert (fixup_graph);
1335 fnum_vertices = fixup_graph->num_vertices;
1336 new_exit_index = fixup_graph->new_exit_index;
1337 new_entry_index = fixup_graph->new_entry_index;
1339 find_max_flow (fixup_graph, new_entry_index, new_exit_index);
1341 /* Initialize the structures for find_negative_cycle(). */
1342 pred = (int *) xcalloc (fnum_vertices, sizeof (int));
1343 d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type));
1344 cycle = (int *) xcalloc (fnum_vertices, sizeof (int));
1346 /* Repeatedly find and cancel negative cost cycles, until
1347 no more negative cycles exist. This also updates the flow field
1348 to represent the minimum cost flow so far. */
1349 iteration = 0;
1350 while (cancel_negative_cycle (fixup_graph, pred, d, cycle))
1352 iteration++;
1353 if (iteration > MAX_ITER (fixup_graph->num_vertices,
1354 fixup_graph->num_edges))
1355 break;
1358 if (dump_file)
1359 dump_fixup_graph (dump_file, fixup_graph,
1360 "After find_minimum_cost_flow()");
1362 /* Cleanup structures. */
1363 free (pred);
1364 free (d);
1365 free (cycle);
1369 /* Compute the sum of the edge counts in TO_EDGES. */
1371 gcov_type
1372 sum_edge_counts (VEC (edge, gc) *to_edges)
1374 gcov_type sum = 0;
1375 edge e;
1376 edge_iterator ei;
1378 FOR_EACH_EDGE (e, ei, to_edges)
1380 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1381 continue;
1382 sum += e->count;
1384 return sum;
1388 /* Main routine. Smoothes the intial assigned basic block and edge counts using
1389 a minimum cost flow algorithm, to ensure that the flow consistency rule is
1390 obeyed: sum of outgoing edges = sum of incoming edges for each basic
1391 block. */
1393 void
1394 mcf_smooth_cfg (void)
1396 fixup_graph_type fixup_graph;
1397 memset (&fixup_graph, 0, sizeof (fixup_graph));
1398 create_fixup_graph (&fixup_graph);
1399 find_minimum_cost_flow (&fixup_graph);
1400 adjust_cfg_counts (&fixup_graph);
1401 delete_fixup_graph (&fixup_graph);