Repository: stfc/PSyclone (python)

Issue:
LFRic-specific Dependency Analysis
As part of #2197, we are moving to using pointers to pass data to kernel calls so as to avoid accessing structures within an OpenACC region (e.g. `my_proxy%data`). However, the Dependence Analysis now sees that we are passing an array to a kernel and, by default, we give all such arguments read-write access (`Call.reference_accesses`). It therefore correctly identifies that this is a potential race condition (since it doesn't know which elements of the array are written to) and says the call cannot be safely executed in parallel.

Since the call is actually to an LFRic kernel (which are only permitted to write to data in the current column), we can do better:

 * If the field is on a discontinuous function space then the access is safe;
 * If the parent loop is over dofs then the access is safe;
 * If the parent loop is over cells of a single colour then the access is safe;

The potential solution to this is to encapsulate this domain knowledge in a domain specialisation of the dependence analysis.

Pull request:
(Closes #2293) Add 'is_independent' property/query to Loop
This will enable the dependence analysis to be made domain-specific in a natural and efficient manner.

Patch:
diff --git a/changelog b/changelog
index 667e2962f..f52c414c2 100644
--- a/changelog
+++ b/changelog
@@ -590,6 +590,8 @@
 	198) PR #2283 for #2282 and #2286. Adds a get_ubound_expression
 	method to ArrayMixin (analagous to get_lbound_expression).
 
+	199) PR #2293 for #2301. Add 'is_independent' property/query to Loop.
+
 release 2.3.1 17th of June 2022
 
 	1) PR #1747 for #1720. Adds support for If blocks to PSyAD.
diff --git a/doc/developer_guide/dependency.rst b/doc/developer_guide/dependency.rst
index ee619e439..1bcad8bb8 100644
--- a/doc/developer_guide/dependency.rst
+++ b/doc/developer_guide/dependency.rst
@@ -1,7 +1,7 @@
 .. -----------------------------------------------------------------------------
    BSD 3-Clause License
 
-   Copyright (c) 2021-2022, Science and Technology Facilities Council.
+   Copyright (c) 2021-2023, Science and Technology Facilities Council.
    All rights reserved.
 
    Redistribution and use in source and binary forms, with or without
@@ -49,11 +49,12 @@
     Config.get().api = "nemo"
 
     code = '''subroutine sub()
-    integer :: i, j, k, a(10, 10)
+    integer :: i, j, k, a(11, 11)
     a(i,j) = 1
     do i=1, 10
        j = 3
        a(i,i) = j + k
+       a(i,i) = a(i+1,i+1)
     enddo
     end subroutine sub
     '''
@@ -65,10 +66,10 @@
     access_info = all_a_accesses[0]
 
     # Take the loop node:
-    loop = psyir.children[0][1]
+    loop = psyir.walk(Loop)[0]
     loop_statements = [loop]
     # One example uses code from an OMP directive to determine
-    # private variables. But since all this example does is calling
+    # private variables. But since all this example does is call
     # `reference_accesses`, we can just pass in the PSyIR node of
     # the loop, which results in two private variables (to avoid
     # creating an OMP Parallel etc)
@@ -516,6 +517,7 @@ thread-private. Note that this code does not handle the usage of
         do i=1, 10
            j = 3
            a(i,i) = j + k
+	   a(i-1,i) = a(i,i) + 1
         enddo
     It should therefore report that 'i' and 'j' should be private
     variables, 'k' is not initialised and therefore assumed to be public.
@@ -594,7 +596,7 @@ until we find accesses that would prevent parallelisation:
 .. testoutput::
     :hide:
 
-    The first 2 statements can be parallelised.
+    The first 3 statements can be parallelised.
 
 
 .. note:: There is a certain overlap in the dependency analysis code
@@ -625,27 +627,20 @@ uses `SymPy` internally to compare expressions symbolically.
           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. It takes a list of statements
+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:
 
 ..
     The setup passes a single (not-nested) loop as `loop_statements`.
-    This loop triggers the message that it is not a nested loop and
-    is therefore not be parallelised by default.
 
 .. testcode::
 
    parallel_loop = OMPLoopTrans()
-   # The loops in the Fortran functions that must be parallelised
-   # are over the 'lat' domain. Note that the psyclone config
-   # file specifies the mapping of loop variable to type, e.g.:
-   #
-   #   mapping-lat = var: jj, start: 1, stop: jpj
-   #
-   # This means any loop using the variable 'jj' is considered a
-   # loop of type 'lat'
-   dt = DependencyTools(["lat"])
+   dt = DependencyTools()
 
    for statement in loop_statements:
        if isinstance(statement, Loop):
@@ -662,4 +657,4 @@ can be parallelised:
 .. testoutput::
     :hide:
 
-    Info: Not a nested loop.
+    Error: The write access to 'a(i,i)' and to 'a(i + 1,i + 1)' are dependent and cannot be parallelised.
diff --git a/examples/nemo/scripts/utils.py b/examples/nemo/scripts/utils.py
index d60a38e3c..7b464827d 100755
--- a/examples/nemo/scripts/utils.py
+++ b/examples/nemo/scripts/utils.py
@@ -44,7 +44,6 @@ from psyclone.psyir.transformations import HoistLoopBoundExprTrans, \
     HoistTrans, ProfileTrans, HoistLocalArraysTrans, Reference2ArrayRangeTrans
 from psyclone.domain.nemo.transformations import NemoAllArrayRange2LoopTrans
 from psyclone.transformations import TransformationError
-from psyclone.psyir.tools import DependencyTools
 
 
 # If routine names contain these substrings then we do not profile them
@@ -218,9 +217,8 @@ def insert_explicit_loop_parallelism(
         many nested loops as possible.
     :param collapse: whether to insert directive on loops with Calls or \
         CodeBlocks in their loop body.
-    '''
-    dep_tools = DependencyTools()
 
+    '''
     # Add the parallel directives in each loop
     for loop in schedule.walk(Loop):
         if loop.ancestor(Directive):
@@ -328,7 +326,7 @@ def insert_explicit_loop_parallelism(
                     break
 
                 # Check that the next loop has no loop-carried dependencies
-                if not dep_tools.can_loop_be_parallelised(next_loop):
+                if not next_loop.independent_iterations():
                     break
 
             # Add collapse clause to the parent directive
diff --git a/src/psyclone/dynamo0p3.py b/src/psyclone/dynamo0p3.py
index 6bba02d9c..fa89afac6 100644
--- a/src/psyclone/dynamo0p3.py
+++ b/src/psyclone/dynamo0p3.py
@@ -7514,6 +7514,113 @@ class DynLoop(PSyLoop):
                                    f"set_clean({halo_depth})")
                     parent.add(call)
 
+    def independent_iterations(self,
+                               test_all_variables=False,
+                               signatures_to_ignore=None,
+                               dep_tools=None):
+        '''
+        This function is an LFRic-specific override of the default method
+        in the Loop class. It allows domain-specific rules to be applied when
+        determining whether or not loop iterations are independent.
+
+        :param bool test_all_variables: 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.
+        :param signatures_to_ignore: list of signatures for which to skip
+            the access checks.
+        :type signatures_to_ignore: Optional[
+            List[:py:class:`psyclone.core.Signature`]]
+        :param dep_tools: an optional instance of DependencyTools so that the
+            caller can access any diagnostic messages detailing why the loop
+            iterations are not independent.
+        :type dep_tools: Optional[
+            :py:class:`psyclone.psyir.tools.DependencyTools]
+
+        :returns: True if the loop iterations are independent, False otherwise.
+        :rtype: bool
+
+        '''
+        # pylint: disable=import-outside-toplevel
+        from psyclone.psyir.tools import DependencyTools, DTCode
+        if not dep_tools:
+            dtools = DependencyTools()
+        else:
+            dtools = dep_tools
+
+        if self.loop_type in ["null", "colours"]:
+            # We know we can't parallelise these loops. ("null" means there
+            # is no actual loop and "colours" is the *outer* loop over the
+            # different colours used - it is the inner, "colour" loop over
+            # cells of a single colour which can be parallelised.)
+            return False
+
+        try:
+            stat = dtools.can_loop_be_parallelised(
+                self, test_all_variables=test_all_variables,
+                signatures_to_ignore=signatures_to_ignore)
+            if stat:
+                return True
+        except (InternalError, KeyError):
+            # LFRic still has symbols that don't exist in the symbol_table
+            # until the gen_code() step, so the dependency analysis raises
+            # errors in some cases.
+            # TODO #1648 - when a transformation colours a loop we must
+            # ensure "last_[halo]_cell_all_colours" is added to the symbol
+            # table.
+            return True
+
+        # The generic DA says that this loop cannot be parallelised. However,
+        # that is often because it wrongly identifies field/operator array
+        # accesses (e.g. fld_proxy%data) as being scalars that are written to.
+        if self.loop_type in ["colour", "dof"]:
+            # This loop is either over cells of a single colour or DoFs. So
+            # long as the symbols that the DA is complaining about are fields
+            # or operators then this is safe to parallelise.
+            table = self.scope.symbol_table
+            # Create the set of all LFRic field types.
+            all_fld_names = set(desc["type"] for desc in
+                                LFRicConstants().DATA_TYPE_MAP.values())
+
+            for msg in dtools.get_all_messages():
+                if msg.code != DTCode.WARN_SCALAR_WRITTEN_ONCE:
+                    # The DA is complaining about something other than writing
+                    # to (what it thinks is) a scalar.  Therefore the loop
+                    # cannot be parallelised.
+                    return False
+                # Currently the DA (wrongly) identifies things like
+                # 'fld_proxy%data' as being scalar accesses. We therefore need
+                # to check that the argument it says is a scalar is in fact a
+                # field. If it is, this is safe to parallelise (because an
+                # LFRic Kernel is constrained to write to dofs in the 'owned'
+                # column).
+                # TODO #2197 - when we change the PSy layer to pass field
+                # pointers to kernels, the DA will identify that they are
+                # arrays and this logic will need to be changed.
+                for name in msg.var_names:
+                    sym = table.lookup(name)
+                    # Ideally at this point we would compare sym.datatype with
+                    # LFRicTypes("RealFieldDataType") etc. but the LFRic PSy
+                    # layer doesn't use those types yet.
+                    if not (isinstance(sym.datatype, DataTypeSymbol) and
+                            sym.datatype.name in all_fld_names):
+                        # The Symbol is not a field or operator.
+                        return False
+            # All of the variables referred to in all of the messages are
+            # actually fields - it is safe to ignore this warning.
+            return True
+
+        if self.loop_type == "":
+            # We can parallelise a non-coloured loop if it only updates
+            # quantities on discontinuous function spaces. If an LFRic kernel
+            # updates quantities on a continuous function space then it must
+            # have at least one argument with GH_INC access. Therefore, we
+            # can simply check whether or not it has such an argument in order
+            # to infer the continuity of the space.
+            return not self.has_inc_arg()
+
+        raise InternalError(f"independent_iterations: loop of type "
+                            f"'{self.loop_type}' is not supported.")
+
 
 class DynKern(CodedKern):
     ''' Stores information about Dynamo Kernels as specified by the
diff --git a/src/psyclone/gocean1p0.py b/src/psyclone/gocean1p0.py
index d1abf1d8d..9d4a4c89b 100644
--- a/src/psyclone/gocean1p0.py
+++ b/src/psyclone/gocean1p0.py
@@ -511,6 +511,48 @@ class GOLoop(PSyLoop):
         '''
         return self._bounds_lookup
 
+    def independent_iterations(self,
+                               test_all_variables=False,
+                               signatures_to_ignore=None,
+                               dep_tools=None):
+        '''
+        This function is a GOcean-specific override of the default method
+        in the Loop class. It allows domain-specific rules to be applied when
+        determining whether or not loop iterations are independent.
+
+        :param bool test_all_variables: 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.
+        :param signatures_to_ignore: list of signatures for which to skip
+            the access checks.
+        :type signatures_to_ignore: Optional[
+            List[:py:class:`psyclone.core.Signature`]]
+        :param dep_tools: an optional instance of DependencyTools so that the
+            caller can access any diagnostic messages detailing why the loop
+            iterations are not independent.
+        :type dep_tools: Optional[
+            :py:class:`psyclone.psyir.tools.DependencyTools]
+
+        :returns: True if the loop iterations are independent, False otherwise.
+        :rtype: bool
+
+        '''
+        if not dep_tools:
+            from psyclone.psyir.tools import DependencyTools
+            dtools = DependencyTools()
+        else:
+            dtools = dep_tools
+
+        try:
+            stat = dtools.can_loop_be_parallelised(
+                self, test_all_variables=test_all_variables,
+                signatures_to_ignore=signatures_to_ignore)
+            return stat
+        except InternalError:
+            # The dependence analysis in GOcean doesn't yet use PSyIR
+            # consistently and that causes failures - TODO #845.
+            return True
+
     # -------------------------------------------------------------------------
     def _halo_read_access(self, arg):
         '''Determines whether the supplied argument has (or might have) its
diff --git a/src/psyclone/psyir/nodes/loop.py b/src/psyclone/psyir/nodes/loop.py
index e099fd393..6c3db9b18 100644
--- a/src/psyclone/psyir/nodes/loop.py
+++ b/src/psyclone/psyir/nodes/loop.py
@@ -294,8 +294,15 @@ class Loop(Statement):
         :returns: Return the dag name for this loop
         :rtype: string
 
+        :raises InternalError: if this Loop has no ancestor Routine.
+
         '''
-        _, position = self._find_position(self.ancestor(Routine))
+        routine = self.ancestor(Routine)
+        if not routine:
+            raise InternalError(f"Cannot generate DAG name for loop node "
+                                f"'{self}' because it is not contained within "
+                                f"a Routine.")
+        _, position = self._find_position(routine)
 
         return "loop_" + str(position)
 
@@ -379,6 +386,40 @@ class Loop(Statement):
             child.reference_accesses(var_accesses)
             var_accesses.next_location()
 
+    def independent_iterations(self,
+                               test_all_variables=False,
+                               signatures_to_ignore=None,
+                               dep_tools=None):
+        '''This function analyses a loop in the PSyIR to see whether
+        its iterations are independent.
+
+        :param bool test_all_variables: 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.
+        :param signatures_to_ignore: list of signatures for which to skip
+            the access checks.
+        :type signatures_to_ignore: Optional[
+            List[:py:class:`psyclone.core.Signature`]]
+        :param dep_tools: an optional instance of DependencyTools so that the
+            caller can access any diagnostic messages detailing why the loop
+            iterations are not independent.
+        :type dep_tools: Optional[
+            :py:class:`psyclone.psyir.tools.DependencyTools]
+
+        :returns: True if the loop iterations are independent, False otherwise.
+        :rtype: bool
+
+        '''
+        if not dep_tools:
+            # pylint: disable=import-outside-toplevel
+            from psyclone.psyir.tools import DependencyTools
+            dtools = DependencyTools()
+        else:
+            dtools = dep_tools
+        return dtools.can_loop_be_parallelised(
+            self, test_all_variables=test_all_variables,
+            signatures_to_ignore=signatures_to_ignore)
+
     def gen_code(self, parent):
         '''
         Generate the Fortran Loop and any associated code.
diff --git a/src/psyclone/psyir/tools/dependency_tools.py b/src/psyclone/psyir/tools/dependency_tools.py
index 761bea476..5294f8315 100644
--- a/src/psyclone/psyir/tools/dependency_tools.py
+++ b/src/psyclone/psyir/tools/dependency_tools.py
@@ -59,8 +59,6 @@ class DTCode(IntEnum):
 
     '''
     INFO_MIN = 1
-    INFO_NOT_NESTED_LOOP = 2
-    INFO_WRONG_LOOP_TYPE = 3
     INFO_MAX = 99
 
     WARN_MIN = 100
@@ -195,39 +193,6 @@ class DependencyTools():
         '''
         return self._messages
 
-    # -------------------------------------------------------------------------
-    def _is_loop_suitable_for_parallel(self, loop, only_nested_loops=True):
-        '''Simple first test to see if a loop should even be considered to
-        be parallelised. The default implementation tests whether the loop
-        has a certain type (e.g. 'latitude'), and optional tests for
-        nested loops (to avoid parallelising single loops which will likely
-        result in a slowdown due to thread synchronisation costs). This
-        function is used by can_loop_be_parallelised() and can of course be
-        overwritten by the user to implement different suitability criteria.
-
-        :param loop: the loop to test.
-        :type loop: :py:class:`psyclone.psyir.nodes.Loop`
-        :param bool only_nested_loops: true (default) if only nested loops\
-                                        should be considered.
-
-        :returns: true if the loop fulfills the requirements.
-        :rtype: bool
-        '''
-        if only_nested_loops:
-            all_loops = loop.walk(Loop)
-            if len(all_loops) == 1:
-                self._add_message("Not a nested loop.",
-                                  DTCode.INFO_NOT_NESTED_LOOP)
-                return False
-
-        if self._loop_types_to_parallelise:
-            if loop.loop_type not in self._loop_types_to_parallelise:
-                self._add_message(f"Loop has wrong loop type '"
-                                  f"{loop.loop_type}'.",
-                                  DTCode.INFO_WRONG_LOOP_TYPE)
-                return False
-        return True
-
     # -------------------------------------------------------------------------
     @staticmethod
     def _partition(comp_ind1, comp_ind2, loop_variables):
@@ -729,26 +694,23 @@ class DependencyTools():
 
     # -------------------------------------------------------------------------
     def can_loop_be_parallelised(self, loop,
-                                 only_nested_loops=True,
                                  test_all_variables=False,
                                  signatures_to_ignore=None):
         # pylint: disable=too-many-branches,too-many-locals
         '''This function analyses a loop in the PsyIR to see if
-        it can be safely parallelised over the specified variable.
+        it can be safely parallelised.
 
         :param loop: the loop node to be analysed.
         :type loop: :py:class:`psyclone.psyir.nodes.Loop`
-        :param bool only_nested_loops: if True, a loop must have an inner\
-                                       loop in order to be considered\
-                                       parallelisable (default: True).
-        :param bool test_all_variables: 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\
+        :param bool test_all_variables: 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.
-        :param signatures_to_ignore: list of signatures for which to skip \
+        :param signatures_to_ignore: list of signatures for which to skip
                                      the access checks.
-        :type signatures_to_ignore: list of :py:class:`psyclone.core.Signature`
+        :type signatures_to_ignore: Optional[
+            List[:py:class:`psyclone.core.Signature`]]
 
         :returns: True if the loop can be parallelised.
         :rtype: bool
@@ -763,14 +725,6 @@ class DependencyTools():
                             f"instance of class Loop but got "
                             f"'{type(loop).__name__}'")
 
-        # Check if the loop type should be parallelised, e.g. to avoid
-        # parallelising inner loops which might not have enough work. This
-        # is supposed to be a fast first check to avoid collecting variable
-        # accesses in some unsuitable loops.
-        if not self._is_loop_suitable_for_parallel(loop, only_nested_loops):
-            # Appropriate messages will have been added already, so just exit
-            return False
-
         var_accesses = VariablesAccessInfo(loop)
         if not signatures_to_ignore:
             signatures_to_ignore = []
diff --git a/src/psyclone/psyir/transformations/parallel_loop_trans.py b/src/psyclone/psyir/transformations/parallel_loop_trans.py
index fc91491cf..10f2c9bc6 100644
--- a/src/psyclone/psyir/transformations/parallel_loop_trans.py
+++ b/src/psyclone/psyir/transformations/parallel_loop_trans.py
@@ -1,7 +1,7 @@
 # -----------------------------------------------------------------------------
 # BSD 3-Clause License
 #
-# Copyright (c) 2017-2022, Science and Technology Facilities Council.
+# Copyright (c) 2017-2023, Science and Technology Facilities Council.
 # All rights reserved.
 #
 # Redistribution and use in source and binary forms, with or without
@@ -42,7 +42,6 @@ import abc
 
 from psyclone import psyGen
 from psyclone.domain.common.psylayer import PSyLoop
-from psyclone.errors import InternalError
 from psyclone.psyir import nodes
 from psyclone.psyir.nodes import Loop
 from psyclone.psyir.tools import DependencyTools, DTCode
@@ -108,7 +107,6 @@ class ParallelLoopTrans(LoopTrans, metaclass=abc.ABCMeta):
         super().validate(node, options=options)
 
         # Check we are not a sequential loop
-        # TODO add a list of loop types that are sequential
         if isinstance(node, PSyLoop) and node.loop_type == 'colours':
             raise TransformationError(f"Error in {self.name} transformation. "
                                       f"The target loop is over colours and "
@@ -148,28 +146,18 @@ class ParallelLoopTrans(LoopTrans, metaclass=abc.ABCMeta):
 
         dep_tools = DependencyTools()
 
-        try:
-            if not dep_tools.can_loop_be_parallelised(node,
-                                                      only_nested_loops=False):
-                # The DependencyTools also returns False for things that are
-                # not an issue, so we ignore specific messages.
-                for message in dep_tools.get_all_messages():
-                    if message.code == DTCode.WARN_SCALAR_WRITTEN_ONCE:
-                        continue
-                    all_msg_str = [str(message) for message in
-                                   dep_tools.get_all_messages()]
-                    messages = "\n".join(all_msg_str)
-                    raise TransformationError(
-                        f"Dependency analysis failed with the following "
-                        f"messages:\n{messages}")
-
-        except (KeyError, InternalError):
-            # LFRic still has symbols that don't exist in the symbol_table
-            # until the gen_code() step, so the dependency analysis raises
-            # KeyErrors in some cases.
-            # Also, the dependence analysis doesn't yet use PSyIR consistently
-            # and that causes failures - TOD0 #845.
-            pass
+        if not node.independent_iterations(dep_tools=dep_tools):
+            # The DependencyTools also returns False for things that are
+            # not an issue, so we ignore specific messages.
+            for message in dep_tools.get_all_messages():
+                if message.code == DTCode.WARN_SCALAR_WRITTEN_ONCE:
+                    continue
+                all_msg_str = [str(message) for message in
+                               dep_tools.get_all_messages()]
+                messages = "\n".join(all_msg_str)
+                raise TransformationError(
+                    f"Dependency analysis failed with the following "
+                    f"messages:\n{messages}")
 
     def apply(self, node, options=None):
         '''


Test patch:
diff --git a/src/psyclone/tests/domain/gocean/goloop_test.py b/src/psyclone/tests/domain/gocean/goloop_test.py
index e2935ada1..5af500203 100644
--- a/src/psyclone/tests/domain/gocean/goloop_test.py
+++ b/src/psyclone/tests/domain/gocean/goloop_test.py
@@ -1,7 +1,7 @@
 # -----------------------------------------------------------------------------
 # BSD 3-Clause License
 #
-# Copyright (c) 2021-2022, Science and Technology Facilities Council.
+# Copyright (c) 2021-2023, Science and Technology Facilities Council.
 # All rights reserved.
 #
 # Redistribution and use in source and binary forms, with or without
@@ -48,6 +48,8 @@ from psyclone.gocean1p0 import GOKern, GOLoop, GOInvokeSchedule
 from psyclone.psyir.nodes import (Schedule, Reference, StructureReference,
                                   Node, Literal)
 from psyclone.psyir.symbols import DataSymbol, INTEGER_TYPE
+from psyclone.psyir.tools import DependencyTools
+from psyclone.psyir.tools.dependency_tools import DTCode
 from psyclone.tests.utilities import get_invoke
 
 API = "gocean1.0"
@@ -337,3 +339,35 @@ def test_loop_bound_when_fparser_not_initialised():
     class list.
     '''
     GOLoop.add_bounds("go_offset_sw:go_ct:internal_we_halo:1:2:3:4")
+
+
+def test_independent_iterations(monkeypatch):
+    '''Test the independent_iterations method of GOLoop.'''
+    schedule = GOInvokeSchedule('name', [])
+    goloop = GOLoop(loop_type="inner", parent=schedule)
+    assert goloop.independent_iterations()
+
+    # Test that we can supply our own instance of DependencyTools. We do this
+    # by monkeypatching the can_loop_be_parallelised() method so that it adds
+    # a message.
+
+    def fake1(deptools, _2, test_all_variables=False,
+              signatures_to_ignore=None):
+        # pylint: disable=unused-argument
+        deptools._add_message("just a test", DTCode.WARN_SCALAR_WRITTEN_ONCE)
+        return True
+
+    monkeypatch.setattr(DependencyTools, "can_loop_be_parallelised", fake1)
+    dtools = DependencyTools()
+    assert goloop.independent_iterations(dep_tools=dtools)
+    assert dtools.get_all_messages()[0].code == DTCode.WARN_SCALAR_WRITTEN_ONCE
+
+    # Test when the DA raises an exception (typically because of missing
+    # variables in the PSyIR - TODO #845) that this is handled by the
+    # independent_iterations method.
+
+    def fake2(_1, _2, test_all_variables=False, signatures_to_ignore=None):
+        # pylint: disable=unused-argument
+        raise InternalError("This is just a test")
+    monkeypatch.setattr(DependencyTools, "can_loop_be_parallelised", fake2)
+    assert goloop.independent_iterations()
diff --git a/src/psyclone/tests/domain/lfric/lfric_loop_test.py b/src/psyclone/tests/domain/lfric/lfric_loop_test.py
index 2228e8ce3..d7e0592e2 100644
--- a/src/psyclone/tests/domain/lfric/lfric_loop_test.py
+++ b/src/psyclone/tests/domain/lfric/lfric_loop_test.py
@@ -1,7 +1,7 @@
 # -----------------------------------------------------------------------------
 # BSD 3-Clause License
 #
-# Copyright (c) 2021-2022, Science and Technology Facilities Council
+# Copyright (c) 2021-2023, Science and Technology Facilities Council
 # All rights reserved.
 #
 # Redistribution and use in source and binary forms, with or without
@@ -54,6 +54,9 @@ from psyclone.parse.algorithm import parse
 from psyclone.psyGen import PSyFactory
 from psyclone.psyir.nodes import (ArrayReference, Call, Literal, Reference,
                                   Schedule, ScopingNode)
+from psyclone.psyir.symbols import DataSymbol, INTEGER_TYPE
+from psyclone.psyir.tools import DependencyTools
+from psyclone.psyir.tools.dependency_tools import Message, DTCode
 from psyclone.tests.lfric_build import LFRicBuild
 from psyclone.tests.utilities import get_invoke
 from psyclone.transformations import (Dynamo0p3ColourTrans,
@@ -997,3 +1000,72 @@ end module testkern_mod
     assert ("A DynLoop of type 'null' can only contain a kernel that "
             "operates on the 'domain' but kernel 'testkern_code' operates "
             "on 'cell_column'" in str(err.value))
+
+
+def test_loop_independent_iterations(monkeypatch, dist_mem):
+    '''Tests for the independent_iterations method.'''
+    # A 'null' loop cannot be parallelised (because there's nothing to
+    # parallelise).
+    loop = DynLoop(loop_type="null")
+    assert not loop.independent_iterations()
+    # A loop over all columns that contains a kernel that increments a field
+    # on a continuous function space does not have independent iterations.
+    _, invoke_info = parse(os.path.join(BASE_PATH,
+                                        "1_single_invoke.f90"),
+                           api=TEST_API)
+    psy = PSyFactory(TEST_API, distributed_memory=dist_mem).create(invoke_info)
+    schedule = psy.invokes.invoke_list[0].schedule
+    loop = schedule.walk(DynLoop)[0]
+    assert not loop.independent_iterations()
+    # Colour the loop.
+    trans = Dynamo0p3ColourTrans()
+    trans.apply(loop)
+    loops = schedule.walk(DynLoop)
+    assert not loops[0].independent_iterations()
+    assert loops[1].independent_iterations()
+    # Loop over dofs.
+    _, invoke_info = parse(os.path.join(BASE_PATH,
+                                        "15.1.6_aX_plus_bY_builtin.f90"),
+                           api=TEST_API)
+    psy = PSyFactory(TEST_API, distributed_memory=dist_mem).create(invoke_info)
+    schedule = psy.invokes.invoke_list[0].schedule
+    loop = schedule.walk(DynLoop)[0]
+    assert loop.independent_iterations()
+    # Test that we can get hold of any DA messages if we supply our own
+    # instance of DependencyTools.
+    dtools = DependencyTools()
+    loop.independent_iterations(dep_tools=dtools)
+    assert len(dtools.get_all_messages()) == 1
+    # Unsupported/unknown loop type
+    monkeypatch.setattr(loop, "_loop_type", "broken")
+    with pytest.raises(InternalError) as err:
+        loop.independent_iterations()
+    assert "loop of type 'broken' is not supported" in str(err.value)
+    monkeypatch.undo()
+    # Test when the DA returns an unexpected message.
+    monkeypatch.setattr(DependencyTools, "get_all_messages",
+                        lambda _1: [Message("just a test",
+                                            DTCode.WARN_SCALAR_REDUCTION)])
+    assert not loop.independent_iterations()
+    # Test when the DA warns about a variable that is not a field or operator.
+    # Add a new symbol to the table so that we can refer to it.
+    schedule.symbol_table.add(DataSymbol("fake", INTEGER_TYPE))
+    monkeypatch.setattr(DependencyTools, "get_all_messages",
+                        lambda _1: [Message("just a test",
+                                            DTCode.WARN_SCALAR_WRITTEN_ONCE,
+                                            var_names=["fake"])])
+    assert not loop.independent_iterations()
+    # Test when the DA returns True. Since this currently never happens for an
+    # LFRic kernel we use monkeypatch.
+    monkeypatch.setattr(DependencyTools, "can_loop_be_parallelised",
+                        lambda _1, _2, test_all_variables=False,
+                        signatures_to_ignore=[]: True)
+    assert loop.independent_iterations()
+    # Test when the DA raises an exception. This is hard to reproduce (it
+    # depends on the precise names used for arguments to a kernel) so we
+    # simply use monkeypatch again to check that it is handled.
+
+    def fake(_1, _2, test_all_variables=False, signatures_to_ignore=None):
+        raise KeyError("This is just a test")
+    monkeypatch.setattr(DependencyTools, "can_loop_be_parallelised", fake)
+    assert loop.independent_iterations()
diff --git a/src/psyclone/tests/psyir/nodes/loop_test.py b/src/psyclone/tests/psyir/nodes/loop_test.py
index a70425012..2d87a2795 100644
--- a/src/psyclone/tests/psyir/nodes/loop_test.py
+++ b/src/psyclone/tests/psyir/nodes/loop_test.py
@@ -38,20 +38,43 @@
 
 ''' Performs py.test tests on the Loop PSyIR node. '''
 
-from __future__ import absolute_import
 import os
 import pytest
 from psyclone.errors import InternalError, GenerationError
 from psyclone.parse.algorithm import parse
 from psyclone.psyGen import PSyFactory
-from psyclone.psyir.nodes import Loop, Literal, Schedule, Return, Assignment, \
-    Reference
-from psyclone.psyir.symbols import DataSymbol, REAL_SINGLE_TYPE, \
-    INTEGER_SINGLE_TYPE, INTEGER_TYPE, ArrayType, REAL_TYPE, \
-    SymbolTable
+from psyclone.psyir.nodes import (
+    Assignment, Loop, Literal, Schedule, Return, Reference, Routine)
+from psyclone.psyir.symbols import (
+    DataSymbol, REAL_SINGLE_TYPE, INTEGER_SINGLE_TYPE, INTEGER_TYPE, ArrayType,
+    REAL_TYPE, SymbolTable)
+from psyclone.psyir.tools import DependencyTools
 from psyclone.tests.utilities import check_links
 
 
+def make_loop():
+    '''
+    Utility to create a simple PSyIR loop for testing. The loop is contained
+    within a Routine as it must have a parent scope for its Symbols.
+
+    :returns: a PSyIR Loop instance.
+    :rtype: :py:class:`psyclone.psyir.nodes.Loop`
+
+    '''
+    start = Literal("0", INTEGER_SINGLE_TYPE)
+    stop = Literal("1", INTEGER_SINGLE_TYPE)
+    step = Literal("1", INTEGER_SINGLE_TYPE)
+    sched = Routine("loop_test_sub")
+    tmp = sched.symbol_table.new_symbol("tmp", symbol_type=DataSymbol,
+                                        datatype=REAL_SINGLE_TYPE)
+    isym = sched.symbol_table.new_symbol("i", symbol_type=DataSymbol,
+                                         datatype=INTEGER_SINGLE_TYPE)
+    child_node = Assignment.create(Reference(tmp), Reference(isym))
+    loop = Loop.create(isym, start, stop, step, [child_node])
+    sched.addchild(loop)
+    return loop
+
+
 def test_loop_init():
     '''Test that a loop instance is created as expected and that it raises
     the expected exceptions where appropriate.
@@ -143,6 +166,55 @@ def test_loop_navigation_properties():
     assert loop.step_expr.value == "2"
 
 
+def test_loop_dag_name():
+    '''Test the dag_name method of Loop.'''
+    loop = make_loop()
+    assert loop.dag_name == "loop_1"
+    # Make the Loop an orphan to test the error handling.
+    loop.detach()
+    with pytest.raises(InternalError) as err:
+        _ = loop.dag_name
+    assert ("Cannot generate DAG name for loop node 'Loop[variable:'i']"
+            in str(err.value))
+
+
+def test_loop_node_str(monkeypatch):
+    '''Test the node_str method of Loop.'''
+    loop = make_loop()
+    assert loop.node_str(colour=False) == "Loop[variable='i']"
+
+    # Rather than mess about with colour codes, it's simpler if we
+    # monkeypatch the 'coloured_name' method (inherited from Node).
+    def fake_coloured_name(colour=True):
+        if colour:
+            return "yes"
+        return "no"
+    monkeypatch.setattr(loop, "coloured_name", fake_coloured_name)
+    assert loop.node_str(colour=True) == "yes[variable='i']"
+    assert loop.node_str(colour=False) == "no[variable='i']"
+
+
+def test_loop_str():
+    '''Test the __str__ property of Loop.'''
+    loop = make_loop()
+    out = str(loop)
+    assert "Loop[variable:'i']\n" in out
+    assert "End Loop" in out
+
+
+def test_loop_independent_iterations():
+    '''Test the independent_iterations method of Loop.'''
+    loop = make_loop()
+    assert not loop.independent_iterations()
+    # Test that we can supply our own instance of DependencyTools and use
+    # it to query any messages.
+    dtools = DependencyTools()
+    loop.independent_iterations(dep_tools=dtools)
+    msgs = dtools.get_all_messages()
+    assert len(msgs) == 1
+    assert "variable 'tmp' is only written once" in str(msgs[0])
+
+
 def test_loop_gen_code():
     ''' Check that the Loop gen_code method prints the proper loop '''
     base_path = os.path.join(os.path.dirname(os.path.dirname(os.path.dirname(
diff --git a/src/psyclone/tests/psyir/tools/dependency_tools_test.py b/src/psyclone/tests/psyir/tools/dependency_tools_test.py
index 4860522dd..514a13488 100644
--- a/src/psyclone/tests/psyir/tools/dependency_tools_test.py
+++ b/src/psyclone/tests/psyir/tools/dependency_tools_test.py
@@ -38,12 +38,9 @@
 
 import pytest
 
-from fparser.common.readfortran import FortranStringReader
-
 from psyclone.configuration import Config
 from psyclone.core import Signature, VariablesAccessInfo
 from psyclone.errors import InternalError
-from psyclone.psyGen import PSyFactory
 from psyclone.psyir.tools import DependencyTools, DTCode, ReadWriteInfo
 from psyclone.tests.utilities import get_invoke
 
@@ -60,11 +57,14 @@ def test_messages():
 
     dep_tools = DependencyTools()
     assert dep_tools.get_all_messages() == []
-    dep_tools._add_message("info-test", DTCode.INFO_NOT_NESTED_LOOP,
+
+    # There aren't currently any INFO messages so we invent one by simply
+    # adding one to the minimum INFO error code.
+    dep_tools._add_message("info-test", DTCode.INFO_MIN+1,
                            ["a", "b"])
     msg = dep_tools.get_all_messages()[0]
     assert str(msg) == "Info: info-test"
-    assert msg.code == DTCode.INFO_NOT_NESTED_LOOP
+    assert msg.code == DTCode.INFO_MIN + 1
     assert msg.var_names == ["a", "b"]
 
     dep_tools._add_message("warning-test", DTCode.WARN_SCALAR_REDUCTION,
@@ -123,69 +123,6 @@ def test_loop_parallelise_errors():
     assert "node must be an instance of class Loop but got" in str(err.value)
 
 
-# -----------------------------------------------------------------------------
-def test_nested_loop_detection(parser):
-    '''Tests if nested loop are handled correctly.
-    '''
-    reader = FortranStringReader('''program test
-                                 integer :: ji, jk
-                                 integer, parameter :: jpi=10, jpk=10
-                                 real, dimension(jpi,jpi,jpk) :: umask, xmask
-                                 do jk = 1, jpk   ! loop 0
-                                   umask(1,1,jk) = -1.0d0
-                                 end do
-                                 do ji = 1, jpi   ! loop 1
-                                   xmask(ji,1,1) = -1.0d0
-                                 end do
-                                 end program test''')
-    prog = parser(reader)
-    psy = PSyFactory("nemo", distributed_memory=False).create(prog)
-    loops = psy.invokes.get("test").schedule
-    dep_tools = DependencyTools(["levels", "lat"])
-
-    # Not a nested loop
-    parallel = dep_tools.can_loop_be_parallelised(loops[0])
-    assert parallel is False
-    msg = dep_tools.get_all_messages()[0]
-    assert "Not a nested loop" in str(msg)
-    assert msg.code == DTCode.INFO_NOT_NESTED_LOOP
-    assert msg.var_names == []
-
-    # Now disable the test for nested loops:
-    parallel = dep_tools.can_loop_be_parallelised(loops[0],
-                                                  only_nested_loops=False)
-    assert parallel is True
-    # Make sure can_loop_be_parallelised clears old messages automatically
-    assert dep_tools.get_all_messages() == []
-
-
-# -----------------------------------------------------------------------------
-def test_loop_type(parser):
-    '''Tests general functionality of can_loop_be_parallelised.
-    '''
-    reader = FortranStringReader('''program test
-                                 integer ji
-                                 integer, parameter :: jpi=10
-                                 real, dimension(jpi,1,1) :: xmask
-                                 do ji = 1, jpi
-                                   xmask(ji,1,1) = -1.0d0
-                                 end do
-                                 end program test''')
-    prog = parser(reader)
-    psy = PSyFactory("nemo", distributed_memory=False).create(prog)
-    loop = psy.invokes.get("test").schedule[0]
-    dep_tools = DependencyTools(["levels", "lat"])
-
-    # Check a loop that has the wrong loop type
-    parallel = dep_tools.can_loop_be_parallelised(loop,
-                                                  only_nested_loops=False)
-    assert parallel is False
-    msg = dep_tools.get_all_messages()[0]
-    assert "wrong loop type 'lon'" in str(msg)
-    assert msg.code == DTCode.INFO_WRONG_LOOP_TYPE
-    assert msg.var_names == []
-
-
 # -----------------------------------------------------------------------------
 def test_arrays_parallelise(fortran_reader):
     '''Tests the array checks of can_loop_be_parallelised.
diff --git a/src/psyclone/tests/psyir/transformations/parallel_loop_trans_test.py b/src/psyclone/tests/psyir/transformations/parallel_loop_trans_test.py
index 8e9e725c5..a51e113ce 100644
--- a/src/psyclone/tests/psyir/transformations/parallel_loop_trans_test.py
+++ b/src/psyclone/tests/psyir/transformations/parallel_loop_trans_test.py
@@ -158,8 +158,7 @@ end subroutine my_sub'''
     trans = ParaTrans()
     # Check that the dependency tools will raise the expected warning.
     dep_tools = DependencyTools()
-    dep_tools.can_loop_be_parallelised(loop,
-                                       only_nested_loops=False)
+    dep_tools.can_loop_be_parallelised(loop)
     for message in dep_tools.get_all_messages():
         if message.code == DTCode.WARN_SCALAR_WRITTEN_ONCE:
             break
@@ -169,29 +168,6 @@ end subroutine my_sub'''
     trans.validate(loop)
 
 
-def test_paralooptrans_validate_ignore_key_error(fortran_reader, monkeypatch):
-    '''
-    Test that a KeyError in the dependence analysis is ignored.
-    (This is required because LFRic still has symbols that don't exist in the
-    symbol_table until the gen_code() step, so the dependency analysis raises
-    KeyErrors in some cases.
-
-    '''
-    psyir = fortran_reader.psyir_from_source(CODE)
-    loop = psyir.walk(Loop)[0]
-    trans = ParaTrans()
-
-    # Create a fake routine that just raises a KeyError.
-    def fake(_1, _2, only_nested_loops=False):
-        raise KeyError()
-
-    # Replace the `can_loop_be_parallelised` method of DependencyTools with
-    # our fake routine.
-    monkeypatch.setattr(DependencyTools, "can_loop_be_parallelised", fake)
-    # `validate` should still complete successfully.
-    trans.validate(loop)
-
-
 def test_paralooptrans_apply_calls_validate(fortran_reader, monkeypatch):
     '''
     Check that the apply() method calls the validate() method.
diff --git a/src/psyclone/tests/psyir/transformations/transformations_test.py b/src/psyclone/tests/psyir/transformations/transformations_test.py
index b2a43b3da..b1d85d2c6 100644
--- a/src/psyclone/tests/psyir/transformations/transformations_test.py
+++ b/src/psyclone/tests/psyir/transformations/transformations_test.py
@@ -407,10 +407,6 @@ def test_parallellooptrans_validate_dependencies(fortran_reader):
     # just with 'jk' and it is not modified in the inner loops
     omplooptrans.validate(loops[1])
 
-    # Check if there is missing symbol information it still validates
-    del loops[1].ancestor(Routine).symbol_table._symbols['zws']
-    omplooptrans.validate(loops[1])
-
     # Reductions also indicate a data dependency that needs to be handled, so
     # we don't permit the parallelisation of the loop (until we support
     # reduction clauses)
@@ -438,8 +434,7 @@ def test_parallellooptrans_validate_dependencies(fortran_reader):
             enddo
           enddo
         enddo''')
-    assert not DependencyTools().can_loop_be_parallelised(
-                    loops[0], only_nested_loops=False)
+    assert not DependencyTools().can_loop_be_parallelised(loops[0])
     omplooptrans.validate(loops[0])