1 //===- InstCombineCasts.cpp -----------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the visit functions for cast operations. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "InstCombineInternal.h" 14 #include "llvm/ADT/SetVector.h" 15 #include "llvm/Analysis/ConstantFolding.h" 16 #include "llvm/IR/DataLayout.h" 17 #include "llvm/IR/DebugInfo.h" 18 #include "llvm/IR/PatternMatch.h" 19 #include "llvm/Support/KnownBits.h" 20 #include "llvm/Transforms/InstCombine/InstCombiner.h" 21 #include <optional> 22 23 using namespace llvm; 24 using namespace PatternMatch; 25 26 #define DEBUG_TYPE "instcombine" 27 28 /// Given an expression that CanEvaluateTruncated or CanEvaluateSExtd returns 29 /// true for, actually insert the code to evaluate the expression. 30 Value *InstCombinerImpl::EvaluateInDifferentType(Value *V, Type *Ty, 31 bool isSigned) { 32 if (Constant *C = dyn_cast<Constant>(V)) 33 return ConstantFoldIntegerCast(C, Ty, isSigned, DL); 34 35 // Otherwise, it must be an instruction. 36 Instruction *I = cast<Instruction>(V); 37 Instruction *Res = nullptr; 38 unsigned Opc = I->getOpcode(); 39 switch (Opc) { 40 case Instruction::Add: 41 case Instruction::Sub: 42 case Instruction::Mul: 43 case Instruction::And: 44 case Instruction::Or: 45 case Instruction::Xor: 46 case Instruction::AShr: 47 case Instruction::LShr: 48 case Instruction::Shl: 49 case Instruction::UDiv: 50 case Instruction::URem: { 51 Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned); 52 Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned); 53 Res = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS); 54 break; 55 } 56 case Instruction::Trunc: 57 case Instruction::ZExt: 58 case Instruction::SExt: 59 // If the source type of the cast is the type we're trying for then we can 60 // just return the source. There's no need to insert it because it is not 61 // new. 62 if (I->getOperand(0)->getType() == Ty) 63 return I->getOperand(0); 64 65 // Otherwise, must be the same type of cast, so just reinsert a new one. 66 // This also handles the case of zext(trunc(x)) -> zext(x). 67 Res = CastInst::CreateIntegerCast(I->getOperand(0), Ty, 68 Opc == Instruction::SExt); 69 break; 70 case Instruction::Select: { 71 Value *True = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned); 72 Value *False = EvaluateInDifferentType(I->getOperand(2), Ty, isSigned); 73 Res = SelectInst::Create(I->getOperand(0), True, False); 74 break; 75 } 76 case Instruction::PHI: { 77 PHINode *OPN = cast<PHINode>(I); 78 PHINode *NPN = PHINode::Create(Ty, OPN->getNumIncomingValues()); 79 for (unsigned i = 0, e = OPN->getNumIncomingValues(); i != e; ++i) { 80 Value *V = 81 EvaluateInDifferentType(OPN->getIncomingValue(i), Ty, isSigned); 82 NPN->addIncoming(V, OPN->getIncomingBlock(i)); 83 } 84 Res = NPN; 85 break; 86 } 87 case Instruction::FPToUI: 88 case Instruction::FPToSI: 89 Res = CastInst::Create( 90 static_cast<Instruction::CastOps>(Opc), I->getOperand(0), Ty); 91 break; 92 case Instruction::Call: 93 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 94 switch (II->getIntrinsicID()) { 95 default: 96 llvm_unreachable("Unsupported call!"); 97 case Intrinsic::vscale: { 98 Function *Fn = Intrinsic::getOrInsertDeclaration( 99 I->getModule(), Intrinsic::vscale, {Ty}); 100 Res = CallInst::Create(Fn->getFunctionType(), Fn); 101 break; 102 } 103 } 104 } 105 break; 106 case Instruction::ShuffleVector: { 107 auto *ScalarTy = cast<VectorType>(Ty)->getElementType(); 108 auto *VTy = cast<VectorType>(I->getOperand(0)->getType()); 109 auto *FixedTy = VectorType::get(ScalarTy, VTy->getElementCount()); 110 Value *Op0 = EvaluateInDifferentType(I->getOperand(0), FixedTy, isSigned); 111 Value *Op1 = EvaluateInDifferentType(I->getOperand(1), FixedTy, isSigned); 112 Res = new ShuffleVectorInst(Op0, Op1, 113 cast<ShuffleVectorInst>(I)->getShuffleMask()); 114 break; 115 } 116 default: 117 // TODO: Can handle more cases here. 118 llvm_unreachable("Unreachable!"); 119 } 120 121 Res->takeName(I); 122 return InsertNewInstWith(Res, I->getIterator()); 123 } 124 125 Instruction::CastOps 126 InstCombinerImpl::isEliminableCastPair(const CastInst *CI1, 127 const CastInst *CI2) { 128 Type *SrcTy = CI1->getSrcTy(); 129 Type *MidTy = CI1->getDestTy(); 130 Type *DstTy = CI2->getDestTy(); 131 132 Instruction::CastOps firstOp = CI1->getOpcode(); 133 Instruction::CastOps secondOp = CI2->getOpcode(); 134 Type *SrcIntPtrTy = 135 SrcTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(SrcTy) : nullptr; 136 Type *MidIntPtrTy = 137 MidTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(MidTy) : nullptr; 138 Type *DstIntPtrTy = 139 DstTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(DstTy) : nullptr; 140 unsigned Res = CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, 141 DstTy, SrcIntPtrTy, MidIntPtrTy, 142 DstIntPtrTy); 143 144 // We don't want to form an inttoptr or ptrtoint that converts to an integer 145 // type that differs from the pointer size. 146 if ((Res == Instruction::IntToPtr && SrcTy != DstIntPtrTy) || 147 (Res == Instruction::PtrToInt && DstTy != SrcIntPtrTy)) 148 Res = 0; 149 150 return Instruction::CastOps(Res); 151 } 152 153 /// Implement the transforms common to all CastInst visitors. 154 Instruction *InstCombinerImpl::commonCastTransforms(CastInst &CI) { 155 Value *Src = CI.getOperand(0); 156 Type *Ty = CI.getType(); 157 158 if (auto *SrcC = dyn_cast<Constant>(Src)) 159 if (Constant *Res = ConstantFoldCastOperand(CI.getOpcode(), SrcC, Ty, DL)) 160 return replaceInstUsesWith(CI, Res); 161 162 // Try to eliminate a cast of a cast. 163 if (auto *CSrc = dyn_cast<CastInst>(Src)) { // A->B->C cast 164 if (Instruction::CastOps NewOpc = isEliminableCastPair(CSrc, &CI)) { 165 // The first cast (CSrc) is eliminable so we need to fix up or replace 166 // the second cast (CI). CSrc will then have a good chance of being dead. 167 auto *Res = CastInst::Create(NewOpc, CSrc->getOperand(0), Ty); 168 // Point debug users of the dying cast to the new one. 169 if (CSrc->hasOneUse()) 170 replaceAllDbgUsesWith(*CSrc, *Res, CI, DT); 171 return Res; 172 } 173 } 174 175 if (auto *Sel = dyn_cast<SelectInst>(Src)) { 176 // We are casting a select. Try to fold the cast into the select if the 177 // select does not have a compare instruction with matching operand types 178 // or the select is likely better done in a narrow type. 179 // Creating a select with operands that are different sizes than its 180 // condition may inhibit other folds and lead to worse codegen. 181 auto *Cmp = dyn_cast<CmpInst>(Sel->getCondition()); 182 if (!Cmp || Cmp->getOperand(0)->getType() != Sel->getType() || 183 (CI.getOpcode() == Instruction::Trunc && 184 shouldChangeType(CI.getSrcTy(), CI.getType()))) { 185 186 // If it's a bitcast involving vectors, make sure it has the same number 187 // of elements on both sides. 188 if (CI.getOpcode() != Instruction::BitCast || 189 match(&CI, m_ElementWiseBitCast(m_Value()))) { 190 if (Instruction *NV = FoldOpIntoSelect(CI, Sel)) { 191 replaceAllDbgUsesWith(*Sel, *NV, CI, DT); 192 return NV; 193 } 194 } 195 } 196 } 197 198 // If we are casting a PHI, then fold the cast into the PHI. 199 if (auto *PN = dyn_cast<PHINode>(Src)) { 200 // Don't do this if it would create a PHI node with an illegal type from a 201 // legal type. 202 if (!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() || 203 shouldChangeType(CI.getSrcTy(), CI.getType())) 204 if (Instruction *NV = foldOpIntoPhi(CI, PN)) 205 return NV; 206 } 207 208 // Canonicalize a unary shuffle after the cast if neither operation changes 209 // the size or element size of the input vector. 210 // TODO: We could allow size-changing ops if that doesn't harm codegen. 211 // cast (shuffle X, Mask) --> shuffle (cast X), Mask 212 Value *X; 213 ArrayRef<int> Mask; 214 if (match(Src, m_OneUse(m_Shuffle(m_Value(X), m_Undef(), m_Mask(Mask))))) { 215 // TODO: Allow scalable vectors? 216 auto *SrcTy = dyn_cast<FixedVectorType>(X->getType()); 217 auto *DestTy = dyn_cast<FixedVectorType>(Ty); 218 if (SrcTy && DestTy && 219 SrcTy->getNumElements() == DestTy->getNumElements() && 220 SrcTy->getPrimitiveSizeInBits() == DestTy->getPrimitiveSizeInBits()) { 221 Value *CastX = Builder.CreateCast(CI.getOpcode(), X, DestTy); 222 return new ShuffleVectorInst(CastX, Mask); 223 } 224 } 225 226 return nullptr; 227 } 228 229 /// Constants and extensions/truncates from the destination type are always 230 /// free to be evaluated in that type. This is a helper for canEvaluate*. 231 static bool canAlwaysEvaluateInType(Value *V, Type *Ty) { 232 if (isa<Constant>(V)) 233 return match(V, m_ImmConstant()); 234 235 Value *X; 236 if ((match(V, m_ZExtOrSExt(m_Value(X))) || match(V, m_Trunc(m_Value(X)))) && 237 X->getType() == Ty) 238 return true; 239 240 return false; 241 } 242 243 /// Filter out values that we can not evaluate in the destination type for free. 244 /// This is a helper for canEvaluate*. 245 static bool canNotEvaluateInType(Value *V, Type *Ty) { 246 if (!isa<Instruction>(V)) 247 return true; 248 // We don't extend or shrink something that has multiple uses -- doing so 249 // would require duplicating the instruction which isn't profitable. 250 if (!V->hasOneUse()) 251 return true; 252 253 return false; 254 } 255 256 /// Return true if we can evaluate the specified expression tree as type Ty 257 /// instead of its larger type, and arrive with the same value. 258 /// This is used by code that tries to eliminate truncates. 259 /// 260 /// Ty will always be a type smaller than V. We should return true if trunc(V) 261 /// can be computed by computing V in the smaller type. If V is an instruction, 262 /// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only 263 /// makes sense if x and y can be efficiently truncated. 264 /// 265 /// This function works on both vectors and scalars. 266 /// 267 static bool canEvaluateTruncated(Value *V, Type *Ty, InstCombinerImpl &IC, 268 Instruction *CxtI) { 269 if (canAlwaysEvaluateInType(V, Ty)) 270 return true; 271 if (canNotEvaluateInType(V, Ty)) 272 return false; 273 274 auto *I = cast<Instruction>(V); 275 Type *OrigTy = V->getType(); 276 switch (I->getOpcode()) { 277 case Instruction::Add: 278 case Instruction::Sub: 279 case Instruction::Mul: 280 case Instruction::And: 281 case Instruction::Or: 282 case Instruction::Xor: 283 // These operators can all arbitrarily be extended or truncated. 284 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) && 285 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI); 286 287 case Instruction::UDiv: 288 case Instruction::URem: { 289 // UDiv and URem can be truncated if all the truncated bits are zero. 290 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); 291 uint32_t BitWidth = Ty->getScalarSizeInBits(); 292 assert(BitWidth < OrigBitWidth && "Unexpected bitwidths!"); 293 APInt Mask = APInt::getBitsSetFrom(OrigBitWidth, BitWidth); 294 // Do not preserve the original context instruction. Simplifying div/rem 295 // based on later context may introduce a trap. 296 if (IC.MaskedValueIsZero(I->getOperand(0), Mask, 0, I) && 297 IC.MaskedValueIsZero(I->getOperand(1), Mask, 0, I)) { 298 return canEvaluateTruncated(I->getOperand(0), Ty, IC, I) && 299 canEvaluateTruncated(I->getOperand(1), Ty, IC, I); 300 } 301 break; 302 } 303 case Instruction::Shl: { 304 // If we are truncating the result of this SHL, and if it's a shift of an 305 // inrange amount, we can always perform a SHL in a smaller type. 306 uint32_t BitWidth = Ty->getScalarSizeInBits(); 307 KnownBits AmtKnownBits = 308 llvm::computeKnownBits(I->getOperand(1), IC.getDataLayout()); 309 if (AmtKnownBits.getMaxValue().ult(BitWidth)) 310 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) && 311 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI); 312 break; 313 } 314 case Instruction::LShr: { 315 // If this is a truncate of a logical shr, we can truncate it to a smaller 316 // lshr iff we know that the bits we would otherwise be shifting in are 317 // already zeros. 318 // TODO: It is enough to check that the bits we would be shifting in are 319 // zero - use AmtKnownBits.getMaxValue(). 320 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); 321 uint32_t BitWidth = Ty->getScalarSizeInBits(); 322 KnownBits AmtKnownBits = 323 llvm::computeKnownBits(I->getOperand(1), IC.getDataLayout()); 324 APInt ShiftedBits = APInt::getBitsSetFrom(OrigBitWidth, BitWidth); 325 if (AmtKnownBits.getMaxValue().ult(BitWidth) && 326 IC.MaskedValueIsZero(I->getOperand(0), ShiftedBits, 0, CxtI)) { 327 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) && 328 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI); 329 } 330 break; 331 } 332 case Instruction::AShr: { 333 // If this is a truncate of an arithmetic shr, we can truncate it to a 334 // smaller ashr iff we know that all the bits from the sign bit of the 335 // original type and the sign bit of the truncate type are similar. 336 // TODO: It is enough to check that the bits we would be shifting in are 337 // similar to sign bit of the truncate type. 338 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); 339 uint32_t BitWidth = Ty->getScalarSizeInBits(); 340 KnownBits AmtKnownBits = 341 llvm::computeKnownBits(I->getOperand(1), IC.getDataLayout()); 342 unsigned ShiftedBits = OrigBitWidth - BitWidth; 343 if (AmtKnownBits.getMaxValue().ult(BitWidth) && 344 ShiftedBits < IC.ComputeNumSignBits(I->getOperand(0), 0, CxtI)) 345 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) && 346 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI); 347 break; 348 } 349 case Instruction::Trunc: 350 // trunc(trunc(x)) -> trunc(x) 351 return true; 352 case Instruction::ZExt: 353 case Instruction::SExt: 354 // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest 355 // trunc(ext(x)) -> trunc(x) if the source type is larger than the new dest 356 return true; 357 case Instruction::Select: { 358 SelectInst *SI = cast<SelectInst>(I); 359 return canEvaluateTruncated(SI->getTrueValue(), Ty, IC, CxtI) && 360 canEvaluateTruncated(SI->getFalseValue(), Ty, IC, CxtI); 361 } 362 case Instruction::PHI: { 363 // We can change a phi if we can change all operands. Note that we never 364 // get into trouble with cyclic PHIs here because we only consider 365 // instructions with a single use. 366 PHINode *PN = cast<PHINode>(I); 367 for (Value *IncValue : PN->incoming_values()) 368 if (!canEvaluateTruncated(IncValue, Ty, IC, CxtI)) 369 return false; 370 return true; 371 } 372 case Instruction::FPToUI: 373 case Instruction::FPToSI: { 374 // If the integer type can hold the max FP value, it is safe to cast 375 // directly to that type. Otherwise, we may create poison via overflow 376 // that did not exist in the original code. 377 Type *InputTy = I->getOperand(0)->getType()->getScalarType(); 378 const fltSemantics &Semantics = InputTy->getFltSemantics(); 379 uint32_t MinBitWidth = 380 APFloatBase::semanticsIntSizeInBits(Semantics, 381 I->getOpcode() == Instruction::FPToSI); 382 return Ty->getScalarSizeInBits() >= MinBitWidth; 383 } 384 case Instruction::ShuffleVector: 385 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) && 386 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI); 387 default: 388 // TODO: Can handle more cases here. 389 break; 390 } 391 392 return false; 393 } 394 395 /// Given a vector that is bitcast to an integer, optionally logically 396 /// right-shifted, and truncated, convert it to an extractelement. 397 /// Example (big endian): 398 /// trunc (lshr (bitcast <4 x i32> %X to i128), 32) to i32 399 /// ---> 400 /// extractelement <4 x i32> %X, 1 401 static Instruction *foldVecTruncToExtElt(TruncInst &Trunc, 402 InstCombinerImpl &IC) { 403 Value *TruncOp = Trunc.getOperand(0); 404 Type *DestType = Trunc.getType(); 405 if (!TruncOp->hasOneUse() || !isa<IntegerType>(DestType)) 406 return nullptr; 407 408 Value *VecInput = nullptr; 409 ConstantInt *ShiftVal = nullptr; 410 if (!match(TruncOp, m_CombineOr(m_BitCast(m_Value(VecInput)), 411 m_LShr(m_BitCast(m_Value(VecInput)), 412 m_ConstantInt(ShiftVal)))) || 413 !isa<VectorType>(VecInput->getType())) 414 return nullptr; 415 416 VectorType *VecType = cast<VectorType>(VecInput->getType()); 417 unsigned VecWidth = VecType->getPrimitiveSizeInBits(); 418 unsigned DestWidth = DestType->getPrimitiveSizeInBits(); 419 unsigned ShiftAmount = ShiftVal ? ShiftVal->getZExtValue() : 0; 420 421 if ((VecWidth % DestWidth != 0) || (ShiftAmount % DestWidth != 0)) 422 return nullptr; 423 424 // If the element type of the vector doesn't match the result type, 425 // bitcast it to a vector type that we can extract from. 426 unsigned NumVecElts = VecWidth / DestWidth; 427 if (VecType->getElementType() != DestType) { 428 VecType = FixedVectorType::get(DestType, NumVecElts); 429 VecInput = IC.Builder.CreateBitCast(VecInput, VecType, "bc"); 430 } 431 432 unsigned Elt = ShiftAmount / DestWidth; 433 if (IC.getDataLayout().isBigEndian()) 434 Elt = NumVecElts - 1 - Elt; 435 436 return ExtractElementInst::Create(VecInput, IC.Builder.getInt32(Elt)); 437 } 438 439 /// Whenever an element is extracted from a vector, optionally shifted down, and 440 /// then truncated, canonicalize by converting it to a bitcast followed by an 441 /// extractelement. 442 /// 443 /// Examples (little endian): 444 /// trunc (extractelement <4 x i64> %X, 0) to i32 445 /// ---> 446 /// extractelement <8 x i32> (bitcast <4 x i64> %X to <8 x i32>), i32 0 447 /// 448 /// trunc (lshr (extractelement <4 x i32> %X, 0), 8) to i8 449 /// ---> 450 /// extractelement <16 x i8> (bitcast <4 x i32> %X to <16 x i8>), i32 1 451 static Instruction *foldVecExtTruncToExtElt(TruncInst &Trunc, 452 InstCombinerImpl &IC) { 453 Value *Src = Trunc.getOperand(0); 454 Type *SrcType = Src->getType(); 455 Type *DstType = Trunc.getType(); 456 457 // Only attempt this if we have simple aliasing of the vector elements. 458 // A badly fit destination size would result in an invalid cast. 459 unsigned SrcBits = SrcType->getScalarSizeInBits(); 460 unsigned DstBits = DstType->getScalarSizeInBits(); 461 unsigned TruncRatio = SrcBits / DstBits; 462 if ((SrcBits % DstBits) != 0) 463 return nullptr; 464 465 Value *VecOp; 466 ConstantInt *Cst; 467 const APInt *ShiftAmount = nullptr; 468 if (!match(Src, m_OneUse(m_ExtractElt(m_Value(VecOp), m_ConstantInt(Cst)))) && 469 !match(Src, 470 m_OneUse(m_LShr(m_ExtractElt(m_Value(VecOp), m_ConstantInt(Cst)), 471 m_APInt(ShiftAmount))))) 472 return nullptr; 473 474 auto *VecOpTy = cast<VectorType>(VecOp->getType()); 475 auto VecElts = VecOpTy->getElementCount(); 476 477 uint64_t BitCastNumElts = VecElts.getKnownMinValue() * TruncRatio; 478 uint64_t VecOpIdx = Cst->getZExtValue(); 479 uint64_t NewIdx = IC.getDataLayout().isBigEndian() 480 ? (VecOpIdx + 1) * TruncRatio - 1 481 : VecOpIdx * TruncRatio; 482 483 // Adjust index by the whole number of truncated elements. 484 if (ShiftAmount) { 485 // Check shift amount is in range and shifts a whole number of truncated 486 // elements. 487 if (ShiftAmount->uge(SrcBits) || ShiftAmount->urem(DstBits) != 0) 488 return nullptr; 489 490 uint64_t IdxOfs = ShiftAmount->udiv(DstBits).getZExtValue(); 491 NewIdx = IC.getDataLayout().isBigEndian() ? (NewIdx - IdxOfs) 492 : (NewIdx + IdxOfs); 493 } 494 495 assert(BitCastNumElts <= std::numeric_limits<uint32_t>::max() && 496 NewIdx <= std::numeric_limits<uint32_t>::max() && "overflow 32-bits"); 497 498 auto *BitCastTo = 499 VectorType::get(DstType, BitCastNumElts, VecElts.isScalable()); 500 Value *BitCast = IC.Builder.CreateBitCast(VecOp, BitCastTo); 501 return ExtractElementInst::Create(BitCast, IC.Builder.getInt32(NewIdx)); 502 } 503 504 /// Funnel/Rotate left/right may occur in a wider type than necessary because of 505 /// type promotion rules. Try to narrow the inputs and convert to funnel shift. 506 Instruction *InstCombinerImpl::narrowFunnelShift(TruncInst &Trunc) { 507 assert((isa<VectorType>(Trunc.getSrcTy()) || 508 shouldChangeType(Trunc.getSrcTy(), Trunc.getType())) && 509 "Don't narrow to an illegal scalar type"); 510 511 // Bail out on strange types. It is possible to handle some of these patterns 512 // even with non-power-of-2 sizes, but it is not a likely scenario. 513 Type *DestTy = Trunc.getType(); 514 unsigned NarrowWidth = DestTy->getScalarSizeInBits(); 515 unsigned WideWidth = Trunc.getSrcTy()->getScalarSizeInBits(); 516 if (!isPowerOf2_32(NarrowWidth)) 517 return nullptr; 518 519 // First, find an or'd pair of opposite shifts: 520 // trunc (or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1)) 521 BinaryOperator *Or0, *Or1; 522 if (!match(Trunc.getOperand(0), m_OneUse(m_Or(m_BinOp(Or0), m_BinOp(Or1))))) 523 return nullptr; 524 525 Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1; 526 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal0), m_Value(ShAmt0)))) || 527 !match(Or1, m_OneUse(m_LogicalShift(m_Value(ShVal1), m_Value(ShAmt1)))) || 528 Or0->getOpcode() == Or1->getOpcode()) 529 return nullptr; 530 531 // Canonicalize to or(shl(ShVal0, ShAmt0), lshr(ShVal1, ShAmt1)). 532 if (Or0->getOpcode() == BinaryOperator::LShr) { 533 std::swap(Or0, Or1); 534 std::swap(ShVal0, ShVal1); 535 std::swap(ShAmt0, ShAmt1); 536 } 537 assert(Or0->getOpcode() == BinaryOperator::Shl && 538 Or1->getOpcode() == BinaryOperator::LShr && 539 "Illegal or(shift,shift) pair"); 540 541 // Match the shift amount operands for a funnel/rotate pattern. This always 542 // matches a subtraction on the R operand. 543 auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * { 544 // The shift amounts may add up to the narrow bit width: 545 // (shl ShVal0, L) | (lshr ShVal1, Width - L) 546 // If this is a funnel shift (different operands are shifted), then the 547 // shift amount can not over-shift (create poison) in the narrow type. 548 unsigned MaxShiftAmountWidth = Log2_32(NarrowWidth); 549 APInt HiBitMask = ~APInt::getLowBitsSet(WideWidth, MaxShiftAmountWidth); 550 if (ShVal0 == ShVal1 || MaskedValueIsZero(L, HiBitMask)) 551 if (match(R, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(L))))) 552 return L; 553 554 // The following patterns currently only work for rotation patterns. 555 // TODO: Add more general funnel-shift compatible patterns. 556 if (ShVal0 != ShVal1) 557 return nullptr; 558 559 // The shift amount may be masked with negation: 560 // (shl ShVal0, (X & (Width - 1))) | (lshr ShVal1, ((-X) & (Width - 1))) 561 Value *X; 562 unsigned Mask = Width - 1; 563 if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) && 564 match(R, m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask)))) 565 return X; 566 567 // Same as above, but the shift amount may be extended after masking: 568 if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) && 569 match(R, m_ZExt(m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask))))) 570 return X; 571 572 return nullptr; 573 }; 574 575 Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, NarrowWidth); 576 bool IsFshl = true; // Sub on LSHR. 577 if (!ShAmt) { 578 ShAmt = matchShiftAmount(ShAmt1, ShAmt0, NarrowWidth); 579 IsFshl = false; // Sub on SHL. 580 } 581 if (!ShAmt) 582 return nullptr; 583 584 // The right-shifted value must have high zeros in the wide type (for example 585 // from 'zext', 'and' or 'shift'). High bits of the left-shifted value are 586 // truncated, so those do not matter. 587 APInt HiBitMask = APInt::getHighBitsSet(WideWidth, WideWidth - NarrowWidth); 588 if (!MaskedValueIsZero(ShVal1, HiBitMask, 0, &Trunc)) 589 return nullptr; 590 591 // Adjust the width of ShAmt for narrowed funnel shift operation: 592 // - Zero-extend if ShAmt is narrower than the destination type. 593 // - Truncate if ShAmt is wider, discarding non-significant high-order bits. 594 // This prepares ShAmt for llvm.fshl.i8(trunc(ShVal), trunc(ShVal), 595 // zext/trunc(ShAmt)). 596 Value *NarrowShAmt = Builder.CreateZExtOrTrunc(ShAmt, DestTy); 597 598 Value *X, *Y; 599 X = Y = Builder.CreateTrunc(ShVal0, DestTy); 600 if (ShVal0 != ShVal1) 601 Y = Builder.CreateTrunc(ShVal1, DestTy); 602 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr; 603 Function *F = 604 Intrinsic::getOrInsertDeclaration(Trunc.getModule(), IID, DestTy); 605 return CallInst::Create(F, {X, Y, NarrowShAmt}); 606 } 607 608 /// Try to narrow the width of math or bitwise logic instructions by pulling a 609 /// truncate ahead of binary operators. 610 Instruction *InstCombinerImpl::narrowBinOp(TruncInst &Trunc) { 611 Type *SrcTy = Trunc.getSrcTy(); 612 Type *DestTy = Trunc.getType(); 613 unsigned SrcWidth = SrcTy->getScalarSizeInBits(); 614 unsigned DestWidth = DestTy->getScalarSizeInBits(); 615 616 if (!isa<VectorType>(SrcTy) && !shouldChangeType(SrcTy, DestTy)) 617 return nullptr; 618 619 BinaryOperator *BinOp; 620 if (!match(Trunc.getOperand(0), m_OneUse(m_BinOp(BinOp)))) 621 return nullptr; 622 623 Value *BinOp0 = BinOp->getOperand(0); 624 Value *BinOp1 = BinOp->getOperand(1); 625 switch (BinOp->getOpcode()) { 626 case Instruction::And: 627 case Instruction::Or: 628 case Instruction::Xor: 629 case Instruction::Add: 630 case Instruction::Sub: 631 case Instruction::Mul: { 632 Constant *C; 633 if (match(BinOp0, m_Constant(C))) { 634 // trunc (binop C, X) --> binop (trunc C', X) 635 Constant *NarrowC = ConstantExpr::getTrunc(C, DestTy); 636 Value *TruncX = Builder.CreateTrunc(BinOp1, DestTy); 637 return BinaryOperator::Create(BinOp->getOpcode(), NarrowC, TruncX); 638 } 639 if (match(BinOp1, m_Constant(C))) { 640 // trunc (binop X, C) --> binop (trunc X, C') 641 Constant *NarrowC = ConstantExpr::getTrunc(C, DestTy); 642 Value *TruncX = Builder.CreateTrunc(BinOp0, DestTy); 643 return BinaryOperator::Create(BinOp->getOpcode(), TruncX, NarrowC); 644 } 645 Value *X; 646 if (match(BinOp0, m_ZExtOrSExt(m_Value(X))) && X->getType() == DestTy) { 647 // trunc (binop (ext X), Y) --> binop X, (trunc Y) 648 Value *NarrowOp1 = Builder.CreateTrunc(BinOp1, DestTy); 649 return BinaryOperator::Create(BinOp->getOpcode(), X, NarrowOp1); 650 } 651 if (match(BinOp1, m_ZExtOrSExt(m_Value(X))) && X->getType() == DestTy) { 652 // trunc (binop Y, (ext X)) --> binop (trunc Y), X 653 Value *NarrowOp0 = Builder.CreateTrunc(BinOp0, DestTy); 654 return BinaryOperator::Create(BinOp->getOpcode(), NarrowOp0, X); 655 } 656 break; 657 } 658 case Instruction::LShr: 659 case Instruction::AShr: { 660 // trunc (*shr (trunc A), C) --> trunc(*shr A, C) 661 Value *A; 662 Constant *C; 663 if (match(BinOp0, m_Trunc(m_Value(A))) && match(BinOp1, m_Constant(C))) { 664 unsigned MaxShiftAmt = SrcWidth - DestWidth; 665 // If the shift is small enough, all zero/sign bits created by the shift 666 // are removed by the trunc. 667 if (match(C, m_SpecificInt_ICMP(ICmpInst::ICMP_ULE, 668 APInt(SrcWidth, MaxShiftAmt)))) { 669 auto *OldShift = cast<Instruction>(Trunc.getOperand(0)); 670 bool IsExact = OldShift->isExact(); 671 if (Constant *ShAmt = ConstantFoldIntegerCast(C, A->getType(), 672 /*IsSigned*/ true, DL)) { 673 ShAmt = Constant::mergeUndefsWith(ShAmt, C); 674 Value *Shift = 675 OldShift->getOpcode() == Instruction::AShr 676 ? Builder.CreateAShr(A, ShAmt, OldShift->getName(), IsExact) 677 : Builder.CreateLShr(A, ShAmt, OldShift->getName(), IsExact); 678 return CastInst::CreateTruncOrBitCast(Shift, DestTy); 679 } 680 } 681 } 682 break; 683 } 684 default: break; 685 } 686 687 if (Instruction *NarrowOr = narrowFunnelShift(Trunc)) 688 return NarrowOr; 689 690 return nullptr; 691 } 692 693 /// Try to narrow the width of a splat shuffle. This could be generalized to any 694 /// shuffle with a constant operand, but we limit the transform to avoid 695 /// creating a shuffle type that targets may not be able to lower effectively. 696 static Instruction *shrinkSplatShuffle(TruncInst &Trunc, 697 InstCombiner::BuilderTy &Builder) { 698 auto *Shuf = dyn_cast<ShuffleVectorInst>(Trunc.getOperand(0)); 699 if (Shuf && Shuf->hasOneUse() && match(Shuf->getOperand(1), m_Undef()) && 700 all_equal(Shuf->getShuffleMask()) && 701 Shuf->getType() == Shuf->getOperand(0)->getType()) { 702 // trunc (shuf X, Undef, SplatMask) --> shuf (trunc X), Poison, SplatMask 703 // trunc (shuf X, Poison, SplatMask) --> shuf (trunc X), Poison, SplatMask 704 Value *NarrowOp = Builder.CreateTrunc(Shuf->getOperand(0), Trunc.getType()); 705 return new ShuffleVectorInst(NarrowOp, Shuf->getShuffleMask()); 706 } 707 708 return nullptr; 709 } 710 711 /// Try to narrow the width of an insert element. This could be generalized for 712 /// any vector constant, but we limit the transform to insertion into undef to 713 /// avoid potential backend problems from unsupported insertion widths. This 714 /// could also be extended to handle the case of inserting a scalar constant 715 /// into a vector variable. 716 static Instruction *shrinkInsertElt(CastInst &Trunc, 717 InstCombiner::BuilderTy &Builder) { 718 Instruction::CastOps Opcode = Trunc.getOpcode(); 719 assert((Opcode == Instruction::Trunc || Opcode == Instruction::FPTrunc) && 720 "Unexpected instruction for shrinking"); 721 722 auto *InsElt = dyn_cast<InsertElementInst>(Trunc.getOperand(0)); 723 if (!InsElt || !InsElt->hasOneUse()) 724 return nullptr; 725 726 Type *DestTy = Trunc.getType(); 727 Type *DestScalarTy = DestTy->getScalarType(); 728 Value *VecOp = InsElt->getOperand(0); 729 Value *ScalarOp = InsElt->getOperand(1); 730 Value *Index = InsElt->getOperand(2); 731 732 if (match(VecOp, m_Undef())) { 733 // trunc (inselt undef, X, Index) --> inselt undef, (trunc X), Index 734 // fptrunc (inselt undef, X, Index) --> inselt undef, (fptrunc X), Index 735 UndefValue *NarrowUndef = UndefValue::get(DestTy); 736 Value *NarrowOp = Builder.CreateCast(Opcode, ScalarOp, DestScalarTy); 737 return InsertElementInst::Create(NarrowUndef, NarrowOp, Index); 738 } 739 740 return nullptr; 741 } 742 743 Instruction *InstCombinerImpl::visitTrunc(TruncInst &Trunc) { 744 if (Instruction *Result = commonCastTransforms(Trunc)) 745 return Result; 746 747 Value *Src = Trunc.getOperand(0); 748 Type *DestTy = Trunc.getType(), *SrcTy = Src->getType(); 749 unsigned DestWidth = DestTy->getScalarSizeInBits(); 750 unsigned SrcWidth = SrcTy->getScalarSizeInBits(); 751 752 // Attempt to truncate the entire input expression tree to the destination 753 // type. Only do this if the dest type is a simple type, don't convert the 754 // expression tree to something weird like i93 unless the source is also 755 // strange. 756 if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) && 757 canEvaluateTruncated(Src, DestTy, *this, &Trunc)) { 758 759 // If this cast is a truncate, evaluting in a different type always 760 // eliminates the cast, so it is always a win. 761 LLVM_DEBUG( 762 dbgs() << "ICE: EvaluateInDifferentType converting expression type" 763 " to avoid cast: " 764 << Trunc << '\n'); 765 Value *Res = EvaluateInDifferentType(Src, DestTy, false); 766 assert(Res->getType() == DestTy); 767 return replaceInstUsesWith(Trunc, Res); 768 } 769 770 // For integer types, check if we can shorten the entire input expression to 771 // DestWidth * 2, which won't allow removing the truncate, but reducing the 772 // width may enable further optimizations, e.g. allowing for larger 773 // vectorization factors. 774 if (auto *DestITy = dyn_cast<IntegerType>(DestTy)) { 775 if (DestWidth * 2 < SrcWidth) { 776 auto *NewDestTy = DestITy->getExtendedType(); 777 if (shouldChangeType(SrcTy, NewDestTy) && 778 canEvaluateTruncated(Src, NewDestTy, *this, &Trunc)) { 779 LLVM_DEBUG( 780 dbgs() << "ICE: EvaluateInDifferentType converting expression type" 781 " to reduce the width of operand of" 782 << Trunc << '\n'); 783 Value *Res = EvaluateInDifferentType(Src, NewDestTy, false); 784 return new TruncInst(Res, DestTy); 785 } 786 } 787 } 788 789 // See if we can simplify any instructions used by the input whose sole 790 // purpose is to compute bits we don't care about. 791 if (SimplifyDemandedInstructionBits(Trunc)) 792 return &Trunc; 793 794 if (DestWidth == 1) { 795 Value *Zero = Constant::getNullValue(SrcTy); 796 797 Value *X; 798 const APInt *C1; 799 Constant *C2; 800 if (match(Src, m_OneUse(m_Shr(m_Shl(m_Power2(C1), m_Value(X)), 801 m_ImmConstant(C2))))) { 802 // trunc ((C1 << X) >> C2) to i1 --> X == (C2-cttz(C1)), where C1 is pow2 803 Constant *Log2C1 = ConstantInt::get(SrcTy, C1->exactLogBase2()); 804 Constant *CmpC = ConstantExpr::getSub(C2, Log2C1); 805 return new ICmpInst(ICmpInst::ICMP_EQ, X, CmpC); 806 } 807 808 Constant *C; 809 if (match(Src, m_OneUse(m_LShr(m_Value(X), m_ImmConstant(C))))) { 810 // trunc (lshr X, C) to i1 --> icmp ne (and X, C'), 0 811 Constant *One = ConstantInt::get(SrcTy, APInt(SrcWidth, 1)); 812 Value *MaskC = Builder.CreateShl(One, C); 813 Value *And = Builder.CreateAnd(X, MaskC); 814 return new ICmpInst(ICmpInst::ICMP_NE, And, Zero); 815 } 816 if (match(Src, m_OneUse(m_c_Or(m_LShr(m_Value(X), m_ImmConstant(C)), 817 m_Deferred(X))))) { 818 // trunc (or (lshr X, C), X) to i1 --> icmp ne (and X, C'), 0 819 Constant *One = ConstantInt::get(SrcTy, APInt(SrcWidth, 1)); 820 Value *MaskC = Builder.CreateShl(One, C); 821 Value *And = Builder.CreateAnd(X, Builder.CreateOr(MaskC, One)); 822 return new ICmpInst(ICmpInst::ICMP_NE, And, Zero); 823 } 824 825 { 826 const APInt *C; 827 if (match(Src, m_Shl(m_APInt(C), m_Value(X))) && (*C)[0] == 1) { 828 // trunc (C << X) to i1 --> X == 0, where C is odd 829 return new ICmpInst(ICmpInst::Predicate::ICMP_EQ, X, Zero); 830 } 831 } 832 833 if (Trunc.hasNoUnsignedWrap() || Trunc.hasNoSignedWrap()) { 834 Value *X, *Y; 835 if (match(Src, m_Xor(m_Value(X), m_Value(Y)))) 836 return new ICmpInst(ICmpInst::ICMP_NE, X, Y); 837 } 838 } 839 840 Value *A, *B; 841 Constant *C; 842 if (match(Src, m_LShr(m_SExt(m_Value(A)), m_Constant(C)))) { 843 unsigned AWidth = A->getType()->getScalarSizeInBits(); 844 unsigned MaxShiftAmt = SrcWidth - std::max(DestWidth, AWidth); 845 auto *OldSh = cast<Instruction>(Src); 846 bool IsExact = OldSh->isExact(); 847 848 // If the shift is small enough, all zero bits created by the shift are 849 // removed by the trunc. 850 if (match(C, m_SpecificInt_ICMP(ICmpInst::ICMP_ULE, 851 APInt(SrcWidth, MaxShiftAmt)))) { 852 auto GetNewShAmt = [&](unsigned Width) { 853 Constant *MaxAmt = ConstantInt::get(SrcTy, Width - 1, false); 854 Constant *Cmp = 855 ConstantFoldCompareInstOperands(ICmpInst::ICMP_ULT, C, MaxAmt, DL); 856 Constant *ShAmt = ConstantFoldSelectInstruction(Cmp, C, MaxAmt); 857 return ConstantFoldCastOperand(Instruction::Trunc, ShAmt, A->getType(), 858 DL); 859 }; 860 861 // trunc (lshr (sext A), C) --> ashr A, C 862 if (A->getType() == DestTy) { 863 Constant *ShAmt = GetNewShAmt(DestWidth); 864 ShAmt = Constant::mergeUndefsWith(ShAmt, C); 865 return IsExact ? BinaryOperator::CreateExactAShr(A, ShAmt) 866 : BinaryOperator::CreateAShr(A, ShAmt); 867 } 868 // The types are mismatched, so create a cast after shifting: 869 // trunc (lshr (sext A), C) --> sext/trunc (ashr A, C) 870 if (Src->hasOneUse()) { 871 Constant *ShAmt = GetNewShAmt(AWidth); 872 Value *Shift = Builder.CreateAShr(A, ShAmt, "", IsExact); 873 return CastInst::CreateIntegerCast(Shift, DestTy, true); 874 } 875 } 876 // TODO: Mask high bits with 'and'. 877 } 878 879 if (Instruction *I = narrowBinOp(Trunc)) 880 return I; 881 882 if (Instruction *I = shrinkSplatShuffle(Trunc, Builder)) 883 return I; 884 885 if (Instruction *I = shrinkInsertElt(Trunc, Builder)) 886 return I; 887 888 if (Src->hasOneUse() && 889 (isa<VectorType>(SrcTy) || shouldChangeType(SrcTy, DestTy))) { 890 // Transform "trunc (shl X, cst)" -> "shl (trunc X), cst" so long as the 891 // dest type is native and cst < dest size. 892 if (match(Src, m_Shl(m_Value(A), m_Constant(C))) && 893 !match(A, m_Shr(m_Value(), m_Constant()))) { 894 // Skip shifts of shift by constants. It undoes a combine in 895 // FoldShiftByConstant and is the extend in reg pattern. 896 APInt Threshold = APInt(C->getType()->getScalarSizeInBits(), DestWidth); 897 if (match(C, m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, Threshold))) { 898 Value *NewTrunc = Builder.CreateTrunc(A, DestTy, A->getName() + ".tr"); 899 return BinaryOperator::Create(Instruction::Shl, NewTrunc, 900 ConstantExpr::getTrunc(C, DestTy)); 901 } 902 } 903 } 904 905 if (Instruction *I = foldVecTruncToExtElt(Trunc, *this)) 906 return I; 907 908 if (Instruction *I = foldVecExtTruncToExtElt(Trunc, *this)) 909 return I; 910 911 // trunc (ctlz_i32(zext(A), B) --> add(ctlz_i16(A, B), C) 912 if (match(Src, m_OneUse(m_Intrinsic<Intrinsic::ctlz>(m_ZExt(m_Value(A)), 913 m_Value(B))))) { 914 unsigned AWidth = A->getType()->getScalarSizeInBits(); 915 if (AWidth == DestWidth && AWidth > Log2_32(SrcWidth)) { 916 Value *WidthDiff = ConstantInt::get(A->getType(), SrcWidth - AWidth); 917 Value *NarrowCtlz = 918 Builder.CreateIntrinsic(Intrinsic::ctlz, {Trunc.getType()}, {A, B}); 919 return BinaryOperator::CreateAdd(NarrowCtlz, WidthDiff); 920 } 921 } 922 923 if (match(Src, m_VScale())) { 924 if (Trunc.getFunction() && 925 Trunc.getFunction()->hasFnAttribute(Attribute::VScaleRange)) { 926 Attribute Attr = 927 Trunc.getFunction()->getFnAttribute(Attribute::VScaleRange); 928 if (std::optional<unsigned> MaxVScale = Attr.getVScaleRangeMax()) { 929 if (Log2_32(*MaxVScale) < DestWidth) { 930 Value *VScale = Builder.CreateVScale(ConstantInt::get(DestTy, 1)); 931 return replaceInstUsesWith(Trunc, VScale); 932 } 933 } 934 } 935 } 936 937 if (DestWidth == 1 && 938 (Trunc.hasNoUnsignedWrap() || Trunc.hasNoSignedWrap()) && 939 isKnownNonZero(Src, SQ.getWithInstruction(&Trunc))) 940 return replaceInstUsesWith(Trunc, ConstantInt::getTrue(DestTy)); 941 942 bool Changed = false; 943 if (!Trunc.hasNoSignedWrap() && 944 ComputeMaxSignificantBits(Src, /*Depth=*/0, &Trunc) <= DestWidth) { 945 Trunc.setHasNoSignedWrap(true); 946 Changed = true; 947 } 948 if (!Trunc.hasNoUnsignedWrap() && 949 MaskedValueIsZero(Src, APInt::getBitsSetFrom(SrcWidth, DestWidth), 950 /*Depth=*/0, &Trunc)) { 951 Trunc.setHasNoUnsignedWrap(true); 952 Changed = true; 953 } 954 955 return Changed ? &Trunc : nullptr; 956 } 957 958 Instruction *InstCombinerImpl::transformZExtICmp(ICmpInst *Cmp, 959 ZExtInst &Zext) { 960 // If we are just checking for a icmp eq of a single bit and zext'ing it 961 // to an integer, then shift the bit to the appropriate place and then 962 // cast to integer to avoid the comparison. 963 964 // FIXME: This set of transforms does not check for extra uses and/or creates 965 // an extra instruction (an optional final cast is not included 966 // in the transform comments). We may also want to favor icmp over 967 // shifts in cases of equal instructions because icmp has better 968 // analysis in general (invert the transform). 969 970 const APInt *Op1CV; 971 if (match(Cmp->getOperand(1), m_APInt(Op1CV))) { 972 973 // zext (x <s 0) to i32 --> x>>u31 true if signbit set. 974 if (Cmp->getPredicate() == ICmpInst::ICMP_SLT && Op1CV->isZero()) { 975 Value *In = Cmp->getOperand(0); 976 Value *Sh = ConstantInt::get(In->getType(), 977 In->getType()->getScalarSizeInBits() - 1); 978 In = Builder.CreateLShr(In, Sh, In->getName() + ".lobit"); 979 if (In->getType() != Zext.getType()) 980 In = Builder.CreateIntCast(In, Zext.getType(), false /*ZExt*/); 981 982 return replaceInstUsesWith(Zext, In); 983 } 984 985 // zext (X == 0) to i32 --> X^1 iff X has only the low bit set. 986 // zext (X == 0) to i32 --> (X>>1)^1 iff X has only the 2nd bit set. 987 // zext (X != 0) to i32 --> X iff X has only the low bit set. 988 // zext (X != 0) to i32 --> X>>1 iff X has only the 2nd bit set. 989 990 if (Op1CV->isZero() && Cmp->isEquality()) { 991 // Exactly 1 possible 1? But not the high-bit because that is 992 // canonicalized to this form. 993 KnownBits Known = computeKnownBits(Cmp->getOperand(0), 0, &Zext); 994 APInt KnownZeroMask(~Known.Zero); 995 uint32_t ShAmt = KnownZeroMask.logBase2(); 996 bool IsExpectShAmt = KnownZeroMask.isPowerOf2() && 997 (Zext.getType()->getScalarSizeInBits() != ShAmt + 1); 998 if (IsExpectShAmt && 999 (Cmp->getOperand(0)->getType() == Zext.getType() || 1000 Cmp->getPredicate() == ICmpInst::ICMP_NE || ShAmt == 0)) { 1001 Value *In = Cmp->getOperand(0); 1002 if (ShAmt) { 1003 // Perform a logical shr by shiftamt. 1004 // Insert the shift to put the result in the low bit. 1005 In = Builder.CreateLShr(In, ConstantInt::get(In->getType(), ShAmt), 1006 In->getName() + ".lobit"); 1007 } 1008 1009 // Toggle the low bit for "X == 0". 1010 if (Cmp->getPredicate() == ICmpInst::ICMP_EQ) 1011 In = Builder.CreateXor(In, ConstantInt::get(In->getType(), 1)); 1012 1013 if (Zext.getType() == In->getType()) 1014 return replaceInstUsesWith(Zext, In); 1015 1016 Value *IntCast = Builder.CreateIntCast(In, Zext.getType(), false); 1017 return replaceInstUsesWith(Zext, IntCast); 1018 } 1019 } 1020 } 1021 1022 if (Cmp->isEquality()) { 1023 // Test if a bit is clear/set using a shifted-one mask: 1024 // zext (icmp eq (and X, (1 << ShAmt)), 0) --> and (lshr (not X), ShAmt), 1 1025 // zext (icmp ne (and X, (1 << ShAmt)), 0) --> and (lshr X, ShAmt), 1 1026 Value *X, *ShAmt; 1027 if (Cmp->hasOneUse() && match(Cmp->getOperand(1), m_ZeroInt()) && 1028 match(Cmp->getOperand(0), 1029 m_OneUse(m_c_And(m_Shl(m_One(), m_Value(ShAmt)), m_Value(X))))) { 1030 auto *And = cast<BinaryOperator>(Cmp->getOperand(0)); 1031 Value *Shift = And->getOperand(X == And->getOperand(0) ? 1 : 0); 1032 if (Zext.getType() == And->getType() || 1033 Cmp->getPredicate() != ICmpInst::ICMP_EQ || Shift->hasOneUse()) { 1034 if (Cmp->getPredicate() == ICmpInst::ICMP_EQ) 1035 X = Builder.CreateNot(X); 1036 Value *Lshr = Builder.CreateLShr(X, ShAmt); 1037 Value *And1 = 1038 Builder.CreateAnd(Lshr, ConstantInt::get(X->getType(), 1)); 1039 return replaceInstUsesWith( 1040 Zext, Builder.CreateZExtOrTrunc(And1, Zext.getType())); 1041 } 1042 } 1043 } 1044 1045 return nullptr; 1046 } 1047 1048 /// Determine if the specified value can be computed in the specified wider type 1049 /// and produce the same low bits. If not, return false. 1050 /// 1051 /// If this function returns true, it can also return a non-zero number of bits 1052 /// (in BitsToClear) which indicates that the value it computes is correct for 1053 /// the zero extend, but that the additional BitsToClear bits need to be zero'd 1054 /// out. For example, to promote something like: 1055 /// 1056 /// %B = trunc i64 %A to i32 1057 /// %C = lshr i32 %B, 8 1058 /// %E = zext i32 %C to i64 1059 /// 1060 /// CanEvaluateZExtd for the 'lshr' will return true, and BitsToClear will be 1061 /// set to 8 to indicate that the promoted value needs to have bits 24-31 1062 /// cleared in addition to bits 32-63. Since an 'and' will be generated to 1063 /// clear the top bits anyway, doing this has no extra cost. 1064 /// 1065 /// This function works on both vectors and scalars. 1066 static bool canEvaluateZExtd(Value *V, Type *Ty, unsigned &BitsToClear, 1067 InstCombinerImpl &IC, Instruction *CxtI) { 1068 BitsToClear = 0; 1069 if (canAlwaysEvaluateInType(V, Ty)) 1070 return true; 1071 if (canNotEvaluateInType(V, Ty)) 1072 return false; 1073 1074 auto *I = cast<Instruction>(V); 1075 unsigned Tmp; 1076 switch (I->getOpcode()) { 1077 case Instruction::ZExt: // zext(zext(x)) -> zext(x). 1078 case Instruction::SExt: // zext(sext(x)) -> sext(x). 1079 case Instruction::Trunc: // zext(trunc(x)) -> trunc(x) or zext(x) 1080 return true; 1081 case Instruction::And: 1082 case Instruction::Or: 1083 case Instruction::Xor: 1084 case Instruction::Add: 1085 case Instruction::Sub: 1086 case Instruction::Mul: 1087 if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI) || 1088 !canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI)) 1089 return false; 1090 // These can all be promoted if neither operand has 'bits to clear'. 1091 if (BitsToClear == 0 && Tmp == 0) 1092 return true; 1093 1094 // If the operation is an AND/OR/XOR and the bits to clear are zero in the 1095 // other side, BitsToClear is ok. 1096 if (Tmp == 0 && I->isBitwiseLogicOp()) { 1097 // We use MaskedValueIsZero here for generality, but the case we care 1098 // about the most is constant RHS. 1099 unsigned VSize = V->getType()->getScalarSizeInBits(); 1100 if (IC.MaskedValueIsZero(I->getOperand(1), 1101 APInt::getHighBitsSet(VSize, BitsToClear), 1102 0, CxtI)) { 1103 // If this is an And instruction and all of the BitsToClear are 1104 // known to be zero we can reset BitsToClear. 1105 if (I->getOpcode() == Instruction::And) 1106 BitsToClear = 0; 1107 return true; 1108 } 1109 } 1110 1111 // Otherwise, we don't know how to analyze this BitsToClear case yet. 1112 return false; 1113 1114 case Instruction::Shl: { 1115 // We can promote shl(x, cst) if we can promote x. Since shl overwrites the 1116 // upper bits we can reduce BitsToClear by the shift amount. 1117 const APInt *Amt; 1118 if (match(I->getOperand(1), m_APInt(Amt))) { 1119 if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI)) 1120 return false; 1121 uint64_t ShiftAmt = Amt->getZExtValue(); 1122 BitsToClear = ShiftAmt < BitsToClear ? BitsToClear - ShiftAmt : 0; 1123 return true; 1124 } 1125 return false; 1126 } 1127 case Instruction::LShr: { 1128 // We can promote lshr(x, cst) if we can promote x. This requires the 1129 // ultimate 'and' to clear out the high zero bits we're clearing out though. 1130 const APInt *Amt; 1131 if (match(I->getOperand(1), m_APInt(Amt))) { 1132 if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI)) 1133 return false; 1134 BitsToClear += Amt->getZExtValue(); 1135 if (BitsToClear > V->getType()->getScalarSizeInBits()) 1136 BitsToClear = V->getType()->getScalarSizeInBits(); 1137 return true; 1138 } 1139 // Cannot promote variable LSHR. 1140 return false; 1141 } 1142 case Instruction::Select: 1143 if (!canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI) || 1144 !canEvaluateZExtd(I->getOperand(2), Ty, BitsToClear, IC, CxtI) || 1145 // TODO: If important, we could handle the case when the BitsToClear are 1146 // known zero in the disagreeing side. 1147 Tmp != BitsToClear) 1148 return false; 1149 return true; 1150 1151 case Instruction::PHI: { 1152 // We can change a phi if we can change all operands. Note that we never 1153 // get into trouble with cyclic PHIs here because we only consider 1154 // instructions with a single use. 1155 PHINode *PN = cast<PHINode>(I); 1156 if (!canEvaluateZExtd(PN->getIncomingValue(0), Ty, BitsToClear, IC, CxtI)) 1157 return false; 1158 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 1159 if (!canEvaluateZExtd(PN->getIncomingValue(i), Ty, Tmp, IC, CxtI) || 1160 // TODO: If important, we could handle the case when the BitsToClear 1161 // are known zero in the disagreeing input. 1162 Tmp != BitsToClear) 1163 return false; 1164 return true; 1165 } 1166 case Instruction::Call: 1167 // llvm.vscale() can always be executed in larger type, because the 1168 // value is automatically zero-extended. 1169 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 1170 if (II->getIntrinsicID() == Intrinsic::vscale) 1171 return true; 1172 return false; 1173 default: 1174 // TODO: Can handle more cases here. 1175 return false; 1176 } 1177 } 1178 1179 Instruction *InstCombinerImpl::visitZExt(ZExtInst &Zext) { 1180 // If this zero extend is only used by a truncate, let the truncate be 1181 // eliminated before we try to optimize this zext. 1182 if (Zext.hasOneUse() && isa<TruncInst>(Zext.user_back()) && 1183 !isa<Constant>(Zext.getOperand(0))) 1184 return nullptr; 1185 1186 // If one of the common conversion will work, do it. 1187 if (Instruction *Result = commonCastTransforms(Zext)) 1188 return Result; 1189 1190 Value *Src = Zext.getOperand(0); 1191 Type *SrcTy = Src->getType(), *DestTy = Zext.getType(); 1192 1193 // zext nneg bool x -> 0 1194 if (SrcTy->isIntOrIntVectorTy(1) && Zext.hasNonNeg()) 1195 return replaceInstUsesWith(Zext, Constant::getNullValue(Zext.getType())); 1196 1197 // Try to extend the entire expression tree to the wide destination type. 1198 unsigned BitsToClear; 1199 if (shouldChangeType(SrcTy, DestTy) && 1200 canEvaluateZExtd(Src, DestTy, BitsToClear, *this, &Zext)) { 1201 assert(BitsToClear <= SrcTy->getScalarSizeInBits() && 1202 "Can't clear more bits than in SrcTy"); 1203 1204 // Okay, we can transform this! Insert the new expression now. 1205 LLVM_DEBUG( 1206 dbgs() << "ICE: EvaluateInDifferentType converting expression type" 1207 " to avoid zero extend: " 1208 << Zext << '\n'); 1209 Value *Res = EvaluateInDifferentType(Src, DestTy, false); 1210 assert(Res->getType() == DestTy); 1211 1212 // Preserve debug values referring to Src if the zext is its last use. 1213 if (auto *SrcOp = dyn_cast<Instruction>(Src)) 1214 if (SrcOp->hasOneUse()) 1215 replaceAllDbgUsesWith(*SrcOp, *Res, Zext, DT); 1216 1217 uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits() - BitsToClear; 1218 uint32_t DestBitSize = DestTy->getScalarSizeInBits(); 1219 1220 // If the high bits are already filled with zeros, just replace this 1221 // cast with the result. 1222 if (MaskedValueIsZero(Res, 1223 APInt::getHighBitsSet(DestBitSize, 1224 DestBitSize - SrcBitsKept), 1225 0, &Zext)) 1226 return replaceInstUsesWith(Zext, Res); 1227 1228 // We need to emit an AND to clear the high bits. 1229 Constant *C = ConstantInt::get(Res->getType(), 1230 APInt::getLowBitsSet(DestBitSize, SrcBitsKept)); 1231 return BinaryOperator::CreateAnd(Res, C); 1232 } 1233 1234 // If this is a TRUNC followed by a ZEXT then we are dealing with integral 1235 // types and if the sizes are just right we can convert this into a logical 1236 // 'and' which will be much cheaper than the pair of casts. 1237 if (auto *CSrc = dyn_cast<TruncInst>(Src)) { // A->B->C cast 1238 // TODO: Subsume this into EvaluateInDifferentType. 1239 1240 // Get the sizes of the types involved. We know that the intermediate type 1241 // will be smaller than A or C, but don't know the relation between A and C. 1242 Value *A = CSrc->getOperand(0); 1243 unsigned SrcSize = A->getType()->getScalarSizeInBits(); 1244 unsigned MidSize = CSrc->getType()->getScalarSizeInBits(); 1245 unsigned DstSize = DestTy->getScalarSizeInBits(); 1246 // If we're actually extending zero bits, then if 1247 // SrcSize < DstSize: zext(a & mask) 1248 // SrcSize == DstSize: a & mask 1249 // SrcSize > DstSize: trunc(a) & mask 1250 if (SrcSize < DstSize) { 1251 APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize)); 1252 Constant *AndConst = ConstantInt::get(A->getType(), AndValue); 1253 Value *And = Builder.CreateAnd(A, AndConst, CSrc->getName() + ".mask"); 1254 return new ZExtInst(And, DestTy); 1255 } 1256 1257 if (SrcSize == DstSize) { 1258 APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize)); 1259 return BinaryOperator::CreateAnd(A, ConstantInt::get(A->getType(), 1260 AndValue)); 1261 } 1262 if (SrcSize > DstSize) { 1263 Value *Trunc = Builder.CreateTrunc(A, DestTy); 1264 APInt AndValue(APInt::getLowBitsSet(DstSize, MidSize)); 1265 return BinaryOperator::CreateAnd(Trunc, 1266 ConstantInt::get(Trunc->getType(), 1267 AndValue)); 1268 } 1269 } 1270 1271 if (auto *Cmp = dyn_cast<ICmpInst>(Src)) 1272 return transformZExtICmp(Cmp, Zext); 1273 1274 // zext(trunc(X) & C) -> (X & zext(C)). 1275 Constant *C; 1276 Value *X; 1277 if (match(Src, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Constant(C)))) && 1278 X->getType() == DestTy) 1279 return BinaryOperator::CreateAnd(X, Builder.CreateZExt(C, DestTy)); 1280 1281 // zext((trunc(X) & C) ^ C) -> ((X & zext(C)) ^ zext(C)). 1282 Value *And; 1283 if (match(Src, m_OneUse(m_Xor(m_Value(And), m_Constant(C)))) && 1284 match(And, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Specific(C)))) && 1285 X->getType() == DestTy) { 1286 Value *ZC = Builder.CreateZExt(C, DestTy); 1287 return BinaryOperator::CreateXor(Builder.CreateAnd(X, ZC), ZC); 1288 } 1289 1290 // If we are truncating, masking, and then zexting back to the original type, 1291 // that's just a mask. This is not handled by canEvaluateZextd if the 1292 // intermediate values have extra uses. This could be generalized further for 1293 // a non-constant mask operand. 1294 // zext (and (trunc X), C) --> and X, (zext C) 1295 if (match(Src, m_And(m_Trunc(m_Value(X)), m_Constant(C))) && 1296 X->getType() == DestTy) { 1297 Value *ZextC = Builder.CreateZExt(C, DestTy); 1298 return BinaryOperator::CreateAnd(X, ZextC); 1299 } 1300 1301 if (match(Src, m_VScale())) { 1302 if (Zext.getFunction() && 1303 Zext.getFunction()->hasFnAttribute(Attribute::VScaleRange)) { 1304 Attribute Attr = 1305 Zext.getFunction()->getFnAttribute(Attribute::VScaleRange); 1306 if (std::optional<unsigned> MaxVScale = Attr.getVScaleRangeMax()) { 1307 unsigned TypeWidth = Src->getType()->getScalarSizeInBits(); 1308 if (Log2_32(*MaxVScale) < TypeWidth) { 1309 Value *VScale = Builder.CreateVScale(ConstantInt::get(DestTy, 1)); 1310 return replaceInstUsesWith(Zext, VScale); 1311 } 1312 } 1313 } 1314 } 1315 1316 if (!Zext.hasNonNeg()) { 1317 // If this zero extend is only used by a shift, add nneg flag. 1318 if (Zext.hasOneUse() && 1319 SrcTy->getScalarSizeInBits() > 1320 Log2_64_Ceil(DestTy->getScalarSizeInBits()) && 1321 match(Zext.user_back(), m_Shift(m_Value(), m_Specific(&Zext)))) { 1322 Zext.setNonNeg(); 1323 return &Zext; 1324 } 1325 1326 if (isKnownNonNegative(Src, SQ.getWithInstruction(&Zext))) { 1327 Zext.setNonNeg(); 1328 return &Zext; 1329 } 1330 } 1331 1332 return nullptr; 1333 } 1334 1335 /// Transform (sext icmp) to bitwise / integer operations to eliminate the icmp. 1336 Instruction *InstCombinerImpl::transformSExtICmp(ICmpInst *Cmp, 1337 SExtInst &Sext) { 1338 Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1); 1339 ICmpInst::Predicate Pred = Cmp->getPredicate(); 1340 1341 // Don't bother if Op1 isn't of vector or integer type. 1342 if (!Op1->getType()->isIntOrIntVectorTy()) 1343 return nullptr; 1344 1345 if (Pred == ICmpInst::ICMP_SLT && match(Op1, m_ZeroInt())) { 1346 // sext (x <s 0) --> ashr x, 31 (all ones if negative) 1347 Value *Sh = ConstantInt::get(Op0->getType(), 1348 Op0->getType()->getScalarSizeInBits() - 1); 1349 Value *In = Builder.CreateAShr(Op0, Sh, Op0->getName() + ".lobit"); 1350 if (In->getType() != Sext.getType()) 1351 In = Builder.CreateIntCast(In, Sext.getType(), true /*SExt*/); 1352 1353 return replaceInstUsesWith(Sext, In); 1354 } 1355 1356 if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 1357 // If we know that only one bit of the LHS of the icmp can be set and we 1358 // have an equality comparison with zero or a power of 2, we can transform 1359 // the icmp and sext into bitwise/integer operations. 1360 if (Cmp->hasOneUse() && 1361 Cmp->isEquality() && (Op1C->isZero() || Op1C->getValue().isPowerOf2())){ 1362 KnownBits Known = computeKnownBits(Op0, 0, &Sext); 1363 1364 APInt KnownZeroMask(~Known.Zero); 1365 if (KnownZeroMask.isPowerOf2()) { 1366 Value *In = Cmp->getOperand(0); 1367 1368 // If the icmp tests for a known zero bit we can constant fold it. 1369 if (!Op1C->isZero() && Op1C->getValue() != KnownZeroMask) { 1370 Value *V = Pred == ICmpInst::ICMP_NE ? 1371 ConstantInt::getAllOnesValue(Sext.getType()) : 1372 ConstantInt::getNullValue(Sext.getType()); 1373 return replaceInstUsesWith(Sext, V); 1374 } 1375 1376 if (!Op1C->isZero() == (Pred == ICmpInst::ICMP_NE)) { 1377 // sext ((x & 2^n) == 0) -> (x >> n) - 1 1378 // sext ((x & 2^n) != 2^n) -> (x >> n) - 1 1379 unsigned ShiftAmt = KnownZeroMask.countr_zero(); 1380 // Perform a right shift to place the desired bit in the LSB. 1381 if (ShiftAmt) 1382 In = Builder.CreateLShr(In, 1383 ConstantInt::get(In->getType(), ShiftAmt)); 1384 1385 // At this point "In" is either 1 or 0. Subtract 1 to turn 1386 // {1, 0} -> {0, -1}. 1387 In = Builder.CreateAdd(In, 1388 ConstantInt::getAllOnesValue(In->getType()), 1389 "sext"); 1390 } else { 1391 // sext ((x & 2^n) != 0) -> (x << bitwidth-n) a>> bitwidth-1 1392 // sext ((x & 2^n) == 2^n) -> (x << bitwidth-n) a>> bitwidth-1 1393 unsigned ShiftAmt = KnownZeroMask.countl_zero(); 1394 // Perform a left shift to place the desired bit in the MSB. 1395 if (ShiftAmt) 1396 In = Builder.CreateShl(In, 1397 ConstantInt::get(In->getType(), ShiftAmt)); 1398 1399 // Distribute the bit over the whole bit width. 1400 In = Builder.CreateAShr(In, ConstantInt::get(In->getType(), 1401 KnownZeroMask.getBitWidth() - 1), "sext"); 1402 } 1403 1404 if (Sext.getType() == In->getType()) 1405 return replaceInstUsesWith(Sext, In); 1406 return CastInst::CreateIntegerCast(In, Sext.getType(), true/*SExt*/); 1407 } 1408 } 1409 } 1410 1411 return nullptr; 1412 } 1413 1414 /// Return true if we can take the specified value and return it as type Ty 1415 /// without inserting any new casts and without changing the value of the common 1416 /// low bits. This is used by code that tries to promote integer operations to 1417 /// a wider types will allow us to eliminate the extension. 1418 /// 1419 /// This function works on both vectors and scalars. 1420 /// 1421 static bool canEvaluateSExtd(Value *V, Type *Ty) { 1422 assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() && 1423 "Can't sign extend type to a smaller type"); 1424 if (canAlwaysEvaluateInType(V, Ty)) 1425 return true; 1426 if (canNotEvaluateInType(V, Ty)) 1427 return false; 1428 1429 auto *I = cast<Instruction>(V); 1430 switch (I->getOpcode()) { 1431 case Instruction::SExt: // sext(sext(x)) -> sext(x) 1432 case Instruction::ZExt: // sext(zext(x)) -> zext(x) 1433 case Instruction::Trunc: // sext(trunc(x)) -> trunc(x) or sext(x) 1434 return true; 1435 case Instruction::And: 1436 case Instruction::Or: 1437 case Instruction::Xor: 1438 case Instruction::Add: 1439 case Instruction::Sub: 1440 case Instruction::Mul: 1441 // These operators can all arbitrarily be extended if their inputs can. 1442 return canEvaluateSExtd(I->getOperand(0), Ty) && 1443 canEvaluateSExtd(I->getOperand(1), Ty); 1444 1445 //case Instruction::Shl: TODO 1446 //case Instruction::LShr: TODO 1447 1448 case Instruction::Select: 1449 return canEvaluateSExtd(I->getOperand(1), Ty) && 1450 canEvaluateSExtd(I->getOperand(2), Ty); 1451 1452 case Instruction::PHI: { 1453 // We can change a phi if we can change all operands. Note that we never 1454 // get into trouble with cyclic PHIs here because we only consider 1455 // instructions with a single use. 1456 PHINode *PN = cast<PHINode>(I); 1457 for (Value *IncValue : PN->incoming_values()) 1458 if (!canEvaluateSExtd(IncValue, Ty)) return false; 1459 return true; 1460 } 1461 default: 1462 // TODO: Can handle more cases here. 1463 break; 1464 } 1465 1466 return false; 1467 } 1468 1469 Instruction *InstCombinerImpl::visitSExt(SExtInst &Sext) { 1470 // If this sign extend is only used by a truncate, let the truncate be 1471 // eliminated before we try to optimize this sext. 1472 if (Sext.hasOneUse() && isa<TruncInst>(Sext.user_back())) 1473 return nullptr; 1474 1475 if (Instruction *I = commonCastTransforms(Sext)) 1476 return I; 1477 1478 Value *Src = Sext.getOperand(0); 1479 Type *SrcTy = Src->getType(), *DestTy = Sext.getType(); 1480 unsigned SrcBitSize = SrcTy->getScalarSizeInBits(); 1481 unsigned DestBitSize = DestTy->getScalarSizeInBits(); 1482 1483 // If the value being extended is zero or positive, use a zext instead. 1484 if (isKnownNonNegative(Src, SQ.getWithInstruction(&Sext))) { 1485 auto CI = CastInst::Create(Instruction::ZExt, Src, DestTy); 1486 CI->setNonNeg(true); 1487 return CI; 1488 } 1489 1490 // Try to extend the entire expression tree to the wide destination type. 1491 if (shouldChangeType(SrcTy, DestTy) && canEvaluateSExtd(Src, DestTy)) { 1492 // Okay, we can transform this! Insert the new expression now. 1493 LLVM_DEBUG( 1494 dbgs() << "ICE: EvaluateInDifferentType converting expression type" 1495 " to avoid sign extend: " 1496 << Sext << '\n'); 1497 Value *Res = EvaluateInDifferentType(Src, DestTy, true); 1498 assert(Res->getType() == DestTy); 1499 1500 // If the high bits are already filled with sign bit, just replace this 1501 // cast with the result. 1502 if (ComputeNumSignBits(Res, 0, &Sext) > DestBitSize - SrcBitSize) 1503 return replaceInstUsesWith(Sext, Res); 1504 1505 // We need to emit a shl + ashr to do the sign extend. 1506 Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize); 1507 return BinaryOperator::CreateAShr(Builder.CreateShl(Res, ShAmt, "sext"), 1508 ShAmt); 1509 } 1510 1511 Value *X; 1512 if (match(Src, m_Trunc(m_Value(X)))) { 1513 // If the input has more sign bits than bits truncated, then convert 1514 // directly to final type. 1515 unsigned XBitSize = X->getType()->getScalarSizeInBits(); 1516 if (ComputeNumSignBits(X, 0, &Sext) > XBitSize - SrcBitSize) 1517 return CastInst::CreateIntegerCast(X, DestTy, /* isSigned */ true); 1518 1519 // If input is a trunc from the destination type, then convert into shifts. 1520 if (Src->hasOneUse() && X->getType() == DestTy) { 1521 // sext (trunc X) --> ashr (shl X, C), C 1522 Constant *ShAmt = ConstantInt::get(DestTy, DestBitSize - SrcBitSize); 1523 return BinaryOperator::CreateAShr(Builder.CreateShl(X, ShAmt), ShAmt); 1524 } 1525 1526 // If we are replacing shifted-in high zero bits with sign bits, convert 1527 // the logic shift to arithmetic shift and eliminate the cast to 1528 // intermediate type: 1529 // sext (trunc (lshr Y, C)) --> sext/trunc (ashr Y, C) 1530 Value *Y; 1531 if (Src->hasOneUse() && 1532 match(X, m_LShr(m_Value(Y), 1533 m_SpecificIntAllowPoison(XBitSize - SrcBitSize)))) { 1534 Value *Ashr = Builder.CreateAShr(Y, XBitSize - SrcBitSize); 1535 return CastInst::CreateIntegerCast(Ashr, DestTy, /* isSigned */ true); 1536 } 1537 } 1538 1539 if (auto *Cmp = dyn_cast<ICmpInst>(Src)) 1540 return transformSExtICmp(Cmp, Sext); 1541 1542 // If the input is a shl/ashr pair of a same constant, then this is a sign 1543 // extension from a smaller value. If we could trust arbitrary bitwidth 1544 // integers, we could turn this into a truncate to the smaller bit and then 1545 // use a sext for the whole extension. Since we don't, look deeper and check 1546 // for a truncate. If the source and dest are the same type, eliminate the 1547 // trunc and extend and just do shifts. For example, turn: 1548 // %a = trunc i32 %i to i8 1549 // %b = shl i8 %a, C 1550 // %c = ashr i8 %b, C 1551 // %d = sext i8 %c to i32 1552 // into: 1553 // %a = shl i32 %i, 32-(8-C) 1554 // %d = ashr i32 %a, 32-(8-C) 1555 Value *A = nullptr; 1556 // TODO: Eventually this could be subsumed by EvaluateInDifferentType. 1557 Constant *BA = nullptr, *CA = nullptr; 1558 if (match(Src, m_AShr(m_Shl(m_Trunc(m_Value(A)), m_Constant(BA)), 1559 m_ImmConstant(CA))) && 1560 BA->isElementWiseEqual(CA) && A->getType() == DestTy) { 1561 Constant *WideCurrShAmt = 1562 ConstantFoldCastOperand(Instruction::SExt, CA, DestTy, DL); 1563 assert(WideCurrShAmt && "Constant folding of ImmConstant cannot fail"); 1564 Constant *NumLowbitsLeft = ConstantExpr::getSub( 1565 ConstantInt::get(DestTy, SrcTy->getScalarSizeInBits()), WideCurrShAmt); 1566 Constant *NewShAmt = ConstantExpr::getSub( 1567 ConstantInt::get(DestTy, DestTy->getScalarSizeInBits()), 1568 NumLowbitsLeft); 1569 NewShAmt = 1570 Constant::mergeUndefsWith(Constant::mergeUndefsWith(NewShAmt, BA), CA); 1571 A = Builder.CreateShl(A, NewShAmt, Sext.getName()); 1572 return BinaryOperator::CreateAShr(A, NewShAmt); 1573 } 1574 1575 // Splatting a bit of constant-index across a value: 1576 // sext (ashr (trunc iN X to iM), M-1) to iN --> ashr (shl X, N-M), N-1 1577 // If the dest type is different, use a cast (adjust use check). 1578 if (match(Src, m_OneUse(m_AShr(m_Trunc(m_Value(X)), 1579 m_SpecificInt(SrcBitSize - 1))))) { 1580 Type *XTy = X->getType(); 1581 unsigned XBitSize = XTy->getScalarSizeInBits(); 1582 Constant *ShlAmtC = ConstantInt::get(XTy, XBitSize - SrcBitSize); 1583 Constant *AshrAmtC = ConstantInt::get(XTy, XBitSize - 1); 1584 if (XTy == DestTy) 1585 return BinaryOperator::CreateAShr(Builder.CreateShl(X, ShlAmtC), 1586 AshrAmtC); 1587 if (cast<BinaryOperator>(Src)->getOperand(0)->hasOneUse()) { 1588 Value *Ashr = Builder.CreateAShr(Builder.CreateShl(X, ShlAmtC), AshrAmtC); 1589 return CastInst::CreateIntegerCast(Ashr, DestTy, /* isSigned */ true); 1590 } 1591 } 1592 1593 if (match(Src, m_VScale())) { 1594 if (Sext.getFunction() && 1595 Sext.getFunction()->hasFnAttribute(Attribute::VScaleRange)) { 1596 Attribute Attr = 1597 Sext.getFunction()->getFnAttribute(Attribute::VScaleRange); 1598 if (std::optional<unsigned> MaxVScale = Attr.getVScaleRangeMax()) { 1599 if (Log2_32(*MaxVScale) < (SrcBitSize - 1)) { 1600 Value *VScale = Builder.CreateVScale(ConstantInt::get(DestTy, 1)); 1601 return replaceInstUsesWith(Sext, VScale); 1602 } 1603 } 1604 } 1605 } 1606 1607 return nullptr; 1608 } 1609 1610 /// Return a Constant* for the specified floating-point constant if it fits 1611 /// in the specified FP type without changing its value. 1612 static bool fitsInFPType(ConstantFP *CFP, const fltSemantics &Sem) { 1613 bool losesInfo; 1614 APFloat F = CFP->getValueAPF(); 1615 (void)F.convert(Sem, APFloat::rmNearestTiesToEven, &losesInfo); 1616 return !losesInfo; 1617 } 1618 1619 static Type *shrinkFPConstant(ConstantFP *CFP, bool PreferBFloat) { 1620 if (CFP->getType() == Type::getPPC_FP128Ty(CFP->getContext())) 1621 return nullptr; // No constant folding of this. 1622 // See if the value can be truncated to bfloat and then reextended. 1623 if (PreferBFloat && fitsInFPType(CFP, APFloat::BFloat())) 1624 return Type::getBFloatTy(CFP->getContext()); 1625 // See if the value can be truncated to half and then reextended. 1626 if (!PreferBFloat && fitsInFPType(CFP, APFloat::IEEEhalf())) 1627 return Type::getHalfTy(CFP->getContext()); 1628 // See if the value can be truncated to float and then reextended. 1629 if (fitsInFPType(CFP, APFloat::IEEEsingle())) 1630 return Type::getFloatTy(CFP->getContext()); 1631 if (CFP->getType()->isDoubleTy()) 1632 return nullptr; // Won't shrink. 1633 if (fitsInFPType(CFP, APFloat::IEEEdouble())) 1634 return Type::getDoubleTy(CFP->getContext()); 1635 // Don't try to shrink to various long double types. 1636 return nullptr; 1637 } 1638 1639 // Determine if this is a vector of ConstantFPs and if so, return the minimal 1640 // type we can safely truncate all elements to. 1641 static Type *shrinkFPConstantVector(Value *V, bool PreferBFloat) { 1642 auto *CV = dyn_cast<Constant>(V); 1643 auto *CVVTy = dyn_cast<FixedVectorType>(V->getType()); 1644 if (!CV || !CVVTy) 1645 return nullptr; 1646 1647 Type *MinType = nullptr; 1648 1649 unsigned NumElts = CVVTy->getNumElements(); 1650 1651 // For fixed-width vectors we find the minimal type by looking 1652 // through the constant values of the vector. 1653 for (unsigned i = 0; i != NumElts; ++i) { 1654 if (isa<UndefValue>(CV->getAggregateElement(i))) 1655 continue; 1656 1657 auto *CFP = dyn_cast_or_null<ConstantFP>(CV->getAggregateElement(i)); 1658 if (!CFP) 1659 return nullptr; 1660 1661 Type *T = shrinkFPConstant(CFP, PreferBFloat); 1662 if (!T) 1663 return nullptr; 1664 1665 // If we haven't found a type yet or this type has a larger mantissa than 1666 // our previous type, this is our new minimal type. 1667 if (!MinType || T->getFPMantissaWidth() > MinType->getFPMantissaWidth()) 1668 MinType = T; 1669 } 1670 1671 // Make a vector type from the minimal type. 1672 return MinType ? FixedVectorType::get(MinType, NumElts) : nullptr; 1673 } 1674 1675 /// Find the minimum FP type we can safely truncate to. 1676 static Type *getMinimumFPType(Value *V, bool PreferBFloat) { 1677 if (auto *FPExt = dyn_cast<FPExtInst>(V)) 1678 return FPExt->getOperand(0)->getType(); 1679 1680 // If this value is a constant, return the constant in the smallest FP type 1681 // that can accurately represent it. This allows us to turn 1682 // (float)((double)X+2.0) into x+2.0f. 1683 if (auto *CFP = dyn_cast<ConstantFP>(V)) 1684 if (Type *T = shrinkFPConstant(CFP, PreferBFloat)) 1685 return T; 1686 1687 // We can only correctly find a minimum type for a scalable vector when it is 1688 // a splat. For splats of constant values the fpext is wrapped up as a 1689 // ConstantExpr. 1690 if (auto *FPCExt = dyn_cast<ConstantExpr>(V)) 1691 if (FPCExt->getOpcode() == Instruction::FPExt) 1692 return FPCExt->getOperand(0)->getType(); 1693 1694 // Try to shrink a vector of FP constants. This returns nullptr on scalable 1695 // vectors 1696 if (Type *T = shrinkFPConstantVector(V, PreferBFloat)) 1697 return T; 1698 1699 return V->getType(); 1700 } 1701 1702 /// Return true if the cast from integer to FP can be proven to be exact for all 1703 /// possible inputs (the conversion does not lose any precision). 1704 static bool isKnownExactCastIntToFP(CastInst &I, InstCombinerImpl &IC) { 1705 CastInst::CastOps Opcode = I.getOpcode(); 1706 assert((Opcode == CastInst::SIToFP || Opcode == CastInst::UIToFP) && 1707 "Unexpected cast"); 1708 Value *Src = I.getOperand(0); 1709 Type *SrcTy = Src->getType(); 1710 Type *FPTy = I.getType(); 1711 bool IsSigned = Opcode == Instruction::SIToFP; 1712 int SrcSize = (int)SrcTy->getScalarSizeInBits() - IsSigned; 1713 1714 // Easy case - if the source integer type has less bits than the FP mantissa, 1715 // then the cast must be exact. 1716 int DestNumSigBits = FPTy->getFPMantissaWidth(); 1717 if (SrcSize <= DestNumSigBits) 1718 return true; 1719 1720 // Cast from FP to integer and back to FP is independent of the intermediate 1721 // integer width because of poison on overflow. 1722 Value *F; 1723 if (match(Src, m_FPToSI(m_Value(F))) || match(Src, m_FPToUI(m_Value(F)))) { 1724 // If this is uitofp (fptosi F), the source needs an extra bit to avoid 1725 // potential rounding of negative FP input values. 1726 int SrcNumSigBits = F->getType()->getFPMantissaWidth(); 1727 if (!IsSigned && match(Src, m_FPToSI(m_Value()))) 1728 SrcNumSigBits++; 1729 1730 // [su]itofp (fpto[su]i F) --> exact if the source type has less or equal 1731 // significant bits than the destination (and make sure neither type is 1732 // weird -- ppc_fp128). 1733 if (SrcNumSigBits > 0 && DestNumSigBits > 0 && 1734 SrcNumSigBits <= DestNumSigBits) 1735 return true; 1736 } 1737 1738 // TODO: 1739 // Try harder to find if the source integer type has less significant bits. 1740 // For example, compute number of sign bits. 1741 KnownBits SrcKnown = IC.computeKnownBits(Src, 0, &I); 1742 int SigBits = (int)SrcTy->getScalarSizeInBits() - 1743 SrcKnown.countMinLeadingZeros() - 1744 SrcKnown.countMinTrailingZeros(); 1745 if (SigBits <= DestNumSigBits) 1746 return true; 1747 1748 return false; 1749 } 1750 1751 Instruction *InstCombinerImpl::visitFPTrunc(FPTruncInst &FPT) { 1752 if (Instruction *I = commonCastTransforms(FPT)) 1753 return I; 1754 1755 // If we have fptrunc(OpI (fpextend x), (fpextend y)), we would like to 1756 // simplify this expression to avoid one or more of the trunc/extend 1757 // operations if we can do so without changing the numerical results. 1758 // 1759 // The exact manner in which the widths of the operands interact to limit 1760 // what we can and cannot do safely varies from operation to operation, and 1761 // is explained below in the various case statements. 1762 Type *Ty = FPT.getType(); 1763 auto *BO = dyn_cast<BinaryOperator>(FPT.getOperand(0)); 1764 if (BO && BO->hasOneUse()) { 1765 Type *LHSMinType = 1766 getMinimumFPType(BO->getOperand(0), /*PreferBFloat=*/Ty->isBFloatTy()); 1767 Type *RHSMinType = 1768 getMinimumFPType(BO->getOperand(1), /*PreferBFloat=*/Ty->isBFloatTy()); 1769 unsigned OpWidth = BO->getType()->getFPMantissaWidth(); 1770 unsigned LHSWidth = LHSMinType->getFPMantissaWidth(); 1771 unsigned RHSWidth = RHSMinType->getFPMantissaWidth(); 1772 unsigned SrcWidth = std::max(LHSWidth, RHSWidth); 1773 unsigned DstWidth = Ty->getFPMantissaWidth(); 1774 switch (BO->getOpcode()) { 1775 default: break; 1776 case Instruction::FAdd: 1777 case Instruction::FSub: 1778 // For addition and subtraction, the infinitely precise result can 1779 // essentially be arbitrarily wide; proving that double rounding 1780 // will not occur because the result of OpI is exact (as we will for 1781 // FMul, for example) is hopeless. However, we *can* nonetheless 1782 // frequently know that double rounding cannot occur (or that it is 1783 // innocuous) by taking advantage of the specific structure of 1784 // infinitely-precise results that admit double rounding. 1785 // 1786 // Specifically, if OpWidth >= 2*DstWdith+1 and DstWidth is sufficient 1787 // to represent both sources, we can guarantee that the double 1788 // rounding is innocuous (See p50 of Figueroa's 2000 PhD thesis, 1789 // "A Rigorous Framework for Fully Supporting the IEEE Standard ..." 1790 // for proof of this fact). 1791 // 1792 // Note: Figueroa does not consider the case where DstFormat != 1793 // SrcFormat. It's possible (likely even!) that this analysis 1794 // could be tightened for those cases, but they are rare (the main 1795 // case of interest here is (float)((double)float + float)). 1796 if (OpWidth >= 2*DstWidth+1 && DstWidth >= SrcWidth) { 1797 Value *LHS = Builder.CreateFPTrunc(BO->getOperand(0), Ty); 1798 Value *RHS = Builder.CreateFPTrunc(BO->getOperand(1), Ty); 1799 Instruction *RI = BinaryOperator::Create(BO->getOpcode(), LHS, RHS); 1800 RI->copyFastMathFlags(BO); 1801 return RI; 1802 } 1803 break; 1804 case Instruction::FMul: 1805 // For multiplication, the infinitely precise result has at most 1806 // LHSWidth + RHSWidth significant bits; if OpWidth is sufficient 1807 // that such a value can be exactly represented, then no double 1808 // rounding can possibly occur; we can safely perform the operation 1809 // in the destination format if it can represent both sources. 1810 if (OpWidth >= LHSWidth + RHSWidth && DstWidth >= SrcWidth) { 1811 Value *LHS = Builder.CreateFPTrunc(BO->getOperand(0), Ty); 1812 Value *RHS = Builder.CreateFPTrunc(BO->getOperand(1), Ty); 1813 return BinaryOperator::CreateFMulFMF(LHS, RHS, BO); 1814 } 1815 break; 1816 case Instruction::FDiv: 1817 // For division, we use again use the bound from Figueroa's 1818 // dissertation. I am entirely certain that this bound can be 1819 // tightened in the unbalanced operand case by an analysis based on 1820 // the diophantine rational approximation bound, but the well-known 1821 // condition used here is a good conservative first pass. 1822 // TODO: Tighten bound via rigorous analysis of the unbalanced case. 1823 if (OpWidth >= 2*DstWidth && DstWidth >= SrcWidth) { 1824 Value *LHS = Builder.CreateFPTrunc(BO->getOperand(0), Ty); 1825 Value *RHS = Builder.CreateFPTrunc(BO->getOperand(1), Ty); 1826 return BinaryOperator::CreateFDivFMF(LHS, RHS, BO); 1827 } 1828 break; 1829 case Instruction::FRem: { 1830 // Remainder is straightforward. Remainder is always exact, so the 1831 // type of OpI doesn't enter into things at all. We simply evaluate 1832 // in whichever source type is larger, then convert to the 1833 // destination type. 1834 if (SrcWidth == OpWidth) 1835 break; 1836 Value *LHS, *RHS; 1837 if (LHSWidth == SrcWidth) { 1838 LHS = Builder.CreateFPTrunc(BO->getOperand(0), LHSMinType); 1839 RHS = Builder.CreateFPTrunc(BO->getOperand(1), LHSMinType); 1840 } else { 1841 LHS = Builder.CreateFPTrunc(BO->getOperand(0), RHSMinType); 1842 RHS = Builder.CreateFPTrunc(BO->getOperand(1), RHSMinType); 1843 } 1844 1845 Value *ExactResult = Builder.CreateFRemFMF(LHS, RHS, BO); 1846 return CastInst::CreateFPCast(ExactResult, Ty); 1847 } 1848 } 1849 } 1850 1851 // (fptrunc (fneg x)) -> (fneg (fptrunc x)) 1852 Value *X; 1853 Instruction *Op = dyn_cast<Instruction>(FPT.getOperand(0)); 1854 if (Op && Op->hasOneUse()) { 1855 FastMathFlags FMF = FPT.getFastMathFlags(); 1856 if (auto *FPMO = dyn_cast<FPMathOperator>(Op)) 1857 FMF &= FPMO->getFastMathFlags(); 1858 1859 if (match(Op, m_FNeg(m_Value(X)))) { 1860 Value *InnerTrunc = Builder.CreateFPTruncFMF(X, Ty, FMF); 1861 Value *Neg = Builder.CreateFNegFMF(InnerTrunc, FMF); 1862 return replaceInstUsesWith(FPT, Neg); 1863 } 1864 1865 // If we are truncating a select that has an extended operand, we can 1866 // narrow the other operand and do the select as a narrow op. 1867 Value *Cond, *X, *Y; 1868 if (match(Op, m_Select(m_Value(Cond), m_FPExt(m_Value(X)), m_Value(Y))) && 1869 X->getType() == Ty) { 1870 // fptrunc (select Cond, (fpext X), Y --> select Cond, X, (fptrunc Y) 1871 Value *NarrowY = Builder.CreateFPTruncFMF(Y, Ty, FMF); 1872 Value *Sel = 1873 Builder.CreateSelectFMF(Cond, X, NarrowY, FMF, "narrow.sel", Op); 1874 return replaceInstUsesWith(FPT, Sel); 1875 } 1876 if (match(Op, m_Select(m_Value(Cond), m_Value(Y), m_FPExt(m_Value(X)))) && 1877 X->getType() == Ty) { 1878 // fptrunc (select Cond, Y, (fpext X) --> select Cond, (fptrunc Y), X 1879 Value *NarrowY = Builder.CreateFPTruncFMF(Y, Ty, FMF); 1880 Value *Sel = 1881 Builder.CreateSelectFMF(Cond, NarrowY, X, FMF, "narrow.sel", Op); 1882 return replaceInstUsesWith(FPT, Sel); 1883 } 1884 } 1885 1886 if (auto *II = dyn_cast<IntrinsicInst>(FPT.getOperand(0))) { 1887 switch (II->getIntrinsicID()) { 1888 default: break; 1889 case Intrinsic::ceil: 1890 case Intrinsic::fabs: 1891 case Intrinsic::floor: 1892 case Intrinsic::nearbyint: 1893 case Intrinsic::rint: 1894 case Intrinsic::round: 1895 case Intrinsic::roundeven: 1896 case Intrinsic::trunc: { 1897 Value *Src = II->getArgOperand(0); 1898 if (!Src->hasOneUse()) 1899 break; 1900 1901 // Except for fabs, this transformation requires the input of the unary FP 1902 // operation to be itself an fpext from the type to which we're 1903 // truncating. 1904 if (II->getIntrinsicID() != Intrinsic::fabs) { 1905 FPExtInst *FPExtSrc = dyn_cast<FPExtInst>(Src); 1906 if (!FPExtSrc || FPExtSrc->getSrcTy() != Ty) 1907 break; 1908 } 1909 1910 // Do unary FP operation on smaller type. 1911 // (fptrunc (fabs x)) -> (fabs (fptrunc x)) 1912 Value *InnerTrunc = Builder.CreateFPTrunc(Src, Ty); 1913 Function *Overload = Intrinsic::getOrInsertDeclaration( 1914 FPT.getModule(), II->getIntrinsicID(), Ty); 1915 SmallVector<OperandBundleDef, 1> OpBundles; 1916 II->getOperandBundlesAsDefs(OpBundles); 1917 CallInst *NewCI = 1918 CallInst::Create(Overload, {InnerTrunc}, OpBundles, II->getName()); 1919 NewCI->copyFastMathFlags(II); 1920 return NewCI; 1921 } 1922 } 1923 } 1924 1925 if (Instruction *I = shrinkInsertElt(FPT, Builder)) 1926 return I; 1927 1928 Value *Src = FPT.getOperand(0); 1929 if (isa<SIToFPInst>(Src) || isa<UIToFPInst>(Src)) { 1930 auto *FPCast = cast<CastInst>(Src); 1931 if (isKnownExactCastIntToFP(*FPCast, *this)) 1932 return CastInst::Create(FPCast->getOpcode(), FPCast->getOperand(0), Ty); 1933 } 1934 1935 return nullptr; 1936 } 1937 1938 Instruction *InstCombinerImpl::visitFPExt(CastInst &FPExt) { 1939 // If the source operand is a cast from integer to FP and known exact, then 1940 // cast the integer operand directly to the destination type. 1941 Type *Ty = FPExt.getType(); 1942 Value *Src = FPExt.getOperand(0); 1943 if (isa<SIToFPInst>(Src) || isa<UIToFPInst>(Src)) { 1944 auto *FPCast = cast<CastInst>(Src); 1945 if (isKnownExactCastIntToFP(*FPCast, *this)) 1946 return CastInst::Create(FPCast->getOpcode(), FPCast->getOperand(0), Ty); 1947 } 1948 1949 return commonCastTransforms(FPExt); 1950 } 1951 1952 /// fpto{s/u}i({u/s}itofp(X)) --> X or zext(X) or sext(X) or trunc(X) 1953 /// This is safe if the intermediate type has enough bits in its mantissa to 1954 /// accurately represent all values of X. For example, this won't work with 1955 /// i64 -> float -> i64. 1956 Instruction *InstCombinerImpl::foldItoFPtoI(CastInst &FI) { 1957 if (!isa<UIToFPInst>(FI.getOperand(0)) && !isa<SIToFPInst>(FI.getOperand(0))) 1958 return nullptr; 1959 1960 auto *OpI = cast<CastInst>(FI.getOperand(0)); 1961 Value *X = OpI->getOperand(0); 1962 Type *XType = X->getType(); 1963 Type *DestType = FI.getType(); 1964 bool IsOutputSigned = isa<FPToSIInst>(FI); 1965 1966 // Since we can assume the conversion won't overflow, our decision as to 1967 // whether the input will fit in the float should depend on the minimum 1968 // of the input range and output range. 1969 1970 // This means this is also safe for a signed input and unsigned output, since 1971 // a negative input would lead to undefined behavior. 1972 if (!isKnownExactCastIntToFP(*OpI, *this)) { 1973 // The first cast may not round exactly based on the source integer width 1974 // and FP width, but the overflow UB rules can still allow this to fold. 1975 // If the destination type is narrow, that means the intermediate FP value 1976 // must be large enough to hold the source value exactly. 1977 // For example, (uint8_t)((float)(uint32_t 16777217) is undefined behavior. 1978 int OutputSize = (int)DestType->getScalarSizeInBits(); 1979 if (OutputSize > OpI->getType()->getFPMantissaWidth()) 1980 return nullptr; 1981 } 1982 1983 if (DestType->getScalarSizeInBits() > XType->getScalarSizeInBits()) { 1984 bool IsInputSigned = isa<SIToFPInst>(OpI); 1985 if (IsInputSigned && IsOutputSigned) 1986 return new SExtInst(X, DestType); 1987 return new ZExtInst(X, DestType); 1988 } 1989 if (DestType->getScalarSizeInBits() < XType->getScalarSizeInBits()) 1990 return new TruncInst(X, DestType); 1991 1992 assert(XType == DestType && "Unexpected types for int to FP to int casts"); 1993 return replaceInstUsesWith(FI, X); 1994 } 1995 1996 static Instruction *foldFPtoI(Instruction &FI, InstCombiner &IC) { 1997 // fpto{u/s}i non-norm --> 0 1998 FPClassTest Mask = 1999 FI.getOpcode() == Instruction::FPToUI ? fcPosNormal : fcNormal; 2000 KnownFPClass FPClass = 2001 computeKnownFPClass(FI.getOperand(0), Mask, /*Depth=*/0, 2002 IC.getSimplifyQuery().getWithInstruction(&FI)); 2003 if (FPClass.isKnownNever(Mask)) 2004 return IC.replaceInstUsesWith(FI, ConstantInt::getNullValue(FI.getType())); 2005 2006 return nullptr; 2007 } 2008 2009 Instruction *InstCombinerImpl::visitFPToUI(FPToUIInst &FI) { 2010 if (Instruction *I = foldItoFPtoI(FI)) 2011 return I; 2012 2013 if (Instruction *I = foldFPtoI(FI, *this)) 2014 return I; 2015 2016 return commonCastTransforms(FI); 2017 } 2018 2019 Instruction *InstCombinerImpl::visitFPToSI(FPToSIInst &FI) { 2020 if (Instruction *I = foldItoFPtoI(FI)) 2021 return I; 2022 2023 if (Instruction *I = foldFPtoI(FI, *this)) 2024 return I; 2025 2026 return commonCastTransforms(FI); 2027 } 2028 2029 Instruction *InstCombinerImpl::visitUIToFP(CastInst &CI) { 2030 if (Instruction *R = commonCastTransforms(CI)) 2031 return R; 2032 if (!CI.hasNonNeg() && isKnownNonNegative(CI.getOperand(0), SQ)) { 2033 CI.setNonNeg(); 2034 return &CI; 2035 } 2036 return nullptr; 2037 } 2038 2039 Instruction *InstCombinerImpl::visitSIToFP(CastInst &CI) { 2040 if (Instruction *R = commonCastTransforms(CI)) 2041 return R; 2042 if (isKnownNonNegative(CI.getOperand(0), SQ)) { 2043 auto *UI = 2044 CastInst::Create(Instruction::UIToFP, CI.getOperand(0), CI.getType()); 2045 UI->setNonNeg(true); 2046 return UI; 2047 } 2048 return nullptr; 2049 } 2050 2051 Instruction *InstCombinerImpl::visitIntToPtr(IntToPtrInst &CI) { 2052 // If the source integer type is not the intptr_t type for this target, do a 2053 // trunc or zext to the intptr_t type, then inttoptr of it. This allows the 2054 // cast to be exposed to other transforms. 2055 unsigned AS = CI.getAddressSpace(); 2056 if (CI.getOperand(0)->getType()->getScalarSizeInBits() != 2057 DL.getPointerSizeInBits(AS)) { 2058 Type *Ty = CI.getOperand(0)->getType()->getWithNewType( 2059 DL.getIntPtrType(CI.getContext(), AS)); 2060 Value *P = Builder.CreateZExtOrTrunc(CI.getOperand(0), Ty); 2061 return new IntToPtrInst(P, CI.getType()); 2062 } 2063 2064 if (Instruction *I = commonCastTransforms(CI)) 2065 return I; 2066 2067 return nullptr; 2068 } 2069 2070 Instruction *InstCombinerImpl::visitPtrToInt(PtrToIntInst &CI) { 2071 // If the destination integer type is not the intptr_t type for this target, 2072 // do a ptrtoint to intptr_t then do a trunc or zext. This allows the cast 2073 // to be exposed to other transforms. 2074 Value *SrcOp = CI.getPointerOperand(); 2075 Type *SrcTy = SrcOp->getType(); 2076 Type *Ty = CI.getType(); 2077 unsigned AS = CI.getPointerAddressSpace(); 2078 unsigned TySize = Ty->getScalarSizeInBits(); 2079 unsigned PtrSize = DL.getPointerSizeInBits(AS); 2080 if (TySize != PtrSize) { 2081 Type *IntPtrTy = 2082 SrcTy->getWithNewType(DL.getIntPtrType(CI.getContext(), AS)); 2083 Value *P = Builder.CreatePtrToInt(SrcOp, IntPtrTy); 2084 return CastInst::CreateIntegerCast(P, Ty, /*isSigned=*/false); 2085 } 2086 2087 // (ptrtoint (ptrmask P, M)) 2088 // -> (and (ptrtoint P), M) 2089 // This is generally beneficial as `and` is better supported than `ptrmask`. 2090 Value *Ptr, *Mask; 2091 if (match(SrcOp, m_OneUse(m_Intrinsic<Intrinsic::ptrmask>(m_Value(Ptr), 2092 m_Value(Mask)))) && 2093 Mask->getType() == Ty) 2094 return BinaryOperator::CreateAnd(Builder.CreatePtrToInt(Ptr, Ty), Mask); 2095 2096 if (auto *GEP = dyn_cast<GEPOperator>(SrcOp)) { 2097 // Fold ptrtoint(gep null, x) to multiply + constant if the GEP has one use. 2098 // While this can increase the number of instructions it doesn't actually 2099 // increase the overall complexity since the arithmetic is just part of 2100 // the GEP otherwise. 2101 if (GEP->hasOneUse() && 2102 isa<ConstantPointerNull>(GEP->getPointerOperand())) { 2103 return replaceInstUsesWith(CI, 2104 Builder.CreateIntCast(EmitGEPOffset(GEP), Ty, 2105 /*isSigned=*/false)); 2106 } 2107 2108 // (ptrtoint (gep (inttoptr Base), ...)) -> Base + Offset 2109 Value *Base; 2110 if (GEP->hasOneUse() && 2111 match(GEP->getPointerOperand(), m_OneUse(m_IntToPtr(m_Value(Base)))) && 2112 Base->getType() == Ty) { 2113 Value *Offset = EmitGEPOffset(GEP); 2114 auto *NewOp = BinaryOperator::CreateAdd(Base, Offset); 2115 NewOp->setHasNoUnsignedWrap(GEP->hasNoUnsignedWrap()); 2116 return NewOp; 2117 } 2118 } 2119 2120 Value *Vec, *Scalar, *Index; 2121 if (match(SrcOp, m_OneUse(m_InsertElt(m_IntToPtr(m_Value(Vec)), 2122 m_Value(Scalar), m_Value(Index)))) && 2123 Vec->getType() == Ty) { 2124 assert(Vec->getType()->getScalarSizeInBits() == PtrSize && "Wrong type"); 2125 // Convert the scalar to int followed by insert to eliminate one cast: 2126 // p2i (ins (i2p Vec), Scalar, Index --> ins Vec, (p2i Scalar), Index 2127 Value *NewCast = Builder.CreatePtrToInt(Scalar, Ty->getScalarType()); 2128 return InsertElementInst::Create(Vec, NewCast, Index); 2129 } 2130 2131 return commonCastTransforms(CI); 2132 } 2133 2134 /// This input value (which is known to have vector type) is being zero extended 2135 /// or truncated to the specified vector type. Since the zext/trunc is done 2136 /// using an integer type, we have a (bitcast(cast(bitcast))) pattern, 2137 /// endianness will impact which end of the vector that is extended or 2138 /// truncated. 2139 /// 2140 /// A vector is always stored with index 0 at the lowest address, which 2141 /// corresponds to the most significant bits for a big endian stored integer and 2142 /// the least significant bits for little endian. A trunc/zext of an integer 2143 /// impacts the big end of the integer. Thus, we need to add/remove elements at 2144 /// the front of the vector for big endian targets, and the back of the vector 2145 /// for little endian targets. 2146 /// 2147 /// Try to replace it with a shuffle (and vector/vector bitcast) if possible. 2148 /// 2149 /// The source and destination vector types may have different element types. 2150 static Instruction * 2151 optimizeVectorResizeWithIntegerBitCasts(Value *InVal, VectorType *DestTy, 2152 InstCombinerImpl &IC) { 2153 // We can only do this optimization if the output is a multiple of the input 2154 // element size, or the input is a multiple of the output element size. 2155 // Convert the input type to have the same element type as the output. 2156 VectorType *SrcTy = cast<VectorType>(InVal->getType()); 2157 2158 if (SrcTy->getElementType() != DestTy->getElementType()) { 2159 // The input types don't need to be identical, but for now they must be the 2160 // same size. There is no specific reason we couldn't handle things like 2161 // <4 x i16> -> <4 x i32> by bitcasting to <2 x i32> but haven't gotten 2162 // there yet. 2163 if (SrcTy->getElementType()->getPrimitiveSizeInBits() != 2164 DestTy->getElementType()->getPrimitiveSizeInBits()) 2165 return nullptr; 2166 2167 SrcTy = 2168 FixedVectorType::get(DestTy->getElementType(), 2169 cast<FixedVectorType>(SrcTy)->getNumElements()); 2170 InVal = IC.Builder.CreateBitCast(InVal, SrcTy); 2171 } 2172 2173 bool IsBigEndian = IC.getDataLayout().isBigEndian(); 2174 unsigned SrcElts = cast<FixedVectorType>(SrcTy)->getNumElements(); 2175 unsigned DestElts = cast<FixedVectorType>(DestTy)->getNumElements(); 2176 2177 assert(SrcElts != DestElts && "Element counts should be different."); 2178 2179 // Now that the element types match, get the shuffle mask and RHS of the 2180 // shuffle to use, which depends on whether we're increasing or decreasing the 2181 // size of the input. 2182 auto ShuffleMaskStorage = llvm::to_vector<16>(llvm::seq<int>(0, SrcElts)); 2183 ArrayRef<int> ShuffleMask; 2184 Value *V2; 2185 2186 if (SrcElts > DestElts) { 2187 // If we're shrinking the number of elements (rewriting an integer 2188 // truncate), just shuffle in the elements corresponding to the least 2189 // significant bits from the input and use poison as the second shuffle 2190 // input. 2191 V2 = PoisonValue::get(SrcTy); 2192 // Make sure the shuffle mask selects the "least significant bits" by 2193 // keeping elements from back of the src vector for big endian, and from the 2194 // front for little endian. 2195 ShuffleMask = ShuffleMaskStorage; 2196 if (IsBigEndian) 2197 ShuffleMask = ShuffleMask.take_back(DestElts); 2198 else 2199 ShuffleMask = ShuffleMask.take_front(DestElts); 2200 } else { 2201 // If we're increasing the number of elements (rewriting an integer zext), 2202 // shuffle in all of the elements from InVal. Fill the rest of the result 2203 // elements with zeros from a constant zero. 2204 V2 = Constant::getNullValue(SrcTy); 2205 // Use first elt from V2 when indicating zero in the shuffle mask. 2206 uint32_t NullElt = SrcElts; 2207 // Extend with null values in the "most significant bits" by adding elements 2208 // in front of the src vector for big endian, and at the back for little 2209 // endian. 2210 unsigned DeltaElts = DestElts - SrcElts; 2211 if (IsBigEndian) 2212 ShuffleMaskStorage.insert(ShuffleMaskStorage.begin(), DeltaElts, NullElt); 2213 else 2214 ShuffleMaskStorage.append(DeltaElts, NullElt); 2215 ShuffleMask = ShuffleMaskStorage; 2216 } 2217 2218 return new ShuffleVectorInst(InVal, V2, ShuffleMask); 2219 } 2220 2221 static bool isMultipleOfTypeSize(unsigned Value, Type *Ty) { 2222 return Value % Ty->getPrimitiveSizeInBits() == 0; 2223 } 2224 2225 static unsigned getTypeSizeIndex(unsigned Value, Type *Ty) { 2226 return Value / Ty->getPrimitiveSizeInBits(); 2227 } 2228 2229 /// V is a value which is inserted into a vector of VecEltTy. 2230 /// Look through the value to see if we can decompose it into 2231 /// insertions into the vector. See the example in the comment for 2232 /// OptimizeIntegerToVectorInsertions for the pattern this handles. 2233 /// The type of V is always a non-zero multiple of VecEltTy's size. 2234 /// Shift is the number of bits between the lsb of V and the lsb of 2235 /// the vector. 2236 /// 2237 /// This returns false if the pattern can't be matched or true if it can, 2238 /// filling in Elements with the elements found here. 2239 static bool collectInsertionElements(Value *V, unsigned Shift, 2240 SmallVectorImpl<Value *> &Elements, 2241 Type *VecEltTy, bool isBigEndian) { 2242 assert(isMultipleOfTypeSize(Shift, VecEltTy) && 2243 "Shift should be a multiple of the element type size"); 2244 2245 // Undef values never contribute useful bits to the result. 2246 if (isa<UndefValue>(V)) return true; 2247 2248 // If we got down to a value of the right type, we win, try inserting into the 2249 // right element. 2250 if (V->getType() == VecEltTy) { 2251 // Inserting null doesn't actually insert any elements. 2252 if (Constant *C = dyn_cast<Constant>(V)) 2253 if (C->isNullValue()) 2254 return true; 2255 2256 unsigned ElementIndex = getTypeSizeIndex(Shift, VecEltTy); 2257 if (isBigEndian) 2258 ElementIndex = Elements.size() - ElementIndex - 1; 2259 2260 // Fail if multiple elements are inserted into this slot. 2261 if (Elements[ElementIndex]) 2262 return false; 2263 2264 Elements[ElementIndex] = V; 2265 return true; 2266 } 2267 2268 if (Constant *C = dyn_cast<Constant>(V)) { 2269 // Figure out the # elements this provides, and bitcast it or slice it up 2270 // as required. 2271 unsigned NumElts = getTypeSizeIndex(C->getType()->getPrimitiveSizeInBits(), 2272 VecEltTy); 2273 // If the constant is the size of a vector element, we just need to bitcast 2274 // it to the right type so it gets properly inserted. 2275 if (NumElts == 1) 2276 return collectInsertionElements(ConstantExpr::getBitCast(C, VecEltTy), 2277 Shift, Elements, VecEltTy, isBigEndian); 2278 2279 // Okay, this is a constant that covers multiple elements. Slice it up into 2280 // pieces and insert each element-sized piece into the vector. 2281 if (!isa<IntegerType>(C->getType())) 2282 C = ConstantExpr::getBitCast(C, IntegerType::get(V->getContext(), 2283 C->getType()->getPrimitiveSizeInBits())); 2284 unsigned ElementSize = VecEltTy->getPrimitiveSizeInBits(); 2285 Type *ElementIntTy = IntegerType::get(C->getContext(), ElementSize); 2286 2287 for (unsigned i = 0; i != NumElts; ++i) { 2288 unsigned ShiftI = i * ElementSize; 2289 Constant *Piece = ConstantFoldBinaryInstruction( 2290 Instruction::LShr, C, ConstantInt::get(C->getType(), ShiftI)); 2291 if (!Piece) 2292 return false; 2293 2294 Piece = ConstantExpr::getTrunc(Piece, ElementIntTy); 2295 if (!collectInsertionElements(Piece, ShiftI + Shift, Elements, VecEltTy, 2296 isBigEndian)) 2297 return false; 2298 } 2299 return true; 2300 } 2301 2302 if (!V->hasOneUse()) return false; 2303 2304 Instruction *I = dyn_cast<Instruction>(V); 2305 if (!I) return false; 2306 switch (I->getOpcode()) { 2307 default: return false; // Unhandled case. 2308 case Instruction::BitCast: 2309 if (I->getOperand(0)->getType()->isVectorTy()) 2310 return false; 2311 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy, 2312 isBigEndian); 2313 case Instruction::ZExt: 2314 if (!isMultipleOfTypeSize( 2315 I->getOperand(0)->getType()->getPrimitiveSizeInBits(), 2316 VecEltTy)) 2317 return false; 2318 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy, 2319 isBigEndian); 2320 case Instruction::Or: 2321 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy, 2322 isBigEndian) && 2323 collectInsertionElements(I->getOperand(1), Shift, Elements, VecEltTy, 2324 isBigEndian); 2325 case Instruction::Shl: { 2326 // Must be shifting by a constant that is a multiple of the element size. 2327 ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1)); 2328 if (!CI) return false; 2329 Shift += CI->getZExtValue(); 2330 if (!isMultipleOfTypeSize(Shift, VecEltTy)) return false; 2331 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy, 2332 isBigEndian); 2333 } 2334 2335 } 2336 } 2337 2338 2339 /// If the input is an 'or' instruction, we may be doing shifts and ors to 2340 /// assemble the elements of the vector manually. 2341 /// Try to rip the code out and replace it with insertelements. This is to 2342 /// optimize code like this: 2343 /// 2344 /// %tmp37 = bitcast float %inc to i32 2345 /// %tmp38 = zext i32 %tmp37 to i64 2346 /// %tmp31 = bitcast float %inc5 to i32 2347 /// %tmp32 = zext i32 %tmp31 to i64 2348 /// %tmp33 = shl i64 %tmp32, 32 2349 /// %ins35 = or i64 %tmp33, %tmp38 2350 /// %tmp43 = bitcast i64 %ins35 to <2 x float> 2351 /// 2352 /// Into two insertelements that do "buildvector{%inc, %inc5}". 2353 static Value *optimizeIntegerToVectorInsertions(BitCastInst &CI, 2354 InstCombinerImpl &IC) { 2355 auto *DestVecTy = cast<FixedVectorType>(CI.getType()); 2356 Value *IntInput = CI.getOperand(0); 2357 2358 // if the int input is just an undef value do not try to optimize to vector 2359 // insertions as it will prevent undef propagation 2360 if (isa<UndefValue>(IntInput)) 2361 return nullptr; 2362 2363 SmallVector<Value*, 8> Elements(DestVecTy->getNumElements()); 2364 if (!collectInsertionElements(IntInput, 0, Elements, 2365 DestVecTy->getElementType(), 2366 IC.getDataLayout().isBigEndian())) 2367 return nullptr; 2368 2369 // If we succeeded, we know that all of the element are specified by Elements 2370 // or are zero if Elements has a null entry. Recast this as a set of 2371 // insertions. 2372 Value *Result = Constant::getNullValue(CI.getType()); 2373 for (unsigned i = 0, e = Elements.size(); i != e; ++i) { 2374 if (!Elements[i]) continue; // Unset element. 2375 2376 Result = IC.Builder.CreateInsertElement(Result, Elements[i], 2377 IC.Builder.getInt32(i)); 2378 } 2379 2380 return Result; 2381 } 2382 2383 /// Canonicalize scalar bitcasts of extracted elements into a bitcast of the 2384 /// vector followed by extract element. The backend tends to handle bitcasts of 2385 /// vectors better than bitcasts of scalars because vector registers are 2386 /// usually not type-specific like scalar integer or scalar floating-point. 2387 static Instruction *canonicalizeBitCastExtElt(BitCastInst &BitCast, 2388 InstCombinerImpl &IC) { 2389 Value *VecOp, *Index; 2390 if (!match(BitCast.getOperand(0), 2391 m_OneUse(m_ExtractElt(m_Value(VecOp), m_Value(Index))))) 2392 return nullptr; 2393 2394 // The bitcast must be to a vectorizable type, otherwise we can't make a new 2395 // type to extract from. 2396 Type *DestType = BitCast.getType(); 2397 VectorType *VecType = cast<VectorType>(VecOp->getType()); 2398 if (VectorType::isValidElementType(DestType)) { 2399 auto *NewVecType = VectorType::get(DestType, VecType); 2400 auto *NewBC = IC.Builder.CreateBitCast(VecOp, NewVecType, "bc"); 2401 return ExtractElementInst::Create(NewBC, Index); 2402 } 2403 2404 // Only solve DestType is vector to avoid inverse transform in visitBitCast. 2405 // bitcast (extractelement <1 x elt>, dest) -> bitcast(<1 x elt>, dest) 2406 auto *FixedVType = dyn_cast<FixedVectorType>(VecType); 2407 if (DestType->isVectorTy() && FixedVType && FixedVType->getNumElements() == 1) 2408 return CastInst::Create(Instruction::BitCast, VecOp, DestType); 2409 2410 return nullptr; 2411 } 2412 2413 /// Change the type of a bitwise logic operation if we can eliminate a bitcast. 2414 static Instruction *foldBitCastBitwiseLogic(BitCastInst &BitCast, 2415 InstCombiner::BuilderTy &Builder) { 2416 Type *DestTy = BitCast.getType(); 2417 BinaryOperator *BO; 2418 2419 if (!match(BitCast.getOperand(0), m_OneUse(m_BinOp(BO))) || 2420 !BO->isBitwiseLogicOp()) 2421 return nullptr; 2422 2423 // FIXME: This transform is restricted to vector types to avoid backend 2424 // problems caused by creating potentially illegal operations. If a fix-up is 2425 // added to handle that situation, we can remove this check. 2426 if (!DestTy->isVectorTy() || !BO->getType()->isVectorTy()) 2427 return nullptr; 2428 2429 if (DestTy->isFPOrFPVectorTy()) { 2430 Value *X, *Y; 2431 // bitcast(logic(bitcast(X), bitcast(Y))) -> bitcast'(logic(bitcast'(X), Y)) 2432 if (match(BO->getOperand(0), m_OneUse(m_BitCast(m_Value(X)))) && 2433 match(BO->getOperand(1), m_OneUse(m_BitCast(m_Value(Y))))) { 2434 if (X->getType()->isFPOrFPVectorTy() && 2435 Y->getType()->isIntOrIntVectorTy()) { 2436 Value *CastedOp = 2437 Builder.CreateBitCast(BO->getOperand(0), Y->getType()); 2438 Value *NewBO = Builder.CreateBinOp(BO->getOpcode(), CastedOp, Y); 2439 return CastInst::CreateBitOrPointerCast(NewBO, DestTy); 2440 } 2441 if (X->getType()->isIntOrIntVectorTy() && 2442 Y->getType()->isFPOrFPVectorTy()) { 2443 Value *CastedOp = 2444 Builder.CreateBitCast(BO->getOperand(1), X->getType()); 2445 Value *NewBO = Builder.CreateBinOp(BO->getOpcode(), CastedOp, X); 2446 return CastInst::CreateBitOrPointerCast(NewBO, DestTy); 2447 } 2448 } 2449 return nullptr; 2450 } 2451 2452 if (!DestTy->isIntOrIntVectorTy()) 2453 return nullptr; 2454 2455 Value *X; 2456 if (match(BO->getOperand(0), m_OneUse(m_BitCast(m_Value(X)))) && 2457 X->getType() == DestTy && !isa<Constant>(X)) { 2458 // bitcast(logic(bitcast(X), Y)) --> logic'(X, bitcast(Y)) 2459 Value *CastedOp1 = Builder.CreateBitCast(BO->getOperand(1), DestTy); 2460 return BinaryOperator::Create(BO->getOpcode(), X, CastedOp1); 2461 } 2462 2463 if (match(BO->getOperand(1), m_OneUse(m_BitCast(m_Value(X)))) && 2464 X->getType() == DestTy && !isa<Constant>(X)) { 2465 // bitcast(logic(Y, bitcast(X))) --> logic'(bitcast(Y), X) 2466 Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy); 2467 return BinaryOperator::Create(BO->getOpcode(), CastedOp0, X); 2468 } 2469 2470 // Canonicalize vector bitcasts to come before vector bitwise logic with a 2471 // constant. This eases recognition of special constants for later ops. 2472 // Example: 2473 // icmp u/s (a ^ signmask), (b ^ signmask) --> icmp s/u a, b 2474 Constant *C; 2475 if (match(BO->getOperand(1), m_Constant(C))) { 2476 // bitcast (logic X, C) --> logic (bitcast X, C') 2477 Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy); 2478 Value *CastedC = Builder.CreateBitCast(C, DestTy); 2479 return BinaryOperator::Create(BO->getOpcode(), CastedOp0, CastedC); 2480 } 2481 2482 return nullptr; 2483 } 2484 2485 /// Change the type of a select if we can eliminate a bitcast. 2486 static Instruction *foldBitCastSelect(BitCastInst &BitCast, 2487 InstCombiner::BuilderTy &Builder) { 2488 Value *Cond, *TVal, *FVal; 2489 if (!match(BitCast.getOperand(0), 2490 m_OneUse(m_Select(m_Value(Cond), m_Value(TVal), m_Value(FVal))))) 2491 return nullptr; 2492 2493 // A vector select must maintain the same number of elements in its operands. 2494 Type *CondTy = Cond->getType(); 2495 Type *DestTy = BitCast.getType(); 2496 if (auto *CondVTy = dyn_cast<VectorType>(CondTy)) 2497 if (!DestTy->isVectorTy() || 2498 CondVTy->getElementCount() != 2499 cast<VectorType>(DestTy)->getElementCount()) 2500 return nullptr; 2501 2502 // FIXME: This transform is restricted from changing the select between 2503 // scalars and vectors to avoid backend problems caused by creating 2504 // potentially illegal operations. If a fix-up is added to handle that 2505 // situation, we can remove this check. 2506 if (DestTy->isVectorTy() != TVal->getType()->isVectorTy()) 2507 return nullptr; 2508 2509 auto *Sel = cast<Instruction>(BitCast.getOperand(0)); 2510 Value *X; 2511 if (match(TVal, m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy && 2512 !isa<Constant>(X)) { 2513 // bitcast(select(Cond, bitcast(X), Y)) --> select'(Cond, X, bitcast(Y)) 2514 Value *CastedVal = Builder.CreateBitCast(FVal, DestTy); 2515 return SelectInst::Create(Cond, X, CastedVal, "", nullptr, Sel); 2516 } 2517 2518 if (match(FVal, m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy && 2519 !isa<Constant>(X)) { 2520 // bitcast(select(Cond, Y, bitcast(X))) --> select'(Cond, bitcast(Y), X) 2521 Value *CastedVal = Builder.CreateBitCast(TVal, DestTy); 2522 return SelectInst::Create(Cond, CastedVal, X, "", nullptr, Sel); 2523 } 2524 2525 return nullptr; 2526 } 2527 2528 /// Check if all users of CI are StoreInsts. 2529 static bool hasStoreUsersOnly(CastInst &CI) { 2530 for (User *U : CI.users()) { 2531 if (!isa<StoreInst>(U)) 2532 return false; 2533 } 2534 return true; 2535 } 2536 2537 /// This function handles following case 2538 /// 2539 /// A -> B cast 2540 /// PHI 2541 /// B -> A cast 2542 /// 2543 /// All the related PHI nodes can be replaced by new PHI nodes with type A. 2544 /// The uses of \p CI can be changed to the new PHI node corresponding to \p PN. 2545 Instruction *InstCombinerImpl::optimizeBitCastFromPhi(CastInst &CI, 2546 PHINode *PN) { 2547 // BitCast used by Store can be handled in InstCombineLoadStoreAlloca.cpp. 2548 if (hasStoreUsersOnly(CI)) 2549 return nullptr; 2550 2551 Value *Src = CI.getOperand(0); 2552 Type *SrcTy = Src->getType(); // Type B 2553 Type *DestTy = CI.getType(); // Type A 2554 2555 SmallVector<PHINode *, 4> PhiWorklist; 2556 SmallSetVector<PHINode *, 4> OldPhiNodes; 2557 2558 // Find all of the A->B casts and PHI nodes. 2559 // We need to inspect all related PHI nodes, but PHIs can be cyclic, so 2560 // OldPhiNodes is used to track all known PHI nodes, before adding a new 2561 // PHI to PhiWorklist, it is checked against and added to OldPhiNodes first. 2562 PhiWorklist.push_back(PN); 2563 OldPhiNodes.insert(PN); 2564 while (!PhiWorklist.empty()) { 2565 auto *OldPN = PhiWorklist.pop_back_val(); 2566 for (Value *IncValue : OldPN->incoming_values()) { 2567 if (isa<Constant>(IncValue)) 2568 continue; 2569 2570 if (auto *LI = dyn_cast<LoadInst>(IncValue)) { 2571 // If there is a sequence of one or more load instructions, each loaded 2572 // value is used as address of later load instruction, bitcast is 2573 // necessary to change the value type, don't optimize it. For 2574 // simplicity we give up if the load address comes from another load. 2575 Value *Addr = LI->getOperand(0); 2576 if (Addr == &CI || isa<LoadInst>(Addr)) 2577 return nullptr; 2578 // Don't tranform "load <256 x i32>, <256 x i32>*" to 2579 // "load x86_amx, x86_amx*", because x86_amx* is invalid. 2580 // TODO: Remove this check when bitcast between vector and x86_amx 2581 // is replaced with a specific intrinsic. 2582 if (DestTy->isX86_AMXTy()) 2583 return nullptr; 2584 if (LI->hasOneUse() && LI->isSimple()) 2585 continue; 2586 // If a LoadInst has more than one use, changing the type of loaded 2587 // value may create another bitcast. 2588 return nullptr; 2589 } 2590 2591 if (auto *PNode = dyn_cast<PHINode>(IncValue)) { 2592 if (OldPhiNodes.insert(PNode)) 2593 PhiWorklist.push_back(PNode); 2594 continue; 2595 } 2596 2597 auto *BCI = dyn_cast<BitCastInst>(IncValue); 2598 // We can't handle other instructions. 2599 if (!BCI) 2600 return nullptr; 2601 2602 // Verify it's a A->B cast. 2603 Type *TyA = BCI->getOperand(0)->getType(); 2604 Type *TyB = BCI->getType(); 2605 if (TyA != DestTy || TyB != SrcTy) 2606 return nullptr; 2607 } 2608 } 2609 2610 // Check that each user of each old PHI node is something that we can 2611 // rewrite, so that all of the old PHI nodes can be cleaned up afterwards. 2612 for (auto *OldPN : OldPhiNodes) { 2613 for (User *V : OldPN->users()) { 2614 if (auto *SI = dyn_cast<StoreInst>(V)) { 2615 if (!SI->isSimple() || SI->getOperand(0) != OldPN) 2616 return nullptr; 2617 } else if (auto *BCI = dyn_cast<BitCastInst>(V)) { 2618 // Verify it's a B->A cast. 2619 Type *TyB = BCI->getOperand(0)->getType(); 2620 Type *TyA = BCI->getType(); 2621 if (TyA != DestTy || TyB != SrcTy) 2622 return nullptr; 2623 } else if (auto *PHI = dyn_cast<PHINode>(V)) { 2624 // As long as the user is another old PHI node, then even if we don't 2625 // rewrite it, the PHI web we're considering won't have any users 2626 // outside itself, so it'll be dead. 2627 if (!OldPhiNodes.contains(PHI)) 2628 return nullptr; 2629 } else { 2630 return nullptr; 2631 } 2632 } 2633 } 2634 2635 // For each old PHI node, create a corresponding new PHI node with a type A. 2636 SmallDenseMap<PHINode *, PHINode *> NewPNodes; 2637 for (auto *OldPN : OldPhiNodes) { 2638 Builder.SetInsertPoint(OldPN); 2639 PHINode *NewPN = Builder.CreatePHI(DestTy, OldPN->getNumOperands()); 2640 NewPNodes[OldPN] = NewPN; 2641 } 2642 2643 // Fill in the operands of new PHI nodes. 2644 for (auto *OldPN : OldPhiNodes) { 2645 PHINode *NewPN = NewPNodes[OldPN]; 2646 for (unsigned j = 0, e = OldPN->getNumOperands(); j != e; ++j) { 2647 Value *V = OldPN->getOperand(j); 2648 Value *NewV = nullptr; 2649 if (auto *C = dyn_cast<Constant>(V)) { 2650 NewV = ConstantExpr::getBitCast(C, DestTy); 2651 } else if (auto *LI = dyn_cast<LoadInst>(V)) { 2652 // Explicitly perform load combine to make sure no opposing transform 2653 // can remove the bitcast in the meantime and trigger an infinite loop. 2654 Builder.SetInsertPoint(LI); 2655 NewV = combineLoadToNewType(*LI, DestTy); 2656 // Remove the old load and its use in the old phi, which itself becomes 2657 // dead once the whole transform finishes. 2658 replaceInstUsesWith(*LI, PoisonValue::get(LI->getType())); 2659 eraseInstFromFunction(*LI); 2660 } else if (auto *BCI = dyn_cast<BitCastInst>(V)) { 2661 NewV = BCI->getOperand(0); 2662 } else if (auto *PrevPN = dyn_cast<PHINode>(V)) { 2663 NewV = NewPNodes[PrevPN]; 2664 } 2665 assert(NewV); 2666 NewPN->addIncoming(NewV, OldPN->getIncomingBlock(j)); 2667 } 2668 } 2669 2670 // Traverse all accumulated PHI nodes and process its users, 2671 // which are Stores and BitcCasts. Without this processing 2672 // NewPHI nodes could be replicated and could lead to extra 2673 // moves generated after DeSSA. 2674 // If there is a store with type B, change it to type A. 2675 2676 2677 // Replace users of BitCast B->A with NewPHI. These will help 2678 // later to get rid off a closure formed by OldPHI nodes. 2679 Instruction *RetVal = nullptr; 2680 for (auto *OldPN : OldPhiNodes) { 2681 PHINode *NewPN = NewPNodes[OldPN]; 2682 for (User *V : make_early_inc_range(OldPN->users())) { 2683 if (auto *SI = dyn_cast<StoreInst>(V)) { 2684 assert(SI->isSimple() && SI->getOperand(0) == OldPN); 2685 Builder.SetInsertPoint(SI); 2686 auto *NewBC = 2687 cast<BitCastInst>(Builder.CreateBitCast(NewPN, SrcTy)); 2688 SI->setOperand(0, NewBC); 2689 Worklist.push(SI); 2690 assert(hasStoreUsersOnly(*NewBC)); 2691 } 2692 else if (auto *BCI = dyn_cast<BitCastInst>(V)) { 2693 Type *TyB = BCI->getOperand(0)->getType(); 2694 Type *TyA = BCI->getType(); 2695 assert(TyA == DestTy && TyB == SrcTy); 2696 (void) TyA; 2697 (void) TyB; 2698 Instruction *I = replaceInstUsesWith(*BCI, NewPN); 2699 if (BCI == &CI) 2700 RetVal = I; 2701 } else if (auto *PHI = dyn_cast<PHINode>(V)) { 2702 assert(OldPhiNodes.contains(PHI)); 2703 (void) PHI; 2704 } else { 2705 llvm_unreachable("all uses should be handled"); 2706 } 2707 } 2708 } 2709 2710 return RetVal; 2711 } 2712 2713 /// Fold (bitcast (or (and (bitcast X to int), signmask), nneg Y) to fp) to 2714 /// copysign((bitcast Y to fp), X) 2715 static Value *foldCopySignIdioms(BitCastInst &CI, 2716 InstCombiner::BuilderTy &Builder, 2717 const SimplifyQuery &SQ) { 2718 Value *X, *Y; 2719 Type *FTy = CI.getType(); 2720 if (!FTy->isFPOrFPVectorTy()) 2721 return nullptr; 2722 if (!match(&CI, m_ElementWiseBitCast(m_c_Or( 2723 m_And(m_ElementWiseBitCast(m_Value(X)), m_SignMask()), 2724 m_Value(Y))))) 2725 return nullptr; 2726 if (X->getType() != FTy) 2727 return nullptr; 2728 if (!isKnownNonNegative(Y, SQ)) 2729 return nullptr; 2730 2731 return Builder.CreateCopySign(Builder.CreateBitCast(Y, FTy), X); 2732 } 2733 2734 Instruction *InstCombinerImpl::visitBitCast(BitCastInst &CI) { 2735 // If the operands are integer typed then apply the integer transforms, 2736 // otherwise just apply the common ones. 2737 Value *Src = CI.getOperand(0); 2738 Type *SrcTy = Src->getType(); 2739 Type *DestTy = CI.getType(); 2740 2741 // Get rid of casts from one type to the same type. These are useless and can 2742 // be replaced by the operand. 2743 if (DestTy == Src->getType()) 2744 return replaceInstUsesWith(CI, Src); 2745 2746 if (isa<FixedVectorType>(DestTy)) { 2747 if (isa<IntegerType>(SrcTy)) { 2748 // If this is a cast from an integer to vector, check to see if the input 2749 // is a trunc or zext of a bitcast from vector. If so, we can replace all 2750 // the casts with a shuffle and (potentially) a bitcast. 2751 if (isa<TruncInst>(Src) || isa<ZExtInst>(Src)) { 2752 CastInst *SrcCast = cast<CastInst>(Src); 2753 if (BitCastInst *BCIn = dyn_cast<BitCastInst>(SrcCast->getOperand(0))) 2754 if (isa<VectorType>(BCIn->getOperand(0)->getType())) 2755 if (Instruction *I = optimizeVectorResizeWithIntegerBitCasts( 2756 BCIn->getOperand(0), cast<VectorType>(DestTy), *this)) 2757 return I; 2758 } 2759 2760 // If the input is an 'or' instruction, we may be doing shifts and ors to 2761 // assemble the elements of the vector manually. Try to rip the code out 2762 // and replace it with insertelements. 2763 if (Value *V = optimizeIntegerToVectorInsertions(CI, *this)) 2764 return replaceInstUsesWith(CI, V); 2765 } 2766 } 2767 2768 if (FixedVectorType *SrcVTy = dyn_cast<FixedVectorType>(SrcTy)) { 2769 if (SrcVTy->getNumElements() == 1) { 2770 // If our destination is not a vector, then make this a straight 2771 // scalar-scalar cast. 2772 if (!DestTy->isVectorTy()) { 2773 Value *Elem = 2774 Builder.CreateExtractElement(Src, 2775 Constant::getNullValue(Type::getInt32Ty(CI.getContext()))); 2776 return CastInst::Create(Instruction::BitCast, Elem, DestTy); 2777 } 2778 2779 // Otherwise, see if our source is an insert. If so, then use the scalar 2780 // component directly: 2781 // bitcast (inselt <1 x elt> V, X, 0) to <n x m> --> bitcast X to <n x m> 2782 if (auto *InsElt = dyn_cast<InsertElementInst>(Src)) 2783 return new BitCastInst(InsElt->getOperand(1), DestTy); 2784 } 2785 2786 // Convert an artificial vector insert into more analyzable bitwise logic. 2787 unsigned BitWidth = DestTy->getScalarSizeInBits(); 2788 Value *X, *Y; 2789 uint64_t IndexC; 2790 if (match(Src, m_OneUse(m_InsertElt(m_OneUse(m_BitCast(m_Value(X))), 2791 m_Value(Y), m_ConstantInt(IndexC)))) && 2792 DestTy->isIntegerTy() && X->getType() == DestTy && 2793 Y->getType()->isIntegerTy() && isDesirableIntType(BitWidth)) { 2794 // Adjust for big endian - the LSBs are at the high index. 2795 if (DL.isBigEndian()) 2796 IndexC = SrcVTy->getNumElements() - 1 - IndexC; 2797 2798 // We only handle (endian-normalized) insert to index 0. Any other insert 2799 // would require a left-shift, so that is an extra instruction. 2800 if (IndexC == 0) { 2801 // bitcast (inselt (bitcast X), Y, 0) --> or (and X, MaskC), (zext Y) 2802 unsigned EltWidth = Y->getType()->getScalarSizeInBits(); 2803 APInt MaskC = APInt::getHighBitsSet(BitWidth, BitWidth - EltWidth); 2804 Value *AndX = Builder.CreateAnd(X, MaskC); 2805 Value *ZextY = Builder.CreateZExt(Y, DestTy); 2806 return BinaryOperator::CreateOr(AndX, ZextY); 2807 } 2808 } 2809 } 2810 2811 if (auto *Shuf = dyn_cast<ShuffleVectorInst>(Src)) { 2812 // Okay, we have (bitcast (shuffle ..)). Check to see if this is 2813 // a bitcast to a vector with the same # elts. 2814 Value *ShufOp0 = Shuf->getOperand(0); 2815 Value *ShufOp1 = Shuf->getOperand(1); 2816 auto ShufElts = cast<VectorType>(Shuf->getType())->getElementCount(); 2817 auto SrcVecElts = cast<VectorType>(ShufOp0->getType())->getElementCount(); 2818 if (Shuf->hasOneUse() && DestTy->isVectorTy() && 2819 cast<VectorType>(DestTy)->getElementCount() == ShufElts && 2820 ShufElts == SrcVecElts) { 2821 BitCastInst *Tmp; 2822 // If either of the operands is a cast from CI.getType(), then 2823 // evaluating the shuffle in the casted destination's type will allow 2824 // us to eliminate at least one cast. 2825 if (((Tmp = dyn_cast<BitCastInst>(ShufOp0)) && 2826 Tmp->getOperand(0)->getType() == DestTy) || 2827 ((Tmp = dyn_cast<BitCastInst>(ShufOp1)) && 2828 Tmp->getOperand(0)->getType() == DestTy)) { 2829 Value *LHS = Builder.CreateBitCast(ShufOp0, DestTy); 2830 Value *RHS = Builder.CreateBitCast(ShufOp1, DestTy); 2831 // Return a new shuffle vector. Use the same element ID's, as we 2832 // know the vector types match #elts. 2833 return new ShuffleVectorInst(LHS, RHS, Shuf->getShuffleMask()); 2834 } 2835 } 2836 2837 // A bitcasted-to-scalar and byte/bit reversing shuffle is better recognized 2838 // as a byte/bit swap: 2839 // bitcast <N x i8> (shuf X, undef, <N, N-1,...0>) -> bswap (bitcast X) 2840 // bitcast <N x i1> (shuf X, undef, <N, N-1,...0>) -> bitreverse (bitcast X) 2841 if (DestTy->isIntegerTy() && ShufElts.getKnownMinValue() % 2 == 0 && 2842 Shuf->hasOneUse() && Shuf->isReverse()) { 2843 unsigned IntrinsicNum = 0; 2844 if (DL.isLegalInteger(DestTy->getScalarSizeInBits()) && 2845 SrcTy->getScalarSizeInBits() == 8) { 2846 IntrinsicNum = Intrinsic::bswap; 2847 } else if (SrcTy->getScalarSizeInBits() == 1) { 2848 IntrinsicNum = Intrinsic::bitreverse; 2849 } 2850 if (IntrinsicNum != 0) { 2851 assert(ShufOp0->getType() == SrcTy && "Unexpected shuffle mask"); 2852 assert(match(ShufOp1, m_Undef()) && "Unexpected shuffle op"); 2853 Function *BswapOrBitreverse = Intrinsic::getOrInsertDeclaration( 2854 CI.getModule(), IntrinsicNum, DestTy); 2855 Value *ScalarX = Builder.CreateBitCast(ShufOp0, DestTy); 2856 return CallInst::Create(BswapOrBitreverse, {ScalarX}); 2857 } 2858 } 2859 } 2860 2861 // Handle the A->B->A cast, and there is an intervening PHI node. 2862 if (PHINode *PN = dyn_cast<PHINode>(Src)) 2863 if (Instruction *I = optimizeBitCastFromPhi(CI, PN)) 2864 return I; 2865 2866 if (Instruction *I = canonicalizeBitCastExtElt(CI, *this)) 2867 return I; 2868 2869 if (Instruction *I = foldBitCastBitwiseLogic(CI, Builder)) 2870 return I; 2871 2872 if (Instruction *I = foldBitCastSelect(CI, Builder)) 2873 return I; 2874 2875 if (Value *V = foldCopySignIdioms(CI, Builder, SQ.getWithInstruction(&CI))) 2876 return replaceInstUsesWith(CI, V); 2877 2878 return commonCastTransforms(CI); 2879 } 2880 2881 Instruction *InstCombinerImpl::visitAddrSpaceCast(AddrSpaceCastInst &CI) { 2882 return commonCastTransforms(CI); 2883 } 2884