New automaton_option "collapse-ndfa"

[Bernd Schmidt <bernds at codesourcery dot com>]

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

Attachment: ga-collapse.diff
Description: Text document