Branch data Line data Source code
1 : : /* Routines to implement minimum-cost maximal flow algorithm used to smooth
2 : : basic block and edge frequency counts.
3 : : Copyright (C) 2008-2024 Free Software Foundation, Inc.
4 : : Contributed by Paul Yuan (yingbo.com@gmail.com) and
5 : : Vinodha Ramasamy (vinodha@google.com).
6 : :
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.
12 : :
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.
17 : :
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/>. */
21 : :
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.
29 : :
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). */
44 : :
45 : : #include "config.h"
46 : : #include "system.h"
47 : : #include "coretypes.h"
48 : : #include "backend.h"
49 : : #include "profile.h"
50 : : #include "dumpfile.h"
51 : :
52 : : /* CAP_INFINITY: Constant to represent infinite capacity. */
53 : : #define CAP_INFINITY INTTYPE_MAXIMUM (int64_t)
54 : :
55 : : /* COST FUNCTION. */
56 : : #define K_POS(b) ((b))
57 : : #define K_NEG(b) (50 * (b))
58 : : #define COST(k, w) ((k) / mcf_ln ((w) + 2))
59 : : /* Limit the number of iterations for cancel_negative_cycles() to ensure
60 : : reasonable compile time. */
61 : : #define MAX_ITER(n, e) 10 + (1000000 / ((n) * (e)))
62 : : enum edge_type
63 : : {
64 : : INVALID_EDGE,
65 : : VERTEX_SPLIT_EDGE, /* Edge to represent vertex with w(e) = w(v). */
66 : : REDIRECT_EDGE, /* Edge after vertex transformation. */
67 : : REVERSE_EDGE,
68 : : SOURCE_CONNECT_EDGE, /* Single edge connecting to single source. */
69 : : SINK_CONNECT_EDGE, /* Single edge connecting to single sink. */
70 : : BALANCE_EDGE, /* Edge connecting with source/sink: cp(e) = 0. */
71 : : REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge. */
72 : : REVERSE_NORMALIZED_EDGE /* Normalized edge for a reverse edge. */
73 : : };
74 : :
75 : : /* Structure to represent an edge in the fixup graph. */
76 : : struct fixup_edge_type
77 : : {
78 : : int src;
79 : : int dest;
80 : : /* Flag denoting type of edge and attributes for the flow field. */
81 : : edge_type type;
82 : : bool is_rflow_valid;
83 : : /* Index to the normalization vertex added for this edge. */
84 : : int norm_vertex_index;
85 : : /* Flow for this edge. */
86 : : gcov_type flow;
87 : : /* Residual flow for this edge - used during negative cycle canceling. */
88 : : gcov_type rflow;
89 : : gcov_type weight;
90 : : gcov_type cost;
91 : : gcov_type max_capacity;
92 : : };
93 : :
94 : : typedef fixup_edge_type *fixup_edge_p;
95 : :
96 : :
97 : : /* Structure to represent a vertex in the fixup graph. */
98 : : struct fixup_vertex_type
99 : : {
100 : : vec<fixup_edge_p> succ_edges;
101 : : };
102 : :
103 : : typedef fixup_vertex_type *fixup_vertex_p;
104 : :
105 : : /* Fixup graph used in the MCF algorithm. */
106 : : struct fixup_graph_type
107 : : {
108 : : /* Current number of vertices for the graph. */
109 : : int num_vertices;
110 : : /* Current number of edges for the graph. */
111 : : int num_edges;
112 : : /* Index of new entry vertex. */
113 : : int new_entry_index;
114 : : /* Index of new exit vertex. */
115 : : int new_exit_index;
116 : : /* Fixup vertex list. Adjacency list for fixup graph. */
117 : : fixup_vertex_p vertex_list;
118 : : /* Fixup edge list. */
119 : : fixup_edge_p edge_list;
120 : : };
121 : :
122 : : struct queue_type
123 : : {
124 : : int *queue;
125 : : int head;
126 : : int tail;
127 : : int size;
128 : : };
129 : :
130 : : /* Structure used in the maximal flow routines to find augmenting path. */
131 : : struct augmenting_path_type
132 : : {
133 : : /* Queue used to hold vertex indices. */
134 : : queue_type queue_list;
135 : : /* Vector to hold chain of pred vertex indices in augmenting path. */
136 : : int *bb_pred;
137 : : /* Vector that indicates if basic block i has been visited. */
138 : : int *is_visited;
139 : : };
140 : :
141 : :
142 : : /* Function definitions. */
143 : :
144 : : /* Dump routines to aid debugging. */
145 : :
146 : : /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */
147 : :
148 : : static void
149 : 0 : print_basic_block (FILE *file, fixup_graph_type *fixup_graph, int n)
150 : : {
151 : 0 : if (n == ENTRY_BLOCK)
152 : 0 : fputs ("ENTRY", file);
153 : 0 : else if (n == ENTRY_BLOCK + 1)
154 : 0 : fputs ("ENTRY''", file);
155 : 0 : else if (n == 2 * EXIT_BLOCK)
156 : 0 : fputs ("EXIT", file);
157 : 0 : else if (n == 2 * EXIT_BLOCK + 1)
158 : 0 : fputs ("EXIT''", file);
159 : 0 : else if (n == fixup_graph->new_exit_index)
160 : 0 : fputs ("NEW_EXIT", file);
161 : 0 : else if (n == fixup_graph->new_entry_index)
162 : 0 : fputs ("NEW_ENTRY", file);
163 : : else
164 : : {
165 : 0 : fprintf (file, "%d", n / 2);
166 : 0 : if (n % 2)
167 : 0 : fputs ("''", file);
168 : : else
169 : 0 : fputs ("'", file);
170 : : }
171 : 0 : }
172 : :
173 : :
174 : : /* Print edge S->D for given fixup_graph with n' and n'' format.
175 : : PARAMETERS:
176 : : S is the index of the source vertex of the edge (input) and
177 : : D is the index of the destination vertex of the edge (input) for the given
178 : : fixup_graph (input). */
179 : :
180 : : static void
181 : 0 : print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d)
182 : : {
183 : 0 : print_basic_block (file, fixup_graph, s);
184 : 0 : fputs ("->", file);
185 : 0 : print_basic_block (file, fixup_graph, d);
186 : 0 : }
187 : :
188 : :
189 : : /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
190 : : file. */
191 : : static void
192 : 0 : dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge)
193 : : {
194 : 0 : if (!fedge)
195 : : {
196 : 0 : fputs ("NULL fixup graph edge.\n", file);
197 : 0 : return;
198 : : }
199 : :
200 : 0 : print_edge (file, fixup_graph, fedge->src, fedge->dest);
201 : 0 : fputs (": ", file);
202 : :
203 : 0 : if (fedge->type)
204 : : {
205 : 0 : fprintf (file, "flow/capacity=%" PRId64 "/",
206 : : fedge->flow);
207 : 0 : if (fedge->max_capacity == CAP_INFINITY)
208 : 0 : fputs ("+oo,", file);
209 : : else
210 : 0 : fprintf (file, "%" PRId64 ",", fedge->max_capacity);
211 : : }
212 : :
213 : 0 : if (fedge->is_rflow_valid)
214 : : {
215 : 0 : if (fedge->rflow == CAP_INFINITY)
216 : 0 : fputs (" rflow=+oo.", file);
217 : : else
218 : 0 : fprintf (file, " rflow=%" PRId64 ",", fedge->rflow);
219 : : }
220 : :
221 : 0 : fprintf (file, " cost=%" PRId64 ".", fedge->cost);
222 : :
223 : 0 : fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest);
224 : :
225 : 0 : if (fedge->type)
226 : : {
227 : 0 : switch (fedge->type)
228 : : {
229 : 0 : case VERTEX_SPLIT_EDGE:
230 : 0 : fputs (" @VERTEX_SPLIT_EDGE", file);
231 : 0 : break;
232 : :
233 : 0 : case REDIRECT_EDGE:
234 : 0 : fputs (" @REDIRECT_EDGE", file);
235 : 0 : break;
236 : :
237 : 0 : case SOURCE_CONNECT_EDGE:
238 : 0 : fputs (" @SOURCE_CONNECT_EDGE", file);
239 : 0 : break;
240 : :
241 : 0 : case SINK_CONNECT_EDGE:
242 : 0 : fputs (" @SINK_CONNECT_EDGE", file);
243 : 0 : break;
244 : :
245 : 0 : case REVERSE_EDGE:
246 : 0 : fputs (" @REVERSE_EDGE", file);
247 : 0 : break;
248 : :
249 : 0 : case BALANCE_EDGE:
250 : 0 : fputs (" @BALANCE_EDGE", file);
251 : 0 : break;
252 : :
253 : 0 : case REDIRECT_NORMALIZED_EDGE:
254 : 0 : case REVERSE_NORMALIZED_EDGE:
255 : 0 : fputs (" @NORMALIZED_EDGE", file);
256 : 0 : break;
257 : :
258 : 0 : default:
259 : 0 : fputs (" @INVALID_EDGE", file);
260 : 0 : break;
261 : : }
262 : : }
263 : 0 : fputs ("\n", file);
264 : : }
265 : :
266 : :
267 : : /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
268 : : file. The input string MSG is printed out as a heading. */
269 : :
270 : : static void
271 : 0 : dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg)
272 : : {
273 : 0 : int i, j;
274 : 0 : int fnum_vertices, fnum_edges;
275 : :
276 : 0 : fixup_vertex_p fvertex_list, pfvertex;
277 : 0 : fixup_edge_p pfedge;
278 : :
279 : 0 : gcc_assert (fixup_graph);
280 : 0 : fvertex_list = fixup_graph->vertex_list;
281 : 0 : fnum_vertices = fixup_graph->num_vertices;
282 : 0 : fnum_edges = fixup_graph->num_edges;
283 : :
284 : 0 : fprintf (file, "\nDump fixup graph for %s(): %s.\n",
285 : : current_function_name (), msg);
286 : 0 : fprintf (file,
287 : : "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
288 : : fnum_vertices, fnum_edges, fixup_graph->new_exit_index);
289 : :
290 : 0 : for (i = 0; i < fnum_vertices; i++)
291 : : {
292 : 0 : pfvertex = fvertex_list + i;
293 : 0 : fprintf (file, "vertex_list[%d]: %d succ fixup edges.\n",
294 : : i, pfvertex->succ_edges.length ());
295 : :
296 : 0 : for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge);
297 : : j++)
298 : : {
299 : : /* Distinguish forward edges and backward edges in the residual flow
300 : : network. */
301 : 0 : if (pfedge->type)
302 : 0 : fputs ("(f) ", file);
303 : 0 : else if (pfedge->is_rflow_valid)
304 : 0 : fputs ("(b) ", file);
305 : 0 : dump_fixup_edge (file, fixup_graph, pfedge);
306 : : }
307 : : }
308 : :
309 : 0 : fputs ("\n", file);
310 : 0 : }
311 : :
312 : :
313 : : /* Utility routines. */
314 : : /* ln() implementation: approximate calculation. Returns ln of X. */
315 : :
316 : : static double
317 : 0 : mcf_ln (double x)
318 : : {
319 : : #define E 2.71828
320 : 0 : int l = 1;
321 : 0 : double m = E;
322 : :
323 : 0 : gcc_assert (x >= 0);
324 : :
325 : 0 : while (m < x)
326 : : {
327 : 0 : m *= E;
328 : 0 : l++;
329 : : }
330 : :
331 : 0 : return l;
332 : : }
333 : :
334 : :
335 : : /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
336 : : implementation) by John Carmack. Returns sqrt of X. */
337 : :
338 : : static double
339 : 0 : mcf_sqrt (double x)
340 : : {
341 : : #define MAGIC_CONST1 0x1fbcf800
342 : : #define MAGIC_CONST2 0x5f3759df
343 : 0 : union {
344 : : int intPart;
345 : : float floatPart;
346 : : } convertor, convertor2;
347 : :
348 : 0 : gcc_assert (x >= 0);
349 : :
350 : 0 : convertor.floatPart = x;
351 : 0 : convertor2.floatPart = x;
352 : 0 : convertor.intPart = MAGIC_CONST1 + (convertor.intPart >> 1);
353 : 0 : convertor2.intPart = MAGIC_CONST2 - (convertor2.intPart >> 1);
354 : :
355 : 0 : return 0.5f * (convertor.floatPart + (x * convertor2.floatPart));
356 : : }
357 : :
358 : :
359 : : /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
360 : : (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
361 : : added set to COST. */
362 : :
363 : : static fixup_edge_p
364 : 0 : add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost)
365 : : {
366 : 0 : fixup_vertex_p curr_vertex = fixup_graph->vertex_list + src;
367 : 0 : fixup_edge_p curr_edge = fixup_graph->edge_list + fixup_graph->num_edges;
368 : 0 : curr_edge->src = src;
369 : 0 : curr_edge->dest = dest;
370 : 0 : curr_edge->cost = cost;
371 : 0 : fixup_graph->num_edges++;
372 : 0 : if (dump_file)
373 : 0 : dump_fixup_edge (dump_file, fixup_graph, curr_edge);
374 : 0 : curr_vertex->succ_edges.safe_push (curr_edge);
375 : 0 : return curr_edge;
376 : : }
377 : :
378 : :
379 : : /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
380 : : MAX_CAPACITY to the edge_list in the fixup graph. */
381 : :
382 : : static void
383 : 0 : add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
384 : : edge_type type, gcov_type weight, gcov_type cost,
385 : : gcov_type max_capacity)
386 : : {
387 : 0 : fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost);
388 : 0 : curr_edge->type = type;
389 : 0 : curr_edge->weight = weight;
390 : 0 : curr_edge->max_capacity = max_capacity;
391 : 0 : }
392 : :
393 : :
394 : : /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
395 : : to the fixup graph. */
396 : :
397 : : static void
398 : 0 : add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
399 : : gcov_type rflow, gcov_type cost)
400 : : {
401 : 0 : fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost);
402 : 0 : curr_edge->rflow = rflow;
403 : 0 : curr_edge->is_rflow_valid = true;
404 : : /* This edge is not a valid edge - merely used to hold residual flow. */
405 : 0 : curr_edge->type = INVALID_EDGE;
406 : 0 : }
407 : :
408 : :
409 : : /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
410 : : exist in the FIXUP_GRAPH. */
411 : :
412 : : static fixup_edge_p
413 : 0 : find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest)
414 : : {
415 : 0 : int j;
416 : 0 : fixup_edge_p pfedge;
417 : 0 : fixup_vertex_p pfvertex;
418 : :
419 : 0 : gcc_assert (src < fixup_graph->num_vertices);
420 : :
421 : 0 : pfvertex = fixup_graph->vertex_list + src;
422 : :
423 : 0 : for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge);
424 : : j++)
425 : 0 : if (pfedge->dest == dest)
426 : 0 : return pfedge;
427 : :
428 : : return NULL;
429 : : }
430 : :
431 : :
432 : : /* Cleanup routine to free structures in FIXUP_GRAPH. */
433 : :
434 : : static void
435 : 0 : delete_fixup_graph (fixup_graph_type *fixup_graph)
436 : : {
437 : 0 : int i;
438 : 0 : int fnum_vertices = fixup_graph->num_vertices;
439 : 0 : fixup_vertex_p pfvertex = fixup_graph->vertex_list;
440 : :
441 : 0 : for (i = 0; i < fnum_vertices; i++, pfvertex++)
442 : 0 : pfvertex->succ_edges.release ();
443 : :
444 : 0 : free (fixup_graph->vertex_list);
445 : 0 : free (fixup_graph->edge_list);
446 : 0 : }
447 : :
448 : :
449 : : /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
450 : :
451 : : static void
452 : 0 : create_fixup_graph (fixup_graph_type *fixup_graph)
453 : : {
454 : 0 : double sqrt_avg_vertex_weight = 0;
455 : 0 : double total_vertex_weight = 0;
456 : 0 : double k_pos = 0;
457 : 0 : double k_neg = 0;
458 : : /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */
459 : 0 : gcov_type *diff_out_in = NULL;
460 : 0 : gcov_type supply_value = 1, demand_value = 0;
461 : 0 : gcov_type fcost = 0;
462 : 0 : int new_entry_index = 0, new_exit_index = 0;
463 : 0 : int i = 0, j = 0;
464 : 0 : int new_index = 0;
465 : 0 : basic_block bb;
466 : 0 : edge e;
467 : 0 : edge_iterator ei;
468 : 0 : fixup_edge_p pfedge, r_pfedge;
469 : 0 : fixup_edge_p fedge_list;
470 : 0 : int fnum_edges;
471 : :
472 : : /* Each basic_block will be split into 2 during vertex transformation. */
473 : 0 : int fnum_vertices_after_transform = 2 * n_basic_blocks_for_fn (cfun);
474 : 0 : int fnum_edges_after_transform =
475 : 0 : n_edges_for_fn (cfun) + n_basic_blocks_for_fn (cfun);
476 : :
477 : : /* Count the new SOURCE and EXIT vertices to be added. */
478 : 0 : int fmax_num_vertices =
479 : 0 : (fnum_vertices_after_transform + n_edges_for_fn (cfun)
480 : 0 : + n_basic_blocks_for_fn (cfun) + 2);
481 : :
482 : : /* In create_fixup_graph: Each basic block and edge can be split into 3
483 : : edges. Number of balance edges = n_basic_blocks. So after
484 : : create_fixup_graph:
485 : : max_edges = 4 * n_basic_blocks + 3 * n_edges
486 : : Accounting for residual flow edges
487 : : max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
488 : : = 8 * n_basic_blocks + 6 * n_edges
489 : : < 8 * n_basic_blocks + 8 * n_edges. */
490 : 0 : int fmax_num_edges = 8 * (n_basic_blocks_for_fn (cfun) +
491 : : n_edges_for_fn (cfun));
492 : :
493 : : /* Initial num of vertices in the fixup graph. */
494 : 0 : fixup_graph->num_vertices = n_basic_blocks_for_fn (cfun);
495 : :
496 : : /* Fixup graph vertex list. */
497 : 0 : fixup_graph->vertex_list =
498 : 0 : (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type));
499 : :
500 : : /* Fixup graph edge list. */
501 : 0 : fixup_graph->edge_list =
502 : 0 : (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type));
503 : :
504 : 0 : diff_out_in =
505 : 0 : (gcov_type *) xcalloc (1 + fnum_vertices_after_transform,
506 : : sizeof (gcov_type));
507 : :
508 : : /* Compute constants b, k_pos, k_neg used in the cost function calculation.
509 : : b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */
510 : 0 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
511 : 0 : total_vertex_weight += bb_gcov_count (bb);
512 : :
513 : 0 : sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight /
514 : 0 : n_basic_blocks_for_fn (cfun));
515 : :
516 : 0 : k_pos = K_POS (sqrt_avg_vertex_weight);
517 : 0 : k_neg = K_NEG (sqrt_avg_vertex_weight);
518 : :
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). */
521 : :
522 : 0 : if (dump_file)
523 : 0 : fprintf (dump_file, "\nVertex transformation:\n");
524 : :
525 : 0 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
526 : : {
527 : : /* v'->v'': index1->(index1+1). */
528 : 0 : i = 2 * bb->index;
529 : 0 : fcost = (gcov_type) COST (k_pos, bb_gcov_count (bb));
530 : 0 : add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb_gcov_count (bb),
531 : : fcost, CAP_INFINITY);
532 : 0 : fixup_graph->num_vertices++;
533 : :
534 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
535 : : {
536 : : /* Edges with ignore attribute set should be treated like they don't
537 : : exist. */
538 : 0 : if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
539 : 0 : continue;
540 : 0 : j = 2 * e->dest->index;
541 : 0 : fcost = (gcov_type) COST (k_pos, edge_gcov_count (e));
542 : 0 : add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, edge_gcov_count (e),
543 : : fcost, CAP_INFINITY);
544 : : }
545 : : }
546 : :
547 : : /* After vertex transformation. */
548 : 0 : gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform);
549 : : /* Redirect edges are not added for edges with ignore attribute. */
550 : 0 : gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform);
551 : :
552 : 0 : fnum_edges_after_transform = fixup_graph->num_edges;
553 : :
554 : : /* 2. Initialize D(v). */
555 : 0 : for (i = 0; i < fnum_edges_after_transform; i++)
556 : : {
557 : 0 : pfedge = fixup_graph->edge_list + i;
558 : 0 : diff_out_in[pfedge->src] += pfedge->weight;
559 : 0 : diff_out_in[pfedge->dest] -= pfedge->weight;
560 : : }
561 : :
562 : : /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */
563 : 0 : for (i = 0; i <= 3; i++)
564 : 0 : diff_out_in[i] = 0;
565 : :
566 : : /* 3. Add reverse edges: needed to decrease counts during smoothing. */
567 : 0 : if (dump_file)
568 : 0 : fprintf (dump_file, "\nReverse edges:\n");
569 : 0 : for (i = 0; i < fnum_edges_after_transform; i++)
570 : : {
571 : 0 : pfedge = fixup_graph->edge_list + i;
572 : 0 : if ((pfedge->src == 0) || (pfedge->src == 2))
573 : 0 : continue;
574 : 0 : r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
575 : 0 : if (!r_pfedge && pfedge->weight)
576 : : {
577 : : /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
578 : : capacity is 0. */
579 : 0 : fcost = (gcov_type) COST (k_neg, pfedge->weight);
580 : 0 : add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src,
581 : : REVERSE_EDGE, 0, fcost, pfedge->weight);
582 : : }
583 : : }
584 : :
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 : 0 : if (dump_file)
588 : 0 : fprintf (dump_file, "\ns'->S, T->t':\n");
589 : :
590 : 0 : new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices;
591 : 0 : fixup_graph->num_vertices++;
592 : : /* Set supply_value to 1 to avoid zero count function ENTRY. */
593 : 0 : add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE,
594 : : 1 /* supply_value */, 0, 1 /* supply_value */);
595 : :
596 : : /* Create new exit with EXIT_BLOCK as single pred. */
597 : 0 : new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices;
598 : 0 : fixup_graph->num_vertices++;
599 : 0 : add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index,
600 : : SINK_CONNECT_EDGE,
601 : : 0 /* demand_value */, 0, 0 /* demand_value */);
602 : :
603 : : /* Connect vertices with unbalanced D(v) to source/sink. */
604 : 0 : if (dump_file)
605 : 0 : 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 : 0 : for (i = 4; i < new_entry_index; i += 2)
609 : : {
610 : 0 : if (diff_out_in[i] > 0)
611 : : {
612 : 0 : add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0,
613 : : diff_out_in[i]);
614 : 0 : demand_value += diff_out_in[i];
615 : : }
616 : 0 : else if (diff_out_in[i] < 0)
617 : : {
618 : 0 : add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0,
619 : : -diff_out_in[i]);
620 : 0 : supply_value -= diff_out_in[i];
621 : : }
622 : : }
623 : :
624 : : /* Set supply = demand. */
625 : 0 : if (dump_file)
626 : : {
627 : 0 : fprintf (dump_file, "\nAdjust supply and demand:\n");
628 : 0 : fprintf (dump_file, "supply_value=%" PRId64 "\n",
629 : : supply_value);
630 : 0 : fprintf (dump_file, "demand_value=%" PRId64 "\n",
631 : : demand_value);
632 : : }
633 : :
634 : 0 : if (demand_value > supply_value)
635 : : {
636 : 0 : pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK);
637 : 0 : pfedge->max_capacity += (demand_value - supply_value);
638 : : }
639 : : else
640 : : {
641 : 0 : pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index);
642 : 0 : pfedge->max_capacity += (supply_value - demand_value);
643 : : }
644 : :
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 : 0 : if (dump_file)
649 : 0 : fprintf (dump_file, "\nNormalize edges:\n");
650 : :
651 : 0 : fnum_edges = fixup_graph->num_edges;
652 : 0 : fedge_list = fixup_graph->edge_list;
653 : :
654 : 0 : for (i = 0; i < fnum_edges; i++)
655 : : {
656 : 0 : pfedge = fedge_list + i;
657 : 0 : r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
658 : 0 : if (((pfedge->type == VERTEX_SPLIT_EDGE)
659 : 0 : || (pfedge->type == REDIRECT_EDGE)) && r_pfedge)
660 : : {
661 : 0 : new_index = fixup_graph->num_vertices;
662 : 0 : fixup_graph->num_vertices++;
663 : :
664 : 0 : if (dump_file)
665 : : {
666 : 0 : fprintf (dump_file, "\nAnti-parallel edge:\n");
667 : 0 : dump_fixup_edge (dump_file, fixup_graph, pfedge);
668 : 0 : dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
669 : 0 : fprintf (dump_file, "New vertex is %d.\n", new_index);
670 : 0 : fprintf (dump_file, "------------------\n");
671 : : }
672 : :
673 : 0 : pfedge->cost /= 2;
674 : 0 : pfedge->norm_vertex_index = new_index;
675 : 0 : if (dump_file)
676 : : {
677 : 0 : fprintf (dump_file, "After normalization:\n");
678 : 0 : dump_fixup_edge (dump_file, fixup_graph, pfedge);
679 : : }
680 : :
681 : : /* Add a new fixup edge: new_index->src. */
682 : 0 : add_fixup_edge (fixup_graph, new_index, pfedge->src,
683 : : REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost,
684 : : r_pfedge->max_capacity);
685 : 0 : gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices);
686 : :
687 : : /* Edge: r_pfedge->src -> r_pfedge->dest
688 : : ==> r_pfedge->src -> new_index. */
689 : 0 : r_pfedge->dest = new_index;
690 : 0 : r_pfedge->type = REVERSE_NORMALIZED_EDGE;
691 : 0 : r_pfedge->cost = pfedge->cost;
692 : 0 : r_pfedge->max_capacity = pfedge->max_capacity;
693 : 0 : if (dump_file)
694 : 0 : dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
695 : : }
696 : : }
697 : :
698 : 0 : if (dump_file)
699 : 0 : dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()");
700 : :
701 : : /* Cleanup. */
702 : 0 : free (diff_out_in);
703 : 0 : }
704 : :
705 : :
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. */
709 : :
710 : : static void
711 : 0 : init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size)
712 : : {
713 : 0 : augmenting_path->queue_list.queue = (int *)
714 : 0 : xcalloc (graph_size + 2, sizeof (int));
715 : 0 : augmenting_path->queue_list.size = graph_size + 2;
716 : 0 : augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int));
717 : 0 : augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int));
718 : 0 : }
719 : :
720 : : /* Free the structures in AUGMENTING_PATH. */
721 : : static void
722 : 0 : free_augmenting_path (augmenting_path_type *augmenting_path)
723 : : {
724 : 0 : free (augmenting_path->queue_list.queue);
725 : 0 : free (augmenting_path->bb_pred);
726 : 0 : free (augmenting_path->is_visited);
727 : 0 : }
728 : :
729 : :
730 : : /* Queue routines. Assumes queue will never overflow. */
731 : :
732 : : static void
733 : 0 : init_queue (queue_type *queue_list)
734 : : {
735 : 0 : gcc_assert (queue_list);
736 : 0 : queue_list->head = 0;
737 : 0 : queue_list->tail = 0;
738 : 0 : }
739 : :
740 : : /* Return true if QUEUE_LIST is empty. */
741 : : static bool
742 : 0 : is_empty (queue_type *queue_list)
743 : : {
744 : 0 : return (queue_list->head == queue_list->tail);
745 : : }
746 : :
747 : : /* Insert element X into QUEUE_LIST. */
748 : : static void
749 : 0 : enqueue (queue_type *queue_list, int x)
750 : : {
751 : 0 : gcc_assert (queue_list->tail < queue_list->size);
752 : 0 : queue_list->queue[queue_list->tail] = x;
753 : 0 : (queue_list->tail)++;
754 : 0 : }
755 : :
756 : : /* Return the first element in QUEUE_LIST. */
757 : : static int
758 : 0 : dequeue (queue_type *queue_list)
759 : : {
760 : 0 : int x;
761 : 0 : gcc_assert (queue_list->head >= 0);
762 : 0 : x = queue_list->queue[queue_list->head];
763 : 0 : (queue_list->head)++;
764 : 0 : return x;
765 : : }
766 : :
767 : :
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.
772 : :
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
779 : :
780 : : Return:
781 : : true if a negative cycle was found, false otherwise. */
782 : :
783 : : static bool
784 : 0 : cancel_negative_cycle (fixup_graph_type *fixup_graph,
785 : : int *pi, gcov_type *d, int *cycle)
786 : : {
787 : 0 : int i, j, k;
788 : 0 : int fnum_vertices, fnum_edges;
789 : 0 : fixup_edge_p fedge_list, pfedge, r_pfedge;
790 : 0 : bool found_cycle = false;
791 : 0 : int cycle_start = 0, cycle_end = 0;
792 : 0 : gcov_type sum_cost = 0, cycle_flow = 0;
793 : 0 : int new_entry_index;
794 : 0 : bool propagated = false;
795 : :
796 : 0 : gcc_assert (fixup_graph);
797 : 0 : fnum_vertices = fixup_graph->num_vertices;
798 : 0 : fnum_edges = fixup_graph->num_edges;
799 : 0 : fedge_list = fixup_graph->edge_list;
800 : 0 : new_entry_index = fixup_graph->new_entry_index;
801 : :
802 : : /* Initialize. */
803 : : /* Skip ENTRY. */
804 : 0 : for (i = 1; i < fnum_vertices; i++)
805 : : {
806 : 0 : d[i] = CAP_INFINITY;
807 : 0 : pi[i] = -1;
808 : 0 : cycle[i] = -1;
809 : : }
810 : 0 : d[ENTRY_BLOCK] = 0;
811 : :
812 : : /* Relax. */
813 : 0 : for (k = 1; k < fnum_vertices; k++)
814 : : {
815 : : propagated = false;
816 : 0 : for (i = 0; i < fnum_edges; i++)
817 : : {
818 : 0 : pfedge = fedge_list + i;
819 : 0 : if (pfedge->src == new_entry_index)
820 : 0 : continue;
821 : 0 : if (pfedge->is_rflow_valid && pfedge->rflow
822 : 0 : && d[pfedge->src] != CAP_INFINITY
823 : 0 : && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
824 : : {
825 : 0 : d[pfedge->dest] = d[pfedge->src] + pfedge->cost;
826 : 0 : pi[pfedge->dest] = pfedge->src;
827 : 0 : propagated = true;
828 : : }
829 : : }
830 : 0 : if (!propagated)
831 : : break;
832 : : }
833 : :
834 : 0 : if (!propagated)
835 : : /* No negative cycles exist. */
836 : : return 0;
837 : :
838 : : /* Detect. */
839 : 0 : for (i = 0; i < fnum_edges; i++)
840 : : {
841 : 0 : pfedge = fedge_list + i;
842 : 0 : if (pfedge->src == new_entry_index)
843 : 0 : continue;
844 : 0 : if (pfedge->is_rflow_valid && pfedge->rflow
845 : 0 : && d[pfedge->src] != CAP_INFINITY
846 : 0 : && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
847 : : {
848 : : found_cycle = true;
849 : : break;
850 : : }
851 : : }
852 : :
853 : 0 : if (!found_cycle)
854 : : return 0;
855 : :
856 : : /* Augment the cycle with the cycle's minimum residual capacity. */
857 : 0 : found_cycle = false;
858 : 0 : cycle[0] = pfedge->dest;
859 : 0 : j = pfedge->dest;
860 : :
861 : 0 : for (i = 1; i < fnum_vertices; i++)
862 : : {
863 : 0 : j = pi[j];
864 : 0 : cycle[i] = j;
865 : 0 : for (k = 0; k < i; k++)
866 : : {
867 : 0 : if (cycle[k] == j)
868 : : {
869 : : /* cycle[k] -> ... -> cycle[i]. */
870 : : cycle_start = k;
871 : : cycle_end = i;
872 : : found_cycle = true;
873 : : break;
874 : : }
875 : : }
876 : 0 : if (found_cycle)
877 : : break;
878 : : }
879 : :
880 : 0 : gcc_assert (cycle[cycle_start] == cycle[cycle_end]);
881 : 0 : if (dump_file)
882 : 0 : fprintf (dump_file, "\nNegative cycle length is %d:\n",
883 : : cycle_end - cycle_start);
884 : :
885 : : sum_cost = 0;
886 : : cycle_flow = CAP_INFINITY;
887 : 0 : for (k = cycle_start; k < cycle_end; k++)
888 : : {
889 : 0 : pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
890 : 0 : cycle_flow = MIN (cycle_flow, pfedge->rflow);
891 : 0 : sum_cost += pfedge->cost;
892 : 0 : if (dump_file)
893 : 0 : fprintf (dump_file, "%d ", cycle[k]);
894 : : }
895 : :
896 : 0 : if (dump_file)
897 : : {
898 : 0 : fprintf (dump_file, "%d", cycle[k]);
899 : 0 : fprintf (dump_file,
900 : : ": (%" PRId64 ", %" PRId64
901 : : ")\n", sum_cost, cycle_flow);
902 : 0 : fprintf (dump_file,
903 : : "Augment cycle with %" PRId64 "\n",
904 : : cycle_flow);
905 : : }
906 : :
907 : 0 : for (k = cycle_start; k < cycle_end; k++)
908 : : {
909 : 0 : pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
910 : 0 : r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]);
911 : 0 : pfedge->rflow -= cycle_flow;
912 : 0 : if (pfedge->type)
913 : 0 : pfedge->flow += cycle_flow;
914 : 0 : r_pfedge->rflow += cycle_flow;
915 : 0 : if (r_pfedge->type)
916 : 0 : r_pfedge->flow -= cycle_flow;
917 : : }
918 : :
919 : : return true;
920 : : }
921 : :
922 : :
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. */
925 : :
926 : : static void
927 : 0 : compute_residual_flow (fixup_graph_type *fixup_graph)
928 : : {
929 : 0 : int i;
930 : 0 : int fnum_edges;
931 : 0 : fixup_edge_p fedge_list, pfedge;
932 : :
933 : 0 : gcc_assert (fixup_graph);
934 : :
935 : 0 : if (dump_file)
936 : 0 : fputs ("\ncompute_residual_flow():\n", dump_file);
937 : :
938 : 0 : fnum_edges = fixup_graph->num_edges;
939 : 0 : fedge_list = fixup_graph->edge_list;
940 : :
941 : 0 : for (i = 0; i < fnum_edges; i++)
942 : : {
943 : 0 : pfedge = fedge_list + i;
944 : 0 : pfedge->rflow = pfedge->max_capacity - pfedge->flow;
945 : 0 : pfedge->is_rflow_valid = true;
946 : 0 : add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow,
947 : 0 : -pfedge->cost);
948 : : }
949 : 0 : }
950 : :
951 : :
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. */
957 : :
958 : : static int
959 : 0 : find_augmenting_path (fixup_graph_type *fixup_graph,
960 : : augmenting_path_type *augmenting_path, int source,
961 : : int sink)
962 : : {
963 : 0 : int u = 0;
964 : 0 : int i;
965 : 0 : fixup_vertex_p fvertex_list, pfvertex;
966 : 0 : fixup_edge_p pfedge;
967 : 0 : int *bb_pred, *is_visited;
968 : 0 : queue_type *queue_list;
969 : :
970 : 0 : gcc_assert (augmenting_path);
971 : 0 : bb_pred = augmenting_path->bb_pred;
972 : 0 : gcc_assert (bb_pred);
973 : 0 : is_visited = augmenting_path->is_visited;
974 : 0 : gcc_assert (is_visited);
975 : 0 : queue_list = &(augmenting_path->queue_list);
976 : :
977 : 0 : gcc_assert (fixup_graph);
978 : :
979 : 0 : fvertex_list = fixup_graph->vertex_list;
980 : :
981 : 0 : for (u = 0; u < fixup_graph->num_vertices; u++)
982 : 0 : is_visited[u] = 0;
983 : :
984 : 0 : init_queue (queue_list);
985 : 0 : enqueue (queue_list, source);
986 : 0 : bb_pred[source] = -1;
987 : :
988 : 0 : while (!is_empty (queue_list))
989 : : {
990 : 0 : u = dequeue (queue_list);
991 : 0 : is_visited[u] = 1;
992 : 0 : pfvertex = fvertex_list + u;
993 : 0 : for (i = 0; pfvertex->succ_edges.iterate (i, &pfedge);
994 : : i++)
995 : : {
996 : 0 : int dest = pfedge->dest;
997 : 0 : if ((pfedge->rflow > 0) && (is_visited[dest] == 0))
998 : : {
999 : 0 : enqueue (queue_list, dest);
1000 : 0 : bb_pred[dest] = u;
1001 : 0 : is_visited[dest] = 1;
1002 : 0 : if (dest == sink)
1003 : : return 1;
1004 : : }
1005 : : }
1006 : : }
1007 : :
1008 : : return 0;
1009 : : }
1010 : :
1011 : :
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.
1018 : :
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. */
1025 : :
1026 : : static gcov_type
1027 : 0 : find_max_flow (fixup_graph_type *fixup_graph, int source, int sink)
1028 : : {
1029 : 0 : int fnum_edges;
1030 : 0 : augmenting_path_type augmenting_path;
1031 : 0 : int *bb_pred;
1032 : 0 : gcov_type max_flow = 0;
1033 : 0 : int i, u;
1034 : 0 : fixup_edge_p fedge_list, pfedge, r_pfedge;
1035 : :
1036 : 0 : gcc_assert (fixup_graph);
1037 : :
1038 : 0 : fnum_edges = fixup_graph->num_edges;
1039 : 0 : fedge_list = fixup_graph->edge_list;
1040 : :
1041 : : /* Initialize flow to 0. */
1042 : 0 : for (i = 0; i < fnum_edges; i++)
1043 : : {
1044 : 0 : pfedge = fedge_list + i;
1045 : 0 : pfedge->flow = 0;
1046 : : }
1047 : :
1048 : 0 : compute_residual_flow (fixup_graph);
1049 : :
1050 : 0 : init_augmenting_path (&augmenting_path, fixup_graph->num_vertices);
1051 : :
1052 : 0 : bb_pred = augmenting_path.bb_pred;
1053 : 0 : while (find_augmenting_path (fixup_graph, &augmenting_path, source, sink))
1054 : : {
1055 : : /* Determine the amount by which we can increment the flow. */
1056 : : gcov_type increment = CAP_INFINITY;
1057 : 0 : for (u = sink; u != source; u = bb_pred[u])
1058 : : {
1059 : 0 : pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1060 : 0 : increment = MIN (increment, pfedge->rflow);
1061 : : }
1062 : 0 : max_flow += increment;
1063 : :
1064 : : /* Now increment the flow. EXIT vertex index is 1. */
1065 : 0 : for (u = sink; u != source; u = bb_pred[u])
1066 : : {
1067 : 0 : pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
1068 : 0 : r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]);
1069 : 0 : if (pfedge->type)
1070 : : {
1071 : : /* forward edge. */
1072 : 0 : pfedge->flow += increment;
1073 : 0 : pfedge->rflow -= increment;
1074 : 0 : r_pfedge->rflow += increment;
1075 : : }
1076 : : else
1077 : : {
1078 : : /* backward edge. */
1079 : 0 : gcc_assert (r_pfedge->type);
1080 : 0 : r_pfedge->rflow += increment;
1081 : 0 : r_pfedge->flow -= increment;
1082 : 0 : pfedge->rflow -= increment;
1083 : : }
1084 : : }
1085 : :
1086 : 0 : if (dump_file)
1087 : : {
1088 : 0 : fprintf (dump_file, "\nDump augmenting path:\n");
1089 : 0 : for (u = sink; u != source; u = bb_pred[u])
1090 : : {
1091 : 0 : print_basic_block (dump_file, fixup_graph, u);
1092 : 0 : fprintf (dump_file, "<-");
1093 : : }
1094 : 0 : fprintf (dump_file,
1095 : : "ENTRY (path_capacity=%" PRId64 ")\n",
1096 : : increment);
1097 : 0 : fprintf (dump_file,
1098 : : "Network flow is %" PRId64 ".\n",
1099 : : max_flow);
1100 : : }
1101 : : }
1102 : :
1103 : 0 : free_augmenting_path (&augmenting_path);
1104 : 0 : if (dump_file)
1105 : 0 : dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()");
1106 : 0 : return max_flow;
1107 : : }
1108 : :
1109 : :
1110 : : /* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1111 : : after applying the find_minimum_cost_flow() routine. */
1112 : :
1113 : : static void
1114 : 0 : adjust_cfg_counts (fixup_graph_type *fixup_graph)
1115 : : {
1116 : 0 : basic_block bb;
1117 : 0 : edge e;
1118 : 0 : edge_iterator ei;
1119 : 0 : int i, j;
1120 : 0 : fixup_edge_p pfedge, pfedge_n;
1121 : :
1122 : 0 : gcc_assert (fixup_graph);
1123 : :
1124 : 0 : if (dump_file)
1125 : 0 : fprintf (dump_file, "\nadjust_cfg_counts():\n");
1126 : :
1127 : 0 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
1128 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1129 : : {
1130 : 0 : i = 2 * bb->index;
1131 : :
1132 : : /* Fixup BB. */
1133 : 0 : if (dump_file)
1134 : 0 : fprintf (dump_file,
1135 : 0 : "BB%d: %" PRId64 "", bb->index, bb_gcov_count (bb));
1136 : :
1137 : 0 : pfedge = find_fixup_edge (fixup_graph, i, i + 1);
1138 : 0 : if (pfedge->flow)
1139 : : {
1140 : 0 : bb_gcov_count (bb) += pfedge->flow;
1141 : 0 : if (dump_file)
1142 : : {
1143 : 0 : fprintf (dump_file, " + %" PRId64 "(",
1144 : : pfedge->flow);
1145 : 0 : print_edge (dump_file, fixup_graph, i, i + 1);
1146 : 0 : fprintf (dump_file, ")");
1147 : : }
1148 : : }
1149 : :
1150 : 0 : pfedge_n =
1151 : 0 : find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1152 : : /* Deduct flow from normalized reverse edge. */
1153 : 0 : if (pfedge->norm_vertex_index && pfedge_n->flow)
1154 : : {
1155 : 0 : bb_gcov_count (bb) -= pfedge_n->flow;
1156 : 0 : if (dump_file)
1157 : : {
1158 : 0 : fprintf (dump_file, " - %" PRId64 "(",
1159 : : pfedge_n->flow);
1160 : 0 : print_edge (dump_file, fixup_graph, i + 1,
1161 : : pfedge->norm_vertex_index);
1162 : 0 : fprintf (dump_file, ")");
1163 : : }
1164 : : }
1165 : 0 : if (dump_file)
1166 : 0 : fprintf (dump_file, " = %" PRId64 "\n", bb_gcov_count (bb));
1167 : :
1168 : : /* Fixup edge. */
1169 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
1170 : : {
1171 : : /* Treat edges with ignore attribute set as if they don't exist. */
1172 : 0 : if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1173 : 0 : continue;
1174 : :
1175 : 0 : j = 2 * e->dest->index;
1176 : 0 : if (dump_file)
1177 : 0 : fprintf (dump_file, "%d->%d: %" PRId64 "",
1178 : 0 : bb->index, e->dest->index, edge_gcov_count (e));
1179 : :
1180 : 0 : pfedge = find_fixup_edge (fixup_graph, i + 1, j);
1181 : :
1182 : 0 : if (bb->index != e->dest->index)
1183 : : {
1184 : : /* Non-self edge. */
1185 : 0 : if (pfedge->flow)
1186 : : {
1187 : 0 : edge_gcov_count (e) += pfedge->flow;
1188 : 0 : if (dump_file)
1189 : : {
1190 : 0 : fprintf (dump_file, " + %" PRId64 "(",
1191 : : pfedge->flow);
1192 : 0 : print_edge (dump_file, fixup_graph, i + 1, j);
1193 : 0 : fprintf (dump_file, ")");
1194 : : }
1195 : : }
1196 : :
1197 : 0 : pfedge_n =
1198 : 0 : find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index);
1199 : : /* Deduct flow from normalized reverse edge. */
1200 : 0 : if (pfedge->norm_vertex_index && pfedge_n->flow)
1201 : : {
1202 : 0 : edge_gcov_count (e) -= pfedge_n->flow;
1203 : 0 : if (dump_file)
1204 : : {
1205 : 0 : fprintf (dump_file, " - %" PRId64 "(",
1206 : : pfedge_n->flow);
1207 : 0 : print_edge (dump_file, fixup_graph, j,
1208 : : pfedge->norm_vertex_index);
1209 : 0 : fprintf (dump_file, ")");
1210 : : }
1211 : : }
1212 : : }
1213 : : else
1214 : : {
1215 : : /* Handle self edges. Self edge is split with a normalization
1216 : : vertex. Here i=j. */
1217 : 0 : pfedge = find_fixup_edge (fixup_graph, j, i + 1);
1218 : 0 : pfedge_n =
1219 : 0 : find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
1220 : 0 : edge_gcov_count (e) += pfedge_n->flow;
1221 : 0 : bb_gcov_count (bb) += pfedge_n->flow;
1222 : 0 : if (dump_file)
1223 : : {
1224 : 0 : fprintf (dump_file, "(self edge)");
1225 : 0 : fprintf (dump_file, " + %" PRId64 "(",
1226 : : pfedge_n->flow);
1227 : 0 : print_edge (dump_file, fixup_graph, i + 1,
1228 : : pfedge->norm_vertex_index);
1229 : 0 : fprintf (dump_file, ")");
1230 : : }
1231 : : }
1232 : :
1233 : 0 : if (bb_gcov_count (bb))
1234 : 0 : e->probability = profile_probability::probability_in_gcov_type
1235 : 0 : (edge_gcov_count (e), bb_gcov_count (bb));
1236 : 0 : if (dump_file)
1237 : : {
1238 : 0 : fprintf (dump_file, " = %" PRId64 "\t",
1239 : 0 : edge_gcov_count (e));
1240 : 0 : e->probability.dump (dump_file);
1241 : 0 : fprintf (dump_file, "\n");
1242 : : }
1243 : : }
1244 : : }
1245 : :
1246 : 0 : bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun)) =
1247 : 0 : sum_edge_counts (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1248 : 0 : bb_gcov_count (EXIT_BLOCK_PTR_FOR_FN (cfun)) =
1249 : 0 : sum_edge_counts (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
1250 : :
1251 : : /* Compute edge probabilities. */
1252 : 0 : FOR_ALL_BB_FN (bb, cfun)
1253 : : {
1254 : 0 : if (bb_gcov_count (bb))
1255 : : {
1256 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
1257 : 0 : e->probability = profile_probability::probability_in_gcov_type
1258 : 0 : (edge_gcov_count (e), bb_gcov_count (bb));
1259 : : }
1260 : : }
1261 : :
1262 : 0 : if (dump_file)
1263 : : {
1264 : 0 : fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n",
1265 : : current_function_name ());
1266 : 0 : FOR_EACH_BB_FN (bb, cfun)
1267 : : {
1268 : 0 : if ((bb_gcov_count (bb) != sum_edge_counts (bb->preds))
1269 : 0 : || (bb_gcov_count (bb) != sum_edge_counts (bb->succs)))
1270 : : {
1271 : 0 : fprintf (dump_file,
1272 : : "BB%d(%" PRId64 ") **INVALID**: ",
1273 : 0 : bb->index, bb_gcov_count (bb));
1274 : 0 : fprintf (stderr,
1275 : : "******** BB%d(%" PRId64
1276 : 0 : ") **INVALID**: \n", bb->index, bb_gcov_count (bb));
1277 : 0 : fprintf (dump_file, "in_edges=%" PRId64 " ",
1278 : : sum_edge_counts (bb->preds));
1279 : 0 : fprintf (dump_file, "out_edges=%" PRId64 "\n",
1280 : : sum_edge_counts (bb->succs));
1281 : : }
1282 : : }
1283 : : }
1284 : 0 : }
1285 : :
1286 : :
1287 : : /* Implements the negative cycle canceling algorithm to compute a minimum cost
1288 : : flow.
1289 : : Algorithm:
1290 : : 1. Find maximal flow.
1291 : : 2. Form residual network
1292 : : 3. Repeat:
1293 : : While G contains a negative cost cycle C, reverse the flow on the found cycle
1294 : : by the minimum residual capacity in that cycle.
1295 : : 4. Form the minimal cost flow
1296 : : f(u,v) = rf(v, u)
1297 : : Input:
1298 : : FIXUP_GRAPH - Initial fixup graph.
1299 : : The flow field is modified to represent the minimum cost flow. */
1300 : :
1301 : : static void
1302 : 0 : find_minimum_cost_flow (fixup_graph_type *fixup_graph)
1303 : : {
1304 : : /* Holds the index of predecessor in path. */
1305 : 0 : int *pred;
1306 : : /* Used to hold the minimum cost cycle. */
1307 : 0 : int *cycle;
1308 : : /* Used to record the number of iterations of cancel_negative_cycle. */
1309 : 0 : int iteration;
1310 : : /* Vector d[i] holds the minimum cost of path from i to sink. */
1311 : 0 : gcov_type *d;
1312 : 0 : int fnum_vertices;
1313 : 0 : int new_exit_index;
1314 : 0 : int new_entry_index;
1315 : :
1316 : 0 : gcc_assert (fixup_graph);
1317 : 0 : fnum_vertices = fixup_graph->num_vertices;
1318 : 0 : new_exit_index = fixup_graph->new_exit_index;
1319 : 0 : new_entry_index = fixup_graph->new_entry_index;
1320 : :
1321 : 0 : find_max_flow (fixup_graph, new_entry_index, new_exit_index);
1322 : :
1323 : : /* Initialize the structures for find_negative_cycle(). */
1324 : 0 : pred = (int *) xcalloc (fnum_vertices, sizeof (int));
1325 : 0 : d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type));
1326 : 0 : cycle = (int *) xcalloc (fnum_vertices, sizeof (int));
1327 : :
1328 : : /* Repeatedly find and cancel negative cost cycles, until
1329 : : no more negative cycles exist. This also updates the flow field
1330 : : to represent the minimum cost flow so far. */
1331 : 0 : iteration = 0;
1332 : 0 : while (cancel_negative_cycle (fixup_graph, pred, d, cycle))
1333 : : {
1334 : 0 : iteration++;
1335 : 0 : if (iteration > MAX_ITER (fixup_graph->num_vertices,
1336 : : fixup_graph->num_edges))
1337 : : break;
1338 : : }
1339 : :
1340 : 0 : if (dump_file)
1341 : 0 : dump_fixup_graph (dump_file, fixup_graph,
1342 : : "After find_minimum_cost_flow()");
1343 : :
1344 : : /* Cleanup structures. */
1345 : 0 : free (pred);
1346 : 0 : free (d);
1347 : 0 : free (cycle);
1348 : 0 : }
1349 : :
1350 : :
1351 : : /* Compute the sum of the edge counts in TO_EDGES. */
1352 : :
1353 : : gcov_type
1354 : 4838 : sum_edge_counts (vec<edge, va_gc> *to_edges)
1355 : : {
1356 : 4838 : gcov_type sum = 0;
1357 : 4838 : edge e;
1358 : 4838 : edge_iterator ei;
1359 : :
1360 : 11632 : FOR_EACH_EDGE (e, ei, to_edges)
1361 : : {
1362 : 6794 : if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
1363 : 32 : continue;
1364 : 6762 : sum += edge_gcov_count (e);
1365 : : }
1366 : 4838 : return sum;
1367 : : }
1368 : :
1369 : :
1370 : : /* Main routine. Smoothes the initial assigned basic block and edge counts using
1371 : : a minimum cost flow algorithm, to ensure that the flow consistency rule is
1372 : : obeyed: sum of outgoing edges = sum of incoming edges for each basic
1373 : : block. */
1374 : :
1375 : : void
1376 : 0 : mcf_smooth_cfg (void)
1377 : : {
1378 : 0 : fixup_graph_type fixup_graph;
1379 : 0 : memset (&fixup_graph, 0, sizeof (fixup_graph));
1380 : 0 : create_fixup_graph (&fixup_graph);
1381 : 0 : find_minimum_cost_flow (&fixup_graph);
1382 : 0 : adjust_cfg_counts (&fixup_graph);
1383 : 0 : delete_fixup_graph (&fixup_graph);
1384 : 0 : }
|
