Using a DFA for insn-recog.c

[Richard Sandiford]

Mark Mitchell <mark@codesourcery.com> writes:
> Richard Sandiford wrote:
>> There has been talk in the past of making automatic extensions
>> easier to express in .md files.  See for example:
>> 
>>     http://gcc.gnu.org/ml/gcc/2004-07/msg01075.html
>
> Would you please summarize the benefits of the patch?  (That's not meant 
> to be a wise-guy question; I'm just getting lost in the details and 
> trying to understand.)
>
>  From your email, it seems that:
>
> * Compilation time is approximately unchanged, despite what appears to 
> be more efficient code in recognizer which avoids checking predicates 
> multiple times
>
> * Text side in resulting compiler is smaller
>
> * Bootstrap time may have increased
>
> Is that right?

Yup.

> Also, based on the preface to your email above, I'm guessing that this 
> patch might be providing leverage for some other improvement?  Perhaps 
> that this paves the way for a future byte-coded implementation that will 
> deliver faster compile times?  Or, do you think that the text size 
> improvements alone justify this patch?  (I'm not saying they do not; 
> just asking.)

No, you're right.

Originally, the main motivation was to make it easier to handle things
like those discussed in the message I linked above.  In other words,
I wanted to allow most MIPS operands of the form:

   (match_operand:DI 0 "register_operand" "d")

to also match:

   (aign_extend:DI (match_operand:SI 0 "register_operand" "d"))

(with appropriate conditions and changes elsewhere).  The sort of
state sharing that we get with the DFA approach can significantly
reduce the size increase in recog.

However, although that was the main motivation for doing this in
the first place, I did hope that the change would be justified
for its own sake, on the grounds you give.

I suppose the argument would be more compelling if I could measure a
significant difference in execution speed.  Unfortunately, results on
my machine seem to be quite noisy, even when it's more-or-less idle.
I'm also not sure what would be a good test.  I don't know whether
there's anything whose gcc execution time is significantly affected
by recog.

(I wondered about using detailed profiling tools, but if that's the
only way to measure the result, would any improvement really count
for much?)

The argument would also be more compelling if there were no increase
in bootstrap time.  (As I think you realise, the time increase is due
to slowness in gcc, rather than in the new genrecog, and I deliberately
picked the most extreme target.)  For example, the argument would be
more compelling if I went straight to the byte-coded version and
measured no difference in execution speed (despite my reservations
about being able to measure this properly on my machine).  The insn
table would obviously compile much faster than the open-coded version.

But like I say, I don't want to do both steps (tree->dfa, open-coded->
byte-coded) at once.  I suppose a lot of the problem is that I don't
think it would be a good idea to pick just one byte encoding, try it,
and send it out.  I'd need to investigate several different possibilities
and see which works out best.  (A stack-based approach to handling the
rtx position?  Separate jump actions?  Fixed-width or variable-width
"instructions"?  And plenty more besides.)  It would be a lot of work,
and I'm only doing this in my spare time. ;)  I can also imagine that
whatever encoding I pick would be controversial with someone.

If the change isn't acceptable on the grounds you give alone[*],
then I'd rather try to find a different approach to the MIPS problem.
I don't want any future MIPS-related change to tip the scales one way
or the other.

  [*] And if it isn't, that's fine.  I knew that was a risk all along.

Richard