[ISel] Round down mask bit when merge undef(s) for DAG combine

[xiangzhangllvm]

Summary

We had some problems in merging splat value.
For example
We usually see 0xuuuu0001 as an undef value, then replace it with totally undef 0xuuuuuuuu.

But this is not make sense when we only use part value of it.

Take llvm.fshl.* for example:

t1: v4i32 = Constant:i32<12>, undef:i32, Constant:i32<12>, undef:i32
t2: v2i64 = bitcast t1
t5: v2i64 = fshl t3, t4, t2

We can not convert t2 to {i64 undef, i64 undef}

But this will be replaced or see "OK to replace" in SelectionDAG::isSplatValue.

[xiangzhangllvm]

Let me try create a small lit test for it. Thanks

[xiangzhangllvm]

Add a test

[xiangzhangllvm]

llvm/test/CodeGen/X86/splat-value.ll

2 ↗

(On Diff #440478)

If use -debug to check it, you will more easy to find the logic error:

In the DAG it will create "t45: v8i64 = X86ISD::VSHL t4, undef:v2i64" node which is totally no meaning.

[pengfei]

llvm/lib/Support/APInt.cpp

2995–2996

Is the comment correct after your change?

llvm/test/CodeGen/X86/splat-value.ll

20–23 ↗

(On Diff #440478)

Where's undef in the test?

[craig.topper]

llvm/include/llvm/ADT/APInt.h

2245–2246

This comment uses the word "down" as well, but to mean the number of bits is decreasing. I believe this patch is implementing this TODO.

[LuoYuanke]

llvm/test/CodeGen/X86/splat-value.ll

31 ↗

(On Diff #440478)

Do we need thoes attributes?

[xiangzhangllvm]

llvm/include/llvm/ADT/APInt.h

2245–2246

So, let me remove this TODO, thanks!

llvm/lib/Support/APInt.cpp

2995–2996

Good catch! Let me update the old comment.

llvm/test/CodeGen/X86/splat-value.ll

20–23 ↗

(On Diff #440478)

It will generated in the mid of DAG combining.

31 ↗

(On Diff #440478)

My copy it from a runfail test, let me recheck it a little later. (Sever can not log on now)

[RKSimon]

Please add test coverage in APIntTest.cpp

llvm/include/llvm/ADT/APInt.h

2246–2251

Yes, 'down' in the TODO meant when reducing the number of bits - maybe 'MatchAllBits' would be better? Current behaviour is 'MatchAnyBits'.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2723

I regret using the term 'UndefElts' - what I meant was that these elements shouldn't be trusted.

llvm/test/CodeGen/X86/splat-value.ll

4 ↗

(On Diff #440478)

Maybe a better test name - and a comment describing what you're testing for?

31 ↗

(On Diff #440478)

Drop the attributes and add -mcpu=cannonlake to the RUN command?

[xiangzhangllvm]

OK, let me add test coverage in APIntTest.cpp, many thanks!

llvm/include/llvm/ADT/APInt.h

2246–2251

Yes, MatchAllBits is better, thanks!

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2723

: ) This is useful for undef optmization.
So In this case (the lit test I write) the UndefElts is mainly used for undef propagation. Now we give out a choose to select MatchAllBits or MatchAnyBits for it.
For BitCast, I think we should Conservatively use MatchAllBits.

llvm/test/CodeGen/X86/splat-value.ll

4 ↗

(On Diff #440478)

OK, this test is about fshl, let me rename it to "define void @test_fshl"

[xiangzhangllvm]

Hi Friends, PLS can you accept this fix ? This is related to one of our Must Fix bug. Many thanks!

[pengfei]

I'm fine with this, please wait one more day for others' opinions.

[RKSimon]

Please pre-commit fshl-splat-undef.ll with current trunk codegen so that the patch commit shows the codegen change.

LGTM with a few minors

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2716

OR -> MatchAnyBits

2723

/*MatchAllBits=*/true

llvm/test/CodeGen/X86/fshl-splat-undef.ll

44

remove the function attrs and the #0 ?

46

remove this?

[xiangzhangllvm]

In D128570#3621731, @RKSimon wrote:

Please pre-commit fshl-splat-undef.ll with current trunk codegen so that the patch commit shows the codegen change.

LGTM with a few minors

In D128570#3621731, @RKSimon wrote:

Please pre-commit fshl-splat-undef.ll with current trunk codegen so that the patch commit shows the codegen change.

LGTM with a few minors

Sure! Pursuing Perfection : ) Thank you!

[xiangzhangllvm]

Address Simon's comments.

llvm/include/llvm/ADT/APInt.h

 /// Compare two values, and if they are different, return the position of the
 /// most significant bit that is different in the values.
 Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A,
                                                   const APInt &B);
 
 /// Splat/Merge neighboring bits to widen/narrow the bitmask represented
 /// by \param A to \param NewBitWidth bits.
 ///
+/// MatchAnyBits: (Default)
 /// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011
 /// e.g. ScaleBitMask(0b00011011, 4) -> 0b0111
-/// A.getBitwidth() or NewBitWidth must be a whole multiples of the other.
 ///
-/// TODO: Do we need a mode where all bits must be set when merging down?
-APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth);
+/// MatchAllBits:
+/// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011
+/// e.g. ScaleBitMask(0b00011011, 4) -> 0b0001
+/// A.getBitwidth() or NewBitWidth must be a whole multiples of the other.
+APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth,
+                   bool MatchAllBits = false);
 } // namespace APIntOps
 
 // See friend declaration above. This additional declaration is required in
 // order to compile LLVM with IBM xlC compiler.
 hash_code hash_value(const APInt &Arg);
 
 /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
 /// with the integer held in IntVal.

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if ((BitWidth % SrcBitWidth) == 0) {
           APIntOps::ScaleBitMask(DemandedElts, NumSrcElts);
       for (unsigned I = 0; I != Scale; ++I) {
         APInt SubUndefElts;
         APInt SubDemandedElt = APInt::getOneBitSet(Scale, I);
         APInt SubDemandedElts = APInt::getSplat(NumSrcElts, SubDemandedElt);
         SubDemandedElts &= ScaledDemandedElts;
         if (!isSplatValue(Src, SubDemandedElts, SubUndefElts, Depth + 1))
           return false;
-        UndefElts |= APIntOps::ScaleBitMask(SubUndefElts, NumElts);
+
+        // Here we can't do "MatchAnyBits" operation merge for undef bits.
+        // Because some operation only use part value of the source.
+        // Take llvm.fshl.* for example:
+        // t1: v4i32 = Constant:i32<12>, undef:i32, Constant:i32<12>, undef:i32
+        // t2: v2i64 = bitcast t1
+        // t5: v2i64 = fshl t3, t4, t2
+        // We can not convert t2 to {i64 undef, i64 undef}
+        UndefElts |= APIntOps::ScaleBitMask(SubUndefElts, NumElts,
+                                            /*MatchAllBits=*/true);
       }
       return true;
     }
     break;
   }
   }
 
   return false;

llvm/lib/Support/APInt.cpp

 Optional<unsigned>
 llvm::APIntOps::GetMostSignificantDifferentBit(const APInt &A, const APInt &B) {
   assert(A.getBitWidth() == B.getBitWidth() && "Must have the same bitwidth");
   if (A == B)
     return llvm::None;
   return A.getBitWidth() - ((A ^ B).countLeadingZeros() + 1);
 }
 
-APInt llvm::APIntOps::ScaleBitMask(const APInt &A, unsigned NewBitWidth) {
+APInt llvm::APIntOps::ScaleBitMask(const APInt &A, unsigned NewBitWidth,
+                                   bool MatchAllBits) {
   unsigned OldBitWidth = A.getBitWidth();
   assert((((OldBitWidth % NewBitWidth) == 0) ||
           ((NewBitWidth % OldBitWidth) == 0)) &&
          "One size should be a multiple of the other one. "
          "Can't do fractional scaling.");
 
   // Check for matching bitwidths.
   if (OldBitWidth == NewBitWidth)
     return A;
 
   APInt NewA = APInt::getZero(NewBitWidth);
 
   // Check for null input.
   if (A.isZero())
     return NewA;
 
   if (NewBitWidth > OldBitWidth) {
     // Repeat bits.
     unsigned Scale = NewBitWidth / OldBitWidth;
     for (unsigned i = 0; i != OldBitWidth; ++i)
       if (A[i])
         NewA.setBits(i * Scale, (i + 1) * Scale);
   } else {
-    // Merge bits - if any old bit is set, then set scale equivalent new bit.
     unsigned Scale = OldBitWidth / NewBitWidth;
-    for (unsigned i = 0; i != NewBitWidth; ++i)
+    for (unsigned i = 0; i != NewBitWidth; ++i) {
+      if (MatchAllBits) {
+        if (A.extractBits(Scale, i * Scale).isAllOnes())
+          NewA.setBit(i);
+      } else {
         if (!A.extractBits(Scale, i * Scale).isZero())
           NewA.setBit(i);
       }
+    }
+  }
 
   return NewA;
 }
 
 /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
 /// with the integer held in IntVal.
 void llvm::StoreIntToMemory(const APInt &IntVal, uint8_t *Dst,
                             unsigned StoreBytes) {

llvm/test/CodeGen/X86/fshl-splat-undef.ll

 ; ==============================================================================
 ; We should make sure not "merging" <i32 12, i32 undef> to <i64 undef>
 ; (We can not convert t2 to {i64 undef, i64 undef, ...})
 ; That is not equal with the origin result)
 ;
 define void @test_fshl(<8 x i64> %lo, <8 x i64> %hi, <8 x i64>* %arr) {
 ; CHECK-LABEL: test_fshl:
 ; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    movl $63, %eax
+; CHECK-NEXT:    vmovd %eax, %xmm2
+; CHECK-NEXT:    movl $12, %eax
+; CHECK-NEXT:    vmovd %eax, %xmm3
+; CHECK-NEXT:    vpand %xmm2, %xmm3, %xmm2
+; CHECK-NEXT:    vpsllq %xmm2, %zmm1, %zmm1
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; CHECK-NEXT:    vpsrlq $1, %zmm0, %zmm0
+; CHECK-NEXT:    vpsrlq $52, %zmm0, %zmm0
 ; CHECK-NEXT:    vpternlogq $168, {{\.?LCPI[0-9]+_[0-9]+}}, %zmm1, %zmm0
 ; CHECK-NEXT:    vmovdqa64 %zmm0, (%eax)
 ; CHECK-NEXT:    vzeroupper
 ; CHECK-NEXT:    retl
 entry:
   %fshl = call <8 x i64> @llvm.fshl.v8i64(<8 x i64> %hi, <8 x i64> %lo, <8 x i64> <i64 12, i64 12, i64 12, i64 12, i64 12, i64 12, i64 12, i64 12>)
   %res = shufflevector <8 x i64> %fshl, <8 x i64> zeroinitializer, <8 x i32> <i32 0, i32 1, i32 10, i32 11, i32 12, i32 13, i32 6, i32 7>
   store <8 x i64> %res, <8 x i64>* %arr, align 64
   ret void
 }
 
 
 ; Function Attrs: nocallback nofree nosync nounwind readnone speculatable willreturn
 declare <8 x i64> @llvm.fshl.v8i64(<8 x i64>, <8 x i64>, <8 x i64>)

llvm/unittests/ADT/APIntTest.cpp

TEST(APIntTest, ScaleBitMask) {
   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0x00), 8), APInt(8, 0x00));
 
   EXPECT_EQ(APIntOps::ScaleBitMask(APInt::getNullValue(1024), 4096),
             APInt::getNullValue(4096));
   EXPECT_EQ(APIntOps::ScaleBitMask(APInt::getAllOnes(4096), 256),
             APInt::getAllOnes(256));
   EXPECT_EQ(APIntOps::ScaleBitMask(APInt::getOneBitSet(4096, 32), 256),
             APInt::getOneBitSet(256, 2));
+
+  EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x00), 8, true), APInt(8, 0x00));
+  EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x01), 8, true), APInt(8, 0x0F));
+  EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x02), 8, true), APInt(8, 0xF0));
+  EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x03), 8, true), APInt(8, 0xFF));
+
+  EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0x00), 4, true), APInt(4, 0x00));
+  EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0xFF), 4, true), APInt(4, 0x0F));
+  EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0xE4), 4, true), APInt(4, 0x08));
 }
 
 } // end anonymous namespace