Revert 221429 and fix bug in TargetLowering::SimplifyDemandedBits

[gilr]

Summary

Suggest to replace rL221429 with the fix described in D6321.

The bug in SimplifyDemandedBits (using DemandedMask instead of the single-use guarded NewMask) should be fixed regardless of the specific X86 blend optimization. Once it's applied, handling multi-uses in the X86 specific code is not needed for correctness.

While 221429 offers a way to perform the optimization even under multiple uses the current implementation would not get a chance to do so due to the multi-use guard (also note that test3 on vselect-avx.ll actually benefits from not performing the optimization as the sext-in-reg is removed altogether if left untouched). Perhaps this approach is worth generalizing to other multi-use cases?

[qcolombet]

Hi Gil,

How does this impact the performances on the whole test suite + externals?

Indeed, when I did r221429, handling the multiple uses like you do in the proposal here, lead to bad regressions. That said, what I tried at that time was slightly different so it may not be the case here.
Anyway, we need to ascertain that.

Let me know if you do not have access to externals, I may be able to run some benchmarks on your behalf.

Thanks,
-Quentin

[gilr]

Hi Quentin,

I ran lnt w/ spec2006 and didn't witness any related performance degradations. However if you could also run it (for more coverage if you have other externals, and to double-check me) that would be great.

One thing I did notice is that this specific sext-in-reg may be optimized away if left alone: DAGCombiner checks whether the value was already sign extended and drops it (this actually happens in vselect-avx.ll). This suggests that at least on some conditions this X86 optimization is redundant all together, but this requires thorough checking beyond this bug fix.

Thanks,
Gil

[qcolombet]

Hi Gil,

Thanks for checking.
I will try to give a try later this week.

One question though!

First, some context.
I can see what kind of bug your patch fixes but I am not convinced that we should remove the SHRUNK_BLEND node. This node prevents optimization on VSELECT (either generic or target specific) to take place later on. This is required because the boolean feeding the related node does not match anymore the expected layout of x86 generic boolean and if those optimizations happens, we may generate wrong code.

Please clarify how your patch addresses that.

Thanks,
-Quentin

[gilr]

Hi Quentin,

Ahh, right, removing the SHRUNK_BLEND node would re-invalidate the booleaness property of the VBLEND condition.
I'll prepare a new patch which keeps the SHRUNK_BLEND node and only fixes the DemandedMask bug (to protect other callers to SimplifyDemandedBits). I'll also look into narrowing this optimization to skip cases where the sext-in-reg could provably be removed on account of all bits already being set.

Thanks,
Gil

[qcolombet]

Hi Gil,

When do you think you will update the patch?

I am trying to plan when I should spare some time to look into the benchmarks.

Thanks,
-Quentin

[gilr]

Hi Quentin,

Hopefuly early next week (still looking into narrowing the optimization down).

Thanks,
Gil

[gilr]

This patch modifies the SIGN_EXTEND_INREG case of SimplifyDemandedBits by:

• Fixing the bug (by using the multi-use guarded) NewMask instead of DemandedMask.
• Avoiding simplifying to shl when the sext-in-reg is known to already be sign-extended, as we can expect it to be removed altogether (by DAGCombiner::visitSIGN_EXTEND_INREG()).

[qcolombet]

Hi Gil,

Thanks for your patience.

The patch does not impact the benchmarks in either direction.

LGTM, with a minor nitpick.

Thanks,
-Quentin

lib/CodeGen/SelectionDAG/TargetLowering.cpp

800 ↗

(On Diff #19651)

Variable names start with a capital letter.

[gilr]

Hi Quentin,

Thanks a lot for helping with this!

One issue that still bothers me has to do with the code in X86ISelLoweing.cpp that handles the multiple uses for this optimization when Cond != TLO.Old:

• Now that SimplifyDemandedBits should not simplify multi-used values, is that code still needed?
• If it is needed, can you please explain why aren't the uses of TLO.Old being checked (for being VSELECT) and replaced? Isn't it the boolean property of TLO.Old that was damaged by the bit simplification?

Gil

[qcolombet]

• Now that SimplifyDemandedBits should not simplify multi-used values, is that code still needed?

I believe this is not used anymore.

The select-avx.ll test case that changed that supposed to exerce that path. As you can see, this does not occur :).

• If it is needed, can you please explain why aren't the uses of TLO.Old being checked (for being VSELECT) and replaced?

Wasn’t it what was happening?
Anyway, no used anymore.

Q.

llvm/trunk/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
         KnownOne |= HighBits;
     }
     break;
   case ISD::SIGN_EXTEND_INREG: {
     EVT ExVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 
     APInt MsbMask = APInt::getHighBitsSet(BitWidth, 1);
     // If we only care about the highest bit, don't bother shifting right.
-    if (MsbMask == DemandedMask) {
+    if (MsbMask == NewMask) {
       unsigned ShAmt = ExVT.getScalarType().getSizeInBits();
       SDValue InOp = Op.getOperand(0);
-
+      unsigned VTBits = Op->getValueType(0).getScalarType().getSizeInBits();
+      bool AlreadySignExtended =
+        TLO.DAG.ComputeNumSignBits(InOp) >= VTBits-ShAmt+1;
+      // However if the input is already sign extended we expect the sign
+      // extension to be dropped altogether later and do not simplify.
+      if (!AlreadySignExtended) {
         // Compute the correct shift amount type, which must be getShiftAmountTy
         // for scalar types after legalization.
         EVT ShiftAmtTy = Op.getValueType();
         if (TLO.LegalTypes() && !ShiftAmtTy.isVector())
           ShiftAmtTy = getShiftAmountTy(ShiftAmtTy);
 
         SDValue ShiftAmt = TLO.DAG.getConstant(BitWidth - ShAmt, ShiftAmtTy);
         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl,
-                                            Op.getValueType(), InOp, ShiftAmt));
+                                                 Op.getValueType(), InOp,
+                                                 ShiftAmt));
+      }
     }
 
     // Sign extension.  Compute the demanded bits in the result that are not
     // present in the input.
     APInt NewBits =
       APInt::getHighBitsSet(BitWidth,
                             BitWidth - ExVT.getScalarType().getSizeInBits());
 

llvm/trunk/test/CodeGen/X86/vector-blend.ll

 ; SSSE3-NEXT:    movapd %xmm4, %xmm0
 ; SSSE3-NEXT:    movaps %xmm5, %xmm1
 ; SSSE3-NEXT:    movapd %xmm6, %xmm2
 ; SSSE3-NEXT:    movaps %xmm7, %xmm3
 ; SSSE3-NEXT:    retq
 ;
 ; SSE41-LABEL: vsel_i648:
 ; SSE41:       # BB#0: # %entry
-; SSE41-NEXT:    pblendw {{.*#+}} xmm0 = xmm0[0,1,2,3],xmm4[4,5,6,7]
-; SSE41-NEXT:    pblendw {{.*#+}} xmm2 = xmm2[0,1,2,3],xmm6[4,5,6,7]
+; SSE41-NEXT:    blendpd {{.*#+}} xmm0 = xmm0[0],xmm4[1]
+; SSE41-NEXT:    blendpd {{.*#+}} xmm2 = xmm2[0],xmm6[1]
 ; SSE41-NEXT:    movaps %xmm5, %xmm1
 ; SSE41-NEXT:    movaps %xmm7, %xmm3
 ; SSE41-NEXT:    retq
 ;
 ; AVX1-LABEL: vsel_i648:
 ; AVX1:       # BB#0: # %entry
 ; AVX1-NEXT:    vblendpd {{.*#+}} ymm0 = ymm0[0],ymm2[1,2,3]
 ; AVX1-NEXT:    vblendpd {{.*#+}} ymm1 = ymm1[0],ymm3[1,2,3]

llvm/trunk/test/CodeGen/X86/vselect-avx.ll

 ; we shrunk some of its bits.
 ; However, this same mask was used in another select (%predphi31) that turned out
 ; to be optimized into a and. In that case, the conditional mask was wrong.
 ;
 ; Make sure that the and is fed by the original mask.
 ; 
 ; <rdar://problem/18819506>
 
-; Note: For now, hard code ORIG_MASK and SHRUNK_MASK registers, because we
-; cannot express that ORIG_MASK must not be equal to ORIG_MASK. Otherwise,
-; even a faulty pattern would pass!
-;  
 ; CHECK-LABEL: test3:
-; Compute the original mask.
-; CHECK: vpcmpeqd {{%xmm[0-9]+}}, {{%xmm[0-9]+}}, [[ORIG_MASK:%xmm0]]
-; Shrink the bit of the mask.
-; CHECK-NEXT: vpslld  $31, [[ORIG_MASK]], [[SHRUNK_MASK:%xmm3]]
-; Use the shrunk mask in the blend.
-; CHECK-NEXT: vblendvps [[SHRUNK_MASK]], %xmm{{[0-9]+}}, %xmm{{[0-9]+}}, %xmm{{[0-9]+}}
-; Use the original mask in the and.
-; CHECK-NEXT: vpand LCPI2_2(%rip), [[ORIG_MASK]], {{%xmm[0-9]+}} 
+; Compute the mask.
+; CHECK: vpcmpeqd {{%xmm[0-9]+}}, {{%xmm[0-9]+}}, [[MASK:%xmm[0-9]+]]
+; Do not shrink the bit of the mask.
+; CHECK-NOT: vpslld $31, [[MASK]], {{%xmm[0-9]+}}
+; Use the mask in the blend.
+; CHECK-NEXT: vblendvps [[MASK]], %xmm{{[0-9]+}}, %xmm{{[0-9]+}}, %xmm{{[0-9]+}}
+; Use the mask in the and.
+; CHECK-NEXT: vpand LCPI2_2(%rip), [[MASK]], {{%xmm[0-9]+}} 
 ; CHECK: retq
 define void @test3(<4 x i32> %induction30, <4 x i16>* %tmp16, <4 x i16>* %tmp17,  <4 x i16> %tmp3, <4 x i16> %tmp12) {
   %tmp6 = srem <4 x i32> %induction30, <i32 3, i32 3, i32 3, i32 3>
   %tmp7 = icmp eq <4 x i32> %tmp6, zeroinitializer
   %predphi = select <4 x i1> %tmp7, <4 x i16> %tmp3, <4 x i16> %tmp12
   %predphi31 = select <4 x i1> %tmp7, <4 x i16> <i16 -1, i16 -1, i16 -1, i16 -1>, <4 x i16> zeroinitializer
 
   store <4 x i16> %predphi31, <4 x i16>* %tmp16, align 8
   store <4 x i16> %predphi, <4 x i16>* %tmp17, align 8
  ret void
 }