Re: First scheduling pass

["Ayal Zaks" <ZAKS at il dot ibm dot com>]

Dale Johannesen writes:
>Sanjiv Kumar Gupta, Noida writes:
>
>Sanjiv> Here, I can't get the scheduler to move the loads to the
>Sanjiv> top of the basic block. This is because the first scheduling pass
>Sanjiv> for SH is disabled. Enabling the first scheduling pass causes
excessive
>Sanjiv> register pressure resulting in lots of spills generated by the
register
>Sanjiv> allocator.
>
>
>     We have found excessive speculation, but not excessive register
>pressure.  You might try decreasing the issue rate to "1" for the first
>scheduling pass, as I did for PowerPC.
>
>
>I've certainly seen excessive register pressure in some cases, and so have
>other people here; I have several bug reports on it.
>

Sanjiv Kumar Gupta, Noida writes:
>Sanjiv> I plan to re-enable the scheduling *before* register allocation
for
>Sanjiv> SH4. IMO, the number of spills can be reduced by applying some
good
>Sanjiv> heuristic(s) to reorder the ready queue. Any ideas for a good
solution?

I see three main problems in the way the first scheduling pass deals with
register
pressure: (1) the tie-breaking heuristic itself, (2) the fact that it is
only
a tie-breaking heuristic among ready instructions, and (3) it does not
consider
the current register pressure and how close it is to the point of spilling.

Problem (1): in rank_for_schedule preference is given to the instruction
that
reduces register pressure more (e.g. stores are preferable to
loads) only if both insns have the same critical-path-distance
(INSN_PRIORITY).
In the original a[i]=b[i] example, I would expect all loads to be more
critical
than all stores, so that register pressure considerations are not given a
chance.
To overcome this, the order of the two heuristics can be swapped when the
current
level of register pressure is "high".

Problem (2): suppose loads have long
latencies, then the ready list will consist of only loads at the beginning.
Register
pressure will continue to rise without considering the possibility of
skipping a
few cycles until a pressure-decreasing instruction becomes ready. To
overcome this,
one can compare the highest-priority ready instruction with the
highest-priority
queued instruction, and if the latter has much higher priority than the
former
(e.g. because it does reduce register pressure which is high) then wait
until it
becomes ready without scheduling instructions from the ready list in the
interim.

I'm trying to see what happens if instructions are never queued by the
first
scheduling pass (but instead are considered ready immediately), which is
some
approximated solution to problem (2).

Ayal Zaks.