1202375Srdivacky//===- InstCombineCasts.cpp -----------------------------------------------===// 2202375Srdivacky// 3202375Srdivacky// The LLVM Compiler Infrastructure 4202375Srdivacky// 5202375Srdivacky// This file is distributed under the University of Illinois Open Source 6202375Srdivacky// License. See LICENSE.TXT for details. 7202375Srdivacky// 8202375Srdivacky//===----------------------------------------------------------------------===// 9202375Srdivacky// 10202375Srdivacky// This file implements the visit functions for cast operations. 11202375Srdivacky// 12202375Srdivacky//===----------------------------------------------------------------------===// 13202375Srdivacky 14202375Srdivacky#include "InstCombine.h" 15226633Sdim#include "llvm/Analysis/ConstantFolding.h" 16249423Sdim#include "llvm/IR/DataLayout.h" 17249423Sdim#include "llvm/Support/PatternMatch.h" 18234353Sdim#include "llvm/Target/TargetLibraryInfo.h" 19202375Srdivackyusing namespace llvm; 20202375Srdivackyusing namespace PatternMatch; 21202375Srdivacky 22202375Srdivacky/// DecomposeSimpleLinearExpr - Analyze 'Val', seeing if it is a simple linear 23202375Srdivacky/// expression. If so, decompose it, returning some value X, such that Val is 24202375Srdivacky/// X*Scale+Offset. 25202375Srdivacky/// 26202375Srdivackystatic Value *DecomposeSimpleLinearExpr(Value *Val, unsigned &Scale, 27210299Sed uint64_t &Offset) { 28202375Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) { 29202375Srdivacky Offset = CI->getZExtValue(); 30202375Srdivacky Scale = 0; 31210299Sed return ConstantInt::get(Val->getType(), 0); 32202375Srdivacky } 33249423Sdim 34202375Srdivacky if (BinaryOperator *I = dyn_cast<BinaryOperator>(Val)) { 35224145Sdim // Cannot look past anything that might overflow. 36224145Sdim OverflowingBinaryOperator *OBI = dyn_cast<OverflowingBinaryOperator>(Val); 37239462Sdim if (OBI && !OBI->hasNoUnsignedWrap() && !OBI->hasNoSignedWrap()) { 38224145Sdim Scale = 1; 39224145Sdim Offset = 0; 40224145Sdim return Val; 41224145Sdim } 42224145Sdim 43202375Srdivacky if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) { 44202375Srdivacky if (I->getOpcode() == Instruction::Shl) { 45202375Srdivacky // This is a value scaled by '1 << the shift amt'. 46210299Sed Scale = UINT64_C(1) << RHS->getZExtValue(); 47202375Srdivacky Offset = 0; 48202375Srdivacky return I->getOperand(0); 49202375Srdivacky } 50249423Sdim 51202375Srdivacky if (I->getOpcode() == Instruction::Mul) { 52202375Srdivacky // This value is scaled by 'RHS'. 53202375Srdivacky Scale = RHS->getZExtValue(); 54202375Srdivacky Offset = 0; 55202375Srdivacky return I->getOperand(0); 56202375Srdivacky } 57249423Sdim 58202375Srdivacky if (I->getOpcode() == Instruction::Add) { 59249423Sdim // We have X+C. Check to see if we really have (X*C2)+C1, 60202375Srdivacky // where C1 is divisible by C2. 61202375Srdivacky unsigned SubScale; 62249423Sdim Value *SubVal = 63202375Srdivacky DecomposeSimpleLinearExpr(I->getOperand(0), SubScale, Offset); 64202375Srdivacky Offset += RHS->getZExtValue(); 65202375Srdivacky Scale = SubScale; 66202375Srdivacky return SubVal; 67202375Srdivacky } 68202375Srdivacky } 69202375Srdivacky } 70202375Srdivacky 71202375Srdivacky // Otherwise, we can't look past this. 72202375Srdivacky Scale = 1; 73202375Srdivacky Offset = 0; 74202375Srdivacky return Val; 75202375Srdivacky} 76202375Srdivacky 77202375Srdivacky/// PromoteCastOfAllocation - If we find a cast of an allocation instruction, 78202375Srdivacky/// try to eliminate the cast by moving the type information into the alloc. 79202375SrdivackyInstruction *InstCombiner::PromoteCastOfAllocation(BitCastInst &CI, 80202375Srdivacky AllocaInst &AI) { 81243830Sdim // This requires DataLayout to get the alloca alignment and size information. 82202375Srdivacky if (!TD) return 0; 83202375Srdivacky 84226633Sdim PointerType *PTy = cast<PointerType>(CI.getType()); 85249423Sdim 86202375Srdivacky BuilderTy AllocaBuilder(*Builder); 87202375Srdivacky AllocaBuilder.SetInsertPoint(AI.getParent(), &AI); 88202375Srdivacky 89202375Srdivacky // Get the type really allocated and the type casted to. 90226633Sdim Type *AllocElTy = AI.getAllocatedType(); 91226633Sdim Type *CastElTy = PTy->getElementType(); 92202375Srdivacky if (!AllocElTy->isSized() || !CastElTy->isSized()) return 0; 93202375Srdivacky 94202375Srdivacky unsigned AllocElTyAlign = TD->getABITypeAlignment(AllocElTy); 95202375Srdivacky unsigned CastElTyAlign = TD->getABITypeAlignment(CastElTy); 96202375Srdivacky if (CastElTyAlign < AllocElTyAlign) return 0; 97202375Srdivacky 98202375Srdivacky // If the allocation has multiple uses, only promote it if we are strictly 99202375Srdivacky // increasing the alignment of the resultant allocation. If we keep it the 100221345Sdim // same, we open the door to infinite loops of various kinds. 101221345Sdim if (!AI.hasOneUse() && CastElTyAlign == AllocElTyAlign) return 0; 102202375Srdivacky 103202375Srdivacky uint64_t AllocElTySize = TD->getTypeAllocSize(AllocElTy); 104202375Srdivacky uint64_t CastElTySize = TD->getTypeAllocSize(CastElTy); 105202375Srdivacky if (CastElTySize == 0 || AllocElTySize == 0) return 0; 106202375Srdivacky 107249423Sdim // If the allocation has multiple uses, only promote it if we're not 108249423Sdim // shrinking the amount of memory being allocated. 109249423Sdim uint64_t AllocElTyStoreSize = TD->getTypeStoreSize(AllocElTy); 110249423Sdim uint64_t CastElTyStoreSize = TD->getTypeStoreSize(CastElTy); 111249423Sdim if (!AI.hasOneUse() && CastElTyStoreSize < AllocElTyStoreSize) return 0; 112249423Sdim 113202375Srdivacky // See if we can satisfy the modulus by pulling a scale out of the array 114202375Srdivacky // size argument. 115202375Srdivacky unsigned ArraySizeScale; 116210299Sed uint64_t ArrayOffset; 117202375Srdivacky Value *NumElements = // See if the array size is a decomposable linear expr. 118202375Srdivacky DecomposeSimpleLinearExpr(AI.getOperand(0), ArraySizeScale, ArrayOffset); 119249423Sdim 120202375Srdivacky // If we can now satisfy the modulus, by using a non-1 scale, we really can 121202375Srdivacky // do the xform. 122202375Srdivacky if ((AllocElTySize*ArraySizeScale) % CastElTySize != 0 || 123202375Srdivacky (AllocElTySize*ArrayOffset ) % CastElTySize != 0) return 0; 124202375Srdivacky 125202375Srdivacky unsigned Scale = (AllocElTySize*ArraySizeScale)/CastElTySize; 126202375Srdivacky Value *Amt = 0; 127202375Srdivacky if (Scale == 1) { 128202375Srdivacky Amt = NumElements; 129202375Srdivacky } else { 130210299Sed Amt = ConstantInt::get(AI.getArraySize()->getType(), Scale); 131202375Srdivacky // Insert before the alloca, not before the cast. 132226633Sdim Amt = AllocaBuilder.CreateMul(Amt, NumElements); 133202375Srdivacky } 134249423Sdim 135210299Sed if (uint64_t Offset = (AllocElTySize*ArrayOffset)/CastElTySize) { 136210299Sed Value *Off = ConstantInt::get(AI.getArraySize()->getType(), 137202375Srdivacky Offset, true); 138226633Sdim Amt = AllocaBuilder.CreateAdd(Amt, Off); 139202375Srdivacky } 140249423Sdim 141202375Srdivacky AllocaInst *New = AllocaBuilder.CreateAlloca(CastElTy, Amt); 142202375Srdivacky New->setAlignment(AI.getAlignment()); 143202375Srdivacky New->takeName(&AI); 144249423Sdim 145202375Srdivacky // If the allocation has multiple real uses, insert a cast and change all 146202375Srdivacky // things that used it to use the new cast. This will also hack on CI, but it 147202375Srdivacky // will die soon. 148221345Sdim if (!AI.hasOneUse()) { 149202375Srdivacky // New is the allocation instruction, pointer typed. AI is the original 150202375Srdivacky // allocation instruction, also pointer typed. Thus, cast to use is BitCast. 151202375Srdivacky Value *NewCast = AllocaBuilder.CreateBitCast(New, AI.getType(), "tmpcast"); 152223017Sdim ReplaceInstUsesWith(AI, NewCast); 153202375Srdivacky } 154202375Srdivacky return ReplaceInstUsesWith(CI, New); 155202375Srdivacky} 156202375Srdivacky 157249423Sdim/// EvaluateInDifferentType - Given an expression that 158202375Srdivacky/// CanEvaluateTruncated or CanEvaluateSExtd returns true for, actually 159202375Srdivacky/// insert the code to evaluate the expression. 160249423SdimValue *InstCombiner::EvaluateInDifferentType(Value *V, Type *Ty, 161202375Srdivacky bool isSigned) { 162202375Srdivacky if (Constant *C = dyn_cast<Constant>(V)) { 163202375Srdivacky C = ConstantExpr::getIntegerCast(C, Ty, isSigned /*Sext or ZExt*/); 164202375Srdivacky // If we got a constantexpr back, try to simplify it with TD info. 165202375Srdivacky if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 166234353Sdim C = ConstantFoldConstantExpression(CE, TD, TLI); 167202375Srdivacky return C; 168202375Srdivacky } 169202375Srdivacky 170202375Srdivacky // Otherwise, it must be an instruction. 171202375Srdivacky Instruction *I = cast<Instruction>(V); 172202375Srdivacky Instruction *Res = 0; 173202375Srdivacky unsigned Opc = I->getOpcode(); 174202375Srdivacky switch (Opc) { 175202375Srdivacky case Instruction::Add: 176202375Srdivacky case Instruction::Sub: 177202375Srdivacky case Instruction::Mul: 178202375Srdivacky case Instruction::And: 179202375Srdivacky case Instruction::Or: 180202375Srdivacky case Instruction::Xor: 181202375Srdivacky case Instruction::AShr: 182202375Srdivacky case Instruction::LShr: 183202375Srdivacky case Instruction::Shl: 184202375Srdivacky case Instruction::UDiv: 185202375Srdivacky case Instruction::URem: { 186202375Srdivacky Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned); 187202375Srdivacky Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned); 188202375Srdivacky Res = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS); 189202375Srdivacky break; 190249423Sdim } 191202375Srdivacky case Instruction::Trunc: 192202375Srdivacky case Instruction::ZExt: 193202375Srdivacky case Instruction::SExt: 194202375Srdivacky // If the source type of the cast is the type we're trying for then we can 195202375Srdivacky // just return the source. There's no need to insert it because it is not 196202375Srdivacky // new. 197202375Srdivacky if (I->getOperand(0)->getType() == Ty) 198202375Srdivacky return I->getOperand(0); 199249423Sdim 200202375Srdivacky // Otherwise, must be the same type of cast, so just reinsert a new one. 201202375Srdivacky // This also handles the case of zext(trunc(x)) -> zext(x). 202202375Srdivacky Res = CastInst::CreateIntegerCast(I->getOperand(0), Ty, 203202375Srdivacky Opc == Instruction::SExt); 204202375Srdivacky break; 205202375Srdivacky case Instruction::Select: { 206202375Srdivacky Value *True = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned); 207202375Srdivacky Value *False = EvaluateInDifferentType(I->getOperand(2), Ty, isSigned); 208202375Srdivacky Res = SelectInst::Create(I->getOperand(0), True, False); 209202375Srdivacky break; 210202375Srdivacky } 211202375Srdivacky case Instruction::PHI: { 212202375Srdivacky PHINode *OPN = cast<PHINode>(I); 213221345Sdim PHINode *NPN = PHINode::Create(Ty, OPN->getNumIncomingValues()); 214202375Srdivacky for (unsigned i = 0, e = OPN->getNumIncomingValues(); i != e; ++i) { 215202375Srdivacky Value *V =EvaluateInDifferentType(OPN->getIncomingValue(i), Ty, isSigned); 216202375Srdivacky NPN->addIncoming(V, OPN->getIncomingBlock(i)); 217202375Srdivacky } 218202375Srdivacky Res = NPN; 219202375Srdivacky break; 220202375Srdivacky } 221249423Sdim default: 222202375Srdivacky // TODO: Can handle more cases here. 223202375Srdivacky llvm_unreachable("Unreachable!"); 224202375Srdivacky } 225249423Sdim 226202375Srdivacky Res->takeName(I); 227223017Sdim return InsertNewInstWith(Res, *I); 228202375Srdivacky} 229202375Srdivacky 230202375Srdivacky 231202375Srdivacky/// This function is a wrapper around CastInst::isEliminableCastPair. It 232202375Srdivacky/// simply extracts arguments and returns what that function returns. 233249423Sdimstatic Instruction::CastOps 234202375SrdivackyisEliminableCastPair( 235202375Srdivacky const CastInst *CI, ///< The first cast instruction 236202375Srdivacky unsigned opcode, ///< The opcode of the second cast instruction 237226633Sdim Type *DstTy, ///< The target type for the second cast instruction 238243830Sdim DataLayout *TD ///< The target data for pointer size 239202375Srdivacky) { 240202375Srdivacky 241226633Sdim Type *SrcTy = CI->getOperand(0)->getType(); // A from above 242226633Sdim Type *MidTy = CI->getType(); // B from above 243202375Srdivacky 244202375Srdivacky // Get the opcodes of the two Cast instructions 245202375Srdivacky Instruction::CastOps firstOp = Instruction::CastOps(CI->getOpcode()); 246202375Srdivacky Instruction::CastOps secondOp = Instruction::CastOps(opcode); 247243830Sdim Type *SrcIntPtrTy = TD && SrcTy->isPtrOrPtrVectorTy() ? 248243830Sdim TD->getIntPtrType(SrcTy) : 0; 249243830Sdim Type *MidIntPtrTy = TD && MidTy->isPtrOrPtrVectorTy() ? 250243830Sdim TD->getIntPtrType(MidTy) : 0; 251243830Sdim Type *DstIntPtrTy = TD && DstTy->isPtrOrPtrVectorTy() ? 252243830Sdim TD->getIntPtrType(DstTy) : 0; 253243830Sdim unsigned Res = CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, 254243830Sdim DstTy, SrcIntPtrTy, MidIntPtrTy, 255243830Sdim DstIntPtrTy); 256202375Srdivacky 257202375Srdivacky // We don't want to form an inttoptr or ptrtoint that converts to an integer 258202375Srdivacky // type that differs from the pointer size. 259243830Sdim if ((Res == Instruction::IntToPtr && SrcTy != DstIntPtrTy) || 260243830Sdim (Res == Instruction::PtrToInt && DstTy != SrcIntPtrTy)) 261202375Srdivacky Res = 0; 262249423Sdim 263202375Srdivacky return Instruction::CastOps(Res); 264202375Srdivacky} 265202375Srdivacky 266203954Srdivacky/// ShouldOptimizeCast - Return true if the cast from "V to Ty" actually 267203954Srdivacky/// results in any code being generated and is interesting to optimize out. If 268203954Srdivacky/// the cast can be eliminated by some other simple transformation, we prefer 269203954Srdivacky/// to do the simplification first. 270203954Srdivackybool InstCombiner::ShouldOptimizeCast(Instruction::CastOps opc, const Value *V, 271226633Sdim Type *Ty) { 272203954Srdivacky // Noop casts and casts of constants should be eliminated trivially. 273202375Srdivacky if (V->getType() == Ty || isa<Constant>(V)) return false; 274249423Sdim 275203954Srdivacky // If this is another cast that can be eliminated, we prefer to have it 276203954Srdivacky // eliminated. 277202375Srdivacky if (const CastInst *CI = dyn_cast<CastInst>(V)) 278203954Srdivacky if (isEliminableCastPair(CI, opc, Ty, TD)) 279202375Srdivacky return false; 280249423Sdim 281203954Srdivacky // If this is a vector sext from a compare, then we don't want to break the 282203954Srdivacky // idiom where each element of the extended vector is either zero or all ones. 283204642Srdivacky if (opc == Instruction::SExt && isa<CmpInst>(V) && Ty->isVectorTy()) 284203954Srdivacky return false; 285249423Sdim 286202375Srdivacky return true; 287202375Srdivacky} 288202375Srdivacky 289202375Srdivacky 290202375Srdivacky/// @brief Implement the transforms common to all CastInst visitors. 291202375SrdivackyInstruction *InstCombiner::commonCastTransforms(CastInst &CI) { 292202375Srdivacky Value *Src = CI.getOperand(0); 293202375Srdivacky 294202375Srdivacky // Many cases of "cast of a cast" are eliminable. If it's eliminable we just 295202375Srdivacky // eliminate it now. 296202375Srdivacky if (CastInst *CSrc = dyn_cast<CastInst>(Src)) { // A->B->C cast 297249423Sdim if (Instruction::CastOps opc = 298202375Srdivacky isEliminableCastPair(CSrc, CI.getOpcode(), CI.getType(), TD)) { 299202375Srdivacky // The first cast (CSrc) is eliminable so we need to fix up or replace 300202375Srdivacky // the second cast (CI). CSrc will then have a good chance of being dead. 301202375Srdivacky return CastInst::Create(opc, CSrc->getOperand(0), CI.getType()); 302202375Srdivacky } 303202375Srdivacky } 304202375Srdivacky 305202375Srdivacky // If we are casting a select then fold the cast into the select 306202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Src)) 307202375Srdivacky if (Instruction *NV = FoldOpIntoSelect(CI, SI)) 308202375Srdivacky return NV; 309202375Srdivacky 310202375Srdivacky // If we are casting a PHI then fold the cast into the PHI 311202375Srdivacky if (isa<PHINode>(Src)) { 312202375Srdivacky // We don't do this if this would create a PHI node with an illegal type if 313202375Srdivacky // it is currently legal. 314204642Srdivacky if (!Src->getType()->isIntegerTy() || 315204642Srdivacky !CI.getType()->isIntegerTy() || 316202375Srdivacky ShouldChangeType(CI.getType(), Src->getType())) 317202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(CI)) 318202375Srdivacky return NV; 319202375Srdivacky } 320249423Sdim 321202375Srdivacky return 0; 322202375Srdivacky} 323202375Srdivacky 324202375Srdivacky/// CanEvaluateTruncated - Return true if we can evaluate the specified 325202375Srdivacky/// expression tree as type Ty instead of its larger type, and arrive with the 326202375Srdivacky/// same value. This is used by code that tries to eliminate truncates. 327202375Srdivacky/// 328202375Srdivacky/// Ty will always be a type smaller than V. We should return true if trunc(V) 329202375Srdivacky/// can be computed by computing V in the smaller type. If V is an instruction, 330202375Srdivacky/// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only 331202375Srdivacky/// makes sense if x and y can be efficiently truncated. 332202375Srdivacky/// 333202375Srdivacky/// This function works on both vectors and scalars. 334202375Srdivacky/// 335226633Sdimstatic bool CanEvaluateTruncated(Value *V, Type *Ty) { 336202375Srdivacky // We can always evaluate constants in another type. 337202375Srdivacky if (isa<Constant>(V)) 338202375Srdivacky return true; 339249423Sdim 340202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 341202375Srdivacky if (!I) return false; 342249423Sdim 343226633Sdim Type *OrigTy = V->getType(); 344249423Sdim 345202375Srdivacky // If this is an extension from the dest type, we can eliminate it, even if it 346202375Srdivacky // has multiple uses. 347249423Sdim if ((isa<ZExtInst>(I) || isa<SExtInst>(I)) && 348202375Srdivacky I->getOperand(0)->getType() == Ty) 349202375Srdivacky return true; 350202375Srdivacky 351202375Srdivacky // We can't extend or shrink something that has multiple uses: doing so would 352202375Srdivacky // require duplicating the instruction in general, which isn't profitable. 353202375Srdivacky if (!I->hasOneUse()) return false; 354202375Srdivacky 355202375Srdivacky unsigned Opc = I->getOpcode(); 356202375Srdivacky switch (Opc) { 357202375Srdivacky case Instruction::Add: 358202375Srdivacky case Instruction::Sub: 359202375Srdivacky case Instruction::Mul: 360202375Srdivacky case Instruction::And: 361202375Srdivacky case Instruction::Or: 362202375Srdivacky case Instruction::Xor: 363202375Srdivacky // These operators can all arbitrarily be extended or truncated. 364202375Srdivacky return CanEvaluateTruncated(I->getOperand(0), Ty) && 365202375Srdivacky CanEvaluateTruncated(I->getOperand(1), Ty); 366202375Srdivacky 367202375Srdivacky case Instruction::UDiv: 368202375Srdivacky case Instruction::URem: { 369202375Srdivacky // UDiv and URem can be truncated if all the truncated bits are zero. 370202375Srdivacky uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); 371202375Srdivacky uint32_t BitWidth = Ty->getScalarSizeInBits(); 372202375Srdivacky if (BitWidth < OrigBitWidth) { 373202375Srdivacky APInt Mask = APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth); 374202375Srdivacky if (MaskedValueIsZero(I->getOperand(0), Mask) && 375202375Srdivacky MaskedValueIsZero(I->getOperand(1), Mask)) { 376202375Srdivacky return CanEvaluateTruncated(I->getOperand(0), Ty) && 377202375Srdivacky CanEvaluateTruncated(I->getOperand(1), Ty); 378202375Srdivacky } 379202375Srdivacky } 380202375Srdivacky break; 381202375Srdivacky } 382202375Srdivacky case Instruction::Shl: 383202375Srdivacky // If we are truncating the result of this SHL, and if it's a shift of a 384202375Srdivacky // constant amount, we can always perform a SHL in a smaller type. 385202375Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) { 386202375Srdivacky uint32_t BitWidth = Ty->getScalarSizeInBits(); 387202375Srdivacky if (CI->getLimitedValue(BitWidth) < BitWidth) 388202375Srdivacky return CanEvaluateTruncated(I->getOperand(0), Ty); 389202375Srdivacky } 390202375Srdivacky break; 391202375Srdivacky case Instruction::LShr: 392202375Srdivacky // If this is a truncate of a logical shr, we can truncate it to a smaller 393202375Srdivacky // lshr iff we know that the bits we would otherwise be shifting in are 394202375Srdivacky // already zeros. 395202375Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) { 396202375Srdivacky uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); 397202375Srdivacky uint32_t BitWidth = Ty->getScalarSizeInBits(); 398202375Srdivacky if (MaskedValueIsZero(I->getOperand(0), 399202375Srdivacky APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) && 400202375Srdivacky CI->getLimitedValue(BitWidth) < BitWidth) { 401202375Srdivacky return CanEvaluateTruncated(I->getOperand(0), Ty); 402202375Srdivacky } 403202375Srdivacky } 404202375Srdivacky break; 405202375Srdivacky case Instruction::Trunc: 406202375Srdivacky // trunc(trunc(x)) -> trunc(x) 407202375Srdivacky return true; 408212904Sdim case Instruction::ZExt: 409212904Sdim case Instruction::SExt: 410212904Sdim // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest 411212904Sdim // trunc(ext(x)) -> trunc(x) if the source type is larger than the new dest 412212904Sdim return true; 413202375Srdivacky case Instruction::Select: { 414202375Srdivacky SelectInst *SI = cast<SelectInst>(I); 415202375Srdivacky return CanEvaluateTruncated(SI->getTrueValue(), Ty) && 416202375Srdivacky CanEvaluateTruncated(SI->getFalseValue(), Ty); 417202375Srdivacky } 418202375Srdivacky case Instruction::PHI: { 419202375Srdivacky // We can change a phi if we can change all operands. Note that we never 420202375Srdivacky // get into trouble with cyclic PHIs here because we only consider 421202375Srdivacky // instructions with a single use. 422202375Srdivacky PHINode *PN = cast<PHINode>(I); 423202375Srdivacky for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 424202375Srdivacky if (!CanEvaluateTruncated(PN->getIncomingValue(i), Ty)) 425202375Srdivacky return false; 426202375Srdivacky return true; 427202375Srdivacky } 428202375Srdivacky default: 429202375Srdivacky // TODO: Can handle more cases here. 430202375Srdivacky break; 431202375Srdivacky } 432249423Sdim 433202375Srdivacky return false; 434202375Srdivacky} 435202375Srdivacky 436202375SrdivackyInstruction *InstCombiner::visitTrunc(TruncInst &CI) { 437202375Srdivacky if (Instruction *Result = commonCastTransforms(CI)) 438202375Srdivacky return Result; 439249423Sdim 440249423Sdim // See if we can simplify any instructions used by the input whose sole 441202375Srdivacky // purpose is to compute bits we don't care about. 442202375Srdivacky if (SimplifyDemandedInstructionBits(CI)) 443202375Srdivacky return &CI; 444249423Sdim 445202375Srdivacky Value *Src = CI.getOperand(0); 446226633Sdim Type *DestTy = CI.getType(), *SrcTy = Src->getType(); 447249423Sdim 448202375Srdivacky // Attempt to truncate the entire input expression tree to the destination 449202375Srdivacky // type. Only do this if the dest type is a simple type, don't convert the 450202375Srdivacky // expression tree to something weird like i93 unless the source is also 451202375Srdivacky // strange. 452204642Srdivacky if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) && 453202375Srdivacky CanEvaluateTruncated(Src, DestTy)) { 454249423Sdim 455202375Srdivacky // If this cast is a truncate, evaluting in a different type always 456202375Srdivacky // eliminates the cast, so it is always a win. 457202375Srdivacky DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type" 458208599Srdivacky " to avoid cast: " << CI << '\n'); 459202375Srdivacky Value *Res = EvaluateInDifferentType(Src, DestTy, false); 460202375Srdivacky assert(Res->getType() == DestTy); 461202375Srdivacky return ReplaceInstUsesWith(CI, Res); 462202375Srdivacky } 463202375Srdivacky 464202375Srdivacky // Canonicalize trunc x to i1 -> (icmp ne (and x, 1), 0), likewise for vector. 465202375Srdivacky if (DestTy->getScalarSizeInBits() == 1) { 466202375Srdivacky Constant *One = ConstantInt::get(Src->getType(), 1); 467226633Sdim Src = Builder->CreateAnd(Src, One); 468202375Srdivacky Value *Zero = Constant::getNullValue(Src->getType()); 469202375Srdivacky return new ICmpInst(ICmpInst::ICMP_NE, Src, Zero); 470202375Srdivacky } 471249423Sdim 472212904Sdim // Transform trunc(lshr (zext A), Cst) to eliminate one type conversion. 473212904Sdim Value *A = 0; ConstantInt *Cst = 0; 474218893Sdim if (Src->hasOneUse() && 475218893Sdim match(Src, m_LShr(m_ZExt(m_Value(A)), m_ConstantInt(Cst)))) { 476212904Sdim // We have three types to worry about here, the type of A, the source of 477212904Sdim // the truncate (MidSize), and the destination of the truncate. We know that 478212904Sdim // ASize < MidSize and MidSize > ResultSize, but don't know the relation 479212904Sdim // between ASize and ResultSize. 480212904Sdim unsigned ASize = A->getType()->getPrimitiveSizeInBits(); 481249423Sdim 482212904Sdim // If the shift amount is larger than the size of A, then the result is 483212904Sdim // known to be zero because all the input bits got shifted out. 484212904Sdim if (Cst->getZExtValue() >= ASize) 485212904Sdim return ReplaceInstUsesWith(CI, Constant::getNullValue(CI.getType())); 486202375Srdivacky 487212904Sdim // Since we're doing an lshr and a zero extend, and know that the shift 488212904Sdim // amount is smaller than ASize, it is always safe to do the shift in A's 489212904Sdim // type, then zero extend or truncate to the result. 490212904Sdim Value *Shift = Builder->CreateLShr(A, Cst->getZExtValue()); 491212904Sdim Shift->takeName(Src); 492212904Sdim return CastInst::CreateIntegerCast(Shift, CI.getType(), false); 493212904Sdim } 494249423Sdim 495218893Sdim // Transform "trunc (and X, cst)" -> "and (trunc X), cst" so long as the dest 496218893Sdim // type isn't non-native. 497218893Sdim if (Src->hasOneUse() && isa<IntegerType>(Src->getType()) && 498218893Sdim ShouldChangeType(Src->getType(), CI.getType()) && 499218893Sdim match(Src, m_And(m_Value(A), m_ConstantInt(Cst)))) { 500218893Sdim Value *NewTrunc = Builder->CreateTrunc(A, CI.getType(), A->getName()+".tr"); 501218893Sdim return BinaryOperator::CreateAnd(NewTrunc, 502218893Sdim ConstantExpr::getTrunc(Cst, CI.getType())); 503218893Sdim } 504212904Sdim 505202375Srdivacky return 0; 506202375Srdivacky} 507202375Srdivacky 508202375Srdivacky/// transformZExtICmp - Transform (zext icmp) to bitwise / integer operations 509202375Srdivacky/// in order to eliminate the icmp. 510202375SrdivackyInstruction *InstCombiner::transformZExtICmp(ICmpInst *ICI, Instruction &CI, 511202375Srdivacky bool DoXform) { 512202375Srdivacky // If we are just checking for a icmp eq of a single bit and zext'ing it 513202375Srdivacky // to an integer, then shift the bit to the appropriate place and then 514202375Srdivacky // cast to integer to avoid the comparison. 515202375Srdivacky if (ConstantInt *Op1C = dyn_cast<ConstantInt>(ICI->getOperand(1))) { 516202375Srdivacky const APInt &Op1CV = Op1C->getValue(); 517249423Sdim 518202375Srdivacky // zext (x <s 0) to i32 --> x>>u31 true if signbit set. 519202375Srdivacky // zext (x >s -1) to i32 --> (x>>u31)^1 true if signbit clear. 520202375Srdivacky if ((ICI->getPredicate() == ICmpInst::ICMP_SLT && Op1CV == 0) || 521202375Srdivacky (ICI->getPredicate() == ICmpInst::ICMP_SGT &&Op1CV.isAllOnesValue())) { 522202375Srdivacky if (!DoXform) return ICI; 523202375Srdivacky 524202375Srdivacky Value *In = ICI->getOperand(0); 525202375Srdivacky Value *Sh = ConstantInt::get(In->getType(), 526202375Srdivacky In->getType()->getScalarSizeInBits()-1); 527202375Srdivacky In = Builder->CreateLShr(In, Sh, In->getName()+".lobit"); 528202375Srdivacky if (In->getType() != CI.getType()) 529226633Sdim In = Builder->CreateIntCast(In, CI.getType(), false/*ZExt*/); 530202375Srdivacky 531202375Srdivacky if (ICI->getPredicate() == ICmpInst::ICMP_SGT) { 532202375Srdivacky Constant *One = ConstantInt::get(In->getType(), 1); 533202375Srdivacky In = Builder->CreateXor(In, One, In->getName()+".not"); 534202375Srdivacky } 535202375Srdivacky 536202375Srdivacky return ReplaceInstUsesWith(CI, In); 537202375Srdivacky } 538234353Sdim 539202375Srdivacky // zext (X == 0) to i32 --> X^1 iff X has only the low bit set. 540202375Srdivacky // zext (X == 0) to i32 --> (X>>1)^1 iff X has only the 2nd bit set. 541202375Srdivacky // zext (X == 1) to i32 --> X iff X has only the low bit set. 542202375Srdivacky // zext (X == 2) to i32 --> X>>1 iff X has only the 2nd bit set. 543202375Srdivacky // zext (X != 0) to i32 --> X iff X has only the low bit set. 544202375Srdivacky // zext (X != 0) to i32 --> X>>1 iff X has only the 2nd bit set. 545202375Srdivacky // zext (X != 1) to i32 --> X^1 iff X has only the low bit set. 546202375Srdivacky // zext (X != 2) to i32 --> (X>>1)^1 iff X has only the 2nd bit set. 547249423Sdim if ((Op1CV == 0 || Op1CV.isPowerOf2()) && 548202375Srdivacky // This only works for EQ and NE 549202375Srdivacky ICI->isEquality()) { 550202375Srdivacky // If Op1C some other power of two, convert: 551202375Srdivacky uint32_t BitWidth = Op1C->getType()->getBitWidth(); 552202375Srdivacky APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 553234353Sdim ComputeMaskedBits(ICI->getOperand(0), KnownZero, KnownOne); 554249423Sdim 555202375Srdivacky APInt KnownZeroMask(~KnownZero); 556202375Srdivacky if (KnownZeroMask.isPowerOf2()) { // Exactly 1 possible 1? 557202375Srdivacky if (!DoXform) return ICI; 558202375Srdivacky 559202375Srdivacky bool isNE = ICI->getPredicate() == ICmpInst::ICMP_NE; 560202375Srdivacky if (Op1CV != 0 && (Op1CV != KnownZeroMask)) { 561202375Srdivacky // (X&4) == 2 --> false 562202375Srdivacky // (X&4) != 2 --> true 563202375Srdivacky Constant *Res = ConstantInt::get(Type::getInt1Ty(CI.getContext()), 564202375Srdivacky isNE); 565202375Srdivacky Res = ConstantExpr::getZExt(Res, CI.getType()); 566202375Srdivacky return ReplaceInstUsesWith(CI, Res); 567202375Srdivacky } 568249423Sdim 569202375Srdivacky uint32_t ShiftAmt = KnownZeroMask.logBase2(); 570202375Srdivacky Value *In = ICI->getOperand(0); 571202375Srdivacky if (ShiftAmt) { 572202375Srdivacky // Perform a logical shr by shiftamt. 573202375Srdivacky // Insert the shift to put the result in the low bit. 574202375Srdivacky In = Builder->CreateLShr(In, ConstantInt::get(In->getType(),ShiftAmt), 575202375Srdivacky In->getName()+".lobit"); 576202375Srdivacky } 577249423Sdim 578202375Srdivacky if ((Op1CV != 0) == isNE) { // Toggle the low bit. 579202375Srdivacky Constant *One = ConstantInt::get(In->getType(), 1); 580226633Sdim In = Builder->CreateXor(In, One); 581202375Srdivacky } 582249423Sdim 583202375Srdivacky if (CI.getType() == In->getType()) 584202375Srdivacky return ReplaceInstUsesWith(CI, In); 585212904Sdim return CastInst::CreateIntegerCast(In, CI.getType(), false/*ZExt*/); 586202375Srdivacky } 587202375Srdivacky } 588202375Srdivacky } 589202375Srdivacky 590202375Srdivacky // icmp ne A, B is equal to xor A, B when A and B only really have one bit. 591202375Srdivacky // It is also profitable to transform icmp eq into not(xor(A, B)) because that 592202375Srdivacky // may lead to additional simplifications. 593202375Srdivacky if (ICI->isEquality() && CI.getType() == ICI->getOperand(0)->getType()) { 594226633Sdim if (IntegerType *ITy = dyn_cast<IntegerType>(CI.getType())) { 595202375Srdivacky uint32_t BitWidth = ITy->getBitWidth(); 596202375Srdivacky Value *LHS = ICI->getOperand(0); 597202375Srdivacky Value *RHS = ICI->getOperand(1); 598202375Srdivacky 599202375Srdivacky APInt KnownZeroLHS(BitWidth, 0), KnownOneLHS(BitWidth, 0); 600202375Srdivacky APInt KnownZeroRHS(BitWidth, 0), KnownOneRHS(BitWidth, 0); 601234353Sdim ComputeMaskedBits(LHS, KnownZeroLHS, KnownOneLHS); 602234353Sdim ComputeMaskedBits(RHS, KnownZeroRHS, KnownOneRHS); 603202375Srdivacky 604202375Srdivacky if (KnownZeroLHS == KnownZeroRHS && KnownOneLHS == KnownOneRHS) { 605202375Srdivacky APInt KnownBits = KnownZeroLHS | KnownOneLHS; 606202375Srdivacky APInt UnknownBit = ~KnownBits; 607202375Srdivacky if (UnknownBit.countPopulation() == 1) { 608202375Srdivacky if (!DoXform) return ICI; 609202375Srdivacky 610202375Srdivacky Value *Result = Builder->CreateXor(LHS, RHS); 611202375Srdivacky 612202375Srdivacky // Mask off any bits that are set and won't be shifted away. 613202375Srdivacky if (KnownOneLHS.uge(UnknownBit)) 614202375Srdivacky Result = Builder->CreateAnd(Result, 615202375Srdivacky ConstantInt::get(ITy, UnknownBit)); 616202375Srdivacky 617202375Srdivacky // Shift the bit we're testing down to the lsb. 618202375Srdivacky Result = Builder->CreateLShr( 619202375Srdivacky Result, ConstantInt::get(ITy, UnknownBit.countTrailingZeros())); 620202375Srdivacky 621202375Srdivacky if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 622202375Srdivacky Result = Builder->CreateXor(Result, ConstantInt::get(ITy, 1)); 623202375Srdivacky Result->takeName(ICI); 624202375Srdivacky return ReplaceInstUsesWith(CI, Result); 625202375Srdivacky } 626202375Srdivacky } 627202375Srdivacky } 628202375Srdivacky } 629202375Srdivacky 630202375Srdivacky return 0; 631202375Srdivacky} 632202375Srdivacky 633202375Srdivacky/// CanEvaluateZExtd - Determine if the specified value can be computed in the 634202375Srdivacky/// specified wider type and produce the same low bits. If not, return false. 635202375Srdivacky/// 636202375Srdivacky/// If this function returns true, it can also return a non-zero number of bits 637202375Srdivacky/// (in BitsToClear) which indicates that the value it computes is correct for 638202375Srdivacky/// the zero extend, but that the additional BitsToClear bits need to be zero'd 639202375Srdivacky/// out. For example, to promote something like: 640202375Srdivacky/// 641202375Srdivacky/// %B = trunc i64 %A to i32 642202375Srdivacky/// %C = lshr i32 %B, 8 643202375Srdivacky/// %E = zext i32 %C to i64 644202375Srdivacky/// 645202375Srdivacky/// CanEvaluateZExtd for the 'lshr' will return true, and BitsToClear will be 646202375Srdivacky/// set to 8 to indicate that the promoted value needs to have bits 24-31 647202375Srdivacky/// cleared in addition to bits 32-63. Since an 'and' will be generated to 648202375Srdivacky/// clear the top bits anyway, doing this has no extra cost. 649202375Srdivacky/// 650202375Srdivacky/// This function works on both vectors and scalars. 651226633Sdimstatic bool CanEvaluateZExtd(Value *V, Type *Ty, unsigned &BitsToClear) { 652202375Srdivacky BitsToClear = 0; 653202375Srdivacky if (isa<Constant>(V)) 654202375Srdivacky return true; 655249423Sdim 656202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 657202375Srdivacky if (!I) return false; 658249423Sdim 659202375Srdivacky // If the input is a truncate from the destination type, we can trivially 660239462Sdim // eliminate it. 661239462Sdim if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) 662202375Srdivacky return true; 663249423Sdim 664202375Srdivacky // We can't extend or shrink something that has multiple uses: doing so would 665202375Srdivacky // require duplicating the instruction in general, which isn't profitable. 666202375Srdivacky if (!I->hasOneUse()) return false; 667249423Sdim 668202375Srdivacky unsigned Opc = I->getOpcode(), Tmp; 669202375Srdivacky switch (Opc) { 670202375Srdivacky case Instruction::ZExt: // zext(zext(x)) -> zext(x). 671202375Srdivacky case Instruction::SExt: // zext(sext(x)) -> sext(x). 672202375Srdivacky case Instruction::Trunc: // zext(trunc(x)) -> trunc(x) or zext(x) 673202375Srdivacky return true; 674202375Srdivacky case Instruction::And: 675202375Srdivacky case Instruction::Or: 676202375Srdivacky case Instruction::Xor: 677202375Srdivacky case Instruction::Add: 678202375Srdivacky case Instruction::Sub: 679202375Srdivacky case Instruction::Mul: 680202375Srdivacky case Instruction::Shl: 681202375Srdivacky if (!CanEvaluateZExtd(I->getOperand(0), Ty, BitsToClear) || 682202375Srdivacky !CanEvaluateZExtd(I->getOperand(1), Ty, Tmp)) 683202375Srdivacky return false; 684202375Srdivacky // These can all be promoted if neither operand has 'bits to clear'. 685202375Srdivacky if (BitsToClear == 0 && Tmp == 0) 686202375Srdivacky return true; 687249423Sdim 688202375Srdivacky // If the operation is an AND/OR/XOR and the bits to clear are zero in the 689202375Srdivacky // other side, BitsToClear is ok. 690202375Srdivacky if (Tmp == 0 && 691202375Srdivacky (Opc == Instruction::And || Opc == Instruction::Or || 692202375Srdivacky Opc == Instruction::Xor)) { 693202375Srdivacky // We use MaskedValueIsZero here for generality, but the case we care 694202375Srdivacky // about the most is constant RHS. 695202375Srdivacky unsigned VSize = V->getType()->getScalarSizeInBits(); 696202375Srdivacky if (MaskedValueIsZero(I->getOperand(1), 697202375Srdivacky APInt::getHighBitsSet(VSize, BitsToClear))) 698202375Srdivacky return true; 699202375Srdivacky } 700249423Sdim 701202375Srdivacky // Otherwise, we don't know how to analyze this BitsToClear case yet. 702202375Srdivacky return false; 703249423Sdim 704202375Srdivacky case Instruction::LShr: 705202375Srdivacky // We can promote lshr(x, cst) if we can promote x. This requires the 706202375Srdivacky // ultimate 'and' to clear out the high zero bits we're clearing out though. 707202375Srdivacky if (ConstantInt *Amt = dyn_cast<ConstantInt>(I->getOperand(1))) { 708202375Srdivacky if (!CanEvaluateZExtd(I->getOperand(0), Ty, BitsToClear)) 709202375Srdivacky return false; 710202375Srdivacky BitsToClear += Amt->getZExtValue(); 711202375Srdivacky if (BitsToClear > V->getType()->getScalarSizeInBits()) 712202375Srdivacky BitsToClear = V->getType()->getScalarSizeInBits(); 713202375Srdivacky return true; 714202375Srdivacky } 715202375Srdivacky // Cannot promote variable LSHR. 716202375Srdivacky return false; 717202375Srdivacky case Instruction::Select: 718202375Srdivacky if (!CanEvaluateZExtd(I->getOperand(1), Ty, Tmp) || 719202375Srdivacky !CanEvaluateZExtd(I->getOperand(2), Ty, BitsToClear) || 720202375Srdivacky // TODO: If important, we could handle the case when the BitsToClear are 721202375Srdivacky // known zero in the disagreeing side. 722202375Srdivacky Tmp != BitsToClear) 723202375Srdivacky return false; 724202375Srdivacky return true; 725249423Sdim 726202375Srdivacky case Instruction::PHI: { 727202375Srdivacky // We can change a phi if we can change all operands. Note that we never 728202375Srdivacky // get into trouble with cyclic PHIs here because we only consider 729202375Srdivacky // instructions with a single use. 730202375Srdivacky PHINode *PN = cast<PHINode>(I); 731202375Srdivacky if (!CanEvaluateZExtd(PN->getIncomingValue(0), Ty, BitsToClear)) 732202375Srdivacky return false; 733202375Srdivacky for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 734202375Srdivacky if (!CanEvaluateZExtd(PN->getIncomingValue(i), Ty, Tmp) || 735202375Srdivacky // TODO: If important, we could handle the case when the BitsToClear 736202375Srdivacky // are known zero in the disagreeing input. 737202375Srdivacky Tmp != BitsToClear) 738202375Srdivacky return false; 739202375Srdivacky return true; 740202375Srdivacky } 741202375Srdivacky default: 742202375Srdivacky // TODO: Can handle more cases here. 743202375Srdivacky return false; 744202375Srdivacky } 745202375Srdivacky} 746202375Srdivacky 747202375SrdivackyInstruction *InstCombiner::visitZExt(ZExtInst &CI) { 748249423Sdim // If this zero extend is only used by a truncate, let the truncate be 749202375Srdivacky // eliminated before we try to optimize this zext. 750202375Srdivacky if (CI.hasOneUse() && isa<TruncInst>(CI.use_back())) 751202375Srdivacky return 0; 752249423Sdim 753202375Srdivacky // If one of the common conversion will work, do it. 754202375Srdivacky if (Instruction *Result = commonCastTransforms(CI)) 755202375Srdivacky return Result; 756202375Srdivacky 757249423Sdim // See if we can simplify any instructions used by the input whose sole 758202375Srdivacky // purpose is to compute bits we don't care about. 759202375Srdivacky if (SimplifyDemandedInstructionBits(CI)) 760202375Srdivacky return &CI; 761249423Sdim 762202375Srdivacky Value *Src = CI.getOperand(0); 763226633Sdim Type *SrcTy = Src->getType(), *DestTy = CI.getType(); 764249423Sdim 765202375Srdivacky // Attempt to extend the entire input expression tree to the destination 766202375Srdivacky // type. Only do this if the dest type is a simple type, don't convert the 767202375Srdivacky // expression tree to something weird like i93 unless the source is also 768202375Srdivacky // strange. 769202375Srdivacky unsigned BitsToClear; 770204642Srdivacky if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) && 771249423Sdim CanEvaluateZExtd(Src, DestTy, BitsToClear)) { 772202375Srdivacky assert(BitsToClear < SrcTy->getScalarSizeInBits() && 773202375Srdivacky "Unreasonable BitsToClear"); 774249423Sdim 775202375Srdivacky // Okay, we can transform this! Insert the new expression now. 776202375Srdivacky DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type" 777202375Srdivacky " to avoid zero extend: " << CI); 778202375Srdivacky Value *Res = EvaluateInDifferentType(Src, DestTy, false); 779202375Srdivacky assert(Res->getType() == DestTy); 780249423Sdim 781202375Srdivacky uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits()-BitsToClear; 782202375Srdivacky uint32_t DestBitSize = DestTy->getScalarSizeInBits(); 783249423Sdim 784202375Srdivacky // If the high bits are already filled with zeros, just replace this 785202375Srdivacky // cast with the result. 786202375Srdivacky if (MaskedValueIsZero(Res, APInt::getHighBitsSet(DestBitSize, 787202375Srdivacky DestBitSize-SrcBitsKept))) 788202375Srdivacky return ReplaceInstUsesWith(CI, Res); 789249423Sdim 790202375Srdivacky // We need to emit an AND to clear the high bits. 791202375Srdivacky Constant *C = ConstantInt::get(Res->getType(), 792202375Srdivacky APInt::getLowBitsSet(DestBitSize, SrcBitsKept)); 793202375Srdivacky return BinaryOperator::CreateAnd(Res, C); 794202375Srdivacky } 795202375Srdivacky 796202375Srdivacky // If this is a TRUNC followed by a ZEXT then we are dealing with integral 797202375Srdivacky // types and if the sizes are just right we can convert this into a logical 798202375Srdivacky // 'and' which will be much cheaper than the pair of casts. 799202375Srdivacky if (TruncInst *CSrc = dyn_cast<TruncInst>(Src)) { // A->B->C cast 800202375Srdivacky // TODO: Subsume this into EvaluateInDifferentType. 801249423Sdim 802202375Srdivacky // Get the sizes of the types involved. We know that the intermediate type 803202375Srdivacky // will be smaller than A or C, but don't know the relation between A and C. 804202375Srdivacky Value *A = CSrc->getOperand(0); 805202375Srdivacky unsigned SrcSize = A->getType()->getScalarSizeInBits(); 806202375Srdivacky unsigned MidSize = CSrc->getType()->getScalarSizeInBits(); 807202375Srdivacky unsigned DstSize = CI.getType()->getScalarSizeInBits(); 808202375Srdivacky // If we're actually extending zero bits, then if 809202375Srdivacky // SrcSize < DstSize: zext(a & mask) 810202375Srdivacky // SrcSize == DstSize: a & mask 811202375Srdivacky // SrcSize > DstSize: trunc(a) & mask 812202375Srdivacky if (SrcSize < DstSize) { 813202375Srdivacky APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize)); 814202375Srdivacky Constant *AndConst = ConstantInt::get(A->getType(), AndValue); 815202375Srdivacky Value *And = Builder->CreateAnd(A, AndConst, CSrc->getName()+".mask"); 816202375Srdivacky return new ZExtInst(And, CI.getType()); 817202375Srdivacky } 818249423Sdim 819202375Srdivacky if (SrcSize == DstSize) { 820202375Srdivacky APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize)); 821202375Srdivacky return BinaryOperator::CreateAnd(A, ConstantInt::get(A->getType(), 822202375Srdivacky AndValue)); 823202375Srdivacky } 824202375Srdivacky if (SrcSize > DstSize) { 825226633Sdim Value *Trunc = Builder->CreateTrunc(A, CI.getType()); 826202375Srdivacky APInt AndValue(APInt::getLowBitsSet(DstSize, MidSize)); 827249423Sdim return BinaryOperator::CreateAnd(Trunc, 828202375Srdivacky ConstantInt::get(Trunc->getType(), 829202375Srdivacky AndValue)); 830202375Srdivacky } 831202375Srdivacky } 832202375Srdivacky 833202375Srdivacky if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src)) 834202375Srdivacky return transformZExtICmp(ICI, CI); 835202375Srdivacky 836202375Srdivacky BinaryOperator *SrcI = dyn_cast<BinaryOperator>(Src); 837202375Srdivacky if (SrcI && SrcI->getOpcode() == Instruction::Or) { 838202375Srdivacky // zext (or icmp, icmp) --> or (zext icmp), (zext icmp) if at least one 839202375Srdivacky // of the (zext icmp) will be transformed. 840202375Srdivacky ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0)); 841202375Srdivacky ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1)); 842202375Srdivacky if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() && 843202375Srdivacky (transformZExtICmp(LHS, CI, false) || 844202375Srdivacky transformZExtICmp(RHS, CI, false))) { 845202375Srdivacky Value *LCast = Builder->CreateZExt(LHS, CI.getType(), LHS->getName()); 846202375Srdivacky Value *RCast = Builder->CreateZExt(RHS, CI.getType(), RHS->getName()); 847202375Srdivacky return BinaryOperator::Create(Instruction::Or, LCast, RCast); 848202375Srdivacky } 849202375Srdivacky } 850202375Srdivacky 851202375Srdivacky // zext(trunc(t) & C) -> (t & zext(C)). 852202375Srdivacky if (SrcI && SrcI->getOpcode() == Instruction::And && SrcI->hasOneUse()) 853202375Srdivacky if (ConstantInt *C = dyn_cast<ConstantInt>(SrcI->getOperand(1))) 854202375Srdivacky if (TruncInst *TI = dyn_cast<TruncInst>(SrcI->getOperand(0))) { 855202375Srdivacky Value *TI0 = TI->getOperand(0); 856202375Srdivacky if (TI0->getType() == CI.getType()) 857202375Srdivacky return 858202375Srdivacky BinaryOperator::CreateAnd(TI0, 859202375Srdivacky ConstantExpr::getZExt(C, CI.getType())); 860202375Srdivacky } 861202375Srdivacky 862202375Srdivacky // zext((trunc(t) & C) ^ C) -> ((t & zext(C)) ^ zext(C)). 863202375Srdivacky if (SrcI && SrcI->getOpcode() == Instruction::Xor && SrcI->hasOneUse()) 864202375Srdivacky if (ConstantInt *C = dyn_cast<ConstantInt>(SrcI->getOperand(1))) 865202375Srdivacky if (BinaryOperator *And = dyn_cast<BinaryOperator>(SrcI->getOperand(0))) 866202375Srdivacky if (And->getOpcode() == Instruction::And && And->hasOneUse() && 867202375Srdivacky And->getOperand(1) == C) 868202375Srdivacky if (TruncInst *TI = dyn_cast<TruncInst>(And->getOperand(0))) { 869202375Srdivacky Value *TI0 = TI->getOperand(0); 870202375Srdivacky if (TI0->getType() == CI.getType()) { 871202375Srdivacky Constant *ZC = ConstantExpr::getZExt(C, CI.getType()); 872226633Sdim Value *NewAnd = Builder->CreateAnd(TI0, ZC); 873202375Srdivacky return BinaryOperator::CreateXor(NewAnd, ZC); 874202375Srdivacky } 875202375Srdivacky } 876202375Srdivacky 877202375Srdivacky // zext (xor i1 X, true) to i32 --> xor (zext i1 X to i32), 1 878202375Srdivacky Value *X; 879203954Srdivacky if (SrcI && SrcI->hasOneUse() && SrcI->getType()->isIntegerTy(1) && 880202375Srdivacky match(SrcI, m_Not(m_Value(X))) && 881202375Srdivacky (!X->hasOneUse() || !isa<CmpInst>(X))) { 882202375Srdivacky Value *New = Builder->CreateZExt(X, CI.getType()); 883202375Srdivacky return BinaryOperator::CreateXor(New, ConstantInt::get(CI.getType(), 1)); 884202375Srdivacky } 885249423Sdim 886202375Srdivacky return 0; 887202375Srdivacky} 888202375Srdivacky 889221345Sdim/// transformSExtICmp - Transform (sext icmp) to bitwise / integer operations 890221345Sdim/// in order to eliminate the icmp. 891221345SdimInstruction *InstCombiner::transformSExtICmp(ICmpInst *ICI, Instruction &CI) { 892221345Sdim Value *Op0 = ICI->getOperand(0), *Op1 = ICI->getOperand(1); 893221345Sdim ICmpInst::Predicate Pred = ICI->getPredicate(); 894221345Sdim 895221345Sdim if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 896221345Sdim // (x <s 0) ? -1 : 0 -> ashr x, 31 -> all ones if negative 897221345Sdim // (x >s -1) ? -1 : 0 -> not (ashr x, 31) -> all ones if positive 898221345Sdim if ((Pred == ICmpInst::ICMP_SLT && Op1C->isZero()) || 899221345Sdim (Pred == ICmpInst::ICMP_SGT && Op1C->isAllOnesValue())) { 900221345Sdim 901221345Sdim Value *Sh = ConstantInt::get(Op0->getType(), 902221345Sdim Op0->getType()->getScalarSizeInBits()-1); 903221345Sdim Value *In = Builder->CreateAShr(Op0, Sh, Op0->getName()+".lobit"); 904221345Sdim if (In->getType() != CI.getType()) 905226633Sdim In = Builder->CreateIntCast(In, CI.getType(), true/*SExt*/); 906221345Sdim 907221345Sdim if (Pred == ICmpInst::ICMP_SGT) 908221345Sdim In = Builder->CreateNot(In, In->getName()+".not"); 909221345Sdim return ReplaceInstUsesWith(CI, In); 910221345Sdim } 911221345Sdim 912221345Sdim // If we know that only one bit of the LHS of the icmp can be set and we 913221345Sdim // have an equality comparison with zero or a power of 2, we can transform 914221345Sdim // the icmp and sext into bitwise/integer operations. 915221345Sdim if (ICI->hasOneUse() && 916221345Sdim ICI->isEquality() && (Op1C->isZero() || Op1C->getValue().isPowerOf2())){ 917221345Sdim unsigned BitWidth = Op1C->getType()->getBitWidth(); 918221345Sdim APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 919234353Sdim ComputeMaskedBits(Op0, KnownZero, KnownOne); 920221345Sdim 921221345Sdim APInt KnownZeroMask(~KnownZero); 922221345Sdim if (KnownZeroMask.isPowerOf2()) { 923221345Sdim Value *In = ICI->getOperand(0); 924221345Sdim 925221345Sdim // If the icmp tests for a known zero bit we can constant fold it. 926221345Sdim if (!Op1C->isZero() && Op1C->getValue() != KnownZeroMask) { 927221345Sdim Value *V = Pred == ICmpInst::ICMP_NE ? 928221345Sdim ConstantInt::getAllOnesValue(CI.getType()) : 929221345Sdim ConstantInt::getNullValue(CI.getType()); 930221345Sdim return ReplaceInstUsesWith(CI, V); 931221345Sdim } 932221345Sdim 933221345Sdim if (!Op1C->isZero() == (Pred == ICmpInst::ICMP_NE)) { 934221345Sdim // sext ((x & 2^n) == 0) -> (x >> n) - 1 935221345Sdim // sext ((x & 2^n) != 2^n) -> (x >> n) - 1 936221345Sdim unsigned ShiftAmt = KnownZeroMask.countTrailingZeros(); 937221345Sdim // Perform a right shift to place the desired bit in the LSB. 938221345Sdim if (ShiftAmt) 939221345Sdim In = Builder->CreateLShr(In, 940221345Sdim ConstantInt::get(In->getType(), ShiftAmt)); 941221345Sdim 942221345Sdim // At this point "In" is either 1 or 0. Subtract 1 to turn 943221345Sdim // {1, 0} -> {0, -1}. 944221345Sdim In = Builder->CreateAdd(In, 945221345Sdim ConstantInt::getAllOnesValue(In->getType()), 946221345Sdim "sext"); 947221345Sdim } else { 948221345Sdim // sext ((x & 2^n) != 0) -> (x << bitwidth-n) a>> bitwidth-1 949221345Sdim // sext ((x & 2^n) == 2^n) -> (x << bitwidth-n) a>> bitwidth-1 950221345Sdim unsigned ShiftAmt = KnownZeroMask.countLeadingZeros(); 951221345Sdim // Perform a left shift to place the desired bit in the MSB. 952221345Sdim if (ShiftAmt) 953221345Sdim In = Builder->CreateShl(In, 954221345Sdim ConstantInt::get(In->getType(), ShiftAmt)); 955221345Sdim 956221345Sdim // Distribute the bit over the whole bit width. 957221345Sdim In = Builder->CreateAShr(In, ConstantInt::get(In->getType(), 958221345Sdim BitWidth - 1), "sext"); 959221345Sdim } 960221345Sdim 961221345Sdim if (CI.getType() == In->getType()) 962221345Sdim return ReplaceInstUsesWith(CI, In); 963221345Sdim return CastInst::CreateIntegerCast(In, CI.getType(), true/*SExt*/); 964221345Sdim } 965221345Sdim } 966221345Sdim } 967221345Sdim 968221345Sdim // vector (x <s 0) ? -1 : 0 -> ashr x, 31 -> all ones if signed. 969226633Sdim if (VectorType *VTy = dyn_cast<VectorType>(CI.getType())) { 970221345Sdim if (Pred == ICmpInst::ICMP_SLT && match(Op1, m_Zero()) && 971221345Sdim Op0->getType() == CI.getType()) { 972226633Sdim Type *EltTy = VTy->getElementType(); 973221345Sdim 974221345Sdim // splat the shift constant to a constant vector. 975221345Sdim Constant *VSh = ConstantInt::get(VTy, EltTy->getScalarSizeInBits()-1); 976221345Sdim Value *In = Builder->CreateAShr(Op0, VSh, Op0->getName()+".lobit"); 977221345Sdim return ReplaceInstUsesWith(CI, In); 978221345Sdim } 979221345Sdim } 980221345Sdim 981221345Sdim return 0; 982221345Sdim} 983221345Sdim 984202375Srdivacky/// CanEvaluateSExtd - Return true if we can take the specified value 985202375Srdivacky/// and return it as type Ty without inserting any new casts and without 986202375Srdivacky/// changing the value of the common low bits. This is used by code that tries 987202375Srdivacky/// to promote integer operations to a wider types will allow us to eliminate 988202375Srdivacky/// the extension. 989202375Srdivacky/// 990202375Srdivacky/// This function works on both vectors and scalars. 991202375Srdivacky/// 992226633Sdimstatic bool CanEvaluateSExtd(Value *V, Type *Ty) { 993202375Srdivacky assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() && 994202375Srdivacky "Can't sign extend type to a smaller type"); 995202375Srdivacky // If this is a constant, it can be trivially promoted. 996202375Srdivacky if (isa<Constant>(V)) 997202375Srdivacky return true; 998249423Sdim 999202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 1000202375Srdivacky if (!I) return false; 1001249423Sdim 1002239462Sdim // If this is a truncate from the dest type, we can trivially eliminate it. 1003239462Sdim if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) 1004202375Srdivacky return true; 1005249423Sdim 1006202375Srdivacky // We can't extend or shrink something that has multiple uses: doing so would 1007202375Srdivacky // require duplicating the instruction in general, which isn't profitable. 1008202375Srdivacky if (!I->hasOneUse()) return false; 1009202375Srdivacky 1010202375Srdivacky switch (I->getOpcode()) { 1011202375Srdivacky case Instruction::SExt: // sext(sext(x)) -> sext(x) 1012202375Srdivacky case Instruction::ZExt: // sext(zext(x)) -> zext(x) 1013202375Srdivacky case Instruction::Trunc: // sext(trunc(x)) -> trunc(x) or sext(x) 1014202375Srdivacky return true; 1015202375Srdivacky case Instruction::And: 1016202375Srdivacky case Instruction::Or: 1017202375Srdivacky case Instruction::Xor: 1018202375Srdivacky case Instruction::Add: 1019202375Srdivacky case Instruction::Sub: 1020202375Srdivacky case Instruction::Mul: 1021202375Srdivacky // These operators can all arbitrarily be extended if their inputs can. 1022202375Srdivacky return CanEvaluateSExtd(I->getOperand(0), Ty) && 1023202375Srdivacky CanEvaluateSExtd(I->getOperand(1), Ty); 1024249423Sdim 1025202375Srdivacky //case Instruction::Shl: TODO 1026202375Srdivacky //case Instruction::LShr: TODO 1027249423Sdim 1028202375Srdivacky case Instruction::Select: 1029202375Srdivacky return CanEvaluateSExtd(I->getOperand(1), Ty) && 1030202375Srdivacky CanEvaluateSExtd(I->getOperand(2), Ty); 1031249423Sdim 1032202375Srdivacky case Instruction::PHI: { 1033202375Srdivacky // We can change a phi if we can change all operands. Note that we never 1034202375Srdivacky // get into trouble with cyclic PHIs here because we only consider 1035202375Srdivacky // instructions with a single use. 1036202375Srdivacky PHINode *PN = cast<PHINode>(I); 1037202375Srdivacky for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1038202375Srdivacky if (!CanEvaluateSExtd(PN->getIncomingValue(i), Ty)) return false; 1039202375Srdivacky return true; 1040202375Srdivacky } 1041202375Srdivacky default: 1042202375Srdivacky // TODO: Can handle more cases here. 1043202375Srdivacky break; 1044202375Srdivacky } 1045249423Sdim 1046202375Srdivacky return false; 1047202375Srdivacky} 1048202375Srdivacky 1049202375SrdivackyInstruction *InstCombiner::visitSExt(SExtInst &CI) { 1050249423Sdim // If this sign extend is only used by a truncate, let the truncate be 1051249423Sdim // eliminated before we try to optimize this sext. 1052202375Srdivacky if (CI.hasOneUse() && isa<TruncInst>(CI.use_back())) 1053202375Srdivacky return 0; 1054249423Sdim 1055202375Srdivacky if (Instruction *I = commonCastTransforms(CI)) 1056202375Srdivacky return I; 1057249423Sdim 1058249423Sdim // See if we can simplify any instructions used by the input whose sole 1059202375Srdivacky // purpose is to compute bits we don't care about. 1060202375Srdivacky if (SimplifyDemandedInstructionBits(CI)) 1061202375Srdivacky return &CI; 1062249423Sdim 1063202375Srdivacky Value *Src = CI.getOperand(0); 1064226633Sdim Type *SrcTy = Src->getType(), *DestTy = CI.getType(); 1065202375Srdivacky 1066202375Srdivacky // Attempt to extend the entire input expression tree to the destination 1067202375Srdivacky // type. Only do this if the dest type is a simple type, don't convert the 1068202375Srdivacky // expression tree to something weird like i93 unless the source is also 1069202375Srdivacky // strange. 1070204642Srdivacky if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) && 1071202375Srdivacky CanEvaluateSExtd(Src, DestTy)) { 1072202375Srdivacky // Okay, we can transform this! Insert the new expression now. 1073202375Srdivacky DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type" 1074202375Srdivacky " to avoid sign extend: " << CI); 1075202375Srdivacky Value *Res = EvaluateInDifferentType(Src, DestTy, true); 1076202375Srdivacky assert(Res->getType() == DestTy); 1077202375Srdivacky 1078202375Srdivacky uint32_t SrcBitSize = SrcTy->getScalarSizeInBits(); 1079202375Srdivacky uint32_t DestBitSize = DestTy->getScalarSizeInBits(); 1080202375Srdivacky 1081202375Srdivacky // If the high bits are already filled with sign bit, just replace this 1082202375Srdivacky // cast with the result. 1083202375Srdivacky if (ComputeNumSignBits(Res) > DestBitSize - SrcBitSize) 1084202375Srdivacky return ReplaceInstUsesWith(CI, Res); 1085249423Sdim 1086202375Srdivacky // We need to emit a shl + ashr to do the sign extend. 1087202375Srdivacky Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize); 1088202375Srdivacky return BinaryOperator::CreateAShr(Builder->CreateShl(Res, ShAmt, "sext"), 1089202375Srdivacky ShAmt); 1090202375Srdivacky } 1091202375Srdivacky 1092202878Srdivacky // If this input is a trunc from our destination, then turn sext(trunc(x)) 1093202878Srdivacky // into shifts. 1094202878Srdivacky if (TruncInst *TI = dyn_cast<TruncInst>(Src)) 1095202878Srdivacky if (TI->hasOneUse() && TI->getOperand(0)->getType() == DestTy) { 1096202878Srdivacky uint32_t SrcBitSize = SrcTy->getScalarSizeInBits(); 1097202878Srdivacky uint32_t DestBitSize = DestTy->getScalarSizeInBits(); 1098249423Sdim 1099202878Srdivacky // We need to emit a shl + ashr to do the sign extend. 1100202878Srdivacky Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize); 1101202878Srdivacky Value *Res = Builder->CreateShl(TI->getOperand(0), ShAmt, "sext"); 1102202878Srdivacky return BinaryOperator::CreateAShr(Res, ShAmt); 1103202878Srdivacky } 1104218893Sdim 1105221345Sdim if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src)) 1106221345Sdim return transformSExtICmp(ICI, CI); 1107218893Sdim 1108202375Srdivacky // If the input is a shl/ashr pair of a same constant, then this is a sign 1109202375Srdivacky // extension from a smaller value. If we could trust arbitrary bitwidth 1110202375Srdivacky // integers, we could turn this into a truncate to the smaller bit and then 1111202375Srdivacky // use a sext for the whole extension. Since we don't, look deeper and check 1112202375Srdivacky // for a truncate. If the source and dest are the same type, eliminate the 1113202375Srdivacky // trunc and extend and just do shifts. For example, turn: 1114202375Srdivacky // %a = trunc i32 %i to i8 1115202375Srdivacky // %b = shl i8 %a, 6 1116202375Srdivacky // %c = ashr i8 %b, 6 1117202375Srdivacky // %d = sext i8 %c to i32 1118202375Srdivacky // into: 1119202375Srdivacky // %a = shl i32 %i, 30 1120202375Srdivacky // %d = ashr i32 %a, 30 1121202375Srdivacky Value *A = 0; 1122202375Srdivacky // TODO: Eventually this could be subsumed by EvaluateInDifferentType. 1123202375Srdivacky ConstantInt *BA = 0, *CA = 0; 1124202375Srdivacky if (match(Src, m_AShr(m_Shl(m_Trunc(m_Value(A)), m_ConstantInt(BA)), 1125202375Srdivacky m_ConstantInt(CA))) && 1126202375Srdivacky BA == CA && A->getType() == CI.getType()) { 1127202375Srdivacky unsigned MidSize = Src->getType()->getScalarSizeInBits(); 1128202375Srdivacky unsigned SrcDstSize = CI.getType()->getScalarSizeInBits(); 1129202375Srdivacky unsigned ShAmt = CA->getZExtValue()+SrcDstSize-MidSize; 1130202375Srdivacky Constant *ShAmtV = ConstantInt::get(CI.getType(), ShAmt); 1131202375Srdivacky A = Builder->CreateShl(A, ShAmtV, CI.getName()); 1132202375Srdivacky return BinaryOperator::CreateAShr(A, ShAmtV); 1133202375Srdivacky } 1134249423Sdim 1135202375Srdivacky return 0; 1136202375Srdivacky} 1137202375Srdivacky 1138202375Srdivacky 1139202375Srdivacky/// FitsInFPType - Return a Constant* for the specified FP constant if it fits 1140202375Srdivacky/// in the specified FP type without changing its value. 1141202375Srdivackystatic Constant *FitsInFPType(ConstantFP *CFP, const fltSemantics &Sem) { 1142202375Srdivacky bool losesInfo; 1143202375Srdivacky APFloat F = CFP->getValueAPF(); 1144202375Srdivacky (void)F.convert(Sem, APFloat::rmNearestTiesToEven, &losesInfo); 1145202375Srdivacky if (!losesInfo) 1146202375Srdivacky return ConstantFP::get(CFP->getContext(), F); 1147202375Srdivacky return 0; 1148202375Srdivacky} 1149202375Srdivacky 1150202375Srdivacky/// LookThroughFPExtensions - If this is an fp extension instruction, look 1151202375Srdivacky/// through it until we get the source value. 1152202375Srdivackystatic Value *LookThroughFPExtensions(Value *V) { 1153202375Srdivacky if (Instruction *I = dyn_cast<Instruction>(V)) 1154202375Srdivacky if (I->getOpcode() == Instruction::FPExt) 1155202375Srdivacky return LookThroughFPExtensions(I->getOperand(0)); 1156249423Sdim 1157202375Srdivacky // If this value is a constant, return the constant in the smallest FP type 1158202375Srdivacky // that can accurately represent it. This allows us to turn 1159202375Srdivacky // (float)((double)X+2.0) into x+2.0f. 1160202375Srdivacky if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) { 1161202375Srdivacky if (CFP->getType() == Type::getPPC_FP128Ty(V->getContext())) 1162202375Srdivacky return V; // No constant folding of this. 1163234353Sdim // See if the value can be truncated to half and then reextended. 1164234353Sdim if (Value *V = FitsInFPType(CFP, APFloat::IEEEhalf)) 1165234353Sdim return V; 1166202375Srdivacky // See if the value can be truncated to float and then reextended. 1167202375Srdivacky if (Value *V = FitsInFPType(CFP, APFloat::IEEEsingle)) 1168202375Srdivacky return V; 1169202375Srdivacky if (CFP->getType()->isDoubleTy()) 1170202375Srdivacky return V; // Won't shrink. 1171202375Srdivacky if (Value *V = FitsInFPType(CFP, APFloat::IEEEdouble)) 1172202375Srdivacky return V; 1173202375Srdivacky // Don't try to shrink to various long double types. 1174202375Srdivacky } 1175249423Sdim 1176202375Srdivacky return V; 1177202375Srdivacky} 1178202375Srdivacky 1179202375SrdivackyInstruction *InstCombiner::visitFPTrunc(FPTruncInst &CI) { 1180202375Srdivacky if (Instruction *I = commonCastTransforms(CI)) 1181202375Srdivacky return I; 1182249423Sdim 1183202375Srdivacky // If we have fptrunc(fadd (fpextend x), (fpextend y)), where x and y are 1184202375Srdivacky // smaller than the destination type, we can eliminate the truncate by doing 1185202375Srdivacky // the add as the smaller type. This applies to fadd/fsub/fmul/fdiv as well 1186202375Srdivacky // as many builtins (sqrt, etc). 1187202375Srdivacky BinaryOperator *OpI = dyn_cast<BinaryOperator>(CI.getOperand(0)); 1188202375Srdivacky if (OpI && OpI->hasOneUse()) { 1189202375Srdivacky switch (OpI->getOpcode()) { 1190202375Srdivacky default: break; 1191202375Srdivacky case Instruction::FAdd: 1192202375Srdivacky case Instruction::FSub: 1193202375Srdivacky case Instruction::FMul: 1194202375Srdivacky case Instruction::FDiv: 1195202375Srdivacky case Instruction::FRem: 1196226633Sdim Type *SrcTy = OpI->getType(); 1197202375Srdivacky Value *LHSTrunc = LookThroughFPExtensions(OpI->getOperand(0)); 1198202375Srdivacky Value *RHSTrunc = LookThroughFPExtensions(OpI->getOperand(1)); 1199249423Sdim if (LHSTrunc->getType() != SrcTy && 1200202375Srdivacky RHSTrunc->getType() != SrcTy) { 1201202375Srdivacky unsigned DstSize = CI.getType()->getScalarSizeInBits(); 1202202375Srdivacky // If the source types were both smaller than the destination type of 1203202375Srdivacky // the cast, do this xform. 1204202375Srdivacky if (LHSTrunc->getType()->getScalarSizeInBits() <= DstSize && 1205202375Srdivacky RHSTrunc->getType()->getScalarSizeInBits() <= DstSize) { 1206202375Srdivacky LHSTrunc = Builder->CreateFPExt(LHSTrunc, CI.getType()); 1207202375Srdivacky RHSTrunc = Builder->CreateFPExt(RHSTrunc, CI.getType()); 1208202375Srdivacky return BinaryOperator::Create(OpI->getOpcode(), LHSTrunc, RHSTrunc); 1209202375Srdivacky } 1210202375Srdivacky } 1211249423Sdim break; 1212202375Srdivacky } 1213249423Sdim 1214249423Sdim // (fptrunc (fneg x)) -> (fneg (fptrunc x)) 1215249423Sdim if (BinaryOperator::isFNeg(OpI)) { 1216249423Sdim Value *InnerTrunc = Builder->CreateFPTrunc(OpI->getOperand(1), 1217249423Sdim CI.getType()); 1218249423Sdim return BinaryOperator::CreateFNeg(InnerTrunc); 1219249423Sdim } 1220202375Srdivacky } 1221249423Sdim 1222249423Sdim IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI.getOperand(0)); 1223249423Sdim if (II) { 1224249423Sdim switch (II->getIntrinsicID()) { 1225249423Sdim default: break; 1226249423Sdim case Intrinsic::fabs: { 1227249423Sdim // (fptrunc (fabs x)) -> (fabs (fptrunc x)) 1228249423Sdim Value *InnerTrunc = Builder->CreateFPTrunc(II->getArgOperand(0), 1229249423Sdim CI.getType()); 1230249423Sdim Type *IntrinsicType[] = { CI.getType() }; 1231249423Sdim Function *Overload = 1232249423Sdim Intrinsic::getDeclaration(CI.getParent()->getParent()->getParent(), 1233249423Sdim II->getIntrinsicID(), IntrinsicType); 1234249423Sdim 1235249423Sdim Value *Args[] = { InnerTrunc }; 1236249423Sdim return CallInst::Create(Overload, Args, II->getName()); 1237249423Sdim } 1238249423Sdim } 1239249423Sdim } 1240249423Sdim 1241212904Sdim // Fold (fptrunc (sqrt (fpext x))) -> (sqrtf x) 1242212904Sdim CallInst *Call = dyn_cast<CallInst>(CI.getOperand(0)); 1243234353Sdim if (Call && Call->getCalledFunction() && TLI->has(LibFunc::sqrtf) && 1244234353Sdim Call->getCalledFunction()->getName() == TLI->getName(LibFunc::sqrt) && 1245224145Sdim Call->getNumArgOperands() == 1 && 1246224145Sdim Call->hasOneUse()) { 1247212904Sdim CastInst *Arg = dyn_cast<CastInst>(Call->getArgOperand(0)); 1248212904Sdim if (Arg && Arg->getOpcode() == Instruction::FPExt && 1249212904Sdim CI.getType()->isFloatTy() && 1250212904Sdim Call->getType()->isDoubleTy() && 1251212904Sdim Arg->getType()->isDoubleTy() && 1252212904Sdim Arg->getOperand(0)->getType()->isFloatTy()) { 1253212904Sdim Function *Callee = Call->getCalledFunction(); 1254212904Sdim Module *M = CI.getParent()->getParent()->getParent(); 1255249423Sdim Constant *SqrtfFunc = M->getOrInsertFunction("sqrtf", 1256212904Sdim Callee->getAttributes(), 1257212904Sdim Builder->getFloatTy(), 1258212904Sdim Builder->getFloatTy(), 1259212904Sdim NULL); 1260212904Sdim CallInst *ret = CallInst::Create(SqrtfFunc, Arg->getOperand(0), 1261212904Sdim "sqrtfcall"); 1262212904Sdim ret->setAttributes(Callee->getAttributes()); 1263249423Sdim 1264249423Sdim 1265212904Sdim // Remove the old Call. With -fmath-errno, it won't get marked readnone. 1266223017Sdim ReplaceInstUsesWith(*Call, UndefValue::get(Call->getType())); 1267212904Sdim EraseInstFromFunction(*Call); 1268212904Sdim return ret; 1269212904Sdim } 1270212904Sdim } 1271249423Sdim 1272202375Srdivacky return 0; 1273202375Srdivacky} 1274202375Srdivacky 1275202375SrdivackyInstruction *InstCombiner::visitFPExt(CastInst &CI) { 1276202375Srdivacky return commonCastTransforms(CI); 1277202375Srdivacky} 1278202375Srdivacky 1279202375SrdivackyInstruction *InstCombiner::visitFPToUI(FPToUIInst &FI) { 1280202375Srdivacky Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0)); 1281202375Srdivacky if (OpI == 0) 1282202375Srdivacky return commonCastTransforms(FI); 1283202375Srdivacky 1284202375Srdivacky // fptoui(uitofp(X)) --> X 1285202375Srdivacky // fptoui(sitofp(X)) --> X 1286202375Srdivacky // This is safe if the intermediate type has enough bits in its mantissa to 1287202375Srdivacky // accurately represent all values of X. For example, do not do this with 1288202375Srdivacky // i64->float->i64. This is also safe for sitofp case, because any negative 1289249423Sdim // 'X' value would cause an undefined result for the fptoui. 1290202375Srdivacky if ((isa<UIToFPInst>(OpI) || isa<SIToFPInst>(OpI)) && 1291202375Srdivacky OpI->getOperand(0)->getType() == FI.getType() && 1292202375Srdivacky (int)FI.getType()->getScalarSizeInBits() < /*extra bit for sign */ 1293202375Srdivacky OpI->getType()->getFPMantissaWidth()) 1294202375Srdivacky return ReplaceInstUsesWith(FI, OpI->getOperand(0)); 1295202375Srdivacky 1296202375Srdivacky return commonCastTransforms(FI); 1297202375Srdivacky} 1298202375Srdivacky 1299202375SrdivackyInstruction *InstCombiner::visitFPToSI(FPToSIInst &FI) { 1300202375Srdivacky Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0)); 1301202375Srdivacky if (OpI == 0) 1302202375Srdivacky return commonCastTransforms(FI); 1303249423Sdim 1304202375Srdivacky // fptosi(sitofp(X)) --> X 1305202375Srdivacky // fptosi(uitofp(X)) --> X 1306202375Srdivacky // This is safe if the intermediate type has enough bits in its mantissa to 1307202375Srdivacky // accurately represent all values of X. For example, do not do this with 1308202375Srdivacky // i64->float->i64. This is also safe for sitofp case, because any negative 1309249423Sdim // 'X' value would cause an undefined result for the fptoui. 1310202375Srdivacky if ((isa<UIToFPInst>(OpI) || isa<SIToFPInst>(OpI)) && 1311202375Srdivacky OpI->getOperand(0)->getType() == FI.getType() && 1312202375Srdivacky (int)FI.getType()->getScalarSizeInBits() <= 1313202375Srdivacky OpI->getType()->getFPMantissaWidth()) 1314202375Srdivacky return ReplaceInstUsesWith(FI, OpI->getOperand(0)); 1315249423Sdim 1316202375Srdivacky return commonCastTransforms(FI); 1317202375Srdivacky} 1318202375Srdivacky 1319202375SrdivackyInstruction *InstCombiner::visitUIToFP(CastInst &CI) { 1320202375Srdivacky return commonCastTransforms(CI); 1321202375Srdivacky} 1322202375Srdivacky 1323202375SrdivackyInstruction *InstCombiner::visitSIToFP(CastInst &CI) { 1324202375Srdivacky return commonCastTransforms(CI); 1325202375Srdivacky} 1326202375Srdivacky 1327202375SrdivackyInstruction *InstCombiner::visitIntToPtr(IntToPtrInst &CI) { 1328203954Srdivacky // If the source integer type is not the intptr_t type for this target, do a 1329203954Srdivacky // trunc or zext to the intptr_t type, then inttoptr of it. This allows the 1330203954Srdivacky // cast to be exposed to other transforms. 1331249423Sdim if (TD && CI.getOperand(0)->getType()->getScalarSizeInBits() != 1332249423Sdim TD->getPointerSizeInBits()) { 1333249423Sdim Type *Ty = TD->getIntPtrType(CI.getContext()); 1334249423Sdim if (CI.getType()->isVectorTy()) // Handle vectors of pointers. 1335249423Sdim Ty = VectorType::get(Ty, CI.getType()->getVectorNumElements()); 1336249423Sdim 1337249423Sdim Value *P = Builder->CreateZExtOrTrunc(CI.getOperand(0), Ty); 1338249423Sdim return new IntToPtrInst(P, CI.getType()); 1339202375Srdivacky } 1340249423Sdim 1341202375Srdivacky if (Instruction *I = commonCastTransforms(CI)) 1342202375Srdivacky return I; 1343202375Srdivacky 1344202375Srdivacky return 0; 1345202375Srdivacky} 1346202375Srdivacky 1347202375Srdivacky/// @brief Implement the transforms for cast of pointer (bitcast/ptrtoint) 1348202375SrdivackyInstruction *InstCombiner::commonPointerCastTransforms(CastInst &CI) { 1349202375Srdivacky Value *Src = CI.getOperand(0); 1350249423Sdim 1351202375Srdivacky if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) { 1352202375Srdivacky // If casting the result of a getelementptr instruction with no offset, turn 1353202375Srdivacky // this into a cast of the original pointer! 1354202375Srdivacky if (GEP->hasAllZeroIndices()) { 1355202375Srdivacky // Changing the cast operand is usually not a good idea but it is safe 1356249423Sdim // here because the pointer operand is being replaced with another 1357202375Srdivacky // pointer operand so the opcode doesn't need to change. 1358202375Srdivacky Worklist.Add(GEP); 1359202375Srdivacky CI.setOperand(0, GEP->getOperand(0)); 1360202375Srdivacky return &CI; 1361202375Srdivacky } 1362249423Sdim 1363202375Srdivacky // If the GEP has a single use, and the base pointer is a bitcast, and the 1364202375Srdivacky // GEP computes a constant offset, see if we can convert these three 1365202375Srdivacky // instructions into fewer. This typically happens with unions and other 1366202375Srdivacky // non-type-safe code. 1367249423Sdim APInt Offset(TD ? TD->getPointerSizeInBits() : 1, 0); 1368202375Srdivacky if (TD && GEP->hasOneUse() && isa<BitCastInst>(GEP->getOperand(0)) && 1369249423Sdim GEP->accumulateConstantOffset(*TD, Offset)) { 1370202375Srdivacky // Get the base pointer input of the bitcast, and the type it points to. 1371202375Srdivacky Value *OrigBase = cast<BitCastInst>(GEP->getOperand(0))->getOperand(0); 1372226633Sdim Type *GEPIdxTy = 1373202375Srdivacky cast<PointerType>(OrigBase->getType())->getElementType(); 1374202375Srdivacky SmallVector<Value*, 8> NewIndices; 1375249423Sdim if (FindElementAtOffset(GEPIdxTy, Offset.getSExtValue(), NewIndices)) { 1376202375Srdivacky // If we were able to index down into an element, create the GEP 1377202375Srdivacky // and bitcast the result. This eliminates one bitcast, potentially 1378202375Srdivacky // two. 1379202375Srdivacky Value *NGEP = cast<GEPOperator>(GEP)->isInBounds() ? 1380226633Sdim Builder->CreateInBoundsGEP(OrigBase, NewIndices) : 1381226633Sdim Builder->CreateGEP(OrigBase, NewIndices); 1382202375Srdivacky NGEP->takeName(GEP); 1383249423Sdim 1384202375Srdivacky if (isa<BitCastInst>(CI)) 1385202375Srdivacky return new BitCastInst(NGEP, CI.getType()); 1386202375Srdivacky assert(isa<PtrToIntInst>(CI)); 1387202375Srdivacky return new PtrToIntInst(NGEP, CI.getType()); 1388249423Sdim } 1389202375Srdivacky } 1390202375Srdivacky } 1391249423Sdim 1392202375Srdivacky return commonCastTransforms(CI); 1393202375Srdivacky} 1394202375Srdivacky 1395202375SrdivackyInstruction *InstCombiner::visitPtrToInt(PtrToIntInst &CI) { 1396203954Srdivacky // If the destination integer type is not the intptr_t type for this target, 1397203954Srdivacky // do a ptrtoint to intptr_t then do a trunc or zext. This allows the cast 1398203954Srdivacky // to be exposed to other transforms. 1399249423Sdim if (TD && CI.getType()->getScalarSizeInBits() != TD->getPointerSizeInBits()) { 1400249423Sdim Type *Ty = TD->getIntPtrType(CI.getContext()); 1401249423Sdim if (CI.getType()->isVectorTy()) // Handle vectors of pointers. 1402249423Sdim Ty = VectorType::get(Ty, CI.getType()->getVectorNumElements()); 1403249423Sdim 1404249423Sdim Value *P = Builder->CreatePtrToInt(CI.getOperand(0), Ty); 1405249423Sdim return CastInst::CreateIntegerCast(P, CI.getType(), /*isSigned=*/false); 1406202375Srdivacky } 1407249423Sdim 1408202375Srdivacky return commonPointerCastTransforms(CI); 1409202375Srdivacky} 1410202375Srdivacky 1411208599Srdivacky/// OptimizeVectorResize - This input value (which is known to have vector type) 1412208599Srdivacky/// is being zero extended or truncated to the specified vector type. Try to 1413208599Srdivacky/// replace it with a shuffle (and vector/vector bitcast) if possible. 1414208599Srdivacky/// 1415208599Srdivacky/// The source and destination vector types may have different element types. 1416226633Sdimstatic Instruction *OptimizeVectorResize(Value *InVal, VectorType *DestTy, 1417208599Srdivacky InstCombiner &IC) { 1418208599Srdivacky // We can only do this optimization if the output is a multiple of the input 1419208599Srdivacky // element size, or the input is a multiple of the output element size. 1420208599Srdivacky // Convert the input type to have the same element type as the output. 1421226633Sdim VectorType *SrcTy = cast<VectorType>(InVal->getType()); 1422249423Sdim 1423208599Srdivacky if (SrcTy->getElementType() != DestTy->getElementType()) { 1424208599Srdivacky // The input types don't need to be identical, but for now they must be the 1425208599Srdivacky // same size. There is no specific reason we couldn't handle things like 1426208599Srdivacky // <4 x i16> -> <4 x i32> by bitcasting to <2 x i32> but haven't gotten 1427249423Sdim // there yet. 1428208599Srdivacky if (SrcTy->getElementType()->getPrimitiveSizeInBits() != 1429208599Srdivacky DestTy->getElementType()->getPrimitiveSizeInBits()) 1430208599Srdivacky return 0; 1431249423Sdim 1432208599Srdivacky SrcTy = VectorType::get(DestTy->getElementType(), SrcTy->getNumElements()); 1433208599Srdivacky InVal = IC.Builder->CreateBitCast(InVal, SrcTy); 1434208599Srdivacky } 1435249423Sdim 1436208599Srdivacky // Now that the element types match, get the shuffle mask and RHS of the 1437208599Srdivacky // shuffle to use, which depends on whether we're increasing or decreasing the 1438208599Srdivacky // size of the input. 1439234353Sdim SmallVector<uint32_t, 16> ShuffleMask; 1440208599Srdivacky Value *V2; 1441249423Sdim 1442208599Srdivacky if (SrcTy->getNumElements() > DestTy->getNumElements()) { 1443208599Srdivacky // If we're shrinking the number of elements, just shuffle in the low 1444208599Srdivacky // elements from the input and use undef as the second shuffle input. 1445208599Srdivacky V2 = UndefValue::get(SrcTy); 1446208599Srdivacky for (unsigned i = 0, e = DestTy->getNumElements(); i != e; ++i) 1447234353Sdim ShuffleMask.push_back(i); 1448249423Sdim 1449208599Srdivacky } else { 1450208599Srdivacky // If we're increasing the number of elements, shuffle in all of the 1451208599Srdivacky // elements from InVal and fill the rest of the result elements with zeros 1452208599Srdivacky // from a constant zero. 1453208599Srdivacky V2 = Constant::getNullValue(SrcTy); 1454208599Srdivacky unsigned SrcElts = SrcTy->getNumElements(); 1455208599Srdivacky for (unsigned i = 0, e = SrcElts; i != e; ++i) 1456234353Sdim ShuffleMask.push_back(i); 1457208599Srdivacky 1458208599Srdivacky // The excess elements reference the first element of the zero input. 1459234353Sdim for (unsigned i = 0, e = DestTy->getNumElements()-SrcElts; i != e; ++i) 1460234353Sdim ShuffleMask.push_back(SrcElts); 1461208599Srdivacky } 1462249423Sdim 1463234353Sdim return new ShuffleVectorInst(InVal, V2, 1464234353Sdim ConstantDataVector::get(V2->getContext(), 1465234353Sdim ShuffleMask)); 1466208599Srdivacky} 1467208599Srdivacky 1468226633Sdimstatic bool isMultipleOfTypeSize(unsigned Value, Type *Ty) { 1469212904Sdim return Value % Ty->getPrimitiveSizeInBits() == 0; 1470212904Sdim} 1471208599Srdivacky 1472226633Sdimstatic unsigned getTypeSizeIndex(unsigned Value, Type *Ty) { 1473212904Sdim return Value / Ty->getPrimitiveSizeInBits(); 1474212904Sdim} 1475212904Sdim 1476212904Sdim/// CollectInsertionElements - V is a value which is inserted into a vector of 1477212904Sdim/// VecEltTy. Look through the value to see if we can decompose it into 1478212904Sdim/// insertions into the vector. See the example in the comment for 1479212904Sdim/// OptimizeIntegerToVectorInsertions for the pattern this handles. 1480212904Sdim/// The type of V is always a non-zero multiple of VecEltTy's size. 1481212904Sdim/// 1482212904Sdim/// This returns false if the pattern can't be matched or true if it can, 1483212904Sdim/// filling in Elements with the elements found here. 1484212904Sdimstatic bool CollectInsertionElements(Value *V, unsigned ElementIndex, 1485212904Sdim SmallVectorImpl<Value*> &Elements, 1486226633Sdim Type *VecEltTy) { 1487212904Sdim // Undef values never contribute useful bits to the result. 1488212904Sdim if (isa<UndefValue>(V)) return true; 1489249423Sdim 1490212904Sdim // If we got down to a value of the right type, we win, try inserting into the 1491212904Sdim // right element. 1492212904Sdim if (V->getType() == VecEltTy) { 1493212904Sdim // Inserting null doesn't actually insert any elements. 1494212904Sdim if (Constant *C = dyn_cast<Constant>(V)) 1495212904Sdim if (C->isNullValue()) 1496212904Sdim return true; 1497249423Sdim 1498212904Sdim // Fail if multiple elements are inserted into this slot. 1499212904Sdim if (ElementIndex >= Elements.size() || Elements[ElementIndex] != 0) 1500212904Sdim return false; 1501249423Sdim 1502212904Sdim Elements[ElementIndex] = V; 1503212904Sdim return true; 1504212904Sdim } 1505249423Sdim 1506212904Sdim if (Constant *C = dyn_cast<Constant>(V)) { 1507212904Sdim // Figure out the # elements this provides, and bitcast it or slice it up 1508212904Sdim // as required. 1509212904Sdim unsigned NumElts = getTypeSizeIndex(C->getType()->getPrimitiveSizeInBits(), 1510212904Sdim VecEltTy); 1511212904Sdim // If the constant is the size of a vector element, we just need to bitcast 1512212904Sdim // it to the right type so it gets properly inserted. 1513212904Sdim if (NumElts == 1) 1514212904Sdim return CollectInsertionElements(ConstantExpr::getBitCast(C, VecEltTy), 1515212904Sdim ElementIndex, Elements, VecEltTy); 1516249423Sdim 1517212904Sdim // Okay, this is a constant that covers multiple elements. Slice it up into 1518212904Sdim // pieces and insert each element-sized piece into the vector. 1519212904Sdim if (!isa<IntegerType>(C->getType())) 1520212904Sdim C = ConstantExpr::getBitCast(C, IntegerType::get(V->getContext(), 1521212904Sdim C->getType()->getPrimitiveSizeInBits())); 1522212904Sdim unsigned ElementSize = VecEltTy->getPrimitiveSizeInBits(); 1523226633Sdim Type *ElementIntTy = IntegerType::get(C->getContext(), ElementSize); 1524249423Sdim 1525212904Sdim for (unsigned i = 0; i != NumElts; ++i) { 1526212904Sdim Constant *Piece = ConstantExpr::getLShr(C, ConstantInt::get(C->getType(), 1527212904Sdim i*ElementSize)); 1528212904Sdim Piece = ConstantExpr::getTrunc(Piece, ElementIntTy); 1529212904Sdim if (!CollectInsertionElements(Piece, ElementIndex+i, Elements, VecEltTy)) 1530212904Sdim return false; 1531212904Sdim } 1532212904Sdim return true; 1533212904Sdim } 1534249423Sdim 1535212904Sdim if (!V->hasOneUse()) return false; 1536249423Sdim 1537212904Sdim Instruction *I = dyn_cast<Instruction>(V); 1538212904Sdim if (I == 0) return false; 1539212904Sdim switch (I->getOpcode()) { 1540212904Sdim default: return false; // Unhandled case. 1541212904Sdim case Instruction::BitCast: 1542212904Sdim return CollectInsertionElements(I->getOperand(0), ElementIndex, 1543249423Sdim Elements, VecEltTy); 1544212904Sdim case Instruction::ZExt: 1545212904Sdim if (!isMultipleOfTypeSize( 1546212904Sdim I->getOperand(0)->getType()->getPrimitiveSizeInBits(), 1547212904Sdim VecEltTy)) 1548212904Sdim return false; 1549212904Sdim return CollectInsertionElements(I->getOperand(0), ElementIndex, 1550249423Sdim Elements, VecEltTy); 1551212904Sdim case Instruction::Or: 1552212904Sdim return CollectInsertionElements(I->getOperand(0), ElementIndex, 1553212904Sdim Elements, VecEltTy) && 1554212904Sdim CollectInsertionElements(I->getOperand(1), ElementIndex, 1555212904Sdim Elements, VecEltTy); 1556212904Sdim case Instruction::Shl: { 1557212904Sdim // Must be shifting by a constant that is a multiple of the element size. 1558212904Sdim ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1)); 1559212904Sdim if (CI == 0) return false; 1560212904Sdim if (!isMultipleOfTypeSize(CI->getZExtValue(), VecEltTy)) return false; 1561212904Sdim unsigned IndexShift = getTypeSizeIndex(CI->getZExtValue(), VecEltTy); 1562249423Sdim 1563212904Sdim return CollectInsertionElements(I->getOperand(0), ElementIndex+IndexShift, 1564212904Sdim Elements, VecEltTy); 1565212904Sdim } 1566249423Sdim 1567212904Sdim } 1568212904Sdim} 1569212904Sdim 1570212904Sdim 1571212904Sdim/// OptimizeIntegerToVectorInsertions - If the input is an 'or' instruction, we 1572212904Sdim/// may be doing shifts and ors to assemble the elements of the vector manually. 1573212904Sdim/// Try to rip the code out and replace it with insertelements. This is to 1574212904Sdim/// optimize code like this: 1575212904Sdim/// 1576212904Sdim/// %tmp37 = bitcast float %inc to i32 1577212904Sdim/// %tmp38 = zext i32 %tmp37 to i64 1578212904Sdim/// %tmp31 = bitcast float %inc5 to i32 1579212904Sdim/// %tmp32 = zext i32 %tmp31 to i64 1580212904Sdim/// %tmp33 = shl i64 %tmp32, 32 1581212904Sdim/// %ins35 = or i64 %tmp33, %tmp38 1582212904Sdim/// %tmp43 = bitcast i64 %ins35 to <2 x float> 1583212904Sdim/// 1584212904Sdim/// Into two insertelements that do "buildvector{%inc, %inc5}". 1585212904Sdimstatic Value *OptimizeIntegerToVectorInsertions(BitCastInst &CI, 1586212904Sdim InstCombiner &IC) { 1587226633Sdim VectorType *DestVecTy = cast<VectorType>(CI.getType()); 1588212904Sdim Value *IntInput = CI.getOperand(0); 1589212904Sdim 1590212904Sdim SmallVector<Value*, 8> Elements(DestVecTy->getNumElements()); 1591212904Sdim if (!CollectInsertionElements(IntInput, 0, Elements, 1592212904Sdim DestVecTy->getElementType())) 1593212904Sdim return 0; 1594212904Sdim 1595212904Sdim // If we succeeded, we know that all of the element are specified by Elements 1596212904Sdim // or are zero if Elements has a null entry. Recast this as a set of 1597212904Sdim // insertions. 1598212904Sdim Value *Result = Constant::getNullValue(CI.getType()); 1599212904Sdim for (unsigned i = 0, e = Elements.size(); i != e; ++i) { 1600212904Sdim if (Elements[i] == 0) continue; // Unset element. 1601249423Sdim 1602212904Sdim Result = IC.Builder->CreateInsertElement(Result, Elements[i], 1603212904Sdim IC.Builder->getInt32(i)); 1604212904Sdim } 1605249423Sdim 1606212904Sdim return Result; 1607212904Sdim} 1608212904Sdim 1609212904Sdim 1610212904Sdim/// OptimizeIntToFloatBitCast - See if we can optimize an integer->float/double 1611212904Sdim/// bitcast. The various long double bitcasts can't get in here. 1612212904Sdimstatic Instruction *OptimizeIntToFloatBitCast(BitCastInst &CI,InstCombiner &IC){ 1613249423Sdim // We need to know the target byte order to perform this optimization. 1614249423Sdim if (!IC.getDataLayout()) return 0; 1615249423Sdim 1616212904Sdim Value *Src = CI.getOperand(0); 1617226633Sdim Type *DestTy = CI.getType(); 1618212904Sdim 1619212904Sdim // If this is a bitcast from int to float, check to see if the int is an 1620212904Sdim // extraction from a vector. 1621212904Sdim Value *VecInput = 0; 1622212904Sdim // bitcast(trunc(bitcast(somevector))) 1623212904Sdim if (match(Src, m_Trunc(m_BitCast(m_Value(VecInput)))) && 1624212904Sdim isa<VectorType>(VecInput->getType())) { 1625226633Sdim VectorType *VecTy = cast<VectorType>(VecInput->getType()); 1626212904Sdim unsigned DestWidth = DestTy->getPrimitiveSizeInBits(); 1627212904Sdim 1628212904Sdim if (VecTy->getPrimitiveSizeInBits() % DestWidth == 0) { 1629212904Sdim // If the element type of the vector doesn't match the result type, 1630212904Sdim // bitcast it to be a vector type we can extract from. 1631212904Sdim if (VecTy->getElementType() != DestTy) { 1632212904Sdim VecTy = VectorType::get(DestTy, 1633212904Sdim VecTy->getPrimitiveSizeInBits() / DestWidth); 1634212904Sdim VecInput = IC.Builder->CreateBitCast(VecInput, VecTy); 1635212904Sdim } 1636249423Sdim 1637249423Sdim unsigned Elt = 0; 1638249423Sdim if (IC.getDataLayout()->isBigEndian()) 1639249423Sdim Elt = VecTy->getPrimitiveSizeInBits() / DestWidth - 1; 1640249423Sdim return ExtractElementInst::Create(VecInput, IC.Builder->getInt32(Elt)); 1641212904Sdim } 1642212904Sdim } 1643249423Sdim 1644212904Sdim // bitcast(trunc(lshr(bitcast(somevector), cst)) 1645212904Sdim ConstantInt *ShAmt = 0; 1646212904Sdim if (match(Src, m_Trunc(m_LShr(m_BitCast(m_Value(VecInput)), 1647212904Sdim m_ConstantInt(ShAmt)))) && 1648212904Sdim isa<VectorType>(VecInput->getType())) { 1649226633Sdim VectorType *VecTy = cast<VectorType>(VecInput->getType()); 1650212904Sdim unsigned DestWidth = DestTy->getPrimitiveSizeInBits(); 1651212904Sdim if (VecTy->getPrimitiveSizeInBits() % DestWidth == 0 && 1652212904Sdim ShAmt->getZExtValue() % DestWidth == 0) { 1653212904Sdim // If the element type of the vector doesn't match the result type, 1654212904Sdim // bitcast it to be a vector type we can extract from. 1655212904Sdim if (VecTy->getElementType() != DestTy) { 1656212904Sdim VecTy = VectorType::get(DestTy, 1657212904Sdim VecTy->getPrimitiveSizeInBits() / DestWidth); 1658212904Sdim VecInput = IC.Builder->CreateBitCast(VecInput, VecTy); 1659212904Sdim } 1660249423Sdim 1661212904Sdim unsigned Elt = ShAmt->getZExtValue() / DestWidth; 1662249423Sdim if (IC.getDataLayout()->isBigEndian()) 1663249423Sdim Elt = VecTy->getPrimitiveSizeInBits() / DestWidth - 1 - Elt; 1664212904Sdim return ExtractElementInst::Create(VecInput, IC.Builder->getInt32(Elt)); 1665212904Sdim } 1666212904Sdim } 1667212904Sdim return 0; 1668212904Sdim} 1669212904Sdim 1670202375SrdivackyInstruction *InstCombiner::visitBitCast(BitCastInst &CI) { 1671202375Srdivacky // If the operands are integer typed then apply the integer transforms, 1672202375Srdivacky // otherwise just apply the common ones. 1673202375Srdivacky Value *Src = CI.getOperand(0); 1674226633Sdim Type *SrcTy = Src->getType(); 1675226633Sdim Type *DestTy = CI.getType(); 1676202375Srdivacky 1677202375Srdivacky // Get rid of casts from one type to the same type. These are useless and can 1678202375Srdivacky // be replaced by the operand. 1679202375Srdivacky if (DestTy == Src->getType()) 1680202375Srdivacky return ReplaceInstUsesWith(CI, Src); 1681202375Srdivacky 1682226633Sdim if (PointerType *DstPTy = dyn_cast<PointerType>(DestTy)) { 1683226633Sdim PointerType *SrcPTy = cast<PointerType>(SrcTy); 1684226633Sdim Type *DstElTy = DstPTy->getElementType(); 1685226633Sdim Type *SrcElTy = SrcPTy->getElementType(); 1686249423Sdim 1687202375Srdivacky // If the address spaces don't match, don't eliminate the bitcast, which is 1688202375Srdivacky // required for changing types. 1689202375Srdivacky if (SrcPTy->getAddressSpace() != DstPTy->getAddressSpace()) 1690202375Srdivacky return 0; 1691249423Sdim 1692202375Srdivacky // If we are casting a alloca to a pointer to a type of the same 1693202375Srdivacky // size, rewrite the allocation instruction to allocate the "right" type. 1694202375Srdivacky // There is no need to modify malloc calls because it is their bitcast that 1695202375Srdivacky // needs to be cleaned up. 1696202375Srdivacky if (AllocaInst *AI = dyn_cast<AllocaInst>(Src)) 1697202375Srdivacky if (Instruction *V = PromoteCastOfAllocation(CI, *AI)) 1698202375Srdivacky return V; 1699249423Sdim 1700202375Srdivacky // If the source and destination are pointers, and this cast is equivalent 1701202375Srdivacky // to a getelementptr X, 0, 0, 0... turn it into the appropriate gep. 1702202375Srdivacky // This can enhance SROA and other transforms that want type-safe pointers. 1703202375Srdivacky Constant *ZeroUInt = 1704202375Srdivacky Constant::getNullValue(Type::getInt32Ty(CI.getContext())); 1705202375Srdivacky unsigned NumZeros = 0; 1706249423Sdim while (SrcElTy != DstElTy && 1707204642Srdivacky isa<CompositeType>(SrcElTy) && !SrcElTy->isPointerTy() && 1708202375Srdivacky SrcElTy->getNumContainedTypes() /* not "{}" */) { 1709202375Srdivacky SrcElTy = cast<CompositeType>(SrcElTy)->getTypeAtIndex(ZeroUInt); 1710202375Srdivacky ++NumZeros; 1711202375Srdivacky } 1712202375Srdivacky 1713202375Srdivacky // If we found a path from the src to dest, create the getelementptr now. 1714202375Srdivacky if (SrcElTy == DstElTy) { 1715202375Srdivacky SmallVector<Value*, 8> Idxs(NumZeros+1, ZeroUInt); 1716226633Sdim return GetElementPtrInst::CreateInBounds(Src, Idxs); 1717202375Srdivacky } 1718202375Srdivacky } 1719249423Sdim 1720212904Sdim // Try to optimize int -> float bitcasts. 1721212904Sdim if ((DestTy->isFloatTy() || DestTy->isDoubleTy()) && isa<IntegerType>(SrcTy)) 1722212904Sdim if (Instruction *I = OptimizeIntToFloatBitCast(CI, *this)) 1723212904Sdim return I; 1724202375Srdivacky 1725226633Sdim if (VectorType *DestVTy = dyn_cast<VectorType>(DestTy)) { 1726204642Srdivacky if (DestVTy->getNumElements() == 1 && !SrcTy->isVectorTy()) { 1727202375Srdivacky Value *Elem = Builder->CreateBitCast(Src, DestVTy->getElementType()); 1728202375Srdivacky return InsertElementInst::Create(UndefValue::get(DestTy), Elem, 1729202375Srdivacky Constant::getNullValue(Type::getInt32Ty(CI.getContext()))); 1730202375Srdivacky // FIXME: Canonicalize bitcast(insertelement) -> insertelement(bitcast) 1731202375Srdivacky } 1732249423Sdim 1733212904Sdim if (isa<IntegerType>(SrcTy)) { 1734212904Sdim // If this is a cast from an integer to vector, check to see if the input 1735212904Sdim // is a trunc or zext of a bitcast from vector. If so, we can replace all 1736212904Sdim // the casts with a shuffle and (potentially) a bitcast. 1737212904Sdim if (isa<TruncInst>(Src) || isa<ZExtInst>(Src)) { 1738212904Sdim CastInst *SrcCast = cast<CastInst>(Src); 1739212904Sdim if (BitCastInst *BCIn = dyn_cast<BitCastInst>(SrcCast->getOperand(0))) 1740212904Sdim if (isa<VectorType>(BCIn->getOperand(0)->getType())) 1741212904Sdim if (Instruction *I = OptimizeVectorResize(BCIn->getOperand(0), 1742208599Srdivacky cast<VectorType>(DestTy), *this)) 1743212904Sdim return I; 1744212904Sdim } 1745249423Sdim 1746212904Sdim // If the input is an 'or' instruction, we may be doing shifts and ors to 1747212904Sdim // assemble the elements of the vector manually. Try to rip the code out 1748212904Sdim // and replace it with insertelements. 1749212904Sdim if (Value *V = OptimizeIntegerToVectorInsertions(CI, *this)) 1750212904Sdim return ReplaceInstUsesWith(CI, V); 1751208599Srdivacky } 1752202375Srdivacky } 1753202375Srdivacky 1754226633Sdim if (VectorType *SrcVTy = dyn_cast<VectorType>(SrcTy)) { 1755249423Sdim if (SrcVTy->getNumElements() == 1) { 1756249423Sdim // If our destination is not a vector, then make this a straight 1757249423Sdim // scalar-scalar cast. 1758249423Sdim if (!DestTy->isVectorTy()) { 1759249423Sdim Value *Elem = 1760249423Sdim Builder->CreateExtractElement(Src, 1761249423Sdim Constant::getNullValue(Type::getInt32Ty(CI.getContext()))); 1762249423Sdim return CastInst::Create(Instruction::BitCast, Elem, DestTy); 1763249423Sdim } 1764249423Sdim 1765249423Sdim // Otherwise, see if our source is an insert. If so, then use the scalar 1766249423Sdim // component directly. 1767249423Sdim if (InsertElementInst *IEI = 1768249423Sdim dyn_cast<InsertElementInst>(CI.getOperand(0))) 1769249423Sdim return CastInst::Create(Instruction::BitCast, IEI->getOperand(1), 1770249423Sdim DestTy); 1771202375Srdivacky } 1772202375Srdivacky } 1773202375Srdivacky 1774202375Srdivacky if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(Src)) { 1775202375Srdivacky // Okay, we have (bitcast (shuffle ..)). Check to see if this is 1776207618Srdivacky // a bitcast to a vector with the same # elts. 1777249423Sdim if (SVI->hasOneUse() && DestTy->isVectorTy() && 1778202375Srdivacky cast<VectorType>(DestTy)->getNumElements() == 1779202375Srdivacky SVI->getType()->getNumElements() && 1780202375Srdivacky SVI->getType()->getNumElements() == 1781202375Srdivacky cast<VectorType>(SVI->getOperand(0)->getType())->getNumElements()) { 1782202375Srdivacky BitCastInst *Tmp; 1783202375Srdivacky // If either of the operands is a cast from CI.getType(), then 1784202375Srdivacky // evaluating the shuffle in the casted destination's type will allow 1785202375Srdivacky // us to eliminate at least one cast. 1786249423Sdim if (((Tmp = dyn_cast<BitCastInst>(SVI->getOperand(0))) && 1787202375Srdivacky Tmp->getOperand(0)->getType() == DestTy) || 1788249423Sdim ((Tmp = dyn_cast<BitCastInst>(SVI->getOperand(1))) && 1789202375Srdivacky Tmp->getOperand(0)->getType() == DestTy)) { 1790202375Srdivacky Value *LHS = Builder->CreateBitCast(SVI->getOperand(0), DestTy); 1791202375Srdivacky Value *RHS = Builder->CreateBitCast(SVI->getOperand(1), DestTy); 1792202375Srdivacky // Return a new shuffle vector. Use the same element ID's, as we 1793202375Srdivacky // know the vector types match #elts. 1794202375Srdivacky return new ShuffleVectorInst(LHS, RHS, SVI->getOperand(2)); 1795202375Srdivacky } 1796202375Srdivacky } 1797202375Srdivacky } 1798249423Sdim 1799204642Srdivacky if (SrcTy->isPointerTy()) 1800202375Srdivacky return commonPointerCastTransforms(CI); 1801202375Srdivacky return commonCastTransforms(CI); 1802202375Srdivacky} 1803