[PATCH] Loop unswitching: support gswitch statements.

[Richard Biener]

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

Richard.

>
> Martin