4 ms·

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() fu

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.

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.