Scheduling automaton question

[Vladimir Makarov]

On 02/11/2011 07:33 AM, Bernd Schmidt wrote:
> Suppose I have two insns, one reserving (A|B|C), and the other reserving
> A. I'm observing that when the first one is scheduled in an otherwise
> empty state, it reserves the A unit and blocks the second one from being
> scheduled in the same cycle. This is a problem when there's an
> anti-dependence of cost 0 between the two instructions.
>

> Vlad - two questions. Is this behaviour what you would expect to happen,
> and how much work do you think would be involved to fix it (i.e. make
> the first one transition to a state where we can still reserve any two
> out of the three units)?
The scheduler can do what you want but if there is no dependence between 
the instructions.  The first cycle multi-pass insn scheduler will try 
different order of ready insns to choose the best one.  But if there is 
a dependence between the insns only one insn will be in the ready list.  
I think it is a lot of work to implement the same for dependent insns 
(and it probably will make the scheduler much slower).

Still there are other solution for your problem.  The first one proposed 
by Frederic RISS is to use NDFA (*nondeterministic* asutomata).  Itanium 
uses partially such automata for analogous problem.

Another solution (it might not work for some cases) is to use another 
order in alternatives (e.g. C|B|A instead of A|B|C).  In this case the 
generated automata permit to issue the first and then the 2nd insn 
because deterministic automata tries first alternative first.  So the 
state without reservation will go a state with reservation C for the 
first insn, the state with reservation C will go to a state with 
reservation B for the 1st insn etc.