RE: DFA state and arc explosion

["Bingfeng Mei" <bmei at broadcom dot com>]

I don't really know what NDFA, DFA and minimal DFA mean. But by a quick
search I found other machine porting could have the same number as well.

 http://osdir.com/ml/linux.lfs.clfs.support/2006-10/msg00042.html


Bingfeng

-----Original Message-----
From: Galloth [mailto:lordgalloth@gmail.com] 
Sent: 14 March 2008 10:58
To: Bingfeng Mei
Subject: Re: DFA state and arc explosion

Hello,
I maybe totally wrong, but how it is possible that your NDFA DFA and
Minimal DFA are the same? I would think that this indicate some sort
of error.

Jan

2008/3/14, Bingfeng Mei <bmei@broadcom.com>:
> Hello,
>  In porting GCC (still 4.2) to our VLIW processor,  I tried to model
>  pipeline as precisely as possible. If I only model the issue slot
>  resource, it is fine. GCC generates a small state machine and
compiles
>  code quickly.
>
>  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.  In the following example,
>
>  (define_insn_reservation "mul_op" 8
>    (and (eq_attr "type" "mul")
>         (eq_attr "dual" "no"))
>    "long_p0|long_p1, nothing * 7")
>
>        50 NDFA states,            178 NDFA arcs
>        50 DFA states,             178 DFA arcs
>        50 minimal DFA states,     178 minimal DFA arcs
>
>  (define_insn_reservation "mul_op" 8
>    (and (eq_attr "type" "mul")
>         (eq_attr "dual" "no"))
>    "long_p0|long_p1, nothing * 6, port_0")
>
>      7680 NDFA states,          27008 NDFA arcs
>      7680 DFA states,           27008 DFA arcs
>      7680 minimal DFA states,   27008 minimal DFA arcs
>
>  The number of states and arcs increases dramatically for just single
>  difference.  Modeling other instructions in a similar way becomes
>  impossible therefore. It takes forever to build GCC.
>
>  What I did wrong here?  I just want to model resource usage in issue
>  slot and writeback stage in order possible stall cycle. What is the
>  cheap to do this? Thanks in advance.
>
>  Cheers,
>
> Bingfeng Mei
>  Broadcom UK
>
>


-- 
Jan Kastil
galloth@jabbim.cz