Are all functions in C/C++ assumed to return?

Question

I was reading this paper on undefined behaviour and one of the example "optimisations" looks highly dubious:

if (arg2 == 0)
    ereport(ERROR, (errcode(ERRCODE_DIVISION_BY_ZERO),
                    errmsg("division by zero")));
/* No overflow is possible */
PG_RETURN_INT32((int32) arg1 / arg2);

Figure 2: An unexpected optimization voids the division-by-zero check, in src/backend/utils/adt/int8.c of PostgreSQL. The call to ereport(ERROR, :::) will raise an exception.

Essentially, the compiler assumes that ereport will return, and removes the arg2 == 0 check since the presence of the division implies a non-zero denominator, i.e. arg2 != 0.

Is this a valid optimisation? Is the compiler free to assume that a function will always return?

EDIT: The whole thing depends on ereport, which is described thus:

   84 /*----------
   85  * New-style error reporting API: to be used in this way:
   86  *      ereport(ERROR,
   87  *              (errcode(ERRCODE_UNDEFINED_CURSOR),
   88  *               errmsg("portal \"%s\" not found", stmt->portalname),
   89  *               ... other errxxx() fields as needed ...));
   90  *
   91  * The error level is required, and so is a primary error message (errmsg
   92  * or errmsg_internal).  All else is optional.  errcode() defaults to
   93  * ERRCODE_INTERNAL_ERROR if elevel is ERROR or more, ERRCODE_WARNING
   94  * if elevel is WARNING, or ERRCODE_SUCCESSFUL_COMPLETION if elevel is
   95  * NOTICE or below.
   96  *
   97  * ereport_domain() allows a message domain to be specified, for modules that
   98  * wish to use a different message catalog from the backend's.  To avoid having
   99  * one copy of the default text domain per .o file, we define it as NULL here
  100  * and have errstart insert the default text domain.  Modules can either use
  101  * ereport_domain() directly, or preferably they can override the TEXTDOMAIN
  102  * macro.
  103  *
  104  * If elevel >= ERROR, the call will not return; we try to inform the compiler
  105  * of that via pg_unreachable().  However, no useful optimization effect is
  106  * obtained unless the compiler sees elevel as a compile-time constant, else
  107  * we're just adding code bloat.  So, if __builtin_constant_p is available,
  108  * use that to cause the second if() to vanish completely for non-constant
  109  * cases.  We avoid using a local variable because it's not necessary and
  110  * prevents gcc from making the unreachability deduction at optlevel -O0.
  111  *----------

Answer 1

Is the compiler free to assume that a function will always return?

It is not legal in C or C++ for a compiler to optimize on that basis, unless it somehow specifically knows that ereport returns (for example by inlining it and inspecting the code).

ereport depends on at least one #define and on the values passed in, so I can't be sure, but it certainly looks to be designed to conditionally not return (and it calls an extern function errstart that, as far as the compiler knows, may or may not return). So if the compiler really is assuming that it always returns then either the compiler is wrong, or the implementation of ereport is wrong, or I've completely misunderstood it.

The paper says,

However, the programmer failed to inform the compiler that the call to ereport(ERROR, ::: ) does not return.

I don't believe that the programmer has any such obligation, unless perhaps there's some non-standard extension in effect when compiling this particular code, that enables an optimization that's documented to break valid code under certain conditions.

Unfortunately it is rather difficult to prove the code transformation is incorrect by citing the standard, since I can't quote anything to show that there isn't, tucked away somewhere in pages 700-900, a little clause that says "oh, by the way, all functions must return". I haven't actually read every line of the standard, but such a clause would be absurd: functions need to be allowed to call abort() or exit() or longjmp(). In C++ they can also throw exceptions. And they need to be allowed to do this conditionally -- the attribute noreturn means that the function never returns, not that it might not return, and its absence proves nothing about whether the function returns or not. My experience of both standards is that they aren't (that) absurd.

Optimizations are not allowed to break valid programs, they're constrained by the "as-if" rule that observable behaviour is preserved. If ereport doesn't return then the "optimization" changes the observable behaviour of the program (from doing whatever ereport does instead of returning, to having undefined behaviour due to the division by zero). Hence it is forbidden.

There's more information on this particular issue here:

http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=616180

It mentions a GCC bug report http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29968 that was (rightly IMO) rejected, but if ereport doesn't return then the PostGreSQL issue is not the same as that rejected GCC bug report.

In the debian bug description is the following:

The gcc guys are full of it. The issue that is relevant here is the C standard's definition of sequence points, and in particular the requirement that visible side effects of a later statement cannot happen before the execution of an earlier function call. The last time I pestered them about this, I got some lame claim that a SIGFPE wasn't a side effect within the definitions of the spec. At that point useful discussion stopped, because it's impossible to negotiate with someone who's willing to claim that.

In point of fact, if a later statement has UB then it is explicitly stated in the standard that the whole program has UB. Ben has the citation in his answer. It is not the case (as this person seems to think) that all visible side effects must occur up to the last sequence point before the UB. UB permits inventing a time machine (and more prosaically, it permits out of order execution that assumes everything executed has defined behaviour). The gcc guys are not full of it if that's all they say.

A SIGFPE would be a visible side effect if the compiler chooses to guarantee and document (as an extension to the standard) that it occurs, but if it's just the result of UB then it is not. Compare for example the -fwrapv option to GCC, which changes integer overflow from UB (what the standard says) to wrap-around (which the compiler guarantees, only if you specify the option). On MIPS, gcc has an option -mcheck-zero-division, which looks like it does define behaviour on division by zero, but I've never used it.

It's possible that the authors of the paper noticed the wrongness of that complaint against GCC, and the thought that one of the PostGreSQL authors was wrong in this way influenced them when they put the snigger quotes into:

We found seven similar issues in PostgreSQL, which were noted as “GCC bugs” in source code comments

But a function not returning is very different from a function returning after some side effects. If it doesn't return, the statement that would have UB is not executed within the definition of the C (or C++) abstract machine in the standard. Unreached statements aren't executed: I hope this isn't contentious. So if the "gcc guys" were to claim that UB from unreached statements renders the whole program undefined, then they'd be full of it. I don't know that they have claimed that, and at the end of the Debian report there's a suggestion that the issue might have gone away by GCC 4.4. If so then perhaps PostGreSQL indeed had encountered an eventually-acknowledged bug, not (as the author of the paper you link to thinks) a valid optimization or (as the person who says the gcc guys are full of it thinks) a misinterpretation of the standard by GCC's authors.

Answer 2

I think the answer is found, at least for C++, in section 1.9p5

A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible executions of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).

In fact, the macro expands to a call to errstart which will return (ERROR >= ERROR), obviously true. That triggers a call to errfinish which calls proc_exit which runs some registered cleanup and then the Standard runtime function exit. So there is no possible execution that contains a divide-by-zero. However, the compiler logic testing this must have gotten it wrong. Or perhaps an earlier version of the code failed to properly exit.

Answer 3

It seems to me that unless the compiler can prove that ereport() doesn't call exit() or abort() or some other mechanism for program termination then this optimization is invalid. The language standard mentions several mechanisms for termination, and even defines the 'normal' program termination via returning from main() in terms of the exit() function.

Not to mention that program termination isn't necessary to avoid the division expression. for (;;) {} is perfectly valid C.