[InstCombine] try to fold binop with phi operands

[spatel]

Summary

This is an alternate version of D115914 that handles/tests all binary opcodes. I think it is close to the same logic, but I was having a hard time making sense of the diffs/comments in that patch, so I just wrote the patch from scratch.

I suspect that we don't see these patterns too often because -simplifycfg would convert the minimal cases into selects rather than leave them in phi form (note: instcombine has logic holes for combining the select patterns too though, so that's another potential patch).

We only create a new binop in a predecessor that unconditionally branches to the final block.
https://alive2.llvm.org/ce/z/C57M2F
https://alive2.llvm.org/ce/z/WHwAoU (not safe to speculate an sdiv for example)
https://alive2.llvm.org/ce/z/rdVUvW (but it is ok on this path)

[lebedev.ri]

This comment was removed by lebedev.ri.

[lebedev.ri]

What about the case where one PHI is fully constant: https://godbolt.org/z/16W8oGYv3 ?

[spatel]

In D117110#3237366, @lebedev.ri wrote:

What about the case where one PHI is fully constant: https://godbolt.org/z/16W8oGYv3 ?

Hmm...so we convert that into a binop with constant operand, and I thought we'd then get that pattern within InstCombinerImpl::foldOpIntoPhi(). But there's an extra clause in that code that is likely also needed here:

// If there is exactly one non-constant value, we can insert a copy of the
// operation in that block.  However, if this is a critical edge, we would be
// inserting the computation on some other paths (e.g. inside a loop).  Only
// do this if the pred block is unconditionally branching into the phi block.
// Also, make sure that the pred block is not dead code.

[spatel]

Patch updated:

1. Added the necessary clause that prevents hoisting into a conditional predecessor (and more tests).
2. Added a TODO for handling phi with 2 constant incoming values (not sure yet if that's reliably handled by simplifycfg and/or other instcombines).

[aeubanks]

is it possible that we're hoisting a non-speculatable operation past something like a call in the same block?

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

42

these tests need to be changed to preserve testing of https://reviews.llvm.org/D30781

[lebedev.ri]

In D117110#3237746, @aeubanks wrote:

is it possible that we're hoisting a non-speculatable operation past something like a call in the same block?

Indeed. If the binop is not freely speculatable, then we need to check that it is guaranteed to be executed: https://alive2.llvm.org/ce/z/VqvC_r

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1299–1301

This is too restrictive (please add a fixme?)
https://alive2.llvm.org/ce/z/kKuiW9 vs https://alive2.llvm.org/ce/z/SJ9oYU

[mingmingl]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1329–1334

I'm wondering if it's idiomatic to validate that this instruction could also be simplified away in later iterations of instruction-combine, and only proceed with the fold if yes.

e.g., in https://godbolt.org/z/fKfondqrn, %res = or i64 %retval.sroa.3.0.extract.shift, %phi.cast instruction is inserted into if.then block, and could be simplified away.

[lebedev.ri]

(as per previous comments regarding UB introduction)

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1329–1334

In general, instcombine tries to do the smallest transform that still results in an improvement. It can then chain together a series of minimal transforms to achieve the larger goal.

So if we can make this patch safe and still profitable while creating a new binop, then that's better than limiting a larger transform to the case where we eliminate the binop completely.

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

42

I think these tests were already altered enough (there's no shift remaining in the existing CHECK lines) that they don't test the original problem (undefined shift). I'll try to come up with another way to cover that path.

[spatel]

Patch updated:

1. Added check for isGuaranteedToTransferExecutionToSuccessor() to make sure the binop is executed.
2. Added TODO comment/test for binop in different block than phi.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1293–1297

the fixme

// TODO: This could miss matching a phi with 2 constant incoming values.

should be here, because uniform constant phi will be simplified into a plain constant

1328–1333

Don't we also need isSafeToSpeculativelyExecute() check?

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1328–1333

That's what the TODO comment and "mul_const_incoming0_speculatable" test are referring to (if I'm understanding the question).
Ie, for correctness, I think we only need to bail out for opcodes like div/rem. But for performance (and as a conservative first step), we probably don't want to hoist anything on this path if it isn't going to be executed unconditionally. Do we know that some other pass will sink the op later if possible?

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

42

Extra test added here:
417f5f4633e

42

lost a char:
f417f5f4633e

[spatel]

Moved TODO comment higher to account for more potential patterns that could be handled here.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1297

Technically, this is wrong.

1. for switch predecessor, we could have more than a single incoming edges
2. This check is backwards. It's not really that it must have exactly two predecessors, but more that there must be at most a single predecessor with non-constant input value, otherwise we'd increase instruction count. And for constant incoming values we'll constant-fold.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1297

Can you please at least add a FIXME for these issues?

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1297

Sorry - I got distracted from this patch. I agree that this should be more like foldOpIntoPhi().
But yes, I can add a FIXME to this and follow-up. We should still get the original motivating case even with this artificial limitation.

[spatel]

Added TODO comment for follow-up enhancement - fix the incoming values check to look for max of 1 variable operand.

[lebedev.ri]

This seems fine as a first step.
Thanks

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (Value *V = SimplifyAddInst(I.getOperand(0), I.getOperand(1),
     return replaceInstUsesWith(I, V);
 
   if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   // (A*B)+(A*C) -> A*(B+C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   if (Instruction *R = factorizeMathWithShlOps(I, Builder))
     return R;
 
   if (Instruction *X = foldAddWithConstant(I))
if (Value *V = SimplifyFAddInst(I.getOperand(0), I.getOperand(1),
     return replaceInstUsesWith(I, V);
 
   if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   if (Instruction *FoldedFAdd = foldBinOpIntoSelectOrPhi(I))
     return FoldedFAdd;
 
   // (-X) + Y --> Y - X
   Value *X, *Y;
   if (match(&I, m_c_FAdd(m_FNeg(m_Value(X)), m_Value(Y))))
     return BinaryOperator::CreateFSubFMF(Y, X, &I);
 
Instruction *InstCombinerImpl::visitSub(BinaryOperator &I) {
   if (Value *V = SimplifySubInst(I.getOperand(0), I.getOperand(1),
                                  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
                                  SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   // If this is a 'B = x-(-A)', change to B = x+A.
   // We deal with this without involving Negator to preserve NSW flag.
   if (Value *V = dyn_castNegVal(Op1)) {
     BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);
 
     if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
Instruction *InstCombinerImpl::visitFSub(BinaryOperator &I) {
   if (Value *V = SimplifyFSubInst(I.getOperand(0), I.getOperand(1),
                                   I.getFastMathFlags(),
                                   getSimplifyQuery().getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   // Subtraction from -0.0 is the canonical form of fneg.
   // fsub -0.0, X ==> fneg X
   // fsub nsz 0.0, X ==> fneg nsz X
   //
   // FIXME This matcher does not respect FTZ or DAZ yet:
   // fsub -0.0, Denorm ==> +-0
   // fneg Denorm ==> -Denorm
   Value *Op;

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Value *V = SimplifyAndInst(I.getOperand(0), I.getOperand(1),
     return replaceInstUsesWith(I, V);
 
   if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   // See if we can simplify any instructions used by the instruction whose sole
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(I))
     return &I;
 
   // Do this before using distributive laws to catch simple and/or/not patterns.
   if (Instruction *Xor = foldAndToXor(I, Builder))
     return Xor;
if (Value *V = SimplifyOrInst(I.getOperand(0), I.getOperand(1),
     return replaceInstUsesWith(I, V);
 
   if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   // See if we can simplify any instructions used by the instruction whose sole
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(I))
     return &I;
 
   // Do this before using distributive laws to catch simple and/or/not patterns.
   if (Instruction *Xor = foldOrToXor(I, Builder))
     return Xor;
if (Value *V = SimplifyXorInst(I.getOperand(0), I.getOperand(1),
     return replaceInstUsesWith(I, V);
 
   if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   if (Instruction *NewXor = foldXorToXor(I, Builder))
     return NewXor;
 
   // (A&B)^(A&C) -> A&(B^C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   // See if we can simplify any instructions used by the instruction whose sole

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   Instruction *foldVectorSelect(SelectInst &Sel);
   Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
 
   /// Given a binary operator, cast instruction, or select which has a PHI node
   /// as operand #0, see if we can fold the instruction into the PHI (which is
   /// only possible if all operands to the PHI are constants).
   Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
 
+  /// For a binary operator with 2 phi operands, try to hoist the binary
+  /// operation before the phi. This can result in fewer instructions in
+  /// patterns where at least one set of phi operands simplifies.
+  /// Example:
+  /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
+  /// -->
+  /// BB1: BO = binop X, Y
+  /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
+  Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
+
   /// Given an instruction with a select as one operand and a constant as the
   /// other operand, try to fold the binary operator into the select arguments.
   /// This also works for Cast instructions, which obviously do not have a
   /// second operand.
   Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
 
   /// This is a convenience wrapper function for the above two functions.
   Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

if (Value *V = SimplifyMulInst(I.getOperand(0), I.getOperand(1),
     return replaceInstUsesWith(I, V);
 
   if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   unsigned BitWidth = I.getType()->getScalarSizeInBits();
 
   // X * -1 == 0 - X
   if (match(Op1, m_AllOnes())) {
if (Value *V = SimplifyFMulInst(I.getOperand(0), I.getOperand(1),
     return replaceInstUsesWith(I, V);
 
   if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
     return FoldedMul;
 
   if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
     return replaceInstUsesWith(I, FoldedMul);
 
   if (Instruction *R = foldFPSignBitOps(I))
     return R;
static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
   return Remainder.isMinValue();
 }
 
 /// This function implements the transforms common to both integer division
 /// instructions (udiv and sdiv). It is called by the visitors to those integer
 /// division instructions.
 /// Common integer divide transforms
 Instruction *InstCombinerImpl::commonIDivTransforms(BinaryOperator &I) {
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   bool IsSigned = I.getOpcode() == Instruction::SDiv;
   Type *Ty = I.getType();
 
   // The RHS is known non-zero.
   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
     return replaceOperand(I, 1, V);
 
Instruction *InstCombinerImpl::visitFDiv(BinaryOperator &I) {
   if (Value *V = SimplifyFDivInst(I.getOperand(0), I.getOperand(1),
                                   I.getFastMathFlags(),
                                   SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   if (Instruction *R = foldFDivConstantDivisor(I))
     return R;
 
   if (Instruction *R = foldFDivConstantDividend(I))
     return R;
 
   if (Instruction *R = foldFPSignBitOps(I))
     return R;
Instruction *InstCombinerImpl::visitFDiv(BinaryOperator &I) {
   return nullptr;
 }
 
 /// This function implements the transforms common to both integer remainder
 /// instructions (urem and srem). It is called by the visitors to those integer
 /// remainder instructions.
 /// Common integer remainder transforms
 Instruction *InstCombinerImpl::commonIRemTransforms(BinaryOperator &I) {
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   // The RHS is known non-zero.
   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
     return replaceOperand(I, 1, V);
 
   // Handle cases involving: rem X, (select Cond, Y, Z)
   if (simplifyDivRemOfSelectWithZeroOp(I))
Instruction *InstCombinerImpl::visitFRem(BinaryOperator &I) {
   if (Value *V = SimplifyFRemInst(I.getOperand(0), I.getOperand(1),
                                   I.getFastMathFlags(),
                                   SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   return nullptr;
 }

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

static Instruction *foldShiftOfShiftedLogic(BinaryOperator &I,
   // shift (logic (shift X, C0), Y), C1 -> logic (shift X, C0+C1), (shift Y, C1)
   Constant *ShiftSumC = ConstantExpr::getAdd(C0, C1);
   Value *NewShift1 = Builder.CreateBinOp(ShiftOpcode, X, ShiftSumC);
   Value *NewShift2 = Builder.CreateBinOp(ShiftOpcode, Y, I.getOperand(1));
   return BinaryOperator::Create(LogicInst->getOpcode(), NewShift1, NewShift2);
 }
 
 Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) {
+  if (Instruction *Phi = foldBinopWithPhiOperands(I))
+    return Phi;
+
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   assert(Op0->getType() == Op1->getType());
 
   // If the shift amount is a one-use `sext`, we can demote it to `zext`.
   Value *Y;
   if (match(Op1, m_OneUse(m_SExt(m_Value(Y))))) {
     Value *NewExt = Builder.CreateZExt(Y, I.getType(), Op1->getName());
     return BinaryOperator::Create(I.getOpcode(), Op0, NewExt);

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::foldBinopWithPhiOperands(BinaryOperator &BO) {
+  auto *Phi0 = dyn_cast<PHINode>(BO.getOperand(0));
+  auto *Phi1 = dyn_cast<PHINode>(BO.getOperand(1));
+  if (!Phi0 || !Phi1 || !Phi0->hasOneUse() || !Phi1->hasOneUse() ||
+      Phi0->getNumOperands() != 2 || Phi1->getNumOperands() != 2)
+    return nullptr;
+
+  // TODO: Remove the restriction for binop being in the same block as the phis.
+  if (BO.getParent() != Phi0->getParent() ||
+      BO.getParent() != Phi1->getParent())
+    return nullptr;
+
+  // Match a pair of incoming constants for one of the predecessor blocks.
+  // TODO: This could miss matching a phi with 2 constant incoming values.
+  BasicBlock *ConstBB, *OtherBB;
+  Constant *C0, *C1;
+  if (match(Phi0->getIncomingValue(0), m_ImmConstant(C0))) {
+    ConstBB = Phi0->getIncomingBlock(0);
+    OtherBB = Phi0->getIncomingBlock(1);
+  } else if (match(Phi0->getIncomingValue(1), m_ImmConstant(C0))) {
+    ConstBB = Phi0->getIncomingBlock(1);
+    OtherBB = Phi0->getIncomingBlock(0);
+  } else {
+    return nullptr;
+  }
+  if (!match(Phi1->getIncomingValueForBlock(ConstBB), m_ImmConstant(C1)))
+    return nullptr;
+
+  // The block that we are hoisting to must reach here unconditionally.
+  // Otherwise, we could be speculatively executing an expensive or
+  // non-speculative op.
+  auto *PredBlockBranch = dyn_cast<BranchInst>(OtherBB->getTerminator());
+  if (!PredBlockBranch || PredBlockBranch->isConditional() ||
+      !DT.isReachableFromEntry(OtherBB))
+    return nullptr;
+
+  // TODO: This check could be tightened to only apply to binops (div/rem) that
+  //       are not safe to speculatively execute. But that could allow hoisting
+  //       potentially expensive instructions (fdiv for example).
+  for (auto BBIter = BO.getParent()->begin(); &*BBIter != &BO; ++BBIter)
+    if (!isGuaranteedToTransferExecutionToSuccessor(&*BBIter))
+      return nullptr;
+
+  // Make a new binop in the predecessor block with the non-constant incoming
+  // values.
+  Builder.SetInsertPoint(PredBlockBranch);
+  Value *NewBO = Builder.CreateBinOp(BO.getOpcode(),
+                                     Phi0->getIncomingValueForBlock(OtherBB),
+                                     Phi1->getIncomingValueForBlock(OtherBB));
+  if (auto *NotFoldedNewBO = dyn_cast<BinaryOperator>(NewBO))
+    NotFoldedNewBO->copyIRFlags(&BO);
+
+  // Fold constants for the predecessor block with constant incoming values.
+  Constant *NewC = ConstantExpr::get(BO.getOpcode(), C0, C1);
+
+  // Replace the binop with a phi of the new values. The old phis are dead.
+  PHINode *NewPhi = PHINode::Create(BO.getType(), 2);
+  NewPhi->addIncoming(NewBO, OtherBB);
+  NewPhi->addIncoming(NewC, ConstBB);
+  return NewPhi;
+}
+
 Instruction *InstCombinerImpl::foldBinOpIntoSelectOrPhi(BinaryOperator &I) {
   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))) {

llvm/test/Transforms/InstCombine/binop-phi-operands.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 declare void @use(i32)
 declare void @sideeffect()
 
+; negative test (but we could allow this?) - don't hoist to conditional predecessor block
+
 define i32 @add_const_incoming0_speculative(i1 %b, i32 %x, i32 %y) {
 ; CHECK-LABEL: @add_const_incoming0_speculative(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[P0:%.*]] = phi i32 [ 42, [[IF]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
then:
   ret i32 %r
 }
 
 define i32 @add_const_incoming0_nonspeculative(i1 %b, i32 %x, i32 %y) {
 ; CHECK-LABEL: @add_const_incoming0_nonspeculative(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i32 [ 42, [[ENTRY:%.*]] ], [ [[X:%.*]], [[IF]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i32 [ 17, [[ENTRY]] ], [ [[Y:%.*]], [[IF]] ]
-; CHECK-NEXT:    [[R:%.*]] = add i32 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF]] ], [ 59, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i32 [ 42, %entry ], [ %x, %if ]
   %p1 = phi i32 [ 17, %entry ], [ %y, %if ]
   %r = add i32 %p0, %p1
   ret i32 %r
 }
 
+; negative test (but we could allow this?) - don't hoist to conditional predecessor block
+
 define i32 @sub_const_incoming0(i1 %b, i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_const_incoming0(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[P0:%.*]] = phi i32 [ 42, [[IF]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
then:
   ret i32 %r
 }
 
 define i32 @sub_const_incoming1(i1 %b, i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i32 [ [[X:%.*]], [[IF]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i32 [ [[Y:%.*]], [[IF]] ], [ 17, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = sub i32 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF]] ], [ 25, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i32 [ %x, %if ], [ 42, %entry ]
   %p1 = phi i32 [ %y, %if ], [ 17, %entry ]
   %r = sub i32 %p0, %p1
   ret i32 %r
 }
 
 define i8 @mul_const_incoming1(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @mul_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = mul i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ [[X:%.*]], [[IF]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ [[Y:%.*]], [[IF]] ], [ 17, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = mul i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ -54, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i8 [ %x, %if ], [ 42, %entry ]
   %p1 = phi i8 [ %y, %if ], [ 17, %entry ]
   %r = mul i8 %p0, %p1
   ret i8 %r
 }
 
 define i8 @and_const_incoming1(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @and_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ [[X:%.*]], [[IF]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ [[Y:%.*]], [[IF]] ], [ 17, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i8 [ %x, %if ], [ 42, %entry ]
   %p1 = phi i8 [ %y, %if ], [ 17, %entry ]
   %r = and i8 %p0, %p1
   ret i8 %r
 }
 
 define i8 @xor_const_incoming1(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @xor_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ [[X:%.*]], [[IF]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ [[Y:%.*]], [[IF]] ], [ 17, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ 59, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i8 [ %x, %if ], [ 42, %entry ]
   %p1 = phi i8 [ %y, %if ], [ 17, %entry ]
   %r = xor i8 %p0, %p1
   ret i8 %r
 }
 
 define i64 @or_const_incoming1(i1 %b, i64 %x, i64 %y) {
 ; CHECK-LABEL: @or_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = or i64 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i64 [ [[X:%.*]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i64 [ [[Y:%.*]], [[IF]] ], [ 16, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = or i64 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i64 [ [[TMP0]], [[IF]] ], [ 19, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i64 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i64 [ %x, %if ], [ 3, %entry ]
   %p1 = phi i64 [ %y, %if ], [ 16, %entry ]
   %r = or i64 %p0, %p1
   ret i64 %r
 }
 
 define i64 @or_const_incoming01(i1 %b, i64 %x, i64 %y) {
 ; CHECK-LABEL: @or_const_incoming01(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = or i64 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i64 [ 3, [[ENTRY:%.*]] ], [ [[X:%.*]], [[IF]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i64 [ 16, [[ENTRY]] ], [ [[Y:%.*]], [[IF]] ]
-; CHECK-NEXT:    [[R:%.*]] = or i64 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i64 [ [[TMP0]], [[IF]] ], [ 19, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i64 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i64 [ 3, %entry ], [ %x, %if]
   %p1 = phi i64 [ %y, %if ], [ 16, %entry ]
   %r = or i64 %p0, %p1
   ret i64 %r
 }
 
 define i64 @or_const_incoming10(i1 %b, i64 %x, i64 %y) {
 ; CHECK-LABEL: @or_const_incoming10(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = or i64 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i64 [ [[Y:%.*]], [[IF]] ], [ 16, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i64 [ [[X:%.*]], [[IF]] ], [ 3, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = or i64 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i64 [ [[TMP0]], [[IF]] ], [ 19, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i64 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i64 [ %y, %if ], [ 16, %entry ]
   %p1 = phi i64 [ 3, %entry ], [ %x, %if]
   %r = or i64 %p0, %p1
   ret i64 %r
 }
 
+; negative test (but we could allow this?) - don't hoist to conditional predecessor block
+
 define i8 @ashr_const_incoming0_speculative(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @ashr_const_incoming0_speculative(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ 42, [[IF]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
then:
   ret i8 %r
 }
 
 define i8 @ashr_const_incoming0(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @ashr_const_incoming0(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = ashr i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ 42, [[ENTRY:%.*]] ], [ [[X:%.*]], [[IF]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ 3, [[ENTRY]] ], [ [[Y:%.*]], [[IF]] ]
-; CHECK-NEXT:    [[R:%.*]] = ashr i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ 5, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i8 [ 42, %entry ], [ %x, %if ]
   %p1 = phi i8 [ 3, %entry ], [ %y, %if ]
   %r = ashr i8 %p0, %p1
   ret i8 %r
 }
 
 define i8 @lshr_const_incoming1(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @lshr_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = lshr i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ [[X:%.*]], [[IF]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ [[Y:%.*]], [[IF]] ], [ 3, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = lshr i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ 5, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i8 [ %x, %if ], [ 42, %entry ]
   %p1 = phi i8 [ %y, %if ], [ 3, %entry ]
   %r = lshr i8 %p0, %p1
   ret i8 %r
 }
 
 define i8 @shl_const_incoming1(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @shl_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ [[X:%.*]], [[IF]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ [[Y:%.*]], [[IF]] ], [ 3, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = shl nuw nsw i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ 80, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
then:
   ret i8 %r
 }
 
 define i8 @sdiv_const_incoming1(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @sdiv_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = sdiv i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ [[X:%.*]], [[IF]] ], [ -42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ [[Y:%.*]], [[IF]] ], [ 17, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ -2, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i8 [ %x, %if ], [ -42, %entry ]
   %p1 = phi i8 [ %y, %if ], [ 17, %entry ]
   %r = sdiv i8 %p0, %p1
   ret i8 %r
 }
 
 define i8 @udiv_const_incoming1(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ [[X:%.*]], [[IF]] ], [ -42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ [[Y:%.*]], [[IF]] ], [ 17, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = udiv i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ 12, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i8 [ %x, %if ], [ -42, %entry ]
   %p1 = phi i8 [ %y, %if ], [ 17, %entry ]
   %r = udiv i8 %p0, %p1
   ret i8 %r
 }
 
 define i8 @srem_const_incoming1(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @srem_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = srem i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ [[X:%.*]], [[IF]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ [[Y:%.*]], [[IF]] ], [ -17, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ 8, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i8 [ %x, %if ], [ 42, %entry ]
   %p1 = phi i8 [ %y, %if ], [ -17, %entry ]
   %r = srem i8 %p0, %p1
   ret i8 %r
 }
 
 define i8 @urem_const_incoming1(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @urem_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = urem i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ [[X:%.*]], [[IF]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi i8 [ [[Y:%.*]], [[IF]] ], [ -17, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = urem i8 [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[IF]] ], [ 42, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi i8 [ %x, %if ], [ 42, %entry ]
   %p1 = phi i8 [ %y, %if ], [ -17, %entry ]
   %r = urem i8 %p0, %p1
   ret i8 %r
 }
 
 define float @fmul_const_incoming1(i1 %b, float %x, float %y) {
 ; CHECK-LABEL: @fmul_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = fmul float [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi float [ [[X:%.*]], [[IF]] ], [ 4.200000e+01, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi float [ [[Y:%.*]], [[IF]] ], [ 1.700000e+01, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = fmul float [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi float [ [[TMP0]], [[IF]] ], [ 7.140000e+02, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret float [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi float [ %x, %if ], [ 42.0, %entry ]
   %p1 = phi float [ %y, %if ], [ 17.0, %entry ]
   %r = fmul float %p0, %p1
   ret float %r
 }
 
 define float @fadd_const_incoming1(i1 %b, float %x, float %y) {
 ; CHECK-LABEL: @fadd_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = fadd fast float [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi float [ [[X:%.*]], [[IF]] ], [ 4.200000e+01, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi float [ [[Y:%.*]], [[IF]] ], [ 1.700000e+01, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = fadd fast float [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi float [ [[TMP0]], [[IF]] ], [ 5.900000e+01, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret float [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi float [ %x, %if ], [ 42.0, %entry ]
   %p1 = phi float [ %y, %if ], [ 17.0, %entry ]
   %r = fadd fast float %p0, %p1
   ret float %r
 }
 
 define float @fsub_const_incoming1(i1 %b, float %x, float %y) {
 ; CHECK-LABEL: @fsub_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = fsub nnan ninf float [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi float [ [[X:%.*]], [[IF]] ], [ 4.200000e+01, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi float [ [[Y:%.*]], [[IF]] ], [ 1.700000e+01, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = fsub nnan ninf float [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi float [ [[TMP0]], [[IF]] ], [ 2.500000e+01, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret float [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 
 then:
   %p0 = phi float [ %x, %if ], [ 42.0, %entry ]
   %p1 = phi float [ %y, %if ], [ 17.0, %entry ]
   %r = fsub ninf nnan float %p0, %p1
   ret float %r
 }
 
 define float @frem_const_incoming1(i1 %b, float %x, float %y) {
 ; CHECK-LABEL: @frem_const_incoming1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[TMP0:%.*]] = frem nsz float [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
-; CHECK-NEXT:    [[P0:%.*]] = phi float [ [[X:%.*]], [[IF]] ], [ 4.200000e+01, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[P1:%.*]] = phi float [ [[Y:%.*]], [[IF]] ], [ 1.700000e+01, [[ENTRY]] ]
-; CHECK-NEXT:    [[R:%.*]] = frem nsz float [[P0]], [[P1]]
+; CHECK-NEXT:    [[R:%.*]] = phi float [ [[TMP0]], [[IF]] ], [ 8.000000e+00, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret float [[R]]
 ;
 entry:
   br i1 %b, label %if, label %then
 
 if:
   br label %then
 

 
 then:
   %p0 = phi i64 [ 42, %if ], [ %x, %entry ]
   %p1 = phi i64 [ %y, %if ], [ 43, %entry ]
   %r = or i64 %p0, %p1
   ret i64 %r
 }
 
+; The mul could be hoisted before the call that may not return
+; if we are ok with speculating a potentially expensive op.
+
 define i8 @mul_const_incoming0_speculatable(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @mul_const_incoming0_speculatable(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ 42, [[ENTRY:%.*]] ], [ [[X:%.*]], [[IF]] ]

 then:
   %p0 = phi i8 [ 42, %entry ], [ %x, %if ]
   %p1 = phi i8 [ 17, %entry ], [ %y, %if ]
   call void @sideeffect()
   %r = mul i8 %p0, %p1
   ret i8 %r
 }
 
+; The udiv should never be hoisted before the call that may not return.
+
 define i8 @udiv_const_incoming0_not_speculatable(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_const_incoming0_not_speculatable(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ 42, [[ENTRY:%.*]] ], [ [[X:%.*]], [[IF]] ]

 then:
   %p0 = phi i8 [ 42, %entry ], [ %x, %if ]
   %p1 = phi i8 [ 17, %entry ], [ %y, %if ]
   call void @sideeffect()
   %r = udiv i8 %p0, %p1
   ret i8 %r
 }
 
+; TODO: It is ok to hoist the udiv even though it is not in the same block as the phis.
+
 define i8 @udiv_const_incoming0_different_block(i1 %b, i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_const_incoming0_different_block(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF:%.*]], label [[THEN:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[P0:%.*]] = phi i8 [ 42, [[ENTRY:%.*]] ], [ [[X:%.*]], [[IF]] ]

 define { i64, i32 } @ParseRetVal(i1 %b, { i64, i32 } ()* %x) {
 ; CHECK-LABEL: @ParseRetVal(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       t:
 ; CHECK-NEXT:    [[T4:%.*]] = tail call { i64, i32 } [[X:%.*]]()
 ; CHECK-NEXT:    [[T5:%.*]] = extractvalue { i64, i32 } [[T4]], 0
 ; CHECK-NEXT:    [[T6:%.*]] = extractvalue { i64, i32 } [[T4]], 1
-; CHECK-NEXT:    [[T7:%.*]] = and i64 [[T5]], -4294967296
-; CHECK-NEXT:    [[T8:%.*]] = and i64 [[T5]], 4294901760
-; CHECK-NEXT:    [[T9:%.*]] = and i64 [[T5]], 65280
-; CHECK-NEXT:    [[T10:%.*]] = and i64 [[T5]], 255
 ; CHECK-NEXT:    br label [[F]]
 ; CHECK:       f:
-; CHECK-NEXT:    [[T12:%.*]] = phi i64 [ [[T10]], [[T]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[T13:%.*]] = phi i64 [ [[T9]], [[T]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[T14:%.*]] = phi i64 [ [[T8]], [[T]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[T15:%.*]] = phi i64 [ [[T7]], [[T]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[T16:%.*]] = phi i32 [ [[T6]], [[T]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[T17:%.*]] = or i64 [[T13]], [[T12]]
-; CHECK-NEXT:    [[T18:%.*]] = or i64 [[T17]], [[T14]]
-; CHECK-NEXT:    [[T19:%.*]] = or i64 [[T18]], [[T15]]
+; CHECK-NEXT:    [[T16:%.*]] = phi i32 [ [[T6]], [[T]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[T19:%.*]] = phi i64 [ [[T5]], [[T]] ], [ 0, [[ENTRY]] ]
 ; CHECK-NEXT:    [[T20:%.*]] = insertvalue { i64, i32 } poison, i64 [[T19]], 0
 ; CHECK-NEXT:    [[T21:%.*]] = insertvalue { i64, i32 } [[T20]], i32 [[T16]], 1
 ; CHECK-NEXT:    ret { i64, i32 } [[T21]]
 ;
 entry:
   br i1 %b, label %t, label %f
 
 t:

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

;
   %zext = zext i1 %bothCond to i8
   ret i8 %zext
 }
 
 ; Here, widening the or from i1 to i32 and removing one of the icmps would
 ; widen an undef value (created by the out-of-range shift), increasing the
 ; range of valid values for the return, so we can't do it.
 
 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: