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

[Ralf Wildenhues]

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