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

["Vinodha Ramasamy" <vinodha at google dot 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
Description: Binary data