From 1b1bb955bb51bc66f9d6b7c7533ab5cf7e6f1129 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Wed, 24 Aug 2016 23:03:36 +0000 Subject: [PATCH] [InstCombine] move foldICmpDivConstConst() contents to foldICmpDivConstant(); NFCI There was no logic in foldICmpDivConstant, so no need for a separate function. The code is directly copy/pasted, so further cleanups to follow. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@279685 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineCompares.cpp | 323 ++++++++++----------- lib/Transforms/InstCombine/InstCombineInternal.h | 2 - 2 files changed, 158 insertions(+), 167 deletions(-) diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp index e1b23500bd8..39a4c24c415 100644 --- a/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -1178,164 +1178,6 @@ Instruction *InstCombiner::foldICmpAddOpConst(Instruction &ICI, return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantExpr::getSub(SMax, C)); } -/// Fold "icmp pred, ([su]div X, DivRHS), CmpRHS" where DivRHS and CmpRHS are -/// both known to be integer constants. -Instruction *InstCombiner::foldICmpDivConstConst(ICmpInst &ICI, - BinaryOperator *DivI, - ConstantInt *DivRHS) { - ConstantInt *CmpRHS = cast(ICI.getOperand(1)); - const APInt &CmpRHSV = CmpRHS->getValue(); - - // FIXME: If the operand types don't match the type of the divide - // then don't attempt this transform. The code below doesn't have the - // logic to deal with a signed divide and an unsigned compare (and - // vice versa). This is because (x /s C1) getOpcode() == Instruction::SDiv; - if (!ICI.isEquality() && DivIsSigned != ICI.isSigned()) - return nullptr; - if (DivRHS->isZero()) - return nullptr; // The ProdOV computation fails on divide by zero. - if (DivIsSigned && DivRHS->isAllOnesValue()) - return nullptr; // The overflow computation also screws up here - if (DivRHS->isOne()) { - // This eliminates some funny cases with INT_MIN. - ICI.setOperand(0, DivI->getOperand(0)); // X/1 == X. - return &ICI; - } - - // Compute Prod = CI * DivRHS. We are essentially solving an equation - // of form X/C1=C2. We solve for X by multiplying C1 (DivRHS) and - // C2 (CI). By solving for X we can turn this into a range check - // instead of computing a divide. - Constant *Prod = ConstantExpr::getMul(CmpRHS, DivRHS); - - // Determine if the product overflows by seeing if the product is - // not equal to the divide. Make sure we do the same kind of divide - // as in the LHS instruction that we're folding. - bool ProdOV = (DivIsSigned ? ConstantExpr::getSDiv(Prod, DivRHS) : - ConstantExpr::getUDiv(Prod, DivRHS)) != CmpRHS; - - // Get the ICmp opcode - ICmpInst::Predicate Pred = ICI.getPredicate(); - - // If the division is known to be exact, then there is no remainder from the - // divide, so the covered range size is unit, otherwise it is the divisor. - ConstantInt *RangeSize = DivI->isExact() ? getOne(Prod) : DivRHS; - - // Figure out the interval that is being checked. For example, a comparison - // like "X /u 5 == 0" is really checking that X is in the interval [0, 5). - // Compute this interval based on the constants involved and the signedness of - // the compare/divide. This computes a half-open interval, keeping track of - // whether either value in the interval overflows. After analysis each - // overflow variable is set to 0 if it's corresponding bound variable is valid - // -1 if overflowed off the bottom end, or +1 if overflowed off the top end. - int LoOverflow = 0, HiOverflow = 0; - Constant *LoBound = nullptr, *HiBound = nullptr; - - if (!DivIsSigned) { // udiv - // e.g. X/5 op 3 --> [15, 20) - LoBound = Prod; - HiOverflow = LoOverflow = ProdOV; - if (!HiOverflow) { - // If this is not an exact divide, then many values in the range collapse - // to the same result value. - HiOverflow = AddWithOverflow(HiBound, LoBound, RangeSize, false); - } - } else if (DivRHS->getValue().isStrictlyPositive()) { // Divisor is > 0. - if (CmpRHSV == 0) { // (X / pos) op 0 - // Can't overflow. e.g. X/2 op 0 --> [-1, 2) - LoBound = ConstantExpr::getNeg(SubOne(RangeSize)); - HiBound = RangeSize; - } else if (CmpRHSV.isStrictlyPositive()) { // (X / pos) op pos - LoBound = Prod; // e.g. X/5 op 3 --> [15, 20) - HiOverflow = LoOverflow = ProdOV; - if (!HiOverflow) - HiOverflow = AddWithOverflow(HiBound, Prod, RangeSize, true); - } else { // (X / pos) op neg - // e.g. X/5 op -3 --> [-15-4, -15+1) --> [-19, -14) - HiBound = AddOne(Prod); - LoOverflow = HiOverflow = ProdOV ? -1 : 0; - if (!LoOverflow) { - ConstantInt *DivNeg =cast(ConstantExpr::getNeg(RangeSize)); - LoOverflow = AddWithOverflow(LoBound, HiBound, DivNeg, true) ? -1 : 0; - } - } - } else if (DivRHS->isNegative()) { // Divisor is < 0. - if (DivI->isExact()) - RangeSize = cast(ConstantExpr::getNeg(RangeSize)); - if (CmpRHSV == 0) { // (X / neg) op 0 - // e.g. X/-5 op 0 --> [-4, 5) - LoBound = AddOne(RangeSize); - HiBound = cast(ConstantExpr::getNeg(RangeSize)); - if (HiBound == DivRHS) { // -INTMIN = INTMIN - HiOverflow = 1; // [INTMIN+1, overflow) - HiBound = nullptr; // e.g. X/INTMIN = 0 --> X > INTMIN - } - } else if (CmpRHSV.isStrictlyPositive()) { // (X / neg) op pos - // e.g. X/-5 op 3 --> [-19, -14) - HiBound = AddOne(Prod); - HiOverflow = LoOverflow = ProdOV ? -1 : 0; - if (!LoOverflow) - LoOverflow = AddWithOverflow(LoBound, HiBound, RangeSize, true) ? -1:0; - } else { // (X / neg) op neg - LoBound = Prod; // e.g. X/-5 op -3 --> [15, 20) - LoOverflow = HiOverflow = ProdOV; - if (!HiOverflow) - HiOverflow = SubWithOverflow(HiBound, Prod, RangeSize, true); - } - - // Dividing by a negative swaps the condition. LT <-> GT - Pred = ICmpInst::getSwappedPredicate(Pred); - } - - Value *X = DivI->getOperand(0); - switch (Pred) { - default: llvm_unreachable("Unhandled icmp opcode!"); - case ICmpInst::ICMP_EQ: - if (LoOverflow && HiOverflow) - return replaceInstUsesWith(ICI, Builder->getFalse()); - if (HiOverflow) - return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE : - ICmpInst::ICMP_UGE, X, LoBound); - if (LoOverflow) - return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT : - ICmpInst::ICMP_ULT, X, HiBound); - return replaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound, - DivIsSigned, true)); - case ICmpInst::ICMP_NE: - if (LoOverflow && HiOverflow) - return replaceInstUsesWith(ICI, Builder->getTrue()); - if (HiOverflow) - return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT : - ICmpInst::ICMP_ULT, X, LoBound); - if (LoOverflow) - return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE : - ICmpInst::ICMP_UGE, X, HiBound); - return replaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound, - DivIsSigned, false)); - case ICmpInst::ICMP_ULT: - case ICmpInst::ICMP_SLT: - if (LoOverflow == +1) // Low bound is greater than input range. - return replaceInstUsesWith(ICI, Builder->getTrue()); - if (LoOverflow == -1) // Low bound is less than input range. - return replaceInstUsesWith(ICI, Builder->getFalse()); - return new ICmpInst(Pred, X, LoBound); - case ICmpInst::ICMP_UGT: - case ICmpInst::ICMP_SGT: - if (HiOverflow == +1) // High bound greater than input range. - return replaceInstUsesWith(ICI, Builder->getFalse()); - if (HiOverflow == -1) // High bound less than input range. - return replaceInstUsesWith(ICI, Builder->getTrue()); - if (Pred == ICmpInst::ICMP_UGT) - return new ICmpInst(ICmpInst::ICMP_UGE, X, HiBound); - return new ICmpInst(ICmpInst::ICMP_SGE, X, HiBound); - } -} - /// Handle "(icmp eq/ne (ashr/lshr const2, A), const1)" -> /// (icmp eq/ne A, Log2(const2/const1)) -> /// (icmp eq/ne A, Log2(const2) - Log2(const1)). @@ -2037,8 +1879,8 @@ Instruction *InstCombiner::foldICmpShrConstant(ICmpInst &Cmp, assert(TheDiv->getOpcode() == Instruction::SDiv || TheDiv->getOpcode() == Instruction::UDiv); - Instruction *Res = - foldICmpDivConstConst(Cmp, TheDiv, cast(DivCst)); + Instruction *Res = foldICmpDivConstant( + Cmp, TheDiv, &(cast(DivCst)->getValue())); assert(Res && "This div/cst should have folded!"); return Res; } @@ -2100,7 +1942,7 @@ Instruction *InstCombiner::foldICmpUDivConstant(ICmpInst &Cmp, } Instruction *InstCombiner::foldICmpDivConstant(ICmpInst &ICI, - BinaryOperator *LHSI, + BinaryOperator *DivI, const APInt *RHSV) { // FIXME: This check restricts all folds under here to scalar types. ConstantInt *RHS = dyn_cast(ICI.getOperand(1)); @@ -2113,10 +1955,161 @@ Instruction *InstCombiner::foldICmpDivConstant(ICmpInst &ICI, // checked. If there is an overflow on the low or high side, remember // it, otherwise compute the range [low, hi) bounding the new value. // See: InsertRangeTest above for the kinds of replacements possible. - if (ConstantInt *DivRHS = dyn_cast(LHSI->getOperand(1))) - if (Instruction *R = - foldICmpDivConstConst(ICI, LHSI, DivRHS)) - return R; + ConstantInt *DivRHS = dyn_cast(DivI->getOperand(1)); + if (!DivRHS) + return nullptr; + + ConstantInt *CmpRHS = cast(ICI.getOperand(1)); + const APInt &CmpRHSV = CmpRHS->getValue(); + + // FIXME: If the operand types don't match the type of the divide + // then don't attempt this transform. The code below doesn't have the + // logic to deal with a signed divide and an unsigned compare (and + // vice versa). This is because (x /s C1) getOpcode() == Instruction::SDiv; + if (!ICI.isEquality() && DivIsSigned != ICI.isSigned()) + return nullptr; + if (DivRHS->isZero()) + return nullptr; // The ProdOV computation fails on divide by zero. + if (DivIsSigned && DivRHS->isAllOnesValue()) + return nullptr; // The overflow computation also screws up here + if (DivRHS->isOne()) { + // This eliminates some funny cases with INT_MIN. + ICI.setOperand(0, DivI->getOperand(0)); // X/1 == X. + return &ICI; + } + + // Compute Prod = CI * DivRHS. We are essentially solving an equation + // of form X/C1=C2. We solve for X by multiplying C1 (DivRHS) and + // C2 (CI). By solving for X we can turn this into a range check + // instead of computing a divide. + Constant *Prod = ConstantExpr::getMul(CmpRHS, DivRHS); + + // Determine if the product overflows by seeing if the product is + // not equal to the divide. Make sure we do the same kind of divide + // as in the LHS instruction that we're folding. + bool ProdOV = (DivIsSigned ? ConstantExpr::getSDiv(Prod, DivRHS) : + ConstantExpr::getUDiv(Prod, DivRHS)) != CmpRHS; + + // Get the ICmp opcode + ICmpInst::Predicate Pred = ICI.getPredicate(); + + // If the division is known to be exact, then there is no remainder from the + // divide, so the covered range size is unit, otherwise it is the divisor. + ConstantInt *RangeSize = DivI->isExact() ? getOne(Prod) : DivRHS; + + // Figure out the interval that is being checked. For example, a comparison + // like "X /u 5 == 0" is really checking that X is in the interval [0, 5). + // Compute this interval based on the constants involved and the signedness of + // the compare/divide. This computes a half-open interval, keeping track of + // whether either value in the interval overflows. After analysis each + // overflow variable is set to 0 if it's corresponding bound variable is valid + // -1 if overflowed off the bottom end, or +1 if overflowed off the top end. + int LoOverflow = 0, HiOverflow = 0; + Constant *LoBound = nullptr, *HiBound = nullptr; + + if (!DivIsSigned) { // udiv + // e.g. X/5 op 3 --> [15, 20) + LoBound = Prod; + HiOverflow = LoOverflow = ProdOV; + if (!HiOverflow) { + // If this is not an exact divide, then many values in the range collapse + // to the same result value. + HiOverflow = AddWithOverflow(HiBound, LoBound, RangeSize, false); + } + } else if (DivRHS->getValue().isStrictlyPositive()) { // Divisor is > 0. + if (CmpRHSV == 0) { // (X / pos) op 0 + // Can't overflow. e.g. X/2 op 0 --> [-1, 2) + LoBound = ConstantExpr::getNeg(SubOne(RangeSize)); + HiBound = RangeSize; + } else if (CmpRHSV.isStrictlyPositive()) { // (X / pos) op pos + LoBound = Prod; // e.g. X/5 op 3 --> [15, 20) + HiOverflow = LoOverflow = ProdOV; + if (!HiOverflow) + HiOverflow = AddWithOverflow(HiBound, Prod, RangeSize, true); + } else { // (X / pos) op neg + // e.g. X/5 op -3 --> [-15-4, -15+1) --> [-19, -14) + HiBound = AddOne(Prod); + LoOverflow = HiOverflow = ProdOV ? -1 : 0; + if (!LoOverflow) { + ConstantInt *DivNeg =cast(ConstantExpr::getNeg(RangeSize)); + LoOverflow = AddWithOverflow(LoBound, HiBound, DivNeg, true) ? -1 : 0; + } + } + } else if (DivRHS->isNegative()) { // Divisor is < 0. + if (DivI->isExact()) + RangeSize = cast(ConstantExpr::getNeg(RangeSize)); + if (CmpRHSV == 0) { // (X / neg) op 0 + // e.g. X/-5 op 0 --> [-4, 5) + LoBound = AddOne(RangeSize); + HiBound = cast(ConstantExpr::getNeg(RangeSize)); + if (HiBound == DivRHS) { // -INTMIN = INTMIN + HiOverflow = 1; // [INTMIN+1, overflow) + HiBound = nullptr; // e.g. X/INTMIN = 0 --> X > INTMIN + } + } else if (CmpRHSV.isStrictlyPositive()) { // (X / neg) op pos + // e.g. X/-5 op 3 --> [-19, -14) + HiBound = AddOne(Prod); + HiOverflow = LoOverflow = ProdOV ? -1 : 0; + if (!LoOverflow) + LoOverflow = AddWithOverflow(LoBound, HiBound, RangeSize, true) ? -1:0; + } else { // (X / neg) op neg + LoBound = Prod; // e.g. X/-5 op -3 --> [15, 20) + LoOverflow = HiOverflow = ProdOV; + if (!HiOverflow) + HiOverflow = SubWithOverflow(HiBound, Prod, RangeSize, true); + } + + // Dividing by a negative swaps the condition. LT <-> GT + Pred = ICmpInst::getSwappedPredicate(Pred); + } + + Value *X = DivI->getOperand(0); + switch (Pred) { + default: llvm_unreachable("Unhandled icmp opcode!"); + case ICmpInst::ICMP_EQ: + if (LoOverflow && HiOverflow) + return replaceInstUsesWith(ICI, Builder->getFalse()); + if (HiOverflow) + return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE : + ICmpInst::ICMP_UGE, X, LoBound); + if (LoOverflow) + return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT : + ICmpInst::ICMP_ULT, X, HiBound); + return replaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound, + DivIsSigned, true)); + case ICmpInst::ICMP_NE: + if (LoOverflow && HiOverflow) + return replaceInstUsesWith(ICI, Builder->getTrue()); + if (HiOverflow) + return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT : + ICmpInst::ICMP_ULT, X, LoBound); + if (LoOverflow) + return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE : + ICmpInst::ICMP_UGE, X, HiBound); + return replaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound, + DivIsSigned, false)); + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_SLT: + if (LoOverflow == +1) // Low bound is greater than input range. + return replaceInstUsesWith(ICI, Builder->getTrue()); + if (LoOverflow == -1) // Low bound is less than input range. + return replaceInstUsesWith(ICI, Builder->getFalse()); + return new ICmpInst(Pred, X, LoBound); + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_SGT: + if (HiOverflow == +1) // High bound greater than input range. + return replaceInstUsesWith(ICI, Builder->getFalse()); + if (HiOverflow == -1) // High bound less than input range. + return replaceInstUsesWith(ICI, Builder->getTrue()); + if (Pred == ICmpInst::ICMP_UGT) + return new ICmpInst(ICmpInst::ICMP_UGE, X, HiBound); + return new ICmpInst(ICmpInst::ICMP_SGE, X, HiBound); + } return nullptr; } diff --git a/lib/Transforms/InstCombine/InstCombineInternal.h b/lib/Transforms/InstCombine/InstCombineInternal.h index 8f2a7f45dc8..32e0bdd3da4 100644 --- a/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/lib/Transforms/InstCombine/InstCombineInternal.h @@ -548,8 +548,6 @@ private: ConstantInt *AndCst = nullptr); Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI, Constant *RHSC); - Instruction *foldICmpDivConstConst(ICmpInst &ICI, BinaryOperator *DivI, - ConstantInt *DivRHS); Instruction *foldICmpCstShrConst(ICmpInst &I, Value *Op, Value *A, ConstantInt *CI1, ConstantInt *CI2); Instruction *foldICmpCstShlConst(ICmpInst &I, Value *Op, Value *A, -- 2.11.0