[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 FoldOperandAction {
+  /// 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;
+  };
+
+  FoldOperandAction(FoldOperandCb FA, Value *InputOperand)
+      : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
+  FoldOperandAction(FoldOperandCb FA, Value *InputOperand, size_t SLHS)
+      : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
+};
+
+} // end anonymous namespace
+
+static Instruction *combineActions(Value *Op0, BinaryOperator &I,
+                                   SmallVectorImpl<FoldOperandAction> &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<FoldOperandAction> &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(FoldOperandAction(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(FoldOperandAction(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(FoldOperandAction(nullptr, Op1, LHSIdx - 1));
+        return Actions.size();
+      }
+
+  return 0;
+}
+
+// X mul 2^C -> X << C
+static Instruction *foldMulPow2Cst(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 mul -> logbase2");
+  BinaryOperator *Shl = BinaryOperator::CreateShl(Op0, C1);
+  if (I.hasNoUnsignedWrap())
+    Shl->setHasNoUnsignedWrap();
+  if (I.hasNoSignedWrap()) {
+    const APInt *V;
+    if (match(C1, m_APInt(V)) && *V != V->getBitWidth() - 1)
+      Shl->setHasNoSignedWrap();
+  }
+  return Shl;
+}
+
+// X mul (C1 << N), where C1 is "1<<C2"  -->  X << (N+C2)
+// X mul (zext (C1 << N)), where C1 is "1<<C2"  -->  X << (N+C2)
+static Instruction *foldMulShl(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 *Shl = BinaryOperator::CreateShl(Op0, N);
+  if (I.hasNoUnsignedWrap())
+    Shl->setHasNoUnsignedWrap();
+  if (I.hasNoSignedWrap() && cast<ShlOperator>(ShiftLeft)->hasNoSignedWrap())
+    Shl->setHasNoSignedWrap();
+  return Shl;
+}
+
+// Recursively visits the possible right hand operands of a mul
+// instruction, seeing through select instructions, to determine if we can
+// replace the mul with something simpler. If we find that an operand is not
+// able to simplify the mul, we abort the entire transformation.
+static size_t visitMulOperand(Value *Op0, Value *Op1,
+                              SmallVectorImpl<FoldOperandAction> &Actions,
+                              unsigned Depth = 0) {
+  // Check to see if this is a multiplication with an exact power of 2, if so,
+  // convert to a left shift.
+  if (match(Op1, m_Power2())) {
+    Actions.push_back(FoldOperandAction(foldMulPow2Cst, Op1));
+    return Actions.size();
+  }
+
+  // X mul (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(FoldOperandAction(foldMulShl, 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 = visitMulOperand(Op0, SI->getOperand(1), Actions, Depth))
+      if (visitMulOperand(Op0, SI->getOperand(2), Actions, Depth)) {
+        Actions.push_back(FoldOperandAction(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;
Instruction *InstCombiner::visitMul(BinaryOperator &I) {
   }
 
   if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
     return FoldedMul;
 
   if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
     return replaceInstUsesWith(I, FoldedMul);
 
+  // (LHS mul (select (select (...)))) -> (LHS << (select (select (...))))
+  SmallVector<FoldOperandAction, 6> MulActions;
+  if (visitMulOperand(Op0, Op1, MulActions))
+    if (Instruction *Inst = combineActions(Op0, I, MulActions, *this))
+      return Inst;
+  MulActions.clear();
+  // ((select (select (...))) mul LHS) -> (LHS << (select (select (...))))
+  if (visitMulOperand(Op1, Op0, MulActions))
+    if (Instruction *Inst = combineActions(Op1, I, MulActions, *this))
+      return Inst;
+
   // Simplify mul instructions with a constant RHS.
   if (isa<Constant>(Op1)) {
     // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
     Value *X;
     Constant *C1;
     if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
       Value *Mul = Builder.CreateMul(C1, Op1);
       // Only go forward with the transform if C1*CI simplifies to a tidier
if (Div && Div->hasOneUse() &&
       return BinaryOperator::CreateSub(Rem, X);
     }
   }
 
   /// i1 mul -> i1 and.
   if (I.getType()->isIntOrIntVectorTy(1))
     return BinaryOperator::CreateAnd(Op0, Op1);
 
-  // X*(1 << Y) --> X << Y
-  // (1 << Y)*X --> X << Y
-  {
-    Value *Y;
-    BinaryOperator *BO = nullptr;
-    bool ShlNSW = false;
-    if (match(Op0, m_Shl(m_One(), m_Value(Y)))) {
-      BO = BinaryOperator::CreateShl(Op1, Y);
-      ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap();
-    } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) {
-      BO = BinaryOperator::CreateShl(Op0, Y);
-      ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap();
-    }
-    if (BO) {
-      if (I.hasNoUnsignedWrap())
-        BO->setHasNoUnsignedWrap();
-      if (I.hasNoSignedWrap() && ShlNSW)
-        BO->setHasNoSignedWrap();
-      return BO;
-    }
-  }
-
   // (bool X) * Y --> X ? Y : 0
   // Y * (bool X) --> X ? Y : 0
   if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
     return SelectInst::Create(X, Op1, ConstantInt::get(I.getType(), 0));
   if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
     return SelectInst::Create(X, Op0, ConstantInt::get(I.getType(), 0));
 
   // (lshr X, 31) * Y --> (ashr X, 31) & Y
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<FoldOperandAction, 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());

llvm/test/Transforms/InstCombine/mul.ll

 ; CHECK-NEXT:    [[MUL:%.*]] = select i1 [[C:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[MUL]]
 ;
   %div = udiv exact i32 %x, %y
   %sel = select i1 %c, i32 %div, i32 1
   %mul = mul i32 %sel, %y
   ret i32 %mul
 }
+
+; Power of twos
+
+define i32 @shift_if_power2(i32 %x, i1 %cond) {
+; CHECK-LABEL: @shift_if_power2(
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], i32 4, i32 2
+; CHECK-NEXT:    [[R:%.*]] = shl i32 [[X:%.*]], [[R_V]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %sel = select i1 %cond, i32 16, i32 4
+  %r = mul i32 %sel, %x
+  ret i32 %r
+}
+
+define i32 @shift_if_power2_double_select(i32 %x, i32 %y, i1 %cond1, i1 %cond2) {
+; CHECK-LABEL: @shift_if_power2_double_select(
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[Y:%.*]], 3
+; CHECK-NEXT:    [[DOTV:%.*]] = select i1 [[COND1:%.*]], i32 [[TMP1]], i32 10
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND2:%.*]], i32 4, i32 [[DOTV]]
+; CHECK-NEXT:    [[R:%.*]] = shl nuw i32 [[X:%.*]], [[R_V]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %shl.res = shl i32 8, %y
+  %sel1 = select i1 %cond1, i32 %shl.res, i32 1024
+  %sel2 = select i1 %cond2, i32 16, i32 %sel1
+  %r = mul nuw i32 %x, %sel2
+  ret i32 %r
+}
+
+define i32 @shift_if_power2_zero(i32 %x, i1 %cond) {
+; CHECK-LABEL: @shift_if_power2_zero(
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], i32 0, i32 2
+; CHECK-NEXT:    [[R:%.*]] = shl i32 [[X:%.*]], [[R_V]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %sel = select i1 %cond, i32 1, i32 4
+  %r = mul i32 %sel, %x
+  ret i32 %r
+}
+
+define <2 x i8> @shift_if_power2_vector(<2 x i8> %px, i1 %cond) {
+; CHECK-LABEL: @shift_if_power2_vector(
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 4, i8 2>, <2 x i8> <i8 0, i8 5>
+; CHECK-NEXT:    [[R:%.*]] = shl <2 x i8> [[PX:%.*]], [[R_V]]
+; CHECK-NEXT:    ret <2 x i8> [[R]]
+;
+  %sel = select i1 %cond, <2 x i8> <i8 16, i8 4>, <2 x i8> <i8 1, i8 32>
+  %r = mul <2 x i8> %px, %sel
+  ret <2 x i8> %r
+}
+
+define i32 @shift_if_extra_use(i32 %x, i1 %cond) {
+; CHECK-LABEL: @shift_if_extra_use(
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 4, i32 128
+; CHECK-NEXT:    call void @use32(i32 [[SEL]])
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND]], i32 2, i32 7
+; CHECK-NEXT:    [[R:%.*]] = shl i32 [[X:%.*]], [[R_V]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %sel = select i1 %cond, i32 4, i32 128
+  call void @use32(i32 %sel)
+  %r = mul i32 %sel, %x
+  ret i32 %r
+}
+
+; Negative tests for power2
+
+define i32 @shift_if_one_not_power2(i32 %x, i1 %cond) {
+; CHECK-LABEL: @shift_if_one_not_power2(
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 5, i32 4
+; CHECK-NEXT:    [[R:%.*]] = mul i32 [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %sel = select i1 %cond, i32 5, i32 4
+  %r = mul i32 %sel, %x
+  ret i32 %r
+}
+
+define i32 @shift_if_not_power2_double_select(i32 %x, i32 %y, i1 %cond1, i1 %cond2) {
+; CHECK-LABEL: @shift_if_not_power2_double_select(
+; CHECK-NEXT:    [[SHL_RES:%.*]] = shl i32 7, [[Y:%.*]]
+; CHECK-NEXT:    [[SEL1:%.*]] = select i1 [[COND1:%.*]], i32 [[SHL_RES]], i32 1024
+; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[COND2:%.*]], i32 16, i32 [[SEL1]]
+; CHECK-NEXT:    [[R:%.*]] = mul nuw i32 [[SEL2]], [[X:%.*]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %shl.res = shl i32 7, %y
+  %sel1 = select i1 %cond1, i32 %shl.res, i32 1024
+  %sel2 = select i1 %cond2, i32 16, i32 %sel1
+  %r = mul nuw i32 %x, %sel2
+  ret i32 %r
+}
+
+define <2 x i8> @shift_if_one_not_power2_vector(<2 x i8> %px, i1 %cond) {
+; CHECK-LABEL: @shift_if_one_not_power2_vector(
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 16, i8 4>, <2 x i8> <i8 0, i8 32>
+; CHECK-NEXT:    [[R:%.*]] = mul <2 x i8> [[SEL]], [[PX:%.*]]
+; CHECK-NEXT:    ret <2 x i8> [[R]]
+;
+  %sel = select i1 %cond, <2 x i8> <i8 16, i8 4>, <2 x i8> <i8 0, i8 32>
+  %r = mul <2 x i8> %px, %sel
+  ret <2 x i8> %r
+}