enum { RecursionLimit = 3 };
STATISTIC(NumExpand, "Number of expansions");
-STATISTIC(NumFactor , "Number of factorizations");
STATISTIC(NumReassoc, "Number of reassociations");
struct Query {
return nullptr;
}
-/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term
-/// using the operation OpCodeToExtract. For example, when Opcode is Add and
-/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)".
-/// Returns the simplified value, or null if no simplification was performed.
-static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS,
- unsigned OpcToExtract, const Query &Q,
- unsigned MaxRecurse) {
- Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract;
- // Recursion is always used, so bail out at once if we already hit the limit.
- if (!MaxRecurse--)
- return nullptr;
-
- BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
- BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
-
- if (!Op0 || Op0->getOpcode() != OpcodeToExtract ||
- !Op1 || Op1->getOpcode() != OpcodeToExtract)
- return nullptr;
-
- // The expression has the form "(A op' B) op (C op' D)".
- Value *A = Op0->getOperand(0), *B = Op0->getOperand(1);
- Value *C = Op1->getOperand(0), *D = Op1->getOperand(1);
-
- // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)".
- // Does the instruction have the form "(A op' B) op (A op' D)" or, in the
- // commutative case, "(A op' B) op (C op' A)"?
- if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) {
- Value *DD = A == C ? D : C;
- // Form "A op' (B op DD)" if it simplifies completely.
- // Does "B op DD" simplify?
- if (Value *V = SimplifyBinOp(Opcode, B, DD, Q, MaxRecurse)) {
- // It does! Return "A op' V" if it simplifies or is already available.
- // If V equals B then "A op' V" is just the LHS. If V equals DD then
- // "A op' V" is just the RHS.
- if (V == B || V == DD) {
- ++NumFactor;
- return V == B ? LHS : RHS;
- }
- // Otherwise return "A op' V" if it simplifies.
- if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, Q, MaxRecurse)) {
- ++NumFactor;
- return W;
- }
- }
- }
-
- // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)".
- // Does the instruction have the form "(A op' B) op (C op' B)" or, in the
- // commutative case, "(A op' B) op (B op' D)"?
- if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) {
- Value *CC = B == D ? C : D;
- // Form "(A op CC) op' B" if it simplifies completely..
- // Does "A op CC" simplify?
- if (Value *V = SimplifyBinOp(Opcode, A, CC, Q, MaxRecurse)) {
- // It does! Return "V op' B" if it simplifies or is already available.
- // If V equals A then "V op' B" is just the LHS. If V equals CC then
- // "V op' B" is just the RHS.
- if (V == A || V == CC) {
- ++NumFactor;
- return V == A ? LHS : RHS;
- }
- // Otherwise return "V op' B" if it simplifies.
- if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, Q, MaxRecurse)) {
- ++NumFactor;
- return W;
- }
- }
- }
-
- return nullptr;
-}
-
/// SimplifyAssociativeBinOp - Generic simplifications for associative binary
/// operations. Returns the simpler value, or null if none was found.
static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS,
MaxRecurse))
return V;
- // Mul distributes over Add. Try some generic simplifications based on this.
- if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul,
- Q, MaxRecurse))
- return V;
-
// Threading Add over selects and phi nodes is pointless, so don't bother.
// Threading over the select in "A + select(cond, B, C)" means evaluating
// "A+B" and "A+C" and seeing if they are equal; but they are equal if and
if (Op0 == Op1)
return Constant::getNullValue(Op0->getType());
- // (X*2) - X -> X
- // (X<<1) - X -> X
- Value *X = nullptr;
- if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) ||
- match(Op0, m_Shl(m_Specific(Op1), m_One())))
- return Op1;
+ // X - (0 - Y) -> X if the second sub is NUW.
+ // If Y != 0, 0 - Y is a poison value.
+ // If Y == 0, 0 - Y simplifies to 0.
+ if (BinaryOperator::isNeg(Op1)) {
+ if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
+ assert(BO->getOpcode() == Instruction::Sub &&
+ "Expected a subtraction operator!");
+ if (BO->hasNoUnsignedWrap())
+ return Op0;
+ }
+ }
// (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
// For example, (X + Y) - Y -> X; (Y + X) - Y -> X
- Value *Y = nullptr, *Z = Op1;
+ Value *X = nullptr, *Y = nullptr, *Z = Op1;
if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
// See if "V === Y - Z" simplifies.
if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1))
if (Constant *Result = computePointerDifference(Q.DL, X, Y))
return ConstantExpr::getIntegerCast(Result, Op0->getType(), true);
- // Mul distributes over Sub. Try some generic simplifications based on this.
- if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul,
- Q, MaxRecurse))
- return V;
-
// i1 sub -> xor.
if (MaxRecurse && Op0->getType()->isIntegerTy(1))
if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap())
return X;
+ // Arithmetic shifting an all-sign-bit value is a no-op.
+ unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL);
+ if (NumSignBits == Op0->getType()->getScalarSizeInBits())
+ return Op0;
+
return nullptr;
}
Q, MaxRecurse))
return V;
- // Or distributes over And. Try some generic simplifications based on this.
- if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or,
- Q, MaxRecurse))
- return V;
-
// If the operation is with the result of a select instruction, check whether
// operating on either branch of the select always yields the same value.
if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
MaxRecurse))
return V;
- // And distributes over Or. Try some generic simplifications based on this.
- if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And,
- Q, MaxRecurse))
- return V;
-
// If the operation is with the result of a select instruction, check whether
// operating on either branch of the select always yields the same value.
if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
MaxRecurse))
return V;
- // And distributes over Xor. Try some generic simplifications based on this.
- if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And,
- Q, MaxRecurse))
- return V;
-
// Threading Xor over selects and phi nodes is pointless, so don't bother.
// Threading over the select in "A ^ select(cond, B, C)" means evaluating
// "A^B" and "A^C" and seeing if they are equal; but they are equal if and
if (!CI2->isZero())
Upper = NegOne.udiv(CI2->getValue()) + 1;
} else if (match(LHS, m_SDiv(m_ConstantInt(CI2), m_Value()))) {
- // 'sdiv CI2, x' produces [-|CI2|, |CI2|].
- Upper = CI2->getValue().abs() + 1;
- Lower = (-Upper) + 1;
+ if (CI2->isMinSignedValue()) {
+ // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2].
+ Lower = CI2->getValue();
+ Upper = Lower.lshr(1) + 1;
+ } else {
+ // 'sdiv CI2, x' produces [-|CI2|, |CI2|].
+ Upper = CI2->getValue().abs() + 1;
+ Lower = (-Upper) + 1;
+ }
} else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) {
- // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2].
APInt IntMin = APInt::getSignedMinValue(Width);
APInt IntMax = APInt::getSignedMaxValue(Width);
- APInt Val = CI2->getValue().abs();
- if (!Val.isMinValue()) {
+ APInt Val = CI2->getValue();
+ if (Val.isAllOnesValue()) {
+ // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX]
+ // where CI2 != -1 and CI2 != 0 and CI2 != 1
+ Lower = IntMin + 1;
+ Upper = IntMax + 1;
+ } else if (Val.countLeadingZeros() < Width - 1) {
+ // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2]
+ // where CI2 != -1 and CI2 != 0 and CI2 != 1
Lower = IntMin.sdiv(Val);
- Upper = IntMax.sdiv(Val) + 1;
+ Upper = IntMax.sdiv(Val);
+ if (Lower.sgt(Upper))
+ std::swap(Lower, Upper);
+ Upper = Upper + 1;
+ assert(Upper != Lower && "Upper part of range has wrapped!");
+ }
+ } else if (match(LHS, m_NUWShl(m_ConstantInt(CI2), m_Value()))) {
+ // 'shl nuw CI2, x' produces [CI2, CI2 << CLZ(CI2)]
+ Lower = CI2->getValue();
+ Upper = Lower.shl(Lower.countLeadingZeros()) + 1;
+ } else if (match(LHS, m_NSWShl(m_ConstantInt(CI2), m_Value()))) {
+ if (CI2->isNegative()) {
+ // 'shl nsw CI2, x' produces [CI2 << CLO(CI2)-1, CI2]
+ unsigned ShiftAmount = CI2->getValue().countLeadingOnes() - 1;
+ Lower = CI2->getValue().shl(ShiftAmount);
+ Upper = CI2->getValue() + 1;
+ } else {
+ // 'shl nsw CI2, x' produces [CI2, CI2 << CLZ(CI2)-1]
+ unsigned ShiftAmount = CI2->getValue().countLeadingZeros() - 1;
+ Lower = CI2->getValue();
+ Upper = CI2->getValue().shl(ShiftAmount) + 1;
}
} else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) {
// 'lshr x, CI2' produces [0, UINT_MAX >> CI2].
return getTrue(ITy);
}
+ // handle:
+ // CI2 << X == CI
+ // CI2 << X != CI
+ //
+ // where CI2 is a power of 2 and CI isn't
+ if (auto *CI = dyn_cast<ConstantInt>(RHS)) {
+ const APInt *CI2Val, *CIVal = &CI->getValue();
+ if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) &&
+ CI2Val->isPowerOf2()) {
+ if (!CIVal->isPowerOf2()) {
+ // CI2 << X can equal zero in some circumstances,
+ // this simplification is unsafe if CI is zero.
+ //
+ // We know it is safe if:
+ // - The shift is nsw, we can't shift out the one bit.
+ // - The shift is nuw, we can't shift out the one bit.
+ // - CI2 is one
+ // - CI isn't zero
+ if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() ||
+ *CI2Val == 1 || !CI->isZero()) {
+ if (Pred == ICmpInst::ICMP_EQ)
+ return ConstantInt::getFalse(RHS->getContext());
+ if (Pred == ICmpInst::ICMP_NE)
+ return ConstantInt::getTrue(RHS->getContext());
+ }
+ }
+ if (CIVal->isSignBit() && *CI2Val == 1) {
+ if (Pred == ICmpInst::ICMP_UGT)
+ return ConstantInt::getFalse(RHS->getContext());
+ if (Pred == ICmpInst::ICMP_ULE)
+ return ConstantInt::getTrue(RHS->getContext());
+ }
+ }
+ }
+
if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
LBO->getOperand(1) == RBO->getOperand(1)) {
switch (LBO->getOpcode()) {
static Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const Query &Q, unsigned) {
// The type of the GEP pointer operand.
PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()->getScalarType());
+ unsigned AS = PtrTy->getAddressSpace();
// getelementptr P -> P.
if (Ops.size() == 1)
return Ops[0];
- if (isa<UndefValue>(Ops[0])) {
- // Compute the (pointer) type returned by the GEP instruction.
- Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1));
- Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace());
- if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType()))
- GEPTy = VectorType::get(GEPTy, VT->getNumElements());
+ // Compute the (pointer) type returned by the GEP instruction.
+ Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1));
+ Type *GEPTy = PointerType::get(LastType, AS);
+ if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType()))
+ GEPTy = VectorType::get(GEPTy, VT->getNumElements());
+
+ if (isa<UndefValue>(Ops[0]))
return UndefValue::get(GEPTy);
- }
if (Ops.size() == 2) {
// getelementptr P, 0 -> P.
if (match(Ops[1], m_Zero()))
return Ops[0];
- // getelementptr P, N -> P if P points to a type of zero size.
- if (Q.DL) {
- Type *Ty = PtrTy->getElementType();
- if (Ty->isSized() && Q.DL->getTypeAllocSize(Ty) == 0)
+
+ Type *Ty = PtrTy->getElementType();
+ if (Q.DL && Ty->isSized()) {
+ Value *P;
+ uint64_t C;
+ uint64_t TyAllocSize = Q.DL->getTypeAllocSize(Ty);
+ // getelementptr P, N -> P if P points to a type of zero size.
+ if (TyAllocSize == 0)
return Ops[0];
+
+ // The following transforms are only safe if the ptrtoint cast
+ // doesn't truncate the pointers.
+ if (Ops[1]->getType()->getScalarSizeInBits() ==
+ Q.DL->getPointerSizeInBits(AS)) {
+ auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * {
+ if (match(P, m_Zero()))
+ return Constant::getNullValue(GEPTy);
+ Value *Temp;
+ if (match(P, m_PtrToInt(m_Value(Temp))))
+ if (Temp->getType() == GEPTy)
+ return Temp;
+ return nullptr;
+ };
+
+ // getelementptr V, (sub P, V) -> P if P points to a type of size 1.
+ if (TyAllocSize == 1 &&
+ match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0])))))
+ if (Value *R = PtrToIntOrZero(P))
+ return R;
+
+ // getelementptr V, (ashr (sub P, V), C) -> Q
+ // if P points to a type of size 1 << C.
+ if (match(Ops[1],
+ m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
+ m_ConstantInt(C))) &&
+ TyAllocSize == 1ULL << C)
+ if (Value *R = PtrToIntOrZero(P))
+ return R;
+
+ // getelementptr V, (sdiv (sub P, V), C) -> Q
+ // if P points to a type of size C.
+ if (match(Ops[1],
+ m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
+ m_SpecificInt(TyAllocSize))))
+ if (Value *R = PtrToIntOrZero(P))
+ return R;
+ }
}
}
projects / oota-llvm.git / blobdiff