[InstCombine][X86] Simplify demanded elts in SSE intrinsics with repeated args (PR24523)

[RKSimon]

Summary

If we are repeating the same argument in SSE cmp/min/max ops and the op is the only user of that arg value, then we know that these are the only demanded elts we require and can be more aggressive with the recursive SimplifyDemandedElts call.

This required the addition of a Value::isOnlyUserOf helper, similar in function to the SDNode version.

Fixes PR24523.

[spatel]

These tests show a set of missed optimizations, so I recommend taking a step back and separate this into a few patches:

1. Fold x86 min/max intrinsics better - if operands are identical, the min/max simplifies away.
2. Fold x86 cmp intrinsics better (thought we had a bug report for this, but I don't see it now) - if operands are identical, the compare can simplify away (see SimplifyFCmpInst()) or change predicate.
3. Improve demanded elements analysis with isOnlyUserOf() - use generic opcode like 'mul' to show that improvement (independent of x86).
4. Improve demanded elements analysis of x86 min/max/cmp - the x86 part of this patch, but with different tests to show the win with different operands.

The first 3 are independent/parallel. The first 2 raise a potential problem that I don't know the answer to: what happens to target-specific intrinsics in a strict FP environment? Do we need to bypass the folds in that case? Is there some existing code that we can look at that deals with that situation?

[spatel]

In D76928#1955125, @spatel wrote:

4. Improve demanded elements analysis of x86 min/max/cmp - the x86 part of this patch, but with different tests to show the win with different operands.

On 2nd thought, I doubt there will be anything left to do for this if the other patches are in place...

The first 3 are independent/parallel. The first 2 raise a potential problem that I don't know the answer to: what happens to target-specific intrinsics in a strict FP environment? Do we need to bypass the folds in that case? Is there some existing code that we can look at that deals with that situation?

I think that this is an existing problem based on the similar demand-based simplifications near the code diff in this patch and transforms in InstCombiner::visitCallInst(), so those patches don't need to be gated on an answer.

[efriedma]

The first 2 raise a potential problem that I don't know the answer to: what happens to target-specific intrinsics in a strict FP environment? Do we need to bypass the folds in that case?

In general, we need new intrinsics for accessing the FP environment, I think; the existing ones are readnone.

[kpn]

Didn't Andy Kaylor have a plan to pass strict FP metadata through using (I think he called it) bundles?

llvm/include/llvm/IR/Value.h

#endif
   /// Return true if this Value has exactly N users.
   bool hasNUses(unsigned N) const;
 
   /// Return true if this value has N users or more.
   ///
   /// This is logically equivalent to getNumUses() >= N.
   bool hasNUsesOrMore(unsigned N) const;
 
+  /// Return true if this value is the only use of \p V.
+  bool isOnlyUserOf(const Value *V) const;
+
   /// Return true if there is exactly one user of this value that cannot be
   /// dropped.
   ///
   /// This is specialized because it is a common request and does not require
   /// traversing the whole use list.
   Use *getSingleUndroppableUse();
 
   /// Return true if there this value.

llvm/lib/IR/Value.cpp

 bool Value::hasNUses(unsigned N) const {
   return hasNItems(use_begin(), use_end(), N);
 }
 
 bool Value::hasNUsesOrMore(unsigned N) const {
   return hasNItemsOrMore(use_begin(), use_end(), N);
 }
 
+bool Value::isOnlyUserOf(const Value *V) const {
+  bool Seen = false;
+  for (auto *U : V->users()) {
+    if (U == this)
+      Seen = true;
+    else
+      return false;
+  }
+  return Seen;
+}
+
 static bool isUnDroppableUser(const User *U) { return !U->isDroppable(); }
 
 Use *Value::getSingleUndroppableUse() {
   Use *Result = nullptr;
   for (Use &U : uses()) {
     if (!U.getUser()->isDroppable()) {
       if (Result)
         return nullptr;

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

if (!V->hasOneUse()) {
       DemandedElts = EltMask;
     }
   }
 
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) return nullptr;        // Only analyze instructions.
 
   bool MadeChange = false;
-  auto simplifyAndSetOp = [&](Instruction *Inst, unsigned OpNum,
-                              APInt Demanded, APInt &Undef) {
+  auto simplifyAndSetOp = [&](Instruction *Inst, unsigned OpNum, APInt Demanded,
+                              APInt &Undef, bool AllowMultipleUsers = false) {
     auto *II = dyn_cast<IntrinsicInst>(Inst);
     Value *Op = II ? II->getArgOperand(OpNum) : Inst->getOperand(OpNum);
-    if (Value *V = SimplifyDemandedVectorElts(Op, Demanded, Undef, Depth + 1)) {
+    if (Value *V = SimplifyDemandedVectorElts(Op, Demanded, Undef, Depth + 1,
+                                              AllowMultipleUsers)) {
       if (II)
         II->setArgOperand(OpNum, V);
       else
         Inst->setOperand(OpNum, V);
       MadeChange = true;
     }
   };
 
case Instruction::Call: {
     // elements come from operand 0. The low element is a function of both
     // operands.
     case Intrinsic::x86_sse_min_ss:
     case Intrinsic::x86_sse_max_ss:
     case Intrinsic::x86_sse_cmp_ss:
     case Intrinsic::x86_sse2_min_sd:
     case Intrinsic::x86_sse2_max_sd:
     case Intrinsic::x86_sse2_cmp_sd: {
-      simplifyAndSetOp(II, 0, DemandedElts, UndefElts);
+      // If the args are duplicated and are only used by this instruction then
+      // arg0 is the most demanded elts we need.
+      bool OnlyUser = II->getArgOperand(0) == II->getArgOperand(1) &&
+                      II->isOnlyUserOf(II->getArgOperand(0));
+
+      simplifyAndSetOp(II, 0, DemandedElts, UndefElts, OnlyUser);
 
       // If lowest element of a scalar op isn't used then use Arg0.
       if (!DemandedElts[0]) {
         Worklist.push(II);
         return II->getArgOperand(0);
       }
 
+      if (!OnlyUser) {
         // Only lower element is used for operand 1.
         DemandedElts = 1;
         simplifyAndSetOp(II, 1, DemandedElts, UndefElts2);
+      }
 
       // Lower element is undefined if both lower elements are undefined.
       // Consider things like undef&0.  The result is known zero, not undef.
       if (!UndefElts2[0])
         UndefElts.clearBit(0);
 
       break;
     }

llvm/test/Transforms/InstCombine/X86/x86-sse.ll

;
   %5 = insertelement <4 x float> undef, float %b, i32 0
   %6 = tail call <4 x float> @llvm.x86.sse.min.ss(<4 x float> %4, <4 x float> %5)
   %7 = extractelement <4 x float> %6, i32 2
   ret float %7
 }
 
 define float @test_min_ss_3(float %a) {
 ; CHECK-LABEL: @test_min_ss_3(
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x float> <float undef, float 0.000000e+00, float 0.000000e+00, float 0.000000e+00>, float [[A:%.*]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x float> undef, float [[A:%.*]], i32 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = tail call <4 x float> @llvm.x86.sse.min.ss(<4 x float> [[TMP1]], <4 x float> [[TMP1]])
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <4 x float> [[TMP2]], i32 0
 ; CHECK-NEXT:    ret float [[TMP3]]
 ;
   %1 = insertelement <4 x float> zeroinitializer, float %a, i32 0
   %2 = tail call <4 x float> @llvm.x86.sse.min.ss(<4 x float> %1, <4 x float> %1)
   %3 = extractelement <4 x float> %2, i32 0
   ret float %3
;
   %5 = insertelement <4 x float> undef, float %b, i32 0
   %6 = tail call <4 x float> @llvm.x86.sse.max.ss(<4 x float> %4, <4 x float> %5)
   %7 = extractelement <4 x float> %6, i32 3
   ret float %7
 }
 
 define float @test_max_ss_4(float %a) {
 ; CHECK-LABEL: @test_max_ss_4(
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x float> <float undef, float 0.000000e+00, float 0.000000e+00, float 0.000000e+00>, float [[A:%.*]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x float> undef, float [[A:%.*]], i32 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = tail call <4 x float> @llvm.x86.sse.max.ss(<4 x float> [[TMP1]], <4 x float> [[TMP1]])
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <4 x float> [[TMP2]], i32 0
 ; CHECK-NEXT:    ret float [[TMP3]]
 ;
   %1 = insertelement <4 x float> zeroinitializer, float %a, i32 0
   %2 = tail call <4 x float> @llvm.x86.sse.max.ss(<4 x float> %1, <4 x float> %1)
   %3 = extractelement <4 x float> %2, i32 0
   ret float %3
;
   %5 = insertelement <4 x float> undef, float %b, i32 0
   %6 = tail call <4 x float> @llvm.x86.sse.cmp.ss(<4 x float> %4, <4 x float> %5, i8 0)
   %7 = extractelement <4 x float> %6, i32 1
   ret float %7
 }
 
 define float @test_cmp_ss_2(float %a) {
 ; CHECK-LABEL: @test_cmp_ss_2(
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x float> <float undef, float 0.000000e+00, float 0.000000e+00, float 0.000000e+00>, float [[A:%.*]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x float> undef, float [[A:%.*]], i32 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = tail call <4 x float> @llvm.x86.sse.cmp.ss(<4 x float> [[TMP1]], <4 x float> [[TMP1]], i8 3)
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <4 x float> [[TMP2]], i32 0
 ; CHECK-NEXT:    ret float [[TMP3]]
 ;
   %1 = insertelement <4 x float> zeroinitializer, float %a, i32 0
   %2 = tail call <4 x float> @llvm.x86.sse.cmp.ss(<4 x float> %1, <4 x float> %1, i8 3)
   %3 = extractelement <4 x float> %2, i32 0
   ret float %3

llvm/test/Transforms/InstCombine/X86/x86-sse2.ll

;
   %4 = insertelement <2 x double> %3, double 2.000000e+00, i32 1
   %5 = tail call <2 x double> @llvm.x86.sse2.min.sd(<2 x double> %2, <2 x double> %4)
   %6 = extractelement <2 x double> %5, i32 1
   ret double %6
 }
 
 define double @test_min_sd_2(double %a) {
 ; CHECK-LABEL: @test_min_sd_2(
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> <double undef, double 0.000000e+00>, double [[A:%.*]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> undef, double [[A:%.*]], i32 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = tail call <2 x double> @llvm.x86.sse2.min.sd(<2 x double> [[TMP1]], <2 x double> [[TMP1]])
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <2 x double> [[TMP2]], i32 0
 ; CHECK-NEXT:    ret double [[TMP3]]
 ;
   %1 = insertelement <2 x double> zeroinitializer, double %a, i32 0
   %2 = tail call <2 x double> @llvm.x86.sse2.min.sd(<2 x double> %1, <2 x double> %1)
   %3 = extractelement <2 x double> %2, i32 0
   ret double %3
;
   %4 = insertelement <2 x double> %3, double 2.000000e+00, i32 1
   %5 = tail call <2 x double> @llvm.x86.sse2.max.sd(<2 x double> %2, <2 x double> %4)
   %6 = extractelement <2 x double> %5, i32 1
   ret double %6
 }
 
 define double @test_max_sd_2(double %a) {
 ; CHECK-LABEL: @test_max_sd_2(
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> <double undef, double 0.000000e+00>, double [[A:%.*]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> undef, double [[A:%.*]], i32 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = tail call <2 x double> @llvm.x86.sse2.max.sd(<2 x double> [[TMP1]], <2 x double> [[TMP1]])
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <2 x double> [[TMP2]], i32 0
 ; CHECK-NEXT:    ret double [[TMP3]]
 ;
   %1 = insertelement <2 x double> zeroinitializer, double %a, i32 0
   %2 = tail call <2 x double> @llvm.x86.sse2.max.sd(<2 x double> %1, <2 x double> %1)
   %3 = extractelement <2 x double> %2, i32 0
   ret double %3
;
   %4 = insertelement <2 x double> %3, double 2.000000e+00, i32 1
   %5 = tail call <2 x double> @llvm.x86.sse2.cmp.sd(<2 x double> %2, <2 x double> %4, i8 0)
   %6 = extractelement <2 x double> %5, i32 1
   ret double %6
 }
 
 define double @test_cmp_sd_2(double %a) {
 ; CHECK-LABEL: @test_cmp_sd_2(
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> <double undef, double 0.000000e+00>, double [[A:%.*]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> undef, double [[A:%.*]], i32 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = tail call <2 x double> @llvm.x86.sse2.cmp.sd(<2 x double> [[TMP1]], <2 x double> [[TMP1]], i8 3)
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <2 x double> [[TMP2]], i32 0
 ; CHECK-NEXT:    ret double [[TMP3]]
 ;
   %1 = insertelement <2 x double> zeroinitializer, double %a, i32 0
   %2 = tail call <2 x double> @llvm.x86.sse2.cmp.sd(<2 x double> %1, <2 x double> %1, i8 3)
   %3 = extractelement <2 x double> %2, i32 0
   ret double %3