return I->getOperand(0);
// Otherwise, must be the same type of cast, so just reinsert a new one.
- Res = CastInst::Create(cast<CastInst>(I)->getOpcode(), I->getOperand(0),Ty);
+ // This also handles the case of zext(trunc(x)) -> zext(x).
+ Res = CastInst::CreateIntegerCast(I->getOperand(0), Ty,
+ Opc == Instruction::SExt);
break;
case Instruction::Select: {
Value *True = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
/// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only
/// makes sense if x and y can be efficiently truncated.
///
+/// This function works on both vectors and scalars.
+///
static bool CanEvaluateTruncated(Value *V, const Type *Ty) {
// We can always evaluate constants in another type.
if (isa<Constant>(V))
return 0;
}
-/// GetLeadingZeros - Compute the number of known-zero leading bits.
-static unsigned GetLeadingZeros(Value *V, const TargetData *TD) {
- unsigned Bits = V->getType()->getScalarSizeInBits();
- APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
- ComputeMaskedBits(V, APInt::getAllOnesValue(Bits), KnownZero, KnownOne, TD);
- return KnownZero.countLeadingOnes();
-}
-
/// CanEvaluateZExtd - Determine if the specified value can be computed in the
-/// specified wider type and produce the same low bits. If not, return -1. If
-/// it is possible, return the number of high bits that are known to be zero in
-/// the promoted value.
-static int CanEvaluateZExtd(Value *V, const Type *Ty,unsigned &NumCastsRemoved,
- const TargetData *TD) {
- const Type *OrigTy = V->getType();
-
- if (isa<Constant>(V)) {
- unsigned Extended = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();
-
- // Constants can always be zero ext'd, even if it requires a ConstantExpr.
- if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
- return Extended + CI->getValue().countLeadingZeros();
- return Extended;
- }
+/// specified wider type and produce the same low bits. If not, return false.
+///
+/// If this function returns true, it can also return a non-zero number of bits
+/// (in BitsToClear) which indicates that the value it computes is correct for
+/// the zero extend, but that the additional BitsToClear bits need to be zero'd
+/// out. For example, to promote something like:
+///
+/// %B = trunc i64 %A to i32
+/// %C = lshr i32 %B, 8
+/// %E = zext i32 %C to i64
+///
+/// CanEvaluateZExtd for the 'lshr' will return true, and BitsToClear will be
+/// set to 8 to indicate that the promoted value needs to have bits 24-31
+/// cleared in addition to bits 32-63. Since an 'and' will be generated to
+/// clear the top bits anyway, doing this has no extra cost.
+///
+/// This function works on both vectors and scalars.
+static bool CanEvaluateZExtd(Value *V, const Type *Ty, unsigned &BitsToClear) {
+ BitsToClear = 0;
+ if (isa<Constant>(V))
+ return true;
Instruction *I = dyn_cast<Instruction>(V);
- if (!I) return -1;
+ if (!I) return false;
// If the input is a truncate from the destination type, we can trivially
- // eliminate it, and this will remove a cast overall.
- if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) {
- // If the first operand is itself a cast, and is eliminable, do not count
- // this as an eliminable cast. We would prefer to eliminate those two
- // casts first.
- if (!isa<CastInst>(I->getOperand(0)) && I->hasOneUse())
- ++NumCastsRemoved;
-
- // Figure out the number of known-zero bits coming in.
- return GetLeadingZeros(I->getOperand(0), TD);
- }
+ // eliminate it.
+ if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty)
+ return true;
// We can't extend or shrink something that has multiple uses: doing so would
// require duplicating the instruction in general, which isn't profitable.
- if (!I->hasOneUse()) return -1;
+ if (!I->hasOneUse()) return false;
- int Tmp1, Tmp2;
- unsigned Opc = I->getOpcode();
+ unsigned Opc = I->getOpcode(), Tmp;
switch (Opc) {
+ case Instruction::ZExt: // zext(zext(x)) -> zext(x).
+ case Instruction::SExt: // zext(sext(x)) -> sext(x).
+ case Instruction::Trunc: // zext(trunc(x)) -> trunc(x) or zext(x)
+ return true;
case Instruction::And:
- Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
- if (Tmp1 == -1) return -1;
- Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
- if (Tmp2 == -1) return -1;
- return std::max(Tmp1, Tmp2);
case Instruction::Or:
case Instruction::Xor:
- Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
- if (Tmp1 == -1) return -1;
- Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
- return std::min(Tmp1, Tmp2);
-
case Instruction::Add:
case Instruction::Sub:
case Instruction::Mul:
- Tmp1 = CanEvaluateZExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
- if (Tmp1 == -1) return -1;
- Tmp2 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
- if (Tmp2 == -1) return -1;
- return 0;
+ case Instruction::Shl:
+ if (!CanEvaluateZExtd(I->getOperand(0), Ty, BitsToClear) ||
+ !CanEvaluateZExtd(I->getOperand(1), Ty, Tmp))
+ return false;
+ // These can all be promoted if neither operand has 'bits to clear'.
+ if (BitsToClear == 0 && Tmp == 0)
+ return true;
- //case Instruction::Shl:
- //case Instruction::LShr:
- case Instruction::ZExt:
- // zext(zext(x)) -> zext(x). Since we're replacing it, it isn't eliminated.
- Tmp1 = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();
- return GetLeadingZeros(I, TD)+Tmp1;
+ return false;
- //case Instruction::SExt: zext(sext(x)) -> sext(x) with no upper bits known.
- //case Instruction::Trunc:
+ case Instruction::LShr:
+ // We can promote lshr(x, cst) if we can promote x. This requires the
+ // ultimate 'and' to clear out the high zero bits we're clearing out though.
+ if (ConstantInt *Amt = dyn_cast<ConstantInt>(I->getOperand(1))) {
+ if (!CanEvaluateZExtd(I->getOperand(0), Ty, BitsToClear))
+ return false;
+ BitsToClear += Amt->getZExtValue();
+ if (BitsToClear > V->getType()->getScalarSizeInBits())
+ BitsToClear = V->getType()->getScalarSizeInBits();
+ return true;
+ }
+ // Cannot promote variable LSHR.
+ return false;
case Instruction::Select:
- Tmp1 = CanEvaluateZExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
- if (Tmp1 == -1) return -1;
- Tmp2 = CanEvaluateZExtd(I->getOperand(2), Ty, NumCastsRemoved, TD);
- return std::min(Tmp1, Tmp2);
+ if (!CanEvaluateZExtd(I->getOperand(1), Ty, Tmp) ||
+ !CanEvaluateZExtd(I->getOperand(2), Ty, BitsToClear) ||
+ Tmp != BitsToClear)
+ return false;
+ return true;
case Instruction::PHI: {
// We can change a phi if we can change all operands. Note that we never
// get into trouble with cyclic PHIs here because we only consider
// instructions with a single use.
PHINode *PN = cast<PHINode>(I);
- int Result = CanEvaluateZExtd(PN->getIncomingValue(0), Ty,
- NumCastsRemoved, TD);
- for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
- if (Result == -1) return -1;
- Tmp1 = CanEvaluateZExtd(PN->getIncomingValue(i), Ty, NumCastsRemoved, TD);
- Result = std::min(Result, Tmp1);
- }
- return Result;
+ if (!CanEvaluateZExtd(PN->getIncomingValue(0), Ty, BitsToClear))
+ return false;
+ for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
+ if (!CanEvaluateZExtd(PN->getIncomingValue(i), Ty, Tmp) ||
+ Tmp != BitsToClear)
+ return false;
+ return true;
}
default:
// TODO: Can handle more cases here.
- return -1;
+ return false;
}
}
Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
+ // If this zero extend is only used by a truncate, let the truncate by
+ // eliminated before we try to optimize this zext.
+ if (CI.hasOneUse() && isa<TruncInst>(CI.use_back()))
+ return 0;
+
// If one of the common conversion will work, do it.
if (Instruction *Result = commonCastTransforms(CI))
return Result;
// type. Only do this if the dest type is a simple type, don't convert the
// expression tree to something weird like i93 unless the source is also
// strange.
- if (isa<VectorType>(DestTy) || ShouldChangeType(SrcTy, DestTy)) {
- unsigned NumCastsRemoved = 0;
- int BitsZExt = CanEvaluateZExtd(Src, DestTy, NumCastsRemoved, TD);
- if (BitsZExt == -1) return 0;
+ unsigned BitsToClear;
+ if ((isa<VectorType>(DestTy) || ShouldChangeType(SrcTy, DestTy)) &&
+ CanEvaluateZExtd(Src, DestTy, BitsToClear)) {
+ assert(BitsToClear < SrcTy->getScalarSizeInBits() &&
+ "Unreasonable BitsToClear");
- uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
+ // Okay, we can transform this! Insert the new expression now.
+ DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
+ " to avoid zero extend: " << CI);
+ Value *Res = EvaluateInDifferentType(Src, DestTy, false);
+ assert(Res->getType() == DestTy);
+
+ uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits()-BitsToClear;
uint32_t DestBitSize = DestTy->getScalarSizeInBits();
-
- // If this is a zero-extension, we need to do an AND to maintain the clear
- // top-part of the computation. If we know the result will be zero
- // extended enough already, we don't need the and.
- if (NumCastsRemoved >= 1 ||
- unsigned(BitsZExt) >= DestBitSize-SrcBitSize) {
-
- // Okay, we can transform this! Insert the new expression now.
- DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
- " to avoid zero extend: " << CI);
- Value *Res = EvaluateInDifferentType(Src, DestTy, false);
- assert(Res->getType() == DestTy);
-
- // If the high bits are already filled with zeros, just replace this
- // cast with the result.
- if (unsigned(BitsZExt) >= DestBitSize-SrcBitSize ||
- MaskedValueIsZero(Res, APInt::getHighBitsSet(DestBitSize,
- DestBitSize-SrcBitSize)))
- return ReplaceInstUsesWith(CI, Res);
-
- // We need to emit an AND to clear the high bits.
- Constant *C = ConstantInt::get(CI.getContext(),
- APInt::getLowBitsSet(DestBitSize, SrcBitSize));
- return BinaryOperator::CreateAnd(Res, C);
- }
+
+ // If the high bits are already filled with zeros, just replace this
+ // cast with the result.
+ if (MaskedValueIsZero(Res, APInt::getHighBitsSet(DestBitSize,
+ DestBitSize-SrcBitsKept)))
+ return ReplaceInstUsesWith(CI, Res);
+
+ // We need to emit an AND to clear the high bits.
+ Constant *C = ConstantInt::get(Res->getType(),
+ APInt::getLowBitsSet(DestBitSize, SrcBitsKept));
+ return BinaryOperator::CreateAnd(Res, C);
}
// If this is a TRUNC followed by a ZEXT then we are dealing with integral
// types and if the sizes are just right we can convert this into a logical
// 'and' which will be much cheaper than the pair of casts.
if (TruncInst *CSrc = dyn_cast<TruncInst>(Src)) { // A->B->C cast
+ // TODO: Subsume this into EvaluateInDifferentType.
+
// Get the sizes of the types involved. We know that the intermediate type
// will be smaller than A or C, but don't know the relation between A and C.
Value *A = CSrc->getOperand(0);
APInt AndValue(APInt::getLowBitsSet(DstSize, MidSize));
return BinaryOperator::CreateAnd(Trunc,
ConstantInt::get(Trunc->getType(),
- AndValue));
+ AndValue));
}
}
/// to promote integer operations to a wider types will allow us to eliminate
/// the extension.
///
-/// This returns 0 if we can't do this or the number of sign bits that would be
-/// set if we can. For example, CanEvaluateSExtd(i16 1, i64) would return 63,
-/// because the computation can be extended (to "i64 1") and the resulting
-/// computation has 63 equal sign bits.
-///
-/// This function works on both vectors and scalars. For vectors, the result is
-/// the number of bits known sign extended in each element.
+/// This function works on both vectors and scalars.
///
-static unsigned CanEvaluateSExtd(Value *V, const Type *Ty,
- unsigned &NumCastsRemoved, TargetData *TD) {
+static bool CanEvaluateSExtd(Value *V, const Type *Ty) {
assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() &&
"Can't sign extend type to a smaller type");
- // If this is a constant, return the number of sign bits the extended version
- // of it would have.
- if (Constant *C = dyn_cast<Constant>(V))
- return ComputeNumSignBits(ConstantExpr::getSExt(C, Ty), TD);
+ // If this is a constant, it can be trivially promoted.
+ if (isa<Constant>(V))
+ return true;
Instruction *I = dyn_cast<Instruction>(V);
- if (!I) return 0;
+ if (!I) return false;
- // If this is a truncate from the destination type, we can trivially eliminate
- // it, and this will remove a cast overall.
- if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) {
- // If the operand of the truncate is itself a cast, and is eliminable, do
- // not count this as an eliminable cast. We would prefer to eliminate those
- // two casts first.
- if (!isa<CastInst>(I->getOperand(0)) && I->hasOneUse())
- ++NumCastsRemoved;
- return ComputeNumSignBits(I->getOperand(0), TD);
- }
+ // If this is a truncate from the dest type, we can trivially eliminate it.
+ if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty)
+ return true;
// We can't extend or shrink something that has multiple uses: doing so would
// require duplicating the instruction in general, which isn't profitable.
- if (!I->hasOneUse()) return 0;
-
- const Type *OrigTy = V->getType();
+ if (!I->hasOneUse()) return false;
- unsigned Opc = I->getOpcode();
- unsigned Tmp1, Tmp2;
- switch (Opc) {
+ switch (I->getOpcode()) {
+ case Instruction::SExt: // sext(sext(x)) -> sext(x)
+ case Instruction::ZExt: // sext(zext(x)) -> zext(x)
+ case Instruction::Trunc: // sext(trunc(x)) -> trunc(x) or sext(x)
+ return true;
case Instruction::And:
case Instruction::Or:
case Instruction::Xor:
- // These operators can all arbitrarily be extended or truncated.
- Tmp1 = CanEvaluateSExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
- if (Tmp1 == 0) return 0;
- Tmp2 = CanEvaluateSExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
- return std::min(Tmp1, Tmp2);
case Instruction::Add:
case Instruction::Sub:
- // Add/Sub can have at most one carry/borrow bit.
- Tmp1 = CanEvaluateSExtd(I->getOperand(0), Ty, NumCastsRemoved, TD);
- if (Tmp1 == 0) return 0;
- Tmp2 = CanEvaluateSExtd(I->getOperand(1), Ty, NumCastsRemoved, TD);
- if (Tmp2 == 0) return 0;
- return std::min(Tmp1, Tmp2)-1;
case Instruction::Mul:
- // These operators can all arbitrarily be extended or truncated.
- if (!CanEvaluateSExtd(I->getOperand(0), Ty, NumCastsRemoved, TD))
- return 0;
- if (!CanEvaluateSExtd(I->getOperand(1), Ty, NumCastsRemoved, TD))
- return 0;
- return 1; // IMPROVE?
+ // These operators can all arbitrarily be extended if their inputs can.
+ return CanEvaluateSExtd(I->getOperand(0), Ty) &&
+ CanEvaluateSExtd(I->getOperand(1), Ty);
//case Instruction::Shl: TODO
//case Instruction::LShr: TODO
- //case Instruction::Trunc: TODO
- case Instruction::SExt:
- case Instruction::ZExt: {
- // sext(sext(x)) -> sext(x)
- // sext(zext(x)) -> zext(x)
- // Note that replacing a cast does not reduce the number of casts in the
- // input.
- unsigned InSignBits = ComputeNumSignBits(I, TD);
- unsigned ExtBits = Ty->getScalarSizeInBits()-OrigTy->getScalarSizeInBits();
- // We'll end up extending it all the way out.
- return InSignBits+ExtBits;
- }
- case Instruction::Select: {
- SelectInst *SI = cast<SelectInst>(I);
- Tmp1 = CanEvaluateSExtd(SI->getTrueValue(), Ty, NumCastsRemoved, TD);
- if (Tmp1 == 0) return 0;
- Tmp2 = CanEvaluateSExtd(SI->getFalseValue(), Ty, NumCastsRemoved,TD);
- return std::min(Tmp1, Tmp2);
- }
+ case Instruction::Select:
+ return CanEvaluateSExtd(I->getOperand(1), Ty) &&
+ CanEvaluateSExtd(I->getOperand(2), Ty);
+
case Instruction::PHI: {
// We can change a phi if we can change all operands. Note that we never
// get into trouble with cyclic PHIs here because we only consider
// instructions with a single use.
PHINode *PN = cast<PHINode>(I);
- unsigned Result = ~0U;
- for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
- Result = std::min(Result,
- CanEvaluateSExtd(PN->getIncomingValue(i), Ty,
- NumCastsRemoved, TD));
- if (Result == 0) return 0;
- }
- return Result;
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+ if (!CanEvaluateSExtd(PN->getIncomingValue(i), Ty)) return false;
+ return true;
}
default:
// TODO: Can handle more cases here.
break;
}
- return 0;
+ return false;
}
Instruction *InstCombiner::visitSExt(SExtInst &CI) {
+ // If this sign extend is only used by a truncate, let the truncate by
+ // eliminated before we try to optimize this zext.
+ if (CI.hasOneUse() && isa<TruncInst>(CI.use_back()))
+ return 0;
+
if (Instruction *I = commonCastTransforms(CI))
return I;
// type. Only do this if the dest type is a simple type, don't convert the
// expression tree to something weird like i93 unless the source is also
// strange.
- if (isa<VectorType>(DestTy) || ShouldChangeType(SrcTy, DestTy)) {
- unsigned NumCastsRemoved = 0;
- // Check to see if we can do this transformation, and if so, how many bits
- // of the promoted expression will be known copies of the sign bit in the
- // result.
- unsigned NumBitsSExt = CanEvaluateSExtd(Src, DestTy, NumCastsRemoved, TD);
- if (NumBitsSExt == 0)
- return 0;
-
+ if ((isa<VectorType>(DestTy) || ShouldChangeType(SrcTy, DestTy)) &&
+ CanEvaluateSExtd(Src, DestTy)) {
+ // Okay, we can transform this! Insert the new expression now.
+ DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
+ " to avoid sign extend: " << CI);
+ Value *Res = EvaluateInDifferentType(Src, DestTy, true);
+ assert(Res->getType() == DestTy);
+
uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
uint32_t DestBitSize = DestTy->getScalarSizeInBits();
+
+ // If the high bits are already filled with sign bit, just replace this
+ // cast with the result.
+ if (ComputeNumSignBits(Res) > DestBitSize - SrcBitSize)
+ return ReplaceInstUsesWith(CI, Res);
- // Because this is a sign extension, we can always transform it by inserting
- // two new shifts (to do the extension). However, this is only profitable
- // if we've eliminated two or more casts from the input. If we know the
- // result will be sign-extended enough to not require these shifts, we can
- // always do the transformation.
- if (NumCastsRemoved >= 2 ||
- NumBitsSExt > DestBitSize-SrcBitSize) {
- // Okay, we can transform this! Insert the new expression now.
- DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
- " to avoid sign extend: " << CI);
- Value *Res = EvaluateInDifferentType(Src, DestTy, true);
- assert(Res->getType() == DestTy);
-
- // If the high bits are already filled with sign bit, just replace this
- // cast with the result.
- if (NumBitsSExt > DestBitSize - SrcBitSize ||
- ComputeNumSignBits(Res) > DestBitSize - SrcBitSize)
- return ReplaceInstUsesWith(CI, Res);
-
- // We need to emit a cast to truncate, then a cast to sext.
- return new SExtInst(Builder->CreateTrunc(Res, Src->getType()), DestTy);
- }
+ // We need to emit a shl + ashr to do the sign extend.
+ Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize);
+ return BinaryOperator::CreateAShr(Builder->CreateShl(Res, ShAmt, "sext"),
+ ShAmt);
}
// If the input is a shl/ashr pair of a same constant, then this is a sign
projects / oota-llvm.git / blobdiff