Program Analysis
The program analysis component of AutoMATES reads in Fortran source code, extracts comments, constructs an intermediate representation of the input code, and translates this to the AIR intermediate representation. A high-level schematic is shown in Figure 1.
Figure 1: The Program Analysis Pipeline: An Overview
The f2grfn tool can be invoked in two ways: (1) as a standalone tool invoked from the command-line, and (2) as a library that can be invoked from within a program.
The command-line invocation is via a Python script f2grfn_standalone.py located in the directory delphi/script. It processes Fortran source files all the way up to AIR intermediate representation.
$ python3.7 f2grfn_standalone.py -f <fortran_file>
This script should be run in the delphi directory. It requires Python version >= 3.7.
Options:
-f filename : filename is the input Fortran file
-d dirname : dirname is the target directory to save generated intermediate files (default: current directory).
-r dirname : dirname is the root directory to begin scanning (Default: current directory).
-m filename : filename is the name of the module log file (Default: modFileLog.json).
f2grfn can be invoked from a program via the following functions:
-
fortran_to_grfn: This function translates Fortran source file to Python IR and all the way up to AIR for any module files that the input Fortran file uses. Then, it returns the translated Python IR in a string to the caller. -
generate_grfn: This function translates Python IR to AIR intermediate representation. It requires a Python IR in a string that thefortran_to_grfnfunction translates to.
The f2grfn tool parses the source code to be analyzed, constructs an intermediate representation of the input code, and translates this to the AIR intermediate representation.
Conceptually, f2grfn consists of the following components:
- A comment extractor, get_comments, that extracts [some] comments from the Fortran source files.
- A preprocessor that processes the input code to work around problems in the Open Fortran Parser (OFP) module used to parse the Fortran code.
- A parser that translates the input program into a collection of abstract syntax trees (ASTs) for its constituent components. f2grfn currently uses the open-source OpenFortranParser (OFP) tool for this, but in principle any parser capable of handling Fortran code would be suitable.
- A rectifier that performs tree-to-tree transformations on the ASTs produced by OFP to regularize the representation and simplify subsequent processing.
- A translator that maps the ASTs obtained from the rectified ASTs obtained from the rectifier to the AIR output used by subsequent analyses.
The get_comments tool extracts comments from the source code into a form suitable for subsequent analysis. It currently returns a dictionary that maps each subprogram name p in the input file to a dictionary that holds source comments associated with the head, neck, and foot of p. Here, "head" refers to the point immediately preceding the declaration of the subprogram; "neck" refers to the point immediately after the subprogram declaration and before any declarations or code in the subprogram body; and "foot" refers to the point immediately after the end of the subprogram and before the next subprogram (if any) or the end of the file. This is illustrated in Figure 2.
Figure 2: Comments extracted by the get_comments tool
- Input: Fortran source code
- Output: Preprocessed (normalized) Fortran source code
The primary function of the preprocessor is to transform the code to get around certain limitations of the OFP parser used to parse the Fortran code. The transformations it implements include the following:
- Discarding comments. This is to get around an OFP problem with correctly handling comments in some Fortran-77 code.
- Merging continuation lines. This is to get around an OFP problem with handling continuation lines in Fortran-77 code.
- Handling file inclusion. The INCLUDE statement in Fortran directs the compiler to replace it with the contents of the file named (this is similar to the
#includedirective in C). The preprocessor carries out this replacement process. - Statement normalization. Some Fortran constructs, e.g., CASE statements, can take a number of different forms with different default values. The preprocessor normalizes them to a canonical form where the default values are made explicit. A conceptually similar issue arises with implicit array declarations; the preprocessor makes such array declarations explicit.
- Input: Fortran source code
- Output: Abstract syntax tree (AST) in XML format
f2grfn uses the Open Fortran Parser (OFP) to transform Fortran source code to an AST that is then translated to the AIR code representation used by subsequent analyses. The details of this translation process are affected by two factors:
- OFP discards source-program comments, which are important for the AutoMATES project. Unfortunately, the version of OFP that is distributed in source form does not produce ASTs, making it nontrivial to modify ofp source code to include comments in the generated AST. We therefore opted for a solution where comments are extracted separately using the get_comments tool mentioned above.
- OFP handles some Fortran constructs incorrectly. For certain Fortran language constructs (e.g., continuation lines in Fortran-77 code; expressions with chained accesses to components of complex data structures) it throws runtime exceptions. For certain other constructs (e.g., nested derived types) it produces ASTs whose structure does not correspond to that of the input code. We deal with the first problem by rewriting the input code in the preprocessor module; and the second problem by repairing the ofp-generated ASTs in the rectifier module.
- Input: AST in XML format
- Output: AST in XML format
Our experiments indicate that—possibly due to idiosyncracies in legacy Fortran syntax—the ASTs produced by OFP can have weirdnesses that complicate downstream processing. This is especially true of combinations of complex language constructs, e.g., derived types containing other derived types (this is akin to structs in C containing other structs). Translating the resulting ASTs directly to a dataflow representation requires a lot of ugly and brittle code to deal with the various corner cases that arise. To address this issue, we use the rectifier module to carry out an AST(xml)-to-AST(xml) transformation that cleans up the weirdnesses of the ASTs generated by OFP and produces ASTs that have a uniform and well-defined structure.
An important AST normalization step performed by the rectifier is the elimination GOTO statements, which have no analog in either Python or AIR. For this we implement an appropriate subset of the GOTO-eliminating AST transformations described in the following paper:
Ana M. Erosa and Laurie J. Hendren. "Taming Control Flow: A Structured Approach to Eliminating Goto Statements". Proceedings of 1994 IEEE International Conference on Computer Languages (ICCL'94). IEEE, 1994.
- Input: AST in XML format
- Output: AutoMATES Intermediate Representation (AIR)
After the original XML produced by the OFP has been cleaned up, the resulting XML AST is used to create the AutoMATES Intermediate Representation (AIR) of the original Fortran file. This is a multi-step process which involves the following steps:
- The XML AST is first converted into a general AST format. This format is more language-independent and represents the program structure in a way that is easier for the rest of the translator to work with. For this purpose, the AST is represented in a JSON format and with an option to save it in easily transportable pickle files. In essence, this AST format makes language translation much easier, possibly allowing the Fortran code to be converted into other languages such as Python, C++, etc.
- Next, the intermediate AST is used to generate a Python script which is equivalent to the original Fortran code. A primary objective while generating the Python script is to ensure that the Fortran file and the Python file produce the same results when executed. This assertion in execution is an important step in the translation process. This step involves handling various Fortran language constructs that differ from or are absent in Python. For example, Fortran strings, arrays, static variables and format statements are implemented in the Python intermediate by using user-defined classes for these language constructs.
- Finally, the python file is used to generate the AutoMATES Intermediate Representation (AIR) files. For this, the AST of the python file is used as the input for the remainder of the translator. The AIR format consists of two files: a) A JSON file that represents the source code program structure in a form that separates identifiers (any program symbol used to denote a program element) from the program elements themselves (namely, variables and functions) b) A python file, called the lambda file which contains executable functions representing every operation in the program.
Detailed information about this format can be found here.
In addition to generating the AIR representation of the input program, the XML-to-AIR trnslator also produces summary information about input program modules. Fortran programs can declare modules using the MODULE keywork, and the variables and subprograms declared within these modules can be imported into other parts of the program using the USE keyword. In order to ensure scalability, we set ourselves the design objective that, in order to analyze a program, it should not be necessary to analyze any program component more than once. An immediate corollary is that it is necessary to create and cache summary information about each module so that, when a module is used, its summary information can be looked up without a need to re-analyze the module. The summary information about the modules in a program is stored in the module log file for the program. Information about each module is represented as a JSON dictionary and has the following fields:
name: <module_name>
file: <file_containing_the_module>
module: <list_of_used_modules>
symbol_export: <list_of_symbols_exported_by_module>
subprogram_list: <procedure_mapping_for_module>
The procedure mapping for each subprogram p defined in module M is a
mapping from each possible tuple of argument types for p to the function to
invoke for that argument type tuple. This is used, where possible, to statically resolve dynamic dispatch.
A number of Fortran idiosyncracies and OFP problems made the project "interesting". The following is a non-exhaustive list of examples.
We are accustomed to whitespace being a token separator in code (outside comments and string literals), e.g., a character sequence abc def is typically understood as two tokens, abc and def. Things are more complicated in Fortran. Spaces matter in some "free-format" dialects (e.g., Fortran-90) but not in "fixed-format" ones (e.g., Fortran-77). DSSAT mixes fixed-format and free-format files, which makes things interesting. For example, the file AUTPLT.for (part of the code involved with PET in DSSAT) contains the following line:
IF (CROP .EQ. 'RI' .AND.(PLME .EQ. 'T' .OR. PLME. EQ. 'N')) THEN
In this example, note the stray space in front of the last EQ. operator: since this is a Fortran-77 (fixed-format) file, the space character does not matter and the character sequence . EQ. is supposed to be recognized as the operator .EQ.. This problem occurs a number of times in several different files in the DSSAT codebase. Unfortunately, the OFP parser chokes on this code.
We could not see a straightforward way to solve this problem automatically, and in the end got around it by manually editing the source code.
OFP has trouble with continuation lines and comments in some fixed-format inputs. We deal with this using the preprocessor to remove comments and merge continuation lines.
OFP has trouble handling expressions containing accesses to nested structured data. Examples include:
- Field accesses of nested derived types. E.g.:
ModuleDefs.for:Value = SAVE_data % PLANT % BIOMAS - Substring of an element of an array of strings. E.g.:
CSUTS.for:IF(facadj(i)(1:1).EQ.'-')THEN
We did not see a simple way to deal with this, and got around the problem by manually editing the source code.
When dealing with a problematic issue in Fortran processing, we have three alternatives: we can manually edit the source code to remove a problematic construct; we can try to transform the offending construct into something that can be handled during preprocessing; we can rectify any problematic XML generated by the OFP parser. The approach used in any given situation was guided by the following considerations:
- If the problematic construct causes an error or exception in OFP, it has to be handled before the construct reaches OFP. We have two alternatives:
- If the problem construct can be transformed into something that OFP can handle using only local code manipulation, i.e., without requiring information from or changes to other parts of the code, it is done in the preprocessor.
- Otherwise it is handled by manually editing the input to replace the problematic construct.
- If the problematic construct is processed normally by OFP but results in a malformed AST, we use the rectifier module to post-process the generated AST and transform it to a desired structure.
The preprocessor performs local transformations on the input source code before it is passed to the OFP parser. Here, "local transformations" refers to code transformations that are applied to small snippets of code (typically just a line or two) without requiring information from, or inducing changes to, other parts of the input code.
The preprocessor is a natural place for code transformations that aim to work around OFP problems. However, the requirement that preprocessor transformations be local, as mentioned above, limit its applicability in some situations. For example, for the problem with field accesses of nested derived types mentioned above, the culprit code
Value = SAVE_data % PLANT % BIOMAS
could be transformed to something like
Type (PlantType) Plant_tmp
...
Plant_tmp = SAVE_data % PLANT
Value = Plant_tmp % BIOMAS
but this transformation is non-local and so is not currently performed by the preprocessor.
The reason the preprocessor limits itself to local transformations is that it is applied before the input has been parsed. Its view of the input is therefore as a sequence of lines of text, i.e., it does not know the structure of the code. This raises the possibility that non-local transformations applied without knowledge of program structure could introduce syntax errors or change the program's semantics. (In principle, it would certainly be possible to add more smarts to the preprocessor so that it could deduce enough of the input program's syntactic structure to be able to apply transformations such as that shown above. We did not have enough time to explore this.)
One of the problems arising out of idiosyncracies of Fortran syntax and/or deficiencies in OFP is that the ASTs produced by OFP sometimes contain irregularities. For example, in some situations (e.g., FORMAT statements within an IF statement; nested derived types) an AST node does not appear where one might intuitively expect it to be. The function of the rectifier module is to restructure the AST produced by OFP to remove such irregularities.
The general design goal for the XML-to-AIR translator is that the input AST in XML format should generally have predictable structure where, as much as possible, information about a node appears at that node and its component computations appear as its children. The rectifier module aims to restructure the AST generated by OFP to achieve this.
Our general approach for adding new Fortran language construct to f2grfn was as follows: we would use a suite of test programs to examine the ASTs produced by OFP for that construct and determine whether these ASTs met the design goal mentioned. If they did not, the deviations from that goal were identified and code added to the rectifier to fix the culprit ASTs so that the result met the design goal.