[GlobalISel][KnownBits] Implement G_CTPOP

[jroelofs]

Summary

Implementation copied almost verbatim from ValueTracking.

[paquette]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

516

[jroelofs]

fix typo

[aemerson]

LGTM.

[GMNGeoffrey]

It looks like this patch failed on the windows pre-merge test. Seems likely to be this patch, given that's the test it added:

Failed Tests (1):
LLVM-Unit :: CodeGen/GlobalISel/./GlobalISelTests.exe/AArch64GISelMITest.TestKnownBitsCTPOP

https://buildkite.com/llvm-project/premerge-checks/builds/51444#f5a03d21-a140-4694-a4d3-a9db24ccf34f

[GMNGeoffrey]

More specifically, since those logs are long:

[ RUN      ] AArch64GISelMITest.TestKnownBitsCTPOP
unknown file: error: SEH exception with code 0x3221225477 thrown in the test body.
[  FAILED  ] AArch64GISelMITest.TestKnownBitsCTPOP (8 ms)

[jroelofs]

Also seems to have broken on PPC:

https://lab.llvm.org/buildbot/#/builders/105/builds/13427/steps/7/logs/FAIL__LLVM-Unit__AArch64GISelMITest_TestKnownBitsC

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

 //===- lib/CodeGen/GlobalISel/GISelKnownBits.cpp --------------*- C++ *-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// Provides analysis for querying information about KnownBits during GISel
 /// passes.
 //
-//===------------------
+//===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/IR/Module.h"
case TargetOpcode::G_BSWAP: {
     break;
   }
   case TargetOpcode::G_BITREVERSE: {
     Register SrcReg = MI.getOperand(1).getReg();
     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
     Known = Known.reverseBits();
     break;
   }
+  case TargetOpcode::G_CTPOP: {
+    computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
+                         Depth + 1);
+    // We can bound the space the count needs.  Also, bits known to be zero can't
+    // contribute to the population.
+    unsigned BitsPossiblySet = Known2.countMaxPopulation();
+    unsigned LowBits = Log2_32(BitsPossiblySet)+1;
+    Known.Zero.setBitsFrom(LowBits);
+    // TODO: we could bound Known.One using the lower bound on the number of
+    // bits which might be set provided by popcnt KnownOne2.
+    break;
+  }
   case TargetOpcode::G_UBFX: {
     KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
     computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
                          Depth + 1);
     computeKnownBitsImpl(MI.getOperand(2).getReg(), OffsetKnown, DemandedElts,
                          Depth + 1);
     computeKnownBitsImpl(MI.getOperand(3).getReg(), WidthKnown, DemandedElts,
                          Depth + 1);

llvm/unittests/CodeGen/GlobalISel/KnownBitsTest.cpp

)";
   Copy = MRI->getVRegDef(CopyAssert3);
   SrcReg = Copy->getOperand(1).getReg();
   Res = Info.getKnownBits(SrcReg);
   EXPECT_EQ(64u, Res.getBitWidth());
   EXPECT_EQ(0u, Res.One.getZExtValue());
   EXPECT_EQ(0xFFFFFFFFFFFFFFF8u, Res.Zero.getZExtValue());
 }
 
+TEST_F(AArch64GISelMITest, TestKnownBitsCTPOP) {
+  StringRef MIRString = R"(
+   %src:_(s32) = COPY $w0
+   %unknown:_(s32) = G_CTPOP %src
+   %constant_4294967295:_(s32) = G_CONSTANT i32 4294967295
+   %thirtytwo:_(s32) = G_CTPOP %constant_4294967295
+   %thirtytwo_copy:_(s32) = COPY %thirtytwo
+   %constant_15:_(s32) = G_CONSTANT i32 15
+   %four:_(s32) = G_CTPOP %constant_15
+   %four_copy:_(s32) = COPY %four
+   %constant_1:_(s32) = G_CONSTANT i32 1
+   %one:_(s32) = G_CTPOP %constant_1
+   %one_copy:_(s32) = COPY %one
+)";
+  setUp(MIRString);
+  if (!TM)
+    return;
+
+  Register UnknownCopy = Copies[Copies.size() - 4];
+  Register ThirtytwoCopy = Copies[Copies.size() - 3];
+  Register FourCopy = Copies[Copies.size() - 2];
+  Register OneCopy = Copies[Copies.size() - 1];
+
+  GISelKnownBits Info(*MF);
+  MachineInstr *Copy;
+  Register SrcReg;
+  KnownBits Res;
+
+  Copy = MRI->getVRegDef(UnknownCopy);
+  SrcReg = Copy->getOperand(1).getReg();
+  Res = Info.getKnownBits(SrcReg);
+  EXPECT_EQ(1u, Res.getBitWidth());
+  EXPECT_EQ(0u, Res.One.getZExtValue());
+  EXPECT_EQ(0u, Res.Zero.getZExtValue());
+
+  Copy = MRI->getVRegDef(ThirtytwoCopy);
+  SrcReg = Copy->getOperand(1).getReg();
+  Res = Info.getKnownBits(SrcReg);
+  EXPECT_EQ(32u, Res.getBitWidth());
+  EXPECT_EQ(0u, Res.One.getZExtValue());
+  EXPECT_EQ(0xFFFFFFC0u, Res.Zero.getZExtValue());
+
+  Copy = MRI->getVRegDef(FourCopy);
+  SrcReg = Copy->getOperand(1).getReg();
+  Res = Info.getKnownBits(SrcReg);
+  EXPECT_EQ(32u, Res.getBitWidth());
+  EXPECT_EQ(0u, Res.One.getZExtValue());
+  EXPECT_EQ(0xFFFFFFF8u, Res.Zero.getZExtValue());
+
+  Copy = MRI->getVRegDef(OneCopy);
+  SrcReg = Copy->getOperand(1).getReg();
+  Res = Info.getKnownBits(SrcReg);
+  EXPECT_EQ(32u, Res.getBitWidth());
+  EXPECT_EQ(0u, Res.One.getZExtValue());
+  EXPECT_EQ(0xFFFFFFFEu, Res.Zero.getZExtValue());
+}
+
 TEST_F(AMDGPUGISelMITest, TestKnownBitsUBFX) {
   StringRef MIRString = "  %3:_(s32) = G_IMPLICIT_DEF\n"
                         "  %4:_(s32) = G_CONSTANT i32 12\n"
                         "  %5:_(s32) = G_CONSTANT i32 8\n"
                         "  %6:_(s32) = G_UBFX %3, %4(s32), %5\n"
                         "  %ubfx_copy:_(s32) = COPY %6\n"
                         "  %7:_(s32) = G_CONSTANT i32 28672\n"
                         "  %8:_(s32) = G_UBFX %7, %4(s32), %5\n"