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