1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth
2 basic block and edge frequency counts.
3 Copyright (C) 2008-2013 Free Software Foundation, Inc.
4 Contributed by Paul Yuan (yingbo.com@gmail.com) and
5 Vinodha Ramasamy (vinodha@google.com).
7 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
23 [1] "Feedback-directed Optimizations in GCC with Estimated Edge Profiles
24 from Hardware Event Sampling", Vinodha Ramasamy, Paul Yuan, Dehao Chen,
25 and Robert Hundt; GCC Summit 2008.
26 [2] "Complementing Missing and Inaccurate Profiling Using a Minimum Cost
27 Circulation Algorithm", Roy Levin, Ilan Newman and Gadi Haber;
30 Algorithm to smooth basic block and edge counts:
31 1. create_fixup_graph: Create fixup graph by translating function CFG into
32 a graph that satisfies MCF algorithm requirements.
33 2. find_max_flow: Find maximal flow.
34 3. compute_residual_flow: Form residual network.
36 cancel_negative_cycle: While G contains a negative cost cycle C, reverse
37 the flow on the found cycle by the minimum residual capacity in that
39 5. Form the minimal cost flow
41 6. adjust_cfg_counts: Update initial edge weights with corrected weights.
42 delta(u.v) = f(u,v) -f(v,u).
43 w*(u,v) = w(u,v) + delta(u,v). */
47 #include "coretypes.h"
48 #include "basic-block.h"
51 #include "diagnostic-core.h"
57 /* CAP_INFINITY: Constant to represent infinite capacity. */
58 #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT)
61 #define K_POS(b) ((b))
62 #define K_NEG(b) (50 * (b))
63 #define COST(k, w) ((k) / mcf_ln ((w) + 2))
64 /* Limit the number of iterations for cancel_negative_cycles() to ensure
65 reasonable compile time. */
66 #define MAX_ITER(n, e) (PARAM_VALUE (PARAM_MIN_MCF_CANCEL_ITERS) + \
67 (1000000 / ((n) * (e))))
72 VERTEX_SPLIT_EDGE
, /* Edge to represent vertex with w(e) = w(v). */
73 REDIRECT_EDGE
, /* Edge after vertex transformation. */
75 SOURCE_CONNECT_EDGE
, /* Single edge connecting to single source. */
76 SINK_CONNECT_EDGE
, /* Single edge connecting to single sink. */
77 SINK_SOURCE_EDGE
, /* Single edge connecting sink to source. */
78 BALANCE_EDGE
, /* Edge connecting with source/sink: cp(e) = 0. */
79 REDIRECT_NORMALIZED_EDGE
, /* Normalized edge for a redirect edge. */
80 REVERSE_NORMALIZED_EDGE
/* Normalized edge for a reverse edge. */
83 /* Structure to represent an edge in the fixup graph. */
84 typedef struct fixup_edge_d
88 /* Flag denoting type of edge and attributes for the flow field. */
91 /* Index to the normalization vertex added for this edge. */
92 int norm_vertex_index
;
93 /* Flow for this edge. */
95 /* Residual flow for this edge - used during negative cycle canceling. */
99 gcov_type max_capacity
;
102 typedef fixup_edge_type
*fixup_edge_p
;
105 /* Structure to represent a vertex in the fixup graph. */
106 typedef struct fixup_vertex_d
108 vec
<fixup_edge_p
> succ_edges
;
111 typedef fixup_vertex_type
*fixup_vertex_p
;
113 /* Fixup graph used in the MCF algorithm. */
114 typedef struct fixup_graph_d
116 /* Current number of vertices for the graph. */
118 /* Current number of edges for the graph. */
120 /* Index of new entry vertex. */
122 /* Index of new exit vertex. */
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
;
130 typedef struct queue_d
138 /* Structure used in the maximal flow routines to find augmenting path. */
139 typedef struct augmenting_path_d
141 /* Queue used to hold vertex indices. */
142 queue_type queue_list
;
143 /* Vector to hold chain of pred vertex indices in augmenting path. */
145 /* Vector that indicates if basic block i has been visited. */
147 } augmenting_path_type
;
150 /* Function definitions. */
152 /* Dump routines to aid debugging. */
154 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */
157 print_basic_block (FILE *file
, fixup_graph_type
*fixup_graph
, int n
)
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
);
173 fprintf (file
, "%d", n
/ 2);
182 /* Print edge S->D for given fixup_graph with n' and n'' format.
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). */
189 print_edge (FILE *file
, fixup_graph_type
*fixup_graph
, int s
, int d
)
191 print_basic_block (file
, fixup_graph
, s
);
193 print_basic_block (file
, fixup_graph
, d
);
197 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
200 dump_fixup_edge (FILE *file
, fixup_graph_type
*fixup_graph
, fixup_edge_p fedge
)
204 fputs ("NULL fixup graph edge.\n", file
);
208 print_edge (file
, fixup_graph
, fedge
->src
, fedge
->dest
);
213 fprintf (file
, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC
"/",
215 if (fedge
->max_capacity
== CAP_INFINITY
)
216 fputs ("+oo,", file
);
218 fprintf (file
, "" HOST_WIDEST_INT_PRINT_DEC
",", fedge
->max_capacity
);
221 if (fedge
->is_rflow_valid
)
223 if (fedge
->rflow
== CAP_INFINITY
)
224 fputs (" rflow=+oo.", file
);
226 fprintf (file
, " rflow=" HOST_WIDEST_INT_PRINT_DEC
",", fedge
->rflow
);
229 fprintf (file
, " cost=" HOST_WIDEST_INT_PRINT_DEC
".", fedge
->cost
);
231 fprintf (file
, "\t(%d->%d)", fedge
->src
, fedge
->dest
);
237 case VERTEX_SPLIT_EDGE
:
238 fputs (" @VERTEX_SPLIT_EDGE", file
);
242 fputs (" @REDIRECT_EDGE", file
);
245 case SOURCE_CONNECT_EDGE
:
246 fputs (" @SOURCE_CONNECT_EDGE", file
);
249 case SINK_CONNECT_EDGE
:
250 fputs (" @SINK_CONNECT_EDGE", file
);
253 case SINK_SOURCE_EDGE
:
254 fputs (" @SINK_SOURCE_EDGE", file
);
258 fputs (" @REVERSE_EDGE", file
);
262 fputs (" @BALANCE_EDGE", file
);
265 case REDIRECT_NORMALIZED_EDGE
:
266 case REVERSE_NORMALIZED_EDGE
:
267 fputs (" @NORMALIZED_EDGE", file
);
271 fputs (" @INVALID_EDGE", file
);
279 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
280 file. The input string MSG is printed out as a heading. */
283 dump_fixup_graph (FILE *file
, fixup_graph_type
*fixup_graph
, const char *msg
)
286 int fnum_vertices
, fnum_edges
;
288 fixup_vertex_p fvertex_list
, pfvertex
;
291 gcc_assert (fixup_graph
);
292 fvertex_list
= fixup_graph
->vertex_list
;
293 fnum_vertices
= fixup_graph
->num_vertices
;
294 fnum_edges
= fixup_graph
->num_edges
;
296 fprintf (file
, "\nDump fixup graph for %s(): %s.\n",
297 current_function_name (), msg
);
299 "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
300 fnum_vertices
, fnum_edges
, fixup_graph
->new_exit_index
);
302 for (i
= 0; i
< fnum_vertices
; i
++)
304 pfvertex
= fvertex_list
+ i
;
305 fprintf (file
, "vertex_list[%d]: %d succ fixup edges.\n",
306 i
, pfvertex
->succ_edges
.length ());
308 for (j
= 0; pfvertex
->succ_edges
.iterate (j
, &pfedge
);
311 /* Distinguish forward edges and backward edges in the residual flow
314 fputs ("(f) ", file
);
315 else if (pfedge
->is_rflow_valid
)
316 fputs ("(b) ", file
);
317 dump_fixup_edge (file
, fixup_graph
, pfedge
);
325 /* Utility routines. */
326 /* ln() implementation: approximate calculation. Returns ln of X. */
347 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
348 implementation) by John Carmack. Returns sqrt of X. */
353 #define MAGIC_CONST1 0x1fbcf800
354 #define MAGIC_CONST2 0x5f3759df
358 } convertor
, convertor2
;
362 convertor
.floatPart
= x
;
363 convertor2
.floatPart
= x
;
364 convertor
.intPart
= MAGIC_CONST1
+ (convertor
.intPart
>> 1);
365 convertor2
.intPart
= MAGIC_CONST2
- (convertor2
.intPart
>> 1);
367 return 0.5f
* (convertor
.floatPart
+ (x
* convertor2
.floatPart
));
371 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
372 (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
373 added set to COST. */
376 add_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
, gcov_type cost
)
378 fixup_vertex_p curr_vertex
= fixup_graph
->vertex_list
+ src
;
379 fixup_edge_p curr_edge
= fixup_graph
->edge_list
+ fixup_graph
->num_edges
;
380 curr_edge
->src
= src
;
381 curr_edge
->dest
= dest
;
382 curr_edge
->cost
= cost
;
383 fixup_graph
->num_edges
++;
385 dump_fixup_edge (dump_file
, fixup_graph
, curr_edge
);
386 curr_vertex
->succ_edges
.safe_push (curr_edge
);
391 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
392 MAX_CAPACITY to the edge_list in the fixup graph. */
395 add_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
396 edge_type type
, gcov_type weight
, gcov_type cost
,
397 gcov_type max_capacity
)
399 fixup_edge_p curr_edge
= add_edge(fixup_graph
, src
, dest
, cost
);
400 curr_edge
->type
= type
;
401 curr_edge
->weight
= weight
;
402 curr_edge
->max_capacity
= max_capacity
;
406 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
407 to the fixup graph. */
410 add_rfixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
411 gcov_type rflow
, gcov_type cost
)
413 fixup_edge_p curr_edge
= add_edge (fixup_graph
, src
, dest
, cost
);
414 curr_edge
->rflow
= rflow
;
415 curr_edge
->is_rflow_valid
= true;
416 /* This edge is not a valid edge - merely used to hold residual flow. */
417 curr_edge
->type
= INVALID_EDGE
;
421 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
422 exist in the FIXUP_GRAPH. */
425 find_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
)
429 fixup_vertex_p pfvertex
;
431 gcc_assert (src
< fixup_graph
->num_vertices
);
433 pfvertex
= fixup_graph
->vertex_list
+ src
;
435 for (j
= 0; pfvertex
->succ_edges
.iterate (j
, &pfedge
);
437 if (pfedge
->dest
== dest
)
444 /* Cleanup routine to free structures in FIXUP_GRAPH. */
447 delete_fixup_graph (fixup_graph_type
*fixup_graph
)
450 int fnum_vertices
= fixup_graph
->num_vertices
;
451 fixup_vertex_p pfvertex
= fixup_graph
->vertex_list
;
453 for (i
= 0; i
< fnum_vertices
; i
++, pfvertex
++)
454 pfvertex
->succ_edges
.release ();
456 free (fixup_graph
->vertex_list
);
457 free (fixup_graph
->edge_list
);
461 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
464 create_fixup_graph (fixup_graph_type
*fixup_graph
)
466 double sqrt_avg_vertex_weight
= 0;
467 double total_vertex_weight
= 0;
470 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */
471 gcov_type
*diff_out_in
= NULL
;
472 gcov_type supply_value
= 0, demand_value
= 0;
474 int new_entry_index
= 0, new_exit_index
= 0;
480 fixup_edge_p pfedge
, r_pfedge
;
481 fixup_edge_p fedge_list
;
484 /* Each basic_block will be split into 2 during vertex transformation. */
485 int fnum_vertices_after_transform
= 2 * n_basic_blocks
;
486 int fnum_edges_after_transform
= n_edges
+ n_basic_blocks
;
488 /* Count the new SOURCE and EXIT vertices to be added. */
489 int fmax_num_vertices
=
490 fnum_vertices_after_transform
+ n_edges
+ n_basic_blocks
+ 2;
492 /* In create_fixup_graph: Each basic block and edge can be split into 3
493 edges. Number of balance edges = n_basic_blocks - 1. And there is 1 edge
494 connecting new_entry and new_exit, and 2 edges connecting new_entry to
495 entry, and exit to new_exit. So after create_fixup_graph:
496 max_edges = 4 * n_basic_blocks + 3 * n_edges + 2
497 Accounting for residual flow edges
498 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges + 2)
499 = 8 * n_basic_blocks + 6 * n_edges + 4
500 < 8 * n_basic_blocks + 8 * n_edges + 8. */
501 int fmax_num_edges
= 8 * (n_basic_blocks
+ n_edges
+ 1);
503 /* Initial num of vertices in the fixup graph. */
504 fixup_graph
->num_vertices
= n_basic_blocks
;
506 /* Fixup graph vertex list. */
507 fixup_graph
->vertex_list
=
508 (fixup_vertex_p
) xcalloc (fmax_num_vertices
, sizeof (fixup_vertex_type
));
510 /* Fixup graph edge list. */
511 fixup_graph
->edge_list
=
512 (fixup_edge_p
) xcalloc (fmax_num_edges
, sizeof (fixup_edge_type
));
515 (gcov_type
*) xcalloc (1 + fnum_vertices_after_transform
,
518 /* Compute constants b, k_pos, k_neg used in the cost function calculation.
519 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */
521 total_vertex_weight
+= bb
->count
;
523 sqrt_avg_vertex_weight
= mcf_sqrt (total_vertex_weight
/ n_basic_blocks
);
525 k_pos
= K_POS (sqrt_avg_vertex_weight
);
526 k_neg
= K_NEG (sqrt_avg_vertex_weight
);
528 /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
529 connected by an edge e from v' to v''. w(e) = w(v). */
532 fprintf (dump_file
, "\nVertex transformation:\n");
536 /* v'->v'': index1->(index1+1). */
539 fcost
= (gcov_type
) COST (k_pos
, bb
->count
);
540 add_fixup_edge (fixup_graph
, i
, i
+ 1, VERTEX_SPLIT_EDGE
, bb
->count
,
541 fcost
, CAP_INFINITY
);
542 fixup_graph
->num_vertices
++;
544 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
546 /* Edges with ignore attribute set should be treated like they don't
548 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
550 j
= 2 * e
->dest
->index
;
551 fcost
= (gcov_type
) COST (k_pos
, e
->count
);
552 add_fixup_edge (fixup_graph
, i
+ 1, j
, REDIRECT_EDGE
, e
->count
, fcost
,
557 /* After vertex transformation. */
558 gcc_assert (fixup_graph
->num_vertices
== fnum_vertices_after_transform
);
559 /* Redirect edges are not added for edges with ignore attribute. */
560 gcc_assert (fixup_graph
->num_edges
<= fnum_edges_after_transform
);
562 fnum_edges_after_transform
= fixup_graph
->num_edges
;
564 /* 2. Initialize D(v). */
565 for (i
= 0; i
< fnum_edges_after_transform
; i
++)
567 pfedge
= fixup_graph
->edge_list
+ i
;
568 diff_out_in
[pfedge
->src
] += pfedge
->weight
;
569 diff_out_in
[pfedge
->dest
] -= pfedge
->weight
;
572 /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */
573 for (i
= 0; i
<= 3; i
++)
576 /* 3. Add reverse edges: needed to decrease counts during smoothing. */
578 fprintf (dump_file
, "\nReverse edges:\n");
579 for (i
= 0; i
< fnum_edges_after_transform
; i
++)
581 pfedge
= fixup_graph
->edge_list
+ i
;
582 if ((pfedge
->src
== 0) || (pfedge
->src
== 2))
584 r_pfedge
= find_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
);
585 if (!r_pfedge
&& pfedge
->weight
)
587 /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
589 fcost
= (gcov_type
) COST (k_neg
, pfedge
->weight
);
590 add_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
,
591 REVERSE_EDGE
, 0, fcost
, pfedge
->weight
);
595 /* 4. Create single source and sink. Connect new source vertex s' to function
596 entry block. Connect sink vertex t' to function exit. */
598 fprintf (dump_file
, "\ns'->S, T->t':\n");
600 new_entry_index
= fixup_graph
->new_entry_index
= fixup_graph
->num_vertices
;
601 fixup_graph
->num_vertices
++;
602 /* Set capacity to 0 initially, it will be updated after
603 supply_value is computed. */
604 add_fixup_edge (fixup_graph
, new_entry_index
, ENTRY_BLOCK
,
605 SOURCE_CONNECT_EDGE
, 0 /* supply_value */, 0,
606 0 /* supply_value */);
607 add_fixup_edge (fixup_graph
, ENTRY_BLOCK
, new_entry_index
,
608 SOURCE_CONNECT_EDGE
, 0 /* supply_value */, 0,
609 0 /* supply_value */);
612 /* Set capacity to 0 initially, it will be updated after
613 demand_value is computed. */
614 new_exit_index
= fixup_graph
->new_exit_index
= fixup_graph
->num_vertices
;
615 fixup_graph
->num_vertices
++;
616 add_fixup_edge (fixup_graph
, 2 * EXIT_BLOCK
+ 1, new_exit_index
,
618 0 /* demand_value */, 0, 0 /* demand_value */);
619 add_fixup_edge (fixup_graph
, new_exit_index
, 2 * EXIT_BLOCK
+ 1,
621 0 /* demand_value */, 0, 0 /* demand_value */);
624 /* Create a back edge from the new_exit to the new_entry.
625 Initially, its capacity will be set to 0 so that it does not
626 affect max flow, but later its capacity will be changed to
627 infinity to cancel negative cycles. */
628 add_fixup_edge (fixup_graph
, new_exit_index
, new_entry_index
,
629 SINK_SOURCE_EDGE
, 0, 0, 0);
633 /* Connect vertices with unbalanced D(v) to source/sink. */
635 fprintf (dump_file
, "\nD(v) balance:\n");
637 /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start
638 with i = 4. diff_out_in[v''] should be 0, but may not be due to
639 rounding error. So here we consider all vertices. */
640 for (i
= 4; i
< new_entry_index
; i
+= 1)
642 if (diff_out_in
[i
] > 0)
644 add_fixup_edge (fixup_graph
, i
, new_exit_index
, BALANCE_EDGE
, 0, 0,
646 demand_value
+= diff_out_in
[i
];
648 else if (diff_out_in
[i
] < 0)
650 add_fixup_edge (fixup_graph
, new_entry_index
, i
, BALANCE_EDGE
, 0, 0,
652 supply_value
-= diff_out_in
[i
];
656 /* Set supply = demand. */
659 fprintf (dump_file
, "\nAdjust supply and demand:\n");
660 fprintf (dump_file
, "supply_value=" HOST_WIDEST_INT_PRINT_DEC
"\n",
662 fprintf (dump_file
, "demand_value=" HOST_WIDEST_INT_PRINT_DEC
"\n",
666 if (demand_value
> supply_value
)
668 pfedge
= find_fixup_edge (fixup_graph
, new_entry_index
, ENTRY_BLOCK
);
669 pfedge
->max_capacity
+= (demand_value
- supply_value
);
673 pfedge
= find_fixup_edge (fixup_graph
, 2 * EXIT_BLOCK
+ 1, new_exit_index
);
674 pfedge
->max_capacity
+= (supply_value
- demand_value
);
677 /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
678 created by the vertex transformation step from self-edges in the original
679 CFG and by the reverse edges added earlier. */
681 fprintf (dump_file
, "\nNormalize edges:\n");
683 fnum_edges
= fixup_graph
->num_edges
;
684 fedge_list
= fixup_graph
->edge_list
;
686 for (i
= 0; i
< fnum_edges
; i
++)
688 pfedge
= fedge_list
+ i
;
689 r_pfedge
= find_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
);
690 if (((pfedge
->type
== VERTEX_SPLIT_EDGE
)
691 || (pfedge
->type
== REDIRECT_EDGE
)) && r_pfedge
)
693 new_index
= fixup_graph
->num_vertices
;
694 fixup_graph
->num_vertices
++;
698 fprintf (dump_file
, "\nAnti-parallel edge:\n");
699 dump_fixup_edge (dump_file
, fixup_graph
, pfedge
);
700 dump_fixup_edge (dump_file
, fixup_graph
, r_pfedge
);
701 fprintf (dump_file
, "New vertex is %d.\n", new_index
);
702 fprintf (dump_file
, "------------------\n");
705 pfedge
->norm_vertex_index
= new_index
;
708 fprintf (dump_file
, "After normalization:\n");
709 dump_fixup_edge (dump_file
, fixup_graph
, pfedge
);
712 /* Add a new fixup edge: new_index->src. */
713 add_fixup_edge (fixup_graph
, new_index
, pfedge
->src
,
714 REVERSE_NORMALIZED_EDGE
, 0, 0,
715 r_pfedge
->max_capacity
);
716 gcc_assert (fixup_graph
->num_vertices
<= fmax_num_vertices
);
718 /* Edge: r_pfedge->src -> r_pfedge->dest
719 ==> r_pfedge->src -> new_index. */
720 r_pfedge
->dest
= new_index
;
721 r_pfedge
->type
= REVERSE_NORMALIZED_EDGE
;
722 r_pfedge
->max_capacity
= pfedge
->max_capacity
;
724 dump_fixup_edge (dump_file
, fixup_graph
, r_pfedge
);
729 dump_fixup_graph (dump_file
, fixup_graph
, "After create_fixup_graph()");
736 /* Allocates space for the structures in AUGMENTING_PATH. The space needed is
737 proportional to the number of nodes in the graph, which is given by
741 init_augmenting_path (augmenting_path_type
*augmenting_path
, int graph_size
)
743 augmenting_path
->queue_list
.queue
= (int *)
744 xcalloc (graph_size
+ 2, sizeof (int));
745 augmenting_path
->queue_list
.size
= graph_size
+ 2;
746 augmenting_path
->bb_pred
= (int *) xcalloc (graph_size
, sizeof (int));
747 augmenting_path
->is_visited
= (int *) xcalloc (graph_size
, sizeof (int));
750 /* Free the structures in AUGMENTING_PATH. */
752 free_augmenting_path (augmenting_path_type
*augmenting_path
)
754 free (augmenting_path
->queue_list
.queue
);
755 free (augmenting_path
->bb_pred
);
756 free (augmenting_path
->is_visited
);
760 /* Queue routines. Assumes queue will never overflow. */
763 init_queue (queue_type
*queue_list
)
765 gcc_assert (queue_list
);
766 queue_list
->head
= 0;
767 queue_list
->tail
= 0;
770 /* Return true if QUEUE_LIST is empty. */
772 is_empty (queue_type
*queue_list
)
774 return (queue_list
->head
== queue_list
->tail
);
777 /* Insert element X into QUEUE_LIST. */
779 enqueue (queue_type
*queue_list
, int x
)
781 gcc_assert (queue_list
->tail
< queue_list
->size
);
782 queue_list
->queue
[queue_list
->tail
] = x
;
783 (queue_list
->tail
)++;
786 /* Return the first element in QUEUE_LIST. */
788 dequeue (queue_type
*queue_list
)
791 gcc_assert (queue_list
->head
>= 0);
792 x
= queue_list
->queue
[queue_list
->head
];
793 (queue_list
->head
)++;
798 /* Finds a negative cycle in the residual network using
799 the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
800 minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
804 FIXUP_GRAPH - Residual graph (input/output)
805 The following are allocated/freed by the caller:
806 PI - Vector to hold predecessors in path (pi = pred index)
807 D - D[I] holds minimum cost of path from i to sink
808 CYCLE - Vector to hold the minimum cost cycle
811 true if a negative cycle was found, false otherwise. */
814 cancel_negative_cycle (fixup_graph_type
*fixup_graph
,
815 int *pi
, gcov_type
*d
, int *cycle
)
818 int fnum_vertices
, fnum_edges
;
819 fixup_edge_p fedge_list
, pfedge
, r_pfedge
;
820 bool found_cycle
= false;
821 int cycle_start
= 0, cycle_end
= 0;
822 gcov_type sum_cost
= 0, cycle_flow
= 0;
823 bool propagated
= false;
825 gcc_assert (fixup_graph
);
826 fnum_vertices
= fixup_graph
->num_vertices
;
827 fnum_edges
= fixup_graph
->num_edges
;
828 fedge_list
= fixup_graph
->edge_list
;
832 for (i
= 1; i
< fnum_vertices
; i
++)
841 for (k
= 1; k
< fnum_vertices
; k
++)
844 for (i
= 0; i
< fnum_edges
; i
++)
846 pfedge
= fedge_list
+ i
;
847 if (pfedge
->is_rflow_valid
&& pfedge
->rflow
848 && d
[pfedge
->src
] != CAP_INFINITY
849 && (d
[pfedge
->dest
] > d
[pfedge
->src
] + pfedge
->cost
))
851 d
[pfedge
->dest
] = d
[pfedge
->src
] + pfedge
->cost
;
852 pi
[pfedge
->dest
] = pfedge
->src
;
861 /* No negative cycles exist. */
865 for (i
= 0; i
< fnum_edges
; i
++)
867 pfedge
= fedge_list
+ i
;
868 if (pfedge
->is_rflow_valid
&& pfedge
->rflow
869 && d
[pfedge
->src
] != CAP_INFINITY
870 && (d
[pfedge
->dest
] > d
[pfedge
->src
] + pfedge
->cost
))
880 /* Augment the cycle with the cycle's minimum residual capacity. */
882 cycle
[0] = pfedge
->dest
;
885 for (i
= 1; i
< fnum_vertices
; i
++)
889 for (k
= 0; k
< i
; k
++)
893 /* cycle[k] -> ... -> cycle[i]. */
904 gcc_assert (cycle
[cycle_start
] == cycle
[cycle_end
]);
906 fprintf (dump_file
, "\nNegative cycle length is %d:\n",
907 cycle_end
- cycle_start
);
910 cycle_flow
= CAP_INFINITY
;
911 for (k
= cycle_start
; k
< cycle_end
; k
++)
913 pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
+ 1], cycle
[k
]);
914 cycle_flow
= MIN (cycle_flow
, pfedge
->rflow
);
915 sum_cost
+= pfedge
->cost
;
917 fprintf (dump_file
, "%d ", cycle
[k
]);
922 fprintf (dump_file
, "%d", cycle
[k
]);
924 ": (" HOST_WIDEST_INT_PRINT_DEC
", " HOST_WIDEST_INT_PRINT_DEC
925 ")\n", sum_cost
, cycle_flow
);
927 "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC
"\n",
931 for (k
= cycle_start
; k
< cycle_end
; k
++)
933 pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
+ 1], cycle
[k
]);
934 r_pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
], cycle
[k
+ 1]);
935 if (pfedge
->rflow
!= CAP_INFINITY
)
936 pfedge
->rflow
-= cycle_flow
;
938 pfedge
->flow
+= cycle_flow
;
939 if (r_pfedge
->rflow
!= CAP_INFINITY
)
940 r_pfedge
->rflow
+= cycle_flow
;
942 r_pfedge
->flow
-= cycle_flow
;
949 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
950 the edges. ENTRY and EXIT vertices should not be considered. */
953 compute_residual_flow (fixup_graph_type
*fixup_graph
)
957 fixup_edge_p fedge_list
, pfedge
;
959 gcc_assert (fixup_graph
);
962 fputs ("\ncompute_residual_flow():\n", dump_file
);
964 fnum_edges
= fixup_graph
->num_edges
;
965 fedge_list
= fixup_graph
->edge_list
;
967 for (i
= 0; i
< fnum_edges
; i
++)
969 pfedge
= fedge_list
+ i
;
970 pfedge
->rflow
= pfedge
->max_capacity
== CAP_INFINITY
?
971 CAP_INFINITY
: pfedge
->max_capacity
- pfedge
->flow
;
972 pfedge
->is_rflow_valid
= true;
973 add_rfixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
, pfedge
->flow
,
979 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
980 SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
981 this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
982 to reflect the path found.
983 Returns: 0 if no augmenting path is found, 1 otherwise. */
986 find_augmenting_path (fixup_graph_type
*fixup_graph
,
987 augmenting_path_type
*augmenting_path
, int source
,
992 fixup_vertex_p fvertex_list
, pfvertex
;
994 int *bb_pred
, *is_visited
;
995 queue_type
*queue_list
;
997 gcc_assert (augmenting_path
);
998 bb_pred
= augmenting_path
->bb_pred
;
999 gcc_assert (bb_pred
);
1000 is_visited
= augmenting_path
->is_visited
;
1001 gcc_assert (is_visited
);
1002 queue_list
= &(augmenting_path
->queue_list
);
1004 gcc_assert (fixup_graph
);
1006 fvertex_list
= fixup_graph
->vertex_list
;
1008 for (u
= 0; u
< fixup_graph
->num_vertices
; u
++)
1011 init_queue (queue_list
);
1012 enqueue (queue_list
, source
);
1013 bb_pred
[source
] = -1;
1015 while (!is_empty (queue_list
))
1017 u
= dequeue (queue_list
);
1019 pfvertex
= fvertex_list
+ u
;
1020 for (i
= 0; pfvertex
->succ_edges
.iterate (i
, &pfedge
);
1023 int dest
= pfedge
->dest
;
1024 if ((pfedge
->rflow
> 0) && (is_visited
[dest
] == 0))
1026 enqueue (queue_list
, dest
);
1028 is_visited
[dest
] = 1;
1039 /* Routine to find the maximal flow:
1041 1. Initialize flow to 0
1042 2. Find an augmenting path form source to sink.
1043 3. Send flow equal to the path's residual capacity along the edges of this path.
1044 4. Repeat steps 2 and 3 until no new augmenting path is found.
1047 SOURCE: index of source vertex (input)
1048 SINK: index of sink vertex (input)
1049 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1050 set to have a valid maximal flow by this routine. (input)
1051 Return: Maximum flow possible. */
1054 find_max_flow (fixup_graph_type
*fixup_graph
, int source
, int sink
)
1057 augmenting_path_type augmenting_path
;
1059 gcov_type max_flow
= 0;
1061 fixup_edge_p fedge_list
, pfedge
, r_pfedge
;
1063 gcc_assert (fixup_graph
);
1065 fnum_edges
= fixup_graph
->num_edges
;
1066 fedge_list
= fixup_graph
->edge_list
;
1068 /* Initialize flow to 0. */
1069 for (i
= 0; i
< fnum_edges
; i
++)
1071 pfedge
= fedge_list
+ i
;
1075 compute_residual_flow (fixup_graph
);
1077 init_augmenting_path (&augmenting_path
, fixup_graph
->num_vertices
);
1079 bb_pred
= augmenting_path
.bb_pred
;
1080 while (find_augmenting_path (fixup_graph
, &augmenting_path
, source
, sink
))
1082 /* Determine the amount by which we can increment the flow. */
1083 gcov_type increment
= CAP_INFINITY
;
1084 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1086 pfedge
= find_fixup_edge (fixup_graph
, bb_pred
[u
], u
);
1087 increment
= MIN (increment
, pfedge
->rflow
);
1089 max_flow
+= increment
;
1091 /* Now increment the flow. EXIT vertex index is 1. */
1092 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1094 pfedge
= find_fixup_edge (fixup_graph
, bb_pred
[u
], u
);
1095 r_pfedge
= find_fixup_edge (fixup_graph
, u
, bb_pred
[u
]);
1097 if (pfedge
->rflow
!= CAP_INFINITY
)
1098 pfedge
->rflow
-= increment
;
1099 if (r_pfedge
->rflow
!= CAP_INFINITY
)
1100 r_pfedge
->rflow
+= increment
;
1105 pfedge
->flow
+= increment
;
1109 /* backward edge. */
1110 gcc_assert (r_pfedge
->type
);
1111 r_pfedge
->flow
-= increment
;
1117 fprintf (dump_file
, "\nDump augmenting path:\n");
1118 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1120 print_basic_block (dump_file
, fixup_graph
, u
);
1121 fprintf (dump_file
, "<-");
1124 "ENTRY (path_capacity=" HOST_WIDEST_INT_PRINT_DEC
")\n",
1127 "Network flow is " HOST_WIDEST_INT_PRINT_DEC
".\n",
1132 free_augmenting_path (&augmenting_path
);
1134 dump_fixup_graph (dump_file
, fixup_graph
, "After find_max_flow()");
1139 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1140 after applying the find_minimum_cost_flow() routine. */
1143 adjust_cfg_counts (fixup_graph_type
*fixup_graph
)
1149 fixup_edge_p pfedge
, pfedge_n
;
1151 gcc_assert (fixup_graph
);
1154 fprintf (dump_file
, "\nadjust_cfg_counts():\n");
1156 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1163 "BB%d: " HOST_WIDEST_INT_PRINT_DEC
"", bb
->index
, bb
->count
);
1165 pfedge
= find_fixup_edge (fixup_graph
, i
, i
+ 1);
1168 bb
->count
+= pfedge
->flow
;
1171 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1173 print_edge (dump_file
, fixup_graph
, i
, i
+ 1);
1174 fprintf (dump_file
, ")");
1179 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1180 /* Deduct flow from normalized reverse edge. */
1181 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1183 bb
->count
-= pfedge_n
->flow
;
1186 fprintf (dump_file
, " - " HOST_WIDEST_INT_PRINT_DEC
"(",
1188 print_edge (dump_file
, fixup_graph
, i
+ 1,
1189 pfedge
->norm_vertex_index
);
1190 fprintf (dump_file
, ")");
1194 fprintf (dump_file
, " = " HOST_WIDEST_INT_PRINT_DEC
"\n", bb
->count
);
1197 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1199 /* Treat edges with ignore attribute set as if they don't exist. */
1200 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1203 j
= 2 * e
->dest
->index
;
1205 fprintf (dump_file
, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC
"",
1206 bb
->index
, e
->dest
->index
, e
->count
);
1208 pfedge
= find_fixup_edge (fixup_graph
, i
+ 1, j
);
1210 if (bb
->index
!= e
->dest
->index
)
1212 /* Non-self edge. */
1215 e
->count
+= pfedge
->flow
;
1218 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1220 print_edge (dump_file
, fixup_graph
, i
+ 1, j
);
1221 fprintf (dump_file
, ")");
1226 find_fixup_edge (fixup_graph
, j
, pfedge
->norm_vertex_index
);
1227 /* Deduct flow from normalized reverse edge. */
1228 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1230 e
->count
-= pfedge_n
->flow
;
1233 fprintf (dump_file
, " - " HOST_WIDEST_INT_PRINT_DEC
"(",
1235 print_edge (dump_file
, fixup_graph
, j
,
1236 pfedge
->norm_vertex_index
);
1237 fprintf (dump_file
, ")");
1243 /* Handle self edges. Self edge is split with a normalization
1244 vertex. Here i=j. */
1245 pfedge
= find_fixup_edge (fixup_graph
, j
, i
+ 1);
1247 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1248 e
->count
+= pfedge_n
->flow
;
1249 bb
->count
+= pfedge_n
->flow
;
1252 fprintf (dump_file
, "(self edge)");
1253 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1255 print_edge (dump_file
, fixup_graph
, i
+ 1,
1256 pfedge
->norm_vertex_index
);
1257 fprintf (dump_file
, ")");
1262 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1264 fprintf (dump_file
, " = " HOST_WIDEST_INT_PRINT_DEC
"\t(%.1f%%)\n",
1265 e
->count
, e
->probability
* 100.0 / REG_BR_PROB_BASE
);
1269 ENTRY_BLOCK_PTR
->count
= sum_edge_counts (ENTRY_BLOCK_PTR
->succs
);
1270 EXIT_BLOCK_PTR
->count
= sum_edge_counts (EXIT_BLOCK_PTR
->preds
);
1272 /* Compute edge probabilities. */
1277 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1278 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1283 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1284 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1288 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1290 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1291 e
->probability
= REG_BR_PROB_BASE
/ total
;
1298 total
+= EDGE_COUNT (bb
->succs
);
1299 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1300 e
->probability
= REG_BR_PROB_BASE
/ total
;
1307 fprintf (dump_file
, "\nCheck %s() CFG flow conservation:\n",
1308 current_function_name ());
1311 if ((bb
->count
!= sum_edge_counts (bb
->preds
))
1312 || (bb
->count
!= sum_edge_counts (bb
->succs
)))
1315 "BB%d(" HOST_WIDEST_INT_PRINT_DEC
") **INVALID**: ",
1316 bb
->index
, bb
->count
);
1318 "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC
1319 ") **INVALID**: \n", bb
->index
, bb
->count
);
1320 fprintf (dump_file
, "in_edges=" HOST_WIDEST_INT_PRINT_DEC
" ",
1321 sum_edge_counts (bb
->preds
));
1322 fprintf (dump_file
, "out_edges=" HOST_WIDEST_INT_PRINT_DEC
"\n",
1323 sum_edge_counts (bb
->succs
));
1330 /* Called before negative_cycle_cancellation, to form a cycle between
1331 * new_exit to new_entry in FIXUP_GRAPH with capacity MAX_FLOW. We
1332 * don't want the flow in the BALANCE_EDGE to be modified, so we set
1333 * the residural flow of those edges to 0 */
1336 modify_sink_source_capacity (fixup_graph_type
*fixup_graph
, gcov_type max_flow
)
1338 fixup_edge_p edge
, r_edge
;
1340 int entry
= ENTRY_BLOCK
;
1341 int exit
= 2 * EXIT_BLOCK
+ 1;
1342 int new_entry
= fixup_graph
->new_entry_index
;
1343 int new_exit
= fixup_graph
->new_exit_index
;
1345 edge
= find_fixup_edge (fixup_graph
, new_entry
, entry
);
1346 edge
->max_capacity
= CAP_INFINITY
;
1347 edge
->rflow
= CAP_INFINITY
;
1349 edge
= find_fixup_edge (fixup_graph
, entry
, new_entry
);
1350 edge
->max_capacity
= CAP_INFINITY
;
1351 edge
->rflow
= CAP_INFINITY
;
1353 edge
= find_fixup_edge (fixup_graph
, exit
, new_exit
);
1354 edge
->max_capacity
= CAP_INFINITY
;
1355 edge
->rflow
= CAP_INFINITY
;
1357 edge
= find_fixup_edge (fixup_graph
, new_exit
, exit
);
1358 edge
->max_capacity
= CAP_INFINITY
;
1359 edge
->rflow
= CAP_INFINITY
;
1361 edge
= find_fixup_edge (fixup_graph
, new_exit
, new_entry
);
1362 edge
->max_capacity
= CAP_INFINITY
;
1363 edge
->flow
= max_flow
;
1364 edge
->rflow
= CAP_INFINITY
;
1366 r_edge
= find_fixup_edge (fixup_graph
, new_entry
, new_exit
);
1367 r_edge
->rflow
= max_flow
;
1369 /* Find all the backwards residual edges corresponding to
1370 BALANCE_EDGEs and set their residual flow to 0 to enforce a
1371 minimum flow constraint on these edges. */
1372 for (i
= 4; i
< new_entry
; i
+= 1)
1374 edge
= find_fixup_edge (fixup_graph
, i
, new_entry
);
1377 edge
= find_fixup_edge (fixup_graph
, new_exit
, i
);
1384 /* Implements the negative cycle canceling algorithm to compute a minimum cost
1387 1. Find maximal flow.
1388 2. Form residual network
1390 While G contains a negative cost cycle C, reverse the flow on the found cycle
1391 by the minimum residual capacity in that cycle.
1392 4. Form the minimal cost flow
1395 FIXUP_GRAPH - Initial fixup graph.
1396 The flow field is modified to represent the minimum cost flow. */
1399 find_minimum_cost_flow (fixup_graph_type
*fixup_graph
)
1401 /* Holds the index of predecessor in path. */
1403 /* Used to hold the minimum cost cycle. */
1405 /* Used to record the number of iterations of cancel_negative_cycle. */
1407 /* Vector d[i] holds the minimum cost of path from i to sink. */
1411 int new_entry_index
;
1414 gcc_assert (fixup_graph
);
1415 fnum_vertices
= fixup_graph
->num_vertices
;
1416 new_exit_index
= fixup_graph
->new_exit_index
;
1417 new_entry_index
= fixup_graph
->new_entry_index
;
1419 max_flow
= find_max_flow (fixup_graph
, new_entry_index
, new_exit_index
);
1421 /* Adjust the fixup graph to translate things into a minimum cost
1422 circulation problem. */
1423 modify_sink_source_capacity (fixup_graph
, max_flow
);
1425 /* Initialize the structures for find_negative_cycle(). */
1426 pred
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1427 d
= (gcov_type
*) xcalloc (fnum_vertices
, sizeof (gcov_type
));
1428 cycle
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1430 /* Repeatedly find and cancel negative cost cycles, until
1431 no more negative cycles exist. This also updates the flow field
1432 to represent the minimum cost flow so far. */
1434 while (cancel_negative_cycle (fixup_graph
, pred
, d
, cycle
))
1437 if (iteration
> MAX_ITER (fixup_graph
->num_vertices
,
1438 fixup_graph
->num_edges
))
1440 inform (DECL_SOURCE_LOCATION (current_function_decl
),
1441 "Exiting profile correction early to avoid excessive "
1448 dump_fixup_graph (dump_file
, fixup_graph
,
1449 "After find_minimum_cost_flow()");
1451 /* Cleanup structures. */
1458 /* Compute the sum of the edge counts in TO_EDGES. */
1461 sum_edge_counts (vec
<edge
, va_gc
> *to_edges
)
1467 FOR_EACH_EDGE (e
, ei
, to_edges
)
1469 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1477 /* Main routine. Smoothes the initial assigned basic block and edge counts using
1478 a minimum cost flow algorithm, to ensure that the flow consistency rule is
1479 obeyed: sum of outgoing edges = sum of incoming edges for each basic
1483 mcf_smooth_cfg (void)
1485 fixup_graph_type fixup_graph
;
1486 memset (&fixup_graph
, 0, sizeof (fixup_graph
));
1487 create_fixup_graph (&fixup_graph
);
1488 find_minimum_cost_flow (&fixup_graph
);
1489 adjust_cfg_counts (&fixup_graph
);
1490 delete_fixup_graph (&fixup_graph
);