[InstCombine] Refactor FoldUDivAction for future usage with multiplication. NFC

[danlark]

Summary

Refactor FoldUDivAction for future usage with multiplication. NFC

Patch by Danila Kutenin. email:danilak at google.com, github:danlark1@ . I don't have commit rights.

[lebedev.ri]

There's a lot of changes in the diff.
Please can you split this into preparatory NFC cleanup, and the actual change?

[danlark]

In D71561#1786388, @lebedev.ri wrote:

There's a lot of changes in the diff.
Please can you split this into preparatory NFC cleanup, and the actual change?

Ok

[danlark]

Make the change NFC

[danlark]

Some style

[danlark]

FoldOperandAction -> OperandFoldAction

[danlark]

In D71561#1786388, @lebedev.ri wrote:

There's a lot of changes in the diff.
Please can you split this into preparatory NFC cleanup, and the actual change?

Finally done. PTAL

[lebedev.ri]

LG i guess

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

196–197

I see that this is only moved, but generally it really just should be an assert().

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

[arsenm]

In D71561#4049980, @lebedev.ri wrote:

This review seems to be stuck/dead, consider abandoning if no longer relevant.

You should probably just push this seeing as you accepted it and there's a commit request

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

for (unsigned I = 0, E = Ty->getVectorNumElements(); I != E; ++I) {
     if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
       return nullptr;
     Elts.push_back(ConstantInt::get(Ty->getScalarType(), IVal->logBase2()));
   }
 
   return ConstantVector::get(Elts);
 }
 
+static const unsigned MaxDepth = 6;
+
+namespace {
+
+using FoldOperandCb = Instruction *(*)(Value *Op0, Value *Op1,
+                                       const BinaryOperator &I,
+                                       InstCombiner &IC);
+
+/// Used to maintain state for visitMul() and visitUDiv().
+struct OperandFoldAction {
+  /// Informs visit() how to fold this operand.  This can be zero if this
+  /// action joins two actions together.
+  FoldOperandCb FoldAction;
+
+  /// Which operand to fold.
+  Value *OperandToFold;
+
+  union {
+    /// The instruction returned when FoldAction is invoked.
+    Instruction *FoldResult;
+
+    /// Stores the LHS action index if this action joins two actions together.
+    size_t SelectLHSIdx;
+  };
+
+  OperandFoldAction(FoldOperandCb FA, Value *InputOperand)
+      : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
+  OperandFoldAction(FoldOperandCb FA, Value *InputOperand, size_t SLHS)
+      : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
+};
+
+} // end anonymous namespace
+
+static Instruction *combineActions(Value *Op0, BinaryOperator &I,
+                                   SmallVectorImpl<OperandFoldAction> &Actions,
+                                   InstCombiner &IC) {
+  for (unsigned i = 0, e = Actions.size(); i != e; ++i) {
+    FoldOperandCb Action = Actions[i].FoldAction;
+    Value *ActionOp1 = Actions[i].OperandToFold;
+    Instruction *Inst;
+    if (Action)
+      Inst = Action(Op0, ActionOp1, I, IC);
+    else {
+      // This action joins two actions together.  The RHS of this action is
+      // simply the last action we processed, we saved the LHS action index in
+      // the joining action.
+      size_t SelectRHSIdx = i - 1;
+      Value *SelectRHS = Actions[SelectRHSIdx].FoldResult;
+      size_t SelectLHSIdx = Actions[i].SelectLHSIdx;
+      Value *SelectLHS = Actions[SelectLHSIdx].FoldResult;
+      Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
+                                SelectLHS, SelectRHS);
+    }
+    // If this is the last action to process, return it to the InstCombiner.
+    // Otherwise, we insert it before the Operator and record it so that we may
+    // use it as part of a joining action (i.e., a SelectInst).
+    if (e - i != 1) {
+      Inst->insertBefore(&I);
+      Actions[i].FoldResult = Inst;
+    } else
+      return Inst;
+  }
+  return nullptr;
+}
+
+// X udiv 2^C -> X >> C
+static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1,
+                                    const BinaryOperator &I, InstCombiner &IC) {
+  Constant *C1 = getLogBase2(Op0->getType(), cast<Constant>(Op1));
+  if (!C1)
+    llvm_unreachable("Failed to constant fold udiv -> logbase2");
+  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, C1);
+  if (I.isExact())
+    LShr->setIsExact();
+  return LShr;
+}
+
+// X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
+// X udiv (zext (C1 << N)), where C1 is "1<<C2"  -->  X >> (N+C2)
+static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
+                                InstCombiner &IC) {
+  Value *ShiftLeft;
+  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
+    ShiftLeft = Op1;
+
+  Constant *CI;
+  Value *N;
+  if (!match(ShiftLeft, m_Shl(m_Constant(CI), m_Value(N))))
+    llvm_unreachable("match should never fail here!");
+  Constant *Log2Base = getLogBase2(N->getType(), CI);
+  if (!Log2Base)
+    llvm_unreachable("getLogBase2 should never fail here!");
+  N = IC.Builder.CreateAdd(N, Log2Base);
+  if (Op1 != ShiftLeft)
+    N = IC.Builder.CreateZExt(N, Op1->getType());
+  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
+  if (I.isExact())
+    LShr->setIsExact();
+  return LShr;
+}
+
+// Recursively visits the possible right hand operands of a udiv
+// instruction, seeing through select instructions, to determine if we can
+// replace the udiv with something simpler.  If we find that an operand is not
+// able to simplify the udiv, we abort the entire transformation.
+static size_t visitUDivOperand(Value *Op0, Value *Op1,
+                               SmallVectorImpl<OperandFoldAction> &Actions,
+                               unsigned Depth = 0) {
+  // Check to see if this is an unsigned division with an exact power of 2,
+  // if so, convert to a right shift.
+  if (match(Op1, m_Power2())) {
+    Actions.push_back(OperandFoldAction(foldUDivPow2Cst, Op1));
+    return Actions.size();
+  }
+
+  // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
+  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
+      match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
+    Actions.push_back(OperandFoldAction(foldUDivShl, Op1));
+    return Actions.size();
+  }
+
+  // The remaining tests are all recursive, so bail out if we hit the limit.
+  if (Depth++ == MaxDepth)
+    return 0;
+
+  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
+    if (size_t LHSIdx =
+            visitUDivOperand(Op0, SI->getOperand(1), Actions, Depth))
+      if (visitUDivOperand(Op0, SI->getOperand(2), Actions, Depth)) {
+        Actions.push_back(OperandFoldAction(nullptr, Op1, LHSIdx - 1));
+        return Actions.size();
+      }
+
+  return 0;
+}
+
 // TODO: This is a specific form of a much more general pattern.
 //       We could detect a select with any binop identity constant, or we
 //       could use SimplifyBinOp to see if either arm of the select reduces.
 //       But that needs to be done carefully and/or while removing potential
 //       reverse canonicalizations as in InstCombiner::foldSelectIntoOp().
 static Value *foldMulSelectToNegate(BinaryOperator &I,
                                     InstCombiner::BuilderTy &Builder) {
   Value *Cond, *OtherOp;
if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
       I.setOperand(1, Y);
       return &I;
     }
   }
 
   return nullptr;
 }
 
-static const unsigned MaxDepth = 6;
-
-namespace {
-
-using FoldUDivOperandCb = Instruction *(*)(Value *Op0, Value *Op1,
-                                           const BinaryOperator &I,
-                                           InstCombiner &IC);
-
-/// Used to maintain state for visitUDivOperand().
-struct UDivFoldAction {
-  /// Informs visitUDiv() how to fold this operand.  This can be zero if this
-  /// action joins two actions together.
-  FoldUDivOperandCb FoldAction;
-
-  /// Which operand to fold.
-  Value *OperandToFold;
-
-  union {
-    /// The instruction returned when FoldAction is invoked.
-    Instruction *FoldResult;
-
-    /// Stores the LHS action index if this action joins two actions together.
-    size_t SelectLHSIdx;
-  };
-
-  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
-      : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
-  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
-      : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
-};
-
-} // end anonymous namespace
-
-// X udiv 2^C -> X >> C
-static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1,
-                                    const BinaryOperator &I, InstCombiner &IC) {
-  Constant *C1 = getLogBase2(Op0->getType(), cast<Constant>(Op1));
-  if (!C1)
-    llvm_unreachable("Failed to constant fold udiv -> logbase2");
-  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, C1);
-  if (I.isExact())
-    LShr->setIsExact();
-  return LShr;
-}
-
-// X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
-// X udiv (zext (C1 << N)), where C1 is "1<<C2"  -->  X >> (N+C2)
-static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
-                                InstCombiner &IC) {
-  Value *ShiftLeft;
-  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
-    ShiftLeft = Op1;
-
-  Constant *CI;
-  Value *N;
-  if (!match(ShiftLeft, m_Shl(m_Constant(CI), m_Value(N))))
-    llvm_unreachable("match should never fail here!");
-  Constant *Log2Base = getLogBase2(N->getType(), CI);
-  if (!Log2Base)
-    llvm_unreachable("getLogBase2 should never fail here!");
-  N = IC.Builder.CreateAdd(N, Log2Base);
-  if (Op1 != ShiftLeft)
-    N = IC.Builder.CreateZExt(N, Op1->getType());
-  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
-  if (I.isExact())
-    LShr->setIsExact();
-  return LShr;
-}
-
-// Recursively visits the possible right hand operands of a udiv
-// instruction, seeing through select instructions, to determine if we can
-// replace the udiv with something simpler.  If we find that an operand is not
-// able to simplify the udiv, we abort the entire transformation.
-static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
-                               SmallVectorImpl<UDivFoldAction> &Actions,
-                               unsigned Depth = 0) {
-  // Check to see if this is an unsigned division with an exact power of 2,
-  // if so, convert to a right shift.
-  if (match(Op1, m_Power2())) {
-    Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
-    return Actions.size();
-  }
-
-  // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
-  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
-      match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
-    Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
-    return Actions.size();
-  }
-
-  // The remaining tests are all recursive, so bail out if we hit the limit.
-  if (Depth++ == MaxDepth)
-    return 0;
-
-  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
-    if (size_t LHSIdx =
-            visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
-      if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
-        Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
-        return Actions.size();
-      }
-
-  return 0;
-}
-
 /// If we have zero-extended operands of an unsigned div or rem, we may be able
 /// to narrow the operation (sink the zext below the math).
 static Instruction *narrowUDivURem(BinaryOperator &I,
                                    InstCombiner::BuilderTy &Builder) {
   Instruction::BinaryOps Opcode = I.getOpcode();
   Value *N = I.getOperand(0);
   Value *D = I.getOperand(1);
   Type *Ty = I.getType();
if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) ||
         match(Op1, m_NUWMul(m_Value(X), m_Specific(A))))
       return BinaryOperator::CreateUDiv(B, X);
     if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) ||
         match(Op1, m_NUWMul(m_Value(X), m_Specific(B))))
       return BinaryOperator::CreateUDiv(A, X);
   }
 
   // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
-  SmallVector<UDivFoldAction, 6> UDivActions;
-  if (visitUDivOperand(Op0, Op1, I, UDivActions))
-    for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
-      FoldUDivOperandCb Action = UDivActions[i].FoldAction;
-      Value *ActionOp1 = UDivActions[i].OperandToFold;
-      Instruction *Inst;
-      if (Action)
-        Inst = Action(Op0, ActionOp1, I, *this);
-      else {
-        // This action joins two actions together.  The RHS of this action is
-        // simply the last action we processed, we saved the LHS action index in
-        // the joining action.
-        size_t SelectRHSIdx = i - 1;
-        Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
-        size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
-        Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
-        Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
-                                  SelectLHS, SelectRHS);
-      }
-
-      // If this is the last action to process, return it to the InstCombiner.
-      // Otherwise, we insert it before the UDiv and record it so that we may
-      // use it as part of a joining action (i.e., a SelectInst).
-      if (e - i != 1) {
-        Inst->insertBefore(&I);
-        UDivActions[i].FoldResult = Inst;
-      } else
-        return Inst;
-    }
+  SmallVector<OperandFoldAction, 6> UDivActions;
+  if (visitUDivOperand(Op0, Op1, UDivActions))
+    if (Instruction *Inst = combineActions(Op0, I, UDivActions, *this))
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
   if (Value *V = SimplifySDivInst(I.getOperand(0), I.getOperand(1),
                                   SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue()) {
       I.setOperand(1, ConstantInt::get(I.getType(), -*Y));
       return &I;
     }
   }
 
   // -X srem Y --> -(X srem Y)
   Value *X, *Y;
   if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
-    return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y)); 
+    return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y));
 
   // If the sign bits of both operands are zero (i.e. we can prove they are
   // unsigned inputs), turn this into a urem.
   APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
   if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
       MaskedValueIsZero(Op0, Mask, 0, &I)) {
     // X srem Y -> X urem Y, iff X and Y don't have sign bit set
     return BinaryOperator::CreateURem(Op0, Op1, I.getName());