Optimize df_worklist_dataflow

[Steven Bosscher]

On Sat, Jun 12, 2010 at 3:40 PM, Jan Hubicka <hubicka@ucw.cz> wrote:


> Everythign in the main dataflow loop seems performance critical, so one age
> is stored in vector and the last change age (that is accessed more times)
> in the AUX field of BB structure.

Why not store both in a vector?  I really dislike using the void*
pointer aux field for an integer value, casting back-and-forth from
(void*) to (size_t).


>        * df-problems.c (df_rd_confluence_n, df_lr_confluence_n, df_live_confluence_n,
>        df_byte_lr_confluence_n, df_md_confluence_n): Return true if something changed.
>        * df.h (df_confluence_function_n): Return bool.
>        * df-core.c (df_worklist_propagate_forward, df_worklist_propagate_backward):
>        track changes and ages.

Nit: s/track/Track/

You should also explain the algorithmic changes you're making. This
"age" trick is not found in text-book dataflow solvers, so it's not as
obvious as the existing code. Therefore, please add a not-too-small
comment explaining what the algorithm is doing. Probably belongs
somewhere before df_worklist_dataflow().


> -static void
> +static bool
>  df_lr_confluence_n (edge e)
...
> -  bitmap_ior_into (op1, &df->hardware_regs_used);
> +  return bitmap_ior_into (op1, &df->hardware_regs_used) || changed;

For readability I prefer,
  changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
  return changed;


> +static bool
>  df_byte_lr_confluence_n (edge e)
...
> -    bitmap_ior_and_compl_into (op1, op2, &problem_data->invalidated_by_call);
> +    changed = bitmap_ior_and_compl_into (op1, op2, &problem_data->invalidated_by_call);

Long line, please break it.

>   else
> -    bitmap_ior_into (op1, op2);
> +    changed = bitmap_ior_into (op1, op2);
>
> -  bitmap_ior_into (op1, &problem_data->hardware_regs_used);
> +  return bitmap_ior_into (op1, &problem_data->hardware_regs_used) || changed;

Same comment as for df_lr_confluence_n: please "return changed;" on a
separate line.


> +static bool
>  df_md_confluence_n (edge e)
...
>   if (e->flags & EDGE_EH)
> -    bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
> +    return bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);

Another long line.


>  /* Free all storage associated with the problem.  */
> Index: df.h
> ===================================================================
> --- df.h        (revision 160661)
> +++ df.h        (working copy)
> @@ -223,7 +223,7 @@ typedef void (*df_dataflow_function) (st
>  typedef void (*df_confluence_function_0) (basic_block);
>
>  /* Confluence operator for blocks with 1 or more out (or in) edges.  */
> -typedef void (*df_confluence_function_n) (edge);
> +typedef bool (*df_confluence_function_n) (edge);

Already mentioned: Please add a comment what the return value should be.


>  /* Transfer function for blocks.  */
>  typedef bool (*df_transfer_function) (int);
> Index: df-core.c
> ===================================================================
> --- df-core.c   (revision 160661)
> +++ df-core.c   (working copy)
> @@ -858,28 +858,35 @@ struct rtl_opt_pass pass_df_finish =
>    and set bits on for successors in PENDING
>    if the out set of the dataflow has changed. */
>
> -static void
> +static bool

Document return value in the pre-function comment.

>  df_worklist_propagate_forward (struct dataflow *dataflow,
>                                unsigned bb_index,
>                                unsigned *bbindex_to_postorder,
>                                bitmap pending,
> -                               sbitmap considered)
> +                               sbitmap considered,
> +                              size_t age)

Document the new parameter in the pre-function comment.


>  {
>   edge e;
>   edge_iterator ei;
>   basic_block bb = BASIC_BLOCK (bb_index);
> +  bool changed = !age;
>
>   /*  Calculate <conf_op> of incoming edges.  */
>   if (EDGE_COUNT (bb->preds) > 0)
>     FOR_EACH_EDGE (e, ei, bb->preds)
>       {
> -        if (TEST_BIT (considered, e->src->index))
> -          dataflow->problem->con_fun_n (e);
> +        if ((age <= (size_t)e->src->aux)

Yuck!


> +            && TEST_BIT (considered, e->src->index))
> +          changed |= dataflow->problem->con_fun_n (e);
>       }
>   else if (dataflow->problem->con_fun_0)
> -    dataflow->problem->con_fun_0 (bb);
> +    {
> +      dataflow->problem->con_fun_0 (bb);
> +      changed = true;

I guess it's not very important for what you're trying to achieve, but
why do you have to set changed = true always after con_fun_0? It makes
you run the transfer function and propagated "changed-ness" all over.
So IIUC, e.g. for a forward propagation that starts with a maximum set
you always propagate changed to all successors.

Am I missing something?


> -static void
> +static bool
>  df_worklist_propagate_backward (struct dataflow *dataflow,
>                                 unsigned bb_index,
>                                 unsigned *bbindex_to_postorder,
>                                 bitmap pending,
> -                                sbitmap considered)
> +                                sbitmap considered,
> +                               size_t age)

Return value and new age argument should be documented.


> +DEF_VEC_I(size_t);
> +DEF_VEC_ALLOC_I(size_t,heap);

> @@ -941,46 +960,65 @@ df_worklist_dataflow_doublequeue (struct
>                                  bitmap pending,
>                                   sbitmap considered,
>                                   int *blocks_in_postorder,
> -                                 unsigned *bbindex_to_postorder)
> +                                 unsigned *bbindex_to_postorder,
> +                                 int n_blocks)

Document n_blocks please.


Looks OK to me otherwise.

Ciao!
Steven