Subversion Repositories openrisc_me

/* Routines to implement minimum-cost maximal flow algorithm used to smooth

   basic block and edge frequency counts.

   Copyright (C) 2008, 2009

   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 INTTYPE_MAXIMUM (HOST_WIDEST_INT)

/* 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,

                edge_type 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,

  /* 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)