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]

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


Committed as revision 139208.

Seongbae

On Wed, Aug 13, 2008 at 12:36 PM, Vinodha Ramasamy <vinodha@google.com> wrote:
> 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.
>> > >
>

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]