Replace enum gfc_try with bool type.
[official-gcc.git] / gcc / mcf.c
blob7a716f58177d80f2333acedb7f06489549ab42a3
1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth
2 basic block and edge frequency counts.
3 Copyright (C) 2008-2013 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
20 <http://www.gnu.org/licenses/>. */
22 /* References:
23 [1] "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 [2] "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 "basic-block.h"
49 #include "gcov-io.h"
50 #include "profile.h"
51 #include "dumpfile.h"
53 /* CAP_INFINITY: Constant to represent infinite capacity. */
54 #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT)
56 /* COST FUNCTION. */
57 #define K_POS(b) ((b))
58 #define K_NEG(b) (50 * (b))
59 #define COST(k, w) ((k) / mcf_ln ((w) + 2))
60 /* Limit the number of iterations for cancel_negative_cycles() to ensure
61 reasonable compile time. */
62 #define MAX_ITER(n, e) 10 + (1000000 / ((n) * (e)))
63 typedef enum
65 INVALID_EDGE,
66 VERTEX_SPLIT_EDGE, /* Edge to represent vertex with w(e) = w(v). */
67 REDIRECT_EDGE, /* Edge after vertex transformation. */
68 REVERSE_EDGE,
69 SOURCE_CONNECT_EDGE, /* Single edge connecting to single source. */
70 SINK_CONNECT_EDGE, /* Single edge connecting to single sink. */
71 BALANCE_EDGE, /* Edge connecting with source/sink: cp(e) = 0. */
72 REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge. */
73 REVERSE_NORMALIZED_EDGE /* Normalized edge for a reverse edge. */
74 } edge_type;
76 /* Structure to represent an edge in the fixup graph. */
77 typedef struct fixup_edge_d
79 int src;
80 int dest;
81 /* Flag denoting type of edge and attributes for the flow field. */
82 edge_type type;
83 bool is_rflow_valid;
84 /* Index to the normalization vertex added for this edge. */
85 int norm_vertex_index;
86 /* Flow for this edge. */
87 gcov_type flow;
88 /* Residual flow for this edge - used during negative cycle canceling. */
89 gcov_type rflow;
90 gcov_type weight;
91 gcov_type cost;
92 gcov_type max_capacity;
93 } fixup_edge_type;
95 typedef fixup_edge_type *fixup_edge_p;
98 /* Structure to represent a vertex in the fixup graph. */
99 typedef struct fixup_vertex_d
101 vec<fixup_edge_p> succ_edges;
102 } fixup_vertex_type;
104 typedef fixup_vertex_type *fixup_vertex_p;
106 /* Fixup graph used in the MCF algorithm. */
107 typedef struct fixup_graph_d
109 /* Current number of vertices for the graph. */
110 int num_vertices;
111 /* Current number of edges for the graph. */
112 int num_edges;
113 /* Index of new entry vertex. */
114 int new_entry_index;
115 /* Index of new exit vertex. */
116 int new_exit_index;
117 /* Fixup vertex list. Adjacency list for fixup graph. */
118 fixup_vertex_p vertex_list;
119 /* Fixup edge list. */
120 fixup_edge_p edge_list;
121 } fixup_graph_type;
123 typedef struct queue_d
125 int *queue;
126 int head;
127 int tail;
128 int size;
129 } queue_type;
131 /* Structure used in the maximal flow routines to find augmenting path. */
132 typedef struct augmenting_path_d
134 /* Queue used to hold vertex indices. */
135 queue_type queue_list;
136 /* Vector to hold chain of pred vertex indices in augmenting path. */
137 int *bb_pred;
138 /* Vector that indicates if basic block i has been visited. */
139 int *is_visited;
140 } augmenting_path_type;
143 /* Function definitions. */
145 /* Dump routines to aid debugging. */
147 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */
149 static void
150 print_basic_block (FILE *file, fixup_graph_type *fixup_graph, int n)
152 if (n == ENTRY_BLOCK)
153 fputs ("ENTRY", file);
154 else if (n == ENTRY_BLOCK + 1)
155 fputs ("ENTRY''", file);
156 else if (n == 2 * EXIT_BLOCK)
157 fputs ("EXIT", file);
158 else if (n == 2 * EXIT_BLOCK + 1)
159 fputs ("EXIT''", file);
160 else if (n == fixup_graph->new_exit_index)
161 fputs ("NEW_EXIT", file);
162 else if (n == fixup_graph->new_entry_index)
163 fputs ("NEW_ENTRY", file);
164 else
166 fprintf (file, "%d", n / 2);
167 if (n % 2)
168 fputs ("''", file);
169 else
170 fputs ("'", file);
175 /* Print edge S->D for given fixup_graph with n' and n'' format.
176 PARAMETERS:
177 S is the index of the source vertex of the edge (input) and
178 D is the index of the destination vertex of the edge (input) for the given
179 fixup_graph (input). */
181 static void
182 print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d)
184 print_basic_block (file, fixup_graph, s);
185 fputs ("->", file);
186 print_basic_block (file, fixup_graph, d);
190 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
191 file. */
192 static void
193 dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge)
195 if (!fedge)
197 fputs ("NULL fixup graph edge.\n", file);
198 return;
201 print_edge (file, fixup_graph, fedge->src, fedge->dest);
202 fputs (": ", file);
204 if (fedge->type)
206 fprintf (file, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC "/",
207 fedge->flow);
208 if (fedge->max_capacity == CAP_INFINITY)
209 fputs ("+oo,", file);
210 else
211 fprintf (file, "" HOST_WIDEST_INT_PRINT_DEC ",", fedge->max_capacity);
214 if (fedge->is_rflow_valid)
216 if (fedge->rflow == CAP_INFINITY)
217 fputs (" rflow=+oo.", file);
218 else
219 fprintf (file, " rflow=" HOST_WIDEST_INT_PRINT_DEC ",", fedge->rflow);
222 fprintf (file, " cost=" HOST_WIDEST_INT_PRINT_DEC ".", fedge->cost);
224 fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest);
226 if (fedge->type)
228 switch (fedge->type)
230 case VERTEX_SPLIT_EDGE:
231 fputs (" @VERTEX_SPLIT_EDGE", file);
232 break;
234 case REDIRECT_EDGE:
235 fputs (" @REDIRECT_EDGE", file);
236 break;
238 case SOURCE_CONNECT_EDGE:
239 fputs (" @SOURCE_CONNECT_EDGE", file);
240 break;
242 case SINK_CONNECT_EDGE:
243 fputs (" @SINK_CONNECT_EDGE", file);
244 break;
246 case REVERSE_EDGE:
247 fputs (" @REVERSE_EDGE", file);
248 break;
250 case BALANCE_EDGE:
251 fputs (" @BALANCE_EDGE", file);
252 break;
254 case REDIRECT_NORMALIZED_EDGE:
255 case REVERSE_NORMALIZED_EDGE:
256 fputs (" @NORMALIZED_EDGE", file);
257 break;
259 default:
260 fputs (" @INVALID_EDGE", file);
261 break;
264 fputs ("\n", file);
268 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
269 file. The input string MSG is printed out as a heading. */
271 static void
272 dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg)
274 int i, j;
275 int fnum_vertices, fnum_edges;
277 fixup_vertex_p fvertex_list, pfvertex;
278 fixup_edge_p pfedge;
280 gcc_assert (fixup_graph);
281 fvertex_list = fixup_graph->vertex_list;
282 fnum_vertices = fixup_graph->num_vertices;
283 fnum_edges = fixup_graph->num_edges;
285 fprintf (file, "\nDump fixup graph for %s(): %s.\n",
286 current_function_name (), msg);
287 fprintf (file,
288 "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
289 fnum_vertices, fnum_edges, fixup_graph->new_exit_index);
291 for (i = 0; i < fnum_vertices; i++)
293 pfvertex = fvertex_list + i;
294 fprintf (file, "vertex_list[%d]: %d succ fixup edges.\n",
295 i, pfvertex->succ_edges.length ());
297 for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge);
298 j++)
300 /* Distinguish forward edges and backward edges in the residual flow
301 network. */
302 if (pfedge->type)
303 fputs ("(f) ", file);
304 else if (pfedge->is_rflow_valid)
305 fputs ("(b) ", file);
306 dump_fixup_edge (file, fixup_graph, pfedge);
310 fputs ("\n", file);
314 /* Utility routines. */
315 /* ln() implementation: approximate calculation. Returns ln of X. */
317 static double
318 mcf_ln (double x)
320 #define E 2.71828
321 int l = 1;
322 double m = E;
324 gcc_assert (x >= 0);
326 while (m < x)
328 m *= E;
329 l++;
332 return l;
336 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
337 implementation) by John Carmack. Returns sqrt of X. */
339 static double
340 mcf_sqrt (double x)
342 #define MAGIC_CONST1 0x1fbcf800
343 #define MAGIC_CONST2 0x5f3759df
344 union {
345 int intPart;
346 float floatPart;
347 } convertor, convertor2;
349 gcc_assert (x >= 0);
351 convertor.floatPart = x;
352 convertor2.floatPart = x;
353 convertor.intPart = MAGIC_CONST1 + (convertor.intPart >> 1);
354 convertor2.intPart = MAGIC_CONST2 - (convertor2.intPart >> 1);
356 return 0.5f * (convertor.floatPart + (x * convertor2.floatPart));
360 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
361 (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
362 added set to COST. */
364 static fixup_edge_p
365 add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost)
367 fixup_vertex_p curr_vertex = fixup_graph->vertex_list + src;
368 fixup_edge_p curr_edge = fixup_graph->edge_list + fixup_graph->num_edges;
369 curr_edge->src = src;
370 curr_edge->dest = dest;
371 curr_edge->cost = cost;
372 fixup_graph->num_edges++;
373 if (dump_file)
374 dump_fixup_edge (dump_file, fixup_graph, curr_edge);
375 curr_vertex->succ_edges.safe_push (curr_edge);
376 return curr_edge;
380 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
381 MAX_CAPACITY to the edge_list in the fixup graph. */
383 static void
384 add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
385 edge_type type, gcov_type weight, gcov_type cost,
386 gcov_type max_capacity)
388 fixup_edge_p curr_edge = add_edge(fixup_graph, src, dest, cost);
389 curr_edge->type = type;
390 curr_edge->weight = weight;
391 curr_edge->max_capacity = max_capacity;
395 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
396 to the fixup graph. */
398 static void
399 add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
400 gcov_type rflow, gcov_type cost)
402 fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost);
403 curr_edge->rflow = rflow;
404 curr_edge->is_rflow_valid = true;
405 /* This edge is not a valid edge - merely used to hold residual flow. */
406 curr_edge->type = INVALID_EDGE;
410 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
411 exist in the FIXUP_GRAPH. */
413 static fixup_edge_p
414 find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest)
416 int j;
417 fixup_edge_p pfedge;
418 fixup_vertex_p pfvertex;
420 gcc_assert (src < fixup_graph->num_vertices);
422 pfvertex = fixup_graph->vertex_list + src;
424 for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge);
425 j++)
426 if (pfedge->dest == dest)
427 return pfedge;
429 return NULL;
433 /* Cleanup routine to free structures in FIXUP_GRAPH. */
435 static void
436 delete_fixup_graph (fixup_graph_type *fixup_graph)
438 int i;
439 int fnum_vertices = fixup_graph->num_vertices;
440 fixup_vertex_p pfvertex = fixup_graph->vertex_list;
442 for (i = 0; i < fnum_vertices; i++, pfvertex++)
443 pfvertex->succ_edges.release ();
445 free (fixup_graph->vertex_list);
446 free (fixup_graph->edge_list);
450 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
452 static void
453 create_fixup_graph (fixup_graph_type *fixup_graph)
455 double sqrt_avg_vertex_weight = 0;
456 double total_vertex_weight = 0;
457 double k_pos = 0;
458 double k_neg = 0;
459 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */
460 gcov_type *diff_out_in = NULL;
461 gcov_type supply_value = 1, demand_value = 0;
462 gcov_type fcost = 0;
463 int new_entry_index = 0, new_exit_index = 0;
464 int i = 0, j = 0;
465 int new_index = 0;
466 basic_block bb;
467 edge e;
468 edge_iterator ei;
469 fixup_edge_p pfedge, r_pfedge;
470 fixup_edge_p fedge_list;
471 int fnum_edges;
473 /* Each basic_block will be split into 2 during vertex transformation. */
474 int fnum_vertices_after_transform = 2 * n_basic_blocks;
475 int fnum_edges_after_transform = n_edges + n_basic_blocks;
477 /* Count the new SOURCE and EXIT vertices to be added. */
478 int fmax_num_vertices =
479 fnum_vertices_after_transform + n_edges + n_basic_blocks + 2;
481 /* In create_fixup_graph: Each basic block and edge can be split into 3
482 edges. Number of balance edges = n_basic_blocks. So after
483 create_fixup_graph:
484 max_edges = 4 * n_basic_blocks + 3 * n_edges
485 Accounting for residual flow edges
486 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
487 = 8 * n_basic_blocks + 6 * n_edges
488 < 8 * n_basic_blocks + 8 * n_edges. */
489 int fmax_num_edges = 8 * (n_basic_blocks + n_edges);
491 /* Initial num of vertices in the fixup graph. */
492 fixup_graph->num_vertices = n_basic_blocks;
494 /* Fixup graph vertex list. */
495 fixup_graph->vertex_list =
496 (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type));
498 /* Fixup graph edge list. */
499 fixup_graph->edge_list =
500 (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type));
502 diff_out_in =
503 (gcov_type *) xcalloc (1 + fnum_vertices_after_transform,
504 sizeof (gcov_type));
506 /* Compute constants b, k_pos, k_neg used in the cost function calculation.
507 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */
508 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
509 total_vertex_weight += bb->count;
511 sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / n_basic_blocks);
513 k_pos = K_POS (sqrt_avg_vertex_weight);
514 k_neg = K_NEG (sqrt_avg_vertex_weight);
516 /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
517 connected by an edge e from v' to v''. w(e) = w(v). */
519 if (dump_file)
520 fprintf (dump_file, "\nVertex transformation:\n");
522 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
524 /* v'->v'': index1->(index1+1). */
525 i = 2 * bb->index;
526 fcost = (gcov_type) COST (k_pos, bb->count);
527 add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count,
528 fcost, CAP_INFINITY);
529 fixup_graph->num_vertices++;
531 FOR_EACH_EDGE (e, ei, bb->succs)
533 /* Edges with ignore attribute set should be treated like they don't
534 exist. */
535 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
536 continue;
537 j = 2 * e->dest->index;
538 fcost = (gcov_type) COST (k_pos, e->count);
539 add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost,
540 CAP_INFINITY);
544 /* After vertex transformation. */
545 gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform);
546 /* Redirect edges are not added for edges with ignore attribute. */
547 gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform);
549 fnum_edges_after_transform = fixup_graph->num_edges;
551 /* 2. Initialize D(v). */
552 for (i = 0; i < fnum_edges_after_transform; i++)
554 pfedge = fixup_graph->edge_list + i;
555 diff_out_in[pfedge->src] += pfedge->weight;
556 diff_out_in[pfedge->dest] -= pfedge->weight;
559 /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */
560 for (i = 0; i <= 3; i++)
561 diff_out_in[i] = 0;
563 /* 3. Add reverse edges: needed to decrease counts during smoothing. */
564 if (dump_file)
565 fprintf (dump_file, "\nReverse edges:\n");
566 for (i = 0; i < fnum_edges_after_transform; i++)
568 pfedge = fixup_graph->edge_list + i;
569 if ((pfedge->src == 0) || (pfedge->src == 2))
570 continue;
571 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
572 if (!r_pfedge && pfedge->weight)
574 /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
575 capacity is 0. */
576 fcost = (gcov_type) COST (k_neg, pfedge->weight);
577 add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src,
578 REVERSE_EDGE, 0, fcost, pfedge->weight);
582 /* 4. Create single source and sink. Connect new source vertex s' to function
583 entry block. Connect sink vertex t' to function exit. */
584 if (dump_file)
585 fprintf (dump_file, "\ns'->S, T->t':\n");
587 new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices;
588 fixup_graph->num_vertices++;
589 /* Set supply_value to 1 to avoid zero count function ENTRY. */
590 add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE,
591 1 /* supply_value */, 0, 1 /* supply_value */);
593 /* Create new exit with EXIT_BLOCK as single pred. */
594 new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices;
595 fixup_graph->num_vertices++;
596 add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index,
597 SINK_CONNECT_EDGE,
598 0 /* demand_value */, 0, 0 /* demand_value */);
600 /* Connect vertices with unbalanced D(v) to source/sink. */
601 if (dump_file)
602 fprintf (dump_file, "\nD(v) balance:\n");
603 /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
604 diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2. */
605 for (i = 4; i < new_entry_index; i += 2)
607 if (diff_out_in[i] > 0)
609 add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0,
610 diff_out_in[i]);
611 demand_value += diff_out_in[i];
613 else if (diff_out_in[i] < 0)
615 add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0,
616 -diff_out_in[i]);
617 supply_value -= diff_out_in[i];
621 /* Set supply = demand. */
622 if (dump_file)
624 fprintf (dump_file, "\nAdjust supply and demand:\n");
625 fprintf (dump_file, "supply_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
626 supply_value);
627 fprintf (dump_file, "demand_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
628 demand_value);
631 if (demand_value > supply_value)
633 pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK);
634 pfedge->max_capacity += (demand_value - supply_value);
636 else
638 pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index);
639 pfedge->max_capacity += (supply_value - demand_value);
642 /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
643 created by the vertex transformation step from self-edges in the original
644 CFG and by the reverse edges added earlier. */
645 if (dump_file)
646 fprintf (dump_file, "\nNormalize edges:\n");
648 fnum_edges = fixup_graph->num_edges;
649 fedge_list = fixup_graph->edge_list;
651 for (i = 0; i < fnum_edges; i++)
653 pfedge = fedge_list + i;
654 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
655 if (((pfedge->type == VERTEX_SPLIT_EDGE)
656 || (pfedge->type == REDIRECT_EDGE)) && r_pfedge)
658 new_index = fixup_graph->num_vertices;
659 fixup_graph->num_vertices++;
661 if (dump_file)
663 fprintf (dump_file, "\nAnti-parallel edge:\n");
664 dump_fixup_edge (dump_file, fixup_graph, pfedge);
665 dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
666 fprintf (dump_file, "New vertex is %d.\n", new_index);
667 fprintf (dump_file, "------------------\n");
670 pfedge->cost /= 2;
671 pfedge->norm_vertex_index = new_index;
672 if (dump_file)
674 fprintf (dump_file, "After normalization:\n");
675 dump_fixup_edge (dump_file, fixup_graph, pfedge);
678 /* Add a new fixup edge: new_index->src. */
679 add_fixup_edge (fixup_graph, new_index, pfedge->src,
680 REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost,
681 r_pfedge->max_capacity);
682 gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices);
684 /* Edge: r_pfedge->src -> r_pfedge->dest
685 ==> r_pfedge->src -> new_index. */
686 r_pfedge->dest = new_index;
687 r_pfedge->type = REVERSE_NORMALIZED_EDGE;
688 r_pfedge->cost = pfedge->cost;
689 r_pfedge->max_capacity = pfedge->max_capacity;
690 if (dump_file)
691 dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
695 if (dump_file)
696 dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()");
698 /* Cleanup. */
699 free (diff_out_in);
703 /* Allocates space for the structures in AUGMENTING_PATH. The space needed is
704 proportional to the number of nodes in the graph, which is given by
705 GRAPH_SIZE. */
707 static void
708 init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size)
710 augmenting_path->queue_list.queue = (int *)
711 xcalloc (graph_size + 2, sizeof (int));
712 augmenting_path->queue_list.size = graph_size + 2;
713 augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int));
714 augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int));
717 /* Free the structures in AUGMENTING_PATH. */
718 static void
719 free_augmenting_path (augmenting_path_type *augmenting_path)
721 free (augmenting_path->queue_list.queue);
722 free (augmenting_path->bb_pred);
723 free (augmenting_path->is_visited);
727 /* Queue routines. Assumes queue will never overflow. */
729 static void
730 init_queue (queue_type *queue_list)
732 gcc_assert (queue_list);
733 queue_list->head = 0;
734 queue_list->tail = 0;
737 /* Return true if QUEUE_LIST is empty. */
738 static bool
739 is_empty (queue_type *queue_list)
741 return (queue_list->head == queue_list->tail);
744 /* Insert element X into QUEUE_LIST. */
745 static void
746 enqueue (queue_type *queue_list, int x)
748 gcc_assert (queue_list->tail < queue_list->size);
749 queue_list->queue[queue_list->tail] = x;
750 (queue_list->tail)++;
753 /* Return the first element in QUEUE_LIST. */
754 static int
755 dequeue (queue_type *queue_list)
757 int x;
758 gcc_assert (queue_list->head >= 0);
759 x = queue_list->queue[queue_list->head];
760 (queue_list->head)++;
761 return x;
765 /* Finds a negative cycle in the residual network using
766 the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
767 minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
768 considered.
770 Parameters:
771 FIXUP_GRAPH - Residual graph (input/output)
772 The following are allocated/freed by the caller:
773 PI - Vector to hold predecessors in path (pi = pred index)
774 D - D[I] holds minimum cost of path from i to sink
775 CYCLE - Vector to hold the minimum cost cycle
777 Return:
778 true if a negative cycle was found, false otherwise. */
780 static bool
781 cancel_negative_cycle (fixup_graph_type *fixup_graph,
782 int *pi, gcov_type *d, int *cycle)
784 int i, j, k;
785 int fnum_vertices, fnum_edges;
786 fixup_edge_p fedge_list, pfedge, r_pfedge;
787 bool found_cycle = false;
788 int cycle_start = 0, cycle_end = 0;
789 gcov_type sum_cost = 0, cycle_flow = 0;
790 int new_entry_index;
791 bool propagated = false;
793 gcc_assert (fixup_graph);
794 fnum_vertices = fixup_graph->num_vertices;
795 fnum_edges = fixup_graph->num_edges;
796 fedge_list = fixup_graph->edge_list;
797 new_entry_index = fixup_graph->new_entry_index;
799 /* Initialize. */
800 /* Skip ENTRY. */
801 for (i = 1; i < fnum_vertices; i++)
803 d[i] = CAP_INFINITY;
804 pi[i] = -1;
805 cycle[i] = -1;
807 d[ENTRY_BLOCK] = 0;
809 /* Relax. */
810 for (k = 1; k < fnum_vertices; k++)
812 propagated = false;
813 for (i = 0; i < fnum_edges; i++)
815 pfedge = fedge_list + i;
816 if (pfedge->src == new_entry_index)
817 continue;
818 if (pfedge->is_rflow_valid && pfedge->rflow
819 && d[pfedge->src] != CAP_INFINITY
820 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
822 d[pfedge->dest] = d[pfedge->src] + pfedge->cost;
823 pi[pfedge->dest] = pfedge->src;
824 propagated = true;
827 if (!propagated)
828 break;
831 if (!propagated)
832 /* No negative cycles exist. */
833 return 0;
835 /* Detect. */
836 for (i = 0; i < fnum_edges; i++)
838 pfedge = fedge_list + i;
839 if (pfedge->src == new_entry_index)
840 continue;
841 if (pfedge->is_rflow_valid && pfedge->rflow
842 && d[pfedge->src] != CAP_INFINITY
843 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
845 found_cycle = true;
846 break;
850 if (!found_cycle)
851 return 0;
853 /* Augment the cycle with the cycle's minimum residual capacity. */
854 found_cycle = false;
855 cycle[0] = pfedge->dest;
856 j = pfedge->dest;
858 for (i = 1; i < fnum_vertices; i++)
860 j = pi[j];
861 cycle[i] = j;
862 for (k = 0; k < i; k++)
864 if (cycle[k] == j)
866 /* cycle[k] -> ... -> cycle[i]. */
867 cycle_start = k;
868 cycle_end = i;
869 found_cycle = true;
870 break;
873 if (found_cycle)
874 break;
877 gcc_assert (cycle[cycle_start] == cycle[cycle_end]);
878 if (dump_file)
879 fprintf (dump_file, "\nNegative cycle length is %d:\n",
880 cycle_end - cycle_start);
882 sum_cost = 0;
883 cycle_flow = CAP_INFINITY;
884 for (k = cycle_start; k < cycle_end; k++)
886 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
887 cycle_flow = MIN (cycle_flow, pfedge->rflow);
888 sum_cost += pfedge->cost;
889 if (dump_file)
890 fprintf (dump_file, "%d ", cycle[k]);
893 if (dump_file)
895 fprintf (dump_file, "%d", cycle[k]);
896 fprintf (dump_file,
897 ": (" HOST_WIDEST_INT_PRINT_DEC ", " HOST_WIDEST_INT_PRINT_DEC
898 ")\n", sum_cost, cycle_flow);
899 fprintf (dump_file,
900 "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC "\n",
901 cycle_flow);
904 for (k = cycle_start; k < cycle_end; k++)
906 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
907 r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]);
908 pfedge->rflow -= cycle_flow;
909 if (pfedge->type)
910 pfedge->flow += cycle_flow;
911 r_pfedge->rflow += cycle_flow;
912 if (r_pfedge->type)
913 r_pfedge->flow -= cycle_flow;
916 return true;
920 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
921 the edges. ENTRY and EXIT vertices should not be considered. */
923 static void
924 compute_residual_flow (fixup_graph_type *fixup_graph)
926 int i;
927 int fnum_edges;
928 fixup_edge_p fedge_list, pfedge;
930 gcc_assert (fixup_graph);
932 if (dump_file)
933 fputs ("\ncompute_residual_flow():\n", dump_file);
935 fnum_edges = fixup_graph->num_edges;
936 fedge_list = fixup_graph->edge_list;
938 for (i = 0; i < fnum_edges; i++)
940 pfedge = fedge_list + i;
941 pfedge->rflow = pfedge->max_capacity - pfedge->flow;
942 pfedge->is_rflow_valid = true;
943 add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow,
944 -pfedge->cost);
949 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
950 SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
951 this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
952 to reflect the path found.
953 Returns: 0 if no augmenting path is found, 1 otherwise. */
955 static int
956 find_augmenting_path (fixup_graph_type *fixup_graph,
957 augmenting_path_type *augmenting_path, int source,
958 int sink)
960 int u = 0;
961 int i;
962 fixup_vertex_p fvertex_list, pfvertex;
963 fixup_edge_p pfedge;
964 int *bb_pred, *is_visited;
965 queue_type *queue_list;
967 gcc_assert (augmenting_path);
968 bb_pred = augmenting_path->bb_pred;
969 gcc_assert (bb_pred);
970 is_visited = augmenting_path->is_visited;
971 gcc_assert (is_visited);
972 queue_list = &(augmenting_path->queue_list);
974 gcc_assert (fixup_graph);
976 fvertex_list = fixup_graph->vertex_list;
978 for (u = 0; u < fixup_graph->num_vertices; u++)
979 is_visited[u] = 0;
981 init_queue (queue_list);
982 enqueue (queue_list, source);
983 bb_pred[source] = -1;
985 while (!is_empty (queue_list))
987 u = dequeue (queue_list);
988 is_visited[u] = 1;
989 pfvertex = fvertex_list + u;
990 for (i = 0; pfvertex->succ_edges.iterate (i, &pfedge);
991 i++)
993 int dest = pfedge->dest;
994 if ((pfedge->rflow > 0) && (is_visited[dest] == 0))
996 enqueue (queue_list, dest);
997 bb_pred[dest] = u;
998 is_visited[dest] = 1;
999 if (dest == sink)
1000 return 1;
1005 return 0;
1009 /* Routine to find the maximal flow:
1010 Algorithm:
1011 1. Initialize flow to 0
1012 2. Find an augmenting path form source to sink.
1013 3. Send flow equal to the path's residual capacity along the edges of this path.
1014 4. Repeat steps 2 and 3 until no new augmenting path is found.
1016 Parameters:
1017 SOURCE: index of source vertex (input)
1018 SINK: index of sink vertex (input)
1019 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1020 set to have a valid maximal flow by this routine. (input)
1021 Return: Maximum flow possible. */
1023 static gcov_type
1024 find_max_flow (fixup_graph_type *fixup_graph, int source, int sink)
1026 int fnum_edges;
1027 augmenting_path_type augmenting_path;
1028 int *bb_pred;
1029 gcov_type max_flow = 0;
1030 int i, u;
1031 fixup_edge_p fedge_list, pfedge, r_pfedge;
1033 gcc_assert (fixup_graph);
1035 fnum_edges = fixup_graph->num_edges;
1036 fedge_list = fixup_graph->edge_list;
1038 /* Initialize flow to 0. */
1039 for (i = 0; i < fnum_edges; i++)
1041 pfedge = fedge_list + i;
1042 pfedge->flow = 0;
1045 compute_residual_flow (fixup_graph);
1047 init_augmenting_path (&augmenting_path, fixup_graph->num_vertices);
1049 bb_pred = augmenting_path.bb_pred;
1050 while (find_augmenting_path (fixup_graph, &augmenting_path, source, sink))
1052 /* Determine the amount by which we can increment the flow. */
1053 gcov_type increment = CAP_INFINITY;
1054 for (u = sink; u != source; u = bb_pred[u])
1056 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1057 increment = MIN (increment, pfedge->rflow);
1059 max_flow += increment;
1061 /* Now increment the flow. EXIT vertex index is 1. */
1062 for (u = sink; u != source; u = bb_pred[u])
1064 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1065 r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]);
1066 if (pfedge->type)
1068 /* forward edge. */
1069 pfedge->flow += increment;
1070 pfedge->rflow -= increment;
1071 r_pfedge->rflow += increment;
1073 else
1075 /* backward edge. */
1076 gcc_assert (r_pfedge->type);
1077 r_pfedge->rflow += increment;
1078 r_pfedge->flow -= increment;
1079 pfedge->rflow -= increment;
1083 if (dump_file)
1085 fprintf (dump_file, "\nDump augmenting path:\n");
1086 for (u = sink; u != source; u = bb_pred[u])
1088 print_basic_block (dump_file, fixup_graph, u);
1089 fprintf (dump_file, "<-");
1091 fprintf (dump_file,
1092 "ENTRY (path_capacity=" HOST_WIDEST_INT_PRINT_DEC ")\n",
1093 increment);
1094 fprintf (dump_file,
1095 "Network flow is " HOST_WIDEST_INT_PRINT_DEC ".\n",
1096 max_flow);
1100 free_augmenting_path (&augmenting_path);
1101 if (dump_file)
1102 dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()");
1103 return max_flow;
1107 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1108 after applying the find_minimum_cost_flow() routine. */
1110 static void
1111 adjust_cfg_counts (fixup_graph_type *fixup_graph)
1113 basic_block bb;
1114 edge e;
1115 edge_iterator ei;
1116 int i, j;
1117 fixup_edge_p pfedge, pfedge_n;
1119 gcc_assert (fixup_graph);
1121 if (dump_file)
1122 fprintf (dump_file, "\nadjust_cfg_counts():\n");
1124 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1126 i = 2 * bb->index;
1128 /* Fixup BB. */
1129 if (dump_file)
1130 fprintf (dump_file,
1131 "BB%d: " HOST_WIDEST_INT_PRINT_DEC "", bb->index, bb->count);
1133 pfedge = find_fixup_edge (fixup_graph, i, i + 1);
1134 if (pfedge->flow)
1136 bb->count += pfedge->flow;
1137 if (dump_file)
1139 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1140 pfedge->flow);
1141 print_edge (dump_file, fixup_graph, i, i + 1);
1142 fprintf (dump_file, ")");
1146 pfedge_n =
1147 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1148 /* Deduct flow from normalized reverse edge. */
1149 if (pfedge->norm_vertex_index && pfedge_n->flow)
1151 bb->count -= pfedge_n->flow;
1152 if (dump_file)
1154 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
1155 pfedge_n->flow);
1156 print_edge (dump_file, fixup_graph, i + 1,
1157 pfedge->norm_vertex_index);
1158 fprintf (dump_file, ")");
1161 if (dump_file)
1162 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\n", bb->count);
1164 /* Fixup edge. */
1165 FOR_EACH_EDGE (e, ei, bb->succs)
1167 /* Treat edges with ignore attribute set as if they don't exist. */
1168 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1169 continue;
1171 j = 2 * e->dest->index;
1172 if (dump_file)
1173 fprintf (dump_file, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC "",
1174 bb->index, e->dest->index, e->count);
1176 pfedge = find_fixup_edge (fixup_graph, i + 1, j);
1178 if (bb->index != e->dest->index)
1180 /* Non-self edge. */
1181 if (pfedge->flow)
1183 e->count += pfedge->flow;
1184 if (dump_file)
1186 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1187 pfedge->flow);
1188 print_edge (dump_file, fixup_graph, i + 1, j);
1189 fprintf (dump_file, ")");
1193 pfedge_n =
1194 find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index);
1195 /* Deduct flow from normalized reverse edge. */
1196 if (pfedge->norm_vertex_index && pfedge_n->flow)
1198 e->count -= pfedge_n->flow;
1199 if (dump_file)
1201 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
1202 pfedge_n->flow);
1203 print_edge (dump_file, fixup_graph, j,
1204 pfedge->norm_vertex_index);
1205 fprintf (dump_file, ")");
1209 else
1211 /* Handle self edges. Self edge is split with a normalization
1212 vertex. Here i=j. */
1213 pfedge = find_fixup_edge (fixup_graph, j, i + 1);
1214 pfedge_n =
1215 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1216 e->count += pfedge_n->flow;
1217 bb->count += pfedge_n->flow;
1218 if (dump_file)
1220 fprintf (dump_file, "(self edge)");
1221 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1222 pfedge_n->flow);
1223 print_edge (dump_file, fixup_graph, i + 1,
1224 pfedge->norm_vertex_index);
1225 fprintf (dump_file, ")");
1229 if (bb->count)
1230 e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1231 if (dump_file)
1232 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\t(%.1f%%)\n",
1233 e->count, e->probability * 100.0 / REG_BR_PROB_BASE);
1237 ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs);
1238 EXIT_BLOCK_PTR->count = sum_edge_counts (EXIT_BLOCK_PTR->preds);
1240 /* Compute edge probabilities. */
1241 FOR_ALL_BB (bb)
1243 if (bb->count)
1245 FOR_EACH_EDGE (e, ei, bb->succs)
1246 e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1248 else
1250 int total = 0;
1251 FOR_EACH_EDGE (e, ei, bb->succs)
1252 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1253 total++;
1254 if (total)
1256 FOR_EACH_EDGE (e, ei, bb->succs)
1258 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1259 e->probability = REG_BR_PROB_BASE / total;
1260 else
1261 e->probability = 0;
1264 else
1266 total += EDGE_COUNT (bb->succs);
1267 FOR_EACH_EDGE (e, ei, bb->succs)
1268 e->probability = REG_BR_PROB_BASE / total;
1273 if (dump_file)
1275 fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n",
1276 current_function_name ());
1277 FOR_EACH_BB (bb)
1279 if ((bb->count != sum_edge_counts (bb->preds))
1280 || (bb->count != sum_edge_counts (bb->succs)))
1282 fprintf (dump_file,
1283 "BB%d(" HOST_WIDEST_INT_PRINT_DEC ") **INVALID**: ",
1284 bb->index, bb->count);
1285 fprintf (stderr,
1286 "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC
1287 ") **INVALID**: \n", bb->index, bb->count);
1288 fprintf (dump_file, "in_edges=" HOST_WIDEST_INT_PRINT_DEC " ",
1289 sum_edge_counts (bb->preds));
1290 fprintf (dump_file, "out_edges=" HOST_WIDEST_INT_PRINT_DEC "\n",
1291 sum_edge_counts (bb->succs));
1298 /* Implements the negative cycle canceling algorithm to compute a minimum cost
1299 flow.
1300 Algorithm:
1301 1. Find maximal flow.
1302 2. Form residual network
1303 3. Repeat:
1304 While G contains a negative cost cycle C, reverse the flow on the found cycle
1305 by the minimum residual capacity in that cycle.
1306 4. Form the minimal cost flow
1307 f(u,v) = rf(v, u)
1308 Input:
1309 FIXUP_GRAPH - Initial fixup graph.
1310 The flow field is modified to represent the minimum cost flow. */
1312 static void
1313 find_minimum_cost_flow (fixup_graph_type *fixup_graph)
1315 /* Holds the index of predecessor in path. */
1316 int *pred;
1317 /* Used to hold the minimum cost cycle. */
1318 int *cycle;
1319 /* Used to record the number of iterations of cancel_negative_cycle. */
1320 int iteration;
1321 /* Vector d[i] holds the minimum cost of path from i to sink. */
1322 gcov_type *d;
1323 int fnum_vertices;
1324 int new_exit_index;
1325 int new_entry_index;
1327 gcc_assert (fixup_graph);
1328 fnum_vertices = fixup_graph->num_vertices;
1329 new_exit_index = fixup_graph->new_exit_index;
1330 new_entry_index = fixup_graph->new_entry_index;
1332 find_max_flow (fixup_graph, new_entry_index, new_exit_index);
1334 /* Initialize the structures for find_negative_cycle(). */
1335 pred = (int *) xcalloc (fnum_vertices, sizeof (int));
1336 d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type));
1337 cycle = (int *) xcalloc (fnum_vertices, sizeof (int));
1339 /* Repeatedly find and cancel negative cost cycles, until
1340 no more negative cycles exist. This also updates the flow field
1341 to represent the minimum cost flow so far. */
1342 iteration = 0;
1343 while (cancel_negative_cycle (fixup_graph, pred, d, cycle))
1345 iteration++;
1346 if (iteration > MAX_ITER (fixup_graph->num_vertices,
1347 fixup_graph->num_edges))
1348 break;
1351 if (dump_file)
1352 dump_fixup_graph (dump_file, fixup_graph,
1353 "After find_minimum_cost_flow()");
1355 /* Cleanup structures. */
1356 free (pred);
1357 free (d);
1358 free (cycle);
1362 /* Compute the sum of the edge counts in TO_EDGES. */
1364 gcov_type
1365 sum_edge_counts (vec<edge, va_gc> *to_edges)
1367 gcov_type sum = 0;
1368 edge e;
1369 edge_iterator ei;
1371 FOR_EACH_EDGE (e, ei, to_edges)
1373 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1374 continue;
1375 sum += e->count;
1377 return sum;
1381 /* Main routine. Smoothes the initial assigned basic block and edge counts using
1382 a minimum cost flow algorithm, to ensure that the flow consistency rule is
1383 obeyed: sum of outgoing edges = sum of incoming edges for each basic
1384 block. */
1386 void
1387 mcf_smooth_cfg (void)
1389 fixup_graph_type fixup_graph;
1390 memset (&fixup_graph, 0, sizeof (fixup_graph));
1391 create_fixup_graph (&fixup_graph);
1392 find_minimum_cost_flow (&fixup_graph);
1393 adjust_cfg_counts (&fixup_graph);
1394 delete_fixup_graph (&fixup_graph);