(I suspected it was this kind of thing, but I thought maybe it was something more generic.)
// 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);
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 (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.