# loki.analyse.dataflow_analysis module

Collection of dataflow analysis schema routines.

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`