[InstCombine] canonicalize multi xor as cmp+select

[Allen]

Summary

extend simplifyWithOpReplaced to look at more than one instruction for Xor instruction.

https://github.com/llvm/llvm-project/issues/63104

[0xdc03]

Have you verified that this fixes the original bug as well? I feel that should also be added as a test case.

[nikic]

We shouldn't restrict this to just xor, but generally recurse the operand replacement.

llvm/lib/Analysis/InstructionSimplify.cpp

4289

This would be the place to recursively call simplifyWithOpReplaced().

[Allen]

address comment

[Allen]

In D153698#4446371, @0xdc03 wrote:

Have you verified that this fixes the original bug as well? I feel that should also be added as a test case.

The original bug need another patch, we should change the phi into select, so I'll add that later.

llvm/lib/Analysis/InstructionSimplify.cpp

4289

Thanks, apply your comment

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

4276

This isn't what I had in mind. Why can't we do the recursive call in here?

[Allen]

llvm/lib/Analysis/InstructionSimplify.cpp

4276

I think there is conflict on the solution.
we need check !is_contained(I->operands(), Op) then entry the recursive call , while in the transform, we can't get all the operands of I

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

4276

You need to keep track whether an operand has been replaced or not. Previously this was just done by is_contained, but now you would have to check the return value of the recursive simplifyWithOpReplaced. If there is no replacement, the following code can be skipped.

[Allen]

recursive call simplifyWithOpReplaced in transform according comment

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

4256

As we're now doing recursive calls, you need to guard against MaxRecurse == 0 here.

4280

These checks for BinaryOperator should not be necessary.

4293

You need to track whether any replacement happened. If it did not happen you can return early.

[Allen]

llvm/lib/Analysis/InstructionSimplify.cpp

4280

yes, but there is some regression. Does it make sense to extend this after we find some cases showed this is beneficial?

a) the vector compare may has scalar operand, which will crash in above line 4268, such as func2 in file llvm/test/Transforms/LoopVectorize/same-base-access.ll.

%17 = insertelement <4 x i32> %16, i32 %13, i64 3
%18 = icmp slt <4 x i32> %17, <i32 4, i32 4, i32 4, i32 4>

b) there is many performance regression when enable isa<SExtInst>(V)) and isa<ZExtInst>(V)) , such as case lshr_out_of_range2 in file llvm/test/Transforms/InstCombine/shift.ll.

c) When I disable the isa<SExtInst>(V)) and isa<ZExtInst>(V)), there are still some cases change because select instruction, where I'm also not sure if it's beneficial or not.

@@ -224,8 +224,8 @@ define i4 @PR45762(i3 %x4) {
 ; CHECK-NEXT:    [[T7:%.*]] = zext i3 [[T4]] to i4
 ; CHECK-NEXT:    [[ONE_HOT_16:%.*]] = shl nuw i4 1, [[T7]]
 ; CHECK-NEXT:    [[OR_69_NOT:%.*]] = icmp eq i3 [[X4]], 0
-; CHECK-NEXT:    [[UMUL_231:%.*]] = select i1 [[OR_69_NOT]], i4 0, i4 [[T7]]
-; CHECK-NEXT:    [[SEL_71:%.*]] = shl i4 [[ONE_HOT_16]], [[UMUL_231]]
+; CHECK-NEXT:    [[UMUL_231:%.*]] = shl i4 [[ONE_HOT_16]], [[T7]]
+; CHECK-NEXT:    [[SEL_71:%.*]] = select i1 [[OR_69_NOT]], i4 -8, i4 [[UMUL_231]]
 ; CHECK-NEXT:    ret i4 [[SEL_71]]

[Allen]

address some comment
1、whether any replacement happened
2、 add condition to guard MaxRecurse == 0
3、delete the check for BinaryOperator, but add the following 3 type to avoid some regression

**if (isa<SelectInst>(I) || isa<CmpInst>(I) || isa<LoadInst>(I))**

[Allen]

llvm/lib/Analysis/InstructionSimplify.cpp

4256

Done, thanks

4276

Thanks, apply your comment, add changed to track that.

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

4285

Could you explain a bit more about why this is necessary for avoiding a regression?

[Allen]

llvm/lib/Analysis/InstructionSimplify.cpp

4285

Thanks for your attrention.

1. I think it is not right to try this because isa<SelectInst>(I) have a select operand, such as case ashr_out_of_range_1 in file Transforms/InstCombine/shift.ll.

%1 = icmp eq i177 %L, -1,  %L = load i177, ptr %A, align 4,i177 -1
%B = select i1 %1, i177 0, i177 %L,  %L = load i177, ptr %A, align 4,i177 -1
 
It is not allowed to deduce the value of %B  is i177 0 when we recursive try the selection operand %1 with i1 true.
we usual try to replace the compare operands, refer to simplifySelectWithICmpEq.

2. For isa<LoadInst>, There will be some crash when we recursive try the pointer operand, which usual is a GetElementPtrInst, so its type is not a vector type, and bring in crash in the above assert in branch if (Op->getType()->isVectorTy()). On the other hand, the value of load is not confirmed, and it is difficult to further optimize.

3. skip isa<CmpInst>(I) is not necessary, so I'll revert it.

[Allen]

revert the skip of isa<CmpInst>

[nikic]

I've ended up implementing this myself in https://github.com/llvm/llvm-project/commit/3d199d086e076f0b9b90d4c59f2226a417a639b5. Additionally, I've landed the following changes to mitigate optimization regressions:

https://github.com/llvm/llvm-project/commit/cd1dcd2c956188521e668e77eec1f8913c01b644
https://github.com/llvm/llvm-project/commit/dc2b2ae7dc333f9c3769785fa147c7872adb9bba
https://github.com/llvm/llvm-project/commit/21827268ada2ee62eaee49fcfa1133ed06a63d25

[Allen]

Thanks for your fixing

llvm/lib/Analysis/InstructionSimplify.cpp

                                      const SimplifyQuery &Q,
                                      bool AllowRefinement,
                                      unsigned MaxRecurse) {
   // Trivial replacement.
   if (V == Op)
     return RepOp;
 
   // We cannot replace a constant, and shouldn't even try.
-  if (isa<Constant>(Op))
-    return nullptr;
-
-  auto *I = dyn_cast<Instruction>(V);
-  if (!I || !is_contained(I->operands(), Op))
+  if (isa<Constant>(Op) || !isa<Instruction>(V) || MaxRecurse == 0)
     return nullptr;
 
+  auto *I = cast<Instruction>(V);
   // The arguments of a phi node might refer to a value from a previous
   // cycle iteration.
   if (isa<PHINode>(I))
     return nullptr;
 
   if (Op->getType()->isVectorTy()) {
     // For vector types, the simplification must hold per-lane, so forbid
     // potentially cross-lane operations like shufflevector.
-    assert(I->getType()->isVectorTy() && "Vector type mismatch");
+    assert((I->getType()->isVectorTy() || isa<LoadInst>(I)) &&
+           "Vector type mismatch");
     if (isa<ShuffleVectorInst>(I) || isa<CallBase>(I))
       return nullptr;
   }
 
   // Replace Op with RepOp in instruction operands.
   SmallVector<Value *, 8> NewOps(I->getNumOperands());
-  transform(I->operands(), NewOps.begin(),
-            [&](Value *V) { return V == Op ? RepOp : V; });
+  bool changed = false;
+  transform(I->operands(), NewOps.begin(), [&](Value *V) {
+    if (V == Op) {
+      changed |= true;
+      return RepOp;
+    }
+    if (!isa<Instruction>(V))
+      return V;
+    // Avoid some regression case.
+    if (isa<SelectInst>(I) || isa<LoadInst>(I))
+      return V;
+    auto *NewI = cast<Instruction>(V);
+    if (NewI->getParent() != I->getParent())
+      return V;
+    // Implement only for a few non-refining
+    if (Value *S = simplifyWithOpReplaced(V, Op, RepOp, Q, 0, MaxRecurse - 1)) {
+      Constant *Cst = dyn_cast<Constant>(S);
+      // It is in fact no replacement when the return value equal to RepOp.
+      if (Cst && Cst != RepOp) {
+        changed |= true;
+        return S;
+      }
+    }
+    return V;
+  });
+
+  // Return early if it did not happen any replacement.
+  if (!changed)
+    return nullptr;
 
   if (!AllowRefinement) {
     // General InstSimplify functions may refine the result, e.g. by returning
     // a constant for a potentially poison value. To avoid this, implement only
     // a few non-refining but profitable transforms here.
 
     if (auto *BO = dyn_cast<BinaryOperator>(I)) {
       unsigned Opcode = BO->getOpcode();

llvm/test/Transforms/InstCombine/select-cmp.ll

 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %cmp1 = icmp eq i8 %y, 0
   %cmp2 = icmp eq i8 %z, %x
   %r = select i1 %c, i1 %cmp1, i1 %cmp2
   ret i1 %r
 }
 
+; https://alive2.llvm.org/ce/z/TGgJTq
+define i32 @select_icmp_xor_multi_insn(i32 noundef %a, i32 noundef %b) {
+; CHECK-LABEL: @select_icmp_xor_multi_insn(
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    ret i32 [[XOR1]]
+;
+  %tobool = icmp eq i32 %a, %b
+  %not = xor i32 %a, -1
+  %xor1 = xor i32 %not, %b
+  %cond = select i1 %tobool, i32 -1, i32 %xor1
+  ret i32 %cond
+}
+
 declare void @use(i1)