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.
