[PATCH] Make LIM able to hoist PHI nodes

[Steven Bosscher]

On Mon, May 3, 2010 at 1:06 PM, Richard Guenther <rguenther@suse.de> wrote:
>
> Working on hoisting malloc/free pairs out of loops (coming from
> Fortran array temporaries)

Yay.

What does this mean for the unswitching pass? It'd be interesting to
know the numbers before/after your patch for how often unswitching
applies. (Unrelated note: why do we still have the RTL unswitching
pass?)

> --- 519,526 ----
>    unsigned cost = 1;
>
>    /* Always try to create possibilities for unswitching.  */
> !   if (gimple_code (stmt) == GIMPLE_COND
> !       || gimple_code (stmt) == GIMPLE_PHI)
>      return LIM_EXPENSIVE;

So hoisting a PHI is always expensive? I doubt that's true. If a PHI
controls loop invariant code, it's likely more profitable to hoist it
than to unswitch the loop on it (and discover after unswitching that
the code is invariant). Am I missing something?


> --- 736,810 ----
>      level = superloop_at_depth (loop, 1);
>    lim_data->max_loop = level;
>
> !   if (gimple_code (stmt) == GIMPLE_PHI)
> !     {
> !       use_operand_p use_p;
> !       unsigned min_cost = 1000;

Magic number, based on...?

> !       unsigned total_cost = 0;
> !       struct lim_aux_data *def_data;
> !
> !       /* We will end up promoting dependencies to be unconditionally
> !        evaluated.  Thus the cost is slighty complicated.  */
> !       FOR_EACH_PHI_ARG (use_p, stmt, iter, SSA_OP_USE)
> !       {
> !         val = USE_FROM_PTR (use_p);
> !         if (TREE_CODE (val) != SSA_NAME)
> !           continue;
> !         if (!add_dependency (val, lim_data, loop, false))
> !           return false;
> !         def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
> !         if (def_data)
> !           {
> !             min_cost = MIN (min_cost, def_data->cost);
> !             total_cost += def_data->cost;
> !           }

So a data ref is never more expensive than min_cost? I don't
understand this part of the patch.


> !       }
> !
> !       lim_data->cost += min_cost;

Make it unconditionally more expensive?

Perhaps you can add comments explaining this cost model. As you say,
it's slighty complicated.


> *************** determine_invariantness_stmt (struct dom
> *** 920,925 ****
> --- 1045,1081 ----
>      fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
>             bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
>
> +   /* Look at PHI nodes, but only if there is a single one only.  */

Maybe it's possible to allow only a single GIMPLE_REG PHI, but also
allow an extra PHI for a memory op? That way you could hoist invariant
loads too.


> +       if (gimple_phi_num_args (stmt) == 1)

Just for my understanding: single-argument PHIs you run into are
probably PHIs for loop-closed SSA form, right? If that's the case,
then perhaps...

> +       {
> +         tree arg = PHI_ARG_DEF (stmt, 0);
> +         new_stmt = gimple_build_assign_with_ops (TREE_CODE (arg),
> +                                                  gimple_phi_result (stmt),
> +                                                  arg, NULL_TREE);
> +         SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
> +       }

... you don't have to build a new PHI here if you move the invariant
out of the loop. OTOH perhaps that just complicates the logic, not
sure.


> +       else
> +       {
> +         basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
> +         gimple cond = gsi_stmt (gsi_last_bb (dom));
> +         tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
> +         /* Get the PHI arguments corresponding to the true and false
> +            edges of COND.  */
> +         extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
> +         gcc_assert (arg0 && arg1);
> +         t = build2 (gimple_cond_code (cond), boolean_type_node,
> +                     gimple_cond_lhs (cond), gimple_cond_rhs (cond));
> +         t = build3 (COND_EXPR, TREE_TYPE (gimple_phi_result (stmt)),
> +                     t, arg0, arg1);
> +         new_stmt = gimple_build_assign_with_ops (COND_EXPR,
> +                                                  gimple_phi_result (stmt),
> +                                                  t, NULL_TREE);
> +         SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
> +         *((unsigned int *)(dw_data->global_data)) |= TODO_cleanup_cfg;
> +       }
> +       gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
> +       remove_phi_node (&bsi, false);
> +     }
> +

Not really related to this patch: Is this COND_EXPR later expanded to
real control flow, or does it live on as a COND_EXPR all the way
through to expand? If the former -- there were reasons not to do this
in e.g. PHIOPT but I don't remember the details. But if this now
works, perhaps we can move bits of ifcvt.c to the GIMPLE level too...

Ciao!
Steven