7.3. Loop-Carried Lexical Forward Dependence

The following example tests the restriction on an SIMD loop with the loop-carried lexical forward-dependence. This dependence must be preserved for the correct execution of SIMD loops.

A loop can be vectorized even though the iterations are not completely independent when it has loop-carried dependences that are forward lexical dependences, indicated in the code below by the read of A[j+1] and the write to A[j] in C/C++ code (or A(j+1) and A(j) in Fortran). That is, the read of A[j+1] (or A(j+1) in Fortran) before the write to A[j] (or A(j) in Fortran) ordering must be preserved for each iteration in j for valid SIMD code generation.

This test assures that the compiler preserves the loop carried lexical forward-dependence for generating a correct SIMD code.

//%compiler: clang
//%cflags: -fopenmp

/*
* name: SIMD.8
* type: C
* version: omp_4.0
*/
#include <stdio.h>
#include <math.h>

int   P[1000];
float A[1000];

float do_work(float *arr)
{
  float pri;
  int i;
#pragma omp simd lastprivate(pri)
  for (i = 0; i < 999; ++i) {
    int j = P[i];

    pri = 0.5f;
    if (j % 2 == 0) {
      pri = A[j+1] + arr[i];
    }
    A[j] = pri * 1.5f;
    pri = pri + A[j];
  }
  return pri;
}

int main(void)
{
  float pri, arr[1000];
  int i;

  for (i = 0; i < 1000; ++i) {
     P[i]   = i;
     A[i]   = i * 1.5f;
     arr[i] = i * 1.8f;
  }
  pri = do_work(&arr[0]);
  if (pri == 8237.25) {
    printf("passed: result pri = %7.2f (8237.25) \n", pri);
  }
  else {
    printf("failed: result pri = %7.2f (8237.25) \n", pri);
  }
  return 0;
}

!!%compiler: gfortran
!!%cflags: -fopenmp

! name: SIMD.8
! type: F-free
! version: omp_4.0
module work

integer :: P(1000)
real    :: A(1000)

contains
function do_work(arr) result(pri)
  implicit none
  real, dimension(*) :: arr

  real :: pri
  integer :: i, j

  !$omp simd private(j) lastprivate(pri)
  do i = 1, 999
    j = P(i)

    pri = 0.5
    if (mod(j-1, 2) == 0) then
      pri = A(j+1) + arr(i)
    endif
    A(j) = pri * 1.5
    pri = pri + A(j)
  end do

end function do_work

end module work

program simd_8f
  use work
  implicit none
  real :: pri, arr(1000)
  integer :: i

  do i = 1, 1000
     P(i)   = i
     A(i)   = (i-1) * 1.5
     arr(i) = (i-1) * 1.8
  end do
  pri = do_work(arr)
  if (pri == 8237.25) then
    print 2, "passed", pri
  else
    print 2, "failed", pri
  endif
2 format(a, ": result pri = ", f7.2, " (8237.25)")

end program