C Evaluation

[robve]

(07-15-2022 11:20 PM)KeithB Wrote:  If you have ever worked with lex and yacc (Yet Another Compiler Compiler) you would understand why evaluation order is not guaranteed. The "natural" way to use yacc puts the operands and operators on a stack and when you "pop" them, they come out in reverse order.

To nit a bit:

Runtime evaluation order in C does not depend on a compiler's "front end" (parsing and semantic analysts). LALR (lookahead LR) parsers Yacc and Bison parse C source code left to right (from source code begin to end, hence LR parsing) and build the parse tree bottom-up towards the root, thereby performing a "right most derivation" (hence LR) to produce intermediate (IR) code. The compiler's "back end" then optimizes and translates the IR to the target representation (assembly, machine code, byte code, stack machine, ...). Because C allows aggressive optimization of the IR and the target representation, operands to operators and arguments passed to functions may be evaluated in an unspecified order to facilitate those optimizations, unlike in Java for example. Consider f(++k)+a[k] which exhibits undefined behavior in C. This is on purpose, because we may want to pre-fetch a[k] before the function call f(++k) to hide the latency of the memory fetch that can take many cycles to complete, even with fast L1/L2 caches. Once f(++k) is done, a[k] is ready to be consumed by the CPU so to speak. Of course, it is still possible to call f(k+1) instead of f(++k) to preserve k in a[k] and then we can increment ++k, but that's not the point. Early compilers were just much simpler and didn't have to bother with that. Without going into too much detail, there is another reason why C (and other PL) typically evaluate function arguments in reverse order (but not always as we know!), which has to do with the way subroutine frames are populated in the generated target code.

- Rob