[InstCombine] Convert binop(phi, v) to phi(binop) for constant phi operands

[Carrot]

Summary

If we have

%p = phi  [c1, pred1], [c2, pred2]
%v = add %p, %op

We'll generate immediate materialization instructions in predecessors. We
can directly fold them into ALU instructions and create phi instruction for
the ALU results.

pred1:
  %op1 = add c1, %op 
  br %bb 
pred2:
  %op2 = add c2, %op 
  br %bb 
bb: 
  %v = phi [%op1, pred1], [%op2, pred2]

[lebedev.ri]

immediate materialization instructions

There is no such thing in IR, so this sounds like it should be a back-end backtransform?

[Carrot]

In D116058#3204290, @lebedev.ri wrote:

immediate materialization instructions

There is no such thing in IR, so this sounds like it should be a back-end backtransform?

Although it is not explicitly expressed in LLVM IR, it must be setup in predecessors later.
Back end transformation should also be doable, but is it worth a new back end pass?

[nikic]

This reminds me of the SpeculateAroundPhis pass, see D37467 and D104099.

[Carrot]

In D116058#3205451, @nikic wrote:

This reminds me of the SpeculateAroundPhis pass, see D37467 and D104099.

Right, it is used to solve the same problem, but with simpler implementation. The SpeculateAroundPhis pass can handle more complex cases, but most common cases should be covered by this patch.

On the other hand, this patch doesn't have the problem reported in D104099 because foldOpIntoPhi doesn't split critical edge.

[Carrot]

ping

[nikic]

I think it's pretty clear that op(phi(c1, c2)) to phi(op(c1), op(c2)) is not the correct canonicalization for the middle-end optimizer, because it increases redundancy. Materialization of phi operands is firmly a backend matter, and this transform should live somewhere in the backend IR pipeline. I do agree that the general idea makes sense if done right (i.e. not overly aggressive, as SpeculateAroundPhis was).

[spatel]

In D116058#3233557, @nikic wrote:

I think it's pretty clear that op(phi(c1, c2)) to phi(op(c1), op(c2)) is not the correct canonicalization for the middle-end optimizer, because it increases redundancy. Materialization of phi operands is firmly a backend matter, and this transform should live somewhere in the backend IR pipeline. I do agree that the general idea makes sense if done right (i.e. not overly aggressive, as SpeculateAroundPhis was).

Agree - I think the first test diff (shrinkLogicAndPhi1) is the inverse of what -simplifycfg would try to do, so this is too general. Alternative patches that should solve the motivating bug are proposed in D115914 and D117110

[davidxl]

Just want to point out that this optimization does not introduce redundancy with diamond shape CFG and care needs to be taken for triangular shaped CFG. it might also increase code size though depending on the target -- it might need to be guarded against size optimization.

Some test case change analysis:

1. llvm/test/Transforms/InstCombine/zext-or-icmp.ll -- the patch produces much *cleaner* code

2. llvm/test/Transforms/InstCombine/rem.ll --- need to examine why the patch blocks the intended hoisting transformation. Note that the intended the transformation may introduce redundancy depending on branch probablities.

3. llvm/test/Transforms/InstCombine/phi.ll --- the patch produces *cleaner* and *neater* code

4. llvm/test/Transforms/InstCombine/not-add.ll -- the patch produces cleaner code with less redundancy

5. llvm/test/Transforms/InstCombine/narrow.ll -- this is the case Sanjay pointed out. There is potential redundancy introduced with the patch.

If issue in 5) can be detected, all in all this patch can improve IR quality.

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
   if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
                           m_c_And(m_Deferred(A), m_Deferred(B))))) {
     // Replacing operands in-place to preserve nuw/nsw flags.
     replaceOperand(I, 0, A);
     replaceOperand(I, 1, B);
     return &I;
   }
 
+  // Try to fold add PHI(constant).
+  if (PHINode *PN = dyn_cast<PHINode>(LHS))
+    if (Instruction *R = foldOpIntoPhi(I, PN))
+      return R;
+
   // TODO(jingyue): Consider willNotOverflowSignedAdd and
   // willNotOverflowUnsignedAdd to reduce the number of invocations of
   // computeKnownBits.
   bool Changed = false;
   if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

Instruction *InstCombinerImpl::foldPHIArgBinOpIntoPHI(PHINode &PN) {
   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
   assert(isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst));
   unsigned Opc = FirstInst->getOpcode();
   Value *LHSVal = FirstInst->getOperand(0);
   Value *RHSVal = FirstInst->getOperand(1);
 
   Type *LHSType = LHSVal->getType();
   Type *RHSType = RHSVal->getType();
+  unsigned LHSNonConst = !isa<Constant>(FirstInst->getOperand(0));
+  unsigned RHSNonConst = !isa<Constant>(FirstInst->getOperand(1));
 
   // Scan to see if all operands are the same opcode, and all have one user.
   for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
     Instruction *I = dyn_cast<Instruction>(PN.getIncomingValue(i));
     if (!I || I->getOpcode() != Opc || !I->hasOneUser() ||
         // Verify type of the LHS matches so we don't fold cmp's of different
         // types.
         I->getOperand(0)->getType() != LHSType ||
         I->getOperand(1)->getType() != RHSType)
       return nullptr;
 
     // If they are CmpInst instructions, check their predicates
     if (CmpInst *CI = dyn_cast<CmpInst>(I))
       if (CI->getPredicate() != cast<CmpInst>(FirstInst)->getPredicate())
         return nullptr;
 
     // Keep track of which operand needs a phi node.
     if (I->getOperand(0) != LHSVal) LHSVal = nullptr;
     if (I->getOperand(1) != RHSVal) RHSVal = nullptr;
+
+    if (!isa<Constant>(I->getOperand(0))) LHSNonConst++;
+    if (!isa<Constant>(I->getOperand(1))) RHSNonConst++;
   }
 
+  // If most of the PHI candidates are const, don't do this transformation,
+  // because materialization of const still needs instructions.
+  if (LHSNonConst <= 1) RHSVal = nullptr;
+  if (RHSNonConst <= 1) LHSVal = nullptr;
+
   // If both LHS and RHS would need a PHI, don't do this transformation,
   // because it would increase the number of PHIs entering the block,
   // which leads to higher register pressure. This is especially
   // bad when the PHIs are in the header of a loop.
   if (!LHSVal && !RHSVal)
     return nullptr;
 
   // Otherwise, this is safe to transform!

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

if (isa<Constant>(Op0))
     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
       if (Instruction *R = FoldOpIntoSelect(I, SI))
         return R;
 
   if (Constant *CUI = dyn_cast<Constant>(Op1))
     if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
       return Res;
 
+  if (isa<SelectInst>(Op1) || isa<PHINode>(Op1))
+    if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I))
+      return FoldedShift;
+
   if (auto *NewShift = cast_or_null<Instruction>(
           reassociateShiftAmtsOfTwoSameDirectionShifts(&I, SQ)))
     return NewShift;
 
   // (C1 shift (A add C2)) -> (C1 shift C2) shift A)
   // iff A and C2 are both positive.
   Value *A;
   Constant *C;
Instruction *InstCombinerImpl::FoldShiftByConstant(Value *Op0, Constant *Op1,
   // See if we can simplify any instructions used by the instruction whose sole
   // purpose is to compute bits we don't care about.
   Type *Ty = I.getType();
   unsigned TypeBits = Ty->getScalarSizeInBits();
   assert(!Op1C->uge(TypeBits) &&
          "Shift over the type width should have been removed already");
   (void)TypeBits;
 
-  if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I))
-    return FoldedShift;
-
   if (!Op0->hasOneUse())
     return nullptr;
 
   if (auto *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
     // If the operand is a bitwise operator with a constant RHS, and the
     // shift is the only use, we can pull it out of the shift.
     const APInt *Op0C;
     if (match(Op0BO->getOperand(1), m_APInt(Op0C))) {

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombinerImpl::FoldOpIntoSelect(Instruction &Op,
   }
 
   Value *NewTV = foldOperationIntoSelectOperand(Op, TV, Builder);
   Value *NewFV = foldOperationIntoSelectOperand(Op, FV, Builder);
   return SelectInst::Create(SI->getCondition(), NewTV, NewFV, "", nullptr, SI);
 }
 
 static Value *foldOperationIntoPhiValue(BinaryOperator *I, Value *InV,
+                                        Value *OtherOp, bool PhiIsLHS,
+                                        BasicBlock *PredBB,
                                         InstCombiner::BuilderTy &Builder) {
-  bool ConstIsRHS = isa<Constant>(I->getOperand(1));
-  Constant *C = cast<Constant>(I->getOperand(ConstIsRHS));
-
-  if (auto *InC = dyn_cast<Constant>(InV)) {
-    if (ConstIsRHS)
-      return ConstantExpr::get(I->getOpcode(), InC, C);
-    return ConstantExpr::get(I->getOpcode(), C, InC);
-  }
-
-  Value *Op0 = InV, *Op1 = C;
-  if (!ConstIsRHS)
+  Value *Op0 = InV, *Op1 = OtherOp;
+  if (!PhiIsLHS)
     std::swap(Op0, Op1);
 
+  auto *C0 = dyn_cast<Constant>(Op0);
+  auto *C1 = dyn_cast<Constant>(Op1);
+  if (C0 && C1)
+    return ConstantExpr::get(I->getOpcode(), C0, C1);
+
+  Builder.SetInsertPoint(PredBB->getTerminator());
   Value *RI = Builder.CreateBinOp(I->getOpcode(), Op0, Op1, "phi.bo");
   auto *FPInst = dyn_cast<Instruction>(RI);
   if (FPInst && isa<FPMathOperator>(FPInst))
     FPInst->copyFastMathFlags(I);
   return RI;
 }
 
 Instruction *InstCombinerImpl::foldOpIntoPhi(Instruction &I, PHINode *PN) {
   unsigned NumPHIValues = PN->getNumIncomingValues();
   if (NumPHIValues == 0)
     return nullptr;
+  if (I.getParent() != PN->getParent())
+    return nullptr;
 
   // We normally only transform phis with a single use.  However, if a PHI has
   // multiple uses and they are all the same operation, we can fold *all* of the
   // uses into the PHI.
   if (!PN->hasOneUse()) {
     // Walk the use list for the instruction, comparing them to I.
     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 if all of the operands of the PHI are simple constants
   // (constantint/constantfp/undef).  If there is one non-constant value,
   // remember the BB it is in.  If there is more than one or if *it* is a PHI,
   // bail out.  We don't do arbitrary constant expressions here because moving
   // their computation can be expensive without a cost model.
   BasicBlock *NonConstBB = nullptr;
+  BasicBlock *DominatorBB = nullptr;
   for (unsigned i = 0; i != NumPHIValues; ++i) {
     Value *InVal = PN->getIncomingValue(i);
+    BasicBlock *PredBB = PN->getIncomingBlock(i);
+    if (DT.dominates(PredBB, PN->getParent()))
+      DominatorBB = PredBB;
+
     // For non-freeze, require constant operand
     // For freeze, require non-undef, non-poison operand
     if (!isa<FreezeInst>(I) && match(InVal, m_ImmConstant()))
       continue;
     if (isa<FreezeInst>(I) && isGuaranteedNotToBeUndefOrPoison(InVal))
       continue;
 
     if (isa<PHINode>(InVal)) return nullptr;  // Itself a phi.
Instruction *InstCombinerImpl::foldOpIntoPhi(Instruction &I, PHINode *PN) {
   // do this if the pred block is unconditionally branching into the phi block.
   // Also, make sure that the pred block is not dead code.
   if (NonConstBB != nullptr) {
     BranchInst *BI = dyn_cast<BranchInst>(NonConstBB->getTerminator());
     if (!BI || !BI->isUnconditional() || !DT.isReachableFromEntry(NonConstBB))
       return nullptr;
   }
 
+  // If we have
+  //   %p = phi  [c1, pred1], [c2, pred2]
+  //   %v = add %p, %op
+  //
+  // We'll generate immediate materialization instructions in predecessors. We
+  // can directly fold them into ALU instructions.
+  //
+  //pred1:
+  //   %op1 = add c1, %op
+  //   br %bb
+  //pred2:
+  //   %op2 = add c2, %op
+  //   br %bb
+  //bb:
+  //   %v = phi [%op1, pred1], [%op2, pred2]
+  bool PhiIsLHS = false;
+  Value *OtherOp = I.getOperand(0);
+  Instruction *OtherI = nullptr;;
+  if (auto *BO = dyn_cast<BinaryOperator>(&I)) {
+    if (dyn_cast<PHINode>(OtherOp) == PN) {
+      OtherOp = BO->getOperand(1);
+      PhiIsLHS = true;
+    }
+    if (!isa<Constant>(OtherOp)) {
+      if (!I.getType()->isIntegerTy())
+        return nullptr;
+      OtherI = dyn_cast<Instruction>(OtherOp);
+      if (OtherI) {
+        if (I.getParent() == OtherI->getParent()) {
+          // If I depends on other instructions in the same BB, check if we can
+          // move them into a dominator. For simplicity we handle only 1
+          // instruction.
+          if (!DominatorBB)
+            return nullptr;
+          if (!isa<PHINode>(OtherI) && mayBeMemoryDependent(*OtherI))
+            return nullptr;
+          for (int i = 0, e = OtherI->getNumOperands(); i != e; ++i) {
+            auto *OpI = dyn_cast<Instruction>(OtherI->getOperand(i));
+            if (OpI && I.getParent() == OpI->getParent())
+              return nullptr;
+          }
+        }
+        else
+          OtherI = nullptr;
+      } else if (!isa<Argument>(OtherOp))
+        return nullptr;
+    }
+  }
+
   // Okay, we can do the transformation: create the new PHI node.
   PHINode *NewPN = PHINode::Create(I.getType(), PN->getNumIncomingValues());
   InsertNewInstBefore(NewPN, *PN);
   NewPN->takeName(PN);
 
   // If we are going to have to insert a new computation, do so right before the
   // predecessor's terminator.
   if (NonConstBB)
for (unsigned i = 0; i != NumPHIValues; ++i) {
       if (auto *InC = dyn_cast<Constant>(PN->getIncomingValue(i)))
         InV = ConstantExpr::getCompare(CI->getPredicate(), InC, C);
       else
         InV = Builder.CreateCmp(CI->getPredicate(), PN->getIncomingValue(i),
                                 C, "phi.cmp");
       NewPN->addIncoming(InV, PN->getIncomingBlock(i));
     }
   } else if (auto *BO = dyn_cast<BinaryOperator>(&I)) {
+    PHINode *OtherPN = nullptr;
+    if (OtherI) {
+      OtherPN = dyn_cast<PHINode>(OtherI);
+      if (!OtherPN)
+        OtherI->moveBefore(DominatorBB->getTerminator());
+    }
     for (unsigned i = 0; i != NumPHIValues; ++i) {
+      if (OtherPN)
+        OtherOp = OtherPN->getIncomingValue(i);
       Value *InV = foldOperationIntoPhiValue(BO, PN->getIncomingValue(i),
-                                             Builder);
+                                             OtherOp, PhiIsLHS,
+                                             PN->getIncomingBlock(i), Builder);
       NewPN->addIncoming(InV, PN->getIncomingBlock(i));
     }
   } else if (isa<FreezeInst>(&I)) {
     for (unsigned i = 0; i != NumPHIValues; ++i) {
       Value *InV;
       if (NonConstBB == PN->getIncomingBlock(i))
         InV = Builder.CreateFreeze(PN->getIncomingValue(i), "phi.fr");
       else
for (User *U : make_early_inc_range(PN->users())) {
     if (User == &I) continue;
     replaceInstUsesWith(*User, NewPN);
     eraseInstFromFunction(*User);
   }
   return replaceInstUsesWith(I, NewPN);
 }
 
 Instruction *InstCombinerImpl::foldBinOpIntoSelectOrPhi(BinaryOperator &I) {
+  if (auto *Sel = dyn_cast<SelectInst>(I.getOperand(0))) {
     if (!isa<Constant>(I.getOperand(1)))
       return nullptr;
-
-  if (auto *Sel = dyn_cast<SelectInst>(I.getOperand(0))) {
     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>(I.getOperand(0)))
+      if (Instruction *NewPhi = foldOpIntoPhi(I, PN))
+        return NewPhi;
+    if (auto *PN = dyn_cast<PHINode>(I.getOperand(1)))
       if (Instruction *NewPhi = foldOpIntoPhi(I, PN))
         return NewPhi;
   }
   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.

llvm/test/Transforms/InstCombine/narrow.ll

 }
 
 ; FIXME:
 ; Narrowing should work with an 'xor' and is not limited to bool types.
 
 define i32 @shrinkLogicAndPhi1(i8 %x, i1 %cond) {
 ; CHECK-LABEL: @shrinkLogicAndPhi1(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
+; CHECK-NEXT:    [[PHI_BO:%.*]] = xor i32 [[ZEXT]], 21
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF:%.*]], label [[ENDIF:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[PHI_BO1:%.*]] = xor i32 [[ZEXT]], 33
 ; CHECK-NEXT:    br label [[ENDIF]]
 ; CHECK:       endif:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 21, [[ENTRY:%.*]] ], [ 33, [[IF]] ]
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
-; CHECK-NEXT:    [[LOGIC:%.*]] = xor i32 [[PHI]], [[ZEXT]]
-; CHECK-NEXT:    ret i32 [[LOGIC]]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[PHI_BO]], [[ENTRY:%.*]] ], [ [[PHI_BO1]], [[IF]] ]
+; CHECK-NEXT:    ret i32 [[PHI]]
 ;
 entry:
   br i1 %cond, label %if, label %endif
 if:
   br label %endif
 endif:
   %phi = phi i32 [ 21, %entry], [ 33, %if ]
   %zext = zext i8 %x to i32
   %logic = xor i32 %phi, %zext
   ret i32 %logic
 }
 
 ; FIXME:
 ; Narrowing should work with an 'xor' and is not limited to bool types.
 ; Test that commuting the xor operands does not inhibit optimization.
 
 define i32 @shrinkLogicAndPhi2(i8 %x, i1 %cond) {
 ; CHECK-LABEL: @shrinkLogicAndPhi2(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
+; CHECK-NEXT:    [[PHI_BO:%.*]] = xor i32 [[ZEXT]], 21
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF:%.*]], label [[ENDIF:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[PHI_BO1:%.*]] = xor i32 [[ZEXT]], 33
 ; CHECK-NEXT:    br label [[ENDIF]]
 ; CHECK:       endif:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 21, [[ENTRY:%.*]] ], [ 33, [[IF]] ]
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
-; CHECK-NEXT:    [[LOGIC:%.*]] = xor i32 [[PHI]], [[ZEXT]]
-; CHECK-NEXT:    ret i32 [[LOGIC]]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[PHI_BO]], [[ENTRY:%.*]] ], [ [[PHI_BO1]], [[IF]] ]
+; CHECK-NEXT:    ret i32 [[PHI]]
 ;
 entry:
   br i1 %cond, label %if, label %endif
 if:
   br label %endif
 endif:
   %phi = phi i32 [ 21, %entry], [ 33, %if ]
   %zext = zext i8 %x to i32
   %logic = xor i32 %zext, %phi
   ret i32 %logic
 }
 

llvm/test/Transforms/InstCombine/not-add.ll

 
 define i32 @pr50308(i1 %c1, i32 %v1, i32 %v2, i32 %v3) {
 ; CHECK-LABEL: @pr50308(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
 ; CHECK-NEXT:    [[ADD_NOT:%.*]] = sub i32 -2, [[V1:%.*]]
 ; CHECK-NEXT:    [[ADD1_NEG:%.*]] = xor i32 [[ADD_NOT]], [[V2:%.*]]
+; CHECK-NEXT:    [[PHI_BO:%.*]] = add i32 [[ADD1_NEG]], [[V3:%.*]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
-; CHECK-NEXT:    [[COND_NEG:%.*]] = phi i32 [ [[ADD1_NEG]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[COND_NEG]], [[V3:%.*]]
-; CHECK-NEXT:    ret i32 [[SUB]]
+; CHECK-NEXT:    [[COND_NEG:%.*]] = phi i32 [ [[PHI_BO]], [[COND_TRUE]] ], [ [[V3]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[COND_NEG]]
 ;
 entry:
   br i1 %c1, label %cond.true, label %cond.end
 
 cond.true:
   %add = add nsw i32 1, %v1
   %xor = xor i32 %add, %v2
   %add1 = add nsw i32 1, %xor

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; If we have
+;   %p = phi  [c1, pred1], [c2, pred2]
+;   %v = add %p, %op
+;
+; We'll generate immediate materialization instructions in predecessors. We
+; can directly fold them into ALU instructions.
+;
+; pred1:
+;   %op1 = add c1, %op
+;   br %bb
+; pred2:
+;   %op2 = add c2, %op
+;   br %bb
+; bb:
+;   %v = phi [%op1, pred1], [%op2, pred2]
+
+; Basic case.
+define zeroext i1 @test1(i32 %s, i32* %ptr) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[S:%.*]], 1025
+; CHECK-NEXT:    [[PHI_BO:%.*]] = and i32 [[S]], 3
+; CHECK-NEXT:    br i1 [[CMP]], label [[RETURN_SINK_SPLIT:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[S]], 4097
+; CHECK-NEXT:    [[PHI_BO1:%.*]] = and i32 [[S]], 7
+; CHECK-NEXT:    br i1 [[CMP2]], label [[RETURN_SINK_SPLIT]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[DOTSINK:%.*]] = phi i32 [ [[PHI_BO]], [[ENTRY:%.*]] ], [ [[PHI_BO1]], [[IF_ELSE]] ]
+; CHECK-NEXT:    store i32 [[DOTSINK]], i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL:%.*]] = phi i1 [ false, [[IF_ELSE]] ], [ true, [[RETURN_SINK_SPLIT]] ]
+; CHECK-NEXT:    ret i1 [[RETVAL]]
+;
+entry:
+  %cmp = icmp ult i32 %s, 1025
+  br i1 %cmp, label %return.sink.split, label %if.else
+
+if.else:
+  %cmp2 = icmp ult i32 %s, 4097
+  br i1 %cmp2, label %return.sink.split, label %return
+
+return.sink.split:
+  %.sink = phi i32 [ 3, %entry ], [ 7, %if.else ]
+  %and0 = and i32 %s, %.sink
+  store i32 %and0, i32* %ptr, align 4
+  br label %return
+
+return:
+  %retval = phi i1 [ false, %if.else ], [ true, %return.sink.split ]
+  ret i1 %retval
+}
+
+; The dependent instruction can be moved to a predecessor that is also a
+; dominator.
+define zeroext i1 @test2(i64 %s, i32* %ptr) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[S:%.*]], 1025
+; CHECK-NEXT:    [[T:%.*]] = trunc i64 [[S]] to i32
+; CHECK-NEXT:    [[PHI_BO:%.*]] = xor i32 [[T]], 3
+; CHECK-NEXT:    br i1 [[CMP]], label [[RETURN_SINK_SPLIT:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[S]], 4097
+; CHECK-NEXT:    [[PHI_BO1:%.*]] = xor i32 [[T]], 7
+; CHECK-NEXT:    br i1 [[CMP2]], label [[RETURN_SINK_SPLIT]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[DOTSINK:%.*]] = phi i32 [ [[PHI_BO]], [[ENTRY:%.*]] ], [ [[PHI_BO1]], [[IF_ELSE]] ]
+; CHECK-NEXT:    store i32 [[DOTSINK]], i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL:%.*]] = phi i1 [ false, [[IF_ELSE]] ], [ true, [[RETURN_SINK_SPLIT]] ]
+; CHECK-NEXT:    ret i1 [[RETVAL]]
+;
+entry:
+  %cmp = icmp ult i64 %s, 1025
+  br i1 %cmp, label %return.sink.split, label %if.else
+
+if.else:
+  %cmp2 = icmp ult i64 %s, 4097
+  br i1 %cmp2, label %return.sink.split, label %return
+
+return.sink.split:
+  %.sink = phi i32 [ 3, %entry ], [ 7, %if.else ]
+  %t = trunc i64 %s to i32
+  %xor0 = xor i32 %t, %.sink
+  store i32 %xor0, i32* %ptr, align 4
+  br label %return
+
+return:
+  %retval = phi i1 [ false, %if.else ], [ true, %return.sink.split ]
+  ret i1 %retval
+}
+
+; There can be 1 non-const predecessor.
+define zeroext i1 @test3(i32 %s, i32 %shm, i32* %ptr) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[S:%.*]], 1025
+; CHECK-NEXT:    [[PHI_BO:%.*]] = shl i32 [[S]], 3
+; CHECK-NEXT:    br i1 [[CMP]], label [[RETURN_SINK_SPLIT:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[PHI_BO1:%.*]] = shl i32 [[S]], [[SHM:%.*]]
+; CHECK-NEXT:    br label [[RETURN_SINK_SPLIT]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[DOTSINK:%.*]] = phi i32 [ [[PHI_BO]], [[ENTRY:%.*]] ], [ [[PHI_BO1]], [[IF_ELSE]] ]
+; CHECK-NEXT:    store i32 [[DOTSINK]], i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  %cmp = icmp ult i32 %s, 1025
+  br i1 %cmp, label %return.sink.split, label %if.else
+
+if.else:
+  br label %return.sink.split
+
+return.sink.split:
+  %.sink = phi i32 [ 3, %entry ], [ %shm, %if.else ]
+  %shl0 = shl i32 %s, %.sink
+  store i32 %shl0, i32* %ptr, align 4
+  ret i1 true
+}
+
+; One phi user depends on another phi user.
+define zeroext i1 @test4(i32 %s, i32* %ptr) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[S:%.*]], 1025
+; CHECK-NEXT:    [[PHI_BO:%.*]] = add i32 [[S]], 7
+; CHECK-NEXT:    [[PHI_BO2:%.*]] = lshr i32 [[PHI_BO]], 3
+; CHECK-NEXT:    br i1 [[CMP]], label [[RETURN_SINK_SPLIT:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[S]], 4097
+; CHECK-NEXT:    [[PHI_BO1:%.*]] = add i32 [[S]], 100
+; CHECK-NEXT:    [[PHI_BO3:%.*]] = lshr i32 [[PHI_BO1]], 7
+; CHECK-NEXT:    br i1 [[CMP2]], label [[RETURN_SINK_SPLIT]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[DOTSINK:%.*]] = phi i32 [ [[PHI_BO2]], [[ENTRY:%.*]] ], [ [[PHI_BO3]], [[IF_ELSE]] ]
+; CHECK-NEXT:    store i32 [[DOTSINK]], i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL:%.*]] = phi i1 [ false, [[IF_ELSE]] ], [ true, [[RETURN_SINK_SPLIT]] ]
+; CHECK-NEXT:    ret i1 [[RETVAL]]
+;
+entry:
+  %cmp = icmp ult i32 %s, 1025
+  br i1 %cmp, label %return.sink.split, label %if.else
+
+if.else:
+  %cmp2 = icmp ult i32 %s, 4097
+  br i1 %cmp2, label %return.sink.split, label %return
+
+return.sink.split:
+  %.sink5 = phi i32 [ 7, %entry ], [ 100, %if.else ]
+  %.sink = phi i32 [ 3, %entry ], [ 7, %if.else ]
+  %add6 = add nuw nsw i32 %.sink5, %s
+  %shr7 = lshr i32 %add6, %.sink
+  store i32 %shr7, i32* %ptr, align 4
+  br label %return
+
+return:
+  %retval = phi i1 [ false, %if.else ], [ true, %return.sink.split ]
+  ret i1 %retval
+}
+
+; One phi user depends on another phi user which depends on a third instruction.
+define zeroext i1 @test5(i64 %s, i32* %ptr) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[S:%.*]], 1025
+; CHECK-NEXT:    [[CONV:%.*]] = trunc i64 [[S]] to i32
+; CHECK-NEXT:    [[PHI_BO:%.*]] = add i32 [[CONV]], 7
+; CHECK-NEXT:    [[PHI_BO2:%.*]] = ashr i32 [[PHI_BO]], 3
+; CHECK-NEXT:    br i1 [[CMP]], label [[RETURN_SINK_SPLIT:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[S]], 4097
+; CHECK-NEXT:    [[PHI_BO1:%.*]] = add i32 [[CONV]], 100
+; CHECK-NEXT:    [[PHI_BO3:%.*]] = ashr i32 [[PHI_BO1]], 7
+; CHECK-NEXT:    br i1 [[CMP2]], label [[RETURN_SINK_SPLIT]], label [[RETURN:%.*]]
+; CHECK:       return.sink.split:
+; CHECK-NEXT:    [[DOTSINK:%.*]] = phi i32 [ [[PHI_BO2]], [[ENTRY:%.*]] ], [ [[PHI_BO3]], [[IF_ELSE]] ]
+; CHECK-NEXT:    store i32 [[DOTSINK]], i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL:%.*]] = phi i1 [ false, [[IF_ELSE]] ], [ true, [[RETURN_SINK_SPLIT]] ]
+; CHECK-NEXT:    ret i1 [[RETVAL]]
+;
+entry:
+  %cmp = icmp ult i64 %s, 1025
+  br i1 %cmp, label %return.sink.split, label %if.else
+
+if.else:
+  %cmp2 = icmp ult i64 %s, 4097
+  br i1 %cmp2, label %return.sink.split, label %return
+
+return.sink.split:
+  %.sink5 = phi i32 [ 7, %entry ], [ 100, %if.else ]
+  %.sink = phi i32 [ 3, %entry ], [ 7, %if.else ]
+  %conv = trunc i64 %s to i32
+  %add6 = add nuw nsw i32 %.sink5, %conv
+  %shr7 = ashr i32 %add6, %.sink
+  store i32 %shr7, i32* %ptr, align 4
+  br label %return
+
+return:
+  %retval = phi i1 [ false, %if.else ], [ true, %return.sink.split ]
+  ret i1 %retval
+}
+
+; Both operands are phi.
+define i64 @test6(i1 %cond, i64 ()* %p) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[RETURN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i64 [[P:%.*]]()
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[P2:%.*]] = phi i64 [ [[CALL]], [[IF_END]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i64 [[P2]]
+;
+entry:
+  br i1 %cond, label %return, label %if.end
+
+if.end:
+  %call = tail call i64 %p()
+  %high = and i64 %call, -4294967296
+  %low = and i64 %call, 4294967295
+  br label %return
+
+return:
+  %p1 = phi i64 [ %low, %if.end ], [ 0, %entry ]
+  %p2 = phi i64 [ %high, %if.end ], [ 0, %entry ]
+  %v = or i64 %p2, %p1
+  ret i64 %v
+}

llvm/test/Transforms/InstCombine/phi.ll

end:
   %z = call i1 @test11a()
   ret i1 %z
 }
 
 
 define i64 @test12(i1 %cond, i8* %Ptr, i64 %Val) {
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[T41:%.*]] = ptrtoint i8* [[PTR:%.*]] to i64
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[END:%.*]], label [[TWO:%.*]]
 ; CHECK:       two:
+; CHECK-NEXT:    [[PHI_BO5:%.*]] = add i64 [[T41]], [[VAL:%.*]]
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[T869_0_OFF64:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[VAL:%.*]], [[TWO]] ]
-; CHECK-NEXT:    [[T41:%.*]] = ptrtoint i8* [[PTR:%.*]] to i64
-; CHECK-NEXT:    [[T2:%.*]] = add i64 [[T869_0_OFF64]], [[T41]]
-; CHECK-NEXT:    ret i64 [[T2]]
+; CHECK-NEXT:    [[T869_0_OFF64:%.*]] = phi i64 [ [[T41]], [[ENTRY:%.*]] ], [ [[PHI_BO5]], [[TWO]] ]
+; CHECK-NEXT:    ret i64 [[T869_0_OFF64]]
 ;
 entry:
   %t41 = ptrtoint i8* %Ptr to i64
   %t42 = zext i64 %t41 to i128
   br i1 %cond, label %end, label %two
 
 two:
   %t36 = zext i64 %Val to i128            ; <i128> [#uses=1]

llvm/test/Transforms/InstCombine/rem.ll

 }
 
 define i32 @pr27968_3(i1 %c0, i1 %always_false, i32* %p) {
 ; CHECK-LABEL: @pr27968_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C0:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[V:%.*]] = load volatile i32, i32* [[P:%.*]], align 4
-; CHECK-NEXT:    [[PHI_BO:%.*]] = and i32 [[V]], 2147483647
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[LHS:%.*]] = phi i32 [ [[PHI_BO]], [[IF_THEN]] ], [ 5, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[LHS:%.*]] = phi i32 [ [[V]], [[IF_THEN]] ], [ 5, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br i1 [[ALWAYS_FALSE:%.*]], label [[REM_IS_SAFE:%.*]], label [[REM_IS_UNSAFE:%.*]]
 ; CHECK:       rem.is.safe:
-; CHECK-NEXT:    ret i32 [[LHS]]
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[LHS]], 2147483647
+; CHECK-NEXT:    ret i32 [[REM]]
 ; CHECK:       rem.is.unsafe:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   br i1 %c0, label %if.then, label %if.end
 
 if.then:
   %v = load volatile i32, i32* %p

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: