1173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner//===- ValueTracking.cpp - Walk computations to compute properties --------===// 2173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 3173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// The LLVM Compiler Infrastructure 4173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 5173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// This file is distributed under the University of Illinois Open Source 6173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// License. See LICENSE.TXT for details. 7173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 8173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner//===----------------------------------------------------------------------===// 9173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 10173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// This file contains routines that help analyze properties that chains of 11173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// computations have. 12173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 13173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner//===----------------------------------------------------------------------===// 14173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 15173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Analysis/ValueTracking.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 17243712720ad1da144d4376bdd854d81260c1beaaDan Gohman#include "llvm/Analysis/InstructionSimplify.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalAlias.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Metadata.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Operator.h" 277c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola#include "llvm/Support/ConstantRange.h" 28173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 29173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/MathExtras.h" 30d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands#include "llvm/Support/PatternMatch.h" 3132a9e7a2654c4aab2e617fbe53140492b3d38066Chris Lattner#include <cstring> 32173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerusing namespace llvm; 33d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sandsusing namespace llvm::PatternMatch; 34d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 35d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sandsconst unsigned MaxDepth = 6; 36d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 37d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// getBitWidth - Returns the bitwidth of the given scalar or pointer type (if 38d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// unknown returns 0). For vector types, returns the element type's bitwidth. 393574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowstatic unsigned getBitWidth(Type *Ty, const DataLayout *TD) { 40d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (unsigned BitWidth = Ty->getScalarSizeInBits()) 41d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return BitWidth; 42d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands assert(isa<PointerType>(Ty) && "Expected a pointer type!"); 43426c2bf5cdd2173e4a33aea8cb92cf684a724f4bChandler Carruth return TD ? TD->getPointerSizeInBits() : 0; 44d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands} 45173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 4600cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewyckystatic void ComputeMaskedBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW, 4700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky APInt &KnownZero, APInt &KnownOne, 4800cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky APInt &KnownZero2, APInt &KnownOne2, 493574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD, unsigned Depth) { 5000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (!Add) { 5100cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (ConstantInt *CLHS = dyn_cast<ConstantInt>(Op0)) { 5200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // We know that the top bits of C-X are clear if X contains less bits 5300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // than C (i.e. no wrap-around can happen). For example, 20-X is 5400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // positive if we can prove that X is >= 0 and < 16. 5500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (!CLHS->getValue().isNegative()) { 5626c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola unsigned BitWidth = KnownZero.getBitWidth(); 5700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros(); 5800cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // NLZ can't be BitWidth with no sign bit 5900cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 6026c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1); 61c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 6200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // If all of the MaskV bits are known to be zero, then we know the 6300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // output top bits are zero, because we now know that the output is 6400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // from [0-C]. 6500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if ((KnownZero2 & MaskV) == MaskV) { 6600cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky unsigned NLZ2 = CLHS->getValue().countLeadingZeros(); 6700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // Top bits known zero. 6826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2); 6900cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 7000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 7100cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 7200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 7300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky 7426c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola unsigned BitWidth = KnownZero.getBitWidth(); 7500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky 7600cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // If one of the operands has trailing zeros, then the bits that the 7700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // other operand has in those bit positions will be preserved in the 7800cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // result. For an add, this works with either operand. For a subtract, 7900cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // this only works if the known zeros are in the right operand. 8000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 8126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola llvm::ComputeMaskedBits(Op0, LHSKnownZero, LHSKnownOne, TD, Depth+1); 8200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky assert((LHSKnownZero & LHSKnownOne) == 0 && 8300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky "Bits known to be one AND zero?"); 8400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky unsigned LHSKnownZeroOut = LHSKnownZero.countTrailingOnes(); 8500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky 8626c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1); 87c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 8800cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky unsigned RHSKnownZeroOut = KnownZero2.countTrailingOnes(); 8900cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky 9000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // Determine which operand has more trailing zeros, and use that 9100cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // many bits from the other operand. 9200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (LHSKnownZeroOut > RHSKnownZeroOut) { 9300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (Add) { 9400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky APInt Mask = APInt::getLowBitsSet(BitWidth, LHSKnownZeroOut); 9500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky KnownZero |= KnownZero2 & Mask; 9600cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky KnownOne |= KnownOne2 & Mask; 9700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } else { 9800cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // If the known zeros are in the left operand for a subtract, 9900cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // fall back to the minimum known zeros in both operands. 10000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky KnownZero |= APInt::getLowBitsSet(BitWidth, 10100cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky std::min(LHSKnownZeroOut, 10200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky RHSKnownZeroOut)); 10300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 10400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } else if (RHSKnownZeroOut >= LHSKnownZeroOut) { 10500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky APInt Mask = APInt::getLowBitsSet(BitWidth, RHSKnownZeroOut); 10600cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky KnownZero |= LHSKnownZero & Mask; 10700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky KnownOne |= LHSKnownOne & Mask; 10800cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 10900cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky 11000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // Are we still trying to solve for the sign bit? 11126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola if (!KnownZero.isNegative() && !KnownOne.isNegative()) { 11200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (NSW) { 11300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (Add) { 11400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // Adding two positive numbers can't wrap into negative 11500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (LHSKnownZero.isNegative() && KnownZero2.isNegative()) 11600cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky KnownZero |= APInt::getSignBit(BitWidth); 11700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // and adding two negative numbers can't wrap into positive. 11800cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky else if (LHSKnownOne.isNegative() && KnownOne2.isNegative()) 11900cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky KnownOne |= APInt::getSignBit(BitWidth); 12000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } else { 12100cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // Subtracting a negative number from a positive one can't wrap 12200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (LHSKnownZero.isNegative() && KnownOne2.isNegative()) 12300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky KnownZero |= APInt::getSignBit(BitWidth); 12400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky // neither can subtracting a positive number from a negative one. 12500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky else if (LHSKnownOne.isNegative() && KnownZero2.isNegative()) 12600cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky KnownOne |= APInt::getSignBit(BitWidth); 12700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 12800cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 12900cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 13000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky} 13100cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky 132f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewyckystatic void ComputeMaskedBitsMul(Value *Op0, Value *Op1, bool NSW, 133f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky APInt &KnownZero, APInt &KnownOne, 134f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky APInt &KnownZero2, APInt &KnownOne2, 1353574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD, unsigned Depth) { 13626c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola unsigned BitWidth = KnownZero.getBitWidth(); 13726c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(Op1, KnownZero, KnownOne, TD, Depth+1); 13826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(Op0, KnownZero2, KnownOne2, TD, Depth+1); 139f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 140f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 141f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky 142f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky bool isKnownNegative = false; 143f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky bool isKnownNonNegative = false; 144f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // If the multiplication is known not to overflow, compute the sign bit. 14526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola if (NSW) { 146f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky if (Op0 == Op1) { 147f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // The product of a number with itself is non-negative. 148f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky isKnownNonNegative = true; 149f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky } else { 150f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky bool isKnownNonNegativeOp1 = KnownZero.isNegative(); 151f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky bool isKnownNonNegativeOp0 = KnownZero2.isNegative(); 152f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky bool isKnownNegativeOp1 = KnownOne.isNegative(); 153f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky bool isKnownNegativeOp0 = KnownOne2.isNegative(); 154f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // The product of two numbers with the same sign is non-negative. 155f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky isKnownNonNegative = (isKnownNegativeOp1 && isKnownNegativeOp0) || 156f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky (isKnownNonNegativeOp1 && isKnownNonNegativeOp0); 157f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // The product of a negative number and a non-negative number is either 158f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // negative or zero. 159f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky if (!isKnownNonNegative) 160f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky isKnownNegative = (isKnownNegativeOp1 && isKnownNonNegativeOp0 && 161f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky isKnownNonZero(Op0, TD, Depth)) || 162f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky (isKnownNegativeOp0 && isKnownNonNegativeOp1 && 163f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky isKnownNonZero(Op1, TD, Depth)); 164f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky } 165f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky } 166f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky 167f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // If low bits are zero in either operand, output low known-0 bits. 168f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // Also compute a conserative estimate for high known-0 bits. 169f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // More trickiness is possible, but this is sufficient for the 170f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // interesting case of alignment computation. 171f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky KnownOne.clearAllBits(); 172f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky unsigned TrailZ = KnownZero.countTrailingOnes() + 173f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky KnownZero2.countTrailingOnes(); 174f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 175f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky KnownZero2.countLeadingOnes(), 176f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky BitWidth) - BitWidth; 177f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky 178f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky TrailZ = std::min(TrailZ, BitWidth); 179f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky LeadZ = std::min(LeadZ, BitWidth); 180f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 181f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky APInt::getHighBitsSet(BitWidth, LeadZ); 182f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky 183f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // Only make use of no-wrap flags if we failed to compute the sign bit 184f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // directly. This matters if the multiplication always overflows, in 185f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // which case we prefer to follow the result of the direct computation, 186f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // though as the program is invoking undefined behaviour we can choose 187f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky // whatever we like here. 188f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky if (isKnownNonNegative && !KnownOne.isNegative()) 189f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky KnownZero.setBit(BitWidth - 1); 190f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky else if (isKnownNegative && !KnownZero.isNegative()) 191f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky KnownOne.setBit(BitWidth - 1); 192f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky} 193f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky 19426c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindolavoid llvm::computeMaskedBitsLoad(const MDNode &Ranges, APInt &KnownZero) { 19526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola unsigned BitWidth = KnownZero.getBitWidth(); 1967c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola unsigned NumRanges = Ranges.getNumOperands() / 2; 1977c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola assert(NumRanges >= 1); 1987c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola 1997c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola // Use the high end of the ranges to find leading zeros. 2007c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola unsigned MinLeadingZeros = BitWidth; 2017c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola for (unsigned i = 0; i < NumRanges; ++i) { 2027c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola ConstantInt *Lower = cast<ConstantInt>(Ranges.getOperand(2*i + 0)); 2037c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola ConstantInt *Upper = cast<ConstantInt>(Ranges.getOperand(2*i + 1)); 2047c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola ConstantRange Range(Lower->getValue(), Upper->getValue()); 2057c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola if (Range.isWrappedSet()) 2067c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola MinLeadingZeros = 0; // -1 has no zeros 2077c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola unsigned LeadingZeros = (Upper->getValue() - 1).countLeadingZeros(); 2087c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola MinLeadingZeros = std::min(LeadingZeros, MinLeadingZeros); 2097c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola } 2107c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola 21126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getHighBitsSet(BitWidth, MinLeadingZeros); 2127c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola} 21326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola/// ComputeMaskedBits - Determine which of the bits are known to be either zero 21426c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola/// or one and return them in the KnownZero/KnownOne bit sets. 21526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola/// 216173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that 217173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// we cannot optimize based on the assumption that it is zero without changing 218173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// it to be an explicit zero. If we don't change it to zero, other code could 219173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// optimized based on the contradictory assumption that it is non-zero. 220173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// Because instcombine aggressively folds operations with undef args anyway, 221173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this won't lose us code quality. 222cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// 223cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// This function is defined on values with integer type, values with pointer 224cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// type (but only if TD is non-null), and vectors of integers. In the case 22526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola/// where V is a vector, known zero, and known one values are the 226cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// same width as the vector element, and the bit is set only if it is true 227cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// for all of the elements in the vector. 22826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindolavoid llvm::ComputeMaskedBits(Value *V, APInt &KnownZero, APInt &KnownOne, 2293574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD, unsigned Depth) { 230173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert(V && "No Value?"); 2319004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman assert(Depth <= MaxDepth && "Limit Search Depth"); 23226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola unsigned BitWidth = KnownZero.getBitWidth(); 23326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola 2341608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem assert((V->getType()->isIntOrIntVectorTy() || 2351608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem V->getType()->getScalarType()->isPointerTy()) && 2361608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem "Not integer or pointer type!"); 2376de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman assert((!TD || 2386de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman TD->getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) && 239b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands (!V->getType()->isIntOrIntVectorTy() || 2406de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman V->getType()->getScalarSizeInBits() == BitWidth) && 2411608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem KnownZero.getBitWidth() == BitWidth && 242173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.getBitWidth() == BitWidth && 243173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner "V, Mask, KnownOne and KnownZero should have same BitWidth"); 244173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 245173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 246173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We know all of the bits for a constant! 24726c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownOne = CI->getValue(); 24826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = ~KnownOne; 249173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 250173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 2516de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // Null and aggregate-zero are all-zeros. 2526de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman if (isa<ConstantPointerNull>(V) || 2536de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman isa<ConstantAggregateZero>(V)) { 2547a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 25526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getAllOnesValue(BitWidth); 256173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 257173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 2586de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // Handle a constant vector by taking the intersection of the known bits of 2597302d80490feabfc8a01bee0fa698aab55169544Chris Lattner // each element. There is no real need to handle ConstantVector here, because 2607302d80490feabfc8a01bee0fa698aab55169544Chris Lattner // we don't handle undef in any particularly useful way. 261df39028607ca751f0a3f50a76144464b825ff97aChris Lattner if (ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) { 262df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // We know that CDS must be a vector of integers. Take the intersection of 263df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // each element. 264df39028607ca751f0a3f50a76144464b825ff97aChris Lattner KnownZero.setAllBits(); KnownOne.setAllBits(); 265df39028607ca751f0a3f50a76144464b825ff97aChris Lattner APInt Elt(KnownZero.getBitWidth(), 0); 2660f193b8a6846dab25323788638e760ae03b7cd87Chris Lattner for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) { 267df39028607ca751f0a3f50a76144464b825ff97aChris Lattner Elt = CDS->getElementAsInteger(i); 268df39028607ca751f0a3f50a76144464b825ff97aChris Lattner KnownZero &= ~Elt; 269c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper KnownOne &= Elt; 270df39028607ca751f0a3f50a76144464b825ff97aChris Lattner } 271df39028607ca751f0a3f50a76144464b825ff97aChris Lattner return; 272df39028607ca751f0a3f50a76144464b825ff97aChris Lattner } 273c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 274173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // The address of an aligned GlobalValue has trailing zeros. 275173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 276173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = GV->getAlignment(); 277891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky if (Align == 0 && TD) { 278c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman if (GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV)) { 279c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman Type *ObjectType = GVar->getType()->getElementType(); 280891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky if (ObjectType->isSized()) { 281891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky // If the object is defined in the current Module, we'll be giving 282891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky // it the preferred alignment. Otherwise, we have to assume that it 283891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky // may only have the minimum ABI alignment. 284891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky if (!GVar->isDeclaration() && !GVar->isWeakForLinker()) 285891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky Align = TD->getPreferredAlignment(GVar); 286891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky else 287891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky Align = TD->getABITypeAlignment(ObjectType); 288891495e67607e7f1403bb8223fad652b8c2c1e72Nick Lewycky } 289c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman } 290004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman } 291173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 29226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getLowBitsSet(BitWidth, 293c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer countTrailingZeros(Align)); 294173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 2957a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownZero.clearAllBits(); 2967a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 297173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 298173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 299307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has 300307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman // the bits of its aliasee. 301307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 302307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman if (GA->mayBeOverridden()) { 3037a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownZero.clearAllBits(); KnownOne.clearAllBits(); 304307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman } else { 30526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(GA->getAliasee(), KnownZero, KnownOne, TD, Depth+1); 306307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman } 307307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman return; 308307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman } 309c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 310b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner if (Argument *A = dyn_cast<Argument>(V)) { 311ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands unsigned Align = 0; 312ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands 313ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands if (A->hasByValAttr()) { 314ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands // Get alignment information off byval arguments if specified in the IR. 315ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands Align = A->getParamAlignment(); 316ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands } else if (TD && A->hasStructRetAttr()) { 317ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands // An sret parameter has at least the ABI alignment of the return type. 318ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands Type *EltTy = cast<PointerType>(A->getType())->getElementType(); 319ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands if (EltTy->isSized()) 320ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands Align = TD->getABITypeAlignment(EltTy); 321ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands } 322ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands 323ffcf6dffee69bd586ab8aa3e24ebbca1d5d279e7Duncan Sands if (Align) 324c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align)); 325b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner return; 326b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner } 327173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 328b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner // Start out not knowing anything. 329b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner KnownZero.clearAllBits(); KnownOne.clearAllBits(); 330173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 33126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola if (Depth == MaxDepth) 332173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Limit search depth. 333173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 334ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *I = dyn_cast<Operator>(V); 335173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!I) return; 336173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 337173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero2(KnownZero), KnownOne2(KnownOne); 338ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman switch (I->getOpcode()) { 339173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 3407c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola case Instruction::Load: 3417c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range)) 34226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola computeMaskedBitsLoad(*MD, KnownZero); 3437c7121edb9d3560cdc0b57f20212176c0697ec51Rafael Espindola return; 344173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: { 345173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If either the LHS or the RHS are Zero, the result is zero. 34626c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 34726c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 348c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 349c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 350c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 351173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 bits are only known if set in both the LHS & RHS. 352173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 353173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 are known to be clear if zero in either the LHS | RHS. 354173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= KnownZero2; 355173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 356173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 357173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: { 35826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 35926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 360c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 361c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 362c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 363173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are only known if clear in both the LHS & RHS. 364173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 365173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in either the LHS | RHS. 366173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= KnownOne2; 367173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 368173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 369173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: { 37026c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 37126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 372c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 373c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 374c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 375173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are known if clear or set in both the LHS & RHS. 376173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 377173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in only one of the LHS, RHS. 378173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 379173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = KnownZeroOut; 380173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 381173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 382173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Mul: { 383f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 384f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky ComputeMaskedBitsMul(I->getOperand(0), I->getOperand(1), NSW, 38526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero, KnownOne, KnownZero2, KnownOne2, TD, Depth); 386f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky break; 387173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 388173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UDiv: { 389173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // For the purposes of computing leading zeros we can conservatively 390173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // treat a udiv as a logical right shift by the power of 2 known to 391173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // be less than the denominator. 39226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 393173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LeadZ = KnownZero2.countLeadingOnes(); 394173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 3957a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne2.clearAllBits(); 3967a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownZero2.clearAllBits(); 39726c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1); 398173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 399173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RHSUnknownLeadingOnes != BitWidth) 400173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ = std::min(BitWidth, 401173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 402173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 40326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ); 404173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 405173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 406173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 40726c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(2), KnownZero, KnownOne, TD, Depth+1); 40826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, 409173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 410c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 411c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 412173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 413173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Only known if known in both the LHS and RHS. 414173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 415173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 416173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 417173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPTrunc: 418173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPExt: 419173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToUI: 420173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToSI: 421173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SIToFP: 422173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UIToFP: 423173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Can't work with floating point. 424173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PtrToInt: 425173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::IntToPtr: 426173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We can't handle these if we don't know the pointer size. 427173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 428173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FALL THROUGH and handle them the same as zext/trunc. 429173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::ZExt: 430173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: { 431db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *SrcTy = I->getOperand(0)->getType(); 43212145f0339648426af2a33ed50c11de7cfcdbdf8Nadav Rotem 433b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner unsigned SrcBitWidth; 434173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Note that we handle pointer operands here because of inttoptr/ptrtoint 435173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // which fall through here. 436521396ab378ba3578cdfdda7422ba8bd79ffee40Nadav Rotem if(TD) { 437521396ab378ba3578cdfdda7422ba8bd79ffee40Nadav Rotem SrcBitWidth = TD->getTypeSizeInBits(SrcTy->getScalarType()); 438521396ab378ba3578cdfdda7422ba8bd79ffee40Nadav Rotem } else { 439521396ab378ba3578cdfdda7422ba8bd79ffee40Nadav Rotem SrcBitWidth = SrcTy->getScalarSizeInBits(); 440521396ab378ba3578cdfdda7422ba8bd79ffee40Nadav Rotem if (!SrcBitWidth) return; 441521396ab378ba3578cdfdda7422ba8bd79ffee40Nadav Rotem } 44212145f0339648426af2a33ed50c11de7cfcdbdf8Nadav Rotem 44312145f0339648426af2a33ed50c11de7cfcdbdf8Nadav Rotem assert(SrcBitWidth && "SrcBitWidth can't be zero"); 44440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zextOrTrunc(SrcBitWidth); 44540f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zextOrTrunc(SrcBitWidth); 44626c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 44740f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zextOrTrunc(BitWidth); 44840f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zextOrTrunc(BitWidth); 449173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Any top bits are known to be zero. 450173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (BitWidth > SrcBitWidth) 451173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 452173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 453173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 454173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::BitCast: { 455db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *SrcTy = I->getOperand(0)->getType(); 4561df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if ((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) && 4570dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner // TODO: For now, not handling conversions like: 4580dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner // (bitcast i64 %x to <2 x i32>) 4591df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands !I->getType()->isVectorTy()) { 46026c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 461173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 462173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 463173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 464173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 465173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: { 466173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the bits in the result that are not present in the input. 467b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); 468c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 46940f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.trunc(SrcBitWidth); 47040f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.trunc(SrcBitWidth); 47126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 472c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 47340f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zext(BitWidth); 47440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zext(BitWidth); 475173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 476173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the sign bit of the input is known set or clear, then we know the 477173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // top bits of the result. 478173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[SrcBitWidth-1]) // Input sign bit known zero 479173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 480173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[SrcBitWidth-1]) // Input sign bit known set 481173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 482173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 483173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 484173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Shl: 48594c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 486173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 487173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 48826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 489c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 490173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero <<= ShiftAmt; 491173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne <<= ShiftAmt; 492173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 493173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 494173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 495173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 496173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::LShr: 49794c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 498173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 499173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 500173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 501c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 502173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Unsigned shift right. 50326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero,KnownOne, TD, Depth+1); 504c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 505173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 506173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 507173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // high bits known zero. 508173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 509173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 510173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 511173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 512173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::AShr: 51394c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // (ashr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 514173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 515173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 51643b40a4620c155c73ac71b48472ea2411d7c35daChris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 517c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 518173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Signed shift right. 51926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 520c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 521173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 522173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 523c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 524173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 525173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[BitWidth-ShiftAmt-1]) // New bits are known zero. 526173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= HighBits; 527173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[BitWidth-ShiftAmt-1]) // New bits are known one. 528173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= HighBits; 529173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 530173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 531173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 532173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: { 53300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 53400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky ComputeMaskedBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW, 53526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero, KnownOne, KnownZero2, KnownOne2, TD, 53626c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola Depth); 53700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky break; 538173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 539173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: { 54000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 54100cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky ComputeMaskedBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW, 54226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero, KnownOne, KnownZero2, KnownOne2, TD, 54326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola Depth); 54400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky break; 545173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 546173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SRem: 547173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 548cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands APInt RA = Rem->getValue().abs(); 549cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands if (RA.isPowerOf2()) { 550cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands APInt LowBits = RA - 1; 55126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 552173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 553cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // The low bits of the first operand are unchanged by the srem. 554cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownZero = KnownZero2 & LowBits; 555cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownOne = KnownOne2 & LowBits; 556cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands 557cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // If the first operand is non-negative or has all low bits zero, then 558cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // the upper bits are all zero. 559173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 560cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownZero |= ~LowBits; 561173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 562cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // If the first operand is negative and not all low bits are zero, then 563cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // the upper bits are all one. 564cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0)) 565cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownOne |= ~LowBits; 566cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands 567c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 568173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 569173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 570c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky 571c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // The sign bit is the LHS's sign bit, except when the result of the 572c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // remainder is zero. 57326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola if (KnownZero.isNonNegative()) { 574c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 57526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, TD, 576c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky Depth+1); 577c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // If it's known zero, our sign bit is also zero. 578c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky if (LHSKnownZero.isNegative()) 5795ff30e70f8dc4ddfdb3bd6925ccdf524130a7b95Duncan Sands KnownZero.setBit(BitWidth - 1); 580c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky } 581c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky 582173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 583173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::URem: { 584173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 585173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt RA = Rem->getValue(); 586173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RA.isPowerOf2()) { 587173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LowBits = (RA - 1); 58826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, 589173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 590ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 59126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero |= ~LowBits; 59226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownOne &= LowBits; 593173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 594173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 595173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 596173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 597173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Since the result is less than or equal to either operand, any leading 598173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits in either operand must also exist in the result. 59926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 60026c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1); 601173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 60279abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned Leaders = std::max(KnownZero.countLeadingOnes(), 603173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countLeadingOnes()); 6047a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 60526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getHighBitsSet(BitWidth, Leaders); 606173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 607173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 608173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 609a276c603b82a11b0bf0b59f0517a69e4b63adeabVictor Hernandez case Instruction::Alloca: { 6107b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AI = cast<AllocaInst>(V); 611173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = AI->getAlignment(); 612a276c603b82a11b0bf0b59f0517a69e4b63adeabVictor Hernandez if (Align == 0 && TD) 613a276c603b82a11b0bf0b59f0517a69e4b63adeabVictor Hernandez Align = TD->getABITypeAlignment(AI->getType()->getElementType()); 614c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 615173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 616c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align)); 617173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 618173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 619173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::GetElementPtr: { 620173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Analyze all of the subscripts of this getelementptr instruction 621173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // to determine if we can prove known low zero bits. 622173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0); 62326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, TD, 62426c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola Depth+1); 625173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TrailZ = LocalKnownZero.countTrailingOnes(); 626173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 627173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner gep_type_iterator GTI = gep_type_begin(I); 628173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) { 629173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *Index = I->getOperand(i); 630db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *STy = dyn_cast<StructType>(*GTI)) { 631173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle struct member offset arithmetic. 632173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 633173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const StructLayout *SL = TD->getStructLayout(STy); 634173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Idx = cast<ConstantInt>(Index)->getZExtValue(); 635173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t Offset = SL->getElementOffset(Idx); 636c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer TrailZ = std::min<unsigned>(TrailZ, 637c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer countTrailingZeros(Offset)); 638173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 639173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle array index arithmetic. 640db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *IndexedTy = GTI.getIndexedType(); 641173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!IndexedTy->isSized()) return; 6426de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits(); 643777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t TypeSize = TD ? TD->getTypeAllocSize(IndexedTy) : 1; 644173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0); 64526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(Index, LocalKnownZero, LocalKnownOne, TD, Depth+1); 646173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, 647c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer unsigned(countTrailingZeros(TypeSize) + 64879abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner LocalKnownZero.countTrailingOnes())); 649173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 650173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 651c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 65226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ); 653173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 654173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 655173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PHI: { 656173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner PHINode *P = cast<PHINode>(I); 657173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle the case of a simple two-predecessor recurrence PHI. 658173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // There's a lot more that could theoretically be done here, but 659173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // this is sufficient to catch some interesting cases. 660173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (P->getNumIncomingValues() == 2) { 661173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 0; i != 2; ++i) { 662173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *L = P->getIncomingValue(i); 663173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *R = P->getIncomingValue(!i); 664ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *LU = dyn_cast<Operator>(L); 665173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!LU) 666173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner continue; 667ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman unsigned Opcode = LU->getOpcode(); 668173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Check for operations that have the property that if 669173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // both their operands have low zero bits, the result 670173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // will have low zero bits. 671173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Opcode == Instruction::Add || 672173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Sub || 673173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::And || 674173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Or || 675173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Mul) { 676173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LL = LU->getOperand(0); 677173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LR = LU->getOperand(1); 678173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Find a recurrence. 679173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (LL == I) 680173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LR; 681173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (LR == I) 682173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LL; 683173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 684173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 685173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Ok, we have a PHI of the form L op= R. Check for low 686173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits. 68726c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(R, KnownZero2, KnownOne2, TD, Depth+1); 688c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene 689c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene // We need to take the minimum number of known bits 690c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene APInt KnownZero3(KnownZero), KnownOne3(KnownOne); 69126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(L, KnownZero3, KnownOne3, TD, Depth+1); 692c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene 69326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getLowBitsSet(BitWidth, 694c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene std::min(KnownZero2.countTrailingOnes(), 695c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene KnownZero3.countTrailingOnes())); 696173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 697173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 698173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 699173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 7009004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman 7013b739d278c87f8ac22b5dc368b319fa278347b2fNick Lewycky // Unreachable blocks may have zero-operand PHI nodes. 7023b739d278c87f8ac22b5dc368b319fa278347b2fNick Lewycky if (P->getNumIncomingValues() == 0) 7033b739d278c87f8ac22b5dc368b319fa278347b2fNick Lewycky return; 7043b739d278c87f8ac22b5dc368b319fa278347b2fNick Lewycky 7059004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Otherwise take the unions of the known bit sets of the operands, 7069004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // taking conservative care to avoid excessive recursion. 7079004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) { 708606199fb85d1c8407615e575b5e8bb5c71be27bdDuncan Sands // Skip if every incoming value references to ourself. 7090fd518beb38568e58eeec86876bb597bab06b722Nuno Lopes if (dyn_cast_or_null<UndefValue>(P->hasConstantValue())) 710606199fb85d1c8407615e575b5e8bb5c71be27bdDuncan Sands break; 711606199fb85d1c8407615e575b5e8bb5c71be27bdDuncan Sands 71226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getAllOnesValue(BitWidth); 71326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownOne = APInt::getAllOnesValue(BitWidth); 7149004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { 7159004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Skip direct self references. 7169004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (P->getIncomingValue(i) == P) continue; 7179004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman 7189004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero2 = APInt(BitWidth, 0); 7199004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne2 = APInt(BitWidth, 0); 7209004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Recurse, but cap the recursion to one level, because we don't 7219004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // want to waste time spinning around in loops. 72226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(P->getIncomingValue(i), KnownZero2, KnownOne2, TD, 72326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola MaxDepth-1); 7249004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero &= KnownZero2; 7259004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne &= KnownOne2; 7269004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // If all bits have been ruled out, there's no need to check 7279004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // more operands. 7289004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (!KnownZero && !KnownOne) 7299004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman break; 7309004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman } 7319004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman } 732173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 733173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 734173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Call: 735173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 736173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner switch (II->getIntrinsicID()) { 737173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 738173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::ctlz: 739173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::cttz: { 740173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LowBits = Log2_32(BitWidth)+1; 741009da05e750b7bac7e1902fcdc85394de4ea63b3Benjamin Kramer // If this call is undefined for 0, the result will be less than 2^n. 742009da05e750b7bac7e1902fcdc85394de4ea63b3Benjamin Kramer if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext())) 743009da05e750b7bac7e1902fcdc85394de4ea63b3Benjamin Kramer LowBits -= 1; 74426c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 745009da05e750b7bac7e1902fcdc85394de4ea63b3Benjamin Kramer break; 746009da05e750b7bac7e1902fcdc85394de4ea63b3Benjamin Kramer } 747009da05e750b7bac7e1902fcdc85394de4ea63b3Benjamin Kramer case Intrinsic::ctpop: { 748009da05e750b7bac7e1902fcdc85394de4ea63b3Benjamin Kramer unsigned LowBits = Log2_32(BitWidth)+1; 74926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 750173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 751173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 75262660310d9e5f9ecf329fd3cacb67c344a12ddbcChad Rosier case Intrinsic::x86_sse42_crc32_64_8: 75362660310d9e5f9ecf329fd3cacb67c344a12ddbcChad Rosier case Intrinsic::x86_sse42_crc32_64_64: 75426c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownZero = APInt::getHighBitsSet(64, 32); 755cb559c1270a773de2c97c99700dcd5456f24a732Evan Cheng break; 756173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 757173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 758173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 75900cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky case Instruction::ExtractValue: 76000cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) { 76100cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky ExtractValueInst *EVI = cast<ExtractValueInst>(I); 76200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (EVI->getNumIndices() != 1) break; 76300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky if (EVI->getIndices()[0] == 0) { 76400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky switch (II->getIntrinsicID()) { 76500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky default: break; 76600cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky case Intrinsic::uadd_with_overflow: 76700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky case Intrinsic::sadd_with_overflow: 76800cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky ComputeMaskedBitsAddSub(true, II->getArgOperand(0), 76926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola II->getArgOperand(1), false, KnownZero, 77026c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownOne, KnownZero2, KnownOne2, TD, Depth); 77100cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky break; 77200cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky case Intrinsic::usub_with_overflow: 77300cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky case Intrinsic::ssub_with_overflow: 77400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky ComputeMaskedBitsAddSub(false, II->getArgOperand(0), 77526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola II->getArgOperand(1), false, KnownZero, 77626c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola KnownOne, KnownZero2, KnownOne2, TD, Depth); 77700cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky break; 778f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky case Intrinsic::umul_with_overflow: 779f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky case Intrinsic::smul_with_overflow: 780f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky ComputeMaskedBitsMul(II->getArgOperand(0), II->getArgOperand(1), 78126c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola false, KnownZero, KnownOne, 782f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky KnownZero2, KnownOne2, TD, Depth); 783f201a066625e32884c9d2b766ff48fe0b70e179aNick Lewycky break; 78400cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 78500cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 78600cbccceb395899c127f2ce0ed485441fc307fa3Nick Lewycky } 787173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 788173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 789173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 790d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// ComputeSignBit - Determine whether the sign bit is known to be zero or 791d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// one. Convenience wrapper around ComputeMaskedBits. 792d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sandsvoid llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, 7933574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD, unsigned Depth) { 794d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands unsigned BitWidth = getBitWidth(V->getType(), TD); 795d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (!BitWidth) { 796d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands KnownZero = false; 797d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands KnownOne = false; 798d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return; 799d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 800d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt ZeroBits(BitWidth, 0); 801d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt OneBits(BitWidth, 0); 80226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, ZeroBits, OneBits, TD, Depth); 803d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands KnownOne = OneBits[BitWidth - 1]; 804d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands KnownZero = ZeroBits[BitWidth - 1]; 805d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands} 806d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 807dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola/// isKnownToBeAPowerOfTwo - Return true if the given value is known to have exactly one 808d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// bit set when defined. For vectors return true if every element is known to 809d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// be a power of two when defined. Supports values with integer or pointer 810d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// types and vectors of integers. 811dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindolabool llvm::isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth) { 812dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (Constant *C = dyn_cast<Constant>(V)) { 813dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (C->isNullValue()) 814dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return OrZero; 815dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 816dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return CI->getValue().isPowerOf2(); 817dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands // TODO: Handle vector constants. 818dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands } 819d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 820d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // 1 << X is clearly a power of two if the one is not shifted off the end. If 821d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // it is shifted off the end then the result is undefined. 822d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (match(V, m_Shl(m_One(), m_Value()))) 823d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 824d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 825d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // (signbit) >>l X is clearly a power of two if the one is not shifted off the 826d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // bottom. If it is shifted off the bottom then the result is undefined. 82793c780288df9631d11f996b010b2212a8b44d4d3Duncan Sands if (match(V, m_LShr(m_SignBit(), m_Value()))) 828d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 829d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 830d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The remaining tests are all recursive, so bail out if we hit the limit. 831d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (Depth++ == MaxDepth) 832d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 833d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 8344604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands Value *X = 0, *Y = 0; 8354604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands // A shift of a power of two is a power of two or zero. 8364604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) || 8374604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands match(V, m_Shr(m_Value(X), m_Value())))) 838dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola return isKnownToBeAPowerOfTwo(X, /*OrZero*/true, Depth); 8394604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands 840d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (ZExtInst *ZI = dyn_cast<ZExtInst>(V)) 841dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola return isKnownToBeAPowerOfTwo(ZI->getOperand(0), OrZero, Depth); 842d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 843d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (SelectInst *SI = dyn_cast<SelectInst>(V)) 844dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola return isKnownToBeAPowerOfTwo(SI->getTrueValue(), OrZero, Depth) && 845dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola isKnownToBeAPowerOfTwo(SI->getFalseValue(), OrZero, Depth); 846dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands 847dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) { 848dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands // A power of two and'd with anything is a power of two or zero. 849dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola if (isKnownToBeAPowerOfTwo(X, /*OrZero*/true, Depth) || 850dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola isKnownToBeAPowerOfTwo(Y, /*OrZero*/true, Depth)) 851dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return true; 852dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands // X & (-X) is always a power of two or zero. 853dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X)))) 854dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return true; 855dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return false; 856dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands } 857d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 85836850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer // Adding a power-of-two or zero to the same power-of-two or zero yields 85936850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer // either the original power-of-two, a larger power-of-two or zero. 86036850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer if (match(V, m_Add(m_Value(X), m_Value(Y)))) { 86136850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer OverflowingBinaryOperator *VOBO = cast<OverflowingBinaryOperator>(V); 86236850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer if (OrZero || VOBO->hasNoUnsignedWrap() || VOBO->hasNoSignedWrap()) { 86336850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer if (match(X, m_And(m_Specific(Y), m_Value())) || 86436850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer match(X, m_And(m_Value(), m_Specific(Y)))) 86536850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer if (isKnownToBeAPowerOfTwo(Y, OrZero, Depth)) 86636850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer return true; 86736850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer if (match(Y, m_And(m_Specific(X), m_Value())) || 86836850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer match(Y, m_And(m_Value(), m_Specific(X)))) 86936850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer if (isKnownToBeAPowerOfTwo(X, OrZero, Depth)) 87036850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer return true; 87136850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer 87236850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer unsigned BitWidth = V->getType()->getScalarSizeInBits(); 87336850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer APInt LHSZeroBits(BitWidth, 0), LHSOneBits(BitWidth, 0); 87436850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer ComputeMaskedBits(X, LHSZeroBits, LHSOneBits, 0, Depth); 87536850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer 87636850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer APInt RHSZeroBits(BitWidth, 0), RHSOneBits(BitWidth, 0); 87736850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer ComputeMaskedBits(Y, RHSZeroBits, RHSOneBits, 0, Depth); 87836850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer // If i8 V is a power of two or zero: 87936850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer // ZeroBits: 1 1 1 0 1 1 1 1 88036850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer // ~ZeroBits: 0 0 0 1 0 0 0 0 88136850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer if ((~(LHSZeroBits & RHSZeroBits)).isPowerOf2()) 88236850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer // If OrZero isn't set, we cannot give back a zero result. 88336850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer // Make sure either the LHS or RHS has a bit set. 88436850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer if (OrZero || RHSOneBits.getBoolValue() || LHSOneBits.getBoolValue()) 88536850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer return true; 88636850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer } 88736850ad779cb77930ab9e03bc1bde4ad47dc9dceDavid Majnemer } 888cb9d4667b7159944598c178dbb6568bc20ae069bDavid Majnemer 8893dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky // An exact divide or right shift can only shift off zero bits, so the result 8901f7bc701b030f5b01553f306cc975eeac1e4d99bNick Lewycky // is a power of two only if the first operand is a power of two and not 8911f7bc701b030f5b01553f306cc975eeac1e4d99bNick Lewycky // copying a sign bit (sdiv int_min, 2). 89255c6d57734cd2f141dc2d6912fc22746d5eeae54Benjamin Kramer if (match(V, m_Exact(m_LShr(m_Value(), m_Value()))) || 89355c6d57734cd2f141dc2d6912fc22746d5eeae54Benjamin Kramer match(V, m_Exact(m_UDiv(m_Value(), m_Value())))) { 894dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola return isKnownToBeAPowerOfTwo(cast<Operator>(V)->getOperand(0), OrZero, Depth); 8953dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky } 8963dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky 897d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 898d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands} 899d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 90070d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth/// \brief Test whether a GEP's result is known to be non-null. 90170d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth/// 90270d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth/// Uses properties inherent in a GEP to try to determine whether it is known 90370d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth/// to be non-null. 90470d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth/// 90570d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth/// Currently this routine does not support vector GEPs. 90670d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruthstatic bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout *DL, 90770d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth unsigned Depth) { 90870d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (!GEP->isInBounds() || GEP->getPointerAddressSpace() != 0) 90970d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth return false; 91070d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 91170d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // FIXME: Support vector-GEPs. 91270d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth assert(GEP->getType()->isPointerTy() && "We only support plain pointer GEP"); 91370d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 91470d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // If the base pointer is non-null, we cannot walk to a null address with an 91570d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // inbounds GEP in address space zero. 91670d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (isKnownNonZero(GEP->getPointerOperand(), DL, Depth)) 91770d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth return true; 91870d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 91970d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // Past this, if we don't have DataLayout, we can't do much. 92070d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (!DL) 92170d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth return false; 92270d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 92370d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // Walk the GEP operands and see if any operand introduces a non-zero offset. 92470d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // If so, then the GEP cannot produce a null pointer, as doing so would 92570d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // inherently violate the inbounds contract within address space zero. 92670d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP); 92770d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth GTI != GTE; ++GTI) { 92870d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // Struct types are easy -- they must always be indexed by a constant. 92970d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (StructType *STy = dyn_cast<StructType>(*GTI)) { 93070d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand()); 93170d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth unsigned ElementIdx = OpC->getZExtValue(); 93270d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth const StructLayout *SL = DL->getStructLayout(STy); 93370d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth uint64_t ElementOffset = SL->getElementOffset(ElementIdx); 93470d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (ElementOffset > 0) 93570d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth return true; 93670d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth continue; 93770d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth } 93870d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 93970d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // If we have a zero-sized type, the index doesn't matter. Keep looping. 94070d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (DL->getTypeAllocSize(GTI.getIndexedType()) == 0) 94170d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth continue; 94270d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 94370d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // Fast path the constant operand case both for efficiency and so we don't 94470d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // increment Depth when just zipping down an all-constant GEP. 94570d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand())) { 94670d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (!OpC->isZero()) 94770d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth return true; 94870d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth continue; 94970d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth } 95070d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 95170d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // We post-increment Depth here because while isKnownNonZero increments it 95270d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // as well, when we pop back up that increment won't persist. We don't want 95370d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // to recurse 10k times just because we have 10k GEP operands. We don't 95470d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // bail completely out because we want to handle constant GEPs regardless 95570d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // of depth. 95670d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (Depth++ >= MaxDepth) 95770d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth continue; 95870d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 95970d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (isKnownNonZero(GTI.getOperand(), DL, Depth)) 96070d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth return true; 96170d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth } 96270d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 96370d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth return false; 96470d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth} 96570d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 966d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// isKnownNonZero - Return true if the given value is known to be non-zero 967d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// when defined. For vectors return true if every element is known to be 968d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// non-zero when defined. Supports values with integer or pointer type and 969d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// vectors of integers. 9703574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowbool llvm::isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth) { 971d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (Constant *C = dyn_cast<Constant>(V)) { 972d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (C->isNullValue()) 973d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 974d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (isa<ConstantInt>(C)) 975d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // Must be non-zero due to null test above. 976d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 977d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // TODO: Handle vectors 978d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 979d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 980d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 981d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The remaining tests are all recursive, so bail out if we hit the limit. 98232a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands if (Depth++ >= MaxDepth) 983d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 984d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 98570d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth // Check for pointer simplifications. 98670d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (V->getType()->isPointerTy()) { 98790842427b2f6ab5c0aab6049fd9177033101847fManman Ren if (isKnownNonNull(V)) 98890842427b2f6ab5c0aab6049fd9177033101847fManman Ren return true; 98970d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) 99070d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth if (isGEPKnownNonNull(GEP, TD, Depth)) 99170d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth return true; 99270d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth } 99370d3bebc8bc857fcf3d7fac44bda884d5e2a7040Chandler Carruth 994fd360c3e242e6317b241107a1db2b7d4a6276476Nadav Rotem unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), TD); 995d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 996d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // X | Y != 0 if X != 0 or Y != 0. 997d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands Value *X = 0, *Y = 0; 998d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (match(V, m_Or(m_Value(X), m_Value(Y)))) 999d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return isKnownNonZero(X, TD, Depth) || isKnownNonZero(Y, TD, Depth); 1000d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 1001d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // ext X != 0 if X != 0. 1002d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (isa<SExtInst>(V) || isa<ZExtInst>(V)) 1003d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return isKnownNonZero(cast<Instruction>(V)->getOperand(0), TD, Depth); 1004d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 10059136782d273cd45b6f19a7d0cc0d146d0791bac9Duncan Sands // shl X, Y != 0 if X is odd. Note that the value of the shift is undefined 1006d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // if the lowest bit is shifted off the end. 1007d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (BitWidth && match(V, m_Shl(m_Value(X), m_Value(Y)))) { 10083dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky // shl nuw can't remove any non-zero bits. 100932a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); 10103dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky if (BO->hasNoUnsignedWrap()) 10113dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky return isKnownNonZero(X, TD, Depth); 10123dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky 1013d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownZero(BitWidth, 0); 1014d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownOne(BitWidth, 0); 101526c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(X, KnownZero, KnownOne, TD, Depth); 1016d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (KnownOne[0]) 1017d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 1018d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 10199136782d273cd45b6f19a7d0cc0d146d0791bac9Duncan Sands // shr X, Y != 0 if X is negative. Note that the value of the shift is not 1020d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // defined if the sign bit is shifted off the end. 1021d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) { 10223dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky // shr exact can only shift out zero bits. 102332a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V); 10243dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky if (BO->isExact()) 10253dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky return isKnownNonZero(X, TD, Depth); 10263dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky 1027d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands bool XKnownNonNegative, XKnownNegative; 1028d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); 1029d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (XKnownNegative) 1030d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 1031d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 10323dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky // div exact can only produce a zero if the dividend is zero. 103355c6d57734cd2f141dc2d6912fc22746d5eeae54Benjamin Kramer else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) { 103455c6d57734cd2f141dc2d6912fc22746d5eeae54Benjamin Kramer return isKnownNonZero(X, TD, Depth); 10353dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky } 1036d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // X + Y. 1037d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands else if (match(V, m_Add(m_Value(X), m_Value(Y)))) { 1038d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands bool XKnownNonNegative, XKnownNegative; 1039d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands bool YKnownNonNegative, YKnownNegative; 1040d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); 1041d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, TD, Depth); 1042d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 1043d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // If X and Y are both non-negative (as signed values) then their sum is not 1044227fba11ca168225d913d1cea94a05b883092e76Duncan Sands // zero unless both X and Y are zero. 1045d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (XKnownNonNegative && YKnownNonNegative) 1046227fba11ca168225d913d1cea94a05b883092e76Duncan Sands if (isKnownNonZero(X, TD, Depth) || isKnownNonZero(Y, TD, Depth)) 1047227fba11ca168225d913d1cea94a05b883092e76Duncan Sands return true; 1048d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 1049d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // If X and Y are both negative (as signed values) then their sum is not 1050d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // zero unless both X and Y equal INT_MIN. 1051d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (BitWidth && XKnownNegative && YKnownNegative) { 1052d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownZero(BitWidth, 0); 1053d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownOne(BitWidth, 0); 1054d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt Mask = APInt::getSignedMaxValue(BitWidth); 1055d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The sign bit of X is set. If some other bit is set then X is not equal 1056d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // to INT_MIN. 105726c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(X, KnownZero, KnownOne, TD, Depth); 1058d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if ((KnownOne & Mask) != 0) 1059d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 1060d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The sign bit of Y is set. If some other bit is set then Y is not equal 1061d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // to INT_MIN. 106226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(Y, KnownZero, KnownOne, TD, Depth); 1063d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if ((KnownOne & Mask) != 0) 1064d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 1065d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 1066d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 1067d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The sum of a non-negative number and a power of two is not zero. 1068dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola if (XKnownNonNegative && isKnownToBeAPowerOfTwo(Y, /*OrZero*/false, Depth)) 1069d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 1070dbaa2376f7b3c027e895ff4bee3ae08351f3ea88Rafael Espindola if (YKnownNonNegative && isKnownToBeAPowerOfTwo(X, /*OrZero*/false, Depth)) 1071d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 1072d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 107332a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // X * Y. 107432a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) { 107532a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); 107632a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // If X and Y are non-zero then so is X * Y as long as the multiplication 107732a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // does not overflow. 107832a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) && 107932a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands isKnownNonZero(X, TD, Depth) && isKnownNonZero(Y, TD, Depth)) 108032a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands return true; 108132a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands } 1082d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // (C ? X : Y) != 0 if X != 0 and Y != 0. 1083d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands else if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 1084d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (isKnownNonZero(SI->getTrueValue(), TD, Depth) && 1085d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands isKnownNonZero(SI->getFalseValue(), TD, Depth)) 1086d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 1087d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 1088d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 1089d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (!BitWidth) return false; 1090d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownZero(BitWidth, 0); 1091d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownOne(BitWidth, 0); 109226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1093d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return KnownOne != 0; 1094d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands} 1095d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 1096173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 1097173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this predicate to simplify operations downstream. Mask is known to be zero 1098173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// for bits that V cannot have. 1099cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// 1100cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// This function is defined on values with integer type, values with pointer 1101cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// type (but only if TD is non-null), and vectors of integers. In the case 1102cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// where V is a vector, the mask, known zero, and known one values are the 1103cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// same width as the vector element, and the bit is set only if it is true 1104cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// for all of the elements in the vector. 1105173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerbool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, 11063574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD, unsigned Depth) { 1107173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0); 110826c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1109c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1110173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return (KnownZero & Mask) == Mask; 1111173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 1112173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1113173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1114173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1115173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// ComputeNumSignBits - Return the number of times the sign bit of the 1116173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// register is replicated into the other bits. We know that at least 1 bit 1117173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// is always equal to the sign bit (itself), but other cases can give us 1118173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// information. For example, immediately after an "ashr X, 2", we know that 1119173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// the top 3 bits are all equal to each other, so we return 3. 1120173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 1121173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 'Op' must have a scalar integer type. 1122173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 11233574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowunsigned llvm::ComputeNumSignBits(Value *V, const DataLayout *TD, 1124846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman unsigned Depth) { 1125b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands assert((TD || V->getType()->isIntOrIntVectorTy()) && 11263574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow "ComputeNumSignBits requires a DataLayout object to operate " 1127bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman "on non-integer values!"); 1128db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = V->getType(); 1129bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman unsigned TyBits = TD ? TD->getTypeSizeInBits(V->getType()->getScalarType()) : 1130bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman Ty->getScalarSizeInBits(); 1131173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Tmp, Tmp2; 1132173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned FirstAnswer = 1; 1133173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1134d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // Note that ConstantInt is handled by the general ComputeMaskedBits case 1135d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // below. 1136d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner 1137173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Depth == 6) 1138173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return 1; // Limit search depth. 1139c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1140ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *U = dyn_cast<Operator>(V); 1141ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman switch (Operator::getOpcode(V)) { 1142173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 1143173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: 114469a008075b29fbe0644ccbeecf1418ef8cca5e24Mon P Wang Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits(); 1145173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return ComputeNumSignBits(U->getOperand(0), TD, Depth+1) + Tmp; 1146c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 11476b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner case Instruction::AShr: { 1148173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 11496b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner // ashr X, C -> adds C sign bits. Vectors too. 11506b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner const APInt *ShAmt; 11516b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner if (match(U->getOperand(1), m_APInt(ShAmt))) { 11526b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner Tmp += ShAmt->getZExtValue(); 1153173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp > TyBits) Tmp = TyBits; 1154173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1155173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 11566b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner } 11576b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner case Instruction::Shl: { 11586b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner const APInt *ShAmt; 11596b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner if (match(U->getOperand(1), m_APInt(ShAmt))) { 1160173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shl destroys sign bits. 1161173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 11626b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner Tmp2 = ShAmt->getZExtValue(); 11636b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner if (Tmp2 >= TyBits || // Bad shift. 11646b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner Tmp2 >= Tmp) break; // Shifted all sign bits out. 11656b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner return Tmp - Tmp2; 1166173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1167173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 11686b0dc92043ab1f63d78b8796098575e1d777b701Chris Lattner } 1169173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: 1170173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: 1171173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: // NOT is handled here. 1172173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Logical binary ops preserve the number of sign bits at the worst. 1173173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1174173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp != 1) { 1175173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1176173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner FirstAnswer = std::min(Tmp, Tmp2); 1177173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We computed what we know about the sign bits as our first 1178173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // answer. Now proceed to the generic code that uses 1179173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // ComputeMaskedBits, and pick whichever answer is better. 1180173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1181173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 1182173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1183173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 1184173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1185173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 1186173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(2), TD, Depth+1); 1187173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::min(Tmp, Tmp2); 1188c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1189173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: 1190173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Add can have at most one carry bit. Thus we know that the output 1191173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 1192173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1193173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 1194c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1195173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Special case decrementing a value (ADD X, -1): 11960001e56f15215ae4bc5fffb82eec5c4828b888f0Dan Gohman if (ConstantInt *CRHS = dyn_cast<ConstantInt>(U->getOperand(1))) 1197173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CRHS->isAllOnesValue()) { 1198173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 119926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(U->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 1200c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1201173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 1202173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 120326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue()) 1204173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 1205c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1206173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If we are subtracting one from a positive number, there is no carry 1207173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // out of the result. 1208173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 1209173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 1210173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1211c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1212173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1213173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 12148d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner return std::min(Tmp, Tmp2)-1; 1215c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1216173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: 1217173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1218173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 1219c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1220173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle NEG. 1221173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CLHS = dyn_cast<ConstantInt>(U->getOperand(0))) 1222173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CLHS->isNullValue()) { 1223173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 122426c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(U->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 1225173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 1226173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 122726c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue()) 1228173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 1229c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1230173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be positive (the sign bit is known clear), 1231173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the output of the NEG has the same number of sign bits as the input. 1232173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 1233173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp2; 1234c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1235173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Otherwise, we treat this like a SUB. 1236173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1237c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1238173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Sub can have at most one carry bit. Thus we know that the output 1239173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 1240173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1241173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 12428d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner return std::min(Tmp, Tmp2)-1; 1243c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 12448d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner case Instruction::PHI: { 12458d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner PHINode *PN = cast<PHINode>(U); 12468d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner // Don't analyze large in-degree PHIs. 12478d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner if (PN->getNumIncomingValues() > 4) break; 1248c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 12498d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner // Take the minimum of all incoming values. This can't infinitely loop 12508d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner // because of our depth threshold. 12518d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner Tmp = ComputeNumSignBits(PN->getIncomingValue(0), TD, Depth+1); 12528d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 12538d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner if (Tmp == 1) return Tmp; 12548d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner Tmp = std::min(Tmp, 12550af20d847ac89f797d613a8a4fc3e7127ccb0b36Evan Cheng ComputeNumSignBits(PN->getIncomingValue(i), TD, Depth+1)); 12568d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner } 12578d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner return Tmp; 12588d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner } 12598d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner 1260173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: 1261173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FIXME: it's tricky to do anything useful for this, but it is an important 1262173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // case for targets like X86. 1263173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 1264173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1265c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1266173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Finally, if we can prove that the top bits of the result are 0's or 1's, 1267173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // use this information. 1268173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 126926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola APInt Mask; 127026c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1271c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1272173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) { // sign bit is 0 1273173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownZero; 1274173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else if (KnownOne.isNegative()) { // sign bit is 1; 1275173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownOne; 1276173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 1277173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Nothing known. 1278173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return FirstAnswer; 1279173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1280c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1281173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 1282173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the number of identical bits in the top of the input value. 1283173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = ~Mask; 1284173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask <<= Mask.getBitWidth()-TyBits; 1285173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Return # leading zeros. We use 'min' here in case Val was zero before 1286173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shifting. We don't want to return '64' as for an i32 "0". 1287173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros())); 1288173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 1289833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 12902b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez/// ComputeMultiple - This function computes the integer multiple of Base that 12912b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez/// equals V. If successful, it returns true and returns the multiple in 12923dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman/// Multiple. If unsuccessful, it returns false. It looks 12932b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez/// through SExt instructions only if LookThroughSExt is true. 12942b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandezbool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, 12953dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman bool LookThroughSExt, unsigned Depth) { 12962b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez const unsigned MaxDepth = 6; 12972b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 12983dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman assert(V && "No Value?"); 12992b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez assert(Depth <= MaxDepth && "Limit Search Depth"); 1300b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands assert(V->getType()->isIntegerTy() && "Not integer or pointer type!"); 13012b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 1302db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *T = V->getType(); 13032b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 13043dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman ConstantInt *CI = dyn_cast<ConstantInt>(V); 13052b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 13062b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Base == 0) 13072b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return false; 1308c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 13092b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Base == 1) { 13102b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = V; 13112b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 13122b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 13132b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 13142b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez ConstantExpr *CO = dyn_cast<ConstantExpr>(V); 13152b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Constant *BaseVal = ConstantInt::get(T, Base); 13162b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (CO && CO == BaseVal) { 13172b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // Multiple is 1. 13182b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = ConstantInt::get(T, 1); 13192b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 13202b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 13212b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 13222b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (CI && CI->getZExtValue() % Base == 0) { 13232b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = ConstantInt::get(T, CI->getZExtValue() / Base); 1324c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper return true; 13252b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 1326c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 13272b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Depth == MaxDepth) return false; // Limit search depth. 1328c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 13292b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Operator *I = dyn_cast<Operator>(V); 13302b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (!I) return false; 13312b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 13322b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez switch (I->getOpcode()) { 13332b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez default: break; 133411fe72661dac17efa1564ef6fc212acae4f0c07eChris Lattner case Instruction::SExt: 13352b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (!LookThroughSExt) return false; 13362b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // otherwise fall through to ZExt 133711fe72661dac17efa1564ef6fc212acae4f0c07eChris Lattner case Instruction::ZExt: 13383dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman return ComputeMultiple(I->getOperand(0), Base, Multiple, 13393dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman LookThroughSExt, Depth+1); 13402b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez case Instruction::Shl: 13412b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez case Instruction::Mul: { 13422b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Op0 = I->getOperand(0); 13432b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Op1 = I->getOperand(1); 13442b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 13452b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (I->getOpcode() == Instruction::Shl) { 13462b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1); 13472b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (!Op1CI) return false; 13482b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // Turn Op0 << Op1 into Op0 * 2^Op1 13492b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez APInt Op1Int = Op1CI->getValue(); 13502b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1); 1351a99793c5ea24dd3839f4925b89b1f6acfcb24604Jay Foad APInt API(Op1Int.getBitWidth(), 0); 13527a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad API.setBit(BitToSet); 1353a99793c5ea24dd3839f4925b89b1f6acfcb24604Jay Foad Op1 = ConstantInt::get(V->getContext(), API); 13542b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 13552b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 13562b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Mul0 = NULL; 1357e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (ComputeMultiple(Op0, Base, Mul0, LookThroughSExt, Depth+1)) { 1358e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Constant *Op1C = dyn_cast<Constant>(Op1)) 1359e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Constant *MulC = dyn_cast<Constant>(Mul0)) { 1360c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper if (Op1C->getType()->getPrimitiveSizeInBits() < 1361e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC->getType()->getPrimitiveSizeInBits()) 1362e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Op1C = ConstantExpr::getZExt(Op1C, MulC->getType()); 1363c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper if (Op1C->getType()->getPrimitiveSizeInBits() > 1364e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC->getType()->getPrimitiveSizeInBits()) 1365e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC = ConstantExpr::getZExt(MulC, Op1C->getType()); 1366c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1367e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner // V == Base * (Mul0 * Op1), so return (Mul0 * Op1) 1368e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Multiple = ConstantExpr::getMul(MulC, Op1C); 1369e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner return true; 1370e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner } 13712b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 13722b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (ConstantInt *Mul0CI = dyn_cast<ConstantInt>(Mul0)) 13732b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Mul0CI->getValue() == 1) { 13742b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // V == Base * Op1, so return Op1 13752b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = Op1; 13762b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 13772b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 13782b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 13792b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 1380e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Value *Mul1 = NULL; 1381e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (ComputeMultiple(Op1, Base, Mul1, LookThroughSExt, Depth+1)) { 1382e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Constant *Op0C = dyn_cast<Constant>(Op0)) 1383e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Constant *MulC = dyn_cast<Constant>(Mul1)) { 1384c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper if (Op0C->getType()->getPrimitiveSizeInBits() < 1385e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC->getType()->getPrimitiveSizeInBits()) 1386e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Op0C = ConstantExpr::getZExt(Op0C, MulC->getType()); 1387c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper if (Op0C->getType()->getPrimitiveSizeInBits() > 1388e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC->getType()->getPrimitiveSizeInBits()) 1389e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC = ConstantExpr::getZExt(MulC, Op0C->getType()); 1390c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1391e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner // V == Base * (Mul1 * Op0), so return (Mul1 * Op0) 1392e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Multiple = ConstantExpr::getMul(MulC, Op0C); 1393e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner return true; 1394e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner } 13952b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 13962b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (ConstantInt *Mul1CI = dyn_cast<ConstantInt>(Mul1)) 13972b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Mul1CI->getValue() == 1) { 13982b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // V == Base * Op0, so return Op0 13992b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = Op0; 14002b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 14012b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 14022b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 14032b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 14042b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 14052b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 14062b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // We could not determine if V is a multiple of Base. 14072b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return false; 14082b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez} 14092b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 1410c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper/// CannotBeNegativeZero - Return true if we can prove that the specified FP 1411833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// value is never equal to -0.0. 1412833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 1413833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// NOTE: this function will need to be revisited when we support non-default 1414833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// rounding modes! 1415833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 1416833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattnerbool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { 1417833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) 1418833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return !CFP->getValueAPF().isNegZero(); 1419c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1420833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (Depth == 6) 1421833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return 1; // Limit search depth. 1422833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1423ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman const Operator *I = dyn_cast<Operator>(V); 1424833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (I == 0) return false; 142585893f48a6994d71414773175440c421e5341810Michael Ilseman 142685893f48a6994d71414773175440c421e5341810Michael Ilseman // Check if the nsz fast-math flag is set 142785893f48a6994d71414773175440c421e5341810Michael Ilseman if (const FPMathOperator *FPO = dyn_cast<FPMathOperator>(I)) 142885893f48a6994d71414773175440c421e5341810Michael Ilseman if (FPO->hasNoSignedZeros()) 142985893f48a6994d71414773175440c421e5341810Michael Ilseman return true; 143085893f48a6994d71414773175440c421e5341810Michael Ilseman 1431833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // (add x, 0.0) is guaranteed to return +0.0, not -0.0. 1432603e874c64c2328cf29395e328bf77c1851068d2Jakub Staszak if (I->getOpcode() == Instruction::FAdd) 1433603e874c64c2328cf29395e328bf77c1851068d2Jakub Staszak if (ConstantFP *CFP = dyn_cast<ConstantFP>(I->getOperand(1))) 1434603e874c64c2328cf29395e328bf77c1851068d2Jakub Staszak if (CFP->isNullValue()) 1435603e874c64c2328cf29395e328bf77c1851068d2Jakub Staszak return true; 1436c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1437833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sitofp and uitofp turn into +0.0 for zero. 1438833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I)) 1439833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return true; 1440c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1441833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 1442833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sqrt(-0.0) = -0.0, no other negative results are possible. 1443833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (II->getIntrinsicID() == Intrinsic::sqrt) 144471339c965ca6268b9bff91213364783c3d06f666Gabor Greif return CannotBeNegativeZero(II->getArgOperand(0), Depth+1); 1445c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1446833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const CallInst *CI = dyn_cast<CallInst>(I)) 1447833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const Function *F = CI->getCalledFunction()) { 1448833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (F->isDeclaration()) { 1449f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar // abs(x) != -0.0 1450f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar if (F->getName() == "abs") return true; 14519d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen // fabs[lf](x) != -0.0 14529d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "fabs") return true; 14539d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "fabsf") return true; 14549d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "fabsl") return true; 14559d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "sqrt" || F->getName() == "sqrtf" || 14569d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen F->getName() == "sqrtl") 145771339c965ca6268b9bff91213364783c3d06f666Gabor Greif return CannotBeNegativeZero(CI->getArgOperand(0), Depth+1); 1458833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 1459833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 1460c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1461833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return false; 1462833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner} 1463833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1464bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// isBytewiseValue - If the specified value can be set by repeating the same 1465bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// byte in memory, return the i8 value that it is represented with. This is 1466bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// true for all i8 values obviously, but is also true for i32 0, i32 -1, 1467bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// i16 0xF0F0, double 0.0 etc. If the value can't be handled with a repeated 1468bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// byte store (e.g. i16 0x1234), return null. 1469bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris LattnerValue *llvm::isBytewiseValue(Value *V) { 1470bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // All byte-wide stores are splatable, even of arbitrary variables. 1471bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (V->getType()->isIntegerTy(8)) return V; 147241bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner 147341bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner // Handle 'null' ConstantArrayZero etc. 147441bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner if (Constant *C = dyn_cast<Constant>(V)) 147541bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner if (C->isNullValue()) 147641bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner return Constant::getNullValue(Type::getInt8Ty(V->getContext())); 1477c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1478bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // Constant float and double values can be handled as integer values if the 1479c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper // corresponding integer value is "byteable". An important case is 0.0. 1480bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) { 1481bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (CFP->getType()->isFloatTy()) 1482bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner V = ConstantExpr::getBitCast(CFP, Type::getInt32Ty(V->getContext())); 1483bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (CFP->getType()->isDoubleTy()) 1484bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner V = ConstantExpr::getBitCast(CFP, Type::getInt64Ty(V->getContext())); 1485bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // Don't handle long double formats, which have strange constraints. 1486bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1487c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1488c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper // We can handle constant integers that are power of two in size and a 1489bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // multiple of 8 bits. 1490bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 1491bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner unsigned Width = CI->getBitWidth(); 1492bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (isPowerOf2_32(Width) && Width > 8) { 1493bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // We can handle this value if the recursive binary decomposition is the 1494bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // same at all levels. 1495bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner APInt Val = CI->getValue(); 1496bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner APInt Val2; 1497bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner while (Val.getBitWidth() != 8) { 1498bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner unsigned NextWidth = Val.getBitWidth()/2; 1499bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner Val2 = Val.lshr(NextWidth); 1500bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner Val2 = Val2.trunc(Val.getBitWidth()/2); 1501bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner Val = Val.trunc(Val.getBitWidth()/2); 1502c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1503bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // If the top/bottom halves aren't the same, reject it. 1504bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (Val != Val2) 1505bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return 0; 1506bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1507bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return ConstantInt::get(V->getContext(), Val); 1508bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1509bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1510c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 151118c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // A ConstantDataArray/Vector is splatable if all its members are equal and 151218c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // also splatable. 151318c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(V)) { 151418c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner Value *Elt = CA->getElementAsConstant(0); 151518c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner Value *Val = isBytewiseValue(Elt); 1516bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (!Val) 1517bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return 0; 1518c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 151918c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner for (unsigned I = 1, E = CA->getNumElements(); I != E; ++I) 152018c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner if (CA->getElementAsConstant(I) != Elt) 1521bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return 0; 1522c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1523bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return Val; 1524bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1525dce42b75dc05befb4f43b664951c80752904bcdeChad Rosier 1526bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // Conceptually, we could handle things like: 1527bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // %a = zext i8 %X to i16 1528bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // %b = shl i16 %a, 8 1529bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // %c = or i16 %a, %b 1530bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // but until there is an example that actually needs this, it doesn't seem 1531bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // worth worrying about. 1532bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return 0; 1533bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner} 1534bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1535bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1536b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This is the recursive version of BuildSubAggregate. It takes a few different 1537b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// arguments. Idxs is the index within the nested struct From that we are 1538b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// looking at now (which is of type IndexedType). IdxSkip is the number of 1539b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// indices from Idxs that should be left out when inserting into the resulting 1540b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct. To is the result struct built so far, new insertvalue instructions 1541b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// build on that. 1542db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerstatic Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType, 15439e639e8fd95488cb4c8ef2f7f3a41919acb29ac4Craig Topper SmallVectorImpl<unsigned> &Idxs, 15447db949df789383acce98ef072f08794fdd5bd04eDan Gohman unsigned IdxSkip, 15457db949df789383acce98ef072f08794fdd5bd04eDan Gohman Instruction *InsertBefore) { 154696f498bd9f140a98321c478f517877c4767b94faDmitri Gribenko llvm::StructType *STy = dyn_cast<llvm::StructType>(IndexedType); 1547b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (STy) { 15480a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Save the original To argument so we can modify it 15490a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Value *OrigTo = To; 1550b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // General case, the type indexed by Idxs is a struct 1551b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1552b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Process each struct element recursively 1553b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.push_back(i); 15540a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Value *PrevTo = To; 1555710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip, 1556ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1557b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.pop_back(); 15580a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (!To) { 15590a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Couldn't find any inserted value for this index? Cleanup 15600a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman while (PrevTo != OrigTo) { 15610a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman InsertValueInst* Del = cast<InsertValueInst>(PrevTo); 15620a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman PrevTo = Del->getAggregateOperand(); 15630a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Del->eraseFromParent(); 15640a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman } 15650a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Stop processing elements 15660a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman break; 15670a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman } 1568b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 15697a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // If we successfully found a value for each of our subaggregates 15700a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (To) 15710a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return To; 1572b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 15730a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Base case, the type indexed by SourceIdxs is not a struct, or not all of 15740a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // the struct's elements had a value that was inserted directly. In the latter 15750a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // case, perhaps we can't determine each of the subelements individually, but 15760a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // we might be able to find the complete struct somewhere. 1577c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 15780a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Find the value that is at that particular spot 1579fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad Value *V = FindInsertedValue(From, Idxs); 15800a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 15810a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (!V) 15820a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return NULL; 15830a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 15840a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Insert the value in the new (sub) aggregrate 158539b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel return llvm::InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip), 1586fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad "tmp", InsertBefore); 1587b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 1588b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1589b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This helper takes a nested struct and extracts a part of it (which is again a 1590b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct) into a new value. For example, given the struct: 1591b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { a, { b, { c, d }, e } } 1592b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// and the indices "1, 1" this returns 1593b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { c, d }. 1594b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 15950a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// It does this by inserting an insertvalue for each element in the resulting 15960a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// struct, as opposed to just inserting a single struct. This will only work if 15970a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// each of the elements of the substruct are known (ie, inserted into From by an 15980a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// insertvalue instruction somewhere). 1599b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 16000a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// All inserted insertvalue instructions are inserted before InsertBefore 1601fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foadstatic Value *BuildSubAggregate(Value *From, ArrayRef<unsigned> idx_range, 16027db949df789383acce98ef072f08794fdd5bd04eDan Gohman Instruction *InsertBefore) { 1603977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman assert(InsertBefore && "Must have someplace to insert!"); 1604db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), 1605fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad idx_range); 16069e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Value *To = UndefValue::get(IndexedType); 1607fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end()); 1608b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned IdxSkip = Idxs.size(); 1609b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1610ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); 1611b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 1612b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1613710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// FindInsertedValue - Given an aggregrate and an sequence of indices, see if 1614710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// the scalar value indexed is already around as a register, for example if it 1615710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// were inserted directly into the aggregrate. 16160a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// 16170a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// If InsertBefore is not null, this function will duplicate (modified) 16180a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// insertvalues when a part of a nested struct is extracted. 1619fc6d3a49867cd38954dc40936a88f1907252c6d2Jay FoadValue *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, 1620fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad Instruction *InsertBefore) { 1621b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Nothing to index? Just return V then (this is useful at the end of our 1622df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // recursion). 1623fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad if (idx_range.empty()) 1624b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return V; 1625df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // We have indices, so V should have an indexable type. 1626df39028607ca751f0a3f50a76144464b825ff97aChris Lattner assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) && 1627df39028607ca751f0a3f50a76144464b825ff97aChris Lattner "Not looking at a struct or array?"); 1628df39028607ca751f0a3f50a76144464b825ff97aChris Lattner assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) && 1629df39028607ca751f0a3f50a76144464b825ff97aChris Lattner "Invalid indices for type?"); 1630a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner 1631a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (Constant *C = dyn_cast<Constant>(V)) { 1632a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner C = C->getAggregateElement(idx_range[0]); 1633a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner if (C == 0) return 0; 1634a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner return FindInsertedValue(C, idx_range.slice(1), InsertBefore); 1635a1f00f4d488eb5daff52faaf99c62ee652fd3b85Chris Lattner } 1636c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1637df39028607ca751f0a3f50a76144464b825ff97aChris Lattner if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) { 1638b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Loop the indices for the insertvalue instruction in parallel with the 1639b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested indices 1640fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad const unsigned *req_idx = idx_range.begin(); 1641710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 1642710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman i != e; ++i, ++req_idx) { 1643fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad if (req_idx == idx_range.end()) { 1644df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // We can't handle this without inserting insertvalues 1645df39028607ca751f0a3f50a76144464b825ff97aChris Lattner if (!InsertBefore) 1646977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman return 0; 1647df39028607ca751f0a3f50a76144464b825ff97aChris Lattner 1648df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // The requested index identifies a part of a nested aggregate. Handle 1649df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // this specially. For example, 1650df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // %A = insertvalue { i32, {i32, i32 } } undef, i32 10, 1, 0 1651df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // %B = insertvalue { i32, {i32, i32 } } %A, i32 11, 1, 1 1652df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // %C = extractvalue {i32, { i32, i32 } } %B, 1 1653df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // This can be changed into 1654df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // %A = insertvalue {i32, i32 } undef, i32 10, 0 1655df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // %C = insertvalue {i32, i32 } %A, i32 11, 1 1656df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // which allows the unused 0,0 element from the nested struct to be 1657df39028607ca751f0a3f50a76144464b825ff97aChris Lattner // removed. 1658df39028607ca751f0a3f50a76144464b825ff97aChris Lattner return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx), 1659df39028607ca751f0a3f50a76144464b825ff97aChris Lattner InsertBefore); 16609954c76f2c89ab3c70bfe8222534621a86f9085aDuncan Sands } 1661c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1662b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // This insert value inserts something else than what we are looking for. 1663b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // See if the (aggregrate) value inserted into has the value we are 1664b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // looking for, then. 1665b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (*req_idx != *i) 1666fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad return FindInsertedValue(I->getAggregateOperand(), idx_range, 1667ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1668b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 1669b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we end up here, the indices of the insertvalue match with those 1670b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested (though possibly only partially). Now we recursively look at 1671b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // the inserted value, passing any remaining indices. 1672fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad return FindInsertedValue(I->getInsertedValueOperand(), 167339b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel makeArrayRef(req_idx, idx_range.end()), 1674ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1675df39028607ca751f0a3f50a76144464b825ff97aChris Lattner } 1676c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1677df39028607ca751f0a3f50a76144464b825ff97aChris Lattner if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) { 1678b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we're extracting a value from an aggregrate that was extracted from 1679b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // something else, we can extract from that something else directly instead. 1680b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // However, we will need to chain I's indices with the requested indices. 1681c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1682c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper // Calculate the number of indices required 1683fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad unsigned size = I->getNumIndices() + idx_range.size(); 1684b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Allocate some space to put the new indices in 16853faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman SmallVector<unsigned, 5> Idxs; 16863faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman Idxs.reserve(size); 1687b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add indices from the extract value instruction 1688fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad Idxs.append(I->idx_begin(), I->idx_end()); 1689c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1690b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add requested indices 1691fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad Idxs.append(idx_range.begin(), idx_range.end()); 1692b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1693c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper assert(Idxs.size() == size 1694710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman && "Number of indices added not correct?"); 1695c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 1696fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad return FindInsertedValue(I->getAggregateOperand(), Idxs, InsertBefore); 1697b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 1698b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Otherwise, we don't know (such as, extracting from a function return value 1699b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // or load instruction) 1700b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return 0; 1701b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 17020ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 1703ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner/// GetPointerBaseWithConstantOffset - Analyze the specified pointer to see if 1704ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner/// it can be expressed as a base pointer plus a constant offset. Return the 1705ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner/// base and offset to the caller. 1706ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris LattnerValue *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, 1707a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman const DataLayout *TD) { 1708a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // Without DataLayout, conservatively assume 64-bit offsets, which is 1709a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // the widest we support. 1710a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman unsigned BitWidth = TD ? TD->getPointerSizeInBits() : 64; 17115cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes APInt ByteOffset(BitWidth, 0); 17125cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes while (1) { 17135cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes if (Ptr->getType()->isVectorTy()) 17145cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes break; 17155cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes 17165cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes if (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) { 17175cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes APInt GEPOffset(BitWidth, 0); 1718a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman if (TD && !GEP->accumulateConstantOffset(*TD, GEPOffset)) 17195cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes break; 17205cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes ByteOffset += GEPOffset; 17215cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes Ptr = GEP->getPointerOperand(); 17225cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes } else if (Operator::getOpcode(Ptr) == Instruction::BitCast) { 17235cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes Ptr = cast<Operator>(Ptr)->getOperand(0); 17245cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) { 17255cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes if (GA->mayBeOverridden()) 17265cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes break; 17275cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes Ptr = GA->getAliasee(); 1728ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner } else { 17295cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes break; 1730ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner } 1731ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner } 17325cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes Offset = ByteOffset.getSExtValue(); 17335cec34754d540faac87fc0173fce42005c76b7d9Nuno Lopes return Ptr; 1734ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner} 1735ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 1736ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 173718c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner/// getConstantStringInfo - This function computes the length of a 17380ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// null-terminated C string pointed to by V. If successful, it returns true 17390ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// and returns the string in Str. If unsuccessful, it returns false. 174018c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattnerbool llvm::getConstantStringInfo(const Value *V, StringRef &Str, 174118c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner uint64_t Offset, bool TrimAtNul) { 174218c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner assert(V); 174318c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner 174418c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // Look through bitcast instructions and geps. 174518c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner V = V->stripPointerCasts(); 1746c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 174718c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // If the value is a GEP instructionor constant expression, treat it as an 174818c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // offset. 174918c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 17500ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Make sure the GEP has exactly three arguments. 17510582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (GEP->getNumOperands() != 3) 17520582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 1753c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 17540ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Make sure the index-ee is a pointer to array of i8. 1755db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner PointerType *PT = cast<PointerType>(GEP->getOperand(0)->getType()); 1756db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType()); 1757b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (AT == 0 || !AT->getElementType()->isIntegerTy(8)) 17580582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 1759c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 17600ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Check to make sure that the first operand of the GEP is an integer and 17610ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // has value 0 so that we are sure we're indexing into the initializer. 17620a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1)); 17630582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (FirstIdx == 0 || !FirstIdx->isZero()) 17640582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 1765c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 17660ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // If the second index isn't a ConstantInt, then this is a variable index 17670ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // into the array. If this occurs, we can't say anything meaningful about 17680ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // the string. 17690ff39b3feb10477c224138156941234f5fa46f58Evan Cheng uint64_t StartIdx = 0; 17700a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 17710ff39b3feb10477c224138156941234f5fa46f58Evan Cheng StartIdx = CI->getZExtValue(); 17720582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling else 17730582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 177418c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner return getConstantStringInfo(GEP->getOperand(0), Str, StartIdx+Offset); 17750ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 17760cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky 17770ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // The GEP instruction, constant or instruction, must reference a global 17780ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // variable that is a constant and is initialized. The referenced constant 17790ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // initializer is the array that we'll use for optimization. 178018c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner const GlobalVariable *GV = dyn_cast<GlobalVariable>(V); 17818255573835970e7130ba93271972172fb335f2ecDan Gohman if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) 17820582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 178318c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner 17840cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky // Handle the all-zeros case 178518c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner if (GV->getInitializer()->isNullValue()) { 17860ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // This is a degenerate case. The initializer is constant zero so the 17870ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // length of the string must be zero. 178818c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner Str = ""; 17890582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; 17900582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling } 1791c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 17920ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Must be a Constant Array 179318c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner const ConstantDataArray *Array = 179418c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner dyn_cast<ConstantDataArray>(GV->getInitializer()); 179518c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner if (Array == 0 || !Array->isString()) 17960582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 1797c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 17980ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Get the number of elements in the array 179918c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner uint64_t NumElts = Array->getType()->getArrayNumElements(); 180018c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner 180118c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // Start out with the entire array in the StringRef. 180218c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner Str = Array->getAsString(); 180318c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner 18040582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (Offset > NumElts) 18050582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 1806c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 180718c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // Skip over 'offset' bytes. 180818c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner Str = Str.substr(Offset); 1809c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 181018c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner if (TrimAtNul) { 181118c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // Trim off the \0 and anything after it. If the array is not nul 181218c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // terminated, we just return the whole end of string. The client may know 181318c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // some other way that the string is length-bound. 181418c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner Str = Str.substr(0, Str.find('\0')); 181518c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner } 18160582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; 18170ff39b3feb10477c224138156941234f5fa46f58Evan Cheng} 181825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 181925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher// These next two are very similar to the above, but also look through PHI 182025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher// nodes. 182125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher// TODO: See if we can integrate these two together. 182225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 182325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// GetStringLengthH - If we can compute the length of the string pointed to by 182425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// the specified pointer, return 'len+1'. If we can't, return 0. 182525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopherstatic uint64_t GetStringLengthH(Value *V, SmallPtrSet<PHINode*, 32> &PHIs) { 182625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Look through noop bitcast instructions. 182718c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner V = V->stripPointerCasts(); 182825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 182925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If this is a PHI node, there are two cases: either we have already seen it 183025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // or we haven't. 183125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (PHINode *PN = dyn_cast<PHINode>(V)) { 183225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!PHIs.insert(PN)) 183325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return ~0ULL; // already in the set. 183425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 183525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If it was new, see if all the input strings are the same length. 183625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t LenSoFar = ~0ULL; 183725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 183825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len = GetStringLengthH(PN->getIncomingValue(i), PHIs); 183925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len == 0) return 0; // Unknown length -> unknown. 184025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 184125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len == ~0ULL) continue; 184225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 184325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len != LenSoFar && LenSoFar != ~0ULL) 184425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; // Disagree -> unknown. 184525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher LenSoFar = Len; 184625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 184725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 184825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Success, all agree. 184925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return LenSoFar; 185025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 185125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 185225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y) 185325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 185425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs); 185525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len1 == 0) return 0; 185625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs); 185725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len2 == 0) return 0; 185825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len1 == ~0ULL) return Len2; 185925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len2 == ~0ULL) return Len1; 186025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len1 != Len2) return 0; 186125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return Len1; 186225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 1863c4265e1d68a88791a004224aac7af9e914a0d411Craig Topper 186418c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner // Otherwise, see if we can read the string. 186518c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner StringRef StrData; 186618c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner if (!getConstantStringInfo(V, StrData)) 186791766fe066efe6e0969ba805a2e3726a70ed34a3Argyrios Kyrtzidis return 0; 186825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 186918c7f80b3e83ab584bd8572695a3cde8bafd9d3cChris Lattner return StrData.size()+1; 187025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher} 187125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 187225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// GetStringLength - If we can compute the length of the string pointed to by 187325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// the specified pointer, return 'len+1'. If we can't, return 0. 187425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopheruint64_t llvm::GetStringLength(Value *V) { 187525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!V->getType()->isPointerTy()) return 0; 187625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 187725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher SmallPtrSet<PHINode*, 32> PHIs; 187825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len = GetStringLengthH(V, PHIs); 187925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return 188025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // an empty string as a length. 188125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return Len == ~0ULL ? 1 : Len; 188225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher} 18835034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman 1884bd1801b5553c8be3960255a92738464e0010b6f6Dan GohmanValue * 18853574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowllvm::GetUnderlyingObject(Value *V, const DataLayout *TD, unsigned MaxLookup) { 18865034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman if (!V->getType()->isPointerTy()) 18875034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman return V; 18885034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) { 18895034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 18905034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman V = GEP->getPointerOperand(); 18915034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } else if (Operator::getOpcode(V) == Instruction::BitCast) { 18925034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman V = cast<Operator>(V)->getOperand(0); 18935034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 18945034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman if (GA->mayBeOverridden()) 18955034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman return V; 18965034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman V = GA->getAliasee(); 18975034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } else { 1898c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman // See if InstructionSimplify knows any relevant tricks. 1899c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman if (Instruction *I = dyn_cast<Instruction>(V)) 19007a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // TODO: Acquire a DominatorTree and use it. 1901bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman if (Value *Simplified = SimplifyInstruction(I, TD, 0)) { 1902c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman V = Simplified; 1903c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman continue; 1904c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman } 1905c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman 19065034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman return V; 19075034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } 19085034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 19095034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } 19105034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman return V; 19115034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman} 191299e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky 1913b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohmanvoid 1914b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohmanllvm::GetUnderlyingObjects(Value *V, 1915b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman SmallVectorImpl<Value *> &Objects, 19163574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD, 1917b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman unsigned MaxLookup) { 1918b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman SmallPtrSet<Value *, 4> Visited; 1919b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman SmallVector<Value *, 4> Worklist; 1920b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman Worklist.push_back(V); 1921b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman do { 1922b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman Value *P = Worklist.pop_back_val(); 1923b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman P = GetUnderlyingObject(P, TD, MaxLookup); 1924b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman 1925b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (!Visited.insert(P)) 1926b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman continue; 1927b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman 1928b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (SelectInst *SI = dyn_cast<SelectInst>(P)) { 1929b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman Worklist.push_back(SI->getTrueValue()); 1930b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman Worklist.push_back(SI->getFalseValue()); 1931b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman continue; 1932b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman } 1933b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman 1934b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (PHINode *PN = dyn_cast<PHINode>(P)) { 1935b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1936b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman Worklist.push_back(PN->getIncomingValue(i)); 1937b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman continue; 1938b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman } 1939b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman 1940b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman Objects.push_back(P); 1941b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman } while (!Worklist.empty()); 1942b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman} 1943b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman 194499e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky/// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer 194599e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky/// are lifetime markers. 194699e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky/// 194799e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewyckybool llvm::onlyUsedByLifetimeMarkers(const Value *V) { 194899e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 194999e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky UI != UE; ++UI) { 195099e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky const IntrinsicInst *II = dyn_cast<IntrinsicInst>(*UI); 195199e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky if (!II) return false; 195299e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky 195399e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky if (II->getIntrinsicID() != Intrinsic::lifetime_start && 195499e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky II->getIntrinsicID() != Intrinsic::lifetime_end) 195599e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky return false; 195699e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky } 195799e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky return true; 195899e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky} 1959f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman 1960febaf8401779fedf8db7b02e499c5e39848fb9f5Dan Gohmanbool llvm::isSafeToSpeculativelyExecute(const Value *V, 19613574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD) { 1962febaf8401779fedf8db7b02e499c5e39848fb9f5Dan Gohman const Operator *Inst = dyn_cast<Operator>(V); 1963febaf8401779fedf8db7b02e499c5e39848fb9f5Dan Gohman if (!Inst) 1964febaf8401779fedf8db7b02e499c5e39848fb9f5Dan Gohman return false; 1965febaf8401779fedf8db7b02e499c5e39848fb9f5Dan Gohman 1966f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) 1967f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i))) 1968f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman if (C->canTrap()) 1969f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return false; 1970f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman 1971f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman switch (Inst->getOpcode()) { 1972f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman default: 1973f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return true; 1974f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::UDiv: 1975f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::URem: 1976f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman // x / y is undefined if y == 0, but calcuations like x / 3 are safe. 1977f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return isKnownNonZero(Inst->getOperand(1), TD); 1978f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::SDiv: 1979f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::SRem: { 1980f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman Value *Op = Inst->getOperand(1); 1981f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman // x / y is undefined if y == 0 1982f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman if (!isKnownNonZero(Op, TD)) 1983f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return false; 1984f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman // x / y might be undefined if y == -1 1985f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman unsigned BitWidth = getBitWidth(Op->getType(), TD); 1986f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman if (BitWidth == 0) 1987f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return false; 1988f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman APInt KnownZero(BitWidth, 0); 1989f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman APInt KnownOne(BitWidth, 0); 199026c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(Op, KnownZero, KnownOne, TD); 1991f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return !!KnownZero; 1992f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman } 1993f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Load: { 1994f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman const LoadInst *LI = cast<LoadInst>(Inst); 1995f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman if (!LI->isUnordered()) 1996f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return false; 1997f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return LI->getPointerOperand()->isDereferenceablePointer(); 1998f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman } 19998369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Instruction::Call: { 20008369687576b062be74c941a4a90dbabb0828e028Nick Lewycky if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 20018369687576b062be74c941a4a90dbabb0828e028Nick Lewycky switch (II->getIntrinsicID()) { 2002c0d18b669674d3b173e6a3eca6ada98871bb808fChandler Carruth // These synthetic intrinsics have no side-effects, and just mark 2003c0d18b669674d3b173e6a3eca6ada98871bb808fChandler Carruth // information about their operands. 2004c0d18b669674d3b173e6a3eca6ada98871bb808fChandler Carruth // FIXME: There are other no-op synthetic instructions that potentially 2005c0d18b669674d3b173e6a3eca6ada98871bb808fChandler Carruth // should be considered at least *safe* to speculate... 2006c0d18b669674d3b173e6a3eca6ada98871bb808fChandler Carruth case Intrinsic::dbg_declare: 2007c0d18b669674d3b173e6a3eca6ada98871bb808fChandler Carruth case Intrinsic::dbg_value: 2008c0d18b669674d3b173e6a3eca6ada98871bb808fChandler Carruth return true; 2009c0d18b669674d3b173e6a3eca6ada98871bb808fChandler Carruth 20108369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::bswap: 20118369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::ctlz: 20128369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::ctpop: 20138369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::cttz: 20148369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::objectsize: 20158369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::sadd_with_overflow: 20168369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::smul_with_overflow: 20178369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::ssub_with_overflow: 20188369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::uadd_with_overflow: 20198369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::umul_with_overflow: 20208369687576b062be74c941a4a90dbabb0828e028Nick Lewycky case Intrinsic::usub_with_overflow: 20218369687576b062be74c941a4a90dbabb0828e028Nick Lewycky return true; 20228369687576b062be74c941a4a90dbabb0828e028Nick Lewycky // TODO: some fp intrinsics are marked as having the same error handling 20238369687576b062be74c941a4a90dbabb0828e028Nick Lewycky // as libm. They're safe to speculate when they won't error. 20248369687576b062be74c941a4a90dbabb0828e028Nick Lewycky // TODO: are convert_{from,to}_fp16 safe? 20258369687576b062be74c941a4a90dbabb0828e028Nick Lewycky // TODO: can we list target-specific intrinsics here? 20268369687576b062be74c941a4a90dbabb0828e028Nick Lewycky default: break; 20278369687576b062be74c941a4a90dbabb0828e028Nick Lewycky } 20288369687576b062be74c941a4a90dbabb0828e028Nick Lewycky } 2029f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return false; // The called function could have undefined behavior or 20308369687576b062be74c941a4a90dbabb0828e028Nick Lewycky // side-effects, even if marked readnone nounwind. 20318369687576b062be74c941a4a90dbabb0828e028Nick Lewycky } 2032f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::VAArg: 2033f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Alloca: 2034f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Invoke: 2035f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::PHI: 2036f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Store: 2037f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Ret: 2038f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Br: 2039f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::IndirectBr: 2040f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Switch: 2041f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Unreachable: 2042f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Fence: 2043f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::LandingPad: 2044f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::AtomicRMW: 2045f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::AtomicCmpXchg: 2046f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman case Instruction::Resume: 2047f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman return false; // Misc instructions which have effects 2048f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman } 2049f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman} 2050de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman 2051de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman/// isKnownNonNull - Return true if we know that the specified value is never 2052de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman/// null. 2053de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohmanbool llvm::isKnownNonNull(const Value *V) { 2054de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman // Alloca never returns null, malloc might. 2055de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman if (isa<AllocaInst>(V)) return true; 2056de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman 2057de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman // A byval argument is never null. 2058de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman if (const Argument *A = dyn_cast<Argument>(V)) 2059de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman return A->hasByValAttr(); 2060de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman 2061de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman // Global values are not null unless extern weak. 2062de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 2063de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman return !GV->hasExternalWeakLinkage(); 2064de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman return false; 2065de0eb19248f3053c07a5b1dad9c47b8435458337Dan Gohman} 2066