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

[Vinodha Ramasamy]

Hi Ralf,

    Thanks for the comments. I will fix the typos and the Makefile
dependencies. During code reviews, it was decided that mpfr routines
are too expensive (compile-time overhead) and not necessary for our
purpose. We are using them to calculate cost functions, so we only
need approximations of these routines.

Best,
    Vinodha

On Tue, Jul 8, 2008 at 10:42 PM, Ralf Wildenhues <Ralf.Wildenhues@gmx.de> wrote:
> Hello,
>
> a couple of quick observations:
>
> * Vinodha Ramasamy wrote on Wed, Jul 09, 2008 at 01:47:47AM CEST:
>>
>>         * 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.
>
> Since profile.c now #include's profile.h, you need to add that as
> dependency to the profile.o rule in Makefile.in.  Also, it seems to
> me the mcf.o rule lists a lot less dependencies than #include's listed
> in mcf.c.
>
>>         (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.
>>         * profile.h: New file.
>
>> --- mcf.c       (revision 0)
>> +++ mcf.c       (revision 0)
>
>> +  /* Fixup vertex list. Adjancency list for fixup graph. */
>
> Adjacency
>
>> +  fixup_vertex_p vertex_list;
>
>> +/* Routines to calculate ln (approximate) and sqrt functions. */
>> +static double mcf_ln (double x);
>> +static double mcf_sqrt (double x);
>
> I wonder why you don't use the mpfr versions of these functions.
>
>> +static void
>> +find_minimum_cost_flow (fixup_graph_type *fixup_graph)
>> +{
>> +  /* Holds the index of predessor in path. */
>
> predecessor
>
>> +  int *pred;
>
>> +/* 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)
>> +   The following are allocated/freed by the caller:
>> +   pi - Vector to hold predessors in path  (pi = pred index)
>
> Likewise.
>
>> +   d - d[i] holds minimum cost of path from i to sink
>> +   cycle - Vector to hold the minimum cost cycle
>
> Cheers,
> Ralf
>