Index: lib/Transforms/InstCombine/InstCombineShifts.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineShifts.cpp +++ 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,51 @@ 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. + if (auto *SI = dyn_cast(Op0)) { + Value *TrueVal = SI->getTrueValue(); + Value *FalseVal = SI->getFalseValue(); + + if (auto *TVI = dyn_cast(TrueVal)) { + if (TVI->hasOneUse() && !isa(FalseVal)) { + const APInt *C; + if (TVI->getOperand(0) == FalseVal && + match(TVI->getOperand(1), m_APInt(C))) { + if (canShiftBinOpWithConstantRHS(I, TVI, *C)) { + Constant *NewRHS = ConstantExpr::get(I.getOpcode(), + cast(TVI->getOperand(1)), Op1); + + Value *NewShift = + Builder.CreateBinOp(I.getOpcode(), FalseVal, Op1); + Value *NewOp = Builder.CreateBinOp(TVI->getOpcode(), NewShift, + NewRHS); + return SelectInst::Create(SI->getCondition(), NewOp, NewShift); + } + } + } + } + + if (auto *FVI = dyn_cast(FalseVal)) { + if (FVI->hasOneUse() && !isa(TrueVal)) { + const APInt *C; + if (FVI->getOperand(0) == TrueVal && + match(FVI->getOperand(1), m_APInt(C))) { + if (canShiftBinOpWithConstantRHS(I, FVI, *C)) { + Constant *NewRHS = ConstantExpr::get(I.getOpcode(), + cast(FVI->getOperand(1)), Op1); + + Value *NewShift = + Builder.CreateBinOp(I.getOpcode(), TrueVal, Op1); + Value *NewOp = Builder.CreateBinOp(FVI->getOpcode(), NewShift, + NewRHS); + return SelectInst::Create(SI->getCondition(), NewShift, NewOp); + } + } + } + } + } } return nullptr; Index: test/Transforms/InstCombine/shift.ll =================================================================== --- test/Transforms/InstCombine/shift.ll +++ 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 +}