[GISelKnownBits] Add support for PHIs

[qcolombet]

Summary

Teach the GISelKnowBits analysis how to deal with PHI operations.
PHIs are essentially COPYs happening on edges, so we can just reuse the code for COPY.

This change would be NFC COPY-wise if we have left Depth untouched when calling computeKnownBitsImpl, like it was for COPYs.
This change is however required for PHIs as they may loop back to themselves and we would end up in an infinite loop.

We could make the change truly NFC for the COPYs by increasing Depth only for PHIs, but generally speaking I am not a fan of not increasing Depth or doing specially cases for COPYs.

[qcolombet]

llvm/unittests/CodeGen/GlobalISel/GISelMITest.h

111

In case someone wonders, this change is required to have MIRString with basic blocks that have variables that are live out, otherwise the machine verifier will complain that some variables are not live out of the predecessors when use in a phi.
(Basically we need the tracksRegLiveness property and when we set it, we need to mark as live ins all phys regs that are used across all the GISel tests.)

[arsenm]

I do think copies should be ignored for depth. Other places generally try to treat intervening copies as irrelevant. For example the MIRBuilder inserts copies where they aren't actually necessary when inserting a cast that turns out to be a no-op. I wouldn't want arbitrary changes like this to have an observable change on the final result

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

133

Typo registes

llvm/unittests/CodeGen/GlobalISel/KnownBitsTest.cpp

115

Register

[qcolombet]

I do think copies should be ignored for depth. Other places generally try to treat intervening copies as irrelevant

Fair enough. I still think we shouldn’t insert useless copies long term (those are not free).

[qcolombet]

• Fix typo in comment
• Don't increase depth on COPYs
• Use Register instead of unsigned in added unitests

[arsenm]

LGTM

In D73317#1838994, @qcolombet wrote:

I do think copies should be ignored for depth. Other places generally try to treat intervening copies as irrelevant

Fair enough. I still think we shouldn’t insert useless copies long term (those are not free).

I agree. I looked at doing this, and it wasn't clear to me what guarantees the MachineIRBuilder should provide for the insert point. You could potentially want to write code that relied on an instruction definitely being inserted

[qcolombet]

Thanks @arsenm for the review!

You could potentially want to write code that relied on an instruction definitely being inserted

As long as it doesn't need to be a new one, we could return the definition of the source.
But agree, some places actually expect that we produce a new register and that's not going to be an easy fix.

[aemerson]

In D73317#1839841, @qcolombet wrote:

Thanks @arsenm for the review!

You could potentially want to write code that relied on an instruction definitely being inserted

As long as it doesn't need to be a new one, we could return the definition of the source.
But agree, some places actually expect that we produce a new register and that's not going to be an easy fix.

I'm not fond of the idea of doing something like:

MIB.setInsertPt(Insn);
MI = MIB.buildOp(...)

and having the builder silently ignore the explicitly setInsertPt. I think that behavior should be opt-in only to CSE, and obvious when it's being done.

[qcolombet]

and having the builder silently ignore the explicitly setInsertPt. I think that behavior should be opt-in only to CSE, and obvious when it's being done.

Fair, but do we really need to build something if a copy is what is going to be inserted?
I am assuming the answer would be a case by case answer.

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known,
 
   KnownBits Known2;
 
   switch (Opcode) {
   default:
     TL.computeKnownBitsForTargetInstr(*this, R, Known, DemandedElts, MRI,
                                       Depth);
     break;
-  case TargetOpcode::COPY: {
-    MachineOperand Dst = MI.getOperand(0);
-    MachineOperand Src = MI.getOperand(1);
-    // Look through trivial copies but don't look through trivial copies of the
-    // form `%1:(s32) = OP %0:gpr32` known-bits analysis is currently unable to
-    // determine the bit width of a register class.
+  case TargetOpcode::COPY:
+  case TargetOpcode::G_PHI:
+  case TargetOpcode::PHI: {
+    Known.One = APInt::getAllOnesValue(BitWidth);
+    Known.Zero = APInt::getAllOnesValue(BitWidth);
+    // Destination registers should not have subregisters at this
+    // point of the pipeline, otherwise the main live-range will be
+    // defined more than once, which is against SSA.
+    assert(MI.getOperand(0).getSubReg() == 0 && "Is this code in SSA?");
+    // PHI's operand are a mix of registers and basic blocks interleaved.
+    // We only care about the register ones.
+    for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
+      const MachineOperand &Src = MI.getOperand(Idx);
+      Register SrcReg = Src.getReg();
+      // Look through trivial copies and phis but don't look through trivial
+      // copies or phis of the form `%1:(s32) = OP %0:gpr32`, known-bits
+      // analysis is currently unable to determine the bit width of a
+      // register class.
       //
       // We can't use NoSubRegister by name as it's defined by each target but
       // it's always defined to be 0 by tablegen.
-    if (Dst.getSubReg() == 0 /*NoSubRegister*/ && Src.getReg().isVirtual() &&
-        Src.getSubReg() == 0 /*NoSubRegister*/ &&
-        MRI.getType(Src.getReg()).isValid()) {
-      // Don't increment Depth for this one since we didn't do any work.
-      computeKnownBitsImpl(Src.getReg(), Known, DemandedElts, Depth);
+      if (SrcReg.isVirtual() && Src.getSubReg() == 0 /*NoSubRegister*/ &&
+          MRI.getType(SrcReg).isValid()) {
+        // For COPYs we don't do anything, don't increase the depth.
+        computeKnownBitsImpl(SrcReg, Known2, DemandedElts,
+                             Depth + (Opcode != TargetOpcode::COPY));
+        Known.One &= Known2.One;
+        Known.Zero &= Known2.Zero;
+      } else {
+        // We know nothing.
+        Known = KnownBits(BitWidth);
+        break;
+      }
     }
     break;
   }
   case TargetOpcode::G_CONSTANT: {
     auto CstVal = getConstantVRegVal(R, MRI);
     if (!CstVal)
       break;
     Known.One = *CstVal;

llvm/unittests/CodeGen/GlobalISel/GISelMITest.h

 static std::pair<std::unique_ptr<Module>, std::unique_ptr<MachineModuleInfo>>
 createDummyModule(LLVMContext &Context, const LLVMTargetMachine &TM,
                   StringRef MIRFunc) {
   SmallString<512> S;
   StringRef MIRString = (Twine(R"MIR(
 ---
 ...
 name: func
+tracksRegLiveness: true
 registers:
   - { id: 0, class: _ }
   - { id: 1, class: _ }
   - { id: 2, class: _ }
   - { id: 3, class: _ }
 body: |
   bb.1:
+    liveins: $x0, $x1, $x2, $x4
+
     %0(s64) = COPY $x0
     %1(s64) = COPY $x1
     %2(s64) = COPY $x2
 )MIR") + Twine(MIRFunc) + Twine("...\n"))
                             .toNullTerminatedStringRef(S);
   std::unique_ptr<MIRParser> MIR;
   auto MMI = std::make_unique<MachineModuleInfo>(&TM);
   std::unique_ptr<Module> M =

llvm/unittests/CodeGen/GlobalISel/KnownBitsTest.cpp

TEST_F(GISelMITest, TestKnownBitsCstWithClass) {
   KnownBits Res2 = Info.getKnownBits(DstReg);
   // We still don't know the values due to the register class constraint but %4
   // did reveal the size of %3.
   EXPECT_EQ((uint64_t)32, Res2.getBitWidth());
   EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue());
   EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue());
 }
 
+// Check that we are able to track bits through PHIs
+// and get the intersections of everything we know on each operand.
+TEST_F(GISelMITest, TestKnownBitsCstPHI) {
+  StringRef MIRString = "  bb.10:\n"
+                        "  %10:_(s8) = G_CONSTANT i8 3\n"
+                        "  %11:_(s1) = G_IMPLICIT_DEF\n"
+                        "  G_BRCOND %11(s1), %bb.11\n"
+                        "  G_BR %bb.12\n"
+                        "\n"
+                        "  bb.11:\n"
+                        "  %12:_(s8) = G_CONSTANT i8 2\n"
+                        "  G_BR %bb.12\n"
+                        "\n"
+                        "  bb.12:\n"
+                        "  %13:_(s8) = PHI %10(s8), %bb.10, %12(s8), %bb.11\n"
+                        "  %14:_(s8) = COPY %13\n";
+  setUp(MIRString);
+  if (!TM)
+    return;
+  Register CopyReg = Copies[Copies.size() - 1];
+  MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg);
+  Register SrcReg = FinalCopy->getOperand(1).getReg();
+  Register DstReg = FinalCopy->getOperand(0).getReg();
+  GISelKnownBits Info(*MF);
+  KnownBits Res = Info.getKnownBits(SrcReg);
+  EXPECT_EQ((uint64_t)2, Res.One.getZExtValue());
+  EXPECT_EQ((uint64_t)0xfc, Res.Zero.getZExtValue());
+
+  KnownBits Res2 = Info.getKnownBits(DstReg);
+  EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue());
+  EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue());
+}
+
+// Check that we report we know nothing when we hit a
+// non-generic register.
+// Note: this could be improved though!
+TEST_F(GISelMITest, TestKnownBitsCstPHIToNonGenericReg) {
+  StringRef MIRString = "  bb.10:\n"
+                        "  %10:gpr32 = MOVi32imm 3\n"
+                        "  %11:_(s1) = G_IMPLICIT_DEF\n"
+                        "  G_BRCOND %11(s1), %bb.11\n"
+                        "  G_BR %bb.12\n"
+                        "\n"
+                        "  bb.11:\n"
+                        "  %12:_(s8) = G_CONSTANT i8 2\n"
+                        "  G_BR %bb.12\n"
+                        "\n"
+                        "  bb.12:\n"
+                        "  %13:_(s8) = PHI %10, %bb.10, %12(s8), %bb.11\n"
+                        "  %14:_(s8) = COPY %13\n";
+  setUp(MIRString);
+  if (!TM)
+    return;
+  Register CopyReg = Copies[Copies.size() - 1];
+  MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg);
+  Register SrcReg = FinalCopy->getOperand(1).getReg();
+  Register DstReg = FinalCopy->getOperand(0).getReg();
+  GISelKnownBits Info(*MF);
+  KnownBits Res = Info.getKnownBits(SrcReg);
+  EXPECT_EQ((uint64_t)0, Res.One.getZExtValue());
+  EXPECT_EQ((uint64_t)0, Res.Zero.getZExtValue());
+
+  KnownBits Res2 = Info.getKnownBits(DstReg);
+  EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue());
+  EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue());
+}
+
+// Check that we manage to process PHIs that loop on themselves.
+// For now, the analysis just stops and assumes it knows nothing,
+// eventually we could teach it how to properly track phis that
+// loop back.
+TEST_F(GISelMITest, TestKnownBitsCstPHIWithLoop) {
+  StringRef MIRString =
+      "  bb.10:\n"
+      "  %10:_(s8) = G_CONSTANT i8 3\n"
+      "  %11:_(s1) = G_IMPLICIT_DEF\n"
+      "  G_BRCOND %11(s1), %bb.11\n"
+      "  G_BR %bb.12\n"
+      "\n"
+      "  bb.11:\n"
+      "  %12:_(s8) = G_CONSTANT i8 2\n"
+      "  G_BR %bb.12\n"
+      "\n"
+      "  bb.12:\n"
+      "  %13:_(s8) = PHI %10(s8), %bb.10, %12(s8), %bb.11, %14(s8), %bb.12\n"
+      "  %14:_(s8) = COPY %13\n"
+      "  G_BR %bb.12\n";
+  setUp(MIRString);
+  if (!TM)
+    return;
+  Register CopyReg = Copies[Copies.size() - 1];
+  MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg);
+  Register SrcReg = FinalCopy->getOperand(1).getReg();
+  Register DstReg = FinalCopy->getOperand(0).getReg();
+  GISelKnownBits Info(*MF);
+  KnownBits Res = Info.getKnownBits(SrcReg);
+  EXPECT_EQ((uint64_t)0, Res.One.getZExtValue());
+  EXPECT_EQ((uint64_t)0, Res.Zero.getZExtValue());
+
+  KnownBits Res2 = Info.getKnownBits(DstReg);
+  EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue());
+  EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue());
+}
+
 TEST_F(GISelMITest, TestKnownBitsPtrToIntViceVersa) {
   StringRef MIRString = "  %3:_(s16) = G_CONSTANT i16 256\n"
                         "  %4:_(p0) = G_INTTOPTR %3\n"
                         "  %5:_(s32) = G_PTRTOINT %4\n"
                         "  %6:_(s32) = COPY %5\n";
   setUp(MIRString);
   if (!TM)
     return;