ValueTracking.cpp revision dce42b75dc05befb4f43b664951c80752904bcde
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" 16243712720ad1da144d4376bdd854d81260c1beaaDan Gohman#include "llvm/Analysis/InstructionSimplify.h" 17173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Constants.h" 18173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Instructions.h" 190ff39b3feb10477c224138156941234f5fa46f58Evan Cheng#include "llvm/GlobalVariable.h" 20307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman#include "llvm/GlobalAlias.h" 21173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/IntrinsicInst.h" 2276f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson#include "llvm/LLVMContext.h" 23ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman#include "llvm/Operator.h" 240582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling#include "llvm/Target/TargetData.h" 25173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 26173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/MathExtras.h" 27d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands#include "llvm/Support/PatternMatch.h" 2825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher#include "llvm/ADT/SmallPtrSet.h" 2932a9e7a2654c4aab2e617fbe53140492b3d38066Chris Lattner#include <cstring> 30173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerusing namespace llvm; 31d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sandsusing namespace llvm::PatternMatch; 32d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 33d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sandsconst unsigned MaxDepth = 6; 34d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 35d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// getBitWidth - Returns the bitwidth of the given scalar or pointer type (if 36d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// unknown returns 0). For vector types, returns the element type's bitwidth. 37db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerstatic unsigned getBitWidth(Type *Ty, const TargetData *TD) { 38d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (unsigned BitWidth = Ty->getScalarSizeInBits()) 39d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return BitWidth; 40d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands assert(isa<PointerType>(Ty) && "Expected a pointer type!"); 41d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return TD ? TD->getPointerSizeInBits() : 0; 42d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands} 43173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 44173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// ComputeMaskedBits - Determine which of the bits specified in Mask are 45173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// known to be either zero or one and return them in the KnownZero/KnownOne 46173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// bit sets. This code only analyzes bits in Mask, in order to short-circuit 47173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// processing. 48173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that 49173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// we cannot optimize based on the assumption that it is zero without changing 50173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// it to be an explicit zero. If we don't change it to zero, other code could 51173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// optimized based on the contradictory assumption that it is non-zero. 52173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// Because instcombine aggressively folds operations with undef args anyway, 53173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this won't lose us code quality. 54cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// 55cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// This function is defined on values with integer type, values with pointer 56cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// type (but only if TD is non-null), and vectors of integers. In the case 57cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// where V is a vector, the mask, known zero, and known one values are the 58cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// same width as the vector element, and the bit is set only if it is true 59cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// for all of the elements in the vector. 60173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnervoid llvm::ComputeMaskedBits(Value *V, const APInt &Mask, 61173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt &KnownZero, APInt &KnownOne, 62846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman const TargetData *TD, unsigned Depth) { 63173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert(V && "No Value?"); 649004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman assert(Depth <= MaxDepth && "Limit Search Depth"); 6579abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned BitWidth = Mask.getBitWidth(); 661608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem assert((V->getType()->isIntOrIntVectorTy() || 671608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem V->getType()->getScalarType()->isPointerTy()) && 681608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem "Not integer or pointer type!"); 696de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman assert((!TD || 706de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman TD->getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) && 71b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands (!V->getType()->isIntOrIntVectorTy() || 726de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman V->getType()->getScalarSizeInBits() == BitWidth) && 731608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem KnownZero.getBitWidth() == BitWidth && 74173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.getBitWidth() == BitWidth && 75173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner "V, Mask, KnownOne and KnownZero should have same BitWidth"); 76173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 77173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 78173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We know all of the bits for a constant! 79173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = CI->getValue() & Mask; 80173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = ~KnownOne & Mask; 81173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 82173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 836de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // Null and aggregate-zero are all-zeros. 846de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman if (isa<ConstantPointerNull>(V) || 856de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman isa<ConstantAggregateZero>(V)) { 867a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 87173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask; 88173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 89173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 906de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // Handle a constant vector by taking the intersection of the known bits of 916de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // each element. 926de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) { 937a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownZero.setAllBits(); KnownOne.setAllBits(); 946de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) { 956de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0); 966de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman ComputeMaskedBits(CV->getOperand(i), Mask, KnownZero2, KnownOne2, 976de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman TD, Depth); 986de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman KnownZero &= KnownZero2; 996de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman KnownOne &= KnownOne2; 1006de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman } 1016de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman return; 1026de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman } 103173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // The address of an aligned GlobalValue has trailing zeros. 104173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 105173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = GV->getAlignment(); 106004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman if (Align == 0 && TD && GV->getType()->getElementType()->isSized()) { 107c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman if (GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV)) { 108c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman Type *ObjectType = GVar->getType()->getElementType(); 109c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman // If the object is defined in the current Module, we'll be giving 110c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman // it the preferred alignment. Otherwise, we have to assume that it 111c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman // may only have the minimum ABI alignment. 112d3a38ccfbb6be0edad037961df77649db2cb9597Duncan Sands if (!GVar->isDeclaration() && !GVar->isWeakForLinker()) 113c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman Align = TD->getPreferredAlignment(GVar); 114c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman else 115c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman Align = TD->getABITypeAlignment(ObjectType); 116c4c2a024857ca92687728f573a3017091a79eaf4Eli Friedman } 117004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman } 118173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 119173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & APInt::getLowBitsSet(BitWidth, 120173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_32(Align)); 121173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 1227a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownZero.clearAllBits(); 1237a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 124173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 125173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 126307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has 127307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman // the bits of its aliasee. 128307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 129307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman if (GA->mayBeOverridden()) { 1307a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownZero.clearAllBits(); KnownOne.clearAllBits(); 131307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman } else { 132307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman ComputeMaskedBits(GA->getAliasee(), Mask, KnownZero, KnownOne, 133307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman TD, Depth+1); 134307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman } 135307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman return; 136307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman } 137b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner 138b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner if (Argument *A = dyn_cast<Argument>(V)) { 139b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner // Get alignment information off byval arguments if specified in the IR. 140b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner if (A->hasByValAttr()) 141b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner if (unsigned Align = A->getParamAlignment()) 142b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner KnownZero = Mask & APInt::getLowBitsSet(BitWidth, 143b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner CountTrailingZeros_32(Align)); 144b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner return; 145b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner } 146173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 147b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner // Start out not knowing anything. 148b3f0673d52b72f34434dec13c4e2044c82012ef6Chris Lattner KnownZero.clearAllBits(); KnownOne.clearAllBits(); 149173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1509004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (Depth == MaxDepth || Mask == 0) 151173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Limit search depth. 152173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 153ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *I = dyn_cast<Operator>(V); 154173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!I) return; 155173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 156173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero2(KnownZero), KnownOne2(KnownOne); 157ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman switch (I->getOpcode()) { 158173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 159173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: { 160173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If either the LHS or the RHS are Zero, the result is zero. 161173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 162173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask & ~KnownZero); 163173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 164173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 165173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 166173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 167173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 168173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 bits are only known if set in both the LHS & RHS. 169173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 170173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 are known to be clear if zero in either the LHS | RHS. 171173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= KnownZero2; 172173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 173173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 174173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: { 175173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 176173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask & ~KnownOne); 177173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 178173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 179173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 180173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 181173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 182173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are only known if clear in both the LHS & RHS. 183173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 184173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in either the LHS | RHS. 185173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= KnownOne2; 186173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 187173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 188173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: { 189173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 190173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask, KnownZero2, KnownOne2, TD, 191173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 192173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 193173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 194173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 195173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are known if clear or set in both the LHS & RHS. 196173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 197173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in only one of the LHS, RHS. 198173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 199173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = KnownZeroOut; 200173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 201173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 202173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Mul: { 203173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = APInt::getAllOnesValue(BitWidth); 204173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero, KnownOne, TD,Depth+1); 205173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 206173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 20732a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 20832a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 20932a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands 21032a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands bool isKnownNegative = false; 21132a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands bool isKnownNonNegative = false; 21232a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // If the multiplication is known not to overflow, compute the sign bit. 21332a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands if (Mask.isNegative() && 21432a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap()) { 21532a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands Value *Op1 = I->getOperand(1), *Op2 = I->getOperand(0); 21632a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands if (Op1 == Op2) { 21732a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // The product of a number with itself is non-negative. 21832a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands isKnownNonNegative = true; 21932a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands } else { 22032a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands bool isKnownNonNegative1 = KnownZero.isNegative(); 22132a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands bool isKnownNonNegative2 = KnownZero2.isNegative(); 22232a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands bool isKnownNegative1 = KnownOne.isNegative(); 22332a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands bool isKnownNegative2 = KnownOne2.isNegative(); 22432a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // The product of two numbers with the same sign is non-negative. 22532a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands isKnownNonNegative = (isKnownNegative1 && isKnownNegative2) || 22632a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands (isKnownNonNegative1 && isKnownNonNegative2); 22732a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // The product of a negative number and a non-negative number is either 22832a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // negative or zero. 22932a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands if (!isKnownNonNegative) 23032a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands isKnownNegative = (isKnownNegative1 && isKnownNonNegative2 && 23132a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands isKnownNonZero(Op2, TD, Depth)) || 23232a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands (isKnownNegative2 && isKnownNonNegative1 && 23332a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands isKnownNonZero(Op1, TD, Depth)); 23432a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands } 23532a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands } 23632a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands 237173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If low bits are zero in either operand, output low known-0 bits. 238173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Also compute a conserative estimate for high known-0 bits. 239173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // More trickiness is possible, but this is sufficient for the 240173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // interesting case of alignment computation. 2417a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 242173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TrailZ = KnownZero.countTrailingOnes() + 243173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes(); 244173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 245173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countLeadingOnes(), 246173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner BitWidth) - BitWidth; 247173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 248173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, BitWidth); 249173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ = std::min(LeadZ, BitWidth); 250173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 251173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt::getHighBitsSet(BitWidth, LeadZ); 252173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= Mask; 25332a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands 254a8f5cd3539580b2fe3c20c748c1374f76992f113Duncan Sands // Only make use of no-wrap flags if we failed to compute the sign bit 255a8f5cd3539580b2fe3c20c748c1374f76992f113Duncan Sands // directly. This matters if the multiplication always overflows, in 256a8f5cd3539580b2fe3c20c748c1374f76992f113Duncan Sands // which case we prefer to follow the result of the direct computation, 257a8f5cd3539580b2fe3c20c748c1374f76992f113Duncan Sands // though as the program is invoking undefined behaviour we can choose 258a8f5cd3539580b2fe3c20c748c1374f76992f113Duncan Sands // whatever we like here. 259a8f5cd3539580b2fe3c20c748c1374f76992f113Duncan Sands if (isKnownNonNegative && !KnownOne.isNegative()) 26032a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands KnownZero.setBit(BitWidth - 1); 261a8f5cd3539580b2fe3c20c748c1374f76992f113Duncan Sands else if (isKnownNegative && !KnownZero.isNegative()) 26232a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands KnownOne.setBit(BitWidth - 1); 26332a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands 264173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 265173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 266173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UDiv: { 267173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // For the purposes of computing leading zeros we can conservatively 268173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // treat a udiv as a logical right shift by the power of 2 known to 269173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // be less than the denominator. 270173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 271173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), 272173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllOnes, KnownZero2, KnownOne2, TD, Depth+1); 273173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LeadZ = KnownZero2.countLeadingOnes(); 274173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 2757a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne2.clearAllBits(); 2767a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownZero2.clearAllBits(); 277173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), 278173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllOnes, KnownZero2, KnownOne2, TD, Depth+1); 279173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 280173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RHSUnknownLeadingOnes != BitWidth) 281173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ = std::min(BitWidth, 282173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 283173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 284173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask; 285173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 286173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 287173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 288173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(2), Mask, KnownZero, KnownOne, TD, Depth+1); 289173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero2, KnownOne2, TD, 290173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 291173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 292173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 293173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 294173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Only known if known in both the LHS and RHS. 295173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 296173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 297173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 298173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPTrunc: 299173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPExt: 300173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToUI: 301173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToSI: 302173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SIToFP: 303173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UIToFP: 304173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Can't work with floating point. 305173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PtrToInt: 306173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::IntToPtr: 307173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We can't handle these if we don't know the pointer size. 308173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 309173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FALL THROUGH and handle them the same as zext/trunc. 310173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::ZExt: 311173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: { 312db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *SrcTy = I->getOperand(0)->getType(); 313b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner 314b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner unsigned SrcBitWidth; 315173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Note that we handle pointer operands here because of inttoptr/ptrtoint 316173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // which fall through here. 3171df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (SrcTy->isPointerTy()) 318b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner SrcBitWidth = TD->getTypeSizeInBits(SrcTy); 319b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner else 320b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner SrcBitWidth = SrcTy->getScalarSizeInBits(); 321b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner 32240f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad APInt MaskIn = Mask.zextOrTrunc(SrcBitWidth); 32340f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zextOrTrunc(SrcBitWidth); 32440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zextOrTrunc(SrcBitWidth); 325173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD, 326173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 32740f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zextOrTrunc(BitWidth); 32840f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zextOrTrunc(BitWidth); 329173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Any top bits are known to be zero. 330173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (BitWidth > SrcBitWidth) 331173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 332173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 333173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 334173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::BitCast: { 335db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *SrcTy = I->getOperand(0)->getType(); 3361df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if ((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) && 3370dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner // TODO: For now, not handling conversions like: 3380dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner // (bitcast i64 %x to <2 x i32>) 3391df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands !I->getType()->isVectorTy()) { 340173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask, KnownZero, KnownOne, TD, 341173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 342173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 343173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 344173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 345173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 346173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: { 347173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the bits in the result that are not present in the input. 348b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); 349173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 35040f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad APInt MaskIn = Mask.trunc(SrcBitWidth); 35140f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.trunc(SrcBitWidth); 35240f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.trunc(SrcBitWidth); 353173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD, 354173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 355173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 35640f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownZero = KnownZero.zext(BitWidth); 35740f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad KnownOne = KnownOne.zext(BitWidth); 358173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 359173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the sign bit of the input is known set or clear, then we know the 360173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // top bits of the result. 361173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[SrcBitWidth-1]) // Input sign bit known zero 362173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 363173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[SrcBitWidth-1]) // Input sign bit known set 364173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 365173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 366173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 367173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Shl: 368173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 369173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 370173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 371173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.lshr(ShiftAmt)); 372173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 373173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 374173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 375173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero <<= ShiftAmt; 376173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne <<= ShiftAmt; 377173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 378173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 379173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 380173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 381173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::LShr: 382173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 383173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 384173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 385173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 386173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 387173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Unsigned shift right. 388173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.shl(ShiftAmt)); 389173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero,KnownOne, TD, 390173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 391ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 392173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 393173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 394173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // high bits known zero. 395173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 396173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 397173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 398173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 399173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::AShr: 400173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (ashr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 401173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 402173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 40343b40a4620c155c73ac71b48472ea2411d7c35daChris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 404173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 405173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Signed shift right. 406173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.shl(ShiftAmt)); 407173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 408173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 409ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 410173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 411173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 412173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 413173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 414173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[BitWidth-ShiftAmt-1]) // New bits are known zero. 415173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= HighBits; 416173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[BitWidth-ShiftAmt-1]) // New bits are known one. 417173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= HighBits; 418173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 419173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 420173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 421173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: { 422173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CLHS = dyn_cast<ConstantInt>(I->getOperand(0))) { 423173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We know that the top bits of C-X are clear if X contains less bits 424173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // than C (i.e. no wrap-around can happen). For example, 20-X is 425173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // positive if we can prove that X is >= 0 and < 16. 426173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!CLHS->getValue().isNegative()) { 427173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros(); 428173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // NLZ can't be BitWidth with no sign bit 429173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 430173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), MaskV, KnownZero2, KnownOne2, 431173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 432173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 433173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If all of the MaskV bits are known to be zero, then we know the 434173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // output top bits are zero, because we now know that the output is 435173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // from [0-C]. 436173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero2 & MaskV) == MaskV) { 437173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned NLZ2 = CLHS->getValue().countLeadingZeros(); 438173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Top bits known zero. 439173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask; 440173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 441173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 442173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 443173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 444173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // fall through 445173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: { 446ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky // If one of the operands has trailing zeros, then the bits that the 4473925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // other operand has in those bit positions will be preserved in the 4483925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // result. For an add, this works with either operand. For a subtract, 4493925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // this only works if the known zeros are in the right operand. 4503925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 4513925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt Mask2 = APInt::getLowBitsSet(BitWidth, 4523925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman BitWidth - Mask.countLeadingZeros()); 4533925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman ComputeMaskedBits(I->getOperand(0), Mask2, LHSKnownZero, LHSKnownOne, TD, 454173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 4553925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman assert((LHSKnownZero & LHSKnownOne) == 0 && 4563925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman "Bits known to be one AND zero?"); 4573925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman unsigned LHSKnownZeroOut = LHSKnownZero.countTrailingOnes(); 458173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 459173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero2, KnownOne2, TD, 460173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 461173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 4623925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman unsigned RHSKnownZeroOut = KnownZero2.countTrailingOnes(); 463173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 4643925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // Determine which operand has more trailing zeros, and use that 4653925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // many bits from the other operand. 4663925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman if (LHSKnownZeroOut > RHSKnownZeroOut) { 467ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman if (I->getOpcode() == Instruction::Add) { 4683925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt Mask = APInt::getLowBitsSet(BitWidth, LHSKnownZeroOut); 4693925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownZero |= KnownZero2 & Mask; 4703925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownOne |= KnownOne2 & Mask; 4713925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } else { 4723925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // If the known zeros are in the left operand for a subtract, 4733925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // fall back to the minimum known zeros in both operands. 4743925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownZero |= APInt::getLowBitsSet(BitWidth, 4753925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman std::min(LHSKnownZeroOut, 4763925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman RHSKnownZeroOut)); 4773925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } 4783925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } else if (RHSKnownZeroOut >= LHSKnownZeroOut) { 4793925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt Mask = APInt::getLowBitsSet(BitWidth, RHSKnownZeroOut); 4803925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownZero |= LHSKnownZero & Mask; 4813925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownOne |= LHSKnownOne & Mask; 4823925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } 483b69050a94c1c9266ab048a79c8375e5b14d87c72Nick Lewycky 484b69050a94c1c9266ab048a79c8375e5b14d87c72Nick Lewycky // Are we still trying to solve for the sign bit? 48514b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer if (Mask.isNegative() && !KnownZero.isNegative() && !KnownOne.isNegative()){ 486b69050a94c1c9266ab048a79c8375e5b14d87c72Nick Lewycky OverflowingBinaryOperator *OBO = cast<OverflowingBinaryOperator>(I); 487b69050a94c1c9266ab048a79c8375e5b14d87c72Nick Lewycky if (OBO->hasNoSignedWrap()) { 48814b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer if (I->getOpcode() == Instruction::Add) { 48914b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer // Adding two positive numbers can't wrap into negative 49014b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer if (LHSKnownZero.isNegative() && KnownZero2.isNegative()) 49114b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer KnownZero |= APInt::getSignBit(BitWidth); 49214b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer // and adding two negative numbers can't wrap into positive. 49314b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer else if (LHSKnownOne.isNegative() && KnownOne2.isNegative()) 49414b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer KnownOne |= APInt::getSignBit(BitWidth); 49514b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer } else { 49614b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer // Subtracting a negative number from a positive one can't wrap 49714b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer if (LHSKnownZero.isNegative() && KnownOne2.isNegative()) 49814b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer KnownZero |= APInt::getSignBit(BitWidth); 49914b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer // neither can subtracting a positive number from a negative one. 50014b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer else if (LHSKnownOne.isNegative() && KnownZero2.isNegative()) 50114b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer KnownOne |= APInt::getSignBit(BitWidth); 50214b2a59301e9e4065c7b9b07a0c68462b6037a4fBenjamin Kramer } 503b69050a94c1c9266ab048a79c8375e5b14d87c72Nick Lewycky } 504b69050a94c1c9266ab048a79c8375e5b14d87c72Nick Lewycky } 505b69050a94c1c9266ab048a79c8375e5b14d87c72Nick Lewycky 506173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 507173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 508173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SRem: 509173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 510cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands APInt RA = Rem->getValue().abs(); 511cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands if (RA.isPowerOf2()) { 512cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands APInt LowBits = RA - 1; 513173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 514173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 515173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 516173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 517cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // The low bits of the first operand are unchanged by the srem. 518cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownZero = KnownZero2 & LowBits; 519cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownOne = KnownOne2 & LowBits; 520cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands 521cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // If the first operand is non-negative or has all low bits zero, then 522cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // the upper bits are all zero. 523173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 524cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownZero |= ~LowBits; 525173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 526cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // If the first operand is negative and not all low bits are zero, then 527cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // the upper bits are all one. 528cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0)) 529cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownOne |= ~LowBits; 530cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands 531cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownZero &= Mask; 532cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownOne &= Mask; 533173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 534ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 535173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 536173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 537c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky 538c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // The sign bit is the LHS's sign bit, except when the result of the 539c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // remainder is zero. 540c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky if (Mask.isNegative() && KnownZero.isNonNegative()) { 541c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky APInt Mask2 = APInt::getSignBit(BitWidth); 542c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 543c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky ComputeMaskedBits(I->getOperand(0), Mask2, LHSKnownZero, LHSKnownOne, TD, 544c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky Depth+1); 545c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky // If it's known zero, our sign bit is also zero. 546c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky if (LHSKnownZero.isNegative()) 547c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky KnownZero |= LHSKnownZero; 548c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky } 549c14bc77315ac4867f16c1585181b41919339eb3cNick Lewycky 550173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 551173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::URem: { 552173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 553173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt RA = Rem->getValue(); 554173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RA.isPowerOf2()) { 555173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LowBits = (RA - 1); 556173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = LowBits & Mask; 557173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= ~LowBits & Mask; 558173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 559173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 560ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 561173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 562173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 563173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 564173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 565173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Since the result is less than or equal to either operand, any leading 566173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits in either operand must also exist in the result. 567173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 568173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), AllOnes, KnownZero, KnownOne, 569173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 570173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), AllOnes, KnownZero2, KnownOne2, 571173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 572173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 57379abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned Leaders = std::max(KnownZero.countLeadingOnes(), 574173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countLeadingOnes()); 5757a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad KnownOne.clearAllBits(); 576173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask; 577173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 578173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 579173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 580a276c603b82a11b0bf0b59f0517a69e4b63adeabVictor Hernandez case Instruction::Alloca: { 5817b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AI = cast<AllocaInst>(V); 582173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = AI->getAlignment(); 583a276c603b82a11b0bf0b59f0517a69e4b63adeabVictor Hernandez if (Align == 0 && TD) 584a276c603b82a11b0bf0b59f0517a69e4b63adeabVictor Hernandez Align = TD->getABITypeAlignment(AI->getType()->getElementType()); 585173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 586173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 587173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & APInt::getLowBitsSet(BitWidth, 588173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_32(Align)); 589173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 590173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 591173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::GetElementPtr: { 592173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Analyze all of the subscripts of this getelementptr instruction 593173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // to determine if we can prove known low zero bits. 594173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LocalMask = APInt::getAllOnesValue(BitWidth); 595173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0); 596173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), LocalMask, 597173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero, LocalKnownOne, TD, Depth+1); 598173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TrailZ = LocalKnownZero.countTrailingOnes(); 599173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 600173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner gep_type_iterator GTI = gep_type_begin(I); 601173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) { 602173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *Index = I->getOperand(i); 603db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *STy = dyn_cast<StructType>(*GTI)) { 604173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle struct member offset arithmetic. 605173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 606173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const StructLayout *SL = TD->getStructLayout(STy); 607173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Idx = cast<ConstantInt>(Index)->getZExtValue(); 608173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t Offset = SL->getElementOffset(Idx); 609173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, 610173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_64(Offset)); 611173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 612173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle array index arithmetic. 613db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *IndexedTy = GTI.getIndexedType(); 614173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!IndexedTy->isSized()) return; 6156de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits(); 616777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t TypeSize = TD ? TD->getTypeAllocSize(IndexedTy) : 1; 617173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalMask = APInt::getAllOnesValue(GEPOpiBits); 618173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0); 619173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(Index, LocalMask, 620173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero, LocalKnownOne, TD, Depth+1); 621173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, 62279abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned(CountTrailingZeros_64(TypeSize) + 62379abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner LocalKnownZero.countTrailingOnes())); 624173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 625173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 626173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 627173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) & Mask; 628173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 629173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 630173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PHI: { 631173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner PHINode *P = cast<PHINode>(I); 632173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle the case of a simple two-predecessor recurrence PHI. 633173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // There's a lot more that could theoretically be done here, but 634173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // this is sufficient to catch some interesting cases. 635173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (P->getNumIncomingValues() == 2) { 636173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 0; i != 2; ++i) { 637173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *L = P->getIncomingValue(i); 638173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *R = P->getIncomingValue(!i); 639ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *LU = dyn_cast<Operator>(L); 640173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!LU) 641173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner continue; 642ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman unsigned Opcode = LU->getOpcode(); 643173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Check for operations that have the property that if 644173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // both their operands have low zero bits, the result 645173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // will have low zero bits. 646173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Opcode == Instruction::Add || 647173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Sub || 648173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::And || 649173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Or || 650173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Mul) { 651173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LL = LU->getOperand(0); 652173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LR = LU->getOperand(1); 653173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Find a recurrence. 654173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (LL == I) 655173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LR; 656173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (LR == I) 657173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LL; 658173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 659173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 660173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Ok, we have a PHI of the form L op= R. Check for low 661173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits. 662173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = APInt::getAllOnesValue(BitWidth); 663173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(R, Mask2, KnownZero2, KnownOne2, TD, Depth+1); 664173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask2 = APInt::getLowBitsSet(BitWidth, 665173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes()); 666c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene 667c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene // We need to take the minimum number of known bits 668c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene APInt KnownZero3(KnownZero), KnownOne3(KnownOne); 669c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene ComputeMaskedBits(L, Mask2, KnownZero3, KnownOne3, TD, Depth+1); 670c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene 671173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & 672173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt::getLowBitsSet(BitWidth, 673c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene std::min(KnownZero2.countTrailingOnes(), 674c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene KnownZero3.countTrailingOnes())); 675173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 676173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 677173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 678173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 6799004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman 6803b739d278c87f8ac22b5dc368b319fa278347b2fNick Lewycky // Unreachable blocks may have zero-operand PHI nodes. 6813b739d278c87f8ac22b5dc368b319fa278347b2fNick Lewycky if (P->getNumIncomingValues() == 0) 6823b739d278c87f8ac22b5dc368b319fa278347b2fNick Lewycky return; 6833b739d278c87f8ac22b5dc368b319fa278347b2fNick Lewycky 6849004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Otherwise take the unions of the known bit sets of the operands, 6859004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // taking conservative care to avoid excessive recursion. 6869004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) { 687606199fb85d1c8407615e575b5e8bb5c71be27bdDuncan Sands // Skip if every incoming value references to ourself. 688606199fb85d1c8407615e575b5e8bb5c71be27bdDuncan Sands if (P->hasConstantValue() == P) 689606199fb85d1c8407615e575b5e8bb5c71be27bdDuncan Sands break; 690606199fb85d1c8407615e575b5e8bb5c71be27bdDuncan Sands 6919004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero = APInt::getAllOnesValue(BitWidth); 6929004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne = APInt::getAllOnesValue(BitWidth); 6939004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { 6949004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Skip direct self references. 6959004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (P->getIncomingValue(i) == P) continue; 6969004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman 6979004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero2 = APInt(BitWidth, 0); 6989004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne2 = APInt(BitWidth, 0); 6999004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Recurse, but cap the recursion to one level, because we don't 7009004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // want to waste time spinning around in loops. 7019004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman ComputeMaskedBits(P->getIncomingValue(i), KnownZero | KnownOne, 7029004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero2, KnownOne2, TD, MaxDepth-1); 7039004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero &= KnownZero2; 7049004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne &= KnownOne2; 7059004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // If all bits have been ruled out, there's no need to check 7069004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // more operands. 7079004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (!KnownZero && !KnownOne) 7089004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman break; 7099004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman } 7109004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman } 711173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 712173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 713173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Call: 714173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 715173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner switch (II->getIntrinsicID()) { 716173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 717173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::ctpop: 718173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::ctlz: 719173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::cttz: { 720173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LowBits = Log2_32(BitWidth)+1; 721173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 722173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 723173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 72462660310d9e5f9ecf329fd3cacb67c344a12ddbcChad Rosier case Intrinsic::x86_sse42_crc32_64_8: 72562660310d9e5f9ecf329fd3cacb67c344a12ddbcChad Rosier case Intrinsic::x86_sse42_crc32_64_64: 726cb559c1270a773de2c97c99700dcd5456f24a732Evan Cheng KnownZero = APInt::getHighBitsSet(64, 32); 727cb559c1270a773de2c97c99700dcd5456f24a732Evan Cheng break; 728173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 729173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 730173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 731173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 732173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 733173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 734d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// ComputeSignBit - Determine whether the sign bit is known to be zero or 735d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// one. Convenience wrapper around ComputeMaskedBits. 736d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sandsvoid llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, 737d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands const TargetData *TD, unsigned Depth) { 738d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands unsigned BitWidth = getBitWidth(V->getType(), TD); 739d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (!BitWidth) { 740d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands KnownZero = false; 741d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands KnownOne = false; 742d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return; 743d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 744d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt ZeroBits(BitWidth, 0); 745d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt OneBits(BitWidth, 0); 746d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeMaskedBits(V, APInt::getSignBit(BitWidth), ZeroBits, OneBits, TD, 747d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands Depth); 748d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands KnownOne = OneBits[BitWidth - 1]; 749d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands KnownZero = ZeroBits[BitWidth - 1]; 750d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands} 751d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 752d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// isPowerOfTwo - Return true if the given value is known to have exactly one 753d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// bit set when defined. For vectors return true if every element is known to 754d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// be a power of two when defined. Supports values with integer or pointer 755d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// types and vectors of integers. 756dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sandsbool llvm::isPowerOfTwo(Value *V, const TargetData *TD, bool OrZero, 757dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands unsigned Depth) { 758dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (Constant *C = dyn_cast<Constant>(V)) { 759dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (C->isNullValue()) 760dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return OrZero; 761dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 762dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return CI->getValue().isPowerOf2(); 763dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands // TODO: Handle vector constants. 764dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands } 765d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 766d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // 1 << X is clearly a power of two if the one is not shifted off the end. If 767d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // it is shifted off the end then the result is undefined. 768d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (match(V, m_Shl(m_One(), m_Value()))) 769d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 770d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 771d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // (signbit) >>l X is clearly a power of two if the one is not shifted off the 772d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // bottom. If it is shifted off the bottom then the result is undefined. 77393c780288df9631d11f996b010b2212a8b44d4d3Duncan Sands if (match(V, m_LShr(m_SignBit(), m_Value()))) 774d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 775d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 776d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The remaining tests are all recursive, so bail out if we hit the limit. 777d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (Depth++ == MaxDepth) 778d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 779d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 7804604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands Value *X = 0, *Y = 0; 7814604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands // A shift of a power of two is a power of two or zero. 7824604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) || 7834604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands match(V, m_Shr(m_Value(X), m_Value())))) 7844604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands return isPowerOfTwo(X, TD, /*OrZero*/true, Depth); 7854604fc7791314af7ba7b66999e4c7fb75a4d9f6eDuncan Sands 786d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (ZExtInst *ZI = dyn_cast<ZExtInst>(V)) 787dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return isPowerOfTwo(ZI->getOperand(0), TD, OrZero, Depth); 788d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 789d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (SelectInst *SI = dyn_cast<SelectInst>(V)) 790dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return isPowerOfTwo(SI->getTrueValue(), TD, OrZero, Depth) && 791dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands isPowerOfTwo(SI->getFalseValue(), TD, OrZero, Depth); 792dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands 793dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) { 794dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands // A power of two and'd with anything is a power of two or zero. 795dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (isPowerOfTwo(X, TD, /*OrZero*/true, Depth) || 796dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands isPowerOfTwo(Y, TD, /*OrZero*/true, Depth)) 797dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return true; 798dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands // X & (-X) is always a power of two or zero. 799dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X)))) 800dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return true; 801dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return false; 802dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands } 803d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 8043dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky // An exact divide or right shift can only shift off zero bits, so the result 8051f7bc701b030f5b01553f306cc975eeac1e4d99bNick Lewycky // is a power of two only if the first operand is a power of two and not 8061f7bc701b030f5b01553f306cc975eeac1e4d99bNick Lewycky // copying a sign bit (sdiv int_min, 2). 8071f7bc701b030f5b01553f306cc975eeac1e4d99bNick Lewycky if (match(V, m_LShr(m_Value(), m_Value())) || 8081f7bc701b030f5b01553f306cc975eeac1e4d99bNick Lewycky match(V, m_UDiv(m_Value(), m_Value()))) { 8096bdd261df972b5e70e4242721ab16b57c6fe3d1fEli Friedman PossiblyExactOperator *PEO = cast<PossiblyExactOperator>(V); 8106bdd261df972b5e70e4242721ab16b57c6fe3d1fEli Friedman if (PEO->isExact()) 811dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands return isPowerOfTwo(PEO->getOperand(0), TD, OrZero, Depth); 8123dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky } 8133dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky 814d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 815d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands} 816d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 817d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// isKnownNonZero - Return true if the given value is known to be non-zero 818d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// when defined. For vectors return true if every element is known to be 819d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// non-zero when defined. Supports values with integer or pointer type and 820d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands/// vectors of integers. 821d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sandsbool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { 822d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (Constant *C = dyn_cast<Constant>(V)) { 823d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (C->isNullValue()) 824d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 825d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (isa<ConstantInt>(C)) 826d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // Must be non-zero due to null test above. 827d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 828d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // TODO: Handle vectors 829d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 830d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 831d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 832d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The remaining tests are all recursive, so bail out if we hit the limit. 83332a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands if (Depth++ >= MaxDepth) 834d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return false; 835d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 836d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands unsigned BitWidth = getBitWidth(V->getType(), TD); 837d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 838d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // X | Y != 0 if X != 0 or Y != 0. 839d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands Value *X = 0, *Y = 0; 840d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (match(V, m_Or(m_Value(X), m_Value(Y)))) 841d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return isKnownNonZero(X, TD, Depth) || isKnownNonZero(Y, TD, Depth); 842d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 843d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // ext X != 0 if X != 0. 844d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (isa<SExtInst>(V) || isa<ZExtInst>(V)) 845d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return isKnownNonZero(cast<Instruction>(V)->getOperand(0), TD, Depth); 846d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 8479136782d273cd45b6f19a7d0cc0d146d0791bac9Duncan Sands // shl X, Y != 0 if X is odd. Note that the value of the shift is undefined 848d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // if the lowest bit is shifted off the end. 849d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (BitWidth && match(V, m_Shl(m_Value(X), m_Value(Y)))) { 8503dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky // shl nuw can't remove any non-zero bits. 85132a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); 8523dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky if (BO->hasNoUnsignedWrap()) 8533dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky return isKnownNonZero(X, TD, Depth); 8543dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky 855d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownZero(BitWidth, 0); 856d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownOne(BitWidth, 0); 8579136782d273cd45b6f19a7d0cc0d146d0791bac9Duncan Sands ComputeMaskedBits(X, APInt(BitWidth, 1), KnownZero, KnownOne, TD, Depth); 858d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (KnownOne[0]) 859d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 860d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 8619136782d273cd45b6f19a7d0cc0d146d0791bac9Duncan Sands // shr X, Y != 0 if X is negative. Note that the value of the shift is not 862d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // defined if the sign bit is shifted off the end. 863d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) { 8643dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky // shr exact can only shift out zero bits. 86532a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V); 8663dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky if (BO->isExact()) 8673dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky return isKnownNonZero(X, TD, Depth); 8683dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky 869d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands bool XKnownNonNegative, XKnownNegative; 870d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); 871d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (XKnownNegative) 872d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 873d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 8743dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky // div exact can only produce a zero if the dividend is zero. 8753dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky else if (match(V, m_IDiv(m_Value(X), m_Value()))) { 87632a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V); 8773dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky if (BO->isExact()) 8783dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky return isKnownNonZero(X, TD, Depth); 8793dfd98744c1f6e6c5d13e419b63ac69894ae84cfNick Lewycky } 880d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // X + Y. 881d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands else if (match(V, m_Add(m_Value(X), m_Value(Y)))) { 882d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands bool XKnownNonNegative, XKnownNegative; 883d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands bool YKnownNonNegative, YKnownNegative; 884d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); 885d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, TD, Depth); 886d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 887d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // If X and Y are both non-negative (as signed values) then their sum is not 888227fba11ca168225d913d1cea94a05b883092e76Duncan Sands // zero unless both X and Y are zero. 889d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (XKnownNonNegative && YKnownNonNegative) 890227fba11ca168225d913d1cea94a05b883092e76Duncan Sands if (isKnownNonZero(X, TD, Depth) || isKnownNonZero(Y, TD, Depth)) 891227fba11ca168225d913d1cea94a05b883092e76Duncan Sands return true; 892d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 893d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // If X and Y are both negative (as signed values) then their sum is not 894d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // zero unless both X and Y equal INT_MIN. 895d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (BitWidth && XKnownNegative && YKnownNegative) { 896d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownZero(BitWidth, 0); 897d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownOne(BitWidth, 0); 898d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt Mask = APInt::getSignedMaxValue(BitWidth); 899d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The sign bit of X is set. If some other bit is set then X is not equal 900d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // to INT_MIN. 901d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeMaskedBits(X, Mask, KnownZero, KnownOne, TD, Depth); 902d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if ((KnownOne & Mask) != 0) 903d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 904d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The sign bit of Y is set. If some other bit is set then Y is not equal 905d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // to INT_MIN. 906d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeMaskedBits(Y, Mask, KnownZero, KnownOne, TD, Depth); 907d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if ((KnownOne & Mask) != 0) 908d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 909d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 910d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 911d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // The sum of a non-negative number and a power of two is not zero. 912dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (XKnownNonNegative && isPowerOfTwo(Y, TD, /*OrZero*/false, Depth)) 913d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 914dd3149d57977d0632cfaf24290dd93416fb2a0efDuncan Sands if (YKnownNonNegative && isPowerOfTwo(X, TD, /*OrZero*/false, Depth)) 915d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 916d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 91732a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // X * Y. 91832a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) { 91932a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); 92032a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // If X and Y are non-zero then so is X * Y as long as the multiplication 92132a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands // does not overflow. 92232a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) && 92332a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands isKnownNonZero(X, TD, Depth) && isKnownNonZero(Y, TD, Depth)) 92432a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands return true; 92532a43cc0fc3cd42702d7859eaa58dd42f561a54dDuncan Sands } 926d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // (C ? X : Y) != 0 if X != 0 and Y != 0. 927d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands else if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 928d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (isKnownNonZero(SI->getTrueValue(), TD, Depth) && 929d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands isKnownNonZero(SI->getFalseValue(), TD, Depth)) 930d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return true; 931d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 932d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 933d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (!BitWidth) return false; 934d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownZero(BitWidth, 0); 935d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands APInt KnownOne(BitWidth, 0); 936d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeMaskedBits(V, APInt::getAllOnesValue(BitWidth), KnownZero, KnownOne, 937d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands TD, Depth); 938d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return KnownOne != 0; 939d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands} 940d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 941173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 942173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this predicate to simplify operations downstream. Mask is known to be zero 943173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// for bits that V cannot have. 944cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// 945cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// This function is defined on values with integer type, values with pointer 946cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// type (but only if TD is non-null), and vectors of integers. In the case 947cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// where V is a vector, the mask, known zero, and known one values are the 948cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// same width as the vector element, and the bit is set only if it is true 949cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// for all of the elements in the vector. 950173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerbool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, 951846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman const TargetData *TD, unsigned Depth) { 952173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0); 953173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth); 954173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 955173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return (KnownZero & Mask) == Mask; 956173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 957173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 958173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 959173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 960173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// ComputeNumSignBits - Return the number of times the sign bit of the 961173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// register is replicated into the other bits. We know that at least 1 bit 962173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// is always equal to the sign bit (itself), but other cases can give us 963173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// information. For example, immediately after an "ashr X, 2", we know that 964173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// the top 3 bits are all equal to each other, so we return 3. 965173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 966173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 'Op' must have a scalar integer type. 967173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 968846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohmanunsigned llvm::ComputeNumSignBits(Value *V, const TargetData *TD, 969846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman unsigned Depth) { 970b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands assert((TD || V->getType()->isIntOrIntVectorTy()) && 971bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman "ComputeNumSignBits requires a TargetData object to operate " 972bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman "on non-integer values!"); 973db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = V->getType(); 974bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman unsigned TyBits = TD ? TD->getTypeSizeInBits(V->getType()->getScalarType()) : 975bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman Ty->getScalarSizeInBits(); 976173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Tmp, Tmp2; 977173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned FirstAnswer = 1; 978173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 979d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // Note that ConstantInt is handled by the general ComputeMaskedBits case 980d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // below. 981d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner 982173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Depth == 6) 983173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return 1; // Limit search depth. 984173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 985ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *U = dyn_cast<Operator>(V); 986ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman switch (Operator::getOpcode(V)) { 987173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 988173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: 98969a008075b29fbe0644ccbeecf1418ef8cca5e24Mon P Wang Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits(); 990173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return ComputeNumSignBits(U->getOperand(0), TD, Depth+1) + Tmp; 991173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 992173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::AShr: 993173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 994173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // ashr X, C -> adds C sign bits. 995173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(U->getOperand(1))) { 996173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp += C->getZExtValue(); 997173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp > TyBits) Tmp = TyBits; 998173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 9999a3dc552022e0e034ef34da889f6ceb9de260c96Nate Begeman // vector ashr X, <C, C, C, C> -> adds C sign bits 10009a3dc552022e0e034ef34da889f6ceb9de260c96Nate Begeman if (ConstantVector *C = dyn_cast<ConstantVector>(U->getOperand(1))) { 10019a3dc552022e0e034ef34da889f6ceb9de260c96Nate Begeman if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) { 10029a3dc552022e0e034ef34da889f6ceb9de260c96Nate Begeman Tmp += CI->getZExtValue(); 10039a3dc552022e0e034ef34da889f6ceb9de260c96Nate Begeman if (Tmp > TyBits) Tmp = TyBits; 10049a3dc552022e0e034ef34da889f6ceb9de260c96Nate Begeman } 10059a3dc552022e0e034ef34da889f6ceb9de260c96Nate Begeman } 1006173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 1007173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Shl: 1008173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(U->getOperand(1))) { 1009173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shl destroys sign bits. 1010173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1011173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (C->getZExtValue() >= TyBits || // Bad shift. 1012173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner C->getZExtValue() >= Tmp) break; // Shifted all sign bits out. 1013173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp - C->getZExtValue(); 1014173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1015173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 1016173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: 1017173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: 1018173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: // NOT is handled here. 1019173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Logical binary ops preserve the number of sign bits at the worst. 1020173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1021173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp != 1) { 1022173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1023173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner FirstAnswer = std::min(Tmp, Tmp2); 1024173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We computed what we know about the sign bits as our first 1025173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // answer. Now proceed to the generic code that uses 1026173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // ComputeMaskedBits, and pick whichever answer is better. 1027173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1028173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 1029173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1030173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 1031173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1032173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 1033173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(2), TD, Depth+1); 1034173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::min(Tmp, Tmp2); 1035173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1036173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: 1037173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Add can have at most one carry bit. Thus we know that the output 1038173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 1039173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1040173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 1041173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1042173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Special case decrementing a value (ADD X, -1): 10430001e56f15215ae4bc5fffb82eec5c4828b888f0Dan Gohman if (ConstantInt *CRHS = dyn_cast<ConstantInt>(U->getOperand(1))) 1044173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CRHS->isAllOnesValue()) { 1045173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 1046173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 1047173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(U->getOperand(0), Mask, KnownZero, KnownOne, TD, 1048173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 1049173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1050173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 1051173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 1052173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero | APInt(TyBits, 1)) == Mask) 1053173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 1054173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1055173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If we are subtracting one from a positive number, there is no carry 1056173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // out of the result. 1057173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 1058173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 1059173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1060173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1061173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1062173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 10638d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner return std::min(Tmp, Tmp2)-1; 1064173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1065173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: 1066173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1067173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 1068173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1069173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle NEG. 1070173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CLHS = dyn_cast<ConstantInt>(U->getOperand(0))) 1071173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CLHS->isNullValue()) { 1072173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 1073173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 1074173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(U->getOperand(1), Mask, KnownZero, KnownOne, 1075173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 1076173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 1077173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 1078173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero | APInt(TyBits, 1)) == Mask) 1079173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 1080173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1081173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be positive (the sign bit is known clear), 1082173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the output of the NEG has the same number of sign bits as the input. 1083173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 1084173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp2; 1085173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1086173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Otherwise, we treat this like a SUB. 1087173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1088173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1089173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Sub can have at most one carry bit. Thus we know that the output 1090173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 1091173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1092173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 10938d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner return std::min(Tmp, Tmp2)-1; 10948d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner 10958d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner case Instruction::PHI: { 10968d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner PHINode *PN = cast<PHINode>(U); 10978d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner // Don't analyze large in-degree PHIs. 10988d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner if (PN->getNumIncomingValues() > 4) break; 10998d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner 11008d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner // Take the minimum of all incoming values. This can't infinitely loop 11018d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner // because of our depth threshold. 11028d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner Tmp = ComputeNumSignBits(PN->getIncomingValue(0), TD, Depth+1); 11038d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 11048d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner if (Tmp == 1) return Tmp; 11058d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner Tmp = std::min(Tmp, 11060af20d847ac89f797d613a8a4fc3e7127ccb0b36Evan Cheng ComputeNumSignBits(PN->getIncomingValue(i), TD, Depth+1)); 11078d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner } 11088d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner return Tmp; 11098d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner } 11108d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner 1111173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: 1112173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FIXME: it's tricky to do anything useful for this, but it is an important 1113173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // case for targets like X86. 1114173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 1115173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1116173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1117173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Finally, if we can prove that the top bits of the result are 0's or 1's, 1118173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // use this information. 1119173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 1120173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 1121173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth); 1122173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1123173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) { // sign bit is 0 1124173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownZero; 1125173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else if (KnownOne.isNegative()) { // sign bit is 1; 1126173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownOne; 1127173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 1128173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Nothing known. 1129173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return FirstAnswer; 1130173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 1131173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1132173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 1133173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the number of identical bits in the top of the input value. 1134173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = ~Mask; 1135173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask <<= Mask.getBitWidth()-TyBits; 1136173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Return # leading zeros. We use 'min' here in case Val was zero before 1137173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shifting. We don't want to return '64' as for an i32 "0". 1138173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros())); 1139173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 1140833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 11412b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez/// ComputeMultiple - This function computes the integer multiple of Base that 11422b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez/// equals V. If successful, it returns true and returns the multiple in 11433dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman/// Multiple. If unsuccessful, it returns false. It looks 11442b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez/// through SExt instructions only if LookThroughSExt is true. 11452b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandezbool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, 11463dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman bool LookThroughSExt, unsigned Depth) { 11472b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez const unsigned MaxDepth = 6; 11482b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11493dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman assert(V && "No Value?"); 11502b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez assert(Depth <= MaxDepth && "Limit Search Depth"); 1151b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands assert(V->getType()->isIntegerTy() && "Not integer or pointer type!"); 11522b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 1153db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *T = V->getType(); 11542b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11553dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman ConstantInt *CI = dyn_cast<ConstantInt>(V); 11562b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11572b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Base == 0) 11582b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return false; 11592b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11602b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Base == 1) { 11612b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = V; 11622b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 11632b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 11642b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11652b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez ConstantExpr *CO = dyn_cast<ConstantExpr>(V); 11662b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Constant *BaseVal = ConstantInt::get(T, Base); 11672b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (CO && CO == BaseVal) { 11682b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // Multiple is 1. 11692b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = ConstantInt::get(T, 1); 11702b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 11712b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 11722b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11732b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (CI && CI->getZExtValue() % Base == 0) { 11742b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = ConstantInt::get(T, CI->getZExtValue() / Base); 11752b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 11762b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 11772b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11782b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Depth == MaxDepth) return false; // Limit search depth. 11792b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11802b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Operator *I = dyn_cast<Operator>(V); 11812b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (!I) return false; 11822b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11832b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez switch (I->getOpcode()) { 11842b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez default: break; 118511fe72661dac17efa1564ef6fc212acae4f0c07eChris Lattner case Instruction::SExt: 11862b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (!LookThroughSExt) return false; 11872b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // otherwise fall through to ZExt 118811fe72661dac17efa1564ef6fc212acae4f0c07eChris Lattner case Instruction::ZExt: 11893dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman return ComputeMultiple(I->getOperand(0), Base, Multiple, 11903dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman LookThroughSExt, Depth+1); 11912b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez case Instruction::Shl: 11922b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez case Instruction::Mul: { 11932b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Op0 = I->getOperand(0); 11942b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Op1 = I->getOperand(1); 11952b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 11962b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (I->getOpcode() == Instruction::Shl) { 11972b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1); 11982b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (!Op1CI) return false; 11992b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // Turn Op0 << Op1 into Op0 * 2^Op1 12002b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez APInt Op1Int = Op1CI->getValue(); 12012b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1); 1202a99793c5ea24dd3839f4925b89b1f6acfcb24604Jay Foad APInt API(Op1Int.getBitWidth(), 0); 12037a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad API.setBit(BitToSet); 1204a99793c5ea24dd3839f4925b89b1f6acfcb24604Jay Foad Op1 = ConstantInt::get(V->getContext(), API); 12052b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 12062b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 12072b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Mul0 = NULL; 1208e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (ComputeMultiple(Op0, Base, Mul0, LookThroughSExt, Depth+1)) { 1209e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Constant *Op1C = dyn_cast<Constant>(Op1)) 1210e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Constant *MulC = dyn_cast<Constant>(Mul0)) { 1211e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Op1C->getType()->getPrimitiveSizeInBits() < 1212e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC->getType()->getPrimitiveSizeInBits()) 1213e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Op1C = ConstantExpr::getZExt(Op1C, MulC->getType()); 1214e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Op1C->getType()->getPrimitiveSizeInBits() > 1215e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC->getType()->getPrimitiveSizeInBits()) 1216e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC = ConstantExpr::getZExt(MulC, Op1C->getType()); 1217e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner 1218e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner // V == Base * (Mul0 * Op1), so return (Mul0 * Op1) 1219e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Multiple = ConstantExpr::getMul(MulC, Op1C); 1220e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner return true; 1221e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner } 12222b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 12232b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (ConstantInt *Mul0CI = dyn_cast<ConstantInt>(Mul0)) 12242b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Mul0CI->getValue() == 1) { 12252b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // V == Base * Op1, so return Op1 12262b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = Op1; 12272b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 12282b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 12292b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 12302b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 1231e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Value *Mul1 = NULL; 1232e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (ComputeMultiple(Op1, Base, Mul1, LookThroughSExt, Depth+1)) { 1233e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Constant *Op0C = dyn_cast<Constant>(Op0)) 1234e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Constant *MulC = dyn_cast<Constant>(Mul1)) { 1235e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Op0C->getType()->getPrimitiveSizeInBits() < 1236e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC->getType()->getPrimitiveSizeInBits()) 1237e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Op0C = ConstantExpr::getZExt(Op0C, MulC->getType()); 1238e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner if (Op0C->getType()->getPrimitiveSizeInBits() > 1239e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC->getType()->getPrimitiveSizeInBits()) 1240e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner MulC = ConstantExpr::getZExt(MulC, Op0C->getType()); 1241e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner 1242e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner // V == Base * (Mul1 * Op0), so return (Mul1 * Op0) 1243e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner Multiple = ConstantExpr::getMul(MulC, Op0C); 1244e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner return true; 1245e971131695ac41afd56e82facddccc2807aa9bbdChris Lattner } 12462b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 12472b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (ConstantInt *Mul1CI = dyn_cast<ConstantInt>(Mul1)) 12482b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Mul1CI->getValue() == 1) { 12492b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // V == Base * Op0, so return Op0 12502b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = Op0; 12512b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 12522b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 12532b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 12542b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 12552b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 12562b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 12572b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // We could not determine if V is a multiple of Base. 12582b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return false; 12592b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez} 12602b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 1261833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// CannotBeNegativeZero - Return true if we can prove that the specified FP 1262833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// value is never equal to -0.0. 1263833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 1264833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// NOTE: this function will need to be revisited when we support non-default 1265833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// rounding modes! 1266833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 1267833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattnerbool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { 1268833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) 1269833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return !CFP->getValueAPF().isNegZero(); 1270833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1271833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (Depth == 6) 1272833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return 1; // Limit search depth. 1273833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1274ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman const Operator *I = dyn_cast<Operator>(V); 1275833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (I == 0) return false; 1276833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1277833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // (add x, 0.0) is guaranteed to return +0.0, not -0.0. 1278ae3a0be92e33bc716722aa600983fc1535acb122Dan Gohman if (I->getOpcode() == Instruction::FAdd && 1279833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner isa<ConstantFP>(I->getOperand(1)) && 1280833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner cast<ConstantFP>(I->getOperand(1))->isNullValue()) 1281833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return true; 1282833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1283833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sitofp and uitofp turn into +0.0 for zero. 1284833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I)) 1285833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return true; 1286833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1287833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 1288833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sqrt(-0.0) = -0.0, no other negative results are possible. 1289833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (II->getIntrinsicID() == Intrinsic::sqrt) 129071339c965ca6268b9bff91213364783c3d06f666Gabor Greif return CannotBeNegativeZero(II->getArgOperand(0), Depth+1); 1291833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1292833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const CallInst *CI = dyn_cast<CallInst>(I)) 1293833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const Function *F = CI->getCalledFunction()) { 1294833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (F->isDeclaration()) { 1295f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar // abs(x) != -0.0 1296f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar if (F->getName() == "abs") return true; 12979d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen // fabs[lf](x) != -0.0 12989d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "fabs") return true; 12999d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "fabsf") return true; 13009d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "fabsl") return true; 13019d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "sqrt" || F->getName() == "sqrtf" || 13029d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen F->getName() == "sqrtl") 130371339c965ca6268b9bff91213364783c3d06f666Gabor Greif return CannotBeNegativeZero(CI->getArgOperand(0), Depth+1); 1304833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 1305833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 1306833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1307833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return false; 1308833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner} 1309833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 1310bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// isBytewiseValue - If the specified value can be set by repeating the same 1311bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// byte in memory, return the i8 value that it is represented with. This is 1312bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// true for all i8 values obviously, but is also true for i32 0, i32 -1, 1313bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// i16 0xF0F0, double 0.0 etc. If the value can't be handled with a repeated 1314bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner/// byte store (e.g. i16 0x1234), return null. 1315bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris LattnerValue *llvm::isBytewiseValue(Value *V) { 1316bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // All byte-wide stores are splatable, even of arbitrary variables. 1317bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (V->getType()->isIntegerTy(8)) return V; 131841bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner 131941bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner // Handle 'null' ConstantArrayZero etc. 132041bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner if (Constant *C = dyn_cast<Constant>(V)) 132141bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner if (C->isNullValue()) 132241bfbb0a8776674c486682cbf2aa80f15abfef68Chris Lattner return Constant::getNullValue(Type::getInt8Ty(V->getContext())); 1323bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1324bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // Constant float and double values can be handled as integer values if the 1325bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // corresponding integer value is "byteable". An important case is 0.0. 1326bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) { 1327bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (CFP->getType()->isFloatTy()) 1328bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner V = ConstantExpr::getBitCast(CFP, Type::getInt32Ty(V->getContext())); 1329bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (CFP->getType()->isDoubleTy()) 1330bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner V = ConstantExpr::getBitCast(CFP, Type::getInt64Ty(V->getContext())); 1331bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // Don't handle long double formats, which have strange constraints. 1332bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1333bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1334bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // We can handle constant integers that are power of two in size and a 1335bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // multiple of 8 bits. 1336bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 1337bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner unsigned Width = CI->getBitWidth(); 1338bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (isPowerOf2_32(Width) && Width > 8) { 1339bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // We can handle this value if the recursive binary decomposition is the 1340bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // same at all levels. 1341bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner APInt Val = CI->getValue(); 1342bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner APInt Val2; 1343bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner while (Val.getBitWidth() != 8) { 1344bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner unsigned NextWidth = Val.getBitWidth()/2; 1345bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner Val2 = Val.lshr(NextWidth); 1346bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner Val2 = Val2.trunc(Val.getBitWidth()/2); 1347bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner Val = Val.trunc(Val.getBitWidth()/2); 1348bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1349bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // If the top/bottom halves aren't the same, reject it. 1350bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (Val != Val2) 1351bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return 0; 1352bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1353bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return ConstantInt::get(V->getContext(), Val); 1354bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1355bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1356bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1357bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // A ConstantArray is splatable if all its members are equal and also 1358bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // splatable. 1359bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (ConstantArray *CA = dyn_cast<ConstantArray>(V)) { 1360bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (CA->getNumOperands() == 0) 1361bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return 0; 1362bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1363bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner Value *Val = isBytewiseValue(CA->getOperand(0)); 1364bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (!Val) 1365bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return 0; 1366bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1367bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner for (unsigned I = 1, E = CA->getNumOperands(); I != E; ++I) 1368bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner if (CA->getOperand(I-1) != CA->getOperand(I)) 1369bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return 0; 1370bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1371bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return Val; 1372bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner } 1373dce42b75dc05befb4f43b664951c80752904bcdeChad Rosier 1374dce42b75dc05befb4f43b664951c80752904bcdeChad Rosier // FIXME: Vector types (e.g., <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>). 1375bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1376bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // Conceptually, we could handle things like: 1377bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // %a = zext i8 %X to i16 1378bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // %b = shl i16 %a, 8 1379bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // %c = or i16 %a, %b 1380bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // but until there is an example that actually needs this, it doesn't seem 1381bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner // worth worrying about. 1382bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner return 0; 1383bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner} 1384bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1385bb89710dddf967199dfc56e8bf5d28b0003f2ee6Chris Lattner 1386b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This is the recursive version of BuildSubAggregate. It takes a few different 1387b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// arguments. Idxs is the index within the nested struct From that we are 1388b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// looking at now (which is of type IndexedType). IdxSkip is the number of 1389b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// indices from Idxs that should be left out when inserting into the resulting 1390b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct. To is the result struct built so far, new insertvalue instructions 1391b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// build on that. 1392db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerstatic Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType, 13937db949df789383acce98ef072f08794fdd5bd04eDan Gohman SmallVector<unsigned, 10> &Idxs, 13947db949df789383acce98ef072f08794fdd5bd04eDan Gohman unsigned IdxSkip, 13957db949df789383acce98ef072f08794fdd5bd04eDan Gohman Instruction *InsertBefore) { 1396db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner llvm::StructType *STy = llvm::dyn_cast<llvm::StructType>(IndexedType); 1397b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (STy) { 13980a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Save the original To argument so we can modify it 13990a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Value *OrigTo = To; 1400b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // General case, the type indexed by Idxs is a struct 1401b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1402b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Process each struct element recursively 1403b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.push_back(i); 14040a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Value *PrevTo = To; 1405710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip, 1406ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1407b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.pop_back(); 14080a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (!To) { 14090a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Couldn't find any inserted value for this index? Cleanup 14100a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman while (PrevTo != OrigTo) { 14110a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman InsertValueInst* Del = cast<InsertValueInst>(PrevTo); 14120a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman PrevTo = Del->getAggregateOperand(); 14130a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Del->eraseFromParent(); 14140a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman } 14150a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Stop processing elements 14160a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman break; 14170a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman } 1418b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 14197a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // If we successfully found a value for each of our subaggregates 14200a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (To) 14210a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return To; 1422b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 14230a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Base case, the type indexed by SourceIdxs is not a struct, or not all of 14240a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // the struct's elements had a value that was inserted directly. In the latter 14250a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // case, perhaps we can't determine each of the subelements individually, but 14260a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // we might be able to find the complete struct somewhere. 14270a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 14280a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Find the value that is at that particular spot 1429fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad Value *V = FindInsertedValue(From, Idxs); 14300a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 14310a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (!V) 14320a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return NULL; 14330a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 14340a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Insert the value in the new (sub) aggregrate 143539b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel return llvm::InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip), 1436fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad "tmp", InsertBefore); 1437b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 1438b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1439b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This helper takes a nested struct and extracts a part of it (which is again a 1440b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct) into a new value. For example, given the struct: 1441b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { a, { b, { c, d }, e } } 1442b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// and the indices "1, 1" this returns 1443b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { c, d }. 1444b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 14450a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// It does this by inserting an insertvalue for each element in the resulting 14460a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// struct, as opposed to just inserting a single struct. This will only work if 14470a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// each of the elements of the substruct are known (ie, inserted into From by an 14480a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// insertvalue instruction somewhere). 1449b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 14500a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// All inserted insertvalue instructions are inserted before InsertBefore 1451fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foadstatic Value *BuildSubAggregate(Value *From, ArrayRef<unsigned> idx_range, 14527db949df789383acce98ef072f08794fdd5bd04eDan Gohman Instruction *InsertBefore) { 1453977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman assert(InsertBefore && "Must have someplace to insert!"); 1454db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), 1455fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad idx_range); 14569e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Value *To = UndefValue::get(IndexedType); 1457fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end()); 1458b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned IdxSkip = Idxs.size(); 1459b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1460ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); 1461b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 1462b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1463710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// FindInsertedValue - Given an aggregrate and an sequence of indices, see if 1464710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// the scalar value indexed is already around as a register, for example if it 1465710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// were inserted directly into the aggregrate. 14660a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// 14670a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// If InsertBefore is not null, this function will duplicate (modified) 14680a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// insertvalues when a part of a nested struct is extracted. 1469fc6d3a49867cd38954dc40936a88f1907252c6d2Jay FoadValue *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, 1470fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad Instruction *InsertBefore) { 1471b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Nothing to index? Just return V then (this is useful at the end of our 1472b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // recursion) 1473fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad if (idx_range.empty()) 1474b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return V; 1475b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // We have indices, so V should have an indexable type 14761df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) 1477b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman && "Not looking at a struct or array?"); 1478fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) 1479b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman && "Invalid indices for type?"); 1480db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner CompositeType *PTy = cast<CompositeType>(V->getType()); 148176f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson 1482b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (isa<UndefValue>(V)) 14839e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson return UndefValue::get(ExtractValueInst::getIndexedType(PTy, 1484fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad idx_range)); 1485b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman else if (isa<ConstantAggregateZero>(V)) 1486a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson return Constant::getNullValue(ExtractValueInst::getIndexedType(PTy, 1487fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad idx_range)); 1488b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman else if (Constant *C = dyn_cast<Constant>(V)) { 1489b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (isa<ConstantArray>(C) || isa<ConstantStruct>(C)) 1490b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Recursively process this constant 1491fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad return FindInsertedValue(C->getOperand(idx_range[0]), idx_range.slice(1), 1492fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad InsertBefore); 1493b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } else if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) { 1494b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Loop the indices for the insertvalue instruction in parallel with the 1495b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested indices 1496fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad const unsigned *req_idx = idx_range.begin(); 1497710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 1498710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman i != e; ++i, ++req_idx) { 1499fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad if (req_idx == idx_range.end()) { 1500977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman if (InsertBefore) 15010a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // The requested index identifies a part of a nested aggregate. Handle 15020a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // this specially. For example, 15030a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %A = insertvalue { i32, {i32, i32 } } undef, i32 10, 1, 0 15040a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %B = insertvalue { i32, {i32, i32 } } %A, i32 11, 1, 1 15050a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %C = extractvalue {i32, { i32, i32 } } %B, 1 15060a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // This can be changed into 15070a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %A = insertvalue {i32, i32 } undef, i32 10, 0 15080a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %C = insertvalue {i32, i32 } %A, i32 11, 1 15090a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // which allows the unused 0,0 element from the nested struct to be 15100a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // removed. 151139b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx), 1512fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad InsertBefore); 1513977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman else 1514977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman // We can't handle this without inserting insertvalues 1515977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman return 0; 15169954c76f2c89ab3c70bfe8222534621a86f9085aDuncan Sands } 1517b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1518b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // This insert value inserts something else than what we are looking for. 1519b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // See if the (aggregrate) value inserted into has the value we are 1520b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // looking for, then. 1521b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (*req_idx != *i) 1522fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad return FindInsertedValue(I->getAggregateOperand(), idx_range, 1523ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1524b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 1525b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we end up here, the indices of the insertvalue match with those 1526b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested (though possibly only partially). Now we recursively look at 1527b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // the inserted value, passing any remaining indices. 1528fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad return FindInsertedValue(I->getInsertedValueOperand(), 152939b5abf507b43da6b92f68b86406e0015ead18e9Frits van Bommel makeArrayRef(req_idx, idx_range.end()), 1530ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1531b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } else if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) { 1532b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we're extracting a value from an aggregrate that was extracted from 1533b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // something else, we can extract from that something else directly instead. 1534b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // However, we will need to chain I's indices with the requested indices. 1535b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1536b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Calculate the number of indices required 1537fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad unsigned size = I->getNumIndices() + idx_range.size(); 1538b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Allocate some space to put the new indices in 15393faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman SmallVector<unsigned, 5> Idxs; 15403faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman Idxs.reserve(size); 1541b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add indices from the extract value instruction 1542fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad Idxs.append(I->idx_begin(), I->idx_end()); 1543b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1544b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add requested indices 1545fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad Idxs.append(idx_range.begin(), idx_range.end()); 1546b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 15473faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman assert(Idxs.size() == size 1548710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman && "Number of indices added not correct?"); 1549b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1550fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad return FindInsertedValue(I->getAggregateOperand(), Idxs, InsertBefore); 1551b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 1552b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Otherwise, we don't know (such as, extracting from a function return value 1553b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // or load instruction) 1554b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return 0; 1555b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 15560ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 1557ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner/// GetPointerBaseWithConstantOffset - Analyze the specified pointer to see if 1558ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner/// it can be expressed as a base pointer plus a constant offset. Return the 1559ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner/// base and offset to the caller. 1560ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris LattnerValue *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, 1561ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner const TargetData &TD) { 1562ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner Operator *PtrOp = dyn_cast<Operator>(Ptr); 15631608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem if (PtrOp == 0 || Ptr->getType()->isVectorTy()) 15641608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem return Ptr; 1565ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 1566ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner // Just look through bitcasts. 1567ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner if (PtrOp->getOpcode() == Instruction::BitCast) 1568ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner return GetPointerBaseWithConstantOffset(PtrOp->getOperand(0), Offset, TD); 1569ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 1570ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner // If this is a GEP with constant indices, we can look through it. 1571ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner GEPOperator *GEP = dyn_cast<GEPOperator>(PtrOp); 1572ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner if (GEP == 0 || !GEP->hasAllConstantIndices()) return Ptr; 1573ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 1574ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner gep_type_iterator GTI = gep_type_begin(GEP); 1575ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner for (User::op_iterator I = GEP->idx_begin(), E = GEP->idx_end(); I != E; 1576ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner ++I, ++GTI) { 1577ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner ConstantInt *OpC = cast<ConstantInt>(*I); 1578ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner if (OpC->isZero()) continue; 1579ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 1580ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner // Handle a struct and array indices which add their offset to the pointer. 1581db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *STy = dyn_cast<StructType>(*GTI)) { 1582ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner Offset += TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); 1583ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner } else { 1584ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()); 1585ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner Offset += OpC->getSExtValue()*Size; 1586ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner } 1587ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner } 1588ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 1589ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner // Re-sign extend from the pointer size if needed to get overflow edge cases 1590ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner // right. 1591ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner unsigned PtrSize = TD.getPointerSizeInBits(); 1592ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner if (PtrSize < 64) 1593ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner Offset = (Offset << (64-PtrSize)) >> (64-PtrSize); 1594ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 1595ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner return GetPointerBaseWithConstantOffset(GEP->getPointerOperand(), Offset, TD); 1596ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner} 1597ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 1598ed58a6f96f605901adc0df3ca76499d52b2d1a1aChris Lattner 15990ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// GetConstantStringInfo - This function computes the length of a 16000ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// null-terminated C string pointed to by V. If successful, it returns true 16010ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// and returns the string in Str. If unsuccessful, it returns false. 16020a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohmanbool llvm::GetConstantStringInfo(const Value *V, std::string &Str, 16030cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky uint64_t Offset, bool StopAtNul) { 16040582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling // If V is NULL then return false; 16050582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (V == NULL) return false; 16060ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 16070ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Look through bitcast instructions. 16080a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman if (const BitCastInst *BCI = dyn_cast<BitCastInst>(V)) 16090582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return GetConstantStringInfo(BCI->getOperand(0), Str, Offset, StopAtNul); 16100582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling 16110ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // If the value is not a GEP instruction nor a constant expression with a 16120ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // GEP instruction, then return false because ConstantArray can't occur 16130cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky // any other way. 16140a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman const User *GEP = 0; 16150a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) { 16160ff39b3feb10477c224138156941234f5fa46f58Evan Cheng GEP = GEPI; 16170a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 16180ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (CE->getOpcode() == Instruction::BitCast) 16190582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return GetConstantStringInfo(CE->getOperand(0), Str, Offset, StopAtNul); 16200582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (CE->getOpcode() != Instruction::GetElementPtr) 16210582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 16220ff39b3feb10477c224138156941234f5fa46f58Evan Cheng GEP = CE; 16230ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 16240ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 16250ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (GEP) { 16260ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Make sure the GEP has exactly three arguments. 16270582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (GEP->getNumOperands() != 3) 16280582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 16290582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling 16300ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Make sure the index-ee is a pointer to array of i8. 1631db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner PointerType *PT = cast<PointerType>(GEP->getOperand(0)->getType()); 1632db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType()); 1633b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (AT == 0 || !AT->getElementType()->isIntegerTy(8)) 16340582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 16350ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 16360ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Check to make sure that the first operand of the GEP is an integer and 16370ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // has value 0 so that we are sure we're indexing into the initializer. 16380a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1)); 16390582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (FirstIdx == 0 || !FirstIdx->isZero()) 16400582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 16410ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 16420ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // If the second index isn't a ConstantInt, then this is a variable index 16430ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // into the array. If this occurs, we can't say anything meaningful about 16440ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // the string. 16450ff39b3feb10477c224138156941234f5fa46f58Evan Cheng uint64_t StartIdx = 0; 16460a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 16470ff39b3feb10477c224138156941234f5fa46f58Evan Cheng StartIdx = CI->getZExtValue(); 16480582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling else 16490582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 16500582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return GetConstantStringInfo(GEP->getOperand(0), Str, StartIdx+Offset, 16510ff39b3feb10477c224138156941234f5fa46f58Evan Cheng StopAtNul); 16520ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 16530cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky 16540ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // The GEP instruction, constant or instruction, must reference a global 16550ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // variable that is a constant and is initialized. The referenced constant 16560ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // initializer is the array that we'll use for optimization. 16570a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman const GlobalVariable* GV = dyn_cast<GlobalVariable>(V); 16588255573835970e7130ba93271972172fb335f2ecDan Gohman if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) 16590582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 16600a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman const Constant *GlobalInit = GV->getInitializer(); 16610ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 16620cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky // Handle the all-zeros case 16630cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky if (GlobalInit->isNullValue()) { 16640ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // This is a degenerate case. The initializer is constant zero so the 16650ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // length of the string must be zero. 16660582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling Str.clear(); 16670582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; 16680582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling } 16690ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 16700ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Must be a Constant Array 16710a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman const ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit); 1672b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (Array == 0 || !Array->getType()->getElementType()->isIntegerTy(8)) 16730582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 16740ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 16750ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Get the number of elements in the array 16760ff39b3feb10477c224138156941234f5fa46f58Evan Cheng uint64_t NumElts = Array->getType()->getNumElements(); 16770ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 16780582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (Offset > NumElts) 16790582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 16800ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 16810ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Traverse the constant array from 'Offset' which is the place the GEP refers 16820ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // to in the array. 16830582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling Str.reserve(NumElts-Offset); 16840ff39b3feb10477c224138156941234f5fa46f58Evan Cheng for (unsigned i = Offset; i != NumElts; ++i) { 16850a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman const Constant *Elt = Array->getOperand(i); 16860a60fa33210202a38a59ae3ea8681216f234ce51Dan Gohman const ConstantInt *CI = dyn_cast<ConstantInt>(Elt); 16870582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (!CI) // This array isn't suitable, non-int initializer. 16880582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 16890ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (StopAtNul && CI->isZero()) 16900582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; // we found end of string, success! 16910582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling Str += (char)CI->getZExtValue(); 16920ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 16930582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling 16940ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // The array isn't null terminated, but maybe this is a memcpy, not a strcpy. 16950582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; 16960ff39b3feb10477c224138156941234f5fa46f58Evan Cheng} 169725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 169825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher// These next two are very similar to the above, but also look through PHI 169925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher// nodes. 170025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher// TODO: See if we can integrate these two together. 170125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 170225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// GetStringLengthH - If we can compute the length of the string pointed to by 170325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// the specified pointer, return 'len+1'. If we can't, return 0. 170425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopherstatic uint64_t GetStringLengthH(Value *V, SmallPtrSet<PHINode*, 32> &PHIs) { 170525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Look through noop bitcast instructions. 170625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) 170725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return GetStringLengthH(BCI->getOperand(0), PHIs); 170825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 170925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If this is a PHI node, there are two cases: either we have already seen it 171025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // or we haven't. 171125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (PHINode *PN = dyn_cast<PHINode>(V)) { 171225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!PHIs.insert(PN)) 171325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return ~0ULL; // already in the set. 171425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 171525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If it was new, see if all the input strings are the same length. 171625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t LenSoFar = ~0ULL; 171725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 171825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len = GetStringLengthH(PN->getIncomingValue(i), PHIs); 171925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len == 0) return 0; // Unknown length -> unknown. 172025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 172125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len == ~0ULL) continue; 172225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 172325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len != LenSoFar && LenSoFar != ~0ULL) 172425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; // Disagree -> unknown. 172525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher LenSoFar = Len; 172625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 172725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 172825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Success, all agree. 172925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return LenSoFar; 173025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 173125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 173225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y) 173325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 173425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs); 173525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len1 == 0) return 0; 173625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs); 173725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len2 == 0) return 0; 173825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len1 == ~0ULL) return Len2; 173925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len2 == ~0ULL) return Len1; 174025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len1 != Len2) return 0; 174125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return Len1; 174225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 174325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 17440cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky // As a special-case, "@string = constant i8 0" is also a string with zero 17450cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky // length, not wrapped in a bitcast or GEP. 17460cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 17470cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky if (GV->isConstant() && GV->hasDefinitiveInitializer()) 17480cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky if (GV->getInitializer()->isNullValue()) return 1; 17490cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky return 0; 17500cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky } 17510cd0fee91eadcee37d01398e05176e7c63bda2a7Nick Lewycky 175225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If the value is not a GEP instruction nor a constant expression with a 175325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // GEP instruction, then return unknown. 175425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher User *GEP = 0; 175525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) { 175625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher GEP = GEPI; 175725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 175825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (CE->getOpcode() != Instruction::GetElementPtr) 175925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 176025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher GEP = CE; 176125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } else { 176225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 176325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 176425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 176525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Make sure the GEP has exactly three arguments. 176625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (GEP->getNumOperands() != 3) 176725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 176825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 176925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Check to make sure that the first operand of the GEP is an integer and 177025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // has value 0 so that we are sure we're indexing into the initializer. 177125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(1))) { 177225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!Idx->isZero()) 177325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 177425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } else 177525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 177625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 177725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If the second index isn't a ConstantInt, then this is a variable index 177825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // into the array. If this occurs, we can't say anything meaningful about 177925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // the string. 178025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t StartIdx = 0; 178125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 178225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher StartIdx = CI->getZExtValue(); 178325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher else 178425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 178525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 178625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // The GEP instruction, constant or instruction, must reference a global 178725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // variable that is a constant and is initialized. The referenced constant 178825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // initializer is the array that we'll use for optimization. 178925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)); 179025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!GV || !GV->isConstant() || !GV->hasInitializer() || 179125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher GV->mayBeOverridden()) 179225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 179325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher Constant *GlobalInit = GV->getInitializer(); 179425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 179525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Handle the ConstantAggregateZero case, which is a degenerate case. The 179625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // initializer is constant zero so the length of the string must be zero. 179725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (isa<ConstantAggregateZero>(GlobalInit)) 179825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 1; // Len = 0 offset by 1. 179925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 180025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Must be a Constant Array 180125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit); 180225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!Array || !Array->getType()->getElementType()->isIntegerTy(8)) 180325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return false; 180425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 180525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Get the number of elements in the array 180625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t NumElts = Array->getType()->getNumElements(); 180725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 180825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Traverse the constant array from StartIdx (derived above) which is 180925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // the place the GEP refers to in the array. 181025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher for (unsigned i = StartIdx; i != NumElts; ++i) { 181125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher Constant *Elt = Array->getOperand(i); 181225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher ConstantInt *CI = dyn_cast<ConstantInt>(Elt); 181325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!CI) // This array isn't suitable, non-int initializer. 181425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 181525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (CI->isZero()) 181625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return i-StartIdx+1; // We found end of string, success! 181725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 181825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 181925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; // The array isn't null terminated, conservatively return 'unknown'. 182025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher} 182125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 182225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// GetStringLength - If we can compute the length of the string pointed to by 182325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// the specified pointer, return 'len+1'. If we can't, return 0. 182425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopheruint64_t llvm::GetStringLength(Value *V) { 182525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!V->getType()->isPointerTy()) return 0; 182625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 182725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher SmallPtrSet<PHINode*, 32> PHIs; 182825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len = GetStringLengthH(V, PHIs); 182925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return 183025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // an empty string as a length. 183125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return Len == ~0ULL ? 1 : Len; 183225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher} 18335034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman 1834bd1801b5553c8be3960255a92738464e0010b6f6Dan GohmanValue * 1835bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohmanllvm::GetUnderlyingObject(Value *V, const TargetData *TD, unsigned MaxLookup) { 18365034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman if (!V->getType()->isPointerTy()) 18375034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman return V; 18385034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) { 18395034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 18405034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman V = GEP->getPointerOperand(); 18415034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } else if (Operator::getOpcode(V) == Instruction::BitCast) { 18425034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman V = cast<Operator>(V)->getOperand(0); 18435034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 18445034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman if (GA->mayBeOverridden()) 18455034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman return V; 18465034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman V = GA->getAliasee(); 18475034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } else { 1848c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman // See if InstructionSimplify knows any relevant tricks. 1849c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman if (Instruction *I = dyn_cast<Instruction>(V)) 18507a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // TODO: Acquire a DominatorTree and use it. 1851bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman if (Value *Simplified = SimplifyInstruction(I, TD, 0)) { 1852c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman V = Simplified; 1853c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman continue; 1854c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman } 1855c01895c7db4c4d8883dd4c31427c42cdae356567Dan Gohman 18565034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman return V; 18575034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } 18585034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 18595034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } 18605034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman return V; 18615034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman} 186299e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky 186399e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky/// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer 186499e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky/// are lifetime markers. 186599e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky/// 186699e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewyckybool llvm::onlyUsedByLifetimeMarkers(const Value *V) { 186799e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 186899e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky UI != UE; ++UI) { 186999e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky const IntrinsicInst *II = dyn_cast<IntrinsicInst>(*UI); 187099e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky if (!II) return false; 187199e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky 187299e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky if (II->getIntrinsicID() != Intrinsic::lifetime_start && 187399e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky II->getIntrinsicID() != Intrinsic::lifetime_end) 187499e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky return false; 187599e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky } 187699e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky return true; 187799e0b2a8df7e3a49c0e1edd250d17604fe2fb21cNick Lewycky} 1878