-
-/// CanEvaluateInDifferentType - Return true if we can take the specified value
-/// and return it as type Ty without inserting any new casts and without
-/// changing the computed value. This is used by code that tries to decide
-/// whether promoting or shrinking integer operations to wider or smaller types
-/// will allow us to eliminate a truncate or extend.
-///
-/// This is a truncation operation if Ty is smaller than V->getType(), or a zero
-/// extension operation if Ty is larger.
-///
-/// If CastOpc is a truncation, then Ty will be a type smaller than V. We
-/// should return true if trunc(V) can be computed by computing V in the smaller
-/// type. If V is an instruction, 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.
-///
-/// If CastOpc is zext, we are asking if the low bits of the value can be
-/// computed in a larger type, which is then and'd to get the final result.
-static bool CanEvaluateInDifferentType(Value *V, const Type *Ty,
- unsigned CastOpc,
- unsigned &NumCastsRemoved) {
- assert(CastOpc == Instruction::ZExt || CastOpc == Instruction::Trunc);
-
- // We can always evaluate constants in another type.
- if (isa<Constant>(V))
- return true;
-
- Instruction *I = dyn_cast<Instruction>(V);
- if (!I) return false;
-
- const Type *OrigTy = V->getType();
-
- // If this is an extension or truncate, we can often eliminate it.
- if (isa<TruncInst>(I) || isa<ZExtInst>(I) || isa<SExtInst>(I)) {
- // If this is a cast from the destination type, we can trivially eliminate
- // it, and this will remove a cast overall.
- if (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;
- 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 false;
-
- unsigned Opc = I->getOpcode();
- switch (Opc) {
- case Instruction::Add:
- case Instruction::Sub:
- case Instruction::Mul:
- case Instruction::And:
- case Instruction::Or:
- case Instruction::Xor:
- // These operators can all arbitrarily be extended or truncated.
- return CanEvaluateInDifferentType(I->getOperand(0), Ty, CastOpc,
- NumCastsRemoved) &&
- CanEvaluateInDifferentType(I->getOperand(1), Ty, CastOpc,
- NumCastsRemoved);
-
- case Instruction::UDiv:
- case Instruction::URem: {
- // UDiv and URem can be truncated if all the truncated bits are zero.
- uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
- uint32_t BitWidth = Ty->getScalarSizeInBits();
- if (BitWidth < OrigBitWidth) {
- APInt Mask = APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth);
- if (MaskedValueIsZero(I->getOperand(0), Mask) &&
- MaskedValueIsZero(I->getOperand(1), Mask)) {
- return CanEvaluateInDifferentType(I->getOperand(0), Ty, CastOpc,
- NumCastsRemoved) &&
- CanEvaluateInDifferentType(I->getOperand(1), Ty, CastOpc,
- NumCastsRemoved);
- }
- }
- break;
- }
- case Instruction::Shl:
- // If we are truncating the result of this SHL, and if it's a shift of a
- // constant amount, we can always perform a SHL in a smaller type.
- if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
- uint32_t BitWidth = Ty->getScalarSizeInBits();
- if (BitWidth < OrigTy->getScalarSizeInBits() &&
- CI->getLimitedValue(BitWidth) < BitWidth)
- return CanEvaluateInDifferentType(I->getOperand(0), Ty, CastOpc,
- NumCastsRemoved);
- }
- break;
- case Instruction::LShr:
- // If this is a truncate of a logical shr, we can truncate it to a smaller
- // lshr iff we know that the bits we would otherwise be shifting in are
- // already zeros.
- if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
- uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
- uint32_t BitWidth = Ty->getScalarSizeInBits();
- if (BitWidth < OrigBitWidth &&
- MaskedValueIsZero(I->getOperand(0),
- APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
- CI->getLimitedValue(BitWidth) < BitWidth) {
- return CanEvaluateInDifferentType(I->getOperand(0), Ty, CastOpc,
- NumCastsRemoved);
- }
- }
- break;
- case Instruction::ZExt:
- case Instruction::SExt:
- case Instruction::Trunc:
- // If this is the same kind of case as our original (e.g. zext+zext), we
- // can safely replace it. Note that replacing it does not reduce the number
- // of casts in the input.
- if (Opc == CastOpc)
- return true;
-
- // sext (zext ty1), ty2 -> zext ty2
- if (CastOpc == Instruction::SExt && Opc == Instruction::ZExt)
- return true;
- break;
- case Instruction::Select: {
- SelectInst *SI = cast<SelectInst>(I);
- return CanEvaluateInDifferentType(SI->getTrueValue(), Ty, CastOpc,
- NumCastsRemoved) &&
- CanEvaluateInDifferentType(SI->getFalseValue(), Ty, CastOpc,
- NumCastsRemoved);
- }
- 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);
- for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
- if (!CanEvaluateInDifferentType(PN->getIncomingValue(i), Ty, CastOpc,
- NumCastsRemoved))
- return false;
- return true;
- }
- default:
- // TODO: Can handle more cases here.
- break;
- }
-
- return false;
-}
-
-/// CanEvaluateSExtd - Return true if we can take the specified value
-/// and return it as type Ty without inserting any new casts and without
-/// changing the value of the common low bits. This is used by code that tries
-/// 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.
-///
-static unsigned CanEvaluateSExtd(Value *V, const Type *Ty,
- unsigned &NumCastsRemoved, TargetData *TD) {
- 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);
-
- Instruction *I = dyn_cast<Instruction>(V);
- if (!I) return 0;
-
- // 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);
- }
-
- // 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();
-
- unsigned Opc = I->getOpcode();
- unsigned Tmp1, Tmp2;
- switch (Opc) {
- 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?
-
- //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::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;
- }
- default:
- // TODO: Can handle more cases here.
- break;
- }
-
- return 0;
-}
-
-
-/// EvaluateInDifferentType - Given an expression that
-/// CanEvaluateInDifferentType or CanEvaluateSExtd returns true for, actually