Loop incorrectly parallelised by ParallelLoopTrans

[mn416]

While working on PR #3213 I found the following example where ParallelLoopTrans incorrectly parallelises a loop:

module main_mod
  implicit none

  type :: Box
    integer :: arr(10)
  end type
contains
  subroutine main()
    type(Box) :: b
    integer :: i

    do i = 1, size(b%arr)
      b%arr(i) = i
      call modify(b)
    end do
  end subroutine

  pure subroutine modify(b)
    type(Box), intent(inout) :: b
    b%arr(1) = 0
  end subroutine
end module

Here is a small script to demonstrate the issue:

from psyclone.psyir.transformations import OMPLoopTrans, TransformationError
from psyclone.psyir.nodes import Loop, Routine

def trans(psyir):
    for loop in psyir.walk(Loop):
        OMPLoopTrans(omp_directive="paralleldo").apply(loop)

Note that DependencyTools actually reports a SCALAR_WRITTEN_ONCE dependency but ParallelLoopTrans explicitly ignores it (for reasons I don't understand). Still, as DependencyTools explores scalar conflicts and array conflicts independently, it never considers the write to b and the write to b%arr(i) to be conflicting, which feels wrong.

@hiker may be interested in this.

[mn416]

Another loop that is parallelised by ParallelLoopTrans but shouldn't be:

subroutine strided_loop(arr)
  integer, intent(inout) :: arr(:)
  integer :: i

  do i = 1, size(arr)
    arr(i/2) = 0
  end do
end subroutine

[LonelyCat124]

The first one seems difficult to solve - we'd need to probably use a lot of the "inlining" functionality (variable renaming etc.) either inside the transformation or the dependency tools analysis (potentially we could be risk-averse and disallow non pure+elemental functions that have any structure or array passed into them, but that may affect some valid code currently using this transformation).

The second one I think should be solved by _array_access_parallelisable but for whatever reason it isn't. @hiker I'm guessing _get_dependency_distance doesn't consider division correctly? I'm not sure how the sympy stuff works but maybe it needs to treat integer division with // instead of / (since in Python 1/2 = 0.5 but 1//2 = 0)

[mn416]

Thanks @LonelyCat124. In the first example, I had envisaged a rule that would say that a write of scalar b conflicts with an array read/write of b%... for all ....

Interesting suggestion on the second example!

[LonelyCat124]

Yeah, maybe the dependency tools isn't considering that call modify(b) should treat b as a potential array access (since it has different behaviours for the result of is_array_access in can_loop_be_parallelised, and that might be sufficient to solve this for now, but I'm guessing a bit as this section of dependency analysis I've not worked with directly, and either @hiker or @sergisiso may be better to work it out.

We maybe could make a StructureSymbol return True if the base symbol is accessed, but I expect s that bits of PSyclone might attempt to lookup the indices at that point and fall over so we might not be able to cheat a solution like that.

[sergisiso]

The problem is that our VariableAccessMap treats b and b%arr completely indpendently, and therefore doesn't check dependencies between them:

(Pdb) pp loop.reference_accesses()
{Signature(b): [<psyclone.core.access_sequence.AccessInfo object at 0x7e45bb137da0>],
 Signature(b%arr): [<psyclone.core.access_sequence.AccessInfo object at 0x7e45bb1378c0>,
                    <psyclone.core.access_sequence.AccessInfo object at 0x7e45bb137a40>],

We could find and merge these accesses entries under their base signature, or even better, under the minimmum common base, so loops only using "Signature(b%arr)" and "Signature(b%arr2)" would still analyse them independenlty.

Maybe the reference_accesses method itself should do the "merging to the common base" step itself, as this problem not only affects the DependencyTools but anything using the reference_accesses output.

[sergisiso]

Note that DependencyTools actually reports a SCALAR_WRITTEN_ONCE dependency but ParallelLoopTrans explicitly ignores it (for reasons I don't understand)

It is because it expects that the lowering will solve the dependency by privatising each scalar write. In this case the lowering doesn't add the private because we have this code:

# If a variable is only accessed once, it is either an error
# or a shared variable - anyway it is not private
if len(accesses) == 1:
    continue

Merging the accesses of both signatures would also solve this.

[mn416]

We could find and merge these accesses entries under their base signature, or even better, under the minimmum common base

Thanks @sergisiso, I like this idea. One slightly surprising thing would be that accesses in an AccessSequence could now have different types. Hopefully existing code would handle that ok.

[hiker]

Besides merging, we could add a separate step in the DA to check for overlaps in structure types. I've opened #3242 to address this after my training (which likely means next year tbh).