"unreachable" reached (with infinite loops) vs Julia

Internals & Design
1

This “unreachable” concept is rather low-level, in LLVM, and I’ve not thought much of it, until seeming you can define it in C++ as a function? Should Julia do the same. And see here C++ vs C difference related to it and loops:

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p2809r3.html

2

This was addressed in Julia#52999.

1 Like
3

Is your question about behavior of infinite loops or explicit unreachable / UB?

Unreachable can be obtained via llvmcall. You can use this to insert assumptions, a la x > 0 || unreachable() to give the compiler license to assume that x is positive. Related is the llvm builtin assume.

There is an argument to put it into Base – I think that would be nice, but not essential (easy enough to type as llvmcall).

4

As far as I’m aware, there’s not much reason to use llvmcall to get unreachable, because julia’s error() already emits an unreachable. e.g.

julia> code_llvm((Int,); debuginfo=:none) do x
           x > 0 || error("got non-positive x!")
           s = 0
           for i ∈ 1:10
               if x < 0
                   s += 1
               end
           end
           s
       end
define i64 @"julia_#8_186"(i64 signext %0) #0 {
top:
  %1 = icmp slt i64 %0, 1
  br i1 %1, label %L23, label %L5.preheader

L5.preheader:                                     ; preds = %top
  ret i64 0

L23:                                              ; preds = %top
  call void @j_error_188({}* inttoptr (i64 140149786375928 to {}*)) #7
  unreachable
}

Here we see that the compiler is re-using the knowledge that x > 0 inside the loop body to determine that the program either returns 0 or errors.

4 Likes
5

Consider the following kind of code:

sqrt(x)

Now you computer will need to check whether x < 0, and if so will need to throw an exception.

But you know that x > 0! So try

x > 0 || error()
sqrt(x)

Ok, the sqrt(x) doesn’t need to check anymore: It can only be reached if x > 0. But the branch cannot be optimized away: In the !(x > 0) case, there will come up an unreachable. But only because it isn’t reached – this function has perfectly well-defined semantics and will longjmp to an exception handler.

On the other hand, consider

x > 0 || unreachable()
sqrt(x)

In this case, there will be no check whether x>0. None at all, the x > 0 || unreachable() has the effect of removing the subsequent check without introducing a new one.

unreachable is literally naked UB – undefined behavior. There are common ways of reasoning about UB:

  1. It is undefined behavior. The compiler can do whatever is convenient.
  2. It cannot happen. That is, the optimizing compiler reasons about your code; it does optimizations that it can prove safe. “prove” is always relative to both logic / rules of deduction, and axioms. Some axioms are stuff like x + (y + z) == (x + y) + z for i64. Another important axiom is that unreachable cannot be reached. Hence, it logically follows that x > 0 (otherwise unreachable would be reached before side-effects), and sqrt doesn’t need to check nonnegativity anymore.

“ex falso quodlibet”, i.e. anything can be derived from a contradiction. If the compiler can also prove that !(x>0) then it follows that your function cannot be called (before side-effects) and any other function that calls your function cannot be called, etc.

5 Likes
6

Thanks, I see Julia is doing the same change as C++ (I see the change already in effect in 1.10.3):

My question wasn’t about invoking unreachable or how exactly possible, rather if Julia should be able to define the destination as in the C++ example:

void unreachable() {
  std::cout << "Hello world!" << std::endl;
}

I see that this “forward progress guarantee” (or not, for trivial infinite loops) is the much more interesting question, and it’s quite the rabbit hole (I hadn’t really looked at this “unreachable” business beyond a single threaded program):

Since C++ diverged from C practical for infinite loops, and then C11 made the same change, and now C++26 is (partially) changing back (and I suppose C too), an interesting question is, does Julia align more with C++, or C when the semantics differ?

N1528: Why undefined behavior for infinite loops? N1528: Why undefined behavior for infinite loops?

C xor C++ Programming: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2735r0.pdf

It is not uncommon to hear about C/C++ programming as a shorthand for “C and C++” programming. This implies that C and C++ are similar, but distinct, programming languages with the obvious interpretation being that C++ is a proper superset of C. However, this does not accurately describe the situation.

C Compilers Disprove Fermat’s Last Theorem: C Compilers Disprove Fermat’s Last Theorem – Embedded in Academia

I suppose at least if it can not be stated if Julia aligns with C++ fully (or C), or mostly, then at least with (there it applies):

Programming languages — a common C/C++ core specification https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2644.pdf

I think I posted this in Offtopic, since I though people might be interested (in obscure C++26 issues), and casually asked, how Julia compares. I at least think I did, and thus assume someone moved to internals. If nothing needs to be discussed about more changes in Julia, at least consider moving back to Offtopic, or where you think more read than Internals.

7

The business with infinite loops being undefined is so nuts to me. Yeah, because no one would ever want to write a program that runs until it is externally terminated. Right, servers aren’t a thing! Julia’s support for this is limited only by LLVM’s.

What I could see is that if a loop has no side effects then it might be ok to just skip it, but even that seems a little dicey to me.

2 Likes
8

It was also about being a trivial loop, loops with side effects were never undefined behaviour. The idea is to allow the language to assume forward progress but it’s a bit of a mess and thankfully they walked it back.

4 Likes