[InstCombine] Improve foldOpIntoPhi() to use isImpliedCondition

[kitaisreal]

Summary

Example https://godbolt.org/z/acq4rqdqK.
Depends on D156619.

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1363

There is an isImpliedByCondition() overload that accepts unpacked icmp operands. We should use that instead of cloning the instruction.

[kitaisreal]

Updated implementation.

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1364

I don't think the RHSOp0, RHSOp1 variables really add value over Ops[0], Ops[1] here.

1365

I think your tests currently only cover one of the LHSIsTrue cases. You also need one with successors swapped.

1372

You can use ConstantInt::getBool() here.

1383

Please extract the code above here into a separate function (which does simplifyInstructionWithOperands plus the special icmp case).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1370

can rename variable from 'Constant'. Its a big confusing to have variable name ==type.

[kitaisreal]

Updated implementation.

[nikic]

Looks basically fine to me.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1338

I think this should check that getSuccessor(0) != getSuccessor(1). This will get canonicalized away, but is not guaranteed due to worklist order.

1345

I'd personally move this block to the end, because simplifyInstructionWithOperands() is the normal case, and this is a special case.

1355

Omit braces

[kitaisreal]

Updated implementation.

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (User *U : PN->users()) {
       Instruction *UI = cast<Instruction>(U);
       if (UI != &I && !I.isIdenticalTo(UI))
         return nullptr;
     }
     // Otherwise, we can replace *all* users with the new PHI we form.
   }
 
   // Check to see whether the instruction can be folded into each phi operand.
   // If there is one operand that does not fold, remember the BB it is in.
   // If there is more than one or if *it* is a PHI, bail out.
   SmallVector<Value *> NewPhiValues;
   BasicBlock *NonSimplifiedBB = nullptr;
   Value *NonSimplifiedInVal = nullptr;
   for (unsigned i = 0; i != NumPHIValues; ++i) {
     Value *InVal = PN->getIncomingValue(i);
     BasicBlock *InBB = PN->getIncomingBlock(i);
 
     // NB: It is a precondition of this transform that the operands be
     // phi translatable! This is usually trivially satisfied by limiting it
     // to constant ops, and for selects we do a more sophisticated check.
     SmallVector<Value *> Ops;
     for (Value *Op : I.operands()) {
       if (Op == PN)
         Ops.push_back(InVal);
       else
         Ops.push_back(Op->DoPHITranslation(PN->getParent(), InBB));
     }
 
+    // Check if incoming PHI value can be replaced with constant
+    // based on implied condition.
+    BranchInst *TerminatorBI = dyn_cast<BranchInst>(InBB->getTerminator());
+    const ICmpInst *ICmp = dyn_cast<ICmpInst>(&I);
+    if (TerminatorBI && TerminatorBI->isConditional() && ICmp) {
+      const Value *RHSOp0 = Ops[0];
+      const Value *RHSOp1 = Ops[1];
+      bool LHSIsTrue = TerminatorBI->getSuccessor(0) == PN->getParent();
+      std::optional<bool> ImpliedCond =
+          isImpliedCondition(TerminatorBI->getCondition(), ICmp->getPredicate(),
+                             RHSOp0, RHSOp1, DL, LHSIsTrue);
+      if (ImpliedCond) {
+        APInt Constant(I.getType()->getScalarSizeInBits(), ImpliedCond.value());
+        NewPhiValues.push_back(
+            ConstantVector::getIntegerValue(I.getType(), Constant));
+        continue;
+      }
+    }
+
     // Don't consider the simplification successful if we get back a constant
     // expression. That's just an instruction in hiding.
     // Also reject the case where we simplify back to the phi node. We wouldn't
     // be able to remove it in that case.
     Value *NewVal = simplifyInstructionWithOperands(
         &I, Ops, SQ.getWithInstruction(InBB->getTerminator()));
     if (NewVal && NewVal != PN && !match(NewVal, m_ConstantExpr())) {
       NewPhiValues.push_back(NewVal);
       continue;
     }
 
     if (isa<PHINode>(InVal)) return nullptr;  // Itself a phi.
     if (NonSimplifiedBB) return nullptr;  // More than one non-simplified value.
 
     NonSimplifiedBB = InBB;

llvm/test/Transforms/InstCombine/phi.ll

if.end:
   %y = phi i32 [ %i, %if.then ], [ 0, %entry ]
   %add = sub i32 %y, %x
   ret i32 %add
 }
 
 define i1 @cmp_eq_phi_node_can_fold_1(ptr %C) {
 ; CHECK-LABEL: @cmp_eq_phi_node_can_fold_1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr [[C:%.*]], align 1
-; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[TMP1]] to i32
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[TMP2]], -48
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
-; CHECK-NEXT:    br i1 [[TMP4]], label [[SUB_IS_ZERO:%.*]], label [[JOIN:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 48
+; CHECK-NEXT:    br i1 [[TMP2]], label [[SUB_IS_ZERO:%.*]], label [[JOIN:%.*]]
 ; CHECK:       sub_is_zero:
-; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 1
-; CHECK-NEXT:    [[TMP6:%.*]] = load i8, ptr [[TMP5]], align 1
-; CHECK-NEXT:    [[TMP7:%.*]] = zext i8 [[TMP6]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 1
+; CHECK-NEXT:    [[TMP4:%.*]] = load i8, ptr [[TMP3]], align 1
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i8 [[TMP4]], 0
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[TMP8:%.*]] = phi i32 [ [[TMP3]], [[TMP0:%.*]] ], [ [[TMP7]], [[SUB_IS_ZERO]] ]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP8]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = phi i1 [ false, [[TMP0:%.*]] ], [ [[TMP5]], [[SUB_IS_ZERO]] ]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %1 = load i8, ptr %C, align 1
   %2 = zext i8 %1 to i32
   %3 = sub nsw i32 %2, 48
   %4 = icmp eq i32 %3, 0
   br i1 %4, label %sub_is_zero, label %join
 
 sub_is_zero:
   %5 = getelementptr inbounds i8, ptr %C, i64 1
   %6 = load i8, ptr %5, align 1
   %7 = zext i8 %6 to i32
   br label %join
 
 join:
   %8 = phi i32 [ %3, %0 ], [ %7, %sub_is_zero ]
   %cmp = icmp eq i32 %8, 0
   ret i1 %cmp
 }
 
 define i1 @cmp_eq_phi_node_can_fold_2(ptr %C) {
 ; CHECK-LABEL: @cmp_eq_phi_node_can_fold_2(
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr [[C:%.*]], align 1
-; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[TMP1]] to i32
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[TMP2]], -48
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
-; CHECK-NEXT:    br i1 [[TMP4]], label [[SUB_IS_ZERO:%.*]], label [[JOIN:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 48
+; CHECK-NEXT:    br i1 [[TMP2]], label [[SUB_IS_ZERO:%.*]], label [[JOIN:%.*]]
 ; CHECK:       sub_is_zero:
-; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 1
-; CHECK-NEXT:    [[TMP6:%.*]] = load i8, ptr [[TMP5]], align 1
-; CHECK-NEXT:    [[TMP7:%.*]] = zext i8 [[TMP6]] to i32
-; CHECK-NEXT:    [[TMP8:%.*]] = add nsw i32 [[TMP7]], -49
-; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 0
-; CHECK-NEXT:    br i1 [[TMP9]], label [[SUB_IS_ZERO1:%.*]], label [[JOIN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 1
+; CHECK-NEXT:    [[TMP4:%.*]] = load i8, ptr [[TMP3]], align 1
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i8 [[TMP4]], 49
+; CHECK-NEXT:    br i1 [[TMP5]], label [[SUB_IS_ZERO1:%.*]], label [[JOIN]]
 ; CHECK:       sub_is_zero1:
-; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 2
-; CHECK-NEXT:    [[TMP11:%.*]] = load i8, ptr [[TMP10]], align 1
-; CHECK-NEXT:    [[TMP12:%.*]] = zext i8 [[TMP11]] to i32
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 2
+; CHECK-NEXT:    [[TMP7:%.*]] = load i8, ptr [[TMP6]], align 1
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i8 [[TMP7]], 0
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[TMP13:%.*]] = phi i32 [ [[TMP3]], [[TMP0:%.*]] ], [ [[TMP8]], [[SUB_IS_ZERO]] ], [ [[TMP12]], [[SUB_IS_ZERO1]] ]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP13]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = phi i1 [ false, [[TMP0:%.*]] ], [ false, [[SUB_IS_ZERO]] ], [ [[TMP8]], [[SUB_IS_ZERO1]] ]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %1 = load i8, ptr %C, align 1
   %2 = zext i8 %1 to i32
   %3 = sub nsw i32 %2, 48
   %4 = icmp eq i32 %3, 0
   br i1 %4, label %sub_is_zero, label %join
 
join:
   %13 = phi i32 [ %3, %0 ], [ %8, %sub_is_zero ], [ %12, %sub_is_zero1 ]
   %cmp = icmp eq i32 %13, 0
   ret i1 %cmp
 }
 
 define i1 @cmp_ne_phi_node_can_fold_1(ptr %C) {
 ; CHECK-LABEL: @cmp_ne_phi_node_can_fold_1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr [[C:%.*]], align 1
-; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[TMP1]] to i32
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[TMP2]], -48
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
-; CHECK-NEXT:    br i1 [[TMP4]], label [[SUB_IS_ZERO:%.*]], label [[JOIN:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 48
+; CHECK-NEXT:    br i1 [[TMP2]], label [[SUB_IS_ZERO:%.*]], label [[JOIN:%.*]]
 ; CHECK:       sub_is_zero:
-; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 1
-; CHECK-NEXT:    [[TMP6:%.*]] = load i8, ptr [[TMP5]], align 1
-; CHECK-NEXT:    [[TMP7:%.*]] = zext i8 [[TMP6]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 1
+; CHECK-NEXT:    [[TMP4:%.*]] = load i8, ptr [[TMP3]], align 1
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i8 [[TMP4]], 0
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[TMP8:%.*]] = phi i32 [ [[TMP3]], [[TMP0:%.*]] ], [ [[TMP7]], [[SUB_IS_ZERO]] ]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP8]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = phi i1 [ true, [[TMP0:%.*]] ], [ [[TMP5]], [[SUB_IS_ZERO]] ]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %1 = load i8, ptr %C, align 1
   %2 = zext i8 %1 to i32
   %3 = sub nsw i32 %2, 48
   %4 = icmp eq i32 %3, 0
   br i1 %4, label %sub_is_zero, label %join
 
 sub_is_zero:
   %5 = getelementptr inbounds i8, ptr %C, i64 1
   %6 = load i8, ptr %5, align 1
   %7 = zext i8 %6 to i32
   br label %join
 
 join:
   %8 = phi i32 [ %3, %0 ], [ %7, %sub_is_zero ]
   %cmp = icmp ne i32 %8, 0
   ret i1 %cmp
 }
 
 define i1 @cmp_ne_phi_node_can_fold_2(ptr %C) {
 ; CHECK-LABEL: @cmp_ne_phi_node_can_fold_2(
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr [[C:%.*]], align 1
-; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[TMP1]] to i32
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[TMP2]], -48
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
-; CHECK-NEXT:    br i1 [[TMP4]], label [[SUB_IS_ZERO:%.*]], label [[JOIN:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 48
+; CHECK-NEXT:    br i1 [[TMP2]], label [[SUB_IS_ZERO:%.*]], label [[JOIN:%.*]]
 ; CHECK:       sub_is_zero:
-; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 1
-; CHECK-NEXT:    [[TMP6:%.*]] = load i8, ptr [[TMP5]], align 1
-; CHECK-NEXT:    [[TMP7:%.*]] = zext i8 [[TMP6]] to i32
-; CHECK-NEXT:    [[TMP8:%.*]] = add nsw i32 [[TMP7]], -49
-; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 0
-; CHECK-NEXT:    br i1 [[TMP9]], label [[SUB_IS_ZERO1:%.*]], label [[JOIN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 1
+; CHECK-NEXT:    [[TMP4:%.*]] = load i8, ptr [[TMP3]], align 1
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i8 [[TMP4]], 49
+; CHECK-NEXT:    br i1 [[TMP5]], label [[SUB_IS_ZERO1:%.*]], label [[JOIN]]
 ; CHECK:       sub_is_zero1:
-; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 2
-; CHECK-NEXT:    [[TMP11:%.*]] = load i8, ptr [[TMP10]], align 1
-; CHECK-NEXT:    [[TMP12:%.*]] = zext i8 [[TMP11]] to i32
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i8, ptr [[C]], i64 2
+; CHECK-NEXT:    [[TMP7:%.*]] = load i8, ptr [[TMP6]], align 1
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp ne i8 [[TMP7]], 0
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[TMP13:%.*]] = phi i32 [ [[TMP3]], [[TMP0:%.*]] ], [ [[TMP8]], [[SUB_IS_ZERO]] ], [ [[TMP12]], [[SUB_IS_ZERO1]] ]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP13]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = phi i1 [ true, [[TMP0:%.*]] ], [ true, [[SUB_IS_ZERO]] ], [ [[TMP8]], [[SUB_IS_ZERO1]] ]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %1 = load i8, ptr %C, align 1
   %2 = zext i8 %1 to i32
   %3 = sub nsw i32 %2, 48
   %4 = icmp eq i32 %3, 0
   br i1 %4, label %sub_is_zero, label %join