2012-07-26 Kazu Hirata <kazu@codesourcery.com>
[official-gcc.git] / gcc / mcf.c
blobf5985c134abec8d70f7fa923eabc9c25df01fc7e
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 "basic-block.h"
50 #include "gcov-io.h"
51 #include "profile.h"
52 #include "dumpfile.h"
54 /* CAP_INFINITY: Constant to represent infinite capacity. */
55 #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT)
57 /* COST FUNCTION. */
58 #define K_POS(b) ((b))
59 #define K_NEG(b) (50 * (b))
60 #define COST(k, w) ((k) / mcf_ln ((w) + 2))
61 /* Limit the number of iterations for cancel_negative_cycles() to ensure
62 reasonable compile time. */
63 #define MAX_ITER(n, e) 10 + (1000000 / ((n) * (e)))
64 typedef enum
66 INVALID_EDGE,
67 VERTEX_SPLIT_EDGE, /* Edge to represent vertex with w(e) = w(v). */
68 REDIRECT_EDGE, /* Edge after vertex transformation. */
69 REVERSE_EDGE,
70 SOURCE_CONNECT_EDGE, /* Single edge connecting to single source. */
71 SINK_CONNECT_EDGE, /* Single edge connecting to single sink. */
72 BALANCE_EDGE, /* Edge connecting with source/sink: cp(e) = 0. */
73 REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge. */
74 REVERSE_NORMALIZED_EDGE /* Normalized edge for a reverse edge. */
75 } edge_type;
77 /* Structure to represent an edge in the fixup graph. */
78 typedef struct fixup_edge_d
80 int src;
81 int dest;
82 /* Flag denoting type of edge and attributes for the flow field. */
83 edge_type type;
84 bool is_rflow_valid;
85 /* Index to the normalization vertex added for this edge. */
86 int norm_vertex_index;
87 /* Flow for this edge. */
88 gcov_type flow;
89 /* Residual flow for this edge - used during negative cycle canceling. */
90 gcov_type rflow;
91 gcov_type weight;
92 gcov_type cost;
93 gcov_type max_capacity;
94 } fixup_edge_type;
96 typedef fixup_edge_type *fixup_edge_p;
98 DEF_VEC_P (fixup_edge_p);
99 DEF_VEC_ALLOC_P (fixup_edge_p, heap);
101 /* Structure to represent a vertex in the fixup graph. */
102 typedef struct fixup_vertex_d
104 VEC (fixup_edge_p, heap) *succ_edges;
105 } fixup_vertex_type;
107 typedef fixup_vertex_type *fixup_vertex_p;
109 /* Fixup graph used in the MCF algorithm. */
110 typedef struct fixup_graph_d
112 /* Current number of vertices for the graph. */
113 int num_vertices;
114 /* Current number of edges for the graph. */
115 int num_edges;
116 /* Index of new entry vertex. */
117 int new_entry_index;
118 /* Index of new exit vertex. */
119 int new_exit_index;
120 /* Fixup vertex list. Adjacency list for fixup graph. */
121 fixup_vertex_p vertex_list;
122 /* Fixup edge list. */
123 fixup_edge_p edge_list;
124 } fixup_graph_type;
126 typedef struct queue_d
128 int *queue;
129 int head;
130 int tail;
131 int size;
132 } queue_type;
134 /* Structure used in the maximal flow routines to find augmenting path. */
135 typedef struct augmenting_path_d
137 /* Queue used to hold vertex indices. */
138 queue_type queue_list;
139 /* Vector to hold chain of pred vertex indices in augmenting path. */
140 int *bb_pred;
141 /* Vector that indicates if basic block i has been visited. */
142 int *is_visited;
143 } augmenting_path_type;
146 /* Function definitions. */
148 /* Dump routines to aid debugging. */
150 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */
152 static void
153 print_basic_block (FILE *file, fixup_graph_type *fixup_graph, int n)
155 if (n == ENTRY_BLOCK)
156 fputs ("ENTRY", file);
157 else if (n == ENTRY_BLOCK + 1)
158 fputs ("ENTRY''", file);
159 else if (n == 2 * EXIT_BLOCK)
160 fputs ("EXIT", file);
161 else if (n == 2 * EXIT_BLOCK + 1)
162 fputs ("EXIT''", file);
163 else if (n == fixup_graph->new_exit_index)
164 fputs ("NEW_EXIT", file);
165 else if (n == fixup_graph->new_entry_index)
166 fputs ("NEW_ENTRY", file);
167 else
169 fprintf (file, "%d", n / 2);
170 if (n % 2)
171 fputs ("''", file);
172 else
173 fputs ("'", file);
178 /* Print edge S->D for given fixup_graph with n' and n'' format.
179 PARAMETERS:
180 S is the index of the source vertex of the edge (input) and
181 D is the index of the destination vertex of the edge (input) for the given
182 fixup_graph (input). */
184 static void
185 print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d)
187 print_basic_block (file, fixup_graph, s);
188 fputs ("->", file);
189 print_basic_block (file, fixup_graph, d);
193 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
194 file. */
195 static void
196 dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge)
198 if (!fedge)
200 fputs ("NULL fixup graph edge.\n", file);
201 return;
204 print_edge (file, fixup_graph, fedge->src, fedge->dest);
205 fputs (": ", file);
207 if (fedge->type)
209 fprintf (file, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC "/",
210 fedge->flow);
211 if (fedge->max_capacity == CAP_INFINITY)
212 fputs ("+oo,", file);
213 else
214 fprintf (file, "" HOST_WIDEST_INT_PRINT_DEC ",", fedge->max_capacity);
217 if (fedge->is_rflow_valid)
219 if (fedge->rflow == CAP_INFINITY)
220 fputs (" rflow=+oo.", file);
221 else
222 fprintf (file, " rflow=" HOST_WIDEST_INT_PRINT_DEC ",", fedge->rflow);
225 fprintf (file, " cost=" HOST_WIDEST_INT_PRINT_DEC ".", fedge->cost);
227 fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest);
229 if (fedge->type)
231 switch (fedge->type)
233 case VERTEX_SPLIT_EDGE:
234 fputs (" @VERTEX_SPLIT_EDGE", file);
235 break;
237 case REDIRECT_EDGE:
238 fputs (" @REDIRECT_EDGE", file);
239 break;
241 case SOURCE_CONNECT_EDGE:
242 fputs (" @SOURCE_CONNECT_EDGE", file);
243 break;
245 case SINK_CONNECT_EDGE:
246 fputs (" @SINK_CONNECT_EDGE", file);
247 break;
249 case REVERSE_EDGE:
250 fputs (" @REVERSE_EDGE", file);
251 break;
253 case BALANCE_EDGE:
254 fputs (" @BALANCE_EDGE", file);
255 break;
257 case REDIRECT_NORMALIZED_EDGE:
258 case REVERSE_NORMALIZED_EDGE:
259 fputs (" @NORMALIZED_EDGE", file);
260 break;
262 default:
263 fputs (" @INVALID_EDGE", file);
264 break;
267 fputs ("\n", file);
271 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
272 file. The input string MSG is printed out as a heading. */
274 static void
275 dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg)
277 int i, j;
278 int fnum_vertices, fnum_edges;
280 fixup_vertex_p fvertex_list, pfvertex;
281 fixup_edge_p pfedge;
283 gcc_assert (fixup_graph);
284 fvertex_list = fixup_graph->vertex_list;
285 fnum_vertices = fixup_graph->num_vertices;
286 fnum_edges = fixup_graph->num_edges;
288 fprintf (file, "\nDump fixup graph for %s(): %s.\n",
289 current_function_name (), msg);
290 fprintf (file,
291 "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
292 fnum_vertices, fnum_edges, fixup_graph->new_exit_index);
294 for (i = 0; i < fnum_vertices; i++)
296 pfvertex = fvertex_list + i;
297 fprintf (file, "vertex_list[%d]: %d succ fixup edges.\n",
298 i, VEC_length (fixup_edge_p, pfvertex->succ_edges));
300 for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge);
301 j++)
303 /* Distinguish forward edges and backward edges in the residual flow
304 network. */
305 if (pfedge->type)
306 fputs ("(f) ", file);
307 else if (pfedge->is_rflow_valid)
308 fputs ("(b) ", file);
309 dump_fixup_edge (file, fixup_graph, pfedge);
313 fputs ("\n", file);
317 /* Utility routines. */
318 /* ln() implementation: approximate calculation. Returns ln of X. */
320 static double
321 mcf_ln (double x)
323 #define E 2.71828
324 int l = 1;
325 double m = E;
327 gcc_assert (x >= 0);
329 while (m < x)
331 m *= E;
332 l++;
335 return l;
339 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
340 implementation) by John Carmack. Returns sqrt of X. */
342 static double
343 mcf_sqrt (double x)
345 #define MAGIC_CONST1 0x1fbcf800
346 #define MAGIC_CONST2 0x5f3759df
347 union {
348 int intPart;
349 float floatPart;
350 } convertor, convertor2;
352 gcc_assert (x >= 0);
354 convertor.floatPart = x;
355 convertor2.floatPart = x;
356 convertor.intPart = MAGIC_CONST1 + (convertor.intPart >> 1);
357 convertor2.intPart = MAGIC_CONST2 - (convertor2.intPart >> 1);
359 return 0.5f * (convertor.floatPart + (x * convertor2.floatPart));
363 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
364 (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
365 added set to COST. */
367 static fixup_edge_p
368 add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost)
370 fixup_vertex_p curr_vertex = fixup_graph->vertex_list + src;
371 fixup_edge_p curr_edge = fixup_graph->edge_list + fixup_graph->num_edges;
372 curr_edge->src = src;
373 curr_edge->dest = dest;
374 curr_edge->cost = cost;
375 fixup_graph->num_edges++;
376 if (dump_file)
377 dump_fixup_edge (dump_file, fixup_graph, curr_edge);
378 VEC_safe_push (fixup_edge_p, heap, curr_vertex->succ_edges, curr_edge);
379 return curr_edge;
383 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
384 MAX_CAPACITY to the edge_list in the fixup graph. */
386 static void
387 add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
388 edge_type type, gcov_type weight, gcov_type cost,
389 gcov_type max_capacity)
391 fixup_edge_p curr_edge = add_edge(fixup_graph, src, dest, cost);
392 curr_edge->type = type;
393 curr_edge->weight = weight;
394 curr_edge->max_capacity = max_capacity;
398 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
399 to the fixup graph. */
401 static void
402 add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
403 gcov_type rflow, gcov_type cost)
405 fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost);
406 curr_edge->rflow = rflow;
407 curr_edge->is_rflow_valid = true;
408 /* This edge is not a valid edge - merely used to hold residual flow. */
409 curr_edge->type = INVALID_EDGE;
413 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
414 exist in the FIXUP_GRAPH. */
416 static fixup_edge_p
417 find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest)
419 int j;
420 fixup_edge_p pfedge;
421 fixup_vertex_p pfvertex;
423 gcc_assert (src < fixup_graph->num_vertices);
425 pfvertex = fixup_graph->vertex_list + src;
427 for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge);
428 j++)
429 if (pfedge->dest == dest)
430 return pfedge;
432 return NULL;
436 /* Cleanup routine to free structures in FIXUP_GRAPH. */
438 static void
439 delete_fixup_graph (fixup_graph_type *fixup_graph)
441 int i;
442 int fnum_vertices = fixup_graph->num_vertices;
443 fixup_vertex_p pfvertex = fixup_graph->vertex_list;
445 for (i = 0; i < fnum_vertices; i++, pfvertex++)
446 VEC_free (fixup_edge_p, heap, pfvertex->succ_edges);
448 free (fixup_graph->vertex_list);
449 free (fixup_graph->edge_list);
453 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
455 static void
456 create_fixup_graph (fixup_graph_type *fixup_graph)
458 double sqrt_avg_vertex_weight = 0;
459 double total_vertex_weight = 0;
460 double k_pos = 0;
461 double k_neg = 0;
462 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */
463 gcov_type *diff_out_in = NULL;
464 gcov_type supply_value = 1, demand_value = 0;
465 gcov_type fcost = 0;
466 int new_entry_index = 0, new_exit_index = 0;
467 int i = 0, j = 0;
468 int new_index = 0;
469 basic_block bb;
470 edge e;
471 edge_iterator ei;
472 fixup_edge_p pfedge, r_pfedge;
473 fixup_edge_p fedge_list;
474 int fnum_edges;
476 /* Each basic_block will be split into 2 during vertex transformation. */
477 int fnum_vertices_after_transform = 2 * n_basic_blocks;
478 int fnum_edges_after_transform = n_edges + n_basic_blocks;
480 /* Count the new SOURCE and EXIT vertices to be added. */
481 int fmax_num_vertices =
482 fnum_vertices_after_transform + n_edges + n_basic_blocks + 2;
484 /* In create_fixup_graph: Each basic block and edge can be split into 3
485 edges. Number of balance edges = n_basic_blocks. So after
486 create_fixup_graph:
487 max_edges = 4 * n_basic_blocks + 3 * n_edges
488 Accounting for residual flow edges
489 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
490 = 8 * n_basic_blocks + 6 * n_edges
491 < 8 * n_basic_blocks + 8 * n_edges. */
492 int fmax_num_edges = 8 * (n_basic_blocks + n_edges);
494 /* Initial num of vertices in the fixup graph. */
495 fixup_graph->num_vertices = n_basic_blocks;
497 /* Fixup graph vertex list. */
498 fixup_graph->vertex_list =
499 (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type));
501 /* Fixup graph edge list. */
502 fixup_graph->edge_list =
503 (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type));
505 diff_out_in =
506 (gcov_type *) xcalloc (1 + fnum_vertices_after_transform,
507 sizeof (gcov_type));
509 /* Compute constants b, k_pos, k_neg used in the cost function calculation.
510 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */
511 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
512 total_vertex_weight += bb->count;
514 sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / n_basic_blocks);
516 k_pos = K_POS (sqrt_avg_vertex_weight);
517 k_neg = K_NEG (sqrt_avg_vertex_weight);
519 /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
520 connected by an edge e from v' to v''. w(e) = w(v). */
522 if (dump_file)
523 fprintf (dump_file, "\nVertex transformation:\n");
525 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
527 /* v'->v'': index1->(index1+1). */
528 i = 2 * bb->index;
529 fcost = (gcov_type) COST (k_pos, bb->count);
530 add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count,
531 fcost, CAP_INFINITY);
532 fixup_graph->num_vertices++;
534 FOR_EACH_EDGE (e, ei, bb->succs)
536 /* Edges with ignore attribute set should be treated like they don't
537 exist. */
538 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
539 continue;
540 j = 2 * e->dest->index;
541 fcost = (gcov_type) COST (k_pos, e->count);
542 add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost,
543 CAP_INFINITY);
547 /* After vertex transformation. */
548 gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform);
549 /* Redirect edges are not added for edges with ignore attribute. */
550 gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform);
552 fnum_edges_after_transform = fixup_graph->num_edges;
554 /* 2. Initialize D(v). */
555 for (i = 0; i < fnum_edges_after_transform; i++)
557 pfedge = fixup_graph->edge_list + i;
558 diff_out_in[pfedge->src] += pfedge->weight;
559 diff_out_in[pfedge->dest] -= pfedge->weight;
562 /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */
563 for (i = 0; i <= 3; i++)
564 diff_out_in[i] = 0;
566 /* 3. Add reverse edges: needed to decrease counts during smoothing. */
567 if (dump_file)
568 fprintf (dump_file, "\nReverse edges:\n");
569 for (i = 0; i < fnum_edges_after_transform; i++)
571 pfedge = fixup_graph->edge_list + i;
572 if ((pfedge->src == 0) || (pfedge->src == 2))
573 continue;
574 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
575 if (!r_pfedge && pfedge->weight)
577 /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
578 capacity is 0. */
579 fcost = (gcov_type) COST (k_neg, pfedge->weight);
580 add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src,
581 REVERSE_EDGE, 0, fcost, pfedge->weight);
585 /* 4. Create single source and sink. Connect new source vertex s' to function
586 entry block. Connect sink vertex t' to function exit. */
587 if (dump_file)
588 fprintf (dump_file, "\ns'->S, T->t':\n");
590 new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices;
591 fixup_graph->num_vertices++;
592 /* Set supply_value to 1 to avoid zero count function ENTRY. */
593 add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE,
594 1 /* supply_value */, 0, 1 /* supply_value */);
596 /* Create new exit with EXIT_BLOCK as single pred. */
597 new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices;
598 fixup_graph->num_vertices++;
599 add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index,
600 SINK_CONNECT_EDGE,
601 0 /* demand_value */, 0, 0 /* demand_value */);
603 /* Connect vertices with unbalanced D(v) to source/sink. */
604 if (dump_file)
605 fprintf (dump_file, "\nD(v) balance:\n");
606 /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
607 diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2. */
608 for (i = 4; i < new_entry_index; i += 2)
610 if (diff_out_in[i] > 0)
612 add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0,
613 diff_out_in[i]);
614 demand_value += diff_out_in[i];
616 else if (diff_out_in[i] < 0)
618 add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0,
619 -diff_out_in[i]);
620 supply_value -= diff_out_in[i];
624 /* Set supply = demand. */
625 if (dump_file)
627 fprintf (dump_file, "\nAdjust supply and demand:\n");
628 fprintf (dump_file, "supply_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
629 supply_value);
630 fprintf (dump_file, "demand_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
631 demand_value);
634 if (demand_value > supply_value)
636 pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK);
637 pfedge->max_capacity += (demand_value - supply_value);
639 else
641 pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index);
642 pfedge->max_capacity += (supply_value - demand_value);
645 /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
646 created by the vertex transformation step from self-edges in the original
647 CFG and by the reverse edges added earlier. */
648 if (dump_file)
649 fprintf (dump_file, "\nNormalize edges:\n");
651 fnum_edges = fixup_graph->num_edges;
652 fedge_list = fixup_graph->edge_list;
654 for (i = 0; i < fnum_edges; i++)
656 pfedge = fedge_list + i;
657 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
658 if (((pfedge->type == VERTEX_SPLIT_EDGE)
659 || (pfedge->type == REDIRECT_EDGE)) && r_pfedge)
661 new_index = fixup_graph->num_vertices;
662 fixup_graph->num_vertices++;
664 if (dump_file)
666 fprintf (dump_file, "\nAnti-parallel edge:\n");
667 dump_fixup_edge (dump_file, fixup_graph, pfedge);
668 dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
669 fprintf (dump_file, "New vertex is %d.\n", new_index);
670 fprintf (dump_file, "------------------\n");
673 pfedge->cost /= 2;
674 pfedge->norm_vertex_index = new_index;
675 if (dump_file)
677 fprintf (dump_file, "After normalization:\n");
678 dump_fixup_edge (dump_file, fixup_graph, pfedge);
681 /* Add a new fixup edge: new_index->src. */
682 add_fixup_edge (fixup_graph, new_index, pfedge->src,
683 REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost,
684 r_pfedge->max_capacity);
685 gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices);
687 /* Edge: r_pfedge->src -> r_pfedge->dest
688 ==> r_pfedge->src -> new_index. */
689 r_pfedge->dest = new_index;
690 r_pfedge->type = REVERSE_NORMALIZED_EDGE;
691 r_pfedge->cost = pfedge->cost;
692 r_pfedge->max_capacity = pfedge->max_capacity;
693 if (dump_file)
694 dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
698 if (dump_file)
699 dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()");
701 /* Cleanup. */
702 free (diff_out_in);
706 /* Allocates space for the structures in AUGMENTING_PATH. The space needed is
707 proportional to the number of nodes in the graph, which is given by
708 GRAPH_SIZE. */
710 static void
711 init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size)
713 augmenting_path->queue_list.queue = (int *)
714 xcalloc (graph_size + 2, sizeof (int));
715 augmenting_path->queue_list.size = graph_size + 2;
716 augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int));
717 augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int));
720 /* Free the structures in AUGMENTING_PATH. */
721 static void
722 free_augmenting_path (augmenting_path_type *augmenting_path)
724 free (augmenting_path->queue_list.queue);
725 free (augmenting_path->bb_pred);
726 free (augmenting_path->is_visited);
730 /* Queue routines. Assumes queue will never overflow. */
732 static void
733 init_queue (queue_type *queue_list)
735 gcc_assert (queue_list);
736 queue_list->head = 0;
737 queue_list->tail = 0;
740 /* Return true if QUEUE_LIST is empty. */
741 static bool
742 is_empty (queue_type *queue_list)
744 return (queue_list->head == queue_list->tail);
747 /* Insert element X into QUEUE_LIST. */
748 static void
749 enqueue (queue_type *queue_list, int x)
751 gcc_assert (queue_list->tail < queue_list->size);
752 queue_list->queue[queue_list->tail] = x;
753 (queue_list->tail)++;
756 /* Return the first element in QUEUE_LIST. */
757 static int
758 dequeue (queue_type *queue_list)
760 int x;
761 gcc_assert (queue_list->head >= 0);
762 x = queue_list->queue[queue_list->head];
763 (queue_list->head)++;
764 return x;
768 /* Finds a negative cycle in the residual network using
769 the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
770 minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
771 considered.
773 Parameters:
774 FIXUP_GRAPH - Residual graph (input/output)
775 The following are allocated/freed by the caller:
776 PI - Vector to hold predecessors in path (pi = pred index)
777 D - D[I] holds minimum cost of path from i to sink
778 CYCLE - Vector to hold the minimum cost cycle
780 Return:
781 true if a negative cycle was found, false otherwise. */
783 static bool
784 cancel_negative_cycle (fixup_graph_type *fixup_graph,
785 int *pi, gcov_type *d, int *cycle)
787 int i, j, k;
788 int fnum_vertices, fnum_edges;
789 fixup_edge_p fedge_list, pfedge, r_pfedge;
790 bool found_cycle = false;
791 int cycle_start = 0, cycle_end = 0;
792 gcov_type sum_cost = 0, cycle_flow = 0;
793 int new_entry_index;
794 bool propagated = false;
796 gcc_assert (fixup_graph);
797 fnum_vertices = fixup_graph->num_vertices;
798 fnum_edges = fixup_graph->num_edges;
799 fedge_list = fixup_graph->edge_list;
800 new_entry_index = fixup_graph->new_entry_index;
802 /* Initialize. */
803 /* Skip ENTRY. */
804 for (i = 1; i < fnum_vertices; i++)
806 d[i] = CAP_INFINITY;
807 pi[i] = -1;
808 cycle[i] = -1;
810 d[ENTRY_BLOCK] = 0;
812 /* Relax. */
813 for (k = 1; k < fnum_vertices; k++)
815 propagated = false;
816 for (i = 0; i < fnum_edges; i++)
818 pfedge = fedge_list + i;
819 if (pfedge->src == new_entry_index)
820 continue;
821 if (pfedge->is_rflow_valid && pfedge->rflow
822 && d[pfedge->src] != CAP_INFINITY
823 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
825 d[pfedge->dest] = d[pfedge->src] + pfedge->cost;
826 pi[pfedge->dest] = pfedge->src;
827 propagated = true;
830 if (!propagated)
831 break;
834 if (!propagated)
835 /* No negative cycles exist. */
836 return 0;
838 /* Detect. */
839 for (i = 0; i < fnum_edges; i++)
841 pfedge = fedge_list + i;
842 if (pfedge->src == new_entry_index)
843 continue;
844 if (pfedge->is_rflow_valid && pfedge->rflow
845 && d[pfedge->src] != CAP_INFINITY
846 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
848 found_cycle = true;
849 break;
853 if (!found_cycle)
854 return 0;
856 /* Augment the cycle with the cycle's minimum residual capacity. */
857 found_cycle = false;
858 cycle[0] = pfedge->dest;
859 j = pfedge->dest;
861 for (i = 1; i < fnum_vertices; i++)
863 j = pi[j];
864 cycle[i] = j;
865 for (k = 0; k < i; k++)
867 if (cycle[k] == j)
869 /* cycle[k] -> ... -> cycle[i]. */
870 cycle_start = k;
871 cycle_end = i;
872 found_cycle = true;
873 break;
876 if (found_cycle)
877 break;
880 gcc_assert (cycle[cycle_start] == cycle[cycle_end]);
881 if (dump_file)
882 fprintf (dump_file, "\nNegative cycle length is %d:\n",
883 cycle_end - cycle_start);
885 sum_cost = 0;
886 cycle_flow = CAP_INFINITY;
887 for (k = cycle_start; k < cycle_end; k++)
889 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
890 cycle_flow = MIN (cycle_flow, pfedge->rflow);
891 sum_cost += pfedge->cost;
892 if (dump_file)
893 fprintf (dump_file, "%d ", cycle[k]);
896 if (dump_file)
898 fprintf (dump_file, "%d", cycle[k]);
899 fprintf (dump_file,
900 ": (" HOST_WIDEST_INT_PRINT_DEC ", " HOST_WIDEST_INT_PRINT_DEC
901 ")\n", sum_cost, cycle_flow);
902 fprintf (dump_file,
903 "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC "\n",
904 cycle_flow);
907 for (k = cycle_start; k < cycle_end; k++)
909 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
910 r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]);
911 pfedge->rflow -= cycle_flow;
912 if (pfedge->type)
913 pfedge->flow += cycle_flow;
914 r_pfedge->rflow += cycle_flow;
915 if (r_pfedge->type)
916 r_pfedge->flow -= cycle_flow;
919 return true;
923 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
924 the edges. ENTRY and EXIT vertices should not be considered. */
926 static void
927 compute_residual_flow (fixup_graph_type *fixup_graph)
929 int i;
930 int fnum_edges;
931 fixup_edge_p fedge_list, pfedge;
933 gcc_assert (fixup_graph);
935 if (dump_file)
936 fputs ("\ncompute_residual_flow():\n", dump_file);
938 fnum_edges = fixup_graph->num_edges;
939 fedge_list = fixup_graph->edge_list;
941 for (i = 0; i < fnum_edges; i++)
943 pfedge = fedge_list + i;
944 pfedge->rflow = pfedge->max_capacity - pfedge->flow;
945 pfedge->is_rflow_valid = true;
946 add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow,
947 -pfedge->cost);
952 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
953 SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
954 this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
955 to reflect the path found.
956 Returns: 0 if no augmenting path is found, 1 otherwise. */
958 static int
959 find_augmenting_path (fixup_graph_type *fixup_graph,
960 augmenting_path_type *augmenting_path, int source,
961 int sink)
963 int u = 0;
964 int i;
965 fixup_vertex_p fvertex_list, pfvertex;
966 fixup_edge_p pfedge;
967 int *bb_pred, *is_visited;
968 queue_type *queue_list;
970 gcc_assert (augmenting_path);
971 bb_pred = augmenting_path->bb_pred;
972 gcc_assert (bb_pred);
973 is_visited = augmenting_path->is_visited;
974 gcc_assert (is_visited);
975 queue_list = &(augmenting_path->queue_list);
977 gcc_assert (fixup_graph);
979 fvertex_list = fixup_graph->vertex_list;
981 for (u = 0; u < fixup_graph->num_vertices; u++)
982 is_visited[u] = 0;
984 init_queue (queue_list);
985 enqueue (queue_list, source);
986 bb_pred[source] = -1;
988 while (!is_empty (queue_list))
990 u = dequeue (queue_list);
991 is_visited[u] = 1;
992 pfvertex = fvertex_list + u;
993 for (i = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, i, pfedge);
994 i++)
996 int dest = pfedge->dest;
997 if ((pfedge->rflow > 0) && (is_visited[dest] == 0))
999 enqueue (queue_list, dest);
1000 bb_pred[dest] = u;
1001 is_visited[dest] = 1;
1002 if (dest == sink)
1003 return 1;
1008 return 0;
1012 /* Routine to find the maximal flow:
1013 Algorithm:
1014 1. Initialize flow to 0
1015 2. Find an augmenting path form source to sink.
1016 3. Send flow equal to the path's residual capacity along the edges of this path.
1017 4. Repeat steps 2 and 3 until no new augmenting path is found.
1019 Parameters:
1020 SOURCE: index of source vertex (input)
1021 SINK: index of sink vertex (input)
1022 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1023 set to have a valid maximal flow by this routine. (input)
1024 Return: Maximum flow possible. */
1026 static gcov_type
1027 find_max_flow (fixup_graph_type *fixup_graph, int source, int sink)
1029 int fnum_edges;
1030 augmenting_path_type augmenting_path;
1031 int *bb_pred;
1032 gcov_type max_flow = 0;
1033 int i, u;
1034 fixup_edge_p fedge_list, pfedge, r_pfedge;
1036 gcc_assert (fixup_graph);
1038 fnum_edges = fixup_graph->num_edges;
1039 fedge_list = fixup_graph->edge_list;
1041 /* Initialize flow to 0. */
1042 for (i = 0; i < fnum_edges; i++)
1044 pfedge = fedge_list + i;
1045 pfedge->flow = 0;
1048 compute_residual_flow (fixup_graph);
1050 init_augmenting_path (&augmenting_path, fixup_graph->num_vertices);
1052 bb_pred = augmenting_path.bb_pred;
1053 while (find_augmenting_path (fixup_graph, &augmenting_path, source, sink))
1055 /* Determine the amount by which we can increment the flow. */
1056 gcov_type increment = CAP_INFINITY;
1057 for (u = sink; u != source; u = bb_pred[u])
1059 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1060 increment = MIN (increment, pfedge->rflow);
1062 max_flow += increment;
1064 /* Now increment the flow. EXIT vertex index is 1. */
1065 for (u = sink; u != source; u = bb_pred[u])
1067 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1068 r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]);
1069 if (pfedge->type)
1071 /* forward edge. */
1072 pfedge->flow += increment;
1073 pfedge->rflow -= increment;
1074 r_pfedge->rflow += increment;
1076 else
1078 /* backward edge. */
1079 gcc_assert (r_pfedge->type);
1080 r_pfedge->rflow += increment;
1081 r_pfedge->flow -= increment;
1082 pfedge->rflow -= increment;
1086 if (dump_file)
1088 fprintf (dump_file, "\nDump augmenting path:\n");
1089 for (u = sink; u != source; u = bb_pred[u])
1091 print_basic_block (dump_file, fixup_graph, u);
1092 fprintf (dump_file, "<-");
1094 fprintf (dump_file,
1095 "ENTRY (path_capacity=" HOST_WIDEST_INT_PRINT_DEC ")\n",
1096 increment);
1097 fprintf (dump_file,
1098 "Network flow is " HOST_WIDEST_INT_PRINT_DEC ".\n",
1099 max_flow);
1103 free_augmenting_path (&augmenting_path);
1104 if (dump_file)
1105 dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()");
1106 return max_flow;
1110 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1111 after applying the find_minimum_cost_flow() routine. */
1113 static void
1114 adjust_cfg_counts (fixup_graph_type *fixup_graph)
1116 basic_block bb;
1117 edge e;
1118 edge_iterator ei;
1119 int i, j;
1120 fixup_edge_p pfedge, pfedge_n;
1122 gcc_assert (fixup_graph);
1124 if (dump_file)
1125 fprintf (dump_file, "\nadjust_cfg_counts():\n");
1127 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1129 i = 2 * bb->index;
1131 /* Fixup BB. */
1132 if (dump_file)
1133 fprintf (dump_file,
1134 "BB%d: " HOST_WIDEST_INT_PRINT_DEC "", bb->index, bb->count);
1136 pfedge = find_fixup_edge (fixup_graph, i, i + 1);
1137 if (pfedge->flow)
1139 bb->count += pfedge->flow;
1140 if (dump_file)
1142 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1143 pfedge->flow);
1144 print_edge (dump_file, fixup_graph, i, i + 1);
1145 fprintf (dump_file, ")");
1149 pfedge_n =
1150 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1151 /* Deduct flow from normalized reverse edge. */
1152 if (pfedge->norm_vertex_index && pfedge_n->flow)
1154 bb->count -= pfedge_n->flow;
1155 if (dump_file)
1157 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
1158 pfedge_n->flow);
1159 print_edge (dump_file, fixup_graph, i + 1,
1160 pfedge->norm_vertex_index);
1161 fprintf (dump_file, ")");
1164 if (dump_file)
1165 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\n", bb->count);
1167 /* Fixup edge. */
1168 FOR_EACH_EDGE (e, ei, bb->succs)
1170 /* Treat edges with ignore attribute set as if they don't exist. */
1171 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1172 continue;
1174 j = 2 * e->dest->index;
1175 if (dump_file)
1176 fprintf (dump_file, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC "",
1177 bb->index, e->dest->index, e->count);
1179 pfedge = find_fixup_edge (fixup_graph, i + 1, j);
1181 if (bb->index != e->dest->index)
1183 /* Non-self edge. */
1184 if (pfedge->flow)
1186 e->count += pfedge->flow;
1187 if (dump_file)
1189 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1190 pfedge->flow);
1191 print_edge (dump_file, fixup_graph, i + 1, j);
1192 fprintf (dump_file, ")");
1196 pfedge_n =
1197 find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index);
1198 /* Deduct flow from normalized reverse edge. */
1199 if (pfedge->norm_vertex_index && pfedge_n->flow)
1201 e->count -= pfedge_n->flow;
1202 if (dump_file)
1204 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
1205 pfedge_n->flow);
1206 print_edge (dump_file, fixup_graph, j,
1207 pfedge->norm_vertex_index);
1208 fprintf (dump_file, ")");
1212 else
1214 /* Handle self edges. Self edge is split with a normalization
1215 vertex. Here i=j. */
1216 pfedge = find_fixup_edge (fixup_graph, j, i + 1);
1217 pfedge_n =
1218 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1219 e->count += pfedge_n->flow;
1220 bb->count += pfedge_n->flow;
1221 if (dump_file)
1223 fprintf (dump_file, "(self edge)");
1224 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
1225 pfedge_n->flow);
1226 print_edge (dump_file, fixup_graph, i + 1,
1227 pfedge->norm_vertex_index);
1228 fprintf (dump_file, ")");
1232 if (bb->count)
1233 e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1234 if (dump_file)
1235 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\t(%.1f%%)\n",
1236 e->count, e->probability * 100.0 / REG_BR_PROB_BASE);
1240 ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs);
1241 EXIT_BLOCK_PTR->count = sum_edge_counts (EXIT_BLOCK_PTR->preds);
1243 /* Compute edge probabilities. */
1244 FOR_ALL_BB (bb)
1246 if (bb->count)
1248 FOR_EACH_EDGE (e, ei, bb->succs)
1249 e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1251 else
1253 int total = 0;
1254 FOR_EACH_EDGE (e, ei, bb->succs)
1255 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1256 total++;
1257 if (total)
1259 FOR_EACH_EDGE (e, ei, bb->succs)
1261 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1262 e->probability = REG_BR_PROB_BASE / total;
1263 else
1264 e->probability = 0;
1267 else
1269 total += EDGE_COUNT (bb->succs);
1270 FOR_EACH_EDGE (e, ei, bb->succs)
1271 e->probability = REG_BR_PROB_BASE / total;
1276 if (dump_file)
1278 fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n",
1279 current_function_name ());
1280 FOR_EACH_BB (bb)
1282 if ((bb->count != sum_edge_counts (bb->preds))
1283 || (bb->count != sum_edge_counts (bb->succs)))
1285 fprintf (dump_file,
1286 "BB%d(" HOST_WIDEST_INT_PRINT_DEC ") **INVALID**: ",
1287 bb->index, bb->count);
1288 fprintf (stderr,
1289 "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC
1290 ") **INVALID**: \n", bb->index, bb->count);
1291 fprintf (dump_file, "in_edges=" HOST_WIDEST_INT_PRINT_DEC " ",
1292 sum_edge_counts (bb->preds));
1293 fprintf (dump_file, "out_edges=" HOST_WIDEST_INT_PRINT_DEC "\n",
1294 sum_edge_counts (bb->succs));
1301 /* Implements the negative cycle canceling algorithm to compute a minimum cost
1302 flow.
1303 Algorithm:
1304 1. Find maximal flow.
1305 2. Form residual network
1306 3. Repeat:
1307 While G contains a negative cost cycle C, reverse the flow on the found cycle
1308 by the minimum residual capacity in that cycle.
1309 4. Form the minimal cost flow
1310 f(u,v) = rf(v, u)
1311 Input:
1312 FIXUP_GRAPH - Initial fixup graph.
1313 The flow field is modified to represent the minimum cost flow. */
1315 static void
1316 find_minimum_cost_flow (fixup_graph_type *fixup_graph)
1318 /* Holds the index of predecessor in path. */
1319 int *pred;
1320 /* Used to hold the minimum cost cycle. */
1321 int *cycle;
1322 /* Used to record the number of iterations of cancel_negative_cycle. */
1323 int iteration;
1324 /* Vector d[i] holds the minimum cost of path from i to sink. */
1325 gcov_type *d;
1326 int fnum_vertices;
1327 int new_exit_index;
1328 int new_entry_index;
1330 gcc_assert (fixup_graph);
1331 fnum_vertices = fixup_graph->num_vertices;
1332 new_exit_index = fixup_graph->new_exit_index;
1333 new_entry_index = fixup_graph->new_entry_index;
1335 find_max_flow (fixup_graph, new_entry_index, new_exit_index);
1337 /* Initialize the structures for find_negative_cycle(). */
1338 pred = (int *) xcalloc (fnum_vertices, sizeof (int));
1339 d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type));
1340 cycle = (int *) xcalloc (fnum_vertices, sizeof (int));
1342 /* Repeatedly find and cancel negative cost cycles, until
1343 no more negative cycles exist. This also updates the flow field
1344 to represent the minimum cost flow so far. */
1345 iteration = 0;
1346 while (cancel_negative_cycle (fixup_graph, pred, d, cycle))
1348 iteration++;
1349 if (iteration > MAX_ITER (fixup_graph->num_vertices,
1350 fixup_graph->num_edges))
1351 break;
1354 if (dump_file)
1355 dump_fixup_graph (dump_file, fixup_graph,
1356 "After find_minimum_cost_flow()");
1358 /* Cleanup structures. */
1359 free (pred);
1360 free (d);
1361 free (cycle);
1365 /* Compute the sum of the edge counts in TO_EDGES. */
1367 gcov_type
1368 sum_edge_counts (VEC (edge, gc) *to_edges)
1370 gcov_type sum = 0;
1371 edge e;
1372 edge_iterator ei;
1374 FOR_EACH_EDGE (e, ei, to_edges)
1376 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1377 continue;
1378 sum += e->count;
1380 return sum;
1384 /* Main routine. Smoothes the initial assigned basic block and edge counts using
1385 a minimum cost flow algorithm, to ensure that the flow consistency rule is
1386 obeyed: sum of outgoing edges = sum of incoming edges for each basic
1387 block. */
1389 void
1390 mcf_smooth_cfg (void)
1392 fixup_graph_type fixup_graph;
1393 memset (&fixup_graph, 0, sizeof (fixup_graph));
1394 create_fixup_graph (&fixup_graph);
1395 find_minimum_cost_flow (&fixup_graph);
1396 adjust_cfg_counts (&fixup_graph);
1397 delete_fixup_graph (&fixup_graph);