Home | History | Annotate | Download | only in InstCombine
      1 //===- InstCombineCasts.cpp -----------------------------------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements the visit functions for cast operations.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "InstCombineInternal.h"
     15 #include "llvm/Analysis/ConstantFolding.h"
     16 #include "llvm/IR/DataLayout.h"
     17 #include "llvm/IR/PatternMatch.h"
     18 #include "llvm/Analysis/TargetLibraryInfo.h"
     19 using namespace llvm;
     20 using namespace PatternMatch;
     21 
     22 #define DEBUG_TYPE "instcombine"
     23 
     24 /// Analyze 'Val', seeing if it is a simple linear expression.
     25 /// If so, decompose it, returning some value X, such that Val is
     26 /// X*Scale+Offset.
     27 ///
     28 static Value *decomposeSimpleLinearExpr(Value *Val, unsigned &Scale,
     29                                         uint64_t &Offset) {
     30   if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) {
     31     Offset = CI->getZExtValue();
     32     Scale  = 0;
     33     return ConstantInt::get(Val->getType(), 0);
     34   }
     35 
     36   if (BinaryOperator *I = dyn_cast<BinaryOperator>(Val)) {
     37     // Cannot look past anything that might overflow.
     38     OverflowingBinaryOperator *OBI = dyn_cast<OverflowingBinaryOperator>(Val);
     39     if (OBI && !OBI->hasNoUnsignedWrap() && !OBI->hasNoSignedWrap()) {
     40       Scale = 1;
     41       Offset = 0;
     42       return Val;
     43     }
     44 
     45     if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
     46       if (I->getOpcode() == Instruction::Shl) {
     47         // This is a value scaled by '1 << the shift amt'.
     48         Scale = UINT64_C(1) << RHS->getZExtValue();
     49         Offset = 0;
     50         return I->getOperand(0);
     51       }
     52 
     53       if (I->getOpcode() == Instruction::Mul) {
     54         // This value is scaled by 'RHS'.
     55         Scale = RHS->getZExtValue();
     56         Offset = 0;
     57         return I->getOperand(0);
     58       }
     59 
     60       if (I->getOpcode() == Instruction::Add) {
     61         // We have X+C.  Check to see if we really have (X*C2)+C1,
     62         // where C1 is divisible by C2.
     63         unsigned SubScale;
     64         Value *SubVal =
     65           decomposeSimpleLinearExpr(I->getOperand(0), SubScale, Offset);
     66         Offset += RHS->getZExtValue();
     67         Scale = SubScale;
     68         return SubVal;
     69       }
     70     }
     71   }
     72 
     73   // Otherwise, we can't look past this.
     74   Scale = 1;
     75   Offset = 0;
     76   return Val;
     77 }
     78 
     79 /// If we find a cast of an allocation instruction, try to eliminate the cast by
     80 /// moving the type information into the alloc.
     81 Instruction *InstCombiner::PromoteCastOfAllocation(BitCastInst &CI,
     82                                                    AllocaInst &AI) {
     83   PointerType *PTy = cast<PointerType>(CI.getType());
     84 
     85   BuilderTy AllocaBuilder(*Builder);
     86   AllocaBuilder.SetInsertPoint(&AI);
     87 
     88   // Get the type really allocated and the type casted to.
     89   Type *AllocElTy = AI.getAllocatedType();
     90   Type *CastElTy = PTy->getElementType();
     91   if (!AllocElTy->isSized() || !CastElTy->isSized()) return nullptr;
     92 
     93   unsigned AllocElTyAlign = DL.getABITypeAlignment(AllocElTy);
     94   unsigned CastElTyAlign = DL.getABITypeAlignment(CastElTy);
     95   if (CastElTyAlign < AllocElTyAlign) return nullptr;
     96 
     97   // If the allocation has multiple uses, only promote it if we are strictly
     98   // increasing the alignment of the resultant allocation.  If we keep it the
     99   // same, we open the door to infinite loops of various kinds.
    100   if (!AI.hasOneUse() && CastElTyAlign == AllocElTyAlign) return nullptr;
    101 
    102   uint64_t AllocElTySize = DL.getTypeAllocSize(AllocElTy);
    103   uint64_t CastElTySize = DL.getTypeAllocSize(CastElTy);
    104   if (CastElTySize == 0 || AllocElTySize == 0) return nullptr;
    105 
    106   // If the allocation has multiple uses, only promote it if we're not
    107   // shrinking the amount of memory being allocated.
    108   uint64_t AllocElTyStoreSize = DL.getTypeStoreSize(AllocElTy);
    109   uint64_t CastElTyStoreSize = DL.getTypeStoreSize(CastElTy);
    110   if (!AI.hasOneUse() && CastElTyStoreSize < AllocElTyStoreSize) return nullptr;
    111 
    112   // See if we can satisfy the modulus by pulling a scale out of the array
    113   // size argument.
    114   unsigned ArraySizeScale;
    115   uint64_t ArrayOffset;
    116   Value *NumElements = // See if the array size is a decomposable linear expr.
    117     decomposeSimpleLinearExpr(AI.getOperand(0), ArraySizeScale, ArrayOffset);
    118 
    119   // If we can now satisfy the modulus, by using a non-1 scale, we really can
    120   // do the xform.
    121   if ((AllocElTySize*ArraySizeScale) % CastElTySize != 0 ||
    122       (AllocElTySize*ArrayOffset   ) % CastElTySize != 0) return nullptr;
    123 
    124   unsigned Scale = (AllocElTySize*ArraySizeScale)/CastElTySize;
    125   Value *Amt = nullptr;
    126   if (Scale == 1) {
    127     Amt = NumElements;
    128   } else {
    129     Amt = ConstantInt::get(AI.getArraySize()->getType(), Scale);
    130     // Insert before the alloca, not before the cast.
    131     Amt = AllocaBuilder.CreateMul(Amt, NumElements);
    132   }
    133 
    134   if (uint64_t Offset = (AllocElTySize*ArrayOffset)/CastElTySize) {
    135     Value *Off = ConstantInt::get(AI.getArraySize()->getType(),
    136                                   Offset, true);
    137     Amt = AllocaBuilder.CreateAdd(Amt, Off);
    138   }
    139 
    140   AllocaInst *New = AllocaBuilder.CreateAlloca(CastElTy, Amt);
    141   New->setAlignment(AI.getAlignment());
    142   New->takeName(&AI);
    143   New->setUsedWithInAlloca(AI.isUsedWithInAlloca());
    144 
    145   // If the allocation has multiple real uses, insert a cast and change all
    146   // things that used it to use the new cast.  This will also hack on CI, but it
    147   // will die soon.
    148   if (!AI.hasOneUse()) {
    149     // New is the allocation instruction, pointer typed. AI is the original
    150     // allocation instruction, also pointer typed. Thus, cast to use is BitCast.
    151     Value *NewCast = AllocaBuilder.CreateBitCast(New, AI.getType(), "tmpcast");
    152     replaceInstUsesWith(AI, NewCast);
    153   }
    154   return replaceInstUsesWith(CI, New);
    155 }
    156 
    157 /// Given an expression that CanEvaluateTruncated or CanEvaluateSExtd returns
    158 /// true for, actually insert the code to evaluate the expression.
    159 Value *InstCombiner::EvaluateInDifferentType(Value *V, Type *Ty,
    160                                              bool isSigned) {
    161   if (Constant *C = dyn_cast<Constant>(V)) {
    162     C = ConstantExpr::getIntegerCast(C, Ty, isSigned /*Sext or ZExt*/);
    163     // If we got a constantexpr back, try to simplify it with DL info.
    164     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
    165       C = ConstantFoldConstantExpression(CE, DL, TLI);
    166     return C;
    167   }
    168 
    169   // Otherwise, it must be an instruction.
    170   Instruction *I = cast<Instruction>(V);
    171   Instruction *Res = nullptr;
    172   unsigned Opc = I->getOpcode();
    173   switch (Opc) {
    174   case Instruction::Add:
    175   case Instruction::Sub:
    176   case Instruction::Mul:
    177   case Instruction::And:
    178   case Instruction::Or:
    179   case Instruction::Xor:
    180   case Instruction::AShr:
    181   case Instruction::LShr:
    182   case Instruction::Shl:
    183   case Instruction::UDiv:
    184   case Instruction::URem: {
    185     Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
    186     Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
    187     Res = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
    188     break;
    189   }
    190   case Instruction::Trunc:
    191   case Instruction::ZExt:
    192   case Instruction::SExt:
    193     // If the source type of the cast is the type we're trying for then we can
    194     // just return the source.  There's no need to insert it because it is not
    195     // new.
    196     if (I->getOperand(0)->getType() == Ty)
    197       return I->getOperand(0);
    198 
    199     // Otherwise, must be the same type of cast, so just reinsert a new one.
    200     // This also handles the case of zext(trunc(x)) -> zext(x).
    201     Res = CastInst::CreateIntegerCast(I->getOperand(0), Ty,
    202                                       Opc == Instruction::SExt);
    203     break;
    204   case Instruction::Select: {
    205     Value *True = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
    206     Value *False = EvaluateInDifferentType(I->getOperand(2), Ty, isSigned);
    207     Res = SelectInst::Create(I->getOperand(0), True, False);
    208     break;
    209   }
    210   case Instruction::PHI: {
    211     PHINode *OPN = cast<PHINode>(I);
    212     PHINode *NPN = PHINode::Create(Ty, OPN->getNumIncomingValues());
    213     for (unsigned i = 0, e = OPN->getNumIncomingValues(); i != e; ++i) {
    214       Value *V =
    215           EvaluateInDifferentType(OPN->getIncomingValue(i), Ty, isSigned);
    216       NPN->addIncoming(V, OPN->getIncomingBlock(i));
    217     }
    218     Res = NPN;
    219     break;
    220   }
    221   default:
    222     // TODO: Can handle more cases here.
    223     llvm_unreachable("Unreachable!");
    224   }
    225 
    226   Res->takeName(I);
    227   return InsertNewInstWith(Res, *I);
    228 }
    229 
    230 
    231 /// This function is a wrapper around CastInst::isEliminableCastPair. It
    232 /// simply extracts arguments and returns what that function returns.
    233 static Instruction::CastOps
    234 isEliminableCastPair(const CastInst *CI, ///< First cast instruction
    235                      unsigned opcode,    ///< Opcode for the second cast
    236                      Type *DstTy,        ///< Target type for the second cast
    237                      const DataLayout &DL) {
    238   Type *SrcTy = CI->getOperand(0)->getType();   // A from above
    239   Type *MidTy = CI->getType();                  // B from above
    240 
    241   // Get the opcodes of the two Cast instructions
    242   Instruction::CastOps firstOp = Instruction::CastOps(CI->getOpcode());
    243   Instruction::CastOps secondOp = Instruction::CastOps(opcode);
    244   Type *SrcIntPtrTy =
    245       SrcTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(SrcTy) : nullptr;
    246   Type *MidIntPtrTy =
    247       MidTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(MidTy) : nullptr;
    248   Type *DstIntPtrTy =
    249       DstTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(DstTy) : nullptr;
    250   unsigned Res = CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy,
    251                                                 DstTy, SrcIntPtrTy, MidIntPtrTy,
    252                                                 DstIntPtrTy);
    253 
    254   // We don't want to form an inttoptr or ptrtoint that converts to an integer
    255   // type that differs from the pointer size.
    256   if ((Res == Instruction::IntToPtr && SrcTy != DstIntPtrTy) ||
    257       (Res == Instruction::PtrToInt && DstTy != SrcIntPtrTy))
    258     Res = 0;
    259 
    260   return Instruction::CastOps(Res);
    261 }
    262 
    263 /// Return true if the cast from "V to Ty" actually results in any code being
    264 /// generated and is interesting to optimize out.
    265 /// If the cast can be eliminated by some other simple transformation, we prefer
    266 /// to do the simplification first.
    267 bool InstCombiner::ShouldOptimizeCast(Instruction::CastOps opc, const Value *V,
    268                                       Type *Ty) {
    269   // Noop casts and casts of constants should be eliminated trivially.
    270   if (V->getType() == Ty || isa<Constant>(V)) return false;
    271 
    272   // If this is another cast that can be eliminated, we prefer to have it
    273   // eliminated.
    274   if (const CastInst *CI = dyn_cast<CastInst>(V))
    275     if (isEliminableCastPair(CI, opc, Ty, DL))
    276       return false;
    277 
    278   // If this is a vector sext from a compare, then we don't want to break the
    279   // idiom where each element of the extended vector is either zero or all ones.
    280   if (opc == Instruction::SExt && isa<CmpInst>(V) && Ty->isVectorTy())
    281     return false;
    282 
    283   return true;
    284 }
    285 
    286 
    287 /// @brief Implement the transforms common to all CastInst visitors.
    288 Instruction *InstCombiner::commonCastTransforms(CastInst &CI) {
    289   Value *Src = CI.getOperand(0);
    290 
    291   // Many cases of "cast of a cast" are eliminable. If it's eliminable we just
    292   // eliminate it now.
    293   if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {   // A->B->C cast
    294     if (Instruction::CastOps opc =
    295             isEliminableCastPair(CSrc, CI.getOpcode(), CI.getType(), DL)) {
    296       // The first cast (CSrc) is eliminable so we need to fix up or replace
    297       // the second cast (CI). CSrc will then have a good chance of being dead.
    298       return CastInst::Create(opc, CSrc->getOperand(0), CI.getType());
    299     }
    300   }
    301 
    302   // If we are casting a select then fold the cast into the select
    303   if (SelectInst *SI = dyn_cast<SelectInst>(Src))
    304     if (Instruction *NV = FoldOpIntoSelect(CI, SI))
    305       return NV;
    306 
    307   // If we are casting a PHI then fold the cast into the PHI
    308   if (isa<PHINode>(Src)) {
    309     // We don't do this if this would create a PHI node with an illegal type if
    310     // it is currently legal.
    311     if (!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() ||
    312         ShouldChangeType(CI.getType(), Src->getType()))
    313       if (Instruction *NV = FoldOpIntoPhi(CI))
    314         return NV;
    315   }
    316 
    317   return nullptr;
    318 }
    319 
    320 /// Return true if we can evaluate the specified expression tree as type Ty
    321 /// instead of its larger type, and arrive with the same value.
    322 /// This is used by code that tries to eliminate truncates.
    323 ///
    324 /// Ty will always be a type smaller than V.  We should return true if trunc(V)
    325 /// can be computed by computing V in the smaller type.  If V is an instruction,
    326 /// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only
    327 /// makes sense if x and y can be efficiently truncated.
    328 ///
    329 /// This function works on both vectors and scalars.
    330 ///
    331 static bool canEvaluateTruncated(Value *V, Type *Ty, InstCombiner &IC,
    332                                  Instruction *CxtI) {
    333   // We can always evaluate constants in another type.
    334   if (isa<Constant>(V))
    335     return true;
    336 
    337   Instruction *I = dyn_cast<Instruction>(V);
    338   if (!I) return false;
    339 
    340   Type *OrigTy = V->getType();
    341 
    342   // If this is an extension from the dest type, we can eliminate it, even if it
    343   // has multiple uses.
    344   if ((isa<ZExtInst>(I) || isa<SExtInst>(I)) &&
    345       I->getOperand(0)->getType() == Ty)
    346     return true;
    347 
    348   // We can't extend or shrink something that has multiple uses: doing so would
    349   // require duplicating the instruction in general, which isn't profitable.
    350   if (!I->hasOneUse()) return false;
    351 
    352   unsigned Opc = I->getOpcode();
    353   switch (Opc) {
    354   case Instruction::Add:
    355   case Instruction::Sub:
    356   case Instruction::Mul:
    357   case Instruction::And:
    358   case Instruction::Or:
    359   case Instruction::Xor:
    360     // These operators can all arbitrarily be extended or truncated.
    361     return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
    362            canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
    363 
    364   case Instruction::UDiv:
    365   case Instruction::URem: {
    366     // UDiv and URem can be truncated if all the truncated bits are zero.
    367     uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
    368     uint32_t BitWidth = Ty->getScalarSizeInBits();
    369     if (BitWidth < OrigBitWidth) {
    370       APInt Mask = APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth);
    371       if (IC.MaskedValueIsZero(I->getOperand(0), Mask, 0, CxtI) &&
    372           IC.MaskedValueIsZero(I->getOperand(1), Mask, 0, CxtI)) {
    373         return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
    374                canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
    375       }
    376     }
    377     break;
    378   }
    379   case Instruction::Shl:
    380     // If we are truncating the result of this SHL, and if it's a shift of a
    381     // constant amount, we can always perform a SHL in a smaller type.
    382     if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
    383       uint32_t BitWidth = Ty->getScalarSizeInBits();
    384       if (CI->getLimitedValue(BitWidth) < BitWidth)
    385         return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI);
    386     }
    387     break;
    388   case Instruction::LShr:
    389     // If this is a truncate of a logical shr, we can truncate it to a smaller
    390     // lshr iff we know that the bits we would otherwise be shifting in are
    391     // already zeros.
    392     if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
    393       uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
    394       uint32_t BitWidth = Ty->getScalarSizeInBits();
    395       if (IC.MaskedValueIsZero(I->getOperand(0),
    396             APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth), 0, CxtI) &&
    397           CI->getLimitedValue(BitWidth) < BitWidth) {
    398         return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI);
    399       }
    400     }
    401     break;
    402   case Instruction::Trunc:
    403     // trunc(trunc(x)) -> trunc(x)
    404     return true;
    405   case Instruction::ZExt:
    406   case Instruction::SExt:
    407     // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest
    408     // trunc(ext(x)) -> trunc(x) if the source type is larger than the new dest
    409     return true;
    410   case Instruction::Select: {
    411     SelectInst *SI = cast<SelectInst>(I);
    412     return canEvaluateTruncated(SI->getTrueValue(), Ty, IC, CxtI) &&
    413            canEvaluateTruncated(SI->getFalseValue(), Ty, IC, CxtI);
    414   }
    415   case Instruction::PHI: {
    416     // We can change a phi if we can change all operands.  Note that we never
    417     // get into trouble with cyclic PHIs here because we only consider
    418     // instructions with a single use.
    419     PHINode *PN = cast<PHINode>(I);
    420     for (Value *IncValue : PN->incoming_values())
    421       if (!canEvaluateTruncated(IncValue, Ty, IC, CxtI))
    422         return false;
    423     return true;
    424   }
    425   default:
    426     // TODO: Can handle more cases here.
    427     break;
    428   }
    429 
    430   return false;
    431 }
    432 
    433 /// Given a vector that is bitcast to an integer, optionally logically
    434 /// right-shifted, and truncated, convert it to an extractelement.
    435 /// Example (big endian):
    436 ///   trunc (lshr (bitcast <4 x i32> %X to i128), 32) to i32
    437 ///   --->
    438 ///   extractelement <4 x i32> %X, 1
    439 static Instruction *foldVecTruncToExtElt(TruncInst &Trunc, InstCombiner &IC,
    440                                          const DataLayout &DL) {
    441   Value *TruncOp = Trunc.getOperand(0);
    442   Type *DestType = Trunc.getType();
    443   if (!TruncOp->hasOneUse() || !isa<IntegerType>(DestType))
    444     return nullptr;
    445 
    446   Value *VecInput = nullptr;
    447   ConstantInt *ShiftVal = nullptr;
    448   if (!match(TruncOp, m_CombineOr(m_BitCast(m_Value(VecInput)),
    449                                   m_LShr(m_BitCast(m_Value(VecInput)),
    450                                          m_ConstantInt(ShiftVal)))) ||
    451       !isa<VectorType>(VecInput->getType()))
    452     return nullptr;
    453 
    454   VectorType *VecType = cast<VectorType>(VecInput->getType());
    455   unsigned VecWidth = VecType->getPrimitiveSizeInBits();
    456   unsigned DestWidth = DestType->getPrimitiveSizeInBits();
    457   unsigned ShiftAmount = ShiftVal ? ShiftVal->getZExtValue() : 0;
    458 
    459   if ((VecWidth % DestWidth != 0) || (ShiftAmount % DestWidth != 0))
    460     return nullptr;
    461 
    462   // If the element type of the vector doesn't match the result type,
    463   // bitcast it to a vector type that we can extract from.
    464   unsigned NumVecElts = VecWidth / DestWidth;
    465   if (VecType->getElementType() != DestType) {
    466     VecType = VectorType::get(DestType, NumVecElts);
    467     VecInput = IC.Builder->CreateBitCast(VecInput, VecType, "bc");
    468   }
    469 
    470   unsigned Elt = ShiftAmount / DestWidth;
    471   if (DL.isBigEndian())
    472     Elt = NumVecElts - 1 - Elt;
    473 
    474   return ExtractElementInst::Create(VecInput, IC.Builder->getInt32(Elt));
    475 }
    476 
    477 Instruction *InstCombiner::visitTrunc(TruncInst &CI) {
    478   if (Instruction *Result = commonCastTransforms(CI))
    479     return Result;
    480 
    481   // Test if the trunc is the user of a select which is part of a
    482   // minimum or maximum operation. If so, don't do any more simplification.
    483   // Even simplifying demanded bits can break the canonical form of a
    484   // min/max.
    485   Value *LHS, *RHS;
    486   if (SelectInst *SI = dyn_cast<SelectInst>(CI.getOperand(0)))
    487     if (matchSelectPattern(SI, LHS, RHS).Flavor != SPF_UNKNOWN)
    488       return nullptr;
    489 
    490   // See if we can simplify any instructions used by the input whose sole
    491   // purpose is to compute bits we don't care about.
    492   if (SimplifyDemandedInstructionBits(CI))
    493     return &CI;
    494 
    495   Value *Src = CI.getOperand(0);
    496   Type *DestTy = CI.getType(), *SrcTy = Src->getType();
    497 
    498   // Attempt to truncate the entire input expression tree to the destination
    499   // type.   Only do this if the dest type is a simple type, don't convert the
    500   // expression tree to something weird like i93 unless the source is also
    501   // strange.
    502   if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) &&
    503       canEvaluateTruncated(Src, DestTy, *this, &CI)) {
    504 
    505     // If this cast is a truncate, evaluting in a different type always
    506     // eliminates the cast, so it is always a win.
    507     DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
    508           " to avoid cast: " << CI << '\n');
    509     Value *Res = EvaluateInDifferentType(Src, DestTy, false);
    510     assert(Res->getType() == DestTy);
    511     return replaceInstUsesWith(CI, Res);
    512   }
    513 
    514   // Canonicalize trunc x to i1 -> (icmp ne (and x, 1), 0), likewise for vector.
    515   if (DestTy->getScalarSizeInBits() == 1) {
    516     Constant *One = ConstantInt::get(SrcTy, 1);
    517     Src = Builder->CreateAnd(Src, One);
    518     Value *Zero = Constant::getNullValue(Src->getType());
    519     return new ICmpInst(ICmpInst::ICMP_NE, Src, Zero);
    520   }
    521 
    522   // Transform trunc(lshr (zext A), Cst) to eliminate one type conversion.
    523   Value *A = nullptr; ConstantInt *Cst = nullptr;
    524   if (Src->hasOneUse() &&
    525       match(Src, m_LShr(m_ZExt(m_Value(A)), m_ConstantInt(Cst)))) {
    526     // We have three types to worry about here, the type of A, the source of
    527     // the truncate (MidSize), and the destination of the truncate. We know that
    528     // ASize < MidSize   and MidSize > ResultSize, but don't know the relation
    529     // between ASize and ResultSize.
    530     unsigned ASize = A->getType()->getPrimitiveSizeInBits();
    531 
    532     // If the shift amount is larger than the size of A, then the result is
    533     // known to be zero because all the input bits got shifted out.
    534     if (Cst->getZExtValue() >= ASize)
    535       return replaceInstUsesWith(CI, Constant::getNullValue(DestTy));
    536 
    537     // Since we're doing an lshr and a zero extend, and know that the shift
    538     // amount is smaller than ASize, it is always safe to do the shift in A's
    539     // type, then zero extend or truncate to the result.
    540     Value *Shift = Builder->CreateLShr(A, Cst->getZExtValue());
    541     Shift->takeName(Src);
    542     return CastInst::CreateIntegerCast(Shift, DestTy, false);
    543   }
    544 
    545   // Transform trunc(lshr (sext A), Cst) to ashr A, Cst to eliminate type
    546   // conversion.
    547   // It works because bits coming from sign extension have the same value as
    548   // the sign bit of the original value; performing ashr instead of lshr
    549   // generates bits of the same value as the sign bit.
    550   if (Src->hasOneUse() &&
    551       match(Src, m_LShr(m_SExt(m_Value(A)), m_ConstantInt(Cst))) &&
    552       cast<Instruction>(Src)->getOperand(0)->hasOneUse()) {
    553     const unsigned ASize = A->getType()->getPrimitiveSizeInBits();
    554     // This optimization can be only performed when zero bits generated by
    555     // the original lshr aren't pulled into the value after truncation, so we
    556     // can only shift by values smaller than the size of destination type (in
    557     // bits).
    558     if (Cst->getValue().ult(ASize)) {
    559       Value *Shift = Builder->CreateAShr(A, Cst->getZExtValue());
    560       Shift->takeName(Src);
    561       return CastInst::CreateIntegerCast(Shift, CI.getType(), true);
    562     }
    563   }
    564 
    565   // Transform "trunc (and X, cst)" -> "and (trunc X), cst" so long as the dest
    566   // type isn't non-native.
    567   if (Src->hasOneUse() && isa<IntegerType>(SrcTy) &&
    568       ShouldChangeType(SrcTy, DestTy) &&
    569       match(Src, m_And(m_Value(A), m_ConstantInt(Cst)))) {
    570     Value *NewTrunc = Builder->CreateTrunc(A, DestTy, A->getName() + ".tr");
    571     return BinaryOperator::CreateAnd(NewTrunc,
    572                                      ConstantExpr::getTrunc(Cst, DestTy));
    573   }
    574 
    575   if (Instruction *I = foldVecTruncToExtElt(CI, *this, DL))
    576     return I;
    577 
    578   return nullptr;
    579 }
    580 
    581 /// Transform (zext icmp) to bitwise / integer operations in order to eliminate
    582 /// the icmp.
    583 Instruction *InstCombiner::transformZExtICmp(ICmpInst *ICI, Instruction &CI,
    584                                              bool DoXform) {
    585   // If we are just checking for a icmp eq of a single bit and zext'ing it
    586   // to an integer, then shift the bit to the appropriate place and then
    587   // cast to integer to avoid the comparison.
    588   if (ConstantInt *Op1C = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
    589     const APInt &Op1CV = Op1C->getValue();
    590 
    591     // zext (x <s  0) to i32 --> x>>u31      true if signbit set.
    592     // zext (x >s -1) to i32 --> (x>>u31)^1  true if signbit clear.
    593     if ((ICI->getPredicate() == ICmpInst::ICMP_SLT && Op1CV == 0) ||
    594         (ICI->getPredicate() == ICmpInst::ICMP_SGT && Op1CV.isAllOnesValue())) {
    595       if (!DoXform) return ICI;
    596 
    597       Value *In = ICI->getOperand(0);
    598       Value *Sh = ConstantInt::get(In->getType(),
    599                                    In->getType()->getScalarSizeInBits() - 1);
    600       In = Builder->CreateLShr(In, Sh, In->getName() + ".lobit");
    601       if (In->getType() != CI.getType())
    602         In = Builder->CreateIntCast(In, CI.getType(), false/*ZExt*/);
    603 
    604       if (ICI->getPredicate() == ICmpInst::ICMP_SGT) {
    605         Constant *One = ConstantInt::get(In->getType(), 1);
    606         In = Builder->CreateXor(In, One, In->getName() + ".not");
    607       }
    608 
    609       return replaceInstUsesWith(CI, In);
    610     }
    611 
    612     // zext (X == 0) to i32 --> X^1      iff X has only the low bit set.
    613     // zext (X == 0) to i32 --> (X>>1)^1 iff X has only the 2nd bit set.
    614     // zext (X == 1) to i32 --> X        iff X has only the low bit set.
    615     // zext (X == 2) to i32 --> X>>1     iff X has only the 2nd bit set.
    616     // zext (X != 0) to i32 --> X        iff X has only the low bit set.
    617     // zext (X != 0) to i32 --> X>>1     iff X has only the 2nd bit set.
    618     // zext (X != 1) to i32 --> X^1      iff X has only the low bit set.
    619     // zext (X != 2) to i32 --> (X>>1)^1 iff X has only the 2nd bit set.
    620     if ((Op1CV == 0 || Op1CV.isPowerOf2()) &&
    621         // This only works for EQ and NE
    622         ICI->isEquality()) {
    623       // If Op1C some other power of two, convert:
    624       uint32_t BitWidth = Op1C->getType()->getBitWidth();
    625       APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
    626       computeKnownBits(ICI->getOperand(0), KnownZero, KnownOne, 0, &CI);
    627 
    628       APInt KnownZeroMask(~KnownZero);
    629       if (KnownZeroMask.isPowerOf2()) { // Exactly 1 possible 1?
    630         if (!DoXform) return ICI;
    631 
    632         bool isNE = ICI->getPredicate() == ICmpInst::ICMP_NE;
    633         if (Op1CV != 0 && (Op1CV != KnownZeroMask)) {
    634           // (X&4) == 2 --> false
    635           // (X&4) != 2 --> true
    636           Constant *Res = ConstantInt::get(Type::getInt1Ty(CI.getContext()),
    637                                            isNE);
    638           Res = ConstantExpr::getZExt(Res, CI.getType());
    639           return replaceInstUsesWith(CI, Res);
    640         }
    641 
    642         uint32_t ShAmt = KnownZeroMask.logBase2();
    643         Value *In = ICI->getOperand(0);
    644         if (ShAmt) {
    645           // Perform a logical shr by shiftamt.
    646           // Insert the shift to put the result in the low bit.
    647           In = Builder->CreateLShr(In, ConstantInt::get(In->getType(), ShAmt),
    648                                    In->getName() + ".lobit");
    649         }
    650 
    651         if ((Op1CV != 0) == isNE) { // Toggle the low bit.
    652           Constant *One = ConstantInt::get(In->getType(), 1);
    653           In = Builder->CreateXor(In, One);
    654         }
    655 
    656         if (CI.getType() == In->getType())
    657           return replaceInstUsesWith(CI, In);
    658         return CastInst::CreateIntegerCast(In, CI.getType(), false/*ZExt*/);
    659       }
    660     }
    661   }
    662 
    663   // icmp ne A, B is equal to xor A, B when A and B only really have one bit.
    664   // It is also profitable to transform icmp eq into not(xor(A, B)) because that
    665   // may lead to additional simplifications.
    666   if (ICI->isEquality() && CI.getType() == ICI->getOperand(0)->getType()) {
    667     if (IntegerType *ITy = dyn_cast<IntegerType>(CI.getType())) {
    668       uint32_t BitWidth = ITy->getBitWidth();
    669       Value *LHS = ICI->getOperand(0);
    670       Value *RHS = ICI->getOperand(1);
    671 
    672       APInt KnownZeroLHS(BitWidth, 0), KnownOneLHS(BitWidth, 0);
    673       APInt KnownZeroRHS(BitWidth, 0), KnownOneRHS(BitWidth, 0);
    674       computeKnownBits(LHS, KnownZeroLHS, KnownOneLHS, 0, &CI);
    675       computeKnownBits(RHS, KnownZeroRHS, KnownOneRHS, 0, &CI);
    676 
    677       if (KnownZeroLHS == KnownZeroRHS && KnownOneLHS == KnownOneRHS) {
    678         APInt KnownBits = KnownZeroLHS | KnownOneLHS;
    679         APInt UnknownBit = ~KnownBits;
    680         if (UnknownBit.countPopulation() == 1) {
    681           if (!DoXform) return ICI;
    682 
    683           Value *Result = Builder->CreateXor(LHS, RHS);
    684 
    685           // Mask off any bits that are set and won't be shifted away.
    686           if (KnownOneLHS.uge(UnknownBit))
    687             Result = Builder->CreateAnd(Result,
    688                                         ConstantInt::get(ITy, UnknownBit));
    689 
    690           // Shift the bit we're testing down to the lsb.
    691           Result = Builder->CreateLShr(
    692                Result, ConstantInt::get(ITy, UnknownBit.countTrailingZeros()));
    693 
    694           if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
    695             Result = Builder->CreateXor(Result, ConstantInt::get(ITy, 1));
    696           Result->takeName(ICI);
    697           return replaceInstUsesWith(CI, Result);
    698         }
    699       }
    700     }
    701   }
    702 
    703   return nullptr;
    704 }
    705 
    706 /// Determine if the specified value can be computed in the specified wider type
    707 /// and produce the same low bits. If not, return false.
    708 ///
    709 /// If this function returns true, it can also return a non-zero number of bits
    710 /// (in BitsToClear) which indicates that the value it computes is correct for
    711 /// the zero extend, but that the additional BitsToClear bits need to be zero'd
    712 /// out.  For example, to promote something like:
    713 ///
    714 ///   %B = trunc i64 %A to i32
    715 ///   %C = lshr i32 %B, 8
    716 ///   %E = zext i32 %C to i64
    717 ///
    718 /// CanEvaluateZExtd for the 'lshr' will return true, and BitsToClear will be
    719 /// set to 8 to indicate that the promoted value needs to have bits 24-31
    720 /// cleared in addition to bits 32-63.  Since an 'and' will be generated to
    721 /// clear the top bits anyway, doing this has no extra cost.
    722 ///
    723 /// This function works on both vectors and scalars.
    724 static bool canEvaluateZExtd(Value *V, Type *Ty, unsigned &BitsToClear,
    725                              InstCombiner &IC, Instruction *CxtI) {
    726   BitsToClear = 0;
    727   if (isa<Constant>(V))
    728     return true;
    729 
    730   Instruction *I = dyn_cast<Instruction>(V);
    731   if (!I) return false;
    732 
    733   // If the input is a truncate from the destination type, we can trivially
    734   // eliminate it.
    735   if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty)
    736     return true;
    737 
    738   // We can't extend or shrink something that has multiple uses: doing so would
    739   // require duplicating the instruction in general, which isn't profitable.
    740   if (!I->hasOneUse()) return false;
    741 
    742   unsigned Opc = I->getOpcode(), Tmp;
    743   switch (Opc) {
    744   case Instruction::ZExt:  // zext(zext(x)) -> zext(x).
    745   case Instruction::SExt:  // zext(sext(x)) -> sext(x).
    746   case Instruction::Trunc: // zext(trunc(x)) -> trunc(x) or zext(x)
    747     return true;
    748   case Instruction::And:
    749   case Instruction::Or:
    750   case Instruction::Xor:
    751   case Instruction::Add:
    752   case Instruction::Sub:
    753   case Instruction::Mul:
    754     if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI) ||
    755         !canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI))
    756       return false;
    757     // These can all be promoted if neither operand has 'bits to clear'.
    758     if (BitsToClear == 0 && Tmp == 0)
    759       return true;
    760 
    761     // If the operation is an AND/OR/XOR and the bits to clear are zero in the
    762     // other side, BitsToClear is ok.
    763     if (Tmp == 0 &&
    764         (Opc == Instruction::And || Opc == Instruction::Or ||
    765          Opc == Instruction::Xor)) {
    766       // We use MaskedValueIsZero here for generality, but the case we care
    767       // about the most is constant RHS.
    768       unsigned VSize = V->getType()->getScalarSizeInBits();
    769       if (IC.MaskedValueIsZero(I->getOperand(1),
    770                                APInt::getHighBitsSet(VSize, BitsToClear),
    771                                0, CxtI))
    772         return true;
    773     }
    774 
    775     // Otherwise, we don't know how to analyze this BitsToClear case yet.
    776     return false;
    777 
    778   case Instruction::Shl:
    779     // We can promote shl(x, cst) if we can promote x.  Since shl overwrites the
    780     // upper bits we can reduce BitsToClear by the shift amount.
    781     if (ConstantInt *Amt = dyn_cast<ConstantInt>(I->getOperand(1))) {
    782       if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI))
    783         return false;
    784       uint64_t ShiftAmt = Amt->getZExtValue();
    785       BitsToClear = ShiftAmt < BitsToClear ? BitsToClear - ShiftAmt : 0;
    786       return true;
    787     }
    788     return false;
    789   case Instruction::LShr:
    790     // We can promote lshr(x, cst) if we can promote x.  This requires the
    791     // ultimate 'and' to clear out the high zero bits we're clearing out though.
    792     if (ConstantInt *Amt = dyn_cast<ConstantInt>(I->getOperand(1))) {
    793       if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI))
    794         return false;
    795       BitsToClear += Amt->getZExtValue();
    796       if (BitsToClear > V->getType()->getScalarSizeInBits())
    797         BitsToClear = V->getType()->getScalarSizeInBits();
    798       return true;
    799     }
    800     // Cannot promote variable LSHR.
    801     return false;
    802   case Instruction::Select:
    803     if (!canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI) ||
    804         !canEvaluateZExtd(I->getOperand(2), Ty, BitsToClear, IC, CxtI) ||
    805         // TODO: If important, we could handle the case when the BitsToClear are
    806         // known zero in the disagreeing side.
    807         Tmp != BitsToClear)
    808       return false;
    809     return true;
    810 
    811   case Instruction::PHI: {
    812     // We can change a phi if we can change all operands.  Note that we never
    813     // get into trouble with cyclic PHIs here because we only consider
    814     // instructions with a single use.
    815     PHINode *PN = cast<PHINode>(I);
    816     if (!canEvaluateZExtd(PN->getIncomingValue(0), Ty, BitsToClear, IC, CxtI))
    817       return false;
    818     for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
    819       if (!canEvaluateZExtd(PN->getIncomingValue(i), Ty, Tmp, IC, CxtI) ||
    820           // TODO: If important, we could handle the case when the BitsToClear
    821           // are known zero in the disagreeing input.
    822           Tmp != BitsToClear)
    823         return false;
    824     return true;
    825   }
    826   default:
    827     // TODO: Can handle more cases here.
    828     return false;
    829   }
    830 }
    831 
    832 Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
    833   // If this zero extend is only used by a truncate, let the truncate be
    834   // eliminated before we try to optimize this zext.
    835   if (CI.hasOneUse() && isa<TruncInst>(CI.user_back()))
    836     return nullptr;
    837 
    838   // If one of the common conversion will work, do it.
    839   if (Instruction *Result = commonCastTransforms(CI))
    840     return Result;
    841 
    842   // See if we can simplify any instructions used by the input whose sole
    843   // purpose is to compute bits we don't care about.
    844   if (SimplifyDemandedInstructionBits(CI))
    845     return &CI;
    846 
    847   Value *Src = CI.getOperand(0);
    848   Type *SrcTy = Src->getType(), *DestTy = CI.getType();
    849 
    850   // Attempt to extend the entire input expression tree to the destination
    851   // type.   Only do this if the dest type is a simple type, don't convert the
    852   // expression tree to something weird like i93 unless the source is also
    853   // strange.
    854   unsigned BitsToClear;
    855   if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) &&
    856       canEvaluateZExtd(Src, DestTy, BitsToClear, *this, &CI)) {
    857     assert(BitsToClear < SrcTy->getScalarSizeInBits() &&
    858            "Unreasonable BitsToClear");
    859 
    860     // Okay, we can transform this!  Insert the new expression now.
    861     DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
    862           " to avoid zero extend: " << CI << '\n');
    863     Value *Res = EvaluateInDifferentType(Src, DestTy, false);
    864     assert(Res->getType() == DestTy);
    865 
    866     uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits()-BitsToClear;
    867     uint32_t DestBitSize = DestTy->getScalarSizeInBits();
    868 
    869     // If the high bits are already filled with zeros, just replace this
    870     // cast with the result.
    871     if (MaskedValueIsZero(Res,
    872                           APInt::getHighBitsSet(DestBitSize,
    873                                                 DestBitSize-SrcBitsKept),
    874                              0, &CI))
    875       return replaceInstUsesWith(CI, Res);
    876 
    877     // We need to emit an AND to clear the high bits.
    878     Constant *C = ConstantInt::get(Res->getType(),
    879                                APInt::getLowBitsSet(DestBitSize, SrcBitsKept));
    880     return BinaryOperator::CreateAnd(Res, C);
    881   }
    882 
    883   // If this is a TRUNC followed by a ZEXT then we are dealing with integral
    884   // types and if the sizes are just right we can convert this into a logical
    885   // 'and' which will be much cheaper than the pair of casts.
    886   if (TruncInst *CSrc = dyn_cast<TruncInst>(Src)) {   // A->B->C cast
    887     // TODO: Subsume this into EvaluateInDifferentType.
    888 
    889     // Get the sizes of the types involved.  We know that the intermediate type
    890     // will be smaller than A or C, but don't know the relation between A and C.
    891     Value *A = CSrc->getOperand(0);
    892     unsigned SrcSize = A->getType()->getScalarSizeInBits();
    893     unsigned MidSize = CSrc->getType()->getScalarSizeInBits();
    894     unsigned DstSize = CI.getType()->getScalarSizeInBits();
    895     // If we're actually extending zero bits, then if
    896     // SrcSize <  DstSize: zext(a & mask)
    897     // SrcSize == DstSize: a & mask
    898     // SrcSize  > DstSize: trunc(a) & mask
    899     if (SrcSize < DstSize) {
    900       APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize));
    901       Constant *AndConst = ConstantInt::get(A->getType(), AndValue);
    902       Value *And = Builder->CreateAnd(A, AndConst, CSrc->getName()+".mask");
    903       return new ZExtInst(And, CI.getType());
    904     }
    905 
    906     if (SrcSize == DstSize) {
    907       APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize));
    908       return BinaryOperator::CreateAnd(A, ConstantInt::get(A->getType(),
    909                                                            AndValue));
    910     }
    911     if (SrcSize > DstSize) {
    912       Value *Trunc = Builder->CreateTrunc(A, CI.getType());
    913       APInt AndValue(APInt::getLowBitsSet(DstSize, MidSize));
    914       return BinaryOperator::CreateAnd(Trunc,
    915                                        ConstantInt::get(Trunc->getType(),
    916                                                         AndValue));
    917     }
    918   }
    919 
    920   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src))
    921     return transformZExtICmp(ICI, CI);
    922 
    923   BinaryOperator *SrcI = dyn_cast<BinaryOperator>(Src);
    924   if (SrcI && SrcI->getOpcode() == Instruction::Or) {
    925     // zext (or icmp, icmp) --> or (zext icmp), (zext icmp) if at least one
    926     // of the (zext icmp) will be transformed.
    927     ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0));
    928     ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1));
    929     if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() &&
    930         (transformZExtICmp(LHS, CI, false) ||
    931          transformZExtICmp(RHS, CI, false))) {
    932       Value *LCast = Builder->CreateZExt(LHS, CI.getType(), LHS->getName());
    933       Value *RCast = Builder->CreateZExt(RHS, CI.getType(), RHS->getName());
    934       return BinaryOperator::Create(Instruction::Or, LCast, RCast);
    935     }
    936   }
    937 
    938   // zext(trunc(X) & C) -> (X & zext(C)).
    939   Constant *C;
    940   Value *X;
    941   if (SrcI &&
    942       match(SrcI, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Constant(C)))) &&
    943       X->getType() == CI.getType())
    944     return BinaryOperator::CreateAnd(X, ConstantExpr::getZExt(C, CI.getType()));
    945 
    946   // zext((trunc(X) & C) ^ C) -> ((X & zext(C)) ^ zext(C)).
    947   Value *And;
    948   if (SrcI && match(SrcI, m_OneUse(m_Xor(m_Value(And), m_Constant(C)))) &&
    949       match(And, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Specific(C)))) &&
    950       X->getType() == CI.getType()) {
    951     Constant *ZC = ConstantExpr::getZExt(C, CI.getType());
    952     return BinaryOperator::CreateXor(Builder->CreateAnd(X, ZC), ZC);
    953   }
    954 
    955   // zext (xor i1 X, true) to i32  --> xor (zext i1 X to i32), 1
    956   if (SrcI && SrcI->hasOneUse() &&
    957       SrcI->getType()->getScalarType()->isIntegerTy(1) &&
    958       match(SrcI, m_Not(m_Value(X))) && (!X->hasOneUse() || !isa<CmpInst>(X))) {
    959     Value *New = Builder->CreateZExt(X, CI.getType());
    960     return BinaryOperator::CreateXor(New, ConstantInt::get(CI.getType(), 1));
    961   }
    962 
    963   return nullptr;
    964 }
    965 
    966 /// Transform (sext icmp) to bitwise / integer operations to eliminate the icmp.
    967 Instruction *InstCombiner::transformSExtICmp(ICmpInst *ICI, Instruction &CI) {
    968   Value *Op0 = ICI->getOperand(0), *Op1 = ICI->getOperand(1);
    969   ICmpInst::Predicate Pred = ICI->getPredicate();
    970 
    971   // Don't bother if Op1 isn't of vector or integer type.
    972   if (!Op1->getType()->isIntOrIntVectorTy())
    973     return nullptr;
    974 
    975   if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
    976     // (x <s  0) ? -1 : 0 -> ashr x, 31        -> all ones if negative
    977     // (x >s -1) ? -1 : 0 -> not (ashr x, 31)  -> all ones if positive
    978     if ((Pred == ICmpInst::ICMP_SLT && Op1C->isNullValue()) ||
    979         (Pred == ICmpInst::ICMP_SGT && Op1C->isAllOnesValue())) {
    980 
    981       Value *Sh = ConstantInt::get(Op0->getType(),
    982                                    Op0->getType()->getScalarSizeInBits()-1);
    983       Value *In = Builder->CreateAShr(Op0, Sh, Op0->getName()+".lobit");
    984       if (In->getType() != CI.getType())
    985         In = Builder->CreateIntCast(In, CI.getType(), true/*SExt*/);
    986 
    987       if (Pred == ICmpInst::ICMP_SGT)
    988         In = Builder->CreateNot(In, In->getName()+".not");
    989       return replaceInstUsesWith(CI, In);
    990     }
    991   }
    992 
    993   if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
    994     // If we know that only one bit of the LHS of the icmp can be set and we
    995     // have an equality comparison with zero or a power of 2, we can transform
    996     // the icmp and sext into bitwise/integer operations.
    997     if (ICI->hasOneUse() &&
    998         ICI->isEquality() && (Op1C->isZero() || Op1C->getValue().isPowerOf2())){
    999       unsigned BitWidth = Op1C->getType()->getBitWidth();
   1000       APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
   1001       computeKnownBits(Op0, KnownZero, KnownOne, 0, &CI);
   1002 
   1003       APInt KnownZeroMask(~KnownZero);
   1004       if (KnownZeroMask.isPowerOf2()) {
   1005         Value *In = ICI->getOperand(0);
   1006 
   1007         // If the icmp tests for a known zero bit we can constant fold it.
   1008         if (!Op1C->isZero() && Op1C->getValue() != KnownZeroMask) {
   1009           Value *V = Pred == ICmpInst::ICMP_NE ?
   1010                        ConstantInt::getAllOnesValue(CI.getType()) :
   1011                        ConstantInt::getNullValue(CI.getType());
   1012           return replaceInstUsesWith(CI, V);
   1013         }
   1014 
   1015         if (!Op1C->isZero() == (Pred == ICmpInst::ICMP_NE)) {
   1016           // sext ((x & 2^n) == 0)   -> (x >> n) - 1
   1017           // sext ((x & 2^n) != 2^n) -> (x >> n) - 1
   1018           unsigned ShiftAmt = KnownZeroMask.countTrailingZeros();
   1019           // Perform a right shift to place the desired bit in the LSB.
   1020           if (ShiftAmt)
   1021             In = Builder->CreateLShr(In,
   1022                                      ConstantInt::get(In->getType(), ShiftAmt));
   1023 
   1024           // At this point "In" is either 1 or 0. Subtract 1 to turn
   1025           // {1, 0} -> {0, -1}.
   1026           In = Builder->CreateAdd(In,
   1027                                   ConstantInt::getAllOnesValue(In->getType()),
   1028                                   "sext");
   1029         } else {
   1030           // sext ((x & 2^n) != 0)   -> (x << bitwidth-n) a>> bitwidth-1
   1031           // sext ((x & 2^n) == 2^n) -> (x << bitwidth-n) a>> bitwidth-1
   1032           unsigned ShiftAmt = KnownZeroMask.countLeadingZeros();
   1033           // Perform a left shift to place the desired bit in the MSB.
   1034           if (ShiftAmt)
   1035             In = Builder->CreateShl(In,
   1036                                     ConstantInt::get(In->getType(), ShiftAmt));
   1037 
   1038           // Distribute the bit over the whole bit width.
   1039           In = Builder->CreateAShr(In, ConstantInt::get(In->getType(),
   1040                                                         BitWidth - 1), "sext");
   1041         }
   1042 
   1043         if (CI.getType() == In->getType())
   1044           return replaceInstUsesWith(CI, In);
   1045         return CastInst::CreateIntegerCast(In, CI.getType(), true/*SExt*/);
   1046       }
   1047     }
   1048   }
   1049 
   1050   return nullptr;
   1051 }
   1052 
   1053 /// Return true if we can take the specified value and return it as type Ty
   1054 /// without inserting any new casts and without changing the value of the common
   1055 /// low bits.  This is used by code that tries to promote integer operations to
   1056 /// a wider types will allow us to eliminate the extension.
   1057 ///
   1058 /// This function works on both vectors and scalars.
   1059 ///
   1060 static bool canEvaluateSExtd(Value *V, Type *Ty) {
   1061   assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() &&
   1062          "Can't sign extend type to a smaller type");
   1063   // If this is a constant, it can be trivially promoted.
   1064   if (isa<Constant>(V))
   1065     return true;
   1066 
   1067   Instruction *I = dyn_cast<Instruction>(V);
   1068   if (!I) return false;
   1069 
   1070   // If this is a truncate from the dest type, we can trivially eliminate it.
   1071   if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty)
   1072     return true;
   1073 
   1074   // We can't extend or shrink something that has multiple uses: doing so would
   1075   // require duplicating the instruction in general, which isn't profitable.
   1076   if (!I->hasOneUse()) return false;
   1077 
   1078   switch (I->getOpcode()) {
   1079   case Instruction::SExt:  // sext(sext(x)) -> sext(x)
   1080   case Instruction::ZExt:  // sext(zext(x)) -> zext(x)
   1081   case Instruction::Trunc: // sext(trunc(x)) -> trunc(x) or sext(x)
   1082     return true;
   1083   case Instruction::And:
   1084   case Instruction::Or:
   1085   case Instruction::Xor:
   1086   case Instruction::Add:
   1087   case Instruction::Sub:
   1088   case Instruction::Mul:
   1089     // These operators can all arbitrarily be extended if their inputs can.
   1090     return canEvaluateSExtd(I->getOperand(0), Ty) &&
   1091            canEvaluateSExtd(I->getOperand(1), Ty);
   1092 
   1093   //case Instruction::Shl:   TODO
   1094   //case Instruction::LShr:  TODO
   1095 
   1096   case Instruction::Select:
   1097     return canEvaluateSExtd(I->getOperand(1), Ty) &&
   1098            canEvaluateSExtd(I->getOperand(2), Ty);
   1099 
   1100   case Instruction::PHI: {
   1101     // We can change a phi if we can change all operands.  Note that we never
   1102     // get into trouble with cyclic PHIs here because we only consider
   1103     // instructions with a single use.
   1104     PHINode *PN = cast<PHINode>(I);
   1105     for (Value *IncValue : PN->incoming_values())
   1106       if (!canEvaluateSExtd(IncValue, Ty)) return false;
   1107     return true;
   1108   }
   1109   default:
   1110     // TODO: Can handle more cases here.
   1111     break;
   1112   }
   1113 
   1114   return false;
   1115 }
   1116 
   1117 Instruction *InstCombiner::visitSExt(SExtInst &CI) {
   1118   // If this sign extend is only used by a truncate, let the truncate be
   1119   // eliminated before we try to optimize this sext.
   1120   if (CI.hasOneUse() && isa<TruncInst>(CI.user_back()))
   1121     return nullptr;
   1122 
   1123   if (Instruction *I = commonCastTransforms(CI))
   1124     return I;
   1125 
   1126   // See if we can simplify any instructions used by the input whose sole
   1127   // purpose is to compute bits we don't care about.
   1128   if (SimplifyDemandedInstructionBits(CI))
   1129     return &CI;
   1130 
   1131   Value *Src = CI.getOperand(0);
   1132   Type *SrcTy = Src->getType(), *DestTy = CI.getType();
   1133 
   1134   // If we know that the value being extended is positive, we can use a zext
   1135   // instead.
   1136   bool KnownZero, KnownOne;
   1137   ComputeSignBit(Src, KnownZero, KnownOne, 0, &CI);
   1138   if (KnownZero) {
   1139     Value *ZExt = Builder->CreateZExt(Src, DestTy);
   1140     return replaceInstUsesWith(CI, ZExt);
   1141   }
   1142 
   1143   // Attempt to extend the entire input expression tree to the destination
   1144   // type.   Only do this if the dest type is a simple type, don't convert the
   1145   // expression tree to something weird like i93 unless the source is also
   1146   // strange.
   1147   if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) &&
   1148       canEvaluateSExtd(Src, DestTy)) {
   1149     // Okay, we can transform this!  Insert the new expression now.
   1150     DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
   1151           " to avoid sign extend: " << CI << '\n');
   1152     Value *Res = EvaluateInDifferentType(Src, DestTy, true);
   1153     assert(Res->getType() == DestTy);
   1154 
   1155     uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
   1156     uint32_t DestBitSize = DestTy->getScalarSizeInBits();
   1157 
   1158     // If the high bits are already filled with sign bit, just replace this
   1159     // cast with the result.
   1160     if (ComputeNumSignBits(Res, 0, &CI) > DestBitSize - SrcBitSize)
   1161       return replaceInstUsesWith(CI, Res);
   1162 
   1163     // We need to emit a shl + ashr to do the sign extend.
   1164     Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize);
   1165     return BinaryOperator::CreateAShr(Builder->CreateShl(Res, ShAmt, "sext"),
   1166                                       ShAmt);
   1167   }
   1168 
   1169   // If this input is a trunc from our destination, then turn sext(trunc(x))
   1170   // into shifts.
   1171   if (TruncInst *TI = dyn_cast<TruncInst>(Src))
   1172     if (TI->hasOneUse() && TI->getOperand(0)->getType() == DestTy) {
   1173       uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
   1174       uint32_t DestBitSize = DestTy->getScalarSizeInBits();
   1175 
   1176       // We need to emit a shl + ashr to do the sign extend.
   1177       Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize);
   1178       Value *Res = Builder->CreateShl(TI->getOperand(0), ShAmt, "sext");
   1179       return BinaryOperator::CreateAShr(Res, ShAmt);
   1180     }
   1181 
   1182   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src))
   1183     return transformSExtICmp(ICI, CI);
   1184 
   1185   // If the input is a shl/ashr pair of a same constant, then this is a sign
   1186   // extension from a smaller value.  If we could trust arbitrary bitwidth
   1187   // integers, we could turn this into a truncate to the smaller bit and then
   1188   // use a sext for the whole extension.  Since we don't, look deeper and check
   1189   // for a truncate.  If the source and dest are the same type, eliminate the
   1190   // trunc and extend and just do shifts.  For example, turn:
   1191   //   %a = trunc i32 %i to i8
   1192   //   %b = shl i8 %a, 6
   1193   //   %c = ashr i8 %b, 6
   1194   //   %d = sext i8 %c to i32
   1195   // into:
   1196   //   %a = shl i32 %i, 30
   1197   //   %d = ashr i32 %a, 30
   1198   Value *A = nullptr;
   1199   // TODO: Eventually this could be subsumed by EvaluateInDifferentType.
   1200   ConstantInt *BA = nullptr, *CA = nullptr;
   1201   if (match(Src, m_AShr(m_Shl(m_Trunc(m_Value(A)), m_ConstantInt(BA)),
   1202                         m_ConstantInt(CA))) &&
   1203       BA == CA && A->getType() == CI.getType()) {
   1204     unsigned MidSize = Src->getType()->getScalarSizeInBits();
   1205     unsigned SrcDstSize = CI.getType()->getScalarSizeInBits();
   1206     unsigned ShAmt = CA->getZExtValue()+SrcDstSize-MidSize;
   1207     Constant *ShAmtV = ConstantInt::get(CI.getType(), ShAmt);
   1208     A = Builder->CreateShl(A, ShAmtV, CI.getName());
   1209     return BinaryOperator::CreateAShr(A, ShAmtV);
   1210   }
   1211 
   1212   return nullptr;
   1213 }
   1214 
   1215 
   1216 /// Return a Constant* for the specified floating-point constant if it fits
   1217 /// in the specified FP type without changing its value.
   1218 static Constant *fitsInFPType(ConstantFP *CFP, const fltSemantics &Sem) {
   1219   bool losesInfo;
   1220   APFloat F = CFP->getValueAPF();
   1221   (void)F.convert(Sem, APFloat::rmNearestTiesToEven, &losesInfo);
   1222   if (!losesInfo)
   1223     return ConstantFP::get(CFP->getContext(), F);
   1224   return nullptr;
   1225 }
   1226 
   1227 /// If this is a floating-point extension instruction, look
   1228 /// through it until we get the source value.
   1229 static Value *lookThroughFPExtensions(Value *V) {
   1230   if (Instruction *I = dyn_cast<Instruction>(V))
   1231     if (I->getOpcode() == Instruction::FPExt)
   1232       return lookThroughFPExtensions(I->getOperand(0));
   1233 
   1234   // If this value is a constant, return the constant in the smallest FP type
   1235   // that can accurately represent it.  This allows us to turn
   1236   // (float)((double)X+2.0) into x+2.0f.
   1237   if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
   1238     if (CFP->getType() == Type::getPPC_FP128Ty(V->getContext()))
   1239       return V;  // No constant folding of this.
   1240     // See if the value can be truncated to half and then reextended.
   1241     if (Value *V = fitsInFPType(CFP, APFloat::IEEEhalf))
   1242       return V;
   1243     // See if the value can be truncated to float and then reextended.
   1244     if (Value *V = fitsInFPType(CFP, APFloat::IEEEsingle))
   1245       return V;
   1246     if (CFP->getType()->isDoubleTy())
   1247       return V;  // Won't shrink.
   1248     if (Value *V = fitsInFPType(CFP, APFloat::IEEEdouble))
   1249       return V;
   1250     // Don't try to shrink to various long double types.
   1251   }
   1252 
   1253   return V;
   1254 }
   1255 
   1256 Instruction *InstCombiner::visitFPTrunc(FPTruncInst &CI) {
   1257   if (Instruction *I = commonCastTransforms(CI))
   1258     return I;
   1259   // If we have fptrunc(OpI (fpextend x), (fpextend y)), we would like to
   1260   // simplify this expression to avoid one or more of the trunc/extend
   1261   // operations if we can do so without changing the numerical results.
   1262   //
   1263   // The exact manner in which the widths of the operands interact to limit
   1264   // what we can and cannot do safely varies from operation to operation, and
   1265   // is explained below in the various case statements.
   1266   BinaryOperator *OpI = dyn_cast<BinaryOperator>(CI.getOperand(0));
   1267   if (OpI && OpI->hasOneUse()) {
   1268     Value *LHSOrig = lookThroughFPExtensions(OpI->getOperand(0));
   1269     Value *RHSOrig = lookThroughFPExtensions(OpI->getOperand(1));
   1270     unsigned OpWidth = OpI->getType()->getFPMantissaWidth();
   1271     unsigned LHSWidth = LHSOrig->getType()->getFPMantissaWidth();
   1272     unsigned RHSWidth = RHSOrig->getType()->getFPMantissaWidth();
   1273     unsigned SrcWidth = std::max(LHSWidth, RHSWidth);
   1274     unsigned DstWidth = CI.getType()->getFPMantissaWidth();
   1275     switch (OpI->getOpcode()) {
   1276       default: break;
   1277       case Instruction::FAdd:
   1278       case Instruction::FSub:
   1279         // For addition and subtraction, the infinitely precise result can
   1280         // essentially be arbitrarily wide; proving that double rounding
   1281         // will not occur because the result of OpI is exact (as we will for
   1282         // FMul, for example) is hopeless.  However, we *can* nonetheless
   1283         // frequently know that double rounding cannot occur (or that it is
   1284         // innocuous) by taking advantage of the specific structure of
   1285         // infinitely-precise results that admit double rounding.
   1286         //
   1287         // Specifically, if OpWidth >= 2*DstWdith+1 and DstWidth is sufficient
   1288         // to represent both sources, we can guarantee that the double
   1289         // rounding is innocuous (See p50 of Figueroa's 2000 PhD thesis,
   1290         // "A Rigorous Framework for Fully Supporting the IEEE Standard ..."
   1291         // for proof of this fact).
   1292         //
   1293         // Note: Figueroa does not consider the case where DstFormat !=
   1294         // SrcFormat.  It's possible (likely even!) that this analysis
   1295         // could be tightened for those cases, but they are rare (the main
   1296         // case of interest here is (float)((double)float + float)).
   1297         if (OpWidth >= 2*DstWidth+1 && DstWidth >= SrcWidth) {
   1298           if (LHSOrig->getType() != CI.getType())
   1299             LHSOrig = Builder->CreateFPExt(LHSOrig, CI.getType());
   1300           if (RHSOrig->getType() != CI.getType())
   1301             RHSOrig = Builder->CreateFPExt(RHSOrig, CI.getType());
   1302           Instruction *RI =
   1303             BinaryOperator::Create(OpI->getOpcode(), LHSOrig, RHSOrig);
   1304           RI->copyFastMathFlags(OpI);
   1305           return RI;
   1306         }
   1307         break;
   1308       case Instruction::FMul:
   1309         // For multiplication, the infinitely precise result has at most
   1310         // LHSWidth + RHSWidth significant bits; if OpWidth is sufficient
   1311         // that such a value can be exactly represented, then no double
   1312         // rounding can possibly occur; we can safely perform the operation
   1313         // in the destination format if it can represent both sources.
   1314         if (OpWidth >= LHSWidth + RHSWidth && DstWidth >= SrcWidth) {
   1315           if (LHSOrig->getType() != CI.getType())
   1316             LHSOrig = Builder->CreateFPExt(LHSOrig, CI.getType());
   1317           if (RHSOrig->getType() != CI.getType())
   1318             RHSOrig = Builder->CreateFPExt(RHSOrig, CI.getType());
   1319           Instruction *RI =
   1320             BinaryOperator::CreateFMul(LHSOrig, RHSOrig);
   1321           RI->copyFastMathFlags(OpI);
   1322           return RI;
   1323         }
   1324         break;
   1325       case Instruction::FDiv:
   1326         // For division, we use again use the bound from Figueroa's
   1327         // dissertation.  I am entirely certain that this bound can be
   1328         // tightened in the unbalanced operand case by an analysis based on
   1329         // the diophantine rational approximation bound, but the well-known
   1330         // condition used here is a good conservative first pass.
   1331         // TODO: Tighten bound via rigorous analysis of the unbalanced case.
   1332         if (OpWidth >= 2*DstWidth && DstWidth >= SrcWidth) {
   1333           if (LHSOrig->getType() != CI.getType())
   1334             LHSOrig = Builder->CreateFPExt(LHSOrig, CI.getType());
   1335           if (RHSOrig->getType() != CI.getType())
   1336             RHSOrig = Builder->CreateFPExt(RHSOrig, CI.getType());
   1337           Instruction *RI =
   1338             BinaryOperator::CreateFDiv(LHSOrig, RHSOrig);
   1339           RI->copyFastMathFlags(OpI);
   1340           return RI;
   1341         }
   1342         break;
   1343       case Instruction::FRem:
   1344         // Remainder is straightforward.  Remainder is always exact, so the
   1345         // type of OpI doesn't enter into things at all.  We simply evaluate
   1346         // in whichever source type is larger, then convert to the
   1347         // destination type.
   1348         if (SrcWidth == OpWidth)
   1349           break;
   1350         if (LHSWidth < SrcWidth)
   1351           LHSOrig = Builder->CreateFPExt(LHSOrig, RHSOrig->getType());
   1352         else if (RHSWidth <= SrcWidth)
   1353           RHSOrig = Builder->CreateFPExt(RHSOrig, LHSOrig->getType());
   1354         if (LHSOrig != OpI->getOperand(0) || RHSOrig != OpI->getOperand(1)) {
   1355           Value *ExactResult = Builder->CreateFRem(LHSOrig, RHSOrig);
   1356           if (Instruction *RI = dyn_cast<Instruction>(ExactResult))
   1357             RI->copyFastMathFlags(OpI);
   1358           return CastInst::CreateFPCast(ExactResult, CI.getType());
   1359         }
   1360     }
   1361 
   1362     // (fptrunc (fneg x)) -> (fneg (fptrunc x))
   1363     if (BinaryOperator::isFNeg(OpI)) {
   1364       Value *InnerTrunc = Builder->CreateFPTrunc(OpI->getOperand(1),
   1365                                                  CI.getType());
   1366       Instruction *RI = BinaryOperator::CreateFNeg(InnerTrunc);
   1367       RI->copyFastMathFlags(OpI);
   1368       return RI;
   1369     }
   1370   }
   1371 
   1372   // (fptrunc (select cond, R1, Cst)) -->
   1373   // (select cond, (fptrunc R1), (fptrunc Cst))
   1374   //
   1375   //  - but only if this isn't part of a min/max operation, else we'll
   1376   // ruin min/max canonical form which is to have the select and
   1377   // compare's operands be of the same type with no casts to look through.
   1378   Value *LHS, *RHS;
   1379   SelectInst *SI = dyn_cast<SelectInst>(CI.getOperand(0));
   1380   if (SI &&
   1381       (isa<ConstantFP>(SI->getOperand(1)) ||
   1382        isa<ConstantFP>(SI->getOperand(2))) &&
   1383       matchSelectPattern(SI, LHS, RHS).Flavor == SPF_UNKNOWN) {
   1384     Value *LHSTrunc = Builder->CreateFPTrunc(SI->getOperand(1),
   1385                                              CI.getType());
   1386     Value *RHSTrunc = Builder->CreateFPTrunc(SI->getOperand(2),
   1387                                              CI.getType());
   1388     return SelectInst::Create(SI->getOperand(0), LHSTrunc, RHSTrunc);
   1389   }
   1390 
   1391   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI.getOperand(0));
   1392   if (II) {
   1393     switch (II->getIntrinsicID()) {
   1394       default: break;
   1395       case Intrinsic::fabs: {
   1396         // (fptrunc (fabs x)) -> (fabs (fptrunc x))
   1397         Value *InnerTrunc = Builder->CreateFPTrunc(II->getArgOperand(0),
   1398                                                    CI.getType());
   1399         Type *IntrinsicType[] = { CI.getType() };
   1400         Function *Overload = Intrinsic::getDeclaration(
   1401             CI.getModule(), II->getIntrinsicID(), IntrinsicType);
   1402 
   1403         SmallVector<OperandBundleDef, 1> OpBundles;
   1404         II->getOperandBundlesAsDefs(OpBundles);
   1405 
   1406         Value *Args[] = { InnerTrunc };
   1407         return CallInst::Create(Overload, Args, OpBundles, II->getName());
   1408       }
   1409     }
   1410   }
   1411 
   1412   return nullptr;
   1413 }
   1414 
   1415 Instruction *InstCombiner::visitFPExt(CastInst &CI) {
   1416   return commonCastTransforms(CI);
   1417 }
   1418 
   1419 // fpto{s/u}i({u/s}itofp(X)) --> X or zext(X) or sext(X) or trunc(X)
   1420 // This is safe if the intermediate type has enough bits in its mantissa to
   1421 // accurately represent all values of X.  For example, this won't work with
   1422 // i64 -> float -> i64.
   1423 Instruction *InstCombiner::FoldItoFPtoI(Instruction &FI) {
   1424   if (!isa<UIToFPInst>(FI.getOperand(0)) && !isa<SIToFPInst>(FI.getOperand(0)))
   1425     return nullptr;
   1426   Instruction *OpI = cast<Instruction>(FI.getOperand(0));
   1427 
   1428   Value *SrcI = OpI->getOperand(0);
   1429   Type *FITy = FI.getType();
   1430   Type *OpITy = OpI->getType();
   1431   Type *SrcTy = SrcI->getType();
   1432   bool IsInputSigned = isa<SIToFPInst>(OpI);
   1433   bool IsOutputSigned = isa<FPToSIInst>(FI);
   1434 
   1435   // We can safely assume the conversion won't overflow the output range,
   1436   // because (for example) (uint8_t)18293.f is undefined behavior.
   1437 
   1438   // Since we can assume the conversion won't overflow, our decision as to
   1439   // whether the input will fit in the float should depend on the minimum
   1440   // of the input range and output range.
   1441 
   1442   // This means this is also safe for a signed input and unsigned output, since
   1443   // a negative input would lead to undefined behavior.
   1444   int InputSize = (int)SrcTy->getScalarSizeInBits() - IsInputSigned;
   1445   int OutputSize = (int)FITy->getScalarSizeInBits() - IsOutputSigned;
   1446   int ActualSize = std::min(InputSize, OutputSize);
   1447 
   1448   if (ActualSize <= OpITy->getFPMantissaWidth()) {
   1449     if (FITy->getScalarSizeInBits() > SrcTy->getScalarSizeInBits()) {
   1450       if (IsInputSigned && IsOutputSigned)
   1451         return new SExtInst(SrcI, FITy);
   1452       return new ZExtInst(SrcI, FITy);
   1453     }
   1454     if (FITy->getScalarSizeInBits() < SrcTy->getScalarSizeInBits())
   1455       return new TruncInst(SrcI, FITy);
   1456     if (SrcTy == FITy)
   1457       return replaceInstUsesWith(FI, SrcI);
   1458     return new BitCastInst(SrcI, FITy);
   1459   }
   1460   return nullptr;
   1461 }
   1462 
   1463 Instruction *InstCombiner::visitFPToUI(FPToUIInst &FI) {
   1464   Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0));
   1465   if (!OpI)
   1466     return commonCastTransforms(FI);
   1467 
   1468   if (Instruction *I = FoldItoFPtoI(FI))
   1469     return I;
   1470 
   1471   return commonCastTransforms(FI);
   1472 }
   1473 
   1474 Instruction *InstCombiner::visitFPToSI(FPToSIInst &FI) {
   1475   Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0));
   1476   if (!OpI)
   1477     return commonCastTransforms(FI);
   1478 
   1479   if (Instruction *I = FoldItoFPtoI(FI))
   1480     return I;
   1481 
   1482   return commonCastTransforms(FI);
   1483 }
   1484 
   1485 Instruction *InstCombiner::visitUIToFP(CastInst &CI) {
   1486   return commonCastTransforms(CI);
   1487 }
   1488 
   1489 Instruction *InstCombiner::visitSIToFP(CastInst &CI) {
   1490   return commonCastTransforms(CI);
   1491 }
   1492 
   1493 Instruction *InstCombiner::visitIntToPtr(IntToPtrInst &CI) {
   1494   // If the source integer type is not the intptr_t type for this target, do a
   1495   // trunc or zext to the intptr_t type, then inttoptr of it.  This allows the
   1496   // cast to be exposed to other transforms.
   1497   unsigned AS = CI.getAddressSpace();
   1498   if (CI.getOperand(0)->getType()->getScalarSizeInBits() !=
   1499       DL.getPointerSizeInBits(AS)) {
   1500     Type *Ty = DL.getIntPtrType(CI.getContext(), AS);
   1501     if (CI.getType()->isVectorTy()) // Handle vectors of pointers.
   1502       Ty = VectorType::get(Ty, CI.getType()->getVectorNumElements());
   1503 
   1504     Value *P = Builder->CreateZExtOrTrunc(CI.getOperand(0), Ty);
   1505     return new IntToPtrInst(P, CI.getType());
   1506   }
   1507 
   1508   if (Instruction *I = commonCastTransforms(CI))
   1509     return I;
   1510 
   1511   return nullptr;
   1512 }
   1513 
   1514 /// @brief Implement the transforms for cast of pointer (bitcast/ptrtoint)
   1515 Instruction *InstCombiner::commonPointerCastTransforms(CastInst &CI) {
   1516   Value *Src = CI.getOperand(0);
   1517 
   1518   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
   1519     // If casting the result of a getelementptr instruction with no offset, turn
   1520     // this into a cast of the original pointer!
   1521     if (GEP->hasAllZeroIndices() &&
   1522         // If CI is an addrspacecast and GEP changes the poiner type, merging
   1523         // GEP into CI would undo canonicalizing addrspacecast with different
   1524         // pointer types, causing infinite loops.
   1525         (!isa<AddrSpaceCastInst>(CI) ||
   1526           GEP->getType() == GEP->getPointerOperand()->getType())) {
   1527       // Changing the cast operand is usually not a good idea but it is safe
   1528       // here because the pointer operand is being replaced with another
   1529       // pointer operand so the opcode doesn't need to change.
   1530       Worklist.Add(GEP);
   1531       CI.setOperand(0, GEP->getOperand(0));
   1532       return &CI;
   1533     }
   1534   }
   1535 
   1536   return commonCastTransforms(CI);
   1537 }
   1538 
   1539 Instruction *InstCombiner::visitPtrToInt(PtrToIntInst &CI) {
   1540   // If the destination integer type is not the intptr_t type for this target,
   1541   // do a ptrtoint to intptr_t then do a trunc or zext.  This allows the cast
   1542   // to be exposed to other transforms.
   1543 
   1544   Type *Ty = CI.getType();
   1545   unsigned AS = CI.getPointerAddressSpace();
   1546 
   1547   if (Ty->getScalarSizeInBits() == DL.getPointerSizeInBits(AS))
   1548     return commonPointerCastTransforms(CI);
   1549 
   1550   Type *PtrTy = DL.getIntPtrType(CI.getContext(), AS);
   1551   if (Ty->isVectorTy()) // Handle vectors of pointers.
   1552     PtrTy = VectorType::get(PtrTy, Ty->getVectorNumElements());
   1553 
   1554   Value *P = Builder->CreatePtrToInt(CI.getOperand(0), PtrTy);
   1555   return CastInst::CreateIntegerCast(P, Ty, /*isSigned=*/false);
   1556 }
   1557 
   1558 /// This input value (which is known to have vector type) is being zero extended
   1559 /// or truncated to the specified vector type.
   1560 /// Try to replace it with a shuffle (and vector/vector bitcast) if possible.
   1561 ///
   1562 /// The source and destination vector types may have different element types.
   1563 static Instruction *optimizeVectorResize(Value *InVal, VectorType *DestTy,
   1564                                          InstCombiner &IC) {
   1565   // We can only do this optimization if the output is a multiple of the input
   1566   // element size, or the input is a multiple of the output element size.
   1567   // Convert the input type to have the same element type as the output.
   1568   VectorType *SrcTy = cast<VectorType>(InVal->getType());
   1569 
   1570   if (SrcTy->getElementType() != DestTy->getElementType()) {
   1571     // The input types don't need to be identical, but for now they must be the
   1572     // same size.  There is no specific reason we couldn't handle things like
   1573     // <4 x i16> -> <4 x i32> by bitcasting to <2 x i32> but haven't gotten
   1574     // there yet.
   1575     if (SrcTy->getElementType()->getPrimitiveSizeInBits() !=
   1576         DestTy->getElementType()->getPrimitiveSizeInBits())
   1577       return nullptr;
   1578 
   1579     SrcTy = VectorType::get(DestTy->getElementType(), SrcTy->getNumElements());
   1580     InVal = IC.Builder->CreateBitCast(InVal, SrcTy);
   1581   }
   1582 
   1583   // Now that the element types match, get the shuffle mask and RHS of the
   1584   // shuffle to use, which depends on whether we're increasing or decreasing the
   1585   // size of the input.
   1586   SmallVector<uint32_t, 16> ShuffleMask;
   1587   Value *V2;
   1588 
   1589   if (SrcTy->getNumElements() > DestTy->getNumElements()) {
   1590     // If we're shrinking the number of elements, just shuffle in the low
   1591     // elements from the input and use undef as the second shuffle input.
   1592     V2 = UndefValue::get(SrcTy);
   1593     for (unsigned i = 0, e = DestTy->getNumElements(); i != e; ++i)
   1594       ShuffleMask.push_back(i);
   1595 
   1596   } else {
   1597     // If we're increasing the number of elements, shuffle in all of the
   1598     // elements from InVal and fill the rest of the result elements with zeros
   1599     // from a constant zero.
   1600     V2 = Constant::getNullValue(SrcTy);
   1601     unsigned SrcElts = SrcTy->getNumElements();
   1602     for (unsigned i = 0, e = SrcElts; i != e; ++i)
   1603       ShuffleMask.push_back(i);
   1604 
   1605     // The excess elements reference the first element of the zero input.
   1606     for (unsigned i = 0, e = DestTy->getNumElements()-SrcElts; i != e; ++i)
   1607       ShuffleMask.push_back(SrcElts);
   1608   }
   1609 
   1610   return new ShuffleVectorInst(InVal, V2,
   1611                                ConstantDataVector::get(V2->getContext(),
   1612                                                        ShuffleMask));
   1613 }
   1614 
   1615 static bool isMultipleOfTypeSize(unsigned Value, Type *Ty) {
   1616   return Value % Ty->getPrimitiveSizeInBits() == 0;
   1617 }
   1618 
   1619 static unsigned getTypeSizeIndex(unsigned Value, Type *Ty) {
   1620   return Value / Ty->getPrimitiveSizeInBits();
   1621 }
   1622 
   1623 /// V is a value which is inserted into a vector of VecEltTy.
   1624 /// Look through the value to see if we can decompose it into
   1625 /// insertions into the vector.  See the example in the comment for
   1626 /// OptimizeIntegerToVectorInsertions for the pattern this handles.
   1627 /// The type of V is always a non-zero multiple of VecEltTy's size.
   1628 /// Shift is the number of bits between the lsb of V and the lsb of
   1629 /// the vector.
   1630 ///
   1631 /// This returns false if the pattern can't be matched or true if it can,
   1632 /// filling in Elements with the elements found here.
   1633 static bool collectInsertionElements(Value *V, unsigned Shift,
   1634                                      SmallVectorImpl<Value *> &Elements,
   1635                                      Type *VecEltTy, bool isBigEndian) {
   1636   assert(isMultipleOfTypeSize(Shift, VecEltTy) &&
   1637          "Shift should be a multiple of the element type size");
   1638 
   1639   // Undef values never contribute useful bits to the result.
   1640   if (isa<UndefValue>(V)) return true;
   1641 
   1642   // If we got down to a value of the right type, we win, try inserting into the
   1643   // right element.
   1644   if (V->getType() == VecEltTy) {
   1645     // Inserting null doesn't actually insert any elements.
   1646     if (Constant *C = dyn_cast<Constant>(V))
   1647       if (C->isNullValue())
   1648         return true;
   1649 
   1650     unsigned ElementIndex = getTypeSizeIndex(Shift, VecEltTy);
   1651     if (isBigEndian)
   1652       ElementIndex = Elements.size() - ElementIndex - 1;
   1653 
   1654     // Fail if multiple elements are inserted into this slot.
   1655     if (Elements[ElementIndex])
   1656       return false;
   1657 
   1658     Elements[ElementIndex] = V;
   1659     return true;
   1660   }
   1661 
   1662   if (Constant *C = dyn_cast<Constant>(V)) {
   1663     // Figure out the # elements this provides, and bitcast it or slice it up
   1664     // as required.
   1665     unsigned NumElts = getTypeSizeIndex(C->getType()->getPrimitiveSizeInBits(),
   1666                                         VecEltTy);
   1667     // If the constant is the size of a vector element, we just need to bitcast
   1668     // it to the right type so it gets properly inserted.
   1669     if (NumElts == 1)
   1670       return collectInsertionElements(ConstantExpr::getBitCast(C, VecEltTy),
   1671                                       Shift, Elements, VecEltTy, isBigEndian);
   1672 
   1673     // Okay, this is a constant that covers multiple elements.  Slice it up into
   1674     // pieces and insert each element-sized piece into the vector.
   1675     if (!isa<IntegerType>(C->getType()))
   1676       C = ConstantExpr::getBitCast(C, IntegerType::get(V->getContext(),
   1677                                        C->getType()->getPrimitiveSizeInBits()));
   1678     unsigned ElementSize = VecEltTy->getPrimitiveSizeInBits();
   1679     Type *ElementIntTy = IntegerType::get(C->getContext(), ElementSize);
   1680 
   1681     for (unsigned i = 0; i != NumElts; ++i) {
   1682       unsigned ShiftI = Shift+i*ElementSize;
   1683       Constant *Piece = ConstantExpr::getLShr(C, ConstantInt::get(C->getType(),
   1684                                                                   ShiftI));
   1685       Piece = ConstantExpr::getTrunc(Piece, ElementIntTy);
   1686       if (!collectInsertionElements(Piece, ShiftI, Elements, VecEltTy,
   1687                                     isBigEndian))
   1688         return false;
   1689     }
   1690     return true;
   1691   }
   1692 
   1693   if (!V->hasOneUse()) return false;
   1694 
   1695   Instruction *I = dyn_cast<Instruction>(V);
   1696   if (!I) return false;
   1697   switch (I->getOpcode()) {
   1698   default: return false; // Unhandled case.
   1699   case Instruction::BitCast:
   1700     return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
   1701                                     isBigEndian);
   1702   case Instruction::ZExt:
   1703     if (!isMultipleOfTypeSize(
   1704                           I->getOperand(0)->getType()->getPrimitiveSizeInBits(),
   1705                               VecEltTy))
   1706       return false;
   1707     return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
   1708                                     isBigEndian);
   1709   case Instruction::Or:
   1710     return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
   1711                                     isBigEndian) &&
   1712            collectInsertionElements(I->getOperand(1), Shift, Elements, VecEltTy,
   1713                                     isBigEndian);
   1714   case Instruction::Shl: {
   1715     // Must be shifting by a constant that is a multiple of the element size.
   1716     ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1));
   1717     if (!CI) return false;
   1718     Shift += CI->getZExtValue();
   1719     if (!isMultipleOfTypeSize(Shift, VecEltTy)) return false;
   1720     return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
   1721                                     isBigEndian);
   1722   }
   1723 
   1724   }
   1725 }
   1726 
   1727 
   1728 /// If the input is an 'or' instruction, we may be doing shifts and ors to
   1729 /// assemble the elements of the vector manually.
   1730 /// Try to rip the code out and replace it with insertelements.  This is to
   1731 /// optimize code like this:
   1732 ///
   1733 ///    %tmp37 = bitcast float %inc to i32
   1734 ///    %tmp38 = zext i32 %tmp37 to i64
   1735 ///    %tmp31 = bitcast float %inc5 to i32
   1736 ///    %tmp32 = zext i32 %tmp31 to i64
   1737 ///    %tmp33 = shl i64 %tmp32, 32
   1738 ///    %ins35 = or i64 %tmp33, %tmp38
   1739 ///    %tmp43 = bitcast i64 %ins35 to <2 x float>
   1740 ///
   1741 /// Into two insertelements that do "buildvector{%inc, %inc5}".
   1742 static Value *optimizeIntegerToVectorInsertions(BitCastInst &CI,
   1743                                                 InstCombiner &IC) {
   1744   VectorType *DestVecTy = cast<VectorType>(CI.getType());
   1745   Value *IntInput = CI.getOperand(0);
   1746 
   1747   SmallVector<Value*, 8> Elements(DestVecTy->getNumElements());
   1748   if (!collectInsertionElements(IntInput, 0, Elements,
   1749                                 DestVecTy->getElementType(),
   1750                                 IC.getDataLayout().isBigEndian()))
   1751     return nullptr;
   1752 
   1753   // If we succeeded, we know that all of the element are specified by Elements
   1754   // or are zero if Elements has a null entry.  Recast this as a set of
   1755   // insertions.
   1756   Value *Result = Constant::getNullValue(CI.getType());
   1757   for (unsigned i = 0, e = Elements.size(); i != e; ++i) {
   1758     if (!Elements[i]) continue;  // Unset element.
   1759 
   1760     Result = IC.Builder->CreateInsertElement(Result, Elements[i],
   1761                                              IC.Builder->getInt32(i));
   1762   }
   1763 
   1764   return Result;
   1765 }
   1766 
   1767 /// Canonicalize scalar bitcasts of extracted elements into a bitcast of the
   1768 /// vector followed by extract element. The backend tends to handle bitcasts of
   1769 /// vectors better than bitcasts of scalars because vector registers are
   1770 /// usually not type-specific like scalar integer or scalar floating-point.
   1771 static Instruction *canonicalizeBitCastExtElt(BitCastInst &BitCast,
   1772                                               InstCombiner &IC,
   1773                                               const DataLayout &DL) {
   1774   // TODO: Create and use a pattern matcher for ExtractElementInst.
   1775   auto *ExtElt = dyn_cast<ExtractElementInst>(BitCast.getOperand(0));
   1776   if (!ExtElt || !ExtElt->hasOneUse())
   1777     return nullptr;
   1778 
   1779   // The bitcast must be to a vectorizable type, otherwise we can't make a new
   1780   // type to extract from.
   1781   Type *DestType = BitCast.getType();
   1782   if (!VectorType::isValidElementType(DestType))
   1783     return nullptr;
   1784 
   1785   unsigned NumElts = ExtElt->getVectorOperandType()->getNumElements();
   1786   auto *NewVecType = VectorType::get(DestType, NumElts);
   1787   auto *NewBC = IC.Builder->CreateBitCast(ExtElt->getVectorOperand(),
   1788                                           NewVecType, "bc");
   1789   return ExtractElementInst::Create(NewBC, ExtElt->getIndexOperand());
   1790 }
   1791 
   1792 Instruction *InstCombiner::visitBitCast(BitCastInst &CI) {
   1793   // If the operands are integer typed then apply the integer transforms,
   1794   // otherwise just apply the common ones.
   1795   Value *Src = CI.getOperand(0);
   1796   Type *SrcTy = Src->getType();
   1797   Type *DestTy = CI.getType();
   1798 
   1799   // Get rid of casts from one type to the same type. These are useless and can
   1800   // be replaced by the operand.
   1801   if (DestTy == Src->getType())
   1802     return replaceInstUsesWith(CI, Src);
   1803 
   1804   if (PointerType *DstPTy = dyn_cast<PointerType>(DestTy)) {
   1805     PointerType *SrcPTy = cast<PointerType>(SrcTy);
   1806     Type *DstElTy = DstPTy->getElementType();
   1807     Type *SrcElTy = SrcPTy->getElementType();
   1808 
   1809     // If we are casting a alloca to a pointer to a type of the same
   1810     // size, rewrite the allocation instruction to allocate the "right" type.
   1811     // There is no need to modify malloc calls because it is their bitcast that
   1812     // needs to be cleaned up.
   1813     if (AllocaInst *AI = dyn_cast<AllocaInst>(Src))
   1814       if (Instruction *V = PromoteCastOfAllocation(CI, *AI))
   1815         return V;
   1816 
   1817     // When the type pointed to is not sized the cast cannot be
   1818     // turned into a gep.
   1819     Type *PointeeType =
   1820         cast<PointerType>(Src->getType()->getScalarType())->getElementType();
   1821     if (!PointeeType->isSized())
   1822       return nullptr;
   1823 
   1824     // If the source and destination are pointers, and this cast is equivalent
   1825     // to a getelementptr X, 0, 0, 0...  turn it into the appropriate gep.
   1826     // This can enhance SROA and other transforms that want type-safe pointers.
   1827     unsigned NumZeros = 0;
   1828     while (SrcElTy != DstElTy &&
   1829            isa<CompositeType>(SrcElTy) && !SrcElTy->isPointerTy() &&
   1830            SrcElTy->getNumContainedTypes() /* not "{}" */) {
   1831       SrcElTy = cast<CompositeType>(SrcElTy)->getTypeAtIndex(0U);
   1832       ++NumZeros;
   1833     }
   1834 
   1835     // If we found a path from the src to dest, create the getelementptr now.
   1836     if (SrcElTy == DstElTy) {
   1837       SmallVector<Value *, 8> Idxs(NumZeros + 1, Builder->getInt32(0));
   1838       return GetElementPtrInst::CreateInBounds(Src, Idxs);
   1839     }
   1840   }
   1841 
   1842   if (VectorType *DestVTy = dyn_cast<VectorType>(DestTy)) {
   1843     if (DestVTy->getNumElements() == 1 && !SrcTy->isVectorTy()) {
   1844       Value *Elem = Builder->CreateBitCast(Src, DestVTy->getElementType());
   1845       return InsertElementInst::Create(UndefValue::get(DestTy), Elem,
   1846                      Constant::getNullValue(Type::getInt32Ty(CI.getContext())));
   1847       // FIXME: Canonicalize bitcast(insertelement) -> insertelement(bitcast)
   1848     }
   1849 
   1850     if (isa<IntegerType>(SrcTy)) {
   1851       // If this is a cast from an integer to vector, check to see if the input
   1852       // is a trunc or zext of a bitcast from vector.  If so, we can replace all
   1853       // the casts with a shuffle and (potentially) a bitcast.
   1854       if (isa<TruncInst>(Src) || isa<ZExtInst>(Src)) {
   1855         CastInst *SrcCast = cast<CastInst>(Src);
   1856         if (BitCastInst *BCIn = dyn_cast<BitCastInst>(SrcCast->getOperand(0)))
   1857           if (isa<VectorType>(BCIn->getOperand(0)->getType()))
   1858             if (Instruction *I = optimizeVectorResize(BCIn->getOperand(0),
   1859                                                cast<VectorType>(DestTy), *this))
   1860               return I;
   1861       }
   1862 
   1863       // If the input is an 'or' instruction, we may be doing shifts and ors to
   1864       // assemble the elements of the vector manually.  Try to rip the code out
   1865       // and replace it with insertelements.
   1866       if (Value *V = optimizeIntegerToVectorInsertions(CI, *this))
   1867         return replaceInstUsesWith(CI, V);
   1868     }
   1869   }
   1870 
   1871   if (VectorType *SrcVTy = dyn_cast<VectorType>(SrcTy)) {
   1872     if (SrcVTy->getNumElements() == 1) {
   1873       // If our destination is not a vector, then make this a straight
   1874       // scalar-scalar cast.
   1875       if (!DestTy->isVectorTy()) {
   1876         Value *Elem =
   1877           Builder->CreateExtractElement(Src,
   1878                      Constant::getNullValue(Type::getInt32Ty(CI.getContext())));
   1879         return CastInst::Create(Instruction::BitCast, Elem, DestTy);
   1880       }
   1881 
   1882       // Otherwise, see if our source is an insert. If so, then use the scalar
   1883       // component directly.
   1884       if (InsertElementInst *IEI =
   1885             dyn_cast<InsertElementInst>(CI.getOperand(0)))
   1886         return CastInst::Create(Instruction::BitCast, IEI->getOperand(1),
   1887                                 DestTy);
   1888     }
   1889   }
   1890 
   1891   if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(Src)) {
   1892     // Okay, we have (bitcast (shuffle ..)).  Check to see if this is
   1893     // a bitcast to a vector with the same # elts.
   1894     if (SVI->hasOneUse() && DestTy->isVectorTy() &&
   1895         DestTy->getVectorNumElements() == SVI->getType()->getNumElements() &&
   1896         SVI->getType()->getNumElements() ==
   1897         SVI->getOperand(0)->getType()->getVectorNumElements()) {
   1898       BitCastInst *Tmp;
   1899       // If either of the operands is a cast from CI.getType(), then
   1900       // evaluating the shuffle in the casted destination's type will allow
   1901       // us to eliminate at least one cast.
   1902       if (((Tmp = dyn_cast<BitCastInst>(SVI->getOperand(0))) &&
   1903            Tmp->getOperand(0)->getType() == DestTy) ||
   1904           ((Tmp = dyn_cast<BitCastInst>(SVI->getOperand(1))) &&
   1905            Tmp->getOperand(0)->getType() == DestTy)) {
   1906         Value *LHS = Builder->CreateBitCast(SVI->getOperand(0), DestTy);
   1907         Value *RHS = Builder->CreateBitCast(SVI->getOperand(1), DestTy);
   1908         // Return a new shuffle vector.  Use the same element ID's, as we
   1909         // know the vector types match #elts.
   1910         return new ShuffleVectorInst(LHS, RHS, SVI->getOperand(2));
   1911       }
   1912     }
   1913   }
   1914 
   1915   if (Instruction *I = canonicalizeBitCastExtElt(CI, *this, DL))
   1916     return I;
   1917 
   1918   if (SrcTy->isPointerTy())
   1919     return commonPointerCastTransforms(CI);
   1920   return commonCastTransforms(CI);
   1921 }
   1922 
   1923 Instruction *InstCombiner::visitAddrSpaceCast(AddrSpaceCastInst &CI) {
   1924   // If the destination pointer element type is not the same as the source's
   1925   // first do a bitcast to the destination type, and then the addrspacecast.
   1926   // This allows the cast to be exposed to other transforms.
   1927   Value *Src = CI.getOperand(0);
   1928   PointerType *SrcTy = cast<PointerType>(Src->getType()->getScalarType());
   1929   PointerType *DestTy = cast<PointerType>(CI.getType()->getScalarType());
   1930 
   1931   Type *DestElemTy = DestTy->getElementType();
   1932   if (SrcTy->getElementType() != DestElemTy) {
   1933     Type *MidTy = PointerType::get(DestElemTy, SrcTy->getAddressSpace());
   1934     if (VectorType *VT = dyn_cast<VectorType>(CI.getType())) {
   1935       // Handle vectors of pointers.
   1936       MidTy = VectorType::get(MidTy, VT->getNumElements());
   1937     }
   1938 
   1939     Value *NewBitCast = Builder->CreateBitCast(Src, MidTy);
   1940     return new AddrSpaceCastInst(NewBitCast, CI.getType());
   1941   }
   1942 
   1943   return commonPointerCastTransforms(CI);
   1944 }
   1945