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