CFA representation of STEP 7 languages

The main goal of the STEP 7 fronted plug-in (cern.plcverif.plc.step7) is to parse the PLC programs (i.e., to produce their AST -- Abstract Syntax Tree) and then represent them as control-flow automata.

The entry point of the CFA representation generation is Step7CodeToCfa.convert(logger, mainprogramfile).

One or more program files can be given to the convert() method.
If an entry block name is provided too, that block will be used as entry (main automaton in the generated CFA). If no such entry block is provided, then the entry block will be the defined OB1 block (any block whose name ends with OB1), or if no OB1 is defined, the first block that can be an entry block will be used.

Assuming that the AST transformations have been already performed, the following key steps are performed:

Determine the scope of the translation (i.e., which blocks and variables need to be represented) (TranslationcScope.collect()),
Compute the types for the expressions in the scope (Step7TypeComputer.compute()),
Create fields to represent the used memory addresses (createMemoryAddressInstances()) and global variables (createGlobalVariableInstances()),
Represent the structure of the blocks, i.e., create automata declarations and data structures for the blocks (representBlockStructure()),
Represent the logic in the blocks, i.e., fill the automata declarations with transitions and locations corresponding to the implementation (ProgramConverter.convertBlock())
Do some additional transformations on the CFA declaration.

In the next subsections, more information can be read about each step.

Determining the scope

The goal of the TranslationScope class is to determine which blocks are required to be represented in the CFA. If we would include each PLC block in the CFA, we would spend a lot of resources on representing unnecessary PLC blocks that are never called, then on the reductions which would eliminate them. This is especially true if one of the parsed files contain built-in functions, as most of them are not used in a given program.

The TranslationScope.collect() method takes one or several program units which are initially in the scope. Then it will explore all of them and include recursively each program block which is directly or transitively used from block(s) in the initial scope. In addition, this scope collector will collect each memory address that is used in the scope (e.g., I0.1) and every global variable that is read anywhere.

After executing the collect() method, the returned TranslationScope object will contain a collection of program units, memory addresses and global variables that are in the scope of the current CFA generation.

Structural representation

After the scope has been determined, the structure of the CFA network will be created. In order to provide tracing for the later steps of the CFA generation, the CFA representations created for various PLC objects are registered in a StructuralAstCfaTrace instance which is called structuralTrace.

Depending on the type of the program unit, different structural elements will be created, as follows.

For each executable program unit (i.e., function, function block, organization block):
- A new data structure is created to represent the block parameters and internal variables (this will be registered in structuralTrace.programUnitToType),
  - Note that the data structure creation produces only a type, but no field will be created!
- For each variable defined in the executable program unit, a new field will be created in the corresponding data structure (they will be registered in astCfaVarTrace)
- A new automaton declaration is created (this will be registered in structuralTrace.programUnitToAutomaton).
In addition, for each organization block and function (that is not handled specially, see below), a singleton instance (a field) will be created to represent the single instance of the organization block/function (this will be registered in structuralTrace.singletonProgramUnitToField and structuralTrace.fieldToAutomaton)
- Certain functions have special handling and they do not need a corresponding automaton declaration. Such functions are the type conversion functions (e.g., REAL_TO_DINT, they can be identified by Step7LanguageHelper.isTypeConversionFunc()) and the library functions defined in the CFA (e.g., SIN, they can be identified by LibraryFunctionsToCfa.isHandledBuiltinBlock).
In addition, for each non-void function that is represented by an automaton declaration, a new field is created representing the return value (RET_VAL) in their corresponding data structure (this will be registered by calling astCfaVarTrace.addRetval()).
For each data block (both shared and instance):
- A new data structure is created to represent the variables in the data block,
- A new field is created with the above data structure (this will be registered in structuralTrace.singletonProgramUnitToField),
- For instance data blocks, the created field will be registered in structuralTrace.fieldToAutomaton,
- The initial assignments of the data block will be represented as initial assignments for the above field.
For each user-defined data type (UDT), a mew data structure is created (this will be registered in structuralTrace.programUnitToType).

Logic representation

The logic representation, i.e., filling the automata created above between the initial and end locations, depends on the implementation language.

For each program unit for which automaton declaration has been created, a ProgramConverter instance will be used to generate the representation of the logic. The implementation of the translation are in the SclBlockToCfa and StlBlockToCfa classes. Their common abstract superclass is BlockToCfa which contains the common methods.

The entry point of those classes is the convert() method. It will perform the following steps:

Create an initial location,
Create a transition from the initial location that reinitializes the temporary variables (as they do not retain their values),
Do some before conversion initialization if needed (beforeConversion()),
Represent the statement list with the corresponding locations and transitions (convertList(), implemented by the concrete subclasses),
- As the locations are created gradually, as the statement list is produced, it is not necessarily possible to create transitions corresponding to jumps (GOTO, EXIT, CONTINUE), as they may require a transition to a location which does not exist. Therefore the conversion methods can register postponed transition creations using the BlockToCfa.postpone() method. These postponed transition creations describe how should the transition be created, without creating them at the time of definition.
As at this point all locations have been created, the registered postponed transition creations will be executed.

SCL to CFA translation

The representation of an SCL statement list as the body of an automaton declaration is handled by the SclBlockToCfa class (and its superclass, BlockToCfa). The convertList method simply calls the convertStatement method for each consecutive statement.

The heart of the SCL to CFA translation is the convert(AbstractSclStatement, Location) method. It takes an SCL statement to be translated and a location from which the statement shall be represented. It returns a location (typically a newly created one) which is the location where the successor statement shall start.

The convertStatement() method implementations translate the various SCL statements (descendants of AbstractSclStatement) differently. Check the corresponding API documentation for the details of each representation. The information contained in the API documentation should not be repeated here to avoid inconsistency.

STL to CFA translation

The representation of an SCL statement list as the body of an automaton declaration is handled by the StlBlockToCfa class (and its superclass, BlockToCfa). The convertList method simply calls the convertStatement method for each consecutive statement.

Before the conversion (beforeConversion()), fields will be created to represent the nesting stack entries up to the depth defined in NestingStackEntry.

The heart of the STL to CFA translation is the convert(AbstractStlStatement, Location) method. It takes an STL statement to be translated and a location from which the statement shall be represented. It returns a location (typically a newly created one) which is the location where the successor statement shall start.

The convert() method implementations translate the various STL statements (descendants of AbstractStlStatement) differently. Check the corresponding API documentation for the details of each representation. The information contained in the API documentation should not be repeated here to avoid inconsistency.

[info] Global variables for STL

The registers used in the STL programs are represented as global variables. In order to create them at most once (exactly once if the program contains STL blocks in the current translation scope), this is handled by the ProgramConverter instance. The created global variables will be represented by an StlGlobalData instance which will be passed to the STL translation class.

Additional steps

For the moment, three additional steps are performed once the above steps have been finished:

Represent the variable views (fields are generated for the views too, but we have to make sure that the view and storage variables are modified together, thus they are kept consistent) using RepresentVariableViews. Read more about the variable view representation here.
Normally, each function call (FC) has a single, unique field that will be used as context. However, this may negatively impact the reductions, thus for the small FCs new fields will be created to make sure that each FC call uses its unique context. This will help inlining. This transformation is implemented in CreateUniqueContextsForSmallFcs.
The time representation (i.e., random assignment of the T_CYCLE global variable and increment of the __GLOBAL_TIME variable) will also be created here, by TimeRepresentation.

CFA representation