On Mon, Oct 4, 2021 at 6:29 PM Michael Matz <m...@suse.de> wrote:
>
> Hello,
>
> On Mon, 4 Oct 2021, Jeff Law wrote:
>
> > And just in case it got lost. Here's the analysis on 960218-1 on visium:
> >
> > We've got this going into ethread:
> >
> > int f (int x)
> > {
> > int D.1420;
> > int a;
> >
> > ;; basic block 2, loop depth 0, maybe hot
> > ;; prev block 0, next block 3, flags: (NEW, REACHABLE, VISITED)
> > ;; pred: ENTRY (FALLTHRU,EXECUTABLE)
> > a_4 = ~x_3(D);
> > goto <bb 4>; [INV]
> > ;; succ: 4 (FALLTHRU,EXECUTABLE)
> >
> > ;; basic block 3, loop depth 1, maybe hot
> > ;; prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
> > ;; pred: 4 (TRUE_VALUE,EXECUTABLE)
> > gl = a_1;
> > ;; succ: 4 (FALLTHRU,DFS_BACK,EXECUTABLE)
> >
> > ;; basic block 4, loop depth 1, maybe hot
> > ;; prev block 3, next block 5, flags: (NEW, REACHABLE, VISITED)
> > ;; pred: 2 (FALLTHRU,EXECUTABLE)
> > ;; 3 (FALLTHRU,DFS_BACK,EXECUTABLE)
> > # a_1 = PHI <a_4(2), 0(3)>
> > if (a_1 != 0)
> > goto <bb 3>; [INV]
> > else
> > goto <bb 5>; [INV]
> > ;; succ: 3 (TRUE_VALUE,EXECUTABLE)
> > ;; 5 (FALSE_VALUE,EXECUTABLE)
> >
> > ;; basic block 5, loop depth 0, maybe hot
> > ;; prev block 4, next block 1, flags: (NEW, REACHABLE, VISITED)
> > ;; pred: 4 (FALSE_VALUE,EXECUTABLE)
> > return;
> > ;; succ: EXIT
> >
> > }
>
> First notice that this doesn't have an empty latch block to start with
> (in fact, there is no separate latch block at all), so the loop optimizers
> haven't been initialized for simple latches at this point. Still, I would
> say that even then we want to be careful with the latch edge, as putting
> code onto it will most probably create a problem downstream once we _do_
> want to intialize the loop optimizers for simple latches. So, that we are
> careful here is okay, we are just too careful in this specific case.
Not sure if the argument about empty or not empty latches is important...
> > There's a pretty obvious jump thread in there. 3->4->5.
> >
> > We used to allow this, but it's currently being rejected and I'm not
> > sure it should.
> >
> > In simplest terms we're threading from inside the loop, through the
> > latch to a point outside the loop. At first glance, that seems safe.
All threadings that start inside the loop and end outside of it are OK
in principle. Even if the path crosses the latch or the header.
We _might_ end up creating a loop with multiple exits though.
> Is at least the unrestricted jump threader (the one after loop optimizers)
> picking this up?
>
> Independend of that, I agree, that this specific instance of threading
> through the latch block, even though followed by to-be-copied
> instructions, is okay. We need to determine precisely when that is okay,
> though. In this case there are several reasons I could see why this is
> so:
> (a) while the thread is through the latch block, it's _not_ through the
> latch edge (which is 4->3). That would create the problem, so here
> we're fine.
> (b) even if it were through the latch edge, and would be followed by
> to-be-copied instructions (and hence fill the latch edge) the ultimate
> end of the path is outside the loop, so all the edges and blocks that
> would now carry instructions would also be outside the loop, and hence
> be no problem
Yep.
> Now, capture this precisely ;-)
I tried to capture this with
+ // The path should either start and end in the same loop or exit the
+ // loop it starts in but never enter a loop. This also catches
+ // creating irreducible loops, not only rotation.
+ if (entry->src->loop_father != exit->dest->loop_father
+ && !flow_loop_nested_p (exit->src->loop_father,
+ entry->dest->loop_father))
+ {
+ cancel_thread (&path, "Path rotates loop");
+ return true;
+ }
it's not really necessary to have (simple) latches to argue about this
I think.
> I think something like so: we have a candidate path
>
> S -> L -> B1 (-> B2 ... Bn)
>
> (Start, Latch, Blocks 1 to n following the latch). (I think in our
> notation that means that the jump in L is redirected to Bn, and all code
> from B1..Bn be copied, right? Do we even support multiple blocks after
> the to-be-redirected jump?)
>
> Now if L is a latch block, but L->B1 is no latch/back edge : no
> restrictions apply.
>
> Otherwise, L->B1 is a latch/back edge (that means B1 is a loop header): if
> all of B2..Bn-1 don't contain jumps back into the loop, and Bn is outside
> the loop, then the thread is okay as well. (B2..Bn-1 can be inside the
> loop, as long as they don't contain jumps back into the loop, after
> copying by the threader, they don't create problems: their copies will be
> placed outside the loop and won't generate side entries back into the
> loop; the copied latch edge will not be a latch edge anymore, but a loop
> exit edge).
>
> It's quite possible that the full generality above is not necessary.
> It's probably enough to just not deal with the (b) case above (and
> continue to reject it), and simply only accept the candidate path if none
> of the involved edges is a latch/back edge (despite one block being the
> latch block). Especially so because I'm not convinced that I handled
> the idea of case (b) correctly above ;-)
>
>
> Ciao,
> Michael.
