This is the mail archive of the
mailing list for the GCC project.
Re: DFA state and arc explosion
Bingfeng Mei wrote:
However, if I also want to model the resource for writing back register
file, the number of states and arcs just explodes. It is especially true
for long pipeline instruction.
The usual solution is to have two DFAs, one used for most instructions,
and one used just for the long pipeline instructions. See for instance
the gcc/config/mips/sb1.md file which has the sb1_cpu_div automaton
which is only used for divide instructions.
DFA stands for deterministic finite automaton, which is a type of finite
state machine. NDFA is non-deterministic finite automaton. Any good
book on the theory of computing should cover this.