From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-patches-return-293491-listarch-gcc-patches=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 6784 invoked by alias); 2 Jun 2011 18:05:49 -0000
Received: (qmail 6773 invoked by uid 22791); 2 Jun 2011 18:05:47 -0000
X-SWARE-Spam-Status: No, hits=-1.7 required=5.0	tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,SPF_HELO_PASS,TW_CF,T_RP_MATCHES_RCVD
X-Spam-Check-By: sourceware.org
Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.44.51)    by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 02 Jun 2011 18:05:32 +0000
Received: from kpbe18.cbf.corp.google.com (kpbe18.cbf.corp.google.com [172.25.105.82])	by smtp-out.google.com with ESMTP id p52I5UlS013820	for <gcc-patches@gcc.gnu.org>; Thu, 2 Jun 2011 11:05:31 -0700
Received: from yxi11 (yxi11.prod.google.com [10.190.3.11])	by kpbe18.cbf.corp.google.com with ESMTP id p52I4h9T026488	(version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT)	for <gcc-patches@gcc.gnu.org>; Thu, 2 Jun 2011 11:05:29 -0700
Received: by yxi11 with SMTP id 11so168602yxi.34        for <gcc-patches@gcc.gnu.org>; Thu, 02 Jun 2011 11:05:29 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.151.79.10 with SMTP id g10mr1045596ybl.301.1307037929212; Thu, 02 Jun 2011 11:05:29 -0700 (PDT)
Received: by 10.151.26.21 with HTTP; Thu, 2 Jun 2011 11:05:29 -0700 (PDT)
In-Reply-To: <20110602180025.36B301EE08E@martint2.mtv.corp.google.com>
References: <20110602180025.36B301EE08E@martint2.mtv.corp.google.com>
Date: Thu, 02 Jun 2011 18:05:00 -0000
Message-ID: <BANLkTinAXbSG9xCJB+TaaTEVUskqSg_wvw@mail.gmail.com>
Subject: Re: [google] Use minimum cost circulation, not minimum cost flow to smooth profiles other minor fixes. (issue4536106)
From: Xinliang David Li <davidxl@google.com>
To: Martin Thuresson <martint@google.com>
Cc: reply@codereview.appspotmail.com, GCC Patches <gcc-patches@gcc.gnu.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-System-Of-Record: true
X-IsSubscribed: yes
Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-patches.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-patches/>
List-Post: <mailto:gcc-patches@gcc.gnu.org>
List-Help: <mailto:gcc-patches-help@gcc.gnu.org>
Sender: gcc-patches-owner@gcc.gnu.org
X-SW-Source: 2011-06/txt/msg00176.txt.bz2

Smoothing works for sample FDO and profile data from multi-threaded
programs. You won't see any difference in SPEC.

David

On Thu, Jun 2, 2011 at 11:00 AM, Martin Thuresson <martint@google.com> wrot=
e:
> This patch from Neil Vachharajani and Dehao Chen improves mcf by using
> minimum cost circulation instead of minimum cost flow to smooth profiles.
> It also introduces a parameter for controlling running time of the algori=
thm.
> This was what was originally presented in the academic work and handles
> certain cases where the function entry and exit have incorrect profile
> weights.
>
> For now, this is for google/main. Once I have collected performance resul=
ts
> from SPEC I will propose this patch for trunk as well.
>
> Bootstraps and no test regressions. Ok for google/main?
>
> 2011-06-02 =A0Neil Vachharajani =A0<nvachhar@gmail.com>, Dehao Chen
> =A0 =A0 =A0 =A0<danielcdh@gmail.com>
>
> =A0 =A0 =A0 =A0* gcc/doc/invoke.texi (min-mcf-cancel-iters): Document.
> =A0 =A0 =A0 =A0* gcc/mcf.c (MAX_ITER): Use new param PARAM_MIN_MCF_CANCEL=
_ITERS.
> =A0 =A0 =A0 =A0(edge_type): Add SINK_SOURCE_EDGE.
> =A0 =A0 =A0 =A0(dump_fixup_edge): Handle SINK_SOURCE_EDGE.
> =A0 =A0 =A0 =A0(create_fixup_graph): Make problem miminum cost circulatio=
n.
> =A0 =A0 =A0 =A0(cancel_negative_cycle): Update handling of infinite capac=
ity.
> =A0 =A0 =A0 =A0(compute_residual_flow): Update handling of infinite capac=
ity.
> =A0 =A0 =A0 =A0(find_max_flow): Update handling of infinite capacity.
> =A0 =A0 =A0 =A0(modify_sink_source_capacity): New function.
> =A0 =A0 =A0 =A0(find_minimum_cost_flow): Make problem miminum cost circul=
ation.
> =A0 =A0 =A0 =A0Use param PARAM_MIN_MCF_CANCEL_ITERS.
> =A0 =A0 =A0 =A0* gcc/params.def (PARAM_MIN_MCF_CANCEL_ITERS): Define.
>
> Index: gcc/doc/invoke.texi
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> --- gcc/doc/invoke.texi (revision 174456)
> +++ gcc/doc/invoke.texi (working copy)
> @@ -8341,6 +8341,12 @@ whether the result of a complex multipli
>
> =A0The default is @option{-fno-cx-fortran-rules}.
>
> +@item min-mcf-cancel-iters
> +The minimum number of iterations of negative cycle cancellation during
> +MCF profile correction before early termination. =A0This parameter is
> +only useful when using @option{-fprofile-correction}.
> +
> +
> =A0@end table
>
> =A0The following options control optimizations that may improve
> Index: gcc/mcf.c
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> --- gcc/mcf.c =A0 (revision 174456)
> +++ gcc/mcf.c =A0 (working copy)
> @@ -52,6 +52,8 @@ along with GCC; see the file COPYING3.
> =A0#include "langhooks.h"
> =A0#include "tree.h"
> =A0#include "gcov-io.h"
> +#include "params.h"
> +#include "diagnostic-core.h"
>
> =A0#include "profile.h"
>
> @@ -64,15 +66,18 @@ along with GCC; see the file COPYING3.
> =A0#define COST(k, w) =A0 =A0 =A0((k) / mcf_ln ((w) + 2))
> =A0/* Limit the number of iterations for cancel_negative_cycles() to ensu=
re
> =A0 =A0reasonable compile time. =A0*/
> -#define MAX_ITER(n, e) =A010 + (1000000 / ((n) * (e)))
> +#define MAX_ITER(n, e) =A0(PARAM_VALUE (PARAM_MIN_MCF_CANCEL_ITERS) + \
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(1000000 / ((n) * (e))))
> +
> =A0typedef enum
> =A0{
> - =A0INVALID_EDGE,
> + =A0INVALID_EDGE =3D 0,
> =A0 VERTEX_SPLIT_EDGE, =A0 =A0 =A0 /* Edge to represent vertex with w(e) =
=3D w(v). =A0*/
> =A0 REDIRECT_EDGE, =A0 =A0 =A0 =A0 =A0 /* Edge after vertex transformatio=
n. =A0*/
> =A0 REVERSE_EDGE,
> =A0 SOURCE_CONNECT_EDGE, =A0 =A0 /* Single edge connecting to single sour=
ce. =A0*/
> =A0 SINK_CONNECT_EDGE, =A0 =A0 =A0 /* Single edge connecting to single si=
nk. =A0*/
> + =A0SINK_SOURCE_EDGE, =A0 =A0 =A0 =A0/* Single edge connecting sink to s=
ource. =A0*/
> =A0 BALANCE_EDGE, =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0/* Edge connecti=
ng with source/sink: cp(e) =3D 0. =A0*/
> =A0 REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge. =A0=
*/
> =A0 REVERSE_NORMALIZED_EDGE =A0 /* Normalized edge for a reverse edge. =
=A0*/
> @@ -250,6 +255,10 @@ dump_fixup_edge (FILE *file, fixup_graph
> =A0 =A0 =A0 =A0 =A0fputs (" @SINK_CONNECT_EDGE", file);
> =A0 =A0 =A0 =A0 =A0break;
>
> + =A0 =A0 =A0 case SINK_SOURCE_EDGE:
> + =A0 =A0 =A0 =A0 fputs (" @SINK_SOURCE_EDGE", file);
> + =A0 =A0 =A0 =A0 break;
> +
> =A0 =A0 =A0 =A0case REVERSE_EDGE:
> =A0 =A0 =A0 =A0 =A0fputs (" @REVERSE_EDGE", file);
> =A0 =A0 =A0 =A0 =A0break;
> @@ -465,7 +474,7 @@ create_fixup_graph (fixup_graph_type *fi
> =A0 double k_neg =3D 0;
> =A0 /* Vector to hold D(v) =3D sum_out_edges(v) - sum_in_edges(v). =A0*/
> =A0 gcov_type *diff_out_in =3D NULL;
> - =A0gcov_type supply_value =3D 1, demand_value =3D 0;
> + =A0gcov_type supply_value =3D 0, demand_value =3D 0;
> =A0 gcov_type fcost =3D 0;
> =A0 int new_entry_index =3D 0, new_exit_index =3D 0;
> =A0 int i =3D 0, j =3D 0;
> @@ -486,14 +495,15 @@ create_fixup_graph (fixup_graph_type *fi
> =A0 =A0 fnum_vertices_after_transform + n_edges + n_basic_blocks + 2;
>
> =A0 /* In create_fixup_graph: Each basic block and edge can be split into=
 3
> - =A0 =A0 edges. Number of balance edges =3D n_basic_blocks. So after
> - =A0 =A0 create_fixup_graph:
> - =A0 =A0 max_edges =3D 4 * n_basic_blocks + 3 * n_edges
> + =A0 =A0 edges. Number of balance edges =3D n_basic_blocks - 1. And ther=
e is 1 edge
> + =A0 =A0 connecting new_entry and new_exit, and 2 edges connecting new_e=
ntry to
> + =A0 =A0 entry, and exit to new_exit. So after create_fixup_graph:
> + =A0 =A0 max_edges =3D 4 * n_basic_blocks + 3 * n_edges + 2
> =A0 =A0 =A0Accounting for residual flow edges
> - =A0 =A0 max_edges =3D 2 * (4 * n_basic_blocks + 3 * n_edges)
> - =A0 =A0 =3D 8 * n_basic_blocks + 6 * n_edges
> - =A0 =A0 < 8 * n_basic_blocks + 8 * n_edges. =A0*/
> - =A0int fmax_num_edges =3D 8 * (n_basic_blocks + n_edges);
> + =A0 =A0 max_edges =3D 2 * (4 * n_basic_blocks + 3 * n_edges + 2)
> + =A0 =A0 =3D 8 * n_basic_blocks + 6 * n_edges + 4
> + =A0 =A0 < 8 * n_basic_blocks + 8 * n_edges + 8. =A0*/
> + =A0int fmax_num_edges =3D 8 * (n_basic_blocks + n_edges + 1);
>
> =A0 /* Initial num of vertices in the fixup graph. =A0*/
> =A0 fixup_graph->num_vertices =3D n_basic_blocks;
> @@ -512,7 +522,7 @@ create_fixup_graph (fixup_graph_type *fi
>
> =A0 /* Compute constants b, k_pos, k_neg used in the cost function calcul=
ation.
> =A0 =A0 =A0b =3D sqrt(avg_vertex_weight(cfg)); k_pos =3D b; k_neg =3D 50b=
. =A0*/
> - =A0FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
> + =A0FOR_ALL_BB (bb)
> =A0 =A0 total_vertex_weight +=3D bb->count;
>
> =A0 sqrt_avg_vertex_weight =3D mcf_sqrt (total_vertex_weight / n_basic_bl=
ocks);
> @@ -526,10 +536,11 @@ create_fixup_graph (fixup_graph_type *fi
> =A0 if (dump_file)
> =A0 =A0 fprintf (dump_file, "\nVertex transformation:\n");
>
> - =A0FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
> + =A0FOR_ALL_BB (bb)
> =A0 {
> =A0 =A0 /* v'->v'': index1->(index1+1). =A0*/
> =A0 =A0 i =3D 2 * bb->index;
> +
> =A0 =A0 fcost =3D (gcov_type) COST (k_pos, bb->count);
> =A0 =A0 add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->cou=
nt,
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 fcost, CAP_INFINITY);
> @@ -593,23 +604,45 @@ create_fixup_graph (fixup_graph_type *fi
>
> =A0 new_entry_index =3D fixup_graph->new_entry_index =3D fixup_graph->num=
_vertices;
> =A0 fixup_graph->num_vertices++;
> - =A0/* Set supply_value to 1 to avoid zero count function ENTRY. =A0*/
> - =A0add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CO=
NNECT_EDGE,
> - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 1 /* supply_value */, 0, 1 /* supply_va=
lue */);
> + =A0/* Set capacity to 0 initially, it will be updated after
> + =A0 =A0 supply_value is computed. */
> + =A0add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK,
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 SOURCE_CONNECT_EDGE, 0 /* supply_value =
*/, 0,
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 0 /* supply_value */);
> + =A0add_fixup_edge (fixup_graph, ENTRY_BLOCK, new_entry_index,
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0SOURCE_CONNECT_EDGE, 0 /* supply_val=
ue */, 0,
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00 /* supply_value */);
>
> - =A0/* Create new exit with EXIT_BLOCK as single pred. =A0*/
> +
> + =A0/* Set capacity to 0 initially, it will be updated after
> + =A0 =A0 demand_value is computed. */
> =A0 new_exit_index =3D fixup_graph->new_exit_index =3D fixup_graph->num_v=
ertices;
> =A0 fixup_graph->num_vertices++;
> =A0 add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index,
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 SINK_CONNECT_EDGE,
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 0 /* demand_value */, 0, 0 /* demand_=
value */);
> + =A0add_fixup_edge (fixup_graph, new_exit_index, 2 * EXIT_BLOCK + 1,
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0SINK_CONNECT_EDGE,
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A00 /* demand_value */, 0, 0 /* demand=
_value */);
> +
> +
> + =A0/* Create a back edge from the new_exit to the new_entry.
> + =A0 =A0 Initially, its capacity will be set to 0 so that it does not
> + =A0 =A0 affect max flow, but later its capacity will be changed to
> + =A0 =A0 infinity to cancel negative cycles. */
> + =A0add_fixup_edge (fixup_graph, new_exit_index, new_entry_index,
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 SINK_SOURCE_EDGE, 0, 0, 0);
> +
> +
>
> =A0 /* Connect vertices with unbalanced D(v) to source/sink. =A0*/
> =A0 if (dump_file)
> =A0 =A0 fprintf (dump_file, "\nD(v) balance:\n");
> - =A0/* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start wi=
th i =3D 4.
> - =A0 =A0 diff_out_in[v''] will be 0, so skip v'' vertices, hence i +=3D =
2. =A0*/
> - =A0for (i =3D 4; i < new_entry_index; i +=3D 2)
> +
> + =A0/* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start
> + =A0 =A0 with i =3D 4. =A0diff_out_in[v''] should be 0, but may not be d=
ue to
> + =A0 =A0 rounding error. =A0So here we consider all vertices. =A0*/
> + =A0for (i =3D 4; i < new_entry_index; i +=3D 1)
> =A0 =A0 {
> =A0 =A0 =A0 if (diff_out_in[i] > 0)
> =A0 =A0 =A0 =A0{
> @@ -674,7 +707,6 @@ create_fixup_graph (fixup_graph_type *fi
> =A0 =A0 =A0 =A0 =A0 =A0 =A0fprintf (dump_file, "------------------\n");
> =A0 =A0 =A0 =A0 =A0 =A0}
>
> - =A0 =A0 =A0 =A0 pfedge->cost /=3D 2;
> =A0 =A0 =A0 =A0 =A0pfedge->norm_vertex_index =3D new_index;
> =A0 =A0 =A0 =A0 =A0if (dump_file)
> =A0 =A0 =A0 =A0 =A0 =A0{
> @@ -684,7 +716,7 @@ create_fixup_graph (fixup_graph_type *fi
>
> =A0 =A0 =A0 =A0 =A0/* Add a new fixup edge: new_index->src. =A0*/
> =A0 =A0 =A0 =A0 =A0add_fixup_edge (fixup_graph, new_index, pfedge->src,
> - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 REVERSE_NORMALIZED_EDGE=
, 0, r_pfedge->cost,
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 REVERSE_NORMALIZED_EDGE=
, 0, 0,
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0r_pfedge->max_capacity=
);
> =A0 =A0 =A0 =A0 =A0gcc_assert (fixup_graph->num_vertices <=3D fmax_num_ve=
rtices);
>
> @@ -692,7 +724,6 @@ create_fixup_graph (fixup_graph_type *fi
> =A0 =A0 =A0 =A0 =A0 =A0 =A0=3D=3D> r_pfedge->src -> new_index. =A0*/
> =A0 =A0 =A0 =A0 =A0r_pfedge->dest =3D new_index;
> =A0 =A0 =A0 =A0 =A0r_pfedge->type =3D REVERSE_NORMALIZED_EDGE;
> - =A0 =A0 =A0 =A0 r_pfedge->cost =3D pfedge->cost;
> =A0 =A0 =A0 =A0 =A0r_pfedge->max_capacity =3D pfedge->max_capacity;
> =A0 =A0 =A0 =A0 =A0if (dump_file)
> =A0 =A0 =A0 =A0 =A0 =A0dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
> @@ -794,14 +825,12 @@ cancel_negative_cycle (fixup_graph_type
> =A0 bool found_cycle =3D false;
> =A0 int cycle_start =3D 0, cycle_end =3D 0;
> =A0 gcov_type sum_cost =3D 0, cycle_flow =3D 0;
> - =A0int new_entry_index;
> =A0 bool propagated =3D false;
>
> =A0 gcc_assert (fixup_graph);
> =A0 fnum_vertices =3D fixup_graph->num_vertices;
> =A0 fnum_edges =3D fixup_graph->num_edges;
> =A0 fedge_list =3D fixup_graph->edge_list;
> - =A0new_entry_index =3D fixup_graph->new_entry_index;
>
> =A0 /* Initialize. =A0*/
> =A0 /* Skip ENTRY. =A0*/
> @@ -820,8 +849,6 @@ cancel_negative_cycle (fixup_graph_type
> =A0 =A0 for (i =3D 0; i < fnum_edges; i++)
> =A0 =A0 =A0 {
> =A0 =A0 =A0 =A0pfedge =3D fedge_list + i;
> - =A0 =A0 =A0 if (pfedge->src =3D=3D new_entry_index)
> - =A0 =A0 =A0 =A0 continue;
> =A0 =A0 =A0 =A0if (pfedge->is_rflow_valid && pfedge->rflow
> =A0 =A0 =A0 =A0 =A0 =A0 && d[pfedge->src] !=3D CAP_INFINITY
> =A0 =A0 =A0 =A0 =A0 =A0&& (d[pfedge->dest] > d[pfedge->src] + pfedge->cos=
t))
> @@ -843,8 +870,6 @@ cancel_negative_cycle (fixup_graph_type
> =A0 for (i =3D 0; i < fnum_edges; i++)
> =A0 =A0 {
> =A0 =A0 =A0 pfedge =3D fedge_list + i;
> - =A0 =A0 =A0if (pfedge->src =3D=3D new_entry_index)
> - =A0 =A0 =A0 continue;
> =A0 =A0 =A0 if (pfedge->is_rflow_valid && pfedge->rflow
> =A0 =A0 =A0 =A0 =A0 && d[pfedge->src] !=3D CAP_INFINITY
> =A0 =A0 =A0 =A0 =A0&& (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
> @@ -912,10 +937,12 @@ cancel_negative_cycle (fixup_graph_type
> =A0 =A0 {
> =A0 =A0 =A0 pfedge =3D find_fixup_edge (fixup_graph, cycle[k + 1], cycle[=
k]);
> =A0 =A0 =A0 r_pfedge =3D find_fixup_edge (fixup_graph, cycle[k], cycle[k =
+ 1]);
> - =A0 =A0 =A0pfedge->rflow -=3D cycle_flow;
> + =A0 =A0 =A0if (pfedge->rflow !=3D CAP_INFINITY)
> + =A0 =A0 =A0 =A0pfedge->rflow -=3D cycle_flow;
> =A0 =A0 =A0 if (pfedge->type)
> =A0 =A0 =A0 =A0pfedge->flow +=3D cycle_flow;
> - =A0 =A0 =A0r_pfedge->rflow +=3D cycle_flow;
> + =A0 =A0 =A0if (r_pfedge->rflow !=3D CAP_INFINITY)
> + =A0 =A0 =A0 =A0r_pfedge->rflow +=3D cycle_flow;
> =A0 =A0 =A0 if (r_pfedge->type)
> =A0 =A0 =A0 =A0r_pfedge->flow -=3D cycle_flow;
> =A0 =A0 }
> @@ -945,7 +972,8 @@ compute_residual_flow (fixup_graph_type
> =A0 for (i =3D 0; i < fnum_edges; i++)
> =A0 =A0 {
> =A0 =A0 =A0 pfedge =3D fedge_list + i;
> - =A0 =A0 =A0pfedge->rflow =3D pfedge->max_capacity - pfedge->flow;
> + =A0 =A0 =A0pfedge->rflow =3D pfedge->max_capacity =3D=3D CAP_INFINITY ?
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0CAP_INFINITY : pfedge->max_c=
apacity - pfedge->flow;
> =A0 =A0 =A0 pfedge->is_rflow_valid =3D true;
> =A0 =A0 =A0 add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfed=
ge->flow,
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 -pfedge->cost);
> @@ -1070,20 +1098,22 @@ find_max_flow (fixup_graph_type *fixup_g
> =A0 =A0 =A0 =A0{
> =A0 =A0 =A0 =A0 =A0pfedge =3D find_fixup_edge (fixup_graph, bb_pred[u], u=
);
> =A0 =A0 =A0 =A0 =A0r_pfedge =3D find_fixup_edge (fixup_graph, u, bb_pred[=
u]);
> +
> + =A0 =A0 =A0 =A0 =A0if (pfedge->rflow !=3D CAP_INFINITY)
> + =A0 =A0 =A0 =A0 =A0 pfedge->rflow -=3D increment;
> + =A0 =A0 =A0 =A0 =A0if (r_pfedge->rflow !=3D CAP_INFINITY)
> + =A0 =A0 =A0 =A0 =A0 r_pfedge->rflow +=3D increment;
> +
> =A0 =A0 =A0 =A0 =A0if (pfedge->type)
> =A0 =A0 =A0 =A0 =A0 =A0{
> =A0 =A0 =A0 =A0 =A0 =A0 =A0/* forward edge. =A0*/
> =A0 =A0 =A0 =A0 =A0 =A0 =A0pfedge->flow +=3D increment;
> - =A0 =A0 =A0 =A0 =A0 =A0 pfedge->rflow -=3D increment;
> - =A0 =A0 =A0 =A0 =A0 =A0 r_pfedge->rflow +=3D increment;
> =A0 =A0 =A0 =A0 =A0 =A0}
> =A0 =A0 =A0 =A0 =A0else
> =A0 =A0 =A0 =A0 =A0 =A0{
> =A0 =A0 =A0 =A0 =A0 =A0 =A0/* backward edge. =A0*/
> =A0 =A0 =A0 =A0 =A0 =A0 =A0gcc_assert (r_pfedge->type);
> - =A0 =A0 =A0 =A0 =A0 =A0 r_pfedge->rflow +=3D increment;
> =A0 =A0 =A0 =A0 =A0 =A0 =A0r_pfedge->flow -=3D increment;
> - =A0 =A0 =A0 =A0 =A0 =A0 pfedge->rflow -=3D increment;
> =A0 =A0 =A0 =A0 =A0 =A0}
> =A0 =A0 =A0 =A0}
>
> @@ -1302,6 +1332,60 @@ adjust_cfg_counts (fixup_graph_type *fix
> =A0}
>
>
> +/* Called before negative_cycle_cancellation, to form a cycle between
> + * new_exit to new_entry in FIXUP_GRAPH with capacity MAX_FLOW. We
> + * don't want the flow in the BALANCE_EDGE to be modified, so we set
> + * the residural flow of those edges to 0 */
> +
> +static void
> +modify_sink_source_capacity (fixup_graph_type *fixup_graph, gcov_type ma=
x_flow)
> +{
> + =A0fixup_edge_p edge, r_edge;
> + =A0int i;
> + =A0int entry =3D ENTRY_BLOCK;
> + =A0int exit =3D 2 * EXIT_BLOCK + 1;
> + =A0int new_entry =3D fixup_graph->new_entry_index;
> + =A0int new_exit =3D fixup_graph->new_exit_index;
> +
> + =A0edge =3D find_fixup_edge (fixup_graph, new_entry, entry);
> + =A0edge->max_capacity =3D CAP_INFINITY;
> + =A0edge->rflow =3D CAP_INFINITY;
> +
> + =A0edge =3D find_fixup_edge (fixup_graph, entry, new_entry);
> + =A0edge->max_capacity =3D CAP_INFINITY;
> + =A0edge->rflow =3D CAP_INFINITY;
> +
> + =A0edge =3D find_fixup_edge (fixup_graph, exit, new_exit);
> + =A0edge->max_capacity =3D CAP_INFINITY;
> + =A0edge->rflow =3D CAP_INFINITY;
> +
> + =A0edge =3D find_fixup_edge (fixup_graph, new_exit, exit);
> + =A0edge->max_capacity =3D CAP_INFINITY;
> + =A0edge->rflow =3D CAP_INFINITY;
> +
> + =A0edge =3D find_fixup_edge (fixup_graph, new_exit, new_entry);
> + =A0edge->max_capacity =3D CAP_INFINITY;
> + =A0edge->flow =3D max_flow;
> + =A0edge->rflow =3D CAP_INFINITY;
> +
> + =A0r_edge =3D find_fixup_edge (fixup_graph, new_entry, new_exit);
> + =A0r_edge->rflow =3D max_flow;
> +
> + =A0/* Find all the backwards residual edges corresponding to
> + =A0 =A0 BALANCE_EDGEs and set their residual flow to 0 to enforce a
> + =A0 =A0 minimum flow constraint on these edges. */
> + =A0for (i =3D 4; i < new_entry; i +=3D 1)
> + =A0 =A0{
> + =A0 =A0 =A0edge =3D find_fixup_edge (fixup_graph, i, new_entry);
> + =A0 =A0 =A0if (edge)
> + =A0 =A0 =A0 edge->rflow =3D 0;
> + =A0 =A0 =A0edge =3D find_fixup_edge (fixup_graph, new_exit, i);
> + =A0 =A0 =A0if (edge)
> + =A0 =A0 =A0 edge->rflow =3D 0;
> + =A0 =A0}
> +}
> +
> +
> =A0/* Implements the negative cycle canceling algorithm to compute a mini=
mum cost
> =A0 =A0flow.
> =A0Algorithm:
> @@ -1330,13 +1414,18 @@ find_minimum_cost_flow (fixup_graph_type
> =A0 int fnum_vertices;
> =A0 int new_exit_index;
> =A0 int new_entry_index;
> + =A0gcov_type max_flow;
>
> =A0 gcc_assert (fixup_graph);
> =A0 fnum_vertices =3D fixup_graph->num_vertices;
> =A0 new_exit_index =3D fixup_graph->new_exit_index;
> =A0 new_entry_index =3D fixup_graph->new_entry_index;
>
> - =A0find_max_flow (fixup_graph, new_entry_index, new_exit_index);
> + =A0max_flow =3D find_max_flow (fixup_graph, new_entry_index, new_exit_i=
ndex);
> +
> + =A0/* Adjust the fixup graph to translate things into a minimum cost
> + =A0 =A0 circulation problem. */
> + =A0modify_sink_source_capacity (fixup_graph, max_flow);
>
> =A0 /* Initialize the structures for find_negative_cycle(). =A0*/
> =A0 pred =3D (int *) xcalloc (fnum_vertices, sizeof (int));
> @@ -1352,7 +1441,12 @@ find_minimum_cost_flow (fixup_graph_type
> =A0 =A0 =A0 iteration++;
> =A0 =A0 =A0 if (iteration > MAX_ITER (fixup_graph->num_vertices,
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 fixup_gra=
ph->num_edges))
> - =A0 =A0 =A0 =A0break;
> + =A0 =A0 =A0 {
> + =A0 =A0 =A0 =A0 inform (DECL_SOURCE_LOCATION (current_function_decl),
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 "Exiting profile correction early to av=
oid excessive "
> + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 "compile time");
> + =A0 =A0 =A0 =A0 break;
> + =A0 =A0 =A0 }
> =A0 =A0 }
>
> =A0 if (dump_file)
> Index: gcc/params.def
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> --- gcc/params.def =A0 =A0 =A0(revision 174456)
> +++ gcc/params.def =A0 =A0 =A0(working copy)
> @@ -977,6 +977,12 @@ DEFPARAM (MIN_PARTITION_SIZE,
> =A0 =A0 =A0 =A0 =A0"Size of minimal paritition for WHOPR (in estimated in=
structions)",
> =A0 =A0 =A0 =A0 =A01000, 0, 0)
>
> +DEFPARAM (PARAM_MIN_MCF_CANCEL_ITERS,
> + =A0 =A0 =A0 =A0 "min-mcf-cancel-iters",
> + =A0 =A0 =A0 =A0 "the minimum number of iterations of negative cycle can=
cellation "
> + =A0 =A0 =A0 =A0 "in MCF",
> + =A0 =A0 =A0 =A0 10, 1, 0)
> +
> =A0/* Diagnostic parameters. =A0*/
>
> =A0DEFPARAM (CXX_MAX_NAMESPACES_FOR_DIAGNOSTIC_HELP,
>
> --
> This patch is available for review at http://codereview.appspot.com/45361=
06
>