[FORTRAN PATCH] Reduce gfc_match_strings usage (part 1)

Roger Sayle roger@eyesopen.com
Sun Mar 11 03:14:00 GMT 2007

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.

In the world computer science and compiler design, lexical analysis and
keyword recognition has evolved to a fine-art.  Modern techniques using
finite state machines or perfect hash functions now achieve remarkable
efficiency, as per-character processing is often a performance bottle-next
in non-optimizing compilation.  The GNU project even has a flex and gperf
tools to simplify the process.  gfortran's current gfc_match_strings
implementation possesses none of these virtuous qualities. :-)

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].

This first installment proposes as alternative implementation for
primary.c's match_logical_constant to avoid use of gfc_match_strings and
thereby avoids run times that have order dependent upon the number of
pattern strings being matched.  This "simple example" should help
introduce the reviewers to the more complex example presented in the
following patch.

The following patch has been tested on x86_64-unknown-linux-gnu, with a
full "make bootstrap", including gfortran, and tested with a top-level
"make -k check" with no new regressions.


2007-03-10  Roger Sayle  <roger@eyesopen.com>

        * primary.c (match_logical_constant_string): New function to match
        a ".true." or a ".false.".
        (match_logical_constant): Use it instead of gfc_match_strings.

[1] LexGen whitepaper, http://www.eyesopen.com/~roger/lexgen.pdf
[2] A. Grant, ... and R. Sayle, "LINGOs, Finite State Machines and Fast
Similarity Searching", Journal of Chemical Informatics and Modeling,
Vol. 26, No. 5, pp. 1912-1918, 2006.
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: patchf.txt
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20070311/3799f4d4/attachment.txt>

More information about the Gcc-patches mailing list