[CFG] Loop unswitching

[Zdenek Dvorak]

Hello.

> > > > +   /* Test must be non-trivial (we use trivial ones to disable unreachable
> > > > +      branches.  */
> > > > +   if (rtx_equal_p (test, always_true_cond)
> > > > +       || rtx_equal_p (test, always_false_cond))
> > > > +     return false;
> > > 
> > > Hmm, really?  Where? Why?
> > 
> > See discussion at unswitch_single_loop.
> 
> The whole issue about updating the jump instruction with new conditional is
> incompatible with lowlevel RTL, unfortunately.
> We can stay with it on the branch, but for the trunk we need to find way
> to paper around this issue.
> 
> If Iunderstand it, you do:
> 1) unswitch on condition A,
> 2) replace condition A by true conditional or false conditional in the copies
> 3) recurse yourself

Not exactly. What I do is:

1) find condition A
2) if we already unswitched on same (or negated) condition, replace it by
   corresponding true/false one and goto 1
3) unswitch on A, killing the conditional in copies directly.
4) recurse

> Given the fact that we are unswitching on the innermost loops only,
> can't we really just kill the conditional? Am I missing something important?

Consider the following code:

while (...)
 {
  if (flag)
   {
    ...
    if (!flag)  /* XXX */
     goto bla:
   
   }
 }
return;
bla:
absolutely_anything ();

bla is unreachable after unswitching on the two conditions.  I'm not sure
whether code like this can pass through previous optimalizations without
getting rid of /* XXX */; if I'm guaranteed that it cannot, it should be
possible to remove the branch. Still there would be problems (like in

while (1)
 {
 if (flag)
  {
   something ();
  }
 ...
 if (flag)
  break;
 }

where I would have to cancel the loop (hmm... in fact this cannot happen, as I
now insist on that both branches lead into the loop)); but they seem
manageable.

> Hmm, perhaps it is even safe to update lowlevel RTL this way, thinking about
> it more, but we need to ensure that someone will kill the instrutions before
> other transformations are done.
> 
> Also on lowlevel RTL it is dificult to localize the conditional, but we cn
> just replace the condjump insn by kind of placeholder.  Perhaps we can hold
> whole issue until midRTL is acceptable for mainline, but I guess it will take
> bit too much time.
> > > > +   if (!cfg_layout_can_duplicate_bb_p (unswitch_on))
> > > > +     return NULL;
> > > Didn't you tested that whole loop is duplicable earlier?
> > 
> > I don't think so.
> I remember seeing something in the function deciding whether to unswitch or not.

OK, it's there. But you're never paranoid enough :-).

Zdenek