3 ms·

Indeed, Clang/LLVM did a stellar job here. It'd be interesting to know how (in part to understand what situations can one expect this sort of thing to happen; f

by _yosefk 10y ago

Indeed, Clang/LLVM did a stellar job here. It'd be interesting to know how (in part to understand what situations can one expect this sort of thing to happen; for instance, I'd be surprised if IEEE floating point emulation code would be compiled to a hardware floating point instruction - though perhaps I underestimate the optimization passes at work here!)

TorKlingberg 10y ago
I bet there is a specific optimization that recognizes common patterns for counting the number of set bits and replaces it with popcntq. There is no popcnt() function built into C, so everyone who needs it uses one of a few common implementations.
- ninjabeans 10y ago
  This sounds the most plausible.
- psuter 10y ago
  Indeed: https://github.com/llvm-mirror/llvm/blob/ae889d36724efb174e8cc05d26e655c4c4ab8867/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L1073-L1077 https://github.com/llvm-mirror/llvm/blob/ae889d36724efb174e8...
  - _yosefk 10y ago
    LoopIdiomRecognize::recognizePopcount? Then I think it's more about "the surprising ability of modern compilers to recognize popcount" than general "cleverness." (I suspected it was this kind of thing, but I thought maybe it was something more generic.)
    - acqq 10y ago
      Yes most other loops that produce the same result wouldn't be recognized, just this very specific, note the steps: // step 1: Check if the loop-back branch is in desirable form. // step 2: detect instructions corresponding to "x2 = x1 & (x1 - 1)" // step 3: Check the recurrence of variable X // step 4: Find the instruction which count the population: cnt2 = cnt1 + 1 It's very, very specific. But they allow that the loop has something more, see the resulting transformation at the end: // After this step, this loop (conceptually) would look like following: // newcnt = __builtin_ctpop(x); // t = newcnt; // if (x) // do { cnt++; x &= x-1; t--) } while (t > 0); This can be later potentially optimized more, in the given simplest case the rest is removed by the later optimization steps.
- pcwalton 10y ago
  Yes. Many compilers, including LLVM, have an "idiom recognizer" (in LLVM parlance) that detects memsets, memcpys, population counts, etc. and turns them into calls to the optimized implementations.
acqq 10y ago
> It'd be interesting to know how Do you mean how this things are implemented in general or how come that this particular function was reduced to one instruction? The answer to later wrote gjm11 here: https://news.ycombinator.com/item?id=11764800 https://news.ycombinator.com/item?id=11764800 (it was to make LLVM good at some benchmark!) The answer to former is: once the sorce code ins transformed to some intermediary form, a lot of optimizations simply look for the "best match" for different patterns and then replace the matched intermediary form sequence with the replacement sequence. Once you have an infrastructure in your compilers, it's typically not so hard to add one more "replace this with that" to get this result to win the benchmark.

by _yosefk 10y ago

TorKlingberg 10y ago

I bet there is a specific optimization that recognizes common patterns for counting the number of set bits and replaces it with popcntq. There is no popcnt() function built into C, so everyone who needs it uses one of a few common implementations.

ninjabeans 10y ago
This sounds the most plausible.
psuter 10y ago
Indeed: https://github.com/llvm-mirror/llvm/blob/ae889d36724efb174e8cc05d26e655c4c4ab8867/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L1073-L1077 https://github.com/llvm-mirror/llvm/blob/ae889d36724efb174e8...
- _yosefk 10y ago
  LoopIdiomRecognize::recognizePopcount? Then I think it's more about "the surprising ability of modern compilers to recognize popcount" than general "cleverness." (I suspected it was this kind of thing, but I thought maybe it was something more generic.)
  - acqq 10y ago
    Yes most other loops that produce the same result wouldn't be recognized, just this very specific, note the steps: // step 1: Check if the loop-back branch is in desirable form. // step 2: detect instructions corresponding to "x2 = x1 & (x1 - 1)" // step 3: Check the recurrence of variable X // step 4: Find the instruction which count the population: cnt2 = cnt1 + 1 It's very, very specific. But they allow that the loop has something more, see the resulting transformation at the end: // After this step, this loop (conceptually) would look like following: // newcnt = __builtin_ctpop(x); // t = newcnt; // if (x) // do { cnt++; x &= x-1; t--) } while (t > 0); This can be later potentially optimized more, in the given simplest case the rest is removed by the later optimization steps.
pcwalton 10y ago
Yes. Many compilers, including LLVM, have an "idiom recognizer" (in LLVM parlance) that detects memsets, memcpys, population counts, etc. and turns them into calls to the optimized implementations.

acqq 10y ago

> It'd be interesting to know how Do you mean how this things are implemented in general or how come that this particular function was reduced to one instruction? The answer to later wrote gjm11 here: https://news.ycombinator.com/item?id=11764800 https://news.ycombinator.com/item?id=11764800 (it was to make LLVM good at some benchmark!) The answer to former is: once the sorce code ins transformed to some intermediary form, a lot of optimizations simply look for the "best match" for different patterns and then replace the matched intermediary form sequence with the replacement sequence. Once you have an infrastructure in your compilers, it's typically not so hard to add one more "replace this with that" to get this result to win the benchmark.