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"
49 #include "basic-block.h"
53 /* CAP_INFINITY: Constant to represent infinite capacity. */
54 #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT)
57 #define K_POS(b) ((b))
58 #define K_NEG(b) (50 * (b))
59 #define COST(k, w) ((k) / mcf_ln ((w) + 2))
60 /* Limit the number of iterations for cancel_negative_cycles() to ensure
61 reasonable compile time. */
62 #define MAX_ITER(n, e) 10 + (1000000 / ((n) * (e)))
66 VERTEX_SPLIT_EDGE
, /* Edge to represent vertex with w(e) = w(v). */
67 REDIRECT_EDGE
, /* Edge after vertex transformation. */
69 SOURCE_CONNECT_EDGE
, /* Single edge connecting to single source. */
70 SINK_CONNECT_EDGE
, /* Single edge connecting to single sink. */
71 BALANCE_EDGE
, /* Edge connecting with source/sink: cp(e) = 0. */
72 REDIRECT_NORMALIZED_EDGE
, /* Normalized edge for a redirect edge. */
73 REVERSE_NORMALIZED_EDGE
/* Normalized edge for a reverse edge. */
76 /* Structure to represent an edge in the fixup graph. */
77 typedef struct fixup_edge_d
81 /* Flag denoting type of edge and attributes for the flow field. */
84 /* Index to the normalization vertex added for this edge. */
85 int norm_vertex_index
;
86 /* Flow for this edge. */
88 /* Residual flow for this edge - used during negative cycle canceling. */
92 gcov_type max_capacity
;
95 typedef fixup_edge_type
*fixup_edge_p
;
97 DEF_VEC_P (fixup_edge_p
);
98 DEF_VEC_ALLOC_P (fixup_edge_p
, heap
);
100 /* Structure to represent a vertex in the fixup graph. */
101 typedef struct fixup_vertex_d
103 VEC (fixup_edge_p
, heap
) *succ_edges
;
106 typedef fixup_vertex_type
*fixup_vertex_p
;
108 /* Fixup graph used in the MCF algorithm. */
109 typedef struct fixup_graph_d
111 /* Current number of vertices for the graph. */
113 /* Current number of edges for the graph. */
115 /* Index of new entry vertex. */
117 /* Index of new exit vertex. */
119 /* Fixup vertex list. Adjacency list for fixup graph. */
120 fixup_vertex_p vertex_list
;
121 /* Fixup edge list. */
122 fixup_edge_p edge_list
;
125 typedef struct queue_d
133 /* Structure used in the maximal flow routines to find augmenting path. */
134 typedef struct augmenting_path_d
136 /* Queue used to hold vertex indices. */
137 queue_type queue_list
;
138 /* Vector to hold chain of pred vertex indices in augmenting path. */
140 /* Vector that indicates if basic block i has been visited. */
142 } augmenting_path_type
;
145 /* Function definitions. */
147 /* Dump routines to aid debugging. */
149 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */
152 print_basic_block (FILE *file
, fixup_graph_type
*fixup_graph
, int n
)
154 if (n
== ENTRY_BLOCK
)
155 fputs ("ENTRY", file
);
156 else if (n
== ENTRY_BLOCK
+ 1)
157 fputs ("ENTRY''", file
);
158 else if (n
== 2 * EXIT_BLOCK
)
159 fputs ("EXIT", file
);
160 else if (n
== 2 * EXIT_BLOCK
+ 1)
161 fputs ("EXIT''", file
);
162 else if (n
== fixup_graph
->new_exit_index
)
163 fputs ("NEW_EXIT", file
);
164 else if (n
== fixup_graph
->new_entry_index
)
165 fputs ("NEW_ENTRY", file
);
168 fprintf (file
, "%d", n
/ 2);
177 /* Print edge S->D for given fixup_graph with n' and n'' format.
179 S is the index of the source vertex of the edge (input) and
180 D is the index of the destination vertex of the edge (input) for the given
181 fixup_graph (input). */
184 print_edge (FILE *file
, fixup_graph_type
*fixup_graph
, int s
, int d
)
186 print_basic_block (file
, fixup_graph
, s
);
188 print_basic_block (file
, fixup_graph
, d
);
192 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
195 dump_fixup_edge (FILE *file
, fixup_graph_type
*fixup_graph
, fixup_edge_p fedge
)
199 fputs ("NULL fixup graph edge.\n", file
);
203 print_edge (file
, fixup_graph
, fedge
->src
, fedge
->dest
);
208 fprintf (file
, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC
"/",
210 if (fedge
->max_capacity
== CAP_INFINITY
)
211 fputs ("+oo,", file
);
213 fprintf (file
, "" HOST_WIDEST_INT_PRINT_DEC
",", fedge
->max_capacity
);
216 if (fedge
->is_rflow_valid
)
218 if (fedge
->rflow
== CAP_INFINITY
)
219 fputs (" rflow=+oo.", file
);
221 fprintf (file
, " rflow=" HOST_WIDEST_INT_PRINT_DEC
",", fedge
->rflow
);
224 fprintf (file
, " cost=" HOST_WIDEST_INT_PRINT_DEC
".", fedge
->cost
);
226 fprintf (file
, "\t(%d->%d)", fedge
->src
, fedge
->dest
);
232 case VERTEX_SPLIT_EDGE
:
233 fputs (" @VERTEX_SPLIT_EDGE", file
);
237 fputs (" @REDIRECT_EDGE", file
);
240 case SOURCE_CONNECT_EDGE
:
241 fputs (" @SOURCE_CONNECT_EDGE", file
);
244 case SINK_CONNECT_EDGE
:
245 fputs (" @SINK_CONNECT_EDGE", file
);
249 fputs (" @REVERSE_EDGE", file
);
253 fputs (" @BALANCE_EDGE", file
);
256 case REDIRECT_NORMALIZED_EDGE
:
257 case REVERSE_NORMALIZED_EDGE
:
258 fputs (" @NORMALIZED_EDGE", file
);
262 fputs (" @INVALID_EDGE", file
);
270 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
271 file. The input string MSG is printed out as a heading. */
274 dump_fixup_graph (FILE *file
, fixup_graph_type
*fixup_graph
, const char *msg
)
277 int fnum_vertices
, fnum_edges
;
279 fixup_vertex_p fvertex_list
, pfvertex
;
282 gcc_assert (fixup_graph
);
283 fvertex_list
= fixup_graph
->vertex_list
;
284 fnum_vertices
= fixup_graph
->num_vertices
;
285 fnum_edges
= fixup_graph
->num_edges
;
287 fprintf (file
, "\nDump fixup graph for %s(): %s.\n",
288 current_function_name (), msg
);
290 "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
291 fnum_vertices
, fnum_edges
, fixup_graph
->new_exit_index
);
293 for (i
= 0; i
< fnum_vertices
; i
++)
295 pfvertex
= fvertex_list
+ i
;
296 fprintf (file
, "vertex_list[%d]: %d succ fixup edges.\n",
297 i
, VEC_length (fixup_edge_p
, pfvertex
->succ_edges
));
299 for (j
= 0; VEC_iterate (fixup_edge_p
, pfvertex
->succ_edges
, j
, pfedge
);
302 /* Distinguish forward edges and backward edges in the residual flow
305 fputs ("(f) ", file
);
306 else if (pfedge
->is_rflow_valid
)
307 fputs ("(b) ", file
);
308 dump_fixup_edge (file
, fixup_graph
, pfedge
);
316 /* Utility routines. */
317 /* ln() implementation: approximate calculation. Returns ln of X. */
338 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
339 implementation) by John Carmack. Returns sqrt of X. */
344 #define MAGIC_CONST1 0x1fbcf800
345 #define MAGIC_CONST2 0x5f3759df
349 } convertor
, convertor2
;
353 convertor
.floatPart
= x
;
354 convertor2
.floatPart
= x
;
355 convertor
.intPart
= MAGIC_CONST1
+ (convertor
.intPart
>> 1);
356 convertor2
.intPart
= MAGIC_CONST2
- (convertor2
.intPart
>> 1);
358 return 0.5f
* (convertor
.floatPart
+ (x
* convertor2
.floatPart
));
362 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
363 (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
364 added set to COST. */
367 add_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
, gcov_type cost
)
369 fixup_vertex_p curr_vertex
= fixup_graph
->vertex_list
+ src
;
370 fixup_edge_p curr_edge
= fixup_graph
->edge_list
+ fixup_graph
->num_edges
;
371 curr_edge
->src
= src
;
372 curr_edge
->dest
= dest
;
373 curr_edge
->cost
= cost
;
374 fixup_graph
->num_edges
++;
376 dump_fixup_edge (dump_file
, fixup_graph
, curr_edge
);
377 VEC_safe_push (fixup_edge_p
, heap
, curr_vertex
->succ_edges
, curr_edge
);
382 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
383 MAX_CAPACITY to the edge_list in the fixup graph. */
386 add_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
387 edge_type type
, gcov_type weight
, gcov_type cost
,
388 gcov_type max_capacity
)
390 fixup_edge_p curr_edge
= add_edge(fixup_graph
, src
, dest
, cost
);
391 curr_edge
->type
= type
;
392 curr_edge
->weight
= weight
;
393 curr_edge
->max_capacity
= max_capacity
;
397 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
398 to the fixup graph. */
401 add_rfixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
402 gcov_type rflow
, gcov_type cost
)
404 fixup_edge_p curr_edge
= add_edge (fixup_graph
, src
, dest
, cost
);
405 curr_edge
->rflow
= rflow
;
406 curr_edge
->is_rflow_valid
= true;
407 /* This edge is not a valid edge - merely used to hold residual flow. */
408 curr_edge
->type
= INVALID_EDGE
;
412 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
413 exist in the FIXUP_GRAPH. */
416 find_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
)
420 fixup_vertex_p pfvertex
;
422 gcc_assert (src
< fixup_graph
->num_vertices
);
424 pfvertex
= fixup_graph
->vertex_list
+ src
;
426 for (j
= 0; VEC_iterate (fixup_edge_p
, pfvertex
->succ_edges
, j
, pfedge
);
428 if (pfedge
->dest
== dest
)
435 /* Cleanup routine to free structures in FIXUP_GRAPH. */
438 delete_fixup_graph (fixup_graph_type
*fixup_graph
)
441 int fnum_vertices
= fixup_graph
->num_vertices
;
442 fixup_vertex_p pfvertex
= fixup_graph
->vertex_list
;
444 for (i
= 0; i
< fnum_vertices
; i
++, pfvertex
++)
445 VEC_free (fixup_edge_p
, heap
, pfvertex
->succ_edges
);
447 free (fixup_graph
->vertex_list
);
448 free (fixup_graph
->edge_list
);
452 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
455 create_fixup_graph (fixup_graph_type
*fixup_graph
)
457 double sqrt_avg_vertex_weight
= 0;
458 double total_vertex_weight
= 0;
461 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */
462 gcov_type
*diff_out_in
= NULL
;
463 gcov_type supply_value
= 1, demand_value
= 0;
465 int new_entry_index
= 0, new_exit_index
= 0;
471 fixup_edge_p pfedge
, r_pfedge
;
472 fixup_edge_p fedge_list
;
475 /* Each basic_block will be split into 2 during vertex transformation. */
476 int fnum_vertices_after_transform
= 2 * n_basic_blocks
;
477 int fnum_edges_after_transform
= n_edges
+ n_basic_blocks
;
479 /* Count the new SOURCE and EXIT vertices to be added. */
480 int fmax_num_vertices
=
481 fnum_vertices_after_transform
+ n_edges
+ n_basic_blocks
+ 2;
483 /* In create_fixup_graph: Each basic block and edge can be split into 3
484 edges. Number of balance edges = n_basic_blocks. So after
486 max_edges = 4 * n_basic_blocks + 3 * n_edges
487 Accounting for residual flow edges
488 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
489 = 8 * n_basic_blocks + 6 * n_edges
490 < 8 * n_basic_blocks + 8 * n_edges. */
491 int fmax_num_edges
= 8 * (n_basic_blocks
+ n_edges
);
493 /* Initial num of vertices in the fixup graph. */
494 fixup_graph
->num_vertices
= n_basic_blocks
;
496 /* Fixup graph vertex list. */
497 fixup_graph
->vertex_list
=
498 (fixup_vertex_p
) xcalloc (fmax_num_vertices
, sizeof (fixup_vertex_type
));
500 /* Fixup graph edge list. */
501 fixup_graph
->edge_list
=
502 (fixup_edge_p
) xcalloc (fmax_num_edges
, sizeof (fixup_edge_type
));
505 (gcov_type
*) xcalloc (1 + fnum_vertices_after_transform
,
508 /* Compute constants b, k_pos, k_neg used in the cost function calculation.
509 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */
510 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
511 total_vertex_weight
+= bb
->count
;
513 sqrt_avg_vertex_weight
= mcf_sqrt (total_vertex_weight
/ n_basic_blocks
);
515 k_pos
= K_POS (sqrt_avg_vertex_weight
);
516 k_neg
= K_NEG (sqrt_avg_vertex_weight
);
518 /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
519 connected by an edge e from v' to v''. w(e) = w(v). */
522 fprintf (dump_file
, "\nVertex transformation:\n");
524 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
526 /* v'->v'': index1->(index1+1). */
528 fcost
= (gcov_type
) COST (k_pos
, bb
->count
);
529 add_fixup_edge (fixup_graph
, i
, i
+ 1, VERTEX_SPLIT_EDGE
, bb
->count
,
530 fcost
, CAP_INFINITY
);
531 fixup_graph
->num_vertices
++;
533 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
535 /* Edges with ignore attribute set should be treated like they don't
537 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
539 j
= 2 * e
->dest
->index
;
540 fcost
= (gcov_type
) COST (k_pos
, e
->count
);
541 add_fixup_edge (fixup_graph
, i
+ 1, j
, REDIRECT_EDGE
, e
->count
, fcost
,
546 /* After vertex transformation. */
547 gcc_assert (fixup_graph
->num_vertices
== fnum_vertices_after_transform
);
548 /* Redirect edges are not added for edges with ignore attribute. */
549 gcc_assert (fixup_graph
->num_edges
<= fnum_edges_after_transform
);
551 fnum_edges_after_transform
= fixup_graph
->num_edges
;
553 /* 2. Initialize D(v). */
554 for (i
= 0; i
< fnum_edges_after_transform
; i
++)
556 pfedge
= fixup_graph
->edge_list
+ i
;
557 diff_out_in
[pfedge
->src
] += pfedge
->weight
;
558 diff_out_in
[pfedge
->dest
] -= pfedge
->weight
;
561 /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */
562 for (i
= 0; i
<= 3; i
++)
565 /* 3. Add reverse edges: needed to decrease counts during smoothing. */
567 fprintf (dump_file
, "\nReverse edges:\n");
568 for (i
= 0; i
< fnum_edges_after_transform
; i
++)
570 pfedge
= fixup_graph
->edge_list
+ i
;
571 if ((pfedge
->src
== 0) || (pfedge
->src
== 2))
573 r_pfedge
= find_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
);
574 if (!r_pfedge
&& pfedge
->weight
)
576 /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
578 fcost
= (gcov_type
) COST (k_neg
, pfedge
->weight
);
579 add_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
,
580 REVERSE_EDGE
, 0, fcost
, pfedge
->weight
);
584 /* 4. Create single source and sink. Connect new source vertex s' to function
585 entry block. Connect sink vertex t' to function exit. */
587 fprintf (dump_file
, "\ns'->S, T->t':\n");
589 new_entry_index
= fixup_graph
->new_entry_index
= fixup_graph
->num_vertices
;
590 fixup_graph
->num_vertices
++;
591 /* Set supply_value to 1 to avoid zero count function ENTRY. */
592 add_fixup_edge (fixup_graph
, new_entry_index
, ENTRY_BLOCK
, SOURCE_CONNECT_EDGE
,
593 1 /* supply_value */, 0, 1 /* supply_value */);
595 /* Create new exit with EXIT_BLOCK as single pred. */
596 new_exit_index
= fixup_graph
->new_exit_index
= fixup_graph
->num_vertices
;
597 fixup_graph
->num_vertices
++;
598 add_fixup_edge (fixup_graph
, 2 * EXIT_BLOCK
+ 1, new_exit_index
,
600 0 /* demand_value */, 0, 0 /* demand_value */);
602 /* Connect vertices with unbalanced D(v) to source/sink. */
604 fprintf (dump_file
, "\nD(v) balance:\n");
605 /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
606 diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2. */
607 for (i
= 4; i
< new_entry_index
; i
+= 2)
609 if (diff_out_in
[i
] > 0)
611 add_fixup_edge (fixup_graph
, i
, new_exit_index
, BALANCE_EDGE
, 0, 0,
613 demand_value
+= diff_out_in
[i
];
615 else if (diff_out_in
[i
] < 0)
617 add_fixup_edge (fixup_graph
, new_entry_index
, i
, BALANCE_EDGE
, 0, 0,
619 supply_value
-= diff_out_in
[i
];
623 /* Set supply = demand. */
626 fprintf (dump_file
, "\nAdjust supply and demand:\n");
627 fprintf (dump_file
, "supply_value=" HOST_WIDEST_INT_PRINT_DEC
"\n",
629 fprintf (dump_file
, "demand_value=" HOST_WIDEST_INT_PRINT_DEC
"\n",
633 if (demand_value
> supply_value
)
635 pfedge
= find_fixup_edge (fixup_graph
, new_entry_index
, ENTRY_BLOCK
);
636 pfedge
->max_capacity
+= (demand_value
- supply_value
);
640 pfedge
= find_fixup_edge (fixup_graph
, 2 * EXIT_BLOCK
+ 1, new_exit_index
);
641 pfedge
->max_capacity
+= (supply_value
- demand_value
);
644 /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
645 created by the vertex transformation step from self-edges in the original
646 CFG and by the reverse edges added earlier. */
648 fprintf (dump_file
, "\nNormalize edges:\n");
650 fnum_edges
= fixup_graph
->num_edges
;
651 fedge_list
= fixup_graph
->edge_list
;
653 for (i
= 0; i
< fnum_edges
; i
++)
655 pfedge
= fedge_list
+ i
;
656 r_pfedge
= find_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
);
657 if (((pfedge
->type
== VERTEX_SPLIT_EDGE
)
658 || (pfedge
->type
== REDIRECT_EDGE
)) && r_pfedge
)
660 new_index
= fixup_graph
->num_vertices
;
661 fixup_graph
->num_vertices
++;
665 fprintf (dump_file
, "\nAnti-parallel edge:\n");
666 dump_fixup_edge (dump_file
, fixup_graph
, pfedge
);
667 dump_fixup_edge (dump_file
, fixup_graph
, r_pfedge
);
668 fprintf (dump_file
, "New vertex is %d.\n", new_index
);
669 fprintf (dump_file
, "------------------\n");
673 pfedge
->norm_vertex_index
= new_index
;
676 fprintf (dump_file
, "After normalization:\n");
677 dump_fixup_edge (dump_file
, fixup_graph
, pfedge
);
680 /* Add a new fixup edge: new_index->src. */
681 add_fixup_edge (fixup_graph
, new_index
, pfedge
->src
,
682 REVERSE_NORMALIZED_EDGE
, 0, r_pfedge
->cost
,
683 r_pfedge
->max_capacity
);
684 gcc_assert (fixup_graph
->num_vertices
<= fmax_num_vertices
);
686 /* Edge: r_pfedge->src -> r_pfedge->dest
687 ==> r_pfedge->src -> new_index. */
688 r_pfedge
->dest
= new_index
;
689 r_pfedge
->type
= REVERSE_NORMALIZED_EDGE
;
690 r_pfedge
->cost
= pfedge
->cost
;
691 r_pfedge
->max_capacity
= pfedge
->max_capacity
;
693 dump_fixup_edge (dump_file
, fixup_graph
, r_pfedge
);
698 dump_fixup_graph (dump_file
, fixup_graph
, "After create_fixup_graph()");
705 /* Allocates space for the structures in AUGMENTING_PATH. The space needed is
706 proportional to the number of nodes in the graph, which is given by
710 init_augmenting_path (augmenting_path_type
*augmenting_path
, int graph_size
)
712 augmenting_path
->queue_list
.queue
= (int *)
713 xcalloc (graph_size
+ 2, sizeof (int));
714 augmenting_path
->queue_list
.size
= graph_size
+ 2;
715 augmenting_path
->bb_pred
= (int *) xcalloc (graph_size
, sizeof (int));
716 augmenting_path
->is_visited
= (int *) xcalloc (graph_size
, sizeof (int));
719 /* Free the structures in AUGMENTING_PATH. */
721 free_augmenting_path (augmenting_path_type
*augmenting_path
)
723 free (augmenting_path
->queue_list
.queue
);
724 free (augmenting_path
->bb_pred
);
725 free (augmenting_path
->is_visited
);
729 /* Queue routines. Assumes queue will never overflow. */
732 init_queue (queue_type
*queue_list
)
734 gcc_assert (queue_list
);
735 queue_list
->head
= 0;
736 queue_list
->tail
= 0;
739 /* Return true if QUEUE_LIST is empty. */
741 is_empty (queue_type
*queue_list
)
743 return (queue_list
->head
== queue_list
->tail
);
746 /* Insert element X into QUEUE_LIST. */
748 enqueue (queue_type
*queue_list
, int x
)
750 gcc_assert (queue_list
->tail
< queue_list
->size
);
751 queue_list
->queue
[queue_list
->tail
] = x
;
752 (queue_list
->tail
)++;
755 /* Return the first element in QUEUE_LIST. */
757 dequeue (queue_type
*queue_list
)
760 gcc_assert (queue_list
->head
>= 0);
761 x
= queue_list
->queue
[queue_list
->head
];
762 (queue_list
->head
)++;
767 /* Finds a negative cycle in the residual network using
768 the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
769 minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
773 FIXUP_GRAPH - Residual graph (input/output)
774 The following are allocated/freed by the caller:
775 PI - Vector to hold predecessors in path (pi = pred index)
776 D - D[I] holds minimum cost of path from i to sink
777 CYCLE - Vector to hold the minimum cost cycle
780 true if a negative cycle was found, false otherwise. */
783 cancel_negative_cycle (fixup_graph_type
*fixup_graph
,
784 int *pi
, gcov_type
*d
, int *cycle
)
787 int fnum_vertices
, fnum_edges
;
788 fixup_edge_p fedge_list
, pfedge
, r_pfedge
;
789 bool found_cycle
= false;
790 int cycle_start
= 0, cycle_end
= 0;
791 gcov_type sum_cost
= 0, cycle_flow
= 0;
793 bool propagated
= false;
795 gcc_assert (fixup_graph
);
796 fnum_vertices
= fixup_graph
->num_vertices
;
797 fnum_edges
= fixup_graph
->num_edges
;
798 fedge_list
= fixup_graph
->edge_list
;
799 new_entry_index
= fixup_graph
->new_entry_index
;
803 for (i
= 1; i
< fnum_vertices
; i
++)
812 for (k
= 1; k
< fnum_vertices
; k
++)
815 for (i
= 0; i
< fnum_edges
; i
++)
817 pfedge
= fedge_list
+ i
;
818 if (pfedge
->src
== new_entry_index
)
820 if (pfedge
->is_rflow_valid
&& pfedge
->rflow
821 && d
[pfedge
->src
] != CAP_INFINITY
822 && (d
[pfedge
->dest
] > d
[pfedge
->src
] + pfedge
->cost
))
824 d
[pfedge
->dest
] = d
[pfedge
->src
] + pfedge
->cost
;
825 pi
[pfedge
->dest
] = pfedge
->src
;
834 /* No negative cycles exist. */
838 for (i
= 0; i
< fnum_edges
; i
++)
840 pfedge
= fedge_list
+ i
;
841 if (pfedge
->src
== new_entry_index
)
843 if (pfedge
->is_rflow_valid
&& pfedge
->rflow
844 && d
[pfedge
->src
] != CAP_INFINITY
845 && (d
[pfedge
->dest
] > d
[pfedge
->src
] + pfedge
->cost
))
855 /* Augment the cycle with the cycle's minimum residual capacity. */
857 cycle
[0] = pfedge
->dest
;
860 for (i
= 1; i
< fnum_vertices
; i
++)
864 for (k
= 0; k
< i
; k
++)
868 /* cycle[k] -> ... -> cycle[i]. */
879 gcc_assert (cycle
[cycle_start
] == cycle
[cycle_end
]);
881 fprintf (dump_file
, "\nNegative cycle length is %d:\n",
882 cycle_end
- cycle_start
);
885 cycle_flow
= CAP_INFINITY
;
886 for (k
= cycle_start
; k
< cycle_end
; k
++)
888 pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
+ 1], cycle
[k
]);
889 cycle_flow
= MIN (cycle_flow
, pfedge
->rflow
);
890 sum_cost
+= pfedge
->cost
;
892 fprintf (dump_file
, "%d ", cycle
[k
]);
897 fprintf (dump_file
, "%d", cycle
[k
]);
899 ": (" HOST_WIDEST_INT_PRINT_DEC
", " HOST_WIDEST_INT_PRINT_DEC
900 ")\n", sum_cost
, cycle_flow
);
902 "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC
"\n",
906 for (k
= cycle_start
; k
< cycle_end
; k
++)
908 pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
+ 1], cycle
[k
]);
909 r_pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
], cycle
[k
+ 1]);
910 pfedge
->rflow
-= cycle_flow
;
912 pfedge
->flow
+= cycle_flow
;
913 r_pfedge
->rflow
+= cycle_flow
;
915 r_pfedge
->flow
-= cycle_flow
;
922 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
923 the edges. ENTRY and EXIT vertices should not be considered. */
926 compute_residual_flow (fixup_graph_type
*fixup_graph
)
930 fixup_edge_p fedge_list
, pfedge
;
932 gcc_assert (fixup_graph
);
935 fputs ("\ncompute_residual_flow():\n", dump_file
);
937 fnum_edges
= fixup_graph
->num_edges
;
938 fedge_list
= fixup_graph
->edge_list
;
940 for (i
= 0; i
< fnum_edges
; i
++)
942 pfedge
= fedge_list
+ i
;
943 pfedge
->rflow
= pfedge
->max_capacity
- pfedge
->flow
;
944 pfedge
->is_rflow_valid
= true;
945 add_rfixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
, pfedge
->flow
,
951 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
952 SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
953 this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
954 to reflect the path found.
955 Returns: 0 if no augmenting path is found, 1 otherwise. */
958 find_augmenting_path (fixup_graph_type
*fixup_graph
,
959 augmenting_path_type
*augmenting_path
, int source
,
964 fixup_vertex_p fvertex_list
, pfvertex
;
966 int *bb_pred
, *is_visited
;
967 queue_type
*queue_list
;
969 gcc_assert (augmenting_path
);
970 bb_pred
= augmenting_path
->bb_pred
;
971 gcc_assert (bb_pred
);
972 is_visited
= augmenting_path
->is_visited
;
973 gcc_assert (is_visited
);
974 queue_list
= &(augmenting_path
->queue_list
);
976 gcc_assert (fixup_graph
);
978 fvertex_list
= fixup_graph
->vertex_list
;
980 for (u
= 0; u
< fixup_graph
->num_vertices
; u
++)
983 init_queue (queue_list
);
984 enqueue (queue_list
, source
);
985 bb_pred
[source
] = -1;
987 while (!is_empty (queue_list
))
989 u
= dequeue (queue_list
);
991 pfvertex
= fvertex_list
+ u
;
992 for (i
= 0; VEC_iterate (fixup_edge_p
, pfvertex
->succ_edges
, i
, pfedge
);
995 int dest
= pfedge
->dest
;
996 if ((pfedge
->rflow
> 0) && (is_visited
[dest
] == 0))
998 enqueue (queue_list
, dest
);
1000 is_visited
[dest
] = 1;
1011 /* Routine to find the maximal flow:
1013 1. Initialize flow to 0
1014 2. Find an augmenting path form source to sink.
1015 3. Send flow equal to the path's residual capacity along the edges of this path.
1016 4. Repeat steps 2 and 3 until no new augmenting path is found.
1019 SOURCE: index of source vertex (input)
1020 SINK: index of sink vertex (input)
1021 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1022 set to have a valid maximal flow by this routine. (input)
1023 Return: Maximum flow possible. */
1026 find_max_flow (fixup_graph_type
*fixup_graph
, int source
, int sink
)
1029 augmenting_path_type augmenting_path
;
1031 gcov_type max_flow
= 0;
1033 fixup_edge_p fedge_list
, pfedge
, r_pfedge
;
1035 gcc_assert (fixup_graph
);
1037 fnum_edges
= fixup_graph
->num_edges
;
1038 fedge_list
= fixup_graph
->edge_list
;
1040 /* Initialize flow to 0. */
1041 for (i
= 0; i
< fnum_edges
; i
++)
1043 pfedge
= fedge_list
+ i
;
1047 compute_residual_flow (fixup_graph
);
1049 init_augmenting_path (&augmenting_path
, fixup_graph
->num_vertices
);
1051 bb_pred
= augmenting_path
.bb_pred
;
1052 while (find_augmenting_path (fixup_graph
, &augmenting_path
, source
, sink
))
1054 /* Determine the amount by which we can increment the flow. */
1055 gcov_type increment
= CAP_INFINITY
;
1056 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1058 pfedge
= find_fixup_edge (fixup_graph
, bb_pred
[u
], u
);
1059 increment
= MIN (increment
, pfedge
->rflow
);
1061 max_flow
+= increment
;
1063 /* Now increment the flow. EXIT vertex index is 1. */
1064 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1066 pfedge
= find_fixup_edge (fixup_graph
, bb_pred
[u
], u
);
1067 r_pfedge
= find_fixup_edge (fixup_graph
, u
, bb_pred
[u
]);
1071 pfedge
->flow
+= increment
;
1072 pfedge
->rflow
-= increment
;
1073 r_pfedge
->rflow
+= increment
;
1077 /* backward edge. */
1078 gcc_assert (r_pfedge
->type
);
1079 r_pfedge
->rflow
+= increment
;
1080 r_pfedge
->flow
-= increment
;
1081 pfedge
->rflow
-= increment
;
1087 fprintf (dump_file
, "\nDump augmenting path:\n");
1088 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1090 print_basic_block (dump_file
, fixup_graph
, u
);
1091 fprintf (dump_file
, "<-");
1094 "ENTRY (path_capacity=" HOST_WIDEST_INT_PRINT_DEC
")\n",
1097 "Network flow is " HOST_WIDEST_INT_PRINT_DEC
".\n",
1102 free_augmenting_path (&augmenting_path
);
1104 dump_fixup_graph (dump_file
, fixup_graph
, "After find_max_flow()");
1109 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1110 after applying the find_minimum_cost_flow() routine. */
1113 adjust_cfg_counts (fixup_graph_type
*fixup_graph
)
1119 fixup_edge_p pfedge
, pfedge_n
;
1121 gcc_assert (fixup_graph
);
1124 fprintf (dump_file
, "\nadjust_cfg_counts():\n");
1126 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1133 "BB%d: " HOST_WIDEST_INT_PRINT_DEC
"", bb
->index
, bb
->count
);
1135 pfedge
= find_fixup_edge (fixup_graph
, i
, i
+ 1);
1138 bb
->count
+= pfedge
->flow
;
1141 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1143 print_edge (dump_file
, fixup_graph
, i
, i
+ 1);
1144 fprintf (dump_file
, ")");
1149 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1150 /* Deduct flow from normalized reverse edge. */
1151 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1153 bb
->count
-= pfedge_n
->flow
;
1156 fprintf (dump_file
, " - " HOST_WIDEST_INT_PRINT_DEC
"(",
1158 print_edge (dump_file
, fixup_graph
, i
+ 1,
1159 pfedge
->norm_vertex_index
);
1160 fprintf (dump_file
, ")");
1164 fprintf (dump_file
, " = " HOST_WIDEST_INT_PRINT_DEC
"\n", bb
->count
);
1167 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1169 /* Treat edges with ignore attribute set as if they don't exist. */
1170 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1173 j
= 2 * e
->dest
->index
;
1175 fprintf (dump_file
, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC
"",
1176 bb
->index
, e
->dest
->index
, e
->count
);
1178 pfedge
= find_fixup_edge (fixup_graph
, i
+ 1, j
);
1180 if (bb
->index
!= e
->dest
->index
)
1182 /* Non-self edge. */
1185 e
->count
+= pfedge
->flow
;
1188 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1190 print_edge (dump_file
, fixup_graph
, i
+ 1, j
);
1191 fprintf (dump_file
, ")");
1196 find_fixup_edge (fixup_graph
, j
, pfedge
->norm_vertex_index
);
1197 /* Deduct flow from normalized reverse edge. */
1198 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1200 e
->count
-= pfedge_n
->flow
;
1203 fprintf (dump_file
, " - " HOST_WIDEST_INT_PRINT_DEC
"(",
1205 print_edge (dump_file
, fixup_graph
, j
,
1206 pfedge
->norm_vertex_index
);
1207 fprintf (dump_file
, ")");
1213 /* Handle self edges. Self edge is split with a normalization
1214 vertex. Here i=j. */
1215 pfedge
= find_fixup_edge (fixup_graph
, j
, i
+ 1);
1217 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1218 e
->count
+= pfedge_n
->flow
;
1219 bb
->count
+= pfedge_n
->flow
;
1222 fprintf (dump_file
, "(self edge)");
1223 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1225 print_edge (dump_file
, fixup_graph
, i
+ 1,
1226 pfedge
->norm_vertex_index
);
1227 fprintf (dump_file
, ")");
1232 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1234 fprintf (dump_file
, " = " HOST_WIDEST_INT_PRINT_DEC
"\t(%.1f%%)\n",
1235 e
->count
, e
->probability
* 100.0 / REG_BR_PROB_BASE
);
1239 ENTRY_BLOCK_PTR
->count
= sum_edge_counts (ENTRY_BLOCK_PTR
->succs
);
1240 EXIT_BLOCK_PTR
->count
= sum_edge_counts (EXIT_BLOCK_PTR
->preds
);
1242 /* Compute edge probabilities. */
1247 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1248 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1253 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1254 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1258 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1260 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1261 e
->probability
= REG_BR_PROB_BASE
/ total
;
1268 total
+= EDGE_COUNT (bb
->succs
);
1269 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1270 e
->probability
= REG_BR_PROB_BASE
/ total
;
1277 fprintf (dump_file
, "\nCheck %s() CFG flow conservation:\n",
1278 current_function_name ());
1281 if ((bb
->count
!= sum_edge_counts (bb
->preds
))
1282 || (bb
->count
!= sum_edge_counts (bb
->succs
)))
1285 "BB%d(" HOST_WIDEST_INT_PRINT_DEC
") **INVALID**: ",
1286 bb
->index
, bb
->count
);
1288 "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC
1289 ") **INVALID**: \n", bb
->index
, bb
->count
);
1290 fprintf (dump_file
, "in_edges=" HOST_WIDEST_INT_PRINT_DEC
" ",
1291 sum_edge_counts (bb
->preds
));
1292 fprintf (dump_file
, "out_edges=" HOST_WIDEST_INT_PRINT_DEC
"\n",
1293 sum_edge_counts (bb
->succs
));
1300 /* Implements the negative cycle canceling algorithm to compute a minimum cost
1303 1. Find maximal flow.
1304 2. Form residual network
1306 While G contains a negative cost cycle C, reverse the flow on the found cycle
1307 by the minimum residual capacity in that cycle.
1308 4. Form the minimal cost flow
1311 FIXUP_GRAPH - Initial fixup graph.
1312 The flow field is modified to represent the minimum cost flow. */
1315 find_minimum_cost_flow (fixup_graph_type
*fixup_graph
)
1317 /* Holds the index of predecessor in path. */
1319 /* Used to hold the minimum cost cycle. */
1321 /* Used to record the number of iterations of cancel_negative_cycle. */
1323 /* Vector d[i] holds the minimum cost of path from i to sink. */
1327 int new_entry_index
;
1329 gcc_assert (fixup_graph
);
1330 fnum_vertices
= fixup_graph
->num_vertices
;
1331 new_exit_index
= fixup_graph
->new_exit_index
;
1332 new_entry_index
= fixup_graph
->new_entry_index
;
1334 find_max_flow (fixup_graph
, new_entry_index
, new_exit_index
);
1336 /* Initialize the structures for find_negative_cycle(). */
1337 pred
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1338 d
= (gcov_type
*) xcalloc (fnum_vertices
, sizeof (gcov_type
));
1339 cycle
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1341 /* Repeatedly find and cancel negative cost cycles, until
1342 no more negative cycles exist. This also updates the flow field
1343 to represent the minimum cost flow so far. */
1345 while (cancel_negative_cycle (fixup_graph
, pred
, d
, cycle
))
1348 if (iteration
> MAX_ITER (fixup_graph
->num_vertices
,
1349 fixup_graph
->num_edges
))
1354 dump_fixup_graph (dump_file
, fixup_graph
,
1355 "After find_minimum_cost_flow()");
1357 /* Cleanup structures. */
1364 /* Compute the sum of the edge counts in TO_EDGES. */
1367 sum_edge_counts (VEC (edge
, gc
) *to_edges
)
1373 FOR_EACH_EDGE (e
, ei
, to_edges
)
1375 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1383 /* Main routine. Smoothes the initial assigned basic block and edge counts using
1384 a minimum cost flow algorithm, to ensure that the flow consistency rule is
1385 obeyed: sum of outgoing edges = sum of incoming edges for each basic
1389 mcf_smooth_cfg (void)
1391 fixup_graph_type fixup_graph
;
1392 memset (&fixup_graph
, 0, sizeof (fixup_graph
));
1393 create_fixup_graph (&fixup_graph
);
1394 find_minimum_cost_flow (&fixup_graph
);
1395 adjust_cfg_counts (&fixup_graph
);
1396 delete_fixup_graph (&fixup_graph
);