Re: issues with first scheduling pass on SH4

[Joern Rennecke <joern dot rennecke at superh dot com>]

"Sanjiv Kumar Gupta, Noida" wrote:
> One solution to this could be to allow the instruction scheduling
> pass estimate the splits which will be performed later. Maybe add a new
> attribute to instructions indicating the number of insns generated
> later, and this value is examined
> by the scheduler during the first scheduling pass.

For RISC processors like the SH, you could just look at the length
attribute.  But that doesn't tell you what kinds of extra registers
are needed - you'd have to look at the constraints for that, in
particular those of clobbers.

> The spill can be avoided by rematerialization of stack
> based addresses (r691),
> but I am thinking if I could anyhow avoid the distance between
> the related insns 1093 and 1094. I am short of any ideas to solve
> this one. Please help.

I can't see how the current scheduling algorithm fits here - it really
comes down to register pressure, and since we don't know what instruction
we will pick after the one we pick currently, we don't know what lifetimes
we are going to create.

It would be different if we did scheduling more like bubblesort - only swap
adjacent instructions - or like a variant on shellsort - we could consider
peepholes of, say five instructions at a time.  That number should probably
be a function of the number of available registers.
We should keep track of how many data dependency chains for each mode
(or better: preferred register class) are life at any point in the insn
stream.  If the current value is critical for the target machine - we can
compute threshold values from the size of register classes, or we could use
a target macro / hook to override this - increasing this number by moving
an insn past such a point which drags more depenencies along it than it
removes should be considered costly.  Likewise, if we can lower the number
of dependency chains at such an bottleneck without making the schedule
worse, this can create opportunities for doing schedule improvements
without spill penalties, so we should also consider instruction re-ordering
to lower register pressure where it is high.
We could also try this as some kind of on-demand schedule change: we examine
the current schedule for stalls, and where we see one, we can try
- to move the feeding instruction upwards
- to move the consumer downwards
- to grab in insn from before the feeding insn or after the consumer insn and
  move it between them.
Besides the impact on the schedule we can then also consider the impact on the
register pressure, as can be estimated by the number and mode / preferred class
of dependency chains and clobbers at each point.
Of course, where multiple insn depend on the same value of a single feeding
insn, that should be counted only as one... so we should represent the
dependency information so that we can tell for each value that an insn
produces which other insns use them, and either keep linear uids for them
up-to-date (the cost for this should be limited as we should only do limited
moves of insns), or put the insns in some kind of balanced tree-structure that
allows to test if one instruction precedes another.
	
-- 
--------------------------
SuperH (UK) Ltd.
2410 Aztec West / Almondsbury / BRISTOL / BS32 4QX
T:+44 1454 465658