Re: [PATCH] Loop unswitching: support gswitch statements.

[Richard Biener <richard.guenther@gmail.com>]

On Thu, Nov 25, 2021 at 11:38 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> 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??).

So conceptually we'd attach extra predicates to an edge (a single one,
and even the "entry" edge of the path in this specific case).  That is,
instead of explicit

   \
   if (p1)
       \
     if (p2)
        |
       { stmts }

we see

      \ p1 && p2
     { stmts }

it might be easier to think of it in this way.  p1 and p2 could be
represented as gimple_seq (but off IL) or as GENERIC tree
and my idea was that compute_outgoing_relations could somehow
process those.

There is edge->aux one could use to more easily experiment
with a solution (to avoid massaging too many APIs), possibly
also edge->insns.g, or one could use a ranger global hash-map.

That said, it's an idea on how to make use of ranger for this more
easily in the future, it's not a strict requirement for the ongoing work.

Richard.

> 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
> >
>