[PATCH] Loop unswitching: support gswitch statements.

[Aldy Hernandez]

On Wed, Nov 24, 2021 at 9:00 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Tue, Nov 23, 2021 at 5:36 PM Martin Liška <mliska@suse.cz> wrote:
> >
> > On 11/23/21 16:20, Martin Liška wrote:
> > > Sure, so for e.g. case 1 ... 5 we would need to create a new unswitch_predicate
> > > with 1 <= index && index <= 5 tree predicate (and the corresponding irange range).
> > > Later once we unswitch on it, we should use a special unreachable_flag that will
> > > be used for marking of dead edges (similarly how we fold gconds to boolean_{false/true}_node.
> > > Does it make sense?
> >
> > I have thought about it more and it's not enough. What we really want is having a irange
> > for *each edge* (2 for gconds and multiple for gswitchs). Once we select a unswitch_predicate,
> > then we need to fold_range in true/false loop all these iranges. Doing that we can handle situations like:
> >
> > if (index < 1)
> >     do_something1
> >
> > if (index > 2)
> >     do_something2
> >
> > switch (index)
> >     case 1 ... 2:
> >       do_something;
> > ...
> >
> > as seen the once we unswitch on 'index < 1' and 'index > 2', then the first case will be taken in the false_edge
> > of 'index > 2' loop unswitching.
>
> Hmm.  I'm not sure it needs to be this complicated.  We're basically
> evaluating ranges/predicates based
> on a fixed set of versioning predicates.  Your implementation created
> "predicates" for the to be simplified
> conditions but in the end we like to evaluate the actual stmt to
> figure the taken/not taken edges.  IIRC
> elsewhere Andrew showed a snipped on how to evaluate a stmt with a
> given range - not sure if that
> was useful enough.  So what I think would be nice if we could somehow
> use rangers path query
> without an actual CFG.  So we virtuall have
>
>   if (versioning-predicate1)
>     if (versioning-predicate2)
>        ;
>    else
>       for (;;) // out current loop
>         {
>           ...
>               if (condition)
>                 ;
>          ...
>               switch (var)
>                  {
> ...
>                   }
>         }
>
> and versioning-predicate1 and versioning-predicate2 are not in the IL.
> What we'd like
> to do is seed the path query with a "virtual" path through the two
> predicates to the
> entry of the loop and compute_ranges based on those.  Then we like to
> use range_of_stmt on 'if (condition)' and 'switch (var)' to determine
> not taken edges.

Huh, that's an interesting idea.  We could definitely adapt
path_range_query to work with an artificial sequence of blocks, but it
would need some surgery.  Off the top of my head:

a) The phi handling code looks for specific edges in the path (both
for intra path ranges and for relations inherent in PHIs).
b) The exported ranges between blocks in the path, probably needs some
massaging.
c) compute_outgoing_relations would need some work as you mention below...

> Looking somewhat at the sources it seems like we "simply" need to do what
> compute_outgoing_relations does - unfortunately the code lacks comments
> so I have no idea what jt_fur_source src (...).register_outgoing_edges does ...

fur_source is an abstraction for operands to the folding mechanism:

// Source of all operands for fold_using_range and gori_compute.
// It abstracts out the source of an operand so it can come from a stmt or
// and edge or anywhere a derived class of fur_source wants.
// The default simply picks up ranges from the current range_query.

class fur_source
{
}

When passed to register_outgoing_edges, it registers outgoing
relations out of a conditional.  I pass it the known outgoing edge out
of the conditional, so only the relational on that edge is recorded.
I have overloaded fur_source into a path specific jt_fur_source that
uses a path_oracle to register relations as they would occur along a
path.  Once register_outgoing_edges is called on each outgoing edge
between blocks in a path, the relations will have been set, and can be
seen by the range_of_stmt:

path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
{
...
  // If resolving unknowns, fold the statement making use of any
  // relations along the path.
  if (m_resolve)
    {
      fold_using_range f;
      jt_fur_source src (stmt, this, &m_ranger->gori (), m_path);
      if (!f.fold_stmt (r, stmt, src))
    r.set_varying (type);
    }
...
}

register_outgoing_edges would probably have to be adjusted for your
CFGless paths, and maybe the path_oracle (Andrew??).

My apologies.  The jt_fur_source is not only  wrongly named
"jump_thread", but is the least obvious part of the solver.  There are
some comments for jt_fur_source, but its use could benefit from better
comments throughout.  Let's see if I have some time before my leave to
document things better.

Aldy

>
> Anyway, for now manually simplifying things is fine but I probably would still
> stick to a basic interface that marks not taken outgoing edges of a stmt based
> on the set of versioning predicates.
>
> Richard.
>
> >
> > Martin
>