at-simd be messing with my for loops

[quinnj]

Consider the following on commit 215249d, Windows 64-bit:

In  [2]: for k = 1:4
    @show k
    for i = 2:4
        @show i
        i == k && continue
    end
end
k = 1
i = 2
i = 3
i = 4
k = 2
i = 2
i = 3
i = 4
k = 3
i = 2
i = 3
i = 4
k = 4
i = 2
i = 3
i = 4

And with @simd

In  [3]: for k = 1:4
    @show k
    @simd for i = 2:4
        @show i
        i == k && continue
    end
end
k = 1
i = 2
i = 3
i = 4
k = 2
i = 2
i = 2
i = 2
i = 2
i = 2
i = 2
i = 2
i = 2
... # until I terminate the process

@ArchRobison

[simonster]

The problem seems to be here. i is incremented after the body of the loop, but that doesn't happen if you call continue. break can also create incorrect behavior because @simd sets i to last(r) when it completes regardless of the number of loop iterations:

julia> function f()
           local i
           for i = 1:10
               i == 2 && break
           end
           i
       end;

julia> f()
2

julia> function f()
           local i
           @simd for i = 1:10
               i == 2 && break
           end
           i
       end;

julia> f()
10

[jakebolewski]

Having break or continue in a @simd loop body does not abide by the assertions it assumes you are making about the loop body.

[StefanKarpinski]

Yes, it should probably be a static error to do that. cc @ArchRobison

[jakebolewski]

Its a slippery slope if the compiler has to prove these assertions, I think at best we could throw a warning in some cases.

[StefanKarpinski]

No, that's not what I mean – I mean if a break or continue appears in a loop body, then raise an error. That's an easy syntactic condition to check.

[ArchRobison]

I concur that @simd should do a syntactic check and reject break and continue. In principle, continue would not be difficult to support with a goto/label, though it's probably a lot of work for little gain since the LLVM vectorizer will probably choke anyway on a non-trivial continue.

Can anyone suggest good prior art in base (or other packages?) for this kind of checking?

[jakebolewski]

I haven't rigorously tested this, but it seems sufficient.

diff --git a/base/simdloop.jl b/base/simdloop.jl
index 139b10f..5be991c 100644
--- a/base/simdloop.jl
+++ b/base/simdloop.jl
@@ -19,10 +19,28 @@ function parse_iteration_space(x)
     x.args # symbol, range
 end

+# reject control flow statements in simd loop body
+function no_control_flow(ex::Expr)
+    if ex.head === :break || ex.head == :continue || (ex.head === :macrocall && ex.args[1] === symbol("@goto"))
+        throw(SimdError("$(ex.head) is not allowed inside @simd loop body"))
+    end
+    for arg in ex.args
+        if isa(arg, Expr)
+            no_control_flow(arg)
+        elseif isa(arg, QuoteNode)
+            no_control_flow(arg)
+        end
+    end
+    return true
+end
+no_control_flow(ex::QuoteNode) = no_control_flow(ex.value)
+no_control_flow(ex) = true
+
 # Compile Expr x in context of @simd.
 function compile(x)
     (isa(x, Expr) && x.head == :for) || throw(SimdError("for loop expected"))
     length(x.args) == 2 || throw(SimdError("1D for loop expected"))
+    no_control_flow(x)

     var,range = parse_iteration_space(x.args[1])
     r = gensym("r") # Range value

[jakebolewski]

I guess what I was thinking about were branches that the compiler can prove are never taken. This should not defeat the vectorizer if the branch is stripped out, so throwing an error in this case doesn't seem to be technically correct but it is probably best to be conservative.

[ArchRobison]

Are the isa tests necessary? It looks like the if...elseif...end part could just be no_control_flow(arg)?

[jakebolewski]

No, they should be stripped out.

[simonster]

Generally, I don't think break and continue have to work since it doesn't seem like LLVM can do any vectorization when they're present, but I'm not sure they're illegal according to our documentation for @simd. If you take out @show, I think @quinnj's original example is safe to execute in arbitrary order and no iteration waits on another to make progress, although it's not straight line code and probably can't be vectorized. break is somewhat more questionable, but I can imagine:

x = false
for i = 1:n
    x |= v[i]
    x && break
end

where break is only a performance optimization, although LLVM won't vectorize this either.

Now that llvm.loop.parallel has been replaced by llvm.loop, it's also not totally clear to me that what we're asserting to LLVM is as strong as what we've documented @simd to assert, although perhaps the extra restrictions will give us freedom to move bounds checks before the loop at some future date.

[ArchRobison]

My long term goal is indeed to let us move bounds checks before the loop, or vectorize the checks, so that using @inbounds with @simd would not be necessary.

While implementing parallel STL for C++, I ran into use cases for break inside a vector loop, but so far I'm not aware of any vectorizer that handles such cases. A sticky point is what the value of the index variable should be after the break. Some use cases will settle for any value that led to a break; other uses cases need the leftmost value.