Mercurial > hg > CbC > CbC_gcc
comparison gcc/mcf.c @ 0:a06113de4d67
first commit
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 17 Jul 2009 14:47:48 +0900 |
parents | |
children | 77e2b8dfacca |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a06113de4d67 |
---|---|
1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth | |
2 basic block and edge frequency counts. | |
3 Copyright (C) 2008 | |
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" | |
51 #include "output.h" | |
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. */ | |
59 #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT) | |
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 | |
391 add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest, int type, | |
392 gcov_type weight, gcov_type cost, gcov_type max_capacity) | |
393 { | |
394 fixup_edge_p curr_edge = add_edge(fixup_graph, src, dest, cost); | |
395 curr_edge->type = type; | |
396 curr_edge->weight = weight; | |
397 curr_edge->max_capacity = max_capacity; | |
398 } | |
399 | |
400 | |
401 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST | |
402 to the fixup graph. */ | |
403 | |
404 static void | |
405 add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest, | |
406 gcov_type rflow, gcov_type cost) | |
407 { | |
408 fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost); | |
409 curr_edge->rflow = rflow; | |
410 curr_edge->is_rflow_valid = true; | |
411 /* This edge is not a valid edge - merely used to hold residual flow. */ | |
412 curr_edge->type = INVALID_EDGE; | |
413 } | |
414 | |
415 | |
416 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not | |
417 exist in the FIXUP_GRAPH. */ | |
418 | |
419 static fixup_edge_p | |
420 find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest) | |
421 { | |
422 int j; | |
423 fixup_edge_p pfedge; | |
424 fixup_vertex_p pfvertex; | |
425 | |
426 gcc_assert (src < fixup_graph->num_vertices); | |
427 | |
428 pfvertex = fixup_graph->vertex_list + src; | |
429 | |
430 for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge); | |
431 j++) | |
432 if (pfedge->dest == dest) | |
433 return pfedge; | |
434 | |
435 return NULL; | |
436 } | |
437 | |
438 | |
439 /* Cleanup routine to free structures in FIXUP_GRAPH. */ | |
440 | |
441 static void | |
442 delete_fixup_graph (fixup_graph_type *fixup_graph) | |
443 { | |
444 int i; | |
445 int fnum_vertices = fixup_graph->num_vertices; | |
446 fixup_vertex_p pfvertex = fixup_graph->vertex_list; | |
447 | |
448 for (i = 0; i < fnum_vertices; i++, pfvertex++) | |
449 VEC_free (fixup_edge_p, heap, pfvertex->succ_edges); | |
450 | |
451 free (fixup_graph->vertex_list); | |
452 free (fixup_graph->edge_list); | |
453 } | |
454 | |
455 | |
456 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */ | |
457 | |
458 static void | |
459 create_fixup_graph (fixup_graph_type *fixup_graph) | |
460 { | |
461 double sqrt_avg_vertex_weight = 0; | |
462 double total_vertex_weight = 0; | |
463 double k_pos = 0; | |
464 double k_neg = 0; | |
465 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */ | |
466 gcov_type *diff_out_in = NULL; | |
467 gcov_type supply_value = 1, demand_value = 0; | |
468 gcov_type fcost = 0; | |
469 int new_entry_index = 0, new_exit_index = 0; | |
470 int i = 0, j = 0; | |
471 int new_index = 0; | |
472 basic_block bb; | |
473 edge e; | |
474 edge_iterator ei; | |
475 fixup_edge_p pfedge, r_pfedge; | |
476 fixup_edge_p fedge_list; | |
477 int fnum_edges; | |
478 | |
479 /* Each basic_block will be split into 2 during vertex transformation. */ | |
480 int fnum_vertices_after_transform = 2 * n_basic_blocks; | |
481 int fnum_edges_after_transform = n_edges + n_basic_blocks; | |
482 | |
483 /* Count the new SOURCE and EXIT vertices to be added. */ | |
484 int fmax_num_vertices = | |
485 fnum_vertices_after_transform + n_edges + n_basic_blocks + 2; | |
486 | |
487 /* In create_fixup_graph: Each basic block and edge can be split into 3 | |
488 edges. Number of balance edges = n_basic_blocks. So after | |
489 create_fixup_graph: | |
490 max_edges = 4 * n_basic_blocks + 3 * n_edges | |
491 Accounting for residual flow edges | |
492 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges) | |
493 = 8 * n_basic_blocks + 6 * n_edges | |
494 < 8 * n_basic_blocks + 8 * n_edges. */ | |
495 int fmax_num_edges = 8 * (n_basic_blocks + n_edges); | |
496 | |
497 /* Initial num of vertices in the fixup graph. */ | |
498 fixup_graph->num_vertices = n_basic_blocks; | |
499 | |
500 /* Fixup graph vertex list. */ | |
501 fixup_graph->vertex_list = | |
502 (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type)); | |
503 | |
504 /* Fixup graph edge list. */ | |
505 fixup_graph->edge_list = | |
506 (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type)); | |
507 | |
508 diff_out_in = | |
509 (gcov_type *) xcalloc (1 + fnum_vertices_after_transform, | |
510 sizeof (gcov_type)); | |
511 | |
512 /* Compute constants b, k_pos, k_neg used in the cost function calculation. | |
513 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */ | |
514 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
515 total_vertex_weight += bb->count; | |
516 | |
517 sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / n_basic_blocks); | |
518 | |
519 k_pos = K_POS (sqrt_avg_vertex_weight); | |
520 k_neg = K_NEG (sqrt_avg_vertex_weight); | |
521 | |
522 /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'', | |
523 connected by an edge e from v' to v''. w(e) = w(v). */ | |
524 | |
525 if (dump_file) | |
526 fprintf (dump_file, "\nVertex transformation:\n"); | |
527 | |
528 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
529 { | |
530 /* v'->v'': index1->(index1+1). */ | |
531 i = 2 * bb->index; | |
532 fcost = (gcov_type) COST (k_pos, bb->count); | |
533 add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count, | |
534 fcost, CAP_INFINITY); | |
535 fixup_graph->num_vertices++; | |
536 | |
537 FOR_EACH_EDGE (e, ei, bb->succs) | |
538 { | |
539 /* Edges with ignore attribute set should be treated like they don't | |
540 exist. */ | |
541 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) | |
542 continue; | |
543 j = 2 * e->dest->index; | |
544 fcost = (gcov_type) COST (k_pos, e->count); | |
545 add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost, | |
546 CAP_INFINITY); | |
547 } | |
548 } | |
549 | |
550 /* After vertex transformation. */ | |
551 gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform); | |
552 /* Redirect edges are not added for edges with ignore attribute. */ | |
553 gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform); | |
554 | |
555 fnum_edges_after_transform = fixup_graph->num_edges; | |
556 | |
557 /* 2. Initialize D(v). */ | |
558 for (i = 0; i < fnum_edges_after_transform; i++) | |
559 { | |
560 pfedge = fixup_graph->edge_list + i; | |
561 diff_out_in[pfedge->src] += pfedge->weight; | |
562 diff_out_in[pfedge->dest] -= pfedge->weight; | |
563 } | |
564 | |
565 /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */ | |
566 for (i = 0; i <= 3; i++) | |
567 diff_out_in[i] = 0; | |
568 | |
569 /* 3. Add reverse edges: needed to decrease counts during smoothing. */ | |
570 if (dump_file) | |
571 fprintf (dump_file, "\nReverse edges:\n"); | |
572 for (i = 0; i < fnum_edges_after_transform; i++) | |
573 { | |
574 pfedge = fixup_graph->edge_list + i; | |
575 if ((pfedge->src == 0) || (pfedge->src == 2)) | |
576 continue; | |
577 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src); | |
578 if (!r_pfedge && pfedge->weight) | |
579 { | |
580 /* Skip adding reverse edges for edges with w(e) = 0, as its maximum | |
581 capacity is 0. */ | |
582 fcost = (gcov_type) COST (k_neg, pfedge->weight); | |
583 add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src, | |
584 REVERSE_EDGE, 0, fcost, pfedge->weight); | |
585 } | |
586 } | |
587 | |
588 /* 4. Create single source and sink. Connect new source vertex s' to function | |
589 entry block. Connect sink vertex t' to function exit. */ | |
590 if (dump_file) | |
591 fprintf (dump_file, "\ns'->S, T->t':\n"); | |
592 | |
593 new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices; | |
594 fixup_graph->num_vertices++; | |
595 /* Set supply_value to 1 to avoid zero count function ENTRY. */ | |
596 add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE, | |
597 1 /* supply_value */, 0, 1 /* supply_value */); | |
598 | |
599 /* Create new exit with EXIT_BLOCK as single pred. */ | |
600 new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices; | |
601 fixup_graph->num_vertices++; | |
602 add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index, | |
603 SINK_CONNECT_EDGE, | |
604 0 /* demand_value */, 0, 0 /* demand_value */); | |
605 | |
606 /* Connect vertices with unbalanced D(v) to source/sink. */ | |
607 if (dump_file) | |
608 fprintf (dump_file, "\nD(v) balance:\n"); | |
609 /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4. | |
610 diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2. */ | |
611 for (i = 4; i < new_entry_index; i += 2) | |
612 { | |
613 if (diff_out_in[i] > 0) | |
614 { | |
615 add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0, | |
616 diff_out_in[i]); | |
617 demand_value += diff_out_in[i]; | |
618 } | |
619 else if (diff_out_in[i] < 0) | |
620 { | |
621 add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0, | |
622 -diff_out_in[i]); | |
623 supply_value -= diff_out_in[i]; | |
624 } | |
625 } | |
626 | |
627 /* Set supply = demand. */ | |
628 if (dump_file) | |
629 { | |
630 fprintf (dump_file, "\nAdjust supply and demand:\n"); | |
631 fprintf (dump_file, "supply_value=" HOST_WIDEST_INT_PRINT_DEC "\n", | |
632 supply_value); | |
633 fprintf (dump_file, "demand_value=" HOST_WIDEST_INT_PRINT_DEC "\n", | |
634 demand_value); | |
635 } | |
636 | |
637 if (demand_value > supply_value) | |
638 { | |
639 pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK); | |
640 pfedge->max_capacity += (demand_value - supply_value); | |
641 } | |
642 else | |
643 { | |
644 pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index); | |
645 pfedge->max_capacity += (supply_value - demand_value); | |
646 } | |
647 | |
648 /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are | |
649 created by the vertex transformation step from self-edges in the original | |
650 CFG and by the reverse edges added earlier. */ | |
651 if (dump_file) | |
652 fprintf (dump_file, "\nNormalize edges:\n"); | |
653 | |
654 fnum_edges = fixup_graph->num_edges; | |
655 fedge_list = fixup_graph->edge_list; | |
656 | |
657 for (i = 0; i < fnum_edges; i++) | |
658 { | |
659 pfedge = fedge_list + i; | |
660 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src); | |
661 if (((pfedge->type == VERTEX_SPLIT_EDGE) | |
662 || (pfedge->type == REDIRECT_EDGE)) && r_pfedge) | |
663 { | |
664 new_index = fixup_graph->num_vertices; | |
665 fixup_graph->num_vertices++; | |
666 | |
667 if (dump_file) | |
668 { | |
669 fprintf (dump_file, "\nAnti-parallel edge:\n"); | |
670 dump_fixup_edge (dump_file, fixup_graph, pfedge); | |
671 dump_fixup_edge (dump_file, fixup_graph, r_pfedge); | |
672 fprintf (dump_file, "New vertex is %d.\n", new_index); | |
673 fprintf (dump_file, "------------------\n"); | |
674 } | |
675 | |
676 pfedge->cost /= 2; | |
677 pfedge->norm_vertex_index = new_index; | |
678 if (dump_file) | |
679 { | |
680 fprintf (dump_file, "After normalization:\n"); | |
681 dump_fixup_edge (dump_file, fixup_graph, pfedge); | |
682 } | |
683 | |
684 /* Add a new fixup edge: new_index->src. */ | |
685 add_fixup_edge (fixup_graph, new_index, pfedge->src, | |
686 REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost, | |
687 r_pfedge->max_capacity); | |
688 gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices); | |
689 | |
690 /* Edge: r_pfedge->src -> r_pfedge->dest | |
691 ==> r_pfedge->src -> new_index. */ | |
692 r_pfedge->dest = new_index; | |
693 r_pfedge->type = REVERSE_NORMALIZED_EDGE; | |
694 r_pfedge->cost = pfedge->cost; | |
695 r_pfedge->max_capacity = pfedge->max_capacity; | |
696 if (dump_file) | |
697 dump_fixup_edge (dump_file, fixup_graph, r_pfedge); | |
698 } | |
699 } | |
700 | |
701 if (dump_file) | |
702 dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()"); | |
703 | |
704 /* Cleanup. */ | |
705 free (diff_out_in); | |
706 } | |
707 | |
708 | |
709 /* Allocates space for the structures in AUGMENTING_PATH. The space needed is | |
710 proportional to the number of nodes in the graph, which is given by | |
711 GRAPH_SIZE. */ | |
712 | |
713 static void | |
714 init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size) | |
715 { | |
716 augmenting_path->queue_list.queue = (int *) | |
717 xcalloc (graph_size + 2, sizeof (int)); | |
718 augmenting_path->queue_list.size = graph_size + 2; | |
719 augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int)); | |
720 augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int)); | |
721 } | |
722 | |
723 /* Free the structures in AUGMENTING_PATH. */ | |
724 static void | |
725 free_augmenting_path (augmenting_path_type *augmenting_path) | |
726 { | |
727 free (augmenting_path->queue_list.queue); | |
728 free (augmenting_path->bb_pred); | |
729 free (augmenting_path->is_visited); | |
730 } | |
731 | |
732 | |
733 /* Queue routines. Assumes queue will never overflow. */ | |
734 | |
735 static void | |
736 init_queue (queue_type *queue_list) | |
737 { | |
738 gcc_assert (queue_list); | |
739 queue_list->head = 0; | |
740 queue_list->tail = 0; | |
741 } | |
742 | |
743 /* Return true if QUEUE_LIST is empty. */ | |
744 static bool | |
745 is_empty (queue_type *queue_list) | |
746 { | |
747 return (queue_list->head == queue_list->tail); | |
748 } | |
749 | |
750 /* Insert element X into QUEUE_LIST. */ | |
751 static void | |
752 enqueue (queue_type *queue_list, int x) | |
753 { | |
754 gcc_assert (queue_list->tail < queue_list->size); | |
755 queue_list->queue[queue_list->tail] = x; | |
756 (queue_list->tail)++; | |
757 } | |
758 | |
759 /* Return the first element in QUEUE_LIST. */ | |
760 static int | |
761 dequeue (queue_type *queue_list) | |
762 { | |
763 int x; | |
764 gcc_assert (queue_list->head >= 0); | |
765 x = queue_list->queue[queue_list->head]; | |
766 (queue_list->head)++; | |
767 return x; | |
768 } | |
769 | |
770 | |
771 /* Finds a negative cycle in the residual network using | |
772 the Bellman-Ford algorithm. The flow on the found cycle is reversed by the | |
773 minimum residual capacity of that cycle. ENTRY and EXIT vertices are not | |
774 considered. | |
775 | |
776 Parameters: | |
777 FIXUP_GRAPH - Residual graph (input/output) | |
778 The following are allocated/freed by the caller: | |
779 PI - Vector to hold predecessors in path (pi = pred index) | |
780 D - D[I] holds minimum cost of path from i to sink | |
781 CYCLE - Vector to hold the minimum cost cycle | |
782 | |
783 Return: | |
784 true if a negative cycle was found, false otherwise. */ | |
785 | |
786 static bool | |
787 cancel_negative_cycle (fixup_graph_type *fixup_graph, | |
788 int *pi, gcov_type *d, int *cycle) | |
789 { | |
790 int i, j, k; | |
791 int fnum_vertices, fnum_edges; | |
792 fixup_edge_p fedge_list, pfedge, r_pfedge; | |
793 bool found_cycle = false; | |
794 int cycle_start = 0, cycle_end = 0; | |
795 gcov_type sum_cost = 0, cycle_flow = 0; | |
796 int new_entry_index; | |
797 bool propagated = false; | |
798 | |
799 gcc_assert (fixup_graph); | |
800 fnum_vertices = fixup_graph->num_vertices; | |
801 fnum_edges = fixup_graph->num_edges; | |
802 fedge_list = fixup_graph->edge_list; | |
803 new_entry_index = fixup_graph->new_entry_index; | |
804 | |
805 /* Initialize. */ | |
806 /* Skip ENTRY. */ | |
807 for (i = 1; i < fnum_vertices; i++) | |
808 { | |
809 d[i] = CAP_INFINITY; | |
810 pi[i] = -1; | |
811 cycle[i] = -1; | |
812 } | |
813 d[ENTRY_BLOCK] = 0; | |
814 | |
815 /* Relax. */ | |
816 for (k = 1; k < fnum_vertices; k++) | |
817 { | |
818 propagated = false; | |
819 for (i = 0; i < fnum_edges; i++) | |
820 { | |
821 pfedge = fedge_list + i; | |
822 if (pfedge->src == new_entry_index) | |
823 continue; | |
824 if (pfedge->is_rflow_valid && pfedge->rflow | |
825 && d[pfedge->src] != CAP_INFINITY | |
826 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost)) | |
827 { | |
828 d[pfedge->dest] = d[pfedge->src] + pfedge->cost; | |
829 pi[pfedge->dest] = pfedge->src; | |
830 propagated = true; | |
831 } | |
832 } | |
833 if (!propagated) | |
834 break; | |
835 } | |
836 | |
837 if (!propagated) | |
838 /* No negative cycles exist. */ | |
839 return 0; | |
840 | |
841 /* Detect. */ | |
842 for (i = 0; i < fnum_edges; i++) | |
843 { | |
844 pfedge = fedge_list + i; | |
845 if (pfedge->src == new_entry_index) | |
846 continue; | |
847 if (pfedge->is_rflow_valid && pfedge->rflow | |
848 && d[pfedge->src] != CAP_INFINITY | |
849 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost)) | |
850 { | |
851 found_cycle = true; | |
852 break; | |
853 } | |
854 } | |
855 | |
856 if (!found_cycle) | |
857 return 0; | |
858 | |
859 /* Augment the cycle with the cycle's minimum residual capacity. */ | |
860 found_cycle = false; | |
861 cycle[0] = pfedge->dest; | |
862 j = pfedge->dest; | |
863 | |
864 for (i = 1; i < fnum_vertices; i++) | |
865 { | |
866 j = pi[j]; | |
867 cycle[i] = j; | |
868 for (k = 0; k < i; k++) | |
869 { | |
870 if (cycle[k] == j) | |
871 { | |
872 /* cycle[k] -> ... -> cycle[i]. */ | |
873 cycle_start = k; | |
874 cycle_end = i; | |
875 found_cycle = true; | |
876 break; | |
877 } | |
878 } | |
879 if (found_cycle) | |
880 break; | |
881 } | |
882 | |
883 gcc_assert (cycle[cycle_start] == cycle[cycle_end]); | |
884 if (dump_file) | |
885 fprintf (dump_file, "\nNegative cycle length is %d:\n", | |
886 cycle_end - cycle_start); | |
887 | |
888 sum_cost = 0; | |
889 cycle_flow = CAP_INFINITY; | |
890 for (k = cycle_start; k < cycle_end; k++) | |
891 { | |
892 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]); | |
893 cycle_flow = MIN (cycle_flow, pfedge->rflow); | |
894 sum_cost += pfedge->cost; | |
895 if (dump_file) | |
896 fprintf (dump_file, "%d ", cycle[k]); | |
897 } | |
898 | |
899 if (dump_file) | |
900 { | |
901 fprintf (dump_file, "%d", cycle[k]); | |
902 fprintf (dump_file, | |
903 ": (" HOST_WIDEST_INT_PRINT_DEC ", " HOST_WIDEST_INT_PRINT_DEC | |
904 ")\n", sum_cost, cycle_flow); | |
905 fprintf (dump_file, | |
906 "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC "\n", | |
907 cycle_flow); | |
908 } | |
909 | |
910 for (k = cycle_start; k < cycle_end; k++) | |
911 { | |
912 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]); | |
913 r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]); | |
914 pfedge->rflow -= cycle_flow; | |
915 if (pfedge->type) | |
916 pfedge->flow += cycle_flow; | |
917 r_pfedge->rflow += cycle_flow; | |
918 if (r_pfedge->type) | |
919 r_pfedge->flow -= cycle_flow; | |
920 } | |
921 | |
922 return true; | |
923 } | |
924 | |
925 | |
926 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of | |
927 the edges. ENTRY and EXIT vertices should not be considered. */ | |
928 | |
929 static void | |
930 compute_residual_flow (fixup_graph_type *fixup_graph) | |
931 { | |
932 int i; | |
933 int fnum_edges; | |
934 fixup_edge_p fedge_list, pfedge; | |
935 | |
936 gcc_assert (fixup_graph); | |
937 | |
938 if (dump_file) | |
939 fputs ("\ncompute_residual_flow():\n", dump_file); | |
940 | |
941 fnum_edges = fixup_graph->num_edges; | |
942 fedge_list = fixup_graph->edge_list; | |
943 | |
944 for (i = 0; i < fnum_edges; i++) | |
945 { | |
946 pfedge = fedge_list + i; | |
947 pfedge->rflow = pfedge->max_capacity - pfedge->flow; | |
948 pfedge->is_rflow_valid = true; | |
949 add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow, | |
950 -pfedge->cost); | |
951 } | |
952 } | |
953 | |
954 | |
955 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to | |
956 SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by | |
957 this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated | |
958 to reflect the path found. | |
959 Returns: 0 if no augmenting path is found, 1 otherwise. */ | |
960 | |
961 static int | |
962 find_augmenting_path (fixup_graph_type *fixup_graph, | |
963 augmenting_path_type *augmenting_path, int source, | |
964 int sink) | |
965 { | |
966 int u = 0; | |
967 int i; | |
968 fixup_vertex_p fvertex_list, pfvertex; | |
969 fixup_edge_p pfedge; | |
970 int *bb_pred, *is_visited; | |
971 queue_type *queue_list; | |
972 | |
973 gcc_assert (augmenting_path); | |
974 bb_pred = augmenting_path->bb_pred; | |
975 gcc_assert (bb_pred); | |
976 is_visited = augmenting_path->is_visited; | |
977 gcc_assert (is_visited); | |
978 queue_list = &(augmenting_path->queue_list); | |
979 | |
980 gcc_assert (fixup_graph); | |
981 | |
982 fvertex_list = fixup_graph->vertex_list; | |
983 | |
984 for (u = 0; u < fixup_graph->num_vertices; u++) | |
985 is_visited[u] = 0; | |
986 | |
987 init_queue (queue_list); | |
988 enqueue (queue_list, source); | |
989 bb_pred[source] = -1; | |
990 | |
991 while (!is_empty (queue_list)) | |
992 { | |
993 u = dequeue (queue_list); | |
994 is_visited[u] = 1; | |
995 pfvertex = fvertex_list + u; | |
996 for (i = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, i, pfedge); | |
997 i++) | |
998 { | |
999 int dest = pfedge->dest; | |
1000 if ((pfedge->rflow > 0) && (is_visited[dest] == 0)) | |
1001 { | |
1002 enqueue (queue_list, dest); | |
1003 bb_pred[dest] = u; | |
1004 is_visited[dest] = 1; | |
1005 if (dest == sink) | |
1006 return 1; | |
1007 } | |
1008 } | |
1009 } | |
1010 | |
1011 return 0; | |
1012 } | |
1013 | |
1014 | |
1015 /* Routine to find the maximal flow: | |
1016 Algorithm: | |
1017 1. Initialize flow to 0 | |
1018 2. Find an augmenting path form source to sink. | |
1019 3. Send flow equal to the path's residual capacity along the edges of this path. | |
1020 4. Repeat steps 2 and 3 until no new augmenting path is found. | |
1021 | |
1022 Parameters: | |
1023 SOURCE: index of source vertex (input) | |
1024 SINK: index of sink vertex (input) | |
1025 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be | |
1026 set to have a valid maximal flow by this routine. (input) | |
1027 Return: Maximum flow possible. */ | |
1028 | |
1029 static gcov_type | |
1030 find_max_flow (fixup_graph_type *fixup_graph, int source, int sink) | |
1031 { | |
1032 int fnum_edges; | |
1033 augmenting_path_type augmenting_path; | |
1034 int *bb_pred; | |
1035 gcov_type max_flow = 0; | |
1036 int i, u; | |
1037 fixup_edge_p fedge_list, pfedge, r_pfedge; | |
1038 | |
1039 gcc_assert (fixup_graph); | |
1040 | |
1041 fnum_edges = fixup_graph->num_edges; | |
1042 fedge_list = fixup_graph->edge_list; | |
1043 | |
1044 /* Initialize flow to 0. */ | |
1045 for (i = 0; i < fnum_edges; i++) | |
1046 { | |
1047 pfedge = fedge_list + i; | |
1048 pfedge->flow = 0; | |
1049 } | |
1050 | |
1051 compute_residual_flow (fixup_graph); | |
1052 | |
1053 init_augmenting_path (&augmenting_path, fixup_graph->num_vertices); | |
1054 | |
1055 bb_pred = augmenting_path.bb_pred; | |
1056 while (find_augmenting_path (fixup_graph, &augmenting_path, source, sink)) | |
1057 { | |
1058 /* Determine the amount by which we can increment the flow. */ | |
1059 gcov_type increment = CAP_INFINITY; | |
1060 for (u = sink; u != source; u = bb_pred[u]) | |
1061 { | |
1062 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u); | |
1063 increment = MIN (increment, pfedge->rflow); | |
1064 } | |
1065 max_flow += increment; | |
1066 | |
1067 /* Now increment the flow. EXIT vertex index is 1. */ | |
1068 for (u = sink; u != source; u = bb_pred[u]) | |
1069 { | |
1070 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u); | |
1071 r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]); | |
1072 if (pfedge->type) | |
1073 { | |
1074 /* forward edge. */ | |
1075 pfedge->flow += increment; | |
1076 pfedge->rflow -= increment; | |
1077 r_pfedge->rflow += increment; | |
1078 } | |
1079 else | |
1080 { | |
1081 /* backward edge. */ | |
1082 gcc_assert (r_pfedge->type); | |
1083 r_pfedge->rflow += increment; | |
1084 r_pfedge->flow -= increment; | |
1085 pfedge->rflow -= increment; | |
1086 } | |
1087 } | |
1088 | |
1089 if (dump_file) | |
1090 { | |
1091 fprintf (dump_file, "\nDump augmenting path:\n"); | |
1092 for (u = sink; u != source; u = bb_pred[u]) | |
1093 { | |
1094 print_basic_block (dump_file, fixup_graph, u); | |
1095 fprintf (dump_file, "<-"); | |
1096 } | |
1097 fprintf (dump_file, | |
1098 "ENTRY (path_capacity=" HOST_WIDEST_INT_PRINT_DEC ")\n", | |
1099 increment); | |
1100 fprintf (dump_file, | |
1101 "Network flow is " HOST_WIDEST_INT_PRINT_DEC ".\n", | |
1102 max_flow); | |
1103 } | |
1104 } | |
1105 | |
1106 free_augmenting_path (&augmenting_path); | |
1107 if (dump_file) | |
1108 dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()"); | |
1109 return max_flow; | |
1110 } | |
1111 | |
1112 | |
1113 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH | |
1114 after applying the find_minimum_cost_flow() routine. */ | |
1115 | |
1116 static void | |
1117 adjust_cfg_counts (fixup_graph_type *fixup_graph) | |
1118 { | |
1119 basic_block bb; | |
1120 edge e; | |
1121 edge_iterator ei; | |
1122 int i, j; | |
1123 fixup_edge_p pfedge, pfedge_n; | |
1124 | |
1125 gcc_assert (fixup_graph); | |
1126 | |
1127 if (dump_file) | |
1128 fprintf (dump_file, "\nadjust_cfg_counts():\n"); | |
1129 | |
1130 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) | |
1131 { | |
1132 i = 2 * bb->index; | |
1133 | |
1134 /* Fixup BB. */ | |
1135 if (dump_file) | |
1136 fprintf (dump_file, | |
1137 "BB%d: " HOST_WIDEST_INT_PRINT_DEC "", bb->index, bb->count); | |
1138 | |
1139 pfedge = find_fixup_edge (fixup_graph, i, i + 1); | |
1140 if (pfedge->flow) | |
1141 { | |
1142 bb->count += pfedge->flow; | |
1143 if (dump_file) | |
1144 { | |
1145 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(", | |
1146 pfedge->flow); | |
1147 print_edge (dump_file, fixup_graph, i, i + 1); | |
1148 fprintf (dump_file, ")"); | |
1149 } | |
1150 } | |
1151 | |
1152 pfedge_n = | |
1153 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index); | |
1154 /* Deduct flow from normalized reverse edge. */ | |
1155 if (pfedge->norm_vertex_index && pfedge_n->flow) | |
1156 { | |
1157 bb->count -= pfedge_n->flow; | |
1158 if (dump_file) | |
1159 { | |
1160 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(", | |
1161 pfedge_n->flow); | |
1162 print_edge (dump_file, fixup_graph, i + 1, | |
1163 pfedge->norm_vertex_index); | |
1164 fprintf (dump_file, ")"); | |
1165 } | |
1166 } | |
1167 if (dump_file) | |
1168 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\n", bb->count); | |
1169 | |
1170 /* Fixup edge. */ | |
1171 FOR_EACH_EDGE (e, ei, bb->succs) | |
1172 { | |
1173 /* Treat edges with ignore attribute set as if they don't exist. */ | |
1174 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) | |
1175 continue; | |
1176 | |
1177 j = 2 * e->dest->index; | |
1178 if (dump_file) | |
1179 fprintf (dump_file, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC "", | |
1180 bb->index, e->dest->index, e->count); | |
1181 | |
1182 pfedge = find_fixup_edge (fixup_graph, i + 1, j); | |
1183 | |
1184 if (bb->index != e->dest->index) | |
1185 { | |
1186 /* Non-self edge. */ | |
1187 if (pfedge->flow) | |
1188 { | |
1189 e->count += pfedge->flow; | |
1190 if (dump_file) | |
1191 { | |
1192 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(", | |
1193 pfedge->flow); | |
1194 print_edge (dump_file, fixup_graph, i + 1, j); | |
1195 fprintf (dump_file, ")"); | |
1196 } | |
1197 } | |
1198 | |
1199 pfedge_n = | |
1200 find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index); | |
1201 /* Deduct flow from normalized reverse edge. */ | |
1202 if (pfedge->norm_vertex_index && pfedge_n->flow) | |
1203 { | |
1204 e->count -= pfedge_n->flow; | |
1205 if (dump_file) | |
1206 { | |
1207 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(", | |
1208 pfedge_n->flow); | |
1209 print_edge (dump_file, fixup_graph, j, | |
1210 pfedge->norm_vertex_index); | |
1211 fprintf (dump_file, ")"); | |
1212 } | |
1213 } | |
1214 } | |
1215 else | |
1216 { | |
1217 /* Handle self edges. Self edge is split with a normalization | |
1218 vertex. Here i=j. */ | |
1219 pfedge = find_fixup_edge (fixup_graph, j, i + 1); | |
1220 pfedge_n = | |
1221 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index); | |
1222 e->count += pfedge_n->flow; | |
1223 bb->count += pfedge_n->flow; | |
1224 if (dump_file) | |
1225 { | |
1226 fprintf (dump_file, "(self edge)"); | |
1227 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(", | |
1228 pfedge_n->flow); | |
1229 print_edge (dump_file, fixup_graph, i + 1, | |
1230 pfedge->norm_vertex_index); | |
1231 fprintf (dump_file, ")"); | |
1232 } | |
1233 } | |
1234 | |
1235 if (bb->count) | |
1236 e->probability = REG_BR_PROB_BASE * e->count / bb->count; | |
1237 if (dump_file) | |
1238 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\t(%.1f%%)\n", | |
1239 e->count, e->probability * 100.0 / REG_BR_PROB_BASE); | |
1240 } | |
1241 } | |
1242 | |
1243 ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs); | |
1244 EXIT_BLOCK_PTR->count = sum_edge_counts (EXIT_BLOCK_PTR->preds); | |
1245 | |
1246 /* Compute edge probabilities. */ | |
1247 FOR_ALL_BB (bb) | |
1248 { | |
1249 if (bb->count) | |
1250 { | |
1251 FOR_EACH_EDGE (e, ei, bb->succs) | |
1252 e->probability = REG_BR_PROB_BASE * e->count / bb->count; | |
1253 } | |
1254 else | |
1255 { | |
1256 int total = 0; | |
1257 FOR_EACH_EDGE (e, ei, bb->succs) | |
1258 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) | |
1259 total++; | |
1260 if (total) | |
1261 { | |
1262 FOR_EACH_EDGE (e, ei, bb->succs) | |
1263 { | |
1264 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) | |
1265 e->probability = REG_BR_PROB_BASE / total; | |
1266 else | |
1267 e->probability = 0; | |
1268 } | |
1269 } | |
1270 else | |
1271 { | |
1272 total += EDGE_COUNT (bb->succs); | |
1273 FOR_EACH_EDGE (e, ei, bb->succs) | |
1274 e->probability = REG_BR_PROB_BASE / total; | |
1275 } | |
1276 } | |
1277 } | |
1278 | |
1279 if (dump_file) | |
1280 { | |
1281 fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n", | |
1282 lang_hooks.decl_printable_name (current_function_decl, 2)); | |
1283 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb) | |
1284 { | |
1285 if ((bb->count != sum_edge_counts (bb->preds)) | |
1286 || (bb->count != sum_edge_counts (bb->succs))) | |
1287 { | |
1288 fprintf (dump_file, | |
1289 "BB%d(" HOST_WIDEST_INT_PRINT_DEC ") **INVALID**: ", | |
1290 bb->index, bb->count); | |
1291 fprintf (stderr, | |
1292 "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC | |
1293 ") **INVALID**: \n", bb->index, bb->count); | |
1294 fprintf (dump_file, "in_edges=" HOST_WIDEST_INT_PRINT_DEC " ", | |
1295 sum_edge_counts (bb->preds)); | |
1296 fprintf (dump_file, "out_edges=" HOST_WIDEST_INT_PRINT_DEC "\n", | |
1297 sum_edge_counts (bb->succs)); | |
1298 } | |
1299 } | |
1300 } | |
1301 } | |
1302 | |
1303 | |
1304 /* Implements the negative cycle canceling algorithm to compute a minimum cost | |
1305 flow. | |
1306 Algorithm: | |
1307 1. Find maximal flow. | |
1308 2. Form residual network | |
1309 3. Repeat: | |
1310 While G contains a negative cost cycle C, reverse the flow on the found cycle | |
1311 by the minimum residual capacity in that cycle. | |
1312 4. Form the minimal cost flow | |
1313 f(u,v) = rf(v, u) | |
1314 Input: | |
1315 FIXUP_GRAPH - Initial fixup graph. | |
1316 The flow field is modified to represent the minimum cost flow. */ | |
1317 | |
1318 static void | |
1319 find_minimum_cost_flow (fixup_graph_type *fixup_graph) | |
1320 { | |
1321 /* Holds the index of predecessor in path. */ | |
1322 int *pred; | |
1323 /* Used to hold the minimum cost cycle. */ | |
1324 int *cycle; | |
1325 /* Used to record the number of iterations of cancel_negative_cycle. */ | |
1326 int iteration; | |
1327 /* Vector d[i] holds the minimum cost of path from i to sink. */ | |
1328 gcov_type *d; | |
1329 int fnum_vertices; | |
1330 int new_exit_index; | |
1331 int new_entry_index; | |
1332 | |
1333 gcc_assert (fixup_graph); | |
1334 fnum_vertices = fixup_graph->num_vertices; | |
1335 new_exit_index = fixup_graph->new_exit_index; | |
1336 new_entry_index = fixup_graph->new_entry_index; | |
1337 | |
1338 find_max_flow (fixup_graph, new_entry_index, new_exit_index); | |
1339 | |
1340 /* Initialize the structures for find_negative_cycle(). */ | |
1341 pred = (int *) xcalloc (fnum_vertices, sizeof (int)); | |
1342 d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type)); | |
1343 cycle = (int *) xcalloc (fnum_vertices, sizeof (int)); | |
1344 | |
1345 /* Repeatedly find and cancel negative cost cycles, until | |
1346 no more negative cycles exist. This also updates the flow field | |
1347 to represent the minimum cost flow so far. */ | |
1348 iteration = 0; | |
1349 while (cancel_negative_cycle (fixup_graph, pred, d, cycle)) | |
1350 { | |
1351 iteration++; | |
1352 if (iteration > MAX_ITER (fixup_graph->num_vertices, | |
1353 fixup_graph->num_edges)) | |
1354 break; | |
1355 } | |
1356 | |
1357 if (dump_file) | |
1358 dump_fixup_graph (dump_file, fixup_graph, | |
1359 "After find_minimum_cost_flow()"); | |
1360 | |
1361 /* Cleanup structures. */ | |
1362 free (pred); | |
1363 free (d); | |
1364 free (cycle); | |
1365 } | |
1366 | |
1367 | |
1368 /* Compute the sum of the edge counts in TO_EDGES. */ | |
1369 | |
1370 gcov_type | |
1371 sum_edge_counts (VEC (edge, gc) *to_edges) | |
1372 { | |
1373 gcov_type sum = 0; | |
1374 edge e; | |
1375 edge_iterator ei; | |
1376 | |
1377 FOR_EACH_EDGE (e, ei, to_edges) | |
1378 { | |
1379 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) | |
1380 continue; | |
1381 sum += e->count; | |
1382 } | |
1383 return sum; | |
1384 } | |
1385 | |
1386 | |
1387 /* Main routine. Smoothes the intial assigned basic block and edge counts using | |
1388 a minimum cost flow algorithm, to ensure that the flow consistency rule is | |
1389 obeyed: sum of outgoing edges = sum of incoming edges for each basic | |
1390 block. */ | |
1391 | |
1392 void | |
1393 mcf_smooth_cfg (void) | |
1394 { | |
1395 fixup_graph_type fixup_graph; | |
1396 memset (&fixup_graph, 0, sizeof (fixup_graph)); | |
1397 create_fixup_graph (&fixup_graph); | |
1398 find_minimum_cost_flow (&fixup_graph); | |
1399 adjust_cfg_counts (&fixup_graph); | |
1400 delete_fixup_graph (&fixup_graph); | |
1401 } |