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