Add "device uether" to various manual pages' synopses.
[dragonfly.git] / contrib / gcc-5.0 / gcc / mcf.c
blob9dacde2d783dff2646d79c00ece4b56ee7853704
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
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 "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
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
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
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
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
136 int *queue;
137 int head;
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
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)
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
177 fprintf (file, "%d", n / 2);
178 if (n % 2)
179 fputs ("''", file);
180 else
181 fputs ("'", file);
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)
195 print_basic_block (file, fixup_graph, s);
196 fputs ("->", file);
197 print_basic_block (file, fixup_graph, d);
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)
206 if (!fedge)
208 fputs ("NULL fixup graph edge.\n", file);
209 return;
212 print_edge (file, fixup_graph, fedge->src, fedge->dest);
213 fputs (": ", file);
215 if (fedge->type)
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);
225 if (fedge->is_rflow_valid)
227 if (fedge->rflow == CAP_INFINITY)
228 fputs (" rflow=+oo.", file);
229 else
230 fprintf (file, " rflow=%" PRId64 ",", fedge->rflow);
233 fprintf (file, " cost=%" PRId64 ".", fedge->cost);
235 fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest);
237 if (fedge->type)
239 switch (fedge->type)
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;
275 fputs ("\n", file);
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)
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++)
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++)
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);
321 fputs ("\n", file);
325 /* Utility routines. */
326 /* ln() implementation: approximate calculation. Returns ln of X. */
328 static double
329 mcf_ln (double x)
331 #define E 2.71828
332 int l = 1;
333 double m = E;
335 gcc_assert (x >= 0);
337 while (m < x)
339 m *= E;
340 l++;
343 return l;
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)
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));
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)
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;
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)
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;
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)
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;
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)
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;
444 /* Cleanup routine to free structures in FIXUP_GRAPH. */
446 static void
447 delete_fixup_graph (fixup_graph_type *fixup_graph)
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);
461 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
463 static void
464 create_fixup_graph (fixup_graph_type *fixup_graph)
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)
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)
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);
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++)
569 pfedge = fixup_graph->edge_list + i;
570 diff_out_in[pfedge->src] += pfedge->weight;
571 diff_out_in[pfedge->dest] -= pfedge->weight;
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++)
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)
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);
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)
622 if (diff_out_in[i] > 0)
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];
628 else if (diff_out_in[i] < 0)
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];
636 /* Set supply = demand. */
637 if (dump_file)
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);
646 if (demand_value > supply_value)
648 pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK);
649 pfedge->max_capacity += (demand_value - supply_value);
651 else
653 pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index);
654 pfedge->max_capacity += (supply_value - demand_value);
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++)
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)
673 new_index = fixup_graph->num_vertices;
674 fixup_graph->num_vertices++;
676 if (dump_file)
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");
685 pfedge->cost /= 2;
686 pfedge->norm_vertex_index = new_index;
687 if (dump_file)
689 fprintf (dump_file, "After normalization:\n");
690 dump_fixup_edge (dump_file, fixup_graph, pfedge);
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);
710 if (dump_file)
711 dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()");
713 /* Cleanup. */
714 free (diff_out_in);
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)
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));
732 /* Free the structures in AUGMENTING_PATH. */
733 static void
734 free_augmenting_path (augmenting_path_type *augmenting_path)
736 free (augmenting_path->queue_list.queue);
737 free (augmenting_path->bb_pred);
738 free (augmenting_path->is_visited);
742 /* Queue routines. Assumes queue will never overflow. */
744 static void
745 init_queue (queue_type *queue_list)
747 gcc_assert (queue_list);
748 queue_list->head = 0;
749 queue_list->tail = 0;
752 /* Return true if QUEUE_LIST is empty. */
753 static bool
754 is_empty (queue_type *queue_list)
756 return (queue_list->head == queue_list->tail);
759 /* Insert element X into QUEUE_LIST. */
760 static void
761 enqueue (queue_type *queue_list, int x)
763 gcc_assert (queue_list->tail < queue_list->size);
764 queue_list->queue[queue_list->tail] = x;
765 (queue_list->tail)++;
768 /* Return the first element in QUEUE_LIST. */
769 static int
770 dequeue (queue_type *queue_list)
772 int x;
773 gcc_assert (queue_list->head >= 0);
774 x = queue_list->queue[queue_list->head];
775 (queue_list->head)++;
776 return x;
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)
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++)
818 d[i] = CAP_INFINITY;
819 pi[i] = -1;
820 cycle[i] = -1;
822 d[ENTRY_BLOCK] = 0;
824 /* Relax. */
825 for (k = 1; k < fnum_vertices; k++)
827 propagated = false;
828 for (i = 0; i < fnum_edges; i++)
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))
837 d[pfedge->dest] = d[pfedge->src] + pfedge->cost;
838 pi[pfedge->dest] = pfedge->src;
839 propagated = true;
842 if (!propagated)
843 break;
846 if (!propagated)
847 /* No negative cycles exist. */
848 return 0;
850 /* Detect. */
851 for (i = 0; i < fnum_edges; i++)
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))
860 found_cycle = true;
861 break;
865 if (!found_cycle)
866 return 0;
868 /* Augment the cycle with the cycle's minimum residual capacity. */
869 found_cycle = false;
870 cycle[0] = pfedge->dest;
871 j = pfedge->dest;
873 for (i = 1; i < fnum_vertices; i++)
875 j = pi[j];
876 cycle[i] = j;
877 for (k = 0; k < i; k++)
879 if (cycle[k] == j)
881 /* cycle[k] -> ... -> cycle[i]. */
882 cycle_start = k;
883 cycle_end = i;
884 found_cycle = true;
885 break;
888 if (found_cycle)
889 break;
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++)
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]);
908 if (dump_file)
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);
919 for (k = cycle_start; k < cycle_end; k++)
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;
931 return true;
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)
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++)
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);
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)
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))
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++)
1008 int dest = pfedge->dest;
1009 if ((pfedge->rflow > 0) && (is_visited[dest] == 0))
1011 enqueue (queue_list, dest);
1012 bb_pred[dest] = u;
1013 is_visited[dest] = 1;
1014 if (dest == sink)
1015 return 1;
1020 return 0;
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)
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++)
1056 pfedge = fedge_list + i;
1057 pfedge->flow = 0;
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))
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])
1071 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1072 increment = MIN (increment, pfedge->rflow);
1074 max_flow += increment;
1076 /* Now increment the flow. EXIT vertex index is 1. */
1077 for (u = sink; u != source; u = bb_pred[u])
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)
1083 /* forward edge. */
1084 pfedge->flow += increment;
1085 pfedge->rflow -= increment;
1086 r_pfedge->rflow += increment;
1088 else
1090 /* backward edge. */
1091 gcc_assert (r_pfedge->type);
1092 r_pfedge->rflow += increment;
1093 r_pfedge->flow -= increment;
1094 pfedge->rflow -= increment;
1098 if (dump_file)
1100 fprintf (dump_file, "\nDump augmenting path:\n");
1101 for (u = sink; u != source; u = bb_pred[u])
1103 print_basic_block (dump_file, fixup_graph, u);
1104 fprintf (dump_file, "<-");
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);
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;
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)
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)
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)
1152 bb->count += pfedge->flow;
1153 if (dump_file)
1155 fprintf (dump_file, " + %" PRId64 "(",
1156 pfedge->flow);
1157 print_edge (dump_file, fixup_graph, i, i + 1);
1158 fprintf (dump_file, ")");
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)
1167 bb->count -= pfedge_n->flow;
1168 if (dump_file)
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, ")");
1177 if (dump_file)
1178 fprintf (dump_file, " = %" PRId64 "\n", bb->count);
1180 /* Fixup edge. */
1181 FOR_EACH_EDGE (e, ei, bb->succs)
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)
1196 /* Non-self edge. */
1197 if (pfedge->flow)
1199 e->count += pfedge->flow;
1200 if (dump_file)
1202 fprintf (dump_file, " + %" PRId64 "(",
1203 pfedge->flow);
1204 print_edge (dump_file, fixup_graph, i + 1, j);
1205 fprintf (dump_file, ")");
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)
1214 e->count -= pfedge_n->flow;
1215 if (dump_file)
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, ")");
1225 else
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)
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, ")");
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);
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)
1261 if (bb->count)
1263 FOR_EACH_EDGE (e, ei, bb->succs)
1264 e->probability = REG_BR_PROB_BASE * e->count / bb->count;
1266 else
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)
1274 FOR_EACH_EDGE (e, ei, bb->succs)
1276 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1277 e->probability = REG_BR_PROB_BASE / total;
1278 else
1279 e->probability = 0;
1282 else
1284 total += EDGE_COUNT (bb->succs);
1285 FOR_EACH_EDGE (e, ei, bb->succs)
1286 e->probability = REG_BR_PROB_BASE / total;
1291 if (dump_file)
1293 fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n",
1294 current_function_name ());
1295 FOR_EACH_BB_FN (bb, cfun)
1297 if ((bb->count != sum_edge_counts (bb->preds))
1298 || (bb->count != sum_edge_counts (bb->succs)))
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));
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)
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))
1363 iteration++;
1364 if (iteration > MAX_ITER (fixup_graph->num_vertices,
1365 fixup_graph->num_edges))
1366 break;
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);
1380 /* Compute the sum of the edge counts in TO_EDGES. */
1382 gcov_type
1383 sum_edge_counts (vec<edge, va_gc> *to_edges)
1385 gcov_type sum = 0;
1386 edge e;
1387 edge_iterator ei;
1389 FOR_EACH_EDGE (e, ei, to_edges)
1391 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1392 continue;
1393 sum += e->count;
1395 return sum;
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)
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);
1411 adjust_cfg_counts (&fixup_graph);
1412 delete_fixup_graph (&fixup_graph);