1202375Srdivacky//===- InstCombineSimplifyDemanded.cpp ------------------------------------===// 2202375Srdivacky// 3202375Srdivacky// The LLVM Compiler Infrastructure 4202375Srdivacky// 5202375Srdivacky// This file is distributed under the University of Illinois Open Source 6202375Srdivacky// License. See LICENSE.TXT for details. 7202375Srdivacky// 8202375Srdivacky//===----------------------------------------------------------------------===// 9202375Srdivacky// 10202375Srdivacky// This file contains logic for simplifying instructions based on information 11202375Srdivacky// about how they are used. 12202375Srdivacky// 13202375Srdivacky//===----------------------------------------------------------------------===// 14202375Srdivacky 15288943Sdim#include "InstCombineInternal.h" 16288943Sdim#include "llvm/Analysis/ValueTracking.h" 17249423Sdim#include "llvm/IR/IntrinsicInst.h" 18276479Sdim#include "llvm/IR/PatternMatch.h" 19202375Srdivacky 20202375Srdivackyusing namespace llvm; 21249423Sdimusing namespace llvm::PatternMatch; 22202375Srdivacky 23276479Sdim#define DEBUG_TYPE "instcombine" 24276479Sdim 25249423Sdim/// ShrinkDemandedConstant - Check to see if the specified operand of the 26202375Srdivacky/// specified instruction is a constant integer. If so, check to see if there 27202375Srdivacky/// are any bits set in the constant that are not demanded. If so, shrink the 28202375Srdivacky/// constant and return true. 29249423Sdimstatic bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo, 30202375Srdivacky APInt Demanded) { 31202375Srdivacky assert(I && "No instruction?"); 32202375Srdivacky assert(OpNo < I->getNumOperands() && "Operand index too large"); 33202375Srdivacky 34202375Srdivacky // If the operand is not a constant integer, nothing to do. 35202375Srdivacky ConstantInt *OpC = dyn_cast<ConstantInt>(I->getOperand(OpNo)); 36202375Srdivacky if (!OpC) return false; 37202375Srdivacky 38202375Srdivacky // If there are no bits set that aren't demanded, nothing to do. 39218893Sdim Demanded = Demanded.zextOrTrunc(OpC->getValue().getBitWidth()); 40202375Srdivacky if ((~Demanded & OpC->getValue()) == 0) 41202375Srdivacky return false; 42202375Srdivacky 43202375Srdivacky // This instruction is producing bits that are not demanded. Shrink the RHS. 44202375Srdivacky Demanded &= OpC->getValue(); 45202375Srdivacky I->setOperand(OpNo, ConstantInt::get(OpC->getType(), Demanded)); 46280031Sdim 47202375Srdivacky return true; 48202375Srdivacky} 49202375Srdivacky 50202375Srdivacky 51202375Srdivacky 52202375Srdivacky/// SimplifyDemandedInstructionBits - Inst is an integer instruction that 53202375Srdivacky/// SimplifyDemandedBits knows about. See if the instruction has any 54202375Srdivacky/// properties that allow us to simplify its operands. 55202375Srdivackybool InstCombiner::SimplifyDemandedInstructionBits(Instruction &Inst) { 56202375Srdivacky unsigned BitWidth = Inst.getType()->getScalarSizeInBits(); 57202375Srdivacky APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 58202375Srdivacky APInt DemandedMask(APInt::getAllOnesValue(BitWidth)); 59249423Sdim 60288943Sdim Value *V = SimplifyDemandedUseBits(&Inst, DemandedMask, KnownZero, KnownOne, 61288943Sdim 0, &Inst); 62276479Sdim if (!V) return false; 63202375Srdivacky if (V == &Inst) return true; 64202375Srdivacky ReplaceInstUsesWith(Inst, V); 65202375Srdivacky return true; 66202375Srdivacky} 67202375Srdivacky 68202375Srdivacky/// SimplifyDemandedBits - This form of SimplifyDemandedBits simplifies the 69202375Srdivacky/// specified instruction operand if possible, updating it in place. It returns 70202375Srdivacky/// true if it made any change and false otherwise. 71249423Sdimbool InstCombiner::SimplifyDemandedBits(Use &U, APInt DemandedMask, 72202375Srdivacky APInt &KnownZero, APInt &KnownOne, 73202375Srdivacky unsigned Depth) { 74288943Sdim auto *UserI = dyn_cast<Instruction>(U.getUser()); 75288943Sdim Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask, KnownZero, 76288943Sdim KnownOne, Depth, UserI); 77276479Sdim if (!NewVal) return false; 78202375Srdivacky U = NewVal; 79202375Srdivacky return true; 80202375Srdivacky} 81202375Srdivacky 82202375Srdivacky 83202375Srdivacky/// SimplifyDemandedUseBits - This function attempts to replace V with a simpler 84202375Srdivacky/// value based on the demanded bits. When this function is called, it is known 85202375Srdivacky/// that only the bits set in DemandedMask of the result of V are ever used 86202375Srdivacky/// downstream. Consequently, depending on the mask and V, it may be possible 87202375Srdivacky/// to replace V with a constant or one of its operands. In such cases, this 88202375Srdivacky/// function does the replacement and returns true. In all other cases, it 89202375Srdivacky/// returns false after analyzing the expression and setting KnownOne and known 90202375Srdivacky/// to be one in the expression. KnownZero contains all the bits that are known 91202375Srdivacky/// to be zero in the expression. These are provided to potentially allow the 92202375Srdivacky/// caller (which might recursively be SimplifyDemandedBits itself) to simplify 93249423Sdim/// the expression. KnownOne and KnownZero always follow the invariant that 94202375Srdivacky/// KnownOne & KnownZero == 0. That is, a bit can't be both 1 and 0. Note that 95202375Srdivacky/// the bits in KnownOne and KnownZero may only be accurate for those bits set 96202375Srdivacky/// in DemandedMask. Note also that the bitwidth of V, DemandedMask, KnownZero 97202375Srdivacky/// and KnownOne must all be the same. 98202375Srdivacky/// 99202375Srdivacky/// This returns null if it did not change anything and it permits no 100202375Srdivacky/// simplification. This returns V itself if it did some simplification of V's 101202375Srdivacky/// operands based on the information about what bits are demanded. This returns 102202375Srdivacky/// some other non-null value if it found out that V is equal to another value 103202375Srdivacky/// in the context where the specified bits are demanded, but not for all users. 104202375SrdivackyValue *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, 105202375Srdivacky APInt &KnownZero, APInt &KnownOne, 106280031Sdim unsigned Depth, 107280031Sdim Instruction *CxtI) { 108276479Sdim assert(V != nullptr && "Null pointer of Value???"); 109202375Srdivacky assert(Depth <= 6 && "Limit Search Depth"); 110202375Srdivacky uint32_t BitWidth = DemandedMask.getBitWidth(); 111226633Sdim Type *VTy = V->getType(); 112288943Sdim assert( 113288943Sdim (!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) && 114288943Sdim KnownZero.getBitWidth() == BitWidth && 115288943Sdim KnownOne.getBitWidth() == BitWidth && 116288943Sdim "Value *V, DemandedMask, KnownZero and KnownOne " 117288943Sdim "must have same BitWidth"); 118202375Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 119202375Srdivacky // We know all of the bits for a constant! 120202375Srdivacky KnownOne = CI->getValue() & DemandedMask; 121202375Srdivacky KnownZero = ~KnownOne & DemandedMask; 122276479Sdim return nullptr; 123202375Srdivacky } 124202375Srdivacky if (isa<ConstantPointerNull>(V)) { 125202375Srdivacky // We know all of the bits for a constant! 126218893Sdim KnownOne.clearAllBits(); 127202375Srdivacky KnownZero = DemandedMask; 128276479Sdim return nullptr; 129202375Srdivacky } 130202375Srdivacky 131218893Sdim KnownZero.clearAllBits(); 132218893Sdim KnownOne.clearAllBits(); 133202375Srdivacky if (DemandedMask == 0) { // Not demanding any bits from V. 134202375Srdivacky if (isa<UndefValue>(V)) 135276479Sdim return nullptr; 136202375Srdivacky return UndefValue::get(VTy); 137202375Srdivacky } 138249423Sdim 139202375Srdivacky if (Depth == 6) // Limit search depth. 140276479Sdim return nullptr; 141249423Sdim 142202375Srdivacky APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 143203954Srdivacky APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); 144202375Srdivacky 145202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 146202375Srdivacky if (!I) { 147280031Sdim computeKnownBits(V, KnownZero, KnownOne, Depth, CxtI); 148276479Sdim return nullptr; // Only analyze instructions. 149202375Srdivacky } 150202375Srdivacky 151202375Srdivacky // If there are multiple uses of this value and we aren't at the root, then 152202375Srdivacky // we can't do any simplifications of the operands, because DemandedMask 153202375Srdivacky // only reflects the bits demanded by *one* of the users. 154202375Srdivacky if (Depth != 0 && !I->hasOneUse()) { 155202375Srdivacky // Despite the fact that we can't simplify this instruction in all User's 156202375Srdivacky // context, we can at least compute the knownzero/knownone bits, and we can 157202375Srdivacky // do simplifications that apply to *just* the one user if we know that 158202375Srdivacky // this instruction has a simpler value in that context. 159202375Srdivacky if (I->getOpcode() == Instruction::And) { 160202375Srdivacky // If either the LHS or the RHS are Zero, the result is zero. 161288943Sdim computeKnownBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth + 1, 162280031Sdim CxtI); 163288943Sdim computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth + 1, 164280031Sdim CxtI); 165249423Sdim 166202375Srdivacky // If all of the demanded bits are known 1 on one side, return the other. 167202375Srdivacky // These bits cannot contribute to the result of the 'and' in this 168202375Srdivacky // context. 169249423Sdim if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == 170202375Srdivacky (DemandedMask & ~LHSKnownZero)) 171202375Srdivacky return I->getOperand(0); 172249423Sdim if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == 173202375Srdivacky (DemandedMask & ~RHSKnownZero)) 174202375Srdivacky return I->getOperand(1); 175249423Sdim 176202375Srdivacky // If all of the demanded bits in the inputs are known zeros, return zero. 177202375Srdivacky if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) 178202375Srdivacky return Constant::getNullValue(VTy); 179249423Sdim 180202375Srdivacky } else if (I->getOpcode() == Instruction::Or) { 181202375Srdivacky // We can simplify (X|Y) -> X or Y in the user's context if we know that 182202375Srdivacky // only bits from X or Y are demanded. 183249423Sdim 184202375Srdivacky // If either the LHS or the RHS are One, the result is One. 185288943Sdim computeKnownBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth + 1, 186280031Sdim CxtI); 187288943Sdim computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth + 1, 188280031Sdim CxtI); 189249423Sdim 190202375Srdivacky // If all of the demanded bits are known zero on one side, return the 191202375Srdivacky // other. These bits cannot contribute to the result of the 'or' in this 192202375Srdivacky // context. 193249423Sdim if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == 194202375Srdivacky (DemandedMask & ~LHSKnownOne)) 195202375Srdivacky return I->getOperand(0); 196249423Sdim if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == 197202375Srdivacky (DemandedMask & ~RHSKnownOne)) 198202375Srdivacky return I->getOperand(1); 199249423Sdim 200202375Srdivacky // If all of the potentially set bits on one side are known to be set on 201202375Srdivacky // the other side, just use the 'other' side. 202249423Sdim if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == 203202375Srdivacky (DemandedMask & (~RHSKnownZero))) 204202375Srdivacky return I->getOperand(0); 205249423Sdim if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == 206202375Srdivacky (DemandedMask & (~LHSKnownZero))) 207202375Srdivacky return I->getOperand(1); 208249423Sdim } else if (I->getOpcode() == Instruction::Xor) { 209249423Sdim // We can simplify (X^Y) -> X or Y in the user's context if we know that 210249423Sdim // only bits from X or Y are demanded. 211249423Sdim 212288943Sdim computeKnownBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth + 1, 213280031Sdim CxtI); 214288943Sdim computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth + 1, 215280031Sdim CxtI); 216249423Sdim 217249423Sdim // If all of the demanded bits are known zero on one side, return the 218249423Sdim // other. 219249423Sdim if ((DemandedMask & RHSKnownZero) == DemandedMask) 220249423Sdim return I->getOperand(0); 221249423Sdim if ((DemandedMask & LHSKnownZero) == DemandedMask) 222249423Sdim return I->getOperand(1); 223202375Srdivacky } 224249423Sdim 225202375Srdivacky // Compute the KnownZero/KnownOne bits to simplify things downstream. 226280031Sdim computeKnownBits(I, KnownZero, KnownOne, Depth, CxtI); 227276479Sdim return nullptr; 228202375Srdivacky } 229249423Sdim 230202375Srdivacky // If this is the root being simplified, allow it to have multiple uses, 231202375Srdivacky // just set the DemandedMask to all bits so that we can try to simplify the 232202375Srdivacky // operands. This allows visitTruncInst (for example) to simplify the 233202375Srdivacky // operand of a trunc without duplicating all the logic below. 234202375Srdivacky if (Depth == 0 && !V->hasOneUse()) 235202375Srdivacky DemandedMask = APInt::getAllOnesValue(BitWidth); 236249423Sdim 237202375Srdivacky switch (I->getOpcode()) { 238202375Srdivacky default: 239280031Sdim computeKnownBits(I, KnownZero, KnownOne, Depth, CxtI); 240202375Srdivacky break; 241202375Srdivacky case Instruction::And: 242202375Srdivacky // If either the LHS or the RHS are Zero, the result is zero. 243288943Sdim if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, RHSKnownZero, 244288943Sdim RHSKnownOne, Depth + 1) || 245202375Srdivacky SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownZero, 246288943Sdim LHSKnownZero, LHSKnownOne, Depth + 1)) 247202375Srdivacky return I; 248249423Sdim assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 249249423Sdim assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 250202375Srdivacky 251280031Sdim // If the client is only demanding bits that we know, return the known 252280031Sdim // constant. 253280031Sdim if ((DemandedMask & ((RHSKnownZero | LHSKnownZero)| 254280031Sdim (RHSKnownOne & LHSKnownOne))) == DemandedMask) 255280031Sdim return Constant::getIntegerValue(VTy, RHSKnownOne & LHSKnownOne); 256280031Sdim 257202375Srdivacky // If all of the demanded bits are known 1 on one side, return the other. 258202375Srdivacky // These bits cannot contribute to the result of the 'and'. 259249423Sdim if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == 260202375Srdivacky (DemandedMask & ~LHSKnownZero)) 261202375Srdivacky return I->getOperand(0); 262249423Sdim if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == 263202375Srdivacky (DemandedMask & ~RHSKnownZero)) 264202375Srdivacky return I->getOperand(1); 265249423Sdim 266202375Srdivacky // If all of the demanded bits in the inputs are known zeros, return zero. 267202375Srdivacky if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) 268202375Srdivacky return Constant::getNullValue(VTy); 269249423Sdim 270202375Srdivacky // If the RHS is a constant, see if we can simplify it. 271202375Srdivacky if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnownZero)) 272202375Srdivacky return I; 273249423Sdim 274202375Srdivacky // Output known-1 bits are only known if set in both the LHS & RHS. 275203954Srdivacky KnownOne = RHSKnownOne & LHSKnownOne; 276202375Srdivacky // Output known-0 are known to be clear if zero in either the LHS | RHS. 277203954Srdivacky KnownZero = RHSKnownZero | LHSKnownZero; 278202375Srdivacky break; 279202375Srdivacky case Instruction::Or: 280202375Srdivacky // If either the LHS or the RHS are One, the result is One. 281288943Sdim if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, RHSKnownZero, 282288943Sdim RHSKnownOne, Depth + 1) || 283249423Sdim SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownOne, 284288943Sdim LHSKnownZero, LHSKnownOne, Depth + 1)) 285202375Srdivacky return I; 286249423Sdim assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 287249423Sdim assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 288249423Sdim 289280031Sdim // If the client is only demanding bits that we know, return the known 290280031Sdim // constant. 291280031Sdim if ((DemandedMask & ((RHSKnownZero & LHSKnownZero)| 292280031Sdim (RHSKnownOne | LHSKnownOne))) == DemandedMask) 293280031Sdim return Constant::getIntegerValue(VTy, RHSKnownOne | LHSKnownOne); 294280031Sdim 295202375Srdivacky // If all of the demanded bits are known zero on one side, return the other. 296202375Srdivacky // These bits cannot contribute to the result of the 'or'. 297249423Sdim if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == 298202375Srdivacky (DemandedMask & ~LHSKnownOne)) 299202375Srdivacky return I->getOperand(0); 300249423Sdim if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == 301202375Srdivacky (DemandedMask & ~RHSKnownOne)) 302202375Srdivacky return I->getOperand(1); 303202375Srdivacky 304202375Srdivacky // If all of the potentially set bits on one side are known to be set on 305202375Srdivacky // the other side, just use the 'other' side. 306249423Sdim if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == 307202375Srdivacky (DemandedMask & (~RHSKnownZero))) 308202375Srdivacky return I->getOperand(0); 309249423Sdim if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == 310202375Srdivacky (DemandedMask & (~LHSKnownZero))) 311202375Srdivacky return I->getOperand(1); 312249423Sdim 313202375Srdivacky // If the RHS is a constant, see if we can simplify it. 314202375Srdivacky if (ShrinkDemandedConstant(I, 1, DemandedMask)) 315202375Srdivacky return I; 316249423Sdim 317202375Srdivacky // Output known-0 bits are only known if clear in both the LHS & RHS. 318203954Srdivacky KnownZero = RHSKnownZero & LHSKnownZero; 319202375Srdivacky // Output known-1 are known to be set if set in either the LHS | RHS. 320203954Srdivacky KnownOne = RHSKnownOne | LHSKnownOne; 321202375Srdivacky break; 322202375Srdivacky case Instruction::Xor: { 323288943Sdim if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, RHSKnownZero, 324288943Sdim RHSKnownOne, Depth + 1) || 325288943Sdim SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, LHSKnownZero, 326288943Sdim LHSKnownOne, Depth + 1)) 327202375Srdivacky return I; 328249423Sdim assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 329249423Sdim assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 330249423Sdim 331280031Sdim // Output known-0 bits are known if clear or set in both the LHS & RHS. 332280031Sdim APInt IKnownZero = (RHSKnownZero & LHSKnownZero) | 333280031Sdim (RHSKnownOne & LHSKnownOne); 334280031Sdim // Output known-1 are known to be set if set in only one of the LHS, RHS. 335280031Sdim APInt IKnownOne = (RHSKnownZero & LHSKnownOne) | 336280031Sdim (RHSKnownOne & LHSKnownZero); 337280031Sdim 338280031Sdim // If the client is only demanding bits that we know, return the known 339280031Sdim // constant. 340280031Sdim if ((DemandedMask & (IKnownZero|IKnownOne)) == DemandedMask) 341280031Sdim return Constant::getIntegerValue(VTy, IKnownOne); 342280031Sdim 343202375Srdivacky // If all of the demanded bits are known zero on one side, return the other. 344202375Srdivacky // These bits cannot contribute to the result of the 'xor'. 345202375Srdivacky if ((DemandedMask & RHSKnownZero) == DemandedMask) 346202375Srdivacky return I->getOperand(0); 347202375Srdivacky if ((DemandedMask & LHSKnownZero) == DemandedMask) 348202375Srdivacky return I->getOperand(1); 349249423Sdim 350202375Srdivacky // If all of the demanded bits are known to be zero on one side or the 351202375Srdivacky // other, turn this into an *inclusive* or. 352202375Srdivacky // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 353202375Srdivacky if ((DemandedMask & ~RHSKnownZero & ~LHSKnownZero) == 0) { 354249423Sdim Instruction *Or = 355202375Srdivacky BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1), 356202375Srdivacky I->getName()); 357223017Sdim return InsertNewInstWith(Or, *I); 358202375Srdivacky } 359249423Sdim 360202375Srdivacky // If all of the demanded bits on one side are known, and all of the set 361202375Srdivacky // bits on that side are also known to be set on the other side, turn this 362202375Srdivacky // into an AND, as we know the bits will be cleared. 363202375Srdivacky // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 364249423Sdim if ((DemandedMask & (RHSKnownZero|RHSKnownOne)) == DemandedMask) { 365202375Srdivacky // all known 366202375Srdivacky if ((RHSKnownOne & LHSKnownOne) == RHSKnownOne) { 367202375Srdivacky Constant *AndC = Constant::getIntegerValue(VTy, 368202375Srdivacky ~RHSKnownOne & DemandedMask); 369226633Sdim Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 370223017Sdim return InsertNewInstWith(And, *I); 371202375Srdivacky } 372202375Srdivacky } 373249423Sdim 374202375Srdivacky // If the RHS is a constant, see if we can simplify it. 375202375Srdivacky // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1. 376202375Srdivacky if (ShrinkDemandedConstant(I, 1, DemandedMask)) 377202375Srdivacky return I; 378249423Sdim 379202375Srdivacky // If our LHS is an 'and' and if it has one use, and if any of the bits we 380202375Srdivacky // are flipping are known to be set, then the xor is just resetting those 381202375Srdivacky // bits to zero. We can just knock out bits from the 'and' and the 'xor', 382202375Srdivacky // simplifying both of them. 383202375Srdivacky if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0))) 384202375Srdivacky if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() && 385202375Srdivacky isa<ConstantInt>(I->getOperand(1)) && 386202375Srdivacky isa<ConstantInt>(LHSInst->getOperand(1)) && 387202375Srdivacky (LHSKnownOne & RHSKnownOne & DemandedMask) != 0) { 388202375Srdivacky ConstantInt *AndRHS = cast<ConstantInt>(LHSInst->getOperand(1)); 389202375Srdivacky ConstantInt *XorRHS = cast<ConstantInt>(I->getOperand(1)); 390202375Srdivacky APInt NewMask = ~(LHSKnownOne & RHSKnownOne & DemandedMask); 391249423Sdim 392202375Srdivacky Constant *AndC = 393202375Srdivacky ConstantInt::get(I->getType(), NewMask & AndRHS->getValue()); 394226633Sdim Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 395223017Sdim InsertNewInstWith(NewAnd, *I); 396249423Sdim 397202375Srdivacky Constant *XorC = 398202375Srdivacky ConstantInt::get(I->getType(), NewMask & XorRHS->getValue()); 399226633Sdim Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC); 400223017Sdim return InsertNewInstWith(NewXor, *I); 401202375Srdivacky } 402203954Srdivacky 403203954Srdivacky // Output known-0 bits are known if clear or set in both the LHS & RHS. 404203954Srdivacky KnownZero= (RHSKnownZero & LHSKnownZero) | (RHSKnownOne & LHSKnownOne); 405203954Srdivacky // Output known-1 are known to be set if set in only one of the LHS, RHS. 406203954Srdivacky KnownOne = (RHSKnownZero & LHSKnownOne) | (RHSKnownOne & LHSKnownZero); 407202375Srdivacky break; 408202375Srdivacky } 409202375Srdivacky case Instruction::Select: 410288943Sdim // If this is a select as part of a min/max pattern, don't simplify any 411288943Sdim // further in case we break the structure. 412288943Sdim Value *LHS, *RHS; 413296417Sdim if (matchSelectPattern(I, LHS, RHS).Flavor != SPF_UNKNOWN) 414288943Sdim return nullptr; 415296417Sdim 416288943Sdim if (SimplifyDemandedBits(I->getOperandUse(2), DemandedMask, RHSKnownZero, 417288943Sdim RHSKnownOne, Depth + 1) || 418288943Sdim SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, LHSKnownZero, 419288943Sdim LHSKnownOne, Depth + 1)) 420202375Srdivacky return I; 421249423Sdim assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 422249423Sdim assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 423249423Sdim 424202375Srdivacky // If the operands are constants, see if we can simplify them. 425202375Srdivacky if (ShrinkDemandedConstant(I, 1, DemandedMask) || 426202375Srdivacky ShrinkDemandedConstant(I, 2, DemandedMask)) 427202375Srdivacky return I; 428249423Sdim 429202375Srdivacky // Only known if known in both the LHS and RHS. 430203954Srdivacky KnownOne = RHSKnownOne & LHSKnownOne; 431203954Srdivacky KnownZero = RHSKnownZero & LHSKnownZero; 432202375Srdivacky break; 433202375Srdivacky case Instruction::Trunc: { 434202375Srdivacky unsigned truncBf = I->getOperand(0)->getType()->getScalarSizeInBits(); 435218893Sdim DemandedMask = DemandedMask.zext(truncBf); 436218893Sdim KnownZero = KnownZero.zext(truncBf); 437218893Sdim KnownOne = KnownOne.zext(truncBf); 438288943Sdim if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, KnownZero, 439288943Sdim KnownOne, Depth + 1)) 440202375Srdivacky return I; 441218893Sdim DemandedMask = DemandedMask.trunc(BitWidth); 442218893Sdim KnownZero = KnownZero.trunc(BitWidth); 443218893Sdim KnownOne = KnownOne.trunc(BitWidth); 444249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 445202375Srdivacky break; 446202375Srdivacky } 447202375Srdivacky case Instruction::BitCast: 448203954Srdivacky if (!I->getOperand(0)->getType()->isIntOrIntVectorTy()) 449276479Sdim return nullptr; // vector->int or fp->int? 450202375Srdivacky 451226633Sdim if (VectorType *DstVTy = dyn_cast<VectorType>(I->getType())) { 452226633Sdim if (VectorType *SrcVTy = 453202375Srdivacky dyn_cast<VectorType>(I->getOperand(0)->getType())) { 454202375Srdivacky if (DstVTy->getNumElements() != SrcVTy->getNumElements()) 455202375Srdivacky // Don't touch a bitcast between vectors of different element counts. 456276479Sdim return nullptr; 457202375Srdivacky } else 458202375Srdivacky // Don't touch a scalar-to-vector bitcast. 459276479Sdim return nullptr; 460204642Srdivacky } else if (I->getOperand(0)->getType()->isVectorTy()) 461202375Srdivacky // Don't touch a vector-to-scalar bitcast. 462276479Sdim return nullptr; 463202375Srdivacky 464288943Sdim if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, KnownZero, 465288943Sdim KnownOne, Depth + 1)) 466202375Srdivacky return I; 467249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 468202375Srdivacky break; 469202375Srdivacky case Instruction::ZExt: { 470202375Srdivacky // Compute the bits in the result that are not present in the input. 471202375Srdivacky unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); 472249423Sdim 473218893Sdim DemandedMask = DemandedMask.trunc(SrcBitWidth); 474218893Sdim KnownZero = KnownZero.trunc(SrcBitWidth); 475218893Sdim KnownOne = KnownOne.trunc(SrcBitWidth); 476288943Sdim if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, KnownZero, 477288943Sdim KnownOne, Depth + 1)) 478202375Srdivacky return I; 479218893Sdim DemandedMask = DemandedMask.zext(BitWidth); 480218893Sdim KnownZero = KnownZero.zext(BitWidth); 481218893Sdim KnownOne = KnownOne.zext(BitWidth); 482249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 483202375Srdivacky // The top bits are known to be zero. 484203954Srdivacky KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 485202375Srdivacky break; 486202375Srdivacky } 487202375Srdivacky case Instruction::SExt: { 488202375Srdivacky // Compute the bits in the result that are not present in the input. 489202375Srdivacky unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); 490249423Sdim 491249423Sdim APInt InputDemandedBits = DemandedMask & 492202375Srdivacky APInt::getLowBitsSet(BitWidth, SrcBitWidth); 493202375Srdivacky 494202375Srdivacky APInt NewBits(APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth)); 495202375Srdivacky // If any of the sign extended bits are demanded, we know that the sign 496202375Srdivacky // bit is demanded. 497202375Srdivacky if ((NewBits & DemandedMask) != 0) 498218893Sdim InputDemandedBits.setBit(SrcBitWidth-1); 499249423Sdim 500218893Sdim InputDemandedBits = InputDemandedBits.trunc(SrcBitWidth); 501218893Sdim KnownZero = KnownZero.trunc(SrcBitWidth); 502218893Sdim KnownOne = KnownOne.trunc(SrcBitWidth); 503288943Sdim if (SimplifyDemandedBits(I->getOperandUse(0), InputDemandedBits, KnownZero, 504288943Sdim KnownOne, Depth + 1)) 505202375Srdivacky return I; 506218893Sdim InputDemandedBits = InputDemandedBits.zext(BitWidth); 507218893Sdim KnownZero = KnownZero.zext(BitWidth); 508218893Sdim KnownOne = KnownOne.zext(BitWidth); 509249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 510249423Sdim 511202375Srdivacky // If the sign bit of the input is known set or clear, then we know the 512202375Srdivacky // top bits of the result. 513202375Srdivacky 514202375Srdivacky // If the input sign bit is known zero, or if the NewBits are not demanded 515202375Srdivacky // convert this into a zero extension. 516203954Srdivacky if (KnownZero[SrcBitWidth-1] || (NewBits & ~DemandedMask) == NewBits) { 517202375Srdivacky // Convert to ZExt cast 518202375Srdivacky CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName()); 519223017Sdim return InsertNewInstWith(NewCast, *I); 520203954Srdivacky } else if (KnownOne[SrcBitWidth-1]) { // Input sign bit known set 521203954Srdivacky KnownOne |= NewBits; 522202375Srdivacky } 523202375Srdivacky break; 524202375Srdivacky } 525288943Sdim case Instruction::Add: 526288943Sdim case Instruction::Sub: { 527288943Sdim /// If the high-bits of an ADD/SUB are not demanded, then we do not care 528288943Sdim /// about the high bits of the operands. 529202375Srdivacky unsigned NLZ = DemandedMask.countLeadingZeros(); 530288943Sdim if (NLZ > 0) { 531288943Sdim // Right fill the mask of bits for this ADD/SUB to demand the most 532202375Srdivacky // significant bit and all those below it. 533202375Srdivacky APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ)); 534202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps, 535288943Sdim LHSKnownZero, LHSKnownOne, Depth + 1) || 536288943Sdim ShrinkDemandedConstant(I, 1, DemandedFromOps) || 537202375Srdivacky SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps, 538288943Sdim LHSKnownZero, LHSKnownOne, Depth + 1)) { 539288943Sdim // Disable the nsw and nuw flags here: We can no longer guarantee that 540288943Sdim // we won't wrap after simplification. Removing the nsw/nuw flags is 541288943Sdim // legal here because the top bit is not demanded. 542288943Sdim BinaryOperator &BinOP = *cast<BinaryOperator>(I); 543288943Sdim BinOP.setHasNoSignedWrap(false); 544288943Sdim BinOP.setHasNoUnsignedWrap(false); 545202375Srdivacky return I; 546288943Sdim } 547202375Srdivacky } 548234353Sdim 549288943Sdim // Otherwise just hand the add/sub off to computeKnownBits to fill in 550202375Srdivacky // the known zeros and ones. 551280031Sdim computeKnownBits(V, KnownZero, KnownOne, Depth, CxtI); 552202375Srdivacky break; 553288943Sdim } 554202375Srdivacky case Instruction::Shl: 555202375Srdivacky if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 556249423Sdim { 557249423Sdim Value *VarX; ConstantInt *C1; 558249423Sdim if (match(I->getOperand(0), m_Shr(m_Value(VarX), m_ConstantInt(C1)))) { 559249423Sdim Instruction *Shr = cast<Instruction>(I->getOperand(0)); 560249423Sdim Value *R = SimplifyShrShlDemandedBits(Shr, I, DemandedMask, 561249423Sdim KnownZero, KnownOne); 562249423Sdim if (R) 563249423Sdim return R; 564249423Sdim } 565249423Sdim } 566249423Sdim 567218893Sdim uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 568202375Srdivacky APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt)); 569249423Sdim 570218893Sdim // If the shift is NUW/NSW, then it does demand the high bits. 571218893Sdim ShlOperator *IOp = cast<ShlOperator>(I); 572218893Sdim if (IOp->hasNoSignedWrap()) 573218893Sdim DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1); 574218893Sdim else if (IOp->hasNoUnsignedWrap()) 575218893Sdim DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 576249423Sdim 577288943Sdim if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, KnownZero, 578288943Sdim KnownOne, Depth + 1)) 579202375Srdivacky return I; 580203954Srdivacky assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 581203954Srdivacky KnownZero <<= ShiftAmt; 582203954Srdivacky KnownOne <<= ShiftAmt; 583202375Srdivacky // low bits known zero. 584202375Srdivacky if (ShiftAmt) 585203954Srdivacky KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 586202375Srdivacky } 587202375Srdivacky break; 588202375Srdivacky case Instruction::LShr: 589202375Srdivacky // For a logical shift right 590202375Srdivacky if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 591218893Sdim uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 592249423Sdim 593202375Srdivacky // Unsigned shift right. 594202375Srdivacky APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 595249423Sdim 596218893Sdim // If the shift is exact, then it does demand the low bits (and knows that 597218893Sdim // they are zero). 598218893Sdim if (cast<LShrOperator>(I)->isExact()) 599218893Sdim DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 600249423Sdim 601288943Sdim if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, KnownZero, 602288943Sdim KnownOne, Depth + 1)) 603202375Srdivacky return I; 604203954Srdivacky assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 605203954Srdivacky KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 606203954Srdivacky KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 607202375Srdivacky if (ShiftAmt) { 608202375Srdivacky // Compute the new bits that are at the top now. 609202375Srdivacky APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 610203954Srdivacky KnownZero |= HighBits; // high bits known zero. 611202375Srdivacky } 612202375Srdivacky } 613202375Srdivacky break; 614202375Srdivacky case Instruction::AShr: 615202375Srdivacky // If this is an arithmetic shift right and only the low-bit is set, we can 616202375Srdivacky // always convert this into a logical shr, even if the shift amount is 617202375Srdivacky // variable. The low bit of the shift cannot be an input sign bit unless 618202375Srdivacky // the shift amount is >= the size of the datatype, which is undefined. 619202375Srdivacky if (DemandedMask == 1) { 620202375Srdivacky // Perform the logical shift right. 621202375Srdivacky Instruction *NewVal = BinaryOperator::CreateLShr( 622202375Srdivacky I->getOperand(0), I->getOperand(1), I->getName()); 623223017Sdim return InsertNewInstWith(NewVal, *I); 624249423Sdim } 625202375Srdivacky 626202375Srdivacky // If the sign bit is the only bit demanded by this ashr, then there is no 627202375Srdivacky // need to do it, the shift doesn't change the high bit. 628202375Srdivacky if (DemandedMask.isSignBit()) 629202375Srdivacky return I->getOperand(0); 630249423Sdim 631202375Srdivacky if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 632218893Sdim uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 633249423Sdim 634202375Srdivacky // Signed shift right. 635202375Srdivacky APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 636202375Srdivacky // If any of the "high bits" are demanded, we should set the sign bit as 637202375Srdivacky // demanded. 638202375Srdivacky if (DemandedMask.countLeadingZeros() <= ShiftAmt) 639218893Sdim DemandedMaskIn.setBit(BitWidth-1); 640249423Sdim 641218893Sdim // If the shift is exact, then it does demand the low bits (and knows that 642218893Sdim // they are zero). 643218893Sdim if (cast<AShrOperator>(I)->isExact()) 644218893Sdim DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 645249423Sdim 646288943Sdim if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, KnownZero, 647288943Sdim KnownOne, Depth + 1)) 648202375Srdivacky return I; 649203954Srdivacky assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 650202375Srdivacky // Compute the new bits that are at the top now. 651202375Srdivacky APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 652203954Srdivacky KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 653203954Srdivacky KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 654249423Sdim 655202375Srdivacky // Handle the sign bits. 656202375Srdivacky APInt SignBit(APInt::getSignBit(BitWidth)); 657202375Srdivacky // Adjust to where it is now in the mask. 658249423Sdim SignBit = APIntOps::lshr(SignBit, ShiftAmt); 659249423Sdim 660202375Srdivacky // If the input sign bit is known to be zero, or if none of the top bits 661202375Srdivacky // are demanded, turn this into an unsigned shift right. 662249423Sdim if (BitWidth <= ShiftAmt || KnownZero[BitWidth-ShiftAmt-1] || 663202375Srdivacky (HighBits & ~DemandedMask) == HighBits) { 664202375Srdivacky // Perform the logical shift right. 665234353Sdim BinaryOperator *NewVal = BinaryOperator::CreateLShr(I->getOperand(0), 666234353Sdim SA, I->getName()); 667234353Sdim NewVal->setIsExact(cast<BinaryOperator>(I)->isExact()); 668223017Sdim return InsertNewInstWith(NewVal, *I); 669203954Srdivacky } else if ((KnownOne & SignBit) != 0) { // New bits are known one. 670203954Srdivacky KnownOne |= HighBits; 671202375Srdivacky } 672202375Srdivacky } 673202375Srdivacky break; 674202375Srdivacky case Instruction::SRem: 675202375Srdivacky if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 676221345Sdim // X % -1 demands all the bits because we don't want to introduce 677221345Sdim // INT_MIN % -1 (== undef) by accident. 678221345Sdim if (Rem->isAllOnesValue()) 679221345Sdim break; 680202375Srdivacky APInt RA = Rem->getValue().abs(); 681202375Srdivacky if (RA.isPowerOf2()) { 682202375Srdivacky if (DemandedMask.ult(RA)) // srem won't affect demanded bits 683202375Srdivacky return I->getOperand(0); 684202375Srdivacky 685202375Srdivacky APInt LowBits = RA - 1; 686202375Srdivacky APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 687288943Sdim if (SimplifyDemandedBits(I->getOperandUse(0), Mask2, LHSKnownZero, 688288943Sdim LHSKnownOne, Depth + 1)) 689202375Srdivacky return I; 690202375Srdivacky 691203954Srdivacky // The low bits of LHS are unchanged by the srem. 692203954Srdivacky KnownZero = LHSKnownZero & LowBits; 693203954Srdivacky KnownOne = LHSKnownOne & LowBits; 694203954Srdivacky 695203954Srdivacky // If LHS is non-negative or has all low bits zero, then the upper bits 696203954Srdivacky // are all zero. 697202375Srdivacky if (LHSKnownZero[BitWidth-1] || ((LHSKnownZero & LowBits) == LowBits)) 698203954Srdivacky KnownZero |= ~LowBits; 699202375Srdivacky 700203954Srdivacky // If LHS is negative and not all low bits are zero, then the upper bits 701203954Srdivacky // are all one. 702203954Srdivacky if (LHSKnownOne[BitWidth-1] && ((LHSKnownOne & LowBits) != 0)) 703203954Srdivacky KnownOne |= ~LowBits; 704202375Srdivacky 705249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 706202375Srdivacky } 707202375Srdivacky } 708221345Sdim 709221345Sdim // The sign bit is the LHS's sign bit, except when the result of the 710221345Sdim // remainder is zero. 711221345Sdim if (DemandedMask.isNegative() && KnownZero.isNonNegative()) { 712221345Sdim APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 713288943Sdim computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth + 1, 714280031Sdim CxtI); 715221345Sdim // If it's known zero, our sign bit is also zero. 716221345Sdim if (LHSKnownZero.isNegative()) 717261991Sdim KnownZero.setBit(KnownZero.getBitWidth() - 1); 718221345Sdim } 719202375Srdivacky break; 720202375Srdivacky case Instruction::URem: { 721202375Srdivacky APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0); 722202375Srdivacky APInt AllOnes = APInt::getAllOnesValue(BitWidth); 723288943Sdim if (SimplifyDemandedBits(I->getOperandUse(0), AllOnes, KnownZero2, 724288943Sdim KnownOne2, Depth + 1) || 725288943Sdim SimplifyDemandedBits(I->getOperandUse(1), AllOnes, KnownZero2, 726288943Sdim KnownOne2, Depth + 1)) 727202375Srdivacky return I; 728202375Srdivacky 729202375Srdivacky unsigned Leaders = KnownZero2.countLeadingOnes(); 730202375Srdivacky Leaders = std::max(Leaders, 731202375Srdivacky KnownZero2.countLeadingOnes()); 732202375Srdivacky KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask; 733202375Srdivacky break; 734202375Srdivacky } 735202375Srdivacky case Instruction::Call: 736202375Srdivacky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 737202375Srdivacky switch (II->getIntrinsicID()) { 738202375Srdivacky default: break; 739202375Srdivacky case Intrinsic::bswap: { 740202375Srdivacky // If the only bits demanded come from one byte of the bswap result, 741202375Srdivacky // just shift the input byte into position to eliminate the bswap. 742202375Srdivacky unsigned NLZ = DemandedMask.countLeadingZeros(); 743202375Srdivacky unsigned NTZ = DemandedMask.countTrailingZeros(); 744249423Sdim 745202375Srdivacky // Round NTZ down to the next byte. If we have 11 trailing zeros, then 746202375Srdivacky // we need all the bits down to bit 8. Likewise, round NLZ. If we 747202375Srdivacky // have 14 leading zeros, round to 8. 748202375Srdivacky NLZ &= ~7; 749202375Srdivacky NTZ &= ~7; 750202375Srdivacky // If we need exactly one byte, we can do this transformation. 751202375Srdivacky if (BitWidth-NLZ-NTZ == 8) { 752202375Srdivacky unsigned ResultBit = NTZ; 753202375Srdivacky unsigned InputBit = BitWidth-NTZ-8; 754249423Sdim 755202375Srdivacky // Replace this with either a left or right shift to get the byte into 756202375Srdivacky // the right place. 757202375Srdivacky Instruction *NewVal; 758202375Srdivacky if (InputBit > ResultBit) 759210299Sed NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0), 760202375Srdivacky ConstantInt::get(I->getType(), InputBit-ResultBit)); 761202375Srdivacky else 762210299Sed NewVal = BinaryOperator::CreateShl(II->getArgOperand(0), 763202375Srdivacky ConstantInt::get(I->getType(), ResultBit-InputBit)); 764202375Srdivacky NewVal->takeName(I); 765223017Sdim return InsertNewInstWith(NewVal, *I); 766202375Srdivacky } 767249423Sdim 768202375Srdivacky // TODO: Could compute known zero/one bits based on the input. 769202375Srdivacky break; 770202375Srdivacky } 771223017Sdim case Intrinsic::x86_sse42_crc32_64_64: 772223017Sdim KnownZero = APInt::getHighBitsSet(64, 32); 773276479Sdim return nullptr; 774202375Srdivacky } 775202375Srdivacky } 776280031Sdim computeKnownBits(V, KnownZero, KnownOne, Depth, CxtI); 777202375Srdivacky break; 778202375Srdivacky } 779249423Sdim 780202375Srdivacky // If the client is only demanding bits that we know, return the known 781202375Srdivacky // constant. 782203954Srdivacky if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) 783203954Srdivacky return Constant::getIntegerValue(VTy, KnownOne); 784276479Sdim return nullptr; 785202375Srdivacky} 786202375Srdivacky 787249423Sdim/// Helper routine of SimplifyDemandedUseBits. It tries to simplify 788249423Sdim/// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into 789249423Sdim/// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign 790249423Sdim/// of "C2-C1". 791249423Sdim/// 792249423Sdim/// Suppose E1 and E2 are generally different in bits S={bm, bm+1, 793249423Sdim/// ..., bn}, without considering the specific value X is holding. 794249423Sdim/// This transformation is legal iff one of following conditions is hold: 795249423Sdim/// 1) All the bit in S are 0, in this case E1 == E2. 796249423Sdim/// 2) We don't care those bits in S, per the input DemandedMask. 797249423Sdim/// 3) Combination of 1) and 2). Some bits in S are 0, and we don't care the 798249423Sdim/// rest bits. 799249423Sdim/// 800249423Sdim/// Currently we only test condition 2). 801249423Sdim/// 802249423Sdim/// As with SimplifyDemandedUseBits, it returns NULL if the simplification was 803249423Sdim/// not successful. 804249423SdimValue *InstCombiner::SimplifyShrShlDemandedBits(Instruction *Shr, 805249423Sdim Instruction *Shl, APInt DemandedMask, APInt &KnownZero, APInt &KnownOne) { 806202375Srdivacky 807255076Sdim const APInt &ShlOp1 = cast<ConstantInt>(Shl->getOperand(1))->getValue(); 808255076Sdim const APInt &ShrOp1 = cast<ConstantInt>(Shr->getOperand(1))->getValue(); 809255076Sdim if (!ShlOp1 || !ShrOp1) 810276479Sdim return nullptr; // Noop. 811249423Sdim 812255076Sdim Value *VarX = Shr->getOperand(0); 813255076Sdim Type *Ty = VarX->getType(); 814255076Sdim unsigned BitWidth = Ty->getIntegerBitWidth(); 815255076Sdim if (ShlOp1.uge(BitWidth) || ShrOp1.uge(BitWidth)) 816276479Sdim return nullptr; // Undef. 817255076Sdim 818255076Sdim unsigned ShlAmt = ShlOp1.getZExtValue(); 819255076Sdim unsigned ShrAmt = ShrOp1.getZExtValue(); 820255076Sdim 821249423Sdim KnownOne.clearAllBits(); 822249423Sdim KnownZero = APInt::getBitsSet(KnownZero.getBitWidth(), 0, ShlAmt-1); 823249423Sdim KnownZero &= DemandedMask; 824249423Sdim 825255076Sdim APInt BitMask1(APInt::getAllOnesValue(BitWidth)); 826255076Sdim APInt BitMask2(APInt::getAllOnesValue(BitWidth)); 827249423Sdim 828249423Sdim bool isLshr = (Shr->getOpcode() == Instruction::LShr); 829249423Sdim BitMask1 = isLshr ? (BitMask1.lshr(ShrAmt) << ShlAmt) : 830249423Sdim (BitMask1.ashr(ShrAmt) << ShlAmt); 831249423Sdim 832249423Sdim if (ShrAmt <= ShlAmt) { 833249423Sdim BitMask2 <<= (ShlAmt - ShrAmt); 834249423Sdim } else { 835249423Sdim BitMask2 = isLshr ? BitMask2.lshr(ShrAmt - ShlAmt): 836249423Sdim BitMask2.ashr(ShrAmt - ShlAmt); 837249423Sdim } 838249423Sdim 839249423Sdim // Check if condition-2 (see the comment to this function) is satified. 840249423Sdim if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) { 841249423Sdim if (ShrAmt == ShlAmt) 842249423Sdim return VarX; 843249423Sdim 844249423Sdim if (!Shr->hasOneUse()) 845276479Sdim return nullptr; 846249423Sdim 847249423Sdim BinaryOperator *New; 848249423Sdim if (ShrAmt < ShlAmt) { 849249423Sdim Constant *Amt = ConstantInt::get(VarX->getType(), ShlAmt - ShrAmt); 850249423Sdim New = BinaryOperator::CreateShl(VarX, Amt); 851249423Sdim BinaryOperator *Orig = cast<BinaryOperator>(Shl); 852249423Sdim New->setHasNoSignedWrap(Orig->hasNoSignedWrap()); 853249423Sdim New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap()); 854249423Sdim } else { 855249423Sdim Constant *Amt = ConstantInt::get(VarX->getType(), ShrAmt - ShlAmt); 856249423Sdim New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) : 857249423Sdim BinaryOperator::CreateAShr(VarX, Amt); 858249423Sdim if (cast<BinaryOperator>(Shr)->isExact()) 859249423Sdim New->setIsExact(true); 860249423Sdim } 861249423Sdim 862249423Sdim return InsertNewInstWith(New, *Shl); 863249423Sdim } 864249423Sdim 865276479Sdim return nullptr; 866249423Sdim} 867249423Sdim 868202375Srdivacky/// SimplifyDemandedVectorElts - The specified value produces a vector with 869202375Srdivacky/// any number of elements. DemandedElts contains the set of elements that are 870202375Srdivacky/// actually used by the caller. This method analyzes which elements of the 871202375Srdivacky/// operand are undef and returns that information in UndefElts. 872202375Srdivacky/// 873202375Srdivacky/// If the information about demanded elements can be used to simplify the 874202375Srdivacky/// operation, the operation is simplified, then the resultant value is 875202375Srdivacky/// returned. This returns null if no change was made. 876202375SrdivackyValue *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, 877203954Srdivacky APInt &UndefElts, 878202375Srdivacky unsigned Depth) { 879202375Srdivacky unsigned VWidth = cast<VectorType>(V->getType())->getNumElements(); 880202375Srdivacky APInt EltMask(APInt::getAllOnesValue(VWidth)); 881202375Srdivacky assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!"); 882202375Srdivacky 883202375Srdivacky if (isa<UndefValue>(V)) { 884202375Srdivacky // If the entire vector is undefined, just return this info. 885202375Srdivacky UndefElts = EltMask; 886276479Sdim return nullptr; 887203954Srdivacky } 888249423Sdim 889203954Srdivacky if (DemandedElts == 0) { // If nothing is demanded, provide undef. 890202375Srdivacky UndefElts = EltMask; 891202375Srdivacky return UndefValue::get(V->getType()); 892202375Srdivacky } 893202375Srdivacky 894202375Srdivacky UndefElts = 0; 895249423Sdim 896234353Sdim // Handle ConstantAggregateZero, ConstantVector, ConstantDataSequential. 897234353Sdim if (Constant *C = dyn_cast<Constant>(V)) { 898234353Sdim // Check if this is identity. If so, return 0 since we are not simplifying 899234353Sdim // anything. 900234353Sdim if (DemandedElts.isAllOnesValue()) 901276479Sdim return nullptr; 902234353Sdim 903226633Sdim Type *EltTy = cast<VectorType>(V->getType())->getElementType(); 904202375Srdivacky Constant *Undef = UndefValue::get(EltTy); 905249423Sdim 906234353Sdim SmallVector<Constant*, 16> Elts; 907234353Sdim for (unsigned i = 0; i != VWidth; ++i) { 908202375Srdivacky if (!DemandedElts[i]) { // If not demanded, set to undef. 909202375Srdivacky Elts.push_back(Undef); 910218893Sdim UndefElts.setBit(i); 911234353Sdim continue; 912234353Sdim } 913249423Sdim 914234353Sdim Constant *Elt = C->getAggregateElement(i); 915276479Sdim if (!Elt) return nullptr; 916249423Sdim 917234353Sdim if (isa<UndefValue>(Elt)) { // Already undef. 918202375Srdivacky Elts.push_back(Undef); 919218893Sdim UndefElts.setBit(i); 920202375Srdivacky } else { // Otherwise, defined. 921234353Sdim Elts.push_back(Elt); 922202375Srdivacky } 923234353Sdim } 924249423Sdim 925202375Srdivacky // If we changed the constant, return it. 926234353Sdim Constant *NewCV = ConstantVector::get(Elts); 927276479Sdim return NewCV != C ? NewCV : nullptr; 928203954Srdivacky } 929249423Sdim 930202375Srdivacky // Limit search depth. 931202375Srdivacky if (Depth == 10) 932276479Sdim return nullptr; 933202375Srdivacky 934223017Sdim // If multiple users are using the root value, proceed with 935202375Srdivacky // simplification conservatively assuming that all elements 936202375Srdivacky // are needed. 937202375Srdivacky if (!V->hasOneUse()) { 938202375Srdivacky // Quit if we find multiple users of a non-root value though. 939202375Srdivacky // They'll be handled when it's their turn to be visited by 940202375Srdivacky // the main instcombine process. 941202375Srdivacky if (Depth != 0) 942202375Srdivacky // TODO: Just compute the UndefElts information recursively. 943276479Sdim return nullptr; 944202375Srdivacky 945202375Srdivacky // Conservatively assume that all elements are needed. 946202375Srdivacky DemandedElts = EltMask; 947202375Srdivacky } 948249423Sdim 949202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 950276479Sdim if (!I) return nullptr; // Only analyze instructions. 951249423Sdim 952202375Srdivacky bool MadeChange = false; 953202375Srdivacky APInt UndefElts2(VWidth, 0); 954202375Srdivacky Value *TmpV; 955202375Srdivacky switch (I->getOpcode()) { 956202375Srdivacky default: break; 957249423Sdim 958202375Srdivacky case Instruction::InsertElement: { 959202375Srdivacky // If this is a variable index, we don't know which element it overwrites. 960202375Srdivacky // demand exactly the same input as we produce. 961202375Srdivacky ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2)); 962276479Sdim if (!Idx) { 963202375Srdivacky // Note that we can't propagate undef elt info, because we don't know 964202375Srdivacky // which elt is getting updated. 965202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 966288943Sdim UndefElts2, Depth + 1); 967202375Srdivacky if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 968202375Srdivacky break; 969202375Srdivacky } 970249423Sdim 971202375Srdivacky // If this is inserting an element that isn't demanded, remove this 972202375Srdivacky // insertelement. 973202375Srdivacky unsigned IdxNo = Idx->getZExtValue(); 974202375Srdivacky if (IdxNo >= VWidth || !DemandedElts[IdxNo]) { 975202375Srdivacky Worklist.Add(I); 976202375Srdivacky return I->getOperand(0); 977202375Srdivacky } 978249423Sdim 979202375Srdivacky // Otherwise, the element inserted overwrites whatever was there, so the 980202375Srdivacky // input demanded set is simpler than the output set. 981202375Srdivacky APInt DemandedElts2 = DemandedElts; 982218893Sdim DemandedElts2.clearBit(IdxNo); 983202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts2, 984288943Sdim UndefElts, Depth + 1); 985202375Srdivacky if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 986202375Srdivacky 987202375Srdivacky // The inserted element is defined. 988218893Sdim UndefElts.clearBit(IdxNo); 989202375Srdivacky break; 990202375Srdivacky } 991202375Srdivacky case Instruction::ShuffleVector: { 992202375Srdivacky ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I); 993202375Srdivacky uint64_t LHSVWidth = 994202375Srdivacky cast<VectorType>(Shuffle->getOperand(0)->getType())->getNumElements(); 995202375Srdivacky APInt LeftDemanded(LHSVWidth, 0), RightDemanded(LHSVWidth, 0); 996202375Srdivacky for (unsigned i = 0; i < VWidth; i++) { 997202375Srdivacky if (DemandedElts[i]) { 998202375Srdivacky unsigned MaskVal = Shuffle->getMaskValue(i); 999202375Srdivacky if (MaskVal != -1u) { 1000202375Srdivacky assert(MaskVal < LHSVWidth * 2 && 1001202375Srdivacky "shufflevector mask index out of range!"); 1002202375Srdivacky if (MaskVal < LHSVWidth) 1003218893Sdim LeftDemanded.setBit(MaskVal); 1004202375Srdivacky else 1005218893Sdim RightDemanded.setBit(MaskVal - LHSVWidth); 1006202375Srdivacky } 1007202375Srdivacky } 1008202375Srdivacky } 1009202375Srdivacky 1010202375Srdivacky APInt UndefElts4(LHSVWidth, 0); 1011202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(0), LeftDemanded, 1012288943Sdim UndefElts4, Depth + 1); 1013202375Srdivacky if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1014202375Srdivacky 1015202375Srdivacky APInt UndefElts3(LHSVWidth, 0); 1016202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(1), RightDemanded, 1017288943Sdim UndefElts3, Depth + 1); 1018202375Srdivacky if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 1019202375Srdivacky 1020202375Srdivacky bool NewUndefElts = false; 1021202375Srdivacky for (unsigned i = 0; i < VWidth; i++) { 1022202375Srdivacky unsigned MaskVal = Shuffle->getMaskValue(i); 1023202375Srdivacky if (MaskVal == -1u) { 1024218893Sdim UndefElts.setBit(i); 1025226633Sdim } else if (!DemandedElts[i]) { 1026226633Sdim NewUndefElts = true; 1027226633Sdim UndefElts.setBit(i); 1028202375Srdivacky } else if (MaskVal < LHSVWidth) { 1029202375Srdivacky if (UndefElts4[MaskVal]) { 1030202375Srdivacky NewUndefElts = true; 1031218893Sdim UndefElts.setBit(i); 1032202375Srdivacky } 1033202375Srdivacky } else { 1034202375Srdivacky if (UndefElts3[MaskVal - LHSVWidth]) { 1035202375Srdivacky NewUndefElts = true; 1036218893Sdim UndefElts.setBit(i); 1037202375Srdivacky } 1038202375Srdivacky } 1039202375Srdivacky } 1040202375Srdivacky 1041202375Srdivacky if (NewUndefElts) { 1042202375Srdivacky // Add additional discovered undefs. 1043234353Sdim SmallVector<Constant*, 16> Elts; 1044202375Srdivacky for (unsigned i = 0; i < VWidth; ++i) { 1045202375Srdivacky if (UndefElts[i]) 1046202375Srdivacky Elts.push_back(UndefValue::get(Type::getInt32Ty(I->getContext()))); 1047202375Srdivacky else 1048202375Srdivacky Elts.push_back(ConstantInt::get(Type::getInt32Ty(I->getContext()), 1049202375Srdivacky Shuffle->getMaskValue(i))); 1050202375Srdivacky } 1051202375Srdivacky I->setOperand(2, ConstantVector::get(Elts)); 1052202375Srdivacky MadeChange = true; 1053202375Srdivacky } 1054202375Srdivacky break; 1055202375Srdivacky } 1056239462Sdim case Instruction::Select: { 1057239462Sdim APInt LeftDemanded(DemandedElts), RightDemanded(DemandedElts); 1058239462Sdim if (ConstantVector* CV = dyn_cast<ConstantVector>(I->getOperand(0))) { 1059239462Sdim for (unsigned i = 0; i < VWidth; i++) { 1060296417Sdim Constant *CElt = CV->getAggregateElement(i); 1061296417Sdim // Method isNullValue always returns false when called on a 1062296417Sdim // ConstantExpr. If CElt is a ConstantExpr then skip it in order to 1063296417Sdim // to avoid propagating incorrect information. 1064296417Sdim if (isa<ConstantExpr>(CElt)) 1065296417Sdim continue; 1066296417Sdim if (CElt->isNullValue()) 1067239462Sdim LeftDemanded.clearBit(i); 1068239462Sdim else 1069239462Sdim RightDemanded.clearBit(i); 1070239462Sdim } 1071239462Sdim } 1072239462Sdim 1073288943Sdim TmpV = SimplifyDemandedVectorElts(I->getOperand(1), LeftDemanded, UndefElts, 1074288943Sdim Depth + 1); 1075239462Sdim if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 1076239462Sdim 1077239462Sdim TmpV = SimplifyDemandedVectorElts(I->getOperand(2), RightDemanded, 1078288943Sdim UndefElts2, Depth + 1); 1079239462Sdim if (TmpV) { I->setOperand(2, TmpV); MadeChange = true; } 1080249423Sdim 1081239462Sdim // Output elements are undefined if both are undefined. 1082239462Sdim UndefElts &= UndefElts2; 1083239462Sdim break; 1084239462Sdim } 1085202375Srdivacky case Instruction::BitCast: { 1086202375Srdivacky // Vector->vector casts only. 1087226633Sdim VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType()); 1088202375Srdivacky if (!VTy) break; 1089202375Srdivacky unsigned InVWidth = VTy->getNumElements(); 1090202375Srdivacky APInt InputDemandedElts(InVWidth, 0); 1091296417Sdim UndefElts2 = APInt(InVWidth, 0); 1092202375Srdivacky unsigned Ratio; 1093202375Srdivacky 1094202375Srdivacky if (VWidth == InVWidth) { 1095202375Srdivacky // If we are converting from <4 x i32> -> <4 x f32>, we demand the same 1096202375Srdivacky // elements as are demanded of us. 1097202375Srdivacky Ratio = 1; 1098202375Srdivacky InputDemandedElts = DemandedElts; 1099296417Sdim } else if ((VWidth % InVWidth) == 0) { 1100296417Sdim // If the number of elements in the output is a multiple of the number of 1101296417Sdim // elements in the input then an input element is live if any of the 1102296417Sdim // corresponding output elements are live. 1103296417Sdim Ratio = VWidth / InVWidth; 1104296417Sdim for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) 1105202375Srdivacky if (DemandedElts[OutIdx]) 1106296417Sdim InputDemandedElts.setBit(OutIdx / Ratio); 1107296417Sdim } else if ((InVWidth % VWidth) == 0) { 1108296417Sdim // If the number of elements in the input is a multiple of the number of 1109296417Sdim // elements in the output then an input element is live if the 1110296417Sdim // corresponding output element is live. 1111296417Sdim Ratio = InVWidth / VWidth; 1112296417Sdim for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) 1113296417Sdim if (DemandedElts[InIdx / Ratio]) 1114296417Sdim InputDemandedElts.setBit(InIdx); 1115202375Srdivacky } else { 1116296417Sdim // Unsupported so far. 1117202375Srdivacky break; 1118202375Srdivacky } 1119249423Sdim 1120202375Srdivacky // div/rem demand all inputs, because they don't want divide by zero. 1121202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(0), InputDemandedElts, 1122288943Sdim UndefElts2, Depth + 1); 1123202375Srdivacky if (TmpV) { 1124202375Srdivacky I->setOperand(0, TmpV); 1125202375Srdivacky MadeChange = true; 1126202375Srdivacky } 1127249423Sdim 1128296417Sdim if (VWidth == InVWidth) { 1129296417Sdim UndefElts = UndefElts2; 1130296417Sdim } else if ((VWidth % InVWidth) == 0) { 1131296417Sdim // If the number of elements in the output is a multiple of the number of 1132296417Sdim // elements in the input then an output element is undef if the 1133296417Sdim // corresponding input element is undef. 1134202375Srdivacky for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) 1135296417Sdim if (UndefElts2[OutIdx / Ratio]) 1136218893Sdim UndefElts.setBit(OutIdx); 1137296417Sdim } else if ((InVWidth % VWidth) == 0) { 1138296417Sdim // If the number of elements in the input is a multiple of the number of 1139296417Sdim // elements in the output then an output element is undef if all of the 1140296417Sdim // corresponding input elements are undef. 1141296417Sdim for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) { 1142296417Sdim APInt SubUndef = UndefElts2.lshr(OutIdx * Ratio).zextOrTrunc(Ratio); 1143296417Sdim if (SubUndef.countPopulation() == Ratio) 1144296417Sdim UndefElts.setBit(OutIdx); 1145296417Sdim } 1146296417Sdim } else { 1147202375Srdivacky llvm_unreachable("Unimp"); 1148202375Srdivacky } 1149202375Srdivacky break; 1150202375Srdivacky } 1151202375Srdivacky case Instruction::And: 1152202375Srdivacky case Instruction::Or: 1153202375Srdivacky case Instruction::Xor: 1154202375Srdivacky case Instruction::Add: 1155202375Srdivacky case Instruction::Sub: 1156202375Srdivacky case Instruction::Mul: 1157202375Srdivacky // div/rem demand all inputs, because they don't want divide by zero. 1158288943Sdim TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, UndefElts, 1159288943Sdim Depth + 1); 1160202375Srdivacky if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1161202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(1), DemandedElts, 1162288943Sdim UndefElts2, Depth + 1); 1163202375Srdivacky if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 1164249423Sdim 1165202375Srdivacky // Output elements are undefined if both are undefined. Consider things 1166202375Srdivacky // like undef&0. The result is known zero, not undef. 1167202375Srdivacky UndefElts &= UndefElts2; 1168202375Srdivacky break; 1169239462Sdim case Instruction::FPTrunc: 1170239462Sdim case Instruction::FPExt: 1171288943Sdim TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, UndefElts, 1172288943Sdim Depth + 1); 1173239462Sdim if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1174239462Sdim break; 1175249423Sdim 1176202375Srdivacky case Instruction::Call: { 1177202375Srdivacky IntrinsicInst *II = dyn_cast<IntrinsicInst>(I); 1178202375Srdivacky if (!II) break; 1179202375Srdivacky switch (II->getIntrinsicID()) { 1180202375Srdivacky default: break; 1181249423Sdim 1182202375Srdivacky // Binary vector operations that work column-wise. A dest element is a 1183202375Srdivacky // function of the corresponding input elements from the two inputs. 1184202375Srdivacky case Intrinsic::x86_sse_sub_ss: 1185202375Srdivacky case Intrinsic::x86_sse_mul_ss: 1186202375Srdivacky case Intrinsic::x86_sse_min_ss: 1187202375Srdivacky case Intrinsic::x86_sse_max_ss: 1188202375Srdivacky case Intrinsic::x86_sse2_sub_sd: 1189202375Srdivacky case Intrinsic::x86_sse2_mul_sd: 1190202375Srdivacky case Intrinsic::x86_sse2_min_sd: 1191202375Srdivacky case Intrinsic::x86_sse2_max_sd: 1192210299Sed TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts, 1193288943Sdim UndefElts, Depth + 1); 1194210299Sed if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } 1195210299Sed TmpV = SimplifyDemandedVectorElts(II->getArgOperand(1), DemandedElts, 1196288943Sdim UndefElts2, Depth + 1); 1197210299Sed if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; } 1198202375Srdivacky 1199202375Srdivacky // If only the low elt is demanded and this is a scalarizable intrinsic, 1200202375Srdivacky // scalarize it now. 1201202375Srdivacky if (DemandedElts == 1) { 1202202375Srdivacky switch (II->getIntrinsicID()) { 1203202375Srdivacky default: break; 1204202375Srdivacky case Intrinsic::x86_sse_sub_ss: 1205202375Srdivacky case Intrinsic::x86_sse_mul_ss: 1206202375Srdivacky case Intrinsic::x86_sse2_sub_sd: 1207202375Srdivacky case Intrinsic::x86_sse2_mul_sd: 1208202375Srdivacky // TODO: Lower MIN/MAX/ABS/etc 1209210299Sed Value *LHS = II->getArgOperand(0); 1210210299Sed Value *RHS = II->getArgOperand(1); 1211202375Srdivacky // Extract the element as scalars. 1212249423Sdim LHS = InsertNewInstWith(ExtractElementInst::Create(LHS, 1213202375Srdivacky ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); 1214223017Sdim RHS = InsertNewInstWith(ExtractElementInst::Create(RHS, 1215202375Srdivacky ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); 1216249423Sdim 1217202375Srdivacky switch (II->getIntrinsicID()) { 1218202375Srdivacky default: llvm_unreachable("Case stmts out of sync!"); 1219202375Srdivacky case Intrinsic::x86_sse_sub_ss: 1220202375Srdivacky case Intrinsic::x86_sse2_sub_sd: 1221223017Sdim TmpV = InsertNewInstWith(BinaryOperator::CreateFSub(LHS, RHS, 1222202375Srdivacky II->getName()), *II); 1223202375Srdivacky break; 1224202375Srdivacky case Intrinsic::x86_sse_mul_ss: 1225202375Srdivacky case Intrinsic::x86_sse2_mul_sd: 1226223017Sdim TmpV = InsertNewInstWith(BinaryOperator::CreateFMul(LHS, RHS, 1227202375Srdivacky II->getName()), *II); 1228202375Srdivacky break; 1229202375Srdivacky } 1230249423Sdim 1231202375Srdivacky Instruction *New = 1232202375Srdivacky InsertElementInst::Create( 1233202375Srdivacky UndefValue::get(II->getType()), TmpV, 1234202375Srdivacky ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U, false), 1235202375Srdivacky II->getName()); 1236223017Sdim InsertNewInstWith(New, *II); 1237202375Srdivacky return New; 1238249423Sdim } 1239202375Srdivacky } 1240249423Sdim 1241202375Srdivacky // Output elements are undefined if both are undefined. Consider things 1242202375Srdivacky // like undef&0. The result is known zero, not undef. 1243202375Srdivacky UndefElts &= UndefElts2; 1244202375Srdivacky break; 1245296417Sdim 1246296417Sdim // SSE4A instructions leave the upper 64-bits of the 128-bit result 1247296417Sdim // in an undefined state. 1248296417Sdim case Intrinsic::x86_sse4a_extrq: 1249296417Sdim case Intrinsic::x86_sse4a_extrqi: 1250296417Sdim case Intrinsic::x86_sse4a_insertq: 1251296417Sdim case Intrinsic::x86_sse4a_insertqi: 1252296417Sdim UndefElts |= APInt::getHighBitsSet(VWidth, VWidth / 2); 1253296417Sdim break; 1254202375Srdivacky } 1255202375Srdivacky break; 1256202375Srdivacky } 1257202375Srdivacky } 1258276479Sdim return MadeChange ? I : nullptr; 1259202375Srdivacky} 1260