gcc/mcf.c

   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 }