Problem with scheduling multi-block regions

[Richard Earnshaw <rearnsha at arm dot com>]

I was looking at the visualization of the instruction scheduler recently 
and was quite surprised to discover some inexplicably large stalls that 
were being inserted in the schedule.  Looking deeper it turns out that 
there would appear to be a bug in the way we calculate the fire point for 
insns whose links span multiple basic blocks (as can happen when 
scheduling a region that contains more than one block).  The problem stems 
from the fact that INSN_TICK is always set to MAX (INSN_TICK, clock+cost); 
but it is never reset when we move from one basic block to another.

Consider a region consisting of, amongst others, the following two blocks:

	bb 1
	...
	(insn x (set (a) (...)))
	...


	bb 2
	...
	(insn y (set (c) (...)))
	(insn z (set (b) (plus (a) (c))))
	...

Now if these are in the same region, it is possible for a link to be 
created between the x and z insns (so that we can potentially move one of 
the insns into the other block).  However, if we don't move the insns and 
then schedule insn x to run at, say, clock tick 30, then we will set 
INSN_TICK(z) to 30+cost: this value will persist even when we start 
scheduling bb 2 with clock set back to zero.  Hence if we finally schedule 
insn y at clock 5, we will enable insn z with 27 stalls (if the cost of 
firing z after either x or y is only, say, 2).

I'm not entirely sure what the fix should be, perhaps someone who 
understands the scheduler code better than myself could comment.  Two 
possibilities that come to mind are:

1) Search out and zero all relevant INSN_TICK entries at the start of 
scheduling each block; the difficulty is finding all such cases quickly.

2) Modify the scheduler so that we preserve "clock" within a region; then 
we wouldn't have the situation where the setting of INSN_TICK from a 
previous block would adversely affect the current block.  This might have 
the added benefit of modelling inter-block stalls as well; though it's not 
clear if we compute enough data for this to be useful.