What are the ways compilers recognize complex patterns?

Question

This answer is an example of a compiler recognizing that a complex expression is equivalent to a single operation:

uint8_t pcnt64(uint64_t n) {
    n = n - ((n >> 1) & 0x5555555555555555ULL);
    n = (n & 0x3333333333333333ULL) + (n >> 2 & 0x3333333333333333ULL);
    n = (n + (n >> 4)) & 0xF0F0F0F0F0F0F0FULL;
    return (n * 0x0101010101010101ULL) >> 56;
}

Gets compiled into

popcnt64:
        xor     eax, eax
        popcnt  rax, rdi
        ret

The compiler knows that all of that code, constants and all, comes down to just counting the number of set bits in a number.

But how would a compiler be able to figure that out, besides hardcoding numerous possible implementations and then comparing until there is a match? Do compilers have a way of 'simulating' the possible inputs and outputs of a function, and determining that they will match the result of a specific assembly instruction? Can compilers reduce any function into some 'canonical form' and then compare with a 'canonical form' of the candidate instruction?

Answer 1

The boring answer: it really is just hardcoded

The answer to the general question of “how do compilers recognize optimizable patterns?” would be large enough to fill a book. Certainly, there are lots of techniques that could be used to apply this type of optimization. However, in this particular case, the answer is sadly rather boring: the compiler really does look for a more-or-less hardcoded pattern.

In LLVM, this optimization was added in 2019, and the given rationale was that this particular implementation of popcount is a particularly common idiom. I haven’t personally investigated the extent to which this is true, but the author cites Hacker’s Delight as the source of the pattern they’ve chosen to recognize. The optimization is performed as part of LLVM’s aggressive-instcombine pass, which “combines expression patterns to form expressions with fewer, simple instructions.” Essentially, it is a slightly more sophisticated variation on peephole optimization.

In the code, the appropriately-named tryToRecognizePopcount function implements the detection, and it is not particularly sophisticated. In theory, it could do something much fancier, like abstractly interpreting bitwise operations to somehow determine whether the end result implements popcount. However, the actual implementation does not do that: it looks for a sequence of instructions that perform a very particular set of bitwise operations, including the relevant hardcoded constants, and if it doesn’t find the implementation it expects, nothing interesting happens.

Although the approach is quite naïve, it’s worth keeping in mind that this analysis runs after LLVM has already lowered the code to its internal, SSA representation (which inherently involves some normalization), and the code has already been “cleaned up” by other simplifying optimization passes. This means that, though the pattern being scanned for is fairly simple, there is good reason to believe minor variations in the way it’s written in the source code will all be normalized to the same basic shape, as long as they are fundamentally the same algorithm. This increases the likelihood that the optimization will fire.

I did not take the time to investigate how GCC performs this optimization, but kouta-kun’s answer explains that it takes essentially the same approach.

Why take this approach?

Optimizing compilers must consider many tradeoffs when choosing what optimizations to perform and how to implement them. In theory, a compiler could choose to implement a set of extremely sophisticated algorithms to squeeze every last drop of performance from a program, but this is not done in practice, for several reasons:

• Program analysis can be expensive, and lengthy compile times make programmers unhappy. Compiler authors must weigh each optimization pass’s compile-time overhead against its runtime benefits, and plenty of optimizations simply don’t pay their weight.

• Compilers are complex, constantly-evolving pieces of software. Each change to the internal representation or static analysis framework requires updating every optimization pass to handle the new API, so complex passes can become a substantial maintenance burden. Compiler authors must always consider whether developer time could be better spent elsewhere.

• Most compilers run most of their optimization passes on all programs, but not all optimizations are broadly applicable. Even if an optimization pass has the potential to win big on certain programs, it’s not worth significant costs if most programs will never see the benefits.

An advantage of a hardcoded pass is that it’s fairly cheap, and maintenance burden is very low. Even if it only fires on a small subset of programs, the overhead is likely to be so small that it’s in the noise. What’s more, an operation like popcount is likely to appear within inner loops, so on those programs, the performance gains have the potential to be very large.

That said, this optimization is absolutely not representative of optimizations as a whole. Hardcoded patterns are rarely the compiler author’s tool of choice, and popcount is simply an exception. I wouldn’t read into it too much.

Answer 2

By running gcc -O3 -fdump-tree-all-all main.c -S -march=haswell which prints out all optimization steps, we can find that this optimization is performed in main.c.036t.forwprop1:

Pass statistics of "forwprop": ----------------

Applying pattern match.pd:4684, gimple-match-6.cc:4680
Applying pattern match.pd:9281, gimple-match-7.cc:2488

Which in turn, by going to the match.pd file, we can see that this is in fact a hardcoded match for that popcnt implementation, constants and all:

/* 64- and 32-bits branchless implementations of popcount are detected:
...
(simplify
 (rshift
  (mult
   (bit_and
    (plus:c
     (rshift @8 INTEGER_CST@5)
      (plus:c@8
       (bit_and @6 INTEGER_CST@7)
    (bit_and
     (rshift
      (minus@6 @0
...
  /* Check constants and optab.  */
  (with { unsigned prec = TYPE_PRECISION (type);
      int shift = (64 - prec) & 63;
      unsigned HOST_WIDE_INT c1
        = HOST_WIDE_INT_UC (0x0101010101010101) >> shift;
      unsigned HOST_WIDE_INT c2
        = HOST_WIDE_INT_UC (0x0F0F0F0F0F0F0F0F) >> shift;
      unsigned HOST_WIDE_INT c3
        = HOST_WIDE_INT_UC (0x3333333333333333) >> shift;
      unsigned HOST_WIDE_INT c4
        = HOST_WIDE_INT_UC (0x5555555555555555) >> shift;

In this particular case, this implementation of popcnt is probably common enough that it warrants a special case being implemented.

Answer 3

As an aside to @kouta-kun's answer for gcc, I searched what llvm does.

I found popcnt being generated in LoopIdiomRecognize.cpp, a pass that recognizes idioms and transforms simple loops into a non-loop form. The recognizePopcount and the detectPopcountIdiom functions only recognizes popcnt implementations that look like this:

for (popcount=0; x; popcount++)
    x &= x - 1;

However, I could not find a detection for the branchless version.

---

But how would a compiler be able to figure that out, besides hardcoding numerous possible implementations and then comparing until there is a match?

Rather than comparing directly to multiple possible implementations, it's more like pattern matching. Here we detect if the loop:

• is small enough,
• has only one block,
• has only one backedge,
• contains instructions corresponding to "x2 = x1 & (x1 - 1)",
• has the cnt2 = cnt1 + 1 increment... And so on.

Do compilers have a way of 'simulating' the possible inputs and outputs of a function, and determining that they will match the result of a specific assembly instruction?

That would quickly become extremely slow to perform during compilation, just for the sake of detecting this very specific optimization.

Answer 4

canonicalisation (c.f. my other answer) is indeed relevant. it is no panacea—we cannot 'reduce any function into some "canonical form"' due to godel, rice, et al, and even for the cases where that is possible, it is often computationally infeasible—but in general, if we have an optimising rewrite x -> y, and x' is an alternate form of x which will by means of other transformations be canonicalised into it, then there is no need to also express the rewrite x' -> y

there is also a a degree to which idioms make their way into the cultural canon, so there will be a particular way of writing a function (like popcnt, as you showed) which it's understood contemporary compilers will reduce to a single instruction if possible. it's debatable the extent to which this is a good idea, but it is a thing

abstract interpretation can be helpful. in general, an optimising rewrite may be predicated not just on the syntactic structure of an expression, but also on facts that are known about individual terms. consider a much simpler example, in the form of the following two expressions (& here means bitwise logical and):

if x < 1 then x < 4 else ...
let x = y & 3 in x < 4

in both of these cases, the subexpression 'x < 4' can be reduced to 'true'. we could express this with a pair of rewrites: first 'if x < P then C[x < Q] else ...' -> 'if x < P then C[true] else ...' if Q <= P; second '(x & P) < Q' -> 'true' if P < Q. you can see how this would blow up quickly, though (and i already had to cheat in order to allow x < Q to be a subexpression in the conditional case)

on the other hand, we could track upper and lower bounds for every term (the abstract domain of intervals). these are broadly useful facts to know. both bitwise and and if can create and propagate those facts as appropriate, and they can be consumed by a single rewrite: 'x < P' -> 'true' if upperbound(x) < P

take abstract interpretation a bit further and you get symbolic abstract domains, which know about relationships between terms. this blogpost suggests that msvc is doing something similar in order to recognise byteswaps and bitreverses. rather than recognise a specific code sequence (like with popcnt), it tries to track the general case when one term is known to be a permutation of the bits in another term. in the case when a term is the bswap permutation of another's bits, it can be directly replaced with a bswap instruction; notably, this requires absolutely no inspection into the structure of the concrete source term, only the abstract state. although this cannot work perfectly in every case (see again godel et al), it will in practice be quite insensitive to the way you happen to write your bswap

(i say 'suggests' because the blogpost is not entirely clear—it could be canonicalising to concrete 'bit permute' instructions and matching on that instead. i could see an argument for going both ways; both would work)

Answer 5

Some compilers use actual complex pattern matching to recognize complex patterns. For instance the optimizer module in TXR Lisp uses pattern matching over the virtual machine instruction sequences.

A nice, compact example of this is at the very bottom, in the function named late-peephole:

(defun early-peephole (code)
  (rewrite-case insns code
    (((mov (t @t1) (d @d1))
      (jmp @lab2)
      @(symbolp @lab1)
      (mov (t @t1) (t 0))
      @lab2
      (ifq (t @t1) (t 0) @lab3)
      . @rest)
    ^((mov (t ,t1) (d ,d1))
      (jmp ,lab3)
      ,lab1
      (mov (t ,t1) (t 0))
      ,lab2
      ,*rest))
    (@else else)))

This looks for an instruction sequence like:

(mov (t 3) (d 9))
(jmp :foo)
:bar
(mov (t 3) (t 0))  ;; (t 0) is an immutable register that holds nil
:foo
(ifq (t 3) (d 9) :xyzzy)   ;; if operands eq, keep going else jump :xyzzy
...

and rewrites it to:

(mov (t 3) (d 9))
(jmp :xyzzy)
:bar
(mov (t 3) (t 0))  ;; (t 0) is an immutable register that holds nil
:foo

The idea is that we know (t 3) and (d 9) are the same since we moved the latter to the former, so we can just jump to :xyzzy after that, and nuke the ifq instruction. (The :foo label should have been removed also; if it is referenced anywhere other than the (jmp :foo) instruction that was removed, that would be bad.)

The rewrite-case macro moves down the list of instructions one by one, testing all the patterns, and doing the rewrites that are possible; it is defined in the same file.

The pattern matching has a lot of power; it can backreference among instructions to match certain registers that have to be the same, and test arbitrary predicates, like that a certain register that is matched must be "dead" (no next use) and whatnot. Some pattern matches in that file test something in one basic block of code, but then also follow a label and test something in a target basic block.

If we have a complex operation that we would like to recognize that has many variants, it can be done in multiple passes. We can recognize smaller numbers of variations in the subexpressions of the whole operation, and rewrite them to a normalized/canonicalized variant. Then later, our larger pattern just matches the normalized variants of the subexpressions.