3 ms·

The core simplification is due to LLVM's induction-detection step. Even after doing induction-based proofs in school, until reading this I had the sense that in

• benmmurphy 5y ago
  the induction step is pretty cool. it will remove the loop calculating the sum of an arithmetic progression and replace it with just multiplies/shifts/subtracts and adds.
• contravariant 5y ago
  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; }
  • missblit 5y ago
    > 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 https://godbolt.org/z/eodhfWe6h ) [1] https://en.cppreference.com/w/cpp/language/memory_model https://en.cppreference.com/w/cpp/language/memory_model
    • secondcoming 5y ago
      Amazing, but crazy. icc does not make this astounding leap in logic.
      • jcranmer 5y ago
        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.
        • matttb 5y ago
          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++
        • account42 5y ago
          > 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).
    • deleted 5y ago
      [deleted]
  • deleted 5y ago
    [deleted]
  • onedognight 5y ago
    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 https://en.m.wikipedia.org/wiki/Collatz_conjecture
• vnorilo 5y ago
  Well, basically it's about converting iteratively computated state to a function of iteration count. Consider indvar[n] = indvar[n-1] + k, indvar[0] = a. It follows that indvar[n] = a + n * k. This is the type of indvar canonicalization that can zap loops such as the one in the article. Suddenly the final state is just a function of the loop trip count. The return value is replaced with canonicalized indvar. That makes the loop itself dead (nobody observes any of its effects) and removed by subsequent dead code elimination pass. My example transforms addition to multiplication. Another common one is multiplication into power. That's close to what's going on in the article example: xor is just a multiplication of signed one-bit integers.
• geofft 5y ago
  This appears to be the source code: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp https://github.com/llvm/llvm-project/blob/main/llvm/lib/Tran... It's long, but it looks well-commented! Some Googling also finds https://llvm.org/devmtg/2009-10/ScalarEvolutionAndLoopOptimization.pdf https://llvm.org/devmtg/2009-10/ScalarEvolutionAndLoopOptimi... which looks relevant. I think "induction" here isn't exactly the sense of proofs by mathematical induction as you learn in school (as in proving something for all positive integers given a base case and a recursive case) - I think all they mean by it is "a loop, over a single integer." Quoting https://en.wikipedia.org/wiki/Induction_variable https://en.wikipedia.org/wiki/Induction_variable : > In computer science, an induction variable is a variable that gets increased or decreased by a fixed amount on every iteration of a loop or is a linear function of another induction variable. The description at https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/ive/ https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/ive/ makes it clearer: > An induction variable is any variable whose value can be represented as a function of: loop invariants; the number of loop iterations that have executed; and other induction variables. That is to say, the link to proofs-by-induction is that if you have a loop like "for (i = 0; i < 10; i++)", you can prove the statement "after N loops, i = N". Why? Because after 0 loops, i = 0 (the first part), and on each loop, i is one greater (the i++ part), and nothing else that happens in the loop changes i (which is what that post means by "loop invariants"). In other words, it's not that the compiler is detecting that the programmer is doing induction (the programmer is not, in fact the programmer is simply writing a for loop and not thinking about it), it's that the compiler is performing induction on the loop. So a simple case is if you have a loop like int i; for (i = 0; i < 10; i++) printf("Hi!\n"); printf("i = %d\n", i"); You can prove that at the end of the loop, i = 10, and you don't need to do actually increment i during each iteration to get there. And if you didn't have that printf (i.e., if the loop body was empty), you could optimize the loop out entirely and just print out 10. So it's not terribly magical that LLVM is able to turn while (number != numberCompare) { even = !even; numberCompare++; } into, in pseudocode, numberCompare = number; even = !!!...!!!even (numberCompare times); i.e., that it's able to get numberCompare out of the loop, to conclude that even in turn is only a function of numberCompare, and then that there's no loop left. What's more magical to me, I think, is that it's able to make sense of "run the ! operation numberCompare times" and turn that into "if (numberCompare % 2 == 1) even = !even". I don't think that's too surprising either - a compiler should know that, for booleans, !!foo can be simplified to foo. But repeatedly applying that rule across an abstract number of calls to !!, plus possibly one more, seems pretty clever. If I'm skimming the code right, that part of the simplification is a different optimization pass entirely. I don't know off hand where that's implemented. I'd be curious if someone can find it.
• jcranmer 5y ago
  Induction detection is relatively simple in LLVM IR. The first thing to remember is that the compiler doesn't work on the same source code that the human does; it works on a different representation. The canonical loop structure would look something like this: loop.preheader: ; This is the block that executes before the loop does. br label %loop.body; loop.body: %i = phi i32 [0, %loop.preheader], [%i.next, %loop.body] %val = phi i1 [0, %loop.preheader], [%val.next, %loop.body] %val.next = xor i1 %val, -1 %i.next = add i32 %i, 1 %cmp = icmp slt i32 %i, %N br i1 %cmp, %loop.exit, %loop.body loop.exit: ; After the loop is done Because of how phis work, in constructing this form, we immediately realize how to describe a value either in terms of its value in the first iteration (this is the value it takes coming from the preheader), or in terms solely of its value in the previous iteration. In other words, %val.next = f(%val) for some function f, which we can easily identify in the source code. Now, if we can compute the repeated composition of f easily, we can replace the recurrence in the loop with repeated composition. Repeated addition of the same value is multiplication, and repeated multiplication of the same value is exponentiation--that's two very easy examples to do so. We recognize that there is no use of the value except of its final occurrence, and so instead of doing the loop, we can generate the composition itself. Thus, after N iterations of the loop, we can conclude that %val.next = f^N(0), and if we can identify the loop iteration count (that's %N in this case), we can simply write out f^N instead of having to compute every individual value.
  • salawat 5y ago
    So if I'm understanding this, this only works for loops with a finite number of iterations knowable at compile time, right?
    • jcranmer 5y ago
      The number of iterations must be knowable, yes. It doesn't need to be known as a direct constant value, but it must be computable as a symbolic value as some kind (say, an argument to the function, maybe plus or minus a constant). I haven't looked at the exact criteria in this transformation, but it's very likely that there are also a couple of constraints on how precisely the loop is structured.