1 //===- InstCombineSimplifyDemanded.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 contains logic for simplifying instructions based on information 10 // about how they are used. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "InstCombineInternal.h" 15 #include "llvm/Analysis/TargetTransformInfo.h" 16 #include "llvm/Analysis/ValueTracking.h" 17 #include "llvm/IR/IntrinsicInst.h" 18 #include "llvm/IR/PatternMatch.h" 19 #include "llvm/Support/KnownBits.h" 20 #include "llvm/Transforms/InstCombine/InstCombiner.h" 21 22 using namespace llvm; 23 using namespace llvm::PatternMatch; 24 25 #define DEBUG_TYPE "instcombine" 26 27 /// Check to see if the specified operand of the specified instruction is a 28 /// constant integer. If so, check to see if there are any bits set in the 29 /// constant that are not demanded. If so, shrink the constant and return true. 30 static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo, 31 const APInt &Demanded) { 32 assert(I && "No instruction?"); 33 assert(OpNo < I->getNumOperands() && "Operand index too large"); 34 35 // The operand must be a constant integer or splat integer. 36 Value *Op = I->getOperand(OpNo); 37 const APInt *C; 38 if (!match(Op, m_APInt(C))) 39 return false; 40 41 // If there are no bits set that aren't demanded, nothing to do. 42 if (C->isSubsetOf(Demanded)) 43 return false; 44 45 // This instruction is producing bits that are not demanded. Shrink the RHS. 46 I->setOperand(OpNo, ConstantInt::get(Op->getType(), *C & Demanded)); 47 48 return true; 49 } 50 51 52 53 /// Inst is an integer instruction that SimplifyDemandedBits knows about. See if 54 /// the instruction has any properties that allow us to simplify its operands. 55 bool InstCombinerImpl::SimplifyDemandedInstructionBits(Instruction &Inst) { 56 unsigned BitWidth = Inst.getType()->getScalarSizeInBits(); 57 KnownBits Known(BitWidth); 58 APInt DemandedMask(APInt::getAllOnesValue(BitWidth)); 59 60 Value *V = SimplifyDemandedUseBits(&Inst, DemandedMask, Known, 61 0, &Inst); 62 if (!V) return false; 63 if (V == &Inst) return true; 64 replaceInstUsesWith(Inst, V); 65 return true; 66 } 67 68 /// This form of SimplifyDemandedBits simplifies the specified instruction 69 /// operand if possible, updating it in place. It returns true if it made any 70 /// change and false otherwise. 71 bool InstCombinerImpl::SimplifyDemandedBits(Instruction *I, unsigned OpNo, 72 const APInt &DemandedMask, 73 KnownBits &Known, unsigned Depth) { 74 Use &U = I->getOperandUse(OpNo); 75 Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask, Known, 76 Depth, I); 77 if (!NewVal) return false; 78 if (Instruction* OpInst = dyn_cast<Instruction>(U)) 79 salvageDebugInfo(*OpInst); 80 81 replaceUse(U, NewVal); 82 return true; 83 } 84 85 /// This function attempts to replace V with a simpler value based on the 86 /// demanded bits. When this function is called, it is known that only the bits 87 /// set in DemandedMask of the result of V are ever used downstream. 88 /// Consequently, depending on the mask and V, it may be possible to replace V 89 /// with a constant or one of its operands. In such cases, this function does 90 /// the replacement and returns true. In all other cases, it returns false after 91 /// analyzing the expression and setting KnownOne and known to be one in the 92 /// expression. Known.Zero contains all the bits that are known to be zero in 93 /// the expression. These are provided to potentially allow the caller (which 94 /// might recursively be SimplifyDemandedBits itself) to simplify the 95 /// expression. 96 /// Known.One and Known.Zero always follow the invariant that: 97 /// Known.One & Known.Zero == 0. 98 /// That is, a bit can't be both 1 and 0. Note that the bits in Known.One and 99 /// Known.Zero may only be accurate for those bits set in DemandedMask. Note 100 /// also that the bitwidth of V, DemandedMask, Known.Zero and Known.One must all 101 /// be the same. 102 /// 103 /// This returns null if it did not change anything and it permits no 104 /// simplification. This returns V itself if it did some simplification of V's 105 /// operands based on the information about what bits are demanded. This returns 106 /// some other non-null value if it found out that V is equal to another value 107 /// in the context where the specified bits are demanded, but not for all users. 108 Value *InstCombinerImpl::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, 109 KnownBits &Known, 110 unsigned Depth, 111 Instruction *CxtI) { 112 assert(V != nullptr && "Null pointer of Value???"); 113 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth"); 114 uint32_t BitWidth = DemandedMask.getBitWidth(); 115 Type *VTy = V->getType(); 116 assert( 117 (!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) && 118 Known.getBitWidth() == BitWidth && 119 "Value *V, DemandedMask and Known must have same BitWidth"); 120 121 if (isa<Constant>(V)) { 122 computeKnownBits(V, Known, Depth, CxtI); 123 return nullptr; 124 } 125 126 Known.resetAll(); 127 if (DemandedMask.isNullValue()) // Not demanding any bits from V. 128 return UndefValue::get(VTy); 129 130 if (Depth == MaxAnalysisRecursionDepth) 131 return nullptr; 132 133 if (isa<ScalableVectorType>(VTy)) 134 return nullptr; 135 136 Instruction *I = dyn_cast<Instruction>(V); 137 if (!I) { 138 computeKnownBits(V, Known, Depth, CxtI); 139 return nullptr; // Only analyze instructions. 140 } 141 142 // If there are multiple uses of this value and we aren't at the root, then 143 // we can't do any simplifications of the operands, because DemandedMask 144 // only reflects the bits demanded by *one* of the users. 145 if (Depth != 0 && !I->hasOneUse()) 146 return SimplifyMultipleUseDemandedBits(I, DemandedMask, Known, Depth, CxtI); 147 148 KnownBits LHSKnown(BitWidth), RHSKnown(BitWidth); 149 150 // If this is the root being simplified, allow it to have multiple uses, 151 // just set the DemandedMask to all bits so that we can try to simplify the 152 // operands. This allows visitTruncInst (for example) to simplify the 153 // operand of a trunc without duplicating all the logic below. 154 if (Depth == 0 && !V->hasOneUse()) 155 DemandedMask.setAllBits(); 156 157 switch (I->getOpcode()) { 158 default: 159 computeKnownBits(I, Known, Depth, CxtI); 160 break; 161 case Instruction::And: { 162 // If either the LHS or the RHS are Zero, the result is zero. 163 if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) || 164 SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.Zero, LHSKnown, 165 Depth + 1)) 166 return I; 167 assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?"); 168 assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?"); 169 170 Known = LHSKnown & RHSKnown; 171 172 // If the client is only demanding bits that we know, return the known 173 // constant. 174 if (DemandedMask.isSubsetOf(Known.Zero | Known.One)) 175 return Constant::getIntegerValue(VTy, Known.One); 176 177 // If all of the demanded bits are known 1 on one side, return the other. 178 // These bits cannot contribute to the result of the 'and'. 179 if (DemandedMask.isSubsetOf(LHSKnown.Zero | RHSKnown.One)) 180 return I->getOperand(0); 181 if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.One)) 182 return I->getOperand(1); 183 184 // If the RHS is a constant, see if we can simplify it. 185 if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnown.Zero)) 186 return I; 187 188 break; 189 } 190 case Instruction::Or: { 191 // If either the LHS or the RHS are One, the result is One. 192 if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) || 193 SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.One, LHSKnown, 194 Depth + 1)) 195 return I; 196 assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?"); 197 assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?"); 198 199 Known = LHSKnown | RHSKnown; 200 201 // If the client is only demanding bits that we know, return the known 202 // constant. 203 if (DemandedMask.isSubsetOf(Known.Zero | Known.One)) 204 return Constant::getIntegerValue(VTy, Known.One); 205 206 // If all of the demanded bits are known zero on one side, return the other. 207 // These bits cannot contribute to the result of the 'or'. 208 if (DemandedMask.isSubsetOf(LHSKnown.One | RHSKnown.Zero)) 209 return I->getOperand(0); 210 if (DemandedMask.isSubsetOf(RHSKnown.One | LHSKnown.Zero)) 211 return I->getOperand(1); 212 213 // If the RHS is a constant, see if we can simplify it. 214 if (ShrinkDemandedConstant(I, 1, DemandedMask)) 215 return I; 216 217 break; 218 } 219 case Instruction::Xor: { 220 if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) || 221 SimplifyDemandedBits(I, 0, DemandedMask, LHSKnown, Depth + 1)) 222 return I; 223 assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?"); 224 assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?"); 225 226 Known = LHSKnown ^ RHSKnown; 227 228 // If the client is only demanding bits that we know, return the known 229 // constant. 230 if (DemandedMask.isSubsetOf(Known.Zero | Known.One)) 231 return Constant::getIntegerValue(VTy, Known.One); 232 233 // If all of the demanded bits are known zero on one side, return the other. 234 // These bits cannot contribute to the result of the 'xor'. 235 if (DemandedMask.isSubsetOf(RHSKnown.Zero)) 236 return I->getOperand(0); 237 if (DemandedMask.isSubsetOf(LHSKnown.Zero)) 238 return I->getOperand(1); 239 240 // If all of the demanded bits are known to be zero on one side or the 241 // other, turn this into an *inclusive* or. 242 // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 243 if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.Zero)) { 244 Instruction *Or = 245 BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1), 246 I->getName()); 247 return InsertNewInstWith(Or, *I); 248 } 249 250 // If all of the demanded bits on one side are known, and all of the set 251 // bits on that side are also known to be set on the other side, turn this 252 // into an AND, as we know the bits will be cleared. 253 // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 254 if (DemandedMask.isSubsetOf(RHSKnown.Zero|RHSKnown.One) && 255 RHSKnown.One.isSubsetOf(LHSKnown.One)) { 256 Constant *AndC = Constant::getIntegerValue(VTy, 257 ~RHSKnown.One & DemandedMask); 258 Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 259 return InsertNewInstWith(And, *I); 260 } 261 262 // If the RHS is a constant, see if we can change it. Don't alter a -1 263 // constant because that's a canonical 'not' op, and that is better for 264 // combining, SCEV, and codegen. 265 const APInt *C; 266 if (match(I->getOperand(1), m_APInt(C)) && !C->isAllOnesValue()) { 267 if ((*C | ~DemandedMask).isAllOnesValue()) { 268 // Force bits to 1 to create a 'not' op. 269 I->setOperand(1, ConstantInt::getAllOnesValue(VTy)); 270 return I; 271 } 272 // If we can't turn this into a 'not', try to shrink the constant. 273 if (ShrinkDemandedConstant(I, 1, DemandedMask)) 274 return I; 275 } 276 277 // If our LHS is an 'and' and if it has one use, and if any of the bits we 278 // are flipping are known to be set, then the xor is just resetting those 279 // bits to zero. We can just knock out bits from the 'and' and the 'xor', 280 // simplifying both of them. 281 if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0))) { 282 ConstantInt *AndRHS, *XorRHS; 283 if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() && 284 match(I->getOperand(1), m_ConstantInt(XorRHS)) && 285 match(LHSInst->getOperand(1), m_ConstantInt(AndRHS)) && 286 (LHSKnown.One & RHSKnown.One & DemandedMask) != 0) { 287 APInt NewMask = ~(LHSKnown.One & RHSKnown.One & DemandedMask); 288 289 Constant *AndC = 290 ConstantInt::get(I->getType(), NewMask & AndRHS->getValue()); 291 Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 292 InsertNewInstWith(NewAnd, *I); 293 294 Constant *XorC = 295 ConstantInt::get(I->getType(), NewMask & XorRHS->getValue()); 296 Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC); 297 return InsertNewInstWith(NewXor, *I); 298 } 299 } 300 break; 301 } 302 case Instruction::Select: { 303 Value *LHS, *RHS; 304 SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor; 305 if (SPF == SPF_UMAX) { 306 // UMax(A, C) == A if ... 307 // The lowest non-zero bit of DemandMask is higher than the highest 308 // non-zero bit of C. 309 const APInt *C; 310 unsigned CTZ = DemandedMask.countTrailingZeros(); 311 if (match(RHS, m_APInt(C)) && CTZ >= C->getActiveBits()) 312 return LHS; 313 } else if (SPF == SPF_UMIN) { 314 // UMin(A, C) == A if ... 315 // The lowest non-zero bit of DemandMask is higher than the highest 316 // non-one bit of C. 317 // This comes from using DeMorgans on the above umax example. 318 const APInt *C; 319 unsigned CTZ = DemandedMask.countTrailingZeros(); 320 if (match(RHS, m_APInt(C)) && 321 CTZ >= C->getBitWidth() - C->countLeadingOnes()) 322 return LHS; 323 } 324 325 // If this is a select as part of any other min/max pattern, don't simplify 326 // any further in case we break the structure. 327 if (SPF != SPF_UNKNOWN) 328 return nullptr; 329 330 if (SimplifyDemandedBits(I, 2, DemandedMask, RHSKnown, Depth + 1) || 331 SimplifyDemandedBits(I, 1, DemandedMask, LHSKnown, Depth + 1)) 332 return I; 333 assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?"); 334 assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?"); 335 336 // If the operands are constants, see if we can simplify them. 337 // This is similar to ShrinkDemandedConstant, but for a select we want to 338 // try to keep the selected constants the same as icmp value constants, if 339 // we can. This helps not break apart (or helps put back together) 340 // canonical patterns like min and max. 341 auto CanonicalizeSelectConstant = [](Instruction *I, unsigned OpNo, 342 const APInt &DemandedMask) { 343 const APInt *SelC; 344 if (!match(I->getOperand(OpNo), m_APInt(SelC))) 345 return false; 346 347 // Get the constant out of the ICmp, if there is one. 348 const APInt *CmpC; 349 ICmpInst::Predicate Pred; 350 if (!match(I->getOperand(0), m_c_ICmp(Pred, m_APInt(CmpC), m_Value())) || 351 CmpC->getBitWidth() != SelC->getBitWidth()) 352 return ShrinkDemandedConstant(I, OpNo, DemandedMask); 353 354 // If the constant is already the same as the ICmp, leave it as-is. 355 if (*CmpC == *SelC) 356 return false; 357 // If the constants are not already the same, but can be with the demand 358 // mask, use the constant value from the ICmp. 359 if ((*CmpC & DemandedMask) == (*SelC & DemandedMask)) { 360 I->setOperand(OpNo, ConstantInt::get(I->getType(), *CmpC)); 361 return true; 362 } 363 return ShrinkDemandedConstant(I, OpNo, DemandedMask); 364 }; 365 if (CanonicalizeSelectConstant(I, 1, DemandedMask) || 366 CanonicalizeSelectConstant(I, 2, DemandedMask)) 367 return I; 368 369 // Only known if known in both the LHS and RHS. 370 Known = KnownBits::commonBits(LHSKnown, RHSKnown); 371 break; 372 } 373 case Instruction::ZExt: 374 case Instruction::Trunc: { 375 unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); 376 377 APInt InputDemandedMask = DemandedMask.zextOrTrunc(SrcBitWidth); 378 KnownBits InputKnown(SrcBitWidth); 379 if (SimplifyDemandedBits(I, 0, InputDemandedMask, InputKnown, Depth + 1)) 380 return I; 381 assert(InputKnown.getBitWidth() == SrcBitWidth && "Src width changed?"); 382 Known = InputKnown.zextOrTrunc(BitWidth); 383 assert(!Known.hasConflict() && "Bits known to be one AND zero?"); 384 break; 385 } 386 case Instruction::BitCast: 387 if (!I->getOperand(0)->getType()->isIntOrIntVectorTy()) 388 return nullptr; // vector->int or fp->int? 389 390 if (VectorType *DstVTy = dyn_cast<VectorType>(I->getType())) { 391 if (VectorType *SrcVTy = 392 dyn_cast<VectorType>(I->getOperand(0)->getType())) { 393 if (cast<FixedVectorType>(DstVTy)->getNumElements() != 394 cast<FixedVectorType>(SrcVTy)->getNumElements()) 395 // Don't touch a bitcast between vectors of different element counts. 396 return nullptr; 397 } else 398 // Don't touch a scalar-to-vector bitcast. 399 return nullptr; 400 } else if (I->getOperand(0)->getType()->isVectorTy()) 401 // Don't touch a vector-to-scalar bitcast. 402 return nullptr; 403 404 if (SimplifyDemandedBits(I, 0, DemandedMask, Known, Depth + 1)) 405 return I; 406 assert(!Known.hasConflict() && "Bits known to be one AND zero?"); 407 break; 408 case Instruction::SExt: { 409 // Compute the bits in the result that are not present in the input. 410 unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); 411 412 APInt InputDemandedBits = DemandedMask.trunc(SrcBitWidth); 413 414 // If any of the sign extended bits are demanded, we know that the sign 415 // bit is demanded. 416 if (DemandedMask.getActiveBits() > SrcBitWidth) 417 InputDemandedBits.setBit(SrcBitWidth-1); 418 419 KnownBits InputKnown(SrcBitWidth); 420 if (SimplifyDemandedBits(I, 0, InputDemandedBits, InputKnown, Depth + 1)) 421 return I; 422 423 // If the input sign bit is known zero, or if the NewBits are not demanded 424 // convert this into a zero extension. 425 if (InputKnown.isNonNegative() || 426 DemandedMask.getActiveBits() <= SrcBitWidth) { 427 // Convert to ZExt cast. 428 CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName()); 429 return InsertNewInstWith(NewCast, *I); 430 } 431 432 // If the sign bit of the input is known set or clear, then we know the 433 // top bits of the result. 434 Known = InputKnown.sext(BitWidth); 435 assert(!Known.hasConflict() && "Bits known to be one AND zero?"); 436 break; 437 } 438 case Instruction::Add: 439 if ((DemandedMask & 1) == 0) { 440 // If we do not need the low bit, try to convert bool math to logic: 441 // add iN (zext i1 X), (sext i1 Y) --> sext (~X & Y) to iN 442 Value *X, *Y; 443 if (match(I, m_c_Add(m_OneUse(m_ZExt(m_Value(X))), 444 m_OneUse(m_SExt(m_Value(Y))))) && 445 X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType()) { 446 // Truth table for inputs and output signbits: 447 // X:0 | X:1 448 // ---------- 449 // Y:0 | 0 | 0 | 450 // Y:1 | -1 | 0 | 451 // ---------- 452 IRBuilderBase::InsertPointGuard Guard(Builder); 453 Builder.SetInsertPoint(I); 454 Value *AndNot = Builder.CreateAnd(Builder.CreateNot(X), Y); 455 return Builder.CreateSExt(AndNot, VTy); 456 } 457 458 // add iN (sext i1 X), (sext i1 Y) --> sext (X | Y) to iN 459 // TODO: Relax the one-use checks because we are removing an instruction? 460 if (match(I, m_Add(m_OneUse(m_SExt(m_Value(X))), 461 m_OneUse(m_SExt(m_Value(Y))))) && 462 X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType()) { 463 // Truth table for inputs and output signbits: 464 // X:0 | X:1 465 // ----------- 466 // Y:0 | -1 | -1 | 467 // Y:1 | -1 | 0 | 468 // ----------- 469 IRBuilderBase::InsertPointGuard Guard(Builder); 470 Builder.SetInsertPoint(I); 471 Value *Or = Builder.CreateOr(X, Y); 472 return Builder.CreateSExt(Or, VTy); 473 } 474 } 475 LLVM_FALLTHROUGH; 476 case Instruction::Sub: { 477 /// If the high-bits of an ADD/SUB are not demanded, then we do not care 478 /// about the high bits of the operands. 479 unsigned NLZ = DemandedMask.countLeadingZeros(); 480 // Right fill the mask of bits for this ADD/SUB to demand the most 481 // significant bit and all those below it. 482 APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ)); 483 if (ShrinkDemandedConstant(I, 0, DemandedFromOps) || 484 SimplifyDemandedBits(I, 0, DemandedFromOps, LHSKnown, Depth + 1) || 485 ShrinkDemandedConstant(I, 1, DemandedFromOps) || 486 SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1)) { 487 if (NLZ > 0) { 488 // Disable the nsw and nuw flags here: We can no longer guarantee that 489 // we won't wrap after simplification. Removing the nsw/nuw flags is 490 // legal here because the top bit is not demanded. 491 BinaryOperator &BinOP = *cast<BinaryOperator>(I); 492 BinOP.setHasNoSignedWrap(false); 493 BinOP.setHasNoUnsignedWrap(false); 494 } 495 return I; 496 } 497 498 // If we are known to be adding/subtracting zeros to every bit below 499 // the highest demanded bit, we just return the other side. 500 if (DemandedFromOps.isSubsetOf(RHSKnown.Zero)) 501 return I->getOperand(0); 502 // We can't do this with the LHS for subtraction, unless we are only 503 // demanding the LSB. 504 if ((I->getOpcode() == Instruction::Add || 505 DemandedFromOps.isOneValue()) && 506 DemandedFromOps.isSubsetOf(LHSKnown.Zero)) 507 return I->getOperand(1); 508 509 // Otherwise just compute the known bits of the result. 510 bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 511 Known = KnownBits::computeForAddSub(I->getOpcode() == Instruction::Add, 512 NSW, LHSKnown, RHSKnown); 513 break; 514 } 515 case Instruction::Shl: { 516 const APInt *SA; 517 if (match(I->getOperand(1), m_APInt(SA))) { 518 const APInt *ShrAmt; 519 if (match(I->getOperand(0), m_Shr(m_Value(), m_APInt(ShrAmt)))) 520 if (Instruction *Shr = dyn_cast<Instruction>(I->getOperand(0))) 521 if (Value *R = simplifyShrShlDemandedBits(Shr, *ShrAmt, I, *SA, 522 DemandedMask, Known)) 523 return R; 524 525 uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 526 APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt)); 527 528 // If the shift is NUW/NSW, then it does demand the high bits. 529 ShlOperator *IOp = cast<ShlOperator>(I); 530 if (IOp->hasNoSignedWrap()) 531 DemandedMaskIn.setHighBits(ShiftAmt+1); 532 else if (IOp->hasNoUnsignedWrap()) 533 DemandedMaskIn.setHighBits(ShiftAmt); 534 535 if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1)) 536 return I; 537 assert(!Known.hasConflict() && "Bits known to be one AND zero?"); 538 539 bool SignBitZero = Known.Zero.isSignBitSet(); 540 bool SignBitOne = Known.One.isSignBitSet(); 541 Known.Zero <<= ShiftAmt; 542 Known.One <<= ShiftAmt; 543 // low bits known zero. 544 if (ShiftAmt) 545 Known.Zero.setLowBits(ShiftAmt); 546 547 // If this shift has "nsw" keyword, then the result is either a poison 548 // value or has the same sign bit as the first operand. 549 if (IOp->hasNoSignedWrap()) { 550 if (SignBitZero) 551 Known.Zero.setSignBit(); 552 else if (SignBitOne) 553 Known.One.setSignBit(); 554 if (Known.hasConflict()) 555 return UndefValue::get(I->getType()); 556 } 557 } else { 558 computeKnownBits(I, Known, Depth, CxtI); 559 } 560 break; 561 } 562 case Instruction::LShr: { 563 const APInt *SA; 564 if (match(I->getOperand(1), m_APInt(SA))) { 565 uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 566 567 // Unsigned shift right. 568 APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 569 570 // If the shift is exact, then it does demand the low bits (and knows that 571 // they are zero). 572 if (cast<LShrOperator>(I)->isExact()) 573 DemandedMaskIn.setLowBits(ShiftAmt); 574 575 if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1)) 576 return I; 577 assert(!Known.hasConflict() && "Bits known to be one AND zero?"); 578 Known.Zero.lshrInPlace(ShiftAmt); 579 Known.One.lshrInPlace(ShiftAmt); 580 if (ShiftAmt) 581 Known.Zero.setHighBits(ShiftAmt); // high bits known zero. 582 } else { 583 computeKnownBits(I, Known, Depth, CxtI); 584 } 585 break; 586 } 587 case Instruction::AShr: { 588 // If this is an arithmetic shift right and only the low-bit is set, we can 589 // always convert this into a logical shr, even if the shift amount is 590 // variable. The low bit of the shift cannot be an input sign bit unless 591 // the shift amount is >= the size of the datatype, which is undefined. 592 if (DemandedMask.isOneValue()) { 593 // Perform the logical shift right. 594 Instruction *NewVal = BinaryOperator::CreateLShr( 595 I->getOperand(0), I->getOperand(1), I->getName()); 596 return InsertNewInstWith(NewVal, *I); 597 } 598 599 // If the sign bit is the only bit demanded by this ashr, then there is no 600 // need to do it, the shift doesn't change the high bit. 601 if (DemandedMask.isSignMask()) 602 return I->getOperand(0); 603 604 const APInt *SA; 605 if (match(I->getOperand(1), m_APInt(SA))) { 606 uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 607 608 // Signed shift right. 609 APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 610 // If any of the high bits are demanded, we should set the sign bit as 611 // demanded. 612 if (DemandedMask.countLeadingZeros() <= ShiftAmt) 613 DemandedMaskIn.setSignBit(); 614 615 // If the shift is exact, then it does demand the low bits (and knows that 616 // they are zero). 617 if (cast<AShrOperator>(I)->isExact()) 618 DemandedMaskIn.setLowBits(ShiftAmt); 619 620 if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1)) 621 return I; 622 623 unsigned SignBits = ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI); 624 625 assert(!Known.hasConflict() && "Bits known to be one AND zero?"); 626 // Compute the new bits that are at the top now plus sign bits. 627 APInt HighBits(APInt::getHighBitsSet( 628 BitWidth, std::min(SignBits + ShiftAmt - 1, BitWidth))); 629 Known.Zero.lshrInPlace(ShiftAmt); 630 Known.One.lshrInPlace(ShiftAmt); 631 632 // If the input sign bit is known to be zero, or if none of the top bits 633 // are demanded, turn this into an unsigned shift right. 634 assert(BitWidth > ShiftAmt && "Shift amount not saturated?"); 635 if (Known.Zero[BitWidth-ShiftAmt-1] || 636 !DemandedMask.intersects(HighBits)) { 637 BinaryOperator *LShr = BinaryOperator::CreateLShr(I->getOperand(0), 638 I->getOperand(1)); 639 LShr->setIsExact(cast<BinaryOperator>(I)->isExact()); 640 return InsertNewInstWith(LShr, *I); 641 } else if (Known.One[BitWidth-ShiftAmt-1]) { // New bits are known one. 642 Known.One |= HighBits; 643 } 644 } else { 645 computeKnownBits(I, Known, Depth, CxtI); 646 } 647 break; 648 } 649 case Instruction::UDiv: { 650 // UDiv doesn't demand low bits that are zero in the divisor. 651 const APInt *SA; 652 if (match(I->getOperand(1), m_APInt(SA))) { 653 // If the shift is exact, then it does demand the low bits. 654 if (cast<UDivOperator>(I)->isExact()) 655 break; 656 657 // FIXME: Take the demanded mask of the result into account. 658 unsigned RHSTrailingZeros = SA->countTrailingZeros(); 659 APInt DemandedMaskIn = 660 APInt::getHighBitsSet(BitWidth, BitWidth - RHSTrailingZeros); 661 if (SimplifyDemandedBits(I, 0, DemandedMaskIn, LHSKnown, Depth + 1)) 662 return I; 663 664 // Propagate zero bits from the input. 665 Known.Zero.setHighBits(std::min( 666 BitWidth, LHSKnown.Zero.countLeadingOnes() + RHSTrailingZeros)); 667 } else { 668 computeKnownBits(I, Known, Depth, CxtI); 669 } 670 break; 671 } 672 case Instruction::SRem: { 673 ConstantInt *Rem; 674 if (match(I->getOperand(1), m_ConstantInt(Rem))) { 675 // X % -1 demands all the bits because we don't want to introduce 676 // INT_MIN % -1 (== undef) by accident. 677 if (Rem->isMinusOne()) 678 break; 679 APInt RA = Rem->getValue().abs(); 680 if (RA.isPowerOf2()) { 681 if (DemandedMask.ult(RA)) // srem won't affect demanded bits 682 return I->getOperand(0); 683 684 APInt LowBits = RA - 1; 685 APInt Mask2 = LowBits | APInt::getSignMask(BitWidth); 686 if (SimplifyDemandedBits(I, 0, Mask2, LHSKnown, Depth + 1)) 687 return I; 688 689 // The low bits of LHS are unchanged by the srem. 690 Known.Zero = LHSKnown.Zero & LowBits; 691 Known.One = LHSKnown.One & LowBits; 692 693 // If LHS is non-negative or has all low bits zero, then the upper bits 694 // are all zero. 695 if (LHSKnown.isNonNegative() || LowBits.isSubsetOf(LHSKnown.Zero)) 696 Known.Zero |= ~LowBits; 697 698 // If LHS is negative and not all low bits are zero, then the upper bits 699 // are all one. 700 if (LHSKnown.isNegative() && LowBits.intersects(LHSKnown.One)) 701 Known.One |= ~LowBits; 702 703 assert(!Known.hasConflict() && "Bits known to be one AND zero?"); 704 break; 705 } 706 } 707 708 // The sign bit is the LHS's sign bit, except when the result of the 709 // remainder is zero. 710 if (DemandedMask.isSignBitSet()) { 711 computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, CxtI); 712 // If it's known zero, our sign bit is also zero. 713 if (LHSKnown.isNonNegative()) 714 Known.makeNonNegative(); 715 } 716 break; 717 } 718 case Instruction::URem: { 719 KnownBits Known2(BitWidth); 720 APInt AllOnes = APInt::getAllOnesValue(BitWidth); 721 if (SimplifyDemandedBits(I, 0, AllOnes, Known2, Depth + 1) || 722 SimplifyDemandedBits(I, 1, AllOnes, Known2, Depth + 1)) 723 return I; 724 725 unsigned Leaders = Known2.countMinLeadingZeros(); 726 Known.Zero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask; 727 break; 728 } 729 case Instruction::Call: { 730 bool KnownBitsComputed = false; 731 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 732 switch (II->getIntrinsicID()) { 733 case Intrinsic::bswap: { 734 // If the only bits demanded come from one byte of the bswap result, 735 // just shift the input byte into position to eliminate the bswap. 736 unsigned NLZ = DemandedMask.countLeadingZeros(); 737 unsigned NTZ = DemandedMask.countTrailingZeros(); 738 739 // Round NTZ down to the next byte. If we have 11 trailing zeros, then 740 // we need all the bits down to bit 8. Likewise, round NLZ. If we 741 // have 14 leading zeros, round to 8. 742 NLZ &= ~7; 743 NTZ &= ~7; 744 // If we need exactly one byte, we can do this transformation. 745 if (BitWidth-NLZ-NTZ == 8) { 746 unsigned ResultBit = NTZ; 747 unsigned InputBit = BitWidth-NTZ-8; 748 749 // Replace this with either a left or right shift to get the byte into 750 // the right place. 751 Instruction *NewVal; 752 if (InputBit > ResultBit) 753 NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0), 754 ConstantInt::get(I->getType(), InputBit-ResultBit)); 755 else 756 NewVal = BinaryOperator::CreateShl(II->getArgOperand(0), 757 ConstantInt::get(I->getType(), ResultBit-InputBit)); 758 NewVal->takeName(I); 759 return InsertNewInstWith(NewVal, *I); 760 } 761 break; 762 } 763 case Intrinsic::fshr: 764 case Intrinsic::fshl: { 765 const APInt *SA; 766 if (!match(I->getOperand(2), m_APInt(SA))) 767 break; 768 769 // Normalize to funnel shift left. APInt shifts of BitWidth are well- 770 // defined, so no need to special-case zero shifts here. 771 uint64_t ShiftAmt = SA->urem(BitWidth); 772 if (II->getIntrinsicID() == Intrinsic::fshr) 773 ShiftAmt = BitWidth - ShiftAmt; 774 775 APInt DemandedMaskLHS(DemandedMask.lshr(ShiftAmt)); 776 APInt DemandedMaskRHS(DemandedMask.shl(BitWidth - ShiftAmt)); 777 if (SimplifyDemandedBits(I, 0, DemandedMaskLHS, LHSKnown, Depth + 1) || 778 SimplifyDemandedBits(I, 1, DemandedMaskRHS, RHSKnown, Depth + 1)) 779 return I; 780 781 Known.Zero = LHSKnown.Zero.shl(ShiftAmt) | 782 RHSKnown.Zero.lshr(BitWidth - ShiftAmt); 783 Known.One = LHSKnown.One.shl(ShiftAmt) | 784 RHSKnown.One.lshr(BitWidth - ShiftAmt); 785 KnownBitsComputed = true; 786 break; 787 } 788 default: { 789 // Handle target specific intrinsics 790 Optional<Value *> V = targetSimplifyDemandedUseBitsIntrinsic( 791 *II, DemandedMask, Known, KnownBitsComputed); 792 if (V.hasValue()) 793 return V.getValue(); 794 break; 795 } 796 } 797 } 798 799 if (!KnownBitsComputed) 800 computeKnownBits(V, Known, Depth, CxtI); 801 break; 802 } 803 } 804 805 // If the client is only demanding bits that we know, return the known 806 // constant. 807 if (DemandedMask.isSubsetOf(Known.Zero|Known.One)) 808 return Constant::getIntegerValue(VTy, Known.One); 809 return nullptr; 810 } 811 812 /// Helper routine of SimplifyDemandedUseBits. It computes Known 813 /// bits. It also tries to handle simplifications that can be done based on 814 /// DemandedMask, but without modifying the Instruction. 815 Value *InstCombinerImpl::SimplifyMultipleUseDemandedBits( 816 Instruction *I, const APInt &DemandedMask, KnownBits &Known, unsigned Depth, 817 Instruction *CxtI) { 818 unsigned BitWidth = DemandedMask.getBitWidth(); 819 Type *ITy = I->getType(); 820 821 KnownBits LHSKnown(BitWidth); 822 KnownBits RHSKnown(BitWidth); 823 824 // Despite the fact that we can't simplify this instruction in all User's 825 // context, we can at least compute the known bits, and we can 826 // do simplifications that apply to *just* the one user if we know that 827 // this instruction has a simpler value in that context. 828 switch (I->getOpcode()) { 829 case Instruction::And: { 830 // If either the LHS or the RHS are Zero, the result is zero. 831 computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI); 832 computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, 833 CxtI); 834 835 Known = LHSKnown & RHSKnown; 836 837 // If the client is only demanding bits that we know, return the known 838 // constant. 839 if (DemandedMask.isSubsetOf(Known.Zero | Known.One)) 840 return Constant::getIntegerValue(ITy, Known.One); 841 842 // If all of the demanded bits are known 1 on one side, return the other. 843 // These bits cannot contribute to the result of the 'and' in this 844 // context. 845 if (DemandedMask.isSubsetOf(LHSKnown.Zero | RHSKnown.One)) 846 return I->getOperand(0); 847 if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.One)) 848 return I->getOperand(1); 849 850 break; 851 } 852 case Instruction::Or: { 853 // We can simplify (X|Y) -> X or Y in the user's context if we know that 854 // only bits from X or Y are demanded. 855 856 // If either the LHS or the RHS are One, the result is One. 857 computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI); 858 computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, 859 CxtI); 860 861 Known = LHSKnown | RHSKnown; 862 863 // If the client is only demanding bits that we know, return the known 864 // constant. 865 if (DemandedMask.isSubsetOf(Known.Zero | Known.One)) 866 return Constant::getIntegerValue(ITy, Known.One); 867 868 // If all of the demanded bits are known zero on one side, return the 869 // other. These bits cannot contribute to the result of the 'or' in this 870 // context. 871 if (DemandedMask.isSubsetOf(LHSKnown.One | RHSKnown.Zero)) 872 return I->getOperand(0); 873 if (DemandedMask.isSubsetOf(RHSKnown.One | LHSKnown.Zero)) 874 return I->getOperand(1); 875 876 break; 877 } 878 case Instruction::Xor: { 879 // We can simplify (X^Y) -> X or Y in the user's context if we know that 880 // only bits from X or Y are demanded. 881 882 computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI); 883 computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, 884 CxtI); 885 886 Known = LHSKnown ^ RHSKnown; 887 888 // If the client is only demanding bits that we know, return the known 889 // constant. 890 if (DemandedMask.isSubsetOf(Known.Zero | Known.One)) 891 return Constant::getIntegerValue(ITy, Known.One); 892 893 // If all of the demanded bits are known zero on one side, return the 894 // other. 895 if (DemandedMask.isSubsetOf(RHSKnown.Zero)) 896 return I->getOperand(0); 897 if (DemandedMask.isSubsetOf(LHSKnown.Zero)) 898 return I->getOperand(1); 899 900 break; 901 } 902 case Instruction::AShr: { 903 // Compute the Known bits to simplify things downstream. 904 computeKnownBits(I, Known, Depth, CxtI); 905 906 // If this user is only demanding bits that we know, return the known 907 // constant. 908 if (DemandedMask.isSubsetOf(Known.Zero | Known.One)) 909 return Constant::getIntegerValue(ITy, Known.One); 910 911 // If the right shift operand 0 is a result of a left shift by the same 912 // amount, this is probably a zero/sign extension, which may be unnecessary, 913 // if we do not demand any of the new sign bits. So, return the original 914 // operand instead. 915 const APInt *ShiftRC; 916 const APInt *ShiftLC; 917 Value *X; 918 unsigned BitWidth = DemandedMask.getBitWidth(); 919 if (match(I, 920 m_AShr(m_Shl(m_Value(X), m_APInt(ShiftLC)), m_APInt(ShiftRC))) && 921 ShiftLC == ShiftRC && 922 DemandedMask.isSubsetOf(APInt::getLowBitsSet( 923 BitWidth, BitWidth - ShiftRC->getZExtValue()))) { 924 return X; 925 } 926 927 break; 928 } 929 default: 930 // Compute the Known bits to simplify things downstream. 931 computeKnownBits(I, Known, Depth, CxtI); 932 933 // If this user is only demanding bits that we know, return the known 934 // constant. 935 if (DemandedMask.isSubsetOf(Known.Zero|Known.One)) 936 return Constant::getIntegerValue(ITy, Known.One); 937 938 break; 939 } 940 941 return nullptr; 942 } 943 944 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify 945 /// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into 946 /// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign 947 /// of "C2-C1". 948 /// 949 /// Suppose E1 and E2 are generally different in bits S={bm, bm+1, 950 /// ..., bn}, without considering the specific value X is holding. 951 /// This transformation is legal iff one of following conditions is hold: 952 /// 1) All the bit in S are 0, in this case E1 == E2. 953 /// 2) We don't care those bits in S, per the input DemandedMask. 954 /// 3) Combination of 1) and 2). Some bits in S are 0, and we don't care the 955 /// rest bits. 956 /// 957 /// Currently we only test condition 2). 958 /// 959 /// As with SimplifyDemandedUseBits, it returns NULL if the simplification was 960 /// not successful. 961 Value *InstCombinerImpl::simplifyShrShlDemandedBits( 962 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl, 963 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known) { 964 if (!ShlOp1 || !ShrOp1) 965 return nullptr; // No-op. 966 967 Value *VarX = Shr->getOperand(0); 968 Type *Ty = VarX->getType(); 969 unsigned BitWidth = Ty->getScalarSizeInBits(); 970 if (ShlOp1.uge(BitWidth) || ShrOp1.uge(BitWidth)) 971 return nullptr; // Undef. 972 973 unsigned ShlAmt = ShlOp1.getZExtValue(); 974 unsigned ShrAmt = ShrOp1.getZExtValue(); 975 976 Known.One.clearAllBits(); 977 Known.Zero.setLowBits(ShlAmt - 1); 978 Known.Zero &= DemandedMask; 979 980 APInt BitMask1(APInt::getAllOnesValue(BitWidth)); 981 APInt BitMask2(APInt::getAllOnesValue(BitWidth)); 982 983 bool isLshr = (Shr->getOpcode() == Instruction::LShr); 984 BitMask1 = isLshr ? (BitMask1.lshr(ShrAmt) << ShlAmt) : 985 (BitMask1.ashr(ShrAmt) << ShlAmt); 986 987 if (ShrAmt <= ShlAmt) { 988 BitMask2 <<= (ShlAmt - ShrAmt); 989 } else { 990 BitMask2 = isLshr ? BitMask2.lshr(ShrAmt - ShlAmt): 991 BitMask2.ashr(ShrAmt - ShlAmt); 992 } 993 994 // Check if condition-2 (see the comment to this function) is satified. 995 if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) { 996 if (ShrAmt == ShlAmt) 997 return VarX; 998 999 if (!Shr->hasOneUse()) 1000 return nullptr; 1001 1002 BinaryOperator *New; 1003 if (ShrAmt < ShlAmt) { 1004 Constant *Amt = ConstantInt::get(VarX->getType(), ShlAmt - ShrAmt); 1005 New = BinaryOperator::CreateShl(VarX, Amt); 1006 BinaryOperator *Orig = cast<BinaryOperator>(Shl); 1007 New->setHasNoSignedWrap(Orig->hasNoSignedWrap()); 1008 New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap()); 1009 } else { 1010 Constant *Amt = ConstantInt::get(VarX->getType(), ShrAmt - ShlAmt); 1011 New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) : 1012 BinaryOperator::CreateAShr(VarX, Amt); 1013 if (cast<BinaryOperator>(Shr)->isExact()) 1014 New->setIsExact(true); 1015 } 1016 1017 return InsertNewInstWith(New, *Shl); 1018 } 1019 1020 return nullptr; 1021 } 1022 1023 /// The specified value produces a vector with any number of elements. 1024 /// This method analyzes which elements of the operand are undef or poison and 1025 /// returns that information in UndefElts. 1026 /// 1027 /// DemandedElts contains the set of elements that are actually used by the 1028 /// caller, and by default (AllowMultipleUsers equals false) the value is 1029 /// simplified only if it has a single caller. If AllowMultipleUsers is set 1030 /// to true, DemandedElts refers to the union of sets of elements that are 1031 /// used by all callers. 1032 /// 1033 /// If the information about demanded elements can be used to simplify the 1034 /// operation, the operation is simplified, then the resultant value is 1035 /// returned. This returns null if no change was made. 1036 Value *InstCombinerImpl::SimplifyDemandedVectorElts(Value *V, 1037 APInt DemandedElts, 1038 APInt &UndefElts, 1039 unsigned Depth, 1040 bool AllowMultipleUsers) { 1041 // Cannot analyze scalable type. The number of vector elements is not a 1042 // compile-time constant. 1043 if (isa<ScalableVectorType>(V->getType())) 1044 return nullptr; 1045 1046 unsigned VWidth = cast<FixedVectorType>(V->getType())->getNumElements(); 1047 APInt EltMask(APInt::getAllOnesValue(VWidth)); 1048 assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!"); 1049 1050 if (isa<UndefValue>(V)) { 1051 // If the entire vector is undef or poison, just return this info. 1052 UndefElts = EltMask; 1053 return nullptr; 1054 } 1055 1056 if (DemandedElts.isNullValue()) { // If nothing is demanded, provide poison. 1057 UndefElts = EltMask; 1058 return PoisonValue::get(V->getType()); 1059 } 1060 1061 UndefElts = 0; 1062 1063 if (auto *C = dyn_cast<Constant>(V)) { 1064 // Check if this is identity. If so, return 0 since we are not simplifying 1065 // anything. 1066 if (DemandedElts.isAllOnesValue()) 1067 return nullptr; 1068 1069 Type *EltTy = cast<VectorType>(V->getType())->getElementType(); 1070 Constant *Poison = PoisonValue::get(EltTy); 1071 SmallVector<Constant*, 16> Elts; 1072 for (unsigned i = 0; i != VWidth; ++i) { 1073 if (!DemandedElts[i]) { // If not demanded, set to poison. 1074 Elts.push_back(Poison); 1075 UndefElts.setBit(i); 1076 continue; 1077 } 1078 1079 Constant *Elt = C->getAggregateElement(i); 1080 if (!Elt) return nullptr; 1081 1082 Elts.push_back(Elt); 1083 if (isa<UndefValue>(Elt)) // Already undef or poison. 1084 UndefElts.setBit(i); 1085 } 1086 1087 // If we changed the constant, return it. 1088 Constant *NewCV = ConstantVector::get(Elts); 1089 return NewCV != C ? NewCV : nullptr; 1090 } 1091 1092 // Limit search depth. 1093 if (Depth == 10) 1094 return nullptr; 1095 1096 if (!AllowMultipleUsers) { 1097 // If multiple users are using the root value, proceed with 1098 // simplification conservatively assuming that all elements 1099 // are needed. 1100 if (!V->hasOneUse()) { 1101 // Quit if we find multiple users of a non-root value though. 1102 // They'll be handled when it's their turn to be visited by 1103 // the main instcombine process. 1104 if (Depth != 0) 1105 // TODO: Just compute the UndefElts information recursively. 1106 return nullptr; 1107 1108 // Conservatively assume that all elements are needed. 1109 DemandedElts = EltMask; 1110 } 1111 } 1112 1113 Instruction *I = dyn_cast<Instruction>(V); 1114 if (!I) return nullptr; // Only analyze instructions. 1115 1116 bool MadeChange = false; 1117 auto simplifyAndSetOp = [&](Instruction *Inst, unsigned OpNum, 1118 APInt Demanded, APInt &Undef) { 1119 auto *II = dyn_cast<IntrinsicInst>(Inst); 1120 Value *Op = II ? II->getArgOperand(OpNum) : Inst->getOperand(OpNum); 1121 if (Value *V = SimplifyDemandedVectorElts(Op, Demanded, Undef, Depth + 1)) { 1122 replaceOperand(*Inst, OpNum, V); 1123 MadeChange = true; 1124 } 1125 }; 1126 1127 APInt UndefElts2(VWidth, 0); 1128 APInt UndefElts3(VWidth, 0); 1129 switch (I->getOpcode()) { 1130 default: break; 1131 1132 case Instruction::GetElementPtr: { 1133 // The LangRef requires that struct geps have all constant indices. As 1134 // such, we can't convert any operand to partial undef. 1135 auto mayIndexStructType = [](GetElementPtrInst &GEP) { 1136 for (auto I = gep_type_begin(GEP), E = gep_type_end(GEP); 1137 I != E; I++) 1138 if (I.isStruct()) 1139 return true;; 1140 return false; 1141 }; 1142 if (mayIndexStructType(cast<GetElementPtrInst>(*I))) 1143 break; 1144 1145 // Conservatively track the demanded elements back through any vector 1146 // operands we may have. We know there must be at least one, or we 1147 // wouldn't have a vector result to get here. Note that we intentionally 1148 // merge the undef bits here since gepping with either an undef base or 1149 // index results in undef. 1150 for (unsigned i = 0; i < I->getNumOperands(); i++) { 1151 if (isa<UndefValue>(I->getOperand(i))) { 1152 // If the entire vector is undefined, just return this info. 1153 UndefElts = EltMask; 1154 return nullptr; 1155 } 1156 if (I->getOperand(i)->getType()->isVectorTy()) { 1157 APInt UndefEltsOp(VWidth, 0); 1158 simplifyAndSetOp(I, i, DemandedElts, UndefEltsOp); 1159 UndefElts |= UndefEltsOp; 1160 } 1161 } 1162 1163 break; 1164 } 1165 case Instruction::InsertElement: { 1166 // If this is a variable index, we don't know which element it overwrites. 1167 // demand exactly the same input as we produce. 1168 ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2)); 1169 if (!Idx) { 1170 // Note that we can't propagate undef elt info, because we don't know 1171 // which elt is getting updated. 1172 simplifyAndSetOp(I, 0, DemandedElts, UndefElts2); 1173 break; 1174 } 1175 1176 // The element inserted overwrites whatever was there, so the input demanded 1177 // set is simpler than the output set. 1178 unsigned IdxNo = Idx->getZExtValue(); 1179 APInt PreInsertDemandedElts = DemandedElts; 1180 if (IdxNo < VWidth) 1181 PreInsertDemandedElts.clearBit(IdxNo); 1182 1183 // If we only demand the element that is being inserted and that element 1184 // was extracted from the same index in another vector with the same type, 1185 // replace this insert with that other vector. 1186 // Note: This is attempted before the call to simplifyAndSetOp because that 1187 // may change UndefElts to a value that does not match with Vec. 1188 Value *Vec; 1189 if (PreInsertDemandedElts == 0 && 1190 match(I->getOperand(1), 1191 m_ExtractElt(m_Value(Vec), m_SpecificInt(IdxNo))) && 1192 Vec->getType() == I->getType()) { 1193 return Vec; 1194 } 1195 1196 simplifyAndSetOp(I, 0, PreInsertDemandedElts, UndefElts); 1197 1198 // If this is inserting an element that isn't demanded, remove this 1199 // insertelement. 1200 if (IdxNo >= VWidth || !DemandedElts[IdxNo]) { 1201 Worklist.push(I); 1202 return I->getOperand(0); 1203 } 1204 1205 // The inserted element is defined. 1206 UndefElts.clearBit(IdxNo); 1207 break; 1208 } 1209 case Instruction::ShuffleVector: { 1210 auto *Shuffle = cast<ShuffleVectorInst>(I); 1211 assert(Shuffle->getOperand(0)->getType() == 1212 Shuffle->getOperand(1)->getType() && 1213 "Expected shuffle operands to have same type"); 1214 unsigned OpWidth = cast<FixedVectorType>(Shuffle->getOperand(0)->getType()) 1215 ->getNumElements(); 1216 // Handle trivial case of a splat. Only check the first element of LHS 1217 // operand. 1218 if (all_of(Shuffle->getShuffleMask(), [](int Elt) { return Elt == 0; }) && 1219 DemandedElts.isAllOnesValue()) { 1220 if (!isa<UndefValue>(I->getOperand(1))) { 1221 I->setOperand(1, UndefValue::get(I->getOperand(1)->getType())); 1222 MadeChange = true; 1223 } 1224 APInt LeftDemanded(OpWidth, 1); 1225 APInt LHSUndefElts(OpWidth, 0); 1226 simplifyAndSetOp(I, 0, LeftDemanded, LHSUndefElts); 1227 if (LHSUndefElts[0]) 1228 UndefElts = EltMask; 1229 else 1230 UndefElts.clearAllBits(); 1231 break; 1232 } 1233 1234 APInt LeftDemanded(OpWidth, 0), RightDemanded(OpWidth, 0); 1235 for (unsigned i = 0; i < VWidth; i++) { 1236 if (DemandedElts[i]) { 1237 unsigned MaskVal = Shuffle->getMaskValue(i); 1238 if (MaskVal != -1u) { 1239 assert(MaskVal < OpWidth * 2 && 1240 "shufflevector mask index out of range!"); 1241 if (MaskVal < OpWidth) 1242 LeftDemanded.setBit(MaskVal); 1243 else 1244 RightDemanded.setBit(MaskVal - OpWidth); 1245 } 1246 } 1247 } 1248 1249 APInt LHSUndefElts(OpWidth, 0); 1250 simplifyAndSetOp(I, 0, LeftDemanded, LHSUndefElts); 1251 1252 APInt RHSUndefElts(OpWidth, 0); 1253 simplifyAndSetOp(I, 1, RightDemanded, RHSUndefElts); 1254 1255 // If this shuffle does not change the vector length and the elements 1256 // demanded by this shuffle are an identity mask, then this shuffle is 1257 // unnecessary. 1258 // 1259 // We are assuming canonical form for the mask, so the source vector is 1260 // operand 0 and operand 1 is not used. 1261 // 1262 // Note that if an element is demanded and this shuffle mask is undefined 1263 // for that element, then the shuffle is not considered an identity 1264 // operation. The shuffle prevents poison from the operand vector from 1265 // leaking to the result by replacing poison with an undefined value. 1266 if (VWidth == OpWidth) { 1267 bool IsIdentityShuffle = true; 1268 for (unsigned i = 0; i < VWidth; i++) { 1269 unsigned MaskVal = Shuffle->getMaskValue(i); 1270 if (DemandedElts[i] && i != MaskVal) { 1271 IsIdentityShuffle = false; 1272 break; 1273 } 1274 } 1275 if (IsIdentityShuffle) 1276 return Shuffle->getOperand(0); 1277 } 1278 1279 bool NewUndefElts = false; 1280 unsigned LHSIdx = -1u, LHSValIdx = -1u; 1281 unsigned RHSIdx = -1u, RHSValIdx = -1u; 1282 bool LHSUniform = true; 1283 bool RHSUniform = true; 1284 for (unsigned i = 0; i < VWidth; i++) { 1285 unsigned MaskVal = Shuffle->getMaskValue(i); 1286 if (MaskVal == -1u) { 1287 UndefElts.setBit(i); 1288 } else if (!DemandedElts[i]) { 1289 NewUndefElts = true; 1290 UndefElts.setBit(i); 1291 } else if (MaskVal < OpWidth) { 1292 if (LHSUndefElts[MaskVal]) { 1293 NewUndefElts = true; 1294 UndefElts.setBit(i); 1295 } else { 1296 LHSIdx = LHSIdx == -1u ? i : OpWidth; 1297 LHSValIdx = LHSValIdx == -1u ? MaskVal : OpWidth; 1298 LHSUniform = LHSUniform && (MaskVal == i); 1299 } 1300 } else { 1301 if (RHSUndefElts[MaskVal - OpWidth]) { 1302 NewUndefElts = true; 1303 UndefElts.setBit(i); 1304 } else { 1305 RHSIdx = RHSIdx == -1u ? i : OpWidth; 1306 RHSValIdx = RHSValIdx == -1u ? MaskVal - OpWidth : OpWidth; 1307 RHSUniform = RHSUniform && (MaskVal - OpWidth == i); 1308 } 1309 } 1310 } 1311 1312 // Try to transform shuffle with constant vector and single element from 1313 // this constant vector to single insertelement instruction. 1314 // shufflevector V, C, <v1, v2, .., ci, .., vm> -> 1315 // insertelement V, C[ci], ci-n 1316 if (OpWidth == 1317 cast<FixedVectorType>(Shuffle->getType())->getNumElements()) { 1318 Value *Op = nullptr; 1319 Constant *Value = nullptr; 1320 unsigned Idx = -1u; 1321 1322 // Find constant vector with the single element in shuffle (LHS or RHS). 1323 if (LHSIdx < OpWidth && RHSUniform) { 1324 if (auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(0))) { 1325 Op = Shuffle->getOperand(1); 1326 Value = CV->getOperand(LHSValIdx); 1327 Idx = LHSIdx; 1328 } 1329 } 1330 if (RHSIdx < OpWidth && LHSUniform) { 1331 if (auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(1))) { 1332 Op = Shuffle->getOperand(0); 1333 Value = CV->getOperand(RHSValIdx); 1334 Idx = RHSIdx; 1335 } 1336 } 1337 // Found constant vector with single element - convert to insertelement. 1338 if (Op && Value) { 1339 Instruction *New = InsertElementInst::Create( 1340 Op, Value, ConstantInt::get(Type::getInt32Ty(I->getContext()), Idx), 1341 Shuffle->getName()); 1342 InsertNewInstWith(New, *Shuffle); 1343 return New; 1344 } 1345 } 1346 if (NewUndefElts) { 1347 // Add additional discovered undefs. 1348 SmallVector<int, 16> Elts; 1349 for (unsigned i = 0; i < VWidth; ++i) { 1350 if (UndefElts[i]) 1351 Elts.push_back(UndefMaskElem); 1352 else 1353 Elts.push_back(Shuffle->getMaskValue(i)); 1354 } 1355 Shuffle->setShuffleMask(Elts); 1356 MadeChange = true; 1357 } 1358 break; 1359 } 1360 case Instruction::Select: { 1361 // If this is a vector select, try to transform the select condition based 1362 // on the current demanded elements. 1363 SelectInst *Sel = cast<SelectInst>(I); 1364 if (Sel->getCondition()->getType()->isVectorTy()) { 1365 // TODO: We are not doing anything with UndefElts based on this call. 1366 // It is overwritten below based on the other select operands. If an 1367 // element of the select condition is known undef, then we are free to 1368 // choose the output value from either arm of the select. If we know that 1369 // one of those values is undef, then the output can be undef. 1370 simplifyAndSetOp(I, 0, DemandedElts, UndefElts); 1371 } 1372 1373 // Next, see if we can transform the arms of the select. 1374 APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts); 1375 if (auto *CV = dyn_cast<ConstantVector>(Sel->getCondition())) { 1376 for (unsigned i = 0; i < VWidth; i++) { 1377 // isNullValue() always returns false when called on a ConstantExpr. 1378 // Skip constant expressions to avoid propagating incorrect information. 1379 Constant *CElt = CV->getAggregateElement(i); 1380 if (isa<ConstantExpr>(CElt)) 1381 continue; 1382 // TODO: If a select condition element is undef, we can demand from 1383 // either side. If one side is known undef, choosing that side would 1384 // propagate undef. 1385 if (CElt->isNullValue()) 1386 DemandedLHS.clearBit(i); 1387 else 1388 DemandedRHS.clearBit(i); 1389 } 1390 } 1391 1392 simplifyAndSetOp(I, 1, DemandedLHS, UndefElts2); 1393 simplifyAndSetOp(I, 2, DemandedRHS, UndefElts3); 1394 1395 // Output elements are undefined if the element from each arm is undefined. 1396 // TODO: This can be improved. See comment in select condition handling. 1397 UndefElts = UndefElts2 & UndefElts3; 1398 break; 1399 } 1400 case Instruction::BitCast: { 1401 // Vector->vector casts only. 1402 VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType()); 1403 if (!VTy) break; 1404 unsigned InVWidth = cast<FixedVectorType>(VTy)->getNumElements(); 1405 APInt InputDemandedElts(InVWidth, 0); 1406 UndefElts2 = APInt(InVWidth, 0); 1407 unsigned Ratio; 1408 1409 if (VWidth == InVWidth) { 1410 // If we are converting from <4 x i32> -> <4 x f32>, we demand the same 1411 // elements as are demanded of us. 1412 Ratio = 1; 1413 InputDemandedElts = DemandedElts; 1414 } else if ((VWidth % InVWidth) == 0) { 1415 // If the number of elements in the output is a multiple of the number of 1416 // elements in the input then an input element is live if any of the 1417 // corresponding output elements are live. 1418 Ratio = VWidth / InVWidth; 1419 for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) 1420 if (DemandedElts[OutIdx]) 1421 InputDemandedElts.setBit(OutIdx / Ratio); 1422 } else if ((InVWidth % VWidth) == 0) { 1423 // If the number of elements in the input is a multiple of the number of 1424 // elements in the output then an input element is live if the 1425 // corresponding output element is live. 1426 Ratio = InVWidth / VWidth; 1427 for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) 1428 if (DemandedElts[InIdx / Ratio]) 1429 InputDemandedElts.setBit(InIdx); 1430 } else { 1431 // Unsupported so far. 1432 break; 1433 } 1434 1435 simplifyAndSetOp(I, 0, InputDemandedElts, UndefElts2); 1436 1437 if (VWidth == InVWidth) { 1438 UndefElts = UndefElts2; 1439 } else if ((VWidth % InVWidth) == 0) { 1440 // If the number of elements in the output is a multiple of the number of 1441 // elements in the input then an output element is undef if the 1442 // corresponding input element is undef. 1443 for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) 1444 if (UndefElts2[OutIdx / Ratio]) 1445 UndefElts.setBit(OutIdx); 1446 } else if ((InVWidth % VWidth) == 0) { 1447 // If the number of elements in the input is a multiple of the number of 1448 // elements in the output then an output element is undef if all of the 1449 // corresponding input elements are undef. 1450 for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) { 1451 APInt SubUndef = UndefElts2.lshr(OutIdx * Ratio).zextOrTrunc(Ratio); 1452 if (SubUndef.countPopulation() == Ratio) 1453 UndefElts.setBit(OutIdx); 1454 } 1455 } else { 1456 llvm_unreachable("Unimp"); 1457 } 1458 break; 1459 } 1460 case Instruction::FPTrunc: 1461 case Instruction::FPExt: 1462 simplifyAndSetOp(I, 0, DemandedElts, UndefElts); 1463 break; 1464 1465 case Instruction::Call: { 1466 IntrinsicInst *II = dyn_cast<IntrinsicInst>(I); 1467 if (!II) break; 1468 switch (II->getIntrinsicID()) { 1469 case Intrinsic::masked_gather: // fallthrough 1470 case Intrinsic::masked_load: { 1471 // Subtlety: If we load from a pointer, the pointer must be valid 1472 // regardless of whether the element is demanded. Doing otherwise risks 1473 // segfaults which didn't exist in the original program. 1474 APInt DemandedPtrs(APInt::getAllOnesValue(VWidth)), 1475 DemandedPassThrough(DemandedElts); 1476 if (auto *CV = dyn_cast<ConstantVector>(II->getOperand(2))) 1477 for (unsigned i = 0; i < VWidth; i++) { 1478 Constant *CElt = CV->getAggregateElement(i); 1479 if (CElt->isNullValue()) 1480 DemandedPtrs.clearBit(i); 1481 else if (CElt->isAllOnesValue()) 1482 DemandedPassThrough.clearBit(i); 1483 } 1484 if (II->getIntrinsicID() == Intrinsic::masked_gather) 1485 simplifyAndSetOp(II, 0, DemandedPtrs, UndefElts2); 1486 simplifyAndSetOp(II, 3, DemandedPassThrough, UndefElts3); 1487 1488 // Output elements are undefined if the element from both sources are. 1489 // TODO: can strengthen via mask as well. 1490 UndefElts = UndefElts2 & UndefElts3; 1491 break; 1492 } 1493 default: { 1494 // Handle target specific intrinsics 1495 Optional<Value *> V = targetSimplifyDemandedVectorEltsIntrinsic( 1496 *II, DemandedElts, UndefElts, UndefElts2, UndefElts3, 1497 simplifyAndSetOp); 1498 if (V.hasValue()) 1499 return V.getValue(); 1500 break; 1501 } 1502 } // switch on IntrinsicID 1503 break; 1504 } // case Call 1505 } // switch on Opcode 1506 1507 // TODO: We bail completely on integer div/rem and shifts because they have 1508 // UB/poison potential, but that should be refined. 1509 BinaryOperator *BO; 1510 if (match(I, m_BinOp(BO)) && !BO->isIntDivRem() && !BO->isShift()) { 1511 simplifyAndSetOp(I, 0, DemandedElts, UndefElts); 1512 simplifyAndSetOp(I, 1, DemandedElts, UndefElts2); 1513 1514 // Any change to an instruction with potential poison must clear those flags 1515 // because we can not guarantee those constraints now. Other analysis may 1516 // determine that it is safe to re-apply the flags. 1517 if (MadeChange) 1518 BO->dropPoisonGeneratingFlags(); 1519 1520 // Output elements are undefined if both are undefined. Consider things 1521 // like undef & 0. The result is known zero, not undef. 1522 UndefElts &= UndefElts2; 1523 } 1524 1525 // If we've proven all of the lanes undef, return an undef value. 1526 // TODO: Intersect w/demanded lanes 1527 if (UndefElts.isAllOnesValue()) 1528 return UndefValue::get(I->getType());; 1529 1530 return MadeChange ? I : nullptr; 1531 } 1532