loki.analyse.analyse_dataflow

Collection of dataflow analysis schema routines.

Functions

array_loop_carried_dependencies(loop[, loop_var])	Find arrays that have true loop-carried dependencies based on subscript analysis.
attach_dataflow_analysis(module_or_routine)	Determine and attach to each IR node dataflow analysis metadata.
classify_array_access_offsets(loop[, loop_var])	For a given loop, classify all array accesses in the loop body by their subscript offset relative to the loop induction variable.
classify_nonzero_offset_arrays(...)	Scan all loops in a routine (or IR subtree) whose induction variable matches loop_var and return the set of array names that are accessed at any non-zero offset of that variable.
dataflow_analysis_attached(module_or_routine)	Create a context in which information about defined, live and used symbols is attached to each IR node
detach_dataflow_analysis(module_or_routine)	Remove from each IR node the stored dataflow analysis metadata.
detect_loop_carry_variables(loop[, loop_var])	Detect variables that serve as inter-iteration state carriers within a loop.
extract_offset(dim, loop_var)	Extract the integer offset of an array subscript expression relative to a loop variable.
loop_carried_dependencies(loop)	Find variables that are potentially loop-carried dependencies.
read_after_write_vars(ir, inspection_node)	Find variables that are read after being written in the given IR.
strip_nested_dimensions(expr)	Strip dimensions from array expressions of arbitrary derived-type nesting depth.

Classes

DataflowAnalysisAttacher([include_literal_kinds])	Analyse and attach in-place the definition, use and live status of symbols.
DataflowAnalysisDetacher(**kwargs)	Remove in-place any dataflow analysis properties.
FindReads([start, stop, active, ...])	Look for reads in a specified part of a control flow tree.
FindWrites([start, stop, active, candidate_set])	Look for writes in a specified part of a control flow tree.

dataflow_analysis_attached(module_or_routine)

Create a context in which information about defined, live and used symbols is attached to each IR node

This makes for each IR node the following properties available:

• Node.live_symbols: symbols defined before the node;

• Node.defines_symbols: symbols (potentially) defined by the node;

• Node.uses_symbols: symbols used by the node that had to be defined before.

This is an in-place update of nodes and thus existing references to IR nodes remain valid. When leaving the context the information is removed from IR nodes, while existing references remain valid.

The analysis is based on a rather crude regions-based analysis, with the hierarchy implied by (nested) InternalNode IR nodes used as regions in the reducible flow graph (cf. Chapter 9, in particular 9.7 of Aho, Lam, Sethi, and Ulliman (2007)). Our implementation shares some similarities with a full reaching definitions dataflow analysis but is not quite as powerful.

In reaching definitions dataflow analysis (cf. Chapter 9.2.4 Aho et. al.), the transfer function of a definition \(d\) can be expressed as:

\[f_d(x) = \operatorname{gen}_d \cup (x - \operatorname{kill}_d)\]

with the set of definitions generated \(\operatorname{gen}_d\) and the set of definitions killed/invalidated \(\operatorname{kill}_d\).

We, however, do not record definitions explicitly and instead operate on consolidated sets of defined symbols, i.e., effectively evaluate the chained transfer functions up to the node. This yields a set of active definitions at this node. The symbols defined by these definitions are in Node.live_symbols, and the symbols defined by the node (i.e., symbols defined by definitions in \(\operatorname{gen}_d\)) are in Node.defines_symbols.

The advantage of this approach is that it avoids the need to introduce a layer for definitions and dependencies. A downside is that this focus on symbols instead of definitions precludes, in particular, the ability to take data space into account, which makes it less useful for arrays.

Note

The context manager operates only on the module or routine itself (i.e., its spec and, if applicable, body), not on any contained subroutines or functions.

Parameters:

module_or_routine (Module or Subroutine) – The object for which the IR is to be annotated.

read_after_write_vars(ir, inspection_node)

Find variables that are read after being written in the given IR.

This requires prior application of dataflow_analysis_attached() to the corresponding Module or Subroutine.

The result is the set of variables with a data dependency across the inspection_node.

See the remarks about implementation and limitations in the description of dataflow_analysis_attached(). In particular, this does not take into account data space and iteration space for arrays.

Parameters:

• ir (Node) – The root of the control flow (sub-)tree to inspect.

• inspection_node (Node) – Only variables with a write before and a read at or after this node are considered.

Returns:

The list of read-after-write variables.

Return type:

set of Scalar or Array

loop_carried_dependencies(loop)

Find variables that are potentially loop-carried dependencies.

This requires prior application of dataflow_analysis_attached() to the corresponding Module or Subroutine.

See the remarks about implementation and limitations in the description of dataflow_analysis_attached(). In particular, this does not take into account data space and iteration space for arrays. For cases with a linear mapping from iteration to data space and no overlap, this will falsely report loop-carried dependencies when there are in fact none. However, the risk of false negatives should be low.

Parameters:

loop (Loop) – The loop node to inspect.

Returns:

The list of variables that potentially have a loop-carried dependency.

Return type:

set of Scalar or Array

classify_array_access_offsets(loop, loop_var=None)

For a given loop, classify all array accesses in the loop body by their subscript offset relative to the loop induction variable.

This is a subscript-aware analysis that goes beyond the symbol-level loop_carried_dependencies(). It examines which dimension of each array uses the loop variable and at what offset (e.g., JK, JK-1, JK+1).

Parameters:

• loop (Loop) – The loop node to analyse.

• loop_var (expression, optional) – The loop induction variable. If not given, uses loop.variable.

Returns:

A dict mapping (array_name, dim_index) to a dict of {offset: set_of_access_types} where access_types are 'read' and/or 'write'. For example:

{
    ('flux', 2): {0: {'read'}, 1: {'write'}},
    ('temp', 1):  {0: {'read', 'write'}, -1: {'read'}},
}

Return type:

dict

array_loop_carried_dependencies(loop, loop_var=None)

Find arrays that have true loop-carried dependencies based on subscript analysis.

Unlike loop_carried_dependencies(), this function examines the actual array subscript offsets relative to the loop induction variable to determine whether different iterations of the loop access overlapping data elements.

A loop-carried dependency exists when:

• Flow (RAW): An array is written at offset w and read at offset r where w != r (the read at iteration k accesses data written at iteration k + (r - w)).

• Anti (WAR): An array is read at offset r and written at offset w where w != r.

• Output (WAW): An array is written at two different offsets.

The dependency distance is r - w for flow dependencies.

Parameters:

• loop (Loop) – The loop node to analyse.

• loop_var (expression, optional) – The loop induction variable. If not given, uses loop.variable.

Returns:

A dict mapping array_name to a list of dependency descriptors. Each descriptor is a dict with keys:

• 'type': one of 'flow' (RAW), 'anti' (WAR), 'output' (WAW)

• 'dim_index': which dimension (0-based) carries the dependency

• 'write_offset': integer offset of the write access

• 'read_offset': integer offset of the read access (for flow/anti) or second write offset (for output)

• 'distance': the dependency distance (positive means the read depends on data from an earlier iteration in an ascending loop)

Example:

{
    'flux': [
        {'type': 'flow', 'dim_index': 2, 'write_offset': 1,
         'read_offset': 0, 'distance': -1}
    ],
    'temp': [
        {'type': 'flow', 'dim_index': 1, 'write_offset': 0,
         'read_offset': -1, 'distance': -1}
    ]
}

Return type:

dict

detect_loop_carry_variables(loop, loop_var=None)

Detect variables that serve as inter-iteration state carriers within a loop.

This identifies two patterns commonly found in iterative computations:

1. Scalar carries: Variables with no loop-variable dimension (e.g., 1-D arrays or scalars) that are both read and written within the loop body. These propagate state from one iteration to the next.

2. Shift registers: Arrays with a loop-variable dimension that are written at one offset and read at a different offset of the loop variable (e.g., written at JK+1 and read at JK).

Parameters:

• loop (Loop) – The loop node to analyse.

• loop_var (expression, optional) – The loop induction variable. If not given, uses loop.variable.

Returns:

A dict with two keys:

• 'scalar_carries': list of dicts, each with:

  • 'name': variable name (lowercased)

• 'shift_registers': list of dicts, each with:

  • 'name': array name (lowercased)

  • 'dim_index': which dimension carries the shift

  • 'write_offset': integer offset of the write

  • 'read_offset': integer offset of the read

  • 'direction': 'downward' if write_offset > read_offset (data flows from lower to higher index in an ascending loop), 'upward' otherwise

Return type:

dict

classify_nonzero_offset_arrays(routine_or_node, loop_var)

Scan all loops in a routine (or IR subtree) whose induction variable matches loop_var and return the set of array names that are accessed at any non-zero offset of that variable.

This is a routine-wide version of the per-loop classify_array_access_offsets(). It collects information from every loop whose induction variable matches loop_var (by name, case-insensitive). An array is classified as “non-zero offset” if, in any of those loops, it is accessed at an offset other than 0 (e.g., JK-1, JK+1).

The result can be used to decide which arrays in a mixed init loop need to remain in a separate (non-fused) loop and which can safely participate in fusion and subsequent demotion.

Parameters:

• routine_or_node (Subroutine or Node) – The routine or IR subtree to scan. If a Subroutine, the routine’s body is scanned.

• loop_var (Scalar, str, or DeferredTypeSymbol) – The loop induction variable whose offsets are of interest.

Returns:

Lowercased array names that have at least one access at a non-zero offset of loop_var anywhere in the scanned IR.

Return type:

set of str

extract_offset(dim, loop_var)

Extract the integer offset of an array subscript expression relative to a loop variable.

For example, if dim is JK - 1 and loop_var is JK, this returns -1. If dim is exactly JK, this returns 0. If dim does not involve loop_var or is non-affine, returns None.

Parameters:

• dim (expression) – The subscript expression for one dimension of an array access.

• loop_var (Scalar or str) – The loop induction variable.

Returns:

The integer offset, or None if the expression is not an affine function of loop_var.

Return type:

int or None