This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]
Other format:	[Raw text]

Re: DFA state and arc explosion

From: Jim Wilson <wilson at tuliptree dot org>
To: Bingfeng Mei <bmei at broadcom dot com>
Cc: gcc at gcc dot gnu dot org
Date: Mon, 17 Mar 2008 10:39:27 -0700
Subject: Re: DFA state and arc explosion
References: <2E073B3ABB3F664DBA1D1C4D5FB47EF40B71CEE2@NT-IRVA-0752.brcm.ad.broadcom.com>

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

References:
- DFA state and arc explosion
  - From: Bingfeng Mei

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]