diff options
Diffstat (limited to 'lib/Transforms/InstCombine/InstructionCombining.cpp')
| -rw-r--r-- | lib/Transforms/InstCombine/InstructionCombining.cpp | 2450 |
1 files changed, 16 insertions, 2434 deletions
diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index 82cc9ebac1..a0bd43ab70 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -48,7 +48,6 @@ #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Support/CallSite.h" -#include "llvm/Support/ConstantRange.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/GetElementPtrTypeIterator.h" @@ -79,20 +78,6 @@ void InstCombiner::getAnalysisUsage(AnalysisUsage &AU) const { } -// getComplexity: Assign a complexity or rank value to LLVM Values... -// 0 -> undef, 1 -> Const, 2 -> Other, 3 -> Arg, 3 -> Unary, 4 -> OtherInst -static unsigned getComplexity(Value *V) { - if (isa<Instruction>(V)) { - if (BinaryOperator::isNeg(V) || - BinaryOperator::isFNeg(V) || - BinaryOperator::isNot(V)) - return 3; - return 4; - } - if (isa<Argument>(V)) return 3; - return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2; -} - // isOnlyUse - Return true if this instruction will be deleted if we stop using // it. static bool isOnlyUse(Value *V) { @@ -246,7 +231,7 @@ bool InstCombiner::SimplifyCommutative(BinaryOperator &I) { // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction // if the LHS is a constant zero (which is the 'negate' form). // -static inline Value *dyn_castNegVal(Value *V) { +Value *InstCombiner::dyn_castNegVal(Value *V) const { if (BinaryOperator::isNeg(V)) return BinaryOperator::getNegArgument(V); @@ -392,13 +377,11 @@ static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) { /// AddOne - Add one to a ConstantInt static Constant *AddOne(Constant *C) { - return ConstantExpr::getAdd(C, - ConstantInt::get(C->getType(), 1)); + return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); } /// SubOne - Subtract one from a ConstantInt static Constant *SubOne(ConstantInt *C) { - return ConstantExpr::getSub(C, - ConstantInt::get(C->getType(), 1)); + return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1)); } /// MultiplyOverflows - True if the multiply can not be expressed in an int /// this size. @@ -424,49 +407,6 @@ static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) { } -// ComputeSignedMinMaxValuesFromKnownBits - Given a signed integer type and a -// set of known zero and one bits, compute the maximum and minimum values that -// could have the specified known zero and known one bits, returning them in -// min/max. -static void ComputeSignedMinMaxValuesFromKnownBits(const APInt& KnownZero, - const APInt& KnownOne, - APInt& Min, APInt& Max) { - assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() && - KnownZero.getBitWidth() == Min.getBitWidth() && - KnownZero.getBitWidth() == Max.getBitWidth() && - "KnownZero, KnownOne and Min, Max must have equal bitwidth."); - APInt UnknownBits = ~(KnownZero|KnownOne); - - // The minimum value is when all unknown bits are zeros, EXCEPT for the sign - // bit if it is unknown. - Min = KnownOne; - Max = KnownOne|UnknownBits; - - if (UnknownBits.isNegative()) { // Sign bit is unknown - Min.set(Min.getBitWidth()-1); - Max.clear(Max.getBitWidth()-1); - } -} - -// ComputeUnsignedMinMaxValuesFromKnownBits - Given an unsigned integer type and -// a set of known zero and one bits, compute the maximum and minimum values that -// could have the specified known zero and known one bits, returning them in -// min/max. -static void ComputeUnsignedMinMaxValuesFromKnownBits(const APInt &KnownZero, - const APInt &KnownOne, - APInt &Min, APInt &Max) { - assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() && - KnownZero.getBitWidth() == Min.getBitWidth() && - KnownZero.getBitWidth() == Max.getBitWidth() && - "Ty, KnownZero, KnownOne and Min, Max must have equal bitwidth."); - APInt UnknownBits = ~(KnownZero|KnownOne); - - // The minimum value is when the unknown bits are all zeros. - Min = KnownOne; - // The maximum value is when the unknown bits are all ones. - Max = KnownOne|UnknownBits; -} - /// AssociativeOpt - Perform an optimization on an associative operator. This /// function is designed to check a chain of associative operators for a @@ -1138,8 +1078,8 @@ Instruction *InstCombiner::visitFAdd(BinaryOperator &I) { /// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the /// code necessary to compute the offset from the base pointer (without adding /// in the base pointer). Return the result as a signed integer of intptr size. -static Value *EmitGEPOffset(User *GEP, InstCombiner &IC) { - TargetData &TD = *IC.getTargetData(); +Value *InstCombiner::EmitGEPOffset(User *GEP) { + TargetData &TD = *getTargetData(); gep_type_iterator GTI = gep_type_begin(GEP); const Type *IntPtrTy = TD.getIntPtrType(GEP->getContext()); Value *Result = Constant::getNullValue(IntPtrTy); @@ -1159,9 +1099,9 @@ static Value *EmitGEPOffset(User *GEP, InstCombiner &IC) { if (const StructType *STy = dyn_cast<StructType>(*GTI)) { Size = TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); - Result = IC.Builder->CreateAdd(Result, - ConstantInt::get(IntPtrTy, Size), - GEP->getName()+".offs"); + Result = Builder->CreateAdd(Result, + ConstantInt::get(IntPtrTy, Size), + GEP->getName()+".offs"); continue; } @@ -1170,130 +1110,25 @@ static Value *EmitGEPOffset(User *GEP, InstCombiner &IC) { ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/); Scale = ConstantExpr::getMul(OC, Scale); // Emit an add instruction. - Result = IC.Builder->CreateAdd(Result, Scale, GEP->getName()+".offs"); + Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs"); continue; } // Convert to correct type. if (Op->getType() != IntPtrTy) - Op = IC.Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c"); + Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c"); if (Size != 1) { Constant *Scale = ConstantInt::get(IntPtrTy, Size); // We'll let instcombine(mul) convert this to a shl if possible. - Op = IC.Builder->CreateMul(Op, Scale, GEP->getName()+".idx"); + Op = Builder->CreateMul(Op, Scale, GEP->getName()+".idx"); } // Emit an add instruction. - Result = IC.Builder->CreateAdd(Op, Result, GEP->getName()+".offs"); + Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs"); } return Result; } -/// EvaluateGEPOffsetExpression - Return a value that can be used to compare -/// the *offset* implied by a GEP to zero. For example, if we have &A[i], we -/// want to return 'i' for "icmp ne i, 0". Note that, in general, indices can -/// be complex, and scales are involved. The above expression would also be -/// legal to codegen as "icmp ne (i*4), 0" (assuming A is a pointer to i32). -/// This later form is less amenable to optimization though, and we are allowed -/// to generate the first by knowing that pointer arithmetic doesn't overflow. -/// -/// If we can't emit an optimized form for this expression, this returns null. -/// -static Value *EvaluateGEPOffsetExpression(User *GEP, Instruction &I, - InstCombiner &IC) { - TargetData &TD = *IC.getTargetData(); - gep_type_iterator GTI = gep_type_begin(GEP); - - // Check to see if this gep only has a single variable index. If so, and if - // any constant indices are a multiple of its scale, then we can compute this - // in terms of the scale of the variable index. For example, if the GEP - // implies an offset of "12 + i*4", then we can codegen this as "3 + i", - // because the expression will cross zero at the same point. - unsigned i, e = GEP->getNumOperands(); - int64_t Offset = 0; - for (i = 1; i != e; ++i, ++GTI) { - if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) { - // Compute the aggregate offset of constant indices. - if (CI->isZero()) continue; - - // Handle a struct index, which adds its field offset to the pointer. - if (const StructType *STy = dyn_cast<StructType>(*GTI)) { - Offset += TD.getStructLayout(STy)->getElementOffset(CI->getZExtValue()); - } else { - uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()); - Offset += Size*CI->getSExtValue(); - } - } else { - // Found our variable index. - break; - } - } - - // If there are no variable indices, we must have a constant offset, just - // evaluate it the general way. - if (i == e) return 0; - - Value *VariableIdx = GEP->getOperand(i); - // Determine the scale factor of the variable element. For example, this is - // 4 if the variable index is into an array of i32. - uint64_t VariableScale = TD.getTypeAllocSize(GTI.getIndexedType()); - - // Verify that there are no other variable indices. If so, emit the hard way. - for (++i, ++GTI; i != e; ++i, ++GTI) { - ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i)); - if (!CI) return 0; - - // Compute the aggregate offset of constant indices. - if (CI->isZero()) continue; - - // Handle a struct index, which adds its field offset to the pointer. - if (const StructType *STy = dyn_cast<StructType>(*GTI)) { - Offset += TD.getStructLayout(STy)->getElementOffset(CI->getZExtValue()); - } else { - uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()); - Offset += Size*CI->getSExtValue(); - } - } - - // Okay, we know we have a single variable index, which must be a - // pointer/array/vector index. If there is no offset, life is simple, return - // the index. - unsigned IntPtrWidth = TD.getPointerSizeInBits(); - if (Offset == 0) { - // Cast to intptrty in case a truncation occurs. If an extension is needed, - // we don't need to bother extending: the extension won't affect where the - // computation crosses zero. - if (VariableIdx->getType()->getPrimitiveSizeInBits() > IntPtrWidth) - VariableIdx = new TruncInst(VariableIdx, - TD.getIntPtrType(VariableIdx->getContext()), - VariableIdx->getName(), &I); - return VariableIdx; - } - - // Otherwise, there is an index. The computation we will do will be modulo - // the pointer size, so get it. - uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth); - - Offset &= PtrSizeMask; - VariableScale &= PtrSizeMask; - - // To do this transformation, any constant index must be a multiple of the - // variable scale factor. For example, we can evaluate "12 + 4*i" as "3 + i", - // but we can't evaluate "10 + 3*i" in terms of i. Check that the offset is a - // multiple of the variable scale. - int64_t NewOffs = Offset / (int64_t)VariableScale; - if (Offset != NewOffs*(int64_t)VariableScale) - return 0; - - // Okay, we can do this evaluation. Start by converting the index to intptr. - const Type *IntPtrTy = TD.getIntPtrType(VariableIdx->getContext()); - if (VariableIdx->getType() != IntPtrTy) - VariableIdx = CastInst::CreateIntegerCast(VariableIdx, IntPtrTy, - true /*SExt*/, - VariableIdx->getName(), &I); - Constant *OffsetVal = ConstantInt::get(IntPtrTy, NewOffs); - return BinaryOperator::CreateAdd(VariableIdx, OffsetVal, "offset", &I); -} /// Optimize pointer differences into the same array into a size. Consider: @@ -1349,12 +1184,12 @@ Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS, return 0; // Emit the offset of the GEP and an intptr_t. - Value *Result = EmitGEPOffset(GEP, *this); + Value *Result = EmitGEPOffset(GEP); // If we had a constant expression GEP on the other side offsetting the // pointer, subtract it from the offset we have. if (CstGEP) { - Value *CstOffset = EmitGEPOffset(CstGEP, *this); + Value *CstOffset = EmitGEPOffset(CstGEP); Result = Builder->CreateSub(Result, CstOffset); } @@ -1559,36 +1394,6 @@ Instruction *InstCombiner::visitFSub(BinaryOperator &I) { return 0; } -/// isSignBitCheck - Given an exploded icmp instruction, return true if the -/// comparison only checks the sign bit. If it only checks the sign bit, set -/// TrueIfSigned if the result of the comparison is true when the input value is -/// signed. -static bool isSignBitCheck(ICmpInst::Predicate pred, ConstantInt *RHS, - bool &TrueIfSigned) { - switch (pred) { - case ICmpInst::ICMP_SLT: // True if LHS s< 0 - TrueIfSigned = true; - return RHS->isZero(); - case ICmpInst::ICMP_SLE: // True if LHS s<= RHS and RHS == -1 - TrueIfSigned = true; - return RHS->isAllOnesValue(); - case ICmpInst::ICMP_SGT: // True if LHS s> -1 - TrueIfSigned = false; - return RHS->isAllOnesValue(); - case ICmpInst::ICMP_UGT: - // True if LHS u> RHS and RHS == high-bit-mask - 1 - TrueIfSigned = true; - return RHS->getValue() == - APInt::getSignedMaxValue(RHS->getType()->getPrimitiveSizeInBits()); - case ICmpInst::ICMP_UGE: - // True if LHS u>= RHS and RHS == high-bit-mask (2^7, 2^15, 2^31, etc) - TrueIfSigned = true; - return RHS->getValue().isSignBit(); - default: - return false; - } -} - Instruction *InstCombiner::visitMul(BinaryOperator &I) { bool Changed = SimplifyCommutative(I); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); @@ -2242,12 +2047,6 @@ static bool isOneBitSet(const ConstantInt *CI) { return CI->getValue().isPowerOf2(); } -// isHighOnes - Return true if the constant is of the form 1+0+. -// This is the same as lowones(~X). -static bool isHighOnes(const ConstantInt *CI) { - return (~CI->getValue() + 1).isPowerOf2(); -} - /// getICmpCode - Encode a icmp predicate into a three bit mask. These bits /// are carefully arranged to allow folding of expressions such as: /// @@ -4186,2223 +3985,6 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { return Changed ? &I : 0; } -static ConstantInt *ExtractElement(Constant *V, Constant *Idx) { - return cast<ConstantInt>(ConstantExpr::getExtractElement(V, Idx)); -} - -static bool HasAddOverflow(ConstantInt *Result, - ConstantInt *In1, ConstantInt *In2, - bool IsSigned) { - if (IsSigned) - if (In2->getValue().isNegative()) - return Result->getValue().sgt(In1->getValue()); - else - return Result->getValue().slt(In1->getValue()); - else - return Result->getValue().ult(In1->getValue()); -} - -/// AddWithOverflow - Compute Result = In1+In2, returning true if the result -/// overflowed for this type. -static bool AddWithOverflow(Constant *&Result, Constant *In1, - Constant *In2, bool IsSigned = false) { - Result = ConstantExpr::getAdd(In1, In2); - - if (const VectorType *VTy = dyn_cast<VectorType>(In1->getType())) { - for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { - Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i); - if (HasAddOverflow(ExtractElement(Result, Idx), - ExtractElement(In1, Idx), - ExtractElement(In2, Idx), - IsSigned)) - return true; - } - return false; - } - - return HasAddOverflow(cast<ConstantInt>(Result), - cast<ConstantInt>(In1), cast<ConstantInt>(In2), - IsSigned); -} - -static bool HasSubOverflow(ConstantInt *Result, - ConstantInt *In1, ConstantInt *In2, - bool IsSigned) { - if (IsSigned) - if (In2->getValue().isNegative()) - return Result->getValue().slt(In1->getValue()); - else - return Result->getValue().sgt(In1->getValue()); - else - return Result->getValue().ugt(In1->getValue()); -} - -/// SubWithOverflow - Compute Result = In1-In2, returning true if the result -/// overflowed for this type. -static bool SubWithOverflow(Constant *&Result, Constant *In1, - Constant *In2, bool IsSigned = false) { - Result = ConstantExpr::getSub(In1, In2); - - if (const VectorType *VTy = dyn_cast<VectorType>(In1->getType())) { - for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { - Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i); - if (HasSubOverflow(ExtractElement(Result, Idx), - ExtractElement(In1, Idx), - ExtractElement(In2, Idx), - IsSigned)) - return true; - } - return false; - } - - return HasSubOverflow(cast<ConstantInt>(Result), - cast<ConstantInt>(In1), cast<ConstantInt>(In2), - IsSigned); -} - - -/// FoldGEPICmp - Fold comparisons between a GEP instruction and something -/// else. At this point we know that the GEP is on the LHS of the comparison. -Instruction *InstCombiner::FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS, - ICmpInst::Predicate Cond, - Instruction &I) { - // Look through bitcasts. - if (BitCastInst *BCI = dyn_cast<BitCastInst>(RHS)) - RHS = BCI->getOperand(0); - - Value *PtrBase = GEPLHS->getOperand(0); - if (TD && PtrBase == RHS && GEPLHS->isInBounds()) { - // ((gep Ptr, OFFSET) cmp Ptr) ---> (OFFSET cmp 0). - // This transformation (ignoring the base and scales) is valid because we - // know pointers can't overflow since the gep is inbounds. See if we can - // output an optimized form. - Value *Offset = EvaluateGEPOffsetExpression(GEPLHS, I, *this); - - // If not, synthesize the offset the hard way. - if (Offset == 0) - Offset = EmitGEPOffset(GEPLHS, *this); - return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Offset, - Constant::getNullValue(Offset->getType())); - } else if (GEPOperator *GEPRHS = dyn_cast<GEPOperator>(RHS)) { - // If the base pointers are different, but the indices are the same, just - // compare the base pointer. - if (PtrBase != GEPRHS->getOperand(0)) { - bool IndicesTheSame = GEPLHS->getNumOperands()==GEPRHS->getNumOperands(); - IndicesTheSame &= GEPLHS->getOperand(0)->getType() == - GEPRHS->getOperand(0)->getType(); - if (IndicesTheSame) - for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i) - if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) { - IndicesTheSame = false; - break; - } - - // If all indices are the same, just compare the base pointers. - if (IndicesTheSame) - return new ICmpInst(ICmpInst::getSignedPredicate(Cond), - GEPLHS->getOperand(0), GEPRHS->getOperand(0)); - - // Otherwise, the base pointers are different and the indices are - // different, bail out. - return 0; - } - - // If one of the GEPs has all zero indices, recurse. - bool AllZeros = true; - for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i) - if (!isa<Constant>(GEPLHS->getOperand(i)) || - !cast<Constant>(GEPLHS->getOperand(i))->isNullValue()) { - AllZeros = false; - break; - } - if (AllZeros) - return FoldGEPICmp(GEPRHS, GEPLHS->getOperand(0), - ICmpInst::getSwappedPredicate(Cond), I); - - // If the other GEP has all zero indices, recurse. - AllZeros = true; - for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i) - if (!isa<Constant>(GEPRHS->getOperand(i)) || - !cast<Constant>(GEPRHS->getOperand(i))->isNullValue()) { - AllZeros = false; - break; - } - if (AllZeros) - return FoldGEPICmp(GEPLHS, GEPRHS->getOperand(0), Cond, I); - - if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands()) { - // If the GEPs only differ by one index, compare it. - unsigned NumDifferences = 0; // Keep track of # differences. - unsigned DiffOperand = 0; // The operand that differs. - for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i) - if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) { - if (GEPLHS->getOperand(i)->getType()->getPrimitiveSizeInBits() != - GEPRHS->getOperand(i)->getType()->getPrimitiveSizeInBits()) { - // Irreconcilable differences. - NumDifferences = 2; - break; - } else { - if (NumDifferences++) break; - DiffOperand = i; - } - } - - if (NumDifferences == 0) // SAME GEP? - return ReplaceInstUsesWith(I, // No comparison is needed here. - ConstantInt::get(Type::getInt1Ty(I.getContext()), - ICmpInst::isTrueWhenEqual(Cond))); - - else if (NumDifferences == 1) { - Value *LHSV = GEPLHS->getOperand(DiffOperand); - Value *RHSV = GEPRHS->getOperand(DiffOperand); - // Make sure we do a signed comparison here. - return new ICmpInst(ICmpInst::getSignedPredicate(Cond), LHSV, RHSV); - } - } - - // Only lower this if the icmp is the only user of the GEP or if we expect - // the result to fold to a constant! - if (TD && - (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) && - (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) { - // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2) ---> (OFFSET1 cmp OFFSET2) - Value *L = EmitGEPOffset(GEPLHS, *this); - Value *R = EmitGEPOffset(GEPRHS, *this); - return new ICmpInst(ICmpInst::getSignedPredicate(Cond), L, R); - } - } - return 0; -} - -/// FoldFCmp_IntToFP_Cst - Fold fcmp ([us]itofp x, cst) if possible. -/// -Instruction *InstCombiner::FoldFCmp_IntToFP_Cst(FCmpInst &I, - Instruction *LHSI, - Constant *RHSC) { - if (!isa<ConstantFP>(RHSC)) return 0; - const APFloat &RHS = cast<ConstantFP>(RHSC)->getValueAPF(); - - // Get the width of the mantissa. We don't want to hack on conversions that - // might lose information from the integer, e.g. "i64 -> float" - int MantissaWidth = LHSI->getType()->getFPMantissaWidth(); - if (MantissaWidth == -1) return 0; // Unknown. - - // Check to see that the input is converted from an integer type that is small - // enough that preserves all bits. TODO: check here for "known" sign bits. - // This would allow us to handle (fptosi (x >>s 62) to float) if x is i64 f.e. - unsigned InputSize = LHSI->getOperand(0)->getType()->getScalarSizeInBits(); - - // If this is a uitofp instruction, we need an extra bit to hold the sign. - bool LHSUnsigned = isa<UIToFPInst>(LHSI); - if (LHSUnsigned) - ++InputSize; - - // If the conversion would lose info, don't hack on this. - if ((int)InputSize > MantissaWidth) - return 0; - - // Otherwise, we can potentially simplify the comparison. We know that it - // will always come through as an integer value and we know the constant is - // not a NAN (it would have been previously simplified). - assert(!RHS.isNaN() && "NaN comparison not already folded!"); - - ICmpInst::Predicate Pred; - switch (I.getPredicate()) { - default: llvm_unreachable("Unexpected predicate!"); - case FCmpInst::FCMP_UEQ: - case FCmpInst::FCMP_OEQ: - Pred = ICmpInst::ICMP_EQ; - break; - case FCmpInst::FCMP_UGT: - case FCmpInst::FCMP_OGT: - Pred = LHSUnsigned ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_SGT; - break; - case FCmpInst::FCMP_UGE: - case FCmpInst::FCMP_OGE: - Pred = LHSUnsigned ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_SGE; - break; - case FCmpInst::FCMP_ULT: - case FCmpInst::FCMP_OLT: - Pred = LHSUnsigned ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_SLT; - break; - case FCmpInst::FCMP_ULE: - case FCmpInst::FCMP_OLE: - Pred = LHSUnsigned ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_SLE; - break; - case FCmpInst::FCMP_UNE: - case FCmpInst::FCMP_ONE: - Pred = ICmpInst::ICMP_NE; - break; - case FCmpInst::FCMP_ORD: - return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext())); - case FCmpInst::FCMP_UNO: - return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext())); - } - - const IntegerType *IntTy = cast<IntegerType>(LHSI->getOperand(0)->getType()); - - // Now we know that the APFloat is a normal number, zero or inf. - - // See if the FP constant is too large for the integer. For example, - // comparing an i8 to 300.0. - unsigned IntWidth = IntTy->getScalarSizeInBits(); - - if (!LHSUnsigned) { - // If the RHS value is > SignedMax, fold the comparison. This handles +INF - // and large values. - APFloat SMax(RHS.getSemantics(), APFloat::fcZero, false); - SMax.convertFromAPInt(APInt::getSignedMaxValue(IntWidth), true, - APFloat::rmNearestTiesToEven); - if (SMax.compare(RHS) == APFloat::cmpLessThan) { // smax < 13123.0 - if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SLT || - Pred == ICmpInst::ICMP_SLE) - return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext())); - return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext())); - } - } else { - // If the RHS value is > UnsignedMax, fold the comparison. This handles - // +INF and large values. - APFloat UMax(RHS.getSemantics(), APFloat::fcZero, false); - UMax.convertFromAPInt(APInt::getMaxValue(IntWidth), false, - APFloat::rmNearestTiesToEven); - if (UMax.compare(RHS) == APFloat::cmpLessThan) { // umax < 13123.0 - if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_ULT || - Pred == ICmpInst::ICMP_ULE) - return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext())); - return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext())); - } - } - - if (!LHSUnsigned) { - // See if the RHS value is < SignedMin. - APFloat SMin(RHS.getSemantics(), APFloat::fcZero, false); - SMin.convertFromAPInt(APInt::getSignedMinValue(IntWidth), true, - APFloat::rmNearestTiesToEven); - if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { // smin > 12312.0 - if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT || - Pred == ICmpInst::ICMP_SGE) - return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext())); - return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext())); - } - } - - // Okay, now we know that the FP constant fits in the range [SMIN, SMAX] or - // [0, UMAX], but it may still be fractional. See if it is fractional by - // casting the FP value to the integer value and back, checking for equality. - // Don't do this for zero, because -0.0 is not fractional. - Constant *RHSInt = LHSUnsigned - ? ConstantExpr::getFPToUI(RHSC, IntTy) - : ConstantExpr::getFPToSI(RHSC, IntTy); - if (!RHS.isZero()) { - bool Equal = LHSUnsigned - ? ConstantExpr::getUIToFP(RHSInt, RHSC->getType()) == RHSC - : ConstantExpr::getSIToFP(RHSInt, RHSC->getType()) == RHSC; - if (!Equal) { - // If we had a comparison against a fractional value, we have to adjust - // the compare predicate and sometimes the value. RHSC is rounded towards - // zero at this point. - switch (Pred) { - default: llvm_unreachable("Unexpected integer comparison!"); - case ICmpInst::ICMP_NE: // (float)int != 4.4 --> true - return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext())); - case ICmpInst::ICMP_EQ: // (float)int == 4.4 --> false - return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext())); - case ICmpInst::ICMP_ULE: - // (float)int <= 4.4 --> int <= 4 - // (float)int <= -4.4 --> false - if (RHS.isNegative()) - return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext())); - break; - case ICmpInst::ICMP_SLE: - // (float)int <= 4.4 --> int <= 4 - // (float)int <= -4.4 --> int < -4 - if (RHS.isNegative()) - Pred = ICmpInst::ICMP_SLT; - break; - case ICmpInst::ICMP_ULT: - // (float)int < -4.4 --> false - // (float)int < 4.4 --> int <= 4 - if (RHS.isNegative()) - return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getContext())); - Pred = ICmpInst::ICMP_ULE; - break; - case ICmpInst::ICMP_SLT: - // (float)int < -4.4 --> int < -4 - // (float)int < 4.4 --> int <= 4 - if (!RHS.isNegative()) - Pred = ICmpInst::ICMP_SLE; - break; - case ICmpInst::ICMP_UGT: - // (float)int > 4.4 --> int > 4 - // (float)int > -4.4 --> true - if (RHS.isNegative()) - return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext())); - break; - case ICmpInst::ICMP_SGT: - // (float)int > 4.4 --> int > 4 - // (float)int > -4.4 --> int >= -4 - if (RHS.isNegative()) - Pred = ICmpInst::ICMP_SGE; - break; - case ICmpInst::ICMP_UGE: - // (float)int >= -4.4 --> true - // (float)int >= 4.4 --> int > 4 - if (!RHS.isNegative()) - return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getContext())); - Pred = ICmpInst::ICMP_UGT; - break; - case ICmpInst::ICMP_SGE: - // (float)int >= -4.4 --> int >= -4 - // (float)int >= 4.4 --> int > 4 - if (!RHS.isNegative()) - Pred = ICmpInst::ICMP_SGT; - break; - } - } - } - - // Lower this FP comparison into an appropriate integer version of the - // comparison. - return new ICmpInst(Pred, LHSI->getOperand(0), RHSInt); -} - -/// FoldCmpLoadFromIndexedGlobal - Called we see this pattern: -/// cmp pred (load (gep GV, ...)), cmpcst -/// where GV is a global variable with a constant initializer. Try to simplify -/// this into some simple computation that does not need the load. For example -/// we can optimize "icmp eq (load (gep "foo", 0, i)), 0" into "icmp eq i, 3". -/// -/// If AndCst is non-null, then the loaded value is masked with that constant -/// before doing the comparison. This handles cases like "A[i]&4 == 0". -Instruction *InstCombiner:: -FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, GlobalVariable *GV, - CmpInst &ICI, ConstantInt *AndCst) { - ConstantArray *Init = dyn_cast<ConstantArray>(GV->getInitializer()); - if (Init == 0 || Init->getNumOperands() > 1024) return 0; - - // There are many forms of this optimization we can handle, for now, just do - // the simple index into a single-dimensional array. - // - // Require: GEP GV, 0, i {{, constant indices}} - if (GEP->getNumOperands() < 3 || - !isa<ConstantInt>(GEP->getOperand(1)) || - !cast<ConstantInt>(GEP->getOperand(1))->isZero() || - isa<Constant>(GEP->getOperand(2))) - return 0; - - // Check that indices after the variable are constants and in-range for the - // type they index. Collect the indices. This is typically for arrays of - // structs. - SmallVector<unsigned, 4> LaterIndices; - - const Type *EltTy = cast<ArrayType>(Init->getType())->getElementType(); - for (unsigned i = 3, e = GEP->getNumOperands(); i != e; ++i) { - ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i)); - if (Idx == 0) return 0; // Variable index. - - uint64_t IdxVal = Idx->getZExtValue(); - if ((unsigned)IdxVal != IdxVal) return 0; // Too large array index. - - if (const StructType *STy = dyn_cast<StructType>(EltTy)) - EltTy = STy->getElementType(IdxVal); - else if (const ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) { - if (IdxVal >= ATy->getNumElements()) return 0; - EltTy = ATy->getElementType(); - } else { - return 0; // Unknown type. - } - - LaterIndices.push_back(IdxVal); - } - - enum { Overdefined = -3, Undefined = -2 }; - - // Variables for our state machines. - - // FirstTrueElement/SecondTrueElement - Used to emit a comparison of the form - // "i == 47 | i == 87", where 47 is the first index the condition is true for, - // and 87 is the second (and last) index. FirstTrueElement is -2 when - // undefined, otherwise set to the first true element. SecondTrueElement is - // -2 when undefined, -3 when overdefined and >= 0 when that index is true. - int FirstTrueElement = Undefined, SecondTrueElement = Undefined; - - // FirstFalseElement/SecondFalseElement - Used to emit a comparison of the - // form "i != 47 & i != 87". Same state transitions as for true elements. - int FirstFalseElement = Undefined, SecondFalseElement = Undefined; - - /// TrueRangeEnd/FalseRangeEnd - In conjunction with First*Element, these - /// define a state machine that triggers for ranges of values that the index - /// is true or false for. This triggers on things like "abbbbc"[i] == 'b'. - /// This is -2 when undefined, -3 when overdefined, and otherwise the last - /// index in the range (inclusive). We use -2 for undefined here because we - /// use relative comparisons and don't want 0-1 to match -1. - int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined; - - // MagicBitvector - This is a magic bitvector where we set a bit if the - // comparison is true for element 'i'. If there are 64 elements or less in - // the array, this will fully represent all the comparison results. - uint64_t MagicBitvector = 0; - - - // Scan the array and see if one of our patterns matches. - Constant *CompareRHS = cast<Constant>(ICI.getOperand(1)); - for (unsigned i = 0, e = Init->getNumOperands(); i != e; ++i) { - Constant *Elt = Init->getOperand(i); - - // If this is indexing an array of structures, get the structure element. - if (!LaterIndices.empty()) - Elt = ConstantExpr::getExtractValue(Elt, LaterIndices.data(), - LaterIndices.size()); - - // If the element is masked, handle it. - if (AndCst) Elt = ConstantExpr::getAnd(Elt, AndCst); - - // Find out if the comparison would be true or false for the i'th element. - Constant *C = ConstantFoldCompareInstOperands(ICI.getPredicate(), Elt, - CompareRHS, TD); - // If the result is undef for this element, ignore it. - if (isa<UndefValue>(C)) { - // Extend range state machines to cover this element in case there is an - // undef in the middle of the range. - if (TrueRangeEnd == (int)i-1) - TrueRangeEnd = i; - if (FalseRangeEnd == (int)i-1) - FalseRangeEnd = i; - continue; - } - - // If we can't compute the result for any of the elements, we have to give - // up evaluating the entire conditional. - if (!isa<ConstantInt>(C)) return 0; - - // Otherwise, we know if the comparison is true or false for this element, - // update our state machines. - bool IsTrueForElt = !cast<ConstantInt>(C)->isZero(); - - // State machine for single/double/range index comparison. - if (IsTrueForElt) { - // Update the TrueElement state machine. - if (FirstTrueElement == Undefined) - FirstTrueElement = TrueRangeEnd = i; // First true element. - else { - // Update double-compare state machine. - if (SecondTrueElement == Undefined) - SecondTrueElement = i; - else - SecondTrueElement = Overdefined; - - // Update range state machine. - if (TrueRangeEnd == (int)i-1) - TrueRangeEnd = i; - else - TrueRangeEnd = Overdefined; - } - } else { - // Update the FalseElement state machine. - if (FirstFalseElement == Undefined) - FirstFalseElement = FalseRangeEnd = i; // First false element. - else { - // Update double-compare state machine. - if (SecondFalseElement == Undefined) - SecondFalseElement = i; - else - SecondFalseElement = Overdefined; - - // Update range state machine. - if (FalseRangeEnd == (int)i-1) - FalseRangeEnd = i; - else - FalseRangeEnd = Overdefined; - } - } - - - // If this element is in range, update our magic bitvector. - if (i < 64 && IsTrueForElt) - MagicBitvector |= 1ULL << i; - - // If all of our states become overdefined, bail out early. Since the - // predicate is expensive, only check it every 8 elements. This is only - // really useful for really huge arrays. - if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined && - SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined && - FalseRangeEnd == Overdefined) - return 0; - } - - // Now that we've scanned the entire array, emit our new comparison(s). We - // order the state machines |