[PATCH] Loop unswitching: support gswitch statements.

Richard Biener richard.guenther@gmail.com
Fri Nov 19 09:49:29 GMT 2021

On Tue, Nov 16, 2021 at 2:53 PM Martin Liška <mliska@suse.cz> wrote:
> On 11/11/21 08:15, Richard Biener wrote:
> > If you look at simplify_using_entry_checks then this is really really simple,
> > so I'd try to abstract this, recording sth like a unswitch_predicate where
> > we store the condition we unswitch on plus maybe cache the constant
> > range of a VAR cmp CST variable condition on the true/false edge.  We
> > can then try to simplify each gcond/gswitch based on such an unswitch_predicate
> > (when we ever scan the loop once to discover all opportunities we'd have a
> > set of unswitch_predicates to try simplifying against).  As said the integer
> > range thing would be an improvement over the current state so even that
> > can be done as followup but I guess for gswitch support that's going to be
> > the thing to use.
> I started working on the unswitch_predicate where I recond also true/false-edge irange
> of an expression we unswitch on.
> I noticed one significant problem, let's consider:
>    for (int i = 0; i < size; i++)
>    {
>      double tmp;
>      if (order == 1)
>        tmp = -8 * a[i];
>      else
>        {
>         if (order == 2)
>           tmp = -4 * b[i];
>         else
>           tmp = a[i];
>        }
>      r[i] = 3.4f * tmp + d[i];
>    }
> We can end up with first unswitching candidate being 'if (order == 2)' (I have a real benchmark where it happens).
> So I collect ranges and they are [2,2] for true edge and [-INF, 0], [3, INF] (because we came to the condition through order != 1 cond).

You can only record a range from the unswitch condition itself, not
from the path you came, so your false edge range
looks wrong.

> Then the loop is cloned and we have

> if (order == 2)
>     loop_version_1
> else
>     loop_version_2
> but in loop_version_2 we wrongly fold 'if (order == 1)' to false because it's reflected in the range.

Of course for loop_version_1 the range is [2, 2] and for
loop_version_2 it is ~[2, 2] - you
do have to invert the range when folding the "false" version.

> So the question is, can one iterate get_loop_body stmts in some dominator order?

I don't think this would fix anything, but yes, in the end we'd like
to unswitch on "outer" conditions
first.  That would mean iterating blocks in program order, the easiest
way is to use
get_loop_body_in_dom_order which should fix the above testcase but
likely not arbitrary
nested ifs.  For those you could use
rev_post_order_and_mark_dfs_back_seme, but as said
using get_loop_body_in_dom_order should be a strict improvement even
without any other
change (you could propose a patch if you have a testcase that shows a
difference with
otherwise unchanged unswitching, for example choosing the outer condition
instead of the inner with --param max-unswitch-level==0).


> Thanks,
> Martin

More information about the Gcc-patches mailing list