1

I want to know whether the CPU executes operations instructions during runtime in the same sequence obeying rules used in precedence to evaluate a value of an expression or not.

Mohamed Atef
  • 65
  • 5
  • The CPU does not have that concept - it is a language construct. The CPU executes instruction serially. – Weather Vane Oct 17 '20 at 18:08
  • @WeatherVane Does this mean rules of precedence can be somehow broken depending on the machine and the compiler implementation and optimization settings ? – Mohamed Atef Oct 17 '20 at 18:09
  • There is a big difference between what the CPU does, and how the compiler prepares instructions for it. The CPU does not care *which* language prepared the code. Of interest may be [Operator Precedence vs Order of Evaluation](https://stackoverflow.com/questions/5473107/operator-precedence-vs-order-of-evaluation) – Weather Vane Oct 17 '20 at 18:09
  • 1
    The compiler will make sure that the machine code follows the precedence rules if it matters. – klutt Oct 17 '20 at 18:10
  • @WeatherVane Thanks a lot , Shall I remove the question ? – Mohamed Atef Oct 17 '20 at 18:10
  • @MohamedAtef I think you could let the question stay – klutt Oct 17 '20 at 18:31
  • 1
    @klutt No one was born great :D – Mohamed Atef Oct 17 '20 at 18:46

1 Answers1

3

There are a few things to clarify. A C source code is "translated" into machine code by the compiler. There is never a 1 to 1 relationship between C code/instructions and machine code/instructions.

When compiling code the only thing that matters is the as if rule. As long as the observable behavior of the program is preserved, the compiler can generate instructions in any order.

Furthermore, on the hardware level, the CPU has its own mechanism for detecting instruction dependencies and can itself execute instructions out of order or in parallel (e.g. a single core has more than 1 ALU and FPU).

So, for a correct C program, the observable behavior of the program will be preserved. Instructions can be reordered, parts of code completely skipped and even algorithms completely changed underneath (e.g. modern compilers can transform recursive functions into non-recursive functions with loop constructs). But the observable behavior of the program will not change.

bolov
  • 72,283
  • 15
  • 145
  • 224
  • Also the order of evaluation is unrelated to the operator precedence, giving the compiler even more freedom. – HolyBlackCat Oct 17 '20 at 18:13
  • C++ has nothing to do with this question without a C++ tag. – Eric Postpischil Oct 17 '20 at 18:15
  • *execute instructions out of order* ... while preserving the *illusion* / appearance of serial execution, at least for a single thread, the HW version of the as-if rule. Usually that goes without saying, but perhaps worth mentioning here. See [How can we expect a program to complete in order?](//stackoverflow.com/q/64276544).and links in that answer, especially http://www.lighterra.com/papers/modernmicroprocessors/, and [this Q&A](https://softwareengineering.stackexchange.com/questions/349972/how-does-a-single-thread-run-on-multiple-cores/350024#350024) about OoO superscalar exec basics. – Peter Cordes Oct 17 '20 at 18:19
  • It would never happen in practice, but in principle, the compiler is free to change a bubble sort to a quick sort if it can guarantee that the observable behavior is equivalent. – klutt Oct 17 '20 at 18:36
  • @klutt: Other kinds of pattern-recognition do happen. clang recognizes `sum(i=0..n)` loops and compiles it to Gauss's closed-form with a multiply https://godbolt.org/z/T6KKeM. Some compilers are also able to recognize bit-count loops and compile to a `popcnt` instruction, or `(x>>n) | (x<<-n)` into a rotate. Some compilers "defeat" SPECint2006's `libquantum` benchmark by inverting a loop (so the memory access pattern doesn't suck). https://www.realworldtech.com/forum/?threadid=102569&curpostid=102580 – Peter Cordes Oct 17 '20 at 19:29