Dependency Analysis Functionality in PSyclone

There are two different dependency analysis methods implemented, the old dependency analysis one, and a new one based on a variable access API. There is a certain overlap between these two methods, and it is expected that the current dependency analysis, which does not support the NEMO API, will be integrated with the variable access API in the future (see #1148).

Dependence Analysis

Dependence Analysis in PSyclone produces ordering constraints between instances of the Argument class within a PSyIR tree.

The Argument class is used to specify the data being passed into and out of instances of the Kern class, HaloExchange class and GlobalSum class (and their subclasses).

As an illustration consider the following invoke:

invoke(           &
    kernel1(a,b), &
    kernel2(b,c))

where the metadata for kernel1 specifies that the 2nd argument is written to and the metadata for kernel2 specifies that the 1st argument is read.

In this case the PSyclone dependence analysis will determine that there is a flow dependence between the second argument of Kernel1 and the first argument of Kernel2 (a read after a write).

Information about arguments is aggregated to the PSyIR node level (kernel1 and kernel2 in this case) and then on to the parent loop node resulting in a flow dependence (a read after a write) between a loop containing kernel1 and a loop containing kernel2. This dependence is used to ensure that a transformation is not able to move one loop before or after the other in the PSyIR schedule (as this would cause incorrect results).

Dependence analysis is implemented in PSyclone to support functionality such as adding and removing halo exchanges, parallelisation and moving nodes in a PSyIR schedule. Dependencies between nodes in a PSyIR schedule can be viewed as a DAG using the dag() method within the Node base class.

DataAccess Class

The DataAccess class is at the core of PSyclone data dependence analysis. It takes an instance of the Argument class on initialisation and provides methods to compare this instance with other instances of the Argument class. The class is used to determine 2 main things, called overlap and covered.

Overlap

Overlap specifies whether accesses specified by two instances of the Argument class access the same data or not. If they do access the same data their accesses are deemed to overlap. The best way to explain the meaning of overlap is with an example:

Consider a one dimensional array called A of size 4 (A(4)). If one instance of the Argument class accessed the first two elements of array A and another instance of the Argument class accessed the last two elements of array A then they would both be accessing array A but their accesses would not overlap. However, if one instance of the Argument class accessed the first three elements of array A and another instance of the Argument class accessed the last two elements of array A then their accesses would overlap as they are both accessing element A(3).

Having explained the idea of overlap in its general sense, in practice PSyclone currently assumes that any two instances of the Argument class that access data with the same name will always overlap and does no further analysis (apart from halo exchanges and vectors, which are discussed below). The reason for this is that nearly all accesses to data, associated with an instance of the Argument class, start at index 1 and end at the number of elements, dofs or some halo depth. The exceptions to this are halo exchanges, which only access the halo and boundary conditions, which only access a subset of the data. However these subset accesses are currently not captured in metadata so PSyclone must assume subset accesses do not exist.

If there is a field vector associated with an instance of an Argument class then all of the data in its vector indices are assumed to be accessed when the argument is part of a Kern or a GlobalSum. However, in contrast, a HaloExchange only acts on a single index of a field vector. Therefore there is one halo exchange per field vector index. For example:

InvokeSchedule[invoke='invoke_0_testkern_stencil_vector_type', dm=True]
... HaloExchange[field='f1', type='region', depth=1, check_dirty=True]
... HaloExchange[field='f1', type='region', depth=1, check_dirty=True]
... HaloExchange[field='f1', type='region', depth=1, check_dirty=True]
... Loop[type='',field_space='w0',it_space='cells', upper_bound='cell_halo(1)']
... ... CodedKern testkern_stencil_vector_code(f1,f2) [module_inline=False]

In the above PSyIR schedule, the field f1 is a vector field and the CodedKern testkern_stencil_vector_code is assumed to access data in all of the vector components. However, there is a separate HaloExchange for each component. This means that halo exchanges accessing the same field but different components do not overlap, but each halo exchange does overlap with the loop node. The current implementation of the overlaps() method deals with field vectors correctly.

Coverage

The concept of coverage naturally follows from the discussion in the previous section.

Again consider a one dimensional array called A of size 4 (A(4)). If one instance (that we will call the source) of the Argument class accessed the first 3 elements of array A (i.e. elements 1 to 3) and another instance of the Argument class accessed the first two elements of array A then their accesses would overlap as they are both accessing elements A(1) and A(2) and elements A(1) and A(2) would be covered. However, access A(3) for the source Argument class would not yet be covered. If a subsequent instance of the Argument class accessed the 2nd and 3rd elements of array A then all of the accesses (A(1), A(2) and A(3)) would now be covered so the source argument would be deemed to be covered.

In PSyclone the above situation occurs when a vector field is accessed in a kernel and also requires halo exchanges e.g.:

InvokeSchedule[invoke='invoke_0_testkern_stencil_vector_type', dm=True]
   HaloExchange[field='f1', type='region', depth=1, check_dirty=True]
   HaloExchange[field='f1', type='region', depth=1, check_dirty=True]
   HaloExchange[field='f1', type='region', depth=1, check_dirty=True]
   Loop[type='',field_space='w0',it_space='cells', upper_bound='cell_halo(1)']
      CodedKern testkern_stencil_vector_code(f1,f2) [module_inline=False]

In this case the PSyIR loop node needs to know about all 3 halo exchanges before its access is fully covered. This functionality is implemented by passing instances of the Argument class to the DataAccess class update_coverage() method and testing the access.covered property until it returns True.

# this example is for a field vector 'f1' of size 3
# f1_index[1,2,3] are halo exchange accesses to vector indices [1,2,3] respectively
access = DataAccess(f1_loop)
access.update_coverage(f1_index1)
result = access.covered  # will be False
access.update_coverage(f1_index2)
result = access.covered  # will be False
access.update_coverage(f1_index3)
result = access.covered  # will be True
access.reset_coverage()

Note the reset_coverage() method can be used to reset internal state so the instance can be re-used (but this is not used by PSyclone at the moment).

The way in which halo exchanges are placed means that it is not possible for two halo exchange with the same index to depend on each other in a schedule. As a result an exception is raised if this situation is found.

Notice there is no concept of read or write dependencies here. Read or write dependencies are handled by classes that make use of the DataAccess class i.e. the _field_write_arguments() and _field_read_arguments() methods, both of which are found in the Arguments class.

Variable Accesses

Especially in the NEMO API, it is not possible to rely on pre-defined kernel information to determine dependencies between loops. So an additional, somewhat lower-level API has been implemented that can be used to determine variable accesses (READ, WRITE etc.), which is based on the PSyIR information. The only exception to this is if a kernel is called, in which case the metadata for the kernel declaration will be used to determine the variable accesses for the call statement. The information about all variable usage of a PSyIR node or a list of nodes can be gathered by creating an object of type psyclone.core.VariablesAccessInfo. This class uses a Signature object to keep track of the variables used.

Signature

A signature can be thought of as a tuple that consists of the variable name and structure members used in an access - called components. For example, an access like a(1)%b(k)%c(i,j) would be stored with a signature (a, b, c), giving three components a, b, and c. A simple variable such as a is stored as a one-element tuple (a, ), having a single component.

class psyclone.core.Signature(variable, sub_sig=None)[source]

Given a variable access of the form a(i,j)%b(k,l)%c, the signature of this access is the tuple (a,b,c). For a simple scalar variable a the signature would just be (a,). The signature is the key used in VariablesAccessInfo. In order to make sure two different signature objects containing the same variable can be used as a key, this class implements __hash__ and other special functions. The constructor also supports appending an existing signature to this new signature using the sub_sig argument. This is used in StructureReference to assemble the overall signature of a structure access.

Parameters:

variable (str or tuple of str or list of str) – the variable that is accessed.
sub_sig (psyclone.core.Signature) – a signature that is to be added to this new signature.

__eq__(other)[source]: Required in order to use a Signature instance as a key. Compares two objects (one of which might not be a Signature).

__hash__()[source]: This returns a hash value that is independent of the instance. I.e. two instances with the same signature will have the same hash key.

__lt__(other)[source]: Required to sort signatures. It just compares the tuples.

property is_structure

Returns:: True if this signature represents a structure.
Return type:: bool

to_language(component_indices=None, language_writer=None)[source]

Converts this signature with the provided indices to a string in the selected language.

TODO 1320 This subroutine can be removed when we stop supporting strings - then we can use a PSyIR writer for the ReferenceNode to provide the right string.

Parameters:

component_indices (None (default is scalar access), or psyclone.core.component_indices.ComponentIndices) – the indices for each component of the signature.
language_writer (None (default is Fortran), or an instance of psyclone.psyir.backend.language_writer.LanguageWriter) – a backend visitor to convert PSyIR expressions to a representation in the selected language. This is used when creating error and warning messages.

Raises:

InternalError – if the number of components in this signature is different from the number of indices in component_indices.

property var_name

Returns:: the actual variable name, i.e. the first component of the signature.
Return type:: str

VariablesAccessInfo

The VariablesAccessInfo class is used to store information about all accesses in a region of code. To collect access information, the function reference_accesses() for the code region must be called. It will add the accesses for the PSyIR subtree to the specified instance of VariablesAccessInfo.

Node.reference_accesses(var_accesses)[source]

Get all variable access information. The default implementation just recurses down to all children.

Parameters:: var_accesses (psyclone.core.VariablesAccessInfo) – Stores the output results.

class psyclone.core.VariablesAccessInfo(nodes=None, options=None)[source]

This class stores all SingleVariableAccessInfo instances for all variables in the corresponding code section. It maintains ‘location’ information, which is an integer number that is increased for each new statement. It can be used to easily determine if one access is before another.

Parameters:

nodes (Optional[psyclone.psyir.nodes.Node | List[psyclone.psyir.nodes.Node]]) – optional, a single PSyIR node or list of nodes from which to initialise this object.
options (Dict[str, Any]) – a dictionary with options to influence which variable accesses are to be collected.
options["COLLECT-ARRAY-SHAPE-READS"] (Any) – if this option is set to a True value, arrays used as first parameter to the PSyIR query operators lbound, ubound, or size will be reported as ‘read’. Otherwise, these accesses will be ignored.
options["USE-ORIGINAL-NAMES"] (Any) – if this option is set to a True value, an imported symbol that is renamed (use mod, a=>b) will be reported using the original name (b in the example). Otherwise these symbols will be reported using the renamed name (a).

Raises:

InternalError – if the optional options parameter is not a dictionary.
InternalError – if the nodes parameter either is a list and contains an element that is not a psyclone.psyir.nodes.Node, of if nodes is not a list and is not of type psyclone.psyir.nodes.Node

__str__()[source]: Gives a shortened visual representation of all variables and their access mode. The output is one of: READ, WRITE, READ+WRITE, or READWRITE for each variable accessed. READ+WRITE is used if the statement (or set of statements) contain individual read and write accesses, e.g. ‘a=a+1’. In this case two accesses to a will be recorded, but the summary displayed using this function will be ‘READ+WRITE’. Same applies if this object stores variable access information about more than one statement, e.g. ‘a=b; b=1’. There would be two different accesses to ‘b’ with two different locations, but the string representation would show this as READ+WRITE. If a variable is is passed to a kernel for which no individual variable information is available, and the metadata for this kernel indicates a READWRITE access, this is marked as READWRITE in the string output.

add_access(signature, access_type, node, component_indices=None)[source]

Adds access information for the variable with the given signature. If the component_indices parameter is not an instance of ComponentIndices, it is used to construct an instance. Therefore it can be None, a list or a list of lists of PSyIR nodes. In the case of a list of lists, this will be used unmodified to construct the ComponentIndices structures. If it is a simple list, it is assumed that it contains the indices used in accessing the last component of the signature. For example, for a%b with component_indices=[i,j], it will create [[], [i,j] as component indices, indicating that no index is used in the first component a. If the access is supposed to be for a(i)%b(j), then the component_indices argument must be specified as a list of lists, i.e. [[i], [j]].

Parameters:

signature (psyclone.core.Signature) – the signature of the variable.
access_type (psyclone.core.access_type.AccessType) – the type of access (READ, WRITE, …)
node (psyclone.psyir.nodes.Node instance) – Node in PSyIR in which the access happens.
component_indices (psyclone.core.component_indices.ComponentIndices, or any other type that can be used to construct a ComponentIndices instance (None, List[psyclone.psyir.nodes.Node] or List[List[psyclone.psyir.nodes.Node]])) – index information for the access.

property all_signatures

Returns:: all signatures contained in this instance, sorted (in order to make test results reproducible).
Return type:: List[psyclone.core.signature]

has_read_write(signature)[source]

Checks if the specified variable signature has at least one READWRITE access (which is typically only used in a function call).

Parameters:: signature (psyclone.core.Signature) – signature of the variable
Returns:: True if the specified variable name has (at least one) READWRITE access.
Return type:: bool
Raises:: KeyError if the signature cannot be found.

is_read(signature)[source]

Checks if the specified variable signature is at least read once.

Parameters:: signature (psyclone.core.Signature) – signature of the variable
Returns:: True if the specified variable name is read (at least once).
Return type:: bool
Raises:: KeyError if the signature cannot be found.

is_written(signature)[source]

Checks if the specified variable signature is at least written once.

Parameters:: signature (psyclone.core.Signature) – signature of the variable.
Returns:: True if the specified variable is written (at least once).
Return type:: bool
Raises:: KeyError if the signature name cannot be found.

property location

Returns the current location of this instance, which is the location at which the next accesses will be stored. See the Developers’ Guide for more information.

Returns:: the current location of this object.
Return type:: int

merge(other_access_info)[source]

Merges data from a VariablesAccessInfo instance to the information in this instance.

Parameters:: other_access_info (psyclone.core.VariablesAccessInfo) – the other VariablesAccessInfo instance.

next_location()[source]: Increases the location number.

options(key=None)[source]

Returns the value of the options for a specified key, or None if the key is not specified in the options. If no key is specified, the whole option dictionary is returned.

Parameters:: key (Optional[str]) – the option to query, or None if all options should be returned.
Returns:: the value of the option associated with the provided key or the whole option dictionary if it is not supplied.
Return type:: Union[None, Any, dict]
Raises:: InternalError – if an invalid key is specified.

This class collects information for each variable used in the tree starting with the given node. A VariablesAccessInfo instance can store information about variables in high-level concepts such as a kernel, as well as for language-level PSyIR. You can pass a single instance to more than one call to reference_accesses() in order to add more variable access information, or use the merge() function to combine two VariablesAccessInfo objects into one. It is up to the user to keep track of which statements (PSyIR nodes) a given VariablesAccessInfo instance is holding information about.

VariablesAccessInfo Options

By default, VariablesAccessInfo will not report the first argument of the PSyIR operators lbound, ubound, or size as read accesses, since these functions do not actually access the content of the array, they only query the size. If these accesses are required (e.g. in kernel extraction this could be important if an array is only used in these intrinsic - a driver would still need these arrays in order to query the size), the optional options parameter of the VariablesAccessInfo constructor can be used: add the key COLLECT-ARRAY-SHAPE-READS and set it to true:

vai = VariablesAccessInfo(options={'COLLECT-ARRAY-SHAPE-READS': True})

In this case all arrays specified as first parameter to one of the PSyIR operators above will be reported as read access.

Fortran also allows to rename a symbol locally when it is being imported, (use some_mod, only: renamed => original_name). Depending on use case, it might be useful to get the non-local, original name. By default, VariablesAccessInfo will report the local name (i.e. the renamed name), but if you add the key USE-ORIGINAL-NAMES and set it to True:

vai = VariablesAccessInfo(options={'USE-ORIGINAL-NAMES': True})

the original name will be returned in the VariablesAccessInfo object.

SingleVariableAccessInfo

The class VariablesAccessInfo uses a dictionary of psyclone.core.SingleVariableAccessInfo instances to map from each variable to the accesses of that variable. When a new variable is detected when adding access information to a VariablesAccessInfo instance via add_access(), a new instance of SingleVariableAccessInfo is added, which in turn stores all access to the specified variable.

class psyclone.core.SingleVariableAccessInfo(signature)[source]

This class stores a list with all accesses to one variable.

Parameters:: signature (psyclone.core.Signature) – signature of the variable.

add_access_with_location(access_type, location, node, component_indices)[source]

Adds access information to this variable.

Parameters:

access_type (psyclone.core.access_type.AccessType) – the type of access (READ, WRITE, ….)
location (int) – location information
node (psyclone.psyir.nodes.Node) – Node in PSyIR in which the access happens.
component_indices (psyclone.core.component_indices.ComponentIndices) – indices used for each component of the access.

property all_accesses

Returns:: a list with all AccessInfo data for this variable.
Return type:: List[psyclone.core.AccessInfo]

property all_read_accesses

Returns:: a list with all AccessInfo data for this variable that involve reading this variable.
Return type:: List[psyclone.core.AccessInfo]

property all_write_accesses

Returns:: a list with all AccessInfo data for this variable that involve writing this variable.
Return type:: List[psyclone.core.AccessInfo]

change_read_to_write()[source]: This function is only used when analysing an assignment statement. The LHS has first all variables identified, which will be READ. This function is then called to change the assigned-to variable on the LHS to from READ to WRITE. Since the LHS is stored in a separate SingleVariableAccessInfo class, it is guaranteed that there is only one entry for the variable.

has_read_write()[source]

Checks if this variable has at least one READWRITE access.

Returns:: True if this variable is read (at least once).
Return type:: bool

is_accessed_before(reference)[source]

Returns True if this variable is accessed before the specified reference, and False if not. This is equivalent to testing that ‘reference’ is the very first access, but this function will also verify that ‘reference’ is indeed in the list of accesses.

Parameters:: reference (psyclone.psyir.nodes.Reference) – the reference at which to stop for access checks.
Returns:: True if this variable is read before the specified reference, and False if not.
Return type:: bool
Raises:: ValueError – if the specified reference is not in the list of all accesses.

is_array(index_variable=None)[source]

Checks if the variable is used as an array, i.e. if it has an index expression. If the optional index_variable is specified, this variable must be used in (at least one) index access in order for this variable to be considered as an array.

Parameters:: index_variable (str) – only considers this variable to be used as array if there is at least one access using this index_variable.
Returns:: true if there is at least one access to this variable that uses an index.
Return type:: bool

is_read()[source]

Returns:: True if this variable is read (at least once).
Return type:: bool

is_read_before(reference)[source]

Returns True if this variable is read before the specified reference, and False if not.

Parameters:: reference (psyclone.psyir.nodes.Reference) – the reference at which to stop for access checks.
Returns:: True if this variable is read before the specified reference, and False if not.
Return type:: bool
Raises:: ValueError – if the specified reference is not in the list of all accesses.

is_read_only()[source]

Checks if this variable is always read, and never written.

Returns:: True if this variable is read only.
Return type:: bool

is_written()[source]

Returns:: True if this variable is written (at least once).
Return type:: bool

is_written_before(reference)[source]

Returns True if this variable is written before the specified reference, and False if not.

Parameters:: reference (psyclone.psyir.nodes.Reference) – the reference at which to stop for access checks.
Returns:: True if this variable is written before the specified reference, and False if not.
Return type:: bool
Raises:: ValueError – if the specified reference is not in the list of all accesses.

is_written_first()[source]

Returns:: True if this variable is written in the first access (which indicates that this variable is not an input variable for a kernel).
Return type:: bool

property signature

Returns:: the signature for which the accesses are stored.
Return type:: psyclone.core.Signature

property var_name

Returns:: the name of the variable whose access info is managed.
Return type:: str

AccessInfo

The class SingleVariableAccessInfo uses a list of psyclone.core.AccessInfo instances to store all accesses to a single variable. A new instance of AccessInfo is appended to the list whenever add_access_with_location() is called.

class psyclone.core.AccessInfo(access_type, location, node, component_indices=None)[source]

This class stores information about a single access pattern of one variable (e.g. variable is read at a certain location). A location is a number which can be used to compare different accesses (i.e. if one access happens before another). Each consecutive location will have an increasing location number, but read and write accesses in the same statement will have the same location number. If the variable accessed is an array, this class will also store the indices used in the access. Note that the name of the variable is not stored in this class. It is a helper class used in the SingleVariableAccessInfo class, which stores all AccessInfo objects for a variable, and it stores the name of the variable.

Parameters:

access – the access type.
location (int) – a number used in ordering the accesses.
node (psyclone.psyir.nodes.Node) – Node in PSyIR in which the access happens.
component_indices (None, [], a list or a list of lists of psyclone.psyir.nodes.Node objects, or an object of type psyclone.core.component_indices.ComponentIndices) – indices used in the access, defaults to None.

property access_type

Returns:: the access type.
Return type:: psyclone.core.access_type.AccessType

change_read_to_write()[source]

This changes the access mode from READ to WRITE. This is used for processing assignment statements, where the LHS is first considered to be READ, and which is then changed to be WRITE.

Raises:: InternalError – if the variable originally does not have READ access.

property component_indices

This function returns the list of accesses used for each component as an instance of ComponentIndices. For example, a(i)%b(j,k)%c will return an instance of ComponentIndices representing [ [i], [j, k], [] ]. In the case of a simple scalar variable such as a, the component_indices will represent [ [] ].

Returns:: the indices used in this access for each component.
Return type:: psyclone.core.component_indices.ComponentIndices

is_array()[source]

Test if any of the components has an index. E.g. an access like a(i)%b would still be considered an array.

Returns:: if any of the variable components uses an index, i.e. the variable is an array.
Return type:: bool

property location

Returns:: the location information for this access. Please see the Developers’ Guide for more information.
Return type:: int

property node

Returns:: the PSyIR node at which this access happens.
Return type:: psyclone.psyir.nodes.Node

Indices

The AccessInfo class stores the original PSyIR node that contains the access, but it also stores the indices used in a simplified form, which makes it easier to analyse dependencies without having to analyse a PSyIR tree for details. The indices are stored in the ComponentIndices object that each access has, which can be accessed using the component_indices property of an AccessInfo object.

class psyclone.core.ComponentIndices(indices=None)[source]

This class stores index information for variable accesses. It stores one index list for each component of a variable, e.g. for a(i)%b(j) it would store [ [i], [j] ]. Even for scalar accesses an empty list is stored, so a would have the component indices [ [] ], and a%b would have [ [], [] ]. Each member of this list of lists is the PSyIR node describing the array expression used.

As a shortcut, the indices parameter can be None or an empty list (which then creates the component indices as [[]], i.e. indicating a scalar access), a list l (which will then create the component indices as [l], i.e. a single component variable, which uses all the indices in the list l as array indices).

TODO #845 - the constructor should check that the things it is passed are PSyIR nodes. Currently it is sometimes given strings.

Parameters:

indices (None, [], a list or a list of lists of psyclone.psyir.nodes.Node) – the indices from which to create this object.

Raises:

InternalError – if the indices parameter is not None, a list or a list of lists.
InternalError – if the indices parameter is a list, and some but not all members are a list.

__getitem__(indx)[source]

Allows to use this class as a dictionary. If indx is an integer, the list of indices for the specified component is returned. If indx is a tuple (as returned from iterate), it will return the PSyIR of the index for the specified component at the specified dimension.

Returns:: either the list of indices for a component, or the index PSyIR node for the specified tuple.
Return type:: list of psyclone.psyir.nodes.Node, or psyclone.psyir.nodes.Node
Raises:: IndexError – if a tuple is given and one of the indices is outside of the valid range.

__len__()[source]

Returns:: the number of components in this class.
Return type:: int

get_subscripts_of(set_of_vars)[source]

This function returns a flat list of which variable from the given set of variables is used in each subscript. For example, the access a(i+i2)%b(j*j+k,k)%c(l,5) would have the component_indices [[i+i2], [j*j+k,k], [l,5]]. If the set of variables is (i,j,k), then get_subscripts_of would return [{i},{j,k},{k},{l},{}].

Parameters:: set_of_vars (Set[str]) – set with name of all variables.
Returns:: a list of sets with all variables used in the corresponding array subscripts as strings.
Return type:: List[Set[str]]

property indices_lists

Returns:: the component indices list of lists.
Return type:: list of list of psyclone.psyir.nodes.Node

is_array()[source]

Test whether there is an index used in any component. E.g. an access like a(i)%b with indices [ [i], [] ] would still be considered an array.

Returns:: whether any of the variable components uses an index, i.e. the variable is an array.
Return type:: bool

iterate()[source]

Allows iterating over all component indices. It returns a tuple with two elements, the first one indicating the component, the second the dimension for which the index is. The return tuple can be used in a dictionary access (see __getitem__) of this object.

Returns:: a tuple of the component index and index.
Return type:: tuple(int, int)

The ComponentIndices class provides an array-like accessor for the internal data structure, you can use len(component_indices) to get the number of components for which array indices are stored. The information can be accessed using array subscription syntax, e.g.: component_index[0] will return the list of array indices used in the first component. You can also use a 2-tuple to select a component and a dimension at the same time, e.g. component_indices[(0,1)], which will return the index used in the second dimension of the first component.

ComponentIndices provides an easy way to iterate over all indices using its iterate() method, which returns all valid 2-tuples of component index and dimension index. For example:

# access_info is an AccessInfo instance and contains one access. This
# could be as simple as `a(i,j)`, but also something more complicated
# like `a(i+2*j)%b%c(k, l)`.
for indx in access_info.component_indices.iterate():
    # indx is a 2-tuple of (component_index, dimension_index)
    psyir_index = access_info.component_indices[indx]

# Using enumerate:
for count, indx in enumerate(access_info.component_indices.iterate()):
    psyir_index = access_info.component_indices[indx]
    # fortran writer converts a PSyIR node to Fortran:
    print(f"Index-id {count} of 'a(i,j)': {fortran_writer(psyir_index)}")

Index-id 0 of 'a(i,j)': i
Index-id 1 of 'a(i,j)': j

To find out details about an index expression, you can either analyse the tree (e.g. using walk), or use the variable access functionality again. Below is an example that shows how this is done to determine if an array expression contains a reference to a given variable specified as a signature in the variable index_variable. The variable access_info is an instance of AccessInfo and contains the information about one reference. The function reference_accesses is used to analyse the index expression. Typically, this code would be wrapped in an outer loop over all accesses.

index_variable = Signature("i")
# access_info contains the access information for a single
# reference, e.g. `a(i+2*j)%b%c(k, l)`. Loop over all
# individual index expressions ("i+2*j", then "k" and "l"
# in the example above).
for indx in access_info.component_indices.iterate():
    index_expression = access_info.component_indices[indx]

    # Create an access info object to collect the accesses
    # in the index expression
    accesses = VariablesAccessInfo(index_expression)

    # Then test if the index variable is used. Note that
    # the key of `access` is a signature, as is the `index_variable`
    if index_variable in accesses:
        # The index variable is used as an index
        # at the specified location.
        print(f"Index '{index_variable}' is used.")
        break
else:
    print(f"Index '{index_variable}' is not used.")

Access Location

Variable accesses are stored in the order in which they happen. For example, an assignment a=a+1 will store two access for the variable a, the first one being a READ access, followed by a WRITE access, since this is the order in which the accesses are executed. Additionally, the function reference_accessess() keeps track of the location at which the accesses happen. A location is an integer number, starting with 0, which is increased for each new statement. This makes it possible to compare accesses to variables: if two accesses have the same location value, it means the accesses happen in the same statement, for example a=a+1: the READ and WRITE access to a will have the same location number. If on the other hand the accesses happen in two separate statements, e.g. a=b+1; c=a+1 then the first access to a (and the access to b) will have a smaller location number than the second access to a (and the access to c). If two statements have consecutive locations, this does not necessarily mean that the statements are executed one after another. For example in if-statements the statements in the if-body are counted first, then the statements in the else-body. It is the responsibility of the user to handle these cases - for example by creating separate VariablesAccessInfo for statements in the if-body and for the else-body.

Note

When using different instances for an if- and else-body, the first statement of the if-body will have the same location number as the first statement of the else-body. So you can only compare location numbers from the same VariablesAccessInformation instance. If you merge two instances together, the locations of the merged-in instance will be appropriately increased to follow the locations of the instance to which it is merged.

The location number is not exactly a line number - several statements can be on one line, which will get different location numbers. And certain lines will not have a location number (e.g. comment lines).

As stated above, one instance of VariablesAccessInfo can be extended by adding additional variable information. It is the responsibility of the user to make sure the accesses are added in the right order - the VariablesAccessInfo object will always assume accesses happen at the current location, and a call to next_location() is required (internally) to increase the location number.

Note

It is not possible to add access information about an earlier usage to an existing VariablesAccessInfo object.

Access Examples

Below we show a simple example of how to use this API. This is from the psyclone.psyir.nodes.OMPParallelDirective, and it is used to determine a list of all the scalar variables that must be declared as thread-private. Note that this code does not handle the usage of first-private declarations.

result = set()
var_accesses = VariablesAccessInfo()
omp_directive.reference_accesses(var_accesses)
for signature in var_accesses.all_signatures:
    if signature.is_structure:
        # A lookup in the symbol table for structures are
        # more complicated, so ignore them for this example.
        continue
    var_name = str(signature)
    symbol = symbol_table.lookup(var_name)
    # Ignore variables that are arrays, we only look at scalar ones.
    # The `is_array_access` function will take information from
    # the access information as well as from the symbol table
    # into account.
    access_info = var_accesses[signature]
    if symbol.is_array_access(access_info=access_info):
        # It's not a scalar variable, so it will not be private
        continue

    # If a scalar variable is only accessed once, it is either a coding
    # error or a shared variable - anyway it is not private
    accesses = access_info.all_accesses
    if len(accesses) == 1:
        continue

    # We have at least two accesses. If the first one is a write,
    # assume the variable should be private:
    if accesses[0].access_type == AccessType.WRITE:
        print("Private variable", var_name)
        result.add(var_name.lower())

The next, hypothetical example shows how the VariablesAccessInfo class can be used iteratively. Assume that you have a function can_be_parallelised that determines if the given variable accesses can be parallelised, and the aim is to determine the largest consecutive block of statements that can be executed in parallel. The accesses of one statement at a time are added until we find accesses that would prevent parallelisation:

# Create an empty instance to store accesses
accesses = VariablesAccessInfo()
list_of_parallelisable_statements = []
for next_statement in statements:
    # Add the variable accesses of the next statement to
    # the existing accesses:
    next_statement.reference_accesses(accesses)
    # Stop when the next statement can not be parallelised
    # together with the previous accesses:
    if not can_be_parallelised(accesses):
        break
    list_of_parallelisable_statements.append(next_statement)

print(f"The first {len(list_of_parallelisable_statements)} statements can "
      f"be parallelised.")

Note

There is a certain overlap in the dependency analysis code and the variable access API. More work on unifying those two approaches will be undertaken in the future. Also, when calling reference_accesses() for a Dynamo or GOcean kernel, the variable access mode for parameters is taken from the kernel metadata, not from the actual kernel source code.

Dependency Tools

PSyclone contains a class that builds upon the data-dependency functionality to provide useful tools for dependency analysis. It especially provides messages for the user to indicate why parallelisation was not possible. It uses SymPy internally to compare expressions symbolically.

class psyclone.psyir.tools.dependency_tools.DependencyTools(loop_types_to_parallelise=None)[source]

This class provides some useful dependency tools, allowing a user to overwrite/modify functions depending on the application. It includes a messaging system where functions can store messages that might be useful for the user to see.

Parameters:: loop_types_to_parallelise (Optional[List[str]]) – A list of loop types that will be considered for parallelisation. An example loop type might be ‘lat’, indicating that only loops over latitudes should be parallelised. The actually supported list of loop types is specified in the PSyclone config file. This can be used to exclude for example 1-dimensional loops.
Raises:: TypeError – if an invalid loop type is specified.

can_loop_be_parallelised(loop, test_all_variables=False, signatures_to_ignore=None)[source]

This function analyses a loop in the PsyIR to see if it can be safely parallelised.

Parameters:

loop (psyclone.psyir.nodes.Loop) – the loop node to be analysed.
test_all_variables (bool) – if True, it will test if all variable accesses can be parallelised, otherwise it will stop after the first variable is found that can not be parallelised.
signatures_to_ignore (Optional[ List[psyclone.core.Signature]]) – list of signatures for which to skip the access checks.

Returns:

True if the loop can be parallelised.

Return type:

bool

Raises:

TypeError – if the supplied node is not a Loop.

get_all_messages()[source]

Returns all messages that have been stored by the last function the user has called.

Returns:: a list of all messages.
Return type:: List[str]

Note

PSyclone provides replace_induction_variable_trans, a transformation that can be very useful to improve the ability of the dependency analysis to provide useful information. It is recommended to run this transformation on a copy of the tree, since the transformation might prevent other optimisations. For example, it will set the values of removed variables at the end of the loop, which can prevent loop fusion etc to work as expected.

An example of how to use this class is shown below. (Note that this is just for demonstration purposes: in reality the validate method of OMPLoopTrans will also use the dependence analysis to check that the transformation is safe.) It takes a list of statements (i.e. nodes in the PSyIR), and adds ‘OMP DO’ directives around loops that can be parallelised:

parallel_loop = OMPLoopTrans()
dt = DependencyTools()

for statement in loop_statements:
    if isinstance(statement, Loop):
        # Check if there is a variable dependency that might
        # prevent this loop from being parallelised:
        if dt.can_loop_be_parallelised(statement):
            parallel_loop.apply(statement)
        else:
            # Print all messages from the dependency analysis
            # as feedback for the user:
            for message in dt.get_all_messages():
                print(message)