LCOV - code coverage report
Current view: top level - gcc - mcf.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 9 603 1.5 %
Date: 2020-04-04 11:58:09 Functions: 1 26 3.8 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

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

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.