[FORTRAN PATCH] Reduce gfc_match_strings usage (part 1)

[Brooks Moses]

Roger Sayle wrote:
> I was recently investigating the feasability of adding support for ".xor."
> as a synonym of ".neqv." as a GNU extension to the gfortran front-end [to
> match the equivalent functionality provided by several commercial fortran
> compilers], when I stumbled across match.c:gfc_match_strings.
[...]
> Perhaps my bioinformatics/chemoinformatics pattern matching background has
> made me sensitive to such inefficiencies [2], but the proposed patch below
> and the following follow-up, provide far more efficient implementations,
> based upon the theory/analysis described in [1].
[...]
> Thoughts?

My first reaction was remembering the chapter on finite-state-machine 
methods of parsing from a compiler book I was reading last week, and 
thus was a mock-incredulous reply of, "What, you mean this is actually 
useful in the real world?"  :)

More seriously, though, I have several sets of thoughts:

1.) This is obviously a more efficient implementation.

2.) However, it takes general solutions and converts them to 
case-specific ones that require much more code.

3.) Does it actually do anything useful?  In particular, in actual 
tests, does this make the compiler measurably faster?

Item 2 is the one that particularly concerns me.  There are multiple 
users of gfc_match_string, and I don't offhand know if there are other 
places in the compiler that could use a better version but it certainly 
looks like the whole pile of "match" usages in the middle of 
gfc_match_if could possibly use such a thing as well.  It seems to me 
that separating these out into individual hardcoded things is going 
backwards.

Thus: Would it be feasible to write an implementation that's a little 
closer to the original form, in which we have a routine (to take the 
place of the mstring declarations) that adds the various strings into 
some treelike representation that's equivalent to the structure of your 
nested piles of 'if' clauses, and then replaces gfc_match_string with 
something that traverses this tree?

I think this is definitely something worth pursuing; I'm just not 
convinced that hardcoding things is the best way to pursue it.

- Brooks