Page MenuHomePhabricator
Differential D124369 Diff 425533 llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

Changeset View

Standalone View

View Options

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

Show First 20 Lines • Show All 367 Lines • ▼ Show 20 Lines
} }
Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) { Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) {
if (Instruction *Phi = foldBinopWithPhiOperands(I)) if (Instruction *Phi = foldBinopWithPhiOperands(I))
return Phi; return Phi;
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
assert(Op0->getType() == Op1->getType()); assert(Op0->getType() == Op1->getType());
Type *Ty = I.getType();
// If the shift amount is a one-use `sext`, we can demote it to `zext`. // If the shift amount is a one-use `sext`, we can demote it to `zext`.
Value *Y; Value *Y;
if (match(Op1, m_OneUse(m_SExt(m_Value(Y))))) { if (match(Op1, m_OneUse(m_SExt(m_Value(Y))))) {
Value *NewExt = Builder.CreateZExt(Y, I.getType(), Op1->getName()); Value *NewExt = Builder.CreateZExt(Y, Ty, Op1->getName());
return BinaryOperator::Create(I.getOpcode(), Op0, NewExt); return BinaryOperator::Create(I.getOpcode(), Op0, NewExt);
} }
// See if we can fold away this shift. // See if we can fold away this shift.
if (SimplifyDemandedInstructionBits(I)) if (SimplifyDemandedInstructionBits(I))
return &I; return &I;
// Try to fold constant and into select arguments. // Try to fold constant and into select arguments.
Show All 15 LinesInstruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) {
Value *A; Value *A;
Constant *C, *C1; Constant *C, *C1;
if (match(Op0, m_Constant(C)) && if (match(Op0, m_Constant(C)) &&
match(Op1, m_NUWAdd(m_Value(A), m_Constant(C1)))) { match(Op1, m_NUWAdd(m_Value(A), m_Constant(C1)))) {
Constant *NewC = ConstantExpr::get(I.getOpcode(), C, C1); Constant *NewC = ConstantExpr::get(I.getOpcode(), C, C1);
return BinaryOperator::Create(I.getOpcode(), NewC, A); return BinaryOperator::Create(I.getOpcode(), NewC, A);
} }
unsigned BitWidth = Ty->getScalarSizeInBits();
const APInt *AC, *AddC;
// Try to pre-shift a constant shifted by a variable amount added with a
// negative number:
// C << (X - AddC) --> (C >> AddC) << X
// and
// C >> (X - AddC) --> (C << AddC) >> X
if (match(Op0, m_APInt(AC)) && match(Op1, m_Add(m_Value(A), m_APInt(AddC))) &&
AddC->isNegative() && (-*AddC).ult(BitWidth)) {
assert(!AC->isZero() && "Expected simplify of shifted zero");
unsigned PosOffset = (-*AddC).getZExtValue();
auto isSuitableForPreShift = [PosOffset, &I,
AC](Instruction::BinaryOps BinOpcode) {
spatelUnsubmitted
Not Done
ReplyInline Actions

This is more verbose than needed - if we're using &I, then we can just grab the opcode from it via I.getOpcode().
So we can either pass things in as params or use refs, instead of partly using both ways?

auto isSuitableForPreShift = [](Instruction &I, const APInt *AC, unsigned PosOffset) {
auto isSuitableForPreShift = [&I, AC, PosOffset]() {
spatel: This is more verbose than needed - if we're using &I, then we can just grab the opcode from it…
switch (BinOpcode) {
default:
return false;
case Instruction::Shl:
return (I.hasNoSignedWrap() || I.hasNoUnsignedWrap()) &&
AC->eq(AC->lshr(PosOffset).shl(PosOffset));
case Instruction::LShr:
return I.isExact() && AC->eq(AC->shl(PosOffset).lshr(PosOffset));
case Instruction::AShr:
return I.isExact() && AC->eq(AC->shl(PosOffset).ashr(PosOffset));
}
};
auto applyFlag = [&I](BinaryOperator *NewShiftOp) {
switch (NewShiftOp->getOpcode()) {
default:
llvm_unreachable("Inconsistency within commonShiftTransforms");
case Instruction::Shl:
NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
return;
case Instruction::LShr:
case Instruction::AShr:
NewShiftOp->setIsExact();
}
};
if (isSuitableForPreShift(I.getOpcode())) {
Constant *NewC = ConstantInt::get(Ty, I.getOpcode() == Instruction::Shl
? AC->lshr(PosOffset)
: AC->shl(PosOffset));
BinaryOperator *NewShiftOp =
BinaryOperator::Create(I.getOpcode(), NewC, A);
applyFlag(NewShiftOp);
spatelUnsubmitted
Not Done
ReplyInline Actions

Instead of a lambda + switch for setting the flags, I'd prefer the shorter and more direct:

if (I.getOpcode() == Instruction::Shl) {
   NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
else
   NewShiftOp->setIsExact();

That might tilt the whole thing towards a lambda-less implementation, but you can decide which is easier to read.

spatel: Instead of a lambda + switch for setting the flags, I'd prefer the shorter and more direct…
return NewShiftOp;
}
}
// X shift (A srem C) -> X shift (A and (C - 1)) iff C is a power of 2. // X shift (A srem C) -> X shift (A and (C - 1)) iff C is a power of 2.
// Because shifts by negative values (which could occur if A were negative) // Because shifts by negative values (which could occur if A were negative)
// are undefined. // are undefined.
if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Constant(C))) && if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Constant(C))) &&
match(C, m_Power2())) { match(C, m_Power2())) {
// FIXME: Should this get moved into SimplifyDemandedBits by saying we don't // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't
// demand the sign bit (and many others) here?? // demand the sign bit (and many others) here??
Constant *Mask = ConstantExpr::getSub(C, ConstantInt::get(I.getType(), 1)); Constant *Mask = ConstantExpr::getSub(C, ConstantInt::get(Ty, 1));
Value *Rem = Builder.CreateAnd(A, Mask, Op1->getName()); Value *Rem = Builder.CreateAnd(A, Mask, Op1->getName());
return replaceOperand(I, 1, Rem); return replaceOperand(I, 1, Rem);
} }
if (Instruction *Logic = foldShiftOfShiftedLogic(I, Builder)) if (Instruction *Logic = foldShiftOfShiftedLogic(I, Builder))
return Logic; return Logic;
return nullptr; return nullptr;
▲ Show 20 Lines • Show All 555 Lines • ▼ Show 20 LinesInstruction *InstCombinerImpl::visitShl(BinaryOperator &I) {
} }
// (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1 // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1
if (match(Op0, m_One()) && if (match(Op0, m_One()) &&
match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X)))) match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X))))
return BinaryOperator::CreateLShr( return BinaryOperator::CreateLShr(
ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X); ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X);
// Try to pre-shift a constant shifted by a variable amount:
// C << (X + AddC) --> (C >> -AddC) << X
// This requires a no-wrap flag and negative offset constant.
const APInt *AddC;
if ((I.hasNoSignedWrap() || I.hasNoUnsignedWrap()) &&
match(Op0, m_APInt(C)) && match(Op1, m_Add(m_Value(X), m_APInt(AddC))) &&
AddC->isNegative() && (-*AddC).ult(BitWidth)) {
assert(!C->isZero() && "Expected simplify of shifted zero");
unsigned PosOffset = (-*AddC).getZExtValue();
if (C->eq(C->lshr(PosOffset).shl(PosOffset))) {
Constant *NewC = ConstantInt::get(Ty, C->lshr(PosOffset));
Instruction *NewShl = BinaryOperator::CreateShl(NewC, X);
NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
return NewShl;
}
}
return nullptr; return nullptr;
} }
Instruction *InstCombinerImpl::visitLShr(BinaryOperator &I) { Instruction *InstCombinerImpl::visitLShr(BinaryOperator &I) {
if (Value *V = SimplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(), if (Value *V = SimplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),
SQ.getWithInstruction(&I))) SQ.getWithInstruction(&I)))
return replaceInstUsesWith(I, V); return replaceInstUsesWith(I, V);
▲ Show 20 Lines • Show All 416 Lines • Show Last 20 Lines