Re: [PATCH] Profile feedback: Use Minimum Cost Flow algorithm to smooth inconsistent edge counts

["Seongbae Park (박성배, 朴成培)" <seongbae dot park at gmail dot com>]

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.
> >