Dependency Analysis Tools#

PSyIR nodes provide multiple methods to reason about the dependencies and lifetimes of the symbols used in a PSyIR tree. These are described in the PSyIR dependency analysis methods section.

These methods currently use two distinct implementations, the new variable access API (which also provides the DefinitionUseChains and the Loop Dependency Tools for deeper analysis), and the older PSyKAl dependency analysis. There is a certain overlap between these two methods, and it is expected that the old PSyKAl dependency analysis will be integrated with the variable access API in the future (see #1148).

PSyIR Dependency Analysis Methods#

Node.reference_accesses()[source]

Return type:: VariablesAccessMap
Returns:: a map of all the symbol accessed inside this node, the keys are Signatures (unique identifiers to a symbol and its structure accessors) and the values are AccessSequence (a sequence of AccessTypes).

Reference.previous_accesses()[source]

Returns:: the nodes accessing the same symbol directly before this reference. It can be multiple nodes if the control flow diverges and there are multiple possible accesses.
Return type:: List[psyclone.psyir.nodes.Node]

Reference.next_accesses()[source]

Returns:: the nodes accessing the same symbol directly after this reference. It can be multiple nodes if the control flow diverges and there are multiple possible accesses.
Return type:: List[psyclone.psyir.nodes.Node]

Reference.escapes_scope(scope, visited_nodes=None)[source]

Whether the symbol lifetime continues after the given scope. For example, given the following fortran code:

    do i=1,10
      a = 1
      b = 2
      c = 3
    end do
    b = 4
    call mysub(a, b)
end subroutine

‘b’ and ‘c’ if it is local, finish their value lifetime at the end of the loop scope (it is not re-used afterwards). While for ‘a’ and ‘c’ if it is global, their value may be used later and they “escape the scope”.

Parameters:

scope (Node) – the given scope that we evaluate.
visited_nodes (Optional[set]) – a set of nodes already visited, this is necessary because the dependency chains may contain cycles. Defaults to an empty set.

Return type:

bool

Returns:

whether the symbol lifetime continues after the given scope.

Reference.enters_scope(scope, visited_nodes=None)[source]

Whether the symbol lifetime starts before the given scope. For example, given the following fortran code:

do i=1,10
  a = 1
  if (b>3) c = 1
end do

‘a’ does not enter the scope. Even if it had a value before in the loop scope this is reassigned to a new value. However, ‘b’ and ‘c’ values enter the scope, because there is a path in which they take the value the symbol had before the scope.

Parameters:

scope (Node) – the given scope that we evaluate.
visited_nodes (Optional[set]) – a set of nodes already visited, this is necessary because the dependency chains may contain cycles. Defaults to an empty set.

Return type:

bool

Returns:

whether the symbol lifetime starts before the given scope.

Loop.independent_iterations(test_all_variables=False, signatures_to_ignore=None, dep_tools=None)[source]

This function analyses a loop in the PSyIR to see whether its iterations are independent.

Parameters:

test_all_variables (bool) – if True, it will test if all variable accesses are independent, otherwise it will stop after the first variable access is found that isn’t.
signatures_to_ignore (Optional[ List[psyclone.core.Signature]]) – list of signatures for which to skip the access checks.
dep_tools (Optional[ psyclone.psyir.tools.DependencyTools]) – an optional instance of DependencyTools so that the caller can access any diagnostic messages detailing why the loop iterations are not independent.

Returns:

True if the loop iterations are independent, False otherwise.

Return type:

bool

PSyKAl analysis methods:

Node.dag(file_name='dag', file_format='svg')[source]

Create a dag of this node and its children, write it to file and return the graph object.

Parameters:

file_name (str) – name of the file to create.
file_format (str) – format of the file to create. (Must be one recognised by Graphviz.)

Returns:

the graph object or None (if ‘graphviz’ is not found).

Return type:

graphviz.Digraph or NoneType

Raises:

GenerationError – if the specified file format is not recognised by Graphviz.

Node.backward_dependence()[source]: Returns the closest preceding Node that this Node has a direct dependence with or None if there is not one. Only Nodes with the same parent as self are returned. Nodes inherit their descendants’ dependencies. The reason for this is that for correctness a node must maintain its parent if it is moved. For example a halo exchange and a kernel call may have a dependence between them but it is the loop body containing the kernel call that the halo exchange must not move beyond i.e. the loop body inherits the dependencies of the routines within it.

Node.forward_dependence()[source]: Returns the closest following Node that this Node has a direct dependence with or None if there is not one. Only Nodes with the same parent as self are returned. Nodes inherit their descendants’ dependencies. The reason for this is that for correctness a node must maintain its parent if it is moved. For example a halo exchange and a kernel call may have a dependence between them but it is the loop body containing the kernel call that the halo exchange must not move beyond i.e. the loop body inherits the dependencies of the routines within it.

PSyKAl Dependence Analysis#

The PSyKAl Kernel objects have additional dependency considerations that we can infer by knowing which specific parts of the provided fields they access. This information is given by the kernel metadata. Currently, how we use this information differs between the GOcean and LFRic DSLs.

In Gocean, CodedKern have assignments as children (automatically generated in the instance creation) that represent the computation pattern given the kernel metadata. We call these assignment the kernel prototype. For instance, a kernel with the following meta_args:

type(go_arg), dimension(3) :: meta_args =    &
     (/ go_arg(GO_WRITE, GO_CU, GO_POINTWISE),            & ! cu
        go_arg(GO_READ,  GO_CT, GO_STENCIL(000,110,000)), & ! p
        go_arg(GO_READ,  GO_CU, GO_POINTWISE)             & ! u
      /)

and called with:

call invoke( compute_cu(cu_fld, p_fld, u_fld) )

will have the following prototype assignment as child:

cu_fld%data(i,j) = p_fld%data(i,j) + p_fld%data(i,j + 1) + u_fld%data(i,j)

This assignment will not be generated to code because the lowering method replaces the entire CodedKern with the appropriate call. But this child is sufficient to provide the VariablesAccessMap used by generic PSyIR the necessary access information to perform the needed dependency checks.

LFric does not currently use this virtual assignments, instead it uses information provided by the Argument class attached to the CodedKern to evaluate the ordering constraints between between kernels.

The Argument class is used to specify the data being passed into and out of instances of the Kern class, HaloExchange class and GlobalReduction 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 GlobalReduction. 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#

When using PSyclone with generic Fortran code, 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.VariablesAccessMap. 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 VariablesAccessMap. 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

property var_name

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

AccessType#

An individual access to a Signature is described by an instance of the AccessType enumeration:

class psyclone.core.access_type.AccessType(*values)[source]

A simple enum-class for the various valid access types.

CALL = 8: A symbol representing a routine is called.

CONSTANT = 10: Access data that cannot be redefined during execution, therefore, it is available at compile-time and can be used for type properties such as kinds or dimensions.

INC = 4: Incremented from more than one cell column (see the LFRic API section of the User Guide).

INQUIRY = 9: The property/ies of a symbol is/are queried but the data it represents is not accessed (e.g. ‘var’ in SIZE(var, dim=1)).

READ = 1: Data associated with the symbol is read.

READINC = 5: Read before incrementing. Requires that the outermost halo be clean (see the LFRic API section of the User Guide).

READWRITE = 3: Data associated with the symbol is both read and written (e.g. is passed to a routine with intent(inout)).

REDUCTION = 6: Is the output of a (min/max/sum) reduction.

UNKNOWN = 7: This is used internally to indicate unknown access type of a variable, e.g. when a variable is passed to a subroutine and the access type of this variable in the subroutine is unknown. TODO #2863 - VariablesAccessMap does not currently consider UNKNOWN accesses and it should!

WRITE = 2: Data associated with the symbols is written.

static all_read_accesses()[source]

Return type:: list[AccessType]
Returns:: A list of all access types that involve reading an argument in some form.

static all_write_accesses()[source]

Return type:: list[AccessType]
Returns:: A list of all access types that involve writing to an argument in some form.

api_specific_name()[source]

This convenience function returns the name of the type in the current API. E.g. in the lfric API, WRITE –> “gh_write”. If no mapping is available then the generic name is returned.

Return type:: str
Returns:: The API specific name.

static from_string(access_string)[source]

Convert a string (e.g. “read”) into the corresponding AccessType enum value (AccessType.READ).

Parameters:: access_string (str) – Access type as a string.
Return type:: AccessType
Returns:: Corresponding AccessType enum.
Raises:: ValueError – if access_string is not a valid access type.

static non_data_accesses()[source]

Return type:: list[AccessType]
Returns:: all access types that do not touch any data associated with a symbol.

VariablesAccessMap#

The VariablesAccessMap class is used to store information about all accesses in a region of code. To collect access information, call any Node reference_accesses() method for the code region of interest. It will return the accesses for the PSyIR in a dictionary of kind VariablesAccessMap.

Node.reference_accesses()[source]

Return type:: VariablesAccessMap
Returns:: a map of all the symbol accessed inside this node, the keys are Signatures (unique identifiers to a symbol and its structure accessors) and the values are AccessSequence (a sequence of AccessTypes).

class psyclone.core.VariablesAccessMap[source]

This dictionary stores AccessSequence instances indexed by their signature.

__str__()[source]: Gives a shortened visual representation of all variables and their access mode

add_access(signature, access_type, node)[source]

Adds access information for the variable with the given signature.

Parameters:

signature (Signature) – the signature of the variable.
access_type (AccessType) – the type of access (READ, WRITE, …)
node (Node) – Node in PSyIR in which the access happens.

Return type:

None

property all_data_accesses: List[Signature]

Returns:: all Signatures in this instance that have a data access (i.e. the data associated with them is read or written).

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_called(signature)[source]

Parameters:: signature (Signature) – signature of the variable.
Return type:: bool
Returns:: True if the specified variable is called at least once.

is_read(signature)[source]

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

Parameters:: signature (psyclone.core.Signature) – signature of the variable
Return type:: bool
Returns:: True if the specified variable name is read (at least once).
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 (Signature) – signature of the variable.
Return type:: bool
Returns:: True if the specified variable is written (at least once).
Raises:: KeyError if the signature name cannot be found.

update(other_access_map)[source]

Updates this dictionary with the entries in the provided VariablesAccessMap. If there are repeated signatures, the provided values are appended to the existing sequence of accesses.

Parameters:: other_access_map (VariablesAccessMap) – the other VariablesAccessMap instance.
Return type:: None

This class collects information for each variable used in the tree starting with the given node. Use the update() method to combine two VariablesAccessMap objects into one. It is up to the user to keep track of which statements (PSyIR nodes) a given VariablesAccessMap instance is holding information about. If the PSyIR tree is modified the VariablesAccessMap maps become invalid, so it is not recommended to store them.

AccessSequence#

The values of the VariablesAccessMap map are AccessSequence, which contain the sequence of accesses to a given variable. When a new variable is detected when adding access information to a VariablesAccessMap instance via the add_access() method, a new instance of AccessSequence is added, which in turn stores all accesses to the specified variable.

class psyclone.core.AccessSequence(signature)[source]

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

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

add_access(access_type, node)[source]

Adds access information to this variable.

Parameters:

access_type (AccessType) – the type of access (READ, WRITE, ….)
node (Node) – Node in PSyIR in which the access happens.

Return type:

None

property all_read_accesses: list[AccessInfo]

Returns:: a list with all AccessInfo data for this variable that involve reading this variable.

property all_write_accesses: list[AccessInfo]

Returns:: a list with all AccessInfo data for this variable that involve writing this variable.

has_data_access()[source]

Return type:: bool
Returns:: True if there is an access of the data associated with this signature (as opposed to a call or an inquiry), False otherwise.

has_indices(index_variable=None)[source]

Checks whether this variable accesses has any index. If the optional index_variable is provided, only indices involving the given variable are considered.

Parameters:: index_variable (Optional[str]) – only consider index expressions that involve this variable.
Return type:: bool
Returns:: true if any of the accesses has an index.

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_called()[source]

Return type:: bool
Returns:: whether or not any accesses of this variable represent a call.

is_read()[source]

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

is_read_only()[source]

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

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

is_written()[source]

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

is_written_first()[source]

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

property signature: Signature

Returns:: the signature for which the accesses are stored.

str_access_summary()[source]

Return type:: str
Returns:: a string of the accesstypes but removing duplicates.

update(access_seq)[source]

This function adds all accesses from the given access sequence to this access sequence.

Parameters:: access_seq (AccessSequence) – the accesses to add to this object.
Raises:: ValueError – if the given access sequence is for a different signature.
Return type:: None

property var_name: str

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

AccessInfo#

The class AccessSequence is an ordered 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() is called.

class psyclone.core.AccessInfo(access_type, node)[source]

This class stores information about an access to a variable (the node where it happens and the type of access, and the index accessed if available).

Parameters:

access – the access type.
node (Union[Node, Symbol]) – Node in PSyIR in which the access happens, can also be a DataSymbol.

property access_type: AccessType

Returns:: the access type.

component_indices()[source]

Returns:: a tuple of tuples of index expressions; one for every component in the accessor. For example, for a scalar it returns (()), for a%b it returns ((),()) - two components with 0 indices in each, and for a(i)%b(j,k+1) it returns ((i,),(j,k+1)).

property description: str

Returns:: a textual description of this access for use in error messages.

has_indices()[source]

Check if the expression is a reference that has indices in any of its components.

Return type:: bool

is_any_read()[source]

Return type:: bool
Returns:: whether this access represents a write of any kind.

is_any_write()[source]

Return type:: bool
Returns:: whether this access represents a write of any kind.

property is_data_access: bool

Returns:: whether or not this access is to the data associated with a signature (i.e. is not just an inquiry-type access).

property node: Node | Symbol

Returns:: the PSyIR node at which this access happens.

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 = omp_directive.reference_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_sequence = 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
    if len(access_sequence) == 1:
        continue

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

The next, hypothetical example shows how the VariablesAccessMap 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 = VariablesAccessMap()
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 an LFRic or GOcean kernel, the variable access mode for parameters is taken from the kernel metadata, not from the actual kernel source code.

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

can_loops_be_fused(loop1, loop2)[source]

Function that verifies if two loops can be fused.

Parameters:

loop1 (psyclone.psyir.nodes.Loop) – the first loop.
loop2 (psyclone.psyir.nodes.Loop) – the second loop.

Returns:

whether the loops can be fused or not.

Return type:

bool

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 ReplaceInductionVariableTrans, 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)

DefinitionUseChain#

PSyclone also provides a DefinitionUseChain class, which can search for forward and backward dependencies for a given Reference inside a region of code. This implementation differs from the DependencyTools as it is control-flow aware, so can find many dependencies for a single Reference in a given Routine or scope.

This is primarily used to implement the Reference.next_accesses and Reference.previous_accesses functions, but can be used directly as follows:

chain = DefinitionUseChain(reference)
accesses = chain.find_forward_accesses()
# accesses contains Nodes that are dependent on reference
accesses[0].....

By default the dependencies will be searched for in the containing Routine.

Limitations#

At the moment the DefinitionUseChain assumes that any control flow could not be taken, i.e. any code inside a Loop or If statement is not guaranteed to occur. These dependencies will be found, but will not limit further searching into the tree. Additionally, GOTO statements are not supported and if found, will throw an Exception.