DFA state and arc explosion

[Jim Wilson]

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.

Jim