1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth
2 basic block and edge frequency counts.
3 Copyright (C) 2008-2015 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"
53 #include "hard-reg-set.h"
56 #include "dominance.h"
58 #include "basic-block.h"
63 /* CAP_INFINITY: Constant to represent infinite capacity. */
64 #define CAP_INFINITY INTTYPE_MAXIMUM (int64_t)
67 #define K_POS(b) ((b))
68 #define K_NEG(b) (50 * (b))
69 #define COST(k, w) ((k) / mcf_ln ((w) + 2))
70 /* Limit the number of iterations for cancel_negative_cycles() to ensure
71 reasonable compile time. */
72 #define MAX_ITER(n, e) 10 + (1000000 / ((n) * (e)))
76 VERTEX_SPLIT_EDGE
, /* Edge to represent vertex with w(e) = w(v). */
77 REDIRECT_EDGE
, /* Edge after vertex transformation. */
79 SOURCE_CONNECT_EDGE
, /* Single edge connecting to single source. */
80 SINK_CONNECT_EDGE
, /* Single edge connecting to single sink. */
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
;
108 /* Structure to represent a vertex in the fixup graph. */
109 typedef struct fixup_vertex_d
111 vec
<fixup_edge_p
> succ_edges
;
114 typedef fixup_vertex_type
*fixup_vertex_p
;
116 /* Fixup graph used in the MCF algorithm. */
117 typedef struct fixup_graph_d
119 /* Current number of vertices for the graph. */
121 /* Current number of edges for the graph. */
123 /* Index of new entry vertex. */
125 /* Index of new exit vertex. */
127 /* Fixup vertex list. Adjacency list for fixup graph. */
128 fixup_vertex_p vertex_list
;
129 /* Fixup edge list. */
130 fixup_edge_p edge_list
;
133 typedef struct queue_d
141 /* Structure used in the maximal flow routines to find augmenting path. */
142 typedef struct augmenting_path_d
144 /* Queue used to hold vertex indices. */
145 queue_type queue_list
;
146 /* Vector to hold chain of pred vertex indices in augmenting path. */
148 /* Vector that indicates if basic block i has been visited. */
150 } augmenting_path_type
;
153 /* Function definitions. */
155 /* Dump routines to aid debugging. */
157 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */
160 print_basic_block (FILE *file
, fixup_graph_type
*fixup_graph
, int n
)
162 if (n
== ENTRY_BLOCK
)
163 fputs ("ENTRY", file
);
164 else if (n
== ENTRY_BLOCK
+ 1)
165 fputs ("ENTRY''", file
);
166 else if (n
== 2 * EXIT_BLOCK
)
167 fputs ("EXIT", file
);
168 else if (n
== 2 * EXIT_BLOCK
+ 1)
169 fputs ("EXIT''", file
);
170 else if (n
== fixup_graph
->new_exit_index
)
171 fputs ("NEW_EXIT", file
);
172 else if (n
== fixup_graph
->new_entry_index
)
173 fputs ("NEW_ENTRY", file
);
176 fprintf (file
, "%d", n
/ 2);
185 /* Print edge S->D for given fixup_graph with n' and n'' format.
187 S is the index of the source vertex of the edge (input) and
188 D is the index of the destination vertex of the edge (input) for the given
189 fixup_graph (input). */
192 print_edge (FILE *file
, fixup_graph_type
*fixup_graph
, int s
, int d
)
194 print_basic_block (file
, fixup_graph
, s
);
196 print_basic_block (file
, fixup_graph
, d
);
200 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
203 dump_fixup_edge (FILE *file
, fixup_graph_type
*fixup_graph
, fixup_edge_p fedge
)
207 fputs ("NULL fixup graph edge.\n", file
);
211 print_edge (file
, fixup_graph
, fedge
->src
, fedge
->dest
);
216 fprintf (file
, "flow/capacity=%" PRId64
"/",
218 if (fedge
->max_capacity
== CAP_INFINITY
)
219 fputs ("+oo,", file
);
221 fprintf (file
, "%" PRId64
",", fedge
->max_capacity
);
224 if (fedge
->is_rflow_valid
)
226 if (fedge
->rflow
== CAP_INFINITY
)
227 fputs (" rflow=+oo.", file
);
229 fprintf (file
, " rflow=%" PRId64
",", fedge
->rflow
);
232 fprintf (file
, " cost=%" PRId64
".", fedge
->cost
);
234 fprintf (file
, "\t(%d->%d)", fedge
->src
, fedge
->dest
);
240 case VERTEX_SPLIT_EDGE
:
241 fputs (" @VERTEX_SPLIT_EDGE", file
);
245 fputs (" @REDIRECT_EDGE", file
);
248 case SOURCE_CONNECT_EDGE
:
249 fputs (" @SOURCE_CONNECT_EDGE", file
);
252 case SINK_CONNECT_EDGE
:
253 fputs (" @SINK_CONNECT_EDGE", file
);
257 fputs (" @REVERSE_EDGE", file
);
261 fputs (" @BALANCE_EDGE", file
);
264 case REDIRECT_NORMALIZED_EDGE
:
265 case REVERSE_NORMALIZED_EDGE
:
266 fputs (" @NORMALIZED_EDGE", file
);
270 fputs (" @INVALID_EDGE", file
);
278 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
279 file. The input string MSG is printed out as a heading. */
282 dump_fixup_graph (FILE *file
, fixup_graph_type
*fixup_graph
, const char *msg
)
285 int fnum_vertices
, fnum_edges
;
287 fixup_vertex_p fvertex_list
, pfvertex
;
290 gcc_assert (fixup_graph
);
291 fvertex_list
= fixup_graph
->vertex_list
;
292 fnum_vertices
= fixup_graph
->num_vertices
;
293 fnum_edges
= fixup_graph
->num_edges
;
295 fprintf (file
, "\nDump fixup graph for %s(): %s.\n",
296 current_function_name (), msg
);
298 "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
299 fnum_vertices
, fnum_edges
, fixup_graph
->new_exit_index
);
301 for (i
= 0; i
< fnum_vertices
; i
++)
303 pfvertex
= fvertex_list
+ i
;
304 fprintf (file
, "vertex_list[%d]: %d succ fixup edges.\n",
305 i
, pfvertex
->succ_edges
.length ());
307 for (j
= 0; pfvertex
->succ_edges
.iterate (j
, &pfedge
);
310 /* Distinguish forward edges and backward edges in the residual flow
313 fputs ("(f) ", file
);
314 else if (pfedge
->is_rflow_valid
)
315 fputs ("(b) ", file
);
316 dump_fixup_edge (file
, fixup_graph
, pfedge
);
324 /* Utility routines. */
325 /* ln() implementation: approximate calculation. Returns ln of X. */
346 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
347 implementation) by John Carmack. Returns sqrt of X. */
352 #define MAGIC_CONST1 0x1fbcf800
353 #define MAGIC_CONST2 0x5f3759df
357 } convertor
, convertor2
;
361 convertor
.floatPart
= x
;
362 convertor2
.floatPart
= x
;
363 convertor
.intPart
= MAGIC_CONST1
+ (convertor
.intPart
>> 1);
364 convertor2
.intPart
= MAGIC_CONST2
- (convertor2
.intPart
>> 1);
366 return 0.5f
* (convertor
.floatPart
+ (x
* convertor2
.floatPart
));
370 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
371 (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
372 added set to COST. */
375 add_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
, gcov_type cost
)
377 fixup_vertex_p curr_vertex
= fixup_graph
->vertex_list
+ src
;
378 fixup_edge_p curr_edge
= fixup_graph
->edge_list
+ fixup_graph
->num_edges
;
379 curr_edge
->src
= src
;
380 curr_edge
->dest
= dest
;
381 curr_edge
->cost
= cost
;
382 fixup_graph
->num_edges
++;
384 dump_fixup_edge (dump_file
, fixup_graph
, curr_edge
);
385 curr_vertex
->succ_edges
.safe_push (curr_edge
);
390 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
391 MAX_CAPACITY to the edge_list in the fixup graph. */
394 add_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
395 edge_type type
, gcov_type weight
, gcov_type cost
,
396 gcov_type max_capacity
)
398 fixup_edge_p curr_edge
= add_edge (fixup_graph
, src
, dest
, cost
);
399 curr_edge
->type
= type
;
400 curr_edge
->weight
= weight
;
401 curr_edge
->max_capacity
= max_capacity
;
405 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
406 to the fixup graph. */
409 add_rfixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
410 gcov_type rflow
, gcov_type cost
)
412 fixup_edge_p curr_edge
= add_edge (fixup_graph
, src
, dest
, cost
);
413 curr_edge
->rflow
= rflow
;
414 curr_edge
->is_rflow_valid
= true;
415 /* This edge is not a valid edge - merely used to hold residual flow. */
416 curr_edge
->type
= INVALID_EDGE
;
420 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
421 exist in the FIXUP_GRAPH. */
424 find_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
)
428 fixup_vertex_p pfvertex
;
430 gcc_assert (src
< fixup_graph
->num_vertices
);
432 pfvertex
= fixup_graph
->vertex_list
+ src
;
434 for (j
= 0; pfvertex
->succ_edges
.iterate (j
, &pfedge
);
436 if (pfedge
->dest
== dest
)
443 /* Cleanup routine to free structures in FIXUP_GRAPH. */
446 delete_fixup_graph (fixup_graph_type
*fixup_graph
)
449 int fnum_vertices
= fixup_graph
->num_vertices
;
450 fixup_vertex_p pfvertex
= fixup_graph
->vertex_list
;
452 for (i
= 0; i
< fnum_vertices
; i
++, pfvertex
++)
453 pfvertex
->succ_edges
.release ();
455 free (fixup_graph
->vertex_list
);
456 free (fixup_graph
->edge_list
);
460 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
463 create_fixup_graph (fixup_graph_type
*fixup_graph
)
465 double sqrt_avg_vertex_weight
= 0;
466 double total_vertex_weight
= 0;
469 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */
470 gcov_type
*diff_out_in
= NULL
;
471 gcov_type supply_value
= 1, demand_value
= 0;
473 int new_entry_index
= 0, new_exit_index
= 0;
479 fixup_edge_p pfedge
, r_pfedge
;
480 fixup_edge_p fedge_list
;
483 /* Each basic_block will be split into 2 during vertex transformation. */
484 int fnum_vertices_after_transform
= 2 * n_basic_blocks_for_fn (cfun
);
485 int fnum_edges_after_transform
=
486 n_edges_for_fn (cfun
) + n_basic_blocks_for_fn (cfun
);
488 /* Count the new SOURCE and EXIT vertices to be added. */
489 int fmax_num_vertices
=
490 (fnum_vertices_after_transform
+ n_edges_for_fn (cfun
)
491 + n_basic_blocks_for_fn (cfun
) + 2);
493 /* In create_fixup_graph: Each basic block and edge can be split into 3
494 edges. Number of balance edges = n_basic_blocks. So after
496 max_edges = 4 * n_basic_blocks + 3 * n_edges
497 Accounting for residual flow edges
498 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
499 = 8 * n_basic_blocks + 6 * n_edges
500 < 8 * n_basic_blocks + 8 * n_edges. */
501 int fmax_num_edges
= 8 * (n_basic_blocks_for_fn (cfun
) +
502 n_edges_for_fn (cfun
));
504 /* Initial num of vertices in the fixup graph. */
505 fixup_graph
->num_vertices
= n_basic_blocks_for_fn (cfun
);
507 /* Fixup graph vertex list. */
508 fixup_graph
->vertex_list
=
509 (fixup_vertex_p
) xcalloc (fmax_num_vertices
, sizeof (fixup_vertex_type
));
511 /* Fixup graph edge list. */
512 fixup_graph
->edge_list
=
513 (fixup_edge_p
) xcalloc (fmax_num_edges
, sizeof (fixup_edge_type
));
516 (gcov_type
*) xcalloc (1 + fnum_vertices_after_transform
,
519 /* Compute constants b, k_pos, k_neg used in the cost function calculation.
520 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */
521 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
522 total_vertex_weight
+= bb
->count
;
524 sqrt_avg_vertex_weight
= mcf_sqrt (total_vertex_weight
/
525 n_basic_blocks_for_fn (cfun
));
527 k_pos
= K_POS (sqrt_avg_vertex_weight
);
528 k_neg
= K_NEG (sqrt_avg_vertex_weight
);
530 /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
531 connected by an edge e from v' to v''. w(e) = w(v). */
534 fprintf (dump_file
, "\nVertex transformation:\n");
536 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
538 /* v'->v'': index1->(index1+1). */
540 fcost
= (gcov_type
) COST (k_pos
, bb
->count
);
541 add_fixup_edge (fixup_graph
, i
, i
+ 1, VERTEX_SPLIT_EDGE
, bb
->count
,
542 fcost
, CAP_INFINITY
);
543 fixup_graph
->num_vertices
++;
545 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
547 /* Edges with ignore attribute set should be treated like they don't
549 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
551 j
= 2 * e
->dest
->index
;
552 fcost
= (gcov_type
) COST (k_pos
, e
->count
);
553 add_fixup_edge (fixup_graph
, i
+ 1, j
, REDIRECT_EDGE
, e
->count
, fcost
,
558 /* After vertex transformation. */
559 gcc_assert (fixup_graph
->num_vertices
== fnum_vertices_after_transform
);
560 /* Redirect edges are not added for edges with ignore attribute. */
561 gcc_assert (fixup_graph
->num_edges
<= fnum_edges_after_transform
);
563 fnum_edges_after_transform
= fixup_graph
->num_edges
;
565 /* 2. Initialize D(v). */
566 for (i
= 0; i
< fnum_edges_after_transform
; i
++)
568 pfedge
= fixup_graph
->edge_list
+ i
;
569 diff_out_in
[pfedge
->src
] += pfedge
->weight
;
570 diff_out_in
[pfedge
->dest
] -= pfedge
->weight
;
573 /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */
574 for (i
= 0; i
<= 3; i
++)
577 /* 3. Add reverse edges: needed to decrease counts during smoothing. */
579 fprintf (dump_file
, "\nReverse edges:\n");
580 for (i
= 0; i
< fnum_edges_after_transform
; i
++)
582 pfedge
= fixup_graph
->edge_list
+ i
;
583 if ((pfedge
->src
== 0) || (pfedge
->src
== 2))
585 r_pfedge
= find_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
);
586 if (!r_pfedge
&& pfedge
->weight
)
588 /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
590 fcost
= (gcov_type
) COST (k_neg
, pfedge
->weight
);
591 add_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
,
592 REVERSE_EDGE
, 0, fcost
, pfedge
->weight
);
596 /* 4. Create single source and sink. Connect new source vertex s' to function
597 entry block. Connect sink vertex t' to function exit. */
599 fprintf (dump_file
, "\ns'->S, T->t':\n");
601 new_entry_index
= fixup_graph
->new_entry_index
= fixup_graph
->num_vertices
;
602 fixup_graph
->num_vertices
++;
603 /* Set supply_value to 1 to avoid zero count function ENTRY. */
604 add_fixup_edge (fixup_graph
, new_entry_index
, ENTRY_BLOCK
, SOURCE_CONNECT_EDGE
,
605 1 /* supply_value */, 0, 1 /* supply_value */);
607 /* Create new exit with EXIT_BLOCK as single pred. */
608 new_exit_index
= fixup_graph
->new_exit_index
= fixup_graph
->num_vertices
;
609 fixup_graph
->num_vertices
++;
610 add_fixup_edge (fixup_graph
, 2 * EXIT_BLOCK
+ 1, new_exit_index
,
612 0 /* demand_value */, 0, 0 /* demand_value */);
614 /* Connect vertices with unbalanced D(v) to source/sink. */
616 fprintf (dump_file
, "\nD(v) balance:\n");
617 /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
618 diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2. */
619 for (i
= 4; i
< new_entry_index
; i
+= 2)
621 if (diff_out_in
[i
] > 0)
623 add_fixup_edge (fixup_graph
, i
, new_exit_index
, BALANCE_EDGE
, 0, 0,
625 demand_value
+= diff_out_in
[i
];
627 else if (diff_out_in
[i
] < 0)
629 add_fixup_edge (fixup_graph
, new_entry_index
, i
, BALANCE_EDGE
, 0, 0,
631 supply_value
-= diff_out_in
[i
];
635 /* Set supply = demand. */
638 fprintf (dump_file
, "\nAdjust supply and demand:\n");
639 fprintf (dump_file
, "supply_value=%" PRId64
"\n",
641 fprintf (dump_file
, "demand_value=%" PRId64
"\n",
645 if (demand_value
> supply_value
)
647 pfedge
= find_fixup_edge (fixup_graph
, new_entry_index
, ENTRY_BLOCK
);
648 pfedge
->max_capacity
+= (demand_value
- supply_value
);
652 pfedge
= find_fixup_edge (fixup_graph
, 2 * EXIT_BLOCK
+ 1, new_exit_index
);
653 pfedge
->max_capacity
+= (supply_value
- demand_value
);
656 /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
657 created by the vertex transformation step from self-edges in the original
658 CFG and by the reverse edges added earlier. */
660 fprintf (dump_file
, "\nNormalize edges:\n");
662 fnum_edges
= fixup_graph
->num_edges
;
663 fedge_list
= fixup_graph
->edge_list
;
665 for (i
= 0; i
< fnum_edges
; i
++)
667 pfedge
= fedge_list
+ i
;
668 r_pfedge
= find_fixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
);
669 if (((pfedge
->type
== VERTEX_SPLIT_EDGE
)
670 || (pfedge
->type
== REDIRECT_EDGE
)) && r_pfedge
)
672 new_index
= fixup_graph
->num_vertices
;
673 fixup_graph
->num_vertices
++;
677 fprintf (dump_file
, "\nAnti-parallel edge:\n");
678 dump_fixup_edge (dump_file
, fixup_graph
, pfedge
);
679 dump_fixup_edge (dump_file
, fixup_graph
, r_pfedge
);
680 fprintf (dump_file
, "New vertex is %d.\n", new_index
);
681 fprintf (dump_file
, "------------------\n");
685 pfedge
->norm_vertex_index
= new_index
;
688 fprintf (dump_file
, "After normalization:\n");
689 dump_fixup_edge (dump_file
, fixup_graph
, pfedge
);
692 /* Add a new fixup edge: new_index->src. */
693 add_fixup_edge (fixup_graph
, new_index
, pfedge
->src
,
694 REVERSE_NORMALIZED_EDGE
, 0, r_pfedge
->cost
,
695 r_pfedge
->max_capacity
);
696 gcc_assert (fixup_graph
->num_vertices
<= fmax_num_vertices
);
698 /* Edge: r_pfedge->src -> r_pfedge->dest
699 ==> r_pfedge->src -> new_index. */
700 r_pfedge
->dest
= new_index
;
701 r_pfedge
->type
= REVERSE_NORMALIZED_EDGE
;
702 r_pfedge
->cost
= pfedge
->cost
;
703 r_pfedge
->max_capacity
= pfedge
->max_capacity
;
705 dump_fixup_edge (dump_file
, fixup_graph
, r_pfedge
);
710 dump_fixup_graph (dump_file
, fixup_graph
, "After create_fixup_graph()");
717 /* Allocates space for the structures in AUGMENTING_PATH. The space needed is
718 proportional to the number of nodes in the graph, which is given by
722 init_augmenting_path (augmenting_path_type
*augmenting_path
, int graph_size
)
724 augmenting_path
->queue_list
.queue
= (int *)
725 xcalloc (graph_size
+ 2, sizeof (int));
726 augmenting_path
->queue_list
.size
= graph_size
+ 2;
727 augmenting_path
->bb_pred
= (int *) xcalloc (graph_size
, sizeof (int));
728 augmenting_path
->is_visited
= (int *) xcalloc (graph_size
, sizeof (int));
731 /* Free the structures in AUGMENTING_PATH. */
733 free_augmenting_path (augmenting_path_type
*augmenting_path
)
735 free (augmenting_path
->queue_list
.queue
);
736 free (augmenting_path
->bb_pred
);
737 free (augmenting_path
->is_visited
);
741 /* Queue routines. Assumes queue will never overflow. */
744 init_queue (queue_type
*queue_list
)
746 gcc_assert (queue_list
);
747 queue_list
->head
= 0;
748 queue_list
->tail
= 0;
751 /* Return true if QUEUE_LIST is empty. */
753 is_empty (queue_type
*queue_list
)
755 return (queue_list
->head
== queue_list
->tail
);
758 /* Insert element X into QUEUE_LIST. */
760 enqueue (queue_type
*queue_list
, int x
)
762 gcc_assert (queue_list
->tail
< queue_list
->size
);
763 queue_list
->queue
[queue_list
->tail
] = x
;
764 (queue_list
->tail
)++;
767 /* Return the first element in QUEUE_LIST. */
769 dequeue (queue_type
*queue_list
)
772 gcc_assert (queue_list
->head
>= 0);
773 x
= queue_list
->queue
[queue_list
->head
];
774 (queue_list
->head
)++;
779 /* Finds a negative cycle in the residual network using
780 the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
781 minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
785 FIXUP_GRAPH - Residual graph (input/output)
786 The following are allocated/freed by the caller:
787 PI - Vector to hold predecessors in path (pi = pred index)
788 D - D[I] holds minimum cost of path from i to sink
789 CYCLE - Vector to hold the minimum cost cycle
792 true if a negative cycle was found, false otherwise. */
795 cancel_negative_cycle (fixup_graph_type
*fixup_graph
,
796 int *pi
, gcov_type
*d
, int *cycle
)
799 int fnum_vertices
, fnum_edges
;
800 fixup_edge_p fedge_list
, pfedge
, r_pfedge
;
801 bool found_cycle
= false;
802 int cycle_start
= 0, cycle_end
= 0;
803 gcov_type sum_cost
= 0, cycle_flow
= 0;
805 bool propagated
= false;
807 gcc_assert (fixup_graph
);
808 fnum_vertices
= fixup_graph
->num_vertices
;
809 fnum_edges
= fixup_graph
->num_edges
;
810 fedge_list
= fixup_graph
->edge_list
;
811 new_entry_index
= fixup_graph
->new_entry_index
;
815 for (i
= 1; i
< fnum_vertices
; i
++)
824 for (k
= 1; k
< fnum_vertices
; k
++)
827 for (i
= 0; i
< fnum_edges
; i
++)
829 pfedge
= fedge_list
+ i
;
830 if (pfedge
->src
== new_entry_index
)
832 if (pfedge
->is_rflow_valid
&& pfedge
->rflow
833 && d
[pfedge
->src
] != CAP_INFINITY
834 && (d
[pfedge
->dest
] > d
[pfedge
->src
] + pfedge
->cost
))
836 d
[pfedge
->dest
] = d
[pfedge
->src
] + pfedge
->cost
;
837 pi
[pfedge
->dest
] = pfedge
->src
;
846 /* No negative cycles exist. */
850 for (i
= 0; i
< fnum_edges
; i
++)
852 pfedge
= fedge_list
+ i
;
853 if (pfedge
->src
== new_entry_index
)
855 if (pfedge
->is_rflow_valid
&& pfedge
->rflow
856 && d
[pfedge
->src
] != CAP_INFINITY
857 && (d
[pfedge
->dest
] > d
[pfedge
->src
] + pfedge
->cost
))
867 /* Augment the cycle with the cycle's minimum residual capacity. */
869 cycle
[0] = pfedge
->dest
;
872 for (i
= 1; i
< fnum_vertices
; i
++)
876 for (k
= 0; k
< i
; k
++)
880 /* cycle[k] -> ... -> cycle[i]. */
891 gcc_assert (cycle
[cycle_start
] == cycle
[cycle_end
]);
893 fprintf (dump_file
, "\nNegative cycle length is %d:\n",
894 cycle_end
- cycle_start
);
897 cycle_flow
= CAP_INFINITY
;
898 for (k
= cycle_start
; k
< cycle_end
; k
++)
900 pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
+ 1], cycle
[k
]);
901 cycle_flow
= MIN (cycle_flow
, pfedge
->rflow
);
902 sum_cost
+= pfedge
->cost
;
904 fprintf (dump_file
, "%d ", cycle
[k
]);
909 fprintf (dump_file
, "%d", cycle
[k
]);
911 ": (%" PRId64
", %" PRId64
912 ")\n", sum_cost
, cycle_flow
);
914 "Augment cycle with %" PRId64
"\n",
918 for (k
= cycle_start
; k
< cycle_end
; k
++)
920 pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
+ 1], cycle
[k
]);
921 r_pfedge
= find_fixup_edge (fixup_graph
, cycle
[k
], cycle
[k
+ 1]);
922 pfedge
->rflow
-= cycle_flow
;
924 pfedge
->flow
+= cycle_flow
;
925 r_pfedge
->rflow
+= cycle_flow
;
927 r_pfedge
->flow
-= cycle_flow
;
934 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
935 the edges. ENTRY and EXIT vertices should not be considered. */
938 compute_residual_flow (fixup_graph_type
*fixup_graph
)
942 fixup_edge_p fedge_list
, pfedge
;
944 gcc_assert (fixup_graph
);
947 fputs ("\ncompute_residual_flow():\n", dump_file
);
949 fnum_edges
= fixup_graph
->num_edges
;
950 fedge_list
= fixup_graph
->edge_list
;
952 for (i
= 0; i
< fnum_edges
; i
++)
954 pfedge
= fedge_list
+ i
;
955 pfedge
->rflow
= pfedge
->max_capacity
- pfedge
->flow
;
956 pfedge
->is_rflow_valid
= true;
957 add_rfixup_edge (fixup_graph
, pfedge
->dest
, pfedge
->src
, pfedge
->flow
,
963 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
964 SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
965 this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
966 to reflect the path found.
967 Returns: 0 if no augmenting path is found, 1 otherwise. */
970 find_augmenting_path (fixup_graph_type
*fixup_graph
,
971 augmenting_path_type
*augmenting_path
, int source
,
976 fixup_vertex_p fvertex_list
, pfvertex
;
978 int *bb_pred
, *is_visited
;
979 queue_type
*queue_list
;
981 gcc_assert (augmenting_path
);
982 bb_pred
= augmenting_path
->bb_pred
;
983 gcc_assert (bb_pred
);
984 is_visited
= augmenting_path
->is_visited
;
985 gcc_assert (is_visited
);
986 queue_list
= &(augmenting_path
->queue_list
);
988 gcc_assert (fixup_graph
);
990 fvertex_list
= fixup_graph
->vertex_list
;
992 for (u
= 0; u
< fixup_graph
->num_vertices
; u
++)
995 init_queue (queue_list
);
996 enqueue (queue_list
, source
);
997 bb_pred
[source
] = -1;
999 while (!is_empty (queue_list
))
1001 u
= dequeue (queue_list
);
1003 pfvertex
= fvertex_list
+ u
;
1004 for (i
= 0; pfvertex
->succ_edges
.iterate (i
, &pfedge
);
1007 int dest
= pfedge
->dest
;
1008 if ((pfedge
->rflow
> 0) && (is_visited
[dest
] == 0))
1010 enqueue (queue_list
, dest
);
1012 is_visited
[dest
] = 1;
1023 /* Routine to find the maximal flow:
1025 1. Initialize flow to 0
1026 2. Find an augmenting path form source to sink.
1027 3. Send flow equal to the path's residual capacity along the edges of this path.
1028 4. Repeat steps 2 and 3 until no new augmenting path is found.
1031 SOURCE: index of source vertex (input)
1032 SINK: index of sink vertex (input)
1033 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
1034 set to have a valid maximal flow by this routine. (input)
1035 Return: Maximum flow possible. */
1038 find_max_flow (fixup_graph_type
*fixup_graph
, int source
, int sink
)
1041 augmenting_path_type augmenting_path
;
1043 gcov_type max_flow
= 0;
1045 fixup_edge_p fedge_list
, pfedge
, r_pfedge
;
1047 gcc_assert (fixup_graph
);
1049 fnum_edges
= fixup_graph
->num_edges
;
1050 fedge_list
= fixup_graph
->edge_list
;
1052 /* Initialize flow to 0. */
1053 for (i
= 0; i
< fnum_edges
; i
++)
1055 pfedge
= fedge_list
+ i
;
1059 compute_residual_flow (fixup_graph
);
1061 init_augmenting_path (&augmenting_path
, fixup_graph
->num_vertices
);
1063 bb_pred
= augmenting_path
.bb_pred
;
1064 while (find_augmenting_path (fixup_graph
, &augmenting_path
, source
, sink
))
1066 /* Determine the amount by which we can increment the flow. */
1067 gcov_type increment
= CAP_INFINITY
;
1068 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1070 pfedge
= find_fixup_edge (fixup_graph
, bb_pred
[u
], u
);
1071 increment
= MIN (increment
, pfedge
->rflow
);
1073 max_flow
+= increment
;
1075 /* Now increment the flow. EXIT vertex index is 1. */
1076 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1078 pfedge
= find_fixup_edge (fixup_graph
, bb_pred
[u
], u
);
1079 r_pfedge
= find_fixup_edge (fixup_graph
, u
, bb_pred
[u
]);
1083 pfedge
->flow
+= increment
;
1084 pfedge
->rflow
-= increment
;
1085 r_pfedge
->rflow
+= increment
;
1089 /* backward edge. */
1090 gcc_assert (r_pfedge
->type
);
1091 r_pfedge
->rflow
+= increment
;
1092 r_pfedge
->flow
-= increment
;
1093 pfedge
->rflow
-= increment
;
1099 fprintf (dump_file
, "\nDump augmenting path:\n");
1100 for (u
= sink
; u
!= source
; u
= bb_pred
[u
])
1102 print_basic_block (dump_file
, fixup_graph
, u
);
1103 fprintf (dump_file
, "<-");
1106 "ENTRY (path_capacity=%" PRId64
")\n",
1109 "Network flow is %" PRId64
".\n",
1114 free_augmenting_path (&augmenting_path
);
1116 dump_fixup_graph (dump_file
, fixup_graph
, "After find_max_flow()");
1121 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH
1122 after applying the find_minimum_cost_flow() routine. */
1125 adjust_cfg_counts (fixup_graph_type
*fixup_graph
)
1131 fixup_edge_p pfedge
, pfedge_n
;
1133 gcc_assert (fixup_graph
);
1136 fprintf (dump_file
, "\nadjust_cfg_counts():\n");
1138 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1139 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1146 "BB%d: %" PRId64
"", bb
->index
, bb
->count
);
1148 pfedge
= find_fixup_edge (fixup_graph
, i
, i
+ 1);
1151 bb
->count
+= pfedge
->flow
;
1154 fprintf (dump_file
, " + %" PRId64
"(",
1156 print_edge (dump_file
, fixup_graph
, i
, i
+ 1);
1157 fprintf (dump_file
, ")");
1162 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1163 /* Deduct flow from normalized reverse edge. */
1164 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1166 bb
->count
-= pfedge_n
->flow
;
1169 fprintf (dump_file
, " - %" PRId64
"(",
1171 print_edge (dump_file
, fixup_graph
, i
+ 1,
1172 pfedge
->norm_vertex_index
);
1173 fprintf (dump_file
, ")");
1177 fprintf (dump_file
, " = %" PRId64
"\n", bb
->count
);
1180 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1182 /* Treat edges with ignore attribute set as if they don't exist. */
1183 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1186 j
= 2 * e
->dest
->index
;
1188 fprintf (dump_file
, "%d->%d: %" PRId64
"",
1189 bb
->index
, e
->dest
->index
, e
->count
);
1191 pfedge
= find_fixup_edge (fixup_graph
, i
+ 1, j
);
1193 if (bb
->index
!= e
->dest
->index
)
1195 /* Non-self edge. */
1198 e
->count
+= pfedge
->flow
;
1201 fprintf (dump_file
, " + %" PRId64
"(",
1203 print_edge (dump_file
, fixup_graph
, i
+ 1, j
);
1204 fprintf (dump_file
, ")");
1209 find_fixup_edge (fixup_graph
, j
, pfedge
->norm_vertex_index
);
1210 /* Deduct flow from normalized reverse edge. */
1211 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1213 e
->count
-= pfedge_n
->flow
;
1216 fprintf (dump_file
, " - %" PRId64
"(",
1218 print_edge (dump_file
, fixup_graph
, j
,
1219 pfedge
->norm_vertex_index
);
1220 fprintf (dump_file
, ")");
1226 /* Handle self edges. Self edge is split with a normalization
1227 vertex. Here i=j. */
1228 pfedge
= find_fixup_edge (fixup_graph
, j
, i
+ 1);
1230 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1231 e
->count
+= pfedge_n
->flow
;
1232 bb
->count
+= pfedge_n
->flow
;
1235 fprintf (dump_file
, "(self edge)");
1236 fprintf (dump_file
, " + %" PRId64
"(",
1238 print_edge (dump_file
, fixup_graph
, i
+ 1,
1239 pfedge
->norm_vertex_index
);
1240 fprintf (dump_file
, ")");
1245 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1247 fprintf (dump_file
, " = %" PRId64
"\t(%.1f%%)\n",
1248 e
->count
, e
->probability
* 100.0 / REG_BR_PROB_BASE
);
1252 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
=
1253 sum_edge_counts (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1254 EXIT_BLOCK_PTR_FOR_FN (cfun
)->count
=
1255 sum_edge_counts (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
1257 /* Compute edge probabilities. */
1258 FOR_ALL_BB_FN (bb
, cfun
)
1262 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1263 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1268 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1269 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1273 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1275 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1276 e
->probability
= REG_BR_PROB_BASE
/ total
;
1283 total
+= EDGE_COUNT (bb
->succs
);
1284 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1285 e
->probability
= REG_BR_PROB_BASE
/ total
;
1292 fprintf (dump_file
, "\nCheck %s() CFG flow conservation:\n",
1293 current_function_name ());
1294 FOR_EACH_BB_FN (bb
, cfun
)
1296 if ((bb
->count
!= sum_edge_counts (bb
->preds
))
1297 || (bb
->count
!= sum_edge_counts (bb
->succs
)))
1300 "BB%d(%" PRId64
") **INVALID**: ",
1301 bb
->index
, bb
->count
);
1303 "******** BB%d(%" PRId64
1304 ") **INVALID**: \n", bb
->index
, bb
->count
);
1305 fprintf (dump_file
, "in_edges=%" PRId64
" ",
1306 sum_edge_counts (bb
->preds
));
1307 fprintf (dump_file
, "out_edges=%" PRId64
"\n",
1308 sum_edge_counts (bb
->succs
));
1315 /* Implements the negative cycle canceling algorithm to compute a minimum cost
1318 1. Find maximal flow.
1319 2. Form residual network
1321 While G contains a negative cost cycle C, reverse the flow on the found cycle
1322 by the minimum residual capacity in that cycle.
1323 4. Form the minimal cost flow
1326 FIXUP_GRAPH - Initial fixup graph.
1327 The flow field is modified to represent the minimum cost flow. */
1330 find_minimum_cost_flow (fixup_graph_type
*fixup_graph
)
1332 /* Holds the index of predecessor in path. */
1334 /* Used to hold the minimum cost cycle. */
1336 /* Used to record the number of iterations of cancel_negative_cycle. */
1338 /* Vector d[i] holds the minimum cost of path from i to sink. */
1342 int new_entry_index
;
1344 gcc_assert (fixup_graph
);
1345 fnum_vertices
= fixup_graph
->num_vertices
;
1346 new_exit_index
= fixup_graph
->new_exit_index
;
1347 new_entry_index
= fixup_graph
->new_entry_index
;
1349 find_max_flow (fixup_graph
, new_entry_index
, new_exit_index
);
1351 /* Initialize the structures for find_negative_cycle(). */
1352 pred
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1353 d
= (gcov_type
*) xcalloc (fnum_vertices
, sizeof (gcov_type
));
1354 cycle
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1356 /* Repeatedly find and cancel negative cost cycles, until
1357 no more negative cycles exist. This also updates the flow field
1358 to represent the minimum cost flow so far. */
1360 while (cancel_negative_cycle (fixup_graph
, pred
, d
, cycle
))
1363 if (iteration
> MAX_ITER (fixup_graph
->num_vertices
,
1364 fixup_graph
->num_edges
))
1369 dump_fixup_graph (dump_file
, fixup_graph
,
1370 "After find_minimum_cost_flow()");
1372 /* Cleanup structures. */
1379 /* Compute the sum of the edge counts in TO_EDGES. */
1382 sum_edge_counts (vec
<edge
, va_gc
> *to_edges
)
1388 FOR_EACH_EDGE (e
, ei
, to_edges
)
1390 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1398 /* Main routine. Smoothes the initial assigned basic block and edge counts using
1399 a minimum cost flow algorithm, to ensure that the flow consistency rule is
1400 obeyed: sum of outgoing edges = sum of incoming edges for each basic
1404 mcf_smooth_cfg (void)
1406 fixup_graph_type fixup_graph
;
1407 memset (&fixup_graph
, 0, sizeof (fixup_graph
));
1408 create_fixup_graph (&fixup_graph
);
1409 find_minimum_cost_flow (&fixup_graph
);
1410 adjust_cfg_counts (&fixup_graph
);
1411 delete_fixup_graph (&fixup_graph
);