Skip to content

Program Analysis

Jump to bottom
Saumya Debray edited this page Apr 28, 2020 · 43 revisions

The Program Analysis Component: Overview

The program analysis component of AutoMATES consists of two tools: get_comments, which extracts comments from the source code; and f2grfn, which parses the source code, constructs an intermediate representation of the input code, and translates this to the AIR intermediate representation.

1. Comment Extraction: get_comments

1.1. Usage

TBD

1.2. Technical Overview

  • Input: Fortran source code
  • Output: Extracted comments, as a Python data structure

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

TODO Place Image Figure 1: Comments extracted by the get_comments tool

2. Program Translation: f2grfn

2.1. Usage

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.

2.1.1. Command-line Invocation

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 : Set input Fortran file
-d : Set target directory to save generated intermediate files (Default: current directory).
-r : Set root directory to begin scanning (Default: Current directory).
-m : Set name of the module log file (Default: modFileLog.json).

2.1.2. Invocation from a Program

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 the fortran_to_grfn function translates to.

2.2. Technical Overview

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.

2.2.1. Organization

Conceptually, f2grfn is structured as a pipeline consisting of the following components:

  1. A preprocessor that processes the input code to work around problems in the Open Fortran Parser (OFP) module used to parse the Fortran code.
  2. 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.
  3. A rectifier that performs tree-to-tree transformations on the ASTs produced by OFP to regularize the representation and simplify subsequent processing.
  4. A translator that maps the ASTs obtained from the rectified ASTs obtained from the rectifier to the AIR output used by subsequent analyses.

2.2.2. Preprocessor

  • 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:

  1. Discarding comments. This is to get around an ofp problem with correctly handling comments in some Fortran-77 code.
  2. Merging continuation lines. This is to get around an OFP problem with handling continuation lines in Fortran-77 code.
  3. 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 #include directive in C). The preprocessor carries out this replacement process.
  4. 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.

2.2.3. Fortran Parser

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

2.2.4. Rectifier

  • 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. The function of the rectify module is to transform the ASTs obtained from OFP in order to normalize them and make their structure more regular and predictable, so as to simplify their subsequent processing. An additional function is to separate the XML-to-AIR translation from particular characteristics of OFP's output ASTs, to make it easier to replace OFP with other Fortran parsers in the future. 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.

2.2.5 XML-to-AIR Translator

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:

  1. 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.
  2. 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.
  3. 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.

Clone this wiki locally