1e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner//===- InstCombineSimplifyDemanded.cpp ------------------------------------===// 2e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// 3e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// The LLVM Compiler Infrastructure 4e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// 5e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// This file is distributed under the University of Illinois Open Source 6e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// License. See LICENSE.TXT for details. 7e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// 8e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner//===----------------------------------------------------------------------===// 9e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// 10e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// This file contains logic for simplifying instructions based on information 11e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// about how they are used. 12e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner// 13e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner//===----------------------------------------------------------------------===// 14e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 15e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 16e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner#include "InstCombine.h" 17e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner#include "llvm/Target/TargetData.h" 18e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner#include "llvm/IntrinsicInst.h" 19e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 20e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattnerusing namespace llvm; 21e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 22e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 23e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// ShrinkDemandedConstant - Check to see if the specified operand of the 24e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// specified instruction is a constant integer. If so, check to see if there 25e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// are any bits set in the constant that are not demanded. If so, shrink the 26e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// constant and return true. 27e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattnerstatic bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo, 28e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt Demanded) { 29e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(I && "No instruction?"); 30e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(OpNo < I->getNumOperands() && "Operand index too large"); 31e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 32e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the operand is not a constant integer, nothing to do. 33e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt *OpC = dyn_cast<ConstantInt>(I->getOperand(OpNo)); 34e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!OpC) return false; 35e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 36e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are no bits set that aren't demanded, nothing to do. 3740f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad Demanded = Demanded.zextOrTrunc(OpC->getValue().getBitWidth()); 38e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((~Demanded & OpC->getValue()) == 0) 39e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return false; 40e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 41e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // This instruction is producing bits that are not demanded. Shrink the RHS. 42e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Demanded &= OpC->getValue(); 43e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->setOperand(OpNo, ConstantInt::get(OpC->getType(), Demanded)); 44e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return true; 45e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 46e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 47e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 48e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 49e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedInstructionBits - Inst is an integer instruction that 50e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedBits knows about. See if the instruction has any 51e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// properties that allow us to simplify its operands. 52e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattnerbool InstCombiner::SimplifyDemandedInstructionBits(Instruction &Inst) { 53e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned BitWidth = Inst.getType()->getScalarSizeInBits(); 54e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 55e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedMask(APInt::getAllOnesValue(BitWidth)); 56e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 57e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Value *V = SimplifyDemandedUseBits(&Inst, DemandedMask, 58e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero, KnownOne, 0); 59e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (V == 0) return false; 60e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (V == &Inst) return true; 61e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ReplaceInstUsesWith(Inst, V); 62e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return true; 63e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 64e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 65e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedBits - This form of SimplifyDemandedBits simplifies the 66e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// specified instruction operand if possible, updating it in place. It returns 67e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// true if it made any change and false otherwise. 68e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattnerbool InstCombiner::SimplifyDemandedBits(Use &U, APInt DemandedMask, 69e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt &KnownZero, APInt &KnownOne, 70e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Depth) { 71e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask, 72e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero, KnownOne, Depth); 73e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (NewVal == 0) return false; 74e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner U = NewVal; 75e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return true; 76e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 77e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 78e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 79e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedUseBits - This function attempts to replace V with a simpler 80e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// value based on the demanded bits. When this function is called, it is known 81e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// that only the bits set in DemandedMask of the result of V are ever used 82e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// downstream. Consequently, depending on the mask and V, it may be possible 83e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// to replace V with a constant or one of its operands. In such cases, this 84e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// function does the replacement and returns true. In all other cases, it 85e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// returns false after analyzing the expression and setting KnownOne and known 86e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// to be one in the expression. KnownZero contains all the bits that are known 87e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// to be zero in the expression. These are provided to potentially allow the 88e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// caller (which might recursively be SimplifyDemandedBits itself) to simplify 89e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// the expression. KnownOne and KnownZero always follow the invariant that 90e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// KnownOne & KnownZero == 0. That is, a bit can't be both 1 and 0. Note that 91e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// the bits in KnownOne and KnownZero may only be accurate for those bits set 92e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// in DemandedMask. Note also that the bitwidth of V, DemandedMask, KnownZero 93e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// and KnownOne must all be the same. 94e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// 95e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// This returns null if it did not change anything and it permits no 96e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// simplification. This returns V itself if it did some simplification of V's 97e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// operands based on the information about what bits are demanded. This returns 98e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// some other non-null value if it found out that V is equal to another value 99e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// in the context where the specified bits are demanded, but not for all users. 100e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris LattnerValue *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, 101e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt &KnownZero, APInt &KnownOne, 102e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Depth) { 103e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(V != 0 && "Null pointer of Value???"); 104e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(Depth <= 6 && "Limit Search Depth"); 105e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner uint32_t BitWidth = DemandedMask.getBitWidth(); 106db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *VTy = V->getType(); 1071df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands assert((TD || !VTy->isPointerTy()) && 108e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner "SimplifyDemandedBits needs to know bit widths!"); 109e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert((!TD || TD->getTypeSizeInBits(VTy->getScalarType()) == BitWidth) && 110b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands (!VTy->isIntOrIntVectorTy() || 111e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner VTy->getScalarSizeInBits() == BitWidth) && 112e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero.getBitWidth() == BitWidth && 113e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownOne.getBitWidth() == BitWidth && 114e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner "Value *V, DemandedMask, KnownZero and KnownOne " 115e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner "must have same BitWidth"); 116e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 117e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // We know all of the bits for a constant! 118e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownOne = CI->getValue() & DemandedMask; 119e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero = ~KnownOne & DemandedMask; 120e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 121e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 122e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (isa<ConstantPointerNull>(V)) { 123e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // We know all of the bits for a constant! 1247a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 125e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero = DemandedMask; 126e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 127e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 128e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1297a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownZero.clearAllBits(); 1307a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 131e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask == 0) { // Not demanding any bits from V. 132e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (isa<UndefValue>(V)) 133e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 134e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return UndefValue::get(VTy); 135e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 136e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 137e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth == 6) // Limit search depth. 138e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 139e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 140e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 141ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); 142e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 143e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *I = dyn_cast<Instruction>(V); 144e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!I) { 14526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, Depth); 146e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; // Only analyze instructions. 147e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 148e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 149e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are multiple uses of this value and we aren't at the root, then 150e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // we can't do any simplifications of the operands, because DemandedMask 151e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // only reflects the bits demanded by *one* of the users. 152e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth != 0 && !I->hasOneUse()) { 153e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Despite the fact that we can't simplify this instruction in all User's 154e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // context, we can at least compute the knownzero/knownone bits, and we can 155e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // do simplifications that apply to *just* the one user if we know that 156e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // this instruction has a simpler value in that context. 157e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (I->getOpcode() == Instruction::And) { 158e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If either the LHS or the RHS are Zero, the result is zero. 15926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1); 16026c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 161e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 162e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known 1 on one side, return the other. 163e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // These bits cannot contribute to the result of the 'and' in this 164e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // context. 165e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == 166e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~LHSKnownZero)) 167e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 168e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == 169e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~RHSKnownZero)) 170e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 171e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 172e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits in the inputs are known zeros, return zero. 173e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) 174e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return Constant::getNullValue(VTy); 175e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 176e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else if (I->getOpcode() == Instruction::Or) { 177e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // We can simplify (X|Y) -> X or Y in the user's context if we know that 178e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // only bits from X or Y are demanded. 179e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 180e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If either the LHS or the RHS are One, the result is One. 18126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1); 18226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 183e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 184e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known zero on one side, return the 185e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // other. These bits cannot contribute to the result of the 'or' in this 186e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // context. 187e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == 188e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~LHSKnownOne)) 189e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 190e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == 191e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~RHSKnownOne)) 192e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 193e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 194e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the potentially set bits on one side are known to be set on 195e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the other side, just use the 'other' side. 196e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == 197e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & (~RHSKnownZero))) 198e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 199e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == 200e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & (~LHSKnownZero))) 201e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 202e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 203e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 204e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the KnownZero/KnownOne bits to simplify things downstream. 20526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I, KnownZero, KnownOne, Depth); 206e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 207e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 208e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 209e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If this is the root being simplified, allow it to have multiple uses, 210e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // just set the DemandedMask to all bits so that we can try to simplify the 211e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // operands. This allows visitTruncInst (for example) to simplify the 212e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // operand of a trunc without duplicating all the logic below. 213e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth == 0 && !V->hasOneUse()) 214e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner DemandedMask = APInt::getAllOnesValue(BitWidth); 215e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 216e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (I->getOpcode()) { 217e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: 21826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I, KnownZero, KnownOne, Depth); 219e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 220e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::And: 221e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If either the LHS or the RHS are Zero, the result is zero. 222e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 223e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner RHSKnownZero, RHSKnownOne, Depth+1) || 224e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownZero, 225e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 226e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 227e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 228e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 229e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 230e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known 1 on one side, return the other. 231e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // These bits cannot contribute to the result of the 'and'. 232e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == 233e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~LHSKnownZero)) 234e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 235e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == 236e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~RHSKnownZero)) 237e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 238e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 239e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits in the inputs are known zeros, return zero. 240e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) 241e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return Constant::getNullValue(VTy); 242e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 243e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the RHS is a constant, see if we can simplify it. 244e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnownZero)) 245e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 246e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 247e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output known-1 bits are only known if set in both the LHS & RHS. 248ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = RHSKnownOne & LHSKnownOne; 249e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output known-0 are known to be clear if zero in either the LHS | RHS. 250ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = RHSKnownZero | LHSKnownZero; 251e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 252e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Or: 253e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If either the LHS or the RHS are One, the result is One. 254e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 255e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner RHSKnownZero, RHSKnownOne, Depth+1) || 256e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownOne, 257e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 258e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 259e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 260e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 261e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 262e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known zero on one side, return the other. 263e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // These bits cannot contribute to the result of the 'or'. 264e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == 265e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~LHSKnownOne)) 266e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 267e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == 268e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~RHSKnownOne)) 269e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 270e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 271e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the potentially set bits on one side are known to be set on 272e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the other side, just use the 'other' side. 273e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == 274e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & (~RHSKnownZero))) 275e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 276e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == 277e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & (~LHSKnownZero))) 278e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 279e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 280e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the RHS is a constant, see if we can simplify it. 281e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, DemandedMask)) 282e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 283e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 284e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output known-0 bits are only known if clear in both the LHS & RHS. 285ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = RHSKnownZero & LHSKnownZero; 286e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output known-1 are known to be set if set in either the LHS | RHS. 287ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = RHSKnownOne | LHSKnownOne; 288e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 289e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Xor: { 290e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 291e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner RHSKnownZero, RHSKnownOne, Depth+1) || 292e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 293e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 294e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 295e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 296e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 297e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 298e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known zero on one side, return the other. 299e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // These bits cannot contribute to the result of the 'xor'. 300e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & RHSKnownZero) == DemandedMask) 301e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 302e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & LHSKnownZero) == DemandedMask) 303e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 304e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 305e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known to be zero on one side or the 306e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // other, turn this into an *inclusive* or. 307e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 308e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~RHSKnownZero & ~LHSKnownZero) == 0) { 309e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *Or = 310e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1), 311e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->getName()); 3126fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(Or, *I); 313e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 314e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 315e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits on one side are known, and all of the set 316e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // bits on that side are also known to be set on the other side, turn this 317e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // into an AND, as we know the bits will be cleared. 318e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 319e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & (RHSKnownZero|RHSKnownOne)) == DemandedMask) { 320e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // all known 321e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((RHSKnownOne & LHSKnownOne) == RHSKnownOne) { 322e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Constant *AndC = Constant::getIntegerValue(VTy, 323e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ~RHSKnownOne & DemandedMask); 324a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 3256fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(And, *I); 326e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 327e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 328e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 329e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the RHS is a constant, see if we can simplify it. 330e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1. 331e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, DemandedMask)) 332e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 333e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 334e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If our LHS is an 'and' and if it has one use, and if any of the bits we 335e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // are flipping are known to be set, then the xor is just resetting those 336e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // bits to zero. We can just knock out bits from the 'and' and the 'xor', 337e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // simplifying both of them. 338e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0))) 339e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() && 340e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner isa<ConstantInt>(I->getOperand(1)) && 341e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner isa<ConstantInt>(LHSInst->getOperand(1)) && 342e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (LHSKnownOne & RHSKnownOne & DemandedMask) != 0) { 343e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt *AndRHS = cast<ConstantInt>(LHSInst->getOperand(1)); 344e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt *XorRHS = cast<ConstantInt>(I->getOperand(1)); 345e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt NewMask = ~(LHSKnownOne & RHSKnownOne & DemandedMask); 346e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 347e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Constant *AndC = 348e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(I->getType(), NewMask & AndRHS->getValue()); 349a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 3506fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman InsertNewInstWith(NewAnd, *I); 351e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 352e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Constant *XorC = 353e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(I->getType(), NewMask & XorRHS->getValue()); 354a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC); 3556fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewXor, *I); 356e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 357ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands 358ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands // Output known-0 bits are known if clear or set in both the LHS & RHS. 359ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero= (RHSKnownZero & LHSKnownZero) | (RHSKnownOne & LHSKnownOne); 360ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands // Output known-1 are known to be set if set in only one of the LHS, RHS. 361ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = (RHSKnownZero & LHSKnownOne) | (RHSKnownOne & LHSKnownZero); 362e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 363e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 364e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Select: 365e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(2), DemandedMask, 366e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner RHSKnownZero, RHSKnownOne, Depth+1) || 367e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 368e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 369e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 370e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 371e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 372e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 373e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the operands are constants, see if we can simplify them. 374e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, DemandedMask) || 375e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ShrinkDemandedConstant(I, 2, DemandedMask)) 376e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 377e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 378e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Only known if known in both the LHS and RHS. 379ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = RHSKnownOne & LHSKnownOne; 380ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = RHSKnownZero & LHSKnownZero; 381e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 382e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Trunc: { 383e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned truncBf = I->getOperand(0)->getType()->getScalarSizeInBits(); 38440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad DemandedMask = DemandedMask.zext(truncBf); 38540f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zext(truncBf); 38640f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zext(truncBf); 387e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 388ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 389e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 39040f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad DemandedMask = DemandedMask.trunc(BitWidth); 39140f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.trunc(BitWidth); 39240f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.trunc(BitWidth); 393ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 394e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 395e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 396e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::BitCast: 397b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (!I->getOperand(0)->getType()->isIntOrIntVectorTy()) 398ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; // vector->int or fp->int? 399e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 400db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (VectorType *DstVTy = dyn_cast<VectorType>(I->getType())) { 401db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (VectorType *SrcVTy = 402e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner dyn_cast<VectorType>(I->getOperand(0)->getType())) { 403e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DstVTy->getNumElements() != SrcVTy->getNumElements()) 404e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Don't touch a bitcast between vectors of different element counts. 405ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; 406e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else 407e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Don't touch a scalar-to-vector bitcast. 408ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; 4091df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands } else if (I->getOperand(0)->getType()->isVectorTy()) 410e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Don't touch a vector-to-scalar bitcast. 411ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; 412e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 413e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 414ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 415e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 416ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 417e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 418e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::ZExt: { 419e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the bits in the result that are not present in the input. 420e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); 421e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 42240f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad DemandedMask = DemandedMask.trunc(SrcBitWidth); 42340f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.trunc(SrcBitWidth); 42440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.trunc(SrcBitWidth); 425e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 426ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 427e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 42840f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad DemandedMask = DemandedMask.zext(BitWidth); 42940f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zext(BitWidth); 43040f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zext(BitWidth); 431ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 432e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // The top bits are known to be zero. 433ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 434e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 435e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 436e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::SExt: { 437e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the bits in the result that are not present in the input. 438e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); 439e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 440e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt InputDemandedBits = DemandedMask & 441e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt::getLowBitsSet(BitWidth, SrcBitWidth); 442e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 443e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt NewBits(APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth)); 444e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If any of the sign extended bits are demanded, we know that the sign 445e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // bit is demanded. 446e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((NewBits & DemandedMask) != 0) 4477a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad InputDemandedBits.setBit(SrcBitWidth-1); 448e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 44940f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad InputDemandedBits = InputDemandedBits.trunc(SrcBitWidth); 45040f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.trunc(SrcBitWidth); 45140f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.trunc(SrcBitWidth); 452e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), InputDemandedBits, 453ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 454e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 45540f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad InputDemandedBits = InputDemandedBits.zext(BitWidth); 45640f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zext(BitWidth); 45740f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zext(BitWidth); 458ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 459e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 460e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the sign bit of the input is known set or clear, then we know the 461e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // top bits of the result. 462e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 463e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the input sign bit is known zero, or if the NewBits are not demanded 464e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // convert this into a zero extension. 465ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands if (KnownZero[SrcBitWidth-1] || (NewBits & ~DemandedMask) == NewBits) { 466e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Convert to ZExt cast 467e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName()); 4686fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewCast, *I); 469ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands } else if (KnownOne[SrcBitWidth-1]) { // Input sign bit known set 470ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne |= NewBits; 471e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 472e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 473e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 474e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Add: { 475e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Figure out what the input bits are. If the top bits of the and result 476e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // are not demanded, then the add doesn't demand them from its input 477e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // either. 478e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned NLZ = DemandedMask.countLeadingZeros(); 479e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 480e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there is a constant on the RHS, there are a variety of xformations 481e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // we can do. 482e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) { 483e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If null, this should be simplified elsewhere. Some of the xforms here 484e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // won't work if the RHS is zero. 485e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (RHS->isZero()) 486e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 487e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 488e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the top bit of the output is demanded, demand everything from the 489e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // input. Otherwise, we demand all the input bits except NLZ top bits. 490e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt InDemandedBits(APInt::getLowBitsSet(BitWidth, BitWidth - NLZ)); 491e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 492e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Find information about known zero/one bits in the input. 493e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), InDemandedBits, 494e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 495e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 496e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 497e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the RHS of the add has bits set that can't affect the input, reduce 498e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the constant. 499e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, InDemandedBits)) 500e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 501e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 502e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Avoid excess work. 503e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (LHSKnownZero == 0 && LHSKnownOne == 0) 504e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 505e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 506e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Turn it into OR if input bits are zero. 507e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((LHSKnownZero & RHS->getValue()) == RHS->getValue()) { 508e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *Or = 509e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1), 510e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->getName()); 5116fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(Or, *I); 512e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 513e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 514e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // We can say something about the output known-zero and known-one bits, 515e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // depending on potential carries from the input constant and the 516e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // unknowns. For example if the LHS is known to have at most the 0x0F0F0 517e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // bits set and the RHS constant is 0x01001, then we know we have a known 518e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // one mask of 0x00001 and a known zero mask of 0xE0F0E. 519e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 520e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // To compute this, we first compute the potential carry bits. These are 521e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the bits which may be modified. I'm not aware of a better way to do 522e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // this scan. 523e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner const APInt &RHSVal = RHS->getValue(); 524e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt CarryBits((~LHSKnownZero + RHSVal) ^ (~LHSKnownZero ^ RHSVal)); 525e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 526e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Now that we know which bits have carries, compute the known-1/0 sets. 527e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 528e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Bits are known one if they are known zero in one operand and one in the 529e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // other, and there is no input carry. 530ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = ((LHSKnownZero & RHSVal) | 531ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands (LHSKnownOne & ~RHSVal)) & ~CarryBits; 532e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 533e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Bits are known zero if they are known zero in both operands and there 534e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // is no input carry. 535ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = LHSKnownZero & ~RHSVal & ~CarryBits; 536e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else { 537e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the high-bits of this ADD are not demanded, then it does not demand 538e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the high bits of its LHS or RHS. 539e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask[BitWidth-1] == 0) { 540e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Right fill the mask of bits for this ADD to demand the most 541e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // significant bit and all those below it. 542e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ)); 543e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps, 544e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1) || 545e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps, 546e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 547e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 548e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 549e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 550e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 551e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 552e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Sub: 553e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the high-bits of this SUB are not demanded, then it does not demand 554e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the high bits of its LHS or RHS. 555e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask[BitWidth-1] == 0) { 556e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Right fill the mask of bits for this SUB to demand the most 557e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // significant bit and all those below it. 558e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner uint32_t NLZ = DemandedMask.countLeadingZeros(); 559e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ)); 560e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps, 561e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1) || 562e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps, 563e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 564e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 565e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 5661fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer 567e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Otherwise just hand the sub off to ComputeMaskedBits to fill in 568e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the known zeros and ones. 56926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, Depth); 5701fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer 5711fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known 5721fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer // zero. 5731fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer if (ConstantInt *C0 = dyn_cast<ConstantInt>(I->getOperand(0))) { 5741fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer APInt I0 = C0->getValue(); 5751fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer if ((I0 + 1).isPowerOf2() && (I0 | KnownZero).isAllOnesValue()) { 5761fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer Instruction *Xor = BinaryOperator::CreateXor(I->getOperand(1), C0); 5771fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer return InsertNewInstWith(Xor, *I); 5781fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer } 5791fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer } 580e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 581e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Shl: 582e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 583a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 584e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt)); 585a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner 586a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // If the shift is NUW/NSW, then it does demand the high bits. 587a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner ShlOperator *IOp = cast<ShlOperator>(I); 588a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner if (IOp->hasNoSignedWrap()) 589a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1); 590a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner else if (IOp->hasNoUnsignedWrap()) 591a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 592a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner 593e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, 594ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 595e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 596ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 597ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero <<= ShiftAmt; 598ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne <<= ShiftAmt; 599e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // low bits known zero. 600e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShiftAmt) 601ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 602e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 603e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 604e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::LShr: 605e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // For a logical shift right 606e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 607a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 608e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 609e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Unsigned shift right. 610e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 611a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner 612a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // If the shift is exact, then it does demand the low bits (and knows that 613a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // they are zero). 614a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner if (cast<LShrOperator>(I)->isExact()) 615a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 616a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner 617e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, 618ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 619e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 620ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 621ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 622ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 623e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShiftAmt) { 624e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the new bits that are at the top now. 625e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 626ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero |= HighBits; // high bits known zero. 627e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 628e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 629e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 630e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::AShr: 631e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If this is an arithmetic shift right and only the low-bit is set, we can 632e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // always convert this into a logical shr, even if the shift amount is 633e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // variable. The low bit of the shift cannot be an input sign bit unless 634e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the shift amount is >= the size of the datatype, which is undefined. 635e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask == 1) { 636e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Perform the logical shift right. 637e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *NewVal = BinaryOperator::CreateLShr( 638e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->getOperand(0), I->getOperand(1), I->getName()); 6396fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewVal, *I); 640e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 641e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 642e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the sign bit is the only bit demanded by this ashr, then there is no 643e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // need to do it, the shift doesn't change the high bit. 644e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask.isSignBit()) 645e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 646e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 647e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 648a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 649e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 650e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Signed shift right. 651e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 652e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If any of the "high bits" are demanded, we should set the sign bit as 653e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // demanded. 654e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask.countLeadingZeros() <= ShiftAmt) 6557a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad DemandedMaskIn.setBit(BitWidth-1); 656a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner 657a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // If the shift is exact, then it does demand the low bits (and knows that 658a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // they are zero). 659a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner if (cast<AShrOperator>(I)->isExact()) 660a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 661a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner 662e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, 663ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 664e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 665ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 666e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the new bits that are at the top now. 667e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 668ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 669ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 670e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 671e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Handle the sign bits. 672e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt SignBit(APInt::getSignBit(BitWidth)); 673e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Adjust to where it is now in the mask. 674e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SignBit = APIntOps::lshr(SignBit, ShiftAmt); 675e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 676e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the input sign bit is known to be zero, or if none of the top bits 677e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // are demanded, turn this into an unsigned shift right. 678ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands if (BitWidth <= ShiftAmt || KnownZero[BitWidth-ShiftAmt-1] || 679e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (HighBits & ~DemandedMask) == HighBits) { 680e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Perform the logical shift right. 681148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky BinaryOperator *NewVal = BinaryOperator::CreateLShr(I->getOperand(0), 682148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky SA, I->getName()); 683148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky NewVal->setIsExact(cast<BinaryOperator>(I)->isExact()); 6846fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewVal, *I); 685ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands } else if ((KnownOne & SignBit) != 0) { // New bits are known one. 686ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne |= HighBits; 687e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 688e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 689e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 690e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::SRem: 691e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 692c6b018b7379f4e1bcc4166a07b17d08180ed776dEli Friedman // X % -1 demands all the bits because we don't want to introduce 693c6b018b7379f4e1bcc4166a07b17d08180ed776dEli Friedman // INT_MIN % -1 (== undef) by accident. 694c6b018b7379f4e1bcc4166a07b17d08180ed776dEli Friedman if (Rem->isAllOnesValue()) 695c6b018b7379f4e1bcc4166a07b17d08180ed776dEli Friedman break; 696e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt RA = Rem->getValue().abs(); 697e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (RA.isPowerOf2()) { 698e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask.ult(RA)) // srem won't affect demanded bits 699e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 700e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 701e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt LowBits = RA - 1; 702e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 703e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), Mask2, 704e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 705e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 706e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 7072c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // The low bits of LHS are unchanged by the srem. 708ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = LHSKnownZero & LowBits; 709ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = LHSKnownOne & LowBits; 7102c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands 7112c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // If LHS is non-negative or has all low bits zero, then the upper bits 7122c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // are all zero. 713e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (LHSKnownZero[BitWidth-1] || ((LHSKnownZero & LowBits) == LowBits)) 7142c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands KnownZero |= ~LowBits; 715e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 7162c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // If LHS is negative and not all low bits are zero, then the upper bits 7172c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // are all one. 7182c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands if (LHSKnownOne[BitWidth-1] && ((LHSKnownOne & LowBits) != 0)) 7192c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands KnownOne |= ~LowBits; 720e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 721e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 722e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 723e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 724c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky 725c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // The sign bit is the LHS's sign bit, except when the result of the 726c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // remainder is zero. 727c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky if (DemandedMask.isNegative() && KnownZero.isNonNegative()) { 728c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 72926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 730c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // If it's known zero, our sign bit is also zero. 731c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky if (LHSKnownZero.isNegative()) 732c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky KnownZero |= LHSKnownZero; 733c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky } 734e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 735e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::URem: { 736e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0); 737e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 738e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), AllOnes, 739e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero2, KnownOne2, Depth+1) || 740e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(1), AllOnes, 741e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero2, KnownOne2, Depth+1)) 742e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 743e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 744e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Leaders = KnownZero2.countLeadingOnes(); 745e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Leaders = std::max(Leaders, 746e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero2.countLeadingOnes()); 747e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask; 748e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 749e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 750e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Call: 751e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 752e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (II->getIntrinsicID()) { 753e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: break; 754e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::bswap: { 755e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the only bits demanded come from one byte of the bswap result, 756e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // just shift the input byte into position to eliminate the bswap. 757e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned NLZ = DemandedMask.countLeadingZeros(); 758e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned NTZ = DemandedMask.countTrailingZeros(); 759e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 760e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Round NTZ down to the next byte. If we have 11 trailing zeros, then 761e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // we need all the bits down to bit 8. Likewise, round NLZ. If we 762e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // have 14 leading zeros, round to 8. 763e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NLZ &= ~7; 764e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NTZ &= ~7; 765e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If we need exactly one byte, we can do this transformation. 766e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (BitWidth-NLZ-NTZ == 8) { 767e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned ResultBit = NTZ; 768e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned InputBit = BitWidth-NTZ-8; 769e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 770e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Replace this with either a left or right shift to get the byte into 771e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the right place. 772e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *NewVal; 773e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (InputBit > ResultBit) 7743e84e2e90f560aa75e08957e1509b9e6d9d502bbGabor Greif NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0), 775e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(I->getType(), InputBit-ResultBit)); 776e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner else 7773e84e2e90f560aa75e08957e1509b9e6d9d502bbGabor Greif NewVal = BinaryOperator::CreateShl(II->getArgOperand(0), 778e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(I->getType(), ResultBit-InputBit)); 779e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NewVal->takeName(I); 7806fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewVal, *I); 781e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 782e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 783e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // TODO: Could compute known zero/one bits based on the input. 784e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 785e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 78662660310d9e5f9ecf329fd3cacb67c344a12ddbcChad Rosier case Intrinsic::x86_sse42_crc32_64_8: 78762660310d9e5f9ecf329fd3cacb67c344a12ddbcChad Rosier case Intrinsic::x86_sse42_crc32_64_64: 7882e6496026f41d2c05ff038d14df9972f8a27fb94Evan Cheng KnownZero = APInt::getHighBitsSet(64, 32); 7892e6496026f41d2c05ff038d14df9972f8a27fb94Evan Cheng return 0; 790e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 791e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 79226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, Depth); 793e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 794e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 795e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 796e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the client is only demanding bits that we know, return the known 797e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // constant. 798ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) 799ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return Constant::getIntegerValue(VTy, KnownOne); 800ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; 801e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 802e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 803e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 804e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedVectorElts - The specified value produces a vector with 805e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// any number of elements. DemandedElts contains the set of elements that are 806e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// actually used by the caller. This method analyzes which elements of the 807e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// operand are undef and returns that information in UndefElts. 808e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// 809e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// If the information about demanded elements can be used to simplify the 810e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// operation, the operation is simplified, then the resultant value is 811e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// returned. This returns null if no change was made. 812e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris LattnerValue *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, 8138609fda0f7e4446de85f882755601ffcbd540324Chris Lattner APInt &UndefElts, 814e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Depth) { 815e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned VWidth = cast<VectorType>(V->getType())->getNumElements(); 816e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt EltMask(APInt::getAllOnesValue(VWidth)); 817e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!"); 818e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 819e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (isa<UndefValue>(V)) { 820e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the entire vector is undefined, just return this info. 821e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = EltMask; 822e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 8238609fda0f7e4446de85f882755601ffcbd540324Chris Lattner } 8248609fda0f7e4446de85f882755601ffcbd540324Chris Lattner 8258609fda0f7e4446de85f882755601ffcbd540324Chris Lattner if (DemandedElts == 0) { // If nothing is demanded, provide undef. 826e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = EltMask; 827e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return UndefValue::get(V->getType()); 828e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 829e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 830e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = 0; 831a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner 832a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner // Handle ConstantAggregateZero, ConstantVector, ConstantDataSequential. 833a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (Constant *C = dyn_cast<Constant>(V)) { 834a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner // Check if this is identity. If so, return 0 since we are not simplifying 835a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner // anything. 836a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (DemandedElts.isAllOnesValue()) 837a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner return 0; 838a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner 839db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *EltTy = cast<VectorType>(V->getType())->getElementType(); 840e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Constant *Undef = UndefValue::get(EltTy); 841a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner 842a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner SmallVector<Constant*, 16> Elts; 843a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner for (unsigned i = 0; i != VWidth; ++i) { 844e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!DemandedElts[i]) { // If not demanded, set to undef. 845e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Elts.push_back(Undef); 8467a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 847a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner continue; 848a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner } 849a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner 850a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner Constant *Elt = C->getAggregateElement(i); 851a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (Elt == 0) return 0; 852a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner 853a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (isa<UndefValue>(Elt)) { // Already undef. 854e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Elts.push_back(Undef); 8557a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 856e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else { // Otherwise, defined. 857a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner Elts.push_back(Elt); 858e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 859a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner } 860a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner 861e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If we changed the constant, return it. 8624ca829e89567f002fc74eb0e3e532a7c7662e031Chris Lattner Constant *NewCV = ConstantVector::get(Elts); 863a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner return NewCV != C ? NewCV : 0; 864e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 865e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 866e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Limit search depth. 867e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth == 10) 868e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 869e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 870ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings // If multiple users are using the root value, proceed with 871e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // simplification conservatively assuming that all elements 872e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // are needed. 873e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!V->hasOneUse()) { 874e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Quit if we find multiple users of a non-root value though. 875e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // They'll be handled when it's their turn to be visited by 876e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the main instcombine process. 877e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth != 0) 878e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // TODO: Just compute the UndefElts information recursively. 879e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 880e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 881e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Conservatively assume that all elements are needed. 882e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner DemandedElts = EltMask; 883e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 884e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 885e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *I = dyn_cast<Instruction>(V); 886e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!I) return 0; // Only analyze instructions. 887e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 888e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner bool MadeChange = false; 889e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt UndefElts2(VWidth, 0); 890e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Value *TmpV; 891e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (I->getOpcode()) { 892e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: break; 893e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 894e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::InsertElement: { 895e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If this is a variable index, we don't know which element it overwrites. 896e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // demand exactly the same input as we produce. 897e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2)); 898e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Idx == 0) { 899e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Note that we can't propagate undef elt info, because we don't know 900e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // which elt is getting updated. 901e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 902e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts2, Depth+1); 903e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 904e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 905e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 906e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 907e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If this is inserting an element that isn't demanded, remove this 908e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // insertelement. 909e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned IdxNo = Idx->getZExtValue(); 910e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (IdxNo >= VWidth || !DemandedElts[IdxNo]) { 911e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Worklist.Add(I); 912e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 913e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 914e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 915e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Otherwise, the element inserted overwrites whatever was there, so the 916e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // input demanded set is simpler than the output set. 917e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedElts2 = DemandedElts; 9187a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad DemandedElts2.clearBit(IdxNo); 919e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts2, 920e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts, Depth+1); 921e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 922e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 923e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // The inserted element is defined. 9247a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.clearBit(IdxNo); 925e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 926e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 927e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::ShuffleVector: { 928e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I); 929e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner uint64_t LHSVWidth = 930e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner cast<VectorType>(Shuffle->getOperand(0)->getType())->getNumElements(); 931e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt LeftDemanded(LHSVWidth, 0), RightDemanded(LHSVWidth, 0); 932e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned i = 0; i < VWidth; i++) { 933e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedElts[i]) { 934e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned MaskVal = Shuffle->getMaskValue(i); 935e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (MaskVal != -1u) { 936e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(MaskVal < LHSVWidth * 2 && 937e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner "shufflevector mask index out of range!"); 938e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (MaskVal < LHSVWidth) 9397a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad LeftDemanded.setBit(MaskVal); 940e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner else 9417a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad RightDemanded.setBit(MaskVal - LHSVWidth); 942e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 943e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 944e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 945e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 946e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt UndefElts4(LHSVWidth, 0); 947e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), LeftDemanded, 948e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts4, Depth+1); 949e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 950e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 951e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt UndefElts3(LHSVWidth, 0); 952e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(1), RightDemanded, 953e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts3, Depth+1); 954e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 955e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 956e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner bool NewUndefElts = false; 957e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned i = 0; i < VWidth; i++) { 958e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned MaskVal = Shuffle->getMaskValue(i); 959e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (MaskVal == -1u) { 9607a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 961c82751dd6761e3db62668b6b1cfddd4f659855b6Eli Friedman } else if (!DemandedElts[i]) { 962c82751dd6761e3db62668b6b1cfddd4f659855b6Eli Friedman NewUndefElts = true; 963c82751dd6761e3db62668b6b1cfddd4f659855b6Eli Friedman UndefElts.setBit(i); 964e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else if (MaskVal < LHSVWidth) { 965e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (UndefElts4[MaskVal]) { 966e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NewUndefElts = true; 9677a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 968e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 969e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else { 970e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (UndefElts3[MaskVal - LHSVWidth]) { 971e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NewUndefElts = true; 9727a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 973e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 974e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 975e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 976e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 977e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (NewUndefElts) { 978e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Add additional discovered undefs. 979a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner SmallVector<Constant*, 16> Elts; 980e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned i = 0; i < VWidth; ++i) { 981e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (UndefElts[i]) 982e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Elts.push_back(UndefValue::get(Type::getInt32Ty(I->getContext()))); 983e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner else 984e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Elts.push_back(ConstantInt::get(Type::getInt32Ty(I->getContext()), 985e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Shuffle->getMaskValue(i))); 986e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 987e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->setOperand(2, ConstantVector::get(Elts)); 988e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner MadeChange = true; 989e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 990e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 991e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 9927971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper case Instruction::Select: { 9937971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper APInt LeftDemanded(DemandedElts), RightDemanded(DemandedElts); 9947971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper if (ConstantVector* CV = dyn_cast<ConstantVector>(I->getOperand(0))) { 9957971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper for (unsigned i = 0; i < VWidth; i++) { 9967971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper if (CV->getAggregateElement(i)->isNullValue()) 9977971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper LeftDemanded.clearBit(i); 9987971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper else 9997971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper RightDemanded.clearBit(i); 10007971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper } 10017971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper } 10027971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper 10037971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper TmpV = SimplifyDemandedVectorElts(I->getOperand(1), LeftDemanded, 10047971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper UndefElts, Depth+1); 10057971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 10067971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper 10077971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper TmpV = SimplifyDemandedVectorElts(I->getOperand(2), RightDemanded, 10087971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper UndefElts2, Depth+1); 10097971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper if (TmpV) { I->setOperand(2, TmpV); MadeChange = true; } 10107971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper 10117971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper // Output elements are undefined if both are undefined. 10127971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper UndefElts &= UndefElts2; 10137971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper break; 10147971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper } 1015e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::BitCast: { 1016e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Vector->vector casts only. 1017db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType()); 1018e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!VTy) break; 1019e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned InVWidth = VTy->getNumElements(); 1020e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt InputDemandedElts(InVWidth, 0); 1021e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Ratio; 1022e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1023e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (VWidth == InVWidth) { 1024e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If we are converting from <4 x i32> -> <4 x f32>, we demand the same 1025e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // elements as are demanded of us. 1026e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Ratio = 1; 1027e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner InputDemandedElts = DemandedElts; 1028e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else if (VWidth > InVWidth) { 1029e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Untested so far. 1030e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1031e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1032e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are more elements in the result than there are in the source, 1033e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // then an input element is live if any of the corresponding output 1034e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // elements are live. 1035e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Ratio = VWidth/InVWidth; 1036e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) { 1037e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedElts[OutIdx]) 10387a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad InputDemandedElts.setBit(OutIdx/Ratio); 1039e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1040e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else { 1041e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Untested so far. 1042e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1043e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1044e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are more elements in the source than there are in the result, 1045e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // then an input element is live if the corresponding output element is 1046e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // live. 1047e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Ratio = InVWidth/VWidth; 1048e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) 1049e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedElts[InIdx/Ratio]) 10507a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad InputDemandedElts.setBit(InIdx); 1051e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1052e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1053e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // div/rem demand all inputs, because they don't want divide by zero. 1054e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), InputDemandedElts, 1055e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts2, Depth+1); 1056e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { 1057e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->setOperand(0, TmpV); 1058e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner MadeChange = true; 1059e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1060e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1061e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = UndefElts2; 1062e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (VWidth > InVWidth) { 1063e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner llvm_unreachable("Unimp"); 1064e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are more elements in the result than there are in the source, 1065e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // then an output element is undef if the corresponding input element is 1066e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // undef. 1067e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) 1068e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (UndefElts2[OutIdx/Ratio]) 10697a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(OutIdx); 1070e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else if (VWidth < InVWidth) { 1071e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner llvm_unreachable("Unimp"); 1072e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are more elements in the source than there are in the result, 1073e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // then a result element is undef if all of the corresponding input 1074e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // elements are undef. 1075e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = ~0ULL >> (64-VWidth); // Start out all undef. 1076e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) 1077e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!UndefElts2[InIdx]) // Not undef? 10787a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.clearBit(InIdx/Ratio); // Clear undef bit. 1079e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1080e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1081e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1082e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::And: 1083e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Or: 1084e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Xor: 1085e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Add: 1086e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Sub: 1087e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Mul: 1088e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // div/rem demand all inputs, because they don't want divide by zero. 1089e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 1090e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts, Depth+1); 1091e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1092e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(1), DemandedElts, 1093e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts2, Depth+1); 1094e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 1095e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1096e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output elements are undefined if both are undefined. Consider things 1097e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // like undef&0. The result is known zero, not undef. 1098e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts &= UndefElts2; 1099e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 11001121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper case Instruction::FPTrunc: 11011121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper case Instruction::FPExt: 11021121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 11031121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper UndefElts, Depth+1); 11041121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 11051121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper break; 1106e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1107e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Call: { 1108e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner IntrinsicInst *II = dyn_cast<IntrinsicInst>(I); 1109e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!II) break; 1110e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (II->getIntrinsicID()) { 1111e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: break; 1112e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1113e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Binary vector operations that work column-wise. A dest element is a 1114e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // function of the corresponding input elements from the two inputs. 1115e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_sub_ss: 1116e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_mul_ss: 1117e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_min_ss: 1118e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_max_ss: 1119e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_sub_sd: 1120e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_mul_sd: 1121e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_min_sd: 1122e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_max_sd: 112330d2577f644a947d51bb81cf1b6e863d8147cccfGabor Greif TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts, 1124551754c4958086cc6910da7c950f2875e212f5cfEric Christopher UndefElts, Depth+1); 112530d2577f644a947d51bb81cf1b6e863d8147cccfGabor Greif if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } 112630d2577f644a947d51bb81cf1b6e863d8147cccfGabor Greif TmpV = SimplifyDemandedVectorElts(II->getArgOperand(1), DemandedElts, 1127551754c4958086cc6910da7c950f2875e212f5cfEric Christopher UndefElts2, Depth+1); 112830d2577f644a947d51bb81cf1b6e863d8147cccfGabor Greif if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; } 1129e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1130e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If only the low elt is demanded and this is a scalarizable intrinsic, 1131e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // scalarize it now. 1132e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedElts == 1) { 1133e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (II->getIntrinsicID()) { 1134e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: break; 1135e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_sub_ss: 1136e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_mul_ss: 1137e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_sub_sd: 1138e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_mul_sd: 1139e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // TODO: Lower MIN/MAX/ABS/etc 11403e84e2e90f560aa75e08957e1509b9e6d9d502bbGabor Greif Value *LHS = II->getArgOperand(0); 11413e84e2e90f560aa75e08957e1509b9e6d9d502bbGabor Greif Value *RHS = II->getArgOperand(1); 1142e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Extract the element as scalars. 11436fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman LHS = InsertNewInstWith(ExtractElementInst::Create(LHS, 1144e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); 11456fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman RHS = InsertNewInstWith(ExtractElementInst::Create(RHS, 1146e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); 1147e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1148e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (II->getIntrinsicID()) { 1149e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: llvm_unreachable("Case stmts out of sync!"); 1150e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_sub_ss: 1151e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_sub_sd: 11526fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman TmpV = InsertNewInstWith(BinaryOperator::CreateFSub(LHS, RHS, 1153e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner II->getName()), *II); 1154e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1155e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_mul_ss: 1156e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_mul_sd: 11576fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman TmpV = InsertNewInstWith(BinaryOperator::CreateFMul(LHS, RHS, 1158e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner II->getName()), *II); 1159e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1160e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1161e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1162e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *New = 1163e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner InsertElementInst::Create( 1164e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefValue::get(II->getType()), TmpV, 1165e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U, false), 1166e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner II->getName()); 11676fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman InsertNewInstWith(New, *II); 1168e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return New; 1169e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1170e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1171e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1172e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output elements are undefined if both are undefined. Consider things 1173e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // like undef&0. The result is known zero, not undef. 1174e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts &= UndefElts2; 1175e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1176e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1177e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1178e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1179e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1180e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return MadeChange ? I : 0; 1181e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 1182