Infinite loop vs infinite recursion. Are both undefined?

Question

Infinite loops without side effect are undefined behaviour. See here for the example from cppreference. Much simpler example:

int foo() {
    while(true) {}
    return 42;
}

Now consider the almost equivalent

int bar() {
    if (true) return bar();
    return 42;
}

Does this invoke undefined behaviour as well?

Or phrased differently: What class of error is infinite recursion according to the language?

PS: note that I am aware of the implications at runtime: The loop in principle could run forever, while the recursion will eventually result in a stackoverflow. Though I am mainly interested in what the compiler does to them. Maybe a quite academic question...

"The loop in principle could run forever, while the recursion will eventually result in a stackoverflow." – Actually, since it is UB it could do anything. And it doesn't have to recurse in the first place on actual hardware because of the as-if rule. In particular, if optimizations are enabled, the compiler is likely to replace your recursive example with effectively a loop (tail call optimization) even if it has side effects. — Arne Vogel, Apr 18 '19 at 07:33
@ArneVogel Yes the code is contrived but in practice most C++ code has no objects with non trivial dtors and cannot be tail optimized most of the time — curiousguy, Apr 18 '19 at 08:27
@ArneVogel read "in principle" as "what would happen if it wasnt ub" — 463035818_is_not_an_ai, Apr 18 '19 at 11:16
@user463035818: I'd say if it wasn't UB I'd say an implementation should be expected to refrain from performing any action which wouldn't occur if the loop were omitted, or any action which would have a non-hoistable data dependency on anything in the loop, but may perform any actions which would occur if the loop were omitted, unless or until it encounters a non-hoistable data dependency. — supercat, Apr 23 '19 at 21:09

Rakete1111 · Accepted Answer · 2019-04-17T19:32:47.240

11

No there is no difference. [basic.progress]p1:

The implementation may assume that any thread will eventually do one of the following:

terminate,

make a call to a library I/O function,

perform an access through a volatile glvalue, or

perform a synchronization operation or an atomic operation.

It doesn't matter how you have your infinite loop; if it doesn't do any of the points above, you get UB. Including the following:

int bar(int cond) {
    if (cond == 42) bar(cond);
    return 42;
}
bar(some_user_input);

The compiler is allowed to assume that some_user_input will never be 42.

edited Apr 17 '19 at 19:32

answered Apr 17 '19 at 19:29

Rakete1111

47,013
16
123
162

ah now I remember that this is the actual phrasing, I didnt find it anymore (i mean somewhere else than in the standard itself). cppreference is a bit short on ub – 463035818_is_not_an_ai Apr 17 '19 at 19:32
Where is it defined UB? Doesn't the standard states about loop removal? – Jean-Baptiste Yunès Apr 17 '19 at 19:41
1

@Jean-BaptisteYunès It's in the "may assume" part. If your program doesn't do that you're violating the compiler's assumption which is the same thing as UB. It does but that's just an example of what could happen. – Rakete1111 Apr 17 '19 at 19:43
1

i am a bit confused. Naively put: Compiler knows that my stacksize is limited, infinite recursion will result in stack overflow, thread will terminate, all fine. Where am I wrong? – 463035818_is_not_an_ai Apr 17 '19 at 19:46
3

@user463035818 In the C++ abstract machine there is no stack size. That's one of those implementation defined limits, but it doesn't count as a program terminating if that makes sense. – Rakete1111 Apr 17 '19 at 19:50
1

@Rakete1111 you want to tell me stackoverflow isnt real ? :P Seriously, what is a stackoverflow in terms of the c++ language? It simply does not exist and therefore is undefined by definition? – 463035818_is_not_an_ai Apr 17 '19 at 20:22
1

@user463035818 Well yeah, it is not something the language is concerned about. It's not necessarily undefined though, it's just that that concept doesn't exist in the abstract machine. – Rakete1111 Apr 17 '19 at 20:23
Is there already an answer to why a compiler may assume that infinite loop is not a busy waiting for a signal to arrive? – Language Lawyer Apr 17 '19 at 21:46
1

@LanguageLawyer Well if you want this waiting you would mark the variable denoting that with `volatile`, which would fall into the conditions above. You'd do that anyway so that the compiler doesn't optimize it away in some other context. – Rakete1111 Apr 17 '19 at 21:49
@Rakete1111 it is not an answer. – Language Lawyer Apr 18 '19 at 14:33
@LanguageLawyer: Given `func1(); func2();` any portions of `func2();` which may be affected by actions performed in `func1()` must behave as though executed after those actions, but any actions in `func1()` and `func2()` that do not interact with each other and have no observable side-effects may be performed in any order. I think the Standard's language about assuming that loops terminate is intended to say that a failure of `func1()` to terminate would not in and of itself be a "side-effect" that must be sequenced prior to `func2()`. – supercat May 09 '19 at 19:16

supercat · Answer 2 · 2019-04-23T20:46:59.653

In most real-world situations, an invitation to assume something will happen implies that one is not obligated to take any special measures to allow for the possibility that it doesn't, but is not a license to behave in arbitrary fashion if one discovers that the event in question won't occur.

Under fashionable interpretations of the C Standard, however, there is no reason to expect that implementations will refrain from totally nonsensical fashion if any assumption the Standard would invite them to make proves incorrect.

I don't think the authors of the Standard intended that C compilers would use complicated inference engines which cascade assumptions to the point that a compiler given e.g.

if (x > 1000) foo(x);
while ( x <= 1000)
  somethingWithNoSideEffectsThatCantAffectX();

would conclude that foo should be executed unconditionally regardless of the value of x. More likely, they intended that a compiler given something like:

volatile int yy;
void test(int x, int *restrict arr)
{
  int y;
  do
    x=arr[x];
  while(x & 1);
  y=yy;
  if (y)
    printf("%d\n",x);
}

would be allowed to use the fact that the final value of x may or may not be needed to rearrange the code to be more efficient in the cases where it isn't (by skipping its calculation altogether). Essentially, the fact that a piece of code takes time to execute--even if infinite--should not be considered a side-effect in and of itself, and if a compiler can prove that a piece of code cannot execute any side-effects that would be visible before it reaches a certain place, it need not wait for that piece of code to finish before executing code at that place.

Unfortunately, the authors of the Standard rely upon compiler writers to recognize what kinds of actions may be usefully taken on the basis of certain assumptions, while compiler writers assume that any possible inference they can draw should be presumed useful.

Infinite loop vs infinite recursion. Are both undefined?

2 Answers2

Linked