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