logoalt Hacker News

jimaway123today at 2:55 PM4 repliesview on HN

Does anyone know exactly what is going on here to cause this difference? I am extremely puzzled that the "beginner friendly" code is not at some point in the compilation pipeline in EXACTLY the same representation as the non-"beginner friendly" code. I would imagine they'd be in the same form very early on, perhaps even at the point of generating an initial syntax tree. And once they take on the same form in the compilation pipeline, the resulting compiler output should be identical. So what is really going on here?


Replies

14113today at 3:11 PM

Representing code in a compiler is not precisely trivial, and the two statements are actually quite different from a compiler or AST perspective. Just looking at the first branch:

  *lwr = x; lwr++;
This could be be represented with something like this (and this is a very vague approximation of an AST):

  block
    statement (assignment)
      expression
        operator (dereference)
          variable
      expression
        variable
    statement
      expression
        operator (post-increment)
          variable
The second form, that looks this in the source:

  *lwr++ = x
might look like this in the AST:

  block
    statement (assignment)
      expression
        operator (post-increment)
          operator (dereference)
            variable
      expression
        variable
 
If these two ASTs are to take the same form in the compilation pipeline, there needs to be some kind of pass that transforms one into the other.

As for why the second form is faster (or rather, why the compiler can generate faster code): There is likely an optimisation pass somewhere in llvm that recognises a pattern that this fits into, which allows it to generate branchless instructions. For instance, in the second form, there is a pattern of:

  operator (post-increment)
    operator (dereference)
that might be recognised by a pass. In the former form, the two operators are far apart in the tree, so a pass would have to "look further" to match them up. A single pass likely won't do this, either for (compiler) performance reasons, or for correctness reasons.

Finding which pass that is can be non-trivial, as it's more than a matter of enabling individual passes until one works. It might be that an earlier pass does some code reshaping that allows the relevant pass to work. My suggestion would be to dump the llvm ir at the end, and find the rough pattern that you're looking for, then re-run the compilation with `-mllvm -print-after-all` to see what the IR looks like after each pass, and then manually "look back" until you can't see the pattern any more.

show 1 reply
rokobtoday at 3:18 PM

Have you considered what happens in the presence of multiple threads? I know aarch is weakly memory ordered but the assembly output by those two versions is quite different when multiple threads are involved. There must be a reason spreading the mutations across multiple lines causes the compiler to pessimize to the branch version.

Edit: not saying they are different just that it is harder for the compiler to see the safety of the transform when they are quite different.

show 1 reply
wimltoday at 3:54 PM

Yeah, that's an interesting question. I would expect the two to look the same once converted to SSA.

You can ask the compiler to dump its intermediate representations, so it might not be too hard to answer the question.

akoboldfryingtoday at 3:26 PM

Complete speculation, but it could be simply that clang only considers applying the branchless optimisation when the code inside the "if" block "looks like" a single instruction/statement -- and this "looks like" check might be done quite early, before "*x++ = y;" and "*x = y; x++;" are converted to the same thing.

Why restrict the optimisation unnecessarily like this? It's never the intention to artificially restrict optimisations, but they are difficult to test and debug as they can interact with other optimisations, and applying an optimisation too broadly leads to horrible correctness bugs. So if you cannot be certain that you understand all possible interactions now and in the future, it makes some sense to be conservative in applying them.