Does our UB have "time travel" semantics?

If a program performs an externally observable action (such as printing to stderr or volatile memory accesses) followed by UB, do we guarantee that the action occurs?

The fact that C does not guarantee this is known as "time-traveling UB" and it can be quite perplexing. It arises when the compiler reorders potentially-UB operations up across mustreturn functions:

eprintln!("I'm here!"); // let's say the compiler deduced that this must return
ptr::null::<i32>().read();

If the read is moved up across the print, we get a pagefault before printing, i.e. we have time travel.

From the theory perspective, this is a reasonably clear situation: either we can move potentially-UB code up across externally observable operations, or we guarantee that UB is properly sequenced wrt externally observable operations. We cannot have both. (In principle we can decide this on a per-operation basis, e.g. we could require proper sequencing for stdout/stderr but allow reordering for volatile accesses.)

So how bad is the cost of not doing such optimizations? Is that even something we can currently evaluate, or does LLVM just always perform such reorderings?

(I am assuming here a general consensus that potentially-UB operations can be reordered wrt not externally observable operations. This can only be observed with a debugger and IMO clearly falls on the side of the optimizations having too may benefits to do anything else.)

(I'm aware that I am going to ignore the questions you directly posed and generally address the broader issue)

I'm very wary of this question. I commented in the meeting that I'm concerned that the actual problem here is not so much about the suitability of some semantics, but about the user's ability to debug programs.

So I'm concerned that we have a sort of fundamental teaching/tooling issue. Many users learn to debug programs compiled in a debugging-friendly mode by inserting println! or such. And then they develop an incorrect intuition for how to debug their programs and eventually try to extend this to a program which executes UB and then have trouble.

I suggested in the meeting that what users probably need is a UB-proof debugging facility. Miri is one such facility, but it can't execute all programs so we definitely need more. Sanitizers are another such partial facility. If we are going to have reorderings over externally observable effects, I think we should be able to explain how users should debug programs in the face of such reorderings.

I suggested in the meeting that what users probably need is a UB-proof debugging facility. Miri is one such facility, but it can't execute all programs so we definitely need more. Sanitizers are another such partial facility. If we are going to have reorderings over externally observable effects, I think we should be able to explain how users should debug programs in the face of such reorderings.

I want to bring up a related point that likely needs a separate issue but I fear will get shot down too quickly out of context. C compilers often come with flags to control what standard they conform to. The obvious example of this is --std=c99 but I am thinking here more about flags like -fwrapv, which can be thought of as crossing out the line of the standard that says "signed overflow is UB" and replacing it with "signed overflow is defined to wrap".

Historically, we have shied away from such flags for fear of fragmenting the ecosystem, but perhaps this is a good place to use the technique. Turning off optimizations is obviously not the right way to get predictable behavior in the face of UB, but a flag that actually makes more things DB (at the expense of performance) might actually be a much more effective way to get many of the same benefits from Miri in the regular compiler. In this case, we could have a flag that makes all IO actions block propagation of UB. Another example along the same lines would be a flag to make all reads and writes volatile.

I'm very wary of this question. I commented in the meeting that I'm concerned that the actual problem here is not so much about the suitability of some semantics, but about the user's ability to debug programs.

That sounds like an important axis for "suitability of the semantics" to me. Making printf-debugging work is a good argument against time-traveling UB.

So how bad is the cost of not doing such optimizations? Is that even something we can currently evaluate, or does LLVM just always perform such reorderings?

I don't think there's a way to specifically tell LLVM not to perform such reorderings. But as far as I can tell, the allowed optimizations without time travel are exactly equivalent to the allowed optimizations if you assume that I/O functions might loop forever instead of returning. So in theory, it should just be a matter of removing the willreturn attribute from all functions that perform externally observable actions (as well as any copies of the attribute that are placed directly on call instructions).

In practice, though, I don't think I/O functions or calls ever get annotated with willreturn in the first place. rustc never applies willreturn annotations except in the case of asm! invocations marked as pure. Even if you use LTO to add in Clang-generated IR, Clang only applies willreturn to functions marked __attribute__((const)) or __attribute__((pure)) (plus the runtime functions used to implement atomics on some platforms).

Nor can LLVM deduce willreturn on its own. Even if the implementations of I/O functions are visible due to LTO, and even if LLVM can follow the chain of calls all the way down to the underlying syscalls, it has no way of knowing the syscalls must return without manual annotations. (Though things might differ if you're in some minimal embedded environment where I/O functions are in-process and just write to some buffer.)

As for volatile accesses, LLVM already treats volatile stores as potentially not returning, though not so for volatile loads, per LangRef.

In sum, with the exception of volatile loads, rustc already doesn't do time travel in practice. If anything, the question is how much performance could be gained by adding willreturn to I/O functions. Probably not much.

That said, if we wanted to officially guarantee the absence of time travel, we'd have to consider the possibility that Clang someday decides to add an attribute for willreturn, and OS vendors start using it for I/O functions, potentially infecting Rust code compiled with LTO. (If the C standard proposal to ban time travel is passed, that might become a non-issue.)

a flag that actually makes more things DB (at the expense of performance) might actually be a much more effective way to get many of the same benefits from Miri in the regular compiler.

Isn't this what debug assertions are already doing with eg. rust-lang/rust#51713? I'm specifically thinking of rust-lang/rust#98112 here, which added assertions on the language level, not just in the library.
I assume that these assertions would also inhibit LLVM from reordering code around them.

@digama0

I do not think so. Per @digama0's comment, what I'm doing is not like -fwrapv, it's like -fsanitize=undefined. I'm interested in making programs halt and report UB, not continue.

@comex

@comex from the llvm langref

The compiler may assume execution will continue after a volatile operation, so operations which modify memory or may have undefined behavior can be hoisted past a volatile operation.

that to me reads that all volatile is "will return" semantically.

@Lokathor

@Lokathor the very next paragraph is:

As an exception to the preceding rule, the compiler may not assume execution will continue after a volatile store operation. This restriction is necessary to support the somewhat common pattern in C of intentionally storing to an invalid pointer to crash the program. In the future, it might make sense to allow frontends to control this behavior.

@nikic

@nikic what is LLVM's current stance on this? IIRC UB is allowed to time-travel back across willreturn functions, and presumably it would be permitted to mark something like putc as willreturn?

@nikic what is LLVM's current stance on this? IIRC UB is allowed to time-travel back across willreturn functions,

Yes.

and presumably it would be permitted to mark something like putc as willreturn?

This doesn't happen currently, and I'm not sure it's valid to mark I/O as willreturn in general. I don't think there is a guarantee that I/O operations ever actually complete?

Maybe not putc, but non-blocking syscalls generally must return, right?

(And ofc LLVM considers volatile reads to be willreturn and those are also observable events, so that could also lead to time travel UB.)

Probably worth noting that the current C standard no longer allows time travel across volatile and I/O (see 5.1.2.4.6).

So that would probably be another argument for making volatile loads non-willreturn. And I guess also a stronger argument for why I/O is not willreturn, beyond "it might hang forever".

The relevant paragraph:

The least requirements on a conforming implementation are:
— Volatile accesses to objects are evaluated strictly according to the rules of the abstract machine.
— At program termination, all data written into files shall be identical to the result that execution
of the program according to the abstract semantics would have produced.
— The input and output dynamics of interactive devices shall take place as specified in 7.23.3.
The intent of these requirements is that unbuffered or line-buffered output appear as soon as
possible, to ensure that prompting messages appear prior to a program waiting for input.
This is the observable behavior of the program.

And a note in the UB definition:

Note 3 to entry: Any other behavior during execution of a program is only affected as a direct consequence of
the concrete behavior that occurs when encountering the erroneous or non-portable program construct or data.
In particular, all observable behavior (5.1.2.4) appears as specified in this document when it happens before an
operation with undefined behavior in the execution of the program.

I'm sure there's a normative version of that somewhere as well :)

Oh, I didn't realize they actually went through with this. By "current" you mean which version? I am looking at C23 and cannot see this in 5.1.2.4. C23 seems to be the latest version that's actually finished if I read this page correctly.

The document I'm looking at is https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3220.pdf. I have no idea what exactly that draft corresponds to...

I was going to do the FCP in the respective PRs (rust-lang/reference#2320, rust-lang/rust#160564).

https://llvm.godbolt.org/z/EddY7hEra (using opt (trunk) so most recent llvm push).

If a function (or call) that does a volatile access or I/O has the willreturn attribute, it can be elided when doing UB immediately after, so this question

I'm notably interested in what happens in the xLTO case where foreign IO/volatile is marked explicitly willreturn (or equivalent), and that inference reaches optimizations done on rust code without knowledge of the body. That seems like precluding time-travelling UB would mean such functions cannot be modeled as having Rust AM side effects.

is still interesting.

Notably, if that function comes from C (but linked with xLTO), it might be doing Pre-C11 signal handler communication that a. Is known to be total, and b. doesn't matter if it gets elided, since the whole program is trashed anyways.

So it's technically possible for "Rust UB" to time travel to before observable behavior performed in a non-Rust language in the face of xLTO.

We could say that the binding to a willreturn function with observable effects is incorrect, but I don't know how desirable that is. Is it perhaps possible to say that the willreturn IO is the one that time travels?

If you are doing xLTO you are deep in unspecified territory anyway. So if you do that you get some funny mix of the semantics of both languages and we don't guarantee ~anything about the details of that. It's not surprising that you are outside the Rust AM at that point.

The reason I ask is because I want to add metadata to my kernel's system call IDL that can be used for optimization, and part of that information I want to put "nonblocking convergent" on the IO routines if I end up changing them to be asynchronous by default. nonblocking would be correct, but under this, it seems like convergent would not be (or inferring willreturn from convergent), despite the fact that no synchronous termination can occur as a result of calling it

(And, of course, this means that there cannot be a willreturn attribute for asm separate from pure as mentioned in the reference PR)

Whatever system interprets the IDL just has to take into account that IO must be preserved even if there is UB later.

That would mean that at least llvm willreturn cannot be inferred from convergent (I also cannot find any practical use in a willreturn equivalent that does not allow the bidirectional motion of potentially-undefined operations accross the barrier).

Yeah that sounds right.

Though, actually, that poses a question.

let x = std::thread::spawn(|| println!("Foo"));
unreachable_unchecked();

Can the unreachable_unchecked moved past the thread::spawn (assuming a total thread::spawn)? Is this strictly a happens-before relationship?

In practice, no, since there's an opaque FFI call involved in spawning a thread.

Maybe what you actually meant to ask is "can I mark pthread_create as willreturn?". I don't know the implementation of that function so I don't know if it indeed will always return, or if there are cases where it may abort the process (e.g. on OOM or so). If it truly always return then I think it's fine to make it willreturn; creating a thread is not an observable behavior.

Yes, the question was "If we can assume spawning a thread on its own does not do any IO and does not terminate", can UB cross it even if the thread spawned might go and do IO/volatile, and that the order of AM Events (IO, volatile, UB) is fixed by happens-before order. Given that (in this case), I can add attributes that let compilers infer whatever true things they want about my system calls. That's probably more useful, especially given that the io system calls won't actually do IO directly, but will spawn a (kernel) thread to do the IO, and if you don't synchronizes-with the thread, you don't have a guarantee that the IO happened before the universe deletes itself and you hit the UB.

You are mixing terms that have no relation with each other. Happens-before and Sync-with are notions of the memory model. They only exist inside the AM. "Observable behavior order" is the only order that exists when looking at the AM from the outside, and the only order relevant here. One may be able to prove theorems relating the two, but a priori they are entirely unrelated.

How do we define the guaranteed inter-thread Observable behavior order without using happens-before?

I don't know which order you mean. This seems like a separate discussion -- it's not about time traveling at all, it's about how observable behavior relates to the concurrency memory model. Please take it to a new issue on Zulip thread.

Navigation Menu

Repository navigation

Does our UB have "time travel" semantics? #407

4 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Does our UB have "time travel" semantics? #407

Description

Activity

saethlin commented on May 27, 2023

digama0 commented on May 27, 2023

RalfJung commented on May 27, 2023

comex commented on May 27, 2023

deltragon commented on May 28, 2023

saethlin commented on May 28, 2023

Lokathor commented on May 28, 2023

JakobDegen commented on May 29, 2023

RalfJung commented on Apr 20, 2026

nikic commented on Apr 20, 2026

RalfJung commented on Apr 20, 2026

nikic commented on Apr 20, 2026

nikic commented on Apr 20, 2026

RalfJung commented on Apr 20, 2026

nikic commented on Apr 20, 2026

4 remaining items

RalfJung commented on Aug 8, 2026

chorman0773 commented on Aug 8, 2026

CAD97 commented on Aug 9, 2026

RalfJung commented on Aug 9, 2026

chorman0773 commented on Aug 10, 2026

chorman0773 commented on Aug 10, 2026

RalfJung commented on Aug 10, 2026

chorman0773 commented on Aug 11, 2026

RalfJung commented on Aug 12, 2026

chorman0773 commented on Aug 12, 2026

RalfJung commented on Aug 13, 2026

chorman0773 commented on Aug 14, 2026

RalfJung commented on Aug 14, 2026

chorman0773 commented on Aug 14, 2026

RalfJung commented on Aug 15, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions