New automaton_option "collapse-ndfa"

[Vladimir Makarov]

On 07/11/2011 05:09 PM, Bernd Schmidt wrote:
> On C6X, we want to use the "ndfa" option to give the scheduler maximum
> freedom when assigning units to instructions. After scheduling is
> complete, we process the insns again in c6x_reorg, looking at each cycle
> and assigning a unit specifier to each instruction so that there is no
> conflict within a cycle.
>
> This works, except for a few reservations that span more than the first
> cycle. To handle these properly, one possibility would be to consider
> the entire scheduled block with a more complicated algorithm. While
> feasible, I'd prefer not to go there for the moment.
>
> I came up with the notion of adding a new transition to the NDFA, one
> which collapses a nondeterministic state (which is composed of multiple
> possible deterministic ones) to just one of its component states. This
> can be done at the end of each cycle, and gives a state that can be
> processed with cpu_unit_reservation_p to identify the units chosen by
> the scheduler. The following patch implements this.
>
> The new option also modifies the generation of advance-cycle transitions
> so that they only exist in deterministic states. This matches the
> expected use of the feature where we have a collapse-ndfa transition
> before the end of each cycle (using the dfa_pre_cycle_insn hook).
> state_transition now recognizes const0_rtx as the collapse-ndfa
> transition (NULL_RTX was taken for advance-cycle).
>
> Tested with 4.5 c6x-elf so far. I hope to commit the C6X port to
> mainline soon and will retest the patch with that as well. IA64 is
> another user of the "ndfa" option, but it failed to bootstrap a clean
> tree when I tried it a few days ago, so I've only built a cross-cc1 and
> examined the generated insn-automata.c before/after the patch. No
> changes beyond slight expected reorganization in the code recognizing
> NULL_RTX as advance-cycle, and no changes in the "ia64.dfa" file
> generated with the "v" option.
>
> Ok?
>
Bernd, sorry for the delay.  I was on vacation last week.

The patch is ok for me.  Thanks, Bernd.

IA64 actually uses the two automata,  one automaton can be considered 
NDFA and is used for scheduling, another one can be considered as DFA 
and used for insn bundling.

I should acknowledge your solution is not trivial and more elegant and 
permitting to use smaller description.

It would be interesting to rewrite IA64 in your way.  Although I think 
it will be never done because it is nontrivial work to do and probably 
better not to fix something when it already works.