[PowerPC] avoid masking already-zero bits in BitPermutationSelector

[inouehrs]

Summary

The current BitPermutationSelector generates a code to build a value by tracking two types of bits: ConstZero and Variable.
ConstZero means a bit we need to mask off and Variable is a bit we copy from an input value.

This patch add third type of bits VariableKnownToBeZero caused by AssertZext node or zero-extending load node.
VariableKnownToBeZero is also a bit comes from an input value, but it is known to be already zero. So we do not need to mask them.
VariableKnownToBeZero enhances flexibility to group bits, since we can avoid redundant masking for these bits.

This patch also renames "HasZero" to "NeedMask" since now we may skip masking even when we have zeros (of type VariableKnownToBeZero).

[hfinkel]

Seems like a good idea. A couple of questions below.

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

1319 ↗

(On Diff #150742)

Why was this changed? I'm fine with it either way, but I think that we should be consistent. Either change the type for V and V.getOperand(0), or the number of bits for both.

1426 ↗

(On Diff #150742)

Couldn't you end up here with a single group that's a mixture of constant zeros and known-to-be-zero bits from different underlying values (with, potentially, different rotation factors)? If so, isn't that a problem?

[inouehrs]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

1319 ↗

(On Diff #150742)

I forgot to remove irrelevant test code unintentionally. Thank you for pointing this out.

1426 ↗

(On Diff #150742)

Known-to-be-zero bits from multiple underlying values can be in the same group of zeros. It is ok if they are known to be zero. Masking bits and copying these (zero) bits from the underlying values should give the same result.
What we need to really care is not to include non-zero bits in a group of zeros, which is checked in line 1434 below.

[inouehrs]

gentle ping

[inouehrs]

• rebase to the latest
• make the test cases more strict

[inouehrs]

gentle ping

[inouehrs]

rebased to the latest revision

[inouehrs]

@hfinkel do you have any further suggestions?

[inouehrs]

gentle ping

[hfinkel]

In D48025#1260406, @inouehrs wrote:

gentle ping

Ack. Sorry. I'll look this over again today.

[hfinkel]

LGTM

llvm/trunk/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

 class BitPermutationSelector {
   struct ValueBit {
     SDValue V;
 
     // The bit number in the value, using a convention where bit 0 is the
     // lowest-order bit.
     unsigned Idx;
 
+    // ConstZero means a bit we need to mask off.
+    // Variable is a bit comes from an input variable.
+    // VariableKnownToBeZero is also a bit comes from an input variable,
+    // but it is known to be already zero. So we do not need to mask them.
     enum Kind {
       ConstZero,
-      Variable
+      Variable,
+      VariableKnownToBeZero
     } K;
 
     ValueBit(SDValue V, unsigned I, Kind K = Variable)
       : V(V), Idx(I), K(K) {}
     ValueBit(Kind K = Variable)
       : V(SDValue(nullptr, 0)), Idx(UINT32_MAX), K(K) {}
 
     bool isZero() const {
-      return K == ConstZero;
+      return K == ConstZero || K == VariableKnownToBeZero;
     }
 
     bool hasValue() const {
-      return K == Variable;
+      return K == Variable || K == VariableKnownToBeZero;
     }
 
     SDValue getValue() const {
       assert(hasValue() && "Cannot get the value of a constant bit");
       return V;
     }
 
     unsigned getValueBitIndex() const {
case ISD::AND:
         // prevents the overall procedure from matching a single immediate 'and'
         // (which is non-optimal because such an and might be folded with other
         // things if we don't select it here).
         std::tie(Interesting, LHSBits) = getValueBits(V.getOperand(0), NumBits);
 
         for (unsigned i = 0; i < NumBits; ++i)
           if (((Mask >> i) & 1) == 1)
             Bits[i] = (*LHSBits)[i];
+          else {
+            // AND instruction masks this bit. If the input is already zero,
+            // we have nothing to do here. Otherwise, make the bit ConstZero.
+            if ((*LHSBits)[i].isZero())
+              Bits[i] = (*LHSBits)[i];
             else
               Bits[i] = ValueBit(ValueBit::ConstZero);
+          }
 
         return std::make_pair(Interesting, &Bits);
       }
       break;
     case ISD::OR: {
       const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
       const auto &RHSBits = *getValueBits(V.getOperand(1), NumBits).second;
 
       bool AllDisjoint = true;
-      for (unsigned i = 0; i < NumBits; ++i)
-        if (LHSBits[i].isZero())
+      SDValue LastVal = SDValue();
+      unsigned LastIdx = 0;
+      for (unsigned i = 0; i < NumBits; ++i) {
+        if (LHSBits[i].isZero() && RHSBits[i].isZero()) {
+          // If both inputs are known to be zero and one is ConstZero and
+          // another is VariableKnownToBeZero, we can select whichever
+          // we like. To minimize the number of bit groups, we select
+          // VariableKnownToBeZero if this bit is the next bit of the same
+          // input variable from the previous bit. Otherwise, we select
+          // ConstZero.
+          if (LHSBits[i].hasValue() && LHSBits[i].getValue() == LastVal &&
+              LHSBits[i].getValueBitIndex() == LastIdx + 1)
+            Bits[i] = LHSBits[i];
+          else if (RHSBits[i].hasValue() && RHSBits[i].getValue() == LastVal &&
+                   RHSBits[i].getValueBitIndex() == LastIdx + 1)
+            Bits[i] = RHSBits[i];
+          else
+            Bits[i] = ValueBit(ValueBit::ConstZero);
+        }
+        else if (LHSBits[i].isZero())
           Bits[i] = RHSBits[i];
         else if (RHSBits[i].isZero())
           Bits[i] = LHSBits[i];
         else {
           AllDisjoint = false;
           break;
         }
+        // We remember the value and bit index of this bit.
+        if (Bits[i].hasValue()) {
+          LastVal = Bits[i].getValue();
+          LastIdx = Bits[i].getValueBitIndex();
+        }
+        else {
+          if (LastVal) LastVal = SDValue();
+          LastIdx = 0;
+        }
+      }
 
       if (!AllDisjoint)
         break;
 
       return std::make_pair(Interesting = true, &Bits);
     }
     case ISD::ZERO_EXTEND: {
       // We support only the case with zero extension from i32 to i64 so far.
case ISD::ZERO_EXTEND: {
       for (unsigned i = 0; i < NumOperandBits; ++i)
         Bits[i] = (*LHSBits)[i];
 
       for (unsigned i = NumOperandBits; i < NumBits; ++i)
         Bits[i] = ValueBit(ValueBit::ConstZero);
 
       return std::make_pair(Interesting, &Bits);
     }
+    case ISD::AssertZext: {
+      // For AssertZext, we look through the operand and
+      // mark the bits known to be zero.
+      const SmallVector<ValueBit, 64> *LHSBits;
+      std::tie(Interesting, LHSBits) = getValueBits(V.getOperand(0),
+                                                    NumBits);
+
+      EVT FromType = cast<VTSDNode>(V.getOperand(1))->getVT();
+      const unsigned NumValidBits = FromType.getSizeInBits();
+      for (unsigned i = 0; i < NumValidBits; ++i)
+        Bits[i] = (*LHSBits)[i];
+
+      // These bits are known to be zero.
+      for (unsigned i = NumValidBits; i < NumBits; ++i)
+        Bits[i] = ValueBit((*LHSBits)[i].getValue(),
+                           (*LHSBits)[i].getValueBitIndex(),
+                           ValueBit::VariableKnownToBeZero);
+
+      return std::make_pair(Interesting, &Bits);
+    }
+    case ISD::LOAD:
+      LoadSDNode *LD = cast<LoadSDNode>(V);
+      if (ISD::isZEXTLoad(V.getNode()) && V.getResNo() == 0) {
+        EVT VT = LD->getMemoryVT();
+        const unsigned NumValidBits = VT.getSizeInBits();
+
+        for (unsigned i = 0; i < NumValidBits; ++i)
+          Bits[i] = ValueBit(V, i);
+
+        // These bits are known to be zero.
+        for (unsigned i = NumValidBits; i < NumBits; ++i)
+          Bits[i] = ValueBit(V, i, ValueBit::VariableKnownToBeZero);
+
+        // Zero-extending load itself cannot be optimized. So, it is not
+        // interesting by itself though it gives useful information.
+        return std::make_pair(Interesting = false, &Bits);
+      }
+      break;
     }
 
     for (unsigned i = 0; i < NumBits; ++i)
       Bits[i] = ValueBit(V, i);
 
     return std::make_pair(Interesting = false, &Bits);
   }
 
   // For each value (except the constant ones), compute the left-rotate amount
   // to get it from its original to final position.
   void computeRotationAmounts() {
-    HasZeros = false;
+    NeedMask = false;
     RLAmt.resize(Bits.size());
     for (unsigned i = 0; i < Bits.size(); ++i)
       if (Bits[i].hasValue()) {
         unsigned VBI = Bits[i].getValueBitIndex();
         if (i >= VBI)
           RLAmt[i] = i - VBI;
         else
           RLAmt[i] = Bits.size() - (VBI - i);
       } else if (Bits[i].isZero()) {
-        HasZeros = true;
+        NeedMask = true;
         RLAmt[i] = UINT32_MAX;
       } else {
         llvm_unreachable("Unknown value bit type");
       }
   }
 
   // Collect groups of consecutive bits with the same underlying value and
   // rotation factor. If we're doing late masking, we ignore zeros, otherwise
   // they break up groups.
   void collectBitGroups(bool LateMask) {
     BitGroups.clear();
 
     unsigned LastRLAmt = RLAmt[0];
     SDValue LastValue = Bits[0].hasValue() ? Bits[0].getValue() : SDValue();
     unsigned LastGroupStartIdx = 0;
+    bool IsGroupOfZeros = !Bits[LastGroupStartIdx].hasValue();
     for (unsigned i = 1; i < Bits.size(); ++i) {
       unsigned ThisRLAmt = RLAmt[i];
       SDValue ThisValue = Bits[i].hasValue() ? Bits[i].getValue() : SDValue();
       if (LateMask && !ThisValue) {
         ThisValue = LastValue;
         ThisRLAmt = LastRLAmt;
         // If we're doing late masking, then the first bit group always starts
         // at zero (even if the first bits were zero).
         if (BitGroups.empty())
           LastGroupStartIdx = 0;
       }
 
+      // If this bit is known to be zero and the current group is a bit group
+      // of zeros, we do not need to terminate the current bit group even the
+      // Value or RLAmt does not match here. Instead, we terminate this group
+      // when the first non-zero bit appears later.
+      if (IsGroupOfZeros && Bits[i].isZero())
+        continue;
+
       // If this bit has the same underlying value and the same rotate factor as
       // the last one, then they're part of the same group.
       if (ThisRLAmt == LastRLAmt && ThisValue == LastValue)
+        // We cannot continue the current group if this bits is not known to
+        // be zero in a bit group of zeros.
+        if (!(IsGroupOfZeros && ThisValue && !Bits[i].isZero()))
           continue;
 
       if (LastValue.getNode())
         BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
                                      i-1));
       LastRLAmt = ThisRLAmt;
       LastValue = ThisValue;
       LastGroupStartIdx = i;
+      IsGroupOfZeros = !Bits[LastGroupStartIdx].hasValue();
     }
     if (LastValue.getNode())
       BitGroups.push_back(BitGroup(LastValue, LastRLAmt, LastGroupStartIdx,
                                    Bits.size()-1));
 
     if (BitGroups.empty())
       return;
 
SDNode *Select32(SDNode *N, bool LateMask, unsigned *InstCnt) {
     if (InstCnt) *InstCnt = 0;
 
     // Take care of cases that should use andi/andis first.
     SelectAndParts32(dl, Res, InstCnt);
 
     // If we've not yet selected a 'starting' instruction, and we have no zeros
     // to fill in, select the (Value, RLAmt) with the highest priority (largest
     // number of groups), and start with this rotated value.
-    if ((!HasZeros || LateMask) && !Res) {
+    if ((!NeedMask || LateMask) && !Res) {
       ValueRotInfo &VRI = ValueRotsVec[0];
       if (VRI.RLAmt) {
         if (InstCnt) *InstCnt += 1;
         SDValue Ops[] =
           { VRI.V, getI32Imm(VRI.RLAmt, dl), getI32Imm(0, dl),
             getI32Imm(31, dl) };
         Res = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops),
                       0);
SDNode *Select64(SDNode *N, bool LateMask, unsigned *InstCnt) {
     if (InstCnt) *InstCnt = 0;
 
     // Take care of cases that should use andi/andis first.
     SelectAndParts64(dl, Res, InstCnt);
 
     // If we've not yet selected a 'starting' instruction, and we have no zeros
     // to fill in, select the (Value, RLAmt) with the highest priority (largest
     // number of groups), and start with this rotated value.
-    if ((!HasZeros || LateMask) && !Res) {
+    if ((!NeedMask || LateMask) && !Res) {
       // If we have both Repl32 groups and non-Repl32 groups, the non-Repl32
       // groups will come first, and so the VRI representing the largest number
       // of groups might not be first (it might be the first Repl32 groups).
       unsigned MaxGroupsIdx = 0;
       if (!ValueRotsVec[0].Repl32) {
         for (unsigned i = 0, ie = ValueRotsVec.size(); i < ie; ++i)
           if (ValueRotsVec[i].Repl32) {
             if (ValueRotsVec[i].NumGroups > ValueRotsVec[0].NumGroups)

   }
 
   void eraseMatchingBitGroups(function_ref<bool(const BitGroup &)> F) {
     BitGroups.erase(remove_if(BitGroups, F), BitGroups.end());
   }
 
   SmallVector<ValueBit, 64> Bits;
 
-  bool HasZeros;
+  bool NeedMask;
   SmallVector<unsigned, 64> RLAmt;
 
   SmallVector<BitGroup, 16> BitGroups;
 
   DenseMap<std::pair<SDValue, unsigned>, ValueRotInfo> ValueRots;
   SmallVector<ValueRotInfo, 16> ValueRotsVec;
 
   SelectionDAG *CurDAG;
SDNode *Select(SDNode *N) {
     if (!Result.first)
       return nullptr;
     Bits = std::move(*Result.second);
 
     LLVM_DEBUG(dbgs() << "Considering bit-permutation-based instruction"
                          " selection for:    ");
     LLVM_DEBUG(N->dump(CurDAG));
 
-    // Fill it RLAmt and set HasZeros.
+    // Fill it RLAmt and set NeedMask.
     computeRotationAmounts();
 
-    if (!HasZeros)
+    if (!NeedMask)
       return Select(N, false);
 
     // We currently have two techniques for handling results with zeros: early
     // masking (the default) and late masking. Late masking is sometimes more
     // efficient, but because the structure of the bit groups is different, it
     // is hard to tell without generating both and comparing the results. With
     // late masking, we ignore zeros in the resulting value when inserting each
     // set of bit groups, and then mask in the zeros at the end. With early

llvm/trunk/test/CodeGen/PowerPC/addi-offset-fold.ll

entry:
   %bf.lshr.tr = trunc i40 %bf.lshr to i32
   %bf.cast = and i32 %bf.lshr.tr, 127
   ret i32 %bf.cast
 
 ; CHECK-LABEL: @foo
 ; FIXME: We don't need to do these stores at all.
 ; CHECK-DAG: std 3, -24(1)
 ; CHECK-DAG: stb 4, -16(1)
-; CHECK-DAG: sldi [[REG3:[0-9]+]], 4, 32
 ; CHECK-DAG: lwz [[REG2:[0-9]+]], -20(1)
-; CHECK-DAG: or [[REG4:[0-9]+]], [[REG2]], [[REG3]]
-; CHECK: rldicl 3, [[REG4]], 33, 57
+; CHECK-DAG: rlwinm 3, [[REG2]], 1, 31, 31
+; CHECK: rlwimi 3, 4, 1, 25, 30
 ; CHECK: blr
 }
 
 attributes #0 = { nounwind "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "target-cpu"="ppc64le" }
 

llvm/trunk/test/CodeGen/PowerPC/bitfieldinsert.ll

 ; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu -mcpu=pwr8 < %s | FileCheck %s
 ; RUN: llc -verify-machineinstrs -mtriple=powerpc64-unknown-linux-gnu -mcpu=pwr8 < %s | FileCheck %s
 
+; equivalent C code
+;   struct s64 {
+;     int a:5;
+;     int b:16;
+;     long c:42;
+;   };
+;   void bitfieldinsert64(struct s *p, unsigned short v) {
+;     p->b = v;
+;   }
+
+%struct.s64 = type { i64 }
+
+define void @bitfieldinsert64(%struct.s64* nocapture %p, i16 zeroext %v) {
+; CHECK-LABEL: @bitfieldinsert64
+; CHECK: ld [[REG1:[0-9]+]], 0(3)
+; CHECK-NEXT: rlwimi [[REG1]], 4, 5, 11, 26
+; CHECK-NEXT: std [[REG1]], 0(3)
+; CHECK-NEXT: blr
+entry:
+  %0 = getelementptr inbounds %struct.s64, %struct.s64* %p, i64 0, i32 0
+  %1 = zext i16 %v to i64
+  %bf.load = load i64, i64* %0, align 8
+  %bf.shl = shl nuw nsw i64 %1, 5
+  %bf.clear = and i64 %bf.load, -2097121
+  %bf.set = or i64 %bf.clear, %bf.shl
+  store i64 %bf.set, i64* %0, align 8
+  ret void
+}
+
 ; bitfieldinsert32: Test for rlwimi
 ; equivalent C code
 ;   struct s32 {
 ;     int a:8;
 ;     int b:16;
 ;     int c:8;
 ;   };
 ;   void bitfieldinsert32(struct s32 *p, unsigned int v) {
 ;     p->b = v;
 ;   }
 
 %struct.s32 = type { i32 }
 
 define void @bitfieldinsert32(%struct.s32* nocapture %p, i32 zeroext %v) {
 ; CHECK-LABEL: @bitfieldinsert32
 ; CHECK: lwz [[REG1:[0-9]+]], 0(3)
-; CHECK: rlwimi [[REG1]], 4, 8, 8, 23
-; CHECK: stw [[REG1]], 0(3)
-; CHECK: blr
+; CHECK-NEXT: rlwimi [[REG1]], 4, 8, 8, 23
+; CHECK-NEXT: stw [[REG1]], 0(3)
+; CHECK-NEXT: blr
 entry:
   %0 = getelementptr inbounds %struct.s32, %struct.s32* %p, i64 0, i32 0
   %bf.load = load i32, i32* %0, align 4
   %bf.value = shl i32 %v, 8
   %bf.shl = and i32 %bf.value, 16776960
   %bf.clear = and i32 %bf.load, -16776961
   %bf.set = or i32 %bf.clear, %bf.shl
   store i32 %bf.set, i32* %0, align 4
   ret void
 }
 

llvm/trunk/test/CodeGen/PowerPC/ppc64le-aggregates.ll

 ; CHECK-DAG: fmr 10, 2
 ; CHECK-DAG: fmr 11, 3
 ; CHECK-DAG: fmr 12, 4
 ; CHECK-DAG: fmr 13, 5
 ; CHECK-DAG: stfs 5, [[OFF0:[0-9]+]](1)
 ; CHECK-DAG: stfs 6, [[OFF1:[0-9]+]](1)
 ; CHECK-DAG: stfs 7, [[OFF2:[0-9]+]](1)
 ; CHECK-DAG: stfs 8, [[OFF3:[0-9]+]](1)
-; CHECK-DAG: lwz [[REG0:[0-9]+]], [[OFF0]](1)
+; CHECK-DAG: lwz 9, [[OFF0]](1)
 ; CHECK-DAG: lwz [[REG1:[0-9]+]], [[OFF1]](1)
-; CHECK-DAG: lwz [[REG2:[0-9]+]], [[OFF2]](1)
+; CHECK-DAG: lwz 10, [[OFF2]](1)
 ; CHECK-DAG: lwz [[REG3:[0-9]+]], [[OFF3]](1)
-; CHECK-DAG: sldi [[REG1]], [[REG1]], 32
-; CHECK-DAG: sldi [[REG3]], [[REG3]], 32
-; CHECK-DAG: or 9, [[REG0]], [[REG1]]
-; CHECK-DAG: or 10, [[REG2]], [[REG3]]
+; CHECK-DAG: rldimi 9, [[REG1]], 32, 0
+; CHECK-DAG: rldimi 10, [[REG3]], 32, 0
 ; CHECK: bl test1
 
 declare void @test1([8 x float], [8 x float])
 
 define float @callee2([8 x float] %a, [5 x float] %b, [2 x float] %c) {
 entry:
   %c.extract = extractvalue [2 x float] %c, 1
   ret float %c.extract

llvm/trunk/test/CodeGen/PowerPC/rlwimi-dyn-and.ll

next:
   %0 = load i8, i8* undef, align 1
   %conv169 = zext i8 %0 to i32
   %shl170 = shl nuw nsw i32 %conv169, 7
   %shl161.masked = and i32 %shl161, 32768
   %conv174 = or i32 %shl170, %shl161.masked
   ret i32 %conv174
 
 ; CHECK-LABEL: @test2
-; CHECK: slwi 3, {{[0-9]+}}, 7
+; CHECK: rlwinm 3, {{[0-9]+}}, 7, 17, 24
 ; CHECK: rlwimi 3, {{[0-9]+}}, 15, 16, 16
 ; CHECK: blr
 }
 
 attributes #0 = { nounwind }