InstCombineSimplifyDemanded.cpp revision 255076
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 15202375Srdivacky 16202375Srdivacky#include "InstCombine.h" 17249423Sdim#include "llvm/IR/DataLayout.h" 18249423Sdim#include "llvm/IR/IntrinsicInst.h" 19249423Sdim#include "llvm/Support/PatternMatch.h" 20202375Srdivacky 21202375Srdivackyusing namespace llvm; 22249423Sdimusing namespace llvm::PatternMatch; 23202375Srdivacky 24249423Sdim/// ShrinkDemandedConstant - Check to see if the specified operand of the 25202375Srdivacky/// specified instruction is a constant integer. If so, check to see if there 26202375Srdivacky/// are any bits set in the constant that are not demanded. If so, shrink the 27202375Srdivacky/// constant and return true. 28249423Sdimstatic bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo, 29202375Srdivacky APInt Demanded) { 30202375Srdivacky assert(I && "No instruction?"); 31202375Srdivacky assert(OpNo < I->getNumOperands() && "Operand index too large"); 32202375Srdivacky 33202375Srdivacky // If the operand is not a constant integer, nothing to do. 34202375Srdivacky ConstantInt *OpC = dyn_cast<ConstantInt>(I->getOperand(OpNo)); 35202375Srdivacky if (!OpC) return false; 36202375Srdivacky 37202375Srdivacky // If there are no bits set that aren't demanded, nothing to do. 38218893Sdim Demanded = Demanded.zextOrTrunc(OpC->getValue().getBitWidth()); 39202375Srdivacky if ((~Demanded & OpC->getValue()) == 0) 40202375Srdivacky return false; 41202375Srdivacky 42202375Srdivacky // This instruction is producing bits that are not demanded. Shrink the RHS. 43202375Srdivacky Demanded &= OpC->getValue(); 44202375Srdivacky I->setOperand(OpNo, ConstantInt::get(OpC->getType(), Demanded)); 45202375Srdivacky return true; 46202375Srdivacky} 47202375Srdivacky 48202375Srdivacky 49202375Srdivacky 50202375Srdivacky/// SimplifyDemandedInstructionBits - Inst is an integer instruction that 51202375Srdivacky/// SimplifyDemandedBits knows about. See if the instruction has any 52202375Srdivacky/// properties that allow us to simplify its operands. 53202375Srdivackybool InstCombiner::SimplifyDemandedInstructionBits(Instruction &Inst) { 54202375Srdivacky unsigned BitWidth = Inst.getType()->getScalarSizeInBits(); 55202375Srdivacky APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 56202375Srdivacky APInt DemandedMask(APInt::getAllOnesValue(BitWidth)); 57249423Sdim 58249423Sdim Value *V = SimplifyDemandedUseBits(&Inst, DemandedMask, 59202375Srdivacky KnownZero, KnownOne, 0); 60202375Srdivacky if (V == 0) return false; 61202375Srdivacky if (V == &Inst) return true; 62202375Srdivacky ReplaceInstUsesWith(Inst, V); 63202375Srdivacky return true; 64202375Srdivacky} 65202375Srdivacky 66202375Srdivacky/// SimplifyDemandedBits - This form of SimplifyDemandedBits simplifies the 67202375Srdivacky/// specified instruction operand if possible, updating it in place. It returns 68202375Srdivacky/// true if it made any change and false otherwise. 69249423Sdimbool InstCombiner::SimplifyDemandedBits(Use &U, APInt DemandedMask, 70202375Srdivacky APInt &KnownZero, APInt &KnownOne, 71202375Srdivacky unsigned Depth) { 72202375Srdivacky Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask, 73202375Srdivacky KnownZero, KnownOne, Depth); 74202375Srdivacky if (NewVal == 0) return false; 75202375Srdivacky U = NewVal; 76202375Srdivacky return true; 77202375Srdivacky} 78202375Srdivacky 79202375Srdivacky 80202375Srdivacky/// SimplifyDemandedUseBits - This function attempts to replace V with a simpler 81202375Srdivacky/// value based on the demanded bits. When this function is called, it is known 82202375Srdivacky/// that only the bits set in DemandedMask of the result of V are ever used 83202375Srdivacky/// downstream. Consequently, depending on the mask and V, it may be possible 84202375Srdivacky/// to replace V with a constant or one of its operands. In such cases, this 85202375Srdivacky/// function does the replacement and returns true. In all other cases, it 86202375Srdivacky/// returns false after analyzing the expression and setting KnownOne and known 87202375Srdivacky/// to be one in the expression. KnownZero contains all the bits that are known 88202375Srdivacky/// to be zero in the expression. These are provided to potentially allow the 89202375Srdivacky/// caller (which might recursively be SimplifyDemandedBits itself) to simplify 90249423Sdim/// the expression. KnownOne and KnownZero always follow the invariant that 91202375Srdivacky/// KnownOne & KnownZero == 0. That is, a bit can't be both 1 and 0. Note that 92202375Srdivacky/// the bits in KnownOne and KnownZero may only be accurate for those bits set 93202375Srdivacky/// in DemandedMask. Note also that the bitwidth of V, DemandedMask, KnownZero 94202375Srdivacky/// and KnownOne must all be the same. 95202375Srdivacky/// 96202375Srdivacky/// This returns null if it did not change anything and it permits no 97202375Srdivacky/// simplification. This returns V itself if it did some simplification of V's 98202375Srdivacky/// operands based on the information about what bits are demanded. This returns 99202375Srdivacky/// some other non-null value if it found out that V is equal to another value 100202375Srdivacky/// in the context where the specified bits are demanded, but not for all users. 101202375SrdivackyValue *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, 102202375Srdivacky APInt &KnownZero, APInt &KnownOne, 103202375Srdivacky unsigned Depth) { 104202375Srdivacky assert(V != 0 && "Null pointer of Value???"); 105202375Srdivacky assert(Depth <= 6 && "Limit Search Depth"); 106202375Srdivacky uint32_t BitWidth = DemandedMask.getBitWidth(); 107226633Sdim Type *VTy = V->getType(); 108204642Srdivacky assert((TD || !VTy->isPointerTy()) && 109202375Srdivacky "SimplifyDemandedBits needs to know bit widths!"); 110202375Srdivacky assert((!TD || TD->getTypeSizeInBits(VTy->getScalarType()) == BitWidth) && 111203954Srdivacky (!VTy->isIntOrIntVectorTy() || 112202375Srdivacky VTy->getScalarSizeInBits() == BitWidth) && 113202375Srdivacky KnownZero.getBitWidth() == BitWidth && 114202375Srdivacky KnownOne.getBitWidth() == BitWidth && 115202375Srdivacky "Value *V, DemandedMask, KnownZero and KnownOne " 116202375Srdivacky "must have same BitWidth"); 117202375Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 118202375Srdivacky // We know all of the bits for a constant! 119202375Srdivacky KnownOne = CI->getValue() & DemandedMask; 120202375Srdivacky KnownZero = ~KnownOne & DemandedMask; 121202375Srdivacky return 0; 122202375Srdivacky } 123202375Srdivacky if (isa<ConstantPointerNull>(V)) { 124202375Srdivacky // We know all of the bits for a constant! 125218893Sdim KnownOne.clearAllBits(); 126202375Srdivacky KnownZero = DemandedMask; 127202375Srdivacky return 0; 128202375Srdivacky } 129202375Srdivacky 130218893Sdim KnownZero.clearAllBits(); 131218893Sdim KnownOne.clearAllBits(); 132202375Srdivacky if (DemandedMask == 0) { // Not demanding any bits from V. 133202375Srdivacky if (isa<UndefValue>(V)) 134202375Srdivacky return 0; 135202375Srdivacky return UndefValue::get(VTy); 136202375Srdivacky } 137249423Sdim 138202375Srdivacky if (Depth == 6) // Limit search depth. 139202375Srdivacky return 0; 140249423Sdim 141202375Srdivacky APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 142203954Srdivacky APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); 143202375Srdivacky 144202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 145202375Srdivacky if (!I) { 146234353Sdim ComputeMaskedBits(V, KnownZero, KnownOne, Depth); 147202375Srdivacky return 0; // Only analyze instructions. 148202375Srdivacky } 149202375Srdivacky 150202375Srdivacky // If there are multiple uses of this value and we aren't at the root, then 151202375Srdivacky // we can't do any simplifications of the operands, because DemandedMask 152202375Srdivacky // only reflects the bits demanded by *one* of the users. 153202375Srdivacky if (Depth != 0 && !I->hasOneUse()) { 154202375Srdivacky // Despite the fact that we can't simplify this instruction in all User's 155202375Srdivacky // context, we can at least compute the knownzero/knownone bits, and we can 156202375Srdivacky // do simplifications that apply to *just* the one user if we know that 157202375Srdivacky // this instruction has a simpler value in that context. 158202375Srdivacky if (I->getOpcode() == Instruction::And) { 159202375Srdivacky // If either the LHS or the RHS are Zero, the result is zero. 160234353Sdim ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1); 161234353Sdim ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 162249423Sdim 163202375Srdivacky // If all of the demanded bits are known 1 on one side, return the other. 164202375Srdivacky // These bits cannot contribute to the result of the 'and' in this 165202375Srdivacky // context. 166249423Sdim if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == 167202375Srdivacky (DemandedMask & ~LHSKnownZero)) 168202375Srdivacky return I->getOperand(0); 169249423Sdim if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == 170202375Srdivacky (DemandedMask & ~RHSKnownZero)) 171202375Srdivacky return I->getOperand(1); 172249423Sdim 173202375Srdivacky // If all of the demanded bits in the inputs are known zeros, return zero. 174202375Srdivacky if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) 175202375Srdivacky return Constant::getNullValue(VTy); 176249423Sdim 177202375Srdivacky } else if (I->getOpcode() == Instruction::Or) { 178202375Srdivacky // We can simplify (X|Y) -> X or Y in the user's context if we know that 179202375Srdivacky // only bits from X or Y are demanded. 180249423Sdim 181202375Srdivacky // If either the LHS or the RHS are One, the result is One. 182234353Sdim ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1); 183234353Sdim ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 184249423Sdim 185202375Srdivacky // If all of the demanded bits are known zero on one side, return the 186202375Srdivacky // other. These bits cannot contribute to the result of the 'or' in this 187202375Srdivacky // context. 188249423Sdim if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == 189202375Srdivacky (DemandedMask & ~LHSKnownOne)) 190202375Srdivacky return I->getOperand(0); 191249423Sdim if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == 192202375Srdivacky (DemandedMask & ~RHSKnownOne)) 193202375Srdivacky return I->getOperand(1); 194249423Sdim 195202375Srdivacky // If all of the potentially set bits on one side are known to be set on 196202375Srdivacky // the other side, just use the 'other' side. 197249423Sdim if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == 198202375Srdivacky (DemandedMask & (~RHSKnownZero))) 199202375Srdivacky return I->getOperand(0); 200249423Sdim if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == 201202375Srdivacky (DemandedMask & (~LHSKnownZero))) 202202375Srdivacky return I->getOperand(1); 203249423Sdim } else if (I->getOpcode() == Instruction::Xor) { 204249423Sdim // We can simplify (X^Y) -> X or Y in the user's context if we know that 205249423Sdim // only bits from X or Y are demanded. 206249423Sdim 207249423Sdim ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1); 208249423Sdim ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 209249423Sdim 210249423Sdim // If all of the demanded bits are known zero on one side, return the 211249423Sdim // other. 212249423Sdim if ((DemandedMask & RHSKnownZero) == DemandedMask) 213249423Sdim return I->getOperand(0); 214249423Sdim if ((DemandedMask & LHSKnownZero) == DemandedMask) 215249423Sdim return I->getOperand(1); 216202375Srdivacky } 217249423Sdim 218202375Srdivacky // Compute the KnownZero/KnownOne bits to simplify things downstream. 219234353Sdim ComputeMaskedBits(I, KnownZero, KnownOne, Depth); 220202375Srdivacky return 0; 221202375Srdivacky } 222249423Sdim 223202375Srdivacky // If this is the root being simplified, allow it to have multiple uses, 224202375Srdivacky // just set the DemandedMask to all bits so that we can try to simplify the 225202375Srdivacky // operands. This allows visitTruncInst (for example) to simplify the 226202375Srdivacky // operand of a trunc without duplicating all the logic below. 227202375Srdivacky if (Depth == 0 && !V->hasOneUse()) 228202375Srdivacky DemandedMask = APInt::getAllOnesValue(BitWidth); 229249423Sdim 230202375Srdivacky switch (I->getOpcode()) { 231202375Srdivacky default: 232234353Sdim ComputeMaskedBits(I, KnownZero, KnownOne, Depth); 233202375Srdivacky break; 234202375Srdivacky case Instruction::And: 235202375Srdivacky // If either the LHS or the RHS are Zero, the result is zero. 236202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 237202375Srdivacky RHSKnownZero, RHSKnownOne, Depth+1) || 238202375Srdivacky SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownZero, 239202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1)) 240202375Srdivacky return I; 241249423Sdim assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 242249423Sdim assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 243202375Srdivacky 244202375Srdivacky // If all of the demanded bits are known 1 on one side, return the other. 245202375Srdivacky // These bits cannot contribute to the result of the 'and'. 246249423Sdim if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == 247202375Srdivacky (DemandedMask & ~LHSKnownZero)) 248202375Srdivacky return I->getOperand(0); 249249423Sdim if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == 250202375Srdivacky (DemandedMask & ~RHSKnownZero)) 251202375Srdivacky return I->getOperand(1); 252249423Sdim 253202375Srdivacky // If all of the demanded bits in the inputs are known zeros, return zero. 254202375Srdivacky if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) 255202375Srdivacky return Constant::getNullValue(VTy); 256249423Sdim 257202375Srdivacky // If the RHS is a constant, see if we can simplify it. 258202375Srdivacky if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnownZero)) 259202375Srdivacky return I; 260249423Sdim 261202375Srdivacky // Output known-1 bits are only known if set in both the LHS & RHS. 262203954Srdivacky KnownOne = RHSKnownOne & LHSKnownOne; 263202375Srdivacky // Output known-0 are known to be clear if zero in either the LHS | RHS. 264203954Srdivacky KnownZero = RHSKnownZero | LHSKnownZero; 265202375Srdivacky break; 266202375Srdivacky case Instruction::Or: 267202375Srdivacky // If either the LHS or the RHS are One, the result is One. 268249423Sdim if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 269202375Srdivacky RHSKnownZero, RHSKnownOne, Depth+1) || 270249423Sdim SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownOne, 271202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1)) 272202375Srdivacky return I; 273249423Sdim assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 274249423Sdim assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 275249423Sdim 276202375Srdivacky // If all of the demanded bits are known zero on one side, return the other. 277202375Srdivacky // These bits cannot contribute to the result of the 'or'. 278249423Sdim if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == 279202375Srdivacky (DemandedMask & ~LHSKnownOne)) 280202375Srdivacky return I->getOperand(0); 281249423Sdim if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == 282202375Srdivacky (DemandedMask & ~RHSKnownOne)) 283202375Srdivacky return I->getOperand(1); 284202375Srdivacky 285202375Srdivacky // If all of the potentially set bits on one side are known to be set on 286202375Srdivacky // the other side, just use the 'other' side. 287249423Sdim if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == 288202375Srdivacky (DemandedMask & (~RHSKnownZero))) 289202375Srdivacky return I->getOperand(0); 290249423Sdim if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == 291202375Srdivacky (DemandedMask & (~LHSKnownZero))) 292202375Srdivacky return I->getOperand(1); 293249423Sdim 294202375Srdivacky // If the RHS is a constant, see if we can simplify it. 295202375Srdivacky if (ShrinkDemandedConstant(I, 1, DemandedMask)) 296202375Srdivacky return I; 297249423Sdim 298202375Srdivacky // Output known-0 bits are only known if clear in both the LHS & RHS. 299203954Srdivacky KnownZero = RHSKnownZero & LHSKnownZero; 300202375Srdivacky // Output known-1 are known to be set if set in either the LHS | RHS. 301203954Srdivacky KnownOne = RHSKnownOne | LHSKnownOne; 302202375Srdivacky break; 303202375Srdivacky case Instruction::Xor: { 304202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 305202375Srdivacky RHSKnownZero, RHSKnownOne, Depth+1) || 306249423Sdim SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 307202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1)) 308202375Srdivacky return I; 309249423Sdim assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 310249423Sdim assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 311249423Sdim 312202375Srdivacky // If all of the demanded bits are known zero on one side, return the other. 313202375Srdivacky // These bits cannot contribute to the result of the 'xor'. 314202375Srdivacky if ((DemandedMask & RHSKnownZero) == DemandedMask) 315202375Srdivacky return I->getOperand(0); 316202375Srdivacky if ((DemandedMask & LHSKnownZero) == DemandedMask) 317202375Srdivacky return I->getOperand(1); 318249423Sdim 319202375Srdivacky // If all of the demanded bits are known to be zero on one side or the 320202375Srdivacky // other, turn this into an *inclusive* or. 321202375Srdivacky // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 322202375Srdivacky if ((DemandedMask & ~RHSKnownZero & ~LHSKnownZero) == 0) { 323249423Sdim Instruction *Or = 324202375Srdivacky BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1), 325202375Srdivacky I->getName()); 326223017Sdim return InsertNewInstWith(Or, *I); 327202375Srdivacky } 328249423Sdim 329202375Srdivacky // If all of the demanded bits on one side are known, and all of the set 330202375Srdivacky // bits on that side are also known to be set on the other side, turn this 331202375Srdivacky // into an AND, as we know the bits will be cleared. 332202375Srdivacky // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 333249423Sdim if ((DemandedMask & (RHSKnownZero|RHSKnownOne)) == DemandedMask) { 334202375Srdivacky // all known 335202375Srdivacky if ((RHSKnownOne & LHSKnownOne) == RHSKnownOne) { 336202375Srdivacky Constant *AndC = Constant::getIntegerValue(VTy, 337202375Srdivacky ~RHSKnownOne & DemandedMask); 338226633Sdim Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 339223017Sdim return InsertNewInstWith(And, *I); 340202375Srdivacky } 341202375Srdivacky } 342249423Sdim 343202375Srdivacky // If the RHS is a constant, see if we can simplify it. 344202375Srdivacky // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1. 345202375Srdivacky if (ShrinkDemandedConstant(I, 1, DemandedMask)) 346202375Srdivacky return I; 347249423Sdim 348202375Srdivacky // If our LHS is an 'and' and if it has one use, and if any of the bits we 349202375Srdivacky // are flipping are known to be set, then the xor is just resetting those 350202375Srdivacky // bits to zero. We can just knock out bits from the 'and' and the 'xor', 351202375Srdivacky // simplifying both of them. 352202375Srdivacky if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0))) 353202375Srdivacky if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() && 354202375Srdivacky isa<ConstantInt>(I->getOperand(1)) && 355202375Srdivacky isa<ConstantInt>(LHSInst->getOperand(1)) && 356202375Srdivacky (LHSKnownOne & RHSKnownOne & DemandedMask) != 0) { 357202375Srdivacky ConstantInt *AndRHS = cast<ConstantInt>(LHSInst->getOperand(1)); 358202375Srdivacky ConstantInt *XorRHS = cast<ConstantInt>(I->getOperand(1)); 359202375Srdivacky APInt NewMask = ~(LHSKnownOne & RHSKnownOne & DemandedMask); 360249423Sdim 361202375Srdivacky Constant *AndC = 362202375Srdivacky ConstantInt::get(I->getType(), NewMask & AndRHS->getValue()); 363226633Sdim Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 364223017Sdim InsertNewInstWith(NewAnd, *I); 365249423Sdim 366202375Srdivacky Constant *XorC = 367202375Srdivacky ConstantInt::get(I->getType(), NewMask & XorRHS->getValue()); 368226633Sdim Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC); 369223017Sdim return InsertNewInstWith(NewXor, *I); 370202375Srdivacky } 371203954Srdivacky 372203954Srdivacky // Output known-0 bits are known if clear or set in both the LHS & RHS. 373203954Srdivacky KnownZero= (RHSKnownZero & LHSKnownZero) | (RHSKnownOne & LHSKnownOne); 374203954Srdivacky // Output known-1 are known to be set if set in only one of the LHS, RHS. 375203954Srdivacky KnownOne = (RHSKnownZero & LHSKnownOne) | (RHSKnownOne & LHSKnownZero); 376202375Srdivacky break; 377202375Srdivacky } 378202375Srdivacky case Instruction::Select: 379202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(2), DemandedMask, 380202375Srdivacky RHSKnownZero, RHSKnownOne, Depth+1) || 381249423Sdim SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 382202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1)) 383202375Srdivacky return I; 384249423Sdim assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 385249423Sdim assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 386249423Sdim 387202375Srdivacky // If the operands are constants, see if we can simplify them. 388202375Srdivacky if (ShrinkDemandedConstant(I, 1, DemandedMask) || 389202375Srdivacky ShrinkDemandedConstant(I, 2, DemandedMask)) 390202375Srdivacky return I; 391249423Sdim 392202375Srdivacky // Only known if known in both the LHS and RHS. 393203954Srdivacky KnownOne = RHSKnownOne & LHSKnownOne; 394203954Srdivacky KnownZero = RHSKnownZero & LHSKnownZero; 395202375Srdivacky break; 396202375Srdivacky case Instruction::Trunc: { 397202375Srdivacky unsigned truncBf = I->getOperand(0)->getType()->getScalarSizeInBits(); 398218893Sdim DemandedMask = DemandedMask.zext(truncBf); 399218893Sdim KnownZero = KnownZero.zext(truncBf); 400218893Sdim KnownOne = KnownOne.zext(truncBf); 401249423Sdim if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 402203954Srdivacky KnownZero, KnownOne, Depth+1)) 403202375Srdivacky return I; 404218893Sdim DemandedMask = DemandedMask.trunc(BitWidth); 405218893Sdim KnownZero = KnownZero.trunc(BitWidth); 406218893Sdim KnownOne = KnownOne.trunc(BitWidth); 407249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 408202375Srdivacky break; 409202375Srdivacky } 410202375Srdivacky case Instruction::BitCast: 411203954Srdivacky if (!I->getOperand(0)->getType()->isIntOrIntVectorTy()) 412203954Srdivacky return 0; // vector->int or fp->int? 413202375Srdivacky 414226633Sdim if (VectorType *DstVTy = dyn_cast<VectorType>(I->getType())) { 415226633Sdim if (VectorType *SrcVTy = 416202375Srdivacky dyn_cast<VectorType>(I->getOperand(0)->getType())) { 417202375Srdivacky if (DstVTy->getNumElements() != SrcVTy->getNumElements()) 418202375Srdivacky // Don't touch a bitcast between vectors of different element counts. 419203954Srdivacky return 0; 420202375Srdivacky } else 421202375Srdivacky // Don't touch a scalar-to-vector bitcast. 422203954Srdivacky return 0; 423204642Srdivacky } else if (I->getOperand(0)->getType()->isVectorTy()) 424202375Srdivacky // Don't touch a vector-to-scalar bitcast. 425203954Srdivacky return 0; 426202375Srdivacky 427202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 428203954Srdivacky KnownZero, KnownOne, Depth+1)) 429202375Srdivacky return I; 430249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 431202375Srdivacky break; 432202375Srdivacky case Instruction::ZExt: { 433202375Srdivacky // Compute the bits in the result that are not present in the input. 434202375Srdivacky unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); 435249423Sdim 436218893Sdim DemandedMask = DemandedMask.trunc(SrcBitWidth); 437218893Sdim KnownZero = KnownZero.trunc(SrcBitWidth); 438218893Sdim KnownOne = KnownOne.trunc(SrcBitWidth); 439202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 440203954Srdivacky KnownZero, KnownOne, Depth+1)) 441202375Srdivacky return I; 442218893Sdim DemandedMask = DemandedMask.zext(BitWidth); 443218893Sdim KnownZero = KnownZero.zext(BitWidth); 444218893Sdim KnownOne = KnownOne.zext(BitWidth); 445249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 446202375Srdivacky // The top bits are known to be zero. 447203954Srdivacky KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 448202375Srdivacky break; 449202375Srdivacky } 450202375Srdivacky case Instruction::SExt: { 451202375Srdivacky // Compute the bits in the result that are not present in the input. 452202375Srdivacky unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); 453249423Sdim 454249423Sdim APInt InputDemandedBits = DemandedMask & 455202375Srdivacky APInt::getLowBitsSet(BitWidth, SrcBitWidth); 456202375Srdivacky 457202375Srdivacky APInt NewBits(APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth)); 458202375Srdivacky // If any of the sign extended bits are demanded, we know that the sign 459202375Srdivacky // bit is demanded. 460202375Srdivacky if ((NewBits & DemandedMask) != 0) 461218893Sdim InputDemandedBits.setBit(SrcBitWidth-1); 462249423Sdim 463218893Sdim InputDemandedBits = InputDemandedBits.trunc(SrcBitWidth); 464218893Sdim KnownZero = KnownZero.trunc(SrcBitWidth); 465218893Sdim KnownOne = KnownOne.trunc(SrcBitWidth); 466202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), InputDemandedBits, 467203954Srdivacky KnownZero, KnownOne, Depth+1)) 468202375Srdivacky return I; 469218893Sdim InputDemandedBits = InputDemandedBits.zext(BitWidth); 470218893Sdim KnownZero = KnownZero.zext(BitWidth); 471218893Sdim KnownOne = KnownOne.zext(BitWidth); 472249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 473249423Sdim 474202375Srdivacky // If the sign bit of the input is known set or clear, then we know the 475202375Srdivacky // top bits of the result. 476202375Srdivacky 477202375Srdivacky // If the input sign bit is known zero, or if the NewBits are not demanded 478202375Srdivacky // convert this into a zero extension. 479203954Srdivacky if (KnownZero[SrcBitWidth-1] || (NewBits & ~DemandedMask) == NewBits) { 480202375Srdivacky // Convert to ZExt cast 481202375Srdivacky CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName()); 482223017Sdim return InsertNewInstWith(NewCast, *I); 483203954Srdivacky } else if (KnownOne[SrcBitWidth-1]) { // Input sign bit known set 484203954Srdivacky KnownOne |= NewBits; 485202375Srdivacky } 486202375Srdivacky break; 487202375Srdivacky } 488202375Srdivacky case Instruction::Add: { 489202375Srdivacky // Figure out what the input bits are. If the top bits of the and result 490202375Srdivacky // are not demanded, then the add doesn't demand them from its input 491202375Srdivacky // either. 492202375Srdivacky unsigned NLZ = DemandedMask.countLeadingZeros(); 493249423Sdim 494202375Srdivacky // If there is a constant on the RHS, there are a variety of xformations 495202375Srdivacky // we can do. 496202375Srdivacky if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) { 497202375Srdivacky // If null, this should be simplified elsewhere. Some of the xforms here 498202375Srdivacky // won't work if the RHS is zero. 499202375Srdivacky if (RHS->isZero()) 500202375Srdivacky break; 501249423Sdim 502202375Srdivacky // If the top bit of the output is demanded, demand everything from the 503202375Srdivacky // input. Otherwise, we demand all the input bits except NLZ top bits. 504202375Srdivacky APInt InDemandedBits(APInt::getLowBitsSet(BitWidth, BitWidth - NLZ)); 505202375Srdivacky 506202375Srdivacky // Find information about known zero/one bits in the input. 507249423Sdim if (SimplifyDemandedBits(I->getOperandUse(0), InDemandedBits, 508202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1)) 509202375Srdivacky return I; 510202375Srdivacky 511202375Srdivacky // If the RHS of the add has bits set that can't affect the input, reduce 512202375Srdivacky // the constant. 513202375Srdivacky if (ShrinkDemandedConstant(I, 1, InDemandedBits)) 514202375Srdivacky return I; 515249423Sdim 516202375Srdivacky // Avoid excess work. 517202375Srdivacky if (LHSKnownZero == 0 && LHSKnownOne == 0) 518202375Srdivacky break; 519249423Sdim 520202375Srdivacky // Turn it into OR if input bits are zero. 521202375Srdivacky if ((LHSKnownZero & RHS->getValue()) == RHS->getValue()) { 522202375Srdivacky Instruction *Or = 523202375Srdivacky BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1), 524202375Srdivacky I->getName()); 525223017Sdim return InsertNewInstWith(Or, *I); 526202375Srdivacky } 527249423Sdim 528202375Srdivacky // We can say something about the output known-zero and known-one bits, 529202375Srdivacky // depending on potential carries from the input constant and the 530202375Srdivacky // unknowns. For example if the LHS is known to have at most the 0x0F0F0 531202375Srdivacky // bits set and the RHS constant is 0x01001, then we know we have a known 532202375Srdivacky // one mask of 0x00001 and a known zero mask of 0xE0F0E. 533249423Sdim 534202375Srdivacky // To compute this, we first compute the potential carry bits. These are 535202375Srdivacky // the bits which may be modified. I'm not aware of a better way to do 536202375Srdivacky // this scan. 537202375Srdivacky const APInt &RHSVal = RHS->getValue(); 538202375Srdivacky APInt CarryBits((~LHSKnownZero + RHSVal) ^ (~LHSKnownZero ^ RHSVal)); 539249423Sdim 540202375Srdivacky // Now that we know which bits have carries, compute the known-1/0 sets. 541249423Sdim 542202375Srdivacky // Bits are known one if they are known zero in one operand and one in the 543202375Srdivacky // other, and there is no input carry. 544249423Sdim KnownOne = ((LHSKnownZero & RHSVal) | 545203954Srdivacky (LHSKnownOne & ~RHSVal)) & ~CarryBits; 546249423Sdim 547202375Srdivacky // Bits are known zero if they are known zero in both operands and there 548202375Srdivacky // is no input carry. 549203954Srdivacky KnownZero = LHSKnownZero & ~RHSVal & ~CarryBits; 550202375Srdivacky } else { 551202375Srdivacky // If the high-bits of this ADD are not demanded, then it does not demand 552202375Srdivacky // the high bits of its LHS or RHS. 553202375Srdivacky if (DemandedMask[BitWidth-1] == 0) { 554202375Srdivacky // Right fill the mask of bits for this ADD to demand the most 555202375Srdivacky // significant bit and all those below it. 556202375Srdivacky APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ)); 557202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps, 558202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1) || 559202375Srdivacky SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps, 560202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1)) 561202375Srdivacky return I; 562202375Srdivacky } 563202375Srdivacky } 564202375Srdivacky break; 565202375Srdivacky } 566202375Srdivacky case Instruction::Sub: 567202375Srdivacky // If the high-bits of this SUB are not demanded, then it does not demand 568202375Srdivacky // the high bits of its LHS or RHS. 569202375Srdivacky if (DemandedMask[BitWidth-1] == 0) { 570202375Srdivacky // Right fill the mask of bits for this SUB to demand the most 571202375Srdivacky // significant bit and all those below it. 572202375Srdivacky uint32_t NLZ = DemandedMask.countLeadingZeros(); 573202375Srdivacky APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ)); 574202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps, 575202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1) || 576202375Srdivacky SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps, 577202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1)) 578202375Srdivacky return I; 579202375Srdivacky } 580234353Sdim 581202375Srdivacky // Otherwise just hand the sub off to ComputeMaskedBits to fill in 582202375Srdivacky // the known zeros and ones. 583234353Sdim ComputeMaskedBits(V, KnownZero, KnownOne, Depth); 584234353Sdim 585234353Sdim // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known 586234353Sdim // zero. 587234353Sdim if (ConstantInt *C0 = dyn_cast<ConstantInt>(I->getOperand(0))) { 588234353Sdim APInt I0 = C0->getValue(); 589234353Sdim if ((I0 + 1).isPowerOf2() && (I0 | KnownZero).isAllOnesValue()) { 590234353Sdim Instruction *Xor = BinaryOperator::CreateXor(I->getOperand(1), C0); 591234353Sdim return InsertNewInstWith(Xor, *I); 592234353Sdim } 593234353Sdim } 594202375Srdivacky break; 595202375Srdivacky case Instruction::Shl: 596202375Srdivacky if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 597249423Sdim { 598249423Sdim Value *VarX; ConstantInt *C1; 599249423Sdim if (match(I->getOperand(0), m_Shr(m_Value(VarX), m_ConstantInt(C1)))) { 600249423Sdim Instruction *Shr = cast<Instruction>(I->getOperand(0)); 601249423Sdim Value *R = SimplifyShrShlDemandedBits(Shr, I, DemandedMask, 602249423Sdim KnownZero, KnownOne); 603249423Sdim if (R) 604249423Sdim return R; 605249423Sdim } 606249423Sdim } 607249423Sdim 608218893Sdim uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 609202375Srdivacky APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt)); 610249423Sdim 611218893Sdim // If the shift is NUW/NSW, then it does demand the high bits. 612218893Sdim ShlOperator *IOp = cast<ShlOperator>(I); 613218893Sdim if (IOp->hasNoSignedWrap()) 614218893Sdim DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1); 615218893Sdim else if (IOp->hasNoUnsignedWrap()) 616218893Sdim DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 617249423Sdim 618249423Sdim if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, 619203954Srdivacky KnownZero, KnownOne, Depth+1)) 620202375Srdivacky return I; 621203954Srdivacky assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 622203954Srdivacky KnownZero <<= ShiftAmt; 623203954Srdivacky KnownOne <<= ShiftAmt; 624202375Srdivacky // low bits known zero. 625202375Srdivacky if (ShiftAmt) 626203954Srdivacky KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 627202375Srdivacky } 628202375Srdivacky break; 629202375Srdivacky case Instruction::LShr: 630202375Srdivacky // For a logical shift right 631202375Srdivacky if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 632218893Sdim uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 633249423Sdim 634202375Srdivacky // Unsigned shift right. 635202375Srdivacky APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 636249423Sdim 637218893Sdim // If the shift is exact, then it does demand the low bits (and knows that 638218893Sdim // they are zero). 639218893Sdim if (cast<LShrOperator>(I)->isExact()) 640218893Sdim DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 641249423Sdim 642202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, 643203954Srdivacky KnownZero, KnownOne, Depth+1)) 644202375Srdivacky return I; 645203954Srdivacky assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 646203954Srdivacky KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 647203954Srdivacky KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 648202375Srdivacky if (ShiftAmt) { 649202375Srdivacky // Compute the new bits that are at the top now. 650202375Srdivacky APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 651203954Srdivacky KnownZero |= HighBits; // high bits known zero. 652202375Srdivacky } 653202375Srdivacky } 654202375Srdivacky break; 655202375Srdivacky case Instruction::AShr: 656202375Srdivacky // If this is an arithmetic shift right and only the low-bit is set, we can 657202375Srdivacky // always convert this into a logical shr, even if the shift amount is 658202375Srdivacky // variable. The low bit of the shift cannot be an input sign bit unless 659202375Srdivacky // the shift amount is >= the size of the datatype, which is undefined. 660202375Srdivacky if (DemandedMask == 1) { 661202375Srdivacky // Perform the logical shift right. 662202375Srdivacky Instruction *NewVal = BinaryOperator::CreateLShr( 663202375Srdivacky I->getOperand(0), I->getOperand(1), I->getName()); 664223017Sdim return InsertNewInstWith(NewVal, *I); 665249423Sdim } 666202375Srdivacky 667202375Srdivacky // If the sign bit is the only bit demanded by this ashr, then there is no 668202375Srdivacky // need to do it, the shift doesn't change the high bit. 669202375Srdivacky if (DemandedMask.isSignBit()) 670202375Srdivacky return I->getOperand(0); 671249423Sdim 672202375Srdivacky if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 673218893Sdim uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 674249423Sdim 675202375Srdivacky // Signed shift right. 676202375Srdivacky APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 677202375Srdivacky // If any of the "high bits" are demanded, we should set the sign bit as 678202375Srdivacky // demanded. 679202375Srdivacky if (DemandedMask.countLeadingZeros() <= ShiftAmt) 680218893Sdim DemandedMaskIn.setBit(BitWidth-1); 681249423Sdim 682218893Sdim // If the shift is exact, then it does demand the low bits (and knows that 683218893Sdim // they are zero). 684218893Sdim if (cast<AShrOperator>(I)->isExact()) 685218893Sdim DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 686249423Sdim 687202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, 688203954Srdivacky KnownZero, KnownOne, Depth+1)) 689202375Srdivacky return I; 690203954Srdivacky assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 691202375Srdivacky // Compute the new bits that are at the top now. 692202375Srdivacky APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 693203954Srdivacky KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 694203954Srdivacky KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 695249423Sdim 696202375Srdivacky // Handle the sign bits. 697202375Srdivacky APInt SignBit(APInt::getSignBit(BitWidth)); 698202375Srdivacky // Adjust to where it is now in the mask. 699249423Sdim SignBit = APIntOps::lshr(SignBit, ShiftAmt); 700249423Sdim 701202375Srdivacky // If the input sign bit is known to be zero, or if none of the top bits 702202375Srdivacky // are demanded, turn this into an unsigned shift right. 703249423Sdim if (BitWidth <= ShiftAmt || KnownZero[BitWidth-ShiftAmt-1] || 704202375Srdivacky (HighBits & ~DemandedMask) == HighBits) { 705202375Srdivacky // Perform the logical shift right. 706234353Sdim BinaryOperator *NewVal = BinaryOperator::CreateLShr(I->getOperand(0), 707234353Sdim SA, I->getName()); 708234353Sdim NewVal->setIsExact(cast<BinaryOperator>(I)->isExact()); 709223017Sdim return InsertNewInstWith(NewVal, *I); 710203954Srdivacky } else if ((KnownOne & SignBit) != 0) { // New bits are known one. 711203954Srdivacky KnownOne |= HighBits; 712202375Srdivacky } 713202375Srdivacky } 714202375Srdivacky break; 715202375Srdivacky case Instruction::SRem: 716202375Srdivacky if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 717221345Sdim // X % -1 demands all the bits because we don't want to introduce 718221345Sdim // INT_MIN % -1 (== undef) by accident. 719221345Sdim if (Rem->isAllOnesValue()) 720221345Sdim break; 721202375Srdivacky APInt RA = Rem->getValue().abs(); 722202375Srdivacky if (RA.isPowerOf2()) { 723202375Srdivacky if (DemandedMask.ult(RA)) // srem won't affect demanded bits 724202375Srdivacky return I->getOperand(0); 725202375Srdivacky 726202375Srdivacky APInt LowBits = RA - 1; 727202375Srdivacky APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 728202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), Mask2, 729202375Srdivacky LHSKnownZero, LHSKnownOne, Depth+1)) 730202375Srdivacky return I; 731202375Srdivacky 732203954Srdivacky // The low bits of LHS are unchanged by the srem. 733203954Srdivacky KnownZero = LHSKnownZero & LowBits; 734203954Srdivacky KnownOne = LHSKnownOne & LowBits; 735203954Srdivacky 736203954Srdivacky // If LHS is non-negative or has all low bits zero, then the upper bits 737203954Srdivacky // are all zero. 738202375Srdivacky if (LHSKnownZero[BitWidth-1] || ((LHSKnownZero & LowBits) == LowBits)) 739203954Srdivacky KnownZero |= ~LowBits; 740202375Srdivacky 741203954Srdivacky // If LHS is negative and not all low bits are zero, then the upper bits 742203954Srdivacky // are all one. 743203954Srdivacky if (LHSKnownOne[BitWidth-1] && ((LHSKnownOne & LowBits) != 0)) 744203954Srdivacky KnownOne |= ~LowBits; 745202375Srdivacky 746249423Sdim assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 747202375Srdivacky } 748202375Srdivacky } 749221345Sdim 750221345Sdim // The sign bit is the LHS's sign bit, except when the result of the 751221345Sdim // remainder is zero. 752221345Sdim if (DemandedMask.isNegative() && KnownZero.isNonNegative()) { 753221345Sdim APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 754234353Sdim ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 755221345Sdim // If it's known zero, our sign bit is also zero. 756221345Sdim if (LHSKnownZero.isNegative()) 757221345Sdim KnownZero |= LHSKnownZero; 758221345Sdim } 759202375Srdivacky break; 760202375Srdivacky case Instruction::URem: { 761202375Srdivacky APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0); 762202375Srdivacky APInt AllOnes = APInt::getAllOnesValue(BitWidth); 763202375Srdivacky if (SimplifyDemandedBits(I->getOperandUse(0), AllOnes, 764202375Srdivacky KnownZero2, KnownOne2, Depth+1) || 765202375Srdivacky SimplifyDemandedBits(I->getOperandUse(1), AllOnes, 766202375Srdivacky KnownZero2, KnownOne2, Depth+1)) 767202375Srdivacky return I; 768202375Srdivacky 769202375Srdivacky unsigned Leaders = KnownZero2.countLeadingOnes(); 770202375Srdivacky Leaders = std::max(Leaders, 771202375Srdivacky KnownZero2.countLeadingOnes()); 772202375Srdivacky KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask; 773202375Srdivacky break; 774202375Srdivacky } 775202375Srdivacky case Instruction::Call: 776202375Srdivacky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 777202375Srdivacky switch (II->getIntrinsicID()) { 778202375Srdivacky default: break; 779202375Srdivacky case Intrinsic::bswap: { 780202375Srdivacky // If the only bits demanded come from one byte of the bswap result, 781202375Srdivacky // just shift the input byte into position to eliminate the bswap. 782202375Srdivacky unsigned NLZ = DemandedMask.countLeadingZeros(); 783202375Srdivacky unsigned NTZ = DemandedMask.countTrailingZeros(); 784249423Sdim 785202375Srdivacky // Round NTZ down to the next byte. If we have 11 trailing zeros, then 786202375Srdivacky // we need all the bits down to bit 8. Likewise, round NLZ. If we 787202375Srdivacky // have 14 leading zeros, round to 8. 788202375Srdivacky NLZ &= ~7; 789202375Srdivacky NTZ &= ~7; 790202375Srdivacky // If we need exactly one byte, we can do this transformation. 791202375Srdivacky if (BitWidth-NLZ-NTZ == 8) { 792202375Srdivacky unsigned ResultBit = NTZ; 793202375Srdivacky unsigned InputBit = BitWidth-NTZ-8; 794249423Sdim 795202375Srdivacky // Replace this with either a left or right shift to get the byte into 796202375Srdivacky // the right place. 797202375Srdivacky Instruction *NewVal; 798202375Srdivacky if (InputBit > ResultBit) 799210299Sed NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0), 800202375Srdivacky ConstantInt::get(I->getType(), InputBit-ResultBit)); 801202375Srdivacky else 802210299Sed NewVal = BinaryOperator::CreateShl(II->getArgOperand(0), 803202375Srdivacky ConstantInt::get(I->getType(), ResultBit-InputBit)); 804202375Srdivacky NewVal->takeName(I); 805223017Sdim return InsertNewInstWith(NewVal, *I); 806202375Srdivacky } 807249423Sdim 808202375Srdivacky // TODO: Could compute known zero/one bits based on the input. 809202375Srdivacky break; 810202375Srdivacky } 811223017Sdim case Intrinsic::x86_sse42_crc32_64_8: 812223017Sdim case Intrinsic::x86_sse42_crc32_64_64: 813223017Sdim KnownZero = APInt::getHighBitsSet(64, 32); 814223017Sdim return 0; 815202375Srdivacky } 816202375Srdivacky } 817234353Sdim ComputeMaskedBits(V, KnownZero, KnownOne, Depth); 818202375Srdivacky break; 819202375Srdivacky } 820249423Sdim 821202375Srdivacky // If the client is only demanding bits that we know, return the known 822202375Srdivacky // constant. 823203954Srdivacky if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) 824203954Srdivacky return Constant::getIntegerValue(VTy, KnownOne); 825203954Srdivacky return 0; 826202375Srdivacky} 827202375Srdivacky 828249423Sdim/// Helper routine of SimplifyDemandedUseBits. It tries to simplify 829249423Sdim/// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into 830249423Sdim/// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign 831249423Sdim/// of "C2-C1". 832249423Sdim/// 833249423Sdim/// Suppose E1 and E2 are generally different in bits S={bm, bm+1, 834249423Sdim/// ..., bn}, without considering the specific value X is holding. 835249423Sdim/// This transformation is legal iff one of following conditions is hold: 836249423Sdim/// 1) All the bit in S are 0, in this case E1 == E2. 837249423Sdim/// 2) We don't care those bits in S, per the input DemandedMask. 838249423Sdim/// 3) Combination of 1) and 2). Some bits in S are 0, and we don't care the 839249423Sdim/// rest bits. 840249423Sdim/// 841249423Sdim/// Currently we only test condition 2). 842249423Sdim/// 843249423Sdim/// As with SimplifyDemandedUseBits, it returns NULL if the simplification was 844249423Sdim/// not successful. 845249423SdimValue *InstCombiner::SimplifyShrShlDemandedBits(Instruction *Shr, 846249423Sdim Instruction *Shl, APInt DemandedMask, APInt &KnownZero, APInt &KnownOne) { 847202375Srdivacky 848255076Sdim const APInt &ShlOp1 = cast<ConstantInt>(Shl->getOperand(1))->getValue(); 849255076Sdim const APInt &ShrOp1 = cast<ConstantInt>(Shr->getOperand(1))->getValue(); 850255076Sdim if (!ShlOp1 || !ShrOp1) 851255076Sdim return 0; // Noop. 852249423Sdim 853255076Sdim Value *VarX = Shr->getOperand(0); 854255076Sdim Type *Ty = VarX->getType(); 855255076Sdim unsigned BitWidth = Ty->getIntegerBitWidth(); 856255076Sdim if (ShlOp1.uge(BitWidth) || ShrOp1.uge(BitWidth)) 857255076Sdim return 0; // Undef. 858255076Sdim 859255076Sdim unsigned ShlAmt = ShlOp1.getZExtValue(); 860255076Sdim unsigned ShrAmt = ShrOp1.getZExtValue(); 861255076Sdim 862249423Sdim KnownOne.clearAllBits(); 863249423Sdim KnownZero = APInt::getBitsSet(KnownZero.getBitWidth(), 0, ShlAmt-1); 864249423Sdim KnownZero &= DemandedMask; 865249423Sdim 866255076Sdim APInt BitMask1(APInt::getAllOnesValue(BitWidth)); 867255076Sdim APInt BitMask2(APInt::getAllOnesValue(BitWidth)); 868249423Sdim 869249423Sdim bool isLshr = (Shr->getOpcode() == Instruction::LShr); 870249423Sdim BitMask1 = isLshr ? (BitMask1.lshr(ShrAmt) << ShlAmt) : 871249423Sdim (BitMask1.ashr(ShrAmt) << ShlAmt); 872249423Sdim 873249423Sdim if (ShrAmt <= ShlAmt) { 874249423Sdim BitMask2 <<= (ShlAmt - ShrAmt); 875249423Sdim } else { 876249423Sdim BitMask2 = isLshr ? BitMask2.lshr(ShrAmt - ShlAmt): 877249423Sdim BitMask2.ashr(ShrAmt - ShlAmt); 878249423Sdim } 879249423Sdim 880249423Sdim // Check if condition-2 (see the comment to this function) is satified. 881249423Sdim if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) { 882249423Sdim if (ShrAmt == ShlAmt) 883249423Sdim return VarX; 884249423Sdim 885249423Sdim if (!Shr->hasOneUse()) 886249423Sdim return 0; 887249423Sdim 888249423Sdim BinaryOperator *New; 889249423Sdim if (ShrAmt < ShlAmt) { 890249423Sdim Constant *Amt = ConstantInt::get(VarX->getType(), ShlAmt - ShrAmt); 891249423Sdim New = BinaryOperator::CreateShl(VarX, Amt); 892249423Sdim BinaryOperator *Orig = cast<BinaryOperator>(Shl); 893249423Sdim New->setHasNoSignedWrap(Orig->hasNoSignedWrap()); 894249423Sdim New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap()); 895249423Sdim } else { 896249423Sdim Constant *Amt = ConstantInt::get(VarX->getType(), ShrAmt - ShlAmt); 897249423Sdim New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) : 898249423Sdim BinaryOperator::CreateAShr(VarX, Amt); 899249423Sdim if (cast<BinaryOperator>(Shr)->isExact()) 900249423Sdim New->setIsExact(true); 901249423Sdim } 902249423Sdim 903249423Sdim return InsertNewInstWith(New, *Shl); 904249423Sdim } 905249423Sdim 906249423Sdim return 0; 907249423Sdim} 908249423Sdim 909202375Srdivacky/// SimplifyDemandedVectorElts - The specified value produces a vector with 910202375Srdivacky/// any number of elements. DemandedElts contains the set of elements that are 911202375Srdivacky/// actually used by the caller. This method analyzes which elements of the 912202375Srdivacky/// operand are undef and returns that information in UndefElts. 913202375Srdivacky/// 914202375Srdivacky/// If the information about demanded elements can be used to simplify the 915202375Srdivacky/// operation, the operation is simplified, then the resultant value is 916202375Srdivacky/// returned. This returns null if no change was made. 917202375SrdivackyValue *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, 918203954Srdivacky APInt &UndefElts, 919202375Srdivacky unsigned Depth) { 920202375Srdivacky unsigned VWidth = cast<VectorType>(V->getType())->getNumElements(); 921202375Srdivacky APInt EltMask(APInt::getAllOnesValue(VWidth)); 922202375Srdivacky assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!"); 923202375Srdivacky 924202375Srdivacky if (isa<UndefValue>(V)) { 925202375Srdivacky // If the entire vector is undefined, just return this info. 926202375Srdivacky UndefElts = EltMask; 927202375Srdivacky return 0; 928203954Srdivacky } 929249423Sdim 930203954Srdivacky if (DemandedElts == 0) { // If nothing is demanded, provide undef. 931202375Srdivacky UndefElts = EltMask; 932202375Srdivacky return UndefValue::get(V->getType()); 933202375Srdivacky } 934202375Srdivacky 935202375Srdivacky UndefElts = 0; 936249423Sdim 937234353Sdim // Handle ConstantAggregateZero, ConstantVector, ConstantDataSequential. 938234353Sdim if (Constant *C = dyn_cast<Constant>(V)) { 939234353Sdim // Check if this is identity. If so, return 0 since we are not simplifying 940234353Sdim // anything. 941234353Sdim if (DemandedElts.isAllOnesValue()) 942234353Sdim return 0; 943234353Sdim 944226633Sdim Type *EltTy = cast<VectorType>(V->getType())->getElementType(); 945202375Srdivacky Constant *Undef = UndefValue::get(EltTy); 946249423Sdim 947234353Sdim SmallVector<Constant*, 16> Elts; 948234353Sdim for (unsigned i = 0; i != VWidth; ++i) { 949202375Srdivacky if (!DemandedElts[i]) { // If not demanded, set to undef. 950202375Srdivacky Elts.push_back(Undef); 951218893Sdim UndefElts.setBit(i); 952234353Sdim continue; 953234353Sdim } 954249423Sdim 955234353Sdim Constant *Elt = C->getAggregateElement(i); 956234353Sdim if (Elt == 0) return 0; 957249423Sdim 958234353Sdim if (isa<UndefValue>(Elt)) { // Already undef. 959202375Srdivacky Elts.push_back(Undef); 960218893Sdim UndefElts.setBit(i); 961202375Srdivacky } else { // Otherwise, defined. 962234353Sdim Elts.push_back(Elt); 963202375Srdivacky } 964234353Sdim } 965249423Sdim 966202375Srdivacky // If we changed the constant, return it. 967234353Sdim Constant *NewCV = ConstantVector::get(Elts); 968234353Sdim return NewCV != C ? NewCV : 0; 969203954Srdivacky } 970249423Sdim 971202375Srdivacky // Limit search depth. 972202375Srdivacky if (Depth == 10) 973202375Srdivacky return 0; 974202375Srdivacky 975223017Sdim // If multiple users are using the root value, proceed with 976202375Srdivacky // simplification conservatively assuming that all elements 977202375Srdivacky // are needed. 978202375Srdivacky if (!V->hasOneUse()) { 979202375Srdivacky // Quit if we find multiple users of a non-root value though. 980202375Srdivacky // They'll be handled when it's their turn to be visited by 981202375Srdivacky // the main instcombine process. 982202375Srdivacky if (Depth != 0) 983202375Srdivacky // TODO: Just compute the UndefElts information recursively. 984202375Srdivacky return 0; 985202375Srdivacky 986202375Srdivacky // Conservatively assume that all elements are needed. 987202375Srdivacky DemandedElts = EltMask; 988202375Srdivacky } 989249423Sdim 990202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 991202375Srdivacky if (!I) return 0; // Only analyze instructions. 992249423Sdim 993202375Srdivacky bool MadeChange = false; 994202375Srdivacky APInt UndefElts2(VWidth, 0); 995202375Srdivacky Value *TmpV; 996202375Srdivacky switch (I->getOpcode()) { 997202375Srdivacky default: break; 998249423Sdim 999202375Srdivacky case Instruction::InsertElement: { 1000202375Srdivacky // If this is a variable index, we don't know which element it overwrites. 1001202375Srdivacky // demand exactly the same input as we produce. 1002202375Srdivacky ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2)); 1003202375Srdivacky if (Idx == 0) { 1004202375Srdivacky // Note that we can't propagate undef elt info, because we don't know 1005202375Srdivacky // which elt is getting updated. 1006202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 1007202375Srdivacky UndefElts2, Depth+1); 1008202375Srdivacky if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1009202375Srdivacky break; 1010202375Srdivacky } 1011249423Sdim 1012202375Srdivacky // If this is inserting an element that isn't demanded, remove this 1013202375Srdivacky // insertelement. 1014202375Srdivacky unsigned IdxNo = Idx->getZExtValue(); 1015202375Srdivacky if (IdxNo >= VWidth || !DemandedElts[IdxNo]) { 1016202375Srdivacky Worklist.Add(I); 1017202375Srdivacky return I->getOperand(0); 1018202375Srdivacky } 1019249423Sdim 1020202375Srdivacky // Otherwise, the element inserted overwrites whatever was there, so the 1021202375Srdivacky // input demanded set is simpler than the output set. 1022202375Srdivacky APInt DemandedElts2 = DemandedElts; 1023218893Sdim DemandedElts2.clearBit(IdxNo); 1024202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts2, 1025202375Srdivacky UndefElts, Depth+1); 1026202375Srdivacky if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1027202375Srdivacky 1028202375Srdivacky // The inserted element is defined. 1029218893Sdim UndefElts.clearBit(IdxNo); 1030202375Srdivacky break; 1031202375Srdivacky } 1032202375Srdivacky case Instruction::ShuffleVector: { 1033202375Srdivacky ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I); 1034202375Srdivacky uint64_t LHSVWidth = 1035202375Srdivacky cast<VectorType>(Shuffle->getOperand(0)->getType())->getNumElements(); 1036202375Srdivacky APInt LeftDemanded(LHSVWidth, 0), RightDemanded(LHSVWidth, 0); 1037202375Srdivacky for (unsigned i = 0; i < VWidth; i++) { 1038202375Srdivacky if (DemandedElts[i]) { 1039202375Srdivacky unsigned MaskVal = Shuffle->getMaskValue(i); 1040202375Srdivacky if (MaskVal != -1u) { 1041202375Srdivacky assert(MaskVal < LHSVWidth * 2 && 1042202375Srdivacky "shufflevector mask index out of range!"); 1043202375Srdivacky if (MaskVal < LHSVWidth) 1044218893Sdim LeftDemanded.setBit(MaskVal); 1045202375Srdivacky else 1046218893Sdim RightDemanded.setBit(MaskVal - LHSVWidth); 1047202375Srdivacky } 1048202375Srdivacky } 1049202375Srdivacky } 1050202375Srdivacky 1051202375Srdivacky APInt UndefElts4(LHSVWidth, 0); 1052202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(0), LeftDemanded, 1053202375Srdivacky UndefElts4, Depth+1); 1054202375Srdivacky if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1055202375Srdivacky 1056202375Srdivacky APInt UndefElts3(LHSVWidth, 0); 1057202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(1), RightDemanded, 1058202375Srdivacky UndefElts3, Depth+1); 1059202375Srdivacky if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 1060202375Srdivacky 1061202375Srdivacky bool NewUndefElts = false; 1062202375Srdivacky for (unsigned i = 0; i < VWidth; i++) { 1063202375Srdivacky unsigned MaskVal = Shuffle->getMaskValue(i); 1064202375Srdivacky if (MaskVal == -1u) { 1065218893Sdim UndefElts.setBit(i); 1066226633Sdim } else if (!DemandedElts[i]) { 1067226633Sdim NewUndefElts = true; 1068226633Sdim UndefElts.setBit(i); 1069202375Srdivacky } else if (MaskVal < LHSVWidth) { 1070202375Srdivacky if (UndefElts4[MaskVal]) { 1071202375Srdivacky NewUndefElts = true; 1072218893Sdim UndefElts.setBit(i); 1073202375Srdivacky } 1074202375Srdivacky } else { 1075202375Srdivacky if (UndefElts3[MaskVal - LHSVWidth]) { 1076202375Srdivacky NewUndefElts = true; 1077218893Sdim UndefElts.setBit(i); 1078202375Srdivacky } 1079202375Srdivacky } 1080202375Srdivacky } 1081202375Srdivacky 1082202375Srdivacky if (NewUndefElts) { 1083202375Srdivacky // Add additional discovered undefs. 1084234353Sdim SmallVector<Constant*, 16> Elts; 1085202375Srdivacky for (unsigned i = 0; i < VWidth; ++i) { 1086202375Srdivacky if (UndefElts[i]) 1087202375Srdivacky Elts.push_back(UndefValue::get(Type::getInt32Ty(I->getContext()))); 1088202375Srdivacky else 1089202375Srdivacky Elts.push_back(ConstantInt::get(Type::getInt32Ty(I->getContext()), 1090202375Srdivacky Shuffle->getMaskValue(i))); 1091202375Srdivacky } 1092202375Srdivacky I->setOperand(2, ConstantVector::get(Elts)); 1093202375Srdivacky MadeChange = true; 1094202375Srdivacky } 1095202375Srdivacky break; 1096202375Srdivacky } 1097239462Sdim case Instruction::Select: { 1098239462Sdim APInt LeftDemanded(DemandedElts), RightDemanded(DemandedElts); 1099239462Sdim if (ConstantVector* CV = dyn_cast<ConstantVector>(I->getOperand(0))) { 1100239462Sdim for (unsigned i = 0; i < VWidth; i++) { 1101239462Sdim if (CV->getAggregateElement(i)->isNullValue()) 1102239462Sdim LeftDemanded.clearBit(i); 1103239462Sdim else 1104239462Sdim RightDemanded.clearBit(i); 1105239462Sdim } 1106239462Sdim } 1107239462Sdim 1108239462Sdim TmpV = SimplifyDemandedVectorElts(I->getOperand(1), LeftDemanded, 1109239462Sdim UndefElts, Depth+1); 1110239462Sdim if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 1111239462Sdim 1112239462Sdim TmpV = SimplifyDemandedVectorElts(I->getOperand(2), RightDemanded, 1113239462Sdim UndefElts2, Depth+1); 1114239462Sdim if (TmpV) { I->setOperand(2, TmpV); MadeChange = true; } 1115249423Sdim 1116239462Sdim // Output elements are undefined if both are undefined. 1117239462Sdim UndefElts &= UndefElts2; 1118239462Sdim break; 1119239462Sdim } 1120202375Srdivacky case Instruction::BitCast: { 1121202375Srdivacky // Vector->vector casts only. 1122226633Sdim VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType()); 1123202375Srdivacky if (!VTy) break; 1124202375Srdivacky unsigned InVWidth = VTy->getNumElements(); 1125202375Srdivacky APInt InputDemandedElts(InVWidth, 0); 1126202375Srdivacky unsigned Ratio; 1127202375Srdivacky 1128202375Srdivacky if (VWidth == InVWidth) { 1129202375Srdivacky // If we are converting from <4 x i32> -> <4 x f32>, we demand the same 1130202375Srdivacky // elements as are demanded of us. 1131202375Srdivacky Ratio = 1; 1132202375Srdivacky InputDemandedElts = DemandedElts; 1133202375Srdivacky } else if (VWidth > InVWidth) { 1134202375Srdivacky // Untested so far. 1135202375Srdivacky break; 1136249423Sdim 1137202375Srdivacky // If there are more elements in the result than there are in the source, 1138202375Srdivacky // then an input element is live if any of the corresponding output 1139202375Srdivacky // elements are live. 1140202375Srdivacky Ratio = VWidth/InVWidth; 1141202375Srdivacky for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) { 1142202375Srdivacky if (DemandedElts[OutIdx]) 1143218893Sdim InputDemandedElts.setBit(OutIdx/Ratio); 1144202375Srdivacky } 1145202375Srdivacky } else { 1146202375Srdivacky // Untested so far. 1147202375Srdivacky break; 1148249423Sdim 1149202375Srdivacky // If there are more elements in the source than there are in the result, 1150202375Srdivacky // then an input element is live if the corresponding output element is 1151202375Srdivacky // live. 1152202375Srdivacky Ratio = InVWidth/VWidth; 1153202375Srdivacky for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) 1154202375Srdivacky if (DemandedElts[InIdx/Ratio]) 1155218893Sdim InputDemandedElts.setBit(InIdx); 1156202375Srdivacky } 1157249423Sdim 1158202375Srdivacky // div/rem demand all inputs, because they don't want divide by zero. 1159202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(0), InputDemandedElts, 1160202375Srdivacky UndefElts2, Depth+1); 1161202375Srdivacky if (TmpV) { 1162202375Srdivacky I->setOperand(0, TmpV); 1163202375Srdivacky MadeChange = true; 1164202375Srdivacky } 1165249423Sdim 1166202375Srdivacky UndefElts = UndefElts2; 1167202375Srdivacky if (VWidth > InVWidth) { 1168202375Srdivacky llvm_unreachable("Unimp"); 1169202375Srdivacky // If there are more elements in the result than there are in the source, 1170202375Srdivacky // then an output element is undef if the corresponding input element is 1171202375Srdivacky // undef. 1172202375Srdivacky for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) 1173202375Srdivacky if (UndefElts2[OutIdx/Ratio]) 1174218893Sdim UndefElts.setBit(OutIdx); 1175202375Srdivacky } else if (VWidth < InVWidth) { 1176202375Srdivacky llvm_unreachable("Unimp"); 1177202375Srdivacky // If there are more elements in the source than there are in the result, 1178202375Srdivacky // then a result element is undef if all of the corresponding input 1179202375Srdivacky // elements are undef. 1180202375Srdivacky UndefElts = ~0ULL >> (64-VWidth); // Start out all undef. 1181202375Srdivacky for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) 1182202375Srdivacky if (!UndefElts2[InIdx]) // Not undef? 1183218893Sdim UndefElts.clearBit(InIdx/Ratio); // Clear undef bit. 1184202375Srdivacky } 1185202375Srdivacky break; 1186202375Srdivacky } 1187202375Srdivacky case Instruction::And: 1188202375Srdivacky case Instruction::Or: 1189202375Srdivacky case Instruction::Xor: 1190202375Srdivacky case Instruction::Add: 1191202375Srdivacky case Instruction::Sub: 1192202375Srdivacky case Instruction::Mul: 1193202375Srdivacky // div/rem demand all inputs, because they don't want divide by zero. 1194202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 1195202375Srdivacky UndefElts, Depth+1); 1196202375Srdivacky if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1197202375Srdivacky TmpV = SimplifyDemandedVectorElts(I->getOperand(1), DemandedElts, 1198202375Srdivacky UndefElts2, Depth+1); 1199202375Srdivacky if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 1200249423Sdim 1201202375Srdivacky // Output elements are undefined if both are undefined. Consider things 1202202375Srdivacky // like undef&0. The result is known zero, not undef. 1203202375Srdivacky UndefElts &= UndefElts2; 1204202375Srdivacky break; 1205239462Sdim case Instruction::FPTrunc: 1206239462Sdim case Instruction::FPExt: 1207239462Sdim TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 1208239462Sdim UndefElts, Depth+1); 1209239462Sdim if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1210239462Sdim break; 1211249423Sdim 1212202375Srdivacky case Instruction::Call: { 1213202375Srdivacky IntrinsicInst *II = dyn_cast<IntrinsicInst>(I); 1214202375Srdivacky if (!II) break; 1215202375Srdivacky switch (II->getIntrinsicID()) { 1216202375Srdivacky default: break; 1217249423Sdim 1218202375Srdivacky // Binary vector operations that work column-wise. A dest element is a 1219202375Srdivacky // function of the corresponding input elements from the two inputs. 1220202375Srdivacky case Intrinsic::x86_sse_sub_ss: 1221202375Srdivacky case Intrinsic::x86_sse_mul_ss: 1222202375Srdivacky case Intrinsic::x86_sse_min_ss: 1223202375Srdivacky case Intrinsic::x86_sse_max_ss: 1224202375Srdivacky case Intrinsic::x86_sse2_sub_sd: 1225202375Srdivacky case Intrinsic::x86_sse2_mul_sd: 1226202375Srdivacky case Intrinsic::x86_sse2_min_sd: 1227202375Srdivacky case Intrinsic::x86_sse2_max_sd: 1228210299Sed TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts, 1229202375Srdivacky UndefElts, Depth+1); 1230210299Sed if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } 1231210299Sed TmpV = SimplifyDemandedVectorElts(II->getArgOperand(1), DemandedElts, 1232202375Srdivacky UndefElts2, Depth+1); 1233210299Sed if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; } 1234202375Srdivacky 1235202375Srdivacky // If only the low elt is demanded and this is a scalarizable intrinsic, 1236202375Srdivacky // scalarize it now. 1237202375Srdivacky if (DemandedElts == 1) { 1238202375Srdivacky switch (II->getIntrinsicID()) { 1239202375Srdivacky default: break; 1240202375Srdivacky case Intrinsic::x86_sse_sub_ss: 1241202375Srdivacky case Intrinsic::x86_sse_mul_ss: 1242202375Srdivacky case Intrinsic::x86_sse2_sub_sd: 1243202375Srdivacky case Intrinsic::x86_sse2_mul_sd: 1244202375Srdivacky // TODO: Lower MIN/MAX/ABS/etc 1245210299Sed Value *LHS = II->getArgOperand(0); 1246210299Sed Value *RHS = II->getArgOperand(1); 1247202375Srdivacky // Extract the element as scalars. 1248249423Sdim LHS = InsertNewInstWith(ExtractElementInst::Create(LHS, 1249202375Srdivacky ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); 1250223017Sdim RHS = InsertNewInstWith(ExtractElementInst::Create(RHS, 1251202375Srdivacky ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); 1252249423Sdim 1253202375Srdivacky switch (II->getIntrinsicID()) { 1254202375Srdivacky default: llvm_unreachable("Case stmts out of sync!"); 1255202375Srdivacky case Intrinsic::x86_sse_sub_ss: 1256202375Srdivacky case Intrinsic::x86_sse2_sub_sd: 1257223017Sdim TmpV = InsertNewInstWith(BinaryOperator::CreateFSub(LHS, RHS, 1258202375Srdivacky II->getName()), *II); 1259202375Srdivacky break; 1260202375Srdivacky case Intrinsic::x86_sse_mul_ss: 1261202375Srdivacky case Intrinsic::x86_sse2_mul_sd: 1262223017Sdim TmpV = InsertNewInstWith(BinaryOperator::CreateFMul(LHS, RHS, 1263202375Srdivacky II->getName()), *II); 1264202375Srdivacky break; 1265202375Srdivacky } 1266249423Sdim 1267202375Srdivacky Instruction *New = 1268202375Srdivacky InsertElementInst::Create( 1269202375Srdivacky UndefValue::get(II->getType()), TmpV, 1270202375Srdivacky ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U, false), 1271202375Srdivacky II->getName()); 1272223017Sdim InsertNewInstWith(New, *II); 1273202375Srdivacky return New; 1274249423Sdim } 1275202375Srdivacky } 1276249423Sdim 1277202375Srdivacky // Output elements are undefined if both are undefined. Consider things 1278202375Srdivacky // like undef&0. The result is known zero, not undef. 1279202375Srdivacky UndefElts &= UndefElts2; 1280202375Srdivacky break; 1281202375Srdivacky } 1282202375Srdivacky break; 1283202375Srdivacky } 1284202375Srdivacky } 1285202375Srdivacky return MadeChange ? I : 0; 1286202375Srdivacky} 1287