lib/Transforms/InstCombine/InstCombineCasts.cpp

   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 "InstCombine.h"
  15 #include "llvm/Target/TargetData.h"
  16 #include "llvm/Support/PatternMatch.h"
  17 using namespace llvm;
  18 using namespace PatternMatch;
  19
  20 // FIXME: InstCombiner::EvaluateInDifferentType!
  21
  22
  23 /// This function is a wrapper around CastInst::isEliminableCastPair. It
  24 /// simply extracts arguments and returns what that function returns.
  25 static Instruction::CastOps
  26 isEliminableCastPair(
  27   const CastInst *CI, ///< The first cast instruction
  28   unsigned opcode,       ///< The opcode of the second cast instruction
  29   const Type *DstTy,     ///< The target type for the second cast instruction
  30   TargetData *TD         ///< The target data for pointer size
  31 ) {
  32
  33   const Type *SrcTy = CI->getOperand(0)->getType();   // A from above
  34   const Type *MidTy = CI->getType();                  // B from above
  35
  36   // Get the opcodes of the two Cast instructions
  37   Instruction::CastOps firstOp = Instruction::CastOps(CI->getOpcode());
  38   Instruction::CastOps secondOp = Instruction::CastOps(opcode);
  39
  40   unsigned Res = CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy,
  41                                                 DstTy,
  42                                   TD ? TD->getIntPtrType(CI->getContext()) : 0);
  43
  44   // We don't want to form an inttoptr or ptrtoint that converts to an integer
  45   // type that differs from the pointer size.
  46   if ((Res == Instruction::IntToPtr &&
  47           (!TD || SrcTy != TD->getIntPtrType(CI->getContext()))) ||
  48       (Res == Instruction::PtrToInt &&
  49           (!TD || DstTy != TD->getIntPtrType(CI->getContext()))))
  50     Res = 0;
  51
  52   return Instruction::CastOps(Res);
  53 }
  54
  55 /// ValueRequiresCast - Return true if the cast from "V to Ty" actually results
  56 /// in any code being generated.  It does not require codegen if V is simple
  57 /// enough or if the cast can be folded into other casts.
  58 bool InstCombiner::ValueRequiresCast(Instruction::CastOps opcode,const Value *V,
  59                                      const Type *Ty) {
  60   if (V->getType() == Ty || isa<Constant>(V)) return false;
  61
  62   // If this is another cast that can be eliminated, it isn't codegen either.
  63   if (const CastInst *CI = dyn_cast<CastInst>(V))
  64     if (isEliminableCastPair(CI, opcode, Ty, TD))
  65       return false;
  66   return true;
  67 }
  68
  69
  70 /// @brief Implement the transforms common to all CastInst visitors.
  71 Instruction *InstCombiner::commonCastTransforms(CastInst &CI) {
  72   Value *Src = CI.getOperand(0);
  73
  74   // Many cases of "cast of a cast" are eliminable. If it's eliminable we just
  75   // eliminate it now.
  76   if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {   // A->B->C cast
  77     if (Instruction::CastOps opc =
  78         isEliminableCastPair(CSrc, CI.getOpcode(), CI.getType(), TD)) {
  79       // The first cast (CSrc) is eliminable so we need to fix up or replace
  80       // the second cast (CI). CSrc will then have a good chance of being dead.
  81       return CastInst::Create(opc, CSrc->getOperand(0), CI.getType());
  82     }
  83   }
  84
  85   // If we are casting a select then fold the cast into the select
  86   if (SelectInst *SI = dyn_cast<SelectInst>(Src))
  87     if (Instruction *NV = FoldOpIntoSelect(CI, SI))
  88       return NV;
  89
  90   // If we are casting a PHI then fold the cast into the PHI
  91   if (isa<PHINode>(Src)) {
  92     // We don't do this if this would create a PHI node with an illegal type if
  93     // it is currently legal.
  94     if (!isa<IntegerType>(Src->getType()) ||
  95         !isa<IntegerType>(CI.getType()) ||
  96         ShouldChangeType(CI.getType(), Src->getType()))
  97       if (Instruction *NV = FoldOpIntoPhi(CI))
  98         return NV;
  99   }
 100
 101   return 0;
 102 }
 103
 104 /// @brief Implement the transforms for cast of pointer (bitcast/ptrtoint)
 105 Instruction *InstCombiner::commonPointerCastTransforms(CastInst &CI) {
 106   Value *Src = CI.getOperand(0);
 107
 108   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
 109     // If casting the result of a getelementptr instruction with no offset, turn
 110     // this into a cast of the original pointer!
 111     if (GEP->hasAllZeroIndices()) {
 112       // Changing the cast operand is usually not a good idea but it is safe
 113       // here because the pointer operand is being replaced with another
 114       // pointer operand so the opcode doesn't need to change.
 115       Worklist.Add(GEP);
 116       CI.setOperand(0, GEP->getOperand(0));
 117       return &CI;
 118     }
 119
 120     // If the GEP has a single use, and the base pointer is a bitcast, and the
 121     // GEP computes a constant offset, see if we can convert these three
 122     // instructions into fewer.  This typically happens with unions and other
 123     // non-type-safe code.
 124     if (TD && GEP->hasOneUse() && isa<BitCastInst>(GEP->getOperand(0))) {
 125       if (GEP->hasAllConstantIndices()) {
 126         // We are guaranteed to get a constant from EmitGEPOffset.
 127         ConstantInt *OffsetV = cast<ConstantInt>(EmitGEPOffset(GEP));
 128         int64_t Offset = OffsetV->getSExtValue();
 129
 130         // Get the base pointer input of the bitcast, and the type it points to.
 131         Value *OrigBase = cast<BitCastInst>(GEP->getOperand(0))->getOperand(0);
 132         const Type *GEPIdxTy =
 133           cast<PointerType>(OrigBase->getType())->getElementType();
 134         SmallVector<Value*, 8> NewIndices;
 135         if (FindElementAtOffset(GEPIdxTy, Offset, NewIndices)) {
 136           // If we were able to index down into an element, create the GEP
 137           // and bitcast the result.  This eliminates one bitcast, potentially
 138           // two.
 139           Value *NGEP = cast<GEPOperator>(GEP)->isInBounds() ?
 140             Builder->CreateInBoundsGEP(OrigBase,
 141                                        NewIndices.begin(), NewIndices.end()) :
 142             Builder->CreateGEP(OrigBase, NewIndices.begin(), NewIndices.end());
 143           NGEP->takeName(GEP);
 144
 145           if (isa<BitCastInst>(CI))
 146             return new BitCastInst(NGEP, CI.getType());
 147           assert(isa<PtrToIntInst>(CI));
 148           return new PtrToIntInst(NGEP, CI.getType());
 149         }
 150       }
 151     }
 152   }
 153
 154   return commonCastTransforms(CI);
 155 }
 156
 157 /// commonIntCastTransforms - This function implements the common transforms
 158 /// for trunc, zext, and sext.
 159 Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
 160   if (Instruction *Result = commonCastTransforms(CI))
 161     return Result;
 162
 163   Value *Src = CI.getOperand(0);
 164   const Type *SrcTy = Src->getType();
 165   const Type *DestTy = CI.getType();
 166   uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
 167   uint32_t DestBitSize = DestTy->getScalarSizeInBits();
 168
 169   // See if we can simplify any instructions used by the LHS whose sole
 170   // purpose is to compute bits we don't care about.
 171   if (SimplifyDemandedInstructionBits(CI))
 172     return &CI;
 173
 174   // If the source isn't an instruction or has more than one use then we
 175   // can't do anything more.
 176   Instruction *SrcI = dyn_cast<Instruction>(Src);
 177   if (!SrcI || !Src->hasOneUse())
 178     return 0;
 179
 180   // Attempt to propagate the cast into the instruction for int->int casts.
 181   int NumCastsRemoved = 0;
 182   // Only do this if the dest type is a simple type, don't convert the
 183   // expression tree to something weird like i93 unless the source is also
 184   // strange.
 185   if ((isa<VectorType>(DestTy) ||
 186        ShouldChangeType(SrcI->getType(), DestTy)) &&
 187       CanEvaluateInDifferentType(SrcI, DestTy,
 188                                  CI.getOpcode(), NumCastsRemoved)) {
 189     // If this cast is a truncate, evaluting in a different type always
 190     // eliminates the cast, so it is always a win.  If this is a zero-extension,
 191     // we need to do an AND to maintain the clear top-part of the computation,
 192     // so we require that the input have eliminated at least one cast.  If this
 193     // is a sign extension, we insert two new casts (to do the extension) so we
 194     // require that two casts have been eliminated.
 195     bool DoXForm = false;
 196     bool JustReplace = false;
 197     switch (CI.getOpcode()) {
 198     default:
 199       // All the others use floating point so we shouldn't actually
 200       // get here because of the check above.
 201       llvm_unreachable("Unknown cast type");
 202     case Instruction::Trunc:
 203       DoXForm = true;
 204       break;
 205     case Instruction::ZExt: {
 206       DoXForm = NumCastsRemoved >= 1;
 207
 208       if (!DoXForm && 0) {
 209         // If it's unnecessary to issue an AND to clear the high bits, it's
 210         // always profitable to do this xform.
 211         Value *TryRes = EvaluateInDifferentType(SrcI, DestTy, false);
 212         APInt Mask(APInt::getBitsSet(DestBitSize, SrcBitSize, DestBitSize));
 213         if (MaskedValueIsZero(TryRes, Mask))
 214           return ReplaceInstUsesWith(CI, TryRes);
 215
 216         if (Instruction *TryI = dyn_cast<Instruction>(TryRes))
 217           if (TryI->use_empty())
 218             EraseInstFromFunction(*TryI);
 219       }
 220       break;
 221     }
 222     case Instruction::SExt: {
 223       DoXForm = NumCastsRemoved >= 2;
 224       if (!DoXForm && !isa<TruncInst>(SrcI) && 0) {
 225         // If we do not have to emit the truncate + sext pair, then it's always
 226         // profitable to do this xform.
 227         //
 228         // It's not safe to eliminate the trunc + sext pair if one of the
 229         // eliminated cast is a truncate. e.g.
 230         // t2 = trunc i32 t1 to i16
 231         // t3 = sext i16 t2 to i32
 232         // !=
 233         // i32 t1
 234         Value *TryRes = EvaluateInDifferentType(SrcI, DestTy, true);
 235         unsigned NumSignBits = ComputeNumSignBits(TryRes);
 236         if (NumSignBits > (DestBitSize - SrcBitSize))
 237           return ReplaceInstUsesWith(CI, TryRes);
 238
 239         if (Instruction *TryI = dyn_cast<Instruction>(TryRes))
 240           if (TryI->use_empty())
 241             EraseInstFromFunction(*TryI);
 242       }
 243       break;
 244     }
 245     }
 246
 247     if (DoXForm) {
 248       DEBUG(errs() << "ICE: EvaluateInDifferentType converting expression type"
 249             " to avoid cast: " << CI);
 250       Value *Res = EvaluateInDifferentType(SrcI, DestTy,
 251                                            CI.getOpcode() == Instruction::SExt);
 252       if (JustReplace)
 253         // Just replace this cast with the result.
 254         return ReplaceInstUsesWith(CI, Res);
 255
 256       assert(Res->getType() == DestTy);
 257       switch (CI.getOpcode()) {
 258       default: llvm_unreachable("Unknown cast type!");
 259       case Instruction::Trunc:
 260         // Just replace this cast with the result.
 261         return ReplaceInstUsesWith(CI, Res);
 262       case Instruction::ZExt: {
 263         assert(SrcBitSize < DestBitSize && "Not a zext?");
 264
 265         // If the high bits are already zero, just replace this cast with the
 266         // result.
 267         APInt Mask(APInt::getBitsSet(DestBitSize, SrcBitSize, DestBitSize));
 268         if (MaskedValueIsZero(Res, Mask))
 269           return ReplaceInstUsesWith(CI, Res);
 270
 271         // We need to emit an AND to clear the high bits.
 272         Constant *C = ConstantInt::get(CI.getContext(),
 273                                  APInt::getLowBitsSet(DestBitSize, SrcBitSize));
 274         return BinaryOperator::CreateAnd(Res, C);
 275       }
 276       case Instruction::SExt: {
 277         // If the high bits are already filled with sign bit, just replace this
 278         // cast with the result.
 279         unsigned NumSignBits = ComputeNumSignBits(Res);
 280         if (NumSignBits > (DestBitSize - SrcBitSize))
 281           return ReplaceInstUsesWith(CI, Res);
 282
 283         // We need to emit a cast to truncate, then a cast to sext.
 284         return new SExtInst(Builder->CreateTrunc(Res, Src->getType()), DestTy);
 285       }
 286       }
 287     }
 288   }
 289
 290   Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0;
 291   Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0;
 292
 293   switch (SrcI->getOpcode()) {
 294   case Instruction::Add:
 295   case Instruction::Mul:
 296   case Instruction::And:
 297   case Instruction::Or:
 298   case Instruction::Xor:
 299     // If we are discarding information, rewrite.
 300     if (DestBitSize < SrcBitSize && DestBitSize != 1) {
 301       // Don't insert two casts unless at least one can be eliminated.
 302       if (!ValueRequiresCast(CI.getOpcode(), Op1, DestTy) ||
 303           !ValueRequiresCast(CI.getOpcode(), Op0, DestTy)) {
 304         Value *Op0c = Builder->CreateTrunc(Op0, DestTy, Op0->getName());
 305         Value *Op1c = Builder->CreateTrunc(Op1, DestTy, Op1->getName());
 306         return BinaryOperator::Create(
 307             cast<BinaryOperator>(SrcI)->getOpcode(), Op0c, Op1c);
 308       }
 309     }
 310
 311     // cast (xor bool X, true) to int  --> xor (cast bool X to int), 1
 312     if (isa<ZExtInst>(CI) && SrcBitSize == 1 &&
 313         SrcI->getOpcode() == Instruction::Xor &&
 314         Op1 == ConstantInt::getTrue(CI.getContext()) &&
 315         (!Op0->hasOneUse() || !isa<CmpInst>(Op0))) {
 316       Value *New = Builder->CreateZExt(Op0, DestTy, Op0->getName());
 317       return BinaryOperator::CreateXor(New,
 318                                       ConstantInt::get(CI.getType(), 1));
 319     }
 320     break;
 321
 322   case Instruction::Shl: {
 323     // Canonicalize trunc inside shl, if we can.
 324     ConstantInt *CI = dyn_cast<ConstantInt>(Op1);
 325     if (CI && DestBitSize < SrcBitSize &&
 326         CI->getLimitedValue(DestBitSize) < DestBitSize) {
 327       Value *Op0c = Builder->CreateTrunc(Op0, DestTy, Op0->getName());
 328       Value *Op1c = Builder->CreateTrunc(Op1, DestTy, Op1->getName());
 329       return BinaryOperator::CreateShl(Op0c, Op1c);
 330     }
 331     break;
 332   }
 333   }
 334   return 0;
 335 }
 336
 337
 338 Instruction *InstCombiner::visitTrunc(TruncInst &CI) {
 339   if (Instruction *Result = commonIntCastTransforms(CI))
 340     return Result;
 341
 342   Value *Src = CI.getOperand(0);
 343   const Type *Ty = CI.getType();
 344   uint32_t DestBitWidth = Ty->getScalarSizeInBits();
 345   uint32_t SrcBitWidth = Src->getType()->getScalarSizeInBits();
 346
 347   // Canonicalize trunc x to i1 -> (icmp ne (and x, 1), 0)
 348   if (DestBitWidth == 1) {
 349     Constant *One = ConstantInt::get(Src->getType(), 1);
 350     Src = Builder->CreateAnd(Src, One, "tmp");
 351     Value *Zero = Constant::getNullValue(Src->getType());
 352     return new ICmpInst(ICmpInst::ICMP_NE, Src, Zero);
 353   }
 354
 355   // Optimize trunc(lshr(), c) to pull the shift through the truncate.
 356   ConstantInt *ShAmtV = 0;
 357   Value *ShiftOp = 0;
 358   if (Src->hasOneUse() &&
 359       match(Src, m_LShr(m_Value(ShiftOp), m_ConstantInt(ShAmtV)))) {
 360     uint32_t ShAmt = ShAmtV->getLimitedValue(SrcBitWidth);
 361
 362     // Get a mask for the bits shifting in.
 363     APInt Mask(APInt::getLowBitsSet(SrcBitWidth, ShAmt).shl(DestBitWidth));
 364     if (MaskedValueIsZero(ShiftOp, Mask)) {
 365       if (ShAmt >= DestBitWidth)        // All zeros.
 366         return ReplaceInstUsesWith(CI, Constant::getNullValue(Ty));
 367
 368       // Okay, we can shrink this.  Truncate the input, then return a new
 369       // shift.
 370       Value *V1 = Builder->CreateTrunc(ShiftOp, Ty, ShiftOp->getName());
 371       Value *V2 = ConstantExpr::getTrunc(ShAmtV, Ty);
 372       return BinaryOperator::CreateLShr(V1, V2);
 373     }
 374   }
 375
 376   return 0;
 377 }
 378
 379 /// transformZExtICmp - Transform (zext icmp) to bitwise / integer operations
 380 /// in order to eliminate the icmp.
 381 Instruction *InstCombiner::transformZExtICmp(ICmpInst *ICI, Instruction &CI,
 382                                              bool DoXform) {
 383   // If we are just checking for a icmp eq of a single bit and zext'ing it
 384   // to an integer, then shift the bit to the appropriate place and then
 385   // cast to integer to avoid the comparison.
 386   if (ConstantInt *Op1C = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
 387     const APInt &Op1CV = Op1C->getValue();
 388
 389     // zext (x <s  0) to i32 --> x>>u31      true if signbit set.
 390     // zext (x >s -1) to i32 --> (x>>u31)^1  true if signbit clear.
 391     if ((ICI->getPredicate() == ICmpInst::ICMP_SLT && Op1CV == 0) ||
 392         (ICI->getPredicate() == ICmpInst::ICMP_SGT &&Op1CV.isAllOnesValue())) {
 393       if (!DoXform) return ICI;
 394
 395       Value *In = ICI->getOperand(0);
 396       Value *Sh = ConstantInt::get(In->getType(),
 397                                    In->getType()->getScalarSizeInBits()-1);
 398       In = Builder->CreateLShr(In, Sh, In->getName()+".lobit");
 399       if (In->getType() != CI.getType())
 400         In = Builder->CreateIntCast(In, CI.getType(), false/*ZExt*/, "tmp");
 401
 402       if (ICI->getPredicate() == ICmpInst::ICMP_SGT) {
 403         Constant *One = ConstantInt::get(In->getType(), 1);
 404         In = Builder->CreateXor(In, One, In->getName()+".not");
 405       }
 406
 407       return ReplaceInstUsesWith(CI, In);
 408     }
 409
 410
 411
 412     // zext (X == 0) to i32 --> X^1      iff X has only the low bit set.
 413     // zext (X == 0) to i32 --> (X>>1)^1 iff X has only the 2nd bit set.
 414     // zext (X == 1) to i32 --> X        iff X has only the low bit set.
 415     // zext (X == 2) to i32 --> X>>1     iff X has only the 2nd bit set.
 416     // zext (X != 0) to i32 --> X        iff X has only the low bit set.
 417     // zext (X != 0) to i32 --> X>>1     iff X has only the 2nd bit set.
 418     // zext (X != 1) to i32 --> X^1      iff X has only the low bit set.
 419     // zext (X != 2) to i32 --> (X>>1)^1 iff X has only the 2nd bit set.
 420     if ((Op1CV == 0 || Op1CV.isPowerOf2()) &&
 421         // This only works for EQ and NE
 422         ICI->isEquality()) {
 423       // If Op1C some other power of two, convert:
 424       uint32_t BitWidth = Op1C->getType()->getBitWidth();
 425       APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
 426       APInt TypeMask(APInt::getAllOnesValue(BitWidth));
 427       ComputeMaskedBits(ICI->getOperand(0), TypeMask, KnownZero, KnownOne);
 428
 429       APInt KnownZeroMask(~KnownZero);
 430       if (KnownZeroMask.isPowerOf2()) { // Exactly 1 possible 1?
 431         if (!DoXform) return ICI;
 432
 433         bool isNE = ICI->getPredicate() == ICmpInst::ICMP_NE;
 434         if (Op1CV != 0 && (Op1CV != KnownZeroMask)) {
 435           // (X&4) == 2 --> false
 436           // (X&4) != 2 --> true
 437           Constant *Res = ConstantInt::get(Type::getInt1Ty(CI.getContext()),
 438                                            isNE);
 439           Res = ConstantExpr::getZExt(Res, CI.getType());
 440           return ReplaceInstUsesWith(CI, Res);
 441         }
 442
 443         uint32_t ShiftAmt = KnownZeroMask.logBase2();
 444         Value *In = ICI->getOperand(0);
 445         if (ShiftAmt) {
 446           // Perform a logical shr by shiftamt.
 447           // Insert the shift to put the result in the low bit.
 448           In = Builder->CreateLShr(In, ConstantInt::get(In->getType(),ShiftAmt),
 449                                    In->getName()+".lobit");
 450         }
 451
 452         if ((Op1CV != 0) == isNE) { // Toggle the low bit.
 453           Constant *One = ConstantInt::get(In->getType(), 1);
 454           In = Builder->CreateXor(In, One, "tmp");
 455         }
 456
 457         if (CI.getType() == In->getType())
 458           return ReplaceInstUsesWith(CI, In);
 459         else
 460           return CastInst::CreateIntegerCast(In, CI.getType(), false/*ZExt*/);
 461       }
 462     }
 463   }
 464
 465   // icmp ne A, B is equal to xor A, B when A and B only really have one bit.
 466   // It is also profitable to transform icmp eq into not(xor(A, B)) because that
 467   // may lead to additional simplifications.
 468   if (ICI->isEquality() && CI.getType() == ICI->getOperand(0)->getType()) {
 469     if (const IntegerType *ITy = dyn_cast<IntegerType>(CI.getType())) {
 470       uint32_t BitWidth = ITy->getBitWidth();
 471       Value *LHS = ICI->getOperand(0);
 472       Value *RHS = ICI->getOperand(1);
 473
 474       APInt KnownZeroLHS(BitWidth, 0), KnownOneLHS(BitWidth, 0);
 475       APInt KnownZeroRHS(BitWidth, 0), KnownOneRHS(BitWidth, 0);
 476       APInt TypeMask(APInt::getAllOnesValue(BitWidth));
 477       ComputeMaskedBits(LHS, TypeMask, KnownZeroLHS, KnownOneLHS);
 478       ComputeMaskedBits(RHS, TypeMask, KnownZeroRHS, KnownOneRHS);
 479
 480       if (KnownZeroLHS == KnownZeroRHS && KnownOneLHS == KnownOneRHS) {
 481         APInt KnownBits = KnownZeroLHS | KnownOneLHS;
 482         APInt UnknownBit = ~KnownBits;
 483         if (UnknownBit.countPopulation() == 1) {
 484           if (!DoXform) return ICI;
 485
 486           Value *Result = Builder->CreateXor(LHS, RHS);
 487
 488           // Mask off any bits that are set and won't be shifted away.
 489           if (KnownOneLHS.uge(UnknownBit))
 490             Result = Builder->CreateAnd(Result,
 491                                         ConstantInt::get(ITy, UnknownBit));
 492
 493           // Shift the bit we're testing down to the lsb.
 494           Result = Builder->CreateLShr(
 495                Result, ConstantInt::get(ITy, UnknownBit.countTrailingZeros()));
 496
 497           if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
 498             Result = Builder->CreateXor(Result, ConstantInt::get(ITy, 1));
 499           Result->takeName(ICI);
 500           return ReplaceInstUsesWith(CI, Result);
 501         }
 502       }
 503     }
 504   }
 505
 506   return 0;
 507 }
 508
 509 Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
 510   // If one of the common conversion will work, do it.
 511   if (Instruction *Result = commonIntCastTransforms(CI))
 512     return Result;
 513
 514   Value *Src = CI.getOperand(0);
 515
 516   // If this is a TRUNC followed by a ZEXT then we are dealing with integral
 517   // types and if the sizes are just right we can convert this into a logical
 518   // 'and' which will be much cheaper than the pair of casts.
 519   if (TruncInst *CSrc = dyn_cast<TruncInst>(Src)) {   // A->B->C cast
 520     // Get the sizes of the types involved.  We know that the intermediate type
 521     // will be smaller than A or C, but don't know the relation between A and C.
 522     Value *A = CSrc->getOperand(0);
 523     unsigned SrcSize = A->getType()->getScalarSizeInBits();
 524     unsigned MidSize = CSrc->getType()->getScalarSizeInBits();
 525     unsigned DstSize = CI.getType()->getScalarSizeInBits();
 526     // If we're actually extending zero bits, then if
 527     // SrcSize <  DstSize: zext(a & mask)
 528     // SrcSize == DstSize: a & mask
 529     // SrcSize  > DstSize: trunc(a) & mask
 530     if (SrcSize < DstSize) {
 531       APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize));
 532       Constant *AndConst = ConstantInt::get(A->getType(), AndValue);
 533       Value *And = Builder->CreateAnd(A, AndConst, CSrc->getName()+".mask");
 534       return new ZExtInst(And, CI.getType());
 535     }
 536
 537     if (SrcSize == DstSize) {
 538       APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize));
 539       return BinaryOperator::CreateAnd(A, ConstantInt::get(A->getType(),
 540                                                            AndValue));
 541     }
 542     if (SrcSize > DstSize) {
 543       Value *Trunc = Builder->CreateTrunc(A, CI.getType(), "tmp");
 544       APInt AndValue(APInt::getLowBitsSet(DstSize, MidSize));
 545       return BinaryOperator::CreateAnd(Trunc,
 546                                        ConstantInt::get(Trunc->getType(),
 547                                                                AndValue));
 548     }
 549   }
 550
 551   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src))
 552     return transformZExtICmp(ICI, CI);
 553
 554   BinaryOperator *SrcI = dyn_cast<BinaryOperator>(Src);
 555   if (SrcI && SrcI->getOpcode() == Instruction::Or) {
 556     // zext (or icmp, icmp) --> or (zext icmp), (zext icmp) if at least one
 557     // of the (zext icmp) will be transformed.
 558     ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0));
 559     ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1));
 560     if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() &&
 561         (transformZExtICmp(LHS, CI, false) ||
 562          transformZExtICmp(RHS, CI, false))) {
 563       Value *LCast = Builder->CreateZExt(LHS, CI.getType(), LHS->getName());
 564       Value *RCast = Builder->CreateZExt(RHS, CI.getType(), RHS->getName());
 565       return BinaryOperator::Create(Instruction::Or, LCast, RCast);
 566     }
 567   }
 568
 569   // zext(trunc(t) & C) -> (t & zext(C)).
 570   if (SrcI && SrcI->getOpcode() == Instruction::And && SrcI->hasOneUse())
 571     if (ConstantInt *C = dyn_cast<ConstantInt>(SrcI->getOperand(1)))
 572       if (TruncInst *TI = dyn_cast<TruncInst>(SrcI->getOperand(0))) {
 573         Value *TI0 = TI->getOperand(0);
 574         if (TI0->getType() == CI.getType())
 575           return
 576             BinaryOperator::CreateAnd(TI0,
 577                                 ConstantExpr::getZExt(C, CI.getType()));
 578       }
 579
 580   // zext((trunc(t) & C) ^ C) -> ((t & zext(C)) ^ zext(C)).
 581   if (SrcI && SrcI->getOpcode() == Instruction::Xor && SrcI->hasOneUse())
 582     if (ConstantInt *C = dyn_cast<ConstantInt>(SrcI->getOperand(1)))
 583       if (BinaryOperator *And = dyn_cast<BinaryOperator>(SrcI->getOperand(0)))
 584         if (And->getOpcode() == Instruction::And && And->hasOneUse() &&
 585             And->getOperand(1) == C)
 586           if (TruncInst *TI = dyn_cast<TruncInst>(And->getOperand(0))) {
 587             Value *TI0 = TI->getOperand(0);
 588             if (TI0->getType() == CI.getType()) {
 589               Constant *ZC = ConstantExpr::getZExt(C, CI.getType());
 590               Value *NewAnd = Builder->CreateAnd(TI0, ZC, "tmp");
 591               return BinaryOperator::CreateXor(NewAnd, ZC);
 592             }
 593           }
 594
 595   return 0;
 596 }
 597
 598 Instruction *InstCombiner::visitSExt(SExtInst &CI) {
 599   if (Instruction *I = commonIntCastTransforms(CI))
 600     return I;
 601
 602   Value *Src = CI.getOperand(0);
 603
 604   // Canonicalize sign-extend from i1 to a select.
 605   if (Src->getType() == Type::getInt1Ty(CI.getContext()))
 606     return SelectInst::Create(Src,
 607                               Constant::getAllOnesValue(CI.getType()),
 608                               Constant::getNullValue(CI.getType()));
 609
 610   // See if the value being truncated is already sign extended.  If so, just
 611   // eliminate the trunc/sext pair.
 612   if (Operator::getOpcode(Src) == Instruction::Trunc) {
 613     Value *Op = cast<User>(Src)->getOperand(0);
 614     unsigned OpBits   = Op->getType()->getScalarSizeInBits();
 615     unsigned MidBits  = Src->getType()->getScalarSizeInBits();
 616     unsigned DestBits = CI.getType()->getScalarSizeInBits();
 617     unsigned NumSignBits = ComputeNumSignBits(Op);
 618
 619     if (OpBits == DestBits) {
 620       // Op is i32, Mid is i8, and Dest is i32.  If Op has more than 24 sign
 621       // bits, it is already ready.
 622       if (NumSignBits > DestBits-MidBits)
 623         return ReplaceInstUsesWith(CI, Op);
 624     } else if (OpBits < DestBits) {
 625       // Op is i32, Mid is i8, and Dest is i64.  If Op has more than 24 sign
 626       // bits, just sext from i32.
 627       if (NumSignBits > OpBits-MidBits)
 628         return new SExtInst(Op, CI.getType(), "tmp");
 629     } else {
 630       // Op is i64, Mid is i8, and Dest is i32.  If Op has more than 56 sign
 631       // bits, just truncate to i32.
 632       if (NumSignBits > OpBits-MidBits)
 633         return new TruncInst(Op, CI.getType(), "tmp");
 634     }
 635   }
 636
 637   // If the input is a shl/ashr pair of a same constant, then this is a sign
 638   // extension from a smaller value.  If we could trust arbitrary bitwidth
 639   // integers, we could turn this into a truncate to the smaller bit and then
 640   // use a sext for the whole extension.  Since we don't, look deeper and check
 641   // for a truncate.  If the source and dest are the same type, eliminate the
 642   // trunc and extend and just do shifts.  For example, turn:
 643   //   %a = trunc i32 %i to i8
 644   //   %b = shl i8 %a, 6
 645   //   %c = ashr i8 %b, 6
 646   //   %d = sext i8 %c to i32
 647   // into:
 648   //   %a = shl i32 %i, 30
 649   //   %d = ashr i32 %a, 30
 650   Value *A = 0;
 651   ConstantInt *BA = 0, *CA = 0;
 652   if (match(Src, m_AShr(m_Shl(m_Value(A), m_ConstantInt(BA)),
 653                         m_ConstantInt(CA))) &&
 654       BA == CA && isa<TruncInst>(A)) {
 655     Value *I = cast<TruncInst>(A)->getOperand(0);
 656     if (I->getType() == CI.getType()) {
 657       unsigned MidSize = Src->getType()->getScalarSizeInBits();
 658       unsigned SrcDstSize = CI.getType()->getScalarSizeInBits();
 659       unsigned ShAmt = CA->getZExtValue()+SrcDstSize-MidSize;
 660       Constant *ShAmtV = ConstantInt::get(CI.getType(), ShAmt);
 661       I = Builder->CreateShl(I, ShAmtV, CI.getName());
 662       return BinaryOperator::CreateAShr(I, ShAmtV);
 663     }
 664   }
 665
 666   return 0;
 667 }
 668
 669
 670 /// FitsInFPType - Return a Constant* for the specified FP constant if it fits
 671 /// in the specified FP type without changing its value.
 672 static Constant *FitsInFPType(ConstantFP *CFP, const fltSemantics &Sem) {
 673   bool losesInfo;
 674   APFloat F = CFP->getValueAPF();
 675   (void)F.convert(Sem, APFloat::rmNearestTiesToEven, &losesInfo);
 676   if (!losesInfo)
 677     return ConstantFP::get(CFP->getContext(), F);
 678   return 0;
 679 }
 680
 681 /// LookThroughFPExtensions - If this is an fp extension instruction, look
 682 /// through it until we get the source value.
 683 static Value *LookThroughFPExtensions(Value *V) {
 684   if (Instruction *I = dyn_cast<Instruction>(V))
 685     if (I->getOpcode() == Instruction::FPExt)
 686       return LookThroughFPExtensions(I->getOperand(0));
 687
 688   // If this value is a constant, return the constant in the smallest FP type
 689   // that can accurately represent it.  This allows us to turn
 690   // (float)((double)X+2.0) into x+2.0f.
 691   if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
 692     if (CFP->getType() == Type::getPPC_FP128Ty(V->getContext()))
 693       return V;  // No constant folding of this.
 694     // See if the value can be truncated to float and then reextended.
 695     if (Value *V = FitsInFPType(CFP, APFloat::IEEEsingle))
 696       return V;
 697     if (CFP->getType() == Type::getDoubleTy(V->getContext()))
 698       return V;  // Won't shrink.
 699     if (Value *V = FitsInFPType(CFP, APFloat::IEEEdouble))
 700       return V;
 701     // Don't try to shrink to various long double types.
 702   }
 703
 704   return V;
 705 }
 706
 707 Instruction *InstCombiner::visitFPTrunc(FPTruncInst &CI) {
 708   if (Instruction *I = commonCastTransforms(CI))
 709     return I;
 710
 711   // If we have fptrunc(fadd (fpextend x), (fpextend y)), where x and y are
 712   // smaller than the destination type, we can eliminate the truncate by doing
 713   // the add as the smaller type.  This applies to fadd/fsub/fmul/fdiv as well
 714   // as many builtins (sqrt, etc).
 715   BinaryOperator *OpI = dyn_cast<BinaryOperator>(CI.getOperand(0));
 716   if (OpI && OpI->hasOneUse()) {
 717     switch (OpI->getOpcode()) {
 718     default: break;
 719     case Instruction::FAdd:
 720     case Instruction::FSub:
 721     case Instruction::FMul:
 722     case Instruction::FDiv:
 723     case Instruction::FRem:
 724       const Type *SrcTy = OpI->getType();
 725       Value *LHSTrunc = LookThroughFPExtensions(OpI->getOperand(0));
 726       Value *RHSTrunc = LookThroughFPExtensions(OpI->getOperand(1));
 727       if (LHSTrunc->getType() != SrcTy &&
 728           RHSTrunc->getType() != SrcTy) {
 729         unsigned DstSize = CI.getType()->getScalarSizeInBits();
 730         // If the source types were both smaller than the destination type of
 731         // the cast, do this xform.
 732         if (LHSTrunc->getType()->getScalarSizeInBits() <= DstSize &&
 733             RHSTrunc->getType()->getScalarSizeInBits() <= DstSize) {
 734           LHSTrunc = Builder->CreateFPExt(LHSTrunc, CI.getType());
 735           RHSTrunc = Builder->CreateFPExt(RHSTrunc, CI.getType());
 736           return BinaryOperator::Create(OpI->getOpcode(), LHSTrunc, RHSTrunc);
 737         }
 738       }
 739       break;
 740     }
 741   }
 742   return 0;
 743 }
 744
 745 Instruction *InstCombiner::visitFPExt(CastInst &CI) {
 746   return commonCastTransforms(CI);
 747 }
 748
 749 Instruction *InstCombiner::visitFPToUI(FPToUIInst &FI) {
 750   Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0));
 751   if (OpI == 0)
 752     return commonCastTransforms(FI);
 753
 754   // fptoui(uitofp(X)) --> X
 755   // fptoui(sitofp(X)) --> X
 756   // This is safe if the intermediate type has enough bits in its mantissa to
 757   // accurately represent all values of X.  For example, do not do this with
 758   // i64->float->i64.  This is also safe for sitofp case, because any negative
 759   // 'X' value would cause an undefined result for the fptoui.
 760   if ((isa<UIToFPInst>(OpI) || isa<SIToFPInst>(OpI)) &&
 761       OpI->getOperand(0)->getType() == FI.getType() &&
 762       (int)FI.getType()->getScalarSizeInBits() < /*extra bit for sign */
 763                     OpI->getType()->getFPMantissaWidth())
 764     return ReplaceInstUsesWith(FI, OpI->getOperand(0));
 765
 766   return commonCastTransforms(FI);
 767 }
 768
 769 Instruction *InstCombiner::visitFPToSI(FPToSIInst &FI) {
 770   Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0));
 771   if (OpI == 0)
 772     return commonCastTransforms(FI);
 773
 774   // fptosi(sitofp(X)) --> X
 775   // fptosi(uitofp(X)) --> X
 776   // This is safe if the intermediate type has enough bits in its mantissa to
 777   // accurately represent all values of X.  For example, do not do this with
 778   // i64->float->i64.  This is also safe for sitofp case, because any negative
 779   // 'X' value would cause an undefined result for the fptoui.
 780   if ((isa<UIToFPInst>(OpI) || isa<SIToFPInst>(OpI)) &&
 781       OpI->getOperand(0)->getType() == FI.getType() &&
 782       (int)FI.getType()->getScalarSizeInBits() <=
 783                     OpI->getType()->getFPMantissaWidth())
 784     return ReplaceInstUsesWith(FI, OpI->getOperand(0));
 785
 786   return commonCastTransforms(FI);
 787 }
 788
 789 Instruction *InstCombiner::visitUIToFP(CastInst &CI) {
 790   return commonCastTransforms(CI);
 791 }
 792
 793 Instruction *InstCombiner::visitSIToFP(CastInst &CI) {
 794   return commonCastTransforms(CI);
 795 }
 796
 797 Instruction *InstCombiner::visitPtrToInt(PtrToIntInst &CI) {
 798   // If the destination integer type is smaller than the intptr_t type for
 799   // this target, do a ptrtoint to intptr_t then do a trunc.  This allows the
 800   // trunc to be exposed to other transforms.  Don't do this for extending
 801   // ptrtoint's, because we don't know if the target sign or zero extends its
 802   // pointers.
 803   if (TD &&
 804       CI.getType()->getScalarSizeInBits() < TD->getPointerSizeInBits()) {
 805     Value *P = Builder->CreatePtrToInt(CI.getOperand(0),
 806                                        TD->getIntPtrType(CI.getContext()),
 807                                        "tmp");
 808     return new TruncInst(P, CI.getType());
 809   }
 810
 811   return commonPointerCastTransforms(CI);
 812 }
 813
 814
 815 Instruction *InstCombiner::visitIntToPtr(IntToPtrInst &CI) {
 816   // If the source integer type is larger than the intptr_t type for
 817   // this target, do a trunc to the intptr_t type, then inttoptr of it.  This
 818   // allows the trunc to be exposed to other transforms.  Don't do this for
 819   // extending inttoptr's, because we don't know if the target sign or zero
 820   // extends to pointers.
 821   if (TD && CI.getOperand(0)->getType()->getScalarSizeInBits() >
 822       TD->getPointerSizeInBits()) {
 823     Value *P = Builder->CreateTrunc(CI.getOperand(0),
 824                                     TD->getIntPtrType(CI.getContext()), "tmp");
 825     return new IntToPtrInst(P, CI.getType());
 826   }
 827
 828   if (Instruction *I = commonCastTransforms(CI))
 829     return I;
 830
 831   return 0;
 832 }
 833
 834 Instruction *InstCombiner::visitBitCast(BitCastInst &CI) {
 835   // If the operands are integer typed then apply the integer transforms,
 836   // otherwise just apply the common ones.
 837   Value *Src = CI.getOperand(0);
 838   const Type *SrcTy = Src->getType();
 839   const Type *DestTy = CI.getType();
 840
 841   if (isa<PointerType>(SrcTy)) {
 842     if (Instruction *I = commonPointerCastTransforms(CI))
 843       return I;
 844   } else {
 845     if (Instruction *Result = commonCastTransforms(CI))
 846       return Result;
 847   }
 848
 849
 850   // Get rid of casts from one type to the same type. These are useless and can
 851   // be replaced by the operand.
 852   if (DestTy == Src->getType())
 853     return ReplaceInstUsesWith(CI, Src);
 854
 855   if (const PointerType *DstPTy = dyn_cast<PointerType>(DestTy)) {
 856     const PointerType *SrcPTy = cast<PointerType>(SrcTy);
 857     const Type *DstElTy = DstPTy->getElementType();
 858     const Type *SrcElTy = SrcPTy->getElementType();
 859
 860     // If the address spaces don't match, don't eliminate the bitcast, which is
 861     // required for changing types.
 862     if (SrcPTy->getAddressSpace() != DstPTy->getAddressSpace())
 863       return 0;
 864
 865     // If we are casting a alloca to a pointer to a type of the same
 866     // size, rewrite the allocation instruction to allocate the "right" type.
 867     // There is no need to modify malloc calls because it is their bitcast that
 868     // needs to be cleaned up.
 869     if (AllocaInst *AI = dyn_cast<AllocaInst>(Src))
 870       if (Instruction *V = PromoteCastOfAllocation(CI, *AI))
 871         return V;
 872
 873     // If the source and destination are pointers, and this cast is equivalent
 874     // to a getelementptr X, 0, 0, 0...  turn it into the appropriate gep.
 875     // This can enhance SROA and other transforms that want type-safe pointers.
 876     Constant *ZeroUInt =
 877       Constant::getNullValue(Type::getInt32Ty(CI.getContext()));
 878     unsigned NumZeros = 0;
 879     while (SrcElTy != DstElTy &&
 880            isa<CompositeType>(SrcElTy) && !isa<PointerType>(SrcElTy) &&
 881            SrcElTy->getNumContainedTypes() /* not "{}" */) {
 882       SrcElTy = cast<CompositeType>(SrcElTy)->getTypeAtIndex(ZeroUInt);
 883       ++NumZeros;
 884     }
 885
 886     // If we found a path from the src to dest, create the getelementptr now.
 887     if (SrcElTy == DstElTy) {
 888       SmallVector<Value*, 8> Idxs(NumZeros+1, ZeroUInt);
 889       return GetElementPtrInst::CreateInBounds(Src, Idxs.begin(), Idxs.end(),"",
 890                                                ((Instruction*) NULL));
 891     }
 892   }
 893
 894   if (const VectorType *DestVTy = dyn_cast<VectorType>(DestTy)) {
 895     if (DestVTy->getNumElements() == 1) {
 896       if (!isa<VectorType>(SrcTy)) {
 897         Value *Elem = Builder->CreateBitCast(Src, DestVTy->getElementType());
 898         return InsertElementInst::Create(UndefValue::get(DestTy), Elem,
 899                      Constant::getNullValue(Type::getInt32Ty(CI.getContext())));
 900       }
 901       // FIXME: Canonicalize bitcast(insertelement) -> insertelement(bitcast)
 902     }
 903   }
 904
 905   if (const VectorType *SrcVTy = dyn_cast<VectorType>(SrcTy)) {
 906     if (SrcVTy->getNumElements() == 1) {
 907       if (!isa<VectorType>(DestTy)) {
 908         Value *Elem =
 909           Builder->CreateExtractElement(Src,
 910                      Constant::getNullValue(Type::getInt32Ty(CI.getContext())));
 911         return CastInst::Create(Instruction::BitCast, Elem, DestTy);
 912       }
 913     }
 914   }
 915
 916   if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(Src)) {
 917     if (SVI->hasOneUse()) {
 918       // Okay, we have (bitconvert (shuffle ..)).  Check to see if this is
 919       // a bitconvert to a vector with the same # elts.
 920       if (isa<VectorType>(DestTy) &&
 921           cast<VectorType>(DestTy)->getNumElements() ==
 922                 SVI->getType()->getNumElements() &&
 923           SVI->getType()->getNumElements() ==
 924             cast<VectorType>(SVI->getOperand(0)->getType())->getNumElements()) {
 925         CastInst *Tmp;
 926         // If either of the operands is a cast from CI.getType(), then
 927         // evaluating the shuffle in the casted destination's type will allow
 928         // us to eliminate at least one cast.
 929         if (((Tmp = dyn_cast<CastInst>(SVI->getOperand(0))) &&
 930              Tmp->getOperand(0)->getType() == DestTy) ||
 931             ((Tmp = dyn_cast<CastInst>(SVI->getOperand(1))) &&
 932              Tmp->getOperand(0)->getType() == DestTy)) {
 933           Value *LHS = Builder->CreateBitCast(SVI->getOperand(0), DestTy);
 934           Value *RHS = Builder->CreateBitCast(SVI->getOperand(1), DestTy);
 935           // Return a new shuffle vector.  Use the same element ID's, as we
 936           // know the vector types match #elts.
 937           return new ShuffleVectorInst(LHS, RHS, SVI->getOperand(2));
 938         }
 939       }
 940     }
 941   }
 942   return 0;
 943 }