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