[InstCombine] Fold two PHI operands of `or` conditionally.

[mingmingl]

Summary

If folding two PHI operands of a binary op into predecessors could simplify IR, make the transformation in InstCombine pass.

[mingmingl]

This revision handles the simple case (as shown in llvm/test/Transforms/InstCombine/fold-phi-of-binary-op.ll).

Send it out to collect feedback, and I will need to iterate and enhance it with more test cases (e.g., or instructions in return block in https://godbolt.org/z/79ehxzW9f), or other test cases in llvm/test/Transforms/SROA/alloca-struct.ll

p.s. I might need to delete alloca-struct.ll itself later.

[aeubanks]

this seems reasonable, I like this approach
needs more test coverage though

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1292

I think we should directly call SimplifyInstruction(), no need to constrict this to or
and the naming on this function isn't great anyway, it returns a Value* but starts with could

1310

need a test for this

1321

need a test for this

1335

need a test for this

1339

early return is nicer

1339

I think even if we only simplify one of the two values it's worth it, don't need to constrict to this to requiring both values to be simplified. can be a TODO though

1366

can we use the value above from the call to couldSimplifyInBasicBlock()?

4478

unintentional change? perhaps some editor config needs to be changed?

llvm/test/Transforms/InstCombine/fold-phi-of-binary-op.ll

1

regarding the file name, it's more of a "binary-op-of-phi" than "phi-of-binary-op"

9

it'd be nice to simplify the IR a bit, e.g. simplify the name, remove dso_local, local_unnamed_addr, nocapture, etc

llvm/test/Transforms/InstCombine/zext-or-icmp.ll

49

this test no longer tests https://reviews.llvm.org/D30781, we need to modify this test somehow
maybe something like

select i1 %param, i32 33, 0 instead of %m.011 = phi ...?

[lebedev.ri]

I like this more than the SROA change at least :)

[aeubanks]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1339

sorry, we should only do this if the phi block dominates the block where we don't simplify the value to avoid adding an instruction for another code path that doesn't reach the phi block

[mingmingl]

thanks everyone for the feedback!

carrot@ had a fix for another issue (in https://reviews.llvm.org/D116058) that has overlap with this one, but covering more cases like https://godbolt.org/z/or7W1b7eE and https://godbolt.org/z/MqTh5Te9c

I'm going to hold this for a while; hopefully after https://reviews.llvm.org/D116058 is in, this patch is not needed.

[spatel]

In D115914#3232967, @luna wrote:

thanks everyone for the feedback!

carrot@ had a fix for another issue (in https://reviews.llvm.org/D116058) that has overlap with this one, but covering more cases like https://godbolt.org/z/or7W1b7eE and https://godbolt.org/z/MqTh5Te9c

I'm going to hold this for a while; hopefully after https://reviews.llvm.org/D116058 is in, this patch is not needed.

I don't think D116058 is viable (and I'll comment there too).
This patch seems ok, but it's both too restrictive (only works with 'or') and potentially more costly than necessary (at least as a first step, we can check for constants instead of trying to simplify generally and fix the motivating tests). I put up an alternate patch: D117110 .

[mingmingl]

In D115914#3237349, @spatel wrote:

In D115914#3232967, @luna wrote:

thanks everyone for the feedback!

carrot@ had a fix for another issue (in https://reviews.llvm.org/D116058) that has overlap with this one, but covering more cases like https://godbolt.org/z/or7W1b7eE and https://godbolt.org/z/MqTh5Te9c

I'm going to hold this for a while; hopefully after https://reviews.llvm.org/D116058 is in, this patch is not needed.

I don't think D116058 is viable (and I'll comment there too).
This patch seems ok, but it's both too restrictive (only works with 'or') and potentially more costly than necessary (at least as a first step, we can check for constants instead of trying to simplify generally and fix the motivating tests). I put up an alternate patch: D117110 .

thanks for the inputs! I agree that this patch is way too restrictive and not using the efficient matcher.

I went through D117110 and learnt another way; only has one comment (for my learning) about whether it's idiomatic validate the newly inserted non-constant instruction could be simplified away in later iterations of instr-combine (basically, a stricter condition than only fold constant).

I'll probably revert this and https://reviews.llvm.org/D114832 after download a patch for my own back-up.

[mingmingl]

actually diff of abandoned revisions are stored somewhere and seems to be available for download. this is good so no need to maintain a local copy.

llvm/lib/Analysis/InstructionSimplify.cpp

if (*C1 == ~*C2) {
       // Or commutes, try both ways.
       if (C1->isMask() &&
           match(B, m_c_Add(m_Specific(A), m_Value(N)))) {
         // Add commutes, try both ways.
         if (MaskedValueIsZero(N, *C1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
           return B;
       }
     }
+
+    // TODO(MML):
+    // Include 'and' for instruction combine case (e.g., generate new
+    // instructions).
+    bool m1 = match(Op0, m_And(m_Value(A), m_APInt(C1)));
+    bool m2 = match(Op1, m_And(m_Specific(A), m_APInt(C2)));
+    bool andIsZero = (((*C1) & (*C2)).isZero());
+    if (m1 && m2 && andIsZero) {
+      APInt orResult = ((*C1) | (*C2));
+      const int bitSize = Op0->getType()->getScalarSizeInBits();
+      if (orResult == APInt::getAllOnes(bitSize)) {
+        return A;
+      }
+      // rewrite
+    }
   }
 
   // If the operation is with the result of a phi instruction, check whether
   // operating on all incoming values of the phi always yields the same value.
   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
       return V;
 

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
 
   // Optimize one of these forms:
   //   and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
   //   or i1 Op, SI  / select i1 Op, i1 true, i1 SI  (if IsAnd = false)
   // into simplier select instruction using isImpliedCondition.
   Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
                                                  bool IsAnd);
 
+  // Imagine there is an instruction that applies `I` over `V0` and `V1` in
+  // `BB`, if this instruction could be simplified away in `BB`, returns the
+  // value; otherwise returns nullptr.
+  //
+  // Note simplification or combination as a result of new instruction won't be
+  // performed by the time this function returns, with the assumption that
+  // future iterations should be able to perform the simplification; if the
+  // assumption doesn't hold and newly created instruction cannot be simplified
+  // later, appending the newly created instruction might be counterproductive.
+  //
+  // Caller should guarantee that it's correct to append the newly-created
+  // instruction at the end of basic block (before terminator); for instance,
+  // see how `foldBinaryOpIntoPHI` folds a binary op with two PHI nodes as
+  // operands and call this helper function.
+  Value *couldSimplifyInBasicBlock(BinaryOperator &I, Value *V0, Value *V1,
+                                   BasicBlock *BB);
+
+  Instruction *foldBinaryOpIntoPHI(BinaryOperator &I, PHINode *PN0,
+                                   PHINode *PN1);
+
 public:
   /// Inserts an instruction \p New before instruction \p Old
   ///
   /// Also adds the new instruction to the worklist and returns \p New so that
   /// it is suitable for use as the return from the visitation patterns.
   Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
     assert(New && !New->getParent() &&
            "New instruction already inserted into a basic block!");
public:
   LLVM_NODISCARD static Value *Negate(bool LHSIsZero, Value *Root,
                                       InstCombinerImpl &IC);
 };
 
 } // end namespace llvm
 
 #undef DEBUG_TYPE
 
-#endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
+#endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
 No newline at end of file

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (User *U : make_early_inc_range(PN->users())) {
     Instruction *User = cast<Instruction>(U);
     if (User == &I) continue;
     replaceInstUsesWith(*User, NewPN);
     eraseInstFromFunction(*User);
   }
   return replaceInstUsesWith(I, NewPN);
 }
 
-Instruction *InstCombinerImpl::foldBinOpIntoSelectOrPhi(BinaryOperator &I) {
-  if (!isa<Constant>(I.getOperand(1)))
-    return nullptr;
+Value *InstCombinerImpl::couldSimplifyInBasicBlock(BinaryOperator &I, Value *V0,
+                                                   Value *V1, BasicBlock *BB) {
+  // Returns nullptr for now for ops that are simply not implemented yet.
+  if (I.getOpcode() != Instruction::Or)
+    return nullptr;
+  if (Value *V = SimplifyOrInst(V0, V1, SQ))
+    return V;
+
+  // FIXME: This function could be enhanced to cover more cases that could be
+  // simplified.
+  return nullptr;
+}
+
+Instruction *InstCombinerImpl::foldBinaryOpIntoPHI(BinaryOperator &I,
+                                                   PHINode *PN0, PHINode *PN1) {
+  const unsigned NumPHIValues = PN0->getNumIncomingValues();
+  // FIXME: Generalize the function when PHI nodes have more than 2 incoming
+  // blocks.
+  if ((NumPHIValues != 2) || (NumPHIValues != PN1->getNumIncomingValues())) {
+    return nullptr;
+  }
+
+  BasicBlock *PN0_BB0 = PN0->getIncomingBlock(0);
+  BasicBlock *PN0_BB1 = PN0->getIncomingBlock(1);
+  BasicBlock *PN1_BB0 = PN1->getIncomingBlock(0);
+  BasicBlock *PN1_BB1 = PN1->getIncomingBlock(1);
+  Value *PN0_VAL0 = PN0->getIncomingValue(0);
+  Value *PN0_VAL1 = PN0->getIncomingValue(1);
+
+  if ((PN0_BB0 == PN1_BB1) && (PN0_BB1 == PN1_BB0)) {
+    std::swap(PN0_BB0, PN0_BB1);
+    std::swap(PN0_VAL0, PN0_VAL1);
+  } else if ((PN0_BB0 != PN1_BB0) || (PN0_BB1 != PN1_BB1)) {
+    return nullptr;
+  }
+
+  Value *PN1_VAL0 = PN1->getIncomingValue(0);
+  Value *PN1_VAL1 = PN1->getIncomingValue(1);
+
+  // Now both PHI nodes have two incoming blocks, and we know
+  // PN0_BB0 == PN1_BB0, and PNO_BB1 == PN1_BB1.
+
+  // Validates both PHI nodes have one use, for simplicity.
+  if (!(PN0->hasOneUse() && PN1->hasOneUse())) {
+    return nullptr;
+  }
+
+  if (couldSimplifyInBasicBlock(I, PN0_VAL0, PN1_VAL0, PN0_BB0) &&
+      couldSimplifyInBasicBlock(I, PN0_VAL1, PN1_VAL1, PN1_BB1)) {
+    // If folding two PHI operands into respective predecessor blocks opens up
+    // opportunity for instruction simplification or combination, then transform
+    //
+    // bb2:
+    //   res0 = phi [val00, bb0], [val01, bb1]
+    //   res1 = phi [val10, bb0], [val11, bb1]
+    //   binaryOp res0, res1
+    //
+    // into
+    //
+    // bb0:
+    //   res_bb0 = binaryOp val00, val10
+    // bb1:
+    //   res_bb1 = binaryOp val01, val11
+    // bb2:
+    //   phi [res_bb0, bb0], [res_bb1, bb1].
+
+    // Step 1: Create the new PHI node.
+    PHINode *NewPN = PHINode::Create(I.getType(), PN0->getNumIncomingValues());
+    InsertNewInstBefore(NewPN, *PN0);
+    NewPN->takeName(PN0);
+
+    // Step 2: Create binary ops and fold them into predecessor blocks.
+    // Step 2.1: Do the step for bb0
+    Builder.SetInsertPoint(PN0_BB0->getTerminator());
+    Value *ValFromBB0 = Builder.CreateBinOp(I.getOpcode(), PN0_VAL0, PN1_VAL0);
+    NewPN->addIncoming(ValFromBB0, PN0_BB0);
+
+    // Step 2.1: Do the step for bb1
+    Builder.SetInsertPoint(PN0_BB1->getTerminator());
+    Value *ValFromBB1 = Builder.CreateBinOp(I.getOpcode(), PN0_VAL1, PN1_VAL1);
+    NewPN->addIncoming(ValFromBB1, PN0_BB1);
+
+    return replaceInstUsesWith(I, NewPN);
+  }
+}
 
-  if (auto *Sel = dyn_cast<SelectInst>(I.getOperand(0))) {
+Instruction *InstCombinerImpl::foldBinOpIntoSelectOrPhi(BinaryOperator &I) {
+  Value *LHS = I.getOperand(0);
+  Value *RHS = I.getOperand(1);
+  const bool constantRHS = isa<Constant>(RHS);
+  if (constantRHS) {
+    if (auto *Sel = dyn_cast<SelectInst>(LHS)) {
       if (Instruction *NewSel = FoldOpIntoSelect(I, Sel))
         return NewSel;
-  } else if (auto *PN = dyn_cast<PHINode>(I.getOperand(0))) {
+    } else if (auto *PN = dyn_cast<PHINode>(LHS)) {
       if (Instruction *NewPhi = foldOpIntoPhi(I, PN))
         return NewPhi;
     }
     return nullptr;
   }
 
+  {
+    auto *PN0 = dyn_cast<PHINode>(LHS);
+    auto *PN1 = dyn_cast<PHINode>(RHS);
+
+    if (PN0 && PN1) {
+      if (Instruction *newInst = foldBinaryOpIntoPHI(I, PN0, PN1)) {
+        return newInst;
+      }
+    }
+  }
+
+  return nullptr;
+}
+
 /// Given a pointer type and a constant offset, determine whether or not there
 /// is a sequence of GEP indices into the pointed type that will land us at the
 /// specified offset. If so, fill them into NewIndices and return the resultant
 /// element type, otherwise return null.
 Type *
 InstCombinerImpl::FindElementAtOffset(PointerType *PtrTy, int64_t IntOffset,
                                       SmallVectorImpl<Value *> &NewIndices) {
   Type *Ty = PtrTy->getElementType();

 }
 
 FunctionPass *llvm::createInstructionCombiningPass(unsigned MaxIterations) {
   return new InstructionCombiningPass(MaxIterations);
 }
 
 void LLVMAddInstructionCombiningPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createInstructionCombiningPass());
-}
+}
 No newline at end of file

llvm/test/Transforms/InstCombine/fold-phi-of-binary-op.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+; Meant to collect the test cases for PHI folding for binary ops in general.
+; Currently only has test case for OR.
+
+; Tests that two PHI nodes of `or` (in `return` basic block) is folded into predecessors,
+; and IR get simplified.
+define dso_local i64 @_Z5ParsebPF6RetValvE(i1 zeroext %test, i64 ()* nocapture %p) local_unnamed_addr {
+; CHECK-LABEL: @_Z5ParsebPF6RetValvE(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[TEST:%.*]], label [[RETURN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL:%.*]] = call i64 [[P:%.*]]()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_SROA_3_0:%.*]] = phi i64 [ [[CALL]], [[IF_END]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i64 [[RETVAL_SROA_3_0]]
+;
+entry:
+  br i1 %test, label %return, label %if.end
+
+if.end:                                           ; preds = %entry
+  %call = call i64 %p()
+  %retval.sroa.3.0.extract.shift = and i64 %call, -4294967296
+  %phi.cast = and i64 %call, 4294967295
+  br label %return
+
+return:                                           ; preds = %entry, %if.end
+  %retval.sroa.0.0 = phi i64 [ %phi.cast, %if.end ], [ 0, %entry ]
+  %retval.sroa.3.0 = phi i64 [ %retval.sroa.3.0.extract.shift, %if.end ], [ 0, %entry ]
+  %retval.sroa.0.0.insert.insert = or i64 %retval.sroa.3.0, %retval.sroa.0.0
+  ret i64 %retval.sroa.0.0.insert.insert
+}

llvm/test/Transforms/InstCombine/zext-or-icmp.ll

 
 define i32 @dont_widen_undef() {
 ; CHECK-LABEL: @dont_widen_undef(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BLOCK2:%.*]]
 ; CHECK:       block1:
 ; CHECK-NEXT:    br label [[BLOCK2]]
 ; CHECK:       block2:
-; CHECK-NEXT:    [[CMP_I:%.*]] = phi i1 [ false, [[BLOCK1:%.*]] ], [ true, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[CMP115:%.*]] = phi i1 [ true, [[BLOCK1]] ], [ false, [[ENTRY]] ]
-; CHECK-NEXT:    [[CMP1:%.*]] = or i1 [[CMP_I]], [[CMP115]]
-; CHECK-NEXT:    [[CONV2:%.*]] = zext i1 [[CMP1]] to i32
-; CHECK-NEXT:    ret i32 [[CONV2]]
+; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br label %block2
 
 block1:
   br label %block2
 
 block2:

 
 define i32 @dont_widen_undef_logical() {
 ; CHECK-LABEL: @dont_widen_undef_logical(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BLOCK2:%.*]]
 ; CHECK:       block1:
 ; CHECK-NEXT:    br label [[BLOCK2]]
 ; CHECK:       block2:
-; CHECK-NEXT:    [[CMP_I:%.*]] = phi i1 [ false, [[BLOCK1:%.*]] ], [ true, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[CMP115:%.*]] = phi i1 [ true, [[BLOCK1]] ], [ false, [[ENTRY]] ]
-; CHECK-NEXT:    [[CMP1:%.*]] = or i1 [[CMP_I]], [[CMP115]]
-; CHECK-NEXT:    [[CONV2:%.*]] = zext i1 [[CMP1]] to i32
-; CHECK-NEXT:    ret i32 [[CONV2]]
+; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br label %block2
 
 block1:
   br label %block2
 
 block2: