Re: Ping agian: [PATCH V2] Loop split upon semi-invariant condition (PR tree-optimization/89134)

[Feng Xue OS <fxue at os dot amperecomputing dot com>]

Hi, Michael,

  Since I was involved in other tasks, it is a little bit late to reply you. Sorry
for that. I composed a new one with your suggestions. Please review that
when you are in convenience. 

> Generally I do like the idea of the transformation, and the basic building
> blocks seem to be sound.  But I dislike it being a separate pass, so
> please integrate the code you have written into the existing loop split
> pass.  Most building blocks can be used as is, except the main driver.
This new transformation was integrated into the pass of original loop split.

>> +@item max-cond-loop-split-insns
>> +The maximum number of insns to be increased due to loop split on
>> +semi-invariant condition statement.

> "to be increased" --> "to be generated" (or "added")
Done.

>> +@item min-cond-loop-split-prob
>> +The minimum threshold for probability of semi-invaraint condition
>> +statement to trigger loop split.

> typo, semi-invariant
Done.

> I think somewhere in the docs your definition of semi-invariant needs
> to be stated in some form (can be short, doesn't need to reproduce the
> diagram or such), so don't just replicate the short info from the
> params.def file.
Done.

>> +DEFPARAM(PARAM_MIN_COND_LOOP_SPLIT_PROB,
>> +       "min-cond-loop-split-prob",
>> +       "The minimum threshold for probability of semi-invaraint condition "
>> +       "statement to trigger loop split.",

> Same typo: "semi-invariant".
Done.

>> -/* This file implements loop splitting, i.e. transformation of loops like
>> +/* This file implements two kind of loop splitting.

> kind_s_, plural
Done.

>> +/* Another transformation of loops like:
>> +
>> +   for (i = INIT (); CHECK (i); i = NEXT ())
>> +     {
>> +       if (expr (a_1, a_2, ..., a_n))
>> +         a_j = ...;  // change at least one a_j
>> +       else
>> +         S;          // not change any a_j
>> +     }

> You should mention that 'expr' needs to be pure, i.e. once it
> becomes false and the inputs don't change, that it remains false.
Done.

>> +static bool
>> +branch_removable_p (basic_block branch_bb)
>> +{
>> +  if (single_pred_p (branch_bb))
>> +    return true;
>> +
>> +  edge e;
>> +  edge_iterator ei;
>> +
>> +  FOR_EACH_EDGE (e, ei, branch_bb->preds)
>> +    {
>> +      if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb))
>> +       continue;
>> +
>> +      if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src))
>> +       continue;

> My gut feeling is surprised by this.  So one of the predecessors of
> branch_bb dominates it.  Why should that indicate that branch_bb
> can be safely removed?
>
> Think about something like this:
>
>   esrc --> cond_bb --> branch_bb
>   '-------------------^

If all predecessors of branch_bb dominate it, these predecessors should also
be in dominating relationship among them, and the conditional statement must
be branch_bb's immediate dominator, and branch_bb is removable. In your example.

For "esrc", loop is continued, nothing is impacted. But in the next iteration, we
encounter "cond_bb", it does not dominate "branch_bb", so the function return
false in the following return statement.

> (cond_bb is the callers bb of the cond statement in question).  Now esrc
> dominates branch_bb but still you can't simply remove it, even if
> the cond_bb->branch_bb edge becomes unexecutable.


>> +static int
>> +get_cond_invariant_branch (struct loop *loop, gcond *cond)

> Please return an edge here, not an edge index (which removes the using of
> -1).  I think the name (and comment) should consistently talk about
> semi-invariant, not invariant.  For when you really need an edge index
> later, you could use "EDGE_SUCC(bb, 0) != edge".  But you probably don't
> really need it, e.g. instead of using the gimple pass-local-flag on a
> statement you can just as well also store the edge in your info structure.
Done.

>> +static bool
>> +is_cond_in_hidden_loop (const struct loop *loop, basic_block cond_bb,
>> +                       int branch)

> With above change in get_cond_invariant_branch, this also should
> take an edge, not a bb+edge-index.
Done.

>> +static int
>> +compute_added_num_insns (struct loop *loop, const_basic_block cond_bb,
>> +                        int branch)

> This should take an edge as well.
Done.

>> +  for (unsigned i = 0; i < loop->num_nodes; i++)
>> +    {
>> +      /* Do no count basic blocks only in opposite branch.  */
>> +      if (dominated_by_p (CDI_DOMINATORS, bbs[i], targ_bb_var))
>> +       continue;
>> +
>> +      for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);
>> +          gsi_next (&gsi))
>> +       num += estimate_num_insns (gsi_stmt (gsi), &eni_size_weights);

> Replace the loop by
>  estimate_num_insn_seq (bb_seq (bbs[i]), &eni_size_weights);
Done.


>> +  /* Add a threshold for increased code size to disable loop split.  */
>> +  if (compute_added_num_insns (loop, cond_bb, branch) >
>> +      PARAM_VALUE (PARAM_MAX_COND_LOOP_SPLIT_INSNS))

> Operator should be first on next line, not last on previous line.
Done.

>> +  /* Skip conditional statement that is inside a nested unrecognized loop.  */
>> +  if (is_cond_in_hidden_loop (loop, cond_bb, branch))
>> +    return false;

> This part (as well as is_cond_in_hidden_loop implementation) had me
> confused for a while, because "unrecognized" loops seems strange.  I think
> I now know what you try to do here, but I wonder if there's an easier way,
> or at least about which situations you stumbled into that made you write
> this code.
Use BB_IRREDUCIBLE_LOOP flag to check that, for tree-loop-init pass 
requires LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS which marks
irreducible loops.

>> +
>> +  /* Temporarily keep branch index in conditional statement.  */
>> +  gimple_set_plf (cond, GF_PLF_1, branch);

> i.e. here, store the edge in your info structure.
Done.

>> +/* Main entry point to perform loop splitting for suitable if-conditions
>> +   in all loops.  */
>> +
>> +static unsigned int
>> +tree_ssa_split_loops_for_cond (void)

> So, from here on the code should be integrated into the existing code
> of the file (which might need changes as well for this integration to look
> good).
Done.

Thanks,
Feng