1 /* Routines to implement minimum-cost maximal flow algorithm used to smooth
2 basic block and edge frequency counts.
3 Copyright (C) 2008-2014 Free Software Foundation, Inc.
4 Contributed by Paul Yuan (yingbo.com@gmail.com) and
5 Vinodha Ramasamy (vinodha@google.com).
7 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
23 [1] "Feedback-directed Optimizations in GCC with Estimated Edge Profiles
24 from Hardware Event Sampling", Vinodha Ramasamy, Paul Yuan, Dehao Chen,
25 and Robert Hundt; GCC Summit 2008.
26 [2] "Complementing Missing and Inaccurate Profiling Using a Minimum Cost
27 Circulation Algorithm", Roy Levin, Ilan Newman and Gadi Haber;
30 Algorithm to smooth basic block and edge counts:
31 1. create_fixup_graph: Create fixup graph by translating function CFG into
32 a graph that satisfies MCF algorithm requirements.
33 2. find_max_flow: Find maximal flow.
34 3. compute_residual_flow: Form residual network.
36 cancel_negative_cycle: While G contains a negative cost cycle C, reverse
37 the flow on the found cycle by the minimum residual capacity in that
39 5. Form the minimal cost flow
41 6. adjust_cfg_counts: Update initial edge weights with corrected weights.
42 delta(u.v) = f(u,v) -f(v,u).
43 w*(u,v) = w(u,v) + delta(u,v). */
47 #include "coretypes.h"
48 #include "basic-block.h"
51 #include "diagnostic-core.h"
57 /* CAP_INFINITY: Constant to represent infinite capacity. */
58 #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT)
61 #define K_POS(b) ((b))
62 #define K_NEG(b) (50 * (b))
63 #define COST(k, w) ((k) / mcf_ln ((w) + 2))
64 /* Limit the number of iterations for cancel_negative_cycles() to ensure
65 reasonable compile time. */
66 #define MAX_ITER(n, e) (PARAM_VALUE (PARAM_MIN_MCF_CANCEL_ITERS) + \
67 (1000000 / ((n) * (e))))
72 VERTEX_SPLIT_EDGE
, /* Edge to represent vertex with w(e) = w(v). */
73 REDIRECT_EDGE
, /* Edge after vertex transformation. */
75 SOURCE_CONNECT_EDGE
, /* Single edge connecting to single source. */
76 SINK_CONNECT_EDGE
, /* Single edge connecting to single sink. */
77 SINK_SOURCE_EDGE
, /* Single edge connecting sink to source. */
78 BALANCE_EDGE
, /* Edge connecting with source/sink: cp(e) = 0. */
79 REDIRECT_NORMALIZED_EDGE
, /* Normalized edge for a redirect edge. */
80 REVERSE_NORMALIZED_EDGE
/* Normalized edge for a reverse edge. */
83 /* Structure to represent an edge in the fixup graph. */
84 typedef struct fixup_edge_d
88 /* Flag denoting type of edge and attributes for the flow field. */
91 /* Index to the normalization vertex added for this edge. */
92 int norm_vertex_index
;
93 /* Flow for this edge. */
95 /* Residual flow for this edge - used during negative cycle canceling. */
99 gcov_type max_capacity
;
102 typedef fixup_edge_type
*fixup_edge_p
;
105 /* Structure to represent a vertex in the fixup graph. */
106 typedef struct fixup_vertex_d
108 vec
<fixup_edge_p
> succ_edges
;
111 typedef fixup_vertex_type
*fixup_vertex_p
;
113 /* Fixup graph used in the MCF algorithm. */
114 typedef struct fixup_graph_d
116 /* Current number of vertices for the graph. */
118 /* Current number of edges for the graph. */
120 /* Index of new entry vertex. */
122 /* Index of new exit vertex. */
124 /* Fixup vertex list. Adjacency list for fixup graph. */
125 fixup_vertex_p vertex_list
;
126 /* Fixup edge list. */
127 fixup_edge_p edge_list
;
130 typedef struct queue_d
138 /* Structure used in the maximal flow routines to find augmenting path. */
139 typedef struct augmenting_path_d
141 /* Queue used to hold vertex indices. */
142 queue_type queue_list
;
143 /* Vector to hold chain of pred vertex indices in augmenting path. */
145 /* Vector that indicates if basic block i has been visited. */
147 } augmenting_path_type
;
150 /* Function definitions. */
152 /* Dump routines to aid debugging. */
154 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */
157 print_basic_block (FILE *file
, fixup_graph_type
*fixup_graph
, int n
)
159 if (n
== ENTRY_BLOCK
)
160 fputs ("ENTRY", file
);
161 else if (n
== ENTRY_BLOCK
+ 1)
162 fputs ("ENTRY''", file
);
163 else if (n
== 2 * EXIT_BLOCK
)
164 fputs ("EXIT", file
);
165 else if (n
== 2 * EXIT_BLOCK
+ 1)
166 fputs ("EXIT''", file
);
167 else if (n
== fixup_graph
->new_exit_index
)
168 fputs ("NEW_EXIT", file
);
169 else if (n
== fixup_graph
->new_entry_index
)
170 fputs ("NEW_ENTRY", file
);
173 fprintf (file
, "%d", n
/ 2);
182 /* Print edge S->D for given fixup_graph with n' and n'' format.
184 S is the index of the source vertex of the edge (input) and
185 D is the index of the destination vertex of the edge (input) for the given
186 fixup_graph (input). */
189 print_edge (FILE *file
, fixup_graph_type
*fixup_graph
, int s
, int d
)
191 print_basic_block (file
, fixup_graph
, s
);
193 print_basic_block (file
, fixup_graph
, d
);
197 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
200 dump_fixup_edge (FILE *file
, fixup_graph_type
*fixup_graph
, fixup_edge_p fedge
)
204 fputs ("NULL fixup graph edge.\n", file
);
208 print_edge (file
, fixup_graph
, fedge
->src
, fedge
->dest
);
213 fprintf (file
, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC
"/",
215 if (fedge
->max_capacity
== CAP_INFINITY
)
216 fputs ("+oo,", file
);
218 fprintf (file
, "" HOST_WIDEST_INT_PRINT_DEC
",", fedge
->max_capacity
);
221 if (fedge
->is_rflow_valid
)
223 if (fedge
->rflow
== CAP_INFINITY
)
224 fputs (" rflow=+oo.", file
);
226 fprintf (file
, " rflow=" HOST_WIDEST_INT_PRINT_DEC
",", fedge
->rflow
);
229 fprintf (file
, " cost=" HOST_WIDEST_INT_PRINT_DEC
".", fedge
->cost
);
231 fprintf (file
, "\t(%d->%d)", fedge
->src
, fedge
->dest
);
237 case VERTEX_SPLIT_EDGE
:
238 fputs (" @VERTEX_SPLIT_EDGE", file
);
242 fputs (" @REDIRECT_EDGE", file
);
245 case SOURCE_CONNECT_EDGE
:
246 fputs (" @SOURCE_CONNECT_EDGE", file
);
249 case SINK_CONNECT_EDGE
:
250 fputs (" @SINK_CONNECT_EDGE", file
);
253 case SINK_SOURCE_EDGE
:
254 fputs (" @SINK_SOURCE_EDGE", file
);
258 fputs (" @REVERSE_EDGE", file
);
262 fputs (" @BALANCE_EDGE", file
);
265 case REDIRECT_NORMALIZED_EDGE
:
266 case REVERSE_NORMALIZED_EDGE
:
267 fputs (" @NORMALIZED_EDGE", file
);
271 fputs (" @INVALID_EDGE", file
);
279 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
280 file. The input string MSG is printed out as a heading. */
283 dump_fixup_graph (FILE *file
, fixup_graph_type
*fixup_graph
, const char *msg
)
286 int fnum_vertices
, fnum_edges
;
288 fixup_vertex_p fvertex_list
, pfvertex
;
291 gcc_assert (fixup_graph
);
292 fvertex_list
= fixup_graph
->vertex_list
;
293 fnum_vertices
= fixup_graph
->num_vertices
;
294 fnum_edges
= fixup_graph
->num_edges
;
296 fprintf (file
, "\nDump fixup graph for %s(): %s.\n",
297 current_function_name (), msg
);
299 "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
300 fnum_vertices
, fnum_edges
, fixup_graph
->new_exit_index
);
302 for (i
= 0; i
< fnum_vertices
; i
++)
304 pfvertex
= fvertex_list
+ i
;
305 fprintf (file
, "vertex_list[%d]: %d succ fixup edges.\n",
306 i
, pfvertex
->succ_edges
.length ());
308 for (j
= 0; pfvertex
->succ_edges
.iterate (j
, &pfedge
);
311 /* Distinguish forward edges and backward edges in the residual flow
314 fputs ("(f) ", file
);
315 else if (pfedge
->is_rflow_valid
)
316 fputs ("(b) ", file
);
317 dump_fixup_edge (file
, fixup_graph
, pfedge
);
325 /* Utility routines. */
326 /* ln() implementation: approximate calculation. Returns ln of X. */
347 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
348 implementation) by John Carmack. Returns sqrt of X. */
353 #define MAGIC_CONST1 0x1fbcf800
354 #define MAGIC_CONST2 0x5f3759df
358 } convertor
, convertor2
;
362 convertor
.floatPart
= x
;
363 convertor2
.floatPart
= x
;
364 convertor
.intPart
= MAGIC_CONST1
+ (convertor
.intPart
>> 1);
365 convertor2
.intPart
= MAGIC_CONST2
- (convertor2
.intPart
>> 1);
367 return 0.5f
* (convertor
.floatPart
+ (x
* convertor2
.floatPart
));
371 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
372 (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
373 added set to COST. */
376 add_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
, gcov_type cost
)
378 fixup_vertex_p curr_vertex
= fixup_graph
->vertex_list
+ src
;
379 fixup_edge_p curr_edge
= fixup_graph
->edge_list
+ fixup_graph
->num_edges
;
380 curr_edge
->src
= src
;
381 curr_edge
->dest
= dest
;
382 curr_edge
->cost
= cost
;
383 fixup_graph
->num_edges
++;
385 dump_fixup_edge (dump_file
, fixup_graph
, curr_edge
);
386 curr_vertex
->succ_edges
.safe_push (curr_edge
);
391 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
392 MAX_CAPACITY to the edge_list in the fixup graph. */
395 add_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
396 edge_type type
, gcov_type weight
, gcov_type cost
,
397 gcov_type max_capacity
)
399 fixup_edge_p curr_edge
= add_edge (fixup_graph
, src
, dest
, cost
);
400 curr_edge
->type
= type
;
401 curr_edge
->weight
= weight
;
402 curr_edge
->max_capacity
= max_capacity
;
406 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
407 to the fixup graph. */
410 add_rfixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
,
411 gcov_type rflow
, gcov_type cost
)
413 fixup_edge_p curr_edge
= add_edge (fixup_graph
, src
, dest
, cost
);
414 curr_edge
->rflow
= rflow
;
415 curr_edge
->is_rflow_valid
= true;
416 /* This edge is not a valid edge - merely used to hold residual flow. */
417 curr_edge
->type
= INVALID_EDGE
;
421 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
422 exist in the FIXUP_GRAPH. */
425 find_fixup_edge (fixup_graph_type
*fixup_graph
, int src
, int dest
)
429 fixup_vertex_p pfvertex
;
431 gcc_assert (src
< fixup_graph
->num_vertices
);
433 pfvertex
= fixup_graph
->vertex_list
+ src
;
435 for (j
= 0; pfvertex
->succ_edges
.iterate (j
, &pfedge
);
437 if (pfedge
->dest
== dest
)
444 /* Cleanup routine to free structures in FIXUP_GRAPH. */
447 delete_fixup_graph (fixup_graph_type
*fixup_graph
)
450 int fnum_vertices
= fixup_graph
->num_vertices
;
451 fixup_vertex_p pfvertex
= fixup_graph
->vertex_list
;
453 for (i
= 0; i
< fnum_vertices
; i
++, pfvertex
++)
454 pfvertex
->succ_edges
.release ();
456 free (fixup_graph
->vertex_list
);
457 free (fixup_graph
->edge_list
);
461 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */
464 create_fixup_graph (fixup_graph_type
*fixup_graph
)
466 double sqrt_avg_vertex_weight
= 0;
467 double total_vertex_weight
= 0;
470 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */
471 gcov_type
*diff_out_in
= NULL
;
472 gcov_type supply_value
= 0, demand_value
= 0;
474 int new_entry_index
= 0, new_exit_index
= 0;
480 fixup_edge_p pfedge
, r_pfedge
;
481 fixup_edge_p fedge_list
;
484 /* Each basic_block will be split into 2 during vertex transformation. */
485 int fnum_vertices_after_transform
= 2 * n_basic_blocks_for_fn (cfun
);
486 int fnum_edges_after_transform
=
487 n_edges_for_fn (cfun
) + n_basic_blocks_for_fn (cfun
);
489 /* Count the new SOURCE and EXIT vertices to be added. */
490 int fmax_num_vertices
=
491 (fnum_vertices_after_transform
+ n_edges_for_fn (cfun
)
492 + n_basic_blocks_for_fn (cfun
) + 2);
494 /* In create_fixup_graph: Each basic block and edge can be split into 3
495 edges. Number of balance edges = n_basic_blocks - 1. And there is 1 edge
496 connecting new_entry and new_exit, and 2 edges connecting new_entry to
497 entry, and exit to new_exit. So after create_fixup_graph:
498 max_edges = 4 * n_basic_blocks + 3 * n_edges + 2
499 Accounting for residual flow edges
501 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
502 = 8 * n_basic_blocks + 6 * n_edges
503 < 8 * n_basic_blocks + 8 * n_edges. */
504 int fmax_num_edges
= 8 * (n_basic_blocks_for_fn (cfun
) +
505 n_edges_for_fn (cfun
));
507 /* Initial num of vertices in the fixup graph. */
508 fixup_graph
->num_vertices
= n_basic_blocks_for_fn (cfun
);
510 /* Fixup graph vertex list. */
511 fixup_graph
->vertex_list
=
512 (fixup_vertex_p
) xcalloc (fmax_num_vertices
, sizeof (fixup_vertex_type
));
514 /* Fixup graph edge list. */
515 fixup_graph
->edge_list
=
516 (fixup_edge_p
) xcalloc (fmax_num_edges
, sizeof (fixup_edge_type
));
519 (gcov_type
*) xcalloc (1 + fnum_vertices_after_transform
,
522 /* Compute constants b, k_pos, k_neg used in the cost function calculation.
523 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */
524 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
525 total_vertex_weight
+= bb
->count
;
527 sqrt_avg_vertex_weight
= mcf_sqrt (total_vertex_weight
/
528 n_basic_blocks_for_fn (cfun
));
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");
539 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
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; pfvertex
->succ_edges
.iterate (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_FOR_FN (cfun
),
1162 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1169 "BB%d: " HOST_WIDEST_INT_PRINT_DEC
"", bb
->index
, bb
->count
);
1171 pfedge
= find_fixup_edge (fixup_graph
, i
, i
+ 1);
1174 bb
->count
+= pfedge
->flow
;
1177 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1179 print_edge (dump_file
, fixup_graph
, i
, i
+ 1);
1180 fprintf (dump_file
, ")");
1185 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1186 /* Deduct flow from normalized reverse edge. */
1187 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1189 bb
->count
-= pfedge_n
->flow
;
1192 fprintf (dump_file
, " - " HOST_WIDEST_INT_PRINT_DEC
"(",
1194 print_edge (dump_file
, fixup_graph
, i
+ 1,
1195 pfedge
->norm_vertex_index
);
1196 fprintf (dump_file
, ")");
1200 fprintf (dump_file
, " = " HOST_WIDEST_INT_PRINT_DEC
"\n", bb
->count
);
1203 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1205 /* Treat edges with ignore attribute set as if they don't exist. */
1206 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1209 j
= 2 * e
->dest
->index
;
1211 fprintf (dump_file
, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC
"",
1212 bb
->index
, e
->dest
->index
, e
->count
);
1214 pfedge
= find_fixup_edge (fixup_graph
, i
+ 1, j
);
1216 if (bb
->index
!= e
->dest
->index
)
1218 /* Non-self edge. */
1221 e
->count
+= pfedge
->flow
;
1224 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1226 print_edge (dump_file
, fixup_graph
, i
+ 1, j
);
1227 fprintf (dump_file
, ")");
1232 find_fixup_edge (fixup_graph
, j
, pfedge
->norm_vertex_index
);
1233 /* Deduct flow from normalized reverse edge. */
1234 if (pfedge
->norm_vertex_index
&& pfedge_n
->flow
)
1236 e
->count
-= pfedge_n
->flow
;
1239 fprintf (dump_file
, " - " HOST_WIDEST_INT_PRINT_DEC
"(",
1241 print_edge (dump_file
, fixup_graph
, j
,
1242 pfedge
->norm_vertex_index
);
1243 fprintf (dump_file
, ")");
1249 /* Handle self edges. Self edge is split with a normalization
1250 vertex. Here i=j. */
1251 pfedge
= find_fixup_edge (fixup_graph
, j
, i
+ 1);
1253 find_fixup_edge (fixup_graph
, i
+ 1, pfedge
->norm_vertex_index
);
1254 e
->count
+= pfedge_n
->flow
;
1255 bb
->count
+= pfedge_n
->flow
;
1258 fprintf (dump_file
, "(self edge)");
1259 fprintf (dump_file
, " + " HOST_WIDEST_INT_PRINT_DEC
"(",
1261 print_edge (dump_file
, fixup_graph
, i
+ 1,
1262 pfedge
->norm_vertex_index
);
1263 fprintf (dump_file
, ")");
1268 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1270 fprintf (dump_file
, " = " HOST_WIDEST_INT_PRINT_DEC
"\t(%.1f%%)\n",
1271 e
->count
, e
->probability
* 100.0 / REG_BR_PROB_BASE
);
1275 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
=
1276 sum_edge_counts (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1277 EXIT_BLOCK_PTR_FOR_FN (cfun
)->count
=
1278 sum_edge_counts (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
1280 /* Compute edge probabilities. */
1281 FOR_ALL_BB_FN (bb
, cfun
)
1285 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1286 e
->probability
= REG_BR_PROB_BASE
* e
->count
/ bb
->count
;
1291 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1292 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1296 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1298 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1299 e
->probability
= REG_BR_PROB_BASE
/ total
;
1306 total
+= EDGE_COUNT (bb
->succs
);
1307 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1308 e
->probability
= REG_BR_PROB_BASE
/ total
;
1315 fprintf (dump_file
, "\nCheck %s() CFG flow conservation:\n",
1316 current_function_name ());
1317 FOR_EACH_BB_FN (bb
, cfun
)
1319 if ((bb
->count
!= sum_edge_counts (bb
->preds
))
1320 || (bb
->count
!= sum_edge_counts (bb
->succs
)))
1323 "BB%d(" HOST_WIDEST_INT_PRINT_DEC
") **INVALID**: ",
1324 bb
->index
, bb
->count
);
1326 "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC
1327 ") **INVALID**: \n", bb
->index
, bb
->count
);
1328 fprintf (dump_file
, "in_edges=" HOST_WIDEST_INT_PRINT_DEC
" ",
1329 sum_edge_counts (bb
->preds
));
1330 fprintf (dump_file
, "out_edges=" HOST_WIDEST_INT_PRINT_DEC
"\n",
1331 sum_edge_counts (bb
->succs
));
1338 /* Called before negative_cycle_cancellation, to form a cycle between
1339 * new_exit to new_entry in FIXUP_GRAPH with capacity MAX_FLOW. We
1340 * don't want the flow in the BALANCE_EDGE to be modified, so we set
1341 * the residural flow of those edges to 0 */
1344 modify_sink_source_capacity (fixup_graph_type
*fixup_graph
, gcov_type max_flow
)
1346 fixup_edge_p edge
, r_edge
;
1348 int entry
= ENTRY_BLOCK
;
1349 int exit
= 2 * EXIT_BLOCK
+ 1;
1350 int new_entry
= fixup_graph
->new_entry_index
;
1351 int new_exit
= fixup_graph
->new_exit_index
;
1353 edge
= find_fixup_edge (fixup_graph
, new_entry
, entry
);
1354 edge
->max_capacity
= CAP_INFINITY
;
1355 edge
->rflow
= CAP_INFINITY
;
1357 edge
= find_fixup_edge (fixup_graph
, entry
, new_entry
);
1358 edge
->max_capacity
= CAP_INFINITY
;
1359 edge
->rflow
= CAP_INFINITY
;
1361 edge
= find_fixup_edge (fixup_graph
, exit
, new_exit
);
1362 edge
->max_capacity
= CAP_INFINITY
;
1363 edge
->rflow
= CAP_INFINITY
;
1365 edge
= find_fixup_edge (fixup_graph
, new_exit
, exit
);
1366 edge
->max_capacity
= CAP_INFINITY
;
1367 edge
->rflow
= CAP_INFINITY
;
1369 edge
= find_fixup_edge (fixup_graph
, new_exit
, new_entry
);
1370 edge
->max_capacity
= CAP_INFINITY
;
1371 edge
->flow
= max_flow
;
1372 edge
->rflow
= CAP_INFINITY
;
1374 r_edge
= find_fixup_edge (fixup_graph
, new_entry
, new_exit
);
1375 r_edge
->rflow
= max_flow
;
1377 /* Find all the backwards residual edges corresponding to
1378 BALANCE_EDGEs and set their residual flow to 0 to enforce a
1379 minimum flow constraint on these edges. */
1380 for (i
= 4; i
< new_entry
; i
+= 1)
1382 edge
= find_fixup_edge (fixup_graph
, i
, new_entry
);
1385 edge
= find_fixup_edge (fixup_graph
, new_exit
, i
);
1392 /* Implements the negative cycle canceling algorithm to compute a minimum cost
1395 1. Find maximal flow.
1396 2. Form residual network
1398 While G contains a negative cost cycle C, reverse the flow on the found cycle
1399 by the minimum residual capacity in that cycle.
1400 4. Form the minimal cost flow
1403 FIXUP_GRAPH - Initial fixup graph.
1404 The flow field is modified to represent the minimum cost flow. */
1407 find_minimum_cost_flow (fixup_graph_type
*fixup_graph
)
1409 /* Holds the index of predecessor in path. */
1411 /* Used to hold the minimum cost cycle. */
1413 /* Used to record the number of iterations of cancel_negative_cycle. */
1415 /* Vector d[i] holds the minimum cost of path from i to sink. */
1419 int new_entry_index
;
1422 gcc_assert (fixup_graph
);
1423 fnum_vertices
= fixup_graph
->num_vertices
;
1424 new_exit_index
= fixup_graph
->new_exit_index
;
1425 new_entry_index
= fixup_graph
->new_entry_index
;
1427 max_flow
= find_max_flow (fixup_graph
, new_entry_index
, new_exit_index
);
1429 /* Adjust the fixup graph to translate things into a minimum cost
1430 circulation problem. */
1431 modify_sink_source_capacity (fixup_graph
, max_flow
);
1433 /* Initialize the structures for find_negative_cycle(). */
1434 pred
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1435 d
= (gcov_type
*) xcalloc (fnum_vertices
, sizeof (gcov_type
));
1436 cycle
= (int *) xcalloc (fnum_vertices
, sizeof (int));
1438 /* Repeatedly find and cancel negative cost cycles, until
1439 no more negative cycles exist. This also updates the flow field
1440 to represent the minimum cost flow so far. */
1442 while (cancel_negative_cycle (fixup_graph
, pred
, d
, cycle
))
1445 if (iteration
> MAX_ITER (fixup_graph
->num_vertices
,
1446 fixup_graph
->num_edges
))
1448 if (dump_enabled_p ())
1449 dump_printf_loc (MSG_NOTE
,
1450 DECL_SOURCE_LOCATION (current_function_decl
),
1451 "Exiting profile correction early to avoid "
1452 "excessive compile time");
1458 dump_fixup_graph (dump_file
, fixup_graph
,
1459 "After find_minimum_cost_flow()");
1461 /* Cleanup structures. */
1468 /* Compute the sum of the edge counts in TO_EDGES. */
1471 sum_edge_counts (vec
<edge
, va_gc
> *to_edges
)
1477 FOR_EACH_EDGE (e
, ei
, to_edges
)
1479 if (EDGE_INFO (e
) && EDGE_INFO (e
)->ignore
)
1487 /* Main routine. Smoothes the initial assigned basic block and edge counts using
1488 a minimum cost flow algorithm, to ensure that the flow consistency rule is
1489 obeyed: sum of outgoing edges = sum of incoming edges for each basic
1493 mcf_smooth_cfg (void)
1495 fixup_graph_type fixup_graph
;
1496 memset (&fixup_graph
, 0, sizeof (fixup_graph
));
1497 create_fixup_graph (&fixup_graph
);
1498 find_minimum_cost_flow (&fixup_graph
);
1499 adjust_cfg_counts (&fixup_graph
);
1500 delete_fixup_graph (&fixup_graph
);