Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Well in this case it seems reasonable that they simply added a rule for the specific line:

    even = !even
and the line

    numberCompare++
resulting in

    even = (indvar & 1)
    numberCompare = indvar
You can then solve from the exit condition that number == numberCompare, which gives you the indvar which can then be substituted into 'even'.

I'm not saying it isn't magical, and certainly requires some symbolic solving, but it's doable.

Of course the real goal is to eventually get it to optimize

    while (number != 1) {
        if (number & 1)
            number = number * 3 + 1
        number >>= 1;
    }


> Of course the real goal is to eventually get it to optimize `while (number != 1) { ... }`

Valid C++ programs are guaranteed to be able to make forward progress [1].

So if `number` is a normal stack allocated integer (and not volatile, etc), then the infinite looping case is undefined behavior here.

So it would be a valid optimization to transform this to `number = 1;`.

(And indeed: https://godbolt.org/z/eodhfWe6h )

[1] https://en.cppreference.com/w/cpp/language/memory_model


Amazing, but crazy.

icc does not make this astounding leap in logic.


This is an example of a transformation that is probably more expensive in compile-time than it actually wins in runtime performance. Gcc has explicitly rejected this kind of optimization in the past for precisely that reason.

In general, compilers face an iron triangle of optimization: do you want a fast compiler, a small binary, or fast output? Optimizations that help all three are rare (especially ones that aren't already implemented in -O1), and even two of the three is often difficult to obtain.


> This is an example of a transformation that is probably more expensive in compile-time

Why? Reasoning that the value must be 1 after the loop is not even a loop optimization, just a simple consequence of the branching instruction. This leaves the loop but nothing it computes is used anymore so since C++ guarantees that it exits you can simply remove it.

The transformation as a whole might not be useful often, but having a constant for the induction variable after the loop and being able to delete useless loops will both have runtime wins.

> In general, compilers face an iron triangle of optimization: do you want a fast compiler, a small binary, or fast output?

I often wish compilers provided more options to just brute force a bit more performance out of release builds. You can manually tune many parameters but then you need to know a lot more about how the passes work than just saying --compile-for=5h (or something like that, doesn't need to have a hard time limit).


Note Gcc does do this, just at -O2 and above, whereas Clang does it on -O1 and above. Gcc also only does it on C++ code whereas Clang does it on both C and C++


Maybe LLVM should add a Collatz[0] optimization pass that would replace your loop with

    number = 1
for at least up to 64bit types?

[0] https://en.m.wikipedia.org/wiki/Collatz_conjecture




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: