[PATCH] Loop unswitching: support gswitch statements.

Richard Biener richard.guenther@gmail.com
Wed Nov 24 12:48:51 GMT 2021


On Wed, Nov 24, 2021 at 11:48 AM Martin Liška <mliska@suse.cz> wrote:
>
> On 11/24/21 09:00, Richard Biener 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.
>
> Yes.
>
> >  IIRC
> > elsewhere Andrew showed a snipped on how to evaluate a stmt with a
> > given range - not sure if that
>
> I'm using that. First I isolate a irange from a versioning-predicate with
> ranger->range_on_edge and I later combine it with:
> fold_range (r, stmt, parent_range).
>
>
> > 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.
>
> What I can do that via building of a vector of tuple<unswitch_predicate,bool>
> that would be passed to recursive calls of tree_unswitch_single_loop.
> That basically describes which true/false edges are taken for the so far created
> versioning-predicates. Right? That should be usable.

Yeah.  Not sure how much incremental re-use we can have here.  I'd keep
things simple at this point and shoot for something that works on a single
recursion level only.

> > Then we like to
> > use range_of_stmt on 'if (condition)' and 'switch (var)' to determine
> > not taken edges.
>
> Works for me and we would mark unreachable case BBs with a unreachable_flag
> (we can't fold it away as shown in the original patch attempt).

As said we probably want to mark edges, unreachable edges from
upthread recursions
should get their flags copied even.

> > 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 ...
> >
> > 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.
>
> Lemme try working on another version of the patch.

Yup.  You did have a branch, right?  Maybe I'll poke at it a bit as well.

Richard.

> Martin
>
> >
> > Richard.
> >
> >>
> >> Martin
>


More information about the Gcc-patches mailing list