[InstCombine] Fold or(phi1,phi2) into or(icmp1,icmp2)

[bipmis]

Summary

For a specific pattern of type or(phi1, phi2), where the other use of phi is an "icmp ne with 0", we can reuse these icmps to form the argument to or. This helps reuse the icmps, reduce or to and, and also bring icmps close to phi for further optimizations.

Alive link https://alive2.llvm.org/ce/z/eAyHWm

[bipmis]

Update patch with a separate function definition to handle cmp(or(phi,phi)).
New test added without loops.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2030

This seems very much so like a DAG type fold where you are basing the decision on existing expressions.
phi doesn't exist in backend (dagcombiner) so its a bit tricky.
@nikic, any place this can be put where it doesn't req iterating the use-list?

generally in instcombine we get our duplication by just blindly canoniclizing to a standard format.

Is there a regression if you blindly do the transform?

[bipmis]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2030

I am seeing quite some benefit with this Transform as we are able to reuse instructions which happens to be the other use of phi.
However just the direct transform
or(i64 a,i64 b) -> or((icmp ne a ,0), (icmp ne b ,0)) is expensive. On the contrary the reverse is true in InstCombine.

I can check if the transform or(i64 phia,i64 phib) regresses.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2030

There are a lot of folds that we can do / improve if we optimized around "what exists". If there is a place for such folds (prior to DAGCombiner) that would want this to be moved there. Maybe nikic has an idea about that.

[bipmis]

Closing this as it may result in reverse fold and can be handle in a better way.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

static Value *foldICmpOrXorSubChain(ICmpInst &Cmp, BinaryOperator *Or,
   for (auto It = CmpValues.rbegin() + 1; It != CmpValues.rend(); ++It) {
     Value *RhsCmp = Builder.CreateICmp(Pred, It->first, It->second);
     LhsCmp = Builder.CreateBinOp(BOpc, LhsCmp, RhsCmp);
   }
 
   return LhsCmp;
 }
 
+/// Fold icmp eq (or phi, phi), 0.
+static Value *foldICmpOrPhiPhi(ICmpInst &Cmp, BinaryOperator *Or,
+                               InstCombiner::BuilderTy &Builder) {
+  // icmp eq (or(phi1, phi2)), 0..where there is another use to phi1, phi2 as
+  // "icmp ne phi1, 0" and "icmp ne phi2, 0" We can possibly fold this as icmp
+  // eq (or((icmp ne phi1, 0), (icmp ne phi2, 0))), 0. The above transformation
+  // helps reuse icmps, reduce uses of phi, bring icmp closer to phi and allow
+  // other transforms.
+
+  ICmpInst::Predicate Pred = Cmp.getPredicate();
+  Value *OrOp0 = Or->getOperand(0), *OrOp1 = Or->getOperand(1);
+  ICmpInst::Predicate EqPred;
+  for (auto operand = Or->operands().begin(); operand != Or->operands().end();
+       ++operand) {
+    auto *Phi = dyn_cast<PHINode>(operand->get());
+    if (Phi && !Phi->hasOneUser()) {
+      // Check all users of PHI. It should either be the "Or" or a "icmp ne".
+      for (User *U : Phi->users()) {
+        // Match to specific
+        if (!(U->hasOneUse() &&
+              (match(U, m_Or(m_Specific(OrOp0), m_Specific(OrOp1))) ||
+               (match(U,
+                      m_ICmp(EqPred, m_Specific(operand->get()), m_Zero())) &&
+                EqPred == ICmpInst::ICMP_NE))))
+          return nullptr;
+      }
+    } else
+      return nullptr;
+  }
+  Value *Zero = Constant::getNullValue(OrOp0->getType());
+  Value *Cmp1 = Builder.CreateICmpNE(OrOp0, Zero);
+  Value *Cmp2 = Builder.CreateICmpNE(OrOp1, Zero);
+  Value *NewOr = Builder.CreateOr(Cmp1, Cmp2);
+  return Builder.CreateICmp(Pred, NewOr,
+                            Constant::getNullValue(NewOr->getType()));
+}
+
 /// Fold icmp (or X, Y), C.
 Instruction *InstCombinerImpl::foldICmpOrConstant(ICmpInst &Cmp,
                                                   BinaryOperator *Or,
                                                   const APInt &C) {
   ICmpInst::Predicate Pred = Cmp.getPredicate();
   if (C.isOne()) {
     // icmp slt signum(V) 1 --> icmp slt V, 1
     Value *V = nullptr;
Value *CmpQ =
         Builder.CreateICmp(Pred, Q, ConstantInt::getNullValue(Q->getType()));
     auto BOpc = Pred == CmpInst::ICMP_EQ ? Instruction::And : Instruction::Or;
     return BinaryOperator::Create(BOpc, CmpP, CmpQ);
   }
 
   if (Value *V = foldICmpOrXorSubChain(Cmp, Or, Builder))
     return replaceInstUsesWith(Cmp, V);
 
+  if (Value *V = foldICmpOrPhiPhi(Cmp, Or, Builder))
+    return replaceInstUsesWith(Cmp, V);
+
   return nullptr;
 }
 
 /// Fold icmp (mul X, Y), C.
 Instruction *InstCombinerImpl::foldICmpMulConstant(ICmpInst &Cmp,
                                                    BinaryOperator *Mul,
                                                    const APInt &C) {
   ICmpInst::Predicate Pred = Cmp.getPredicate();

llvm/test/Transforms/InstCombine/phi.ll

 }
 
 define i1 @fold_or_phi_into_or_icmp(ptr noundef readnone %dv1, ptr noundef readnone %dv2, ptr noundef %val1, ptr noundef %val2, i64 %i1, i64 %i2) {
 ; CHECK-LABEL: @fold_or_phi_into_or_icmp(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_I:%.*]] = icmp eq ptr [[VAL1:%.*]], null
 ; CHECK-NEXT:    br i1 [[CMP_I]], label [[_Z3FOOPKC_EXIT:%.*]], label [[COND_I:%.*]]
 ; CHECK:       cond.i:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ne i64 [[I1:%.*]], 0
 ; CHECK-NEXT:    br label [[_Z3FOOPKC_EXIT]]
 ; CHECK:       _Z3fooPKc.exit:
-; CHECK-NEXT:    [[RETVAL_0_I:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[I1:%.*]], [[COND_I]] ]
+; CHECK-NEXT:    [[RETVAL_0_I:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[TMP0]], [[COND_I]] ]
 ; CHECK-NEXT:    [[CMP_I10:%.*]] = icmp eq ptr [[VAL2:%.*]], null
 ; CHECK-NEXT:    br i1 [[CMP_I10]], label [[_Z3FOOPKC_EXIT19:%.*]], label [[COND_I11:%.*]]
 ; CHECK:       cond.i11:
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[I2:%.*]], 0
 ; CHECK-NEXT:    br label [[_Z3FOOPKC_EXIT19]]
 ; CHECK:       _Z3fooPKc.exit19:
-; CHECK-NEXT:    [[RETVAL_0_I20:%.*]] = phi i64 [ 0, [[_Z3FOOPKC_EXIT]] ], [ [[I2:%.*]], [[COND_I11]] ]
-; CHECK-NEXT:    [[TMP0:%.*]] = or i64 [[RETVAL_0_I]], [[RETVAL_0_I20]]
-; CHECK-NEXT:    [[OR_COND_NOT:%.*]] = icmp eq i64 [[TMP0]], 0
-; CHECK-NEXT:    br i1 [[OR_COND_NOT]], label [[IF_THEN:%.*]], label [[IF_END4:%.*]]
+; CHECK-NEXT:    [[RETVAL_0_I20:%.*]] = phi i1 [ false, [[_Z3FOOPKC_EXIT]] ], [ [[TMP1]], [[COND_I11]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[RETVAL_0_I]], [[RETVAL_0_I20]]
+; CHECK-NEXT:    br i1 [[TMP2]], label [[IF_END4:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr [[DV1:%.*]], [[DV2:%.*]]
 ; CHECK-NEXT:    br label [[CLEANUP:%.*]]
 ; CHECK:       if.end4:
-; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp ne i64 [[RETVAL_0_I20]], 0
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i64 [[RETVAL_0_I]], 0
-; CHECK-NEXT:    [[OR_COND10:%.*]] = and i1 [[TOBOOL]], [[TOBOOL2]]
+; CHECK-NEXT:    [[OR_COND10:%.*]] = and i1 [[RETVAL_0_I]], [[RETVAL_0_I20]]
 ; CHECK-NEXT:    br label [[CLEANUP]]
 ; CHECK:       cleanup:
 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i1 [ [[CMP]], [[IF_THEN]] ], [ [[OR_COND10]], [[IF_END4]] ]
 ; CHECK-NEXT:    ret i1 [[RETVAL_0]]
 ;
 entry:
   %cmp.i = icmp eq ptr %val1, null
   br i1 %cmp.i, label %_Z3fooPKc.exit, label %cond.i

 ; CHECK-NEXT:    br i1 [[CMP_I]], label [[_Z3FOOPKC_EXIT:%.*]], label [[WHILE_COND_I:%.*]]
 ; CHECK:       while.cond.i:
 ; CHECK-NEXT:    [[TEST_0_I:%.*]] = phi ptr [ [[INCDEC_PTR_I:%.*]], [[WHILE_COND_I]] ], [ [[VAL1]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[TEST_0_I]], align 1
 ; CHECK-NEXT:    [[CMP1_NOT_I:%.*]] = icmp eq i8 [[TMP0]], 0
 ; CHECK-NEXT:    [[INCDEC_PTR_I]] = getelementptr inbounds i8, ptr [[TEST_0_I]], i64 1
 ; CHECK-NEXT:    br i1 [[CMP1_NOT_I]], label [[WHILE_END_I:%.*]], label [[WHILE_COND_I]]
 ; CHECK:       while.end.i:
-; CHECK-NEXT:    [[SUB_PTR_LHS_CAST_I:%.*]] = ptrtoint ptr [[TEST_0_I]] to i64
-; CHECK-NEXT:    [[SUB_PTR_RHS_CAST_I:%.*]] = ptrtoint ptr [[VAL1]] to i64
-; CHECK-NEXT:    [[SUB_PTR_SUB_I:%.*]] = sub i64 [[SUB_PTR_LHS_CAST_I]], [[SUB_PTR_RHS_CAST_I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne ptr [[TEST_0_I]], [[VAL1]]
 ; CHECK-NEXT:    br label [[_Z3FOOPKC_EXIT]]
 ; CHECK:       _Z3fooPKc.exit:
-; CHECK-NEXT:    [[RETVAL_0_I:%.*]] = phi i64 [ [[SUB_PTR_SUB_I]], [[WHILE_END_I]] ], [ 0, [[ENTRY]] ]
+; CHECK-NEXT:    [[RETVAL_0_I:%.*]] = phi i1 [ [[TMP1]], [[WHILE_END_I]] ], [ false, [[ENTRY]] ]
 ; CHECK-NEXT:    [[CMP_I10:%.*]] = icmp eq ptr [[VAL2:%.*]], null
 ; CHECK-NEXT:    br i1 [[CMP_I10]], label [[_Z3FOOPKC_EXIT19:%.*]], label [[WHILE_COND_I11:%.*]]
 ; CHECK:       while.cond.i11:
 ; CHECK-NEXT:    [[TEST_0_I12:%.*]] = phi ptr [ [[INCDEC_PTR_I14:%.*]], [[WHILE_COND_I11]] ], [ [[VAL2]], [[_Z3FOOPKC_EXIT]] ]
-; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr [[TEST_0_I12]], align 1
-; CHECK-NEXT:    [[CMP1_NOT_I13:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = load i8, ptr [[TEST_0_I12]], align 1
+; CHECK-NEXT:    [[CMP1_NOT_I13:%.*]] = icmp eq i8 [[TMP2]], 0
 ; CHECK-NEXT:    [[INCDEC_PTR_I14]] = getelementptr inbounds i8, ptr [[TEST_0_I12]], i64 1
 ; CHECK-NEXT:    br i1 [[CMP1_NOT_I13]], label [[WHILE_END_I15:%.*]], label [[WHILE_COND_I11]]
 ; CHECK:       while.end.i15:
-; CHECK-NEXT:    [[SUB_PTR_LHS_CAST_I16:%.*]] = ptrtoint ptr [[TEST_0_I12]] to i64
-; CHECK-NEXT:    [[SUB_PTR_RHS_CAST_I17:%.*]] = ptrtoint ptr [[VAL2]] to i64
-; CHECK-NEXT:    [[SUB_PTR_SUB_I18:%.*]] = sub i64 [[SUB_PTR_LHS_CAST_I16]], [[SUB_PTR_RHS_CAST_I17]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne ptr [[TEST_0_I12]], [[VAL2]]
 ; CHECK-NEXT:    br label [[_Z3FOOPKC_EXIT19]]
 ; CHECK:       _Z3fooPKc.exit19:
-; CHECK-NEXT:    [[RETVAL_0_I20:%.*]] = phi i64 [ [[SUB_PTR_SUB_I18]], [[WHILE_END_I15]] ], [ 0, [[_Z3FOOPKC_EXIT]] ]
-; CHECK-NEXT:    [[TMP2:%.*]] = or i64 [[RETVAL_0_I]], [[RETVAL_0_I20]]
-; CHECK-NEXT:    [[OR_COND_NOT:%.*]] = icmp eq i64 [[TMP2]], 0
-; CHECK-NEXT:    br i1 [[OR_COND_NOT]], label [[IF_THEN:%.*]], label [[IF_END4:%.*]]
+; CHECK-NEXT:    [[RETVAL_0_I20:%.*]] = phi i1 [ [[TMP3]], [[WHILE_END_I15]] ], [ false, [[_Z3FOOPKC_EXIT]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = or i1 [[RETVAL_0_I]], [[RETVAL_0_I20]]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[IF_END4:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr [[DV1:%.*]], [[DV2:%.*]]
 ; CHECK-NEXT:    br label [[CLEANUP:%.*]]
 ; CHECK:       if.end4:
-; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp ne i64 [[RETVAL_0_I20]], 0
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i64 [[RETVAL_0_I]], 0
-; CHECK-NEXT:    [[OR_COND10:%.*]] = and i1 [[TOBOOL]], [[TOBOOL2]]
+; CHECK-NEXT:    [[OR_COND10:%.*]] = and i1 [[RETVAL_0_I]], [[RETVAL_0_I20]]
 ; CHECK-NEXT:    br label [[CLEANUP]]
 ; CHECK:       cleanup:
 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i1 [ [[CMP]], [[IF_THEN]] ], [ [[OR_COND10]], [[IF_END4]] ]
 ; CHECK-NEXT:    ret i1 [[RETVAL_0]]
 ;
 entry:
   %cmp.i = icmp eq ptr %val1, null
   br i1 %cmp.i, label %_Z3fooPKc.exit, label %while.cond.i