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" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 19c811976b0400257511f2a255ec70538c3614f85eShuxin Yang#include "llvm/Support/PatternMatch.h" 20e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 21e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattnerusing namespace llvm; 22c811976b0400257511f2a255ec70538c3614f85eShuxin Yangusing namespace llvm::PatternMatch; 23e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 248a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper/// ShrinkDemandedConstant - Check to see if the specified operand of the 25e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// specified instruction is a constant integer. If so, check to see if there 26e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// are any bits set in the constant that are not demanded. If so, shrink the 27e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// constant and return true. 288a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topperstatic bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo, 29e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt Demanded) { 30e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(I && "No instruction?"); 31e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(OpNo < I->getNumOperands() && "Operand index too large"); 32e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 33e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the operand is not a constant integer, nothing to do. 34e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt *OpC = dyn_cast<ConstantInt>(I->getOperand(OpNo)); 35e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!OpC) return false; 36e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 37e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are no bits set that aren't demanded, nothing to do. 3840f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad Demanded = Demanded.zextOrTrunc(OpC->getValue().getBitWidth()); 39e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((~Demanded & OpC->getValue()) == 0) 40e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return false; 41e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 42e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // This instruction is producing bits that are not demanded. Shrink the RHS. 43e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Demanded &= OpC->getValue(); 44e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->setOperand(OpNo, ConstantInt::get(OpC->getType(), Demanded)); 45e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return true; 46e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 47e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 48e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 49e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 50e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedInstructionBits - Inst is an integer instruction that 51e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedBits knows about. See if the instruction has any 52e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// properties that allow us to simplify its operands. 53e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattnerbool InstCombiner::SimplifyDemandedInstructionBits(Instruction &Inst) { 54e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned BitWidth = Inst.getType()->getScalarSizeInBits(); 55e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 56e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedMask(APInt::getAllOnesValue(BitWidth)); 578a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 588a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper Value *V = SimplifyDemandedUseBits(&Inst, DemandedMask, 59e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero, KnownOne, 0); 60e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (V == 0) return false; 61e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (V == &Inst) return true; 62e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ReplaceInstUsesWith(Inst, V); 63e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return true; 64e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 65e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 66e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedBits - This form of SimplifyDemandedBits simplifies the 67e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// specified instruction operand if possible, updating it in place. It returns 68e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// true if it made any change and false otherwise. 698a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topperbool InstCombiner::SimplifyDemandedBits(Use &U, APInt DemandedMask, 70e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt &KnownZero, APInt &KnownOne, 71e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Depth) { 72e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask, 73e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero, KnownOne, Depth); 74e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (NewVal == 0) return false; 75e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner U = NewVal; 76e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return true; 77e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 78e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 79e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 80e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedUseBits - This function attempts to replace V with a simpler 81e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// value based on the demanded bits. When this function is called, it is known 82e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// that only the bits set in DemandedMask of the result of V are ever used 83e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// downstream. Consequently, depending on the mask and V, it may be possible 84e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// to replace V with a constant or one of its operands. In such cases, this 85e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// function does the replacement and returns true. In all other cases, it 86e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// returns false after analyzing the expression and setting KnownOne and known 87e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// to be one in the expression. KnownZero contains all the bits that are known 88e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// to be zero in the expression. These are provided to potentially allow the 89e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// caller (which might recursively be SimplifyDemandedBits itself) to simplify 908a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper/// the expression. KnownOne and KnownZero always follow the invariant that 91e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// KnownOne & KnownZero == 0. That is, a bit can't be both 1 and 0. Note that 92e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// the bits in KnownOne and KnownZero may only be accurate for those bits set 93e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// in DemandedMask. Note also that the bitwidth of V, DemandedMask, KnownZero 94e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// and KnownOne must all be the same. 95e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// 96e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// This returns null if it did not change anything and it permits no 97e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// simplification. This returns V itself if it did some simplification of V's 98e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// operands based on the information about what bits are demanded. This returns 99e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// some other non-null value if it found out that V is equal to another value 100e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// in the context where the specified bits are demanded, but not for all users. 101e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris LattnerValue *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, 102e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt &KnownZero, APInt &KnownOne, 103e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Depth) { 104e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(V != 0 && "Null pointer of Value???"); 105e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(Depth <= 6 && "Limit Search Depth"); 106e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner uint32_t BitWidth = DemandedMask.getBitWidth(); 107db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *VTy = V->getType(); 1081df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands assert((TD || !VTy->isPointerTy()) && 109e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner "SimplifyDemandedBits needs to know bit widths!"); 110e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert((!TD || TD->getTypeSizeInBits(VTy->getScalarType()) == BitWidth) && 111b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands (!VTy->isIntOrIntVectorTy() || 112e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner VTy->getScalarSizeInBits() == BitWidth) && 113e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero.getBitWidth() == BitWidth && 114e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownOne.getBitWidth() == BitWidth && 115e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner "Value *V, DemandedMask, KnownZero and KnownOne " 116e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner "must have same BitWidth"); 117e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 118e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // We know all of the bits for a constant! 119e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownOne = CI->getValue() & DemandedMask; 120e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero = ~KnownOne & DemandedMask; 121e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 122e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 123e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (isa<ConstantPointerNull>(V)) { 124e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // We know all of the bits for a constant! 1257a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 126e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero = DemandedMask; 127e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 128e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 129e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1307a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownZero.clearAllBits(); 1317a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 132e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask == 0) { // Not demanding any bits from V. 133e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (isa<UndefValue>(V)) 134e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 135e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return UndefValue::get(VTy); 136e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1378a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 138e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth == 6) // Limit search depth. 139e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 1408a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 141e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 142ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); 143e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 144e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *I = dyn_cast<Instruction>(V); 145e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!I) { 14626c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, Depth); 147e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; // Only analyze instructions. 148e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 149e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 150e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are multiple uses of this value and we aren't at the root, then 151e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // we can't do any simplifications of the operands, because DemandedMask 152e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // only reflects the bits demanded by *one* of the users. 153e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth != 0 && !I->hasOneUse()) { 154e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Despite the fact that we can't simplify this instruction in all User's 155e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // context, we can at least compute the knownzero/knownone bits, and we can 156e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // do simplifications that apply to *just* the one user if we know that 157e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // this instruction has a simpler value in that context. 158e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (I->getOpcode() == Instruction::And) { 159e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If either the LHS or the RHS are Zero, the result is zero. 16026c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1); 16126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 1628a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 163e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known 1 on one side, return the other. 164e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // These bits cannot contribute to the result of the 'and' in this 165e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // context. 1668a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == 167e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~LHSKnownZero)) 168e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 1698a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == 170e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~RHSKnownZero)) 171e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 1728a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 173e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits in the inputs are known zeros, return zero. 174e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) 175e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return Constant::getNullValue(VTy); 1768a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 177e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else if (I->getOpcode() == Instruction::Or) { 178e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // We can simplify (X|Y) -> X or Y in the user's context if we know that 179e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // only bits from X or Y are demanded. 1808a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 181e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If either the LHS or the RHS are One, the result is One. 18226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1); 18326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 1848a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 185e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known zero on one side, return the 186e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // other. These bits cannot contribute to the result of the 'or' in this 187e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // context. 1888a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == 189e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~LHSKnownOne)) 190e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 1918a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == 192e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~RHSKnownOne)) 193e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 1948a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 195e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the potentially set bits on one side are known to be set on 196e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the other side, just use the 'other' side. 1978a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == 198e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & (~RHSKnownZero))) 199e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 2008a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == 201e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & (~LHSKnownZero))) 202e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 203a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang } else if (I->getOpcode() == Instruction::Xor) { 204a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang // We can simplify (X^Y) -> X or Y in the user's context if we know that 205a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang // only bits from X or Y are demanded. 2068a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 207a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1); 208a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 2098a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 210a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang // If all of the demanded bits are known zero on one side, return the 2118a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper // other. 212a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang if ((DemandedMask & RHSKnownZero) == DemandedMask) 213a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang return I->getOperand(0); 214a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang if ((DemandedMask & LHSKnownZero) == DemandedMask) 215a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang return I->getOperand(1); 216e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 217a09e18fcfab0e998526724357f8fc5ef7f4c3e7aShuxin Yang 218e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the KnownZero/KnownOne bits to simplify things downstream. 21926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I, KnownZero, KnownOne, Depth); 220e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 221e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 2228a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 223e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If this is the root being simplified, allow it to have multiple uses, 224e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // just set the DemandedMask to all bits so that we can try to simplify the 225e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // operands. This allows visitTruncInst (for example) to simplify the 226e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // operand of a trunc without duplicating all the logic below. 227e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth == 0 && !V->hasOneUse()) 228e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner DemandedMask = APInt::getAllOnesValue(BitWidth); 2298a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 230e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (I->getOpcode()) { 231e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: 23226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I, KnownZero, KnownOne, Depth); 233e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 234e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::And: 235e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If either the LHS or the RHS are Zero, the result is zero. 236e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 237e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner RHSKnownZero, RHSKnownOne, Depth+1) || 238e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownZero, 239e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 240e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 2418a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 2428a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 243e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 244e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known 1 on one side, return the other. 245e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // These bits cannot contribute to the result of the 'and'. 2468a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == 247e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~LHSKnownZero)) 248e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 2498a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == 250e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~RHSKnownZero)) 251e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 2528a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 253e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits in the inputs are known zeros, return zero. 254e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) 255e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return Constant::getNullValue(VTy); 2568a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 257e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the RHS is a constant, see if we can simplify it. 258e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnownZero)) 259e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 2608a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 261e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output known-1 bits are only known if set in both the LHS & RHS. 262ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = RHSKnownOne & LHSKnownOne; 263e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output known-0 are known to be clear if zero in either the LHS | RHS. 264ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = RHSKnownZero | LHSKnownZero; 265e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 266e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Or: 267e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If either the LHS or the RHS are One, the result is One. 2688a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 269e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner RHSKnownZero, RHSKnownOne, Depth+1) || 2708a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownOne, 271e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 272e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 2738a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 2748a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 2758a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 276e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known zero on one side, return the other. 277e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // These bits cannot contribute to the result of the 'or'. 2788a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == 279e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~LHSKnownOne)) 280e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 2818a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == 282e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & ~RHSKnownOne)) 283e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 284e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 285e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the potentially set bits on one side are known to be set on 286e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the other side, just use the 'other' side. 2878a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == 288e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & (~RHSKnownZero))) 289e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 2908a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == 291e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (DemandedMask & (~LHSKnownZero))) 292e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 2938a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 294e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the RHS is a constant, see if we can simplify it. 295e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, DemandedMask)) 296e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 2978a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 298e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output known-0 bits are only known if clear in both the LHS & RHS. 299ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = RHSKnownZero & LHSKnownZero; 300e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output known-1 are known to be set if set in either the LHS | RHS. 301ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = RHSKnownOne | LHSKnownOne; 302e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 303e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Xor: { 304e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 305e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner RHSKnownZero, RHSKnownOne, Depth+1) || 3068a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 307e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 308e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 3098a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 3108a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 3118a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 312e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known zero on one side, return the other. 313e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // These bits cannot contribute to the result of the 'xor'. 314e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & RHSKnownZero) == DemandedMask) 315e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 316e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & LHSKnownZero) == DemandedMask) 317e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(1); 3188a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 319e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits are known to be zero on one side or the 320e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // other, turn this into an *inclusive* or. 32194c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 322e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((DemandedMask & ~RHSKnownZero & ~LHSKnownZero) == 0) { 3238a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper Instruction *Or = 324e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1), 325e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->getName()); 3266fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(Or, *I); 327e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 3288a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 329e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If all of the demanded bits on one side are known, and all of the set 330e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // bits on that side are also known to be set on the other side, turn this 331e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // into an AND, as we know the bits will be cleared. 33294c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 3338a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if ((DemandedMask & (RHSKnownZero|RHSKnownOne)) == DemandedMask) { 334e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // all known 335e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((RHSKnownOne & LHSKnownOne) == RHSKnownOne) { 336e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Constant *AndC = Constant::getIntegerValue(VTy, 337e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ~RHSKnownOne & DemandedMask); 338a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 3396fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(And, *I); 340e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 341e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 3428a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 343e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the RHS is a constant, see if we can simplify it. 344e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1. 345e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, DemandedMask)) 346e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 3478a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 348e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If our LHS is an 'and' and if it has one use, and if any of the bits we 349e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // are flipping are known to be set, then the xor is just resetting those 350e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // bits to zero. We can just knock out bits from the 'and' and the 'xor', 351e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // simplifying both of them. 352e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0))) 353e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() && 354e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner isa<ConstantInt>(I->getOperand(1)) && 355e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner isa<ConstantInt>(LHSInst->getOperand(1)) && 356e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (LHSKnownOne & RHSKnownOne & DemandedMask) != 0) { 357e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt *AndRHS = cast<ConstantInt>(LHSInst->getOperand(1)); 358e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt *XorRHS = cast<ConstantInt>(I->getOperand(1)); 359e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt NewMask = ~(LHSKnownOne & RHSKnownOne & DemandedMask); 3608a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 361e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Constant *AndC = 362e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(I->getType(), NewMask & AndRHS->getValue()); 363a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC); 3646fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman InsertNewInstWith(NewAnd, *I); 3658a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 366e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Constant *XorC = 367e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(I->getType(), NewMask & XorRHS->getValue()); 368a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC); 3696fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewXor, *I); 370e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 371ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands 372ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands // Output known-0 bits are known if clear or set in both the LHS & RHS. 373ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero= (RHSKnownZero & LHSKnownZero) | (RHSKnownOne & LHSKnownOne); 374ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands // Output known-1 are known to be set if set in only one of the LHS, RHS. 375ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = (RHSKnownZero & LHSKnownOne) | (RHSKnownOne & LHSKnownZero); 376e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 377e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 378e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Select: 379e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(2), DemandedMask, 380e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner RHSKnownZero, RHSKnownOne, Depth+1) || 3818a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, 382e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 383e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 3848a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?"); 3858a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?"); 3868a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 387e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the operands are constants, see if we can simplify them. 388e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, DemandedMask) || 389e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ShrinkDemandedConstant(I, 2, DemandedMask)) 390e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 3918a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 392e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Only known if known in both the LHS and RHS. 393ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = RHSKnownOne & LHSKnownOne; 394ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = RHSKnownZero & LHSKnownZero; 395e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 396e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Trunc: { 397e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned truncBf = I->getOperand(0)->getType()->getScalarSizeInBits(); 39840f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad DemandedMask = DemandedMask.zext(truncBf); 39940f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zext(truncBf); 40040f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zext(truncBf); 4018a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 402ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 403e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 40440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad DemandedMask = DemandedMask.trunc(BitWidth); 40540f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.trunc(BitWidth); 40640f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.trunc(BitWidth); 4078a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 408e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 409e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 410e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::BitCast: 411b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (!I->getOperand(0)->getType()->isIntOrIntVectorTy()) 412ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; // vector->int or fp->int? 413e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 414db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (VectorType *DstVTy = dyn_cast<VectorType>(I->getType())) { 415db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (VectorType *SrcVTy = 416e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner dyn_cast<VectorType>(I->getOperand(0)->getType())) { 417e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DstVTy->getNumElements() != SrcVTy->getNumElements()) 418e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Don't touch a bitcast between vectors of different element counts. 419ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; 420e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else 421e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Don't touch a scalar-to-vector bitcast. 422ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; 4231df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands } else if (I->getOperand(0)->getType()->isVectorTy()) 424e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Don't touch a vector-to-scalar bitcast. 425ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; 426e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 427e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 428ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 429e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 4308a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 431e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 432e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::ZExt: { 433e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the bits in the result that are not present in the input. 434e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); 4358a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 43640f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad DemandedMask = DemandedMask.trunc(SrcBitWidth); 43740f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.trunc(SrcBitWidth); 43840f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.trunc(SrcBitWidth); 439e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, 440ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 441e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 44240f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad DemandedMask = DemandedMask.zext(BitWidth); 44340f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zext(BitWidth); 44440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zext(BitWidth); 4458a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 446e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // The top bits are known to be zero. 447ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 448e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 449e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 450e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::SExt: { 451e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the bits in the result that are not present in the input. 452e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); 4538a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 4548a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper APInt InputDemandedBits = DemandedMask & 455e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt::getLowBitsSet(BitWidth, SrcBitWidth); 456e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 457e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt NewBits(APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth)); 458e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If any of the sign extended bits are demanded, we know that the sign 459e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // bit is demanded. 460e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((NewBits & DemandedMask) != 0) 4617a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad InputDemandedBits.setBit(SrcBitWidth-1); 4628a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 46340f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad InputDemandedBits = InputDemandedBits.trunc(SrcBitWidth); 46440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.trunc(SrcBitWidth); 46540f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.trunc(SrcBitWidth); 466e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), InputDemandedBits, 467ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 468e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 46940f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad InputDemandedBits = InputDemandedBits.zext(BitWidth); 47040f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zext(BitWidth); 47140f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zext(BitWidth); 4728a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 4738a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 474e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the sign bit of the input is known set or clear, then we know the 475e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // top bits of the result. 476e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 477e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the input sign bit is known zero, or if the NewBits are not demanded 478e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // convert this into a zero extension. 479ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands if (KnownZero[SrcBitWidth-1] || (NewBits & ~DemandedMask) == NewBits) { 480e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Convert to ZExt cast 481e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName()); 4826fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewCast, *I); 483ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands } else if (KnownOne[SrcBitWidth-1]) { // Input sign bit known set 484ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne |= NewBits; 485e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 486e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 487e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 488e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Add: { 489e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Figure out what the input bits are. If the top bits of the and result 490e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // are not demanded, then the add doesn't demand them from its input 491e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // either. 492e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned NLZ = DemandedMask.countLeadingZeros(); 4938a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 494e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there is a constant on the RHS, there are a variety of xformations 495e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // we can do. 496e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) { 497e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If null, this should be simplified elsewhere. Some of the xforms here 498e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // won't work if the RHS is zero. 499e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (RHS->isZero()) 500e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 5018a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 502e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the top bit of the output is demanded, demand everything from the 503e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // input. Otherwise, we demand all the input bits except NLZ top bits. 504e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt InDemandedBits(APInt::getLowBitsSet(BitWidth, BitWidth - NLZ)); 505e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 506e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Find information about known zero/one bits in the input. 5078a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if (SimplifyDemandedBits(I->getOperandUse(0), InDemandedBits, 508e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 509e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 510e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 511e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the RHS of the add has bits set that can't affect the input, reduce 512e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the constant. 513e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShrinkDemandedConstant(I, 1, InDemandedBits)) 514e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 5158a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 516e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Avoid excess work. 517e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (LHSKnownZero == 0 && LHSKnownOne == 0) 518e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 5198a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 520e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Turn it into OR if input bits are zero. 521e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if ((LHSKnownZero & RHS->getValue()) == RHS->getValue()) { 522e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *Or = 523e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1), 524e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->getName()); 5256fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(Or, *I); 526e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 5278a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 528e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // We can say something about the output known-zero and known-one bits, 529e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // depending on potential carries from the input constant and the 530e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // unknowns. For example if the LHS is known to have at most the 0x0F0F0 531e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // bits set and the RHS constant is 0x01001, then we know we have a known 532e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // one mask of 0x00001 and a known zero mask of 0xE0F0E. 5338a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 534e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // To compute this, we first compute the potential carry bits. These are 535e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the bits which may be modified. I'm not aware of a better way to do 536e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // this scan. 537e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner const APInt &RHSVal = RHS->getValue(); 538e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt CarryBits((~LHSKnownZero + RHSVal) ^ (~LHSKnownZero ^ RHSVal)); 5398a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 540e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Now that we know which bits have carries, compute the known-1/0 sets. 5418a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 542e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Bits are known one if they are known zero in one operand and one in the 543e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // other, and there is no input carry. 5448a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper KnownOne = ((LHSKnownZero & RHSVal) | 545ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands (LHSKnownOne & ~RHSVal)) & ~CarryBits; 5468a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 547e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Bits are known zero if they are known zero in both operands and there 548e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // is no input carry. 549ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = LHSKnownZero & ~RHSVal & ~CarryBits; 550e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else { 551e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the high-bits of this ADD are not demanded, then it does not demand 552e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the high bits of its LHS or RHS. 553e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask[BitWidth-1] == 0) { 554e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Right fill the mask of bits for this ADD to demand the most 555e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // significant bit and all those below it. 556e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ)); 557e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps, 558e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1) || 559e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps, 560e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 561e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 562e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 563e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 564e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 565e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 566e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Sub: 567e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the high-bits of this SUB are not demanded, then it does not demand 568e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the high bits of its LHS or RHS. 569e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask[BitWidth-1] == 0) { 570e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Right fill the mask of bits for this SUB to demand the most 571e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // significant bit and all those below it. 572e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner uint32_t NLZ = DemandedMask.countLeadingZeros(); 573e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ)); 574e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps, 575e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1) || 576e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps, 577e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 578e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 579e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 5801fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer 581e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Otherwise just hand the sub off to ComputeMaskedBits to fill in 582e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the known zeros and ones. 58326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, Depth); 5841fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer 5851fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known 5861fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer // zero. 5871fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer if (ConstantInt *C0 = dyn_cast<ConstantInt>(I->getOperand(0))) { 5881fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer APInt I0 = C0->getValue(); 5891fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer if ((I0 + 1).isPowerOf2() && (I0 | KnownZero).isAllOnesValue()) { 5901fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer Instruction *Xor = BinaryOperator::CreateXor(I->getOperand(1), C0); 5911fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer return InsertNewInstWith(Xor, *I); 5921fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer } 5931fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer } 594e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 595e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Shl: 596e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 597c811976b0400257511f2a255ec70538c3614f85eShuxin Yang { 598c811976b0400257511f2a255ec70538c3614f85eShuxin Yang Value *VarX; ConstantInt *C1; 599c811976b0400257511f2a255ec70538c3614f85eShuxin Yang if (match(I->getOperand(0), m_Shr(m_Value(VarX), m_ConstantInt(C1)))) { 600c811976b0400257511f2a255ec70538c3614f85eShuxin Yang Instruction *Shr = cast<Instruction>(I->getOperand(0)); 601c811976b0400257511f2a255ec70538c3614f85eShuxin Yang Value *R = SimplifyShrShlDemandedBits(Shr, I, DemandedMask, 602c811976b0400257511f2a255ec70538c3614f85eShuxin Yang KnownZero, KnownOne); 603c811976b0400257511f2a255ec70538c3614f85eShuxin Yang if (R) 604c811976b0400257511f2a255ec70538c3614f85eShuxin Yang return R; 605c811976b0400257511f2a255ec70538c3614f85eShuxin Yang } 606c811976b0400257511f2a255ec70538c3614f85eShuxin Yang } 607c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 608a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 609e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt)); 6108a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 611a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // If the shift is NUW/NSW, then it does demand the high bits. 612a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner ShlOperator *IOp = cast<ShlOperator>(I); 613a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner if (IOp->hasNoSignedWrap()) 614a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1); 615a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner else if (IOp->hasNoUnsignedWrap()) 616a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 6178a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 6188a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, 619ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 620e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 621ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 622ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero <<= ShiftAmt; 623ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne <<= ShiftAmt; 624e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // low bits known zero. 625e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShiftAmt) 626ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 627e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 628e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 629e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::LShr: 630e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // For a logical shift right 631e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 632a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 6338a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 634e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Unsigned shift right. 635e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 6368a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 637a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // If the shift is exact, then it does demand the low bits (and knows that 638a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // they are zero). 639a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner if (cast<LShrOperator>(I)->isExact()) 640a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 6418a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 642e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, 643ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 644e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 645ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 646ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 647ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 648e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ShiftAmt) { 649e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the new bits that are at the top now. 650e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 651ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero |= HighBits; // high bits known zero. 652e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 653e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 654e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 655e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::AShr: 656e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If this is an arithmetic shift right and only the low-bit is set, we can 657e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // always convert this into a logical shr, even if the shift amount is 658e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // variable. The low bit of the shift cannot be an input sign bit unless 659e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the shift amount is >= the size of the datatype, which is undefined. 660e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask == 1) { 661e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Perform the logical shift right. 662e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *NewVal = BinaryOperator::CreateLShr( 663e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->getOperand(0), I->getOperand(1), I->getName()); 6646fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewVal, *I); 6658a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper } 666e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 667e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the sign bit is the only bit demanded by this ashr, then there is no 668e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // need to do it, the shift doesn't change the high bit. 669e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask.isSignBit()) 670e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 6718a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 672e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 673a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 6748a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 675e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Signed shift right. 676e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); 677e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If any of the "high bits" are demanded, we should set the sign bit as 678e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // demanded. 679e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask.countLeadingZeros() <= ShiftAmt) 6807a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad DemandedMaskIn.setBit(BitWidth-1); 6818a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 682a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // If the shift is exact, then it does demand the low bits (and knows that 683a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner // they are zero). 684a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner if (cast<AShrOperator>(I)->isExact()) 685a81556fb52e39e3f6cde0c11c1acd2bdf8a560a2Chris Lattner DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 6868a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 687e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, 688ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero, KnownOne, Depth+1)) 689e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 690ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 691e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Compute the new bits that are at the top now. 692e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 693ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 694ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 6958a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 696e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Handle the sign bits. 697e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt SignBit(APInt::getSignBit(BitWidth)); 698e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Adjust to where it is now in the mask. 6998a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper SignBit = APIntOps::lshr(SignBit, ShiftAmt); 7008a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 701e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the input sign bit is known to be zero, or if none of the top bits 702e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // are demanded, turn this into an unsigned shift right. 7038a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper if (BitWidth <= ShiftAmt || KnownZero[BitWidth-ShiftAmt-1] || 704e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner (HighBits & ~DemandedMask) == HighBits) { 705e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Perform the logical shift right. 706148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky BinaryOperator *NewVal = BinaryOperator::CreateLShr(I->getOperand(0), 707148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky SA, I->getName()); 708148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky NewVal->setIsExact(cast<BinaryOperator>(I)->isExact()); 7096fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewVal, *I); 710ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands } else if ((KnownOne & SignBit) != 0) { // New bits are known one. 711ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne |= HighBits; 712e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 713e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 714e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 715e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::SRem: 716e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 717c6b018b7379f4e1bcc4166a07b17d08180ed776dEli Friedman // X % -1 demands all the bits because we don't want to introduce 718c6b018b7379f4e1bcc4166a07b17d08180ed776dEli Friedman // INT_MIN % -1 (== undef) by accident. 719c6b018b7379f4e1bcc4166a07b17d08180ed776dEli Friedman if (Rem->isAllOnesValue()) 720c6b018b7379f4e1bcc4166a07b17d08180ed776dEli Friedman break; 721e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt RA = Rem->getValue().abs(); 722e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (RA.isPowerOf2()) { 723e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedMask.ult(RA)) // srem won't affect demanded bits 724e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 725e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 726e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt LowBits = RA - 1; 727e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 728e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), Mask2, 729e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner LHSKnownZero, LHSKnownOne, Depth+1)) 730e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 731e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 7322c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // The low bits of LHS are unchanged by the srem. 733ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownZero = LHSKnownZero & LowBits; 734ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands KnownOne = LHSKnownOne & LowBits; 7352c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands 7362c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // If LHS is non-negative or has all low bits zero, then the upper bits 7372c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // are all zero. 738e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (LHSKnownZero[BitWidth-1] || ((LHSKnownZero & LowBits) == LowBits)) 7392c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands KnownZero |= ~LowBits; 740e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 7412c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // If LHS is negative and not all low bits are zero, then the upper bits 7422c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands // are all one. 7432c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands if (LHSKnownOne[BitWidth-1] && ((LHSKnownOne & LowBits) != 0)) 7442c47368a7d843486a59e12a08595297003e3cb2dDuncan Sands KnownOne |= ~LowBits; 745e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 7468a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?"); 747e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 748e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 749c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky 750c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // The sign bit is the LHS's sign bit, except when the result of the 751c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // remainder is zero. 752c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky if (DemandedMask.isNegative() && KnownZero.isNonNegative()) { 753c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 75426c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1); 755c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // If it's known zero, our sign bit is also zero. 756c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky if (LHSKnownZero.isNegative()) 757c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky KnownZero |= LHSKnownZero; 758c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky } 759e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 760e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::URem: { 761e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0); 762e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 763e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (SimplifyDemandedBits(I->getOperandUse(0), AllOnes, 764e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero2, KnownOne2, Depth+1) || 765e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner SimplifyDemandedBits(I->getOperandUse(1), AllOnes, 766e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero2, KnownOne2, Depth+1)) 767e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I; 768e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 769e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Leaders = KnownZero2.countLeadingOnes(); 770e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Leaders = std::max(Leaders, 771e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero2.countLeadingOnes()); 772e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask; 773e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 774e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 775e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Call: 776e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 777e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (II->getIntrinsicID()) { 778e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: break; 779e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::bswap: { 780e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the only bits demanded come from one byte of the bswap result, 781e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // just shift the input byte into position to eliminate the bswap. 782e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned NLZ = DemandedMask.countLeadingZeros(); 783e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned NTZ = DemandedMask.countTrailingZeros(); 7848a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 785e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Round NTZ down to the next byte. If we have 11 trailing zeros, then 786e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // we need all the bits down to bit 8. Likewise, round NLZ. If we 787e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // have 14 leading zeros, round to 8. 788e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NLZ &= ~7; 789e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NTZ &= ~7; 790e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If we need exactly one byte, we can do this transformation. 791e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (BitWidth-NLZ-NTZ == 8) { 792e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned ResultBit = NTZ; 793e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned InputBit = BitWidth-NTZ-8; 7948a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 795e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Replace this with either a left or right shift to get the byte into 796e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the right place. 797e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *NewVal; 798e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (InputBit > ResultBit) 7993e84e2e90f560aa75e08957e1509b9e6d9d502bbGabor Greif NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0), 800e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(I->getType(), InputBit-ResultBit)); 801e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner else 8023e84e2e90f560aa75e08957e1509b9e6d9d502bbGabor Greif NewVal = BinaryOperator::CreateShl(II->getArgOperand(0), 803e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(I->getType(), ResultBit-InputBit)); 804e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NewVal->takeName(I); 8056fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman return InsertNewInstWith(NewVal, *I); 806e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 8078a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 808e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // TODO: Could compute known zero/one bits based on the input. 809e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 810e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 81162660310d9e5f9ecf329fd3cacb67c344a12ddbcChad Rosier case Intrinsic::x86_sse42_crc32_64_8: 81262660310d9e5f9ecf329fd3cacb67c344a12ddbcChad Rosier case Intrinsic::x86_sse42_crc32_64_64: 8132e6496026f41d2c05ff038d14df9972f8a27fb94Evan Cheng KnownZero = APInt::getHighBitsSet(64, 32); 8142e6496026f41d2c05ff038d14df9972f8a27fb94Evan Cheng return 0; 815e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 816e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 81726c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, Depth); 818e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 819e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 8208a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 821e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the client is only demanding bits that we know, return the known 822e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // constant. 823ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) 824ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return Constant::getIntegerValue(VTy, KnownOne); 825ac512171ff12829c5961ca2614dfaf4b37bf8c2eDuncan Sands return 0; 826e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 827e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 828c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// Helper routine of SimplifyDemandedUseBits. It tries to simplify 829c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into 830c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign 831c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// of "C2-C1". 832c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// 833c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// Suppose E1 and E2 are generally different in bits S={bm, bm+1, 834c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// ..., bn}, without considering the specific value X is holding. 835c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// This transformation is legal iff one of following conditions is hold: 836c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// 1) All the bit in S are 0, in this case E1 == E2. 837c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// 2) We don't care those bits in S, per the input DemandedMask. 838c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// 3) Combination of 1) and 2). Some bits in S are 0, and we don't care the 839c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// rest bits. 840c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// 841c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// Currently we only test condition 2). 842c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// 843c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// As with SimplifyDemandedUseBits, it returns NULL if the simplification was 844c811976b0400257511f2a255ec70538c3614f85eShuxin Yang/// not successful. 845c811976b0400257511f2a255ec70538c3614f85eShuxin YangValue *InstCombiner::SimplifyShrShlDemandedBits(Instruction *Shr, 846c811976b0400257511f2a255ec70538c3614f85eShuxin Yang Instruction *Shl, APInt DemandedMask, APInt &KnownZero, APInt &KnownOne) { 847c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 848c811976b0400257511f2a255ec70538c3614f85eShuxin Yang unsigned ShlAmt = cast<ConstantInt>(Shl->getOperand(1))->getZExtValue(); 849c811976b0400257511f2a255ec70538c3614f85eShuxin Yang unsigned ShrAmt = cast<ConstantInt>(Shr->getOperand(1))->getZExtValue(); 850c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 851c811976b0400257511f2a255ec70538c3614f85eShuxin Yang KnownOne.clearAllBits(); 852c811976b0400257511f2a255ec70538c3614f85eShuxin Yang KnownZero = APInt::getBitsSet(KnownZero.getBitWidth(), 0, ShlAmt-1); 853c811976b0400257511f2a255ec70538c3614f85eShuxin Yang KnownZero &= DemandedMask; 854c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 855c811976b0400257511f2a255ec70538c3614f85eShuxin Yang if (ShlAmt == 0 || ShrAmt == 0) 856c811976b0400257511f2a255ec70538c3614f85eShuxin Yang return 0; 857c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 858c811976b0400257511f2a255ec70538c3614f85eShuxin Yang Value *VarX = Shr->getOperand(0); 859c811976b0400257511f2a255ec70538c3614f85eShuxin Yang Type *Ty = VarX->getType(); 860c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 8615f70c2e934c8cf7814fc047f4824ac89b35dd72dShuxin Yang APInt BitMask1(APInt::getAllOnesValue(Ty->getIntegerBitWidth())); 8625f70c2e934c8cf7814fc047f4824ac89b35dd72dShuxin Yang APInt BitMask2(APInt::getAllOnesValue(Ty->getIntegerBitWidth())); 863c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 864c811976b0400257511f2a255ec70538c3614f85eShuxin Yang bool isLshr = (Shr->getOpcode() == Instruction::LShr); 865c811976b0400257511f2a255ec70538c3614f85eShuxin Yang BitMask1 = isLshr ? (BitMask1.lshr(ShrAmt) << ShlAmt) : 866c811976b0400257511f2a255ec70538c3614f85eShuxin Yang (BitMask1.ashr(ShrAmt) << ShlAmt); 867c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 868c811976b0400257511f2a255ec70538c3614f85eShuxin Yang if (ShrAmt <= ShlAmt) { 869c811976b0400257511f2a255ec70538c3614f85eShuxin Yang BitMask2 <<= (ShlAmt - ShrAmt); 870c811976b0400257511f2a255ec70538c3614f85eShuxin Yang } else { 871c811976b0400257511f2a255ec70538c3614f85eShuxin Yang BitMask2 = isLshr ? BitMask2.lshr(ShrAmt - ShlAmt): 872c811976b0400257511f2a255ec70538c3614f85eShuxin Yang BitMask2.ashr(ShrAmt - ShlAmt); 873c811976b0400257511f2a255ec70538c3614f85eShuxin Yang } 874c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 875c811976b0400257511f2a255ec70538c3614f85eShuxin Yang // Check if condition-2 (see the comment to this function) is satified. 876c811976b0400257511f2a255ec70538c3614f85eShuxin Yang if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) { 877c811976b0400257511f2a255ec70538c3614f85eShuxin Yang if (ShrAmt == ShlAmt) 878c811976b0400257511f2a255ec70538c3614f85eShuxin Yang return VarX; 879c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 880c811976b0400257511f2a255ec70538c3614f85eShuxin Yang if (!Shr->hasOneUse()) 881c811976b0400257511f2a255ec70538c3614f85eShuxin Yang return 0; 882c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 883c811976b0400257511f2a255ec70538c3614f85eShuxin Yang BinaryOperator *New; 884c811976b0400257511f2a255ec70538c3614f85eShuxin Yang if (ShrAmt < ShlAmt) { 885c811976b0400257511f2a255ec70538c3614f85eShuxin Yang Constant *Amt = ConstantInt::get(VarX->getType(), ShlAmt - ShrAmt); 886c811976b0400257511f2a255ec70538c3614f85eShuxin Yang New = BinaryOperator::CreateShl(VarX, Amt); 887c811976b0400257511f2a255ec70538c3614f85eShuxin Yang BinaryOperator *Orig = cast<BinaryOperator>(Shl); 888c811976b0400257511f2a255ec70538c3614f85eShuxin Yang New->setHasNoSignedWrap(Orig->hasNoSignedWrap()); 889c811976b0400257511f2a255ec70538c3614f85eShuxin Yang New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap()); 890c811976b0400257511f2a255ec70538c3614f85eShuxin Yang } else { 891c811976b0400257511f2a255ec70538c3614f85eShuxin Yang Constant *Amt = ConstantInt::get(VarX->getType(), ShrAmt - ShlAmt); 892bba3eb054a4e0e052cdeff22e678c52c4e59f07eShuxin Yang New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) : 893bba3eb054a4e0e052cdeff22e678c52c4e59f07eShuxin Yang BinaryOperator::CreateAShr(VarX, Amt); 8945f70c2e934c8cf7814fc047f4824ac89b35dd72dShuxin Yang if (cast<BinaryOperator>(Shr)->isExact()) 8955f70c2e934c8cf7814fc047f4824ac89b35dd72dShuxin Yang New->setIsExact(true); 896c811976b0400257511f2a255ec70538c3614f85eShuxin Yang } 897c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 898c811976b0400257511f2a255ec70538c3614f85eShuxin Yang return InsertNewInstWith(New, *Shl); 899c811976b0400257511f2a255ec70538c3614f85eShuxin Yang } 900c811976b0400257511f2a255ec70538c3614f85eShuxin Yang 901c811976b0400257511f2a255ec70538c3614f85eShuxin Yang return 0; 902c811976b0400257511f2a255ec70538c3614f85eShuxin Yang} 903e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 904e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// SimplifyDemandedVectorElts - The specified value produces a vector with 905e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// any number of elements. DemandedElts contains the set of elements that are 906e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// actually used by the caller. This method analyzes which elements of the 907e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// operand are undef and returns that information in UndefElts. 908e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// 909e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// If the information about demanded elements can be used to simplify the 910e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// operation, the operation is simplified, then the resultant value is 911e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner/// returned. This returns null if no change was made. 912e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris LattnerValue *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, 9138609fda0f7e4446de85f882755601ffcbd540324Chris Lattner APInt &UndefElts, 914e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Depth) { 915e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned VWidth = cast<VectorType>(V->getType())->getNumElements(); 916e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt EltMask(APInt::getAllOnesValue(VWidth)); 917e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!"); 918e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 919e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (isa<UndefValue>(V)) { 920e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If the entire vector is undefined, just return this info. 921e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = EltMask; 922e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 9238609fda0f7e4446de85f882755601ffcbd540324Chris Lattner } 9248a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 9258609fda0f7e4446de85f882755601ffcbd540324Chris Lattner if (DemandedElts == 0) { // If nothing is demanded, provide undef. 926e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = EltMask; 927e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return UndefValue::get(V->getType()); 928e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 929e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 930e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = 0; 9318a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 932a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner // Handle ConstantAggregateZero, ConstantVector, ConstantDataSequential. 933a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (Constant *C = dyn_cast<Constant>(V)) { 934a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner // Check if this is identity. If so, return 0 since we are not simplifying 935a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner // anything. 936a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (DemandedElts.isAllOnesValue()) 937a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner return 0; 938a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner 939db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *EltTy = cast<VectorType>(V->getType())->getElementType(); 940e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Constant *Undef = UndefValue::get(EltTy); 9418a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 942a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner SmallVector<Constant*, 16> Elts; 943a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner for (unsigned i = 0; i != VWidth; ++i) { 944e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!DemandedElts[i]) { // If not demanded, set to undef. 945e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Elts.push_back(Undef); 9467a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 947a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner continue; 948a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner } 9498a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 950a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner Constant *Elt = C->getAggregateElement(i); 951a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (Elt == 0) return 0; 9528a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 953a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (isa<UndefValue>(Elt)) { // Already undef. 954e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Elts.push_back(Undef); 9557a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 956e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else { // Otherwise, defined. 957a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner Elts.push_back(Elt); 958e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 959a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner } 9608a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 961e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If we changed the constant, return it. 9624ca829e89567f002fc74eb0e3e532a7c7662e031Chris Lattner Constant *NewCV = ConstantVector::get(Elts); 963a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner return NewCV != C ? NewCV : 0; 964e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 9658a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 966e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Limit search depth. 967e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth == 10) 968e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 969e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 970ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings // If multiple users are using the root value, proceed with 971e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // simplification conservatively assuming that all elements 972e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // are needed. 973e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!V->hasOneUse()) { 974e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Quit if we find multiple users of a non-root value though. 975e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // They'll be handled when it's their turn to be visited by 976e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // the main instcombine process. 977e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Depth != 0) 978e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // TODO: Just compute the UndefElts information recursively. 979e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return 0; 980e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 981e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Conservatively assume that all elements are needed. 982e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner DemandedElts = EltMask; 983e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 9848a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 985e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *I = dyn_cast<Instruction>(V); 986e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!I) return 0; // Only analyze instructions. 9878a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 988e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner bool MadeChange = false; 989e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt UndefElts2(VWidth, 0); 990e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Value *TmpV; 991e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (I->getOpcode()) { 992e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: break; 9938a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 994e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::InsertElement: { 995e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If this is a variable index, we don't know which element it overwrites. 996e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // demand exactly the same input as we produce. 997e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2)); 998e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (Idx == 0) { 999e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Note that we can't propagate undef elt info, because we don't know 1000e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // which elt is getting updated. 1001e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 1002e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts2, Depth+1); 1003e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1004e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1005e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 10068a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1007e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If this is inserting an element that isn't demanded, remove this 1008e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // insertelement. 1009e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned IdxNo = Idx->getZExtValue(); 1010e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (IdxNo >= VWidth || !DemandedElts[IdxNo]) { 1011e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Worklist.Add(I); 1012e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return I->getOperand(0); 1013e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 10148a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1015e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Otherwise, the element inserted overwrites whatever was there, so the 1016e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // input demanded set is simpler than the output set. 1017e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt DemandedElts2 = DemandedElts; 10187a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad DemandedElts2.clearBit(IdxNo); 1019e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts2, 1020e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts, Depth+1); 1021e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1022e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1023e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // The inserted element is defined. 10247a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.clearBit(IdxNo); 1025e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1026e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1027e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::ShuffleVector: { 1028e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I); 1029e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner uint64_t LHSVWidth = 1030e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner cast<VectorType>(Shuffle->getOperand(0)->getType())->getNumElements(); 1031e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt LeftDemanded(LHSVWidth, 0), RightDemanded(LHSVWidth, 0); 1032e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned i = 0; i < VWidth; i++) { 1033e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedElts[i]) { 1034e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned MaskVal = Shuffle->getMaskValue(i); 1035e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (MaskVal != -1u) { 1036e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner assert(MaskVal < LHSVWidth * 2 && 1037e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner "shufflevector mask index out of range!"); 1038e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (MaskVal < LHSVWidth) 10397a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad LeftDemanded.setBit(MaskVal); 1040e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner else 10417a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad RightDemanded.setBit(MaskVal - LHSVWidth); 1042e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1043e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1044e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1045e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1046e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt UndefElts4(LHSVWidth, 0); 1047e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), LeftDemanded, 1048e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts4, Depth+1); 1049e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1050e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1051e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt UndefElts3(LHSVWidth, 0); 1052e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(1), RightDemanded, 1053e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts3, Depth+1); 1054e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 1055e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1056e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner bool NewUndefElts = false; 1057e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned i = 0; i < VWidth; i++) { 1058e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned MaskVal = Shuffle->getMaskValue(i); 1059e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (MaskVal == -1u) { 10607a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 1061c82751dd6761e3db62668b6b1cfddd4f659855b6Eli Friedman } else if (!DemandedElts[i]) { 1062c82751dd6761e3db62668b6b1cfddd4f659855b6Eli Friedman NewUndefElts = true; 1063c82751dd6761e3db62668b6b1cfddd4f659855b6Eli Friedman UndefElts.setBit(i); 1064e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else if (MaskVal < LHSVWidth) { 1065e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (UndefElts4[MaskVal]) { 1066e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NewUndefElts = true; 10677a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 1068e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1069e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else { 1070e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (UndefElts3[MaskVal - LHSVWidth]) { 1071e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner NewUndefElts = true; 10727a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(i); 1073e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1074e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1075e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1076e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1077e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (NewUndefElts) { 1078e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Add additional discovered undefs. 1079a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner SmallVector<Constant*, 16> Elts; 1080e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned i = 0; i < VWidth; ++i) { 1081e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (UndefElts[i]) 1082e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Elts.push_back(UndefValue::get(Type::getInt32Ty(I->getContext()))); 1083e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner else 1084e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Elts.push_back(ConstantInt::get(Type::getInt32Ty(I->getContext()), 1085e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Shuffle->getMaskValue(i))); 1086e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1087e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->setOperand(2, ConstantVector::get(Elts)); 1088e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner MadeChange = true; 1089e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1090e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1091e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 10927971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper case Instruction::Select: { 10937971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper APInt LeftDemanded(DemandedElts), RightDemanded(DemandedElts); 10947971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper if (ConstantVector* CV = dyn_cast<ConstantVector>(I->getOperand(0))) { 10957971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper for (unsigned i = 0; i < VWidth; i++) { 10967971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper if (CV->getAggregateElement(i)->isNullValue()) 10977971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper LeftDemanded.clearBit(i); 10987971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper else 10997971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper RightDemanded.clearBit(i); 11007971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper } 11017971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper } 11027971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper 11037971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper TmpV = SimplifyDemandedVectorElts(I->getOperand(1), LeftDemanded, 11047971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper UndefElts, Depth+1); 11057971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 11067971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper 11077971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper TmpV = SimplifyDemandedVectorElts(I->getOperand(2), RightDemanded, 11087971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper UndefElts2, Depth+1); 11097971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper if (TmpV) { I->setOperand(2, TmpV); MadeChange = true; } 11108a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 11117971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper // Output elements are undefined if both are undefined. 11127971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper UndefElts &= UndefElts2; 11137971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper break; 11147971de4178d3be9b31ac03c20e2b50c3e7f4641cPete Cooper } 1115e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::BitCast: { 1116e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Vector->vector casts only. 1117db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType()); 1118e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!VTy) break; 1119e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned InVWidth = VTy->getNumElements(); 1120e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner APInt InputDemandedElts(InVWidth, 0); 1121e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner unsigned Ratio; 1122e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1123e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (VWidth == InVWidth) { 1124e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If we are converting from <4 x i32> -> <4 x f32>, we demand the same 1125e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // elements as are demanded of us. 1126e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Ratio = 1; 1127e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner InputDemandedElts = DemandedElts; 1128e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else if (VWidth > InVWidth) { 1129e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Untested so far. 1130e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 11318a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1132e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are more elements in the result than there are in the source, 1133e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // then an input element is live if any of the corresponding output 1134e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // elements are live. 1135e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Ratio = VWidth/InVWidth; 1136e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) { 1137e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedElts[OutIdx]) 11387a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad InputDemandedElts.setBit(OutIdx/Ratio); 1139e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1140e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else { 1141e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Untested so far. 1142e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 11438a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1144e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are more elements in the source than there are in the result, 1145e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // then an input element is live if the corresponding output element is 1146e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // live. 1147e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Ratio = InVWidth/VWidth; 1148e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) 1149e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedElts[InIdx/Ratio]) 11507a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad InputDemandedElts.setBit(InIdx); 1151e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 11528a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1153e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // div/rem demand all inputs, because they don't want divide by zero. 1154e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), InputDemandedElts, 1155e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts2, Depth+1); 1156e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { 1157e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner I->setOperand(0, TmpV); 1158e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner MadeChange = true; 1159e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 11608a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1161e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = UndefElts2; 1162e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (VWidth > InVWidth) { 1163e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner llvm_unreachable("Unimp"); 1164e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are more elements in the result than there are in the source, 1165e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // then an output element is undef if the corresponding input element is 1166e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // undef. 1167e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) 1168e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (UndefElts2[OutIdx/Ratio]) 11697a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.setBit(OutIdx); 1170e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } else if (VWidth < InVWidth) { 1171e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner llvm_unreachable("Unimp"); 1172e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If there are more elements in the source than there are in the result, 1173e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // then a result element is undef if all of the corresponding input 1174e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // elements are undef. 1175e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts = ~0ULL >> (64-VWidth); // Start out all undef. 1176e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) 1177e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!UndefElts2[InIdx]) // Not undef? 11787a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad UndefElts.clearBit(InIdx/Ratio); // Clear undef bit. 1179e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1180e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1181e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1182e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::And: 1183e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Or: 1184e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Xor: 1185e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Add: 1186e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Sub: 1187e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Mul: 1188e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // div/rem demand all inputs, because they don't want divide by zero. 1189e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 1190e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts, Depth+1); 1191e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 1192e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner TmpV = SimplifyDemandedVectorElts(I->getOperand(1), DemandedElts, 1193e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts2, Depth+1); 1194e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } 11958a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1196e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output elements are undefined if both are undefined. Consider things 1197e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // like undef&0. The result is known zero, not undef. 1198e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts &= UndefElts2; 1199e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 12001121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper case Instruction::FPTrunc: 12011121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper case Instruction::FPExt: 12021121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, 12031121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper UndefElts, Depth+1); 12041121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } 12051121c786fc24a4a8ce6c778cb9b5acdfa9006ffbPete Cooper break; 12068a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1207e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Instruction::Call: { 1208e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner IntrinsicInst *II = dyn_cast<IntrinsicInst>(I); 1209e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (!II) break; 1210e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (II->getIntrinsicID()) { 1211e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: break; 12128a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1213e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Binary vector operations that work column-wise. A dest element is a 1214e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // function of the corresponding input elements from the two inputs. 1215e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_sub_ss: 1216e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_mul_ss: 1217e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_min_ss: 1218e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_max_ss: 1219e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_sub_sd: 1220e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_mul_sd: 1221e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_min_sd: 1222e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_max_sd: 122330d2577f644a947d51bb81cf1b6e863d8147cccfGabor Greif TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts, 1224551754c4958086cc6910da7c950f2875e212f5cfEric Christopher UndefElts, Depth+1); 122530d2577f644a947d51bb81cf1b6e863d8147cccfGabor Greif if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } 122630d2577f644a947d51bb81cf1b6e863d8147cccfGabor Greif TmpV = SimplifyDemandedVectorElts(II->getArgOperand(1), DemandedElts, 1227551754c4958086cc6910da7c950f2875e212f5cfEric Christopher UndefElts2, Depth+1); 122830d2577f644a947d51bb81cf1b6e863d8147cccfGabor Greif if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; } 1229e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner 1230e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // If only the low elt is demanded and this is a scalarizable intrinsic, 1231e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // scalarize it now. 1232e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner if (DemandedElts == 1) { 1233e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (II->getIntrinsicID()) { 1234e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: break; 1235e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_sub_ss: 1236e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_mul_ss: 1237e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_sub_sd: 1238e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_mul_sd: 1239e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // TODO: Lower MIN/MAX/ABS/etc 12403e84e2e90f560aa75e08957e1509b9e6d9d502bbGabor Greif Value *LHS = II->getArgOperand(0); 12413e84e2e90f560aa75e08957e1509b9e6d9d502bbGabor Greif Value *RHS = II->getArgOperand(1); 1242e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Extract the element as scalars. 12438a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper LHS = InsertNewInstWith(ExtractElementInst::Create(LHS, 1244e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); 12456fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman RHS = InsertNewInstWith(ExtractElementInst::Create(RHS, 1246e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); 12478a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1248e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner switch (II->getIntrinsicID()) { 1249e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner default: llvm_unreachable("Case stmts out of sync!"); 1250e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_sub_ss: 1251e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_sub_sd: 12526fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman TmpV = InsertNewInstWith(BinaryOperator::CreateFSub(LHS, RHS, 1253e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner II->getName()), *II); 1254e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1255e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse_mul_ss: 1256e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner case Intrinsic::x86_sse2_mul_sd: 12576fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman TmpV = InsertNewInstWith(BinaryOperator::CreateFMul(LHS, RHS, 1258e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner II->getName()), *II); 1259e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1260e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 12618a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1262e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner Instruction *New = 1263e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner InsertElementInst::Create( 1264e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefValue::get(II->getType()), TmpV, 1265e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U, false), 1266e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner II->getName()); 12676fd5a6000bb6d23d6e41f6a8b8d07ad3cca3ea76Eli Friedman InsertNewInstWith(New, *II); 1268e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return New; 12698a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper } 1270e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 12718a8413d75cb1b6dbbb77a775052568548382cbb4Craig Topper 1272e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // Output elements are undefined if both are undefined. Consider things 1273e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner // like undef&0. The result is known zero, not undef. 1274e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner UndefElts &= UndefElts2; 1275e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1276e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1277e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner break; 1278e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1279e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner } 1280e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner return MadeChange ? I : 0; 1281e0b4b721aa82796c6ee5cf501ecd85f4974732eeChris Lattner} 1282