Repository: stfc/PSyclone (python)

Issue:
get_private_clauses of OMPParallelDirective incorrectly flagging non-array accesses as firstprivate
I have the following test in the task branch which now fails (and before the `firstprivate` changes did not). I've slightly adjusted it as previously it was easy to argue "k wasn't set", but now k is an input parameter and PSyclone doesn't change its behaviour.

```
    code = '''
    subroutine my_subroutine(k)
        integer :: i, ii
        integer :: j, jj
        integer :: k
        do i = 1, 320, 32
            do j = 1, 320, 32
                do ii=i, i+32
                    do jj = j,j+32
                        k = k + ii
                        k = k * jj
                    end do
                end do
            end do
        end do
    end subroutine
    '''
    tree = fortran_reader.psyir_from_source(code)
    ptrans = OMPParallelTrans()
    strans = OMPSingleTrans()
    tdir = DynamicOMPTaskDirective()
    loops = tree.walk(Loop)
    loop = loops[1].children[3].children[0]
    parent = loop.parent
    loop.detach()
    tdir.children[0].addchild(loop)
    parent.addchild(tdir, index=0)
    strans.apply(loops[0])
    ptrans.apply(loops[0].parent.parent)
    correct = '''subroutine my_subroutine(k)
  integer :: k
  integer :: i
  integer :: ii
  integer :: j
  integer :: jj


  !$omp parallel default(shared), private(i,ii,j,jj)
  !$omp single
  do i = 1, 320, 32
    do j = 1, 320, 32
      !$omp task private(ii,jj), firstprivate(i,j), shared(k), \
depend(in: k), depend(out: k)
      do ii = i, i + 32, 1
        do jj = j, j + 32, 1
          k = k + ii
          k = k * jj
        enddo
      enddo
      !$omp end task
    enddo
  enddo
  !$omp end single
  !$omp end parallel

end subroutine my_subroutine\n'''
    assert fortran_writer(tree) == correct
```

For some reason, the access `k = k + ii` is being flagged as a `firstprivate` access - I think because its a non-array access, however since its an assignment to `k`, it should be `shared` - if this was in an `OMPDoDirective` then we'd obviously have a race condition (which is not allowed), however the data concurrency issue is handle by the dependency on the task.

The output from `fortran_writer(tree)` is instead:
```
subroutine my_subroutine(k)
  integer :: k
  integer :: i
  integer :: ii
  integer :: j
  integer :: jj

  !$omp parallel default(shared), private(i,ii,j,jj), firstprivate(k)
  !$omp single
  do i = 1, 320, 32
    do j = 1, 320, 32
      !$omp task private(ii,jj), firstprivate(i,j), shared(k), depend(in: k), depend(out: k)
      do ii = i, i + 32, 1
        do jj = j, j + 32, 1
          k = k + ii
          k = k * jj
        enddo
      enddo
      !$omp end task
    enddo
  enddo
  !$omp end single
  !$omp end parallel

end subroutine my_subroutine
```

I think this affects a lot of my tests, and are instances with PSyclone generating incorrect code.

@sergisiso @nmnobre What were the rules decided for determining if a variable in PSyclone is `firstprivate` as opposed to `shared`? Maybe this needs to be smarter - perhaps variable accesses inside OMPSerialRegions need difference rules?

Pull request description:
(closes #2101) Refactor OpenMP inference of private symbols and report symbols needing sync

Patch:
diff --git a/.gitignore b/.gitignore
index f401dd74e..64ddd5929 100644
--- a/.gitignore
+++ b/.gitignore
@@ -22,3 +22,5 @@ src/*.egg-info
 *.sublime-project
 *.sublime-workspace
 .idea
+.rtx.toml
+.venv
diff --git a/changelog b/changelog
index 7b700c92c..c22bd5875 100644
--- a/changelog
+++ b/changelog
@@ -485,6 +485,9 @@
 	164) PR #2208 towards #2205. Ensures that functions or subroutines
 	that CONTAIN other functions/subroutines are put into a CodeBlock.
 
+	165) PR #2124 fir #2101. Refactors OpenMP inference of private/first-
+	private variables and those requiring synchronisation.
+
 release 2.3.1 17th of June 2022
 
 	1) PR #1747 for #1720. Adds support for If blocks to PSyAD.
diff --git a/src/psyclone/psyir/nodes/omp_directives.py b/src/psyclone/psyir/nodes/omp_directives.py
index 0ed2ff1bb..377c36a9f 100644
--- a/src/psyclone/psyir/nodes/omp_directives.py
+++ b/src/psyclone/psyir/nodes/omp_directives.py
@@ -494,7 +494,16 @@ class OMPParallelDirective(OMPRegionDirective):
 
     def gen_code(self, parent):
         '''Generate the fortran OMP Parallel Directive and any associated
-        code'''
+        code.
+
+        :param parent: the node in the generated AST to which to add content.
+        :type parent: :py:class:`psyclone.f2pygen.BaseGen`
+
+        :raises GenerationError: if the OpenMP directive needs some
+            synchronisation mechanism to create valid code. These are not
+            implemented yet.
+
+        '''
         # pylint: disable=import-outside-toplevel
         from psyclone.psyGen import zero_reduction_variables
 
@@ -507,8 +516,17 @@ class OMPParallelDirective(OMPRegionDirective):
         # this almost certainly indicates a user error.
         self._encloses_omp_directive()
 
-        # Update/generate the private clause if the code has changed.
-        private_clause, fprivate_clause = self._get_private_clauses()
+        # Generate the private and firstprivate clauses
+        private, fprivate, need_sync = self._infer_sharing_attributes()
+        private_clause = OMPPrivateClause.create(
+                            sorted(private, key=lambda x: x.name))
+        fprivate_clause = OMPFirstprivateClause.create(
+                            sorted(fprivate, key=lambda x: x.name))
+        if need_sync:
+            raise GenerationError(
+                f"OMPParallelDirective.gen_code() does not support symbols "
+                f"that need synchronisation, but found: "
+                f"{[x.name for x in need_sync]}")
 
         reprod_red_call_list = self.reductions(reprod=True)
         if reprod_red_call_list:
@@ -591,6 +609,9 @@ class OMPParallelDirective(OMPRegionDirective):
         :returns: the lowered version of this node.
         :rtype: :py:class:`psyclone.psyir.node.Node`
 
+        :raises GenerationError: if the OpenMP directive needs some
+            synchronisation mechanism to create valid code. These are not
+            implemented yet.
         '''
         # Keep the first two children and compute the rest using the current
         # state of the node/tree (lowering it first in case new symbols are
@@ -598,7 +619,20 @@ class OMPParallelDirective(OMPRegionDirective):
         self._children = self._children[:2]
         for child in self.children:
             child.lower_to_language_level()
-        private_clause, fprivate_clause = self._get_private_clauses()
+
+        # Create data sharing clauses (order alphabetically to make generation
+        # reproducible)
+        private, fprivate, need_sync = self._infer_sharing_attributes()
+        private_clause = OMPPrivateClause.create(
+                            sorted(private, key=lambda x: x.name))
+        fprivate_clause = OMPFirstprivateClause.create(
+                            sorted(fprivate, key=lambda x: x.name))
+        if need_sync:
+            raise GenerationError(
+                f"Lowering {type(self).__name__} does not support symbols that"
+                f" need synchronisation, but found: "
+                f"{[x.name for x in need_sync]}")
+
         self.addchild(private_clause)
         self.addchild(fprivate_clause)
         return self
@@ -630,21 +664,40 @@ class OMPParallelDirective(OMPRegionDirective):
         '''
         return "omp end parallel"
 
-    def _get_private_clauses(self):
-        '''
-        Returns the OpenMP clauses with the symbols of the variable names that
-        should be marked as PRIVATE and FIRSTPRIVATE in this parallel region.
-
-        :returns: a PRIVATE and a FIRSTPRIVATE clause containing the \
-                  variables that need to be marked private for this directive.
-        :rtype: Tuple[ \
-            :py:class:`psyclone.psyir.nodes.omp_clauses.OMPPrivateClause`,
-            :py:class:`psyclone.psyir.nodes.omp_clauses.OMPFirstprivateClause`]
+    def _infer_sharing_attributes(self):
+        '''
+        The PSyIR does not specify if each symbol inside an OpenMP region is
+        private, firstprivate, shared or shared but needs synchronisation,
+        the attributes are infered looking at the usage of each symbol inside
+        the parallel region.
+
+        This method analyses the directive body and automatically classifies
+        each symbol using the following rules:
+        - All arrays are shared.
+        - Scalars that are accessed only once are shared.
+        - Scalars that are read-only or written outside a loop are shared.
+        - Scalars written in multiple iterations of a loop are private, unless:
+          * there is a write-after-read dependency in a loop iteration,
+          in this case they are shared but need synchronisation;
+          * they are read before in the same parallel region (but not inside
+          the same loop iteration), in this case they are firstprivate.
+          * they are only conditionally written in some iterations;
+          in this case they are firstprivate.
+
+        This method returns the sets of private, firstprivate, and shared but
+        needing synchronisation symbols, all symbols not in these sets are
+        assumed shared. How to synchronise the symbols in the third set is
+        up to the caller of this method.
+
+        :returns: three set of symbols that classify each of the symbols in \
+            the directive body as PRIVATE, FIRSTPRIVATE or SHARED NEEDING \
+            SYNCHRONISATION.
+        :rtype: Tuple[Set(:py:class:`psyclone.psyir.symbols.symbol), \
+                      Set(:py:class:`psyclone.psyir.symbols.symbol), \
+                      Set(:py:class:`psyclone.psyir.symbols.symbol)]
 
         :raises GenerationError: if the DefaultClauseType associated with \
                                  this OMPParallelDirective is not shared.
-        :raises InternalError: if a Kernel has local variable(s) but they \
-                               aren't named.
 
         '''
         if (self.default_clause.clause_type !=
@@ -652,12 +705,26 @@ class OMPParallelDirective(OMPRegionDirective):
             raise GenerationError("OMPParallelClause cannot correctly generate"
                                   " the private clause when its default "
                                   "data sharing attribute in its default "
-                                  "clause is not shared.")
+                                  "clause is not 'shared'.")
+
+        # TODO #598: Improve the handling of scalar variables, there are
+        # remaining issues when we have accesses after the parallel region
+        # of variables that we currently declare as private. This should be
+        # lastprivate.
+        # e.g:
+        # !$omp parallel do <- will set private(ji, my_index)
+        # do ji = 1, jpk
+        #   my_index = ji+1
+        #   array(my_index) = 2
+        # enddo
+        # #end do
+        # call func(my_index) <- my_index has not been updated
 
         private = set()
         fprivate = set()
+        need_sync = set()
 
-        # Now determine scalar variables that must be private:
+        # Determine variables that must be private, firstprivate or need_sync
         var_accesses = VariablesAccessInfo()
         self.reference_accesses(var_accesses)
         for signature in var_accesses.all_signatures:
@@ -671,71 +738,81 @@ class OMPParallelDirective(OMPRegionDirective):
             if len(accesses) == 1:
                 continue
 
-            # We have at least two accesses. We consider private variables the
-            # ones that are written in every iteration of a loop. If one such
-            # scalar is read before it is written, it will be considered
-            # firstprivate.
+            # TODO #598: If we only have writes, it must be need_sync:
+            # do ji = 1, jpk
+            #   if ji=3:
+            #      found = .true.
+            # Or lastprivate in order to maintain the serial semantics
+            # do ji = 1, jpk
+            #   found = ji
+
+            # We consider private variables as being the ones that are written
+            # in every iteration of a loop.
+            # If one such scalar is potentially read before it is written, it
+            # will be considered firstprivate.
             has_been_read = False
+            last_read_position = 0
             for access in accesses:
                 if access.access_type == AccessType.READ:
                     has_been_read = True
+                    last_read_position = access.node.abs_position
 
                 if access.access_type == AccessType.WRITE:
-                    # Check if the write access is inside a loop. If the write
-                    # is outside of a loop, it is an assignment to a shared
-                    # variable. Example where jpk is likely used outside of the
-                    # parallel section later, so it must be declared as shared
-                    # in order keep its value:
+
+                    # Check if the write access is outside a loop. In this case
+                    # it will be marked as shared. This is done because it is
+                    # likely to be re-used later. e.g:
                     # !$omp parallel
                     # jpk = 100
                     # !omp do
                     # do ji = 1, jpk
-
-                    # TODO #598: Improve the handling of scalar variables,
-                    # there are remaining issues with references after the
-                    # parallel region of variables that we currently declare
-                    # as private.
-
-                    # Check if it is inside a loop
                     loop_ancestor = access.node.ancestor(
                         (Loop, WhileLoop),
                         limit=self,
                         include_self=True)
-
-                    if loop_ancestor:
-                        # The assignment to the variable is inside a loop, so
-                        # declare it to be private
-                        name = str(signature).lower()
-                        symbol = access.node.scope.symbol_table.lookup(name)
-
-                        # Is the write conditional?
-                        conditional_write = access.node.ancestor(
-                            IfBlock,
-                            limit=loop_ancestor,
-                            include_self=True)
-
-                        # If a previous value might be needed we mark it as
-                        # firstprivate
-                        if has_been_read or conditional_write:
+                    if not loop_ancestor:
+                        # If we find it at least once outside a loop we keep it
+                        # as shared
+                        break
+
+                    # Otherwise, the assignment to this variable is inside a
+                    # loop (and it will be repeated for each iteration), so
+                    # we declare it as private or need_synch
+                    name = signature.var_name
+                    # TODO #2094: var_name only captures the top-level
+                    # component in the derived type accessor. If the attributes
+                    # only apply to a sub-component, this won't be captured
+                    # appropriately.
+                    symbol = access.node.scope.symbol_table.lookup(name)
+
+                    # If it has been read before we have to check if ...
+                    if has_been_read:
+                        loop_pos = loop_ancestor.loop_body.abs_position
+                        if last_read_position < loop_pos:
+                            # .. it was before the loop, so it is fprivate
                             fprivate.add(symbol)
                         else:
-                            private.add(symbol)
+                            # or inside the loop, in which case it needs sync
+                            need_sync.add(symbol)
+                        break
+
+                    # If the write is not guaranteed, we make it firstprivate
+                    # so that in the case that the write doesn't happen we keep
+                    # the original value
+                    conditional_write = access.node.ancestor(
+                        IfBlock,
+                        limit=loop_ancestor,
+                        include_self=True)
+                    if conditional_write:
+                        fprivate.add(symbol)
+                        break
 
                     # Already found the first write and decided if it is
                     # shared, private or firstprivate. We can stop looking.
+                    private.add(symbol)
                     break
 
-        # Convert the sets into a list and sort them, so that we get
-        # reproducible results
-        list_private = list(private)
-        list_private.sort(key=lambda x: x.name)
-        list_fprivate = list(fprivate)
-        list_fprivate.sort(key=lambda x: x.name)
-
-        # Create the OMPPrivateClause and OMPFirstpirvateClause
-        priv_clause = OMPPrivateClause.create(list_private)
-        fpriv_clause = OMPFirstprivateClause.create(list_fprivate)
-        return priv_clause, fpriv_clause
+        return private, fprivate, need_sync
 
     def validate_global_constraints(self):
         '''
@@ -1313,15 +1390,25 @@ class OMPParallelDoDirective(OMPParallelDirective, OMPDoDirective):
         # pylint: disable=protected-access
         default_str = self.children[1]._clause_string
         # pylint: enable=protected-access
-        private, fprivate = self._get_private_clauses()
+        private, fprivate, need_sync = self._infer_sharing_attributes()
+        private_clause = OMPPrivateClause.create(
+                            sorted(private, key=lambda x: x.name))
+        fprivate_clause = OMPFirstprivateClause.create(
+                            sorted(fprivate, key=lambda x: x.name))
+        if need_sync:
+            raise GenerationError(
+                f"OMPParallelDoDirective.gen_code() does not support symbols "
+                f"that need synchronisation, but found: "
+                f"{[x.name for x in need_sync]}")
 
-        private_list = [child.symbol.name for child in private.children]
-        private_str = "private(" + ",".join(private_list) + ")"
-        fp_list = [child.symbol.name for child in fprivate.children]
+        private_str = ""
+        fprivate_str = ""
+        private_list = [child.symbol.name for child in private_clause.children]
+        if private_list:
+            private_str = "private(" + ",".join(private_list) + ")"
+        fp_list = [child.symbol.name for child in fprivate_clause.children]
         if fp_list:
             fprivate_str = "firstprivate(" + ",".join(fp_list) + ")"
-        else:
-            fprivate_str = ""
 
         # Set schedule clause
         if self._omp_schedule != "none":


Test patch:
diff --git a/src/psyclone/tests/psyir/nodes/omp_directives_test.py b/src/psyclone/tests/psyir/nodes/omp_directives_test.py
index 494a01645..3d0a5ab93 100644
--- a/src/psyclone/tests/psyir/nodes/omp_directives_test.py
+++ b/src/psyclone/tests/psyir/nodes/omp_directives_test.py
@@ -59,7 +59,7 @@ from psyclone.psyir.symbols import DataSymbol, INTEGER_TYPE, SymbolTable, \
 from psyclone.errors import InternalError, GenerationError
 from psyclone.transformations import Dynamo0p3OMPLoopTrans, OMPParallelTrans, \
     OMPParallelLoopTrans, DynamoOMPParallelLoopTrans, OMPSingleTrans, \
-    OMPMasterTrans, OMPTaskloopTrans
+    OMPMasterTrans, OMPTaskloopTrans, OMPLoopTrans
 from psyclone.tests.utilities import get_invoke
 
 BASE_PATH = os.path.join(os.path.dirname(os.path.dirname(os.path.dirname(
@@ -69,9 +69,10 @@ GOCEAN_BASE_PATH = os.path.join(os.path.dirname(os.path.abspath(__file__)),
                                 "gocean1p0")
 
 
-def test_ompparallel_changes_begin_string(fortran_reader):
-    ''' Check that when the code inside an OMP Parallel region changes, the
-    parallel clause changes appropriately. '''
+def test_ompparallel_lowering(fortran_reader, monkeypatch):
+    ''' Check that lowering an OMP Parallel region leaves it with the
+    appropriate begin_string and clauses for the backend to generate
+    the right code'''
     code = '''
     subroutine my_subroutine()
         integer, dimension(320) :: A
@@ -101,7 +102,10 @@ def test_ompparallel_changes_begin_string(fortran_reader):
     assert isinstance(pdir.children[3], OMPFirstprivateClause)
     priv_clause = pdir.children[2]
 
-    # Make acopy of the loop
+    # If the code inside the region changes after lowering, the next lowering
+    # will update the clauses appropriately
+    # TODO 2157: Alternatively, we could invalidate the clauses with an
+    # upwards signal when changed, or not store them at all.
     new_loop = pdir.children[0].children[0].children[0].children[0].copy()
     # Change the loop variable to j
     jvar = DataSymbol("j", INTEGER_SINGLE_TYPE)
@@ -112,10 +116,32 @@ def test_ompparallel_changes_begin_string(fortran_reader):
     pdir.lower_to_language_level()
     assert pdir.children[2] is not priv_clause
 
+    # Monkeypatch a case with private and firstprivate clauses
+    monkeypatch.setattr(pdir, "_infer_sharing_attributes",
+                        lambda: ({Symbol("a")}, {Symbol("b")}, None))
+
+    pdir.lower_to_language_level()
+    assert isinstance(pdir.children[2], OMPPrivateClause)
+    assert len(pdir.children[2].children) == 1
+    assert pdir.children[2].children[0].name == 'a'
+    assert isinstance(pdir.children[3], OMPFirstprivateClause)
+    assert len(pdir.children[3].children) == 1
+    assert pdir.children[3].children[0].name == 'b'
+
+    # Monkeypatch a case with shared variables that need synchronisation
+    monkeypatch.setattr(pdir, "_infer_sharing_attributes",
+                        lambda: ({}, {}, {Symbol("a")}))
+    with pytest.raises(GenerationError) as err:
+        pdir.lower_to_language_level()
+    assert ("Lowering OMPParallelDirective does not support symbols that "
+            "need synchronisation, but found: ['a']" in str(err.value))
 
-def test_ompparallel_changes_gen_code(monkeypatch):
-    ''' Check that when the code inside an OMP Parallel region changes, the
-    private clause changes appropriately. '''
+
+def test_ompparallel_gen_code_clauses(monkeypatch):
+    ''' Check that the OMP Parallel region clauses are generated
+    appropriately. '''
+
+    # Check with an LFRic kernel, the cell variable must be private
     _, invoke_info = parse(os.path.join(BASE_PATH, "1_single_invoke_w3.f90"),
                            api="dynamo0.3")
     psy = PSyFactory("dynamo0.3", distributed_memory=False).create(invoke_info)
@@ -136,7 +162,8 @@ def test_ompparallel_changes_gen_code(monkeypatch):
     assert len(pdir.children) == 4
     assert "private(cell)" in code
 
-    # Make acopy of the loop
+    # Check that making a change (add private k variable) after the first
+    # time psy.gen is called recomputes the clauses attributes
     new_loop = pdir.children[0].children[0].children[0].children[0].copy()
     routine = pdir.ancestor(Routine)
     routine.symbol_table.add(DataSymbol("k", INTEGER_SINGLE_TYPE))
@@ -152,20 +179,27 @@ def test_ompparallel_changes_gen_code(monkeypatch):
     assert "private(cell,k)" in code
 
     # Monkeypatch a case with private and firstprivate clauses
-    pclause = OMPPrivateClause(children=[Reference(Symbol("a"))])
-    fpclause = OMPFirstprivateClause(children=[Reference(Symbol("b"))])
-    monkeypatch.setattr(pdir, "_get_private_clauses",
-                        lambda: (pclause, fpclause))
+    monkeypatch.setattr(pdir, "_infer_sharing_attributes",
+                        lambda: ({Symbol("a")}, {Symbol("b")}, None))
 
     code = str(psy.gen).lower()
     assert "private(a)" in code
     assert "firstprivate(b)" in code
 
+    # Monkeypatch a case with shared variables that need synchronisation
+    monkeypatch.setattr(pdir, "_infer_sharing_attributes",
+                        lambda: ({}, {}, {Symbol("a")}))
+    with pytest.raises(GenerationError) as err:
+        code = str(psy.gen).lower()
+    assert ("OMPParallelDirective.gen_code() does not support symbols that "
+            "need synchronisation, but found: ['a']" in str(err.value))
+
 
-def test_omp_paralleldo_changes_gen_code(monkeypatch):
-    ''' Check that when the code inside an OMP Parallel Do region changes, the
-    private clause changes appropriately. Also check that changing the schedule
-    is correctly picked up.'''
+def test_omp_paralleldo_clauses_gen_code(monkeypatch):
+    ''' Check that the OMP ParallelDo clauses are generated
+    appropriately. '''
+
+    # Check with an LFRic kernel, the cell variable must be private
     _, invoke_info = parse(os.path.join(BASE_PATH, "1_single_invoke_w3.f90"),
                            api="dynamo0.3")
     psy = PSyFactory("dynamo0.3", distributed_memory=False).create(invoke_info)
@@ -182,7 +216,8 @@ def test_omp_paralleldo_changes_gen_code(monkeypatch):
     assert "schedule(auto)" in code
     assert "firstprivate" not in code
 
-    # Modify the loop
+    # Check that making a change (add private k variable) after the first
+    # time psy.gen is called recomputes the clauses attributes
     routine = pdir.ancestor(Routine)
     routine.symbol_table.add(DataSymbol("k", INTEGER_SINGLE_TYPE))
     # Change the loop variable to k
@@ -198,19 +233,26 @@ def test_omp_paralleldo_changes_gen_code(monkeypatch):
     assert "firstprivate" not in code
 
     # Monkeypatch a case with firstprivate clauses
-    pclause = OMPPrivateClause(children=[Reference(Symbol("a"))])
-    fpclause = OMPFirstprivateClause(children=[Reference(Symbol("b"))])
-    monkeypatch.setattr(pdir, "_get_private_clauses",
-                        lambda: (pclause, fpclause))
+    monkeypatch.setattr(pdir, "_infer_sharing_attributes",
+                        lambda: ({Symbol("a")}, {Symbol("b")}, None))
 
     code = str(psy.gen).lower()
     assert "private(a)" in code
     assert "firstprivate(b)" in code
 
+    # Monkeypatch a case with shared variables that need synchronisation
+    monkeypatch.setattr(pdir, "_infer_sharing_attributes",
+                        lambda: ({}, {}, {Symbol("a")}))
+    with pytest.raises(GenerationError) as err:
+        code = str(psy.gen).lower()
+    assert ("OMPParallelDoDirective.gen_code() does not support symbols that "
+            "need synchronisation, but found: ['a']" in str(err.value))
+
 
-def test_omp_parallel_do_changes_begin_str(fortran_reader):
-    ''' Check that when the code inside an OMP Parallel Do region changes, the
-    private clause changes appropriately. '''
+def test_omp_parallel_do_lowering(fortran_reader, monkeypatch):
+    ''' Check that lowering an OMP Parallel Do leaves it with the
+    appropriate begin_string and clauses for the backend to generate
+    the right code'''
     code = '''
     subroutine my_subroutine()
         integer, dimension(321, 10) :: A
@@ -240,7 +282,8 @@ def test_omp_parallel_do_changes_begin_str(fortran_reader):
     fpriv_clause = pdir.children[3]
     sched_clause = pdir.children[4]
 
-    # Make acopy of the loop
+    # If the code inside the region changes after lowering, the next lowering
+    # will update the clauses appropriately
     routine = pdir.ancestor(Routine)
     routine.symbol_table.add(DataSymbol("k", INTEGER_SINGLE_TYPE))
     # Change the loop variable to j
@@ -258,6 +301,26 @@ def test_omp_parallel_do_changes_begin_str(fortran_reader):
     assert pdir.children[4] is not sched_clause
     assert isinstance(pdir.children[4], OMPScheduleClause)
 
+    # Monkeypatch a case with private and firstprivate clauses
+    monkeypatch.setattr(pdir, "_infer_sharing_attributes",
+                        lambda: ({Symbol("a")}, {Symbol("b")}, None))
+
+    pdir.lower_to_language_level()
+    assert isinstance(pdir.children[2], OMPPrivateClause)
+    assert len(pdir.children[2].children) == 1
+    assert pdir.children[2].children[0].name == 'a'
+    assert isinstance(pdir.children[3], OMPFirstprivateClause)
+    assert len(pdir.children[3].children) == 1
+    assert pdir.children[3].children[0].name == 'b'
+
+    # Monkeypatch a case with shared variables that need synchronisation
+    monkeypatch.setattr(pdir, "_infer_sharing_attributes",
+                        lambda: ({}, {}, {Symbol("a")}))
+    with pytest.raises(GenerationError) as err:
+        pdir.lower_to_language_level()
+    assert ("Lowering OMPParallelDoDirective does not support symbols that "
+            "need synchronisation, but found: ['a']" in str(err.value))
+
 
 def test_omp_teams_distribute_parallel_do_strings(
         fortran_reader, fortran_writer):
@@ -531,8 +594,10 @@ def test_omp_do_children_err():
             "this Node has a child of type 'Return'" in str(err.value))
 
 
-def test_directive_get_private_lfric():
-    ''' Tests for the _get_private_clauses() method of OMPParallelDirective.
+def test_directive_infer_sharing_attributes_lfric():
+    ''' Tests for the _infer_sharing_attributes() method of
+    OMPParallelDirective containing an LFRic kernel.
+
     Note: this test does not apply colouring so the loops must be over
     discontinuous function spaces.
 
@@ -558,27 +623,57 @@ def test_directive_get_private_lfric():
     # replaced by a `lower_to_language_level` call.
     # pylint: disable=pointless-statement
     psy.gen
-    # Now check that _get_private_clause returns what we expect
-    pvars, fpvars = directive._get_private_clauses()
-    assert isinstance(pvars, OMPPrivateClause)
-    assert isinstance(fpvars, OMPFirstprivateClause)
-    assert len(pvars.children) == 1
-    assert len(fpvars.children) == 0
-    assert pvars.children[0].name == 'cell'
+    # Now check that _infer_sharing_attributes returns what we expect
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert isinstance(pvars, set)
+    assert isinstance(fpvars, set)
+    assert len(pvars) == 1
+    assert len(fpvars) == 0
+    assert len(sync) == 0
+    assert list(pvars)[0].name == 'cell'
 
     directive.children[1] = OMPDefaultClause(
             clause_type=OMPDefaultClause.DefaultClauseTypes.NONE)
     with pytest.raises(GenerationError) as excinfo:
-        _ = directive._get_private_clauses()
+        _ = directive._infer_sharing_attributes()
     assert ("OMPParallelClause cannot correctly generate the private clause "
             "when its default data sharing attribute in its default clause is "
-            "not shared." in str(excinfo.value))
+            "not 'shared'." in str(excinfo.value))
 
 
-def test_directive_get_private(fortran_reader):
-    ''' Tests for the _get_private_clauses() method of OpenMP directives.'''
+def test_directive_infer_sharing_attributes(fortran_reader):
+    ''' Tests for the _infer_sharing_attributes() method of OpenMP directives
+    with generic code inside the directive body.
+    '''
+
+    # Example with arrays, read-only and only-writen-once variables, this are
+    # all shared (only the iteration index is private in this parallel region)
+    psyir = fortran_reader.psyir_from_source('''
+        subroutine my_subroutine()
+            integer :: i, scalar1, scalar2
+            real, dimension(10) :: array
+            scalar2 = scalar1
+            do i = 1, 10
+               array(i) = scalar2
+            enddo
+        end subroutine''')
+    omplooptrans = OMPLoopTrans()
+    loop = psyir.walk(Loop)[0]
+    omplooptrans.apply(loop)
+    omptrans = OMPParallelTrans()
+    routine = psyir.walk(Routine)[0]
+    omptrans.apply(routine.children)
+    directive = psyir.walk(OMPParallelDirective)[0]
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 1
+    assert list(pvars)[0].name == 'i'
+    assert len(fpvars) == 0
+    assert len(sync) == 0
 
     # Example with private and firstprivate variables on OMPParallelDoDirective
+    # In this case scalar1 is firstprivate because it has a conditional-write
+    # that it is not guaranteed to happen on each iteration, so the private
+    # variable needs to be initialised with the value it has before the loop.
     psyir = fortran_reader.psyir_from_source('''
         subroutine my_subroutine()
             integer :: i, scalar1, scalar2
@@ -596,15 +691,16 @@ def test_directive_get_private(fortran_reader):
     loop = psyir.walk(Loop)[0]
     omplooptrans.apply(loop)
     directive = psyir.walk(OMPParallelDoDirective)[0]
-    pvars, fpvars = directive._get_private_clauses()
-    assert len(pvars.children) == 2
-    assert len(fpvars.children) == 1
-    assert pvars.children[0].name == 'i'
-    assert pvars.children[1].name == 'scalar2'
-    assert fpvars.children[0].name == 'scalar1'
-
-    # Another example with OMPParallelDirective (not actual worksharing)
-    # and scalars set outside the loop (this should be shared by convention)
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 2
+    assert sorted(pvars, key=lambda x: x.name)[0].name == 'i'
+    assert sorted(pvars, key=lambda x: x.name)[1].name == 'scalar2'
+    assert len(fpvars) == 1
+    assert list(fpvars)[0].name == 'scalar1'
+    assert len(sync) == 0
+
+    # Another example with only a OMPParallelDirective (not actual worksharing)
+    # and scalars set outside the loop (only-written-once), these are shared
     psyir = fortran_reader.psyir_from_source('''
         subroutine my_subroutine()
             integer :: i, scalar1, scalar2, scalar3, scalar4
@@ -616,17 +712,231 @@ def test_directive_get_private(fortran_reader):
                array(i) = scalar2
             enddo
         end subroutine''')
-    omplooptrans = OMPParallelTrans()
-    loop = psyir.walk(Routine)[0]
-    omplooptrans.apply(loop.children)
+    omptrans = OMPParallelTrans()
+    routine = psyir.walk(Routine)[0]
+    omptrans.apply(routine.children)
+    directive = psyir.walk(OMPParallelDirective)[0]
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 2
+    assert len(fpvars) == 0
+    assert len(sync) == 0
+    assert sorted(pvars, key=lambda x: x.name)[0].name == 'i'
+    assert sorted(pvars, key=lambda x: x.name)[1].name == 'scalar2'
+    # scalar1 is shared because is read-only and scalar3 and scalar4 are
+    # shared because they are set outside a loop (only written once)
+
+    # Another example with only a OMPParallelDirective (not actual worksharing)
+    # and one scalar (scalar2) it is used as a private variable inside the loop
+    # but it is first read before the loop, and therefore it should be
+    # firstprivate
+    psyir = fortran_reader.psyir_from_source('''
+        subroutine my_subroutine()
+            integer :: i, scalar1, scalar2, scalar3
+            real, dimension(10) :: array
+            scalar3 = scalar2
+            do i = 1, 10
+               scalar2 = scalar1 + scalar3 + array(i)
+               array(i) = scalar2
+            enddo
+        end subroutine''')
+    omptrans = OMPParallelTrans()
+    routine = psyir.walk(Routine)[0]
+    omptrans.apply(routine.children)
+    directive = psyir.walk(OMPParallelDirective)[0]
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 1
+    assert len(fpvars) == 1
+    assert len(sync) == 0
+    assert list(pvars)[0].name == 'i'
+    assert list(fpvars)[0].name == 'scalar2'
+
+    # Similar but with a OMPParallelDoDirective and the firstprivate is
+    # in the same loop but before the loop body
+    psyir = fortran_reader.psyir_from_source('''
+        subroutine my_subroutine()
+            integer :: i, scalar1
+            real, dimension(10) :: array
+            do i = 1, 10, scalar1
+                scalar1 = array(i)
+                array(i) = scalar1
+            enddo
+        end subroutine''')
+    omplooptrans = OMPParallelLoopTrans()
+    loop = psyir.walk(Loop)[0]
+    omplooptrans.apply(loop, options={'force': True})
+    directive = psyir.walk(OMPParallelDoDirective)[0]
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 1
+    assert len(fpvars) == 1
+    assert len(sync) == 0
+    assert list(pvars)[0].name == 'i'
+    assert list(fpvars)[0].name == 'scalar1'
+
+    # In this example the scalar2 variable is shared but it needs
+    # synchronisation to avoid race conditions (write-after-read
+    # in the same statement)
+    psyir = fortran_reader.psyir_from_source('''
+        subroutine my_subroutine()
+            integer :: i, scalar1, scalar2
+            real, dimension(10) :: array
+            do i = 1, 10
+               scalar2 = scalar2 + scalar1
+            enddo
+        end subroutine''')
+    omplooptrans = OMPParallelLoopTrans()
+    loop = psyir.walk(Loop)[0]
+    omplooptrans.apply(loop, options={"force": True})
+    directive = psyir.walk(OMPParallelDoDirective)[0]
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 1
+    assert list(pvars)[0].name == 'i'
+    assert len(fpvars) == 0
+    assert len(sync) == 1
+    assert list(sync)[0].name == 'scalar2'
+
+    # In this example the scalar2 variable is shared but it needs
+    # synchronisation to avoid race conditions (write-after-read
+    # in different statements)
+    psyir = fortran_reader.psyir_from_source('''
+        subroutine my_subroutine()
+            integer :: i, scalar1, scalar2, tmp
+            real, dimension(10) :: array
+            do i = 1, 10
+               tmp = scalar2 + scalar1
+               scalar2 = tmp
+            enddo
+        end subroutine''')
+    omplooptrans = OMPParallelLoopTrans()
+    loop = psyir.walk(Loop)[0]
+    omplooptrans.apply(loop, options={"force": True})
+    directive = psyir.walk(OMPParallelDoDirective)[0]
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 2
+    assert sorted(pvars, key=lambda x: x.name)[0].name == 'i'
+    assert sorted(pvars, key=lambda x: x.name)[1].name == 'tmp'
+    assert len(fpvars) == 0
+    assert len(sync) == 1
+    assert list(sync)[0].name == 'scalar2'
+
+    # Example tiling routine (k is a reduction - needs sync)
+    psyir = fortran_reader.psyir_from_source('''
+        subroutine my_subroutine(k)
+            integer :: i, ii
+            integer :: j, jj
+            integer :: k
+            do i = 1, 320, 32
+                do j = 1, 320, 32
+                    do ii=i, i+32
+                        do jj = j,j+32
+                            k = k + ii
+                            k = k * jj
+                        end do
+                    end do
+                end do
+            end do
+        end subroutine''')
+    ptrans = OMPParallelTrans()
+    loop = psyir.walk(Loop)[0]
+    ptrans.apply(loop)
     directive = psyir.walk(OMPParallelDirective)[0]
-    pvars, fpvars = directive._get_private_clauses()
-    assert len(pvars.children) == 2
-    assert len(fpvars.children) == 0
-    assert pvars.children[0].name == 'i'
-    assert pvars.children[1].name == 'scalar2'
-    # scalar 1 is shared because is read-only and scalar3 and scalar4 are
-    # shared because they are set outside a loop
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 4
+    assert sorted(pvars, key=lambda x: x.name)[0].name == 'i'
+    assert sorted(pvars, key=lambda x: x.name)[1].name == 'ii'
+    assert sorted(pvars, key=lambda x: x.name)[2].name == 'j'
+    assert sorted(pvars, key=lambda x: x.name)[3].name == 'jj'
+    assert len(fpvars) == 0
+    assert len(sync) == 1
+    assert list(sync)[0].name == 'k'
+
+
+def test_directive_infer_sharing_attributes_with_structures(fortran_reader):
+    ''' Tests for the _infer_sharing_attributes() method of OpenMP directives
+    with code that contains structure accesses.
+    '''
+    psyir = fortran_reader.psyir_from_source('''
+        subroutine my_subroutine()
+            use my_mod
+            integer :: i, scalar1
+            type(my_type) :: mt1, mt2
+            real, dimension(10) :: array
+            mt1%scalar1 = 3
+            do i = 1, 10
+               if (i .eq. 4) then
+                  mt2%field1%scalar1 = array(i)
+               endif
+               scalar1 = mt2%field1%scalar1 + mt1%scalar1
+               array(i) = scalar1
+            enddo
+        end subroutine''')
+    omptrans = OMPParallelTrans()
+    routine = psyir.walk(Routine)[0]
+    omptrans.apply(routine.children)
+    directive = psyir.walk(OMPParallelDirective)[0]
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 2
+    assert sorted(pvars, key=lambda x: x.name)[0].name == 'i'
+    assert sorted(pvars, key=lambda x: x.name)[1].name == 'scalar1'
+    assert len(fpvars) == 1
+    assert list(fpvars)[0].name == 'mt2'
+    assert len(sync) == 0
+
+    # In this example a sub-part of mt1 should be shared and another
+    # firstprivate
+    psyir = fortran_reader.psyir_from_source('''
+        subroutine my_subroutine()
+            use my_mod
+            integer :: i, scalar1
+            type(my_type) :: mt1
+            real, dimension(10) :: array
+            do i = 1, 10
+               if (i .eq. 4) then
+                  mt1%scalar1 = 3
+               endif
+               mt1%array(i) = mt1%scalar1
+            enddo
+        end subroutine''')
+    omptrans = OMPParallelTrans()
+    routine = psyir.walk(Routine)[0]
+    omptrans.apply(routine.children)
+    directive = psyir.walk(OMPParallelDirective)[0]
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 1
+    assert list(pvars)[0].name == 'i'
+    assert len(fpvars) == 1
+    if list(fpvars)[0].name == 'mt2':
+        pytest.xfail("#2094: Currently we only support top-level derived types"
+                     "as OpenMP sharing attributes, but there are cases that "
+                     "more detail is necessary.")
+
+
+def test_infer_sharing_attributes_sequential_semantics(fortran_reader):
+    ''' _infer_sharing_attributes() tries to conserve the same semantics
+    as the sequential loop, however, for loops that are not possible to
+    parallelise (but we force the transformation anyway). For now this
+    may return different results than the original code.
+
+    #TODO #598: This could be a lastprivate?
+    '''
+
+    # In this example the result will take the value of the last i in
+    # sequential order, but an arbitrary i in parallel.
+    psyir = fortran_reader.psyir_from_source('''
+        subroutine my_subroutine()
+            integer :: i, result
+            do i = 1, 10
+               result = i
+            enddo
+        end subroutine''')
+    omplooptrans = OMPParallelLoopTrans()
+    loop = psyir.walk(Loop)[0]
+    omplooptrans.apply(loop, options={"force": True})
+    directive = psyir.walk(OMPParallelDoDirective)[0]
+    pvars, fpvars, sync = directive._infer_sharing_attributes()
+    assert len(pvars) == 1
+    assert list(pvars)[0].name == 'i'
+    assert len(fpvars) == 0
+    assert len(sync) == 0
 
 
 def test_directive_lastprivate(fortran_reader, fortran_writer):
diff --git a/src/psyclone/tests/psyir/transformations/transformations_test.py b/src/psyclone/tests/psyir/transformations/transformations_test.py
index a229afbb8..b2a43b3da 100644
--- a/src/psyclone/tests/psyir/transformations/transformations_test.py
+++ b/src/psyclone/tests/psyir/transformations/transformations_test.py
@@ -493,47 +493,6 @@ firstprivate(scalar1), schedule(auto)
     assert expected in gen
     assert Compile(tmpdir).string_compiles(gen)
 
-    # Example with a read before write
-    psyir = fortran_reader.psyir_from_source('''
-        module my_mod
-            contains
-            subroutine my_subroutine()
-                integer :: ji, jj, jk, jpkm1, jpjm1, jpim1, scalar1, scalar2
-                real, dimension(10, 10, 10) :: zwt, zwd, zwi, zws
-                do jk = 2, jpkm1, 1
-                  do jj = 2, jpjm1, 1
-                    do ji = 2, jpim1, 1
-                       scalar2 = scalar1 + zwt(ji,jj,jk)
-                       scalar1 = 3
-                       zws(ji,jj,jk) = scalar2 + scalar1
-                    enddo
-                  enddo
-                enddo
-            end subroutine
-        end module my_mod''')
-    omplooptrans = OMPParallelLoopTrans()
-    loop = psyir.walk(Loop)[0]
-    # This need to be forced since the DependencyAnalysis wrongly considers
-    # it a reduction
-    omplooptrans.apply(loop, options={"force": True})
-    expected = '''\
-    !$omp parallel do default(shared), private(ji,jj,jk,scalar2), \
-firstprivate(scalar1), schedule(auto)
-    do jk = 2, jpkm1, 1
-      do jj = 2, jpjm1, 1
-        do ji = 2, jpim1, 1
-          scalar2 = scalar1 + zwt(ji,jj,jk)
-          scalar1 = 3
-          zws(ji,jj,jk) = scalar2 + scalar1
-        enddo
-      enddo
-    enddo
-    !$omp end parallel do'''
-
-    gen = fortran_writer(psyir)
-    assert expected in gen
-    assert Compile(tmpdir).string_compiles(gen)
-
 
 def test_omplooptrans_apply_firstprivate_fail(fortran_reader):
     ''' Test applying the OMPLoopTrans in cases where a firstprivate