]>
Commit | Line | Data |
---|---|---|
f7bc085c L |
1 | /* Routines to implement minimum-cost maximal flow algorithm used to smooth |
2 | basic block and edge frequency counts. | |
a5544970 | 3 | Copyright (C) 2008-2019 Free Software Foundation, Inc. |
f7bc085c L |
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" | |
c7131fb2 | 48 | #include "backend.h" |
f7bc085c | 49 | #include "profile.h" |
7ee2468b | 50 | #include "dumpfile.h" |
f7bc085c L |
51 | |
52 | /* CAP_INFINITY: Constant to represent infinite capacity. */ | |
a9243bfc | 53 | #define CAP_INFINITY INTTYPE_MAXIMUM (int64_t) |
f7bc085c L |
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))) | |
a79683d5 | 62 | enum edge_type |
f7bc085c L |
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. */ | |
a79683d5 | 73 | }; |
f7bc085c L |
74 | |
75 | /* Structure to represent an edge in the fixup graph. */ | |
a79683d5 | 76 | struct fixup_edge_type |
f7bc085c L |
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; | |
a79683d5 | 92 | }; |
f7bc085c L |
93 | |
94 | typedef fixup_edge_type *fixup_edge_p; | |
95 | ||
f7bc085c L |
96 | |
97 | /* Structure to represent a vertex in the fixup graph. */ | |
a79683d5 | 98 | struct fixup_vertex_type |
f7bc085c | 99 | { |
9771b263 | 100 | vec<fixup_edge_p> succ_edges; |
a79683d5 | 101 | }; |
f7bc085c L |
102 | |
103 | typedef fixup_vertex_type *fixup_vertex_p; | |
104 | ||
105 | /* Fixup graph used in the MCF algorithm. */ | |
a79683d5 | 106 | struct fixup_graph_type |
f7bc085c L |
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; | |
a79683d5 | 120 | }; |
f7bc085c | 121 | |
a79683d5 | 122 | struct queue_type |
f7bc085c L |
123 | { |
124 | int *queue; | |
125 | int head; | |
126 | int tail; | |
127 | int size; | |
a79683d5 | 128 | }; |
f7bc085c L |
129 | |
130 | /* Structure used in the maximal flow routines to find augmenting path. */ | |
a79683d5 | 131 | struct augmenting_path_type |
f7bc085c L |
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; | |
a79683d5 | 139 | }; |
f7bc085c L |
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 | print_basic_block (FILE *file, fixup_graph_type *fixup_graph, int n) | |
150 | { | |
151 | if (n == ENTRY_BLOCK) | |
152 | fputs ("ENTRY", file); | |
153 | else if (n == ENTRY_BLOCK + 1) | |
154 | fputs ("ENTRY''", file); | |
155 | else if (n == 2 * EXIT_BLOCK) | |
156 | fputs ("EXIT", file); | |
157 | else if (n == 2 * EXIT_BLOCK + 1) | |
158 | fputs ("EXIT''", file); | |
159 | else if (n == fixup_graph->new_exit_index) | |
160 | fputs ("NEW_EXIT", file); | |
161 | else if (n == fixup_graph->new_entry_index) | |
162 | fputs ("NEW_ENTRY", file); | |
163 | else | |
164 | { | |
165 | fprintf (file, "%d", n / 2); | |
166 | if (n % 2) | |
167 | fputs ("''", file); | |
168 | else | |
169 | fputs ("'", file); | |
170 | } | |
171 | } | |
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 | print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d) | |
182 | { | |
183 | print_basic_block (file, fixup_graph, s); | |
184 | fputs ("->", file); | |
185 | print_basic_block (file, fixup_graph, d); | |
186 | } | |
187 | ||
188 | ||
189 | /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a | |
190 | file. */ | |
191 | static void | |
192 | dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge) | |
193 | { | |
194 | if (!fedge) | |
195 | { | |
196 | fputs ("NULL fixup graph edge.\n", file); | |
197 | return; | |
198 | } | |
199 | ||
200 | print_edge (file, fixup_graph, fedge->src, fedge->dest); | |
201 | fputs (": ", file); | |
202 | ||
203 | if (fedge->type) | |
204 | { | |
16998094 | 205 | fprintf (file, "flow/capacity=%" PRId64 "/", |
f7bc085c L |
206 | fedge->flow); |
207 | if (fedge->max_capacity == CAP_INFINITY) | |
208 | fputs ("+oo,", file); | |
209 | else | |
16998094 | 210 | fprintf (file, "%" PRId64 ",", fedge->max_capacity); |
f7bc085c L |
211 | } |
212 | ||
213 | if (fedge->is_rflow_valid) | |
214 | { | |
215 | if (fedge->rflow == CAP_INFINITY) | |
216 | fputs (" rflow=+oo.", file); | |
217 | else | |
16998094 | 218 | fprintf (file, " rflow=%" PRId64 ",", fedge->rflow); |
f7bc085c L |
219 | } |
220 | ||
16998094 | 221 | fprintf (file, " cost=%" PRId64 ".", fedge->cost); |
f7bc085c L |
222 | |
223 | fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest); | |
224 | ||
225 | if (fedge->type) | |
226 | { | |
227 | switch (fedge->type) | |
228 | { | |
229 | case VERTEX_SPLIT_EDGE: | |
230 | fputs (" @VERTEX_SPLIT_EDGE", file); | |
231 | break; | |
232 | ||
233 | case REDIRECT_EDGE: | |
234 | fputs (" @REDIRECT_EDGE", file); | |
235 | break; | |
236 | ||
237 | case SOURCE_CONNECT_EDGE: | |
238 | fputs (" @SOURCE_CONNECT_EDGE", file); | |
239 | break; | |
240 | ||
241 | case SINK_CONNECT_EDGE: | |
242 | fputs (" @SINK_CONNECT_EDGE", file); | |
243 | break; | |
244 | ||
245 | case REVERSE_EDGE: | |
246 | fputs (" @REVERSE_EDGE", file); | |
247 | break; | |
248 | ||
249 | case BALANCE_EDGE: | |
250 | fputs (" @BALANCE_EDGE", file); | |
251 | break; | |
252 | ||
253 | case REDIRECT_NORMALIZED_EDGE: | |
254 | case REVERSE_NORMALIZED_EDGE: | |
255 | fputs (" @NORMALIZED_EDGE", file); | |
256 | break; | |
257 | ||
258 | default: | |
259 | fputs (" @INVALID_EDGE", file); | |
260 | break; | |
261 | } | |
262 | } | |
263 | 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 | dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg) | |
272 | { | |
273 | int i, j; | |
274 | int fnum_vertices, fnum_edges; | |
275 | ||
276 | fixup_vertex_p fvertex_list, pfvertex; | |
277 | fixup_edge_p pfedge; | |
278 | ||
279 | gcc_assert (fixup_graph); | |
280 | fvertex_list = fixup_graph->vertex_list; | |
281 | fnum_vertices = fixup_graph->num_vertices; | |
282 | fnum_edges = fixup_graph->num_edges; | |
283 | ||
284 | fprintf (file, "\nDump fixup graph for %s(): %s.\n", | |
e6d46b5a | 285 | current_function_name (), msg); |
f7bc085c L |
286 | 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 | for (i = 0; i < fnum_vertices; i++) | |
291 | { | |
292 | pfvertex = fvertex_list + i; | |
293 | fprintf (file, "vertex_list[%d]: %d succ fixup edges.\n", | |
9771b263 | 294 | i, pfvertex->succ_edges.length ()); |
f7bc085c | 295 | |
9771b263 | 296 | for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge); |
f7bc085c L |
297 | j++) |
298 | { | |
299 | /* Distinguish forward edges and backward edges in the residual flow | |
300 | network. */ | |
301 | if (pfedge->type) | |
302 | fputs ("(f) ", file); | |
303 | else if (pfedge->is_rflow_valid) | |
304 | fputs ("(b) ", file); | |
305 | dump_fixup_edge (file, fixup_graph, pfedge); | |
306 | } | |
307 | } | |
308 | ||
309 | fputs ("\n", file); | |
310 | } | |
311 | ||
312 | ||
313 | /* Utility routines. */ | |
314 | /* ln() implementation: approximate calculation. Returns ln of X. */ | |
315 | ||
316 | static double | |
317 | mcf_ln (double x) | |
318 | { | |
319 | #define E 2.71828 | |
320 | int l = 1; | |
321 | double m = E; | |
322 | ||
323 | gcc_assert (x >= 0); | |
324 | ||
325 | while (m < x) | |
326 | { | |
327 | m *= E; | |
328 | l++; | |
329 | } | |
330 | ||
331 | 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 | mcf_sqrt (double x) | |
340 | { | |
341 | #define MAGIC_CONST1 0x1fbcf800 | |
342 | #define MAGIC_CONST2 0x5f3759df | |
343 | union { | |
344 | int intPart; | |
345 | float floatPart; | |
346 | } convertor, convertor2; | |
347 | ||
348 | gcc_assert (x >= 0); | |
349 | ||
350 | convertor.floatPart = x; | |
351 | convertor2.floatPart = x; | |
352 | convertor.intPart = MAGIC_CONST1 + (convertor.intPart >> 1); | |
353 | convertor2.intPart = MAGIC_CONST2 - (convertor2.intPart >> 1); | |
354 | ||
355 | 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 | add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost) | |
365 | { | |
366 | fixup_vertex_p curr_vertex = fixup_graph->vertex_list + src; | |
367 | fixup_edge_p curr_edge = fixup_graph->edge_list + fixup_graph->num_edges; | |
368 | curr_edge->src = src; | |
369 | curr_edge->dest = dest; | |
370 | curr_edge->cost = cost; | |
371 | fixup_graph->num_edges++; | |
372 | if (dump_file) | |
373 | dump_fixup_edge (dump_file, fixup_graph, curr_edge); | |
9771b263 | 374 | curr_vertex->succ_edges.safe_push (curr_edge); |
f7bc085c L |
375 | 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 | |
32e8bb8e ILT |
383 | 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) | |
f7bc085c | 386 | { |
c3284718 | 387 | fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost); |
f7bc085c L |
388 | curr_edge->type = type; |
389 | curr_edge->weight = weight; | |
390 | curr_edge->max_capacity = max_capacity; | |
391 | } | |
392 | ||
393 | ||
394 | /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST | |
395 | to the fixup graph. */ | |
396 | ||
397 | static void | |
398 | add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest, | |
399 | gcov_type rflow, gcov_type cost) | |
400 | { | |
401 | fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost); | |
402 | curr_edge->rflow = rflow; | |
403 | curr_edge->is_rflow_valid = true; | |
404 | /* This edge is not a valid edge - merely used to hold residual flow. */ | |
405 | curr_edge->type = INVALID_EDGE; | |
406 | } | |
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 | find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest) | |
414 | { | |
415 | int j; | |
416 | fixup_edge_p pfedge; | |
417 | fixup_vertex_p pfvertex; | |
418 | ||
419 | gcc_assert (src < fixup_graph->num_vertices); | |
420 | ||
421 | pfvertex = fixup_graph->vertex_list + src; | |
422 | ||
9771b263 | 423 | for (j = 0; pfvertex->succ_edges.iterate (j, &pfedge); |
f7bc085c L |
424 | j++) |
425 | if (pfedge->dest == dest) | |
426 | return pfedge; | |
427 | ||
428 | return NULL; | |
429 | } | |
430 | ||
431 | ||
432 | /* Cleanup routine to free structures in FIXUP_GRAPH. */ | |
433 | ||
434 | static void | |
435 | delete_fixup_graph (fixup_graph_type *fixup_graph) | |
436 | { | |
437 | int i; | |
438 | int fnum_vertices = fixup_graph->num_vertices; | |
439 | fixup_vertex_p pfvertex = fixup_graph->vertex_list; | |
440 | ||
441 | for (i = 0; i < fnum_vertices; i++, pfvertex++) | |
9771b263 | 442 | pfvertex->succ_edges.release (); |
f7bc085c L |
443 | |
444 | free (fixup_graph->vertex_list); | |
445 | free (fixup_graph->edge_list); | |
446 | } | |
447 | ||
448 | ||
449 | /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */ | |
450 | ||
451 | static void | |
452 | create_fixup_graph (fixup_graph_type *fixup_graph) | |
453 | { | |
454 | double sqrt_avg_vertex_weight = 0; | |
455 | double total_vertex_weight = 0; | |
456 | double k_pos = 0; | |
457 | double k_neg = 0; | |
458 | /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */ | |
459 | gcov_type *diff_out_in = NULL; | |
460 | gcov_type supply_value = 1, demand_value = 0; | |
461 | gcov_type fcost = 0; | |
462 | int new_entry_index = 0, new_exit_index = 0; | |
463 | int i = 0, j = 0; | |
464 | int new_index = 0; | |
465 | basic_block bb; | |
466 | edge e; | |
467 | edge_iterator ei; | |
468 | fixup_edge_p pfedge, r_pfedge; | |
469 | fixup_edge_p fedge_list; | |
470 | int fnum_edges; | |
471 | ||
472 | /* Each basic_block will be split into 2 during vertex transformation. */ | |
0cae8d31 | 473 | int fnum_vertices_after_transform = 2 * n_basic_blocks_for_fn (cfun); |
dc936fb2 DM |
474 | int fnum_edges_after_transform = |
475 | n_edges_for_fn (cfun) + n_basic_blocks_for_fn (cfun); | |
f7bc085c L |
476 | |
477 | /* Count the new SOURCE and EXIT vertices to be added. */ | |
478 | int fmax_num_vertices = | |
dc936fb2 DM |
479 | (fnum_vertices_after_transform + n_edges_for_fn (cfun) |
480 | + n_basic_blocks_for_fn (cfun) + 2); | |
f7bc085c L |
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. */ | |
dc936fb2 DM |
490 | int fmax_num_edges = 8 * (n_basic_blocks_for_fn (cfun) + |
491 | n_edges_for_fn (cfun)); | |
f7bc085c L |
492 | |
493 | /* Initial num of vertices in the fixup graph. */ | |
0cae8d31 | 494 | fixup_graph->num_vertices = n_basic_blocks_for_fn (cfun); |
f7bc085c L |
495 | |
496 | /* Fixup graph vertex list. */ | |
497 | fixup_graph->vertex_list = | |
498 | (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type)); | |
499 | ||
500 | /* Fixup graph edge list. */ | |
501 | fixup_graph->edge_list = | |
502 | (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type)); | |
503 | ||
504 | diff_out_in = | |
505 | (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. */ | |
fefa31b5 | 510 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
3995f3a2 | 511 | total_vertex_weight += bb_gcov_count (bb); |
f7bc085c | 512 | |
0cae8d31 DM |
513 | sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / |
514 | n_basic_blocks_for_fn (cfun)); | |
f7bc085c L |
515 | |
516 | k_pos = K_POS (sqrt_avg_vertex_weight); | |
517 | 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 | if (dump_file) | |
523 | fprintf (dump_file, "\nVertex transformation:\n"); | |
524 | ||
fefa31b5 | 525 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
f7bc085c L |
526 | { |
527 | /* v'->v'': index1->(index1+1). */ | |
528 | i = 2 * bb->index; | |
3995f3a2 JH |
529 | fcost = (gcov_type) COST (k_pos, bb_gcov_count (bb)); |
530 | add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb_gcov_count (bb), | |
f7bc085c L |
531 | fcost, CAP_INFINITY); |
532 | fixup_graph->num_vertices++; | |
533 | ||
534 | FOR_EACH_EDGE (e, ei, bb->succs) | |
535 | { | |
536 | /* Edges with ignore attribute set should be treated like they don't | |
537 | exist. */ | |
538 | if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) | |
539 | continue; | |
540 | j = 2 * e->dest->index; | |
3995f3a2 JH |
541 | fcost = (gcov_type) COST (k_pos, edge_gcov_count (e)); |
542 | add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, edge_gcov_count (e), | |
543 | fcost, CAP_INFINITY); | |
f7bc085c L |
544 | } |
545 | } | |
546 | ||
547 | /* After vertex transformation. */ | |
548 | gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform); | |
549 | /* Redirect edges are not added for edges with ignore attribute. */ | |
550 | gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform); | |
551 | ||
552 | fnum_edges_after_transform = fixup_graph->num_edges; | |
553 | ||
554 | /* 2. Initialize D(v). */ | |
555 | for (i = 0; i < fnum_edges_after_transform; i++) | |
556 | { | |
557 | pfedge = fixup_graph->edge_list + i; | |
558 | diff_out_in[pfedge->src] += pfedge->weight; | |
559 | diff_out_in[pfedge->dest] -= pfedge->weight; | |
560 | } | |
561 | ||
562 | /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */ | |
563 | for (i = 0; i <= 3; i++) | |
564 | diff_out_in[i] = 0; | |
565 | ||
566 | /* 3. Add reverse edges: needed to decrease counts during smoothing. */ | |
567 | if (dump_file) | |
568 | fprintf (dump_file, "\nReverse edges:\n"); | |
569 | for (i = 0; i < fnum_edges_after_transform; i++) | |
570 | { | |
571 | pfedge = fixup_graph->edge_list + i; | |
572 | if ((pfedge->src == 0) || (pfedge->src == 2)) | |
573 | continue; | |
574 | r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src); | |
575 | if (!r_pfedge && pfedge->weight) | |
576 | { | |
577 | /* Skip adding reverse edges for edges with w(e) = 0, as its maximum | |
578 | capacity is 0. */ | |
579 | fcost = (gcov_type) COST (k_neg, pfedge->weight); | |
580 | add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src, | |
581 | REVERSE_EDGE, 0, fcost, pfedge->weight); | |
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 | if (dump_file) | |
588 | fprintf (dump_file, "\ns'->S, T->t':\n"); | |
589 | ||
590 | new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices; | |
591 | fixup_graph->num_vertices++; | |
592 | /* Set supply_value to 1 to avoid zero count function ENTRY. */ | |
593 | add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE, | |
594 | 1 /* supply_value */, 0, 1 /* supply_value */); | |
595 | ||
596 | /* Create new exit with EXIT_BLOCK as single pred. */ | |
597 | new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices; | |
598 | fixup_graph->num_vertices++; | |
599 | add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index, | |
600 | SINK_CONNECT_EDGE, | |
601 | 0 /* demand_value */, 0, 0 /* demand_value */); | |
602 | ||
603 | /* Connect vertices with unbalanced D(v) to source/sink. */ | |
604 | if (dump_file) | |
605 | fprintf (dump_file, "\nD(v) balance:\n"); | |
606 | /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4. | |
607 | diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2. */ | |
608 | for (i = 4; i < new_entry_index; i += 2) | |
609 | { | |
610 | if (diff_out_in[i] > 0) | |
611 | { | |
612 | add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0, | |
613 | diff_out_in[i]); | |
614 | demand_value += diff_out_in[i]; | |
615 | } | |
616 | else if (diff_out_in[i] < 0) | |
617 | { | |
618 | add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0, | |
619 | -diff_out_in[i]); | |
620 | supply_value -= diff_out_in[i]; | |
621 | } | |
622 | } | |
623 | ||
624 | /* Set supply = demand. */ | |
625 | if (dump_file) | |
626 | { | |
627 | fprintf (dump_file, "\nAdjust supply and demand:\n"); | |
16998094 | 628 | fprintf (dump_file, "supply_value=%" PRId64 "\n", |
f7bc085c | 629 | supply_value); |
16998094 | 630 | fprintf (dump_file, "demand_value=%" PRId64 "\n", |
f7bc085c L |
631 | demand_value); |
632 | } | |
633 | ||
634 | if (demand_value > supply_value) | |
635 | { | |
636 | pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK); | |
637 | pfedge->max_capacity += (demand_value - supply_value); | |
638 | } | |
639 | else | |
640 | { | |
641 | pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index); | |
642 | 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 | if (dump_file) | |
649 | fprintf (dump_file, "\nNormalize edges:\n"); | |
650 | ||
651 | fnum_edges = fixup_graph->num_edges; | |
652 | fedge_list = fixup_graph->edge_list; | |
653 | ||
654 | for (i = 0; i < fnum_edges; i++) | |
655 | { | |
656 | pfedge = fedge_list + i; | |
657 | r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src); | |
658 | if (((pfedge->type == VERTEX_SPLIT_EDGE) | |
659 | || (pfedge->type == REDIRECT_EDGE)) && r_pfedge) | |
660 | { | |
661 | new_index = fixup_graph->num_vertices; | |
662 | fixup_graph->num_vertices++; | |
663 | ||
664 | if (dump_file) | |
665 | { | |
666 | fprintf (dump_file, "\nAnti-parallel edge:\n"); | |
667 | dump_fixup_edge (dump_file, fixup_graph, pfedge); | |
668 | dump_fixup_edge (dump_file, fixup_graph, r_pfedge); | |
669 | fprintf (dump_file, "New vertex is %d.\n", new_index); | |
670 | fprintf (dump_file, "------------------\n"); | |
671 | } | |
672 | ||
673 | pfedge->cost /= 2; | |
674 | pfedge->norm_vertex_index = new_index; | |
675 | if (dump_file) | |
676 | { | |
677 | fprintf (dump_file, "After normalization:\n"); | |
678 | dump_fixup_edge (dump_file, fixup_graph, pfedge); | |
679 | } | |
680 | ||
681 | /* Add a new fixup edge: new_index->src. */ | |
682 | add_fixup_edge (fixup_graph, new_index, pfedge->src, | |
683 | REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost, | |
684 | r_pfedge->max_capacity); | |
685 | gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices); | |
686 | ||
687 | /* Edge: r_pfedge->src -> r_pfedge->dest | |
688 | ==> r_pfedge->src -> new_index. */ | |
689 | r_pfedge->dest = new_index; | |
690 | r_pfedge->type = REVERSE_NORMALIZED_EDGE; | |
691 | r_pfedge->cost = pfedge->cost; | |
692 | r_pfedge->max_capacity = pfedge->max_capacity; | |
693 | if (dump_file) | |
694 | dump_fixup_edge (dump_file, fixup_graph, r_pfedge); | |
695 | } | |
696 | } | |
697 | ||
698 | if (dump_file) | |
699 | dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()"); | |
700 | ||
701 | /* Cleanup. */ | |
702 | free (diff_out_in); | |
703 | } | |
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 | init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size) | |
712 | { | |
713 | augmenting_path->queue_list.queue = (int *) | |
714 | xcalloc (graph_size + 2, sizeof (int)); | |
715 | augmenting_path->queue_list.size = graph_size + 2; | |
716 | augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int)); | |
717 | augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int)); | |
718 | } | |
719 | ||
720 | /* Free the structures in AUGMENTING_PATH. */ | |
721 | static void | |
722 | free_augmenting_path (augmenting_path_type *augmenting_path) | |
723 | { | |
724 | free (augmenting_path->queue_list.queue); | |
725 | free (augmenting_path->bb_pred); | |
726 | free (augmenting_path->is_visited); | |
727 | } | |
728 | ||
729 | ||
730 | /* Queue routines. Assumes queue will never overflow. */ | |
731 | ||
732 | static void | |
733 | init_queue (queue_type *queue_list) | |
734 | { | |
735 | gcc_assert (queue_list); | |
736 | queue_list->head = 0; | |
737 | queue_list->tail = 0; | |
738 | } | |
739 | ||
740 | /* Return true if QUEUE_LIST is empty. */ | |
741 | static bool | |
742 | is_empty (queue_type *queue_list) | |
743 | { | |
744 | return (queue_list->head == queue_list->tail); | |
745 | } | |
746 | ||
747 | /* Insert element X into QUEUE_LIST. */ | |
748 | static void | |
749 | enqueue (queue_type *queue_list, int x) | |
750 | { | |
751 | gcc_assert (queue_list->tail < queue_list->size); | |
752 | queue_list->queue[queue_list->tail] = x; | |
753 | (queue_list->tail)++; | |
754 | } | |
755 | ||
756 | /* Return the first element in QUEUE_LIST. */ | |
757 | static int | |
758 | dequeue (queue_type *queue_list) | |
759 | { | |
760 | int x; | |
761 | gcc_assert (queue_list->head >= 0); | |
762 | x = queue_list->queue[queue_list->head]; | |
763 | (queue_list->head)++; | |
764 | return x; | |
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 | cancel_negative_cycle (fixup_graph_type *fixup_graph, | |
785 | int *pi, gcov_type *d, int *cycle) | |
786 | { | |
787 | int i, j, k; | |
788 | int fnum_vertices, fnum_edges; | |
789 | fixup_edge_p fedge_list, pfedge, r_pfedge; | |
790 | bool found_cycle = false; | |
791 | int cycle_start = 0, cycle_end = 0; | |
792 | gcov_type sum_cost = 0, cycle_flow = 0; | |
793 | int new_entry_index; | |
794 | bool propagated = false; | |
795 | ||
796 | gcc_assert (fixup_graph); | |
797 | fnum_vertices = fixup_graph->num_vertices; | |
798 | fnum_edges = fixup_graph->num_edges; | |
799 | fedge_list = fixup_graph->edge_list; | |
800 | new_entry_index = fixup_graph->new_entry_index; | |
801 | ||
802 | /* Initialize. */ | |
803 | /* Skip ENTRY. */ | |
804 | for (i = 1; i < fnum_vertices; i++) | |
805 | { | |
806 | d[i] = CAP_INFINITY; | |
807 | pi[i] = -1; | |
808 | cycle[i] = -1; | |
809 | } | |
810 | d[ENTRY_BLOCK] = 0; | |
811 | ||
812 | /* Relax. */ | |
813 | for (k = 1; k < fnum_vertices; k++) | |
814 | { | |
815 | propagated = false; | |
816 | for (i = 0; i < fnum_edges; i++) | |
817 | { | |
818 | pfedge = fedge_list + i; | |
819 | if (pfedge->src == new_entry_index) | |
820 | continue; | |
821 | if (pfedge->is_rflow_valid && pfedge->rflow | |
822 | && d[pfedge->src] != CAP_INFINITY | |
823 | && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost)) | |
824 | { | |
825 | d[pfedge->dest] = d[pfedge->src] + pfedge->cost; | |
826 | pi[pfedge->dest] = pfedge->src; | |
827 | propagated = true; | |
828 | } | |
829 | } | |
830 | if (!propagated) | |
831 | break; | |
832 | } | |
833 | ||
834 | if (!propagated) | |
835 | /* No negative cycles exist. */ | |
836 | return 0; | |
837 | ||
838 | /* Detect. */ | |
839 | for (i = 0; i < fnum_edges; i++) | |
840 | { | |
841 | pfedge = fedge_list + i; | |
842 | if (pfedge->src == new_entry_index) | |
843 | continue; | |
844 | if (pfedge->is_rflow_valid && pfedge->rflow | |
845 | && d[pfedge->src] != CAP_INFINITY | |
846 | && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost)) | |
847 | { | |
848 | found_cycle = true; | |
849 | break; | |
850 | } | |
851 | } | |
852 | ||
853 | if (!found_cycle) | |
854 | return 0; | |
855 | ||
856 | /* Augment the cycle with the cycle's minimum residual capacity. */ | |
857 | found_cycle = false; | |
858 | cycle[0] = pfedge->dest; | |
859 | j = pfedge->dest; | |
860 | ||
861 | for (i = 1; i < fnum_vertices; i++) | |
862 | { | |
863 | j = pi[j]; | |
864 | cycle[i] = j; | |
865 | for (k = 0; k < i; k++) | |
866 | { | |
867 | 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 | if (found_cycle) | |
877 | break; | |
878 | } | |
879 | ||
880 | gcc_assert (cycle[cycle_start] == cycle[cycle_end]); | |
881 | if (dump_file) | |
882 | fprintf (dump_file, "\nNegative cycle length is %d:\n", | |
883 | cycle_end - cycle_start); | |
884 | ||
885 | sum_cost = 0; | |
886 | cycle_flow = CAP_INFINITY; | |
887 | for (k = cycle_start; k < cycle_end; k++) | |
888 | { | |
889 | pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]); | |
890 | cycle_flow = MIN (cycle_flow, pfedge->rflow); | |
891 | sum_cost += pfedge->cost; | |
892 | if (dump_file) | |
893 | fprintf (dump_file, "%d ", cycle[k]); | |
894 | } | |
895 | ||
896 | if (dump_file) | |
897 | { | |
898 | fprintf (dump_file, "%d", cycle[k]); | |
899 | fprintf (dump_file, | |
16998094 | 900 | ": (%" PRId64 ", %" PRId64 |
f7bc085c L |
901 | ")\n", sum_cost, cycle_flow); |
902 | fprintf (dump_file, | |
16998094 | 903 | "Augment cycle with %" PRId64 "\n", |
f7bc085c L |
904 | cycle_flow); |
905 | } | |
906 | ||
907 | for (k = cycle_start; k < cycle_end; k++) | |
908 | { | |
909 | pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]); | |
910 | r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]); | |
911 | pfedge->rflow -= cycle_flow; | |
912 | if (pfedge->type) | |
913 | pfedge->flow += cycle_flow; | |
914 | r_pfedge->rflow += cycle_flow; | |
915 | if (r_pfedge->type) | |
916 | r_pfedge->flow -= cycle_flow; | |
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 | compute_residual_flow (fixup_graph_type *fixup_graph) | |
928 | { | |
929 | int i; | |
930 | int fnum_edges; | |
931 | fixup_edge_p fedge_list, pfedge; | |
932 | ||
933 | gcc_assert (fixup_graph); | |
934 | ||
935 | if (dump_file) | |
936 | fputs ("\ncompute_residual_flow():\n", dump_file); | |
937 | ||
938 | fnum_edges = fixup_graph->num_edges; | |
939 | fedge_list = fixup_graph->edge_list; | |
940 | ||
941 | for (i = 0; i < fnum_edges; i++) | |
942 | { | |
943 | pfedge = fedge_list + i; | |
944 | pfedge->rflow = pfedge->max_capacity - pfedge->flow; | |
945 | pfedge->is_rflow_valid = true; | |
946 | add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow, | |
947 | -pfedge->cost); | |
948 | } | |
949 | } | |
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 | find_augmenting_path (fixup_graph_type *fixup_graph, | |
960 | augmenting_path_type *augmenting_path, int source, | |
961 | int sink) | |
962 | { | |
963 | int u = 0; | |
964 | int i; | |
965 | fixup_vertex_p fvertex_list, pfvertex; | |
966 | fixup_edge_p pfedge; | |
967 | int *bb_pred, *is_visited; | |
968 | queue_type *queue_list; | |
969 | ||
970 | gcc_assert (augmenting_path); | |
971 | bb_pred = augmenting_path->bb_pred; | |
972 | gcc_assert (bb_pred); | |
973 | is_visited = augmenting_path->is_visited; | |
974 | gcc_assert (is_visited); | |
975 | queue_list = &(augmenting_path->queue_list); | |
976 | ||
977 | gcc_assert (fixup_graph); | |
978 | ||
979 | fvertex_list = fixup_graph->vertex_list; | |
980 | ||
981 | for (u = 0; u < fixup_graph->num_vertices; u++) | |
982 | is_visited[u] = 0; | |
983 | ||
984 | init_queue (queue_list); | |
985 | enqueue (queue_list, source); | |
986 | bb_pred[source] = -1; | |
987 | ||
988 | while (!is_empty (queue_list)) | |
989 | { | |
990 | u = dequeue (queue_list); | |
991 | is_visited[u] = 1; | |
992 | pfvertex = fvertex_list + u; | |
9771b263 | 993 | for (i = 0; pfvertex->succ_edges.iterate (i, &pfedge); |
f7bc085c L |
994 | i++) |
995 | { | |
996 | int dest = pfedge->dest; | |
997 | if ((pfedge->rflow > 0) && (is_visited[dest] == 0)) | |
998 | { | |
999 | enqueue (queue_list, dest); | |
1000 | bb_pred[dest] = u; | |
1001 | is_visited[dest] = 1; | |
1002 | 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. | |
b8698a0f | 1018 | |
f7bc085c L |
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 | find_max_flow (fixup_graph_type *fixup_graph, int source, int sink) | |
1028 | { | |
1029 | int fnum_edges; | |
1030 | augmenting_path_type augmenting_path; | |
1031 | int *bb_pred; | |
1032 | gcov_type max_flow = 0; | |
1033 | int i, u; | |
1034 | fixup_edge_p fedge_list, pfedge, r_pfedge; | |
1035 | ||
1036 | gcc_assert (fixup_graph); | |
1037 | ||
1038 | fnum_edges = fixup_graph->num_edges; | |
1039 | fedge_list = fixup_graph->edge_list; | |
1040 | ||
1041 | /* Initialize flow to 0. */ | |
1042 | for (i = 0; i < fnum_edges; i++) | |
1043 | { | |
1044 | pfedge = fedge_list + i; | |
1045 | pfedge->flow = 0; | |
1046 | } | |
1047 | ||
1048 | compute_residual_flow (fixup_graph); | |
1049 | ||
1050 | init_augmenting_path (&augmenting_path, fixup_graph->num_vertices); | |
1051 | ||
1052 | bb_pred = augmenting_path.bb_pred; | |
1053 | 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 | for (u = sink; u != source; u = bb_pred[u]) | |
1058 | { | |
1059 | pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u); | |
1060 | increment = MIN (increment, pfedge->rflow); | |
1061 | } | |
1062 | max_flow += increment; | |
1063 | ||
1064 | /* Now increment the flow. EXIT vertex index is 1. */ | |
1065 | for (u = sink; u != source; u = bb_pred[u]) | |
1066 | { | |
1067 | pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u); | |
1068 | r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]); | |
1069 | if (pfedge->type) | |
1070 | { | |
1071 | /* forward edge. */ | |
1072 | pfedge->flow += increment; | |
1073 | pfedge->rflow -= increment; | |
1074 | r_pfedge->rflow += increment; | |
1075 | } | |
1076 | else | |
1077 | { | |
1078 | /* backward edge. */ | |
1079 | gcc_assert (r_pfedge->type); | |
1080 | r_pfedge->rflow += increment; | |
1081 | r_pfedge->flow -= increment; | |
1082 | pfedge->rflow -= increment; | |
1083 | } | |
1084 | } | |
1085 | ||
1086 | if (dump_file) | |
1087 | { | |
1088 | fprintf (dump_file, "\nDump augmenting path:\n"); | |
1089 | for (u = sink; u != source; u = bb_pred[u]) | |
1090 | { | |
1091 | print_basic_block (dump_file, fixup_graph, u); | |
1092 | fprintf (dump_file, "<-"); | |
1093 | } | |
1094 | fprintf (dump_file, | |
16998094 | 1095 | "ENTRY (path_capacity=%" PRId64 ")\n", |
f7bc085c L |
1096 | increment); |
1097 | fprintf (dump_file, | |
16998094 | 1098 | "Network flow is %" PRId64 ".\n", |
f7bc085c L |
1099 | max_flow); |
1100 | } | |
1101 | } | |
1102 | ||
1103 | free_augmenting_path (&augmenting_path); | |
1104 | if (dump_file) | |
1105 | dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()"); | |
1106 | return max_flow; | |
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 | adjust_cfg_counts (fixup_graph_type *fixup_graph) | |
1115 | { | |
1116 | basic_block bb; | |
1117 | edge e; | |
1118 | edge_iterator ei; | |
1119 | int i, j; | |
1120 | fixup_edge_p pfedge, pfedge_n; | |
1121 | ||
1122 | gcc_assert (fixup_graph); | |
1123 | ||
1124 | if (dump_file) | |
1125 | fprintf (dump_file, "\nadjust_cfg_counts():\n"); | |
1126 | ||
fefa31b5 DM |
1127 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), |
1128 | EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
f7bc085c L |
1129 | { |
1130 | i = 2 * bb->index; | |
1131 | ||
1132 | /* Fixup BB. */ | |
1133 | if (dump_file) | |
1134 | fprintf (dump_file, | |
3995f3a2 | 1135 | "BB%d: %" PRId64 "", bb->index, bb_gcov_count (bb)); |
f7bc085c L |
1136 | |
1137 | pfedge = find_fixup_edge (fixup_graph, i, i + 1); | |
1138 | if (pfedge->flow) | |
1139 | { | |
3995f3a2 | 1140 | bb_gcov_count (bb) += pfedge->flow; |
f7bc085c L |
1141 | if (dump_file) |
1142 | { | |
16998094 | 1143 | fprintf (dump_file, " + %" PRId64 "(", |
f7bc085c L |
1144 | pfedge->flow); |
1145 | print_edge (dump_file, fixup_graph, i, i + 1); | |
1146 | fprintf (dump_file, ")"); | |
1147 | } | |
1148 | } | |
1149 | ||
1150 | pfedge_n = | |
1151 | find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index); | |
1152 | /* Deduct flow from normalized reverse edge. */ | |
1153 | if (pfedge->norm_vertex_index && pfedge_n->flow) | |
1154 | { | |
3995f3a2 | 1155 | bb_gcov_count (bb) -= pfedge_n->flow; |
f7bc085c L |
1156 | if (dump_file) |
1157 | { | |
16998094 | 1158 | fprintf (dump_file, " - %" PRId64 "(", |
f7bc085c L |
1159 | pfedge_n->flow); |
1160 | print_edge (dump_file, fixup_graph, i + 1, | |
1161 | pfedge->norm_vertex_index); | |
1162 | fprintf (dump_file, ")"); | |
1163 | } | |
1164 | } | |
1165 | if (dump_file) | |
3995f3a2 | 1166 | fprintf (dump_file, " = %" PRId64 "\n", bb_gcov_count (bb)); |
f7bc085c L |
1167 | |
1168 | /* Fixup edge. */ | |
1169 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1170 | { | |
1171 | /* Treat edges with ignore attribute set as if they don't exist. */ | |
1172 | if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) | |
1173 | continue; | |
1174 | ||
1175 | j = 2 * e->dest->index; | |
1176 | if (dump_file) | |
16998094 | 1177 | fprintf (dump_file, "%d->%d: %" PRId64 "", |
3995f3a2 | 1178 | bb->index, e->dest->index, edge_gcov_count (e)); |
f7bc085c L |
1179 | |
1180 | pfedge = find_fixup_edge (fixup_graph, i + 1, j); | |
1181 | ||
1182 | if (bb->index != e->dest->index) | |
1183 | { | |
1184 | /* Non-self edge. */ | |
1185 | if (pfedge->flow) | |
1186 | { | |
3995f3a2 | 1187 | edge_gcov_count (e) += pfedge->flow; |
f7bc085c L |
1188 | if (dump_file) |
1189 | { | |
16998094 | 1190 | fprintf (dump_file, " + %" PRId64 "(", |
f7bc085c L |
1191 | pfedge->flow); |
1192 | print_edge (dump_file, fixup_graph, i + 1, j); | |
1193 | fprintf (dump_file, ")"); | |
1194 | } | |
1195 | } | |
1196 | ||
1197 | pfedge_n = | |
1198 | find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index); | |
1199 | /* Deduct flow from normalized reverse edge. */ | |
1200 | if (pfedge->norm_vertex_index && pfedge_n->flow) | |
1201 | { | |
3995f3a2 | 1202 | edge_gcov_count (e) -= pfedge_n->flow; |
f7bc085c L |
1203 | if (dump_file) |
1204 | { | |
16998094 | 1205 | fprintf (dump_file, " - %" PRId64 "(", |
f7bc085c L |
1206 | pfedge_n->flow); |
1207 | print_edge (dump_file, fixup_graph, j, | |
1208 | pfedge->norm_vertex_index); | |
1209 | 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 | pfedge = find_fixup_edge (fixup_graph, j, i + 1); | |
1218 | pfedge_n = | |
1219 | find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index); | |
3995f3a2 JH |
1220 | edge_gcov_count (e) += pfedge_n->flow; |
1221 | bb_gcov_count (bb) += pfedge_n->flow; | |
f7bc085c L |
1222 | if (dump_file) |
1223 | { | |
1224 | fprintf (dump_file, "(self edge)"); | |
16998094 | 1225 | fprintf (dump_file, " + %" PRId64 "(", |
f7bc085c L |
1226 | pfedge_n->flow); |
1227 | print_edge (dump_file, fixup_graph, i + 1, | |
1228 | pfedge->norm_vertex_index); | |
1229 | fprintf (dump_file, ")"); | |
1230 | } | |
1231 | } | |
1232 | ||
3995f3a2 | 1233 | if (bb_gcov_count (bb)) |
357067f2 JH |
1234 | e->probability = profile_probability::probability_in_gcov_type |
1235 | (edge_gcov_count (e), bb_gcov_count (bb)); | |
f7bc085c | 1236 | if (dump_file) |
357067f2 JH |
1237 | { |
1238 | fprintf (dump_file, " = %" PRId64 "\t", | |
1239 | edge_gcov_count (e)); | |
1240 | e->probability.dump (dump_file); | |
1241 | fprintf (dump_file, "\n"); | |
1242 | } | |
f7bc085c | 1243 | } |
b8698a0f | 1244 | } |
f7bc085c | 1245 | |
3995f3a2 | 1246 | bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun)) = |
fefa31b5 | 1247 | sum_edge_counts (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs); |
3995f3a2 | 1248 | bb_gcov_count (EXIT_BLOCK_PTR_FOR_FN (cfun)) = |
fefa31b5 | 1249 | sum_edge_counts (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds); |
f7bc085c L |
1250 | |
1251 | /* Compute edge probabilities. */ | |
04a90bec | 1252 | FOR_ALL_BB_FN (bb, cfun) |
f7bc085c | 1253 | { |
3995f3a2 | 1254 | if (bb_gcov_count (bb)) |
f7bc085c L |
1255 | { |
1256 | FOR_EACH_EDGE (e, ei, bb->succs) | |
357067f2 JH |
1257 | e->probability = profile_probability::probability_in_gcov_type |
1258 | (edge_gcov_count (e), bb_gcov_count (bb)); | |
f7bc085c L |
1259 | } |
1260 | } | |
1261 | ||
1262 | if (dump_file) | |
1263 | { | |
1264 | fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n", | |
e6d46b5a | 1265 | current_function_name ()); |
11cd3bed | 1266 | FOR_EACH_BB_FN (bb, cfun) |
f7bc085c | 1267 | { |
3995f3a2 JH |
1268 | if ((bb_gcov_count (bb) != sum_edge_counts (bb->preds)) |
1269 | || (bb_gcov_count (bb) != sum_edge_counts (bb->succs))) | |
f7bc085c L |
1270 | { |
1271 | fprintf (dump_file, | |
16998094 | 1272 | "BB%d(%" PRId64 ") **INVALID**: ", |
3995f3a2 | 1273 | bb->index, bb_gcov_count (bb)); |
f7bc085c | 1274 | fprintf (stderr, |
16998094 | 1275 | "******** BB%d(%" PRId64 |
3995f3a2 | 1276 | ") **INVALID**: \n", bb->index, bb_gcov_count (bb)); |
16998094 | 1277 | fprintf (dump_file, "in_edges=%" PRId64 " ", |
f7bc085c | 1278 | sum_edge_counts (bb->preds)); |
16998094 | 1279 | fprintf (dump_file, "out_edges=%" PRId64 "\n", |
f7bc085c L |
1280 | sum_edge_counts (bb->succs)); |
1281 | } | |
1282 | } | |
1283 | } | |
1284 | } | |
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 | find_minimum_cost_flow (fixup_graph_type *fixup_graph) | |
1303 | { | |
1304 | /* Holds the index of predecessor in path. */ | |
1305 | int *pred; | |
1306 | /* Used to hold the minimum cost cycle. */ | |
1307 | int *cycle; | |
1308 | /* Used to record the number of iterations of cancel_negative_cycle. */ | |
1309 | int iteration; | |
1310 | /* Vector d[i] holds the minimum cost of path from i to sink. */ | |
1311 | gcov_type *d; | |
1312 | int fnum_vertices; | |
1313 | int new_exit_index; | |
1314 | int new_entry_index; | |
1315 | ||
1316 | gcc_assert (fixup_graph); | |
1317 | fnum_vertices = fixup_graph->num_vertices; | |
1318 | new_exit_index = fixup_graph->new_exit_index; | |
1319 | new_entry_index = fixup_graph->new_entry_index; | |
1320 | ||
1321 | find_max_flow (fixup_graph, new_entry_index, new_exit_index); | |
1322 | ||
1323 | /* Initialize the structures for find_negative_cycle(). */ | |
1324 | pred = (int *) xcalloc (fnum_vertices, sizeof (int)); | |
1325 | d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type)); | |
1326 | 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 | iteration = 0; | |
1332 | while (cancel_negative_cycle (fixup_graph, pred, d, cycle)) | |
1333 | { | |
1334 | iteration++; | |
1335 | if (iteration > MAX_ITER (fixup_graph->num_vertices, | |
1336 | fixup_graph->num_edges)) | |
1337 | break; | |
1338 | } | |
1339 | ||
1340 | if (dump_file) | |
1341 | dump_fixup_graph (dump_file, fixup_graph, | |
1342 | "After find_minimum_cost_flow()"); | |
1343 | ||
1344 | /* Cleanup structures. */ | |
1345 | free (pred); | |
1346 | free (d); | |
1347 | free (cycle); | |
1348 | } | |
1349 | ||
1350 | ||
1351 | /* Compute the sum of the edge counts in TO_EDGES. */ | |
1352 | ||
1353 | gcov_type | |
9771b263 | 1354 | sum_edge_counts (vec<edge, va_gc> *to_edges) |
f7bc085c L |
1355 | { |
1356 | gcov_type sum = 0; | |
1357 | edge e; | |
1358 | edge_iterator ei; | |
1359 | ||
1360 | FOR_EACH_EDGE (e, ei, to_edges) | |
1361 | { | |
1362 | if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) | |
1363 | continue; | |
3995f3a2 | 1364 | sum += edge_gcov_count (e); |
f7bc085c L |
1365 | } |
1366 | return sum; | |
1367 | } | |
1368 | ||
1369 | ||
073a8998 | 1370 | /* Main routine. Smoothes the initial assigned basic block and edge counts using |
f7bc085c L |
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 | mcf_smooth_cfg (void) | |
1377 | { | |
1378 | fixup_graph_type fixup_graph; | |
1379 | memset (&fixup_graph, 0, sizeof (fixup_graph)); | |
1380 | create_fixup_graph (&fixup_graph); | |
1381 | find_minimum_cost_flow (&fixup_graph); | |
1382 | adjust_cfg_counts (&fixup_graph); | |
1383 | delete_fixup_graph (&fixup_graph); | |
1384 | } |