1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth
2    basic block and edge frequency counts.
3    Copyright (C) 2008-2015 Free Software Foundation, Inc.
4    Contributed by Paul Yuan (yingbo.com@gmail.com) and
5                   Vinodha Ramasamy (vinodha@google.com).
7 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
22 /* References:
23     "Feedback-directed Optimizations in GCC with Estimated Edge Profiles
24         from Hardware Event Sampling", Vinodha Ramasamy, Paul Yuan, Dehao Chen,
25         and Robert Hundt; GCC Summit 2008.
26     "Complementing Missing and Inaccurate Profiling Using a Minimum Cost
27         Circulation Algorithm", Roy Levin, Ilan Newman and Gadi Haber;
28         HiPEAC '08.
30    Algorithm to smooth basic block and edge counts:
31    1. create_fixup_graph: Create fixup graph by translating function CFG into
32       a graph that satisfies MCF algorithm requirements.
33    2. find_max_flow: Find maximal flow.
34    3. compute_residual_flow: Form residual network.
35    4. Repeat:
36       cancel_negative_cycle: While G contains a negative cost cycle C, reverse
37       the flow on the found cycle by the minimum residual capacity in that
38       cycle.
39    5. Form the minimal cost flow
40       f(u,v) = rf(v, u).
41    6. adjust_cfg_counts: Update initial edge weights with corrected weights.
42       delta(u.v) = f(u,v) -f(v,u).
43       w*(u,v) = w(u,v) + delta(u,v).  */
45 #include "config.h"
46 #include "system.h"
47 #include "coretypes.h"
48 #include "predict.h"
49 #include "vec.h"
50 #include "hashtab.h"
51 #include "hash-set.h"
52 #include "machmode.h"
53 #include "tm.h"
54 #include "hard-reg-set.h"
55 #include "input.h"
56 #include "function.h"
57 #include "dominance.h"
58 #include "cfg.h"
59 #include "basic-block.h"
60 #include "gcov-io.h"
61 #include "profile.h"
62 #include "dumpfile.h"
64 /* CAP_INFINITY: Constant to represent infinite capacity.  */
65 #define CAP_INFINITY INTTYPE_MAXIMUM (int64_t)
67 /* COST FUNCTION.  */
68 #define K_POS(b)        ((b))
69 #define K_NEG(b)        (50 * (b))
70 #define COST(k, w)      ((k) / mcf_ln ((w) + 2))
71 /* Limit the number of iterations for cancel_negative_cycles() to ensure
72    reasonable compile time.  */
73 #define MAX_ITER(n, e)  10 + (1000000 / ((n) * (e)))
74 typedef enum
75 {
76   INVALID_EDGE,
77   VERTEX_SPLIT_EDGE,        /* Edge to represent vertex with w(e) = w(v).  */
78   REDIRECT_EDGE,            /* Edge after vertex transformation.  */
79   REVERSE_EDGE,
80   SOURCE_CONNECT_EDGE,      /* Single edge connecting to single source.  */
81   SINK_CONNECT_EDGE,        /* Single edge connecting to single sink.  */
82   BALANCE_EDGE,             /* Edge connecting with source/sink: cp(e) = 0.  */
83   REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge.  */
84   REVERSE_NORMALIZED_EDGE   /* Normalized edge for a reverse edge.  */
85 } edge_type;
87 /* Structure to represent an edge in the fixup graph.  */
88 typedef struct fixup_edge_d
89 {
90   int src;
91   int dest;
92   /* Flag denoting type of edge and attributes for the flow field.  */
93   edge_type type;
94   bool is_rflow_valid;
95   /* Index to the normalization vertex added for this edge.  */
96   int norm_vertex_index;
97   /* Flow for this edge.  */
98   gcov_type flow;
99   /* Residual flow for this edge - used during negative cycle canceling.  */
100   gcov_type rflow;
101   gcov_type weight;
102   gcov_type cost;
103   gcov_type max_capacity;
104 } fixup_edge_type;
106 typedef fixup_edge_type *fixup_edge_p;
109 /* Structure to represent a vertex in the fixup graph.  */
110 typedef struct fixup_vertex_d
111 {
112   vec<fixup_edge_p> succ_edges;
113 } fixup_vertex_type;
115 typedef fixup_vertex_type *fixup_vertex_p;
117 /* Fixup graph used in the MCF algorithm.  */
118 typedef struct fixup_graph_d
119 {
120   /* Current number of vertices for the graph.  */
121   int num_vertices;
122   /* Current number of edges for the graph.  */
123   int num_edges;
124   /* Index of new entry vertex.  */
125   int new_entry_index;
126   /* Index of new exit vertex.  */
127   int new_exit_index;
128   /* Fixup vertex list. Adjacency list for fixup graph.  */
129   fixup_vertex_p vertex_list;
130   /* Fixup edge list.  */
131   fixup_edge_p edge_list;
132 } fixup_graph_type;
134 typedef struct queue_d
135 {
136   int *queue;
138   int tail;
139   int size;
140 } queue_type;
142 /* Structure used in the maximal flow routines to find augmenting path.  */
143 typedef struct augmenting_path_d
144 {
145   /* Queue used to hold vertex indices.  */
146   queue_type queue_list;
147   /* Vector to hold chain of pred vertex indices in augmenting path.  */
148   int *bb_pred;
149   /* Vector that indicates if basic block i has been visited.  */
150   int *is_visited;
151 } augmenting_path_type;
154 /* Function definitions.  */
156 /* Dump routines to aid debugging.  */
158 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format.  */
160 static void
161 print_basic_block (FILE *file, fixup_graph_type *fixup_graph, int n)
162 {
163   if (n == ENTRY_BLOCK)
164     fputs ("ENTRY", file);
165   else if (n == ENTRY_BLOCK + 1)
166     fputs ("ENTRY''", file);
167   else if (n == 2 * EXIT_BLOCK)
168     fputs ("EXIT", file);
169   else if (n == 2 * EXIT_BLOCK + 1)
170     fputs ("EXIT''", file);
171   else if (n == fixup_graph->new_exit_index)
172     fputs ("NEW_EXIT", file);
173   else if (n == fixup_graph->new_entry_index)
174     fputs ("NEW_ENTRY", file);
175   else
176     {
177       fprintf (file, "%d", n / 2);
178       if (n % 2)
179         fputs ("''", file);
180       else
181         fputs ("'", file);
182     }
183 }
186 /* Print edge S->D for given fixup_graph with n' and n'' format.
187    PARAMETERS:
188    S is the index of the source vertex of the edge (input) and
189    D is the index of the destination vertex of the edge (input) for the given
190    fixup_graph (input).  */
192 static void
193 print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d)
194 {
195   print_basic_block (file, fixup_graph, s);
196   fputs ("->", file);
197   print_basic_block (file, fixup_graph, d);
198 }
201 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
202    file.  */
203 static void
204 dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge)
205 {
206   if (!fedge)
207     {
208       fputs ("NULL fixup graph edge.\n", file);
209       return;
210     }
212   print_edge (file, fixup_graph, fedge->src, fedge->dest);
213   fputs (": ", file);
215   if (fedge->type)
216     {
217       fprintf (file, "flow/capacity=%"PRId64 "/",
218                fedge->flow);
219       if (fedge->max_capacity == CAP_INFINITY)
220         fputs ("+oo,", file);
221       else
222         fprintf (file, "%"PRId64 ",", fedge->max_capacity);
223     }
225   if (fedge->is_rflow_valid)
226     {
227       if (fedge->rflow == CAP_INFINITY)
228         fputs (" rflow=+oo.", file);
229       else
230         fprintf (file, " rflow=%"PRId64 ",", fedge->rflow);
231     }
233   fprintf (file, " cost=%"PRId64 ".", fedge->cost);
235   fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest);
237   if (fedge->type)
238     {
239       switch (fedge->type)
240         {
241         case VERTEX_SPLIT_EDGE:
242           fputs (" @VERTEX_SPLIT_EDGE", file);
243           break;
245         case REDIRECT_EDGE:
246           fputs (" @REDIRECT_EDGE", file);
247           break;
249         case SOURCE_CONNECT_EDGE:
250           fputs (" @SOURCE_CONNECT_EDGE", file);
251           break;
253         case SINK_CONNECT_EDGE:
254           fputs (" @SINK_CONNECT_EDGE", file);
255           break;
257         case REVERSE_EDGE:
258           fputs (" @REVERSE_EDGE", file);
259           break;
261         case BALANCE_EDGE:
262           fputs (" @BALANCE_EDGE", file);
263           break;
265         case REDIRECT_NORMALIZED_EDGE:
266         case REVERSE_NORMALIZED_EDGE:
267           fputs ("  @NORMALIZED_EDGE", file);
268           break;
270         default:
271           fputs (" @INVALID_EDGE", file);
272           break;
273         }
274     }
275   fputs ("\n", file);
276 }
279 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
280    file. The input string MSG is printed out as a heading.  */
282 static void
283 dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg)
284 {
285   int i, j;
286   int fnum_vertices, fnum_edges;
288   fixup_vertex_p fvertex_list, pfvertex;
289   fixup_edge_p pfedge;
291   gcc_assert (fixup_graph);
292   fvertex_list = fixup_graph->vertex_list;
293   fnum_vertices = fixup_graph->num_vertices;
294   fnum_edges = fixup_graph->num_edges;
296   fprintf (file, "\nDump fixup graph for %s(): %s.\n",
297            current_function_name (), msg);
298   fprintf (file,
299            "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
300            fnum_vertices, fnum_edges, fixup_graph->new_exit_index);
302   for (i = 0; i < fnum_vertices; i++)
303     {
304       pfvertex = fvertex_list + i;
305       fprintf (file, "vertex_list[%d]: %d succ fixup edges.\n",
306                i, pfvertex->succ_edges.length ());
308       for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge);
309            j++)
310         {
311           /* Distinguish forward edges and backward edges in the residual flow
312              network.  */
313           if (pfedge->type)
314             fputs ("(f) ", file);
315           else if (pfedge->is_rflow_valid)
316             fputs ("(b) ", file);
317           dump_fixup_edge (file, fixup_graph, pfedge);
318         }
319     }
321   fputs ("\n", file);
322 }
325 /* Utility routines.  */
326 /* ln() implementation: approximate calculation. Returns ln of X.  */
328 static double
329 mcf_ln (double x)
330 {
331 #define E       2.71828
332   int l = 1;
333   double m = E;
335   gcc_assert (x >= 0);
337   while (m < x)
338     {
339       m *= E;
340       l++;
341     }
343   return l;
344 }
347 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
348    implementation) by John Carmack.  Returns sqrt of X.  */
350 static double
351 mcf_sqrt (double x)
352 {
353 #define MAGIC_CONST1    0x1fbcf800
354 #define MAGIC_CONST2    0x5f3759df
355   union {
356     int intPart;
357     float floatPart;
358   } convertor, convertor2;
360   gcc_assert (x >= 0);
362   convertor.floatPart = x;
363   convertor2.floatPart = x;
364   convertor.intPart = MAGIC_CONST1 + (convertor.intPart >> 1);
365   convertor2.intPart = MAGIC_CONST2 - (convertor2.intPart >> 1);
367   return 0.5f * (convertor.floatPart + (x * convertor2.floatPart));
368 }
371 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
372    (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
373    added set to COST.  */
375 static fixup_edge_p
376 add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost)
377 {
378   fixup_vertex_p curr_vertex = fixup_graph->vertex_list + src;
379   fixup_edge_p curr_edge = fixup_graph->edge_list + fixup_graph->num_edges;
380   curr_edge->src = src;
381   curr_edge->dest = dest;
382   curr_edge->cost = cost;
383   fixup_graph->num_edges++;
384   if (dump_file)
385     dump_fixup_edge (dump_file, fixup_graph, curr_edge);
386   curr_vertex->succ_edges.safe_push (curr_edge);
387   return curr_edge;
388 }
391 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
392    MAX_CAPACITY to the edge_list in the fixup graph.  */
394 static void
395 add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
396                 edge_type type, gcov_type weight, gcov_type cost,
397                 gcov_type max_capacity)
398 {
399   fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost);
400   curr_edge->type = type;
401   curr_edge->weight = weight;
402   curr_edge->max_capacity = max_capacity;
403 }
406 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
407    to the fixup graph.  */
409 static void
410 add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
411                  gcov_type rflow, gcov_type cost)
412 {
413   fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost);
414   curr_edge->rflow = rflow;
415   curr_edge->is_rflow_valid = true;
416   /* This edge is not a valid edge - merely used to hold residual flow.  */
417   curr_edge->type = INVALID_EDGE;
418 }
421 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
422    exist in the FIXUP_GRAPH.  */
424 static fixup_edge_p
425 find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest)
426 {
427   int j;
428   fixup_edge_p pfedge;
429   fixup_vertex_p pfvertex;
431   gcc_assert (src < fixup_graph->num_vertices);
433   pfvertex = fixup_graph->vertex_list + src;
435   for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge);
436        j++)
437     if (pfedge->dest == dest)
438       return pfedge;
440   return NULL;
441 }
444 /* Cleanup routine to free structures in FIXUP_GRAPH.  */
446 static void
447 delete_fixup_graph (fixup_graph_type *fixup_graph)
448 {
449   int i;
450   int fnum_vertices = fixup_graph->num_vertices;
451   fixup_vertex_p pfvertex = fixup_graph->vertex_list;
453   for (i = 0; i < fnum_vertices; i++, pfvertex++)
454     pfvertex->succ_edges.release ();
456   free (fixup_graph->vertex_list);
457   free (fixup_graph->edge_list);
458 }
461 /* Creates a fixup graph FIXUP_GRAPH from the function CFG.  */
463 static void
464 create_fixup_graph (fixup_graph_type *fixup_graph)
465 {
466   double sqrt_avg_vertex_weight = 0;
467   double total_vertex_weight = 0;
468   double k_pos = 0;
469   double k_neg = 0;
470   /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v).  */
471   gcov_type *diff_out_in = NULL;
472   gcov_type supply_value = 1, demand_value = 0;
473   gcov_type fcost = 0;
474   int new_entry_index = 0, new_exit_index = 0;
475   int i = 0, j = 0;
476   int new_index = 0;
477   basic_block bb;
478   edge e;
479   edge_iterator ei;
480   fixup_edge_p pfedge, r_pfedge;
481   fixup_edge_p fedge_list;
482   int fnum_edges;
484   /* Each basic_block will be split into 2 during vertex transformation.  */
485   int fnum_vertices_after_transform =  2 * n_basic_blocks_for_fn (cfun);
486   int fnum_edges_after_transform =
487     n_edges_for_fn (cfun) + n_basic_blocks_for_fn (cfun);
489   /* Count the new SOURCE and EXIT vertices to be added.  */
490   int fmax_num_vertices =
491     (fnum_vertices_after_transform + n_edges_for_fn (cfun)
492      + n_basic_blocks_for_fn (cfun) + 2);
494   /* In create_fixup_graph: Each basic block and edge can be split into 3
495      edges. Number of balance edges = n_basic_blocks. So after
496      create_fixup_graph:
497      max_edges = 4 * n_basic_blocks + 3 * n_edges
498      Accounting for residual flow edges
499      max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
500      = 8 * n_basic_blocks + 6 * n_edges
501      < 8 * n_basic_blocks + 8 * n_edges.  */
502   int fmax_num_edges = 8 * (n_basic_blocks_for_fn (cfun) +
503                             n_edges_for_fn (cfun));
505   /* Initial num of vertices in the fixup graph.  */
506   fixup_graph->num_vertices = n_basic_blocks_for_fn (cfun);
508   /* Fixup graph vertex list.  */
509   fixup_graph->vertex_list =
510     (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type));
512   /* Fixup graph edge list.  */
513   fixup_graph->edge_list =
514     (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type));
516   diff_out_in =
517     (gcov_type *) xcalloc (1 + fnum_vertices_after_transform,
518                            sizeof (gcov_type));
520   /* Compute constants b, k_pos, k_neg used in the cost function calculation.
521      b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b.  */
522   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
523     total_vertex_weight += bb->count;
525   sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight /
526                                      n_basic_blocks_for_fn (cfun));
528   k_pos = K_POS (sqrt_avg_vertex_weight);
529   k_neg = K_NEG (sqrt_avg_vertex_weight);
531   /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
532      connected by an edge e from v' to v''. w(e) = w(v).  */
534   if (dump_file)
535     fprintf (dump_file, "\nVertex transformation:\n");
537   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
538   {
539     /* v'->v'': index1->(index1+1).  */
540     i = 2 * bb->index;
541     fcost = (gcov_type) COST (k_pos, bb->count);
542     add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count,
543                     fcost, CAP_INFINITY);
544     fixup_graph->num_vertices++;
546     FOR_EACH_EDGE (e, ei, bb->succs)
547     {
548       /* Edges with ignore attribute set should be treated like they don't
549          exist.  */
550       if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
551         continue;
552       j = 2 * e->dest->index;
553       fcost = (gcov_type) COST (k_pos, e->count);
554       add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost,
555                       CAP_INFINITY);
556     }
557   }
559   /* After vertex transformation.  */
560   gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform);
561   /* Redirect edges are not added for edges with ignore attribute.  */
562   gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform);
564   fnum_edges_after_transform = fixup_graph->num_edges;
566   /* 2. Initialize D(v).  */
567   for (i = 0; i < fnum_edges_after_transform; i++)
568     {
569       pfedge = fixup_graph->edge_list + i;
570       diff_out_in[pfedge->src] += pfedge->weight;
571       diff_out_in[pfedge->dest] -= pfedge->weight;
572     }
574   /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3.  */
575   for (i = 0; i <= 3; i++)
576     diff_out_in[i] = 0;
578   /* 3. Add reverse edges: needed to decrease counts during smoothing.  */
579   if (dump_file)
580     fprintf (dump_file, "\nReverse edges:\n");
581   for (i = 0; i < fnum_edges_after_transform; i++)
582     {
583       pfedge = fixup_graph->edge_list + i;
584       if ((pfedge->src == 0) || (pfedge->src == 2))
585         continue;
586       r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
587       if (!r_pfedge && pfedge->weight)
588         {
589           /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
590              capacity is 0.  */
591           fcost = (gcov_type) COST (k_neg, pfedge->weight);
592           add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src,
593                           REVERSE_EDGE, 0, fcost, pfedge->weight);
594         }
595     }
597   /* 4. Create single source and sink. Connect new source vertex s' to function
598      entry block. Connect sink vertex t' to function exit.  */
599   if (dump_file)
600     fprintf (dump_file, "\ns'->S, T->t':\n");
602   new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices;
603   fixup_graph->num_vertices++;
604   /* Set supply_value to 1 to avoid zero count function ENTRY.  */
605   add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE,
606                   1 /* supply_value */, 0, 1 /* supply_value */);
608   /* Create new exit with EXIT_BLOCK as single pred.  */
609   new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices;
610   fixup_graph->num_vertices++;
611   add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index,
612                   SINK_CONNECT_EDGE,
613                   0 /* demand_value */, 0, 0 /* demand_value */);
615   /* Connect vertices with unbalanced D(v) to source/sink.  */
616   if (dump_file)
617     fprintf (dump_file, "\nD(v) balance:\n");
618   /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
619      diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2.  */
620   for (i = 4; i < new_entry_index; i += 2)
621     {
622       if (diff_out_in[i] > 0)
623         {
624           add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0,
625                           diff_out_in[i]);
626           demand_value += diff_out_in[i];
627         }
628       else if (diff_out_in[i] < 0)
629         {
630           add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0,
631                           -diff_out_in[i]);
632           supply_value -= diff_out_in[i];
633         }
634     }
636   /* Set supply = demand.  */
637   if (dump_file)
638     {
639       fprintf (dump_file, "\nAdjust supply and demand:\n");
640       fprintf (dump_file, "supply_value=%"PRId64 "\n",
641                supply_value);
642       fprintf (dump_file, "demand_value=%"PRId64 "\n",
643                demand_value);
644     }
646   if (demand_value > supply_value)
647     {
648       pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK);
649       pfedge->max_capacity += (demand_value - supply_value);
650     }
651   else
652     {
653       pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index);
654       pfedge->max_capacity += (supply_value - demand_value);
655     }
657   /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
658      created by the vertex transformation step from self-edges in the original
659      CFG and by the reverse edges added earlier.  */
660   if (dump_file)
661     fprintf (dump_file, "\nNormalize edges:\n");
663   fnum_edges = fixup_graph->num_edges;
664   fedge_list = fixup_graph->edge_list;
666   for (i = 0; i < fnum_edges; i++)
667     {
668       pfedge = fedge_list + i;
669       r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
670       if (((pfedge->type == VERTEX_SPLIT_EDGE)
671            || (pfedge->type == REDIRECT_EDGE)) && r_pfedge)
672         {
673           new_index = fixup_graph->num_vertices;
674           fixup_graph->num_vertices++;
676           if (dump_file)
677             {
678               fprintf (dump_file, "\nAnti-parallel edge:\n");
679               dump_fixup_edge (dump_file, fixup_graph, pfedge);
680               dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
681               fprintf (dump_file, "New vertex is %d.\n", new_index);
682               fprintf (dump_file, "------------------\n");
683             }
685           pfedge->cost /= 2;
686           pfedge->norm_vertex_index = new_index;
687           if (dump_file)
688             {
689               fprintf (dump_file, "After normalization:\n");
690               dump_fixup_edge (dump_file, fixup_graph, pfedge);
691             }
693           /* Add a new fixup edge: new_index->src.  */
694           add_fixup_edge (fixup_graph, new_index, pfedge->src,
695                           REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost,
696                           r_pfedge->max_capacity);
697           gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices);
699           /* Edge: r_pfedge->src -> r_pfedge->dest
700              ==> r_pfedge->src -> new_index.  */
701           r_pfedge->dest = new_index;
702           r_pfedge->type = REVERSE_NORMALIZED_EDGE;
703           r_pfedge->cost = pfedge->cost;
704           r_pfedge->max_capacity = pfedge->max_capacity;
705           if (dump_file)
706             dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
707         }
708     }
710   if (dump_file)
711     dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()");
713   /* Cleanup.  */
714   free (diff_out_in);
715 }
718 /* Allocates space for the structures in AUGMENTING_PATH.  The space needed is
719    proportional to the number of nodes in the graph, which is given by
720    GRAPH_SIZE.  */
722 static void
723 init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size)
724 {
725   augmenting_path->queue_list.queue = (int *)
726     xcalloc (graph_size + 2, sizeof (int));
727   augmenting_path->queue_list.size = graph_size + 2;
728   augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int));
729   augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int));
730 }
732 /* Free the structures in AUGMENTING_PATH.  */
733 static void
734 free_augmenting_path (augmenting_path_type *augmenting_path)
735 {
736   free (augmenting_path->queue_list.queue);
737   free (augmenting_path->bb_pred);
738   free (augmenting_path->is_visited);
739 }
742 /* Queue routines. Assumes queue will never overflow.  */
744 static void
745 init_queue (queue_type *queue_list)
746 {
747   gcc_assert (queue_list);
748   queue_list->head = 0;
749   queue_list->tail = 0;
750 }
752 /* Return true if QUEUE_LIST is empty.  */
753 static bool
754 is_empty (queue_type *queue_list)
755 {
756   return (queue_list->head == queue_list->tail);
757 }
759 /* Insert element X into QUEUE_LIST.  */
760 static void
761 enqueue (queue_type *queue_list, int x)
762 {
763   gcc_assert (queue_list->tail < queue_list->size);
764   queue_list->queue[queue_list->tail] = x;
765   (queue_list->tail)++;
766 }
768 /* Return the first element in QUEUE_LIST.  */
769 static int
770 dequeue (queue_type *queue_list)
771 {
772   int x;
773   gcc_assert (queue_list->head >= 0);
774   x = queue_list->queue[queue_list->head];
776   return x;
777 }
780 /* Finds a negative cycle in the residual network using
781    the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
782    minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
783    considered.
785 Parameters:
786    FIXUP_GRAPH - Residual graph  (input/output)
787    The following are allocated/freed by the caller:
788    PI - Vector to hold predecessors in path  (pi = pred index)
789    D - D[I] holds minimum cost of path from i to sink
790    CYCLE - Vector to hold the minimum cost cycle
792 Return:
793    true if a negative cycle was found, false otherwise.  */
795 static bool
796 cancel_negative_cycle (fixup_graph_type *fixup_graph,
797                        int *pi, gcov_type *d, int *cycle)
798 {
799   int i, j, k;
800   int fnum_vertices, fnum_edges;
801   fixup_edge_p fedge_list, pfedge, r_pfedge;
802   bool found_cycle = false;
803   int cycle_start = 0, cycle_end = 0;
804   gcov_type sum_cost = 0, cycle_flow = 0;
805   int new_entry_index;
806   bool propagated = false;
808   gcc_assert (fixup_graph);
809   fnum_vertices = fixup_graph->num_vertices;
810   fnum_edges = fixup_graph->num_edges;
811   fedge_list = fixup_graph->edge_list;
812   new_entry_index = fixup_graph->new_entry_index;
814   /* Initialize.  */
815   /* Skip ENTRY.  */
816   for (i = 1; i < fnum_vertices; i++)
817     {
818       d[i] = CAP_INFINITY;
819       pi[i] = -1;
820       cycle[i] = -1;
821     }
822   d[ENTRY_BLOCK] = 0;
824   /* Relax.  */
825   for (k = 1; k < fnum_vertices; k++)
826   {
827     propagated = false;
828     for (i = 0; i < fnum_edges; i++)
829       {
830         pfedge = fedge_list + i;
831         if (pfedge->src == new_entry_index)
832           continue;
833         if (pfedge->is_rflow_valid && pfedge->rflow
834             && d[pfedge->src] != CAP_INFINITY
835             && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
836           {
837             d[pfedge->dest] = d[pfedge->src] + pfedge->cost;
838             pi[pfedge->dest] = pfedge->src;
839             propagated = true;
840           }
841       }
842     if (!propagated)
843       break;
844   }
846   if (!propagated)
847   /* No negative cycles exist.  */
848     return 0;
850   /* Detect.  */
851   for (i = 0; i < fnum_edges; i++)
852     {
853       pfedge = fedge_list + i;
854       if (pfedge->src == new_entry_index)
855         continue;
856       if (pfedge->is_rflow_valid && pfedge->rflow
857           && d[pfedge->src] != CAP_INFINITY
858           && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
859         {
860           found_cycle = true;
861           break;
862         }
863     }
865   if (!found_cycle)
866     return 0;
868   /* Augment the cycle with the cycle's minimum residual capacity.  */
869   found_cycle = false;
870   cycle = pfedge->dest;
871   j = pfedge->dest;
873   for (i = 1; i < fnum_vertices; i++)
874     {
875       j = pi[j];
876       cycle[i] = j;
877       for (k = 0; k < i; k++)
878         {
879           if (cycle[k] == j)
880             {
881               /* cycle[k] -> ... -> cycle[i].  */
882               cycle_start = k;
883               cycle_end = i;
884               found_cycle = true;
885               break;
886             }
887         }
888       if (found_cycle)
889         break;
890     }
892   gcc_assert (cycle[cycle_start] == cycle[cycle_end]);
893   if (dump_file)
894     fprintf (dump_file, "\nNegative cycle length is %d:\n",
895              cycle_end - cycle_start);
897   sum_cost = 0;
898   cycle_flow = CAP_INFINITY;
899   for (k = cycle_start; k < cycle_end; k++)
900     {
901       pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
902       cycle_flow = MIN (cycle_flow, pfedge->rflow);
903       sum_cost += pfedge->cost;
904       if (dump_file)
905         fprintf (dump_file, "%d ", cycle[k]);
906     }
908   if (dump_file)
909     {
910       fprintf (dump_file, "%d", cycle[k]);
911       fprintf (dump_file,
912                ": (%"PRId64 ", %"PRId64
913                ")\n", sum_cost, cycle_flow);
914       fprintf (dump_file,
915                "Augment cycle with %"PRId64 "\n",
916                cycle_flow);
917     }
919   for (k = cycle_start; k < cycle_end; k++)
920     {
921       pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
922       r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]);
923       pfedge->rflow -= cycle_flow;
924       if (pfedge->type)
925         pfedge->flow += cycle_flow;
926       r_pfedge->rflow += cycle_flow;
927       if (r_pfedge->type)
928         r_pfedge->flow -= cycle_flow;
929     }
931   return true;
932 }
935 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
936    the edges. ENTRY and EXIT vertices should not be considered.  */
938 static void
939 compute_residual_flow (fixup_graph_type *fixup_graph)
940 {
941   int i;
942   int fnum_edges;
943   fixup_edge_p fedge_list, pfedge;
945   gcc_assert (fixup_graph);
947   if (dump_file)
948     fputs ("\ncompute_residual_flow():\n", dump_file);
950   fnum_edges = fixup_graph->num_edges;
951   fedge_list = fixup_graph->edge_list;
953   for (i = 0; i < fnum_edges; i++)
954     {
955       pfedge = fedge_list + i;
956       pfedge->rflow = pfedge->max_capacity - pfedge->flow;
957       pfedge->is_rflow_valid = true;
958       add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow,
959                        -pfedge->cost);
960     }
961 }
964 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
965    SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
966    this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
967    to reflect the path found.
968    Returns: 0 if no augmenting path is found, 1 otherwise.  */
970 static int
971 find_augmenting_path (fixup_graph_type *fixup_graph,
972                       augmenting_path_type *augmenting_path, int source,
973                       int sink)
974 {
975   int u = 0;
976   int i;
977   fixup_vertex_p fvertex_list, pfvertex;
978   fixup_edge_p pfedge;
979   int *bb_pred, *is_visited;
980   queue_type *queue_list;
982   gcc_assert (augmenting_path);
983   bb_pred = augmenting_path->bb_pred;
984   gcc_assert (bb_pred);
985   is_visited = augmenting_path->is_visited;
986   gcc_assert (is_visited);
987   queue_list = &(augmenting_path->queue_list);
989   gcc_assert (fixup_graph);
991   fvertex_list = fixup_graph->vertex_list;
993   for (u = 0; u < fixup_graph->num_vertices; u++)
994     is_visited[u] = 0;
996   init_queue (queue_list);
997   enqueue (queue_list, source);
998   bb_pred[source] = -1;
1000   while (!is_empty (queue_list))
1001     {
1002       u = dequeue (queue_list);
1003       is_visited[u] = 1;
1004       pfvertex = fvertex_list + u;
1005       for (i = 0; pfvertex->succ_edges.iterate (i, &pfedge);
1006            i++)
1007         {
1008           int dest = pfedge->dest;
1009           if ((pfedge->rflow > 0) && (is_visited[dest] == 0))
1010             {
1011               enqueue (queue_list, dest);
1012               bb_pred[dest] = u;
1013               is_visited[dest] = 1;
1014               if (dest == sink)
1015                 return 1;
1016             }
1017         }
1018     }
1020   return 0;
1021 }
1024 /* Routine to find the maximal flow:
1025    Algorithm:
1026    1. Initialize flow to 0
1027    2. Find an augmenting path form source to sink.
1028    3. Send flow equal to the path's residual capacity along the edges of this path.
1029    4. Repeat steps 2 and 3 until no new augmenting path is found.
1031 Parameters:
1032 SOURCE: index of source vertex (input)
1033 SINK: index of sink vertex    (input)
1034 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1035              set to have a valid maximal flow by this routine. (input)
1036 Return: Maximum flow possible.  */
1038 static gcov_type
1039 find_max_flow (fixup_graph_type *fixup_graph, int source, int sink)
1040 {
1041   int fnum_edges;
1042   augmenting_path_type augmenting_path;
1043   int *bb_pred;
1044   gcov_type max_flow = 0;
1045   int i, u;
1046   fixup_edge_p fedge_list, pfedge, r_pfedge;
1048   gcc_assert (fixup_graph);
1050   fnum_edges = fixup_graph->num_edges;
1051   fedge_list = fixup_graph->edge_list;
1053   /* Initialize flow to 0.  */
1054   for (i = 0; i < fnum_edges; i++)
1055     {
1056       pfedge = fedge_list + i;
1057       pfedge->flow = 0;
1058     }
1060   compute_residual_flow (fixup_graph);
1062   init_augmenting_path (&augmenting_path, fixup_graph->num_vertices);
1064   bb_pred = augmenting_path.bb_pred;
1065   while (find_augmenting_path (fixup_graph, &augmenting_path, source, sink))
1066     {
1067       /* Determine the amount by which we can increment the flow.  */
1068       gcov_type increment = CAP_INFINITY;
1069       for (u = sink; u != source; u = bb_pred[u])
1070         {
1071           pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1072           increment = MIN (increment, pfedge->rflow);
1073         }
1074       max_flow += increment;
1076       /* Now increment the flow. EXIT vertex index is 1.  */
1077       for (u = sink; u != source; u = bb_pred[u])
1078         {
1079           pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1080           r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]);
1081           if (pfedge->type)
1082             {
1083               /* forward edge.  */
1084               pfedge->flow += increment;
1085               pfedge->rflow -= increment;
1086               r_pfedge->rflow += increment;
1087             }
1088           else
1089             {
1090               /* backward edge.  */
1091               gcc_assert (r_pfedge->type);
1092               r_pfedge->rflow += increment;
1093               r_pfedge->flow -= increment;
1094               pfedge->rflow -= increment;
1095             }
1096         }
1098       if (dump_file)
1099         {
1100           fprintf (dump_file, "\nDump augmenting path:\n");
1101           for (u = sink; u != source; u = bb_pred[u])
1102             {
1103               print_basic_block (dump_file, fixup_graph, u);
1104               fprintf (dump_file, "<-");
1105             }
1106           fprintf (dump_file,
1107                    "ENTRY  (path_capacity=%"PRId64 ")\n",
1108                    increment);
1109           fprintf (dump_file,
1110                    "Network flow is %"PRId64 ".\n",
1111                    max_flow);
1112         }
1113     }
1115   free_augmenting_path (&augmenting_path);
1116   if (dump_file)
1117     dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()");
1118   return max_flow;
1119 }
1122 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1123    after applying the find_minimum_cost_flow() routine.  */
1125 static void
1126 adjust_cfg_counts (fixup_graph_type *fixup_graph)
1127 {
1128   basic_block bb;
1129   edge e;
1130   edge_iterator ei;
1131   int i, j;
1132   fixup_edge_p pfedge, pfedge_n;
1134   gcc_assert (fixup_graph);
1136   if (dump_file)
1137     fprintf (dump_file, "\nadjust_cfg_counts():\n");
1139   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
1140                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1141     {
1142       i = 2 * bb->index;
1144       /* Fixup BB.  */
1145       if (dump_file)
1146         fprintf (dump_file,
1147                  "BB%d: %"PRId64 "", bb->index, bb->count);
1149       pfedge = find_fixup_edge (fixup_graph, i, i + 1);
1150       if (pfedge->flow)
1151         {
1152           bb->count += pfedge->flow;
1153           if (dump_file)
1154             {
1155               fprintf (dump_file, " + %"PRId64 "(",
1156                        pfedge->flow);
1157               print_edge (dump_file, fixup_graph, i, i + 1);
1158               fprintf (dump_file, ")");
1159             }
1160         }
1162       pfedge_n =
1163         find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1164       /* Deduct flow from normalized reverse edge.  */
1165       if (pfedge->norm_vertex_index && pfedge_n->flow)
1166         {
1167           bb->count -= pfedge_n->flow;
1168           if (dump_file)
1169             {
1170               fprintf (dump_file, " - %"PRId64 "(",
1171                        pfedge_n->flow);
1172               print_edge (dump_file, fixup_graph, i + 1,
1173                           pfedge->norm_vertex_index);
1174               fprintf (dump_file, ")");
1175             }
1176         }
1177       if (dump_file)
1178         fprintf (dump_file, " = %"PRId64 "\n", bb->count);
1180       /* Fixup edge.  */
1181       FOR_EACH_EDGE (e, ei, bb->succs)
1182         {
1183           /* Treat edges with ignore attribute set as if they don't exist.  */
1184           if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1185             continue;
1187           j = 2 * e->dest->index;
1188           if (dump_file)
1189             fprintf (dump_file, "%d->%d: %"PRId64 "",
1190                      bb->index, e->dest->index, e->count);
1192           pfedge = find_fixup_edge (fixup_graph, i + 1, j);
1194           if (bb->index != e->dest->index)
1195             {
1196               /* Non-self edge.  */
1197               if (pfedge->flow)
1198                 {
1199                   e->count += pfedge->flow;
1200                   if (dump_file)
1201                     {
1202                       fprintf (dump_file, " + %"PRId64 "(",
1203                                pfedge->flow);
1204                       print_edge (dump_file, fixup_graph, i + 1, j);
1205                       fprintf (dump_file, ")");
1206                     }
1207                 }
1209               pfedge_n =
1210                 find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index);
1211               /* Deduct flow from normalized reverse edge.  */
1212               if (pfedge->norm_vertex_index && pfedge_n->flow)
1213                 {
1214                   e->count -= pfedge_n->flow;
1215                   if (dump_file)
1216                     {
1217                       fprintf (dump_file, " - %"PRId64 "(",
1218                                pfedge_n->flow);
1219                       print_edge (dump_file, fixup_graph, j,
1220                                   pfedge->norm_vertex_index);
1221                       fprintf (dump_file, ")");
1222                     }
1223                 }
1224             }
1225           else
1226             {
1227               /* Handle self edges. Self edge is split with a normalization
1228                  vertex. Here i=j.  */
1229               pfedge = find_fixup_edge (fixup_graph, j, i + 1);
1230               pfedge_n =
1231                 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1232               e->count += pfedge_n->flow;
1233               bb->count += pfedge_n->flow;
1234               if (dump_file)
1235                 {
1236                   fprintf (dump_file, "(self edge)");
1237                   fprintf (dump_file, " + %"PRId64 "(",
1238                            pfedge_n->flow);
1239                   print_edge (dump_file, fixup_graph, i + 1,
1240                               pfedge->norm_vertex_index);
1241                   fprintf (dump_file, ")");
1242                 }
1243             }
1245           if (bb->count)
1246             e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1247           if (dump_file)
1248             fprintf (dump_file, " = %"PRId64 "\t(%.1f%%)\n",
1249                      e->count, e->probability * 100.0 / REG_BR_PROB_BASE);
1250         }
1251     }
1253   ENTRY_BLOCK_PTR_FOR_FN (cfun)->count =
1254                      sum_edge_counts (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1255   EXIT_BLOCK_PTR_FOR_FN (cfun)->count =
1256                      sum_edge_counts (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
1258   /* Compute edge probabilities.  */
1259   FOR_ALL_BB_FN (bb, cfun)
1260     {
1261       if (bb->count)
1262         {
1263           FOR_EACH_EDGE (e, ei, bb->succs)
1264             e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1265         }
1266       else
1267         {
1268           int total = 0;
1269           FOR_EACH_EDGE (e, ei, bb->succs)
1270             if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1271               total++;
1272           if (total)
1273             {
1274               FOR_EACH_EDGE (e, ei, bb->succs)
1275                 {
1276                   if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1277                     e->probability = REG_BR_PROB_BASE / total;
1278                   else
1279                     e->probability = 0;
1280                 }
1281             }
1282           else
1283             {
1284               total += EDGE_COUNT (bb->succs);
1285               FOR_EACH_EDGE (e, ei, bb->succs)
1286                   e->probability = REG_BR_PROB_BASE / total;
1287             }
1288         }
1289     }
1291   if (dump_file)
1292     {
1293       fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n",
1294                current_function_name ());
1295       FOR_EACH_BB_FN (bb, cfun)
1296         {
1297           if ((bb->count != sum_edge_counts (bb->preds))
1298                || (bb->count != sum_edge_counts (bb->succs)))
1299             {
1300               fprintf (dump_file,
1301                        "BB%d(%"PRId64 ")  **INVALID**: ",
1302                        bb->index, bb->count);
1303               fprintf (stderr,
1304                        "******** BB%d(%"PRId64
1305                        ")  **INVALID**: \n", bb->index, bb->count);
1306               fprintf (dump_file, "in_edges=%"PRId64 " ",
1307                        sum_edge_counts (bb->preds));
1308               fprintf (dump_file, "out_edges=%"PRId64 "\n",
1309                        sum_edge_counts (bb->succs));
1310             }
1311          }
1312     }
1313 }
1316 /* Implements the negative cycle canceling algorithm to compute a minimum cost
1317    flow.
1318 Algorithm:
1319 1. Find maximal flow.
1320 2. Form residual network
1321 3. Repeat:
1322   While G contains a negative cost cycle C, reverse the flow on the found cycle
1323   by the minimum residual capacity in that cycle.
1324 4. Form the minimal cost flow
1325   f(u,v) = rf(v, u)
1326 Input:
1327   FIXUP_GRAPH - Initial fixup graph.
1328   The flow field is modified to represent the minimum cost flow.  */
1330 static void
1331 find_minimum_cost_flow (fixup_graph_type *fixup_graph)
1332 {
1333   /* Holds the index of predecessor in path.  */
1334   int *pred;
1335   /* Used to hold the minimum cost cycle.  */
1336   int *cycle;
1337   /* Used to record the number of iterations of cancel_negative_cycle.  */
1338   int iteration;
1339   /* Vector d[i] holds the minimum cost of path from i to sink.  */
1340   gcov_type *d;
1341   int fnum_vertices;
1342   int new_exit_index;
1343   int new_entry_index;
1345   gcc_assert (fixup_graph);
1346   fnum_vertices = fixup_graph->num_vertices;
1347   new_exit_index = fixup_graph->new_exit_index;
1348   new_entry_index = fixup_graph->new_entry_index;
1350   find_max_flow (fixup_graph, new_entry_index, new_exit_index);
1352   /* Initialize the structures for find_negative_cycle().  */
1353   pred = (int *) xcalloc (fnum_vertices, sizeof (int));
1354   d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type));
1355   cycle = (int *) xcalloc (fnum_vertices, sizeof (int));
1357   /* Repeatedly find and cancel negative cost cycles, until
1358      no more negative cycles exist. This also updates the flow field
1359      to represent the minimum cost flow so far.  */
1360   iteration = 0;
1361   while (cancel_negative_cycle (fixup_graph, pred, d, cycle))
1362     {
1363       iteration++;
1364       if (iteration > MAX_ITER (fixup_graph->num_vertices,
1365                                 fixup_graph->num_edges))
1366         break;
1367     }
1369   if (dump_file)
1370     dump_fixup_graph (dump_file, fixup_graph,
1371                       "After find_minimum_cost_flow()");
1373   /* Cleanup structures.  */
1374   free (pred);
1375   free (d);
1376   free (cycle);
1377 }
1380 /* Compute the sum of the edge counts in TO_EDGES.  */
1382 gcov_type
1383 sum_edge_counts (vec<edge, va_gc> *to_edges)
1384 {
1385   gcov_type sum = 0;
1386   edge e;
1387   edge_iterator ei;
1389   FOR_EACH_EDGE (e, ei, to_edges)
1390     {
1391       if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1392         continue;
1393       sum += e->count;
1394     }
1395   return sum;
1396 }
1399 /* Main routine. Smoothes the initial assigned basic block and edge counts using
1400    a minimum cost flow algorithm, to ensure that the flow consistency rule is
1401    obeyed: sum of outgoing edges = sum of incoming edges for each basic
1402    block.  */
1404 void
1405 mcf_smooth_cfg (void)
1406 {
1407   fixup_graph_type fixup_graph;
1408   memset (&fixup_graph, 0, sizeof (fixup_graph));
1409   create_fixup_graph (&fixup_graph);
1410   find_minimum_cost_flow (&fixup_graph);