Performance: LLVM 20 aggressively optimizes popcnt and results in worse performance

[jabraham17]

I am finding that the same microbenchmark, when compiled with clang 20, is much slower then the same benchmark compiled with clang 19.

This link has the full benchmark and the assembly for clang 19 and 20.

The LLVM 20 code is much longer, and seems to be because the LLVM 20 version is vectorized and not using the popcnt instruction. For some reason, this is slower. The LLVM 20 version takes .15s, the LLVM 19 version takes .05s.

Using the naive popcnt for the C version does seem to get pattern matched better and result in LLVM 20 being just as fast, if not faster

   uint64_t c = 0;
   while (n) {
        n &= (n - 1);
        c++;
    }
    return c;

[topperc]

Looks like the compiler was able to see that the input to the popcnt was only 32-bits. This caused some constants to be simplified in a way that broke the popcnt pattern match.

[jabraham17]

Wow, that does seem to have solved it in the microbenchmark. I'll plug that into Chapel and see what happens.

[topperc]

This fixes it, but it needs some refactoring to reduce duplication.

diff --git a/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp b/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp
index c128687062ad..f31b4d892d48 100644
--- a/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp
+++ b/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp
@@ -328,15 +328,29 @@ static bool tryToRecognizePopCount(Instruction &I) {
                               m_SpecificInt(Mask33))))) {
         Value *Root, *SubOp1;
         // Matching "i - ((i >> 1) & 0x55555555...)".
+        const APInt *AndMask;
         if (match(AndOp0, m_Sub(m_Value(Root), m_Value(SubOp1))) &&
             match(SubOp1, m_And(m_LShr(m_Specific(Root), m_SpecificInt(1)),
-                                m_SpecificInt(Mask55)))) {
-          LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");
-          IRBuilder<> Builder(&I);
-          I.replaceAllUsesWith(
-              Builder.CreateIntrinsic(Intrinsic::ctpop, I.getType(), {Root}));
-          ++NumPopCountRecognized;
-          return true;
+                                m_APInt(AndMask)))) {
+          if (*AndMask == Mask55) {
+            LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");
+            IRBuilder<> Builder(&I);
+            I.replaceAllUsesWith(
+                Builder.CreateIntrinsic(Intrinsic::ctpop, I.getType(), {Root}));
+            ++NumPopCountRecognized;
+            return true;
+          }
+          if (AndMask->isSubsetOf(Mask55)) {
+            APInt NeededMask = Mask55 & ~*AndMask;
+            if (MaskedValueIsZero(cast<Instruction>(SubOp1)->getOperand(0), NeededMask, SimplifyQuery(I.getDataLayout()))) {
+              LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");
+              IRBuilder<> Builder(&I);
+              I.replaceAllUsesWith(
+                  Builder.CreateIntrinsic(Intrinsic::ctpop, I.getType(), {Root}));
+              ++NumPopCountRecognized;
+              return true;
+            }
+          }
         }
       }
     }

[bradcray]

Thanks, @topperc !