2008-08-18 H.J. Lu <hongjiu.lu@intel.com>

	* mcf.c: Really add it.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@139209 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1401 insertions, 0 deletions

diff --git a/gcc/mcf.c b/gcc/mcf.c
new file mode 100644
index 00000000000..d7bc5f30e72
--- /dev/null
+++ b/gcc/mcf.c
@@ -0,0 +1,1401 @@
+/* Routines to implement minimum-cost maximal flow algorithm used to smooth
+   basic block and edge frequency counts.
+   Copyright (C) 2008
+   Free Software Foundation, Inc.
+   Contributed by Paul Yuan (yingbo.com@gmail.com) and
+                  Vinodha Ramasamy (vinodha@google.com).
+
+This file is part of GCC.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* References:
+   [1] "Feedback-directed Optimizations in GCC with Estimated Edge Profiles
+        from Hardware Event Sampling", Vinodha Ramasamy, Paul Yuan, Dehao Chen,
+        and Robert Hundt; GCC Summit 2008.
+   [2] "Complementing Missing and Inaccurate Profiling Using a Minimum Cost
+        Circulation Algorithm", Roy Levin, Ilan Newman and Gadi Haber;
+        HiPEAC '08.
+
+   Algorithm to smooth basic block and edge counts:
+   1. create_fixup_graph: Create fixup graph by translating function CFG into
+      a graph that satisfies MCF algorithm requirements.
+   2. find_max_flow: Find maximal flow.
+   3. compute_residual_flow: Form residual network.
+   4. Repeat:
+      cancel_negative_cycle: While G contains a negative cost cycle C, reverse
+      the flow on the found cycle by the minimum residual capacity in that
+      cycle.
+   5. Form the minimal cost flow
+      f(u,v) = rf(v, u).
+   6. adjust_cfg_counts: Update initial edge weights with corrected weights.
+      delta(u.v) = f(u,v) -f(v,u).
+      w*(u,v) = w(u,v) + delta(u,v).  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "basic-block.h"
+#include "output.h"
+#include "langhooks.h"
+#include "tree.h"
+#include "gcov-io.h"
+
+#include "profile.h"
+
+/* CAP_INFINITY: Constant to represent infinite capacity.  */
+#define CAP_INFINITY __LONG_LONG_MAX__
+
+/* COST FUNCTION.  */
+#define K_POS(b)        ((b))
+#define K_NEG(b)        (50 * (b))
+#define COST(k, w)      ((k) / mcf_ln ((w) + 2))
+/* Limit the number of iterations for cancel_negative_cycles() to ensure
+   reasonable compile time.  */
+#define MAX_ITER(n, e)  10 + (1000000 / ((n) * (e)))
+typedef enum
+{
+  INVALID_EDGE,
+  VERTEX_SPLIT_EDGE,	    /* Edge to represent vertex with w(e) = w(v).  */
+  REDIRECT_EDGE,	    /* Edge after vertex transformation.  */
+  REVERSE_EDGE,
+  SOURCE_CONNECT_EDGE,	    /* Single edge connecting to single source.  */
+  SINK_CONNECT_EDGE,	    /* Single edge connecting to single sink.  */
+  BALANCE_EDGE,		    /* Edge connecting with source/sink: cp(e) = 0.  */
+  REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge.  */
+  REVERSE_NORMALIZED_EDGE   /* Normalized edge for a reverse edge.  */
+} edge_type;
+
+/* Structure to represent an edge in the fixup graph.  */
+typedef struct fixup_edge_d
+{
+  int src;
+  int dest;
+  /* Flag denoting type of edge and attributes for the flow field.  */
+  edge_type type;
+  bool is_rflow_valid;
+  /* Index to the normalization vertex added for this edge.  */
+  int norm_vertex_index;
+  /* Flow for this edge.  */
+  gcov_type flow;
+  /* Residual flow for this edge - used during negative cycle canceling.  */
+  gcov_type rflow;
+  gcov_type weight;
+  gcov_type cost;
+  gcov_type max_capacity;
+} fixup_edge_type;
+
+typedef fixup_edge_type *fixup_edge_p;
+
+DEF_VEC_P (fixup_edge_p);
+DEF_VEC_ALLOC_P (fixup_edge_p, heap);
+
+/* Structure to represent a vertex in the fixup graph.  */
+typedef struct fixup_vertex_d
+{
+  VEC (fixup_edge_p, heap) *succ_edges;
+} fixup_vertex_type;
+
+typedef fixup_vertex_type *fixup_vertex_p;
+
+/* Fixup graph used in the MCF algorithm.  */
+typedef struct fixup_graph_d
+{
+  /* Current number of vertices for the graph.  */
+  int num_vertices;
+  /* Current number of edges for the graph.  */
+  int num_edges;
+  /* Index of new entry vertex.  */
+  int new_entry_index;
+  /* Index of new exit vertex.  */
+  int new_exit_index;
+  /* Fixup vertex list. Adjacency list for fixup graph.  */
+  fixup_vertex_p vertex_list;
+  /* Fixup edge list.  */
+  fixup_edge_p edge_list;
+} fixup_graph_type;
+
+typedef struct queue_d
+{
+  int *queue;
+  int head;
+  int tail;
+  int size;
+} queue_type;
+
+/* Structure used in the maximal flow routines to find augmenting path.  */
+typedef struct augmenting_path_d
+{
+  /* Queue used to hold vertex indices.  */
+  queue_type queue_list;
+  /* Vector to hold chain of pred vertex indices in augmenting path.  */
+  int *bb_pred;
+  /* Vector that indicates if basic block i has been visited.  */
+  int *is_visited;
+} augmenting_path_type;
+
+
+/* Function definitions.  */
+
+/* Dump routines to aid debugging.  */
+
+/* Print basic block with index N for FIXUP_GRAPH in n' and n'' format.  */
+
+static void
+print_basic_block (FILE *file, fixup_graph_type *fixup_graph, int n)
+{
+  if (n == ENTRY_BLOCK)
+    fputs ("ENTRY", file);
+  else if (n == ENTRY_BLOCK + 1)
+    fputs ("ENTRY''", file);
+  else if (n == 2 * EXIT_BLOCK)
+    fputs ("EXIT", file);
+  else if (n == 2 * EXIT_BLOCK + 1)
+    fputs ("EXIT''", file);
+  else if (n == fixup_graph->new_exit_index)
+    fputs ("NEW_EXIT", file);
+  else if (n == fixup_graph->new_entry_index)
+    fputs ("NEW_ENTRY", file);
+  else
+    {
+      fprintf (file, "%d", n / 2);
+      if (n % 2)
+	fputs ("''", file);
+      else
+	fputs ("'", file);
+    }
+}
+
+
+/* Print edge S->D for given fixup_graph with n' and n'' format.
+   PARAMETERS:
+   S is the index of the source vertex of the edge (input) and
+   D is the index of the destination vertex of the edge (input) for the given
+   fixup_graph (input).  */
+
+static void
+print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d)
+{
+  print_basic_block (file, fixup_graph, s);
+  fputs ("->", file);
+  print_basic_block (file, fixup_graph, d);
+}
+
+
+/* Dump out the attributes of a given edge FEDGE in the fixup_graph to a
+   file.  */
+static void
+dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge)
+{
+  if (!fedge)
+    {
+      fputs ("NULL fixup graph edge.\n", file);
+      return;
+    }
+
+  print_edge (file, fixup_graph, fedge->src, fedge->dest);
+  fputs (": ", file);
+
+  if (fedge->type)
+    {
+      fprintf (file, "flow/capacity=" HOST_WIDEST_INT_PRINT_DEC "/",
+	       fedge->flow);
+      if (fedge->max_capacity == CAP_INFINITY)
+	fputs ("+oo,", file);
+      else
+	fprintf (file, "" HOST_WIDEST_INT_PRINT_DEC ",", fedge->max_capacity);
+    }
+
+  if (fedge->is_rflow_valid)
+    {
+      if (fedge->rflow == CAP_INFINITY)
+	fputs (" rflow=+oo.", file);
+      else
+	fprintf (file, " rflow=" HOST_WIDEST_INT_PRINT_DEC ",", fedge->rflow);
+    }
+
+  fprintf (file, " cost=" HOST_WIDEST_INT_PRINT_DEC ".", fedge->cost);
+
+  fprintf (file, "\t(%d->%d)", fedge->src, fedge->dest);
+
+  if (fedge->type)
+    {
+      switch (fedge->type)
+	{
+	case VERTEX_SPLIT_EDGE:
+	  fputs (" @VERTEX_SPLIT_EDGE", file);
+	  break;
+
+	case REDIRECT_EDGE:
+	  fputs (" @REDIRECT_EDGE", file);
+	  break;
+
+	case SOURCE_CONNECT_EDGE:
+	  fputs (" @SOURCE_CONNECT_EDGE", file);
+	  break;
+
+	case SINK_CONNECT_EDGE:
+	  fputs (" @SINK_CONNECT_EDGE", file);
+	  break;
+
+	case REVERSE_EDGE:
+	  fputs (" @REVERSE_EDGE", file);
+	  break;
+
+	case BALANCE_EDGE:
+	  fputs (" @BALANCE_EDGE", file);
+	  break;
+
+	case REDIRECT_NORMALIZED_EDGE:
+	case REVERSE_NORMALIZED_EDGE:
+	  fputs ("  @NORMALIZED_EDGE", file);
+	  break;
+
+	default:
+	  fputs (" @INVALID_EDGE", file);
+	  break;
+	}
+    }
+  fputs ("\n", file);
+}
+
+
+/* Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
+   file. The input string MSG is printed out as a heading.  */
+
+static void
+dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg)
+{
+  int i, j;
+  int fnum_vertices, fnum_edges;
+
+  fixup_vertex_p fvertex_list, pfvertex;
+  fixup_edge_p pfedge;
+
+  gcc_assert (fixup_graph);
+  fvertex_list = fixup_graph->vertex_list;
+  fnum_vertices = fixup_graph->num_vertices;
+  fnum_edges = fixup_graph->num_edges;
+
+  fprintf (file, "\nDump fixup graph for %s(): %s.\n",
+	   lang_hooks.decl_printable_name (current_function_decl, 2), msg);
+  fprintf (file,
+	   "There are %d vertices and %d edges. new_exit_index is %d.\n\n",
+	   fnum_vertices, fnum_edges, fixup_graph->new_exit_index);
+
+  for (i = 0; i < fnum_vertices; i++)
+    {
+      pfvertex = fvertex_list + i;
+      fprintf (file, "vertex_list[%d]: %d succ fixup edges.\n",
+	       i, VEC_length (fixup_edge_p, pfvertex->succ_edges));
+
+      for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge);
+	   j++)
+	{
+	  /* Distinguish forward edges and backward edges in the residual flow
+             network.  */
+	  if (pfedge->type)
+	    fputs ("(f) ", file);
+	  else if (pfedge->is_rflow_valid)
+	    fputs ("(b) ", file);
+	  dump_fixup_edge (file, fixup_graph, pfedge);
+	}
+    }
+
+  fputs ("\n", file);
+}
+
+
+/* Utility routines.  */
+/* ln() implementation: approximate calculation. Returns ln of X.  */
+
+static double
+mcf_ln (double x)
+{
+#define E       2.71828
+  int l = 1;
+  double m = E;
+
+  gcc_assert (x >= 0);
+
+  while (m < x)
+    {
+      m *= E;
+      l++;
+    }
+
+  return l;
+}
+
+
+/* sqrt() implementation: based on open source QUAKE3 code (magic sqrt
+   implementation) by John Carmack.  Returns sqrt of X.  */
+
+static double
+mcf_sqrt (double x)
+{
+#define MAGIC_CONST1    0x1fbcf800
+#define MAGIC_CONST2    0x5f3759df
+  union {
+    int intPart;
+    float floatPart;
+  } convertor, convertor2;
+
+  gcc_assert (x >= 0);
+
+  convertor.floatPart = x;
+  convertor2.floatPart = x;
+  convertor.intPart = MAGIC_CONST1 + (convertor.intPart >> 1);
+  convertor2.intPart = MAGIC_CONST2 - (convertor2.intPart >> 1);
+
+  return 0.5f * (convertor.floatPart + (x * convertor2.floatPart));
+}
+
+
+/* Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
+   (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
+   added set to COST.  */
+
+static fixup_edge_p
+add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost)
+{
+  fixup_vertex_p curr_vertex = fixup_graph->vertex_list + src;
+  fixup_edge_p curr_edge = fixup_graph->edge_list + fixup_graph->num_edges;
+  curr_edge->src = src;
+  curr_edge->dest = dest;
+  curr_edge->cost = cost;
+  fixup_graph->num_edges++;
+  if (dump_file)
+    dump_fixup_edge (dump_file, fixup_graph, curr_edge);
+  VEC_safe_push (fixup_edge_p, heap, curr_vertex->succ_edges, curr_edge);
+  return curr_edge;
+}
+
+
+/* Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
+   MAX_CAPACITY to the edge_list in the fixup graph.  */
+
+static void
+add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest, int type,
+		gcov_type weight, gcov_type cost, gcov_type max_capacity)
+{
+  fixup_edge_p curr_edge = add_edge(fixup_graph, src, dest, cost);
+  curr_edge->type = type;
+  curr_edge->weight = weight;
+  curr_edge->max_capacity = max_capacity;
+}
+
+
+/* Add a residual edge (SRC->DEST) with attributes RFLOW and COST
+   to the fixup graph.  */
+
+static void
+add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest,
+		 gcov_type rflow, gcov_type cost)
+{
+  fixup_edge_p curr_edge = add_edge (fixup_graph, src, dest, cost);
+  curr_edge->rflow = rflow;
+  curr_edge->is_rflow_valid = true;
+  /* This edge is not a valid edge - merely used to hold residual flow.  */
+  curr_edge->type = INVALID_EDGE;
+}
+
+
+/* Return the pointer to fixup edge SRC->DEST or NULL if edge does not
+   exist in the FIXUP_GRAPH.  */
+
+static fixup_edge_p
+find_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest)
+{
+  int j;
+  fixup_edge_p pfedge;
+  fixup_vertex_p pfvertex;
+
+  gcc_assert (src < fixup_graph->num_vertices);
+
+  pfvertex = fixup_graph->vertex_list + src;
+
+  for (j = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, j, pfedge);
+       j++)
+    if (pfedge->dest == dest)
+      return pfedge;
+
+  return NULL;
+}
+
+
+/* Cleanup routine to free structures in FIXUP_GRAPH.  */
+
+static void
+delete_fixup_graph (fixup_graph_type *fixup_graph)
+{
+  int i;
+  int fnum_vertices = fixup_graph->num_vertices;
+  fixup_vertex_p pfvertex = fixup_graph->vertex_list;
+
+  for (i = 0; i < fnum_vertices; i++, pfvertex++)
+    VEC_free (fixup_edge_p, heap, pfvertex->succ_edges);
+
+  free (fixup_graph->vertex_list);
+  free (fixup_graph->edge_list);
+}
+
+
+/* Creates a fixup graph FIXUP_GRAPH from the function CFG.  */
+
+static void
+create_fixup_graph (fixup_graph_type *fixup_graph)
+{
+  double sqrt_avg_vertex_weight = 0;
+  double total_vertex_weight = 0;
+  double k_pos = 0;
+  double k_neg = 0;
+  /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v).  */
+  gcov_type *diff_out_in = NULL;
+  gcov_type supply_value = 1, demand_value = 0;
+  gcov_type fcost = 0;
+  int new_entry_index = 0, new_exit_index = 0;
+  int i = 0, j = 0;
+  int new_index = 0;
+  basic_block bb;
+  edge e;
+  edge_iterator ei;
+  fixup_edge_p pfedge, r_pfedge;
+  fixup_edge_p fedge_list;
+  int fnum_edges;
+
+  /* Each basic_block will be split into 2 during vertex transformation.  */
+  int fnum_vertices_after_transform =  2 * n_basic_blocks;
+  int fnum_edges_after_transform = n_edges + n_basic_blocks;
+
+  /* Count the new SOURCE and EXIT vertices to be added.  */
+  int fmax_num_vertices =
+    fnum_vertices_after_transform + n_edges + n_basic_blocks + 2;
+
+  /* In create_fixup_graph: Each basic block and edge can be split into 3
+     edges. Number of balance edges = n_basic_blocks. So after
+     create_fixup_graph:
+     max_edges = 4 * n_basic_blocks + 3 * n_edges
+     Accounting for residual flow edges
+     max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
+     = 8 * n_basic_blocks + 6 * n_edges
+     < 8 * n_basic_blocks + 8 * n_edges.  */
+  int fmax_num_edges = 8 * (n_basic_blocks + n_edges);
+
+  /* Initial num of vertices in the fixup graph.  */
+  fixup_graph->num_vertices = n_basic_blocks;
+
+  /* Fixup graph vertex list.  */
+  fixup_graph->vertex_list =
+    (fixup_vertex_p) xcalloc (fmax_num_vertices, sizeof (fixup_vertex_type));
+
+  /* Fixup graph edge list.  */
+  fixup_graph->edge_list =
+    (fixup_edge_p) xcalloc (fmax_num_edges, sizeof (fixup_edge_type));
+
+  diff_out_in =
+    (gcov_type *) xcalloc (1 + fnum_vertices_after_transform,
+			   sizeof (gcov_type));
+
+  /* Compute constants b, k_pos, k_neg used in the cost function calculation.
+     b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b.  */
+  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+    total_vertex_weight += bb->count;
+
+  sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / n_basic_blocks);
+
+  k_pos = K_POS (sqrt_avg_vertex_weight);
+  k_neg = K_NEG (sqrt_avg_vertex_weight);
+
+  /* 1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
+     connected by an edge e from v' to v''. w(e) = w(v).  */
+
+  if (dump_file)
+    fprintf (dump_file, "\nVertex transformation:\n");
+
+  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+  {
+    /* v'->v'': index1->(index1+1).  */
+    i = 2 * bb->index;
+    fcost = (gcov_type) COST (k_pos, bb->count);
+    add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count,
+                    fcost, CAP_INFINITY);
+    fixup_graph->num_vertices++;
+
+    FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      /* Edges with ignore attribute set should be treated like they don't
+         exist.  */
+      if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
+        continue;
+      j = 2 * e->dest->index;
+      fcost = (gcov_type) COST (k_pos, e->count);
+      add_fixup_edge (fixup_graph, i + 1, j, REDIRECT_EDGE, e->count, fcost,
+                      CAP_INFINITY);
+    }
+  }
+
+  /* After vertex transformation.  */
+  gcc_assert (fixup_graph->num_vertices == fnum_vertices_after_transform);
+  /* Redirect edges are not added for edges with ignore attribute.  */
+  gcc_assert (fixup_graph->num_edges <= fnum_edges_after_transform);
+
+  fnum_edges_after_transform = fixup_graph->num_edges;
+
+  /* 2. Initialize D(v).  */
+  for (i = 0; i < fnum_edges_after_transform; i++)
+    {
+      pfedge = fixup_graph->edge_list + i;
+      diff_out_in[pfedge->src] += pfedge->weight;
+      diff_out_in[pfedge->dest] -= pfedge->weight;
+    }
+
+  /* Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3.  */
+  for (i = 0; i <= 3; i++)
+    diff_out_in[i] = 0;
+
+  /* 3. Add reverse edges: needed to decrease counts during smoothing.  */
+  if (dump_file)
+    fprintf (dump_file, "\nReverse edges:\n");
+  for (i = 0; i < fnum_edges_after_transform; i++)
+    {
+      pfedge = fixup_graph->edge_list + i;
+      if ((pfedge->src == 0) || (pfedge->src == 2))
+        continue;
+      r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
+      if (!r_pfedge && pfedge->weight)
+	{
+	  /* Skip adding reverse edges for edges with w(e) = 0, as its maximum
+	     capacity is 0.  */
+	  fcost = (gcov_type) COST (k_neg, pfedge->weight);
+	  add_fixup_edge (fixup_graph, pfedge->dest, pfedge->src,
+			  REVERSE_EDGE, 0, fcost, pfedge->weight);
+	}
+    }
+
+  /* 4. Create single source and sink. Connect new source vertex s' to function
+     entry block. Connect sink vertex t' to function exit.  */
+  if (dump_file)
+    fprintf (dump_file, "\ns'->S, T->t':\n");
+
+  new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices;
+  fixup_graph->num_vertices++;
+  /* Set supply_value to 1 to avoid zero count function ENTRY.  */
+  add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE,
+		  1 /* supply_value */, 0, 1 /* supply_value */);
+
+  /* Create new exit with EXIT_BLOCK as single pred.  */
+  new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices;
+  fixup_graph->num_vertices++;
+  add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index,
+                  SINK_CONNECT_EDGE,
+                  0 /* demand_value */, 0, 0 /* demand_value */);
+
+  /* Connect vertices with unbalanced D(v) to source/sink.  */
+  if (dump_file)
+    fprintf (dump_file, "\nD(v) balance:\n");
+  /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
+     diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2.  */
+  for (i = 4; i < new_entry_index; i += 2)
+    {
+      if (diff_out_in[i] > 0)
+	{
+	  add_fixup_edge (fixup_graph, i, new_exit_index, BALANCE_EDGE, 0, 0,
+			  diff_out_in[i]);
+	  demand_value += diff_out_in[i];
+	}
+      else if (diff_out_in[i] < 0)
+	{
+	  add_fixup_edge (fixup_graph, new_entry_index, i, BALANCE_EDGE, 0, 0,
+			  -diff_out_in[i]);
+	  supply_value -= diff_out_in[i];
+	}
+    }
+
+  /* Set supply = demand.  */
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nAdjust supply and demand:\n");
+      fprintf (dump_file, "supply_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
+	       supply_value);
+      fprintf (dump_file, "demand_value=" HOST_WIDEST_INT_PRINT_DEC "\n",
+	       demand_value);
+    }
+
+  if (demand_value > supply_value)
+    {
+      pfedge = find_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK);
+      pfedge->max_capacity += (demand_value - supply_value);
+    }
+  else
+    {
+      pfedge = find_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index);
+      pfedge->max_capacity += (supply_value - demand_value);
+    }
+
+  /* 6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
+     created by the vertex transformation step from self-edges in the original
+     CFG and by the reverse edges added earlier.  */
+  if (dump_file)
+    fprintf (dump_file, "\nNormalize edges:\n");
+
+  fnum_edges = fixup_graph->num_edges;
+  fedge_list = fixup_graph->edge_list;
+
+  for (i = 0; i < fnum_edges; i++)
+    {
+      pfedge = fedge_list + i;
+      r_pfedge = find_fixup_edge (fixup_graph, pfedge->dest, pfedge->src);
+      if (((pfedge->type == VERTEX_SPLIT_EDGE)
+	   || (pfedge->type == REDIRECT_EDGE)) && r_pfedge)
+	{
+	  new_index = fixup_graph->num_vertices;
+	  fixup_graph->num_vertices++;
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "\nAnti-parallel edge:\n");
+	      dump_fixup_edge (dump_file, fixup_graph, pfedge);
+	      dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
+	      fprintf (dump_file, "New vertex is %d.\n", new_index);
+	      fprintf (dump_file, "------------------\n");
+	    }
+
+	  pfedge->cost /= 2;
+	  pfedge->norm_vertex_index = new_index;
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "After normalization:\n");
+	      dump_fixup_edge (dump_file, fixup_graph, pfedge);
+	    }
+
+	  /* Add a new fixup edge: new_index->src.  */
+	  add_fixup_edge (fixup_graph, new_index, pfedge->src,
+			  REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost,
+			  r_pfedge->max_capacity);
+	  gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices);
+
+	  /* Edge: r_pfedge->src -> r_pfedge->dest
+             ==> r_pfedge->src -> new_index.  */
+	  r_pfedge->dest = new_index;
+	  r_pfedge->type = REVERSE_NORMALIZED_EDGE;
+	  r_pfedge->cost = pfedge->cost;
+	  r_pfedge->max_capacity = pfedge->max_capacity;
+	  if (dump_file)
+	    dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
+	}
+    }
+
+  if (dump_file)
+    dump_fixup_graph (dump_file, fixup_graph, "After create_fixup_graph()");
+
+  /* Cleanup.  */
+  free (diff_out_in);
+}
+
+
+/* Allocates space for the structures in AUGMENTING_PATH.  The space needed is
+   proportional to the number of nodes in the graph, which is given by
+   GRAPH_SIZE.  */
+
+static void
+init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size)
+{
+  augmenting_path->queue_list.queue = (int *)
+    xcalloc (graph_size + 2, sizeof (int));
+  augmenting_path->queue_list.size = graph_size + 2;
+  augmenting_path->bb_pred = (int *) xcalloc (graph_size, sizeof (int));
+  augmenting_path->is_visited = (int *) xcalloc (graph_size, sizeof (int));
+}
+
+/* Free the structures in AUGMENTING_PATH.  */
+static void
+free_augmenting_path (augmenting_path_type *augmenting_path)
+{
+  free (augmenting_path->queue_list.queue);
+  free (augmenting_path->bb_pred);
+  free (augmenting_path->is_visited);
+}
+
+
+/* Queue routines. Assumes queue will never overflow.  */
+
+static void
+init_queue (queue_type *queue_list)
+{
+  gcc_assert (queue_list);
+  queue_list->head = 0;
+  queue_list->tail = 0;
+}
+
+/* Return true if QUEUE_LIST is empty.  */
+static bool
+is_empty (queue_type *queue_list)
+{
+  return (queue_list->head == queue_list->tail);
+}
+
+/* Insert element X into QUEUE_LIST.  */
+static void
+enqueue (queue_type *queue_list, int x)
+{
+  gcc_assert (queue_list->tail < queue_list->size);
+  queue_list->queue[queue_list->tail] = x;
+  (queue_list->tail)++;
+}
+
+/* Return the first element in QUEUE_LIST.  */
+static int
+dequeue (queue_type *queue_list)
+{
+  int x;
+  gcc_assert (queue_list->head >= 0);
+  x = queue_list->queue[queue_list->head];
+  (queue_list->head)++;
+  return x;
+}
+
+
+/* Finds a negative cycle in the residual network using
+   the Bellman-Ford algorithm. The flow on the found cycle is reversed by the
+   minimum residual capacity of that cycle. ENTRY and EXIT vertices are not
+   considered.
+
+Parameters:
+   FIXUP_GRAPH - Residual graph  (input/output)
+   The following are allocated/freed by the caller:
+   PI - Vector to hold predecessors in path  (pi = pred index)
+   D - D[I] holds minimum cost of path from i to sink
+   CYCLE - Vector to hold the minimum cost cycle
+
+Return:
+   true if a negative cycle was found, false otherwise.  */
+
+static bool
+cancel_negative_cycle (fixup_graph_type *fixup_graph,
+		       int *pi, gcov_type *d, int *cycle)
+{
+  int i, j, k;
+  int fnum_vertices, fnum_edges;
+  fixup_edge_p fedge_list, pfedge, r_pfedge;
+  bool found_cycle = false;
+  int cycle_start = 0, cycle_end = 0;
+  gcov_type sum_cost = 0, cycle_flow = 0;
+  int new_entry_index;
+  bool propagated = false;
+
+  gcc_assert (fixup_graph);
+  fnum_vertices = fixup_graph->num_vertices;
+  fnum_edges = fixup_graph->num_edges;
+  fedge_list = fixup_graph->edge_list;
+  new_entry_index = fixup_graph->new_entry_index;
+
+  /* Initialize.  */
+  /* Skip ENTRY.  */
+  for (i = 1; i < fnum_vertices; i++)
+    {
+      d[i] = CAP_INFINITY;
+      pi[i] = -1;
+      cycle[i] = -1;
+    }
+  d[ENTRY_BLOCK] = 0;
+
+  /* Relax.  */
+  for (k = 1; k < fnum_vertices; k++)
+  {
+    propagated = false;
+    for (i = 0; i < fnum_edges; i++)
+      {
+	pfedge = fedge_list + i;
+	if (pfedge->src == new_entry_index)
+	  continue;
+	if (pfedge->is_rflow_valid && pfedge->rflow
+            && d[pfedge->src] != CAP_INFINITY
+	    && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
+	  {
+	    d[pfedge->dest] = d[pfedge->src] + pfedge->cost;
+	    pi[pfedge->dest] = pfedge->src;
+            propagated = true;
+	  }
+      }
+    if (!propagated)
+      break;
+  }
+
+  if (!propagated)
+  /* No negative cycles exist.  */
+    return 0;
+
+  /* Detect.  */
+  for (i = 0; i < fnum_edges; i++)
+    {
+      pfedge = fedge_list + i;
+      if (pfedge->src == new_entry_index)
+	continue;
+      if (pfedge->is_rflow_valid && pfedge->rflow
+          && d[pfedge->src] != CAP_INFINITY
+	  && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
+	{
+	  found_cycle = true;
+	  break;
+	}
+    }
+
+  if (!found_cycle)
+    return 0;
+
+  /* Augment the cycle with the cycle's minimum residual capacity.  */
+  found_cycle = false;
+  cycle[0] = pfedge->dest;
+  j = pfedge->dest;
+
+  for (i = 1; i < fnum_vertices; i++)
+    {
+      j = pi[j];
+      cycle[i] = j;
+      for (k = 0; k < i; k++)
+	{
+	  if (cycle[k] == j)
+	    {
+	      /* cycle[k] -> ... -> cycle[i].  */
+	      cycle_start = k;
+	      cycle_end = i;
+	      found_cycle = true;
+	      break;
+	    }
+	}
+      if (found_cycle)
+	break;
+    }
+
+  gcc_assert (cycle[cycle_start] == cycle[cycle_end]);
+  if (dump_file)
+    fprintf (dump_file, "\nNegative cycle length is %d:\n",
+	     cycle_end - cycle_start);
+
+  sum_cost = 0;
+  cycle_flow = CAP_INFINITY;
+  for (k = cycle_start; k < cycle_end; k++)
+    {
+      pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
+      cycle_flow = MIN (cycle_flow, pfedge->rflow);
+      sum_cost += pfedge->cost;
+      if (dump_file)
+	fprintf (dump_file, "%d ", cycle[k]);
+    }
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "%d", cycle[k]);
+      fprintf (dump_file,
+	       ": (" HOST_WIDEST_INT_PRINT_DEC ", " HOST_WIDEST_INT_PRINT_DEC
+	       ")\n", sum_cost, cycle_flow);
+      fprintf (dump_file,
+	       "Augment cycle with " HOST_WIDEST_INT_PRINT_DEC "\n",
+	       cycle_flow);
+    }
+
+  for (k = cycle_start; k < cycle_end; k++)
+    {
+      pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
+      r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]);
+      pfedge->rflow -= cycle_flow;
+      if (pfedge->type)
+	pfedge->flow += cycle_flow;
+      r_pfedge->rflow += cycle_flow;
+      if (r_pfedge->type)
+	r_pfedge->flow -= cycle_flow;
+    }
+
+  return true;
+}
+
+
+/* Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
+   the edges. ENTRY and EXIT vertices should not be considered.  */
+
+static void
+compute_residual_flow (fixup_graph_type *fixup_graph)
+{
+  int i;
+  int fnum_edges;
+  fixup_edge_p fedge_list, pfedge;
+
+  gcc_assert (fixup_graph);
+
+  if (dump_file)
+    fputs ("\ncompute_residual_flow():\n", dump_file);
+
+  fnum_edges = fixup_graph->num_edges;
+  fedge_list = fixup_graph->edge_list;
+
+  for (i = 0; i < fnum_edges; i++)
+    {
+      pfedge = fedge_list + i;
+      pfedge->rflow = pfedge->max_capacity - pfedge->flow;
+      pfedge->is_rflow_valid = true;
+      add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow,
+		       -pfedge->cost);
+    }
+}
+
+
+/* Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
+   SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
+   this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
+   to reflect the path found.
+   Returns: 0 if no augmenting path is found, 1 otherwise.  */
+
+static int
+find_augmenting_path (fixup_graph_type *fixup_graph,
+		      augmenting_path_type *augmenting_path, int source,
+		      int sink)
+{
+  int u = 0;
+  int i;
+  fixup_vertex_p fvertex_list, pfvertex;
+  fixup_edge_p pfedge;
+  int *bb_pred, *is_visited;
+  queue_type *queue_list;
+
+  gcc_assert (augmenting_path);
+  bb_pred = augmenting_path->bb_pred;
+  gcc_assert (bb_pred);
+  is_visited = augmenting_path->is_visited;
+  gcc_assert (is_visited);
+  queue_list = &(augmenting_path->queue_list);
+
+  gcc_assert (fixup_graph);
+
+  fvertex_list = fixup_graph->vertex_list;
+
+  for (u = 0; u < fixup_graph->num_vertices; u++)
+    is_visited[u] = 0;
+
+  init_queue (queue_list);
+  enqueue (queue_list, source);
+  bb_pred[source] = -1;
+
+  while (!is_empty (queue_list))
+    {
+      u = dequeue (queue_list);
+      is_visited[u] = 1;
+      pfvertex = fvertex_list + u;
+      for (i = 0; VEC_iterate (fixup_edge_p, pfvertex->succ_edges, i, pfedge);
+	   i++)
+	{
+	  int dest = pfedge->dest;
+	  if ((pfedge->rflow > 0) && (is_visited[dest] == 0))
+	    {
+	      enqueue (queue_list, dest);
+	      bb_pred[dest] = u;
+	      is_visited[dest] = 1;
+	      if (dest == sink)
+		return 1;
+	    }
+	}
+    }
+
+  return 0;
+}
+
+
+/* Routine to find the maximal flow:
+   Algorithm:
+   1. Initialize flow to 0
+   2. Find an augmenting path form source to sink.
+   3. Send flow equal to the path's residual capacity along the edges of this path.
+   4. Repeat steps 2 and 3 until no new augmenting path is found.
+   
+Parameters:
+SOURCE: index of source vertex (input)
+SINK: index of sink vertex    (input)
+FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be
+             set to have a valid maximal flow by this routine. (input)
+Return: Maximum flow possible.  */
+
+static gcov_type
+find_max_flow (fixup_graph_type *fixup_graph, int source, int sink)
+{
+  int fnum_edges;
+  augmenting_path_type augmenting_path;
+  int *bb_pred;
+  gcov_type max_flow = 0;
+  int i, u;
+  fixup_edge_p fedge_list, pfedge, r_pfedge;
+
+  gcc_assert (fixup_graph);
+
+  fnum_edges = fixup_graph->num_edges;
+  fedge_list = fixup_graph->edge_list;
+
+  /* Initialize flow to 0.  */
+  for (i = 0; i < fnum_edges; i++)
+    {
+      pfedge = fedge_list + i;
+      pfedge->flow = 0;
+    }
+
+  compute_residual_flow (fixup_graph);
+
+  init_augmenting_path (&augmenting_path, fixup_graph->num_vertices);
+
+  bb_pred = augmenting_path.bb_pred;
+  while (find_augmenting_path (fixup_graph, &augmenting_path, source, sink))
+    {
+      /* Determine the amount by which we can increment the flow.  */
+      gcov_type increment = CAP_INFINITY;
+      for (u = sink; u != source; u = bb_pred[u])
+	{
+	  pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
+	  increment = MIN (increment, pfedge->rflow);
+	}
+      max_flow += increment;
+
+      /* Now increment the flow. EXIT vertex index is 1.  */
+      for (u = sink; u != source; u = bb_pred[u])
+	{
+	  pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
+	  r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]);
+	  if (pfedge->type)
+	    {
+	      /* forward edge.  */
+	      pfedge->flow += increment;
+	      pfedge->rflow -= increment;
+	      r_pfedge->rflow += increment;
+	    }
+	  else
+	    {
+	      /* backward edge.  */
+	      gcc_assert (r_pfedge->type);
+	      r_pfedge->rflow += increment;
+	      r_pfedge->flow -= increment;
+	      pfedge->rflow -= increment;
+	    }
+	}
+
+      if (dump_file)
+	{
+	  fprintf (dump_file, "\nDump augmenting path:\n");
+	  for (u = sink; u != source; u = bb_pred[u])
+	    {
+	      print_basic_block (dump_file, fixup_graph, u);
+	      fprintf (dump_file, "<-");
+	    }
+	  fprintf (dump_file,
+		   "ENTRY  (path_capacity=" HOST_WIDEST_INT_PRINT_DEC ")\n",
+		   increment);
+	  fprintf (dump_file,
+		   "Network flow is " HOST_WIDEST_INT_PRINT_DEC ".\n",
+		   max_flow);
+	}
+    }
+
+  free_augmenting_path (&augmenting_path);
+  if (dump_file)
+    dump_fixup_graph (dump_file, fixup_graph, "After find_max_flow()");
+  return max_flow;
+}
+
+
+/* Computes the corrected edge and basic block weights using FIXUP_GRAPH
+   after applying the find_minimum_cost_flow() routine.  */
+
+static void
+adjust_cfg_counts (fixup_graph_type *fixup_graph)
+{
+  basic_block bb;
+  edge e;
+  edge_iterator ei;
+  int i, j;
+  fixup_edge_p pfedge, pfedge_n;
+
+  gcc_assert (fixup_graph);
+
+  if (dump_file)
+    fprintf (dump_file, "\nadjust_cfg_counts():\n");
+
+  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+    {
+      i = 2 * bb->index;
+
+      /* Fixup BB.  */
+      if (dump_file)
+        fprintf (dump_file,
+                 "BB%d: " HOST_WIDEST_INT_PRINT_DEC "", bb->index, bb->count);
+
+      pfedge = find_fixup_edge (fixup_graph, i, i + 1);
+      if (pfedge->flow)
+        {
+          bb->count += pfedge->flow;
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
+	               pfedge->flow);
+	      print_edge (dump_file, fixup_graph, i, i + 1);
+	      fprintf (dump_file, ")");
+	    }
+        }
+
+      pfedge_n =
+        find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
+      /* Deduct flow from normalized reverse edge.  */
+      if (pfedge->norm_vertex_index && pfedge_n->flow)
+        {
+          bb->count -= pfedge_n->flow;
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
+		       pfedge_n->flow);
+	      print_edge (dump_file, fixup_graph, i + 1,
+			  pfedge->norm_vertex_index);
+	      fprintf (dump_file, ")");
+	    }
+        }
+      if (dump_file)
+        fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\n", bb->count);
+
+      /* Fixup edge.  */
+      FOR_EACH_EDGE (e, ei, bb->succs)
+        {
+          /* Treat edges with ignore attribute set as if they don't exist.  */
+          if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
+	    continue;
+
+          j = 2 * e->dest->index;
+          if (dump_file)
+	    fprintf (dump_file, "%d->%d: " HOST_WIDEST_INT_PRINT_DEC "",
+		     bb->index, e->dest->index, e->count);
+
+          pfedge = find_fixup_edge (fixup_graph, i + 1, j);
+
+          if (bb->index != e->dest->index)
+	    {
+	      /* Non-self edge.  */
+	      if (pfedge->flow)
+	        {
+	          e->count += pfedge->flow;
+	          if (dump_file)
+		    {
+		      fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
+			       pfedge->flow);
+		      print_edge (dump_file, fixup_graph, i + 1, j);
+		      fprintf (dump_file, ")");
+		    }
+	        }
+
+	      pfedge_n =
+	        find_fixup_edge (fixup_graph, j, pfedge->norm_vertex_index);
+	      /* Deduct flow from normalized reverse edge.  */
+	      if (pfedge->norm_vertex_index && pfedge_n->flow)
+	        {
+	          e->count -= pfedge_n->flow;
+	          if (dump_file)
+		    {
+		      fprintf (dump_file, " - " HOST_WIDEST_INT_PRINT_DEC "(",
+			       pfedge_n->flow);
+		      print_edge (dump_file, fixup_graph, j,
+			          pfedge->norm_vertex_index);
+		      fprintf (dump_file, ")");
+		    }
+	        }
+	    }
+          else
+	    {
+	      /* Handle self edges. Self edge is split with a normalization
+                 vertex. Here i=j.  */
+	      pfedge = find_fixup_edge (fixup_graph, j, i + 1);
+	      pfedge_n =
+	        find_fixup_edge (fixup_graph, i + 1, pfedge->norm_vertex_index);
+	      e->count += pfedge_n->flow;
+	      bb->count += pfedge_n->flow;
+	      if (dump_file)
+	        {
+	          fprintf (dump_file, "(self edge)");
+	          fprintf (dump_file, " + " HOST_WIDEST_INT_PRINT_DEC "(",
+		           pfedge_n->flow);
+	          print_edge (dump_file, fixup_graph, i + 1,
+			      pfedge->norm_vertex_index);
+	          fprintf (dump_file, ")");
+	        }
+	    }
+
+          if (bb->count)
+	    e->probability = REG_BR_PROB_BASE * e->count / bb->count;
+          if (dump_file)
+	    fprintf (dump_file, " = " HOST_WIDEST_INT_PRINT_DEC "\t(%.1f%%)\n",
+		     e->count, e->probability * 100.0 / REG_BR_PROB_BASE);
+        }
+    } 
+
+  ENTRY_BLOCK_PTR->count = sum_edge_counts (ENTRY_BLOCK_PTR->succs); 
+  EXIT_BLOCK_PTR->count = sum_edge_counts (EXIT_BLOCK_PTR->preds);
+
+  /* Compute edge probabilities.  */
+  FOR_ALL_BB (bb)
+    {
+      if (bb->count)
+        {
+          FOR_EACH_EDGE (e, ei, bb->succs)
+            e->probability = REG_BR_PROB_BASE * e->count / bb->count;
+        }
+      else
+        {
+          int total = 0;
+          FOR_EACH_EDGE (e, ei, bb->succs)
+            if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
+              total++;
+          if (total)
+            {
+              FOR_EACH_EDGE (e, ei, bb->succs)
+                {
+                  if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
+                    e->probability = REG_BR_PROB_BASE / total;
+                  else
+                    e->probability = 0;
+                }
+            }
+          else
+            {
+              total += EDGE_COUNT (bb->succs);
+              FOR_EACH_EDGE (e, ei, bb->succs)
+                  e->probability = REG_BR_PROB_BASE / total;
+            }
+        }
+    }
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nCheck %s() CFG flow conservation:\n",
+           lang_hooks.decl_printable_name (current_function_decl, 2));
+      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
+        {
+          if ((bb->count != sum_edge_counts (bb->preds))
+               || (bb->count != sum_edge_counts (bb->succs)))
+            {
+              fprintf (dump_file,
+                       "BB%d(" HOST_WIDEST_INT_PRINT_DEC ")  **INVALID**: ",
+                       bb->index, bb->count);
+              fprintf (stderr,
+                       "******** BB%d(" HOST_WIDEST_INT_PRINT_DEC
+                       ")  **INVALID**: \n", bb->index, bb->count);
+              fprintf (dump_file, "in_edges=" HOST_WIDEST_INT_PRINT_DEC " ",
+                       sum_edge_counts (bb->preds));
+              fprintf (dump_file, "out_edges=" HOST_WIDEST_INT_PRINT_DEC "\n",
+                       sum_edge_counts (bb->succs));
+            }
+         }
+    }
+}
+
+
+/* Implements the negative cycle canceling algorithm to compute a minimum cost
+   flow.
+Algorithm:
+1. Find maximal flow.
+2. Form residual network
+3. Repeat:
+  While G contains a negative cost cycle C, reverse the flow on the found cycle
+  by the minimum residual capacity in that cycle.
+4. Form the minimal cost flow
+  f(u,v) = rf(v, u)
+Input:
+  FIXUP_GRAPH - Initial fixup graph.
+  The flow field is modified to represent the minimum cost flow.  */
+
+static void
+find_minimum_cost_flow (fixup_graph_type *fixup_graph)
+{
+  /* Holds the index of predecessor in path.  */
+  int *pred;
+  /* Used to hold the minimum cost cycle.  */
+  int *cycle;
+  /* Used to record the number of iterations of cancel_negative_cycle.  */
+  int iteration;
+  /* Vector d[i] holds the minimum cost of path from i to sink.  */
+  gcov_type *d;
+  int fnum_vertices;
+  int new_exit_index;
+  int new_entry_index;
+
+  gcc_assert (fixup_graph);
+  fnum_vertices = fixup_graph->num_vertices;
+  new_exit_index = fixup_graph->new_exit_index;
+  new_entry_index = fixup_graph->new_entry_index;
+
+  find_max_flow (fixup_graph, new_entry_index, new_exit_index);
+
+  /* Initialize the structures for find_negative_cycle().  */
+  pred = (int *) xcalloc (fnum_vertices, sizeof (int));
+  d = (gcov_type *) xcalloc (fnum_vertices, sizeof (gcov_type));
+  cycle = (int *) xcalloc (fnum_vertices, sizeof (int));
+
+  /* Repeatedly find and cancel negative cost cycles, until
+     no more negative cycles exist. This also updates the flow field
+     to represent the minimum cost flow so far.  */
+  iteration = 0;
+  while (cancel_negative_cycle (fixup_graph, pred, d, cycle))
+    {
+      iteration++;
+      if (iteration > MAX_ITER (fixup_graph->num_vertices,
+                                fixup_graph->num_edges))
+        break;
+    }
+
+  if (dump_file)
+    dump_fixup_graph (dump_file, fixup_graph,
+		      "After find_minimum_cost_flow()");
+
+  /* Cleanup structures.  */
+  free (pred);
+  free (d);
+  free (cycle);
+}
+
+
+/* Compute the sum of the edge counts in TO_EDGES.  */
+
+gcov_type
+sum_edge_counts (VEC (edge, gc) *to_edges)
+{
+  gcov_type sum = 0;
+  edge e;
+  edge_iterator ei;
+
+  FOR_EACH_EDGE (e, ei, to_edges)
+    {
+      if (EDGE_INFO (e) && EDGE_INFO (e)->ignore)
+        continue;
+      sum += e->count;
+    }
+  return sum;
+}
+
+
+/* Main routine. Smoothes the intial assigned basic block and edge counts using
+   a minimum cost flow algorithm, to ensure that the flow consistency rule is
+   obeyed: sum of outgoing edges = sum of incoming edges for each basic
+   block.  */
+
+void
+mcf_smooth_cfg (void)
+{
+  fixup_graph_type fixup_graph;
+  memset (&fixup_graph, 0, sizeof (fixup_graph));
+  create_fixup_graph (&fixup_graph);
+  find_minimum_cost_flow (&fixup_graph);
+  adjust_cfg_counts (&fixup_graph);
+  delete_fixup_graph (&fixup_graph);
+}