This is the mail archive of the
`gcc-patches@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: "Vinodha Ramasamy" <vinodha at google dot com>*To*: "Seongbae Par k (ëìë, ææå)" <seongbae dot park at gmail dot com>*Cc*: gcc-patches <gcc-patches at gcc dot gnu dot org>*Date*: Wed, 13 Aug 2008 12:36:49 -0700*Subject*: Re: [PATCH] Profile feedback: Use Minimum Cost Flow algorithm to smooth inconsistent edge counts*References*: <7b8274c30807081647l70da0e78qc1a10ce3cc08cd9b@mail.gmail.com> <488A1342.3060105@google.com> <7b8274c30807281108k26c67535icd74b32eb0a78fa6@mail.gmail.com> <7b8274c30807311635y31f6a8c5m337d4ac157c5b127@mail.gmail.com> <7b8274c30808051026s1fe0b9a1m43f71e55a9ce59fe@mail.gmail.com> <ab3a61990808121619x227ab4e8uc1d3dd89a842df38@mail.gmail.com>

Hi Seongbae, Here's the patch as requested: Added documentation in doc/invoke.texi Updated to latest trunk ChangeLog not included in patch - inlined below. ChangeLog entry: 2008-08-13 Paul Yuan <yingbo.com@gmail.com> Vinodha Ramasamy <vinodha@google.com> * cgraph.c (cgraph_edge): Handle inconsistent counts when setting count_scale. * value-prof.c (check_counter): Fix the counter if flag_profile_correction is true. (tree_divmod_fixed_value_transform, tree_mod_pow2_value_transform, tree_mod_subtract_transform): Follow check_counter parameter change. * common.opt (fprofile-correction): New option. * mcf.c: New file. * profile.c (edge_info, EDGE_INFO): Moved to new file profile.h. (sum_edge_counts, is_edge_inconsistent, correct_negative_edge_counts, is_inconsistent, set_bb_counts, read_profile_edge_counts): New functions. (compute_branch_probabilities): Refactored. Invokes mcf_smooth_cfg if flag_profile_correction is set. Best, Vinodha On Tue, Aug 12, 2008 at 4:19 PM, Seongbae Park (ëìë, ææå) <seongbae.park@gmail.com> wrote: > > Can you add a documentation for the new option in doc/invoke.texi ? > Also, please update the patch with the latest trunk (there's a minor conflict). > The patch file should not include changes to ChangeLog, > and ChangeLog entry should be inlined in the email (I know, it's a pain). > Once that's done, I'll apply the patch, since Diego already gave OK. > Thanks! > > Seongbae > > On Tue, Aug 5, 2008 at 10:26 AM, Vinodha Ramasamy <vinodha@google.com> wrote: > > > > ---------- Forwarded message ---------- > > From: Vinodha Ramasamy <vinodha@google.com> > > Date: Thu, Jul 31, 2008 at 4:35 PM > > Subject: Re: [PATCH] Profile feedback: Use Minimum Cost Flow algorithm > > to smooth inconsistent edge counts > > To: Diego Novillo <dnovillo@google.com> > > Cc: Seongbae Park <spark@google.com>, Paul Yuan <yingbo.com@gmail.com> > > > > > > Hi Diego, > > > > I've incorporated your review comments. This patch also fixes the > > following bugs introduced by the new code: > > 1. cancel_negative_cycle() in mcf.c - Need to check for overflow. > > Added check d[pfedge->src] != CAP_INFINITY. Also restrict the number > > of iterations of cancel_negative_cycle to MAX_ITER to control > > compile-time. > > 2. read_profile_edge_counts() in profile.c - exec_counts_pos should be > > initialized outside the loop. > > > > Please find the patch attached to be submitted. Verified that > > bootstrap build and gcc regression tests pass. > > > > Best, > > Vinodha > > > > > > On Mon, Jul 28, 2008 at 11:08 AM, Vinodha Ramasamy <vinodha@google.com> wrote: > > > > > > Hi Diego, > > > > > > Thanks for the review. I'm incorporated the review feedback. Will send out a revised patch when I'm done. > > > > > > Best, > > > Vinodha > > > > > > > > > On Fri, Jul 25, 2008 at 10:54 AM, Diego Novillo <dnovillo@google.com> wrote: > > >> > > >> On 7/8/08 7:47 PM, Vinodha Ramasamy wrote: > > >> > > >>> if (node->call_site_hash) > > >>> return (struct cgraph_edge *) > > >>> - htab_find_with_hash (node->call_site_hash, call_stmt, > > >>> - htab_hash_pointer (call_stmt)); > > >>> + htab_find_with_hash (node->call_site_hash, call_stmt, > > >>> + htab_hash_pointer (call_stmt)); > > >> > > >> This hunk doesn't seem to be changing anything. > > >> > > >>> + if (flag_profile_correction) > > >>> + { > > >>> + inform ("%HCorrecting inconsistent value profile: " > > >>> + "%s profiler count is inconsistent", > > >>> + locus, name); > > >>> + *all = bb_count; > > >>> + if (*count > *all) *count = *all; > > >> > > >> The assignment inside the 'if' should go in the next line. > > >> > > >>> +/* References: > > >>> + [1] "Feedback-directed Optimizations in GCC with Estimated Edge Profiles > > >>> + from Hardware Event Sampling", Vinodha Ramasamy, Paul Yuan, Dehao Chen, > > >>> + and Robert Hundt; GCC Summit 2008. > > >>> + [2] "Complementing Missing and Inaccurate Profiling Using a Minimum Cost > > >>> + Circulation Algorithm", Roy Levin, Ilan Newman and Gadi Haber; > > >>> + HiPEAC '08. > > >>> + > > >>> +*/ > > >> > > >> Closing comment goes on same line as ending period. > > >> > > >> Could you also add a high-level description of the algorithm? Nothing > > >> elaborate, but enough detail that one can follow it and it's tied to the > > >> functions in the file. > > >> > > >>> +/* CAP_INFINITY: Constant to represent infinite capacity. */ > > >>> +#define CAP_INFINITY __LONG_LONG_MAX__ > > >>> + > > >> > > >> Two spaces after final '.'. Happens in a few places in the file. > > >> > > >>> +typedef struct _queue > > >>> +{ > > >>> + int *queue; > > >>> + int head; > > >>> + int tail; > > >>> + int size; > > >>> +} queue_type; > > >>> + > > >>> +/* Structure used in the maximal flow routines to find augmenting path. */ > > >>> +typedef struct _augmenting_path > > >> > > >> I think that identifiers starting with '_' are reserved, but I am not > > >> sure about this. The informal convention we follow is to call structs > > >> 'struct NAME_d' and the typedefs 'NAME' or 'NAME_t'. It's certainly not > > >> followed consistently, though. > > >> > > >> > > >>> +/* Dump routines for debugging. */ > > >>> +/* Dump edge_f[u,v]. */ > > >>> +static void dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, > > >>> + fixup_edge_p pfedge); > > >>> +static void dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, > > >>> + const char *msg); > > >>> +static void print_basic_block (FILE *file, fixup_graph_type *fixup_graph, > > >>> + int n); > > >>> +static void print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, > > >>> + int d); > > >> > > >> Unless you need static declarations to break circular references, the > > >> convention is to define static functions before their callers. This > > >> convention helps with readability because it tends to cluster the big > > >> entry points and high-level functionality at the bottom of the file. > > >> > > >> Also, comments describing what a function does should go in the function > > >> definition, not its declaration. > > >> > > >>> + > > >>> + > > >>> +/* Function definitions. */ > > >>> +/* ln() implementation: approximate calculation. */ > > >>> + > > >>> +static double > > >>> +mcf_ln (double x) > > >> > > >> Missing documentation for X. > > >> > > >>> +/* sqrt() implementation: based on open source QUAKE3 code by Carmack. > > >>> + Original code is under GPL */ > > >>> + > > >>> + > > >>> +static double > > >>> +mcf_sqrt (double x) > > >> > > >> Likewise. Only one blank line after comment. No need to specify what > > >> type of license the original code is under. Do you have a more specific > > >> reference to the original code? > > >> > > >>> + return 0.5f * (convertor.floatPart + (x * convertor2.floatPart)); > > >>> +} > > >>> + > > >>> +void > > >>> +mcf_smooth_cfg (void) > > >>> +{ > > >> > > >> Needs documentation. > > >> > > >>> +/* Common code to add edge shared between add_fixup_edge and add_rfixup_edge */ > > >>> + > > >>> +static fixup_edge_p > > >>> +add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost) > > >> > > >> Likewise. Also comments should end with '. */' > > >> > > >> Several other functions are missing documentation or documentation of > > >> their arguments. I've only marked these two. > > >> > > >>> + > > >>> +/* cancel_negative_cycle: Finds a negative cycle in the residual network using > > >>> + 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 > > >>> + considered. > > >>> + > > >>> +Parameters: > > >>> + fixup_graph - Residual graph (input/output) > > >> > > >> When referring to arguments and local variables, the convention is to capitalize them. > > >> > > >>> + > > >>> +static void > > >>> +enqueue (queue_type *queue_list, int x) > > >>> +{ > > >>> + gcc_assert (queue_list->tail < queue_list->size); > > >>> + queue_list->queue[queue_list->tail] = x; > > >> > > >> Would it make sense to implement this queue with VEC()? It may simplify some of the management. > > >> > > >>> + > > >>> + FOR_EACH_EDGE (e, ei, to_edges) > > >>> + { > > >>> + sum += e->count; > > >>> + } > > >> > > >> Braces are not needed here. > > >> > > >>> + return sum; > > >>> +} > > >>> + > > >>> + > > >>> +/* adjust_cfg_counts: Computes the corrected edge and basic block > > >> > > >> No need to include the function name in the comment. > > >> > > >>> > > >>> -/* Compute the branch probabilities for the various branches. > > >>> - Annotate them accordingly. */ > > >>> +/* Return the sum of count of all edges of the given "edges" set */ > > >> > > >> s/"edges"/EDGES/ > > >> > > >>> + > > >>> +static bool > > >>> +is_edge_inconsistent (VEC(edge,gc) *edges) > > >> > > >> Needs comment. > > >> > > >> > > >> > > >> I have no comments on the algorithm itself other than it reads well and seems easy to follow. > > >> > > >> The patch looks fine to me with the revisions I suggested. > > >> > > >> > > >> Thanks. Diego. > > >

**Attachment:
mcf_patch**

**Follow-Ups**:

**References**:**Fwd: [PATCH] Profile feedback: Use Minimum Cost Flow algorithm to smooth inconsistent edge counts***From:*Vinodha Ramasamy

**Re: [PATCH] Profile feedback: Use Minimum Cost Flow algorithm to smooth inconsistent edge counts***From:*Seongbae Park (박성배, 朴成培)

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |