Re: [PATCH V12]: Improve code sinking pass

[Richard Biener <richard.guenther@gmail.com>]

On Wed, Mar 13, 2024 at 9:27 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 3/13/24 4:22 AM, Richard Biener wrote:
>
> >
> > ... this hunk is OK (please test and split it out separatley).  In the spirit of
> > moving the stmt the least amount (in this case not schedule it within the
> > basic-block).  In the same spirit one would choose an earlier basic-block
> > but only if the old choosen one post-dominates that, dominance isn't
> > a good criteria since you'd move it where the computation might not be
> > needed.  A practical testcase would be
> >
> >    tem = a + b;
> >    if (foo)
> >      bar ();
> >    tem2 = tem + d;
> >
> > where we at the moment would sink 'tem = a+ b' to the block containing
> > 'tem2 = tem + d' not reducing the number of evaluations (of course bar()
> > might not return, but that's a minor detail).  Code motion like that should
> > be subject to register-pressure considerations which we do not estimate
> > here at all.  So it could be argued we shouldn't perform any sinking here.
> Agreed.  This looks more like a scheduling and register-pressure issue
> rather than a classic sinking issue.
>
> Sinking is supposed to be moving code to lesser executed points.  In the
> case above, the only way sinking into the tem2 = block would be if bar()
> doesn't return.  It just doesn't make sense to me from a sinking standpoint.
>
> The block execution data generally prevents this kind of gratuitous
> movement.
>
> I actually evaluated our sinking code several years ago against an
> implementation of Click's algorithm.  In general they were quite
> comparable in terms of selecting an "optimal" block from an execution
> standpoint.  There were a couple of fixes that were added to our
> implementation at that time, but again, generally we were picking
> sensible blocks.
>
>
> >
> > A good first-order heuristic would be to avoid the scheduling
> > when the number of non-virtual SSA uses on the stmt to be moved is bigger
> > than one.  For zero we reduce the lifetime of the def.  For one we're not
> > making things worse.  For more uses it depends on whether we're moving
> > within the lifetime of the uses and it becomes a global problem (we're
> > greedily moving dependent statements, so we even get "local global" wrong
> > then).
> >
> > That said, changing will cause regressions, given both before and after
> > is somewhat ad-hoc it's hard to argue one is more correct than the other.
> >
> > IMO scheduling should be left to a stmt scheduler on GIMPLE
> > (which we don't have).
> Click's work can function as a statement scheduler, though I'm not
> convinced it's actually a good one.  Essentially most statements are
> conceptually disassociated from their blocks, then re-scheduled by
> visiting defining statements of "pinned" instructions.  That model is
> mostly for driving redundancy elimination.  Scheduling is just a side
> effect.
>
>
>
> Bernd had a statement scheduler for gimple years ago, but it was
> somewhat controversial at the time and never moved forward enough to get
> integrated.  IIRC it ran just before or just after TER and its primary
> objective was to avoid some of the pathological cases that ultimately
> result in significant spilling after we're done with the bulk of the RTL
> pipeline.

Yeah, the most difficult thing with scheduling on GIMPLE is the interaction
with TER.  TER does have some "scheduling boundaries" it respects
(I'd have to look them up), so GIMPLE scheduling that only looks at
scheduling across such boundaries might be useful.

Richard.