[InstCombine] Support folding a subtract with a constant LHS into a phi node

[craig.topper]

Summary

We currently only support folding a subtract into a select but not a PHI. This fixes that.

I had to fix an assumption in FoldOpIntoPhi that assumed the PHI node was always in operand 0. Now we pass it in like we do for FoldOpIntoSelect. But we still require some dancing to find the Constant when we create the BinOp or ConstantExpr. This is based code is similar to what we do for selects.

[spatel]

LGTM. See inline comments for a couple of minor bits.

lib/Transforms/InstCombine/InstCombineInternal.h

565

Since we're changing the signature, how about fixing the capitalization to current fashion as a clean-up ?
foldOpIntoPhi()
foldOpIntoSelect()

test/Transforms/InstCombine/sub.ll

749–754

Best to make this an NFC change before this commit.

[• dberlin]

Just FYI, i'm about to post a patch to newgvn (just doing some debugging) which will do equivalence between phi of ops and op of phis, in value numbering (which makes them susceptible for later simplification)

It gets these cases already (and i suspect, a lot of instcombine cases)
For the initial version, it is limited to insertion in cases where the phi nodes end up constants for simplicity.
(Which is enough to catch all of these cases)

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
       // (X + signbit) + C could have gotten canonicalized to (X ^ signbit) + C,
       // transform them into (X + (signbit ^ C))
       if (XorRHS->getValue().isSignBit())
         return BinaryOperator::CreateAdd(XorLHS,
                                          ConstantExpr::getXor(XorRHS, CI));
     }
   }
 
-  if (isa<Constant>(RHS) && isa<PHINode>(LHS))
-    if (Instruction *NV = FoldOpIntoPhi(I))
+  if (isa<Constant>(RHS))
+    if (auto *PN = dyn_cast<PHINode>(LHS))
+      if (Instruction *NV = FoldOpIntoPhi(I, PN))
         return NV;
 
   if (I.getType()->getScalarType()->isIntegerTy(1))
     return BinaryOperator::CreateXor(LHS, RHS);
 
   // X + X --> X << 1
   if (LHS == RHS) {
     BinaryOperator *New =
       BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1));
if (Constant *C = dyn_cast<Constant>(Op0)) {
     if (match(Op1, m_Not(m_Value(X))))
       return BinaryOperator::CreateAdd(X, AddOne(C));
 
     // Try to fold constant sub into select arguments.
     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
       if (Instruction *R = FoldOpIntoSelect(I, SI))
         return R;
 
+    // Try to fold constant sub into PHI values.
+    if (PHINode *PN = dyn_cast<PHINode>(Op1))
+      if (Instruction *R = FoldOpIntoPhi(I, PN))
+        return R;
+
     // C-(X+C2) --> (C-C2)-X
     Constant *C2;
     if (match(Op1, m_Add(m_Value(X), m_Constant(C2))))
       return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
 
     // Fold (sub 0, (zext bool to B)) --> (sext bool to B)
     if (C->isNullValue() && match(Op1, m_ZExt(m_Value(X))))
       if (X->getType()->getScalarType()->isIntegerTy(1))

lib/Transforms/InstCombine/InstCombineCasts.cpp

Instruction *InstCombiner::commonCastTransforms(CastInst &CI) {
   }
 
   // If we are casting a select, then fold the cast into the select.
   if (auto *SI = dyn_cast<SelectInst>(Src))
     if (Instruction *NV = FoldOpIntoSelect(CI, SI))
       return NV;
 
   // If we are casting a PHI, then fold the cast into the PHI.
-  if (isa<PHINode>(Src)) {
+  if (auto *PN = dyn_cast<PHINode>(Src)) {
     // Don't do this if it would create a PHI node with an illegal type from a
     // legal type.
     if (!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() ||
         shouldChangeType(CI.getType(), Src->getType()))
-      if (Instruction *NV = FoldOpIntoPhi(CI))
+      if (Instruction *NV = FoldOpIntoPhi(CI, PN))
         return NV;
   }
 
   return nullptr;
 }
 
 /// Return true if we can evaluate the specified expression tree as type Ty
 /// instead of its larger type, and arrive with the same value.

lib/Transforms/InstCombine/InstCombineCompares.cpp

if (RHSC->isNullValue() &&
           I.getPredicate(), LHSI->getOperand(0),
           Constant::getNullValue(LHSI->getOperand(0)->getType()));
     break;
   case Instruction::PHI:
     // Only fold icmp into the PHI if the phi and icmp are in the same
     // block.  If in the same block, we're encouraging jump threading.  If
     // not, we are just pessimizing the code by making an i1 phi.
     if (LHSI->getParent() == I.getParent())
-      if (Instruction *NV = FoldOpIntoPhi(I))
+      if (Instruction *NV = FoldOpIntoPhi(I, cast<PHINode>(LHSI)))
         return NV;
     break;
   case Instruction::Select: {
     // If either operand of the select is a constant, we can fold the
     // comparison into the select arms, which will cause one to be
     // constant folded and the select turned into a bitwise or.
     Value *Op1 = nullptr, *Op2 = nullptr;
     ConstantInt *CI = nullptr;
if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
                               ConstantFP::get(RHSC->getContext(), F));
         break;
       }
       case Instruction::PHI:
         // Only fold fcmp into the PHI if the phi and fcmp are in the same
         // block.  If in the same block, we're encouraging jump threading.  If
         // not, we are just pessimizing the code by making an i1 phi.
         if (LHSI->getParent() == I.getParent())
-          if (Instruction *NV = FoldOpIntoPhi(I))
+          if (Instruction *NV = FoldOpIntoPhi(I, cast<PHINode>(LHSI)))
             return NV;
         break;
       case Instruction::SIToFP:
       case Instruction::UIToFP:
         if (Instruction *NV = foldFCmpIntToFPConst(I, LHSI, RHSC))
           return NV;
         break;
       case Instruction::FSub: {

lib/Transforms/InstCombine/InstCombineInternal.h

private:
 
   Value *SimplifyVectorOp(BinaryOperator &Inst);
   Value *SimplifyBSwap(BinaryOperator &Inst);
 
 
   /// 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);
+  Instruction *FoldOpIntoPhi(Instruction &I, PHINode *PN);
 
   /// 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.

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
     return &I;
 
   if (isa<Constant>(Op1)) {
     if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
       if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
         if (Instruction *R = FoldOpIntoSelect(I, SI))
           return R;
-      } else if (isa<PHINode>(Op0I)) {
+      } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
         using namespace llvm::PatternMatch;
         const APInt *Op1Int;
         if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
             (I.getOpcode() == Instruction::URem ||
              !Op1Int->isMinSignedValue())) {
           // FoldOpIntoPhi will speculate instructions to the end of the PHI's
           // predecessor blocks, so do this only if we know the srem or urem
           // will not fault.
-          if (Instruction *NV = FoldOpIntoPhi(I))
+          if (Instruction *NV = FoldOpIntoPhi(I, PN))
             return NV;
         }
       }
 
       // See if we can fold away this rem instruction.
       if (SimplifyDemandedInstructionBits(I))
         return &I;
     }

lib/Transforms/InstCombine/InstCombineSelect.cpp

if ((SPF == SPF_SMAX || SPF == SPF_UMAX) &&
       }
     }
 
     // TODO.
     // ABS(-X) -> ABS(X)
   }
 
   // See if we can fold the select into a phi node if the condition is a select.
-  if (isa<PHINode>(SI.getCondition()))
+  if (auto *PN = dyn_cast<PHINode>(SI.getCondition()))
     // The true/false values have to be live in the PHI predecessor's blocks.
     if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
         canSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
-      if (Instruction *NV = FoldOpIntoPhi(SI))
+      if (Instruction *NV = FoldOpIntoPhi(SI, PN))
         return NV;
 
   if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {
     if (TrueSI->getCondition()->getType() == CondVal->getType()) {
       // select(C, select(C, a, b), c) -> select(C, a, c)
       if (TrueSI->getCondition() == CondVal) {
         if (SI.getTrueValue() == TrueSI->getTrueValue())
           return nullptr;

lib/Transforms/InstCombine/InstructionCombining.cpp

if (auto *CI = dyn_cast<CmpInst>(SI->getCondition())) {
     }
   }
 
   Value *NewTV = foldOperationIntoSelectOperand(Op, TV, this);
   Value *NewFV = foldOperationIntoSelectOperand(Op, FV, this);
   return SelectInst::Create(SI->getCondition(), NewTV, NewFV, "", nullptr, SI);
 }
 
-Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
-  PHINode *PN = cast<PHINode>(I.getOperand(0));
+static Value *foldOperationIntoPhiValue(Value *InV, Constant *C,
+                                        Instruction::BinaryOps Opc,
+                                        bool ConstIsRHS, InstCombiner *IC) {
+  if (auto *InC = dyn_cast<Constant>(InV)) {
+    if (ConstIsRHS)
+      return ConstantExpr::get(Opc, InC, C);
+    return ConstantExpr::get(Opc, C, InC);
+  }
+
+  Value *Op0 = InV, *Op1 = C;
+  if (!ConstIsRHS)
+    std::swap(Op0, Op1);
+
+  return IC->Builder->CreateBinOp(Opc, Op0, Op1, "phitmp");
+}
+
+Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I, PHINode *PN) {
   unsigned NumPHIValues = PN->getNumIncomingValues();
   if (NumPHIValues == 0)
     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()) {
for (unsigned i = 0; i != NumPHIValues; ++i) {
         InV = Builder->CreateICmp(CI->getPredicate(), PN->getIncomingValue(i),
                                   C, "phitmp");
       else
         InV = Builder->CreateFCmp(CI->getPredicate(), PN->getIncomingValue(i),
                                   C, "phitmp");
       NewPN->addIncoming(InV, PN->getIncomingBlock(i));
     }
   } else if (I.getNumOperands() == 2) {
-    Constant *C = cast<Constant>(I.getOperand(1));
+    bool ConstIsRHS = isa<Constant>(I.getOperand(1));
+    Constant *C = cast<Constant>(I.getOperand(ConstIsRHS));
     for (unsigned i = 0; i != NumPHIValues; ++i) {
-      Value *InV = nullptr;
-      if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i)))
-        InV = ConstantExpr::get(I.getOpcode(), InC, C);
-      else
-        InV = Builder->CreateBinOp(cast<BinaryOperator>(I).getOpcode(),
-                                   PN->getIncomingValue(i), C, "phitmp");
+      Value *InV = foldOperationIntoPhiValue(PN->getIncomingValue(i), C,
+                                            cast<BinaryOperator>(I).getOpcode(),
+                                            ConstIsRHS, this);
       NewPN->addIncoming(InV, PN->getIncomingBlock(i));
     }
   } else {
     CastInst *CI = cast<CastInst>(&I);
     Type *RetTy = CI->getType();
     for (unsigned i = 0; i != NumPHIValues; ++i) {
       Value *InV;
       if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i)))

 }
 
 Instruction *InstCombiner::foldOpWithConstantIntoOperand(BinaryOperator &I) {
   assert(isa<Constant>(I.getOperand(1)) && "Unexpected operand type");
 
   if (auto *Sel = dyn_cast<SelectInst>(I.getOperand(0))) {
     if (Instruction *NewSel = FoldOpIntoSelect(I, Sel))
       return NewSel;
-  } else if (isa<PHINode>(I.getOperand(0))) {
-    if (Instruction *NewPhi = FoldOpIntoPhi(I))
+  } else if (auto *PN = dyn_cast<PHINode>(I.getOperand(0))) {
+    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

test/Transforms/InstCombine/sub.ll

 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %sub = sub i32 254, %X
   %res = and i32 %sub, 127
   ret i32 %res
 }
 
 define <2 x i1> @test53(<2 x i1> %A, <2 x i1> %B) {
+; CHECK-LABEL: @test53(
+; CHECK-NEXT:    [[SUB:%.*]] = xor <2 x i1> [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret <2 x i1> [[SUB]]
+;
   %sub = sub <2 x i1> %A, %B
   ret <2 x i1> %sub
-; CHECK-LABEL: @test53(
-; CHECK-NEXT: %sub = xor <2 x i1> %A, %B
-; CHECK-NEXT: ret <2 x i1> %sub
 }
 
 define i32 @test54(i1 %C) {
 ; CHECK-LABEL: @test54(
 ; CHECK-NEXT:    [[V:%.*]] = select i1 [[C:%.*]], i32 -877, i32 113
 ; CHECK-NEXT:    ret i32 [[V]]
 ;
   %A = select i1 %C, i32 1000, i32 10

 
 define i32 @test55(i1 %which) {
 ; CHECK-LABEL: @test55(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[WHICH:%.*]], label [[FINAL:%.*]], label [[DELAY:%.*]]
 ; CHECK:       delay:
 ; CHECK-NEXT:    br label [[FINAL]]
 ; CHECK:       final:
-; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1000, [[ENTRY:%.*]] ], [ 10, [[DELAY]] ]
-; CHECK-NEXT:    [[VALUE:%.*]] = sub nsw i32 123, [[A]]
-; CHECK-NEXT:    ret i32 [[VALUE]]
+; CHECK-NEXT:    [[A:%.*]] = phi i32 [ -877, [[ENTRY:%.*]] ], [ 113, [[DELAY]] ]
+; CHECK-NEXT:    ret i32 [[A]]
 ;
 entry:
   br i1 %which, label %final, label %delay
 
 delay:
   br label %final
 
 final:
   %A = phi i32 [ 1000, %entry ], [ 10, %delay ]
   %value = sub i32 123, %A
   ret i32 %value
 }
 
 define <2 x i32> @test55vec(i1 %which) {
 ; CHECK-LABEL: @test55vec(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[WHICH:%.*]], label [[FINAL:%.*]], label [[DELAY:%.*]]
 ; CHECK:       delay:
 ; CHECK-NEXT:    br label [[FINAL]]
 ; CHECK:       final:
-; CHECK-NEXT:    [[A:%.*]] = phi <2 x i32> [ <i32 1000, i32 1000>, [[ENTRY:%.*]] ], [ <i32 10, i32 10>, [[DELAY]] ]
-; CHECK-NEXT:    [[VALUE:%.*]] = sub nsw <2 x i32> <i32 123, i32 123>, [[A]]
-; CHECK-NEXT:    ret <2 x i32> [[VALUE]]
+; CHECK-NEXT:    [[A:%.*]] = phi <2 x i32> [ <i32 -877, i32 -877>, [[ENTRY:%.*]] ], [ <i32 113, i32 113>, [[DELAY]] ]
+; CHECK-NEXT:    ret <2 x i32> [[A]]
 ;
 entry:
   br i1 %which, label %final, label %delay
 
 delay:
   br label %final
 
 final:
   %A = phi <2 x i32> [ <i32 1000, i32 1000>, %entry ], [ <i32 10, i32 10>, %delay ]
   %value = sub <2 x i32> <i32 123, i32 123>, %A
   ret <2 x i32> %value
 }
 
 define <2 x i32> @test55vec2(i1 %which) {
 ; CHECK-LABEL: @test55vec2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[WHICH:%.*]], label [[FINAL:%.*]], label [[DELAY:%.*]]
 ; CHECK:       delay:
 ; CHECK-NEXT:    br label [[FINAL]]
 ; CHECK:       final:
-; CHECK-NEXT:    [[A:%.*]] = phi <2 x i32> [ <i32 1000, i32 2500>, [[ENTRY:%.*]] ], [ <i32 10, i32 30>, [[DELAY]] ]
-; CHECK-NEXT:    [[VALUE:%.*]] = sub nsw <2 x i32> <i32 123, i32 333>, [[A]]
-; CHECK-NEXT:    ret <2 x i32> [[VALUE]]
+; CHECK-NEXT:    [[A:%.*]] = phi <2 x i32> [ <i32 -877, i32 -2167>, [[ENTRY:%.*]] ], [ <i32 113, i32 303>, [[DELAY]] ]
+; CHECK-NEXT:    ret <2 x i32> [[A]]
 ;
 entry:
   br i1 %which, label %final, label %delay
 
 delay:
   br label %final
 
 final:
   %A = phi <2 x i32> [ <i32 1000, i32 2500>, %entry ], [ <i32 10, i32 30>, %delay ]
   %value = sub <2 x i32> <i32 123, i32 333>, %A
   ret <2 x i32> %value
 }