|
0
|
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 }
|
