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). 7 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 12 version. 13 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 17 for more details. 18 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/>. */ 22 23 /* References: 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; 29 HiPEAC '08. 30 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. 36 4. Repeat: 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 39 cycle. 40 5. Form the minimal cost flow 41 f(u,v) = rf(v, u). 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). */ 45 46 #include "config.h" 47 #include "system.h" 48 #include "coretypes.h" 49 #include "tm.h" 50 #include "basic-block.h" 51 #include "output.h" 52 #include "langhooks.h" 53 #include "tree.h" 54 #include "gcov-io.h" 55 56 #include "profile.h" 57 58 /* CAP_INFINITY: Constant to represent infinite capacity. */ 59 #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT) 60 61 /* COST FUNCTION. */ 62 #define K_POS(b) ((b)) 63 #define K_NEG(b) (50 * (b)) 64 #define COST(k, w) ((k) / mcf_ln ((w) + 2)) 65 /* Limit the number of iterations for cancel_negative_cycles() to ensure 66 reasonable compile time. */ 67 #define MAX_ITER(n, e) 10 + (1000000 / ((n) * (e))) 68 typedef enum 69 { 70 INVALID_EDGE, 71 VERTEX_SPLIT_EDGE, /* Edge to represent vertex with w(e) = w(v). */ 72 REDIRECT_EDGE, /* Edge after vertex transformation. */ 73 REVERSE_EDGE, 74 SOURCE_CONNECT_EDGE, /* Single edge connecting to single source. */ 75 SINK_CONNECT_EDGE, /* Single edge connecting to single sink. */ 76 BALANCE_EDGE, /* Edge connecting with source/sink: cp(e) = 0. */ 77 REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge. */ 78 REVERSE_NORMALIZED_EDGE /* Normalized edge for a reverse edge. */ 79 } edge_type; 80 81 /* Structure to represent an edge in the fixup graph. */ 82 typedef struct fixup_edge_d 83 { 84 int src; 85 int dest; 86 /* Flag denoting type of edge and attributes for the flow field. */ 87 edge_type type; 88 bool is_rflow_valid; 89 /* Index to the normalization vertex added for this edge. */ 90 int norm_vertex_index; 91 /* Flow for this edge. */ 92 gcov_type flow; 93 /* Residual flow for this edge - used during negative cycle canceling. */ 94 gcov_type rflow; 95 gcov_type weight; 96 gcov_type cost; 97 gcov_type max_capacity; 98 } fixup_edge_type; 99 100 typedef fixup_edge_type *fixup_edge_p; 101 102 DEF_VEC_P (fixup_edge_p); 103 DEF_VEC_ALLOC_P (fixup_edge_p, heap); 104 105 /* Structure to represent a vertex in the fixup graph. */ 106 typedef struct fixup_vertex_d 107 { 108 VEC (fixup_edge_p, heap) *succ_edges; 109 } fixup_vertex_type; 110 111 typedef fixup_vertex_type *fixup_vertex_p; 112 113 /* Fixup graph used in the MCF algorithm. */ 114 typedef struct fixup_graph_d 115 { 116 /* Current number of vertices for the graph. */ 117 int num_vertices; 118 /* Current number of edges for the graph. */ 119 int num_edges; 120 /* Index of new entry vertex. */ 121 int new_entry_index; 122 /* Index of new exit vertex. */ 123 int new_exit_index; 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; 128 } fixup_graph_type; 129 130 typedef struct queue_d 131 { 132 int *queue; 133 int head; 134 int tail; 135 int size; 136 } queue_type; 137 138 /* Structure used in the maximal flow routines to find augmenting path. */ 139 typedef struct augmenting_path_d 140 { 141 /* Queue used to hold vertex indices. */ 142 queue_type queue_list; 143 /* Vector to hold chain of pred vertex indices in augmenting path. */ 144 int *bb_pred; 145 /* Vector that indicates if basic block i has been visited. */ 146 int *is_visited; 147 } augmenting_path_type; 148 149 150 /* Function definitions. */ 151 152 /* Dump routines to aid debugging. */ 153 154 /* Print basic block with index N for FIXUP_GRAPH in n' and n'' format. */ 155 156 static void 157 print_basic_block (FILE *file, fixup_graph_type *fixup_graph, int n) 158 { 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); 171 else 172 { 173 fprintf (file, "%d", n / 2); 174 if (n % 2) 175 fputs ("''", file); 176 else 177 fputs ("'", file); 178 } 179 } 180 181 182 /* Print edge S->D for given fixup_graph with n' and n'' format. 183 PARAMETERS: 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). */ 187 188 static void 189 print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d) 190 { 191 print_basic_block (file, fixup_graph, s); 192 fputs ("->", file); 193 print_basic_block (file, fixup_graph, d); 194 } 195 196 197 /* Dump out the attributes of a given edge FEDGE in the fixup_graph to a 198 file. */ 199 static void 200 dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge) 201 { 202 if (!fedge) 203 { 204 fputs ("NULL fixup graph edge.\n", file); 205 return; 206 } 207 208 print_edge (file, fixup_graph, fedge->src, fedge->dest); 209 fputs (": ", file); 210 211 if (fedge->type) 212 { 213 fprintf (file, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC "/", 214 fedge->flow); 215 if (fedge->max_capacity == CAP_INFINITY) 216 fputs ("+oo,", file); 217 else 218 fprintf (file, "" HOST_WIDEST_INT_PRINT_DEC ",", fedge->max_capacity); 219 } 220 221 if (fedge->is_rflow_valid) 222 { 223 if (fedge->rflow == CAP_INFINITY) 224 fputs (" rflow=+oo.", file); 225 else 226 fprintf (file, " rflow=" HOST_WIDEST_INT_PRINT_DEC ",", fedge->rflow); 227 } 228 229 fprintf (file, " cost=" HOST_WIDEST_INT_PRINT_DEC ".", fedge->cost); 230 231 fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest); 232 233 if (fedge->type) 234 { 235 switch (fedge->type) 236 { 237 case VERTEX_SPLIT_EDGE: 238 fputs (" @VERTEX_SPLIT_EDGE", file); 239 break; 240 241 case REDIRECT_EDGE: 242 fputs (" @REDIRECT_EDGE", file); 243 break; 244 245 case SOURCE_CONNECT_EDGE: 246 fputs (" @SOURCE_CONNECT_EDGE", file); 247 break; 248 249 case SINK_CONNECT_EDGE: 250 fputs (" @SINK_CONNECT_EDGE", file); 251 break; 252 253 case REVERSE_EDGE: 254 fputs (" @REVERSE_EDGE", file); 255 break; 256 257 case BALANCE_EDGE: 258 fputs (" @BALANCE_EDGE", file); 259 break; 260 261 case REDIRECT_NORMALIZED_EDGE: 262 case REVERSE_NORMALIZED_EDGE: 263 fputs (" @NORMALIZED_EDGE", file); 264 break; 265 266 default: 267 fputs (" @INVALID_EDGE", file); 268 break; 269 } 270 } 271 fputs ("\n", file); 272 } 273 274 275 /* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump 276 file. The input string MSG is printed out as a heading. */ 277 278 static void 279 dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg) 280 { 281 int i, j; 282 int fnum_vertices, fnum_edges; 283 284 fixup_vertex_p fvertex_list, pfvertex; 285 fixup_edge_p pfedge; 286 287 gcc_assert (fixup_graph); 288 fvertex_list = fixup_graph->vertex_list; 289 fnum_vertices = fixup_graph->num_vertices; 290 fnum_edges = fixup_graph->num_edges; 291 292 fprintf (file, "\nDump fixup graph for %s(): %s.\n", 293 lang_hooks.decl_printable_name (current_function_decl, 2), msg); 294 fprintf (file, 295 "There are %d vertices and %d edges. new_exit_index is %d.\n\n", 296 fnum_vertices, fnum_edges, fixup_graph->new_exit_index); 297 298 for (i = 0; i < fnum_vertices; i++) 299 { 300 pfvertex = fvertex_list + i; 301 fprintf (file, "vertex_list[%d]: %d succ fixup edges.\n", 302 i, VEC_length (fixup_edge_p, pfvertex->succ_edges)); 303 304 for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge); 305 j++) 306 { 307 /* Distinguish forward edges and backward edges in the residual flow 308 network. */ 309 if (pfedge->type) 310 fputs ("(f) ", file); 311 else if (pfedge->is_rflow_valid) 312 fputs ("(b) ", file); 313 dump_fixup_edge (file, fixup_graph, pfedge); 314 } 315 } 316 317 fputs ("\n", file); 318 } 319 320 321 /* Utility routines. */ 322 /* ln() implementation: approximate calculation. Returns ln of X. */ 323 324 static double 325 mcf_ln (double x) 326 { 327 #define E 2.71828 328 int l = 1; 329 double m = E; 330 331 gcc_assert (x >= 0); 332 333 while (m < x) 334 { 335 m *= E; 336 l++; 337 } 338 339 return l; 340 } 341 342 343 /* sqrt() implementation: based on open source QUAKE3 code (magic sqrt 344 implementation) by John Carmack. Returns sqrt of X. */ 345 346 static double 347 mcf_sqrt (double x) 348 { 349 #define MAGIC_CONST1 0x1fbcf800 350 #define MAGIC_CONST2 0x5f3759df 351 union { 352 int intPart; 353 float floatPart; 354 } convertor, convertor2; 355 356 gcc_assert (x >= 0); 357 358 convertor.floatPart = x; 359 convertor2.floatPart = x; 360 convertor.intPart = MAGIC_CONST1 + (convertor.intPart >> 1); 361 convertor2.intPart = MAGIC_CONST2 - (convertor2.intPart >> 1); 362 363 return 0.5f * (convertor.floatPart + (x * convertor2.floatPart)); 364 } 365 366 367 /* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge 368 (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge 369 added set to COST. */ 370 371 static fixup_edge_p 372 add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost) 373 { 374 fixup_vertex_p curr_vertex = fixup_graph->vertex_list + src; 375 fixup_edge_p curr_edge = fixup_graph->edge_list + fixup_graph->num_edges; 376 curr_edge->src = src; 377 curr_edge->dest = dest; 378 curr_edge->cost = cost; 379 fixup_graph->num_edges++; 380 if (dump_file) 381 dump_fixup_edge (dump_file, fixup_graph, curr_edge); 382 VEC_safe_push (fixup_edge_p, heap, curr_vertex->succ_edges, curr_edge); 383 return curr_edge; 384 } 385 386 387 /* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and 388 MAX_CAPACITY to the edge_list in the fixup graph. */ 389 390 static void 391 add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest, 392 edge_type type, gcov_type weight, gcov_type cost, 393 gcov_type max_capacity) 394 { 395 fixup_edge_p curr_edge = add_edge(fixup_graph, src, dest, cost); 396 curr_edge->type = type; 397 curr_edge->weight = weight; 398 curr_edge->max_capacity = max_capacity; 399 } 400 401 402 /* Add a residual edge (SRC->DEST) with attributes RFLOW and COST 403 to the fixup graph. */ 404 405 static void 406 add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest, 407 gcov_type rflow, gcov_type cost) 408 { 409 fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost); 410 curr_edge->rflow = rflow; 411 curr_edge->is_rflow_valid = true; 412 /* This edge is not a valid edge - merely used to hold residual flow. */ 413 curr_edge->type = INVALID_EDGE; 414 } 415 416 417 /* Return the pointer to fixup edge SRC->DEST or NULL if edge does not 418 exist in the FIXUP_GRAPH. */ 419 420 static fixup_edge_p 421 find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest) 422 { 423 int j; 424 fixup_edge_p pfedge; 425 fixup_vertex_p pfvertex; 426 427 gcc_assert (src < fixup_graph->num_vertices); 428 429 pfvertex = fixup_graph->vertex_list + src; 430 431 for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge); 432 j++) 433 if (pfedge->dest == dest) 434 return pfedge; 435 436 return NULL; 437 } 438 439 440 /* Cleanup routine to free structures in FIXUP_GRAPH. */ 441 442 static void 443 delete_fixup_graph (fixup_graph_type *fixup_graph) 444 { 445 int i; 446 int fnum_vertices = fixup_graph->num_vertices; 447 fixup_vertex_p pfvertex = fixup_graph->vertex_list; 448 449 for (i = 0; i < fnum_vertices; i++, pfvertex++) 450 VEC_free (fixup_edge_p, heap, pfvertex->succ_edges); 451 452 free (fixup_graph->vertex_list); 453 free (fixup_graph->edge_list); 454 } 455 456 457 /* Creates a fixup graph FIXUP_GRAPH from the function CFG. */ 458 459 static void 460 create_fixup_graph (fixup_graph_type *fixup_graph) 461 { 462 double sqrt_avg_vertex_weight = 0; 463 double total_vertex_weight = 0; 464 double k_pos = 0; 465 double k_neg = 0; 466 /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v). */ 467 gcov_type *diff_out_in = NULL; 468 gcov_type supply_value = 1, demand_value = 0; 469 gcov_type fcost = 0; 470 int new_entry_index = 0, new_exit_index = 0; 471 int i = 0, j = 0; 472 int new_index = 0; 473 basic_block bb; 474 edge e; 475 edge_iterator ei; 476 fixup_edge_p pfedge, r_pfedge; 477 fixup_edge_p fedge_list; 478 int fnum_edges; 479 480 /* Each basic_block will be split into 2 during vertex transformation. */ 481 int fnum_vertices_after_transform = 2 * n_basic_blocks; 482 int fnum_edges_after_transform = n_edges + n_basic_blocks; 483 484 /* Count the new SOURCE and EXIT vertices to be added. */ 485 int fmax_num_vertices = 486 fnum_vertices_after_transform + n_edges + n_basic_blocks + 2; 487 488 /* In create_fixup_graph: Each basic block and edge can be split into 3 489 edges. Number of balance edges = n_basic_blocks. So after 490 create_fixup_graph: 491 max_edges = 4 * n_basic_blocks + 3 * n_edges 492 Accounting for residual flow edges 493 max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges) 494 = 8 * n_basic_blocks + 6 * n_edges 495 < 8 * n_basic_blocks + 8 * n_edges. */ 496 int fmax_num_edges = 8 * (n_basic_blocks + n_edges); 497 498 /* Initial num of vertices in the fixup graph. */ 499 fixup_graph->num_vertices = n_basic_blocks; 500 501 /* Fixup graph vertex list. */ 502 fixup_graph->vertex_list = 503 (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type)); 504 505 /* Fixup graph edge list. */ 506 fixup_graph->edge_list = 507 (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type)); 508 509 diff_out_in = 510 (gcov_type *) xcalloc (1 + fnum_vertices_after_transform, 511 sizeof (gcov_type)); 512 513 /* Compute constants b, k_pos, k_neg used in the cost function calculation. 514 b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b. */ 515 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 516 total_vertex_weight += bb->count; 517 518 sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / n_basic_blocks); 519 520 k_pos = K_POS (sqrt_avg_vertex_weight); 521 k_neg = K_NEG (sqrt_avg_vertex_weight); 522 523 /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'', 524 connected by an edge e from v' to v''. w(e) = w(v). */ 525 526 if (dump_file) 527 fprintf (dump_file, "\nVertex transformation:\n"); 528 529 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 530 { 531 /* v'->v'': index1->(index1+1). */ 532 i = 2 * bb->index; 533 fcost = (gcov_type) COST (k_pos, bb->count); 534 add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count, 535 fcost, CAP_INFINITY); 536 fixup_graph->num_vertices++; 537 538 FOR_EACH_EDGE (e, ei, bb->succs) 539 { 540 /* Edges with ignore attribute set should be treated like they don't 541 exist. */ 542 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) 543 continue; 544 j = 2 * e->dest->index; 545 fcost = (gcov_type) COST (k_pos, e->count); 546 add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost, 547 CAP_INFINITY); 548 } 549 } 550 551 /* After vertex transformation. */ 552 gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform); 553 /* Redirect edges are not added for edges with ignore attribute. */ 554 gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform); 555 556 fnum_edges_after_transform = fixup_graph->num_edges; 557 558 /* 2. Initialize D(v). */ 559 for (i = 0; i < fnum_edges_after_transform; i++) 560 { 561 pfedge = fixup_graph->edge_list + i; 562 diff_out_in[pfedge->src] += pfedge->weight; 563 diff_out_in[pfedge->dest] -= pfedge->weight; 564 } 565 566 /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3. */ 567 for (i = 0; i <= 3; i++) 568 diff_out_in[i] = 0; 569 570 /* 3. Add reverse edges: needed to decrease counts during smoothing. */ 571 if (dump_file) 572 fprintf (dump_file, "\nReverse edges:\n"); 573 for (i = 0; i < fnum_edges_after_transform; i++) 574 { 575 pfedge = fixup_graph->edge_list + i; 576 if ((pfedge->src == 0) || (pfedge->src == 2)) 577 continue; 578 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src); 579 if (!r_pfedge && pfedge->weight) 580 { 581 /* Skip adding reverse edges for edges with w(e) = 0, as its maximum 582 capacity is 0. */ 583 fcost = (gcov_type) COST (k_neg, pfedge->weight); 584 add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src, 585 REVERSE_EDGE, 0, fcost, pfedge->weight); 586 } 587 } 588 589 /* 4. Create single source and sink. Connect new source vertex s' to function 590 entry block. Connect sink vertex t' to function exit. */ 591 if (dump_file) 592 fprintf (dump_file, "\ns'->S, T->t':\n"); 593 594 new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices; 595 fixup_graph->num_vertices++; 596 /* Set supply_value to 1 to avoid zero count function ENTRY. */ 597 add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE, 598 1 /* supply_value */, 0, 1 /* supply_value */); 599 600 /* Create new exit with EXIT_BLOCK as single pred. */ 601 new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices; 602 fixup_graph->num_vertices++; 603 add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index, 604 SINK_CONNECT_EDGE, 605 0 /* demand_value */, 0, 0 /* demand_value */); 606 607 /* Connect vertices with unbalanced D(v) to source/sink. */ 608 if (dump_file) 609 fprintf (dump_file, "\nD(v) balance:\n"); 610 /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4. 611 diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2. */ 612 for (i = 4; i < new_entry_index; i += 2) 613 { 614 if (diff_out_in[i] > 0) 615 { 616 add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0, 617 diff_out_in[i]); 618 demand_value += diff_out_in[i]; 619 } 620 else if (diff_out_in[i] < 0) 621 { 622 add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0, 623 -diff_out_in[i]); 624 supply_value -= diff_out_in[i]; 625 } 626 } 627 628 /* Set supply = demand. */ 629 if (dump_file) 630 { 631 fprintf (dump_file, "\nAdjust supply and demand:\n"); 632 fprintf (dump_file, "supply_value=" HOST_WIDEST_INT_PRINT_DEC "\n", 633 supply_value); 634 fprintf (dump_file, "demand_value=" HOST_WIDEST_INT_PRINT_DEC "\n", 635 demand_value); 636 } 637 638 if (demand_value > supply_value) 639 { 640 pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK); 641 pfedge->max_capacity += (demand_value - supply_value); 642 } 643 else 644 { 645 pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index); 646 pfedge->max_capacity += (supply_value - demand_value); 647 } 648 649 /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are 650 created by the vertex transformation step from self-edges in the original 651 CFG and by the reverse edges added earlier. */ 652 if (dump_file) 653 fprintf (dump_file, "\nNormalize edges:\n"); 654 655 fnum_edges = fixup_graph->num_edges; 656 fedge_list = fixup_graph->edge_list; 657 658 for (i = 0; i < fnum_edges; i++) 659 { 660 pfedge = fedge_list + i; 661 r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src); 662 if (((pfedge->type == VERTEX_SPLIT_EDGE) 663 || (pfedge->type == REDIRECT_EDGE)) && r_pfedge) 664 { 665 new_index = fixup_graph->num_vertices; 666 fixup_graph->num_vertices++; 667 668 if (dump_file) 669 { 670 fprintf (dump_file, "\nAnti-parallel edge:\n"); 671 dump_fixup_edge (dump_file, fixup_graph, pfedge); 672 dump_fixup_edge (dump_file, fixup_graph, r_pfedge); 673 fprintf (dump_file, "New vertex is %d.\n", new_index); 674 fprintf (dump_file, "------------------\n"); 675 } 676 677 pfedge->cost /= 2; 678 pfedge->norm_vertex_index = new_index; 679 if (dump_file) 680 { 681 fprintf (dump_file, "After normalization:\n"); 682 dump_fixup_edge (dump_file, fixup_graph, pfedge); 683 } 684 685 /* Add a new fixup edge: new_index->src. */ 686 add_fixup_edge (fixup_graph, new_index, pfedge->src, 687 REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost, 688 r_pfedge->max_capacity); 689 gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices); 690 691 /* Edge: r_pfedge->src -> r_pfedge->dest 692 ==> r_pfedge->src -> new_index. */ 693 r_pfedge->dest = new_index; 694 r_pfedge->type = REVERSE_NORMALIZED_EDGE; 695 r_pfedge->cost = pfedge->cost; 696 r_pfedge->max_capacity = pfedge->max_capacity; 697 if (dump_file) 698 dump_fixup_edge (dump_file, fixup_graph, r_pfedge); 699 } 700 } 701 702 if (dump_file) 703 dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()"); 704 705 /* Cleanup. */ 706 free (diff_out_in); 707 } 708 709 710 /* Allocates space for the structures in AUGMENTING_PATH. The space needed is 711 proportional to the number of nodes in the graph, which is given by 712 GRAPH_SIZE. */ 713 714 static void 715 init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size) 716 { 717 augmenting_path->queue_list.queue = (int *) 718 xcalloc (graph_size + 2, sizeof (int)); 719 augmenting_path->queue_list.size = graph_size + 2; 720 augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int)); 721 augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int)); 722 } 723 724 /* Free the structures in AUGMENTING_PATH. */ 725 static void 726 free_augmenting_path (augmenting_path_type *augmenting_path) 727 { 728 free (augmenting_path->queue_list.queue); 729 free (augmenting_path->bb_pred); 730 free (augmenting_path->is_visited); 731 } 732 733 734 /* Queue routines. Assumes queue will never overflow. */ 735 736 static void 737 init_queue (queue_type *queue_list) 738 { 739 gcc_assert (queue_list); 740 queue_list->head = 0; 741 queue_list->tail = 0; 742 } 743 744 /* Return true if QUEUE_LIST is empty. */ 745 static bool 746 is_empty (queue_type *queue_list) 747 { 748 return (queue_list->head == queue_list->tail); 749 } 750 751 /* Insert element X into QUEUE_LIST. */ 752 static void 753 enqueue (queue_type *queue_list, int x) 754 { 755 gcc_assert (queue_list->tail < queue_list->size); 756 queue_list->queue[queue_list->tail] = x; 757 (queue_list->tail)++; 758 } 759 760 /* Return the first element in QUEUE_LIST. */ 761 static int 762 dequeue (queue_type *queue_list) 763 { 764 int x; 765 gcc_assert (queue_list->head >= 0); 766 x = queue_list->queue[queue_list->head]; 767 (queue_list->head)++; 768 return x; 769 } 770 771 772 /* Finds a negative cycle in the residual network using 773 the Bellman-Ford algorithm. The flow on the found cycle is reversed by the 774 minimum residual capacity of that cycle. ENTRY and EXIT vertices are not 775 considered. 776 777 Parameters: 778 FIXUP_GRAPH - Residual graph (input/output) 779 The following are allocated/freed by the caller: 780 PI - Vector to hold predecessors in path (pi = pred index) 781 D - D[I] holds minimum cost of path from i to sink 782 CYCLE - Vector to hold the minimum cost cycle 783 784 Return: 785 true if a negative cycle was found, false otherwise. */ 786 787 static bool 788 cancel_negative_cycle (fixup_graph_type *fixup_graph, 789 int *pi, gcov_type *d, int *cycle) 790 { 791 int i, j, k; 792 int fnum_vertices, fnum_edges; 793 fixup_edge_p fedge_list, pfedge, r_pfedge; 794 bool found_cycle = false; 795 int cycle_start = 0, cycle_end = 0; 796 gcov_type sum_cost = 0, cycle_flow = 0; 797 int new_entry_index; 798 bool propagated = false; 799 800 gcc_assert (fixup_graph); 801 fnum_vertices = fixup_graph->num_vertices; 802 fnum_edges = fixup_graph->num_edges; 803 fedge_list = fixup_graph->edge_list; 804 new_entry_index = fixup_graph->new_entry_index; 805 806 /* Initialize. */ 807 /* Skip ENTRY. */ 808 for (i = 1; i < fnum_vertices; i++) 809 { 810 d[i] = CAP_INFINITY; 811 pi[i] = -1; 812 cycle[i] = -1; 813 } 814 d[ENTRY_BLOCK] = 0; 815 816 /* Relax. */ 817 for (k = 1; k < fnum_vertices; k++) 818 { 819 propagated = false; 820 for (i = 0; i < fnum_edges; i++) 821 { 822 pfedge = fedge_list + i; 823 if (pfedge->src == new_entry_index) 824 continue; 825 if (pfedge->is_rflow_valid && pfedge->rflow 826 && d[pfedge->src] != CAP_INFINITY 827 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost)) 828 { 829 d[pfedge->dest] = d[pfedge->src] + pfedge->cost; 830 pi[pfedge->dest] = pfedge->src; 831 propagated = true; 832 } 833 } 834 if (!propagated) 835 break; 836 } 837 838 if (!propagated) 839 /* No negative cycles exist. */ 840 return 0; 841 842 /* Detect. */ 843 for (i = 0; i < fnum_edges; i++) 844 { 845 pfedge = fedge_list + i; 846 if (pfedge->src == new_entry_index) 847 continue; 848 if (pfedge->is_rflow_valid && pfedge->rflow 849 && d[pfedge->src] != CAP_INFINITY 850 && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost)) 851 { 852 found_cycle = true; 853 break; 854 } 855 } 856 857 if (!found_cycle) 858 return 0; 859 860 /* Augment the cycle with the cycle's minimum residual capacity. */ 861 found_cycle = false; 862 cycle[0] = pfedge->dest; 863 j = pfedge->dest; 864 865 for (i = 1; i < fnum_vertices; i++) 866 { 867 j = pi[j]; 868 cycle[i] = j; 869 for (k = 0; k < i; k++) 870 { 871 if (cycle[k] == j) 872 { 873 /* cycle[k] -> ... -> cycle[i]. */ 874 cycle_start = k; 875 cycle_end = i; 876 found_cycle = true; 877 break; 878 } 879 } 880 if (found_cycle) 881 break; 882 } 883 884 gcc_assert (cycle[cycle_start] == cycle[cycle_end]); 885 if (dump_file) 886 fprintf (dump_file, "\nNegative cycle length is %d:\n", 887 cycle_end - cycle_start); 888 889 sum_cost = 0; 890 cycle_flow = CAP_INFINITY; 891 for (k = cycle_start; k < cycle_end; k++) 892 { 893 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]); 894 cycle_flow = MIN (cycle_flow, pfedge->rflow); 895 sum_cost += pfedge->cost; 896 if (dump_file) 897 fprintf (dump_file, "%d ", cycle[k]); 898 } 899 900 if (dump_file) 901 { 902 fprintf (dump_file, "%d", cycle[k]); 903 fprintf (dump_file, 904 ": (" HOST_WIDEST_INT_PRINT_DEC ", " HOST_WIDEST_INT_PRINT_DEC 905 ")\n", sum_cost, cycle_flow); 906 fprintf (dump_file, 907 "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC "\n", 908 cycle_flow); 909 } 910 911 for (k = cycle_start; k < cycle_end; k++) 912 { 913 pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]); 914 r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]); 915 pfedge->rflow -= cycle_flow; 916 if (pfedge->type) 917 pfedge->flow += cycle_flow; 918 r_pfedge->rflow += cycle_flow; 919 if (r_pfedge->type) 920 r_pfedge->flow -= cycle_flow; 921 } 922 923 return true; 924 } 925 926 927 /* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of 928 the edges. ENTRY and EXIT vertices should not be considered. */ 929 930 static void 931 compute_residual_flow (fixup_graph_type *fixup_graph) 932 { 933 int i; 934 int fnum_edges; 935 fixup_edge_p fedge_list, pfedge; 936 937 gcc_assert (fixup_graph); 938 939 if (dump_file) 940 fputs ("\ncompute_residual_flow():\n", dump_file); 941 942 fnum_edges = fixup_graph->num_edges; 943 fedge_list = fixup_graph->edge_list; 944 945 for (i = 0; i < fnum_edges; i++) 946 { 947 pfedge = fedge_list + i; 948 pfedge->rflow = pfedge->max_capacity - pfedge->flow; 949 pfedge->is_rflow_valid = true; 950 add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow, 951 -pfedge->cost); 952 } 953 } 954 955 956 /* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to 957 SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by 958 this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated 959 to reflect the path found. 960 Returns: 0 if no augmenting path is found, 1 otherwise. */ 961 962 static int 963 find_augmenting_path (fixup_graph_type *fixup_graph, 964 augmenting_path_type *augmenting_path, int source, 965 int sink) 966 { 967 int u = 0; 968 int i; 969 fixup_vertex_p fvertex_list, pfvertex; 970 fixup_edge_p pfedge; 971 int *bb_pred, *is_visited; 972 queue_type *queue_list; 973 974 gcc_assert (augmenting_path); 975 bb_pred = augmenting_path->bb_pred; 976 gcc_assert (bb_pred); 977 is_visited = augmenting_path->is_visited; 978 gcc_assert (is_visited); 979 queue_list = &(augmenting_path->queue_list); 980 981 gcc_assert (fixup_graph); 982 983 fvertex_list = fixup_graph->vertex_list; 984 985 for (u = 0; u < fixup_graph->num_vertices; u++) 986 is_visited[u] = 0; 987 988 init_queue (queue_list); 989 enqueue (queue_list, source); 990 bb_pred[source] = -1; 991 992 while (!is_empty (queue_list)) 993 { 994 u = dequeue (queue_list); 995 is_visited[u] = 1; 996 pfvertex = fvertex_list + u; 997 for (i = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, i, pfedge); 998 i++) 999 { 1000 int dest = pfedge->dest; 1001 if ((pfedge->rflow > 0) && (is_visited[dest] == 0)) 1002 { 1003 enqueue (queue_list, dest); 1004 bb_pred[dest] = u; 1005 is_visited[dest] = 1; 1006 if (dest == sink) 1007 return 1; 1008 } 1009 } 1010 } 1011 1012 return 0; 1013 } 1014 1015 1016 /* Routine to find the maximal flow: 1017 Algorithm: 1018 1. Initialize flow to 0 1019 2. Find an augmenting path form source to sink. 1020 3. Send flow equal to the path's residual capacity along the edges of this path. 1021 4. Repeat steps 2 and 3 until no new augmenting path is found. 1022 1023 Parameters: 1024 SOURCE: index of source vertex (input) 1025 SINK: index of sink vertex (input) 1026 FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be 1027 set to have a valid maximal flow by this routine. (input) 1028 Return: Maximum flow possible. */ 1029 1030 static gcov_type 1031 find_max_flow (fixup_graph_type *fixup_graph, int source, int sink) 1032 { 1033 int fnum_edges; 1034 augmenting_path_type augmenting_path; 1035 int *bb_pred; 1036 gcov_type max_flow = 0; 1037 int i, u; 1038 fixup_edge_p fedge_list, pfedge, r_pfedge; 1039 1040 gcc_assert (fixup_graph); 1041 1042 fnum_edges = fixup_graph->num_edges; 1043 fedge_list = fixup_graph->edge_list; 1044 1045 /* Initialize flow to 0. */ 1046 for (i = 0; i < fnum_edges; i++) 1047 { 1048 pfedge = fedge_list + i; 1049 pfedge->flow = 0; 1050 } 1051 1052 compute_residual_flow (fixup_graph); 1053 1054 init_augmenting_path (&augmenting_path, fixup_graph->num_vertices); 1055 1056 bb_pred = augmenting_path.bb_pred; 1057 while (find_augmenting_path (fixup_graph, &augmenting_path, source, sink)) 1058 { 1059 /* Determine the amount by which we can increment the flow. */ 1060 gcov_type increment = CAP_INFINITY; 1061 for (u = sink; u != source; u = bb_pred[u]) 1062 { 1063 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u); 1064 increment = MIN (increment, pfedge->rflow); 1065 } 1066 max_flow += increment; 1067 1068 /* Now increment the flow. EXIT vertex index is 1. */ 1069 for (u = sink; u != source; u = bb_pred[u]) 1070 { 1071 pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u); 1072 r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]); 1073 if (pfedge->type) 1074 { 1075 /* forward edge. */ 1076 pfedge->flow += increment; 1077 pfedge->rflow -= increment; 1078 r_pfedge->rflow += increment; 1079 } 1080 else 1081 { 1082 /* backward edge. */ 1083 gcc_assert (r_pfedge->type); 1084 r_pfedge->rflow += increment; 1085 r_pfedge->flow -= increment; 1086 pfedge->rflow -= increment; 1087 } 1088 } 1089 1090 if (dump_file) 1091 { 1092 fprintf (dump_file, "\nDump augmenting path:\n"); 1093 for (u = sink; u != source; u = bb_pred[u]) 1094 { 1095 print_basic_block (dump_file, fixup_graph, u); 1096 fprintf (dump_file, "<-"); 1097 } 1098 fprintf (dump_file, 1099 "ENTRY (path_capacity=" HOST_WIDEST_INT_PRINT_DEC ")\n", 1100 increment); 1101 fprintf (dump_file, 1102 "Network flow is " HOST_WIDEST_INT_PRINT_DEC ".\n", 1103 max_flow); 1104 } 1105 } 1106 1107 free_augmenting_path (&augmenting_path); 1108 if (dump_file) 1109 dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()"); 1110 return max_flow; 1111 } 1112 1113 1114 /* Computes the corrected edge and basic block weights using FIXUP_GRAPH 1115 after applying the find_minimum_cost_flow() routine. */ 1116 1117 static void 1118 adjust_cfg_counts (fixup_graph_type *fixup_graph) 1119 { 1120 basic_block bb; 1121 edge e; 1122 edge_iterator ei; 1123 int i, j; 1124 fixup_edge_p pfedge, pfedge_n; 1125 1126 gcc_assert (fixup_graph); 1127 1128 if (dump_file) 1129 fprintf (dump_file, "\nadjust_cfg_counts():\n"); 1130 1131 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 1132 { 1133 i = 2 * bb->index; 1134 1135 /* Fixup BB. */ 1136 if (dump_file) 1137 fprintf (dump_file, 1138 "BB%d: " HOST_WIDEST_INT_PRINT_DEC "", bb->index, bb->count); 1139 1140 pfedge = find_fixup_edge (fixup_graph, i, i + 1); 1141 if (pfedge->flow) 1142 { 1143 bb->count += pfedge->flow; 1144 if (dump_file) 1145 { 1146 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(", 1147 pfedge->flow); 1148 print_edge (dump_file, fixup_graph, i, i + 1); 1149 fprintf (dump_file, ")"); 1150 } 1151 } 1152 1153 pfedge_n = 1154 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index); 1155 /* Deduct flow from normalized reverse edge. */ 1156 if (pfedge->norm_vertex_index && pfedge_n->flow) 1157 { 1158 bb->count -= pfedge_n->flow; 1159 if (dump_file) 1160 { 1161 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(", 1162 pfedge_n->flow); 1163 print_edge (dump_file, fixup_graph, i + 1, 1164 pfedge->norm_vertex_index); 1165 fprintf (dump_file, ")"); 1166 } 1167 } 1168 if (dump_file) 1169 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\n", bb->count); 1170 1171 /* Fixup edge. */ 1172 FOR_EACH_EDGE (e, ei, bb->succs) 1173 { 1174 /* Treat edges with ignore attribute set as if they don't exist. */ 1175 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) 1176 continue; 1177 1178 j = 2 * e->dest->index; 1179 if (dump_file) 1180 fprintf (dump_file, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC "", 1181 bb->index, e->dest->index, e->count); 1182 1183 pfedge = find_fixup_edge (fixup_graph, i + 1, j); 1184 1185 if (bb->index != e->dest->index) 1186 { 1187 /* Non-self edge. */ 1188 if (pfedge->flow) 1189 { 1190 e->count += pfedge->flow; 1191 if (dump_file) 1192 { 1193 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(", 1194 pfedge->flow); 1195 print_edge (dump_file, fixup_graph, i + 1, j); 1196 fprintf (dump_file, ")"); 1197 } 1198 } 1199 1200 pfedge_n = 1201 find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index); 1202 /* Deduct flow from normalized reverse edge. */ 1203 if (pfedge->norm_vertex_index && pfedge_n->flow) 1204 { 1205 e->count -= pfedge_n->flow; 1206 if (dump_file) 1207 { 1208 fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(", 1209 pfedge_n->flow); 1210 print_edge (dump_file, fixup_graph, j, 1211 pfedge->norm_vertex_index); 1212 fprintf (dump_file, ")"); 1213 } 1214 } 1215 } 1216 else 1217 { 1218 /* Handle self edges. Self edge is split with a normalization 1219 vertex. Here i=j. */ 1220 pfedge = find_fixup_edge (fixup_graph, j, i + 1); 1221 pfedge_n = 1222 find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index); 1223 e->count += pfedge_n->flow; 1224 bb->count += pfedge_n->flow; 1225 if (dump_file) 1226 { 1227 fprintf (dump_file, "(self edge)"); 1228 fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(", 1229 pfedge_n->flow); 1230 print_edge (dump_file, fixup_graph, i + 1, 1231 pfedge->norm_vertex_index); 1232 fprintf (dump_file, ")"); 1233 } 1234 } 1235 1236 if (bb->count) 1237 e->probability = REG_BR_PROB_BASE * e->count / bb->count; 1238 if (dump_file) 1239 fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\t(%.1f%%)\n", 1240 e->count, e->probability * 100.0 / REG_BR_PROB_BASE); 1241 } 1242 } 1243 1244 ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs); 1245 EXIT_BLOCK_PTR->count = sum_edge_counts (EXIT_BLOCK_PTR->preds); 1246 1247 /* Compute edge probabilities. */ 1248 FOR_ALL_BB (bb) 1249 { 1250 if (bb->count) 1251 { 1252 FOR_EACH_EDGE (e, ei, bb->succs) 1253 e->probability = REG_BR_PROB_BASE * e->count / bb->count; 1254 } 1255 else 1256 { 1257 int total = 0; 1258 FOR_EACH_EDGE (e, ei, bb->succs) 1259 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 1260 total++; 1261 if (total) 1262 { 1263 FOR_EACH_EDGE (e, ei, bb->succs) 1264 { 1265 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 1266 e->probability = REG_BR_PROB_BASE / total; 1267 else 1268 e->probability = 0; 1269 } 1270 } 1271 else 1272 { 1273 total += EDGE_COUNT (bb->succs); 1274 FOR_EACH_EDGE (e, ei, bb->succs) 1275 e->probability = REG_BR_PROB_BASE / total; 1276 } 1277 } 1278 } 1279 1280 if (dump_file) 1281 { 1282 fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n", 1283 lang_hooks.decl_printable_name (current_function_decl, 2)); 1284 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb) 1285 { 1286 if ((bb->count != sum_edge_counts (bb->preds)) 1287 || (bb->count != sum_edge_counts (bb->succs))) 1288 { 1289 fprintf (dump_file, 1290 "BB%d(" HOST_WIDEST_INT_PRINT_DEC ") **INVALID**: ", 1291 bb->index, bb->count); 1292 fprintf (stderr, 1293 "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC 1294 ") **INVALID**: \n", bb->index, bb->count); 1295 fprintf (dump_file, "in_edges=" HOST_WIDEST_INT_PRINT_DEC " ", 1296 sum_edge_counts (bb->preds)); 1297 fprintf (dump_file, "out_edges=" HOST_WIDEST_INT_PRINT_DEC "\n", 1298 sum_edge_counts (bb->succs)); 1299 } 1300 } 1301 } 1302 } 1303 1304 1305 /* Implements the negative cycle canceling algorithm to compute a minimum cost 1306 flow. 1307 Algorithm: 1308 1. Find maximal flow. 1309 2. Form residual network 1310 3. Repeat: 1311 While G contains a negative cost cycle C, reverse the flow on the found cycle 1312 by the minimum residual capacity in that cycle. 1313 4. Form the minimal cost flow 1314 f(u,v) = rf(v, u) 1315 Input: 1316 FIXUP_GRAPH - Initial fixup graph. 1317 The flow field is modified to represent the minimum cost flow. */ 1318 1319 static void 1320 find_minimum_cost_flow (fixup_graph_type *fixup_graph) 1321 { 1322 /* Holds the index of predecessor in path. */ 1323 int *pred; 1324 /* Used to hold the minimum cost cycle. */ 1325 int *cycle; 1326 /* Used to record the number of iterations of cancel_negative_cycle. */ 1327 int iteration; 1328 /* Vector d[i] holds the minimum cost of path from i to sink. */ 1329 gcov_type *d; 1330 int fnum_vertices; 1331 int new_exit_index; 1332 int new_entry_index; 1333 1334 gcc_assert (fixup_graph); 1335 fnum_vertices = fixup_graph->num_vertices; 1336 new_exit_index = fixup_graph->new_exit_index; 1337 new_entry_index = fixup_graph->new_entry_index; 1338 1339 find_max_flow (fixup_graph, new_entry_index, new_exit_index); 1340 1341 /* Initialize the structures for find_negative_cycle(). */ 1342 pred = (int *) xcalloc (fnum_vertices, sizeof (int)); 1343 d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type)); 1344 cycle = (int *) xcalloc (fnum_vertices, sizeof (int)); 1345 1346 /* Repeatedly find and cancel negative cost cycles, until 1347 no more negative cycles exist. This also updates the flow field 1348 to represent the minimum cost flow so far. */ 1349 iteration = 0; 1350 while (cancel_negative_cycle (fixup_graph, pred, d, cycle)) 1351 { 1352 iteration++; 1353 if (iteration > MAX_ITER (fixup_graph->num_vertices, 1354 fixup_graph->num_edges)) 1355 break; 1356 } 1357 1358 if (dump_file) 1359 dump_fixup_graph (dump_file, fixup_graph, 1360 "After find_minimum_cost_flow()"); 1361 1362 /* Cleanup structures. */ 1363 free (pred); 1364 free (d); 1365 free (cycle); 1366 } 1367 1368 1369 /* Compute the sum of the edge counts in TO_EDGES. */ 1370 1371 gcov_type 1372 sum_edge_counts (VEC (edge, gc) *to_edges) 1373 { 1374 gcov_type sum = 0; 1375 edge e; 1376 edge_iterator ei; 1377 1378 FOR_EACH_EDGE (e, ei, to_edges) 1379 { 1380 if (EDGE_INFO (e) && EDGE_INFO (e)->ignore) 1381 continue; 1382 sum += e->count; 1383 } 1384 return sum; 1385 } 1386 1387 1388 /* Main routine. Smoothes the intial assigned basic block and edge counts using 1389 a minimum cost flow algorithm, to ensure that the flow consistency rule is 1390 obeyed: sum of outgoing edges = sum of incoming edges for each basic 1391 block. */ 1392 1393 void 1394 mcf_smooth_cfg (void) 1395 { 1396 fixup_graph_type fixup_graph; 1397 memset (&fixup_graph, 0, sizeof (fixup_graph)); 1398 create_fixup_graph (&fixup_graph); 1399 find_minimum_cost_flow (&fixup_graph); 1400 adjust_cfg_counts (&fixup_graph); 1401 delete_fixup_graph (&fixup_graph); 1402 } 1403