silent incorrect result when reusing the previous iteration value

[johnnychen94]

I'm not sure how to describe this issue, maybe I'm using the wrong terminology. Here's the MWE

using LoopVectorization

A = rand(Bool, 64, 64)

function f_v1(A)
    out = zeros(size(A))

    for y in 2:(size(A, 2) - 1)
        for x in 2:(size(A, 1) - 1)
            tmp = max(max(A[x, y], A[x - 1, y]), A[x + 1, y])
            out[x, y] = max(max(tmp, A[x, y - 1]), A[x, y + 1])
        end
    end
    return out
end

function f_turbo_v1(A)
    out = zeros(size(A))

    @turbo for y in 2:(size(A, 2) - 1)
        for x in 2:(size(A, 1) - 1)
            tmp = max(max(A[x, y], A[x - 1, y]), A[x + 1, y])
            out[x, y] = max(max(tmp, A[x, y - 1]), A[x, y + 1])
        end
    end
    return out
end

# the idea is to reuse the `getindex` result from last iteration
function f_v2(A)
    out = zeros(size(A))

    for y in 2:(size(A, 2) - 1)
        p, p_down = A[1, y], A[2, y]
        for x in 2:(size(A, 1) - 1)
            p_up, p, p_down = p, p_down, A[x + 1, y]
            tmp = max(max(p, p_up), p_down)
            out[x, y] = max(max(tmp, A[x, y - 1]), A[x, y + 1])
        end
    end
    return out
end

function f_turbo_v2(A)
    out = zeros(size(A))

    @turbo for y in 2:(size(A, 2) - 1)
        p, p_down = A[1, y], A[2, y]
        for x in 2:(size(A, 1) - 1)
            p_up, p, p_down = p, p_down, A[x + 1, y]
            tmp = max(max(p, p_up), p_down)
            out[x, y] = max(max(tmp, A[x, y - 1]), A[x, y + 1])
        end
    end
    return out
end

out1 = f_v1(A);
out2 = f_turbo_v1(A);
out3 = f_v2(A);
out4 = f_turbo_v2(A);

out1 == out2 # true
out1 == out3 # true
out1 == out4 # false # Oops

LoopVectorization v0.12.118 on Ubuntu(WSL)

julia> versioninfo()
Julia Version 1.8.0-rc1
Commit 6368fdc656 (2022-05-27 18:33 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 24 × 12th Gen Intel(R) Core(TM) i9-12900K
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, goldmont)
  Threads: 16 on 24 virtual cores

[johnnychen94]

Are not relying on specific execution order. @turbo can and will re-order operations and loops inside its scope, so the correctness cannot depend on a particular order. You cannot implement cumsum with @turbo.

Oh, I guess I break this assumption from README?

[chriselrod]

Yes. I am spending most of my free time on
https://github.com/JuliaSIMD/LoopModels
which will fix this issue (and many others) by properly tracking dependencies across loop iterations.

[johnnychen94]

Close since it's a "known" issue. But if you want it open, feel free to reopen it.