In C99, is f()+g() undefined or merely unspecified?

Question

I used to think that in C99, even if the side-effects of functions f and g interfered, and although the expression f() + g() does not contain a sequence point, f and g would contain some, so the behavior would be unspecified: either f() would be called before g(), or g() before f().

I am no longer so sure. What if the compiler inlines the functions (which the compiler may decide to do even if the functions are not declared inline) and then reorders instructions? May one get a result different of the above two? In other words, is this undefined behavior?

This is not because I intend to write this kind of thing, this is to choose the best label for such a statement in a static analyzer.

Gunpowder

6.5.2.2 paragraph 12 contains the example (*pf[f1()]) (f2(), f3() + f4()). If only it said that the side-effects in f3 and f4 interfered, I would have my answer, but it focuses more on the fact that all side-effects are finished before (*pf[f1()]) is called. – Gunpowder

Does it really matter which? Either one means that you can't rely on an behavior known to work on FooOS with BarCC version X.Y.ZpW if any of Foo, Bar, X, Y, Z, or W change. The best you can hope for is consistency as long as you stick to the one rigidly specified environment. – Atabrine

@dmckee Call it pedantry if you like, but in a context where you have to emit some false alarms for widely accepted theoretical reasons, we like to distinguish between "if this is a true alarm, this might do anything at all" of "if this is a true alarm, this may have two distinct well-identified behaviors". I would expand on this but the comment limit won't allow me to. – Gunpowder

@Pascal: I see the difference. Actually undefined behavior is an immediate and unconditional show stopper and merely unspecified only takes you to NastilyUnsupportableLand. But NastilyUnsupportableLand is, well, nasty, so I can only see justifying it in the most extreme cases. – Atabrine

@dmckee Well, it was long, so I explained it in an answer below. – Gunpowder

@dmckee: The difference is significant if both functions perform a sequence of operations like "1. save global state; 2. configure global state for own use; 3. use global state; 4. restore global state;". If each function, once started, will execute in its entirety before the other begins, it won't matter which one executes first. If, however, both functions do the first two steps, and then both functions to the second two steps, things won't work. – Extinct

Answer 1

The expression f() + g() contains a minimum of 4 sequence points; one before the call to f() (after all zero of its arguments are evaluated); one before the call to g() (after all zero of its arguments are evaluated); one as the call to f() returns; and one as the call to g() returns. Further, the two sequence points associated with f() occur either both before or both after the two sequence points associated with g(). What you cannot tell is which order the sequence points will occur in - whether the f-points occur before the g-points or vice versa.

Even if the compiler inlined the code, it has to obey the 'as if' rule - the code must behave the same as if the functions were not interleaved. That limits the scope for damage (assuming a non-buggy compiler).

So the sequence in which f() and g() are evaluated is unspecified. But everything else is pretty clean.

---

In a comment, supercat asks:

I would expect function calls in the source code remain as sequence points even if a compiler decides on its own to inline them. Does that remain true of functions declared "inline", or does the compiler get extra latitude?

I believe the 'as if' rule applies and the compiler doesn't get extra latitude to omit sequence points because it uses an explicitly inline function. The main reason for thinking that (being too lazy to look for the exact wording in the standard) is that the compiler is allowed to inline or not inline a function according to its rules, but the behaviour of the program should not change (except for performance).

Also, what can be said about the sequencing of (a(),b()) + (c(),d())? Is it possible for c() and/or d() to execute between a() and b(), or for a() or b() to execute between c() and d()?

• Clearly, a executes before b, and c executes before d. I believe it is possible for c and d to be executed between a and b, though it is fairly unlikely that it the compiler would generate the code like that; similarly, a and b could be executed between c and d. And although I used 'and' in 'c and d', that could be an 'or' - that is, any of these sequences of operation meet the constraints:

  • Definitely allowed
  • abcd
  • cdab
  • Possibly allowed (preserves a ≺ b, c ≺ d ordering)
  • acbd
  • acdb
  • cadb
  • cabd

   
  I believe that covers all possible sequences. See also the chat between Jonathan Leffler and AnArrayOfFunctions — the gist is that AnArrayOfFunctions does not think the 'possibly allowed' sequences are allowed at all.

If such a thing would be possible, that would imply a significant difference between inline functions and macros.

There are significant differences between inline functions and macros, but I don't think the ordering in the expression is one of them. That is, any of the functions a, b, c or d could be replaced with a macro, and the same sequencing of the macro bodies could occur. The primary difference, it seems to me, is that with the inline functions, there are guaranteed sequence points at the function calls - as outlined in the main answer - as well as at the comma operators. With macros, you lose the function-related sequence points. (So, maybe that is a significant difference...) However, in so many ways the issue is rather like questions about how many angels can dance on the head of a pin - it isn't very important in practice. If someone presented me with the expression (a(),b()) + (c(),d()) in a code review, I would tell them to rewrite the code to make it clear:

a();
c();
x = b() + d();

And that assumes there is no critical sequencing requirement on b() vs d().

Superorder

I would expect function calls in the source code remain as sequence points even if a compiler decides on its own to inline them. Does that remain true of functions declared "inline", or does the compiler get extra latitude? Also, what can be said about the sequencing of (a(),b()) + (c(),d())? Is it possible for c() and/or d() to execute between a() and b(), or for a() or b() to execute between c() and d()? If such a thing would be possible, that would imply a significant difference between inline functions and macros. – Extinct

@supercat: As Jonathan says, an execution order like acdb or cabd is possible whether a() etc. are inline functions or macros. An example of the difference is that if x is a global variable and we have #define a() x++ and #define c() x++, then (a(),b()) + (c(),d()) will cause UB: x could wind up as anything at all, but most plausibly will be incremented either once or twice depending on how the read-modify-write instructions are interleaved; while if we have void a() { x++; } void c() { x++; } (optionally inline), there's no UB and x will definitely be incremented twice. – Wacky

@j_random_hacker: Certainly if a() and c() are macros their expansion does not represent a sequence point or sequencing relation. My question was about functions declared inline. If a compiler decides to inline a function which is not declared inline, I would expect that it's required to preserve the semantics of an ordinary function call. If a function is declared inline, does that relieve any semantic requirements? – Extinct

@supercat: Just looked in the (now old) C++ standard, and sure enough 1.9/17 explicitly says "When calling a function, (whether or not the function is inline), there is a sequence point after the evaluation of all function arguments...". Not sure about C99 -- I seem to recall it has slightly different semantics for inline -- but it would make sense to behave the same way in this respect. – Wacky

Hmm I'm fairly certain that b() must execute strictly after a() (and d() after c()) unless the compiler have some additional information to apply the "as if" rule. Why anyone here thought that the comma operator semantics can be ignored (unless of-course as part of the "as if" rule)? – Sapphera

(But to apply the "as if" rule I'm pretty sure we must have information about the the functions side-effects (and thus have their definitions included in the current TU).) – Sapphera

@AnArrayOfFunctions: You've chosen to stipulate 'b() after a()' whereas the main answer stipulates 'a() before b()', but that amounts to the same thing, does it not? So no-one is ignoring the comma operator semantics. The notation is easy to misread; I had to look several times before re-realizing that I was correct in the answer. – Superorder

@AnArrayOfFunctions: je ne comprend pas? I don't understand the problem that you're asking about or commenting upon. Please quote the wording in my answer that you think is erroneous — I don't see the problem you think you're seeing. – Superorder

@JonathanLeffler "any of these sequences of operation meet the constraints:" - then there is a list which allows for example (a(),b()) to be executed after c() and before d() which may not confront the "as if" rule. – Sapphera

Because maybe (a(), b()) modifies the same object that c() modifies and d() uses. And in that case unless (a(), b()) store the same value in that object the side effects of the program may be different. – Sapphera

That point is covered in the answer. I believe it is possible for c and d to be executed between a and b, though it is fairly unlikely that it the compiler would generate the code like that; similarly, a and b could be executed between c and d. If you prefer to disagree with 'it is possible', that is your right — if you can quote chapter and verse of the standard that stipulates that it is impossible, that would be helpful. – Superorder

You have wrote that "any of these sequences of operation meet the constraints" without including the function definitions and mentioning the "as if rule" which is a false statement. – Sapphera

Let us continue this discussion in chat. – Superorder

Answer 2

See Annex C for a list of sequence points. Function calls (the point between all arguments being evaluated and execution passing to the function) are sequence points. As you've said, it's unspecified which function gets called first, but each of the two functions will either see all the side effects of the other, or none at all.

Butternut

Answer 3

@dmckee

Well, that won't fit inside a comment, but here is the thing:

First, you write a correct static analyzer. "Correct", in this context, means that it won't remain silent if there is anything dubious about the analyzed code, so at this stage you merrily conflate undefined and unspecified behaviors. They are both bad and unacceptable in critical code, and you warn, rightly, for both of them.

But you only want to warn once for one possible bug, and also you know that your analyzer will be judged in benchmarks in terms of "precision" and "recall" when compared to other, possibly not correct, analyzers, so you mustn't warn twice about one same problem... Be it a true or false alarm (you don't know which. you never know which, otherwise it would be too easy).

So you want to emit a single warning for

*p = x;
y = *p;

Because as soon as p is a valid pointer at the first statement, it can be assumed to be a valid pointer at the second statement. And not inferring this will lower your score on the precision metric.

So you teach your analyzer to assume that p is a valid pointer as soon as you have warned about it the first time in the above code, so that you don't warn about it the second time. More generally, you learn to ignore values (and execution paths) that correspond to something you have already warned about.

Then, you realize that not many people are writing critical code, so you make other, lightweight analyses for the rest of them, based on the results of the initial, correct analysis. Say, a C program slicer.

And you tell "them": You don't have to check about all the (possibly, often false) alarms emitted by the first analysis. The sliced program behaves the same as the original program as long as none of them is triggered. The slicer produces programs that are equivalent for the slicing criterion for "defined" execution paths.

And users merrily ignore the alarms and use the slicer.

And then you realize that perhaps there is a misunderstanding. For instance, most implementations of memmove (you know, the one that handles overlapping blocks) actually invoke unspecified behavior when called with pointers that do not point to the same block (comparing addresses that do not point to the same block). And your analyzer ignore both execution paths, because both are unspecified, but in reality both execution paths are equivalent and all is well.

So there shouldn't be any misunderstanding on the meaning of alarms, and if one intends to ignore them, only unmistakable undefined behaviors should be excluded.

And this is how you end up with a strong interest in distinguishing between unspecified behavior and undefined behavior. No-one can blame you for ignoring the latter. But programmers will write the former without even thinking about it, and when you say that your slicer excludes "wrong behaviors" of the program, they will not feel as they are concerned.

And this is the end of a story that definitely did not fit in a comment. Apologies to anyone who read that far.

Gunpowder

As someone who writes critical code, such an analyzer would provide more benefit if it told me about the full trace of *p's invalidity -- that is, once you know it's wrong, don't ignore the path, make it all the same problem and tell me where it starts and the vastness of it's error inducement. – Oglesby

@Mark This involves a whole set of other (specifically, backwards) techniques, I'm afraid: "What inputs can lead p to be invalid here?". "All in good time" is the only answer I'm afraid I can provide at the moment. – Gunpowder

Understandably this is difficult, but what I'm suggesting is that you should continue to propagate the error forwards, and mark it as the same error, rather than a new one or not at all. – Oglesby

BTW, have you heard of sixgill or SATURN? – Oglesby

I didn't know about these tools, although the names behind them are familiar. The design space for such verification tools is very large. It's always good to hear about different approaches. – Gunpowder

@Pascal: Thank you for taking the time to write this. I am clearly playing out of my league here. Obviously a very hard problem. I've read your whole comment twice and am starting to see what you're getting at. For what little it is worth, I withdraw my objection above. – Atabrine

@Pascal is there a benchmark set of programs you use to test your framework? (it sounds like the community might be small enough that there's a shared set...) – Oglesby

@Mark the tools are so different that the only way is an open "exposition" such as organized by NIST . This seems like good fun. rgaucher.info/post/2008/02/05/… . Otherwise, there is se.cs.toronto.edu/index.php/Verisec_Suite , but we have verified that at least one case was not a bug and another had a bug in addition to the one you were supposed to find. – Gunpowder

Perhaps what would be most helpful would be a tool which could provide a hierarchical list of warnings? So that the first warning about "p" would start out being visible, but clicking on it would show the rest? I wonder if any tools do that? Also, when you say memmove is "unspecified", does that mean that unrelated pointers may arbitrarily compare greater or less than each other in a way which isn't guaranteed to form a consistent ranking, but such comparisons will not, in and of themselves, cause nasal demons? – Extinct

@Extinct Most static analysis tools try to offer warning hierarchies, and options to show only the warnings you are interested in, but none of them want the imprecision from one dubious construct to pollute the rest of the analysis, so there are always difficult choices. Regarding my use of "unspecified", it turned out after closer scrutiny that I was wrong: simply comparing pointers with <, > can be undefined. There were a lot of good answers to my other question on that topic: #4023820 – Gunpowder

I know the tools offer options to turn on and off various warnings. I was curious whether any of them offer warnings in a format which can be viewed like a tree control or collapsible list (perhaps including an option for a scripted HTML format) so that one could see something like "p is used by 'foo' 19 times where it might be null", and clicking on the message would give a list of what those 19 times were, without having to rerun the tool. – Extinct

@PascalCuoq: The fact that the Standard allows the < and > operators to behave in arbitrary fashion when fed unrelated pointers doesn't imply that the authors thought compilers should be deemed suitable for systems programming without the ability to compare pointers in all cases the hardware could easily handle. If people didn't expect the Standard to define everything necessary to make an implementation suitable for all purposes, it wouldn't often matter if the Standard failed to mandate a commonplace behavior upon which programmers rely, since implementations would support it anyway. – Extinct