[CFG] Loop unswitching

[Jan Hubicka]

> 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

I see. 
So the main problem is not killing the conditional described bellow.
Perhaps you can simply kill the conditonal and create fake edge to keep
datastructure consistent.  This is probably cleaner sollution than keeping
"constant" condjump in the loop.

Also note that heuristics in recursing can be badly confused by not killing the
code early in case the condtional guards important portion of the loop
(this is often the case).
> 
> > 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

CSE should delete it, but it is just pseudo global, by looping regions
(that may happen in internal loops via irregular ones) can be the optimization
tricked away, I guess.

How dificult is to write code to update the tree in such case?
I don't think we need to maitain time complexity in the bounds for such side
corners, but of course we must handle it.
Keeping the dead code in the copies around looks somewhat unfortunate.

(Also the heuristics deciding about loop copies should probably use dominance
tree to stimate growth of code size after removing code dominated by the
conditional, later)

> 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, can you just try how often such case happends?
This looks like trackable by loop peeling-we may notice the fact and
force peeling to happen.
> 
> > 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