Reconsider stance on forward progress guarantees

[Keno]

Our longstanding policy on forward progress guarantees has basically been that
we expose the LLVM behavior and follow the C/C++ world by considering infinite
loops to be undefined behavior, leading to behavior like:

julia> f(x) = x ? true : while true; end
f (generic function with 1 method)

julia> f(true)
true

julia> f(false)
true

This might not seem to bad, but it can lead to unsoundness and security vulnerabilities ("nice error check you have there, would be a shame if somebody were to see the UB before it")

julia> @noinline function my_checkbounds(Alen::Int, i::Int)
               if i < 0 || i > Alen
                       while true; end # A bad error path, maybe inlined from somewhere
                       return false
               end
               return true
       end
my_checkbounds (generic function with 2 methods)

julia> function my_getindex(A::Vector{Int}, i::Int)
               my_checkbounds(length(A), i) || error("Out of bounds!")
               @inbounds A[i]
       end
my_getindex (generic function with 1 method)

julia> my_getindex(Int[1], 100000000)

signal (11): Segmentation fault

For this reason, more modern languages tend to not make forward progress assumptions. The Rust folks in particular took this quite seriously and recently changed LLVM to require the mustprogress attribute in order to top into forward progress guarantees (https://reviews.llvm.org/D85393). We should carefully chose what to do here. Since we don't set the new LLVM attribute, LLVM actually no longer makes these forward progress assumptions on our code. However, we do still make such assumptions in our own inference code.

Now that LLVM is fixed, my preference would be to follow Rust here and stop making any forward progress assumptions.

[nsajko]

I'd just like to note that I think some things above are possibly misleading. This is the relevant part of the example:

while true; end
return false

In the context of the rest of the example, probably everybody would prefer the infinite loop to stay where it is and keep the return from executing and it's true that the forward progress guarantee could cause the loop to be eliminated, but ...

... I think the loop could also be eliminated by much more basic semantics: return false has no dependency on the loop; so I suppose a compiler for basically any compiled programming language could reorder the two lines, putting the loop after the return, thus making the loop unreachable anyway.

AFAIK, Julia has no memory model or specifications for stuff like observability, volatile reads or volatile writes (I think it's not even possible to do volatile reads or writes from Julia?); it seems like this discussion could lack essence until Julia is better specified in those regards.

(BTW, it's possible I made some mistakes here because I'm new to Julia, but I tried to talk about programming language stuff in general.)

[Keno]

I'd just like to note that I think some things above are possibly misleading.

The point was to illustrate that undefined behavior can lead to soundness violations that are otherwise unexpected. I'm not sure what's misleading about that.

... I think the loop could also be eliminated by much more basic semantics: return false has no dependency on the loop; so I suppose a compiler for basically any compiled programming language could reorder the two lines, putting the loop after the return, thus making the loop unreachable anyway.

C/C++ explicitly make this undefined behavior, but I don't really know of any compiler that reasons this way. You can usually move probably pure statements between sequence points, but a return is usually a terminal sequence point and you cannot commute things past it. Of course you can eliminate pure statements that have an unused result, but that gets back to the definition of purity here.

[martinholters]

Given that f(false) now hangs, can you provide an example which exposes the problem on the Julia rather than the LLVM side?

[stevengj]

This loop doesn't hang (in either 1.7 or 1.9-dev):

julia> f(x) = while x end
f (generic function with 1 method)

julia> f(true) # doesn't hang

[brenhinkeller]

Since #47664 is closed as dup, I'll just note here that it might be nice if the solution ensures this

julia> all(Iterators.repeated(true))
false

julia> any(Iterators.repeated(false))
true

doesn't happen one way or another 😀

[gbaraldi]

https://isocpp.org/files/papers/P2809R3.html C++ just changed their side of this so probably a useful reference