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 if (!CanEvaluateZExtd(I->getOperand(0), Ty, BitsToClear) || 681202375Srdivacky !CanEvaluateZExtd(I->getOperand(1), Ty, Tmp)) 682202375Srdivacky return false; 683202375Srdivacky // These can all be promoted if neither operand has 'bits to clear'. 684202375Srdivacky if (BitsToClear == 0 && Tmp == 0) 685202375Srdivacky return true; 686249423Sdim 687202375Srdivacky // If the operation is an AND/OR/XOR and the bits to clear are zero in the 688202375Srdivacky // other side, BitsToClear is ok. 689202375Srdivacky if (Tmp == 0 && 690202375Srdivacky (Opc == Instruction::And || Opc == Instruction::Or || 691202375Srdivacky Opc == Instruction::Xor)) { 692202375Srdivacky // We use MaskedValueIsZero here for generality, but the case we care 693202375Srdivacky // about the most is constant RHS. 694202375Srdivacky unsigned VSize = V->getType()->getScalarSizeInBits(); 695202375Srdivacky if (MaskedValueIsZero(I->getOperand(1), 696202375Srdivacky APInt::getHighBitsSet(VSize, BitsToClear))) 697202375Srdivacky return true; 698202375Srdivacky } 699249423Sdim 700202375Srdivacky // Otherwise, we don't know how to analyze this BitsToClear case yet. 701202375Srdivacky return false; 702249423Sdim 703263508Sdim case Instruction::Shl: 704263508Sdim // We can promote shl(x, cst) if we can promote x. Since shl overwrites the 705263508Sdim // upper bits we can reduce BitsToClear by the shift amount. 706263508Sdim if (ConstantInt *Amt = dyn_cast<ConstantInt>(I->getOperand(1))) { 707263508Sdim if (!CanEvaluateZExtd(I->getOperand(0), Ty, BitsToClear)) 708263508Sdim return false; 709263508Sdim uint64_t ShiftAmt = Amt->getZExtValue(); 710263508Sdim BitsToClear = ShiftAmt < BitsToClear ? BitsToClear - ShiftAmt : 0; 711263508Sdim return true; 712263508Sdim } 713263508Sdim return false; 714202375Srdivacky case Instruction::LShr: 715202375Srdivacky // We can promote lshr(x, cst) if we can promote x. This requires the 716202375Srdivacky // ultimate 'and' to clear out the high zero bits we're clearing out though. 717202375Srdivacky if (ConstantInt *Amt = dyn_cast<ConstantInt>(I->getOperand(1))) { 718202375Srdivacky if (!CanEvaluateZExtd(I->getOperand(0), Ty, BitsToClear)) 719202375Srdivacky return false; 720202375Srdivacky BitsToClear += Amt->getZExtValue(); 721202375Srdivacky if (BitsToClear > V->getType()->getScalarSizeInBits()) 722202375Srdivacky BitsToClear = V->getType()->getScalarSizeInBits(); 723202375Srdivacky return true; 724202375Srdivacky } 725202375Srdivacky // Cannot promote variable LSHR. 726202375Srdivacky return false; 727202375Srdivacky case Instruction::Select: 728202375Srdivacky if (!CanEvaluateZExtd(I->getOperand(1), Ty, Tmp) || 729202375Srdivacky !CanEvaluateZExtd(I->getOperand(2), Ty, BitsToClear) || 730202375Srdivacky // TODO: If important, we could handle the case when the BitsToClear are 731202375Srdivacky // known zero in the disagreeing side. 732202375Srdivacky Tmp != BitsToClear) 733202375Srdivacky return false; 734202375Srdivacky return true; 735249423Sdim 736202375Srdivacky case Instruction::PHI: { 737202375Srdivacky // We can change a phi if we can change all operands. Note that we never 738202375Srdivacky // get into trouble with cyclic PHIs here because we only consider 739202375Srdivacky // instructions with a single use. 740202375Srdivacky PHINode *PN = cast<PHINode>(I); 741202375Srdivacky if (!CanEvaluateZExtd(PN->getIncomingValue(0), Ty, BitsToClear)) 742202375Srdivacky return false; 743202375Srdivacky for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 744202375Srdivacky if (!CanEvaluateZExtd(PN->getIncomingValue(i), Ty, Tmp) || 745202375Srdivacky // TODO: If important, we could handle the case when the BitsToClear 746202375Srdivacky // are known zero in the disagreeing input. 747202375Srdivacky Tmp != BitsToClear) 748202375Srdivacky return false; 749202375Srdivacky return true; 750202375Srdivacky } 751202375Srdivacky default: 752202375Srdivacky // TODO: Can handle more cases here. 753202375Srdivacky return false; 754202375Srdivacky } 755202375Srdivacky} 756202375Srdivacky 757202375SrdivackyInstruction *InstCombiner::visitZExt(ZExtInst &CI) { 758249423Sdim // If this zero extend is only used by a truncate, let the truncate be 759202375Srdivacky // eliminated before we try to optimize this zext. 760202375Srdivacky if (CI.hasOneUse() && isa<TruncInst>(CI.use_back())) 761202375Srdivacky return 0; 762249423Sdim 763202375Srdivacky // If one of the common conversion will work, do it. 764202375Srdivacky if (Instruction *Result = commonCastTransforms(CI)) 765202375Srdivacky return Result; 766202375Srdivacky 767249423Sdim // See if we can simplify any instructions used by the input whose sole 768202375Srdivacky // purpose is to compute bits we don't care about. 769202375Srdivacky if (SimplifyDemandedInstructionBits(CI)) 770202375Srdivacky return &CI; 771249423Sdim 772202375Srdivacky Value *Src = CI.getOperand(0); 773226633Sdim Type *SrcTy = Src->getType(), *DestTy = CI.getType(); 774249423Sdim 775202375Srdivacky // Attempt to extend the entire input expression tree to the destination 776202375Srdivacky // type. Only do this if the dest type is a simple type, don't convert the 777202375Srdivacky // expression tree to something weird like i93 unless the source is also 778202375Srdivacky // strange. 779202375Srdivacky unsigned BitsToClear; 780204642Srdivacky if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) && 781249423Sdim CanEvaluateZExtd(Src, DestTy, BitsToClear)) { 782202375Srdivacky assert(BitsToClear < SrcTy->getScalarSizeInBits() && 783202375Srdivacky "Unreasonable BitsToClear"); 784249423Sdim 785202375Srdivacky // Okay, we can transform this! Insert the new expression now. 786202375Srdivacky DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type" 787202375Srdivacky " to avoid zero extend: " << CI); 788202375Srdivacky Value *Res = EvaluateInDifferentType(Src, DestTy, false); 789202375Srdivacky assert(Res->getType() == DestTy); 790249423Sdim 791202375Srdivacky uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits()-BitsToClear; 792202375Srdivacky uint32_t DestBitSize = DestTy->getScalarSizeInBits(); 793249423Sdim 794202375Srdivacky // If the high bits are already filled with zeros, just replace this 795202375Srdivacky // cast with the result. 796202375Srdivacky if (MaskedValueIsZero(Res, APInt::getHighBitsSet(DestBitSize, 797202375Srdivacky DestBitSize-SrcBitsKept))) 798202375Srdivacky return ReplaceInstUsesWith(CI, Res); 799249423Sdim 800202375Srdivacky // We need to emit an AND to clear the high bits. 801202375Srdivacky Constant *C = ConstantInt::get(Res->getType(), 802202375Srdivacky APInt::getLowBitsSet(DestBitSize, SrcBitsKept)); 803202375Srdivacky return BinaryOperator::CreateAnd(Res, C); 804202375Srdivacky } 805202375Srdivacky 806202375Srdivacky // If this is a TRUNC followed by a ZEXT then we are dealing with integral 807202375Srdivacky // types and if the sizes are just right we can convert this into a logical 808202375Srdivacky // 'and' which will be much cheaper than the pair of casts. 809202375Srdivacky if (TruncInst *CSrc = dyn_cast<TruncInst>(Src)) { // A->B->C cast 810202375Srdivacky // TODO: Subsume this into EvaluateInDifferentType. 811249423Sdim 812202375Srdivacky // Get the sizes of the types involved. We know that the intermediate type 813202375Srdivacky // will be smaller than A or C, but don't know the relation between A and C. 814202375Srdivacky Value *A = CSrc->getOperand(0); 815202375Srdivacky unsigned SrcSize = A->getType()->getScalarSizeInBits(); 816202375Srdivacky unsigned MidSize = CSrc->getType()->getScalarSizeInBits(); 817202375Srdivacky unsigned DstSize = CI.getType()->getScalarSizeInBits(); 818202375Srdivacky // If we're actually extending zero bits, then if 819202375Srdivacky // SrcSize < DstSize: zext(a & mask) 820202375Srdivacky // SrcSize == DstSize: a & mask 821202375Srdivacky // SrcSize > DstSize: trunc(a) & mask 822202375Srdivacky if (SrcSize < DstSize) { 823202375Srdivacky APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize)); 824202375Srdivacky Constant *AndConst = ConstantInt::get(A->getType(), AndValue); 825202375Srdivacky Value *And = Builder->CreateAnd(A, AndConst, CSrc->getName()+".mask"); 826202375Srdivacky return new ZExtInst(And, CI.getType()); 827202375Srdivacky } 828249423Sdim 829202375Srdivacky if (SrcSize == DstSize) { 830202375Srdivacky APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize)); 831202375Srdivacky return BinaryOperator::CreateAnd(A, ConstantInt::get(A->getType(), 832202375Srdivacky AndValue)); 833202375Srdivacky } 834202375Srdivacky if (SrcSize > DstSize) { 835226633Sdim Value *Trunc = Builder->CreateTrunc(A, CI.getType()); 836202375Srdivacky APInt AndValue(APInt::getLowBitsSet(DstSize, MidSize)); 837249423Sdim return BinaryOperator::CreateAnd(Trunc, 838202375Srdivacky ConstantInt::get(Trunc->getType(), 839202375Srdivacky AndValue)); 840202375Srdivacky } 841202375Srdivacky } 842202375Srdivacky 843202375Srdivacky if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src)) 844202375Srdivacky return transformZExtICmp(ICI, CI); 845202375Srdivacky 846202375Srdivacky BinaryOperator *SrcI = dyn_cast<BinaryOperator>(Src); 847202375Srdivacky if (SrcI && SrcI->getOpcode() == Instruction::Or) { 848202375Srdivacky // zext (or icmp, icmp) --> or (zext icmp), (zext icmp) if at least one 849202375Srdivacky // of the (zext icmp) will be transformed. 850202375Srdivacky ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0)); 851202375Srdivacky ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1)); 852202375Srdivacky if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() && 853202375Srdivacky (transformZExtICmp(LHS, CI, false) || 854202375Srdivacky transformZExtICmp(RHS, CI, false))) { 855202375Srdivacky Value *LCast = Builder->CreateZExt(LHS, CI.getType(), LHS->getName()); 856202375Srdivacky Value *RCast = Builder->CreateZExt(RHS, CI.getType(), RHS->getName()); 857202375Srdivacky return BinaryOperator::Create(Instruction::Or, LCast, RCast); 858202375Srdivacky } 859202375Srdivacky } 860202375Srdivacky 861202375Srdivacky // zext(trunc(t) & C) -> (t & zext(C)). 862202375Srdivacky if (SrcI && SrcI->getOpcode() == Instruction::And && SrcI->hasOneUse()) 863202375Srdivacky if (ConstantInt *C = dyn_cast<ConstantInt>(SrcI->getOperand(1))) 864202375Srdivacky if (TruncInst *TI = dyn_cast<TruncInst>(SrcI->getOperand(0))) { 865202375Srdivacky Value *TI0 = TI->getOperand(0); 866202375Srdivacky if (TI0->getType() == CI.getType()) 867202375Srdivacky return 868202375Srdivacky BinaryOperator::CreateAnd(TI0, 869202375Srdivacky ConstantExpr::getZExt(C, CI.getType())); 870202375Srdivacky } 871202375Srdivacky 872202375Srdivacky // zext((trunc(t) & C) ^ C) -> ((t & zext(C)) ^ zext(C)). 873202375Srdivacky if (SrcI && SrcI->getOpcode() == Instruction::Xor && SrcI->hasOneUse()) 874202375Srdivacky if (ConstantInt *C = dyn_cast<ConstantInt>(SrcI->getOperand(1))) 875202375Srdivacky if (BinaryOperator *And = dyn_cast<BinaryOperator>(SrcI->getOperand(0))) 876202375Srdivacky if (And->getOpcode() == Instruction::And && And->hasOneUse() && 877202375Srdivacky And->getOperand(1) == C) 878202375Srdivacky if (TruncInst *TI = dyn_cast<TruncInst>(And->getOperand(0))) { 879202375Srdivacky Value *TI0 = TI->getOperand(0); 880202375Srdivacky if (TI0->getType() == CI.getType()) { 881202375Srdivacky Constant *ZC = ConstantExpr::getZExt(C, CI.getType()); 882226633Sdim Value *NewAnd = Builder->CreateAnd(TI0, ZC); 883202375Srdivacky return BinaryOperator::CreateXor(NewAnd, ZC); 884202375Srdivacky } 885202375Srdivacky } 886202375Srdivacky 887202375Srdivacky // zext (xor i1 X, true) to i32 --> xor (zext i1 X to i32), 1 888202375Srdivacky Value *X; 889203954Srdivacky if (SrcI && SrcI->hasOneUse() && SrcI->getType()->isIntegerTy(1) && 890202375Srdivacky match(SrcI, m_Not(m_Value(X))) && 891202375Srdivacky (!X->hasOneUse() || !isa<CmpInst>(X))) { 892202375Srdivacky Value *New = Builder->CreateZExt(X, CI.getType()); 893202375Srdivacky return BinaryOperator::CreateXor(New, ConstantInt::get(CI.getType(), 1)); 894202375Srdivacky } 895249423Sdim 896202375Srdivacky return 0; 897202375Srdivacky} 898202375Srdivacky 899221345Sdim/// transformSExtICmp - Transform (sext icmp) to bitwise / integer operations 900221345Sdim/// in order to eliminate the icmp. 901221345SdimInstruction *InstCombiner::transformSExtICmp(ICmpInst *ICI, Instruction &CI) { 902221345Sdim Value *Op0 = ICI->getOperand(0), *Op1 = ICI->getOperand(1); 903221345Sdim ICmpInst::Predicate Pred = ICI->getPredicate(); 904221345Sdim 905221345Sdim if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 906221345Sdim // (x <s 0) ? -1 : 0 -> ashr x, 31 -> all ones if negative 907221345Sdim // (x >s -1) ? -1 : 0 -> not (ashr x, 31) -> all ones if positive 908221345Sdim if ((Pred == ICmpInst::ICMP_SLT && Op1C->isZero()) || 909221345Sdim (Pred == ICmpInst::ICMP_SGT && Op1C->isAllOnesValue())) { 910221345Sdim 911221345Sdim Value *Sh = ConstantInt::get(Op0->getType(), 912221345Sdim Op0->getType()->getScalarSizeInBits()-1); 913221345Sdim Value *In = Builder->CreateAShr(Op0, Sh, Op0->getName()+".lobit"); 914221345Sdim if (In->getType() != CI.getType()) 915226633Sdim In = Builder->CreateIntCast(In, CI.getType(), true/*SExt*/); 916221345Sdim 917221345Sdim if (Pred == ICmpInst::ICMP_SGT) 918221345Sdim In = Builder->CreateNot(In, In->getName()+".not"); 919221345Sdim return ReplaceInstUsesWith(CI, In); 920221345Sdim } 921221345Sdim 922221345Sdim // If we know that only one bit of the LHS of the icmp can be set and we 923221345Sdim // have an equality comparison with zero or a power of 2, we can transform 924221345Sdim // the icmp and sext into bitwise/integer operations. 925221345Sdim if (ICI->hasOneUse() && 926221345Sdim ICI->isEquality() && (Op1C->isZero() || Op1C->getValue().isPowerOf2())){ 927221345Sdim unsigned BitWidth = Op1C->getType()->getBitWidth(); 928221345Sdim APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 929234353Sdim ComputeMaskedBits(Op0, KnownZero, KnownOne); 930221345Sdim 931221345Sdim APInt KnownZeroMask(~KnownZero); 932221345Sdim if (KnownZeroMask.isPowerOf2()) { 933221345Sdim Value *In = ICI->getOperand(0); 934221345Sdim 935221345Sdim // If the icmp tests for a known zero bit we can constant fold it. 936221345Sdim if (!Op1C->isZero() && Op1C->getValue() != KnownZeroMask) { 937221345Sdim Value *V = Pred == ICmpInst::ICMP_NE ? 938221345Sdim ConstantInt::getAllOnesValue(CI.getType()) : 939221345Sdim ConstantInt::getNullValue(CI.getType()); 940221345Sdim return ReplaceInstUsesWith(CI, V); 941221345Sdim } 942221345Sdim 943221345Sdim if (!Op1C->isZero() == (Pred == ICmpInst::ICMP_NE)) { 944221345Sdim // sext ((x & 2^n) == 0) -> (x >> n) - 1 945221345Sdim // sext ((x & 2^n) != 2^n) -> (x >> n) - 1 946221345Sdim unsigned ShiftAmt = KnownZeroMask.countTrailingZeros(); 947221345Sdim // Perform a right shift to place the desired bit in the LSB. 948221345Sdim if (ShiftAmt) 949221345Sdim In = Builder->CreateLShr(In, 950221345Sdim ConstantInt::get(In->getType(), ShiftAmt)); 951221345Sdim 952221345Sdim // At this point "In" is either 1 or 0. Subtract 1 to turn 953221345Sdim // {1, 0} -> {0, -1}. 954221345Sdim In = Builder->CreateAdd(In, 955221345Sdim ConstantInt::getAllOnesValue(In->getType()), 956221345Sdim "sext"); 957221345Sdim } else { 958221345Sdim // sext ((x & 2^n) != 0) -> (x << bitwidth-n) a>> bitwidth-1 959221345Sdim // sext ((x & 2^n) == 2^n) -> (x << bitwidth-n) a>> bitwidth-1 960221345Sdim unsigned ShiftAmt = KnownZeroMask.countLeadingZeros(); 961221345Sdim // Perform a left shift to place the desired bit in the MSB. 962221345Sdim if (ShiftAmt) 963221345Sdim In = Builder->CreateShl(In, 964221345Sdim ConstantInt::get(In->getType(), ShiftAmt)); 965221345Sdim 966221345Sdim // Distribute the bit over the whole bit width. 967221345Sdim In = Builder->CreateAShr(In, ConstantInt::get(In->getType(), 968221345Sdim BitWidth - 1), "sext"); 969221345Sdim } 970221345Sdim 971221345Sdim if (CI.getType() == In->getType()) 972221345Sdim return ReplaceInstUsesWith(CI, In); 973221345Sdim return CastInst::CreateIntegerCast(In, CI.getType(), true/*SExt*/); 974221345Sdim } 975221345Sdim } 976221345Sdim } 977221345Sdim 978221345Sdim // vector (x <s 0) ? -1 : 0 -> ashr x, 31 -> all ones if signed. 979226633Sdim if (VectorType *VTy = dyn_cast<VectorType>(CI.getType())) { 980221345Sdim if (Pred == ICmpInst::ICMP_SLT && match(Op1, m_Zero()) && 981221345Sdim Op0->getType() == CI.getType()) { 982226633Sdim Type *EltTy = VTy->getElementType(); 983221345Sdim 984221345Sdim // splat the shift constant to a constant vector. 985221345Sdim Constant *VSh = ConstantInt::get(VTy, EltTy->getScalarSizeInBits()-1); 986221345Sdim Value *In = Builder->CreateAShr(Op0, VSh, Op0->getName()+".lobit"); 987221345Sdim return ReplaceInstUsesWith(CI, In); 988221345Sdim } 989221345Sdim } 990221345Sdim 991221345Sdim return 0; 992221345Sdim} 993221345Sdim 994202375Srdivacky/// CanEvaluateSExtd - Return true if we can take the specified value 995202375Srdivacky/// and return it as type Ty without inserting any new casts and without 996202375Srdivacky/// changing the value of the common low bits. This is used by code that tries 997202375Srdivacky/// to promote integer operations to a wider types will allow us to eliminate 998202375Srdivacky/// the extension. 999202375Srdivacky/// 1000202375Srdivacky/// This function works on both vectors and scalars. 1001202375Srdivacky/// 1002226633Sdimstatic bool CanEvaluateSExtd(Value *V, Type *Ty) { 1003202375Srdivacky assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() && 1004202375Srdivacky "Can't sign extend type to a smaller type"); 1005202375Srdivacky // If this is a constant, it can be trivially promoted. 1006202375Srdivacky if (isa<Constant>(V)) 1007202375Srdivacky return true; 1008249423Sdim 1009202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 1010202375Srdivacky if (!I) return false; 1011249423Sdim 1012239462Sdim // If this is a truncate from the dest type, we can trivially eliminate it. 1013239462Sdim if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty) 1014202375Srdivacky return true; 1015249423Sdim 1016202375Srdivacky // We can't extend or shrink something that has multiple uses: doing so would 1017202375Srdivacky // require duplicating the instruction in general, which isn't profitable. 1018202375Srdivacky if (!I->hasOneUse()) return false; 1019202375Srdivacky 1020202375Srdivacky switch (I->getOpcode()) { 1021202375Srdivacky case Instruction::SExt: // sext(sext(x)) -> sext(x) 1022202375Srdivacky case Instruction::ZExt: // sext(zext(x)) -> zext(x) 1023202375Srdivacky case Instruction::Trunc: // sext(trunc(x)) -> trunc(x) or sext(x) 1024202375Srdivacky return true; 1025202375Srdivacky case Instruction::And: 1026202375Srdivacky case Instruction::Or: 1027202375Srdivacky case Instruction::Xor: 1028202375Srdivacky case Instruction::Add: 1029202375Srdivacky case Instruction::Sub: 1030202375Srdivacky case Instruction::Mul: 1031202375Srdivacky // These operators can all arbitrarily be extended if their inputs can. 1032202375Srdivacky return CanEvaluateSExtd(I->getOperand(0), Ty) && 1033202375Srdivacky CanEvaluateSExtd(I->getOperand(1), Ty); 1034249423Sdim 1035202375Srdivacky //case Instruction::Shl: TODO 1036202375Srdivacky //case Instruction::LShr: TODO 1037249423Sdim 1038202375Srdivacky case Instruction::Select: 1039202375Srdivacky return CanEvaluateSExtd(I->getOperand(1), Ty) && 1040202375Srdivacky CanEvaluateSExtd(I->getOperand(2), Ty); 1041249423Sdim 1042202375Srdivacky case Instruction::PHI: { 1043202375Srdivacky // We can change a phi if we can change all operands. Note that we never 1044202375Srdivacky // get into trouble with cyclic PHIs here because we only consider 1045202375Srdivacky // instructions with a single use. 1046202375Srdivacky PHINode *PN = cast<PHINode>(I); 1047202375Srdivacky for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1048202375Srdivacky if (!CanEvaluateSExtd(PN->getIncomingValue(i), Ty)) return false; 1049202375Srdivacky return true; 1050202375Srdivacky } 1051202375Srdivacky default: 1052202375Srdivacky // TODO: Can handle more cases here. 1053202375Srdivacky break; 1054202375Srdivacky } 1055249423Sdim 1056202375Srdivacky return false; 1057202375Srdivacky} 1058202375Srdivacky 1059202375SrdivackyInstruction *InstCombiner::visitSExt(SExtInst &CI) { 1060249423Sdim // If this sign extend is only used by a truncate, let the truncate be 1061249423Sdim // eliminated before we try to optimize this sext. 1062202375Srdivacky if (CI.hasOneUse() && isa<TruncInst>(CI.use_back())) 1063202375Srdivacky return 0; 1064249423Sdim 1065202375Srdivacky if (Instruction *I = commonCastTransforms(CI)) 1066202375Srdivacky return I; 1067249423Sdim 1068249423Sdim // See if we can simplify any instructions used by the input whose sole 1069202375Srdivacky // purpose is to compute bits we don't care about. 1070202375Srdivacky if (SimplifyDemandedInstructionBits(CI)) 1071202375Srdivacky return &CI; 1072249423Sdim 1073202375Srdivacky Value *Src = CI.getOperand(0); 1074226633Sdim Type *SrcTy = Src->getType(), *DestTy = CI.getType(); 1075202375Srdivacky 1076202375Srdivacky // Attempt to extend the entire input expression tree to the destination 1077202375Srdivacky // type. Only do this if the dest type is a simple type, don't convert the 1078202375Srdivacky // expression tree to something weird like i93 unless the source is also 1079202375Srdivacky // strange. 1080204642Srdivacky if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) && 1081202375Srdivacky CanEvaluateSExtd(Src, DestTy)) { 1082202375Srdivacky // Okay, we can transform this! Insert the new expression now. 1083202375Srdivacky DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type" 1084202375Srdivacky " to avoid sign extend: " << CI); 1085202375Srdivacky Value *Res = EvaluateInDifferentType(Src, DestTy, true); 1086202375Srdivacky assert(Res->getType() == DestTy); 1087202375Srdivacky 1088202375Srdivacky uint32_t SrcBitSize = SrcTy->getScalarSizeInBits(); 1089202375Srdivacky uint32_t DestBitSize = DestTy->getScalarSizeInBits(); 1090202375Srdivacky 1091202375Srdivacky // If the high bits are already filled with sign bit, just replace this 1092202375Srdivacky // cast with the result. 1093202375Srdivacky if (ComputeNumSignBits(Res) > DestBitSize - SrcBitSize) 1094202375Srdivacky return ReplaceInstUsesWith(CI, Res); 1095249423Sdim 1096202375Srdivacky // We need to emit a shl + ashr to do the sign extend. 1097202375Srdivacky Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize); 1098202375Srdivacky return BinaryOperator::CreateAShr(Builder->CreateShl(Res, ShAmt, "sext"), 1099202375Srdivacky ShAmt); 1100202375Srdivacky } 1101202375Srdivacky 1102202878Srdivacky // If this input is a trunc from our destination, then turn sext(trunc(x)) 1103202878Srdivacky // into shifts. 1104202878Srdivacky if (TruncInst *TI = dyn_cast<TruncInst>(Src)) 1105202878Srdivacky if (TI->hasOneUse() && TI->getOperand(0)->getType() == DestTy) { 1106202878Srdivacky uint32_t SrcBitSize = SrcTy->getScalarSizeInBits(); 1107202878Srdivacky uint32_t DestBitSize = DestTy->getScalarSizeInBits(); 1108249423Sdim 1109202878Srdivacky // We need to emit a shl + ashr to do the sign extend. 1110202878Srdivacky Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize); 1111202878Srdivacky Value *Res = Builder->CreateShl(TI->getOperand(0), ShAmt, "sext"); 1112202878Srdivacky return BinaryOperator::CreateAShr(Res, ShAmt); 1113202878Srdivacky } 1114218893Sdim 1115221345Sdim if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src)) 1116221345Sdim return transformSExtICmp(ICI, CI); 1117218893Sdim 1118202375Srdivacky // If the input is a shl/ashr pair of a same constant, then this is a sign 1119202375Srdivacky // extension from a smaller value. If we could trust arbitrary bitwidth 1120202375Srdivacky // integers, we could turn this into a truncate to the smaller bit and then 1121202375Srdivacky // use a sext for the whole extension. Since we don't, look deeper and check 1122202375Srdivacky // for a truncate. If the source and dest are the same type, eliminate the 1123202375Srdivacky // trunc and extend and just do shifts. For example, turn: 1124202375Srdivacky // %a = trunc i32 %i to i8 1125202375Srdivacky // %b = shl i8 %a, 6 1126202375Srdivacky // %c = ashr i8 %b, 6 1127202375Srdivacky // %d = sext i8 %c to i32 1128202375Srdivacky // into: 1129202375Srdivacky // %a = shl i32 %i, 30 1130202375Srdivacky // %d = ashr i32 %a, 30 1131202375Srdivacky Value *A = 0; 1132202375Srdivacky // TODO: Eventually this could be subsumed by EvaluateInDifferentType. 1133202375Srdivacky ConstantInt *BA = 0, *CA = 0; 1134202375Srdivacky if (match(Src, m_AShr(m_Shl(m_Trunc(m_Value(A)), m_ConstantInt(BA)), 1135202375Srdivacky m_ConstantInt(CA))) && 1136202375Srdivacky BA == CA && A->getType() == CI.getType()) { 1137202375Srdivacky unsigned MidSize = Src->getType()->getScalarSizeInBits(); 1138202375Srdivacky unsigned SrcDstSize = CI.getType()->getScalarSizeInBits(); 1139202375Srdivacky unsigned ShAmt = CA->getZExtValue()+SrcDstSize-MidSize; 1140202375Srdivacky Constant *ShAmtV = ConstantInt::get(CI.getType(), ShAmt); 1141202375Srdivacky A = Builder->CreateShl(A, ShAmtV, CI.getName()); 1142202375Srdivacky return BinaryOperator::CreateAShr(A, ShAmtV); 1143202375Srdivacky } 1144249423Sdim 1145202375Srdivacky return 0; 1146202375Srdivacky} 1147202375Srdivacky 1148202375Srdivacky 1149202375Srdivacky/// FitsInFPType - Return a Constant* for the specified FP constant if it fits 1150202375Srdivacky/// in the specified FP type without changing its value. 1151202375Srdivackystatic Constant *FitsInFPType(ConstantFP *CFP, const fltSemantics &Sem) { 1152202375Srdivacky bool losesInfo; 1153202375Srdivacky APFloat F = CFP->getValueAPF(); 1154202375Srdivacky (void)F.convert(Sem, APFloat::rmNearestTiesToEven, &losesInfo); 1155202375Srdivacky if (!losesInfo) 1156202375Srdivacky return ConstantFP::get(CFP->getContext(), F); 1157202375Srdivacky return 0; 1158202375Srdivacky} 1159202375Srdivacky 1160202375Srdivacky/// LookThroughFPExtensions - If this is an fp extension instruction, look 1161202375Srdivacky/// through it until we get the source value. 1162202375Srdivackystatic Value *LookThroughFPExtensions(Value *V) { 1163202375Srdivacky if (Instruction *I = dyn_cast<Instruction>(V)) 1164202375Srdivacky if (I->getOpcode() == Instruction::FPExt) 1165202375Srdivacky return LookThroughFPExtensions(I->getOperand(0)); 1166249423Sdim 1167202375Srdivacky // If this value is a constant, return the constant in the smallest FP type 1168202375Srdivacky // that can accurately represent it. This allows us to turn 1169202375Srdivacky // (float)((double)X+2.0) into x+2.0f. 1170202375Srdivacky if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) { 1171202375Srdivacky if (CFP->getType() == Type::getPPC_FP128Ty(V->getContext())) 1172202375Srdivacky return V; // No constant folding of this. 1173234353Sdim // See if the value can be truncated to half and then reextended. 1174234353Sdim if (Value *V = FitsInFPType(CFP, APFloat::IEEEhalf)) 1175234353Sdim return V; 1176202375Srdivacky // See if the value can be truncated to float and then reextended. 1177202375Srdivacky if (Value *V = FitsInFPType(CFP, APFloat::IEEEsingle)) 1178202375Srdivacky return V; 1179202375Srdivacky if (CFP->getType()->isDoubleTy()) 1180202375Srdivacky return V; // Won't shrink. 1181202375Srdivacky if (Value *V = FitsInFPType(CFP, APFloat::IEEEdouble)) 1182202375Srdivacky return V; 1183202375Srdivacky // Don't try to shrink to various long double types. 1184202375Srdivacky } 1185249423Sdim 1186202375Srdivacky return V; 1187202375Srdivacky} 1188202375Srdivacky 1189202375SrdivackyInstruction *InstCombiner::visitFPTrunc(FPTruncInst &CI) { 1190202375Srdivacky if (Instruction *I = commonCastTransforms(CI)) 1191202375Srdivacky return I; 1192249423Sdim 1193202375Srdivacky // If we have fptrunc(fadd (fpextend x), (fpextend y)), where x and y are 1194202375Srdivacky // smaller than the destination type, we can eliminate the truncate by doing 1195202375Srdivacky // the add as the smaller type. This applies to fadd/fsub/fmul/fdiv as well 1196202375Srdivacky // as many builtins (sqrt, etc). 1197202375Srdivacky BinaryOperator *OpI = dyn_cast<BinaryOperator>(CI.getOperand(0)); 1198202375Srdivacky if (OpI && OpI->hasOneUse()) { 1199202375Srdivacky switch (OpI->getOpcode()) { 1200202375Srdivacky default: break; 1201202375Srdivacky case Instruction::FAdd: 1202202375Srdivacky case Instruction::FSub: 1203202375Srdivacky case Instruction::FMul: 1204202375Srdivacky case Instruction::FDiv: 1205202375Srdivacky case Instruction::FRem: 1206226633Sdim Type *SrcTy = OpI->getType(); 1207202375Srdivacky Value *LHSTrunc = LookThroughFPExtensions(OpI->getOperand(0)); 1208202375Srdivacky Value *RHSTrunc = LookThroughFPExtensions(OpI->getOperand(1)); 1209249423Sdim if (LHSTrunc->getType() != SrcTy && 1210202375Srdivacky RHSTrunc->getType() != SrcTy) { 1211202375Srdivacky unsigned DstSize = CI.getType()->getScalarSizeInBits(); 1212202375Srdivacky // If the source types were both smaller than the destination type of 1213202375Srdivacky // the cast, do this xform. 1214202375Srdivacky if (LHSTrunc->getType()->getScalarSizeInBits() <= DstSize && 1215202375Srdivacky RHSTrunc->getType()->getScalarSizeInBits() <= DstSize) { 1216202375Srdivacky LHSTrunc = Builder->CreateFPExt(LHSTrunc, CI.getType()); 1217202375Srdivacky RHSTrunc = Builder->CreateFPExt(RHSTrunc, CI.getType()); 1218202375Srdivacky return BinaryOperator::Create(OpI->getOpcode(), LHSTrunc, RHSTrunc); 1219202375Srdivacky } 1220202375Srdivacky } 1221249423Sdim break; 1222202375Srdivacky } 1223249423Sdim 1224249423Sdim // (fptrunc (fneg x)) -> (fneg (fptrunc x)) 1225249423Sdim if (BinaryOperator::isFNeg(OpI)) { 1226249423Sdim Value *InnerTrunc = Builder->CreateFPTrunc(OpI->getOperand(1), 1227249423Sdim CI.getType()); 1228249423Sdim return BinaryOperator::CreateFNeg(InnerTrunc); 1229249423Sdim } 1230202375Srdivacky } 1231249423Sdim 1232263508Sdim // (fptrunc (select cond, R1, Cst)) --> 1233263508Sdim // (select cond, (fptrunc R1), (fptrunc Cst)) 1234263508Sdim SelectInst *SI = dyn_cast<SelectInst>(CI.getOperand(0)); 1235263508Sdim if (SI && 1236263508Sdim (isa<ConstantFP>(SI->getOperand(1)) || 1237263508Sdim isa<ConstantFP>(SI->getOperand(2)))) { 1238263508Sdim Value *LHSTrunc = Builder->CreateFPTrunc(SI->getOperand(1), 1239263508Sdim CI.getType()); 1240263508Sdim Value *RHSTrunc = Builder->CreateFPTrunc(SI->getOperand(2), 1241263508Sdim CI.getType()); 1242263508Sdim return SelectInst::Create(SI->getOperand(0), LHSTrunc, RHSTrunc); 1243263508Sdim } 1244263508Sdim 1245249423Sdim IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI.getOperand(0)); 1246249423Sdim if (II) { 1247249423Sdim switch (II->getIntrinsicID()) { 1248249423Sdim default: break; 1249249423Sdim case Intrinsic::fabs: { 1250249423Sdim // (fptrunc (fabs x)) -> (fabs (fptrunc x)) 1251249423Sdim Value *InnerTrunc = Builder->CreateFPTrunc(II->getArgOperand(0), 1252249423Sdim CI.getType()); 1253249423Sdim Type *IntrinsicType[] = { CI.getType() }; 1254249423Sdim Function *Overload = 1255249423Sdim Intrinsic::getDeclaration(CI.getParent()->getParent()->getParent(), 1256249423Sdim II->getIntrinsicID(), IntrinsicType); 1257249423Sdim 1258249423Sdim Value *Args[] = { InnerTrunc }; 1259249423Sdim return CallInst::Create(Overload, Args, II->getName()); 1260249423Sdim } 1261249423Sdim } 1262249423Sdim } 1263249423Sdim 1264212904Sdim // Fold (fptrunc (sqrt (fpext x))) -> (sqrtf x) 1265263508Sdim // Note that we restrict this transformation based on 1266263508Sdim // TLI->has(LibFunc::sqrtf), even for the sqrt intrinsic, because 1267263508Sdim // TLI->has(LibFunc::sqrtf) is sufficient to guarantee that the 1268263508Sdim // single-precision intrinsic can be expanded in the backend. 1269212904Sdim CallInst *Call = dyn_cast<CallInst>(CI.getOperand(0)); 1270234353Sdim if (Call && Call->getCalledFunction() && TLI->has(LibFunc::sqrtf) && 1271263508Sdim (Call->getCalledFunction()->getName() == TLI->getName(LibFunc::sqrt) || 1272263508Sdim Call->getCalledFunction()->getIntrinsicID() == Intrinsic::sqrt) && 1273224145Sdim Call->getNumArgOperands() == 1 && 1274224145Sdim Call->hasOneUse()) { 1275212904Sdim CastInst *Arg = dyn_cast<CastInst>(Call->getArgOperand(0)); 1276212904Sdim if (Arg && Arg->getOpcode() == Instruction::FPExt && 1277212904Sdim CI.getType()->isFloatTy() && 1278212904Sdim Call->getType()->isDoubleTy() && 1279212904Sdim Arg->getType()->isDoubleTy() && 1280212904Sdim Arg->getOperand(0)->getType()->isFloatTy()) { 1281212904Sdim Function *Callee = Call->getCalledFunction(); 1282212904Sdim Module *M = CI.getParent()->getParent()->getParent(); 1283263508Sdim Constant *SqrtfFunc = (Callee->getIntrinsicID() == Intrinsic::sqrt) ? 1284263508Sdim Intrinsic::getDeclaration(M, Intrinsic::sqrt, Builder->getFloatTy()) : 1285263508Sdim M->getOrInsertFunction("sqrtf", Callee->getAttributes(), 1286263508Sdim Builder->getFloatTy(), Builder->getFloatTy(), 1287263508Sdim NULL); 1288212904Sdim CallInst *ret = CallInst::Create(SqrtfFunc, Arg->getOperand(0), 1289212904Sdim "sqrtfcall"); 1290212904Sdim ret->setAttributes(Callee->getAttributes()); 1291249423Sdim 1292249423Sdim 1293212904Sdim // Remove the old Call. With -fmath-errno, it won't get marked readnone. 1294223017Sdim ReplaceInstUsesWith(*Call, UndefValue::get(Call->getType())); 1295212904Sdim EraseInstFromFunction(*Call); 1296212904Sdim return ret; 1297212904Sdim } 1298212904Sdim } 1299249423Sdim 1300202375Srdivacky return 0; 1301202375Srdivacky} 1302202375Srdivacky 1303202375SrdivackyInstruction *InstCombiner::visitFPExt(CastInst &CI) { 1304202375Srdivacky return commonCastTransforms(CI); 1305202375Srdivacky} 1306202375Srdivacky 1307202375SrdivackyInstruction *InstCombiner::visitFPToUI(FPToUIInst &FI) { 1308202375Srdivacky Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0)); 1309202375Srdivacky if (OpI == 0) 1310202375Srdivacky return commonCastTransforms(FI); 1311202375Srdivacky 1312202375Srdivacky // fptoui(uitofp(X)) --> X 1313202375Srdivacky // fptoui(sitofp(X)) --> X 1314202375Srdivacky // This is safe if the intermediate type has enough bits in its mantissa to 1315202375Srdivacky // accurately represent all values of X. For example, do not do this with 1316202375Srdivacky // i64->float->i64. This is also safe for sitofp case, because any negative 1317249423Sdim // 'X' value would cause an undefined result for the fptoui. 1318202375Srdivacky if ((isa<UIToFPInst>(OpI) || isa<SIToFPInst>(OpI)) && 1319202375Srdivacky OpI->getOperand(0)->getType() == FI.getType() && 1320202375Srdivacky (int)FI.getType()->getScalarSizeInBits() < /*extra bit for sign */ 1321202375Srdivacky OpI->getType()->getFPMantissaWidth()) 1322202375Srdivacky return ReplaceInstUsesWith(FI, OpI->getOperand(0)); 1323202375Srdivacky 1324202375Srdivacky return commonCastTransforms(FI); 1325202375Srdivacky} 1326202375Srdivacky 1327202375SrdivackyInstruction *InstCombiner::visitFPToSI(FPToSIInst &FI) { 1328202375Srdivacky Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0)); 1329202375Srdivacky if (OpI == 0) 1330202375Srdivacky return commonCastTransforms(FI); 1331249423Sdim 1332202375Srdivacky // fptosi(sitofp(X)) --> X 1333202375Srdivacky // fptosi(uitofp(X)) --> X 1334202375Srdivacky // This is safe if the intermediate type has enough bits in its mantissa to 1335202375Srdivacky // accurately represent all values of X. For example, do not do this with 1336202375Srdivacky // i64->float->i64. This is also safe for sitofp case, because any negative 1337249423Sdim // 'X' value would cause an undefined result for the fptoui. 1338202375Srdivacky if ((isa<UIToFPInst>(OpI) || isa<SIToFPInst>(OpI)) && 1339202375Srdivacky OpI->getOperand(0)->getType() == FI.getType() && 1340202375Srdivacky (int)FI.getType()->getScalarSizeInBits() <= 1341202375Srdivacky OpI->getType()->getFPMantissaWidth()) 1342202375Srdivacky return ReplaceInstUsesWith(FI, OpI->getOperand(0)); 1343249423Sdim 1344202375Srdivacky return commonCastTransforms(FI); 1345202375Srdivacky} 1346202375Srdivacky 1347202375SrdivackyInstruction *InstCombiner::visitUIToFP(CastInst &CI) { 1348202375Srdivacky return commonCastTransforms(CI); 1349202375Srdivacky} 1350202375Srdivacky 1351202375SrdivackyInstruction *InstCombiner::visitSIToFP(CastInst &CI) { 1352202375Srdivacky return commonCastTransforms(CI); 1353202375Srdivacky} 1354202375Srdivacky 1355202375SrdivackyInstruction *InstCombiner::visitIntToPtr(IntToPtrInst &CI) { 1356203954Srdivacky // If the source integer type is not the intptr_t type for this target, do a 1357203954Srdivacky // trunc or zext to the intptr_t type, then inttoptr of it. This allows the 1358203954Srdivacky // cast to be exposed to other transforms. 1359249423Sdim 1360263508Sdim if (TD) { 1361263508Sdim unsigned AS = CI.getAddressSpace(); 1362263508Sdim if (CI.getOperand(0)->getType()->getScalarSizeInBits() != 1363263508Sdim TD->getPointerSizeInBits(AS)) { 1364263508Sdim Type *Ty = TD->getIntPtrType(CI.getContext(), AS); 1365263508Sdim if (CI.getType()->isVectorTy()) // Handle vectors of pointers. 1366263508Sdim Ty = VectorType::get(Ty, CI.getType()->getVectorNumElements()); 1367263508Sdim 1368263508Sdim Value *P = Builder->CreateZExtOrTrunc(CI.getOperand(0), Ty); 1369263508Sdim return new IntToPtrInst(P, CI.getType()); 1370263508Sdim } 1371202375Srdivacky } 1372249423Sdim 1373202375Srdivacky if (Instruction *I = commonCastTransforms(CI)) 1374202375Srdivacky return I; 1375202375Srdivacky 1376202375Srdivacky return 0; 1377202375Srdivacky} 1378202375Srdivacky 1379202375Srdivacky/// @brief Implement the transforms for cast of pointer (bitcast/ptrtoint) 1380202375SrdivackyInstruction *InstCombiner::commonPointerCastTransforms(CastInst &CI) { 1381202375Srdivacky Value *Src = CI.getOperand(0); 1382249423Sdim 1383202375Srdivacky if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) { 1384202375Srdivacky // If casting the result of a getelementptr instruction with no offset, turn 1385202375Srdivacky // this into a cast of the original pointer! 1386202375Srdivacky if (GEP->hasAllZeroIndices()) { 1387202375Srdivacky // Changing the cast operand is usually not a good idea but it is safe 1388249423Sdim // here because the pointer operand is being replaced with another 1389202375Srdivacky // pointer operand so the opcode doesn't need to change. 1390202375Srdivacky Worklist.Add(GEP); 1391202375Srdivacky CI.setOperand(0, GEP->getOperand(0)); 1392202375Srdivacky return &CI; 1393202375Srdivacky } 1394249423Sdim 1395263508Sdim if (!TD) 1396263508Sdim return commonCastTransforms(CI); 1397263508Sdim 1398202375Srdivacky // If the GEP has a single use, and the base pointer is a bitcast, and the 1399202375Srdivacky // GEP computes a constant offset, see if we can convert these three 1400202375Srdivacky // instructions into fewer. This typically happens with unions and other 1401202375Srdivacky // non-type-safe code. 1402263508Sdim unsigned AS = GEP->getPointerAddressSpace(); 1403263508Sdim unsigned OffsetBits = TD->getPointerSizeInBits(AS); 1404263508Sdim APInt Offset(OffsetBits, 0); 1405263508Sdim BitCastInst *BCI = dyn_cast<BitCastInst>(GEP->getOperand(0)); 1406263508Sdim if (GEP->hasOneUse() && 1407263508Sdim BCI && 1408249423Sdim GEP->accumulateConstantOffset(*TD, Offset)) { 1409202375Srdivacky // Get the base pointer input of the bitcast, and the type it points to. 1410263508Sdim Value *OrigBase = BCI->getOperand(0); 1411202375Srdivacky SmallVector<Value*, 8> NewIndices; 1412263508Sdim if (FindElementAtOffset(OrigBase->getType(), 1413263508Sdim Offset.getSExtValue(), 1414263508Sdim NewIndices)) { 1415202375Srdivacky // If we were able to index down into an element, create the GEP 1416202375Srdivacky // and bitcast the result. This eliminates one bitcast, potentially 1417202375Srdivacky // two. 1418202375Srdivacky Value *NGEP = cast<GEPOperator>(GEP)->isInBounds() ? 1419263508Sdim Builder->CreateInBoundsGEP(OrigBase, NewIndices) : 1420263508Sdim Builder->CreateGEP(OrigBase, NewIndices); 1421202375Srdivacky NGEP->takeName(GEP); 1422249423Sdim 1423202375Srdivacky if (isa<BitCastInst>(CI)) 1424202375Srdivacky return new BitCastInst(NGEP, CI.getType()); 1425202375Srdivacky assert(isa<PtrToIntInst>(CI)); 1426202375Srdivacky return new PtrToIntInst(NGEP, CI.getType()); 1427249423Sdim } 1428202375Srdivacky } 1429202375Srdivacky } 1430249423Sdim 1431202375Srdivacky return commonCastTransforms(CI); 1432202375Srdivacky} 1433202375Srdivacky 1434202375SrdivackyInstruction *InstCombiner::visitPtrToInt(PtrToIntInst &CI) { 1435203954Srdivacky // If the destination integer type is not the intptr_t type for this target, 1436203954Srdivacky // do a ptrtoint to intptr_t then do a trunc or zext. This allows the cast 1437203954Srdivacky // to be exposed to other transforms. 1438249423Sdim 1439263508Sdim if (!TD) 1440263508Sdim return commonPointerCastTransforms(CI); 1441249423Sdim 1442263508Sdim Type *Ty = CI.getType(); 1443263508Sdim unsigned AS = CI.getPointerAddressSpace(); 1444263508Sdim 1445263508Sdim if (Ty->getScalarSizeInBits() == TD->getPointerSizeInBits(AS)) 1446263508Sdim return commonPointerCastTransforms(CI); 1447263508Sdim 1448263508Sdim Type *PtrTy = TD->getIntPtrType(CI.getContext(), AS); 1449263508Sdim if (Ty->isVectorTy()) // Handle vectors of pointers. 1450263508Sdim PtrTy = VectorType::get(PtrTy, Ty->getVectorNumElements()); 1451263508Sdim 1452263508Sdim Value *P = Builder->CreatePtrToInt(CI.getOperand(0), PtrTy); 1453263508Sdim return CastInst::CreateIntegerCast(P, Ty, /*isSigned=*/false); 1454202375Srdivacky} 1455202375Srdivacky 1456208599Srdivacky/// OptimizeVectorResize - This input value (which is known to have vector type) 1457208599Srdivacky/// is being zero extended or truncated to the specified vector type. Try to 1458208599Srdivacky/// replace it with a shuffle (and vector/vector bitcast) if possible. 1459208599Srdivacky/// 1460208599Srdivacky/// The source and destination vector types may have different element types. 1461226633Sdimstatic Instruction *OptimizeVectorResize(Value *InVal, VectorType *DestTy, 1462208599Srdivacky InstCombiner &IC) { 1463208599Srdivacky // We can only do this optimization if the output is a multiple of the input 1464208599Srdivacky // element size, or the input is a multiple of the output element size. 1465208599Srdivacky // Convert the input type to have the same element type as the output. 1466226633Sdim VectorType *SrcTy = cast<VectorType>(InVal->getType()); 1467249423Sdim 1468208599Srdivacky if (SrcTy->getElementType() != DestTy->getElementType()) { 1469208599Srdivacky // The input types don't need to be identical, but for now they must be the 1470208599Srdivacky // same size. There is no specific reason we couldn't handle things like 1471208599Srdivacky // <4 x i16> -> <4 x i32> by bitcasting to <2 x i32> but haven't gotten 1472249423Sdim // there yet. 1473208599Srdivacky if (SrcTy->getElementType()->getPrimitiveSizeInBits() != 1474208599Srdivacky DestTy->getElementType()->getPrimitiveSizeInBits()) 1475208599Srdivacky return 0; 1476249423Sdim 1477208599Srdivacky SrcTy = VectorType::get(DestTy->getElementType(), SrcTy->getNumElements()); 1478208599Srdivacky InVal = IC.Builder->CreateBitCast(InVal, SrcTy); 1479208599Srdivacky } 1480249423Sdim 1481208599Srdivacky // Now that the element types match, get the shuffle mask and RHS of the 1482208599Srdivacky // shuffle to use, which depends on whether we're increasing or decreasing the 1483208599Srdivacky // size of the input. 1484234353Sdim SmallVector<uint32_t, 16> ShuffleMask; 1485208599Srdivacky Value *V2; 1486249423Sdim 1487208599Srdivacky if (SrcTy->getNumElements() > DestTy->getNumElements()) { 1488208599Srdivacky // If we're shrinking the number of elements, just shuffle in the low 1489208599Srdivacky // elements from the input and use undef as the second shuffle input. 1490208599Srdivacky V2 = UndefValue::get(SrcTy); 1491208599Srdivacky for (unsigned i = 0, e = DestTy->getNumElements(); i != e; ++i) 1492234353Sdim ShuffleMask.push_back(i); 1493249423Sdim 1494208599Srdivacky } else { 1495208599Srdivacky // If we're increasing the number of elements, shuffle in all of the 1496208599Srdivacky // elements from InVal and fill the rest of the result elements with zeros 1497208599Srdivacky // from a constant zero. 1498208599Srdivacky V2 = Constant::getNullValue(SrcTy); 1499208599Srdivacky unsigned SrcElts = SrcTy->getNumElements(); 1500208599Srdivacky for (unsigned i = 0, e = SrcElts; i != e; ++i) 1501234353Sdim ShuffleMask.push_back(i); 1502208599Srdivacky 1503208599Srdivacky // The excess elements reference the first element of the zero input. 1504234353Sdim for (unsigned i = 0, e = DestTy->getNumElements()-SrcElts; i != e; ++i) 1505234353Sdim ShuffleMask.push_back(SrcElts); 1506208599Srdivacky } 1507249423Sdim 1508234353Sdim return new ShuffleVectorInst(InVal, V2, 1509234353Sdim ConstantDataVector::get(V2->getContext(), 1510234353Sdim ShuffleMask)); 1511208599Srdivacky} 1512208599Srdivacky 1513226633Sdimstatic bool isMultipleOfTypeSize(unsigned Value, Type *Ty) { 1514212904Sdim return Value % Ty->getPrimitiveSizeInBits() == 0; 1515212904Sdim} 1516208599Srdivacky 1517226633Sdimstatic unsigned getTypeSizeIndex(unsigned Value, Type *Ty) { 1518212904Sdim return Value / Ty->getPrimitiveSizeInBits(); 1519212904Sdim} 1520212904Sdim 1521212904Sdim/// CollectInsertionElements - V is a value which is inserted into a vector of 1522212904Sdim/// VecEltTy. Look through the value to see if we can decompose it into 1523212904Sdim/// insertions into the vector. See the example in the comment for 1524212904Sdim/// OptimizeIntegerToVectorInsertions for the pattern this handles. 1525212904Sdim/// The type of V is always a non-zero multiple of VecEltTy's size. 1526263508Sdim/// Shift is the number of bits between the lsb of V and the lsb of 1527263508Sdim/// the vector. 1528212904Sdim/// 1529212904Sdim/// This returns false if the pattern can't be matched or true if it can, 1530212904Sdim/// filling in Elements with the elements found here. 1531263508Sdimstatic bool CollectInsertionElements(Value *V, unsigned Shift, 1532212904Sdim SmallVectorImpl<Value*> &Elements, 1533263508Sdim Type *VecEltTy, InstCombiner &IC) { 1534263508Sdim assert(isMultipleOfTypeSize(Shift, VecEltTy) && 1535263508Sdim "Shift should be a multiple of the element type size"); 1536263508Sdim 1537212904Sdim // Undef values never contribute useful bits to the result. 1538212904Sdim if (isa<UndefValue>(V)) return true; 1539249423Sdim 1540212904Sdim // If we got down to a value of the right type, we win, try inserting into the 1541212904Sdim // right element. 1542212904Sdim if (V->getType() == VecEltTy) { 1543212904Sdim // Inserting null doesn't actually insert any elements. 1544212904Sdim if (Constant *C = dyn_cast<Constant>(V)) 1545212904Sdim if (C->isNullValue()) 1546212904Sdim return true; 1547249423Sdim 1548263508Sdim unsigned ElementIndex = getTypeSizeIndex(Shift, VecEltTy); 1549263508Sdim if (IC.getDataLayout()->isBigEndian()) 1550263508Sdim ElementIndex = Elements.size() - ElementIndex - 1; 1551263508Sdim 1552212904Sdim // Fail if multiple elements are inserted into this slot. 1553263508Sdim if (Elements[ElementIndex] != 0) 1554212904Sdim return false; 1555249423Sdim 1556212904Sdim Elements[ElementIndex] = V; 1557212904Sdim return true; 1558212904Sdim } 1559249423Sdim 1560212904Sdim if (Constant *C = dyn_cast<Constant>(V)) { 1561212904Sdim // Figure out the # elements this provides, and bitcast it or slice it up 1562212904Sdim // as required. 1563212904Sdim unsigned NumElts = getTypeSizeIndex(C->getType()->getPrimitiveSizeInBits(), 1564212904Sdim VecEltTy); 1565212904Sdim // If the constant is the size of a vector element, we just need to bitcast 1566212904Sdim // it to the right type so it gets properly inserted. 1567212904Sdim if (NumElts == 1) 1568212904Sdim return CollectInsertionElements(ConstantExpr::getBitCast(C, VecEltTy), 1569263508Sdim Shift, Elements, VecEltTy, IC); 1570249423Sdim 1571212904Sdim // Okay, this is a constant that covers multiple elements. Slice it up into 1572212904Sdim // pieces and insert each element-sized piece into the vector. 1573212904Sdim if (!isa<IntegerType>(C->getType())) 1574212904Sdim C = ConstantExpr::getBitCast(C, IntegerType::get(V->getContext(), 1575212904Sdim C->getType()->getPrimitiveSizeInBits())); 1576212904Sdim unsigned ElementSize = VecEltTy->getPrimitiveSizeInBits(); 1577226633Sdim Type *ElementIntTy = IntegerType::get(C->getContext(), ElementSize); 1578249423Sdim 1579212904Sdim for (unsigned i = 0; i != NumElts; ++i) { 1580263508Sdim unsigned ShiftI = Shift+i*ElementSize; 1581212904Sdim Constant *Piece = ConstantExpr::getLShr(C, ConstantInt::get(C->getType(), 1582263508Sdim ShiftI)); 1583212904Sdim Piece = ConstantExpr::getTrunc(Piece, ElementIntTy); 1584263508Sdim if (!CollectInsertionElements(Piece, ShiftI, Elements, VecEltTy, IC)) 1585212904Sdim return false; 1586212904Sdim } 1587212904Sdim return true; 1588212904Sdim } 1589249423Sdim 1590212904Sdim if (!V->hasOneUse()) return false; 1591249423Sdim 1592212904Sdim Instruction *I = dyn_cast<Instruction>(V); 1593212904Sdim if (I == 0) return false; 1594212904Sdim switch (I->getOpcode()) { 1595212904Sdim default: return false; // Unhandled case. 1596212904Sdim case Instruction::BitCast: 1597263508Sdim return CollectInsertionElements(I->getOperand(0), Shift, 1598263508Sdim Elements, VecEltTy, IC); 1599212904Sdim case Instruction::ZExt: 1600212904Sdim if (!isMultipleOfTypeSize( 1601212904Sdim I->getOperand(0)->getType()->getPrimitiveSizeInBits(), 1602212904Sdim VecEltTy)) 1603212904Sdim return false; 1604263508Sdim return CollectInsertionElements(I->getOperand(0), Shift, 1605263508Sdim Elements, VecEltTy, IC); 1606212904Sdim case Instruction::Or: 1607263508Sdim return CollectInsertionElements(I->getOperand(0), Shift, 1608263508Sdim Elements, VecEltTy, IC) && 1609263508Sdim CollectInsertionElements(I->getOperand(1), Shift, 1610263508Sdim Elements, VecEltTy, IC); 1611212904Sdim case Instruction::Shl: { 1612212904Sdim // Must be shifting by a constant that is a multiple of the element size. 1613212904Sdim ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1)); 1614212904Sdim if (CI == 0) return false; 1615263508Sdim Shift += CI->getZExtValue(); 1616263508Sdim if (!isMultipleOfTypeSize(Shift, VecEltTy)) return false; 1617263508Sdim return CollectInsertionElements(I->getOperand(0), Shift, 1618263508Sdim Elements, VecEltTy, IC); 1619212904Sdim } 1620249423Sdim 1621212904Sdim } 1622212904Sdim} 1623212904Sdim 1624212904Sdim 1625212904Sdim/// OptimizeIntegerToVectorInsertions - If the input is an 'or' instruction, we 1626212904Sdim/// may be doing shifts and ors to assemble the elements of the vector manually. 1627212904Sdim/// Try to rip the code out and replace it with insertelements. This is to 1628212904Sdim/// optimize code like this: 1629212904Sdim/// 1630212904Sdim/// %tmp37 = bitcast float %inc to i32 1631212904Sdim/// %tmp38 = zext i32 %tmp37 to i64 1632212904Sdim/// %tmp31 = bitcast float %inc5 to i32 1633212904Sdim/// %tmp32 = zext i32 %tmp31 to i64 1634212904Sdim/// %tmp33 = shl i64 %tmp32, 32 1635212904Sdim/// %ins35 = or i64 %tmp33, %tmp38 1636212904Sdim/// %tmp43 = bitcast i64 %ins35 to <2 x float> 1637212904Sdim/// 1638212904Sdim/// Into two insertelements that do "buildvector{%inc, %inc5}". 1639212904Sdimstatic Value *OptimizeIntegerToVectorInsertions(BitCastInst &CI, 1640212904Sdim InstCombiner &IC) { 1641263508Sdim // We need to know the target byte order to perform this optimization. 1642263508Sdim if (!IC.getDataLayout()) return 0; 1643263508Sdim 1644226633Sdim VectorType *DestVecTy = cast<VectorType>(CI.getType()); 1645212904Sdim Value *IntInput = CI.getOperand(0); 1646212904Sdim 1647212904Sdim SmallVector<Value*, 8> Elements(DestVecTy->getNumElements()); 1648212904Sdim if (!CollectInsertionElements(IntInput, 0, Elements, 1649263508Sdim DestVecTy->getElementType(), IC)) 1650212904Sdim return 0; 1651212904Sdim 1652212904Sdim // If we succeeded, we know that all of the element are specified by Elements 1653212904Sdim // or are zero if Elements has a null entry. Recast this as a set of 1654212904Sdim // insertions. 1655212904Sdim Value *Result = Constant::getNullValue(CI.getType()); 1656212904Sdim for (unsigned i = 0, e = Elements.size(); i != e; ++i) { 1657212904Sdim if (Elements[i] == 0) continue; // Unset element. 1658249423Sdim 1659212904Sdim Result = IC.Builder->CreateInsertElement(Result, Elements[i], 1660212904Sdim IC.Builder->getInt32(i)); 1661212904Sdim } 1662249423Sdim 1663212904Sdim return Result; 1664212904Sdim} 1665212904Sdim 1666212904Sdim 1667212904Sdim/// OptimizeIntToFloatBitCast - See if we can optimize an integer->float/double 1668212904Sdim/// bitcast. The various long double bitcasts can't get in here. 1669212904Sdimstatic Instruction *OptimizeIntToFloatBitCast(BitCastInst &CI,InstCombiner &IC){ 1670249423Sdim // We need to know the target byte order to perform this optimization. 1671249423Sdim if (!IC.getDataLayout()) return 0; 1672249423Sdim 1673212904Sdim Value *Src = CI.getOperand(0); 1674226633Sdim Type *DestTy = CI.getType(); 1675212904Sdim 1676212904Sdim // If this is a bitcast from int to float, check to see if the int is an 1677212904Sdim // extraction from a vector. 1678212904Sdim Value *VecInput = 0; 1679212904Sdim // bitcast(trunc(bitcast(somevector))) 1680212904Sdim if (match(Src, m_Trunc(m_BitCast(m_Value(VecInput)))) && 1681212904Sdim isa<VectorType>(VecInput->getType())) { 1682226633Sdim VectorType *VecTy = cast<VectorType>(VecInput->getType()); 1683212904Sdim unsigned DestWidth = DestTy->getPrimitiveSizeInBits(); 1684212904Sdim 1685212904Sdim if (VecTy->getPrimitiveSizeInBits() % DestWidth == 0) { 1686212904Sdim // If the element type of the vector doesn't match the result type, 1687212904Sdim // bitcast it to be a vector type we can extract from. 1688212904Sdim if (VecTy->getElementType() != DestTy) { 1689212904Sdim VecTy = VectorType::get(DestTy, 1690212904Sdim VecTy->getPrimitiveSizeInBits() / DestWidth); 1691212904Sdim VecInput = IC.Builder->CreateBitCast(VecInput, VecTy); 1692212904Sdim } 1693249423Sdim 1694249423Sdim unsigned Elt = 0; 1695249423Sdim if (IC.getDataLayout()->isBigEndian()) 1696249423Sdim Elt = VecTy->getPrimitiveSizeInBits() / DestWidth - 1; 1697249423Sdim return ExtractElementInst::Create(VecInput, IC.Builder->getInt32(Elt)); 1698212904Sdim } 1699212904Sdim } 1700249423Sdim 1701212904Sdim // bitcast(trunc(lshr(bitcast(somevector), cst)) 1702212904Sdim ConstantInt *ShAmt = 0; 1703212904Sdim if (match(Src, m_Trunc(m_LShr(m_BitCast(m_Value(VecInput)), 1704212904Sdim m_ConstantInt(ShAmt)))) && 1705212904Sdim isa<VectorType>(VecInput->getType())) { 1706226633Sdim VectorType *VecTy = cast<VectorType>(VecInput->getType()); 1707212904Sdim unsigned DestWidth = DestTy->getPrimitiveSizeInBits(); 1708212904Sdim if (VecTy->getPrimitiveSizeInBits() % DestWidth == 0 && 1709212904Sdim ShAmt->getZExtValue() % DestWidth == 0) { 1710212904Sdim // If the element type of the vector doesn't match the result type, 1711212904Sdim // bitcast it to be a vector type we can extract from. 1712212904Sdim if (VecTy->getElementType() != DestTy) { 1713212904Sdim VecTy = VectorType::get(DestTy, 1714212904Sdim VecTy->getPrimitiveSizeInBits() / DestWidth); 1715212904Sdim VecInput = IC.Builder->CreateBitCast(VecInput, VecTy); 1716212904Sdim } 1717249423Sdim 1718212904Sdim unsigned Elt = ShAmt->getZExtValue() / DestWidth; 1719249423Sdim if (IC.getDataLayout()->isBigEndian()) 1720249423Sdim Elt = VecTy->getPrimitiveSizeInBits() / DestWidth - 1 - Elt; 1721212904Sdim return ExtractElementInst::Create(VecInput, IC.Builder->getInt32(Elt)); 1722212904Sdim } 1723212904Sdim } 1724212904Sdim return 0; 1725212904Sdim} 1726212904Sdim 1727202375SrdivackyInstruction *InstCombiner::visitBitCast(BitCastInst &CI) { 1728202375Srdivacky // If the operands are integer typed then apply the integer transforms, 1729202375Srdivacky // otherwise just apply the common ones. 1730202375Srdivacky Value *Src = CI.getOperand(0); 1731226633Sdim Type *SrcTy = Src->getType(); 1732226633Sdim Type *DestTy = CI.getType(); 1733202375Srdivacky 1734202375Srdivacky // Get rid of casts from one type to the same type. These are useless and can 1735202375Srdivacky // be replaced by the operand. 1736202375Srdivacky if (DestTy == Src->getType()) 1737202375Srdivacky return ReplaceInstUsesWith(CI, Src); 1738202375Srdivacky 1739226633Sdim if (PointerType *DstPTy = dyn_cast<PointerType>(DestTy)) { 1740226633Sdim PointerType *SrcPTy = cast<PointerType>(SrcTy); 1741226633Sdim Type *DstElTy = DstPTy->getElementType(); 1742226633Sdim Type *SrcElTy = SrcPTy->getElementType(); 1743249423Sdim 1744202375Srdivacky // If the address spaces don't match, don't eliminate the bitcast, which is 1745202375Srdivacky // required for changing types. 1746202375Srdivacky if (SrcPTy->getAddressSpace() != DstPTy->getAddressSpace()) 1747202375Srdivacky return 0; 1748249423Sdim 1749202375Srdivacky // If we are casting a alloca to a pointer to a type of the same 1750202375Srdivacky // size, rewrite the allocation instruction to allocate the "right" type. 1751202375Srdivacky // There is no need to modify malloc calls because it is their bitcast that 1752202375Srdivacky // needs to be cleaned up. 1753202375Srdivacky if (AllocaInst *AI = dyn_cast<AllocaInst>(Src)) 1754202375Srdivacky if (Instruction *V = PromoteCastOfAllocation(CI, *AI)) 1755202375Srdivacky return V; 1756249423Sdim 1757202375Srdivacky // If the source and destination are pointers, and this cast is equivalent 1758202375Srdivacky // to a getelementptr X, 0, 0, 0... turn it into the appropriate gep. 1759202375Srdivacky // This can enhance SROA and other transforms that want type-safe pointers. 1760202375Srdivacky Constant *ZeroUInt = 1761202375Srdivacky Constant::getNullValue(Type::getInt32Ty(CI.getContext())); 1762202375Srdivacky unsigned NumZeros = 0; 1763249423Sdim while (SrcElTy != DstElTy && 1764204642Srdivacky isa<CompositeType>(SrcElTy) && !SrcElTy->isPointerTy() && 1765202375Srdivacky SrcElTy->getNumContainedTypes() /* not "{}" */) { 1766202375Srdivacky SrcElTy = cast<CompositeType>(SrcElTy)->getTypeAtIndex(ZeroUInt); 1767202375Srdivacky ++NumZeros; 1768202375Srdivacky } 1769202375Srdivacky 1770202375Srdivacky // If we found a path from the src to dest, create the getelementptr now. 1771202375Srdivacky if (SrcElTy == DstElTy) { 1772202375Srdivacky SmallVector<Value*, 8> Idxs(NumZeros+1, ZeroUInt); 1773226633Sdim return GetElementPtrInst::CreateInBounds(Src, Idxs); 1774202375Srdivacky } 1775202375Srdivacky } 1776249423Sdim 1777212904Sdim // Try to optimize int -> float bitcasts. 1778212904Sdim if ((DestTy->isFloatTy() || DestTy->isDoubleTy()) && isa<IntegerType>(SrcTy)) 1779212904Sdim if (Instruction *I = OptimizeIntToFloatBitCast(CI, *this)) 1780212904Sdim return I; 1781202375Srdivacky 1782226633Sdim if (VectorType *DestVTy = dyn_cast<VectorType>(DestTy)) { 1783204642Srdivacky if (DestVTy->getNumElements() == 1 && !SrcTy->isVectorTy()) { 1784202375Srdivacky Value *Elem = Builder->CreateBitCast(Src, DestVTy->getElementType()); 1785202375Srdivacky return InsertElementInst::Create(UndefValue::get(DestTy), Elem, 1786202375Srdivacky Constant::getNullValue(Type::getInt32Ty(CI.getContext()))); 1787202375Srdivacky // FIXME: Canonicalize bitcast(insertelement) -> insertelement(bitcast) 1788202375Srdivacky } 1789249423Sdim 1790212904Sdim if (isa<IntegerType>(SrcTy)) { 1791212904Sdim // If this is a cast from an integer to vector, check to see if the input 1792212904Sdim // is a trunc or zext of a bitcast from vector. If so, we can replace all 1793212904Sdim // the casts with a shuffle and (potentially) a bitcast. 1794212904Sdim if (isa<TruncInst>(Src) || isa<ZExtInst>(Src)) { 1795212904Sdim CastInst *SrcCast = cast<CastInst>(Src); 1796212904Sdim if (BitCastInst *BCIn = dyn_cast<BitCastInst>(SrcCast->getOperand(0))) 1797212904Sdim if (isa<VectorType>(BCIn->getOperand(0)->getType())) 1798212904Sdim if (Instruction *I = OptimizeVectorResize(BCIn->getOperand(0), 1799208599Srdivacky cast<VectorType>(DestTy), *this)) 1800212904Sdim return I; 1801212904Sdim } 1802249423Sdim 1803212904Sdim // If the input is an 'or' instruction, we may be doing shifts and ors to 1804212904Sdim // assemble the elements of the vector manually. Try to rip the code out 1805212904Sdim // and replace it with insertelements. 1806212904Sdim if (Value *V = OptimizeIntegerToVectorInsertions(CI, *this)) 1807212904Sdim return ReplaceInstUsesWith(CI, V); 1808208599Srdivacky } 1809202375Srdivacky } 1810202375Srdivacky 1811226633Sdim if (VectorType *SrcVTy = dyn_cast<VectorType>(SrcTy)) { 1812249423Sdim if (SrcVTy->getNumElements() == 1) { 1813249423Sdim // If our destination is not a vector, then make this a straight 1814249423Sdim // scalar-scalar cast. 1815249423Sdim if (!DestTy->isVectorTy()) { 1816249423Sdim Value *Elem = 1817249423Sdim Builder->CreateExtractElement(Src, 1818249423Sdim Constant::getNullValue(Type::getInt32Ty(CI.getContext()))); 1819249423Sdim return CastInst::Create(Instruction::BitCast, Elem, DestTy); 1820249423Sdim } 1821249423Sdim 1822249423Sdim // Otherwise, see if our source is an insert. If so, then use the scalar 1823249423Sdim // component directly. 1824249423Sdim if (InsertElementInst *IEI = 1825249423Sdim dyn_cast<InsertElementInst>(CI.getOperand(0))) 1826249423Sdim return CastInst::Create(Instruction::BitCast, IEI->getOperand(1), 1827249423Sdim DestTy); 1828202375Srdivacky } 1829202375Srdivacky } 1830202375Srdivacky 1831202375Srdivacky if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(Src)) { 1832202375Srdivacky // Okay, we have (bitcast (shuffle ..)). Check to see if this is 1833207618Srdivacky // a bitcast to a vector with the same # elts. 1834249423Sdim if (SVI->hasOneUse() && DestTy->isVectorTy() && 1835263508Sdim DestTy->getVectorNumElements() == SVI->getType()->getNumElements() && 1836202375Srdivacky SVI->getType()->getNumElements() == 1837263508Sdim SVI->getOperand(0)->getType()->getVectorNumElements()) { 1838202375Srdivacky BitCastInst *Tmp; 1839202375Srdivacky // If either of the operands is a cast from CI.getType(), then 1840202375Srdivacky // evaluating the shuffle in the casted destination's type will allow 1841202375Srdivacky // us to eliminate at least one cast. 1842249423Sdim if (((Tmp = dyn_cast<BitCastInst>(SVI->getOperand(0))) && 1843202375Srdivacky Tmp->getOperand(0)->getType() == DestTy) || 1844249423Sdim ((Tmp = dyn_cast<BitCastInst>(SVI->getOperand(1))) && 1845202375Srdivacky Tmp->getOperand(0)->getType() == DestTy)) { 1846202375Srdivacky Value *LHS = Builder->CreateBitCast(SVI->getOperand(0), DestTy); 1847202375Srdivacky Value *RHS = Builder->CreateBitCast(SVI->getOperand(1), DestTy); 1848202375Srdivacky // Return a new shuffle vector. Use the same element ID's, as we 1849202375Srdivacky // know the vector types match #elts. 1850202375Srdivacky return new ShuffleVectorInst(LHS, RHS, SVI->getOperand(2)); 1851202375Srdivacky } 1852202375Srdivacky } 1853202375Srdivacky } 1854249423Sdim 1855204642Srdivacky if (SrcTy->isPointerTy()) 1856202375Srdivacky return commonPointerCastTransforms(CI); 1857202375Srdivacky return commonCastTransforms(CI); 1858202375Srdivacky} 1859263508Sdim 1860263508SdimInstruction *InstCombiner::visitAddrSpaceCast(AddrSpaceCastInst &CI) { 1861263508Sdim return commonCastTransforms(CI); 1862263508Sdim} 1863