Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineShifts.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineShifts.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineShifts.cpp @@ -310,6 +310,40 @@ } } +// If this is a bitwise operator or add with a constant RHS we might be able +// to pull it through a shift. +static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift, + BinaryOperator *BO, + const APInt &C) { + bool IsValid = true; // Valid only for And, Or Xor, + bool HighBitSet = false; // Transform ifhigh bit of constant set? + + switch (BO->getOpcode()) { + default: IsValid = false; break; // Do not perform transform! + case Instruction::Add: + IsValid = Shift.getOpcode() == Instruction::Shl; + break; + case Instruction::Or: + case Instruction::Xor: + HighBitSet = false; + break; + case Instruction::And: + HighBitSet = true; + break; + } + + // If this is a signed shift right, and the high bit is modified + // by the logical operation, do not perform the transformation. + // The HighBitSet boolean indicates the value of the high bit of + // the constant which would cause it to be modified for this + // operation. + // + if (IsValid && Shift.getOpcode() == Instruction::AShr) + IsValid = C.isNegative() == HighBitSet; + + return IsValid; +} + Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1, BinaryOperator &I) { bool isLeftShift = I.getOpcode() == Instruction::Shl; @@ -472,33 +506,7 @@ // shift is the only use, we can pull it out of the shift. const APInt *Op0C; if (match(Op0BO->getOperand(1), m_APInt(Op0C))) { - bool isValid = true; // Valid only for And, Or, Xor - bool highBitSet = false; // Transform if high bit of constant set? - - switch (Op0BO->getOpcode()) { - default: isValid = false; break; // Do not perform transform! - case Instruction::Add: - isValid = isLeftShift; - break; - case Instruction::Or: - case Instruction::Xor: - highBitSet = false; - break; - case Instruction::And: - highBitSet = true; - break; - } - - // If this is a signed shift right, and the high bit is modified - // by the logical operation, do not perform the transformation. - // The highBitSet boolean indicates the value of the high bit of - // the constant which would cause it to be modified for this - // operation. - // - if (isValid && I.getOpcode() == Instruction::AShr) - isValid = Op0C->isNegative() == highBitSet; - - if (isValid) { + if (canShiftBinOpWithConstantRHS(I, Op0BO, *Op0C)) { Constant *NewRHS = ConstantExpr::get(I.getOpcode(), cast(Op0BO->getOperand(1)), Op1); @@ -525,6 +533,53 @@ return BinaryOperator::CreateSub(NewRHS, NewShift); } } + + // If we have a select that conditionally executes some binary operator, + // see if we can pull it the select and operator through the shift. + // + // For example, turning: + // shl (select C, (add X, C1), X), C2 + // Into: + // Y = shl X, C2 + // select C, (add Y, C1 << C2), Y + Value *Cond; + BinaryOperator *TBO; + Value *FalseVal; + if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)), + m_Value(FalseVal)))) { + const APInt *C; + if (!isa(FalseVal) && TBO->getOperand(0) == FalseVal && + match(TBO->getOperand(1), m_APInt(C)) && + canShiftBinOpWithConstantRHS(I, TBO, *C)) { + Constant *NewRHS = ConstantExpr::get(I.getOpcode(), + cast(TBO->getOperand(1)), Op1); + + Value *NewShift = + Builder.CreateBinOp(I.getOpcode(), FalseVal, Op1); + Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift, + NewRHS); + return SelectInst::Create(Cond, NewOp, NewShift); + } + } + + BinaryOperator *FBO; + Value *TrueVal; + if (match(Op0, m_Select(m_Value(Cond), m_Value(TrueVal), + m_OneUse(m_BinOp(FBO))))) { + const APInt *C; + if (!isa(TrueVal) && FBO->getOperand(0) == TrueVal && + match(FBO->getOperand(1), m_APInt(C)) && + canShiftBinOpWithConstantRHS(I, FBO, *C)) { + Constant *NewRHS = ConstantExpr::get(I.getOpcode(), + cast(FBO->getOperand(1)), Op1); + + Value *NewShift = + Builder.CreateBinOp(I.getOpcode(), TrueVal, Op1); + Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift, + NewRHS); + return SelectInst::Create(Cond, NewShift, NewOp); + } + } } return nullptr; Index: llvm/trunk/test/Transforms/InstCombine/shift.ll =================================================================== --- llvm/trunk/test/Transforms/InstCombine/shift.ll +++ llvm/trunk/test/Transforms/InstCombine/shift.ll @@ -1332,3 +1332,263 @@ %y = and i7 %x, 1 ; this extracts the lsb which should be 0 because we shifted an even number of bits and all even bits of the shift input are 0. ret i7 %y } + +define i32 @shl_select_add_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @shl_select_add_true( +; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = add i32 [[TMP1]], 14 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = add i32 %x, 7 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = shl i32 %2, 1 + ret i32 %3 +} + +define i32 @shl_select_add_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @shl_select_add_false( +; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = add i32 [[TMP1]], 14 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = add i32 %x, 7 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = shl i32 %2, 1 + ret i32 %3 +} + +define i32 @shl_select_and_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @shl_select_and_true( +; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 14 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = and i32 %x, 7 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = shl i32 %2, 1 + ret i32 %3 +} + +define i32 @shl_select_and_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @shl_select_and_false( +; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 14 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = and i32 %x, 7 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = shl i32 %2, 1 + ret i32 %3 +} + +define i32 @lshr_select_and_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @lshr_select_and_true( +; CHECK-NEXT: [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = and i32 %x, 7 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = lshr i32 %2, 1 + ret i32 %3 +} + +define i32 @lshr_select_and_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @lshr_select_and_false( +; CHECK-NEXT: [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = and i32 %x, 7 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = lshr i32 %2, 1 + ret i32 %3 +} + +define i32 @ashr_select_and_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @ashr_select_and_true( +; CHECK-NEXT: [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], -1073741821 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = and i32 %x, 2147483655 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = ashr i32 %2, 1 + ret i32 %3 +} + +define i32 @ashr_select_and_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @ashr_select_and_false( +; CHECK-NEXT: [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], -1073741821 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = and i32 %x, 2147483655 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = ashr i32 %2, 1 + ret i32 %3 +} + +define i32 @shl_select_or_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @shl_select_or_true( +; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = or i32 [[TMP1]], 14 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = or i32 %x, 7 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = shl i32 %2, 1 + ret i32 %3 +} + +define i32 @shl_select_or_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @shl_select_or_false( +; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = or i32 [[TMP1]], 14 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = or i32 %x, 7 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = shl i32 %2, 1 + ret i32 %3 +} + +define i32 @lshr_select_or_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @lshr_select_or_true( +; CHECK-NEXT: [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = or i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = or i32 %x, 7 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = lshr i32 %2, 1 + ret i32 %3 +} + +define i32 @lshr_select_or_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @lshr_select_or_false( +; CHECK-NEXT: [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = or i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = or i32 %x, 7 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = lshr i32 %2, 1 + ret i32 %3 +} + +define i32 @ashr_select_or_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @ashr_select_or_true( +; CHECK-NEXT: [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = or i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = or i32 %x, 7 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = ashr i32 %2, 1 + ret i32 %3 +} + +define i32 @ashr_select_or_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @ashr_select_or_false( +; CHECK-NEXT: [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = or i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = or i32 %x, 7 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = ashr i32 %2, 1 + ret i32 %3 +} + +define i32 @shl_select_xor_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @shl_select_xor_true( +; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = xor i32 [[TMP1]], 14 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = xor i32 %x, 7 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = shl i32 %2, 1 + ret i32 %3 +} + +define i32 @shl_select_xor_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @shl_select_xor_false( +; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = xor i32 [[TMP1]], 14 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = xor i32 %x, 7 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = shl i32 %2, 1 + ret i32 %3 +} + +define i32 @lshr_select_xor_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @lshr_select_xor_true( +; CHECK-NEXT: [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = xor i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = xor i32 %x, 7 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = lshr i32 %2, 1 + ret i32 %3 +} + +define i32 @lshr_select_xor_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @lshr_select_xor_false( +; CHECK-NEXT: [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = xor i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = xor i32 %x, 7 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = lshr i32 %2, 1 + ret i32 %3 +} + +define i32 @ashr_select_xor_true(i32 %x, i1 %cond) { +; CHECK-LABEL: @ashr_select_xor_true( +; CHECK-NEXT: [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = xor i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = xor i32 %x, 7 + %2 = select i1 %cond, i32 %1, i32 %x + %3 = ashr i32 %2, 1 + ret i32 %3 +} + +define i32 @ashr_select_xor_false(i32 %x, i1 %cond) { +; CHECK-LABEL: @ashr_select_xor_false( +; CHECK-NEXT: [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = xor i32 [[TMP1]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]] +; CHECK-NEXT: ret i32 [[TMP3]] +; + %1 = xor i32 %x, 7 + %2 = select i1 %cond, i32 %x, i32 %1 + %3 = ashr i32 %2, 1 + ret i32 %3 +}