loki.analyse.dataflow_analysis

Collection of dataflow analysis schema routines.

Functions

attach_dataflow_analysis(module_or_routine)

Determine and attach to each IR node dataflow analysis metadata.

dataflow_analysis_attached(module_or_routine)

detach_dataflow_analysis(module_or_routine)

Remove from each IR node the stored dataflow analysis metadata.

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

DataflowAnalysis([include_literal_kinds])

Concrete DFA implementation based on a simplified Reaching Definition Dataflow Analysis, using the current attacher and detacher logic.

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.
strip_nested_dimensions(expr)

Strip dimensions from array expressions of arbitrary derived-type nesting depth.

class DataflowAnalysis(include_literal_kinds=True)

Bases: AbstractDataflowAnalysis

Concrete DFA implementation based on a simplified Reaching Definition Dataflow Analysis, using the current attacher and detacher logic.

This data flow 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.

get_attacher() → Any

Returns an instance of the associated “Attacher” Transformation.

resolve_call_effects(call, *, attacher, **kwargs)
attach_dataflow_analysis(module_or_routine)
detach_dataflow_analysis(module_or_routine)
class DataflowAnalysisAttacher(include_literal_kinds=True, **kwargs)

Bases: Transformer

Analyse and attach in-place the definition, use and live status of symbols.

Parameters:

include_literal_kinds (bool (default : True)) – Include kind specifiers for literals in dataflow analysis.

visit_Node(o, **kwargs)

Handler for Node objects.

It replaces o by mapper[o], if it is in the mapper, otherwise visits all children before rebuilding the node.

visit_Interface(o, **kwargs)
visit_InternalNode(o, **kwargs)
visit_Associate(o, **kwargs)
visit_Loop(o, **kwargs)
visit_WhileLoop(o, **kwargs)
visit_Conditional(o, **kwargs)
visit_MultiConditional(o, **kwargs)
visit_TypeConditional(o, **kwargs)
visit_MaskedStatement(o, **kwargs)
visit_Assignment(o, **kwargs)
visit_ConditionalAssignment(o, **kwargs)
visit_CallStatement(o, **kwargs)
visit_Allocation(o, **kwargs)
visit_Deallocation(o, **kwargs)
visit_Nullify(o, **kwargs)
visit_Import(o, **kwargs)
visit_VariableDeclaration(o, **kwargs)
visit_StatementFunction(o, **kwargs)

Handler for Node objects.

It replaces o by mapper[o], if it is in the mapper, otherwise visits all children before rebuilding the node.

class DataflowAnalysisDetacher(**kwargs)

Bases: Transformer

Remove in-place any dataflow analysis properties.

visit_Node(o, **kwargs)

Handler for Node objects.

It replaces o by mapper[o], if it is in the mapper, otherwise visits all children before rebuilding the node.

attach_dataflow_analysis(module_or_routine)

Determine and attach to each IR node dataflow analysis metadata.

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, i.e., live in subsequent nodes;

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

The IR nodes are updated in-place and thus existing references to IR nodes remain valid.

detach_dataflow_analysis(module_or_routine)

Remove from each IR node the stored dataflow analysis metadata.

Accessing the relevant attributes afterwards raises RuntimeError.

dataflow_analysis_attached(module_or_routine)
class FindReads(start=None, stop=None, active=False, candidate_set=None, clear_candidates_on_write=False, **kwargs)

Bases: Visitor

Look for reads in a specified part of a control flow tree.

Parameters:

  • start ((iterable of) Node, optional) – Visitor is only active after encountering one of the nodes in start and until encountering a node in stop.

  • stop ((iterable of) Node, optional) – Visitor is no longer active after encountering one of the nodes in stop until it encounters again a node in start.

  • active (bool, optional) – Set the visitor active right from the beginning.

  • candidate_set (set of Node, optional) – If given, only reads for symbols in this set are considered.

  • clear_candidates_on_write (bool, optional) – If enabled, writes of a symbol remove it from the candidate_set.

visit(o, *args, **kwargs)

Apply this Visitor to an IR tree.

Parameters:

  • o (Node) – The node to visit.

  • *args – Optional arguments to pass to the visit methods.

  • **kwargs – Optional keyword arguments to pass to the visit methods.

visit_object(o, **kwargs)

Fallback method for objects that do not match any handler.

Parameters:

  • o – The object to visit.

  • **kwargs – Optional keyword arguments passed to the visit methods.

Returns:

The default return value.

Return type:

GenericVisitor.default_retval()

visit_LeafNode(o, **kwargs)
visit_Conditional(o, **kwargs)
visit_Loop(o, **kwargs)
visit_WhileLoop(o, **kwargs)
class FindWrites(start=None, stop=None, active=False, candidate_set=None, **kwargs)

Bases: Visitor

Look for writes in a specified part of a control flow tree.

Parameters:

  • start ((iterable of) Node, optional) – Visitor is only active after encountering one of the nodes in start and until encountering a node in stop.

  • stop ((iterable of) Node, optional) – Visitor is no longer active after encountering one of the nodes in stop until it encounters again a node in start.

  • active (bool, optional) – Set the visitor active right from the beginning.

  • candidate_set (set of Node, optional) – If given, only writes for symbols in this set are considered.

visit(o, *args, **kwargs)

Apply this Visitor to an IR tree.

Parameters:

  • o (Node) – The node to visit.

  • *args – Optional arguments to pass to the visit methods.

  • **kwargs – Optional keyword arguments to pass to the visit methods.

visit_object(o, **kwargs)

Fallback method for objects that do not match any handler.

Parameters:

  • o – The object to visit.

  • **kwargs – Optional keyword arguments passed to the visit methods.

Returns:

The default return value.

Return type:

GenericVisitor.default_retval()

visit_LeafNode(o, **kwargs)
visit_Loop(o, **kwargs)
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