1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth
2 basic block and edge frequency counts.
3 Copyright (C) 2008, 2009
4 Free Software Foundation, Inc.
5 Contributed by Paul Yuan (yingbo.com@gmail.com) and
6 Vinodha Ramasamy (vinodha@google.com).
8 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
24 [1] "Feedback-directed Optimizations in GCC with Estimated Edge Profiles
25 from Hardware Event Sampling", Vinodha Ramasamy, Paul Yuan, Dehao Chen,
26 and Robert Hundt; GCC Summit 2008.
27 [2] "Complementing Missing and Inaccurate Profiling Using a Minimum Cost
28 Circulation Algorithm", Roy Levin, Ilan Newman and Gadi Haber;
31 Algorithm to smooth basic block and edge counts:
32 1. create_fixup_graph: Create fixup graph by translating function CFG into
33 a graph that satisfies MCF algorithm requirements.
34 2. find_max_flow: Find maximal flow.
35 3. compute_residual_flow: Form residual network.
37 cancel_negative_cycle: While G contains a negative cost cycle C, reverse
38 the flow on the found cycle by the minimum residual capacity in that
40 5. Form the minimal cost flow
42 6. adjust_cfg_counts: Update initial edge weights with corrected weights.
43 delta(u.v) = f(u,v) -f(v,u).
44 w*(u,v) = w(u,v) + delta(u,v). */
48 #include "coretypes.h"
50 #include "basic-block.h"
52 #include "langhooks.h"
56 #include "diagnostic-core.h"
60 /* CAP_INFINITY: Constant to represent infinite capacity. */
61 #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT)
64 #define K_POS(b) ((b))
65 #define K_NEG(b) (50 * (b))
66 #define COST(k, w) ((k) / mcf_ln ((w) + 2))
67 /* Limit the number of iterations for cancel_negative_cycles() to ensure
68 reasonable compile time. */
69 #define MAX_ITER(n, e) (PARAM_VALUE (PARAM_MIN_MCF_CANCEL_ITERS) + \
70 (1000000 / ((n) * (e))))
75 VERTEX_SPLIT_EDGE
, /* Edge to represent vertex with w(e) = w(v). */
76 REDIRECT_EDGE
, /* Edge after vertex transformation. */
78 SOURCE_CONNECT_EDGE
, /* Single edge connecting to single source. */
79 SINK_CONNECT_EDGE
, /* Single edge connecting to single sink. */
80 SINK_SOURCE_EDGE
, /* Single edge connecting sink to source. */
81 BALANCE_EDGE
, /* Edge connecting with source/sink: cp(e) = 0. */
82 REDIRECT_NORMALIZED_EDGE
, /* Normalized edge for a redirect edge. */
83 REVERSE_NORMALIZED_EDGE
/* Normalized edge for a reverse edge. */
86 /* Structure to represent an edge in the fixup graph. */
87 typedef struct fixup_edge_d
91 /* Flag denoting type of edge and attributes for the flow field. */
94 /* Index to the normalization vertex added for this edge. */
95 int norm_vertex_index
;
96 /* Flow for this edge. */
98 /* Residual flow for this edge - used during negative cycle canceling. */
102 gcov_type max_capacity
;
105 typedef fixup_edge_type
*fixup_edge_p
;
107 DEF_VEC_P (fixup_edge_p
);
108 DEF_VEC_ALLOC_P (fixup_edge_p
, heap
);
110 /* Structure to represent a vertex in the fixup graph. */
111 typedef struct fixup_vertex_d
113 VEC (fixup_edge_p
, heap
) *succ_edges
;
116 typedef fixup_vertex_type
*fixup_vertex_p
;
118 /* Fixup graph used in the MCF algorithm. */
119 typedef struct fixup_graph_d
121 /* Current number of vertices for the graph. */
123 /* Current number of edges for the graph. */
125 /* Index of new entry vertex. */
127 /* Index of new exit vertex. */
129 /* Fixup vertex list. Adjacency list for fixup graph. */
130 fixup_vertex_p vertex_list
;
131 /* Fixup edge list. */
132 fixup_edge_p edge_list
;
135 typedef struct queue_d
143 /* Structure used in the maximal flow routines to find augmenting path. */
144 typedef struct augmenting_path_d
146 /* Queue used to hold vertex indices. */
147 queue_type queue_list
;
148 /* Vector to hold chain of pred vertex indices in augmenting path. */
150 /* Vector that indicates if basic block i has been visited. */
152 } augmenting_path_type
;
155 /* Function definitions. */
157 /* Dump routines to aid debugging. */
159 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */
162 print_basic_block (FILE *file
, fixup_graph_type
*fixup_graph
, int n
)
164 if (n
== ENTRY_BLOCK
)
165 fputs ("ENTRY", file
);
166 else if (n
== ENTRY_BLOCK
+ 1)
167 fputs ("ENTRY''", file
);
168 else if (n
== 2 * EXIT_BLOCK
)
169 fputs ("EXIT", file
);
170 else if (n
== 2 * EXIT_BLOCK
+ 1)
171 fputs ("EXIT''", file
);
172 else if (n
== fixup_graph
->new_exit_index
)
173 fputs ("NEW_EXIT", file
);
174 else if (n
== fixup_graph
->new_entry_index
)
175 fputs ("NEW_ENTRY", file
);
178 fprintf (file
, "%d", n
/ 2);
187 /* Print edge S->D for given fixup_graph with n' and n'' format.
189 S is the index of the source vertex of the edge (input) and
190 D is the index of the destination vertex of the edge (input) for the given
191 fixup_graph (input). */
194 print_edge (FILE *file
, fixup_graph_type
*fixup_graph
, int s
, int d
)
196 print_basic_block (file
, fixup_graph
, s
);
198 print_basic_block (file
, fixup_graph
, d
);
202 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
205 dump_fixup_edge (FILE *file
, fixup_graph_type
*fixup_graph
, fixup_edge_p fedge
)
209 fputs ("NULL fixup graph edge.\n", file
);
213 print_edge (file
, fixup_graph
, fedge
->src
, fedge
->dest
);
218 fprintf (file
, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC
"/",
220 if (fedge
->max_capacity
== CAP_INFINITY
)
221 fputs ("+oo,", file
);
223 fprintf (file
, "" HOST_WIDEST_INT_PRINT_DEC
",", fedge
->max_capacity
);
226 if (fedge
->is_rflow_valid
)
228 if (fedge
->rflow
== CAP_INFINITY
)
229 fputs (" rflow=+oo.", file
);
231 fprintf (file
, " rflow=" HOST_WIDEST_INT_PRINT_DEC
",", fedge
->rflow
);
234 fprintf (file
, " cost=" HOST_WIDEST_INT_PRINT_DEC
".", fedge
->cost
);
236 fprintf (file
, "\t(%d->%d)", fedge
->src
, fedge
->dest
);
242 case VERTEX_SPLIT_EDGE
:
243 fputs (" @VERTEX_SPLIT_EDGE", file
);
247 fputs (" @REDIRECT_EDGE", file
);
250 case SOURCE_CONNECT_EDGE
:
251 fputs (" @SOURCE_CONNECT_EDGE", file
);
254 case SINK_CONNECT_EDGE
:
255 fputs (" @SINK_CONNECT_EDGE", file
);
258 case SINK_SOURCE_EDGE
:
259 fputs (" @SINK_SOURCE_EDGE", file
);
263 fputs (" @REVERSE_EDGE", file
);
267 fputs (" @BALANCE_EDGE", file
);
270 case REDIRECT_NORMALIZED_EDGE
:
271 case REVERSE_NORMALIZED_EDGE
:
272 fputs (" @NORMALIZED_EDGE", file
);
276 fputs (" @INVALID_EDGE", file
);
284 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
285 file. The input string MSG is printed out as a heading. */
288 dump_fixup_graph (FILE *file
, fixup_graph_type
*fixup_graph
, const char *msg
)
291 int fnum_vertices
, fnum_edges
;
293 fixup_vertex_p fvertex_list
, pfvertex
;
296 gcc_assert (fixup_graph
);
297 fvertex_list
= fixup_graph
->vertex_list
;
298 fnum_vertices
= fixup_graph
->num_vertices
;
299 fnum_edges
= fixup_graph
->num_edges
;
301 fprintf (file
, "\nDump fixup graph for %s(): %s.\n",
302 lang_hooks
.decl_printable_name (current_function_decl
, 2), msg
);
304 "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
305 fnum_vertices
, fnum_edges
, fixup_graph
->new_exit_index
);
307 for (i
= 0; i
< fnum_vertices
; i
++)
309 pfvertex
= fvertex_list
+ i
;
310 fprintf (file
, "vertex_list[%d]: %d succ fixup edges.\n",
311 i
, VEC_length (fixup_edge_p
, pfvertex
->succ_edges
));
313 for (j
= 0; VEC_iterate (fixup_edge_p
, pfvertex
->succ_edges
, j
, pfedge
);
316 /* Distinguish forward edges and backward edges in the residual flow
319 fputs ("(f) ", file
);
320 else if (pfedge
->is_rflow_valid
)
321 fputs ("(b) ", file
);
322 dump_fixup_edge (file
, fixup_graph
, pfedge
);
330 /* Utility routines. */
331 /* ln() implementation: approximate calculation. Returns ln of X. */
352 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
353 implementation) by John Carmack. Returns sqrt of X. */
358 #define MAGIC_CONST1 0x1fbcf800
359 #define MAGIC_CONST2 0x5f3759df
363 } convertor
, convertor2
;
367 convertor
.floatPart
= x
;
368 convertor2
.floatPart
= x
;
369 convertor
.intPart
= MAGIC_CONST1
+ (convertor
.intPart
>> 1);
370 convertor2
.intPart
= MAGIC_CONST2
- (convertor2
.intPart
>> 1);
372 return 0.5f
* (convertor
.floatPart
+ (x
* convertor2
.floatPart
));
376 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
377 (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
378 added set to COST. */
381 add_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
, gcov_type cost
)
383 fixup_vertex_p curr_vertex
= fixup_graph
->vertex_list
+ src
;
384 fixup_edge_p curr_edge
= fixup_graph
->edge_list
+ fixup_graph
->num_edges
;
385 curr_edge
->src
= src
;
386 curr_edge
->dest
= dest
;
387 curr_edge
->cost
= cost
;
388 fixup_graph
->num_edges
++;
390 dump_fixup_edge (dump_file
, fixup_graph
, curr_edge
);
391 VEC_safe_push (fixup_edge_p
, heap
, curr_vertex
->succ_edges
, curr_edge
);
396 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
397 MAX_CAPACITY to the edge_list in the fixup graph. */
400 add_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
401 edge_type type
, gcov_type weight
, gcov_type cost
,
402 gcov_type max_capacity
)
404 fixup_edge_p curr_edge
= add_edge(fixup_graph
, src
, dest
, cost
);
405 curr_edge
->type
= type
;
406 curr_edge
->weight
= weight
;
407 curr_edge
->max_capacity
= max_capacity
;
411 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
412 to the fixup graph. */
415 add_rfixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
416 gcov_type rflow
, gcov_type cost
)
418 fixup_edge_p curr_edge
= add_edge (fixup_graph
, src
, dest
, cost
);
419 curr_edge
->rflow
= rflow
;
420 curr_edge
->is_rflow_valid
= true;
421 /* This edge is not a valid edge - merely used to hold residual flow. */
422 curr_edge
->type
= INVALID_EDGE
;
426 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
427 exist in the FIXUP_GRAPH. */
430 find_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
)
434 fixup_vertex_p pfvertex
;
436 gcc_assert (src
< fixup_graph
->num_vertices
);
438 pfvertex
= fixup_graph
->vertex_list
+ src
;
440 for (j
= 0; VEC_iterate (fixup_edge_p
, pfvertex
->succ_edges
, j
, pfedge
);
442 if (pfedge
->dest
== dest
)
449 /* Cleanup routine to free structures in FIXUP_GRAPH. */
452 delete_fixup_graph (fixup_graph_type
*fixup_graph
)
455 int fnum_vertices
= fixup_graph
->num_vertices
;
456 fixup_vertex_p pfvertex
= fixup_graph
->vertex_list
;
458 for (i
= 0; i
< fnum_vertices
; i
++, pfvertex
++)
459 VEC_free (fixup_edge_p
, heap
, pfvertex
->succ_edges
);
461 free (fixup_graph
->vertex_list
);
462 free (fixup_graph
->edge_list
);
466 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
469 create_fixup_graph (fixup_graph_type
*fixup_graph
)
471 double sqrt_avg_vertex_weight
= 0;
472 double total_vertex_weight
= 0;
475 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */
476 gcov_type
*diff_out_in
= NULL
;
477 gcov_type supply_value
= 0, demand_value
= 0;
479 int new_entry_index
= 0, new_exit_index
= 0;
485 fixup_edge_p pfedge
, r_pfedge
;
486 fixup_edge_p fedge_list
;
489 /* Each basic_block will be split into 2 during vertex transformation. */
490 int fnum_vertices_after_transform
= 2 * n_basic_blocks
;
491 int fnum_edges_after_transform
= n_edges
+ n_basic_blocks
;
493 /* Count the new SOURCE and EXIT vertices to be added. */
494 int fmax_num_vertices
=
495 fnum_vertices_after_transform
+ n_edges
+ n_basic_blocks
+ 2;
497 /* In create_fixup_graph: Each basic block and edge can be split into 3
498 edges. Number of balance edges = n_basic_blocks - 1. And there is 1 edge
499 connecting new_entry and new_exit, and 2 edges connecting new_entry to
500 entry, and exit to new_exit. So after create_fixup_graph:
501 max_edges = 4 * n_basic_blocks + 3 * n_edges + 2
502 Accounting for residual flow edges
503 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges + 2)
504 = 8 * n_basic_blocks + 6 * n_edges + 4
505 < 8 * n_basic_blocks + 8 * n_edges + 8. */
506 int fmax_num_edges
= 8 * (n_basic_blocks
+ n_edges
+ 1);
508 /* Initial num of vertices in the fixup graph. */
509 fixup_graph
->num_vertices
= n_basic_blocks
;
511 /* Fixup graph vertex list. */
512 fixup_graph
->vertex_list
=
513 (fixup_vertex_p
) xcalloc (fmax_num_vertices
, sizeof (fixup_vertex_type
));
515 /* Fixup graph edge list. */
516 fixup_graph
->edge_list
=
517 (fixup_edge_p
) xcalloc (fmax_num_edges
, sizeof (fixup_edge_type
));
520 (gcov_type
*) xcalloc (1 + fnum_vertices_after_transform
,
523 /* Compute constants b, k_pos, k_neg used in the cost function calculation.
524 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */
526 total_vertex_weight
+= bb
->count
;
528 sqrt_avg_vertex_weight
= mcf_sqrt (total_vertex_weight
/ n_basic_blocks
);
530 k_pos
= K_POS (sqrt_avg_vertex_weight
);
531 k_neg
= K_NEG (sqrt_avg_vertex_weight
);
533 /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
534 connected by an edge e from v' to v''. w(e) = w(v). */
537 fprintf (dump_file
, "\nVertex transformation:\n");
541 /* v'->v'': index1->(index1+1). */
544 fcost
= (gcov_type
) COST (k_pos
, bb
->count
);
545 add_fixup_edge (fixup_graph
, i
, i
+ 1, VERTEX_SPLIT_EDGE
, bb
->count
,
546 fcost
, CAP_INFINITY
);
547 fixup_graph
->num_vertices
++;
549 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
551 /* Edges with ignore attribute set should be treated like they don't
553 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
555 j
= 2 * e
->dest
->index
;
556 fcost
= (gcov_type
) COST (k_pos
, e
->count
);
557 add_fixup_edge (fixup_graph
, i
+ 1, j
, REDIRECT_EDGE
, e
->count
, fcost
,
562 /* After vertex transformation. */
563 gcc_assert (fixup_graph
->num_vertices
== fnum_vertices_after_transform
);
564 /* Redirect edges are not added for edges with ignore attribute. */
565 gcc_assert (fixup_graph
->num_edges
<= fnum_edges_after_transform
);
567 fnum_edges_after_transform
= fixup_graph
->num_edges
;
569 /* 2. Initialize D(v). */
570 for (i
= 0; i
< fnum_edges_after_transform
; i
++)
572 pfedge
= fixup_graph
->edge_list
+ i
;
573 diff_out_in
[pfedge
->src
] += pfedge
->weight
;
574 diff_out_in
[pfedge
->dest
] -= pfedge
->weight
;
577 /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */
578 for (i
= 0; i
<= 3; i
++)
581 /* 3. Add reverse edges: needed to decrease counts during smoothing. */
583 fprintf (dump_file
, "\nReverse edges:\n");
584 for (i
= 0; i
< fnum_edges_after_transform
; i
++)
586 pfedge
= fixup_graph
->edge_list
+ i
;
587 if ((pfedge
->src
== 0) || (pfedge
->src
== 2))
589 r_pfedge
= find_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
);
590 if (!r_pfedge
&& pfedge
->weight
)
592 /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
594 fcost
= (gcov_type
) COST (k_neg
, pfedge
->weight
);
595 add_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
,
596 REVERSE_EDGE
, 0, fcost
, pfedge
->weight
);
600 /* 4. Create single source and sink. Connect new source vertex s' to function
601 entry block. Connect sink vertex t' to function exit. */
603 fprintf (dump_file
, "\ns'->S, T->t':\n");
605 new_entry_index
= fixup_graph
->new_entry_index
= fixup_graph
->num_vertices
;
606 fixup_graph
->num_vertices
++;
607 /* Set capacity to 0 initially, it will be updated after
608 supply_value is computed. */
609 add_fixup_edge (fixup_graph
, new_entry_index
, ENTRY_BLOCK
,
610 SOURCE_CONNECT_EDGE
, 0 /* supply_value */, 0,
611 0 /* supply_value */);
612 add_fixup_edge (fixup_graph
, ENTRY_BLOCK
, new_entry_index
,
613 SOURCE_CONNECT_EDGE
, 0 /* supply_value */, 0,
614 0 /* supply_value */);
617 /* Set capacity to 0 initially, it will be updated after
618 demand_value is computed. */
619 new_exit_index
= fixup_graph
->new_exit_index
= fixup_graph
->num_vertices
;
620 fixup_graph
->num_vertices
++;
621 add_fixup_edge (fixup_graph
, 2 * EXIT_BLOCK
+ 1, new_exit_index
,
623 0 /* demand_value */, 0, 0 /* demand_value */);
624 add_fixup_edge (fixup_graph
, new_exit_index
, 2 * EXIT_BLOCK
+ 1,
626 0 /* demand_value */, 0, 0 /* demand_value */);
629 /* Create a back edge from the new_exit to the new_entry.
630 Initially, its capacity will be set to 0 so that it does not
631 affect max flow, but later its capacity will be changed to
632 infinity to cancel negative cycles. */
633 add_fixup_edge (fixup_graph
, new_exit_index
, new_entry_index
,
634 SINK_SOURCE_EDGE
, 0, 0, 0);
638 /* Connect vertices with unbalanced D(v) to source/sink. */
640 fprintf (dump_file
, "\nD(v) balance:\n");
642 /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start
643 with i = 4. diff_out_in[v''] should be 0, but may not be due to
644 rounding error. So here we consider all vertices. */
645 for (i
= 4; i
< new_entry_index
; i
+= 1)
647 if (diff_out_in
[i
] > 0)
649 add_fixup_edge (fixup_graph
, i
, new_exit_index
, BALANCE_EDGE
, 0, 0,
651 demand_value
+= diff_out_in
[i
];
653 else if (diff_out_in
[i
] < 0)
655 add_fixup_edge (fixup_graph
, new_entry_index
, i
, BALANCE_EDGE
, 0, 0,
657 supply_value
-= diff_out_in
[i
];
661 /* Set supply = demand. */
664 fprintf (dump_file
, "\nAdjust supply and demand:\n");
665 fprintf (dump_file
, "supply_value=" HOST_WIDEST_INT_PRINT_DEC
"\n",
667 fprintf (dump_file
, "demand_value=" HOST_WIDEST_INT_PRINT_DEC
"\n",
671 if (demand_value
> supply_value
)
673 pfedge
= find_fixup_edge (fixup_graph
, new_entry_index
, ENTRY_BLOCK
);
674 pfedge
->max_capacity
+= (demand_value
- supply_value
);
678 pfedge
= find_fixup_edge (fixup_graph
, 2 * EXIT_BLOCK
+ 1, new_exit_index
);
679 pfedge
->max_capacity
+= (supply_value
- demand_value
);
682 /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
683 created by the vertex transformation step from self-edges in the original
684 CFG and by the reverse edges added earlier. */
686 fprintf (dump_file
, "\nNormalize edges:\n");
688 fnum_edges
= fixup_graph
->num_edges
;
689 fedge_list
= fixup_graph
->edge_list
;
691 for (i
= 0; i
< fnum_edges
; i
++)
693 pfedge
= fedge_list
+ i
;
694 r_pfedge
= find_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
);
695 if (((pfedge
->type
== VERTEX_SPLIT_EDGE
)
696 || (pfedge
->type
== REDIRECT_EDGE
)) && r_pfedge
)
698 new_index
= fixup_graph
->num_vertices
;
699 fixup_graph
->num_vertices
++;
703 fprintf (dump_file
, "\nAnti-parallel edge:\n");
704 dump_fixup_edge (dump_file
, fixup_graph
, pfedge
);
705 dump_fixup_edge (dump_file
, fixup_graph
, r_pfedge
);
706 fprintf (dump_file
, "New vertex is %d.\n", new_index
);
707 fprintf (dump_file
, "------------------\n");
710 pfedge
->norm_vertex_index
= new_index
;
713 fprintf (dump_file
, "After normalization:\n");
714 dump_fixup_edge (dump_file
, fixup_graph
, pfedge
);
717 /* Add a new fixup edge: new_index->src. */
718 add_fixup_edge (fixup_graph
, new_index
, pfedge
->src
,
719 REVERSE_NORMALIZED_EDGE
, 0, 0,
720 r_pfedge
->max_capacity
);
721 gcc_assert (fixup_graph
->num_vertices
<= fmax_num_vertices
);
723 /* Edge: r_pfedge->src -> r_pfedge->dest
724 ==> r_pfedge->src -> new_index. */
725 r_pfedge
->dest
= new_index
;
726 r_pfedge
->type
= REVERSE_NORMALIZED_EDGE
;
727 r_pfedge
->max_capacity
= pfedge
->max_capacity
;
729 dump_fixup_edge (dump_file
, fixup_graph
, r_pfedge
);
734 dump_fixup_graph (dump_file
, fixup_graph
, "After create_fixup_graph()");
741 /* Allocates space for the structures in AUGMENTING_PATH. The space needed is
742 proportional to the number of nodes in the graph, which is given by
746 init_augmenting_path (augmenting_path_type
*augmenting_path
, int graph_size
)
748 augmenting_path
->queue_list
.queue
= (int *)
749 xcalloc (graph_size
+ 2, sizeof (int));
750 augmenting_path
->queue_list
.size
= graph_size
+ 2;
751 augmenting_path
->bb_pred
= (int *) xcalloc (graph_size
, sizeof (int));
752 augmenting_path
->is_visited
= (int *) xcalloc (graph_size
, sizeof (int));
755 /* Free the structures in AUGMENTING_PATH. */
757 free_augmenting_path (augmenting_path_type
*augmenting_path
)
759 free (augmenting_path
->queue_list
.queue
);
760 free (augmenting_path
->bb_pred
);
761 free (augmenting_path
->is_visited
);
765 /* Queue routines. Assumes queue will never overflow. */
768 init_queue (queue_type
*queue_list
)
770 gcc_assert (queue_list
);
771 queue_list
->head
= 0;
772 queue_list
->tail
= 0;
775 /* Return true if QUEUE_LIST is empty. */
777 is_empty (queue_type
*queue_list
)
779 return (queue_list
->head
== queue_list
->tail
);
782 /* Insert element X into QUEUE_LIST. */
784 enqueue (queue_type
*queue_list
, int x
)
786 gcc_assert (queue_list
->tail
< queue_list
->size
);
787 queue_list
->queue
[queue_list
->tail
] = x
;
788 (queue_list
->tail
)++;
791 /* Return the first element in QUEUE_LIST. */
793 dequeue (queue_type
*queue_list
)
796 gcc_assert (queue_list
->head
>= 0);
797 x
= queue_list
->queue
[queue_list
->head
];
798 (queue_list
->head
)++;
803 /* Finds a negative cycle in the residual network using
804 the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
805 minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
809 FIXUP_GRAPH - Residual graph (input/output)
810 The following are allocated/freed by the caller:
811 PI - Vector to hold predecessors in path (pi = pred index)
812 D - D[I] holds minimum cost of path from i to sink
813 CYCLE - Vector to hold the minimum cost cycle
816 true if a negative cycle was found, false otherwise. */
819 cancel_negative_cycle (fixup_graph_type
*fixup_graph
,
820 int *pi
, gcov_type
*d
, int *cycle
)
823 int fnum_vertices
, fnum_edges
;
824 fixup_edge_p fedge_list
, pfedge
, r_pfedge
;
825 bool found_cycle
= false;
826 int cycle_start
= 0, cycle_end
= 0;
827 gcov_type sum_cost
= 0, cycle_flow
= 0;
828 bool propagated
= false;
830 gcc_assert (fixup_graph
);
831 fnum_vertices
= fixup_graph
->num_vertices
;
832 fnum_edges
= fixup_graph
->num_edges
;
833 fedge_list
= fixup_graph
->edge_list
;
837 for (i
= 1; i
< fnum_vertices
; i
++)
846 for (k
= 1; k
< fnum_vertices
; k
++)
849 for (i
= 0; i
< fnum_edges
; i
++)
851 pfedge
= fedge_list
+ i
;
852 if (pfedge
->is_rflow_valid
&& pfedge
->rflow
853 && d
[pfedge
->src
] != CAP_INFINITY
854 && (d
[pfedge
->dest
] > d
[pfedge
->src
] + pfedge
->cost
))
856 d
[pfedge
->dest
] = d
[pfedge
->src
] + pfedge
->cost
;
857 pi
[pfedge
->dest
] = pfedge
->src
;
866 /* No negative cycles exist. */
870 for (i
= 0; i
< fnum_edges
; i
++)
872 pfedge
= fedge_list
+ i
;
873 if (pfedge
->is_rflow_valid
&& pfedge
->rflow
874 && d
[pfedge
->src
] != CAP_INFINITY
875 && (d
[pfedge
->dest
] > d
[pfedge
->src
] + pfedge
->cost
))
885 /* Augment the cycle with the cycle's minimum residual capacity. */
887 cycle
[0] = pfedge
->dest
;
890 for (i
= 1; i
< fnum_vertices
; i
++)
894 for (k
= 0; k
< i
; k
++)
898 /* cycle[k] -> ... -> cycle[i]. */
909 gcc_assert (cycle
[cycle_start
] == cycle
[cycle_end
]);
911 fprintf (dump_file
, "\nNegative cycle length is %d:\n",
912 cycle_end
- cycle_start
);
915 cycle_flow
= CAP_INFINITY
;
916 for (k
= cycle_start
; k
< cycle_end
; k
++)
918 pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
+ 1], cycle
[k
]);
919 cycle_flow
= MIN (cycle_flow
, pfedge
->rflow
);
920 sum_cost
+= pfedge
->cost
;
922 fprintf (dump_file
, "%d ", cycle
[k
]);
927 fprintf (dump_file
, "%d", cycle
[k
]);
929 ": (" HOST_WIDEST_INT_PRINT_DEC
", " HOST_WIDEST_INT_PRINT_DEC
930 ")\n", sum_cost
, cycle_flow
);
932 "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC
"\n",
936 for (k
= cycle_start
; k
< cycle_end
; k
++)
938 pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
+ 1], cycle
[k
]);
939 r_pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
], cycle
[k
+ 1]);
940 if (pfedge
->rflow
!= CAP_INFINITY
)
941 pfedge
->rflow
-= cycle_flow
;
943 pfedge
->flow
+= cycle_flow
;
944 if (r_pfedge
->rflow
!= CAP_INFINITY
)
945 r_pfedge
->rflow
+= cycle_flow
;
947 r_pfedge
->flow
-= cycle_flow
;
954 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
955 the edges. ENTRY and EXIT vertices should not be considered. */
958 compute_residual_flow (fixup_graph_type
*fixup_graph
)
962 fixup_edge_p fedge_list
, pfedge
;
964 gcc_assert (fixup_graph
);
967 fputs ("\ncompute_residual_flow():\n", dump_file
);
969 fnum_edges
= fixup_graph
->num_edges
;
970 fedge_list
= fixup_graph
->edge_list
;
972 for (i
= 0; i
< fnum_edges
; i
++)
974 pfedge
= fedge_list
+ i
;
975 pfedge
->rflow
= pfedge
->max_capacity
== CAP_INFINITY
?
976 CAP_INFINITY
: pfedge
->max_capacity
- pfedge
->flow
;
977 pfedge
->is_rflow_valid
= true;
978 add_rfixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
, pfedge
->flow
,
984 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
985 SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
986 this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
987 to reflect the path found.
988 Returns: 0 if no augmenting path is found, 1 otherwise. */
991 find_augmenting_path (fixup_graph_type
*fixup_graph
,
992 augmenting_path_type
*augmenting_path
, int source
,
997 fixup_vertex_p fvertex_list
, pfvertex
;
999 int *bb_pred
, *is_visited
;
1000 queue_type
*queue_list
;
1002 gcc_assert (augmenting_path
);
1003 bb_pred
= augmenting_path
->bb_pred
;
1004 gcc_assert (bb_pred
);
1005 is_visited
= augmenting_path
->is_visited
;
1006 gcc_assert (is_visited
);
1007 queue_list
= &(augmenting_path
->queue_list
);
1009 gcc_assert (fixup_graph
);
1011 fvertex_list
= fixup_graph
->vertex_list
;
1013 for (u
= 0; u
< fixup_graph
->num_vertices
; u
++)
1016 init_queue (queue_list
);
1017 enqueue (queue_list
, source
);
1018 bb_pred
[source
] = -1;
1020 while (!is_empty (queue_list
))
1022 u
= dequeue (queue_list
);
1024 pfvertex
= fvertex_list
+ u
;
1025 for (i
= 0; VEC_iterate (fixup_edge_p
, pfvertex
->succ_edges
, i
, pfedge
);
1028 int dest
= pfedge
->dest
;
1029 if ((pfedge
->rflow
> 0) && (is_visited
[dest
] == 0))
1031 enqueue (queue_list
, dest
);
1033 is_visited
[dest
] = 1;
1044 /* Routine to find the maximal flow:
1046 1. Initialize flow to 0
1047 2. Find an augmenting path form source to sink.
1048 3. Send flow equal to the path's residual capacity along the edges of this path.
1049 4. Repeat steps 2 and 3 until no new augmenting path is found.
1052 SOURCE: index of source vertex (input)
1053 SINK: index of sink vertex (input)
1054 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1055 set to have a valid maximal flow by this routine. (input)
1056 Return: Maximum flow possible. */
1059 find_max_flow (fixup_graph_type
*fixup_graph
, int source
, int sink
)
1062 augmenting_path_type augmenting_path
;
1064 gcov_type max_flow
= 0;
1066 fixup_edge_p fedge_list
, pfedge
, r_pfedge
;
1068 gcc_assert (fixup_graph
);
1070 fnum_edges
= fixup_graph
->num_edges
;
1071 fedge_list
= fixup_graph
->edge_list
;
1073 /* Initialize flow to 0. */
1074 for (i
= 0; i
< fnum_edges
; i
++)
1076 pfedge
= fedge_list
+ i
;
1080 compute_residual_flow (fixup_graph
);
1082 init_augmenting_path (&augmenting_path
, fixup_graph
->num_vertices
);
1084 bb_pred
= augmenting_path
.bb_pred
;
1085 while (find_augmenting_path (fixup_graph
, &augmenting_path
, source
, sink
))
1087 /* Determine the amount by which we can increment the flow. */
1088 gcov_type increment
= CAP_INFINITY
;
1089 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1091 pfedge
= find_fixup_edge (fixup_graph
, bb_pred
[u
], u
);
1092 increment
= MIN (increment
, pfedge
->rflow
);
1094 max_flow
+= increment
;
1096 /* Now increment the flow. EXIT vertex index is 1. */
1097 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1099 pfedge
= find_fixup_edge (fixup_graph
, bb_pred
[u
], u
);
1100 r_pfedge
= find_fixup_edge (fixup_graph
, u
, bb_pred
[u
]);
1102 if (pfedge
->rflow
!= CAP_INFINITY
)
1103 pfedge
->rflow
-= increment
;
1104 if (r_pfedge
->rflow
!= CAP_INFINITY
)
1105 r_pfedge
->rflow
+= increment
;
1110 pfedge
->flow
+= increment
;
1114 /* backward edge. */
1115 gcc_assert (r_pfedge
->type
);
1116 r_pfedge
->flow
-= increment
;
1122 fprintf (dump_file
, "\nDump augmenting path:\n");
1123 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1125 print_basic_block (dump_file
, fixup_graph
, u
);
1126 fprintf (dump_file
, "<-");
1129 "ENTRY (path_capacity=" HOST_WIDEST_INT_PRINT_DEC
")\n",
1132 "Network flow is " HOST_WIDEST_INT_PRINT_DEC
".\n",
1137 free_augmenting_path (&augmenting_path
);
1139 dump_fixup_graph (dump_file
, fixup_graph
, "After find_max_flow()");
1144 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1145 after applying the find_minimum_cost_flow() routine. */
1148 adjust_cfg_counts (fixup_graph_type
*fixup_graph
)
1154 fixup_edge_p pfedge
, pfedge_n
;
1156 gcc_assert (fixup_graph
);
1159 fprintf (dump_file
, "\nadjust_cfg_counts():\n");
1161 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1168 "BB%d: " HOST_WIDEST_INT_PRINT_DEC
"", bb
->index
, bb
->count
);
1170 pfedge
= find_fixup_edge (fixup_graph
, i
, i
+ 1);
1173 bb
->count
+= pfedge
->flow
;
1176 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1178 print_edge (dump_file
, fixup_graph
, i
, i
+ 1);
1179 fprintf (dump_file
, ")");
1184 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1185 /* Deduct flow from normalized reverse edge. */
1186 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1188 bb
->count
-= pfedge_n
->flow
;
1191 fprintf (dump_file
, " - " HOST_WIDEST_INT_PRINT_DEC
"(",
1193 print_edge (dump_file
, fixup_graph
, i
+ 1,
1194 pfedge
->norm_vertex_index
);
1195 fprintf (dump_file
, ")");
1199 fprintf (dump_file
, " = " HOST_WIDEST_INT_PRINT_DEC
"\n", bb
->count
);
1202 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1204 /* Treat edges with ignore attribute set as if they don't exist. */
1205 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1208 j
= 2 * e
->dest
->index
;
1210 fprintf (dump_file
, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC
"",
1211 bb
->index
, e
->dest
->index
, e
->count
);
1213 pfedge
= find_fixup_edge (fixup_graph
, i
+ 1, j
);
1215 if (bb
->index
!= e
->dest
->index
)
1217 /* Non-self edge. */
1220 e
->count
+= pfedge
->flow
;
1223 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1225 print_edge (dump_file
, fixup_graph
, i
+ 1, j
);
1226 fprintf (dump_file
, ")");
1231 find_fixup_edge (fixup_graph
, j
, pfedge
->norm_vertex_index
);
1232 /* Deduct flow from normalized reverse edge. */
1233 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1235 e
->count
-= pfedge_n
->flow
;
1238 fprintf (dump_file
, " - " HOST_WIDEST_INT_PRINT_DEC
"(",
1240 print_edge (dump_file
, fixup_graph
, j
,
1241 pfedge
->norm_vertex_index
);
1242 fprintf (dump_file
, ")");
1248 /* Handle self edges. Self edge is split with a normalization
1249 vertex. Here i=j. */
1250 pfedge
= find_fixup_edge (fixup_graph
, j
, i
+ 1);
1252 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1253 e
->count
+= pfedge_n
->flow
;
1254 bb
->count
+= pfedge_n
->flow
;
1257 fprintf (dump_file
, "(self edge)");
1258 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1260 print_edge (dump_file
, fixup_graph
, i
+ 1,
1261 pfedge
->norm_vertex_index
);
1262 fprintf (dump_file
, ")");
1267 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1269 fprintf (dump_file
, " = " HOST_WIDEST_INT_PRINT_DEC
"\t(%.1f%%)\n",
1270 e
->count
, e
->probability
* 100.0 / REG_BR_PROB_BASE
);
1274 ENTRY_BLOCK_PTR
->count
= sum_edge_counts (ENTRY_BLOCK_PTR
->succs
);
1275 EXIT_BLOCK_PTR
->count
= sum_edge_counts (EXIT_BLOCK_PTR
->preds
);
1277 /* Compute edge probabilities. */
1282 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1283 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1288 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1289 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1293 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1295 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1296 e
->probability
= REG_BR_PROB_BASE
/ total
;
1303 total
+= EDGE_COUNT (bb
->succs
);
1304 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1305 e
->probability
= REG_BR_PROB_BASE
/ total
;
1312 fprintf (dump_file
, "\nCheck %s() CFG flow conservation:\n",
1313 lang_hooks
.decl_printable_name (current_function_decl
, 2));
1314 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
, next_bb
)
1316 if ((bb
->count
!= sum_edge_counts (bb
->preds
))
1317 || (bb
->count
!= sum_edge_counts (bb
->succs
)))
1320 "BB%d(" HOST_WIDEST_INT_PRINT_DEC
") **INVALID**: ",
1321 bb
->index
, bb
->count
);
1323 "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC
1324 ") **INVALID**: \n", bb
->index
, bb
->count
);
1325 fprintf (dump_file
, "in_edges=" HOST_WIDEST_INT_PRINT_DEC
" ",
1326 sum_edge_counts (bb
->preds
));
1327 fprintf (dump_file
, "out_edges=" HOST_WIDEST_INT_PRINT_DEC
"\n",
1328 sum_edge_counts (bb
->succs
));
1335 /* Called before negative_cycle_cancellation, to form a cycle between
1336 * new_exit to new_entry in FIXUP_GRAPH with capacity MAX_FLOW. We
1337 * don't want the flow in the BALANCE_EDGE to be modified, so we set
1338 * the residural flow of those edges to 0 */
1341 modify_sink_source_capacity (fixup_graph_type
*fixup_graph
, gcov_type max_flow
)
1343 fixup_edge_p edge
, r_edge
;
1345 int entry
= ENTRY_BLOCK
;
1346 int exit
= 2 * EXIT_BLOCK
+ 1;
1347 int new_entry
= fixup_graph
->new_entry_index
;
1348 int new_exit
= fixup_graph
->new_exit_index
;
1350 edge
= find_fixup_edge (fixup_graph
, new_entry
, entry
);
1351 edge
->max_capacity
= CAP_INFINITY
;
1352 edge
->rflow
= CAP_INFINITY
;
1354 edge
= find_fixup_edge (fixup_graph
, entry
, new_entry
);
1355 edge
->max_capacity
= CAP_INFINITY
;
1356 edge
->rflow
= CAP_INFINITY
;
1358 edge
= find_fixup_edge (fixup_graph
, exit
, new_exit
);
1359 edge
->max_capacity
= CAP_INFINITY
;
1360 edge
->rflow
= CAP_INFINITY
;
1362 edge
= find_fixup_edge (fixup_graph
, new_exit
, exit
);
1363 edge
->max_capacity
= CAP_INFINITY
;
1364 edge
->rflow
= CAP_INFINITY
;
1366 edge
= find_fixup_edge (fixup_graph
, new_exit
, new_entry
);
1367 edge
->max_capacity
= CAP_INFINITY
;
1368 edge
->flow
= max_flow
;
1369 edge
->rflow
= CAP_INFINITY
;
1371 r_edge
= find_fixup_edge (fixup_graph
, new_entry
, new_exit
);
1372 r_edge
->rflow
= max_flow
;
1374 /* Find all the backwards residual edges corresponding to
1375 BALANCE_EDGEs and set their residual flow to 0 to enforce a
1376 minimum flow constraint on these edges. */
1377 for (i
= 4; i
< new_entry
; i
+= 1)
1379 edge
= find_fixup_edge (fixup_graph
, i
, new_entry
);
1382 edge
= find_fixup_edge (fixup_graph
, new_exit
, i
);
1389 /* Implements the negative cycle canceling algorithm to compute a minimum cost
1392 1. Find maximal flow.
1393 2. Form residual network
1395 While G contains a negative cost cycle C, reverse the flow on the found cycle
1396 by the minimum residual capacity in that cycle.
1397 4. Form the minimal cost flow
1400 FIXUP_GRAPH - Initial fixup graph.
1401 The flow field is modified to represent the minimum cost flow. */
1404 find_minimum_cost_flow (fixup_graph_type
*fixup_graph
)
1406 /* Holds the index of predecessor in path. */
1408 /* Used to hold the minimum cost cycle. */
1410 /* Used to record the number of iterations of cancel_negative_cycle. */
1412 /* Vector d[i] holds the minimum cost of path from i to sink. */
1416 int new_entry_index
;
1419 gcc_assert (fixup_graph
);
1420 fnum_vertices
= fixup_graph
->num_vertices
;
1421 new_exit_index
= fixup_graph
->new_exit_index
;
1422 new_entry_index
= fixup_graph
->new_entry_index
;
1424 max_flow
= find_max_flow (fixup_graph
, new_entry_index
, new_exit_index
);
1426 /* Adjust the fixup graph to translate things into a minimum cost
1427 circulation problem. */
1428 modify_sink_source_capacity (fixup_graph
, max_flow
);
1430 /* Initialize the structures for find_negative_cycle(). */
1431 pred
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1432 d
= (gcov_type
*) xcalloc (fnum_vertices
, sizeof (gcov_type
));
1433 cycle
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1435 /* Repeatedly find and cancel negative cost cycles, until
1436 no more negative cycles exist. This also updates the flow field
1437 to represent the minimum cost flow so far. */
1439 while (cancel_negative_cycle (fixup_graph
, pred
, d
, cycle
))
1442 if (iteration
> MAX_ITER (fixup_graph
->num_vertices
,
1443 fixup_graph
->num_edges
))
1445 if (flag_opt_info
>= OPT_INFO_MAX
)
1446 inform (DECL_SOURCE_LOCATION (current_function_decl
),
1447 "Exiting profile correction early to avoid excessive "
1454 dump_fixup_graph (dump_file
, fixup_graph
,
1455 "After find_minimum_cost_flow()");
1457 /* Cleanup structures. */
1464 /* Compute the sum of the edge counts in TO_EDGES. */
1467 sum_edge_counts (VEC (edge
, gc
) *to_edges
)
1473 FOR_EACH_EDGE (e
, ei
, to_edges
)
1475 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1483 /* Main routine. Smoothes the intial assigned basic block and edge counts using
1484 a minimum cost flow algorithm, to ensure that the flow consistency rule is
1485 obeyed: sum of outgoing edges = sum of incoming edges for each basic
1489 mcf_smooth_cfg (void)
1491 fixup_graph_type fixup_graph
;
1492 memset (&fixup_graph
, 0, sizeof (fixup_graph
));
1493 create_fixup_graph (&fixup_graph
);
1494 find_minimum_cost_flow (&fixup_graph
);
1495 adjust_cfg_counts (&fixup_graph
);
1496 delete_fixup_graph (&fixup_graph
);