[Instsimplfy] X == Y ? 0 : X - Y --> X - Y

[junaire]

Summary

Alive2: https://alive2.llvm.org/ce/z/rPN1GB
Fixes: https://github.com/llvm/llvm-project/issues/62238

Depends on D150377

Signed-off-by: Jun Zhang <[e-mail]>

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

4578

While you're at it, can you also do select (X != Y ? X - Y : 0)? Something like:

if(CMPEQ || CMPNE) {
Value * MatchZero, *MatchSub;
if(CMPEQ) {
  MatchZero = TrueVal;
  MatchSub = FalseVal;
}
else {
  MatchZero = FalseVal;
  MatchSub = TrueVal;
}

// Your current code using MatchZero/MatchSub.
}

You will have to move out of the current branch.

4584

can you put this all in nested if (match(TrueVal, m_Zero)) { // check RHS-LHS and LHS-RHS }

[nikic]

The handling for this should be inside simplifyWithOpReplaced().

[junaire]

Move the fold to simplifyWithOpReplaced

[junaire]

In D150378#4335986, @nikic wrote:

The handling for this should be inside simplifyWithOpReplaced().

I updated the patch. The transform I wrote is based on my understanding of the code and I'm not super confident that's what you meant. Educate me please if it's wrong, thanks!

llvm/lib/Analysis/InstructionSimplify.cpp

4578

NE will always be canonicalized to EQ in Line 4476, so we don't have to do that.

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

4252

I think this can just return zero.

[junaire]

Replace simplifyInstructionWithOperands => Constant::getNullValue(Op0->getType())

[junaire]

llvm/lib/Analysis/InstructionSimplify.cpp

4252

Done, thx.

[nikic]

LGTM

I've clarified the preconditions for this function in https://github.com/llvm/llvm-project/commit/8d2bae8c227debdcd0632ce364c58883bd12ad84, so we can actually justify the transform.

llvm/lib/Analysis/InstructionSimplify.cpp

4250–4252

[junaire]

Address comments, thanks!

llvm/lib/Analysis/InstructionSimplify.cpp

if (auto *BO = dyn_cast<BinaryOperator>(I)) {
                                                       /* RHS */ true))
         return NewOps[0];
 
       // x & x -> x, x | x -> x
       if ((Opcode == Instruction::And || Opcode == Instruction::Or) &&
           NewOps[0] == NewOps[1])
         return NewOps[0];
 
       // If we are substituting an absorber constant into a binop and extra
       // poison can't leak if we remove the select -- because both operands of
       // the binop are based on the same value -- then it may be safe to replace
       // the value with the absorber constant. Examples:
       // (Op == 0) ? 0 : (Op & -Op)            --> Op & -Op
       // (Op == 0) ? 0 : (Op * (binop Op, C))  --> Op * (binop Op, C)
       // (Op == -1) ? -1 : (Op | (binop C, Op) --> Op | (binop C, Op)
       if (RepOp == ConstantExpr::getBinOpAbsorber(Opcode, I->getType()) &&
           impliesPoison(BO, Op))
         return RepOp;
     }
if (match(CmpLHS, m_And(m_Value(X), m_Value(Y))) &&
       // (X & Y) == -1 implies X == -1 and Y == -1.
       if (Value *V = simplifySelectWithICmpEq(X, CmpRHS, TrueVal, FalseVal, Q,
                                               MaxRecurse))
         return V;
       if (Value *V = simplifySelectWithICmpEq(Y, CmpRHS, TrueVal, FalseVal, Q,
                                               MaxRecurse))
         return V;
     }
+
+    // select((X == Y) ? 0 : X - Y) --> X - Y
+    if (match(TrueVal, m_Zero()) &&
+        match(FalseVal, m_Sub(m_Specific(CmpLHS), m_Specific(CmpRHS))))
+      return FalseVal;
+    if (match(TrueVal, m_Zero()) &&
+        match(FalseVal, m_Sub(m_Specific(CmpRHS), m_Specific(CmpLHS))))
+      return FalseVal;
   }
 
   return nullptr;
 }
 
 /// Try to simplify a select instruction when its condition operand is a
 /// floating-point comparison.
 static Value *simplifySelectWithFCmp(Value *Cond, Value *T, Value *F,

llvm/test/Transforms/InstSimplify/select.ll

latch:
   br label %loop
 
 exit:
   ret ptr %sel
 }
 
 define i8 @select_sub_cmp(i8 %0, i8 %1) {
 ; CHECK-LABEL: @select_sub_cmp(
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1:%.*]], [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP4:%.*]] = sub nsw i8 [[TMP1]], [[TMP0]]
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP3]], i8 0, i8 [[TMP4]]
-; CHECK-NEXT:    ret i8 [[TMP5]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub nsw i8 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret i8 [[TMP3]]
 ;
   %3 = icmp eq i8 %1, %0
   %4 = sub nsw i8 %1, %0
   %5 = select i1 %3, i8 0, i8 %4
   ret i8 %5
 }
 
 define <2 x i8> @select_sub_cmp_vec(<2 x i8> %0, <2 x i8> %1) {
 ; CHECK-LABEL: @select_sub_cmp_vec(
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i8> [[TMP1:%.*]], [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP4:%.*]] = sub nsw <2 x i8> [[TMP1]], [[TMP0]]
-; CHECK-NEXT:    [[TMP5:%.*]] = select <2 x i1> [[TMP3]], <2 x i8> zeroinitializer, <2 x i8> [[TMP4]]
-; CHECK-NEXT:    ret <2 x i8> [[TMP5]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub nsw <2 x i8> [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret <2 x i8> [[TMP3]]
 ;
   %3 = icmp eq <2 x i8> %1, %0
   %4 = sub nsw <2 x i8> %1, %0
   %5 = select <2 x i1> %3, <2 x i8> <i8 0, i8 0>, <2 x i8> %4
   ret <2 x i8> %5
 }
 
 define i8 @select_sub_cmp_swap(i8 %0, i8 %1) {
 ; CHECK-LABEL: @select_sub_cmp_swap(
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1:%.*]], [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP4:%.*]] = sub nsw i8 [[TMP0]], [[TMP1]]
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP3]], i8 0, i8 [[TMP4]]
-; CHECK-NEXT:    ret i8 [[TMP5]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub nsw i8 [[TMP0:%.*]], [[TMP1:%.*]]
+; CHECK-NEXT:    ret i8 [[TMP3]]
 ;
   %3 = icmp eq i8 %1, %0
   %4 = sub nsw i8 %0, %1
   %5 = select i1 %3, i8 0, i8 %4
   ret i8 %5
 }
 
 define <2 x i8> @select_sub_cmp_vec_swap(<2 x i8> %0, <2 x i8> %1) {
 ; CHECK-LABEL: @select_sub_cmp_vec_swap(
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i8> [[TMP1:%.*]], [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP4:%.*]] = sub nsw <2 x i8> [[TMP0]], [[TMP1]]
-; CHECK-NEXT:    [[TMP5:%.*]] = select <2 x i1> [[TMP3]], <2 x i8> zeroinitializer, <2 x i8> [[TMP4]]
-; CHECK-NEXT:    ret <2 x i8> [[TMP5]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub nsw <2 x i8> [[TMP0:%.*]], [[TMP1:%.*]]
+; CHECK-NEXT:    ret <2 x i8> [[TMP3]]
 ;
   %3 = icmp eq <2 x i8> %1, %0
   %4 = sub nsw <2 x i8> %0, %1
   %5 = select <2 x i1> %3, <2 x i8> <i8 0, i8 0>, <2 x i8> %4
   ret <2 x i8> %5
 }