From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 17446 invoked by alias); 2 Jun 2011 18:28:00 -0000 Received: (qmail 17433 invoked by uid 22791); 2 Jun 2011 18:27:57 -0000 X-SWARE-Spam-Status: No, hits=-1.5 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) (74.125.121.67) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 02 Jun 2011 18:27:40 +0000 Received: from wpaz9.hot.corp.google.com (wpaz9.hot.corp.google.com [172.24.198.73]) by smtp-out.google.com with ESMTP id p52IRbXt014535 for ; Thu, 2 Jun 2011 11:27:38 -0700 Received: from pzk36 (pzk36.prod.google.com [10.243.19.164]) by wpaz9.hot.corp.google.com with ESMTP id p52IR14Y009008 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Thu, 2 Jun 2011 11:27:36 -0700 Received: by pzk36 with SMTP id 36so545431pzk.6 for ; Thu, 02 Jun 2011 11:27:35 -0700 (PDT) Received: by 10.68.28.103 with SMTP id a7mr368904pbh.395.1307039255752; Thu, 02 Jun 2011 11:27:35 -0700 (PDT) MIME-Version: 1.0 Received: by 10.142.143.6 with HTTP; Thu, 2 Jun 2011 11:27:15 -0700 (PDT) In-Reply-To: References: <20110602180025.36B301EE08E@martint2.mtv.corp.google.com> From: Martin Thuresson Date: Thu, 02 Jun 2011 18:28:00 -0000 Message-ID: Subject: Re: [google] Use minimum cost circulation, not minimum cost flow to smooth profiles other minor fixes. (issue4536106) To: Xinliang David Li Cc: reply@codereview.appspotmail.com, GCC Patches Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-System-Of-Record: true Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2011-06/txt/msg00181.txt.bz2 On Thu, Jun 2, 2011 at 11:17 AM, Xinliang David Li wro= te: > Counter overflow? Infinite capacity should not be modified. If it is, there is a chance for overflow as it is stored as #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT) Martin > > David > > On Thu, Jun 2, 2011 at 11:12 AM, Martin Thuresson wr= ote: >> On Thu, Jun 2, 2011 at 11:05 AM, Xinliang David Li = wrote: >>> >>> Smoothing works for sample FDO and profile data from multi-threaded >>> programs. You won't see any difference in SPEC. >> >> Dehao reported some performance improvements from the algorithmic improv= ements >> he added in terms of extra fixup edges and handling of infinite capacity. >> >> Martin >> >> >> >> >>> >>> David >>> >>> On Thu, Jun 2, 2011 at 11:00 AM, Martin Thuresson = wrote: >>> > This patch from Neil Vachharajani and Dehao Chen improves mcf by using >>> > minimum cost circulation instead of minimum cost flow to smooth profi= les. >>> > It also introduces a parameter for controlling running time of the al= gorithm. >>> > This was what was originally presented in the academic work and handl= es >>> > certain cases where the function entry and exit have incorrect profile >>> > weights. >>> > >>> > For now, this is for google/main. Once I have collected performance r= esults >>> > 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, Dehao Chen >>> > =A0 =A0 =A0 =A0 >>> > >>> > =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_CA= NCEL_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 circul= ation. >>> > =A0 =A0 =A0 =A0(cancel_negative_cycle): Update handling of infinite c= apacity. >>> > =A0 =A0 =A0 =A0(compute_residual_flow): Update handling of infinite c= apacity. >>> > =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 ci= rculation. >>> > =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 duri= ng >>> > +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 = ensure >>> > =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 transform= ation. =A0*/ >>> > =A0 REVERSE_EDGE, >>> > =A0 SOURCE_CONNECT_EDGE, =A0 =A0 /* Single edge connecting to single = source. =A0*/ >>> > =A0 SINK_CONNECT_EDGE, =A0 =A0 =A0 /* Single edge connecting to singl= e sink. =A0*/ >>> > + =A0SINK_SOURCE_EDGE, =A0 =A0 =A0 =A0/* Single edge connecting sink = to source. =A0*/ >>> > =A0 BALANCE_EDGE, =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0/* Edge conn= ecting 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 = there is 1 edge >>> > + =A0 =A0 connecting new_entry and new_exit, and 2 edges connecting n= ew_entry 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 ca= lculation. >>> > =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_basi= c_blocks); >>> > @@ -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-= >count, >>> > =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, SOURC= E_CONNECT_EDGE, >>> > - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 1 /* supply_value */, 0, 1 /* suppl= y_value */); >>> > + =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_va= lue */, 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= _value */, 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->n= um_vertices; >>> > =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 /* dem= and_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 /* de= mand_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 star= t with 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 due 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->sr= c, >>> > - =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_capa= city); >>> > =A0 =A0 =A0 =A0 =A0gcc_assert (fixup_graph->num_vertices <=3D fmax_nu= m_vertices); >>> > >>> > @@ -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_pfe= dge); >>> > @@ -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-= >cost)) >>> > @@ -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->cos= t)) >>> > @@ -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], cy= cle[k]); >>> > =A0 =A0 =A0 r_pfedge =3D find_fixup_edge (fixup_graph, cycle[k], cycl= e[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_INFINI= TY ? >>> > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0CAP_INFINITY : pfedge->m= ax_capacity - pfedge->flow; >>> > =A0 =A0 =A0 pfedge->is_rflow_valid =3D true; >>> > =A0 =A0 =A0 add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, = pfedge->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_p= red[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_typ= e max_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 = minimum 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_ex= it_index); >>> > + >>> > + =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= _graph->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 t= o avoid 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 estimate= d instructions)", >>> > =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= cancellation " >>> > + =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/4= 536106 >>> > >> >